Source-linked AI summary
Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations
Jaehyeong Jo, Seul Lee, Sung Ju Hwang
TL;DR
Graph generation requires models that respect graph structure and capture dependencies between nodes and edges, especially for molecules. GDSS introduces continuous-time joint diffusion with SDE-based score learning and reverse-process integration, achieving strong generation performance across graph and molecule tasks.
Problem
Existing graph generative methods can miss permutation invariance, structural information, or complex dependencies between nodes and edges; adjacency-only score models also omit node features.
Method
GDSS jointly diffuses node features and adjacency matrices through a dependent system of SDEs, learns componentwise joint scores, and efficiently solves the reverse process.
Results
GDSS outperforms one-shot graph generators, is competitive with autoregressive models on generic graphs, and outperforms state-of-the-art baselines on molecule generation.
Takeaways & Limitations
Modeling node–edge dependency through the SDE system is supported by improved generic graph performance and molecule-generation results.
Takeaways & Limitations
EDP-GNN's adjacency-only formulation illustrates the scope boundary addressed by GDSS, while a stated variant relies on approximations to joint score functions.
Abstract
from arXiv · showhide
Generating graph-structured data requires learning the underlying distribution of graphs. Yet, this is a challenging problem, and the previous graph generative methods either fail to capture the permutation-invariance property of graphs or cannot sufficiently model the complex dependency between nodes and edges, which is crucial for generating real-world graphs such as molecules. To overcome such limitations, we propose a novel score-based generative model for graphs with a continuous-time framework. Specifically, we propose a new graph diffusion process that models the joint distribution of the nodes and edges through a system of stochastic differential equations (SDEs). Then, we derive novel score matching objectives tailored for the proposed diffusion process to estimate the gradient of the joint log-density with respect to each component, and introduce a new solver for the system of SDEs to efficiently sample from the reverse diffusion process. We validate our graph generation method on diverse datasets, on which it either achieves significantly superior or competitive performance to the baselines. Further analysis shows that our method is able to generate molecules that lie close to the training distribution yet do not violate the chemical valency rule, demonstrating the effectiveness of the system of SDEs in modeling the node-edge relationships. Our code is available at https://github.com/harryjo97/GDSS.
1. Introduction
Graph generation is challenging because existing approaches struggle with permutation invariance, structural information, and node–edge dependencies. GDSS addresses these limitations with continuous-time score-based diffusion that jointly models node features and adjacency matrices.
- Autoregressive models are costly and miss graph permutation invariance, while likelihood-based one-shot models struggle to capture structural information.
- EDP-GNN uses heuristically chosen discrete noise scales and generates only adjacency matrices, limiting flexibility and node–edge dependency modeling.
- GDSS introduces continuous-time diffusion that jointly perturbs and generates node features and adjacency matrices through a system of SDEs.
- The method derives score-matching objectives for componentwise joint log-density gradients and an efficient integrator for reverse SDE sampling.
- On synthetic, real-world, and molecule generation tasks, GDSS outperforms one-shot models, matches autoregressive models competitively on generic graphs, and surpasses state-of-the-art baselines for molecules.
2. Related Work
Score-based graph generation extends diffusion-based sampling to graph data, where discreteness and complex node–edge dependencies remain difficult. GDSS uses dependent continuous-time diffusion to generate nodes and edges interdependently rather than relying on adjacency-only or sequential alternatives.
- Score-based generative models perturb data with increasing noise, learn score functions, and reverse the perturbation to generate samples from noise.
- Graph generation remains underexplored because graph structures are discrete and nodes and edges have complex dependencies.
- Graph generative models are commonly categorized as autoregressive or one-shot according to whether components are generated sequentially or at once.
- Earlier score-based graph generation estimated adjacency scores at finite noise scales and sampled with Langevin dynamics, requiring many steps and omitting node features.
- GDSS uses a system of dependent SDEs to smoothly transform node features and adjacency between data and a known prior, enabling interdependent generation.
3. Graph Diffusion via the System of SDEs
GDSS introduces a continuous-time graph diffusion framework that perturbs node features and adjacency matrices through interdependent SDEs. It estimates component-wise partial scores and uses a specialized reverse-time solver to generate graphs while modeling node-edge dependency.
- 3.1. Graph Diffusion Process: GDSS represents a graph as node features X and adjacency matrix A, then diffuses both components toward a tractable prior distribution over a fixed time horizon.The forward process starts from G0 sampled from pdata and adds infinitesimal noise through an Itô SDE.
- 3.1. Graph Diffusion Process: The reverse process starts from prior samples and uses a system of SDEs whose component processes are coupled through gradients of the joint log-density.These partial score functions connect the diffusion of node features and adjacency through time.
- 3.1. Graph Diffusion Process: EDP-GNN is a special GDSS instance that omits node-feature diffusion, while GDSS-seq generates node features first and adjacency sequentially under simplified dependency assumptions.The sequential variant is obtained by neglecting parts of the dependency between the components.
- 3.1. Graph Diffusion Process: In a bivariate Gaussian-mixture toy experiment, GDSS represents variable correlation, whereas GDSS-seq and EDP-GNN fail to capture covariance and deviate from the data distribution.The experiment directly tests whether the diffusion process models dependency between components.
- 3.2. Estimating the Partial Score Functions: GDSS trains time-dependent models for the node and adjacency partial scores using objectives that generalize score matching to gradients of each component.The objectives use samples from the data distribution and the transition distribution induced by the forward diffusion.
- 3.3. Solving the System of Reverse-time SDEs: S4, a symmetric-splitting integrator, simulates the coupled reverse-time SDE system efficiently and accurately, requiring half as many score-model forward passes as the PC sampler.The solver is designed for interdependently tied diffusion processes and also applies to general systems of SDEs.
4. Experiments
Experiments evaluate GDSS on generic and molecular graph generation, including dependency modeling, solver efficiency, and comparisons with prior methods. GDSS generally outperforms one-shot baselines, competes with autoregressive models, and achieves strong molecule validity, distributional proximity, and generation speed.
- Generic Graph Generation: GDSS significantly outperforms one-shot baselines and beats autoregressive methods on most generic graph datasets, except Grid.On Grid, GDSS achieves performance competitive with GraphRNN, while EDP-GNN fails on large graphs.
- Molecule Generation: GDSS achieves the highest validity without post-hoc valency correction and significantly outperforms baselines on NSPDK MMD and most FCD results.These results indicate that generated molecules remain close to the data distribution in graph and chemical spaces while respecting chemical valency.
- Molecule Generation: GDSS generates molecules 450× faster than GraphDF on QM9 and requires less generation time than EDP-GNN.The authors attribute the efficiency advantage over EDP-GNN to continuous-time diffusion rather than discrete-step perturbation.
- Dependency Modeling: GDSS models node-edge dependency more effectively than GDSS-seq, which is reflected by consistently better graph-generation metrics and molecule validity.GDSS-seq models only the dependency of A on X, whereas GDSS models the dependency through its SDE framework.
- Solver Analysis: The S4 solver outperforms predictor-only EM and Reverse samplers and surpasses PC samplers with half the computation time.The comparison is attributed to fewer evaluations of the score-based models.
- Ablation Studies: Replacing GDSS’s continuous-time diffusion with discrete-step perturbation produces poor molecule-generation performance and increases generation time.Using GMH instead of GNN in the score model yields results comparable with GDSS.
5. Conclusion
GDSS is presented as a score-based graph-generation framework that jointly diffuses node features and adjacency while modeling their dependency. Across diverse synthetic, real-world, and molecular graphs, it outperforms existing generative methods.
- 5. Conclusion: GDSS transforms node features and adjacency into noise and back through a system of SDEs, modeling their dependency.The framework estimates component-wise joint log-density gradients and uses an integrator for reverse diffusion.
- 5. Conclusion: GDSS outperforms existing generative methods across diverse synthetic and real-world graph-generation tasks, including molecules.
- 5. Conclusion: The paper identifies node-edge dependency as crucial for learning graph distributions and highlights implications for score-based graph generation.
A. Derivations
The appendix derives equivalent score-matching objectives, formulates reverse diffusion with Fokker-Planck operators, and develops the symmetric-splitting S4 solver. S4 combines correction steps with operator-based prediction steps and has global prediction error O(δt).
- Score-matching derivations: Original and denoising score-matching objectives are shown equivalent with respect to θ and φ for the corresponding score components.
- Score-matching derivations: The joint conditional score with respect to X_t reduces to the node-feature conditional score because the adjacency term has zero X_t-gradient.
- Fokker-Planck operators: Fokker-Planck operators decompose reverse diffusion into component processes, including diffusion and reverse-time ODE actions for X_t and A_t.
- S4 solver: The S4 solver approximates the intractable propagator through symmetric splitting, using transition distributions and Euler integration; its global prediction error is O(δt).Its prediction step has local error O(δt^2).
- S4 solver: Algorithm 1 alternates score computation, Langevin correction for X and A, and split prediction steps until producing X_0 and A_0.
A.5. Derivation of the transition distribution
The appendix specifies transition distributions for the diffusion processes used by GDSS and situates the score-model architectures within the broader generation procedure. VPSDE and VESDE transitions are Gaussian under their linear drift coefficients.
- Transition distributions: Transition distributions are derived for sufficiently small reverse-time steps, assuming the current state is given and the input is a zero-variance normal state.
- VPSDE: For VPSDE, linear drift yields Gaussian transitions whose mean and covariance are derived from the SDE coefficients and β_t schedule.
- VESDE: For VESDE, linear drift likewise yields Gaussian transitions, with covariance determined by σ_min, σ_max, and the time-dependent variance schedule.
B.1. Score-based Model Architecture
GDSS uses separate score models for node features and adjacency, then samples graph size, runs reverse diffusion, and quantizes the resulting graph. The appendix documents the associated model, diffusion, solver, and training hyperparameters.
- B.1. Score-based Model Architecture: The node-feature score model sθ,t and adjacency score model sφ,t are described as the proposed score-based architectures.
- B.1. Score-based Model Architecture: The reported hyperparameters cover the two score models, diffusion SDEs for X and A, the SDE solver, and training.
- B.1. Score-based Model Architecture: Generation samples the node count from the training-size distribution, draws prior noise, simulates reverse SDEs, and quantizes X_0 and A_0.
C. Experimental Details
The experiments cover toy, generic graph, and molecule generation settings, with implementation details and hyperparameters reported for GDSS and baselines.
- The experimental section includes toy experiments, generic graph generation tasks, and molecule generation tasks.
C.1. Toy Experiment
The experiments use diverse graph and molecular datasets, standardized preprocessing and evaluation, and additional analyses of variability, sampling, and solver performance.
- The graph benchmarks span Ego-small, Community-small, Enzymes, and Grid, covering synthetic, real-world, social, and biochemical graphs.
- Molecular experiments use QM9 and ZINC250k, representing molecules with binary atom features and bond-type adjacency matrices.
- GDSS molecules are kekulized, stripped of hydrogens, evaluated with valency correction, and tuned using novelty and FCD criteria.
- Baseline molecule generators are implemented through DIG, official repositories, and original experimental settings where available.
- Additional results report standard deviations, validity, uniqueness, novelty, larger-sample MMD, and comparisons among fixed-step SDE solvers.
D.3. Ablation Studies
The ablation-related results show that the S4 solver is computationally competitive, while visualizations compare generated and training graphs across several datasets.
- Ablation Studies: S4 significantly outperforms predictor-only methods and achieves competitive results against PC samplers with half the computation time.
- Graph Visualizations: Figures 6–9 visualize randomly selected training and GDSS-generated graphs for Ego-small, Community-small, Enzymes, and Grid.
- Graph Visualizations: The visualizations additionally report each graph’s number of edges e and number of nodes n.
E.2. Molecule Generation
GDSS generates molecules structurally close to selected training molecules, using Tanimoto similarity based on Morgan fingerprints for comparison.
- GDSS generates molecules structurally close to training molecules, whereas other baselines deviate from the training distribution.
- Figure 10 selects generated molecules maximally similar to dataset molecules and displays each Tanimoto similarity value.