arxiv: 2605.11987 · v1 · submitted 2026-05-12 · 💻 cs.AI · cs.LG· stat.AP· stat.ML

Recognition: 2 theorem links

· Lean Theorem

Random-Set Graph Neural Networks

Davide Bacciu, Fabio Cuzzolin, Matteo Tolloso, Shireen Kudukkil Manchingal, Tommy Woodley

Pith reviewed 2026-05-13 05:11 UTC · model grok-4.3

classification 💻 cs.AI cs.LGstat.APstat.ML

keywords graph neural networksepistemic uncertaintybelief functionsrandom setsuncertainty quantificationgraph classificationautonomous driving

0 comments

The pith

Graph neural networks can output finite random sets over classes to separately derive probability predictions and node-level epistemic uncertainty.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proposes modeling epistemic uncertainty in Graph Neural Networks through a belief-function formalism that represents uncertainty as finite random sets. A dedicated head in the network predicts such a random set for each node over the possible classes. From this output both a precise class probability and a quantitative measure of epistemic uncertainty are extracted. Experiments across nine graph datasets, including real-world autonomous driving scenes, indicate that this yields better uncertainty estimates than conventional GNN approaches.

Core claim

By equipping a GNN with a belief-function head that predicts a random set over the list of classes, the model produces both a precise probability prediction and a direct measure of epistemic uncertainty arising from incomplete knowledge of graph topology or node features.

What carries the argument

The belief-function head that outputs a finite random set over classes, from which probability and epistemic uncertainty are derived within the random-set formalism of belief function theory.

If this is right

Both accurate class probabilities and separate epistemic uncertainty values are obtained directly from the same random-set prediction.
Epistemic uncertainty arising from graph topology or node representations can be quantified at the node level.
The approach shows improved uncertainty quantification performance across nine graph datasets that include autonomous driving benchmarks.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same random-set head could be attached to other neural architectures to model epistemic uncertainty in non-graph settings.
In safety-critical applications such as autonomous driving, the explicit uncertainty output might support more conservative planning when epistemic uncertainty is high.
Combining the random-set output with existing aleatoric uncertainty estimators could yield a fuller uncertainty picture for graph data.

Load-bearing premise

The finite random set formalism accurately represents node-level epistemic uncertainty in GNNs without introducing modeling artifacts and the reported gains hold under controlled comparisons.

What would settle it

A controlled re-run of the nine-dataset experiments in which the RS-GNN uncertainty scores show no better correlation with actual prediction errors or out-of-distribution failures than the baseline uncertainty methods.

Figures

Figures reproduced from arXiv: 2605.11987 by Davide Bacciu, Fabio Cuzzolin, Matteo Tolloso, Shireen Kudukkil Manchingal, Tommy Woodley.

**Figure 2.** Figure 2: Overview of the Random-Set Graph Neural Network (RS-GNN). RS-GNN replaces the softmax layer with a belief head that outputs a mass function mv over a budgeted collection of focal sets F (singletons plus selected subsets). From the predicted mass function we derive (i) a pignistic probability vector BetPv for point prediction and (ii) singleton lower and upper probabilities defining the induced credal set. … view at source ↗

