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- 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@. 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 be a simple graph with node set and edge set , and let . A node selection task on consists of identifying a single unknown node . A probabilistic method for such a task outputs a probability distribution over , i.e., an element in the -dimensional probability simplex
whose component denotes the estimated probability that node 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 and propagates across . Given some information about the progression of the spread at some later time, the task is to identify its origin . Many methods for this type of inverse problem are probabilistic, issuing a distribution over . 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 should take into account.
Hierarchical classification. A label taxonomy organises a set of fine-grained classes as the leaf nodes of a rooted tree , with internal nodes representing progressively coarser superclasses as we move from leaf nodes towards the root. A probabilistic classifier typically outputs a distribution over the leaf classes for a given input, which can also be viewed as a distribution by assigning zero mass to internal nodes. The true label is a single leaf . 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 and an observed true node , how should we evaluate against in a way that is both sensitive to the graph structure of and statistically well-justified? We can formalise this challenge as the problem of constructing a scoring rule 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 be a finite nonempty set of outcomes that we identify with the integers , and let denote a probability distribution over , where is the predicted probability of outcome . A scoring rule on is a function that evaluates a probabilistic prediction against an observed outcome . We adopt the convention that smaller scores indicate better predictions, although the opposite choice is also common.
Definition 3.1. A scoring rule is called proper if
for every . It is called strictly proper if equation 2 holds as a strict inequality whenever .
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 but they report , 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 coincides with the true data distribution . Beyond evaluation, proper scoring rules also provide principled loss functions for probabilistic estimation and machine learning, since minimising their empirical average encourages to match .
Canonical examples
We briefly recall three canonical examples of strictly proper scoring rules on a finite outcome space , all of which will reappear in the rest of the paper. Throughout, denotes the estimated distribution, and the observed ground truth.
The Brier score is the oldest and most classical example:
where denotes the -th standard basis vector and 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
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 has a natural ordering. The Ranked probability score (RPS) Epstein, [14] is defined as
where the inner sum is the predicted cumulative probability up to category . 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 : probability mass far away from the true category 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 becomes the node set of a graph of size . 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 be a symmetric function, called the kernel. Let denote the corresponding kernel matrix, and write for the orthogonal complement of the -dimensional vector of ones . Define the associated quadratic form by
The following definitions are well-known:
Definition 3.2. The kernel is called
positive definite (p.d.) if for every ,
negative definite (n.d.) if for every ,
conditionally positive definite (c.p.d.) if for every ,
conditionally negative definite (c.n.d.) if for every .
Moreover, 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 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 is p.d., then is n.d., and in particular c.n.d.
For a c.n.d. kernel , the corresponding kernel score is defined as
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:
This is a proper scoring rule if and only if is c.n.d., and strictly proper if and only if 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 is miscalibrated with respect to the true outcome , while the second is an entropy term quantifying the spread of independently of . 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),
The scoring rules and are strongly equivalent in that they differ only by a term that does not depend on . Strong equivalence preserves propriety. We prefer the convention because it yields the clean quadratic form
which is always non-negative: since for all and , c.n.d. of implies . Note, that if is strictly p.d., then can be seen as a special case of the squared maximum mean discrepancy [19] between and a point mass at . Moreover, in the case where is the node set of a graph (see § 5), it is a type of node vector distance [9] between and .
As it turns out, two of the scores introduced in the previous section are, in fact, kernel scores. The Brier score corresponds to , while the RPS corresponds to [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- 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 -credible set size (CSS), 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 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 [25], and proper scoring rules for top- list predictions (Resin, 2023), where the prediction consists of the 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@ (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 to be a simple graph of size , and we set , identifying the nodes with integers .
Let be the adjacency matrix of . Denote by the degree of node , and let be the degree matrix, i.e., the diagonal matrix with entries . The graph Laplacian is defined as , with eigenvalues and associated orthonormal eigenbasis , where . We write for the identity matrix and for the -th standard basis vector, defined by . It will be repeatedly useful to recall the fact that for all and .
We will sometimes refer to special graphs: denotes the complete graph on nodes, with Laplacian and non-zero eigenvalues . denotes the path graph with nodes and edges for . Moreover, denotes the cycle graph, which is the same as but with an additional edge 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 . In each case, it suffices to find a (strictly) c.n.d. kernel matrix on ; the score 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 is called positive definite (rather than just positive semi-definite) if for all , and strictly positive definite (rather than just positive definite) if the inequality is strict for . Under this convention, the graph Laplacian is p.d., and its Moore–Penrose pseudoinverse is p.d. as well: if is the eigendecomposition of , then , which has exclusively non-negative eigenvalues.
A first Laplacian score
The graph Laplacian 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 is conditionally negative definite. If the graph is connected, then is strictly c.n.d.
Proof. is positive definite, thus is trivially c.n.d. If the graph is connected, then the null space of is one-dimensional and is spanned by . Thus, any nonzero is not in the null space, and since is negative definite, this implies that .
Using equation (9) with , the corresponding score reads
By Lemma 5.1, the kernel score is a strictly proper scoring rule on any connected graph. This score rewards probability mass concentrated on neighbours of (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 . (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 . Thus, 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 , all local neighbourhoods are identical with . The incentives of the score thus transform exactly into those of the Brier score. More formally, is a generalisation of the Brier score in the following sense:
Proposition 5.2. On the complete graph , is strongly equivalent to the multi-category Brier score.
Proof. Consider the complete graph and its Laplacian . The Laplace score in its product form (equation 10) is then:
Now observe that . Hence, the score reduces to
\hfill
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 , it is defined as
where denotes the Moore-Penrose pseudoinverse of . Note that is symmetric and vanishes if and only if . Moreover, all resistance distances are non-negative. This is an immediate consequence of equation 12, because is positive definite. An alternative way to write the resistance distance is as follows:
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 denote the matrix of all pairwise resistance distances.
Lemma 5.3. If , then .
Proof. With we can write . The matrix is rank 1 with null space , from which follows that for all . \hfill
Lemma 5.4. The matrix is conditionally negative definite. If the graph is connected, then is strictly conditionally negative definite.
Proof. By Lemma 5.3, for every , we have , since is positive definite. Hence, is c.n.d. If the graph is connected, then the null space of is spanned by . Thus, every nonzero lies outside the null space, and since is positive definite, we have . Consequently, for every nonzero , proving that is strictly c.n.d. \hfill
Lemma 5.4 is a special case of a classical result: since is a p.d. kernel, it induces a Hilbert space embedding of , and the squared Euclidean distance between nodes and in this embedding space is precisely . 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 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 is the kernel score associated with :
Since , it coincides with .
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
which shows that it measures the node vector distance between and induced by the p.d. kernel ([9]). Using the notation of Devriendt et al. [12], the Resistance score can also be written as
where is the graph variance of . 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 , the Resistance score is strongly equivalent to the multi-category Brier score.
Proof. On the complete graph we find that , where we have used the property of orthonormal bases that . As a consequence, the Resistance score in the form of equation (15) reduces (up to a constant) to the Laplacian score of equation (11),
But, as was stated in Proposition 5.2, this is equivalent to the Brier score, specifically
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 equals the shortest-path distance for all nodes .
With Proposition 5.8 at our disposal, the following result is immediate:
Proposition 5.9. On the path graph , the Resistance score equals the Ranked probability score (RPS) for ordinal categories.
Proof. As noted in § 3.2, the RPS is a kernel score on the integers with associated kernel (a proof of this well-known result is supplied in Appendix § 10). Identifying these integers with the nodes of the path graph, the kernel equals the shortest-path metric on . Since is a tree, Proposition 5.8 gives , so the two kernel scores coincide: .
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 ) and the RPS (recovered on ). 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 , with the Euclidean distance replaced by the effective resistance metric. The special case when is a rooted tree is discussed in § 5.6. The different special cases of the Resistance score are summarised in Figure 1.

Figure 1. The Resistance score on a general graph specialises to the Brier score on the complete graph (Proposition 5.7), to the Ranked probability score (RPS) on the path graph (Proposition 5.9), and to a hierarchy-aware score on a rooted tree (§ 5.6). On a depth-1 tree (star graph ), 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 we have where . In the continuum limit , the Resistance score on 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:
or equivalently where . 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 contributes nothing to the Resistance score: for any ,
since . The Resistance score therefore depends on the second-order term 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 is the heat kernel or diffusion kernel (Smola & Kondor, 2003),
where the parameter controls the diffusion time.
Definition 5.10. We define the -Diffusion score by
The diffusion kernel is strictly positive definite no matter whether the underlying graph is connected or not. Therefore, is strictly c.n.d., and we have:
Proposition 5.11. The -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 and for any , the -Diffusion score is strongly equivalent to the multi-category Brier score.
Proof. On the complete graph, the diffusion kernel of equation 19 simplifies to . Recalling that and , we obtain . Observing again the fact that , it follows that .
The interesting feature of the Diffusion score is its behaviour with respect to varying , irrespective of the graph structure. It is most clearly illustrated on a disconnected graph:
Proposition 5.13. Let be a graph with connected components .
For small , the -diffusion score has the expansion
As , the -diffusion score asymptotically converges to
where is the total probability mass placed on a subset of nodes by the distribution .
Proof. 1. For small , we have the first-order Taylor expansion and thus .
Consider the eigenspace of corresponding to eigenvalue . It is -dimensional and spanned by the orthonormal basis , where for . For we thus obtain the singular value decomposition . Plugging this into equation 20 yields . From and , it follows that , which completes the proof.
The limit 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, scores well if it places the correct total mass on component rather than necessarily getting the individual node probabilities 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 unaffected. Moreover, compared to the regular Brier score, 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 . For it reduces to the Brier score, which favours concentration of exactly on node , but otherwise prefers a uniform distribution. For small but non-zero , 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 , the score increasingly favours concentration of on the connected component which contains the true node , but otherwise prefers a more uniform distribution of the probability mass between the different components. When using the diffusion score for large , 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 is an expected feature of this score.
This idea extends further to the case where is connected: for large the asymptotic expression remains approximately valid if we interpret as the main clusters of . The diffusion score for large 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 induces a natural scale-dependent clustering on the graph. In this interpretation, the number of clusters is itself dependent on : the case represents maximal granularity in which each node is its own cluster (), while in the case the entire (connected) graph becomes a single cluster (). In other words, the parameter 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 .
One detail is worth pointing out: for connected graphs, the Diffusion score as defined in equation (20) converges to zero as , since the diffusion kernel converges to which annihilates . To compensate for this decay, let and set which shifts the spectrum of the Laplacian by . We can define the -regularised -Diffusion score by
Since , the regularised score is simply . Thus, for fixed , regularisation amounts only to an overall rescaling and does not change the relative scores or their minimiser. In other words, the -regularised -Diffusion score is strongly equivalent to the original -Diffusion score. For connected graphs, a natural prior choice is , the Fiedler eigenvalue. In this case, the contribution of the slowest non-constant diffusion mode 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 by can be represented by a permutation , such that . Note that is not unique if several entries of are tied, but the choice of permutation in this case is irrelevant for the arguments that follow.
Definition 5.14. Let be a ranking of by .
The rank score is defined as
The top- error is defined as
As is the case for our graph-aware scores, smaller values indicate better performance. Alternatively, often one considers the inverse rank score or the top- hit instead. In Appendix § 11, we show the following reassuring fact:
Proposition 5.15. Both the rank score and the top- error are proper scoring rules.
By the same token, the inverse rank score and the top- 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 does not change the score as long as the ranking of the entries is preserved. A further weakness, specific to the top- 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 is uni-modal, consider its mode (i.e., the top-1 prediction) denoted by .
Definition 5.16. The Error distance is defined as
where denotes the shortest-path distance on and the diameter of .
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 , 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 -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 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.
| Score | Graph-aware | Proper | Strictly proper | Parameters |
| Rank score | — | |||
| Top- error | ||||
| Brier score | — | |||
| Log-score | — | |||
| Error distance | — | |||
| Resistance score | — | |||
| Diffusion score |
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 ; the gray shading indicates the probabilistic estimate of , 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 -Diffusion score uses the regularisation with .
Top- 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 , 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 the graph-awareness increases and the pattern in this case is not unlike that of the Resistance score. At large , 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 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 whose leaf nodes 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: is a distribution over , embedded into by assigning zero mass to internal nodes. In non-mandatory leaf-node prediction (NMLP), mass may be placed on any node of , 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 be a rooted tree. For , let denote their lowest common ancestor and the length of the longest downward path from to any leaf in its subtree (leaves have height 0). The Hierarchical error distance is
where is the mode (i.e., top-1 prediction) of .
Like the Error distance (Definition 5.16), of which it is the natural hierarchical analogue, depends on only through its mode and is therefore not a proper scoring rule:
Proposition 5.20. 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- classes. This metric is denoted distance@ in Karthik et al. [27] and reduces to for . 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@ can be improved at no cost: replacing the ranking based on maximising with the ranking based on minimising (conditional risk minimisation) reduces distance@ without retraining. By contrast, a strictly proper scoring rule such as 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
where denotes the shortest-path distance in the taxonomy tree. The first term measures the expected taxonomic distance of from the true class ; the second term is the variance of under the tree distance metric in the sense of Devrient et al. (2022).
Since for any rooted tree, where denotes the distance from the root to , substituting into equation 28 and expanding yields
(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 , 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 ), the identity holds for all nodes , so equation 29 further simplifies to
which is purely in terms of LCA heights. Given that , this is exactly twice the kernel score of equation 9 with kernel . 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 entirely. Urbani et al. (2024) generalise HXE and prove propriety. Below we extend their result to strict propriety.
For a node denote by its parent in the rooted tree, by the closed set of its ancestors (i.e., including itself), by the set of leaves in its subtree, and by the total probability mass on that subtree.
The hierarchical cross-entropy (HXE) is defined for by
where is a free parameter. At all weights equal 1 and the log-ratios telescope to , recovering the standard log-score. For , 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 plays a similar role as in the Diffusion score (§ 5.3): both interpolate between a score over independent classes (the log-score for , and the Brier score for , respectively) and a progressively more coarse-grained, hierarchy- or graph-aware score.
Urbani et al. (2024) generalise HXE to the family
with arbitrary positive weights , using log-marginals rather than log-ratios. Expanding the ratios in equation 31 shows that is a special case of equation 32 with weights for internal nodes and for the leaf . Urbani et al. (2024) prove that is proper when the weights are balanced, which means that is the same constant for all leaves . In fact, their proof readily extends to strict propriety:
Proposition 5.21. is strictly proper whenever the weights are balanced.
Proof. Let be a distribution over the leaf nodes and a more general vector. The expectation
is strictly convex in , and so is its restriction to . It is not hard to see that the gradient at has -th component , which is independent of under the balancedness condition. The gradient is therefore proportional to , which is orthogonal to . Its projection to is thus zero, which, together with strict convexity, implies that is the unique minimiser of in . But this is the same as strict propriety of .
For HXE, the weights satisfy for every leaf , independently of (the sum telescopes), so the balancedness condition holds on any tree.
Corollary 5.22. is strictly proper for every .
Both and are defined for MLP, and there is no obvious extension to NMLP. The balancedness condition cannot hold simultaneously for all nodes 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 nodes and leaves, the Resistance score in the MLP setting is strongly equivalent to the Brier score with classes, while (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.
| Score | Reference | Proper | Strictly proper | NMLP | Parameters |
| Wu–Palmer similarity | Wu & Palmer (1994) | — | |||
| Gen. tree distance loss | Cao et al. [8] | ||||
| Tree distance loss () | Ramaswamy et al. (2015) | — | |||
| distance@ | Karthik et al. [27] | ||||
| Hier. error dist. () | Russakovsky et al. (2015) | — | |||
| Urbani family | Urbani et al. (2024) | balanced | |||
| HXE () | Bertinetto et al. [4] | ||||
| Resistance score | [ours] | — |
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 , 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 requires the Moore–Penrose pseudoinverse , which costs via SVD (or with close to 3 when using fast matrix multiplication). However, recall from equation (15) the quadratic form of the Resistance score, . The key observation is that . For a connected graph, restricted to is invertible, and its inverse coincides with the restriction of . Thus, can be obtained by solving on the subspace . The Resistance score can therefore be computed as the dot product , without ever forming explicitly. Laplacian solvers (Spielman & Teng (2004)) solve such systems approximately in nearly linear time in . 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 with , compared to 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 requires forming the full matrix exponential , which costs . Since , it suffices to compute the matrix-exponential-vector product for . 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 by projecting onto a low-dimensional Krylov subspace , requiring only sparse matrix-vector products with . The cost is where is the Krylov dimension, which is chosen adaptively by the algorithm based on the spectral radius of and a target accuracy. In practice, it tends to be small relative to , although it grows with .
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 whose nodes represent individuals and whose edges 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 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 from a single unknown source node .
Suppose that we are given the vector of observed states of all nodes at time , denoted by . 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.

Figure 3. An instance of the source detection problem on the Karate Club network. (a) Infection status at time : red nodes are infected, blue nodes are susceptible. (b) True conditional source distribution , computed by ABC with zero-tolerance rejection sampling. (c)–(f) Four different probabilistic estimates of the source node . 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 . Rather, the problem can be framed as estimating the true conditional distribution over potential source nodes , where the probability is taken over the joint distribution induced by a uniformly random source node and the subsequent stochastic dynamics . Due to the inverse nature of the problem and the inherent combinatorial complexity of stochastic processes on networks, this distribution 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 at time , which are 852 in total. Figure 3b depicts the resulting distribution .
Suppose now that we have a model that issues a probabilistic estimate of the source node . 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 to the true probabilities 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 , the estimate can only be judged on the basis of the single ground-truth source using a scoring rule. Figure 4 shows how each probabilistic estimate stacks up under a range of scoring rules, averaged over all 852 realisations .
Figure 4. Comparison of scores on the four source estimators (c)–(f) against the true distribution (b), averaged over realisations . Lower is better for all scores. Colour represents performance normalised within each column (darkest: worst model). The -Diffusion score uses the regularisation with .
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- error and Error distance, which depend only on the mode or top- 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 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 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 , which should already have washed out many of the more egregious artefacts that may appear when evaluating on a single realisation . 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 , the leaf nodes 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 over , and the true label is a single leaf . 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 , 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@ 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@ 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.

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,

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-50 | Swin-Tiny | |
| Top-1 error | 0.000 | 1.000 |
| Top-5 error | 0.000 | 0.000 |
| Distance@1 | 0.000 | 1.000 |
| Distance@5 | 9.200 | 9.200 |
| Log-loss | 0.536 | 1.179 |
| HXE () | 0.048 | 0.022 |
| Brier score | 0.220 | 0.748 |
| Resistance score | 1.371 | 1.018 |
Table 7.
| ViT-S/16 | Swin-Tiny | |
| Top-1 error | 1.000 | 1.000 |
| Top-5 error | 0.000 | 0.000 |
| Distance@1 | 7.000 | 17.000 |
| Distance@5 | 6.200 | 10.600 |
| Log-loss | 4.871 | 1.752 |
| HXE () | 0.288 | 0.475 |
| Brier score | 1.568 | 0.751 |
| Resistance score | 7.515 | 6.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 , 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 , 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 . 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 and the quality of a probabilistic prediction is judged by the proximity of its mass to 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 ) 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 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 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 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 with a weighted version , set where 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 is not symmetric either, and the effective resistance formula 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 rather than 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 is straightforward: . 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 -Diffusion score is a one-parameter family of scores where the diffusion time controls the coarse-graining scale of evaluation, from node-level accuracy at to cluster-level accuracy at large . 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 . Indeed, for , the identity
holds by direct inspection. Taking and computing the expectation over gives
where is the CDF of and we used . Taking two independent copies and computing the double expectation gives
Combining the two expressions and solving for yields
which is precisely equation 9 with kernel .
Propriety of traditional scores
Proof of Proposition 5.15. Let . Assume w.l.o.g. that the nodes are ordered in such a way that , then . For the rank score, propriety is a simple consequence of the rearrangement inequality, which says that for increasing sequences and and for all permutations , the expression is smaller or equal than . Specifically, the inequality implies that , which proves propriety. Meanwhile, propriety of the top- error can be seen as follows:
Proof of Proposition 5.17. Consider the tree graph with vertex set , edge set , and leaf set . The shortest-path distances between the leaf nodes are , . Let and define distributions over ,
where entries correspond to , , , and , respectively (see Figure 10).
Figure 10. Tree with distributions and as defined in equation 33.
For we have and . Therefore,
and
Since implies , we have , so and the Error distance is improper.
Proof of Proposition 5.18. We use the same tree , leaf nodes, distributions , , and as above. The matrix of shortest-path distances between leaf nodes is
with rows and columns indexed by , , . Denote by and the three-dimensional restrictions of and to the leaf nodes. Note that and . A direct computation yields the difference
For we have , so , giving . Hence, the average Error distance is improper.
Proof of Proposition 5.20. We use the same tree and distributions , which depend on as above. This time, let . Furthermore, we explicitly mark as the root node. The lowest common ancestors are then given by , , and for any leaf . Recall that the LCA-height of two nodes is the height of their lowest common ancestor, where the height of a node is the length of the longest downward path from to any leaf in its subtree (so all leaves have height 0). In , the node has height 1 and the root has height 2. Given that and , we find
and
Since implies , we have and thus 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 () 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 SI outbreaks ( simulations in total) with transmission rate and a fixed observation horizon of time steps, yielding an average outbreak size of 11.5 of nodes.
From among the possible observation states at time , we select ten states satisfying two criteria: (a) sufficiently many simulations resulted in for the true distribution to be estimated with reasonable precision, and (b) the true distribution is neither too concentrated nor too uniform. For each selected , 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 . 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 outbreaks per source node, ( 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 .
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, 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 . The original paper prescribes a method to fit to the data. We instead evaluate the method at five fixed values .
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]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]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]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]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]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]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]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]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]Michele Coscia and Karel Devriendt. Fast node vector distance computations using laplacian solvers, 2023. URL https://arxiv.org/abs/2310.11222.
- [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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]Svetlana Kiritchenko, Stan Matwin, and Fazel Famili. Functional annotation of genes using hierarchical text categorization. Proceedings of BioLink SIG, ISMB, 2005.
- [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]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]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]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]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.
















