Uncertainty Estimation on Graphs with Structure Informed Stochastic Partial Differential Equations
Fred Xu, Thomas Markovich · 2025
Read Uncertainty Estimation on Graphs with Structure Informed Stochastic Partial Differential Equations by Fred Xu, Thomas Markovich (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-06907.txt.
Introduction
Fred Xu and Thomas Markovich design a message-passing scheme for networks that knows its own uncertainty. Their paper is from two thousand twenty-five. Graph neural networks learn from data arranged as nodes and links. They are strong predictors, but they rarely say how unsure they are, above all when new data differs from training data.
The authors borrow from a branch of math that models random change over space and time. In their scheme, each pass between nodes carries noise shaped by that theory. A dial controls how smooth the shared uncertainty is across the graph. Tests on out-of-sample detection beat past methods on graphs with both weak and strong label signals. The method captures doubt from both the graph shape and its labels.
Catalog record
| CREATOR | Fred Xu, Thomas Markovich |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 96 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-06907
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Uncertainty Estimation on Graphs with Structure Informed Stochastic Partial Differential Equations Fred Xu, Thomas Markovich Abstract Graph Neural Networks (GNNs) have achieved impressive results across diverse network modeling tasks, but accurately estimating uncertainty on graphs remains difficult—especially under distributional shifts. Unlike traditional uncertainty estimation, graph-based uncertainty must account for randomness arising from both the graph’s structure and its label distribution, which adds complexity. In this paper, making an analogy between the evolution of a stochastic partial differential equation (SPDE) driven by Matérn Gaussian Process and message passing using GNN layers, we present a principled way to design a novel message passing scheme that incorporates spatial-temporal noises motivated by the Gaussian Process approach to SPDE. Our method simultaneously captures uncertainty across space and time and allows explicit control over the covariance kernel’s smoothness, thereby enhancing uncertainty estimates on graphs with both low and high label informativeness. Our extensive experiments on Out-of-Distribution (OOD) detection on graph datasets with varying label informativeness demonstrate the soundness and superiority of our model to existing approaches. 1 Introduction Uncertainty Estimation is crucial to developing reliable machine learning systems, now deployed in safety-critical fields such as healthcare Habli2020ArtificialII , medicine Basile2019ArtificialIF , and financial modeling Giudici2023SAFEAI . This task usually handles uncertainty from the lack of data samples and the inherent randomness in the data generating process Gal2016UncertaintyID and has traditionally been addressed for i.i.d data using energy based models song2021trainenergybasedmodels , Bayesian learning framework charpentier2020posteriornetworkuncertaintyestimation , or stochastic process to inject random noise into model learning kong2020sdenetequippingdeepneural ; thiagarajan2022singlemodeluncertaintyestimation . Already a challenging problem, Uncertainty Estimation when applied to graph data, requires even more consideration on the dependency between nodes and even substructures on a graph. For graph data, Graph Neural Networks (GNNs) have been the standard model, leading state-of-art performance on many graph related learning tasks. By aggregating information from neighbors, GNNs are able to learn meaningful representations of nodes efficiently Kipf2016SemiSupervisedCW ; Velickovic2017GraphAN . Despite their superior performance, GNNs can generate overly confident predictions on tasks even when making the wrong predictions stadler2021graphposteriornetworkbayesian . Recently many works have attempted to address uncertainty estimation for graph data in the similar manners as i.i.d data, using the Bayesian framework stadler2021graphposteriornetworkbayesian , energy based model fuchsgruber2024energybasedepistemicuncertaintygraph ; wu2023energybasedoutofdistributiondetectiongraph , or through injecting noise in model training using a stochastic process lin2024_graph ; bergna2023graphneuralstochasticdifferential . Despite some remarkable progresses, these models assume that nodes that are close-by in the graph should share similar uncertainty, which often connects to the concept of graph homophily wu2023energybasedoutofdistributiondetectiongraph ; lin2024_graph . However, in cases such as low label informativeness platonov2024characterizinggraphdatasetsnode , nodes that are close to each other often have different labels distribution patterns, resulting in the phenomenon that knowing the neighborhood labels doesn’t decrease uncertainty of center node’s label. luan2024heterophilicgraphlearninghandbook ; luan2024heterophilyspecificgnnshomophilymetrics . When graphs exhibit low label informativeness, tasks like node classification become more difficult for traditional GNNs, and so is uncertainty estimation: when labels that are close by are uninformative, GNNs that are poorly calibrated either generate incorrect predictions with high certainty or cannot capture the pattern at all platonov2024criticallookevaluationgnns ; platonov2024characterizinggraphdatasetsnode . (a) Matérn Kernel on a Heterophilic Graph (b) Structure Informed SPDE Figure 1 : (a) Graph Matérn kernel with varying degrees of smoothness \nu : for low \nu , the Gaussian random field is rough, with higher variance for each node and higher correlation between nodes. Red links are high correlation edges that do not exist in the original graph. (b) Our proposed Structure Informed SPDE (SISPDE) to incorporate spatial correlations between node uncertainty (section 3 ): Gaussian noises between nodes are correlated according to the Matérn Gaussian Random Field. This potential difficulty has not been addressed by previous works but has been raised by many existing works as future directions wu2023energybasedoutofdistributiondetectiongraph ; lin2024_graph ; fuchsgruber2024energybasedepistemicuncertaintygraph . In this paper, we directly address this challenge by proposing a message passing scheme on GNN that explicitly models the dependency between uncertainty of nodes through a spatially-correlated stochastic partial differential equation (SPDE) (Figure 1 (b)) hairer2023introductionstochasticpdes . In particular, we extend the basic framework of Q -Wiener process from lin2024_graph , which uses the graph Laplacian to model spatial correlation, to a Matérn Gaussian process on graph borovitskiy2021materngaussianprocessesgraphs . With this construction, we can explicitly regulate the smoothness of the spectrum used to represent the Brownian motion on graph, creating covariance structures that can capture long-distance dependencies between uncertainties of nodes. We further provide theoretical analysis for the construction and demonstrate the existence and uniqueness of mild solution of the underlying SPDE. We conduct extensive experiments on Out-of-Distribution (OOD) Detection on 8 graph datasets with varying degrees of label informativeness to demonstrate our model’s effectiveness. The main contribution of this paper are: (1) we introduce a physics-inspired way to perform message passing on graph with spatially-correlated noise to improve uncertainty estimation, even under low label-informativeness. (2) We extend the Q -Wiener process on graph to a smoothness-regulated, spatially-correlated noise process and analyze its property and the theoretical implication for the underlying stochastic process on graph. (3) We provide an efficient implementation of this general framework, conduct extensive experiments on standard uncertainty estimation tasks, and provide detailed ablations and visualizations for the properties of designed covariance structure. Empirical results and thorough analyses demonstrate our model’s novelty and superiority compared with previous approaches. 2 Background 2.1 Uncertainty Estimation on Graph Data Let G=(V,E) be a graph, where V is the set of vertices and E the set of edges, then a semi-supervised node classification problem can be formulated by (1) partitioning the graph nodes: V=\mathcal{T}\cup\mathcal{U} , where v\in\mathcal{T} are the set of nodes with labels and u\in\mathcal{U} are the set of nodes without labels, and (2) train a GNN model to predict the labels of u\in\mathcal{U} using the final node features after T rounds of message passing. Denote node features as \mathbf{X} and \mathbf{H}^{(T)} as feature after T rounds of message passing, then the classification results depend on P(y\mid\mathbf{H}^{(T)}) . Traditionally, predictive uncertainty can be measured by (a) adopting an energy-based model perspective ( wu2023energybasedoutofdistributiondetectiongraph ; fuchsgruber2024energybasedepistemicuncertaintygraph ) on the classifier, (b) formulating a Bayesian perspective and compute the entropy of the posterior predictive distribution ( stadler2021graphposteriornetworkbayesian ) , and (c) formulating the message passing GNN as a stochastic process and compute an expected Shannon entropy H[\mathbb{E}[p(y\mid\mathbf{H}(T))]] . In this paper, we investigate approach (c), which allows for a principled design of GNN architecture and explicit modeling of both aleatoric uncertainty and epistemic uncertainty through P(\mathbf{H}(T)) and \mathbb{E}_{P(\mathbf{H}(T))}[H[P(y\mid\mathbf{H}(T))]] , respectively ( kong2020sdenetequippingdeepneural ; lin2024_graph ) . 2.2 Label Informativeness Traditionally for node classification tasks, graph datasets were divided into homophilic and heterophilic datasets, where similar nodes are more likely to be connected in the former and less likely to be connected in the later case luan2024heterophilicgraphlearninghandbook . While it occurred that classical GNNs perform poorly on heterophilic datasets, it has been recently discovered that fine-tuning can address the issue without relying on heterophilic-specific methods luan2024heterophilicgraphlearninghandbook ; platonov2024characterizinggraphdatasetsnode ; platonov2024criticallookevaluationgnns , leading to design of metrics that better characterize node classification difficulty. Among the newly proposed metrics, Label Informativeness (LI) leverages the mutual information framework and better characterizes the structural distribution of graph labels. For two nodes i,j\in V and their