PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph Residual Conjugate Diffusion: SNR-Equalized Heat Flow for Graph Signals

Jinwei Li, Daniel Tenbrinck

arXiv:2609.39658v1cs.LG

TL;DR

Graph diffusion must accommodate graph signals whose spectral energy varies across frequencies, even though isotropic corruption applies equal noise variance to every mode. GRCD uses a mode-dependent clock and a fitted finite-SNR Gaussian reference, with an analytic propagator for its Gaussian score component. At finite terminal SNR, fitting the reference lowers aMMD by 2.7–7.3 times, while that advantage shrinks near zero terminal SNR.

  • Problem

    Graph signals can have nonuniform spectral energy, while isotropic corruption adds equal noise variance across graph-Fourier modes; the paper asks whether diffusion can instead use a fitted finite-SNR reference.

    Source: §1 · pp. 1–2

  • Method

    GRCD uses a mode-dependent clock, fits a zero-mean graph-spectral Gaussian reference on training data, and integrates only the learned residual score numerically.

    Source: §1 · p. 2

  • Results

    At finite terminal SNR, fitting the reference reduces aMMD by 2.7–7.3 times across five settings, compared with 1.00–1.01 times near zero terminal SNR.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The fitted Gaussian reference has an exact modewise propagator, enabling accurate sampling with few function evaluations.

    Source: §6 · p. 10

    The construction assumes a fixed symmetric graph operator, models only second-order dependencies, and focuses on unconditional generation.

    Source: §6 · p. 10

Abstract

from arXiv · show

Diffusion models generate data by reversing a forward corruption process that typically approaches a simple Gaussian prior. Recent work has extended this framework to signals supported on fixed graphs, e.g., road-network traffic and sensor-network measurements. Many graph signals have nonuniform spectral energy, whereas isotropic corruption adds the same conditional noise variance to every graph-frequency mode. Driving all modes to near-zero terminal signal-to-noise ratio (SNR) requires strong corruption, which increases the noise range that must be covered under a fixed sampling budget. We introduce Graph Residual Conjugate Diffusion (GRCD), which replaces the shared clock of graph heat diffusion with a mode-dependent clock that gives every graph-Fourier mode the same conditional SNR. GRCD fits a zero-mean graph-spectral Gaussian reference on the training split and stops at a finite terminal SNR at which the propagated reference still carries the fitted spectral variances. The Gaussian component has an exact modewise propagator in the probability-flow ODE, so sampling advances it analytically and integrates only the learned residual score numerically. We evaluate GRCD on five settings (METR-LA traffic, Molene weather, and three stochastic block models) against seven comparators under a matched protocol: Graph-Aware Diffusion (GAD), EDM (graph backbone), two adaptations of Whitened Score Diffusion (WSD), and three preconditioning controls. At four function evaluations (NFEs), GRCD lowers averaged maximum mean discrepancy (aMMD) by 22 to 36 times over the best comparator on all five settings, reaching 0.054 on METR-LA, where it clears an aMMD 0.1 target with 87% less sampling wall-clock time than the cheapest comparator that reaches it. Fitting the terminal reference reduces aMMD by 2.7 to 7.3 times at finite terminal SNR, while the factors shrink to 1.00 to 1.01 near zero.

1 INTRODUCTION

Graph signals can have uneven spectral energy, motivating a diffusion process that equalizes conditional SNR across graph frequencies and can stop at a fitted finite-SNR reference. GRCD combines that reference with a learned residual, and its reported benefits are strongest at finite terminal SNR and low sampling budgets.

