Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory

2025/05/28 by Dominik Fuchsgruber, Fuchsgruber, Dominik, Tom Wollschläger +5 · 1 citation
Computer Science · #Advanced Graph Neural Networks #Adversarial Robustness in Machine Learning #Explainable Artificial Intelligence (XAI) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Social and Information Networks (cs.SI)

paper · pdf · doi:10.48550/arxiv.2505.22152

openalex publication_date 2025/05/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

While uncertainty estimation for graphs recently gained traction, most methods rely on homophily and deteriorate in heterophilic settings. We address this by analyzing message passing neural networks from an information-theoretic perspective and developing a suitable analog to data processing inequality to quantify information throughout the model's layers. In contrast to non-graph domains, information about the node-level prediction target can increase with model depth if a node's features are semantically different from its neighbors. Therefore, on heterophilic graphs, the latent embeddings of an MPNN each provide different information about the data distribution - different from homophilic settings. This reveals that considering all node representations simultaneously is a key design principle for epistemic uncertainty estimation on graphs beyond homophily. We empirically confirm this with a simple post-hoc density estimator on the joint node embedding space that provides state-of-the-art uncertainty on heterophilic graphs. At the same time, it matches prior work on homophilic graphs without explicitly exploiting homophily through post-processing.

Citations

• SGS-GNN: A Supervised Graph Sparsification method for Graph Neural Networks
• Energy-based Epistemic Uncertainty for Graph Neural Networks
• GATE: How to Keep Out Intrusive Neighbors
• Revisiting the Message Passing in Heterophilous Graph Neural Networks
• Transitional Uncertainty with Layered Intermediate Predictions
• Uncertainty for Active Learning on Graphs
• Accurate and Scalable Estimation of Epistemic Uncertainty for Graph Neural Networks
• Accurate and Scalable Estimation of Epistemic Uncertainty for Graph Neural Networks
• When Do Graph Neural Networks Help with Node Classification? Investigating the Impact of Homophily Principle on Node Distinguishability
• A critical look at the evaluation of GNNs under heterophily: Are we really making progress?
• Energy-based Out-of-Distribution Detection for Graph Neural Networks
• Revisiting Heterophily For Graph Neural Networks
• Characterizing Graph Datasets for Node Classification: Homophily-Heterophily Dichotomy and Beyond
• Single Model Uncertainty Estimation via Stochastic Data Centering
• Towards OOD Detection in Graph Classification from Uncertainty Estimation Perspective
• Finding Global Homophily in Graph Neural Networks When Meeting Heterophily
• Deep Deterministic Uncertainty for Semantic Segmentation
• Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods
• Graph Posterior Network: Bayesian Predictive Uncertainty for Node Classification
• Nested Graph Neural Networks
• A Survey of Uncertainty in Deep Neural Networks
• Exploring the Limits of Out-of-Distribution Detection
• How Attentive are Graph Attention Networks?
• Improving Graph Neural Networks with Simple Architecture Design
• Deep Deterministic Uncertainty: A Simple Baseline
• On Feature Collapse and Deep Kernel Learning for Single Forward Pass Uncertainty
• Beyond Low-frequency Information in Graph Convolutional Networks
• Node Similarity Preserving Graph Convolutional Networks
• Uncertainty Aware Semi-Supervised Learning on Graph Data
• Energy-based Out-of-distribution Detection
• Machine Learning for Reliability Engineering and Safety Applications: Review of Current Status and Future Opportunities
• Machine learning for reliability engineering and safety applications: Review of current status and future opportunities
• Adaptive Universal Generalized PageRank Graph Neural Network
• Gaussian Processes on Graphs via Spectral Kernel Learning
• Bayesian Graph Neural Networks with Adaptive Connection Sampling
• Simple and Principled Uncertainty Estimation with Deterministic Deep Learning via Distance Awareness
• Posterior Network: Uncertainty Estimation without OOD Samples via Density-Based Pseudo-Counts
• Efficient and Scalable Bayesian Neural Nets with Rank-1 Factors
• Geom-GCN: Geometric Graph Convolutional Networks
• Your Classifier is Secretly an Energy Based Model and You Should Treat it Like One
• DropEdge: Towards Deep Graph Convolutional Networks on Node Classification
• Fast Graph Representation Learning with PyTorch Geometric
• Pitfalls of Graph Neural Network Evaluation
• Bayesian Semi-supervised Learning with Graph Gaussian Processes
• Evidential Deep Learning to Quantify Classification Uncertainty
• Predictive Uncertainty Estimation via Prior Networks
• On Calibration of Modern Neural Networks
• Inductive Representation Learning on Large Graphs
• Simple and Scalable Predictive Uncertainty Estimation using Deep Ensembles
• Semi-Supervised Classification with Graph Convolutional Networks
• Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learning
• Weight Uncertainty in Neural Networks
• Deep Learning and the Information Bottleneck Principle
• VERIFICATION OF FORECASTS EXPRESSED IN TERMS OF PROBABILITY

Cited by

• Credal Graph Neural Networks

Related

• Linear Opinion Pooling for Uncertainty Quantification on Graphs
• Credal Graph Neural Networks
• A Graph Is More Than Its Nodes: Towards Structured Uncertainty-Aware Learning on Graphs
• Accurate and Scalable Estimation of Epistemic Uncertainty for Graph Neural Networks
• Graph Posterior Network: Bayesian Predictive Uncertainty for Node Classification