Making Graphs Compact by Lossless Contraction

Summary: Introduces lossless graph contraction into supernodes carrying per-query-class synopses S_Q, enabling exact answers with on-demand decontraction. Generic across label-based or not, local or global queries; adapts existing algorithms (subgraph isomorphism, triangle counting, shortest path) with incremental updates, achieving ~71% compression and ~1.5–2.1x speedups. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hd25dd00b24ce0913
Venue: SIGMOD
Year: 2021
Pagerank: 6.0858703e-05
Overall Rank: 5,554 | 62.66%
DOI: 10.1145/3448016.3452797

Incoming Non-self Citations Over Time

Authors

1. Wenfei Fan (Beihang University; Shenzhen University; University of Edinburgh)
2. Yuanhao Li (University of Edinburgh)
3. Muyang Liu (University of Edinburgh)
4. Can Lu (Shenzhen University)

BibTeX Citation

@inproceedings{fan_sigmod21,
        title = {{Making Graphs Compact by Lossless Contraction}},
        author = {Fan, Wenfei and Li, Yuanhao and Liu, Muyang and Lu, Can},
        series = {{SIGMOD} '21},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3448016.3452797},
        url = {https://dl.acm.org/doi/10.1145/3448016.3452797},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,015	A Hierarchical Contraction Scheme for Querying Big Graphs	2022	SIGMOD	5.6210836e-05
10,573	GraphTwin: Cache-Centric Bit-Level Graph Representation for Fast and Exact Graph Queries	2026	SIGMOD	4.9793485e-05
11,523	Graph Summarization: Compactness Meets Efficiency	2024	SIGMOD	4.9793485e-05
11,574	Poligras: Policy-based Graph Summarization	2024	VLDB	4.9793485e-05
11,662	Neighborhood-Preserving Graph Sparsification	2024	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 16 of 16 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
197	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00025584127
490	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017438618
497	Efficient Aggregation for Graph Summarization	2008	SIGMOD	0.00017318153
563	Graph Summarization with Bounded Error	2008	SIGMOD	0.00016327158
600	Massive Graph Triangulation	2013	SIGMOD	0.00015740352
657	Efficient Subgraph Matching by Postponing Cartesian Products	2016	SIGMOD	0.0001505607
693	GRAIL: Scalable Reachability Index for Large Graphs	2010	VLDB	0.00014734389
774	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00014083518
960	Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together	2019	SIGMOD	0.00012836554
1,100	CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching	2019	SIGMOD	0.00012013426
1,375	Query Preserving Graph Compression	2012	SIGMOD	0.00010877488
1,506	Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs	2015	VLDB	0.00010452205
1,507	Finding the Maximum Clique in Massive Graphs	2017	VLDB	0.00010450256
1,563	TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph	2013	SIGMOD	0.00010224369
2,851	Incremental Graph Computations: Doable and Undoable	2017	SIGMOD	7.9419904e-05
8,177	Data Management for Social Networking	2016	PODS	5.3829638e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,329	A Memory Efficient Reachability Data Structure Through Bit Vector Compression	2011	SIGMOD
2	355	On Graph Query Optimization in Large Networks	2010	VLDB
3	10,638	Enabling Efficient Direct Update on Rule-Based Compressed Graph	2026	SIGMOD
4	6,526	CompressGraph: Efficient Parallel Graph Analytics with Rule-Based Compression	2023	SIGMOD
5	7,840	DAG Reduction: Fast Answering Reachability Queries	2017	SIGMOD
6	563	Graph Summarization with Bounded Error	2008	SIGMOD
7	11,662	Neighborhood-Preserving Graph Sparsification	2024	VLDB
8	1,187	Local Graph Sparsification for Scalable Clustering	2011	SIGMOD
9	7,015	A Hierarchical Contraction Scheme for Querying Big Graphs	2022	SIGMOD
10	1,375	Query Preserving Graph Compression	2012	SIGMOD