Does Graph Distillation See Like Vision Dataset Counterpart?
Authors: Beining Yang
Kai Wang
Qingyun Sun
Cheng Ji
Xingcheng Fu
Hao Tang
Yang You
Jianxin Li
Venue: NeurIPS 2023 poster (2023)
Keywords: data-efficient learning
graph generation
graph neural networks
TL;DR: We broadcast the original graph structure to the process of graph condensation, well-preserve the original graph structure, and greatly improve the performance  in both cross-architecture settings and complex tasks.

Abstract: Training on large-scale graphs has achieved remarkable results in graph representation learning, but its cost and storage have attracted increasing concerns. Existing graph condensation methods primarily focus on optimizing the feature matrices of condensed graphs while overlooking the impact of the structure information from the original graphs. To investigate the impact of the structure information, we conduct analysis from the spectral domain and empirically identify substantial Laplacian Energy Distribution (LED) shifts in previous works. Such shifts lead to poor performance in cross-architecture generalization and specific tasks, including anomaly detection and link prediction. In this paper, we propose a novel Structure-broadcasting Graph Dataset Distillation (\textbf{SGDD}) scheme for broadcasting the original structure information to the generation of the synthetic one, which explicitly prevents overlooking the original structure information. 
Theoretically, the synthetic graphs by SGDD are expected to have smaller LED shifts than previous works, leading to superior performance in both cross-architecture settings and specific tasks.
We validate the proposed SGDD~across 9 datasets and achieve state-of-the-art results on all of them: for example, on YelpChi dataset, our approach maintains 98.6\% test accuracy of training on the original graph dataset with 1,000 times saving on the scale of the graph. Moreover, we empirically evaluate there exist 17.6\% $\sim$ 31.4\% reductions in LED shift crossing 9 datasets. Extensive experiments and analysis verify the effectiveness and necessity of the proposed designs. The code will be made public.

Does Graph Distillation See Like Vision Dataset Counterpart?
Beining Yang Kai Wang"; Qingyun Sun 1:2 Cheng Ji Xingcheng Ful.2,
Hao Tang', Yang You?, Jianxin Li
"School of Computer Science and Engineering, Beihang University
2 "Advanced Innovation Center for Big Data and Brain Computing, Beihang University
National University of Singapore *Carnegie Mellon University
Abstract
Training on large-scale graphs has achieved remarkable results in graph representa- tion learning, but its cost and storage have attracted increasing concerns. Existing graph condensation methods primarily focus optimizing the feature matrices of condensed graphs while overlooking the impact of the structure information from the original graphs. To investigate the impact of the structure information, we conduct analysis from the spectral domain and empirically identify substan- tial Laplacian Energy Distribution (LED) shifts in previous works. Such shifts lead to poor performance in cross-architecture generalization and specific tasks, including anomaly detection and link prediction. In this paper, we propose novel Graph Dataset Distillation (SGDD) scheme for broadcast- ing the original structure information the generation of the synthetic one, which explicitly prevents overlooking the original structure information. Theoretically, the synthetic graphs by SGDD are expected to have smaller LED shifts than pre- vious works, leading to superior performance in both cross-architecture settings and specific tasks. We validate the proposed SGDD across 9 datasets and achieve state-of-the-ee results on all of them: for example, on the YelpChi dataset, our ap- proach maintains 98.69 test accuracy of training on the original graph dataset with 1,000 times saving on the scale of the graph. Moreover, there exist 17.6% 31.4% reductions in LED shift crossing datasets. Extensive experiments and analysis verify the effectiveness and necessity of the proposed designs. The code is available the
empirically evaluate
1 Introduction
Graphs have been applied in many research areas and achieved remarkable results, including social networks [27, 67, 73, 79], physical [16, 3, 57, 10], and chemical interactions [2, 93, 111, 80). Graph neural networks (GNNs), classical and wide-studied graph representation learning method [40, 84, 98, 63], is proposed extract information via modeling the features and structures from the given graph. Nevertheless, the computational and memory costs are extremely heavy when training on large graph [48, 89, 99]. One of the most straightforward ideas is to reduce the redundancy of the large graph. For example, graph sparsification [66, 77] and coarsening [53, 52, 46, 75] are proposed achieve this goal by dropping redundant edges and grouping similar nodes. These methods have shown promising results in reducing the size and complexity of large graphs while preserving their essential properties.
"Equal contribution (yangbeining @ edua.edu.en, kai. wang @ cos...uu...d..sg). I Project lead sunqy @ buaa. edu.aedu..c 'Correspondigg author lijx @ @buaa.edu.cn.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

474
85.3
86.6
06.7
86.2
X
86.0
f(X')
Graclient
X
A'
Matiching
85.8
19.
SC: 0.46
64.2
06.9
09.0
08.0
05.0
3
(a) Condense scheme of GCond
(b) A' of GCond
(c) Cross-arch. Acc. of GCond
87.8
80.6
89
90.7
X
f(Z,X,Y)
Gindient
5077
87.6
Matching
87.6
87
10.0
10.8
00.4
A
Broadcasting
SC : 0.18
68
58.1
21.4
06:9
58.4
5
(d)
Condense scheme of SGDD
(e) A' of SGDD (l) Cross-arch. Acc. of SGDD
Figure (a) and (d) illustrate that the pipelines SGDD and GCond [37]. One can find that SGDD broadcast A from the original graph to the generation of A' while GCond synthesizes A via the operation ʃ(-) (e.g., pair-wise feature similarity [74]) on X'. We also show the condensed graph and its shift coefficient (SC) of GCond and SGDD in (b) and (c), respectively. Note that introduce SC as an approximation of the LED shift. We show the cross- cross-architecture performance of GCond and SGDD in (c) and (f), 1, 2, 3, 4, and denote APPNP [42]. Cheby [13], GCN [41], SAGE [26], and SGC [92], more cross-architecture results can be found in Tab. 2.
However, graph sparsification and coarsening heavily rely on heuristics [5] (e.g. . the largest principle eigenvalues [78], pairwise distances [66, 81), which may lead to poor generalization on various architectures tasks and sub-optimal for the downstream GNNs training [37]. Most recently, as shown in Fig. ((a), GCond [37] follows the vision dataset distillation methods [88, 105, 24, 103] and proposes to condense the original graph by the gradient matching strategy. The feature of the synthetic graph dataset is optimized by minimizing the gradient differences between training on original and synthetic graph datasets. Then, the synthetic feature is fed into the function f(X)) (e.g.. pair-wise feature similarity [74]) to obtain the structure of the graph. The synthetic graph dataset (including feature and structure) expected to preserve the task relevatt information and achieve comparable results as training on the original graph dataset at an extremely small cost.
Although the gradient matching strategy has achieved significant success in graph dataset condensa- tion, most of these works [37, 36, 50, 109] follow the previous vision dataset distillation methods to synthesize the condensed graphs, which results in the following limitations: 1) In Fig. 1(b). we can find that the original graph structure information is not well preserved in the condensed graph. That's s because they build the structure (A') upon the learned feature (X') (Fig. I(a)), which may cause the loss of original structure information. 2) In vision dataset distillation, applying the gradient matching strategy may result an entanglement between the synthetic dataset and the architecture that is used for condensing [106, 104, 39]. This can detrimentally impact their performance, especially when it comes to generalizing to unseen architectures [22]. This issue is compounded when dealing with graph data that comprise both features and structures. As shown in Fig. 1(c) and Tab. 2, GCond [37] explicitly displays inferior performance, demonstrating that generating structure only based on the feature degrades the generalization of the condensed graph.
To investigate the relation between the structure of the condensed graph and the performance of training on it, we follow previous works [82, 1, 13, 78] to analyze it from a spectral view. Specifically, we explore the relationship between the Laplacian Energy Distribution (LED) shift [82, 25, 12] and the generalization performance of the condensed graph. We empirically find positive correlation between LED shift and the performance in cross- arohtterchee settings. To address these issues, we introduce a novel Structure- brotdeebboddasttnggg Graph Dataset Distillation (SGDD) scheme to condense the original graph dataset by broadcasting the original adjacency matrix to the generation of the synthetic one, named SGDD, which explicitly prevents overlooking the original structure information. As shown in Fig. (d)) we propose the graphon approximation to broadcast the original structure as supervision to the generation of condensed graph structure A'. Then, optimize A' by minimizing

---

