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

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 across graph frequencies, 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 signal-to-noise ratio. GRCD fits a zero-mean graph-spectral Gaussian reference on the training split and, rather than driving the corruption to near-zero terminal SNR, stops at a finite terminal SNR at which the propagated reference still carries the fitted spectral variances, narrowing the SNR range that sampling must cover. 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 graph-signal settings (the METR-LA traffic and Molene weather datasets, and three synthetic settings from stochastic block models) against seven comparators under a matched protocol: Graph-Aware Diffusion (GAD), EDM adapted to the graph backbone, two graph adaptations of Whitened Score Diffusion (WSD), and three preconditioning controls. At four function evaluations (NFEs), GRCD lowers averaged maximum mean discrepancy (aMMD) by $22$–$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. Within GRCD, fitting the terminal reference reduces aMMD by factors of $2.7$–$7.3\times$ at finite terminal SNR, while the corresponding factors shrink to $1.00$–$1.01\times$ near zero, matching the analytic limit in which the propagated reference loses dependence on the fitted covariance.