Mirage: Model-agnostic Graph Distillation for Graph Classification
Authors: Mridul Gupta
Sahil Manchanda
HARIPRASAD KODAMANA
Sayan Ranu
Venue: ICLR 2024 poster (2024)
Keywords: graph distillation
graph classification
frequent pattern mining
Primary area: learning on graphs and other geometries & topologies
TL;DR: An unsupervised and model/hyper-parameter agnostic graph distillation algorithm for graph classification.

Abstract: GNNs, like other deep learning models, are data and computation hungry. There is a pressing need to scale training of GNNs on large datasets to enable their usage on low-resource environments. Graph distillation is an effort in that direction with the aim to construct a smaller synthetic training set from the original training data without significantly compromising model performance. While initial efforts are promising, this work is motivated by two key observations: (1) Existing graph distillation algorithms themselves rely on training with the full dataset, which undermines the very premise of graph distillation. (2) The distillation process is specific to the target GNN architecture and hyper-parameters and thus not robust to changes in the modeling pipeline. We circumvent these limitations by designing a distillation algorithm called MIRAGE for graph classification. MIRAGE is built on the insight that a message-passing GNN decomposes the input graph into a multiset of computation trees. Furthermore, the frequency distribution of computation trees is often skewed in nature, enabling us to condense this data into a concise distilled summary. By compressing the computation data itself, as opposed to emulating gradient flows on the original training set—a prevalent approach to date—MIRAGE transforms into an unsupervised and architecture-agnostic distillation algorithm. Extensive benchmarking on real-world datasets underscores MIRAGE’s superiority, showcasing enhanced generalization accuracy, data compression, and distillation efficiency when compared to state-of-the-art baselines.

Published as a conference paper at ICLR 2024
MIRAGE: MODEL-AGNOSTIC GRAPH DISTILLATION FOR GRAPH CLASSIFICATION
Mridul Gupta'
Sahil Manchanda"
Yardi School of Artificial Intelligence Indian Institute of Technology, Delhi
Department of Computer Science Indian Institute of Technology, Delhi Hauz Khas, New Delhi, Delhi, India
Hauz Khas, New Delhi, Delhi, India mridul. gupt aepptascca iitd.ac.ii.
sahi 1m1 992 02mmmmmmmmmmmm com
Hariprasad Kodamana
Sayan Ranu
Department of Chemical Engineering Yardi School of Artificial Intelligence Indian Institute of Technology, Delhi Hauz Khas, New Delhi, Delhi, India kodamana@ ait.dac.......
Department of Computer Science Yardi School of Artificial Intelligence Indian Institute of Technology, Delhi Hauz Khas, New Delhi, Delhi, India sayanranu@cse, iitrsse.iiiiii aitddaa.c..
ABSTRACT
GNNS, like other deep learning models, are data and computation hungry. There is pressing need to scale training of GNNs on large datasets to enable their usage on low-resource environments. Graph distillation
an effort in that direction with the aim to construct smaller synthetic training set from the original training data without significantly compromising model performance. While initial efforts are promising. this work is motivated by two key observations: (1) Existing graph distillation algorithms themselves rely on training with the full dataset, which undermines the very premise of graph distillation. (2) The distillation process is specific to the target GNN architecture and Syyper-parametes and thus not robust to changes in the modeling pipeline. We circumvent these limitations by designing a distillation algorithm called MIRAGE for graph classification. MIRAGE is built on the insight that a pessage-passiiggg GNN decomposes the input graph into multi- set of computation trees. Furthermore, the frequency distribution of computation trees is often skewed in nature, enabling us to condense this data into concise distilled summary. By compressing the computation data itself, as opposed to emulating gradient flows on the original training set-a prevalent approach to date-MIRAGE transforms into architecture-agnosiic distillation algorithm. Extensive benchmarking on real-world datasets underscores MIRAGE'S supe- riority, showcasing enhanced generalization accuracy, data compression, and distillation efficiency when compared to state-of-the-an baselines.
INTRODUCTION AND RELATED WORK
GNNS have shown oftte- performance in various machine learning tasks, including node classification (Hamilton et al., 2017: Veličković et al., 2018), graph classification (Ying al., 2021; Rampášek et al., 2022), and graph generative modeling (Vignac et al., 2023; You et al., 2018; Goyal al., 2020; Gupta et al., 2022; Manchanda al., 2023). Their applications percolate various do- mains including social networks (Manchanda et al., 2020; Chakraborty et al., 2023; Wang et al., 2021; Yang et al., 2011), traffic forecasting (Gupta et al., 2023; Jain et al., 2021; Li et al., 2020; Wu et al., 2017), modeling of physical systems (Bishnoi et al., 2023; Bhattoo et al., 2022: Sanchez- Gonzalez et al., 2020) and several others. Despite the efficacy of GNNS, like many other deep- learning models, GNNS are data, as well as, computation hungry. One important area of study that tackles this problem is the idea of data distillation (or condensation) for graphs. Data distillation seeks to compress the vital information within a graph dataset while preserving its critical structural and functional properties. The objective in the distillation process is to compress the train data as much as possible without compromising the predictive accuracy of the GNN when trained on the distilled data. The distilled data therefore significantly alleviates computational and storage
Denotes Equal Contribution

---

Published as a conference paper at ICLR 2024
demands, due to which GNNS may be trained more efficiently including on devices with limited resources, like small chips. It is important to note that the distilled dataset need not be a subset of the original data; it may be fully synthetic dataset.
1.1 EXISTING WORKS
Data distillation has proven to be an effective strategy for alleviating the computational demands imposed by deep learning models. For instance, in the case of Dc (Zhao et al.. 2021), dataset of R 60, 000 images was distilled down to just 100 images, resulting in an impressive accuracy of 97.4%, compared to the original accuracy of 99.6%.
Graph distillation has also been explored in prior research (Jin et al., 2022; 2021; Xu et al., 2023). These graph distillation algorithms share common approach, where the distilled dataset seeks to replicate the same gradient trajectory of the model parameters as seen in the original training set. In this work, we observe that the process of mimicking gradients necessitates supervision from the original training set, giving rise to significant limitations.
Counter-objective design: The primary goal in data distillation is to circumvent the need for training on the entire training dataset, given the evident computational and storage constraints. Paradoxically, existing algorithms aim to replicate the gradient trajectory of the original dataset, necessitating training on the full dataset for distillation. Consequently, the fundamental premise of data distillation is compromised.
2. Dependency on Model and Hyper-Pase pper-Parameters: The gradients of model weights are contingent on various factors such as the specific GNN architecture and number of layers, hidden dimensions, dropout rates, and more. As result, any alteration in the architecture, such as transitioning from a Graph Convolutional Network (GCN) to a Graph Attention Network (GAT), or adjustments distillation. It has been shown in the literature (Yang et al., 2023), and also substantiated in our empirical study (Appendix C), that there is a noticeable drop in performance if the GNN architecture used for distillation is different from the one used for eventual training and inference. Storage Overhead: Given the dependence of the distillation process on both the GNN architecture and hyper-parametend unique combination of architecture and hyper-parameters. This inevitably amplifies the storage requirements and maintenance overhead.
including the
hyper-parameters, necessitates a fresh round of
a distinct distilled dataset must be maintained for each
1.2 CONTRIBUTIONS
To address the above outlined limitations of existing algorithms, we design a graph distillation al- gorithm called MIRAGE for graph classification. MIRAGE proposes several innovative strategies imparting significant advantages over existing graph distillation methods.
Model-agnostic algorithm: Instead of replicating the gradient trajectory, MIRAGE emulates the input data processed by message-passing G By shifting the computation task to the pre-leamnig phase, MIRAGE and the resulting distilled data become independent of hyper- parameters and model architecture (as long as it adheres to message-passing GNN framework like GAT (Veličković al., 2018). GCN (Kipf & Welling, 2016), GRAPHSAGE (Hamilton al., 2017), GIN (Xu et al., 2019), etc.). Moreover, this addresses a critical limitation of existing graph distillation algorithms that necessitate training on the entire dataset.
Novel GxN-customized algorithm: MIRAGE exploits the insight that given graph, an é-layered sessaag-passsig GNNS decomposes the graph into a set of computation trees of depth f. Fur- thermore, the frequency distribution of computation trees often follows power-law distribution (See. Fig. 2). MIRAGE exploits this pattern by mining the set frequently co-occurring trees. Subsequently, the GNN is trained by sampling from the co-occurring trees. An additional benefit of this straightforward distillation process is its computational efficiency, as the entire algorithm be executed on CPU. This stands in contrast to existing graph distillation algorithms that rely on GPUs, making MIRAGE a more resource and environment friendly alternative.
Empirical performance: We perform extensive henchmarking of MIRAGE against state-of- the-art graph distillation algorithms on six real world-graph datasets and establish that MIRAGE achieves (1) higher prediction accuracy on average, (2) 5 times higher data compression, and (3) significant 150-fold acceleration in the distillation process when compared to state-of-the-a graph distillation algorithms.
Hence, the name MIRAGE.
2

