Multi-resolution Spectral Coherence for Graph Generation with Score-based Diffusion
Authors: Hyuna Cho
Minjae Jeong
Sooyeon Jeon
Sungsoo Ahn
Won Hwa Kim
Venue: NeurIPS 2023 poster (2023)
Keywords: graph wavelet transform
multi-scale wavelet filtering
graph generation
diffusion model

Abstract: Successful graph generation depends on the accurate estimation of the joint distribution of graph components such as nodes and edges from training data. While recent deep neural networks have demonstrated sampling of realistic graphs together with diffusion models, however, they still suffer from oversmoothing problems which are inherited from conventional graph convolution and thus high-frequency characteristics of nodes and edges become intractable. To overcome such issues and generate graphs with high fidelity, this paper introduces a novel approach that captures the dependency between nodes and edges at multiple resolutions in the spectral space. By modeling the joint distribution of node and edge signals in a shared graph wavelet space, together with a score-based diffusion model, we propose a Wavelet Graph Diffusion Model (Wave-GD) which lets us sample synthetic graphs with real-like frequency characteristics of nodes and edges. Experimental results on four representative benchmark datasets validate the superiority of the Wave-GD over existing approaches, highlighting its potential for a wide range of applications that involve graph data.

Multi-resolution Spectral Coherence for Graph Generation with Score-based Diffusion
Hyuna Cho Minjae Jeong
Sooyeon Jeon Sungsoo Ahn POSTECH, South Korea
Won Hwa Kim
Chyunacho, minjaetidtid, jsuyeon, sungsoo. ahn, wonhwa) ac.
Abstract
Successful graph generation depends the accurate estimation of the joint distribu- tion of graph components such as nodes and edges from training data. While recent deep neural networks have demonstrated sampling of realistic graphs together with diffusion models, however, they still suffer from oversmoothing problems which inherited from conventional graph convolution and thus high-frequency characteristics of nodes and edges become intractable. To overcome such issues and generate graphs with high fidelity, this paper introduces a novel approach that captures the dependency between nodes and edges at multiple resolutions in the spectral space. By modeling the joint distribution of node and edge signals in a shared graph wavelet space, together with score-based diffusion model, we pro- pose a Wavelet Graph Diffusion Model (Wave-GD) which lets us sample synthetic graphs with real-like frequency characteristics of nodes and edges. Experimental results on four representative benchmark datasets validate the superiority the Wave-GD over existing approaches, highlighting its potential for wide range of applications that involve graph data.
1 Introduction
The flexible representation of graphs lets us investigate a variety of real-world phenomena such as social networks [8,39], traffic flows [43, 45], molecule structure [18, 19,34,44), and brain networks [2, 28). The rich expressive power of graphs inherits from embodying various combinations of nodes and edges within an irregular structure. However, the analysis of graph data is challenging due to the arbitrary and heterogeneous structure, as it becomes difficult to characterize robust patterns both within graph and across different graphs for downstream machine learning task.
The same issue arises in graph generation, where the objective is learn the underlying graph distribution from training samples and thereby synthetic graphs with similar characteristics to the training data can be generated, i.e., sampled. For this, accurately estimating the joint distribution of the measurements from node features and graph structures is essential. Recent graph generative methods [13,35, 35,3] have been successful in sampling realistic node and edge features, however, their generated samples often fail to embed the true relationships especially given in sparse connections between nodes. This problem often occurs as existing methods derive separate embeddings of nodes and edges considering them different entities [37]. Moreover, successive layers of graph convolution (13,35] aggravate this issue by overly averaging signals on graphs, such that local details (i.e., higg-frey characteristics) become intractable.
Key ideas. Notice that the edge signals, e.g., edge weights and connectivity, should coherent to node signals as the edges should properly explain the relationships between the nodes. Based on this homophily assumption, to address the aforementioned issues, we propose a novel generative model that precisely captures the dependency between nodes and edges in multiple resolutions -olobal structures. This is realized via spectral graph wavelet transform (SGWT) [9], which
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