1 INTRODUCTION

  • Graph signals can have nonuniform spectral energy, but isotropic corruption adds the same noise variance to every graph-Fourier mode, motivating a structured finite-SNR endpoint.The paper asks whether such an endpoint can replace driving graph-signal diffusion near zero SNR.Source: §1 · pp. 1–2
  • GRCD derives a mode-dependent diffusion clock that gives every graph-Fourier mode the same conditional SNR in conjugate coordinates.A scalar q(t) controls corruption there, while the original signal space retains graph-dependent dynamics.Source: §1 · p. 2
  • GRCD fits a shared zero-mean Gaussian reference from training data, retaining graph-Fourier diagonal variances and propagating it to the selected finite terminal SNR.Its probability-flow ODE score splits into an analytic Gaussian component and a learned residual, so only the residual is integrated numerically.Source: §1 · p. 2
  • As terminal noise grows, the propagated reference becomes independent of the fitted spectral covariance.The paper reports this as the zero-terminal-SNR asymptotic behavior of the reference.Source: §1 · p. 2
  • At finite terminal SNR, fitting the terminal reference reduces aMMD by 2.7–7.3 times; on METR-LA, GRCD reaches 0.054 aMMD at 4 NFE and cuts time to the 0.10 target by 87%.Near-zero terminal SNR, the reference-fitting factors shrink to 1.00–1.01.Source: §1 · p. 2

2 BACKGROUND AND SETTING

The setting represents signals on a fixed undirected weighted graph and uses a shifted, spectrally normalized Laplacian for diffusion. Sampling uses a probability-flow ODE, with terminal SNR describing the remaining fitted covariance in GRCD’s propagated reference.

2 BACKGROUND AND SETTING

  • The paper considers graph signals on a fixed, undirected weighted graph with N nodes and a symmetric weighted adjacency matrix.Source: §2 · p. 2
  • The symmetric normalized graph Laplacian is positive semidefinite for undirected graphs with nonnegative weights and admits an eigendecomposition.The eigenvectors are orthonormal and the eigenvalues are nonnegative.Source: §2 · p. 2
  • The diffusion operator rescales the Laplacian by its largest eigenvalue and adds a positive spectral shift, making all eigenvalues strictly positive.This affine transformation preserves the Laplacian eigenvectors and eigenvalue ordering.Source: §2 · p. 3
  • The probability-flow ODE is a deterministic sampling formulation whose initialized marginal density matches the corresponding SDE at every time.The paper measures sampling cost in function evaluations.Source: §2 · p. 3
  • In GRCD, terminal SNR controls how much fitted graph-spectral covariance remains in the propagated terminal reference.The paper distinguishes this role from the nonzero-terminal-SNR training–inference mismatch discussed for image diffusion.Source: §2 · p. 3

3 METHODOLOGY

GRCD uses a mode-dependent graph-diffusion clock and a training-fitted Gaussian reference to shape corruption and initialize reverse sampling. It separates the Gaussian score for exact propagation from a learned residual that is handled numerically.

3.1 CONJUGATE GRAPH DIFFUSION

  • A mode-dependent clock makes graph-Fourier modes share conditional noise variance in conjugate coordinates while preserving graph-dependent dynamics in the original signal space.The modewise drift damps each coefficient toward zero, and its clock controls Gaussian noise injection; as q(t) grows, conditional SNR tends to zero.Source: §3.1 · pp. 3–4

3.2 GAUSSIAN REFERENCE AND FINITE-SNR TERMINAL INITIALIZATION

  • The zero-mean Gaussian reference is fitted on training data using diagonal graph-Fourier variances from a Ledoit–Wolf shrinkage covariance.Because the reference and graph filter share a graph-Fourier basis, the reference propagates analytically; dependence on fitted variances vanishes as q(t) approaches infinity.Source: §3.2 · p. 4

3.3 RESIDUAL SCORE PARAMETERIZATION

  • The residual score is the difference between the marginal data score and the propagated Gaussian-reference score, and a neural network parameterizes this residual.At the population optimum, the residual parameterization recovers the marginal score exactly.Source: §3.3 · p. 5

3.4 EXACT GAUSSIAN PROPAGATION AND THE EXPONENTIAL-RESIDUAL SAMPLER

  • The sampler propagates the Gaussian component exactly and approximates only the learned residual numerically, using two network evaluations per step.The power-law grid parameter ρ is selected by validation aMMD; the reported setting is ρ = 3, fixed before test evaluation.Source: §3.4 · pp. 5–6

