Efficient and Degree-Guided Graph Generation via Discrete Diffusion Modeling

1. Introduction

• Existing deep large-graph generators such as NetGAN and CELL cannot reproduce some important statistics without memorizing training graphs.The cited limitation also applies to other edge-independent models, including VGAE and GraphVAE.Source: §1 · p. 1
• Diffusion models generate edges through multiple dependent steps and are permutation-invariant, but prior versions were designed for graphs usually smaller than one hundred nodes.These properties distinguish them from one-shot and autoregressive approaches described in the introduction.Source: §1 · p. 1
• Diffusion models incur O(TN^2) pairwise computation and face greater difficulty capturing global statistics as graph sizes increase.Their performance degrades as training graphs scale up.Source: §1 · p. 1
• EDGE uses a discrete diffusion process converging to the empty graph, encouraging sparsity during generation.This edge-removal design reduces message-passing computation because the MPNN runtime is linear in the number of edges.Source: §1 · pp. 1–2
• EDGE predicts edges only for active nodes, reducing the number of MPNN predictions while retaining the forward transition probabilities.Active nodes are those whose edges change in the original edge-removal process.Source: §1 · p. 2
• EDGE explicitly models node degrees, and the paper reports efficient generation of large graphs with desired statistics.The introduction presents degree modeling as improving the match between generated-graph statistics and training-graph statistics.Source: §1 · p. 2

2. Background

• A discrete diffusion process corrupts data graph A0 over T steps into a trajectory, whose terminal distribution approaches a simple convergent distribution as T grows.The trajectory after A0 is treated as latent variables.Source: §2 · p. 2
• The generative model learns reverse transitions pθ(At−1|At) and defines a graph-data distribution through its marginal pθ(A0).The reverse model is trained to match the forward posterior by maximizing a variational lower bound.Source: §2 · p. 2
• The forward process can independently resample edge entries using Bernoulli probabilities, with a noise schedule making the terminal graph approximately G(N, p).The diffusion rate determines resampling probability, and the schedule is chosen so the terminal state is nearly independent of A0.Source: §2 · p. 2
• The forward marginal allows sampling At directly from A0 at any time step, and its posterior conditioned on A0 can be computed analytically.The text presents these as properties needed for model fitting.Source: §2 · p. 2
• During generation, sampling starts from the terminal distribution and iteratively denoises to produce an A0 adjacency matrix.The terminal distribution is the convergent distribution of the forward process.Source: §2 · p. 2

3.1. Diffuse graphs to empty graphs – a motivation

• Setting p = 0 makes the forward process remove edges toward an empty graph, reducing message-passing work because MPNN runtime is linear in the input graph’s edge count.The method also analyzes output prediction costs and observes that only a small fraction of nodes are active in this process.Source: §3.1 · p. 3

3.2. A diffusion-based model that explicitly models active nodes

• EDGE treats degree changes as latent active-node indicators and predicts edges only between selected active nodes, carrying edges incident to inactive nodes across the reverse step.The reverse process first predicts active nodes, then samples the preceding graph conditional on those nodes.Source: §3.2 · pp. 3–4

3.3. Learning the reverse process

• The reverse-process objective includes reconstruction, edge-prediction, and node-selection terms; edge prediction uses Monte Carlo cross-entropy because its posterior lacks a closed form.The authors leave variance reduction for future work.Source: §3.3 · p. 4

3.4. Degree-guided graph generation

• EDGE models the original degree sequence as a random variable, samples degrees, then generates a graph conditioned on them; specified degrees can accurately control generated degrees.The degree constraint chiefly affects node selection, and the authors reason that it reduces possible graph trajectories and modeling complexity.Source: §3.4 · pp. 4–5

3.5. Implementation

• The implementation shares an MPNN for node classification and link prediction, while fitting degree sequences with an RNN for multi-graph datasets or using the observed degrees for a single graph.Generation starts from an empty graph, samples a degree sequence, and iteratively samples active nodes and preceding graphs.Source: §3.5 · p. 5

3.6. Model analysis

• With linear noise scheduling, active nodes are at least ten times fewer than all nodes, reducing edge predictions relative to prior diffusion models that predict for all node pairs.Per step, EDGE computes node representations, predicts active nodes, and predicts links among them; prior diffusion models require O(N^2) link predictions per step.Source: §3.1 · p. 3, §3.6 · p. 5
• EDGE generates graphs iteratively, so it is not edge-independent and avoids the theoretical limitation attributed to one-shot edge-independent models.Its ability may still be affected by the underlying MPNN’s capacity to distinguish graph structures.Source: §3.6 · p. 5

