Research map / Graph learning / GNN architectures

Random-Set Graph Neural Networks

NeurIPS 2026 · Graph learning › GNN architectures · approach: GNN generalization theory · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes Random-Set Graph Neural Networks (RS-GNN), replacing the softmax head of a GNN with a belief-function head that predicts masses over budgeted focal sets, for node-level epistemic uncertainty and OOD detection.

Problem

Standard GNN softmax classifiers collapse epistemic ambiguity into point estimates over known classes, yielding confident errors on structurally novel or conflicting nodes, which hurts OOD detection and calibration.

Approach

Node-level belief-function (random-set) head with sigmoid-predicted belief values over a budgeted focal-set family, converted to masses via Möbius inversion and to pignistic probabilities; epistemic uncertainty is the credal-set width of the predicted class, trained with BCE in belief space plus mass-validity regularisation.

Key results

• On the nine-benchmark OOD table, RS-GNN attains the best AUROC on Amazon-Ratings (51.05) and second-best on Chameleon (84.18 credal) and ArXiv (70.21 credal), but CaGCN and GNNSafe remain stronger on several datasets such as Coauthor and Reddit2.
• On the ROAD held-out OOD setting, RS-GNN raises entropy AUROC from 0.425 (vanilla) to 0.662 and reaches credal-width AUROC 0.342, while ID accuracy is comparable (0.746 vs 0.754).
• On nuScenes held-out OOD, RS-GNN improves ID accuracy from 0.418 to 0.593 and entropy AUROC from 0.463 to 0.500, with credal-width AUROC 0.521.

Surprising findings

• The authors report that the singletons-only focal-set ablation achieves the highest mean AUROC, and that BCE-only variants differ only marginally from margin-regularised ones.
• Vanilla softmax entropy collapses to near-random detection on nuScenes (AUROC 0.463) and to AUROC about 0.001 in the cross-dataset ROAD-to-nuScenes setting.

Limitations

• Results are mixed: RS-GNN is not uniformly superior, with baselines such as CaGCN, GNNSafe and the classical ensemble winning on several datasets, and performance varies with focal-set configuration.
• Message passing is not itself belief-based; the belief head is only applied at the output, as the authors note as future work.
• Cross-dataset OOD (ROAD to nuScenes) remains poor, with RS-GNN entropy AUROC of 0.053.

Experimental setup

Datasets: Coauthors Chameleon Squirrel Reddit2 ArXiv Roman Empire Amazon-Ratings Cora Patents ROAD nuScenes

Benchmarks: Chameleon Squirrel ArXiv Patents Amazon-Ratings Roman Empire Coauthor Reddit2 Cora ROAD nuScenes

Metrics: AUROC AUPRC FPR95 accuracy ECE NLL Brier score

Baselines: Energy KNN ODIN Mahalanobis GNNSafe Classical ensemble JLDE GEBM CaGCN Credal ensemble CredalLJ Vanilla GNN softmax

Builds on: Random-Set Neural Networks GATv2 GNNSafe Dempster-Shafer belief theory

Closest papers by meaning

• Accurate and Scalable Estimation of Epistemic Uncertainty for Graph Neural Networks (ICLR 2024 · similarity 0.88)
• A Unified Uncertainty Representation for Graph Neural Networks via Doubly-Spectral Stochastic Expansion (NeurIPS 2026 · similarity 0.88)
• Energy-based Epistemic Uncertainty for Graph Neural Networks (NeurIPS 2024 · similarity 0.87)
• Random-Set Neural Networks (ICLR 2025 · similarity 0.87)
• Two Heads Are Better Than One: Boosting Graph Sparse Training via Semantic and Topological Awareness (ICML 2024 · similarity 0.87)
• Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory (ICML 2025 · similarity 0.87)