Research map / Graph learning / GNN architectures
Bonsai: Gradient-free Graph Condensation for Node Classification
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Bonsai, a gradient-free, model-agnostic graph condensation method that selects exemplar computation trees via reverse k-NN coverage maximization in WL-kernel space, then sparsifies with PPR, running in linear time on CPU.
Problem
Existing graph condensation methods for node classification require training a GNN on the full dataset and must be redone for every GNN architecture or hyper-parameter change, and their condensed graphs are dense (fully connected), so they do not reduce edge-level computation.
Approach
Treat each node's computation tree as the basic unit, embed trees with a WL-kernel-style feature, and select exemplar trees that maximize coverage via reverse k-NN (greedy submodular maximization), then induce a sparse subgraph and refine with PPR-based pruning and enrichment; no gradients are used.
Key results
- Bonsai achieves the best accuracy in 12 of 18 dataset/ratio scenarios on GCN, e.g., 85.76% on Cora at 1% vs 77.56% for the second-best GCSR.
- Bonsai is on average more than 7x faster than the fastest baseline EXGC, e.g., 2.60s vs 34.87s on Cora at 0.5%, and is the only method to complete MAG240M (52.33% at 0.5%).
- Bonsai's condensation has lower carbon emissions than training on the full dataset in all listed datasets, unlike the baselines.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Bonsai instead of the strongest listed baseline at 1% compression | GCN condensation · Cora | accuracy: 77.56 ± 0.74 -> 85.76 ± 0.24 | Helped |
| Use Bonsai instead of the strongest listed baseline at 1% compression | GCN condensation · Citeseer | accuracy: 77.62 ± 0.71 -> 77.03 ± 0.33 | No clear effect |
| Use Bonsai instead of the strongest listed baseline at 1% compression | GCN condensation · Pubmed | accuracy: 80.80 ± 1.07 -> 87.08 ± 0.04 | Helped |
| Use Bonsai instead of the strongest listed baseline at 1% compression | GCN condensation · Flickr | accuracy: 46.99 ± 1.38 -> 49.05 ± 0.17 | Helped |
| Use Bonsai instead of the strongest listed baseline at 1% compression | GCN condensation · Ogbn-arxiv | accuracy: 62.31 ± 0.88 -> 58.35 ± 0.09 | Hurt |
| Use Bonsai instead of the strongest listed baseline at 1% compression | GCN condensation · Reddit | accuracy: 90.63 ± 0.84 -> 85.65 ± 0.08 | Hurt |
| Use Bonsai instead of the strongest listed baseline at 1% compression | GCN condensation · MAG240M | accuracy: 37.93 ± 0.08 -> 52.58 ± 0.33 | Helped |
| Remove PPR sparsification (ablation) | Bonsai · most datasets | accuracy | Hurt |
| Replace Rev-k-NN coverage maximization with random exemplar selection (ablation) | Bonsai · most datasets | accuracy | Hurt |
| Remove both PPR and Rev-k-NN selection (ablation) | Bonsai · benchmark datasets | accuracy | Hurt |
| Increase Rev-k-NN sample size (ablation) | Bonsai · benchmark datasets | accuracy | Helped |
| Set Rev-k-NN k to 5 (ablation) | Bonsai · benchmark datasets | accuracy | Helped |
Surprising findings
- Several baselines (GCond, GDEM, GCSR, EXGC, GEOM) have condensation times exceeding full-dataset training time on most datasets.
- Random node-induced subgraphs with partial neighborhoods perform worse than Bonsai's exemplar-tree selection, while Bonsai-Rev-kNN (random tree selection with PPR) often beats plain Random.
Limitations
- Relies on approximate knowledge of the number of GNN layers L.
- Some baseline comparisons are only reported on GCN for the main table; cross-architecture results are on a subset of datasets.
- Gradient-free selection uses sampling and greedy approximations whose accuracy depends on sample size and k.
Experimental setup
Datasets: Cora Citeseer Pubmed Flickr Ogbn-arxiv Reddit MAG240M
Benchmarks: Cora Citeseer Pubmed Flickr Ogbn-arxiv Reddit MAG240M
Metrics: test accuracy condensation time carbon emissions compression ratio
Baselines: Random Herding GCond GDEM GCSR EXGC GC-SNTK GEOM
Builds on: Weisfeiler-Lehman kernel GCond GDEM Herding
Closest papers by meaning
- GC4NC: A Benchmark Framework for Graph Condensation on Node Classification with New Insights (NeurIPS 2025 · similarity 0.93)
- Towards Pre-trained Graph Condensation via Optimal Transport (NeurIPS 2025 · similarity 0.91)
- Bi-Directional Multi-Scale Graph Dataset Condensation via Information Bottleneck (AAAI 2025 · similarity 0.90)
- GC-Bench: An Open and Unified Benchmark for Graph Condensation (NeurIPS 2024 · similarity 0.90)
- Navigating Complexity: Toward Lossless Graph Condensation via Expanding Window Matching (ICML 2024 · similarity 0.89)
- Classic GNNs are Strong Baselines: Reassessing GNNs for Node Classification (NeurIPS 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.