# Condensing Graphs via One-Step Gradient Matching

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

## Key facts

- Cited by 100 papers in the map (data through 14 Oct 2026).
- Builds on 52 of its 66 references that are in the map.
- First posted on arXiv 15 Jun 2022.

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

- [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)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [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)
- [Learning without Forgetting](https://mlsanity.com/paper/1606.09282/) (2016)
- [iCaRL: Incremental Classifier and Representation Learning](https://mlsanity.com/paper/1611.07725/) (2016)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [DARTS: Differentiable Architecture Search](https://mlsanity.com/paper/1806.09055/) (2018)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables](https://mlsanity.com/paper/1611.00712/) (2016)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [Convolutional Networks on Graphs for Learning Molecular Fingerprints](https://mlsanity.com/paper/1509.09292/) (2015)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [End-to-End Incremental Learning](https://mlsanity.com/paper/1807.09536/) (2018)
- [DeepGCNs: Can GCNs Go as Deep as CNNs?](https://mlsanity.com/paper/1904.03751/) (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)
- [Graph Structure Learning for Robust Graph Neural Networks](https://mlsanity.com/paper/2005.10203/) (2020)
- [Dataset Condensation with Distribution Matching](https://mlsanity.com/paper/2110.04181/) (2021)
- [Towards Deeper Graph Neural Networks](https://mlsanity.com/paper/2007.09296/) (2020)
- [Dataset Condensation with Differentiable Siamese Augmentation](https://mlsanity.com/paper/2102.08259/) (2021)
- [Graph Contrastive Learning Automated](https://mlsanity.com/paper/2106.07594/) (2021)

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

- [Dataset Distillation: A Comprehensive Review](https://mlsanity.com/paper/2301.07014/) (2023)
- [A Comprehensive Survey of Dataset Distillation](https://mlsanity.com/paper/2301.05603/) (2023)
- [Data Distillation: A Survey](https://mlsanity.com/paper/2301.04272/) (2023)
- [Structure-free Graph Condensation: From Large-scale Graphs to Condensed Graph-free Data](https://mlsanity.com/paper/2306.02664/) (2023)
- [Accelerating Dataset Distillation via Model Augmentation](https://mlsanity.com/paper/2212.06152/) (2022)
- [A Comprehensive Survey on Graph Reduction: Sparsification, Coarsening, and Condensation](https://mlsanity.com/paper/2402.03358/) (2024)
- [CaT: Balanced Continual Graph Learning with Graph Condensation](https://mlsanity.com/paper/2309.09455/) (2023)
- [M3D: Dataset Condensation by Minimizing Maximum Mean Discrepancy](https://mlsanity.com/paper/2312.15927/) (2023)
- [Does Graph Distillation See Like Vision Dataset Counterpart?](https://mlsanity.com/paper/2310.09192/) (2023)
- [Fast Graph Condensation with Structure-based Neural Tangent Kernel](https://mlsanity.com/paper/2310.11046/) (2023)
- [A Survey on Dataset Distillation: Approaches, Applications and Future Directions](https://mlsanity.com/paper/2305.01975/) (2023)
- [Graph Condensation for Inductive Node Representation Learning](https://mlsanity.com/paper/2307.15967/) (2023)
- [Navigating Complexity: Toward Lossless Graph Condensation via Expanding Window Matching](https://mlsanity.com/paper/2402.05011/) (2024)
- [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)
- [Efficient Bi-Level Optimization for Recommendation Denoising](https://mlsanity.com/paper/2210.10321/) (2022)
- [EXGC: Bridging Efficiency and Explainability in Graph Condensation](https://mlsanity.com/paper/2402.05962/) (2024)
- [Continual Graph Learning: A Survey](https://mlsanity.com/paper/2301.12230/) (2023)
- [A Survey on Graph Neural Network Acceleration: Algorithms, Systems, and Customized Hardware](https://mlsanity.com/paper/2306.14052/) (2023)
- [Importance-Aware Adaptive Dataset Distillation](https://mlsanity.com/paper/2401.15863/) (2024)
- [Graph Data Condensation via Self-expressive Graph Structure Reconstruction](https://mlsanity.com/paper/2403.07294/) (2024)
- [Graph Distillation with Eigenbasis Matching](https://mlsanity.com/paper/2310.09202/) (2023)
- [Towards Data-centric Graph Machine Learning: Review and Outlook](https://mlsanity.com/paper/2309.10979/) (2023)
- [DANCE: Dual-View Distribution Alignment for Dataset Condensation](https://mlsanity.com/paper/2406.01063/) (2024)
- [Mirage: Model-Agnostic Graph Distillation for Graph Classification](https://mlsanity.com/paper/2310.09486/) (2023)
- [Can pre-trained models assist in dataset distillation?](https://mlsanity.com/paper/2310.03295/) (2023)
- [Graph Coarsening via Convolution Matching for Scalable Graph Neural Network Training](https://mlsanity.com/paper/2312.15520/) (2023)
- [GC-Bench: An Open and Unified Benchmark for Graph Condensation](https://mlsanity.com/paper/2407.00615/) (2024)
- [Disentangled Condensation for Large-scale Graphs](https://mlsanity.com/paper/2401.12231/) (2024)

## Abstract (arXiv)

As training deep learning models on large dataset takes a lot of time and resources, it is desired to construct a small synthetic dataset with which we can train deep learning models sufficiently. There are recent works that have explored solutions on condensing image datasets through complex bi-level optimization. For instance, dataset condensation (DC) matches network gradients w.r.t. large-real data and small-synthetic data, where the network weights are optimized for multiple steps at each outer iteration. However, existing approaches have their inherent limitations: (1) they are not directly applicable to graphs where the data is discrete; and (2) the condensation process is computationally expensive due to the involved nested optimization. To bridge the gap, we investigate efficient dataset condensation tailored for graph datasets where we model the discrete graph structure as a probabilistic model. We further propose a one-step gradient matching scheme, which performs gradient matching for only one single step without training the network weights. Our theoretical analysis shows this strategy can generate synthetic graphs that lead to lower classification loss on real graphs. Extensive experiments on various graph datasets demonstrate the effectiveness and efficiency of the proposed method. In particular, we are able to reduce the dataset size by 90% while approximating up to 98% of the original performance and our method is significantly faster than multi-step gradient matching (e.g. 15x in CIFAR10 for synthesizing 500 graphs). Code is available at urlhttps://github.com/amazon-research/DosCond.