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: 4067
Venue: SIGMOD
Year: 2008
Pagerank: 0.00016694936
Overall Rank: 548 | 96.25%
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
364	Graph Clustering Based on Structural/Attribute Similarities	2009	VLDB	0.00020054172
1,069	Truss-based Community Search: a Truss-equivalence Based Indexing Approach	2017	VLDB	0.00012323497
1,336	Query Preserving Graph Compression	2012	SIGMOD	0.00011118804
1,487	Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs	2015	VLDB	0.00010615297
3,119	GConnect: A Connectivity Index for Massive Disk-Resident Graphs	2009	VLDB	7.7370163e-05
3,160	Graph Cube: On Warehousing and OLAP Multidimensional Networks	2011	SIGMOD	7.6823631e-05
4,236	On Dense Pattern Mining in Graph Streams	2010	VLDB	6.8164649e-05
4,474	Querying Big Graphs within Bounded Resources	2014	SIGMOD	6.6803983e-05
4,497	Leveraging History for Faster Sampling of Online Social Networks	2015	VLDB	6.6618536e-05
4,581	Mining Graph Patterns Efficiently via Randomized Summaries	2009	VLDB	6.6198548e-05
4,953	Efficient Graph Summarization using Weighted LSH at Billion-Scale	2021	SIGMOD	6.4303691e-05
5,415	Making Graphs Compact by Lossless Contraction	2021	SIGMOD	6.2255551e-05
5,751	Summarizing Static and Dynamic Big Graphs	2017	VLDB	6.0994565e-05
5,849	Summarizing Answer Graphs Induced by Keyword Queries	2013	VLDB	6.0666529e-05
6,266	Utility-Driven Graph Summarization	2019	VLDB	5.9355329e-05
7,624	RECEIPT: REfine CoarsE-grained IndePendent Tasks for Parallel Tip decomposition of Bipartite Graphs	2021	VLDB	5.5805027e-05
7,933	PAnG - Finding Patterns in Annotation Graphs	2012	SIGMOD	5.5181056e-05
8,117	Realtime Analysis of Information Diffusion in Social Media	2013	VLDB	5.4837975e-05
8,245	The shortest path is not always a straight line: Leveraging semi-metricity in graph analysis	2016	VLDB	5.4577751e-05
9,055	Causal DAG Summarization	2025	VLDB	5.3251649e-05
10,376	GraphTwin: Cache-Centric Bit-Level Graph Representation for Fast and Exact Graph Queries	2026	SIGMOD	5.093636e-05
11,178	Graph Summarization: Compactness Meets Efficiency	2024	SIGMOD	5.093636e-05
11,241	Poligras: Policy-based Graph Summarization	2024	VLDB	5.093636e-05
11,853	Anti-Freeze for Large and Complex Spreadsheets: Asynchronous Formula Computation	2019	SIGMOD	5.093636e-05
12,294	Making Queries Tractable on Big Data with Preprocessing (through the eyes of complexity theory)	2013	VLDB	5.093636e-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.00077458002
138	Discovering Large Dense Subgraphs in Massive Graphs	2005	VLDB	0.00029823423
230	Gigascope: A Stream Database for Network Applications	2003	SIGMOD	0.00023891474
307	Approximate Query Processing Using Wavelets	2000	VLDB	0.00021792475
435	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB	0.000185063
1,721	Semantic Compression and Pattern Extraction with Fascicles	1999	VLDB	9.9258415e-05
2,382	The Generalized MDL Approach for Summarization	2002	VLDB	8.6603462e-05
5,980	Extracting large-scale knowledge bases from the web	1999	VLDB	6.0211324e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,849	Summarizing Answer Graphs Induced by Keyword Queries	2013	VLDB
2	486	Efficient Aggregation for Graph Summarization	2008	SIGMOD
3	10,450	Enabling Efficient Direct Update on Rule-Based Compressed Graph	2026	SIGMOD
4	4,581	Mining Graph Patterns Efficiently via Randomized Summaries	2009	VLDB
5	6,408	CompressGraph: Efficient Parallel Graph Analytics with Rule-Based Compression	2023	SIGMOD
6	5,415	Making Graphs Compact by Lossless Contraction	2021	SIGMOD
7	11,178	Graph Summarization: Compactness Meets Efficiency	2024	SIGMOD
8	1,336	Query Preserving Graph Compression	2012	SIGMOD
9	6,266	Utility-Driven Graph Summarization	2019	VLDB
10	4,953	Efficient Graph Summarization using Weighted LSH at Billion-Scale	2021	SIGMOD