# Spectrally approximating large graphs with smaller graphs

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

## Key facts

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

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

- [Graph Condensation for Graph Neural Networks](https://mlsanity.com/paper/2110.07580/) (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)
- [Graph Filters for Signal Processing and Machine Learning on Graphs](https://mlsanity.com/paper/2211.08854/) (2022)
- [Does Graph Distillation See Like Vision Dataset Counterpart?](https://mlsanity.com/paper/2310.09192/) (2023)
- [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)
- [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)
- [Data-centric Graph Learning: A Survey](https://mlsanity.com/paper/2310.04987/) (2023)
- [Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networks](https://mlsanity.com/paper/2207.08629/) (2022)
- [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)
- [Partition and Code: learning how to compress graphs](https://mlsanity.com/paper/2107.01952/) (2021)
- [SQALER: Scaling Question Answering by Decoupling Multi-Hop and Logical Reasoning](https://mlsanity.com/paper/2110.14266/) (2021)
- [Disentangled Condensation for Large-scale Graphs](https://mlsanity.com/paper/2401.12231/) (2024)
- [A Unified Framework for Optimization-Based Graph Coarsening](https://mlsanity.com/paper/2210.00437/) (2022)
- [Graph Condensation for Open-World Graph Learning](https://mlsanity.com/paper/2405.17003/) (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)
- [Simple Graph Condensation](https://mlsanity.com/paper/2403.14951/) (2024)
- [HyperEF: Spectral Hypergraph Coarsening by Effective-Resistance Clustering](https://mlsanity.com/paper/2210.14813/) (2022)
- [Adversarial Erasing with Pruned Elements: Towards Better Graph Lottery Ticket](https://mlsanity.com/paper/2308.02916/) (2023)
- [Calibrated Dataset Condensation for Faster Hyperparameter Search](https://mlsanity.com/paper/2405.17535/) (2024)
- [HyperSF: Spectral Hypergraph Coarsening via Flow-based Local Clustering](https://mlsanity.com/paper/2108.07901/) (2021)
- [TEDDY: Trimming Edges with Degree-based Discrimination strategY](https://mlsanity.com/paper/2402.01261/) (2024)
- [Spectral Greedy Coresets for Graph Neural Networks](https://mlsanity.com/paper/2405.17404/) (2024)
- [Taxonomy of reduction matrices for Graph Coarsening](https://mlsanity.com/paper/2506.11743/) (2025)

## Abstract (arXiv)

How does coarsening affect the spectrum of a general graph? We provide conditions such that the principal eigenvalues and eigenspaces of a coarsened and original graph Laplacian matrices are close. The achieved approximation is shown to depend on standard graph-theoretic properties, such as the degree and eigenvalue distributions, as well as on the ratio between the coarsened and actual graph sizes. Our results carry implications for learning methods that utilize coarsening. For the particular case of spectral clustering, they imply that coarse eigenvectors can be used to derive good quality assignments even without refinement---this phenomenon was previously observed, but lacked formal justification.