Bonsai: Gradient-free Graph Distillation for Node Classification
Graph Neural Networks;Machine Learning;Data Distillation;Graph Distillation;Dataset Distillation;Sustainable AI
Yes
No ethics review needed.
See weakness
1. Compared to previous works, BONSAI is novel.
2. The experimental results look very good, especially regarding the training time.
3. The theoretical analysis is solid.
This paper proposes a novel graph distillation method empowered by the observation that computation trees form the fundamental processing units of message-passing GNNs. This paper specifically addresses the issue of overly dense edges in graph distillation. Experiments on various datasets verify the effectiveness of the method.
1. This paper is not easy to understand.
2. In some cases, BONSAI does not perform the best, such as with citeseer.
3. Regarding table 5, can you provide experimental results for other compression rates?
4. PPR and RkNN involve many parameters, and the ablation study in Fig. 4(b) is insufficient.
Yes
No ethics review needed.
Please see the weaknesses
1. The proposed gradient-free approach bypasses the need for computationally expensive gradient calculations, resulting in a significantly faster distillation process. This efficiency makes Bonsai highly scalable even for large datasets.
2. This model-agnostic method is interesting and saves efforts in hyperparameter tuning when changing condensation models.
3. It is the first distillation method that retains the original node features and synthesizes graphs with unweighted edges, which more faithfully represent the original graph structure.
This paper studies critical limitations in existing graph distillation methods. It introduces a new approach that optimizes the training of GNNs by generating smaller, representative datasets without requiring full training on the original data. The proposed method leverages a computation tree-based approach to create a distilled representation that is efficient, adaptable, and capable of maintaining high accuracy across varied datasets and models. Experimental results have demonstrated its effectiveness and efficiency.
1. The idea of Bonsai is very similar to MIRAGE[1], as both methods select frequent trees. This similarity makes Bonsai appear to be a minor adaptation of MIRAGE. Furthermore, much of the theoretical analysis, such as Graph Isomorphism, is borrowed from MIRAGE. Although these two works focus on different tasks, it's strongly recommended to discuss the differences between Bonsai and MIRAGE in the related work section.
2. This paper claims that "distilling to fully-condensed graph" is a problem for previous work. However, most prior methods include a sparsification step, setting a threshold to obtain a sparse graph. Consequently, the number of edges reported in Table 2 is inaccurate. For correct edge counts, please refer to Table 5 in the GCond paper [2].
3. Although this paper presents comprehensive deductions in the theoretical section, some hypotheses appear to be too strong and lack support. For example, Hypothesis 1 (line 201) and Logical Progression 2 (line 215) may not hold true.
4. In Fig. 2, the authors empirically demonstrate the correlation between GNN embedding and WL embedding. When the threshold is large, almost all node pairs are considered, leading to a low correlation. How does this observation inform the method design?
5. In line 235, **Diversity** is highlighted. Which part of the method addresses this concern?
6. To select the trees with top representativeness, why do the authors choose Reverse K-NN? Would it be possible to simply adopt clustering instead?
7. The experimental settings differ from commonly used ones in the following ways: (a) Different dataset split (i.e., training/validation/test set split) (b) Different metric for compression rate. The authors are suggested to clarify the reasons for choosing a different setting.


### Minor
1. The details of PPR starting from line 332 could be simplified or moved to the Appendix as people are familiar with it.
2. Why is Herding OOT (out of time) for Reddit? In my understanding, this method should be efficient.

### References
[1] Mridul Gupta, Sahil Manchanda, HARIPRASAD KODAMANA, and Sayan Ranu. Mirage: Model-
agnostic graph distillation for graph classification. In ICLR 2024

