# Bonsai: Gradient-free Graph Condensation for Node Classification

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

## Key facts

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

## Builds on (most cited first, 23 of 23)

- [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)
- [Quantifying the Carbon Emissions of Machine Learning](https://mlsanity.com/paper/1910.09700/) (2019)
- [OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphs](https://mlsanity.com/paper/2103.09430/) (2021)
- [Graph Condensation for Graph Neural Networks](https://mlsanity.com/paper/2110.07580/) (2021)
- [Wasserstein Weisfeiler-Lehman Graph Kernels](https://mlsanity.com/paper/1906.01277/) (2019)
- [Condensing Graphs via One-Step Gradient Matching](https://mlsanity.com/paper/2206.07746/) (2022)
- [Structure-free Graph Condensation: From Large-scale Graphs to Condensed Graph-free Data](https://mlsanity.com/paper/2306.02664/) (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)
- [Navigating Complexity: Toward Lossless Graph Condensation via Expanding Window Matching](https://mlsanity.com/paper/2402.05011/) (2024)
- [Learning Articulated Rigid Body Dynamics with Lagrangian Graph Neural Network](https://mlsanity.com/paper/2209.11588/) (2022)
- [Unravelling the Performance of Physics-informed Graph Neural Networks for Dynamical Systems](https://mlsanity.com/paper/2211.05520/) (2022)
- [Enhancing the Inductive Biases of Graph Neural ODE for Modeling Dynamical Systems](https://mlsanity.com/paper/2209.10740/) (2022)
- [EXGC: Bridging Efficiency and Explainability in Graph Condensation](https://mlsanity.com/paper/2402.05962/) (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)
- [GraphReach: Position-Aware Graph Neural Network using Reachability Estimations](https://mlsanity.com/paper/2008.09657/) (2020)
- [FRIGATE: Frugal Spatio-temporal Forecasting on Road Networks](https://mlsanity.com/paper/2306.08277/) (2023)
- [Mirage: Model-Agnostic Graph Distillation for Graph Classification](https://mlsanity.com/paper/2310.09486/) (2023)
- [FAST-PPR: Scaling Personalized PageRank Estimation for Large Graphs](https://mlsanity.com/paper/1404.3181/) (2014)

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

- [GnnXemplar: Exemplars to Explanations -- Natural Language Rules for Global GNN Interpretability](https://mlsanity.com/paper/2509.18376/) (2025)

## Abstract (arXiv)

Graph condensation has emerged as a promising avenue to enable scalable training of GNNs by compressing the training dataset while preserving essential graph characteristics. Our study uncovers significant shortcomings in current graph condensation techniques. First, the majority of the algorithms paradoxically require training on the full dataset to perform condensation. Second, due to their gradient-emulating approach, these methods require fresh condensation for any change in hyperparameters or GNN architecture, limiting their flexibility and reusability. Finally, they fail to achieve substantial size reduction due to synthesizing fully-connected, edge-weighted graphs. To address these challenges, we present Bonsai, a novel graph condensation method empowered by the observation that textitcomputation trees form the fundamental processing units of message-passing GNNs. Bonsai condenses datasets by encoding a careful selection of textitexemplar trees that maximize the representation of all computation trees in the training set. This unique approach imparts Bonsai as the first linear-time, model-agnostic graph condensation algorithm for node classification that outperforms existing baselines across 7 real-world datasets on accuracy, while being 22 times faster on average. Bonsai is grounded in rigorous mathematical guarantees on the adopted approximation strategies making it robust to GNN architectures, datasets, and parameters.