When Edge Independence Fails: Joint Graph Diffusion with Latent Sociability Priors

When Edge Independence Fails: Joint Graph Diffusion with Latent Sociability Priors

arXiv:2610.13765v1 [cs.LG] 9 Oct 2026

Adarsh Jamadandi1 , Nicolas Keriven1 , Aline Roumy2 CNRS, IRISA, Rennes, France1 , INRIA, Rennes, France2 adarsh.jamadandi@irisa.fr, nicolas.keriven@cnrs.fr, aline.roumy@inria.fr

Abstract Discrete graph diffusion models corrupt graph structure through independent edge updates with a Markovian noise model. Combined with the exchangeability requirement on the output distribution, the terminal prior is necessarily an Erdős–Rényi (E-R) random graph. This has a fundamental consequence for unconditional graph generation without node features: in the large graph limit, any GNN denoiser applied to an E-R graph approximately outputs an E-R graph, making effective denoising difficult. In practice, generated graphs fail to recover meaningful node heterogeneity and higher-order structure. Previous models introduced specialized node features to compensate, framing this as an expressivity problem, while the role of the prior remained unexamined. We instead address the root cause by introducing the Latent Sociability Prior (LSP) and a joint diffusion process that co-evolves latent node sociability variables and graph structure, removing edge independence while preserving exchangeability. Unlike existing latent graph diffusion methods, the sociability mechanism requires no complex encoder: its sole role is to guide edge updates and preserve node heterogeneity throughout the trajectory. We validate our approach on multiple graph generation datasets and show that the proposed framework more accurately captures graph distributions than baseline methods without node features.

1

Introduction

Diffusion models [48, 49, 18, 36] have recently emerged as a powerful class of generative models, with major improvements in image [55] and video generation [34]. Motivated by this success, diffusion-based methods have been extended to graph generation. The two most popular approaches are: embedding nodes into a continuous latent space and applying Gaussian diffusion [38, 22, 12], or operating directly in the graph space through a discrete corruption process on edges [3]. The latter approach has been shown to be more appropriate for generating realistic graph structures [17, 51], leading to a growing body of work on both graph diffusion and discrete flow matching [15, 41, 43]. Despite this recent progress, discrete diffusion models also have inherent problems. For instance, scaling to large graphs is a bottleneck as the computational complexity grows quadratically with increasing graph size. Recent methods [9, 31, 42] have made notable progress on addressing these practical limitations. In this work, however, we identify a more fundamental limitation at the core of existing graph diffusion models. We find that, in unconditional graph generation without node features, the combination of edge independence in the forward process and the requirement that the output graph distribution remains exchangeable tightly constrains the terminal distribution, leaving Erdős–Rényi (E-R) as the only admissible prior. We show theoretically and empirically that such graph diffusion models exhibit a fixed-point pathology in the large graph limit: for most architectures including attention-based GNNs, when initialized from an E-R prior, any denoiser approximately outputs constant edge predictions (Theorem 4.2) which is also an E-R random graph. Consequently, the generated graphs tend to look homogeneous and lack higher-order structure. 40th Conference on Neural Information Processing Systems (NeurIPS 2026).

In practice, this failure is commonly attributed to insufficient model expressivity, with auxiliary node features introduced as a remedy even in the unconditional setting [51, 9, 42], leaving the role of the E-R prior unexamined. While such features may improve performance, they can be expensive to compute and obscure the real source of failure. Our claim is therefore not simply that existing models are insufficiently expressive, but that the standard edge-independent discrete diffusion pipeline is fundamentally mismatched with unconditional graph generation. As a resolution, we propose a joint diffusion framework that co-evolves continuous latent variables together with the discrete graph structure, combining the strengths of latent diffusion models and graph-space discrete diffusion. Our framework is built around a new prior inspired by inhomogeneous random graph models [39, 4, 19, 5], termed the Latent Sociability Prior (LSP). Each node is endowed with a positive sociability weight, and edge probabilities are conditioned on these weights, inducing node-level heterogeneity. We jointly diffuse these variables and the graph edges during both noising and denoising, allowing them to guide edge updates throughout the diffusion trajectory. As a consequence, the terminal prior is no longer edge-independent and therefore does not induce the fixed-point behavior of standard discrete denoisers. Crucially, the sociability mechanism is much simpler than existing latent graph diffusion approaches, as its role is not to generate graphs alone but to guide the companion discrete diffusion process. In particular, it requires no pre-trained encoder, and the clean latent variables admit an approximate closed-form expression from the training data. Our contributions can be summarized as follows: 1. We identify a fundamental limitation in existing discrete graph diffusion pipelines. Without node features, an edge-independent terminal prior together with independent edge updates leads to a fixed-point pathology: any denoiser applied to an E-R random graph approximately yields an E-R random graph, making it difficult to escape this regime and preventing recovery of meaningful node heterogeneity and higher-order structure. 2. We propose a joint diffusion framework for graph generation that co-evolves continuous latent variables together with discrete graph structure, allowing latent node heterogeneity to directly guide edge updates throughout both noising and denoising. 3. We instantiate this framework through the Latent Sociability Prior (LSP), a novel exchangeable latent-variable prior inspired by inhomogeneous random graph models. The LSP admits a closed-form approximation for the clean latent variables, bypassing the need for an encoder, while inducing beneficial edge dependencies and preserving node-level heterogeneity. 4. We validate our approach on multiple graph generation benchmarks and show that, even without node features, the proposed framework more accurately captures the target graph distribution compared to existing baselines.

2

Related work

Latent graph diffusion. Extending the original diffusion formulation [48, 49, 18, 36] for graph generation involves embedding the graphs into a low-dimensional continuous space using variational autoencoders (VAEs) and corrupting the graph structure using Gaussian noise in this latent space [38, 22, 12]. Although this approach is appealing since it allows for a computationally friendly diffusion process, it also presents unique challenges. For instance, VAEs are notorious for training instabilities [10] and small reconstruction errors in the encoding-decoding process can affect the structural validity of generated graphs. Further, generating large graphs is challenging since the dimensionality of the latent space itself becomes a bottleneck, limiting the structural detail that can be faithfully recovered. Discrete diffusion for graphs. Another popular approach for graph diffusion is to adopt the discrete diffusion paradigm [3] where the corruption process is carried out directly in the space of graphs through independent edge additions and deletions. This framework has been shown to be more appropriate for generating realistic graph structures, resulting in large improvements in both diffusion models [17, 51, 9, 31, 40, 37, 23, 47] and discrete flow matching [15, 21, 41, 43]. However, most of these advancements address practical issues such as scalability, since the computational burden grows quadratically with increasing graph sizes. In this work, we identify a more fundamental limitation specific to discrete graph diffusion models: the edge-independent forward process forces the terminal 2

prior to be Erdős–Rényi, which leads to a fixed-point pathology that constrains generation quality independently of model capacity. Influence of prior distributions. The role of the prior in graph generation has received some attention. [6, 7] study the limitations of edge-independent generative models and show they cannot simultaneously produce diverse graphs and capture higher-order statistics such as triangle and cycle counts a theoretical finding that directly motivates our work. In the continuous flow matching setting, [8] use embedding-based source distributions as informed starting points, and [52] propose motif-based priors via Gromov–Wasserstein-coupled flow matching, improving structural fidelity at the cost of expensive optimal transport and manual motif specification per graph family. These methods operate outside the discrete diffusion setting and do not address the fixed-point pathology we identify. Our approach requires no optimal transport and no domain-specific prior engineering: node heterogeneity emerges directly from the latent sociability variables by construction.

3

Background on discrete denoising diffusion framework

We recall the discrete denoising diffusion framework for graph generation following [3, 51]. Let Ddata = {G1 , . . . , GM } be a dataset of graphs drawn from an unknown distribution pdata . For a graph G = (X, E) with node features X and edges E, the goal is to learn a distribution pθ (G) from which new graphs can be sampled. Node features and edges are represented via one-hot encodings, giving tensors X ∈ Rn×d and E ∈ Rn×n×b , where d is the number of node feature types and b the number of edge categories. Here we simply consider b = 2 edge categories, with eij ∈ B = {0, 1} denoting the scalar edge state (absence or presence) between nodes i and j, and eij ∈ Rb its one-hot encoding, organized into the edge tensor E ∈ Rn×n×b . Since we focus on unconditional graph generation without node features we set X = 1 throughout, unless otherwise written. The forward process defines a sequence of increasingly noisy graphs G0 , G1 , . . . , GT , where G0 is a clean training graph and GT is drawn from the terminal prior πT . We denote by e0ij ∈ B the clean edge state between nodes i and j in G0 , and by e0ij ∈ Rb its one-hot encoding. The probability of a noisy sequence (G1 , . . . , GT ) given G0 factorizes as q(G1:T | G0 ) =

T Y

q(Gt | Gt−1 )

(1)

t=1

The transition matrix QtE ∈ Rb×b governs one-step edge corruption, with entries [QtE ]rs = q(et = s | et−1 = r), and Q̄tE = Q1E · · · QtE is the cumulative transition matrix. Since transitions act independently on each edge, the per-edge forward marginal is the 1 × b probability vector q(etij | e0ij ) = e0ij Q̄tE . The joint forward marginal over all edges is Y q(Et | E0 ) = q(etij | e0ij ) (2) 1≤i,j≤n

For undirected graphs, noise is applied only to the upper-triangular part of E and then symmetrized. A denoising network ϕθ takes a noisy graph Gt = (1, Et ) and timestep t as input, and outputs for b each node pair (i, j) a probability vector p̂E,t ij ∈ R over edge types. It is optimized via cross-entropy against the clean edge states:   X LCE (p̂E,t , G0 ) = CE e0ij , p̂E,t (3) ij 1≤i,j≤n

New graphs are sampled by running the reverse process from GT ∼ πT . Since node features remain fixed, the reverse distribution factorizes over edges: Y t pθ (Et−1 | Gt ) = pθ (et−1 (4) ij | G ) 1≤i,j≤n

Each factor is computed by marginalizing over the predicted clean edge distribution: X
E,t t t 0 pθ (et−1 q et−1 ij | G ) = ij | eij , eij = r p̂ij (r) r∈B

3

(5)

where q(et−1 | etij , eij = r) is the forward posterior, available in closed form in [51] and p̂E,t ij (r) ij denotes the network’s estimate of the probability that the clean edge takes value r given the noisy graph Gt . As we will see later, by Theorem 4.2, when Gt is an E-R random graph, p̂E,t ij is approximately t t−1 constant across all pairs (i, j), so pθ (et−1 | G ) is the same for all pairs and E again follows an ij E-R distribution. Transition matrices are chosen as in [51] to preserve the empirical marginal distribution of edge types mE ∈ Rb throughout diffusion through QtE = αt I + βt 1b m⊤ E where, βt = 1 − αt . With probability αt the edge state is preserved, and with probability βt it is resampled from mE . As t → T , every edge is driven independently towards mE , so the terminal prior πT := q(GT ) is a product of independent marginals, an Erdős–Rényi random graph where every edge is drawn independently with probability equal to the empirical edge density of the training set. Exchangeability. An important feature of any graph generation method is that it needs to be exchangeable: all permutations of the generated graphs need to be equiprobable. In other words, if we denote by σ · G the relabelling of a graph G by a permutation σ, our entire generation process needs to satisfy pθ (σ · G0 ) = pθ (G0 ) 0 for all σ, G . Fortunately, if a) the prior distribution πT = q(GT ) is exchangeable (which is naturally the case of E-R random graphs), and b) the denoiser ϕθ is permutation equivariant1 , then it is easy to see that the final distribution is exchangeable: we have pθ (σ · Gt−1 | σ · Gt ) = pθ (Gt−1 | Gt ) by equivariance, and q(σ · GT ) = q(GT ) by exchangeability of the prior.

