Generator-based Graph Generation via Heat Diffusion

AI summary

Overview

Research area: Machine learning / statistical machine learning (stat.ML) — specifically graph generative modelling, continuous-time generative models, and spectral graph theory.

Technical level: Advanced. The paper assumes familiarity with Markov process generators, semigroups, Kolmogorov equations, flow matching, Bregman divergences, and graph Laplacian spectral theory.

Scope: The paper introduces a framework, called G³ (Generator-based Graph Generation), that defines a principled graph noising process via Laplacian heat diffusion and learns to reverse it using the Generator Matching paradigm, then benchmarks it against two existing graph generative baselines.

What This Paper Is About

Graph generative models aim to learn the distribution of a collection of observed graphs and produce new graphs with similar structural properties, which is difficult because graphs are discrete, combinatorial, and invariant to node relabelling. Most existing diffusion-based approaches define noise directly on adjacency matrices or node/edge features without a principled reason for the choice of noising process. This paper instead builds the forward noising process out of the graph Laplacian and its heat kernel, so that the corruption of a graph is tied to its own topology, and then learns a neural surrogate of the resulting infinitesimal generator to sample new graphs.

Key Contributions

1. A generator-matching framework for graph-structured data (G³). The authors adapt the Generator Matching paradigm of Holderrieth et al. (2024) to graphs by choosing a topology-aware forward noising mechanism: symmetric Laplacian heat diffusion on a matrix representation of a graph.

2. An explicit, closed-form learning target. Because the symmetric heat diffusion admits a closed-form infinitesimal generator, 𝒢Y = -(LY + YL), the training target is available analytically rather than being estimated. The time-rescaled process X_t := Y_{T(1-t)} gives a generator 𝒥(X) = T(LX + XL) that is fully determined by the graph Laplacian and therefore respects permutation equivariance and graph locality by construction.

3. A stable sampler that sidesteps the ill-posedness of reversing diffusion. The exact time reversal of the contractive heat diffusion is anti-diffusive and numerically unstable; the paper instead learns a regularised surrogate generator and integrates the reverse-time ODE from a permutation-symmetric Dirichlet-based base distribution, with projection and thresholding steps to produce a discrete adjacency matrix.

4. A unifying and empirical evaluation. The framework is presented as unifying and generalising existing diffusion-based graph generative models while injecting domain-specific inductive bias via the Laplacian. It is benchmarked against SPECTRE and DeFoG on three synthetic and three real-world datasets, using reruns of the baselines' code rather than quoted numbers.

Main Findings

• Competitive but not uniformly best MMD scores. Across the five metrics (clustering coefficient, degree distribution, 4-node orbit count, graph Laplacian spectrum, triangle counts), the paper states there is "no clear winner over all of the datasets and metrics." For example on SBM, G³ achieves clustering MMD 0.0356 ± 0.0005 versus DeFoG's 0.0500 ± 0.0000 and SPECTRE's 0.0588 ± 0.0089; on Planar, G³ achieves degree 0.0030 ± 0.0015, orbit 0.0035 ± 0.0018 and spectrum 0.0060 ± 0.0015, while DeFoG is better on all three (0.0007 ± 0.0001, 0.0002 ± 0.0000, 0.0006 ± 0.0003 respectively). On QM9, SPECTRE is best on all five attributes.

• Substantial speed advantage. Training and generation time per sample graph takes seconds for G³, compared with 15-30 minutes for DeFoG and SPECTRE (Figure 11).

• G³ wins under constrained compute budgets. When DeFoG and SPECTRE were rerun with the number of training epochs decreased by a factor of 10-100 (denoted DeFoG* and SPECTRE*), their total training times still generally exceeded those of G³, and G³ tends to outperform them, particularly with respect to degree distribution and spectral accuracy.

• Symmetric versus asymmetric diffusion. The symmetric heat diffusion generally performs better than the asymmetric version, but "there is no great margin," and on QM9, Enzymes and Proteins the asymmetric process is preferred. The authors note that planarity alone cannot explain this, since the symmetric version performs better on the planar synthetic dataset.

• Maximum diffusion time should scale with dataset size. Spectral MMD is sensitive to the choice of T, and the paper reports a general principle that T should increase with training set size N, removing the need to tune it. Less dependence on the number of nodes n was observed than expected, with curve minima occurring at approximately the same T, indicating N is the more important factor.

• Network width has a stable optimum. Spectral MMD is minimised at approximately 2¹² = 4096 hidden units per layer, independent of N, so the architecture was fixed at that value across datasets rather than tuned per dataset.

• Base distribution concentration matters. Empirically, α < 1 is preferable for planar-like graphs including the biomolecular datasets, while α = 1 is preferable for community-like graphs such as SBM and DCSBM. The choice of α affects not only spectral performance but also the ability to generate unique new graphs.

Methodology in Plain English

The method has four moving parts.

1. Represent the graph and diffuse it. Each training graph is stored as its adjacency matrix A with Laplacian L = D - A. Instead of adding random noise, the authors smooth the graph using the heat kernel H_s = e^{-sL}, producing a sequence of increasingly blurred matrices Y_s = H_s Y_0 H_s with Y_0 = A. As s grows, the matrix converges to a constant matrix proportional to the all-ones matrix, so the endpoint of the forward process is a nearly structureless state — a natural starting point for generation.

