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: 4005
Venue: SIGMOD
Year: 2008
Pagerank: 0.00024662272
Overall Rank: 388 | 97.31%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 25 of 25 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
313	Graph Clustering Based on Structural/Attribute Similarities	2009	VLDB	0.00028097557
1,530	Truss-based Community Search: a Truss-equivalence Based Indexing Approach	2017	VLDB	0.00011495611
1,579	Query Preserving Graph Compression	2012	SIGMOD	0.00011283792
2,007	Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs	2015	VLDB	9.8081235e-05
2,048	Graph Cube: On Warehousing and OLAP Multidimensional Networks	2011	SIGMOD	9.6914395e-05
2,108	Leveraging History for Faster Sampling of Online Social Networks	2015	VLDB	9.5327714e-05
3,020	GConnect: A Connectivity Index for Massive Disk-Resident Graphs	2009	VLDB	7.6992238e-05
4,089	On Dense Pattern Mining in Graph Streams [Extended Abstract]	2010	VLDB	6.4587806e-05
4,211	Querying Big Graphs within Bounded Resources	2014	SIGMOD	6.3563454e-05
4,716	Mining Graph Patterns Efficiently via Randomized Summaries	2009	VLDB	5.9755569e-05
4,761	Efficient Graph Summarization using Weighted LSH at Billion-Scale	2021	SIGMOD	5.9404527e-05
4,836	Making Graphs Compact by Lossless Contraction	2021	SIGMOD	5.8896897e-05
5,968	Summarizing Static and Dynamic Big Graphs	2017	VLDB	5.2503253e-05
6,210	Summarizing Answer Graphs Induced by Keyword Queries	2013	VLDB	5.1560547e-05
6,329	Utility-Driven Graph Summarization	2019	VLDB	5.1077685e-05
7,512	PAnG - Finding Patterns in Annotation Graphs	2012	SIGMOD	4.7180617e-05
7,801	Realtime Analysis of Information Diffusion in Social Media	2013	VLDB	4.6469803e-05
7,804	RECEIPT: REfine CoarsE-grained IndePendent Tasks for Parallel Tip decomposition of Bipartite Graphs	2021	VLDB	4.6466513e-05
8,070	The shortest path is not always a straight line: Leveraging semi-metricity in graph analysis	2016	VLDB	4.5932982e-05
10,085	GraphTwin: Cache-Centric Bit-Level Graph Representation for Fast and Exact Graph Queries	2026	SIGMOD	4.1945683e-05
10,581	Causal DAG Summarization	2025	VLDB	4.1945683e-05
10,964	Graph Summarization: Compactness Meets Efficiency	2024	SIGMOD	4.1945683e-05
11,031	Poligras: Policy-based Graph Summarization	2024	VLDB	4.1945683e-05
11,658	Anti-Freeze for Large and Complex Spreadsheets: Asynchronous Formula Computation	2019	SIGMOD	4.1945683e-05
12,097	Making Queries Tractable on Big Data with Preprocessing (through the eyes of complexity theory)	2013	VLDB	4.1945683e-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
14	Online Aggregation	1997	SIGMOD	0.0010801504
57	Discovering Large Dense Subgraphs in Massive Graphs	2005	VLDB	0.00065491112
323	Gigascope: A Stream Database for Network Applications	2003	SIGMOD	0.00027492196
361	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB	0.00025775749
405	Approximate Query Processing Using Wavelets	2000	VLDB	0.00024057494
1,598	Semantic Compression and Pattern Extraction with Fascicles	1999	VLDB	0.00011202905
2,074	The Generalized MDL Approach for Summarization	2002	VLDB	9.6134804e-05
4,676	Extracting large-scale knowledge bases from the web	1999	VLDB	6.0052781e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,210	Summarizing Answer Graphs Induced by Keyword Queries	2013	VLDB	5.1560547e-05
435	Efficient Aggregation for Graph Summarization	2008	SIGMOD	0.00023260172
10,161	Enabling Efficient Direct Update on Rule-Based Compressed Graph	2026	SIGMOD	4.1945683e-05
4,716	Mining Graph Patterns Efficiently via Randomized Summaries	2009	VLDB	5.9755569e-05
6,985	CompressGraph: Efficient Parallel Graph Analytics with Rule-Based Compression	2023	SIGMOD	4.8729387e-05
4,836	Making Graphs Compact by Lossless Contraction	2021	SIGMOD	5.8896897e-05
10,964	Graph Summarization: Compactness Meets Efficiency	2024	SIGMOD	4.1945683e-05
1,579	Query Preserving Graph Compression	2012	SIGMOD	0.00011283792
6,329	Utility-Driven Graph Summarization	2019	VLDB	5.1077685e-05
4,761	Efficient Graph Summarization using Weighted LSH at Billion-Scale	2021	SIGMOD	5.9404527e-05