# Demystifying Graph Sparsification Algorithms in Graph Properties Preservation

arXiv: https://arxiv.org/abs/2311.12314 · HTML: https://mlsanity.com/paper/2311.12314/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Nov 2023.

## Built on by (most cited first, 14 of 14)

- [Cut the Crap: An Economical Communication Pipeline for LLM-based Multi-Agent Systems](https://mlsanity.com/paper/2410.02506/) (2024)
- [Graph Sparsification via Mixture of Graphs](https://mlsanity.com/paper/2405.14260/) (2024)
- [Two Heads Are Better Than One: Boosting Graph Sparse Training via Semantic and Topological Awareness](https://mlsanity.com/paper/2402.01242/) (2024)
- [Molecular Topological Profile (MOLTOP) -- Simple and Strong Baseline for Molecular Graph Classification](https://mlsanity.com/paper/2407.12136/) (2024)
- [Efficient Topology-aware Data Augmentation for High-Degree Graph Neural Networks](https://mlsanity.com/paper/2406.05482/) (2024)
- [A Comprehensive Benchmark on Spectral GNNs: The Impact on Efficiency, Memory, and Effectiveness](https://mlsanity.com/paper/2406.09675/) (2024)
- [Spectral Neural Graph Sparsification](https://mlsanity.com/paper/2510.27474/) (2025)
- [Efficient Sparsification of Simplicial Complexes via Local Densities of States](https://mlsanity.com/paper/2502.07558/) (2025)
- [Optimizing Federated Learning using Remote Embeddings for Graph Neural Networks](https://mlsanity.com/paper/2506.12425/) (2025)
- [Demystifying Distributed Training of Graph Neural Networks for Link Prediction](https://mlsanity.com/paper/2506.20818/) (2025)
- [Not All Neighbors Matter: Understanding the Impact of Graph Sparsification on GNN Pipelines](https://mlsanity.com/paper/2603.06952/) (2026)
- [EmbedPart: Embedding-Driven Graph Partitioning for Scalable Graph Neural Network Training](https://mlsanity.com/paper/2604.01000/) (2026)
- [Moment-guided edge sampling](https://mlsanity.com/paper/2609.30472/) (2026)
- [Scaffold: Support Graph Theory Based Sparsification for Graph Neural Networks](https://mlsanity.com/paper/2609.31466/) (2026)

## Abstract (arXiv)

Graph sparsification is a technique that approximates a given graph by a sparse graph with a subset of vertices and/or edges. The goal of an effective sparsification algorithm is to maintain specific graph properties relevant to the downstream task while minimizing the graph's size. Graph algorithms often suffer from long execution time due to the irregularity and the large real-world graph size. Graph sparsification can be applied to greatly reduce the run time of graph algorithms by substituting the full graph with a much smaller sparsified graph, without significantly degrading the output quality. However, the interaction between numerous sparsifiers and graph properties is not widely explored, and the potential of graph sparsification is not fully understood. In this work, we cover 16 widely-used graph metrics, 12 representative graph sparsification algorithms, and 14 real-world input graphs spanning various categories, exhibiting diverse characteristics, sizes, and densities. We developed a framework to extensively assess the performance of these sparsification algorithms against graph metrics, and provide insights to the results. Our study shows that there is no one sparsifier that performs the best in preserving all graph properties, e.g. sparsifiers that preserve distance-related graph properties (eccentricity) struggle to perform well on Graph Neural Networks (GNN). This paper presents a comprehensive experimental study evaluating the performance of sparsification algorithms in preserving essential graph metrics. The insights inform future research in incorporating matching graph sparsification to graph algorithms to maximize benefits while minimizing quality degradation. Furthermore, we provide a framework to facilitate the future evaluation of evolving sparsification algorithms, graph metrics, and ever-growing graph data.