**Figure 3.** Figure 3: This figure presents the best-performing RS-GNN configuration for each dataset, providing [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗

**Figure 4.** Figure 4: Distribution of RS-GNN AUROC scores across datasets, showing variability in uncertainty [PITH_FULL_IMAGE:figures/full_fig_p015_4.png] view at source ↗

**Figure 5.** Figure 5: The results indicate that the choice of focal set has a measurable effect on both performance [PITH_FULL_IMAGE:figures/full_fig_p016_5.png] view at source ↗

**Figure 6.** Figure 6: These results allow us to distinguish between AUROC and ID accuracy for the ablation [PITH_FULL_IMAGE:figures/full_fig_p017_6.png] view at source ↗

read the original abstract

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

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

RS-GNN adds a belief-function head to GNNs for node-level epistemic uncertainty via random sets, but the abstract supplies almost no equations or controls, leaving the separation from aleatoric effects and the reported gains on NuScenes unverified.

read the letter

The paper's central move is to replace the usual softmax head on a GNN with a belief-function layer that outputs a random set over classes. From that set you can read off both a precise probability and a separate epistemic-uncertainty score. They run the thing on nine graph datasets, two of them real autonomous-driving graphs, and say the uncertainty numbers come out better than standard baselines. That framing is the genuinely new piece; most prior GNN uncertainty work stays inside probabilistic or ensemble methods, so the finite-random-set route is a clear departure. The motivation also lands: epistemic uncertainty really does matter when graphs are incomplete or topologies are uncertain, and safety-critical uses like driving need a usable signal for it. The experiments on NuScenes and ROAD at least show they tried to move beyond toy citation graphs. The weak link is exactly what the stress-test note flags. Without any displayed equations for how the belief masses are formed or how the head is trained, it is impossible to tell whether the random-set output isolates lack of knowledge or simply re-expresses the GNN's internal correlations and over-smoothing effects. The abstract also gives no baseline list, no metric definitions for the uncertainty part, and no error analysis, so the claim of superiority rests on an unshown comparison. If the full paper contains a clean derivation that keeps the masses independent of message-passing artifacts, that would change the picture; right now the evidence is too thin to judge. This is for people already working on uncertainty quantification inside graph models, especially those who need to plug something into downstream decision systems. A reader who wants to see whether belief functions can be made to work on graphs will find the experiments worth looking at, but only after the method section is examined. I would send it to peer review. The topic is live, the application area is real, and the idea is distinct enough that referees should check the derivations and the controls rather than desk-reject on the abstract alone.

Referee Report

2 major / 2 minor

Summary. The manuscript proposes Random-Set Graph Neural Networks (RS-GNN) that incorporate a belief-function head based on finite random set theory to model node-level epistemic uncertainty in GNNs. The head outputs a random set over classes from which both precise class probabilities and an epistemic uncertainty measure are derived. Experiments on nine graph datasets, including autonomous-driving benchmarks NuScenes and ROAD, are reported to demonstrate superior uncertainty quantification.

Significance. If the central claims hold under rigorous controls, the work would provide a principled integration of Dempster-Shafer belief functions with GNN message passing, offering a formal representation of epistemic ignorance that standard softmax or ensemble methods do not supply. This could be valuable for safety-critical graph tasks where distinguishing reducible model uncertainty from irreducible data noise improves downstream decision making.

major comments (2)

[Belief-function head (methods)] The abstract and methods description assert that the belief-function head isolates epistemic uncertainty without artifacts from GNN message passing or parametrization, yet no explicit equations or derivation are supplied showing how the random-set masses are computed from node embeddings independently of graph-induced correlations (e.g., over-smoothing or missing edges). This is load-bearing for the central claim.
[Experiments] The experimental section claims superiority on nine datasets including NuScenes and ROAD, but the abstract supplies neither the precise baselines, metrics (e.g., AUROC, ECE, or set-valued accuracy), nor ablation studies that would confirm the random-set head outperforms standard GNN uncertainty methods under matched computational budgets.

minor comments (2)

[Abstract] The abstract contains the typo 'Nuscene' (should be NuScenes) and the awkward phrasing 'as such Nuscene and ROAD'.
[Notation] Notation for the random-set masses and the mapping from belief functions to point probabilities should be introduced with a short table or explicit formulas to aid readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their constructive and detailed feedback on our manuscript. We address each major comment point by point below and have incorporated revisions to strengthen the presentation and rigor of the work.

read point-by-point responses

Referee: [Belief-function head (methods)] The abstract and methods description assert that the belief-function head isolates epistemic uncertainty without artifacts from GNN message passing or parametrization, yet no explicit equations or derivation are supplied showing how the random-set masses are computed from node embeddings independently of graph-induced correlations (e.g., over-smoothing or missing edges). This is load-bearing for the central claim.

Authors: We appreciate the referee's identification of this key point. The belief-function head is applied to the final node embeddings produced by the GNN, with the random-set masses computed via a dedicated parametrization that models epistemic ignorance at the output level. However, we acknowledge that the manuscript would benefit from greater explicitness on this separation. In the revised version, we will add a dedicated derivation subsection (new Section 3.3) providing the full equations for mass function computation directly from the embedding vector, with a clear statement that no additional graph-structure terms are introduced at this stage. This will clarify independence from message-passing artifacts such as over-smoothing. revision: yes
Referee: [Experiments] The experimental section claims superiority on nine datasets including NuScenes and ROAD, but the abstract supplies neither the precise baselines, metrics (e.g., AUROC, ECE, or set-valued accuracy), nor ablation studies that would confirm the random-set head outperforms standard GNN uncertainty methods under matched computational budgets.

Authors: We agree that the abstract could more explicitly summarize the experimental design to aid quick assessment. The full experimental section (Section 4) already reports results against baselines including standard GNN+softmax, MC-Dropout, and deep ensembles, using metrics such as AUROC for uncertainty quantification, ECE for calibration, and set-valued accuracy for the random-set outputs, along with ablation studies. To address the comment directly, we will revise the abstract to concisely list these elements and expand the experiments section with an additional paragraph and table explicitly comparing performance under matched computational budgets (e.g., similar parameter counts and inference times). revision: yes

Circularity Check

0 steps flagged

No circularity: belief-function head defined independently of outputs

full rationale

The paper proposes an original framework in which a belief-function head predicts a random set over classes, from which precise probabilities and an epistemic uncertainty measure are obtained. This construction is presented as a new modeling choice grounded in finite random set formalism from belief function theory, with no equations or definitions in the abstract or description showing that the random-set masses or uncertainty measure are fitted to or defined in terms of the target predictions themselves. Experiments on nine datasets are reported as validation, not as part of the derivation. No self-citation chains, uniqueness theorems, or ansatzes are invoked in the provided text to justify the central step. The derivation therefore remains self-contained and does not reduce to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract provides no explicit free parameters, axioms, or invented entities; the random-set representation is introduced as part of the new framework but without further specification.

pith-pipeline@v0.9.0 · 5503 in / 1182 out tokens · 59394 ms · 2026-05-13T05:11:24.949639+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation washburn_uniqueness_aczel unclear
RS-GNN replaces the classical softmax layer of a GNN with a belief-output layer that predicts mass functions over a budgeted collection of focal sets... credal set width Wv = P̄v(ŷv) − Pv(ŷv)
IndisputableMonolith/Foundation/RealityFromDistinction reality_from_one_distinction unclear
node-level epistemic uncertainty is modelled in a belief function (finite random set) formalism

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages · 2 internal anchors

[1]

Epistemic deep learning.arXiv preprint arXiv:2206.07609,

Shireen Kudukkil Manchingal and Fabio Cuzzolin. Epistemic deep learning.arXiv preprint arXiv:2206.07609,

work page arXiv
[2]

Epistemic deep learning: Enabling machine learning models to know when they do not know.arXiv preprint arXiv:2510.22261,

Shireen Kudukkil Manchingal. Epistemic deep learning: Enabling machine learning models to know when they do not know.arXiv preprint arXiv:2510.22261,

work page arXiv
[4]

Bayesian neural networks: An introduction and survey

Ethan Goan and Clinton Fookes. Bayesian neural networks: An introduction and survey. InCase Studies in Applied Bayesian Data Science: CIRM Jean-Morlet Chair, Fall 2018, pages 45–87. Springer,

work page 2018
[5]

Uncertainty in graph neural networks: A survey.arXiv preprint arXiv:2403.07185, 2024b

Fangxin Wang, Yuqing Liu, Kay Liu, Yibo Wang, Sourav Medya, and Philip S Yu. Uncertainty in graph neural networks: A survey.arXiv preprint arXiv:2403.07185, 2024b. Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles.Advances in neural information processing systems, 30,

work page arXiv
[6]

Deep-ensemble-based uncertainty quantification in spatiotemporal graph neural networks for traffic forecasting.arXiv preprint arXiv:2204.01618,

Tanwi Mallick, Prasanna Balaprakash, and Jane Macfarlane. Deep-ensemble-based uncertainty quantification in spatiotemporal graph neural networks for traffic forecasting.arXiv preprint arXiv:2204.01618,

work page arXiv
[7]

Credal graph neural networks.arXiv preprint arXiv:2512.02722,

Matteo Tolloso and Davide Bacciu. Credal graph neural networks.arXiv preprint arXiv:2512.02722,

work page arXiv
[8]

The intersection probability: betting with probability intervals.arXiv preprint arXiv:2201.01729,

Fabio Cuzzolin. The intersection probability: betting with probability intervals.arXiv preprint arXiv:2201.01729,

work page arXiv
[9]

Credal deep ensembles for uncertainty quantification.Advances in Neural Information Processing Systems, 37: 79540–79572, 2024c

Kaizheng Wang, Fabio Cuzzolin, Keivan Shariatmadar, David Moens, Hans Hallez, et al. Credal deep ensembles for uncertainty quantification.Advances in Neural Information Processing Systems, 37: 79540–79572, 2024c. Kaizheng Wang, Fabio Cuzzolin, Keivan Shariatmadar, David Moens, and Hans Hallez. A review of uncertainty representation and quantification in n...

work page arXiv
[10]

Random-set neural networks

Shireen Kudukkil Manchingal, Muhammad Mubashar, Kaizheng Wang, Keivan Shariatmadar, and Fabio Cuzzolin. Random-set neural networks. InThe Thirteenth International Conference on Learning Representations, 2025a. URLhttps://openreview.net/forum?id=pdjkikvCch. Shireen Kudukkil Manchingal, Armand Amaritei, Mihir Gohad, Maryam Sultana, Julian FP Kooij, Fabio Cu...

work page arXiv
[11]

Credal and interval deep evidential classifications.arXiv preprint arXiv:2512.05526,

Michele Caprio, Shireen K Manchingal, and Fabio Cuzzolin. Credal and interval deep evidential classifications.arXiv preprint arXiv:2512.05526,

work page arXiv
[12]

Creinns: Credal-set interval neural networks for uncertainty estimation in classification tasks.Neural Networks, 185:107198, 2025b

Kaizheng Wang, Keivan Shariatmadar, Shireen Kudukkil Manchingal, Fabio Cuzzolin, David Moens, and Hans Hallez. Creinns: Credal-set interval neural networks for uncertainty estimation in classification tasks.Neural Networks, 185:107198, 2025b. Kaizheng Wang, Fabio Cuzzolin, Keivan Shariatmadar, David Moens, and Hans Hallez. Credal wrapper of model averagin...

work page arXiv
[13]

doi: 10.1007/978-1-4612-1942-2_11

ISBN 978-1-4612-7350-9. doi: 10.1007/978-1-4612-1942-2_11. David Ross. Random sets without separability.Annals of Probability, 14(3):1064–1069, July

work page doi:10.1007/978-1-4612-1942-2_11 1942
[14]

Reasoning with random sets: An agenda for the future.arXiv preprint arXiv:2401.09435,

Fabio Cuzzolin. Reasoning with random sets: An agenda for the future.arXiv preprint arXiv:2401.09435,

work page arXiv
[15]

Belief likelihood function for generalised logistic regression.arXiv preprint arXiv:1808.02560, 2018a

Fabio Cuzzolin. Belief likelihood function for generalised logistic regression.arXiv preprint arXiv:1808.02560, 2018a. Fabio Cuzzolin.The Geometry of Uncertainty: The Geometry of Imprecise Probabilities. Artificial Intelligence: Foundations, Theory, and Algorithms. Springer International Publishing,

work page arXiv
[16]

Visions of a generalized probability theory.arXiv preprint arXiv:1810.10341, 2018b

Fabio Cuzzolin. Visions of a generalized probability theory.arXiv preprint arXiv:1810.10341, 2018b. Philippe Smets and Robert Kennes. The transferable belief model.Artificial intelligence, 66(2): 191–234,

work page arXiv
[17]

Random-set large language models.arXiv preprint arXiv:2504.18085,

Muhammad Mubashar, Shireen Kudukkil Manchingal, and Fabio Cuzzolin. Random-set large language models.arXiv preprint arXiv:2504.18085,

work page arXiv
[18]

Epistemic generative adversarial networks.arXiv preprint arXiv:2603.18348,

Muhammad Mubashar and Fabio Cuzzolin. Epistemic generative adversarial networks.arXiv preprint arXiv:2603.18348,

work page arXiv
[19]

Epistemic wrapping for uncertainty quantification.arXiv preprint arXiv:2505.02277,

Maryam Sultana, Neil Yorke-Smith, Kaizheng Wang, Shireen Kudukkil Manchingal, Muhammad Mubashar, and Fabio Cuzzolin. Epistemic wrapping for uncertainty quantification.arXiv preprint arXiv:2505.02277,

work page arXiv
[20]

Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory

20 Dominik Fuchsgruber, Tom Wollschläger, Johannes Bordne, and Stephan Günnemann. Uncer- tainty estimation for heterophilic graphs through the lens of information theory.arXiv preprint arXiv:2505.22152,

work page internal anchor Pith review Pith/arXiv arXiv
[21]

Uncertainty Quantification on Graph Learning: A Survey

Chao Chen, Chenghua Guo, Rui Xu, Xiangwen Liao, Xi Zhang, Sihong Xie, Hui Xiong, and Philip Yu. Uncertainty quantification on graph learning: A survey.arXiv preprint arXiv:2404.14642,

work page internal anchor Pith review Pith/arXiv arXiv
[22]

Maximilian Stadler, Bertrand Charpentier, Simon Geisler, Daniel Zügner, and Stephan Günnemann

URL https://proceedings.neurips.cc/paper/2020/hash/ 968c9b4f09cbb7d7925f38aea3484111-Abstract.html. Maximilian Stadler, Bertrand Charpentier, Simon Geisler, Daniel Zügner, and Stephan Günnemann. Graph posterior network: Bayesian predictive uncertainty for node classification. InAdvances in Neural Information Processing Systems, volume 34, pages 18033–1804...

work page arXiv 2020
[23]

Pignistic probability transforms for mixes of low-and high-probability events.arXiv preprint arXiv:1505.07751,

John J Sudano. Pignistic probability transforms for mixes of low-and high-probability events.arXiv preprint arXiv:1505.07751,

work page arXiv
[24]

Pitfalls of graph neural network evaluation,

22 Fabio Cuzzolin. Geometry of relative plausibility and relative belief of singletons.Annals of Mathematics and Artificial Intelligence, 59(1):47–79, 2010c. Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation.arXiv preprint arXiv:1811.05868,

work page arXiv
[25]

A critical look at the evaluation of GNNs under heterophily: Are we re- ally making progress?.arXiv preprint arXiv:2302.11640,

Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look at the evaluation of gnns under heterophily: Are we really making progress?arXiv preprint arXiv:2302.11640,

work page arXiv
[26]

Enhancing the reliability of out-of-distribution image detection in neural networks.arXiv preprint arXiv:1706.02690,

Shiyu Liang, Yixuan Li, and Rayadurgam Srikant. Enhancing the reliability of out-of-distribution image detection in neural networks.arXiv preprint arXiv:1706.02690,

work page arXiv
[27]

How attentive are graph attention networks?arXiv preprint arXiv:2105.14491,

Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks?arXiv preprint arXiv:2105.14491,

work page arXiv
[28]

URL http://arxiv.org/abs/2206.10691. 23

work page arXiv