# A Unifying Framework for Spectrum-Preserving Graph Sparsification and Coarsening

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Feb 2019.

## Built on by (most cited first, 30 of 31)

- [Understanding Pooling in Graph Neural Networks](https://mlsanity.com/paper/2110.05292/) (2021)
- [A Comprehensive Survey on Graph Reduction: Sparsification, Coarsening, and Condensation](https://mlsanity.com/paper/2402.03358/) (2024)
- [Graph Coarsening with Neural Networks](https://mlsanity.com/paper/2102.01350/) (2021)
- [SizeShiftReg: a Regularization Method for Improving Size-Generalization in Graph Neural Networks](https://mlsanity.com/paper/2207.07888/) (2022)
- [Efficient and Scalable Graph Generation through Iterative Local Expansion](https://mlsanity.com/paper/2312.11529/) (2023)
- [Graph Condensation for Inductive Node Representation Learning](https://mlsanity.com/paper/2307.15967/) (2023)
- [Graph Condensation: A Survey](https://mlsanity.com/paper/2401.11720/) (2024)
- [Rethinking and Accelerating Graph Condensation: A Training-Free Approach with Class Partition](https://mlsanity.com/paper/2405.13707/) (2024)
- [Graph coarsening: From scientific computing to machine learning](https://mlsanity.com/paper/2106.11863/) (2021)
- [A Survey on Graph Neural Network Acceleration: Algorithms, Systems, and Customized Hardware](https://mlsanity.com/paper/2306.14052/) (2023)
- [A Gromov--Wasserstein Geometric View of Spectrum-Preserving Graph Coarsening](https://mlsanity.com/paper/2306.08854/) (2023)
- [Principle of Relevant Information for Graph Sparsification](https://mlsanity.com/paper/2206.00118/) (2022)
- [A Unified Framework for Optimization-Based Graph Coarsening](https://mlsanity.com/paper/2210.00437/) (2022)
- [A Survey on Graph Condensation](https://mlsanity.com/paper/2402.02000/) (2024)
- [Graph Coarsening with Message-Passing Guarantees](https://mlsanity.com/paper/2405.18127/) (2024)
- [The Conditional Cauchy-Schwarz Divergence with Applications to Time-Series Data and Sequential Decision Making](https://mlsanity.com/paper/2301.08970/) (2023)
- [HyperSF: Spectral Hypergraph Coarsening via Flow-based Local Clustering](https://mlsanity.com/paper/2108.07901/) (2021)
- [Taxonomy of reduction matrices for Graph Coarsening](https://mlsanity.com/paper/2506.11743/) (2025)
- [Theoretical analysis and computation of the sample Frechet mean for sets of large graphs based on spectral information](https://mlsanity.com/paper/2201.05923/) (2022)
- [FunQG: Molecular Representation Learning Via Quotient Graphs](https://mlsanity.com/paper/2207.08597/) (2022)
- [Rapid training of Hamiltonian graph networks using random features](https://mlsanity.com/paper/2506.06558/) (2025)
- [SMGRL: Scalable Multi-resolution Graph Representation Learning](https://mlsanity.com/paper/2201.12670/) (2022)
- [DGC: Training Dynamic Graphs with Spatio-Temporal Non-Uniformity using Graph Partitioning by Chunks](https://mlsanity.com/paper/2309.03523/) (2023)
- [AH-UGC: Adaptive and Heterogeneous-Universal Graph Coarsening](https://mlsanity.com/paper/2505.15842/) (2025)
- [Learning Gaussian Graphical Models under Total Positivity via Spectral Graph Sparsification](https://mlsanity.com/paper/2605.17154/) (2026)
- [Sparsistent filtering of comovement networks from high-dimensional data](https://mlsanity.com/paper/2101.09174/) (2021)
- [Fast and Effective GNN Training through Sequences of Random Path Graphs](https://mlsanity.com/paper/2306.04828/) (2023)
- [Scalable Topology-Preserving Graph Coarsening: Concepts and Algorithms](https://mlsanity.com/paper/2601.22943/) (2026)
- [Informative Graph Structure Learning](https://mlsanity.com/paper/2605.16809/) (2026)
- [Does Graph Compression Preserve Signal Propagation?](https://mlsanity.com/paper/2607.23338/) (2026)

## Abstract (arXiv)

How might one "reduce" a graph? That is, generate a smaller graph that preserves the global structure at the expense of discarding local details? There has been extensive work on both graph sparsification (removing edges) and graph coarsening (merging nodes, often by edge contraction); however, these operations are currently treated separately. Interestingly, for a planar graph, edge deletion corresponds to edge contraction in its planar dual (and more generally, for a graphical matroid and its dual). Moreover, with respect to the dynamics induced by the graph Laplacian (e.g., diffusion), deletion and contraction are physical manifestations of two reciprocal limits: edge weights of 0 and ∞, respectively. In this work, we provide a unifying framework that captures both of these operations, allowing one to simultaneously sparsify and coarsen a graph while preserving its large-scale structure. The limit of infinite edge weight is rarely considered, as many classical notions of graph similarity diverge. However, its algebraic, geometric, and physical interpretations are reflected in the Laplacian pseudoinverse mathbfmathitLdagger, which remains finite in this limit. Motivated by this insight, we provide a probabilistic algorithm that reduces graphs while preserving mathbfmathitLdagger, using an unbiased procedure that minimizes its variance. We compare our algorithm with several existing sparsification and coarsening algorithms using real-world datasets, and demonstrate that it more accurately preserves the large-scale structure.