---

Published as a conference paper at ICLR 2024
Frequent
Htmmeet Mining
GNN
Frequenty Co-ocourring Trees
Graph Database
Computation Trees
Trained Model
Figure I: Pipeline of MIRAGE.
PRELIMINARIES AND PROBLEM FORMULATION
Definition (Graph). A graph is defined as G = =V,,,, over finite non-emply node set V and edge set and & = {(u,,) v) | u,v v E V}. X RIVXXIF is node feature matrix where F is set of features characterizing each node.
As example, in case of molecules, nodes and edges would correspond to atoms and bonds, spectively, while features would correspond to properties such as atom type, hybridisation state, etc.
Equivalence between graphs is captured through graph isomorphism.
Definition 2 (Graph Isomorphism). Two graphs 91 and G2 are considered isomorphic (denoted as 91 G2) if there exists a bijection between their node sets that preserves the edges and node features. Specifically, G1 = G2 X((r), 2 and (3) (u,w) E & if and only if (fu), E
Ef Vi + V22 such that: (1) f is bijection, (2) Xx
Graph Classification: In graph classification, we are given set of train graphs Dtr (91,... G. where each graph G. is tagged with class label V. The objective is to train GNN Pe,, parameterized by Oer from this train set such that given an unseen set of validation graphs Deal with unknown labels, the label prediction error is minimized. Mathematically, this involves learning the optimal parameter set Orr, where:
ir = arg minn {e (( (9) VA Doath))
Here, &e.. (G) denotes the predicted label of G by GNN & and (f (G) VG D denotes the error with parameter set O Error may be measured using any of the known metrics such cross-entropy loss, negative log-likelihood, etc.
Hereon, we implicitly assume & to be a message-passing GNN (Kipf & Welling, 2016; Hamilton al., 2017; Veličković al., 2018; Xu al., 2019). Furthermore, assume the validation to be fixed. Hence, the generalization error of GNN & when trained on dataset D,, is simply denoted using ED.. The problem graph distillation for graph classification now defined as follows.
Problem 1 (Graph Distillation). Given training set and validation set of graphs, DEy and Deab respectively, generate a dataset S from Der with the following dual objectives:
Error: Minimize the error gap between and Der on the validation set, i.e., mini-
mize [les-(D,)
Compression: Minimize the size of S. Size will be measured terms of raw memory consump- tion, i.e., in bytes.
In addition to the above objectives, we impose two practical constraints on the distillation algorithm. First, it should not rely on the specific GNN architecture, except for the assumption that belongs to the message- message-passing family. Second, it should be independent of the model parameters when trained on the original training set. Adhering to these constraints addresses the limitations outlined in $ 1.1.
MIRAGE: PROPOSED METHODOLOGG
MIRAGE exploits the computation framework of message-passing GNNS to craft effective data compression strategy. Fig. presents the pipeline of MIRAGE. GNNs decompose any graph into collection of computation trees. In Fig. 2, plot the frequency distribution of computation trees across various graph datasets. We observe that the frequency distribution follows a power-law. This distribution indicates that compact of top-k frequent trees effectively captures substantial portion of the distribution mass while retaining a wealth of information content. Empowered with this observation, in MIRAGE, the GNN is trained only through the frequent tree sets. We next elaborate on each of these intermediate steps.
One may relax feature equivalence having distance within certain threshold.
3

---

Published as a conference paper at ICLR 2024
Up
Fo: Ma, Mp
20, M1, M2
14
ED; 12, M0
87 2/2
M5
Ei, M2, 81
P0; M2, 12
Computational tree do
Paths from dg
11
(a) Construction of computation tree for E Gi (O) for L 2 hops.
(b) G2.
Figure 3: In (a) we show the construction of the computation tree for un 91. In (b), we present G2. which has an isomorphic 2-hop computational tree for u2 despite its neighborhood being non- isomorphic to Vo. We assume the node feature vectors to be an one-hot encoding of the node colors.
3.1 COMPUTATION FRAMEWORK OF GNNS
GNNS aggregate messages in layer-by-layer manner. Assuming X, RIFF the input feature
vector for every node v E V. the 0th layer representation of node v is simply h. = X2 Ve E V. Subsequently, in each layer GNNS draw messages from its neighbours No and aggregate them as follows:
Msa hh Vu NN m (u)
(2)
m AGGREGATE' (u)
(3)
where MsGf and AGGREGATE are either pre-defined functions (Ex: MEANPOOL) or neural networks (GAT (Veličković et al., 2018)). K-B denotes multi-set since the same message may be received from multiple nodes. The 4hh layer representation of v is a summary of all the messages drawn.
he COMBINE' (ha-) ,m
(4)
where COMBINE' is a neural network. Finally, the representation of the graph is computed as:
10a
ogtt-malivv
DD
hg COMBINE(h Ve E V)
(5)
Distribution (%)
100
b. D booost
Here, COMBINE could be aggregation functions
such MEANPOOL, SUMPOOL, etc. and L is total number layers in the GNN.
10-2
3.2 COMPUTATION TREES
We now define the concept of computation trees and draw attention to some important properties that sets the base for graph distillation.
10
10-2 2
10
Normalized Frequency
Figure 2: Frequency distribution of compu- tation trees across datasets. The "frequency" a computation tree denotes the number of occurrences of that specific tree across all graphs in a dataset. The normalized fre- quency of a tree is computed by dividing its frequency with the total number of graphs in dataset and thus falls in the range (0, 1]- The æ-axis of the plot depicts the normal- ized frequency counts observed in a dataset, while the y-axis represents the percentage of computation trees corresponding to each fre- quency count. Both x and y axes are in log scale. The distribution highly skewed characterized by a dominance of trees with low frequency counts, while a small subset of trees exhibiting higher frequencies. For ex- ample, in ogbg-molhiv the most frequent tree alone has normalized frequency of 0.32.
Definition 3 (Computation Tree). Given graph G. node e and the number of layers in a GNN, we construct a computation tree T rooted at Start- ing from v, enumerate all paths, including non- simple paths of L hops. Next, merge these paths under the following constraints to form T.!. Two nodes U; and v in paths P = {uo = v. U1. .........1 } and p' {16 U, rq..... ,v',), respectively, are merged into single node in T if withhrr or 11, = and vk E [0, - 1], and v' have been merged.
Observation In an I.-layered GNN, the final rep- resentation by; of node in graph G can be com- puted from its computation tree T..
Proof. In each layer, GNN draws messages from its direct neighbors. Over L layers, a node v re- ceives messages from nodes reachable within L hops. All paths of length up to L from are con-
tained within T.' Hence, the computation tree sufficient for computing h.:
Observation 2. IsT!' = T then h- h--
non-simple path allows repetition of vertices
4

---

Published as a conference paper at ICLR 2024
Proof. A peessage-passing GNN is at most as powerful Weisfeiler-Lehman tests (1-WL) (Xu et al., 2019), which implies that the L-hop neighborhoods nodes u and v are indistinguishable by 1- WL. then their representations would be the same. 1-WL cannot distinguish between graphs of identical computation trees (Shervashidze et al., 2011).
IT
Observation Two nodes with noniisomorphie L-hop neighborhoods may have isomorphic com- putation trees.
PROOF. See Figure. 3.
Implications: Obs. I reveals that any graph may be decomposed into a multiset of computation trees (not a set since the same may appear multiple times) without loosing any information. By learn- ing the representations of each computation tree root, we can construct each node representation accurately, and consequently, derive an accurate representation for the entire graph (Recall Eq. 5). Now, suppose the frequency distribution of these computation trees in the multiset is significantly skewed, with a small minority dominating the count. In that case, the graph representation, obtained by aggregating the root representations of only the highly frequent trees, will closely approximate the true graph representation. This phenomenon, illustrated Figure. 2, is commonly observed. Furthermore, Obs. 3 implies that the set of all computations trees is strictly subset of the set of all L-hop subgraphs in the dataset, leading to further skewness in the distribution. Leveraging this pattern, we devise distillation process that revolves around retaining only those computation trees that co-occur frequently. While frequency captures the contribution of a computation tree towards the graph representation, co-occurrence among trees captures frequent graph compositions.
3.3 MINING FREQUENTLY CO-OCCURRING COMPUTATION TREES
Let T (Ti,..., Tn) be set of computation trees. The frequency of T in the train set D (GI.... } is defined as the proportion of graphs that contain all of the computation trees in T. Formally,
fTeq(T) [9 E D VT E T, .T! E Tg, T = T.'
(6)
|D]
Here, T& denotes the set of computation trees in graph G.
Problem 2 (Mining Frequent Co-occurring Trees), Given a set of (D] computation tree multi-sets* (T,,.... m corresponding each graph in the train set = (91,... 9.m and a thresh- old 0, mine all co-occurring trees with frequency of at least 0. Formally, we seek to identify the following distilled answer set.
S == freg(X) 2 0} where = -UP
U (T.
VT,EI
denotes the universe of all unique computation trees, ie.,, VT, E T.
We map Problem 2 to the problem of mining frequent itemsets from transaction databases (Han et al., 2004), which we solve using the FPGROWTH algorithm (Han et al., 2004).
3.4 MODELING AND INFERENCE
Algorithm. 1 in the appendix outlines the pscudocode of our data distillation and Algorithm. outlines the modeling algorithm. We decompose each graph into their computation trees. We mine the frequently co-occurring trees from each class separately. Instead of training on a batch of graphs, we sample batch of frequent tree sets. Each of these frequent tree sets serves entire graph, allowing us to approximate the graph embedding. To achieve this approximation, we utilize the COMBINE function (Eq. 5) on the embeddings of the root node within each tree present in the selected set. The probability of selecting a particular tree set for sampling is directly proportional its frequency of occurrence.
surrogate for an
3.5 PROPERTIES AND PARAMETERS
Parameters: As opposed to existing graph distillation algorithms (Jin et al., 2022; 2021; Xu et al., 2023), which are dependent on the specific choice of GNN architecture and all paper-parameters that the GNN relies on, MIR AGE intakes only two parameters: the number of GNN layers T. and the fre- quency threshold 0. 0, which lies in [0, 1], is GNN independent parameter. The size of the distilled dataset increases monotonically with decrease in Hence, may be selected based on the desired distillation size. L is the only model-specific information require. We note that the number of
non- isomorphic graphs may decompose the same set of computation trees
5

---

Published as a conference paper at ICLR 2024
layers used while training needs to be L. and need not exactly L, since T 2 To! Hence, should be set based on the expected upper limit that may be used. GNNS are typically run with L I 3 due to the well- issue of mmoosiig and over-squashing (Topping et al., 2022).
Algorithm Characterization: MIRAGE has several salient characteristics when compared to exist- ing baselines, all arising due to being unsupervised to original training gradients-th predominant approach in graph distillation.
Robustness:
The distillation process is independent of training ryper-parameterr (except the mild assumption on maximum number of GNN layers) and choice of GNN architecture. Hence, it does not need to be regenerated for changes to any of the above factors.
Storage Overhead: MIRAGE has a smaller storage footprint since a single distilled dataset suf- fices for all combinations of architecture and syper-parameters.
CPU-bound executions and efficiency: The distillation pipeline is function of the training dataset only. Hence, it is computationally efficient requiring only CPU-bound operations.
Complexity Analysis: A detailed complexity analysis of MIRAGE is provided in Appendix A. We also discuss strategies to speed-up tree frequency counting through the usage of canonical labels. In summary, the entire process of decomposing the full graph database into computation tree sets incurs (( x d²) cost, where z ΣxgeD [V] and 5 the average degree of nodes. Counting frequency of all trees consume O (z x Lø log(o)) time. FPGROWTH consumes O(2) in the worst case, but it has been shown in the literature that empirical efficiency is dramatically faster due sparsity in frequent patterns (Han et al., 2004).
EXPERIMENTS
In this section, we benchmark MIRAGE and establish: Accuracy:
MIRAGE the most robust distillation algorithm and consistently ranks among the top-2 performers across all dataset-GNN combinations.
Compression: MIRAGE achieves the highest compression on average, which is 4 and as times smaller that the state of the art algorithms of DOSCOND and KIDD) respectively.
Efficiency: MIRAGE is & 150 and xs 500 times faster than DOSCOND and KIDD on average.
All experiments have been executed 5 times. We report the mean and standard deviations. The com iiiiaiiitd/Miaageeee For details on the hardware and software platform used, please refer to Appendix B.1.
codebase MIRAGE shared at
4.1 DATASETS
Table
Dataset statistics
To evaluate MIRAGE, datasets from Open Graph Bench-
use
Dataset
#Classes
#Graphs
Avg. Nodes
Avg. Edges
Domain
mark (OGB) (Hu et al., 2020) and TU Datasets (DD, IMDB-B and NCI1) (Morris al., 2020) span- ning a variety of domains. The chosen datasets represent suffi- cient diversity in graph sizes (~2 24 nodes to 284 nodes) and density (+= 10).
ogbg-molbace NC11
2
1513
34.1
36.9
Molecules
2
4110
29.9
32.3
Molecules
oghg-man molhbbp
2039
24.1
Molecules
ogbg-molhiv
41,127
25.5
54.9
Molecules
DD
2
1178
284.3
715.7
Proteins
IMDB-B
1000
193.25
Movic
IMDB-M
1500
13
65.1
Movie
4.2 EXPERIMENTAL. SETUP
Baselines. Among neural baselines, we consider the state of the graph distillation algorithms for graph classification, which are (1) DoSCOND (Jin et al., 2022) and (2) KIDD (Xu et al., 2023). We do not consider GCOND (Jin al., 2021) since DOsCOND have been shown consistently outperform GCOND. KIDD supports graph distillation only GIN. We also include (3) HERD- ING (Welling, 2009) maps graphs into embeddings using the target GNN architecture. Subsequently, it selects the graphs that are closest to the cluster centers in the distilled set. Finally, consider the (4) RANDOM baseline, wherein we randomly select graphs over iterations from each class in the dataset till the combined size exceeds the size of the distilled dataset produced by MIRAGE.
Evaluation Protocol. We benchmark MIRAGE and considered baselines across three different GNN architectures, namely GCN (Kipf & Welling, 2016), GAT (Veličković et al., 2018) and GIN (Xu al., 2019). is worth noting that this is the first graph distillation study to span three GNN architectures when compared DosCOND KIDD, that evaluate only specific GNN of choice. KIDD only

---

Published as a conference paper at ICLR 2024
Table 2: AUC-ROC of benchmarked algorithms across datasets and GNN architectures. The best and the second best AUC-ROC in each dataset is highlighted in dark and light green colors respectively. We do not report the results of GAT in IMDB-B and IMDB-M since GAT achieves an AUC-ROC of ~ 0.5 across the full datasets and their distilled versions for all baselines. These datasets do not contain any node features and GAT struggles to learn attention in this scenario.
Dataset
Model
RANDOM (mean)
RANDOM (sum)
HERDING
KIDD
DoSCOND
MIRAGE
Full Datasel
65.43
73.75
58.30 7.04
66:16-440 4.82
08.30
70.77
77.20 + 2.20
molg-molliac
GCN
62.96 2: 3.25
76.03 + 0.60
52.46 4: 6-37
63
05.9223
13.1
67.34 = 1.81
77.03 2 1:24
77.81 +: 1.60
GIN
57.18 + 10.4
74,95 + 2:28
60.24
+ 6.17
77 0.57
63.41
0.06
76.18 +: 0.61
78.08 + 3.70
50.46
6.87
06.77
60.62
1.47
58.10
63.50 0.71
NCI
GCN
51.36 + 0.36
60.72 + 8.06
66.86 + 0.73
04.85
2.32
57.90
0.75
68.20 0.044
87.03 + 0.557
GIN
51,60 +: 5.85
61.15 + 7.30
67.12 90
60.83 2.26
2.30 59.80
07.91 0.31
85, +: 2.19
57.16
62.88
3.31
61.12
64.70 2.10
molg-bo
GCN
00.18 2: 2.63
58.76 4. 3.51
56.93 1: L.09
58.77
1.83
59.19 = 0.95
0.52 61.30
64.43 1: 2.21
GIN
60.06 + 3.85
60.21 + 3.14
54.88 +: 2.84
64:21 0.00
61.10 =: 2.10
0.77 61:21
64.95 + 2.24
53.35
61:61
7G
69.77
0.64
73.71 1.166
molhiv
GCN
48.21 4: 5.95
67.20 1: 6.16
59.36 1: 2.79
69.56
2.74
73:16
0.69
3.29 69.59
75.93 1: 1.29
GIN
53.07 7.07
60.94 + 1.42
69:66 + 2.64
63:02
4.48
72.72 0.80
71.58 1.42
78.66 + 1.31
GAT
10.87 + 1.10
67.31 12.0
71.20 2.14
73.14
4.32
63.45 - 2.47
76.08
76.36 01.09
DD
GCN
33.5 58 2.38
58.02 +: 8.57
26.26 +: 5.63
71 6.04
68.39
9.64
74.84
2.15
75.37 +: 1.23
GIN
57.34 4: 1.60
67.50 +: 9.66
13.23 1: 3.02
64.55 = 3,50
60.23 =: 1.76
74.45 4: 0.67
74.74 1: 0.58
IMDR-8
Gcy
32.06
50.38 0.31
60:80 3:-43
08 10
05.56
10.17
00.84 2.50
GIN
51.31 4 4.10
51.12 4: 2.76
60, 68 1: 3.28
07.45 = 0.16
60.02 = 2.19
02.18
0.17
66.73 +: 1.53
IMDB-M
GCN
55.10 1 3,80
52.90 +: 2.52
61:00 +: 2:30
57 1.11
55,90 = 1.06
63:20 -: 1.12
61.10 +: 1.10
GIN
60.10
2.667 2.67
56.30 à 5.50
58.47 1 4.12
54.15 0.90
58.30 1.70
61.80
1.51
64.50 4: 1.10
supports GIN. Hence, for other GNN architectures, we use the distilled dataset for GIN, but train using the target GNN.
Parameter settings. Syper-parameters used to train MIRAGE, the baselines, and the GNN models are discussed in Appendix B.2.
4.3 PERFORMANCE IN GRAPH DISTILLATION
Prediction Accuracy. In Table 2, we report the mean and standard deviation of the testset AUC- ROC of all baselines on the distilled dataset as well as the AUC-ROC when trained on the full dataset. Several important insights emerge from Table 2.
Firstly, it is noteworthy that MIRAGE consistently ranks as either the top performer or the second- best across all combinations of datasets and architectures. Particularly striking is the fact that MI- RAGE achieves the best performance in 8 out of the 17 architecter combinations, which stands as the highest number of top rankings among all considered baselines. This demonstrates that being unsupervised to original training gradients does not hurt MIRAGE'S prediction accuracy.
Secondly, we observe instances, such as in DD, where the distilled dataset outperforms the full dataset, an outcome that might initially seem counter-intuitive This phenomenon has been reported in the literature before (Xu et al., 2023). While pinpointing the exact cause behind this behavior is challenging, we hypothesize that the distillation process may tend to remove outliers from the train- ing set, subsequently leading to improved accuracy. Additionally, given that distillation prioritizes the selection of graph components that more informative to the task, it is likely to retain the most critical patterns, resulting in enhanced model generalizability.
Finally, we note that the performance of RANDOM (sum), which involves random graph selection and the COMBINE function (Eq. 5) being SUMPOOL, is surprisingly strong, and at times surpassing the performance of all baselines. Interestingly, in the literature, DOSCOND and KIDD have reported results only with RANDOM (mean), which is substantially weaker. We investigated this phenomenon and noticed that in datasets where RANDOM (sum) performs well, the label distri- bution of nodes and the number of nodes across the classes are noticeably different. SUMPOOL is better at preserving these magnitude differences in node and label counts compared to MEANPOOL, which averages them out.
Compression. We next investigate the size of the distilled dataset. MIRAGE independent of the underlying GNN architecture, ensuring that its size remains consistent regardless of the specific architecture employed. On the other hand, KIDD, as previously indicated in $ 4.2, conducts dis- tillation with the assumption that GIN serves as the underlying GNN architecture. In the case of DOSCOND and HERDING, these methods support various GNN architectures; however, the size of the distilled datasets is architecture-specii DOM from this analysis as, per our discussion in $ 4.2, we select graphs until the dataset's size exceeds that of MIRAGE Consequently, by design, its size closely aligns with that of MIRAGE.
for each. It is important to note that we exclude RAN-
7

---

Published as a conference paper at ICLR 2024
Table 3: Size of distilled dataset, in terms of bytes, produced by benchmarked algorithms across datasets and GNN architectures. The best compression is highlighted in dark green color. The results for IMDB-B and IMDB-M for GAT represented as are skipped since GAT achieves = 0.5 AUC-ROC on IMDB-B and IMDB-M.
Method
HERDING
DOSCOND
KIDD
MIRAGE
Full Dataset
Dataset
GAT
GcN
GIN
GAT
GCN
GIN
ogbg-molbace
25,771
26,007
26,129
2,592
23,176
23.176
23,176
1.612
1,610,356
NCII
5,662
5,680
5,683
26,822
70.168
70,760
73.128
318
1,046,288
ogbg-molbbbp
10,497
10,514
10,466
3,618
13,632
14,280
20,832
6,108
740,236
ogbg-molhiv
21,096
21,096
21,140
7,672
4,808
5,280
4,400
3,288
41,478.694
DD
89,882
89,869
90,086
408,
210,168
210,184
209,816
448
7,414,218
IMDB-B
1,238
1,252
980
1184
2484
280
635,856
IMDB-M
1,156
1,256
936
720
824
228
645.160
In Table 3, we present the compression results. MIRAGE stands out by achieving the highest com- pression in 5 out 6 datasets. In the single dataset where it does not hold the smallest size, MIRAGE still ranks the second smallest, showcasing its consistent compression performance. On average, MIRAGE achieves a compression rate that is RJ 4 times higher compared to DOSCOND and 5 times greater than KIDD, This notable advantage of MIRAGE over the baseline methods underscores the effectiveness of exploiting data distribution over replicating gradients, at least within the context of graph databases where recurring patterns are prevalent.
Distillation Time. We now focus on the efficiency of the distillation process. Fig. 4a presents this information. We observe that MIRAGE is more than 500 times faster on average than KIDD and ~ 150 times faster than DOSCOND. This impressive computational-effict despite MIRAGE utilizing only a CPU for its computations, whereas DOSCOND and KIDD are reliant on GPUs This trend is direct consequence of MIRAGE not being dependent training on the full data, KIDD is slower than DOSCOND since, while both seek to replicate the gradient trajectory of model weights, KIDD solves this optimization problem exactly, whereas DOSCOND an approximation. When compared to the training time on full dataset (See Table I, MIRAGE is more than 30 times faster average). Overall, MIRAGE is not only faster, but also presents more environment-friee frienddl and energy-efficient approach to graph distillation.
is achieved
4.4 SUFFICIENCY OF FREQUENT TREE PATTERNS
In order to establish the sufficiency of frequent tree patterns in capturing the dataset characteristic, we conduct the following experiment. We train the model on the full dataset and store its weights at each epoch. Then, we freeze the model at the weights after each epoch's training and pass both the distilled dataset consisting of just the frequent tree patterns and the full dataset. We then compute the differences between the losses as shown in Fig. 5a. We do this for all the models for datasets ogbg-molbace, agbg-molbbbp and ogbg-molhiv (full results in Figure I in appendix). The rationale behind this is that the weights of the full model recognise the patterns that are important towards minimizing the loss. Now, if the same weights continue to be effective on the distilled train set, indicates that the distilled dataset has retained the important information. In the figure, we can see that the difference quickly approaches O for all the models for all the datasets, and only starts at a high value at the random initialization where the weights are not yet trained to recognize the important patterns. Furthermore, gradient descent will run more iterations on trees that it sees more often and hence infrequent trees have limited impact on the gradients. Further, in Fig. 5b, we plot the train loss on full and distilled dataset with their own parameters learned through independent training. As visible, the losses are similar, further substantiating the rich information content in
Harding (GAT) Herding (GCN)
Hending (GIN) DosCond (GAT)
DevGond (CCN)
KID
DosCond (GIN)
Destattion Time
Mirage KDD
Running time
10.-
Dond
(CAT)
DosCand (CCN)
100
DooCard (GIM)
10-
ogbg-mollace
NC11
ogbg-mollbbb molgi
DD
IMDB-B
n_hops
(a) Distillation times for the different methods. Full numbers and stan- dard deviations are in Table E in Appendix.
(b) Distillation time vs
number of hops
Figure 4: (a) Distillation times for the different methods. (b) Distillation time as a function of number of hops on ogbg-molbbbp dataset.
8

---

Published as a conference paper at ICLR 2024
oghag moll-molbace
oghg-malbbbp
oghg-malliv
Full dataset
10
Distilled
Loss difference
Train Loss
10
Ll A Aod
10
15
20
25
30
100
Epoch
Epochs
(a) Sufficiency of Frequent Tree Patterns
(b) Training loss epechs
Figure 5: (a) For this experiment the model weights extracted after each epoch. Then, the model weights are loaded from the epoch weights and kept fixed for the following procedure. The dataset condensed using MIRAGE and the full dataset are then passed through the model. The difference between the losses is plotted. The difference between the losses approaches 0. Note that the model was trained on the full dataset. (b) Training loss vs epochs on Dgbg-molhiv(GCN). Results on more datasets can be found in Appendix H.
the distilled dataset. These results empirically establish the sufficiency of frequent tree patterns in capturing the majority of the dataset characteristics.
4.5 IMPACT OF PARAMETERS
Impact of Frequency Threshold. In Appendix we study the impact of frequency threshold on distillation efficiency.
Appendix 4b we analyze the efficiency of distillation as the number of hops increase. We observe running time of MIRAGE is lower similar to other distillation methods as number of hops increase. For more details see Appendix
Impact of Number of Hops:
We refer the reader to Appendix F and H for more experiments parameter variations and their impact on AUC and efficiency.
5 CONCLUSIONS, LIMITATIONS AND FUTURE WORKS
Training Graph Neural Networks (GNNS) on large-scale graph datasets can be computationally in- tensive and resource-demmanding. To address this challenge, one potential solution to distill the extensive graph dataset into more compact synthetic dataset while maintaining competitive predic- tive accuracy. While the concept graph distillation has gained attention in recent years, existing methods typically rely on model-related information, such as gradients or embeddings. In this re- search endeavor, we introduce novel framework named MIRAGE, which employs a frequent pattern mining-based approach. MIRAGE leverages the inherent design of message-passing frameworks, which decompose graphs into computation trees. It capitalizes on the observation that the distribu- tion of these computation trees often exhibits a highly skewed nature. This unique feature enables us to compress the computational data itself without requiring access to specific model details or hyper-parameters, aside from reasonable assumption regarding the maximum number of GNN lay- ers. Our extensive experimentation across six real-world datasets, in comparison to state-of-the-an algorithms, demonstrates MIRAGE'S superiority across three critical metries: predictive accuracy, distillation efficiency that is 150 times higher, and data compression rates that are 4 times higher. Moreover, it's noteworthy that MIRAGE solely relies on CPU-bound operations, offering a more environmentally sustainable alternative to existing algorithms.
Limitations and Future Works: MIRAGE, well as, existing graph distillation algorithms cur- rently lack the ability to generalize effectively to unseen tasks. Moreover, their applicability to other types of graphs, such as temporal networks, remains unexplored. Additionally, there is a need to assess how these existing algorithms perform on contemporary architectures like graph transform- ers (e.g., (Ying et al., 2021; Rampášek et al., 2022)) or equivariant GNNS (e.g., (Satorras et al., 2022)). Our future work will be dedicated to exploring these avenues of research. Finally, MI- RAGE relies on the assumption that the distribution of computation trees is skewed. Although we provide compelling evidence of its prevalence across diverse range of datasets, this assumption may not hold universally, especially in the case of heterophilous datasets. The development a model-agnostic distillation algorithm remains open challenge in such scenarios.

---

Published as a conference paper at ICLR 2024
6 ACKNOWLEDGEMENT
We acknowledge the Yardi School of AI, IIT Delhi for supporting this research. Mridul Gupta acknowledges Google for supporting his travel. Sahil Manchanda acknowledges GP Goyal Alumni Grant of IIT Delhi for supporting his travel.
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. 1 1
Suresh Bishnoi, Ravinder Bhatroo, Sayan Ranu, and NM Krishnan. Enhancing the inductive biases of graph neural ode for modeling dynamical systems. ICLR, 2023. (Cited on p. <-)
Douglas M. Campbell and David Radford. Tree isomorphism algorithms: Speed vs. clarity, Mathe- maticy Magazine, 64(4):252-261, 1991. ISSN 0025570X, 19300980. URL http:/www.jsttrr.org stable/2690833. (Cited on p. 13 (-)
Pritish Chakraborty, Sayan Ranu, Krishna Sri Ipsit Mantri, and Abir De. Learning and maximizing influence in social networks under capacity constraints. In Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining, pp. 733-741, 2023. (Cited p.
Yun Chi, Yirong Yang, and Richard R. Muntz. Canonical forms for labelled trees and their applica- tions in frequent subtree mining. Knowledge and Information Systems, 8(2):203-234, Aug 2005. ISSN 0219-3116. doi: 10.1007/1101115-044-01000
URL https://0o..rr//000000//01111110
0180-7. (Cited on p. 13 (2)
Nikhil Goyal, Harsh Vardhan Jain, and Sayan Ranu. Graphgen: scalable approach domain- agnostic labeled graph generation. Proceedings of The Web Conference 2020, pp. 1253-1263, 2020. (Cited on p. 1+)
Mridul Gupta, Hariprasad Kodamana, and Sayan Ranu. FRIGATE: Frugal spatio-temporal forecast- ing road networks. In 29th SIGKDD Conference Knowledge Discovery and Data Mining, 2023. URL
(Cited on ())
Shubham Gupta, Sahil Manchanda, Srikanta Bedathur, and Sayan Ranu. Tigger: Scalable generative modelling for temporal interaction graphs. In Proceedings of the AAAI Conference on Artificial Intelligence volume 36, pp. 6819-6828, 2022. (Cited on p. 14)
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31st International Conference Neural Information Processing Systems, NIPS' 17, pp. 1025-1035, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860964, (Cited on pp. and ())
Jiawei Han, Jian Pei, Yiwen Yin, and Runying Mao. Mining frequent patterns without candidate generation: frequent-pattem approach. Data Mining and Knowledge Discovery, 8(1):53- 87, January 2004. (Cited on pp. 5, 6, and ())
Weihua Hu, Matthias Fey, Marinka Zitikk Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22118 18-22133,, 2020. (Cited p. 6 (2)
Jayant Jain, Vrittika Bagadia, Sahil Manchanda, and Sayan Ranu. Neuromir: Robust & reliable route recommendation road networks. Advances in Neural Information Processing Systems, 34:22070-22082, 2021. (Cited on (-)
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. 5, and 6 (-)
10

---

Published as a conference paper at ICLR 2024
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 pp. 2, 5, and (-)
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: 2016. (Cited on pp. 2, 3, and 6 +-)
Xiucheng Li, Cong, and Yun Cheng. Spatial transition learning on road networks with deep probabilistic models. 2020 IEEE 36th International Conference Data Engineering (ICDE), pp. 349-360, 2020. URL ())
(Cited on p.
Sahil Manchanda, Akash Mittal, Anuj Dhawan, Sourav Medya, Sayan Ranu, and Ambuj Singh. Gcomb: Learning budget-constrained combinatorial algorithms over billion-sized graphs. Ad- vances in Neural Information Processing Systems, 11-20000-20011 2020. (Cited on p. (-)
Sahil Manchanda, Shubham Gupta, Sayan Ranu, and Srikanta J. Bedathur. Generative modeling of labeled graphs under data scarcity. In The Second Learning Graphs Conference, 2023. URL https://openreview.. http:///ppeneiiiee..ee/ooonoll/s
(Cited on p. 1 1+)
Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. arXiv preprint arXiv:2007.08666. 2020. (Cited p. 6 (-)
Ladislav Rampášck, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for General, Powerful, Scalable Graph Transformer, Advances Neural Information Processing Systems, 35, 2022. (Cited on pp. and 9 (-)
Alvaro
Jonathan Godwin, Tobias Pfaff, Rex Ying, Jure Leskovee, and Peter Battaglia. Learning simulate complex physics with graph networks. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 8459-8468. PMLR, 13-18 Jul 2020. (Cited on p. ())
Victor Garcia Satorras, Emiel Hoogeboom, and Max Welling. E(n) equivariant graph neural net- works. In ICML, 2022. (Cited on (2)
Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhor, and Karsten M. Borgwardt. Weisfeiler-lehman graph kernels. J. Mach. Learn. Res., 12(mull):2599-25 2561, nov 2011. ISSN 1532-4435. (Cited on p. 5 +)
Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J. Sutherland, and Ali Kemal Sinop. Exphormer: Sparse transformers for graphs. In ICML, 2023. (Cited on p. 17 (-)
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. In ICLR, 2022. (Cited on p. +))
Gabriel Valiente. Tree Isomorphism, pp. 151-251. Springer Berlin Heidelberg, Berlin, Hei- delberg, 2002. ISBN 978-3-662--0922--1. doi: 10.1007/978-33662--99999 2018. URL //00:.or//0..1007777336666--0099
URL https:
(Cited on p. 13+2)
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, (Cited pp. 1, 2, 3, 4, and 6 +2)
Clement Vignac, Igor Krawczuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pascal Frossard. Digress: Discrete denoising diffusion for graph generation. In The Eleventh Inter- national Conference on Learning Representations, 2023. URL https://openreview..n http:///oeemeiiieeeee//ooonni wwt.:/rr///fftttt........ ?id= Nu86-N (Cited on p. (~)

---

Published as a conference paper at ICLR 2024
Wei Wang, Haili Yang, Yuanfu Lu, Yuanhang Zou, Xu Zhang. Shuting Guo, and Leyu Lin. Influence maximization multi-relational social networks. In Proceedings of the 30th ACM international conference on information & knowledge management, pp. 4193 4202, 2021. (Cited on p. +-)
Max Welling, Herding dynamical weights learn. In Proceedings of the 26th Annual International Conference on Machine Learning, pp. 1121-1128, 2009. (Cited on p. 6 (-)
Hao Wu, Ziyang Chen, Weiwei Sun, Baihua Zheng, and Wei Wang. Modeling trajectories with
recurrent neural networks. Proceedings of the 26th International Joint Conference on Artificial Intelligence, IJCAI 17, pp. 3083-3090, 2017. (Cited on 1 (2)
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph ral networks? In International Conference on Learning Representations, 2019. URL https: //openreview //opemreview.nefffouum cieefforummii-ryyssiiiii
(Cited pp. 2, and +-)
Zhe Xu, Yuzhong Chen, Menghai Pan, Huiyuan Chen, Mahashweta Das, Hao Yang, and Hang- hang Tong. Kernel ridge regression-based graph dataset distillation. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. KDD '23, pp. 2850-2861, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9798400701030. doi: (Cited on pp. 2, 5,
10. 145/3580000335993998. URL http::///bbb.or//1..111/5///////
6, and 7 <-)
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 cttpoopperreiiieeeeeffrrrr VqIWgUVsXc. (Cited on p. 2 (-)
Shuang-Houn -ong Yang, Bo Long, Alex Smola, Narayanan Sadagopan, Zhaohui Zheng, and Hongyuan Zha. Like like alike: joint friendship and interest propagation in social networks. In Proceedings of the 20th international conference World wide web, pp. 537-546, 2011. (Cited p. 1 (~)
Chengxuan Ying. Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu. Do transformers really perform badly for graph representation? In A. Beygelzimer, Y. Dauphin, P. Liang, and Wortman Vaughan (eds.). )) Advances in Neural Information Processing Systems, 2021. URL https://openreview. www.//erummdd-OOOOe Wwoo::/mmdddddooooooooooooD (Cited on pp. and? +))
Jiaxuan You, Rex Ying, Xiang Ren, William L. Hamilton, and Jure Leskovec. Graphrnn: Generat- ing realistic graphs with deep auto-regressive models. In Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmüssan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Ma- chine Learning Research, pp. 5694-5703. PMLR, 2018. URL http://proceedinggss mlr press/v80/ wwt.ssssss...../888.1 youl8a.html. (Cited p. 1
Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. Dataset condensation with gradient matching. In ICLR, 2021. (Cited on {ي)
12

---

Published as a conference paper at ICLR 2024
(())))))
(((O)))
(0))))
(0)O)
(0)
(0)
(0)
(0)
(0)
(0)
(a)
(b)
Figure (a) and (b) show Knuth Tuples based canonical labels for two isomorphic trees. The process starts at the leaves and goes up to the root. Whenever a node encapsulates its children's s labels, sorts them in increasing order of length. This can be adapted for the cases when nodes have labels and when the edges have labels by making appropriate changes to the tuples.
APPENDIX
A COMPLEXITY ANALYSIS
Computation tree decomposition: Each graph 9 = (V. X), decomposes into | computation trees. Assuming an average node degree of 8, enumerating a computation tree consumes ((*)) time. Hence, the entire process of decomposing the full graph database into computation tree sets incurs ((2 x 8²) computation cost, where = Evged [
Frequency counting: Computing the frequency of a computation tree requires to perform tree isomorphism test. Although no polynomial time algorithm exists for graph isomorphism, in rooted trees, it can be performed in linear time the number of nodes in the tree (Valiente, 2002), which in our context is (8))) Thus, frequency counting of all trees requires O x 2²) time. In MIR AGE, we optimize frequency counting further using canonical labeling (Campbell Radford, 1991).
Definition 4 (Canonical label). A canonical label of a graph G involves defining a unique represen- tation or labeling of a graph a way that invariant under isomorphism. Specifically, if the function that maps a graph to its canonical label, then
9 _ G2 + L(G)) L(G2)
There are several algorithms available described (Campbell & Radford, 1991) and (Chi et al., 2005) that map rooted-treed ttreesttesseee canonical labels. We use (Campbell & Radford, 1991) 1) in our imple- mentation, which is explained in Fig. F.
Canonical label construction for rooted tree consumes O(m log(m)) time if the tree contains m nodes. In our case, m = ((5²) ) as discussed earlier. Thus, the complexity O log(ō")) = OLL log(o)) time. Once trees have been constructed, frequency counting involves hashing each of the canonical labels, which takes linear time to the number of graphs. Hence, the complexity reduces O(z x L8 log())) when compared the all pairs tree isomorphism approach of O(8" x 2?) (L log(8) <2). 2).
Frequent itemset mining: Finally, in the frequent itemset mining step, the complexity in the worst case is (l) In reality, however, the running times dramatically smaller due majority of items (trees in our context) being infrequent (and hence itemsets as well) (Han et al., 2004).
EMPIRICAL SETUP
B. HARDWARE AND SOFTWARE PLATFORM
All experiments are performed on an Intel Xeon Gold 6248 processor with 96 cores and NYIDIA A100 GPU with 40GB memory, and 377 GB RAM with Ubuntu 18.04. In all experiments, have trained using the Adam optimizer with a learning rate of 0.0001 and choose the model based on the best validation loss.
13

---

Return Published as a conference paper at ICLR 2024
Algorithm MIRAGE: Proposed graph distillation algorithm
Input Train set D, number of layers GNN, frequency threshold
Output Distilled dataset S and parameters θ of the GNN when trained on S
1: S 0
2: for each Class in dataset do
3:
Ie 6-
4:
for each 9 = (V,E, X) E D such that V/g = co
5:
T イ-
6:
for each e E V do
7:
T TU (T
compute-tree(C, Vu v)
8:
T S.UT
9: S 6 S-SURT FFGROWTTTH 0)
Algorithm Training GNN using data distilled using MIRAGE
Input Distilled dataset S
Output Parameters θ of the GNN when trained on S
Randomly initialize
2: while Model loss has not converged do
3: B <-a batch of tree sets sampled in proportion to their frequencies from
4: for each T 2 do
5: hy CCMBIINE VT E T)
6: Update θ using backpropagation based on loss over {hr VT B}
7: Return +
B.2 PARAMETERS
Table Da presents the parameters used to train MIRAGE. Note that the same distillation parameters are used for all benchmarked GNN architectures and hence showcasing its robustness to different flavors of modeling pipelines.
For neural baselines KIDD and DOSCOND, we use the same parameters recommended in their respective papers on datasets that are also used in their studies. Otherwise, the optimal parameters are chosen using grid search.
perform grid search optimize performance the whole dataset. The same parameters are used to train and infer on the distilled dataset. The hyper- parameters used are shown in Table Db.
For the model hyper-parametert
Train-validation--ess Splits. The OGB datasets come with the train-validation-tess splits, which also used in DosCOND and KIDD. For TU Datasets, randomly split the graphs into 80% 10% 11% for
We stop the training of a model it does not improve the validation loss for more than 15 epochs.
Table Parameters used for MIRAGE.
(a) Distillation parameters. &o and 0 represent the frequency thresholds class respectively.
(b) Model parameters
Dulaset
6,
#hops (L)
Model
Layers
Hidden Dimension
Dropout
Reduce Type
NCHI
27%
35%
GeN
[2.3)
(64, 128)
[0, 0.6
(sum,mean)
oghg molhbbp
5%.
7%
GAT
(2,3)
[64, 128
0.0.6
(sum,mean
oghg-molbace
13%
10%
GIN
(2.3)
(64, 128)
0.0.6
(sum,mean)
oghg mothiv
5%.
8%
DD
2%
2%
IMDB.R B
20%
20%
14

---

Published as a conference paper at ICLR 2024
Table Graph distillation time (in seconds) consumed by various algorithms. In the last column, also present the total training time in the full dataset to showcase the efficiency gain of distillation.
Method
HERDING
DOSCOND
KIDD
MIRAGE
GAT
GCN
GIN
GAT
GCN
GIN
ophe-molhace
0.57
255.62
7.52
191.22
198.80
2.51
NCII
13.86 +: 0.29
11.61
0.41
11.70
1318 21 + 11.2
1275.83 = 13.2
1237 96
82.5
2200.04
2.39 = 0.16
ogbg-molbbing
23.35 4: 1.59
28.18
1.33
23.86 1: 1.52
285.02
3.34
240.91
7.58
244.44
4.4.1.5.. 5.33
1855.81
14.75 0.09
ogbg-molhiv
173.41 23.8
530.89
27.8
535,08
32.774
808.11 - 12.3
708.33
7.34
755. 18
51.9
6421.98
50.86 = 0.32
DD
8.18
1: 0.51
7.95 1 0.57
9.02 0.56
$51.99
00
8.36
485.81
1. 3.79
511.14 1.444.444.11 4.13
2201.09
13.93 1: 0.16
IMDB-B
4.64
Table F: Cross-arch performance: The performance of DOSCOND when graph distillation is per- formed using gradients of particular GNN, while the model is trained another GNN.
GAT
GCN
GIN
condensed using.
GAT GCN GIN
61.12 + 2.51
59.86 + 1.50
59.36
1.26
59.33 + 3.37
59.19 + 0.95
57.02 + 3.09
58.20 + 1.91
56.42 + 1.68
61.10 = 2.10
(a) ogbg-molbbbp
train-test-> using
GAT
GCN
GIN
GAT
68.30 + 1.01
67.01 + 4.21
62.90 4.84
GCN
63.70 + 2.98
67.34 + 1.84
58.91 = 4.85
GIN
65.7 + 3.81
66.47 + 3.83
63.41 = 0.66
(b) ogbg-molbace
C DISTILLATION GENERALIZATION OF DOSCOND
While message-passing GNNS come in various architectural forms, one may argue that the embed- dings generated, when the data and the loss same, are correlated. Hence, even in the case of GNN-dependent distillation algorithmss, such as DOSCOND, it stands to reason that the same distil- lation data could generalize well other GNNS. In Table the six evaluated combinations. except for the case of GCN in ogbg-molbbbp, we consistently ob- serve that the highest performance is achieved when the distillation GNN matches the training GNN. This behavior is unsurprising since although GNNS share the initial task of breaking down input graphs into individual components of message-passing trees, subsequent computations diverge. For instance, GIN employs SUMPOOL, which is density-dependee Conversely, GCN, owing to their normalization based on node degrees, does not preserve magni- tude information effectively. GAT, on the other hand, utilizes attention mechanisms, resulting in varying message weights learned as a function the loss. In summary, Table F provides additional evidence supporting the necessity for GNN-independent distillation algorithms.
investigate this hypotheses. Across
and retains magnitude information.
Table G: Below we present the AUCROC numbers of DOSCOND on randomly initialized GCN models, warm start (100 epochs) and converged DosCOND (typically around 1000 epochs).
Dataset
Random
Warm Started
Convergence
ogbg-molbace
55.04 + 9.07
59.95 + 1.61
67.34 + 1.84
NCI1
51.22 + 2.00
48.18 2.78
57.90 + 0.75
ogbg-molbbbp
52.64 + 1.98
50.72 3.48
59.19 + 0.95
ogbg-molhiy
48.21 + 5.95
34.99 7.25
73.16 +: 0.69
DD
52.39 = 7.19
61.58 2.11
68.39 + 9.64
15

---

Published as a conference paper at ICLR 2024
Table H: Node classification results
Dataset Type
Size (bytes)
AUC-ROC (%)
Full
1610356
91.15 + 0.09
Distilled using MIRAGE Distilled using DOSCOND
1816
88.92 + 0.77
7760
81.29 = 3.81
D DOSCOND DISTILLATION: RANDOM, WARM-STARTED AND FULLY OPTIMIZED
In this section we investigate how the quality of condensed dataset synthesized by DOSCOND changes during its course optimization. Towards this, we obtain the condensed dataset at ran- dom initialization, after optimizing for small number of epochs and after training of DOSCOND until convergence. In Table G, we present the results. As visible, there a noticeable gap in the AUCROC numbers indicating full training is necessary.
E
NODE CLASSIFICATION
The primary focus of MIRAGE on graph classification. However, it can be easily extended to node classification. Specifically, we omit the graph level embedding construction (Eq. 5) and training is performed on node level embeddings (Eq. 4). use ogbg-molbace to analyze performance in node classification. Here, each node is labeled as aromatic or non-aromatic depending whether it is part of an aromatic ring substructure. The results are tabulated Table H. Consistent with previous results, MIRAGE outperforms DOSCOND in both AUC-ROC and compression (smaller size of the distilled dataset). DOSCOND produces a dataset that is ss times the size that produced by MIRAGE, yet performs more than 7% lower in AUC-ROC. This coupled with aadel--gnostic-ness further solidifies the superiority of MIRAGE.
COMPUTATIONAL COST OF DISTILLATION
In clarifying the computational overhead inherent in the dataset distillation procedure, we conduct series of experiments. Initially, we manipulate the number of hops, recording the corresponding dis- tillation time (Figure H). Simultaneously. (Table I), facilitating a comparative analysis. Our findings reveal that even under high hop counts from the GNN perspective, the distillation process is more time-efficient than complete dataset train- ing. Moreover, the distilled dataset's performance converges closely with that of the full dataset, as evident in Table 2.
provide training time metric for the full dataset setting
55
35
5.
Sa
63.1
251.2
31.65
125
25LBs
15
5.2
251.3:
633s
901.2:
125
2.0
501 25
1000.2
2981 1s
3.0
14 1.6 1.8
22
15
3.5
1.2
12
ragativc das
Throllod regaiee Uass
Theshild eepalre ciew
(a) DD
(b) IMDB-B
(c) ogbg-molliv molhiv
Figure G: Impact of frequency threshold (both positive and negative classes) the distillation time. Here, the thresholds on the positive and negative classes are varied in the and x axis respectively. and the time is presented Subsequently, we subject the system to variations threshold parameters, graphically showing the resulting time in Figure G. Notably, the distillation process exceeds the time of full dataset reaches
contour.
training solely under extreme threshold values. This divergence occurs when distilled reaceet equality with the full dataset in size post-distillation Conversely, for pragmatic threshold values, the dataset distillation procedure consistently manifests as a significantly faster option to full dataset training.
16

---

Published as a conference paper at ICLR 2024
Mrage DoxCond (GCN)
DosCond (GAT)
KiDD
DosCond (GIN)
Distillation Time (4)
2000
3900
1500
1000
300
3
n_hopp
n__hops
ogbg-molbbbb
agbg-molbace
Figure H: Distillation times of MIRAGE, DOSCOND, and KIDD against the number of hops (layers)
in the GNN.
Table I: Training time (in seconds) for full dataset
Model
GAT
GCN
GIN
Dataset +
ogbg-molbace
98.08
73.49
72.99
NCI1
90.71
145.09
120.96
ogbg-molbbbp
150.52
114.55
106.71
ogbg-molhiv
2744.21
1510.36
2418.61
DD
110.06
29.35
106.64
IMDB-B
12.84
11.42
9.81
G SUFFICIENCY OF FREQUENT TREE PATTERNS
This section contains the extended result of the experiment described in section 4.4 as shown in Fig. I. From the Fig. it is clearly visible that the dataset distilled using MIRAGE able to capture the important information present in the full dataset since the difference between the losses when the full dataset is passed through the model and when the distilled dataset is passed through the model quickly approaches O. This trend is held across models even though any information from the model was not used to compute the distilled dataset.
H PARAMETER VARIATIONS
In investigating the influence of the number of hops the Area Under the Curve (AUC), present a graphical representation of the AUC's variation in relation to the number of hops (Fig. K). Also, we depict the AUC in correlation with dataset sizes (Fig. L). important note that sizes are closely tied to threshold parameters; however, the latter is not explicitly shown in the graphical representation due to their inherent high correlation with dataset sizes.
We see mild deterioration in AUC at higher hops in Fig. K. This is consistent with the literature since GNNS are known to suffer from oversmoothing and oversquashing higher layers (Shirzad et al., 2023).
Training Efficiency. We now investigate the reduction in training loss over the course multiple epochs. The outcomes for the datasets bolgmmolbace, ogbg-mohin mohiv, DD, and IMDB-B are displayed Fig. We selected these four datasets due to their representation graph dataset, the dataset with the largest graphs, and the densest graphs, respectively. Across all these datasets, the loss in the distilled dataset remains close to the loss in the full dataset. More interestingly, in three out of four datasets (DD and IMDB-B), the loss begins at substantially lower value in the distilled dataset and approaches the minima quicker than in the full dataset. This trend provides evidence of MIRAGE'S ability to achieve dual objective. By identifying frequently co-
the smallest and largest
17

---

Published as a conference paper at ICLR 2024
ogbg-molbace
ogbg- bbbgbboobbbbp
mgbg-mmlhivv
Loss difference
GCN
10-
5
10
15
20
25
30
20
Loss difference
15-
GAT
10-
5
10
15
20
25
30
100
Loss difference
GIN
50-
Epoch
Figure I: Sufficiency of Frequent Tree Patterns: is seen that the trend that the loss difference
quickly approaches 0 holds across model and datasets.
Full detant
Fall dataset
Full dataet
Full cocaset
2>
Tran Los
Train
Real
50
100
Epochs
Epocks
Epochs
(a) ogbg-molhiv
(b) DD
(c) IMDB-B
(d) ogbg-molbace
Figure J: Variation of training loss against the number of epochs in GCN.
occurring computation trees, we simultaneously preserve the most informative patterns within the dataset while effectively removing noise.
18

---

Published as a conference paper at ICLR 2024
ogbg-molbace
ogbg-molbbbp
100
100
100
75
75
75
AUC (%)
50
50
50
25
25
25
0
3
3
7
n_hops
n_hops
n_hops
GAT
GCN
GIN
Figure K: ROC-AUC versus the hops parameter used during dataset distillation.
100
80
60
AUC (%)
40
ogbg-molhiv
ogbg-molbbbp
20
ogbg-molbace
DD
NCI1
1000
1200
1400
1600
1800
2000
2200
2400
size (bytes)
Figure I. Size vs. AUC for MIRAGE. Note that size is correlated to (0o. 0
19


Reviews:
[{"review_id": "NCU5oHaNLV", "reviewer": "Reviewer_2KBE", "summary": "This paper proposes MIRAGE, a model-agnostic graph distillation method for graph classification task. Specifically, the authors first observe that existing graph distillation methods still rely on training with the full dataset and specific to GNNs architectures and hyper-parameters. To this end, MIRAGE can tackle these two limitations via decomposing input graphs into computation trees. The long-tailed frequency distribution of the computation tree enables the graph distillation with a high compression ratio. Experiments demonstrate the superiority of MIRAGE in terms of its effectiveness, compression ratio, and distillation efficiency.", "questions": "Please see the weakness part.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1.\tThis paper is well-organized and easy to follow.\n2.\tThe idea of making graph distillation model-agnostic is interesting and meaningful in practice. \n3.\tThe proposed data-centric solution is a natural way to mitigate model hyperparameter dependency using the frequency distribution of the computation tree.", "weaknesses": "1. Motivations: \n- (a) Problem Motivation: In the abstract, one of the identified limitations pertains to the reliance on training with the full dataset. To provide a clearer argument regarding the necessity of full dataset training for existing methods and the distinct advantages of MIRAGE, we should consider the following: What is the comparative performance of existing distillation methods (e.g., gradient matching) when applied to both randomly initialized and well-trained models? Is there a substantial performance gap between the two scenarios? Regarding computational costs in the distillation process, it's worth examining the resource requirements for calculating the computation tree frequency distribution, particularly in the context of deep GNNs. How does this computational overhead compare to training models on the full dataset?  \n- (b) Technical Motivation: While the concept of the computation tree is inherent to GNNs, we should address the sufficiency of the frequency distribution for the computation tree. Key points to explore include: Why is maintaining a high computation tree frequency distribution sufficient for effective learning? What is the distribution pattern of the computation tree, and does it exhibit a long-tail distribution?\n\n2. Objectives: Ideally, the distillate data should mirror the distribution of the full dataset, implying that the gradients of the distillate data should align with those of the full dataset for any model (random or well-trained). It's essential to clarify that while distillation can reduce computation costs, the primary objective remains data distillation. Additionally, considering the architecture transferability for existing graph distillation methods, the advantage of model-agnostic techniques is not significant.\n\n3. Experiments: \n- (a) Comprehensive Model Comparison: In evaluating baselines, it would be beneficial to perform a comprehensive comparison across various model architectures. Specifically, assessing performance across different architecture pairs would enhance the evaluation's robustness and provide insights into transferability.\n\n- (b) Baselines and Model Initialization: Investigate the significance of GNN model training prior to distillation for baselines. Explore performance outcomes for well-trained, randomly initialized, and warm-up trained models. Understanding the effectiveness of random initialization can help determine the necessity of training on the full data for baseline methods.\n\n- (c) Hyperparameter Investigation: Explore the impact of different hyperparameters, such as threshold values and the number of hops, on various metrics, including accuracy, efficiency, compression ratio, and transferability.\n\n- (d) Trade-off Analysis: Provide insights into the trade-off between accuracy, efficiency, and compression ratio. Understanding these trade-offs can offer valuable guidance for practical applications.\n\nIn a nutshell, I am currently leaning toward weak rejection. I am looking forward to the authors’ response.\n\n-------------------After rebuttal -------------------------\nThanks for the response. I increase my score to 6.", "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": "MHRwBKHkfy", "reviewer": "Reviewer_pdUR", "summary": "This paper studies a new graph distillation approach called MIRAGE for graph classification, which addresses limitations in existing methods. MIRAGE leverages the idea that message-passing GNNs break down input graphs into computation trees with skewed frequency distributions, allowing for concise data summarization. Unlike traditional methods that emulate gradient flows, MIRAGE compresses the computation data itself, making it an unsupervised and architecture-agnostic distillation algorithm.", "questions": "My major questions are on the experimental evaluation. It would tremendously strengthen this work by addressing the concerns listed in the Weakness section.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. It is crucial to address the issue of existing costs in training large-scale graphs through graph distillation, as it remains an under-explored problem.\n2. It is interesting to observe how the authors have proposed an unsupervised approach for graph distillation, eliminating the requirement for parameters and model architecture, and still achieving comparable performance to the original dataset.\n3. The methodology is interesting, and the performances achieved by their approach are amazing.", "weaknesses": "1. In the results presented in Table 2, why there is a discrepancy compared to those from the original DosCond paper? Could the authors clarify why the authors deviated from the settings employed in the DosCond paper? \n\n2. It would be beneficial if the authors could delve deeper into the sensitivity of their approach with respect to distillation parameters \\theta_1 and \\theta_2. Undertaking further experiments to report the performance across varied distillation parameters might offer greater insights, given that these parameters significantly influence the size of the distilled dataset. \n\n3. On the ogbg-molhiv dataset, could the authors provide an explanation for the better performance observed achieved by distilled data compared to the original dataset.\n\n4. As we are removing the nodes that exist in the less-occurring computational trees, how can we be sure that we are not losing important information in the dataset (especially since this process does not consider the feature information)?  Can authors justify it theoretically or/and empirically by running some experiments?", "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": "hcWsi2mqtE", "reviewer": "Reviewer_yzvf", "summary": "This paper presents a model-agnostic graph distillation algorithm for graph classification, which aims to distill the original graph dataset into a small and compact synthetic dataset maintaining competitive model performance. It is pointed out that existing distillation methods typically rely on model-related information and need to train on the full dataset, resulting in poor generalization and efficiency issues, respectively. To address these weaknesses, MIRAGE directly compresses the computation trees to synthesize datasets by mining sets of frequently co-occurring items. This is inspired by the observation that the distribution of the computation trees, formed by decomposing graphs based message-passing GNN frameworks, always exhibits high skewness. Therefore, it is possible to approximate the true graph representation by aggregating the root representations of only the highly frequent trees. Extensive benchmarking demonstrates the superiority of MIRAGE.", "questions": "1. Original dataset labels are still used during the distillation procedure. So is it a strictly unsupervised algorithm from this perspective?\n\n2. There is no clear statement about how Figure 1 is plotted. And I can't get what the x-axis and y-axis represent, respectively.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper distills the original graph dataset into a novel form, namely the sets of computation trees, instead of traditional feature and structure information, i.e. X’ and A’.\n\n2. This paper not only improves generalization by avoiding model-related computation but also addresses the limitation of the traditional distillation step that necessitates training on the entire dataset.\n\n3. MIRAGE demonstrates superiority from various metrics, i.e. predictive accuracy, distillation efficiency, and data compression rates.", "weaknesses": "1. Unlike DOSCOND and KIDD, MIRAGE seems infeasible to be generalized to node classification tasks.\n\n2. There is no theoretical analysis nor experimental proof to investigate the error when approximating the true graph representation by aggregating the root representations of only the highly frequent trees.\n\n3. MIRAGE compresses the computation trees by mining the set of frequently co-occurring items. However, we can consider an extreme situation in which two computation trees are co-occurring in all graphs, but their frequencies in each graph are very low. So, these trees can’t approximate the true graph representation, which will destroy the synthetic dataset performance.\n\n4. The synthetic dataset can solely be used to train GNNs based on the message-passing framework, but can’t used to train certain spectral GNNs, such as ChebyNet with multiple propagation steps.", "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": "FFEqsQNz5f", "reviewer": "Reviewer_XL6A", "summary": "This paper introduces a graph classification model called MIRAGE, which is a graph distillation method based on frequent pattern mining. MIRAGE takes advantage of the design features of the message passing framework, decomposes the graph into calculation trees, and uses the distribution characteristics of the calculation tree to compress calculation data. Compared with existing graph distillation algorithms, MIRAGE shows advantages in key indicators such as prediction accuracy, distillation efficiency, and data compression rate. Furthermore, MIRAGE only relies on CPU operations, providing a more environmentally friendly and energy-efficient graph distillation method.", "questions": "1. Would MIRAGE still be as effective if used on a very large data set?\n2. Why is MIRAGE, which only uses the CPU, so much faster than DOSCOND and KIDD, which can use the GPU?\n3. If a datasets is large, but its global computation tree is very similar, will such a datasets affect the effect of MIRAGE?\n4. How will MIRAGE perform in multi-classification tasks?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. It is a novel idea to transform the graph distillation problem into the problem of graph decomposition.\n2. This paper clearly expresses the distillation problem in mathematical language and naturally transforms it into a graph decomposition problem.\n3. The experimental configuration is described in detail, and the experimental results are good and reasonable.", "weaknesses": "1. The datasets used in the experiment is too small.", "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)