Bonsai: Gradient-free Graph Condensation for Node Classification

Authors: Mridul Gupta, Samyak Jain, Vansh Ramani, HARIPRASAD KODAMANA, Sayan Ranu
Primary area: learning on graphs and other geometries & topologies
Keywords: Graph Neural Networks, Machine Learning, Data Distillation, Graph Distillation, Dataset Distillation, Sustainable AI, Graph Condensation, Data Condensation, Dataset Condensation

Abstract:
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. To address these challenges, we present Bonsai, a novel graph condensation method empowered by the observation that *computation trees* form the fundamental processing units of message-passing GNNs. Bonsai condenses 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 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.

Decision: accept (poster)
Reviewer scores: 6, 6, 6, 6

Reviews and discussion:
<thread>
creation date:
1730085679329

thread_type:
official_review

<thread_object>
creator: reviewer_q9ty

<content>
summary:
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.

strengths:
S1: The problem is important in this field.

S2: Presentation is good. Good model name.

S3: The solution looks novel to me.

weaknesses:
W1: The experiments are not very standard. 

W2: Some recent works are not included as baseline.

questions:
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
</content>
</thread_object>

</thread>
<thread>
creation date:
1730429331041

thread_type:
official_review

<thread_object>
creator: reviewer_n8k1

<content>
summary:
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.

strengths:
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.

weaknesses:
See questions.

questions:
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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730730853426

thread_type:
official_review

<thread_object>
creator: reviewer_t6gr

<content>
summary:
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.

strengths:
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.

weaknesses:
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.

questions:
Please see the weaknesses
</content>
</thread_object>

</thread>
<thread>
creation date:
1730996288774

thread_type:
official_review

<thread_object>
creator: reviewer_yqxy

<content>
summary:
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.

strengths:
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.

weaknesses:
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.

questions:
See weakness
</content>
</thread_object>

</thread>
<thread>
creation date:
1732036056582

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Cover letter

comment:
We thank the reviewers for their insights and constructive suggestions. A comprehensive point-by-point response to the reviewers' comments is presented below. **We have updated the main manuscript** to address these comments. The changes made in the manuscript are highlighted in **blue** font. The major additional changes are listed below.

- **Additional experiments:** We have incorporated all of the additional experiments requested by the reviewers spanning
    - Three additional baselines of EXGC, GCSNTK and GEOM
    - Expanded ablation study in Fig. 4
    - Additional data on carbon emissions
    - Empirical analysis that highlights relationship between WL embedding similarities and training gradients

- **Presentation:** We have addressed several presentation-related inquiries, such as highlighting differences between Mirage and Bonsai, moving auxiliary details to appendix, and adding clarifications wherever appropriate.

We hope these revisions will satisfactorily address the concerns raised by the reviewers and elevate the overall quality of our work. We remain open to any further suggestions.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732786957297

thread_type:
official_comment

<thread_object>
creator: area_chair_gc58

<content>
comment:
I would like to encourage the reviewers to engage with the author's replies if they have not already done so. At the very least, please 
acknowledge that you have read the rebuttal.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This authors proposes a gradient-free graph distillation/condensation method based on the observation that  similar computation trees imply similar embeddings, which in turn imply similar gradients. The method is model-agnostic, retains the original node features, and scalable. The reviewers were convinced by both the idea and the experimental results. The reviewers also appreciated the theoretical analysis (simple but interesting).