Uncertainty in Graph Neural Networks: A Survey

Fangxin Wang, Yuqing Liu, Kay Liu, Yibo Wang, Sourav Medya, Philip S. Yu

Introduction

Graph Neural Networks (GNNs) have revolutionized the modeling of relational data, yet their deployment in safety-critical applications remains limited. A primary hurdle is their tendency to produce overconfident, erroneous predictions without any measure of reliability. This survey provides the first comprehensive roadmap for navigating uncertainty in GNNs, establishing a unified framework to transform these "black boxes" into trust-aware systems for applications like drug discovery and traffic forecasting.

A Unified Framework for Uncertainty

The research landscape is organized into a three-stage pipeline: identifying sources, quantifying levels, and utilizing results for downstream tasks.

The three-stage framework for uncertainty in GNNs: Identification (S2), Quantification (S3), and Utilization (S4).

1. Identification: The "Where"

Uncertainty is broadly categorized into two types based on its origin:

  • Aleatoric Uncertainty: Inherent noise in the data (e.g., sensor errors or blurry inputs) that cannot be reduced by further training.
  • Epistemic Uncertainty: The model’s lack of knowledge due to insufficient training data. This is further decomposed into Model Uncertainty (limitations in architecture or parameters) and Distributional Uncertainty (mismatch between training and test data distributions).

2. Quantification: The "How"

The survey categorizes quantification methods into three primary families:

  • Single Deterministic Models: These use simple metrics like softmax probability or entropy. Because GNNs are often miscalibrated, these methods frequently require post-hoc "calibration" to align predicted probabilities with actual accuracy.
  • Stochastic Models (Bayesian GNNs): These treat model weights as probability distributions rather than fixed values (e.g., Monte Carlo Dropout). Dirichlet-based models are highlighted as particularly effective for identifying distributional shifts.
  • Ensemble Methods: These involve training multiple models and using their disagreement as a proxy for uncertainty. While reliable, they are computationally expensive for large-scale graphs.
A comprehensive taxonomy linking uncertainty quantification models, sources, and evaluation metrics.

3. Utilization: The "Why"

Quantified uncertainty is a powerful tool for enhancing GNN performance and reliability in downstream tasks:

  • Active Learning: Selecting the most "informative" nodes for labeling, thereby reducing data requirements.
  • OOD Detection: Flagging data points that the model has not encountered during training, essential for safety in autonomous systems.
  • Robustness: Improving model stability by identifying and ignoring noisy neighbors or edges during graph convolutions.

Key Insights and Challenges

The survey synthesizes several critical findings from across the literature:

  • The Propagation Dilemma: Uncertainty in GNNs is unique because it propagates through the graph structure. A single noisy node or incorrect edge can "infect" the representations of its entire neighborhood.
  • The Under-confidence Trap: Unlike many deep learning models that are overconfident, GNNs often suffer from under-confidence due to their typically shallow structures. This makes calibration a unique and critical challenge for graph-based learning.
  • Uncertainty as a Performance Booster: Uncertainty is not merely a safety check; it is a tool for better learning. For instance, in active learning, uncertainty-guided sample selection can significantly outperform random selection, reaching high accuracy with far less labeled data.

Benchmarks and Future Directions

As a survey, the paper reviews existing benchmarks like the GOOD (Graph Out-of-Distribution) suite and the CardioTox dataset for molecular property prediction. However, several "missing links" remain for future research:

  • Lack of Ground Truth: Evaluating uncertainty is difficult because ground-truth labels for "how uncertain" a sample should be are rarely available.
  • Fine-grained Uncertainty: Future work must distinguish between uncertainty stemming from node features versus the graph's topology (edges).
  • Computational Efficiency: Developing "lightweight" quantification methods is essential for massive, real-time networks where Bayesian or ensemble methods are too slow.

Conclusion

By categorizing types of uncertainty and comparing quantification methods, this survey provides a foundation for building more reliable GNNs. Moving forward, the field must focus on standardized metrics and efficient architectures to bring uncertainty awareness to large-scale, real-world applications.

Summary updated

BibTeX
@article{wang2024uncertainty,
  author = {Fangxin Wang and Yuqing Liu and Kay Liu and Yibo Wang and Sourav Medya and Philip S. Yu},
  title = {{Uncertainty in Graph Neural Networks: A Survey}},
  journal = {Accepted by TMLR},
  year = {2024},
  url = {https://openreview.net/forum?id=0e1Kn76HM1},
}
Figure