Discrete Diffusion for Large Graph Generation via Structural Candidate Restriction

1 Introduction

• The method targets representative large-graph generation when real-world data are incomplete, sensitive, or costly to obtain.It aims to match structural statistics without memorizing training graphs.Source: §1 · pp. 1–2
• A degree-aware masking schedule keeps noisy graphs structurally informative throughout the reverse process.The schedule reveals node pairs according to node degree.Source: §1 · p. 2
• Training on edges, wedge non-edges, and a small random coverage set reduces cost from O(N^2) to O(Nµ2) under chosen conditions.The restricted objective is an unbiased estimator of the full-pair objective with improved signal-to-noise.Source: §1 · p. 2
• Across datasets, the model achieves consistently strong large-graph structural fidelity relative to other diffusion models.Small-graph generation is not the primary objective, though performance there is described as reasonable.Source: §1 · p. 2

2 Related work

• Classical models fit fixed probabilistic forms to observed statistics, while ERGM permits edge dependence but requires MCMC for fitting and sampling because its normalizing constant is intractable.The paper adopts Chung–Lu degree-based edge probabilities as a terminal distribution.Source: §2 · p. 2
• Autoregressive methods can incur O(N^2) cost; BiGG instead achieves O((N + m) log N), while K2-tree generation retains quadratic encoding and decoding costs.The latter shifts quadratic cost to preprocessing and postprocessing rather than eliminating it.Source: §2 · p. 2
• Discrete diffusion can trend toward dense intermediate graphs under dense resampling marginals, whereas deletion-only absorbing processes do not increase graph density.Regardless of process type, training on mostly absent pairs can degrade signal-to-noise.Source: §2 · pp. 2–3
• EDGE restricts prediction to K active nodes but has O(max(m, K^2)) attention cost and an empty-graph stationary distribution; SparseDiff has O(m) training cost but sampling still covers all pairs.These methods restrict computation in different parts of the denoising process.Source: §2 · p. 3
• ARROW-Diff diffuses sampled random walks but lacks formal convergence guarantees, while GraphMaker assumes rich node features that may not be available.GraphMaker uses decoupled, asynchronous mini-batch training of structure and features.Source: §2 · p. 3

3 Preliminaries and Background

• A graph is represented as G = (V, E, X, Y), with one-hot node and edge attributes; without edge types, Y is the binary adjacency matrix.In that setting, Aij = 1 exactly when an edge exists between nodes i and j.Source: §3 · p. 3
• Graph diffusion corrupts a clean graph G0 through forward transitions and trains a denoiser to reverse the process from GT to G0.The discrete formulation uses cumulative transition matrices for node and edge attributes.Source: §3 · p. 3
• A common transition preserves the current state with probability αt and resamples from marginal p otherwise.The transition is parameterized as Qt = αtI + (1 − αt)1p⊤.Source: §3 · p. 3

4 Method

• Training uses a candidate set of observed edges and pairs with common neighbors, plus random non-edge coverage, yielding |Qt| = O(Nµ2) when µ2 is the degree-sequence second moment.The candidate-pair fraction is O(µ2/N), vanishing as N grows whenever µ2 = o(N); sampling still requires resolving all pairs at quadratic cost.Source: §4 · pp. 4, 7
• The denoiser conditions on common-neighbor count, a local closure statistic, and restricts diffusion to observed edges and pairs with positive common-neighbor count.Pairs without shared neighbors have a known zero value and add no further information through this feature.Source: §4 · p. 4
• The forward process fixes pairs outside Qt as non-edges and applies a partial absorbing process over {0, 1, M} to pairs inside Qt.M is a mask token.Source: §4 · p. 4
• A floored cosine schedule keeps the noisy graph sparse and non-empty, while degree-aware masking masks high-degree pairs faster than low-degree pairs.This gives the denoiser more reverse-process steps to recover low-degree connectivity than a uniform masking rate would.Source: §4 · p. 5
• The predictor uses a sparse graph encoder to pass messages over visible edges, then independently predicts each queried pair; target degree is a permanent node-conditioning feature.Pairs outside Qt are not queried during training and remain fixed non-edges.Source: §4 · p. 5
• Randomly sampled non-edges receive a Horvitz–Thompson correction, while deterministic wedge non-edges are rescaled, yielding an unbiased estimator of the full ELBO.Time-dependent edge-presence weighting additionally addresses the edge/non-edge imbalance.Source: §4 · pp. 6–7
• Candidate restriction improves unweighted class-mass SNR from Θ(m/N^2) to Θ(m/Nµ2) at fixed masking fraction, and class reweighting balances the remaining classes.Together, the stated improvement over an unweighted dense-pool baseline is Θ(N^2/m), with larger gains for sparser graphs; the coverage term preserves unbiasedness.Source: §4 · p. 8