4

Issue with Erdős–Rényi prior

In this section, we show that the E-R prior introduces a fundamental limitation in the generation process: in the large-graph limit, E-R random graphs are approximate fixed points for any denoiser. That is, as the graph size grows, denoising an E-R graph approximately yields another E-R graph, making it increasingly difficult to escape this regime. We begin by asking whether a different prior could have been chosen within the discrete diffusion framework. E-R prior is unavoidable. As we have seen in the previous section, the prior distribution πT needs to be exchangeable to guarantee exchangeability of the whole generation process. Moreover, the discrete diffusion process is based on successive independent edge perturbations, such that the terminal distribution has fully independent edges. We then have the following result, shown in Appendix B.1 for completeness. Lemma 4.1. [2, 20] Any exchangeable random graph model with independent edges is an E-R model. In other words, as long as discrete diffusion operates with independent edges, the terminal distribution πT is necessarily an E-R random graph. E-R is a fixed point for denoisers. Consider a simple denoiser that performs link prediction by first computing node representations with a GNN X̂ = ϕθ (X, E) (recall that we generally consider X = 1 in this paper, but the result below is more generally valid for node features X), then compute edge probabilities using these representations with a similarity function φ: (K)

(K)

p̂ij = φ(xi , xj ) ∈ [0, 1] This method is akin to a Variational Graph Auto-Encoder (VGAE) [26, 27], but when the GNN is a GAT [50], this is close to the graph transformer [11] used in DiGress [51], removing some normalization layers and edge modulation for simplicity 2 . Denote by r q 2 P P P P 2 std(p̂) = n12 ij p̂ij − n12 ij p̂ij , std(X) = n1 i Xi − n1 i Xi (6) 1 that is, ϕ (σ · G) = σ · ϕ (G) θ θ 2 Technically, in vanilla graph transformers the edge probabilities would also be modulated by the input graph p̂ (K)

(K)

ij =

φ(xi , xj , eij ), in which case our result become: p̂E is approximately an affine function of E instead of being approximately constant. That is: the output graph is a probabilistic “sum” of the input E-R graph and another E-R graph. We choose our version for simplicity.

4

the standard deviation of the edge probabilities and input node features, respectively, such that E-R random graphs have exactly std(p̂) = 0. We have the following result. Theorem 4.2. Consider an input graph E of size n, drawn from an Erdős–Rényi model with parameter p. Then, for the GNNs outlined below, there is C such that: for all δ, ϵ > 0, if n is large enough, then with probability at least 1 − δ, std(p̂) ≲ Cstd(X) + ϵ where the multiplicative constant only depends on the parameters of the GNN. We have: • if the GNN is a GAT [50] with K layers, then C = (1/p)K , and n is such that pn ≳ log(n/δ)

(7)

In particular, one can choose ϵ = 0 in this case. • if the GNN is a GCN [28], then C = O(1), and n is such that pn ≳ ϵ−2 log(n/δ)

(8)

• if the GNN is GIN [53], for all r > 0 there exists Cr such that the result is valid with C = O(1), and n such that pn ≳ ϵ−2 log(n/δ)

and

n ≥ Cr δ −r

(9)

The details for this theorem and precise description of the considered GNNs are given in Appendix B.2. In short, we thus have the following: when the node features have low standard deviation, the denoiser outputs approximately constant edge probabilities. Constant features are an extreme version of that, since std(1) = 0. In other words, the class of E-R random graphs represents an approximate fixed-point for denoisers, and as a result node heterogeneity remains low during the whole diffusion process (Figure 2), as all graphs will be almost E-R-like. Applicability of Theorem 4.2 on Graph Transformer. We prove Theorem 4.2 on a simplified link predictor in Appendix B.2 while in practice DiGress uses a complex Graph Transformer with its edge predictions modulated by FiLM layers [51]. We argue this does not change the conclusion as this setup provides with a tractable model to study behavior. Further, the edge modulation in the DiGress transformer is applied per pair: each pair’s modulation is computed from its own edge feature and from the global (timestep) vector, so it does not introduce dependence between different pairs. With constant node features, the predicted edge logits depend on each pair only through its own current state and a global summary of the graph, leading to E-R-like graphs and preventing node heterogeneity from emerging. Empirically, this is what we observe on the model used in practice: Fig. 2 shows the node propensity variance of the actual DiGress denoiser, with edge modulation, collapsing toward zero at high noise, while the LSP-based model retains heterogeneity throughout. Structural node features. The above issue has often been interpreted as a lack of “expressivity” of GNNs, hampering their denoising abilities. To fix this, many works add structural node features computed a posteriori at each denoising step, such as degrees, cycle counts, and so on. While such node features indeed counteract the incapacity of GNNs to compute these quantities, they only offer limited fix to the E-R problem, as shown in the following Lemma proved in Appendix B.3. Lemma 4.3. Consider a dense E-R random graph with parameter p = O(1) for simplicity. Consider a template graph H of size r, and denote by Ci the number of subgraphs equal to H containing node i. Then C = E(Ci ) does not depend on i, and with probability at least 1 − δ, p std(Ci /C) ≲ log(n/δ)/n Hence, in the limit, this does not solve the problem, as the standard deviation of such features also vanishes. This is shown in Figure 7 in the Appendix.

5

Latent variable guided discrete diffusion

Lemma 4.1 establishes that the E-R prior is not merely a sub-optimal choice but an unavoidable consequence of edge independence and exchangeability, and Theorem 4.2 and Lemma 4.3 state that 5

E-R graphs become difficult to denoise in the large graph limit, even with structural features computed a posteriori. To resolve this, we propose a new prior that induces node-level heterogeneity directly through latent variables, along with the corresponding joint diffusion process on latent variables and discrete graph structure. (E0 , u 0 )

q(u 1 u 0 ) q(E1 E0 , u 0 )

Original edge

(E0 , u 0 )

(E1 , u 1 )

Added edge

p (u 0 u 1 , E1 ) p (E0 E1 , u0, 1 )

(E2 , u 2 )

q(u 2 u 1 ) q(E2 E1 , u 0 )

q(u T u T 1 ) q(ET ET 1 , u 0 )

Removed edge

(E1 , u 1 )

MLP

Forward process (add noise)

p (u 1 u 2 , E2 ) p (E1 E2 , u0, 2 )

(E2 , u 2 )

uT

(E

T 1, u T 1)

MLP

(ET , u T )