4 EXPERIMENTAL SETUP

The evaluation covers five graph settings and compares GRCD with seven alternatives under a matched protocol, using aMMD to measure generation quality.

4 EXPERIMENTAL SETUP

  • The five settings are METR-LA traffic, Molene temperature, and three stochastic block model regimes with spectral concentration c ∈ {1, 4, 16}.The directed METR-LA adjacency is symmetrized before constructing the graph Laplacian; results average three random seeds at the validation-converged stage.Source: §4 · p. 6
  • Generation quality is measured by aMMD, the mean of MMDs for quadratic variation, spectral centroid, and degree correlation on normalized signals.Graph-based statistics use the combinatorial Laplacian D − W, fixed across methods.Source: §4 · p. 6
  • GRCD is compared under a matched graph protocol with EDM, two WSD-style adaptations, GAD, and isotropic, static-graph, and dynamic-conjugate preconditioning controls.The reported GAD values use this matched protocol and are not a reproduction of the values in Rozada et al. (2026).Source: §4 · p. 6

5 RESULTS

GRCD has its largest reported advantage at low sampling budgets: it leads at NFE 4 across all five settings, and on METR-LA it reaches 0.0538 aMMD. The results also show that fitted-reference gains depend on finite terminal SNR, while solver choice and measured runtime affect how quickly quality is reached.

5.1 OVERALL COMPARISON

  • At NFE 4 on METR-LA, GRCD reaches 0.0538 aMMD versus 1.2431 for the strongest method at that budget, the matched graph-prior WSD-style variant.Across the other four settings, GRCD is best at NFE 4 by 22–36×; at NFE 64, some controls overtake it on three SBM settings and conjugate preconditioning on SBM c=16.Source: §5.1 · pp. 6–7, Table 1 · p. 7

5.2 TERMINAL-REFERENCE EFFECTS ACROSS SNR REGIMES

  • At terminal SNR 2.66 on METR-LA, fitting the reference improves aMMD by 2.7×–7.3× across five settings, versus 1.00–1.01× at terminal SNR 0.010.On METR-LA, mean per-sensor standard deviation changes from 0.795 to 0.913 at finite SNR, but only from 0.916 to 0.918 near zero SNR.Source: §5.2 · p. 7, Figure 1 · p. 8

5.3 COMPONENT CONTRIBUTIONS IN GRCD

  • At NFE 16, fitting the terminal reference reduces aMMD from 0.3722 to 0.0513, a 7.25× reduction, while the residual parameterization changes it to 0.0537.The residual parameterization structurally separates the analytic Gaussian score from the learned residual, enabling the propagator; the exponential-residual solver shifts comparable quality toward smaller NFE.Source: §5.3 · p. 7, Table 2 · p. 8

5.4 SOLVER AND GRID COMPARISON

  • The exponential-residual solver is competitive with DPM-Solver++ but does not win consistently; the strongest DPM-Solver++ configuration beats it at NFE 4, while it has lower means at NFE 8, 16, and 32.At NFE 16 and 32, mean differences from the best DPM-Solver++ configuration are 0.0010 and 0.0003; at NFE 4, the ρ = 3 grid improves DPM-Solver++ 2M aMMD from 0.0659 to 0.0523.Source: §5.4 · p. 8, Table 3 · p. 9

5.5 WALL-CLOCK EFFICIENCY

  • At the aMMD 0.1 target, GRCD reaches it in 0.52 seconds per 1000 samples versus 4.02 seconds for the cheapest comparator that reaches it, an 87% reduction.Its analytic propagator handles the Gaussian component, leaving only the learned residual to integrate numerically and allowing fewer steps for useful quality.Source: Figure 2 · p. 9, §5.5 · p. 9

6 CONCLUSION

