Bonsai: Gradient-free Graph Condensation for Node Classification
Authors: Mridul Gupta
Samyak Jain
Vansh Ramani
HARIPRASAD KODAMANA
Sayan Ranu
Venue: ICLR 2025 Poster (2025)
Keywords: Graph Neural Networks
Machine Learning
Data Distillation
Graph Distillation
Dataset Distillation
Sustainable AI
Graph Condensation
Data Condensation
Dataset Condensation
Primary area: learning on graphs and other geometries & topologies
TL;DR: An unsupervised and model/hyper-parameter agnostic graph condensation algorithm for Node CLassification

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.

Published as a conference paper at ICLR 2025
BONSAI: GRADIENT-FREE GRAPH CONDENSATION FOR NODE CLASSIFICATION
Mridul Gupta
Samyak Jain 2*
Vansh Ramani
Hariprasad Kodamana" 1,3,4 Sayan Ranul-2
Yardi School of Artificial Intelligence 3 "Department of Chemical Engineering
Department of Computer Science
Indian Institute of Technology Delhi, New Delhi, 110016, India
Indian Institute of Technology Delhi, Abu Dhabi, Zayed City, Abu Dhabi, UAE
(mridul. guptadacai, ce500 orrp.a/seeaooooaoooooooooeaeeear .itdd. iitd..itie. aatd.acc.i
kodamana@,
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 GNN architecture, limiting their flexibility
any change in hyper-parameters 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 message passgeggggnng GNNS. BONSAI condenses datasets by encoding careful selection of exemplar trees that maximize the representation of all computation trees the training set. This unique approach imparts BONSAI 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.
INTRODUCTION AND RELATED WORKS
Graph Neural Networks (GNNS) have shown remarkable success in various predictive tasks on graph data such as node classification and link prediction (Veličković et al., 2018; Kipf & Welling, 2017; Hamilton al., 2017: Nishad et al., 2021), modeling physical systems (Bhattoo al., 2022: Thanga- muthu et al., 2022; Bishnoi et al., 2023; 2024), and spatio-temporal data (Jain et al., 2021: Gupta et al., 2023). However, real-world graphs often contain millions of nodes and edges making the training pipeline slow and computationally demanding (Hu et al., 2021). This limitation hinders their adop- tion resource-constraingg datasets (Hu et al., 2021). Graph condensation (also called graph distillation) has emerged promising way to bypass this bottleneck (Jin et al., 2021; Liu et al., 2024a;b; Zheng et al., 2023). The objective in graph condensation is synthesize significantly smaller condensed data set that retains the essential information of the original data. By training GNNS on these condensed datasets, we can achieve comparable performance while reducing computational overhead and storage costs. This makes GNNS more accessible and practical for wider range of applications, including those with limited computational resources and large-scale scale datasets. In this work, we study the problem of graph condensation for node classification.
environments (Miao et al., 2021) and applications dealing with massive
1.1 EXISTING WORKS AND THEIR I LIMITATIONS
Table presents existing graph condensation algorithms proposed for node classification and their characterization across various dimensions. We omit listing DOsCOND (Jin et al., 2022), MI. RAGE (Gupta al., 2024), and KIDD (Xu al., 2023) in Table I since they designed for graph classification, whereas we focus on node classification.
*enotess equal contribution.

---

Published as a conference paper at ICLR 2025
Table 1: Characterization of existing graph condensation algorithms. Cells shaded in Red indicate the presence of an undesirable property, while Green represents their absence.
Algorithm
Requires training GNN on full-dataset
Condenses to a fully- connected graph'
Model-specific
condensation
GCOND (Jin et al., 2021)
SGDD (Yang al., 2023)
SrGe (Zheng et al., 2023)
GC-SNTK (Wang et al., 2024)
X
Exuc (Fang ul., 2024)
GFOM (Zhang et al., 2024)
X
<
GDEM (Liu et al., 2024a)
X
X
GESs (Liu 2024b)
BONSAI
X
X
Full GNN training is pre-requisite: The fundamental requirement of data condensation is that it should require less computational resources and time than training on the full dataset. However, this basic premise is violated by majority of the techniques (See Table 1) since they adopt a design where training the target GNN on the full trainset is a prerequisite to condensation. These algorithms adopt gradient-dependen optimization framework. They first train GNN on the full trainset and extract gradients of model parameters over epochs. The condensation process is formulated as an optimiza- tion problem create condensed dataset that replicates the gradient trajectory observed in the original training set. This need for full dataset training for condensation contradicts its fundamental premise, which we address in our work.
a message-passing GNN, the computation cost of each forward pass is O(EE),, where & denotes the set of edges. Consequently, the computational effectiveness of graph condensation is primarily determined by the reduction in edge count between the original and condensed graphs, rather than node count alone. However, current graph condensa- tion algorithms (see Table 1) quantify the condensation ratio based on the node count. This creates a fundamental disconnect between the metric used evaluate compression (node count) and the computational goal of reducing (IE)), which directly governs training and inference time. Conse- quently, this misalignment can lead to a condensed graph that less efficient than the original.
Node compression vs. Edge complexity:
Model-specific condensation: Gradients of model weights are influenced by the specific GNN architecture and any architectural change, such as switching from GCN (Kipf & Welling, 2017) to a GAT (Veličković adjustments, necessitates new round of condensation.
(e.g.. number of layers, hidden dimensions, etc.). Consequently,
et al., 2018), or
1.2 CONTRIBUTIONS
To address the limitations outlined in Table I, we present BONSAI?
Gradient-free condensation: Instead of replicating the gradient trajectory. BONSAI emulates the distribution of input data processed by message-passingg GNNS. By shifting the computation task to the pre-learning phase, BONSAI achieves independence from syper-parameters and model archi- tectures as long as it adheres to a message-passing GNN framework like GAT, GCN, GRAPHSAGE, GIN, etc. Moreover, this addresses critical limitation of existing graph condensation algorithms that necessitates training on the entire training dataset.
Novel algorithm design: BONSAI is empowered by the observation that any message message-passing GNN decomposes graph of nodes into rooted computation trees. Furthermore, topologically similar computation trees generate similar embeddings regardless of the GNN being used (Xu al., 2019; Togninalli et al., 2019). BONSAI exploits this observation to identify a small subset of diverse com- putation trees, called exemplars, that are located in dense regions and thereby representative of the full set. Hence, the induced subgraph spanned by the exemplars forms effective condensed set. Empirical evaluation: We perform rigorous benchmarking incorporating state-of of-the-arr graph condensation algorithms 7 real-world datasets containing up to hundreds of millions of edges. Our analysis establishes that BONSAI (1) achieves higher prediction accuracy, (2) produces at least 7-times faster condensation times despite being CPU-bound in contrast to GPU-bound condensation of baselines, and (3) exhibits superior robustness to GNN architectures and datasets.
'Some algorithms sparsify the fully-connected graph based on edge weights. But this sparsification process requires training on the fully connected graph itself to identify the pruning threshold.
"Inspired by the art of Bonsai, which transforms large trees into miniature forms while preserving their essence, our graph condensation algorithm gracefully prunes redundant computation trees, creating a condensed graph that is significantly smaller yet maintains comparable performance.
2

---

Published as a conference paper at ICLR 2025
2 PROBLEM FORMULATION AND PRELIMINARIES
Definition (Graph). G E, denotes a graph over a finite, non-empty node set V and edge set & {(uu v) u,o E V}. RIV|x|FI denotes node attributes encoded using F-dimensional feature vectors. We denote the attributes of node v as Ny-
Two graphs are identical if they are isomorphic to each other.
Definition 2 (Graph Isomorphism). Graph 91 is isomorphic to graph 92 if there exists bijective mapping between their node sets that preserves both edge connectivity and node features. Specif- ically, 91 is isomorphic G2 < 3f V1
V/2 such that: (1) f is bijection, (2) X.
Xf(u): where v E f(v) E V22 and (3) (u, v) E E if and only if (f(,,, E E
The problem of graph condensation for node classification is defined as follows.
Problem 1 (Graph Condensation). Given train and validation graphs, Grr and Guat, respectively, and a memory budget in bytes, synthesize a graph from 9rr within the budget, while minimizing the error gap between G. and Gty on the validation set, i.e., minimize {leg. cg...). eg represents the node classification error on validation set when trained on graph G.
2.1 COMPUTATION STRUCTURE OF GNNS
GNNS operate through an iterative process of information exchange between nodes. Let x, E RIFI represent the initial feature vector of node V. The propagation mechanism proceeds follows:
Initialization:
Set h. = Xv, Ye E V.
Message creation: In layer L, collect and aggregate messages for each neighbor.
m (u) MESSAGE' (h 1n-1), Vu Eu, {u (u, E
m p AGGREGATE ( (1 (fm, (u) uu N
Update embedding: h UPDATE (h m
2-hop paths P1
2-hop paths from 211
Here, MESSAGE AGGREGATE', and UPDATE may be predefined operations (e.g.. mean pooling) or
Pt. P1.Pa.P1
Computation tree
Py1.
Pi. P2
Pit, Pio: Vy
learnable neural networks. B- denotes a multiset. This process repeats for L layers, yielding the final node representations h..
Ps P2.
Piz. Va. P11
Pi. Po
Pizz Pg. By
Wig, Mg. Py
computation free describes how information prop- agates through the graph during the neural network's operation (Xu et al., 2019).
Sample Graph
V4
V'
V1
3/4
V/
P11
Definition (Computation Tree). Given a graph G (V, E)),, node E V and the number of layers L in the GNN, the computation tree T- rooted is constructed follows:
Figure 1: The figure depicts the construction of computation trees for nodes t1 and 0n1 in the sample graph, at depth L 2. Node col- ors indicate their labels. Despite being distant from each other in the graph and embedded non-isomorphic L-hop neighborhoods, v1 and 1n i have isomorphic computation trees.
Enumerate all paths of length L (including those with repeated vertices) starting from v. Merge these paths into a tree structure where:
1. The root is always and
2. Two nodes from different paths are merged if: (i) They are at the same depth their respective paths, and (ii) All their ancestors in the paths have already been merged.
Fig. 1 illustrates the idea of a computation tree with an example.
Properties of computation frees: We now highlight two key properties of computation trees, formally established in Xu et al. (2019), that form the core our algorithm design. These properties hold regardless of the underlying bessagg-passsigg GNN (GCN, GAT, GRAPHSAGE, GIN, etc.).
Property (Sufficiency). In an L-layered GNN, the computation tree T is sufficient to compute node embedding h Vu V. Hence, given graph = (V, E, X), we may treat il as a (multi)set of computation trees T = (T.L Yv E V). Clearly, [T [V].
Property (Equivalence). If isomorphic to T then h = h since the expressive power of messagg-ppassnng GNN is upper bounded by the Weisfeiler-Lehmee Lehman test (1 (1-WL) (Xu et al., 2019).
3

---

Published as a conference paper at ICLR 2025
Pearson's Correlation
1.0
Citeseer Pubmed
Pearson's Correlation
1.00
Citeseer
Pearson' Correlation
1.0
Citeseer
0.75
Cora Pubmed
Cora
Pubmed
0.6
0.50
0.6
0.4
0.25
0.4
0.00
0.2
0.2
-0.25
0.00
0.25
0.50
1.00
0.00
0.25
0.50 0.75
0.00
0.25
0.50
0.75
1.00
Distance Threshold
Distance Threshold
Distance Threshold
(a) GCN
(b) GIN
(c) GAT
Figure 2: Pearson correlations between the Lg distances of node pairs in the GNN embedding space and the unsupervised embeddings derived from the WL-kernel, computed for pairs with a specific distance threshold in the WL-space (x-axis).
Motivated with the above observations, we explore relaxation of the Equivalence property: do nodes rooted at topologically similar computation trees generate similar node embeddings? To explore this hypothesis, we need method to quantify the distance between computation trees. Given that the Equivalence property is derived from the 1-WL test, the Weisfeiler-Lehman kernel (Togninalli et al., 2019) presents itself as the natural choice for this distance metric.
Definition 4 (Weisfeiler-Lehmall (WL) Kernel (Togninalli et al., 2019)). Given graph g (V. X), WL-kernel constructs unsupervised embeddings over each node the graph via message passsing aggregation. Like in GNNS, the initial embedding aL: in layer 0 is initialized to Ny. Subsequently, the embeddings in any layer is defined as:
a a(())
4-1 a
Σ WEN(()
w((e, a
=
deg(v)
Here, (Vv) denotes the neighbors of v, deg(v) (w) and w((e, u)) for unweighted graphs.
By emulating the same message messagge-assing framework employed by GNNs, the unsupervised embedding a. jointly encapsulates the topology and node attributes within the computation tree T.h. Hence, the distance between two computation trees T. and T L defined to be:
(T.² Te²) = | a!il2
While the T22 norm, may other distance functions vectors as well. The following corollary follows from the Eq. 2.
Corollary 1. T! isomorphic to Th, then a = = Hypothesis (Relaxed Equivalence). Tf Te,, then a a and, therefore by by irre- spective of the specific message-passinee architecture employed.
To test our hypothesis, Fig. 2, we examine all node pairs within specified distance threshold based the Weisfeiler-Lehman (WL.) kernel. We then analyze the correlation between their un- supervised WL-distance and the L2 distance between their GNN embeddings. The results reveal compelling trend: between WL-distance and GNN embedding distance. This pattern supports our hypothesis, indicat- ing that computation trees that proximate in the WL-space also exhibit proximity in the GNN embedding space.
decrease the distance threshold,
observe strengthening correlation
BONSAL: PROPOSED METHODOLOGY
Fig. 3 presents the pipeline of BONSAI, which is founded on the follow- ing logical progression:
Table 2: Correlation be-
tween WL-embedding sim- ilarities and training gradi- ents.
1. Similar computation trees produce similar GNN embeddings (Hy- potheses 1).
2. Similar GNN embeddings generate comparable outputs, resulting in similar impacts on the loss function and, consequently, on the gra- dients Table 2 presents empirical data supporting this relationship. showing statistically significant correlations (p < 0.05) between WL-eemeedingg similarities and training gradients.
Dutuset
Correlation
p-valuc
Cor
0.74
0
Citeseer
0.83
2 0
Pubmed
Reddit
0.42
%: 0
4

---

Published as a conference paper at ICLR 2025
Input Graph (Training Set)
Computation Trees
WL Keme
high NAM
addinesiional embeddied
addimeraional airbadding
netgibeur
RKNN and coverage maximisation
spariffiatiion using Pensonallzed Pagelank
Induced subgraph spanned topa compptatittttnooonnn thees
Rankd
Condensed Graph
Fitting until budget is filled
Figure 3: Pipeline of the proposed algorithm for graph condensation using toy example is displayed. We use L = 1 and k = 2 for this example.
Building on this reasoning. BONSAI aims to identify set of b exemplar computation trees that opti- mally represent the full training set', These exemplars are selected based on two critical criteria:
Representativeness: Each exemplar should be similar trees from the input training set, ensuring it captures common structural patterns. We quantify the representative power of computation tree using the idea of reverse k nearest neighbors ($ 3.1). Specifically, if tree Tj is among the k-NN tree T3 for a small k. this indicates these two trees are similar in WL-embedding. Hence, seek to include those trees in the condensed set that reside the K--N of lots other trees. Consequently, if these trees are selected, their GNN embeddings are also likely similar to their k-NN neighbors from the WL space. As result, they can effectively approximate the GNN embeddings of the filtered-out nodes. Since similar GNN embeddings lead similar gradients (Table 2), we minimize the information lost from nodes that are filtered out. Diversity: The set of exemplars should be diverse, maximizing the coverage of different structural patterns present in the original graph ($ 3.2). To achieve this objective, we develop greedy tree selection algorithm (Alg. 1), which begins with the reverse k-NN set and iteratively selects the computation tree that appears in the k-NN sets of the maximum number of currently uncovered trees. This approach ensures two key properties:
large number of other computation
It systematically captures trees that are centrally located within the graph's embedding space. 2. It progressively selects trees that provide maximum coverage of the remaining, yet-unselected computation trees.
By prioritizing trees with the highest marginal impact uncovered trees, method naturally cre- ates a diverse subset that comprehensively represents the original graph's s structural and computa- tional characteristics. The induced subgraph spanned by these exemplar trees forms the initial densed set. This initial version undergoes further refinement through an iterative process of edge sparsification and enrichment reduce O((E)) complexity of GNNS.
3.1 QUANTIPYING REPRESENTATIVENES THROUGH REVERSE k-NN
Utilizing Sufficiency (Property 1), we decompose the input graph 9 (V,E, X) into set of | computation trees T and then embed them into feature space using WL-kernel (See Fig. 3), We now identify representative exemplars by analyzing this space.
The k nearest neighbors of computation tree Th T, denoted k-NN(T.)), are its k nearest computations trees from in the WL-kernel space (Def. 4).
Definition (Reverse k-NN and Representative Power). The reverse N-NN of denotes the set of trees that contains T, in their k-NNs. Formally, Rev-k-NN(TT)) = [T! T K-NN (-NN(TT.)) The representative power of T is:
II (T:) |Rev-K-NN(TT')
(3)
T
We overload the notation for the budget by denoting the number of exemplar trees that fit within the input budget constraint (Recall Problem. b.
5

---

Published as a conference paper at ICLR 2025
If T.' k-NN(TT')) for small k, it suggests that h h (Hypothesis 1). Consequently, a high TI (T.4) indicates that Th frequently appears in the k-NN lists of many other trees and is therefore positioned in a dense region capturing shared characteristics across many trees. Hence, it serves as strong candidate of being exemplar.
3.1.1 SAMPLING FOR SCALABLE COMPUTATION OF REVERSE k-NN
Computing k-NN for each tree consumes On log log z (n)) time (since k < n)), where [ Since [T] = n, computing k-NN for all trees consumes O(n²) time. Hence, computing reverse k-NN for all trees consumes (n²²) time well, which may be prohibitively expensive for graphs containing millions nodes. To address this challenge, we employ a sampling technique that offers a provable approximation guarantee on accuracy. This is achieved follows. Let sample < n trees uniformly at random from T, which we denote as S. Now, we compute the k-NN of only trees in S, which incurs (22) computation cost. We next approximate reverse k--N of all trees in T based only on S. Specifically, Rev-k-NN (Teh) (THs E Te' k-NN (Td)) }- The approximated representative power is therefore:
(T Rev-k-NN((Tt)
[|]
The sample size balances the trade-off between accuracy and computational efficiency. By applying Chernoff bounds, we demonstrate in Lemma that can be precisely determined to maintain the error within specified error threshold 6, with confidence level of 1 - 5.
Lemma 1.
Given a desirable error upper bound 0 and a confidence interval of 1 8, we sample at least in (3) (2+0)) trees in S, then for any T E T: 82
P - II (T:) S 2
(5)
PROOF. For the formal proof, see App. A.1. Lemma I induces the following positive implications.
The number of samples needed is independent of the size T.
Because grows logarithmically with ln(3),, even a small sample size provides high confidence.
Hence, the computation cost of Rev-k-NN reduces O(n) since <<
3.2 COVERAGE MAXIMIZATION
We aim find the set of exemplar computation trees with the maximum representative power. Definition (The exemplars). Let the representative power of a set of trees be denoted by:
Rev-k-NN (T:L) /
(A) = U
T
(6)
VTLEA
Then, given the set of computation trees T and the budget b, we seek to identify the subset of compu- tations trees, termed exemplars, h., by maximizing the following objective:
A. max
IT(A)
For brevity of discourse, Theorem 1. Maximizing the representative power of ex- emplars (Eq. 7) is NP-hard.
we proceed assuming the true
reverse
k-NN
set.
Algorithm I The greedy approach
Require: Graph G. budget b, RNN (TT)
PROOF. App. A.2 presents the formal proof by reducing to
Ensure: solution set à. [A] =
the Set Cover problem (Cormen et al., 2009).
0
I: A
2:
while size(A) (within budget) do
Fortunately, Eq. 6 is monotone and submodular, which al- lows the greedy hill-climbing algorithm (Alg. 1) to ap- proximate Eq. 7 within provable error bound.
3:
T.t + arg arg (TT(A (T.h))
[[AA]
A AU
5: Return
Theorem 2. The exemplars, Agreedy, selected by Alg. 1
provides 1 f/e approximation, ie., I[ (Aggody)y (1 -1- (T(*).

---

Published as a conference paper at ICLR 2025
PROOF. App. A.3 presents the proofs of monotonicity and submodularity of (I)... For monotonic and submodular functions, greedy selection provides 1 - 1//e approximation (Feige, 1998).
Alg. I begins with the reverse k-NN set of each computation tree imput. It then iteratively selects trees based on their marginal cardinality specifically, choosing the tree that appears in the k-NN sets of the largest number of yet-uncovered trees (lines 3-4). A tree is considered uncovered if none of its k-nearest neighbors have been selected for the condensed set. This focus on marginal contribution naturally promotes diversity. Consider two similar trees, Ti and T2, both with high reverse k-NN cardinality. Due to the transitivity of distance functions, these trees likely share many of the same neighbors in their reverse k-NN sets. Consequently, if [ is selected, T2's 's marginal cardinality sig- nificantly decreases despite its high initial reverse k-NN cardinality, preventing redundant selection of similar trees.
We further enhance the efficiency of Alg. by exploiting the property of monotonically decreasing marginal gains in submodular optimization (Leskovec et al., 2007).
Initial condensed graph: The initial condensed graph G. = (V,, X,) is formed by extracting the induced subgraph spanned by the exemplar computation trees, i.e. V. V., E V.} and X, = (xx) u E V. Set
{u E., E Aggreedy: (v). & = ((u, (v) contains nodes within L hops from u.
Sparsification and Enrichment: In the final step, we seek sparsify the graph induced by the exemplar trees. Furthermore, in the additional space created due to sparsfication, we include more exemplar trees, resulting in further magnification of the representative power. Further details of our implementation is provided in App. A.4.
3.3 PROPERTIES OF BONSAI
Complexity analysis: The computation complexity of BONSAI is +(IV)+18) (details in App. A.5).
CPU-bound and Parallelizable: BONSAI does not involve learning any parameters through gradient descent or its variants. Hence, the entire process is CPU-bound. Furthermore, all steps are embarrassingly parallclizable leading condensation of datasets with hundreds of millions of edges within minutes.
Independence from model-architecture and hyper-parameters: Unlike majority of existing condensation algorithms that require knowledge of the GNN architecture and all training hyper- parameters, BONSAI only requires approximate knowledge of the number of layers L.
4 EXPERIMENTS
In this section, we benchmark BONSAI and establish:
Superior accuracy: BONSAI consistently outperforms existing baselines in terms of accuracy across various compression factors, datasets, and GNN architectures.
Enhanced computation and energy efficiency: On average, BONSAI is at least 7 times faster and 17 times more energy efficient than the state-of-the-art basclines.
Increased robustness: Unlike existing methods that require tuning condensation-specins hyper- parameters for each combination of GNN architecture, dataset, and compression ratio, BONSAI achieves superior performance using single set of parameters across all scenarios.
Our implementation is available https://gtthub.comm/// Table 3: Datasets.
4.1
EXPERIMENTAL SETUP
Dataset
Edges
Classes
Features
The specifics of our experimental setup, including hardware and software environment, and hyper- parameters are detailed in App. B. For the baseline algorithms, we use the code shared by their respective authors. We conduct each experiment 5 times and report the means and standard deviations.
Crea (Kipf & Welling, 2017)
Citeseer (Kipf Welling, 2017)
2,708
10.556
9.104
7 1,433
Pubmed (Kipf & Welling, 2017)
19:717
85,648
3
500
Flickr (Zeng al., 2020)
89.250
899,756
7
500
Oghn arxiv (Hu
2021)
2.315,598
Reddit (Hamilton et al., 2017)
232.965
23,213,838
41
602
MAG240M (Hu al., 2021)
1,398,159
26,434,726
153
768
Datasets: Table 3 lists the benchmark datasets used.

---

Published as a conference paper at ICLR 2025
Table 4: Accuracy achieved by the various baselines on benchmark datasets across various com- pression ratios over byte consumption (denoted S, (%)), on the GCN architecture. The best and the second-best accuracies in each row are highlighted by dark and lighter shades of Green, respectively. OOT indicates the scenario where the algorithm failed condense within 5 hours.
Dalaset
Random
Herding
GCond
GDEM
GCSR
EXGC
GUSNTK
GEOM
BONSAI
Full
0.5
30.90 is
45.61
17.30
07-49
74
77.8510.7 34
33.76
83 35
Cora
52.07
11.30.0.31
09.32147:
77.561874
36, 24
67 67.5210.77
30.02.000
85.761021
18.56.00.
62.26
80,..000
81.73an.4s
81.70
77.20
36.42
75.6419.2
54.80a1.00
80.38
0.5
33.90
22 22.00
70.00a2.40
67.03
20. 42ans
89.02.
24.02
CiscSeer
4d. 11.00=2:32
49. 10c5.02
72
72. 18
74.77
20.67
69 22
28.00 Mal.s
77 00l09:5
78.50
11. 21
67 0000..0
17. 22
76. a0
77:27
25.07
33. 88..88
76 80.880
40.63
80.72.0.03
79.4
45.77a0
03.04
ODT
Pubmed
19
79.92
80.50
79.11
44
81..33
87.22.0000
$2. 02.50mmmm
78.00
77.00=a.15
81.0730.00
79.94
47.02am07
67 67.72e2.0
O0T
87 87.6120m
0.5
4d. 41788
47 98
16.00:1100
06. L5
66.41ma.co
45.47
31.977
O0T
15. 23:077
Flickr
1122aaum
16. 16.72:0.01
39 88
16. 1.999
OOT (5
15. s8.97
42 50tesss
O0T
19 06:0.1
50.93=muu
36.36mmm
46.54
16.04a1.6
47.35
36.58
on
25.00
64.73104 12.63.0mm
60:0611:6
18.47
Oghn-arxiv
29.27
$4.91 15.40
50.40mmmm
51.451114
O0T
61.73s1-4
62 01..5
DOT
58. 56.35 m
68.97
57. 28
52.01:0044
50,37
OCT
62. 12.961131
36 30100.7
OOT
61:31
36,00 00:00=4:33
$1.72
38.91
90.5130.35
O0T
78.47
37 57.15
00T
80,33s9
Reddit
13.96-133
90.63em:44
81660s111
38 87.870
44.97a2m
88. 51 25.15
08.78:0ass
85, 78
OCT
00M
47.48
OCT
00
0.5
36.18 34.4
OOT
0OM
O0T
0OM
00T
DOT
MAG240M
87.58 98:3nns
37 29 05.06
OOT
00M
OCT
00M
00T
00T
52 (0.58
69.96
43.96
OCT
00M
O0T
00M
00T
00T
5d. 54.39
Baselines: Table 1 lists all the graph condensation algorithms for node classification. We omit SEGC (Zheng et al., 2023) and SGDD (Yang et al.. 2023) as baselines since both GDEM and GcsR have been shown to outperform them. Among non-neural, baselines, we compare with selecting the induced subgraph spanned by a random selection of nodes, and Herding (Welling, 2009).
Metrics:
Prediction quality is measured through Accuracy on the test set, i.e., the percentage of
correct predictions. Compression ratio is quantified as S, size of full data sct bytcs
size of condensed dataset in bytes
4.2 PREDICTION ACCURACY
Table presents the accuracies obtained by BONSAI and the baselines on GCN. BONSAI achieves the best accuracy in 12 out of 18 scenarios, with substantial improvements (2 5%) over the second- best performer in several cases. This demonstrates that the unsupervised gradient-agnostic approach adopted by BONSAI does not come at the cost of accuracy. GDEM emerges the second best perfomer. GCsR fails to complete in the two largest datasets of Ogbn-arxiv and Reddit, since it trains on the entire dataset 100 times to condense, which exceeds 5 hours. GEOM is even slower since it trains on full train set 200 times. All baselines except Random and Herding failed to finish within 5 hours on MAG240M.
4.3 CROSS-ARCHITECTRE GENERALIZATION
GDEM and BONSAI are both model-agnostic, meaning their condensed datasets are independent of the downstream GNN architecture used. In contrast, GCOND and GCSR produce architecture-specife condensation datasets, requiring separate training for each architecture. This distinction raises two important questions: First, how well do the condensed datasets generated by GDEM and BONSAI gen- eralize across different architectures Second, if we apply the condensation datasets produced by GCOND and GCSR for GCN to other architectures, how significantly does it impact performance? We explore these questions in Table
Consistent with the earlier trend, BONSAI continues to outperform all baselines. We further observe that the performance gap between BONSAI and the baselines is wider in GAT and GIn compared to GCN (Table 4). For GCOND and GCSR, this wider gap is not surprising since they are trained on the gradients of GCN, which are expected to differ from those of GIN and GAT. GIN uses a Sum- Pool aggregation, while GAT employs attention to effectively dampen unimportant edges, with potentially different eigen spectrum the property that GDEM attempts to preserve. The approach of BONSAL, on the other hand, aligns more directly with the computational structure of GNNS. It focuses on analyzing the input space of computation trees and aims to represent as much of this space as possible within the given budget.
8

---

Published as a conference paper at ICLR 2025
Table 5: Accuracies achieved by the various baselines on GAT and GIN.
Dataset
%
|
GNN
Random
Herding
G GCond
GDEM
GCSR
BONSAI
Full
0.5
GAT
33.80 47.44
13.21 1.00
65.91
15.00
1..42
1
GAT
42.73+1.03
46.00 16.00=0.5 s6
35, 33.2140.00
73.49+2.04
37 0..0.0..
78.67
85. 70..00000
Cora
3
GAT
60.22
56.7520.45
35. 23.24
24.28
36.72s0.81
80.6020.80
0.5
GiN
49.04
34.39 :o
14.1326.80
63.665.7.1
76.05
85.421.0.75
1
GIN
50.48
33.80+2.4 42
33. 11.91
75.92s4.34
00.70=4.44
84.80+0..
86 29
3
GIN
59.52200.8
36.35 se
31.70
59.59 7.45
51.6225.00 00
85.422.0.55
0.5
GAT
42.76:20.55
36.0440.46
21.472..00
69.861
21.92.0.0
08.56120.57
1
GAT
46.19#1.as
52.07
21.47=0.00
23.87
21 5.00000...
69.43+2.82
77. 78
CiteSeer
3
GAT
61.65+0.51
65.1740.00
21. 26
22,90
21. 21.50g0.00 0600
69. 1.111
0.5
GIn
44.86
22.97 30
21.472.0:00
67.60 as
50.66 60.66.1.11
71. 01.80
!
GiN
47.90
39.67 a0.70..5 s2
19.49
67. 67.64434.55
64.74.1.6
72. 1.:..6
75.45
3
GIN
61.832..05
60.48 as
18. 18.6522..50 50
48.65 17
59.95 or
70. 20.51
0,5
GAT
77.73+0.12
37. 47.19044.01
80,06+1..8 .16
38, 29.2
85.60+2..a
1
GAT
78.85+s0.00
76.64
41.55+a.18
80,75#0.47
40.47 40.47:0.00
85.88+00.2
86.3320.08
PubMed
3
GAT
82,8/44..11
78.18
37.77=a.61
65.08
10.27=0.20
85, 86.624n.36
0.5
GIN
77.45+20.14
48.48
30. 40.57
78.78a0.0
36.88 00
84.3240.33
!
GiN
78.4310.22
62.22.n.11
82.8426.27
78.72s0.9
33.75
80.57
84.6620.05
3
GIn
80.56
45.40 46
16:147
81.08
26.77
85, 0..
0,5
GAT
43.64
36,50+13.22 22
20.24
25, 15.43:10.57
28. 03.03a6.uu 60
48. 2.:6.0
GAT
43.56:1.06
36.34=1.14
10.85=1.00
18.4449.42
OOT
45. 45.62+1.85
51-42+0.07
Flickr
3
GAT
45.71#1887
12.70=1.17
41.51ana1
25.83+11.39
OOT
47.80+2.06
0.5
GiN
42.67:20.85
39.98
13.63
14.102s.68
05.92s1.0z
44.97+22.2
1
GiN
42.90
41.87
16.6516.35
19.4419.00
OOT
44.90100.8
45.3720:57
3
GiN
19.63
43.72:3.25
24.25
20.97
OOT
45.04
4.4 CONDENSATION EFFICIENCY
Table. 6 presents the time consumed by BONSAI and other baselines. We note that while BONSAI is CPU-bound, all other algorithms are GPU-bound. Despite being CPU-bound, BONSAI, on average, is more than 7-times faster than the fastest baseline Exgc. In addition, all baselines require training on the full dataset. This algorithm design shows up in the running times where the condensation time is higher than the full dataset training time, negating the very purpose of graph condensation. More worryingly, the condensation process of all algorithms, except BONSAI, have higher carbon emissions than training on the full dataset (See Table 8 in Appendix).
Table 6: Condensation times of various methods in seconds at 0.5%. Condensation times that higher than training on the full dataset itself are highlighted in red. The fastest condensation time for each dataset is highlighted in green.
Dataset
GCOND
GDEM
GesR
EXGC
GC-SNTK
GEOM
BONSAI
Full
Cora
2738
105
5260
34.87
82
12996
2.60
24.97
Citescer
2712
167
66336
34.51
124
15763
2.75
24.87
Pubmed
2567
530
1319
114.96
117
0OT
24.24
51.06
Flickr
1935
3405
17445
243.28
612
00T
118.23
180.08
Ogbn-arxiv
14474
569
OOT
1594.83
12218
OOT
298.64
524.67
Reddit
30112
20098
0OT
6903.47
29211
O0T
1170.64
2425.68
Component-wise analysis: We discuss the individual time consumption by each component of BON. SAI in App. B.4.1.
4.5 ABLATION STUDY AND IMPACT OF PARAMETERS
Fig. 4 presents an ablation study comparing BONSAI against three variants: (i) BONSAI-PPR, which omits the use of Personalized PageRank, (ii) BONSAI-ReY-K-NN, which substitutes the Rev-k-NN- based coverage maximization with random exemplar selection, but performs PPR, (iii) and random that does not do either PPR or Rev-k-NN. Before analyzing the trends, we emphasize an important distinction between -oNNAA--Re----- computation trees till the condensation budget is exhausted, in Random, we iteratively add random nodes, till their induced subgraph exhausts the budget. Consequently, Random covers more diverse nodes with partial local neighborhood information, while BONSAI-ReV-K-NN selects a smaller node set with complete L--hop topology, enabling precise GNN embedding computation.
and Random. While in BONsA--Re----NN, we randomly add
Several important insights emerge from this experiment. Random performs significantly worse than BONSAL, demonstrating that the condensed graph's information content substantially exceeds that of an equally sized subgraph induced by random node selection. This finding, consistent with the trend observed in Table 4, underscores the effectiveness of BONSAI over random sampling.

---

Published as a conference paper at ICLR 2025
Bureal Bornal FPR
Sonsa RAMM
tonsal
Scnnsa RAMN
Sonsal Sonsa PM
Dencel RISM Random
Random
Sonsa PPR
Randam
02
50
60
62
Accursoy
Accuracy
8
Core Chasser
rutMed
0gon
Cor3
Coosoor AJEMed
H007
9gen
A000R
PitMed Flcorr 0go7
Reddi
(a) 0.5%
(b) 1%
(c) 3%
Figure 4: Ablation study of BONSAL
Second, removal of either Rev-k-NN or PPR result in significant drops across most datasets, indi- cating both play important and complementary roles, While Rev-k-NN identifies the exemplars that are important, PPR sparsifies the graph making space for more exemplars be added. Interestingly, the relative impact of these components varies with dataset compression and size. At higher com- pression rates (such as 0.5%), removing Rev-k-NN leads to higher drop in accuracy across most datasets. However, this trend reverses as the condensed dataset size increases. Closer examination reveals that higher-ranked exemplars typically have higher degrees in their I--hop neighborhoods. When the memory budget is constrained, high-ranked exemplars are often skipped because their L-hop neighborhoods exceed the available memory. This limitation diminishes as the budget in- creases. Consequently, higher budgets, edge density increases, making graph sparsification (via PPR) increasingly critical. This explains why PPR becomes more important at higher budgets or in inherently dense graphs like Reddit.
Finally, we discuss the performance comparison of Random with BONSAI- RewsAI-ReV-K-NN. This is an interesting comparison since both represent two distinct mechanisms of random selection. In most cases, BONSAI-ReV-K-NN achieves a higher accuracy indicating that obtaining full h.-hop topological information for a smaller set of nodes leads better results than partial I--hop information over broader set of nodes.
Impact of Parameters: We analyze the impact of sampling size and l Rev-k-NN in App. B.4.2.
5 CONCLUSIONS AND FUTURE WORKS
In this work, we have developed BONSAI, novel graph condensation method that addresses criti- cal limitations in existing approaches. By leveraging the fundamental role of computation trees in message-passing GNNs, BONSAI achieves superior performance in node classification tasks across multiple real-world datasets. Our method stands out as the first linear-time, model-agnostic graph condensation algorithm, offering significant improvements in both accuracy and computational ef- ficiency. BONSAI'S unique approach of encoding exemplar trees that maximize representation of the full training set's computation trees has proven to be highly effective. This strategy not only overcomes the paradoxical requirement of training on full datasets for condensation but also elim- inates the need for repeated condensation when changing hyper-parameters or GNN architectures. Furthermore, BONSAI achieves substantial size reduction without resorting to fully-connected, edge- weighted graphs, thereby reducing computational demands. In contrast to baselines, BONSAI is com- pletely CPU-bound, resulting in at least 17-times lower carbon emissions, making more environ- mentally friendly option. These features collectively position BONSAI as a significant advancement in the field of graph condensation, offering both performance benefits and sustainability advantages.
While existing research on graph condensation has primarily fo- cused node and graph classification tasks, GNNS have demonstrated their versatility across broader spectrum of applications. In our future work, we aim to expand the scope of graph con- densation by developing task-agnostic data condensation algorithms.
Limitations and Future Works:
REPRODUCIBILITY STATEMENT
To support the reproducibility of our work, we provide several resources in the paper and its supple- mentary materials. The source code of our models and algorithms is available at https//github.com comm idea-iitd/Bonsal which also includes details of how to train the baseline models in different settings. All theoretical results and assumptions are detailed in the Appendix A, ensuring clarity in our claims. Full experimental settings documented in Appendix B.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
We acknowledge the Yardi School of AI, IIT Delhi for supporting this research. This work was partially supported by the CSE Research Acceleration Fund of IIT Delhi, Sayan Ranu acknowledges the Nick McKeown Chair position endowment. Hariprasad Kodamana acknowledges IIT Delhi Abu Dhabi for partial support of this research. Samyak Jain acknowledges the generous grant received from Microsoft Research India to sponsor his travel to ICLR 2025; and Hudson River Trading LLC for funding his work on the project.
REFERENCES
Ravinder Bhattoo, Sayan Ranu, and NM Krishnan. Learning articulated rigid body dynamics with lagrangian graph neural network. Advances in Neural Information Processing Systems, 35: 29789- 29800, 2022. (Cited on p. (-)
Suresh Bishnoi, Ravinder Bhattoo, Sayan Ranu, and NM Krishnan. Enhancing the inductive biases of graph neural ode for modeling dynamical systems. ICLR, 2023. (Cited on p. (-)
Suresh Bishnoi, Jayadeva Jayadeva, Sayan Ranu, and N M Anoop Krishnan. BroGNet: Momentum-
conserving graph neural stochastic differential equation for learning brownian dynamics. In The Twelfth International Conference Learning Representations, 2024. URL https://
openreview helffooummiddd2iiiSHHmee
(Cited on 1+)
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. The MIT Press, 3rd edition, 2009. ISBN 0262033844. (Cited on pp. 6 and 15 +)
Junfeng Fang, Xinglin Li, Yongduo Sui, Yuan Gao, Guibin Zhang, Kun Wang, Xiang Wang, and Xiangnan He. Exge: Bridging efficiency and explainability in graph condensation. In Proceed- ings of the ACM Web Conference 2024, WWW '24, pp. 721-732, New York. NY, USA, 2024. Association for Computing Machinery. ISBN 9798400701719 doi: 10. 10.1145535893343665555 URL https://doi.org/10.. 115/311933444466555555 (Cited p. 2 (-)
Uriel Feige. A threshold of In for approximating set cover. J. ACM, 45(4):633-652, 1998. (Cited on p. (
Mridul Gupta, Hariprasad Kodamana, and Sayan Ranu. FRIGATE: Frugal spatio-temporal forecast- ing on road networks. In 29th SIGKDD Conference on Knowledge Discovery and Data Mining, 2023. URL http::/ppeneeiiee..eeffoummmmmm (itioorummmiid22222224422 (Cited p. (-)
Mridul Gupta, Sahil Manchanda, Hariprasad Kodamana, and Sayan Ranu. Mirage: Model-agnostic graph distillation for graph classification. In The Twelfth International Conference on Learning Representations, 2024. URL
(Cited on p. 1 +))
William Hamilton, Rex Ying, and Jure Leskovee. Inductive representation learning on large graphs. In Proceedings of the st International Conference Neural Information Processing Systems, NIPS' 17, pp. 1025-1035, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860964 (Cited on pp. 1 and +2)
Weihua Hu, Matthias Fey, Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskovec. Ogb-lse: A large-scale challenge for machine learning on graphs. arXiv preprint arXi::2103.09430, 2021. (Cited on pp. 1 and 7 +2)
Jayant Jain, Vrittika Bagadia, Sahil Manchanda, and Sayan Ranu. Neuromlr: Robust & reliable route recommendation on road networks. Advances in Neural Information Processing Systems, 34:22070-22082. 2021. (Cited on p. (2)
Wei Jin, Lingxiao Zhao, Shichang Zhang, Yozen Liu, Jiliang Tang, and Neil Shah. Graph condensa- tion for graph neural networks. International Conference on Learning Representations, 2021. (Cited on pp. 1 and (-)

---

Published as a conference paper at ICLR 2025
Wei Jin, Xianfeng Tang, Haoming Jiang. Zheng Li, Danqing Zhang, Jiliang Tang, and Bing Yin. Condensing graphs via one-step gradient matching. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 720-730, 2022. (Cited on p. 1 (-)
Thomas Kipf and Max Welling. Semi-supervised clasifiiittinn with graph convolutional networks.
ICLR, 2017. (Cited on pp. 1, 2, and 7 (-)
Alexandre Lacoste, Alexandra Luccioni, Victor Schmidt, and Thomas Dandres. Quantifying the carbon emissions of machine learning, arXiv preprint arXiv: 2019. (Cited on p. 19
Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, and Natalie Glance. Cost-effective outbreak detection in networks. In Proceedings of the 13th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pp. 429, 2007. (Cited on P. ))
Yang Liu, Deyu Bo, and Chuan Shi. Graph distillation with eigenbasis matching. In Forty-first International Conference on Machine Learning, 2024a. URL, httpss//ooenrevieennefffooo net/forumm?id DYN66UCI9. (Cited on pp. and 2 ())
Zhanyu Liu, Chaoly Zeng, and Guanjie Zheng. Graph data condensation via self- graph structure reconstruction. In Proceedings of the 30th ACM SIGKDI) Conference Knowledge Discovery and Data Mining, KDD '24, pp. 1992-2002 2024b. (Cited on pp. and (-)
Peter A. Lofgren, Siddhartha Banerjee. Ashish Goel, and C. Seshadhri. Fast-ppr: scaling personal- ized pagerank estimation for large graphs. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '14, pp- 1445, 2014. (Cited on p. 17+1) +))
WeiWei Miao, Zeng Zeng, Mingxuan Zhang, Siping Quan, Zhen Zhang, Shihao Li, Li Zhang, and Qi Sun. Workload prediction edge computing based on graph neural network. 2021 IEEE Intl Conf on Parallel & Distributed Processing with Applications, Big Data & Cloud Com- puting, Sustainable Computing & Communications, Social Computing & Networking (ISPA/BD- Cloud/Social CowtaaCoainoooononnaaaaa pp. 1663-1666, 2021. doi: 10.1 10.1000/SPABBDDlooSSSeollll SustainCom52081 .2021.00225, .00223. (Cited on p. 1
Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, 1995. (Cited on p. 14 +))
Sunil Nishad, Shubhangi Agarwal, Arnab Bhattacharya, and Sayan Ranu. Graphreach: Position- aware graph neural network using reachability estimations. IJCAI, 2021. (Cited on p. 1 1+)
Lawrence Page. Sergey Brin, Rajeev Motwani, and Terry Winograd. The PageRank Citation Rank- ing: Bringing Order the Web. Technical report, 1998. (Cited on p. 16 (2)
Abishek Thangamuthu, Gunjan Kumar, Suresh Bishnoi, Ravinder Bhattoo, NM Krishnan, and Sayan Ranu. Unravelling the performance of physics-informet graph neural networks for dynamical systems. In Advances in Neural Information Processing Systems, 2022. (Cited on p. 1 (2)
Matteo Togninalli, Elisabetta Ghisu, Felipe Llinares-López, Bastian Rieck, and Karsten Borgwardt. Wasserstein teasffileer-ehmaar graph kernels. In Advances in Neural Information Processing Sys- lems 32 (NeurIPS), pp. 6436-6446. 2019. (Cited on pp. 2 and 4 (2)
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference Learning Representations, 2018. URL https///pperreview deetforummmidddJXMPpp
(Cited on pp. and 2 +)
Lin Wang, Wenqi Fan, Jiatong Li, Yao Ma. and Qing Li. Fast graph condensation with structure-based neural tangent kernel. In Proceedings of the ACM Web Conference 2024, WWW '24, pp. 4439 4448, New York, NY, USA. 2024. Association for Computing Machin- ery. ISBN 9798400001719. doi: 10.1145525993343345544, URL htpps///doi.or/110. 145/
3589334.3645694. (Cited p. 2 (r)
12

---

Published as a conference paper at ICLR 2025
Max Welling, Herding dynamical weights learn. In Proceedings of the 26th Annual International Conference on Machine Learning. pp. 1121-1128, 2009. (Cited on p. 8 (-)
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neu- ral networks? In International Conference on Learning Representations, 2019. URL https: //openreview.netee mel/foonm"id---yGGiiAASSK (Cited on pp. and 3 (-)
Zhe Xu, Yuzhong Chen, Menghai Pan, Huiyuan Chen, Mahashweta Das, Hao Yang, and Hang- hang Tong. Kernel ridge regression-basee based graph dataset distillation. In Proceedings of the 29th ACM SIGKDD Conference Knowledge Discovery and Data Mining, KDD '23, pp. 2850-2861, New York, NY, USA, 2023, Association for Computing Machinery, ISBN 9798400701030, doi: 10.1 35555/99 URL https://doi..nw wtg/ 10. 111114553500533555 35993388 (Cited p. (+)
Beining Yang, Kai Wang. Qingyun Sun, Cheng Ji, Xingcheng Fu, Hao Tang, Yang You, and Jianxin Li. Does graph distillation see like vision dataset counterpart? In Thirty-seventh Confer- ence on Neural Information Processing Systems, 2023. URL https://openreview htt.://erreeieeeete//uuu????? net/forum?id-
VqIWgUVsXe.. (Cited on pp. and 8 (-)
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- SAINT: Graph sampling based inductive learning method. International Conference on Learn- ing Representations, 2020. URL
(Cited on
Yuchen Zhang, Tianle Zhang, Kai Wang. Ziyao Guo, Yuxuan Liang, Xavier Bresson, Wei Jin, and Yang You. Navigating complexity: Toward lossless graph condensation via expanding window matching. In Forty-first International Conference on Machine Learning, 2024. URL https://openrevieew.. wet/fooummm/u--gEE2A.2..... (Cited on p. 2
Xin Zheng, Miao Zhang, Chunyang Chen, Quoc Viet Hung Nguyen, Xingquan Zhu, and Shirui Pan. Structure-free graph condensation: From large-scale graphs to condensed graph-free data. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL https: //openreview.
(Cited on pp. 1, 2, and 8 (-)
13

---

Published as a conference paper at ICLR 2025
A APPENDIX
A.1 PROOF OF THEOREM
Recall the notation that & C T denotes the subset of trees from which the representative power of all trees in T is being estimated. Let
Corresponding to each T. E S, let us define an indicator random variable X denoting whether The E k-NN(TT"). Therefore, have:
X" = Σ
X = 211 (T
(8)
ETL
Since each tree in S is sampled uniformly at random from T, have E(X") 2II (T."). We also note that X" Binomial (T,")). Given any 2 from Chernoff bounds (Motwani & Raghavan, 1995), we have:
Upper tail bound:
- (-
(T+))) ((x"2(++))2 (T+))))(TT)) exp
=ll (T!²) 22c
(9)
Lower tail bound:
2 (- (T
P(X S (1- (T!t)
$ exx
(10)
Combining the upper and tail bounds, we obtain:
2
P 2II (T:)) 2 cell (T!))
2eep
2Il (T!)
(11)
2
2
+ P - =Il - (T.) + 2exp
=ll (T!²)
(12)
2 +
2
+ (77)
$ 2exp
21I (T!!)
(13)
2 +
Plugging from Eq. 5 in Eq. 13, we obtain 0 = ell (T.!). Hence,
P ( 11 (T+ 20) 2exp
a11 (Tel)
(14)
2 IT(T))
0
2exp
(15)
21I (T. !.) +
For any T T, II (T.²) Thus,
82
P ( TT (T:²) 2 20) < 2exp
(16)
2+0
14

---

Published as a conference paper at ICLR 2025
Now, if we want confidence interval of 1 (as stated in Eq. 5), have:
0
2 2xxp
2
(17)
2 + 0
8²
2 exp
(18)
2
2 2+0 0
6
0
In
2
(19)
2
2 2+0 0
2
8
In
3
(20)
2 2+
2
8
+ In
(21)
2 0
(2+ In
+
(22)
0
Hence, if we sample at least (2++0) 6²
trees in S, then for any T E T::
T (u 01 (Tx²) + 0] with probability at least 8.
(23)
A.2 NP-HARDNESS; PROOF THEOREM 1
PROoF. To establish NP-hardness of our proposed problem we reduce it to the classical Set Cover problem (Cormen al., 2009).
Definition 7 (Set Cover). Given budget b and collection of subsets S = {Si..... Sm from a universe of items determine whether there exists subset S' C S such that | b and covers all items in the universe, ie., UUs.es Sil =
{u,,- Un iee, VS; S, S; C U, the Set Cover problem seeks to
We show that given any instance of a Set Cover problem (S,0), 6, it can be mapped to the problem of maximizing the representative power (Eq. 7).
Given an instance of the Set Cover problem, we construct a database of computation trees T = we add a computation tree Ta, E Ty. For each S. S, we add a tree
To Ts. For each uy Ts. E Ts. an item uj E S,, then we have Tu, E Rev-k-NN(Ts.) (equivalently Ts, E k-NN(TT,)) ))-
With this construction, can state that there exists Set Cover size b and only if there exists solution set & C such that II(A)
[T
[
A.3 PRooFs MONOTONICITY, SURMODULARITY
Theorem (Monotonicity). VA'S C A, IIAA) - -I(()) 2 0, where & and A!' are sets of computation trees.
Proof. Since the denominator in II(A) is constant, it suffices to prove that the numerator is mono- tonic. This reduces to establishing that:
U YT!EAA
Rev-K-NN (T!H)
>
U
Rev-k-NN (T!
(24)
YT,EEA
This inequality holds true because the union operation a monotonic function. As A' a superset of A, the union over A' will always include at least as many elements the union over A.
Theorem (Submodularity). AA' 2 A, I[AA' U (T)) I[AA) < I[A U (T)) I(A),, where A
and A' are sets of computation trees and T is computation tree.
PROOF BY CONTRADICTION. Let us assume
AYE 2 A, IT U (TH) ITAA) IT(A U (T)) IT(A)
(25)
15

---

Published as a conference paper at ICLR 2025
10-2
Cora
Citeseer
Pubmed
PPR Score
10-3
Flickr
AaPand orth
10-4
10-5
0.0
0.5
1.0
Ranked order based on PPR score
Figure Distribution of PPR scores against node ranks.
Eq. 25 implies:
Rev-k-NN(T) U ET'EA'
Rev-k-NN (T) Rev-k-NN(T) \ U
Rev-k-NN (T)
(26)
YT'EA
A 2 A', which contradiction.
A.4 SPARSIFICATION THROUGH PERSONALIZED PAGERANK (PPR)
Let Vss be the node set in the initial condensed graph, which can be partitioned into two disjoint subsets: Vroot and V Vego. where Vroot = {v S7. E }. the root nodes, that serve as the root node of some exemplar in grreedy: and Vego Vs Vroat; the ego nodes, that are included because they fall within the L-hop neighborhood of root node. We propose to employ Personalized PageRank (PPR) (Page al., 1998) with teleportation only to root nodes identify and prune ego nodes with minimal impact on the root node embeddings. Starting with timestamp t O, we proceed as follows:
Compute the PPR distribution n, for 2 0 defined by:
π (1 8) A) + Be
(27)
where: To[o] |vs for all e|i] |Vooo if Vroot, otherwise 0, A is the normalized
adjacency matrix, |3 is the teleportation probability.
2. Obtain the PPR vector π after convergence where π, πt-1.
Sort the nodes in æ by their PPR scores in descending order such that Vi, π 1] 2 π x
4. Define the knee point innce as:
Ance = arg max T + 1] M|i 1] 2 -- [[]}}
(28)
Prune all ego nodes with PPR scores below π [isnee]
6. Use the freed-up up space to include additional exemplar trees using Algorithm 1.
Repeat steps 1-6 iteratively until iknce 2 0, where is a threshold setting the minimum number of nodes to be removed.
The rationale for this pruning process can be outlined follows. The PPR distribution π. iteratively updates based on the transition matrix A and teleportation vector e. Given that To is initialized root nodes, π. converges
uniformly and e assigns higher probabilities nodes more connected to root nodes have higher scores (See Fig. 5 in Appendix). After convergence, the vector я represents the steady-state probabilities of nodes in the graph. Sorting л by descending scores ensures that nodes with the highest influence root nodes are prioritized. The knee point iknee is identified as the maximum curvature the sorted PPR scores. This point is where the rate of change in scores shifts most significantly, indicating transition between nodes of high and low influence. Nodes with PPR scores below π [iknnel have minimal impact on root node embeddings and removing these nodes and edges incident them effectively sparsifies the graph without substantial loss of information. Additional exemplar trees can then be incorporated into the available space using the greedy algorithm given by Algorithm 1.
distribution where
16

---

Published as a conference paper at ICLR 2025
A.5 COMPLEXITY ANALYSIS
For this analysis, we assume |V] and - m. In syne with Fig. 3, the computation structure of BONSAI can be decomposed into four components.
1. Embed trees into WL-space: This operation requires pass through each twice, and is identical the message-pass structure of a GNN. Hence, the computation cost is bounded (m)). A crucial distinction from GNN is that it does not require pack-propagation and hence is fully CPU-bound.
2. Rev-k-NN: As discussed in $ 3.1.1, computing Rev-k-NN consumes ((n) time with sampling. Coverage Maximization: Each iteration in Alg. 1, iterates over nodes (trees) in the graph (T) that have not yet been added to the set of exemplars. For each node (equivalently, tree rooted at this node), we compute its marginal gain (line in Alg. 1). which is bounded by the sample size since the cardinality of Rev-k-NN set is bounded by the number of trees sampled for Rev-k- NN computation ((S 3.1.1)). Since 2 < n, the complexity per iteration is (22)) R O(n). The number of iterations is bounded by the size of the condensation budget, which we typically set to less than 3% of the full dataset and hence has negligible impact on the complexity.
PPR: PPR can be computed in linear time (Lofgren al., 2014). Since the size of the condensed set is at most the full graph, this bounds the cost of PPT to (n))
Combining all these components, the of BONSAI bounded by O + m.)
B EXPERIMENTAL SETUP
Across all datasets, except MAG240M, we maintain sein-validation-teee split ratio of 60 20 20. In MAG240M, use ratio of 80: 10:10.
B.1 HARDWARE CONFIGURATION
All experiments were conducted on high-performance computing system with the following spec- ifications:
CPU: 96 logical cores
RAM: 512
GPU: NVIDIA A100-PCIE-40GB
B.2
SOFTWARE CONFIGURATION
The software environment for our experiments was configured as follows:
Operating System: Linux (Ubuntu 20.04.4 L:TS (GNU/Linux 5.4.0-124 -eee-ri x86_64))
PyTorch Version: 1.13.1
CUDA Version: 11.7
PyTorch Geometric Version: 2.3.1
B.3 ADDITIONAL EXPERIMENTAL PARAMETERS
Number of layers in evaluation models: 2 (with RELU in between) for GCN, GAT, and GIN. The MLP used GIN a simple linear transform with bias defined by the following equation WX + where X is the input design matrix.
Value of & in Rev-k-NN:
parameess Baselines: We use the config files shared by the authors. We note that the benchmark datasets are common between our experiments and those used in the baselines.
B.4 ADDITIONAL EXPERIMENTS
B.4.1 RUNNING TIME ANALYSIS OF BONSAI
Fig. 7 presents the time consumed by the various components within BONSAL. We observe that most of the time is spent in PPR computation, except Reddit, where Rev-k-NN is dominant contributor.
17

---

Published as a conference paper at ICLR 2025
Table 7: Component-wise analysis of BONSAI's running times in seconds.
Datasct
WL
Rev-k-NN
Greedy
PPR
Full
Cora
0.87
0.05
0.005
1.68
2.60
Citescer
0.97
0.07
0.005
1.71
2.75
Pubmed
8.89
1.39
0.030
13.93
24.24
Reddit 682.80
293.15
0.696
193.99
1170.64
This trend can be explained by the high density of Reddit, where the average degree 100 contrast to < 5 in the other networks.
Flickr
Ogbn-ansiv
Reddit
10a
60
100
Time 14)
Accuracy
400
60
101
40
20
25
100
Sampling Parcentage
Sampling Percentage
k in RKNN
(a) Impact of sampling size on(b) Impact of sampling size on Accuracy
(c) Effeect of varying k in the Rev-k-NN in BoNSAL.
time
Figure 6: Impact of k in Rev-k-NN and sampling size for Rev-k-NN approximation on the perfor- mance of BONSAL.
B.4.2 IMPACT OF PARAMETERS ON BONSAI
BONSAI has two parameters, both related to the computation of Rev-k-NN. The value of Rev-k- NN and the sample size to accurately approximate the representative power.
Fig. 6a and Fig. 6b present the impact of sample size on accuracy and time, respectively. As expected, the general trend shows that increasing the sample size leads higher accuracy and longer running times. However, we note that the increase in accuracy is minor. This observation is consistent with Lemma 1, which states that a small sample size sufficient to achieve a high-quality approximation.
Fig. 6c presents the impact of & on accuracy. While the performance is generally stable against k the peak accuracy typically achieved when & 5.
B.5 ADDITIONAL TRAINING TIMES
Fig. 7 presents the training times condensed datasets in Cora, Citeseer, Pubmed, and Reddit 0.5% size. Figs. and 9 presents the training times on condensed datasets Cora, Citeseer, Pubmed, Flickr, Ogbn-arxiv, and Reddit 1%, and 3% sizes. BONSAI is faster all architectures. The gap between BONSAI and the baselines increase with increase condensed dataset size. This is more pronounced in larger datasets like Flickr, Ogbn-arxiv, and Reddit because the number of edges is (((V22) for the baselines and forward pass through GNNS is usually O(EE)) Additionally, the condensed dataset created by GCOND and GDEM for Reddit at 3% size cannot be used to train basic Py Torch Geometric models for GAT and GIN, resulting in out-of of-mmmory (OOM) errors because the backward pass graph maintained by PyTorch is larger.
B.6 CARBON EMISIIONS
18

---

Published as a conference paper at ICLR 2025
GCond GDEM
Bonsai
GCSR
GCond
Bonsai
GCSR
GDEM
10.0
10.0
Training Time (s)
Training Time (s)
7.5
7.5
5.0
2.5
2.5
0.0
0.0
GCN
GAT
GIN
GIN
(a) Cora
(b) Citeseer
GCand GDEM
Bonsai
GCSR
GCond
GDEM
Bonsai
10.0
Training Time (s)
Training Time (s)
7.5
40
5.0
20
2.5
0.0
GCN
GAT
GIN
GAT
GIN
(c) Pubmed
(d) Reddit
Figure 7: Comparing time required to train models on datasets condensed by GCOND, GDEM, BoN- SAL, and GCSR at 0.5% of Cora, Citeseer, Pubmed, and Reddit. Note that there is no condensed dataset for Reddit output by GCSR due to OOT.
Table 8: Estimated CO2 emissions from condensation of various methods in seconds 0.5%. Emis- sions that are higher than training on the full dataset itself are highlighted red. The least emission from condensation for each dataset is highlighted in green. CO2 emissions computed 10.8kg per 100 hours for Nvidia A 100 GPU and 4.32kg per 100 hours for 10 CPUs of Intel Xeon Gold 6248 (Lacoste al., 2019).
Dataset
GCOND
GDEM
GCSR
ExgC
GC-SNTK
GEOM
BONSAI
Full
Cora
82.14
3.15
157.80
1.05
2.46
389.88
0.03
0.75
Citeseer
81.36
5.01
199.08
1.03
3.72
472.89
0.03
0.75
Pubmed
77.01
15.90
39.57
3.45
3.51
2540.00
0.3
1.53
Flickr
58.05
102.15
523.35
7.30
18.36
2540.00
1.42
5,40
Ogbn-arxiv
434.22
17.07
2540.00
46.49
366.54
2540.00
4.18
15.74
Reddit
903.36
602.94
2540.00
207.10
876.33
2540.00
17.34
72.77
19

---

Published as a conference paper at ICLR 2025
GCond
Bonsai
GCSR
GCond
Bonsai
GCSR
GDEM
GDEM
10.0
10.0
Training Time (5)
Training Time (s)
7.5
7.5
5.0
2.5
2.5
0.0
0.0
GCN
GAT
GIN
GCN
GAT
GIN
(a) Cora
(b) Citeseer
GCond
Bonsai
GCSR
GCond
GDEM
Bonsai
GDEM
10.0
15
Training Time (8)
7.5
Training Time
10
+0C+
2.5
0.0
GCN
GAT
GCN
GAT
GIN
(c) Pubmed
(d) Flickr
GCond
GDEM
Bonsai
GCond
GDEM
Bonsai
Training Time (s)
150
20
100
Training
10
50
GCN
GIN
GCN
GAT
GIN
(c) Ogbn-arxiv
(f) Reddit
Figure 8: Comparing time required to train models on datasets condensed by GCOND, GDEM, BoN- SAI, and GCSR at 1% of Cora, Citeseer, Pubmed, Flickr, Ogbn-arxiv, and Reddit. Note that there is no condensed dataset for Flickr, Ogbn-arxiv, Reddit output by GCsR due to OOT.
20

---

Published as a conference paper at ICLR 2025
GCond
Bonsai
GCSR
GCond
Bonsai
GCSR
GDEM
GDEM
10.0
Training Time (s)
8
7.5
Training Time
4
2.5
2
0.0
GCN
GAT
0
GCN
GAT
GIN
(a) Cora
(b) Citeseer
GCond
Bonsai
GCSR
GCond
GDEM
Bonsai
GDEM
Training Time (s)
8
Training Time (s)
60
40
20
GCN
GAT
GIN
GCN
GAT
GIN
(c) Pubmed
(d) Flickr
GCond
GDEM
Bonsai
GCond
GDEM
Bonsai
Training Time (s)
Training Time (s)
300
75
200
50
25
100
0
GCN
GAT
GIN
GCN
GAT
GIN
(e) Ogbn-arxiv
Reddit
Figure 9; Comparing time required to train models datasets condensed by GCOND, GDEM, BoN- SAL, and GCSR at 3% Cora, Citeseer, Pubmed, Flickr, Ogbn-arxiv, and Reddit. Note that there no condensed dataset for Flickr, Ogbn-arxiv, Reddit output by GCSR due to OOT; and condensed datasets produced by GCOND and GDEM for Reddit cannot train on standard 2-layered PyTorch Ge- ometric GAT and GIN due to OOM.
21


Reviews:
[{"review_id": "wCiwRPuAvh", "reviewer": "Reviewer_YqxY", "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.", "questions": "See weakness", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. Compared to previous works, BONSAI is novel.\n2. The experimental results look very good, especially regarding the training time.\n3. The theoretical analysis is solid.", "weaknesses": "1. This paper is not easy to understand.\n2. In some cases, BONSAI does not perform the best, such as with citeseer.\n3. Regarding table 5, can you provide experimental results for other compression rates?\n4. PPR and RkNN involve many parameters, and the ablation study in Fig. 4(b) is insufficient.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4QVUQhQeO0", "reviewer": "Reviewer_t6gR", "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.", "questions": "Please see the weaknesses", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "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.\n2. This model-agnostic method is interesting and saves efforts in hyperparameter tuning when changing condensation models.\n3. 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.\n2. 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].\n3. 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.\n4. 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?\n5. In line 235, **Diversity** is highlighted. Which part of the method addresses this concern?\n6. To select the trees with top representativeness, why do the authors choose Reverse K-NN? Would it be possible to simply adopt clustering instead?\n7. 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.\n\n\n### Minor\n1. The details of PPR starting from line 332 could be simplified or moved to the Appendix as people are familiar with it.\n2. Why is Herding OOT (out of time) for Reddit? In my understanding, this method should be efficient.\n\n### References\n[1] Mridul Gupta, Sahil Manchanda, HARIPRASAD KODAMANA, and Sayan Ranu. Mirage: Model-\nagnostic graph distillation for graph classification. In ICLR 2024\n\n[2] Wei Jin, Lingxiao Zhao, Shichang Zhang, Yozen Liu, Jiliang Tang, and Neil Shah. Graph condensa-\ntion for graph neural networks. In ICLR, 2021.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ThAFMpMz3B", "reviewer": "Reviewer_n8k1", "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.", "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.\n2. 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.\n3. 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?\n\n[A] Mridul Gupta, Sahil Manchanda, HARIPRASAD KODAMANA, and Sayan Ranu. Mirage: Model\u0002\nagnostic graph distillation for graph classification. ICLR 2024.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The performance of bonsai is impressive, including the cross-arch results.\n2. The proof of maximizing the representative power of exemplars is NP-hard is simple but attracting.", "weaknesses": "See questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "31YGpHmoL4", "reviewer": "Reviewer_q9ty", "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.", "questions": "Q1: Why the authors choose 0.5%, 1% and 3% as $S_r$? This setting does not align with previous works.\n\nQ2: 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.\n\nQ3: Other graph condensation methods should be included for accuracy comparison, e.g., SGDD [3], SFGC [4], GEOM [5].\n\n[1] Exgc: Bridging efficiency and explainability in graph condensation\n\n[2] Fast Graph Condensation with Structure-based Neural Tangent\n\n[3] Does graph distillation see like vision dataset counterpart\n\n[4] Structure-free graph condensation: From large-scale graphs to condensed graph-free data\n\n[5] Navigating Complexity: Toward Lossless Graph Condensation via Expanding Window Matching", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "S1: The problem is important in this field.\n\nS2: Presentation is good. Good model name.\n\nS3: The solution looks novel to me.", "weaknesses": "W1: The experiments are not very standard. \n\nW2: Some recent works are not included as baseline.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)