Colored Graph Signal Diffusion Models

Yiğit Berkay Uslu, Samar Hadou, Shirin Saeedi Bidokhti, Alejandro RibeiroarXiv 2026 · arXiv

TL;DR

This paper introduces Colored Graph Signal Diffusion Models, a novel framework that tailors noise injection to the underlying graph structure. By replacing standard "white" noise with "colored" noise and introducing a tunable "spectral clock," the authors achieve high-quality signal generation in up to 20x fewer sampling steps than standard diffusion methods.

What Problem Does This Paper Address?

Standard diffusion models (like those used in DALL-E or Stable Diffusion) typically add "white" noise to data—meaning they inject noise uniformly across all frequencies. However, many real-world signals, especially those defined on graphs (like brain activity or traffic patterns), are "smooth." Their energy is concentrated in low-frequency components, while high-frequency components are often sparse or noise-dominated.

When you use standard diffusion on these signals, the model is forced into a fixed "coarse-to-fine" generation order determined solely by the data's energy distribution. This is often inefficient. The authors argue that for graph signals, the generation hierarchy should be a design choice, not a side effect of the noise.

Methods

The authors propose three key innovations to make diffusion "graph-aware":

  1. Colored Forward Process: Instead of isotropic noise, they use a Gaussian prior "colored" by the Graph Shift Operator (GSO)—a matrix representing the graph's topology (like the Laplacian). This ensures the noise respects the graph's natural "frequencies."
  2. The Spectral Clock ($\phi$): They introduce a tunable function that acts as a clock for each frequency band. This allows researchers to control exactly when different parts of the signal (e.g., global trends vs. local details) are lost during the forward process and recovered during the reverse process.
  3. Hybrid Denoiser Design: The denoiser is split into two parts:
  4. Analytic Wiener Head: A linear filter that mathematically handles the Gaussian second-order structure of the graph signal.
  5. GNN Body: A Graph Neural Network that only has to learn the remaining complex, non-Gaussian "residuals."

This "preconditioning" significantly reduces the learning burden on the neural network.

Datasets

The model was evaluated on two real-world graph signal datasets:

  • fMRI (Human Connectome Project): Brain activity recorded across 360 cortical regions.
  • METR-LA: Traffic speed data from a network of 153 sensors in Los Angeles.

The authors compared their approach against standard Variance Preserving (VP) diffusion and existing Graph-Aware Diffusion (GAD) baselines.

Key Insights and Ideas

  • Decoupling Hierarchy from Prior: By tuning the spectral clock, you can change the order in which information is generated without changing the final distribution you're aiming for.
  • Efficiency through Math: A major "aha" moment is that the analytic Wiener head carries most of the performance gain. By solving the "easy" part of the denoising problem with classical signal processing, the GNN becomes much more efficient.
  • Spectral Anisotropy is a Feature: Instead of fighting the fact that graph signals have different properties at different frequencies, this model embraces it as a tunable axis for optimization.

Key Results

The most striking result is the massive improvement in sampling efficiency.

Fig. 1: Comparison of the colored model (pinned at the SQ-selected ¯a = −0.83) with the standard VP on fMRI data. (a) Relative covariance error of generated clouds against the held-out frames versus the step budget N across Heun and ancestral samplers. (b) Descriptor MMDs, differenced within each fold, values above zero favor coloring. (c) Per-band variance of generated clouds relative to the held-out variance at N = 50 Heun steps, with bands ordered by decreasing λi from the smoothest to the roughest modes and shading the fold range.

As seen in Figure 1(a) above, the colored model (blue) reaches the "oracle" covariance error level in just 10 to 20 steps. In contrast, standard VP diffusion (orange) requires over 200 steps to reach the same quality.

Furthermore, Figure 1(c) shows that at 50 steps, standard diffusion fails to capture the correct variance in middle-to-high frequency bands, whereas the colored model reproduces the training variance accurately across the entire spectrum.

Table 1: Generation quality comparisons at two ancestral bud- gets and one probability-flow budget. Columns name the sampler and the step count N. Bold marks the arm closest to the reference row of its column, the oracle for cov and the real data for aMMD. The baselines are standard VP [19, 17] and GAD [4]. SQ marks the spectral-quantile exponent of Section 3.

In Table 1, the "SQ" (Spectral-Quantile) arm—a specific clock design proposed by the authors—consistently beats baselines across both fMRI and traffic data, particularly in the low-budget (N=20) sampling regime.

Limitations and Future Work

  • Clock Optimization: While the authors provide a "Spectral-Quantile" rule for setting the clock, they haven't yet explored automated, task-specific optimization of the clock shape (e.g., via reinforcement learning or bilevel optimization).
  • Scalability: The current implementation uses eigendecomposition, which is computationally expensive for very large graphs (millions of nodes). The authors suggest that "matrix-free" methods like Krylov approximations are a necessary next step for scaling.
  • Stability: A formal stability analysis of these colored SDEs remains an open theoretical question.

Summary updated

Abstract

Standard diffusion processes with isotropic noise corruption are not spectrally neutral. They inherit a coarse-to-fine generation hierarchy from the nonuniform data spectrum, because each frequency band loses signal-to-noise ratio (SNR) at its own rate. For signals on a graph, the relevant spectrum is that of the graph shift operator (GSO). A natural construction, therefore, builds both the diffusion dynamics and the denoiser from graph filters of the GSO, and any such design also takes a position on this hierarchy. We expose this hierarchy as a tunable axis through a family of colored score-based diffusions. Fixing the terminal prior to a Gaussian colored by the GSO couples the drift and diffusion through a positive spectral rate, which acts as a clock for each graph-frequency band. The clock sets when a band loses and recovers information, and the forward processes of standard and certain graph-aware diffusions appear as members of this family. A GSO-valued EDM preconditioning splits the denoiser into an analytic Wiener head that carries the Gaussian second-order structure and a graph neural network (GNN) that learns the remaining non-Gaussian dependencies. Numerical experiments show that colored diffusions reach a given generation quality in far fewer sampling steps than standard diffusion.
BibTeX
@misc{uslu2026colored,
  author = {Yiğit Berkay Uslu and Samar Hadou and Shirin Saeedi Bidokhti and Alejandro Ribeiro},
  title = {{Colored Graph Signal Diffusion Models}},
  year = {2026},
  eprint = {2610.17282},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.17282},
}
Figure