the optimal transport distance of these two structures. For X', we follow the [37] to synthesize the feature of the condensed graph. The A' and X' are jointly optimized in bi-level loop. Both theoretical analysis (Sec. 3.2) and empirical studies (Fig. ((c) and (()) consistently show that our method reduces the LED shift significantly (0.46 0.18..
We further evaluate the impact of LED shifts and conduct experiments in the cross- coos-architecture setting. Comparing Fig. I(f), I(c), and Tab. 2, the improvement of SGDD is up to 11.3% To evaluate the generalization of our method, we extend SGDD to node classification, anomaly detection, and link prediction tasks. SGDD achieves ttae-off-the-at results on these tasks in most cases. Notably, we obtain new state-of oiie-oofthhe ti--hhe-rtt arr results on YelpChi and Amazon with 9.6% and 7.7% improvements, respectively. Our main contributions can be summarized as follows:
Based on the analysis of the difference between graph and vision dataset distillation, we introduce SGDD, novel framework for graph dataset distillation via broadcasting the original structure information the generation of a condensed graph.
SGDD, the graphon approximation provides novel scheme broadcast the original structure information to condensed graph generation, and the optimal transport is proposed to minimize the LED shifts between original and condensed graph structures.
SGDD effectively reduces the LED shift between the original and the condensed graphs, consistently surpassing the performance of current state-of-the-an methods across a variety of datasets.
2 Related Work
Dataset Distillation & Dataset Condensation. Dataset distillation (DD) [88, 106, 24, 51, 110, 23, 86, 49, 87, 6, 7] aims to distill large dataset into smaller but informative synthetic one. The proposed method imposes constraints on the synthetic samples by minimizing the training loss difference, while ensuring that the samples remain informative. This technique is useful for applications such as continual learning [105, 106, 39, 44, 104], as well as neural architecture search [61, 62, 96]. Recently, GCond [37] is proposed to reduce a large-scale graph to smaller one for node classification using the gradient matching scheme in DC [105]. Unlike GCond [37], who build the structure only through the learned feature, we explicitly broadcast the original graph structure to the generations to prevent the overlooking of the original graph structure information.
Graph Coarsening & Graph Sparsification. Graph Coarsening [53, 52, 14] follows the intuition that nodes in the original graph can naturally group the similiar node to a super-nodes. Graph Sparsification [66, 38, 78] is aimed at reducing the edges in the original graph, as there are many redundant relations in the graphs. We can simply sum up both two methods by trying to reduce the "useless" component in the graph. Nevertheless. these methods primarily rely unsupervised techniques such as the largest cigenvalue [66] or the multilevel incomplete LU factorization [14], which cannot guarantee the behavior of the synthetic graph in downstream tasks. Moreover, they fail to reduce the graph size to an extremely small degree (e.g., reduce the number of nodes to 0.1 % of the original). In contrast, graph condensation can aggregate information into smaller yet informative graph in a supervised way, thereby overcoming the aforementioned limitations.
3 Preliminary and Analysis
3.1 Formulation of graph condensation
Consider a graph dataset G {A, X. X.Y), where A E N.N denotes the adjacency matrix, X E N xd is the feature, and Y E Nx1 represents the labels. S = (A', X', Y'} is defined as the synthetic dataset, the first dimension of A', X', and Y' are N' (N' < N).
The goal of graph condensation is achieving comparable results as training on the original graph dataset G via training on the synthetic one S. The optimization process can be formulated follow,
S* arg min M(0', 0g) s.t 0r arg min Loss (N))
(1)
where GNN, (1) denotes a GNN parameterized with 0, 0s and 0g are the parameters that are trained on S and G. and t e (8,9). M(-) denotes matching function and Loss(-) is the loss function.
3

---

Original
Original
GCN
8C00
p q
SC:0.19
Avg.75.16
Avg.76.30
SGC
SC:0.77
pm3. q
SC:024
Avg.73.32
Avg:73.30
APPNP
SC-0.37
p=1, q=3
SC:039
Avg.70.36
Avg.66740
SAGE
SC-0.42
p=0, q=4
Avg. Avg.662.50
Avg.063.30
0.0
2.0
À
À
(a) LEDs in various architectures
(b) LEDs in BWGNN [82]
Figure 2: (a): Illustrations of the LEDs (use the density plotting, each peak represents the LED of graph), SC, and Avg. (average test performances on GCN, SGC, APPNP, and SAGE) in various architectures. (b): Evaluation of these three metrics in frequency-adaptiv BWGNN. We empirically find that the LED shifts (i.e., SC) are high-consistent with Avg. performances, thus SC could be good indicator to evaluate the performance of the condensed graph.
3.2 Analysis of the structure of the condensed graph and its effeets
In this section, we first introduce the definition of Laplacian Energy Distribution (LED), then analyze the LED previous work, and finally explore its influence on generalization performance.
Laplacian Energy Distribution. Following the previous works [25, 12, 82], we introduce Laplacian energy distribution (LED) to analyze the structure of graph data. Given adjacency matrix A RNZK the Laplacian matrix is defined as D A, where the D is the degree matrix of A. We utilize the normalized Lapalacian matrix L = - D-112 AD-1/2, where I an identity matrix. The eigenvalues of are then defined as At.... An AN by ascending order, i.e., À1 < ... A, S .... AN. with orthonormal eigenvectors U (u1, Un, uN) correspond to these eigenvalues.
xN) E Rxd be the feature of graph, we have X (Ø) ........ -t. ...... U X as the post-Graph Crap-Gaah-Forrier Fourier- Transform of X. The formulation of LED is defined as:
Definition 1 (Laplacian Energy Distribution [25, 12, 82)). Let X (II, ... In. IN)
422
Th [X,
(X L)
Fn.
Σm= #
LED analysis of previous work. First, we define n and 7 as the LED of the original graph and condensed graph, respectively. Then the LED shift of the above two graphs can be formulated as:
||ns - D TH (X, L) شラ= (X',', L')lI. In GCond [37], the matching function M defaults the MSE loss. Therefore, the objective GCond can be written as ||6g Asll S c, where e is a small number as expected. Incorporating such an objective in the LED shift formula, the lower bound is shown as follows.
Proposition 1. Refer to [1, 4, 82], the GNN can be recognized the bandpass filter. Assume the frequency response area of GNN is (a, b), where (a, b) is auchitecture-specffee The lower bound of GCond is shown in Eq. (3). Detailed proof can be found in Appendix B.I.
N'
11
17
T
x 2
(3)
j=b
According to Eq. (3), we find the lower bond of LED in GCond is related to the frequency response area (a, b) (i.e., specific GNN). For example, GCN [40] or SGC [92] (utilized in GCond) is a low-pass filter [1], which emphasizes the lower Laplacian energy. As shown in Fig. 1(a), the A' is built upon the learned "low now-frequency" feature X', which may fail to generalize to cross-architecture (i.e., high-pass filters) and specific tasks.
Exploration the effects of LED shift on the generalization performance. Although the LED shift phenomenon occurs in GCond, quantifying the LED shift is challenging because G and S have

---

To prevent overlooking the original structure A from G, we broadcast A supervision for the generation of A/. Considering the different shapes between A and A' (N' < N), we introduce graphon [21, 70, 17, 33, 94] to distill the original structure information to the condensed structure A'. Specifically, given random noise Z(N') E R N x'' as the input coordinates, through the generative model, we then synthesize an adjacency matrix A' with N' nodes. This process can be formulated generative model with parameter h and the Optimizing X"
Optimizing A'
X
X
Gradient Matching
LED Matching
GEN
Distance
A
Broadcasting
2. 2 Laplacian pscudo-inverse
Z: Random noise
Freeze parameters
Figure 3: The Training pipeline of the SGDD (left). We first fix A' to optimize X' through the gradient matching strategy and we broadcast the supervision of A the generation of the graph structure A'. To mitigate the Laplacian Energy Distribution (LED) shift phenomenon, we propose the LED Matching strategy to optimize the A', which optimizes the learned structure with the optimal transport (OT) distance (right).
different numbers of nodes. To enable comparison, we follow an intuitive assumption that two nodes with similar eigenvalue distribution proportions can be aligned in comparison. Thus, we first convert LEDs of & and S into probability distributions using the Kernel Density Estimation (KDE) method [60]. Then we quantify the LED shifts as the distance of the probability distributions using the -Snsen-Shannon (JS) divergence [47]. We define the LED shift coefficient (SC') in Definition 2: Definition 2 (LED shift coefficient, SC). The LED shift coefficient between G and S is:
SC JS
Σ K ((- R,EXg
Σ TyEXs
K
T
Voll
Vslh
where the JS(-Il)) denotes the JS- JS-divergence, the VVll and the \Vsl is the number of the nodes to corresponding graphs, the K-)) represents the Gaussian kernel function with bandwidth parameter h. SC E [0, reflects the divergence between G and S (a smaller SC indicates more similar).
In Fig. 2, we empirically study the influences of SC in two settings: various GNNs Fig. 2(a) and fixed BWGNN [82] with adaptive bandpass in Fig. 2(b). Based on the results in Fig. 2, We have several observations: (I) The entangled learning paradigm that building structure (i.e., adjacency matrix) upon feature matrix will significantly lead to the LED shift phenomenon. (2) The positive correlation exists between the LED shift and the generalization performance of the condensed graph. (3) Preserving more information about the original graph structure may alleviate the LED shift phenomenon and improve the generalization performance of the condensed graph.
Structure-broodccsttnn Graph Dataset Distillation
In this section, first present the pipeline and overview of SGDD in Fig. 3. Then, introduce two modules of SGDD. Finally, we summarize the training pipeline of our SGDD.
4.1 Learning graph structure via graphon approximation
A' (EN"(((N): Φ), where the GEN(.) optimization process is then defined as:
Lstructure Distance A, GEN(Z(N')) 2)),
(5)
where A is supervision and Distance(-) is metric that measure the difference of A and A'. The
details of Distance(-)) can found in Sec. 4.2. avoid overlooking of the inherent relation [32, 73] between A' and the corresponding node information (i.e., X' and Y'), we jointly input X' and Y' as conditions to generate A'. Therefore, the final version the generative model can be written as A' GEN(Z((N)) + X' + Y Φ), the @ denotes the concatenate operation.
5

---

To study the performance of SGDD in the above paradigm, we theoretically prove the upper bound of LED shift in SGDD by invoking graphon theory. The result can be presented as follows.
Proposition The upper bound of the LED shift on SGDD shown as:
1|m9 - 11
('.
(6)
where on denotes the cut distance [54] and WA the graphon of A. See details Appendix B.2.
Note minimizing the upper bound of Eq. (6) is equal to optimizing the Lstructure on Eq. (5). Compared to the lower bound in (Eq. (3)), our upper bound is not related to any frequency response of specific GNN (i.e, the terms of Σ t |ه क5 +1 ||
x x221 []) As a result, SGDD may
perform better than the previous work, especially in the cross-are coss-architeccure setting and specific tasks.
4.2 Optimizing the graph structure via optimal transport
To mitigate the LED shift between A and A', ideally, can directly minimize the proposed SC. However, SC requires an extremely cone-consuming (O(N3)) [4, 58] eigenvalue decomposition operation. Therefore, propose the LED Matching strategy based on the optimal transport theory to form an efficient optimizing process.
Recall in the E4) of calculating SC, we first decompose the eigenvalue, followed by aligning the node through the IS divergence, which essentially compares the distribution proportions. The key point is to decide the node mapping strategy to align such two graphs. Alternatively, assuming we know the prior distribution of the alignment
S (i.e., we know the bijection of nodes in S to the 9) and denoting such alignment as St, we can directly measure the distance between G and S* by employing the 2- 2-Wasserstein metric[15, 56).
1 - 1
W2 (17 ,nStt
Furthermore, following the assumption previous work[56, 15], we have 17 ~ N (0, lib) and v ~N (o, lis.). Then, the (7) have closed-form expression[15] as follows:
1110 - -| Nt (r/b) + N' (Tis.) 2tr (vi5.1n13)
(8)
the I. denotes the Laplacian pseudo-inverse operation and the tr indicates the trace operation of matrix. Therefore, even though could not know the actual mapping strategy Sx, we can the infimum of all possible strategies as a proxy solution. Formally, following the prior work [56], we employ the function T transport plan in the metric space X' represent all feasible mapping strategies. Then, we use the T to represent the pushing forward process of transferring the distribution of rf to the v As result, the distance can be regarded as finding the infimum.
inf J 1|x -(x)))))) Twns=
|178 11
= =N'r(L'') - 2tr (L1)) ((bb)// LiP (13) 1/2 1/2
Here, due to the transport plan T is impractical in optimizing. following the previous work[15], we use P E N'N denotes as a free parameter serving as the direct mapping strategy between nodes. Thus, the Distance in the Eq. (5) could be directly optimized by the E9. (i.e., use the P represents all possible mapping strategies, the optimizing of P is equal to choosing a more optimal mapping strategy). In the experimental setting, we use the Sinkhorn-
Knopp[9] Sinkhorn-Knopp(99
algorithm to optimize P.
The overall time complexity is reduced to the O(N*) < ((N23333) Note that the T.G. may be too large for computing, so we empirically sample a medium size (e.g., 2,000 nodes) sub-structure in the experiment and ablate its influence in Appendix C.7.

---

Table 1: Comparisons to state-of-the- methods. SGDD achieves the highest results in most cases on node classification (NC), anomaly detection (AD), and link prediction (LP) tasks. We report test accuracy (%) on NC datasets (including Citeseer, Cora, Ogbn-arxiv, Flickr, and Reddit), Fl-macro (%) on AD datasets (including YelpChi and Amazon), and AUC (%) on LP datasets (including Citeseer-L and DBLP). Bold entries best results, underline mark the runner-ups.
Dataset
Ratio (r)
Random
Herding
K-Center
Coarsening
GDC
Geond
SGDD
Whole
0.90%
54.4.4.4
57.1
52,4428
52.2+0.4
66.8 66.8
70,5
69.5.0.4
Citeseer (41)
1.80%
64.2g17
66.721a
64.3g1.
59.0
66.9
70.6-0.9
70.2:08
71.7
3.60%
69.1
69.0go
69.1g01
65.320s
66.3g1.5
69.8-1.4
70.3
1.30%
63.6ga.7
67.0.1.
64.022.8
31.2.0.2
67.3
79.8
80.1
Cora [41]
2.0 2.60%
72.8
73.410
73.2+1.2
65.2
67. 07.6
80.1-0.8
80.6
81.2.02
5.20%
76.820.1
76.8
76.720.1
70.6
67.7g9.
79.3
80.4
NC
0.05%
47.1
52.4218
47.2
35.4
58.6.0.1
$9.2
60.8
Ogbn-arxiv [29]
0.25%
57.3
58.6+12
56.820.
43.5.0.2
59 29.9
65.8 63.2=0.a
41.
0.50%
60.0ga.9
60.4.0.
60.3
50.4.0.1
59.5
64.0..0.4
66.3
0.10%
41.8g2.0
42.5
42.0
41.920.2
46.3
46.5-004
26.9
Flickr [100]
0.50%
44.0g0.4
43,9
43.2+00.1
44.5
45.9
=0.1
47.1
47.2
1.00%
44.6:0.2
44,4
44.4
44,6.0.1
45.8 45.8
47.1
47.1
0.01%
46. 24.4
53.1
46.612.a
40.9
88.2.0.2
88.0=1.8
90.5
Reddit [26]
0.05%
58.0.2.2
62.7a1.
53.0
42.8
89.5
89.6..07
91.8
93.9
0.50%
66.321.
71.0g15
58.5+2.1
47.4
90.521.2
90.1
91.6218
0.05%
41.8
46.1
49.3
46.2.22
47.9
48.6...7
56.2
YelpChi [68]
0.10%
43.7g1.a
47.1g12
44.2
47.5
50.2
49.6_1.8
58.1
61.1_1
0.20%
45.9222
46.420.
47.5
49.1
49.722.0
50.1
59.7
AD
0.02%
76.220.8
74.1209
73.4
75.222
14.1
77.9
83.3
Amazon [102]
0.20%
76.421.
76.5
74.2
76.821.
78.2
78.1
84,8
89.5
2.00%
78.220.
77.221
13.8
77.8
79.3.3.1
79.2
86.9
0.90%
56.820.8
63.1
78.3+2.
76.920.8
81.5222
83.4-.9
86.4
Citeseer-L [97]
1.80%
61.421.8
63.3214
79.1
77.4
83.4216
83.8-
87.2
96.8
3.60%
63.5 63.5g0.9
64.7
80.6
78.4004
84.2
83.1
87.1
LP
0.05%
64.1
65.820.7
72.441.
77.8
78.9.2.1
77.2-211
81.3
DBLP [83]
0.25%
68.321.4
71.2+1.7
74.942.
76.940.
77.5
78.6-1.2
82.1=1.
84.2.0.7
0.50%
68.7
74.3
75.24..
76.8.2.1
77.6.2.1
79.9-
82.1
4.3
Training pipeline of SGDD
As illustrated in Fig. ((d) and Fig. 3, we commence by introducing novel graph structure learning paradigm termed "graphon approximation". This paradigm integrates both the feature X' and auxiliary information Z to generate the structure. Subsequently, the learned structure A' is forced to be closer to the original graph structure A in terms of Laplacian energy distribution.
Additionally, our proposed methodology, SGDD, implements a bi-loop optimization schema. Within this framework, we concurrently optimize the parameters X' and A'. More specifically, the refinement of X' is achieved through gradient matching strategy, whereas the A' is enhanced using the LED matching technique. During each step, the other component is frozen to ensure effective refinement.
Our overall training loss function can be summarized as C = L feature + aLstructure + B1 A 122, where the ||||| is proposed as a sparsity regularization term and feature denotes the gradient matching strategy [37]. a and | are trade-off parameters, we study their sensitiveness in the Sec. 5.3. The algorithm can be found in Appendix C.3.
5
Experiments
5.1 Datasets and implementation details
Datasets. We evaluate SGDD on five node classification datasets: Cora [41], Citeseer [41], Ogbn- arxiv [29], Flickr [100], Reddit [26], two anomaly detection datasets: YelpChi [68], Amazon [102], and two link prediction datasets: Citeseer-L [97], DBLP [83]. For the node classification and anomaly detection tasks, we follow the public settings [18] of train and test. To make a fair comparison, we also follow the previous setting [101, 83), we randomly split 80% nodes for training, 10% nodes for validation, and the remaining 10% for testing. To avoid data leakage, we only utilize 80% training samples for condensation. More details of each dataset can be found in Appendix C.I.
7

---

70-
75
60
700
Spursity F1st
Performunce
60
55
Per Performance
8
68
45
55
30
50
F7 45
15
45
6.02
le
1e
10
Ogbn-arxiv
YelpChi
Condensing Ratio (16)
GCod
Original
GDC
Yayai
Optnandi
Spunity
(a) Ablation of X' and A.
(b) Evaluation of r(%)
(c) Evaluation of c
(d) Evaluation of B
Figure 4: (a) Ablation of components in SGDD. (b) Evaluation of the scalability of SGDD. (c) and (d): the trade-off parameters analysis and [.
Implementation details. Without specific designation, in the condense stage, we adopt the 2-layer GCN with 128 hidden units as the backbone, and we adopt the settings on [94], which use 2-layer MLP represent the structure generative model (i.e., GFN). The learning rates for structure and feature are set to 0.001 (0.0001 for Ogbn-arxiv and Reddit) and 0.0001, respectively. We set to 0.1, and B to 0.1. In the evaluation stage, we train the same network for 1,000 epochs on the condensed graph with learning rate of 0.001. Following the settings in [37]. repeat all experiments ten times report average performance and variance. More details* can be found in Appendix C.2.
5.2 Comparison with state-of-the-art methods
We compare our proposed SGDD with six baselines: Random, which randomly selected nodes to form the original graph, corset methods (Herding [90] and K-Center [72]), graph coarsening methods (Corasening [30]), and the state-of-the-at graph condensation methods (GCond [37]). GDC proposed as a baseline in [37], where cosine similarity is added as constraint to generate the structure of the condensed graph. In Table 1, we present the performance metrics including accuracy, Fl-macro, and AUC. For clarity and simplicity, percentages are represented without the % symbol, and variance values are provided. Based on the results, we have the following observations: 1) Our proposed SGDD achieves the highest results in most settings, which shows the superiority and generalization of method. 2) On anomaly detection datasets, the improvements significant than other tasks, i.e., improving GCond with 9.6% and 7.7% on YelpChi and Amazon datasets, which can be explained that our method captures the structure information from the original graph dataset more efficiently.
more
Table 2: Results of cross-architecture setting, we condensed graphs in APPNP, Cheby, GCN, GraphSAGE, and SGC. Avg. and Std. the average performance and the standard deviation the
results, the A denotes the improvements upon the GDC. We mark the best performance by bold.
Datasets
Methods
MEP
DAT]S4]
APPNE
Architectures
Cheby [13]
GCN [1]
SAGE [26]
SGC 192]
Statisties
Sid.
4(%)
GDC
81.2
17.5
89.3
$9.7
50.3
16.9
Reddit [26]
GCond
42.5
60.2
87.8
75.5
89.4
89.1
89.6
76.3
18.5
0.1
89.2
4.7
GDC
67.2
64.2
67.1
67.7
67.9
66.2
72.3
67.6
2.6
Cora [4]]
GCond
73.1
66.2
78.5
76
80.1
78.2
79.3
75.9
4.9
8.3
78.4
78.5
79.8
GDC
74.4
76.8
71.4
76.7
78.9
74.8
78.4
76.8
1.7
DBLP (83)
GCond
78.9
76.1
79.6
77.4
Ours
78.4
79.6
80.1
80.6
82.1
80.7
81.4
80.4
1.2
3.6
GDC
30.7
36.4
43.7
41.3
49.6
47.4
30.1
42.8
7.2
YelpChi [68]
Ours
$4.2
56.4
58.2
56.8
59.7
$4.1
56.7
56.6
2.0
13,8
5.3
Ablation Study
Cross-architecture generalization analysis. To evaluate the generalization ability of SGDD on unseen architectures, we conduct experiments that train on the condensed graph with different
'The code available in http://giitbbbco///iiiggSSss///s based PyTorch[65] and MindSpore[31].

