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: h4eb762af1a85580f
Venue: VLDB
Year: 2019
Pagerank: 5.8023555e-05
Overall Rank: 6,388 | 57.06%
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
5,075	Efficient Graph Summarization using Weighted LSH at Billion-Scale	2021	SIGMOD	6.2860889e-05
6,183	Causal Data Integration	2023	VLDB	5.8587542e-05
11,574	Poligras: Policy-based Graph Summarization	2024	VLDB	4.9793485e-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
497	Efficient Aggregation for Graph Summarization	2008	SIGMOD	0.00017318153
563	Graph Summarization with Bounded Error	2008	SIGMOD	0.00016327158
1,367	Resisting Structural Re-identification in Anonymized Social Networks	2008	VLDB	0.00010911008
6,331	Generating Preview Tables for Entity Graphs	2016	SIGMOD	5.8121052e-05

Semantically Similar Papers

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