• Edge-independent models, including ER, SBM, neural auto-encoders, and NetGAN variants, have been reported unable to reproduce statistics such as triangle counts and clustering coefficients.The cited work identifies this limitation for target-network statistics.Source: §4 · p. 6
• Deep autoregressive models generate graphs by sequentially filling adjacency matrices, requiring N^2 predictions and facing long-term-memory and node-order invariance challenges.Sparsity-based prediction of nonzero entries is one proposed approach to reducing their prediction burden.Source: §4 · p. 6
• Diffusion models generate graphs through multiple steps that capture edge correlations, but prior work focused on small-graph generation tasks.The passage contrasts them with one-shot models that directly predict an adjacency matrix and autoregressive graph models.Source: §4 · p. 6

5. Experiments

• Experiments assess whether generated graphs match training-graph statistics and whether they can be sampled efficiently.Source: §5 · p. 6

5.1. Experimental setup

• The study includes Community and Ego graphs, four real-world networks with thousands of nodes, and QM9; baselines vary by task and model family.Generic-graph evaluation uses structural and neural metrics; large-network evaluation compares graph statistics and edge overlap, while QM9 evaluation includes molecular-generation metrics.Source: §5.1 · pp. 6–7

5.2. Evaluation of sample quality

• EDGE outperforms baselines on 8 of 10 generic-graph metrics and is only slightly worse on the other two.The evaluation covers Community and Ego; the authors hypothesize degree modeling helps because degrees inform graph structure.Source: §5.2 · p. 7, Table 2 · p. 7
• EDGE shows superior performance across all four large networks, with clear improvements on Polblogs and PPI and lower edge overlap on Road-Minnesota and Cora.On Road-Minnesota, statistics are similar to edge-independent models; on Cora, EDGE slightly improves over them.Source: §5.2 · p. 7, Table 3 · p. 8

5.3. Efficiency

• 0.5s slower than GraphCNF on Community, EDGE has a clear sampling-time advantage on large graphs.Figure 3 compares sampling time across models and graph sizes; EDGE's computation scales with edge count, and Ego graphs are often sparser than Community graphs.Source: Figure 3 · p. 7, §5.3 · p. 7

5.4. Generative performance on QM9 dataset

• On QM9, extended EDGE performs comparably to DiGress and runs much faster.The extension uses a hierarchical generation process to sample node attributes.Source: §5.4 · p. 8, Table 4 · p. 8

5.5. Ablation studies

• The G(N, 0.5) convergence variant could not be trained because it required excessive GPU memory; active-node modeling improved sampling speed, and degree guidance improved generation performance.Source: §5.5 · p. 8, Table 5 · p. 8
• Large T does not always improve performance: T = 64 is best for Cora and Road-Minnesota, while denser Polblogs and PPI require T = 128 and T = 256, respectively.For sparse graphs, large T can leave few active nodes per step and create an imbalanced classification problem; beyond the stated settings, further increases do not improve performance.Source: §5.5 · p. 9, Table 6 · p. 9

6. Conclusion

• EDGE is more efficient than benchmark methods and achieves superior graph-generation quality while scaling to graphs with thousands of nodes.Its generated graphs have statistics more similar to those of the training graphs.Source: §6 · p. 9

A.1. The G(N, 0) diffusion process

• The section derives forward and reverse transition distributions for the G(N, 0) process and examines degree changes in both directions.For p = 0, the forward process removes edges, and the reverse posterior has uncertainty when an edge could have been removed before timestep t.Source: A. Derivation of the G(N, 0) Diffusion… · p. 13, §A.1 · p. 13

A.2. The distribution of active nodes

• Each node’s degree evolves through binomial retention: each existing edge is kept with probability 1−β_t in a one-step transition.The forward degree distributions are derived from the edge-wise diffusion process.Source: §A.2 · p. 14
• The posterior degree distribution combines the current degree with uncertainty over which edges were removed to characterize the previous degree.The derivation treats the relevant edge variables as independent.Source: §A.2 · p. 14
• The reverse degree distribution supports degree guidance and shows that only part of the nodes may change degree at each transition.The paper uses the reverse degree-change distribution when learning the reverse process.Source: §A.2 · p. 14

B.1. Derivation of the objective L(A0; θ)

• The objective models latent graph states and active-node selections, with reconstruction, edge-prediction, and node-selection terms.Learning node selection from the current graph can be difficult because it requires capturing dynamic node interactions and global graph structure.Source: §B.1 · p. 15

B.2. Derivation of the objective L(A0, d0; θ)

