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

• Independent edge updates and exchangeability force an E-R terminal prior, whose fixed-point pathology constrains denoising and limits recovery of node heterogeneity and higher-order structure.Source: §1 · pp. 1–2
• Prior work often treats the problem as insufficient model expressivity and adds auxiliary node features, leaving the E-R prior's role unexamined.Source: §1 · p. 2
• The joint framework co-evolves latent variables and graph structure so node heterogeneity guides edge updates during both noising and denoising.Source: §1 · p. 2
• LSP conditions edge probabilities on positive node sociabilities, inducing heterogeneity and edge dependencies without requiring a pre-trained encoder.Source: §1 · p. 2
• Across multiple graph-generation benchmarks, the proposed framework more accurately captures target graph distributions than existing baselines without node features.Source: §1 · p. 2

• Continuous latent graph diffusion uses VAEs and Gaussian noise, but training instability, reconstruction errors, and latent-space dimensionality can hinder validity and large-graph detail.Source: §2 · p. 2
• Discrete diffusion corrupts edges directly and has improved graph generation [3] [40] [37] [47], while quadratic computational cost remains a practical concern.Source: §2 · p. 2
• In discrete diffusion, edge-independent corruption forces an E-R terminal prior, creating a fixed-point pathology that constrains generation quality independently of model capacity.Source: §2 · pp. 2–3
• Other prior approaches use embedding-based sources or motif-based priors outside discrete diffusion; motif specification and optimal transport can be costly, whereas LSP needs neither.Source: §2 · p. 3

• Graphs are represented by node-feature tensors and edge tensors, with each edge encoded as absent or present.Source: §3 · p. 3
• A denoiser receives the noisy graph and timestep, predicts edge-type probabilities, and is trained against clean edge states; the reverse distribution factorizes over edges when node features stay fixed.Source: §3 · p. 3
• The forward process independently perturbs each edge toward the empirical edge-type marginal, producing an E-R terminal prior at the end of diffusion.Source: §3 · pp. 3–4
• Exchangeability requires permutation-invariant graph probabilities, which follow when the prior is exchangeable and the denoiser is permutation equivariant.Source: §3 · p. 4

• Exchangeability plus independent edges makes the terminal prior necessarily E-R in discrete diffusion.Source: §4 · p. 4
• For large graphs, the analyzed GAT, GCN, and GIN denoisers produce approximately constant edge probabilities when node features have low standard deviation, making E-R graphs approximate fixed points.Source: §4 · p. 5
• The fixed-point behavior keeps node heterogeneity low through diffusion, so generated graphs remain nearly E-R-like and struggle to recover higher-order structure.Source: §4 · pp. 4–5
• The analysis argues that the result also applies to DiGress's Graph Transformer because its pairwise edge modulation does not introduce dependence between pairs.Source: §4 · p. 5
• A posteriori structural features such as subgraph counts do not solve the limiting problem for dense E-R graphs because their standard deviation also vanishes.Source: §4 · p. 5

5 Latent variable guided discrete diffusion

• The E-R prior follows from edge independence plus exchangeability, so the paper replaces it with a latent-variable prior and joint diffusion.E-R graphs become difficult to denoise in the large-graph limit.Source: §5 · pp. 5–6

5.1 Latent Sociability Prior (LSP)

• LSP assigns each node a positive sociability weight; edge probabilities depend on paired weights, yielding conditionally independent but marginally dependent edges while preserving exchangeability.A high-variance sociability distribution produces diverse connection propensities and higher-order structures.Source: §5.1 · p. 6

5.2 Joint diffusion with LSP

• The clean latent vector has an approximate closed-form estimate from node degrees, centered by the graph-level mean to capture relative degree heterogeneity.The estimate uses log(degree + δ) + μ, with δ as a small smoothing constant.Source: §5.2 · pp. 6–7
• The forward process jointly noises latent variables and edges, using pair-specific edge transitions parameterized by clean latents to keep forward posteriors tractable.The latent variables are reparameterized as unconstrained log-weights before Gaussian diffusion.Source: §5.2 · pp. 6–7
• During reverse sampling, the network predicts clean latents that condition edge updates, while training combines edge cross-entropy with latent-regression MSE.The reverse kernel separately updates continuous latents and discrete edges.Source: §5.2 · pp. 7–8

