📊 statistics

Matérn Gaussian Processes on Graphs

This paper extends Matérn Gaussian processes to undirected graphs by leveraging their stochastic partial differential equation characterization, demonstrating that the resulting models inherit key properties from Euclidean analogs and can be efficiently trained using standard techniques like inducing points for mini-batch and non-conjugate settings.

Original authors: Viacheslav Borovitskiy, Iskander Azangulov, Alexander Terenin, Peter Mostowsky, Marc Peter Deisenroth, Nicolas Durrande

Published 2026-05-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Viacheslav Borovitskiy, Iskander Azangulov, Alexander Terenin, Peter Mostowsky, Marc Peter Deisenroth, Nicolas Durrande

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to predict traffic jams in a city. If you were using a standard map, you might assume that two locations are "close" if they are a short drive apart in a straight line. But in the real world, a river or a highway barrier might make two nearby streets completely disconnected. You can't drive from one to the other, even if they are right next to each other on a map.

This paper introduces a new way for computers to learn about things that exist on networks (like road maps, citation networks, or social circles) rather than just smooth, open spaces. The authors call this "Graph Matérn Gaussian Processes."

Here is a breakdown of their work using simple analogies:

1. The Problem: The "Straight Line" Trap

Standard computer models (Gaussian Processes) are great at learning patterns in smooth spaces, like temperature across a field. They assume that if two points are close, they are similar.

But on a graph (a network of nodes and connecting lines), "closeness" is tricky.

The Old Way: Some models tried to just swap "straight-line distance" for "distance along the roads." The authors say this is like trying to measure the distance between two cities by counting the number of turns you make, rather than the actual road length. It often breaks the math and gives weird results.
The New Way: The authors built a model that respects the actual shape of the network. If you have to travel a long way around a loop to get from Point A to Point B, the model knows they are "far apart," even if they look close on a map.

2. The Solution: The "Mathematical Blueprint"

The authors took a famous mathematical tool used for smooth spaces (the Matérn kernel) and translated it into the language of graphs.

The Analogy: Think of the Matérn kernel as a "smoothness rule." It tells the computer: "If I know the value at one point, how much should I expect the value to change as I move to a neighbor?"
The Innovation: They figured out how to write this rule using the Graph Laplacian. You can think of the Laplacian as a "connectivity map" that describes how information flows through the network. By plugging this map into their equations, they created a version of the Matérn kernel that works perfectly for networks.

3. Key Features of the New Model

The paper highlights three main superpowers of this new model:

