Evidential Uncertainty Probes for Graph Neural Networks

Linlin Yu, Kangshuo Li, Pritom Kumar Saha, Yifei Lou, Feng Chen

Introduction

Graph Neural Networks (GNNs) have become the standard for modeling structured data in domains ranging from drug discovery to fraud detection. However, a significant hurdle to their deployment in high-stakes environments is their tendency toward overconfidence. Standard GNNs often provide high-probability predictions even when faced with out-of-distribution (OOD) data or inherent noise. While Evidential Deep Learning (EDL) has emerged as a promising solution for quantifying uncertainty in a single forward pass, existing EDL-based GNNs require specialized architectures and must be trained from scratch. This prevents the use of high-performing, pre-trained GNNs already available in the field.

The Evidential Probing Network (EPN)

To bridge this gap, researchers have developed the Evidential Probing Network (EPN), a "plug-and-play" framework that adds reliable uncertainty quantification to pre-trained GNNs without the need for expensive retraining. The core philosophy of EPN is to treat the pre-trained GNN as a fixed feature extractor. A lightweight Multi-Layer Perceptron (MLP) "probe" is attached to the hidden representations of the model, focusing entirely on learning the mapping of these features to "evidence."

Core Components and Methodology

  1. Evidential Learning: Instead of predicting a single probability vector via a softmax layer, the EPN predicts the parameters of a Dirichlet distribution. This allows the model to treat predictions as a collection of evidence gathered from the data, enabling the separation of Aleatoric uncertainty (noise inherent in the data) from Epistemic uncertainty (the model’s lack of knowledge regarding new classes).
  2. EPN-reg (Regularization): The authors identified that standard training often fails to distinguish between in-distribution (ID) and OOD samples. They introduced two novel regularization techniques:
  3. Intra-Class Evidence-Based (ICE): This distills class-label information into the latent space, forcing samples of the same class to cluster together and increasing the "evidence" for known patterns.
  4. Positive-Confidence Learning (PCL): This uses the pre-trained model’s own confidence as a "weak supervisor," pushing the probe to assign high evidence to confident ID samples and low evidence to everything else.
  5. Uncertainty Propagation: To leverage the structural information of the graph, the framework utilizes propagation schemes (such as vacuity-prop) to ensure that neighboring nodes share similar uncertainty levels.

Theoretical Justification

A critical insight of this research is the theoretical proof that standard Uncertainty Cross-Entropy (UCE) loss can reach its minimum even if it fails to correctly order uncertainty between ID and OOD samples. This finding explains why previous methods often struggled with OOD detection and justifies the necessity of the ICE and PCL regularizations introduced in the EPN-reg framework.

Experimental Evaluation

The framework was evaluated across eight diverse graph datasets, including citation networks (CoraML, CiteSeer, PubMed), co-purchase networks (AmazonPhotos, AmazonComputers), and large-scale benchmarks like OGBN-Arxiv. The researchers tested these across five different "Left-Out-Classes" (LOC) settings to simulate various real-world OOD scenarios.

Key Results

  • State-of-the-Art Performance: EPN-reg ranked in the top two for OOD detection in 60 out of 150 tested cases, consistently outperforming baselines like GPN and specialized EDL-GNNs.
  • Computational Efficiency: On the large-scale OGBN-Arxiv dataset, EPN achieved a 5x speedup in training time compared to the next best model. By training only a small MLP head, it bypasses the heavy computational cost of training deep graph layers.
  • Versatility: The method proved robust across different GNN backbones (such as GCN and GAT) and various activation functions, making it a truly model-agnostic solution.

Conclusion and Future Work

The Evidential Probing Network offers a scalable and efficient way to equip existing GNNs with uncertainty awareness. While the current work focuses on node classification, the authors suggest that the framework could be extended to other graph tasks like link prediction or graph-level classification. Furthermore, the "probing" approach holds potential for broader deep learning architectures in computer vision and natural language processing, where pre-trained models are ubiquitous but uncertainty quantification remains a challenge.

Summary updated

BibTeX
@inproceedings{yu2025evidential,
  author = {Linlin Yu and Kangshuo Li and Pritom Kumar Saha and Yifei Lou and Feng Chen},
  title = {{Evidential Uncertainty Probes for Graph Neural Networks}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2025},
  url = {https://openreview.net/forum?id=qVDnA4BdCc},
}
Figure