Strictly proper scoring rules for node selection tasks on graphs
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.
Related
- Learning Probabilistic Filters with Strictly Proper Scoring Rules
- Proper scoring rules for survival times
- A Strictly Proper Scoring-Rule Theory for Calibrating Stochastic Car-Following Models
- Matrix-Aware Proper Scoring Rules and Significance Testing for Correlation and Covariance Forecasts in Python
- Classification of strictly resistance nonnegative graphs
BibTeX
@misc{hilfiker2026strictly,
title = {{Strictly proper scoring rules for node selection tasks on graphs}},
author = {Lorenz Hilfiker and Nathan Cincera Brack and Martin Sterchi},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.03274},
eprint = {2611.03274},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.03274},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Strictly proper scoring rules for node selection tasks on graphs
AU - Lorenz Hilfiker
AU - Nathan Cincera Brack
AU - Martin Sterchi
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.03274
UR - https://arxiv.org/abs/2611.03274
AB - 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.
ER -