Graph Summarization with Bounded Error

Summary: Two-part graph representation: a summary graph and a corrections set, enabling lossless or lossy compression with provable bounded error. First to apply MDL to graph summarization; MDL-based summaries with corrections enable compact, bounded-error reconstructions, validated on real data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h31af2f9774772469
Venue: SIGMOD
Year: 2008
Pagerank: 0.00016327158
Overall Rank: 563 | 96.22%
DOI: 10.1145/1376616.1376661

Incoming Non-self Citations Over Time

Authors

1. Saket Navlakha (AT&T; University of Maryland)
2. Rajeev Rastogi (AT&T; Yahoo)
3. Nisheeth Shrivastava (AT&T)

BibTeX Citation

@inproceedings{navlakha_sigmod08,
        title = {{Graph Summarization with Bounded Error}},
        author = {Navlakha, Saket and Rastogi, Rajeev and Shrivastava, Nisheeth},
        series = {{SIGMOD} '08},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1376616.1376661},
        url = {https://dl.acm.org/doi/10.1145/1376616.1376661},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 25 of 25 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
375	Graph Clustering Based on Structural/Attribute Similarities	2009	VLDB	0.00019628745
1,092	Truss-based Community Search: a Truss-equivalence Based Indexing Approach	2017	VLDB	0.00012072382
1,375	Query Preserving Graph Compression	2012	SIGMOD	0.00010877488
1,506	Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs	2015	VLDB	0.00010452205
3,168	GConnect: A Connectivity Index for Massive Disk-Resident Graphs	2009	VLDB	7.5723309e-05
3,222	Graph Cube: On Warehousing and OLAP Multidimensional Networks	2011	SIGMOD	7.5135441e-05
4,320	On Dense Pattern Mining in Graph Streams	2010	VLDB	6.6666852e-05
4,551	Querying Big Graphs within Bounded Resources	2014	SIGMOD	6.5401646e-05
4,560	Leveraging History for Faster Sampling of Online Social Networks	2015	VLDB	6.5343842e-05
4,647	Mining Graph Patterns Efficiently via Randomized Summaries	2009	VLDB	6.4867875e-05
5,075	Efficient Graph Summarization using Weighted LSH at Billion-Scale	2021	SIGMOD	6.2860889e-05
5,554	Making Graphs Compact by Lossless Contraction	2021	SIGMOD	6.0858703e-05
5,660	Summarizing Static and Dynamic Big Graphs	2017	VLDB	6.0478621e-05
5,924	Summarizing Answer Graphs Induced by Keyword Queries	2013	VLDB	5.9458126e-05
6,388	Utility-Driven Graph Summarization	2019	VLDB	5.8023555e-05
7,747	RECEIPT: REfine CoarsE-grained IndePendent Tasks for Parallel Tip decomposition of Bipartite Graphs	2021	VLDB	5.4601389e-05
8,101	PAnG - Finding Patterns in Annotation Graphs	2012	SIGMOD	5.3942942e-05
8,298	Realtime Analysis of Information Diffusion in Social Media	2013	VLDB	5.360756e-05
8,413	The shortest path is not always a straight line: Leveraging semi-metricity in graph analysis	2016	VLDB	5.3353234e-05
9,231	Causal DAG Summarization	2025	VLDB	5.2056825e-05
10,573	GraphTwin: Cache-Centric Bit-Level Graph Representation for Fast and Exact Graph Queries	2026	SIGMOD	4.9793485e-05
11,523	Graph Summarization: Compactness Meets Efficiency	2024	SIGMOD	4.9793485e-05
11,574	Poligras: Policy-based Graph Summarization	2024	VLDB	4.9793485e-05
12,153	Anti-Freeze for Large and Complex Spreadsheets: Asynchronous Formula Computation	2019	SIGMOD	4.9793485e-05
12,585	Making Queries Tractable on Big Data with Preprocessing (through the eyes of complexity theory)	2013	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
9	Online Aggregation	1997	SIGMOD	0.00076195956
131	Discovering Large Dense Subgraphs in Massive Graphs	2005	VLDB	0.00030242586
240	Gigascope: A Stream Database for Network Applications	2003	SIGMOD	0.00023435436
309	Approximate Query Processing Using Wavelets	2000	VLDB	0.00021384073
448	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB	0.00018129161
1,756	Semantic Compression and Pattern Extraction with Fascicles	1999	VLDB	9.7140303e-05
2,434	The Generalized MDL Approach for Summarization	2002	VLDB	8.4746361e-05
6,103	Extracting large-scale knowledge bases from the web	1999	VLDB	5.8864128e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,924	Summarizing Answer Graphs Induced by Keyword Queries	2013	VLDB
2	497	Efficient Aggregation for Graph Summarization	2008	SIGMOD
3	10,638	Enabling Efficient Direct Update on Rule-Based Compressed Graph	2026	SIGMOD
4	4,647	Mining Graph Patterns Efficiently via Randomized Summaries	2009	VLDB
5	6,526	CompressGraph: Efficient Parallel Graph Analytics with Rule-Based Compression	2023	SIGMOD
6	5,554	Making Graphs Compact by Lossless Contraction	2021	SIGMOD
7	11,523	Graph Summarization: Compactness Meets Efficiency	2024	SIGMOD
8	1,375	Query Preserving Graph Compression	2012	SIGMOD
9	6,388	Utility-Driven Graph Summarization	2019	VLDB
10	5,075	Efficient Graph Summarization using Weighted LSH at Billion-Scale	2021	SIGMOD