---

Table 3: Comparison of the cross-architecture gener- alization performance between GCond and SGDD on Ogbn-arxiv. Bold entries are the best results. 1/j: our method show increase or decrease performance.
Table 4: Neural Architecture Search. Methods are compared in validation accuracy correlation and test accuracy on obtained architecture
CIT
APPNP Giloedl SCIDU
Clubo GDond/ / SCaID
GUN OChed SSCDD
SAGE Oceed/ SGIDO
SGC (iCodd SCE3D
Peanson Cormestion Perfomance (%)
Whole
APPSP
66.3:
889/624
59.0 68.2
61.2/81 414
Dotaset
Random
GCond
SCDD
(%)
Ogbo-aravv
0.63/711
064/71.2
0.67 77.6
71.9
GCN
SAGE
SGC
59.7/ (UU0
57.6:SUM SU.
AL.::AL1:
515/55.7
49.5/52.31
51.5/535
00:5 64.2
59.2/63.3
581/663
569/022
57.5/61.88
60.2/60.2:
60.5/615)
59.1/
59.0/61.1
YelyOhi
DRLP
0
0.58/81.2
062/815
048: 58.4
0,56 6666
0.68/84.
61.1
84.2
architectures and report their performances in Tab. 2. Here, the condensed graph is obtained by optimizing SGDD with SGC [92]. We test its crosttrcchte generalization performances on 2-layer-MLP [11], GAT [84), APPNP [42], Cheby [13], GCN [41], and SAGE [26].
To better understand, we also show several statistics metrics, including Avg., Std., and A. SGDD and GCond improves GDC significantly, which indicates there exists a large difference between graph dataset condensation and vision dataset distillation, i.e,, the structure information should be specially considered. Compared to GCond, the improvement of our method is up to 11.3% demonstrating the effectiveness of broadcasting the original structure to the condensed graph structure generation. More experiments on other datasets can be found in Appendix C.6.
Versatility of SGDD. Following the setting of GCond [37], we also study whether our proposed SGDD is robust on various architectures. We first condense the Ogbn-arxiv graph dataset with five architectures, including APPNP [42], Cheby [13], GCN [41], SAGE [26], and SGC [92], respectively. Then, we evaluate these condensed graphs on the above five architectures and report their
performances in Tab. 3. The experiment results show that SGDD achieves non-trivial improvements than GCond in most cases, which demonstrates the strong versatility of our method.
Evaluation on neural architecture search. Similar to vision dataset distillation, graph dataset distillation is also expected to reduce the high cost of neural architecture search (NAS). In order to make fair comparison, we follow the experimental setting in [37]: searching architectures on condensed Obgn-arxiv, YclpChi, and DBLP datasets with 0.25%, 0.2%, and 0.5% condensing ratios. We report Pearson correlation [45] and performance of random, GCond, and SGDD in Tab. 4. Our SGDD consistently achieves the highest Pearson correlations as well as performances, which indicates the architectures searched by our method are efficient for the whole graph dataset training.
Evaluation of components SGDD. To explore the effect of the conditions (mentioned Sec. 4.1) in the condensed graph generation, we design the ablation study of X' and A. As shown in Fig 4(a), X' and A are complementary with each other. SGDD w/o performs poorly on Obgn-arxiv and YelpChi datasets, which demonstrates the effect of original graph structure information. Jointly using X' and A achieves the highest performances on both datasets, improves GCond with 3.1% on Ogbn-arxiv, and 8.0% on YclpChi.
Evaluation of the scalability of SGDD, To investigate the scalability of SGDD, we evaluate the SGDD on various condensing ratios with E {0.02, 0,2, 5, 10, 20) As shown in Fig. 4(b), the performance of our method continuously increase as the condensing ratio rises, which indicates the strong scalability of our method. GCond obtains marginal improvements than GDC at all ratios while our SGDD outperforms them significantll.. More important, SGDD achieves lossless performance as training on the original graph data when the condensing ratio is 10%.
Exploring the sensitivity of a and 8. We conduct experiments to test such two parameters sensitivity on YelpChi, Cora, and Ogbn-arxiv. As shown in Fig. 4(c), we empirically find that the performance of our SGDD is not sensitive the a. Specifically, compared to the case that a is zero, we have significant improvement, which proves the effectiveness of our method. Another finding is that the a should be set higher on anomaly detection than on node classification tasks. It could be explained by the original graph structure information being more important on the complex task (such as anomaly detection). We define 3 as a regularization coefficient to control the sparsity of the condensed graph. As shown in Fig. 4(d), we evaluate the 33 from 0 to 10 on the YelpChi dataset. The results illustrate that the performance is not sensitive with 3 and achieve the highest result (F1-macro) when 3 is set to our default value (5- 0.1). More experiments can be found in Appendix C.5.

---

SC:0.31
SC:0.22
SC:0.0
ACC: 64.1
ACC: 67.3
(a) Original Ogbn-arxiv
(b) Condensed by GCond [37]
(c) Condensed by SGDD
15
-12
-02
80
SC:0.45
SC
-37
ACC: 66.5
90 109
130
(d) Original synthetic graph
(c) Condensed by GCond [37]
(f) Condensed by SGDD
Figure Visualizations of the real dataset (a), synthetic dataset (d), and the corresponding condensed
graph obtained by GCond (b, e) and SGDD (c, f). The condensing ratio is set to 0.5%.
5.4 Visualizations
To better understand the effectiveness of our SGDD, visualize the condensed graphs of GCond and SGDD that are synthesized from real and synthetic graph datasets. For the synthetic graph dataset, use the Stochastic Block Model (SBM) [28] to synthesize graphs with community (Fig. 5(d)). As shown in Fig. 5, one can find that our method consistently achieves better performances and SC. SGDD reduces 29.0% (comparing 5(b) and 5(c)) and 62.2% (comparing 5(c) and 5(D) SC on Ogbn-arxit arxiv and synthetic datasets. Visually, the condensed graphs of our method preserve the original graph structure information obviously better than GCond (see the second row of Fig. 5), which proves SGDD is powerful graph dataset distillation method.
6 Conclusion
We present SGDD, novel framework for graph dataset distillation via broadcasting the original structure information to the generation of the synthetic one. SGDD shows its robustness on various tasks and datasets, achieving state-of-the-an results on YelpChi, Amazon, Ogbn-arxiv, and DBLP. SGDD reduces the scale of the Yelpchi dataset by 1,000 times while maintaining 98.6% as training on the original data. We provide sufficient experiments and theoretical analysis in this paper and hope can help the following research in this area. Limitations and future work: Although broadcasting the original information the generated graph shows remarkable success, some informative properties (e.g., the heterogeneity) may lose during the current condense process, which results in sub-optimal performance the downstream tasks, We are going to explore a more general method in the future.
Acknowledgement
The corresponding author is Jianxin Li. This work was supported by the NSFC through grant No. 20.66225202 and No.62302023. This research is supported by the National Research Foundation, Singapore under its Al Singapore Programme (A (AISG Award No: AISG2-PhD-200 100-2001----000 Yang You's 's research group is being sponsored by NUS startup grant (Presidential Young Professorship), Singapore MOE Tier-1 grant, ByteDance grant, ARCTIC grant, SMI grant, and Alibaba grant. We gratefully acknowledge the support of MindSpore, CANN(Compute Architecture for Neural Networks) and Ascend AI Processor used for this research.
10

---

References
[1] Muhammet Balcilar, Guillaume Renton, Pierre Héroux, Benoit Gaüzère, Sébastien Adam, and Paul Honeine. Analyzing the expressive power of graph neural networks in spectral perspective. In 9th International Conference on Learning Representations, Virtual Event, Austria, May 3-7, 2021, 2021.
[2] Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks, ArXiv preprint. 2018.
[3] Daniel Bear, Chaofei Fan, Damian Mrowca, Yunzhu Li, Seth Alter, Aran Nayebi, Jeremy Schwartz, Li Fei-Fei, Jiajun Wu, Josh Tenenbaum, and Daniel L. Yamins. Learning physical graph representations from visual scenes. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, December 6- 12, 2020, virtual, 2020.
[4] Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks graphs. In Yoshua Bengio and Yann LeCun, editors, 2nd International Conference on Learning Representations, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014.
[5] Chen Cai, Dingkang Wang, and Yusu Wang. Graph coarsening with neural networks, In 9th International Conference on Learning Representations, Virtual Event, Austria, May 3-7, 2021, 2021.
[6] George Cazenavette, Tongzhou Wang, Antonio Torralba, Alexei A. Efros, and Jun- Yan Zhu. Dataset distillation by matching training trajectories. In /EEE/CVF Conference on Computer Vision and Patter Recognition Workshops, CVPR Workshops 2022, New Orleans, LA, USA, June 19-20, 2022, pages 4749-4758 2022.
[7] George Cazenavette, Tongzhou Wang. Antonio Torralba, Alexei A Efros, and Jun- Yan Zhu. Generalizing dataset distillation via deep generative prior. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 3739-3748 2023.
[8] Yu Chen, Lingfei Wu, and Mohammed Zaki. Iterative deep graph learning for graph neural networks: Better and robust node embeddings. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, December 12, 2020, virtual, 2020.
[9] Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport, Christopher J. C. Burges, Léon Bottou, Zoubin Ghahramani, and Kilian Q. Weinberger, editors, Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States, pages 2292-2300, 2013.
[10] Évariste Daller, Sébastien Bougleux, Luc Brun, and Olivier Lézoray. Local patterns and supergraph for chemical graph classification with convolutional networks. In Structural, Syntactic, and Statistical Pattern Recognition Joint IAPR International Workshop, S+SSPR 2018, Beijing, China, August 17-19, 2018, Proceedings, volume 11004, pages 97-106, 2018.
[11] Tuan Van Dao, Hiroshi Sato, and Masao Kubo. Mip-mixer-atttencodeer A lightweight ensemble architecture for malware classification. Inf., 14(3):167, 2023.
[12] Kinkar Ch. Das, Seyed Ahmad Mojallal, and Vilmar Trevisan. Distribution of laplacian cigenvalues of graphs. Linear Algebra and its Applications, 508:48-61, 2016.
[13] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Garnett, editors, Advances in Neural Information
11

---

Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016,
December 5-10, 2016, Barcelona, Spain, pages 3837-3845, 2016.
[14] Chenhui Deng, Zhiqiang Zhao, Yongyu Wang, Zhiru Zhang, and Zhuo Feng. Graphzoom: A multi-level spectral approach for accurate and scalable graph embedding. In 8th International Conference on Learning Representations, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
[15] Yihe Dong and Will Sawin. CОPT: coordinated optimal transport on graphs. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florin Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, December 6-1 2020, virtual, 2020.
[16] Holger Ebel and Stefan Bornholdt. Coevolutionary games networks. Physical Review E, 66(5):056115 18,56618,2200 2002.
[17] Justin Eldridge, Mikhail Belkin, and Yusu Wang. Graphons, mergeons, and so on! In Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Garnett, editors, Advances in Neural Information Processing Systems 29; Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 2307-2315, 2016.
[18] Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. ArXiv preprint, 2019.
[19] Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He. Learning discrete structures for graph neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 1972 1982, 2019.
[20] Alan Frieze and Ravi Kannan. Quick approximation to matrices and applications. Combina- torica, 19(2):175-255 220,, 1999.
[21] Shuang Gao and Peter E Caines. Graphon control of large-scale networks of linear systems. IEEE Transactions on Automatic Control, 2019.
[22] Jiahui Geng, Zongxiong Chen, Yuandou Wang, Herbert Woisetschlaeger, Sonja Schimm- ler, Ruben Mayer, Zhiming Zhao, and Chumming Rong. A survey on dataset distillation: Approaches, applications and future directions. ArXiv preprint, abs/2305.01975, 2023.
[23] Jianyang Gu, Kai Wang. Wei Jiang, and Yang You. Summarizing stream data for memory- restricted online continual learning. ArXiv preprint, abs/2305.16645, 2023.
[24] Ziyao Guo, Kai Wang, George Cazenavette, Hui Li, Kaipeng Zhang, and Yang You. To- wards lossless dataset distillation via difficulty-aligned trajectory matching. ArXiv preprint, abs/2310.05773, 2023.
[25] Ivan Gutman and Bo Zhou. Laplacian energy of graph. Linear Algebra and its Applications, 414(1):29-37, 2006.
[26] William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, V. N. Vishwanathan, and Roman Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 1034-1034, 2017.
[27] Peter D Hoff, Adrian E Raftery, and Mark S Handcock. Latent space approaches social network analysis. Journal of the american Statistical association, 109060): 2002.
[28] Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks, 5(2):109-137, 1983.
12

---

[29] Weihua Hu, Matthias Fey. Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan- Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, December 6-12, 2020, virtual, 2020.
[30] Zengfeng Huang, Shengzhong Zhang, Chong Xi, Tang Liu, and Min Zhou. Scaling up graph neural networks via graph coarsening. In In Proceedings the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 221), 2021.
[31] Huawei. Mindspore. https: //www/ http::////wmmmmmnprrr... 2020.
[32] Joseph J. Pfeiffer III, Sebastián Moreno, Timothy La Fond, Jennifer Neville, and Brian Gallagher. Attributed graph models: modeling network structure with correlated attributes. In Chin-Wan Chung, Andrei Z. Broder, Kyuseok Shim. and Torsten Suel, editors, 23rd International World Wide Web Conference, WWW '44 Scoul, Republic of Korea, April 7-11, 2014, pages 831-842, 2014.
[33] Svante Janson. Graphons, cut norm and distance, couplings and rearrangements. New York journal of mathematics, 2013.
[34] Svante Janson and Persi Diaconis. Graph limits and exchangeable random graphs. Rendiconti di Matemalica e delle sue Applicuzioni. Serie VII, pages 33-61, 2008.
[35] Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. In Rajesh Gupta, Yan Liu, Jiliang Tang, and B. Aditya Prakash, editors, KDD '20: The 26th ACM Conference on Knowledge Discovery and Data Mining, Virtual Event, CA, USA, August 23-27, 2020, pages 66-74, 2020.
[36] Wei Jin, Xianfeng Tang, Haoming Jiang, Zheng Li, Danqing Zhang, Jiliang Tang, and Bing Yin. Condensing graphs via one-step gradient matching. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2022.
[37] Wei Jin, Lingxiao Zhao, Shichang Zhang, Yozen Liu, Jiliang Tang, and Neil Shah. Graph condensation for graph neural networks. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022, 2022.
[38] David R. Karger. Random sampling in cut, flow, and network design problems. Math. Oper. Res., 24(2):383-413, 1999.
[39] Jang-Hyun Kim, Jinuk Kim, Scong Joon Oh, Sangdoo Yun, Hwanjun Song, Joonhyun Jeong, Jung-Woo Ha, and Hyun Oh Song. Dataset condensation via efficient synthetic-data parame- terization. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song. Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning. 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 11102-11118 2022.
[40] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
[41] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
[42] Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In 7th International Conference on Learning Representations, New Orleans, LA. USA, May 6-9, 2019, 2019.
[43] Eric D. Kolaczyk. Statistical Analysis of Network Data: Methods and Models. IEEE, 2009.
13

---

[44] Sachyung Lee, Sanghyuk Chun, Sangwon Jung, Sangdoo Yun. and Sungroh Yoon. Dataset condensation with contrastive signals. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song. Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 12352-12364, 2022.
[45] Guanzhi Li, Aining Zhang, Qizhi Zhang, Di Wu, and Choujun Zhan. Pearson correlation peefficentt-bseed performance enhancement broad learning system for stock price prediction. IEEE Trans. Circuits Syst. II Express Briefs, 69(5):44332441 2022.
[46] Jianxin Li, Qingyun Sun, Hao Peng, Beining Yang, Jia Wu, and S Yu Phillp. Adaptive subgraph neural network with reinforced critical structure mining. IEEE Transactions on Puttern Analysis and Machine Intelligence, 2023.
[47] Jianhua Lin. Divergence measures based on the shannon entropy. IEEE Trans. Inf. Theory, 37(1):145-151, 1991.
[48] Zhiqi Lin, Cheng Li, Youshan Miao, Yunxin Liu, and Yinlong Xu. Pagraph: Scaling gnn training on large graphs via computation-awaat caching. In Proceedings of the 11th ACM Symposium on Cloud Computing, 2020.
[49] Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: differentiable architecture search. In 7th International Conference on Learning Representations, New Orleans, LA, USA, May 6-9, 2019, 2019.
[50] Mengyang Liu, Shanchuan Li, Xinshi Chen, and Le Song. Graph condensation via receptive field distribution matching. ArXiv preprint, abs/2206. 13697, 2022.
[51] Yanqing Liu, Jianyang Gu, Kai Wang, Zheng Zhu, Wei Jiang, and Yang You. Dream: Efficient dataset distillation by representative matching. ArXiv preprint, abs/2302. 144166, 2023.
[52] Andreas Loukas. Graph reduction with spectral and cut guarantees. Mach. Learn. Res.,
20: 16::161:111:42 2019.
[53] Andreas Loukas and Pierre Vandergheynst. Spectrally approximating large graphs with smaller graphs. In Jennifer G. Dy and Andreas Krause, editors, Proceedings the 35th International Conference on Machine Learning, Stockholmsmüsssan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 3243-3252. 2018
[54] László Lovász. Large networks and graph limits, volume 60. IEEE, 2012.
[55] Dongsheng Luo, Wei Cheng, Wenchao Yu, Bo Zong, Jingchao Ni, Haifeng Chen, and Xiang Zhang. Learning to drop: Robust graph neural network via topological denoising. WSDM, pages 779-787, 2021.
[56] Hermina Petric Maretic, Mireille El Gheche, Giovanni Chierchia, and Pascal Frossard. GOT: an optimal transport framework for graph comparison. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' JccééBBue, Emily B. Fox, and Roman Gameett, editors. Ad- vances in Neural Information Processing Systems 32: Annual Conference on Neural Infor- mation Processing Systems 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 13876-13887, 2019.
[57] Brendan D. McKay, Mehmet Aziz Yirik, and Christoph Steinbeck. Surge: a fast open-source chemical graph generator. Cheminformatics, 2022.
[58] Facundo Mémoli. Spectral Gromov-Wasserstein distances for shape matching. In ICCV Workshops, pages 256-263, 2009.
[59] Matthew W. Morency and Geert Leus. Graphon filters: Graph signal processing in the limit. 2021.
IEEE Trans. Signal Process.,
14

---

[60] Bilal Nehme. Olivier Strauss, and Kevin Loquin. Estimating the variance of a kernel density estimation. Christian Borgelt, Gil Konzzlez-Rodrigee Wolfgang Trutschnig, María Asun- ción Lubiano, María Angeles Gil, Przemyslaw Grzegorzewski, and Olgierd Hryniewicz. editors, Combining Soft Computing and Statistical Methods in Data Analysis, SMPS 2010, Oviedo, Spain, September 29 October 2010, volume 77 of Advances in Intelligent and Soft Computing, pages 483 493, 2010.
[61] Timothy Nguyen, Zhourong Chen, and Jaehoon Lee. Dataset meta-leaming from kernel ridge-regression. In 9th International Conference on Learning Representations, Virtual Event, Austria, May 3-7, 2021, 2021.
[62] Timothy Nguyen, Roman Novak, Lechao Xiao, and Jachoon Lee. Dataset distillation with infinitely wide convolutional networks. In Mare Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Informa- tion Processing Systems 34: Anmual Conference on Neural Information Processing Systems 2021, December 64, 2021, virtual, pages 5186-5199 2021.
[63] Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang. Lina Yao, and Chengqi Zhang. Adversarially regularized graph autoencoder for graph embedding. In Jérôme Lang, editor, Proceedings of the Twenty-Sevens International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden, pages 2609 2615, 2018.
[64] Francesca Parise and Asuman Ozdaglar. Graphon games: A statistical framework for network games and interventions. ArXiv preprint, abs/1802.00080, 2018.
[65] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- gegh-performance deep learning library. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' A'AhhheBBue Buce Emily Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, December 14, 2019, Vancouver, BC, Canada, pages 8024-8035, 2019.
[66] David Peleg and Alejandro Schäffer: Graph spanners. J. Graph Theory, 13(1)999-116, 1989.
[67] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: online learning of social representations. In Sofus A. Macskassy, Claudia Perlich, Jure Leskovec, Wei Wang, and Rayid Ghani, editors, The 20th ACM International Conference on Knowledge Discovery and Data Mining, KDD '14 New York, NY, USA August 24 27, 2014, pages 701-710, 2014.
[68] Shebuti Rayana and Leman Akoglu. Collective opinion spam detection: Bridging review networks and metadata. In Longbing Cao, Chengqi Zhang, Thorsten Joachims, Geoffrey I. Webb, Dragos D. Margineantu, and Graham Williams, editors, Proceedings of the 21th ACM International Conference on Knowledge Discovery and Data Mining, Sydney, NSW, Australia, August 10-13, 2015, pages 985-994, 2015.
[69] Luana Ruiz, Luiz F. O. Chamon, and Alejandro Ribeiro. The graphon fourier transform. In 2020 IEEE International Conference on Acoustics, Speech and Signal Processing, Barcelona, Spain, May 4-8, 2020, pages 1660-5664, 2020.
[70] Luana Ruiz, Luiz F. O. Chamon, and Alejandro Ribeiro. Graphon neural networks and the transferability of graph neural networks. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Floring Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, December 6-1,, 2020, virtual, 2020.
[71] Luana Ruiz, Luiz FO Chamon, and Alejandro Ribeiro. Graphon signal processing. IFEE Transactions on Signal Processing, 69:4961-4976, 2021.
15

---

[72] Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. In 6th International Conference on Learning Representations, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings, 2018.
[73] Cosma Rohilla Shalizi and Andrew C. Thomas. Homophily and contagion are generically confounded in observational social network studies. CoRR, abs/1004.47044, 2010.
[74] Chao Shang, Jie Chen, and Jinbo Bi. Discrete graph structure learning for forecasting multiple time series. In 9th International Conference on Learning Representations, Virtual Event, Austria, May 3-7, 2021, 2021.
[75] Mingjia Shi, Yuhao Zhou, Kai Wang, Huaizheng Zhang, Shudong Huang, Qing Ye, and Jiancheng Lv. PRIOR: Personalized prior for reactivating the information overlooked in federated learning. In Proceedings of the 37th NeurIPS, 2023.
[76] Vincent Sitzmann, Julien N. P. Martel, Alexander W. Bergman, David B. Lindell, and Gor- don Wetzstein. Implicit neural representations with periodic activation functions. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tiet Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, December 6-12, 2020, virtual, 2020.
[77] Daniel A. Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM
J. Comput., 1916))9113-1966 2011.
[78] Daniel A. Spielman and Shang- Teng. Spectral sparsification of graphs. SIAM J. Comput., 10(4),981- 2011.
[79] Qingyun Sun, Jianxin Li, Hao Peng. Jia Wu, Xingeheng Fu, Cheng Ji, and Philip S. Yu. Graph structure learning with variational information bottleneck. In Thirty-Sixth AAAI Conference on Artificial Intelligence, Virtual Event, February 22 March 2022, pages 0165-41725 2022.
[80] Qingyun Sun, Jianxin Li, Hao Peng, Jia Wu, Yuanxing Ning, Philip S Yu, and Lifang He. Sugar: Subgraph neural network with reinforcement pooling and self-supervised mutual information mechanism. In The International Conference of World Wide Web 2021, pages 2081-2091, 2021.
[81] Qingyun Sun, Jianxin Li, Haonan Yuan, Xingcheng Fu, Hao Peng. Cheng Ji, Qian Li, and Philip S Yu. Position-aware structure learning for graph topology-imballnn by relieving under- reaching and ever-squashing In International Conference on Information and Knowledge Management, pages 1848 1158-1857.00 2022.
[82] Jianheng Tang. Jiajin Li, Ziqi Gao, and Jia Li. Rethinking graph neural networks for anomaly detection. In Kamalika Chaudhuri. Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 21076-21089 2022.
[83] Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, and Zhong Su. Ametminer: Extraction and mining of academic social networks. Proceedings of the 14th ACM SIGKDD Interna- tional Conference on Knowledge Discovery and Data Mining, KDD '08, page 990-998, New York, NY, USA, 2008
[84] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph attention networks. In 6th International Conference on Learning Rep- resentations, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings, 2018.
[85] Renato Vizuete, Federica Garin, and Paolo Frasca. The laplacian spectrum of large graphs sampled from graphons. IEEE Transactions on Network Science and Engineering, page 1711-1721, Mar 2021.
[86] Kai Wang, Jianyang Gu, Daquan Zhou, Zheng Zhu, Wei Jiang, and Yang You. Dim: Distilling dataset into generative model. ArXiv preprint, abs/2303.04707, 2023.
16

