# Graph Coarsening with Preserved Spectral Properties

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

## Key facts

- Cited by 41 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Feb 2018.

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

- [Data Augmentation for Deep Graph Learning: A Survey](https://mlsanity.com/paper/2202.08235/) (2022)
- [Scaling Up Graph Neural Networks Via Graph Coarsening](https://mlsanity.com/paper/2106.05150/) (2021)
- [Structure-free Graph Condensation: From Large-scale Graphs to Condensed Graph-free Data](https://mlsanity.com/paper/2306.02664/) (2023)
- [Graph Filters for Signal Processing and Machine Learning on Graphs](https://mlsanity.com/paper/2211.08854/) (2022)
- [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)
- [Accelerating Transformers with Spectrum-Preserving Token Merging](https://mlsanity.com/paper/2405.16148/) (2024)
- [Geometric Knowledge Distillation: Topology Compression for Graph Neural Networks](https://mlsanity.com/paper/2210.13014/) (2022)
- [Data-centric Graph Learning: A Survey](https://mlsanity.com/paper/2310.04987/) (2023)
- [Graph coarsening: From scientific computing to machine learning](https://mlsanity.com/paper/2106.11863/) (2021)
- [Graph Distillation with Eigenbasis Matching](https://mlsanity.com/paper/2310.09202/) (2023)
- [A Gromov--Wasserstein Geometric View of Spectrum-Preserving Graph Coarsening](https://mlsanity.com/paper/2306.08854/) (2023)
- [Towards Data-centric Graph Machine Learning: Review and Outlook](https://mlsanity.com/paper/2309.10979/) (2023)
- [A Topology-aware Graph Coarsening Framework for Continual Graph Learning](https://mlsanity.com/paper/2401.03077/) (2024)
- [Partition and Code: learning how to compress graphs](https://mlsanity.com/paper/2107.01952/) (2021)
- [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)
- [Graph Coarsening via Supervised Granular-Ball for Scalable Graph Neural Network Training](https://mlsanity.com/paper/2412.13842/) (2024)
- [Latent Spectral Regularization for Continual Learning](https://mlsanity.com/paper/2301.03345/) (2023)
- [Contrastive Graph Condensation: Advancing Data Versatility through Self-Supervised Learning](https://mlsanity.com/paper/2411.17063/) (2024)
- [MaxCutPool: differentiable feature-aware Maxcut for pooling in graph neural networks](https://mlsanity.com/paper/2409.05100/) (2024)
- [JITuNE: Just-In-Time Hyperparameter Tuning for Network Embedding Algorithms](https://mlsanity.com/paper/2101.06427/) (2021)
- [HyperSF: Spectral Hypergraph Coarsening via Flow-based Local Clustering](https://mlsanity.com/paper/2108.07901/) (2021)
- [Understanding the Basis of Graph Convolutional Neural Networks via an Intuitive Matched Filtering Approach](https://mlsanity.com/paper/2108.10751/) (2021)
- [Taxonomy of reduction matrices for Graph Coarsening](https://mlsanity.com/paper/2506.11743/) (2025)
- [Graph Community Detection from Coarse Measurements: Recovery Conditions for the Coarsened Weighted Stochastic Block Model](https://mlsanity.com/paper/2102.13135/) (2021)
- [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)
- [CoRe-GD: A Hierarchical Framework for Scalable Graph Visualization with GNNs](https://mlsanity.com/paper/2402.06706/) (2024)
- [Learning Lagrangian Interaction Dynamics with Sampling-Based Model Order Reduction](https://mlsanity.com/paper/2407.03925/) (2024)
- [Efficient Large-Scale Urban Parking Prediction: Graph Coarsening Based on Real-Time Parking Service Capability](https://mlsanity.com/paper/2410.04022/) (2024)

## Abstract (arXiv)

Large-scale graphs are widely used to represent object relationships in many real world applications. The occurrence of large-scale graphs presents significant computational challenges to process, analyze, and extract information. Graph coarsening techniques are commonly used to reduce the computational load while attempting to maintain the basic structural properties of the original graph. As there is no consensus on the specific graph properties preserved by coarse graphs, how to measure the differences between original and coarse graphs remains a key challenge. In this work, we introduce a new perspective regarding the graph coarsening based on concepts from spectral graph theory. We propose and justify new distance functions that characterize the differences between original and coarse graphs. We show that the proposed spectral distance naturally captures the structural differences in the graph coarsening process. In addition, we provide efficient graph coarsening algorithms to generate graphs which provably preserve the spectral properties from original graphs. Experiments show that our proposed algorithms consistently achieve better results compared to previous graph coarsening methods on graph classification and block recovery tasks.