Random-Set Graph Neural Networks

Graph Neural Networks deployed in safety-critical settings must recognise when a node's neighborhood is structurally novel, conflicting, or underrepresented in the training graph; standard softmax classifiers collapse this epistemic ambiguity into a point estimate over known classes, producing confident errors on unseen structure. We propose Random-Set Graph Neural Networks (RS-GNN), a framework that replaces the softmax head of any message-passing backbone with a belief function over a budgeted family of focal sets. Each node is mapped to a mass function whose pignistic projection yields the point prediction and whose induced credal-set width quantifies epistemic uncertainty. Focal sets are selected from class-overlap statistics in the learned node-embedding space, making the budget graph-aware rather than uniform over the power set. Across nine node-classification benchmarks spanning homophilic and heterophilic regimes (Cora, Coauthor, Reddit2, ArXiv, Patents, Chameleon, Squirrel, Roman Empire, Amazon-Ratings), RS-GNN matches or outperforms strong probabilistic, ensemble, and credal baselines (including Classical Ensemble, GEBM, and CaGCN) on leave-out-class OOD detection, reaching AUROC of 88.84 on Cora and 84.18 on Chameleon. On temporal road-scene graphs constructed from ROAD and nuScenes, RS-GNN improves nuScenes node-classification accuracy from 0.418 to 0.593 and avoids the overconfidence collapse that softmax heads exhibit under cross-dataset shift. These results indicate that credal-set width recovers an epistemic signal that scalar softmax-derived scores cannot, particularly when graph evidence is incomplete or out of distribution.