DBScholar

Back to papers

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.00016319495
Overall Rank
563 | 96.22%
DOI
10.1145/1376616.1376661

Incoming Non-self Citations Over Time

Authors

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.00019619557
1,092 Truss-based Community Search: a Truss-equivalence Based Indexing Approach 2017 VLDB 0.00012066667
1,375 Query Preserving Graph Compression 2012 SIGMOD 0.00010872356
1,507 Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs 2015 VLDB 0.00010447258
3,169 GConnect: A Connectivity Index for Massive Disk-Resident Graphs 2009 VLDB 7.5687463e-05
3,224 Graph Cube: On Warehousing and OLAP Multidimensional Networks 2011 SIGMOD 7.5099873e-05
4,321 On Dense Pattern Mining in Graph Streams 2010 VLDB 6.6635292e-05
4,550 Querying Big Graphs within Bounded Resources 2014 SIGMOD 6.5380867e-05
4,562 Leveraging History for Faster Sampling of Online Social Networks 2015 VLDB 6.5312909e-05
4,650 Mining Graph Patterns Efficiently via Randomized Summaries 2009 VLDB 6.4837167e-05
5,079 Efficient Graph Summarization using Weighted LSH at Billion-Scale 2021 SIGMOD 6.2831131e-05
5,556 Making Graphs Compact by Lossless Contraction 2021 SIGMOD 6.0829894e-05
5,661 Summarizing Static and Dynamic Big Graphs 2017 VLDB 6.0449991e-05
5,924 Summarizing Answer Graphs Induced by Keyword Queries 2013 VLDB 5.9429979e-05
6,391 Utility-Driven Graph Summarization 2019 VLDB 5.7996087e-05
7,753 RECEIPT: REfine CoarsE-grained IndePendent Tasks for Parallel Tip decomposition of Bipartite Graphs 2021 VLDB 5.4575542e-05
8,108 PAnG - Finding Patterns in Annotation Graphs 2012 SIGMOD 5.3917406e-05
8,304 Realtime Analysis of Information Diffusion in Social Media 2013 VLDB 5.3582183e-05
8,421 The shortest path is not always a straight line: Leveraging semi-metricity in graph analysis 2016 VLDB 5.3327977e-05
9,241 Causal DAG Summarization 2025 VLDB 5.2032182e-05
10,584 GraphTwin: Cache-Centric Bit-Level Graph Representation for Fast and Exact Graph Queries 2026 SIGMOD 4.9769913e-05
11,529 Graph Summarization: Compactness Meets Efficiency 2024 SIGMOD 4.9769913e-05
11,580 Poligras: Policy-based Graph Summarization 2024 VLDB 4.9769913e-05
12,159 Anti-Freeze for Large and Complex Spreadsheets: Asynchronous Formula Computation 2019 SIGMOD 4.9769913e-05
12,591 Making Queries Tractable on Big Data with Preprocessing (through the eyes of complexity theory) 2013 VLDB 4.9769913e-05
Previous Page 1 / 1 Next

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.00076265429
131 Discovering Large Dense Subgraphs in Massive Graphs 2005 VLDB 0.00030236369
240 Gigascope: A Stream Database for Network Applications 2003 SIGMOD 0.00023425462
309 Approximate Query Processing Using Wavelets 2000 VLDB 0.00021376597
448 Histogram-Based Approximation of Set-Valued Query Answers 1999 VLDB 0.00018121533
1,758 Semantic Compression and Pattern Extraction with Fascicles 1999 VLDB 9.7095435e-05
2,435 The Generalized MDL Approach for Summarization 2002 VLDB 8.4706335e-05
6,106 Extracting large-scale knowledge bases from the web 1999 VLDB 5.8836299e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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