Paper deep dive

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

Adarsh Jamadandi, Nicolas Keriven, Aline Roumy

Year: 2026Venue: arXiv preprintArea: cs.LGType: PreprintEmbeddings: 119

Intelligence

Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 91%

Last extracted: 10/13/2026, 3:03:17 AM

Summary

The paper identifies a fundamental limitation in discrete graph diffusion models where the terminal prior is necessarily an Erdős–Rényi (E-R) random graph due to edge independence and exchangeability requirements. This leads to a fixed-point pathology in the large graph limit, where GNN denoisers output homogeneous graphs lacking node heterogeneity. The authors propose the Latent Sociability Prior (LSP), a joint diffusion framework that co-evolves latent node sociability variables with graph structure to preserve heterogeneity without complex encoders.

Entities (7)

Erdős–Rényi · graph-model · 99%Latent Sociability Prior · method · 98%Discrete Graph Diffusion · method · 95%GNN · model-architecture · 90%DiGress · baseline-model · 85%GAT · model-architecture · 85%GCN · model-architecture · 85%

Relation Signals (5)

Latent Sociability Prior → preserves → Node Heterogeneity

confidence 95% · its sole role is to guide edge updates and preserve node heterogeneity throughout the trajectory.

Discrete Graph Diffusion → producesterminalprior → Erdős–Rényi

confidence 95% · Combined with the exchangeability requirement on the output distribution, the terminal prior is necessarily an Erdős–Rényi (E-R) random graph.

Latent Sociability Prior → solves → Fixed-Point Pathology

confidence 95% · We instead address the root cause by introducing the Latent Sociability Prior (LSP)... removing edge independence while preserving exchangeability.

Erdős–Rényi → causes → Fixed-Point Pathology

confidence 90% · in the large graph limit, any GNN denoiser applied to an E-R graph approximately outputs an E-R graph, making effective denoising difficult.

DiGress → uses → Graph Transformer

confidence 85% · close to the graph transformer [11] used in DiGress [51]

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

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 join} 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.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

115,723 characters extracted from source content.

Expand or collapse full text

