Pard: Permutation-Invariant Autoregressive Diffusion for Graph Generation
Authors: Lingxiao Zhao
Xueying Ding
Leman Akoglu
Venue: NeurIPS 2024 poster (2024)
Keywords: diffusion
generative model
graph generation
graph generative model
Primary area: generative_models
TL;DR: Combining autoregressive method with diffusion for modeling graph distribution with SOTA graph generation performance.

Abstract: Graph generation has been dominated by autoregressive models due to their simplicity and effectiveness, despite their sensitivity to ordering. Yet diffusion models have garnered increasing attention, as they offer comparable performance while being permutation-invariant. Current graph diffusion models generate graphs in a one-shot fashion, but they require extra features and thousands of denoising steps to achieve optimal performance. We introduce PARD, a Permutation-invariant Auto Regressive Diffusion model that integrates diffusion models with autoregressive methods. PARD harnesses the effectiveness and efficiency of the autoregressive model while maintaining permutation invariance without ordering sensitivity. Specifically, we show that contrary to sets, elements in a graph are not entirely un-ordered and there is a unique partial order for nodes and edges. With this partial order, PARD generates a graph in a block-by-block, autoregressive fashion, where each block’s probability is conditionally modeled by a shared diffusion model with an equivariant network. To ensure efficiency while being expressive, we further propose a higher-order graph transformer, which integrates transformer with PPGN (Maronet al., 2019). Like GPT, we extend the higher-order graph transformer to support parallel training of all blocks. Without any extra features, PARD achieves state-of-the-art performance on molecular and non-molecular datasets, and scales to large datasets like MOSES containing 1.9M molecules.

PARD: Permutation-invariant satrri--- Diffusion for Graph Generation
Lingxiao Zhao Carnegie Mellon University 1ingxiaozlx@gmail. com
Xueying Ding Carnegie Mellon University xding20andrew cmu, edu
Leman Akoglu Carnegie Mellon University
lakoglu@andrew cmu. edu
Abstract
Graph generation has been dominated by autoregressive models due to their sim- plicity and effectiveness, despite their sensitivity to node ordering. Diffusion models, on the other hand, have garnered increasing attention as they offer com- parable performance while being permutation-invariint,, Current graph diffusion models generate graphs in a one-shot fashion, however they require extra features and thousands of denoising steps achieve optimal performance. We introduce PARD, a diffusion models with autoregressive methods. PARD harnesses the effective- ness and efficiency of the autoregressive model while maintaining permutation invariance without order sensitivity. Specifically, we show that contrary sets, elements in a graph are not entirely unordered and there is unique partial or- der for nodes and edges. With this partial order, PARD generates graph in a block-by-block autoregressive fashion, where each block's probability is condi- tionally modeled by shared diffusion model with an equívariant network. To ensure efficiency while being expressive, we further propose higher-order graph transformer, which integrates transformer with PPGN. Like GPT, we extend the higher-order graph transformer to support parallel training of all blocks. Without any extra features, PARD achieves saute-of-the-ree performance on molecular and non-molecular datasets, and scales to large datasets like MOSES containing 1.9M molecules. PARD is open-sourced at https: : // thub. com/ /emm//ingxiii LingxiaoSaasn/ aoShasn/Pard
AutoRegressive Diffusion model that integrates
Introduction
Graphs provide a powerful abstraction for representing relational information in many domains, including social networks, biological and molecular structures, recommender systems, and networks of various infrastructures such as computers, roads, etc. Accordingly, generative models of graphs that learn the underlying graph distribution from data find applications in network science [7]. drug discovery [26, 42], protein design [1, 43), and various use-cases for Internet of Things [10]. Importantly, they serve as a prerequisite building generative foundation model [6] for graphs.
Despite significant progress in generative models for images and language, graph generation is uniquely challenged by its inherent combinatorial nature. Specifically: 1) Graphs are naturally high-dimensional and discrete with varying sizes, contrasting with the continuous space and fixed- objects,
size advancements that cannot be directly applied here; Being permutation-invariie exchangeable probability distribution, where permutations of nodes
graphs require modeling and edges do not alter a graph's probability: and 3) The rich substructures in graphs necessitate an expressive model capable of capturing higher-order motifs and interactions. Several graph generative models have been proposed to address (part of) these challenges, based on various techniques like autoregression [48, 28), VAEs [37], GANs [11], flow-based methods [36], and denoising diffusion [32, 44). Among these, autoregressive models and diffusion models stand out with superior performance, thus significant popularity. However, current autoregressive models, while
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

efficient, are sensitive to node/edge order with non-exchangeable probabilities; whereas diffusion models, though promising, are less efficient, requiring thousands of denoising steps and extra nodeledgeegrrah--eeee features (structural and/or domain-specific) to achieve high generation quality,
In this paper, we introduce PARD (leopard in Ancient Greek), the first Permutation-invariant AutoRegressive Diffusion model that combines the efficiency of autoregressive methods and the quality of diffusion models together, while retaining the property of exchangeable probability. Instead of generating an entire graph directly, we explore the direction of generating through block-wise graph enlargement. Graph enlargement offers a fine linegrained control over graph generation, which can be particularly advantageous for real-world applications that require local revisions to generate graphs. Moreover, it essentially decomposes the joint distribution of the graph into a series of sim- pler conditional distributions, thereby leveraging the data efficiency characteristic of autoregressive modeling. We also argue that graphs, unlike sets, inherently exhibit unique partial order among nodes, naturally facilitating the decomposition of the joint distribution. Thanks to this unique partial order, PARD'S 's block-wise autoregressive sequence is coomuutaiioninvariinn unlike any prior graph autoregressive methods in the literature.
To model the conditional distribution of nodes and edges within a block, we have, for the first time, identified a fundamental challenge in equivariant models for generation: it is impossible for any equivariant model, no matter how powerful, to perform general graph transformations without symmetry breaking. However, through diffusion process that injects noise, a permutation equivariant network can progressively denoise to realize targeted graph transformations. This approach inspired by the annealing process where energy is initially heightened before achieving stable state, akin to the process of tempering iron. Our analytical findings naturally lead to the design of our proposed PARD that combines autoregressive approach with local block-wise discrete denoising diffusion. Using a diffusion model with equivariant networks ensures that each block's 's conditional distribution is exchangeable. Coupled with the permutation-invarian block sequence, this renders the entire process coomutation-inaariann and the joint distribution exchangeable. What is more, this inevitable combination of autoregression and diffusion successfully combines the strength of both approaches while getting rid of their shortcomings: By being permutation -nvvrriant,, a key advantage of diffusion, it generalizes better than autoregressive models while also being much more data-efficient. By decomposing the challenging joint probability into simpler conditional distributions, an advantage of autoregression, it requires significantly fewer diffusion steps, outperforming pure diffusion methods by a large margin. Additionally, each inference step in the diffusion process incurs lower computational cost by processing only the generated part of the graph, rather than the entire graph. And it can further leverage caching mechanisms (to be explored in future) to avoid redundant computations.
Within PARD, we further propose several architectural improvements. First, to achieve 2-FWL expressivity with improved memory efficiency, we propose a higher-order graph transformer that integrates transformer with PPGN [30], while utilizing& significantly reduced representation size for edges. Second, to ensure training efficiency without substantial overhead compared to the original diffusion model, we design GiT-like causal mechanism to support parallel training of all blocks. These extensions are generalizable and can lay the groundwork for a higher-order GPT.
PARD achieves new SOTA performance on many molecular and non-molecular datasets without any extra features, significantly outperforming DiGress [44]. Thanks efficient architecture and parallel training, PARD scales to large datasets like MOSES [33] with 1.9M graphs. Finally, not only PARD can serve as a generative foundation model for graphs in the future, its autoregressive parallel mechanism can further be combined with language models for language-grapp generative pretraining.
2 Related Work
Autoregressive (AR) Models for Graph Generation. AR models create graphs step-hy-step, adding nodes and edges sequentially. This method acknowledges graphs' discrete nature but faces a key challenge there is no inherent order in graph generation. To address this, various strategies have been proposed to simplify orderings and approximate the marginalization over permutations; i.c. p(G' = Emerio p(G,*), Li et al. [27] propose using random or deterministic empirical orderings. GraphRNN [48] aligns permutations with greadth-first-eean
(BFS) ordering, with many-to-ore to-one mapping. GRAN [28] offers marginalization over a family of canonical node orderings, including node degree descending, DFS/BFS tree rooted at the largest degree node, and k-core ordering. GraphGEN [16] uses a single canonical node ordering, but does not guarantee the same
2

---

