SwinGNN: Rethinking Permutation Invariance in Diffusion Models for Graph Generation
Authors: Qi Yan
Zhengyang Liang
Yang Song
Renjie Liao
Lele Wang
Venue: Accepted by TMLR ()

Abstract: Permutation-invariant diffusion models of graphs achieve the invariant sampling and invariant loss functions by restricting architecture designs, which often sacrifice empirical performances. In this work, we first show that the performance degradation may also be contributed by the increasing modes of target distributions brought by invariant architectures since 1) the optimal one-step denoising scores are score functions of Gaussian mixtures models (GMMs) whose components center on these modes and 2) learning the scores of GMMs with more components is often harder. Motivated by the analysis, we propose SwinGNN along with a simple yet provable trick that enables permutation-invariant sampling. It benefits from more flexible (non-invariant) architecture designs and permutation-invariant sampling. We further design an efficient 2-WL message passing network using the shifted-window self-attention. Extensive experiments on synthetic and real-world protein and molecule datasets show that SwinGNN outperforms existing methods by a substantial margin on most metrics. Our code is released at https://github.com/qiyan98/SwinGNN.

Published in Transactions on Machine Learning Research (06/2024)
SwinGNN: Rethinking Permutation Invariance in Diffusion Models for Graph Generation
Qi Yan University of British Columbia Vector Institute for Al
qu. ga.yaneee..uee ubc.ca
Zhengyang Liang
marzas@tonngii.ddue
Tongji University
Yang Song* OpenAl
congyang@openai..oommm
Renjic Liao
rjliaoßece, ubc.
University of British Columbia
Vector Institute for Al
Canada CIFAR AI Chair
Lele Wang
lelewang@ece.udee wuc.eeeee.bbb.... ubc.ca
University of British Columbia
Reviewed on OpenReview: opwneevee.......... net/ forum? id- abft5plv04
Abstract
Permutation-invariian diffusion models of graphs achieve the invariant sampling and in- variant loss functions restricting architecture designs, which often sacrifice empirical performances. In this work, we first show that the performance degradation may also be contributed by the increasing modes of target distributions brought by invariant architec- lures since 1) the optimal one-step denoising scores are score functions of Gaussian mix- tures models (GMMs) whose components center on these modes and 2) learning the scores of GMMs with more components often harder. Motivated by the analysis, we propose SWinGNN along with a simple yet provable trick that enables permutation-invariaan sam- pling. It benefits from more flexible (non-invariant) architecture designs and permutation- invariant sampling. We further design efficient 2-WL message passing network using the shifted-windd self-attention. Extensive experiments on synthetic and real-world protein and molecule datasets show that SwinGNN oulperforms existing methods by a substantial margin on most metrics. Our code is released at stttps://iihuut cow Saamm/iyaan//Svinnt
1 INTRODUCTION
Diffusion models (Sohl-Dickstein et al. 2015 Ho et al. 2020; Song et al. 2021a have recently emerged powerful class of deep generative models. They generate high-dimensional data, e.g., images and videos (Dhariwal & Nichol 2021 Ho et al. 2022 at unprecedented high qualities. While originally designed for continuous data, diffusion models have inspired new models for graph generation that involves discrete data and has a wide range of applications, including molecule generation (Jin et al. 2018), code completion (Brockschmidt al.] 2019). urban planning (Chu al. 2019), scene graph generation (Suhail et al. 2021 and neural architecture search (Li et al. 2022).
* Work done Stanford.

---

Published in Transactions on Machine Learning Research (06/2024)
There exist two ways to generalize diffusion models to graphs. The first one is simply treating adjacency matrices as images and applying existing techniques built for continuous data. The only additional challenge compared to image generation is that a desirable probability distribution over graphs should be invariant to the permutation of nodes. Niu et al. (2200) Jo et al. (2022) construct permutation equivariant scoro-basod models that induce permutation invariant distributions. Post-hoc thresholding is needed to convert sampled continuous adjacency matrices to binary oncs. The other one relies on the recently proposed discrete diffusion models (Austin et al. 2021) that naturally operate on binary adjacency matrices with discrete transitions. Vignac et al. (2023) shows that such models learn permutation invariant graph distributions by construction and achieve impressive results on molecule generation.
In this paper, we first clarify two key concepts of permutation invariance: invariant training losses and invari- ant sampling. For practical applications, graph generative models should ideally have an invariant sampling process, ensuring generated graphs that are isomorphic have equal likelihoods regardless of node orders. Pre- vious works achieve this goal by using invariant diffusion models trained with invariant losses. However, such invariant models often achieve worse empirical performances than their non-invariant counterparts. This is likely due to 1) invariant models have more restrictive architecture designs and 2) their target distributions having more modes. Specifically, since the optimal one-step denoising scores are score functions of Gaussian mixtures models (GMMs) whose components center on these modes, learning the scores of GMMs with more components is often harder. Importantly, while an invariant loss is sufficient, it is not necessary for invariant sampling. We present a simple technique of randomly permuting generated graphs that provably enables any graph generative model to achieve permutation-invaria invariant sampling.
Motivated by the analysis, we propose non-invariant diffusion model, called SwinGNN, to embrace more powerful architecture designs while still maintaining permutation-invarianl sampling. Inspired by the ex- pressive 2-WL graph neural networks (GNNs) (Morris et al., 2021] and Swin Transforrrss (Liu et al. 2021). our SwinGNN performs efficient edge-to-edge 2-WL message passing via shifted window based self- self-attention mechanism and customized graph downsampling/ huaaii/pggppappingggggg. operators, thus being scalable to generate large graphs (e.g., over 500 nodes). Note that diiretlly applying 2-WL GNNs would have siguificantly higher com- putational costs whereas directly applying Twinfransformrss would lead to worse performances since they are essentially 1-WL GNNs. Our model aligns with the rationale of k-order GNN (Maron et al.. 2019b) k-WL GNN (Morris et al. 2019), enhancing network expressivity by utilizing k-tuples of nodes (k- = 2 in case). Further, we thoroughly investigate the recent. advances of diffusson models for image (Karras et al.
2022 Song & Ermon 2020) and identify several techniques that significantly improve the sample quality of graph generation. Extensive experiments on synthetic and real-world molecule and protein datasets show that our SwinGNN achieves stale-of-the-art performances, surpassing the existing models by several orders of magnitude in most metrics.
2 RELATED WORK
Generative models of graphs (a.k.a., random graph models) have been studied in mathematics, network science, and other subjects for decades since the seminal Erdós Rényi model (Erdös & Rényi 1959). Most of these models, e.g., Watts Strogatz model (Watts & Strogatz 1998) and Barabási Albert model (Albert & Barabási 2002), are mathematically tractable, i.e., one can rigorously analyze their propertics such as degree distribut ions. In the context of deep learning, deep generative models for graphs (Liao] 2022) prioritize fitting complex distributions of real-world graphs over obtaining tractable propertics and have achieved impressive performances. They can be broadly classified based on the generative modeling techniques.
The first class of methods relies on diffusion models (Sohl-Dickstein et al. 2015 Ho et al. 2020 that achieve great successes in image and video generation. We focus on continuous diffusion graph generative models which treat the adjacency matrices as images. (Niu et al. 2020) proposes a permutation-innariall score- matching objective along with a GNN architecture for generating binary adjacency matrices by thresholding continuous matrices. Jo et al. (2022 extends this approach to handle node and edge attributcs via stochastic differential equation framework (Song et al. (2221b). Following this line of research, we investigate the limiting factors of these models and propose our improvements that achieve state-of-the-art performances.
2

---

Published in Transactions on Machine Learning Research (06/2024)
PAR
PLAF
RAR
PAA
Pdata (Aa)
Pdato A4)
Fasts 1/6
Pdata (Aa) 1/6
PMF
PLAI
PMF
Pdasa (Ag)
Pastal (Aa)
Placa (Aa) 1/6
1/6
Pasta 1/6
A. A; A4
A. As A. Ac
PLAR
BAA
PLAR
P.AR
Pdata A1)
Pricta (Ag)
P 1/6
Paasa (
1/6
Empirical Data Distribution Pdata
Invariant Effective Target Distribution Pdata
Figure 1: Data distribution and target distribution for a 3-node tree graph. For permutation matrix P. and adjacency matrix A,, filled/blan cells mean one/zero. The probability mass function (PMF) highlights the difference modes. Our example also shows graph automorphism (e.g., Pi and P2).
Besides continuous diffusion, discrete diffusion based graph generalive models also emerged recently. Vignac et al. (2023) proposes permutation-ing invarninnvvannttttt model based on discrete diffusion models (Austin et al. 2021 Hoogeboom ct al. 2021 Johnson et al., 2021). For the discrete graph data, e.g., binary adjacency matrices or categorical node and edge attributes, discrete diffusion is more intuitive than the continuous counterpart.
Apart from the above diffusion based models, there also exist models based on generative adversarial networks (GANs) (De Cao & Kipl 20188
Krawezuk et al.) 2021 Martinkus et al.
2022).
variational auto-encoders
(VAEs) Kippf & Welling 2016
Simonovsky & Komodakis 2018
Jin et al.
2018
Vignac & Frossard 2022
normalizing flows (Liu et al. 2019
Madhawa et al. 2019 Lippe & Gavves
2021
Luo et al. 2021 and
autoregressive models (You et al. 2018 Liao et al. 2019 Mercado et al.) 2021
Among them, autoregressive
based models enjoy the best empirical performance, although they are not invariant to permutations.
Recently, Han 2023
propose modeling the graph distribution by summing over the isomorphism class of adjacency matrices with autoregressive models, where graph 9 with an adjacency matrix A of n nodes admits probability of
p(g) Σ p(A.),
(1)
ALEZA
where ZA is the isomorphism class of with a size up to O(n)).
3 PRELIMINARIES
Notation. A graph g = (V,E) comprises node set V with n nodes V= set E E V V. We focus on simple graphs, i.e., unweighted and undirected graphs without self-loops multiple e Such graph can be represented by an adjacency matrix A E 10,1 where node ordering implies the matrix's row/column order. A permutation matrix Px,+,, denotes bijection between two node orderings TI, π2, i.e., T P Am PT P
and an edge
We omit the node ordering notations for simplicity. Let Sn be all n! permutation matrices of n nodes. Any P E S, that maps A to itself, ie., A = PAPT denotes a graph antomorphism of A. Two graphs G1, G2 with adjacency matrices A1, A2 are isomorphic and only if there exists E S, such that PA, = Aq. The isomorphism class of A, denoted by IA (PAPT P E S,), is the set of adjacency matrices isomorphic to A. We obscrve { mL Pdats (A), drawn from the unknown data distribution of graphs (data(A).
i.i.d. samples,
Weighted graphs (i.c., real-valued adjacency matrices) casier to baudle for contimuous diffusion models since the thresh- olding step is unnecessary. Our model also extends multigraphs with node and edge attributes (e.g., molecules), detailed further in the experiment section and App.
3

---

Published in Transactions on Machine Learning Research (06/2024)
Graph generative models aim to learn a distribution po (A) that closely approximates Pdata(A), Denoising Diffusion Models. A denoising diffusion model consists of two parts: (1) forward contimuous--tatee Markov chain that gradually adds noise to observed data until it becomes standard normal noise and (2) a backward continuous-state Markov chain (learnable) that gradually denoises from the standard normal noise until becomes observed data. The transition probability of the backward chain is typically parameterized by a deep neural network. Two consocutive transitions in the forward (backward) chain correspond to two noise levels that are increasing (decreasing). One can have discrete-time (finite noise levels) (Ho et al. 2020) continuous-timg (infinite noise levels) (Song et al., 2021b) denoising diffusion models.
In the context of graphs, if we treat an adjacency matrix A as image, it is straightforward to apply these models. In particular, considering one noise level o, the loss of denoising diffusson models is
E (d (A)p (Ā [IIoo(A,o) - A
(2)
where Do(A, is the denoising network, Ā is the noisy data (graph), and ||. ||e is the Frobenius norm. The forward transition probability is a Gaussian distribution pa (AlA) = Ni A, Note that we add ii.d clement-wise Gaussian noise to the adjacency matrix. Based on the Twoodic's formula (Efron 2011 one can derive the optimal denoiser Dg- (A,o) = Å V Po (A), where the noisy data distribution Po (Á) = Paata(A)po (A) (ÁlA) appears.
Scoro-based Models. Scoro-based models aim to learn the score function (the gradicnt of the log density w.r.t. data) of the data distribution Pdata(A,, denoted by 8( s(A) == V log Pdata (A). Since Pdata (A) is unknown, one needs to leverage techniques such as denoising score matching (DSM) (Vincent 2011] to train
a score cstimation network 8g. Similar to diffusion models, we add i.i.d. element-wise Gaussian noise to data, i.e., Po (AlA) = (Ā; A, II... For a single noise level 0, the DSM loss is
E Pansa (A (A,0(AA)))))) V lo (A
(3)
where V log lo a= Minimizing Eq. (3) almost surely leads to optimal score network 8g- (Á,
that matches the score of the noisy data distribution, i.e., sg- (A, 0) V Á log Pa (A) (Vincent 2011
Further, the denoising diffusion models and score- based models are essentially the same (Song et al.) 2021b
The optimal denoiser of Eq. [2) and the optimal score estimator of Eq. (3) are inherently connected by
Dg. (À = Ā + o² oz (Ā, We use both terms interchangeably in what follows.
DSM Estimates the Score of GMMs. Our training set consists of i.i.d. samples (adjacency matrices) {A,) 1=1- The corresponding empirical data distribution? is a mixture of Dirac delta. distributions, i.e.,
Pdata (A) = Em 8,)-A,) from which we can get the closed-form of the empirical noisy data distribution is an m-component GMM with uniform weights, and the DSM objective in Eq. 3 learns its score function.
(A) = 1 Σ m AiA 02) (A)
4 PERMUTATION INVARIANT LOSS AND SAMPLING
Existing models employ permutation invariant losses to attain permutation invariant sampling, a feature essential for real-world applications. However, we demonstrate that permutation invariant losses lead to degraded empirical performances. Alternatively, we introduce a simple yet provable technique to ensure invariant sampling without requiring an invariant loss, fostering flexibility in model architecture design and inspiring our non-invariant method.
4.1 Challenges of Permutation Invariant Loss
Theoretical Analysis. As shown in Fig. 1 the empirical graph distribution (A) may only assign a non-zero probability to a single observed adjacency matrix its isomorphism class. The ultimate goal of graph generative model is to match this empirical distribution, which may be biased by the observed
2Wth slight abuse of notation, refer to both the data distribution and its empirical version Pdata since the data distribution is unknown and will not be often used.
4

---

Published in Transactions on Machine Learning Research (06/2024)
1.0
0.8
SwinGNN (ours, non invarriii)
PE+PPGN (non invariant)
Recall
PPGN (invariant)
0.6
DiGress (invariant)
0.4
0.2
1
100
200
300
4000
Number of permutations (7)
Figure 2: Invariant models perform significantly worse than non invariant models when the number of applied permutations (l) is small.
permutation. However, the target distribution that generative models are trained to match may differ from the empirical one, dependent on the model design w..tt. permutation symmetry. For clarity, we define the effective target distribution the closest distribution (e-g., measured in total variation distance) to the empirical data distribution achievable by the generative model, assuming sufficient data and model capacity.
Previous works [Niu et al. 2020 Xu et al. 2022 Hoogeboom et al. 2022) learn permutation invariant models (A( with permutation invariant losses via equivariant networks. We argue the induced invariant effective target distributions are hard to learn. Let the training set only contain one graph A1, e.g., in Fig. D Even if we optimize the invariant model distribution po (A) lowards the empirical one Panta (A) to the optimum, they can never exactly match. This because if it does (i.e., Pdata A1) = pe A1) 1), pp(A) will also assign the same probability to isomorphic graphs of A due to permutation invariance, thus violating the probability sum-to-one rule. Instead, the optimal (a(A) (f.e., the effective target distribution) will assign equal probability 1/|ZA, to isomorphic graphs of A
Formally, given a training set of adjacency matrices ) one can construct the union set of each graph's isomorphism class, denoted as .A' = , Z EArEA- 8(A A"), where be always achievable due graph automorphism.
IA.- The corresponding mixture distribution Piaca (A) == |A"| = ((Im) the normalizing constant. Note that Z nlm may not
Lemma 4.1. Assume at least one training graph has Mn!! distinct adjacency matrices in its isomorphism class. Let P denote all discrete permutation invariant distributions. The closest distributions in P to Pdlsa, measured by lotal varialion, have al least M(n!) modes. If, in addition, restricl P to be the sel of permutation invariant distributions such that p(A,) p(A,) > 0 for all matrices in the training set {Ar] then the closest distribution is given by arg minger TV (4, Pdata) = Pasta
Under mild conditions, Pāata (A) of O(n!)) modes becomes the effective target distribution, which is the case of prior invariant models using equivariant networks for invariant losses (see App. A for details). contrast, we employ oouvvuuivaraant network (i.e., the underlying training objective is not invariant), the effective target distribution would be (Aata()) which only has 0(m) modes. Moreover, the modes of the Dirac delta target distributions dictate the components of the GMMs in the diffusion models, with each component precisely centered on a larget mode. With the invariant loss, the GMMs have the form of (A) = Σ E ((Ā, o21 with an O(n!) factor more components than the non-invariant loss (detailed in App. A.3). Arguably, learning with permutation invariant loss much harder than non- invariant one, implied by the O(n!)-factor surge in modes of target distribution and components of GMMs.
5

---

Published in Transactions on Machine Learning Research (06/2024)
Empirical Investigation. We typically observe one adjacency matrix from its isomorphism class in training data {A, By applying permutation n! times, one can construct Pdata from Pdata We define a trade-off between them, called the l-permuted empirical distribution: Paata(A) == ml E 5(A P,A.P,). where PI...., Pi are 1 distinct permutation matrices. Paata has O(1m) modes governed by l. With proper permutation matrices, Paata = Pdata when / = and Pdata ~ Pdata when = n!. To study the impact of the mode count the effective target distribution on empirical perlormance, we use Paata as the diffusion model's target by tuning 1. An equivariant network matches the invariant target Pdata: having (n!m) modes when / = n!. For I nt,, one must use non-equivariant network to learn a non-invariant training objective.
To assess empirical performance, we conduct experiments with 16 nodes and degrees in [2, 11]. The value of I ranges from 1 to 500 and we ensure training is converged for all models. We use two invariant models as baselines for learning Paata: DiGress (Vignac et al. 2023) and PPGN (Maron et al. 2019a). with PPGN being notably expressive as a 3WL-discriminative GNN. For non-invariant models matching Palta with I < n!, we add index-based positional embedding to PPGN and compare it with our SwinGNN model (dctailed in Sec. 5.1 Please see App. B.1 for more details.
toy dataset of 10 random regular graphs, each
We use recall as the metric, which is defined by the proportion of generated graphs that isomorphic to any training graph and ranges between 0 and 1. The recall requires isomorphism testing and is invariant to permutation, which is fair for all models. A higher recall indicates strong capacity to capture the toy data distribution. In Fig. 2 invariant models, regardless of using discrete (DiGress) or continuous (PPGN) Markov chains in the diffusion processes, fail to achieve high recall. Conversely, non-invariant models perform exceptionally well when is small and the target distributions have modest imposed permutations. As goes up, the sample quality of non-invariant models drops significantly, indicating the learning difficulties incurred by more modes"] Notably, in practical applications of non-invariant models, one typically chooses I = 1, often resulting in empirically stronger performance compared to invariant counterparts.
4.2 Technique to Reclaim Invariant Sampling
While non-invariant models show stronger performances empirically, they cannot guarantee permutation- invariant sampling. We present the following lemma to restore the invariant sampling.
Lemma 4.2. Let A be random adjacency matrix distributed according to any graph distribution on n vertices. Let P, ~ Unif(S,) be uniform over the set of permutation matrices. Then, the induced distribuution of the random malria A, = P.AP,,, denoled as go (Ar),, permeulation invariant, i.e., (o(A)) (PA,, Y. S,.
This trick is applicable to all types of generative models. Note that the random permutation does not go beyond the isomorphism class. Although go is provably invariant, il captures the same amount of isomorphism classes as pe. Graphs generated from qe must have isomorphic counterparts that pe could generate. Thus far, we have uncoverod two insights into permutation invariance in graph generative modcls: 1) invariant loss ensures invariant sampling but may impair empirical performances, and 2) invariant loss is not a prerequisite for invariant sampling. These insights prompt rethinking the prevailing design of invariant models using invariant losses. Aiming to accurately capture the complex real-world graph distributions while preserving sampling invariance, we introduce a novel diffusion model, integrating non son-invariant loss with the invariant sampling technique in Lemma 4.2
5
METHOD
5.1
Efficient High-order Graph Transformer
A continuous denoising network for graph data takes noisy adjacency matrix Á and its noise level input and outputs denoised adjacency matrix. However, unlike in typical graph representation learning, our model carries out edge regression without clear graph topology (i.e., no sparse binary adjacency matrices).
They are identical without non-trivial automorphisms.
4 SSampl complexity analysis for non-invariant, models provided in App. A.4
6

---

Published in Transactions on Machine Learning Research (06/2024)
NxN
N
x20
7 7"
NxX
read
down sample
SA
up sample
up sample
Layer = 20 (odd)
MLP
Upsample
4.400
Downsample
reshape
Layer 2n (even)
Input Downsample by Patch
Window Partition
TTT
Figure 3: The overall architecture of our SwinGNN.
Approximating 2-WL Message Passing. The vanilla GNNs, such as the GCN Kipf & Welling 2017] have been shown to have the same expressiveness as the 1-dimensional Weisfeiler-Leman graph isomorphism heuristic (1-WL) in terms of distinguishing non-isomorphic graphs (Xu et al. 2019). Specifically, the graphs that the 1-WL algorithm fails to distinguish are also provably difficult to handle for classical GNNs. To
address the limitations in expressiveness and performance, higher-order GNNs (Maron et al., 2019b Morris let al. 2019) have been proposed to match the theoretical capacity of the higher-dimensionall WT test, which is named k-L GNNs in contrast to the vanilla GNNs of 1-WL expressiveness: To improve model capacity, we draw inspiration from the k-order GNN (Maron et al. 2019b) and the &-WL GNN (Morris et al.) 2019 that improve network expressivity using k-tuples of nodes. The k- discrimination power characterizes the isomorphism testing ability, which proves equivalent to the function approximation capacity (Chen et al. 2019). However, applying any expressive network of k 2 is challenging in practice due to its poor scalability. In our case, we view noisy imput data Á R= as weighted cully-connected graphs with nodes, which have O(n²) k-element subsets, leading to message passing complexity of (n.2k.
To address the computation challenges of k-WL network, choose h 2 to simplify the internal order and introduce a novel graph transformer to approximate the 2-WL (i.e., edge-to-edee message passing with efficient attention mechanism. Our model, as shown in Fig. 3 treats each edge value in the input matrix as a token, apply transformers with self-attention (Vaswani et al. 2017 to update the token representations, and output final edge lokens for denoising.
Specifically, we apply window-based partitioning to confine self-attention to local representations improve efficiency. The model splits the n entries into local windows of size M x M in the grid map and computes self-attention within each window in parallel. With 2 tokens per window and some reasonable M, the self- attention complexity reduces to O(n²M²), a significant decrease from the original O(n*) in 2-WL message passing. However, this approach limits inter-window message passing, To enhance cross window interactions, we apply a shifted window technique (Liu et al. 2021). alternating between regular and shifted windows to approximate dense edge-to-odge interactions.
Although SwinGNN shares the same window allention with Swin Transformers (Liu al. 2021 they are fundamentally different. SwinGNN is specially designed to approximate the computationnally-ssae www.lsiieeeeeeivveeeeee 2- WL network, while SwinTransforme Transformers can be viewed as 1-WL GNN applied to patch-level tokens. We conduct experiments in Tab. [ Tab. 2 and App. B.6 to showcase our model's superior performances.
Swin Transformers are general- feature extraction backbones for vision tasks. They need to be cus- tomized by connecting
task-spocific prediction head, which we implement using UperNet (Xiao et al., 2018) in our baseline experiments. However, we'd like to clarify that SwinnTansformers simply treat graphs image tensors and do not account for network expressiveness.

---

Published in Transactions on Machine Learning Research (06/2024)
Multi-scale Edge Representation Learning. The window self-attention complexity Q(n2M²) is depen- dent on n², which hinders scaling for large graphs. To further reduce memory footprint and better capture long-range interaction, we apply channel taxing-based downsampling and upsampling layers to construct hicrarchical graph representations. As shown in Fig. g in the downsampling layer, we split the edge rep- resentation lensor into four half-sized tensors by index parity (odd or even) along rows and columns, make concatenation along channel dimension, and update tokens the downsized tensors independently using an MLP. The upsampling stage is carried out likewise in the opposite direction, following the skip connection that concatenates same-size token tensors along channels.
Putting things together, we propose our model, called SwinGNN, that efficiently learns edge representations via approximating 2-WL message passing.
5.2 Training and Sampling with SDE
We construct the noisy data distribution through stochastic differential equation (SDE) modeling with continuous time variable t E []. Let noise a evolve with and the noisy distribution reads as:
1 m m
(A()(()
N(AAA,
(4)
Namely, Po(o) is the Dirac delta data distribution, and Po(T) is close the pure Gaussian noise (sampling prior distribution). The general forward and reverse process SDEs (Song et al. 2021b) are defined by:
dA fa(A, f)d dtt + 9a(()
(5)
dA [fa t)dt ga(t)² logr((A)]dt + ga(t)dW,
(6)
where the dA+ and dA_ denote forward and reverse processes respectively, fa(A, [A and ga(t) are the drift and diffusion coelficients, and W is the standard Wiener process. We solve for the fa(A, () and ga(l) so that the noisy distribution in Eq. (6) satisfies Eq. and the solution is given by
f(A.t) t) 0. g() (2)(o())
which be found in Eq. (9) of Song et al. (2021b) or Eq. (6) of Karras et al. (2022).
We select the time-varying noise strength (t) to be linear with i.e., al) 1, as in Nichol & Dhariwal (2021bg Song et al. (2021a), which turns the SDEs into
dA,- = 22dW dA_ = 2 (A)) + 2tdWW
(7)
Further, we adopt network preconditioning for improved training dynamics following the Elucidating Dif- fusion Model (EDM) (Krrra et al.) 2022). First, instead of training DSM in Eq. 3 we use its equiva- lent form in Eq. [ and parameterize denoising function Do with noise dependent scaling: DA (o) + (o) Falc (o))), where F6 is the actual neural network and the other coefficients are sum- marized in App. B.4 In implementation, Dg is wrapper with preconditioning operations, and we construct F using our SwinGNN model in Sec. 5.1 Second, we sample with In(a) ~ ([Pmmcan Paa) to select noise stochastically in a broad range to draw training samples. Third, we apply the weighting coefficients ((o) = 1/),(o)² on the denoising loss to improve training stability. The overall training objective is
E. [A(o)]c.(o)AA+ (o))))((c(())A
A A
(8)
The target of Fo is A-c,(oAA
co(a) an interpolation between pure Gaussian noise A Á (when - 0) and clean sample A (when - oo). downscaled by co(o). These measures altogether case the training of F by making the network inputs and targets have unit variance.
Caad-ooniiionnng. We apply self-conditioning CCen et al. 2023 to let the diffusson model rely sample created by itself. Let Å denote the sample created by the denoiser function Dg during the reverse process,
8

---

Published in Transactions on Machine Learning Research (06/2024)
which is initialized as zero tensors and becomes available after the first sampling step. We have modified the denoising function to be Do (A, A,), allowing it to take the previously generated sample A as an additional input. In implementation, the backbone network Fo o) needs to be changed accordingly and includes a dedicated initial layer concatenate À and Á.
During training, however, we do not conduct iterative denoising sampling, and we do not have direct access to Å. Following the heuristics in Chen et al. (2023), we manage Å during training follows: given a noisy sample A, with 50% probability, we set Á to 0 (placcholder self-conditioning signal); otherwise, obtain Á by running (A, 0, to get the denoised result and then use it for celf-conditionin. Note that we only add additional information created by the diffusion model itself to the network input, and the overall training loss remains unchanged. During training, when trying to obtain Å, we disable gradient calculation (e.g., using torch. no go_grad()) ()). Therefore, the extra memory overhead is negligible for training, and, on average, half of the training steps invoke another one-step inference.
first
Algorithm 1 Sampler w. 2rd-r correction.
Require: Dg, NV [t N
1: sample (0) ~ (0, 1) A O.
2: for i= 0 to N - do
3: sample E ~ (O0 s noise I)
B Variance perturbation
4:
71
> Time perturbation
5:
Á + A00
+ 1 1.
b. Noise injection from & to &
6:
A@ < (A Al) 1t)
> Self-conditioning signal at current step Evaluate dA/dl at i Reverse process from A' to (
+ (A Al0 /1:
7:
1 < A + (t+t1 - d;
8:
# Below is -od-order correction.
(1+1) Do (A(+1), A00 li+1)
Self-conditioning for next step i + b. Evaluate dA/dl al 44+1 P Heun's integration for A correction
d' 6 (++1) Alt11) )
10:
( < A + [li+1 - (d) + d()
11:
12: end for
return (N)
13:
Stochastic Sampler with 2nd-order Correction. Our sampler is formally presented in Alg. 1 based on the 2nd-order sampler in Karras et al. 2022). Due to the nature of SDE, one can flexibly select any N sampling steps in the reverse process and their associated SDE time {4),W which are paraeersrameters of the sampler. We initialize the denoising samples A (0) from standard normal Gaussians and initialize the self colditondiio signal ( as zero tensors. In the reverse process, we always apply a perturbed variance that is slightly larger than the unit variance (I.3) inject Gaussian noise. At the i-th iteration, the sampler adds noise to A(,,, moving slightly forward along time to i,, whose distance from nominal time 4 is governed by another perturbed time & based on the denoised signal at the nominal time 4, which is obtained or initialized prior to the current sampling step. Then, we evaluate d'//dl at perturbed time l, and move the denoising sample Ā backward in time following the reverse process in Eq.
Tt is
% (L4-5). We then obtain the cellitonnii signal at L6 for the current
7 to obtain ( (L6-8). The sampler then evaluates dA/d dt at time 4+1 and corrects ((+11) using Heun's integration (Süli & Mayers 2003) on I.9-11. Note that we keep track of the generated samples 10) for model self-conditioning (L9) to save computation.
9

---

Published in Transactions on Machine Learning Research (06/2024)
Training data
GRAN
GDSS
Ours
Ego
small
Community small
Grid
Protein
(a) Sample graphs generated by different models.
QM9
ZINC
(b) Molecules generated by our models.
Figure 4: Qualitative results on plain graph and molecule datasets.
6 EXPERIMENTS
We now empirically verify the effectiveness of our model on synthetic and real-world graph datasets including molecule generation with node and edge attributes.
Experiment Setup. We consider the following synthetic and real-world graph datasets: (1) Ego-small:
200 small ego graphs from Citeseer dataset (Sen et al. 2008), (2) Commmityy-smal. 100 random graphs
generated by Erdós Rényi model (Erdös & Rényi 1959) consisting of two equal-sized communities, (3) Grid:
100 random 2D grid graphs with V E [100, 400], (4) DD protein dataset (Dobson & Doig 2003), (5) QM9
dataset (Ramakrishnan et al. 2014), (6) ZINC250k dataset [Trwin al. 2012).
For synthetic and real-world datasets (1-4), follow the same setup in Liao al. 2019 You al. (2018)
and apply random split to 80% of the graphs for training and the rest 20% for testing. In evaluation, we generate the same number of graphs as the test set to compute the maximum mean discrepancy (MMD) of statistics like node degrees, clustering coefficients, and orbit counts. To compute MMD efficiently, we follow (Liao et al. 2019 and use the total variation distance kernel.
For molecule datascts (5-6), to ensure fair comparison, we use the same pre-processing and training tosstigg set splitting as in Jo et al. (2022); Shi* et al. (2020); Luo al. (2021). We generate 10,000 molecule graphs and compare the following key metrics: (1) validity w/o correction: the proportion of valid molecules without
10

---

Published in Transactions on Machine Learning Research (06/2024)
Table Quantitative results on ego-small and community-small benchmark datasets.
Invariant Loss
Ego-Small (V) [4, 18], 200 graphs)
Community-Smal ([V) E [12, 20], 100 graphs)
Methods
Deg. +
Clus. +
Orbit.
Deg.
Clus.
Orbit. +
GRAN
X
3.40e-3
2.83e-2
1.16e-2
4.00e-3
1.44e-1
4.10e-2
EDP-GNN
1.12e-2
2.73e-2
1.12e-2
1.77e-2
7.23e-2
6,90e-3
GDSS
2.59e-2
8.91e-2
1.38e-2
3.73e-2
7.02e-2
6.60e-3
DiGress
V
1.20e-1
1.86e-1
3.48e-2
8.99e-2
1.92e-1
7.48e-1
GraphVAE-MM
X
3.45e-2
7.32e-1
6.39e-1
5.87e-2
3.56e-1
5.32e-2
SPECTRE
X
1.61e-2
1.30e-1
6.58e-3
8.65e-3
7.06e-2
8.18e-3
PPGN
V
2.37e-3
3.77e-2
4.71e-3
1.14e-2
1.74e-1
4.15e-2
PPGN+PE
X
1.21e-3
3.76e-2
4.94e-3
2.20e-3
9.37e-2
3,76e-2
SwinTFF
X
8.50e-3
4.42e-2
8,00e-3
2.70e-3
7.1le-2
1.30c-3
UNet
X
9.38e-4
2.79e-2
6.08e-3
4.29e-3
7.24e-2
8.33e-3
SwinGNN
X
3.61e-4
2.12e-2
3.58e-3
2.98e-3
5.11e-2
4.33e-3
SwinGNN-L
X
5.72e-3
3.20e-2
5.35e-3
1.42e-3
4.52e-2
6.30e-3
valency correction or edge resampling: (2) uniqueness: the proportion of unique and valid molecules; (3)
Fréchet ChemNet Distance (FCD) (rreee et al., 2018): activation difference using pretrained Chem (4) neighborhood subgraph pairwise distance kernel (NSPDK) MMD (Costa Grave 2010 graph kernel distance considering subgraph structures and node features.
Baselines. We compare method with state-of-the-art graph generative models. For non-molecule experiments, we include auloregressive model GRAN (Liao et al. 2019. VAE-base GraphVAE-MM (Zahirnia et al. 2022 and GAN-based SPECTRE (Martinkus et al. 2022) as baselines. We also compare with continuous diffusion models with permutation equivariant backbone, i.e., EDP-GNN (Niu et al. 2020) and GDSS [Jo el al. 2022), and discrete diffusion model DiGress (Vignac al. 2023). We additionally compare the PPGN networks used Sec. 4.1 Moreover, validate the effectiveness of our SwinGNN, we also compare it with recent UNet (Dhariwal & Nichol, (021)) and the vision Swin SwrinTrranffoooeSSSSviii/ employ the UperNet top of the Swin Transformer for the denoising task (refer to App. B.6 for more details). On molecule datasets, we compare with GDSS (Jo et al. 2022
(Liu
al. 2021 backbones. Specifically,
DiGress VVinncc et al. 2023), GraphAF (Shi* et al.) 2020) and GraphDF (Luo et al. 2021
We re-run all
these baselines with the same data split for a fair comparison.
Implementation Details. We try two model variants: standard SwinGNN (60-dim token) and SwinGNN-L (96-dim token), trained using exponential moving average (EMA). The same training and sampling methods are applied to UNet and SwinTF baselines described in Sec. 5.2 Different node and edge attribute encoding methods, such scalar, binary bits, and one-hot encoding, compared in molecule generation experiments. Further details are provided in App. B
6.1 Synthetic Datasets
Fig. 4a showeases samples generated by various models ego-small, community-small and grid datasets. The quality of our generated samples is high and comparable to that of auto-regressive models. Invariant diffusion models like GDSS can capture structural information for small graphs but fail on larger and more complicated graphs (e.g., grid). Quantitative maximum mean discrepancy (MMD) results on various graph statistics are presented in Tab. [ and Tab. 2 Our SwinGNN consistently outperforms the baselines across all datascts by several orders of magnitude, and can generate large graphs with around 400 nodes (grid). Our customized SwinGNN backbone notably outperforms UNet and SwinTF in most metrics, setting itself apart effective solution compared to the powerful visual learning model.
11

---

Published in Transactions on Machine Learning Research (06/2024)
Table 2: Quantitative results on grid, and protein benchmark datasets.
Invariant Loss
Grid (() E [100, 400), 100 graphs)
Protein ([V) E [100, 500], 918 graphs)
Methods
Deg.
Clus.
Orbit.
Dog. +
Clus.
Orbit. +
GRAN
X
8.23e-4
3.79e-
1.59e-3
6.40e-3
6.03e-2
2.02e-1
EDP-GNN
V
9.15e-1
3.78e-2
1.15
9.50e-1
1.63
8.37e-1
GDSS
/
3.78e-1
1.01e-2
4.42e-1
1.11
1.70
0.27
DiGress
/
9.57e-1
2.66e-2
1.03
8.31e-2
2.60e-1
1.17e-1
GM
X
5.90e-4
0.00
1.60e-3
7.95+-3
6.33e-2
9.24e-2
SPECTRE
X
OOM
OOM
OOM
OOM
OOM
OOM
PPGN
V
1.77e-1
1.47e-3
1.52e-1
0OM
OOM
OOM
PPGN-PE
X
8.48e-2
5.37e-2
7.94e-3
0OM
0OM
0OM
SW
X
2.50e-3
8.78e-5
1.25e-2
4.99e-2
1.32e-
1.56e-1
UNet
X
9.35e-6
0.00
6.91e-5
5.48--2
7.26e-2
2.71e-1
SwinGNN
X
1.91c-7
0.00
6.88c-6
1.88c-3
1.55c-2
2.54c-3
SwinGNN-L
X
2.09e-6
0.00
9.70e-7
1.19e-3
1.57e-2
8.60e-4
Table 3: Quantitalive results on QM9 and ZINC250K molecule datasels
Invariant Loss
QM9 ([V) [1,9),
131,000 molocules)
ZINC250K (IV)
[6, 38,38),
250,000 molecules)
Methods
Valid w/o cor.1
Uniquet
FCD]
NSPDK]
Valid w/o cor.
Uniquet
FCD4
NSPDK]
GruphAF
57.16
83.78
5.384
2.10s-2
68.47
99.01
16.023
4.40c-2
GraphDF
95.73
11.283
7.50e-2
41.84
93.75
40.51
3.54e-1
GDSS
90.36
94.70
2.923
4.40e-3
97.35
99.76
11,398
1.80e-2
DiGress
7.28c-4
84.94
99.21
8.75e-3
SwinGNN (scalar)
X
99.68
95.92
0.169
4.02c-4
87.74
99.98
5.219
7.52c-3
SwinGNN (bits)
X
99.91
96.29
0.142
3. 3.44-1
83.50
99.97
4.536
5.61e-3
SwinGNN (one-hot)
X
99.71
96.25
0.125
3.21e-4
81.72
99.98
5.920
6.98e-3
SwinGNN-L (scular)
X
99.88
96.46
0.123
2. 2.70c-4
93.34
99.80
2.492
3.60e-3
SwinGNN L (bits)
X
99.97
95.88
0.096
2.01e-4
90.46
99.79
2.314
2.36e-3
SwinGNN-I. L (one-hot)
X
99.92
96.02
0.100
2.04e-4
90.68
99.73
1.991
1.64e-3
6.2 Real-world Datasets
Protein Dataset. We conduct experiments on the DD protein graph dataset, which has significantly larger number of nodes (up 500) and dataset size compared to other benchmark datasets. As shown in Fig. 4a our model can generate samples visually similar to those from the training set, while previous diffusion models cannot learn the topology well. Tab. 2 demonstrates that the MMD metrics of our model surpass the baselines by several orders of magnitude.
Molecule Datasets. Our SwinGNN can be extended to generate molecule graphs with node and edge features (see App. B.3 for details). We evaluate model against baselines QM9 and ZINC250k using metrics such validity without correction, uniqueness, Fréchet ChemNet Distance (FCD) Preeer et al, 2018), and neighborhood subgraph pairwise distance kernel (NSPDK) MMD (Costa & Grave 2010). No- lably, our models exhibit substantial improvements in FCD and NSPDK metrics, surpassing the baselines by several orders of magnitude. We include the experimental results on novelty scores in App. B.8 for com- pleteness. However, we argue that novelty score may not be reliable indicator for unconditional generative models, particularly in molecule generation, where novel samples are likely to violate essential chemical principles |Vignac et. al. 2023 Vignac & Frossard 2022
12

---

Published in Transactions on Machine Learning Research (06/2024)
6.3 Ablation Study
6.3.1
Model Runtime Efficiency
Table 4: Comparison of running time using one NVIDIA RTX 3090 (24 GB) GPU.
Method
#params
Training
Inference
GDSS
0.37M
215s
113s
DiGress
18.43M
713s
205s
Unet 32.58M
1573s
795s
SwinGNN
15.31M
100s
54s
SwinGNN-L
35.91M
139s
80s
In Tab. compare the training and inference time of various methods also the grid dataset. With the maximally allowed batch size for each model, we measure the time for training 100 epochs and for generating a fixed number of samples once (equal to the testing set size). Our model operates much more efficiently than baselines handling non-downsampled dense tensors, such as GDSS or DiGress. Specifically, when compared to the DiGress with a similar number of trainable parameters, our model trains approximately 7 times faster and performs inference about 4 times faster on the grid datasct. Our model (SwinGNN-L) sustains faster training and sampling time, even with the largest parameter size. We also compare the GPU memory use in App. B.5 where our model is more memory-efficient.
6.3.2 Diffusion Model Training Techniques
Table 5: Ablations on various training techniques.
Grid (DV) E [100, 400),
100 graphs)
Model
Self-cond.
EMA
Deg.
Clus.
Orbit. +
1.82e-1
9.70e-3
2.28e-1
/
1.98e-1
9.97e-3
2.24e-1
GDSS
x
3.18c-1
1.10c-2
3.59c-1
X
x
3.78e-1
1.01e-2
4.42e-1
3.89e-1
1.23e-2
0.55
X
V
4.92e-1
1.02e-2
0.59
DiGress
X
8.73e-1
1.96c-2
0.97
X
X
9.57e-1
2.66e-2
1.03
1.91e-7
0.00
6.88e-6
V
1.14c-5
2.15c-5
1.58c-5
SwinGNN-EDA
X
5.12e-5
2.43e-5
3.38e-5
X
X
5.90e-5
2.71e-5
9.24e-5
V
2.89e-3
1.36e-4
3.70e-3
SwinGNN-DDPM
X
X
4.01e-2
8.62e-2
1.05e-1
In Tab. perform ablations on grid dataset to assess the impact of self-conditioning and EMA across GDSS, DiGress and our SwinGNN models on the grid datasct. Both tricks slightly improve the bascline models, but they still lag behind our models. Additionally, we compare the EDM (Karras el. al. 2022) framework, that incorporates SDE modeling and the objective in Eq. (8), against the vanilla DDPM (Ho et al. 2020), finding that EDM substantially improves performance. Further, we conduct comparison exporiments in App. [.6] to showcase our model's superior performance SwinTF, Discussions on the window size are available in App. B.7
13

---

Published in Transactions on Machine Learning Research (06/2024)
7 CONCLUSION
Invariant graph diffusion models trained with invariant losses face learning challenges from thcoretical and empirical aspects. On the other hand, non-invariant models, despite exhibiting strong empirical performance, struggle with invariant sampling. To overcome this, we introduce a simple random permutation technique to help reclaim invariant sampling. We propose non-invariant model SwinGNN that efficiently approximates B- message passing and can generate large graphs with high qualities. Experiments show that our model achieves state-of-the-arl performance in wide range of datasets. In the future, it promising to generalize model to the discrete diffusion framework.
Acknowledgments and Disclosure of Funding
This work was funded, in part, by NSERC DG Grants (No. RGPIN-2022-04636 and No. RGPIN-2019- 05448), the NSERC Collaborative Research and Development Grant (No. CRDPJ 543676-19), the Vec- tor Institute for AI, Canada CTFAR AT Chair, and Oracle Cloud credits. Resources used in preparing this research were provided, in part, by the Province of Ontario, the Government of Canada through the Digital Research Alliance of Canada alliance. caw.anceeca.cc.....mmmmmmm and companies sponsoring the Vector Insti- tute www. www.vectorinstitute.ee awtettteii//praaaa ai/Hpartners Advanced Research Computing at the University of British Columbia, and the Oracle for Rescarch program. Additional hardware support was provided by John R. Evans Leaders Fund CFI grant and the Digital Research Alliance of Canada under the Resource Allocation Competition award.
14

---

Published in Transactions on Machine Learning Research (06/2024)
References
Réka. Albert and Albert-László Barabási. Statistical mechanics of complex networks. Reviews of modern physics, 74(1):47, 2002.
Hassan Ashtiani, Shai Ben-David, Nicholas A. Harvey, Christopher Liaw, Abbas Mehrabian, and Yaniv Plan. Near-optimal sample complexity bounds for robust learning of gaussian mixtures via compression schemes. J. ACM, 67()), oct 2020. ISSN 0004-5411. doi: 10.1145/341794. URL https://doi.orrg/1/
1145/3417994.
Jacob Austin, Daniel D. Johnson, Jonathan Ho, Danicl Tarlow, and Rianne van den Borg. Structured denoising diffuusion models in discrete state-spaces. Advances in Neural Information Processing Systems, 2021. URL https://openrevierr htt.:///w..e...ooommiia.aaaa XixxPAAL
Marc Brockschmidt, Miltiadis Allamanis, Alexander L. Gaunt, and Oleksandr Polozov. Generative code modeling with graphs In International Conference on Learning Hepresentations, 2019. URL https:
//openreview.c http://www.e.toooommdddd-edeeee
Ting Chen, Ruixiang ZHANG, and Geoffrey Hinton. Analog bits: Generating discrete data using diffusson models with self-conditioning.. In The Eleventh International Conference Learning Representations, 2023. URL
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL httpssttst////// http:::::///oceeddnnne wtwpeeeddnnnnnnnuuune.ee www.ipuu.pp... wwwp:iipppccpppppppppppm cwtpappr_ffptteeeeeeeeee hacales/pappee Bog/fFibe/1ee1110002222001133133
.df
Hang Chu, Daiqing Li, David Acuna, Amlan Kar, Maria Shugrina, Xinkai Wei, Ming- Yu Liu, Antonio Torralba, and Sanja Fidler. Neural turtle graphics for modeling city road layouts. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), October 2019.
Fabrizio Costa and Kurt De Grave. Fast neighborhood subgraph pairwise distance kernel. In Proceedings of the 27th International Conference on International Conference on Machine Learning, ICML'10, pp. 255 262, Madison, WT, USA, 2010. Omnipress. ISBN 9781605589077.
Nicola De Cao and Thomas Kipf. MolGAN: An implicit generative model for small molecular graphs. ICML 2018 workshop Theoretical Foundations and Applications of Deep Generative Models, 2018.
Prafulla Dhariwal and Alexander Nichol. Diffusion models beat gans on image synthesis. Advances in Neural Information Processing Systems, volume 34, pp. 8780-8794. Curran As- sociates, Inc., 2021. URL httpps://proceedings www.ing...urrris...... cc/paper filess/pape//222//ilel (9ccaaaeeesfee08877022........
pdf
Paul D. Dobson and Andrew J. Doig. Distinguishing enzyme structures from non-enzymes without aligmments. Journal of Molecular Biology, 330(4):771 783, 2003. ISSN 0022-2836. doi: https://doi.
org/10.1016/ S0000028360023333333002000033322 $002228303306622
URL
Bradley Efron. Tweedie's formula and selection bias. Journal of the American Statistical Association, 106 (496):1602-100 2011. doi:
2011.mmm1111m URL https::/doi.org:: 1118///a...1/.aaaa.... 2011.
tm1 1181 PMID: 22505788.
P. Erdös and A. Rényi. On random graphs Publicationes Mathematicae Debrecen, 6:290, 1959.
Mohammad Fercydounian, Hamed Hassani, and Amin Karbasi. What functions can graph neural networks generate? arXiv preprinl Xiw:2202.00833, 2022.
Aric Hagberg, Pieter Swart, and Daniel Chult. Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National Lab. Lab.([.ANT) Los Alamos, NM (United States), 2008.
15

---

Published in Transactions on Machine Learning Research (06/2024)
William L. Hamilton. Graph representation learning. Synthesis Lectures on Artificial Intelligence and Machine Learning, 14(3):1-159) 2020.
Xu Han, Xiaohui Chen, Francisco JR Ruiz, and Li-Ping Liu. Fitting autoregressive graph generative models through maximum likelihood estimation. Journal of Machine Learning Research, 24(97): 2023.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. In Advances in Neural Information Processing Systems, volume 33, pp. 6840-6851. Curran As- sociates, Inc., 2020. URL
papp
Jonathan Ho, William Chan, Chitwan Saharia, Jay Whang, Ruiqi Gao, Alexey Gritsenko, Diederik P Kingma, Ben Poolc, Mohammad Norouzi, David J Flect, al. Imagen video: High definition video generation with diffusion models. Xiv preprinl or orXiv:2210.02300, 2022.
Emiel Hoogeboom, Didrik Nielsen, Priyank Jaini, Patrick Forré, and Max Welling. Argmax flows and multinomial diffusion: Learning categorical distributions. In Advances in Newral Information Process- ing Systems, volume 34, pp. 12454-12465. Curran Associates, Inc., 2021. URL https::/proceeddigggg http:///.......a./....ooooaaaaaa
Emiel Hoogeboom, Victor Garcia Satorras, Clément Vignac, and Max Welling. Equivariant diffusion for molecule generation in 3D. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 8867-8887. PMLR, 17-23 Jul 2022. URL mlr.
Attps://proceediin http://........eeee////////////e /ttes//112/hhoogbooo222 html
Jonathan H Huggins, Trevor Campbell, Mikolaj Kasprzak, and Tamara Broderick. Practical bounds on the error of bayesian posterior approximations: A nonasymplotic approach. aiviv preprinl Xrx: 899.09505. 2018.
Aapo Hyvärinen. Estimation of non-normalized statistical models by score matching, J. Mach. Learn. Res., 6:695-709, dee 2005. ISSN 1532-4435.
John J. Irwin, Teague Sterling, Michael M. Mysinger, Erin S. Bolstad, and Ryan G. Coleman. Zine: A free tool to discover chemistry for biology. Journal of Chemical Information and Modeling, 52(7):1757-1768, 2012. doi: 10.1021 /0.1001/ii3001127 /c30012277.
URL hattps://don org/10. wttgg//..1///////.// 1011111111110000 PMID: 22587354.
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 2323-2332. PMLR, 10-15 Jul 2018. URL https:
/ //proceedings.. mlr. ppess/v80/ inn... html.
Jaehyeong Jo, Seul Lee, and Sung Ju Hwang. Score-based generative modeling of graphs via the system of stochastic differential equations. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 10362-10383. PMLR, 17-23 Jul 2022. URL https:
wwwpediinnnmmm...eeeeeeeee www..rres//vv2// jo2aa. html html
Daniel D. Johnson, Jacob Austin, Rianne van den Berg, and Daniel Tarlow. Beyond in-place corruption: Insertion and deletion in denoising probabilistic models. Tn ICML Workshop on Invertible Neural Networks, Normalizing Flows, and Explicit Likelihood Models, 2021. URL
CAsVBUe1RR
Oliver Johnson and Andrew Barron. Fisher information incqualities and the central limit theorem. Probability Theory and Related Fields, 1 129(3):391-409) Jul 2004. ISSN 1432-2064. doi: 10.1007/4404400-044444444
URL https://doi. org/00..rg11... 000.00.0000/000000 1ttp:/00000000000400000000000000
Tero Karras, Miika Aittala, Timo Aila, and Samuli Laine. Elucidating the design space of diffusion- based generative models. In Advances in Neurol Information Processing Systems, 2022. URL https:
16

---

Published in Transactions on Machine Learning Research (06/2024)
Nicolas Keriven and Samuel Vaiter. What functions can graph neural networks compute random graphs? the role of positional encoding. arXiv preprint arXin:230..1 14814, 2023.
Thomas N Kipf and Max Welling. Variational graph anto-encoders. NIPS Workshop on Boyesion Deep Learning, 2016.
Thomas N. Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. In International Conference on Learning Represenlations, 2017. URL
SJ
Igor Krawczuk, Pedro Abranches, Andreas Loukas, and Volkan Cevher. Cg-gam: A geometric graph gener- ative adversarial network, 2021. URL httpps///pppaeeree....o//////o/p
Christophe Ley and Yvik Swan. Stein's density approach and information inequalities. Electronic Commu- nications in Probobility, 18(none):1 14, 2013. doi: 10.1214/ECP.v18- URL https://doi.org//
1214/ECP v57-2578
Muchen Li, Jeffrey Yunfan Liu, Leonid Sigal, and Renjie Liao. Graphpnas: Learning distribution of good 2022.
neural architectures via deep graph generative models. arXiv preprint
Renjie Liao. Graph neural networks: graph generation. Graph Neural Networks: Foundations, Frontiers, and Applications, pp. 225-250, 2022.
Renjie Liao, Yujia Li, Yang Song, Shenlong Wang. Charlie Nash, William L. Hamilton, David Duvenaud, Raquel Urtasun, and Richard Zemel. Efficient graph generation with graph recurrent attention networks. In NewrIPS, 2019.
Phillip Lippe and Eistratios Gavves. Categorical normalizing flows via continuous transformations. International Conference on Learning Representations, 2021. URL https:///pparrrrie..eeeee wtt.://wiwwieetee/oorroreiie
-GLNZeVDuik
Jenny Liu, Aviral Kumar, Jimmy Ba, Jamie Kiros, and Kevin Swersky. Graph normaliz- ing flows. In Advances in Neural Information Processing Systems, volume 32. Curran As-
sociates, Inc., 2019. URL. https://proceeddngg www.ips.criic.oooe sac/paper__ htcp:/pper_feeeeeeee_eeeeeee filles/ppper2219//fi.e Paper .df.
Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer: Hierarchical vision transformer using shifted windows. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), 2021.
Youzhi Luo, Keqiang Yan, and Shuiwang Ji. Graphdf: discrete flow model for molecular graph generation. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 7192-7203. PMLR, 18 24 Jul 2021. URL https://prooceddings mlr prees/v1139/uo2la.htm
Kaushalya Madhawa, Katushiko Ishiguro, Kosuke Nakago, and Motoki Abe. Graphnvp: An invertible flow model for generating molecular graphs. arXie preprint 1905.11600, 2019.
Sadegh Mahdavi, Kevin Swersky, Thomas Kipf, Milad Hashemi, Christos Thrampoulidis, and Renjie Liao. Towards better out-of-distribation generalization of neural algorithmic reasoning tasks. Transactions on Machine Learning Research, 2023. ISSN 2835-8856. URL https://openrevieet net. net/forum?id xkrtvHlp3P
Haggai Maron, Heli Ben-Hame Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Advances in Neural Information Processing Systems, volume 32. Curran As- sociates, Inc., 2019a. URL BBC
17

---

Published in Transactions on Machine Learning Research (06/2024)
Haggai Maron, Heli Ben- Ben-Hamm,, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In International Conference on Learning Represenlations, 2019b. URL httpps://openreviie http///ppwriiiieneeeeeeeeeeeeeee wwt. forum?
id=Syx72j09tm
Karolis Martinkus, Andreas Loukas, Nathanaël Perraudin, and Roger Wattenhofer. SPECTRE:
Spectral conditioning helps to overcome the expressivity limits of one-shot graph generators. In Proceedings of the 39th International Conference Machine Learning, volume 162 of Proceedings of Machine Learn- ing Research, pp. 15159-15179. PMLR, 17-23 Jul 2022. URL https: sttpps://proceedingss mmlr. mlr. http:///nn.........////1/12 press/v162/ martinkus22a.hua html
Rocío Mcrcado, Tobias Rastemo, Edvard Lindelöf, Günter Klambauer, Ola Engkvist, Hongming Chen, and Esben Jannik Bjerrum. Graph networks for molecular design. Machine Learning: Science and Technology, 2(2):025023, mar 2021. doi: (0.108//2632-20 2113-211///// 2153/abef91. abcf91. abcf91
URL URLhttts: pttttp::/axx.di.orrg... doi http:pp://.........o/0/11/////// 11t..///0000000/2222222111111
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. Proceedings of the AAAI Conference on Arlificial Intelligence, 33(01) 4609, Jul. 2019. doi: (.1609/aaai.vv32 33014602. URL https://ojs. aaai www.aaaaa...gaaaaaaaa orggindex///ooooooooooooo pttp://AA///atttca//////////////
Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M Kriege, Martin Grohe, Matthias Fey, and Karsten Borgwardt. Weisfeiler and leman go machine learning: The story so far. arXiv preprint arXiv:211.009092 2021.
Alexander Quinn Nichol and Prafulla Dhariwal. Improved denoising diffusion probabilistic models. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 8162-8171. PMLR, 18-24 Jul 2021. URL press/v139/nichol21a. httml
mlr.
Chenhao Niu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon. Permutation invariant graph generation via score-based generative modeling. In Proceedings of the Twenly Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 4474-4484. PMLR, 26-28 Aug 2020. URL https://proceedings mlr press// v108/niu20a.hta.
Kristina Preuer, Philipp Renz, Thomas Unterthiner, Sepp Hochreiter, and Günter Klambauer. Fréchet chemnet distance: A metric for generative models for molecules in drug discovery. Journal of Chemical Information and Modeling, 58(9:11336 1741, 2018. doi: 10.102//acs.jimm.80000000 jbi...0033.... URL https://doi. org/ 10/110..12100 102..................1 jcim jci.mmmo02m34 PMID: 30118593.
Raghunathan Ramakrishnan, Pavlo O. Dral, Matthias Rupp, and O. Anatole von Lilienfeld. Quantum chemistry structures and properties of 134 kilo molecules. Scientific Data, 111):140022, Aug 2014. ISSN 2052-4463. doi: 10. 10.1038/sdaata.2014.22 URL https://doii org/10, 1038/sdata. 2014.22
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Fliassi-Rad Col- lective classification in network data. AT Magazine, 29(3))93, Sep. 2008. doi: 10.1609/aime aamag. 2amma..22:3.2155) v1913.2157.
wtt.:/aaaa..gggaaaaaaeeeeeeeeeee http://aaaazziieiidaaaaee https//ppppaaamzaiiaiiee http///aaaaaiiieaaaieeeeeeeeeeee URL https://ojs.aaat aaai. org
Wenkang Shan, Zhenhua Liu, Xinfeng Zhang, Zhao Wang, Kai Han, Shanshe Wang, Siwei Ma, and Wen Gao. Diffusion- based 3d human pose estimation with hulti-s aggregation. arXiv preprint
wwXiv:2303.11577 2023.
Chence Shi Minkai Xu*, Zhaocheng Zhu, Weinan Zhang, Ming Zhang, and Jian Tang. Graphaf: flow- based autorcgressive model for molecular graph generation. In International Conference on Learning Representations, 2020. URL
Martin Simonovsky and Nikos Komodakis. Graphvae: Towards generation of small graphs using variational autoencoders. In Artificial Neural Nelworks and Machine -CCrning-TCANN ICANN 2018: 27th International
18

---

Published in Transactions on Machine Learning Research (06/2024)
Conference Artificial Neural Networks, Rhodes, Greece, October 4-7, 2018, Proceedings, Port I 27, pp. 412-422. Springer, 2018
Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibriun thermodynamics. In Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pp. 2256-2265) Lille, France, 07-09 Jul 2015. PMLR. URL atttps:/pproceedingg
html
Jiaming Song, Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit models. International Con- StigiarCH ference on Learning Representations, 2021a. URL |ateps://openreeveeu wtt/ffrummid htt.:ppparooreeooooooooorrorraaa htt.://www....oouuuraaaaa.aaaaaa
Yang Song and Stefano Ermon. Improved techniques for training score-based generative mod- els. In Advances in Neural Information Processing Systems, volume 33, pp. 12438-12448, Cur- Associates, Inc., 2020. URL 92cb0661165700227766ssaaaaaaa222
Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stelano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. In International Conference on Learning Representations, 2021b. URL
Mohammed Suhail, Abhay Mittal, Behjat Siddiquie, Chris Broaddus, Jayan Eledath, Gerard Medioni, and Leonid Sigal. Energy-based learning for scene graph generation. In Proceedings of the IEEE/CVE Con- ference on Computer Vision and Pattern Recognition (CVPR), pp. 13936-13945, June 2021.
Ananda Thoertha Suresh, Alon Orlitsky, Jayadev Acharya, and Ashkan Jafarpour. Near-optimal-samlle estimators for spherical gaussian mixtures. In Advances in Neural Information Processing Systems, vol- ume 27. Curran Associates, Inc., 2014. URL http::/s/ppppeeang...ar......... ftaapprrffflee/ppperrr
pdf
Endre Süli and David F. Mayers. An Introduction to Numerical Analysis. Cambridge University Press, 2003. doi: 10.1017/C300978811111111
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
Clement Vignac and Pascal Frossard. Top-n: Equivariant set and graph generation without exchangeability. In International Conference on Learning Representations, 2022. URL httpsss//ppperreeeeeeneee//////s new.ooruuweeeerrr
[d=-Gk_ IPJWvk
Clement Vignac, Igor Krawezuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pascal Frossard. Digress: Discrete denoising diffusion for graph generation. In The Fleventh International Conference Learning Representations, 2023. URL
Pascal Vincent. A Connection Between Score Matching and Denoising Autoencoders. Newral Computation. 2367):1661-1674 07 2011. ISSN 0899-7667. doi: 10. 10.1162/NECO__000 _01442. URL https://doi. org/10. 1162/NECO a 00142
Duncan J. Watts and Steven H. Strogatz. Collective dynamics of 'small-world" networks. Nature, 393(6)8
140,442, Jun 1998. ISSN 1476-4687. doi: 10.1038/30918. URL
Tete Xiao, Yingcheng Liu, Bolei Zhou, Yuning Jiang, and Jian Sun. Unified perceptual parsing for scene understanding. Proceedings of the European conference on computer vision (ECCV), pp. 418-434, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanic Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. URL http://pparrrreeo.ooee/ooroorooe ryGm6iA5Km
19

---

Published in Transactions on Machine Learning Research (06/2024)
Minkai Xu, Lantao Yu, Yang Song, Chence Shi, Stefano Ermon, and Jian Tang. Geodiff: A geometric diffusion model for molecular conformation generation. In International Conference on Learning Repre- sentations, 2022. URL http::///pppaarrrre.eeee///rrrsp
Ling Yang, Zhilong Zhang, Yang Song, Shenda Hong, Runsheng Xu, Yue Zhao, Yingxia Shao, Wentao Zhang, Bin Cui, and Ming- Hsuan Yang. Diffusion models: A comprchensive survey of methods and applications. arXiv preprinl or arxi:220090000 00796, 2022.
Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. GraphRNN: Generating realistic graphs with deep auto-regressive models. In Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 5708-5711 PMLR, 10-15 Jul 2018.
URL httpps://proceedinng. .ml.rinn..........mmm..m...... m html
Kiarash Zahirnia, Oliver Schulto, Parmis Naddaf, and Ke Li. Micro and macro level graph modeling for graph variational aulo-encoders. In Advances in Newral Information Processing Systems, 2022. URL
20

---

Published in Transactions on Machine Learning Research (06/2024)
Appendix
TABLE OF CONTENTS
A PROOFS AND ADDITIONAL THEORETICAL ANALYSIS
22
Proof of Lemma 4J
22
Proof of Leinma
25
A.3 Invariant Model Distribution via Permutation Equivariant Network
26
A.4
Sample Complexity Lower Bound of Non- Nou-perrmataatooncuuuvaaaaa Network
27
B
ADDITIONAL EXPERIMENT DETAILS
29
B.1
Detailed Experiment Sctup
29
B.2
Network Architecture Details
30
B.3
Node and Edge Attribute Encoding
B.4
Diffusion Process Hyperparameters
31
B.5
Model Memory Efficiency
31
B.6
Comparing against the Swin Transformer Baseline
32
B.
Effects of Window Size
32
Additional Resulls on Molecule Datasels
33
B.9
Additional Qualitative Results
35
21

---

Published in Transactions on Machine Learning Research (06/2024)
A*
Q
A'
A-/Q
Figure 5: Different configurations of TV Pdata), given fixed A (the support of Pdata) and its induced A". Here, we modify Q (the support of q). Left: maximal TV, Q is disjoint from A/A". Middle: intermediate TV, intersecting Q and A/A" Right: minimal TV, Q = A
A PROOFS AND ADDITIONAL THEORETICAL ANALYSIS
A.1 Proof of Lemma 4.1
Lemma 4.1. Assume at least one training graph has (n!) distinct adjacency matrices in its isomorphism class. Let P denole all discrele permulation invoriant distribuations. The closest distribulions in P to Pdata; measured by total variation, have at least. 52(m)) modes. Tf, in addition, we restrict P to be the set of permutation invariant distributions such that p(A.) p(A,) > 0 for all matrices in the training set { then the closest distribution is given by arg min TV (q. Pdata) Pdsta
Proof. Recall the definitions on Pdata and Pdata in our context:
Pdata (A)
Σ 5(A A,), Panta (A)
1
Σ 6(A-A)) A,EA'
Z
In other words, Pdata and Pdata are both discrete uniform distributions. We use A and A = IA, UIA, ...U Iam. to denote the support of Pdata and Pdata respectively. Let TV = TV Pdata) be the "golden standard' total variation distance that we aim to outperform.
Let g E P without loss of generality. As q is permutation invariant, must assign equal probability to graphs in the same isomorphism class, We denote the support of q by Q {In, 1 (A) E P: EATEZ, 8(A-
A,), whore E P. = 1, P; > O, and > O stand for the number of isomorphism classes contained in Fig. 5 summarizes the possibilities of TV used our proof.
Proof of lin!) Modes. This first part of the lemma imposes no constraints on P: we do not require distributions in P to be uniform on A. We first prove two helpful claims and then use proof by contradiction to prove our result on ((n!) modes.
Clain 1: The maximal TV(4, (q, Pdata) is achieved when Q and A are disjoint (so are Q and A).
Proof of Claim 1: Without loss of generality, the TV distance is:
TV(g. ((att)
Pi AA
1
Σ
Pi
+
Σ
A
1
1=1
AET NA
AEI
AEQ.AEA
Σ (pi+ +
[A
Σ
Pi
Σ
A
(triangle inequality)
1=1
AETg nn
AEI
AEQ.AEA
Σ
Σ
A
Pi
A
AEIg NA
AEIn
AEQ.AEA
+
Σ
Σ
P: +
=
A
1=1 AEI.
AEA
The triangle inequality is strict when Ee Ig. n-AI > 0, as Pj and
A are always positive, and lp: T
Pi L holds. If Q and A are disjoint, TV (g, Paata) Σ. IZ maximum TV distance is achieved when there is no intersection between Q and A".
p + गे x |A| 2, meaning that the
22

---

Published in Transactions on Machine Learning Research (06/2024)
Claim 2: It is always possible to have a q eEEgEEE P with (g Pasta) < 2 by allowing Q and A to intersect some isomorphism classes (Iq. Niew- Notice Iy; n A & 0, Vi E v as per isomorphism.
Proof of Claim 2:
+
(g, Pdata) =
Σ
Σ AA
Pi
|A|
+
Σ
+
Σ
IAI
2=1
A
AEQ.AEA
Σ
Σ
Σ +++ Σ
Pi
A
+
A
IEV
AA
A
IEVU AET
AEQ.AEA
Σ
ZZg n
Pi
A
1
+
(Z
Kg. nA)A))))
+ +I
E ++
Σ
A
SEV
iEN
AEC.AEA
Σ 11 n-11 (1-
AA
1
Pi
Σ
Pi
Pi|IZal
+
|
Σ
A
1
AEA
AEQna
(0i-
1
Σ 3EV
11 n-1
Ing nAA
AAI +
A
==1
=0 if iEtN
= Σ Js nAl (1
1
Pi
T
Pi
A
Σ i
Ipp 0 A
|
+
1ER
ΣI nAl (0--
Pi [A]
+2 +2<
|A|
iEV
1 The last inequality is strict as Pi: [AI and [Tg. n.A) are all strictly positive for i E v.
Let q² E arg gep TV (g, Pdata) be minizizer whose support is O- @ and A must not be disjoint, i.e., Q' intersects A' for at least one isomorphism class in A".
Clain 3:
Proof of Claim 3: Assume Q" and A have no intersection, then mingep TV (ddga) = TV -Pdata) = 2, which is validated in Claim 1. From Claim 2, we know there must exist another q' P with TV (q' Paata) < 2. Therefore, mingep (V Pdata) S (V Paata) < 2, which contradicts minger (q. Pdats) 2. To minimize TV Pdata), one can enlarge the set optimal |Q"| has a lower bound Q(n!) that does not depend on the size of empirical data distribution [A].
Pduta)=
that the intersection covers A. Consequently, the
Proof of Optimality of Piata when P is Discrete Uniform on a Superset of A.
Now we procoed to prove the second part of our lemma, which is a special case when P has some constraints w.r.t. A. Assume A = {A, consists of m graphs (adjacency matrices) belonging to isomorphic equivalence classes, where m 2 k due to some potential isomorphic graphs. Subsequently, let A" have adjacency matrices for all k equivalence classes (1 2 m), i.e. A" = UA = - where (E denote k equivalence classes.
Further, let 4 E P and let 2, 2 A be its support. That is, 4- = 1 |.. EAre 5(A - As), where 10,1 2 m.
The lotal variation distance is:
TV
x m + (1 - m) = 2(1 - m
7)
m
12 - m
m
TV Pdata)
x m +
= 2
|0,1
m
12
|
To minimize TV Pdata) over Gy, we need to minimize 12
Since A C 2, and 4, is permutation LA* = l. Therefore, we conclude that
invariant, the smallest 12 would be | Jum IA.1
U Io,l
min TV Pdata) = TV 2(1 T). and arg min TV Pdata) Pdata EP
23

---

Published in Transactions on Machine Learning Research (06/2024)
Justification on the Constraints of P to Guarantee the Optimality of Pdata'
In the end, we justify the reason why P has to be discrete uniform on a superset of A (i.e., assign equal probability to each element in A) for the second part of the lemma to hold. We list all possible conditions in the table below and give concrete counterexamples for the cases where the optimality of Pdata is no longer true, i.e,, Paata & arg min (g, Pdata) or equivalently min TV (1.Paatta) < TV = TViPaata: Pdata). For ease gEp of proof, we further divide Pdata into two calegories based on the existence of isomorphic graphs.
PEP
Paeex conditions
A has isomorppic graphs
A does not have isomorphic graphs
support contains A and uniform support contains A and not uniform
Our proof in the above: True, min TV (g.p) = TV*
dEP
P conditions support does not contain A
False, Case 1: min (V (ttaa)) TV
False, Case 2: min Piaa) < TV
gEP
False, Case 3: min TV(:: < TV
False, Case 4: min (V(g. Panta) < TV
'EP
OEP
Consider graphs with n = 4 nodes, let the support of Paata (d.e., A*) be adjacency matrices belonging to two isomorphism classes In and Ip, where [Tal = 24, [Tol = 6. Namely, I, has no automorphism (e.g., complete disconnected graphs), and the aulomorphism number of Io is (e.g., star graphs). Let Ia = (A1, A2, ... A243 and Ia == {A25,... "A.))
Case 1: Let A= {A23, A21, A with isomorphic graphs. Let qa (A) = Po E ((A-A)) Eieos 8(A
A,) be a mixture of Dirac delta distributions, where Pa-Pb > 0. Due to normalization, ΣA 9a (A)
24pa + 6ps = 1 or Pb 1-240- We can tweak Pa: Ph so that Qa is not necessarily uniform over its support, but Qa is permutation invariant by design, i.c., qa (a(A)) = (A()))
9a (A21) and qa (A2)) = qa (A26)
2a (A32). The TV is:
1
29
TV (qa, Pdata) = Poo 1 x 2+ + Po: J
1
5
TV 1/
3
+
x 29
+
+2pp
+ 5pp
4pa
32
32
16'
3
Setting (g Pdata) =
5/5 + App < TV = 29
I6. we have: Po <
aB Let Pa = 1
28. Pb =
12'
1
We now have:
min (g.Pedata) I (ga, Pditaa < TV*, and Pdata is not a minimizer of min TV (g. Pdusa)- 9EP
PEP
Case 2: Let A = {A21. A2s} without isomorphic graphs. Similarly, let go (A) = Pa Ei 8(A - A.) +
Ph 2i=25 8(A A.) be a mixture of Dirac delta distributions. The TV is:
15
1 2
1 2 + 23p + +5pp = + 6pa.
TV =
2/2
x 2 +
x 30 = TV Pdata) = -po - + Pb
32
32
8
2
3
Setting TV (1 (qox, Pdata)
5 + 6p < TV 15
5 we have: Pa Fे. Let Pa T8 Pb = -/22 Again, we have:
min TV (VVV(.PPaa Pdata) S TV (9a: (qa: Pdata) < TV*, and Pdata is not minimizer of min TV (q. Pdsta). PEP
'EP
Case 3: Let A= = (A2s, A A with isomorphic graphs. Let qs be a uniform discrete distribution on Iz. Us is permutation invariant (thus gæ P) whose support does not contain A. The TV is:
1 TV
1 x
29
1 3
1 x
5
1/3
x
29-
(g), (data)
+
3 x2= 3
32
32
16"
6
So, min TV Pdata) SVV (q3. Pdata) TV* Piata is not minimizer of min TV (g, Pdata). 'EP-
-EP-
Case 4: Let A= = (A21,A55) without isomorphic graphs. We use the same qo as above. The TV is:
1 1 TV
1 x 30 : TQ Pdasa) 1 1
15
5 3
2+
+
x5
x5+
x 1
32
32
2
2
Again, min TV (q, Paata) 5 TV (Ts,, Pdata) TV*, Piata is not minimizer of min TV (g, Pdata). 9EP-
gEP-
In fact, in case 3 and 4, Panta $ P, and by definition, Piata cannot be a minimizer of min TV ('V Pdata). To gEp see that, the support of Pāata must contain A" (a superset of A), while the support of any q E P is not a superset of A as per P conditions in case 3 and 4.
24

---

Published in Transactions on Machine Learning Research (06/2024)
A.2 Proof of Lemma 4.2
Lemma 4.2. Let A be random adjacency malriz distribuled according to any graph. distribulion vertices. Let Pr ~ Uni be uniform over the set of permatation matrices. Then, the induced distribution of the random matric Ar = P,AP,, denoted as qo (Ar), permatation invariant, i.c., (A(A,) = S.(PA,PP)) E
Proof. Let P(-) denote the probability of a random variable.
/ (A,A,A)) (A))A))o(AA)A
2o (A,))
(define the random permutation conditional)
((PA-AA)PO(AACAA
(PA+A, satifies PA-A,APA- Ar)
Σ P(PA-A.)P((A) AEIA,
(permutation cannot go beyond isomorphism class)
Let us define the set of 'primitive graphs' that could be generated by po: C(IA.) = (Alpo(A) 0, A E IA.) that corresponds the isomorphism class IA.. Let Aut(+) denote the automorphism number. Then, we have:
40 (A,)
Σ P(PA-AA))O(A)
AETA
Σ
P(PA-A.)PO(A)
AEC(IA,)
Σ
(.PA-A,)PO(A)
Σ
P(P ((PA-A))PO(A)
A:-AAAECIZA.)
A.CA.AECIIA.)
Aut(Ar)
(P: PA-AA APT A, A,H
Σ
(A( n..
Σ
Po (A)
n!
A:ECTAA
A.y A.E.A.EC(TA.))
Aul(A,) (A)
Aul(A,)
Σ
Σ
Po (A)
n!!
n!!
AECAAACC
A-CA.AEC(IA.)
Aut(A,)
Σ
(A)
AEC(TA.)
For the case of A, = A, A(PA-A)) is the probability of obtaining automorphic permutation matrices, which is Aut(Ar) by definition. As for A, A, need to compute the size of fip {P: PA-A, APT A,, A, + A), i.e,, how many permutation matrices there to transform A into A,. The orbit-stabilizer n! theorem states that there are Aut(A) many distinct adjacency matrices in IA (size of permutation group Aut(A] subgroups, where
orbit). For any A, we could divide all the permutation matrices in Sn into each group E 21, .p} transforms A to new adjacency matrix A, One of the subgroups transforms A into itself ei.e., automorphism), and the rest p subgroups transform A into distinct adjacency matrices. As A, # A, the size of Sp is equal to the size of one such subgroup, which is Aut(A). So, we could aggregate the two cases of A, = A and A, # A.
For any A and A, that are isomorphic to each other, we have:
Aul(AA)
Σ Aul(A,)
(o,)
Σ
PA(A)=
po(AA) (A(),))
n!
AECIZAL
AEC(IA.)
The second equality holds because (ut(A (A,(A,),, IA, IA. and C(IA;) C(IA.), which are evident facts for isomorphic graphs. Thus, any two isomorphic graphs have the same probability in go. The random permutation operation propagates the probability of the primitive graphs to all their isomorphic forms. 7
25

---

Published in Transactions on Machine Learning Research (06/2024)
A.3 Invariant Model Distribution via Permutation Equivariant Network
For demoising model, if we consider one noise level, the optimal score network would be the score of the following noisy data distribution Po (A) = 1 the dataset )= This is the case for diffusion models with non--ermutation-cuuvvaaaaa in what follows, we first show that for equivariant networks, the noisy data distribution a GMM with (nlm) components. As score estimation and denoising diffusion are equivalent, we use the terms 'score' or 'diffusion' interchangeably.
m Ei=1 (NA A, I² which is a GMM with m components for
networks, and
Lemma A.1. Assume we only observe one adjacency matriz out of its isomorphism class in dataset { and the size of isomorphism class for each graph is the same, i.e. [TA,] = |ZAa| = | Let 8g be permatation equivariant score estimator. Under our definitions of Pāata (Bata(A) (A) and Pdatal ( (A), the following two truining objectives are equivalent:
m
1.
B pa (A)pa (Á(A) [ V log Po (A|
(9)
E Pdata A)) (AIA)
[]|s@] (A,
V log Po (A
(10)
Proof. We conduct the proof from Eq. [0] to Eq. 9 Let P S, be an arbitrary permutation matrix and ps. be a uniform distribution over all possible permutation matrices Sn.
B PamallA) ()), (AIA) 6 (Á, V log [}
A-A Ā pT1
= Pa
Ps (A, p
[
Frobenius norm is permutation invariant)
d²
A Ā
=P (AIA) ||| PAP" .0)
p²1
(sg is permutation equivariant)
PT
BP
dÅ dB
= (B 15 p
pT P
Det
I]
(change of variable PAP
g2
(p (B, PAP B
||
Det(P & P)
0²
E Ap (B,o) V (B )
Epans (P)r A | |1|> (B.,),
V lo B PAP )
(let ~ ps.. be uniform) (permuting Pdata samples leads to Pdata samples)
Epina (A (
B, V (B
E (A), (AAA)
||| 0² r) V logp: (Ā A) [}
(change name of random variable)
The change of variable between À and B leverages the fact that permuting i.i.d. Gaussian random variables does not change the multivariate joint distributions. Conditioned on A and P, we have Á= = A + E; B PAP + PEPT, where the randomness related to e (Gaussian noise) is not affected by permutation due to iid. property. The second last equality due to our definition of Pdata and Pdata- Recall we take the Dirac delta function over A to build Pdata and over A' to build Paata: where A is the union of all isomorphism classes in A. By applying random permutation on samples drawn from Paatas we subsequently obtain samples following Pasta- The main idea is similar to the proofs in previous works (Niu al.] 2020 Xu et al, 2022 Hoogeboom et al. )022).
If we do not have the essumptions the size of isomorphism class, the non-trivial automorphism would make the equality between Eq. (1)) and Eq. (9) no longer hold, as each isomorphism class may be weighted differently in the actual invariant distribution. We can then replace the Pdsta by a slightly different invariant distribution: (-permuted (I n!!) empirical distribution, defined follows: Paata (A) = E/ 5(A- P,A.P,), where S, (PI..... Pt). Both planta (A) and Piata have 0(nmm) many modes. Therefore, the assumptions do not affect the number of GMM components for underlying noisy data distribution, which is result we care about.
26

---

Published in Transactions on Machine Learning Research (06/2024)
More formally, connect the number of modes in the discrete distribution Pdata Paata to the number of components in their induced GMMs. We show that the noisy data distribution of permutation equivariant network is (A) = Σ ATEA- (A; I))
I) of O(n!)) components. Namely, the optimal solution sg.
to Eq. 19 or equation 10 is V log (A). Leveraging the results from Vincent 2011 we have
B Panca (A)A) 24 o) - V log Po (
Explicit score matching for p:
E ((()) [11.0 (A,o) V logo p (A)
-0 C2
C E (A) |IV logpo(()) p.) C2 =B,
-Bpan. Panca (A)p. (A log (AIA)]])
As Ci C2 are constants irrelevant to 0, optimization objective on V log (A) is equivalent to Eq. 10 the latter of which is often used as the training objective in implementation.
A.4 Sample Complexity Lower Bound of Non- pnermutaaiionequivariinn Network
In this part, we study the minimum number of samples (i.e., the sample complexity) required to learn the noisy data distribution in the PAC learning sctting. Specifically, our analysis is mainly applicable for the catrrrmullaiinnequiiurreee
network, where we do not assume any hard-coded permulation symmetry. We leave the analysis for permutation equivariant network as future work.
Recall that training DSM at a single noise level amounts to matching the score of the noisy data distribution. Knowing this sample complexity would help us get a sense the hardness of training DSM since if you can succossfully learn a noisy data distribution then you can obtain its score by taking the gradient. Now we derive a lower bound of the sample complexity for learning the noisy data distribution (i.e., a GMM).
Lemma A.2. Any algorithm that learns the score function of Gaussian noisy data distribution that con- tains centroids of d-dimension requires M(ld/e)) samples to achieve Fisher information distance ef with probability at least 2-
Here the Fisher divergence (or Fisher information distance) (Johnson & Barron 2004 is defined Je(f.g) = Ex(x) [||Vx log f(X) Vx x log 9(x) where f(X) and g are two absolutely continuous distributions defined over IRd. Now we apply Lemma A.2 the graph distribution in our context. Recall we the N(A; A,;
assume m graphs {AA, with nodes in the training set. Similar to our investigation in Sec. 4.1
GMM corresponding to the l-permuted empirical distribution: 1o (Ā) mt A
Let go (A) denote the estimated distribution returned by Corollary A.3. Any algorithm that learns qo for the largel l-permaled distribution P' lo Ef error in Jr(p. 9o) with probability at least & requires N(mln²/e samples.
wepprrrttttiooncqquvaieee network.
Corollary A.3 states the condition to learn distribution go explicitly with bounded Fisher divergence, from which one could compute a score estimator 8go = V log go (A) with bounded DSM error w.r.t. the target P/. The sample complexity lower bound holds regardless of the specific learning algorithm.
The highlight that the sample complexity lower bound has a dependency on 12(1), which would substantially increase goes to its maximum n!. more practical implication is that given a training samples drawn from ph,, one could expect, with at least probability, a score network to have at least of min"" error in Fisher divergence. If we extend to the maximum nl, the learning bottleneck would be the size of the graph instead of the number of the graphs m, for single large graph could induce prohibitively enormous sample complexity. This analysis also aligns with our experimental investigation in Sec. 4.1 where the recall metrics drop with going up.
27

---

Published in Transactions on Machine Learning Research (06/2024)
Proof of Lemma A.2 We first introduce two useful lemmas before diving into the proof.
Lemma A.4. Por twice continuously differentiable distribulions I and g defined over Rd, lel JF(f.9) == F() x x log f(X) V log [F be the Fisher information distonce and let Jrv(f.g) = ((X))XX be the total variation (TV) distance. Jr(f.g) 2 CFTV(f. for some con- staml C C>0 0. (Huggins el al., 2018; Ley 8 Swan 2013/. The enact value of C relies on conditions of I and (c.f. Theorem 5.9 in Huggins et al. (2018))
SuPBCR" (x(
Lemma A.5. Any method for learning the class of I-miatures of d-dimensional isotropic Gaussian distribu- tion with C2 error in total variation with probability at least has sample complerity (((d/c() (Suresh et al. 2014 Ashliani et al, 2020).
Now we restate Lemma A.2 and show the proof formally.
Lemma A.2. Any algorithm that learns the score function of Gaussian noisy data distribution that con- tains centroids of d-dimension requires ( samples to achieve Fisher information distance cf with probability at least 1.
Proof. We derive our results through the distribution learning (a.k.a. density estimation) approach on top of existing analysis. Without loss of generality, let f(X) and g be two twice continuously differentiable distributions defined over Rd. Let us assume f(X) to be a GMM whose Gaussian components have isotropic variance, similar to the noisy data distribution P in the diffusion model. We consider the general distribution learning problem where learning algorithm lakes sequence of i.i.d. samples drawn from the target distribution f and outputs a distribution as an estimate for f.
According to Lemma A.4 the Fisher information distance Jr(f.g) g) is lower bounded by the square of TV distance (Jy with a posilive multiplicative factor C, under some mild conditions. In order to bound the Jr(f.9) g) by Ey: (ry(f.g) must be smaller than V Importantly, the target f is a GMM, whose density estimation problem with TV distance have been well-studied and it admits sample complexity lower bound illustrated in Lemmaa A.5 Plugging in the desired error bound for JIv(f.g) e V L we obtain sample complexity lower bound M2(l/ee)), where the constant C is absorbed. It has the same PAC-learning mcaning for gT)(f.g) with error bound = V and for JF(f.9) with error bound Cy.
We first identify that TV distance a weaker metric than the Fisher information distance, the latter of which corresponds to the original score estimation objective. Then, we utilize the recent advances in sample complexity analysis for learning GMMs with bouned TV error, and thus obtain sample complexity lower bound for score estimation. In summary, we use the result of 'weaker' distribution learning task to show how hard the score estimation objective at least is.
Proof of Corollary A.3
Corollary A.3. Any algoritium that learns go for the target l-permated distribution r' to ef error in Jr(pa. qo) with probubility al least 3 requires Q(mln? /ez) samples.
Proof. We conduct the proof by applying the results from Lemma components. Since our samples drawn from the noisy distribution P'a are noisy adjacency matrix Á E Raxx first vectorize them to be R= In this way, we can view p/, as GMM with O(ml) components of n dimensions. Recall we inject i.i.d. noise to each entries, each Gaussian component has isotropic covariance. The conditions of Lemma A.2 (specifically, Lemma A.5) are all satisfied. Plugging in the above parameters, we obtain the sample complexity lower bound 2(mln"// for score estimation w.r.t. p/r through distribution learning perspective.
A.2 We know p', is an GMM with ((m))
28

---

Published in Transactions on Machine Learning Research (06/2024)
e=16, n=16
e=24, n=16
e=32, n=16
e=40, n=16
e= n= 16
e=56, n=16
e=64, n=16
e=72, n-16
e=80, n-
e=88, n=16
Figure Toy dataset for the investigation of effective target distributions. The datasct compriscs randomly generated regular graphs each with 16 nodes and degrees ranging from to 11.
B ADDITIONAL EXPERIMENT DETAILS
B.1 Detailed Experiment Setup
Toy Dataset. For the toy dataset experiment, we conduct a sampling process where each model allowed to generate 100 graphs. To determine the graph recall rate, we perform isomorphism testing utilizing the networkx HHagergg et al. 22088) package. The training set's visualization provided in Fig. 6
Synthetic and Real-world Datasets. We consider the following synthetic and real-world graph datasets: (1) Ego-small: 200 small ego graphs from Citescer dataset (Sen et al. 2008) with [ E [4, (8, (2) Community-
small: 100 random graphs generated by Erdös Rényi model (Erdös & Rényi 1959) consisting of two equal-
sized communities whose [V] E [12, 20), (3) Grid: 100 random 2D grid graphs with [V] E [100, 400). (4) Protcin: real-world DD protein dataset (Dobson & Doig 2003) that has 918 graphs with [V] E [100, 500]. We follow the same setup in Liao et al. (2019); You et al. (2018) and apply random split to use 80% of the graphs for training and the rest 20% for testing. In evaluation, we generate the same number of graphs as the test set compute the maximum mean discrepancy (MMD) of statistics like node degrees, clustering coefficients, and orbit counts. To compute MMD efficiently, follow (Liao et al.] 2019) and use the total variation distance kernel.
Molecule Datasets. We utilize the QM9 (Ramakrishnan et al. 2014 and ZINC250k (Irwin et al. 2012) as molecule datasets. To ensure a fair comparison, we use the same pre-processing and training/testinng set splitting as Jo al. (2022); Shi* et al. (2020); : Luo al. (202T). We generate 10,000 molecule graphs and compare the following key metrics: (1) validity w/o correction: the proportion of valid molccules without valency correction or edge resampling; (2) uniqueness: the proportion of unique and valid molecules; (3) Fréchet ChemNet Distance (FCD) (Preuer et al.) 2018): activation difference using pretrained ChemNet; (4) neighborhood subgraph pairwise distance kernel (NSPDK) MMD (Costa & Grave! 2010): graph ker- nel distance considering subgraph structures and node features. We defer the discussion on novelty score
in App. B.8
Data Quantization. In this paper, we learn a continuous diffusion model for graph data. Following DDPM (o al. 2020), we map the binary data into the range of [-1, 1] and add noise to the processed data during training. During sampling, start with Gaussian noise. After the refinement, map the results from (-1,
29

---

Published in Transactions on Machine Learning Research (06/2024)
1] to [0, 1]. Since graphs are discrete data, choose 0.5 as threshold to quantize the continuous results.
Similar approaches have been adopted in previous works NNu et al. 2020 Jo et al. 2022
B.2 Network Architecture Details
Table 6: Architecture details of the proposed SwinGNN and major baselines. "The same hyper-parametees are employed for both SwinGNN and SwinGNN-L, barring specific exceptions outlined in the table. The UNet adopted from Dhariwal & Nichol 2021 with their heprpaaraeeters for the ImageNet-64 dataset.
Hyperperamttr
Ego-smaal
Community-amal
Grid
Protein
QM9
ZINC250K
Downsammlling block layes
4,
1. 3,
1]
3, 3, [1. 1.
Upsampling block layers
[1.
[1, 4.
3,
1. 1.
p. 1,
Patch size
3
4
4
Window
SwinGNN
Token dimeusion
60
G0
601
60
Foodforward layer dimeension
240
240
240
240
240
240
Number attention heads
[3, 6, 12, 24]
[3, 12, 24]
[3, 6, 12, 24] 15.31M
[3, 24]
33, 6, 12, 21)
[3, 6, 12, 24]
Number trainable perameters
15.37M
16.37M
15.31M
15.25M
15.25M
Number of epochs
10000
10000
15000
50000
5000
5000
FMA
0.9
0.90
0.99
0.9800
0.0009
0.9800
96
Foodforward layer dimension
384
384
384
384
384
394
SwinGNN.L"
Number of trainable paramacters
34.51M
35,91M
35.91M
35.91M
35.78M
35.78M
Number epochs
10000
10000
15000
50000
5000
5000
EMA
0.99
0.95
0.95
0.9899
0.9999
0.9999
Channel multiplier
61
61
Channels per resolation
1, 2, 3.
[1, 2,
[1, 2, 9,
[1, 1,
2,
Residule blocks per resolution
UNM
Number trainable perameters
30.86M
31.12M
29.50M
32.588 52M
Number of epochs
5000
5000
15000
10000
EMA
0.9999
0.99
0.999
Optimization
Optinnizer Learning
Adan
Adamn
Adai
Adam 1.0 10
Adam 1.0 10
Adamn
10
1.0
10-4
10
1.0 10
Our Models and Baselines. Tab. shows the network architecture details of our models and the UNet baselines on various datasets. Regarding the PPGN (Maron et al., 2019a),, we utilize the implementation in Martinkus et al. (2022). takes an n x n noisy matrix as input and produces the denoised signal as output. To build non-permuaation-cquvviaaa
version of PPGN, simusoidal positional encoding (Vaswani ett al. 2017) is applied at each layer. We use the same diffusion setup for PPGN-based networks and our SwinGNN, as specified in Tab. 7 For fair comparison, we utilize the publicly available code from the other baselines and run experiments using dataset splits.
Network Expressivity. Both theoretical and empirical evidence have underscored the intrinsic connec- tion between the WL test and function approximation capability for GNNs (Mahdavi et al.) 2023 Hamil-
ton 2020 Chen et al.) 2019; Morris et al. 2019 Maron et al.] 2019b Xu et al. 2019). The permutation equivariant PPGN layer, notable for its certified 3-WL test capacity, is doemed sufficiently expressive for experimental investigation. Further, it crucial to note the considerable theoretical expressivity displayed by non-permmin patn--eeuaattineuuvvvattee Fercydounian et al.) 2022). We argue that the GNNs employed in our studies thcoretically have sufficient function approximation capacities, and therefore, the results of our research not limited by the expres- siveness of the network.
GNNs, particularly those with positional encoding (Keriven & Vaiter 2023
B.3 Node and Edge Attribute Encoding
Molecules possess various edge types, ranging from no bond to single, double, and triple bonds. Also, they encompass diverse node types like C, N, O, F, and others. We employ three methods to encode the diverse node and edge attributes: 1) scalar representation, 2) binary bits, and 3) one-hot encoding.
Scalar Encoding. We divide the interval [-1, 1] into several equal-sized sub-intervals (excopt for the intervals near the boundaries), with each sub-interval representing a specific type. We quantize the node edge attributes in the samples based on the sub-interval to which it belongs in Jo et al. (0022)
30

---

Published in Transactions on Machine Learning Research (06/2024)
Binary-bit Encoding. Following Chen et al. (2023). encode attribute integers using multi-channel binary bits. For better training dynamics, remap the bits from 0/1 to -1/1 representation. During sampling, we perform quantization for the continuous channel-wise bit samples and convert them back to integers.
One-hot Encoding. We adopt a similar process as the binary-bit encoding, up until the integer-vector conversion. We use argmax quantize the samples and convert them integers.
Network Modifications. We concatenate the features of the source and target node of an edge to the original edge feature, creating multi-channel edge features as the augmented input. At the final readout layer, we use two MLPs to convert the shared edge features for edge and node denoising.
B.4 Diffusion Process Hyperparameters
Table 7: Training and sampling hyperparameters in the diffusson process.
c,(o) to
colo) = add
/ 102+02
c(o)
(a(d) (n((r)
Va3+02
Od = 0.5, ln)o) ~ (N P2 Pald): : Pmeaa = - Pstd = -1.
Omin = 0.002, maax = 80, p =
Semin 0.05, S umax 50, Snoise 1.003, Schurn = -00 256
t. (amax N-1 (Tmin Tmax ))8
7 = 1 Sty Stemn min( Schaen v2 1)
No
The hyperparameters of the diffusion model training and sampling steps are summarized in Tab. 7 For our SwinGNN model, maintain consistent setup throughout the paper, unless stated otherwise. This setup is used for various experiments, including the ablation studies where we compare against the vanilla DDPM (Ho et al. 2020) and the toy dataset experiments.
The pivotal role of refining both the training and sampling phases in diffusion models to bolster performance has been emphasized in prior literature (Song et al. 2021a Nichol Dhariwal 2021 Karras et al. 2022). Such findings, validated across broad spectrum of fields beyond image generation (Shan et al.) [023 Yang et al. 2022), inspired our adoption of the most recent diffusion model framework. For a detailed discussion the principles of hyperparameter fine-tuning, readers are encouraged to refer to the previously mentioned studies.
B.5 Model Memory Efficiency
Table 8: Analysis of the GPU memory consumption during the training phase on a single NVIDIA RTX 3090 (24 GB) graphics card, where 00M stands for out-of- memooy. Experiments are performed on the protein datasct that contains 918 graphs, each having node count ranging from 100 500.
Method
#params
BS=1
BS=2
BS=4
BS-8
BS=16
BS=32
GDSS
0.37M
3008M
4790M
8644M
15504M
OOM
OOM
DiGress 18.43M
16344M
19422M
22110M
OOM
OOM
OOM
EDP-GNN 0.09M
7624M
13050M
23848M
OOM
OOM
OOM
Unet
32.58M
6523M
10557M
18247M
OOM
OOM
OOM
PPGN 2.96M
OOM
OOM
OOM
OOM
OOM
OOM
PPGN-PE
3.26M
OOM
OOM
OOM
OOM
OOM
OOM
SwinGNN
15.31M
2905M
3563M
5127M
8175M
14325M
OOM
SwinGNN-L,
35.91M
4057M
5208M
7471M
12113M
21451M
OOM
31

---

Published in Transactions on Machine Learning Research (06/2024)
GPU Memory Usage. Our model's efficiency in GPU memory usage during training, thanks to window self-attention and hierarchical graph representations learning, allows for faster training compared to models with similar parameter counts, In Tab. g we compare the training memory costs for various models with different batch sizes using the real-world protein dataset.
B.6
Comparing against the Tranfroosrrm Baseline
Table 9: Comparing our SwinGNN against the vanilla visual Swin Transformer
Liu et al. 2021
Ego-Small Clus. J
Community-Son
Grid Clus. J
Protein
Methods
Deg.
Ozbit. 4
Deg.
Clus. 4
Orbit.
Deg, J
Orbit.
Deg. 4
Clus. 4
Orbit. 4
SwinGNN
3.61e-1
2.12e-2
3.58e-3
2,98e-3
5.11e-2
4.33e-3
1.91e-7
0.00
6.88e-6
1.88e-3
1.55e-2
2.51e-3
SwinGNN-I.
5.726-3
3.20k-2
5.35e-3
1.42n-3
4.52e-2
6.30e-3
2.09e-6
0.00
9.70e-7
1.19e-3
1.57e-2
8.60e-4
SwinTF
8.50--3
4.42-2
8.00e-3
2.70e-3
7.11e-2
1:30-3
2.50e-3
8.78e-5
1.25e-2
4.99o-2
1.32e-1
1.56e-1
To further demonstrate the effectiveness of our proposed network in handling adjacency matrices for denoising purposes, we include an additional comparison with SwinTranstormer (Liu et al. 2021). Twinnraanffrmer is a general-purpose backbone network commonly used in visual tasks such as semantic segmentation, which also involves dense predictions similar our denoising task.
In experiments, modify the SwinTF + UperNet (Xiao et al. 2018 method and adapt it to output denoising signals. Specifically, we conduct experiments on the various graphs datasets, and the results are presented in Tab. The results clearly demonstrate the superior performance of our proposed SwinGNN model compared to simply adapting the visual TwinTraasfomeer for graph generation.
B.7 Effects of Window Size
Table 10: Effects of window size on SwinGNN modols (grid data).
Grid ((V) E
100 graphs)
Model
Window Size
Deg. 4
Clus. J
Orbit. +
1.46e-1
7.69e-3
2.73e-2
2
3.06e-4
1.75e-4
1.77e-4
SwinGNN (ours)
4
6.60e-5
2.15e-5
3.1le-4
6 (default)
1.91e-7
0.00
6.88e-6
12
1.92o-5
0.00
1.50e-5
Receptive Field Analysis. The window size must be large enough regarding the number of downsampling layers and graph sizes to create sufficient receptive field. Otherwise, the model would perform poorly (e.g.. window size of 1 or 2 in the grid dataset). Let n be the size of the graph and M be the window size. After k iterations of shift-window, the receptive field of each edge token is enlarged k times. The effective receptive field of window attention grows from M x M into kM x kM. With each half-sizing downsampling operator, the self-attention receptive field grows 2 times larger the subsequent window attention layer. Putting these together, assume cach attention layer has & itcrations of window shifting, there are such layers, cach followed by down-sampling operator, the receptive field is (2kM)). When k; M and suitably chosen, it is feasible to ensure the receptive field is larger than the graph size n, meaning that the message passing between any two edge tokens can be approximated by our architecture.
Experimental Results. Tab. 10 summarizes the impact of window size M on empirical performance in the grid benchmark dataset. When M is considerably small relative to the graph size, the performance tends be subpar. Converscly, when M is sufficiently with an appropriate number of layers- it acts more like hyper-parameter, requiring tuning to optimize performance.
the entire graph within the receptive field
32

---

Published in Transactions on Machine Learning Research (06/2024)
B.8 Additional Results on Molecule Datasets
Table 11: QM9 results with novelty metrics.
QM9
Methods
Valid w/o cor.t
Novelty
Uniquet
FCD4
NSPDK]
GraphAF
57.16
81.27
83.78
5.384
2.10e-2
GraphDF
79.33
86.47
95.73
11.283
7.50e-2
GDSS
90.36
65.29
94.70
2.923
4.40c-3
DiGress
95.43
27.69
93.78
0.643
7.28e-4
SwinGNN (scalar)
99.68
15.14
95.92
0.169
4.02e-4
SwinGNN (bits)
99.91
13.60
96.29
0.142
3.44e-4
SwinGNN (onc-hot)
99.71
17.34
96.25
0.125
3.21c-4
SwinGNN-L (scalar)
99.88
13.62
96.46
0.123
2.70e-4
SwinGNN-L (bits)
99.97
10.72
95.88
0.096
2.01e-4
SwinGNN-L (onc-hot)
99.92
11.36
96.02
0.100
2.04c-4
SwinGNN (scalar, novelty-tuning)
97.05
41.01
95.60
0.544
1.95e-3
SwinGNN-L, (scalar, novelty-tuning)
97.24
42.31
96.39
0.380
1.19e-3
Table 12: ZINC250k results with novelty metrics.
ZINC250k
Methods
Valid w/o cor.t
Novelty
Unique
FCD1
NSPDK
GraphAF
68.47
100.0
99.01
16.023
4.40e-2
GraphDF
41.84
100.0
93.75
40.51
3.54c-1
GDSS
97.35
100.0
99.76
11.398
1.80c-2
DiGress
84.94
100.0
99.21
4.88
8.75e-3
SwinGNN (scalar)
87.74
99.38
99.98
5.219
7.52c-3
SwinGNN (bits)
83.50
99.29
99.97
4.536
5.61e-3
SwinGNN (one-hot)
81.72
99.91
99.98
5.920
6.98e-3
SwinGNN-L (scalar)
93.34
95.43
99.80
2.492
3.60e-3
SwinGNN-L (bits)
90.46
95.73
99.79
2.314
2.36e-3
SwinGNN-L (one-hot)
90.68
96.39
99.73
1.991
1.64e-3
SwinGNN (scalar, novelty-tuning) SwinGNN-L (scalar, novelty-tuning)
88.13
100.0
99.94
5.43
7.75e-3
90.78
99.0
99.95
3.68
5.37c-3
Discussion on Novelty Metric. In the main paper, we do not report novelty the molecule datasets following Vignac et al. (2023): Vignac & Frossard (2022). Novelty metric is measured by proportion of generated samples not seen in the training set. The QM9 dataset provides a comprehensive collection of small molecules that meet specific predefined criteria. Generating molecules outside this set. (i.e., novel graphs) does not necessarily indicate that the network accurately capture the underlying data distribution. Further, in ZINC250k dataset, all models show very high novelly, making novelty not distinguishable for model performance.
Morcover, we argue that training the diffusion models is essentially maximizing the lower bound of likeli- hood. Diffusion (i.e., score-based) models are essentially maximum likelihood estimators (MLE) (Hyääineen 2005). Generating samples resembling the training data is actually consistent with the MLE objective, as theoretically the closest model distribution to the training distribution would be the Dirac delta functions of training data. Novelty metric may not be good indicator of model performance on its own. For example, poorly trained generative model may have very high novelty and bad performance.
33

---

Published in Transactions on Machine Learning Research (06/2024)
Results with Novelty Metric. Nevertheless, for the sake of completeness, present additional ex- perimental results including the novelty metrics in the QM9 and ZINC250k molecule datasets, seen in and Tab. 12 In the main experimental section (Tab. 3 the optimization of training hyperparameters is mainly directed towards improving FCD and NSPDK metrics, with the novelty scores presented in the initial rows. When the novelty scores are considered in the hyperparameter tuning, the results for the scalar-encoding SwinGNN models are displayed in the concluding rows, demonstrating that our models still maintain remarkable performance.
On the QM9 dataset (Tab. I1 our model outperforms the DiGress baseline by exhibiting higher novelty and excelling in FCD, no matter if it is fine-tuned for novelty or not. In comparison, GraphAF, GraphDF, and GDSS models, despite their competitive uniqueness and novelty, demonstrate deficiencies in validity, FCD, or NSPDK scores. Specifically, their high novelty suggests the generation of substantial number of new, likely undesirable molecules that violate fundamental chemical principles. This indicative of a significant deviation from the training distribution, as reflected their low validity and elevated FCD and NSPDK scores.
In the ZINC250K dataset (Tab. 12 all models exhibit high novelty, scoring at least 95%. However, the bascline models struggle in aspects of validity, FCD, and NSPDK scores, indicating difficulties in effectively capturing the data distribution. Contrarily, our model (SwinGNN-L) stands out by achieving the best FCD and NSPDK scores when not specifically optimized for novelty. Furthermore, with dedicated tuning, our model's novelty score closely competes with others (e.g., 99.0 vs 100.0), demonstrating a harmonious balance between fostering novelty and maintaining crucial chemical attributes in the generated molecules.
34

---

Published in Transactions on Machine Learning Research (06/2024)
B.9 Additional Qualitative Results
e=5, n=5
e=3, n=4
e=5, n=4
e=3, n=4
e= 10, n=6
e=4, n=4
e= 6, n=6
e=7, n=6
e=4, n=4
e=9, n=10
e=3, n=4
e=18, n=12
e=5, n=6
e=3, n=4
e= n=6
e=9, n=7
Figure 7: Visualization of sample graphs generated by model the ego-small dataset.
e= 1
e=50, n=18
e= n=18
e=21, n=12
e=49, 1=18
5050, n=18
e=26, n=14
e=25, n=14
e=37, n=16
e=37, n=16
e=21, n=12
e=26, n=14
4= 1=18
e=26, n=14
e-60, n=20
e=37, n=16
Figure 8: Visualization of sample graphs generated by model the community dataset.
35

---

Published in Transactions on Machine Learning Research (06/2024)
e=402, n=216
499 n=266
e=646, n=342
e=538, n=285
e=368, n= 198
e=352, n=190
e=333, n=180
e=473, n=252
e=542, n-288
3-389, 2
e1613, n-324
o=437,n=236
e=576, 3-36
e= 609, 3=323
e=463, 2
e= n=228
Figure 9: Visualization of sample graphs generated by our model on the grid dataset.
e=309, 129
e=337, n=133
e=373, n=149
e=374, n=159
e=435, 194
e04 n=162
e=634, n=221
e=463, n=192
e=407, 1=
e=470, n= 183
e=343, 139
e=328, n=146
e=228, 1=1
e=536, n=238
e=392, 15150
e=277, n-114
Figure 10: Visualization of sample graphs generated by our model on the DD protein dataset.
36

---

Published in Transactions on Machine Learning Research (06/2024)
OH
OH
Figure 11: Visualization of sample graphs generated by our model on the QM9 molccule datasct.
lotd
Figure 12: Visualization of sample graphs generated by our model on the ZINC250k molecule dataset.
37


Reviews:
[{"review_id": "l2gi5jKfaH", "reviewer": "Reviewer_gRVi", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n1. The paper offers valuable insights, both theoretical and empirical, into the potential limitations of permutation-invariant models and the necessity for invariant sampling. These findings hold significant importance for future design considerations.\n2. Building upon these insights, the authors introduce SwinGNN, a non-invariant framework designed to enhance performance and efficiency in capturing intricate real-world graph distributions while ensuring sampling invariance.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "⁤This paper aims to develop a graph generation model that addresses the limitations of permutation-invariant diffusion models. ⁤⁤Initially, the authors analyze the performance of existing invariant models. ⁤⁤They identify a degradation in performance due to restrictive architectures and an increased number of target distribution modes. ⁤⁤This analysis highlights the need for a more flexible approach. ⁤⁤Subsequently, the authors introduce SwinGNN, a GNN that maintains permutation-invariant sampling without being invariant and utilizes shifted-window self-attention to enhance scalability for large graphs. ⁤⁤Empirical results demonstrate SwinGNN's superiority over existing methods across synthetic and real-world datasets.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I'm intrigued by how the theories presented in this paper might apply to graphs constructed using radial cutoffs. Unlike graphs generated by sampling adjacency matrices, these graphs are created by sampling node coordinates and constructing adjacency matrices based on pairwise distances between sampled nodes. Does the theory in this paper suggest that we need to reconsider the design of such architectures too? Alternatively, could the paper offer a clear explanation of the scope of diffusion models, specifically outlining the implications of the theory it covers?", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "7jQK496YN8", "reviewer": "Reviewer_Asq3", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths:\n\n1. The research provides both theoretical analysis and empirical evidence. The theory part is clear and well-written. SwinGNN uses a simple random permutation technique that ensures invariant sampling without the need for an invariant loss, providing flexibility in model architecture design.\n\n2. The paper has conducted extensive experiments to compare SwinGNN with other baselines. For instance, this paper highlights that SwinGNN maintains a balance between fostering novelty and preserving important chemical properties in molecule generation, outperforming other models in validity, FCD, and NSPDK scores, especially in the QM9 dataset. SwinGNN is noted to be memory-efficient during training, which is crucial for practical deployment and experimentation on various graph sizes and types.\n\n\n### Weaknesses:\n\nThe presentation in Section 5.1 about the derivation of the architecture of SwinGNN needs to be expanded. There should be a brief introduction of $k$-order GNN and the $k$-WL GNN for readers unfamiliar with these concepts. Explaining these concepts would lay the groundwork for why SwinGNN’s architecture is structured the way it is, and why certain architectural choices were made, such as using shifted window-based self-attention to approximate the 2-WL message passing. Besides, there should be more details about the comparison between SwinGNN and Swin Transformers to show the expressivity of the SwinGNN.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper first establishes that the degradation in performance for permutation-invariant diffusion models of graphs is not only due to restrictive architecture designs but also because of the increasing modes of target distributions. Then, the authors introduce SwinGNN, a non-invariant diffusion model. SwinGNN incorporates an efficient 2-WL message-passing network using the novel shifted-window-based self-attention mechanism from SwinGNNs, which allows it to scale and generate large graphs effectively. Additionally, the paper demonstrates that random permutation of generated graphs can be a simple yet effective technique to achieve permutation-invariant sampling without necessarily relying on an invariant loss function. The authors have presented many experiments to validate the performance of SwinGNN, which showed that it outperforms existing methods by a significant margin on both synthetic and real-world datasets, including protein and molecule datasets, and it can be conducted more efficiently than other baselines.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Can you explain the notation $\\mathcal{N}(\\tilde{A};A,\\sigma^2I)$?\n\n2. In Figure 2, did you train the models with the same hyperparameters for all different $l$? How do you choose distinct permutation matrices $P_1,\\ldots,P_l$ in the experiments?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "y6BNoWon1V", "reviewer": "Reviewer_hsNm", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\nThe paper tackles an important problem of graph generation and studies the interesting phenomenon of equivariance and invariance in the generation process. \n\nThe paper presents a simple and interesting argument for why equip/invariance might be a bad thing. \n\nThe proposed method seems to do well. \n\n**Weaknesses**\n\nI think the writing of the paper could be improved. Specifically since TMLR doesn't have a page limit. In particular I think section 5.2 needs a lot of details, specially the two sections on the self conditioning and the stochastic sampler. \n\nThe other weaknesses (sort of the related to the first) is it is unclear to me why the network has certain features. Specifically, \n\n1) The locality window are completely arbitrary and do not reflect locality on the graph. The splitting along even and odd party indexes does not help with this. Why is this is a reasonable thing to do?\n\n2) The loss function in Equation 4. The paper mentions that at $t=T$, this is pure Gaussian noise, however, it is still just a picture of Gaussian, just with bigger variance. Shouldn't the means be updated through time as well?\n\n3) The self conditioning and the sampler need more details. \n\nHence, it is not clear to me what is new in the paper. \n\n**Questions**\n\nIf the network were invariant and not equivariant. Would this alleviate the problem?\n\nThe arguments for the modes only works for methods that find the density of the model right - such as diffusion models, and flow based models. It does not apply to methods (eg. GANS) that do not do density estimation right?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper looks at the problem of generating graphs. The paper claims that due to the permutation invariance of the graph, this problem is significantly challenging. In particular, prior work has attempted to tackle this by using a permutation equivariant neural network and a permutation invariant loss function.\n\nHowever, the paper claims that this is suboptimal. The reason provided is that for most datasets, we only see one instance (not all permutations). Then due to the permutation invariance the model \"incorrectly\" assigns non-zero probabilities to the permutations. Further, if we try to correct this by adding the permutations to the dataset, we create too many modes and hence make optimization difficult. \n\nThe paper then proposes an architecture and tests it for real and synthetic datasets. The paper compares against a variety of different methods and shows and improvement.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the weaknesses and add more details about the model and the training process.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The three reviewers agree that the paper is relevant to the TMLR community and make substantial substantial contributions that may prove useful for future design considerations within diffusion models. The round of reviews and revisions made to the paper improved its quality and clarity.
Decision: Accept (poster)