cs.LGNov 2, 2026

Strictly proper scoring rules for node selection tasks on graphs

Authors: Lorenz Hilfiker, Nathan Cincera Brack, Martin Sterchi

Organizations: University of Applied Sciences and Arts Northwestern Switzerland FHNW · University of Zurich

Abstract

In node selection tasks, the goal is to identify a single unknown target node in a graph. We consider probabilistic supervised node selection, where the estimator outputs a probability distribution over the nodes of the graph and the ground-truth node is available for evaluation. Classical evaluation metrics for such tasks are either statistically ill-conceived or blind to the graph structure. To fill this gap, we introduce two strictly proper scoring rules that are explicitly graph-aware: the Resistance score, which is parameter-free, and the Diffusion score, which operates at an adjustable coarse-graining resolution. We show that the Diffusion score interpolates between the multi-category Brier score and a cluster-level weighted Brier score. The Resistance score generalises two classical scoring rules: the multi-category Brier score and the Ranked probability score. Applied to rooted trees, it also serves as the strictly proper version of the improper Hierarchical error distance used in hierarchical classification. In the same setting, we furthermore establish strict propriety of the Hierarchical cross-entropy family, a recently introduced separate class of hierarchy-aware scoring rules. Experiments on epidemic source detection and on ImageNet classification confirm that the proposed scores detect meaningful differences in estimation quality that classical metrics miss.

Figures & tables

Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Not All Nodes Are Created Equal: Homophily-Aware Stratification for Stable GNN Evaluation

    Sep 16, 2026Naga Venkata Sai Jitin Jami, Thomas Altstidl, Sebastian Hoefler +4Graph Neural NetworksNode Classification

  2. Closed-Form Node Classification with Exact Graph Unlearning

    May 25, 2026Aditya Gaur, Charu SharmaGraph Representation LearningPrivacy-Preserving ML