GRCD combines mode-dependent graph diffusion with a fitted graph-spectral Gaussian reference and a learned residual score. The conclusion highlights finite-terminal-SNR benefits and fast analytic propagation, while noting limits in graph structure, reference expressiveness, and scope.

6 CONCLUSION

  • At finite terminal SNR, the fitted reference improves generation by preserving data-dependent spectral structure, but this benefit disappears as terminal SNR approaches zero.The reference also provides an exact modewise propagator, enabling accurate sampling with few function evaluations.Source: §6 · p. 9
  • The Gaussian reference has an exact modewise propagator, enabling accurate sampling with few function evaluations.The neural network learns only the residual score.Source: §6 · pp. 9–10
  • The construction assumes a fixed symmetric graph operator, models only second-order dependencies, and can produce invalid values for bounded signals.For non-Gaussian data, a residual terminal-distribution mismatch may persist.Source: §6 · p. 10
  • The study focuses on unconditional generation, leaving conditional tasks and higher-dimensional domains open; gains peak at low budgets and alternative controls can outperform GRCD at higher NFE.Source: §6 · p. 10

AI USE STATEMENT

The authors report using generative AI to improve manuscript readability, identify potentially relevant literature, and assist with coding; they manually reviewed and verified all AI-assisted content.

AI USE STATEMENT

  • The authors used generative AI for grammar and readability, literature discovery, and coding assistance, then manually reviewed and verified all AI-assisted content.They state that they take responsibility for the final content.Source: AI USE STATEMENT · p. 10

A.1.1 DERIVATION OF MODE EQUALIZATION AND THE MODE-DEPENDENT CLOCK

The derivation constructs mode-dependent graph diffusion by matching its behavior to isotropic variance-exploding corruption in conjugate coordinates. Within this linear family, the prescribed noise schedule uniquely determines the mode dynamics and clock.

A.1.1 DERIVATION OF MODE EQUALIZATION AND THE MODE-DEPENDENT CLOCK

  • In the stated notation, x_t is the graph-space process, its tilde form is the conjugate-coordinate representation, and subscript i denotes a graph-Fourier coefficient.Source: §A.1.1 · p. 11
  • The derivation considers a graph-Fourier mode with μ_i > 0 and seeks a linear graph-diffusion process that follows isotropic VE diffusion with noise amplitude q(t).Source: §A.1.1 · pp. 11–12
  • For a prescribed differentiable nondecreasing q(t) with q(0) = 0, coefficient matching and a_i(0) = 1 uniquely determine a_i(t) and c_i(t).Source: §A.1.1 · p. 13
  • The resulting mode dependence is induced by exact conjugacy to the prescribed isotropic VE corruption within the linear graph-diffusion family.Source: §A.1.1 · p. 13

A.1.2 WHY A SHARED SCALAR CLOCK CANNOT EXACTLY EQUALIZE MODES

A shared scalar clock cannot exactly equalize graph-Fourier modes with distinct eigenvalues. Its transformed conditional variance depends on the eigenvalue, whereas the mode-equalized construction requires a common target variance.

A.1.2 WHY A SHARED SCALAR CLOCK CANNOT EXACTLY EQUALIZE MODES

  • Unlike the mode-equalized expression, the shared-clock conditional variance in transformed coordinates depends explicitly on μ_i.Source: §A.1.2 · p. 13
  • For fixed t with q(t) > 0, the quantity required to match the common target variance is strictly decreasing in μ_i.Source: §A.1.2 · p. 13
  • A single shared scalar clock cannot realize the common conjugate variance q(t)^2 in two modes with distinct eigenvalues, so the construction requires a mode-dependent clock.Source: §A.1.2 · p. 13

A.2 GAUSSIAN-REFERENCE DETAILS

These appendices describe how GRCD approximates and propagates its Gaussian reference, targets the learned residual score, and evaluates the method, including low-budget results and limitations of the reference. They also define how METR-LA sampling cost is measured against a quality target and identify the fitted-terminal-reference configuration.

