Research map / Graph learning / Graph self-supervised learning
A Non-Asymptotic Convergent Analysis for Scored-Based Graph Generative Model via a System of Stochastic Differential Equations
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.
Gives the first non-asymptotic KL convergence analysis for score-based graph generative models modeled as coupled SDEs over node features and adjacency, covering feature-only, structure-only, and joint generation, and validates it on synthetic graphs.
Problem
Convergence behavior of score-based graph generative models, which use a system of coupled SDEs for graph structure and node features, is theoretically underexplored; existing SGM convergence analyses assume a single SDE and independent elements.
Approach
Extends the non-asymptotic KL convergence analysis of score-based diffusion to a coupled system of SDEs for adjacency and node-feature matrices, deriving bounds for three generation paradigms (feature-only, structure-only, joint) under Euler-Maruyama and exponential integrator samplers, and linking bound terms to graph size, degree heterogeneity, and feature norms.
Key results
- Theory gives KL bounds for three paradigms; bounds grow quadratically in graph size N (N^2 for structure) but only linearly in feature dimension F.
- Bounds scale with sigma_A, bounded by max degree, so heterogeneous-degree (power-law) graphs have larger error; experiments show SGGMs perform better on regular than power-law graphs.
- Exponential integrator yields smaller discretization error than Euler-Maruyama; normalization of features reduces error, confirmed empirically on synthetic graphs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use normalization on node features (ablation) | SGGM in feature generation with fixed graph structure · Synthetic graphs; increasing feature size | performance | Helped |
| Generate regular graphs instead of power-law graphs | SGGM · Synthetic regular and power-law graphs | performance | Helped |
| Increase graph size rather than feature size | SGGM · Synthetic graphs | performance | Hurt |
| Use the exponential integrator instead of Euler-Maruyama | SGGM · Graph generation | convergence bound | Helped |
| Increase diffusion length T | SGGM · Joint graph structure and node feature generation | generative error | Helped |
Limitations
- Assumes smooth, bounded data distributions and a score function of GNN form; learning-process errors are treated as a static constant.
- Empirical validation limited to small synthetic graphs (N=50, F=50) with a one-layer GCN.
- Analysis uses vanilla GCN with identity transforms; normalization effect is argued theoretically rather than for general architectures.
Experimental setup
Datasets: synthetic regular graphs synthetic Barabási-Albert power-law graphs
Builds on: score-based generative models Ornstein-Uhlenbeck process Euler-Maruyama scheme exponential integrator
Closest papers by meaning
- Quality Measures for Dynamic Graph Generative Models (ICLR 2025 · similarity 0.89)
- On the Role of Edge Dependency in Graph Generative Models (ICML 2024 · similarity 0.89)
- Algorithm- and Data-Dependent Generalization Bounds for Diffusion Models (NeurIPS 2025 · similarity 0.89)
- SBGD: Improving Graph Diffusion Generative Model via Stochastic Block Diffusion (ICML 2025 · similarity 0.88)
- Towards Addressing Frontiers in Graph Generation (AAAI 2025 · similarity 0.88)
- GLAD: Improving Latent Graph Generative Modeling with Simple Quantization (AAAI 2025 · similarity 0.87)
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.