When Edge Independence Fails: Joint Graph Diffusion with Latent Sociability Priors Adarsh Jamadandi Email: adarsh.jamadandi@irisa.fr Nicolas Keriven Email: nicolas.keriven@cnrs.fr Aline Roumy Email: aline.roumy@inria.fr CNRS IRISA Rennes France INRIA Rennes France 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. 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 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. [7, 6] 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 data=G1,…,GMD_data=\G_1,…,G_M\ be a dataset of graphs drawn from an unknown distribution pdatap_data. For a graph G=(X,E)G=(X,E) with node features X and edges E, the goal is to learn a distribution pθ(G)p_θ(G) from which new graphs can be sampled. Node features and edges are represented via one-hot encodings, giving tensors ∈ℝn×dX ^n× d and ∈ℝn×n×bE ^n× n× b, where d is the number of node feature types and b the number of edge categories. Here we simply consider b=2b=2 edge categories, with eij∈ℬ=0,1e_ij =\0,1\ denoting the scalar edge state (absence or presence) between nodes i and j, and ij∈ℝbe_ij ^b its one-hot encoding, organized into the edge tensor ∈ℝn×n×bE ^n× 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,…,GTG^0,G^1,…,G^T, where G0G^0 is a clean training graph and GTG^T is drawn from the terminal prior πT _T. We denote by eij0∈ℬe_ij^0 the clean edge state between nodes i and j in G0G^0, and by ij0∈ℝbe_ij^0 ^b its one-hot encoding. The probability of a noisy sequence (G1,…,GT)(G^1,…,G^T) given G0G^0 factorizes as q(G1:T∣G0)=∏t=1Tq(Gt∣Gt−1)q(G^1:T G^0)= _t=1^Tq(G^t G^t-1) (1) The transition matrix Et∈ℝb×bQ_E^t ^b× b governs one-step edge corruption, with entries [Et]rs=q⁡(et=s∣et−1=r)[Q_E^t]_rs=q(e^t=s e^t-1=r), and ¯Et=E1⋯Et Q_E^t=Q_E^1·sQ_E^t is the cumulative transition matrix. Since transitions act independently on each edge, the per-edge forward marginal is the 1×b1× b probability vector q⁡(eijt∣eij0)=ij0¯Etq(e_ij^t e_ij^0)=e_ij^0\, Q_E^t. The joint forward marginal over all edges is q⁡(t∣0)=∏1≤i,j≤nq⁡(eijt∣eij0)q(E^t ^0)= _1≤ i,j≤ nq(e_ij^t e_ij^0) (2) 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=(,t)G^t=(1,E^t) and timestep t as input, and outputs for each node pair (i,j)(i,j) a probability vector ^ijE,t∈ℝb p_ij^E,t ^b over edge types. It is optimized via cross-entropy against the clean edge states: ℒCE(^E,t,G0)=∑1≤i,j≤nCE⁡(eij0,^ijE,t)L_CE( p^E,t,G^0)= _1≤ i,j≤ nCE\! (e^0_ij, p_ij^E,t ) (3) New graphs are sampled by running the reverse process from GT∼πTG^T _T. Since node features remain fixed, the reverse distribution factorizes over edges: pθ(t−1∣Gt)=∏1≤i,j≤npθ(eijt−1∣Gt)p_θ(E^t-1 G^t)= _1≤ i,j≤ np_θ(e_ij^t-1 G^t) (4) Each factor is computed by marginalizing over the predicted clean edge distribution: pθ(eijt−1∣Gt)=∑r∈ℬq⁡(eijt−1∣eijt,eij0=r)^ijE,t(r)p_θ(e_ij^t-1 G^t)= _r q\! (e_ij^t-1 e_ij^t,e^0_ij=r ) p_ij^E,t(r) (5) where q⁡(eijt−1∣eijt,eij=r)q(e_ij^t-1 e_ij^t,e_ij=r) is the forward posterior, available in closed form in [51] and ^ijE,t(r) p_ij^E,t(r) denotes the network’s estimate of the probability that the clean edge takes value r given the noisy graph GtG^t. As we will see later, by Theorem 4.2, when GtG^t is an E-R random graph, ^ijE,t p_ij^E,t is approximately constant across all pairs (i,j)(i,j), so pθ(eijt−1∣Gt)p_θ(e_ij^t-1 G^t) is the same for all pairs and t−1E^t-1 again follows an E-R distribution. Transition matrices are chosen as in [51] to preserve the empirical marginal distribution of edge types E∈ℝbm_E ^b throughout diffusion through Et=αtI+βtbE⊤Q_E^t= _tI+ _t1_bm_E where, βt=1−αt _t=1- _t. With probability αt _t the edge state is preserved, and with probability βt _t it is resampled from Em_E. As t→Tt→ T, every edge is driven independently towards Em_E, so the terminal prior πT:=q⁡(GT) _T:=q(G^T) 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σ· G the relabelling of a graph G by a permutation σ, our entire generation process needs to satisfy pθ(σ⋅G0)=pθ(G0)p_θ(σ· G^0)=p_θ(G^0) for all σ,G0σ,G^0. Fortunately, if a) the prior distribution πT=q⁡(GT) _T=q(G^T) is exchangeable (which is naturally the case of E-R random graphs), and b) the denoiser ϕθ _θ is permutation equivariant11 1 that is, ϕθ(σ⋅G)=σ⋅ϕθ(G) _θ(σ· G)=σ· _θ(G), then it is easy to see that the final distribution is exchangeable: we have pθ(σ⋅Gt−1∣σ⋅Gt)=pθ(Gt−1∣Gt)p_θ(σ· G^t-1 σ· G^t)=p_θ(G^t-1 G^t) by equivariance, and q⁡(σ⋅GT)=q⁡(GT)q(σ· G^T)=q(G^T) 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 _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 _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 =1X=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 φ : p^ij=φ⁡(i(K),j(K))∈[0,1] p_ij= (x_i^(K),x_j^(K))∈[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 22 2 Technically, in vanilla graph transformers the edge probabilities would also be modulated by the input graph p^ij=φ⁡(i(K),j(K),eij) p_ij= (x_i^(K),x_j^(K),e_ij), in which case our result become: ^E 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.. Denote by std(p^)=1n2∑ij|p^ij−1n2∑ijp^ij|2,std()=1n∑i‖i−1n∑i‖2 std( p)= 1n^2 _ij | p_ij- 1n^2 _ij p_ij |^2, 8.8543pt std(X)= 1n _i _i- 1n _iX_i ^2 (6) the standard deviation of the edge probabilities and input node features, respectively, such that E-R random graphs have exactly std(p^)=0 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δ,ε>0, if n is large enough, then with probability at least 1−δ1-δ, std(p^)≲Cstd()+ϵ std( p) C std(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)KC=(1/p)^K, and n is such that pn≳log⁡(n/δ)pn (n/δ) (7) In particular, one can choose ϵ=0ε=0 in this case. • if the GNN is a GCN [28], then C=O⁡(1)C=O(1), and n is such that pn≳ϵ−2log⁡(n/δ)pn ε^-2 (n/δ) (8) • if the GNN is GIN [53], for all r>0r>0 there exists CrC_r such that the result is valid with C=O⁡(1)C=O(1), and n such that pn≳ϵ−2log⁡(n/δ)andn≥Crδ−rpn ε^-2 (n/δ) n≥ C_rδ^-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()=0 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)p=O(1) for simplicity. Consider a template graph H of size r, and denote by CiC_i the number of subgraphs equal to H containing node i. Then C=⁡(Ci)C=E(C_i) does not depend on i, and with probability at least 1−δ1-δ, std(Ci/C)≲log⁡(n/δ)/n std(C_i/C) (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 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. Figure 1: Joint diffusion over edges and latent sociability. Top: the latent sociability utu^t and edge states tE^t are jointly noised, with edge transitions conditioned on u0u^0, until reaching uT∼⁡(μLSP,σLSP2)u^T ( _LSP, _LSP^2) and T∼πTE^T _T. Bottom: during denoising, the graph transformer ϕθ _θ predicts the less noisy latent u^t−1 u^t-1, which conditions the reverse edge transition pθ(t−1∣t,u^t−1)p_θ(E^t-1 ^t, u^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. Definition 1 (Latent Sociability Distribution [39]). Let w1,…,wn∼i.i.d.pWw_1,…,w_n i.i.d. p_W be latent sociability weights, where pWp_W is a distribution on ℝ>0R_>0 to be specified in Section 5.2. The latent sociability distribution defines a random undirected graph G with conditionally independent Bernoulli edges as ℙ⁡(eij=1∣wi,wj)=1−e−wiwj,i<j,P(e_ij=1 w_i,w_j)=1-e^-w_iw_j, 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,…,wnw_1,…,w_n but marginally dependent, while global exchangeability is preserved. Intuitively, a node with high weights wiw_i will tend to be more “connected”: all the pijp_ij will be higher. Hence, a distribution pWp_W 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 wiw_i 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)w_i= (u_i) with ui∈ℝu_i unconstrained. Under a Gaussian prior on uiu_i, the induced prior on wiw_i is log-normal. After this reparameterization, the edge probability in Equation 10 becomes pij=1−e−eui+ujp_ij=1-e^-e^u_i+u_j (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 G0G^0, one must first construct the corresponding clean latent vector 0u^0. While usual latent approaches require training an encoder, in the LSP 0u^0 admits a simple, approximate closed-form expression. Lemma 5.1. Consider an LSP random graph. Assuming a sparse regime where ui=O⁡(−cn)u_i=O(-c_n) for some constant cn≫0c_n 0, we have for all i ⁡(di∣)=Ceui+O⁡(ne−4cn)E(d_i )=Ce^u_i+O(ne^-4c_n) for some constant C=O⁡(ne−cn)C=O(ne^-c_n), where did_i denotes the degree of node i. Following this, we set ui0≈log⁡(di+δ)+μu_i^0≈ (d_i+δ)+μ where δ>0δ>0 is a small smoothing constant. To better capture relative degree heterogeneity across different training graphs, we remove the graph-level mean and obtain ui0=μLSP+log⁡(di+δ)−1|V|∑k∈Vlog⁡(dk+δ)u_i^0= _LSP+ (d_i+δ)- 1|V| _k∈ V (d_k+δ) (12) where μLSP _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)( _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 t=μLSP+α¯t(0−μLSP)+σLSP1−α¯tϵ,ϵ∼⁡(0,I)u^t= _LSP+ α_t\,(u^0- _LSP)+ _LSP 1- α_t\,ε, ε (0,I) (13) so that t=0u^t=u^0 at t=0t=0 and tu^t converges in distribution to ⁡(μLSP,σLSP2I)N( _LSP, _LSP^2I) as t→Tt→ 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 Em_E with a pair-specific stationary ij0=[ 1−pij0,pij0]∈ℝbp_ij^0=[\,1-p_ij^0,\;p_ij^0\,] ^b, where pij0=1−e−eui0+uj0p_ij^0=1-e^-e^u_i^0+u_j^0. This gives the pair-specific transition matrices Et,ij=αtI+βtb(ij0)⊤,¯Et,ij=α¯tI+(1−α¯t)b(ij0)⊤Q_E^t,ij= _tI+ _t1_b(p_ij^0) , Q_E^t,ij= α_tI+(1- α_t)1_b(p_ij^0) (14) with entries [Et,ij]rs=q⁡(eijt=s∣eijt−1=r,0)[Q_E^t,ij]_rs=q(e_ij^t=s e_ij^t-1=r,u^0). Since 0u^0 is a deterministic function of G0G^0, all matrices are fixed given (0,0)(E^0,u^0), and the joint forward marginal factors over independent edges: q⁡(t∣0,0)=∏1≤i,j≤nq⁡(eijt∣eij0,0),q⁡(eijt∣eij0,0)=eij0¯Et,ijq(E^t ^0,u^0)= _1≤ i,j≤ nq(e_ij^t e_ij^0,u^0), q(e_ij^t e_ij^0,u^0)=e_ij^0\, Q_E^t,ij (15) 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 0u^0 rather than tu^t is what makes this possible: if the transitions depended on tu^t, the matrices would be random variables and the product structure in Equation 15 would no longer hold. Reverse process. Starting from (t,t)(u^t,E^t), the network ϕθ _θ predicts the clean latent vector ^0,t=ϕθ(t,t,t) u^0,t= _θ(u^t,E^t,t) and updates both components separately. The reverse kernel factorizes as pθ(t−1,t−1∣t,t)=pθ(t−1∣t,t)pθ(t−1∣^0,t,t)p_θ(u^t-1,E^t-1 ^t,E^t)=p_θ(u^t-1 ^t,E^t)\,p_θ(E^t-1 u^0,t,E^t) (16) For the continuous component, the reverse update follows the DDPM posterior in the shifted-and-scaled parameterization derived in Appendix A.2. For the discrete component, ^0,t u^0,t determines pair-specific reverse transition matrices ^Et,ij=αtI+βtb(^ij0,t)⊤,¯^Et,ij=α¯tI+(1−α¯t)b(^ij0,t)⊤ Q_E^t,ij= _tI+ _t1_b( p_ij^0,t) , Q_E^t,ij= α_tI+(1- α_t)1_b( p_ij^0,t) (17) where p^ij0,t=1−e−eu^i0,t+u^j0,t p_ij^0,t=1-e^-e u_i^0,t+ u_j^0,t and ^ij0,t=[ 1−p^ij0,t,p^ij0,t] p_ij^0,t=[\,1- p_ij^0,t,\; p_ij^0,t\,]. The reverse edge distribution factorizes as in Equation 4, with each factor given by pθ(eijt−1∣eijt,^0,t)=∑r∈ℬq⁡(eijt−1∣eijt,eij=r;^0,t)^ijE,t(r)p_θ(e_ij^t-1 e_ij^t, u^0,t)= _r\,∈\,Bq(e_ij^t-1 e_ij^t,e_ij=r;\, u^0,t)\, p_ij^E,t(r) (18) where the posterior is computed from the pair-specific matrices in Equation 17. 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: ℒ=∑1≤i,j≤nCE⁡(eij,^ijE,t)+λu(1n∑i=1n‖u^i0,t−ui0‖22)L= _1≤ i,j≤ nCE(e_ij,\, p_ij^E,t)+ _u ( 1n _i=1^n\| u_i^0,t-u_i^0\|_2^2 ) (19) where λu∈ℝ+ _u _+ 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 real-world graphs; details are given in Appendix E. We generate 30003000 graphs for n∈10,20,50,100n∈\10,20,50,100\ and 14001400 for n=500n=500, across node sizes n∈10,20,50,100,500n∈\10,20,50,100,500\. We also conduct experiments on the commonly used benchmarks Ego and Community datasets [54], with a 60/20/2060/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 itS_i^t using the predicted clean edge probabilities at diffusion step t. For each node i, we compute it=1n−1∑j≠i^ijE,tS^t_i= 1n-1 _j≠ i p_ij^E,t, where ^ijE,t p_ij^E,t denotes the model’s predicted clean edge probability between nodes i and j at time t. Intuitively, itS_i^t measures the average connectivity propensity of node i at a given noise level. To quantify how much this varies across nodes, we compute Vt=Vari=1,…,n(it)V^t=Var_i=1,…,n(S_i^t). We evaluate this metric at different diffusion steps t∈500,50,0t∈\500,50,0\, where t=500t=500 corresponds to the maximally noisy state, over training graphs in a batch. For each graph, VtV^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→Tt→ 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. (a) Forward Noising Process. (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. 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 [6] and [9]. For each statistic, we report the MMD ratio r=MMD(generated,test)2MMD(train,test)2r= MMD(generated,\,test)^2MMD(train,\,test)^2 following [51]. Lower is better, with r=1r=1 as the 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=0k=0), and finally Digress with the full set of structural and spectral features (k=17k=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=10k=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=10k=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,100n∈\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-node-feature 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=100n=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,500n∈\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 0u^0. Table 1: Feature subset ablation for DiGress on CoraChameleon-Node100. JointLSP+DiGress (k=0k=0, no features) is included for direct comparison. Bold: best result excluding the k=17k=17 ceiling. Degree ↓ Clustering ↓ Triangles ↓ Assortativity ↓ PLE ↓ CPL ↓ DiGress + Structural features k=2k=2 9.32±3.089.32_± 3.08 5.08±2.955.08_± 2.95 11.75±4.5011.75_± 4.50 118.18±2.68118.18_± 2.68 7.43±2.657.43_± 2.65 47.23±8.4747.23_± 8.47 k=4k=4 7.01±0.537.01_± 0.53 9.73±7.679.73_± 7.67 11.46±4.5511.46_± 4.55 107.68±12.37107.68_± 12.37 10.07±5.7510.07_± 5.75 43.99±4.4343.99_± 4.43 k=8k=8 10.88±11.4210.88_± 11.42 5.89±4.605.89_± 4.60 7.45±5.087.45_± 5.08 79.81±52.7279.81_± 52.72 7.04±5.387.04_± 5.38 36.55±19.2836.55_± 19.28 k=10k=10 4.25±1.514.25_± 1.51 10.72±6.4610.72_± 6.46 10.06±6.1110.06_± 6.11 70.54±40.8570.54_± 40.85 6.99±3.696.99_± 3.69 34.47±21.4934.47_± 21.49 JointLSP+DiGress (no features) k=0k=0 10.50±0.1610.50_± 0.16 2.07±0.102.07_± 0.10 2.33±0.152.33_± 0.15 59.72±0.7559.72_± 0.75 10.79±0.1910.79_± 0.19 44.99±0.2944.99_± 0.29 DiGress + Structural features + Spectral features k=17k=17 0.93±0.000.93_± 0.00 1.95±0.001.95_± 0.00 1.68±0.001.68_± 0.00 3.55±0.003.55_± 0.00 1.53±0.001.53_± 0.00 1.92±0.001.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=10n=10 6.30±1.576.30_± 1.57 2.46±0.342.46_± 0.34 15.28±7.2715.28_± 7.27 12.41±1.5512.41_± 1.55 35.40±6.4135.40_± 6.41 12.97±4.1912.97_± 4.19 n=20n=20 22.47±1.6322.47_± 1.63 1.44±0.001.44_± 0.00 58.45±9.8858.45_± 9.88 49.80±3.0849.80_± 3.08 15.84±2.3915.84_± 2.39 11.46±2.2211.46_± 2.22 n=50n=50 21.09±0.9121.09_± 0.91 1.51±0.011.51_± 0.01 16.90±0.2316.90_± 0.23 70.67±1.9570.67_± 1.95 18.57±1.0718.57_± 1.07 55.49±3.0155.49_± 3.01 n=100n=100 4.53±0.114.53_± 0.11 11.33±0.2711.33_± 0.27 14.82±0.1214.82_± 0.12 101.95±2.13101.95_± 2.13 4.64±0.174.64_± 0.17 39.68±1.1439.68_± 1.14 JointLSP+DiGress (no features) n=10n=10 5.19±1.615.19_± 1.61 1.79±0.061.79_± 0.06 13.45±4.2513.45_± 4.25 1.25±0.251.25_± 0.25 23.58±4.9523.58_± 4.95 12.93±3.9012.93_± 3.90 n=20n=20 11.13±1.2911.13_± 1.29 1.40±0.001.40_± 0.00 8.38±0.928.38_± 0.92 14.04±3.7214.04_± 3.72 34.19±3.4734.19_± 3.47 7.82±1.247.82_± 1.24 n=50n=50 8.01±0.428.01_± 0.42 1.40±0.001.40_± 0.00 4.87±0.804.87_± 0.80 33.18±1.1633.18_± 1.16 10.77±0.6910.77_± 0.69 30.65±1.7130.65_± 1.71 n=100n=100 10.50±0.1610.50_± 0.16 2.07±0.102.07_± 0.10 2.33±0.152.33_± 0.15 59.72±0.7559.72_± 0.75 10.79±0.1910.79_± 0.19 44.99±0.2944.99_± 0.29 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. 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. References [1] R. Abboud, İ. İ. Ceylan, M. Grohe, and T. Lukasiewicz (2021) The surprising power of graph neural networks with random node initialization. External Links: 2010.01179, Link Cited by: §D.3. [2] D. J. Aldous (1981) Representations for partially exchangeable arrays of random variables. Journal of Multivariate Analysis 11 (4), p. 581–598. External Links: ISSN 0047-259X, Document, Link Cited by: Lemma 4.1. [3] J. Austin, D. D. Johnson, J. Ho, D. Tarlow, and R. van den Berg (2021) Structured denoising diffusion models in discrete state-spaces. In Advances in Neural Information Processing Systems, M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. W. Vaughan (Eds.), Vol. 34, p. 17981–17993. External Links: Link Cited by: §1, §2, §3. [4] B. Bollobás, S. Janson, and O. Riordan (2007) The phase transition in inhomogeneous random graphs. Random Structures and Algorithms 31 (1), p. 3–122. External Links: ISSN 1098-2418, Link, Document Cited by: §1. [5] F. Caron and E. B. Fox (2017) Sparse graphs using exchangeable random measures. Journal of the Royal Statistical Society Series B: Statistical Methodology 79 (5), p. 1295–1366. External Links: ISSN 1369-7412, Document, Link, https://academic.oup.com/jrsssb/article-pdf/79/5/1295/49269335/jrsssb_79_5_1295.pdf Cited by: §1. [6] S. Chanpuriya, C. N. Musco, K. Sotiropoulos, and C. Tsourakakis (2024) On the role of edge dependency in graph generative models. In Proceedings of the 41st International Conference on Machine Learning, R. Salakhutdinov, Z. Kolter, K. Heller, A. Weller, N. Oliver, J. Scarlett, and F. Berkenkamp (Eds.), Proceedings of Machine Learning Research, Vol. 235, p. 6325–6345. External Links: Link Cited by: §2, §6.2. [7] S. Chanpuriya, C. Musco, K. Sotiropoulos, and C. E. Tsourakakis (2021) On the power of edge independent graph models. CoRR abs/2111.00048. External Links: Link, 2111.00048 Cited by: §2. [8] H. Chen, N. Zilberstein, and S. Segarra (2026) Prior-informed flow matching for graph reconstruction. External Links: 2601.22107, Link Cited by: §2. [9] X. Chen, J. He, X. Han, and L. Liu (2023) Efficient and degree-guided graph generation via discrete diffusion modeling. External Links: 2305.04111, Link Cited by: §1, §1, §2, §6.2. [10] D. Dehaene and R. Brossard (2021) Re-parameterizing vaes for stability. CoRR abs/2106.13739. External Links: Link, 2106.13739 Cited by: §2. [11] V. P. Dwivedi and X. Bresson (2021) A generalization of transformer networks to graphs. External Links: 2012.09699, Link Cited by: §E.1, §4. [12] I. Evdaimon, G. Nikolentzos, C. Xypolopoulos, A. Kammoun, M. Chatzianastasis, H. Abdine, and M. Vazirgiannis (2024) Neural graph generator: feature-conditioned graph generation using latent diffusion models. External Links: 2403.01535, Link Cited by: §1, §2. [13] M. Fey and J. E. Lenssen (2019) Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, Cited by: §E.1. [14] J. G. Foster, D. V. Foster, P. Grassberger, and M. Paczuski (2010) Edge direction and the structure of networks. Proceedings of the National Academy of Sciences 107 (24), p. 10815–10820. External Links: Document, Link, https://w.pnas.org/doi/pdf/10.1073/pnas.0912671107 Cited by: §6.2. [15] I. Gat, T. Remez, N. Shaul, F. Kreuk, R. T. Chen, G. Synnaeve, Y. Adi, and Y. Lipman (2024) Discrete flow matching. Advances in Neural Information Processing Systems 37, p. 133345–133385. Cited by: §1, §2. [16] L. Gonon, T. Meyer-Brandis, and N. Weber (2026) Universality and approximation rates of graph neural networks with random features. External Links: 2607.26699, Link Cited by: §D.3. [17] K. K. Haefeli, K. Martinkus, N. Perraudin, and R. Wattenhofer (2023) Diffusion models for graphs benefit from discrete state spaces. External Links: 2210.01549, Link Cited by: §1, §2. [18] J. Ho, A. Jain, and P. Abbeel (2020) Denoising diffusion probabilistic models. CoRR abs/2006.11239. External Links: Link, 2006.11239 Cited by: §A.2, §A.2, Appendix C, §1, §2, §5.1. [19] R. v. d. Hofstad (2016) Random graphs and complex networks. Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press. Cited by: §1. [20] D. N. Hoover (1979) Relations on probability spaces and arrays of random variables. Technical report Institute for Advanced Study, Princeton, NJ. Note: Preprint External Links: Link Cited by: Lemma 4.1. [21] K. Jiang, J. Cui, X. Dong, and L. Toni (2026) Bures-wasserstein flow matching for graph generation. In The Fourteenth International Conference on Learning Representations, External Links: Link Cited by: §2. [22] J. Jo, S. Lee, and S. J. Hwang (2022) Score-based generative modeling of graphs via the system of stochastic differential equations. In Proceedings of the 39th International Conference on Machine Learning, K. Chaudhuri, S. Jegelka, L. Song, C. Szepesvari, G. Niu, and S. Sabato (Eds.), Proceedings of Machine Learning Research, Vol. 162, p. 10362–10383. External Links: Link Cited by: §1, §2. [23] M. Karami (2025) HiGen: hierarchical graph generative networks. External Links: 2305.19337, Link Cited by: §2. [24] N. Keriven and S. Vaiter (2022) Sparse and smooth: improved guarantees for spectral clustering in the dynamic stochastic block model. Electronic Journal of Statistics 16, p. 1330 – 1366. Cited by: Lemma B.1. [25] N. Keriven and S. Vaiter (2023) What functions can graph neural networks compute on random graphs? the role of positional encoding. In Neural Information Processing Systems (NeurIPS), Cited by: 2nd item. [26] D. P. Kingma and M. Welling (2022) Auto-encoding variational bayes. External Links: 1312.6114, Link Cited by: §4. [27] T. N. Kipf and M. Welling (2016) Variational graph auto-encoders. External Links: 1611.07308, Link Cited by: §4. [28] T. N. Kipf and M. Welling (2017) Semi-Supervised Classification with Graph Convolutional Networks. In ICLR, Cited by: 2nd item. [29] J. Lei and A. Rinaldo (2015) Consistency of spectral clustering in stochastic block models. Annals of Statistics 43, p. 215–237. External Links: Document, ISSN 00905364 Cited by: §B.2. [30] J. Leskovec, J. Kleinberg, and C. Faloutsos (2007) Graph evolution: densification and shrinking diameters. External Links: physics/0603229, Link Cited by: Appendix E. [31] M. Li, E. Kreacic, V. K. Potluru, and P. Li (2024) GraphMaker: can diffusion models generate large attributed graphs?. External Links: Link Cited by: §1, §2. [32] A. K. McCallum, K. Nigam, J. Rennie, and K. Seymore (2000) Automating the construction of internet portals with machine learning. Information Retrieval 3 (2), p. 127–163. External Links: Document, ISBN 1573-7659, Link Cited by: Appendix E, §6. [33] C. McDiarmid (1989) On the method of bounded differences. In Surveys in combinatorics, 1989 (Norwich, 1989), London Math. Soc. Lecture Note Ser., Vol. 141, p. 148–188. External Links: MathReview (Alan M. Frieze) Cited by: §B.3. [34] A. Melnik, M. Ljubljanac, C. Lu, Q. Yan, W. Ren, and H. Ritter (2024) Video diffusion models: a survey. External Links: 2405.03150, Link Cited by: §1. [35] M. E. J. Newman (2003) Mixing patterns in networks. Physical Review E 67 (2). External Links: ISSN 1095-3787, Link, Document Cited by: §6.2. [36] A. Q. Nichol and P. Dhariwal (2021) Improved denoising diffusion probabilistic models. In Proceedings of the 38th International Conference on Machine Learning, M. Meila and T. Zhang (Eds.), Proceedings of Machine Learning Research, Vol. 139, p. 8162–8171. External Links: Link Cited by: §1, §2. [37] M. Ninniri, M. Podda, and D. Bacciu (2025) Graph diffusion that can insert and delete. External Links: 2506.15725, Link Cited by: §2. [38] C. Niu, Y. Song, J. Song, S. Zhao, A. Grover, and S. Ermon (2020) Permutation invariant graph generation via score-based generative modeling. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, S. Chiappa and R. Calandra (Eds.), Proceedings of Machine Learning Research, Vol. 108, p. 4474–4484. External Links: Link Cited by: §1, §2. [39] I. Norros and H. Reittu (2006) On a conditionally poissonian graph process. Advances in Applied Probability 38 (1), p. 59–75. External Links: Document Cited by: §1, Definition 1. [40] N. Osman, K. Jiang, D. Buffelli, X. Dong, and L. Toni (2025) LGDC: latent graph diffusion via spectrum-preserving coarsening. External Links: 2512.01190, Link Cited by: §2. [41] Y. Qin, M. Madeira, D. Thanou, and P. Frossard (2025) DeFoG: discrete flow matching for graph generation. In International Conference on Machine Learning (ICML), Cited by: §E.1, §1, §2. [42] Y. QIN, C. Vignac, and P. Frossard (2025) SparseDiff: sparse discrete diffusion for scalable graph generation. Transactions on Machine Learning Research. Note: External Links: ISSN 2835-8856, Link Cited by: §D.2, Appendix E, §1, §1. [43] D. Roos, O. Davis, F. Eijkelboom, M. Bronstein, M. Welling, İ. İ. Ceylan, L. Ambrogioni, and J. van de Meent (2026) Categorical flow maps. External Links: 2602.12233, Link Cited by: §1, §2. [44] B. Rozemberczki, C. Allen, and R. Sarkar (2019) Multi-scale attributed node embedding. CoRR abs/1909.13021. External Links: Link, 1909.13021 Cited by: Appendix E, §6. [45] R. Sato, M. Yamada, and H. Kashima (2021) Random features strengthen graph neural networks. External Links: 2002.03155, Link Cited by: §D.3. [46] P. Sen, G. Namata, M. Bilgic, L. Getoor, B. Galligher, and T. Eliassi-Rad (2008) Collective classification in network data. AI Magazine 29 (3), p. 93. External Links: Link, Document Cited by: Appendix E. [47] A. Siraudin and C. Morris (2026) Principled latent diffusion for graphs via laplacian autoencoders. arXiv preprint arXiv:2601.13780. Cited by: §2, §5.1. [48] J. Sohl-Dickstein, E. Weiss, N. Maheswaranathan, and S. Ganguli (2015) Deep unsupervised learning using nonequilibrium thermodynamics. In Proceedings of the 32nd International Conference on Machine Learning, F. Bach and D. Blei (Eds.), Proceedings of Machine Learning Research, Vol. 37, Lille, France, p. 2256–2265. External Links: Link Cited by: §1, §2. [49] Y. Song and S. Ermon (2020) Generative modeling by estimating gradients of the data distribution. External Links: 1907.05600, Link Cited by: §1, §2. [50] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio (2018) Graph Attention Networks. In ICLR, Cited by: 1st item, §4. [51] C. Vignac, I. Krawczuk, A. Siraudin, B. Wang, V. Cevher, and P. Frossard (2023) DiGress: discrete denoising diffusion for graph generation. External Links: 2209.14734, Link Cited by: Appendix C, Appendix C, Appendix C, Appendix C, Appendix C, §D.3, §E.1, §1, §1, §2, §3, §3, §3, §4, §4, §5.2, §6.2, §6.2. [52] A. Wijesinghe, S. Kandanaarachchi, D. M. Steinberg, and C. S. Ong (2026) Flowette: flow matching with graphette priors for graph generation. External Links: 2602.23566, Link Cited by: §2. [53] K. Xu, W. Hu, J. Leskovec, and S. Jegelka (2019) How powerful are graph neural networks?. In International Conference on Learning Representations, External Links: Link Cited by: 3rd item. [54] J. You, R. Ying, X. Ren, W. L. Hamilton, and J. Leskovec (2018) GraphRNN: A deep generative model for graphs. CoRR abs/1802.08773. External Links: Link, 1802.08773 Cited by: §D.1, Appendix E, Appendix E, §6. [55] T. Zhang, Z. Wang, J. Huang, M. M. Tasnim, and W. Shi (2023) A survey of diffusion based image generation models: issues and their solutions. External Links: 2308.13142, Link Cited by: §1. Appendix A Appendix Algorithm 1 Calibrating the LSP terminal prior 1: Training dataset dataD_data, smoothing constant δ>0δ>0, number of quadrature nodes K 2: for each graph G∈dataG _data and each node i∈V⁡(G)i∈ V(G) do 3: Compute u~i=log⁡(di+δ)−1|V|∑k∈Vlog⁡(dk+δ) u_i= (d_i+δ)- 1|V| _k∈ V (d_k+δ) 4: end for 5: σLSP←std(u~i:i∈V(G),G∈data) _LSP (\ u_i:i∈ V(G),\,G _data\ ) ⊳ std over all nodes across all training graphs 6: ρdata←1|data|∑G∈data2|EG|nG(nG−1) _data← 1|D_data| _G _data 2|E_G|n_G(n_G-1) ⊳ mean empirical edge density over training graphs 7: Initialize μLSP0←12(log⁡ρdata−σLSP2) _LSP^0← 12( _data- _LSP^2) ⊳ sparse-regime approximation, see Appendix A.1 8: Solve ρ⁡(μLSP)=ρdataρ( _LSP)= _data for μLSP _LSP using K-node Gauss-Hermite quadrature to evaluate ρ⁡(⋅)ρ(·), starting from μLSP0 _LSP^0 9: return (μLSP,σLSP)( _LSP,\, _LSP) Algorithm 2 Training JointLSP 1: A graph G=(,0)G=(1,E^0), calibrated prior parameters (μLSP,σLSP)( _LSP, _LSP) from Algorithm 1 2: Sample t∼⁡(1,…,T)t (\1,…,T\) 3: Compute 0u^0 from G using Equation 12 4: Sample t∼q⁡(t∣0)u^t q(u^t ^0) using Equation 13 5: Compute ij0p_ij^0 for all pairs (i,j)(i,j) using pij0=1−e−eui0+uj0p_ij^0=1-e^-e^u_i^0+u_j^0 6: Sample t∼q⁡(t∣0,0)E^t q(E^t ^0,u^0) using Equation 15 7: (^0,t,^E,t)←ϕθ(t,t,t)( u^0,t, p^E,t)← _θ(u^t,E^t,t) 8: Optimizer step on ℒ⁡(^0,t,^E,t,0,0)L( u^0,t, p^E,t;u^0,E^0) using Equation 19 Algorithm 3 Sampling from JointLSP 1: Trained network ϕθ _θ, calibrated prior parameters (μLSP,σLSP)( _LSP, _LSP) 2: Sample n from the empirical node-count distribution of dataD_data 3: Sample T∼⁡(μLSP,σLSP2I)u^T ( _LSP, _LSP^2I) 4: Compute ijT=[1−pijT,pijT]p_ij^T=[1-p_ij^T,\,p_ij^T] where pijT=1−e−euiT+ujTp_ij^T=1-e^-e^u_i^T+u_j^T for all pairs (i,j)(i,j) 5: Sample TE^T: each edge (i,j)(i,j) independently from Bernoulli⁡(pijT)Bernoulli(p_ij^T) 6: for t=Tt=T down to 11 do 7: (^0,t,^E,t)←ϕθ(t,t,t)( u^0,t, p^E,t)← _θ(u^t,E^t,t) 8: Sample t−1∼pθ(t−1∣t,t)u^t-1 p_θ(u^t-1 ^t,E^t) using Equation 37 9: Sample t−1∼pθ(t−1∣^0,t,t)E^t-1 p_θ(E^t-1 u^0,t,E^t) using Equation 18 10: end for 11: return 0E^0 A.1 Constructing the Latent Sociability Prior We derive the calibration procedure for the terminal prior parameters (μLSP,σLSP)( _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 dataD_data. Reparameterization. From Section 5.2, the latent sociability weights satisfy wi=exp⁡(ui)w_i= (u_i), so ui=log⁡wi∈ℝu_i= w_i . We place a Gaussian prior on the log-weights, ui∼i.i.d.(μLSP,σLSP2)u_i i.i.d. N( _LSP, _LSP^2), which induces a log-normal distribution on wiw_i. With c=1c=1, the edge probability becomes pij=1−e−eui+ujp_ij=1-e^-e^u_i+u_j (20) Estimating σLSP _LSP. Since the true weights wiw_i are unobserved, we construct a proxy from the degree sequence. For each node i in each training graph G, define the centered log-degree u~i=log⁡(di+δ)−1|V|∑k∈Vlog⁡(dk+δ) u_i= (d_i+δ)- 1|V| _k∈ V (d_k+δ) (21) where δ>0δ>0 is a small smoothing constant. Centering removes the graph-level mean so that u~i u_i captures relative degree heterogeneity within each graph. We then set σLSP=std(u~i:i∈V(G),G∈data) _LSP=std (\ u_i:i∈ V(G),\,G _data\ ) (22) where the standard deviation is taken over all nodes across all training graphs. Estimating μLSP _LSP. We calibrate μLSP _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 ρdata=1|data|∑G∈data2|EG|nG(nG−1) _data= 1|D_data| _G _data 2|E_G|n_G(n_G-1) (23) Under the LSP with parameters (μLSP,σLSP)( _LSP, _LSP), the expected edge probability between any two nodes is ρ⁡(μLSP)=⁡[pij]=⁡[1−e−eui+uj]ρ( _LSP)=E[p_ij]=E [1-e^-e^u_i+u_j ] (24) Note that c enters Equation 24 only through the product ceui+ujc\,e^u_i+u_j, which in the sparse regime reduces to ce2μLSP+σLSP2c\,e^2 _LSP+ _LSP^2 (see Equation 27). Any value of c>0c>0 can therefore be absorbed into μLSP _LSP via the substitution μLSP←μLSP+12log⁡c _LSP← _LSP+ 12 c, leaving the model unchanged. We fix c=1c=1 throughout without loss of generality, since μLSP _LSP is calibrated directly to match ρdata _data. Since ui,uj∼i.i.d.(μLSP,σLSP2)u_i,u_j i.i.d. N( _LSP, _LSP^2), the sum S=ui+uj∼⁡(2μLSP,2σLSP2)S=u_i+u_j (2 _LSP,2 _LSP^2). Writing S=2μLSP+2σLSPZS=2 _LSP+ 2\, _LSP\,Z with Z∼⁡(0,1)Z (0,1), Equation 24 becomes ρ⁡(μLSP)=1−Z∼⁡(0,1)[e−e2μLSP+2σLSPZ]ρ( _LSP)=1-E_Z (0,1)\! [e^-e^2 _LSP+ 2\, _LSP\,Z ] (25) We solve ρ⁡(μLSP)=ρdataρ( _LSP)= _data for μLSP _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+uje^u_i+u_j is small, pij=1−e−eui+uj≈eui+ujp_ij=1-e^-e^u_i+u_j≈ e^u_i+u_j, so ρdata≈⁡[eui+uj]=e2μLSP+σLSP2 _data [e^u_i+u_j ]=e^2 _LSP+ _LSP^2 (26) Solving for μLSP _LSP gives the initialization μLSP0=12(log⁡ρdata−σLSP2) _LSP^0= 12 ( _data- _LSP^2 ) (27) where we have used c=1c=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 uiu_i; the result extends to the full vector u coordinatewise. Forward process. The standard DDPM forward process [18] takes the form xt=α¯tx0+1−α¯tϵ,ϵ∼⁡(0,I).x^t= α_t\,x^0+ 1- α_t\,ε, ε (0,I). (28) In our setting the latent sociability variables should diffuse toward a Gaussian prior with mean μLSP _LSP and variance σLSP2 _LSP^2, rather than toward ⁡(0,I)N(0,I). To obtain this, we apply the DDPM construction to the centered and scaled variable (u−μLSP)/σLSP(u- _LSP)/ _LSP: ut−μLSPσLSP=α¯tu0−μLSPσLSP+1−α¯tϵ,ϵ∼⁡(0,I). u^t- _LSP _LSP= α_t\, u^0- _LSP _LSP+ 1- α_t\,ε, ε (0,I). (29) Multiplying through by σLSP _LSP and adding μLSP _LSP gives ut=μLSP+α¯t(u0−μLSP)+σLSP1−α¯tϵ,ϵ∼⁡(0,I),u^t= _LSP+ α_t(u^0- _LSP)+ _LSP 1- α_t\,ε, ε (0,I), (30) so that ut=u0u^t=u^0 at t=0t=0 and ut→⁡(μLSP,σLSP2)u^t ( _LSP, _LSP^2) as t→Tt→ T. Reverse process. Since Equation 29 is the standard DDPM forward process applied to u~t:=(ut−μLSP)/σLSP u^t:=(u^t- _LSP)/ _LSP, the reverse posterior in u~ u-space is the standard DDPM Gaussian posterior [18]: q⁡(u~t−1∣u~t,u~0)=⁡(u~t−1∣μ~t−1,β~t)q( u^t-1 u^t, u^0)=N( u^t-1 μ_t-1,\, β_t) (31) with mean μ~t−1=α¯t−1βt1−α¯tu~0+αt(1−α¯t−1)1−α¯tu~t μ_t-1= α_t-1\, _t1- α_t\, u^0+ _t(1- α_t-1)1- α_t\, u^t (32) and variance β~t=βt(1−α¯t−1)1−α¯t. β_t= _t(1- α_t-1)1- α_t. (33) Substituting u~t=(ut−μLSP)/σLSP u^t=(u^t- _LSP)/ _LSP and u~0=(u0−μLSP)/σLSP u^0=(u^0- _LSP)/ _LSP into Equation 32 and multiplying through by σLSP _LSP gives the posterior mean in u-space: μt−1=μLSP+α¯t−1βt1−α¯t(u0−μLSP)+αt(1−α¯t−1)1−α¯t(ut−μLSP) _t-1= _LSP+ α_t-1\, _t1- α_t(u^0- _LSP)+ _t(1- α_t-1)1- α_t(u^t- _LSP) (34) The posterior variance scales by σLSP2 _LSP^2, giving σ~t2=σLSP2β~t=σLSP2βt(1−α¯t−1)1−α¯t σ_t^2= _LSP^2\, β_t= _LSP^2\, _t(1- α_t-1)1- α_t (35) so that q⁡(ut−1∣ut,u0)=⁡(ut−1∣μt−1,σ~t2).q(u^t-1 u^t,u^0)=N(u^t-1 _t-1,\, σ_t^2). (36) The reverse sampling step is therefore ut−1=μt−1+σLSPβt(1−α¯t−1)1−α¯tz,z∼⁡(0,1),u^t-1= _t-1+ _LSP _t(1- α_t-1)1- α_t\,z, z (0,1), (37) which is the update used in Section 5.2, with u0u^0 replaced by the network prediction u^0,t u^0,t at each timestep. Appendix B Proofs B.1 Proof of Lemma 4.1 Proof of Lemma 4.1. Since the edges are discrete in 0,1\0,1\, they are independent Bernoulli random variables. We note ℙ⁡(eij=1)=pijP(e_ij=1)=p_ij its parameters. Denote by A=[eij]ijA=[e_ij]_ij the adjacency matrix of a drawn graph, we have P=[pij]ij=⁡(A)P=[p_ij]_ij=E(A). By exchangeability, σAσ⊤σ Aσ has the same distribution as A for any permutation matrix σ, and therefore ⁡[σAσ⊤]=⁡[A]E[σ Aσ ]=E[A] (38) which is πPπ⊤=Pπ 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=pP_ij=p for all i≠ji≠ j. Therefore the model is Erdős–Rényi. ∎ B.2 Proof of Thm. 4.2 GNNs. Denote by (0)=X^(0)=X the input node features. The GNNs we are examining are all under the form (k)=σ⁡((k−1)θ0(k)+Sk((k−1))(k−1)θ1(k)+1n(k))∈ℝn×dkX^(k)=σ (X^(k-1) _0^(k)+S_k(X^(k-1))X^(k-1) _1^(k)+1_nb^(k) ) ^n× d_k where Sk((k−1))∈ℝn×nS_k(X^(k-1)) ^n× n are message-passing matrices that depends on the graph structure and may depend on the layer k and (k−1)X^(k-1) for attention-based models, θi(k)∈ℝdk−1×dk _i^(k) ^d_k-1× d_k are trainable weights, (k)∈ℝdkb^(k) ^d_k are trainable biases, and σ is an activation function that we assume to be 11-Lipschitz. All models can then be obtained by varying the choice of Sk()S_k(X), which we denote by S when it is fixed: • for GCN, S=D~−1/2A~D~−1/2S= D^-1/2 A D^-1/2 where A~=Id+A A=Id+A and D~ D is the corresponding degree matrix. • GIN uses sum-aggregation, which would correspond to S=AS=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, S=1pnAS= 1pnA assuming that p is known for simplicity. Note that, for a fixed graph size n, this normalization can be absorbed by the weight θ1 _1, such that this is indeed equivalent to the vanilla GIN; • for GAT, we consider attention coefficients ck(,′)c_k(x,x ) at layer k (typically exponentials of dot products), and normalized attention: [Sk()]ij=ck(i,j)∑ℓ∼ick(i,ℓ)[S_k(X)]_ij= c_k(x_i,x_j) _ ic_k(x_i,x_ ) We will assume that ck(⋅)≥cmin>0c_k(·)≥ c_ >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 p^ij=[φ⁡(i(K),j(K))]i,j=1n∈[0,1] p_ij=[ (x_i^(K),x_j^(K))]_i,j=1^n∈[0,1] where φ is a link function that we assume to be LφL_ -Lipschitz in each component. Proof of Thm. 4.2. Recall that std(p^)=1n2∑ij(p^ij−p¯)2 std( p)= 1n^2 _ij( p_ij- p)^2 where p¯=∑ijp^ij p= _ij p_ij. First observe that ∑ij(p^ij−p¯)2=min⁡∑ijp⁡(pij−p)2 _ij( p_ij- p)^2= _p _ij(p_ij-p)^2 and similarly, for ∈ℝn×dX ^n× d, std()=1n∑i‖i−¯‖2=min⁡1n∑i‖i−‖2 std(X)= 1n _i _i- x ^2= _x 1n _i _i-x ^2 where ¯=1n∑i x= 1n _ix_i. We therefore denote ¯(k)=1n∑i(k) x^(k)= 1n _ix^(k)_i. Hence, for any x, by Lipschitz property of φ and a triangular inequality std(p^) std( p) ≤1n2∑ij(φ⁡(i(K),j(K))−φ⁡(,))2 ≤ 1n^2 _ij( (x_i^(K),x_j^(K))- (x,x))^2 ≤1n2∑ij(φ⁡(i(K),j(K))−φ⁡(i(K),))2+1n2∑ij(φ⁡(i(K),)−φ⁡(,))2 ≤ 1n^2 _ij( (x_i^(K),x_j^(K))- (x_i^(K),x))^2+ 1n^2 _ij( (x_i^(K),x)- (x,x))^2 ≤2Lφ1n∑i‖i(K)−‖2 ≤ 2L_ 1n _i _i^(K)-x ^2 and by minimizing over x, we get std(p^)≤2Lφstd((K)) std( p)≤ 2L_ std(X^(K)). Now, denote by Ek=std((k))E_k= std(X^(k)). Define ‖⋅‖F,n=‖⋅‖F/n · _F,n= · _F/ n for short, where ‖⋅‖F · _F is the Frobenius norm, and observe that std()=‖−1n¯⊤‖F,n std(X)= -1_n x _F,n. Moreover, observe that ‖Sθ‖F,n≤‖S‖2‖F,n‖θ‖2 SXθ _F,n≤ S _2 _F,n θ _2. We have the recursion equation: since minimizing over x is more general than over σ⁡()σ(x), and using the fact that σ is 11-Lipschitz and we can decompose minx⁡‖y+y′−x‖=minx,x′⁡‖y+y′−(x+x′)‖≤minx⁡‖y−x‖+minx⁡‖y′−x‖ _x y+y -x = _x,x y+y -(x+x ) ≤ _x y-x + _x y -x , std((k)) std(X^(k)) =min⁡‖(k)−1n⊤‖F,n≤min⁡‖(k)−1nσ()⊤‖F,n = _x ^(k)-1_nx _F,n≤ _x ^(k)-1_nσ(x) _F,n =min⁡‖σ⁡((k−1)θ0(k)+Sk((k−1))(k−1)θ1(k)+1n(k))−σ⁡(1n⊤)‖F,n = _x σ (X^(k-1) _0^(k)+S_k(X^(k-1))X^(k-1) _1^(k)+1_nb^(k) )-σ(1_nx ) _F,n ≤min⁡‖(k−1)θ0(k)+Sk((k−1))(k−1)θ1(k)+1n(k)−1n⊤‖F,n ≤ _x ^(k-1) _0^(k)+S_k(X^(k-1))X^(k-1) _1^(k)+1_nb^(k)-1_nx _F,n ≤min⁡‖(k−1)θ0(k)−1n⊤‖F,n+min⁡‖Sk((k−1))(k−1)θ1(k)−1n⊤‖F,n ≤ _x ^(k-1) _0^(k)-1_nx _F,n+ _x S_k(X^(k-1))X^(k-1) _1^(k)-1_nx _F,n For the first term, by picking =θ0(k)⊤¯(k−1)x=θ^(k)_0 x^(k-1), we get min⁡‖(k−1)θ0(k)−1n⊤‖F,n≤‖((k−1)−1n(¯(k−1))⊤)θ0(k)‖F,n≤Ek−1‖θ0(k)‖2 _x ^(k-1) _0^(k)-1_nx _F,n≤ (X^(k-1)-1_n( x^(k-1)) ) _0^(k) _F,n≤ E_k-1 _0^(k) _2 We need to divide the second term, since the term 1n⊤1_nx cannot necessarily be written as Sk((k−1))1n′⊤S_k(X^(k-1))1_nx for some ′x . So we introduce a term Sk((k−1))1n′⊤S_k(X^(k-1))1_nx for some ′x : min⁡‖Sk((k−1))(k−1)θ1(k)−1n⊤‖F,n _x S_k(X^(k-1))X^(k-1) _1^(k)-1_nx _F,n ≤‖Sk((k−1))((k−1)θ1(k)−1n′⊤)‖F,n ≤ S_k(X^(k-1)) (X^(k-1) _1^(k)-1_nx ) _F,n +min⁡‖Sk((k−1))1n′⊤−1n⊤‖F,n + _x S_k(X^(k-1))1_nx -1_nx _F,n Then, as previously, by picking ′=~k=θ1(k)⊤¯(k−1)x = x_k=θ^(k)_1 x^(k-1) the first term in this equation can be bounded by ‖Sk((k−1))((k−1)θ1(k)−1n′⊤)‖F,n≤‖Sk((k−1))‖2Ek−1‖θ1(k)‖2 S_k(X^(k-1)) (X^(k-1) _1^(k)-1_nx ) _F,n≤ S_k(X^(k-1)) _2E_k-1 _1^(k) _2 Note that we must then bound ‖Sk((k−1))‖2 S_k(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((k−1))1n~k⊤−1n⊤‖F,nr_n^(k)= _x S_k(X^(k-1))1_n x_k -1_nx _F,n which we will again bound for each example. At the end of the day, we obtain Ek E_k ≤(‖θ0(k)‖2+‖Sk((k−1))‖2‖θ1(k)‖2)⏟ukEk−1+rn(k) ≤ ( _0^(k) _2+ S_k(X^(k-1)) _2 _1^(k) _2 )_u_kE_k-1+r_n^(k) =∑ℓ=1k[∏p=ℓ+1kup]rn(ℓ)⏟rn(δ)+[∏ℓ=1kup]E0 = _ =1^k [ _p= +1^ku_p ]r_n^( )_r_n(δ)+ [ _ =1^ku_p ]E_0 For all example, we are going to show that uk=O⁡(1)u_k=O(1) with probability 1−δ1-δ if n is large enough, and bound rn(δ)r_n(δ) wrt n and δ. Our general strategy will be to write rn(k)=min⁡‖Sk((k−1))1n~k⊤−1n⊤‖F,n≤‖~k‖mincmaxi|∑j∼isij−c|r_n^(k)= _x S_k(X^(k-1))1_n x_k -1_nx _F,n≤ x_k _c _i | _j is_ij-c | (40) for some constant c∈ℝc (often 11 in our examples), and sijs_ij are the elements of Sk((k−1))S_k(X^(k-1)) for short. We remark that ‖~k‖≤‖θ1(k)‖2‖(k−1)‖F,n x_k ≤ _1^(k) _2 ^(k-1) _F,n and we can use Lemma B.2 to bound this term, which again involves uku_k. 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−δ1-δ, the degrees did_i satisfy maxi⁡|dipn−1|≲log⁡(n/δ)pn _i | d_ipn-1 | (n/δ)pn (41) In particular, if n≳log⁡(n/δ)pn (n/δ)p (42) then with probability 1−δ1-δ, for all i pn2≤di≤3pn2 pn2≤ d_i≤ 3pn2 We now bound ‖Sk((k−1))‖2 S_k(X^(k-1)) _2 and rnr_n through Equation 40 for our examples. GAT. GAT is actually the simplest model to bound. Indeed, due to the normalization of the coefficients ∑j∼isij=1 _j is_ij=1 at all layers, we directly obtain rn(k)=0r_n^(k)=0. For the bound on ‖Sk()‖2 S_k(X) _2, we remark that under the bound Equation 42 on n, for all i,j,ki,j,k ck(i,j)∑ℓ∼ick(i,ℓ)≤cmaxcmin2pn c_k(x_i,x_j) _ ic_k(x_i,x_ )≤ c_ c_ 2pn and thus for any layer and X ‖Sk()‖2 S_k(X) _2 ≤‖Sk()‖F=∑ijsij2≲cmaxcmin∑idi(pn)2≲cmaxpcmin ≤ S_k(X) _F= _ijs_ij^2 c_ c_ _i d_i(pn)^2 c_ pc_ hence the result C=O⁡(1/pK)C=O(1/p^K). GIN. For GIN, we have S=A/(pn)S=A/(pn). Hence Equation 40 directly yields rn(k)≤‖~k‖maxi|dipn−1|r_n^(k)≤ x_k _i | d_ipn-1 |, and the last term is smaller than ϵε when pn≥ϵ−2log⁡(n/δ)pn≥ε^-2 (n/δ) by Lemma B.1. For the bound on ‖S‖2 S _2, we invoke [29, Thm 5.2], such that for any r>0r>0, there is a constant CrC_r such that, if n≥Cr(1/δ)rn≥ C_r(1/δ)^r, then ‖Apn−1n×n‖2≲1pn Apn- 1_n× nn _2 1 pn and ‖1n×n‖2=1 1_n× nn _2=1 hence the result. GCN. For GCN, if pn≥ϵ−2log⁡(n/δ)pn≥ε^-2 (n/δ) by Lemma B.1 |di−pn|=O⁡(pnϵ)|d_i-pn|=O(pnε) and thus since 1a=1b+O⁡(|a−b|b3/2) 1 a= 1 b+O( |a-b|b^3/2), 1di=1pn+O⁡(ϵpn) 1 d_i= 1 pn+O ( ε pn ) From this we get maxi⁡|∑j∼isij−1| _i | _j is_ij-1 | =maxi⁡|1di∑j∼i1dj−1| = _i | 1 d_i _j i 1 d_j-1 | ≤maxi⁡|dipn−1|+O⁡(ϵpn) ≤ _i | d_ipn-1 |+O ( ε pn ) and we go back to the GIN case. For the bound on ‖S‖2 S _2 we have directly that ‖S‖2≤1 S _2≤ 1, since its a symmetric normalized Laplacian (up to identity term). ∎ Lemma B.2. ‖(k)‖F,n≤∑ℓ=1k[∏p=ℓ+1kup]vℓ+[∏ℓ=1kup]‖(0)‖F,n ^(k) _F,n≤ _ =1^k [ _p= +1^ku_p ]v_ + [ _ =1^ku_p ] ^(0) _F,n (43) where uk=‖θ0(k)‖2+‖Sk((k−1))‖2‖θ1(k)‖2,vk=‖(k)‖ u_k= _0^(k) _2+ S_k(X^(k-1)) _2 _1^(k) _2, v_k= ^(k) Proof. We write the recursion ‖(k)‖F,n ^(k) _F,n =‖σ⁡((k−1)θ0(k)+Sk((k−1))(k−1)θ1(k)+1n(k))‖F,n = σ (X^(k-1) _0^(k)+S_k(X^(k-1))X^(k-1) _1^(k)+1_nb^(k) ) _F,n ≤(‖θ0(k)‖2+‖Sk((k−1))‖2‖θ1(k)‖2)⏟uk‖(k−1)‖F,n+‖(k)‖⏟vk ≤ ( _0^(k) _2+ S_k(X^(k-1)) _2 _1^(k) _2 )_u_k ^(k-1) _F,n+ ^(k) _v_k =∑ℓ=1k[∏p=ℓ+1kup]vℓ+[∏ℓ=1kup]‖(0)‖F,n = _ =1^k [ _p= +1^ku_p ]v_ + [ _ =1^ku_p ] ^(0) _F,n ∎ B.3 Proof of Lemma 4.3 With the same reasoning as before, we have std(Ci/C)≤maxi⁡|Ci/C−1| std(C_i/C)≤ _i|C_i/C-1| we are going to bound the right hand side. The feature CiC_i can be expressed as a sum over subsets of r−1r-1 indices: Ci=∑⊂([1,n]\i)r−11Gi∪≃HC_i= _S⊂([1,n] \i\)^r-11_G_\i\ H (44) where G_S refers to the subgraph of G corresponding to subset of nodes S, and 1F≃H=11_F H=1 if F and H are isomorphic and 00 otherwise. By exchangeability, it is obvious that C=⁡(Ci)C=E(C_i) does not depend on the node i. For S of size r, since G_S is also an E-R graph of size r, we have 1Gi∪≃H=r!pmH(1−p)r⁡(r−1)/2−mHE1_G_\i\ H=r!p^m_H(1-p)^r(r-1)/2-m_H where mHm_H is the number of edges in H, such that C=(n−1r−1)r!pmH(1−p)r⁡(r−1)/2−mH=O⁡(nr−1)C= n-1r-1r!p^m_H(1-p)^r(r-1)/2-m_H=O(n^r-1) (45) We are going to bound the deviation of Ci/C_i/C from its expectation of 11 using McDiarmid’s concentration inequality [33], which requires to bound the variation of Ci/C_i/C when one edge ekℓe_k flips, and sum the square of these variations over all indices k,ℓk, . If ekℓe_k flips and k,ℓk, are different from i, then the terms affected are those where S contains both k,ℓk, . There are (n−3r−3)=O⁡(nr−3) n-3r-3=O(n^r-3) such terms, such that the deviation of Ci/C_i/C is of order 1/n21/n^2. There are O⁡(n2)O(n^2) such indices k,ℓk, , such that the sum of the square of the deviation has a term O⁡(n2/n4)=O⁡(1/n2)O(n^2/n^4)=O(1/n^2). If ekℓe_k flips and k=ik=i, then the terms affected are those where S contains ℓ . There are (n−2r−2)=O⁡(nr−2) n-2r-2=O(n^r-2) such terms, such that the deviation of Ci/C_i/C is of order 1/n1/n. There are O⁡(n)O(n) such indices k,ℓk, , such that the sum of the square of the deviation has a term O⁡(n/n2)=O⁡(1/n)O(n/n^2)=O(1/n). Similarly when ℓ=i =i. Hence, by applying McDiarmid’s inequality, with probability 1−δ1-δ, |Ci/C−1||C_i/C-1| is bounded by log⁡(1/δ)/n (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−x1-e^-x yields pij=eui+uj+O⁡((eui+uj)2)=eui+uj+O⁡(e−4cn)p_ij=e^u_i+u_j+O((e^u_i+u_j)^2)=e^u_i+u_j+O(e^-4c_n) Then, ⁡(di∣) (d_i ) =∑jpij=∑jeui+uj+O⁡(ne−4cn) = _jp_ij= _je^u_i+u_j+O(ne^-4c_n) (∑jeuj)⏟Ceui+O⁡(ne−4cn) ( _je^u_j )_Ce^u_i+O(ne^-4c_n) Appendix 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 ¯Et,ij Q_E^t,ij are parameterized by the clean latent vector 0u^0 rather than the noisy tu^t 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 G0G^0 has a discrete component that depends on 0u^0: edges converge to Bernoulli⁡(pij0)Bernoulli(p_ij^0) where pij0=1−e−eui0+uj0p_ij^0=1-e^-e^u_i^0+u_j^0. The sampling process (Algorithm 3), on the other hand, draws T∼⁡(μLSP,σLSP2I)u^T ( _LSP, _LSP^2I) and then samples edges from Bernoulli⁡(pijT)Bernoulli(p_ij^T) where pijTp_ij^T depends on Tu^T. These two terminals coincide only in expectation over 0u^0. 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 zt=(t,t)z^t=(u^t,E^t), with clean graph z0=(0,0)z^0=(u^0,E^0) and terminal state zT=(T,T)z^T=(u^T,E^T). Joint forward factorization. Because the continuous and discrete components are corrupted independently, the forward process factorizes as q⁡(zt∣z0)=q⁡(t∣0)q(t∣0,0)q(z^t z^0)=q(u^t ^0)\,q(E^t ^0,u^0) (46) The continuous component follows the shifted-scaled Gaussian diffusion of Appendix A.2: q(t∣0)=(t|μLSP+α¯t(0−μLSP),σLSP2(1−α¯t)I)q(u^t ^0)=N\! (u^t\; |\; _LSP+ α_t(u^0- _LSP),\; _LSP^2(1- α_t)I ) (47) The discrete component follows from the pair-specific forward marginals of Equation 15: q⁡(t∣0,0)=∏1≤i,j≤nq⁡(eijt∣eij0,0)q(E^t ^0,u^0)= _1≤ i,j≤ nq(e_ij^t e_ij^0,\,u^0) (48) Evidence lower bound. Following [51], applying Jensen’s inequality with q(z1:T∣z0)q(z^1:T z^0) as the variational distribution gives the ELBO: logpθ(G)≥logp(nG)−DKL[q(zT∣G)∥p(zT∣nG)]−∑t=2TLt(G)+q⁡(z1∣G)[logpθ(G∣z1)] p_θ(G)≥ p(n_G)-D_KL\! [q(z^T G)\,\|\,p(z^T n_G) ]- _t=2^TL_t(G)+E_q(z^1 G)\! [ p_θ(G z^1) ] (49) where Lt(G)=q⁡(zt∣G)[DKL(q(zt−1∣zt,z0)∥pθ(zt−1∣zt))]L_t(G)=E_q(z^t G) [D_KL\! (q(z^t-1 z^t,z^0)\,\|\,p_θ(z^t-1 z^t) ) ] (50) Terminal prior KL. With the 0u^0-keyed forward process, the training terminal factors as p⁡(zT∣nG)=⁡(μLSP,σLSP2I)×∏1≤i,j≤nBernoulli⁡(pij0)p(z^T n_G)=N( _LSP,\, _LSP^2I)× _1≤ i,j≤ nBernoulli(p_ij^0) (51) where pij0=1−exp⁡(−eui0+uj0)p_ij^0=1- (-e^u_i^0+u_j^0) depends on the clean graph. The prior KL decomposes as DKL[q(zT∣G)∥p(zT∣nG)]=DKL[q(T∣0)∥(μLSP,σLSP2I)]+DKL[q(T∣0,0)∥∏1≤i,j≤nBernoulli(pij0)]D_KL\! [q(z^T G)\,\|\,p(z^T n_G) ]=D_KL\! [q(u^T ^0)\,\|\,N( _LSP, _LSP^2I) ]\\ +\,D_KL\! [q(E^T ^0,u^0)\,\|\, _1≤ i,j≤ nBernoulli(p_ij^0) ] (52) Both terms vanish as α¯T→0 α_T→ 0 for the 0u^0-keyed forward process: the continuous component converges to ⁡(μLSP,σLSP2I)N( _LSP, _LSP^2I) and each row of ¯ET,ij Q_E^T,ij converges to (ij0)⊤(p_ij^0) , so q⁡(eijT∣eij0,0)q(e_ij^T e_ij^0,u^0) converges to Bernoulli⁡(pij0)Bernoulli(p_ij^0) independently of eij0e_ij^0. Note that this vanishing holds for the training terminal conditioned on 0u^0, not for the unconditional sampling terminal. Decomposition of the diffusion loss. Because the forward posterior factorizes as q⁡(zt−1∣zt,z0)=q⁡(t−1∣t,0)q(t−1∣t,0,0)q(z^t-1 z^t,z^0)=q(u^t-1 ^t,u^0)\,q(E^t-1 ^t,E^0,u^0) (53) the per-step loss Lt(G)L_t(G) splits into independent continuous and discrete terms: Lt(G)=Ltu(G)+Lt(G)L_t(G)=L_t^u(G)+L_t^E(G) (54) where Lt(G)L_t^E(G) is identical in form to the DiGress per-step loss [51], and Ltu(G)L_t^u(G) is the additional term: Ltu(G)=q⁡(t∣0)[DKL(q(t−1∣t,0)∥pθ(t−1∣zt))]L_t^u(G)=E_q(u^t ^0) [D_KL\! (q(u^t-1 ^t,u^0)\,\|\,p_θ(u^t-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 0u^0-keyed forward process by construction. Appendix 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. Table 3: Results on Tree dataset Method Degree Assortativity PLE CPL DiGress 1073.41 ± 38.35 33.89 ± 0.81 242.14 ± 0.63 222.38 ± 6.51 JointLSP+DiGress 204.17 ± 26.83 15.45 ± 1.58 134.26 ± 2.03 231.38 ± 1.19 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=500n=500 and the Ego and Community datasets. The results on CoraChameleon across n∈10,20,50,100,500n∈\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=500n=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 4: MMD ratios on CoraChameleon datasets for SparseDiff and JointLSP+SparseDiff under no-node features. Results are mean± over 3 random seeds. Bold: better of SparseDiff vs. JointLSP+SparseDiff. Degree ↓ Clustering ↓ Triangles ↓ Assortativity ↓ PLE ↓ CPL ↓ SparseDiff (no features) n=10n=10 17.23±0.8717.23_± 0.87 1.99±0.021.99_± 0.02 6.68±0.076.68_± 0.07 69.77±18.1769.77_± 18.17 431.13±133.46431.13_± 133.46 114.33±21.79114.33_± 21.79 n=20n=20 49.10±2.0849.10_± 2.08 1.41±0.001.41_± 0.00 3.67±0.433.67_± 0.43 30.17±4.0330.17_± 4.03 27.25±2.6727.25_± 2.67 0.92±0.120.92_± 0.12 n=50n=50 17.51±0.9817.51_± 0.98 1.55±0.041.55_± 0.04 25.87±0.7725.87_± 0.77 60.65±4.8460.65_± 4.84 4.98±0.594.98_± 0.59 3.69±0.393.69_± 0.39 n=100n=100 30.43±0.1530.43_±0.15 3.43±0.103.43_±0.10 66.65±0.7666.65_±0.76 50.44±2.3450.44_±2.34 15.33±0.1015.33_±0.10 18.92±0.1018.92_±0.10 n=500n=500 3.93±0.013.93_± 0.01 3.23±0.023.23_± 0.02 113.81±7.41113.81_± 7.41 39.04±0.1439.04_± 0.14 2.13±0.002.13_± 0.00 7.93±0.007.93_± 0.00 JointLSP+SparseDiff (no features) n=10n=10 14.18±0.6414.18_± 0.64 2.00±0.012.00_± 0.01 6.43±0.146.43_± 0.14 11.38±7.1611.38_± 7.16 37.70±14.1337.70_± 14.13 37.19±3.1937.19_± 3.19 n=20n=20 29.08±1.1129.08_± 1.11 1.40±0.001.40_± 0.00 2.19±0.232.19_± 0.23 15.31±0.9515.31_± 0.95 15.75±1.2915.75_± 1.29 0.54±0.120.54_± 0.12 n=50n=50 13.29±0.3213.29_± 0.32 1.49±0.011.49_± 0.01 15.11±0.3415.11_± 0.34 36.18±1.1636.18_± 1.16 6.29±0.196.29_± 0.19 5.76±0.165.76_± 0.16 n=100n=100 19.07±0.4919.07_± 0.49 3.07±0.073.07_± 0.07 36.00±0.8436.00_± 0.84 24.88±1.1824.88_± 1.18 11.14±0.2311.14_± 0.23 16.24±0.2116.24_± 0.21 n=500n=500 3.82±0.013.82_± 0.01 2.99±0.022.99_± 0.02 35.41±4.2135.41_± 4.21 28.89±0.2728.89_± 0.27 2.20±0.002.20_± 0.00 8.37±0.008.37_± 0.00 Table 5: Comparison of graph generation with JointLSP+SparseDiff and SparseDiff on Ego and Community datasets. Results are mean± over 3 random seeds. Degree ↓ Clustering ↓ Triangles ↓ Assortativity ↓ PLE ↓ CPL ↓ Ego SparseDiff 768.06±107.44768.06_± 107.44 14.78±0.2514.78_± 0.25 85.20±12.2185.20_± 12.21 1715.86±53.101715.86_± 53.10 1696.14±183.271696.14_± 183.27 183.07±31.15183.07_± 31.15 JointLSP+SparseDiff 302.50±51.36302.50_± 51.36 15.48±0.5715.48_± 0.57 12.41±1.2512.41_± 1.25 785.72±141.52785.72_± 141.52 750.94±145.86750.94_± 145.86 28.95±6.3128.95_± 6.31 Community SparseDiff 91.57±24.3491.57_± 24.34 6.86±0.636.86_± 0.63 8.12±0.968.12_± 0.96 0.99±1.270.99_± 1.27 226.18±49.36226.18_± 49.36 21917.62±157.4321917.62± 157.43 JointLSP+SparseDiff 38.70±14.1838.70_±14.18 5.08±0.445.08_±0.44 1.54±0.441.54_±0.44 9.02±6.799.02_±6.79 105.09±39.66105.09_±39.66 18251.36±550.4618251.36_±550.46 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) d_i=d_i/(n-1) as a node-level feature, and the mean μd _d and standard deviation σd _d of d~i d_i across nodes as graph-level features, recomputed from the noisy adjacency AtA_t 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 AtA_t is approximately E-R, so all d~i≈p¯ 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 u0u^0, 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=0k=0, no features) is included for direct comparison. Bold: best result excluding the k=17k=17 ceiling. Degree ↓ Clustering ↓ Triangles ↓ Assortativity ↓ PLE ↓ CPL ↓ DiGress+Degree k=1k=1 10.67±0.1410.67_± 0.14 2.04±0.022.04_± 0.02 2.41±0.142.41_± 0.14 57.66±0.7657.66_± 0.76 10.81±0.1710.81_± 0.17 45.54±0.5645.54_± 0.56 JointLSP+DiGress k=0k=0 10.50±0.1610.50_± 0.16 2.07±0.102.07_± 0.10 2.33±0.152.33_± 0.15 59.72±0.7559.72_± 0.75 10.79±0.1910.79_± 0.19 44.99±0.2944.99_± 0.29 DiGress + 17 features k=17k=17 0.93±0.000.93_± 0.00 1.95±0.001.95_± 0.00 1.68±0.001.68_± 0.00 3.55±0.003.55_± 0.00 1.53±0.001.53_± 0.00 1.92±0.001.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=Tt=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. (a) Forward Noising Process. (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. 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=X=1), and at each denoising step we concatenate random features r∈ℝn×dr ^n× d, drawn i.i.d. from ⁡(0,I)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 4.53±0.1 11.33±0.27 14.82±0.12 101.95±2.13 4.64±0.17 39.68±1.14 DiGress+RND 5.48±0.13 12.50±1.18 10.13±0.04 127.06±6.20 4.14±0.41 24.01±1.57 JointLSP+DiGress 10.50±0.16 2.07±0.10 2.33±0.15 59.72±0.75 10.79±0.19 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,0t∈\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 ^ijE,t p_ij^E,t 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=500t=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→0t→ 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. 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=100m=100 graphs) with increasing node sizes n=10,20,50,100,500,1000n=\10,20,50,100,500,1000\ under three random graph models: 1. Dense Bernoulli baseline: Aij∼Bern(ρdense)A_ij Bern( _dense), where ρdense=0.1 _dense=0.1. 2. Sparse mean-field Bernoulli: Aij∼Bern(ρsparse)A_ij Bern( _sparse), where ρsparse=k¯n−1 _sparse= kn-1 and k¯=5 k=5, and 3. Latent Sociability Prior: Aij∼Bern(Pij)A_ij Bern(P_ij), where Pij=1−e(−ceui+uj)P_ij=1-e^(-ce^u_i+u_j). To quantify node-level heterogeneity, we measure the within-graph degree variance Vari(di(m))Var_i(d_i^(m)) and within-graph degree mean i[di(m)]E_i[d_i^(m)], and define the dispersion index φ=Vari[di(m)]i[di(m)], = Var_i[d_i^(m)]E_i[d_i^(m)], (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→1000n→ 1000, both the dense and sparse Bernoulli baselines yield φ≈1 ≈ 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 >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. Figure 5: Dispersion index φ as a function of node size under three prior models. Unlike edge-independent 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,1000n=\10,20,50,100,500,1000\, we simulate 100100 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. (a) Triangle Count. (b) 4-Cycle Count. (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. 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,5000n∈\100,500,1000,2000,5000\ under two priors at matched edge density ρ=0.1ρ=0.1. For E-R, each edge is drawn independently with probability p=0.1p=0.1. For the LSP, we fix σLSP=1.0 _LSP=1.0 and solve for μLSP _LSP such that ⁡[pij]=0.1E[p_ij]=0.1 using the calibration procedure of Algorithm 1. Graphs are then sampled directly from the prior by drawing ui∼⁡(μLSP,σLSP2)u_i ( _LSP,σ^2_LSP) and connecting each pair (i,j)(i,j) with probability pij=1−e−eui+ujp_ij=1-e^-e^u_i+u_j. 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 CiC_i and measure std⁡(Ci/C¯)std(C_i/ C) where C¯=meani(Ci) C=mean_i(C_i). 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. 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. Appendix 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.5 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.7p_forward=0.7 and backward probability pbackward=0.3p_backward=0.3. And a dense-core sampling strategy that randomly picks top-10%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 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|/2n=|V|/2 nodes and p=0.3p=0.3. The inter-community edges are added with probability 0.05|V|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 3000 10 [14,45] CoraChameleon-Node20 3000 20 [27,120] CoraChameleon-Node50 3000 50 [71,300] CoraChameleon-Node100 3000 100 [172,600] CoraChameleon-Node500 1400 500 [1282,4630] EGO 757 [50,399] [57,1071] Community 510 [60,160] [231,1956] (a) CoraChameleon-Node100 (b) CoraChameleon-Node500 (c) Community dataset Figure 8: Sample graphs from the training set. (a) Sample CoraChameleon-Node100 graphs generated using JointLSP+DiGress. (b) Sample CoraChameleon-Node100 graphs generated 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 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 LR Weight Decay #Training Epochs Diffusion Steps JointLSP+DiGress CoraChameleon-Node10 6 0.0001 0.00012 5000 500 CoraChameleon-Node20 6 0.0001 0.00012 5000 500 CoraChameleon-Node50 6 0.0001 0.00012 5000 500 CoraChameleon-Node100 6 0.0001 0.00012 5000 500 JointLSP+SparseDiff CoraChameleon-Node10 6 0.0001 0.00001 100 500 CoraChameleon-Node20 6 0.0001 0.00001 100 500 CoraChameleon-Node50 6 0.0001 0.00001 100 500 CoraChameleon-Node100 6 0.0001 0.00001 100 500 CoraChameleon-Node500 4 0.0001 0.00001 100 500 EGO 6 0.0001 0.000012 2000 500 Community 6 0.0001 0.000012 1000 500 Runtime analysis LSP does not change the complexity of the underlying model. The denoiser forward pass is O⁡(Kn2d2)O(Kn^2d^2) for both DiGress and JointLSP+DiGress; the operations LSP adds is computing pij0=1−e−eui0+uj0p^0_ij=1-e^-e^u^0_i+u^0_j across node pairs and the DDPM update on the n latent variables which are O⁡(n2)O(n^2) and O⁡(n)O(n) respectively, smaller than the base cost by a factor O⁡(Kd2)O(Kd^2). Prior calibration (Algorithm 1) is a one time pre-processing step, not per-iteration. Table 10: Runtime analysis Metric DiGress JointLSP+DiGress Model parameters 8,888,579 8,888,579 Training step (in ms) 493.3±4.7 489.8±5.0 Peak GPU Memory (GiB) 13.40 13.39 Sampling (graph/sec) 9.50 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. Table 11: Auxiliary features used in DiGress. Feature Description k3_node Node triangle count k4_node Node 4-cycle count k5_node Node 5-cycle count k3_graph Graph triangle count k4_graph Graph 4-cycle count k5_graph Graph 5-cycle count k6_graph Graph 6-cycle count n_comp Number of connected components nonLCC Indicator for nodes outside the largest connected component eigvec1 First nontrivial Laplacian eigenvector eigvec2 Second nontrivial Laplacian eigenvector eigval1 First nonzero Laplacian eigenvalue eigval2 Second nonzero Laplacian eigenvalue eigval3 Third nonzero Laplacian eigenvalue eigval4 Fourth nonzero Laplacian eigenvalue eigval5 Fifth nonzero Laplacian eigenvalue n/max_n Normalized graph size (n/nmaxn/n_ ) Appendix 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.

Instant research discovery