A.2.1 SPECTRAL DIAGONAL APPROXIMATION

  • The spectral-diagonal reference discards cross-mode covariances, leaving off-diagonal energy of 0.6677 on METR-LA for the learned residual to address.The appendix characterizes this as a deliberately coarse covariance model.Source: §A.2.1 · p. 14

A.2.3 REFERENCE MARGINAL VERSUS THE TRUE DATA MARGINAL

  • The propagated Gaussian reference is not generally the true data marginal, which is Gaussian only if the initial data distribution equals the reference.For an arbitrary initial distribution, the conjugate marginal is generally non-Gaussian.Source: §A.2.3 · p. 14

A.3 RESIDUAL-SCORE TARGET DERIVATION

  • The residual parameterization learns the density-ratio score between the true marginal and propagated Gaussian reference, and its population optimum recovers the marginal score.If data equal the fitted Gaussian reference at t = 0, the reference supplies the complete score analytically and no learned residual is needed.Source: §A.3 · pp. 15–16

A.4 DERIVATION OF THE EXACT GAUSSIAN PROPAGATOR

  • The Gaussian component has an exact, composable propagator between arbitrary time points, and the exponential-residual solver is exact when the residual is zero.In implementation, it integrates the residual with composite Simpson quadrature on 65 nodes after linear interpolation; each reverse step uses two network evaluations.Source: §A.4 · pp. 16–17, §A.6.5 · p. 19

A.6.1 DATASETS AND SPLITS

  • The matched evaluation uses chronological splits for real datasets and independently generated splits for SBM, with normalization, covariance fitting, and reference estimation restricted to training data.It uses aMMD over quadratic variation, spectral centroid, and degree correlation; each comparison uses 5,000 generated and held-out signals except Molene, which uses 150.Source: §A.6.1 · p. 17, §A.6.6 · p. 19

A.6.2 TRAINING PROTOCOL

  • The experiments use a common graph backbone and stopping criterion, evaluate finite and near-zero terminal-SNR regimes, and compare GRCD with adapted WSD, EDM, GAD, and preconditioning controls.The finite-SNR setting uses κ = 2 and has energy-weighted terminal SNR 2.663 on METR-LA; near-zero settings are two to three orders of magnitude lower. Under its own configuration, GAD reaches aMMD 2.10 ± 0.15 and takes 261 seconds per 1000 samples, versus GRCD’s 0.52.Source: §A.6.2 · p. 18, §A.6.3 · p. 18, §A.6.4 · p. 19

A.7 OTHER BENCHMARK RESULTS

  • GRCD is best at NFE 4 on all four settings, but by NFE 64 several controls match or beat it on the three SBM settings.On Molene, EDM’s NFE-16 result is a crossing point rather than a converged value; its aMMD degrades to 0.176 and 0.213 at NFE 32 and 64.Source: §A.7 · pp. 20–21, Table 7 · p. 21, Table 8 · p. 21

A.8.1 NON-LEARNED GAUSSIAN CONTROLS

  • At NFE 4, the best Gaussian control has higher aMMD than GRCD on every setting; on METR-LA, the values are 0.1921 versus 0.0538.The graph-spectral reference alone reaches 0.4134 on METR-LA; across SBM, the gap rises from 1.08× at c = 1 to 2.93× at c = 16. At c = 1, however, the reference’s 0.0535 is close to GRCD’s 0.0497, while other methods can outperform GRCD at NFE 64.Source: §A.8.1 · p. 22, Table 11 · p. 23

A.8.2 COST TO REACH A QUALITY TARGET

  • Table 12 reports the cheapest measured cost, in seconds per 1000 samples, at which each configuration first reaches an aMMD target at κ = 2, converged.“Never” means the target is not reached at any budget up to NFE 64.Source: Table 12 · p. 23
  • The “+ fitted terminal reference” configuration in Table 12 is the “GRCD w/o residual score” row in Table 1.Source: Table 12 · p. 23
Loading 2609.39658v1…