Research map / Graph learning / Graph self-supervised learning

DiPhon: Diffusion on Graphons for Scalable Graph Generation

NeurIPS 2026 · Graph learning › Graph self-supervised learning · approach: Diffusion-based graph generation · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes DiPhon, a graph diffusion model that runs a Jacobi SDE on cell-discretized graphons, matching first moments exactly and second moments up to a closed-form gap, and trains on small graphs to generate larger ones without retraining.

Problem

Diffusion-based graph generators do not scale to larger graph sizes, and it is unclear whether a model trained on small graphs can generate larger graphs without retraining; discrete and Gaussian diffusions do not admit a natural graphon formulation.

Approach

Defines a Jacobi (Wright-Fisher-type) SDE pointwise on the graphon, keeping edge probabilities in [0,1]; discretizes into cell averages with per-cell Jacobi diffusions whose parameters are renormalized by N^2 so the first moment matches exactly and the second moment gap is closed-form; reverse process uses a Jacobi conditional score with a GNN denoiser estimating the initial edge probabilities.

Key results

• Forward simulation on a two-community SBM (N=20, 100) matches the closed-form first moment exactly under deterministic and Bernoulli initializations.
• DiPhon trained on small graphs keeps high validity accuracy on SBM, PA, and tree graphs up to 300 nodes, while discrete diffusion baselines (DiGress, DeFoG) collapse at larger sizes.
• Gaussian baseline GruM is more stable than discrete baselines on SBMs but performs poorly on tree graphs.

Surprising findings

• Gaussian diffusion GruM is more stable at large sizes than discrete diffusion methods on SBM graphs, but poor on trees.
• The method works on tree graphs (sparse, outside the dense graphon regime) even though the theory does not formally cover them.

Limitations

• Theory developed only in the dense regime; formal guarantees do not fully explain sparse-graph behavior.
• Equivalence to the discrete graphon process holds only for the first two moments, not full distributional distance.
• Training requires simulating forward trajectories since the renormalized Jacobi transition has no tractable closed-form density, adding overhead.

Experimental setup

Datasets: synthetic SBM graphs synthetic preferential attachment graphs synthetic tree graphs

Benchmarks: SBM validity PA validity tree forest accuracy

Metrics: fraction of valid graphs (forest accuracy, fitted block-mode first and second moments of Jacobi process

Baselines: DiGress DeFoG GDSS GruM

Builds on: DiGress GDSS Jacobi diffusion graphon theory graph transformer with relative random walk features

Closest papers by meaning

• Graph Generation with Diffusion Mixture (ICML 2024 · similarity 0.89)
• Discrete-state Continuous-time Diffusion for Graph Generation (NeurIPS 2024 · similarity 0.88)
• Advancing Graph Generation through Beta Diffusion (ICLR 2025 · similarity 0.88)
• Generative Modelling of Structurally Constrained Graphs (NeurIPS 2024 · similarity 0.88)
• SBGD: Improving Graph Diffusion Generative Model via Stochastic Block Diffusion (ICML 2025 · similarity 0.87)
• Pard: Permutation-Invariant Autoregressive Diffusion for Graph Generation (NeurIPS 2024 · similarity 0.87)