5.1 Datasets and metrics

• Across citation and financial networks, evaluation compares local and global structural statistics and checks edge overlap to assess fidelity without instance memorization.Smaller datasets also use uniqueness and novelty; baselines are efficient large-graph models, excluding runs that fail from out-of-memory errors.Source: §5.1 · p. 8
• On all six datasets, the model is closest or tied-closest to ground truth on EO, PLE, CPL, and CC; assortativity is uneven across datasets.For CC, it is closest or second-closest on all six datasets; the authors describe the connection to wedge completion and Ltri as suggestive, not established.Source: Table 2 · p. 9, §5.1 · p. 9

5.2 Ablation study

• On Alpha, replacing the degree-based Chung–Lu prior with ER or SBM worsens clustering-coefficient error by 5× to 6×; SBM remains competitive on Polblogs.Polblogs' binary ideological communities explicitly fit the block-model prior; the authors conclude that matching the prior to the degree schedule is essential.Source: §5.2 · pp. 9–10
• Removing Ldeg worsens CC error by 2–4×, while removing Ltri nearly doubles AC error on Cora and Polblogs; PLE changes by at most 0.02 under either ablation.The authors attribute the CC sensitivity to degree normalization and report that the forward schedule anchors the global degree distribution while the losses provide localized corrections.Source: §5.2 · p. 10
• At 50% of the training schedule, inference steps cut sampling time in half with negligible metric degradation; performance drops noticeably only at 10%.The reverse posterior permits skipped steps without modifying the sampling procedure.Source: §5.2 · p. 10

6 Conclusion

• Training on a structurally motivated pair subset plus a small random coverage sample yields an unbiased objective with sub-quadratic complexity in node count.A degree-aware forward process keeps noisy graphs informative, while dynamic common-neighbor features condition the denoiser on local structure at every noise level.Source: §6 · p. 10
• Across datasets of varying size and domain, the method achieves best-or-second-best structural fidelity on large graphs without memorizing training graphs.On small graphs, it remains comparable to baselines designed specifically for small or molecular graphs.Source: §6 · p. 10

Pre-computation

• Training precomputes the candidate set Q, graph statistics, masking exponents, weights, Chung–Lu parameters, and a cached prior term.The candidate set is the union of observed edges and wedge non-edges.Source: A Training and Sampling Algorithms · p. 15

Training

• Each training iteration samples time t and a coverage set, then trains the sparse encoder and pairwise decoder on Qt = Q ∪ St.The encoder’s message passing is restricted to visible edges; the decoder scores candidate pairs using node embeddings and τ values.Source: A Training and Sampling Algorithms · p. 15

Sampling

• Sampling fixes a training graph’s size and degree sequence as an expected target, initializes from a partial-absorbing Chung–Lu prior, and follows a decreasing reverse-step sequence.The prior draws pairs independently; their visibility probability matches the forward marginal at t = T.Source: A Training and Sampling Algorithms · p. 15
• At each reverse step, masked pairs are revealed probabilistically while visible pairs retain their state, and the final step decodes all remaining masked pairs.Sampling scores all pairs in chunks because a query set derived from visible edges could miss hub pairs that are likely masked and lack visible neighbors early in the chain.Source: A Training and Sampling Algorithms · p. 15

Complexity

• Training evaluates a sub-quadratic O(Nµ2) fraction of node pairs, but sampling must resolve every pair and therefore costs O(N2) per reverse step.The sampling-time cost is a limitation relative to dense diffusion baselines.Source: B Analysis and Discussions · pp. 15–16, Table 4 · p. 17
• Unlike EDGE’s schedule-dependent O(max(m, K2)) training bound, O(Nµ2) is guaranteed by graph structure; EDGE may retain subquadratic sampling through its active-node restriction.EDGE’s forward process converges to an empty graph, enabling monotonic reverse growth; this method’s partial absorbing prior avoids a fully erased state but forfeits that restriction.Source: B Analysis and Discussions · p. 16

Degree heterogeneity

• Wedge enumeration makes cost depend on degree heterogeneity: O(Nµ2) reduces to O(m) when the degree second moment matches the mean-degree order.A bounded maximum degree is sufficient for that condition.Source: B Analysis and Discussions · p. 16
• A star graph has m = N − 1 edges but O(N2) wedges, so sparsity alone does not ensure O(m) cost; the analysis reports O(Nµ2).This tracks the structural complexity driving deterministic wedge enumeration.Source: B Analysis and Discussions · p. 17

Choice of λS

