mlsanityData to 7 Oct 2026

Spectrally approximating large graphs with smaller graphs

arXiv 1802.07510 ↗First posted 21 Feb 2018cs.LG cs.DS stat.MLcited by 56

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 7; 2022: 7; 2023: 8; 2024: 18; 2025: 10; 2026: 6.

56 papers.

Sort:

By area:

  1. 2021Graph Condensation for Graph Neural Networkscited by 150
  2. 2024A Comprehensive Survey on Graph Reduction: Sparsification, Coarsening, and Condensationcited by 57
  3. 2021Graph Coarsening with Neural Networkscited by 55
  4. 2022Graph Filters for Signal Processing and Machine Learning on Graphscited by 53
  5. 2023Does Graph Distillation See Like Vision Dataset Counterpart?cited by 45
  6. 2022SizeShiftReg: a Regularization Method for Improving Size-Generalization in Graph Neural Networkscited by 36
  7. 2023Efficient and Scalable Graph Generation through Iterative Local Expansioncited by 35
  8. 2024Accelerating Transformers with Spectrum-Preserving Token Mergingcited by 35
  9. 2023Graph Condensation for Inductive Node Representation Learningcited by 31
  10. 2024Graph Condensation: A Surveycited by 23
  11. 2024Rethinking and Accelerating Graph Condensation: A Training-Free Approach with Class Partitioncited by 23
  12. 2023Data-centric Graph Learning: A Surveycited by 22
38 more
  1. 2022Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networkscited by 18
  2. 2023A Survey on Graph Neural Network Acceleration: Algorithms, Systems, and Customized Hardwarecited by 18
  3. 2023A Gromov--Wasserstein Geometric View of Spectrum-Preserving Graph Coarseningcited by 15
  4. 2021Partition and Code: learning how to compress graphscited by 10
  5. 2021SQALER: Scaling Question Answering by Decoupling Multi-Hop and Logical Reasoningcited by 10
  6. 2024Disentangled Condensation for Large-scale Graphscited by 10
  7. 2022A Unified Framework for Optimization-Based Graph Coarseningcited by 9
  8. 2024Graph Condensation for Open-World Graph Learningcited by 9
  9. 2024Graph Coarsening with Message-Passing Guaranteescited by 9
  10. 2024Graph Coarsening via Supervised Granular-Ball for Scalable Graph Neural Network Trainingcited by 9
  11. 2024Simple Graph Condensationcited by 8
  12. 2022HyperEF: Spectral Hypergraph Coarsening by Effective-Resistance Clusteringcited by 6
  13. 2023Adversarial Erasing with Pruned Elements: Towards Better Graph Lottery Ticketcited by 5
  14. 2021HyperSF: Spectral Hypergraph Coarsening via Flow-based Local Clusteringcited by 4
  15. 2024TEDDY: Trimming Edges with Degree-based Discrimination strategYcited by 4
  16. 2024Calibrated Dataset Condensation for Faster Hyperparameter Searchcited by 4
  17. 2024Spectral Greedy Coresets for Graph Neural Networkscited by 3
  18. 2025Taxonomy of reduction matrices for Graph Coarseningcited by 3
  19. 2022FunQG: Molecular Representation Learning Via Quotient Graphscited by 2
  20. 2025Partition-wise Graph Filtering: A Unified Perspective Through the Lens of Graph Coarseningcited by 2
  21. 2025GBGC: Efficient and Adaptive Graph Coarsening via Granular-ball Computingcited by 2
  22. 2025Heterogeneous Graph Representation of Stiffened Panels with Non-Uniform Boundary Conditions and Loadscited by 2
  23. 2026StructSAM: Structure- and Spectrum-Preserving Token Merging for Segment Anything Modelscited by 2
  24. 2022SMGRL: Scalable Multi-resolution Graph Representation Learningcited by 1
  25. 2024On the Robustness of Graph Reduction Against GNN Backdoorcited by 1
  26. 2025Rotary Position Encodings for Graphscited by 1
  27. 2021Interferometric Graph Transform for Community Labelingcited by 0
  28. 2021Low-Rank Projections of GCNs Laplaciancited by 0
  29. 2023Fast and Effective GNN Training through Sequences of Random Path Graphscited by 0
  30. 2024Efficient User Sequence Learning for Online Services via Compressed Graph Neural Networkscited by 0
  31. 2024Modularity aided consistent attributed graph clustering via coarseningcited by 0
  32. 2024SHyPar: A Spectral Coarsening Approach to Hypergraph Partitioningcited by 0
  33. 2024On the Adversarial Robustness of Graph Neural Networks with Graph Reductioncited by 0
  34. 2024PASCO (PArallel Structured COarsening): an overlay to speed up graph clustering algorithmscited by 0
  35. 2025Inference-friendly Graph Compression for Graph Neural Networkscited by 0
  36. 2025Test-Time Search in Neural Graph Coarsening Procedures for the Capacitated Vehicle Routing Problemcited by 0
  37. 2025BoolSkeleton: Boolean Network Skeletonization via Homogeneous Pattern Reductioncited by 0
  38. 2025LGDC: Latent Graph Diffusion via Spectrum-Preserving Coarseningcited by 0

50 most cited of 56 All 56 (JSON)