# Fast Graph Condensation with Structure-based Neural Tangent Kernel

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

## Key facts

- Cited by 36 papers in the map (data through 14 Oct 2026).
- Builds on 40 of its 59 references that are in the map.
- First posted on arXiv 17 Oct 2023.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [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)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [On Exact Computation with an Infinitely Wide Neural Net](https://mlsanity.com/paper/1904.11955/) (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)
- [Dataset Condensation with Distribution Matching](https://mlsanity.com/paper/2110.04181/) (2021)
- [Gradient-based Hyperparameter Optimization through Reversible Learning](https://mlsanity.com/paper/1502.03492/) (2015)
- [Dataset Condensation with Differentiable Siamese Augmentation](https://mlsanity.com/paper/2102.08259/) (2021)
- [Exploring the Potential of Large Language Models (LLMs) in Learning on Graphs](https://mlsanity.com/paper/2307.03393/) (2023)
- [Dataset Meta-Learning from Kernel Ridge-Regression](https://mlsanity.com/paper/2011.00050/) (2020)
- [Is Homophily a Necessity for Graph Neural Networks?](https://mlsanity.com/paper/2106.06134/) (2021)
- [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)
- [Privacy for Free: How does Dataset Condensation Help Privacy?](https://mlsanity.com/paper/2206.00240/) (2022)
- [A Unified View on Graph Neural Networks as Graph Signal Denoising](https://mlsanity.com/paper/2010.01777/) (2020)
- [Dataset Condensation with Contrastive Signals](https://mlsanity.com/paper/2202.02916/) (2022)
- [Remember the Past: Distilling Datasets into Addressable Memories for Neural Networks](https://mlsanity.com/paper/2206.02916/) (2022)
- [Condensing Graphs via One-Step Gradient Matching](https://mlsanity.com/paper/2206.07746/) (2022)
- [Understanding and correcting pathologies in the training of learned optimizers](https://mlsanity.com/paper/1810.10180/) (2018)
- [Generative Diffusion Models on Graphs: Methods and Applications](https://mlsanity.com/paper/2302.02591/) (2023)

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

- [A Comprehensive Survey on Graph Reduction: Sparsification, Coarsening, and Condensation](https://mlsanity.com/paper/2402.03358/) (2024)
- [Graph Machine Learning in the Era of Large Language Models (LLMs)](https://mlsanity.com/paper/2404.14928/) (2024)
- [Linear-Time Graph Neural Networks for Scalable Recommendations](https://mlsanity.com/paper/2402.13973/) (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)
- [Graph Unlearning with Efficient Partial Retraining](https://mlsanity.com/paper/2403.07353/) (2024)
- [GC-Bench: An Open and Unified Benchmark for Graph Condensation](https://mlsanity.com/paper/2407.00615/) (2024)
- [A Survey on Graph Condensation](https://mlsanity.com/paper/2402.02000/) (2024)
- [Graph Condensation for Open-World Graph Learning](https://mlsanity.com/paper/2405.17003/) (2024)
- [Learning on Large Graphs using Intersecting Communities](https://mlsanity.com/paper/2405.20724/) (2024)
- [RobGC: Towards Robust Graph Condensation](https://mlsanity.com/paper/2406.13200/) (2024)
- [GC4NC: A Benchmark Framework for Graph Condensation on Node Classification with New Insights](https://mlsanity.com/paper/2406.16715/) (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)
- [Backdoor Graph Condensation](https://mlsanity.com/paper/2407.11025/) (2024)
- [Bi-Directional Multi-Scale Graph Dataset Condensation via Information Bottleneck](https://mlsanity.com/paper/2412.17355/) (2024)
- [Efficient Graph Condensation via Gaussian Process](https://mlsanity.com/paper/2501.02565/) (2025)
- [Simple yet Effective Graph Distillation via Clustering](https://mlsanity.com/paper/2505.20807/) (2025)
- [Efficient Learning on Large Graphs using a Densifying Regularity Lemma](https://mlsanity.com/paper/2504.18273/) (2025)
- [Decoupling and Damping: Structurally-Regularized Gradient Matching for Multimodal Graph Condensation](https://mlsanity.com/paper/2511.20222/) (2025)
- [Effective Dataset Distillation for Spatio-Temporal Forecasting with Bi-dimensional Compression](https://mlsanity.com/paper/2603.10410/) (2026)
- [FIT-GNN: Faster Inference Time for GNNs that 'FIT' in Memory Using Coarsening](https://mlsanity.com/paper/2410.15001/) (2024)
- [Bonsai: Gradient-free Graph Condensation for Node Classification](https://mlsanity.com/paper/2410.17579/) (2024)
- [Multi-view Graph Condensation via Tensor Decomposition](https://mlsanity.com/paper/2508.14330/) (2025)
- [Rethinking Efficient Graph Coarsening via a Non-Selfishness Principle](https://mlsanity.com/paper/2605.13021/) (2026)
- [Position: Graph Condensation Needs a Reset -- Move Beyond Full-dataset Training and Model-Dependence](https://mlsanity.com/paper/2605.18893/) (2026)
- [Acceleration Algorithms in GNNs: A Survey](https://mlsanity.com/paper/2405.04114/) (2024)
- [TCGU: Data-centric Graph Unlearning based on Transferable Condensation](https://mlsanity.com/paper/2410.06480/) (2024)
- [Extending Graph Condensation to Multi-Label Datasets: A Benchmark Study](https://mlsanity.com/paper/2412.17961/) (2024)

## Abstract (arXiv)

The rapid development of Internet technology has given rise to a vast amount of graph-structured data. Graph Neural Networks (GNNs), as an effective method for various graph mining tasks, incurs substantial computational resource costs when dealing with large-scale graph data. A data-centric manner solution is proposed to condense the large graph dataset into a smaller one without sacrificing the predictive performance of GNNs. However, existing efforts condense graph-structured data through a computational intensive bi-level optimization architecture also suffer from massive computation costs. In this paper, we propose reforming the graph condensation problem as a Kernel Ridge Regression (KRR) task instead of iteratively training GNNs in the inner loop of bi-level optimization. More specifically, We propose a novel dataset condensation framework (GC-SNTK) for graph-structured data, where a Structure-based Neural Tangent Kernel (SNTK) is developed to capture the topology of graph and serves as the kernel function in KRR paradigm. Comprehensive experiments demonstrate the effectiveness of our proposed model in accelerating graph condensation while maintaining high prediction performance. The source code is available on https://github.com/WANGLin0126/GCSNTK.