Demystifying Graph Sparsification Algorithms in Graph Properties Preservation

Summary: Empirical benchmarking of 12 sparsifiers across 16 graph metrics on 14 real-world graphs with an open-source evaluation framework. No universal sparsifier—clear tradeoffs (e.g., distance-preserving methods degrade GNN performance); provides artifacts and guidance to match sparsifiers to downstream tasks. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13634
Venue: VLDB
Year: 2024
Pagerank: 4.6362484e-05
Overall Rank: 7,849 | 45.40%
DOI: 10.14778/3632093.3632106

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,827	On Graph Representation for Attributed Hypergraph Clustering	2025	SIGMOD	5.3113542e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
777	Local Graph Sparsification for Scalable Clustering	2011	SIGMOD	0.0001679862

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,731	GraphCSR: A Degree-Equalized CSR Format for Large-scale Graph Processing	2025	VLDB	4.1945683e-05
11,560	Factorized Graph Representations for Semi-Supervised Learning from Sparse Data	2020	SIGMOD	4.1945683e-05
10,604	GraphSparseNet: a Novel Method for Large Scale Traffic Flow Prediction	2025	VLDB	4.1945683e-05
1,040	Graph Sketches: Sparsification, Spanners, and Subgraphs	2012	PODS	0.00014488943
10,663	Inference-friendly Graph Compression for Graph Neural Networks	2025	VLDB	4.1945683e-05
10,011	A Comprehensive Benchmark on Spectral GNNs: The Impact on Efficiency, Memory, and Effectiveness	2026	SIGMOD	4.1945683e-05
13,174	Topology-preserving Graph Coarsening: An Elementary Collapse-based Approach	2024	VLDB	-
11,355	SparRL: Graph Sparsification via Deep Reinforcement Learning	2022	SIGMOD	4.1945683e-05
777	Local Graph Sparsification for Scalable Clustering	2011	SIGMOD	0.0001679862
11,138	Neighborhood-Preserving Graph Sparsification	2024	VLDB	4.1945683e-05