Utility-Driven Graph Summarization

Summary: Introduces iterative graph summarization that incrementally tracks utility, enabling summaries conditioned on a user-specified utility threshold. Provides exhaustive and scalable algorithms, validated on real graphs and applications to balance compression against task usefulness. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 12157
Venue: VLDB
Year: 2019
Pagerank: 5.9355329e-05
Overall Rank: 6,266 | 57.02%
DOI: 10.14778/3297753.3297755

Incoming Non-self Citations Over Time

Authors

1. K. Ashwin Kumar (Symantec Research Labs)
2. Petros Efstathopoulos (Symantec Research Labs)

BibTeX Citation

@article{kumar_vldb19,
        title = {{Utility-Driven Graph Summarization}},
        author = {Kumar, K. Ashwin and Efstathopoulos, Petros},
        journal = {PVLDB},
        series = {{VLDB} '19},
        volume = {12},
        number = {4},
        pages = {335--347},
        doi = {10.14778/3297753.3297755},
        url = {https://doi.org/10.14778/3297753.3297755},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,953	Efficient Graph Summarization using Weighted LSH at Billion-Scale	2021	SIGMOD	6.4303691e-05
6,054	Causal Data Integration	2023	VLDB	5.9932261e-05
11,241	Poligras: Policy-based Graph Summarization	2024	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
486	Efficient Aggregation for Graph Summarization	2008	SIGMOD	0.00017692185
548	Graph Summarization with Bounded Error	2008	SIGMOD	0.00016694936
1,326	Resisting Structural Re-identification in Anonymized Social Networks	2008	VLDB	0.00011145219
6,201	Generating Preview Tables for Entity Graphs	2016	SIGMOD	5.9455064e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,408	CompressGraph: Efficient Parallel Graph Analytics with Rule-Based Compression	2023	SIGMOD
2	13,467	The Power of Summarization in Graph Mining and Learning: Smaller Data, Faster Methods, More Interpretability	2021	VLDB
3	8,274	Query-Oriented Summarization of RDF Graphs	2015	VLDB
4	2,148	Graph Stream Summarization: From Big Bang to Big Crunch	2016	SIGMOD
5	11,178	Graph Summarization: Compactness Meets Efficiency	2024	SIGMOD
6	5,849	Summarizing Answer Graphs Induced by Keyword Queries	2013	VLDB
7	4,953	Efficient Graph Summarization using Weighted LSH at Billion-Scale	2021	SIGMOD
8	548	Graph Summarization with Bounded Error	2008	SIGMOD
9	486	Efficient Aggregation for Graph Summarization	2008	SIGMOD
10	5,751	Summarizing Static and Dynamic Big Graphs	2017	VLDB