2. Note that this diffusion has a known rate of change. The matrix-valued heat equation dY_s/ds = -L Y_s - Y_s L gives an exact formula for how fast the state changes at any point. This is the "generator," and it becomes the label the neural network has to predict.

3. Train a network to predict that rate. Time is rescaled so the process runs from t = 0 (heavily diffused) to t = 1 (original graph). The authors sample a random time, compute the diffused state, compute the true generator value T(LX + XL), and train a 4-layer MLP with ReLU activations and layer normalisation to match it by minimising the squared Frobenius norm difference. Only the lower-triangular parts are used since all matrices are symmetric, which implicitly removes self-loops.

4. Sample by integrating backwards. Generation starts from a simple, permutation-symmetric base distribution: columns are drawn i.i.d. from a Dirichlet distribution, symmetry is enforced, and the result is scaled by the average degree. This approximate "fully diffused" state is then pushed through the learned ODE using explicit Euler steps with step size δ = 1/M, applying symmetrisation, diagonal zeroing and element clipping after each step. Finally, entries above a threshold c (set from the average degree of the training data) become edges in the generated adjacency matrix.

Why This Matters

Impact on research. The paper reframes graph diffusion modelling from "choose a noise process and hope" to "derive the noise process from a graph operator with a closed-form generator." Because the Laplacian is permutation-equivariant and local, the resulting model inherits those properties by construction rather than by architectural patching. The authors present it as unifying flow matching and existing diffusion-based graph generative models under a single generator-matching view, and as an alternative to methods that diffuse in latent spaces or require separate edge-reconstruction modules.

Real-world applications.

• De novo molecule design in chemistry, cited as an application of graph generation in the introduction.
• Synthetic network construction for privacy-preserving data sharing, cited explicitly as a motivation (Fu et al., 2023).
• Social network modelling (Nettleton, 2013) and knowledge graph representation (Schneider, 1973; Ji et al., 2021).
• Biomolecular structure generation, where the network's Enzymes and Proteins results are directly relevant, and where the asymmetric variant of G³ was preferred.

Industry relevance. The headline practical result is cost: seconds per sample graph versus 15-30 minutes for DeFoG and SPECTRE. The paper also removes several tuning burdens — T follows from training set size, network width is fixed at 4096 units across datasets, and the training procedure includes an automatic learning-rate decay when the loss stalls. For teams that need to generate graphs repeatedly or iterate on models, that combination of speed and few hyperparameters is the main draw. The paper provides training (Algorithm 1) and sampling (Algorithm 2) pseudocode, which supports reproducibility.

Future Directions

1. Directed graphs. The authors state that their method "in principle" extends to directed settings within the same generator-centric formulation, unlike the related heat-kernel work of Law et al. (2025), which targets directed graphs but requires a separate edge model. Whether the approach works in practice for directed data is left open.

2. Closing the gap on metrics where baselines win. DeFoG is substantially better on the Planar clustering metric (0.0413 ± 0.0047 versus G³'s 0.3090 ± 0.0300) and on several DCSBM metrics, and SPECTRE is best on all five QM9 attributes. Understanding why the Laplacian-derived process struggles with clustering structure and small molecular graphs is unresolved.

3. Explaining the symmetric/asymmetric split. The paper observes that the asymmetric variant is preferred on QM9, Enzymes and Proteins but explicitly rules out planarity as the explanation, leaving the reason unexplained.

4. Scaling behaviour and node count. The sensitivity study focused on graphs with n = 64 nodes and found less dependence on n than expected; whether the "problem gets harder as n increases" (as observed for planar graphs) is a fundamental limitation or an artefact of the fixed architecture is not settled. The paper does not report results at larger graph sizes.

Target Audience

Researchers and graduate students working on generative modelling, graph representation learning, and diffusion or flow-matching methods will get the most from this paper, particularly those interested in replacing ad hoc noising schemes with operator-derived ones. Practitioners in computational chemistry and bioinformatics who need to generate molecular or protein-like graphs at scale will find the speed and minimal tuning attractive, though they should note that the paper does not report performance on very large graphs. Readers without a background in Markov generators, semigroups, and spectral graph theory will find Sections 2.4 and 3.1 dense; the experimental section (Section 5) is accessible on its own.

Authors’ abstract

Graph generative modelling has become an essential task due to the wide range of applications in chemistry, biology, social networks, and knowledge representation. In this work, we propose a novel framework for generating graphs by adapting the Generator Matching (arXiv:2410.20587) paradigm to graph-structured data. We leverage the graph Laplacian and its associated heat kernel to define a continous-time diffusion on each graph. The Laplacian serves as the infinitesimal generator of this diffusion, and its heat kernel provides a family of conditional perturbations of the initial graph. A neural network is trained to match this generator by minimising a Bregman divergence between the true generator and a learnable surrogate. Once trained, the surrogate generator is used to simulate a time-reversed diffusion process to sample new graph structures. Our framework unifies and generalises existing diffusion-based graph generative models, injecting domain-specific inductive bias via the Laplacian, while retaining the flexibility of neural approximators. Experimental studies demonstrate that our approach captures structural properties of real and synthetic graphs effectively.