Graph Condensation for Graph Neural Networks
Authors: Wei Jin
Lingxiao Zhao
Shichang Zhang
Yozen Liu
Jiliang Tang
Neil Shah
Venue: ICLR 2022 Poster (2022)
Keywords: data-efficient learning
graph generation
graph neural networks

Abstract: Given the prevalence of large-scale graphs in real-world applications, the storage and time for training neural models have raised increasing concerns. To alleviate the concerns, we propose and study the problem of graph condensation for graph neural networks (GNNs).  Specifically, we aim to condense the large, original graph into a small, synthetic and highly-informative graph, such that GNNs trained on the small graph and large graph have comparable performance. We approach the condensation problem by imitating the GNN training trajectory  on the original graph through the optimization of a gradient matching loss and design a strategy to condense node futures and structural information simultaneously. Extensive experiments have demonstrated the effectiveness of the proposed framework in condensing different graph datasets into informative smaller graphs. In particular, we are able to approximate the original test accuracy by 95.3\% on Reddit, 99.8\% on Flickr and 99.0\% on Citeseer,  while reducing their graph size by more than 99.9\%, and the condensed graphs can be used to train various GNN architectures. 

Published as a conference paper at ICLR 2022
GRAPH CONDENSATION FOR GRAPH NEURAL NET- WORKS
Wei Jin
Lingxiao Zhao
Shichang Zhang
Michigan State University iinei22@mu..
Carnegie Mellon University lingxi coocmmeede
UCLA sh i chrcchnngess.cco ucla edu
Yozen Liu
Jiliang Tang
Neil Shah Snap Inc. nshahe snap com
Snap Inc.
Michigan State University tang immsu. edu
yliu2esnap.com com
ABSTRACT
Given the prevalence large-scale graphs in real-world applications, the stor- age and time for training neural models have raised increasing concerns. To alleviate the concerns, we propose and study the problem of graph condensa- tion for graph neural networks (GNNs). Specifically, we aim to condense the large, original graph into a small, synthetic and highly-inforrnttve graph, such that GNNs trained on the small graph and large graph have comparable perfor- mance. We approach the condensation problem by imitating the GNN training trajectory the original graph through the optimization of gradient match- ing loss and design a strategy to condense node features and structural infor- mation simultaneously. Extensive experiments have demonstrated the effective- ness of the proposed framework in condensing different graph datasets into in- formative smaller graphs. In particular, we are able to approximate the orig- inal test accuracy by 95.3% on Reddit, 99.8% on Flickr and 99.0% on Cite- seer, while reducing their graph size by more than 99.9%, and the condensed graphs can be used to train various GNN architectures. Code is released at https: htttttgtthhuh//e
INTRODUCTION
Many real-world data can be naturally represented graphs such social networks, chemical molecules, transportation networks, and recommender systems (Battaglia et al., 2018; Wu et al., 2019b; Zhou et al., 2018). As generalization of deep neural networks for graph-structured data, graph neural networks (GNNs) have achieved great success in capturing the abundant information residing in graphs and tackle various graph-related applications (Wu et al., 2019b; Zhou et al., 2018).
However, the prevalence of large-scale graphs in real-world scenarios, often on the scale of millions of nodes and edges, poses significant computational challenges for training GNNs. More dramat- ically, the computational cost continues to increase when we need to retrain the models multiple times, e.g., under incremental learning settings, hyperparameter and neural architecture search. To address this challenge, a natural idea is to properly simplify, or reduce the graph so that we can only speed up graph algorithms (including GNNs) but also facilitate storage, visualization and retrieval for associated graph data analysis tasks.
There are two main strategies simplify graphs: graph sparsification (Peleg & Schäffer, 1989; Spielman & Teng, 2011) 1) and graph coarsening (Loukas & Vandergheynst, 2018; Loukas, 2019) Graph sparsification approximates a graph with sparse graph by reducing the number of edges, while graph coarsening directly reduces the number of nodes by replacing the original node set with its subset. However, these methods have some shortcomings: (1) sparsification becomes much less promising in simplifying graphs when nodes are also associated with attributes sparsification does not reduce the node attributes; (2) the goal of sparsification and coarsening is to preserve some graph
Work done while author on internship Snap Inc.

---