[2] Wei Jin, Lingxiao Zhao, Shichang Zhang, Yozen Liu, Jiliang Tang, and Neil Shah. Graph condensa-
tion for graph neural networks. In ICLR, 2021.
Yes
No ethics review needed.
1. Could the authors clarify their specific contributions to Mirage [A]? While Mirage highlights the importance of the computation tree in graph dataset condensation, their primary focus is on the graph level (with node-level experiments included in the appendix). Thus, extending their approach to the node level by following the 1-WL test may not represent a substantial novelty.
2. Regarding Fig. 4(b), although the authors emphasize the significance of the RkNN and PPR components, the random exemplar selection still yields considerable results. How do the authors interpret this outcome? Could they also provide a performance comparison for $\mathbf{S_r}$ using different exemplars on datasets like Cora, Ogbn-arxiv, and Reddit? Including results for random selection would further clarify the comparison.
3. From my perspective, selecting datasets using a sampling strategy seems more akin to traditional graph reduction, sparsification, or coarsening methods, rather than directly aligning with the field of graph condensation. Therefore, it’s challenging to accept the significant improvements claimed over random or herding baselines. Could the authors provide an intuitive example to support their approach?

[A] Mridul Gupta, Sahil Manchanda, HARIPRASAD KODAMANA, and Sayan Ranu. Mirage: Model
agnostic graph distillation for graph classification. ICLR 2024.
1. The performance of bonsai is impressive, including the cross-arch results.
2. The proof of maximizing the representative power of exemplars is NP-hard is simple but attracting.
The paper presents Bonsai, a gradient-free graph distillation method for node classification that overcomes limitations in existing approaches. By selecting exemplar computation trees rather than synthesizing fully connected graphs, Bonsai efficiently distills graphs without needing full dataset training or specific GNN architectures. This approach achieves higher accuracy and faster distillation across various datasets and GNN models.
See questions.
Yes
No ethics review needed.
Q1: Why the authors choose 0.5%, 1% and 3% as $S_r$? This setting does not align with previous works.

Q2: Recently, a lot of works have studied the efficiency of graph condensation, e.g., Exgc [1] and GC-SNTK [2]. These two methods should be included as baselines when comparing condensation time. By the way, it would be better to present time comparison via table than figure.

Q3: Other graph condensation methods should be included for accuracy comparison, e.g., SGDD [3], SFGC [4], GEOM [5].

[1] Exgc: Bridging efficiency and explainability in graph condensation

[2] Fast Graph Condensation with Structure-based Neural Tangent

[3] Does graph distillation see like vision dataset counterpart

[4] Structure-free graph condensation: From large-scale graphs to condensed graph-free data

[5] Navigating Complexity: Toward Lossless Graph Condensation via Expanding Window Matching
S1: The problem is important in this field.

S2: Presentation is good. Good model name.

S3: The solution looks novel to me.
This paper proposes Bonsai, a linear-time, model-agnostic graph distillation algorithm for node classification. It observe three limitations of previous works, Full Gnn training, Distilling to a fully-connected graph and Model-specific. To address these limitations, Bonsai  aims to identify a set of b exemplar computation trees that optimally represent the full training set.
W1: The experiments are not very standard. 

W2: Some recent works are not included as baseline.
An unsupervised and model/hyper-parameter agnostic graph distillation algorithm for Node CLassification
@inproceedings{
anonymous2024bonsai,
title={Bonsai: Gradient-free Graph Distillation for Node Classification},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=5x88lQ2MsH},
note={under review}
}
Graph distillation 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 distillation techniques. First, the majority of the algorithms paradoxically require training on the full dataset to perform distillation. Second, due to their gradient-emulating approach, these methods require fresh distillation 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 distillation method empowered by the observation that *computation trees* form the fundamental processing units of message-passing GNNs. Bonsai distills datasets by encoding a careful selection of *exemplar* 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 distillation algorithm for node classification that outperforms existing baselines across $6$ 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.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Graph Neural Networks Machine Learning Data Distillation Graph Distillation Dataset Distillation Sustainable AI
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/5e6dee9f6f09baa2fbf9192440313288218d1f08.pdf
learning on graphs and other geometries & topologies
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
Bonsai: Gradient-free Graph Distillation for Node Classification
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission