Research map / Graph learning / Graph self-supervised learning
Generating Graphs via Spectral Diffusion
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 GGSD, a graph generative model that runs a DDPM-style diffusion over truncated Laplacian eigenvectors and eigenvalues, then recovers the adjacency matrix with a PPGN graph predictor.
Problem
Graph generation with diffusion models is bottlenecked by quadratic output size in the number of nodes, and existing spectral methods either condition on eigenvectors that are not generated or cannot condition on target spectra.
Approach
Diffuse over a truncated set of Laplacian eigenpairs (linear in node count, permutation-invariant transformer with cross-attention between eigenvectors and eigenvalues), then reconstruct the Laplacian and refine it with a PPGN predictor trained with reconstruction and adversarial losses; this also permits conditioning generation on target spectral properties.
Key results
- On Planar, GGSD reaches MMD degree 0.0007 and orbit 0.0047, and on SBM degree 0.0005 and clustering 0.0115, achieving best or second-best on most metrics.
- On Proteins, GGSD achieves the best MMD on all four statistics (e.g., degree 0.0014 vs SPECTRE 0.0082).
- On QM9 the VUN score is 0.847, the second-best among compared methods behind GDSS's 0.7257 being underlined, i.e. GGSD is reported as top in VUN (bold).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GGSD instead of SPECTRE | graph generation · Proteins | Deg. MMD: 0.0082$\pm$0.0021 -> 0.0014$\pm$0.0003 | Helped |
| Use GGSD instead of DiGress | graph generation · QM9 | V.& U.& N.: 0.3180 -> 0.847 | Helped |
| Use GGSD instead of DiGress | graph generation · Planar | Clus. MMD: 0.0178 -> 0.1881 | Hurt |
| Use GGSD instead of SPECTRE | graph generation · SBM | Deg. MMD: 0.0044 -> 0.0005 | Helped |
| Use GGSD instead of SPECTRE | graph generation · SBM | Spect. MMD: 0.0015 -> 0.0045 | Hurt |
| Omit the Graph Predictor and reconstruct from the complete generated spectrum (ablation) | GGSD on Community-small with full eigenpairs · Community-small | Deg. MMD: 0.00562 -> 0.00134 | Helped |
| Omit the Graph Predictor and reconstruct from the complete generated spectrum (ablation) | GGSD on Community-small with full eigenpairs · Community-small | Clus. MMD: 0.07887 -> 0.05484 | Helped |
| Omit the Graph Predictor and reconstruct from the complete generated spectrum (ablation) | GGSD on Community-small with full eigenpairs · Community-small | Spect. MMD: 0.02232 -> 0.01574 | Helped |
| Omit the Graph Predictor and reconstruct from the complete generated spectrum (ablation) | GGSD on Community-small with full eigenpairs · Community-small | Orb. MMD: 0.00942 -> 0.00514 | Helped |
| Add the Graph Predictor to diffusion using the first 8 eigenpairs (ablation) | GGSD on Community-small · Community-small | Deg. MMD: 0.00936 -> 0.00423 | Helped |
| Add the Graph Predictor to diffusion using the first 8 eigenpairs (ablation) | GGSD on Community-small · Community-small | Clus. MMD: 0.09753 -> 0.05464 | Helped |
| Add the Graph Predictor to diffusion using the first 8 eigenpairs (ablation) | GGSD on Community-small · Community-small | Spect. MMD: 0.04341 -> 0.01832 | Helped |
Surprising findings
- Eigenvectors for the smallest eigenvalues did not consistently give better reconstructions than the largest ones, contrary to the usual low-frequency intuition.
- Planar validity is lower than DiGress, and the spectrum metric is not best on SBM and Planar.
Limitations
- The PPGN graph predictor has quadratic complexity, so the overall pipeline is not fully linear.
- Frequency selection is fixed by hand (smallest/largest k) rather than learned per dataset.
- Generated eigenvectors are only approximately orthonormal, and performance on Planar graphs is weaker.
Experimental setup
Datasets: Community-small Planar Stochastic Block Model QM9 Proteins
Benchmarks: Community-small Planar SBM Proteins QM9
Metrics: MMD degree MMD clustering MMD spectrum MMD orbit validity uniqueness novelty VUN
Baselines: GraphRNN GRAN DiGress SPECTRE GDSS GSDM GraphVAE
Builds on: DDPM SPECTRE PPGN GSDM RePaint
Closest papers by meaning
- Simple and Critical Iterative Denoising: A Recasting of Discrete Diffusion in Graph Generation (ICML 2025 · similarity 0.91)
- SBGD: Improving Graph Diffusion Generative Model via Stochastic Block Diffusion (ICML 2025 · similarity 0.90)
- Graph Generation with Diffusion Mixture (ICML 2024 · similarity 0.90)
- Advancing Graph Generation through Beta Diffusion (ICLR 2025 · similarity 0.89)
- Discrete-state Continuous-time Diffusion for Graph Generation (NeurIPS 2024 · similarity 0.89)
- Unifying Generation and Prediction on Graphs with Latent Graph Diffusion (NeurIPS 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.