Technical Summary: DiPhon – Diffusion on Graphons for Scalable Graph Generation

1. Problem Statement

Diffusion models have established themselves as a leading paradigm for graph generation, particularly in domains like molecular design and neural architecture search. However, scaling these models to large graphs remains a fundamental challenge. Current approaches face two primary limitations:

1. Training and Deployment Costs: Diffusion models are computationally expensive to train and deploy when dealing with large-scale graphs.
2. Lack of Size Transferability: Even when trained on small graphs, it remains unclear whether the learned generative mechanisms can generalize to larger graph sizes without retraining.

Existing graph diffusion methods struggle to address this in the dense-graph setting. Discrete diffusion models operate on categorical edge variables, preventing a natural extension to the continuous spatial domain required by graphons. Conversely, Gaussian SDE-based approaches inject noise pointwise but produce unbounded trajectories, which cannot be directly interpreted as edge probabilities (which must lie in $[0, 1]$), making their connection to graphon theory implicit at best.

2. Methodology

The paper proposes DiPhon, a diffusion framework for size-scalable graph generation that leverages graphons—the size-agnostic limit objects of dense graph sequences. The methodology bridges the gap between continuous graphon dynamics and discrete graph generation through the following steps:

2.1 Forward Process: Graphon Diffusion via Jacobi SDE

The authors formulate a continuous diffusion process directly on the graphon space $W: [0, 1]^2 \to [0, 1]$. To ensure the process remains within the valid probability range $[0, 1]$, they adapt a Jacobi stochastic differential equation (SDE):
$$dW_t(x, y) = \kappa (\mu - W_t(x, y)) dt + \sigma \sqrt{W_t(x, y)(1 - W_t(x, y))} dB_t(x, y)$$
where $\mu \in (0, 1)$ is the stationary mean, $\kappa > 0$ is the pull rate, and $\sigma > 0$ is the noise strength. The diffusion term vanishes at the boundaries, keeping the process bounded.

2.2 Discretization: From Graphon to Graph

Since continuous graphons are not directly observable, the authors propose a discretize-then-diffuse strategy. They partition the unit square into $N^2$ cells and define a discrete process $\tilde{W}_t^{ij}$ for each cell.

• Renormalization: To ensure the discrete process matches the statistical properties of the continuous "diffuse-then-discretize" ideal, the parameters of the discrete SDE are renormalized. Specifically, the noise amplitude is scaled ($\tilde{\sigma}^2 = \sigma^2 N^2$) and the drift rate is adjusted ($\tilde{\kappa}$) to compensate for the discretization.
• Initial Condition: The process starts from an observed binary graph $A_0$, where each entry $A_0^{ij}$ is treated as a Bernoulli sample of the underlying graphon cell average.

2.3 Reverse Process and Learning

The reverse-time SDE is derived using the standard score-based formulation, requiring the marginal score $\nabla \log \tilde{p}_t$.

• Tractable Score: For the Jacobi process, the conditional score admits a closed-form expression involving shifted Jacobi polynomials and their derivatives.
• Denoising Objective: Since the true initial graphon entry is unobserved, the authors train a Graph Neural Network (GNN) $\Phi_\theta$ to predict the clean initial graph $A_0$ from the noisy state $\tilde{W}_t$. The network is trained via a binary cross-entropy loss (denoising objective).
• Sampling: During inference, the reverse SDE is integrated backward from the stationary distribution (Beta distribution) to $t=0$. The learned denoiser provides the necessary score estimate at each step, and the final state is converted to a binary graph via independent Bernoulli draws.

3. Key Contributions

The paper makes four primary contributions:

1. C1 (Formulation): A novel diffusion process for graphons based on Jacobi SDEs, from which DiPhon is derived by discretizing the underlying dynamics.
2. C2 (Moment Alignment): A theoretical characterization showing that the discrete DiPhon process matches the first moment of the continuous graphon process exactly. The second moment discrepancy is derived in closed form and is shown to be controlled by the in-cell variance and discretization factor, vanishing as the graph size increases.
3. C3 (Sampling & Limit): A sampling procedure that generates graphs from the model's marginal distributions. The authors prove that in the stationary regime, the generated graphs converge in homomorphism density to an Erdős–Rényi graphon, establishing a structural limit for the process.
4. C4 (Empirical Scalability): Empirical validation demonstrating that DiPhon can be trained on small graphs and successfully generate larger, out-of-distribution graphs without retraining, preserving core topological properties across various graph families.

4. Experimental Results

The authors evaluate DiPhon on three synthetic graph families: Stochastic Block Models (SBM), Preferential Attachment (PA) graphs, and Trees.

• Setup: Models are trained on small graphs (e.g., 40–80 nodes) and tested on progressively larger sizes (up to 300 nodes).
• Baselines: DiPhon is compared against discrete diffusion methods (DiGress, DeFoG) and Gaussian diffusion models (GDSS, GruM).
• Findings:
  • Moment Alignment: Experiments confirm that the empirical mean and variance of the discretized process align with the theoretical closed-form references derived from the continuous graphon theory.
  • Scalability: DiPhon maintains high accuracy across all datasets and node sizes. In contrast, discrete diffusion methods show performance collapse at larger sizes, and Gaussian baselines exhibit inconsistency, particularly on tree structures.
  • Robustness: Notably, DiPhon remains effective even on Tree graphs, a sparse regime where the formal graphon theory does not strictly apply, suggesting the method's empirical scope exceeds its theoretical guarantees.

5. Significance and Claims

The paper claims that DiPhon provides a principled route toward scalable graph generation by utilizing graphons as the carrier of diffusion dynamics.

• Size-Agnosticity: By operating in the graphon space, the model inherently learns a distribution that is independent of the number of nodes, enabling transfer from small training regimes to large inference regimes.
• Theoretical Grounding: The use of Jacobi SDEs ensures bounded edge probabilities and allows for a rigorous analysis of moment matching and convergence in homomorphism density, addressing limitations of previous Gaussian or discrete approaches.
• Practical Utility: The ability to generate large-scale graphs without retraining offers a significant advantage for applications requiring variable graph sizes, such as molecular design or network analysis.

The authors acknowledge limitations, noting that the theoretical guarantees are developed for dense graphs and rely on moment matching rather than bounding the full distributional distance. Additionally, the training process requires simulating forward trajectories, introducing overhead compared to models with tractable transition densities. However, the framework is presented as a foundation that can naturally extend to node features and weighted edges in future work.