betaFeedback

WorksComputer Science

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.

Introduction

Graph learning encompasses a range of tasks, from supervised problems such as graph classification, node classification, or link prediction to unsupervised problems such as community detection. In this paper, we focus on the supervised task of (single) node selection. Whereas node classification assigns class labels to nodes, potentially assigning the same label to multiple nodes, node selection consists of identifying a single node as the output.

Many real-world applications take this form: where did an epidemic or rumour start? Which node should we target to maximise influence? Which node has failed? In other words: node selection subsumes important graph learning problems such as source detection for spreading processes like epidemics or rumours (Shah & Zaman, 2011), optimisation problems such as single-seed influence maximisation [28], or fault detection in communication networks (Ma et al., 2014). Moreover, any edge selection task can be recast as a node selection task on the corresponding line graph. Finally, an important special case is node selection on rooted trees, which naturally captures hierarchical classification (Silla & Freitas, 2011), where class labels are organised according to a hierarchical taxonomy. Applications range from computer vision [11] to natural language processing [31] and bio-informatics (Radivojac et al., 2013).

Most state-of-the-art approaches to node selection tasks are probabilistic (e.g., Monte Carlo methods or graph neural networks). Rather than directly predicting a single node, these methods output a probability distribution over the entire set of nodes. This raises the question of how such probabilistic estimates should be evaluated against the ground truth.

Despite the prevalence of probabilistic node selection methods, there is no consensus on how to evaluate them. Most papers report rank-based metrics such as top-KK accuracy or the rank of the true node (e.g., Lokhov et al. [34]; Altarelli et al. [2]; Antulov-Fantulin et al. [3]; Paluch et al. (2018); Sha et al. (2021)). However, these metrics are unsatisfactory for at least two reasons: (a) they do not take into account the graph structure when assessing how closely an estimate matches the observed true node, and (b) they do not adequately penalise overconfident, yet incorrect, estimates. Existing alternatives such as the Error distance (Antulov-Fantulin et al., [3]; Jiang et al., [26]; Paluch et al., 2018) or the classical multi-category Brier score (Brier, [7]) address either (a) or (b), but neither of them resolves both points simultaneously.

In this paper, we close this gap by proposing evaluation metrics that are both graph-aware – rewarding estimates that place high probability near the true node in a graph sense – and strictly proper – so that the score is uniquely minimised when the estimated distribution matches the true one. We achieve this by bridging ideas from statistics, in particular the concept of kernel scores (Gneiting & Raftery, [18]), with ideas from graph learning (Smola & Kondor, 2003; Fouss et al., [15]) and network science (Devriendt et al., [12]; Villegas et al., 2023).

In the special case of hierarchical classification, hierarchy-aware evaluation metrics have received considerable attention (Silla & Freitas, 2011; Kosmopoulos et al., [31]; Zangari et al., 2024). Threshold-based set-overlap metrics such as Hierarchical precision, recall and F-score (Kiritchenko et al., [29]) and mode-based metrics such as Hierarchical error distance (Russakovsky et al., 2015) are widely used, but they are not proper scores. The only exception known to us is the concurrent and independent work of Urbani et al. (2024), who prove propriety (but not strict propriety) of a family of log-score-type scoring rules for node selection on rooted trees. We extend their result to strict propriety and provide a complementary Brier-type family of scoring rules applicable to general graphs.

Our main contributions are:

  • We provide the first systematic treatment of strictly proper scoring rules for node selection tasks on general graphs that reward estimates based on their proximity to the true node in the graph. We show that existing graph-aware metrics (Error distance, Hierarchical error distance and their variations) are improper.

  • We introduce two strictly proper, graph-aware scoring rules for probabilistic node selection: the Resistance score (parameter-free, based on effective resistance distance) and the Diffusion score (one-parameter family, based on the diffusion kernel).

  • We show that the Resistance score generalises the multi-category Brier score (recovered on the complete graph) and the Ranked probability score (recovered on the path graph), and that, specialised to rooted trees, it is the natural way to turn the improper Hierarchical error distance into a proper score.

The paper is structured as follows. Section 2 formally states the problem, Section 3 provides the necessary statistical background on proper scoring rules, and Section 4 discusses related work. In Section 5, we introduce the Resistance score and the Diffusion score. We discuss their properties, show how they relate to classical proper scoring rules, and illustrate their behaviour on a toy example. Section 5.6 discusses the Resistance score in the context of hierarchical classification, where it provides a strictly proper alternative to widely used but improper metrics such as Hierarchical error distance and distance@KK. Efficient computation of our scores on large graphs is briefly discussed in Section 5.7. Section 6 illustrates the scores on a canonical source detection task. Section 7 presents an empirical evaluation in the standard hierarchical classification setting on ImageNet. We conclude with a discussion of extensions and limitations in Section 8.

Problem Statement

Let G=(V,E)G=(V,E) be a simple graph with node set VV and edge set EE, and let N=∣V∣N=|V|. A node selection task on GG consists of identifying a single unknown node i∈Vi\in V. A probabilistic method for such a task outputs a probability distribution over VV, i.e., an element in the (N−1)(N-1)-dimensional probability simplex

ΔN−1={p∈RN | ∑j=1Npj′=1, pj≥0 ∀j=1,…,N},(1)\Delta^{N-1}=\left\{\mathbf{p}\in\mathbb{R}^{N}\,\middle|\,\sum_{j=1}^{N}p_j'=1,\ p_j\geq0\ \forall j=1,\ldots,N\right\}, \tag*{(1)}

whose component pjp_j denotes the estimated probability that node jj is the true node. This setting subsumes a variety of problems in graph learning and network science. We mention two canonical instances that will serve as examples in the paper:

Source detection. A spreading process (an epidemic, a rumour, a cascade) originates at a single unknown source node i∈Vi\in V and propagates across GG. Given some information about the progression of the spread at some later time, the task is to identify its origin ii. Many methods for this type of inverse problem are probabilistic, issuing a distribution p\mathbf{p} over VV. The graph structure matters when evaluating this task: it is arguably better to miss the true source by a single hop than estimating a node far away from the true source, so a fair evaluation of p\mathbf{p} should take GG into account.

Hierarchical classification. A label taxonomy organises a set of fine-grained classes as the leaf nodes V~⊂V\widetilde{V}\subset V of a rooted tree T=(V,E)T=(V,E), with internal nodes representing progressively coarser superclasses as we move from leaf nodes towards the root. A probabilistic classifier typically outputs a distribution p~∈ΔN~−1\widetilde{\mathbf{p}}\in\Delta^{\widetilde{N}-1} over the N~=∣V~∣\widetilde{N}=|\widetilde{V}| leaf classes for a given input, which can also be viewed as a distribution p∈ΔN−1\mathbf{p}\in\Delta^{N-1} by assigning zero mass to internal nodes. The true label is a single leaf i∈V~i\in\widetilde{V}. The graph structure encodes semantic similarity: for example, in image classification, confusing a Golden Retriever with a Labrador Retriever is a qualitatively different mistake from confusing it with an elephant, and evaluation metrics should reflect this.

In both settings, the central question is the same: given a probabilistic estimate p∈ΔN−1\mathbf{p}\in\Delta^{N-1} and an observed true node i∈Vi\in V, how should we evaluate p\mathbf{p} against ii in a way that is both sensitive to the graph structure of GG and statistically well-justified? We can formalise this challenge as the problem of constructing a scoring rule S(p,i)S(\mathbf{p},i) that is graph-aware and strictly proper.

Background on Proper Scoring Rules

In this section we give a brief overview of the theory of proper scoring rules. For a recent in-depth review of the vast statistical literature on this topic, see for example Waghmare & Ziegel (2025). We restrict our attention to scoring rules for finite outcome spaces.

Throughout this section, let Y\mathcal{Y} be a finite nonempty set of outcomes that we identify with the integers 1,…,N1,\ldots,N, and let p=(p1,…,pN)T∈ΔN−1\mathbf{p}=(p_1,\ldots,p_N)^{\mathsf{T}}\in\Delta^{N-1} denote a probability distribution over Y\mathcal{Y}, where pjp_j is the predicted probability of outcome jj. A scoring rule on Y\mathcal{Y} is a function S:ΔN−1×Y→R‾S:\Delta^{N-1}\times\mathcal{Y}\to\overline{\mathbb{R}} that evaluates a probabilistic prediction p\mathbf{p} against an observed outcome i∈Yi\in\mathcal{Y}. We adopt the convention that smaller scores indicate better predictions, although the opposite choice is also common.

Definition 3.1. A scoring rule S:ΔN−1×Y→R‾S:\Delta^{N-1}\times\mathcal{Y}\to\overline{\mathbb{R}} is called proper if

Ei∼qS(q,i)≤Ei∼qS(p,i)(2)\mathbb{E}_{i\sim\mathbf{q}}S(\mathbf{q},i)\leq\mathbb{E}_{i\sim\mathbf{q}}S(\mathbf{p},i) \tag*{(2)}

for every p,q∈ΔN−1\mathbf{p},\mathbf{q}\in\Delta^{N-1}. It is called strictly proper if equation 2 holds as a strict inequality whenever p≠q\mathbf{p}\neq\mathbf{q}.

Much of the literature on proper scoring rules has developed in the context of forecast evaluation, with applications such as meteorology or prediction markets in mind. The central motivation for using proper scoring rules in these fields lies in incentivising the forecaster to reveal their true beliefs. If the forecaster’s true belief is q\mathbf{q} but they report p≠q\mathbf{p} \ne\mathbf{q}, equation (2) guarantees that they cannot expect to score any better by doing so. If the scoring rule is strictly proper, they would in fact expect to incur a strictly positive penalty for misreporting.

The same logic applies when evaluating a probabilistic estimator rather than a forecaster: a strictly proper scoring rule ensures that the best expected score is achieved if and only if the model distribution p\mathbf{p} coincides with the true data distribution q\mathbf{q}. Beyond evaluation, proper scoring rules also provide principled loss functions for probabilistic estimation and machine learning, since minimising their empirical average encourages p\mathbf{p} to match q\mathbf{q}.

Canonical examples

We briefly recall three canonical examples of strictly proper scoring rules on a finite outcome space Y\mathcal{Y}, all of which will reappear in the rest of the paper. Throughout, p∈ΔN−1\mathbf{p} \in\Delta^{N-1} denotes the estimated distribution, and i∈Yi \in\mathcal{Y} the observed ground truth.

The Brier score is the oldest and most classical example:

Br⁡(p,i)=∥p−ei∥22=∑j=1N(pj−δij)2∈[0,2],(3)\operatorname{Br}(\mathbf{p},i)=\lVert\mathbf{p}-\mathbf{e}_i\rVert_2^2=\sum_{j=1}^{N}(p_j-\delta_{ij})^2\in[0,2], \tag*{(3)}

where ei\mathbf{e}_i denotes the ii-th standard basis vector and δij\delta_{ij} the Kronecker-Delta. It penalises probability mass assigned to any class other than the true one, while preferring mass to be spread evenly among wrong classes rather than concentrated on a single wrong class. This is a first illustration of the general principle that proper scoring rules balance incentivising well-justified sharpness with penalising unjustified overconfidence.

The logarithmic score, better known as log-loss or cross-entropy loss in machine learning, is

Slog⁡(p,i)=−log⁡pi∈[0,∞).(4)S_{\log}(\mathbf{p},i)=-\log p_i\in[0,\infty). \tag*{(4)}

This is a local scoring rule in that it depends on the predicted distribution only through the probability assigned to the true outcome. Minimising it amounts to maximum likelihood estimation.

Now consider the case of ordinal classification, where the outcome space Y\mathcal{Y} has a natural ordering. The Ranked probability score (RPS) Epstein, [14] is defined as

RPS⁡(p,i)=∑j′=1N((∑j=1j′pj)−1i≤j′)2∈[0,N−1].(5)\operatorname{RPS}(\mathbf{p},i)=\sum_{j'=1}^{N}\left(\left(\sum_{j=1}^{j'}p_j\right)-\mathbb{1}_{i\leq j'}\right)^2\in[0,N-1]. \tag*{(5)}

where the inner sum is the predicted cumulative probability up to category j′j'. The RPS is the natural discrete analog of the popular Continuous ranked probability score (CRPS) Gneiting & Raftery, [18] for univariate real outcome spaces, and both are strictly proper. While outwardly similar to the Brier score, the RPS accounts for the additional structure on Y\mathcal{Y}: probability mass far away from the true category ii is penalised more heavily than mass placed on a neighbouring category. This provides a first example of a proper scoring rule that takes into account a relationship between the categories. The main contribution of the present paper is to construct scoring rules for categorical variables with arbitrary binary relationships between the categories, so that Y\mathcal{Y} becomes the node set of a graph of size NN. As we have seen, such outcome spaces arise naturally in many applications.

Kernel scores

We now focus on the class of proper scoring rules known as kernel scores, as they provide the foundation for our proposed graph-aware scoring rules.

Let k:Y×Y→Rk:\mathcal{Y}\times\mathcal{Y}\to\mathbb{R} be a symmetric function, called the kernel. Let K=[k(i,j)]i,j=1NK=[k(i,j)]_{i,j=1}^{N} denote the corresponding kernel matrix, and write 1⊥:={x∈RN∣∑j=1Nxj=0}\mathbf{1}^{\perp}:=\{\mathbf{x}\in\mathbb{R}^{N}\mid\sum_{j=1}^{N}x_j=0\} for the orthogonal complement of the NN-dimensional vector of ones 1=(1,…,1)T\mathbf{1}=(1,\ldots,1)^{\mathsf{T}}. Define the associated quadratic form by

bk(x):=xTKxfor x∈RN.(6)b_k(\mathbf{x}):=\mathbf{x}^{\mathsf{T}}K\mathbf{x}\quad\text{for }\mathbf{x}\in\mathbb{R}^{N}. \tag*{(6)}

The following definitions are well-known:

Definition 3.2. The kernel kk is called

  • positive definite (p.d.) if bk(x)≥0b_k(\mathbf{x})\geq0 for every x∈RN\mathbf{x}\in\mathbb{R}^{N},

  • negative definite (n.d.) if bk(x)≤0b_k(\mathbf{x})\leq0 for every x∈RN\mathbf{x}\in\mathbb{R}^{N},

  • conditionally positive definite (c.p.d.) if bk(x)≥0b_k(\mathbf{x})\geq0 for every x∈1⊥\mathbf{x}\in\mathbf{1}^{\perp},

  • conditionally negative definite (c.n.d.) if bk(x)≤0b_k(\mathbf{x})\leq0 for every x∈1⊥\mathbf{x}\in\mathbf{1}^{\perp}.

Moreover, kk is called strictly p.d., strictly n.d., strictly c.p.d., or strictly c.n.d., respectively, if the corresponding inequality is strict whenever x≠0\mathbf{x}\neq\mathbf{0} in the respective domain.

Evidently, c.p.d. (c.n.d.) kernels include all p.d. (n.d.) kernels. Moreover, there are subtle connections between p.d. (n.d.) and c.n.d. (c.p.d.) kernels: the two notions are dual to each other in a non-trivial way (van den Berg et al., 1984). For the purposes of this paper, however, we only need the simple observation that if kk is p.d., then −k-k is n.d., and in particular c.n.d.

For a c.n.d. kernel k:Y×Y→Rk:\mathcal{Y}\times\mathcal{Y}\to\mathbb{R}, the corresponding kernel score is defined as

Sk(p,i)=EJ∼p[k(J,i)]−12EJ,J′∼p[k(J,J′)].(7)S_k(\mathbf{p},i)=\mathbb{E}_{J\sim\mathbf{p}}[k(J,i)]-\frac{1}{2}\mathbb{E}_{J,J'\sim\mathbf{p}}[k(J,J')]. \tag*{(7)}

This expectation-based form is, in fact, more general and applies to arbitrary outcome spaces. In our finite setting, it can be written in the following simple vector form:

Sk(p,i)=pTKei−12pTKp.(8)S_k(\mathbf{p},i)=\mathbf{p}^{\mathsf{T}}K\mathbf{e}_i-\frac{1}{2}\mathbf{p}^{\mathsf{T}}K\mathbf{p}. \tag*{(8)}

This is a proper scoring rule if and only if kk is c.n.d., and strictly proper if and only if kk is strictly c.n.d. [18]. This is a significant simplification compared to infinite outcome spaces, where strict positive definiteness of the underlying p.d. kernel is still sufficient but no longer necessary for strict propriety of the kernel score (Ziegel et al., 2024).

The first and second term in equation (8) have a clear interpretation: the first is a calibration term measuring the extent to which p\mathbf{p} is miscalibrated with respect to the true outcome ii, while the second is an entropy term quantifying the spread of p\mathbf{p} independently of ii. Their opposing signs mean that the kernel score balances calibration against sharpness. As mentioned above, this is a general feature of proper scoring rules.