14.3
0,9
23.9
-2.0
-9.5/
1.1
0.9
-0.2
14.3
0.9
-9.5
-0.2
(a)
(b)
(c)
(d)
(e)
(f)
Figure 1: An example of SGWT with diverse scales that impacts the graph representation. (a) An undirected
graph with adjacency matrix A. (b) Disconnectivity between nodes with dashed lines for A. (c) Result from graph transform A with a band pass kernel k(s) = saze
scale # = and (d) corresponding disconnectivity to (c). (e) Result from graph transform of using the same band-pass kernel at s = 0.1. (1) Corresponding disconnectivity for (c). The edge thickness denotes the magnitude of connectivity, which is controlled by a scale parameter. Compared to A, the sparse connection (orange) is significantly strengthened via SGWT s and disconnectivities (blue) are also emphasized the same scale.
band-pass
enables the filtering of graph signals specific level of granularity. We transform the node and edge signals into a common graph wavelet space and obtain their underlying rrosscharacteristtis. Le., spectral coherence, via their inner product at different scales. We expect that sparse connections between nodes (i.e., higher variation) can be captured with high fidelity as high-frequency components in the spectral space. Fig. shows example of such effect with wavelet transforms on edges, which accentuates certain connectivity and disconnectivity over a template graph. These accentuated (dis-)oc cisneccinntsssssis specifie scales be characterized by generative model with multiresolution wavelet filtering. Also, we further show that the scale-specific node and edge features computed in the spectral space be easily and jointly obtained in spatial graph convolutional form by applying wavelet filtering to either nodes or edges for efficiency.
Proposed F Framework. We leverage this spectral coherence to model the joint distribution of graph node and edge features embedded in a common graph wavelet space with a score-based diffusion model [36]. As opposed to conventional approaches [13] where the scores for the joint distribution of nodes and edges are modeled with graph multi-heas attention (GMH) [1] involving graph convolutions of the raw node and edge signals, model calculates the scores over multiple scales of nodes and edges to capture different frequency characteristics. With diffusion and reverse denoising processes in multi-resolution, distribution of the node and edge features preserving their graph frequency characteristics.
Wavelet Graph Diffusion Model (Wave-GD) accurately estimates the joint
Contributions. To this end, we summarize main contributions as follows: 1) To obtain representa- tive graph characteristics different fidelity, we propose a novel concept to capture spectral coherence between nodes and edges in multiple scales in common graph wavelet space. 2) Furthermore, show that spectral coherence can be obtained in the graph domain as spatial graph convolutional formulation, which allows to perform the SGWT only the edge signals for efficiency. 3) We propose a training scheme on the multi-resolution at which the optimal joint frequency characteristics of graph nodes and edges can be captured from training samples. The Wave-GD was tested on four representative benchmarks for graph generation which demonstrated outperforming results over state-of-the-art baselines. Extensive experiments on real-world, synthetic, and biochemical graph datasets validate the generality of the method, suggesting its potential for diverse applications with graph samples.
2 Related Work
Deep graph generative models aim learn the underlying distribution of node and edge signals from the training set. They can be categorized into (I) autoregressive models that construct graphs by the iterative generation of node or an edge signal at each step or (2) one-shot models that simultancously update all the signals once.
Autoregressive models. Autoregressive models are widely used for graph generation since they are based on straightforward way to iteratively update the graph structure conditioned on an incomplete graph generated so far. Prior works have parameterized the autoregressive models using recurrent neural network (RNN) [29,4] (9,,11,42,, variational autoencoder (VAE) [11, 12], and normalizing flow [20, 34). However, they suffer from high complexity since the required number of updates to generate the graph grows with the size of the graph. Furthermore, their generation is sensitive to the order of nodes being generated, i.e., autoregressive models may assign different probabilities for the construction of the same graph executed in a different way.

---

One-shot models. One-shot models alleviate the issues of autoregressive models by simultaneous generation of node and edge signals. This potentially reduces the complexity of generation since the number of generation steps no longer depends on the graph size. Furthermore, their generation is often permutation invariant and assigns the same probability for generating a graph regardless of the permutation. Researchers have considered parameterizing these models using generative adversarial network (GAN) [4], VAE [21], normalizing flow models [23, 44], and diffusion models [13.25, 37].
Diffusion models. In particular, diffusion models are recently catching attention due to their extraordinary capability in learning the joint distributions of graph components such as nodes and edges. They are based on (1) defining a forward diffusion process to sequentially corrupt graph using noise distributions and (2) training a reverse diffusion process parameterized by a graph neural network to reconstruct the original graph. Existing works mainly differ by defining the diffusion processes in the continuous space [13] or the discrete space [10, 25,37].
3 Generating Graphs with Robust Spectral Characteristics
3.1 Preliminary: Graph Wavelet Transform
be an undirected graph, where X E RXF represents F-dimensional node features for N nodes and A RNNN is adjacency matrix representing connectivity among the nodes. The graph Laplacian is defined as L = D A, where D is a diagonal degree matrix. As the L is real and positive semi-definite, it has a of orthonormal eigenvectors U [u1, 122, ux] and corresponding non-negative real eigenvalues A = diag(A),.... .x)) Decomposing this Laplacian as == UAU the connectivity, complexity, and spectral properties of the graph are characterized. Specifically. its eigenvectors and eigenvalues identify the frequencies and mode of vibrations of graph. Eigenvectors with small eigenvalues represent large connected components in a graph structure and slow-varying signals among nodes. On the other hand, eigenvectors associated with large eigenvalues indicate the sparse and disconnected signals in the graph [22, 22,,2,,44),
Let G== = (X,
To capture localized characteristics of signals on arbitrary graph structures, the spectral graph wavelet transform [9] is defined by constructing a set of graph wavelet bases v.- (tha) 1222 "....... Vay) with J scales where vi. Uk(sA)U* The th is a realization of kernel function k(-)) in the spectral domain localized with on in the graph space, which captures the local characteristics of the graph at each node. The scale selects specific bandwidth in the spectral space which corresponds to the range of locality in the original graph space. The choice of wavelet basis. i.c., mother wavelet, depends on the shape of k(-). which may vary depending on a target task such as smoothing or band-pass filtering. In this work, we used both types of kernel functions: (I) a band-pac hand-pass kernel k(s) sre sz
to capture both low and high frequency of graphs and (2) a low-pass kernel Rc(s) = e -2 to capture cluster-like and smoothed features from graphs.
Using the bases v.s graph wavelet transform projects a signal x (e.g., node feature or connectivity) from the graph domain into the spectral domain as
W =< V.. >= 1h,2
(I)
which yields wavelet coefficient (s).. This wavelet coefficient is a scale-filtered signal defined in the wavelet space. When admissibility condition on k(-) is satisfied [24], the inverse transform completely reconstructs the signal æ by projecting Wa (s))s) back to the graph domain as follows:
1
ds vb (s)
x = Ch J
with an admissibility constant C = S 1(x))2 dx < oc.
3.2 Adaptive Multi-Resolutiin Representation of Nodes and Edges
To capture both fine and coarse graph features from an irregular graph structure, the filtering operation performed over multiple scales. The multi-resolution representations of graph nodes and edges are derived by decomposing the graph signals X and A with scales { using (I), which result in (Wx (W+()) [s and (WA (s:)); } in the spectral domain. These are wavelet coefficients that contain different levels of local and global details of graph node and edge signals in multi-resolution fashion.
To obtain the multi-resolution representations of these graph signals in the graph space, the inverse transform in the Eq. 2 is performed on the filtered coefficients using the bases vh at the same scales.
3

---

XT
AT
A7
A
X
X
1x,1ogpi(X..4)
14
11
Forward SDD
Reverse SDE
A
14
1t
tt
X1
A1
A1
A
shared
14
14
14
Age
aa (X.
X
Ao
A
Forward SDE
Node Peatures
Adjacency Matrix
Scale Bitered Adj. Matris
Ao. >=
(s(s)
Inverse
Aù
Graph
Transform
(a)
Diffusion
process
(b) Overview of the model architecture.
scheme of Wave-GD.
Figure 2: (a) Schematic diagram of Wave-GD with rustiiressoution diffusion. Note that the scale-filtering is applied to the Ag. not to the A₁. (b) Overview of Wave-GD that jointly estimates partial scores of node features X and edges A along with scale-filtered edges A". We first perform multi-resolution filtering on the given edges Ao
0 using graph wavelet basis vhs with trainable scale s. Forward diffusion processes smoothly transform X, A, and A' into noises parallel they are reconstructed by solving reverse-timg time SDEs. During the reconstruction, the knowledge across multi resolution is shared in the score- based model Ag,t. Also, the information in separate edge and node components is effectively entangled by obtaining their spectral coherence various resolutions.
As the Eq. 2 is the superposition of multi-resolution representation of over scales at [0, 00), it allows us define a scale-filteeed signal the graph space at specific & as
= v. (s) UK?(sA)U*>
where k.2 (sA) = ( (s{x))) is diagonal matrix [2]. Therefore, the X and A multiple resolutions the spatial domain are defined as {X*) (*A*(s and {A*) J. ? AJUT A respectively. Within proposed framework, make these scales trainable such that the local-to-globa -lobal characteristics can be obtained adaptively.
3.3 Refining Spectral Coherence between Nodes and Edges in Multi-resolution Fashion
As the graph features X and A should be coherent, i.e., connectivities should explain the relationship among features from different nodes, we hypothesize that they should share similarities even when observed from different resolutions. To capture the key components that are shared both edges and nodes at multi-resolution, we measure the underlying cross-characteristies between nodes and edges in each scale in the spectral space. We quantify their coherence and use this spectral coherence as a feature that represents a graph at a specific resolution 8, which is used estimate the score function in multiple resolutions later in Section 3.5.
dot product WA (s) Wx(s)
Lemma 1. Let G be undirected graph, with node signal X and symmetric adjacency matrix A. Given wavelet coefficients WA (s) and Wx (8), which are spectral representations of X and A at specific scale dot product of these wavelet coefficients is equivalent to the product between the scale-filtered edge signals and the node signals in the graph space, i.e., WA(s) (x(s) = A
By Lemma we can efficiently extract multi-resolution coherence by applying the filtering only on the edges. Using the J number of A along with the given data G = (),X), we introduce our simple yet effective graph generative framework through the stochastic differential equations (SDEs) in Sec. 3.4 and explain how Lemma is used in the generative model in Sec. 3.5. The proof of Lemma given Appendix
3.4 Wave-GD: Wavelet Graph Diffusion Model via Multi-resolution
Now we describe our graph generative model which captures the dependency of node and edge on both local and global structures with adaptive spectral filtering. The overall description Wave-GD is given in Fig. 2, which demonstrates (a) multi-resolution diffusion strategy and (b) overall model architecture. particular, we enhance the existing diffusion models for graphs [13] using the spectral coherence introduced in Lemma 1. The building blocks of model are follows: 1) the forward

---

diffusion to corrupt the graph distribution in a continuous domain, 2) the reverse diffusion to recover the original graph, and 3) the training objective for our model.
Multi-resolution forward diffusion process. Building upon the work of GDSS [13], we propose diffusion process that sequentially corrupts graph structure different levels of resolution based on the Itō SDE [32]. As the forward diffusion process is modeled by SDE which describes a process of random variables, (X,, {A follows:
}o=ob with A," A at timestep [o, 2'] are diffused as
dX,- = fx t)dt + ddW.
(4)
dA fA.: (Aj), t)dt oA:, (dW,
where fx RXF NxF and fA N NNN are drift functions, dx,t and A are scalar diffusion coefficients, and wx and WA are standard Wiener processes for X, and (/ respectively. As this diffusion process is simulated at varying levels of granularity in a multi-resolution scheme, it is likely that certain frequency characteristics are accentuated and the highlighted information will be preserved from corruption. In other words, at an arbitrary timestep I, the scale-filtered edges {A{ J;=1 are highly likely to contain richer information of edges for score estimation than the given A, as their edge signals are adaptively controlled and highlighted by trainable scales.
Learning the reverse diffusion process. Let G. Ax) be a given graph at timestep t and {G = Af ) be set of graphs for multiple scales at the same timestep. Given the multi- resolution forward diffusion process, we generate graphs from solving the associated SDE backward in time. To be specific, the reverse diffusion process can be formulated as follows:
dX, = fx (X,,) t) x Vx, log Pi (Gt) + xx,xdxx
d = [CA (A - i V A. log (G, ]dl + aAA,,dWA'.
where Pc() and Pt (G denote the distribution of the forward diffusion process evaluated at time f. This reverse-time SDE recovers the original data distribution po (Xo, (A W with the standard reverse-time Wiener processes wx and WAs in which the direction of time is reversed as df.
However, since the score functions of the joint distribution, i.e., Vx, log Pr and V VA, log Pc ), are unknown, we train a neural network to estimate them using the denoising score matching loss [38]:
Lx min E. (xx()))aa.c,cccllleee. Vx, (X.
(6)
0
LA = min Eg
(t) Ea, Bc.. - VA, log Po: (A Ao)
0.5
+AA+ (t) > Bay o (IAA).( - V A. log (A, A |1
where (-)(-) denotes the transition distribution from po to Pt. No are graph neural networks trained to approximate the true score functions. The Ax (t), (t AA (f) are time-varying scaling factors for individual loss terms and are defined as in [36].
score-based models which
Both our method and GDSS perform denoising score- more-matching to the partial scores of X, and A,- However, our method additionally models the joint probability space of X, and A& via SDEs. This realized by the loss in Eq. 7, and this operation allows a model to flexibly estimate the complex dependency between nodes and edges with multi-resolution SGWT. Also, note that the scales of SWGT [=:]__ Eq. are trainable so that multi-level granularities that characterize a graph distribution can be adaptively captured during training.
Remark. While we solve the reverse SDEs for (X,, (A. 1. } in the training, we only need to solve the reverse diffusion processes (5) only for the node signal X and the non-filtered graph A = A 50 in the sampling phase. In other words, we do not generate {A in the sampling phase. Also note that the parameters of the networks As. are shared across different scales so that they can learn generalizable representations over different resolutions. As the shared parameters in the score function do not overfit to a specific scale, it also promotes stable training.
}
5

---

3.5 Score-based Joint Density Estimation with
Coherence
Finally, we describe the score-based models X and Ag.: to better capture the spectral coherence over different resolutions. In particular, revise the graph multi-head attention (GMH) [1] layer to better incorporate the spectral coherence between the edge and the node attributes. In the original GMH layer, node and edge attributes were encoded into query Q, key K, and value V as follows:
Q QqQ K == A, V= A,X,W
(8)
where Wo. WK. Wy are trainable weights. This layer is repeated for each {sa) as follows:
Q X K X,WK, V A X.Wv,
which incorporate spectral coherence at specific scale 8; given in Lemma 1. Using Q K V*, as the new query, key, and value for the GMH layer, one can incorporate the spectral coherence when training W's. Consequently, the score-based models consist of multiple GMH layers followed by multi-layer perceptron (MLP). We used the original GMH layer for the parameterization of Xg, and the modified GMH layer is used for As, Note that this parameterization preserves the permutation invariance of the original GMH layer, hence our score-basee based models are also permutation invariant.
4 Experiment
In this section, we quantitatively and qualitatively evaluate method in comparison various recent graph generative methods on four benchmark datasets. Ablation studies are also introduced to empirically analyze the roles of individual components within Wave-GD.
4.1 Datasets
We evaluated Wave-GD on four public datasets with varying sizes and characteristics, demonstrating its robustness and generalizability to generate high-quality graphs for diverse graph domains. Ego- small [33] consists of 200 small real sub-graphs from the Citeseer network dataset with S N < 18. Community-smal consists of 100 randomly generated synthetic graphs with 12 < N < 20.
The graphs are constructed by two equal-sized communities and each community is generated by E-R model [5] and 0.05. inter-community edges added with uniform probability as in previous works [17, 25]. Grid consists of randomly generated 100 standard 2D grid graphs with 100 < N 400. As all nodes
arranged in regular lattice, the maximum number of edges per node is 4. QM9 [31] is a molecular dataset with 133,885 molecules that are represented by attributed graphs with 1 S N < 9, four node types, and three edge types.
4.2 Experimental Setup
For all datasets, we used 80% of the whole data as a train set and the rest 20% as test set with the same split as in [13,42] As in [13], we sampled 10,000 molecules from the QM9 dataset, and for the remaining generic datasets, we sampled an equal number of data as the number of test data in each respective dataset. Also, the predictor-correttr sampler (PC-sampling) proposed in [36] was used to sample data with 1000 predictor and 1000 corrector steps.
We set two wavelet kernels kss): one is low-pass filter k(s) = e that captures signals in the low-frequency and the other k(s) = sze =z a band-pass filter which is 0 at the origin. To obtain the combined effect of the low-pass and band-pass filters using total of J scales, edges at one scale are filtered using the low-pass filter. For the remaining J scales, the band-pass filter is applied. This approach enables selective extraction and processing of different frequency components across the spectral domain. The number of scales was set to 11, 6, 4, and 6 for the Ego-small, Community Grid, and QM9 datasets, respectively. More detailed experimental settings are given Appendix
4.3 Experiment on Generic Graphs
To assess the versatility of Wave-GD, we used both real-world and synthetic datasets with varying sizes and characteristics. Experimental results these diverse generic datasets demonstrate the robustness of Wave-GD in sampling graphs of various characteristics.
Baselines and metrics. For experiments generic graph datasets (i.e., Ego-small, Community-small, and Grid), we compared the performance of our proposed method with the following autoregres- sive and one-shot graph generation methods: DeepGMG [16], GraphRNN [42], GraphAF [34].

---

Table 1: Generation results on generic graph datasets. MMD statisties between sampled graphs and test data are given, where smaller values indicate that the generated samples are more similar to the test set. The baseline results are from [13, 20, Mcan from three replicates are reported, and their standard deviations are reported in Appendix C.
Method
Ego-small
Community
-
Degree
Cluster
Orbit
Avg.
Degree
Cluster
Orbit
Avg.
Degree
Cluster
Orhir
DeeGGMG [16]
0.040
0,100
0.020
0,053
0.220
0.950
0.400
0.523
Autoreg.
GraphRNN [42)
0.090
0.220
0.003
0.104
0,080
0.120
0.040
0.080
0.064
0.043
0.021
0.043
GraphAF [34]
0.001
0.047
0.180
0.020
0.133
GraphDF (20)
0.040
0.130
0.010
0.060
0.060
0.120
0.030
0,070
GAIp [55]
0.130
0.170
0.050
0.117
0,350
0.980
0.540
0.623
1,619
0.0
0.919
0.846
One-sboo
GNF [17]
0.030
0.100
0.001
0.044
0,200
0.200
0.110
0.170
GNN (25)
0.052
0.093
0.007
0.051
0.053
0.144
0.026
0.074
0.455
0.238
0.328
0.340
GDSS [13]
0.021
0.024
0.007
0.017
0.045
0.086
0.007
0,046
0.111
0.005
0,070
0.062
DiGress [37]'
0.017
0.021
0.010
0.016
0.028
0.115
0.009
0.050
Wave-GD (Ours)
0.012
0.005
0.009
0.007
0.058
0.002
0.022
0.144
0.004
0.021
0.056
+: results not reported in the original manuscripts, t: results obtained with the official public code.
Table 2: Converged scales of generic graph datasets.
Dutuset
J
low-pass
bund-puss
Ego-small
11
45.4
46.8
46.6
43.7
40.6
38.1
37.0
31.3
29.0
25.6
20.0
Community-small
6
32.8
44.7
31.0
27.5
21.4
16.5
Grid
4
35.8
25.4
18.1
12.0
Table 3: Generation results on generic graph datasets using a larger number of samples. We compared 1024 generated samples with the given test set and evaluated their MMDs.
Ego-small
Community
Method
Degree
Cluster
Orbit
Avg.
Degree
Cluster
Orbit
Avg.
GraphRNN [42]
0.040
0,050
0.060
0,050
0,030
0.010
0.010
0.017
GNF [17]
0.010
0.030
0.001
0.014
0.120
0.150
0.020
0.097
EDP-GNN [25]
0.010
0.025
0.003
0.013
0.006
0.127
0.018
0.050
GDSS [13]
0.023
0.020
0.005
0.016
0.029
0.068
0.004
0.034
Wave-GD (Ours)
0.010
0.018
0.005
0.011
0.016
0.077
0.001
0.031
GraphDF [20]. GraphVAE [35], GNF [17], EDP-GNN [25], GDSS [13] and DiGress [37]. To evaluate the generation quality of the generated graphs, we used Maximum Mean Discrepancy (MMD) [7] to statistically measure similarities between probability distributions of sampled data and the real test data. Following prior works (13,42), we compared distributions of three different graph statistics-degree, clustering coefficient, and orbit counts-to compute MMD between generated and test graphs.
Main results. Table 1 shows the comparisons of degree, clustering, orbit, and their averaged MMDs between the graphs generated from baselines and our method. The results show that our model significantly outperforms all baseline models for all metrics on Ego-small and Community-smi datasets. Specifically, on the Ego-small dataset, Wave-GD demonstrated far smaller average MMDs by margin of 0.108 over Graph VAE and least 0.007 lower than DiGress. For the Community- small data, our method exhibited up to 0.601 lower MMD compared to Graph and at least 0.024 better than GDSS. For the Grid dataset, our method outperformed all baselines in terms of orbit MMD and outperformed all one-shot baselines for the averaged MMD. Note that, while one-shot models struggle to generate large graphs due to their intricate and complex structures, our method achieved comparable results to GraphRNN on large grid graphs (with 100 < N < 400). This highlights the effectiveness of our approach in learning graphs with varying sizes and structures through multi-resolution learning.
Table shows converged scales for different datasets. Interestingly, the scales of the large Grid dataset (with 100 < N < 400 nodes) were generally smaller compared to the Ego-small (4 < N < 18) and Community-smal (12 < N < 20) datasets. Specifically, the converged scales of Ego-small ranged within [20, 47] and the scales of Grid ranged within [12, 36). Note that the smaller scales capture local graph features with higher frequencies. Therefore, the results demonstrate that capturing local and detailed graph representations is more critical when dealing with complex and large graphs, in
7

---

Train
Ours
Train
Ours
Train
0.0889
0.9231
0.9231
0.9
0.9286
0.9286
0,9112
0.9412
0.8947 0.8888
0.9474
Ours
Figure 3: Visualization of training samples and generated graphs on Ego-small (top), Community-small (middle), and QM9 (bottom). The generated molecules from the QM9 dataset (bottom panel) are represented with the pairwise Tanimoto similarity based the Morgan fingerprints [15], which show the one-to-one similarity the real training samples the same location the upper panel.
5DS5 Cuns
GOSS
Ours
6D6S
Curs
GDSS
MND
0.05
MMD
MMD
0:3
0.2
2000
3033
4200
5000
1002
2003
2003
1200
5200
1000
2022
1200
4030
530
Epoch
Epoch
Epooh
Epuch
(a) Degree
(b) Clustering
(c) Orbit
(d) Average
Figure 4: Comparison MMDs between GDSS and Wave-GD on Ego-small. The sample quality of
Wave-GD GD stable and converges faster for a) Degree, b) Clustering, c) Orbit, and d) their average.
comparison to smaller graphs. In other words, for the Ego-small and Community-smal small datasets, features in relatively low frequency (e.g., cluster-related features) were captured with larger scales.
Experiments with larger sample size. To provide more definitive assessment of the generated sample quality, we conducted additional experiments by generating larger number of samples compared the test data, as in previous works [13, [13, 17.25J. For this, we sampled 1024 graphs for evaluating the MMD metrics for the Ego-small and Community- small datasets. As shown in Table 3, the lower MMDs of Wave-GD demonstrate superior performance to the baselines on Ego-small. For the Community-sme small dataset, GraphRNN performed better than ours on the averaged MMD, however, our method still surpasses recent acore-based models [13,25 and normalizing flow model [17] with at most 0.066 margin. Along with these quantitative results, we present the actual visualization of the generated samples from Wave-GD in Fig. 3, which are highly similar to the training samples.
Stability analysis. In addition to MMDs, we present a stability analysis of Wave-GD in Fig. 4. The figure presents comparison of the averaged MMDS between GDSS and our method the Ego-small dataset. Specifically, between 3000-5000 epochs, while the difference between the maximum and minimum values of the averaged MMD of GDSS is 0.016, Wave-GD shows better stability with a difference of ~0.0018 at the same epochs, indicating that our method can much more robustly generate high-quality samples.
4.4 Experiment on Molecular Graphs
In addition the generic graphs, we evaluated Wave-GD on a molecular benchmark dataset, which contains complex chemical bonds between atoms (i.e., nodes) and edges. By evaluating Wave-GD on

---

Table Generation results on QM9 molecular dataset. The baseline results are taken from [13,20, 34] and all results are presented without validity correction. We report the mean of three runs and their standard deviations. The best performance is marked in bold and the second-best result is indicated by an underline.
Method
Validity (%)
Novelty f
Uniq. f
Avg. (%)
NSPDK
FCD J
time
Ope-shot AR
GraphAF [34]
67
88. 83
94.51
83.45
0,020 3
5.27 +
2.52cl
GraphDF [20]
82.67
98.10
97.62
92.80
0,063 1e-3
10.82 +
5.35c*
MoFlow [44]
91.36 = 1.2
94.72 8
98.65 +
94.91
0.017 + 3e
4.47 4 6
4.60."
EDP-GNN [25]
47.52 + 3,6
86,58 + 1.9
99.25 .11
77.78
0.005 + Ie
2.68 + .2
4,40c²
GraphEBM [18]
8.22 + 2.2
97.01 = .2
97.90 +
67.71
0,030 + 4e-3
6.14 + .4
3.71e!
GDSS [13]
95.72 = 1.9
86,27 2.3
98.46 + .6
93.48
0.003 + 0
2.90
1.14g
DiGress [37]]
99.37 + .0
35.31 0
96.74 + 0
77.14
1.4e + .0
0.07 + .0
6.14c²
Wave Wave-GDDaa (Ours)
96.95 1 33
89.79 = 5
98.87 22
95.20
0.003 +: .0.0
3.85 :.
1.21e*
results obtained with the official public code.
the molecular graph generation task, we validated its ability to capture the complex dependencies between nodes and edges. Notably, Wave-GD successfully generated plausible graphs while adhering to the chemical valency rule, ensuring the realistic representation of molecular structures.
Baselines and evaluation metrics. In this experiment, we compared the results from seven baselines and Wave-GD on real molecular QM9 dataset. Among the baselines, two are autoregressive flow- based models, namely GraphAF [34] and GraphDF [20]. which employ discrete latent variables. Five others are one-shot generative models, which include MoFlow [44], GraphEBM [18), EDP-GNN [25], GDSS [13], and DiGress [37]. Following the standard procedure as in [20, 34], the molecule data were kekulized by the RDKit library [15] and hydrogen atoms were removed.
We evaluated the quality of generated molecular samples with six metrics as [13]: 1) Validity is the fraction of valid molecules that hold chemical rules. In our experiment, we did not apply any valency correction or edge resampling. 2) Novelty measures the proportion of valid molecules that are not present in the training set. 3) Uniqueness is the proportion of generated molecules that are not duplicated. 4) Neighborhood subgraph pairwise distance kernel (NSPDK) [3] is the MMD between the generated molecules and test molecules which considers both the nodes and edges for evaluation. 5) Fréchet ChemNet Distance (FCD) [30] evaluates the distance between distributions of the training and generated sets using the activations of the ChemNet layer. 6) Time quantifies the duration required to generate 10,000 molecules in the RDKit molecule format. In addition to these metrics, we also report the average values of validity, novelty, and uniqueness present unified evaluation over various aspects of the generated graphs.
Results. As shown in Table 4, our model outperformed all baselines on the average of validity, novelty, and uniqueness and showed the second-best results on validity, uniqueness, and NSPDK. To be specific, our method showed at most 27. 27.49% gain over GraphEBM and 18.06%p margin over DiGress in terms of the averaged statistic. Note that, DiGress performed better than our model in NSPDK and FCD, however, its lower novelty (35.31%) inherently leads to lower FCD and NSPDK scores. As the molecular generation task aims to create previously unseen molecular structures, novelty may be more critical measure which Wave-GD performed better.
In general, Wave-GD outperformed most of the baselines, excelling not only in generation quality but also in generation speed. It was faster than all autoregressive models, showing 442x speed up compared to GraphDF and 21 x speed up compared to GraphAF. Moreover, our method requires shorter generation time than discrete-time diffusion models. For example, our method was 36x faster than EDP-GNN and 5x faster than DiGress. These results demonstrate that employing a continuous-tine diffusion process for converting graphs into noise and vice versa is considerably more efficient compared to the discrete-step noise perturbation utilized in EDP-GNN and DiGress.
4.5 Ablation Studies
Ablation study on oversmoothing, In Fig. 5, we present the effect of the number of GMH layers (i.e.. depth D) on the quality of generated samples. With larger D, while the sample quality of GDSS decreased with high averaged MMDs (blue line) due to the oversmoothing, the average MMD of Wave-GD (yellow line) is consistently low representing high fidelity in the generated samples. This because Wave-GD captures diverse graph frequency characteristies by adaptive multi-resolution filtering, which allows the model to preserve fine-graines details even in deeper layers.

---

Communiyy straal
Deg. +
Clus.
Orb. 4
Avg.
0.12
0.011
0.072
0,003
0.028
Degree
Clustering
Drotts
0.007
0.031
0.08
0.006
0.065
0.002
0.024
MM00
0.007
0.058
0.002
0.022
0.005
0.069
0.009
0.027
Val.
Uniq.
Nov.
Avg.
0.03
97.73
79.21
92.68
89.87
QM9
96.82
88.68
99.07
94.85
96.70
88.95
98.91
94.85
96.36
88. 10
98.82
94.42
Figure 5: Comparison between Wave-GD (yellow line) and GDSS (blue line) for GMH depths D Community-small Bar graphs are MMDs of Wave-GD.
Table 5: Ablation studies on the number scales,
Ablation study on the number of scales. In Table 5, we report degree, cluster, orbit MMDs, and by changing the numbers of scales J. Also, validity,
their averaged value on the Community-sman uniqueness, novelty, and their averaged value are presented on the QM9 dataset for multiple J's. All experiments were replicated three times and the averaged results are reported. We observed that the averaged MMD slightly depends on the number of scales, however, the overall quality of generated samples still better than existing baselines most settings.
4.6 Limitations
Although Wave-GD is robust to varying numbers of scales as shown in Table 5, the choice of J differs across datasets which should be carefully chosen by user. Also, as Wave-GD performs multi-resolution diffusion, it requires larger resources than conventional models during training. However, the diffusion processes are performed in parallel there is overhead in time. Moreover, as sampling is performed without multi-resolution filtering, the generation process is still quite efficient.
5 Conclusion
In this paper, proposed Wave-GD which leverages spectral dependencies between node and edge signals to better characterize their joint distributions via a score-based diffusion model. By capturing their multi-resolution coherence, the model is able to generate graphs of high-fidelity preserving frequency characteristics of the graphs from the training samples. Extensive validation on various datasets and superior performance of Wave-GD highlights its significant potential for various application domains for graph modeling and generation.
Acknowledgement. This research was supported by NRF-2022R (000022R1A22299200 00290 (40%), JTTP-2019-0-01900 (AI Graduate Program at POSTECH, 10%), ITTP-2022-2024 01461 (TTRC, 10%) from South Korea, and NSF IIS CRII 1948510 from the U.S.
A2C2092336 (40%). 1022-2022-0-
References
[1] Baek, J., Kang, M., et al.: Accurate learning of graph representations with graph multiset pooling. International Conference Learning Representations (2021)
[2] Cho, H., Wu, G., al.: Mixing temporal graphs with MLP for longitudinal brain connectome analysis. In: International Conference on Medical Image Computing and Computer-Assisted Intervention. pp. 776-786. Springer (2023)
[3] Costa, F., De Grave, K.: Fast neighborhood subgraph pairwise distance kernel. In: International Conference on Machine Learning. pp. 255-262 (2010)
[4] De Cao, N., Kipf, T.: MolGAN: An implicit generative model for small molecular graphs. arXiv preprint arXiv:1805. 1973 (2018)
[5] Erdös, P., Rényi, A.: On random graphs i. Publicationes Mathematicae (Debrecen) 6. 290-297 (1959)
[6] Grenander, U., Miller, M.I.: Representations of knowledge in complex systems. Journal of the
Royal Statistical Society: Series B (Methodological) 56(4), 549-581 (1994)
10

---

[7] Gretton, A., Borgwardt, K.M., et al.: A kernel two-sample test. The Journal of Machine Learning Research 13(1). 723-773 (2012)
[8] Grover, A., Zweig, A., al.: Graphite: Iterative generative modeling of graphs. In: International Conference on Machine Learning, pp. 2434-2444 PMLR (2019)
[9] Hammond, D.K., Vandergheynst, P., et al.: Wavelets on graphs via spectral graph theory.
Applied and Computational Harmonic Analysis 30(2), 129-150 (2011)
[10] Hui, K.H., Li, R., et al:: Neural wavelet-domain diffusion for 3d shape generation. In: SIG- GRAPH Asia 2022 Conference Papers. pp. 1-9 (2022)
[11] Jin, W., Barzilay, R., et al.: Junction tree variational autoencoder for molecular graph generation.
In: International Conference Machine Learning. pp. 2323-2332222 PMLR (2018)
[12] Jin, W., Barzilay, R., et al.: Hierarchical generation of molecular graphs using structural motifs.
In: International Conference on Machine Learning. pp. 4839-4844 PMLR (2020)
[13] Jo, J., Lee, S., et al.: Score-based generative modeling of graphs via the system of stochastic differential equations. In: International Conference on Machine Learning, pp. 10362-10383. PMLR (2022)
[14] Kim, W.H., Kim, H.J., et al.: Latent variable graphical model selection using harmonic analysis: applications to the Human Connectome Project (HCP). In: Computer Vision and Pattern Recognition. pp. 2443-2451 (2016)
[15] Landrum, G., et al.: RDKit: Open-source cheminformatics software. 2016. URL http://www. rdkit. org/, https://github. com/rdkit/rdkit (2016)
[16] Li, Y., Vinyals, O., et al.: Learning deep generative models of graphs. arXiv preprint
arXiv:1803.03322 (2018)
[17] Liu, J., Kumar, A.. et al.: Graph normalizing flows. Advances in Neural Information Processing Systems 32 (2019)
[18] Liu, M., Yan, K., et al.: GraphEBM: Molecular graph generation with energy-based models. arXiv preprint arXiv:2 Sat.::220200546 (2021)
[19] Liu, Q., Allamanis, M., et al.: Constrained graph variational autoencoders for molecule design. Advances in Neural Information Processing Systems 31 (2018)
[20] Luo, Y., Yan, K., al.: GraphDF: A discrete flow model for molecular graph generation. In:
International Conference on Machine Learning. pp. 7192-7203. PMLR (2021)
[21] Ma, T., Chen, J., et al.: Constrained generation of semantically valid graphs via regularizing variational autoencoders. Advances in Neural Information Processing Systems 31 (2018)
[22] Ma, X., Wu, G., et al.: Learning multi-resolution graph edge embedding for discovering brain network dysfunction in neurological disorders. In: Information Processing in Medical Imaging. pp. 233-266..32 Springer (2021)
[23] Madhawa, K., Ishiguro, K., et al.: GraphNVP: An invertible flow model for generating molecular graphs. arXiv preprint arXiv: 1905. 1600 (2019)
[24] Mallat, S.: A wavelet tour of signal processing. Elsevier (1999)
[25] Niu, C., Song, Y., al.: Permutation invariant graph generation via score-based generative modeling. In: International Conference on Artificial Intelligence and Statistics. pp. 4474-4484. PMLR (2020)
(26) Opolka, F., Zhi, Y.C., al.: Adaptive gaussian processes on graphs via spectral graph wavelets. In: International Conference on Artificial Intelligence and Statistics. pp. 481 4818-4834, PMLR (2022)
[27] Parisi, G.: Correlation functions and computer simulations. Nuclear Physies 180(3). 378-384 384 (1981)
[28] Park, J., Hwang, Y., et al.: Convolving directed graph edges via Hodge Laplacian for brain network analysis. In: International Conference on Medical Image Computing and Computer- Assisted Intervention. pp. 789-799. Springer (2023)
[29] Popova, M., Shvets, M., et al.: MolecularRNN: Generating realistic molecular graphs with optimized properties. arXiv preprint arXiv:1905. 133772 (2019)

---

[30] Preuer, K., Renz, P., et al.: Fréchet ChemNet distance: metric for generative models for molecules in drug discovery. Journal of Chemical Information and Modeling 58(9). 1736-1741 (2018)
[31] Ramakrishnan, R., Dral, P.O., et al.: Quantum chemistry structures and properties of 134 kilo
molecules. Scientific Data ((1), 1-7 (2014)
[32] Rogers, L.C.G., Williams, D.: Diffusions, Markov processes and martingales: Volume 2, Itō calculus, vol. 2. Cambridge University Press (2000)
[33] Sen, P., Namata, G., et al..: Collective classification in network data. Al Magazine 29(3). 93-93 (2008)
[34] Shi, C., Xu, M., et al.: GraphAF: a flow-based autoregressive model for molecular graph generation. International Conference on Learning Representations (2020)
[35] Simonovsky, M., Komodakis, N.: GraphVAE: Towards generation of small graphs using
variational autoencoders. In: International Conference on Artificial Neural Networks, pp. 412-
422. Springer (2018)
[36] Song, Y., Sohl-Dickstein, J., et al.: Score-based generative modeling through stochastic differ- ential equations. International Conference on Learning Representations (2021)
[37] Vignac, C., Krawczuk, et al.: DiGress: Discrete denoising diffusion for graph generation.
International Conference on Learning Representations (2023)
[38] Vincent, P.: A connection between score matching and denoising autoencoders. Neural Compu-
tation 23(7), 1661-1674 (2011)
[39] Wang, H., Wang, J., et al.: GraphGAN: Graph representation learning with generative adversarial
nets. In: Association for the Advancement of Artificial Intelligence. vol. 32 (2018)
[40] Xu, B., Shen, H.. al.: Graph wavelet neural network. International Conference on Machine
Learning (2019)
[41] You, J., Liu, B., et al.: Graph convolutional policy network for goal-directed molecular graph
generation. Advances in Neural Information Processing Systems 31 (2018)
[42] You, J., Ying, R., et al.: GraphRNN: Generating realistic graphs with deep auto-regressive
models. In: International Conference on Machine Learning. pp. 5708-5717. PMLR (2018)
[43] Yu, JJ.Q., Gu, J.: Real-time traffic speed estimation with graph convolutional generative autoencoder. IEEE Transactions on Intelligent Transportation Systems 20(10), 3940-3951 (2019)
[44] Zang, C., Wang, F: MoFlow: invertible flow model for generating molecular graphs In:
ACM SIGKDD Conference on Knowledge Discovery and Data Mining. pp. 617-626 (2020)
[45] Zhang, Q., Chang, J., et al.: Spatio-temporal graph structure learning for traffic forecasting. In: Association for the Advancement of Artificial Intelligence. vol. 34, pp. 1177-1185 (2020)
12

---

Appendix
In this appendix, we present 1) the proof of Lemma given in the main paper, 2) additional implementation details of Wave-GD, 3) standard deviations of MMDs for generic datasets, 4) additional ablation studies on the number of scales on Ego-small and Grid datasets, 5) holistic architecture of score-based models Xg and As. and 6) qualitative comparison of generated samples for all datasets which were not included in the main manuscript due to the page limit.
A Proof of Lemma 1
Lemma 1.
Let be an undirected graph, with a node signal and a symmetric adjacency matrix A. Given wavelet coefficients W (s) and (x(s), which spectral representations of X and A at a specific scale s, dot product of these wavelet coefficients is equivalent to the product between the scale-fite fale-fil edge signals and the node signals in the graph space, i.e., WA(s) (W((s) A
Proof. With vh. UK(SA)U" as the basis, the wavelet coefficients of the edge and node signals are given follows:
WA = 1/ A Uk(sAJUTA A
(10)
(x(s) t., X Uk(sA)U"X.
As the (ssA) is a diagonal matrix and U is set of orthonormal eigenvectors, the dot product of WA (s) and Wx(s) is computed as
Wa(s) Wx(s) (UMSAJU" (UK(SA)UXX
AU (SUU"UA' -AUK(AJK(SS)IU'
(1I)
AURR(AAUUXX
From Eq. (3) in the main paper. A v. WA(S) US?USU A, and Eq. (11) becomes
WA(s) Wx (A
(12)
= A
as A is symmetric. Therefore, a dot product of wavelet coefficients the edge and node signals be replaced with a spatial graph convolution form in the graph domain by applying inverse transform only to the edge coefficients.
13

---

B Additional implementation setting
We utilized the PyTorch framework implement Wave-GD and trained the model using a single NVIDIA GeForce RTX 3090 GPU. In Table 6, we provide details of the implementation settings of Wave-GD. For a fair comparison, we followed the same settings of data splitting and node features as in [13, 17, 25, 42]. For generic datasets, the node features are initialized as one-hot encoding of the degrees and the generated adjacency matrices are quantized with the operator 1.5005 to obtain binary edges. As in [13], we used two types of SDEs: Variance Preserving (VP) SDE and Variance Exploding (VE) SDE [36] for diffusion processes. To solve the SDEs, we used the peedictor-correcte sampler (PC sampler) [36] with either the Euler-Maruyama (EM) predictor the
reverse diffusion predictor (Rev), which discretizes the reverse-time SDE. As the corrector for the
sampler, Langevin MCMC [6. 27] was employed.
Table 6: Hyperparameters of Wave-GD for all datasets. We provide hyperparameters and detailed settings for training two score score-based models Ag and Ag and diffusion processes with SDE.
Hyperparameter
Egalsmall
Community-sman small
Grid
QM9
Number of attention heads
4
Number of initial channels
2
2
Number hidden channels
8
Number of final channels
4
4
4
Number GCN layers
3
Hidden dimension
32
32
32
16
Number scales
11
6
Number of attention heads
4
4
Number of initial channels
2
Number hidden channels
8
Number of final channels
4
4
Number of GCN layers
5
3
Hidden dimension
32
32
32
16
Type
VP
VP
VE
Number of sampling steps
1000
1000
1000
1000
SDE
Bmnn
0.1
Amaz
1.0
1.0
1.0
1.0
Type
VE
Number of sampling steps
1000
1000
1000
1000
SDE {A")o
8mi
0.1
0.1
8man
1.0
1.0
0.8
1.0
Type
EM
Langevin
Rev. + Langevin
Rev. Langevin
Solver
SNR
0.05
0.1
0.2
Scale coefficient
0.7
0.7
Optimizer
Adam
Adam
Adam
Adam
Learning rate
8 x 10
5
10-3
x 10
Weight decay
x 10-4
10-4
x 10-4
x 10-4
Train
Batch size
128
128
1024
Number of epochs
5000
5000
6000
300
Exponential Moving Average
0.999
14

---

C Generation results with standard deviation on generic datasets
In Table 1 and Table of the main manuscript, we reported the mean MMDs of three independent runs generic datasets, using different model parameter initializations. In Table 7, we provide the standard deviation of degree, clustering, and orbit MMDs, as well the time required to generate samples for each generic dataset. The generation time slightly increases in the experiments where more samples (i.e., 1024 samples) are generated on Ego-small and Community-small datasets. Furthermore, as the graph becomes more complicated with more nodes and edges, the generation time also increases accordingly.
Table 7: Generation results of Wave-GD on the generic datasets. The results are the mean MMDs of three runs and their standard deviation.
Ego-small
# of test data
# of samples
Degree
Cluster
Orbit
time (s)
40
0.012 E 0.001
0.010 1 0.001
0.005 0.001
40.03
40
1024
0.010 1 0.001
0.018 + 0.003
0.005 0.002
40.95
Community
small
20
0.007 + 0.002
0.058 + 0.004
0.002 0.0
89.80
20
1024
0.016 1 0.003
0.077 4 0.006
0.001
0.002
94.75
Grid
20
0.144 0.004
0.004 + 0.001
0.021
0.001
733.79
D
Ablation studies on the number of scales
Along with Table 5 in the main paper, report the ablation studies on the number of scales / for Ego-small and Grid datasets Table All experiments with different were replicated three times and their averaged results were reported. We found that the average MMDs on the Ego-small slightly differ depending on the J and that of Grid relatively consistent along the J's. general, the number of scales affects the sample quality depending on the datasets, however, the averaged MMD of Wave-GD is still better than cxisting methods most settings.
Table 8: Ablation studies on the number of scales.
Ego-small
Grid
Deg.
Clus.
Orh.
Avg.
Deg.
Clus.
Orb.
Avg.
0.019
0.016
0.011
0.015
0.142
0.003
0.034
0.059
0.016
0.001
0.015
0.011
0.144
0.004
0.021
0.056
10
0.015
0.008
0.005
0.009
0.161
0.001
0.015
0.059
0.012
0.010
0.005
0.009
0.168
0.005
0.015
0.062
12
0.018
0.016
0.013
0.016
15

---

E The architecture of the score-based models of Wave-GD
Graph Mulli Head Attention (GMH)
(A Xia)
Attertionn
GAN(ALo Koo 1) GCN GCN(ALO-1
GCN GCN(Aun Kea)
Xzn N
Aze
Xca
(C.(Aca.X.p)
Ex
Figure 6: The architecture of X4 that estimates the partial score Vx, logge(Ge).
Graph Multi-Hend Attention (GMI))
Q CCN(A Ken)
30 (A N12-
GCN Xenl
Min
NiP
GCN Ner
Acn 11
Ace
Xxe
GCM
GCN(Aca- Nopo-)
Palogp((X,AA)
shared
shared
ocu(As Nen) * GCN Kenl
GCN GCN Man-1)
Attonttoo
MrP
MLP
GCN (A Ken-1
ML
M12
Meg I.. ll
V GCN Kyp-s)
A/e
Xin
V. (X.
Figure 7: The architecture of A that estimates the partial scores V (og):(G.)) and {V A log (r()
Here we illustrate the architecture of score-based models Xz. and Ag.t in Figure and Figure 7, respectively, which described in Section 3.5 in the main manuscript. Basically, utilized graph multi-head attention (GMH) [1] as in GDSS [13], which is an iterative attention mechanism using graph convolutions as query, key, and values.
Given H1, = X,, the attention operation GMH(-) is performed D times to estimate the partial scores Vx, log Pr (Xe, Ar) and { AV logpt A )) as follows:
(G.) = MI.P, ([[MM (H At.a) (G = MI. ([ (H,, )
(13)
respectively, where [-] represents the concatenation of GMH outputs and H1,4+1 GNN(H,,d Ar.a)
As shown Figure the score-based model Ag shared across the multi-resolution edges and the given adjacency matrices. During training, it estimates the partial scores in parallel along the graphs using a graph convolution with node features X in the GMH layers, so that the model able to capture generalized spectral coherence across different resolutions. However, in the sampling process, only the partial score of A, (i.e., VA, log Pt (X,, A,)) is estimated from Ag. as generating samples of multi-resolution edges is not our aim. For the other score-based model Xg. it produces the partial score Vx, log Pe (X1, Ar) in both training and the sampling processes as does not rely on multi-resolutien approach.
16

---

Qualitative evaluation of generated samples
F1 Comparison with state-of-the-art baselines on generic datasets
In Figures 8, 9, and 10, we qualitatively compare the generation results of Wave-GD on the generic datasets with two ofte-oofthhe-rr diffusion models for graph generation: DiGress [37] and GDSS [13]. The visualized graphs demonstrate the superiority of Wave-GD which closely simulates training data compared the SOTA baselines.
Train
Ours
DiGress
GDSS
Figure Non-curated samples generated by Wave-GD, DiGress, and GDSS trained on the Ego-small dataset.
Train
Ours
DiGress
GDSS
Figure 9: Non-curated samples generated by Wave-GD, DiGress, and GDSS trained the Community-smen dataset.
Train
Ours
GDSS
Figure 10: Non-curated samples generated by Wave-GD, DiGress, and GDSS trained on Grid dataset.
17

---

F.2 Comparison with state-of-the-art baselines on QM9 dataset
In Figure we provide the visualization of training datasets and generated samples of Wave- GD for the molecular dataset. Along with the visualization, a quantitative comparison is also provided by measuring Tanimoto similarity based on Morgan fingerprints, which are calculated by the RDKit library [15]. For each generated molecule, the pairwise similarity between the training sample is calculated. As shown in the figure, Wave-GD successfully generates high-quality molecules that closely resemble the training data, whereas other baseline methods produce molecules that deviate from the training distribution.
Train
Ours
0.9412
0.9412
0.9
0.9474
0,9474
DiGress
0.5263
0.381
0.4583
0.4706
0.45
0.6087
0.52
0.5238
0.5714
0.5556
0.5
GDSS
0.8
0.8333
0.6667
0.5882
0.5789
0.5
0.6818
0.4091
0.4348
0.6
0.7143
0.5789
Visualization of the sampled graphs on the QM9 dataset with maximum Tanimoto similarity. For each graph, we display the one-to-one similarity to the real training samples the same location in the upper panel.
Figure 11:
18


Reviews:
[{"review_id": "OlYg9PHoqW", "reviewer": "Reviewer_6cNy", "summary": "This paper claims the node feature and graph topology are not coherent in most previous generative graph models and high-frequency signals in node features and graph topology may neglect during the generation process. Therefore, they propose a Wavelet graph diffusion model (Wave-GD) with score-based diffusion. Specifically, it uses different graph wavelet bases to get graph signals in different frequency ranges. The overall model diffuses node features, the original graph, and the adjacency matrix constructed by graph wavelet bases. To improve the coherence between node features and graph topology, the score-based models are based on graph multi-head attention layers, which take the product of node features and adjacency matrices including the original one and ones learned by different bases, which alleviates the gap between node features and graph structures. Performance on three small synthetic datasets and one real-world molecular dataset show that the proposed model can generate graphs that are not only realistic graphs in shape but also obey the chemical rules in high fidelity.", "questions": "Q1: Would you give some experimental analysis that can show if the main contribution comes from coherence or multi-resolution?\n\n\nQ2: how do you define $s$ for graph wavelet bases?\n", "limitations": "Yes. It may produce molecules that may harm the body.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThe novel part is the paper considers high frequency and discovers the coherence between node features and graph structures in diffusion models but still uses a simple dot product to solve it.\n2.\tThe empirical results on real-world molecular datasets show the effectiveness in terms of generating realistic graphs with high fidelity and high novelty in a relatively fast time. \n3.\tThe model enjoys high flexibility regarding different tasks where they need frequency graph signals at different scales. \n", "weaknesses": "1.\t\"nodes and edges\" in line 26 is misleading, it would be better if you mention \"node\" means \"node features\" and \"edges\" means \"graph structures\" in the introduction and then use \"node\" and \"edge\" for simplicity.\n2.\tMulti-resolution and coherence are two major claims in your paper, but it is not verified that coherence improves performance. \n3.\tthe proposed model is limited to small graphs due to the decomposition in spectral graph wavelet bases.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "W1) Change descriptions of the node and edge in line 26.\n\nA) We will use the terms ‘node features’ and ‘graph structure’ in the intro properly as the reviewer suggested. We appreciate the reviewer's comment. \n\nW2/Q1) Does performance improvement come from coherence or multi-resolution?\n\nA) As we have shown in the proof of Lemma 1 (in the supplementary material), the coherence as a dot product between wavelet representation $W_{A}(s)$ and $W_{X}(s)$ at scale $s$ in the spectral domain is equivalent to a simple matrix multiplication $A^{s}X$ in the graph domain. Although the concept of coherence was not used in the previous literature, GDSS used the formulation $AX$ to compute scores for joint distribution learning, and we are essentially deriving its multi-resolution representations and using them as the multi-resolution coherence. Therefore, we conclude that it is the multi-resolution that improves graph generation.\n\nW3) The method is limited to small graphs due to spectral decomposition.\n\nA) We agree that online spectral decomposition can be challenging for extremely large graphs due to its computational costs, i.e., $O(N^3)$ with $N$ nodes. To mitigate this issue, first of all, conventional polynomial approximations for the transforms can be easily achieved based on [1,2], which have been cited in the original manuscript. Moreover, for exact computation, the decomposition does not necessarily have to be performed online. It can be done in the data preprocessing stage to save all eigenvectors and eigenvalues before model training, which can be a reasonable strategy for a population of graphs with relatively small sizes.  \n\nTo empirically assess the computational cost for the decomposition, we examined the actual decomposition time of randomly generated \"fully connected graphs of diverse sizes\" and presented their results in the pdf of the general response (Fig 1(b)). The decomposition was performed using Pytorch (with torch.linalg library) on one Nvidia T4 GPU. As shown in the result, a random graph with 10 nodes requires 0.0004s and a random graph with 5000 nodes requires 20.1s for decomposition. If there are 1000 graphs with 5000 nodes, the required time is probably <6 hours. We think this computational cost with ~5000 nodes may be reasonable and applicable in many practices as it only needs to be done only once at the first preprocessing stage. \n\n[1] Xu et al. \"Graph wavelet neural network.\" International Conference on Learning Representations (ICLR), 2019.\n\n[2] Ma et al. \"Learning multi-resolution graph edge embedding for discovering brain network dysfunction in neurological disorders.\" Information Processing in Medical Imaging (IPMI), 2021.\n\nQ2) How do you define $s$?\n\nA) The scales for graph wavelet bases were randomly initialized within a range $[10, 50]$, and they converged to different values after training. We provided figures of convergences of the scales for each dataset in Section 7 of the supplementary material. Also, the optimal values are presented in the pdf of the general response, which we will add in the revision once the paper is accepted. "}, {"review_id": "EqXdjGKnHc", "reviewer": "Reviewer_jRF4", "summary": "The paper introduces a graph generative approach that leverages diffusion models and wavelet theory. The key concept revolves around utilizing the wavelet transform of the adjacency matrix across various scales, and learning a joint backward diffusion process that remains valid at all considered scales simultaneously. Consequently, the proposed approach exhibits a multi-resolution characteristic. The proposed approach is evaluated in the graph generation task using four benchmarks and is compared against autoregressive and one-shot approaches from previous works.", "questions": "It would be helpful if the authors could provide clarification on why only $A^s$ and not $X^s$ is considered for learning the diffusion process.\n\nRegarding Table 4, should the lower numbers indicate better results? In the QM9 part of the table, higher numbers are bold. Is my interpretation wrong?\n\nThe following paper, which explores diffusion in the wavelet coefficient space for 3D shape generation, could be an interesting reference: \\\n_Hui, Ka-Hei, et al. \"Neural wavelet-domain diffusion for 3d shape generation.\" SIGGRAPH Asia 2022 Conference Papers. 2022_", "limitations": "The authors adequately addressed the limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The adaptation of diffusion models to the graph generation field is a timely and intriguing topic, considering the challenges posed by the discrete nature of graph data.\n\nThe experimental evaluation provides substantial support for the claims made in the paper. The proposed approach outperforms recent methods on three benchmark in the graph generation task and achieves comparable results in molecule generation task.\nThe experimental setup and the metric considered for the evaluation are clearly presented.", "weaknesses": "Having to choose the parameter *J* without any insight or guidance for different datasets can be a drawback in practical applications. I would suggest to further investigate the relationship between performance and *J* among different datasets, along with the impact of graph statistics on the optimal *J*. Also, it is not clear which how many scales have been used to obtain the results reported in Tables 1-3.\n\nThe time complexity of the proposed approach, as indicated in Table 3, could present challenges in certain settings. Further discussion or potential mitigation strategies for addressing this issue would be beneficial.\n\nClarity could be improved in certain sections. For instance, Figure 1's purpose is unclear to me, and the role of spectral coherence between nodes and edges in the proposed approach needs better explanation. Providing a clear definition of the scale (s) domain and kernel function (k) in the preliminary sections would also help readers understand the concepts more quickly.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nW1) Ablation study on $J$ and analyses of the impact of graph statistics on the optimal J are needed. Also, how the J’s were set to obtain the main results? \n\nA) We provide our answers in the following, and we will discuss them in the main manuscript to make the paper more clear. \n* We agree that the number of scales $J$ needs to be carefully chosen for each dataset. We already have done the ablation studies on $J$ which are given in Table 4 of the manuscript for Community-small and QM9 datasets and Section 4 of the supplementary for Ego-small and Grid datasets. We observed that the results are not too sensitive to $J$, but we had to try varying numbers to obtain the optimal result. \n\n* For the relationship between $J$ and graph statistics, we empirically observed that relatively smaller $J$ ($J=4$) performs better on large Grid graphs (with $100 \\leq |V| \\leq 400$) and larger $J$ ($6 \\leq J \\leq11$) showed the best performances on smaller graphs such as Ego-small ($4 \\leq |V| \\leq18$), Community-small ($12 \\leq |V| \\leq 20$) and QM9 ($1 \\leq |V| \\leq 9$). \n\n* As we mentioned in line 224, to obtain the results in Table 1-3, $J$ was set to $11$, $6$, $4$, and $6$ for the Ego-small, Community-small, Grid, and QM9 datasets, respectively. Also, we analyzed the convergences of $J$ scales along epochs for each dataset and reported the results in Section 7 of the supplementary material. The exact trained scale values were reported in the pdf of the general response.\n\nW2) Time complexity could present challenges.\n\nA) As in GDSS, PC sampling was used with a reverse diffusion predictor and Langevin MCMC corrector for the QM9 dataset. By omitting the correction step and using a predictor-only method, the sampling time was reduced from 154s to 61s. However, we observed a trade-off between sampling time and sample quality, as validity slightly decreased (~1.7%p drop) for a predictor-only method. Regarding the complexity challenge for the spectral decomposition of large graphs, as we mentioned to Reviewer 6cNy, there are approximations available. \n\n\nW3) Need to improve clarity (e.g., Figure. 1, description of the spectral coherence, scales, and kernel function).\n\nA) Thank you for the suggestion. We will improve the clarity that the reviewer pointed out such as a description of the kernels we used, and the definition of scales in the preliminary section as well as in Figure 1. The intention of Figure 1 was to show that certain connections/disconnections are accentuated at specific scales which can be better characterized in the diffusion model, and we will connect dots between Figure 1 and the design of our model to help future readers. \n\n\nQ1) Why only $A^s$ is used and $X^s$ is not considered?\n\nA) As shown in the proof of Lemma 1 in the supplementary material, using either $A^s$ or $X^s$ is enough to capture the spectral coherence between node features and graph structures. Specifically, the Eq. (2) and (3) in the proof show that $W_{A}(s) \\cdot W_{X}(s) = AUk^2(s\\Lambda)U^TX = A^sX = AX^s$. Therefore, either $A^s$ or $X^s$ should be used with an unfiltered counterpart. We will add this explanation to the revised manuscript for better understanding.\n\n\nQ2) Interpretation in Table 4 is confusing.\n\nA) As in Table 3, higher numbers are better results for QM9. Note that, the metrics we used for the molecular QM9 dataset, i.e., validity, uniqueness, novelty, are different from those for generic graph datasets. Unlike QM9, lower MMD values indicate better results for the generic graph datasets such as Ego-small, community-small, and Grid. We will improve the clarity in Table 4 by adding up/down arrows beside the metrics.\n\nQ3) Suggestion on additional reference.\n\nA) Thank you for suggesting an interesting reference on 3D generative modeling with wavelet representation. The proposed reference and our work basically use different wavelet construction, and we will discuss it in the Related work section. "}, {"review_id": "b5OXETJXO9", "reviewer": "Reviewer_nurq", "summary": "In this work the authors tackle the problem of graph generation learning where the goal is to learn the key features of a set of graphs and be able to generate graphs with similar properties. To that extend, the authors extend the GDSS (Jo 2022) method through an additional loss term (Eq. 7). This loss term encourages the employed GNNs to learn to reconstruct spectrally modified matrices A^s_i in addition to the normal adjacency matrices. The spectrally modified matrices are obtained through an SVD/PCA like approach where some spectral properties of the adjacency matrix are accentuated. This spectral accentuation is learnable as part of the training procedure.\nThe authors evaluate their approach on two real world and two synthetic datasets also used in previous studies. In terms of MMD (Mean maximum deviation) their approach frequently outperforms other methods employed for the task of graph generation learning. On molecule data, the employed procedure still ranks amount the best.\n", "questions": "It would be interesting to see which scales lambda (as in lines 219, 220) have actually been obtained from the training. Do they differ significantly for different datasets? Would an equidistant choice of lambda be sufficient?\nSimilarly it would be interesting to see the relative strengths of the lambda_A/ lambda_A^{s_i} (as in eq.7). From a theoretical perspective (thinking of spectral clustering) one would assume that mostly low frequency modes are relevant for the community dataset, is that really the case?\nLastly, it would be interesting to see whether the performance increase obtained from the spectrally filtered adjacency matrix is any better than just introducing A^{s_i}", "limitations": "see questions above", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The authors provide an interesting extension to an existing approach (GDSS), which allows to better learn the scales that are important for a specific set of graphs. The greatly increased stability during training compared to GDSS (Figure 3) seems promising. The paper contains extensive comparison to other methods. The presented approach is on par/outperforms these other methods on the presented datasets. Most computational overhead is in the training phase, inference is as fast as GDSS.", "weaknesses": "Overall the core weakness of the paper is its presentation, which has a lot of room for improvements and weak support for the main claims of the paper (last point).\n\nThe presentation of the SDE learning (lines 155-179) is not understandable without reading the GDSS paper. I think it could be drastically improved by highlighting the differences/ improvements in comparison to GDSS rather than repeating all the definitions/equations.\n\nThe description of Figure 2a) could be much improved as it is not well understandable without reading the rest of the paper first.\n\nSome of the equations and notation does not further the main cause of the paper: Section 3.1 beyond the first paragraph can almost entirely be cut. The introduced transformation $X^{s_i}$ on the edge signal X is not really used.\n\nLemma 1 seems to be misplaced as it introduced (lines 138ff) quite far away from where it is used (lines 190ff). Also it seems Lemma 1 is likely not a new result.\n\nThe bold highlights in Table 1 are not correct, in column “orbit”, three other methods outperform the presented approach but are not highlighted in bold. Also in lines 289f the text mismatches the table.\n\nIt is also unclear from the text how much hyperparameter tuning was done to achieve the results presented.\n\nLast but not least, the experimental section shows, from an applicant's point of view, that the proposed changes lead to empirical performance increase on the graph generation task. On the other hand the experimental section does not well support whether the introduced changes actually had the desired effect of learning different “scales” better. \n\nIt might as well be, that the introduced changes simply increase training robustness. More on this in the “Questions” section. It seems that one would need additional support for the main claim.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "W1) Improve clarity on SDE learning, Fig. 2a, Sec 3.1, Lemma 1, and Tab. 1.\n\nA) We thank the reviewer for the detailed constructive comments. \nWe presented a revised version of Fig. 2a with its improved description in the pdf of the general response, so please check on it. We will also clarify all other places based on the reviewer’s suggestions, such as highlighting the difference between our method and GDSS by adding the description of the loss in Eq. 7 and modifying the bolds in Table 1 in the revision. \n\nSpecifically, we will add the following descriptions in line 180, before the Remark section: “Both our method and GDSS perform denoising score-matching to the partial scores of $X$ and $A$. However, our method additionally models the joint probability space of $X$ and $A^s$ via SDEs. This is realized by the loss in Eq. (7), and this operation allows a model to flexibly estimate the complex dependency between nodes and edges with multi-resolution SGWT. Also, note that the scales of SWGT {$s_i$}$_{i=1}^J$ in Eq. (7) are trainable so that multi-level granularities that characterize graph distribution can be adaptively captured during training.”.\n\nFor the $X^s$ in Sec 3.2, it is not used in our method, however, it can be used by replacing $A^sX$ with $AX^s$. As shown in the proof of Lemma 1 in the supplementary material, $W_{A}(s) \\cdot W_{X}(s) = AUk^2(s\\Lambda)U^TX = A^sX = AX^s$. Therefore, either $A^sX$ or $AX^s$ can be used to capture the spectral coherence between node features and graph structures. We will add this explanation to the revised manuscript for better understanding.\n\nW2) Lemma 1 is likely not a new result.\n\nA) To our best knowledge, Lemma 1 and its proof are novel ideas as it proposes that computing the coherence as a dot product of multi-resolution nodes and edges in the spectral space is equivalent to a graph convolution in the original graph space. Please let us know of any references that suggested the same idea so that we can properly credit them. \n\nW3) How much hyperparameter tuning was done?\n\nA) Basically, we followed most hyperparameter settings of GDSS as Wave-GD is built upon the GDSS. The hyperparameter we mainly tried out was learning rate and $J$, i.e., the number of scales. As we used two wavelet filters (i.e., low-pass and band-pass filters), we conducted experiments with at least two scales ($J=2$). Subsequently, we increased $J$ by 1 for the band-pass filter until the optimal results were achieved. For the Grid dataset, the maximum $J$ we could try was $6$ due to computational limitations. We provided ablation studies on $J$ in Table 4 in the main paper and Section 4 in the supplementary material for all datasets. While the optimal $J$ may be different across different datasets, the results within each dataset are not very sensitive but rather robust to the choice of $J$. For the learning rate, we performed a grid search in {$0.0008, 0.001, 0.002, 0.005, 0.01$} for each dataset.\n\nW4/Q1) Which scales were obtained? The values should be presented in the experimental section.\n\nA) In the pdf of the global response, we reported the table of converged scale values. We will add the table in the revised paper. \n\nIn Section 7 of the supplementary material, we provided all scale convergence flows along epochs and analyzed the converged scale ranges for generic graph datasets. We observed that the scales differ for different datasets. Interestingly, the scales of the large Grid dataset (with $100  \\leq |V| \\leq 400$ nodes) were generally smaller compared to the Ego-small ($4 \\leq |V| \\leq18$) and Community-small ($12 \\leq |V| \\leq 20$) datasets. Specifically, the converged scales of Ego-small ranged within $[20, 47]$ and the scales of Grid ranged within $[12, 36]$. Note that the smaller scales capture local graph features with higher frequencies. Therefore, the results demonstrate that capturing local and detailed graph representations is more critical when dealing with complex and large graphs, in comparison to smaller graphs. In other words, for the Community-small dataset, features in relatively low frequency (e.g., cluster-related features) were captured with larger scales.\n\nQ2) Relative strength of lambda in Eq. 7.\n\nA) $\\lambda$'s in Eq. 7 were set to 1 so the relative strength between $A$ and $A^{s}$ were the same. \n\nQ3) Performance comparison between spectrally filtered adjacency matrix and $A^{s_i}$.\n\nA) The use of spectrally filtered adjacency matrix (i.e., wavelet coefficient $W_{A}(s)=\\psi_s \\cdot \\mathbf{A}$) with spectrally filtered node features (i.e., $W_{X}(s)$) will make the same result as using $A^s$ and $X$. As shown in the proof of Lemma 1 in the supplementary material, $W_{A}(s) \\cdot W_{X}(s) = A^{s}X$, and therefore the result of using either side of the data will be equivalent. \n"}, {"review_id": "Ta58nLI5Ng", "reviewer": "Reviewer_ZNjR", "summary": "This paper proposes Wave-GD, a score-based generative model, to generate graphs with high fidelity. By capturing the dependency between nodes and edges at multiple resolutions in the spectral space, it claims it overcomes the over-smoothing problem and achieves real-like frequency characteristics of nodes and edges.", "questions": "Please address the weakness above and:\n\n1. How exactly can the SGWT addresses the over-smoothing problem?\n\n2. Can you give a concrete example why it can capture \"multi-resolution\" of the graph, and can you provide a formal definition of the multi-resolution.\n\n3. what's the motivation of conducting the experiment with larger sample size?", "limitations": "1. The result on molecule generation is not that expressive.\n\n2. The contribution may be insignificant: there are many GNN design that may alleviate the over-smoothing problem. Any baseline model with a better score networks may overcome this limitation easily. ", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well-written and easy to follow.\n2. The paper's motivation is clear, and the paper has shown some limitations that previous models may have.\n3. The idea of the paper is simple and straightforward.", "weaknesses": "1. The experiment is not sufficient to support the proposed method.\n\n(1) lack of baselines: some baselines that utilize spectral information/graph characteristics are missing. It would be great to see the author compare them.[1,2,3]\n\n(2) lack of more robust graph datasets: Ego-small and Community-small graphs are too simple, I think over-smoothing can't be a major issue for graphs in such scales. And how the \"multi-resolution\" should be defined in such small graphs? I suggest the authors run experiments on more complex graphs such as Planar graphs, SBM graphs, and large networks if possible with hundreds of nodes. \n\n(3) I suggest the author also include DiGress in Figure 5 -- since it also utilizes spectral information.\n\n(4) Another comment in Figure 5: it's not clear whether the performance drop when increasing #GNN layers is really due to the over-smoothing problem, more investigation should be conduct to further prove this phenomenom. \n\n2. While the author propose to also diffuse on the edge weights obtained from SGWT, there are also other ways to define the edge importance (e.g., edge conductance). Justiifcation should be provided why SGWT is the chosen over others.\n\n[1] Luo, Tianze, Zhanfeng Mo, and Sinno Jialin Pan. \"Fast Graph Generative Model via Spectral Diffusion.\" arXiv preprint arXiv:2211.08892 (2022).\n\n[2] Martinkus, Karolis, et al. \"Spectre: Spectral conditioning helps to overcome the expressivity limits of one-shot graph generators.\" International Conference on Machine Learning. PMLR, 2022.\n\n[3] Chen, Xiaohui, et al. \"Efficient and Degree-Guided Graph Generation via Discrete Diffusion Modeling.\" arXiv preprint arXiv:2305.04111 (2023).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "W1) Compare with more baselines.\n\nA) We thank the reviewer for introducing great references. We compared Wave-GD with Martinkus et al (ICML 2022) and Chen et al (ICML 2023) and reported the results in the pdf of the global response. As shown in the result, our method outperformed both baselines in three datasets. We will add these results in the revision and discuss their methods.\n\nW2) Compare with additional datasets with larger graphs.\n\nA) As suggested by the reviewer, we conducted an experiment on the Planar data and presented both qualitative and quantitative results in the global response. We compared MMDs of test and generated graph sets on degree, clustering coefficients, and orbit counts. Our method outperformed five baselines including SPECTRE and EDGE for the average of three MMDs. \nThe resultant optimal scales for the Planar dataset were also reported in the general response, which shows that their optimal scales are relatively smaller than other generic graph datasets. These results indicate that capturing high-frequency and localized features from individual nodes was more informative than capturing cluster-related features in this dataset. \n\nNote that we rushed these experiments with limited time and resources, and hyperparameters such as learning rate and $J$ were not fine-tuned. But still, we obtained the results of Wave-GD outperforming many recent baselines. Regarding SBM dataset, we were not able to pull reportable results given limited time but confirmed them to be promising. We plan to prepare a journal version and these additional experiments in more complete form will be included there.\n\nW3) Include DiGress in Figure 5. \n\nA) We thank the reviewer for the suggestion. However, in Figure 5, we compared our method with GDSS for multiple Graph Multi-Head attention (GMH) layers to observe robustness against oversmoothing caused by repetitive graph convolutions (within the GMH layers). As DiGress does not use graph convolutions nor GMH layers, we cannot directly compare our method with DiGress to examine its performance against oversmoothing problem, we believe that the reviewer will easily see why DiGress cannot be compared directly within Figure 5. \n\nW4/Q1) It is not clear that the performance drop in Figure 5 is caused by the increase in the number of GNN layers. How can the SGWT address the over-smoothing problem?\n\nA) The performance drop in Figure 5 is caused by repetitive graph convolutions with increasing GMH layers. As shown in lines 190-192, the query, key, and values in the GMH layer were made up of graph convolutions, which aggregate features from neighboring nodes. Many previous literatures [1, 2] have shown that repetitive graph convolutions with multiple layers cause the oversmoothing problem.\n\nBoth our method and GDSS used GMH layers and graph convolutions, however, SWGT in our method allows a model to flexibly preserve discriminative characteristics of graph representations. This is because filtered eigenvalues $k(s\\Lambda)$ and corresponding eigenvectors restrict the extent of message propagation and preserve the unique characteristics of localized signals. This spectral filtering with limited eigenvectors/eigenvalues prevents the over-smoothing issue in deep layers compared to using unfiltered raw data.\n\nWe conducted an empirical analysis to support this claim by comparing Mean Average Distance (MAD) [1] between $AX$ and $A^sX$, where the MAD is a metric to measure the smoothness of the graph representation. Given a template graph shown in Fig. 1a in the main paper, $X_{i+1} = AX_{i}$ (i=0,1,2) was calculated as in 3-layer graph convolution (without weights), where the $X_0$ is a one-hot encoded degree matrix. The MAD value of $AX_3$ was 0.079 and that of $A^sX_3$ with s=20 was 0.724, which is 9 times larger. The low MAD value without SGWT represents that the node representations become indistinguishable, and the higher MAD with SGWT shows that the local and discriminative features were preserved.\n\nQ2) Provide an example and definition of multi-resolution.\n\nA) The multi-resolution is a hierarchical concept [3] to capture information of data at varying levels of granularity. This multi-resolution is well-established with Wavelet transform (Mallat, 1999) and Spectral Graph Wavelet Transform (Hammonds, 2012) extends its concept to graphs as which is utilized in our framework. Basically, it is the band-pass filter $k(s)$ which covers different bands, i.e., scales, in the frequency space. Given a signal $x$, controlling $s$ in Eq (1) and (2) in the main paper yields the representation of $x$ in different resolutions. We will clarify these in the preliminary section of our revision.   \nFor empirical evaluation, in Sec. 7 of supplementary material and the general response, we provided the value of the actual converged scales for generic graph datasets for our experiments, which show the capability of Wave-GD to capture different multi-resolution graph representations considering the characteristics of datasets. \n\nQ3) What is the motivation for the experiment with larger samples?\n\nA) As in EDP-GNN [4] and GDSS [5], we performed the experiment with more samples to extensively assess the quality of generated samples. With more data, the larger sample set may contain more abnormalities or high-fidelity samples. Therefore, the experiment aims to assess how the quality of generated samples changes with greater diversity.\n\n[1] Chen et al. \"Measuring and relieving the over-smoothing problem for graph neural networks from the topological view.\" AAAI. 2020.\n\n[2] Zhao and Akoglu. \"Pairnorm: Tackling oversmoothing in GNNs.\" ICLR, 2020.\n\n[3] Rosenfeld, “Multiresolution image processing and analysis.” Springer Science & Business Media, 2013.\n\n[4] Niu et al. “Permutation invariant graph generation via score-based generative modeling.” AISTATS, 2020 \n\n[5] Jo et al. “Score-based generative modeling of graphs via the system of stochastic differential equations.” ICML, 2022"}]

Author rebuttal:
We thank all reviewers for their constructive reviews with anonymously positive evaluations.

In the pdf of the general response, we present $\bf{1) }$ A revised version of Fig. 2a and its description, $\bf{2) }$ an analysis on the computational time of eigendecomposition, $\bf{3) }$ optimal scale values after training, $\bf{4) }$ comparison with additional baselines, and $\bf{5) }$ comparison with an additional dataset.


Meta-review: The paper proposes a new method for diffusion-based graph generation, by using graph wavelet bases to separate predictions of different frequency ranges, thereby overcoming some of the oversmoothing issues of existing methods. Reviewers were generally aligned and found the paper interesting and novel.
Decision: Accept (poster)