Structure-free Graph Condensation: From Large-scale Graphs to Condensed Graph-free Data
Authors: Xin Zheng
Miao Zhang
Chunyang Chen
Quoc Viet Hung Nguyen
Xingquan Zhu
Shirui Pan
Venue: NeurIPS 2023 spotlight (2023)
Keywords: graph neural networks (GNNs)
graph condensation
training trajectory meta-matching
graph neural feature score

Abstract: Graph condensation, which reduces the size of a large-scale graph by synthesizing a small-scale condensed graph as its substitution, has immediate benefits for various graph learning tasks.
However, existing graph condensation methods rely on the joint optimization of nodes and structures in the condensed graph, and overlook critical issues in effectiveness and generalization ability.
In this paper, we advocate a new Structure-Free Graph Condensation paradigm, named SFGC, to distill a large-scale graph into a small-scale graph node set without explicit graph structures, i.e., graph-free data.
Our idea is to implicitly encode topology structure information into the node attributes in the synthesized graph-free data, whose topology is reduced to an identity matrix.
Specifically, SFGC contains two collaborative components: 
(1) a training trajectory meta-matching scheme for effectively synthesizing small-scale graph-free data;
(2) a graph neural feature score metric for dynamically evaluating the quality of the condensed data. 
Through training trajectory meta-matching, SFGC aligns the long-term GNN learning behaviors between the large-scale graph and the condensed small-scale graph-free data, ensuring comprehensive and compact transfer of informative knowledge to the graph-free data.
Afterward, the underlying condensed graph-free data would be dynamically evaluated with the graph neural feature score, which is a closed-form metric for ensuring the excellent expressiveness of the condensed graph-free data.
Extensive experiments verify the superiority of SFGC across different condensation ratios.

Structure-free Graph Condensation: From Large-scale Graphs to Condensed Graph-free Data
Xin Zheng',
Miao Zhang', Chunyang Chen', Quoc Viet Hung Nguyen Xingquan Zhu', Shirui Pan Monash University, Australia, "aarbi Institute of Technology (Shenzhen), China Griffith University, Australia, 4Florida Atlantic University, USA xin. www.ggeonnash.h...ommm edu, zhangmiao@hit, edu. en, chunyang- wwwnhhonash.hemmmmmmm edu henry iguyen@griffithh edu. au, xzhu3@fau. s. s.panegriffith. edu, au
Abstract
Graph condensation, which reduces the size of large-scale graph by synthesizing a small-scale condensed graph as its substitution, has immediate benefits for various graph learning tasks. However, existing graph condensation methods rely on the joint optimization of nodes and structures in the condensed graph, and overlook critical issues in effectiveness and generalization ability. In this paper, we advocate new Structure-Free Graph Condensation paradigm, named SFGC, to distill large- scale graph into small-scale graph node set without explicit graph structures, i.e. graph-free data. Our idea is to implicitly encode topology structure information into the node attributes in the synthesized graph-free data, whose topology reduced an identity matrix. Specifically, SFGC contains two collaborative components: (I) a training trajectory meta-matching scheme for effectively synthesizing small- scale graph-free data; (2) a graph neural feature score metric for dynamically evaluating the quality of the condensed data. Through training trajectory meta- matching, SFGC aligns the long-term GNN learning behaviors between the large- scale graph and the condensed small-scale graph-free free data, ensuring comprehensive and compact transfer of informative knowledge to the graph-free data. Afterward, the underlying condensed graph-free data would be dynamically evaluated with the graph neural feature score, which is closed-form metric for ensuring the excellent expressiveness of the condensed graph-free data. Extensive experiments verify the superiority of SFGC across different condensation ratios
Introduction
As prevalent graph data learning models, graph neural networks (GNNs) have attracted much attention and achieved great success [68]
23). Various graph data in the real 43 reflecting diverse node attributes and Modeling such large-scale graphs brings serious challenges in both data storage and GNN model designs, hindering the applications of GNNs in many industrial scenarios 774
36
22
82
25
24
world comprises millions of nodes and edges 37
38
complex structural connections
33 34
32
54
For instance, designing GNN models usually requires repeatedly training GNNs for adjusting proper hyper-parameters and constructing optimal model architectures. When taking large-scale graphs as training data, repeated training through message passing along complex graph structures, makes it highly computation-intensivee and time-consuming through try-and-erros
80 72
To address these challenges brought by the scale of graph data, a natural data-centric solution 78 is graph size reduction, which transforms the real-world large-scale graph small-scale
'Corresoondig author
*Code is available at htttps://githhi http:/thub..ccmmmmmmaa.... Zheng/ SFGC
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

