Random-Set Graph Neural Networks

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

Read Random-Set Graph Neural Networks by Tommy Woodley, Shireen Kudukkil Manchingal, Matteo Tolloso, Davide Bacciu, Fabio Cuzzolin (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-11987.txt.

Introduction

Tommy Woodley and four colleagues model node-level epistemic uncertainty in graph neural networks with belief functions. Noise-driven uncertainty comes from noisy, incomplete data, while knowledge-gap uncertainty reflects missing facts about topology or features and shrinks as more data arrives. Their Random-Set Graph Neural Networks use a belief-function head that predicts a random set over classes, giving both a sharp probability forecast and a knowledge-gap score. Tests on nine graph datasets showed better uncertainty scores.

Catalog record

CREATORTommy Woodley, Shireen Kudukkil Manchingal, Matteo Tolloso, Davide Bacciu, Fabio Cuzzolin
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE61180
LICENSEhttp://creativecommons.org/licenses/by-sa/4.0/
RIGHTSCC BY SA
SOURCEarXiv

Source: https://arxiv.org/abs/2605.11987

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Random-Set Graph Neural Networks Tommy Woodley, Shireen Kudukkil Manchingal, Matteo Tolloso, Davide Bacciu, Fabio Cuzzolin 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. 1 Introduction Machine learning systems are increasingly deployed in safety-critical domains, where erroneous predictions may lead to severe consequences. In such settings, it is not sufficient for a model to be accurate; it must also be aware of its own limitations; in other words, to know when it does not know ( 65 ; 70 ) . A central obstacle to trustworthy deployment is the reliable quantification of epistemic uncertainty , the uncertainty arising from limited knowledge about the data-generating process ( 52 ; 50 ) . This challenge is particularly acute for Graph Neural Networks (GNNs) ( 84 ) . Unlike classical learning in which data points are i.i.d. (independent and identically distribute), graph data exhibits strong relational dependencies between instances: uncertainty, therefore, can originate not only from noisy node features but also from structural ambiguity in the graph topology ( 53 ; 104 ) . A node may be uncertain because its neighborhood is inherently ambiguous (aleatoric uncertainty), or because its structural context is novel and insufficiently represented in the training data (epistemic uncertainty). Topological uncertainties are a factor in signal processing ( 10 ) , wireless networks ( 13 ) and multi-agent systems ( 114 ) , to cite just a few examples. Disentangling these sources is essential for robust out-of-distribution (OOD) detection ( 112 ) and reliable graph learning ( 39 ; 102 ) . Bayesian approaches provide a principled lens for this decomposition by marginalizing predictions over a posterior distribution of model parameters ( 62 ) . In Graph Neural Networks, Bayesian variants place distributions over weights and, in some cases, over graph structure itself ( 47 ; 76 ) . However, Bayesian Graph Neural Networks often incur substantial computational overhead and require carefully specified priors ( 40 ; 103 ) . Ensemble-based approaches offer a practical alternative by measuring disagreement across independently trained models ( 54 ; 63 ) , yet they scale poorly and remain limited to first-order probability representations. Recent work has explored credal learning on graphs ( 101 ) , where models output probability intervals ( 35 ; 79 ; 14 ; 21 ; 32 ) forming a credal set ( 9 ; 106 ) . While credal methods provide expressive set-valued predictions and principled uncertainty decompositions, they operate within the space of probability distributions. A recent review of uncertainty quantification in neural networks can be found in ( 108 ) . A recent wave of results in classification, uncertainty quantification and out-of-distribution detection using both random-set ( 68 ; 69 ; 70 ; 64 ; 67 ) and credal set representations ( 7 ; 83 ; 9 ; 8 ; 109 ; 107 ; 105 ) , is providing significant evidence that second-order uncertainty theory ( 31 ; 34 ) is a most promising framework for tackling the above challenges (as also supported by the results of the recent Epistemic AI ( 15 ) Horizon 2020 project 1 1 1 https://www.epistemic-ai.eu/ 2 2 2 https://cordis.europa.eu/project/id/964505/results ). Random sets ( 77 ; 81 ; 93 ; 66 ; 33 ; 41 ; 45 ) , in particular, offer a more fundamental representation of epistemic uncertainty. A random set is a set-valued random variable that assigns probability mass directly to subsets of outcomes ( 72 ; 73 ; 71 ; 85 ) . On finite domains, random sets take the form of belief functions ( 26 ; 27 ; 28 ; 30 ) , which generalize classical probability measures and naturally induce a convex set of consistent probability distributions (a credal set) ( 57 ; 29 ) . In the recently proposed Random-Set Neural Networks (RS-NN) 69 , predictions are expressed as belief functions over the class list, encoding epistemic uncertainty through the size and geometry of the associated credal set. A point prediction can then be recovered via the pignistic transformation ( 91 ) , corresponding geometrically to the center of mass of the credal set. The approach has recently been extended to large language models ( 75 ) , generative adversarial networks ( 74 ) and Dirichlet random-set representations in a network’s parameter space ( 99 ) . While RS-NNs have demonstrated strong performance in image classification and OOD detection, their formulation assumes independent data. Extending random-set learning to graphs, therefore, introduces new conceptual and technical challenges. Message passing in GNNs violates the i.i.d. assumption by construction, and information about a node’s label is progressively gained and lost across layers ( 36 ) . In heterophilic graphs, where connected nodes may belong to different classes, smoothing mechanisms can blur class boundaries and exacerbate epistemic uncertainty ( 116 ; 59 ) . A random-set formulation must therefore account for the distinctive dynamics of graph information propagation. While message passing in the form of belief functions has been studied in the early Nineties, mostly by Shenoy and Shafer ( 88 ; 87 ; 89 ) , the problem has been never tackled from a machine learning perspective. In this paper, we introduce Random-Set Graph Neural Networks (RS-GNNs) , the first framework to extend random-set neural learning to the graph domain. 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. Each node is thus mapped to a belief function, which is mathematically equivalent to a credal set of probability distributions on the class list. The pignistic probability provides a central prediction, while the geometry of the induced credal set quantifies epistemic uncertainty. Our approach inherits the theoretical advantages of random sets, namely, the ability to model second-order uncertainty without committing to a precise probability distribution, while adapting them to graph-structured data. By integrating belief-function outputs with message-passing representations, RS-GNN provides a principled and scalable framework for epistemic uncertainty quantification in node classification and OOD detection. Main Contributions. Our contributions are threefold: (i) we introduce Random-Set Graph Neural Networks (RS-GNNs), extending belief-function learning to graph-structured data; (ii) we develop a budgeted focal-set selection strategy compatible with graph representations, ensuring scalability to large class spaces; and (iii)

Read the complete text