Graph-aware scoring rules improve node selection evaluation accuracy
Strictly proper scoring rules for node selection tasks on graphs
Machine LearningSocial and Information Networks
Summary
Identifying the right node in a network is tricky, especially when judging how good guesses are. The authors created new ways to score guesses that understand the network’s layout better than older methods. These scores, called Resistance and Diffusion, give fairer feedback by considering the graph's structure. They tested these scores in spotting sources of outbreaks and recognizing images, finding that their methods spot differences others miss.
What this means in practice
- •For epidemic response teams: Evaluate and improve probabilistic models that identify outbreak origins more precisely by using graph-aware scoring rules.
- •For computer vision developers: Enhance image classification by assessing predictions with scoring rules sensitive to semantic hierarchies in label graphs.
Authors
Lorenz Hilfiker, Nathan Cincera Brack, Martin Sterchi
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.