# Rethinking and Accelerating Graph Condensation: A Training-Free Approach with Class Partition

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- Builds on 54 of its 79 references that are in the map.
- First posted on arXiv 22 May 2024.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [Dataset Condensation with Gradient Matching](https://mlsanity.com/paper/2006.05929/) (2020)
- [Dataset Distillation by Matching Training Trajectories](https://mlsanity.com/paper/2203.11932/) (2022)
- [InfoGraph: Unsupervised and Semi-supervised Graph-Level Representation Learning via Mutual Information Maximization](https://mlsanity.com/paper/1908.01000/) (2019)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [Dataset Condensation with Distribution Matching](https://mlsanity.com/paper/2110.04181/) (2021)
- [Dataset Meta-Learning from Kernel Ridge-Regression](https://mlsanity.com/paper/2011.00050/) (2020)
- [Graph Condensation for Graph Neural Networks](https://mlsanity.com/paper/2110.07580/) (2021)
- [How to learn a graph from smooth signals](https://mlsanity.com/paper/1601.02513/) (2016)
- [Data Augmentation for Deep Graph Learning: A Survey](https://mlsanity.com/paper/2202.08235/) (2022)
- [Dataset Distillation: A Comprehensive Review](https://mlsanity.com/paper/2301.07014/) (2023)
- [A Survey on Heterogeneous Graph Embedding: Methods, Techniques, Applications and Sources](https://mlsanity.com/paper/2011.14867/) (2020)
- [A Unified Lottery Ticket Hypothesis for Graph Neural Networks](https://mlsanity.com/paper/2102.06790/) (2021)
- [A Comprehensive Survey of Dataset Distillation](https://mlsanity.com/paper/2301.05603/) (2023)
- [Condensing Graphs via One-Step Gradient Matching](https://mlsanity.com/paper/2206.07746/) (2022)
- [Unifying Graph Convolutional Neural Networks and Label Propagation](https://mlsanity.com/paper/2002.06755/) (2020)
- [Self-Supervised Learning for Recommender Systems: A Survey](https://mlsanity.com/paper/2203.15876/) (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)
- [Rethinking and Scaling Up Graph Contrastive Learning: An Extremely Efficient Approach with Group Discrimination](https://mlsanity.com/paper/2206.01535/) (2022)
- [Graph Condensation via Receptive Field Distribution Matching](https://mlsanity.com/paper/2206.13697/) (2022)

## Built on by (most cited first, 23 of 23)

- [A Comprehensive Survey on Imbalanced Data Learning](https://mlsanity.com/paper/2502.08960/) (2025)
- [RobGC: Towards Robust Graph Condensation](https://mlsanity.com/paper/2406.13200/) (2024)
- [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)
- [Efficient Graph Condensation via Gaussian Process](https://mlsanity.com/paper/2501.02565/) (2025)
- [PAMAS: Self-Adaptive Multi-Agent System with Perspective Aggregation for Misinformation Detection](https://mlsanity.com/paper/2602.03158/) (2026)
- [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)
- [Multi-view Graph Condensation via Tensor Decomposition](https://mlsanity.com/paper/2508.14330/) (2025)
- [Conv4Rec: A 1-by-1 Convolutional AutoEncoder for User Profiling through Joint Analysis of Implicit and Explicit Feedbacks](https://mlsanity.com/paper/2509.07499/) (2025)
- [Relational Database Distillation: From Structured Tables to Condensed Graph Data](https://mlsanity.com/paper/2510.06980/) (2025)
- [C2TC: A Training-Free Framework for Efficient Tabular Data Condensation](https://mlsanity.com/paper/2602.21717/) (2026)
- [Towards Pre-trained Graph Condensation via Optimal Transport](https://mlsanity.com/paper/2509.14722/) (2025)
- [Adaptive Graph Coarsening for Efficient GNN Training](https://mlsanity.com/paper/2509.25706/) (2025)
- [Transferable Graph Condensation from the Causal Perspective](https://mlsanity.com/paper/2601.21309/) (2026)
- [Anchor-guided Hypergraph Condensation with Dual-level Discrimination](https://mlsanity.com/paper/2605.10001/) (2026)
- [An Efficient and Scalable Graph Condensation with Structure-Preserving](https://mlsanity.com/paper/2605.31016/) (2026)
- [Text-attributed Graph Condensation via Text Selection and Attribute Matching](https://mlsanity.com/paper/2606.03839/) (2026)
- [Heterogeneous Graph Condensation via Role-Aware Clustering](https://mlsanity.com/paper/2607.03097/) (2026)
- [CA-DGCL: Dynamic Graph Continual Learning via Condensation and Attachment](https://mlsanity.com/paper/2607.11112/) (2026)
- [Semi-Supervised Text-Attributed Graph Distillation](https://mlsanity.com/paper/2607.20477/) (2026)
- [Edge Sparsification via Temporal Forman-Ricci Curvature for Dynamic Graph Learning](https://mlsanity.com/paper/2608.07158/) (2026)

## Abstract (arXiv)

The increasing prevalence of large-scale graphs poses a significant challenge for graph neural network training, attributed to their substantial computational requirements. In response, graph condensation (GC) emerges as a promising data-centric solution aiming to substitute the large graph with a small yet informative condensed graph to facilitate data-efficient GNN training. However, existing GC methods suffer from intricate optimization processes, necessitating excessive computing resources and training time. In this paper, we revisit existing GC optimization strategies and identify two pervasive issues therein: (1) various GC optimization strategies converge to coarse-grained class-level node feature matching between the original and condensed graphs; (2) existing GC methods rely on a Siamese graph network architecture that requires time-consuming bi-level optimization with iterative gradient computations. To overcome these issues, we propose a training-free GC framework termed Class-partitioned Graph Condensation (CGC), which refines the node distribution matching from the class-to-class paradigm into a novel class-to-node paradigm, transforming the GC optimization into a class partition problem which can be efficiently solved by any clustering methods. Moreover, CGC incorporates a pre-defined graph structure to enable a closed-form solution for condensed node features, eliminating the need for back-and-forth gradient descent in existing GC approaches. Extensive experiments demonstrate that CGC achieves an exceedingly efficient condensation process with advanced accuracy. Compared with the state-of-the-art GC methods, CGC condenses the Ogbn-products graph within 30 seconds, achieving a speedup ranging from 102X to 104X and increasing accuracy by up to 4.2%.