canonical ordering during generation. Chen et al. [9] avoid defining ad-hoc orderings by modeling the conditional probability of orderings, p( p(T[G), with a trainable AR model, estimating marginalized probabilities during training to enhance both the generative model and the ordering probability model.
Diffusion Models for Graph Generation. EDP-GNN [32] is the first work that adapts score matching [39] to graph generation, by viewing graphs as matrices with continuous values. GDSS [24] generalizes EDP-GNN by adapting SDE-based diffusion [40] and considers node and edge features. Yan et al. [46] argues that learning exchangeable probability with equivariant networks is hard, hence proposes cormmutaaiio-senssttii SwinGNN with continuous-stan score matching. Previous works apply continuous-state diffusion to graph generation, ignoring the natural discreteness of graphs. DiGress [44] the first to apply discrete-state state diffusion [3, 20] to graph generation and achieves sigmificant improvement. However, DiGress relies on many additional structural and domain -peaii-specific features. GraphArm [25] applies Autoregressive Diffusion Model (ADM) [21] to graph generation, where exactly one node and its adjacent edges decay to the absorbing states at each forward step based on random node order. Similar to AR models, GraphArm is permutation sensitive.
We remark that although both are termed "autoregressive diffusion", it is important to distinguish that PARD is not ADM. The term "autoregressive diffusion" in our context refers the integration of autoregressive methods with diffusion models. In contrast, ADM represents specific type of discrete denoising diffusion where exactly one dimension decays to an absorbing state at time in the forward diffusion process. See Fan et al. [13] for survey of recent diffusion models on graphs
3 permuttationinvariian Autoregressive Denoising Diffusion
We first introduce setting and notations. We focus on graphs with categorical features. Let G = EV.E) be a labeled graph with the number of distinct node and edge labels denoted K, and Ke, respectively, Let o' {0, 1)Kk,, Vi E V be the one-hot encoding of node i's label. Let e E {0, 10k,, Vi, e V be the one-hot encoding of the label for the edge between node and j. We also represent "absence of edge" as type of edge label, hence El |V| x [ Let E {0, 13 / and E (0, 1) Vix[V|X be the collection of one-hot encodings of all nodes and edges using the default node order, and let G: (V, E). To deseribe probability, let x be a random variable with its sampled value æ. Similarly, G random graph with its sampled graph G. In diffusion process, noises are injected from t=0 to t=I' with T being the maximum time step. Let Xg ~ Pasta (Xo) be the random variable of observed data with underlying distribution Pdama (xo). X₁ ~ q(x,) be the random variable at time t, and let Xt|s ~ ((x((x)) denote the conditional random variable. Also, we interchangeably use g(x, Xx.). (x.=0; xx= and (1,, æ:)) when there is no ambiguity. We model the forward diffusion process independently for each node and edge, while the backward denoising process is modeled jointly for all nodes and edges. All vectors are column-wise vectors. Let (1,)) denote inner product.
3.1 Discrete Denoising Diff'usion on Graphs
Denoising Diffussin is first developed by Sohl-Dickstein et al. [38] and later improved by Ho et al. [19]. It is further generalized to discrete-state case by Hoogeboom et al. [20] and Austin et al. [3]. Taking a graph Gu example, diffusion model defines a forward diffusion process to gradually inject noise to all nodes and edges independently until all reach a non-informative state Gy. Then, denoising network is trained to reconstruct Go from the noisy sample G, at each time step, by optimizing a Variational Lower Bound (VLB) for log pa (o). Specifically, the forward process is defined Markov chain with GG./). Vi [1, T). and the backward denoising process is parameterized with another Markov chain pe (r-]( Vt e [1,7]. Note that while the forward process independently applied to all elements, the backward process is coupled together with conditional independence assumption. Formally,
[GG
II alvilvi II a(e/"%e,2 (2222) G.) II *EV
po (vi_ G.) II
pa (e 1. (G)
ieV
SJEV
LeE
Then, the VLB of log (G.) can be written (see Apdx.$A.I) as
log (Go)) > (g(G) [og
Dia.
Buccyass [Dra Go)llpoGGG G.)]
-C,(0)
2,(0)
(2)
where Eprirr R 0, since po (GT) Ra (GG) is designed as a fixed noise distribution that is easy to sample from. To compute Eq. (2), we need to formalize the distributions (1) g(Gr|Go) and (i)
3

---

g(Ge-I/G, Go), as well as (iit) the parameterization of Po DiGress [44] applies D3PM [3] define these three terms. Different from DiGress, we closely follow the approach in Zhao et al. [52] to define these three terms, as their formulation is simplified with improved memory usage and loss computation. For brevity, we refer readers to Appx. $A.2 for the details. Notice that while neural network can directly be used to parameterize (iil) po (G---/G,)) we follow [52] to parameterize pe (Go|G.) instead, and compute (iit) from pe (G))
With (i ~ in known, one can compute the negative VLB loss in Eq. (2) exactly. In addition, at each time step t, the cross entropy (CE) loss between (i) g (Gu) and po Go|G,) that quantifies reconstruction quality is often employed as an auxiliary loss, which is formulated as
CO (0) = /G
Σ
log (vo G.) + Σ log logpe(e' 4 [G]]
iEV
ijEV
In fact, DiGress solely uses (0) to train their diffusion model. In this paper, we adopt hybrid
loss [3], that is (0) + AC with À = 0.1 at each time i, as we found it to help reduce overfitting. To generate graph from pa (n), pure noise graph is first sampled from pa (G7) and gradually denoised using the learned po GG G+) from step T to
A significant advantage of diffusion models is their ability to achieve exchangeable probability in combination with permutation equivariant networks under certain conditions [45]. DiGress is the first work that applied discrete denoising diffusion to graph generation, achieving significant improvement over previous continuous-str nature of graphs and their complex internal dependencies, modeling the joint distribution of all nodes and edges directly presents significant challenges. DiGress requires thousands of denoising steps to accurately capture the original dependencies. Moreover, DiGress relies on many extra supplementary node and graph-level features, such as cycle counts and eigenvectors, to effectively break symmetries among structural equivalences to achieve high performance.
based diffusion. However, given the inherently tigh-dimensional
3.2 Autoregressive Graph Generation
Order is important for AR models. Unlike diffusion models that aim to capture the joint distribution directly, AR models decompose the joint probability into a product of simpler conditional probabilities based on an order. This makes AR models inherently suitable for ordinal data, where a natural order exists, such in natural languages and images.
Order Sensitivity. Early works of graph generation contain many AR models like GraphRNN [48] and GRAN [28] based on non-deterministic heuristic node orders like BFS/DFS and k-core ordering. Despite being permutation sensitive, AR models achieve SOTA performance on small simulated structures like grid and lobster graphs. However, permutation invariance is necessary for estimating an accurate likelihood of a graph, and can benefit large-size datasets for better generalization.
Let π denote an ordering of nodes. To make AR urder-insensitive there are two directions: (I) Modeling the joint probability p(G, T) and then marginalizing π. (2) Finding unique canonical order T (G) for any graph G such that p(T G) 1 if π = π (G) and 0 otherwise. In direction (1), directly integrating out π is prohibitive as the number of permutations is factorial in the graph size. Several studies [27, 9, 28] have used subsets of either random or canonical orderings. This approach aims to simplify the process, but results in approximated integrals with indeterminate errors. Moreover, it escalates computational expense due to the need for data augmentation involving these subsets of orderings. In direction (2), identifying a universal canonical order for all graphs is referred to as graph canonicalization. There exists no polynomial time solution for this task on general graphs, which is at least as challenging as the NP-intermediate Graph Isomorphism problem [2]. Goyal et al. [17] explored using minimum DFS code to construct canonical labels for specific dataset with polyyoomlill time complexity. However, the canonicalization is specific to each training dataset with the randomness derived from DFS. This results in generalization issue, due to the canonical order being π GrariinSet) instead of (G).
The Existence of Partial Order. While finding unique order for all nodes of a graph is NP. intermediate, we argue that finding a unique partial order, where certain nodes and edges are with the same rank, is easily achievable. For example, trivial partial order is simply all nodes and edges having the same rank. Nevertheless, a graph is not the same as a set (a set is just graph with empty E). where all elements are essentially unordered with equivalent rank. That is because a non-empty graph contains edges between nodes, and these edges give different structural properties to nodes. Notice that some nodes edges have the same structural property as they are structurally equivalent.

---

Algorithm Structural Partial Order e
1: Input: Graph G. maximum hops Ka.
2: Init: Go = G. x= 0, & with Φ(v) = 0 Ve.
3: while G2 is not 0 do
G G
a|Bis, Bissal]
4: Compute wx, (v), Ve V(G.), using Eq. (4),
Find all nodes C with wX2 vic) wxy, (v).
Figure 1: Example case where the equiv- ariant graph transformation from G[B to G G[B is impossible for any permutation- equivariant network due to structural equiva- lence of nodes. See Proposition 3.3.
6: Let ((b) = i Vu E C.
7: Gi+1 & (G) c1iti44.
8:
end while
9:
Output: @ i- +
We view each structural property color, and rank all unique colors within the graph define the partial order over nodes, which we call a structural partial order. The structural partial order defines a sequence of blocks such that all nodes within a block have the same rank (i.e. color).
Let Ø: V [l,.... Kn] be the function that assigns rank to nodes based on their structural properties, where Kn denotes the maximum number of blocks. We use C[S] to denote the induced subgraph on the subset C V. There are many ways to assign rank to structural colors, however we would like the resulting partial order to satisfy certain constraints. Most importantly, want
Vr E [I,...,k]]
G(o(V) S r] is a connected graph.
The connectivity requirement is to ensure a more accurate representation of real-world graph genera- tion processes, where it is typical of real-world dynamic graphs to enlarge with newcoming nodes being connected at any time, Then, one can sequentially remove all nodes with the lowest degree to maintain this connectivity and establish partial order. However, degree only reflects limited information of the first-hop neighbors, and many nodes share the same degree- leading to only a few distinct blocks, not significantly different from a trivial, single-block block approach.
To ensure connectivity while reducing rank collision, we consider larger hops to define a weighted degree. Consider maximum of K₁ hops. For any node E V, the number of neighbors at each hop of v can be easily obtained as [d1 (v), ...., dx, (1)) We then define the weighted degree as
Kn.
WK, (v) = Σ dx< x Ka-Ka
A=1
Equation Eq. (4) may appear as an ad-hoc design, but it fundamentally serves as a hash that maps the vector (v), dz(v),... dx (v)] to a unique scalar value. This mapping ensures one-to-one correspondence between the vector and the scalar. Furthermore, it prioritizes lower- hop degrees over higher-hop degrees, akin how e.g. the number "123" is represented as x 102 + 2 10 + 3 x 10". Eq. (4) is efficient to compute and guarantees: 1) Nodes have the same rank if and only if they have the same number of neighbors up to K₂, hops. 2) Lower-hop degrees are weighted more heavily. With wk, defined, we present our structural partial order in Algo. 1.
Proposition 3.1. For any G, its structural partial order & defined by Algo. 1 is permutation ((G) for any permutation operator P.
equivariant, such that @ G)
is easy to prove Prop. 3.1. Algo. I shows that (ii) for Vi E V is uniquely determined by node i's structural higher-order degree. As nodes' higher-order degree is permutation equivariant, & is also permutation equivariant. Notice that é is unique and deterministic for any graph.
Autoregressive Blockwise Generation. é in Algo. with output in range [1, K&) divides the nodes (G) into Kn 9 blocks [B, ...; BKg order, where B, (i E V(G) = =] Let B1s == ,
be the union of the first i blocks. PARD decomposes the joint probability of a graph G into
Ka
(G) = III pe (G|B..) \ G[B G[B 1=1
(5)
where G[Br:o] is defined as the empty graph, and G[B G[B denotes the set of nodes and edges that are present in G[B but not in G(B All of them are represented in natural order of G. As each conditional probability only contains subset of edges and nodes, and having access to all previous blocks, this conditional probability is significantly easier to model than the whole joint probability. Given the property Prop. 3.1 of B., it is easy to verify that po (G) is exchangeable with permutation-invariant probability for any G if and only if all conditional probabilities are exchangeable. See Appx. $A.6 for details of permutation-invarian
probability. Note that while
GRAN [28] also generates graphs bock-by-block all nodes within GRAN have different generation
5

---

ordering, even within the same block (it breaks symmetry for the problem identified later). Essentially, GRAN an autoregressive method and, as such, suffers from all the disadvantages inherent to AR.
3.3 Impossibility of Equivariant Graph Transformation
In Eq. (5), need to parameterize the conditional probability po (G[B1a) \ G[B G(B to be permutation-invarian This can be achieved by letting the conditional probability be
po [Baa]
G[B
II
po
G[B ([
(6)
X (G
where x is any node and edge in G[B].s] \. G[Bra-1], 0 denotes an empty graph, hence G[B U 0 [B.]]]] depicts augmenting G[B with empty (or virtual) nodes and edges to the same size as
G[Bra)) With the augmented graph, we can parameterize (x G[B U ((B=sl) for any node
and edge x with a permutation equivariant network to achieve the required permutation invariance. For simplicity, let G - [B:] G[B [[.
The Flaw in Equivariant Modeling. Although the parameterization in Eq. (6) along with an equivariant network makes the conditional probability in Eq. (5) become permutation commmuttiioninvaiinntt
have found that the equivariant graph transformation pe (x G G[B | ) cannot be achieved in general for any permutation equivariant network, no matter how powerful it is (!) For definition of graph transformation, see Appx.$A.7. The underlying cause is the symmetry of structural equivalence. which is also problem in link prediction [41, 49). Formally, let A(G) be the adjacency matrix of G (ignoring labels) based on G's default node order, then an automorphism a of G satisfies
(G) A(a G)
where a G is a reordering of nodes based on the mapping a. Then the automorphism group is Aut(G) for E P A(G) = A(o G}}
(8)
where F,, denotes all permutation mappings for size n. That is, Aut(G) contains all automorphisms of G. For a node of G. the orbit that contains node i is defined as
o(i) (i) Vo E Aut(G))
In words, the orbit oi) contains all nodes that are structurally equivalent to node in G. Two edges (i,5) and (u, v) are structurally equivalent if 3o E Aut(G)) such that oii) and o(j) = t. Theorem 3.2. Any structurally equivalent nodes and edges will have identical representations in any equivariant network, regardless of its power or expressiveness.
See proof in AA.5. Theorem 3.2 indicates that no matter how powerful the equivariant network is, any structually equivalent elements have the same representation, which implies the following. Proposition 3.3. General graph transformation is not achievable with any equivariant model.
Proof. To prove it, we only need to show there are many "bottleneck" cases where the transformation cannot be achieved. Fig. 1 shows case where G[B,.] is 4-cycle, and the next target block contains two additional nodes, each with a single edge connecting to one of the nodes of G[B,). It is easy to see that nodes 1-4 all structurally equivalent, and so are nodes 6 in the augmented case (middle). Hence, edges in ((5, V) E [1, 4]} are structurally equivalent (also {(6, i) IVi E [1, 4]). Similarly, Vi E [1, 4), edge (5, and (6, are structurally equivalent. Combining all cases, edges in {G. i)lvi E []. E {5, 6}} are structurally equivalent. Theorem 3.2 states that all these edges would have the same prediction, hence making the target G[B1++1] 1] not achievable.
3.4 PARD: Autoregressive Denoising Diffusion
The Magic of cannot be transformed to a target graph with fewer automorphisms. We hypothesize that a graph with lower "energy" is hard to be transformed to a graph with higher "energy" with equivariant networks. There exist some definitions and discussion of graph energy [18, 4] based on symmetry and eigen-information to measure graph complexity, where graphs with more symmetries have lower energy. The theoretical characterization of the conditions for successful graph transformation is a valuable direction, which we leave for future work investigate.
In Fig. 1 we showed that graph with many automorphisms
Based on the above hypothesis, to achieve a successful transformation of a graph into a target graph, it is necessary to increase its energy. Since graphs with fewer symmetries exhibit higher energy levels, our approach involves adding random noise to nodes and edges. Our approach of elevating the energy level, followed by its reduction to attain desired target properties, mirrors the annealing process.

---

Autoregressive Blockwiise Generation
a (m
af [Baa
G. a
Local Denoising Dillusion
2-1
PT-
Figure 2:
PARD integrates the autoregressive method with diffusion modeling. (top) PARD decom- poses the joint probability into series of block-wise enlargements, where each block's conditional distribution is captured with a shared discrete diffusion (bottom).
Diffusion. This further motivates us to use denoising diffusion to model (x G G[B [8.1]) it naturally injects noise in the forward process, and its backward denoising process is the same as annealing. As we show below, this yields po (G) in Eq. (5) to be permutation-invariant
Theorem 3.4. PARD is permulation-innaaiian such that Po x G) po (G) A permutator P.
The proof is given in Appx. $A.6. With all constituent parts presented, we summarize our proposed PARD, the first permutation-invariae autoregressive diffusion model that integrates AR with denoising diffusion. PARD relies on unique, permutation equivariant structural partial order ó (Algo. 1) to decompose the joint graph probability to the product of simpler conditional probabilities, based on Eq. (5). Each block's 's conditional probability is modeled with the product of conditional block size probability and a conditional block enlargement probability as in Eq. (6), where the latter for every block is shared discrete denoising diffusion model as described in $3.1. Fig. illustrates PARD'S two parts: (top) block-wise AR and (bottom) local denoising diffusson at each AR step.
Notice that there are two tasks in Eq. (6); one for predicting the next block's size, and the other for predicting the next block's 's nodes and edges with diffusion. These with a single network, although for better performance we use two different networks. For each block's s diffusion model, we set the maximum time steps to 40 without much tuming.
tasks can be trained together
Training and Inference. We provide the training and inference algorithms for PARD in Apdx.$A.8 Specifically, Algo. 2 is used to train next block's size prediction model; Algo. 3 is used train the shared diffusion for block conditional probabilities; and Algo. 4 presents the generation steps.
4 Architecture Improvement
PARD is a general framework that can be combined with any equivariant network. Nevertheless, would like equivariant network with enough expressiveness to process symmetries inside the generated blocks for modeling the next block's conditional probability. While there are many expressive GNNs like subgraph GNNs [5, 50] and higher-order GNNs [51, 31], PPGN [30] is still natural choice that models edge (2-tuple) representations directly with 3-WL expressivity and O(n²) complexity in graph size. However, PPGN's memory cost is relatively high for many datasets.
4.1 Efficient and Expressive Higher-order Transformer
To enhance the memory efficiency of PPGN while maintaining the expressiveness equivalent to the 3- Weisfeiler-Lehman (3-WL) test, we introduce a hybrid approach that integrates Graph Transformers with PPGN. Graph Transformers operate on nodes as the fundamental units of representation, offering better scalability and reduced memory consumption (O(n²) compared PPGN. PPGN utilizes edges as their primary representation units and therefore incurs significantly higher memory requirements (O(n))) However, the expressiveness of Graph Transformers (without position encoding) limited to the 1-WL. test [8]. By combining these two models, we can drastically decrease the size of edge representations while allocating larger hidden sizes nodes. This synergistic approach not only substantially lowers the memory footprint but also enhances overall performance, leveraging the
7

---

strengths of both architectures to achieve balance between expressivity and efficiency. We provide the detailed design App..$A.9. Note that we use GRIT [29] as the graph transformer block.
4.2 Parallel Training with Causal Transformer
As shown in Eq. (5), for graph G, there are KB conditional probabilities being modeled by shared diffusion model using a 0-parameterized network fe. By default, these K3 number of inputs [G( Kn 1) are viewed as separate graphs and the representations during network passing fo(G (1))) for different i E [1, K Kg] are not shared. This leads to a scalability issue; in effect enlarging the dataset by roughly Kg times and resulting in KB times longer training.
To minimize computational overhead, it is crucial to enable parallel training of all the KB conditional probabilities, and allow these processes to share representations, through which we can pass the full graph G to the network fo only once and obtain all KB conditional probabilities. This is also key advantage of transformers over RNNs. Transformers (GPTs) can train all next-token predictions simultaneously with representation sharing through causal masking, whereas RNNs must train sequentially. However, the default causal masking of GPTs is not applicable to our architecture, as PARD contains both Transformer and PPGN where the PPGN's causal masking is not designed.
To ensure representation sharing without risking information leakage we first assign "block ID" to every node and edge within graph G. Specifically, for every node and edge in G -[B we assign the ID equal to i. To prevent information leakage effectively, it is crucial that any node and edge labeled with ID i are restricted to communicate only with other nodes and edges whose ID) is I i. Let A, E R and E RR. There are mainly two non-elementwise operations in Transformer and PPGN that have the risk of leakage: the attention-vector product operation Ax of Transformer, and the matrix-matris product operation AB of PPGN. (We ignore the feature dimension of A and as it does not affect the information leakage.) Let M E {0, 1] | be a mask matrix, such that i) 2 block_ID j) else O. One can verify that
Maj = if
(10) generalize Ax and AB respectively and safely bypass information leakage. We provide more details of parallel training and derivation of Eq. (10) Appx. 1A. We use these operations in our network and enable representation sharing, along with parallel training of all K blocks for denoising diffusion as well as next block size prediction. In practice, these offer more than 10x speed-up speddup, and the parallel training allows PARD to scale to large datasets like MOSES [33].
(A Φ M)x, and (A@M) + A(B & M - (A M) O M
5 Experiments
We evaluate PARD on 8 diverse benchmark datasets with varying sizes and structural properties, including both molecular (55.1) and non- non-molecular/geeeric ($5.2) graph generation. A summary of the datasets and details are in Appx. $A.11. Ablations and runtime measures are in Appx. $2
5.1 Molecular Graph Generation
Datasets. We experiment with three different molecular datasets used across the graph generation literature: (1) QM9 [34] (2) ZINC250K [23], and (3) MOSES [33] that contains more than 1.9 million graphs. We use a 80%-20% train and test split, and among the train data we split additional 20% as validation. For QM9 and ZINC250K, we generate 10,000 molecules for stand-alone evaluation, and on MOSES we generate 25,000 molecules.
The literature has not been consistent in evaluating molecule generation on well-adopted benchmark datasets and metrics. Among baselines, DiGress [44] stands out as the most competitive. We also compare to many other baselines shown in tables, such as GDSS [24] and GraphARM [25].
Baselines.
Metrics. The literature has adopted number of different evaluation metries that are not consistent across datasets. Most common ones include Validity (f). Uniqueness (1) (frac. of valid molecules that are unique), and Novelty (f) (frac. of valid molecules that not included in the training set). For QM9, following earlier work [44], we report additional evaluations w.r.t. Atom Stability (1) and
Molecule Stability (f), as defined by [22], whereas Novelty is not reported explained in [44]. On ZINC250K and MOSES, we also measure the Fréchet ChemNet Distance (FCD) (L) between the generated and the training samples, which is based on the embedding learned by ChemNet [27]. For MOSES, there are three additional measures: Filter (1) score is the fraction of molecules passing the same filters as the test set, SNN (1) evaluates nearest neighbor similarity using Tanimoto Distance, and Scaffold similarity (1) analyzes the occurrence of
scaffolds [33].
8

---

Table I: Generation quality on QM9 with explict
Table 2: Generation quality on ZINC
hydrogens.
Model
Validity
FCD
Uni.
Model Size
Model
Valid. + Uni.
Atom.
Mol. t
EDP-GNN
82.97
16.74
99.79
0.09M
Dataset (optimal)
97.8
100
98.5
87.0
GruphEBM
5.29
35.47
98.79
SPECTRE
90.20
18.44
67.05
ConGress
86.7
98.4
97.2
69.5
GDSS
97.01
14.66
99.64
0.37M
DiGress (uniform)
89.8
97.8
97.3
70.5
GraphArm
88.23
16.26
99.46
DiGress (marginal)
92.3
97.9
97.3
66.8
DiGress
91.02
23.06
81.23
18.43M
DiGress (marg. + feat.)
95.4
97.6
98.1
79.8
SwinGNN-L
90.68
1.99
99.73
35.91M
PARD (no feat.)
97.5
95.8
98.4
86.1
PARD
95.23
1.98
99.99
4.1M
Results. Table shows generation evaluation results on QM9, where the baseline results are sourced from [44]. PARD outperforms DiGress and variants that do nol use any auxiliary features, with slightly lower Uniqueness. What is notable is that PARD, without using any extra features, achieves a similar performance gap against DiGress that uses specialized extra features. Table 2 shows PARD'S performance on ZINC250K, with baseline results carried over from [25] and [46]. PARD achieves the best Uniqueness, stands out in FCD alongside SwinGNN [46], and is the runner-up w.r.t. Validity.
Table 3: Generation quality on MOSES. The top three methods use hard-coded rules (not highlight).
Model
Val. 1
Uni.
Novel. f Filters
FCD | SNN t Seaf.
VAE
97.7
99.8
69.5
99.7
0.57
0.58
5.9
JT-VAE
100
100
99.9
97.8
1.00
0.53
10.0
GophINVENT
96.4
99.8
95.0
1.22
0.54
12.7
ConGress
83.4
99.9
96.4
94.8
1.48
0.50
16.4
DiGress
85.7
100
95.0
97.1
1.19
0.52
14.8
PARD
86.8
100
78.2
99.0
1.00
0.56
2.2
Finally, Table 3 shows generation quality on the largest dataset MOSES. We mainly compare with DiGress and its variants, which has been the only general-purpose generative model in the literature that is not based on molecular fragments or SMILES strings. Baselines are sourced from [44]. While other specialized models, excluding PARD and DiGress, have hard-coded rules to ensure high Validity, PARD outperforms those several other metries including FCD and SNN, and achives competitive performance on others. Again, it is notable here that PARD, without relying on any auxiliary features, achieves similarly competitive results as with DiGress which utilizes extra features.
5.2
Generic Graph Generation
Table 4: Generation quality on generic graphs. All metrics based on generated-to- to-tes set MMD distances, the lower the better. Top performance is in bold, and Runner-up is underlined.
[OMMUNITY-SMALL
CAVEMAN
CORA
BREAST
GRID
Model
Deg. Clus.
Orbit
Deg.
Clus.
Orbit
Deg.
Clus,
Orbit
Deg.
Clus. Orbit
Deg.
Clus. Orbit
GraphRNN
0.080
0.120
0.040
10.371 1.035
0.033
1.689
0.608 0.308
10.103 0.138 0.005 0.064 0.043 0.021
GRAN
0.060 0.110
0.050
0.043 0.130
0.018
0.125
0.272
0.127
0.073 0.413 0.010
EDP-GNN
0.053 0.144
0.026
0.032
0.168
0.030
0.093
0.269
0.062
0.131 0.038
0.019
0.455
0.238
0,328 0.005
GDSS
0.045 0.086
0.007
0.019
0.048
0.006
0,160
0.376
0.187
0.113 0.020 0.003
0.111
0.070
GraphArm
0.034 0.082
0.004
0.039
0.028
0.018
0.273
0.138
0.105
0.036
0.041
0.002
DiGress
0.047 0.041
0.026
0.0019
0.040
0.003
0.044
0.042
0.223
0.152
0.024
0.008
PARD
0.003 0.071
0.012
|0.002 0.047 0.00003
0.0003
0.003 0.0097 0.044 0.024
0.0003 0.028 0.002 0.029
Datasets. We use five generic graph datasets with various structure and semantie: (1) COMMUNITY-
SMALL [48], (2) CAVEMAN [47], (3) CORA [35], (4) BREAST [15], and (5) GRID [48]. We split each dataset into 80%-20% train-test, and randomly sample 20% of training graphs for validation. We generate the same number of samples as the test set. Notice that GRID contains graphs with 100~~400 nodes, which is relatively large for diffusion models. There are lots of symmetries inside, hence is difficult to capture all dependencies with crmmutation-equivartin
models.
Baselines. We mainly compare against the latest reneral-purpont GraphArm [25], which reported DiGress [44] and GDSS [24] as top two most competitive, along with several other baselines.
Metrics. We follow [48] to measure generation quality using the maximum mean discrepancy (MMD) as distribution distance between the generated graphs and the test graphs (L), as pertain to distributions of (i) Degree, (ii) Clustering coefficient, and (tiz) occurrence count of all Orbits.

---

Results. Table 4 provides the generation results of PARD against the baselines as sourced from [25]. PARD shows outstanding performance achieving SOTA or close runner-up results, while none the baselines shows as consistent performance across datasets and metrics.
5.3 Ablation Study
Q1: do we really need AR in diffusion, given diffluson is already permutation-invariiatt
In DiGress [44], we observed that pure diffusion, while being permutation-invariian. requires (I) many sampling/denoising steps to break symmetries and (2) additional features like eigenvectors to further break symmetry. This shows that directly capturing the FULL joint distribution and solving the transformation difficulty (in Sec. 3.3) via diffusion is challenging. Additionally, AR methods still dominate LLMss, indicating their potential to benefit diffusion models. To quantitatively verify our analysis, we perform an ablation study on the maximum number of hops, Kn, which controls the extent of autoregression (AR). When KA O, all nodes have fixed degree of 1, resulting in single block per graph, equivalent to full diffusion without AR. As K₁, increases, more blocks are generated with smaller average block sizes, indicating a greater number of AR steps.
Table 5: Ablation study on QM9 with varying maximum hops while keeping the total diffusion steps fixed (first two parts). The last part examines the effect of increasing steps for the AR case.
Setting
No AR
With AR
No AR, 1 steps
Total diffusion steps
140
140
280
490
Maximum hops
1
3
0
0
Average number of blocks
1
4.3
5.6
7.75
1
1
Diffusion steps per block
140
32
25
20
280
490
Validity
93.8
97.1
96.7
97.0
94.3
95.2
Uniqueness
96.9
96.5
96.2
96.1
96.5
96.9
Mol stability
76.4
86.1
85.4
86.3
79.3
79.2
Atom Stability
97.7
98.3
98.3
98.4
97.9
98.0
Table 5 shows the result of the controlled experiment with 140 total diffusion steps across all trials, using the same model architecture, diffusion algorithm, and training settings. The significant improvement from K₁ = 0 to K₁ confirms that our enhancement stems from breaking the full joint distribution into several conditional distributions. Furthermore, adding more diffusion steps to full diffusion approach does not close the gap to AR enhanced diffusion, indicates the necessary of combining AR and diffusion.
Q2: how does model architecture affect performance?
Table Results for QM9 dataset with different model architectures with K₁, and 140 total steps.
Backbone
Transformer
PPGN PPGNTransformer
Validity
26.3
96.6
97.1
Uniqueness
94.5
96.3
96.0
Mol Stability
17.6
84.67
86.2
Atom Stability
81.4
98.2
98.4
Table 6 this indicates that PPGN component is essential for diffusion with autoregression. The design of combining PPGN and transformer in Sec. 4 further addresses the efficiency of PPGN.
Other ablations: other ablations and runtime measures are in Appx. $A.12
6 Conclusion
We presented PARD, the first permutation invariant autoregressive diffusion model for graph genera- tion. PARD decomposes the joint probability of a graph autoregressively into the product of several block conditional probabilities. by relying on unique and permutation equivariant structural partial order. All conditional probabilities are then modeled with shared discrete diffusion. PARD can be trained in parallel on all blocks, and efficiently scales to millions of graphs. PARD achieves SOTA performance on molecular and non-molecular datasets without using any extra features. Notably, we expect PARD to serve as cornerstone toward generative foundation modeling for graphs.
10

---

References
[1] Namrata Anand and Possu Huang. Generative modeling for protein structures. Advances in neural information processing systems, 31, 2018.
[2] Vikraman Arvind, Bireswar Das, and Johannes Köbler. The space complexity of k-tree isomor- phism. In Algorithms and Computation: 18th International Symposium, ISAAC 2007, Sendai, Japan, December 17-19, 2007. Proceedings 18, pages 822- Springer, 2007.
[3] Jacob Austin, Daniel D Johnson, Jonathan Ho, Daniel Tarlow, and Rianne van den Berg. Structured denoising diffusion models in discrete state-spaces. Advances in Neural Information Processing Systems, 14:17981-17993 2021.
[4] R Balakrishnan. The energy of graph. Linear Algebra and its Applications, 387:287-295.
2004.
[5] Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M. Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks. In International Conference on Learning Representations, 2022.
[6] Rishi Bommasani, Drew A Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, Michael Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, et al. On the opportunities and risks of foundation models. arXiv preprint arXiv:2108.072555 2021.
[7] Angela Bonifati, Irena Holubová, Arnau Prat-Pérez, and Sherif Sakr. Graph generators: State of the art and open challenges. ACM computing surveys (CSUR), 53(2):1-30, 2020.
[8] Chen Cai, Truong Son Hy, Rose Yu, and Yusu Wang. On the connection between mpnn and graph transformer. International Conference on Machine Learning, 2023.
(9] Xiaohui Chen, Xu Han, Jiajing Hu, Francisco Ruiz, and Liping Liu. Order matters: Probabilistic modeling of node sequence for graph generation. In International Conference Machine Learning, pages 1630-1639. PMLR, 2021.
[10] Suparna De, Maria Bermudez-Edo, Honghui Xu, and Zhipeng Cai. Deep generative models in the industrial internet of things: a survey, IEEE Transactions on Industrial Informatics, 18(9): 5728-5737, 2022.
[11] Nicola De Cao and Thomas Kipf. Molgan: An implicit generative model for small molecular graphs. arXiv preprint 11X1v:1805.11973, 2018.
[12] William A Falcon. Pytorch lightning. GitHub, 3, 2019.
[13] Wenqi Fan, Chengyi Liu, Yunqing Liu, Jiatong Li, Hang Li, Hui Liu, Jiliang Tang, and Qing Li. Generative diffusion models on graphs: Methods and applications. arXiv preprint 2rXiv:2302.02591, 2023.
[14] Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv: 094402222,, 2019.
[15] Laura Gonzalez-Malerva, Jaehong Park, Lihua Zou, Yanhui Hu, Zahra Moradpour, Joseph Pearlberg, Jacqueline Sawyer, Hallam Stevens, Ed Harlow, and Joshua LaBaer. High-throughput ectopic expression screen for tamoxifen resistance identifies an atypical kinase that blocks autophagy. Proceedings of the National Academy of Sciences, 108(5):2058-200 2011.
[16] Nikhil Goyal, Harsh Vardhan Jain, and Sayan Ranu. Graphgen: scalable approach to domain-agnostic labeled graph generation. In Proceedings of The Web Conference 2020, pages 1253-1263, 2020.
[17] Nikhil Goyal, Harsh Vardhan Jain, and Sayan Ranu. Graphgen: scalable approach to domain-agnostic labeled graph generation. In Proceedings of The Web Conference 2020, pages 1253-1263, 2020.
[18] Ivan Gutman, Xueliang Li, and Jianbin Zhang. Graph energy. Analysis of Complex Networks: From Biology to Linguistics, pages 145-174, 2009.
2009.

---

[19] Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems, 33:6840 13:6840-6851, 2020.
[20] Emiel Hoogeboom, Didrik Nielsen, Priyank Jaini, Patrick Forré, and Max Welling, Argmax flows and multinomial diffusion: Learning categorical distributions. Advances in Neural Information Processing Systems, 34:12454-12465 2021.
[21] Emiel Hoogeboom, Alexey A. Gritsenko, Jasmijn Bastings, Ben Poole, Rianne van den Berg, and Tim Salimans. Autoregressive diffusion models. In International Conference on Learning Representations, 2022.
[22] Emiel Hoogeboom, Víctor Garcia Satorras, Clément Vignac, and Max Welling. Equivariant diffusion for molecule generation in 3D. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 8867-8887. PMLR, 17-23 Jul 2022.
[23] John Irwin, Teague Sterling, Michael M Mysinger, Erin Bolstad, and Ryan G Coleman. Zinc: a free tool to discover chemistry for biology. Journal of chemical information and modeling, 52 (7):1757-1768, 2012.
[24] Jachyeong Jo, Seul Lee, and Sung Ju Hwang. Score-based generative modeling of graphs via the system of stochastic differential equations. In International Conference Machine Learning, pages 10362-10383. PMLR, 2022.
[25] Lingkai Kong, Jiaming Cui, Haotian Sun, Yuchen Zhuang, B Aditya Prakash, and Chao Zhang Autoregressive diffusion model for graph generation. In International Conference on Machine Learning, pages 17391-17408. PMLR, 2023.
[26] Yibo Li, Liangren Zhang, and Zhenming Liu. Multi-objective de novo drug design with conditional graph generative model. Journal of Cheminformaties, 10:1-24, 2018.
[27] Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter Battaglia. Learning deep generative models of graphs. arXiv preprint arXiv: 2018.
[28] Renjie Liao, Yujia Li, Yang Song, Shenlong Wang, Will Hamilton, David K Duvenaud, Raquel Urtasun, and Richard Zemel. Efficient graph generation with graph recurrent attention networks. Advances in neural information processing systems, 32, 2019.
[29] Liheng Ma, Chen Lin, Derek Lim, Adriana Romero-Soriin K. Dokania, Mark Coates, Philip H.S. Torr, and Ser-Nam Lim. Graph Inductive Biases in Transformers without Message Passing. In Proc. Int. Conf. Mach. Learn., 2023.
[30] Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances in neural information processing systems, 2019.
[31] Christopher Morris, Gaurav Rattan, Sandra Kiefer, and Siamak Ravanbakhsh. Speqnets: Sparsity-aware permutation-cquivariaai graph networks. In International Conference on Ma- chine Learning, pages 16017-16042. PMLR, 2022.
[32] Chenhao Niu, Yang Song, Jiaming Song. Shengjia Zhao, Aditya Grover, and Stefano Ermon. Permutation invariant graph generation via score-based generative modeling. In International Conference on Artificial Intelligence and Statisticy, pages 4484 PMIR, 2020.
[33] Daniil Polykovskiy, Alexander Zhebrak, Benjamin Sanchez-Lengelingg Sergey Golovanov, Oktai Tatanov, Stanislay Belyaev, Rauf Kurbanov, Aleksey Artamonov, Vladimir Aladinskiy, Mark Veselov, Artur Kadurin, Simon Johansson, Hongming Chen, Sergey Nikolenko, Alan Aspuru-Guzik, and Alex Zhavoronkov. Molecular Sets (MOSES): A Benchmarking Platform for Molecular Generation Models. Frontiers in Pharmacology. 2020.
[34] Raghunathan Ramakrishnan, Pavlo O Dral, Matthias Rupp, and O Anatole Von Lilienfeld. Quantum chemistry structures and properties of 134 kilo molecules. Scientific data, 1(1):177, 2014.
12

---

[35]
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al magazine, 29(3):93 93, 2008.
[36] Chence Shi*, Minkai Xu*, Zhaocheng Zhu, Weinan Zhang, Ming Zhang, and Jian Tang. Graphaf: flow-based autoregressive model for molecular graph generation. In International Conference on Learning Representations, 2020.
[37] Martin Simonovsky and Nikos Komodakis. Graphvae: Towards generation of small graphs using variational autoencoders. In International conference on artificial neural networks, pages 412-422 Springer, 2018.
[38] Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and sunrya Ganguli. Deep unsunper- vised learning using nonequilibrium thermodynamics. International Conference on Machine Learning, pages 2256-2265. PMLR, 2015.
[39] Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. Advances in neural information processing systems, 32, 2019.
[40] Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. In International Conference on Learning Representations, 2021.
[41] Balasubramaniam Srinivasan and Bruno Ribeiro. On the equivalence between positional node embeddings and structural graph representations. In International Conference on Learning Representations, 2020.
[42] Xiaochu Tong. Xiaohong Liu, Xiaoqin Tan, Xutong Li, Jiaxin Jiang, Zhaoping Xiong, Tingyang Xu, Hualiang Jiang. Nan Qiao, and Mingyue Zheng. Generative models for de novo drug design. Journal of Medicinal Chemistry,
1011):14011140000 2021.
[43] Jeanne Trinquier, Guido Uguzzoni, Andrea Pagnani, Francesco Zamponi, and Martin Weigt. Efficient generative modeling of protein sequences using simple autoregressive models. Nature communications, 12(1):5800, 2021.
[44] Clement Vignac, Igor Krawczuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pas- cal Frossard. Digress: Discrete denoising diffusion for graph generation. In The Eleventh International Conference on Learning Representations, 2023.
[45] 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 Representations, 2022.
[46] Qi Yan, Zhengyang Liang, Yang Song, Renjie Liao, and Lele Wang. Swingnn: Rethinking per- mutation invariance in diffusion models for graph generation, arXiv preprint wxX1v23307.01646 2023.
[47] Jiaxuan You. Caveman Dataset, https: //g thub. com/JJiaxaanoougrraaaa wwwprr//oo/grpppggggeeertiiol/oa blob/master/ cweateee py, 2018. [Online; accessed 2024).
[48] Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. Graphrun: Generat- ing realistic graphs with deep auto-regressive models. In International conference on machine learning, pages 1708-57177 PMLR, 2018
[49] Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: A theory of using graph neural networks for modti-node representation learning. Advances Neural Information Processing Systems, 14:9061-9077 2021.
[50] Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any GNN with local structure awareness. In International Conference on Learning Representations, 2022.
[51] Lingxiao Zhao, Neil Shah, and Leman Akoglu. A practical, progressively-expressi gnn. Advances in Neural Information Processing Systems, 35:34106-34120, 2022.
[52] Lingxiao Zhao, Xueying Ding, Lijun Yu, and Leman Akoglu. Improving and unifying discreteeconninuuus-ttine discrete denoising diffusion. arXiv preprint arX1v:2402.03701, 2024.
13

---

A Appendix
A.1 Variational Lower Bound Derivation
log f ((Gir) Go) pe(Go.T) g(Gr.r Go) dG1. 2 Be(cnr)lb)) log (oppooooT) log ((G))))
T
Pa
= (G) (og (Go.T) +
log
G,,
pe (G G1)
Pe Go
= - log + log (G]
log
[ Go)
po (G)
Po G+)
g(G
(GG (oggo((T)) log
log
(G,
G(G Go)
( Go)
po G
log (G) Go)
T
pa Po G.)
- [logpo(Gr) log
+ Σ
log
gGn
(Gr/Go)
(GG Gr, Go)
= (Go [oggo + log (G
(GT Go) Σ log (G,-1 Gr, Go)
T
Po Po(G,-I
T
= Go) lo (Gol (Go
B. Go) DRI((((G GGolooGGGGG const.
(o)
(,
(11)
Using Eq. (1), the first term can simplified as
Bg (Ga)
log (v) G1) +
Σ
log po (1))
(12)
iJ
and similarly, the t-th step loss C,( is
E Eg(c.,bo)
Σ KL KL l po
Σ KL pl i
(13)
A.2 Details of Discrete Diffusion Used in Paper
We closely follow the approach in Zhao et al. [52] to define forward and backward process discrete diffusion, and get the formulation of three important distributions, (i) (G, Go) (ti) gG Go), and (Mil po (G.- detailed constructions. Notice that only use the most basic discrete-time discrete diffusion formulation in Zhao et al. [52], mainly for improved memory efficiency over other old approaches like D3PM [3]. Other enhanced techniques in [52] like approximated loss and continuous-time formulation are not used, to keep the discrete diffusion part simple.
needed for computing negative VL.B based loss. In here, we explain the
DiGress [44] applies D3PM [3] to define these three terms, our approach is similar. Since all elements in the forward process are independent as shown in Eq. (1), one can verify that the two terms (G, G.) and g Gr, Gu) are in the form of product of independent distributions simplicity, we introduce the formulation for a single element x, with x being v or e We assume each discrete random variable x, has categorical distribution, i.e. X₁ Cat(x;; p) with p [0, 1]K and 1 p 1 One can verify that p(x; xt;) x, p. simply p(xx) x; p. As shown in Hoogeboom et al. [20], Austin et al. [3], the forward process with discrete variables ((x: [x:-) can be represented as transition matrix Qi E [0, 1] K x such that [Qelaj g(x, e,(x;-1 e,). Then,
each element. For
x(xx(xx1) Cat(x;; Q7 xT-1))
(14)
14

---

Given transition matrices Q1. Qr, the forward conditional marginal distribution is
()) g [xx]] xx)) Cat(x;; Q2 mo), with Q. = QI...Qr,
(15)
and the (t-1) posterior distribution can be written as
(ii) (xx,1 = Cat(xx-1; Qix @ Q2-100
(16)
x. Q2 Zg
See Apdx. $A.3 for the derivation. We have the option to specify node- or edge-specine quantities, Qtd and Q respectively, or allow all nodes and edges to share common QU and Qi- Leveraging Eq. (15) and Eq. (16), we can precisely determine q(v:lv) and (iv;-llv', vo) for every node, and similar approach can be applied for the edges. To ensure simplicity and a non-informative q(G (o)) (see Apdx $A.4), we choose
(17) for all nodes and edges, where a E [0. 1]. and m uniform distribution (1/K, for nodes and 1/K, for edges). Note that DiGress [44] chooses the marginal distribution of nodes and edges. As p(x{-1(x;) = Exo ((x,-1/x,, Xo xx)p((x)xx)) the parametcrization of po p GG) can use the relationship, with
= (1 am
(88) po (x = Σ (xxx-ilxx (x) Gt)
(18)
where x can be any v or ehd With Eq. (18), we can parameterize po (xo G) directly with a neural network, and compute the negative VLB loss in Eq. (2) exactly, using Eq.s (15), (16) and (18).
A.3 Derivation of (12,
First, define Q1 Q++1--Qu- Note that Q110 Q, and Q:j=-1 Qt- Accordingly, derive the following two equalities.
( Qi x.-1)
(19)
q(x-- = g(xx1 xx- (xx-1)((xx11/x)
Cat(x; QJ xi- (xtx-- 1: Ri-1
q(111 (1x)
Cat(x;; 0, xo)
5T11Qx0 xT xT100-180 X,-1
Qix 3 Q1-1x0 CCa((x--1;
T Qixi @ Q1-1x0, x, Q, Xo
xx Qe Xo
x, Q2 Xo
(20)
A.4 Simplification of Transition Matrix
For any transition matrices QI,... Qr, which however should be chosen such that every row of Q. Qrjo converge the same known stationary distribution when becomes large (i.e. at T), let the known stationary distribution be mg ~ Cat m.). Then, the constraint can be stated as lim Q2 1m.
(21)
t-T
To achieve the desired convergence on nominal data (which is typical data type in edges and nodes of graphs), while keeping the flexibility of choosing any categorical stationary distribution my Cat m), we define Q₁ as
Q: = a + (1 1m
(22)
where a; E [0, 1). This results in the accumulated transition matrix Qzjs being equal to
Q = e / + (1 TT 1m 14
(23)
where Tt/s = I[ - 0g. Note that ã. Tejo a...c We achieve Eq. (21) by picking a such that lim4-47 04 = 0.
15

---

A.5 Proof of Theorem 3.2
We prove this for node case. For structurally equivalent edges, the analysis is the same. Assume node i and node j are structually equivalent, then we can find an automorphism a E Aut(G) such that j. For any permutation P PiG and equivariant network f, we have
f(P + P f(G)
(24)
Replace P with o, and using the fact that G = G. We can get
f(G) = f(o * G) = o f(G)
(25)
Hence, we get S(G); = [(G),. that is two nodes and j have the same representation.
A.6 Proof of Exchangeable Probability
To prove that (G) is exchangeable probability, need to show that for any permutation operator P with P * G = (PV, PEPT), the probability satisfies Pa [ * G) (G)).. While P is defined as a group acting on all nodes ([VI) in the graph G, this operator can also applied directly to sub-components of G, in such manner that it permutes only the elements within these components. use P to these sub-components directly the following proof.
Recall that PARD define (G) as
KB (G) = II po (GIBial G[B (aaii1)GBBBB-11 G(Bra-1)). 1=1
(26)
Observe that for graph G, B; represents a subset containing certain nodes from G. When G represented in its default order G, the subset B, can be represented as a binary vector mask {0, 1)1l, where value of 1 at the j-th position indicates that the j-th node in is included in the subset. Then G[B;] can be view as indexing nodes and edges from G using mask B, As indexing operation is permutation equivariant, we have P [G] is actually a function of G and can be represented as (G). This function is actually permutation equivariant, such that (P G) PB (G), (G) is determined by algorithm solely based on structural degree information (up to K hops) of each node, where the structural feature is permutation equivariant.
(P x G)
Br.l What is more, B;
Then we have Po [P * G)
Kn
Po ((P*))BI.(PP*)))) (PP P| (/c)://(__(PP00]|P//////BB/L..
(P (P*))\BI--PPxGG))
K
(P+ (P+
(P*
(P+ P (P+G)P*BB..II) (Prop. 3.1)
(=1
III pe (G(Bi.)))) p G
P PG
(Indexing's equivariance)
Kn
(P* (G(B,u) G(B
P* (G(B
Pe
Kg
[Bil
P P G pa
(P (G
G.B P* (B(B:n)))U0(1..)))
(27)
Notice that we are using permutation invariant function to approximate po [B&]]
P G(B
hence we have
Po (1B.)
P G[B po (15a) G[B 1l).
(28)
16

---

For the second part, notice that
Ps G[B \ G[BLn-I]
[[B:=-1]U0[Bi. =
f po [[[B:=-i] (G/B G[Bra-1]) G[B u ([Br..) d
(29)
Then we have
Pe P (G[B G[B P* (G
/ [H[B U P (G|B |Bt.all\GGBBB....
G[ P (G dH[B
/ po
P* x
P
P (G[Baa) G[BI P P (G dP ((
/ po P (H(B)=-11) (G(B).] \ G(B
P (G u dH(Bi:111 (30)
Now notice that the probability pe P* (H ( P p
actually a conditional distribution from one graph to another graph (with same size), and we can simplify it pe (H(G). As this part is modeled by diffusion model, we prove that this function is permutation equivariant. That is, for any permutation P.
pe (H[G) pe ( G
(31)
Proof. Our diffusion process is using an equivariant model through a markov chain that from Hy, and then from H7 to Hr-1, 1, .... H, H until H₃ Ho H. Then we have
pa GH (H G)
po (o (Hr G)
po (H, H4-1)dH11r (=1
II
(32)
Because we are using an shared permutation equivariant model model all po(H:|H,,1), have po (H, H,-1) Po(P (P+ H, P Hę-1) Jtt P. Also, because we have chosen the distribution (Hr G), such that all conditioned part from B1s are the same with input G, and all other left elements are sampled from isotrophic noise, the distribution Po(Hz/G) (G) is also equivariant with Po(H7 PP Hr| G). Take these properties back we have
/ (Hr P G)p P Ho) II po HHH
po * H
T
= f po Hy P G P Ho)
II
Po * H. P H4-1)dHH:r
= =fmott poo(Hr] (G)
II
HH
1=1
GH]
(33)
With the conclusion from Eq. (31), we can apply it to Eq. (30)
Pa P (G[B IlB P (
= f po P PP(H(BB,-1)) (G(B.a) G(BB+-))) P (G[B u ((Bı=)) dH(Bia-1]
f po [H[BI=-1] (G G(B
G[Bra-1] u 0[B1a]) dH (H
(G(BIa) \ G[B G ((
(34)
17

---

Apply Eq. (28) and Eq. (34) to Eq. (27), we can finalize our proof that
Kg
Pa Pa G)
[B:
P* P P
P (G[Bra] G(B
P* [
2=1
II Po i=1
[Ba
G(BIa-1l) (((B:)) \ G[BLa-1] G[B]][(BB.. G(B ((
K
II po [[B]a] G[Bra-1] G[BLa-1) po(G)
Hence, our method PARD a permutation-invarian probability model.
A.7 Definition of Graph Transformation
Definition A.1 (Graph Transformation). Given labeled graph G (Vg, Eg) and labeled target graph H (VH,Ex) that have the same number of nodes, the graph transformation function G:G + H is defined such that f(G) H.
Notice that while the graph transformation function requires input and output graph have the same graph size, this function is general enough to accommodate any changing of size operation. Specif- ically, if G has more nodes than H, the function must assign 'empty' token nodes and edges within G that do not correspond to those in H. Conversely, if G has fewer nodes than H, the function will augment G with 'empty' nodes and edges until matches the size of H. Subsequently, transforms this augmented version of G to match H.
Definition A.2 (Equivariant Graph Transformation), An equivariant graph transformation f is graph transformation that satisfies f(Px G) = s(P x H) for any permutation operation P.
A.8 Algorithms of Training and Generation
We present blocksize prediction algorithm in Algo. and denoising diffusion algorithm in Algo. 3. Notice while the blocksize network ge Algo. and denoising diffusion network fe Algo. use the same subscript parameter 0, the essentially represents concatenation of and f's parameters.
Algorithm 2 Train blocksize distribution po (IB,) G[B1-11])
1: Input: G, maximum hop Kn, a network ge that takes a graph as input and output graph wise prediction.
2: Get structural partial order function G from Algo.
3: Using to get the sequence of node blocks [B,.... BKB] for G.
4: Minimize Σ KB
Σ CrossEntropy (ge (G(,,)), [B+1l), with [Ba++1|
Algorithm 3 Train denoising diffusion for distribution po (G(BLa) G[B1s-1] G[B ((((.
1: Input: G, max time T, maximum hop Kg. network fo that inputs a graph and outputs nodes and edges predictions.
2: Get structural partial order function ø of G from Algo.
3: Using é to get the sequence of node blocks [Bi,... 3x,l n for G.
4: Sample t ~ (1,...,
5: for 1,... Kn do
6: M + indice mask of G[B \ G[B
7: Sample noise graph [ from 4: (G[Baa)) according to Eq. (15)
8:
G[Bi.]] < M @ G[B + (1 - M) @ G[B
9:
+ fo(G[B M
10:
Y + G C M
11: 4 + -,(,X,)) 0.1 CCE(X,Y)) using C, in Eq. (2) and LCE in Eq. (3).
12: end for
13: Minimize Kg 4.
(The for loop can parallelized.)
18

---

Algorithm 4 Generation
1: Input: blocksize model go. diffusion model fa; first blocksize distribution from TrainSet.
2: G G 0; i
3: Sample n from the first block's size distribution.
4: while n > 0 do
5: Add a new block B, with n nodes into G
6: .M <- indice mask of G[Bis] \ G[B
7:
G G For nodes and edges within M, sample from noise m, and ma
8:
for : do
9:
- fo(G)
< Sample according
M @ S (1 M)
12:
end for
G G
14:
n + Sample from gG)
i- i
16:
end while
Return: G
A.9 Visualization of the PPGN-Transfonne Block
BN
DN
DN
MSA
FRN
PPGN Black
out
Transformer Block
FFN
PFN
X,
BN
FFN
(a) The Overall Architecture of PPGN Transformer Block
(b) Transformer
[c) PPGN Block
Figure 3: The Architecture the TPGN-Tranfformer Block. In (b) and (c) we provide illustrations of how edge and node features are processed through Transformer and PPGN blocks.
A.10
Details and Derivations of Causal Matrix-Matrix Product
A.10.1
Derivation of causal version matrix product
For any matrix X, let X, denotes the i-th row of X, and X.,, denotes i-th column of X, Let (:, denotes vector inner product. For normal matrix product AB, we know that
(AB);, (A,, B.,)
(35)
In our causal setting with block ID introduced main context, the (i. position will have its block ID being max(block ID(i), block ID(j)). Hence, the product in Eq. (35) should not use any information outside block whose ID larger than max(block (bxlock_II(()) block (acc__I(()). Let O, be the needed safe output position (i,5) of the matrix-matie product, can verify that the following uses all information within useable blocks without any information leakage.
O (A @ (M, M2), B..)) (where or denotes elementwise or operation)
(A O (M, + M, - M, @ M,), B.J)
(A; O M, B2) (A,, B.j M,) (A, A,, B M,)
(A, O M. Bj) (A,, B. M. (A, O A, B O M..)
(36)
Where mask matrix M satisfies M.,; = 1 if Boock_D(nnode i) 2 block Mrrk_DDnnook DD(nod j) else 0.
Based on Eq. (36), we can rewrite it to matrix operation such that
0 = (A O M) A(B O M (A O M) M
(37)
19

---

Where the matrix O's (1 position value is just Oij in Eq. (36). Hence we have derived the equation in Eq. (10).
A.10.2 Discussion of expressivity
While the causal maarix-mmtrri product makes the training more efficient with parallel support, have to acknowledge that it is highly possible that its expressiveness in graph distinguishing ability is reduced. Hence the causal PPGN should have less expressiveness than the normal PPGN. In fact, we have found that for symmetry-rich datasets like GRID, sequential training of PARD'S loss is easier to minimize than parallel training of PARD.
A.10.3 Additional details of parallel training
The previous discussion mainly focuses on preventing information leakage, which is the most critical aspect of causal parallel training. Another essential component of parallel training is the ability to output all predictions for subsequent blocks simultaneously. For GPT, no modifications are necessary for predicting all next tokens, the next token can simply use the position from the previous token. However, when predicting the next block given all previous blocks, it's not feasible to use any positions within previous blocks hold the prediction for the next block due differences in size and lack of alignment. Therefore, as shown in Eq. (6), a virtual block needs to be augmented to serve as prediction placeholder for the next block. For parallel prediction, virtual block will be augmented for each block in the graph, with each virtual block having the same block ID as the corresponding original block. To summarize, for a graph with N nodes, needs to be expanded to 2N nodes by adding N virtual nodes for parallel training.
A.11 Experiment Details
Table 7: Dataset summary
Name
#Graphs
IVlnvg
E avg
QM9
133,885
19
ZINC250K
249,455
23
50
MOSES
1,936,963
22
47
COMMUNITY-S
200
15.8
75.5
CAVEMAN
200
13.9
68.8
CORA
18,850
51.9
121.2
BREAST
100
55.7
117.0
GRID
100
210
783.0
We use a single RTX-A6000 GPU for all experiments. For discrete diffusion, we follow [52]'s basic discrete diffusion implementation, where exponential moving average is not enabled. For model implementation, we use Pytorch Geometric [14], and we implement our combination of PPGN and Transformer by referencing the code in Maron al. [30] and Ma et al. [29]. Additionally, we use Pytorch Lightning [12] for training and keeping the code clean. We use Adam optimizer with cosine decay learning rate scheduler to train. For diffusion and blocksize prediction, we also input the embedding of block id and node degree as additional feature, as we have block id computed in preprocessing. Additionally, it important to observe that nodes within the same block all have the same degree. At diffusion stage, we conditional on the predicted degree for the next block to train diffusion model, where the degree predicted along with the block size using the same network. We provide source code and all configuration files at https: //github. com coomLingxaae wainggiiaosaaan.... PPard.
A.12 Ablations and Runtime Measure
How does the sampling steps for diffusion models in PARD impact the performance of graph generation? To answer it, we conducted detailed ablation on number of difffusion steps in QM9, with results in Table. 8. To summarize, too small a number of steps hurt the performance, while too large doesn't help improve the performance further. See the table below. Within the table, we have emphasized a configuration that employs just 140 total diffusion steps. This amount is considerably less than the steps used by DiGress, yet it dramatically outperforms DiGress.
While graphs are trained with single, fixed generation path based on Φ; is the same path being used in generation? We acknowledge that although each graph undergoes single decomposition
20

---

Table Comparison of different models on QM9 dataset
Ablation on QM9
PARD
DiGress
Average number of blocks
7
7
7
7
Number of Diffusion Steps Per Block
10
20
40
70
100
500
Total Number of Diffusion Steps
70
140
280
490
700
500
Validity
0.9419
0.9708
0.971
0.973
0.9755
95.4
Uniqueness
0.9676
0.9605
0,9579
0.9544
0.9609
97.6
Mol stability
0.8094
0.8627
0.8625
0.8589
0.8561
79.8
Atom Stability
0.9767
0.9847
0.9844
0.9839
0.9837
98.1
block sequence during training. it is possible for the generation path to differ from the training path. This discrepancy attributed a phenomenon known exposure bias, challenge encountered in autoregressive methods and imitation learning alike. Despite this, we have conducted empirical analysis to estimate the likelihood of divergence between the generation and training paths. By sampling 2,000 graphs generated by the model trained on the QM9 dataset, we tracked the generation path for each graph and compared it to the training path defined by the decomposition block sequence algorithm. Our findings indicate that 94.7% of the generated samples followed the exact same path as their corresponding training path.
Runtime comparison. To show that our method doesn't 't introduce much runtime overhead, we report the training time in Table used achieve the number reported on two datasets: QW9 and Moses. The training time for DiGress is mentioned in their github. Notice that the training time is also affected by the machine, we use GPU A6000 all experiments.
Table Training time comparison on QM9 and Moses datasets
Training Time
QM9
Moses
DiGress
~6
~7 days
PARD
~12h
~4 days
A.13
Visualization of Generation
A.13.1
QM9
Figure 4: Non curated QM9 (with explicit hydrogens) graphs generated from the PARD trained with 20 steps per block.
21

---

GRID
Deg.
Clus.
Orbit
EDP-GNN
0.455
0.238
0.328
GDSS
0.111
0.005
0.070
PARD
0.028
0.002
0.029
PARD with Eigen Vec.
0.053
0
0.008
Table 10: Performance comparison of diffusion methods GRID.
A.13.2 Grid
Figure Non curated grid graphs generated from the PARD trained with 50 steps per block.
Figure 6: Non curated grid graphs generated from the PARD (with eigenvector) trained with 50 steps per block.
22

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We propose new graph diffusion method that integrates autoregressive graph
generation with diffusion. We showcase our method in the main paper with thorough experiments.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should elearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We briefly discuss the limitations of PARD with respect to long training and sampling times, but we have pointed out potential improvements with for parallel training in causal transformers.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-texx system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
23

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
All our theorems, formulas and proof' in the paper are numbered and ref- erenced. The assumptions are clearly stated. The proofs are shown in main paper and appendix.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We introduce new algorithm and architecture for graph generation tasks, The detailed explanations on the algorithm, and the experiment details are clearly shown in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
24

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We have publicized our training repository with anonymous link referenced in the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/ //nips.cc/pullll wttpcccppppccccceeccc..cc..c.ttt welicc/guiieeee des/ CodeSubmi sssssssio ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We use the same test bed as our benchmarking methods, so the dataset split and evaluation codes are publicly available. The hyperparameter configurations discussed in the appendix as well as in our code library.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We provide experiment results and evaluations over 10,000-25,000 sampled graphs, the numbers of high confidence.
25

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provide the memory, running time, sampling time discussions in the main paper and in appendix. All experiments running on A6000 GPUs.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported didn't 'tttt make it into the paper).
paper (e.g., preliminary or failed experiments that
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics stttps://neurppes cc cc/public/ happullc//Etitt hetlicc///hiiitiieee delunddliinsse
Answer: [Yes]
Justification: The authors have reviewed the code of ethics. paper and the code base preserve anonymity.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
26

---

Answer:
[NA]
Justification:
There is no societal impact of the work performed.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymentt of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning conrectly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer:[NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All our datasets and benchmarking methods are from publicly available libraries under proper licenses.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
27

---

The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's ' creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We provide anonymous code base.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the datasct/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing research with human subjects.
Guidelines:
28

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
29


Reviews:
[{"review_id": "qX9D32cSku", "reviewer": "Reviewer_SjHr", "summary": "This paper proposes to integrate autoregression models with diffusion models seamlessly to harnesses the effectiveness and efficiency of the autoregressive model while maintaining permutation invariance without order sensitivity. It also proposes architectural improvement to make the model and algorithm efficient and scalable. The presentation is smooth and the experimental results on both molecular and general graph generation demonstrate its effectiveness.", "questions": "It would be better if the authors can provide some insights about the hyperparameter the maximum of hops $K_h$.", "limitations": "The authors have adequately mentioned several limitations of their work which sound quite reasonable.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "It proposes a novel graph decomposition method considering not individual node and its degree but subsets of nodes with structual similarity. In this way, it removes node order sensitivity in the graph but only needs to maintain the order of the blocks. Within each block, the diffusion model focuses on a much smaller graph and thus has the efficiency to generate a denoised graph.", "weaknesses": "It would be better if the authors can provide some insights about the hyperparameter the maximum of hops $K_h$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### Thank you for giving positive feedback to our paper, we would like to further answer your question in detail. \n\n>**Provide some insights about the hyperparameter the maximum of hops $K_h$** \n\nLet us first lay out $K_h$'s impact on the model: There is a relation between $K_h$ and block-size (hence the number of autoregression steps). As $K_h$ increases, the \"weighted degree\" of nodes diversify more with fewer equivalences, which induces a partial order with smaller blocks (i.e. fewer number of nodes and edges inside each block). Thus, the larger the hops $K_h$ is, the larger is the number of blocks and hence the number of autoregression steps.\n\nOriginally, we did not do ablation on the maximum hops during our experiments.  We have an intuition that there would be a tradeoff, such that the smaller the block size, the easier it would be to learn within block diffusion, but the harder the autoregressive (AR) generation of the next block would be due to the exposure bias and the consequent error propagation of AR methods (If a block is mistakenly predicted during inference, the error will be propagated and the future blocks conditioned on this one will be impacted---this is true for all AR methods like LLMs). As the maximum hops essentially controls the combination ratios of diffusion model and autoregressive approach, we would like to choose it to make the number blocks to be 3 to 5 times smaller than the total number of nodes (such that each block has 3 to 5 number of nodes on average). Hence, for all molecular graphs, we set $K_h=3$. For all non-molecular graphs, we set $K_h=1$, as this provides a reasonable number of blocks based on our intuition.\n\nNevertheless, we would also like to formally and quantitatively answer the influence of $K_h$. Hence we have conducted an ablation study on the QM9 dataset, changing $K_h$  from 0 to 4. Notice that when $K_h=0$, all nodes have a fixed degree 1, hence it only provides a single block, which is equivalent to full graph diffusion (only) without any autoregressive approach.  As $K_h$, block size (count) tends to decrease (increase) and we have a diffusion-AR hybrid as proposed.\n\n|                               |   Pard    |    Pard     |    Pard     |   Pard      |    Pard   |\n|:--------------------------- | :------- | :------- | :-------- | :------ | :------- |\n| Maximum hops                  | 0      | 1      | 2      | 3      | 4      |\n| Average number of blocks      | **1**      | 4.3    | 5.6    | 7.75   | 7.83  |\n| Diffusion steps per block     | 140    | 32     | 25     | 20     | 18     |\n| Total diffusion steps | 140    | 140    | 140    |140    |140    |\n| Validity                      | 93.8 | 97.1 | 96.7 | 97.0 | 97.1 |\n| Uniqueness                    | 96.9 | 96.5 | 96.2 | 96.1 | 95.9 |\n| Mol stability                 | 76.4 | 86.1 | 85.4 | 86.3 | 85.7 |\n| Atom Stability                | 97.7 | 98.3 | 98.3 | 98.4 | 98.3 |\n\nAs you can see from this ablation on $K_h$, we have found:\n1.  Combining autoregressive and diffusion works significantly better than diffusion-only ($K_h$=0) approach. \n2.  The performance seems to be robust with respect to the maximum hops (at least in range 1-4). \n\n-------------------------------------------------\n### We hope that we have fully addressed your concerns, and we are looking forward to your further input and your support of the paper in score.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "o2kx5C8BuN", "reviewer": "Reviewer_adow", "summary": "The work proposes a new graph generative model based on an autoregressive procedure. It proposes an approach to deciding a partial order of graph nodes according to their degrees in a node-removal procedure. Based on the partial order, the work devises a new graph generative model.", "questions": "How do you justify the advantage of using an autoregressive model with partial order?", "limitations": "The proposed model seems to have a long running time because it needs to run a diffusion model at the generation of each block.", "rating": 3, "confidence": 4, "soundness": 1, "presentation": 3, "contribution": 2, "strengths": "The graph algorithm of deciding a partial order of graph nodes would be interesting if such an algorithm does not exist in the literature of graph theory.", "weaknesses": "The work lacks justification. As the field has moved to generative methods with discrete-diffusion models, which are already permutation-invariant, it is less clear about the advantage of designing a complex autoregressive model to satisfy the permutation-invariant property. \n\nThe advantage of the model is not obvious even considering only autoregressive models. Note that Chen et al. [9] have an approach of \"optimizing\" node orders for the generative model and show that the likelihood calculation is more accurate with their approach than a pre-determined order. How does the work justify its advantage over such an approach?\n\nThe analysis in 3.3 does not seem to be reasonable. The **probability calculations** are indeed the same for nodes in the same orbit, but they may get different connections in the sampling procedure and then break the symmetry. The analysis in 3.3 is well known, and it is not a concern for generative models. In some diffusion-based generative models, the starting graph is a graph with no edges, then all nodes are in the same orbit, but it is not an issue at all because the edge sampling process will break the symmetry. \n\nWithout clear justification, I don't know where performance improvements are from (maybe architecture improvement?). I feel that the work should have a thorough investigation of the model.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### Thank you for your questions. We have conducted extensive new ablation studies. We want to show that our analysis/motivation is not just a fancy story, but indeed the primary driver behind performance. \n\n>1. **Lack of justification: it is less clear about the advantage of designing a complex autoregressive model to satisfy the permutation-invariant property.**\n\nThe reviewer questions why we introduce an autoregressive (AR) approach to a diffusion model, given that the default diffusion model already captures the permutation-invariant property. In DiGress, we observed that full-graph diffusion, while permutation-invariant, requires (1) many sampling/denoising steps to break symmetry and (2) additional features like eigenvectors to further break symmetry. This shows that directly capturing the FULL joint distribution and solving the transformation difficulty (in Sec. 3.3) via diffusion is challenging. Additionally, AR methods still dominate LLMs, indicating their potential to benefit diffusion models. As stated in the abstract, this paper aims to combine the strengths of both approaches: AR’s training and inference efficiency and diffusion’s data efficiency through permutation-invariance.\n\nTo verify our analysis quantitatively, we conduct an ablation study on the maximum hops $K_h$, which controls the degree of autoregression. At $K_h=0$, all nodes have a fixed degree of 1, resulting in a single block per graph, equivalent to full graph diffusion (only) without autoregression. Increasing $K_h$ produces more blocks with smaller average block size, indicating more AR steps.\n\n|QM9|Pard (no AR)|Pard|Pard|Pard|\n|-|-|-|-|-|\n|Maximum hops|0|1|2|3| \n| Average number of blocks|1|4.3| 5.6| 7.75 | \n| Diffusion steps per block|140| 32| 25| 20|\n| Total diffusion steps |140| 140| 140|140|\n| Validity| 93.8 | 97.1| 96.7| 97.0|\n| Uniqueness|96.9|96.5|96.2| 96.1|\n| Mol stability|76.4|86.1|85.4| 86.3|\n| Atom Stability|97.7|98.3|98.3| 98.4|\n\nThis ablation study maintains 140 total diffusion steps across all trials, using the same model architecture, diffusion algorithm, and training settings. The significant improvement from $K_h=0$ to $K_h=1$ confirms that our enhancement stems from breaking the full joint distribution into several **conditional** distributions, effectively combining diffusion and AR approaches.\n\n>2. **The likelihood calculation is more accurate with Chen[9]’s approach than a predetermined order. How does the work justify its advantage over such an approach?** \n\nThe reviewer is concerned that the predefined partial order is not optimal, given that Chen[9] shows that a learned order can be better than a predefined node order like BFS and DFS. We want to clarify that we are not arguing that our predefined **partial** order is optimal, instead, we claim that **partial order** should be used to replace the absolute order in an autoregressive approach as it is fully deterministic and a canonical partial order can be easily defined, which is the cornerstone of the permutation-invariant property we achieved.  On the contrary, the absolute node order contains randomness (as finding a canonical node order is as hard as solving a graph isomorphism test), cannot achieve permutation invariance and hence is data inefficient. Our experiments comparing with many AR methods already verified this. \n\nNevertheless, our predefined **partial** order may not be optimal. In future, a reasonable follow-up work could be to learn a task-dependent partial order based on graph structures, e.g. one can consider the variational approach in Chen[9].  We look forward to seeing better partial order(s) being discovered.\n\n>3. **The analysis in 3.3 is well known, and it is not a concern for generative models, as the sampling process will break the symmetry.**\n\nThe analysis in 3.3 is indeed known in the link prediction setting, but this is the first time being mentioned for graph generation. If you know some paper has mentioned it in generation, we are happy to add references. \n\nIndeed, sampling breaks the symmetry and makes the transformation achievable in certain conditions. We have clearly stated this in Sec. 3.4, which motivates us to use diffusion for capturing block conditional distribution. Nevertheless, as sampling is the only way to help symmetry breaking, lots of sampling steps are needed for a symmetry-intense setting. Splitting a FULL joint distribution to several conditional distributions simplifies it, with each conditional distribution containing less symmetry, which is easier to capture. Hence we show not only a significant improvement in generation quality, but also a great reduction in sampling steps. \n\nWhen $K_h=0$, more diffusion steps breaks symmetries more, thus one may argue that we just need to increase diffusion steps. Thus, we conduct an additional ablation for steps when $K_h=0$.  As shown, there is still a large gap to Diffusion+AR. \n\n|Maximum Hops|0|0|0|0|1|\n|-|-|-|-|-|-|\n| Total Diffusion Steps|70|140|280|490| **140**|\n| Validity| 92.1 |93.8 |94.3|95.2| **97.1** |\n| Uniqueness|96.4|96.9|96.5|96.9| **96.5**|\n| Mol stability|74.0|76.4|79.3|79.2| **86.1** | \n| Atom Stability|97.4|97.7|97.9|98.0| **98.3** |\n\n>4. **Pard seems to have a long inference running time.**\n\nIn diffusion, inference time depends on (1) total number of diffusion steps and (2) resource usage per step. Pard outperforms full-graph diffusion in both aspects:\n1. Pard uses 1/4 steps (140 vs. 500) and significantly outperforms DiGress.  \n2. DiGress denoises the whole graph at each step, while Pard only denoises the next block (significantly smaller) with less resource per step.  \n3. Pard, with its AR mechanism, allows previously generated blocks to be cached, accelerating inference similar to KV cache in LLM inference. \n\n- - -\n### We hope these ablations showcase the advantage of Pard and the intrinsic source of the performance improvement clearly. We are happy to address any concerns and hope you can consider reevaluating our work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vvo8lV2C8W", "reviewer": "Reviewer_2orD", "summary": "This paper proposes a graph generation method that combines AutoRegressive (AR) models and diffusion models. By utilizing a unique partial order, it addresses the issue of non-exchangeable probabilities in AR models and the efficiency problem in diffusion models.", "questions": "1.\tIs there a reasonable explanation for the significant improvement of FCD on ZINC250K compared to other baselines? Similarly, why is there such a large difference in performance between Scaf. and baseline methods on MOSES?", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed block-wise AR diffusion model in this paper offers a new idea for graph generation, particularly by introducing the use of weight-degree to differentiate blocks.\n2. The limitations of equivariant networks demonstrated in this paper also hold value for further exploration and resolution within the community.\n3. The overall structure and writing of the paper are relatively clear.", "weaknesses": "1. There is a part in the paper that I believe needs to be clarified more clearly to ensure logical coherence. Why does diffusion based on equivariant network solve the flaw in equivariant modeling? I think besides the analogy of tempering iron (or higher/lower energy), more mathematical proofs are needed.\n\n2. Ablation of PPGN is necessary to demonstrate its effectiveness.\n\n3. Following the experimental settings of GDSS, NSPDK is also an important metric for QM9 and ZINC250K.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### Thank you for giving positive feedback to our paper, we would like to address all your questions in detail. \n\n>1. **Why does diffusion based on an equivariant network solve the flaw in equivariant modeling?**\n\nThe underlying magic behind the randomness introduced in the diffusion process is relatively straightforward. During each training and inference step, noise is added to the current graph structure (assumed to have many symmetries) through resampling. This process modifies the graph to a different structure with fewer symmetries. Consequently, the number of sampling steps is crucial in controlling the degree of symmetry-breaking. A larger number of sampling steps increases the likelihood of successfully breaking the current symmetries, thereby making it easier to denoise to the target graph. This concept shares similarities with the findings of Abboud et al. in their paper \"The surprising power of graph neural networks with random node initialization.\" We acknowledge the need for a formal proof of its connection to graph energy, and we have highlighted this in our paper to encourage future research. Note that our paper is the first work mentioning the issue of equivalent generative models, and pointing out the connection to diffusion. We hope this can motivate future research for equivalent generative modeling. \n\n\n>2. **Ablation of PPGN is necessary to demonstrate its effectiveness.**\n\nWe have done an ablation study on the QM9 dataset. Please see the following table. \n|QM9|Pard w. Transformer |Pard w. PPGN |Pard w. PPGNTransformer|\n|-|-|-|-|\n|Maximum Hops|3|3|3|\n|Total Diffusion Steps |140|140|140|\n|Validity |26.3 |96.6 |97.1 |\n|Uniqueness| 94.5|96.3 |96.0 |\n|Mol stability|17.6|84.67| 86.2 |\n|Atom Stability|81.4|98.2| 98.4 |\n\nInterestingly, this indicates that PPGN is essential for diffusion with autoregression. As the transformer architecture is used in full-graph diffusion like DiGress, we hypothesize that it is less sensitive when using diffusion directly without any autoregression. Hence, we did another ablation by setting maximum hops $K_h=0$. At $K_h=0$, all nodes have a fixed degree of 1, resulting in a single block per graph, equivalent to full graph diffusion (only) without autoregression. \n\n|QM9|Pard w. Transformer |Pard w. PPGN |Pard w. PPGNTransformer|\n|-|-|-|-|\n|Maximum Hops|0|0|0|\n| Total Diffusion Steps |140|140|140|\n| Validity|93.1|93.3|93.8|\n|Uniqueness|96.3|96.7|96.9|\n|Mol stability|74.7|77.1|76.4|\n|Atom Stability|97.6|97.9|97.7|\n\nThe above result confirms that performance is not much sensitive to architecture when **no** autoregression is employed. \n\n>3. **For experimental settings of GDSS, NSPDK is also an important metric for QM9 and ZINC250K.** \n\nWe apologize for unintentionally missing the NSPDK metric. We now implemented the NSPDK metric, and computed it for QM9 and ZINC250K. Notice that we do not have the number for baselines in QM9 dataset, as we use the harder QM9 setting considering explicit hydrogens, which is introduced in DiGress. For reference, SwinGNN achieves 2.01e-4 NSPDK for a simpler setting without hydrogens. We will update the table in the final version to include the NSPDK metric. \n\n|NSPDK |QM9|ZINC250k|\n|-|-|-|\n|Pard   |2.40e-04|**7.10e-04**|\n|DiGress| \\-|8.75e-3|\n|SwinGNN|\\- |1.64e-03|\n|GDSS   |\\- |1.80e-02|\n\n>4. **Is there a reasonable explanation for the significant improvement of FCD on ZINC250K compared to other baselines? Similarly, why is there such a large difference in performance between Scaf. and baseline methods on MOSES?**\n\nOur method's superior performance on these metrics can be attributed to the synergistic combination of autoregressive (AR) and diffusion models, which allows us to better capture the underlying molecular distribution. For both ZINC250K and MOSES datasets, we used the standardized evaluation code provided in the MOSES repository to compute FCD and Scaf. metrics, ensuring consistency with baseline methods. We are confident in the reproducibility of our results and can provide model checkpoints.\n\nHowever, we are not very familiar with some molecule-specific metric like Scaf. We acknowledge a deeper understanding of molecule-specific metrics like Scaf. would be beneficial. Future collaboration with domain experts in molecular science could provide valuable insights into these performance differences and help refine our approach further.\n\n---\n### We hope we have addressed your concerns and questions, and thank you again for your detailed feedback. If you feel more confident with these additional ablations and explanations, please help us in achieving a better score. Thank you.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "K6QTFVHQWF", "reviewer": "Reviewer_KWRX", "summary": "The paper introduces PARD, a graph generation model that combines autoregressive and diffusion models. Traditional autoregressive models are effective but sensitive to order, while diffusion models are permutation-invariant but need many denoising steps and extra features. PARD overcomes these issues by generating graphs block-by-block using a partial order of nodes and edges. It employs a shared diffusion model with an equivariant network and a higher-order graph transformer, supporting parallel training like GPT. PARD achieves state-of-the-art performance on various datasets, including large ones like MOSES, without extra features.", "questions": "1. Seems that in Fig. 2 the prior of the diffusion process is not the same as the second part of Eq. 6. What is the choice of the graph distribution at timestep T?\n2. The total number of diffusion steps is directly related to number of blocks. I anticipate the generic graphs will have more blocks than QM9. Can you show the total number of diffusion steps for other datasets?\n3. Some of the discussions are redundant can be moved to appendix, like the comparison to DiGress and GRAN in Sec. 3.1 and Sec 3.2, the energy view in Sec. 3.4. The running time comparison can be moved to the experiment section.", "limitations": "There is no discussion about the limitation in the manuscript.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "1. This work presents a successful showcase of the combination of autoregressive modeling with diffusion model on graph.\n2. The proposed partial order ensures the permutation-invariance in the autoregressive generation process.\n3. Impressive experimental results show the effectiveness and efficiency.", "weaknesses": "1. It is unclear how the diffusion model is employed in PARD. Sec 3.1 and the second part of Eq. 6 are not quite relevant to each other. Can you elaborate on that?\n2. Please provide proof or reference for some statements. e.g.: 2-FWL expressivity for the proposed higher-order transformer\n3. Please provide the results of other baselines on QM9 if possible.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### Thank you for these detailed questions and feedback for improving the presentation. Let us provide detailed response to all your questions. \n\n>1. **It is unclear how the diffusion model is employed in PARD. Sec 3.1 and the second part of Eq. 6 are not quite relevant to each other. Can you elaborate on that?** \n\nSure! As you know, diffusion requires input and output to have exactly the same size (same number of nodes and edges), which is shown in Sec 3.1. Hence, to use diffusion for each block’s conditional distribution, we should pad the input (which has B blocks) to the same size of the output (which now has B+1 blocks), that is why in Eq. 6 the second part is actually conditional on the target block’s size, and the first part of Eq.6 captures the distribution of next (i.e. (B+1)-th) block’s size (|.| denotes size). The padding procedure is also shown in Fig. 2, where dashed edges and nodes are added (virtual nodes and edges). After padding, we use the second part of Eq. 6 to model the diffusion process, which is the same as procedures introduced in Sec. 3.1, except that we DO NOT modify all previously generated B blocks: noise is only introduced in the target (B+1)-th block. Please let us know whether this is clear, and we would like to hear your feedback on how to make this easier to understand. Note that you can also find/study the exact implementation in the provided anonymous repo, under pard/parallel/task.py. \n\n>2. **Proof for the statement: 2-FWL expressivity for the proposed higher-order transformer.**\n\nAs the higher-order transformer combines PPGN and Transformer, it shares the same expressivity as PPGN. The reason is simple: the Transformer part (with weaker expressivity) can implement identity mapping, and does not affect the expressivity of the PPGN part. For the 2-FWL expressivity of PPGN, please see the [paper] (https://arxiv.org/abs/1905.11136) for the detailed proof. \n\n>3. **Please provide the results of other baselines on QM9 if possible.**\n\nFor QM9, we adopt the more challenging setting that considers explicit hydrogens, as introduced in DiGress. We avoid the easier setting because most baselines, including DiGress and SwinGNN, can achieve 99% accuracy on it, rendering it an ineffective testbed due to the lack of distinction between models. However, we do not have the performance numbers for other baselines as they did not report their numbers in this more challenging setting. Given the time limitation of the rebuttal period, we apologize that re-running all baselines for the new setting is unrealistic, and hope you can understand. \n\n>4. **The total number of diffusion steps is directly related to the number of blocks. I anticipate the generic graphs will have more blocks than QM9. Can you show the total number of diffusion steps for other datasets?** \n\nAs shown in Appendix Table 6, we can achieve the same result using only 140 total diffusion steps in QM9. To demonstrate the number of blocks for a generic setting, we report the numbers for the grid dataset, which has the largest graph size (100~400). For this dataset, there is a maximum of 27 blocks, with an average of 18.625 blocks. With the default 40 steps we used, the total number of diffusion steps is 745. Note that we haven't conducted an ablation study to reduce the number of diffusion steps as shown in Table 6, and we expect that a smaller number of diffusion steps can be used without sacrificing performance.\n\n>5. **Some of the discussions are redundant can be moved to appendix**\n\nThank you for your suggestion, we fully agree that the part related to DiGress and GRAN can be moved to the appendix, and we will make this adjustment. Please let us know if you think other interesting results should be moved to the main section. \n\n>6. **There is no discussion about the limitation in the manuscript.**\n\nWe briefly discuss the limitation in the Neurips checklist section, but we would like to elaborate further here. One major limitation is that each block currently uses the same number of diffusion steps, which is not ideal and can result in unnecessary sampling steps. Empirical evidence shows that approximately 50% of blocks can be predicted directly without any sampling steps, as they do not encounter transformation problems (introduced in Sec. 3.3). It would be highly beneficial to develop a hardness measure (such as graph energy) for the symmetry problem and use this measure to determine the appropriate number of diffusion steps for each block. This approach could significantly reduce the total number of diffusion steps.\n\n\n---\n### If you feel that we have addressed most of your concerns, please consider supporting us in achieving a better overall score. Thank you for your time.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
### We thank all the reviewers for their feedback and suggestions on our work. Here we first re-iterate the key contributions of our work, and then summarize the list of additional experiments we performed.

---

### **Why a Hybrid (AR+Diffusion) Approach for (Graph) Generation?**

Our proposed Pard for graph generation is the first of its kind in bringing together autoregressive (AR) and diffusion-based generation. We want to emphasize that this approach stands on clear motivation, in other words, we have not simply “slap” diffusion on AR for no obvious reason.

Our contributions and rationale/justification for the effectiveness of PARD are: 1) We establish a **novel partial order** of nodes that is permutation-invariant. Thanks to this novel partial order, autoregression becomes permutation-invariant, which is not the case for ANY prior graph autoregressive method in the literature. This addresses the challenging pain point of AR of being data inefficient and having bad generalization. 2) With the order being partial, the graph is split into blocks, such that we decompose the complex joint distribution is decomposed into **easier** conditional probabilities. Next, we study how to model each block's conditional distribution. For the first time, we have identified the fundamental problems of equivariant model for generation: general graph transformation without symmetry breaking is impossible for ANY equivariant model. This further motivates us to choose diffusion approach to model each block's conditional distribution: the magic of randomness and annealing process. Following the line of reasoning/designs step by step, we found that the combination of AR and diffusion is not accidental, but an inevitable choice. Even more, this inevitable combination successfully combines the strength of both approaches while getting rid of their shortcomings: 
1. With being permutation invariant (+ advantage of diffusion), it generalizes better than AR and being much data efficient (- downside of AR). 
2. With decomposing the hard joint probability to simpler conditional distributions (+ advantage of AR), it uses significantly less diffusion steps while dramatically outperforms pure diffusion method (- downside of diffusion). What is more, each inference step uses less cost as it does not access to the full graph but just the generated part, and can use cache (like the KV cache in LLM inference) to avoid repeated computations (+ advantage of AR). 

The impressive performance improvement (by reviewer 4) strongly shows the effectiveness of Pard. And many detailed advantages have been observed by reviewers: 
* Reviewer 3 has summarized it all well: “By utilizing a unique partial order, it addresses the issue of non-exchangeable probabilities in AR models and the efficiency problem in diffusion models.”
* Reviewer 1’s understanding is also spot-on: “... it removes node order sensitivity …. Within each block, the diffusion model focuses on a much smaller graph and thus has the efficiency to generate a denoised graph.”
* Reviewer 4 states: “successful showcase of the combination of autoregressive modeling with diffusion model”


### **Additional Ablations and Experiments**

Nevertheless, we have further done extensive ablation studies to verify Pard's rationality and designs. There is an interplay between the number of AR vs. diffusion steps in Pard, that is indirectly controlled by maximum hops $K_h$. As $K_h$ increases, the weighted degree of nodes diversify and hence we obtain fewer node equivalences = smaller blocks = more AR steps.
In contrast, when $K_h=0$, we have only a single block, which corresponds to diffusion-only model (no AR). 

1. In the first ablation on QM9 dataset, we keep the total number of diffusion steps (across all AR steps) fixed, and study how performance changes for $K_h$ varied from 0 to 4.

2. In the second ablation, we increase the number of diffusion steps when $K_h=0$ to see if more diffusion within a single block helps achieve better performance without AR, and compare that to $K_h>0$ (i.e. diffusion+AR hybrid).

Based on reviewer feedback, we also do ablation regarding architecture. Recall that Pard combines Transformer with PPGN (coined PPGNTransformer) in a novel design. 

3. We report performance results for Pard w/ PPGN only and Transformer only as compared to the original PPGN+Transformer.

4. We also report results for an additional molecular metric as requested by a reviewer.

---
###  We hope that the additional experiments, discussions, and clarifications lead to a better appreciation of the contributions of our work. Graph generation is a hard problem, gaining popularity only in the last 5 or so years, and we strongly believe that Pard sets a new milestone in this area with its rigorous design and SOTA empirical performance.

Meta-review: The paper introduces a novel framework that combines autoregressive (AR) and diffusion models for graph generation, effectively leveraging the strengths of both approaches while mitigating their inherent weaknesses. Reviewer SjHr praised the paper for its “novel graph decomposition method” that addresses node order sensitivity, noting the efficiency gains in graph denoising and describing the presentation as “smooth” with high impact contributions. Reviewer 2orD highlighted the innovative use of partial ordering to tackle “non-exchangeable probabilities in AR models,” deeming the work to be “technically solid” and offering a fresh perspective on graph generation. Reviewer KWRX echoed these sentiments, acknowledging the paper as a “successful showcase” of AR and diffusion models in tandem and underscored the “impressive experimental results” that demonstrate state-of-the-art performance on various datasets. Despite some concerns raised by Reviewer adow regarding the justification of combining AR with diffusion, the authors provided extensive ablation studies and clarifications, showing that their approach not only reduces the number of diffusion steps but also significantly outperforms existing models. The paper’s rigorous design, clear motivation, and robust empirical results make it a strong candidate for acceptance.
Decision: Accept (poster)