Research map / Graph learning / Graph self-supervised learning
SBGD: Improving Graph Diffusion Generative Model via Stochastic Block 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 SBGD, a graph diffusion model that partitions graphs into METIS blocks and diffuses over block graphs plus a cross-block interaction network, reducing memory and improving size generalization.
Problem
Graph diffusion generative models operate on the full graph, giving O(N^2) memory that limits scalability to large graphs, and they generalize poorly to graph sizes unseen in training.
Approach
Decompose each graph into k METIS-partitioned block graphs, run diffusion separately on each block's adjacency and features with a graph transformer, and model sparse inter-block links with a separate network conditioned on two generated blocks, so memory scales with block size C rather than N.
Key results
- SBGD is the only evaluated method that trains on OGBN-Products, where GraphRNN, SPECTRE, GDSS and DiGress run out of memory.
- On planar graphs SBGD achieves the best average MMD (0.32) and FID 25.0 with a memory ratio of 1.0 versus 4.2 to 6.1 for baselines (up to 6x memory savings).
- On cSBM, SBGD achieves the lowest MMD on degree, clustering, orbit and wavelet metrics and FID 16.3 versus 17.6 for SPECTRE.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use block-space diffusion instead of full-graph diffusion | SBGD · Planar Graphs | Avg.: 0.33 -> 0.32 | Helped |
| Use block-space diffusion instead of full-graph diffusion | SBGD · Planar Graphs | FID: 29.0 ± 3.011 -> 25.0 ± 2.857 | Helped |
| Use block-space diffusion instead of full-graph diffusion | SBGD · Contextual Stochastic Block Model | Avg.: 0.31 -> 0.29 | Helped |
| Use block-space diffusion instead of full-graph diffusion | SBGD · Contextual Stochastic Block Model | FID: 17.6 ± 0.92 -> 16.3 ± 0.32 | Helped |
| Use block-space diffusion instead of full-graph diffusion | SBGD · QM9 | FID: 19.7 ± 1.25 -> 20.0 ± 1.02 | Hurt |
| Use block-space diffusion instead of full-graph diffusion | SBGD · QM9 | V.U.N: 92.8 ± 1.42 -> 91.2 ± 1.08 | Hurt |
| Use block-space diffusion instead of full-graph diffusion | SBGD · OGBN-Arxiv | Avg.: 0.28 -> 0.27 | Helped |
| Use block-space diffusion instead of full-graph diffusion | SBGD · OGBN-Arxiv | FID: 21.6 ± 1.56 -> 21.4 ± 1.23 | Helped |
| Use block-space diffusion to enable training on the large dataset | SBGD · OGBN-Products | successful training | Helped |
| Vary the number of partitions; smaller blocks initially improve generation quality, but excessively small blocks degrade it (ablation) | SBGD · cSBM | FID | Mixed |
| Increase the partition number (smaller blocks) (ablation) | SBGD · cSBM size generalization to smaller graphs | FID | Helped |
| Decrease the partition number (larger blocks) (ablation) | SBGD · cSBM size generalization to larger graphs | FID | Helped |
Surprising findings
- On QM9, DiGress (V.U.N 92.8, FID 19.7) slightly outperforms SBGD (91.2, 20.0), and on OGBN-Arxiv SBGD is not uniformly best.
- The authors report that performance is non-monotonic in the number of partitions: too many partitions lose global structure, too few pick up noise.
Limitations
- Performance depends on the number of partitions/block size, which must be tuned and has no principled selection rule.
- Some baselines are not compared on several datasets (N.S. entries), and DiGress is slightly better on QM9 and several metrics on Arxiv.
- Cross-block interaction network and partitioning are heuristic (METIS); the authors note partition algorithm choice is unexplored.
Experimental setup
Datasets: Planar graphs Contextual Stochastic Block Model (cSBM) Proteins QM9 OGBN-Arxiv OGBN-Products
Benchmarks: Planar graphs cSBM QM9 OGBN-Arxiv OGBN-Products
Metrics: MMD degree MMD clustering MMD orbit MMD spectral MMD wavelet V.U.N FID memory ratio
Baselines: GraphRNN SPECTRE EDGE EDP-GNN GDSS DiGress
Builds on: DiGress GDSS DDPM DDIM
Closest papers by meaning
- Advancing Graph Generation through Beta Diffusion (ICLR 2025 · similarity 0.91)
- Unifying Generation and Prediction on Graphs with Latent Graph Diffusion (NeurIPS 2024 · similarity 0.91)
- Efficient and Scalable Graph Generation through Iterative Local Expansion (ICLR 2024 · similarity 0.90)
- Generative Modelling of Structurally Constrained Graphs (NeurIPS 2024 · similarity 0.90)
- Pard: Permutation-Invariant Autoregressive Diffusion for Graph Generation (NeurIPS 2024 · similarity 0.90)
- Discrete-state Continuous-time Diffusion for Graph Generation (NeurIPS 2024 · similarity 0.90)
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.