There is an alternative convention for kernel scores which involves an additional term (Ziegel et al., 2024),

Sk+(p,i)=Sk(p,i)−12Kii.(9)S_k^{+}(\mathbf{p},i)=S_k(\mathbf{p},i)-\frac{1}{2}K_{ii}. \tag*{(9)}

The scoring rules SkS_k and Sk+S_k^{+} are strongly equivalent in that they differ only by a term that does not depend on p\mathbf{p}. Strong equivalence preserves propriety. We prefer the Sk+S_k^{+} convention because it yields the clean quadratic form

Sk+(p,i)=−12(p−ei)TK(p−ei),(10)S_k^{+}(\mathbf{p},i)=-\frac{1}{2}(\mathbf{p}-\mathbf{e}_i)^{\mathsf{T}}K(\mathbf{p}-\mathbf{e}_i), \tag*{(10)}

which is always non-negative: since p−ei∈1⊥\mathbf{p}-\mathbf{e}_i\in\mathbf{1}^{\perp} for all p∈ΔN−1\mathbf{p}\in\Delta^{N-1} and i∈Yi\in\mathcal{Y}, c.n.d. of KK implies Sk+(p,i)≥0S_k^{+}(\mathbf{p},i)\geq0. Note, that if −k-k is strictly p.d., then Sk+S_k^{+} can be seen as a special case of the squared maximum mean discrepancy [19] between p\mathbf{p} and a point mass at ii. Moreover, in the case where Y\mathcal{Y} is the node set of a graph (see § 5), it is a type of node vector distance [9] between p\mathbf{p} and ei\mathbf{e}_i.