2 I), ET ( LSP , LSP

T

p (u T 1 u T , ET ) p (ET 1 ET , u0, T )

(ET , u T )

MLP

Reverse process (denoise)

Figure 1: Joint diffusion over edges and latent sociability. Top: the latent sociability ut and edge states Et are jointly noised, with edge transitions conditioned on u0 , until reaching uT ∼ 2 N (µLSP , σLSP ) and ET ∼ πT . Bottom: during denoising, the graph transformer ϕθ predicts the less t−1 noisy latent û , which conditions the reverse edge transition pθ (Et−1 | Et , ût−1 ). 5.1

Latent Sociability Prior (LSP)

Unlike existing latent graph diffusion approaches [47], which encode the entire graph structure into high-dimensional latent space and may require complex autoencoders, the role of the latent variables here is strictly to enforce node heterogeneity along the discrete diffusion process. This allows our choice of latent model to be extremely simple. i.i.d.

Definition 1 (Latent Sociability Distribution [39]). Let w1 , . . . , wn ∼ pW be latent sociability weights, where pW is a distribution on R>0 to be specified in Section 5.2. The latent sociability distribution defines a random undirected graph G with conditionally independent Bernoulli edges as P(eij = 1 | wi , wj ) = 1 − e−wi wj ,

i < j,

(10)

We refer to this distribution of random graphs as Latent Sociability Prior (LSP). By construction, the edges are conditionally independent given w1 , . . . , wn but marginally dependent, while global exchangeability is preserved. Intuitively, a node with high weights wi will tend to be more “connected”: all the pij will be higher. Hence, a distribution pW with a large variance guarantees a diverse profile of connection propensities (see Figure 2), and empirically a variety of higher-order structures as well (Figure 6), unlike the E-R prior. Integrating this latent-variable prior into the discrete denoising framework of Section 3 is not immediately obvious. We develop below a joint diffusion process that combines continuous Gaussian diffusion [18] on the latent weights with the discrete corruption process on the graph edges. 5.2

Joint diffusion with LSP

A direct diffusion on the weights wi is not suitable, since Gaussian diffusion would not preserve the positivity constraint and could produce invalid intermediate states. We therefore reparameterize the weights as wi = exp(ui ) with ui ∈ R unconstrained. Under a Gaussian prior on ui , the induced prior on wi is log-normal. After this reparameterization, the edge probability in Equation 10 becomes ui +uj

pij = 1 − e−e

(11)

Forward process. We define a joint forward noising process over the continuous latent vector u and the discrete edge tensor E. Given a clean graph G0 , one must first construct the corresponding clean latent vector u0 . While usual latent approaches require training an encoder, in the LSP u0 admits a simple, approximate closed-form expression. 6

Lemma 5.1. Consider an LSP random graph. Assuming a sparse regime where ui = O(−cn ) for some constant cn ≫ 0, we have for all i E(di | u) = Ceui + O(ne−4cn ) for some constant C = O(ne−cn ), where di denotes the degree of node i. Following this, we set u0i ≈ log(di + δ) + µ where δ > 0 is a small smoothing constant. To better capture relative degree heterogeneity across different training graphs, we remove the graph-level mean and obtain 1 X u0i = µLSP + log(di + δ) − log(dk + δ) (12) |V | k∈V

where µLSP is the mean of the terminal Gaussian prior. Similarly to enforcing the marginal edge density in the E-R prior, we calibrate the parameters (µLSP , σLSP ) from the training data, as detailed in Appendix A.1. We corrupt the latent variables using the shifted and scaled DDPM forward process ut = µLSP +

√

√ ᾱt (u0 − µLSP ) + σLSP 1 − ᾱt ϵ,

ϵ ∼ N (0, I)

(13)

2 so that ut = u0 at t = 0 and ut converges in distribution to N (µLSP , σLSP I) as t → T . The derivation and reverse posterior are given in Appendix A.2.

For the discrete component, we modify the transition matrix of Section 3 by replacing the global stationary mE with a pair-specific stationary p0ij = [ 1−p0ij , p0ij ] ∈ Rb , where p0ij = 1−e−e 0 ⊤ Qt,ij E = αt I + βt 1b (pij ) ,

0 u0 i +uj

. This gives the pair-specific transition matrices

0 ⊤ Q̄t,ij E = ᾱt I + (1 − ᾱt )1b (pij )

(14)

t−1 t with entries [Qt,ij = r, u0 ). Since u0 is a deterministic function of G0 , all E ]rs = q(eij = s | eij matrices are fixed given (E0 , u0 ), and the joint forward marginal factors over independent edges:

q(Et | E0 , u0 ) =

Y

q(etij | e0ij , u0 ),

q(etij | e0ij , u0 ) = e0ij Q̄t,ij E

(15)

1≤i,j≤n

This has the same closed-form structure as Equation 2, with pair-specific stationaries, so the forward posteriors needed for reverse sampling remain tractable [51]. Crucially, parameterizing the transitions by u0 rather than ut is what makes this possible: if the transitions depended on ut , the matrices would be random variables and the product structure in Equation 15 would no longer hold. Reverse process. Starting from (ut , Et ), the network ϕθ predicts the clean latent vector û0,t = ϕθ (ut , Et , t) and updates both components separately. The reverse kernel factorizes as pθ (ut−1 , Et−1 | ut , Et ) = pθ (ut−1 | ut , Et ) pθ (Et−1 | û0,t , Et )

(16)

For the continuous component, the reverse update follows the DDPM posterior in the shifted-andscaled parameterization derived in Appendix A.2. For the discrete component, û0,t determines pair-specific reverse transition matrices 0,t ⊤ Q̂t,ij E = αt I + βt 1b (p̂ij ) ,

ˆ t,ij = ᾱ I + (1 − ᾱ )1 (p̂0,t )⊤ Q̄ t t b ij E

0,t 0,t û +û i j

(17)

0,t 0,t −e where p̂0,t and p̂0,t ij = 1 − e ij = [ 1 − p̂ij , p̂ij ]. The reverse edge distribution factorizes as in Equation 4, with each factor given by X E,t t 0,t t 0,t pθ (et−1 q(et−1 (18) ij | eij , û ) = ij | eij , eij = r; û ) p̂ij (r) r∈B

where the posterior is computed from the pair-specific matrices in Equation 17. 7

Training objective. We retain the cross-entropy objective of Equation 3 for edge prediction and augment it with an MSE loss on the predicted clean latents: ! n X 1 X 0,t E,t L= CE(eij , p̂ij ) + λu ∥û − u0i ∥22 (19) n i=1 i 1≤i,j≤n

where λu ∈ R+ controls the relative weight of the latent regression term. The variational derivation and its scope are detailed in Appendix C.

6

Experiments

Datasets. We introduce a new synthetic benchmark by sampling subgraphs from two real-world datasets, Cora [32] and Chameleon [44], which we refer to as CoraChameleon. Unlike commonly used synthetic benchmarks such as SBM or planar graphs, this better reflects the structural properties of realworld graphs; details are given in Appendix E. We generate 3000 graphs for n ∈ {10, 20, 50, 100} and 1400 for n = 500, across node sizes n ∈ {10, 20, 50, 100, 500}. We also conduct experiments on the commonly used benchmarks Ego and Community datasets [54], with a 60/20/20 train/test/validation split. 6.1

JointLSP preserves node heterogeneity at high noise

To study whether the proposed joint diffusion framework with LSP preserves node-level heterogeneity during the diffusion process, we define a node propensity score Sit using the predicted clean edge P E,t E,t 1 probabilities at diffusion step t. For each node i, we compute Sit = n−1 j̸=i p̂ij , where p̂ij denotes the model’s predicted clean edge probability between nodes i and j at time t. Intuitively, Sit measures the average connectivity propensity of node i at a given noise level. To quantify how much this varies across nodes, we compute V t = Vari=1,...,n (Sit ). We evaluate this metric at different diffusion steps t ∈ {500, 50, 0}, where t = 500 corresponds to the maximally noisy state, over training graphs in a batch. For each graph, V t is computed across all nodes, and the mean and standard deviation are reported over graphs in the batch. This is shown for CoraChameleon-Node100 in Figure 2. The results show that the node heterogeneity induced by the JointLSP is preserved even at high noise levels. In contrast, under the original DiGress marginal prior without node features, the predicted edge probabilities become increasingly uniform across node pairs as t → T , causing the node propensity scores to collapse toward a common value. This indicates that, at highly noisy states, the model effectively starts from an ER graph and must rely on auxiliary handcrafted features to recover richer structure during denoising. By contrast, our framework allows the model to retain variation in node propensity throughout the reverse process, providing an intrinsic source of heterogeneity without requiring such external features.

DiGress

JointLSP+DiGress

JointLSP+DiGress

0.004

Var(si)

Var(si)

0.004

0.002

0.002 0.000

DiGress

0

0.000

200 400 Timestep t

(a) Forward Noising Process.

400

200 Timestep t

0

(b) Reverse Denoising Process.

Figure 2: We compare the variance of node propensity scores for both the original DiGress and JointLSP+DiGress (LSP in the figure). We observe at terminal noisy state, our prior helps maintain a healthy level of node heterogeneity as opposed to DiGress which loses node distinguishability during the diffusion process.

8

6.2

Experiments on graph generation

Evaluation metrics. We evaluate generated graphs using degree distribution, clustering coefficient, triangle count, and degree assortativity. We additionally report the power-law exponent of the degree sequence (PLE) and characteristic path length (CPL), following [7] and [9]. For each statistic, we test)2 report the MMD ratio r = MMD(generated, following [51]. Lower is better, with r = 1 as the MMD(train, test)2 natural baseline. Ablation with auxiliary features. We first establish a DiGress [51] baseline using the full set of recommended auxiliary features. We find that the performance of existing graph diffusion models relies heavily on these additional node and graph-level features rather than on the diffusion process alone. These features fall into two categories: structural features such as k-cycle counts, which we address in Lemma 4.3, and spectral features such as eigenvectors and eigenvalues computed at every denoising step. We note however that the latter are expensive to compute, and prohibitive at scale. The full list is given in Appendix Table 11. In Table 1 we present results on CoraChameleon-Node100 for three methods: DiGress+k structural features, by randomly choosing feature subsets of size k, averaged over 3 runs, JointLSP+DiGress, which augments DiGress with our joint diffusion framework and LSP but uses no auxiliary features (k = 0), and finally Digress with the full set of structural and spectral features (k = 17), which is more computationally intensive. The training details and hyperparameters are given in Appendix E.1. We can observe that structural features are consistently insufficient: even with k = 10 features, performance on higher-order statistics such as triangle count and assortativity remains poor. We also conduct another ablation study in Table 6, where we supply degree as both node and graph-level feature and observe similar results. This is consistent with Lemma 4.3: structural features computed on a near-ER graph are themselves nearly constant across nodes, and therefore provide little additional information to the denoiser at high noise levels. JointLSP+DiGress outperforms DiGress with up to k = 10 features on clustering coefficient, triangle count, and assortativity, demonstrating that improving the prior directly addresses these limitations. Nevertheless, JointLSP+DiGress is still outperformed by the use of spectral features, even if much more expensive to compute. Integrating such spectral components into our novel joint diffusion process is a major avenue for future work. Unconditional graph generation without node features. In Table 2 we present results for CoraChameleon datasets with n ∈ {10, 20, 50, 100} comparing DiGress without features against our proposed method. Our goal is not to claim state-of-the-art performance, but to isolate the no-nodefeature setting in which the standard discrete diffusion pipeline is most constrained. Our method shows consistent improvements on triangle count and assortativity [35, 14]. At n = 100, DiGress performs better on degree distribution and PLE, which likely reflects occasional over-correction of the degree distribution under the stronger node heterogeneity induced by LSP. Additional results are reported in the appendix: results for JointLSP+SparseDiff on CoraChameleon across n ∈ {10, 20, 50, 100, 500} and on the Ego and Community datasets are given in Appendix D. Finally, Table 6 examines whether supplying node degree directly as an auxiliary feature to DiGress can close the gap, showing that while degree features improve some metrics, they cannot recover the higher-order structural statistics that the LSP improves confirming that the benefit of our method is not reducible to the degree information used in constructing u0 .

7

Conclusion

We identify a fundamental limitation in discrete graph diffusion models for unconditional graph generation without node features: the combination of independent edge updates and an E-R terminal prior leads to a fixed-point pathology in the large graph limit, where any GNN denoiser applied to an E-R graph approximately outputs an E-R graph. We propose the Latent Sociability Prior, a simple latent-variable prior that is co-diffused with discrete edge updates in a joint diffusion framework. By preserving node heterogeneity throughout the diffusion trajectory, LSP enables the model to recover higher-order graph structure without relying on auxiliary structural features. We validate this on graph generation benchmarks across multiple graph sizes. 9

Table 1: Feature subset ablation for DiGress on CoraChameleon-Node100. JointLSP+DiGress (k = 0, no features) is included for direct comparison. Bold: best result excluding the k = 17 ceiling. Degree ↓ Clustering ↓ Triangles ↓ Assortativity ↓ PLE ↓ CPL ↓ DiGress + Structural features k=2 9.32±3.08 5.08±2.95 k=4 7.01±0.53 9.73±7.67 k=8 10.88±11.42 5.89±4.60 k = 10 4.25±1.51 10.72±6.46

11.75±4.50 11.46±4.55 7.45±5.08 10.06±6.11

118.18±2.68 107.68±12.37 79.81±52.72 70.54±40.85

7.43±2.65 10.07±5.75 7.04±5.38 6.99±3.69

47.23±8.47 43.99±4.43 36.55±19.28 34.47±21.49

JointLSP+DiGress (no features) k=0 10.50±0.16 2.07±0.10

2.33±0.15

59.72±0.75

10.79±0.19

44.99±0.29

DiGress + Structural features + Spectral features k = 17 0.93±0.00 1.95±0.00 1.68±0.00

3.55±0.00

1.53±0.00

1.92±0.00

Table 2: MMD ratios for unconditional graph generation under no-node features. Degree ↓ Clustering ↓ Triangles ↓ Assortativity ↓ PLE ↓ CPL ↓ DiGress (no features) n = 10 6.30±1.57 n = 20 22.47±1.63 n = 50 21.09±0.91 n = 100 4.53±0.11

2.46±0.34 1.44±0.00 1.51±0.01 11.33±0.27

15.28±7.27 58.45±9.88 16.90±0.23 14.82±0.12

12.41±1.55 49.80±3.08 70.67±1.95 101.95±2.13

35.40±6.41 15.84±2.39 18.57±1.07 4.64±0.17

12.97±4.19 11.46±2.22 55.49±3.01 39.68±1.14

JointLSP+DiGress (no features) n = 10 5.19±1.61 1.79±0.06 n = 20 11.13±1.29 1.40±0.00 n = 50 8.01±0.42 1.40±0.00 n = 100 10.50±0.16 2.07±0.10

13.45±4.25 8.38±0.92 4.87±0.80 2.33±0.15

1.25±0.25 14.04±3.72 33.18±1.16 59.72±0.75

23.58±4.95 34.19±3.47 10.77±0.69 10.79±0.19

12.93±3.90 7.82±1.24 30.65±1.71 44.99±0.29

Limitations and future work. This work focuses on a key limitation in existing graph diffusion models and several questions remain. Our framework is most suited to graphs with absent or limited node features. For molecular generation, where rich semantic features are available, the fixed-point pathology is less of a concern and the benefit of LSP is expected to be minimal. Combining LSP with auxiliary node features is a natural next step, but is non-trivial since LSP is already informative at high noise levels contrary to E-R prior which is uninformative. Thus, there is no guarantee that the auxiliary features will compound the benefits of the LSP. Promising future directions could include designing auxiliary features that complement the LSP, rather than duplicating the degree heterogeneity already captured by the sociability variables. In particular, spectral features appear important for improving community-level structure, but explicitly computing eigenvectors or eigenvalues at every denoising step can be expensive. One possibility is to extend the LSP itself with a community-aware component, by replacing the sociability prior with a calibrated community-conditioned variant. This would make the terminal prior informative about degree heterogeneity and community structure.

Acknowledgments and Disclosure of Funding This work was funded by the European Union ERC-2024- STG-101163069 MALAGA.

10

References [1] Ralph Abboud, İsmail İlkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization, 2021. URL https://arxiv. org/abs/2010.01179. [2] David J. Aldous. Representations for partially exchangeable arrays of random variables. Journal of Multivariate Analysis, 11(4):581–598, 1981. ISSN 0047-259X. doi: https://doi. org/10.1016/0047-259X(81)90099-3. URL https://www.sciencedirect.com/science/ article/pii/0047259X81900993. [3] Jacob Austin, Daniel D. Johnson, Jonathan Ho, Daniel Tarlow, and Rianne van den Berg. Structured denoising diffusion models in discrete state-spaces. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 17981–17993. Curran Associates, Inc., 2021. URL https://proceedings.neurips.cc/paper_files/paper/2021/file/ 958c530554f78bcd8e97125b70e6973d-Paper.pdf. [4] Béla Bollobás, Svante Janson, and Oliver Riordan. The phase transition in inhomogeneous random graphs. Random Structures and Algorithms, 31(1):3–122, June 2007. ISSN 1098-2418. doi: 10.1002/rsa.20168. URL http://dx.doi.org/10.1002/rsa.20168. [5] François Caron and Emily B. Fox. Sparse graphs using exchangeable random measures. Journal of the Royal Statistical Society Series B: Statistical Methodology, 79(5):1295–1366, 09 2017. ISSN 1369-7412. doi: 10.1111/rssb.12233. URL https://doi.org/10.1111/rssb.12233. [6] Sudhanshu Chanpuriya, Cameron Musco, Konstantinos Sotiropoulos, and Charalampos E. Tsourakakis. On the power of edge independent graph models. CoRR, abs/2111.00048, 2021. URL https://arxiv.org/abs/2111.00048. [7] Sudhanshu Chanpuriya, Cameron N Musco, Konstantinos Sotiropoulos, and Charalampos Tsourakakis. On the role of edge dependency in graph generative models. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 6325–6345. PMLR, 21–27 Jul 2024. URL https://proceedings.mlr.press/v235/chanpuriya24a.html. [8] Harvey Chen, Nicolas Zilberstein, and Santiago Segarra. Prior-informed flow matching for graph reconstruction, 2026. URL https://arxiv.org/abs/2601.22107. [9] Xiaohui Chen, Jiaxing He, Xu Han, and Li-Ping Liu. Efficient and degree-guided graph generation via discrete diffusion modeling, 2023. URL https://arxiv.org/abs/2305. 04111. [10] David Dehaene and Rémy Brossard. Re-parameterizing vaes for stability. abs/2106.13739, 2021. URL https://arxiv.org/abs/2106.13739.

CoRR,

[11] Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs, 2021. URL https://arxiv.org/abs/2012.09699. [12] Iakovos Evdaimon, Giannis Nikolentzos, Christos Xypolopoulos, Ahmed Kammoun, Michail Chatzianastasis, Hadi Abdine, and Michalis Vazirgiannis. Neural graph generator: Featureconditioned graph generation using latent diffusion models, 2024. URL https://arxiv.org/ abs/2403.01535. [13] Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019. [14] Jacob G. Foster, David V. Foster, Peter Grassberger, and Maya Paczuski. Edge direction and the structure of networks. Proceedings of the National Academy of Sciences, 107(24):10815–10820, 2010. doi: 10.1073/pnas.0912671107. URL https://www.pnas.org/doi/abs/10.1073/ pnas.0912671107. 11

[15] Itai Gat, Tal Remez, Neta Shaul, Felix Kreuk, Ricky TQ Chen, Gabriel Synnaeve, Yossi Adi, and Yaron Lipman. Discrete flow matching. Advances in Neural Information Processing Systems, 37:133345–133385, 2024. [16] Lukas Gonon, Thilo Meyer-Brandis, and Niklas Weber. Universality and approximation rates of graph neural networks with random features, 2026. URL https://arxiv.org/abs/2607. 26699. [17] Kilian Konstantin Haefeli, Karolis Martinkus, Nathanaël Perraudin, and Roger Wattenhofer. Diffusion models for graphs benefit from discrete state spaces, 2023. URL https://arxiv. org/abs/2210.01549. [18] Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. CoRR, abs/2006.11239, 2020. URL https://arxiv.org/abs/2006.11239. [19] Remco van der Hofstad. Random Graphs and Complex Networks. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2016. [20] Douglas N. Hoover. Relations on probability spaces and arrays of random variables. Technical report, Institute for Advanced Study, Princeton, NJ, 1979. URL https://www.stat. berkeley.edu/~aldous/Research/hoover.pdf. Preprint. [21] Keyue Jiang, Jiahao Cui, Xiaowen Dong, and Laura Toni. Bures-wasserstein flow matching for graph generation. In The Fourteenth International Conference on Learning Representations, 2026. URL https://openreview.net/forum?id=5Bl5qf3fON. [22] Jaehyeong Jo, Seul Lee, and Sung Ju Hwang. Score-based generative modeling of graphs via the system of stochastic differential equations. 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 10362–10383. PMLR, 17–23 Jul 2022. URL https://proceedings.mlr.press/ v162/jo22a.html. [23] Mahdi Karami. Higen: Hierarchical graph generative networks, 2025. URL https://arxiv. org/abs/2305.19337. [24] Nicolas Keriven and Samuel Vaiter. Sparse and smooth: improved guarantees for spectral clustering in the dynamic stochastic block model. Electronic Journal of Statistics, 16:1330 – 1366, 2022. [25] Nicolas Keriven and Samuel Vaiter. What functions can graph neural networks compute on random graphs? the role of positional encoding. In Neural Information Processing Systems (NeurIPS), 2023. [26] Diederik P Kingma and Max Welling. Auto-encoding variational bayes, 2022. URL https: //arxiv.org/abs/1312.6114. [27] Thomas N. Kipf and Max Welling. Variational graph auto-encoders, 2016. URL https: //arxiv.org/abs/1611.07308. [28] Thomas N. Kipf and Max Welling. Semi-Supervised Classification with Graph Convolutional Networks. In ICLR, 2017. [29] Jing Lei and Alessandro Rinaldo. Consistency of spectral clustering in stochastic block models. Annals of Statistics, 43:215–237, 2015. ISSN 00905364. doi: 10.1214/14-AOS1274. [30] Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graph evolution: Densification and shrinking diameters, 2007. URL https://arxiv.org/abs/physics/0603229. [31] Mufei Li, Eleonora Kreacic, Vamsi K. Potluru, and Pan Li. Graphmaker: Can diffusion models generate large attributed graphs?, 2024. URL https://openreview.net/forum? id=ledQ1BCrwc. 12

[32] Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3(2): 127–163, 2000. doi: 10.1023/A:1009953814988. URL https://doi.org/10.1023/A: 1009953814988. [33] Colin McDiarmid. On the method of bounded differences. In Surveys in combinatorics, 1989 (Norwich, 1989), volume 141 of London Math. Soc. Lecture Note Ser., pages 148–188. Cambridge Univ. Press, Cambridge, 1989. [34] Andrew Melnik, Michal Ljubljanac, Cong Lu, Qi Yan, Weiming Ren, and Helge Ritter. Video diffusion models: A survey, 2024. URL https://arxiv.org/abs/2405.03150. [35] M. E. J. Newman. Mixing patterns in networks. Physical Review E, 67(2), February 2003. ISSN 1095-3787. doi: 10.1103/physreve.67.026126. URL http://dx.doi.org/10.1103/ PhysRevE.67.026126. [36] Alexander Quinn Nichol and Prafulla Dhariwal. Improved denoising diffusion probabilistic models. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 8162–8171. PMLR, 18–24 Jul 2021. URL https://proceedings.mlr.press/v139/ nichol21a.html. [37] Matteo Ninniri, Marco Podda, and Davide Bacciu. Graph diffusion that can insert and delete, 2025. URL https://arxiv.org/abs/2506.15725. [38] Chenhao Niu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon. Permutation invariant graph generation via score-based generative modeling. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 4474–4484. PMLR, 26–28 Aug 2020. URL https://proceedings.mlr. press/v108/niu20a.html. [39] Ilkka Norros and Hannu Reittu. On a conditionally poissonian graph process. Advances in Applied Probability, 38(1):59–75, 2006. doi: 10.1239/aap/1143936140. [40] Nagham Osman, Keyue Jiang, Davide Buffelli, Xiaowen Dong, and Laura Toni. Lgdc: Latent graph diffusion via spectrum-preserving coarsening, 2025. URL https://arxiv.org/abs/ 2512.01190. [41] Yiming Qin, Manuel Madeira, Dorina Thanou, and Pascal Frossard. Defog: Discrete flow matching for graph generation. In International Conference on Machine Learning (ICML), 2025. [42] Yiming QIN, Clement Vignac, and Pascal Frossard. Sparsediff: Sparse discrete diffusion for scalable graph generation. Transactions on Machine Learning Research, 2025. ISSN 2835-8856. URL https://openreview.net/forum?id=kuJ3lpxnVC. [43] Daan Roos, Oscar Davis, Floor Eijkelboom, Michael Bronstein, Max Welling, İsmail İlkan Ceylan, Luca Ambrogioni, and Jan-Willem van de Meent. Categorical flow maps, 2026. URL https://arxiv.org/abs/2602.12233. [44] Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. CoRR, abs/1909.13021, 2019. URL http://arxiv.org/abs/1909.13021. [45] Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks, 2021. URL https://arxiv.org/abs/2002.03155. [46] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. AI Magazine, 29(3):93, Sep. 2008. doi: 10.1609/aimag.v29i3.2157. URL https://ojs.aaai.org/index.php/aimagazine/ article/view/2157. [47] Antoine Siraudin and Christopher Morris. Principled latent diffusion for graphs via laplacian autoencoders. arXiv preprint arXiv:2601.13780, 2026. 13

[48] Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In Francis Bach and David Blei, editors, Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 2256–2265, Lille, France, 07–09 Jul 2015. PMLR. URL https://proceedings.mlr.press/v37/sohl-dickstein15.html. [49] Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution, 2020. URL https://arxiv.org/abs/1907.05600. [50] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. In ICLR, 2018. [51] Clement Vignac, Igor Krawczuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pascal Frossard. Digress: Discrete denoising diffusion for graph generation, 2023. URL https: //arxiv.org/abs/2209.14734. [52] Asiri Wijesinghe, Sevvandi Kandanaarachchi, Daniel M. Steinberg, and Cheng Soon Ong. Flowette: Flow matching with graphette priors for graph generation, 2026. URL https: //arxiv.org/abs/2602.23566. [53] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. URL https: //openreview.net/forum?id=ryGs6iA5Km. [54] Jiaxuan You, Rex Ying, Xiang Ren, William L. Hamilton, and Jure Leskovec. Graphrnn: A deep generative model for graphs. CoRR, abs/1802.08773, 2018. URL http://arxiv.org/ abs/1802.08773. [55] Tianyi Zhang, Zheng Wang, Jing Huang, Mohiuddin Muhammad Tasnim, and Wei Shi. A survey of diffusion based image generation models: Issues and their solutions, 2023. URL https://arxiv.org/abs/2308.13142.

14

A

Appendix

Algorithm 1 Calibrating the LSP terminal prior Require: Training dataset Ddata , smoothing constant δ > 0, number of quadrature nodes K 1: for each graph G ∈ Ddata and each node P i ∈ V (G) do 2: Compute ũi = log(di + δ) − |V1 | k∈V log(dk + δ) 3: end for
4: σLSP ← std {ũi : i ∈ V (G), G ∈ Ddata } ▷ std over all nodes across all training graphs P 2|EG | 1 5: ρdata ← |D ▷ mean empirical edge density over training graphs G∈Ddata nG (nG −1) data | 2 6: Initialize µ0LSP ← 21 (log ρdata − σLSP ) ▷ sparse-regime approximation, see Appendix A.1 7: Solve ρ(µLSP ) = ρdata for µLSP using K-node Gauss-Hermite quadrature to evaluate ρ(·), starting from µ0LSP 8: return (µLSP , σLSP )

Algorithm 2 Training JointLSP Require: A graph G = (1, E0 ), calibrated prior parameters (µLSP , σLSP ) from Algorithm 1 1: Sample t ∼ U({1, . . . , T }) 2: Compute u0 from G using Equation 12 3: Sample ut ∼ q(ut | u0 ) using Equation 13 0 u0 i +uj

4: Compute p0ij for all pairs (i, j) using p0ij = 1 − e−e

5: Sample Et ∼ q(Et | E0 , u0 ) using Equation 15 6: (û0,t , p̂E,t ) ← ϕθ (ut , Et , t) 7: Optimizer step on L(û0,t , p̂E,t ; u0 , E0 ) using Equation 19

Algorithm 3 Sampling from JointLSP Require: Trained network ϕθ , calibrated prior parameters (µLSP , σLSP ) 1: Sample n from the empirical node-count distribution of Ddata 2 I) 2: Sample uT ∼ N (µLSP , σLSP T T T −e 3: Compute pT ij = [1 − pij , pij ] where pij = 1 − e

T uT i +uj

for all pairs (i, j)

4: Sample ET : each edge (i, j) independently from Bernoulli(pT ij ) 5: for t = T down to 1 do 6: (û0,t , p̂E,t ) ← ϕθ (ut , Et , t) 7: Sample ut−1 ∼ pθ (ut−1 | ut , Et ) using Equation 37 8: Sample Et−1 ∼ pθ (Et−1 | û0,t , Et ) using Equation 18 9: end for 10: return E0

A.1

Constructing the Latent Sociability Prior

We derive the calibration procedure for the terminal prior parameters (µLSP , σLSP ), which are estimated from the training data and fixed before training begins. The goal is to choose these parameters so that graphs sampled from the LSP terminal prior match the empirical edge density and degree heterogeneity of Ddata . Reparameterization. From Section 5.2, the latent sociability weights satisfy wi = exp(ui ), so i.i.d.

2 ui = log wi ∈ R. We place a Gaussian prior on the log-weights, ui ∼ N (µLSP , σLSP ), which induces a log-normal distribution on wi . With c = 1, the edge probability becomes ui +uj

pij = 1 − e−e 15

(20)

Estimating σLSP . Since the true weights wi are unobserved, we construct a proxy from the degree sequence. For each node i in each training graph G, define the centered log-degree 1 X ũi = log(di + δ) − log(dk + δ) (21) |V | k∈V

where δ > 0 is a small smoothing constant. Centering removes the graph-level mean so that ũi captures relative degree heterogeneity within each graph. We then set
σLSP = std {ũi : i ∈ V (G), G ∈ Ddata } (22) where the standard deviation is taken over all nodes across all training graphs. Estimating µLSP . We calibrate µLSP by matching the expected edge probability under the LSP to the empirical edge density of the training data. The empirical edge density, averaged over training graphs, is X 1 2|EG | ρdata = (23) |Ddata | nG (nG − 1) G∈Ddata

Under the LSP with parameters (µLSP , σLSP ), the expected edge probability between any two nodes is  ui +uj  ρ(µLSP ) = E[pij ] = E 1 − e−e (24) Note that c enters Equation 24 only through the product c eui +uj , which in the sparse regime reduces 2 to c e2µLSP +σLSP (see Equation 27). Any value of c > 0 can therefore be absorbed into µLSP via the substitution µLSP ← µLSP + 12 log c, leaving the model unchanged. We fix c = 1 throughout without loss of generality, since µLSP is calibrated directly to match ρdata . i.i.d.

2 2 Since ui ,√ uj ∼ N (µLSP , σLSP ), the sum S = ui + uj ∼ N (2µLSP , 2σLSP ). Writing S = 2µLSP + 2 σLSP Z with Z ∼ N (0, 1), Equation 24 becomes h 2µ +√2 σ Z i LSP LSP ρ(µLSP ) = 1 − EZ∼N (0,1) e−e (25)

We solve ρ(µLSP ) = ρdata for µLSP using root-finding with the expectation in Equation 25 evaluated via K-node Gauss-Hermite quadrature, which replaces the integral by a deterministic weighted sum. Initialization of the root-finding. In the sparse regime where eui +uj is small, pij = 1−e−e eui +uj , so   2 ρdata ≈ E eui +uj = e2µLSP +σLSP

ui +uj

≈

(26)

Solving for µLSP gives the initialization 2 µ0LSP = 21 log ρdata − σLSP

(27)

where we have used c = 1. Since real-world graphs are typically sparse, this approximation is mild and provides a close starting point for the root-finder in practice. A.2

Shifted and scaled DDPM for latent sociability variables

The following derivation is stated for a single coordinate ui ; the result extends to the full vector u coordinatewise. Forward process.

The standard DDPM forward process [18] takes the form √ √ xt = ᾱt x0 + 1 − ᾱt ϵ, ϵ ∼ N (0, I).

(28)

In our setting the latent sociability variables should diffuse toward a Gaussian prior with mean µLSP 2 and variance σLSP , rather than toward N (0, I). To obtain this, we apply the DDPM construction to the centered and scaled variable 16

(u − µLSP )/σLSP : √ u0 − µLSP √ ut − µLSP = ᾱt + 1 − ᾱt ϵ, σLSP σLSP

ϵ ∼ N (0, I).

(29)

Multiplying through by σLSP and adding µLSP gives ut = µLSP +

√

√ ᾱt (u0 − µLSP ) + σLSP 1 − ᾱt ϵ,

ϵ ∼ N (0, I),

(30)

2 so that ut = u0 at t = 0 and ut → N (µLSP , σLSP ) as t → T .

Reverse process. Since Equation 29 is the standard DDPM forward process applied to ũt := (ut − µLSP )/σLSP , the reverse posterior in ũ-space is the standard DDPM Gaussian posterior [18]: q(ũt−1 | ũt , ũ0 ) = N (ũt−1 | µ̃t−1 , β̃t ) with mean

√ µ̃t−1 =

ᾱt−1 βt 0 ũ + 1 − ᾱt

√

αt (1 − ᾱt−1 ) t ũ 1 − ᾱt

(31) (32)

and variance β̃t =

βt (1 − ᾱt−1 ) . 1 − ᾱt

(33)

Substituting ũt = (ut − µLSP )/σLSP and ũ0 = (u0 − µLSP )/σLSP into Equation 32 and multiplying through by σLSP gives the posterior mean in u-space: µt−1 = µLSP +

√ √ αt (1 − ᾱt−1 ) t ᾱt−1 βt 0 (u − µLSP ) + (u − µLSP ) 1 − ᾱt 1 − ᾱt

(34)

2 The posterior variance scales by σLSP , giving

2 2 σ̃t2 = σLSP β̃t = σLSP

βt (1 − ᾱt−1 ) 1 − ᾱt

(35)

so that q(ut−1 | ut , u0 ) = N (ut−1 | µt−1 , σ̃t2 ).

(36)

The reverse sampling step is therefore s u

t−1

= µt−1 + σLSP

βt (1 − ᾱt−1 ) z, 1 − ᾱt

z ∼ N (0, 1),

(37)

which is the update used in Section 5.2, with u0 replaced by the network prediction û0,t at each timestep.

B

Proofs

B.1

Proof of Lemma 4.1

Proof of Lemma 4.1. Since the edges are discrete in {0, 1}, they are independent Bernoulli random variables. We note P(eij = 1) = pij its parameters. Denote by A = [eij ]ij the adjacency matrix of a drawn graph, we have P = [pij ]ij = E(A). By exchangeability, σAσ ⊤ has the same distribution as A for any permutation matrix σ, and therefore E[σAσ ⊤ ] = E[A] 17

(38)

which is

πP π ⊤ = P

(39)

The only matrices invariant under conjugation by all permutation matrices have constant off-diagonal entries. Since the diagonal is zero for simple graphs, it follows that Pij = p for all i ̸= j. Therefore the model is Erdős–Rényi. B.2

Proof of Thm. 4.2

GNNs. Denote by X(0) = X the input node features. The GNNs we are examining are all under the form   (k) (k) X(k) = σ X(k−1) θ0 + Sk (X(k−1) )X(k−1) θ1 + 1n b(k) ∈ Rn×dk where Sk (X(k−1) ) ∈ Rn×n are message-passing matrices that depends on the graph structure and (k) may depend on the layer k and X(k−1) for attention-based models, θi ∈ Rdk−1 ×dk are trainable weights, b(k) ∈ Rdk are trainable biases, and σ is an activation function that we assume to be 1-Lipschitz. All models can then be obtained by varying the choice of Sk (X), which we denote by S when it is fixed: • for GCN,

S = D̃−1/2 ÃD̃−1/2

where à = Id + A and D̃ is the corresponding degree matrix. • GIN uses sum-aggregation, which would correspond to S = A. However for random graphs this choice may diverge when n increases if not properly normalized. We choose the classical normalization for random graphs [25] by the expected density of the graph: for the ER model considered in the result, 1 S= A pn assuming that p is known for simplicity. Note that, for a fixed graph size n, this normalization can be absorbed by the weight θ1 , such that this is indeed equivalent to the vanilla GIN; • for GAT, we consider attention coefficients ck (x, x′ ) at layer k (typically exponentials of dot products), and normalized attention: ck (xi , xj ) ℓ∼i ck (xi , xℓ )

[Sk (X)]ij = P

We will assume that ck (·) ≥ cmin > 0, which is for instance the case for exponential attention coefficients on bounded features. Graph Transformers are essentially the same model, when stripped of various normalization layers (which we do not consider here for simplicity). After K layers, the node representations are used pairwise to obtain the edge prediction (K)

p̂ij = [φ(xi

(K)

, xj

)]ni,j=1 ∈ [0, 1]

where φ is a link function that we assume to be Lφ -Lipschitz in each component. Proof of Thm. 4.2. Recall that std(p̂) = X

q

1 n2

P

ij (p̂ij − p̄)

(p̂ij − p̄)2 = min p

ij

X

2 where p̄ =

P

ij p̂ij . First observe that

(pij − p)2

ij

and similarly, for X ∈ Rn×d , s std(X) = where x̄ = n1

P

1X 2 ∥xi − x̄∥ = min x n i

i xi . We therefore denote x̄

(k)

= n1 18

s

(k) i xi .

P

1X 2 ∥xi − x∥ n i

Hence, for any x, by Lipschitz property of φ and a triangular inequality s 1 X (K) (K) (φ(xi , xj ) − φ(x, x))2 std(p̂) ≤ n2 ij s s 1 X 1 X (K) (K) (K) (K) 2 ≤ (φ(x , x ) − φ(x , x)) + (φ(xi , x) − φ(x, x))2 i j i n2 ij n2 ij s 2 1 X (K) ≤ 2Lφ xi − x n i and by minimizing over x, we get std(p̂) ≤ 2Lφ std(X(K) ). √ Now, denote by Ek = std(X(k) ). Define ∥·∥F,n = ∥·∥F / n for short, where ∥·∥F is the Frobenius norm, and observe that std(X) = X − 1n x̄⊤ F,n . Moreover, observe that ∥SXθ∥F,n ≤ ∥S∥2 ∥X∥F,n ∥θ∥2 . We have the recursion equation: since minimizing over x is more general than over σ(x), and using the fact that σ is 1-Lipschitz and we can decompose minx ∥y + y ′ − x∥ = minx,x′ ∥y + y ′ − (x + x′ )∥ ≤ minx ∥y − x∥ + minx ∥y ′ − x∥, std(X(k) ) = min X(k) − 1n x⊤ ≤ min X(k) − 1n σ(x)⊤ x x F,n F,n   (k) (k) = min σ X(k−1) θ0 + Sk (X(k−1) )X(k−1) θ1 + 1n b(k) − σ(1n x⊤ ) x

≤ min

(k) (k) X(k−1) θ0 + Sk (X(k−1) )X(k−1) θ1 + 1n b(k) − 1n x⊤

≤ min

(k) X(k−1) θ0 − 1n x⊤

x

x

F,n

(k) ⊤ (k−1)

For the first term, by picking x = θ0 (k)

min X(k−1) θ0 − 1n x⊤ x

x̄

+ min Sk (X

(k−1)

x

F,n

(k) )X(k−1) θ1 − 1n x⊤

F,n

, we get (k)

F,n

F,n

≤ (X(k−1) − 1n (x̄(k−1) )⊤ )θ0

(k)

F,n

≤ Ek−1 θ0

2

We need to divide the second term, since the term 1n x⊤ cannot necessarily be written as ⊤ ⊤ Sk (X(k−1) )1n x′ for some x′ . So we introduce a term Sk (X(k−1) )1n x′ for some x′ :   ⊤ (k) (k) min Sk (X(k−1) )X(k−1) θ1 − 1n x⊤ ≤ Sk (X(k−1) ) X(k−1) θ1 − 1n x′ x

F,n

F,n

+ min Sk (X

(k−1)

x

)1n x

′⊤

− 1n x

⊤ F,n

(k) ⊤

Then, as previously, by picking x′ = x̃k = θ1 x̄(k−1) the first term in this equation can be bounded by   ⊤ (k) (k) Sk (X(k−1) ) X(k−1) θ1 − 1n x′ ≤ Sk (X(k−1) ) Ek−1 θ1 F,n

2

2

Note that we must then bound Sk (X(k−1) ) 2 , which is random and depend on the random graph and chosen GNN architecture. We denote the remaining term by ⊤ rn(k) = min Sk (X(k−1) )1n x̃⊤ k − 1n x x

which we will again bound for each example. 19

F,n

At the end of the day, we obtain   (k) (k) θ1 + Sk (X(k−1) ) Ek ≤ θ0 Ek−1 + rn(k) 2 2 2 | {z } uk

=

k X



k Y

 ℓ=1

 up  rn(ℓ) +

" k Y

p=ℓ+1

up E0

ℓ=1

{z

|

#

}

rn (δ)

For all example, we are going to show that uk = O(1) with probability 1 − δ if n is large enough, and bound rn (δ) wrt n and δ. Our general strategy will be to write ⊤ rn(k) = min Sk (X(k−1) )1n x̃⊤ k − 1n x x

F,n

≤ ∥x̃k ∥ min max c

i

X

sij − c

(40)

j∼i

for some constant c ∈ R (often 1 in our examples), and sij are the elements of Sk (X(k−1) ) for short. (k)

We remark that ∥x̃k ∥ ≤ θ1 again involves uk .

2

X(k−1) F,n and we can use Lemma B.2 to bound this term, which

Our main tool will be the following Lemma. Lemma B.1 (Lemma 3 in [24]). Consider an ER model with parameter p. Then, with probability at least 1 − δ, the degrees di satisfy s log(n/δ) di −1 ≲ (41) max i pn pn In particular, if n≳

log(n/δ) p

(42)

then with probability 1 − δ, for all i pn 3pn ≤ di ≤ 2 2 We now bound Sk (X(k−1) ) 2 and rn through Equation 40 for our examples. GAT. GAT is actually the simplest model to bound. Indeed, due to the normalization of the P (k) coefficients j∼i sij = 1 at all layers, we directly obtain rn = 0. For the bound on ∥Sk (X)∥2 , we remark that under the bound Equation 42 on n, for all i, j, k c (x , x ) cmax 2 P k i j ≤ c (x , x ) cmin pn i ℓ ℓ∼i k and thus for any layer and X s sX cmax X di cmax 2 ∥Sk (X)∥2 ≤ ∥Sk (X)∥F = sij ≲ ≲ 2 c (pn) pc min min ij i hence the result C = O(1/pK ). GIN. For GIN, we have S

(k)

= A/(pn).

Hence Equation 40 directly yields rn

≤

di ∥x̃k ∥ maxi pn − 1 , and the last term is smaller than ϵ when pn ≥ ϵ−2 log(n/δ) by Lemma B.1.

For the bound on ∥S∥2 , we invoke [29, Thm 5.2], such that for any r > 0, there is a constant Cr such that, if n ≥ Cr (1/δ)r , then A 1n×n 1 − ≲√ pn n 2 pn and

1n×n n

2

= 1 hence the result. 20

GCN. For GCN, if pn ≥ ϵ−2 log(n/δ) by Lemma B.1 |di − pn| = O(pnϵ) and thus since 1 √1 = √ + O( |a−b| ), a b3/2 b   ϵ 1 1 √ = √ +O √ pn pn di From this we get 1 X 1 p −1 sij − 1 = max √ i di j∼i dj j∼i   di ϵ ≤ max −1 +O √ i pn pn

X

max i

and we go back to the GIN case. For the bound on ∥S∥2 we have directly that ∥S∥2 ≤ 1, since its a symmetric normalized Laplacian (up to identity term).

Lemma B.2. (k)

≤

X

F,n

k X



k Y

 ℓ=1

 u p  vℓ +

" k Y

p=ℓ+1

# up

X(0)

,

vk = b(k)

(43)

F,n

ℓ=1

where (k)

uk = θ0

2

+ Sk (X(k−1) )

(k)

2

θ1

2

Proof. We write the recursion   (k) (k) X(k) = σ X(k−1) θ0 + Sk (X(k−1) )X(k−1) θ1 + 1n b(k) F,n F,n   (k) (k) (k−1) (k−1) X + b(k) ≤ θ0 + Sk (X ) θ1 F,n 2 2 2 | {z } {z } | vk

uk

=

k X

k Y

 ℓ=1

B.3



 up  vℓ +

p=ℓ+1

" k Y

# up

ℓ=1

X(0) F,n

Proof of Lemma 4.3

With the same reasoning as before, we have std(Ci /C) ≤ max |Ci /C − 1| i

we are going to bound the right hand side. The feature Ci can be expressed as a sum over subsets of r − 1 indices: X Ci = 1G{i}∪S ≃H

(44)

S⊂([1,n]\{i})r−1

where GS refers to the subgraph of G corresponding to subset of nodes S, and 1F ≃H = 1 if F and H are isomorphic and 0 otherwise. By exchangeability, it is obvious that C = E(Ci ) does not depend on the node i. For S of size r, since GS is also an E-R graph of size r, we have E1G{i}∪S ≃H = r!pmH (1 − p)r(r−1)/2−mH where mH is the number of edges in H, such that   n−1 C= r!pmH (1 − p)r(r−1)/2−mH = O(nr−1 ) (45) r−1 21

We are going to bound the deviation of Ci /C from its expectation of 1 using McDiarmid’s concentration inequality [33], which requires to bound the variation of Ci /C when one edge ekℓ flips, and sum the square of these variations over all indices k, ℓ. If ekℓ flips and k, ℓ are from i, then the terms affected are those where S contains both
different r−3 k, ℓ. There are n−3 ) such terms, such that the deviation of Ci /C is of order 1/n2 . r−3 = O(n 2 There are O(n ) such indices k, ℓ, such that the sum of the square of the deviation has a term O(n2 /n4 ) = O(1/n2 ).
If ekℓ flips and k = i, then the terms affected are those where S contains ℓ. There are n−2 r−2 = O(nr−2 ) such terms, such that the deviation of Ci /C is of order 1/n. There are O(n) such indices k, ℓ, such that the sum of the square of the deviation has a term O(n/n2 ) = O(1/n). Similarly when ℓ = i. Hence, by applying McDiarmid’s inequality, with probability 1 − δ, |Ci /C − 1| is bounded by p log(1/δ)/n. Using a union bound over i, we obtain the result. B.4

Proof of Lemma 5.1

A simple approximation of 1 − e−x yields pij = eui +uj + O((eui +uj )2 ) = eui +uj + O(e−4cn ) Then, E(di | u) =

X

pij =

j

X

eui +uj + O(ne−4cn )

j

  X  euj  eui + O(ne−4cn ) j

|

C

{z C

}

Variational motivation for the training objective

The following derivation provides variational motivation for the joint training objective in Equation 19. We follow the DiGress framework [51] and highlight the additional terms arising from the continuous latent component u. A key structural feature of our forward process is that the discrete transition matrices Q̄t,ij E are parameterized by the clean latent vector u0 rather than the noisy ut this is what gives the forward process its closed-form factorization (Section 5.2). As a consequence, the terminal distribution of the forward process conditioned on a training graph G0 has a discrete component that depends on u0 : 0 u0 i +uj

edges converge to Bernoulli(p0ij ) where p0ij = 1 − e−e . The sampling process (Algorithm 3), 2 on the other hand, draws uT ∼ N (µLSP , σLSP I) and then samples edges from Bernoulli(pTij ) where pTij depends on uT . These two terminals coincide only in expectation over u0 . We therefore do not claim that 19 is an exact ELBO for the generative model in Algorithm 3; rather, following the pragmatic stance of DiGress [51], we treat the objective as a well-motivated denoising loss whose variational structure we describe below. Let the joint state at time t be z t = (ut , Et ), with clean graph z 0 = (u0 , E0 ) and terminal state z T = (uT , ET ). Joint forward factorization. Because the continuous and discrete components are corrupted independently, the forward process factorizes as q(z t | z 0 ) = q(ut | u0 ) q(Et | E0 , u0 ) The continuous component follows the shifted-scaled Gaussian diffusion of Appendix A.2:
√ 2 q(ut | u0 ) = N ut µLSP + ᾱt (u0 − µLSP ), σLSP (1 − ᾱt )I 22

(46)

(47)

The discrete component follows from the pair-specific forward marginals of Equation 15: Y q(Et | E0 , u0 ) = q(etij | e0ij , u0 )

(48)

1≤i,j≤n

Evidence lower bound. Following [51], applying Jensen’s inequality with q(z 1:T | z 0 ) as the variational distribution gives the ELBO: T   X   log pθ (G) ≥ log p(nG ) − DKL q(z T | G) ∥ p(z T | nG ) − Lt (G) + Eq(z1 |G) log pθ (G | z 1 ) t=2

(49) where 
 Lt (G) = Eq(zt |G) DKL q(z t−1 | z t , z 0 ) ∥ pθ (z t−1 | z t )

(50)

With the u0 -keyed forward process, the training terminal factors as Y 2 p(z T | nG ) = N (µLSP , σLSP I) × Bernoulli(p0ij )

(51)

Terminal prior KL.

1≤i,j≤n 0

0

where p0ij = 1 − exp(−eui +uj ) depends on the clean graph. The prior KL decomposes as     2 DKL q(z T | G) ∥ p(z T | nG ) = DKL q(uT | u0 ) ∥ N (µLSP , σLSP I)   Y + DKL q(ET | E0 , u0 ) ∥ Bernoulli(p0ij ) (52) 1≤i,j≤n

Both terms vanish as ᾱT → 0 for the u0 -keyed forward process: the continuous component converges 2 to N (µLSP , σLSP I) and each row of Q̄T,ij converges to (p0ij )⊤ , so q(eTij | e0ij , u0 ) converges E 0 0 to Bernoulli(pij ) independently of eij . Note that this vanishing holds for the training terminal conditioned on u0 , not for the unconditional sampling terminal. Decomposition of the diffusion loss.

Because the forward posterior factorizes as

q(z t−1 | z t , z 0 ) = q(ut−1 | ut , u0 ) q(Et−1 | Et , E0 , u0 )

(53)

the per-step loss Lt (G) splits into independent continuous and discrete terms: Lt (G) = Lut (G) + LE t (G)

(54)

u where LE t (G) is identical in form to the DiGress per-step loss [51], and Lt (G) is the additional term: 
 Lut (G) = Eq(ut |u0 ) DKL q(ut−1 | ut , u0 ) ∥ pθ (ut−1 | z t ) (55)

Practical training objective. As in DDPM [18] and DiGress [51], we do not optimize the ELBO term-by-term. Instead, we optimize the simplified joint objective of Equation 19, replacing the per-step KL terms with cross-entropy and MSE losses respectively. The prior KL terms are dropped since they vanish for the u0 -keyed forward process by construction.

D

Additional experiments

D.1

DiGress on Tree dataset

In Table 3 we also present results on the Tree dataset [54] comparing DiGress with no aux features and our JointLSP with DiGress. We can observe that our proposed method outperforms DiGress on 3 out of 4 metrics. 23

Table 3: Results on Tree dataset

Method

Degree

Assortativity

PLE

CPL

DiGress JointLSP+DiGress

1073.41 ± 38.35 204.17 ± 26.83

33.89 ± 0.81 15.45 ± 1.58

242.14 ± 0.63 134.26 ± 2.03

222.38 ± 6.51 231.38 ± 1.19

Table 4: MMD ratios on CoraChameleon datasets for SparseDiff and JointLSP+SparseDiff under no-node features. Results are mean±std over 3 random seeds. Bold: better of SparseDiff vs. JointLSP+SparseDiff. Degree ↓

Clustering ↓

Triangles ↓

Assortativity ↓

PLE ↓

CPL ↓

SparseDiff (no features) n = 10 17.23±0.87 n = 20 49.10±2.08 n = 50 17.51±0.98 n = 100 30.43±0.15 n = 500 3.93±0.01

1.99±0.02 1.41±0.00 1.55±0.04 3.43±0.10 3.23±0.02

6.68±0.07 3.67±0.43 25.87±0.77 66.65±0.76 113.81±7.41

69.77±18.17 30.17±4.03 60.65±4.84 50.44±2.34 39.04±0.14

431.13±133.46 27.25±2.67 4.98±0.59 15.33±0.10 2.13±0.00

114.33±21.79 0.92±0.12 3.69±0.39 18.92±0.10 7.93±0.00

JointLSP+SparseDiff (no features) n = 10 14.18±0.64 2.00±0.01 n = 20 29.08±1.11 1.40±0.00 n = 50 13.29±0.32 1.49±0.01 n = 100 19.07±0.49 3.07±0.07 n = 500 3.82±0.01 2.99±0.02

6.43±0.14 2.19±0.23 15.11±0.34 36.00±0.84 35.41±4.21

11.38±7.16 15.31±0.95 36.18±1.16 24.88±1.18 28.89±0.27

37.70±14.13 15.75±1.29 6.29±0.19 11.14±0.23 2.20±0.00

37.19±3.19 0.54±0.12 5.76±0.16 16.24±0.21 8.37±0.00

D.2

Graph generation using JointLSP+SparseDiff

We augment SparseDiff [42] with our prior and joint diffusion process, referring to the result as JointLSP+SparseDiff. SparseDiff is particularly efficient at larger graph sizes, processing only randomly selected node pairs at each step, which is why we use it as the baseline for n = 500 and the Ego and Community datasets. The results on CoraChameleon across n ∈ {10, 20, 50, 100, 500} are reported in Table 4. JointLSP+SparseDiff consistently improves over SparseDiff on most metrics, with gains most pronounced on triangle count and assortativity. Notably, the improvement holds at n = 500, where the fixed-point pathology is most severe and the edge-independent prior has the greatest influence on generated statistics. The results on Ego and Community are reported in Table 5. These datasets remain challenging for both methods, as indicated by the uniformly large MMD ratios. This is likely due in part to the presence of self-loops in Ego and the lack of auxiliary spectral features needed to capture community structure. Nevertheless, JointLSP+SparseDiff improves over SparseDiff on all metrics except clustering on Ego and assortativity on Community. Taken together, these results support our main claim: the benefit of the proposed method is not that it universally optimizes generation quality, but that it addresses a fundamental limitation of edge-independent diffusion in the no-node feature setting.

Table 5: Comparison of graph generation with JointLSP+SparseDiff and SparseDiff on Ego and Community datasets. Results are mean±std over 3 random seeds. Degree ↓

Clustering ↓

Triangles ↓

Assortativity ↓

PLE ↓

CPL ↓

Ego SparseDiff JointLSP+SparseDiff

768.06±107.44 302.50±51.36

14.78±0.25 15.48±0.57

85.20±12.21 12.41±1.25

1715.86±53.10 785.72±141.52

1696.14±183.27 750.94±145.86

183.07±31.15 28.95±6.31

Community SparseDiff JointLSP+SparseDiff

91.57±24.34 38.70±14.18

6.86±0.63 5.08±0.44

8.12±0.96 1.54±0.44

0.99±1.27 9.02±6.79

226.18±49.36 105.09±39.66

21917.62±157.43 18251.36±550.46

24

D.3

DiGress with degree features

In the JointDiffusion+LSP proposal we derive the latent weights for each node by using the node degree as a proxy. This naturally leads to the question: is this similar to supplying node degree as auxiliary features to the denoiser, and whether DiGress [51] could also benefit from such augmentation? To answer this question, we conduct an experiment where we compute node degrees from the noisy graph at each denoising step and feed them as auxiliary features. More specifically, we compute the normalized degree d˜i = di /(n − 1) as a node-level feature, and the mean µd and standard deviation σd of d˜i across nodes as graph-level features, recomputed from the noisy adjacency At at every reverse step. The results are shown in Table 6. We can observe that JointLSP+DiGress outperforms DiGress+Degree features on metrics like degree, triangles, PLE and CPL. Thus, DiGress augmented with degree features does not recover the performance of JointLSP. This is consistent with Lemma 4.3: at high noise levels At is approximately E-R, so all d˜i ≈ p̄ and the features collapse to a near-constant, carrying no structural signal. The key distinction is that the LSP does not compute degree on the noisy graph, it supplies this information inherently by construction. The degree-informed heterogeneity information is baked into the terminal prior itself via u0 , making node-level variation available throughout the entire reverse trajectory rather than only when the graph is sufficiently clean. Table 6: DiGress + degree features on CoraChameleon-Node100. JointLSP+DiGress (k = 0, no features) is included for direct comparison. Bold: best result excluding the k = 17 ceiling. Degree ↓ Clustering ↓ Triangles ↓ Assortativity ↓ PLE ↓ CPL ↓

DiGress+Degree k=1 10.67±0.14

2.04±0.02

2.41±0.14

57.66±0.76

10.81±0.17

45.54±0.56

JointLSP+DiGress k=0 10.50±0.16

2.07±0.10

2.33±0.15

59.72±0.75

10.79±0.19

44.99±0.29

DiGress + 17 features k = 17 0.93±0.00

1.95±0.00

1.68±0.00

3.55±0.00

1.53±0.00

1.92±0.00

DiGress+degree does not preserve node heterogeneity. We compute the variance in node propensity scores as defined in Section 6.1, comparing JointLSP+DiGress, DiGress, and DiGress+Degree — where node degree is supplied as both a node-level and graph-level auxiliary feature — in Figure 3. JointLSP+DiGress maintains consistently high node heterogeneity throughout the reverse trajectory, starting from t = T where the LSP prior already induces diverse connection propensities. DiGress+Degree, by contrast, starts near zero at high noise levels and builds heterogeneity only as denoising progresses. This confirms that degree features are reactive: they can only provide structural signal once the graph is already partially denoised, whereas LSP provides it from initialization. The two mechanisms are therefore fundamentally different, even though both draw on degree information.

JointLSP+DiGress

0.0025

0.0025 0.0000

DiGress DiGress+Degree

Var(si)

JointLSP+DiGress

Var(si)

DiGress DiGress+Degree

0

0.0000

200 400 Timestep t

(a) Forward Noising Process.

400 200 Timestep t

0

(b) Reverse Denoising Process.

Figure 3: We compare the variance in node propensity scores for JointLSP+DiGress, DiGress+degree and DiGress. We can observe that our proposal yields node heterogeneity throughout the diffusion trajectory even at highly noisy states as opposed to DiGress with degree features which only improve the node heterogeneity when the graph is already denoised.

25

Random node features Many works such as [1, 45, 16] suggest incorporating random node features improve GNN expressivity, we test if this also helps improve generation quality in graph diffusion models. We verify this empirically on the CoraChameleon-Node100 dataset and compare DiGress with no aux features, DiGress+RND which denotes the random node features and JointLSP+Digress. The setup is as follows: The diffused node state is unchanged (X = 1), and at each denoising step we concatenate random features r ∈ Rn×d , drawn i.i.d. from N (0, I) with dim=8 to the node input. The results are presented in Table 7, adding random node features does not help with generation because firstly RND leaves the corruption process and the terminal distribution unchanged: Lemma 4.1 still applies and the terminal distribution is still E-R, and sampling still begins from a graph with no node-level structure. RND alters only the denoiser input, not where the reverse trajectory starts. Second, the heterogeneity it supplies is uncalibrated, as the features are drawn independently of the data, whereas LSP is calibrated from the training data. Table 7: Results on CoraChameleon-Node100 dataset comparing DiGress with random node features Method

Degree

Clustering

Triangles

Assortativity

PLE

CPL

DiGress DiGress+RND JointLSP+DiGress

4.53±0.1 5.48±0.13 10.50±0.16

11.33±0.27 12.50±1.18 2.07±0.10

14.82±0.12 10.13±0.04 2.33±0.15

101.95±2.13 127.06±6.20 59.72±0.75

4.64±0.17 4.14±0.41 10.79±0.19

39.68±1.14 24.01±1.57 44.99±0.29

D.4

LSP improves generation quality throughout diffusion trajectory

To further demonstrate the effectiveness of the proposed JointLSP framework, we track the MMD ratio (r) presented in Section 6.2 at various timesteps t ∈ {500, 50, 0} for both JointLSP+DiGress and DiGress on CoraChameleon-Node100 dataset. At each timestep t, we use the network’s predicted clean edge probabilities p̂E,t ij to construct a graph and evaluate MMD against the test set. The results are shown in Figure 4. JointLSP+DiGress consistently achieves lower MMD ratios than DiGress at all timesteps across all three structural statistics except Degree, where we surmise the LSP over-corrects the degree when inducing node heterogeneity. At t = 500, where the input is close to the terminal prior, DiGress produces graphs with very high MMD as the ER prior provides no structural information making it difficult for the denoiser. JointLSP+DiGress already achieves substantially lower MMD at this stage, confirming that the LSP along with the joint diffusion process provides a more informative starting point. As t → 0 both models improve, but JointLSP+DiGress maintains a consistent advantage, particularly on assortativity and triangle count. This supports our main claim that our proposal indeed improves the diffusion pipeline and does not result in the fixed-point pathology we have pointed out.

MMD² ratio r

JointLSP+DiGress

DiGress

100

10

10

50

5

5

0 T=500 t=50 t=0 Assortativity

0 T=500 t=50 t=0 Clustering

0 T=500 t=50 t=0 Degree

15 10 5 0 T=500 t=50 t=0 Triangle

Figure 4: We track the MMD ratio across various diffusion timesteps for JointLSP+DiGress and DiGress. Our proposed framework consistently generates good quality graphs even at intermediate steps. D.5

LSP induces node heterogeneity

To verify that the proposed prior preserves node distinguishability, we simulate graphs (m = 100 graphs) with increasing node sizes n = {10, 20, 50, 100, 500, 1000} under three random graph models: 1. Dense Bernoulli baseline: Aij ∼ Bern(ρdense ), where ρdense = 0.1. 26

k̄ 2. Sparse mean-field Bernoulli: Aij ∼ Bern(ρsparse ), where ρsparse = n−1 and k̄ = 5, and

3. Latent Sociability Prior: Aij ∼ Bern(Pij ), where Pij = 1 − e(−ce

ui +uj )

. (m)

To quantify node-level heterogeneity, we measure the within-graph degree variance Vari (di (m) within-graph degree mean Ei [di ], and define the dispersion index (m)

φ=

Vari [di

]

(m) Ei [di ]

,

) and

(56)

which we then average across all sampled graphs. This statistic captures how much node degrees vary within a graph. The results are shown in Figure 5. As n → 1000, both the dense and sparse Bernoulli baselines yield φ ≈ 1, indicating that edge-independent models remain tightly constrained by their mean degree and therefore, by design, cannot induce meaningful node heterogeneity. In contrast, LSP consistently yields φ > 1, showing that it preserves non-trivial degree variation as graph size increases. This confirms that, unlike ER-type models, LSP does not collapse to a homogeneous fixed-point. Dense Bernoulli

Sparse Mean-Field

Latent Sociability Prior

Node size

00 10

0 50

10

0

50

20

10

Overdispersion Index

1.4 1.2 1.0 0.8 0.6 0.4

Figure 5: Dispersion index φ as a function of node size under three prior models. Unlike edgeindependent Bernoulli baselines, LSP preserves non-trivial node heterogeneity as graph size increases.

D.6

LSP can generate higher triangle and cycle counts

We conduct a second experiment to study how higher-order graph statistics scale with increasing graph size under a fixed mean-degree constraint. This distinction is important, since large triangle or cycle counts can be obtained trivially by generating dense graphs. Specifically, for node sizes n = {10, 20, 50, 100, 500, 1000}, we simulate 100 graphs from each random graph model while fixing the mean degree to the same target value. For each graph, we measure the number of triangles, 4-cycles, and 4-cliques, and study how these quantities scale as n increases. The results, shown in Figure 6, indicate that LSP consistently produces substantially larger higher-order structure counts than a sparse mean-field Bernoulli prior under the same mean-degree budget. This shows that the gain is not a consequence of simply generating denser graphs, but of inducing non-trivial dependencies that support richer local structure. D.7

Structural features are uninformative for E-R graphs

In Figure 7 we empirically validate Lemma 4.3. We simulate 100 graphs of node sizes n ∈ {100, 500, 1000, 2000, 5000} under two priors at matched edge density ρ = 0.1. For E-R, each edge is drawn independently with probability p = 0.1. For the LSP, we fix σLSP = 1.0 and solve for µLSP such that E[pij ] = 0.1 using the calibration procedure of Algorithm 1. Graphs are then 2 sampled directly from the prior by drawing ui ∼ N (µLSP , σLSP ) and connecting each pair (i, j) 27

LSP

200 100 10

20

50 100 Node size

500 1000

(a) Triangle Count.

2000 1000 0

Sparse Mean-Field

LSP

3000

Mean 4-clique count

300

Sparse Mean-Field Mean 4-cycle count

Mean triangle count

Sparse Mean-Field

10

20

50 100 Node size

LSP

60 40 20

500 1000

(b) 4-Cycle Count.

0

10

20

50 100 Node size

500 1000

(c) 4-Clique Count.

Figure 6: We simulate graphs using the sparse Bernoulli and our proposed LSP and compute how many triangles, 4-cycles and 4-cliques can the prior generate at a fixed mean-degree resolution while the number of nodes is increased. ui +uj

with probability pij = 1 − e−e . Note that no diffusion process is involved; we sample from the terminal prior directly to isolate the effect of the prior on structural feature statistics. For each graph, we compute the per-node triangle count Ci and measure std(Ci /C̄) where C̄ = meani (Ci ). As n grows, this quantity vanishes for E-R graphs, confirming that structural features become increasingly uniform across nodes and therefore uninformative to a denoiser. The LSP maintains a stable, non-trivial spread across all graph sizes.

ER

LSP

std(Ci/C)

1.5 1.0 0.5 0.0

100

500

1000

Graph size n

2000

5000

Figure 7: We empirically validate the hypothesis that in the large graph limit the structural features derived from an E-R are uninformative for the denoiser.

E

Dataset generation

CoraChameleon datasets. Existing datasets like Community and Planar graphs which are usually used in evaluation of the graph diffusion models do not accurately reflect the characteristics of real-world graphs. Hence, we generate 5 new datasets by sampling from two real-world datasets Cora [32] and Chameleon [44]. We apply 3 sampling strategies to the source graphs: random walk based where a biased random walk starts from a random node. The walk continues until ∼ 1.5x the target node size has been visited, then the BFS-largest connected component is taken. After half of the allowed attempts, the starting node is biased toward high-degree nodes to improve connectivity. Forest-fire [30] which starting from a seed node, each active node stochastically ignites a geometrically-distributed number of its un-burned neighbors with forward probability pforward = 0.7 and backward probability pbackward = 0.3. And a dense-core sampling strategy that randomly picks top-10% of highest degree nodes in the source graph as candidate neighbours and greedily scores how many edges are already in the currently selected set and picks the highest-scoring candidate and adds it. A density check is done once target size nodes are collected, rejects the subgraph if it isn’t connected or if its average degree is below minimum average degree (default 4.0). We use a ratio of 40% Random walk, 40% Forest-fire and 20% Dense core to generate our synthetic graphs. Additionally 100 graphs are generated which are 28

divided into 60/40 as test and validation sets respectively. The hyperparameters are tuned on the validation set. Ego network Similar to SparseDiff [42] we also evaluate our models on the Ego dataset [54] which is a 3-hop ego network extracted from the Citeseer dataset [46]. Community dataset We also evaluate on the community dataset [54] which consists of 2 communities generated by an E-R model with n = |V |/2 nodes and p = 0.3. The inter-community edges are added with probability 0.05|V | with uniform probability. In Table 8 we provide the data statistics of the graphs used for the generation task. Table 8: Statistics for the datasets used in the graph generation experiments

Dataset

#Graphs

#Nodes

#Edges

CoraChameleon-Node10 CoraChameleon-Node20 CoraChameleon-Node50 CoraChameleon-Node100 CoraChameleon-Node500 EGO Community

3000 3000 3000 3000 1400 757 510

10 20 50 100 500 [50,399] [60,160]

[14,45] [27,120] [71,300] [172,600] [1282,4630] [57,1071] [231,1956]

(a) CoraChameleon-Node100

(b) CoraChameleon-Node500

(c) Community dataset

Figure 8: Sample graphs from the training set.

(a) Sample CoraChameleon-Node100 graphs gen- (b) Sample CoraChameleon-Node100 graphs generated using JointLSP+DiGress. erated using DiGress.

Figure 9: We visualize the generated graphs from both JointLSP+DiGress (a) and DiGress (b) on CoraChameleon-Node100 dataset. Clearly, we can observe that without node features the generation quality is impacted, but DiGress generates graphs which are dense and hairball-like even generating isolated nodes. E.1

Training details

All experiments were implemented in PyTorch and PyTorch Geometric [13]. Our model architecture follows DiGress and SparseDiff, using a Graph Transformer [11] as the denoising network. All 29

experiments were run on a single A40 GPU. Hyperparameters are provided in Table 9. For each configuration, we train a single model and run inference three times with different random seeds; reported mean and standard deviation are computed over these three inference runs. This evaluation setup is consistent with the protocol followed in existing graph diffusion papers such as DeFoG [41] which reports the mean and std deviation averaged over 5 sampling runs and not 5 independent runs as it is computationally infeasible. For instance, training DiGress [51] on Planar graphs requires nearly 50K epochs with a 10 layer transformer and DeFoG is trained for 100000 epochs with a 10 layer transformer. Additionally, computing the auxiliary features such as spectral adds further overhead. In our setup, we report the mmd ratios averaged over 3 sampling runs. Table 9: Hyperparameters used for the graph generation task. Dataset

#Layers

CoraChameleon-Node10 CoraChameleon-Node20 CoraChameleon-Node50 CoraChameleon-Node100

6 6 6 6

Weight Decay

LR

#Training Epochs

Diffusion Steps

5000 5000 5000 5000

500 500 500 500

100 100 100 100 100 2000 1000

500 500 500 500 500 500 500

JointLSP+DiGress 0.0001 0.0001 0.0001 0.0001

0.00012 0.00012 0.00012 0.00012

JointLSP+SparseDiff CoraChameleon-Node10 CoraChameleon-Node20 CoraChameleon-Node50 CoraChameleon-Node100 CoraChameleon-Node500 EGO Community

6 6 6 6 4 6 6

0.0001 0.0001 0.0001 0.0001 0.0001 0.0001 0.0001

0.00001 0.00001 0.00001 0.00001 0.00001 0.000012 0.000012

Runtime analysis LSP does not change the complexity of the underlying model. The denoiser forward pass is O(Kn2 d2 ) for both DiGress and JointLSP+DiGress; the operations LSP adds is 0 u0 i +uj

computing p0ij = 1 − e−e across node pairs and the DDPM update on the n latent variables 2 which are O(n ) and O(n) respectively, smaller than the base cost by a factor O(Kd2 ). Prior calibration (Algorithm 1) is a one time pre-processing step, not per-iteration. Table 10: Runtime analysis Metric

DiGress

JointLSP+DiGress

Model parameters Training step (in ms) Peak GPU Memory (GiB) Sampling (graph/sec)

8,888,579 493.3±4.7 13.40 9.50

8,888,579 489.8±5.0 13.39 9.33

List of auxiliary features In 11 the details of node level and graph level features used as auxiliary features for DiGress is provided.

F

Broader impact

Graph diffusion models have potential applications across a range of domains, including drug discovery, protein interaction networks, and social network analysis, where the ability to generate realistic graph structures could accelerate scientific discovery or inform network design. Like all generative models, these methods are not free from certain risks, for instance, realistic graph generation could in principle be misused to generate fake synthetic social network structures or in the long term, to design molecules with adversarial properties. However, we note that these risks are not specific to our contribution. This work addresses a theoretical limitation in existing discrete graph diffusion pipelines and proposes a prior and a joint diffusion framework that improves graph generation in the no-node-feature setting.

30

Table 11: Auxiliary features used in DiGress. Feature

Description

k3_node k4_node k5_node k3_graph k4_graph k5_graph k6_graph n_comp nonLCC eigvec1 eigvec2 eigval1 eigval2 eigval3 eigval4 eigval5 n/max_n

Node triangle count Node 4-cycle count Node 5-cycle count Graph triangle count Graph 4-cycle count Graph 5-cycle count Graph 6-cycle count Number of connected components Indicator for nodes outside the largest connected component First nontrivial Laplacian eigenvector Second nontrivial Laplacian eigenvector First nonzero Laplacian eigenvalue Second nonzero Laplacian eigenvalue Third nonzero Laplacian eigenvalue Fourth nonzero Laplacian eigenvalue Fifth nonzero Laplacian eigenvalue Normalized graph size (n/nmax )

31

Related documents

• When Edge Independence Fails: Joint Graph Diffusion with Latent Sociability Priors#1298261
• UltraDiff: Transferring High-Fidelity Priors to Compressed Latent Spaces for High-Resolution Image Generation#1356538
• Popularity Regression-Based Latent Space Model for Large-Scale Sparse Network Analysis#1141327
• Your Discrete Graph Diffusion Model is Secretly Memorizing#1298282
• Your Discrete Graph Diffusion Model is Secretly Memorizing#1291808