• The coverage-sample size is fixed at O(Nµ2) by construction, and its dataset-specific constant c is chosen for memory safety rather than generation quality.The constant is set as large as possible while keeping the realized per-step tensor footprint within a fixed memory budget.Source: B Analysis and Discussions · pp. 17–18

Coverage bound

• The candidate-pair fraction tends to zero as N grows precisely when µ2 = O(N), according to the coverage bound.The bound concerns the training candidate set formed from edges, wedges, and the sampled coverage set.Source: B Analysis and Discussions · pp. 18–19

ELBO analysis

• The reweighted ELBO is an unbiased estimator of the full-graph loss with respect to randomness in the sampled coverage set.The edge and wedge terms are deterministic given the graph, while the coverage term uses a correction for sampling.Source: B Analysis and Discussions · pp. 19–20
• Weighting the wedge term by 1/λ can produce Θ(N2) bias, which is not negligible unless average wedge loss is asymptotically smaller than typical non-wedge non-edge loss.In the subquadratic-coverage regime, λ tends to zero and the bias can be of the same order as the full-graph loss.Source: B Analysis and Discussions · pp. 20–21

• The reweighted SNR is exactly 1, and its total gain over an unweighted dense-pool ELBO scales as the inverse graph density.Thus, the SNR gain is larger for sparser graphs, the regime motivating the work.Source: B Analysis and Discussions · p. 22

B.1 Practical analysis

• The masking analysis uses closed-form expectations over each dataset’s true graph, not model training or sampling, and compares degree-aware masking with a uniform baseline.Its retention curves are computed over the full graph rather than the restricted training-time candidate pool.Source: §B.1 · pp. 22, 24
• Hub–hub edges have higher masking rates than leaf–leaf edges: 2.14 vs. 0.68 for Cora and 2.68 vs. 0.64 for Polblogs.By the midpoint, hub–hub edge survival is 0.18 for Polblogs and 0.27 for Cora, while leaf–leaf survival remains 0.64–0.67; uniform masking yields 0.517 across edge types.Source: §B.1 · p. 22
• At the schedule midpoint, triangle survival falls 3–16× lower under degree-aware masking than uniform masking, and the triangle-intact half-life drops from 0.31 to 0.19–0.22.The half-life is the point in t/T when the fraction of triangles whose three edges remain unmasked first drops below one half.Source: §B.1 · pp. 22–23
• At the midpoint, degree-aware masking distorts the degree distribution 1.23× more for Cora and 1.46× more for Polblogs than uniform masking.Different resolution times for hub and leaf edges produce a mixture of early-resolved leaf edges and late-resolved hub edges.Source: §B.1 · p. 23
• Degree-aware masking reduces masked-edge class imbalance relative to uniform masking by 0.69× for Cora, 0.67× for Citeseer, and 0.41× for Polblogs.The reduction grows with degree heterogeneity, but does not eliminate the sparsity-driven imbalance; it lightens the correction required from reweighting.Source: §B.1 · p. 24

C Extended Results

• The model achieves the best clustering-coefficient recovery among compared methods, although it underrepresents the high-degree tail on larger datasets.Its generated degree distributions closely track training distributions across most of the degree range.Source: C Extended Results · p. 25

C.1 Results on Small Graphs

• On ZINC, the model achieves the best performance on all reported metrics except orbits and validity; validity measures structural, not chemical, validity.The model is also comparable to methods designed specifically for small graphs, most of which do not scale to the paper’s large-graph setting.Source: §C.1 · p. 25

C.2 Empirical sampling time

• For graphs with more than 10k nodes, the model generates in under 110 seconds, while EDGE and GraphMaker require approximately 200 seconds.ARROW-Diff is comparably fast at this scale but has substantially higher edge overlap; the model combines comparable sampling time with low edge overlap and recovery of other structural statistics.Source: §C.2 · pp. 25–26

C.3 Efficiency of sampling: reduced diffusion steps

• Generation quality is largely preserved down to T≈50%, while sampling time decreases roughly in proportion to T; degradation becomes pronounced at T=10%.The 10% reduction is more severe for Cora trained with Ttrain=64 than for Citeseer and Polblogs trained with Ttrain=512.Source: §C.3 · p. 27
• Across all six ablation datasets, reduced-step sampling preserves quality substantially better under degree-adaptive masking than under uniform masking.The authors offer the schedule’s degree-correlated temporal separation as an explanation consistent with reveal-order data, not an independently verified mechanism.Source: §C.3 · pp. 27, 29
• Hub–hub edges (95th percentile) resolve later in every one of six datasets (Cora, CiteSeer, PubMed, Polblogs, Bitcoin Alpha, and Bitcoin OTC) at 50.6–57.7% of the reverse trajectory.The gap is 10.2–13.0 percentage points in Cora, CiteSeer, and PubMed, versus 3.9–4.7 points in Polblogs and the two Bitcoin networks. In Bitcoin Alpha and OTC, βmax=1.0 is numerically identical to the uniform baseline βij=1.Source: §C.3 · p. 29