It's "Sparse" (Efficient):
Imagine a giant spreadsheet where most cells are empty. The authors' model creates a "sparse" version of the math. This means the computer doesn't have to do heavy lifting for every single connection; it only calculates what's necessary. This makes it fast enough to run on huge networks without crashing your computer.
It Understands "Variance" (Uncertainty):
In some parts of a network, the model is very confident; in others, it's not.
- The Star Graph Example: Imagine a network where one central hub connects to many spokes. The model knows that the "center" is very stable (low uncertainty) because it's connected to so many things. The "spokes" are more uncertain. The model naturally learns this without being told explicitly.
It Converges (It's Consistent):
If you take a graph and make it infinitely dense (adding more and more nodes until it looks like a smooth surface), this new model naturally turns into the standard, smooth-space model. This proves the math is solid and consistent.

4. How They Trained It

Training these models on huge networks is usually hard. The authors showed two ways to make it easy:

Fourier Features: They broke the network down into its "vibrational modes" (like plucking a guitar string to hear its notes) and used the most important ones to approximate the model.
Inducing Points: They picked a small, representative sample of the network to act as "anchors" and learned from those, rather than trying to memorize every single node.

5. Real-World Tests

The authors tested their idea on two specific problems:

Traffic in San Jose: They predicted traffic speeds on a map of highways. The model successfully predicted that two roads might have very different traffic speeds even if they are physically close, simply because the road network separates them.
Scientific Citations: They tried to guess the topic of a scientific paper based only on which other papers it cited (the network structure). The model was very accurate, proving it can learn complex patterns just by looking at the connections.

Summary

In short, the authors built a "traffic-aware" learning tool. Instead of assuming everything is connected by straight lines, their tool understands that in a network, you can only travel where the roads (or links) actually go. They proved this tool is mathematically sound, fast to compute, and works better than older methods for predicting things on complex networks.

Technical Summary: Matérn Gaussian Processes on Graphs

Problem Statement

Gaussian Processes (GPs) are a versatile framework for learning unknown functions by encoding prior information, such as differentiability or periodicity, through covariance kernels. While GPs are well-established for Euclidean input spaces ( $\mathbb{R}^d$ ), their application to undirected graphs is limited. Standard Euclidean kernels based on Euclidean distance are often inappropriate for graph-structured data (e.g., road networks), where spatial proximity does not guarantee functional similarity due to connectivity constraints.

Existing approaches for graph GPs, such as Gaussian Markov Random Fields (GMRFs), rely on Markovian assumptions that limit model flexibility. Alternatively, simply replacing Euclidean distance with graph distance in stationary kernels often fails to produce well-defined covariance structures. Consequently, there is a lack of a flexible, theoretically grounded class of kernels for graphs that mirrors the rich properties of the widely used Matérn family in Euclidean settings.

Methodology

The authors propose a framework for Graph Matérn Gaussian Processes by generalizing the Stochastic Partial Differential Equation (SPDE) characterization of Matérn GPs from Euclidean and Riemannian manifolds to the graph setting.

1. SPDE Characterization on Graphs

In the Euclidean setting, Matérn GPs are defined as solutions to SPDEs involving the Laplacian operator $\Delta$ . The authors adapt this by:

Defining the Graph Laplacian $\Delta = D - W$ (where $D$ is the degree matrix and $W$ is the adjacency matrix) as the discrete analog of the negative Laplacian.
Utilizing functional calculus to define operators on the graph. For a function $\Phi$ , the operator $\Phi(\Delta)$ is defined via the eigenvalue decomposition $\Delta = U\Lambda U^T$ as $\Phi(\Delta) = U\Phi(\Lambda)U^T$ .
Formulating the graph Matérn GP as the solution to:
$\left( \frac{2\nu}{\kappa^2} + \Delta \right)^{\frac{\nu}{2}} f = W$
where $W$ is a standard Gaussian vector (analogous to white noise), $\nu$ is the smoothness parameter, and $\kappa$ is the length scale.
This yields a Gaussian process with a precision matrix (inverse covariance) given by $\left( \frac{2\nu}{\kappa^2} + \Delta \right)^{\nu}$ .

2. Key Properties

The resulting kernels exhibit several distinct properties:

Sparsity: For integer $\nu$ and sparse graphs, the precision matrices are sparse, enabling efficient computation similar to GMRFs.
Non-Uniform Variance: Unlike stationary Euclidean kernels, the prior variance of graph Matérn GPs varies across vertices, depending on the global graph structure (e.g., return times of random walks) rather than just local node degrees.
Convergence: The graph Matérn kernels converge to the graph diffusion kernel as $\nu \to \infty$ . Furthermore, under appropriate regularity conditions and edge weighting, these kernels converge to Riemannian Matérn kernels as the graph becomes a finer discretization of a manifold.

3. Scalable Training Techniques

To address computational challenges, the paper proposes two primary training strategies:

Graph Fourier Feature Approximation: The kernel matrix is approximated using a truncated eigenvalue expansion of the graph Laplacian. This relates the GP to a Bayesian linear regression model with orthogonal features, allowing for efficient inference.
Sparse Precision Matrices: By restricting $\nu$ to small integers, the authors exploit the sparsity of the precision matrix. This allows the use of established GMRF inference algorithms.
Non-Conjugate Settings: For tasks like classification where the posterior is non-Gaussian, the authors employ doubly stochastic variational inference using inducing points. They also discuss interdomain inducing variables using kernel eigenvectors to further accelerate training.

Key Contributions

Definition of Graph Matérn Kernels: The paper establishes a rigorous definition of Matérn GPs on undirected graphs via SPDE generalization, providing a flexible alternative to existing graph kernels.
Theoretical Properties: It demonstrates that these kernels inherit attractive properties from their Euclidean and Riemannian counterparts, including convergence to manifold kernels and connections to random walks.
Scalable Inference: The work provides practical techniques for training these models on large graphs, including Fourier feature approximations and sparse linear algebra methods compatible with standard variational inference frameworks (e.g., inducing points).
Empirical Validation: The authors validate the approach on two distinct tasks: probabilistic interpolation of traffic flow data on a road network and multi-class classification on a scientific citation network.

Results

The authors evaluate the proposed Graph Matérn GPs against other graph kernels, including the diffusion kernel, random walk kernel, and inverse cosine kernel.

Traffic Interpolation: In predicting traffic flow speeds on a San Jose highway network, the model successfully captures both global dependencies and local structural nuances (e.g., distinguishing between opposite sides of a road that are Euclidean-close but graph-distant).
Citation Classification: On the Cora citation network, the model achieved high accuracy in classifying scientific topics based solely on citation structure, outperforming or matching baseline kernels in low-data regimes.
Comparative Performance: Table 1 in the paper indicates that the flexible Matérn class yields performance similar to or slightly improved over alternative kernels (diffusion, random walk) in terms of RMSE for regression and accuracy for classification.

Significance and Claims

The paper claims that Graph Matérn GPs offer a flexible, interpretable, and performant framework for learning on graphs. By leveraging the SPDE characterization, the authors bridge the gap between continuous manifold learning and discrete graph learning.

The significance lies in making graph GPs more accessible to practitioners:

They can be trained using standard methods (e.g., inducing points, variational inference) rather than bespoke algorithms.
They support mini-batch training and non-conjugate settings (like classification), which were previously difficult to implement for graph GPs.
They provide a principled way to substitute for manifold Matérn kernels when the underlying manifold is represented as a graph (e.g., output of manifold learning algorithms).

The authors conclude that these techniques aim to inspire broader adoption of Gaussian processes in machine learning applications involving graph-structured data.