Published as a conference paper at ICLR 2022
(A
(A', ("))
Tast accuracies
Test accuracles GON: 89, 4%
GCN: 93.9%
Condense
S6C: 93.5%
88 APPNP: 87.5%
APPNP: 94.3%
GraphSAGE:
GraphSAGE: 99.2%
153,992 training nodes
154 training nodes
We study the graph condensation problem, which seeks to learn small, synthetic graph, features and labels (A', Y"} from a large, original dataset {A, X, Y), which can be used to train GNN models that generalize comparably to the original. Shown: An illustration of our proposed GCOND graph condensation approach's 's empirical performance, which exhibits 95.3% % of original graph test performance with 99.9% data reduction.
Figure 1:
properties such as principle eigenvalues (Loukas & Vandergheynst, 2018) that could be not optimal for the downstream performance of GNNs. In this work, we ask if it is possible to significantly reduce the graph size while providing sufficient information well train GNN models.
Motivated by dataset distillation (Wang et al., 2018) and dataset condensation (Zhao et al., 2021) which generate small set of images train deep neural networks the downstream task, aim to condense a given graph through learning synthetic graph structure and node attributes. Correspondingly, we propose the task of graph condensation'. It aims minimize the performance gap between GNN models trained on a synthetic, simplified graph and the original training graph. In this work, we focus on attributed graphs and the node classification task. We show that we are able to reduce the number of graph nodes to as low as 0.1% while training various GNN architectures to reach surprisingly good performance on the synthetic graph. For example, Figure I, we condense the graph of the Reddit dataset with 153,932 training nodes into only 154 synthetic nodes together (1) how to formulate the objective for graph condensation tractable for learning; and (2) how parameterize the to-be-learned node features and graph structure. To address the above challenges, we adapt the gradient matching scheme in (Zhao al., 2021) and match the gradients of GNN parameters w.r.t. the condensed graph and original graph. In this way, the GNN trained on condensed graph can mimic the training trajectory of that on real data. Further, we carefully design the strategy for parametrizations for the condensed graph. In particular, we introduce the strategy of parameterizing the condensed features as free parameters and model the synthetic graph structure as function of features, which takes advantage of the implicit relationship between structure and node features, consumes less number of parameters and offers better performance.
with their connections. In essence, we face two challenges for graph condensation:
Our contributions can be summarized as follows:
We make the first attempt to condense a large-real graph into small-synthetic graph, such that the GNN models trained on the large graph and small graph have comparable performance. We introduce a proposed framework for graph condensation (GConD) which parameterizes the con- densed graph structure function of condensed node features, and leverages gradient match- ing loss as the condensation objective.
2. Through extensive experimentation, datasets and achieve comparable performance to their larger counterparts. For instance, GCOND approximates the original test accuracy by 95.3% on Reddit, 99.8% on Flickr and 99.0% on Cite- seer, while reducing their graph size by more than 99.9%. Our approach consistently outperforms coarsening, coreset and dataset condensation baselines.
show that GCOND is able to condense different graph
3. We show that the condensed graphs can generalize well to different GNN test models. Addition- ally, we observed reliable correlation performances between condensed dataset training and whole-dataset training in the neural architecture search (NAS) experiments.
RELATED WORK
Dataset Distillation & Condensation. Dataset distillation (DD) (Wang et al., 2018; Bohdal al., 2020; Nguyen et al., 2021) aims to distill knowledge of a large training dataset into small synthetic
We aim condense both graph structure and node attributes. formal definition is given in Section 3.
2

---

Published as a conference paper at ICLR 2022
dataset, such that model trained on the synthetic set is able obtain the comparable performance to that of a model trained on the original dataset. To improve the efficiency of DD, dataset conden- sation (DC) (Zhao et al., 2021; Zhao & Bilen, 2021) is proposed to learn the small synthetic dataset by matching the gradients of the network parameters w.r.f. large-real and small-synthetic training data. However, these methods are designed exclusively for image data and are not applicable to non-Euclidean graph-structured data where samples (nodes) are interdependent. In this work, we generalize the problem of dataset condensation to graph domain and we seek to jointly learn the synthetic node features as well as graph structure. Additionally, our work relates to coreset meth- ods (Welling, 2009; Sener & Savarese, 2018; Rebuffi et al., 2017), which seek to find informative samples from the original datasets. However, they rely on the presence of representative samples, and tend to give suboptimal performance.
Graph Sparsification & Coarsening. Graph sparsification and coarsening are two means of reduc- ing the size of a graph. Sparsification reduces the number of edges while approximating pairwise distances (Peleg & Schäffer, 1989), cuts (Karger, 1999) eigenvalues (Spielman & Teng, 2011) while coarsening reduces the number of nodes with similar constraints (Loukas & Vandergheynsl, 2018; Loukas, 2019; Deng et al., 2020), typically by grouping original nodes into super-nodes, and defining their connections. Cai et al. (2021) proposes a GNN-based framework to learn these con- nections improve coarsening quality. Huang al. (2021b) adopts coarsening as a preprocessing method to help scale up GNNs. Graph condensation also aims to reduce the number of nodes, but aims learn synthetic nodes and connections in supervised way, rather than unsupervised group- ing as in these prior works. Graph pooling is also related to our work, but it targets at improving graph-level representation learning (see Appendix D).
Graph Neural Networks. Graph neural networks (GNNs) are a modern way to capture the intuition that inferences for individual samples (nodes) can be enhanced by utilizing graph-baat bash- information from neighboring nodes (Kipf& & Welling, 2017; Hamilton et al., 2017; Klicpera et al., 2019; Velick- ovic et al., 201 88; Wu et al., 2019b;a; Liu et al., 2020; 2021; You et al., 2021; Zhou et al., 2021; Zhao et al., 2022). Due to their prevalence, various real-world applications have been tremendously fa- cilitated including recommender systems (Ying et al., 20180 Sa; Fan et al., 2019), computer vision (Li et al., 2019) and drug discovery (Duvenaud et al., 2015).
Graph Structure Learning. Our work is also related to graph structure learning, which explores methods to learn graphs from data. One line of work (Dong et al., 2016; Egilmez et al., 2017) learns graphs under certain structural constraints (e.g. sparsity) based on graph signal processing. Recent efforts aim learn graphs by leveraging GNNs (Franceschi et al., 2019; Jin et al., 2020; Chen al., 2020). However, these methods are incapable of learning graphs with smaller size, and are thus not applicable for graph condensation.
METHODOLOGY
In this section, we present our proposed graph condensation framework, GCOND. Consider that we have a graph dataset T= (A, X, Y), where A E - is the adjacency matrix, N is the number of nodes, X E R. N is the d-dimensional node feature matrix and Y E (O...., C' - 1] denotes the node labels over C. classes. Graph condensation aims to learn a small, synthetic graph dataset = (A', X', Y') with A' E V''' X' E N'D Y' E (O...., C C-1] 1] and N' & N, such that a GNN trained on S can achieve comparable performance to one trained on the much larger T. Thus, the objective can be formulated as the following bi-level problem.
min L (GNNg3 (A,X) X), Y) s.t 0g = arg min (A', Y'),
(I)
S
where GNNo denotes the GNN model parameterized with 0, Ag denotes the parameters of the model trained on S, and L denotes the loss function used measure the difference between model predictions and ground truth, i.c. cross-entropy loss. However, optimizing the above objective can lead to overfitting on a specific model initialization. To generate condensed data that generalizes to a distribution of random initializations Po.. we rewrite the objective as follows:
min Eg,-Pa, [c (GNN,, (), Y)] s.t. 0s = arg min L(GNN (A', Y'). (2)
where 0 ((0)) indicates that 0 is function acting Oy. Note that the setting discussed above is for inductive learning where all the nodes are labeled and test nodes are unseen during training. We can easily generalize graph condensation to transductive setting by assuming Y is partially labeled.
3

---

Published as a conference paper at ICLR 2022
3.1 GRAPH CONDENSATION VIA GRADIENT MATCHING
To tackle the optimization problem in Eq. (2), one strategy is to compute the gradient of & w.r.t S and optimize S via gradient descent, as in dataset distillation (Wang et al., 2018). However, this requires solving nested loop optimization and unrolling the whole training trajectory of the inner problem, which can be prohibitively expensive. To bypass the bi-level optimization, we follow the gradient matching method proposed in (Zhao et al., 2021) which aims to match the network parameters w.r.. large-real and small synthetic training data by matching their gradients at each training step. this way, the training trajectory on small- synthesytttticc data S can mimic that on the large-real data T, i.e., the models trained on these two datasets converge to similar solutions (parameters). Concretely, the parameter matching process for GNNs can be modeled as follows:
ming Ego-Po Peo (A', (A', X'), ))) and 0 opta (- (A.N)
En D 0 .0?
with
(3)
opto 0--1=000 opto (c (c (GNNN
(A,
where -): is a distance function, T' is the number of steps of the whole training trajectory, opty is the update rule for model parameters, and 0 07 denote the model parameters trained on and T at time step I, respectively. Since our goal is to match the parameters step by step, we then consider one-step gradient descent for the update rule opts:
0 t 0 Vo (GNNøg (A', (A', (A', Y')
and 0 07 0, vVV (GNNo? X), Y
(4)
where 77 is the learning rate for the gradient descent. Based on the observation made in Zhao et al. (2021) that the distance between 0₂ and 0² is typically small, we can simplify the objective gradient matching process as follows,
Σ DVOL (A', Y') VoL (GNNo, (A, X), Y))
min EO Peu
(5)
where o and 0² are replaced by 0,. which is trained on the small-synthetic graph. The distance D further defined as the sum of the distance dis at each layer. Given two gradients G R4 and GT E IRd xd2 at a specific layer, the distance dis(:)) -) used for condensation is defined as follows,
(
de
G.S. G.
(is (G) - -
G |
where G G. are the i-th column vectors of the gradient matrices. With the above formulations, we are able to achieve parameter matching through an efficient strategy of gradient matching.
We note that jointly learning the three variables A', X' and Y' is highly challenging, they interdependent. Hence, to simplify the problem, we fix the node labels Y' while keeping the class distribution the same the original labels Y.
Graph Sampling. GNNs are often trained in a full-batch manner (Kipf & Welling, 2017; Wu al., 2019b). However, suggested by previous works that reconstruct data from gradients (Zhu et al, 2019), large batch size tends to make reconstruction more difficult because more variables are involved during optimization. To make things worse, the computation cost of GNNs gets expensive on large graphs as the forward pass of GNNs involves the aggregation of enormous neighboring nodes. To address the above issues, we sample a fixed-size set of neighbors on the original graph in each aggregation layer of GNNs and adopt mini-batch training strategy. To further reduce memory usage and ease optimization, we calculate the gradient matching loss for nodes from different classes separately, as matching the gradients w.r.t. the data from single class is easier than that from all classes. Specifically, for a given class e, we sample a batch of nodes of class e together with a portion of their neighbors from large-real data T. We denote the process For the condensed graph A', we sample a batch of synthetic nodes of class c but do not sample their neighbors. In other words, use all of their neighbors, i.e., all other nodes, during the aggregation process, since we need to learn the connections with other nodes. We denote the process (A X Y!) S.
(Ac; X., Y.) T.
3.2
MODELING CONDENSED GRAPH DATA
One essential challenge in the graph condensation problem is how to model the condensed graph data and resolve dependency among nodes. The most straightforward way is to treat both A' and X'
4

---

Published as a conference paper at ICLR 2022
as free parameters. However, the number of parameters in A' grows quadratically as N' increases. The increased model complexity can pose challenges in optimizing the framework and increase the risk of overfitting. Therefore, it is desired to parametrize the condensed adjacency matrix in way where the number of parameters does not grow too fast. On the other hand, treating A' and X' as independent parameters overlooks the implicit correlations between graph structure and features, which have been widely acknowledged in the literature (IIII et al., 2014; Shalizi & Thomas, 2011); e.g., in social networks, users interact with others based on their interests, while in e-commerce, users purchase products due to certain product attributes. Hence, we propose to model the condensed graph structure as a function of the condensed node features:
with A = Sigmoid MMLP (xx x,D) + MLP (X/)
A' = I (X'),
where MLPs is multi-layer neural network parameterized with + and [:3-]] denotes concatenation. In Eq. (7), we intentionally control A = A to make the condensed graph structure symmetric since we are mostly dealing with symmetric graphs. It can also adjust to asymmetric graphs by setting A = (MLLo ([x;;
x4D). Then we rewrite our objective as
T-1 Σ
min E Peo X'
D DVVoL (GNNo, (X),, X'), Y"), V (GNNo, (A, Y))
(8)
1=
Note that there are two clear benefits of the above formulation over the naïve one (free parameters). Firstly, the number of parameters for modeling graph structure no longer depends on the number of nodes, hence avoiding jointly learning ( parameters; as result, when N' gets larger, GCOND suffers less risk of overfitting. Secondly, if we want to grow the synthetic graph by adding more synthetic nodes condensed from real graph, the trained MLP2 can be employed to infer the connections of new synthetic nodes, and hence only need to learn their features.
Alternating Optimization Schema. Jointly optimizing X' and is often challenging as they are directly affecting each other. Instead, we propose alternatively optimize X' and Φ: we update & for the first т₁ epochs and then update X' for 72 epochs; the process is repeated until the stopping find empirically that this does better shown in Appendix C.
condition is met
Sparsification. In the learned condensed adjacency matrix A', there can exist some small values which have little effect the aggregation process in GNNs but still take up certain amount of storage (e.g. bytes per float). Thus, we remove the entries whose values are smaller than a given threshold 8 to promote sparsity of the learned A'. We further justify that suitable choices of 8 for sparsification do not degrade performance a lot in Appendix C.
The detailed algorithm can be found in Algorithm in Appendix B. In detail, first set the con- densed label set Y' to fixed values and initialize X' as node features randomly selected from each class, In each outer loop, we sample GNN model initialization from distribution Pe. Then, for each class we sample the corresponding node batches from T and S, and calculate the gradient matching loss within each class. The sum of losses from different classes are used to update X' or Q. After that we update the GNN parameters for To epochs. When finishing the updating of condensed graph parameters, we use A' ReLU(go (X)) - 5) to obtain the final sparsified graph structure.
A "Graphless" Model Variant. We now explore another parameterization for the condensed graph data. We provide a model variant named GCOND-X that only learns the condensed node features X' without learning the condensed structure A'. In other words, we use fixed identity matrix I as the condensed graph structure. Specifically, this model variant aims to match the gradients of GNN parameters the large-real data X) and small-synteetic data (I, X'). Although GCOND-X is unable to learn the condensed graph structure which can be highly useful for downstream data analysis, it still shows competitive performance in Table in the experiments because the features are learned to incorporate relevant information from the graph via the matching loss.
EXPERIMENTS
In this section, we design experiments to validate the effectiveness of the proposed framework GCOND. We first introduce experimental settings, then compare GCOND against representative baselines with discussions and finally show some advantages of GCOND.
5

---

Published as a conference paper at ICLR 2022
4.1 EXPERIMENTAL SETUP
Datasets. We evaluate the condensation performance of the proposed framework on three transduc- tive datasets, i.c., Cora, Citeseer (Kipf & Welling, 2017) and Ogbn-arxiv (Hu et al., 2020), and two inductive datasets, i.e., Flickr (Zeng et al,, 2020) and Reddit (Hamilton et al., 2017). We use the pub- lic splits for all the datasets. For the inductive setting, we follow the setup in (Hamilton et al., 2017) where the test graph is not available during training. Dataset statistics are shown in Appendix A.
Baselines. We compare our proposed methods to five baselines: (i) one graph coarsening method (Loukas, 2019; Huang et al., 2021b), (ii-iv) three coreset methods (Random, Herd- ing (Welling, 2009) and K-Center (Farahani & Hekmatfar, 2009; Sener Savarese, 2018)), and (v) dataset condensation (DC). For the graph coarsening method, we adopt the variation neighbor- hoods method implemented by Huang et al. (2021b). For coreset methods, we first use them to select nodes from the original dataset and induce subgraph from the selected nodes serve the reduced graph. In Random, the nodes are randomly selected. The Herding method, which is often used in continual learning (Rebuffi et al., 2017; Castro et al., 2018), picks samples that are closest to the cluster center. K-Center selects the center samples to minimize the largest distance between sample and its nearest center. We use the implementations provided by Zhao et al. (2021) for Herding, K- K-Center and DC. As vanilla DC cannot leverage any structure information, we develop a variant named DC-Graph, which additionally leverages graph structure during test stage, to replace DC for the following experiments. A comparison between DC, DC-Graph, GCOND and GCOND-X shown in Table and their training details can be found in Appendix A.3.
Evaluation. We first use the aforementioned baselines to obtain condensed graphs and then eval- uate them on GNNs for both transductive and inductive node classification tasks. For transductive datasets, we condense the full graph with N nodes into synthetic graph with rN (0 < < 1) nodes, where r is the ratio of synthetic nodes to original nodes. For inductive datasets, we only condense the training graph since the rest of the full graph is not available during training. The choices of r are listed in Table 2. For each r, we generate 5 condensed graphs with different seeds. To evaluate the effectiveness of condensed graphs, we have two stages: (1) training stage, where we train a GNN model on the condensed graph, and (2) a test stage, where the trained GNN uses the test graph (or full graph transductive setting) to infer the labels for test nodes. The resulting test performance is compared with that obtained when training on original datasets. All experiments are repeated 10 times, and we report average performance and variance.
Hyperparameter settings. As our goal is to generate highly informative synthetic graphs which can benefit GNNs, we choose one representative model, GCN (Kipf & Welling, 2017). for performance evaluation. For the GNN used in condensation. i.c., the G-N in Eq. (8), we adopt SGC (Wu et al., 2019a) which decouples the propagation and transformation process but still shares similar graph filtering behavior as GCN. Unless otherwise stated, we use 2-layer models with 256 hidden units. The weight decay and dropout for the models are set to in condensation process. More details for hyper-parameter tuning can be found in Appendix A.
4.2 COMPARISON WITH BASELINES
In this subsection, test the performance of a 2-layer GCN the condensed graphs, and compare the proposed GCOND and GCOND-X with baselines. Notably, all methods produce both structure and node features, i.e. A' and X', except DC-Graph and GCOND-X. Since DC-Graph and GCOND- x do not produce any structure, we simply use an identity matrix as the adjacency matrix when training GNNs solely on condensed features. However, during inference, we use the full graph (transductive setting) or test graph (inductive setting) to propagate information based on the trained GNNs. This training paradigm is similar to the C&S model (Huang et al., 2021a) which trains an MLP without the graph information and performs label propagation based on MLP predictions. Table 2 reports node classification performance; we make the following observations:
Obs 1. Condensation methods achieve promising performance even with extremely large re- duction rates. Condensation methods, i.e., GCOND, GCOND-X x and DC-Graph, outperform coreset methods and graph coarsening significantly at the lowest ratio for each dataset. This shows the importance of learning synthetic data using the guidance from downstream tasks. Notably, GCOND
We determine based original graph size and labeling rate see Appendix A for details.

---

Published as a conference paper at ICLR 2022
Table 1: Information comparison used during condensation, training and test for reduction methods. A X' and A, X are condensed (original) graph and features, respectively.
DC
DC-Graph
GCOND-X
GCOND
Condensation
X
train
Xuain
Arain Xusin
A Arain Xuai
Training
X'
X'
X'
A' Aust, Xasst
Test
X
Auss, Xee
Aust, X
Table 2: GCOND and GCOND-X x achieves promising performance in comparison to baselines even with extremely large reduction rates. We report transductive performance on Citeseer, Cora, Ogbn- arxiv; inductive performance on Flickr, Reddit. Performance is reported as test accuracy (%).
Baselines
Proposed
Random (A' X')
Herding (A' X')
K-Center (A'
Crarsening (A',x')
DC-Gmph (X')
GCOND-X (X')
GCOND (A'X'))
Dataset
Ratio (r)
Datasct
0.9%
57.1+15 54.44444
52. 22.8
52.240.4
66.841.5
71.4+0.8
70.5+11.2
Citeseer
1.8%
6..2.11.77
66.711.0
64.311.0
59.010.5
66.910.9
69.811.11
70.6100.
71.7.10.1
3.6%
69.110.11
60.020.11
69.120.1
65.310.5
66.311.5
69.411..4
69.8
1.3%
63.6133.7
67.01:..
64.012.33
31.210.2
67.311.9
75.91112
7..8
Cora
2.6%
1.18:11.1
1.0
7.2
65.21006
67.613.5
75.71:0.9
80.1.:06
81.220.2
5.2%
76.8+00.1 1
76.8:0.11
76.7#0.1
70.6:0.1
67.722.2
76.0#0.9
79.3=0.3
0.05%
17.19:3.9
52.411.8
47.233.0
35.410..3
58.610.44
61.310.5
59.211.11
Ogbn-anxiv
0.25%
57.3411.1
58.6 1.2
56.820.8
43.5.10.2
59.910.3
64.240.4
63.24.,33
71.4#0.1
0.5%
60.0.10.9
60.410.8
60.310.4
50.410.1
59.510.3
63.110.5
64.0.0..4
1::2000
42.5118
42.0
41.910.2
46.310.2
45.910.11
48.510.4
Flickr
0.5%
44.0.10.4
43.91.0.9
43.210.1
44.510.11
45.910.1
45.010.2
47.1
47.210.1
1%
44.640.2
44.4200.6
44.1
44.620.1
45.840.1
45.040.1
47.120.1
0.05%
46. 16.1444,4
13.1
46.612.3
40.910.5
88.210.2
88.410.44
88.011.8
Reddit
0.1%
58.0:22.2
1.0
53.043.3
42.810.8
89.510..1
80.310.11
89.6-0.7
93.920.0
0.2%
66.3+:1.9
71.0=116
58.5+2.1
47.4
90.5+112
88.840.4
90.1
achieves 79.8%, 80.1% % and 79.3% at 1.3%, 2.6% and 5.2% condensation ratios at Cora, while the whole dataset performance is 81.2%. The GCOND variants also show promising performance on Cora, Flickr and Reddit at all coarsening ratios. Although the gap between whole-datased Ogbn-arxiv and our methods is larger, they still outperform baselines by a large margin.
Obs 2. Learning X' instead of (A', X') as the condensed graph can also lead to good results. GCOND-X achieves close performance to GCOND on 11 of cases. Since our objective in graph condensation is to achieve parameter matching through gradient matching, training GNN on the learned features X' with identity adjacency matrix is also able to mimic the training trajectory of GNN parameters. One reason could be that X' has already encoded node features and structural in- formation of the original graph during the condensation process. However, there are many scenarios where the graph structure is essential such the generalization to other GNN architectures (e.g., GAT) and visualizing the patterns in the data. More details are given in the following subsections.
Obs 3. Condensing node features and structural information simultaneously can lead to better performance. In most cases, GCOND and GCOND-X obtain much better performance than DC- Graph. One key reason is that GCOND and GCOND-X can take advantage of both node features and structural information in the condensation process. We notice that DC-Graph achieves highly comparable result (90.5%) (93.9%). This may indicate that the original training graph structure might not be useful. To verify this assumption, we train a GCN on the original Reddit dataset without using graph structure (i.e., setting A main = I), but allow using the test graph structure for inference using the trained model. The obtained performance is 92.5%, which is very close to the original performance 93.9%, indicating that training without graph structure can still achieve comparable performance. We also note that learning X', A' simultaneously creates opportunities to absorb information from graph structure directly into learned features, lessening reliance distilling graph properties reliably while still achieving good generalization performance from features.
Reddit 0.2% condensation ratio the whole dataset performance
Obs 4. Larger condensed graph size does not strictly indicate better performance. Although larger condensed graph sizes allow for more parameters which can potentially encapsulate more information from original graph, it simultaneously becomes harder optimize due the increased

---

Published as a conference paper at ICLR 2022
Table Graph condensation can work well with different architectures, Avg. stands for the average test accuracy of APPNP, Cheby, GCN, GraphSAGE and SGC. SAGE stands for GraphSAGE.
Methods
Data
MLP
GAT
APPNP
Cheby
GCN
SAGE
SGC
Avg.
DC-Grraph
X
66.2
66.4
66.2
65.9
69.6
66.6
Citeseer
1.8%
GCOND-X
X
69.6
69.7
70.6
69.7
69.2
71.6
70.2
GCOnd
A x
63.9
55.4
69.6
68.3
70.5
66.2
70.3
69.0
Cora
DC Grapr
x'
67.2
67.1
67.7
67.9
66.2
72.8
68.3
2.6%
GCOND-X
GCOND
A' x'
X
73.1
76.0
66.2
78.5
77.0
76.0
74.1
80.1
75.3
78.2
76.0
79.3
76.1
78.4
75.7
Ogbn-andvv 0.25%
DC DC-Graph
X'
59.9
59.8
60.0
60.4
GCOND-X
X"
61.1
61.5
59.5
64.22
64.4
64.7
62.9
GCOND
A x
62.2
60.0
63.4
54.9
63.2
62.6
63.7
61.6
DC-Graph
X'
43.1
45.7
43.8
45.9
45.8
45.6
45.4
Flickr
0.5%
GCOND-X
x'
42.1
44.6
42.3
45.0
44.7
44.4
44.2
GCOND
A' x'
44.8
40.1
45.9
42.8
47.1
46.2
46.1
45.6
Reddit
DC-Graph GCOND-X
X'
50.3
81.2
77.5
89.5
89.7
90.5
86.7
0.1%
X'
40.1
78.7
74.0
89.3
89.3
91.0
84.5
GCOND
A', X'
42.5
60.2
87.8
75.5
89.4
89.1
89.6
86.3
model complexity. We observe that once the condensation ratio reaches certain threshold, the performance becomes stable. However, the performance of coreset methods and graph coarsening much more sensitive to the reduction ratio. Coreset methods only select existing samples while graph coarsening groups existing nodes into super nodes. When the reduction ratio too low, becomes extremely difficult to select informative nodes or form representative super nodes by grouping.
4.3 GENERALIZABILITY OF CONDENSED GRAPHS
Next, we illustrate the generalizability of condensed graphs from the following three perspectives.
Different Architectures. Next, we show the generalizability of the graph condensation proce- dure. Specifically, we show test performance when using a graph condensed by one GNN model to train different GNN architectures. Specifically, we choose APPNP (Klicpera et al., 2019), GCN, SGC (Wu et al., 2019a), GraphSAGE (Hamilton et al., 2017), Cheby (Defferrard et al., 2016) and GAT (Velickovic et al., 2018). We also include MLP and report the results in Table 3. From the ta- ble, we find that the condensed graphs generated by GCOND show good generalization on different architectures. We may attribute such transferability across different architectures similar filtering behaviors of those GNN models, which have been studied in Ma et al. (2020); Zhu et al. (2021).
Versatility of GCOND. The proposed GCOND is highly composable in that GNNs inside the condensation network. We investigate the performances of various GNNs when us- ing different GNN models in the condensation process, i.e., GNNa(-) in Eq. (8). We choose APPNP, Cheby, GCN, GraphS and SGC to serve as the models used in condensation and evaluation. Note that we omit GAT due its deterioration under large neighborhood sizes (Ma et al., 2021). We choose Cora and Ogbn-arxiv to report the performance in Table 4 where C and T denote con- densation and test models, respectively. The graphs condensed by different GNNs all show strong transfer performance on other architectures.
adopt various
Neural Architecture Search. We also perform experiments on neural architecture search, detailed in Appendix C.2. We search 480 architectures of APPNP and perform the search process on Cora, Citeseer and Ogbn-arxiv. Specifically, we train each architecture on the reduced graph for epochs on as the model converges faster the smaller graph. We observe reliable correlation of performances between condensed dataset training and whole-dataset training as shown in Table 9: 0.76/0.79/0.66 for BaraaCiiteeer/Ogonnarae
4.4 ANALYSIS ON CONDENSED DATA
Statistics of Condensed Graphs. In Table 5, we compare several properties between condensed graphs and original graphs. Note that widely used homophily measure is defined in (Zhu et al., 2020) but does not apply to weighted graphs. Hence, when computing homophily, we binarize the graphs by removing edges whose weights are smaller than 0.5. We make the following observations. First, while achieving similar performance for downstream tasks, the condensed graphs contain fewer nodes and take much less storage. Second, the condensed graphs are less sparse than their
8

---

Published as a conference paper at ICLR 2022
Table
performance is shown in test accuracy (%). SAGE: GraphSAGE. Graphs
condensed by different GNNs all show strong transfer performance on other architectures.
(a) Cora, r=2.6%
(b) agbn-arxivv r=0.0%
CXT
APPNP
Cheby
GCN
SAGE
SGC
CVT
APPNP
Cheby
GCN
SAGE
SGC
APPNP
72.142.6
60.826.4
73.542.4
72.343.5
73.143.1
APPNP
60.3+0.2
51.840.5
50.9=0.4
19.0+1.1
61.2=0.44
Cheby
75.3#2.9
71.81.1
76 8+2.1
76.4+2.0
75.5+3.5
Cheby 57.4+0.4
53.5+0.5
57.4=0.8
57.1
58 2
OCN
69.814.0 53.243.4
70.643.7
60.24199
68.7
GCN 59.310.4
51.840.7
60.340.3
60.2:0.4
59.240.7
SAGE
77.111.1 69.311.7
77.010.7
77.711. 76.110.77
SAGE 57.6.00.8
53.910.6
58.1.00.6
57.8.0.7
59.01111
78.541.0
76.041.1
80.120.6
78.240.9 79.340.7
59.740.5
49.540.8
50.221.1
58.941.6 60.540.6
Table 5: Comparison between condensed graphs and original graphs. The condensed graphs have
fewer nodes and are more dense.
Citeseer, r=0.%%
Cora, r=1.3%
|Ogbn- r=0.25%|
Flickr, r-0.5%
Reddit, r=0.1%
Whole
GCOND
Whole
GCOND
Whole
GCOND
Whole
GCOND
Whole
GCOND
Accuracy
70.7
70.5
81.5
79.8
71.4
63.2
47.1
47.1
94.1
89.4
#Nodes
3.327
2,708
70
169,343
454
44,625
223
153,932
153
HEdges
4,732
1,454
5,429
2,128
1,166,243
3,354
218,140
1,788
10.753,238
301
Spansity
3.25%
0.02%:
Homoptily
0.74
0.65
0.81
0.79
0.65
0.07
0.33
0.28
0.78
0.04
Storage
47.1 MB
0.9 MB
14.9 MB
0.4 MB
100.4 MB
0.3 MB
86.8 MB
0.5 MB
435.5 MB
0.4 MB
(a) Cora, r=2.5% (b) Citeseer, r=1.8% (c) Arxiv, 00005% (d) Flickr, r=0.1
(e) Reddit, r=0.1%
Figure 2: Condensed graphs sometimes exhibit structure mimicking the original (a, b, d). Other
times (c, e), learned features absorb graph properties and create less explicit graph reliance.
larger counterparts. Since the condensed graph on extremely small scale, there would be almost no connections between nodes if the condensed graph maintains the original sparsity. Third, for Citeseer, Cora and Flickr, the homophily information are well preserved in the condensed graphs.
Visualization. We present the visualization results for all datasets in Figure 4, where nodes with the same color are from the same class. Notably, as the learned condensed graphs are weighted graphs, use black lines to denote the edges with weights larger than 0.5 and gray lines to denote the edges with weights smaller than 0.5. From Figure 4, we can observe some patterns in the con- densed graphs, e.g., the homophily patterns the learned graph for Reddit is very close to a star graph where almost all the nodes only have con- nections with very few center nodes. Such structure can be meaningless for GNNs because almost all the nodes receive the information from their neighbors. In this case, the learned features X' play major role in training GNN parameters, indicating that the original training graph of Reddit not very informative, aligning with our observations in Section 4.2.
Cora and Citeseer
well preserved. Interestingly,
CONCLUSION
The prevalence of large-scale graphs poses great challenges in training graph neural networks. Thus, we study novel problem of graph condensation which targets at condensing a large-real graph into a small-synthetic one while maintaining the performances framework, we are able to significantly reduce the graph size while approximating the original per- formance. The condensed graphs take much less space of storage and can be used to efficiently train various GNN architectures. Future work can be done on (1) improving the transferability of condensed graphs for different GNNs, (2) studying graph condensation for other tasks such as graph classification and (3) designing condensation framework for multi-label datasets.
GNNs. Through our proposed

---

Published as a conference paper at ICLR 2022
ACKNOLWEDGEMENT
Wei Jin and Jiliang Tang are supported by the National Science Foundation (NSF) under grant num- bers IIS1714741, CNS1815636, IIS IIS1845081, IIS1907704, IIS IIS1928278, IIS1955285, I0$2107215, and IOS2035472, the Army Research Office (ARO) under grant number INF-2111-0119, the Home Depot, Cisco Systems Inc. and SNAP Inc.
ETHICS STATEMENT
To the best of our knowledge, there no ethical issues with this paper.
REPRODUCIBILITY STATEMENT
To ensure reproducibility of experiments, provide our source code https: / ////ttttttt github. com/
The parareparameters are described in details in the appendix. We also provide pseudo-code implementation of our framework in the appendix.
REFERENCES
Peter W Battaglia, Jessica B Hamrick. Victor Bapst, Alvaro
Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. ArXiv preprint, 2018.
Ondrej Bohdal, Yongxin Yang, and Timothy Hospedales. Flexible dataset distillation: Learn labels instead of images. ArXiv preprint, 2020.
Chen Cai, Dingkang Wang, and Yusu Wang. Graph coarsening with neural networks. In 9th Inter- national Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021.
Francisco M Castro, Manuel Marín-Jiménez, Nicolás Guil, Cordelia Schmid, and Karteek Alahari. End-to-end incremental learning. In Proceedings of the European conference on computer vision (ECCV), 2018.
Yu Chen, Lingfei Wu, and Mohammed J. Zaki. Iterative deep graph learning for graph neural networks: Better and robust node embeddings. Advances Neural Information Processing Systems 33; Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5- 10, 2016, Barcelona, Spain, 2016.
Chenhui Deng, Zhiqiang Zhao, Yongyu Wang. Zhiru Zhang, and Zhuo Feng. Graphzoom: multi- level spectral approach for accurate and scalable graph embedding. In 8th International Confer- ence on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
Xiaowen Dong, Dorina Thanou, Pascal Frossard, and Pierre Vandergheynst. Learning laplacian matrix in smooth graph signal representations. IEEE Transactions on Signal Processing, (23), 2016.
David Duvenaud, Dougal Maclaurin, Jorge Sgarrara-lparraguirre,, Rafael Coómez-Bombared Timo- thy Hirzel, Alán Aspuru-Guzik, and Ryan P. Adams. Convolutional networks on graphs for learn- ing molecular fingerprints. Advances Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, 2015.
Hilmi E Egilmez, Eduardo Pavez, and Antonio Ortega. Graph learning from data under laplacian and structural constraints. IEEE Journal of Selected Topics in Signal Processing, (6), 2017.
10

---

Published as a conference paper at ICLR 2022
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Yihong Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation, In The World Wide Web Conference, WWW 2019, San Francisco, CA, USA, May 13-17, 2019, 2019.
Reza Zanjirani Farahani and Masoud Hekmatfar. Facility location: concepts, models, algorithms and case studies. 2009.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. ArXiv preprint, 2019.
Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He. Learning discrete structures for graph neural networks. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, Proceedings of Machine Learning Research, 2019.
Hongyang Gao and Shuiwang Ji. Graph u-nets. In Proceedings of the 36th International Conference Machine Learning, /CML 2019, 9-15 June 2019, Long Beach, California, USA, Proceedings of Machine Learning Research, 2019.
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, 2017.
Weihua Hu, Mathhis Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Ad- vances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, viriual, 2020.
Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin R. Benson. Combining label prop- agation and simple models out-performs graph neural networks. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021, 2021a.
Zengfeng Huang, Shengzhong Zhang, Chong Xi, Tang Liu, and Min Zhou. Scaling up graph neural networks via graph coarsening. In In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD '21), 2021b.
Joseph J. Pfeiffer III, Sebastián Moreno, Timothy La Fond, Jennifer Neville, and Brian Gallagher. Attributed graph models: modeling network structure with correlated attributes. In 23rd Inter- national World Wide Web Conference, WWW '14, Scoul, Republic of Korea, April 7-11, 2014, 2014.
Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. In KDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, CA, USA, August 23-27, 2020, 2020.
David R Karger. Random sampling in cut, flow, and network design problems. Mathematics of Operations Research, (2), 1999.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
Guohao Li, Matthias Müller, Ali K. Thabet, and Bernard Ghanem. Deepgens: Can gens go as deep as enns? In 2019 IEEE/CVF International Conference on Computer Vision, ICCV 2019, Seoul, Korea (South), October 27 November 2, 2019, 2019.
Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery Data Mining. ACM, 2020.
11

---

Published as a conference paper at ICLR 2022
Xiaorui Liu, Wei Jin, Yao Ma. Yaxin Li, Hua Liu, Yiqi Wang, Ming Yan, and Jiliang Tang. Elastic graph neural networks. In Proceedings of the 38th International Conference on Machine Learn ing. ICML 2021, 18-24 July 2021, Virtual Event, Proceedings of Machine Learning Research, 2021.
Andreas Loukas. Graph reduction with spectral and cut guarantees. Mach. Learn. Res., (116), 2019.
Andreas Loukas and Pierre Vandergheynst. Spectrally approximating large graphs with smaller graphs. In Proceedings of the 35th International Conference Machine Learning, ICML 2018, Stockholmsmüsssn, Stockholm, Sweden, July 10-15, 2018, Proceedings of Machine Learning Re- search, 2018.
Xiaojun Ma, Ziyao Li, Lingjun Xu, Guojie Song, Yi Li, and Chuan Shi. Learning discrete adaptive receptive fields for graph convolutional networks, 2021.
Yao Ma, Xiaorui Liu, Tong Zhao, Yozen Liu, Jiliang Tang, and Neil Shah. A unified view graph neural networks as graph signal denoising. ArXiv preprint, 2020.
Timothy Nguyen, Zhourong Chen, and Jaehoon Lee. Dataset meta-learning from kernel ridge- regression. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021, 2021.
David Peleg and Alejandro A Schäffer. Graph spanners. Journal of graph theory, (1), 1989.
Sylvestre- Sylvestre-Alvise Rebuffi, Alexander Kolesnikov, Georg Sperl, and Christoph H. Lampert. icarl: Incremental classifier and representation learning. In 2017 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, Honolulu, HI, USA, July 21-26, 2017, 2017.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings, 2018.
Cosma Rohilla Shalizi and Andrew C Thomas. Homophily and contagion are generically con- founded in observational social network studies. Sociological methods & research, (2), 2011.
Daniel Spielman and Shang-Hua Teng. Spectral sparsification of graphs. SIAM Journal on Computing, (4), 2011.
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, (11), 2008
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings, 2018.
Tongzhou Wang, Jun-Yen Yan Zhu, Antonio Torralba, and Alexei Efros. Dataset distillation. ArXiv preprint, 2018.
Max Welling. Herding dynamical weights to learn. In Proceedings of the 26th Annual International Conference on Machine Learning, ICML 2009, Montreal, Quebec, Canada, June 14-18, 2009, ACM International Conference Proceeding Series, 2009.
Felix Wu, Amauri H. Souza Jr., Tianyi Zhang, Christopher Fifty. Tao Yu, and Kilian Q. Weinberger. Simplifying graph convolutional networks. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, Proceedings of Machine Learning Research, 2019a.
Zonghan WU, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip Yu. A comprehensive survey graph neural networks. ArXiv preprint, 2019h 9b.
12

---

Published as a conference paper at ICLR 2022
Rex Ying, Ruining He. Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Pro- ceedings of the 24th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, KDD 2018, London, UK, August 19-23, 2018, 2018a.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, William L. Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. In Advances in Neural In- formation Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, 2018b.
Yuning You, Tianlong Chen, Yang Shen, and Zhangyang Wang. Graph contrastive learning auto- mated. In Proceedings of the 38th International Conference Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, Proceedings of Machine Learning Research, 2021.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor K. Prasanna. Graphsaint: Graph sampling based inductive learning method. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 60-3,, 2020, 2020.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI- 18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans. Louisiana, USA. February 2-7, 2018, 2018.
Bo Zhao and Hakan Bilen. Dataset condensation with differentiable siamese augmentation. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, Proceedings of Machine Learning Research, 2021.
Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. Dataset condensation with gradient matching. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 202 1, 2021.
Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any GNN with local structure awareness. In International Conference Learning Representations, 2022. URL httpp/////ppeeeeeeeeeeeeeeeeeeed wtt.rrrmmm....aaaa..po.......... WYKΟEH.
Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changeheng Li, and Maosong Sun. Graph neural networks: review of methods and applications. ArXiv preprint, 2018.
Kaixiong Zhou, Ninghao Liu, Fan Yang. Zirui Liu, Rui Chen, Li Li, Soo-Hyun Choi, and Xia Hu. Adaptive label smoothing to regularize large-scale graph training. arXiv preprint arXiv:2108.11 135555, 2021.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Process- ing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
Ligeng 7hu, Zhijian Liu, and Song Han. Deep leakage from gradients. In Advances in Neural In- formation Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, 2019.
Meiqi Zhu, Xiao Wang, Chuan Shi. Houye Ji, and Peng Cui. Interpreting and unifying graph neural networks with an optimization framework, In Proceedings of the Weh Conference 2021, 2021.
13

---

Published as a conference paper at ICLR 2022
A DATASETS AND HYPER-PARAMETERS
A.1 DATASETS
We evaluate the proposed framework on three transductive datasets, i.e., Cora, Citeseer (Kipf & Welling, 2017) and Ogbn-arxiv (Hu et al., 2020), and two inductive datasets, i.e., Flickr (Zeng et al., 2020) and Reddit (Hamilton et al., 2017). Since all the datasets have public splits, we download them from PyTorch Geometric (Fey & Lenssen, 2019) and use those splits throughout the experiments. Dataset statisties are shown in Table 6.
Table 6: Dataset statistics. datasets.
The first three are transductive datasets and the last two are inductive
Dataset
#Nodes
#Edges
#Classes
#Features
Training/Validationns
Cora
2,708
5,429
7
1,433
140/500/1 1000
Citeseer
3,327
4,732
6
3,703
120/500/ 1000000/1000
Ogbn-arxiv
169,343
1,166,243
40
128
09.941/2,,99/48..00
Flickr
89,250
899,756
7
500
44,625/22312222333
Reddit
232,965
57,307,946
210
602
15.3952//3.699/555334
A.2 HYPER-PARAMETER SETTING
Condensation Process. For DC, we tune the number of hidden layers in range of (1, and fix the number of hidden units to 256. We further tune the number of epochs for training DC in a range of {100, 200, 4003. For GCOND, without specific mention, we adopt 2-layer SGC (Wu et al., 2019a) with 256 hidden units as the GNN used for gradient matching. The function ga that models the relationship between A' and X' is implemented as multi-layer perceptron (MLP). Specifically, we adopt a 3-layer MIP with 128 hidden units for small graphs (Cora and Citeseer) and 256 hidden units for large graphs (Flickr, Reddit and Ogbn-arxiv). We tune the training epoch for GCOND in range of {400, 600, 1000]. For GCOND-X. X. we tune the number of hidden layers in range of {1, 2, 3} and fix the number of hidden units 256. We further tune the number of epochs for training GCOND-X X in a range of { 100, 200, 4003. We tune the learning rate for all the methods in range of 10. 0.01, 0.001, 0.0001). }. Furthermore, we set be 0.05, 0.05, 0.01, 0.01, 0.01 for Citeseer, Cora, Ogbn-arxii Flickr and Reddit, respectively.
For the choices of condensation ratio r. we divide the discussion into two parts. The first part is about transductive datasets. For Cora and Citeseer, since their labeling rates are very small (5.2% and 3.6%, respectively), we choose r to be (25%, 50%, 100%) of the labeling rate. Thus, we finally choose {1.3%, 2.6%, 5.2%) } for Cora and (0.9%, 1.8%, 3.6%) } for Citeseer. For Ogbn-arxiv, choose r to be {0.1% 1%, 0.5%, 1%} of its labeling rate (53%). thus being (0.05%, 0.25%, 0.5%). 3.).. The second part is about inductive datasets. As the nodes in the training graphs are all labeled in inductive datasets, we simply choose (0.1%, 0.5%, 0.1 %) for Flickr and 0.05%, 0. 1,, 0.2% for Reddit.
Evaluation Process. During the evaluation process, we dropout rate be 0 and weight decay to be 0.0005 when training various GNNs. The number of epochs is set to 3000 for GAT while it is set to 600 for other models. The initial learning rate is set to 0.01.
Settings for Table 3 and Table 4, In both condensation stage and evaluation stage, we set the depth of GNNs to 2. During condensation stage, set weight decay to O, dropout to 0 and training epochs to 1000. During evaluation stage, we set weight decay to 0.0005, dropout to O and training epochs 600.
A.3 TRAINING DETAILS OF DC-GRAPH, GCOND-X AND GCOND
DC-Graph: During the condensation stage, DC-Graph only leverages the node features to produce condensed node features X'. During the training stage of evaluation, DC- OC-Graph takes the condensed features X' together with an identity matrix the graph structure to train GNN. In the later test stage of evaluation, the GNN takes both test node features and test graph structure as input to make predictions for test nodes.
14

---

Published as a conference paper at ICLR 2022
During the condensation stage, GCOND-X leverages both the graph structure and node features to produce condensed node features X'. During the training stage of evaluation, GCOND-X takes the condensed features X' together with identity matrix as the graph structure to train GNN. In the later test stage of evaluation, the GNN takes both test node features and test graph structure input make predictions for test nodes.
GCOND-X:
GCOND: During the condensation stage, GCOND leverages both the graph structure and node features produce condensed graph data (A', IA'X) X'). During the training stage of evaluation, GCOND takes the condensed data (A', X') to train a GNN. In the later test stage of evaluation, the GNN takes both test node features and test graph structure input to make predictions for test nodes.
B ALGORITHM
We show the detailed algorithm of GCOND in Algorithm In detail, first set the condensed label set Y' to fixed values and initialize X' as node features randomly selected from each class. In each outer loop, class we sample the corresponding node batches from T and S, and calculate the gradient matching loss within each class. The sum losses from different classes are used to update X' or 4. After that we update the GNN parameters for To epochs. When finishing the updating of condensed graph parameters, we use A' ReL.U(go (X') 8) obtain the final sparsified graph structure.
sample GNN model initialization from distribution Pa. Then, for each
Algorithm 1: GCOND for Graph Condensation
Input: Training data (A, X, Y), pre-defined condensed labels Y' Initialize X as node features randomly selected from each class for k O, ................................ K do
Initialize Ou Poo
for t 0, 0,....
do
D D'
for ...... C do
Compute A go (X'); then [A', Y
Sample (Aa, X., Y.) ~OTTTTTTT T and (A, Y.) ~ S
to detailed in Section 3.1
10
Compute L = C (GNNo, (A., (A,, Y.) and L = L (GNNo, (.,.))) Y'))
11
D' D' CT, vo.
if 1%(1 + 72) then
Update X X' 1/1 D
14
else
Update + - + D'
16
Update 0.11 + (0,,
t Ta the number of steps for updating
A' ReL.U(g (X') 5) Return: (A', X', Y')
18
C MORE EXPERIMENTS
C.1 ABLATION STUDY
Different Parameterization. We study the effect of different parameterizations for modeling A' and compare GCOND with modeling A' free parameters Table From the table, we observe significant improvement by taking into account the relationship between A' and X'. This suggests that directly modeling the structure as a function features can ease the optimization and lead to better condensed graph data.
Joint optimization versus alternate optimization. We perform the ablation study on joint opti- mization and alternate optimization when updating & and X'. The results shown in Table 8. From the table, we can observe that joint optimization always gives worse performance and the standard deviation is much higher than alternate optimization.
15

---

Published as a conference paper at ICLR 2022
Table 7: Ablation study on different parametrizations.
Parameters
Citeseer, r=1.8%
Cora, r=2.6%
Ogbn-arxiv, r=0.5%%
A'. X
62.2.14.8
75.5100.6 80.1100.6
63.010.5
Φ X
70.6.10.9
63.2.10.3
Table 8: Ablation study different optimization strategies.
Citeseer, 1=1.8%
Cora, r=2.6%
Ogbn-arxiv. r=0.25%
Flickr. r=0.5
Reddit. r=0.1%
Joint Alteraae
68.2:13.0
1.6911.6
62.8:::11 63.2:00.3
45.4400.4
87.511.8
70.6:10.9
80.1
47.110.1
89.510.8
C.2 NEURAL ARCHITECTURE SEARCH
We focus on APPNP instead of GCN since the architecture APPNP involves more hyper- parameters regarding its architecture setup. The detailed search space is shown as follows:
(a) Number of propagation K: we search the number propagation K in the range of
{2, 4, 6, 8, 10].
(b) Residual coefficient a: for the residual coefficient in APPNP, we search in the range of
{0.1, 0.2).
(c) Hidden dimension: We collect the set of dimensions that are widely adopted by existing work as the candidates, i.e.,
(d) Activation function: The set of available activation functions is listed as follows: {Sigmoid, Tanh, ReLU, Linear, Softplus, LeakyReLU, ReLU6, ELU}
In total, for each dataset we search 480 architectures of APPNP and we perform the search process on Cora, Citeseer and Ogbn-arxiv. Specifically, we train each architecture on the reduced graph for epochs on as the model converges faster on the smaller graph. We use the best validation accuracy choose the final architecture. We report (1) the Pearson correlation between validation accuracies obtained by architectures trained on condensed graphs and those trained on original graphs, and (2) the average test accuracy of the searched architecture over 20 runs.
Table Neural Architecture Search. Methods are compared in validation accuracy correlation and test accuracy obtained by searched architecture. Whole means the architecture is searched using whole dataset.
Pearson Correlation
Test Accuracy
Random
Herding
GCOND
Random
Herding
GCOND
Whole
Cora Citeseer
0.40
0.21
0.76
82.9
82.9
83.1
82.6
0.56
0.29
0.79
71.4
71.3
71.3
71.6
Ogbn-arxiv
0.63
0.60
0.64
71.1
71.2
71.2
71.9
C.3 TIME COMPLEXITY AND RUNNING TIME
Time Complexity. We start from analyzing the time complexity calculating gradient matching loss, i.c., line 8 to line 11 in Algorithm 1. Let the number of MLP layers in 9a be L and r be the number of sampled neighbors per node. For simplicity, we assume all the hidden units are d for all layers and we use L-layer GCN for the analysis. The forward process of has complexity of 2( The forward process of GCN on the original graph has a complexity of Or Nd) and that on condensed graph has a complexity of OL LN'd), The complexity calculating the second-order derivatives in backward propagation has additional factor of O |0 || Xx which can be reduced to O(0,) + A XXI) with finite difference approximation. Although there note that the process is easily parallelizable. Furthermore, the process updating 0, in line 16 has a complexity of To (LN + LN' d). Considering there are T' iterations and K different initializations, multiply the aforementioned complexity by KT. To
C iterations in line 7-11,
16

---

Published as a conference paper at ICLR 2022
sum up, that the time complexity linearly increases with number of nodes in the original graph.
Running Time. We report the rumning time of the proposed GCOND for different condensation rates. Specifically, we vary the condensation rates in the range of {0.1 %, 0.5%, 1% on Ogbn-arxiv single A100-SXM4 GPU is
and (1%, 5%, 10%] on Cora. The running time of 50 epochs reported in Table 10. The whole condensation process (1000 epochs) for generating 0.5% condensed graph of Ogbn-arxiv takes around 2.4 hours, which an acceptable cost given the huge benefits of the condensed graph.
Table 10: Running time of GCOND for 50 epochs.
0.1%
0.5%
%
1 1%
5%
10%
Ogbn-arxiv
348.6s
428.2s
609.8s
Cora
37.4s
43.9s
64.8s
C.4 SPARSIFICATION
In this subsection, investigate the effect of threshold 5 on the test accuracy and sparsity. In detail, we vary the values of the threshold ô used for truncating adjacency matrix in range of {0.01, 0.05, 0.1, 0.2, 0.4, 0.6, 0.8), and report the corresponding test accuracy and sparsity in Fig- ure 3. From the figure, we can see that increasing 5 can effectively increase the sparsity of the obtained adjacency matrix without affecting the performance too much.
100
100
80
acc
SccuracyySpessiiy
80-
--- sparsity
yccuraryySSpaaii risity
80
-A- sparsity
Accuracy/Spariitty (96)
60
4-0-
sparsity
60-
60-
40
60-
20
Threshold
Threshold
Threshold
(a) Cora, r=2.5%
(b) Citeseer, 1=1.8%
(c) Ogbn- Ogbn-arxiv, r=0.05% 75000
Accuracy/Sparidyy 199)
-a- sparsity
Seccuracy/pparaattyyy (96)
80
- sparsity
60-
20
40
20
20
0.3
0.1
0.5
0.6
0.7
au
233
04 Threshold
055
0.6
0.r 0.
Threshold
(d) Flickr, 0=0.1
(e) Reddit, r=0.1%
Figure 3: Test accuracy and sparsity under different values of 6.
C.5 DIFFERENT DEPTH AND HIDDEN UNITS.
Depth Versus Hidden Units. We vary the number of model layers (GCN) in range of (1, 4} and the number hidden units a range of {16, 32, 64, 128, 256). and test them on the condensed graphs of Cora and Citeseer. The results reported in Table 1.. From the table, that changing the number of layers impacts the model performance a lot while changing the number of units does not.
observe
17

---

Published as a conference paper at ICLR 2022
Table 11: Test accuracy on different numbers of hidden units (H) and layers (L). When L=1, there is no hidden layer so the number of hidden units is meaningless.
(a) Cora, r=2.6%
(b) Citeseer, r=1.8%
ITL
3
IT:L
2
4
16
74.8=0.5
76.8+1.0
68. 38.023.00
50.91995
16
58.6#12.1
69.2=14
56.918.4
00.4+1122
79.2.10.7
70.4133.2
61.117.2
32
69.4 1.3
59.9110.2
42.6.13.6
1.0
72.043.3
6..512.2
64
69.7=1.5
60.3410.3
43.613.7
128
79.9#0.3
76.6#1.8
618833.8
128
1.42-14
63.349.7
61.01188
80.1#0.6
75.9+1.6
65.64:2.9
256
7..6=0.9
63.5410.0
52.945.5
Table 12: Cross-depth accuracy on Cora, r=2.6%
C
2
3
4
5
80.30
80.70
79.46
76.06
71.23
40.62
72.37
40.14
67.19
35.02
74.24
72.56
76.26
71.70
65.12
71.31
75.73
70.95
73.13
67.12
6
75.20
75.18
75.67
76.16
75.00
Propagation Versus Transformation. We further study the effect of propagation and transforma- tion on the condensed graph. We use Cora as an example and SGC as the test model due its decoupled architecture. Specifically, we vary both the propagation layers and transformation layers of SGC the range of 2,,,,3, 4, 5). and report the performance Table 13. As can seen, the condensed graph still achieves good performance with 3 and 4 layers of propagation. Although the condensed graph is generated under 2-layer SGC, is able to generalize to 3-layer and 4-layer SGC. When increasing the propagation 5, the performance degrades a lot which could be the cause of the oversmoothing issue. On the other hand, stacking more transformation layers can first help boost the performance but then hurt. Given the small scale of the graph, SGC suffers the overfitting issue in this case.
Cross-depth Performance. We show the cross-depth performance in Table 12. Specifically, SGC of different depth in the condensation to generate condensed graphs and then use them to test on SGC of different depth. Note that in this table, set weight decay to 0 and dropout to 0.5. We can observe that usgin deeper GNN is not always helpful. Stacking more layers do not necessarily mean we can learn better condensed graphs since more nodes are involved during the optimization, and this makes optimization more difficult.
Table 13: Test accuracy of SGC on different transformations and propagations for Cora, r=2.6%
Trans's \ Prop
2
3
4
77 77.0910.44
79.02=
78.12:2..1
74.04+3.60
61.1917.73 73
2
76.94+0.50
79.01=0.557
79.11=1.115
77.57+1.03
72.37-4.25
75.28+00.58
77.95+0.67
74.16+1.50
70.58+3.71
58.28+8..9
66.87+00.7
66.5440.82
59.244+1660
43.9446.33
30.45+9.67
5
46.44+0.91
37.29+3.23
16.05+22.4
15.33+2.79
15.33+2.79
C.6 VISUALIZATION OF NODE FEATURES.
In addition, provide the t-SNE (Van der Maaten & Hinton, 2008) plots of condensed node fea- tures to further understand the condensed graphs. In Cora and Citeseer, the condensed node features well clustered. For Ogbn-arxiv and Reddit. also observe some clustered pattern for the nodes within the same class. contrast, the condensed features are less discriminative in Flickr, which indicates that the condensed structure information be essential in training GNN.
18

---

Published as a conference paper at ICLR 2022
(a) Cora, r=2.5% (b) Citeseer, r=1.8% (c) Arxiv, 00005%
(d) Flickr, r=0.1%
(c) Reddit, r=0.1%
Figure 4: The t-SNE plots of node features in condensed graphs.
C.7 PERFORMANCES ON ORIGINAL GRAPHS
We show the performances of various GNNs original graphs in Table 14 to serve references.
Table 14: Performances of various GNNs on original graphs. SAGE: GraphSAGE.
GAT
Cheby
SAGE
SGC
APPNP
GCN
Cora
83.1
81.4
81.2
81.4
83.1
81.2
Citeseer
70.8
70.2
70.1
71.3
71.8
71.7
Oghn-arxiv
71.5
71.4
71.5
71.4
71.2
71.7
Flickr
44.3
47.0
46.1
46.2
47.3
47.1
Reddit
91.0
93.1
93.0
93.5
94.3
93.9
C.8 EXPERIMENTS ON PUBMED.
We also show the experiments for Pubmed with condensation ratio of 0.3% in Table 15. From the table, we can observe that GCOND approximates the original performance very well (77.92% vs. 79.32% GCN). It also generalizes well to different architectures and outperforms GCOND-X and DC-Graph, indicating that it is important to leverage the graph structure information and learn a condensed structure.
Table 15: Performance of different GNNs on Pubmed (r=0.3%).
APPNP
Cheby
GCN
GraphSage
SGC
DC-Graph GCOND-X GCOND
12.76+11.39 73.91
72.66+00.59
72.44+12.90 71.81+0.94 77.9240:42
71.96++2.50
75.43-+-0.5
1.057+11000
73.10 71.1243.10
76.72++0.65
76.77-1.117
75.48:0.82
75.91
D MORE RELATED WORK
Graph pooling, Graph pooling (Zhang et al., 2018; Ying et al., 20182 Gao & Ji, 2019) also gener- ates coarsened graph with smaller size. Zhang et al. (2018) is one the first to propose end-to-end architecture for graph classification by incorporating graph pooling. Later, DifiPPoo (Ying et al., 2018b) proposes to GNNs parameterize the process of node grouping. However, those meth- ods are majorly tailored for the graph classification task and the coarsened graphs are a byproduct graph during the representation learning process.
19


Reviews:
[{"review_id": "UQbKK0_dDZr", "reviewer": "Reviewer_cTj2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Strength:\n- The paper is easy to follow and overall well-organized.\n- The method is sound.\n- Various experiments are conducted, including the generalization experiments \n\nWeaknesses:\n- The overall method is similar to the existing gradient matching method. The innovation is limited, but the setting is new for applying this method.\n- Compared to the existing gradient matching method for data condensation, the major difference in graph problem is the new parameterization for the adjacency matrix A' and X'. The authors claim that it is important to parameterize A' as a function of X'. However, experiments are not conducted to support this very important claim.\n\nQuestions:\n- What if A' and X' are treated as free parameters? What if A' is independent of X'? For example, we can set $A_{ij}'= relu( W_{ij} - \\delta )$ where $W_{ij}$ is a free parameter to replace equation (7). What's the performance of this approach, in terms of both the optimization efficiency and the test performance?\n- Experiments use GNNs with 2 layers. What if more layers are used? Intuitively, using fewer layers (e.g., 0 layer in the extreme case) will reduce this problem to the normal data condensation problems on non-graph data. What if a deeper GNN is used so that the graph structure plays a more important role?\n- Some statements are not clear enough. For example, for the $\\theta_t$ in equation (5), it only mentions this replaces the $\\theta_t^S$ and $\\theta_t^T$ (I believe there is a typo under equation (5), too). However, how $\\theta_t$ is computed is not mentioned. Taking the average of $\\theta_t^S$ and $\\theta_t^T$? \n", "summary_of_the_paper": "This paper studies the graph condensation problem for GNN training, in which a large graph is condensed into a small synthetic graph, and the GNN trained on the small graph is expected to perform similar to the GNN trained on the large graph.\n\nTechnically, the overall framework follows the gradient matching method, but specific parameterization is proposed for optimizing the small synthetic graph.\n", "summary_of_the_review": "- Pro: The method is sound.\n- Con: The method is similar to the existing gradient matching method, but the graph setting is new.\n- Con: Experiments can be improved:\n-- Ablation study is needed to verify the effectiveness of the proposed parameterization.\n-- Experiments on deeper GNNs can better demonstrate the method.\n\nMy score is actually between weak rejection and weak acceptance. I will consider increasing my score to weak acceptance if experiments can be improved.\n\n---post rebuttal\n\nThe new experimental results in the revised paper have addressed my concerns so I choose to raise the score to 6.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "By9B7PMOc0K", "reviewer": "Reviewer_R5cV", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Strengths:\n1. The idea of using data condensation/distillation on GNNs is new and interesting. \n2. The empirical results looks quite promising. It is impressive that the compression ratio can be more than 100, and the testing accuracies remain competitive in many cases.\n3. Empirical results show that the synthetic graph constructed based on SGC work well across different models. This generalizability is a useful property of this technique.\n4. The paper is well-written.\n\nWeaknesses:\n1. Although applying condensation techniques on GNNs is new and some technical details need to be taken care of, the main ideas still follow previous work, e.g. the gradient matching loss.\n2. The aim of graph condensation is to alleviate the storage and time consumption. However, to construct the smaller graph, one still needs to train a GNN model on the original graph, which still requires sampling methods for large graphs. I think the authors should provide more discussions on the computation costs of the condensation process. \n3. On more complicated datasets such as OGB-arxiv, the accuracy gap is still quite noticeable. And it seems difficult to improve the accuracy by using larger condensed graph size, since it would become more difficult to train the parameters in the synthetic graph.", "summary_of_the_paper": "To alleviate the storage and time consumption for training GNN models on large graphs, the paper studies graph condensation, which draws inspirations from data distillation/condensation. It first constructs a much smaller synthetic graph, and then train GNN models on this small graph. Empirical results show that, graph condensation can reduce the size of the graph by 99% but still achieves comparable accuracy.", "summary_of_the_review": "Overall, I think graph condensation is a new and interesting direction, and the empirical results presented in the submission are generally encouraging. On the other hand, given previous work on data condensation, the novelty of the current method is not significant. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "5sVWiov2J45", "reviewer": "Reviewer_XqrK", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Strength:\n1. This paper is generally well-written and easy to follow.\n\n2. The paper's motivation is clear.\n\n3. Extensive experiments are conducted to demonstrate the model's effectiveness.\n\nWeakness:\n1. This paper attempts to extend the Dataset Condensation model and Gradient Matching technique presented in [1] to the domain of GNNs. Although some differences exist, they are so minor that the main equations (1) - (5) in this work are nearly identical to equations (4), (5), and (7) - (9) in [1]. As a result, I believe this work lacks innovation in terms of technical contribution.\n\n[1] Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. Dataset condensation with gradient matching. https://openreview.net/pdf?id=mSAKhLYLSsl.\n\n\n2. In Section 3.2, the authors claim that GCond-X, which only learns the condensed node features X' and not the condensed graph structure A', also performs well. This observation leads me to wonder if the proposed method is better suited for *dataset* condensation rather than *graph* condensation.\n\n3. The paper makes no attempt to analyze the algorithm's complexity or to report its runtime.\n\nMinor comments:\n1. In equation (3), the letter 'D' should be in the mathematical font. \n\n2. On page 4, line 1, it appears that the phrases '[...] and unrolling the entire training trajectory of the inner problem' have been omitted or repeated. \n\n3. Page 6, Evaluation section, line 3: 'With r percent of N nodes'. Here r should be a number between 0 and 100, and yet it is a percentage in Table 2. \n\n4. All 'r=...' in the supporting materials appear to be in a non-math typeface.", "summary_of_the_paper": "This paper introduces GCond, a graph condensation framework designed to compress graph datasets and reduce storage and time requirements while training GNNs on large-scale graphs. GCond makes use of gradient matching and graph sampling to reduce the graph size. Experiments demonstrate that GCond can maintain a high degree of accuracy while significantly lowering the size of the graph.", "summary_of_the_review": "The paper's idea is interesting, as evidenced by the experimental results. However, the theoretical depth and novelty may not be enough to meet ICLR's standards. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "4Ho6VBNZI9V", "reviewer": "Reviewer_peGb", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Overall, I personally found the idea of the problem presented in the paper intriguing. Being able to shrink large datasets to smaller ones in order to allow an easy training and tuning of a variety of approaches is something that would for sure help both in academic and industrial settings. \n\nThis said, I’m not sure the solution proposed in the paper fully addresses the problem. In order to make the new condensed graphs actually useful for training and tuning, we would need a variety of different GNNs to actually approach their original performance when actually trained on the smaller synthetic graphs or at least to show the same order of performance (i.e. if performance of GNN1 are better than GNN2 when trained on the original graph, they should also be better when trained on the synthetic graph), so that we could for instance tune a variety of different architectures on the smaller condensed graphs G’ and then re-train only the best performing one on the original datasets. However, these conditions don’t seem to be satisfied for a variety of approaches. Besides for GCN, which achieves in 4 out of 5 datasets performance which are reasonably close to the ones it would have if trained on the original graphs, the generalizability of condensed graphs to different architectures doesn’t seem particularly strong as outlined in Table 3. For instance, Graph Attention Network which achieves 83% on the original CORA, it achieves only 66.2% on the condensed one with SGC and, in addition to this, it is actually outperformed by GCN which instead achieves lower performance than GAT if trained on the original dataset (a similar, although less marked, comparison could be made for APPNP as well, which is outperformed by GCN both on Citeseer and Cora, while outperforming it if trained on the original datasets as per https://arxiv.org/pdf/1903.02428v3.pdf). This is most likely due to the way in which the condensed graphs are constructed (i.e. via SGC), which intrinsically pushes the condensed graph to perform well for the model used at condensation time (or models which are reasonably similar to this one, e.g. GCN) but it doesn’t offer any guarantee for reasonably different models. \n\nFor this reason, while I personally think that the problem outlined in paper is of interest to the community, I’m not sure the solution proposed in the manuscript is mature enough for pushing for an acceptance to ICLR.\n\nIn addition to this, there are a variety of other points that I would like to highlight in my review and which I would like the authors to address in their rebuttal:\n\n1) Equation 6, the distance measure boils down to the sum of one minus the cosine similarity between the columns of the two different gradients. Why did the authors choose that specific distance and not for instance an L2 distance? What is the effect of that distance on performance of the approach?\n\n2) In the graph sampling paragraph of subsection 3.1, the authors state “To further reduce memory usage and ease optimization, we calculate the gradient matching loss for nodes from different classes separately, as matching the gradients w.r.t. the data from a single class is easier than that from all classes.”, however there is not really an explanation in the paper why this would be easier. Do the authors match gradients on each class separately as they want nodes of the same class to provide the same information? why? I believe the approach should work even if we aggregate the gradients on all samples from different classes.\n\n3) In the same subsection as for points 2, the authors also state “For the condensed graph A’, we sample a batch of synthetic nodes of class c but do not sample their neighbors as we need to learn the connections with other nodes.”. Does this imply that their model will learn connections only across the sampled nodes at each step instead of out of the entire pool of available nodes?\n\n4) The authors evaluate their approach on Cora and Citeseer (among the other datasets) but they didn’t consider PubMed which is typically used in experimental evaluations alongside these two. Is there a specific reason why the authors decided to skip PubMed in their experimental evaluation?\n\n5) In Section 4.1 the authors state “As vanilla DC cannot leverage any structure information, we develop a variant named DC-Graph, which additionally leverages graph structure during test stage, to replace DC for the following experiments.”. However, as for DC-Graph the authors use only the identity matrix on the condensed graph at training time, while they use the whole original graph at test time, it is unclear how DC and DC-Graph differ at test time. Did the authors discard the connectivity of the original graph during testing when evaluating a model trained on graph condensed with DC? If that is correct, why?\n\n6) Section 4.3, paragraph “Different Architectures” is quite unclear. I believe the authors are showing the performance that different architectures tested with graphs condensed with SGC allow to achieve, however these numbers don't match the ones reported in table 4 for ChebNet. I believe this is just a typo and I would ask the authors to please confirm this and if I'm correct to fix the error in the table. Additionally, I would kindly ask the authors to please report the performance that the considered models were able to achieve on the original graphs. It would greatly help at highlighting the variation in performance of the approaches wrt the ideal scenario (i.e. where we train and test them on the same graph)\n\n7) Section 4.3, paragraph “Versatility of GCOND”, the authors omit GAT out of the comparison showing the performance of a graph condensed with a GNN but then used for training with a different one because of its “deterioration in performance with large neighborhood sizes”. However, this doesn’t appear to me as a sufficient justification for omitting GAT altogether and if this fails at performing well in those specific conditions it should probably be shown in the table with the other methods.  Additionally, couldn't we restrict the neighborhood sizes in the condensed graph (e.g. by considering only the K most similar neighbors) before training GAT if this fails to perform well with large neighborhoods?\n\n8) In Table 4, surprisingly a graph condensed with GCN is not the best one for training GCN (the graph condensed with SGC allows to achieve 10% more in terms of accuracy with GCN). This is quite surprising and I wonder if the authors have a justification for this. \n\n9) Table 5, the graph condensed with SGC for OGBN-Arxiv loses its original homophily. This is probably the reason for the drop in performance, however I was not able to identify in the paper a reason for this. Do the authors have a justification for this behavior?\n\n----\n\nUpdated score to 6 after author's rebuttal.", "summary_of_the_paper": "The paper proposes and addresses the problem of graph condensation. In a nutshell, provided a large graph G, the scope of the paper is to propose a solution able to generate a smaller synthetic graph G’, which effectively allows to train Graph Neural Networks (GNNs) able to achieve similar performance as if they were trained on G. In order to do that, the authors propose to match the gradients produced by a specific GNN on mini-batches extracted from G and G’. This avoids the need of constructing a minimization problem based on an outer and inner training loop which would be computationally heavy to handle. The node-wise features X’ of the smaller graph G’ are considered as free parameters in the optimization process and the adjacency matrix A’ is instead inferred from X’ via a learnable MLP which is trained alongside X’ with an alternating optimization schema. The authors evaluate the quality of their approach on the Cora, Citeseer, OGBN-Arxiv and Reddit datasets, condensing and evaluating the new graphs with a variety of different architectures. ", "summary_of_the_review": "The paper proposes and addresses the problem of graph condensation. While the formulation of the problem is interesting, I didn’t find the approach proposed by the authors to be mature enough for ICLR due to the limitations and issues highlighted in the main review. I thus consider the paper a weak reject for the conference and I kindly ask the authors to reply to the points highlighted in my review in their rebuttal.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper addresses the scale issue in Graph Neural Networks by proposing a “condensation” approach that produces a small synthetic graph from a large original graph such that GNNs trained on both graphs have comparable performance. 

Reviewer cTj2 had concerns with novelty: they claimed the proposed method was close to gradient matching. However, they admitted that the graph setting was new. They suggested some clarity and experimental improvements. 

Reviewer R5cV made a similar comment w.r.t. the similarity to gradient matching. Though overall they were more positive than R5cV and thought the idea was interesting and results were compelling.

Reviewer XqrK like the others, argued that the paper “lacked technical innovation in terms of technical contribution”. They pressed for a complexity or runtime analysis. 

Reviewer peGb found the idea and problem “intriguing” though felt the solution fell short. They offered many suggestions for improving the quality of the experiments and the analysis. 

In the discussion period, reviewer peGb raised their score, thanking the authors for answering their questions. They felt that the additional experiment for NAS was relevant and cleared up a key doubt. Reviewer cTj2 updated their score as well but stated it was critical that the author release the code for reproducing the new experimental results. I think that with most reviewers now on the “accept” side of the fence, I am more inclined to recommend acceptance because I do not see any critical flaws. I think that cTj2’s request for code is reasonable and strongly suggest that the authors do so.
Decision: Accept (Poster)