Practical Non-Stationary Graph Gaussian Processes

Matern Gaussian processes offer a principled framework for learning and uncertainty quantification on graphs. However, they struggle with heterogeneous networks. A central challenge is that variance at a node can represent genuine signal that should strongly propagate (diffuse) to neighbors, mere noise that should be isolated, or a mixture of both. While this problem has been studied in continuous spatial domains, directly translating those approaches to graphs leaves a free parameter per node, causing extreme over-parameterization. To resolve this, we introduce non-stationary Variance-Coupled Gaussian Processes (VCGPs). These models use an auxiliary signal (often easily derived from historical data) to determine relative diffusivity between nodes, tied to the regression data via a single learned hyperparameter, $\gamma$. The sign of $\gamma$ captures whether the auxiliary signal is directly or inversely proportional to node diffusivity, while its magnitude calibrates this relationship.We formally prove that $\gamma = 1$ is the unique point where VCGPs are stationary up to rescaling, ensuring that varying $\gamma$ results in genuinely non-stationary correlations. Across five real-world datasets, our VCGPs match or outperform both stationary and heavily parameterized non-stationary baselines.