• The degree-conditioned objective fits pθ(d0) to the empirical degree distribution and parameterizes node selection to make its KL term zero.The degree sequence is obtained from the original graph A0.Source: §B.2 · p. 16

C.1. Parameterization of the edge prediction distribution

• The edge-prediction network updates node features with message-passing blocks and predicts edges only for pairs selected as active.Initial node features use degree sequences d0 and d_t; the final edge parameter is computed from the two node embeddings.Source: §C.1 · pp. 16–17, Figure 5 · p. 17

C.2. Modeling the degree sequence distribution

• EDGE models a permutation-invariant degree histogram with an RNN, then samples the degree sequence from that model.For large-network generation, the method uses the training graph’s node degrees; degree-distribution modeling is used for generic graph generation.Source: §C.2 · pp. 17–18

C.3. Training

• Training estimates the edge-prediction gradient with Monte Carlo samples of diffusion states, timesteps, and active nodes.The procedure samples an original graph, draws consecutive noisy states, obtains the active-node variable, and updates the model from the edge-prediction log probability.Source: §C.3 · p. 18

D.1. Technical differences of existing diffusion-based graph models

• EDGE reduces generation complexity from the O(TN^2) required by current diffusion graph models to O(min(K^2, M)).Here K is the maximum number of active nodes and M is the number of graph edges.Source: §D.1 · p. 19, Table 7 · p. 19

E.1. Hierarchical generation

• Categorical attributed graphs are generated by sampling node attributes, then EDGE-conditioned graph structure, then edge attributes conditioned on both.The model represents node and edge attributes as one-hot vectors, with an extra edge-attribute category indicating whether an edge exists.Source: §E.1 · p. 19

E.2. Model Details

• For node attributes, the model uses a sequence-modeling approach similar to degree-sequence modeling, with sequence length Cnode.For graph structure, EDGE is conditioned on node features during training and generation.Source: §E.2 · p. 19
• Edge-attribute diffusion starts with random edge labels and iteratively refines labels using node features and graph structure, predicting only for edges already present.This restriction allows an MPNN to calculate edge features.Source: §E.2 · p. 19

F. Additional Details for Experimental Setups

• Experiments add no extra input features except current degrees dt and target degrees d0, and set p = 10^-12 for numerical stability.Table 8 lists the experimental hyperparameters.Source: F. Additional Details for Experimental… · pp. 19–20, Table 8 · p. 20

F.1. Generic graph generation

• Generic-graph experiments follow You et al. (2018) for Community and Ego data and reproduce baselines for evaluation under a common metric protocol.GraphCNF uses a smaller model for Ego because of GPU-memory limits, and DiGress is run without structural features.Source: §F.1 · p. 20

F.2. Large network generation

• Large-network experiments use one network as training data, omit validation and test sets, and generate samples from final-epoch models after network statistics converge.The models are trained for 30,000 iterations.Source: §F.2 · p. 20
• 15% EO on average for Poblogs results from degree-based node ordering, while random ordering yields an EO value almost 0.The degree-ascending permutation is applied to both generated and training graphs.Source: §F.2 · pp. 20–21

F.3. Computational Resources

• Training uses Tesla A100, V100, or QUADRO RTX 6000 GPUs with 32 CPU cores; generic tasks finish within 72 hours and large-network tasks within 24 hours.Sampling speeds are measured on a Tesla A100 GPU.Source: §F.3 · p. 21

G.1. Comparison between the node degrees from generated graphs and the node degrees d0

• Generated node degrees accurately approximate the specified degrees d0, with Figure 6 showing degree differences across datasets.The degree difference is the actual generated degree minus the given degree.Source: §G.1 · p. 21, Figure 6 · p. 21

G.2. Further justification the use of G(N, 0) as the convergent distribution

• G(N, 0) achieves better generative performance than G(N, 0.5) on Community-small, supporting its use as the convergent distribution.The authors describe G(N, 0) as an absorbing state.Source: §G.2 · pp. 21–22, Table 9 · p. 22

G.3. Full results on graph generation tasks

• The paper reports mean metrics and the standard derivation of metrics for generic graph generation and large network generation tasks in Tables 10 and 11, respectively.Source: §G.3 · p. 22

G.4. Visualizations

• Figures 7 and 8 visualize six generic test-data graphs and generated graphs for each dataset, with examples randomly selected; Figure 9 visualizes 16 QM9 molecules generated by GDSS, DiGress, and our approach.Source: §G.4 · p. 22, Figure 7 · p. 24, Figure 8 · p. 25