Uncertainty Estimation on Graphs with Structure Informed Stochastic Partial Differential Equations

• URL: http://arxiv.org/abs/2506.06907v1
• Date: Sat, 07 Jun 2025 19:58:38 GMT
• Title: Uncertainty Estimation on Graphs with Structure Informed Stochastic Partial Differential Equations
• Authors: Fred Xu, Thomas Markovich,
• Abstract summary: Graph Neural Networks have achieved impressive results across diverse network modeling tasks, but accurately estimating uncertainty on graphs remains difficult.<n>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.<n>Our method simultaneously captures uncertainty across space and time and allows explicit control over the covariance kernel smoothness, thereby enhancing uncertainty estimates on graphs with both low and high label informativeness.
• Score: 0.9591674293850556
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph Neural Networks 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 Matern 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 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.

Related papers

• On the Stability of Graph Convolutional Neural Networks: A Probabilistic Perspective [24.98112303106984]
  We study how perturbations in the graph topology affect GCNN outputs and propose a novel formulation for analyzing model stability.<n>Unlike prior studies that focus only on worst-case perturbations, our distribution-aware formulation characterizes output perturbations across a broad range of input data.
  arXiv  Detail & Related papers  (2025-06-01T23:17:19Z)
• Uncertainty Modeling in Graph Neural Networks via Stochastic Differential Equations [14.422150854883453]
  We introduce Latent Graph Neural Differential Equations (LGNSDE) to address the problem of learning uncertainty-aware representations for graph-structured data.<n>We prove that the variance of the latent space bounds the variance of model outputs, thereby providing theoretically sensible guarantees for the uncertainty estimates.<n>Our framework is competitive in out-of-distribution detection, robustness to noise, and active learning, underscoring the ability of LGNSDEs to quantify uncertainty reliably.
  arXiv  Detail & Related papers  (2024-08-28T19:59:58Z)
• Data-heterogeneity-aware Mixing for Decentralized Learning [63.83913592085953]
  We characterize the dependence of convergence on the relationship between the mixing weights of the graph and the data heterogeneity across nodes. We propose a metric that quantifies the ability of a graph to mix the current gradients. Motivated by our analysis, we propose an approach that periodically and efficiently optimize the metric.
  arXiv  Detail & Related papers  (2022-04-13T15:54:35Z)
• Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations [57.15855198512551]
  We propose a novel score-based generative model for graphs with a continuous-time framework. We show that our method is able to generate molecules that lie close to the training distribution yet do not violate the chemical valency rule.
  arXiv  Detail & Related papers  (2022-02-05T08:21:04Z)
• Handling Distribution Shifts on Graphs: An Invariance Perspective [78.31180235269035]
  We formulate the OOD problem on graphs and develop a new invariant learning approach, Explore-to-Extrapolate Risk Minimization (EERM) EERM resorts to multiple context explorers that are adversarially trained to maximize the variance of risks from multiple virtual environments. We prove the validity of our method by theoretically showing its guarantee of a valid OOD solution.
  arXiv  Detail & Related papers  (2022-02-05T02:31:01Z)
• Bayesian Graph Contrastive Learning [55.36652660268726]
  We propose a novel perspective of graph contrastive learning methods showing random augmentations leads to encoders. Our proposed method represents each node by a distribution in the latent space in contrast to existing techniques which embed each node to a deterministic vector. We show a considerable improvement in performance compared to existing state-of-the-art methods on several benchmark datasets.
  arXiv  Detail & Related papers  (2021-12-15T01:45:32Z)
• OOD-GNN: Out-of-Distribution Generalized Graph Neural Network [73.67049248445277]
  Graph neural networks (GNNs) have achieved impressive performance when testing and training graph data come from identical distribution. Existing GNNs lack out-of-distribution generalization abilities so that their performance substantially degrades when there exist distribution shifts between testing and training graph data. We propose an out-of-distribution generalized graph neural network (OOD-GNN) for achieving satisfactory performance on unseen testing graphs that have different distributions with training graphs.
  arXiv  Detail & Related papers  (2021-12-07T16:29:10Z)
• Distributionally Robust Semi-Supervised Learning Over Graphs [68.29280230284712]
  Semi-supervised learning (SSL) over graph-structured data emerges in many network science applications. To efficiently manage learning over graphs, variants of graph neural networks (GNNs) have been developed recently. Despite their success in practice, most of existing methods are unable to handle graphs with uncertain nodal attributes. Challenges also arise due to distributional uncertainties associated with data acquired by noisy measurements. A distributionally robust learning framework is developed, where the objective is to train models that exhibit quantifiable robustness against perturbations.
  arXiv  Detail & Related papers  (2021-10-20T14:23:54Z)
• Robust Graph Learning Under Wasserstein Uncertainty [35.85333465732067]
  In many scenarios, an accurate graph structure representing signals is not available at all. We propose a graph learning framework using Wasserstein distributionally robust optimization (WDRO) We show that our scheme can learn a reliable graph in the context of uncertainty.
  arXiv  Detail & Related papers  (2021-05-10T09:09:44Z)
• Stochastic Graph Recurrent Neural Network [6.656993023468793]
  We propose SGRNN, a novel neural architecture that applies latent variables to simultaneously capture evolution in node attributes and topology. Specifically, deterministic states are separated from states in the iterative process to suppress mutual interference. Experiments on real-world datasets demonstrate the effectiveness of the proposed model.
  arXiv  Detail & Related papers  (2020-09-01T16:14:30Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.