C.4 Effect of the prior scaffold.

• With the masking schedule held fixed, the Chung–Lu prior is best suited to it in most cases because both are governed by node degree.On Alpha, ER and SBM overestimate clustering by 7–8×; on Polblogs, SBM edges out SCR on three metrics, consistent with its community structure aligning with the SBM bias.Source: §C.4 · p. 30

C.5 Effect of the regularizers.

• The full model is best or tied-best in 10 of 12 dataset-metric cells; removing Ldeg worsens clustering recovery, while removing Ltri worsens assortativity.The Bitcoin-Alpha exception is that adding Ldeg degrades AC from |∆| 0.12 to 0.27; the authors report this as observed rather than a fully diagnosed mechanism.Source: §C.5 · p. 31

D Implementation Details

• The GIN-style message-passing backbone weights neighbor messages by current-step edge probabilities, while node embeddings combine target degree and current noisy-state degree.The model uses 3–6 message-passing layers and embedding dimensions of 32 or 64, with dataset-specific settings.Source: D Implementation Details · p. 32
• Candidate-edge decoding combines endpoint embeddings with a triangle feature counting common currently revealed neighbors; training-only node-level regression predicts target degree and triangle count.A 4-head self-attention block processes the source, target, and edge-context tokens, followed by FiLM conditioning on the raw edge context.Source: D Implementation Details · p. 32
• Training uses Adam, global-norm gradient clipping at 1.0, and dropout 0.1; runs are statistically but not bit-exactly reproducible across re-execution.CUDA-deterministic algorithms are not enabled.Source: D Implementation Details · p. 32

E Datasets

• Single-graph datasets are converted to undirected graphs, stripped of self-loops, and reduced to their largest connected component before evaluation.The evaluated single graphs include citation networks, political-blog links, and Bitcoin trust networks; signs and weights are discarded for the Bitcoin datasets.Source: E Datasets · pp. 32–33
• The graph collections cover synthetic Community and Citeseer-derived Ego networks, while ZINC graphs are reduced to binary topology by discarding atom features and collapsing bond types.ZINC uses 10,000 training, 1,000 validation, and 1,000 test graphs; its graphs have 9–37 nodes and mean degree about 2.15.Source: E Datasets · pp. 33–34

Edge Overlap

• Edge Overlap (EO) measures recovered ground-truth edges; lower EO is preferred because memorizing the training graph yields 100 while a novel valid graph is near 0.EO is defined as the fraction of ground-truth edges recovered.Source: §E.1 · p. 34

Graph statistics

• PLE is estimated by maximum likelihood with fixed xmin = 1, while CPL is mean shortest-path distance over reachable pairs and is sampled for graphs with N > 2000.For larger graphs, CPL uses breadth-first search from 500 uniformly sampled sources.Source: §E.1 · pp. 34–35
• Global clustering is the ratio of closed to all length-two paths, and degree assortativity is the Pearson correlation of endpoint degrees across edges.Positive assortativity indicates hubs connect to hubs; negative values indicate hubs connect to low-degree nodes.Source: §E.1 · p. 35

Histogram-based variants

• Histogram MMD includes local clustering-coefficient distributions, whereas the comparison-table CC metric is global transitivity.The clustering histogram uses 100 bins on [0, 1].Source: §E.1 · pp. 35–36

Molecular metrics

• Molecule validity checks connectedness and training-set-derived per-type maximum valence, while uniqueness uses topology-and-atom-type WL hashes and novelty is measured among unique outputs.Validity certifies valence-plausibility, not chemical realizability, because bond orders are not generated and RDKit sanitization is not performed.Source: §E.1 · pp. 35–36

Maximum Mean Discrepancy

• MMD compares generated and reference graph structural statistics with a biased V-statistic estimator, reported in four variants that differ in graph embedding and kernel.The variants include histogram-based kernels and NSPDK.Source: §E.1 · p. 36

Histogram-based variants

• Orbit MMD compares mean per-node counts of two 3-path orbits and the 4-cycle orbit, computed with ORCA.The orbit representation is a vector of mean 4-node orbit counts per node.Source: §E.1 · p. 36

NSPDK

• NSPDK compares explicit bounded-radius subgraph-pair features; on ZINC, atom-type labels make the kernel sensitive to local chemical composition as well as topology.It uses a linear inner-product kernel without a smoothing parameter.Source: §E.1 · p. 36