As it turns out, two of the scores introduced in the previous section are, in fact, kernel scores. The Brier score corresponds to k(j,j′)=1−δj,j′k(j,j')=1-\delta_{j,j'}, while the RPS corresponds to k(j,j′)=∣j−j′∣k(j,j')=|j-j'| [18]. For details, see Appendix § 10.

Related Work

Evaluation metrics for node selection tasks. For non-probabilistic methods, the standard aggregate evaluation metric is accuracy (or, equivalently, the error rate). Probabilistic, likelihood-based or ranking-based methods typically report the (inverse) rank of the true node or top-KK accuracy [34, 2, 3] (Sha et al. 2021). A popular alternative is the Error distance [3, 26] (Zhu & Ying 2016; Paluch et al. 2018), also known as Graph error distance or Distance error, which measures the shortest-path distance between the top-1 prediction and the true node. Error distance is graph-aware but improper (see § 5.4). Paluch et al. (2020) propose the α\alpha-credible set size (CSSα_\alpha), i.e., the number of nodes needed to cover a given fraction of predicted probability mass, as a complementary sharpness measure. The use of CSSα_\alpha implicitly acknowledges that rank and accuracy fail to capture important aspects of the full distribution, yet it does not constitute a principled solution: it is not a proper scoring rule and does not account for graph structure.

Proper scoring rules and kernel scores. The statistical literature on proper scoring rules has largely focused on standard outcome spaces. Gneiting & Raftery [18] give a comprehensive treatment of proper scoring rules and kernel scores on Euclidean spaces. They establish the connection between c.n.d. kernels and strictly proper kernel scores and introduce energy scores and CRPS as canonical examples. Notable extensions to non-standard outcome spaces include the circular CRPS of Grimit et al. [20], the adaptation of the Hyvärinen score to Riemannian manifolds (Mardia et al., 2016) and to {−1,1}N\{-1,1\}^{N} [25], and proper scoring rules for top-kk list predictions (Resin, 2023), where the prediction consists of the kk most likely classes together with associated confidence levels.

Proper scoring rules on node sets of graphs. The only prior work to study proper scoring rules specifically on the node set of a graph is Dawid et al. [10], who characterise proper scoring rules which are local in the sense that the score only depends on the total probability assigned to a neighbourhood of the true node. They show for an important class of such scoring rules (namely those that only depend on probability ratios rather than absolute probabilities) that they can be decomposed as a superposition of the logarithmic score and proper scoring rules on maximal cliques. While elegant, this result does not provide scoring rules that evaluate the entire probability distribution according to its proximity to the true node, which is the primary goal of the present paper.

Kernels and distributions on node sets of graphs. A number of machine learning papers explicitly consider p.d. kernels on the node set of graphs. The seminal work Smola & Kondor (2003) constructs kernels as functions of the graph Laplacian, defining diffusion kernels and random walk kernels as special cases. Fouss et al. [15] introduce the resistance or commute-time kernel, but the convergence results of von Luxburg et al. (2014) show that resistance distance has limited discrimination power on large graphs unless they are sufficiently sparse. Fouss et al. [16] review and compare a variety of Laplacian-based kernels on node sets of graphs. Borovitskiy et al. [6] generalise Matérn kernels to node sets of graphs with a construction that also makes use of the graph Laplacian. Meanwhile, Devriendt et al. [12] study probability distributions over node sets directly, introducing a notion of variance based on the effective resistance distance. All three of these papers use the graph Laplacian as the central object encoding proximity between nodes, and their constructions inform the scoring rules we propose in § 5. Coscia & Devriendt [9] show how Laplacian-based node vector distances can be computed efficiently using Laplacian solvers. Their framework applies directly to computing the Resistance score (§ 5.7). The Diffusion score introduced in § 5.3 is also informed by the Laplacian renormalisation group of Villegas et al. (2023), which uses the diffusion kernel to coarse-grain graphs at different scales.

Evaluation metrics for hierarchical classification. There is a large literature on hierarchy-aware evaluation metrics [31] (Silla & Freitas 2011; Zangari et al. 2024). Most of these metrics operate on point estimates rather than probability distributions over nodes, and some of them apply to estimated node subsets rather than our single node selection setting. Hierarchical precision, recall and F-score [29] measure set overlap between the predicted subset of nodes and a true subset of nodes. Tree-distance metrics [8] (Ramawamy et al. 2015) score a single estimated node against the true node. Metrics based on the lowest common ancestor (LCA), including the semantic similarity of Wu & Palmer (1994) and the Hierarchical error distance (Russakovsky et al., 2015) and its generalisation to distance@KK (Bertinetto et al., [4]; Karthik et al. [27]), depend on the distribution only through its mode or its ranking. Separately, Valmadre (2022) evaluates hierarchy-aware sensitivity and specificity by sweeping an inference threshold, and Karthik et al. [27] and Plaud et al. (2025) derive post-hoc Bayes-optimal point estimates from a distributional estimate under hierarchical costs. Neither line of work addresses the evaluation of the distribution itself. To the best of our knowledge, the only proper scoring rules for hierarchical node selection are the hierarchical cross-entropy (HXE) of Bertinetto et al. [4] and its generalisations, whose propriety (but not strict propriety) was recognised and proved by Urbani et al. (2024).

Strictly proper scoring rules for node selection

We now consider scoring rules for the case where the set of outcomes is the node set of a graph. As in § 2, we assume G=(V,E)G=(V,E) to be a simple graph of size N=∣V∣N=|V|, and we set Y=V\mathcal{Y}=V, identifying the nodes VV with integers 1,…,N1,\ldots,N.

Let A∈{0,1}N×NA\in\{0,1\}^{N\times N} be the adjacency matrix of GG. Denote by dj=∑j′=1NAjj′d_j=\sum_{j'=1}^{N}A_{jj'} the degree of node jj, and let D∈RN×ND\in\mathbb{R}^{N\times N} be the degree matrix, i.e., the diagonal matrix with entries Djj′=djδjj′D_{jj'}=d_j\delta_{jj'}. The graph Laplacian is defined as L=D−AL=D-A, with eigenvalues 0=λ1≤λ2≤⋯≤λN0=\lambda_1\leq\lambda_2\leq\cdots\leq\lambda_N and associated orthonormal eigenbasis v1,v2,…,vN∈RN\mathbf{v}_1,\mathbf{v}_2,\ldots,\mathbf{v}_N\in\mathbb{R}^{N}, where v1=1N1\mathbf{v}_1=\frac{1}{\sqrt{N}}\mathbf{1}. We write I\mathbb{I} for the N×NN\times N identity matrix and ej∈{0,1}N\mathbf{e}_j\in\{0,1\}^{N} for the jj-th standard basis vector, defined by (ei)j=δij(\mathbf{e}_i)_j=\delta_{ij}. It will be repeatedly useful to recall the fact that p−ei∈1⊥\mathbf{p}-\mathbf{e}_i\in\mathbf{1}^{\perp} for all p∈ΔN−1\mathbf{p}\in\Delta^{N-1} and i∈Vi\in V.

We will sometimes refer to special graphs: KNK_N denotes the complete graph on NN nodes, with Laplacian L=NI−11TL=N\mathbb{I}-\mathbf{1}\mathbf{1}^{\mathsf{T}} and non-zero eigenvalues λ2=⋯=λN=N\lambda_2=\cdots=\lambda_N=N. PNP_N denotes the path graph with nodes 1,…,N1,\ldots,N and edges (j,j+1)(j,j+1) for j=1,…,N−1j=1,\ldots,N-1. Moreover, CNC_N denotes the cycle graph, which is the same as PNP_N but with an additional edge (N,1)(N,1) to close the cycle.

We construct our scoring rules within the kernel score framework of § 3.2. Specifically, we design scores of the form displayed in equation (9) with kernels derived from the graph Laplacian LL. In each case, it suffices to find a (strictly) c.n.d. kernel matrix KK on VV; the score SK+(p,i)S_K^+(\mathbf{p},i) is then automatically non-negative and (strictly) proper.

Throughout this section, we adopt the convention of the kernel literature, consistent with our Definition 3.2 (and aligned with the definition of proper and strictly proper scoring rules), that a symmetric matrix M∈RN×NM\in\mathbb{R}^{N\times N} is called positive definite (rather than just positive semi-definite) if xTMx≥0\mathbf{x}^{\mathsf{T}}M\mathbf{x}\geq0 for all x∈RN\mathbf{x}\in\mathbb{R}^{N}, and strictly positive definite (rather than just positive definite) if the inequality is strict for x≠0\mathbf{x}\neq0. Under this convention, the graph Laplacian LL is p.d., and its Moore–Penrose pseudoinverse L†L^\dagger is p.d. as well: if L=∑k=1NλkvkvkTL=\sum_{k=1}^{N}\lambda_k\mathbf{v}_k\mathbf{v}_k^{\mathsf{T}} is the eigendecomposition of LL, then L†=∑k:λk>0λk−1vkvkTL^\dagger=\sum_{k:\lambda_k>0}\lambda_k^{-1}\mathbf{v}_k\mathbf{v}_k^{\mathsf{T}}, which has exclusively non-negative eigenvalues.

A first Laplacian score

The graph Laplacian LL is a natural candidate kernel matrix, as it encodes one-hop proximity between nodes. The following lemma ensures that it can indeed be used to construct a proper kernel score:

Lemma 5.1. The negative Laplacian −L-L is conditionally negative definite. If the graph is connected, then −L-L is strictly c.n.d.

Proof. LL is positive definite, thus −L-L is trivially c.n.d. If the graph is connected, then the null space of −L-L is one-dimensional and is spanned by v1=1\mathbf{v}_1=\mathbf{1}. Thus, any nonzero x∈1⊥\mathbf{x}\in\mathbf{1}^{\perp} is not in the null space, and since −L-L is negative definite, this implies that −xTLx<0-\mathbf{x}^{\mathsf{T}}L\mathbf{x}<0.

Using equation (9) with K=−LK=-L, the corresponding score reads

S−L+(p,i)=12pTLp−eiTLp+di2.(11)S^+_{-L}(\mathbf{p},i)=\frac{1}{2}\mathbf{p}^{\mathsf{T}}L\mathbf{p}-\mathbf{e}_i^{\mathsf{T}}L\mathbf{p}+\frac{d_i}{2}. \tag*{(11)}

By Lemma 5.1, the kernel score S−L+S^{+}_{-L} is a strictly proper scoring rule on any connected graph. This score rewards probability mass concentrated on neighbours of ii (via the second term) and penalises globally rough distributions (via the first term). In this sense, the score is reminiscent of the Hyvärinen score ([24]) for distributions on Rn\mathbb{R}^{n}. (For a modern introduction to this score we refer to the review by Waghmare & Ziegel (2025)). However, since the Laplacian is zero everywhere except on the diagonal and the first off-diagonal, the calibration term of the score sees only the one-hop neighbourhood of the true node: any probability mass at shortest path distance two or more from the true node is treated identically by S−L+S^{+}_{-L}. Thus, S−L+S^{+}_{-L} is at best a first order refinement of the Brier score. This motivates looking for a kernel that encodes the global graph structure rather than just the local adjacency structure.

Before we do just that, let us make the following observation. On the complete graph KNK_N, all local neighbourhoods are identical with VV. The incentives of the score S−L+S^{+}_{-L} thus transform exactly into those of the Brier score. More formally, S−L+S^{+}_{-L} is a generalisation of the Brier score in the following sense:

Proposition 5.2. On the complete graph KNK_N, S−L+S^{+}_{-L} is strongly equivalent to the multi-category Brier score.

Proof. Consider the complete graph KNK_N and its Laplacian L=NI−11TL=N I-\mathbf{1}\mathbf{1}^{\mathsf{T}}. The Laplace score in its product form (equation 10) is then:

S−L(p,i)=12(p−ei)T(NI−11T)(p−ei).S_{-L}(\mathbf{p},i)=\frac{1}{2}(\mathbf{p}-\mathbf{e}_i)^{\mathsf{T}}(N I-\mathbf{1}\mathbf{1}^{\mathsf{T}})(\mathbf{p}-\mathbf{e}_i).

Now observe that 1T(p−ei)=0\mathbf{1}^{\mathsf{T}}(\mathbf{p}-\mathbf{e}_i)=0. Hence, the score reduces to

S−L(p,i)=N2(p−ei)T(p−ei)=N2Br⁡(p,i).S_{-L}(\mathbf{p},i)=\frac{N}{2}(\mathbf{p}-\mathbf{e}_i)^{\mathsf{T}}(\mathbf{p}-\mathbf{e}_i)=\frac{N}{2}\operatorname{Br}(\mathbf{p},i).

\hfill □\square

The Resistance score

A natural upgrade to the one-hop Laplacian kernel score is to construct a scoring rule based on a notion of distance between nodes. Effective resistance distance ([30]) is one of the distances that can be defined on the nodes of a graph. For nodes i,j∈Vi,j\in V, it is defined as

ωjj′:=(ej−ej′)TL†(ej−ej′).(12)\omega_{jj'} := (\mathbf{e}_j-\mathbf{e}_{j'})^{\mathsf{T}}L^{\dagger}(\mathbf{e}_j-\mathbf{e}_{j'}). \tag*{(12)}

where L†L^{\dagger} denotes the Moore-Penrose pseudoinverse of LL. Note that ωjj′\omega_{jj'} is symmetric and vanishes if and only if j=j′j=j'. Moreover, all resistance distances are non-negative. This is an immediate consequence of equation 12, because L†L^{\dagger} is positive definite. An alternative way to write the resistance distance is as follows:

ωjj′=Ljj†+Lj′j′†−2Ljj′†.(13)\omega_{jj'}=L^{\dagger}_{jj}+L^{\dagger}_{j'j'}-2L^{\dagger}_{jj'}. \tag*{(13)}

As the name betrays, the origins of this distance can be found in physics: the effective resistance distance between two nodes is equivalent to the electric resistance between them if the graph is viewed as an electric network with each edge representing a resistor of unit weight.

Let Ω=[ωij]i,j=1N\Omega=[\omega_{ij}]_{i,j=1}^{N} denote the matrix of all pairwise resistance distances.

Lemma 5.3. If x∈1⊥\mathbf{x}\in\mathbf{1}^{\perp}, then xTΩx=−2xTL†x\mathbf{x}^{\mathsf{T}}\Omega\mathbf{x}=-2\mathbf{x}^{\mathsf{T}}L^{\dagger}\mathbf{x}.

Proof. With d=diag⁡(L†)\mathbf{d}=\operatorname{diag}(L^{\dagger}) we can write Ω=d1T+1dT−2L†\Omega=\mathbf{d}\mathbf{1}^{\mathsf{T}}+\mathbf{1}\mathbf{d}^{\mathsf{T}}-2L^{\dagger}. The matrix d1T\mathbf{d}\mathbf{1}^{\mathsf{T}} is rank 1 with null space 1⊥\mathbf{1}^{\perp}, from which follows that xT(d1T+1dT)x=0\mathbf{x}^{\mathsf{T}}(\mathbf{d}\mathbf{1}^{\mathsf{T}}+\mathbf{1}\mathbf{d}^{\mathsf{T}})\mathbf{x}=0 for all x∈1⊥\mathbf{x}\in\mathbf{1}^{\perp}. \hfill □\square

Lemma 5.4. The matrix Ω\Omega is conditionally negative definite. If the graph is connected, then Ω\Omega is strictly conditionally negative definite.

Proof. By Lemma 5.3, for every x∈1⊥\mathbf{x}\in\mathbf{1}^{\perp}, we have xTΩx=−2xTL†x≤0\mathbf{x}^{\mathsf{T}}\Omega\mathbf{x}=-2\mathbf{x}^{\mathsf{T}}L^{\dagger}\mathbf{x}\leq0, since L†L^{\dagger} is positive definite. Hence, Ω\Omega is c.n.d. If the graph is connected, then the null space of L†L^{\dagger} is spanned by 1\mathbf{1}. Thus, every nonzero x∈1⊥\mathbf{x}\in\mathbf{1}^{\perp} lies outside the null space, and since L†L^{\dagger} is positive definite, we have xTL†x>0\mathbf{x}^{\mathsf{T}}L^{\dagger}\mathbf{x}>0. Consequently, xTΩx=−2xTL†x<0\mathbf{x}^{\mathsf{T}}\Omega\mathbf{x}=-2\mathbf{x}^{\mathsf{T}}L^{\dagger}\mathbf{x}<0 for every nonzero x∈1⊥\mathbf{x}\in\mathbf{1}^{\perp}, proving that Ω\Omega is strictly c.n.d. \hfill □\square

Lemma 5.4 is a special case of a classical result: since L†L^{\dagger} is a p.d. kernel, it induces a Hilbert space embedding of VV, and the squared Euclidean distance between nodes jj and j′j' in this embedding space is precisely ωjj′\omega_{jj'}. By Schoenberg’s theorem (see, e.g., van den Berg et al. (1984)), the squared distance in a Hilbert space is always c.n.d., which yields Lemma 5.4 as a corollary. The use of L†L^{\dagger} as a p.d. kernel on the node set of a graph appears explicitly in Fouss et al. [15].

Definition 5.5. The Resistance score Sres:ΔN−1×V→R≥0S_{\mathrm{res}} : \Delta^{N-1} \times V \to\mathbb{R}_{\ge0} is the kernel score SΩ+S_{\Omega}^{+} associated with Ω\Omega:

Sres(p,i):=ei⊤Ωp−12p⊤Ωp(14)S_{\mathrm{res}}(\mathbf{p},i) := \mathbf{e}_i^{\top}\Omega\mathbf{p} - \frac{1}{2}\mathbf{p}^{\top}\Omega\mathbf{p} \tag*{(14)}

Since ωjj=0\omega_{jj}=0, it coincides with SΩS_{\Omega}.

From Lemma 5.4 follows:

Proposition 5.6. The Resistance score is a proper scoring rule. If the graph is connected, it is strictly proper.

By Lemma 5.3 and equation (10), the Resistance score admits the alternative representation

Sres(p,i)=(p−ei)⊤L†(p−ei),(15)S_{\mathrm{res}}(\mathbf{p},i) = (\mathbf{p}-\mathbf{e}_i)^{\top}L^{\dagger}(\mathbf{p}-\mathbf{e}_i), \tag*{(15)}

which shows that it measures the node vector distance between p\mathbf{p} and ei\mathbf{e}_i induced by the p.d. kernel L†L^{\dagger} ([9]). Using the notation of Devriendt et al. [12], the Resistance score can also be written as

Sres(p,i)=[Ωp]i−Var⁡ω(p),(16)S_{\mathrm{res}}(\mathbf{p},i) = [\Omega\mathbf{p}]_i - \operatorname{Var}_{\omega}(\mathbf{p}), \tag*{(16)}

where Var⁡ω(p)=12p⊤Ωp\operatorname{Var}_{\omega}(\mathbf{p}) = \frac{1}{2}\mathbf{p}^{\top}\Omega\mathbf{p} is the graph variance of p\mathbf{p}. The first term penalises probability mass in proportion to its resistance distance from the true node. The second term acts as a regulariser that discourages excessive concentration of mass in a small region of the graph.

Connections to classical proper scoring rules. Like the Laplace score, the Resistance score reduces to the Brier score when the graph structure becomes irrelevant:

Proposition 5.7. On the complete graph KNK_N, the Resistance score is strongly equivalent to the multi-category Brier score.

Proof. On the complete graph we find that L†=∑j=2N1λjvjvj⊤=1N∑j=2Nvjvj⊤=1N(I−v1v1⊤)=1N2LL^{\dagger} = \sum_{j=2}^{N} \frac{1}{\lambda_j}\mathbf{v}_j\mathbf{v}_j^{\top} = \frac{1}{N}\sum_{j=2}^{N}\mathbf{v}_j\mathbf{v}_j^{\top} = \frac{1}{N}(I-\mathbf{v}_1\mathbf{v}_1^{\top}) = \frac{1}{N^2}L, where we have used the property of orthonormal bases that I=∑j=1Nvjvj⊤I = \sum_{j=1}^{N}\mathbf{v}_j\mathbf{v}_j^{\top}. As a consequence, the Resistance score in the form of equation (15) reduces (up to a constant) to the Laplacian score of equation (11),

Sres(p,i)=2N2S−L(p,i).S_{\mathrm{res}}(\mathbf{p},i) = \frac{2}{N^2}S_{-L}(\mathbf{p},i).

But, as was stated in Proposition 5.2, this is equivalent to the Brier score, specifically

Sres(p,i)=1NSBr(p,i).S_{\mathrm{res}}(\mathbf{p},i) = \frac{1}{N}S_{\mathrm{Br}}(\mathbf{p},i).

To state the next connection, we first recall a fundamental property of resistance distance, which will also be used in § 5.6.

Proposition 5.8 (Klein & Randić [30]). On any tree, the effective resistance distance ωjj′\omega_{jj'} equals the shortest-path distance d(j,j′)d(j,j') for all nodes j,j′∈Vj,j' \in V.

With Proposition 5.8 at our disposal, the following result is immediate:

Proposition 5.9. On the path graph PNP_N, the Resistance score equals the Ranked probability score (RPS) for NN ordinal categories.

Proof. As noted in § 3.2, the RPS is a kernel score on the integers 1,…,N1,\ldots,N with associated kernel k(j,j′)=∣j−j′∣k(j,j') = \lvert j-j'\rvert (a proof of this well-known result is supplied in Appendix § 10). Identifying these integers with the nodes of the path graph, the kernel kk equals the shortest-path metric on PNP_N. Since PNP_N is a tree, Proposition 5.8 gives ωjj′=∣j−j′∣\omega_{jj'} = \lvert j-j'\rvert, so the two kernel scores coincide: Sres(p,i)=RPS⁡(p,i)S_{\mathrm{res}}(\mathbf{p},i) = \operatorname{RPS}(\mathbf{p},i).

In summary, Propositions 5.7 and 5.9 show that the Resistance score builds a bridge between two of the most widely used proper scoring rules: the Brier score (recovered on KNK_N) and the RPS (recovered on PNP_N). To our knowledge, this connection is new in the literature. More generally, the Resistance score can be viewed as an extension of the generalised energy score of Gneiting & Raftery [18] with β=1\beta= 1, with the Euclidean distance replaced by the effective resistance metric. The special case when GG is a rooted tree is discussed in § 5.6. The different special cases of the Resistance score are summarised in Figure 1.

Resistance score specialisations on graphs

Figure 1. The Resistance score on a general graph GG specialises to the Brier score on the complete graph KNK_N (Proposition 5.7), to the Ranked probability score (RPS) on the path graph PNP_N (Proposition 5.9), and to a hierarchy-aware score on a rooted tree TT (§ 5.6). On a depth-1 tree (star graph SNS_N), the latter further specialises to the Brier score on the leaf nodes (Proposition 5.23). Arrows indicate specialisation.

As an aside, on the cycle graph CNC_N we have ωjj′=djj′(N−djj′)/N\omega_{jj'} = d_{jj'}(N-d_{jj'})/N where djj′=min⁡(∣j−j′∣,N−∣j−j′∣)d_{jj'}=\min(|j-j'|,N-|j-j'|). In the continuum limit N→∞N \to\infty, the Resistance score on CNC_N therefore does not converge to the circular CRPS defined in Grimit et al. [20]. The latter is linear in the angular distance, whereas the limit of the Resistance score is quadratic in the angular distance.

Large graphs. An interesting consideration concerns the behaviour of the resistance score on large graphs. On many large graphs, von Luxburg et al. (2014) show that effective resistance distance converges asymptotically to a function only of node degree:

ωjj′→N→∞1dj+1dj′,(17)\omega_{jj'} \xrightarrow[N\to\infty]{} \frac{1}{d_j}+\frac{1}{d_{j'}}, \tag*{(17)}

or equivalently Ω≈w1T+1wT\Omega\approx\mathbf{w}\mathbf{1}^{\mathsf{T}}+\mathbf{1}\mathbf{w}^{\mathsf{T}} where wj=1/djw_j=1/d_j. This effect does not occur on sufficiently sparse graphs, where the resistance distance remains asymptotically aware of the full graph topology. The convergence result makes resistance distance unattractive as a similarity or distance measure on large graphs that are not sufficiently sparse. However, the leading term w1T+1wT\mathbf{w}\mathbf{1}^{\mathsf{T}}+\mathbf{1}\mathbf{w}^{\mathsf{T}} contributes nothing to the Resistance score: for any x=p−ei∈1⊥\mathbf{x}=\mathbf{p}-\mathbf{e}_i\in\mathbf{1}^{\perp},

xT(w1T+1wT)x=(xTw)(1Tx)+(xT1)(wTx)=0,(18)\mathbf{x}^{\mathsf{T}}(\mathbf{w}\mathbf{1}^{\mathsf{T}}+\mathbf{1}\mathbf{w}^{\mathsf{T}})\mathbf{x}=(\mathbf{x}^{\mathsf{T}}\mathbf{w})(\mathbf{1}^{\mathsf{T}}\mathbf{x})+(\mathbf{x}^{\mathsf{T}}\mathbf{1})(\mathbf{w}^{\mathsf{T}}\mathbf{x})=0, \tag*{(18)}

since xT1=1Tx=0\mathbf{x}^{\mathsf{T}}\mathbf{1}=\mathbf{1}^{\mathsf{T}}\mathbf{x}=0. The Resistance score therefore depends on the second-order term Ω−(w1T+1wT)\Omega-(\mathbf{w}\mathbf{1}^{\mathsf{T}}+\mathbf{1}\mathbf{w}^{\mathsf{T}}) in the asymptotic expansion, and von Luxburg et al.’s argument does not obviously invalidate it even on denser graphs. Whether this residual retains meaningful global topological information is an open question. If it reduces to quantities that depend on local neighbourhood structure only, the Resistance score would reflect only local graph properties in that regime. The Diffusion score, introduced in the next section, provides a more robustly topology-sensitive alternative at the cost of introducing a free parameter.

The Diffusion score

Another Laplacian-based kernel on GG is the heat kernel or diffusion kernel (Smola & Kondor, 2003),

Hτ:=e−τ2L=∑j=1Ne−τ2λjvjvjT,τ≥0,(19)H^{\tau} := e^{-\frac{\tau}{2}L} = \sum_{j=1}^{N} e^{-\frac{\tau}{2}\lambda_j}v_jv_j^{\mathsf{T}}, \qquad\tau\ge0, \tag*{(19)}

where the parameter τ\tau controls the diffusion time.

Definition 5.10. We define the τ\tau-Diffusion score Sdiffτ:ΔN−1×V→R≥0S_{\mathrm{diff}}^{\tau} : \Delta^{N-1} \times V \to\mathbb{R}_{\ge0} by

Sdiffτ(p,i):=(p−ei)THτ(p−ei).(20)S_{\mathrm{diff}}^{\tau}(\mathbf{p},i) := (\mathbf{p}-\mathbf{e}_i)^{\mathsf{T}}H^{\tau}(\mathbf{p}-\mathbf{e}_i). \tag*{(20)}

The diffusion kernel is strictly positive definite no matter whether the underlying graph is connected or not. Therefore, −Hτ-H^{\tau} is strictly c.n.d., and we have:

Proposition 5.11. The τ\tau-Diffusion score is a strictly proper scoring rule on any simple graph.

As for the Resistance score, we find:

Proposition 5.12. On the complete graph KNK_N and for any τ≥0\tau\ge0, the τ\tau-Diffusion score is strongly equivalent to the multi-category Brier score.

Proof. On the complete graph, the diffusion kernel of equation 19 simplifies to Hτ=v1v1T+e−τ2N∑j=2NvjvjTH^{\tau} = \mathbf{v}_1\mathbf{v}_1^{\mathsf{T}} + e^{-\frac{\tau}{2}N}\sum_{j=2}^{N}\mathbf{v}_j\mathbf{v}_j^{\mathsf{T}}. Recalling that ∑j=1NvjvjT=I\sum_{j=1}^{N}\mathbf{v}_j\mathbf{v}_j^{\mathsf{T}} = \mathbb{I} and v1=1N1\mathbf{v}_1 = \frac{1}{\sqrt{N}}\mathbf{1}, we obtain Hτ=1N(1−e−τ2N)11T+e−τ2NIH^{\tau} = \frac{1}{N}(1-e^{-\frac{\tau}{2}N})\mathbf{1}\mathbf{1}^{\mathsf{T}}+e^{-\frac{\tau}{2}N}\mathbb{I}. Observing again the fact that 1T(p−ei)=0\mathbf{1}^{\mathsf{T}}(\mathbf{p}-\mathbf{e}_i)=0, it follows that Sdiffτ(p,i)=e−τ2N(p−ei)T(p−ei)=e−τ2NBr⁡(p,i)S_{\mathrm{diff}}^{\tau}(\mathbf{p},i)=e^{-\frac{\tau}{2}N}(\mathbf{p}-\mathbf{e}_i)^{\mathsf{T}}(\mathbf{p}-\mathbf{e}_i)=e^{-\frac{\tau}{2}N}\operatorname{Br}(\mathbf{p},i).

The interesting feature of the Diffusion score is its behaviour with respect to varying τ\tau, irrespective of the graph structure. It is most clearly illustrated on a disconnected graph:

Proposition 5.13. Let GG be a graph with K≥1K \ge1 connected components C1,…,CKC_1,\ldots,C_K.

  1. For small τ\tau, the τ\tau-diffusion score has the expansion

Sdiffτ(p,i)=Br⁡(p,i)−τS+−(p,i)+O(τ2).(21)S_{\mathrm{diff}}^{\tau}(\mathbf{p},i)=\operatorname{Br}(\mathbf{p},i)-\tau S_{+}^{-}(\mathbf{p},i)+O(\tau^2). \tag*{(21)}
  1. As τ→∞\tau\to\infty, the τ\tau-diffusion score asymptotically converges to

Sdiff∞(p,i)=∑k=1K(P(Ck)−1i∈Ck)2∣Ck∣,(22)S_{\mathrm{diff}}^{\infty}(\mathbf{p},i)=\sum_{k=1}^{K}\frac{\left(P(C_k)-1_{i\in C_k}\right)^2}{\lvert C_k\rvert}, \tag*{(22)}

where P(C)P(C) is the total probability mass placed on a subset of nodes C⊆VC \subseteq V by the distribution p\mathbf{p}.

Proof. 1. For small τ\tau, we have the first-order Taylor expansion Hτ=I−τ2L+O(τ2)H^{\tau}=\mathbb{I}-\frac{\tau}{2}L+O(\tau^2) and thus Sdiffτ(p,i)=(p−ei)T(p−ei)−τ2(p−ei)TL(p−ei)+O(τ2)=Br⁡(p,i)−τS+−(p,i)+O(τ2)S_{\mathrm{diff}}^{\tau}(\mathbf{p},i)=(\mathbf{p}-\mathbf{e}_i)^{\mathsf{T}}(\mathbf{p}-\mathbf{e}_i)-\frac{\tau}{2}(\mathbf{p}-\mathbf{e}_i)^{\mathsf{T}}L(\mathbf{p}-\mathbf{e}_i)+O(\tau^2)=\operatorname{Br}(\mathbf{p},i)-\tau S_{+}^{-}(\mathbf{p},i)+O(\tau^2).

  1. Consider the eigenspace of LL corresponding to eigenvalue 00. It is KK-dimensional and spanned by the orthonormal basis 1∣C1∣1C1,…,1∣CK∣1CK\frac{1}{\sqrt{\lvert C_1\rvert}}\mathbf{1}_{C_1},\ldots,\frac{1}{\sqrt{\lvert C_K\rvert}}\mathbf{1}_{C_K}, where 1C:=∑j∈Cej\mathbf{1}_C:=\sum_{j\in C}\mathbf{e}_j for C⊆VC\subseteq V. For τ→∞\tau\to\infty we thus obtain the singular value decomposition Hτ→H∞=∑k=1K1∣Ck∣1Ck1CkTH^{\tau}\to H^{\infty}=\sum_{k=1}^{K}\frac{1}{\lvert C_k\rvert}\mathbf{1}_{C_k}\mathbf{1}_{C_k}^{\mathsf{T}}. Plugging this into equation 20 yields Sdiff∞(p,i)=∑k=1K1∣Ck∣(p−ei)T1Ck1CkT(p−ei)S_{\mathrm{diff}}^{\infty}(\mathbf{p},i)=\sum_{k=1}^{K}\frac{1}{\lvert C_k\rvert}(\mathbf{p}-\mathbf{e}_i)^{\mathsf{T}}\mathbf{1}_{C_k}\mathbf{1}_{C_k}^{\mathsf{T}}(\mathbf{p}-\mathbf{e}_i). From P(C)=1CTpP(C)=\mathbf{1}_C^{\mathsf{T}}\mathbf{p} and 1CTei=1i∈C\mathbf{1}_C^{\mathsf{T}}\mathbf{e}_i=1_{i\in C}, it follows that (p−ei)T1Ck1CkT(p−ei)=(P(Ck)−1i∈Ck)2(\mathbf{p}-\mathbf{e}_i)^{\mathsf{T}}\mathbf{1}_{C_k}\mathbf{1}_{C_k}^{\mathsf{T}}(\mathbf{p}-\mathbf{e}_i)=\left(P(C_k)-1_{i\in C_k}\right)^2, which completes the proof.

The limit τ→∞\tau\to\infty corresponds to a weighted version of the Brier score, where the categories are connected components rather than individual nodes, and the squared error for each component contributes with a weight proportional to the inverse of its size. In this limit, p\mathbf{p} scores well if it places the correct total mass P(Ck)P(C_k) on component CkC_k rather than necessarily getting the individual node probabilities pjp_j right. Note that the diffusion score is no longer strictly proper in this limit, as any redistribution of mass within a connected component leaves the value of Sdiff∞(p,i)S_{\mathrm{diff}}^\infty(\mathbf{p},i) unaffected. Moreover, compared to the regular Brier score, Sdiff∞(p,i)S_{\mathrm{diff}}^\infty(\mathbf{p},i) down-weights larger connected components, preventing them from dominating the total score simply by virtue of their size. Consequently, there is no incentive to hedge by placing disproportionate probability mass on nodes belonging to smaller connected components.

Proposition 5.13 provides us more generally with an interpretation of the Diffusion score as a function of τ\tau. For τ=0\tau= 0 it reduces to the Brier score, which favours concentration of p\mathbf{p} exactly on node ii, but otherwise prefers a uniform distribution. For small but non-zero τ\tau, the Laplacian score discussed in § 5.1 enters the expansion with a negative sign, reflecting a shift in preference: probability mass on the neighboring nodes is now encouraged, not just on the correct node itself. For larger τ\tau, the score increasingly favours concentration of p\mathbf{p} on the connected component which contains the true node ii, but otherwise prefers a more uniform distribution of the probability mass between the different components. When using the diffusion score for large τ\tau, we take a deliberate decision to focus on predicting the correct connected component rather than exactly the right node. In this sense, the loss of strict propriety in the limit τ→∞\tau\to\infty is an expected feature of this score.

This idea extends further to the case where GG is connected: for large τ\tau the asymptotic expression Sdiff∞(p,i)S_{\mathrm{diff}}^\infty(\mathbf{p},i) remains approximately valid if we interpret C1…,CKC_1 \ldots, C_K as the main clusters of GG. The diffusion score for large τ\tau thus favours predictions that are concentrated on the correct main cluster, without much consideration for the way the probability is distributed within the cluster. But as Villegas et al. (2023) demonstrate in their recent work on Laplacian coarse-graining, the diffusion kernel HτH^\tau induces a natural scale-dependent clustering on the graph. In this interpretation, the number KK of clusters is itself dependent on τ\tau: the case τ=0\tau= 0 represents maximal granularity in which each node is its own cluster (K(τ=0)=NK(\tau= 0) = N), while in the case τ→∞\tau\to\infty the entire (connected) graph becomes a single cluster (lim⁡τ→∞K(τ)=1\lim_{\tau\to\infty} K(\tau) = 1). In other words, the parameter τ\tau in the Diffusion score acts as a control on the spectral scale on which to push our calibration. The scale-dependent coarse-graining of Villegas et al. (2023) may provide a useful framework for a principled selection of τ\tau.

One detail is worth pointing out: for connected graphs, the Diffusion score as defined in equation (20) converges to zero as τ→∞\tau\to\infty, since the diffusion kernel converges to 1N11T\frac{1}{N}\mathbf{1}\mathbf{1}^{\mathsf{T}} which annihilates p−ei\mathbf{p}-\mathbf{e}_i. To compensate for this decay, let μ>0\mu> 0 and set Hμτ:=e−τ2(L−μI)H_\mu^\tau:= e^{-\frac{\tau}{2}(L-\mu I)} which shifts the spectrum of the Laplacian by μ\mu. We can define the μ\mu-regularised τ\tau-Diffusion score by

Sdiffτ,μ(p,i):=(p−ei)THμτ(p−ei).(23)S_{\mathrm{diff}}^{\tau,\mu}(\mathbf{p},i) := (\mathbf{p}-\mathbf{e}_i)^{\mathsf{T}} H_\mu^\tau(\mathbf{p}-\mathbf{e}_i). \tag*{(23)}

Since Hμτ=eτμ2HτH_\mu^\tau= e^{\frac{\tau\mu}{2}}H^\tau, the regularised score is simply Sdiffτ,μ(p,i)=eτμ2Sdiffτ(p,i)S_{\mathrm{diff}}^{\tau,\mu}(\mathbf{p},i) = e^{\frac{\tau\mu}{2}}S_{\mathrm{diff}}^\tau(\mathbf{p},i). Thus, for fixed τ\tau, regularisation amounts only to an overall rescaling and does not change the relative scores or their minimiser. In other words, the μ\mu-regularised τ\tau-Diffusion score is strongly equivalent to the original τ\tau-Diffusion score. For connected graphs, a natural prior choice is μ=λ2\mu= \lambda_2, the Fiedler eigenvalue. In this case, the contribution of the slowest non-constant diffusion mode v2\mathbf{v}_2 is no longer exponentially damped.

Traditional scores for node selection

Before comparing our scoring rules on examples, we briefly review some of the scoring rules traditionally used for node selection problems. One class are scores based on a ranking of nodes by their assigned probability mass. Such a ranking of VV by p\mathbf{p} can be represented by a permutation σ∈SN\sigma\in\mathfrak{S}_N, such that pσ−1(1)≥⋯≥pσ−1(N)p_{\sigma^{-1}(1)} \geq\cdots\geq p_{\sigma^{-1}(N)}. Note that p\mathbf{p} is not unique if several entries of p\mathbf{p} are tied, but the choice of permutation in this case is irrelevant for the arguments that follow.

Definition 5.14. Let σp∈SN\sigma_{\mathbf{p}} \in\mathfrak{S}_N be a ranking of VV by p\mathbf{p}.

  1. The rank score is defined as

Srank(p,i)=σp(i)∈{1,…,N}(24)S_{\mathrm{rank}}(\mathbf{p}, i) = \sigma_{\mathbf{p}}(i) \in\{1,\ldots,N\} \tag*{(24)}
  1. The top-KK error is defined as

StopK(p,i)=1σp(i)>K∈{0,1}(25)S_{\mathrm{top}K}(\mathbf{p}, i) = \mathbf{1}_{\sigma_{\mathbf{p}}(i)>K} \in\{0,1\} \tag*{(25)}

As is the case for our graph-aware scores, smaller values indicate better performance. Alternatively, often one considers the inverse rank score σp(i)−1\sigma_{\mathbf{p}}(i)^{-1} or the top-KK hit 1σp(i)≤K\mathbf{1}_{\sigma_{\mathbf{p}}(i)\leq K} instead. In Appendix § 11, we show the following reassuring fact:

Proposition 5.15. Both the rank score and the top-KK error are proper scoring rules.

By the same token, the inverse rank score and the top-KK hit are proper scoring rules according to the opposite sign convention (higher values are better). However, all of these rank-based scoring rules completely ignore the graph-structure. Moreover, they are very far from strictly proper: altering p\mathbf{p} does not change the score as long as the ranking of the entries is preserved. A further weakness, specific to the top-KK error, is that it is binary and therefore meaningful only in aggregate, i.e., as an error rate over multiple examples.

Another often used evaluation metric (see, e.g., [3]; Zhu & Ying (2016); [26]; Paluch et al. (2018)) is the Error distance. Assuming that p\mathbf{p} is uni-modal, consider its mode (i.e., the top-1 prediction) denoted by mp=arg⁡max⁡j∈Vpjm_{\mathbf{p}} = \arg\max_{j\in V} p_j.

Definition 5.16. The Error distance is defined as

Sed(p,i)=d(mp,i)∈{1,…,diam⁡(G)}(26)S_{\mathrm{ed}}(\mathbf{p}, i) = d(m_{\mathbf{p}}, i) \in\{1,\ldots,\operatorname{diam}(G)\} \tag*{(26)}

where d:V×V→Nd : V \times V \to\mathbb{N} denotes the shortest-path distance on GG and diam⁡(G)\operatorname{diam}(G) the diameter of GG.

If the distribution is multi-modal, any tie-breaking mechanism or average over modes may be employed without affecting the following discussion.

In contrast to the rank-based scores, error distance does take the graph structure into account. However, by focusing solely on the mode of p\mathbf{p}, the Error distance essentially ignores the probabilistic nature of the prediction or estimate it is supposed to evaluate. It is therefore not surprising that we find the following negative result:

Proposition 5.17. The Error distance is not a proper scoring rule.

A simple counter-example is given in the Appendix § 11. The Error distance thus lacks statistical justification and we do not recommend using it. Furthermore, we would like to point out that resorting to a p\mathbf{p}-averaged version of the Error distance does not resolve the issue either, despite taking into account the full distribution:

Proposition 5.18. The average Error distance Saed(p,i)=∑j=1Npjd(j,i)S_{\mathrm{aed}}(\mathbf{p}, i) = \sum_{j=1}^{N} p_j d(j,i) is not a proper scoring rule.

Again, a counter-example is provided in Appendix § 11. Intuitively, however, the reason is clear: this score unduly rewards overconfident estimates.

In the literature on hierarchical classification, a closely related metric is the Hierarchical error distance, which we discuss in § 5.6 together with its impropriety. The counterexample of Appendix § 11 applies to it as well, using the same toy tree.

Table 1 summarises the properties of the traditional evaluation metrics for node selection tasks alongside the proposed scores.

ScoreGraph-awareProperStrictly properParameters
Rank score×\times✓\checkmark×\times—
Top-KK error×\times✓\checkmark×\timesK=1,2,3,…K=1,2,3,\ldots
Brier score×\times✓\checkmark✓\checkmark—
Log-score×\times✓\checkmark✓\checkmark—
Error distance✓\checkmark×\times×\times—
Resistance score✓\checkmark✓\checkmark✓\checkmark—
Diffusion score✓\checkmark✓\checkmark✓\checkmarkτ>0\tau>0

Table 1. Evaluation metrics for node selection on general graphs.

Comparison of scores: a toy example

We illustrate the differences between the proposed scores and classical alternatives with a concrete example.

The left panel of Figure 2 shows a fixed graph of ten nodes with a designated true node. We consider six probability distributions, each placing equal mass on four nodes, so that the support always consists of exactly four nodes. The top row of distributions includes the true node in the support, while the bottom row does not. Within each row, the three distributions differ in the distance of their mass from the true node: the leftmost concentrates mass near the true node, whereas the middle and rightmost place mass farther away.

Figure 2. Left: Six different probabilistic node estimates on the same toy graph. The red circle indicates the true node ii; the gray shading indicates the probabilistic estimate pp of ii, with probability mass 0.25 assigned to each gray node. Right: Evaluation of these estimates by different scores. For each score, values are reported for the six estimates shown on the left, in matching order. Lower scores indicate better performance. The τ\tau-Diffusion score uses the regularisation with μ=λ3\mu= \lambda_3.

Top-KK error. Since all four-element supports either include or exclude the true node, the top-4 error gives 0 to all three top-row distributions and 1 to all three bottom-row distributions. As a graph-blind metric, it is unable to distinguish any further: within each row the three distributions are seen as equally valid, despite differing substantially in their proximity to the true node.

Brier score. The Brier score is also unaware of the graph structure. It depends only on the probability mass at the true node and on the degree of uniformity of the distribution away from the true node. In our constrained toy example with four equal masses, the latter is fully determined by the former. Consequently, the Brier score also assigns lower scores to the top-row distributions than to the bottom-row ones, and fails to see any difference between the distributions within a row.

Resistance score. By contrast, the Resistance score is graph-aware. Like the two classical scores, it prefers the distributions in the top row to those in the bottom row. However, it also discriminates within each row, correctly identifying the distributions on the left as superior to those on the right.

Diffusion score. At small τ=0.1\tau= 0.1, the Diffusion score approximates the Brier score (Proposition 5.13). Indeed, the scores within each row are nearly equal, with only small differences reflecting the graph structure. At τ=1\tau= 1 the graph-awareness increases and the pattern in this case is not unlike that of the Resistance score. At large τ=10\tau= 10, however, the score converges to a cluster-level Brier score (Proposition 5.13) that reflects the macroscopic structure of the graph. It primarily distinguishes the two main clusters, favouring estimates that place all probability mass in the upper one, which contains the true node: top-left, top-middle, and bottom-left score substantially better than the remaining estimates, which place a quarter of their mass in the lower cluster. Within each of these two groups, the score further favours estimates that concentrate more of their probability mass in the dense upper-right sub-cluster containing the true node: top-left over top-middle and bottom-left in the first group, and bottom-middle and bottom-right over top-right in the second. In summary: the coarse-scale structure dominates the score, with finer-scale structure providing a secondary distinction. These examples illustrate how the parameter τ\tau controls the spatial scale at which the Diffusion score operates.

Scoring rules on rooted trees: the case of hierarchical classification

Hierarchical classification is a node selection task in which the graph is a rooted taxonomy tree T=(V,E)T = (V,E) whose leaf nodes V~⊂V\widetilde{V} \subset V correspond to the most fine-grained categories. In this section we apply the scores of the preceding sections to this setting and discuss their relationship to existing approaches.

Following Silla & Freitas (2011), we distinguish two settings depending on where probability mass may be placed. In mandatory leaf-node prediction (MLP), the standard setting in image classification, the classifier assigns all probability mass to leaf nodes: p~∈ΔN~−1\widetilde{\mathbf{p}} \in\Delta^{\widetilde{N}-1} is a distribution over V~\widetilde{V}, embedded into ΔN−1\Delta^{N-1} by assigning zero mass to internal nodes. In non-mandatory leaf-node prediction (NMLP), mass may be placed on any node of VV, including internal nodes.

LCA-height and Hierarchical error distance. A widely used hierarchy-aware evaluation metric is Hierarchical error distance, introduced alongside the ImageNet benchmark (Russakovsky et al., 2015) and since adopted broadly.

Definition 5.19. Let T=(V,E)T = (V,E) be a rooted tree. For i,j∈Vi,j \in V, let LCA⁡(i,j)\operatorname{LCA}(i,j) denote their lowest common ancestor and height⁡(j)\operatorname{height}(j) the length of the longest downward path from jj to any leaf in its subtree (leaves have height 0). The Hierarchical error distance is

SLCA(p,i):=height⁡(LCA⁡(mp,i)),(27)S_{\mathrm{LCA}}(\mathbf{p},i) := \operatorname{height}(\operatorname{LCA}(m_{\mathbf{p}},i)), \tag*{(27)}

where mp=arg⁡max⁡jpjm_{\mathbf{p}} = \arg\max_j p_j is the mode (i.e., top-1 prediction) of p\mathbf{p}.

Like the Error distance (Definition 5.16), of which it is the natural hierarchical analogue, SLCAS_{\mathrm{LCA}} depends on p\mathbf{p} only through its mode mpm_{\mathbf{p}} and is therefore not a proper scoring rule:

Proposition 5.20. SLCAS_{\mathrm{LCA}} is not a proper scoring rule.

We refer to Appendix § 11 for a counterexample using the same tree and distributions as those for the Error distance (Propositions 5.17 and 5.18).

Several papers [4, 27] (Russakovsky et al. 2015) also use the average Hierarchical error distance from each of the top-KK classes. This metric is denoted distance@KK in Karthik et al. [27] and reduces to SLCAS_{\mathrm{LCA}} for K=1K = 1. However, just like in the case of the average Error distance, simple averaging does not make the fundamental deficiencies of the metric go away. Indeed, Karthik et al. [27] point out that distance@KK can be improved at no cost: replacing the ranking based on maximising pjp_j with the ranking based on minimising ∑ipiheight⁡(LCA⁡(i,j))\sum_i p_i \operatorname{height}(\operatorname{LCA}(i,j)) (conditional risk minimisation) reduces distance@KK without retraining. By contrast, a strictly proper scoring rule such as SresS_{\mathrm{res}} cannot be manipulated or “gamed” in that way.

The Resistance score as a proper alternative. By Proposition 5.8, the resistance distance on any tree equals the shortest-path distance, so the Resistance score equation 14 takes the explicit form

Sres(p,i)=∑j∈Vpjd(i,j)−12∑j,k∈Vpjd(j,k)pk,(28)S_{\mathrm{res}}(\mathbf{p},i) = \sum_{j \in V} p_j d(i,j) - \frac{1}{2}\sum_{j,k \in V} p_j d(j,k) p_k, \tag*{(28)}

where dd denotes the shortest-path distance in the taxonomy tree. The first term measures the expected taxonomic distance of p\mathbf{p} from the true class ii; the second term is the variance of p\mathbf{p} under the tree distance metric in the sense of Devrient et al. (2022).

Since d(i,j)=depth⁡(i)+depth⁡(j)−2depth⁡(LCA⁡(i,j))d(i,j)=\operatorname{depth}(i)+\operatorname{depth}(j)-2\operatorname{depth}(\operatorname{LCA}(i,j)) for any rooted tree, where depth⁡(j)=d(r,j)\operatorname{depth}(j)=d(r,j) denotes the distance from the root rr to jj, substituting into equation 28 and expanding yields

Sres(p,i)=depth⁡(i)−2Ej∼p[depth⁡(LCA⁡(i,j))]+Ej,k∼p[depth⁡(LCA⁡(j,k))].(29)S_{\mathrm{res}}(\mathbf{p},i)=\operatorname{depth}(i)-2\mathbb{E}_{j\sim p}\left[\operatorname{depth}(\operatorname{LCA}(i,j))\right]+\mathbb{E}_{j,k\sim p}\left[\operatorname{depth}(\operatorname{LCA}(j,k))\right]. \tag*{(29)}

(29) expresses the Resistance score purely in terms of LCA depths: its calibration term rewards distributions that concentrate probability mass on classes sharing a deep LCA with the true class ii, while the entropy term rewards a distribution if two independent draws from it tend to share a shallow LCA.

On a balanced tree (where all leaves have the same depth dd), the identity height⁡(j)=d−depth⁡(j)\operatorname{height}(j)=d-\operatorname{depth}(j) holds for all nodes jj, so equation 29 further simplifies to

Sres(p,i)=2Ej∼p[height⁡(LCA⁡(i,j))]−Ej,k∼p[height⁡(LCA⁡(j,k))]−height⁡(i),(30)S_{\mathrm{res}}(\mathbf{p},i)=2\mathbb{E}_{j\sim p}\left[\operatorname{height}(\operatorname{LCA}(i,j))\right]-\mathbb{E}_{j,k\sim p}\left[\operatorname{height}(\operatorname{LCA}(j,k))\right]-\operatorname{height}(i), \tag*{(30)}

which is purely in terms of LCA heights. Given that i=LCA⁡(i,i)i=\operatorname{LCA}(i,i), this is exactly twice the kernel score of equation 9 with kernel k(i,j)=height⁡(LCA⁡(i,j))k(i,j)=\operatorname{height}(\operatorname{LCA}(i,j)). This observation makes it evident that the Resistance score is the natural way to turn the Hierarchical error distance into a proper scoring rule. It is obtained by replacing mode-evaluation with a carefully balanced distribution-averaging.

The log-score family. The resistance score is not the only strictly proper scoring rule for hierarchical classification in the MLP setting. Bertinetto et al. [4] introduce the hierarchical cross-entropy (HXE), a hierarchy-aware training loss generalising the log-score, apparently unaware that it constitutes a proper scoring rule. As a consequence, neither Bertinetto et al. [4] nor Karthik et al. [27] apply HXE directly as an evaluation metric, which would have sidestepped the gameability of SLCAS_{\mathrm{LCA}} entirely. Urbani et al. (2024) generalise HXE and prove propriety. Below we extend their result to strict propriety.

For a node j∈Vj\in V denote by par⁡(j)\operatorname{par}(j) its parent in the rooted tree, by Anc⁡(j)⊂V\operatorname{Anc}(j)\subset V the closed set of its ancestors (i.e., including jj itself), by V~(j)={k∈V~∣j∈Anc⁡(k)}\widetilde{V}(j)=\{k\in\widetilde{V}\mid j\in\operatorname{Anc}(k)\} the set of leaves in its subtree, and by Pj(p~):=∑k∈V~(j)p~kP_j(\widetilde{\mathbf p}):=\sum_{k\in\widetilde{V}(j)}\widetilde{p}_k the total probability mass on that subtree.

The hierarchical cross-entropy (HXE) is defined for i∈V~i\in\widetilde{V} by

SHXE(p~,i)=−∑j∈Anc⁡(i)∖{r}e−α⋅depth⁡(j)log⁡Pj(p~)Ppar⁡(j)(p~),(31)S_{\mathrm{HXE}}(\widetilde{\mathbf p},i)=-\sum_{j\in\operatorname{Anc}(i)\setminus\{r\}}e^{-\alpha\cdot\operatorname{depth}(j)}\log\frac{P_j(\widetilde{\mathbf p})}{P_{\operatorname{par}(j)}(\widetilde{\mathbf p})}, \tag*{(31)}

where α≥0\alpha\geq0 is a free parameter. At α=0\alpha=0 all weights equal 1 and the log-ratios telescope to log⁡p~i\log\widetilde{p}_i, recovering the standard log-score. For α>0\alpha>0, the exponential factor down-weights fine-grained (deep) terms and up-weights coarse (near-root) terms, so that the score penalises taxonomically distant errors more heavily. The parameter α\alpha plays a similar role as τ\tau in the Diffusion score (§ 5.3): both interpolate between a score over independent classes (the log-score for α=0\alpha=0, and the Brier score for τ=0\tau=0, respectively) and a progressively more coarse-grained, hierarchy- or graph-aware score.

Urbani et al. (2024) generalise HXE to the family

SUrb(p~,i)=−∑j∈Anc⁡(i)∖{r}wjlog⁡Pj(p~)(32)S_{\mathrm{Urb}}(\widetilde{\mathbf p},i)=-\sum_{j\in\operatorname{Anc}(i)\setminus\{r\}}w_j\log P_j(\widetilde{\mathbf p}) \tag*{(32)}

with arbitrary positive weights wj>0w_j>0, using log-marginals rather than log-ratios. Expanding the ratios in equation 31 shows that SHXES_{\mathrm{HXE}} is a special case of equation 32 with weights wj=e−α⋅depth⁡(j)(1−e−α)w_j=e^{-\alpha\cdot\operatorname{depth}(j)}(1-e^{-\alpha}) for internal nodes j∈Anc⁡(i)∖{i,r}j\in\operatorname{Anc}(i)\setminus\{i,r\} and wi=e−α⋅depth⁡(i)w_i=e^{-\alpha\cdot\operatorname{depth}(i)} for the leaf ii. Urbani et al. (2024) prove that SUrbS_{\mathrm{Urb}} is proper when the weights are balanced, which means that ∑j∈Anc⁡(k)∖{r}wj\sum_{j\in\operatorname{Anc}(k)\setminus\{r\}}w_j is the same constant CC for all leaves k∈V~k\in\widetilde{V}. In fact, their proof readily extends to strict propriety:

Proposition 5.21. SUrbS_{\mathrm{Urb}} is strictly proper whenever the weights are balanced.

Proof. Let q~∈ΔN~−1\tilde{\mathbf{q}} \in\Delta^{\tilde{N}-1} be a distribution over the leaf nodes and f~∈{v~∈RN∣Pj(v~)>0 ∀j∈V}⊃ΔN~−1\tilde{\mathbf{f}} \in\{\tilde{\mathbf{v}} \in\mathbb{R}^{N} \mid P_j(\tilde{\mathbf{v}}) > 0\ \forall j \in V\} \supset\Delta^{\tilde{N}-1} a more general vector. The expectation

E(f~):=Ei∼q~[SUrb(f~,i)]=−∑i∈V~q~i∑j∈Anc⁡(i)∖{r}wjlog⁡Pj(f~)=−∑j∈V∖{r}∑i∈V~(j)q~iwjlog⁡Pj(f~)=−∑j∈V∖{r}Pj(q~)wjlog⁡Pj(f~)\begin{aligned} E(\tilde{\mathbf{f}}) := \mathbb{E}_{i \sim\tilde{\mathbf{q}}}[S_{\mathrm{Urb}}(\tilde{\mathbf{f}},i)] = - \sum_{i \in\tilde{V}} \tilde{q}_i \sum_{j \in\operatorname{Anc}(i)\setminus\{r\}} w_j \log P_j(\tilde{\mathbf{f}}) \\ &= - \sum_{j \in V\setminus\{r\}} \sum_{i \in\tilde{V}(j)} \tilde{q}_i w_j \log P_j(\tilde{\mathbf{f}}) \\ &= - \sum_{j \in V\setminus\{r\}} P_j(\tilde{\mathbf{q}}) w_j \log P_j(\tilde{\mathbf{f}}) \end{aligned}

is strictly convex in f~\tilde{\mathbf{f}}, and so is its restriction to ΔN~−1\Delta^{\tilde{N}-1}. It is not hard to see that the gradient ∇f~E(f~)\nabla_{\tilde{\mathbf{f}}}E(\tilde{\mathbf{f}}) at f~=q~\tilde{\mathbf{f}} = \tilde{\mathbf{q}} has kk-th component ∑j∈Anc⁡(k)∖{r}wj\sum_{j \in\operatorname{Anc}(k)\setminus\{r\}} w_j, which is independent of kk under the balancedness condition. The gradient is therefore proportional to 1\mathbf{1}, which is orthogonal to ΔN~−1\Delta^{\tilde{N}-1}. Its projection to ΔN~−1\Delta^{\tilde{N}-1} is thus zero, which, together with strict convexity, implies that q~\tilde{\mathbf{q}} is the unique minimiser of EE in ΔN~−1\Delta^{\tilde{N}-1}. But this is the same as strict propriety of SUrbS_{\mathrm{Urb}}.

For HXE, the weights satisfy ∑j∈Anc⁡(k)∖{r}wj=e−α\sum_{j \in\operatorname{Anc}(k)\setminus\{r\}} w_j = e^{-\alpha} for every leaf k∈V~k \in\tilde{V}, independently of depth⁡(k)\operatorname{depth}(k) (the sum telescopes), so the balancedness condition holds on any tree.

Corollary 5.22. SHXEαS_{\mathrm{HXE}}^{\alpha} is strictly proper for every α≥0\alpha\ge0.

Both SUrbS_{\mathrm{Urb}} and SHXEαS_{\mathrm{HXE}}^{\alpha} are defined for MLP, and there is no obvious extension to NMLP. The balancedness condition cannot hold simultaneously for all nodes kk beyond just the leaves, and the gradient argument breaks down.

The following observation is trivial:

Proposition 5.23. On a rooted tree of depth 1 (star graph) with NN nodes and N~=N−1\tilde{N} = N - 1 leaves, the Resistance score in the MLP setting is strongly equivalent to the Brier score with N~\tilde{N} classes, while SUrbS_{\mathrm{Urb}} (and therefore also HXE) is strongly equivalent to the logarithmic score.

In summary, the Resistance score and the HXE are both strictly proper and hierarchy-aware, but generalise different hierarchy-blind scores: the Resistance score generalises the Brier score (and the RPS), while HXE and the Urbani score generalise the logarithmic score. The Resistance score additionally applies to both MLP and NMLP and requires no free parameter. We compare the two families empirically in § 7. Table 2 gives an overview of hierarchy-aware metrics for single-label hierarchical classification.

ScoreReferenceProperStrictly properNMLPParameters
Wu–Palmer similarityWu & Palmer (1994)×\times×\times✓\checkmark—
Gen. tree distance lossCao et al. [8]×\times×\times✓\checkmarkc≥0c \ge0
Tree distance loss (c=0c = 0)Ramaswamy et al. (2015)×\times×\times✓\checkmark—
distance@KKKarthik et al. [27]×\times×\times✓\checkmarkK=1,2,3,…K = 1, 2, 3, \ldots
Hier. error dist. (K=1K = 1)Russakovsky et al. (2015)×\times×\times✓\checkmark—
Urbani familyUrbani et al. (2024)✓\checkmark✓\checkmark×\timeswj>0w_j > 0 balanced
HXE (wj∝e−α depth(j)w_j \propto e^{-\alpha\ \mathrm{depth}(j)})Bertinetto et al. [4]✓\checkmark✓\checkmark×\timesα≥0\alpha\ge0
Resistance score[ours]✓\checkmark✓\checkmark✓\checkmark—

Table 2. Hierarchy-aware evaluation metrics for (single-label) hierarchical classification. All metrics are applicable to the MLP setting, and the NMLP column specifies whether each metric can be applied meaningfully to the NMLP setting as well.

Efficient computation

Both the Resistance score and the Diffusion score are defined in terms of the graph Laplacian LL, and their naive computation via dense matrix operations is prohibitively expensive for large graphs. In this section, we briefly describe efficient alternatives.

Resistance score. The naive computation of SresS_{\mathrm{res}} requires the Moore–Penrose pseudoinverse L†L^{\dagger}, which costs O(N3)\mathcal{O}(N^3) via SVD (or O(Nη)\mathcal{O}(N^\eta) with η\eta close to 3 when using fast matrix multiplication). However, recall from equation (15) the quadratic form of the Resistance score, Sres(p,i)=(p−ei)TL†(p−ei)S_{\mathrm{res}}(\mathbf{p},i)=(\mathbf{p}-\mathbf{e}_i)^{\mathsf{T}}L^{\dagger}(\mathbf{p}-\mathbf{e}_i). The key observation is that v=p−ei∈1⊥\mathbf{v}=\mathbf{p}-\mathbf{e}_i\in\mathbf{1}^{\perp}. For a connected graph, LL restricted to 1⊥\mathbf{1}^{\perp} is invertible, and its inverse coincides with the restriction of L†L^{\dagger}. Thus, L†vL^{\dagger}\mathbf{v} can be obtained by solving Lx=vL\mathbf{x}=\mathbf{v} on the subspace 1⊥\mathbf{1}^{\perp}. The Resistance score can therefore be computed as the dot product vTx\mathbf{v}^{\mathsf{T}}\mathbf{x}, without ever forming L†L^{\dagger} explicitly. Laplacian solvers (Spielman & Teng (2004)) solve such systems approximately in nearly linear time in ∣E∣\lvert E\rvert. Our fast implementation uses the ApproxChol solver from the Laplacians.jl Julia package (Gao et al. [17]), called from Python via juliacall. Coscia & Devriendt [9] demonstrate on a range of real-world networks and representative synthetic network models that the approximation error is negligible for practical purposes, while empirically the solver scales as O(Nη)\mathcal{O}(N^\eta) with η∈[1.1,1.4]\eta\in[1.1,1.4], compared to η∈[2.6,2.9]\eta\in[2.6,2.9] for the SVD-based baseline. This translates to a runtime advantage over the exact SVD baseline of several orders of magnitude for large and reasonably sparse graphs.

Diffusion score. The naive computation of SdiffτS_{\mathrm{diff}}^{\tau} requires forming the full N×NN\times N matrix exponential e−τ2L\mathrm{e}^{-\frac{\tau}{2}L}, which costs O(N3)\mathcal{O}(N^3). Since Sdiffτ(p,i)=(p−ei)Te−τ2L(p−ei)S_{\mathrm{diff}}^{\tau}(\mathbf{p},i)=(\mathbf{p}-\mathbf{e}_i)^{\mathsf{T}}\mathrm{e}^{-\frac{\tau}{2}L}(\mathbf{p}-\mathbf{e}_i), it suffices to compute the matrix-exponential-vector product e−τ2Lv\mathrm{e}^{-\frac{\tau}{2}L}\mathbf{v} for v=p−ei\mathbf{v}=\mathbf{p}-\mathbf{e}_i. This can be done efficiently using Krylov subspace methods (Saad (1992)), such as the expm_multiply routine (Al-Mohy & Higham [1]) of SciPy. It approximates e−τ2Lv\mathrm{e}^{-\frac{\tau}{2}L}\mathbf{v} by projecting onto a low-dimensional Krylov subspace span⁡{v,Lv,L2v,…,Lk−1v}\operatorname{span}\{\mathbf{v},L\mathbf{v},L^2\mathbf{v},\ldots,L^{k-1}\mathbf{v}\}, requiring only sparse matrix-vector products with LL. The cost is O(∣E∣⋅k)\mathcal{O}(\lvert E\rvert\cdot k) where kk is the Krylov dimension, which is chosen adaptively by the algorithm based on the spectral radius of τ2L\frac{\tau}{2}L and a target accuracy. In practice, it tends to be small relative to NN, although it grows with τ\tau.

A canonical use case: source detection

As a first concrete example of a node selection task, we consider the source detection problem. Consider a network G=(V,E)G=(V,E) whose nodes VV represent individuals and whose edges EE represent contacts between them. An epidemic outbreak takes place on this network, with the disease spreading along the edges. At any given time, nodes occupy different states with respect to the disease, for example susceptible or infected. Denote by M\mathcal{M} the stochastic process governing the disease dynamics, such as a simple Susceptible-Infected (SI) model characterised by a fixed transmission probability per unit time. For simplicity, we assume the outbreak began at time t=0t=0 from a single unknown source node i0∈Vi_0\in V.

Suppose that we are given the vector of observed states of all nodes at time t=Tt=T, denoted by OT\mathbf{O}_T. Figure 3a shows an example of such a snapshot, taken from a simulated outbreak on the well-known Zachary’s Karate Club network (Zachary (1977)). The task is to identify the most likely source of the outbreak from this snapshot alone.

An instance of the source detection problem on the Karate Club network

Figure 3. An instance of the source detection problem on the Karate Club network. (a) Infection status at time TT: red nodes are infected, blue nodes are susceptible. (b) True conditional source distribution qq, computed by ABC with zero-tolerance rejection sampling. (c)–(f) Four different probabilistic estimates pp of the source node i0i_0. Node shading represents estimated probability. The scatter plots show the estimated probabilities against the true probabilities from (b), whereby each dot represents a node. A perfectly calibrated estimator would place all points on the diagonal.

Naturally, the source is not fully determined by OT\mathbf{O}_T. Rather, the problem can be framed as estimating the true conditional distribution qi=Pr⁡M(i0=i∣OT)q_i=\Pr_{\mathcal{M}}(i_0=i\mid\mathbf{O}_T) over potential source nodes i∈Vi\in V, where the probability is taken over the joint distribution induced by a uniformly random source node i0∈Vi_0\in V and the subsequent stochastic dynamics M\mathcal{M}. Due to the inverse nature of the problem and the inherent combinatorial complexity of stochastic processes on networks, this distribution q=(q1,…,qN)T\mathbf{q}=(q_1,\ldots,q_N)^{\mathsf{T}} is generally intractable. For the small network in our example, however, we can estimate it numerically almost exactly by Approximate Bayesian computation (ABC) with a zero-tolerance criterion in the rejection sampler: we accept only those simulation runs that produce exactly the observed snapshot OT\mathbf{O}_T at time t=Tt=T, which are 852 in total. Figure 3b depicts the resulting distribution q\mathbf{q}.

Suppose now that we have a model that issues a probabilistic estimate p\mathbf{p} of the source node i0i_0. Figures 3c–f show four such estimates. Three are derived from published source detection models (see Appendix § 12 for details); the fourth estimate is a piecewise-uniform heuristic added for illustrative purposes. The four estimators are not meant as a representative benchmark of source detection methods. Figure 3 also shows calibration plots, which compare the estimated probabilities p\mathbf{p} to the true probabilities q\mathbf{q} for each model. These leave no doubt that the estimates in panels (c) and (d) are superior to those in (e) and (f), with (c) likely the best.

However, in real scenarios without access to the entire distribution q\mathbf{q}, the estimate p\mathbf{p} can only be judged on the basis of the single ground-truth source i0i_0 using a scoring rule. Figure 4 shows how each probabilistic estimate stacks up under a range of scoring rules, averaged over all 852 realisations i0∼qi_0 \sim\mathbf{q}.

Figure 4. Comparison of scores on the four source estimators (c)–(f) against the true distribution (b), averaged over realisations i0∼qi_0 \sim q. Lower is better for all scores. Colour represents performance normalised within each column (darkest: worst model). The τ\tau-Diffusion score uses the regularisation with μ=0.8\mu= 0.8.

The results reveal a number of troubling patterns among the traditional scores. First and most importantly, they are sometimes rather off-mark: estimator (f), for instance, consistently receives the same or better scores than (d), even though visual inspection and the calibration plots confirm it is clearly inferior. Second, some scores show very limited ability to discriminate between the four estimates: for example, the Error distance rates estimators (c), (e) and (f) identically. Third, the traditional scores disagree substantially with one another about the ranking of the estimates.

The main reason for this behaviour is that estimators (e) and (f) are both overconfident. Their mode coincides with the mode of the true distribution (b), but their distributions are significantly more peaked. All strictly proper scores (including the graph-unaware Brier score) detect and penalise this excess sharpness: (e) and (f) score worse than (c) and (d) on every strictly proper score. The top-KK error and Error distance, which depend only on the mode or top-KK of the distribution, are blind to this.

The graph-aware strictly proper scores detect additional structure beyond sharpness. For example, graph-aware scores clearly prefer (f) over (e), while the difference in Brier score is less significant. Moreover, estimate (d) achieves the best Diffusion score at τ=30\tau= 30 among all non-true distributions. This distribution was handcrafted to place exactly the right total mass on each of the three main clusters of the infected subgraph but distributes it uniformly within these clusters. The example shows the sensitivity of the Diffusion score at large τ\tau to correct cluster-level mass assignment.

Our example illustrates the limitations of classical scores vis-à-vis the new graph-aware and strictly proper scores. Note again that all scores in Figure 4 are averaged over the true distribution q\mathbf{q}, which should already have washed out many of the more egregious artefacts that may appear when evaluating on a single realisation i0∼qi_0 \sim\mathbf{q}. Any real epidemic source detection scenario yields exactly one ground truth per outbreak, making the choice of a strictly proper, graph-aware score all the more consequential.

Application to hierarchical classification: ImageNet

As a second concrete illustration of the node selection framework, we apply our scoring rules to the evaluation of image classifiers on the ImageNet-1k benchmark ((Russakovsky et al., 2015)). In this setting, the graph is the WordNet taxonomy pruned to a tree TT, the leaf nodes V~\widetilde{V} are the 1,000 fine-grained ImageNet classes, and the node selection task is: given an image, identify its correct leaf label. A classifier outputs a distribution p~∈ΔN~−1\widetilde{\mathbf{p}} \in\Delta^{\widetilde{N}-1} over V~\widetilde{V}, and the true label is a single leaf i∈V~i \in\widetilde{V}. This is the mandatory leaf-node prediction (MLP) setting of Section 5.6.

Setup

Label graph. Starting from the WordNet hypernym graph, we take the subgraph made up of the 1,000 ImageNet leaf synsets and all their ancestors, yielding a directed acyclic graph (DAG) of 1,860 nodes and 1,937 edges. The DAG structure arises because a small percentage of classes are part of multiple superclasses. Following Bertinetto et al. [4] we then prune the DAG to a tree: for each leaf, we retain the longest path to the root, breaking ties in favour of paths that introduce the fewest new nodes. This yields a tree of 1,816 nodes, on which the HXE of Bertinetto et al. [4] is well-defined and the Resistance score, according to Proposition 5.8, has the explicit form equation 28.

Classifiers. We evaluate ten pretrained classifiers spanning a wide range of architectural families and accuracy levels. Four models represent architecturally distinct approaches at similar top-1 error rates (18–22%): ConvNeXt-Tiny (Liu et al., [33]) (modern CNN), Swin-Tiny (Liu et al., [32]) (hierarchical Vision Transformer), ViT-S/16 (Dosovitskiy et al., [13]) (pure Vision Transformer), and EfficientNet-B2 (Tan & Le, 2019) (compound-scaled CNN). Six further models of varying top-1 error rates (19–33%) provide a broader comparison baseline: ResNet-50 and ResNet-18 (He et al., [22]), EfficientNet-B0 (Tan & Le, 2019), MobileNetV3-Large and MobileNetV3-Small (Howard et al., [23]), and ShuffleNet-V2 (Ma et al., 2018). All models use publicly available pretrained weights. We run inference on the full ImageNet-1k validation set (50,000 images) and save the softmax probability vectors.

Metrics. We report top-1 and top-5 error, Hierarchical error distance@1 and distance@5 (improper, mode-dependent), log-loss, HXE, Brier score and the Resistance score. For HXE we use α=0.5\alpha= 0.5, the mid-range value that Bertinetto et al. [4] report as best-performing on ImageNet when using HXE as a training loss.

Aggregate comparison

Figure 5 shows the full comparison. The aggregate model ranking produced by the Resistance score aligns closely with top-1 error rate, Brier score, and log-loss (Spearman rank correlations of 0.99, 0.99, and 0.94, respectively). Hierarchical error distance@1 agrees perfectly with top-1 error as well. The hierarchical error distance@5, by contrast, is essentially uncorrelated with top-1 error (Spearman rank correlation −0.07), underlining our doubts about distance@K as a suitable hierarchy-aware metric. Meanwhile, HXE correlates reasonably well with top-1 error (Spearman rank correlation 0.79) and the Resistance score, but shows some notable disagreements, indicating that it captures a subtly different notion of hierarchical quality than the Resistance score.

Figure 5. Comparison of ten ImageNet classifiers, ordered by their Resistance Score. All metrics are averaged over 50,000 validation images. Lower is better throughout (top-1 and top-5 reported as error rates).

The most obvious anomaly is ResNet-50, which ranks third by top-1 error rate and Resistance score but last by distance@5, worse than models with top-1 error rates 12 percentage points higher. ResNet-type models trained with standard cross-entropy are known to be systematically overconfident (Guo et al., [21]): they concentrate too much probability mass on the top-1 prediction. The remaining mass is spread thinly across the taxonomy with little consideration of the hierarchical structure, so the top-5 predictions land far from the true class on average. Proper scores are less affected because they weigh predictions by their probability: the low mass outside the top-1 class contributes little to either the calibration or the entropy term.

Another interesting comparison is ViT-S/16 versus EfficientNet-B2. EfficientNet-B2 has a marginally lower top-1 error rate and distance@1, yet all four proper scores favour ViT-S/16, indicating better distributions overall. Similarly, ConvNeXt-Tiny beats Swin-Tiny on all proper scores and on distance@1, but distance@5 gives the opposite verdict. This again underscores the fact that an improper score such as Hierarchical error distance@KK should not be trusted for evaluation.

At a more granular level, we examine how the metrics behave in cases where models struggle to identify the correct class. For each individual model, we compute Spearman correlations between metrics on all misclassified images (wrong top-1). Figure 6 reports the results, with all models exhibiting very similar patterns. First, the Brier score is essentially uncorrelated with distance@1 and is only weakly correlated with distance@5 and HXE. This illustrates at the image level that the Brier score and the hierarchy-aware metrics measure orthogonal aspects of prediction quality: the Brier score prefers a uniform distribution over the wrong classes, while distance@KK and HXE favour hierarchical proximity to the true class. Second, log-loss sits somewhere in between: it correlates most clearly with Brier, since both are sensitive to the probability assigned to the true class, and more moderately with Resistance, HXE, distance@5 and distance@1. Third, the Resistance score correlates with HXE, but not perfectly. This shows that the two scores are complementary rather than redundant, even though both are hierarchy-aware and strictly proper.

Figure 6. Spearman correlation of different scores, averaged over all images that are misclassified by the respective model.

Qualitative examples

Figures 7–9 show head-to-head comparisons of selected model pairs on three individual images, illustrating characteristic behaviours of the different evaluation metrics. Each figure shows the relevant subtree of the WordNet hierarchy, the probability mass that the models place on the included classes, and a score comparison table for that image.

In Figure 7 (Image #16763), ResNet-50 correctly predicts a tabby cat, while Swin-Tiny opts for a tiger cat as top-1. All classical metrics are either unable to distinguish the two models or prefer ResNet-50. However, Swin-Tiny is actually significantly more confident at predicting a cat in general (assigning about 83% of the total probability to cats versus 70% for ResNet-50). As a consequence, the hierarchy-aware scores both prefer Swin-Tiny. This example illustrates that classical proper scores alone are insufficient to detect the hierarchical quality of a distribution.

ResNet-50 versus Swin-Tiny on image #16763, showing output distributions, the induced WordNet taxonomy subtree, and score comparisons

Figure 7. ResNet-50 versus Swin-Tiny on image #16763 (ground truth: tabby). Top: Output distributions of both models on the 15 classes with the highest assigned probability, together with the induced subtree of the WordNet taxonomy. The remaining mass is attributed to ‘other’. Right: Comparisons of different scores. Hierarchy-aware scores favour Swin-Tiny’s concentration of probability mass within the cat subtree.

Figure 8 (Image #22561) shows an example where HXE and the Resistance score disagree. Both ViT-S/16 and Swin-Tiny misclassify the hotdog in the picture: ViT-S/16 confidently predicts bagel (with probability 0.761), placing only 0.008 probability on the true class, while Swin-Tiny’s top-1 is hook (with probability 0.221). HXE favours ViT-S/16, because bagel is close to hotdog in the taxonomy and its hierarchical weighting rewards a confident prediction near the true class. In contrast, the Resistance score favours Swin-Tiny,

ViT-S/16 versus Swin-Tiny on image #22561, showing output distributions, the induced WordNet taxonomy subtree, and score comparisons

Figure 8. ViT-S/16 versus Swin-Tiny on image #22561 (ground truth: hotdog). Top: Output distributions of both models on the 15 classes with the highest assigned probability, together with the induced subtree of the WordNet taxonomy. The remaining mass is attributed to ‘other’. Right: Comparisons of different scores. HXE favours ViT-S/16’s confident prediction of the nearby bagel, while the Resistance score favours Swin-Tiny for placing more mass on the true class.

ResNet-50Swin-Tiny
Top-1 error0.0001.000
Top-5 error0.0000.000
Distance@10.0001.000
Distance@59.2009.200
Log-loss0.5361.179
HXE (α=0.5\alpha=0.5)0.0480.022
Brier score0.2200.748
Resistance score1.3711.018

Table 7.

ViT-S/16Swin-Tiny
Top-1 error1.0001.000
Top-5 error0.0000.000
Distance@17.00017.000
Distance@56.20010.600
Log-loss4.8711.752
HXE (α=0.5\alpha=0.5)0.2880.475
Brier score1.5680.751
Resistance score7.5156.521

Table 8.

because it assigns substantially more probability (0.173) to the true class and otherwise hedges its prediction quite broadly. This illustrates that HXE, like the Diffusion score with large τ\tau, rewards proximity at the cluster level: getting the broad category right matters more than placing mass on the exact true leaf. Whether this is desirable depends on the application.

Finally, Figure 9 (Image #44101) illustrates a potential limitation of hierarchy-aware scores in the standard ImageNet evaluation setting. The image contains a dog of breed vizsla (ground-truth label) and a moped with roughly equal visual prominence. ViT-S/16 concentrates 0.428 mass on vizsla and most remaining mass on related hunting dogs, while ConvNeXt-Tiny places 0.488 on vizsla but 0.137 on moped and 0.058 on motor scooter. Under the official ground truth, the hierarchy-aware scores penalise ConvNeXt-Tiny for this hedging. However, under a ground truth distribution of qvizsla=qmoped=0.5q_{\mathrm{vizsla}} = q_{\mathrm{moped}} = 0.5, the verdict reverses: ConvNeXt-Tiny’s hedging toward moped is now rewarded, outperforming ViT-S/16 in expectation on all scores. We return to the implications of such label ambiguities in the Discussion.

Figure 9. ViT-S/16 versus ConvNeXt-Tiny on image #44101 (ground truth: vizsla). Top: Output distributions of both models on the 15 classes with the highest assigned probability, together with the induced subtree of the WordNet taxonomy. The remaining mass is attributed to ‘other’. Bottom left: Scores under the ground truth vizsla. Hierarchy-aware scores penalise ConvNeXt-Tiny for placing a significant proportion of mass on moped and motor scooter. Bottom right: Expected scores under an ambiguous ground truth qvizsla=qmoped=0.5q_{\mathrm{vizsla}} = q_{\mathrm{moped}} = 0.5. In this case, all scores reward ConvNeXt-Tiny for hedging.

Discussion

Scope and limitations. The scoring rules introduced in this paper are designed for (single) node selection tasks: settings in which the ground truth is a single node i∈Vi \in V and the quality of a probabilistic prediction pp is judged by the proximity of its mass to ii in the graph topology. This is the natural setting for source detection and related localisation problems, where graph proximity is directly meaningful: a predicted source one hop away from the true source is a qualitatively different error from one in a far away corner of the network. For hierarchical classification it is the right framework when the taxonomy genuinely encodes semantic proximity and when the ground truth label is unambiguous.

The ImageNet experiments (§ 7) illustrate both the strength and an important limitation of our scores. When the uncertainty of the annotator (i.e., the true data distribution q\mathbf{q}) is concentrated within a closely connected region of the graph, proper hierarchy-aware scores reward well-calibrated distributional predictions in ways that classical metrics cannot detect. When the true distribution q\mathbf{q} is itself spread across distant parts of the taxonomy (as in the vizsla/moped example of Figure 9), these scores conflate what are effectively independent prediction problems. For large data sets such as ImageNet with relatively few ambiguous labels, such ambiguities likely average out and the aggregate rankings remain trustworthy. However, if label-ambiguities are more abundant, the problem should be treated as a multi-label (or multi-node selection) problem instead.

Choice of scoring rule. Which of the two proposed scoring rules should be used depends both on the graph in question and on the relevant notion of proximity. On small graphs and on sufficiently sparse graphs (in particular trees, which includes the case of hierarchical classification) the Resistance score is the natural choice. It is parameter-free and fully graph-aware. On large and denser graphs, the asymptotic behaviour of the resistance distance raises questions about the sensitivity of the Resistance score to the global graph topology. The Diffusion score provides a more interpretable alternative for this case at the cost of introducing the diffusion time τ\tau as a free parameter. Moreover, if proximity to the true node matters mainly at the cluster level, the Diffusion score with a suitably large value of τ\tau is the score of choice. Likewise, in hierarchical classification, HXE may be preferred over the Resistance score when cluster-level accuracy of a classifier is the primary concern.

Extensions and future work. Several extensions to more general graphs are of interest. The extension to weighted graphs is immediate: replace the adjacency matrix AA with a weighted version W=(wjj′)W = (w_{jj^\prime}), set L=DW−WL = D_W - W where DWD_W is the diagonal matrix of weighted degrees, and all results carry over without modification. The extension to directed graphs is more subtle. The Laplacian of a directed graph is not symmetric, so its pseudoinverse L†L^{\dagger} is not symmetric either, and the effective resistance formula ωjj′=Ljj†+Lj′j′†−2Ljj′†\omega_{jj^\prime} = L^\dagger_{jj} + L^\dagger_{j^\prime j^\prime} - 2L^\dagger_{jj^\prime} no longer defines a symmetric kernel. Symmetrising the Laplacian before taking the pseudoinverse is one workaround, but this is tantamount to discarding all directional information. However, Young et al. (2016) propose a different generalisation of effective resistance to directed graphs. It reduces to the standard effective resistance on undirected graphs and its square root defines a valid metric on the nodes. Whether this generalisation constitutes the right notion of proximity for a given directed-graph application would require careful examination of the score’s properties. We leave this for future work. Two concrete applications motivate this extension: localisation tasks (e.g., source detection) on temporal networks, where the lossless temporal event graph representation of Mellor (2018) represents a temporal network as a DAG whose nodes are events and whose edges encode temporal precedence; and hierarchical classification on DAG-structured taxonomies (e.g., WordNet), where pruning to a tree (as we do in Section 7) discards some structural information that a directed analogue of the Resistance score could exploit.

As hinted at above, a practically important extension is to multi-node selection, where the ground truth is a set of nodes rather than a single one. Multi-node selection is subtly different from simple binary node classification as it constitutes a structured prediction problem rather than treating all nodes independently. It has many applications both on general graphs (e.g., multi-source detection, multi-seed influence maximisation, multi-fault detection) as well as in hierarchical classification (e.g., document labelling, protein function prediction, multi-object image classification). Extending strictly proper scoring rules to multi-node selection tasks is a non-trivial open problem, as it would have to deal with distributions on the power set of VV rather than VV itself.

Strictly proper scoring rules also make natural training losses, since minimising their empirical average encourages the model distribution to match the true data distribution. The Resistance score and Diffusion score can in principle serve as loss functions for node selection problems. The gradient of a kernel score with respect to p\mathbf{p} is straightforward: ∇pSk+(p,i)=K(ei−p)\nabla_{\mathbf{p}} S_k^+(\mathbf{p}, i) = K(\mathbf{e}_i - \mathbf{p}). For the Resistance and Diffusion score, this is computable via the same Laplacian solver or Krylov subspace methods, respectively, as described in § 5.7. One practical challenge is that the gradient vanishes in the corners of the simplex. However, this issue could be bypassed using a Fenchel-Young regularisation of the score as described in [5]. A systematic investigation of graph-aware scoring rules as training losses is left for future work.

Conclusion

In many node selection tasks, proximity in the network matters: a node estimate one hop away from the true node is different from a node estimate in an entirely different region of the network. We argue that evaluation metrics should reflect this distinction and be graph-aware. Yet, as we have shown, the graph-aware metrics in common use, such as Error distance on general graphs and Hierarchical error distance in hierarchical classification, are statistically ill-founded: they are improper scoring rules and therefore produce misleading evaluations.

We have introduced two graph-aware strictly proper scoring rules for probabilistic node selection tasks. The Resistance score is a parameter-free score which reduces to the Brier score on the complete graph and to the RPS on the path graph, thus revealing it as a natural generalisation of these widely used scoring rules to arbitrary graphs. The τ\tau-Diffusion score is a one-parameter family of scores where the diffusion time τ\tau controls the coarse-graining scale of evaluation, from node-level accuracy at τ=0\tau= 0 to cluster-level accuracy at large τ\tau. Both scores can be computed in nearly linear time on large and reasonably sparse graphs.

Specialising to hierarchical classification on rooted trees, the Resistance score can be seen as both the hierarchy-aware generalisation of the Brier score as well as the strict “proprification” of the improper Hierarchical error distance. As such, it is orthogonal to the HXE family of Bertinetto et al. [4] and Urbani et al. (2024) that generalises the logarithmic score instead. We have also shown that the recently established propriety of the HXE family does, in fact, hold strictly.

The generalisation of our scores to weighted graphs is straightforward. Extensions to directed graphs, directed acyclic graphs, temporal networks, multi-node ground truths, and the use of these scores as loss functions for training remain open directions for future work.

Code availability

Code implementing the proposed scoring rules and reproducing all experiments and figures is available at https://github.com/lo-hfk/proper-graph-scoring-rules.

Acknowledgments

This work was supported by the Swiss National Science Foundation (SNSF), grant number 228527.

RPS as a kernel score

We show that the Ranked probability score is a kernel score equation (9) with kernel k(j,j′)=∣i−j∣k(j,j') = |i-j|. Indeed, for j,j′∈{1,…,N}j,j' \in\{1,\ldots,N\}, the identity

∣j−j′∣=∑k=1N−1(1j≤k−1j′≤k)2|j-j'| = \sum_{k=1}^{N-1} \left(\mathbb{1}_{j\leq k}-\mathbb{1}_{j'\leq k}\right)^2

holds by direct inspection. Taking J∼pJ \sim\mathbf{p} and computing the expectation over JJ gives

EJ∼p∣J−i∣=∑k=1N−1EJ∼p[(1J≤k−1i≤k)2]=∑k=1N−1(Var⁡J∼p[1J≤k]+(Fp(k)−1i≤k)2)=∑k=1N−1Fp(k)(1−Fp(k))+RPS⁡(p,i),\begin{aligned} \mathbb{E}_{J\sim\mathbf{p}}|J-i| &= \sum_{k=1}^{N-1}\mathbb{E}_{J\sim\mathbf{p}}\left[\left(\mathbb{1}_{J\leq k}-\mathbb{1}_{i\leq k}\right)^2\right]\\ &= \sum_{k=1}^{N-1}\left(\operatorname{Var}_{J\sim\mathbf{p}}[\mathbb{1}_{J\leq k}]+\left(F_{\mathbf{p}}(k)-\mathbb{1}_{i\leq k}\right)^2\right)\\ &= \sum_{k=1}^{N-1}F_{\mathbf{p}}(k)(1-F_{\mathbf{p}}(k))+\operatorname{RPS}(\mathbf{p},i), \end{aligned}

where Fp(k)=∑j=1kpjF_{\mathbf{p}}(k)=\sum_{j=1}^{k}p_j is the CDF of p\mathbf{p} and we used Var⁡[1J≤k]=Fp(k)(1−Fp(k))\operatorname{Var}[\mathbb{1}_{J\leq k}]=F_{\mathbf{p}}(k)(1-F_{\mathbf{p}}(k)). Taking two independent copies J,J′∼pJ,J'\sim\mathbf{p} and computing the double expectation gives

EJ,J′∼p∣J−J′∣=∑k=1N−1EJ,J′∼p[(1J≤k−1J′≤k)2]=2∑k=1N−1Var⁡J∼p[1J≤k]=2∑k=1N−1Fp(k)(1−Fp(k)).\begin{aligned} \mathbb{E}_{J,J'\sim\mathbf{p}}|J-J'| &= \sum_{k=1}^{N-1}\mathbb{E}_{J,J'\sim\mathbf{p}}\left[\left(\mathbb{1}_{J\leq k}-\mathbb{1}_{J'\leq k}\right)^2\right]\\ &= 2\sum_{k=1}^{N-1}\operatorname{Var}_{J\sim\mathbf{p}}[\mathbb{1}_{J\leq k}]\\ &= 2\sum_{k=1}^{N-1}F_{\mathbf{p}}(k)(1-F_{\mathbf{p}}(k)). \end{aligned}

Combining the two expressions and solving for RPS⁡(p,i)\operatorname{RPS}(\mathbf{p},i) yields

RPS⁡(p,i)=EJ∼p∣J−i∣−12EJ,J′∼p∣J−J′∣,\operatorname{RPS}(\mathbf{p},i)=\mathbb{E}_{J\sim p}|J-i|-\frac{1}{2}\mathbb{E}_{J,J'\sim p}|J-J'|,

which is precisely equation 9 with kernel k(i,j)=∣i−j∣k(i,j)=|i-j|.

Propriety of traditional scores

Proof of Proposition 5.15. Let q,p∈ΔN−1\mathbf{q},\mathbf{p}\in\Delta^{N-1}. Assume w.l.o.g. that the nodes are ordered in such a way that q0≤q1≤⋯≤qN−1q_0\leq q_1\leq\cdots\leq q_{N-1}, then σq(N−1)≤⋯≤σq(1)≤σq(0)\sigma_{\mathbf{q}}(N-1)\leq\cdots\leq\sigma_{\mathbf{q}}(1)\leq\sigma_{\mathbf{q}}(0). For the rank score, propriety is a simple consequence of the rearrangement inequality, which says that for increasing sequences x0,…,xN−1x_0,\ldots,x_{N-1} and y0,…,yN−1y_0,\ldots,y_{N-1} and for all permutations σ∈SN\sigma\in S^N, the expression ∑i=0N−1xiyN−1−i\sum_{i=0}^{N-1}x_i y_{N-1-i} is smaller or equal than ∑i=0N−1xiyσ(i)\sum_{i=0}^{N-1}x_i y_{\sigma(i)}. Specifically, the inequality implies that ∑i=0N−1qiσq(i)≤∑i=0N−1qiσp(i)\sum_{i=0}^{N-1}q_i\sigma_{\mathbf{q}}(i)\leq\sum_{i=0}^{N-1}q_i\sigma_{\mathbf{p}}(i), which proves propriety. Meanwhile, propriety of the top-KK error can be seen as follows:

∑j=0N−1qjStop⁡K(q,j)=∑j=0N−1qj1σq(j)>K=∑j:σq(j)>Kqj=∑j=0N−K−1qj≤∑j:σp(j)>Kqj=∑j=0N−1qj1σp(j)>K=∑j=0N−1qjStop⁡K(p,j).\begin{aligned} \sum_{j=0}^{N-1}q_j S_{\operatorname{top}K}(\mathbf{q},j)=\sum_{j=0}^{N-1}q_j\mathbf{1}_{\sigma_{\mathbf{q}}(j)>K}=\sum_{j:\sigma_{\mathbf{q}}(j)>K}q_j=\sum_{j=0}^{N-K-1}q_j \\ &\leq\sum_{j:\sigma_{\mathbf{p}}(j)>K}q_j=\sum_{j=0}^{N-1}q_j\mathbf{1}_{\sigma_{\mathbf{p}}(j)>K}=\sum_{j=0}^{N-1}q_jS_{\operatorname{top}K}(\mathbf{p},j). \end{aligned}

Proof of Proposition 5.17. Consider the tree graph T=(V,E)T=(V,E) with vertex set V={r,v,a,b,c}V=\{r,v,a,b,c\}, edge set E={(r,v),(v,a),(v,b),(r,c)}E=\{(r,v),(v,a),(v,b),(r,c)\}, and leaf set V~={a,b,c}\widetilde{V}=\{a,b,c\}. The shortest-path distances between the leaf nodes are d(a,b)=2d(a,b)=2, d(a,c)=d(b,c)=3d(a,c)=d(b,c)=3. Let δ∈(0,118)\delta\in(0,\frac{1}{18}) and define distributions over VV,

p=(0,0,13,13+δ,13−δ)andq=(0,0,13,13−δ,13+δ),(33)\mathbf{p}=\left(0,0,\frac{1}{3},\frac{1}{3}+\delta,\frac{1}{3}-\delta\right) \qquad\text{and}\qquad \mathbf{q}=\left(0,0,\frac{1}{3},\frac{1}{3}-\delta,\frac{1}{3}+\delta\right), \tag*{(33)}

where entries correspond to rr, vv, aa, bb and cc, respectively (see Figure 10).

Figure 10. Tree TT with distributions p\mathbf{p} and q\mathbf{q} as defined in equation 33.

For δ>0\delta>0 we have mp=bm_{\mathbf{p}}=b and mq=cm_{\mathbf{q}}=c. Therefore,

Ei∼qSed⁡(p,i)=13⋅d(b,a)+(13−δ)⋅d(b,b)+(13+δ)⋅d(b,c)=13⋅2+0+(13+δ)⋅3=53+3δ\mathbb{E}_{i\sim\mathbf{q}}S_{\operatorname{ed}}(\mathbf{p},i)=\frac{1}{3}\cdot d(b,a)+\left(\frac{1}{3}-\delta\right)\cdot d(b,b)+\left(\frac{1}{3}+\delta\right)\cdot d(b,c)=\frac{1}{3}\cdot2+0+\left(\frac{1}{3}+\delta\right)\cdot3=\frac{5}{3}+3\delta

and

Ei∼qSed⁡(q,i)=13⋅d(c,a)+(13−δ)⋅d(c,b)+(13+δ)⋅d(c,c)=13⋅3+(13−δ)⋅3+0=2−3δ.\mathbb{E}_{i\sim\mathbf{q}}S_{\operatorname{ed}}(\mathbf{q},i)=\frac{1}{3}\cdot d(c,a)+\left(\frac{1}{3}-\delta\right)\cdot d(c,b)+\left(\frac{1}{3}+\delta\right)\cdot d(c,c)=\frac{1}{3}\cdot3+\left(\frac{1}{3}-\delta\right)\cdot3+0=2-3\delta.

Since δ<118\delta<\frac{1}{18} implies 6δ<136\delta<\frac{1}{3}, we have 53+3δ<2−3δ\frac{5}{3}+3\delta<2-3\delta, so Ei∼qSed⁡(p,i)<Ei∼qSed⁡(q,i)\mathbb{E}_{i\sim\mathbf{q}}S_{\operatorname{ed}}(\mathbf{p},i)<\mathbb{E}_{i\sim\mathbf{q}}S_{\operatorname{ed}}(\mathbf{q},i) and the Error distance is improper.

Proof of Proposition 5.18. We use the same tree TT, leaf nodes, distributions p\mathbf{p}, q\mathbf{q}, and δ∈(0,118)\delta\in\left(0,\frac{1}{18}\right) as above. The matrix of shortest-path distances between leaf nodes is

Dsp=[023203330],D_{\mathrm{sp}} = \begin{bmatrix} 0 & 2 & 3 \\ 2 & 0 & 3 \\ 3 & 3 & 0 \end{bmatrix},

with rows and columns indexed by aa, bb, cc. Denote by p~\tilde{\mathbf{p}} and q~\tilde{\mathbf{q}} the three-dimensional restrictions of p\mathbf{p} and q\mathbf{q} to the leaf nodes. Note that Ei∼qSaed(p,i)=q~⊤Dspp~\mathbb{E}_{i\sim q}S_{\mathrm{aed}}(\mathbf{p},i)=\tilde{\mathbf{q}}^{\top}D_{\mathrm{sp}}\tilde{\mathbf{p}} and Ei∼qSaed(q,i)=q~⊤Dspq~\mathbb{E}_{i\sim q}S_{\mathrm{aed}}(\mathbf{q},i)=\tilde{\mathbf{q}}^{\top}D_{\mathrm{sp}}\tilde{\mathbf{q}}. A direct computation yields the difference

q~⊤Dsp(q~−p~)=q~⊤Dsp(0−2δ2δ)=2δ(13−6δ).\tilde{\mathbf{q}}^{\top}D_{\mathrm{sp}}(\tilde{\mathbf{q}}-\tilde{\mathbf{p}}) = \tilde{\mathbf{q}}^{\top}D_{\mathrm{sp}} \begin{pmatrix} 0 \\ -2\delta\\ 2\delta \end{pmatrix} = 2\delta\left(\frac{1}{3}-6\delta\right).

For δ<118\delta<\frac{1}{18} we have 13−6δ>0\frac{1}{3}-6\delta>0, so q~⊤Dsp(q~−p~)>0\tilde{\mathbf{q}}^{\top}D_{\mathrm{sp}}(\tilde{\mathbf{q}}-\tilde{\mathbf{p}})>0, giving Ei∼qSaed(p,i)<Ei∼qSaed(q,i)\mathbb{E}_{i\sim q}S_{\mathrm{aed}}(\mathbf{p},i)<\mathbb{E}_{i\sim q}S_{\mathrm{aed}}(\mathbf{q},i). Hence, the average Error distance is improper.

Proof of Proposition 5.20. We use the same tree TT and distributions p\mathbf{p}, q\mathbf{q} which depend on δ\delta as above. This time, let δ∈(0,112)\delta\in\left(0,\frac{1}{12}\right). Furthermore, we explicitly mark rr as the root node. The lowest common ancestors are then given by LCA⁡(a,b)=v\operatorname{LCA}(a,b)=v, LCA⁡(a,c)=LCA⁡(b,c)=r\operatorname{LCA}(a,c)=\operatorname{LCA}(b,c)=r, and LCA⁡(x,x)=x\operatorname{LCA}(x,x)=x for any leaf x∈V~x\in\tilde{V}. Recall that the LCA-height of two nodes is the height of their lowest common ancestor, where the height of a node uu is the length of the longest downward path from uu to any leaf in its subtree (so all leaves have height 0). In TT, the node vv has height 1 and the root rr has height 2. Given that mp=bm_{\mathbf{p}}=b and mq=cm_{\mathbf{q}}=c, we find

Ei∼qSLCA(p,i)=13⋅1+(13−δ)⋅0+(13+δ)⋅2=1+2δ\mathbb{E}_{i\sim q}S_{\mathrm{LCA}}(\mathbf{p},i) = \frac{1}{3}\cdot1+\left(\frac{1}{3}-\delta\right)\cdot0+\left(\frac{1}{3}+\delta\right)\cdot2 = 1+2\delta

and

Ei∼qSLCA(q,i)=13⋅2+(13−δ)⋅2+(13+δ)⋅0=43−2δ.\mathbb{E}_{i\sim q}S_{\mathrm{LCA}}(\mathbf{q},i) = \frac{1}{3}\cdot2+\left(\frac{1}{3}-\delta\right)\cdot2+\left(\frac{1}{3}+\delta\right)\cdot0 = \frac{4}{3}-2\delta.

Since δ<112\delta<\frac{1}{12} implies 1+2δ<43−2δ1+2\delta<\frac{4}{3}-2\delta, we have Ei∼qSLCA(p,i)<Ei∼qSLCA(q,i)\mathbb{E}_{i\sim q}S_{\mathrm{LCA}}(\mathbf{p},i)<\mathbb{E}_{i\sim q}S_{\mathrm{LCA}}(\mathbf{q},i) and thus SLCAS_{\mathrm{LCA}} is improper.

Source detection: supplementary information

This section contains supplementary information and additional results for the example presented in Section 6.

Network and observation state selection

The Karate Club network (N=34N=34) serves as the basis for this example because it sits at a convenient middle ground: large enough to produce non-trivial outbreak patterns, yet small enough that the true source distribution is computationally accessible via Monte Carlo enumeration for at least a subset of observation states.

From every node in the network, we simulate 10710^{7} SI outbreaks (3.4×1083.4\times10^{8} simulations in total) with transmission rate β=0.03\beta=0.03 and a fixed observation horizon of T=25T=25 time steps, yielding an average outbreak size of 11.5 of nodes.

From among the 2342^{34} possible observation states at time TT, we select ten states OT\mathbf{O}_{T} satisfying two criteria: (a) sufficiently many simulations resulted in OT\mathbf{O}_{T} for the true distribution q\mathbf{q} to be estimated with reasonable precision, and (b) the true distribution is neither too concentrated nor too uniform. For each selected OT\mathbf{O}_{T}, the true distribution is estimated as the empirical distribution over all simulated outbreaks that resulted in that particular state. Figure 11 shows the ten selected observed states together with their true source distributions q\mathbf{q}. The example shown in Section 6 is state #2.

Figure 11. All ten observed states together with their true source distribution. Red nodes are infected, blue nodes susceptible.

Estimators

All estimators are trained on balanced sets of simulated outbreaks with nn outbreaks per source node, n∈{10,100,1,000,10,000}n \in\{10, 100, 1{,}000, 10{,}000\} (34n34n outbreaks in total).

GNN. The GNN estimator is a variant of the best-performing graph neural network architecture identified in the benchmark study of Sterchi et al. (2026). It takes the binary infection-status vector and the graph structure as input and outputs a probability distribution over source nodes. We train separate models for training-set sizes n∈{10,100,1,000,10,000}n \in\{10, 100, 1{,}000, 10{,}000\}.

MCMF. The Monte Carlo Mean-Field (MCMF) estimator of Sterchi et al. (2023) estimates the posterior source distribution by approximating the likelihood of the observed infection state given each candidate source under a node-independence assumption, with marginal node-state probabilities estimated by Monte Carlo simulation. Here, nn refers to the number of simulations per candidate source node.

SME. The Soft-Margin Estimator (SME) of Antulov-Fantulin et al. [3] is another Monte Carlo method based on Approximate Bayesian computation (ABC) with a soft acceptance criterium, whose tolerance is determined by a parameter aa. The original paper prescribes a method to fit aa to the data. We instead evaluate the method at five fixed values a∈{0.1,0.15,0.2,0.3,0.4}a \in\{0.1, 0.15, 0.2, 0.3, 0.4\}.

Selected states and score tables

Figure 12–Figure 21 show, for each of the ten selected observed states, the network coloured by infection status alongside the empirical true-source distribution, and the full score table comparing all estimators. The observed state and models in the main text are selected to jointly illustrate several interesting features.

Figure 12. Observed state #1 − expected scores under the true distribution for all estimators (darker: worse).

Figure 21. Observed state #10 – expected scores under the true distribution for all estimators (darker: worse).

Figure 13. Observed state #2 − expected scores under the true distribution for all estimators (darker: worse).

Figure 14. Observed state #3 – expected scores under the true distribution for all estimators (darker: worse).

Figure 15. Observed state #4 – expected scores under the true distribution for all estimators (darker: worse).

Figure 16. Observed state #5 − expected scores under the true distribution for all estimators (darker: worse).

Figure 17. Observed state #6 – expected scores under the true distribution for all estimators (darker: worse).

Figure 18. Observed state #7 − expected scores under the true distribution for all estimators (darker: worse).

Figure 19. Observed state #8 – expected scores under the true distribution for all estimators (darker: worse).

Figure 20. Observed state #9 − expected scores under the true distribution for all estimators (darker: worse).

References

  1. [1]Awad Al-Mohy and Nicholas Higham. Computing the action of the matrix exponential, with an application to exponential integrators. SIAM Journal on Scientific Computing, 33(2):488–511, 2011. doi:10.1137/100788860.
  2. [2]Fabrizio Altarelli, Alfredo Braunstein, Luca Dall’Asta, Alejandro Lage-Castellanos, and Riccardo Zecchina. Bayesian inference of epidemics on networks via belief propagation. Phys. Rev. Lett., 112:118701, 2014. doi:10.1103/PhysRevLett.112.118701.DOI
  3. [3]Nino Antulov-Fantulin, Alen Lančić, Tomislav Šmuc, Hrvoje Štefančić, and Mile Šikić. Identification of patient zero in static and temporal networks: Robustness and limitations. Phys. Rev. Lett., 114:248701, 2015. doi:10.1103/PhysRevLett.114.248701.
  4. [4]Luca Bertinetto, Romain Mueller, Konstantinos Tertikas, Sina Samangooei, and Nicholas Lord. Making better mistakes: Leveraging class hierarchies with deep networks. In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 12503–12512, 2020. doi:10.1109/CVPR42600.2020.01252.
  5. [5]Mathieu Blondel, André Martins, and Vlad Niculae. Learning with fenchel-young losses. Journal of Machine Learning Research, 21(1), 2020. ISSN 1532-4435.arxiv.org/abs/1901.02324
  6. [6]Viacheslav Borovitskiy, Iskander Azangulov, Alexander Terenin, Peter Mostowsky, Marc Deisenroth, and Nicolas Durrande. Matérn gaussian processes on graphs. In Arindam Banerjee and Kenji Fukumizu (eds.), Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pp. 2593–2601. PMLR, 2021. URL https://proceedings.mlr.press/v130/borovitskiy21a.html.arxiv.org/abs/2010.15538
  7. [7]Glenn Brier. Verification of forecasts expressed in terms of probability. Monthly Weather Review, 78(1):1 – 3, 1950. doi:10.1175/1520-0493(1950)078<0001:VOFEIT>2.0.CO;2.doi.org/10.1175/1520-0493(1950)078<0001:vofeit>2.0.co;2
  8. [8]Yuzhou Cao, Lei Feng, and Bo An. Consistent hierarchical classification with a generalized metric. In Sanjoy Dasgupta, Stephan Mandt, and Yingzhen Li (eds.), Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pp. 4825–4833. PMLR, 2024.
  9. [9]Michele Coscia and Karel Devriendt. Fast node vector distance computations using laplacian solvers, 2023. URL https://arxiv.org/abs/2310.11222.
  10. [10]A. Philip Dawid, Steffen Lauritzen, and Matthew Parry. Proper local scoring rules on discrete sample spaces. The Annals of Statistics, 40(1):593 – 608, 2012. doi:10.1214/12-AOS972.DOI
  11. [11]Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pp. 248–255, 2009. doi:10.1109/CVPR.2009.5206848.DOI
  12. [12]Karel Devriendt, Samuel Martin-Gutierrez, and Renaud Lambiotte. Variance and covariance of distributions on graphs. SIAM Review, 64(2):343–359, 2022. doi:10.1137/20M1361328.DOI
  13. [13]Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale, 2021. URL https://arxiv.org/abs/2010.11929.
  14. [14]Edward Epstein. A scoring system for probability forecasts of ranked categories. Journal of Applied Meteorology and Climatology, 8(6):985 – 987, 1969. doi:10.1175/1520-0450(1969)008<0985:ASSPFP>2.0.CO;2.doi.org/10.1175/1520-0450(1969)008<0985:assfpf>2.0.co;2
  15. [15]François Fouss, Alain Pirotte, Jean-Michel Renders, and Marco Saerens. Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation. IEEE Transactions on Knowledge and Data Engineering, 19(3):355 – 369, 2007. doi:10.1109/TKDE.2007.46.
  16. [16]François Fouss, Kevin Francoisse, Luh Yen, Alain Pirotte, and Marco Saerens. An experimental investigation of kernels on graphs for collaborative recommendation and semisupervised classification. Neural Networks, 31:53–72, 2012. ISSN 0893-6080. doi:https://doi.org/10.1016/j.neunet.2012.03.001.
  17. [17]Yuan Gao, Rasmus Kyng, and Daniel Spielman. Robust and practical solution of laplacian equations by approximate elimination, 2023. URL https://arxiv.org/abs/2303.00709.
  18. [18]Tilmann Gneiting and Adrian Raftery. Strictly proper scoring rules, prediction, and estimation. Journal of the American Statistical Association, 102(477):359–378, 2007. doi:10.1198/016214506000001437.
  19. [19]Arthur Gretton, Karsten Borgwardt, Malte Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. Journal of Machine Learning Research, 13(25):723–773, 2012. URL http://jmlr.org/papers/v13/gretton12a.html.DOI
  20. [20]Eric Grimit, Tilmann Gneiting, Veronica Berrocal, and Nicholas Johnson. The continuous ranked probability score for circular variables and its application to mesoscale forecast ensemble verification. Quarterly Journal of the Royal Meteorological Society, 132(621C):2925–2942, 2006. doi:https://doi.org/10.1256/qj.05.235.
  21. [21]Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Weinberger. On calibration of modern neural networks. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 1321–1330. PMLR, 2017. URL https://proceedings.mlr.press/v70/guo17a.html.arxiv.org/abs/1706.04599
  22. [22]Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770–778, 2016. doi:10.1109/CVPR.2016.90.DOI
  23. [23]Andrew Howard, Mark Sandler, Bo Chen, Weijun Wang, Liang-Chieh Chen, Mingxing Tan, Grace Chu, Vijay Vasudevan, Yukun Zhu, Ruoming Pang, Hartwig Adam, and Quoc Le. Searching for mobilenetv3. In 2019 IEEE/CVF International Conference on Computer Vision (ICCV), pp. 1314–1324, 2019. doi:10.1109/ICCV.2019.00140.DOI
  24. [24]Aapo Hyvärinen. Estimation of non-normalized statistical models by score matching. Journal of Machine Learning Research, 6(24):695–709, 2005. URL http://jmlr.org/papers/v6/hyvarinen05a.html.
  25. [25]Aapo Hyvärinen. Some extensions of score matching. Computational Statistics & Data Analysis, 51(5):2499–2512, 2007. ISSN 0167-9473. doi:https://doi.org/10.1016/j.csda.2006.09.003.
  26. [26]Jiaojiao Jiang, Sheng Wen, Shui Yu, Yang Xiang, and Wanlei Zhou. Identifying propagation sources in networks: State-of-the-art and comparative studies. IEEE Communications Surveys & Tutorials, 19(1):465–481, 2017. doi:10.1109/COMST.2016.2615098.
  27. [27]Shyamgopal Karthik, Ameya Prabhu, Puneet K. Dokania, and Vineet Gandhi. No cost likelihood manipulation at test time for making better mistakes in deep networks, 2021. URL https://arxiv.org/abs/2104.00795.
  28. [28]David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through a social network. In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’03, pp. 137–146, New York, NY, USA, 2003. Association for Computing Machinery. ISBN 1581137370. doi:10.1145/956750.956769.
  29. [29]Svetlana Kiritchenko, Stan Matwin, and Fazel Famili. Functional annotation of genes using hierarchical text categorization. Proceedings of BioLink SIG, ISMB, 2005.
  30. [30]D. J. Klein and M. Randić. Resistance distance. Journal of Mathematical Chemistry, 12(1):81–95, 1993. ISSN 1572-8897. doi:10.1007/BF01164627.DOI
  31. [31]Aris Kosmopoulos, Ioannis Partalas, Eric Gaussier, Georgios Paliouras, and Ion Androutsopoulos. Evaluation measures for hierarchical classification: a unified view and novel approaches. Data Mining and Knowledge Discovery, 29(3):820–865, 2015. ISSN 1384-5810. doi:10.1007/s10618-014-0382-x.
  32. [32]Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer: Hierarchical vision transformer using shifted windows. In 2021 IEEE/CVF International Conference on Computer Vision (ICCV), pp. 9992–10002, 2021. doi:10.1109/ICCV48922.2021.00986.
  33. [33]Zhuang Liu, Hanzi Mao, Chao-Yuan Wu, Christoph Feichtenhofer, Trevor Darrell, and Saining Xie. A convnet for the 2020s. In 2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 11966–11976, 2022. doi:10.1109/CVPR52688.2022.01167.DOI
  34. [34]Andrey Y. Lokhov, Marc Mézard, Hiroki Ohta, and Lenka Zdeborová. Inferring the origin of an epidemic with a dynamic message-passing algorithm. Phys. Rev. E, 90:012801, 2014. doi:10.1103/PhysRevE.90.012801.

Paper details

vlnc:W_8qwkztke
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 7

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents