Source-linked AI summary
Random-Set Graph Neural Networks
Tommy Woodley, Shireen Kudukkil Manchingal, Matteo Tolloso, Davide Bacciu, Fabio Cuzzolin
TL;DR
GNNs need reliable epistemic uncertainty estimates because uncertainty can arise from noisy node features and ambiguous or novel graph structure. RS-GNN assigns node-level belief functions over class sets, yielding both a pignistic probability prediction and an epistemic uncertainty measure. Experiments across nine graph datasets report improved uncertainty quantification, including real-world autonomous-driving benchmarks.
Problem
Reliable epistemic uncertainty quantification is challenging for GNNs because graph uncertainty can arise from noisy features and ambiguous or novel structure.
Source: §1 · pp. 1–2Method
RS-GNN replaces the softmax output with node-level belief functions over class sets, from which it derives pignistic predictions and a measure of epistemic uncertainty.
Source: §1 · p. 3Results
Across nine graph datasets, RS-GNN demonstrates superior uncertainty quantification capabilities, including on the nuScenes and ROAD autonomous-driving benchmarks.
Source: §6 · p. 17Takeaways & Limitations
RS-GNN provides a framework for epistemic uncertainty quantification in node classification and OOD detection on graph-structured data.
Source: §1 · p. 3Full integration of belief-function representations into the GNN message-passing core remains a natural next step.
Source: §6 · p. 17
Abstract
from arXiv · showhide
Uncertainty quantification has become an important factor in understanding the data representations produced by Graph Neural Networks (GNNs). Despite their predictive capabilities being ever useful across industrial workspaces, the inherent uncertainty induced by the nature of the data is a huge mitigating factor to GNN performance. While aleatoric uncertainty is the result of noisy and incomplete stochastic data such as missing edges or over-smoothing, epistemic uncertainty arises from lack of knowledge about a system or model (e.g., a graph's topology or node feature representation), which can be reduced by gathering more data and information. In this paper, we propose an original new framework in which node-level epistemic uncertainty is modelled in a belief function (finite random set) formalism. The resulting Random-Set Graph Neural Networks have a belief-function head predicting a random set over the list of classes, from which both a precise probability prediction and a measure of epistemic uncertainty can be obtained. Extensive experiments on 9 different graph learning datasets, including real-world autonomous driving benchmarks as such Nuscene and ROAD, demonstrate RS-GNN's superior uncertainty quantification capabilities
1 Introduction
Reliable epistemic uncertainty estimation is a central challenge for GNNs because graph uncertainty can arise from both noisy features and ambiguous structure. RS-GNN brings belief-function learning to node-level graph predictions, aiming to represent epistemic uncertainty while supporting classification and OOD detection.
Motivation
- In safety-critical settings, reliable epistemic uncertainty quantification matters because erroneous predictions can have severe consequences and models should recognize limits in their knowledge.Epistemic uncertainty is described as uncertainty arising from limited knowledge about the data-generating process.Source: §1 · p. 1
Graph-specific challenge
- Graph uncertainty can arise from noisy node features, ambiguous neighborhoods, or novel structural context, making its sources relevant to robust OOD detection.The paper distinguishes aleatoric uncertainty from neighborhood ambiguity and epistemic uncertainty from structural context insufficiently represented in training data.Source: §1 · pp. 1–2
Existing approaches
- Bayesian GNNs can model uncertainty over parameters and graph structure but often add computational overhead and require specified priors; ensembles scale poorly and retain first-order probability representations.Credal graph methods provide set-valued predictions and uncertainty decompositions, but remain within the space of probability distributions.Source: §1 · p. 2
Random-set background
- Random sets assign probability mass to outcome subsets and, on finite domains, yield belief functions that induce a convex set of consistent probability distributions.Earlier random-set neural networks assume independent data, whereas graph message passing violates that assumption and brings graph-specific information propagation challenges.Source: §1 · p. 2
Contributions
- RS-GNN extends random-set neural learning to graphs with node-level belief functions, pignistic predictions, and credal-set geometry for epistemic uncertainty.Its contributions also include budgeted focal-set selection for scalability and experiments reporting competitive classification with more reliable uncertainty estimates and improved OOD detection.Source: §1 · p. 3
2 Related Work
The related work groups GNN uncertainty methods into deterministic models, Bayesian approaches, and ensembles, each with different modeling and computational trade-offs.
Single Deterministic Models
- Deterministic methods range from softmax confidence and entropy heuristics to evidential Dirichlet models and energy-based approaches, with differing calibration and retraining properties.Post-hoc calibration and Graph Energy-Based Models are described as not requiring retraining.Source: §2 · p. 3
Bayesian Graph Neural Networks
- Bayesian GNNs place uncertainty over weights and graph elements such as edges, features, or propagation, but typically cost more computationally and require carefully designed priors.Approaches include adaptive connection sampling, Monte Carlo Dropout, variational inference, and Graph Posterior Networks.Source: §2 · pp. 3–4
Ensemble Methods
- Ensembles quantify uncertainty through disagreement across independently trained GNNs and can perform strongly, but require training and maintaining multiple models.This creates computational and memory overhead.Source: §2 · p. 4
3 Methodology
RS-GNN assigns belief functions to individual nodes and uses a belief-function head, uncertainty measures, and belief-space training to support node classification and OOD detection.
3.1 Approach: Node-level representation
- Node-level belief assignments localize epistemic uncertainty to each node’s features and structural context, supporting fine-grained OOD detection and calibrated decisions.The paper contrasts this with graph-level beliefs for graph classification and edge-level beliefs, which it says add complexity without improving node classification.Source: §3.1 · p. 4
3.2 Belief function head
- RS-GNN uses a budgeted focal-set collection containing singleton classes and selected subsets, then derives mass values and a pignistic probability from predicted beliefs.The pignistic probability gives a central prediction, while the belief function induces a credal set; mass validity is encouraged through non-negativity and normalization regularization.Source: §3.2 · pp. 4–5, Figure 2 · p. 5
3.3 Uncertainty quantification
- Pignistic entropy measures predictive uncertainty, while credal-set width—the probability-interval width for a singleton class—measures epistemic uncertainty.The interval width is its upper probability bound minus its lower bound.Source: §3.3 · pp. 5–6
3.4 Loss function and training
- Training uses a target belief encoding that assigns belief 1 to class sets containing the ground-truth label, with binary cross-entropy over focal sets as the primary loss.Regularization penalizes negative mass values and deviations from normalization in the final objective.Source: §3.4 · p. 6
4.1 Datasets
The evaluation suite comprises nine benchmark graph datasets spanning different domains and structural properties, with node-classification tasks defined by each dataset’s features and labels.
Dataset scope
- The evaluation covers nine benchmark graph datasets selected for varied domains and structural properties.The listed datasets include Coauthors, Chameleon, Squirrel, Reddit2, ArXiv, Roman Empire, Amazon-Ratings, Cora, and Patents.Source: §4.1 · pp. 6–7
Dataset characteristics
- The benchmarks span co-authorship, Wikipedia, Reddit, citation, word-dependency, and product networks, with tasks such as predicting fields, traffic categories, subreddits, publication years, syntactic roles, ratings, topics, and patent grant dates.Node features include keyword, text, title-and-abstract, word, and metadata representations.Source: §4.1 · pp. 6–7
Dataset caveat
- Chameleon and Squirrel have been criticized for train-test leakage from duplicate nodes, although they remain widely used.Source: §4.1 · p. 6
4.2 Setting
The setting tests node-level OOD detection on a single attributed graph using a leave-out-class training strategy. The model is trained on ID classes and should classify them while assigning high uncertainty to OOD nodes.
4.2 Setting
- The protocol uses a single attributed graph whose node classes are partitioned into disjoint ID and OOD sets.Source: §4.2 · p. 7
- OOD classes are masked during training, so supervision covers only ID classes while test nodes may belong to either ID or OOD classes.The test-class set is therefore a superset of the training classes.Source: §4.2 · p. 7
- The task combines classifying in-distribution nodes with producing high uncertainty scores for nodes from OOD classes.Source: §4.2 · p. 7
4.3 Baselines
The evaluation compares the proposed approaches with post-hoc, nearest-neighbor, graph-specific, and ensemble baselines. The Classical Ensemble is the reference method to outperform.
4.3 Baselines
- Baselines include Energy, ODIN, CaGCN, Mahalanobis, and KNN methods, alongside graph-specific GNNSafe and GEBM.The methods use logits, perturbations, calibration, latent-space distances, or graph-specific designs, as described in the passage.Source: §4.3 · p. 7
- The Classical Ensemble is the de-facto reference for uncertainty quantification, with performance across tasks and datasets motivating it as the target to outperform.It independently trains multiple standard models.Source: §4.3 · p. 7
- The Classical Ensemble combines high performance with practical simplicity, effective scaling, and few hyperparameters.Its stated requirement is independent training of multiple standard models.Source: §4.3 · p. 7
4.4 Random-Set Graphs for Road Scene Understanding
This section evaluates random-set representations for uncertainty-aware graph learning, focusing on risk-aware road-scene perception and uncertainty quality alongside predictive performance. It considers how effectiveness varies with dataset properties, configuration, and focal-set construction, including challenges under extreme cross-dataset shift.
4.4.1 Datasets and Temporal Graph Construction
- ROAD temporal graphs connect scene nodes to agents and link scene and same-agent nodes across adjacent frames; nuScenes graphs use eight object categories and the same graph-building pipeline.The evaluation uses temporal windows on both datasets and includes rare ROAD classes and interaction patterns relevant to epistemic uncertainty.Source: §4.4.1 · pp. 8–9
4.4.2 Models: What They Do for Road Scene Understanding
- RS-GNN replaces the softmax head’s forced singleton-class probabilities with non-singleton focal-set masses, representing ambiguity and increasing uncertainty signals for OOD detection.A pignistic projection supplies point predictions for accuracy and calibration; the shared backbone isolates the output representation as the key difference.Source: §4.4.2 · p. 9
4.4.3 Training and Leave-Out-Class Protocol
- Training excludes OOD-labeled nodes: ROAD holds out classes {8, 9}, nuScenes {6, 7}, while cross-dataset evaluation trains on ROAD classes and tests nuScenes as OOD.The section evaluates both within-dataset leave-out-class OOD and ROAD(ID)-nuScenes(OOD) shift.Source: §4.4.1 · p. 8, §4.4.3 · pp. 9–10
4.4.4 Backbone and Training Details
- A two-layer GATv2 encoder with 128 hidden units feeds a belief head using 74 ROAD and 72 nuScenes focal sets, including up to 64 non-singletons.RS-GNN uses belief-space binary cross-entropy with mass-validity regularization; its compact set representation is compatible with mini-batch training without global graph normalization.Source: §4.4.4 · pp. 10–11
4.4.5 Evaluation Protocol
- Evaluation reports ID accuracy and calibration metrics, plus OOD AUROC, AUPRC, and FPR95 using entropy and RS-GNN’s predicted-class credal width.Mean credal width is also reported separately on ID and OOD nodes.Source: §4.4.5 · p. 12
4.4.6 Results
- RS-GNN reached nuScenes accuracy 0.593 versus 0.418 (Vanilla) and NLL 2.079 versus 7.047; on ROAD, accuracy was 0.746 versus 0.754 and ECE 0.132 versus 0.178.In the ROAD(ID)-nuScenes(OOD) setting, RS-GNN ID accuracy was 0.770 versus 0.751, while Vanilla had slightly better ECE and NLL on ROAD alone.Source: §4.4.6 · pp. 12–13, Table 6 · p. 13
- On ROAD held-out OOD, entropy AUROC rose from 0.425 (Vanilla) to 0.662 (RS-GNN), while RS-GNN credal-width AUROC was 0.342.The reported results indicate that RS-GNN improves entropy-based detection but that absolute performance remains moderate.Source: Table 7 · p. 13, §4.4.6 · p. 13
- On nuScenes held-out OOD, entropy AUROC was 0.463 (Vanilla) versus 0.500 (RS-GNN), with RS-GNN credal-width AUROC 0.521; cross-dataset values were ≈0.001 versus 0.053 and 0.083.For the cross-dataset setting, the first two values are entropy AUROC for Vanilla and RS-GNN, respectively, and 0.083 is RS-GNN credal-width AUROC; detection remained challenging.Source: Table 7 · p. 13, §4.4.6 · p. 13
- Focal-set construction is part of model capacity: small-class datasets use all non-empty subsets, while larger label spaces use a budgeted family because the full power set is impractical.The passage states that uncertainty-estimate quality depends partly on the expressiveness of the focal-set family.Source: §4.4.6 · p. 14
- Configurations with the highest OOD AUROC did not always achieve the highest ID accuracy, so selecting random-set configurations requires joint evaluation of both criteria.This trade-off is reported across patents, reddit2, and roman empire.Source: §4.4.6 · p. 14
- Dataset diversity tests the method under varying task conditions, including less conventional graph regimes in squirrel and chameleon and a larger citation setting in arxiv.Patents and reddit2 test uncertainty estimation on complex data; cora provides a smaller standard benchmark, while roman empire, amazon ratings, and coauthor add topology, label-structure, and task-difficulty diversity.Source: §4.4.6 · pp. 14–15
- RS-GNN is not uniformly superior across graph domains, but offers structured uncertainty representation whose strengths emerge when both predictive performance and uncertainty quality are evaluated across diverse datasets.The passage names patents, reddit2, cora, roman empire, squirrel, chameleon, arxiv, coauthor, and amazon ratings.Source: §4.4.6 · p. 15
5 Ablation studies
The ablations attribute RS-GNN’s effectiveness primarily to its belief-function representation, while focal-set design and training objective have meaningful secondary roles. Results also show trade-offs among AUROC, stability, expressiveness, and computational efficiency.
5 Ablation studies
- Standard focal sets achieve the highest observed AUROC with more consistent results, while singleton-only sets have the highest mean AUROC but greater variability.Multi-class subsets in standard focal sets can represent partial knowledge when evidence does not strongly support one class.Source: §5 · pp. 15–16, Figure 5 · p. 16
- 0.6070 and 0.5777 are the mean AUROC values for standard focal sets with BCE and with BCE plus margin regularisation, respectively.The authors report lower overall performance for both BCE-based variants and describe the full belief-space objective as better aligned with the uncertainty framework.Source: §5 · p. 16
- Lightweight focal-set configurations may trade some peak AUROC for lower computational cost, especially where full focal-set enumeration is infeasible.The performance gap relative to reduced or singleton-based focal sets is described as relatively small.Source: §5 · pp. 15–16
- High test accuracy does not necessarily correspond to better uncertainty estimation: AUROC varies more across configurations than accuracy.Figure 6 distinguishes AUROC from ID accuracy in the ablation studies.Source: §5 · p. 17, Figure 6 · p. 17
- Some configurations have comparable peak performance but differ in mean AUROC, indicating differences in sensitivity to initialization and training dynamics.The results therefore emphasize consistency across runs alongside best-case performance.Source: §5 · p. 17
- RS-GNN’s effectiveness is attributed primarily to its belief-function representation, with focal-set design and training objective playing secondary but meaningful roles.The study compares singleton-only and standard focal sets, plus alternative training objectives, on cora and roman empire.Source: §5 · pp. 15, 17
6 Conclusions
RS-GNN models node-level epistemic uncertainty with a belief-function head that predicts a finite random set over classes. Experiments across nine graph-learning datasets show superior uncertainty-quantification capabilities, while integrating belief functions into message passing remains a next step.
6 Conclusions
- Across 9 graph-learning datasets, including NuScenes and ROAD, RS-GNN demonstrates superior uncertainty-quantification capabilities.Source: §6 · p. 17
- RS-GNN models node-level epistemic uncertainty with a belief-function head predicting a finite random set over classes.Source: §6 · p. 17
- The head yields a precise probability prediction via the pignistic transform and epistemic uncertainty via class-probability interval sizes.Source: §6 · p. 17
- Full integration of belief-function representations into GNN message passing is identified as the natural next step.Source: §6 · p. 17