---

[87] Kai Wang, Bo Zhao, Xiangyu Peng, Zheng Zhu, Shuo Yang, Shuo Wang, Guan Huang, Hakan Bilen, Xinchao Wang, and Yang You. Cafe: Learning to condense dataset by aligning features. In CVPR, 2022.
[88] Tongzhou Wang, Jun- Yan Zhu, Antonio Torralba, and Alexei A Efros. Dataset distillation. ArXiv preprint, 2018.
[89] Yili Wang, Kaixiong Zhou, Rui Miao, Ninghao Liu, and Xin Wang. Adagel: Adaptive subgraph contrastive learning to generalize large-scale graph training.
[90] Max Welling. Herding dynamical weights to learn. In Andrea Pohoreckyj Danyluk, Léon Bot- tou, and Michael L. Littman, editors, Proceedings of the 26th Annual International Conference Machine Learning, Montreal, Quebec, Canada, June 14-18, 2009, volume 382 of ACM International Conference Proceeding Series, pages 1121-1128, 2009.
[91] Gert W. Wolf. Facility location: concepts, models, algorithms and case studies. series: Contributions to management science. Int. J. Geogr. Inf. Sci., (5(2)333--333, 2011.
[92] Felix Wu, Amauri H. Souza Jr., Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Q. Weinberger. Simplifying graph convolutional networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Muchine Learning, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 6861-6877 2019.
[93] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S Yu. A comprehensive survey on graph neural networks. ArXiv preprint, 2019.
[94] Xinyue Xia, Gal Mishne, and Yusu Wang. Implicit graphon neural representation. In Proceed- ings of the 26th International Conference on Artificial Intelligence and Statistics,, 2023.
[95] Hongteng Xu, Dixin Luo, Lawrence Carin, and Hongyuan Zha. Learning graphons via structured wnssev-waserstein barycenters. In Thirty-Fifth AAAI Conference on Artificial Intelligence, Virtual Event, February 2-9, 2021, pages 10505-10513, 2021.
[96] Shuo Yang. Zeke Xie, Hanyu Peng, Min Xu, Mingming Sun, and Ping Li. Dataset pruning: Reducing training data by examining generalization influence. ArXiv preprint, abs/2205.09329, 2022.
[97] Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In Maria-Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of the 33nd International Conference Muchine Learning, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pages 40-48 2016.
[98] Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Yike Guo and Faisal Farooq, editors, Proceedings of the 24th ACM International Conference on Knowledge Discovery & Data Mining, London, UK, August 19-23, 2018, pages 974-983, 2018.
[99] Haiyang Yu, Limei Wang, Bokun Wang, Meng Liu, Tianbao Yang, and Shuiwang Ji. Graphfm: Improving saage-scale GNN training via feature momentum. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages
2022.
[100] Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor K. Prasanna. Graphsaint: Graph sampling based inductive learning method. In 8th International Conference on Learning Representations, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
[101] Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Gamettt, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, December 3-8, 2018, Montréal, Canada, pages 5171-5181, 2018
17

---

[102] Shijie Zhang, Hongzhi Yin, Tong Chen, Quoe Viet Hung Nguyen, Zi Huang, and Lizhen Cui. Gen-based user representation learning for unifying robust recommendation and fraudster detection. In Jimmy Huang, Yi Chang, Xueqi Cheng, Jaap Kamps, Vanessa Murdock, Ji-Rong Wen, and Yiqun Liu, editors, Proceedings of the 43rd International ACM conference on research and development in Information Retrieval, Virtual Event, China, July 25-30, 2020, pages 689-698, 2020.
[103] Yifan Zhang. Daquan Zhou, Bryan Hooi, Kai Wang, and Jiashi Feng. Expanding small- datasets with guided imagination. ArXiv preprint, abs/2211. 2022.
[104] Bo Zhao and Hakan Bilen. Dataset condensation with distribution matching. ArXiv preprint, abs/21 10.04181, 2021.
[105] Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. Dataset condensation with gradient matching. In 9th International Conference Learning Representations, Virtual Event, Austria, May 3-7, 2021, 2021.
[106] Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. Dataset condensation with gradient matching, In 9th International Conference on Learning Representations, Virtual Event, Austria, May 3-7, 2021, 2021.
[107] Tong Zhao, Yozen Liu, Leonardo Neves, Oliver J. Woodford, Meng Jiang, and Neil Shah. Data augmentation for graph neural networks. In Thirty-Fifth AAAI Conference on Artificial Intelligence, Virtual Event, February 2-9, 2021, pages 11015- 11033, 2021.
[108] Cheng Zheng, Bo Zong, Wei Cheng, Dongjin Song, Jingchao Ni. Wenchao Yu, Haifeng Chen, and Wei Wang. Robust graph representation learning via neural sparsification. In Proceedings of the 37th International Conference on Machine Learning, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 11458 1 11468, 2020.
[109] Xin Zheng, Miao Zhang, Chunyang Chen, Quoe Viet Hung Nguyen, Xingquan Zhu, and Shirui Pan. Structure-free graph condensation: From large-scale graphs to condensed graph-free data. In Advances in Neural Information Processing Systems, 2023.
[110] Daquan Zhou, Kai Wang. Jianyang Gu, Xiangyu Peng, Dongze Lian, Yifan Zhang, Yang You, and Jiashi Feng. Dataset quantization. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 17205-17216, 2023.
[111] Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang. Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. ArXiv preprint, 2018
18

---

A More Preliminary and Related Work
A.1 More preliminary
Graphon. A graphon [43, 34, 54] is a bounded, symmetric, and Lebesgue measurable function,
denote as W -22 >> [0, 1]. where a probability measure space. By randomly selecting points create a graph of any size by connecting each point with edge weight Eij W Uy). Formally, we can follow the random sampling process to get arbitrarily
{vo, U ) from 12,
sized (n) graphs:
0i ~ Uniform(S2,, for 1, .. Cij (ernonli(W(H; vy)), for i.
(10)
Conventionally, we use a deterministic setting to select the node, e.g., the fixed grid by 1 Graphs derived from the same graphon share several important properties for statistical analysis: such as density [21], clustering coefficient [70], and degree distribution [71], which motivate us to broadcast the original graph structure information the condensed graph via the graphon approximating.
A.2 More related work
Graph structure learning. Graph structure learning [19, 35, 8, 108, 55] also aims at jointly optimiz- ing the graph structure and the corresponding node features. Most of these methods learn the new structure based on the certain constraints (e.g., low-rank [91], sparsity [8], feature smoothness [35], and homophily [108]). However, these methods are unable learn a new structure with a signif- icantly reduced node size. In contrast, our method can synthesize smaller graph structure while simultaneously constructing new node features. The obtained small but informative graph can reduce the training cost in the downstream tasks.
B Proofs
B.1
Proof of Proposition
Proof. First, the gradient matching objective in GCond [37] can be shown as:
Match(
(A, Y)), VeLes (GNNo (A', X'), Y')),
(11)
where Match(-) is the matching function that measures the distance of the two gradients. 0 represents the parameters of the GNN, the V denotes the gradient in the backpropagation process, and the Cets represents the loss function that is used in the supervised tasks, i.e., cross-entropy loss. Following the discussion in the [4, 1, 82], the GNN can be viewed as a bandpass filter in the spectral domain. Expanding the GNN in the spectral domain, we can rewrite the objective as:
|1 11 UA diag(T
N'' f
U diag
Sc,
(12)
where the T(X) denotes the frequency response of the given GNN, the À and the U is the eigenvalue and eigenvector of the corresponding graph, respectively. Note we drop the V, the Lets- and the Y (Y') terms because they can be viewed the intermediate process [105, 107] in approximating to (12). We use the MSE [37] as the matching function Match(-) for simplicity.
To simplify T(A), without loss of generality,
assume the bandwidth of the specific GNN's frequency response is (a, b), which intuitively indicates that only the signal of frequency (a, b) can pass through the filter on the graph. Then the Eq. (12) can be written
/1/0 1=0 k=a
N'
UA (Ax X
UN diag Ax A
U Sc,
J
(13)
further combine the first integration, the objective can thus be summarized as:
11 k=a
(UA " UA diag(As "JU
cc
(14)
19

---

Then following the transformation in the spectral domain [1], we can briefly summarized:
x
S
(15)
Ama
Take the Eq. (15) into the ||150 11p11
M
11180 1/811
=11
-
Σ
Σ
(16)
20+ +
Σ
+
-
Note the second inequality is under the assumption: intuitively. the overall distance of ny and n should be larger than the condition that two graphs have the same size (i.e., N').
B.2 Proof of Proposition 2
To prove Proposition 2, we first introduce the following notations and theorems in graphon theory.
The cut norm [20, 54] is defined as:
|ilo: = sup xyCa xxy
((x, y)dady
(17)
where the Ω is the probability space of graphon W, the supremum is taken over all measurable subsets X' and y [95]. Then the cut distance between W1, W2 [54] can be defined as:
8 (W1, W2) = inf diESq
Wi w:] 1'
(18)
where the Sn is the set of measure- presuurvieeeeegiggggg mappings from Q to Ω. When two graphons W1, W2 have (W,, W2) = 0, they can be seen equivalent, denoted as W1 = W2.
To effectively approximate W in the real world graphs, works [54, 33, 17 introduce an approximation named step function. Let = (P,,..., Px) be partition of S2 into K measurable sets. The step function Wp Ω2 + [0, 1] is defined as:
W = Wkk Lp x (I,
(19)
R.K'=
where the Was E [0, 1] and the indicator function Ipp (z. y) is if (z, y) E Pk x Px, or it is
To explore the relationship between step function and the W, we introduce the Weak Regularity Lemma as follows.
Theorem (Weak Regularity Lemma [54]). For every graphon W E W and K < 1, there always exists a step function Wp with [P| = K steps such that
2
IW Wollo Vlog K W
(20)
We can further obtain the corollary that 8 (w) ||W Wellp- Intuitively, we can use any step function to approximate the ideal W real graphs.
Ving Wil,, as the 8 WP) <
Then to investigate the properties of the graphon in the spectral domain, following [71, 85, 59, 69]. we have the conclusion that:
Sw Sw, || S | Wrln.
(21)
where the S denotes the signal spectrum of the graphs [85] (i.e., the FosttGraaph-Fuurie- Transffrrm UT X), Intuitively, the Eq. (21) shows that when the step function Wp approximated the W, they have similar signal spectrum.
20

---

Proof. By combining the Theorem I and (21, the Proposition 2 replace the Wp with the WAA that's because we use the generative model (i.e., GEN(()) approximate the step function Wp. we aim to learn the graphon of the original structure A, the graphon W can be rewrite as WA
A'
S| Swal S II WAllD-
(22)
We notice that the S here is related to the Laplacian energy distribution (LED), where the LED represents the probability distribution the S, then we use the Σ ã; and Σj=1 Ty to represent the summation of the original signal spectrum and the condensed one, respectively, we have:
SWA
SW N'
11 1 ||
Σ 21
Σド=
S max
)|[S
Swall II
(23)
Ei=1 D4
Σj= B3
I - WAlln,
where in the second inequality, we drop the max(-) term since it always lower than As the WA here represents the graphon of the synthetic A', we can use the A' directly in the in to form compact upper bound.
1|m 7 (AAAWWA)
(24)
Note that minimizing the upper bound has been proven to be equivalent to minimizing the optimal transport distance between the two graphs [95].
B.3 Time complexity analysis and running time
Time complexity. For simplicity, let the number of MLP layers in GEN(-) be L,, and all the hidden units are d. In the forward process, we have three steps: first, we calculate the A' by the GEN(-), which have the complexity of d2) Second, the forward process of GNN on the original graph has complexity of O )f), where the m denotes the sampled size per node in training. Third, the complexity of training on the condensed graph (LN'd). In the backward process, the complexity of gradient matching strategy (i.e., f is [(0) [37]. For the structure optimization term (i.e, Lstructure), ). the complexity is O + 222), The overall complexity of SGDD be represented Note N' < N, we can drop the terms that only involve N' and constants (e.g., the number of L and m). The final complexity can be simplified as O(m Nd2) + O(N2N), thus the complexity of SGDD still be linear to the number of nodes in the original graph.
((0] +)) N N). (2 (md N
Running time. We report the running time of the SGDD in the two datasets: Ogbn-arxiv, and YelpChi. We vary the condensing ratio r in the range of [0.05%, 0.25%, 0.50% for Ogbn-arxiv and (0.05%, 0.10%, 0.20%) | for YelpChi. All experiments are conducted five times A100-SXM4 GPU. We also compare our results to those obtained using GCond [37] under the same settings. As shown in the Tab. 5, our approach achieves similar running time GCond when the condensing ratio was low (i.e., r = 0.05% for both datasets), and is 10% faster when the condensing ratio increased. The difference can be explained by the efficient generative model employed for generating structure, which prevents the consumption of time-complex operations such as calculating the pair-wised feature similarity (ON22).
single
Table 5: Runing time on Ogbn-arxiv and YelpChi for 50 epochs.
Dataset
r
GCond
SGDD
Dataset
r
GCond
SGDD
0.05%
315+1.8s
308+1.6s
0.05%
6742.6s
4742.8s
Ogbn-arxiv
0.25%
41342.6s
37443.2s
YelpChi
0.10%
96+2.8s
74+1.7s
0.50%
52742.7s
46742.1s
0.20%
110+0.8s
9342.6s
21

---

C Experimental Details and More Experiments
C.1 Dataset statisties
We evaluate the proposed SGDI) on nine datasets, including five node classification datasets:
Cora [41]. Citeseer [41], Oghn-arxiv [29], Flickr [100], and Reddit [26]; anomaly detection
datasets: YelpChi [68] and Amazon [102]; two link prediction datasets Citeseer-L [97] and DBLP [83].
We report the dataset statistics in Tab. 6.
Table 6: Dataset statics, including five node classification datasets, two anomaly detection datasets, and two link prediction datasets.
Datasets
# #Nodes
#Edges
#Classes
#Features
Cora [41]
2,708
5,429
7
1,433
Citeseer [41]
3,327
4,732
3,703
ND
Ogbn-arxiv [29]
169,343
1,166,243
40
128
Flickr [100]
89,250
899,756
500
Reddit [26]
232.965
57,307,946
210
602
YelpChi [68]
45,954
3,846,979
32
AD
Amazon [102]
11,944
4,398,392
2
25
Citeseer-L L [41]
3,327
4,732
2
3,703
LP
DBLP [83]
26,128
105,734
4,057
Citeseer-L: We use the Citeseer in the link prediction setting, named Citeseer-L. We randomly sample 80% nodes in training, 10% nodes validation, and the remaining 10% nodes for testing. The classes here denote "have edge" and "do not have edge".
DBLP: We treat the original graph as a homogeneous graph here.
C.2 Implementation details
Structure GDC. We utilize the DC [107] as our baseline, and to incorporate the structure information, add the constraint produce graph structure, named Graph DC (GDC). Specifically, we use the cosine similarity function [8] (formally, A = cos(X;, X X))) to generate structure, where X and X, are the learned features obtained through the vanilla gradient matching strategy.
GEN(-) in SGDD. introduce the GEN(-) as our generative model in Sec. 4.1. Here, we show implementation details of this module.
To start, we aim to find method broadcast the original graph structure to condensed graph A', Motivated by that all graphs with the same graphon W will exhibit similar properties, we can simply caleulate the graphon W of A and leverage it in the condensing process. Nevertheless, directly calculating W of A is not feasible since conventional graphon learning methods should summarize graphon from a set of graphs [21, 33, 64] (We only have one graph A). Recent advancements of IGNR [94] demonstrate the potential of utilizing the generative approach to approximate the W. Specifically, given that the graphon W defined as Ω + [0, 1] (as described in Appendix A. we can similarly construct the function f as follows.
(25) the continuous space 522 is defined by RR. For computational convenience, the input space can further be limited to [0, 1] [94], then the Eq. (25) is transformed to sample points to reconstruct data, following IGNR[94], we use SIREN[76] as S.
f f: + 10, 1].
hg PostionalEEncodinn((2 ((N")), h. Sin(W: (h; + b,), 1, .1-1,
(26)
h Sigmoid Baanoidd(Whij-- + bi).
where the 2(N') E RN is random noise that plays the coordinates, and the learnable weights O = (W; E Rlob++ b, E R for i = 1.... map the pair of points to the edge probability. GEN(Z 4) E R N''' equal to represent the adjacency matrix A' R N' X
22

---

after transformation, where each entry represents a probability that each node pair should be connected. To incorporate the node information into the structure generation. we adopt them as conditional information that leads the generation process. We can then rewrite Eq. (25) to:
R R
[0. 1],
(27)
where the R here is to present the conditional information, thus the learned model considers both the node's coordinates message along with the node's 's specific information. The basic implements can be:
h; MX @ Y') e Sin( W W, + b:), 1, ,
(28)
where the @ denotes the concatenate operation, the Y' is treated one-hot vector for dimensionality fit through a multilayer perceptron (MLP), This method allows for the incorporation of significant node information into the resulting synthetic graph.
Condensation stage. For GCond [37], we use the 2-layer SGC [92] serve as the condensing
architecture with 256 units, and tune the number of epochs in range of {400, 500, 6000, 1000, 2000). For GDC [107, 105], we tune the number of hidden layers in the range of (1, 2, 3) and the number of hidden units in the range of (128, 256). For SGDD, we use the GCN [40] as the default condensing architecture and tune the number hidden layers in a range of (1, 3]. We further tune the number of epochs in range (400, 500, 600, 1000, 2000), and tune the learning rate in range of {0.1, 0.01, 0.001, 0,0001).
Evaluation stage. We set the training epoch to 1000 with an early stopping strategy for evaluating GNNs and set the dropout rate to with the learning rate of 0.1.
Configurations. We conduct all experiments with:
Operating System: Ubuntu 20.04 LTS.
CPU: Intel(R) Xeon(R) Platinum 8358 CPU@2.60GHZ with 1TB DDR4 of Memory.
GPU: NVIDIA Tesla A100 SMX4 with 40GB of Memory.
Software: CUDA 10.1, Python 3., Py/oocc [65] 1.7.0.
C.3 Objective loss function and training algorithm
In this subsection, we present the objective function and provide detailed training algorithm. Our objective is to jointly learn X' and A'. We follow GCond[37] to optimize X' as free parameter using the gradient matching strategy[ [04], the loss can be expressed by Eq. (29),
(29) Here, Match(-) the matching function that measures the distance of the two gradients, we the MSE [37] in practice. 0 represents the parameters of the specific backbone GNN, the V denotes the gradient in the backpropagation process, and the Cets represents the loss function that used in the supervised tasks, i.e., cross cross-entropy loss. Our objective loss function can be written as:
Lreature Match V Cots (GNN Y)), VoCola (GNNo X'), Y').
C = feature + Letreuture + 3 ||A|||z 1l2
(30)
where the controls the contribution of the Latreuture term. To model the low-rank properties of real-world graphs, we use the ||A'|| as a regularity to control the sparsification of A' with B.
We summarize our pipeline in Algorithm. 1.
C.4 Stochastic Block Model experments setting
In Sec. 5.4, we generate a synthetic graph dataset with different community structures using the Stochastic Block Model (SBM) (N, C.p. g) [28]. Here, we show the parameters settings, we set the number of nodes N to 100, while setting the number of communities C' to 5. The parameter represents the edge probability within the same community and g represents the edge probability between communities, we set them to 0.8 and 0.1 in practice, respectively.
23

---

Algorithm 1: SGDD for Graph Condensation
Input: Training data G (A, X. Y). pre-defined condensed labels Y'
Initialize GEN as the structure learning model
Initialize X' by randomly selecet node feature from each class
for ......
Randomly initialize GNNs
for t = , T
do
D D
co 0, C do
Initialize 2(N')
Compute A' = GEN(Z(N") @ X' @ 4) then S [A',X', Y'
11
Sample (Ac, X,, Ye) ~ G and (A,, X Y.) ~ S
Compute Latructure
> detailed in Eq. (9) detailed in Eq. (29)
Compute Lreature
14
D' t D' + Lifattrre + aL aastructure + [|| A'112
15
if (T(T1 + T2) < T2 then
16
Update X + X' 1/1 D
else
Update
122 D opto (0,, TT
19
Update Dc+1
Dr Ta is the number of steps for updating 0
20 A' (EN(Z 1 D + Y
A, Ag A 0.5, otherwise
22
Return: (A', X', Y")
C,5 More explorations of the sensitivity of /3
In Fig. 4(d), we demonstrate that SGDD is not sensitive the coefficient on the YelpChi dataset. Here, we provide more experiments on the other datasets. In Fig. 6, we can see that increasing B leads to the more sparsity of the condensed graph, and the corresponding performance does not have severe drop. These observations demonstrate the effectiveness of the regularity term in our objective.
90
80
90
Spunity/ (C)))))) (%)
Sperstyy CC (2))
Sparsity/ACC ACC (%)
80
80
80-
70
40
Spunity
ACC
60
Fl-mecro Spunily
20
ACC
60
ACC
20
40
Sparstt
60
0
le le
0.1
1
10
50
6
0.1
le
12
0.1
10
20
le
0.1
10
B
B
B
Cora
(b) Citeseer
(c) Oghn-arxiv
(d) Amazon
90
ACC
Spassity
0.25
98.0
ACC
Spariity
0025
AUC
70
ACC (%6)
0.20
0.20
AUC Spazaity
Rllgga Spalisily
50
0.15
0.15
30
0.10
0.1000
0.05
0.05
10
0
0.1
B
(e) DBLP
(f) Plickr
(g)
Reddit
Figure 6: Evaluations of 3 in seven datasets. For the Flickr and Reddit datasets, due to the datasets' low sparsity, we use the shared x-axis form for the Flickr and Reddit figures.
24

---

Table 7: Comparison of the cross-architecture generalization performance between GCond and SGDD on YelpChi. Bold entries are the best results. 1/ our method show increase or decrease performance.
APPNP GCond SGDD
Cheby
GCN
SAGE
SGC GCond / SGDD
C/T
GCond SGDD
GCond SGDD
GCond SGDDD
APPNP
08.1/55.11
46.3/57.47
50.1/58.61
46.7 (7..1
49.6/ 57.6
Cheby
48.0 56.21
45.9/ 56.8
$5.9/56.8*
49.8/58.7
46.8 58.3*
49.8 / 58.4
GCN
47.6 56.5
46.6/ 56.8
48.6/ 59.7
47.4 57.6"
50.1 50.1/
SAGE
46.7/57..8
46.8 57.51
48.9/
48.6 58.6"
48.9 48.9/58.6
SGC
4 57.61
57.21
57.8/
47.4 59.07
48.7 57.6
C.6 More eross-architecturg experiments
In this subsection, we further report the results of cross-architecture experiments on the YelpChi. As shown in Tab. 7, our SGDD improves the performance all cases, the average improvements compared to the GCond [37] is 9.6%, which indicates the strong generalization performance of the condensed graph by SGDD,
C.7 Ablation of the sampling operation in OT distance
To further reduce condensing time and memory usage, we follow GCond [37] to sample from original graph A in the condensing stage (line 11 in the Algorithm 1). We evaluate the SGDD various sample sizes, Le., (100, 500, 1000, 2000, 5000), and report the corresponding performance and SC. As shown in Fig. 7, with the increase in the number of nodes, the performance obtains marginal improvements while the SC is decreasing. However, larger sample sizes are not always beneficial to performance. In this study, the highest results obtained when the sample size is 2000. This result empirically demonstrates the scalability of the structure learning module. Specifically, the module enables efficient condensing on large graphs.
67.50
67.75
ACC
SC
-0.55
0.50
62.0
marro
0.50
$2.5
AUC
n25
[Lmarco
045
67.00
0.40
0.35
0.20
66.50
0.30
$4.5
56.0
0.30
0.20
81.0
0.15
66,00
500
1000
2000
500d
53.0
100
500
1000
2000
5000
0.15
80.5
100
500
1000
2000
5000
0.10
Number of Nodes
Number Nodes
Number of Nodes
(a) Ogbn-arxiv
(b) YelpChi
(c) DBLP
Figure 7: Evaluation of the number of sampled nodes to the performance.
C.8 More discussion of the condensed graphs.
We next show the comparison condensed graphs and original graphs. As shown in Tab. 8, the condensed graphs obviously have fewer nodes and edges, while maintaining comparable accuracy, which shows the effectiveness our SGDD. We also represent the visualizations some condensed graphs. In Fig. 8, the black lines denote that edge weights represent as smaller than 0.5. We can observe that there are some patterns in the condensed graph, e.g., the homophily patterns Cora and Citeseer. However, for the remaining datasets, the visualizations are inadequate in revealing the properties of the condensed graph, which proves the superiority of analyzing structure in spectral view.
larger than 0.5 and the gray lines
C.9 More discussion of the large graphs.
We conduct experiments on the Ogbn-mag datasets and show the details as follows: (note we transform the original heterogeneous graph to the homogeneous by ignoring difference of
25

---

Table The comparison between condensed graphs and original graphs.
Citeseer, =0.9%
Cora, r=1.3%
Oghn-arxiv, r=0.5%
Flickr, r=0.1%
Reddit, r=
Whole
SGDD
Whole
SGDD
Whole
SGDD
Whole
SGDD
Whole
SGDD
Accuracy
70.7
69.5
81.5
79.6
71.4
65.3
47.1
47.1
94.1
90.5
#Nodes
3k3
60
2k7
169k
454
44
153k
153
#Edges
4k7
1k
5k4
1.166k
8k6
218k
331
10,753k
3k
(M)))
47.1
0.8
14.9
100.4
1.0
0.1
435.5
0.7
(a) Cora
(b) Citeseer
(c) Ogbn-arxiv
(d) Flickr
Figure 8: Visualizations of condensed graphs, the different colors on the graphs denote the classes.
26


Reviews:
[{"review_id": "rufCZeLuF8", "reviewer": "Reviewer_5ivm", "summary": "This paper proposes a new graph condensation framework called SGDD. The authors argue that existing methods overlook the structure information of the original graph during the condensation. And thus they propose to 1) use the Laplacian Energy Distribution (LED) shift to indicate the generalization performance of the condensed graph, and 2) minimize the LED shift (they claim it’s equivalent to the OT distance between the original and the condensed graphs) to preserve the structure information. Experiments on different datasets over node classification, anomaly detection and link prediction tasks show the effectiveness of the proposed method.", "questions": "Please see the above part.", "limitations": "None.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The motivation of preserving the structure information is clear and reasonable.\n- The experiments seem relatively sufficient and the results are good.", "weaknesses": "My major concern is the soundness of this paper:\n- Some claims seem to be problematic. For example, in line 176-179, the authors claim that ‘minimizing the LED shift is equivalent to minimizing the distance of Laplacian pseudo-inverse matrices [65]’ and ‘Following the previous work [78], minimizing such distance can be further approximated to optimizing a free parameter $P$ in Eq(6)’. However, the equivalence in [65] only applies to the objective using a specific GW distance and the approximation in [78] only applies to another OT distance based objective. So the two claims cannot hold simultaneously. What’s worse, the authors do not describe which OT distance is used in their original objective function. Then how could we conclude that ‘minimizing the upper bound of Eq. (7) is equal to optimizing the $L_{structure}$ on Eq. (5)’ in line 189?\n- The writing is not very easy to follow. The mixed use of ‘LED shift’, ‘LED shift coefficient’, ‘SC’ is very confusing (e.g., in Def2 and the caption of Fig2). And it’s not clear what’s the role of the proposed LED shift coefficient. This coefficient is neither used to derive the objective function, nor adopted as a performance metric in the tables for comparison.\n\n=============================\nPost-rebuttal: The author responses have basically solved my concerns about the soundness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the detailed comments and insightful questions. We make responses as follows.\n\n## **Q1:** The conflict of assumptions from the references [65] and [78].\n\n**A1:** Thanks for the comment. There are primarily two types of graph optimal transport distances: Gromov-Wasserstein (GW) and Graph Optimal Transport (GOT). We present the differences between them as follows.\n\n| Optimal Transports | Core Technologies | Famous Methods |\n| - | - | - |\n| GW | (1) GW is defined using a customized distance function that evaluates pairs of vertices in a graph [65]. (2) It quantifies the major alterations to the graph that significantly impact the distance function [A, B]. |FGW [65]、S-GWL[A]、SGW [B]|\n|GOT | (1) GOT is defined based on the graph signal [A]. (2) It primarily captures changes to the graph that significantly affect the eigenvectors of the Laplacian with small eigenvalues [78]. |FGOT [C]、COPT [78]、GOT [D]|\n\nFGW [65] belongs to the GW methods, while COPT [78] is a GOT-related method. Our proposed SGDD also relies on the graph signal $X$ of vertices and utilizes the Laplacian pseudo-inverse operation like [D], so our SGDD is a kind of GOT-related method. **After we checked our source code of Latex, there was a mistake in the reference GW-based method [65]. We update Line 175 to 177 as follows:** \n\n***Optimal transport distance.** To address the above issue, we utilize optimal transport (OT) [78, D] to efficiently optimize the shift of LEDs. Specifically, minimizing the LED shift is equivalent to minimizing the distance of Laplacian pseudo-inverse matrices[D].*\n\n**We will carefully check the content related to this issue in revision.** \n\n---\n\n[A] Hongteng Xu et. al. Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matching. NeurIPS 2019.\n\n[B] Titouan et. al. Sliced Gromove-Wasserstein. NeurIPS 2019.\n\n[C] Maretic et. al. FGOT: Graph Distances based on Filters and Optimal Transport. AAAI 2021.\n\n[D] Petric Maretic et. al. GOT: an optimal transport framework for graph comparison. NeurIPS 2019.\n\n## **Q2**: Why minimizing Eq. (7) is equal to optimizing the $L_{structure}$ on Eq. (5)?\n\nA2: Thanks for the question. First, considering the typically large different shapes between the original $\\mathrm{A}$ and the condensed $\\mathrm{A’}(N' \\ll N)$ (line 160), the $A’$ here is the “graphon” $W_{\\mathbf{A}}'$ with $N'$ nodes as an approximation to the oracle graphon $W_A$ [74], i.e., the abstract of the original graph. Thus Eq. (5) can be written as:\n\n$$ \\mathcal{L}_{\\textbf{structure}} = \\mathrm{Distance} (W_A', W_A).$$\n\nIn our settings, we replace the original graph $\\mathrm{A}$ with $W_{\\mathrm{A}}$ as $\\mathrm{A}$ is an actual observed value of $W_A$ with $N$ nodes[74, 75]. Second, in Appendix B.2, the upper bound of Eq. (7) is the cut distance of two graphons: \n\n$$ \\delta_{\\square}(W_{\\mathrm{A}}', {W_\\mathrm{A}}). $$\n\n**As the cut distance $\\delta_{\\square}$ here can be regarded as a specific $\\mathrm{Distance}$, the upper bound in Eq. (7) and** $L_{structure}$ in **Eq.(5) can be recognized equally.** \n\nWe will make it clear and check similar issues in the revision. Thanks again for the question.                                                                                                                                                                                                                                                                                                                                                                  \n\n## **Q3:** Mixed use of the concepts of LED shift, LED shift coefficient, and $SC$.\n\nA3: Thanks for the comment. Assume that we have two graphs, we introduce the definitions of LED, LED shift, LED shift coefficient, and SC as follows,\n\n**LED** is the distribution of the post-graph Fourier-transformed graph signal of the graph.\n\n**LED shift** is the phenomenon that denotes the differences between these two graphs’ LED.\n\n**LED shift coefficient** reflects the divergence between these two graphs. We provide the detailed formulation in Eq. 4 (lines 144 to 147).\n\n$SC$ represents an abbreviation of the LED Shift Coefficient. We claim it in line 143 and  Eq. 4.\n\nWe are sorry about the confusion and will make it clear in the revision.\n\n## **Q4**: Where the $SC$ be used.\n\nA4: Thanks for the question. \n\n1. As mentioned in lines 172 to 174, $SC$ requires the eigenvalue decomposition process, which is extremely time-consuming $O(N^3)$, particularly when dealing with large graphs. We show the estimated time cost per run of $SC$ as follows.\n\n|  | Cora, $r$=1.3% | Citeseer, $r$=0.9% | Reddit, $r$=0.1% | Flickr, $r$=0.1% | Ogbn-arxiv, $r$=0.5% |\n| - | - | - | - | - | - |\n| $SC$ (h) | 18.0 | 21.0 | 130.0 | 65.0 | 78.0 |\n| OT (h) | 0.8 | 0.9 | 2.1 | 1.1 | 1.8 |\n1. Since we aim at alleviating the LED shift, the GOT-related OT distance serves as an approximate indicator ($O(N^2K)$($K \\le N^{0.373}$)  [78]), which is more practical. As shown in the above table, OT is 61.9X faster than $SC$ on Reddit, 59.0X faster on Flickr, 43.3X faster on Ogbn-arxiv, 22.5X faster on Cora, and 23.3X faster on Citeseer, respectively.\n2. By leveraging the OT distance, we achieve consistent reduction on $SC$ (see Figure 1(b, e) and Figure 5(b, e)). We provide more results as follows.\n\nNote: we use the $\\downarrow$ to denote the reduction of $SC$ of SGDD to the GCond. \n\n| Methods | Ogbn-arxiv($r$=0.25%)  ($SC$/Acc.) | Reddit($r$=0.05%)  ($SC$/Acc.)) | YelpChi ($r$=0.10%) ($SC$/F1-macro) | Amazon($r$=0.2%) ($SC$/F1-macro) |\n| - | - | - | - | - |\n| GCond | 0.34/63.2 | 0.46/89.6 | 0.46/49.6 | 0.48/78.1 |\n| SGDD | 0.24/67.2 ↓29.4% |0.18/91.8 ↓51.1%|0.23/58.1 ↓50.0%|0.18/84.8 ↓62.5%|\n\nConclusion(s): \n\n- **The** $SC$ **metric serves as a good indicator for measuring the relationship between LED shift and generalization performance.**"}, {"review_id": "D2M6hQjUSa", "reviewer": "Reviewer_ZZ8V", "summary": "The paper investigates the effects of structural information in graph condensation methods. The authors claim that by maintaining the original structure during condensation using a newly formulated method called Structure-broadcasting Graph Dataset Distillation (SGDD), they are able to achieve more refined results on 9 data sets thereby significantly reducing Laplacian Energy Distribution (LED) shift. ", "questions": "I don't have question regarding this paper.", "limitations": "Need experiment for large datasets", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "This paper addresses an important question regarding the impact of structural information. The authors conduct a comprehensive analysis from the spectral domain and empirically identify significant shifts in Laplacian Energy Distribution (LED), which ultimately result in poor performance in cross-architecture generalization and specific tasks.\n\nThe proposed method demonstrates effectiveness in the experiments, and empirical analysis confirms the efficacy and necessity of the proposed designs.\n\nOverall, the presentation of the paper is also commendable", "weaknesses": "large datasets in the Open Graph Benchmark (OGB) is more effective in demonstrating the efficacy of these methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the insightful comment. We make responses as follows.\n\n**Q1:** Need experiment for large datasets.\n\nA1: Thanks for the reviewer’s suggestion. \n\n**Dataset Statics:**\n\n- As illustrated in the table below, there are four datasets that are significantly larger than Ogbn-arxiv.\n\n| Datasets | #Nodes | #Edges | #Classes | Metric |\n| --- | --- | --- | --- | --- |\n| Ogbn-arxiv | 169,343 | 1,166,243 | 40 | Accuracy |\n| Ogbn-mag | 1,939,743 | 21,111,007 | 349 | Accuracy |\n| Ogbn-proteins | 132,534 | 3,561,252 | 112 (Multi-label) | ROC-AUC |\n| Ogbn-products | 2,449,029 | 61,859,140 | 47 | Accuracy |\n| Ogbn-papers100M | 111,059,956 | 1,615,685,872 | 172 | Accuracy |\n\nWe conduct experiments on the Ogbn-mag datasets and show the details as follows. \n\n**Results on Ogbn-mag:**  \n\nNote: we report the results on SGDD and the other 3 baselines on 7 different condensation ratios ($r$). The accuracy on the whole dataset is 30.4 [A].\n\n| Condensation Ratio($r$) | Random | K-Center | GCond | SGDD |\n| --- | --- | --- | --- | --- |\n|  0.0001% | 0.9 | 5.7 | 15.3 | 18.1 |\n| 0.0002% | 1.1 | 6.8 | 15.4 | 18.3 |\n| 0.0003% | 1.1 | 6.9 | 15.4 | 18.4 |\n| 0.0004% | 1.4 | 7.1 | 15.3 | 18.7 |\n| 0.0005% | 1.5 | 6.4 | 15.4 | 18.7 |\n| 0.001% | 1.4 | 8.7 | 15.4 | 18.8 |\n| 0.002% | 1.5 | 10.4 | 15.1 | 18.8 |\n\nConclusion(s): \n\n- **On the large-scale dataset Ogbn-mag, our method achieves non-trivial improvements compared to other baselines.**\n\nDue to computational resource limitations, we are currently running experiments on additional datasets. We would like to provide it in the discussion period if the reviewer is interested.\n\n---\n\n[A] Hu et al. Open Graph Benchmark: Datasets for Machine Learning on Graphs. NeurIPS 2021."}, {"review_id": "SPwIWRfkL5", "reviewer": "Reviewer_9hTZ", "summary": "The paper proposes a novel approach for graph dataset distillation called Structure-broadcasting Graph Dataset Distillation (SGDD). The authors explicitly consider the impact of the original structure information on graph condensation and demonstrate that their approach achieves state-of-the-art results on 9 datasets, showing superior performance in cross-architecture settings and specific tasks. Overall, the paper presents a significant contribution to the field of graph dataset distillation.", "questions": "Questions: Please see weaknesses. I would like to update my evaluation after the discussion.\n", "limitations": "N.A.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper proposes a novel approach for graph dataset distillation that explicitly considers the impact of the original structure information on graph condensation. This is a significant departure from existing methods that primarily focus on optimizing the feature matrices of condensed graphs while overlooking the structure information.\n- The authors introduce the concept of Substantial Laplacian Energy Distribution (LED) shifts and demonstrate that previous works suffer from such shifts, leading to poor performance in cross-architecture generalization and specific tasks. The authors propose SGDD as a solution to this problem, which is a novel and original contribution.\n- The authors provide a thorough analysis of the proposed approach, including theoretical analysis and empirical evaluation on 9 datasets. The results demonstrate that SGDD consistently outperforms existing state-of-the-art methods, indicating the high quality of the proposed approach.\n", "weaknesses": "- [Actual Computation Savings] The authors distill the graph dataset. However, the authors only provide the distilled dataset's size ratio to original dataset size. It would be helpful to provide the actual computation savings in terms of time and memory usage.\n\n- [The Cost during Graph Distillation]  The cost of graph distillation for condensed small graph dataset is recommended to be provided. Since the used benchmark graph datasets are less computationally expensive than datasets in computer vision and natural language processing, the cost of graph distillation period will reflect whether the dataset is necessary for practical use.\n\n- [Comparison with Other Methods]  The paper provides a comparison of the proposed method with other methods in terms of performance and size ratio (e.g., Table 1). However, it would be beneficial to also compare the cost of graph distillation for the proposed method with other methods. This information would provide a more comprehensive understanding of the practicality of the proposed approach compared to other methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate reviewer 9hTZ’s constructive feedback and are glad that the reviewer finds our work novel. We answer the questions one by one as follows. Hope it can address the reviewer’s concern.\n\n### Q1: [Actual Computation Savings]\n\nA1: Thanks for the suggestion. We conduct the experiments on 5 datasets and show results as follows. \n\n**Storage Saving:** We present the basic statics of datasets and the storage saving in the following table.\n\n|  | Citeseer, |   $r$=0.9% | Cora,  |  $r$=1.3% | Ogbn-arxiv,  |  $r$=0.5% | Flickr,  | $r$=0.1% | Reddit,   | $r$=0.1% |\n| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |\n|  | Whole | SGDD | Whole | SGDD | Whole | SGDD | Whole | SGDD | Whole | SGDD |\n| Accuracy (%) | 70.7 | 69.5 | 81.5 | 79.6 | 71.4 | 65.3 | 47.1 | 47.1 | 93.9 | 90.5 |\n| #Nodes | 3,327 | 60 | 2,708 | 70 | 169,343 | 454 | 44,625 | 44 | 232,965 | 153 |\n| #Edges | 4,732 | 1,434 | 5,429 | 2,131 | 1,166,243 | 8,681 | 218,140 | 331 | 57,307,946 | 3,427 |\n| Storage (MB) | 47.1 | 0.8 **$\\downarrow$ 58.8X** | 14.9 | 0.4 **$\\downarrow$ 37.2X** | 100.4  | 1.0 **$\\downarrow$ 100.4X** | 86.8 | 0.1 **$\\downarrow$ 868X** | 435.5 | 0.7 **$\\downarrow$ 622X** |\n\nConclusion(s):  \n\n- **We achieved a storage saving of 868X in Flickr, 622X in Reddit, 100.4X in Ogbn-arxiv, 58.8X in Citeseer, and 37.2X in Cora, respectively.**\n\n**Computing Saving:** We calculate the computing saving in the following table. All results are obtained with the repetition of 5 runs (X denotes times).\n\n|  | Whole Training Time(min) | Condensed  Training Time(min) | Acceleration Rate | Whole  Training Memory (GB) | Condensed  Training Memory(GB) | Compression Rate |\n| --- | --- | --- | --- | --- | --- | --- |\n| Cora | 18.6 ± 2.1 | 0.4 ± 0.1 | **$\\downarrow$46.5X** | 3.2 ± 0.8 | 0.8 ± 0.1 | **$\\downarrow$4.0X** |\n| Citeseer | 32.7 ± 5.8 | 0.8 ± 0.2 | **$\\downarrow$40.8X** | 3.1 ± 0.6 | 0.8 ± 0.1 | **$\\downarrow$3.9X** |\n| Reddit | 56.8 ± 10.1 | 1.1 ± 0.1 | **$\\downarrow$51.6X** | 22.3 ± 1.5 | 1.4 ± 0.1 | **$\\downarrow$15.9X** |\n| Flickr | 23.4 ± 4.2 | 1.1 ± 0.3 | **$\\downarrow$23.0X** | 8.4 ± 0.8 | 1.1 ± 0.2 | **$\\downarrow$7.6X** |\n| Ogbn-arxiv | 48.7 ± 12.1 | 1.2 ± 0.3 | **$\\downarrow$40.5X** | 17.4 ± 1.8 | 1.2 ± 0.1 | **$\\downarrow$14.5X** |\n\nConclusion(s): \n\n- **Our method achieves a speedup of at least 23.0X and a compression ratio of at least 3.9X.**\n\n### Q2: [The Cost during Graph Distillation]\n\nA2: Thanks for the suggestion. We compared the costs of the graph distillation process and the costs of training on the whole graph. The results are shown in the following table.\n\nWe conduct experiments on 5 datasets and report the average computing time and memory. All experiments are repeated 5 times.\n\n|  | Whole Training Time(min) | Distillation Time(min) | Time Cost Rate | Whole  Training Memory (GB) | Distillation  Memory(GB) | Computing Cost Rate |\n| --- | --- | --- | --- | --- | --- | --- |\n| Cora | 18.6 ± 2.1 | 46.1 ± 4.8 | **$\\uparrow$2.4X** | 3.2 ± 0.8 | 3.8 ± 0.6 | **$\\uparrow$1.1X** |\n| Citeseer | 32.7 ± 5.8 | 53.8 ± 3.6 | **$\\uparrow$1.6X** | 3.1 ± 0.6 | 4.1 ± 0.7 | **$\\uparrow$1.3X** |\n| Reddit | 56.8 ± 10.1 | 120.8 ± 20.6 | **$\\uparrow$2.1X** | 22.3 ± 1.5 | 28.6 ± 1.6 | **$\\uparrow$1.3X** |\n| Flickr | 23.4 ± 4.2 | 67.3 ± 10.7 | **$\\uparrow$2.8X** | 8.4 ± 0.8 | 11.7 ± 0.4 | **$\\uparrow$1.4X** |\n| Ogbn-arxiv | 48.7 ± 12.1 | 140.3 ± 3.6 | **$\\uparrow$2.8X** | 17.4 ± 1.8 | 22.7 ± 0.7 | **$\\uparrow$1.3X** |\n\nConclusion(s): \n\n- **Despite the cost of our method being 1.6X-2.8X higher, considering the acceleration rate (23-51X) and compression rate (3.9-15.9X) when condensation is finished, it remains highly valuable.**\n\n### Q3: [Comparison with Other Methods]\n\nA3: Thanks for the suggestion. We compare our method SGDD and the other 6 baselines on three datasets (Ogbn-arxiv, Reddit, and Flickr), the average results (5 runs) are shown in the following table. \n\n- **Note:** We use the **Coarsening*** method as the base method to compare and calculate the time cost rate as well as the performance comparison.\n\n|  | Random | Herding | K-Center | Coarsening* | GDC | GCond | SGDD | Whole |\n| --- | --- | --- | --- | --- | --- | --- | --- | --- |\n| Avg. Time (min) | - | 10.2 ± 1.2 | 24 ± 1.2 | 61.7 ± 4.2 | 184.3 ± 10.4 | 160.2 ± 13.8 | 109.4 ± 10.2 | 42.7 ± 5.2 |\n| **Time Cost Rate** | - | **0.1X** | **0.3X** | **1.0X** | **3.0X** | **2.6X** | **1.7X** | - |\n| Avg. Computing (GB) | - | - | - | 7.4± 0.8 | 14.3 ± 1.2 | 14.8 ± 1.1 | 16.0 ± 1.4 | 11.5 ± 2.1 |\n| **Computing Cost Rate** | - | - | - | **1.0X** | **1.9X** | **2.0X** | **2.1X** | - |\n| Avg. Performance | 48.1 ± 2.1 | 54.6 ± 1.3 | 51 ± 0.7 | 56.6 ± 1.4 | 65.1 ± 0.8 | 66.6 ± 1.2 | 68.6 ± 0.7 | 73.1 ± 1.8 |\n| **Performance Comparison (%)** | **-8.5** | **-2.0** | **-5.6** | **0.0** | **+8.5** | **+10.0** | **+12.0** | - |\n\nConclusions: \n\n- **Compare with heuristic methods: Heuristic methods have lower costs but much worse performance (-8.5% to -2.0%), indicating their limitations in condensation tasks.**\n- **Compare with other condensation methods: SGDD only introduces a slightly higher computational cost than GDC and GCond (2.1X vs 1.9X and 2.0X), but achieves faster convergence (1.7X vs 2.6X and 3.0X), which can be attributed to the benefits of the better-learned structure. Meanwhile, SGDD achieves higher results faster than GDC and GCond.**\n\nWe hope the above response could address the concerns and would like to show more experiments in the discussion period if the reviewer is interested. "}, {"review_id": "yczCaisCrs", "reviewer": "Reviewer_UGAQ", "summary": "This paper proposes a novel method called SGDD for condensing large-scale graph datasets while preserving the original structure information. The proposed method uses a graphon approximation method to broadcast the original structure as supervision for generating the condensed graph structure and optimizes it using an optimal transport method. The proposed SGDD achieves state-of-the-art results on various datasets and tasks.", "questions": "(1) Please detailed the motivation in weakness.1 and weakness.2. \n(2) Consider adding the baseline mentioned in weakness (3) or specify the reason why do not compare with this method.\n(3) There is a high variance in the results of SGDD in Table 1. Would changing the backbone potentially improve the overall performance as shown in Table 1?\n", "limitations": "(1) In the real world, graphs may contain multiple types of edges, resulting in heterogeneity. However, the current learning methods may fail to capture this heterogeneity, leading to information loss.\n(2) Lack of discussion on different backbones.\n", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1) This paper uncovers the issue of Laplacian energy distribution shift during the condensation of graph datasets and shows that previous graph condensation methods that overlook the original structure information can lead to poor performance in cross-architecture generalization and specific tasks. This paper introduces a metric SC to quantify the Laplacian energy distribution issue.\n(2) A new condensing paradigm in graph condensation. This paper leverages the graphon theory to guarantee the structure information consistency between the original and generated graph, which firstly involves the generated learning fashion in graph condensation. Consequently, the generated structure may capture the native properties of the original structure in comparison to current methods, which benefits the downstream tasks.\n(3) Extensive experimental results demonstrate the effectiveness of the proposed method. This work includes extensive experiments on three node-level tasks as well as multiple ablation studies. All of the experiments demonstrate superior results. The most appealing result is that this method performs well in a cross-architecture setting, significantly improving the effectiveness of graph condensation. \n(4) Potential Impact. When the data and model go bigger and bigger, graph condensation may have more applications and research meanings. As the applications and challenges related to graph condensation remain unidentified, this paper may set the stage for future exploration of this problem and inspire the communities to further investigate and may benefit the areas like pruning, LLM with graphs, and NAS. \n", "weaknesses": "(1) The motivation for using JS divergence in the calculation of SC is unclear. There are serval ways of calculating the distance of two distributions.\n(2) In Figure.2, the author uses the BWGNN without specifying the difference between BWGNN and other backbones. \n(3) There is another related method called DosCond[1] which is mentioned in the introduction but not involved in the baselines. The reason why not choosing this method for comparison should be specified.\n[1] Jin, Wei, et al. “Condensing Graphs via One-Step Gradient Matching.” Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2022.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the detailed comments and insightful questions. We make responses to the reviewer’s comments as follows.\n\n## Q1: The motivation for using JS divergence in the calculation of $SC$ is unclear?\n\nA1: Thanks for the comment. We list three commonly used distances in the table below and compared their characteristics.\n\n| Distance Type | Characteristics |\n| - | - |\n| Wasserstein distance | Wasserstein distance is often used in the situation where the two distributions are non-overlapping |\n| Kullback-Leibler divergence (KL) | KL-divergence is asymmetrical and can’t satisfy the requirement in comparing |\n| Jensen-Shannon divergence (JS) | It offers an intuitive perspective on the similarity or dissimilarity of two distributions in terms of their shapes. |\n\nHere we list the results on two graphs $G_a$ and $G_b$ condensed from the four datasets ($G_o$). We report the different distance and the average accuracy of them.\n\nNote we use the $\\uparrow$, $\\downarrow$, and - to denote the improve, decrease, and no change respectively.\n\n|  | Cora, | $r$=2.6% | Citeseer, | $r$=1.8% | Flickr, | $r$=0.5% | Reddit, | $r$=0.05% |\n| - | - | - | - | - | - | - | - | - |\n|  | $G_a$ vs $G_o$ | $G_b$ vs $G_o$ | $G_a$ vs $G_o$ | $G_b$ vs $G_o$ | $G_a$ vs $G_o$ | $G_b$ vs $G_o$ | $G_a$ vs $G_o$ | $G_b$ vs $G_o$ |\n| KL | 0.15 | 0.15 - | 0.16 | 0.32$\\uparrow$ | 0.18 | 0.19$\\uparrow$ | 0.21 | 0.22$\\uparrow$ |\n| Wasserstein distance | 0.24 | 0.21 $\\downarrow$ | 0.14 | 0.18$\\uparrow$ | 0.26 | 0.17$\\downarrow$ | 0.32 | 0.18$\\downarrow$ |\n| JS | 0.11 | 0.24 $\\uparrow$ | 0.27 | 0.36$\\uparrow$ | 0.16 | 0.19$\\uparrow$ | 0.33 | 0.42$\\uparrow$ |\n| Avg. Acc. (%) | 74.1 | 68.2 $\\downarrow$ | 68.2 | 64.2$\\downarrow$ | 45.6 | 33.1$\\downarrow$ | 90.6 | 88.7$\\downarrow$ |\n\nConclusion(s): \n\n- **While KL divergence and Wasserstein distance could theoretically be used, we observe that their consistency was inferior to that of JS divergence in this specific case. As a result, we chose to utilize JS divergence in our experiments.**\n\n## Q2: The difference between BWGNN and other backbones?\n\nIn Figure.2, the author uses the BWGNN without specifying the difference between BWGNN and other backbones\n\nA2:  Thanks for the question.\n\n**Motivation:**  We select the BWGNN [63] in order to examine the impact of the frequency response of each backbone on the Laplacian energy distribution (LED) of the condensed graph, it is crucial to eliminate the influence of differences among the backbones themselves. Therefore, we choose the frequency-adaptive BWGNN.\n\n**Brief introduction to BWGNN:** the BWGNN mainly uses the Beta wavelet, which has the probability density function of Beta distribution admits:\n\n$$\n\\beta_{p, q}(w)= \\begin{cases}\\frac{1}{B(p+1, q+1)} w^p(1-w)^q, & \\text { if } w \\in[0,1] \\\\ 0, & \\text { otherwise }\\end{cases}\n$$\n\nWhere $p, q \\in \\mathbb{R}^{+}$ and $B(p+1, q+1) = p!q!/(p+q+1)!$ is a constant, the BWGNN adopt $B^*_{(p, q)} (w) = \\frac{1}{2}B_{p,q} (\\frac{w}{2})$ to cover the complete spectral range of $L$. Thus we can use a different parameter setting to change the frequency response of BWGNN (see 3.2 Beta Wavelet on Graph on [63]).\n\n**Difference to other backbones:** Following  [1], we list the difference between BWGNN and the other backbones as follows.\n\n| Backbones | Low-pass support | high-pass support | Controllable spectral range |\n| - | - | - | - |\n| SGC | $\\checkmark$ | $\\times$ | $\\times$ |\n| GCN | $\\checkmark$ | $\\times$ | $\\times$ |\n| ChebNet | $\\checkmark$ | $\\checkmark$ | $\\times$ |\n| GAT | $\\checkmark$ | $\\checkmark$ | $\\times$ |\n| BWGNN | $\\checkmark$ | $\\checkmark$ | $\\checkmark$ |\n\nConclusion(s):\n\n-  **Compared to other backbones, BWGNN not only provides support for all-pass filtering but also offers controllability, which is convenient for applying it to 9 datasets.**  \n\n## Q3: The experiment results about DosCond?\n\nA3: Thanks for the suggestion. We conduct experiments on node classification and anomaly detection tasks on DosCond [29] and show the results in the following table.\n\n- **Note:** We use $\\Delta$ to indicate the performance improvement from method DosCond to SGDD.\n\n|  | Citeseer($r$=1.8%) | Cora($r$=2.6%) | Ogbn-arxiv($r$=0.25%) | Flickr($r$=0.5%) | Reddit($r$=0.1%) | YelpChi($r$=0.1%) | Amazon($r$=0.2%) |\n| - | - | - | - | - | - | - | - |\n| Whole Dataset | 71.7±0.1 | 81.2±0.2 | 71.4±0.1 | 47.2±0.1 | 93.9±0.0 | 61.1±1.8 | 89.5±0.9 |\n| DosCond [3] | 69.8±1.8 | 79.4±1.1 | 58.8±1.3 | 46.3±0.4 | 88.6±0.5 | 47.6±0.3 | 77.4±0.8 |\n| SGDD | 70.3±0.8 | 80.6±0.8 | 67.2±2.8 | 47.1±0.3 | 91.8±1.9 | 58.1±2.3 | 84.8±1.7 |\n| $\\Delta$(%) | 0.5 $\\uparrow$ | 1.2 $\\uparrow$ | 8.4$\\uparrow$ | 0.8$\\uparrow$ | 3.2$\\uparrow$ | 10.5$\\uparrow$ | 7.3$\\uparrow$ |\n\nConclusion(s): \n\n- **Our method SGDD demonstrates superior performance compared to DosCond, particularly on the YelpChi and Amazon datasets.**\n\n## Q4: Would changing the backbone potentially improve the overall performance?\n\nA4: Thanks for the question. We conduct the experiments on three datasets: Reddit, Ogbn-arxiv, and Flickr with 6 different backbones. \n\n- **Note:** We use the $\\uparrow$ and $\\downarrow$ to indicate the increase and the decrease to the default GCN respectively.\n\n| Acc. (%) | GCN | APPNP | Cheby | SAGE | SGC | GAT |\n| - | - | - | - | - | - | - |\n| Reddit, $r$=0.05% | 91.8 | 91.4/0.4$\\downarrow$ | 92.1/0.3$\\uparrow$ | 90.6/1.2$\\downarrow$ | 91.9/0.1$\\uparrow$ | 92.0/0.2$\\uparrow$ |\n| Ogbn-arxiv, $r$=0.25% | 67.2 | 66.4/0.8$\\downarrow$  | 66.8/0.4$\\downarrow$ | 66.5/0.7$\\downarrow$ | 66.4/0.8$\\downarrow$ | 66.4/0.8$\\downarrow$ |\n| Flickr, $r$=0.50% | 47.1 | 47.2/0.1$\\uparrow$  | 46.2/0.9$\\downarrow$ | 46.8/0.3$\\downarrow$ | 47.0/0.1$\\downarrow$ | 47.2/0.1$\\uparrow$ |\n\nConclusion(s): \n\n- **The range of upward and downward performance is not particularly large in our case, as it falls within a specific range between -0.8 and 0.3.**"}, {"review_id": "hDzPOLqdhP", "reviewer": "Reviewer_FmUF", "summary": "This paper mainly focuses on the Laplacian Energy Distribution (LED) shift problem of graph dataset condensation.", "questions": "see above.", "limitations": "see above.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The pipeline figure is clear and straightforward.\n\nThe studied problem, how to condense a graph dataset, is relatively important.\n", "weaknesses": "Compared to existing studies that widely investigated the gradient matching, it seems that the major contribution of this paper is considering the LED shift. Why LED and how can LED benefit? The authors need to provide more analyses and explanation about their motivation. \n\nIn the Introduction, the authors mention “We empirically find a positive correlation between LED shift and the performance in cross-architecture settings”. This can only be considered as a finding. The motivation for introducing LED is ambiguous, especially given the correlation does not mean causality. \n\nThe authors simply compare their method  with Gcond and consider it as the SOTA. However, there are many works that have been proposed since Gcond. The authors should consider compare with them as well for a comprehensive evaluation of their method. For example, [1, 2, 3, 4, 5]\n\n[1] Jin, Wei, et al. \"Condensing graphs via one-step gradient matching.\" Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2022.\n\n[2] Yu, Ruonan, Songhua Liu, and Xinchao Wang. \"Dataset distillation: A comprehensive review.\" arXiv preprint arXiv:2301.07014 (2023).\n\n[3] Liu, Chuang, et al. \"Comprehensive graph gradual pruning for sparse training in graph neural networks.\" IEEE Transactions on Neural Networks and Learning Systems (2023).\n\n[4] Zheng, Xin, et al. \"Structure-free Graph Condensation: From Large-scale Graphs to Condensed Graph-free Data.\" arXiv preprint arXiv:2306.02664 (2023).\n\n[5] Yang, Shuo, et al. \"Dataset pruning: Reducing training data by examining generalization influence.\" arXiv preprint arXiv:2205.09329 (2022).\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the instructive questions. We make responses to the reviewer’s comments as follows.\n\n## Q1: More analyses and explanations of motivation?\n\nA1:  Thanks for the question, we show the storyline of our paper as follows.\n\n- The core question in our paper is: “Does graph distillation see like vision dataset counterpart?“. Previous works follow the vision dataset distillation methods, which may lead to the following limitations: 1) the original graph structure information is not well preserved after condensing (see Fig. 1(b)); 2) In vision dataset distillation, gradient matching may entangle the synthetic dataset and architecture[86], which may be compounded on graph data (lines 43-54). \n- Then how to broadcast the original structure information into the condensed graph? In graph spectral theory [63, 1, 10, 62], the LED shift serves as a metric for measuring the differences between two graph structures. However, due to the significant size difference between the original and condensed graphs, directly calculating the LED shift is impractical. Inspired by the [63, 1], we analyze the LED shift between two graphs in the spectral view. We introduce the LED Shift Coefficient ($SC$) as a measure of shifts and empirically validate its consistency with performance. As optimizing $SC$ incurs substantial costs (see our response to Q4 of reviewer 5ivm), we further employ the Optimal Transport distance to approximate $SC$ during optimization. A detailed analysis is provided in lines 172 to 181.\n- Our SGDD approach achieves state-of-the-art results on 9 datasets. For example, in the YelpChi, we maintain 98.6% test accuracy while reducing the graph scale by 1,000 times.\n- Compared to previous methods, $SC$ is significantly reduced by SGDD. For example,  29.4% reduction on Reddit, 50.0% on YelpChi, 60.8% on Reddit, and 62.5% on Amazon (see Fig. 1(b, e), Fig. 5(b, e), and the response to Q4 of reviewer 5ivm).\n\nIn summary:\n\n1. The capability of the LED to convert the graph structure into a frequency domain distribution is essential for calculating the structure distance, particularly in cases where there is a substantial size difference.\n2. Following the discussion on [63, 1, 10, 62], the LED is closely associated with the generalization performance of GNNs, providing valuable insights into the role of graph structure in the condensation process.\n\n**The correlation does not mean causality:** Thanks for the question. The correlation inspires us to design the SGDD method, which effectively broadcast the structural information from the original graph dataset to a condensed version. Our SGDD achieves SOTA in most cases, including new SOTA results on YelpChi and Amazon with improvements of 9.6% and 7.7%, respectively. \n\nEmpirical results support the consistency between LED shift and generalization performance (see Fig. 1(b, e), Fig. 5(b, e), and response to Q4 of reviewer 5ivm). Compared to previous methods, our SGDD significantly improves performance while reducing $SC$.\n\n---\n\n## Q2: Considering compare with more baselines?\n\nA2: Thanks for the advice. We conduct experiments on 5 additional baselines. \n\nWe first clarify that (1) the **public date (5 Jun) of SFGC [4] is behind the deadline for NeurIPS submission (17 May).** Nevertheless,  we would like to compare them in the revision. (2) the literature [2] is a survey on the computer vision area, we choose the representative method MTT [A] to compare with.\n\n- Note and details:\n    - We calculate the average performance of each method and use the $\\Delta$ to indicate the relative difference of the SGDD to the other method.\n    - Since CGP [3] has no public code, we reproduce it in the evaluation.\n    - The Dataset Pruning [5] requires a solver in linear programming, we use the CPLEX [B] as the backend optimizer.\n\nWe highlight the best-performing entries in **bold** and indicate the $\\underline{\\text{runner-ups}}$ with underlined values.\n\n|  | Citeseer($r$=1.8%) | Cora($r$=2.6%) | Ogbn-arxiv($r$=0.25%) | Flickr($r$=0.5%) | Reddit($r$=0.1%) | YelpChi($r$=0.1%) | Amazon($r$=0.2%) | Avg.  / $\\Delta$ (%) |\n| --- | --- | --- | --- | --- | --- | --- | --- | --- |\n| Whole Dataset | 71.7±0.1 | 81.2±0.2 | 71.4±0.1 | 47.2±0.1 | 93.9±0.0 | 61.1±1.8 | 89.5±0.9 | 73.7 / - |\n| MTT [2, A] | 68.4±0.8 | 78.3±0.8 | 59.9±0.6 | 44.8±0.8 | 86.7±0.1 | 44.1±0.8 | 76.7±1.1 | 65.5 / **-5.8** |\n| CGP [3] | 67.4±1.3 | 77.6±0.8 | 61.1±0.7 | 45.4±0.4 | 86.6±1.8 | 49.6±0.2 | 77.4±1.8 | 66.4 / **-4.9** |\n| Dataset Pruning [5] | 66.8±1.8 | 74.6±1.9 | More than 3 days | More than 3 days | More than 3 days | 46.8±1.1 | 68.6±0.4 | 64.2 / - |\n| DosCond [1] | 69.8±0.3 | 79.4±0.7 | 58.8±1.1 | 46.3±0.4 | 88.6±0.5 | 47.6±0.3 | 77.4±0.8 | 66.8 / **-4.5** |\n| SFGC [4] | **72.4±0.4** | **81.7±0.5** | $\\underline{66.1±0.4}$ | $\\underline{47.0±0.1}$ | $\\underline{90.0±0.3}$ | $\\underline{44.7±0.1}$ | $\\underline{77.5±0.7}$ | 68.4 / **-2.9** |\n| SGDD | $\\underline{70.3±0.8}$ | $\\underline{80.6±0.8}$ | **67.2±2.8** | **47.1±0.3** | **91.8±1.9** | **58.1±2.3** | **84.8±1.7** | 71.4 |\n\nConclusions:\n\n- **Compared to Dataset Condensation methods [2, 1, 4], our method demonstrates an average improvement across all datasets. Notably, SGDD exhibits higher improvements on large datasets, highlighting the importance of broadcasting the structural information in condensing larger datasets.**\n- **Compared to dataset pruning methods [3, 5], the linear programming-based approach [5] fails in efficiency, and the mask-based method [3] may hinder condensed graph connectivity, resulting in poor performance.**\n\nDue to the limited time, we primarily focus on the node classification and anomaly detection tasks, we would like to show more experiments if the reviewer is interested.\n\n---\n\n[A] George Cazenavett. et al. \"Dataset Distillation by Matching Training Trajectories.\" CVPR  2022.\n\n[B] Cplex, I. I. User’s Manual for CPLEX. *International Business Machines Corporation*, 2009."}]

Author rebuttal:

Meta-review: This paper focuses on graph distillation and presents a structure-braodcasting strategy. Extensive experiments demonstrate its superiority. After the response, it receives mixed ratings, including three positive scores and two borderline reject. The main concerns lie in the inadequate comparison and insufficient experimental support for the cost. The authors provide detailed responses to these disadvantages. Overall, I think the improvement over recent methods is acceptable. I vote for its acceptance. Please incorporate these results in the camera-ready version.
Decision: Accept (poster)