graph, such as graph sampling [66 66, graph coreset 47 60), graph sparsification 5 and graph coarsening B 28]. These conventional methods either extract representative nodes and edges or preserve specific graph properties from the large-scale graphs, resulting in severe limitations of the obtained small-scale graphs in the following two folds. First, the available information on derived small-scale graphs is significantly upper-bounded and limited within the range of large- scale graphs [66] [0]. Second, the preserved properties of small-scale graphs, e,g., spectrum and clustering, might not always be optimal for training GNNs for downstream tasks 3 28
Graph r- (C...)
In light of these limitations of conventional meth- ods, in this work, we mainly focus on graph con- densation [27 26], a new rising synthetic method for graph size reduction. Concretely, graph conden- sation aims to directly optimize and synthesize a small-scale condensed graph, so that the small-scale scale condensed graph could achieve comparable test per- formance as the large-scale graph when training the same GNN model. Therefore, the principal goal of graph condensation is to ensure consistent test re- sults for GNNs when taking the large-scale graph and the small-scale condensed graph as training data.
traie
GHiNve-)
Dot
ADC
Goeparshir
Candossation
trole
GNNN,,
Fiee
ACC
vs.
Oonporaber
MLP/GNNNR))
test
ADC
Fax
Condossation
Figure Comparisons of condensation vs structure-free condensation on graphs.
However, due to the structural characteristic of graph data, nodes and edges are tightly coupled. This makes condensing graph data a complicated task since high-quality condensed graphs are required to jointly synthesize discriminative node attributes and topology structures. Some recent works have made initial explorations of graph condensation [27 26). For instance, GCOND 27 proposed the online gradient matching schema between the synthesized small-scale graph and the large-scale graph, followed by a condensed graph structure learning module for synthesizing both condensed nodes and structures. However, existing methods overlook two-fold critical issues regarding effectiveness and generalization ability. First, graph condensation requires a triple-level optimization to jointly learn three objectives: GNN parameters, distilled node attributes, and topology structures. Such complex optimization cannot guarantee optimal solutions for both nodes and edges in the condensed graph, significantly limiting its effectiveness as the representative of the large-scale graph. Furthermore, existing online GNN gradients [27 26 are calculated with the short-range matching, leading to the short-sight issue of failing imitate holistic GNN learning behaviors, limiting the quality of condensed graphs. Second, existing condensed graphs generally show poor generalization ability across different GNN models 27 26), because different GNN models vary their convolution operations along graph structures. As a result, existing methods are vuinerable to overfiting of specific GNN architectures by distilling convolutional information into condensed graph structures.
To deal with the above two-fold challenges, in this work, we propose a novel Structure- Graph Condensation paradigm, named SFGC, to distill large-scale real-world graphs into small-scale syn- thetic graph node sets without graph structures, i.e., condensed graph-free data. Different from conventional graph condensation that synthesizes both nodes and structures derive scall-scale graph, as shown in Fig. [ the proposed structure-free graph condensation only synthesizes a small- scaled node set to train GNN/MLP, when it implicitly encodes topology structure information into the node attributes in the synthesized graph-free data, by simplifying the condensed topology to an identity matrix. Overall, the proposed SFGC contains two essential components: (1) training trajectory meta-matching scheme for effectively synthesizing small-scale graph-free data; (2) a graph neural feature score metric for dynamically evaluating the quality of condensed graph-free data, To address the short-sight issue of existing online gradient matching, our training trajectory meta- matching scheme first trains set of training trajectories of GNNs on the large-scale graph to acquire an expert parameter distribution, which serves as offline guidance for optimizing the condensed graph-free data. Then, the proposed SFGC conducts meta-matching to align the long-term GNN learning behaviors between the large-scale graph and condensed graph-free data by sampling from the training trajectory distribution, enabling the comprehensive and compact transfer informative knowledge to the graph-free data. At each meta-matching step, we would obtain updated condensed graph-free data, which would be fed into the proposed graph neural feature score metric for dynam- ically evaluating its quality. This metric is derived based on the closed-fone solutions of GNNs under the graph neural tangent kernel (GNTK) ridge regression, eliminating the iterative training

---

of GNNs in the dynamic evaluation. Finally, the proposed SFGC selects the condensed graph-free data with the smallest score as the optimal representative of the large-scale graph. Our proposed structure-free graph condensation method could benefit many potential application scenarios, such as,
graph neural architecture search [79] 81 privacy protection [69], adversarial robustness [67 (0], continual learning (78), and so on. We provide detailed demonstrations of how our method facilitates the development of these areas in Appendix B
In summary, the contributions of this work are listed as follows:
We propose a novel Structure- Free Graph Condensation paradigm to effectively distill large-scale real-world graphs small-scale synthetic graph-free data with superior expressiveness, the best of our knowledge, for the first time.
To explicitly imitate the holistic GNN training process, we propose the training trajectory meta- matching scheme, which aligns the long-term GNN learning behaviors between the large-scale graph and the condensed graph-free data, with the theoretical guarantee of climinating graph structure constraints.
To ensure the high quality of the condensed data, we derive a GNTTK-aase graph neural feature score metric, which dynamically evaluates the small-scale graph-free data each meta-matching step and selects the optimal one. Extensive experiments verify the superiority of our method.
Prior Works. Our research falls into the research topic dataset distillation (condensation) 33 [9]
which aims synthesize small typical dataset that distills the most important knowledge from given large target dataset as its effective substitution. Considering most of the works condense image 76 4 due to the complexity of graph structural data, only few works [27 26 address graph condensation, while our research designs a new structure-free graph condensation paradigm for addressing the effectiveness and generalization ability issues in existing graph conden- sation works. Our research also significantly differs from other general graph size reduction methods, for instance, graph coreset 47 60), graph sparsification about related works can be found in Appendix
data 159 39
3 and so on, More detailed discussions
Structure-Free Graph Condensation
2.1 Preliminaries
Notations.
Denote large-scale graph dataset to be condensed by T T A, Y), where X E Nxd denotes N number of nodes with d-dimensional features, A E N denotes the adjacency matrix indicating the edge connections, and Y E IR XxC denotes the C-classes of node labels. In general, graph condensation synthesizes small-scale graph dataset denoted T (X', A',Y" with XC when N' < N. In this work, we propose the
(X,
X' R xd A' E N''''', and Y' e RM N'C structure-free graph condensation paradigm, which aims to synthesize a small-scale graph node set S = (X, Y) without explicitly condensing graph structures, i.e., the condensed graph-free data, as an effective substitution of the given large-scale graph. Hence, X contains joint node context attributes and topology structure information, which is a more compact representative compared with (X', A').
Graph Condensation. Given a GNN model parameterized by 0, graph condensation [2] is defined to solve the following triple-level optimization objective by taking T (X. A, Y) as input:
min L [GNNe,, (X, A), Y]
s.l. A 0 arg min [GNN (X', A'), Y'J,
2/ A' arg minf [GSL. (X'),
where GSL is submodule parameterized by &b to synthesize the graph structure A'. One of inner loops learns the optimal GNN parameters 0y,, while another learns the optimal GSL parameters 2/ A obtain the condensed A', and the outer loop updates the condensed nodes X'. All these comprise the condensed small-scale graph T' = (X' A', Y'), where Y' is pre-defined based on the class distribution of the label space Y in the large- scale graph.
Overall, the above optimization objective needs to solve the following variables iteratively: (1) con- densed X': (2) condensed A' with GSL and (3) GNNe,,. Jointly learning these interdependent
3

---

Stage:: Groph Synthess
Stage2: Condensed Gruph free Evalsation
T- (X.A.))
-traiigg
0
Expert
0
0:¹
0.11
T.K
fg+11
Expert set: Po, (0/)
(0, R--1
Graph
Mete-matohiig trglering
metta-t -1
Grephh
1n+1
Dynamiic
i ro+
(NG Ks)
Avaluntion
G.V -ttraningg
gu
Sub-Graph Vea
Condensed graph-free data
Bock Propoaation & Updatt
Figure 2: Overall pipeline of the proposed Structure-Free Graph Condensation (SFGC) framework.
objectives is highly challenging. It is hard to guarantee that each objective obtains the optimal and convergent solution in such a complex and nested optimization process, resulting in the limited expressiveness of the condensed graph. This dilemma motivates us to reconsider the optimization objective of graph condensation synthesize the condensed graph more effectively.
Graph Neural Tangent Kernel (GNTK), As a new class of graph kernels, graph neural tangent kernel (GNTK) is easy to train with provable theoretical guarantees, and meanwhile, enjoys the full expressive power of GNNs 10
19 21 41 In general, GNTK can be taken as the infinitely -iide multi-layer GNNs trained by gradient descent. It learns class of smooth functions graphs with close-form solutions. More specifically, let G = (V, E) denote a graph with nodes V and edges E, where each node E V within its neighbor set (v)... Given two graphs G (V. E) and G² = (V', E') with n and n' number of nodes, their covariance matrix between input features can be denoted as Σ() (G,G') E IR Each element in [ (G, G') un' is the inner product h h.s where ha and h. are of input features of two nodes u E V and u' E V.. Then, for each GNN layer {0, 1,...,
L.} L that has fully-connected layers with ReLU activation, GNTK calculates
(0) G") for each B E [B]:
[ (G,G)) mn
| (G,G3) (0 (8)
[200 (G. (G.G)) um
(2)
(G, G")
ww!
where ()0) denotes the derivative w.rl the f-th GNN layer of the covariance matrix, and the (e+ 1) layer's covariance matrix aggregates neighbors along graph structures
(2(0 (C,
EmEN(uUU(a) EvENGwyUN 20 (G, pve ditto for the kernel
(((t)) (G, (G.G")
und" With
(0)
the GNTK matrix x((L) (G, E Baxn' the node level, we use the graph kernel method to solve the equivalent GNN model for node classification with closed-form solutions. This would significantly benefit the efficiency of condensed data evaluation by eliminating iterative GNN training.
2.2 Overview of SFGC Framework
The crux of achieving structure-free graph condensation is in determining discriminative node attribute contexts, which implicitly integrates topology structure information. We compare the paradigms between existing graph condensation (GC) and our new structure-free condensation SFGC as follows:
T (X Y) + T' = (X', A', Y'), GC.
(3)
T = (X,A - - = S (X, SFGC.

---

It is fundamentally different between existing GC paradigm with T + T' and our SFGC with T + S. Our idea is to synthesize graph-free data S (X.1, Y) whose topology is reduced to an identity matrix I (i.e., structure-free), instead of explicitly learning A a'as existing GC. To enforce node attribute X encoding topology structure information as X = (X, A), we propose long-term imitation learning process with training trajectories, which requires a GNN model learned from S, i.e. GNNs= GNN(X,, I, Y) must imitate a GNN model from the original graph, i.e. GNN, = GNN(X, A, Y). We provide more theoretical illustrations of the proposed structure-free graph condensation paradigm from the views statistical learning and information flow, respectively, in Appendix D The overall pipeline of the proposed Structure-Free Graph Condensation (SFGC) framework is shown in Fig.
We consider two coupled stages in the proposed SFGC framework, i.e., graph-free data synthesis ( ! 4 ) and condensed graph-free data evaluation ( ( ) corresponding to two essential components: (I) the training trajectory meta-matching scheme and (2) the graph neural feature score metric. Concretely, as illustrated Fig. taking the given large-scale graph 7 as input, we first (0) ) train
an expert set of G.NNT, parameterized by (07)=== {0;- 1=1 denoting K numbers of expert
training trajectories, each within T time steps. Then, we sample single expert training trajectory i at to step, i.e., 6% and further use it to initialize the model (@) ) GNNs trained by the condensed graph-free data S. Then, after steps of GNNs and p steps of GNN we conduct the meta-matching
( ( between the long-term intervals of training trajectories p 0 20o+ and 0% 0%o+p with the proposed meta- meta-matching loss Lmeta-tt. Next, the loss function back propapropssates along GNNs and the condensed graph-free data S is updated ( (Q). After, the updated S at the current step is used to calculate the GNTK-based graph neural feature score metric Ygni for dynamic evaluation (①), along with the large-scale validation subgraph T Finally, SFGC selects the optimal condensed graph-free data with the smallest 'ggr as the expressive substitution of the large-scale graph.
2.3 Training Trajectory Meta-matching
Different from existing graph condensation methods 27 26 that conduct online gradient matching within the short range, i.e., step-by-step or single-step matching gradients between the large-scale graph and the condensed graph, the proposed SFGC matches their long-term GNN training trajectories with the guidance of the offline expert parameter distribution. Concretely, inspired by 4.) we first train K numbers of GNN models with the same architecture denoted as GNN, on the large-scale T
{ - =(0;-) (=1
K =
graph T. Then, we save their network parameters
at certain epoch intervals,
resulting in K numbers of expert training trajectories that have comprehensive knowledge of the large-scale graph in terms of GNN's training process. Such expert training trajectories further build a parameter distribution Pe., denoting the GNN learning behavior on the large-scale graph. Note that such a parameter distribution is pre-caleulated and stored. Hence, this process can be offline and separated from the end-to-end graph condensation pipeline, moderately reducing the online computation costs.
By sampling from the pre-derived parameter distribution Per, we optimize the following objective for synthesizing S as:
min "Pe [mmetosa (0i1Emt O 0r1%
Note that 0, and O, i_ denote the parameters of GNN within the range of (fu, to + p) and GNNs within (Lo, to + q). respectively, where to < la + < T. More specifically, Lmeta- calculates
0% certain parameter training intervals within 0% totp
and ro O 0
0 to
0 to+p
Lueetau
(5)
2
0 0 .
||2
to+p
Here, we initialize the parameter of GNNs with that of GNN at ty training step, so that we have ord² O And we consider the expectation on S w.n.t different initialized parameter 0%,² in
5

---

Algorithm Structure-Freee Graph Condensation (SFGC)
Require: (1) per: Pretrained set of K numbers of GNNs the large-scale graph GNN1 parameterized by ry: (2) To: numbers of meta-matching steps; (3) Tı: GNNs training steps.
Ensure: A small-scale condensed graph-free data S
X, Y
1: while 1j < To do
2: randomly sample a pretrained training trajectory in Per and calculate the Cmeta-n according
to Eq. (5);
3: for ii do
H+1
-VVCCc [GNNS (x.1) Y..
4: train GNNs through gradient descent by Os
0s
where Ç is the step size;
5: end for
6: update the condensed graph-free data Sn according to Eq. (4)
7: calculate current 17-th step (S,) according to Eq.
8: end while
9: select the optimal condensed graph-free data S, with the smallest score 7gar as the final output.
distribution Per, which can be taken as a 'meta' way to make the distilled dataset S adapt different parameter initialization. That is why we call 'meta-matching" In this way, when initializing GNNT and GNNs with the same model parameters, Eq. (5) contributes to aligning the learning behaviors of GNNT that experiences p-steps optimization,
GNNs that experiences g-steps optimization. In this way, the proposed training trajectory meta-matching schema could comprehensively imitate the long-term learning behavior of GNN training. As result, the informative knowledge of the lcrge-scale graph T can be effectively transferred to the small-scale condensed graph-free free data
S (X, Y) in the above outer-loop optimization objective of Eq. 4
For the inner loop, we train GNNs on the synthesized small-scale condensed graph-free data for optimizing its model parameter until the optimal 0g. Therefore, the final optimization objective of the proposed SFGC
min R [meen (0:1E=tn.
(6)
s.t. 0. arg migCiss [GNN, (8)]
where Cots is the node classification loss calculated with the cross-entropy graphs. Compared with the triple-level optimization in Eq. (T). the proposed SFGC directly replaces the learnable A' in Eq. ( with a fixed identity matrix I, resulting in the condensed structure-frea graph data S = (X, I, Y). Without synthesizing condensed graph structures with GSLgg proposed SFGC refines the complex triple-level optimization to the bi-level one, ensuring effectiveness of the condensed graph-free data.
Hence, the advances of the training trajectory meta-matching schema in the proposed SFGC can be summarized as follows: (1) compared with the online gradient calculation, SFCC's offline parameter sampling avoids dynamically computing and storing gradients of both the large and condensed small graphs, reducing computation and memory costs during the condensation process; (2) compared with short-range matching, SFGC's long-term meta-matching avoids condensed data short-sightedly fit certain optimization steps, contributing to more holistic and comprehensive way to imitate GNN's learning behaviors.
2.4
Graph Neural Feature Score
For each update of the outer loop in Eq. (6). we would synthesize the brand-new condensed graph-free data. However, evaluating the quality the underlying condensed graph-free data in the dynamical meta-matching condensation process is quite challenging. That is because we cannot quantity graph dataset's performance without blending in a GNN model. And the condensed graph-free data itself cannot be measured by convergence or decision boundary. Generally, graph-free data, we use to train GNN model. If the condensed data at certain meta-matching step achieves better GNN test performance node classification, it indicates the higher quality of
evaluate the condensed

---

the current condensed data. That means, evaluating condensed graph-free data needs an extra process of training GNN model from scratch, leading to much more time and computation costs.
In light of this, we aim to derive a metric to dynamically evaluate the condensed graph-free data in the meta-matching process, and utilize it select the optimal small-scale graph-free data. Meanwhile, the evaluation progress would not introduce extra GNN iterative training for saving computation and time. To achieve this goal, we first identify what characteristics such metric should have: (1) closed-form solutions of GNNs to avoid iterative training in evaluation; (2) the ability to build strong connections between the large-scale graph and the small-scale synthesized graph-free data. In this case, the graph neural tangent kernel (GNTK) stands out, as typical class of graph kernels, and has the full expressive power of GNNs with provable closed-form solutions. Moreover, as shown in Eq. ( GNTK naturally builds connections between arbitrary two graphs even with different sizes.
Based the graph kernel method with GNTK, proposed graph neural feature score metric Yggff to dynamically evaluate and select the optimal condensed graph-free data as follows:
Vgnnt - vall K. (Tvll: 8) +1)) (D "
where KC S) I NNXNN' and K. SS E N denote the node-level GNTK matrices derived according to Eq. 2 And Tval is the validation sub-graph of the large-scale graph with Nval numbers of nodes. Concretely, (S) calculates the graph neural tangent kernel based ridge regression error. It measures that, given an -nfe GNN trained on the condensed graph S with ridge regression, how close such GNN's prediction on Tral to its ground truth labels Y Note that Eq. 7 can be regarded as the Kernel Inducing Point (KIP) algorithm GNTK kernel GNN models.
39 40 adapted to the
Hence, the proposed graph neural feature score meets the above-mentioned characteristics as: (1) it calculates a closed-form GNTK-based ridge regression error for evaluation without iteratively training GNN models; (2) it strongly connects the condensed graph-free data with the large-scale validation graph; In summary, the overall algorithm of the proposed SFGC is presented in Algo. [
3 Experiments
3.1 Experimental Settings
Datasets. Following 27), we evaluate the node classification performance of the proposed SFGC method on Cora, Citeseer [61], and Ogbn-arxiv [17] under the transductive setting, on Flickr [66] and Reddit [16] under the inductive setting. For all datasets under two settings, we use the public splits and setups for fair comparisons. We consider three condensation ratios (r) for each dataset. Concretely, r is the ratio of condensed node numbers (O < r < 1) to large-scale node numbers N. In the transductive setting, N represents the number of nodes in the entire large- scale graph, while in the inductive setting, N indicates the number of nodes in the training sub-graph of the whole large-scale graph. The dataset statistic details are shown in Appendix C
Baselines & Implementations. We adopt the following baselines for comprehensive compar- isons | graph coarsening method [20). graph coreset methods, i.e., Random, Herding (60, and K-Center (51), the graph-based variant DC-Graph of general dataset condensation method DC [77). which is introduced by [27] graph dataset condensation method GCOND (27 and its variant GCOND- X without utilizing the graph structure. The whole pipeline of our experimental evaluation can be divided into two stages: (I) the condensation stage: synthesizing condensed graph-free data, where GCN model [1]; (2) the condensed graph free data test
we use the classical and commonly stage: training certain GNN model (default with GCN) by the obtained condensed graph-fre data from the first stage and testing the GNN on the test set of the large-scale graph with repeated 10 times. We report the average transductive and inductive node classification accuracy (ACC%) with standard deviation (std). Following [27] we use the two-layer GNN with 256 hidden units as the defaulted setting. Besides, we adopt the K-center (5T) features to initialize our condensed node attributes for stabilizing the training process. Additional papper-prramter setting details are listed in Appendix E
7

---

Table 1: Node classification performance (ACC% comparison between condensation methods and other graph size reduction methods with different condensation ratios. (Best results in bold, and the second bests are u
Datasets
Raiio
Other Graph Sior Reduction Baseliner
Condensation Methodl
Whole Dutnee
Counsening
Random
Hending AJ
KeCine
DC DC-Graph
GCOND-X
GCOND
SPUC (ours)
44,4a4
52.4
71.4.08
70.5a1-2
Cheseer
59.0ke.
64.2617
64.3a12
88.N
70.6400
72.4.0.4
T1.7
69
663
31.2
63.617
67.0aa
62.02.1
75.9
79.8
80.1
2ano
72.8
732217
75 78.7
lana
81.7
81.2g09
5.29
70.6
76.8
7688
76.766
67.749
76.0gm
79.3468
81.6.0
0.055
47.1a39
52.4s1a
47.2
58.6004
61,3.0
59,211.1
65.5.8.7
Ogho-ansiv
0.25%
43.5
57.3
S
86.8
59 Sani
64.2en
63.2468
66.1
7g.4g0
0,5%
50,4am
60.0
60,4
60.3
59 5ana
63.1 Ja
64,0an
66.8:144
0,1%
41 41.9a12
418s20
42.5sta
42.0sa7
46 36n2
45. 9
46.5an.
46.6:0.22
Hickr
0,5%
44.5
44.0a0
43.5 43.9
43.2.6.
45.9 15.9
45.0an2
47.3am
47 Deb.i
40.2
18
44.5
44.6
44.4g0
44.1
458
45.0am
47.
47. 27.
0.05%
40.9
46, 1
53.s
46.622.1
88 2and
$8.6am4
88.0 18.0x1.8
89.7
Reddit
42.8
58.012
62.7ate
53.0...1
89.5
39.3am1
90.0...3
98.9uam
47.4
66.3e1
71.0st
58.5
58.
Ogha anddy
P1.3%
m4.
4516641 +3F222 12R6-45
157604 13R +856
# 13RC-42
KSKG41 5516642
#39044
Figure 3: Comparisons between five variants of synthesizing graph structures vs. our structure- free
SFGC (discrete & k-mearesi neighbor (kNN) structure variants: SPCC-d1 (k = 1). SPCC- (k 2), and SPCC d5 (k 5), continuous graph
structure variant: SPOC-c, purameterized graph structure variant: SPCC-p).
3.2 Experimental Results
Performance of SFGC on Node Classification. We compare the node classification performance between SFGC and other graph size reduction methods, especially the graph condensation methods. The overall performance comparison is listed in Table I Generally, SFCC achieves the best per- formance the node classification task with 13 of 15 cases (five datasets and three condensation ratios for each of them), compared with all other baseline methods, illustrating the high quality and expressiveness of the condensed graph-free data synthesized by our SFGC. More specifically, the better performance of SFGC than GCOND and its structure-free variant GCOND-X experimentally verifies the superiority of the proposed method. We attribute such superiority to the following two aspects regarding the condensation stage. First, the long-term parameter distribution matching of our SFGC works better than the short-term gradient matching in GCOND and GCOND-X. That means capturing the long-range GNN learning behaviors facilitates to holistically imitate GNN's training process, leading to comprehensive knowledge transfer from the large-scale graph to the small-scale condensed graph-free data. Second, the structure-fire free paradigm of our SFGC enables more compact small-scale graph-free data. For one thing, it liberates the optimization process from triple-level objectives, alleviating the complexity and difficulty of condensation. For another thing. the obtained optimal condensed graph-free data compactly integrates node attribute contexts and topology structure information. Furthermore, on Cora and Citeseer, SFGC synthesizes better condensed graph-free data that even exceeds the whole large-scale graph dataset. These results confirm that SFGC is able to break the information limitation under the large-scale graph and effectively synthesize new, small-scale traph-free data as an optimal representation of the large-scale graph.
Effectiveness of Structure-free Paradigm in SFGC. The proposed SFGC introduces the structure- free paradigm without condensing graph structures in graph condensation. To verify the effectiveness of the structure- free paradigm, we compare the proposed SFGC with its variants, which synthesize graph structures in the condensation process. Specifically, we evaluate the following three different methods of synthesizing graph structures with five variants of SFGC: (1) discrete k-nearest neighbor
(kNN) structures calculated by condensed node features under k = (1, 2, 5), corresponding to the
variants SFGC-d1, SFGC-d2, and SFGC-d5; (2) cosine similarity based continuous graph structures
8

---

Table 2: Performance across different GNN architectures.
Dotavets (Ratio)
Methods
ML.P
GAT
APPNP
GCN
SOC
Avg:
DC-Gragh x
66.2
66.4
61.9
66.2
65.9
69.6
66.6
Ciseseer
GOOND X S
69.6
69.7
70.5
69.7
69.2
71,6
70.2
1.8%)
GCOND (ours)
63.9
55,4
69.6
68.3
70.5
66.2
70.3
69.0
DC-Gragh bd
67.2
67.1
67.7
67.9
66.2
72.8
68.3
Cora
GCOND X bu
76.0
77.0
74,1
75.3
76.0
76.1
75.7
2.0%)
GCOND (ours)
73.1
66.2
78.5
76.0
80.1
78.2
79.3
78.4
DC-Gragh bd
59.9
60.0
55.7
59.8
60.0
60.4
59.2
Oghn-arsiv
GCOND X
64.1
61.5
59.5
64.2
64.4
64.7
62.9
0.25%))
GCOND (ours)
62.2
60,0
63.4
54,9
62.6
63.7
61.6
DC-Gragh bd
43.1
45.7
43.8
45.9
45.8
45.6
45.4
Flickr
GCOND X bz
42.1
44.6
42.3
45.0
44.7
44,4
44,2
0.5%)
GCOND
14.8
45,9
42.8
47.1
46.2
46.1
45.6
SFCD (ours)
40.7
DC-Gragh bd
50.3
81.2
77.5
89.5
89.7
90.5
85.7
Reddit
GCOND X
40.1
78.7
74.0
89.3
89.3
91.0
84.5
0.156)
GOOND
42.5
75.5
86.3
SFCD (ours)
90.3
calculated by condensed node features, corresponding to the variant SFGC-c; (3) parameterized graph structure learning module with condensed node features adapted by 127 corresponding to the variant SFGC-p. We conduct experiments on three transductive datasets under nine condensation ratios for each graph structure synthesis variant and the proposed SFGC. The results are presented in Fig. [3] In general, the proposed SFGC achieves the best performance over various graph structure synthesis methods, and these results empirically verify the effectiveness of the proposed structure- free condensation paradigm. More specifically, for discrete k-nearest neighbor (kNN) structure variants, different datasets adapt different numbers k-nearest neighbors under different condensation ratios, which means predefining the value of k can be very challenging. For example, Citeseer dataset has better performance with k = 1 in SFGC-d1 under r = 0.9% than SFGC-d2 and SFGC-d5, but under 1.8%, k in SFGC-d2 performs better than others two. Besides, for continuous graph structure variant SFGC-c, generally cannot exceed the discrete graph structure variants, except for Ogbn-arxiv dataset under 0.05%. And the parameterized variant SFGC-p almost fails synthesize satisfied condensed graphs under the training trajectory meta-man meta-matching scheme. The superior performance of SFGC to all structure-basee based methods demonstrates the effectiveness of its structure- free paradigm.
Effectiveness of Graph Neural Feature Score in SFGC. We compare the learning time between GNN iterative training our proposed GNTK-based closed-form solutions of Tgaf- Note that the iterative training evaluation strategy mandates the complete training scratch at each meta-matching step, hence, we calculate its time that covers all training epochs under the best test performance for fair comparisons. Typically, for Flickr dataset (r = 0.1%), our proposed 'guf based GNTK closed-form solutions takes only 0.015s for dynamic evaluation, which significantly outperforms the iterative training evaluation with 0.845s. The superior performance can also be observed in Ogbn-arxiv dataset (r 0.05%) with 0.042s of our Ygníí compared with 4.264s of iterative training, illustrating our SFGC's s high dynamic evaluation efficiency. More results and analysis of our proposed Ygt in GNTK- closed- solutions can be found in Appendix.
GNN model from
Generalization Ability of SFGC across Different GNNs. We evaluate and compare the general- ization ability of the proposed SFGC and other graph condensation methods. Concretely, we test the node classification performance our synthesized graph-free free data (condensed on GCN) with seven different GNN architectures: MLP, GAT (56), APPNP 14]. Cheby 77. GCN (61) SAGE [16), and SGC [63] It can be generally observed that the proposed SFGC achieves outstanding performance over all tested GNN architectures, reflecting its excellent generalization ability. This is because method reduces the graph structure to the identity matrix, so that the condensed graph node set can no longer be influenced by different convolution operations of GNNs along graph structures, enabling it consistent and good performance with various GNNs.
More experimental analysis and discussions, including the effects of different ranges of long-term meta-matchon matching, the performance on downstream unsupervised graph clustering task, visualization of condensed structure-fret free node set, well as time complexity analysis, detailed in Appendix

---

4 Conclusion
This work proposes a novel Structure-Free Graph Condensation paradigm, named SFGC, to distill the large-scale graph into the small-scale graph-free node set without graph structures. Under the structure- learning paradigm, the training trajectory meta-mater mntaa-mtchinng scheme and the graph neural feature measured dynamic evaluation work collaboratively to synthesize small-scale graph-free freh-ffree data with superior effectiveness and good generalization ability. Extensive experimental results and analysis under large condensation ratios confirm the superiority of the proposed SFGC method in synthesizing excellent small-scale graph-free data. can be anticipated that our work would bridge the gap between academic GNNs and industrial ML.Ps by synthesizing small-scale, graph-free data to address graph data scalability, while retaining the expressive performance of graph learning. Our method works on condensing the number of nodes in single graph at the node level, and we will explore extending it to condense the number of graphs in a graph set at the graph level in the future. We will also explore the potential of unifying graphs and large language models 4M for the graph condensation task.
Acknowledgment
In this work, S. Pan was supported by an Australian Research Council (ARC) Future Fellowship (FT210100097), and M. Zhang was supported by National Natural Science Foundation of China (NSFC) grant (62306084). This research is partially sponsored by the U.S. National Science Founda- tion through Grant No 130228..
References
[1] Joshua Batson, Daniel A Spielman, Nikhil Srivastava, and Shang- Hua Teng. 2013. Spectral Sparsification of Graphs: Theory and Algorithms. Commun. ACM 56, (2013), 87-94.
[2] Davide Buffelli, Pietro Lio, and Fabio Vandin. 2022. SizeShiftReg: Regularization Method for Improving Geeeraeerrliinoonnn in Graph Neural Networks. In Advances in Neural Information Processing Systems (NeurIPS).
[3] Chen Cai, Dingkang Wang, and Yusu Wang. 2020. Graph Coarsening with Neural Networks. In International Conference on Learning Representaaiion(/CCRR))
[4] George Cazenavette, Tongzhou Wang, Antonio Torralba, Alexei A Efros, and Jun- Yan Zhu. 2022. Dataset Distillation by Matching Training Trajectories. In Proceedings of the IEEF/CVF Conference Computer Vision and Pattern Recognition (CVPR). 4759.
[5] Tianlong Chen, Yongduo Sui, Xuxi Chen, Aston Zhang, and Zhangyang Wang. 2021. A Unified Lottery Ticket Hypothesis For Graph Neural Networks. In International Conference on Machine Learning (ICML). PMLR, 1695-1706.
[6] Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsich, 2019. Cluster- GCN: An Efficient Algorithm For Training Deep And Large Graph Convolutional Networks. In Proceedings of the 25th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (SIGKDD). 257-266.
[7] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. 2016. Convolutional Neural Networks Graphs with Fast Localized Spectral Filtering. Advances in Neural Information Processing Systems (NeurIPS) 29 (2016).
[8] Zhiwei Deng and Olga Russakovsky. 2022. Remember the Past: Distilling Datasets into Addressable Memories for Neural Networks. In Advances in Neural Information Processing Systems (NeurIPS).
[9] Mucong Ding, Xiaoyu Liu, Tahseen Rabbani, and Furong Huang. 2022. Faster Hyperparameter Search on Graphs via Calibrated Dataset Condensation. NeurIPS 2022 Workshop: New Frontiers in Graph Learning.
10

---

[10] Simon S Du, Kangcheng Hou, Russ R Salakhutdinov, Barnabas Poczos. Ruosong Wang, and Keyulu Xu. 2019. Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels. Advances in Neural Information Processing Systems (NeurIPS) 32 (2019).
[11] Yichao Du, Pengfei Luo, Xudong Hong, Tong Xu, Zhe Zhang, Chao Ren, Yi Zheng, and Enhong Chen. 2021. Inheritance-gunt gaaeeneeeeguedddded hierarchical assignment for clinical automatic diagnosis. In International Conference on Database Systems for Advanced Applications (DASFAA). Springer, 461-477.
[12] Falih Gozi Febrinanto, Feng Xia, Kristen Moore, Chandra Thapa, and Charu Aggarwal. 2023, Graph lifelong learning: A survey. IEEE Computational Intelligence Magazine 18, (2023), 32-51.
[13] Yang Gao, Hong Yang. Peng Zhang, Chuan Zhou, and Yue Hu. 2020. Graph Neural Architecture Search.. In International Joint Conferences Artificial Intelligence (ICAAI, Vol. 20. 1403- 1409.
[14] Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. 2018. Predict then Propagate: Graph Neural Networks Meet Personalized PageRank. In International Conference on Learning Representations (ICLR).
[15] Viresh Gupta and Tanmoy Chakraborty. 2021. VIKING: Adversarial Attack on Network Embeddings via Supervised Network Poisoning. Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining (PAKDD). Springer, 103-115.
[16] Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive Representation Learning on Large Graphs. Advances in Neural Information Processing Systems (NeurlPS) 30 (2017).
[17) Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. 2020. Open Graph Benchmark: Datasets for Machine Learning on Graphs. Advances in Neural Information Processing Systems (NeurIPS) 33 (2020), 22118- 22133.
[18] ZHAO Huan, YAO Quanming, and TU Weiwei. 2021. Search to aggregate neighborhood for graph neural network. In International Conference on Data Engineering (ICDE). IEEE, 552-563.
[19] Wei Huang, Yayong Li, Richard Xu, Jie Yin, Ling Chen, Miao Zhang, et al. 2021. Towards Deepening Graph Neural Networks: A GNTK-based Optimization Perspective. In International Conference Learning Representations (ICLR).
[20] Zengfeng Huang, Shengzhong Zhang, Chong Xi, Tang Liu, and Min Zhou. 2021. Scaling up Graph Neural Networks Via Graph Coarsening. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining (SIGKDD). 675-684.
[21] Arthur Jacot, Franck Gabriel, and Clément Hongler. 2018. Neural Tangent Kernel: Convergence and Generalization in Neural Networks. Advances in Neural Information Processing Systems (NeurIPS) 31 (2018).
[22] Ming Jin, Yuan-Fang Li, and Shirui Pan. 2022. Neural Temporal Walks: Motif-Aware Repre- sentation Learning on Continuous-Tine Dynamic Graphs. In Advances in Neural Information Processing Systems (NeurIPS).
[23] Ming Jin, Shiyu Wang, Lintao Ma, Zhixuan Chu, James Y Zhang, Xiaoming Shi, Pin-Yu Yu Chen, Yuxuan Liang, Yuan-Fang Li, Shirui Pan, al. 2023. Time-LLM: Time Series Forecasting by Reprogramming Large Language Models, arXiv preprint arXiv:2310.01728 (2023).
[24] Ming Jin, Qingsong Wen, Yuxuan Liang, Chaoli Zhang, Siqiao Xue, Xue Wang, James Zhang, Yi Wang. Haifeng Chen, Xiaoli Li, Shirui Pan, Vincent S. Tseng, Yu Zheng, Lei Chen, and Hui Xiong. 2023. Large Models for Time Series and arXiv preprint arXiv:2310.101 (2023).
Data: A Survey and Outlook.
11

---

[25] Ming Jin, Yu Zheng, Yuan-Fang Li, Siheng Chen, Bin Yang, and Shirui Pan. 2022. Multivariate Time Series Forecasting with Dynamic Graph Neural ODEs. IEEE Transactions on Knowledge and Data Engineering (TKDE) (2022).
[26] Wei Jin, Xianfeng Tang, Haoming Jiang, Zheng Li, Danqing Zhang, Jiliang Tang, and Bing Yin. 2022. Condensing Graphs Via One-Step Gradient Matching. In Pruceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (SIGKDD), 720-730.
[27] Wei Jin, Lingxiao Zhao, Shichang Zhang, Yozen Liu, Jiliang Tang, and Neil Shah. 2021. Graph Condensation For Graph Neural Networks. In International Conference on Learning Representations (ICLR).
[28) Yu Jin, Andreas Loukas, and Joseph JaJa. 2020. Graph Coarsening With Preserved Spectral Properties. In International Conference on Artificial Intelligence and Statistics (ICAIS). PMLR, 4452-4462.
[29] Thomas Kipf and Max Welling. 2016. Variational graph auto-encoders, In In Neural Informa- tion Processing Systems Workshop. 1-3.
[30] Shiye Lei and Dacheng Tao. 2023. A Comprehensive Survey to Dataset Distillation. arXiv preprint arXiv:2301.0566 006603 (2023).
[31] Huihui Liu, Yiding Yang, and Xinchao Wang. 2021. Overcoming catastrophic forgetting in graph neural networks. In Proceedings of the Association for the Advanced of Artificial Intelligence (AAAI), Vol. 35. 8653-8661.
[32] Yixin Liu, Kaize Ding, Jianling Wang. Vincent Lee, Huan Liu, and Shirui Pan. 2023. Learn- ing Strong Graph Neural Networks with Weak Information. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD).
[33] Yixin Liu, Ming Jin, Shirui Pan, Chuan Zhou, Yu Zheng, Feng Xia, and Philip Yu. 2022. Graph Self-supervised Learning: A Survey. IEEE Transactions on Knowledge and Data Engineering (TKDE) (2022).
[34] Yixin Liu, Zhao Li, Shirui Pan, Chen Gong, Chuan Zhou, and George Karypis. 2021. Anomaly Detection on Attributed Networks Via Contrastive Self-supervised Learning. IEEE Transactions on Neural Networks and Learning Systems (TNNLS) 33, (2021), 2378-2392.
[35] Yixin Liu, Yu Zheng, Daokun Zhang, Hongxu Chen, Hao Peng, and Shirui Pan. 2022. Towards unsupervised deep graph structure learning. In Proceedings of the ACM Web Conference (WWW). 1392-1403.
[36] Yixin Liu, Yizhen Zheng, Daokun Zhang, Vincent Lee, and Shirui Pan. 2023. Beyond Smooth- ing: Unsupervised Graph Representation Learning with Edge Heterophily Discriminating. In Proceedings of the Association for the Advanced of Artificial Intelligence (AAAI).
[37] Linhao Luo, Yuan-Fang Li, Gholamreza Haffari, and Shirui Pan. 2023. Normalizing flow-base neural process for few-shot knowledge graph completion. In The 46th International ACM SIGIR Conference Research and Development in Information Retrieval.
[38] Linhao Luo, Yuan-Fang Li, Gholamreza Haffari, and Shirui Pan. 2023. Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning. arXiv preprint arxiv:2310.0166/ (2023).
[39] Timothy Nguyen, Zhourong Chen, and Jachoon Lee. 2020. Dataset Meta-Learning from Kernel Ridge-Regression. In International Conference on Learning Representations (ICLR).
[40] Timothy Nguyen, Roman Novak, Lechao Xiao, and Jachoon Lee. 2021. Dataset Distillation with Infinitlly Wide Convolutional Networks. Advances in Neural Information Processing Systems (NeurIPS) 34 (2021), 5186-5198.
[41] Roman Novak, Jascha Sohl-Dickstein, and Samuel S Schoenholz. 2022. Fast Finite Width Neural Tangent Kernel. In International Conference on Machine Learning (ICML). PMLR, 17018-17044.
12

---

[42] Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, Lina Yao, and Chengqi Zhang. 2018. Adver- sarially regularized graph autoencoder for graph embedding. Proceedings of International Joint Conference Artificial Intelligence (IJCAI). 2615-2615.
[43] Shirui Pan, Linhao Luo, Yufei Wang, Chen Chen, Jiapu Wang, and Xindong Wu. 2023. Unifying Large Language Models and Knowledge Graphs: A Roadmap. arXiv preprint arxiv:2306.08332 (2023).
[44] Shirui Pan, Yizhen Zheng, and Yixin Liu. 2023. Integrating Graphs with Large Language Models: Methods and Prospects. arXiv preprint arXiv:2310.05499 (2023).
[45] German Parisi, Ronald Kemker, Jose L Part, Christopher Kanan, and Stefan Wermter. 2019. Continual lifelong learning with neural networks: A review. Neural networks 113 (2019), 54-71.
[46] Yijian Qin, Xin Wang, Zeyang Zhang, and Wenwu Zhu. 2021. Graph differentiable architecture search with structure learning. In Advances in Neural Information Processing Systems (NeurIPS), Vol. 34. 16860-16872.
[47] Sylvestre-Alvise Rebuffi, Alexander Kolesnikov, Georg Sperl, and Christoph H Lampert. 2017. iCaRL: Incremental Classifier and Representation Learning. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition (CVPR). 2001-2010.
[48] Andrea Rosasco, Antonio Carta, Andrea Cossu, Vincenzo Lomonaco, and Davide Bacciu. 2022. Distilled replay: Overcoming forgetting through synthetic samples. In Continual Semi- Supervised Learning: First International Workshop (CSSL). Springer, 104-117.
[49] Noveen Sachdeva and Julian McAuley. 2023. Data Distillation: A Survey. arXiv preprint arXiv:2301.04272 (2023).
[50] Mattia Sangermano, Antonio Carta, Andrea Cossu, and Davide Bacciu. 2022. Sample con- densation in online continual learning. In International Joint Conference on Neural Networks (JJCNN. IEEE, 01-08.
[51] Ozan Sener and Silvio Savarese. 2018. Active Learning for Convolutional Neural Networks: A Core-Set Approach. In International Conference on Learning Representations (ICLR).
[52] Junyuan Shang. Tengfei Ma, Cao Xiao, and Jimeng Sun. 2019. Pre-training of graph augmented transformers for medication recommendation. In International Joint Conference Artificial Intelligence (ICCAI). 5953-5959.
[53] Yiwei Sun, Suhang Wang, Xianfeng Tang, Tsung- Yu Hsich, and Vasant Honavar. 2020. Ad- versarial attacks on graph neural networks via node injections: hierarchical reinforcement learning approach. In Proceedings of the Web Conference (WWW). 673-683.
[54] Yue Tan, Yixin Liu, Guodong Long, Jing Jiang, Qinghua Lu, and Chengqi Zhang. 2023. Federated learning on non-iid graphs via structural knowledge sharing. In Proceedings of the AAAI conference on artificial intelligence, Vol. 37. 9953-9961.
[55] Laurens Van der Maaten and Geoffrey Hinton. 2008. Visualizing Data Using t-SNE. Journal of Machine Learning Research 9, 11 (2008).
[56] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. 2018 Graph Attention Networks. In International Conference on Learning Representations (ICLR).
[57] Wang, Pan. R Hu, G Long, J Jiang, and Zhang, 2019. Attributed Graph Clustering: A Deep Attentional Embedding Approach. In Proceedings of International Joint Conference on Artificial Intelligence (ICCAT).
[58] Chun Wang. Shirui Pan, Guodong Long, Xingquan Zhu, and Jing Jiang. 2017. Mgae: Marginal- ized graph autoencoder for graph clustering. Proceedings of ACM on Conference on Informa- tion and Knowledge Management (CIKM). 889-898.
13

---

[59] Tongzhou Wang, Jun-Yan Zhu, Antonio Torralba, and Alexei A Efros. 2018. Dataset Distillation. arXiv preprint arXiv:1811.10953 (2018).
[60] Max Welling. 2009. Herding Dynamical Weights to Learn. In International Conference on Machine Learning (ICML). 1121-1128.
[61] Max Welling and Thomas N Kipf. 2017. Semi-supervised Classification with Graph Convolu- tional Networks. In International Conference on Learning Representations (ICLR).
[62] Felix Wiewel and Bin Yang. 2021. Condensed composite memory continual learning. In International Joint Conference on Neural Networks (IJCNN). IEEE, 1-8.
[63] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. 2019. Simplifying Graph Convolutional Networks. In International Conference Machine Learning (ICMI.). PMLR, 6861-6871
[64] Zhe Xu, Boxin Du and Hanghang Tong, 2022. Graph Sanitation with Application to Node Classification. In Proceedings of the ACM Web Conference (WWW). 1136-1147.
[65] Qiao Yuan, Sheng-Uei Guan, Pin Ni, Tianlun Luo, Ka Lok Man, Prudence Wong, and Victor Chang. 2023, Continual Graph Learning: A Survey, arXiv preprint 1rxXiv:3301.222:0 (2023).
[66] Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. 2019. GraphSAINT: Graph Sampling Based Inductive Learning Method. In International Conference on Learning Representations (ICLR).
[67] He Zhang, Bang Wu, Shuo Wang, Xiangwen Yang. Minhui Xue, Shirui Pan, and Xingliang Yuan. 2023, Demystifying uneven vulnerability of link stealing attacks against graph neural networks. In International Conference on Machine Learning. PMLR, 41737-41752.
[68] He Zhang, Bang Wu, Xingliang Yuan, Shirui Pan, Hanghang Tong, and Jian Pei. 2022. Trustwor- thy Graph Neural Networks: Aspects, Methods and Trends. arXiv preprint arXiv:2205.07422 (2022).
[69] He Zhang, Xingliang Yuan, Quoc Viet Hung Nguyen, and Shirui Pan. 2023. On the inter- action between node fairness and edge privacy in graph neural networks. arXiv preprint arXiv:2331. / (2023).
[70] He Zhang, Xingliang Yuan, Chuan Zhou, and Shirui Pan. 2022. Projective ranking-based gnn evasion attacks. IEEE Transactions Knowledge and Data Engineering (TKDE) (2022).
[71] Miao Zhang. Shirui Pan, Xiaojun Chang. Steven Su, Jilin Hu, Gholamreza Reza Haffari, and Bin Yang. 2022. BaLeNAS: Differentiable Architecture Search Via the Bayesian Learning Rule. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR). 11871-11880.
[72] Miao Zhang, Steven W Su, Shirui Pan, Xiaojun Chang, Ehsan M Abbasnejad, and Reza Haffari. 2021. iDARTS: Differentiable Architecture Search with Stochastic Implicit Gradients. In International Conference on Machine Learning (ICML). PMLR, 12557-12566.
[73] Shichang Zhang, Yozen Liu, Yizhou Sun, and Neil Shah. 2021. Graph-less Neural Networks: Teaching Old MLPs New Tricks Via Distillation. In International Conference on Learning Representations (ICLR).
[74] Wentao Zhang, Ziqi Yin, Zeang Sheng, Yang Li, Wen Ouyang, Xiaosen Li, Yangyu Tao, Zhi Yang, and Bin Cui. 2022. Graph Attention Multi-Layer Perceptron. In Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining (SIGKDD).
[75] Xiaotong Zhang, Han Liu, Qimai Li, and Xiao Ming Wu. 2019. Attributed graph clustering via adaptive graph convolution. In Proceedings of International Joint Conference on Artificial Intelligence (IJCAI). 4337-4333
(76) Bo Zhao and Hakan Bilen. 2023. Dataset Condensation with Distribution Matching. In IEEE/CVF Winter Conference Applications of Computer Vision (WACV).
14

---

[77] Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. 2020. Dataset Condensation with Gradient Matching. In International Conference on Learning Representations (ICLR).
[78] Xin Zheng, Yixin Liu, Zhifeng Bao, Meng Fang, Xia Hu, Alan Wee-Chung Liew, and Shirui Pan. 2023. Towards Data-centric Graph Machine Learning: Review and Outlook. arXiv preprint arXiv:2309.10977 (2023).
[79] Xin Zheng, Yixin Liu, Shirui Pan, Miao Zhang, Di Jin, and Philip S Yu. 2022. Graph Neural Networks for Graphs with Heterophily: A Survey. arXiv preprint
(2022).
[80] Xin Zheng, Miao Zhang, Chunyang Chen, Chaojie Li, Chuan Zhou, and Shirui Pan. 2022. Multi-relational Graph Neural Architecture Search with Fine-grained Message Passing. In IEEE International Conference on Data Mining (ICDM).
[81] Xin Zheng, Miao Zhang, Chunyang Chen, Qin Zhang, Chuan Zhou, and Shirui Pan. 2023, Auto- heg: Automated graph neural network on heterophilic graphs. arXiv preprint arXiv:2302.12355 (2023).
[82] Yizhen Zheng, Shirui Pan, Vincent Cs Lee, Yu Zheng, and Philip S Yu. 2022. Rethinking and Scaling Up Graph Contrastive Learning: An Extremely Efficient Approach with Group Discrimination. Advances in Neural Information Processing Systems (NeurIPS).
[83] Fan Zhou and Chengtai Cao. 2021. Overcoming catastrophic forgetting in graph neural net- works with experience replay. In Proceedings of the Association for the Advanced of Artificial Intelligence (AAAI), Vol. 35. 4714
[84] Daniel Zügner and Stephan Günnemann. 2019, Adversarial Attacks on Graph Neural Networks via Meta Learning. In International Conference on Learning Representations (ICLR).
15

---

Appendix
This the appendix of our work: 'Structure-free Graph Condensation: From Large-scale Graphs to Condensed Graph-free Data'. In this appendix, we provide more details of the proposed SFGC in terms of related works, potential application scenarios, dataset statistics, method analysis, and experimental settings with some additional results.
A Related Works
Dataset Distillation (Condensation) aims to synthesize a small typical dataset that distills the most important knowledge from given large target dataset, such that the synthesized small dataset could serve as an effective substitution of the large target dataset for various scenarios [30 49 e.g.,
model training and inference, architecture search, and continue learning. Typically, DD
15 and
DC-KRR (39] adopted the meta-learning framework to solve bi-level distillation objectives through calculating meta-gradients. In contrast, DC [77]. DM (76), and MTT 4 designed surrogate functions to avoid unrolled optimization through the gradient matching, feature distribution matching, and training trajectory matching, respectively, where the core idea is to effectively mimic the large target dataset in the synthesized small dataset. Except for the image data condensed by the above-mentioned works, GCOND (27] first extended the online gradient matching scheme in DC (77] to structural graph data, along with parameterized graph structure learning module to synthesize condensed edge connections. Furthermore, DosCond [26] proposed single-step gradient matching to synthesize graph nodes, with a probabilistic graph model to condense structures on the graph classification task. In this work, eliminate the process of synthesizing graph structures and propose novel structure-free graph condensation paradigm, to distill the large-scale graph to the small-scale graph- free data, leading to the easier optimization process of condensation. Meanwhile, the structure-free characteristic allows condensed data better generalization ability to different GNN architectures.
Graph Size Reduction aims to reduce the graph size to fewer nodes and edges for effective and efficient GNN training, including graph sampling [66 6 graph coreset 47 60 graph sparsifica-
tion 5) graph coarsening 3 28), and recently rising graph condensation [27 26]. Concretely,
graph sampling methods [66] 6 and graph coreset methods [47] 60) sample or select the subset
of nodes and edges from the whole graph, such that the information of the derived sub-graph is constrained by the whole large-scale graph, which considerably limits the expressiveness of the size-reduced graph. Moreover, graph sparsification methods 5 and graph coarsening methods 3 [1] reduce the number of edges and nodes by simplifying the edge connections and grouping node representations of the large-scale graph, respectively. The core idea of both sparsification and coarsening is to preserve specific large-scale graph properties (e.g., spectrum and principle eigenvalues) in the sparse and coarsen small graph. The preserved graph properties in the small-scale graph, however, might not be suitable for downstream GNN tasks. In contrast, our work focuses on graph condensation to directly optimize and synthesize the small-scale condensed data, which breaks information constraints of the large-scale graph and encourages consistent GNN test performance.
B Potential Application Scenarios
We would like to highlight the significance of graph condensation task to various application scenarios within the research field of dataset distillation/condeesatiooo while comprehensive overviews can be found in survey works 30 [9]. Specifically, we present several potential scenarios where our proposed structure-free graph condensation method could bring benefits:
Graph Neural Architecture Search. Graph neural architecture search (GraphNAS) aims develop potential and expressive GNN architectures beyond existing -demanddesigne GNNs. By automatically searching in space containing various candidate GNN architecture components, GraphNAS could derive powerful and creative GNNs with superior performance on specific graph datasets for specific
tasks [0 8I 46 13 18. Hence, GraphNAS needs to repeatedly train different potential GNN architectures on the specific graph dataset, and ultimately selects the optimal one. When in the large-scale graph, this would incur severe computation and memory costs. this case, searching on our developed small-scale condensed graph-free data, representative substitution of the large-scale graph, could significantly benefit for saving many computation costs and accelerating new GNN architecture development in GraphNAS research field.
16

---

Privacy Profection. Considering the outsoureing scenario of graph learning tasks, the original large-scale graph data is not allowed release due to privacy, for example, patients expect to use GNNs for medical diagnosis without their personal medical profiles being leaked [22 I1]. In this case, as compact and representative substitution, the synthesized small-scale condensed graph could be used to train GNN models, so that the private information of the original graph data can be protected. Besides, considering the scenario that wer-pparaeterized GNNs might easily memorize training data, inferring the well-trained models could cause potential privacy leakage issue. In this case, we could release a GNN model trained by the synthesized small-scale condensed graph, so that the model avoids explicitly training the original large-scale graph and consequently helps protect its data privacy.
Ad Adversarial Robustness. In practical applications, GNNs might be attacked with disrupted perfor- mance, when attackers impose adversarial perturbations to the original graph data [68], for instance, poisoning attacks on graph data (58] 15 [4], where attackers attempt to alter the edges and nodes of training graphs of target GNN. Training on poisoned graph data could significantly damage GNNs' performance. In this case, given poisoned original training graph, graph condensation could synthe- size a new condensed graph from it, which we use to train the target GNN would achieve comparable test performance with that trained by the original training graph before being poisoned. Hence, the new condensed graph could eliminate adversarial samples in the original poisoned graph data with great adversarial robustness, so that using to train a GNN would not damage its performance for inferring test graphs.
Continual learning (CL) aims to progressively accumulates knowledge over a continuous data stream to support future learning while maintaining previously learned informa- One of key challenges of CL is catastrophic forgetting [31 833. where knowledge extracted and learned from old data/tasks are easily forgotten when new information from new data/tasks are learned. Some works have studied that data distillationccondensatioi is an effective solution to alleviate catastrophic forgetting [8] 48 50 62) where the distilled and condensed data is taken representative summary stored in replay buffer that is continually updated to instruct the training of subsequent data/tasks.
Continual learning.
tion 455 12 65
To summarize, graph condensation task holds great promise and is expected to bring significant benefits to various graph learning tasks and applications. By producing compact, high-quality. small-scale condensed graph data, graph condensation has the potential to enhance the efficiency and effectiveness of future graph machine learning works.
C Dataset Details
We provide the details of the original dataset statistics in Table AT Moreover, we also compare the statistics of our condensed graph-free data with GCOND [27 condensed graphs in Table [A]] It can be observed that both GCOND (27) and our proposed SFGC significantly reduce the numbers of nodes and edges from large-scale graphs, as well as the data storage. Importantly, our proposed SFGC directly reduces the number of edges to 0 by eliminating graphs structures in the condensation process, but with superior node attribute contexts integrating topology structure information.
Table A1: Details of dataset statistics.
Datasets
#Nodes
#Edges
#Classes
#Features
Train/Val/Test
Cora
2,708
5,429
7
1,433
140/500/ 1000
Citeseer
3,327
4,732
6
3,703
1 120/500/
Ogbn-arxiv
169,343
1.166,243
40
128
90,941/29,7990 799/486003
Flickr
89,250
899.756
7
500
44.625/22311/222311
Reddit
232.965
57,307.946
41
602
15.3992/22.699/5553344
D More Analysis of Structure-free Paradigm
In this section, we theoretically analyze the rationality of the proposed structure-free paradigm from the views of statistical learning and information flow, respectively.
17

---

Table A2: The statistic comparison of condensed graphs by GCOND +i data by our SFCC.
and condensed graph-free
Diiae
Clower ln 2,09)
Oven Ir 2/P1
15 - 1.11
Whek:
GOUNDE
Whrk:
GEUNN 11
5997
Whek
GOUNU
GCUN FC
8590 (ours)
Wink
4Node
3327
60
2.788
70
TD
168343
454
46.025
223
223
153/02
153
153
Spanity
0009
80 13
0.15
15.28%
5,0%
01079
15.2%
0,39%
2.5%
Skango
5.5H
The View of Statistical Learning. We start from the graph condensation optimization objective of synthesizing graphs structures in Eq. (1) of the main submission. Considering its inner loops T arg minC [GNN, (X', AA), Y'I with A' GSL (X'), it equals to learn the conditional
0 probability Q(Y' IT) given the condensed graph T' = (X', A', Y') as
Q(Y' (T) ~ Σ
Q(Y' X', A')Q'' X')
A'E
Σ
A
(8)
E
A
(Q(X','')/QO = Q(Y'
where we simplify the notation of graph structure learning module GSL as parameterized &b (X'). As can be observed, when the condensed graph structures are learned from the condensed nodes as A' E ub (X'), the optimization objective of the conditional probability is not changed, while its goal is still to solve the posterior probability Q(Y" X'). In this way, eliminating graph structures to conduct structure- free condensation is rational from the view of statistical learning. By directly synthesizing the graph-free data, the proposed SFGC could ease the optimization process and directly transfer all the informative knowledge of the large-scale graph to the condensed graph node set without structures. Hence, the proposed SFGC conducts more compact condensation to derive the small-scale graph-free data via Eq. (6) of the main manuscript, whose node attributes already integrate implicit topology structure information.
The View of Information Flow. For training on large-scale graphs to obtain offline parameter trajectories, we solve the node classification task on T = (X, A, Y) with certain GNN model as
07 arg min Cets [GNNo (X,No(X,AA)) A), Y],
0
where * denotes the optimal training parameters that build the training trajectory distribution pey- The whole graph information, i.e., node attributes X and topology structures A are both embedded in the latent space of GNN network parameters. Hence, the large-scale graph information flows to GNN parameters as (X, A) Pey. In this way, by meta-sampling the trajectory distribution, Eq. (4) and Eq. (5) in the main manuscript explicitly transfer learning behaviors of the large-scale graph to the parameter space Os of GNNs as Pe, = 0s.. As a result, the informative knowledge of the large-scale graphs, i.e., node attributes and topology structure information (X, A), would be comprehensively transferred as (X, A) + Pe, = Os. In this way, we could identify the critical goal of graph condensation is to further transfer the knowledge in Os to the output condensed graph data as:
X, A) + Per + Us
+ T' A'), GC.
(10)
A) + Per Os + S = (X), SFGC.
where GC and SFGC are corresponding to the existing graph condensation and the proposed structure- free graph condensation, respectively.
Hence, from the view of information flow, we could observe that condensing structures would not inherit more information from the large-scale graph. Compared with GC which formulates the condensed graph into nodes and structures, the proposed SFGC directly distills all the large-scale graph knowledge into the small-scale graph node set without structures. Consequently, the proposed SFGC conducts more compact condensation to derive the small-scale graph- data, which implicitly encodes the topology structure information into the discriminative node attributes.
18

---

Table A3: Running time comparison (seconds) of the proposed SFGC and GCOND 27 for 50 epochs with single GeForce RTX 3080 GPU.
Ogbn-arxiv
00.05%
r=0.25%
r=0.5%
GCOND(27 SFCC (ours)
296.34
442.58 183.54
885.58
150.35
Dynamic Tenser Used Compartson
Deker exkrept
1n mutter Beer
ABrr OUAT
Figure A1: Comparison of the dynamic tensor used memory cost between online short-range gradient matching method GCOND [27 and our proposed SFGC.
E
More Experimental Settings and Results
E.1
Time Complexity Analysis & Dynamic Memory Cost Comparison
We first analyze the time complexity of the proposed method and compare the running time between our proposed SFGC and GCOND (27].
Let the number of GCN layers be L, the large-scale graph node number be N, the small-scale condensed graph node number be N', the the feature dimension be d, the time complexity of calculating training trajectory meta- veeaa-mtchhing objective function is about TK OLL' LN'd), for each process of the forward, backward, and training trajectory meta matching loss calculation, where T denotes the number of iterations and K denotes the meta-matching steps. Note that the offline expert training stage costs an extra (KO + LNd?) on the large-scale graph, where the number of edges.
In contrast, for GCOND, has at least TKO LN') + TKO(N22 d2), and also additional TKO(LEd+ LNd") on the large-scale graph, where K denotes the number of different initialization here. can be observed that our proposed SFGC has smaller time complexity compared to GCOND, which can be mainly attributed to our structure-free paradigm when the adjacency matrix related calculation in d can be avoided. The corresponding comparison running time in the graph condensation process can be found in Table A3 As can be observed, both results on time complexity and running time could verify the superionity of the proposed SFGC.
Moreover, we present the comparison result of the dynamic tensor used memory cost between the online short-range gradient matching method GCOND 27 and our offline long-range methhnn SFGC. As shown in Fig. A we consider three stages of optimizing the objective function, i.e., before outer optimization, the outer and inner optimization, and after outer optimization. can be observed that the proposed SFGC could significantly alleviate heavy online memory and computation costs. This can be attributed to its offline parameter matching schema.
E.2 Effectiveness of Graph Neural Feature Score in SFGC
To verify the effectiveness of graph neural feature score "gnnf in the proposed SFGC, consider the following two aspects in dynamic evaluation: (1) node classification performance at different meta-matching steps in Table A4 (2) learning time comparison between iterative GNN training and our closed-form gat in Fig.
As shown in Table A4 we select certain meta- metaa-mathhing step intervals, i.e., 1000, 2000, and 3000, for resting their condensed data's performance, which is commonly-used evaluation strategy for existing methods. Here, we set long-enough meta-matchie mattamnttiingggg steps empirically to ensure sufficient learning to expert training trajectory-built parameter distribution. And we compare these interval-step results with the performance of our condensed graph-free data, which is selected at certain steps of
19

---

Table A4: Performance of the condensed graph-free data between different meta meta-natching steps and 7gnl dynamic evaluation selected steps in the proposed SFGC.
Datasets (Ratio)
Meta- matching Steps
Taet
1000
2000
3000
ACC
Selected Steps
Citeseer
(r 1.8%)
61.813.1
64.2+5.2
72.410.4
46
Cora (r 2.6%)
81.2+0.5
81.8=0.7
81.7+0.5
929
Ogbn-arxiv
64.5
6..
66.140.4
90
(r 0.25%
Flickr
46.3+0.2
44.7=0.3
47.0+0.1
200
0.5%)
Reddit
86.9+0.5
8..
89.9=0.5
90.0+0.3
2299
0.1%)
Learning Time Comparison: GCN vs. GNTK in Ygnt
Redlt
1235
(rd [0%)
1.114
Flickr (--8119)
0.345
0:85
4.244
Ogte-ande
Come
60077
Gieeser (m-809%)
6.066
Figure A2: Learning time comparison (seconds) in dynamic evaluation between GNN iterative training and closed-form GNTK in "/gat of the proposed SFGC.
the meta-matching process according to the metric Ygat- Overall, Yggut could select optimal condensed graph-free data with superior effectiveness at best meta-matching steps.
For the learning time comparison between GNN iterative training vs. --NTKd closed-form solutions of 7gn Fig. A2 we consider the time of GNN iterative training that covers all training epochs under the best test performance for fair comparisons. This is due to the fact that the iterative training evaluation strategy mandates the complete training of a GNN model from scratch at each meta-matching step. For instance, in Flickr dataset (r 0.1%), calculate 200 epochs rumning time, i.e., 0.845s, which is the optimal parameter setting for training GNN under 0.1% condensation ratio. As can be generally observed, for all datasets, the proposed GNTK-based closed- solutions of %gal significantly save the learning time for evaluating the condensed graph-free data in meta-natching, illustrating SFGC's high dynamic evaluation efficiency.
E.3 Analysis of Different Meta-matching Ranges
To explore the effects of different ranges of long-term meta-na, we present the different step combinations of steps (student) in GNN and p steps (expert) of GNNT in Eq. (5) of the main manuscript Ogbn-arxiv dataset under 0.05%. The results are shown in Fig. A3 As can be observed, there exists the optimal step combination of g student steps (600) and expert p steps (1800). Under such setting, the condensed small-scale graph-free data has the best node classification performance. Moreover, the quality and expressiveness of the condensed graph-free data moderately vary with different step combinations. but the variance is not too drastic.
More detailed settings of hyper-parameters of y steps (student) in GNNs and p steps (expert) of GNN, in the long-term meta-matching. as well as the meta-matching learning rate (LR) in the outer-level optimization and GNN, learning rate (step size) Ç (Algorithm of the main manuscript) in the inner-level optimization, are listed in Table A5
20

---

Figure A3: Performance with different step combinations of student steps and expert p steps on Ogbn-arxiv (r 0.05%).
Table A5: rate (LR) in the outer-level optimization and GNNs s learning rate (step size) Ç in the inner-level optimization.
of expert steps and g student steps with meta-matching learning
Datasets
Ratios (r)
p steps (expert)
g steps (student)
Meta-matching
Ç for GNNs
0.9%
500
200
0.0005
1.0
Citescer
1.8%
500
3.6%
400
300
0.001
1.0
1.3%
1500
400
0.0001
0.5
Cora
2.6%
1200
500
0.0001
0.5
5.2%
2000
500
0.0001
0.5
0.05%
1800
Ogba-arxiv
0.25%
1900
1200
0.1
0.1
0.5%
1900
1000
0.1
0.1
0.1%
700
600
0.1
0.3
Flickr
0.5%
1%
900
900
0.02
0.2
0.05%
900
900
0.02
0.5
Reddit
0.1%
900
900
0.05
0.5
0.2%
900
900
E.4
Performance on Graph Node Clustering Task
Taking graph node clustering the downstream task, verified that, condensed graph-free data, synthesized based on the node classification task, can be effectively utilized for other graph machine learning tasks, demonstrating the applicability of our condensed data. The experimental results shown in Table A6 and Table Table beloow..
Concretely, we use our condensed graph-free freh data, which is generated using GNN classification experts, to train GCN model. Then, the trained GCN model conducts clustering on the original large-scale graph. The clustering results in percentage on Cora and Citeseer datasets are shown by four commonly-used metries, including clustering accuracy (C-ACC), Normalized Mutual Information (NMI), Fl-score (F1), and Adjusted Rand Index (ARI).
Table A6: Performance comparison on Cora terms graph node clustering, Best results are in bold and the second best with underlines.
Clusterings on Cora
C-ACC
NMI
F1
ARI
K-means
50.0
31.7
37.6
23.9
VGAE
29
59.2
40.8
45.6
34.7
ARGA 42
64.0
44.9
61.9
35.2
MGAE 58
68.1
48.9
53.1
56.5
AGC 75
68.9
53.7
65.6
44.8
DAEGC 57
52.8
68.2
49.6
SUBLIME
54.2
63.5
50.3
SFGC (ours) (r = 1.3%)
70.5
51.9
71.0
43.7
SFGC (ours) (r 2.6%)
69.4
51.3
70.1
42.2
SFGC (ours) 5.2%)
71.8
53.0
73.1
43.8
21

---

Table A7: Performance comparison on Citeseer in terms of graph node clustering. Best results are in bold and the second best are with underlines.
Clusterings Citeseer
C-ACC
NMI
F1
ARI
K K-means
31.2
41.3
VGAF 29
39.2
16.3
27.8
10.1
ARGA 42
57.3
35.0
54.6
34.1
MGAE 58
66.9
41.6
52.6
42.5
AGC 75
67.0
41.1
62.5
41.5
DAEGC [57
67.2
39.7
63.6
41.0
SUBLIME 35
68,5
44.1
63.2
43,9
SFGC (ours) 0.9%)
64.9
38.1
63.6
37.3
SFCC (ours) 1.8%)
66.5
39.4
64,9
39.7
SFGC (ours) 3.6%)
65.3
37.6
63.4
38.0
Cona (1-5 20%)
Gleseer (w43.9%)
Ogbe (--0.5))
nltkr (mm11))
Readit (20021)
Figure A4: Visualization of t-SNE condensed graph-free data by SFGC.
As can be observed, our condensed graph enables the GNN model to achieve comparable results with many graph node clustering bascline methods, even though we do not customize the optimization objective targeting node clustering task the condensation process. These results could justify that: (1) the condensed graph-free data that is synthesized based GNN classification experts, could also work well other tasks, even without task-specific customization in the condensation process; (2) the condensed graph-free data contains adequate information about the original large-scale graph, which can be taken as the representative and informative substitution of the original large-scale graph, reflecting the good performance of our proposed method in graph condensation.
E.5 Visualization of Our Condensed Graph-free Data
we present I-SNE [5 plots of condensed graph-free data our proposed SFGC under the minimum condensation ratios over all datasets in Fig. A4 The condensed graph-free data shows a well-clustered pattern over Cora and Citeseer. In contrast, on larger-scale datasets with larger condensation ratios, results show that the small-scale graph-free data synthesized by our method has discriminative and representative node attributes that capture comprehensive information from large-scale graphs.
also observe some implicit clusters within the same class. These
22


Reviews:
[{"review_id": "wGrDqrmGkG", "reviewer": "Reviewer_U4b1", "summary": "This paper proposes a graph dataset condensing algorithm with a main idea of creating a new format of graph representation that does not explicitly include edge information. The authors suggest a new graph kernel and training algorithm with trajectory for online gradient to achieve graph condensation. Experiments demonstrate that the suggested algorithm (named SFGC) outperforms other baselines that condense the graph with explicit edge information in terms of node classification. The authors also showcase the performance of SFGC in terms of generalization ability and empirical learning time efficiency.\n", "questions": "- Can SFGC be used for edge classification tasks, such as edge prediction?\n- I am curious why using SFGC is better than using the whole dataset in Cora data (Table 1). In lines 303 to 304, the authors mentioned this phenomenon, but it would be beneficial to see the reason backed with examples.\n", "limitations": "It is challenging to find the limitation section. Could you please indicate the part where the limitations of the proposed method are discussed?", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "One of the main strengths of this paper is introducing an interesting method for compressing graph datasets. The idea of removing edge information explicitly seems strong, but it appears plausible and well-founded, akin to non-negative matrix factorization with constraints of non-negativity. The simplicity of the idea allows other researchers to easily adapt it to their own graph-related research. Furthermore, the authors present numerous experimental results demonstrating that the suggested framework outperforms the baseline models.\n", "weaknesses": "I have some questions, so I hope to listen to the answers from the authors.\n\nIt is hard to see Figure 3.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Response to Reviewer U4b1**\n\nWe sincerely appreciate the time and effort the reviewer dedicated to reviewing our work, and we are pleased to learn that our proposed SFGC is interesting and well-founded to the reviewer. The following are our detailed responses to the reviewer’s thoughtful comments and suggestions. And we will refine our manuscript to make Fig.3 more clear.\n\n**Q1: Can SFGC be used for edge classification tasks, such as edge prediction?**:\nYes, our SFGC can be also used for edge classification tasks, e.g.,  edge prediction, by using edge prediction loss (BCE loss) as the optimization objection. More specifically, according to the definition of graph condensation mentioned in Lines 45-52 of our main submission, the proposed SFGC method condenses large-scale graph data into small-scale condensed graph-free data, so that the small-scale condensed data could achieve comparable ‘test performance’ as the large-scale graph when training the same GNN model. Thus, the proposed method will remain effective for different tasks regarding the ‘test performance’.\n\n**Q2: More analysis of Cora dataset results**:\nThe reason SFGC condensed graph-free data has a performance that even exceeds the whole large-scale graph dataset on Cora and Citeseer is mainly attributed to the following aspects:\n\nSFGC is a data-centric method in a generative way. The parameterized node features are continuously updated and optimized in the whole condensation progress of imitating GNN’s learning behavior, which means we have very extensive space to seek optimal condensed graph-free data, resulting in models outperforming the one trained from the original graph. Besides, the long-term training trajectory meta-matching technique allows us to receive comprehensive knowledge as informative supervision from extensive GNN expert training processes by learning their parameter distribution, which further contributes the superior performance of our condensed graph from the original graph. Thanks for your suggestion and we will add such discussions in the final version.\n\n**Discussed Limitation and potential future direction**: We mentioned the limitation at the end of our main submission (ref. Lines 358-360),  that is our proposed SFGC mainly works on node-level condensation by reducing the number of nodes in a single graph, which has limited ability on graph-level tasks that require multiple graphs to supervise GNN training. In light of this, for potential future direction, we would like to further explore more on the graph-level condensation problem, which should simultaneously reduce “the number of nodes“ and “the number of graphs“ in the large-scale graph collection. \n"}, {"review_id": "exkHHeHx3h", "reviewer": "Reviewer_8VHW", "summary": "This paper introduces a structure-free graph condensation method designed to distill large-scale graphs into small-scale graph-free data while preserving comparable expressiveness. The proposed method, named SFGC, achieves this by condensing the graph topology into an identity matrix, effectively embedding the structure information into the node attributes. To effectively imitate the GNN training process, SFGC employs a training trajectory meta-matching scheme. Additionally, a graph neural feature scoring technique is used, which dynamically evaluates the quality and relevance of the synthetic graph-free data.", "questions": "- Could you provide more details on how the three condensation ratios for each dataset used in the experiments were determined? \n- I am curious why the performances of the five variants of SFGC in Figure 3 (Citeseer), used for synthesizing graph structures, drop significantly at a condensation ratio (r) of 3.6%, which is even much worse than the case of smaller condensation ratios. \n- I would like to know if the number of expert trajectories affects the performance and how the number of expert trajectories were set.\n- Claiming that the long-term parameter distribution matching method is superior because the SFGC method outperforms GCOND and GCOND-X in Table 1 might be somewhat hasty. While the superior performance could be due to the consideration of long-range, it seems that finding the optimal condensed graph-free data, as seen in Table A4, also plays a significant role. \n\n", "limitations": "The authors do not include a discussion on the potential limitations of this study or offer insights into possible future research directions.\n\n- An important consideration is that if SFGC necessitates the pre-training of a GNN on a large-scale graph to obtain a pre-trained training trajectory, it implies that real-world large-scale data must be initially trained. While this process is distinct from the graph condensation pipeline, it nonetheless introduces challenges associated with intensive computational demands. Addressing and suggesting solutions for this could provide valuable directions for future studies.\n\n- I find the potential of employing different GNN models as the condensation network intriguing. As the method of incorporating graph structural information into node features heavily relies on the characteristics of the condensation model, using a different GNN model could potentially alter the properties of the condensed graph and impact the final performance. Therefore, additional experiments with various condensation networks and test networks would offer valuable insights.\n\n", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Graph condensation is a crucial research area with many real-world applications. The authors propose a new “structure-free” graph condensation method. \n- They provide convincing experimental results and comprehensive discussions overall.\n- The idea of using GNTK-based graph neural feature score metric is interesting and effective. \n- The paper is clearly written and easy to follow. Supplementary materials also offer valuable additional information regarding the model and its performance behaviors. \n", "weaknesses": "- The authors claim that this is the first work that distills large-scale graphs to small-scale synthetic graph-free data, but the previous work GCOND-X also appears to perform a similar task of distilling large graphs to small-scale graph-free data. Further clarification on this would be needed. \n- It appears that the experiments do not precisely determine the extent to which different aspects of the model contribute to performance improvement. \n- The effectiveness of the “structure-free paradigm” in SFCG should also be convincingly demonstrated. In Section 3.2, a graph structure is generated from condensed node features and compared with SFCG. However, since the graph structure is already included in the node features, inputting the graph structure and condensed node features into the GNN model again could cause over-smoothing. Therefore, it is unclear whether the performance improvement over existing models is due to the structure-free paradigm or appears to be due to over-smoothing.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Response to Reviewer 8VHW**\n\nWe are glad that you recognize the significance of graph condensation. We have carefully considered your thoughtful comments and suggestions, and the following are our detailed responses. \n\n**W1: Clarification on GCOND’s graphless variant GCOND-X**:\nOur SFGC has different motivations and technical implementations with GCOND-X [14]. GCOND aims to simultaneously learn node attributes and graph structure, 'graphless' variant GCOND-X is not their main goal, but a by-product for ablation study. In contrast, our SFGC directly encodes structure information into more compact condensed node attributes, with comprehensive theoretical analysis and thorough empirical studies in Appendix Sec. D and Sec.3. Besides, our SFGC conducts offline long-term training trajectory meta-matching schema for condensation, whereas GCOND-X conducts online gradient matching schema. We will add these discussions in the final version.\n\n**W2: To what extent each aspect of the model contribute to performance improvement**:\nWe have three core components in our framework: (C1) training trajectory meta-matching scheme, (C2) graph neural feature score metric, (C3) structure-free paradigm.We have individually analyzed the effectiveness of each one, i.e., Lines 327-336 (C1), Table A4 (C2), and Fig. 3  (C3) in the submission. To summarize the component contributions, we showed **Table.Re 1 in the response PDF file**  for the ablation study in Cora dataset with 2.6% condensation rate.\nAs observed,  IDX-1 vs. IDX-3, IDX-3 vs. IDX-4, and IDX-2 vs. IDX-3, verify the effectiveness of C1, C2, and C3, with 5.5%, 0.5, 7.3% improvement, respectively, illustrating the effectiveness of each aspect of our proposed SFGC.\n\n**W3: Whether the effectiveness of SFGC due to the structure-free paradigm or oversmoothing.**\nWe have compared our “structure-free paradigm” (w/o structure) vs. other 5 variants (w/ structure) in Sec.3.2 to verify its effectiveness, where the 5 w/ structure variants follow existing graph structure learning methods, i.e., GCOND[14], to synthesize graph structures from condensed node features. Such graph structure learning strategy might have potential over-smoothing when “graph structure is already included in the node features”.  Importantly, this is the main drawback of existing methods and motivates us to propose “structure-free condensation paradigm”, and performance improvement in Fig.3 over other variants (w/ structure) could illustrate the effectiveness of “structure-free paradigm” in SFGC.\n\n**Q1: Details of condensation ratio**: Due to response word limitations, please refer to our response to Reviewer-4KcB, W1 for more details. \n\n**Q2:Synthesizing graph structures drop at a large condensation rate**:\nThis observation accurately reflects the limitation of existing graph structure learning based condensation methods, which require optimizing a triple-level condensation objective. In fact, when condensation rate is relatively large 3.6% in Citeseer,  the number of nodes is larger, and the graph structure learning space increases exponentially, making the problem harder to be optimized. Hence, it is intuitive that synthesizing graph structures would drop significantly at a large condensation rate with more nodes. And this also motivates us to propose the “structure-free paradigm’’. \n\n**Q3:The number of expert trajectories $K$**:\nIn our submission, $K$ is empirically set as 200. Here, we also conduct a hyperparameter analysis on $K$ in **Table.Re 2 of the response PDF file**. Intuitively, more experts might lead to more guidance on condensation, and fewer experts might limit the model behavior imitations. However, when the number of experts keeps raising from 200 to 300, the performance drops moderately. One potential reason is: the distribution of more expert GNN parameters would be more complex, and accurately computing their expectation to guide condensation would be more difficult. We will add these discussions in the final version.\n\n**Q4: Superiority of long-term parameter distribution matching**\nFirst, compared to “online short-range gradient matching” in GCOND and GCOND-X, the superiority of our “offline long-term parameter distribution matching” is (1) good condensation performance and (2) saved memory usage (SFGC: 118.116 vs. GCOND [14] 910.4)*100Mb (ref. Figure A1 in the appendix).\nWe list the comparison results w/ and w/o the GNTK-based dynamic evaluation strategy in **Table.Re 3 of the response PDF file**. It shows, our SFGC (w/o dynamic evaluation) achieves better performance than GCOND-X and GCOND, verifying the effectiveness of the proposed “offline long-term parameter distribution matching”.\n\n**Discussed Limitation and potential future direction**: We mentioned the limitation at the end of our main submission (ref. Lines 358-360), that is our SFGC has limited ability on graph-level tasks which build on multiple graphs. And we would like to further explore more on the graph-level condensation problem, which should simultaneously reduce the number of nodes and the number of graphs in the large-scale graph collection. \n\n**L1. Suggestion for intensive computation on training real-world large-scale graph data**: We would suggest employing GraphSage [10], GraphSAINT [35], or  ClusterGCN [KDD-19-Cluster-GCN] as the backbone to train super-large graphs for alleviating for intensive computation. \n\n**L2. Employing different GNN condensation networks**: Our work can be straightforwardly extended to employ different GNN models as condensation networks by imitating their training behaviors. Thanks for sharing the thoughtful suggestion, and we will add these limitation discussions to the final version.\n\n"}, {"review_id": "KcJYmojrC8", "reviewer": "Reviewer_KcU6", "summary": "This paper studies the problem of reducing the size of a large graph dataset while preserving task-relevant information. \nIt introduces a new methodology to distill large-scale real-world graphs into smaller synthetic graph node sets by disregarding graph structures to create condensed graph-free data. The approach involves two key components: a training trajectory meta-matching scheme for effectively synthesizing small-scale graph-free data, and a graph neural feature score metric for evaluating the quality of condensed graph-free data dynamically. Extensive experiments have demonstrated the efficiency and effectiveness of the proposed method.\n\n", "questions": "1. Complexity comparison of GCN and GNTK \n2. What is the exact formulation for $\\mathcal{K}$ in Eq. 7? Specifically, what are the values for $\\beta$ and $K$.", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The paper addresses an interesting problem in the field of graph condensation, which has significant practical implications.\n2. The proposed SFGC methodology exhibits commendable performance and generalization across various graph neural network (GNN) architectures.\n3. The utilization of the Graph Neural Tangent Kernel (GNTK) to avoid iterative training of GNNs adds an interesting aspect to the paper.\n\n", "weaknesses": "\nSuggestions for Improvement:\n1. To further strengthen the paper, it is recommended to demonstrate the benefits of SFGC in practical applications such as neural architecture search, privacy protection, adversarial robustness, or continual learning. Including at least one of these applications would greatly enhance the paper's significance.\n2. It would be of interest to clarify how SFGC can benefit neural architecture search for GNNs since it does not generate graph structures, which are essential for GNNs, and different GNNs may require distinct operations over the graph structure.\n3. While Figure A2 provides a comparison of the running time between GCN and GNTK, it would be valuable to include a detailed complexity analysis of both methods concerning the number of nodes. \n * Specifically, elaborate on the quadratic complexity of GNTK due to the pairwise kernel matrix calculations and the matrix inversion operation. \n  * I guess that is also why on Reddit (r=0.05%) GCN and GNTK exhibit similar running times. What if we further increase r to 0.1%?  \n4. It would be beneficial to include an empirical comparison with DosCond, as it also aims to accelerate the graph condensation process, to provide a comprehensive evaluation of SFGC.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Response to Reviewer KcU6**\n\nThanks for sharing your thoughts and questions with us. We greatly appreciate your valuable suggestions on discussing more on the practical application and complexity of our proposed SFGC method. We have taken your suggestions into careful consideration and we have provided detailed responses to your questions below. We hope that these answers will help to address your concerns clearly.\n\n**W1: Demonstrate the benefits of SFGC in practical applications**:\nThanks for your suggestion. We have given some detailed illustrations about how the benefits of SFGC in Appendix Sec.B Potential Application Scenarios. \nFor instance, for graph neural architecture search (GraphNAS), which needs to repeatedly train different potential GNN architectures, our SFGC generated small-scale condensed graph-free data can be taken as a representative substitution of the large-scale graph, significantly benefiting for saving many computation costs and accelerating new GNN development. A more detailed explanation can be seen in responses to W2.\n\n**W2: How SFGC can benefit GNNs neural architecture search**:\nAccording to the below survey work *[IJCAI-Survey-2021]*, the design of GraphNAS search space can extensively involve: (a) Micro search space with “aggregation functions”, “aggregation weights”, number of attention heads, combining functions, feature dimensionality, Non-linear activation function; (b) Macro search space with layer-wise combination function; (c) the Pooling function and (d) Hyper-parameters. \nHence, for fine-grained search space, our proposed structure-free can only slightly affect the design of “aggregation functions and weights” in the (a) Micro search space. Considering all different types of aggregation weights in different GNNs are calculated based on the node features, SFGC condensed graph-free data has implicitly encoded topology structure information into the node features. Hence, SFGC could still benefit GraphNAS by designing node-attribute weighted aggregation functions in the search space, as well as all other aspects in (b)-(d) to design new GNN models driven by specific tasks. Thanks for your valuable suggestions and we will add these discussions into the final version.\n\n*[IJCAI-Survey-2021] Ziwei Zhang, Xin Wang, Wenwu Zhu Automated Machine Learning on Graphs: A Survey.*\n\n**W3-Detailed complexity analysis of GCN and GNTK**:\nGiven $T$ is the number of GCN training iterations, $N$ and $N^{'}$ are the number of large-scale graph nodes and condensed graph nodes, respectively, $L$ denotes the number of layers, and $F$ denotes feature dimension. \nIn our SFGC, we use $L=2$, hence for GCN, we have its complexity dominated by $\\mathcal{O}(4TN^{'}F^{2})$. For node-level GNTK calculation, its complexity can be dominated by $\\mathcal{O}(4N^{2}N^{'2})$.\nHence, under certain iterative times $T$ setting, the GCN’s and GNTK’s might have comparable complexity ($TF^{2}$ vs. $N^{'}N^{2}$), which might be a reason for Reddit (r=0.05%) GCN and GNTK have similar running times (GNTK still better).\nWhen the condensed graph has more nodes, for instance, Reddit further increases r to 0.1%, GCN needs to involve more iterative times $T$, and GNTK also needs to calculate a bigger Kronecker product matrix. It might be hard to make a straightforward comparison, since it is hard to make sure how to set hyperparameters (for instance, $T$, learning rate) to iteratively train GCN on the mid-product condensed graph in the optimization process. And this challenge is our main motivation to leverage close-form GNTK in dynamic evaluation, avoiding iterative GCN training tied to hyperparameter settings. We sincerely thank you for your suggestion, and we will add these discussions in the final version.\n\n**W4-Empirical comparison with DosCond**:\nThe node classification performance comparison between our proposed SFGC and DosCond can be seen in Table.Re-KcU6-1, where the DosCond results are from its work. As can be observed, our proposed method still outperforms DosCond. \nDosCond improves the graph condensation process by simplifying short-range gradient matching to the one-step pattern to accelerate condensation, in contrast, our proposed SFGC improves the graph condensation process by simplifying the optimization objective with a structure-free paradigm to obtain high-quality condensed graph-free data. DosCond and our proposed SFGC do have different targets. Thanks for your valuable suggestion, we will add this discussion to our final version.\n\n**Table.Re-KcU6-1. Performance comparison between DosCond and our proposed SFGC.**\n\n| Methods | Cora (r=2.6%) | Citeseer (r=1.8%) | Flickr (r=0.1%) |\n| :--- | :---: | :---: | :---: |\n| DosCond | 80.0 | 71.0 | 46.1 |\n| SFGC (**Ours**) |**81.7** | **72.4** | **46.6** |\n\n**Q2-Formulation of Eq.(7)**: The K in Eq.(7) is the GNTK kernel and its detailed calculation has been illustrated in Eq.(2) of our main submission. The $\\beta$ denotes the number of fully-connected layers in calculating GNTK in Eq.(2) and we set it to 2 in our work.\n"}, {"review_id": "PZ4lJOhiSs", "reviewer": "Reviewer_yKD6", "summary": "This paper presents a new method to condense a training graph into a smaller number of disconnected nodes, such that a GNN trained on these nodes performs similar to one trained on the original graph at test time.", "questions": "What does the condensed structure-free data look like in relation to the original training data? Some intuitive visualization would be nice to have.\n\nWhat are the GNN depths used? It seems that the fidelity of structure-free condensation should go down as more neighbor aggregation steps are involved at test time, as they were not encountered when training on the condensed data.", "limitations": "A discussion of limitations is missing. An obvious limitation is that structure-free condensation won't work under ego- and neighbor-embedding separation [1] which is an effective recommendation for heterophilic datasets.\n\n[1] Zhu et. al. \"Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs.\" NeurIPS 2020", "rating": 6, "confidence": 1, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "**Originality.** Structure-free condensation has been reported before (GCOND-X), but the proposed method to do so is novel.\n\n**Quality.** The overall quality of the work is good, including the presented techniques, results, tables and plots.\n\n**Clarity.** The paper is mostly clear.\n\n**Significance.** Graph condensation can be very useful under the right application scenarios. I don't see any special significance of aiming for structure-free condensation, except that the method ends up giving better results (e.g. due to easier optimization, as discussed in the paper).", "weaknesses": "The paper is not particularly easy to follow.\n\nGCOND-X is not discussed explicitly in the related works, even though it is a structure-free graph condensation method.\n\nHyper-parameter details have not been provided.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Response to Reviewer yKD6**\n\nWe sincerely appreciate your thoughtful review of our paper. We are glad to hear that you recognize the significance of graph condensation research, as well as encouraging comments for our work. We have carefully considered your comments and suggestions, and the following are our detailed responses. We are expecting these could be helpful in answering your questions.\n\n**W1: Discussion of GCOND’s graphless variant GCOND-X**:\nOur SFGC has different motivations and technical implementations with GCOND-X [14]. GCOND aims to simultaneously learn node attributes and graph structure, 'graphless' variant GCOND-X is not their main goal, but a by-product for ablation study. In contrast, our SFGC directly encodes structure information into more compact condensed node attributes, with comprehensive theoretical analysis and thorough empirical studies in Appendix Sec. D and Sec.3. Besides, our SFGC conducts offline long-term training trajectory meta-matching schema for condensation, where GCOND-X conducts online gradient matching schema. Thanks for your suggestion and we will add these discussions in the final version.\n\n**W2: Hyper-parameter details**: We have provided detailed hyper-parameter settings in Table A5 containing student and teacher steps, meta-matching learning rate, GNN training step size for all 5 datasets with 15 condensation cases.\n\n**Q1: Visualization of the condensed structure-free data in relation to the original training data**:\nThanks for your suggestion, and the visualization of (a) original Cora dataset and (b) the condensed Cora dataset (r=5.2%) by our proposed SFGC in **Fig. Re1 of the response PDF file** for illustrating their relationship, and we will add this to the final version.\nIt can be observed that our proposed method significantly distills the original graph with complex structures (black dense edges ) to reduced small-scale node set without explicit graph structures. Importantly, they share the same class-label space and similar test performance, as illustrated by the experimental results in Table 1 of our main submission.\n\n\n**Q2: What are the GNN depths used? As neighbors (structures) were not encountered when training on the condensed data, whether performance of structure-free condensation would drop at the test time**:\nWe use two-layer GCN for condensation progress.\nEven the topology neighbors “were not encountered when training on the condensed data” explicitly, the performance of our proposed SFGC on the test set of large-scale graph would not drop at the test time (as illustrated by the results in Table 1 of our main submission). That is because, our proposed structure-free condensation could enforce the condensed node features to encode topology structure information of the original large-scale graph, and its GNN learning behavior imitation strategy could comprehensively distill the large-scale graph information (both nodes and structures) into small-scale condensed node set.\n\n**Discussed Limitation and potential future direction**: We mentioned the limitation at the end of our main submission (ref. Lines 358-360),  that is our proposed SFGC mainly works on node-level condensation by reducing the number of nodes in a single graph, which has limited ability on graph-level tasks that require multiple graphs to supervise GNN training. In light of this, for potential future direction, we would like to further explore more on the graph-level condensation problem, which should simultaneously reduce “the number of nodes“ and “the number of graphs“ in the large-scale graph collection. \n\n**L1: Heterophilic datasets**: Thank you for suggesting the interesting heterophily graph type. On the heterophilic graph dataset, a possible and straightforward solution under our proposed SFGC can be: we use the heterophilic-GNN, e.g, H2GNN mentioned in [1], as the condensation model (rather than vanilla GCN in our submission) to distill the information of the original heterophilic graph to the condensed graph-free data.  Once the heterophily characteristic of the original heterophilic graph is condensed into the synthesized node attributes, we still use the condensed data to train a GNN model and infer on the test set of the heterophilic graph. However, effectively learning the intricate and diverse heterophily characteristics presents a severe challenge that deserves more future exploration. We deeply value your perceptive insights and we will add the discussion of this interesting research question to the final version.\n\n"}, {"review_id": "7xUSDFQRsE", "reviewer": "Reviewer_PLzT", "summary": "This paper studies an interesting problem. The authors proposes a new paradigm for reducing the size of large-scale graphs without explicit graph structures. The proposed SFGC, encodes topology structure information into node attributes in synthesized graph-free data. Extensive experiments demonstrate the effectiveness of the proposed method compred with existing graph condensation methods.", "questions": "- How computationally efficient is the SFGC strategy compared to the current graph condensation techniques?\n- How effective and robust is the SFGC method on real-world graphs with noisy or insufficient data?", "limitations": "The authors could benefit from a more thorough discussion of the limitations and potential negative societal impacts of their work, as well as potential ways to mitigate these issues. ", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The paper proposes a novel SFGC approach.\n- This paper studies the effectiveness and generalization ability issues in graph condensation.\n- This paper provides theoretical illustrations of the proposed structure-free graph condensation paradigm from the views of statistical learning and information flow, respectively.", "weaknesses": "- The work fails to provide a clear motivation for why it is important or required to reduce the size of big graphs lacking explicit graph structures. \n- The paper could benefit from a more thorough discussion of the limitations and potential future directions of the proposed approach.\n- Without having access to the source code, it is challenging to reproduce the results. The experimental setting is described, however it would be beneficial to have access to the source code to guarantee that the findings can be reproducible.\n\nIf the main concern about the reproducibility is solved, I am willing to increase the score.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Response to Reviewer PLzT**\n\nWe sincerely appreciate the time and effort you dedicated to reviewing our work. We have carefully considered your comments and suggestions. Following the instructions for the rebuttal, we have sent the source code via an anonymous link to the AC. We appreciate it if you obtain the link from AC. The source code will be made public upon acceptance. The following are our detailed responses. We are expecting these could be helpful in answering your questions.\n\n**W1: Motivation for why it is “important or required” to reduce the size of big graphs lacking explicit graph structures**:\nIn the general context of dataset condensation and graph size reduction, our proposed SFGC shares a similar motivation that reducing the size of big graphs into small counterparts could help in reducing storage costs and accelerating GNN model development progress, as mentioned in Lines 25-30 of the main submission.\nMoreover, the motivations for our proposed ‘Structure-free’ graph condensation pattern (without explicit graph structures) are in the following aspect: (1) simplifying existing complex ‘triple-level’ optimization (‘with structure’) into effective ‘bi-level’ progress (‘structure-free’) to improve graph condensation effectiveness (Ref. Lines 60-66 of the main submission); (2) alleviating the limitation of condensed graph data on certain graph convolution operations that depends on graph structures to improve synthesized graph data generalization ability.(Ref. Lines 67-70 of the main submission).\nHence, even without explicit graph structures, our proposed SFGC encodes topology structure information into the node attributes in the synthesized graph-free data (Ref. Lines 76-78 of the main submission), achieving comparable test performance with the original large-scale graph. \nBesides, the importance and necessity of our proposed structure-free graph condensation can also be reflected in various potential applications in practice (Ref. Section-B of Appendix), covering: graph neural architecture search, privacy protection, adversarial robustness, and continue learning.\n\n**W2: More thorough discussion of the limitations and potential future direction.**\nAs mentioned at the end of our main submission (ref. Lines 358-360),  our proposed SFGC mainly works on node-level condensation by reducing the number of nodes in a single graph, as a result, our condensed graph-free data has limited ability on graph-level tasks, which requires multiple graphs to supervise GNN training.\nIn light of this, for potential future direction, we would like to further explore more on the graph-level condensation problem, which should simultaneously reduce “the number of nodes“ and “the number of graphs“ in the large-scale graph collection. The proposed long-term training trajectory meta-matching scheme would be considered for multiple graph condensation scenarios, and the core challenge would be how to jointly incorporate the node-level and graph-level complexity and diversity into the condensation progress for high-quality condensed data.\nBesides, condensing graph data for various downstream graph learning tasks is another promising research direction, for instance, condensing large-scale graph data to a small-scale counterpart for improving GNN online serving performance.\n\n**Q1: How computationally efficient is the SFGC strategy compared to the current graph condensation techniques?**:\nAs mentioned in our Appendix, in Table A3, Figure A1, and Sec.E.1,  we have provided the (1) Running time comparison, (2) Dynamic tensor used memory cost, and (3) Theoretical Time Complexity Analysis, respectively, to illustrate the computation efficiency of our proposed SFGC and existing graph condensation method GCOND [14].\nIn summary, our proposed method has (1) 5x less running time (SFGC: 150.35s vs. GCOND [14]: 885.58s) on Ogbn-arxiv condensation; (2) significantly low dynamic memory usage (SFGC: 118.116 vs. GCOND [14] 910.4)*100Mb in the overall optimization progress; and (3) at least less O(LN'^2d) time complexity.\nMore detailed results and analysis can be found in our Appendix. These results could reflect the good computational efficiency of our proposed SFGC compared with the current graph condensation method.\n\n**Q2: How effective and robust is the SFGC method on real-world graphs with noisy or insufficient data?**\nFor **noisy data**,  we would like to emphasize that, in the context of graph condensation, our proposed SFGC is a “data-centric” method that synthesizes small-scale graph-free data from the original input graph, with the constraint of ensuring comparable test performance on GNNs.\nHence, if the original graph is noisy and taken as the input for training a certain GCN* model, in the process of graph condensation,  the condensed small-scale graph-free data might learn the distilled comprehensive information (including noisy) from the original graph by imitating the GCN*’s learning behavior. In this case, the noisy information could also be filtered by the graph condensation process.\n\nFor **insufficient data**, as the graph condensation technique, the central focus of our proposed SFGC is to distill large-scale graph data into small-scale synthetic graph-free data as its training substitution. Hence, when given graph data is ‘insufficient’ (not in large-scale quantity), there might be no necessity to further condense it in practical scneario. \n"}, {"review_id": "67s0Lz6Xnn", "reviewer": "Reviewer_4KcB", "summary": "This work proposes a structure-free graph condensation paradigm to distill a large-scale graph into a small-scale graph node set without explicit graph structures. The node attributes of the obtained small-scale condensed graph-free data could encode topology structure information. And the condensed node set could serve as a substitution to replace the large-scale graph for training GNNs and achieves comparable performance on the test set.\nThe method contains two techniques, (1) the parameter matching schema under imitation learning, and (2) a dynamic evaluation schema with a GNTK score. The experimental results could verify its claims and show performance effectiveness.\n", "questions": "\nPlease provide more details corresponding to the weakness.", "limitations": "Yes, the authors have mentioned limitations, no negative social impact.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "S1-[originality]: This work's most remarkable part is its structure-free condensation paradigm, which removes the graph structure by encoding it into node attributes, so that the obtained condensed graph-free data only contains a set of informative nodes. I think this paper would inspire many interesting questions for future researches and topics, when only use a set of nodes to represent the whole large-scale graph for training but obtain comparable test results.\n\nS2-[clarity]: Overall, the question descriptions, contributions, techniques, and experimental results of this paper are described clearly and soundly. \n\nfirst, the concept of structure-free graph condensation and its relevant scenarios have been clearly defined and exemplified.\n\nsecond, the contributions and techniques including the training trajectory matching with online GNN parameters and the GNTK-based dynamic score are clear and sound. \nThis paper could ease three-level optimization to a bi-level optimization without condensed graph structures, which is a novel and interesting structure-free graph condensation pattern. \nThe GNTK-based dynamic evaluation score enables the closed-form solution of GNN evaluation and sounds novel to me.\n\nthird, the experimental results compared with the whole graph dataset training results could support this paper's arguments. An ablation study verifies the effectiveness of the structure-free paradigm. There is another interesting part that the results across different GNN architectures show surprisingly good generalization ability in terms of the condensed node set. This is an inspirable result and deserves future explorations.\n\nS3-[significance]: this work on graph condensation is an interesting problem to reduce the effects brought by large-graph data scale and quantity, and it might be helpful for reducing calculations in real-world applications.\n", "weaknesses": "There are only some technical details that are not well presented here.\n\nW1: how to choose the condensation ratios like Cora with 0.9% and Citeseer with 1.3%? More details and explanations should be involved.\n\nW2: how to deal with the condensed graph labels Y? Is it generated according to the original large-scale graph's classes and each class examples?\n\nW3: are the student steps and teacher steps empirical hyperparameters or learnable parameters that need to be optimized in the condensation process? More details should be given. Besides, this work provides some interesting results, and more discussions of experimental findings should be given, for instance, why the synthesized graph-free data has good generalization ability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Response to Reviewer 4KcB**\n\nThank you for taking the time to review my work and providing your valuable feedback. We are so encouraged by your positive comments on our originality and clear clarity and we appreciate your recognition of our research significance. The following are our detailed responses. We are expecting these could be helpful in answering your questions.\n\n**W1: Details of condensation ratio**:\nThe condensation ratio is chosen based on the labeling rates of the benchmark graph datasets for training, that is the proportion of labeled training nodes in relation to all nodes. For example, in Cora and Citeseer, their training set labeling rates are 5.2% and 3.6% (for 20 labeled samples per class), respectively, and we choose the set according to labeling percentage as {25%, 50%, 100%}, corresponding to {1.3%, 2.6%, 5.2%} for Cora, and {0.9%, 1.8%, 3.6%} for Citeseer. Hence, the 5.2% and 3.6% would be the maximum ratios for Cora and Citeseer, respectively. \n\n**W2: Condensed graph labels Y**:\nAs mentioned in Lines 133-134 of the main submission, for all graph condensation tasks, 'label $Y^{\\prime}$ of the small-scale condensed graph are pre-defined based on the class distribution of the label space $Y$ in the large-scale graph.'\nFor instance, given Flickr dataset, which has $N = 44,625$ nodes from $C=7$ classes (labeled from '0' to '6') in its training graph.\nAmong $N = 44,625$ nodes, we have $N_{C1}=4,321$ nodes labeled '1', $N_{C2}=3,164$ nodes labeled '2', and $N_{C0}+N_{C1}+\\cdots+N_{C6}=N$. In this case, for the $r=0.1$% condensation ratio, the synthesized condensed graph-free data would have $N_{C1}\\times r = 4,321\\times 0.1$% $\\approx 4$ nodes labeled '1' and $N_{C2}\\times r=3,164\\times 0.1$% $\\approx 3$ nodes labeled '2', and so on for the other classes.\n\n**W3: Student/ teacher step setting and experimental finding discussions.**\nStudent steps and teacher steps are empirical hyperparameters with no need to be optimized. We have provided their settings in Table A5 of the Appendix. \nWe appreciate your recognition in terms of the good generalization ability of synthesized graph-free data condensed by our proposed SFGC. One of our contributions is to overcome the poor generalization ability issue in existing graph condensation methods with our proposed structure-free paradigm. The main reason that leads to such good generalization ability can be that different GNN architectures mainly differ in convolution operations along graph structures, our proposed structure-free paradigm would minimize the impact of different convolution operations on graph structures by only learning with a condensed graph node set, leading to consistent and reliable performance across various GNN architectures.  Thanks for your suggestion and we will add more discussions in our revised version.\n"}]

Author rebuttal:
**Common response to all reviewers**: 

We thank all reviewers for their thorough review and valuable suggestions. We are delighted that our contributions have been positively acknowledged, including:

**(1) Novel and interesting problem of structure-free graph condensation paradigm for practical application scenarios (@All Reviewers!)**

**(2) Effective long-term training trajectory meta-matching framework with the bi-level optimization (Reviewer 4KcB,Reviewer yKD6)**

**(3) Interesting and effective GNTK-based evaluation metric with graph neural feature score (Reviewer 8VHW, Reviewer 4KcB, Reviewer KcU6)**

**(4) Numerous and convincing experimental results with superior performance effectiveness. (@All Reviewers!)**

**(5) Good generalization ability of our synthesized graph over cross architectures (Reviewer KcU6, Reviewer PLzT, Reviewer 4KcB)**

We greatly appreciate all the positive comments and valuable suggestions for our work. These comments encourage us to continue our efforts in advancing this new promising graph condensation research area for real-world applications. More detailed responses are as follows. We hope our responses address all weaknesses and questions! Please let us know if there is any concern. We have considered your thoughtful suggestions, and have modified accordingly to improve the manuscript in the final version.


Meta-review: Reviewers unanimously offer affirmative feedback on the manuscript. They concur that the research addresses a novel problem. Both the proposed methodology and the chosen evaluation metrics demonstrate effectiveness, while the experimental results are convincing.
Decision: Accept (spotlight)