# A Comprehensive Survey on Graph Reduction: Sparsification, Coarsening, and Condensation

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

## Key facts

- Cited by 57 papers in the map (data through 14 Oct 2026).
- Builds on 80 of its 159 references that are in the map.
- First posted on arXiv 29 Jan 2024.

## Builds on (most cited first, 30 of 80)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Membership Inference Attacks against Machine Learning Models](https://mlsanity.com/paper/1610.05820/) (2016)
- [A Survey on Bias and Fairness in Machine Learning](https://mlsanity.com/paper/1908.09635/) (2019)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [Dataset Condensation with Gradient Matching](https://mlsanity.com/paper/2006.05929/) (2020)
- [Graph Neural Networks in Recommender Systems: A Survey](https://mlsanity.com/paper/2011.02260/) (2020)
- [Dataset Condensation with Distribution Matching](https://mlsanity.com/paper/2110.04181/) (2021)
- [OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphs](https://mlsanity.com/paper/2103.09430/) (2021)
- [A Comprehensive Survey of Neural Architecture Search: Challenges and Solutions](https://mlsanity.com/paper/2006.02903/) (2020)
- [Dataset Meta-Learning from Kernel Ridge-Regression](https://mlsanity.com/paper/2011.00050/) (2020)
- [Dataset Distillation with Infinitely Wide Convolutional Networks](https://mlsanity.com/paper/2107.13034/) (2021)
- [XGNN: Towards Model-Level Explanations of Graph Neural Networks](https://mlsanity.com/paper/2006.02587/) (2020)
- [Data Augmentation for Graph Neural Networks](https://mlsanity.com/paper/2006.06830/) (2020)
- [Graph neural networks for materials science and chemistry](https://mlsanity.com/paper/2208.09481/) (2022)
- [FearNet: Brain-Inspired Model for Incremental Learning](https://mlsanity.com/paper/1711.10563/) (2017)
- [Handling Distribution Shifts on Graphs: An Invariance Perspective](https://mlsanity.com/paper/2202.02466/) (2022)
- [Graph Clustering with Graph Neural Networks](https://mlsanity.com/paper/2006.16904/) (2020)
- [Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels](https://mlsanity.com/paper/1905.13192/) (2019)
- [Graph Condensation for Graph Neural Networks](https://mlsanity.com/paper/2110.07580/) (2021)
- [Foundations and modelling of dynamic networks using Dynamic Graph Neural Networks: A survey](https://mlsanity.com/paper/2005.07496/) (2020)
- [Privacy for Free: How does Dataset Condensation Help Privacy?](https://mlsanity.com/paper/2206.00240/) (2022)
- [A Unified Lottery Ticket Hypothesis for Graph Neural Networks](https://mlsanity.com/paper/2102.06790/) (2021)
- [Condensing Graphs via One-Step Gradient Matching](https://mlsanity.com/paper/2206.07746/) (2022)
- [Out-Of-Distribution Generalization on Graphs: A Survey](https://mlsanity.com/paper/2202.07987/) (2022)
- [Decoupling the Depth and Scope of Graph Neural Networks](https://mlsanity.com/paper/2201.07858/) (2022)

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

- [Graph Machine Learning in the Era of Large Language Models (LLMs)](https://mlsanity.com/paper/2404.14928/) (2024)
- [Graph Transformers: A Survey](https://mlsanity.com/paper/2407.09777/) (2024)
- [Towards Graph Foundation Models: Learning Generalities Across Graphs via Task-Trees](https://mlsanity.com/paper/2412.16441/) (2024)
- [Navigating Complexity: Toward Lossless Graph Condensation via Expanding Window Matching](https://mlsanity.com/paper/2402.05011/) (2024)
- [Rethinking and Accelerating Graph Condensation: A Training-Free Approach with Class Partition](https://mlsanity.com/paper/2405.13707/) (2024)
- [EXGC: Bridging Efficiency and Explainability in Graph Condensation](https://mlsanity.com/paper/2402.05962/) (2024)
- [Graph Sparsification via Mixture of Graphs](https://mlsanity.com/paper/2405.14260/) (2024)
- [Graph ODEs and Beyond: A Comprehensive Survey on Integrating Differential Equations with Graph Neural Networks](https://mlsanity.com/paper/2503.23167/) (2025)
- [A Survey on Graph Condensation](https://mlsanity.com/paper/2402.02000/) (2024)
- [Two Trades is not Baffled: Condensing Graph via Crafting Rational Gradient Matching](https://mlsanity.com/paper/2402.04924/) (2024)
- [RobGC: Towards Robust Graph Condensation](https://mlsanity.com/paper/2406.13200/) (2024)
- [GCAL: Adapting Graph Models to Evolving Domain Shifts](https://mlsanity.com/paper/2505.16860/) (2025)
- [GC4NC: A Benchmark Framework for Graph Condensation on Node Classification with New Insights](https://mlsanity.com/paper/2406.16715/) (2024)
- [AutoG: Towards automatic graph construction from tabular data](https://mlsanity.com/paper/2501.15282/) (2025)
- [Recent Advances in Malware Detection: Graph Learning and Explainability](https://mlsanity.com/paper/2502.10556/) (2025)
- [Contrastive Graph Condensation: Advancing Data Versatility through Self-Supervised Learning](https://mlsanity.com/paper/2411.17063/) (2024)
- [Scalable Graph Condensation with Evolving Capabilities](https://mlsanity.com/paper/2502.17614/) (2025)
- [GCondenser: Benchmarking Graph Condensation](https://mlsanity.com/paper/2405.14246/) (2024)
- [TinyGraph: Joint Feature and Node Condensation for Graph Neural Networks](https://mlsanity.com/paper/2407.08064/) (2024)
- [Backdoor Graph Condensation](https://mlsanity.com/paper/2407.11025/) (2024)
- [Simple yet Effective Graph Distillation via Clustering](https://mlsanity.com/paper/2505.20807/) (2025)
- [From Points to Places: Towards Human Mobility-Driven Spatiotemporal Foundation Models via Understanding Places](https://mlsanity.com/paper/2506.14570/) (2025)
- [ReassembleNet: Learnable Keypoints and Diffusion for 2D Fresco Reconstruction](https://mlsanity.com/paper/2505.21117/) (2025)
- [GBGC: Efficient and Adaptive Graph Coarsening via Granular-ball Computing](https://mlsanity.com/paper/2506.19224/) (2025)
- [Spectral Neural Graph Sparsification](https://mlsanity.com/paper/2510.27474/) (2025)
- [Scale-aware Message Passing For Graph Node Classification](https://mlsanity.com/paper/2411.19392/) (2024)
- [Grothendieck Graph Neural Networks Framework: An Algebraic Platform for Crafting Topology-Aware GNNs](https://mlsanity.com/paper/2412.08835/) (2024)
- [Training-free Heterogeneous Graph Condensation via Data Selection](https://mlsanity.com/paper/2412.16250/) (2024)
- [Dynamic Graph Condensation](https://mlsanity.com/paper/2506.13099/) (2025)
- [PlaceRep: Geospatial Place Representation Learning from Large-Scale Point-of-Interest Data](https://mlsanity.com/paper/2507.02921/) (2025)

## Abstract (arXiv)

Many real-world datasets can be naturally represented as graphs, spanning a wide range of domains. However, the increasing complexity and size of graph datasets present significant challenges for analysis and computation. In response, graph reduction, or graph summarization, has gained prominence for simplifying large graphs while preserving essential properties. In this survey, we aim to provide a comprehensive understanding of graph reduction methods, including graph sparsification, graph coarsening, and graph condensation. Specifically, we establish a unified definition for these methods and introduce a hierarchical taxonomy to categorize the challenges they address. Our survey then systematically reviews the technical details of these methods and emphasizes their practical applications across diverse scenarios. Furthermore, we outline critical research directions to ensure the continued effectiveness of graph reduction techniques, as well as provide a comprehensive paper list at urlhttps://github.com/Emory-Melody/awesome-graph-reduction. We hope this survey will bridge literature gaps and propel the advancement of this promising field.