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.00016294243
Overall Rank
563 | 96.23%
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
373 Graph Clustering Based on Structural/Attribute Similarities 2009 VLDB 0.00019709993
1,045 Truss-based Community Search: a Truss-equivalence Based Indexing Approach 2017 VLDB 0.00012318828
1,376 Query Preserving Graph Compression 2012 SIGMOD 0.00010857788
1,502 Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs 2015 VLDB 0.00010431532
3,150 GConnect: A Connectivity Index for Massive Disk-Resident Graphs 2009 VLDB 7.5754686e-05
3,235 Graph Cube: On Warehousing and OLAP Multidimensional Networks 2011 SIGMOD 7.4859375e-05
4,323 On Dense Pattern Mining in Graph Streams 2010 VLDB 6.650678e-05
4,568 Querying Big Graphs within Bounded Resources 2014 SIGMOD 6.5171208e-05
4,576 Leveraging History for Faster Sampling of Online Social Networks 2015 VLDB 6.5118467e-05
4,666 Mining Graph Patterns Efficiently via Randomized Summaries 2009 VLDB 6.4630612e-05
5,102 Efficient Graph Summarization using Weighted LSH at Billion-Scale 2021 SIGMOD 6.2623372e-05
5,571 Making Graphs Compact by Lossless Contraction 2021 SIGMOD 6.0628752e-05
5,628 Summarizing Static and Dynamic Big Graphs 2017 VLDB 6.0438005e-05
5,937 Summarizing Answer Graphs Induced by Keyword Queries 2013 VLDB 5.9241313e-05
6,401 Utility-Driven Graph Summarization 2019 VLDB 5.7804316e-05
7,752 RECEIPT: REfine CoarsE-grained IndePendent Tasks for Parallel Tip decomposition of Bipartite Graphs 2021 VLDB 5.4440674e-05
8,126 PAnG - Finding Patterns in Annotation Graphs 2012 SIGMOD 5.3739121e-05
8,318 Realtime Analysis of Information Diffusion in Social Media 2013 VLDB 5.3405011e-05
8,399 The shortest path is not always a straight line: Leveraging semi-metricity in graph analysis 2016 VLDB 5.3235867e-05
9,265 Causal DAG Summarization 2025 VLDB 5.1860131e-05
10,647 GraphTwin: Cache-Centric Bit-Level Graph Representation for Fast and Exact Graph Queries 2026 SIGMOD 4.9605343e-05
11,578 Graph Summarization: Compactness Meets Efficiency 2024 SIGMOD 4.9605343e-05
11,629 Poligras: Policy-based Graph Summarization 2024 VLDB 4.9605343e-05
12,202 Anti-Freeze for Large and Complex Spreadsheets: Asynchronous Formula Computation 2019 SIGMOD 4.9605343e-05
12,634 Making Queries Tractable on Big Data with Preprocessing (through the eyes of complexity theory) 2013 VLDB 4.9605343e-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.00076079812
130 Discovering Large Dense Subgraphs in Massive Graphs 2005 VLDB 0.0003029792
240 Gigascope: A Stream Database for Network Applications 2003 SIGMOD 0.00023371986
311 Approximate Query Processing Using Wavelets 2000 VLDB 0.00021315058
450 Histogram-Based Approximation of Set-Valued Query Answers 1999 VLDB 0.0001806593
1,768 Semantic Compression and Pattern Extraction with Fascicles 1999 VLDB 9.6803078e-05
2,444 The Generalized MDL Approach for Summarization 2002 VLDB 8.4450845e-05
6,115 Extracting large-scale knowledge bases from the web 1999 VLDB 5.86577e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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