6 Experiments

• The experiments use CoraChameleon subgraphs at n ∈ {10, 20, 50, 100, 500}, alongside Ego and Community datasets.CoraChameleon contains 3000 graphs for sizes 10–100 and 1400 graphs at size 500.Source: §6 · p. 8

6.1 JointLSP preserves node heterogeneity at high noise

• At high noise, JointLSP preserves variation in node propensity scores, whereas DiGress scores collapse toward a common value.The comparison evaluates CoraChameleon-Node100 at diffusion steps t ∈ {500, 50, 0}.Source: §6.1 · p. 8, Figure 2 · p. 8

6.2 Experiments on graph generation

• Generated-graph evaluation reports MMD ratios for degree distribution, clustering coefficient, triangle count, assortativity, PLE, and CPL, with lower values better and r = 1 as baseline.PLE and CPL denote power-law exponent and characteristic path length.Source: §6.2 · p. 9
• JointLSP+DiGress beats DiGress with up to k = 10 structural features on clustering coefficient, triangle count, and assortativity, but spectral features perform better and are expensive to compute.Even k = 10 structural features remain insufficient on triangle count and assortativity.Source: §6.2 · p. 9
• JointLSP+DiGress consistently improves triangle count and assortativity over feature-free DiGress; at n = 100, DiGress does better on degree distribution and PLE.The authors state that the comparison isolates the unconditional setting without node features and do not claim state-of-the-art performance.Source: §6.2 · p. 9

7 Conclusion

• LSP co-diffuses sociability variables and graph edges, preserving node heterogeneity to recover higher-order structure without auxiliary structural features; benchmarks span multiple graph sizes.The framework is most suited to graphs with absent or limited node features; for molecular generation with rich semantic features, its benefit is expected to be minimal.Source: §7 · pp. 9–10
• Combining LSP with auxiliary node features remains non-trivial because LSP is already informative at high noise levels, so added features are not guaranteed to compound its benefits.The conclusion suggests designing complementary features and identifies per-step spectral-feature computation as expensive.Source: §7 · p. 10

A.1 Constructing the Latent Sociability Prior

• Prior parameters are calibrated from training data to match empirical edge density and degree heterogeneity.The procedure estimates sociability variability from centered log-degrees and calibrates the mean by matching expected edge probability to empirical density.Source: §A.1 · pp. 15–16

A.2 Shifted and scaled DDPM for latent sociability variables

• Latent sociability variables diffuse toward a Gaussian prior with mean µLSP and variance σ2_LSP, and reverse updates use the network's predicted clean sociability values.The forward process is shifted and scaled to this prior rather than the standard N(0, I) target.Source: §A.2 · pp. 16–17

B.1 Proof of Lemma 4.1

• The adjacency matrix A has edge-probability matrix P equal to its expectation.The proof treats edges as independent Bernoulli variables with parameters p_ij.Source: §B.1 · p. 17
• Exchangeability makes the distribution of A invariant under conjugation by any node-permutation matrix.This invariance carries over to the expected adjacency matrix.Source: §B.1 · p. 17
• Permutation invariance forces constant off-diagonal probabilities, so the model is Erdős–Rényi.The diagonal is zero for simple graphs.Source: §B.1 · p. 18

B.2 Proof of Thm. 4.2

• The proof considers GNN layers with message-passing matrices that can depend on graph structure and, for attention models, on layer inputs.The link function is assumed Lipschitz in each component, and activations are assumed 1-Lipschitz.Source: §B.2 · p. 18
• The analyzed architectures use specific conditions: GIN is normalized by expected graph density, GAT uses bounded-positive attention coefficients, and GCN uses a symmetric normalized Laplacian.The GIN normalization is chosen to avoid divergence as graph size increases.Source: §B.2 · pp. 18, 21

B.3 Proof of Lemma 4.3

• For the graph feature Ci, the proof applies McDiarmid’s inequality and a union bound to establish concentration around its expectation with high probability.The stated deviation bound scales with log(1/δ)/n.Source: §B.3 · p. 22

C Variational motivation for the training objective

• The objective is not an exact ELBO for the sampling model because training and sampling terminal distributions coincide only in expectation over u0.The training terminal is conditioned on u0, whereas sampling draws uT from the LSP prior.Source: C Variational motivation for the… · p. 22
• The joint state comprises sociability variables and edges, and the forward process factorizes because the two components are corrupted independently.The continuous and discrete components follow shifted-scaled Gaussian diffusion and pair-specific edge marginals, respectively.Source: C Variational motivation for the… · pp. 22–23
• The simplified training objective replaces per-step KL terms with cross-entropy and MSE losses and drops prior KL terms that vanish for the u0-keyed forward process.The paper presents this as a practical objective rather than optimizing the ELBO term by term.Source: C Variational motivation for the… · pp. 22–23

D.1 DiGress on Tree dataset

• On Tree, the proposed method outperforms DiGress on 3 of 4 metrics.Table 3 reports results on the Tree dataset.Source: §D.1 · p. 23, Table 3 · p. 24

D.2 Graph generation using JointLSP+SparseDiff

• JointLSP+SparseDiff consistently improves over SparseDiff on most CoraChameleon metrics across n = 10, 20, 50, 100, and 500, especially triangle count and assortativity.The improvement holds at n = 500, where the fixed-point pathology is most severe.Source: §D.2 · p. 24, Table 4 · p. 24
• On Ego and Community, JointLSP+SparseDiff improves over SparseDiff on all metrics except clustering on Ego and assortativity on Community.Both datasets remain challenging, with uniformly large MMD ratios; the authors cite self-loops in Ego and missing auxiliary spectral features for community structure as likely contributors.Source: §D.2 · p. 24, Table 5 · p. 24

D.3 DiGress with degree features

• JointLSP+DiGress maintains node heterogeneity throughout the reverse trajectory, whereas DiGress+Degree builds heterogeneity only as denoising progresses.At t = T, the LSP prior already induces diverse connection propensities; degree features are reactive and provide structural signal only once the graph is partially denoised.Source: §D.3 · p. 25, Figure 3 · p. 25, Table 6 · p. 25

D.4 LSP improves generation quality throughout diffusion trajectory

• JointLSP+DiGress achieves lower MMD ratios than DiGress at all evaluated timesteps for all three structural statistics except Degree, with an advantage already at t = 500.The comparison uses predicted clean edge probabilities to construct graphs; the authors surmise LSP over-corrects degree when inducing node heterogeneity.Source: §D.4 · p. 26, Figure 4 · p. 26

D.5 LSP induces node heterogeneity

• As n approaches 1000, LSP has dispersion index φ > 1, while dense and sparse Bernoulli baselines approach φ ≈ 1.The index measures within-graph degree variation relative to its mean.Source: §D.5 · p. 27, Figure 5 · p. 27

D.6 LSP can generate higher triangle and cycle counts

• At fixed mean degree, LSP produces substantially larger triangle, 4-cycle, and 4-clique counts than a sparse mean-field Bernoulli prior as graph size increases.The matched mean-degree setup shows the difference is not simply due to denser graphs.Source: §D.6 · p. 27, Figure 6 · p. 28

D.7 Structural features are uninformative for E-R graphs

• As graph size grows, normalized per-node triangle-count spread vanishes under E-R but remains stably non-trivial under LSP.The experiment samples directly from the terminal priors, without a diffusion process, to isolate their effect on structural-feature statistics.Source: §D.7 · p. 28, Figure 7 · p. 28

E Dataset generation

• CoraChameleon is constructed by sampling subgraphs from Cora and Chameleon using random-walk, forest-fire, and dense-core strategies.The strategy mix is 40% random walk, 40% forest-fire, and 20% dense core; generated subgraphs are checked for connectivity and minimum average degree.Source: E Dataset generation · p. 28

E.1 Training details

• Experiments use a Graph Transformer denoiser and report mean and standard deviation over three inference runs with different random seeds for each trained configuration.The experiments ran on a single A40 GPU; the paper notes that repeated independent training runs and auxiliary spectral-feature computation can be computationally costly.Source: §E.1 · pp. 29–30

F Broader impact

• The paper notes that realistic graph generation could be misused, while stating that these risks are not specific to its contribution.The stated contribution addresses a theoretical limitation in discrete graph diffusion and proposes a framework for the no-node-feature setting.Source: F Broader impact · p. 30