GNNRank: Learning Global Rankings from Pairwise Comparisons via
Directed Graph Neural Networks

Yixuan HeUnivOx,Amazon
Quan GanAmazon
David WipfAmazon
Gesine ReinertUnivOx,turing
Junchi YanSJTU
Mihai CucuringuUnivOx,turing

UnivOxDepartment of Statistics, University of Oxford, Oxford, United Kingdom
turingThe Alan Turing Institute, London, United Kingdom
AmazonAmazon, Shanghai, China
SJTUInstitute of Artificial Intelligence, Shanghai Jiaotong University, Shanghai, China

Mihai<EMAIL_ADDRESS>
Machine Learning, ICML

Recovering global rankings from pairwise comparisons is an important problem with many
applications, ranging from time synchronization to sports team ranking. Pairwise comparisons corresponding to matches in a competition can naturally be construed as edges in a directed graph (digraph), whose nodes represent competitors with an unknown rank or skill strength. However, existing methods addressing the rank estimation problem have thus far not utilized powerful neural network architectures to optimize ranking objectives. Hence, we aim to augment a certain ranking algorithm with neural networks, in particular graph neural networks (GNN) for its intrinsic connection to the problem at hand. In this paper, we introduce GNNRank, a modeling framework that is compatible with any GNN capable of learning digraph embeddings, and we devise trainable objectives to encode ranking  upsets/violations. This framework includes a ranking score estimation approach, and adds a useful inductive bias by unfolding the Fiedler vector computation of the graph constructed from a learnable similarity matrix. Experimental results on a wide range of data sets show that our methods attain competitive and often superior performance compared with existing approaches. It also shows promising transfer ability to new data based on the trained GNN.

§ INTRODUCTION

Recovering global rankings from pairwise comparisons reflecting relative latent strengths or scores is a fundamental problem in information retrieval [Schütze et al., 2008, Liu, 2011] and beyond.
When analyzing large-scale data sets, one often seeks various forms of rankings (i.e. orderings) of the data for the purpose of  identifying the most important entries, efficient computation of search & sort operations, or for extracting the main features. There is a swarm of applications employing ranking techniques ranging from
Amazon's Mechanical Turk system for crowdsourcing
[Raykar & Yu, 2011]
to the movie recommendation system provided by Netflix  [Cremonesi et al., 2010], and
modeling outcomes of football matches [Tsokos et al., 2019].

A very rich literature on ranking traces back to
[Kendall & Smith, 1940], who studied
recovering the ranking of a set of players from pairwise comparisons reflecting a total ordering. The last decades have seen a flurry of methods for ranking from pairwise comparisons, mostly based on spectral methods leveraging the eigenvectors of suitably defined matrix operators built directly from the data, which will be detailed in the related work. In particular, SerialRank [Fogel et al., 2014] shows promising ability in ranking for a set of totally ordered items without ties, by introducing a specific inductive bias from the so-called seriation problem [Atkins et al., 1998]: a Fiedler vector of a certain similarity matrix could recover true rankings given enough pairwise comparisons in the noiseless setting.The Fiedler value of a symmetric and nonnegative
matrix (or a graph) is defined to be the second smallest eigenvalue of the combinatorial Laplacian of the matrix
[Fiedler, 1973], and its corresponding eigenvector is called a Fiedler vector.
The Fiedler vector has been shown able to encode useful information of a graph, such as bi-partitions of a graph [Fiedler, 1973], seriation problem [Atkins et al., 1998], and can be employed for partitioning hypergraphs [Chen et al., 2017].

Moreover, there has been promising progress on  combinatorial optimization
in machine learning [Wang et al., 2021, Maurya et al., 2021],
especially graph neural networks (GNNs) [Zhou et al., 2020, Wu et al., 2020],
due to their potential in data exploration.
Compared with its great success in many combinatorial tasks, the capability of GNNs
in ranking tasks is still not well
developed. The few existing works are restricted
to specific settings e.g. top-$n$ personalized recommendations [Wang et al., 2021], approximating centrality measures [Maurya et al., 2021]. Another technical gap is the inability to learn a model by directly optimizing the ranking objective, which we aim to fill in our work.

We propose GNNRank, an end-to-end ranking framework compatible with existing GNN models e.g. [He et al., 2021, Tong et al., 2020] that is able to learn directed graph (digraph) node embeddings. We devise trainable objectives to encode ranking upsets/violations. Following the standard protocol in [d'Aspremont et al., 2021], an upset of an edge is a ranking violation; the inferred relative ranking is in the opposite direction to what the original measurement indicates. GNNRank consists of a family of ranking score estimation techniques, and adds an inductive bias by unfolding the Fiedler vector computation of the graph
constructed from a learnable similarity matrix.

1) To our best knowledge, this is the first neural network framework (specifically GNN) to recover global rankings from pairwise comparisons whereby a direct optimization of
the ranking objectives is enabled, without supervision.
2) For jointly solving global ranking and GNN training, we design and introduce an inductive bias as achieved by the proximal gradient steps to our neural network, as unfolded from the Fiedler vector calculation, as an effective way of encoding latent orderings.
3) Our methods empirically attain competitive, and often superior,  accuracy compared to SOTA by extensive evaluations, and its cost-effectiveness is especially pronounced when the trained GNN model is transferred to new datasets for ranking recovery. Compared to some
existing methods e.g. Minimum Violation Rank (MVR) [Ali et al., 1986] with expensive optimizations, our methods have
better asymptotic time complexity.
4) From a computational perspective, when the data may have a temporal dimension or when there are
similarities across different data sets, one can apply an already trained model to
to new data sets that are similar to the one the model has been trained on.

Anonymized codes and preprocessed data are at: <https://anonymous.4open.science/r/GNNRank>.

§ RELATED WORK

Ranking Methods
One of the most popular models in the ranking literature is the Bradley-Terry-Luce (BTL) model [Bradley & Terry, 1952], [Luce, 1959].
In its basic version, the probability that player $i$ beats player $j$ is given by $P_{ij} = \frac{w_i}{w_i + w_j}$, where the parameter vector $w \in \mathbb{R}_{+}^n$
is estimated from the
data, and $w_i$ is a proxy for the strength of player $i$.  [Firth, 2005]
facilitates the specification and fitting of Bradley-Terry logit models to pairwise comparisons.

Employing the stationary distribution of a suitably defined Markov chain for the ranking task traces its roots in early work on the topic of network centrality. Such measures have been designed to quantify the extent to which nodes of the graph (or other network structures) are most important [Newman, 2010]; see for example
[Page et al., 1998], [Bonacich, 1987], and [Negahban et al., 2017].

David's Score [David, 1987] computes rankings from proportions of wins and losses.
Minimum Violation Rank (MVR) [Ali et al., 1986] encompasses a suite of methods that aim to directly minimize certain penalty functions at the level of each upset.
In our experiments, we compare against the algorithm of  [Gupte et al., 2011], that considers a linear relaxation of an  integer program that  minimizes a so-called agony loss.
However, MVR is computationally expensive as also will be shown in our experiments.

SyncRank [Cucuringu, 2016] formulates the ranking problem with incomplete noisy pairwise information as an instance of the group synchronization problem over the group SO(2) of planar rotations  [Singer, 2011], which has attracted significant attention in recent years.
The SpringRank algorithm of [De Bacco et al., 2018]  borrows intuition from statistical physics, and proposes to infer hierarchical rankings in directed networks by solving a linear system of equations.
[d'Aspremont et al., 2021] introduces simple algorithms for ranking and synchronization based on singular value decompositions, with theoretical guarantees. SerialRank [Fogel et al., 2014]
first computes the Laplacian from a certain similarity matrix $\mathbf{S'}$. The corresponding Fiedler vector
of $\mathbf{S'}$
then serves as the final ranking estimate.
The intuition is that the more similar two players are  (in terms of the pattern of incoming/outgoing edges), the more similar their ranking should be; indeed, if two players defeat, and are defeated, by the same set of other players, then they are likely to have a similar ranking/strength. In this classical ordering problem (called seriation [Atkins et al., 1998]), one is given a similarity matrix between a set of items and assumes that the items can be ordered along a chain such that the similarity between items decreases with their distance within this chain.

Apart from the above classic learning-free optimizers for ranking problems, there also exist learning-based (mostly neural) ranking models. The early work [Scarselli et al., 2005] applies a certain form of GNN to ranking web pages, while it requires label supervision for ground-truth ranks for training. While the authors in [Damke & Hüllermeier, 2021] propose the family of so-called RankGNNs, their competitors are graphs.
[Rigutini et al., 2011] applies a neural network approach for preference learning,
[Köppel et al., 2019] generalizes
[Burges et al., 2005], but these methods require queries as input, which solve a different problem from ours.
[Maurya et al., 2021] proposes the first GNN-based model to approximate betweenness and closeness centrality, facilitating locating influential nodes in the graphs in terms of information spread and connectivity. The pairwise direction is rarely considered in these works but it
is important for the problem studied in this paper.

Directed Graph Neural Networks
Directed GNNs are useful in learning digraph node embeddings.
[Tong et al., 2020] builds aggregators based on higher-order proximity.
[Zhang et al., 2021] constructs a complex Hermitian Laplacian matrix.
[He et al., 2021] introduces imbalance objectives for digraph clustering. In GNNRank, existing digraph neural networks can be readily incorporated.

Unfolding Techiques
Algorithm unfolding [Gregor & LeCun, 2010] was first introduced to unfold the iterations as a cascade of layers while adding learnable parameters. The unfolding idea has later been applied to problems such as semantic segmentation [Liu et al., 2017] and efficient power allocation [Chowdhury et al., 2021]. The work [Yang et al., 2021] discusses a new family of GNN layers designed to mimic and integrate the update rules of classical iterative algorithms. The unfolding idea inspires us to add a useful inductive bias from the calculation of the Fiedler vector. Most importantly, unfolding allows us to pass gradients through the optimization of a useful function.

Overview of GNNRank based on directed graph neural networks and the proximal gradient steps corresponding to Algo. <ref>: starting from an adjacency matrix $\mathbf{A}$ which encodes pairwise comparisons, input feature matrix $\mathbf{X}$ and embedding dimension $d,$ GNNRank first applies a directed graph neural network model to learn node embeddings $\mathbf{Z}$ for each competitor (node). Then it calculates the inner product or the similarity score with respect to a learnable vector to produce non-proximal outcomes for ranking scores (“innerproduct" or “dist"). Proximal  variants start from a similarity matrix constructed from the learnable embeddings $\mathbf{Z}$, then utilize proximal gradient steps to output ranking scores. Depending on the initial guess score vector $\mathbf{r}'$, the proximal variants have names “proximal innerproduct", “proximal dist" or “proximal baseline". Ordering the scores in the score vector $\mathbf{r}$ induces the final ranking/ordering vector $\mathbf{R}\in\mathbb{R}^n.$ The loss function is applied to a variant's output score vector $\mathbf{r}$, given the  input adjacency matrix $\mathbf{A},$ while the final evaluation is based on $\mathbf{R}$ and $\mathbf{A}.$ Red frames indicate trainable tensors/vectors/matrices. Grey squares correspond to fixed inputs.

§ APPROACH

§.§ Problem Definition

Without loss of generality, we consider pairwise comparisons in a competition, which can be encoded in a directed graph (digraph) $\mathcal{G}=(\mathcal{V}, \mathcal{E})$, where the node set $\mathcal{V}$ denotes competitors, and the edge set $\mathcal{E}$ represents pairwise comparisons. The outcomes of the matches can be captured by the adjacency matrix $\mathbf{A}$.
A single edge $e\in\mathcal{E}$ from node $v_i$ to node $v_j$, with edge weight $\mathbf{A}_{i,j}\geq 0$ that is not reciprocal, denotes that node $v_i$ is better than node $v_j$ by $\mathbf{A}_{i,j}$. For a reciprocal edge, $\mathbf{A}_{i,j}$ and $\mathbf{A}_{j,i}$ could be different, and they could denote the (sum of) match scores for both competitors in matches between them, or the sum of absolute wins across different matches between them, where $\mathbf{A}_{i,j}$ is the sum of absolute wins for $v_i.$

Recovering global rankings from pairwise comparisons amounts to assigning an integer $R_i$ to each node $v_i\in\mathcal{V}$, denoting its position among competitors, where the lower the rank, the better the node is. To this end, many existing methods (including our proposed methods) first learn a real-valued ranking score $r_i$ for $v_i$, where the higher the score, the better/stronger the node is. The scores are then ordered to provide the final integer ranking.

§.§ Motivation and Connection to SerialRank

The whole GNNRank framework is described in Algo. <ref>, using steps from Algo. <ref>, and a diagram is provided in Fig. <ref>. Details will be provided later in this section.

Indeed, we highlight an intrinsic connection to SerialRank [Fogel et al., 2014], which operates by  first computing the Laplacian from a certain similarity matrix $\mathbf{S}'=\frac{1}{2}(n\mathbf{1}\mathbf{1}^\top + \mathbf{C}\mathbf{C}^\top)$, where $\mathbf{C}$ is the binary comparison matrix with $\mathbf{C}_{i,j}=\text{sign}(\mathbf{A}_{i,j}-\mathbf{A}_{j,i})$, with  $\mathbf{A}$ the
digraph adjacency matrix. The corresponding Fiedler vector of $\mathbf{S}'$
then serves as the final ranking estimate, after a global sign reconciliation. While often effective in practice, SerialRank is heavily dependent on the quality of the underlying similarity matrix $\mathbf{S}'$.

To address this issue, we introduce a parameterized GNN model that allows us to compute trainable measures of similarity that are useful for subsequent ranking. However, for training purposes, we of course need to somehow back-propagate gradients through the computation of a Fiedler vector to update the GNN parameters.  Because it is generally difficult to directly pass gradients through eigenvector computations, we instead express the Fiedler vector as the solution of a constrained optimization problem.  We then approximate the solution of this problem using proximal gradient steps, each of which are themselves differentiable with respect to the underlying optimization variables, and ultimately by the chain rule, the GNN parameters. Note that Algo. <ref> can be viewed as a differentiable function that inputs $\mathbf{r}'$ and $\mathbf{L}$, and outputs $\mathbf{r}$.  Therefore, the gradients can backpropagate through Algo. <ref> into
$\mathbf{L}$ and $\mathbf{r}'$, hence the similarity matrix $\mathbf{S}$ and the rest of the model parameters.

In broader contexts, this process is sometimes referred to as unfolded optimization  [Gregor & LeCun, 2010], and is applicable in situations whereby a high-level loss function (in our case a ranking loss) is defined with respect to the minimization of some lower-level, parameter-dependent optimization problem (e.g., Fiedler vector computation) that has been unfolded across differentiable iterations/updates. Within our proposed framework, this process allows to combine the inductive bias of Fiedler-vector-based rankings with the flexibility of GNNs for modeling relations between entities.Also, SerialRank can be viewed as a special case of GNNRank;
$\mathbf{S}'_{i,j}$ counts the number of competitors that beat both $v_i$ and $v_j,$ plus that of competitors beaten by both $v_i$ and $v_j$, minus that of competitors beating one of $v_i$ and $v_j$ but
beaten by the other, plus half the number of nodes.
Information from common
neighbors could be aggregated by directed GNNs, and a
kernel such as a Gaussian RBF kernel applied to the digraph embeddings could approximate $\mathbf{S}'$.

§.§ Loss Functions and Objectives

Define the skew-symmetric
matrix $\mathbf{M'} = \mathbf{A} - \mathbf{A}^\top$ and a vector $\mathbf{r}=[r_1, \dots,r_n]^\top$ with real-valued ranking scores as entries. Let $t$ be the number of nonzero elements in $\mathbf{M'}$.
The upset loss is defined as the portion of relationships disagreeing with their expected relationships, in the spirit of [d'Aspremont et al., 2021]. Formally, let $\mathbf{1}$
be an all-one column vector, and define the matrix $\mathbf{T'}=\mathbf{r1}^\top-\mathbf{1r}^\top\in\mathbb{R}^{n\times n}.$ Then we have $\mathbf{T'}_{i,j} = r_i-r_j, \forall i,j\in\{1,\cdots,n\}$. To not penalize entries where the initial pairwise rankings are not available,
we only compare $\mathbf{T'}$ with $\mathbf{M'}$ at locations where $\mathbf{M'}$ has nonzero entries. A naive upset loss is
defined as

\begin{equation}
\vspace{-1mm}
\mathcal{L}_\text{upset, naive} =
{\sum_{i,j:\mathbf{M'}_{i,j}\neq 0}(\text{sign}(\mathbf{T'}_{i,j})\neq \text{sign}(\mathbf{M'}_{i,j}))}/t.
\label{eq:loss_upset_naive}
\end{equation}

Being piecewise constant,
$\mathcal{L}_\text{upset, naive}$ is not useful in gradient descent. Thus, we define $\mathbf{M} = \frac{\mathbf{A} - \mathbf{A}^\top}{\mathbf{A} + \mathbf{A}^\top},$ and $\mathbf{T}=\frac{\mathbf{r1}^\top-\mathbf{1r}^\top}{\mathbf{r1}^\top+\mathbf{1r}^\top}\in\mathbb{R}^{n\times n}.$ Then $\mathbf{T}_{i,j} = \frac{r_i-r_j}{r_i+r_j}, \forall i,j\in\{1,\cdots,n\}.$
Similarly, we only compare $\mathbf{T}$ with $\mathbf{M}$ at locations where $\mathbf{M}$ has nonzero entries.

With $\Tilde{\mathbf{T}}$ where $\Tilde{\mathbf{T}}_{i,j}=\mathbf{T}_{i,j}$ if $\mathbf{M}_{i,j}\neq 0$ and $\Tilde{\mathbf{T}}_{i,j}=0$ if $\mathbf{M}_{i,j}= 0$, the differentiable upset loss is then defined as

\begin{equation}
\vspace{-1.5mm}
\mathcal{L}_\text{upset, ratio} =
\left\lVert \Tilde{\mathbf{T}}-\mathbf{M} \right\rVert^2_F/t(\mathbf{M}),
\label{eq:loss_upset}
\end{equation}

where subscript $F$ means Frobenius norm,
and $t(\mathbf{M})$ is the number of nonzero elements in $\mathbf{M}.$

Note that $\mathcal{L}_\text{upset, ratio}$ requires $r_i\geq 0$ for each $r_i$ to represent the skill level. Hence we use transformations e.g. $r_i \leftarrow \text{sigmoid}(r_i)$ for general $r_i\in\mathbb{R}$,  and $r_i \leftarrow \frac{r_i+1}{2}$ when we know $r_i\geq -1,$ e.g. when the score  $\mathbf{r}=(r_i)$ has unit norm.

Another choice is the margin loss $\mathcal{L}_\text{upset, margin}$, with a tunable nonnegative parameter $\epsilon\geq 0$ (default 0.01), defined as

\begin{equation}
\mathcal{L}_\text{upset, margin} = \sum_{i, j}(\mathbf{M}_{i,j}+|\mathbf{M}_{i,j}|)\cdot \text{ReLU}(r_j - r_i + \epsilon)/t(\mathbf{M}), \label{eq:loss_margin}
\end{equation}

ReLU is the Rectified Linear Unit.

The training loss used is either $\mathcal{L}_\text{upset, ratio}$, $\mathcal{L}_\text{upset, margin}$ or $\mathcal{L}_\text{upset, ratio} + \mathcal{L}_\text{upset, ratio},$ the choice is set as a hyperparameter.

Evaluation.For evaluation, in addition to $\mathcal{L}_\text{upset, naive}$, we introduce another objective similar to $\mathcal{L}_\text{upset, naive}$ but penalizing predicted signs opposite to the actual signs more than predicted signs being zero, i.e. we distinguish predictions as ties or being opposite signs, which can also take integer rankings as input

\begin{equation}
\mathcal{L}_\text{upset, simple} =
\left\lVert \text{sign}(\mathbf{T'})- \text{sign}(\mathbf{M'})) \right\rVert^2_F/t,
\label{eq:loss_upset_simple}
\end{equation}

where the sign function acts element-wise,
and $t$ is the number of nonzero elements in $\mathbf{M}'.$ However, although $\mathcal{L}_\text{upset, simple}$ distinguishes ties and opposite signs, this loss has a trivial solution of 1 by assigning the same score to all nodes, which means that whenever we achieve a value larger than 1, the model performs even worse than random guess, or it is not able to detect ties.

When ground-truth rankings are available, we use the Kendall tau [Brandenburg et al., 2013] values for evaluation, and select the model based on the lowest $\mathcal{L}_\text{upset, simple}$.

§.§ Obtaining Directed Graph Embeddings

For obtaining a directed graph embedding, any GNN method able to take into account directionality and output node embeddings could be applied, e.g. DIMPA by [He et al., 2021], the inception block model (IB) [Tong et al., 2020], and MagNet [Zhang et al., 2021]. In our experiments, we employ DIMPA and IB, to aid in the ranking task.
Denoting the final node embedding $\mathbf{Z}\in \mathbb{R}^{n \times d}$, the embedding vector $\mathbf{z}_i$ for a node $v_i$ is $\mathbf{z}_i:=(\mathbf{Z})_{(i,:)} \in \mathbb{R}^{d}, $ the $i^\text{th}$ row of $\mathbf{Z}$.

§.§ Obtaining Final Scores and Rankings

To obtain the final ranking score, we unfold the calculation of a Fiedler vector for the graph
constructed from our symmetric similarity matrix $\mathbf{S}$ with proximal gradient steps.

Obtaining the similarity matrix.From the high-dimensional embedding matrix $\mathbf{Z},$ we calculate the symmetric similarity matrix $\mathbf{S}$ with $\mathbf{S}_{i,j}=\exp(-|\mathbf{z}_j-\mathbf{z}_i|_2^2/(\sigma^2d))$
where $\sigma\in\mathbb{R}$ is the same trainable parameter as in “dist".

Denote by $\mathbf{D}$ the diagonal matrix with $\mathbf{D}_{i,i}=\sum_j\mathbf{S}_{i,j}$.
We consider the unnormalized Laplacian $\mathbf{L = D - S}$, and apply proximal gradient to approximate a Fiedler vector of $\mathbf{S}$,
which then serves as $\mathbf{r}$.

Transformation of the Optimization Problem.Computing a Fiedler vector of the similarity matrix $\mathbf{S}$
is equivalent to solving the optimization problem

\begin{align}
\label{eq:problem_original}
\min_\mathbf{r} \mathbf{r}^\top \mathbf{L} \mathbf{r}
\text{ s.t.} &\quad \left\lVert \mathbf{r} \right\rVert_2^2 = 1, \quad \mathbf{r}^\top \mathbf{1} = 0,
\end{align}

where $\mathbf{L}$ is the graph Laplacian matrix.
The constraints describe an intersection of a unit sphere and a hyperplane.  By rotating the problem and the constraints so that the hyperplane becomes cardinal, we can effectively fix one dimension to zero and solve

\begin{equation}
\min_\mathbf{y} \mathbf{y}^\top
\mathbf{Q} \mathbf{L} \mathbf{Q}^\top
\mathbf{y}
\text{ s.t.} \quad \left\lVert \mathbf{y} \right\rVert_2^2 = 1.
\end{equation}

Here $\mathbf{Q}$ is an orthogonal matrix.
We choose a
$\mathbf{Q}$ such that $\mathbf{Q} \mathbf{1} = \sqrt{n} \mathbf{e}_1$, where $\mathbf{e}_1 = \begin{bmatrix} 1 & 0 & \cdots & 0 \end{bmatrix}^\top$.
Let $\mathbf{y} = \mathbf{Q} \mathbf{r}$, and thus $\mathbf{r} = \mathbf{Q}^\top \mathbf{y}$. The problem  becomes

\begin{align*}
&\min_\mathbf{y} \mathbf{y}^\top \mathbf{Q} \mathbf{L} \mathbf{Q}^\top \mathbf{y} \\
\text{s.t.} &\quad
\left\lVert \mathbf{r} \right\rVert_2^2=1
\qquad  \mathbf{r}^\top \mathbf{1}
= \sqrt{n} \mathbf{y}^\top \mathbf{e}_1 = \sqrt{n} y_1 = 0.
\end{align*}

Since we fix $y_1 = 0$, this is equivalent to

\begin{align}
\label{eq:problem_reduced}
&\min_{\mathbf{y}' \in \mathbb{R}^{n-1}} \mathbf{y}'^\top \left[ \mathbf{Q} \mathbf{L} \mathbf{Q}^\top\right]_{2:n,2:n} \mathbf{y}' \quad
\text{s.t.} \quad \left\lVert \mathbf{y}' \right\rVert_2^2 = 1,
\end{align}

where $\left[\cdot\right]_{2:n,2:n}$ represents the matrix with its first row and first column removed. We provide discussion to better understand the above equivalence. Since the constraint $\mathbf{r}^\top \mathbf{1}=0$ is equivalent to $y_1=0,$ we need to ensure that $y_1=0$ is maintained throughout. If we start with $\mathbf{y}\in\mathbb{R}^n$ where $y_1=0,$ and let $\mathbf{y}'=[y_2, \dots,y_n]^\top \in \mathbb{R}^{n-1}$ then
\begin{align*}
&\mathbf{y}^\top \left[ \mathbf{Q} \mathbf{L} \mathbf{Q}^\top\right]_{1:n,1:n} \mathbf{y}=\sum_{1\leq i \leq n, 1\leq j \leq n}\left[ \mathbf{Q} \mathbf{L} \mathbf{Q}^\top\right]_{i,j}y_iy_j \\ = & \sum_{2\leq i \leq n, 2\leq j \leq n}\left[ \mathbf{Q} \mathbf{L} \mathbf{Q}^\top\right]_{i,j}y_iy_j
= \mathbf{y}'^\top \left[ \mathbf{Q} \mathbf{L} \mathbf{Q}^\top\right]_{2:n,2:n} \mathbf{y}'.
\end{align*}

One possible $\mathbf{Q}$, with details of construction in Supplementary Information (SI) C, is
the following upper Hessenberg matrix,
can be efficiently precomputed

\begin{equation*}
\mathbf{Q}_{ij} = \begin{cases}
\sqrt{\frac{1}{n}} & i=1 \\
-\sqrt{\frac{n-i+1}{n-i+2}} & i\geq 2, j=i-1 \\
\sqrt{\frac{1}{(n-i+1)(n-i+2)}} & i\geq 2, j\geq i \\
0 & \text{otherwise.}
\end{cases}
\end{equation*}

Proximal Gradient Steps.
To enforce a zero in the first entry of the initial guess, we
zero-center the input score vector, then left multiply it by $\mathbf{Q}$, so this resulting vector has 0 in its first entry. We then remove the first entry of the resulting vector, and discard the first row and first column for the matrix $\mathbf{Q L Q^\top}$. The gradient of the objective $\mathbf{y^\top}\widetilde{\mathbf{L}}\mathbf{y}$ with respect to $\mathbf{y}$ is $(\widetilde{\mathbf{L}} + \widetilde{\mathbf{L}}^\top)\mathbf{y}=2\widetilde{\mathbf{L}}\mathbf{y}$ since $\widetilde{\mathbf{L}}$ is symmetric. We set the
number of proximal steps as $\Gamma=5,$ and initial learning rates inside proximal gradient steps $\alpha_\gamma = 1, \gamma=1, \ldots, \Gamma$.
Define the spherical projection operation $\mathcal{P}_{\mathcal{S}^{n-1}}(\cdot):\mathbb{R}^n\rightarrow\mathbb{R}^n$ by $\mathcal{P}_{\mathcal{S}^{n-1}}(\mathbf{x})=\frac{\mathbf{x}}{\left\lVert \mathbf{x} \right\rVert_2}$ if $\mathbf{x}\neq \mathbf{0}$ and $\mathcal{P}_{\mathcal{S}^{n-1}}(\mathbf{0})=\mathbf{e}_1,$ where $\mathbf{0}=[0,\dots,0]^\top.$ Algo. <ref> details the proximal gradient steps, which guarantees descent of the optimization objective in (<ref>) given suitable $\alpha$'s [Parikh & Boyd, 2014].

Proximal Gradient Steps

Input: Initial score $\mathbf{r'}\in\mathbb{R}^n$, Laplacian $\mathbf{L}\in\mathbb{R}^{n\times n}$ and $\mathbf{Q}\in\mathbb{R}^{n\times n}$

Parameter: (Initial) learning rate set $\{\alpha_\gamma>0\}_{\gamma=1}^\Gamma$ that could either be fixed or trainable (default: trainable).

Output: Updated score vector $\mathbf{r}=[r_1, \dots, r_n]^\top$.

[1]
Let $\mathbf{y}= \mathbf{r'} - \sum_{i=1}^n r'_i/n$;
$\mathbf{y} \leftarrow \mathbf{Q}'\mathbf{y} \in \mathbb{R}^{n-1}$ ($\mathbf{Q}'$ is $\mathbf{Q}$ with the first row removed);
$\mathbf{y} \leftarrow \mathcal{P}_{\mathcal{S}^{n-1}}(\mathbf{y})$ to have unit 2-norm;
$ \widetilde{\mathbf{L}} \leftarrow \left[\mathbf{Q L Q}^\top\right]_{2:n,2:n}.$
$\gamma < \Gamma$
$\mathbf{y} \leftarrow \mathbf{y} - \alpha_\gamma (2\widetilde{\mathbf{L}})\mathbf{y}/n$;
$\mathbf{y} \leftarrow \mathcal{P}_{\mathcal{S}^{n-2}}(\mathbf{y})$ to have unit 2-norm;
$\gamma \leftarrow  \gamma + 1.$
$\mathbf{y} \leftarrow \text{CONCAT}(0, \mathbf{y})\in\mathbb{R}^n$;
$\mathbf{r} = \mathbf{Q}^\top \mathbf{y}$
return $\mathbf{r}$;

GNNRank: Proposed Ranking Framework

Input: Digraph adjacency matrix $\mathbf{A}\in\mathbb{R}^{n\times n}$, node feature matrix $\mathbf{X}$, variant name $var$, (optional) initial guess from baseline $\mathbf{r'}$.

Parameter: Learnable vector $\mathbf{a}\in\mathbb{R}^n, b\in\mathbb{R}, \sigma\in\mathbb{R}$, GNN parameters, parameters from Algo. <ref>.

Output: Score vector $\mathbf{r}$.
[1]
$\mathbf{Z}\in\mathbb{R}^{n\times d} = \text{GNN}(\mathbf{A},\mathbf{X})$;
$var\in${“dist", “proximal dist"}
Compute $\mathbf{r}: r_i = \exp(-|\mathbf{a}-\mathbf{z}_i|_2^2/(\sigma^2d))$;
$var\in${“innerproduct", “proximal innerproduct"}
Compute $\mathbf{r}: r_i = \text{sigmoid}(z_i\cdot \mathbf{a}+b)$;
$var\in${“proximal dist", “proximal innerproduct",  “proximal baseline"}
Compute $\mathbf{S}:\mathbf{S}_{i,j}=\exp(-|\mathbf{z}_j-\mathbf{z}_i|_2^2/(\sigma^2d))$;
Compute Laplacian $\mathbf{L}$ and $\mathbf{Q}$ by Sec. <ref>;
$var==${“proximal baseline"}
$\mathbf{r} =\mathbf{r'}$;
$\mathbf{r}\leftarrow \text{Proximal Gradient Steps} (\mathbf{r}, \mathbf{L}, \mathbf{Q})$ from Algo. <ref>;
return $\mathbf{r}$;

§.§ Initialization and Pretraining Considerations

Algo. <ref> requires an initial guess $\mathbf{r'}\in\mathbb{R}^n$.
To achieve this, we introduce two non-proximal variants, whose output score vector could serve as $\mathbf{r'}$. These non-proximal variants are also evaluated in our experiments.

(1) “innerproduct" variant: With a trainable vector $\mathbf{a}$ that has its dimension equal to the embedding dimension, we obtain the scores by the inner product of $\mathbf{z}_i$  with  $\mathbf{a}$, plus a trainable  bias $b$, followed by a sigmoid layer to force positive score values: $r_i = \text{sigmoid}(\mathbf{z}_i \cdot \mathbf{a} + b).$

(2) “dist" variant: $r_i = \exp(-|\mathbf{a}-\mathbf{z}_i|_2^2/(\sigma^2d))$ where $\mathbf{a}\in\mathbb{R}^{d}, \sigma\in\mathbb{R}$ are trainable parameters. This variant applies a trainable Gaussian RBF kernel to describe the scores.

For each non-proximal variant, the corresponding proximal variant
is called (3) “proximal dist" or (4) “proximal innerproduct". We can also adopt the initial guess from a certain existing baseline's output, with variant name (5) “proximal baseline".

For a reasonable similarity matrix to start with, we apply some pretraining. One option is to train the ranking model with a non-proximal variant, “dist" or “innerproduct", for the early training epochs.
As the proximal variants are inspired by unfolding the Fiedler vector calculation introduced in SerialRank [Fogel et al., 2014], another option is to add a term to the loss function in early training epochs that compares the similarity matrix constructed by $\mathbf{Z}$ using a GNN with the normalized version (divided by the max entry so that the maximum is 1) of $\mathbf{S'}$, the similarity matrix from SerialRank.
The corresponding additional term added to the loss function $\mathcal{L}_\text{upset, ratio}$ from Eq. (<ref>) or $\mathcal{L}_\text{upset, margin}$ from Eq. (<ref>), or their sum,
is $\mathcal{L}_\text{similarity} = n^{-2}  {\left\lVert \mathbf{S}-\mathbf{S'}/\max(\{\mathbf{S'}_{i,j}\})\right\rVert^2_F}.$

§.§ Convergence Analysis

An analysis of the convergence of our proximal gradient steps is provided in Appendix <ref>, along with additional theoretical and practical considerations. We summarize our main result below; the proof is available in  Appendix <ref>.

Let $\{\alpha_\gamma>0\}_{\gamma=1}^\Gamma$ in Algo. <ref> be fixed (equal to $\alpha$) and let $\rho$ be the Fiedler eigenvalue of $\mathbf{S}$.  Denote a Fiedler eigenvector by $\mathbf{r}^*$. Assume that $\mathbf{r}^*$ is a strict local minimizer of problem (<ref>).
then with our definition of the similarity matrix,  Algo. <ref> converges locally uniformly to $\mathbf{r}^*$.

§ EXPERIMENTS

Implementation details are provided in Appendix <ref>.
Experiments were conducted on a compute node with 8 Nvidia Tesla T4, 96 Intel Xeon Platinum 8259CL CPUs @ 2.50GHz and $378$GB RAM.

§.§ Data sets and Protocol

Real-World Data.
We consider 10 real-world data sets (78 digraphs constructed in total). Digraphs based on pairwise comparisons are constructed as follows in most cases: for each match, at most one edge is added, with the edge  weight as the difference between scores (absolute wins), with ties treated the same as no match between the pair of players.

When raw data with individual match scores on both competitors are available, we in addition construct a “finer" version as follows: for each match, we have a reciprocal edge with potentially different weights on the two
directions. If there are multiple matches, weights are added. To distinguish zero (a tie) from
no game, for our methods, we add
a small value (here 0.1) to every existing edge.

Real-world data sets, detailed in Appendix <ref>, include

(1) NCAA College Basketball[<https://www.ncaa.com/sports/basketball-men/d1>] (Basketball and Basketball finer) includes outcomes of
matches from seasons 1985-2014.
We construct two separate digraphs for each season,
a regular version and a “finer" version introduced in the last paragraph.
(2) England Football Premier League[<https://www.premierleague.com/>] (Football and Football finer) contains
match results for six seasons, from 2009 to 2014, between 20 teams. As in NCAA College Basketball, we construct two separate digraphs for each season.
Animal Dominance Network (Animal) [Hobson & DeDeo, 2015] describes the number of net aggressive wins of 21 captive monk parakeets.
Microsoft Halo 2 Tournament on Head-to-Head Games (HeadToHead) collects game outcomes during the Beta testing period for the Xbox game Halo 2[Credits for using the Halo 2 Beta data set are given to Microsoft Research Ltd. and Bungie.].
Faculty Hiring Networks (Faculty: Business, Faculty: CS and Faculty: History) [Clauset et al., 2015] contains three North American academic hiring networks tracking the flow of academics between universities.
Lead-Lag Relationships on Stocks (Finance) [Bennett et al., 2021] contains lead-lag relationships on 1315 stocks from 2001-2019. An edge $(i,j)$ in the digraph encodes the $t$-value of the coefficient in the regression of the daily returns of stock $i$ on the  lag-1 (previous day) returns of stock $j$.

Table <ref> gives the number of nodes ($n$), the number of directed edges ($|\mathcal{E}|$), the number of reciprocal edges ($|\mathcal{E}^r|$) (self-loops are counted once and for $ u \ne v$, a reciprocal edge $u\rightarrow v, v\rightarrow u$ is counted twice) and their percentage among all edges, for the real-world networks, illustrating the variability in network size and density (defined as ${|\mathcal{E}|}/[{n(n-1)}]$).
When input features are unavailable, we stack the real and imaginary parts of the top $K$ eigenvectors of $(\mathbf{A}-\mathbf{A}^\top)\cdot i$ in line with the protocol in [Cucuringu et al., 2020] for GNNs.
We report the embedding dimension $d$.

Summary statistics
for the real-world networks.

Data                   $n$      $|\mathcal{E}|$   density   $|\mathcal{E}^r|$   $\frac{|\mathcal{E}^r|}{|\mathcal{E}|}$(%)   $K$   $d$
HeadToHead   602   5010   1.38e-02   464   9.26   48   32

Finance   1315   1729225   1.00e+00   1729225   100   20   64

Animal   21   193   4.60e-01   64   33.16   3   8

Faculty:Business   113   1787   1.41e-01   0   0.00   5   16

Faculty:CS   206   1407   3.33e-02   0   0.00   9   16

Faculty:History   145   1204   5.77e-02   0   0.00   12   16

Football(avg)   20   201   5.29e-01   71   32.17   9   8

Basketball(avg)   316   3506   3.51e-02   986   28.57   20   16

Football finer (avg)   20   367   9.65e-01   367   100   9   8

Basketball finer (avg)   316   6139   6.12e-02   6139   100   20   16

Synthetic Data
We perform experiments on graphs with $n=350$ nodes for Erdős-Rényi Outlier (ERO) models
as in [d'Aspremont et al., 2021], with edge density $p\in\{0.05, 1\}$, noise level  $\eta\in\{0,0.1,\dots,0.8\}$ (corresponding to $\gamma$ in [d'Aspremont et al., 2021]) and style “uniform" or “gamma" depending on the distribution from which the ground-truth scores are generated. We fix $K=5, d=16$ for the ERO.

§.§ Main Experimental Results

In our numerical experiments, we compare against 11 baselines, where results are averaged over 10 runs: Eigenvector Centrality (Eig.Cent.) [Bonacich, 1987], PageRank [Page et al., 1998], Rank Centrality (RankCent.) [Negahban et al., 2017], Minimum Violation Rank (MVR) [Ali et al., 1986], SerialRank [Fogel et al., 2014], SyncRank [Cucuringu, 2016], SVD_NRS and SVD_RS by [d'Aspremont et al., 2021], Bradley-Terry-Luce (BTL) model [Firth, 2005], David's Score (DavidScore) [David, 1987], and SpringRank [De Bacco et al., 2018]. Models are selected based on the lowest $\mathcal{L}_\text{upset, simple}$ obtained without label supervision, where non-proximal results (for “dist" and “innerproduct" variants) are listed in the “GNNRank-N" column and proximal methods (for “proximal dist", “proximal innerproduct" and “proximal baseline" variants) listed with “GNNRank-P", in all tables. We report the best-performing variant for each data set within GNNRank-N and GNNRank-P, respectively.
Performance with respect to each of the GNNRank variants, for each individual input digraph, and on different objectives, are given in Appendix <ref>.
Table <ref> compares our two groups of methods
against baselines on 10 real-world data sets, where basketball data sets are averaged over 30 seasons, and football ones are averaged over 6 seasons.
Our best-performing variant of the  proximal method also outperforms  its inspiration
SerialRank [Fogel et al., 2014] on all real-world data sets by including more trainable parameters. Our
proximal method achieves state-of-the-art performance when using a typically good baseline, such as SyncRank, as an initial guess to the score vector before applying proximal gradient steps.

Table <ref> shows
Kendall tau
selected from the lowest
$\mathcal{L}_\text{upset, naive}$ on synthetic models. For some dense digraphs, SerialRank (which motivated our proximal gradient steps) attains leading performance, while for some other cases it fails. GNNRank-P outperforms across all synthetic models shown here. Full results are in Appendix <ref>.

We tend to conclude that both non-proximal and proximal methods can achieve leading performance on real-world data sets, while on the synthetic models listed here, the best method in GNNRank-P performs much better than that in GNNRank-N. Performance results for
each of the variants are provided in Appendix <ref>;
we conclude that the individual variants also attain comparable and often superior performance compared to the  baselines.We observe across all data sets that our proximal methods:
can improve on existing baseline methods when using them as initial guesses, and never perform significantly worse than the corresponding baseline, hence they can be used to enhance existing methods;
(2) do not rely on baseline methods for an initial guess  but can instead use GNNRank-N outcomes, such as “proximal dist" and “proximal innerproduct”;
(3) can outperform SerialRank by unfolding its Fiedler vector calculations with a trainable similarity matrix and proximal gradient steps.

Performance on $\mathcal{L}_\text{upset, simple}$ (top half) and $\mathcal{L}_\text{upset, naive}$ (bottom half), averaged over 10 runs with one standard deviation. “avg" for time series first average over all seasons, then consider mean and standard deviation over the 10 averaged values. The best is marked in bold red while the second best is in underline blue. When MVR does not generate results after one week, we fill in “NAN".

Data      SpringRank     SyncRank     SerialRank     BTL     DavidScore     Eig.Cent.     PageRank     RankCent.     SVD_RS     SVD_NRS    MVR       GNNRank-N     GNNRank-P

HeadToHead     1.00$\pm$0.00     1.94$\pm$0.00     2.01$\pm$0.00     1.12$\pm$0.01     1.16$\pm$0.00     1.47$\pm$0.00     1.36$\pm$0.00     2.00$\pm$0.02     1.79$\pm$0.00     1.42$\pm$0.00     nan$\pm$nan     0.99$\pm$0.00     0.96$\pm$0.00

Finance     1.63$\pm$0.00     1.98$\pm$0.00     1.61$\pm$0.00     1.78$\pm$0.01     1.63$\pm$0.00     1.74$\pm$0.00     1.75$\pm$0.00     1.88$\pm$0.00     1.64$\pm$0.00     1.64$\pm$0.00     nan$\pm$nan     1.00$\pm$0.00     1.00$\pm$0.00

Animal     0.50$\pm$0.00     1.62$\pm$0.24     1.98$\pm$0.48     0.45$\pm$0.00     0.33$\pm$0.00     0.55$\pm$0.00     0.63$\pm$0.00     1.96$\pm$0.00     1.03$\pm$0.00     0.53$\pm$0.00     2.02$\pm$0.32     0.41$\pm$0.09     0.25$\pm$0.00

Faculty: Business     0.41$\pm$0.00     0.83$\pm$0.00     1.19$\pm$0.00     0.41$\pm$0.01     0.49$\pm$0.00     0.49$\pm$0.00     0.49$\pm$0.00     2.01$\pm$0.03     0.68$\pm$0.00     0.46$\pm$0.00     0.78$\pm$0.05     0.38$\pm$0.01     0.36$\pm$0.00

Faculty: CS     0.33$\pm$0.00     0.98$\pm$0.10     1.40$\pm$0.00     0.34$\pm$0.01     0.61$\pm$0.00     0.51$\pm$0.00     0.44$\pm$0.00     1.99$\pm$0.27     0.93$\pm$0.00     0.58$\pm$0.00     0.87$\pm$0.09     0.33$\pm$0.03     0.32$\pm$0.00

Faculty: History     0.32$\pm$0.00     0.57$\pm$0.00     2.16$\pm$0.80     0.30$\pm$0.01     0.57$\pm$0.00     0.40$\pm$0.00     0.37$\pm$0.00     2.13$\pm$0.30     0.95$\pm$0.00     0.38$\pm$0.00     0.84$\pm$0.17     0.28$\pm$0.01     0.30$\pm$0.01

Basketball (avg)     0.78$\pm$0.00     1.72$\pm$0.00     1.98$\pm$0.00     0.91$\pm$0.03     0.79$\pm$0.00     0.88$\pm$0.00     0.88$\pm$0.00     1.95$\pm$0.00     0.99$\pm$0.00     0.89$\pm$0.00     nan$\pm$nan     0.80$\pm$0.00     0.73$\pm$0.00

Basketball finer (avg)     0.81$\pm$0.00     1.73$\pm$0.01     1.96$\pm$0.00     1.39$\pm$0.02     0.85$\pm$0.00     1.19$\pm$0.00     1.15$\pm$0.00     1.97$\pm$0.00     1.00$\pm$0.00     0.90$\pm$0.00     nan$\pm$nan     0.84$\pm$0.00     0.74$\pm$0.00

Football (avg)     0.91$\pm$0.00     1.63$\pm$0.12     1.20$\pm$0.00     0.94$\pm$0.02     0.94$\pm$0.00     1.07$\pm$0.00     1.08$\pm$0.00     1.78$\pm$0.03     1.00$\pm$0.00     0.90$\pm$0.00     1.72$\pm$0.09     0.81$\pm$0.03     0.78$\pm$0.02

Football finer (avg)     0.98$\pm$0.00     1.68$\pm$0.03     1.16$\pm$0.00     1.01$\pm$0.02     0.93$\pm$0.00     1.13$\pm$0.00     1.21$\pm$0.00     1.91$\pm$0.01     1.00$\pm$0.00     0.90$\pm$0.00     2.06$\pm$0.04     0.89$\pm$0.06     0.82$\pm$0.01

HeadToHead     0.25$\pm$0.00     0.48$\pm$0.00     0.50$\pm$0.00     0.28$\pm$0.00     0.29$\pm$0.00     0.37$\pm$0.00     0.34$\pm$0.00     0.50$\pm$0.01     0.45$\pm$0.00     0.36$\pm$0.00     nan$\pm$nan     0.27$\pm$0.00     0.24$\pm$0.00

Finance     0.41$\pm$0.00     0.50$\pm$0.00     0.40$\pm$0.00     0.45$\pm$0.00     0.41$\pm$0.00     0.44$\pm$0.00     0.44$\pm$0.00     0.47$\pm$0.00     0.41$\pm$0.00     0.41$\pm$0.00     nan$\pm$nan     0.41$\pm$0.00     0.40$\pm$0.00

Animal     0.13$\pm$0.00     0.40$\pm$0.06     0.58$\pm$0.11     0.11$\pm$0.00     0.08$\pm$0.00     0.14$\pm$0.00     0.16$\pm$0.00     0.49$\pm$0.00     0.26$\pm$0.00     0.13$\pm$0.00     0.50$\pm$0.08     0.10$\pm$0.02     0.06$\pm$0.00

Faculty: Business     0.10$\pm$0.00     0.21$\pm$0.00     0.30$\pm$0.00     0.10$\pm$0.00     0.12$\pm$0.00     0.12$\pm$0.00     0.12$\pm$0.00     0.50$\pm$0.01     0.17$\pm$0.00     0.12$\pm$0.00     0.19$\pm$0.01     0.10$\pm$0.00     0.09$\pm$0.00

Faculty: CS     0.08$\pm$0.00     0.24$\pm$0.02     0.35$\pm$0.00     0.08$\pm$0.00     0.15$\pm$0.00     0.13$\pm$0.00     0.11$\pm$0.00     0.50$\pm$0.07     0.23$\pm$0.00     0.15$\pm$0.00     0.22$\pm$0.02     0.08$\pm$0.01     0.08$\pm$0.00

Faculty: History     0.08$\pm$0.00     0.14$\pm$0.00     0.54$\pm$0.20     0.08$\pm$0.00     0.15$\pm$0.00     0.10$\pm$0.00     0.09$\pm$0.00     0.53$\pm$0.08     0.24$\pm$0.00     0.10$\pm$0.00     0.21$\pm$0.04     0.07$\pm$0.00     0.07$\pm$0.00

Basketball (avg)     0.20$\pm$0.00     0.43$\pm$0.00     0.49$\pm$0.00     0.23$\pm$0.01     0.20$\pm$0.00     0.22$\pm$0.00     0.22$\pm$0.00     0.49$\pm$0.00     0.25$\pm$0.00     0.22$\pm$0.00     nan$\pm$nan     0.20$\pm$0.00     0.18$\pm$0.00

Basketball finer (avg)     0.20$\pm$0.00     0.43$\pm$0.00     0.49$\pm$0.00     0.35$\pm$0.00     0.21$\pm$0.00     0.30$\pm$0.00     0.29$\pm$0.00     0.49$\pm$0.00     0.25$\pm$0.00     0.23$\pm$0.00     nan$\pm$nan     0.21$\pm$0.00     0.18$\pm$0.00

Football (avg)     0.23$\pm$0.00     0.41$\pm$0.03     0.30$\pm$0.00     0.23$\pm$0.01     0.24$\pm$0.00     0.27$\pm$0.00     0.27$\pm$0.00     0.44$\pm$0.01     0.25$\pm$0.00     0.22$\pm$0.00     0.43$\pm$0.02     0.22$\pm$0.01     0.21$\pm$0.00

Football finer (avg)     0.25$\pm$0.00     0.42$\pm$0.01     0.29$\pm$0.00     0.25$\pm$0.01     0.23$\pm$0.00     0.28$\pm$0.00     0.30$\pm$0.00     0.48$\pm$0.00     0.25$\pm$0.00     0.22$\pm$0.00     0.51$\pm$0.01     0.24$\pm$0.01     0.21$\pm$0.00

Performance on Kendall Tau based on the lowest $\mathcal{L}_\text{upset, naive}$ on ERO models, averaged over 10 runs with one standard deviation. “avg" for time series first average over all seasons, then consider mean and standard deviation over the 10 averaged values. The best is marked in bold red while the second best is in underline blue. As MVR does not generate results after one week, we leave it out here.

Data      SpringRank     SyncRank     SerialRank     BTL     DavidScore     Eig.Cent.     PageRank     RankCent.     SVD_RS     SVD_NRS     GNNRank-N     GNNRank-P

ERO(p=0.05, style=uniform,$\eta$=0.1)     0.75$\pm$0.00     0.04$\pm$0.00     0.03$\pm$0.00     0.70$\pm$0.01     0.77$\pm$0.00     0.56$\pm$0.00     0.58$\pm$0.00     0.01$\pm$0.05     0.74$\pm$0.00     0.77$\pm$0.00     0.76$\pm$0.01     0.79$\pm$0.01

ERO(p=0.05, style=gamma,$\eta$=0.2)     0.61$\pm$0.00     0.01$\pm$0.00     -0.01$\pm$0.00     0.61$\pm$0.00     0.74$\pm$0.00     0.52$\pm$0.00     0.51$\pm$0.00     -0.01$\pm$0.01     0.45$\pm$0.00     0.64$\pm$0.00     0.52$\pm$0.01     0.77$\pm$0.00

ERO(p=0.05, style=uniform,$\eta$=0.3)     0.61$\pm$0.00     0.05$\pm$0.00     0.01$\pm$0.00     0.59$\pm$0.01     0.68$\pm$0.00     0.44$\pm$0.00     0.41$\pm$0.00     0.05$\pm$0.00     0.60$\pm$0.00     0.62$\pm$0.00     0.62$\pm$0.00     0.70$\pm$0.02

ERO(p=0.05, style=gamma,$\eta$=0.4)     0.51$\pm$0.00     0.08$\pm$0.00     -0.00$\pm$0.00     0.52$\pm$0.00     0.65$\pm$0.00     0.43$\pm$0.00     0.43$\pm$0.00     0.09$\pm$0.01     0.23$\pm$0.00     0.44$\pm$0.00     0.38$\pm$0.08     0.66$\pm$0.01

ERO(p=1, style=uniform,$\eta$=0.5)     0.85$\pm$0.00     0.07$\pm$0.00     0.92$\pm$0.00     0.81$\pm$0.03     0.91$\pm$0.00     0.80$\pm$0.00     0.73$\pm$0.00     0.24$\pm$0.00     0.89$\pm$0.00     0.87$\pm$0.00     0.90$\pm$0.01     0.92$\pm$0.00

ERO(p=1, style=gamma,$\eta$=0.6)     0.72$\pm$0.00     0.09$\pm$0.00     0.89$\pm$0.00     0.67$\pm$0.01     0.88$\pm$0.00     0.65$\pm$0.00     0.64$\pm$0.00     0.05$\pm$0.02     0.74$\pm$0.00     0.73$\pm$0.00     0.77$\pm$0.00     0.89$\pm$0.00

Kendall tau values and corresponding $\mathcal{L}_\text{upset, simple}$ values on ERO models, where GNN results are selected from the lowest $\mathcal{L}_\text{upset, simple}$. Results are averaged over 10 runs with one standard deviation. The best for each evaluation metric is in bold red.

Evaluation   4c|Kendall tau   4c$\mathcal{L}_\text{upset, simple}$

Data      SpringRank     SerialRank       GNNRank-N     GNNRank-P    SpringRank     SerialRank       GNNRank-N     GNNRank-P

ERO(p=0.05, style=gamma,$\eta$=0)     0.81$\pm$0.00     0.00$\pm$0.00     0.87$\pm$0.00     0.87$\pm$0.00      0.30$\pm$0.00     2.05$\pm$0.00     0.17$\pm$0.00     0.17$\pm$0.00

ERO(p=0.05, style=uniform,$\eta$=0.5)     0.47$\pm$0.00     0.01$\pm$0.00     0.42$\pm$0.04     0.47$\pm$0.00      1.16$\pm$0.00     2.03$\pm$0.00     1.26$\pm$0.08     1.16$\pm$0.00

ERO(p=0.05, style=uniform,$\eta$=0.6)     0.39$\pm$0.00     -0.00$\pm$0.00     0.33$\pm$0.00     0.39$\pm$0.00      1.26$\pm$0.00     2.04$\pm$0.00     1.40$\pm$0.01     1.26$\pm$0.00

ERO(p=1, style=uniform,$\eta$=0)     1.00$\pm$0.00     1.00$\pm$0.00     1.00$\pm$0.00     1.00$\pm$0.00    	 0.00$\pm$0.00     0.00$\pm$0.00     0.00$\pm$0.00     0.00$\pm$0.00

ERO(p=1, style=gamma,$\eta$=0)     1.00$\pm$0.00     1.00$\pm$0.00     1.00$\pm$0.00     1.00$\pm$0.00      0.00$\pm$0.00     0.00$\pm$0.00     0.00$\pm$0.00     0.00$\pm$0.00

ERO(p=1, style=uniform,$\eta$=0.1)     0.94$\pm$0.00     0.98$\pm$0.00     0.93$\pm$0.01     0.98$\pm$0.00      0.31$\pm$0.00     0.24$\pm$0.00     0.33$\pm$0.02     0.24$\pm$0.00

ERO(p=1, style=gamma,$\eta$=0.1)     0.88$\pm$0.00     0.98$\pm$0.00     0.89$\pm$0.01     0.98$\pm$0.00     0.41$\pm$0.00     0.23$\pm$0.00     0.40$\pm$0.01     0.23$\pm$0.00

$\mathcal{L}_\text{upset, simple}$ comparison for different variants on real-world data, averaged over 10 runs, and plus/minus one standard deviation. The best for each group (GNNRank-N or GNNRank-P) is marked in bold red while the second best is in underline blue.

Methods   3c|GNNRank-N   7cGNNRank-P

Data/Variant    loss sum     $\mathcal{L}_\text{upset,margin} $     $\mathcal{L}_\text{upset, ratio} $     loss sum     $\mathcal{L}_\text{upset,margin} $      $\mathcal{L}_\text{upset, ratio} $       no pretrain     $\{\alpha_\gamma\}_{\gamma=1}^\Gamma$not trainable    $\Gamma=3$     $\Gamma=7$

Animal     0.43$\pm$0.06     0.59$\pm$0.08     0.41$\pm$0.09     0.25$\pm$0.00     0.25$\pm$0.00     0.25$\pm$0.01     0.25$\pm$0.00     0.25$\pm$0.00     0.25$\pm$0.00     0.25$\pm$0.00

Faculty: Business     0.40$\pm$0.02     0.49$\pm$0.16     0.38$\pm$0.01     0.36$\pm$0.00     0.36$\pm$0.00     0.36$\pm$0.00     0.36$\pm$0.00     0.36$\pm$0.00     0.36$\pm$0.00     0.36$\pm$0.00

Faculty: CS     0.35$\pm$0.01     0.36$\pm$0.01     0.33$\pm$0.03     0.32$\pm$0.00     0.32$\pm$0.00     0.32$\pm$0.00     0.33$\pm$0.00     0.32$\pm$0.00     0.32$\pm$0.00     0.32$\pm$0.00

Faculty: History     0.28$\pm$0.01     0.31$\pm$0.01     0.28$\pm$0.01     0.30$\pm$0.01     0.30$\pm$0.01     0.30$\pm$0.02     0.30$\pm$0.01     0.30$\pm$0.01     0.30$\pm$0.01     0.30$\pm$0.01

Football (avg)     0.82$\pm$0.01     0.84$\pm$0.03     0.82$\pm$0.05     0.78$\pm$0.02     0.78$\pm$0.01     0.79$\pm$0.01     0.79$\pm$0.02     0.79$\pm$0.02     0.77$\pm$0.01     0.78$\pm$0.02

Football finer (avg)     0.90$\pm$0.01     0.97$\pm$0.06     0.91$\pm$0.07     0.82$\pm$0.01     0.84$\pm$0.01     0.82$\pm$0.01     0.84$\pm$0.02     0.82$\pm$0.00     0.82$\pm$0.01     0.82$\pm$0.01

§.§ Discussion

Ablation Study.
Table <ref> shows results on varying the current choices:
1) For GNNRank-N methods: forcing the loss to be the sum $\mathcal{L}_\text{upset, simple}+\mathcal{L}_\text{upset, margin}$, $\mathcal{L}_\text{upset, simple}$ only, or $\mathcal{L}_\text{upset, margin}$, respectively;
2) for GNNRank-P methods: in addition to the variants for GNNRank-N methods, removing pretraining, fixing all $\alpha_\gamma$ in Algo. <ref>, and changing the number of Fiedler proximal steps from default 5 to 3 or 7.

It is shown that for GNNRank-N methods, using $\mathcal{L}_\text{upset, margin}$  usually harms performance.  For GNNRank-P methods, using $\mathcal{L}_\text{upset, margin}$ in addition to $\mathcal{L}_\text{upset, ratio}$ usually boosts performance.
Pretraining generally leads to better performance, so does making $\{\alpha_\gamma\}_{\gamma=1}^\Gamma$ trainable.
The number of proximal gradient steps does not seem to matter much, so we use 5 throughout. Full comparison tables are in Appendix <ref> including results on $\mathcal{L}_\text{upset, naive}$, with similar conclusions.

Inductive Learning.
We observe that
our proximal methods, if trained only once and then applied to similar data sets, still perform comparably. This can save training time and validates the inductive learning ability for our framework.
To this end, Appendix <ref> shows results on the performance of “IB proximal baseline" variant, trained with “emb baseline" on the Basketball finer data set. On average, directly applying gives $\mathcal{L}_\text{upset, simple}=0.75\pm 0.02$ and $\mathcal{L}_\text{upset, naive}=0.19\pm 0.01$ while training specifically for the
season gives $\mathcal{L}_\text{upset, simple}=0.74\pm 0.00$ and $\mathcal{L}_\text{upset, naive}=0.19\pm 0.00$.

Variants and Hyperparameters.
The results
in Tables <ref> and <ref> are selected within either non-proximal or proximal categories, depending on whether they have proximal gradient steps within the architecture, showing
the lowest reported evaluation metric (except for Kendall tau,
when we select variants based on the lowest $\mathcal{L}_\text{upset, naive}$) for all variants within the group.
Appendix <ref> gives
the variant selected based on minimizing either $\mathcal{L}_\text{upset, simple}$ or $\mathcal{L}_\text{upset, ratio}$ for non-proximal and proximal groups, respectively. We find that each variant has its scenarios where it shows competitive or even outstanding performance;  that “dist" seems to outperform “innerproduct" within non-proximal methods; and that “proximal baseline" is usually the best among proximal methods, with SyncRank output as initial guess, pretrained with a SerialRank similarity matrix. This shows
that our proximal method, initialized
with a good baseline, e.g. Sync-Rank, and pretrained with information from SerialRank, can boost it by using a learnable similarity matrix.

Boosting Baselines.
Appendix <ref> shows improvements on $\mathcal{L}_{upset, simple}$ and $\mathcal{L}_{upset, naive}$ by “proximal baseline" when setting a certain baseline as $\mathbf{r}'$. Across all data sets, “proximal baseline" improves the most (by 1.02 and 0.24, respectively) with SyncRank as initial guess,
while the average improvement for SpringRank, SerialRank, BTL, Eig.Cent., PageRank and SVD_NRS are 0.07, 0.82, 0.22, 0.19, 0.21, and 0.12, respectively, for $\mathcal{L}_{upset, simple}$, and for 0.00, 0.18, 0.04, 0.03, 0.03, and 0.01, respectively, for $\mathcal{L}_{upset, naive}$.

§ CONCLUSION AND OUTLOOK

We have proposed a general framework based on directed graph neural networks to recover global rankings from pairwise comparisons. Future directions include  learning a more powerful model to work for different input digraphs, minimizing upsets under some constraints, training with some supervision of ground-truth rankings, and exploring the interplay with low-rank matrix completion. Incorporating side information, in the form of node level covariates, and comparing to the, currently rather limited, existing literature on ranking with covariates, is another interesting direction where we expect  GNNRank to perform well.

[Ali et al., 1986]
Ali, I., Cook, W. D., and Kress, M.
On the minimum violations ranking of a tournament.
Management Science, 320 (6):0 660–672, 1986.
ISSN 00251909, 15265501.
URL <http://www.jstor.org/stable/2631621>.

[Atkins et al., 1998]
Atkins, J., Boman, E., and Hendrickson, B.
A spectral algorithm for seriation and the consecutive ones problem.
SIAM Journal on Computing, 1998.

[Bennett et al., 2021]
Bennett, S., Cucuringu, M., and Reinert, G.
Detection and clustering of lead-lag networks for multivariate time
series with an application to financial markets.
7th SIGKDD Workshop on Mining and Learning from Time Series
(MiLeTS), 2021.

[Bonacich, 1987]
Bonacich, P.
Power and centrality: A family of measures.
American Journal of Sociology, 920 (5):0
1170–1182, 1987.

[Bradley & Terry, 1952]
Bradley, R. A. and Terry, M. E.
Rank analysis of incomplete block designs: I. the method of paired
Biometrika, 390 (3/4):0 324–345, 1952.

[Brandenburg et al., 2013]
Brandenburg, F. J., Gleißner, A., and Hofmeier, A.
Comparing and aggregating partial orders with Kendall tau
Discrete Mathematics, Algorithms and Applications, 2013.

[Burges et al., 2005]
Burges, C., Shaked, T., Renshaw, E., Lazier, A., Deeds, M., Hamilton, N., and
Hullender, G.
Learning to rank using gradient descent.
In Proceedings of the 22nd International Conference on Machine
learning, pp.  89–96, 2005.

[Chen et al., 2017]
Chen, Y., Qi, L., and Zhang, X.
The Fiedler vector of a Laplacian tensor for hypergraph
SIAM Journal on Scientific Computing, 390
(6):0 A2508–A2537, 2017.

[Chowdhury et al., 2021]
Chowdhury, A., Verma, G., Rao, C., Swami, A., and Segarra, S.
Unfolding wmmse using graph neural networks for efficient power
IEEE Transactions on Wireless Communications, 2021.

[Clauset et al., 2015]
Clauset, A., Arbesman, S., and Larremore, D. B.
Systematic inequality and hierarchy in faculty hiring networks.
Science Advances, 10 (1):0 e1400005, 2015.

[Cremonesi et al., 2010]
Cremonesi, P., Koren, Y., and Turrin, R.
Performance of recommender algorithms on top-n recommendation tasks.
In Proceedings of the fourth ACM Conference on Recommender
Systems, pp.  39–46. ACM, 2010.

[Cucuringu, 2016]
Cucuringu, M.
Sync-rank: Robust ranking, constrained ranking and rank aggregation
via eigenvector and SDP synchronization.
IEEE Transactions on Network Science and Engineering,
30 (1):0 58–79, 2016.

[Cucuringu et al., 2020]
Cucuringu, M., Li, H., Sun, H., and Zanetti, L.
Hermitian matrices for clustering directed graphs: insights and
In International Conference on Artificial Intelligence and
Statistics, pp.  983–992. PMLR, 2020.

[Damke & Hüllermeier, 2021]
Damke, C. and Hüllermeier, E.
Ranking structured objects with graph neural networks.
arXiv preprint arXiv:2104.08869, 2021.

[d'Aspremont et al., 2021]
d'Aspremont, A., Cucuringu, M., and Tyagi, H.
Ranking and synchronization from pairwise measurements via SVD.
Journal of Machine Learning Research, 22:0 19–1,

[David, 1987]
David, H. A.
Ranking from unbalanced paired-comparison data.
Biometrika, 740 (2):0 432–436, 1987.

[De Bacco et al., 2018]
De Bacco, C., Larremore, D. B., and Moore, C.
A physical model for efficient ranking in networks.
Science advances, 40 (7):0 eaar8260, 2018.

[Fiedler, 1973]
Fiedler, M.
Algebraic connectivity of graphs.
Czechoslovak Mathematical Journal, 230 (2):0
298–305, 1973.

[Firth, 2005]
Firth, D.
Bradley-Terry models in R.
Journal of Statistical Software, 120 (1):0
1–12, 2005.

[Fogel et al., 2014]
Fogel, F., d'Aspremont, A., and Vojnovic, M.
Serialrank: Spectral ranking using seriation.
Advances in Neural Information Processing Systems,
27:0 900–908, 2014.

[Gregor & LeCun, 2010]
Gregor, K. and LeCun, Y.
Learning fast approximations of sparse coding.
In Proceedings of the 27th International Conference on Machine
Learning, pp.  399–406, 2010.

[Gupte et al., 2011]
Gupte, M., Shankar, P., Li, J., Muthukrishnan, S., and Iftode, L.
Finding hierarchy in directed online social networks.
In Proceedings of the 20th International Conference on the
World wide Web, pp.  557–566, 2011.

[He et al., 2021]
He, Y., Reinert, G., and Cucuringu, M.
DIGRAC: Digraph Clustering with Flow Imbalance.
arXiv preprint arXiv:2106.05194, 2021.

[Hobson & DeDeo, 2015]
Hobson, E. A. and DeDeo, S.
Social feedback and the emergence of rank in animal society.
PLoS Computational Biology, 110 (9):0
e1004411, 2015.

[Kendall & Smith, 1940]
Kendall, M. G. and Smith, B. B.
On the method of paired comparisons.
Biometrika, 310 (3-4):0 324–345, 1940.

[Kingma & Ba, 2014]
Kingma, D. P. and Ba, J.
Adam: A method for stochastic optimization.
arXiv preprint arXiv:1412.6980, 2014.

[Köppel et al., 2019]
Köppel, M., Segner, A., Wagener, M., Pensel, L., Karwath, A., and Kramer,
Pairwise learning to rank by neural networks revisited:
Reconstruction, theoretical analysis and practical performance.
arXiv preprint arXiv:1909.02768, 2019.

[Liu, 2011]
Liu, T.-Y.
Learning to rank for information retrieval.
Springer Science & Business Media, 2011.

[Liu et al., 2017]
Liu, Z., Li, X., Luo, P., Loy, C. C., and Tang, X.
Deep learning markov random field for semantic segmentation.
IEEE Transactions on Pattern Analysis and Machine
Intelligence, 400 (8):0 1814–1828, 2017.

[Luce, 1959]
Luce, R. D.
Individual choice behavior: A theoretical analysis.
Courier Corporation, 1959.

[Maurya et al., 2021]
Maurya, S. K., Liu, X., and Murata, T.
Graph neural networks for fast node ranking approximation.
ACM Transactions on Knowledge Discovery from Data (TKDD),
150 (5):0 1–32, 2021.

[Negahban et al., 2017]
Negahban, S., Oh, S., and Shah, D.
Rank centrality: Ranking from pairwise comparisons.
Operations Research, 2017.

[Newman, 2010]
Newman, M. E. J.
Networks: An Introduction.
Oxford University Press, USA, 2010.

[Page et al., 1998]
Page, L., Brin, S., Motwani, R., and Winograd, T.
The PageRank citation ranking: Bringing order to the Web.
In Proceedings of the 7th International World Wide Web
Conference, pp.  161–172, 1998.

[Parikh & Boyd, 2014]
Parikh, N. and Boyd, S.
Proximal algorithms.
Foundations and Trends in Optimization, 10
(3):0 127–239, 2014.

[Raykar & Yu, 2011]
Raykar, V. C. and Yu, S.
Ranking annotators for crowdsourced labeling tasks.
In Advances in Neural Information Processing Systems, pp.  1809–1817, 2011.

[Rigutini et al., 2011]
Rigutini, L., Papini, T., Maggini, M., and Scarselli, F.
SortNet: Learning to rank by a neural preference function.
IEEE Transactions on Neural Networks, 220
(9):0 1368–1380, 2011.

[Scarselli et al., 2005]
Scarselli, F., Yong, S. L., Gori, M., Hagenbuchner, M., Tsoi, A. C., and
Maggini, M.
Graph neural networks for ranking web pages.
In The 2005 IEEE/WIC/ACM International Conference on Web
Intelligence (WI'05). IEEE, 2005.

[Schütze et al., 2008]
Schütze, H., Manning, C. D., and Raghavan, P.
Introduction to information retrieval, volume 39.
Cambridge University Press Cambridge, 2008.

[Singer, 2011]
Singer, A.
Angular synchronization by eigenvectors and semidefinite programming.
Applied and Computational Harmonic Analysis, 300
(1):0 20–36, 2011.

[Tong et al., 2020]
Tong, Z., Liang, Y., Sun, C., Li, X., Rosenblum, D., and Lim, A.
Digraph inception convolutional networks.
Advances in Neural Information Processing Systems,
33:0 17907–17918, 2020.

[Tsokos et al., 2019]
Tsokos, A., Narayanan, S., Kosmidis, I., Baio, G., Cucuringu, M., Whitaker, G.,
and Király, F.
Modeling outcomes of soccer matches.
Machine Learning, 1080 (1):0 77–95, 2019.

[Vu et al., 2019]
Vu, T., Raich, R., and Fu, X.
On convergence of projected gradient descent for minimizing a
large-scale quadratic over the unit sphere.
In 2019 IEEE 29th International Workshop on Machine Learning
for Signal Processing (MLSP), pp.  1–6. IEEE, 2019.

[Wang et al., 2021]
Wang, J., Xie, H., Wang, F. L., Lee, L.-K., and Au, O. T. S.
Top-n personalized recommendation with graph neural networks in
Computers and Education: Artificial Intelligence, 2:0
100010, 2021.

[Wu et al., 2020]
Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., and Philip, S. Y.
A comprehensive survey on graph neural networks.
IEEE Transactions on Neural Networks and Learning Systems,
320 (1):0 4–24, 2020.

[Yang et al., 2021]
Yang, Y., Liu, T., Wang, Y., Zhou, J., Gan, Q., Wei, Z., Zhang, Z., Huang, Z.,
and Wipf, D.
Graph neural networks inspired by classical iterative algorithms.
In International Conference on Machine Learning. PMLR, 2021.

[Zhang et al., 2021]
Zhang, X., He, Y., Brugnone, N., Perlmutter, M., and Hirn, M.
Magnet: A neural network for directed graphs.
Advances in Neural Information Processing Systems, 34, 2021.

[Zhou et al., 2020]
Zhou, J., Cui, G., Hu, S., Zhang, Z., Yang, C., Liu, Z., Wang, L., Li, C., and
Sun, M.
Graph neural networks: A review of methods and applications.
AI Open, 1:0 57–81, 2020.

§ IMPLEMENTATION DETAILS

§.§ Setup

We use all data for training for at most 1000 epochs, and stop  early if the loss does not decrease for 200 epochs. For proximal variants, we use 50 epochs for pretraining. We use Adam [Kingma & Ba, 2014] and  Stochastic Gradient Descend (SGD) as the optimizers and $\ell_2$ regularization with weight decay $5\cdot 10^{-4}$ to avoid overfitting. We use as learning rate 0.01 throughout for GNNRank-N methods as well as pretraining with Adam, and 10 times that of pretraining learning rate for GNNRank-P methods with SGD. We run a grid search on hyperparameters.

For real-world data sets, we conduct 10 repeated runs, while for synthetic data, we generate 5 synthetic networks under the same setting, each with 2 repeated runs.

§.§ Codes, Data and Hardware

To fully  reproduce our results, anonymized code and preprocessed data are available at <https://anonymous.4open.science/r/GNNRank>. Experiments were conducted on a compute node with 8 Nvidia Tesla T4, 96 Intel Xeon Platinum 8259CL CPUs @ 2.50GHz and $378$GB RAM. Most experiments can be completed within a week, including all variants,  hyperparameter searches and ablation studies, except for those on MVR.

§ DETAILS ON FINDING $\MATHBF{Q}$ FOR PROXIMAL GRADIENT STEPS

There are infinitely many choices of valid $\mathbf{Q}$;
here we construct one of the special $\mathbf{Q}$'s for which
we can compute $\mathbf{Q} \mathbf{L}$ efficiently.
Since $\mathbf{Q}^\top \mathbf{e}_1 = \mathbf{1}/\sqrt{n}$, we can construct $\mathbf{R} = \mathbf{Q}^\top$ as a series of matrix multiplication of $(n-1)$ rotation matrices on two adjacent axes

\mathbf{R} = \mathbf{R}_{n-1} \mathbf{R}_{n-2} \cdots \mathbf{R}_2 \mathbf{R}_1

where $\mathbf{R}_k$ is defined by:

\left[ \mathbf{R}_k \right]_{ij} = \begin{cases}
\sqrt{\frac{1}{n-k}} & i=k,j=k \text{ or } i=k+1, j=k+1 \\
-\sqrt{\frac{n-k-1}{n-k}} & i=k,j=k+1 \\
\sqrt{\frac{n-k-1}{n-k}} & i=k+1, j=k \\
1 & i=j \text{, and } i, j \ne k \text{ or } k + 1 \\
0 & \text{otherwise.}
\end{cases}

To explain this construction, starting from $\mathbf{e}_1 = \begin{bmatrix} 1 & 0 & \cdots & 0 \end{bmatrix}^\top$,
we carry out a rotation on the first and second axis to make the first element $\sqrt{1 / n}$.  The rotation matrix is

\mathbf{R}_1 = \begin{bmatrix}
\sqrt{\frac{1}{n}} & -\sqrt{\frac{n-1}{n}} & & & \cdots & \\
\sqrt{\frac{n-1}{n}} & \sqrt{\frac{1}{n}} & & & \cdots & \\
& & 1 & & \cdots & \\
& & & 1 & \cdots & \\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\
& & & & & 1
\end{bmatrix}

We observe that
$$\mathbf{R}_1 \mathbf{e}_1 = \begin{bmatrix} \sqrt{\frac{1}{n}} & \sqrt{\frac{n-1}{n}} & 0 & 0 & \cdots & 0 \end{bmatrix}^\top.$$

The second rotation
occurs on the second and third axis to render $\mathbf{R}_2 \mathbf{R}_1 \mathbf{e}_1 = \begin{bmatrix} \sqrt{\frac{1}{n}} & \sqrt{\frac{1}{n}} & \sqrt{\frac{n-2}{n}} & 0 & \cdots & 0 \end{bmatrix}^\top$; this $\mathbf{R}_2$ is

\mathbf{R}_2 = \begin{bmatrix}
1 & & & & \cdots & \\
& \sqrt{\frac{1}{n-1}} & -\sqrt{\frac{n-2}{n-1}} & & \cdots & \\
& \sqrt{\frac{n-2}{n-1}} & \sqrt{\frac{1}{n-1}} & & \cdots & \\
& & & 1 & \cdots & \\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\
& & & & & 1
\end{bmatrix}

The general matrices $R_k$ are obtained by continuing this construction.

The matrix $\mathbf{R}$ is

\begin{equation*}
\begin{scriptsize}
\begin{bmatrix}
\sqrt\frac{1}{n} & -\sqrt{\frac{n-1}{n}} & & & \cdots & \\
\sqrt\frac{1}{n} & \sqrt{\frac{1}{n(n-1)}} & -\sqrt{\frac{n-2}{n-1}} & & \cdots & \\
\sqrt\frac{1}{n} & \sqrt{\frac{1}{n(n-1)}} & \sqrt{\frac{1}{(n-1)(n-2)}} & -\sqrt{\frac{n-3}{n-2}} & \cdots & \\
\sqrt{\frac{1}{n}} & \sqrt{\frac{1}{n(n-1)}} & \sqrt{\frac{1} {(n-1)(n-2)}} & \sqrt{\frac{1}{(n-2)(n-3)}} & \cdots & \\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\
\sqrt{\frac{1}{n}} & \sqrt{\frac{1}{n(n-1)}} & \sqrt{\frac{1}{(n-1)(n-2)}}& \sqrt{\frac{1}{(n-2)(n-3)}} & \cdots & \sqrt{\frac{1}{2}}
\end{bmatrix}
\end{scriptsize}
\end{equation*}

We then put $\mathbf{Q} = \mathbf{R}^\top$.

The resulting $\mathbf{Q}$ is
the following upper Hessenberg matrix, which is independent of model parameters and can be efficiently precomputed

\begin{equation*}
\mathbf{Q}_{ij} = \begin{cases}
\sqrt{\frac{1}{n}} & i=1 \\
-\sqrt{\frac{n-i+1}{n-i+2}} & i\geq 2, j=i-1 \\
\sqrt{\frac{1}{(n-i+1)(n-i+2)}} & i\geq 2, j\geq i \\
0 & \text{otherwise.}
\end{cases}
\end{equation*}

The computation of $\mathbf{Q} \mathbf{L}$ takes $O(n^2)$ time since $\mathbf{Q}$ is a summation of (1) an upper-triangular matrix $\mathbf{U}$ with the same non-zero value on the same row, and (2) a shift matrix $\mathbf{V}$ (with negative subdiagonal). Then
$\mathbf{U} \mathbf{L}$ is essentially a cumulative sum from the bottom row to the top row, followed by a row-wise multiplication of the diagonal of $\mathbf{U}$, and
$\mathbf{V} \mathbf{L}$ is essentially a combination of row-wise multiplication and indexing.

§ THEORETICAL ANALYSIS AND PRACTICAL CONSIDERATIONS ON CONVERGENCE OF THE PROXIMAL GRADIENT STEPS

First we prove a theorem useful for the main result.

Let $\{\alpha_\gamma>0\}_{\gamma=1}^\Gamma$ in Algo. <ref> be fixed and equal to $\alpha$. Let $\rho$ be the Fiedler eigenvalue of $\mathbf{S}$, i.e., the second smallest eigenvalue of $\mathbf{L}$.  Let $\mathbf{r}^*$ be a Fiedler eigenvector corresponding to $\rho,$ let  $\mathbf{y}^*=\left[\mathbf{Q}\mathbf{r}^*\right]_{2:n}$ and $\widetilde{L} = \left[\mathbf{Q L Q}^\top\right]_{2:n,2:n}.$
Let $\lambda_1 \geq \lambda_2 \cdots \geq \lambda_{n-1}=0$ be the eigenvalues of $ \mathbf{P}\widetilde{\mathbf{L}}\mathbf{P},$ where $\mathbf{P}=\mathbf{I}-\mathbf{y}^*\mathbf{y}^{*\top}$.
Let $\rho_\alpha=\max_{1\leq i \leq n-2}\frac{|1-2\alpha\lambda_i|}{1-2\alpha\rho}$. If $\mathbf{r}^*$ is a strict local minimum of problem (<ref>), and if $\rho_\alpha<1$ and $\alpha(\lambda_1+\rho)<1,$ then Algo. <ref> converges locally uniformly to  $\mathbf{r}^*$.

Our problem (<ref>) is a special case of the problem (2) in [Vu et al., 2019] (henceforth (<ref>) further below, of minimizing a quadratic over a sphere), where our fixed point $\mathbf{y}^*$ is determined by $\mathbf{f}_\alpha(\mathbf{\overline{x}})=\mathcal{P}_{\mathcal{S}^{n-2}}(-\alpha(2\widetilde{\mathbf{L}}\mathbf{\overline{x}}))=\mathbf\mathbf{\overline{x}}$. Recall that the spherical projection operator $\mathcal{P}_{\mathcal{S}^{n-2}}(\cdot):\mathbb{R}^{n-1}\rightarrow\mathbb{R}^{n-1}$ is defined to be $\mathcal{P}_{\mathcal{S}^{n-2}}(\mathbf{x})=\frac{\mathbf{x}}{\left\lVert \mathbf{x} \right\rVert_2}$ if $\mathbf{x}\neq \mathbf{0}$, and $\mathcal{P}_{\mathcal{S}^{n-2}}(\mathbf{0})=[1,0,\dots,0]^\top,$ where $\mathbf{0}=[0,\dots,0]^\top.$
It is shown in Lemma 1 of [Vu et al., 2019] (henceforth Lemma <ref> further below) that $\mathbf{y}^*$ with $||\mathbf{y}^*||=1 $ being a solution of (<ref>) is equivalent to the existence of a constant   $\rho(\mathbf{\overline{x}})$ such that

=\rho(\mathbf{y}^*) \cdot \mathbf{y}^*,$$

rendering  $\rho(\mathbf{y}^*)$ to be  an eigenvalue of  $\widetilde{\mathbf{L}}$.  Theorem 1 in [Vu et al., 2019]  (henceforth Theorem <ref> below)  states that with an initial step size $\alpha>0$,  such that $2\alpha(\rho(
\mathbf{y}^*)+\lambda_1)<2$, as long as $\rho_\alpha=\max_{1\leq i \leq n-2}\frac{|1-2\alpha\lambda_i|}{1-2\alpha\gamma(\mathbf{y}^*})
<1,$ the proximal gradients steps will converge to a local minimum.

Since $\mathbf{r}^*$ is a strict local minimum of problem (<ref>), we have that $\mathbf{y}^*$ is a strict local minimum of problem (<ref>).
This is true because problem (<ref>) and problem (<ref>) are equivalent, and  there is a one-to-one correspondence between $\mathbf{r}^*$ and $\mathbf{y}^*, $ namely,  $\mathbf{y}^*=\left[\mathbf{Q}\mathbf{r}^*\right]_{2:n}\in\mathbb{R}^{n-1},$ and $\mathbf{r}^*=\text{CONCAT}(0,\left[\mathbf{Q}^\top\mathbf{r}^*\right])\in\mathbb{R}^n.$

Lemma <ref>
from  [Vu et al., 2019], we have $\rho<\lambda_{n-2}$, since $\mathbf{y}^*$ is a strict local minimum. In particular,
Theorem <ref>
in [Vu et al., 2019], when $\mathbf{y}^*$ is a strict local minimum to problem  (<ref>),
if $2\alpha(\rho+\lambda_1)<2$, i.e., $\alpha(\rho+\lambda_1)<1,$ there is a constant M such that

$$ || \mathbf{y}^{\gamma} -\mathbf{y}^* ||  \leq M  || \mathbf{y}^{0} - \mathbf{y}^*|| (\rho_\alpha + o(1))^\gamma,$$

where $\mathbf{y}^{0}$ is the initial guess at proximal gradient step 0, and $\gamma$ denotes the step number. As $\rho_\alpha <1$ is assumed, convergence follows.

For convergence,  it suffices to ensure that $\rho_\alpha<1,$ i.e. to have $2\alpha\gamma(\mathbf{\overline{x}})<1$, $|1-2\alpha\lambda_1|<1-\alpha\gamma(\mathbf{\overline{x}})$ and $|1-2\alpha\lambda_{n-2}|<1-2\alpha\gamma(\mathbf{\overline{x}})$. In particular, in our problem we take
$\rho(\mathbf{\overline{x}})=\rho$, which is also the smallest eigenvalue of $\widetilde{\mathbf{L}},$ so $\rho< \lambda_{n-2}\leq \lambda_1.$
To apply Theorem <ref> in order to obtain a convergence guarantee in Algo. <ref>, as
$\lambda_{n-2}>\rho,$ (which is equivalent to $\mathbf{r}^*$ being a strict local minimum) it remains to use an $\alpha$ value such that $2\alpha\lambda_{1}<1.$
Lemma <ref>
of  [Vu et al., 2019] also suggests that  if $2\alpha\lambda_{1}<1$,  then
we indeed have $\mathbf{r}^*$ as a global minimizer to problem (<ref>).

Finally we have the ingredients to prove the main result.

Let $\{\alpha_\gamma>0\}_{\gamma=1}^\Gamma$ in Algo. <ref> be fixed (equal to $\alpha$) and let $\rho$ be the Fiedler eigenvalue of $\mathbf{S}$.  Denote a Fiedler eigenvector by $\mathbf{r}^*$. Assume that $\mathbf{r}^*$ is a strict local minimizer of problem (<ref>).
then with our definition of the similarity matrix,  Algo. <ref> converges locally uniformly to $\mathbf{r}^*$.

Via our similarity matrix construction process, entries in $\mathbf{S}$ are upper-bounded by 1, so the degree matrix $\mathbf{D}$ has entries bounded above by $n,$ the number of nodes, and lower bounded by 0, and that $\mathbf{L}$ is positive semi-definite. We thus  have that the eigenvalues of $\mathbf{L}$ are in $[0,(n-1)+(n-1)\times 1]$ by the Gershgorin disc theorem.  Since $\mathbf{Q}$ is orthogonal, we have that eigenvalues of $\widetilde{\mathbf{L}}$ are also within the range $[0,2(n-1)].$ To see this, suppose $\mathbf{x}$ is an eigenvector of $\mathbf{L}$ with eigenvalue $\lambda,$ i.e., $\mathbf{Lx}=\lambda\mathbf{x}$, so $\mathbf{QLQ}\top(\mathbf{Qx})=\mathbf{QL}(\mathbf{Q}\top\mathbf{Q})\mathbf{x}=\mathbf{QL}\mathbf{x}=\mathbf{Q}(\mathbf{Lx})=\mathbf{Q}\lambda\mathbf{x}=\lambda(\mathbf{Qx}).$ Therefore, the values $\{\lambda_i\}_{i=1}^{n-2}$ in Theorem <ref> are bounded above by $2(n-1).$
Thus, we have that $\rho+\lambda_1\leq 2(n-1)+2(n-1)=4(n-1).$

For convergence,  it suffices to ensure that $\rho_\alpha=\max_{1\leq i \leq n-2}\frac{|1-2\alpha\lambda_i|}{1-2\alpha\rho}<1,$ i.e. to have $2\alpha\rho<1$, $|1-2\alpha\lambda_1|<1-2\alpha\rho$,  and $|1-\alpha\lambda_{n-2}|<1-2\alpha\rho$.

Thus, since we have $\lambda_{n-2}>\rho$ by
Lemma <ref>
from  [Vu et al., 2019] and proof of Theorem <ref>, it remains to use an $\alpha$ value such that $2\alpha\lambda_{1}<1,$ then $2\alpha\rho<2\alpha\lambda_1<1$, and $0<1-2\alpha\lambda_1=|1-2\alpha\lambda_1|\leq 1-2\alpha\lambda_{n-2}=|1-2\alpha\lambda_{n-2}|< 1-2\alpha\rho.$
With $\alpha<\frac{1}{4(n-1)},$ we indeed have $2\alpha\lambda_{1}<2\times\frac{1}{4(n-1)}\times 2(n-1)=1.$

Our current setting is to initialize all $\alpha$ values to be $\frac{1}{n-1}$.
Note that within Algo. <ref>, the $\alpha$ values are fixed. Although not guaranteed to converge with the initial $\alpha$,   they could  be adapted by our outer training loop, i.e. by optimization over the ranking loss function.
[Vu et al., 2019] also suggests the value of the optimal step size to be $\frac{2}{\lambda_1+\lambda_{n-2}},$ which during training our method could in principle reproduce if the optimal step size is actually important for making accurate final rankings.

We remark that real-world weighted networks have the corresponding Fiedler eigenvalue of multiplicity 1; this multiplicity is larger than 1, only for certain special classes of graphs that exhibit certain symmetries. Our pragmatic assumption that the Fiedler eigenvalue has multiplicity 1, which thus means $\mathbf{r}^*$ being a strict local minimum of problem <ref>, is not a very restrictive one.

For completeness, the remainder of this section recalls the setup and main results from [Vu et al., 2019]. The problem considered therein is that of minimizing a quadratic form over the sphere

\begin{align}
\label{eq:problem_vu}
\min_{\mathbf{x}} \mathbf{x}^\top  \mathbf{Bx}- \mathbf{b}^\top\mathbf{x}
\quad  \text{ s.t.} & \quad \left\lVert \mathbf{x} \right\rVert_2^2 = 1
\end{align}

with the matrix $\mathbf{B}\in\mathbb{R}^{m\times m}$ assumed symmetric but not positive semi-definite, hence a non-convex objective function. Upon considering the corresponding Lagrangian function, with $\nu$ denoting the Lagrange multiplier, the authors prove the following results, which also constitute building blocks in our analysis. The eigenvalues of $\mathbf{A}$ are given by $ \lambda_{min}(\mathbf{B}) \leq \lambda_{m-1} \leq \ldots \leq \lambda_1 \leq \lambda_{max}(\mathbf{B})$.

(Stationary conditions). The vector $\mathbf{x}_{*}$  is a stationary point of problem (<ref>) if and only if $\mathbf{x}_{*} \in \mathcal{S}^{m-1}=\{\mathbf{x}\in\mathbb{R}^m:\lVert \mathbf{x}\rVert=1\} $ and there exists a constant
$ \nu(\mathbf{x}_{*}) $
such that $\mathbf{r}_{*} = A \mathbf{x}_{*} - b = \nu(\mathbf{x}_{*}) \cdot   \mathbf{x}_{*} $.

A stationary point $\mathbf{x}_{*}$ of problem (<ref>) is a strict local minimum if and only if
$ \nu(\mathbf{x}_{*})  < \lambda_{m-1}(\mathbf{x}_{*})$. Furthermore, $\mathbf{x}_{*}$  is a global minimizer of problem (<ref>) if and only if
$ \nu(\mathbf{x}_{*}) \leq \lambda_{min}(\mathbf{B}). $

The following result establishes that
Projected Gradient Descent (PGD)  converges to a local minimum at an asymptotic linear rate $\rho_{\beta}$.

The vector $\mathbf{x}_{*}$ is a strict local minimum of problem (<ref>), i.e. $ \nu < \lambda_{m-1}$, if and only if there exists $ \beta >0 $ such that Algorithm 1 [Projected Gradient Descent (PGD)] with step size $\alpha$ converges locally uniformly to $\mathbf{x}_{*}$. Furthermore, for any step size $ \beta >0 $  such that $\beta(\lambda_1 + \nu)<2$, the sequence $\{ \mathbf{x}^{(t)} \}$  satisfies

\begin{equation*}
\lVert \mathbf{x}^{(t)} - \mathbf{x}_{*} \rVert
\leq M \lVert \mathbf{x}^{(0)} - \mathbf{x}_{*} \rVert  \left(  \rho_{\alpha} + o(1) \right)^t,
\end{equation*}

for some constant $M>0$ and $\rho_{\beta} = \max_{1 \leq i \leq m-1} \frac{| 1- \beta \lambda_i |}{ 1- \beta \nu }. $

§ DETAILED SUMMARY STATISTICS

Table <ref> gives the number of nodes ($n$), the number of directed edges ($|\mathcal{E}|$), the number of reciprocal edges ($|\mathcal{E}^r|$) (self-loops are counted once and for $ u \ne v$, a reciprocal edge $u\rightarrow v, v\rightarrow u$ is counted twice) as well as their percentage among all edges, for the real-world networks, illustrating the variability in network size and density (defined as ${|\mathcal{E}|}/[{n(n-1)}]$).
As we do not have input features available, we use the eigengap of the Hermitian matrix $(\mathbf{A}-\mathbf{A}^\top)\cdot i,$ where $\mathbf{A}$ is the adjacency matrix and $i$
the imaginary unit, introduced in [Cucuringu et al., 2020], to determine the value $K,$ which is assumed to be the number of clusters if we are solving a clustering problem.
We then stack the real and imaginary parts of the top $K$ eigenvectors of $(\mathbf{A}-\mathbf{A}^\top)\cdot i$ into $2K$-dimensional input features for GNNs. We also report the embedding dimension $d$ used in the experiments, for each of the data sets.

Summary statistics
for the real-world networks.

Data                    $n$      $|\mathcal{E}|$   density   $|\mathcal{E}^r|$   $\frac{|\mathcal{E}^r|}{|\mathcal{E}|}$(%)   $K$   $d$
HeadToHead   602   5010   1.38e-02   464   9.26   48   32

Basketball (1985)   282   2904   3.66e-02   998   34.37   20   16

Basketball finer (1985)   282   4814   6.08e-02   4814   100.00   20   16

Basketball (1986)   283   2937   3.68e-02   1014   34.53   20   16

Basketball finer (1986)   283   4862   6.09e-02   4862   100.00   20   16

Basketball (1987)   290   3045   3.63e-02   1012   33.23   20   16

Basketball finer (1987)   290   5088   6.07e-02   5088   100.00   20   16

Basketball (1988)   290   3099   3.70e-02   1034   33.37   20   16

Basketball finer (1988)   290   5170   6.17e-02   5170   100.00   20   16

Basketball (1989)   293   3162   3.70e-02   1014   32.07   20   16

Basketball finer (1989)   293   5318   6.22e-02   5318   100.00   20   16

Basketball (1990)   292   3192   3.76e-02   1042   32.64   20   16

Basketball finer (1990)   292   5350   6.30e-02   5350   100.00   20   16

Basketball (1991)   295   3218   3.71e-02   1018   31.63   20   16

Basketball finer (1991)   295   5420   6.25e-02   5420   100.00   20   16

Basketball (1992)   298   3238   3.66e-02   1036   32.00   20   16

Basketball finer (1992)   298   5444   6.15e-02   5444   100.00   20   16

Basketball (1993)   298   3088   3.49e-02   1024   33.16   20   16

Basketball finer (1993)   298   5160   5.83e-02   5160   100.00   20   16

Basketball (1994)   301   3144   3.48e-02   1044   33.21   20   16

Basketball finer (1994)   301   5252   5.82e-02   5252   100.00   20   16

Basketball (1995)   302   3182   3.50e-02   1034   32.50   20   16

Basketball finer (1995)   302   5336   5.87e-02   5336   100.00   20   16

Basketball (1996)   305   3256   3.51e-02   1026   31.51   20   16

Basketball finer (1996)   305   5498   5.93e-02   5498   100.00   20   16

Basketball (1997)   305   3333   3.59e-02   1044   31.32   20   16

Basketball finer (1997)   305   5628   6.07e-02   5628   100.00   20   16

Basketball (1998)   306   3321   3.56e-02   966   29.09   20   16

Basketball finer (1998)   306   5684   6.09e-02   5684   100.00   20   16

Basketball (1999)   310   3385   3.53e-02   998   29.48   20   16

Basketball finer (1999)   310   5788   6.04e-02   5788   100.00   20   16

Basketball (2000)   318   3475   3.45e-02   852   24.52   20   16

Basketball finer (2000)   318   6274   6.22e-02   6274   100.00   20   16

Basketball (2001)   318   3405   3.38e-02   904   26.55   20   16

Basketball finer (2001)   318   6116   6.07e-02   6116   100.00   20   16

Basketball (2002)   321   3505   3.41e-02   976   27.85   20   16

Basketball finer (2002)   321   6192   6.03e-02   6192   100.00   20   16

Basketball (2003)   327   3560   3.34e-02   954   26.80   20   16

Basketball finer (2003)   327   6356   5.96e-02   6356   100.00   20   16

Basketball (2004)   326   3527   3.33e-02   952   26.99   20   16

Basketball finer (2004)   326   6316   5.96e-02   6316   100.00   20   16

Basketball (2005)   330   3622   3.34e-02   946   26.12   20   16

Basketball finer (2005)   330   6476   5.96e-02   6476   100.00   20   16

Basketball (2006)   334   3695   3.32e-02   924   25.01   20   16

Basketball finer (2006)   334   6680   6.01e-02   6680   100.00   20   16

Basketball (2007)   336   3974   3.53e-02   976   24.56   20   16

Basketball finer (2007)   336   7186   6.38e-02   7186   100.00   20   16

Basketball (2008)   342   4051   3.47e-02   972   23.99   20   16

Basketball finer (2008)   342   7386   6.33e-02   7386   100.00   20   16

Basketball (2009)   347   4155   3.46e-02   1046   25.17   20   16

Basketball finer (2009)   347   7478   6.23e-02   7478   100.00   20   16

Basketball (2010)   347   4133   3.44e-02   916   22.16   20   16

Basketball finer (2010)   347   7538   6.28e-02   7538   100.00   20   16

Basketball (2011)   345   4086   3.44e-02   950   23.25   20   16

Basketball finer (2011)   345   7504   6.32e-02   7504   100.00   20   16

Basketball (2012)   345   4126   3.48e-02   950   23.02   20   16

Basketball finer (2012)   345   7580   6.39e-02   7580   100.00   20   16

Basketball (2013)   347   4153   3.46e-02   960   23.12   20   16

Basketball finer (2013)   347   7616   6.34e-02   7616   100.00   20   16

Basketball (2014)   351   4196   3.42e-02   1008   24.02   20   16

Basketball finer (2014)   351   7650   6.23e-02   7650   100.00   20   16

Football (2009)   20   215   5.66e-01   78   36.28   9   8

Football finer (2009)   20   380   1.00e+00   380   100.00   9   8

Football (2010)   20   219   5.76e-01   86   39.27   9   8

Football finer (2010)   20   380   1.00e+00   380   100.00   9   8

Football (2011)   20   226   5.95e-01   92   40.71   9   8

Football finer (2011)   20   380   1.00e+00   380   100.00   9   8

Football (2012)   20   216   5.68e-01   86   39.81   9   8

Football finer (2012)   20   380   1.00e+00   380   100.00   9   8

Football (2013)   20   222   5.84e-01   82   36.94   9   8

Football finer (2013)   20   380   1.00e+00   380   100.00   9   8

Football (2014)   20   107   2.82e-01   0   0.00   9   8

Football finer (2014)   20   300   7.89e-01   300   100.00   9   8

Football(avg)   20   201   5.29e-01   71   32.17   9   8

Basketball(avg)   316   3506   3.51e-02   986   28.57   20   16

Football finer(avg)   20   367   9.65e-01   367   100   9   8

Basketball finer(avg)   316   6139   6.12e-02   6139   100   20   16

Animal   21   193   4.60e-01   64   33.16   3   8

Finance   1315   1729225   1.00e+00   1729225   100   20   64

Faculty:Business   113   1787   1.41e-01   0   0.00   5   16

Faculty:CS   206   1407   3.33e-02   0   0.00   9   16

Faculty:History   145   1204   5.77e-02   0   0.00   12   16

§ FULL RESULT TABLES

§.§ Results on Individual Digraphs and $\mathcal{L}_\text{upset, ratio}$

Tables <ref>, <ref> and <ref> provide detailed comparison on both $\mathcal{L}_\text{upset, simple}$, $\mathcal{L}_\text{upset, naive}$ and $\mathcal{L}_\text{upset, ratio}$ for all time-series match data, where Table <ref> additionally provides $\mathcal{L}_\text{upset, ratio}$ results on other real-world data sets. Again the best-performing variants of the non-proximal and of the proximal method are reported. The proximal method does not perform as well as the non-proximal method in terms of $\mathcal{L}_\text{upset, ratio}$, perhaps partially due to the fact that outputs from SerialRank [Fogel et al., 2014] do not align well with skill level but rather
relate to relative ordering. It is also natural for GNNRank-N methods that are not motivated by SerialRank to perform well on this metric as $\mathcal{L}_\text{upset, ratio}$ is in the training loss function. Therefore, here we only
present the results on $\mathcal{L}_\text{upset, ratio}$ but do not
draw conclusions on which method outperforms others.

Result table on $\mathcal{L}_\text{upset, simple}$ for individual directed graphs, averaged over 10 runs, and plus/minus one standard deviation. The best is marked in bold red while the second best is highlighted in underline blue. When MVR could not generate results after a week, we omit the results and fill in “NAN" here.

Data      SpringRank     SyncRank     SerialRank     BTL     DavidScore     Eig.Cent.     PageRank     RankCent.    SVD_RS     SVD_NRS   MVR       GNNRank-N     GNNRank-P

HeadToHead     1.00$\pm$0.00     1.94$\pm$0.00     2.01$\pm$0.00     1.12$\pm$0.01     1.16$\pm$0.00     1.47$\pm$0.00     1.36$\pm$0.00     2.00$\pm$0.02     1.79$\pm$0.00     1.42$\pm$0.00     nan$\pm$nan     0.99$\pm$0.00     0.96$\pm$0.00

Finance     1.63$\pm$0.00     1.98$\pm$0.00     1.61$\pm$0.00     1.78$\pm$0.01     1.63$\pm$0.00     1.74$\pm$0.00     1.75$\pm$0.00     1.88$\pm$0.00     1.64$\pm$0.00     1.64$\pm$0.00     nan$\pm$nan     1.00$\pm$0.00     1.00$\pm$0.00

Animal     0.50$\pm$0.00     1.62$\pm$0.24     1.98$\pm$0.48     0.45$\pm$0.00     0.33$\pm$0.00     0.55$\pm$0.00     0.63$\pm$0.00     1.96$\pm$0.00     1.03$\pm$0.00     0.53$\pm$0.00     2.02$\pm$0.32     0.41$\pm$0.09     0.25$\pm$0.00

Faculty: Business     0.41$\pm$0.00     0.83$\pm$0.00     1.19$\pm$0.00     0.41$\pm$0.01     0.49$\pm$0.00     0.49$\pm$0.00     0.49$\pm$0.00     2.01$\pm$0.03     0.68$\pm$0.00     0.46$\pm$0.00     0.78$\pm$0.05     0.38$\pm$0.01     0.36$\pm$0.00

Faculty: CS     0.33$\pm$0.00     0.98$\pm$0.10     1.40$\pm$0.00     0.34$\pm$0.01     0.61$\pm$0.00     0.51$\pm$0.00     0.44$\pm$0.00     1.99$\pm$0.27     0.93$\pm$0.00     0.58$\pm$0.00     0.87$\pm$0.09     0.33$\pm$0.03     0.32$\pm$0.00

Faculty: History     0.32$\pm$0.00     0.57$\pm$0.00     2.16$\pm$0.80     0.30$\pm$0.01     0.57$\pm$0.00     0.40$\pm$0.00     0.37$\pm$0.00     2.13$\pm$0.30     0.95$\pm$0.00     0.38$\pm$0.00     0.84$\pm$0.17     0.28$\pm$0.01     0.30$\pm$0.01

Basketball(1985)     0.76$\pm$0.00     1.62$\pm$0.00     2.11$\pm$0.00     0.93$\pm$0.08     0.75$\pm$0.00     0.89$\pm$0.00     0.91$\pm$0.00     1.92$\pm$0.00     1.00$\pm$0.00     0.86$\pm$0.00     nan$\pm$nan     0.77$\pm$0.01     0.71$\pm$0.00

Basketball(1986)     0.78$\pm$0.00     1.79$\pm$0.00     1.99$\pm$0.00     0.96$\pm$0.02     0.78$\pm$0.00     0.89$\pm$0.00     0.88$\pm$0.00     1.96$\pm$0.00     1.09$\pm$0.00     0.86$\pm$0.00     nan$\pm$nan     0.78$\pm$0.01     0.69$\pm$0.00

Basketball(1987)     0.82$\pm$0.00     1.79$\pm$0.00     1.88$\pm$0.00     0.99$\pm$0.02     0.85$\pm$0.00     0.99$\pm$0.00     0.90$\pm$0.00     1.94$\pm$0.00     0.99$\pm$0.00     0.91$\pm$0.00     nan$\pm$nan     0.84$\pm$0.01     0.77$\pm$0.01

Basketball(1988)     0.74$\pm$0.00     1.66$\pm$0.00     1.91$\pm$0.00     0.92$\pm$0.03     0.77$\pm$0.00     0.87$\pm$0.00     0.85$\pm$0.00     1.93$\pm$0.00     0.97$\pm$0.00     0.83$\pm$0.00     nan$\pm$nan     0.76$\pm$0.01     0.70$\pm$0.00

Basketball(1989)     0.75$\pm$0.00     1.74$\pm$0.00     1.86$\pm$0.00     0.94$\pm$0.02     0.77$\pm$0.00     0.82$\pm$0.00     0.85$\pm$0.00     1.87$\pm$0.00     0.98$\pm$0.00     0.90$\pm$0.00     nan$\pm$nan     0.78$\pm$0.02     0.70$\pm$0.00

Basketball(1990)     0.75$\pm$0.00     1.68$\pm$0.00     1.94$\pm$0.00     0.89$\pm$0.08     0.78$\pm$0.00     0.90$\pm$0.00     0.88$\pm$0.00     1.95$\pm$0.00     0.91$\pm$0.00     0.85$\pm$0.00     nan$\pm$nan     0.77$\pm$0.02     0.70$\pm$0.00

Basketball(1991)     0.80$\pm$0.00     1.80$\pm$0.00     2.03$\pm$0.00     0.92$\pm$0.07     0.77$\pm$0.00     0.86$\pm$0.00     0.84$\pm$0.00     1.95$\pm$0.00     1.00$\pm$0.00     0.90$\pm$0.00     nan$\pm$nan     0.78$\pm$0.01     0.70$\pm$0.00

Basketball(1992)     0.75$\pm$0.00     1.74$\pm$0.00     1.89$\pm$0.00     0.86$\pm$0.10     0.72$\pm$0.00     0.84$\pm$0.00     0.80$\pm$0.00     2.00$\pm$0.00     0.96$\pm$0.00     0.84$\pm$0.00     nan$\pm$nan     0.74$\pm$0.01     0.67$\pm$0.00

Basketball(1993)     0.75$\pm$0.00     1.68$\pm$0.00     2.04$\pm$0.00     0.88$\pm$0.06     0.74$\pm$0.00     0.83$\pm$0.00     0.85$\pm$0.00     1.93$\pm$0.00     0.99$\pm$0.00     0.86$\pm$0.00     nan$\pm$nan     0.76$\pm$0.02     0.68$\pm$0.01

Basketball(1994)     0.74$\pm$0.00     1.67$\pm$0.00     2.00$\pm$0.00     0.77$\pm$0.09     0.74$\pm$0.00     0.82$\pm$0.00     0.83$\pm$0.00     2.04$\pm$0.00     0.90$\pm$0.00     0.84$\pm$0.00     nan$\pm$nan     0.75$\pm$0.01     0.69$\pm$0.00

Basketball(1995)     0.77$\pm$0.00     1.78$\pm$0.00     1.88$\pm$0.00     0.84$\pm$0.10     0.78$\pm$0.00     0.83$\pm$0.00     0.87$\pm$0.00     2.02$\pm$0.00     0.94$\pm$0.00     0.86$\pm$0.00     nan$\pm$nan     0.78$\pm$0.01     0.72$\pm$0.01

Basketball(1996)     0.82$\pm$0.00     1.67$\pm$0.00     2.05$\pm$0.00     0.96$\pm$0.07     0.81$\pm$0.00     0.90$\pm$0.00     0.92$\pm$0.00     2.05$\pm$0.00     1.08$\pm$0.00     0.95$\pm$0.00     nan$\pm$nan     0.84$\pm$0.01     0.77$\pm$0.01

Basketball(1997)     0.81$\pm$0.00     1.72$\pm$0.00     1.95$\pm$0.00     0.97$\pm$0.02     0.83$\pm$0.00     0.91$\pm$0.00     0.90$\pm$0.00     1.89$\pm$0.00     0.96$\pm$0.00     0.92$\pm$0.00     nan$\pm$nan     0.83$\pm$0.01     0.76$\pm$0.01

Basketball(1998)     0.77$\pm$0.00     1.69$\pm$0.00     1.91$\pm$0.00     0.96$\pm$0.03     0.79$\pm$0.00     0.90$\pm$0.00     0.85$\pm$0.00     1.92$\pm$0.00     0.96$\pm$0.00     0.89$\pm$0.00     nan$\pm$nan     0.80$\pm$0.01     0.74$\pm$0.01

Basketball(1999)     0.83$\pm$0.00     1.56$\pm$0.00     2.02$\pm$0.00     0.97$\pm$0.06     0.81$\pm$0.00     0.93$\pm$0.00     0.94$\pm$0.00     1.90$\pm$0.00     1.16$\pm$0.00     0.95$\pm$0.00     nan$\pm$nan     0.84$\pm$0.01     0.74$\pm$0.00

Basketball(2000)     0.84$\pm$0.00     1.77$\pm$0.00     1.97$\pm$0.00     0.98$\pm$0.02     0.86$\pm$0.00     0.91$\pm$0.00     0.91$\pm$0.00     1.91$\pm$0.00     1.11$\pm$0.00     0.94$\pm$0.00     nan$\pm$nan     0.82$\pm$0.01     0.77$\pm$0.00

Basketball(2001)     0.75$\pm$0.00     1.73$\pm$0.00     2.03$\pm$0.00     0.91$\pm$0.07     0.78$\pm$0.00     0.88$\pm$0.00     0.84$\pm$0.00     2.00$\pm$0.00     1.05$\pm$0.00     0.94$\pm$0.00     nan$\pm$nan     0.77$\pm$0.01     0.71$\pm$0.00

Basketball(2002)     0.80$\pm$0.00     1.69$\pm$0.00     1.91$\pm$0.00     0.92$\pm$0.05     0.80$\pm$0.00     0.85$\pm$0.00     0.91$\pm$0.00     1.94$\pm$0.00     1.06$\pm$0.00     0.88$\pm$0.00     nan$\pm$nan     0.80$\pm$0.01     0.73$\pm$0.00

Basketball(2003)     0.81$\pm$0.00     1.85$\pm$0.00     2.05$\pm$0.00     0.95$\pm$0.07     0.80$\pm$0.00     0.94$\pm$0.00     0.94$\pm$0.00     1.93$\pm$0.00     0.99$\pm$0.00     0.94$\pm$0.00     nan$\pm$nan     0.83$\pm$0.01     0.78$\pm$0.00

Basketball(2004)     0.75$\pm$0.00     1.67$\pm$0.00     2.00$\pm$0.11     0.89$\pm$0.07     0.75$\pm$0.00     0.85$\pm$0.00     0.87$\pm$0.00     1.95$\pm$0.00     0.92$\pm$0.00     0.86$\pm$0.00     nan$\pm$nan     0.77$\pm$0.01     0.69$\pm$0.00

Basketball(2005)     0.78$\pm$0.00     1.78$\pm$0.01     1.98$\pm$0.05     0.98$\pm$0.02     0.81$\pm$0.00     0.85$\pm$0.00     0.91$\pm$0.00     1.87$\pm$0.00     1.05$\pm$0.00     0.92$\pm$0.00     nan$\pm$nan     0.81$\pm$0.02     0.73$\pm$0.00

Basketball(2006)     0.81$\pm$0.00     1.78$\pm$0.00     2.00$\pm$0.00     0.84$\pm$0.08     0.77$\pm$0.00     0.86$\pm$0.00     0.89$\pm$0.00     1.99$\pm$0.00     1.03$\pm$0.00     0.91$\pm$0.00     nan$\pm$nan     0.82$\pm$0.01     0.74$\pm$0.00

Basketball(2007)     0.79$\pm$0.00     1.87$\pm$0.00     1.94$\pm$0.08     0.94$\pm$0.01     0.84$\pm$0.00     0.89$\pm$0.00     0.89$\pm$0.00     1.94$\pm$0.00     0.92$\pm$0.00     0.89$\pm$0.00     nan$\pm$nan     0.83$\pm$0.01     0.77$\pm$0.00

Basketball(2008)     0.82$\pm$0.00     1.75$\pm$0.00     2.01$\pm$0.00     0.90$\pm$0.07     0.80$\pm$0.00     0.90$\pm$0.00     0.93$\pm$0.00     1.92$\pm$0.00     0.98$\pm$0.00     0.90$\pm$0.00     nan$\pm$nan     0.83$\pm$0.01     0.78$\pm$0.00

Basketball(2009)     0.78$\pm$0.00     1.74$\pm$0.00     2.02$\pm$0.00     0.94$\pm$0.02     0.76$\pm$0.00     0.85$\pm$0.00     0.86$\pm$0.00     1.89$\pm$0.00     0.95$\pm$0.00     0.88$\pm$0.00     nan$\pm$nan     0.78$\pm$0.01     0.72$\pm$0.01

Basketball(2010)     0.79$\pm$0.00     1.55$\pm$0.00     1.97$\pm$0.00     0.85$\pm$0.10     0.77$\pm$0.00     0.92$\pm$0.00     0.91$\pm$0.00     2.03$\pm$0.00     0.93$\pm$0.00     0.91$\pm$0.00     nan$\pm$nan     0.82$\pm$0.01     0.71$\pm$0.00

Basketball(2011)     0.81$\pm$0.00     1.63$\pm$0.00     1.96$\pm$0.00     0.85$\pm$0.08     0.79$\pm$0.00     0.88$\pm$0.00     0.89$\pm$0.00     2.03$\pm$0.00     0.95$\pm$0.00     0.87$\pm$0.00     nan$\pm$nan     0.80$\pm$0.01     0.74$\pm$0.00

Basketball(2012)     0.76$\pm$0.00     1.81$\pm$0.00     1.97$\pm$0.00     0.88$\pm$0.08     0.77$\pm$0.00     0.85$\pm$0.00     0.84$\pm$0.00     1.96$\pm$0.00     0.90$\pm$0.00     0.85$\pm$0.00     nan$\pm$nan     0.78$\pm$0.01     0.69$\pm$0.00

Basketball(2013)     0.80$\pm$0.00     1.71$\pm$0.00     1.99$\pm$0.05     0.95$\pm$0.06     0.80$\pm$0.00     0.90$\pm$0.00     0.87$\pm$0.00     1.95$\pm$0.00     1.00$\pm$0.00     0.90$\pm$0.00     nan$\pm$nan     0.81$\pm$0.01     0.76$\pm$0.00

Basketball(2014)     0.80$\pm$0.00     1.72$\pm$0.00     2.06$\pm$0.00     0.87$\pm$0.09     0.79$\pm$0.00     0.88$\pm$0.00     0.91$\pm$0.00     1.94$\pm$0.00     1.01$\pm$0.00     0.87$\pm$0.00     nan$\pm$nan     0.83$\pm$0.01     0.75$\pm$0.00

Basketball finer(1985)     0.76$\pm$0.00     1.63$\pm$0.00     1.96$\pm$0.10     1.46$\pm$0.05     0.83$\pm$0.00     1.18$\pm$0.00     1.16$\pm$0.00     1.97$\pm$0.00     1.00$\pm$0.00     0.87$\pm$0.00     nan$\pm$nan     0.79$\pm$0.01     0.71$\pm$0.00

Basketball finer(1986)     0.77$\pm$0.00     1.81$\pm$0.00     1.99$\pm$0.00     1.42$\pm$0.06     0.84$\pm$0.00     1.16$\pm$0.00     1.15$\pm$0.00     1.99$\pm$0.00     1.09$\pm$0.00     0.86$\pm$0.00     nan$\pm$nan     0.81$\pm$0.01     0.69$\pm$0.00

Basketball finer(1987)     0.82$\pm$0.00     1.79$\pm$0.00     1.87$\pm$0.00     1.41$\pm$0.06     0.89$\pm$0.00     1.17$\pm$0.00     1.21$\pm$0.00     1.95$\pm$0.00     0.99$\pm$0.00     0.91$\pm$0.00     nan$\pm$nan     0.86$\pm$0.02     0.77$\pm$0.01

Basketball finer(1988)     0.78$\pm$0.00     1.79$\pm$0.00     1.90$\pm$0.00     1.43$\pm$0.10     0.84$\pm$0.00     1.23$\pm$0.00     1.19$\pm$0.00     1.97$\pm$0.00     0.97$\pm$0.00     0.83$\pm$0.00     nan$\pm$nan     0.80$\pm$0.01     0.70$\pm$0.01

Basketball finer(1989)     0.77$\pm$0.00     1.67$\pm$0.00     1.86$\pm$0.00     1.43$\pm$0.05     0.83$\pm$0.00     1.13$\pm$0.00     1.14$\pm$0.00     1.94$\pm$0.00     0.99$\pm$0.00     0.90$\pm$0.00     nan$\pm$nan     0.82$\pm$0.02     0.70$\pm$0.00

Basketball finer(1990)     0.79$\pm$0.00     1.67$\pm$0.00     1.93$\pm$0.00     1.45$\pm$0.05     0.82$\pm$0.00     1.28$\pm$0.00     1.17$\pm$0.00     1.98$\pm$0.00     0.91$\pm$0.00     0.84$\pm$0.00     nan$\pm$nan     0.80$\pm$0.02     0.71$\pm$0.00

Basketball finer(1991)     0.81$\pm$0.00     1.83$\pm$0.00     2.03$\pm$0.00     1.36$\pm$0.06     0.83$\pm$0.00     1.38$\pm$0.00     1.31$\pm$0.00     1.97$\pm$0.00     0.99$\pm$0.00     0.89$\pm$0.00     nan$\pm$nan     0.83$\pm$0.01     0.71$\pm$0.00

Basketball finer(1992)     0.73$\pm$0.00     1.72$\pm$0.00     1.88$\pm$0.00     1.33$\pm$0.06     0.77$\pm$0.00     1.26$\pm$0.00     1.21$\pm$0.00     1.87$\pm$0.00     0.95$\pm$0.00     0.84$\pm$0.00     nan$\pm$nan     0.75$\pm$0.02     0.67$\pm$0.00

Basketball finer(1993)     0.75$\pm$0.00     1.66$\pm$0.00     2.03$\pm$0.00     1.35$\pm$0.05     0.78$\pm$0.00     1.18$\pm$0.00     1.10$\pm$0.00     1.97$\pm$0.00     0.98$\pm$0.00     0.86$\pm$0.00     nan$\pm$nan     0.80$\pm$0.01     0.68$\pm$0.01

Basketball finer(1994)     0.74$\pm$0.00     1.69$\pm$0.00     2.01$\pm$0.00     1.35$\pm$0.08     0.78$\pm$0.00     1.23$\pm$0.00     1.10$\pm$0.00     1.94$\pm$0.00     0.90$\pm$0.00     0.83$\pm$0.00     nan$\pm$nan     0.77$\pm$0.01     0.67$\pm$0.00

Basketball finer(1995)     0.79$\pm$0.00     1.78$\pm$0.00     1.89$\pm$0.00     1.35$\pm$0.06     0.83$\pm$0.00     1.19$\pm$0.00     1.13$\pm$0.00     1.92$\pm$0.01     0.95$\pm$0.00     0.87$\pm$0.00     nan$\pm$nan     0.78$\pm$0.01     0.72$\pm$0.01

Basketball finer(1996)     0.81$\pm$0.00     1.67$\pm$0.00     1.95$\pm$0.00     1.44$\pm$0.06     0.88$\pm$0.00     1.22$\pm$0.00     1.20$\pm$0.00     1.94$\pm$0.00     1.08$\pm$0.00     0.95$\pm$0.00     nan$\pm$nan     0.86$\pm$0.01     0.77$\pm$0.00

Basketball finer(1997)     0.83$\pm$0.00     1.77$\pm$0.00     1.94$\pm$0.00     1.40$\pm$0.04     0.86$\pm$0.00     1.19$\pm$0.00     1.16$\pm$0.00     2.05$\pm$0.00     0.96$\pm$0.00     0.92$\pm$0.00     nan$\pm$nan     0.85$\pm$0.01     0.75$\pm$0.01

Basketball finer(1998)     0.78$\pm$0.00     1.70$\pm$0.00     1.92$\pm$0.00     1.36$\pm$0.07     0.83$\pm$0.00     1.14$\pm$0.00     1.13$\pm$0.00     1.91$\pm$0.00     0.97$\pm$0.00     0.90$\pm$0.00     nan$\pm$nan     0.82$\pm$0.02     0.73$\pm$0.01

Basketball finer(1999)     0.81$\pm$0.00     1.64$\pm$0.00     2.02$\pm$0.00     1.38$\pm$0.07     0.86$\pm$0.00     1.17$\pm$0.00     1.11$\pm$0.00     1.99$\pm$0.00     1.17$\pm$0.00     0.94$\pm$0.00     nan$\pm$nan     0.86$\pm$0.01     0.73$\pm$0.00

Basketball finer(2000)     0.84$\pm$0.00     1.75$\pm$0.00     1.97$\pm$0.00     1.39$\pm$0.05     0.90$\pm$0.00     1.26$\pm$0.00     1.18$\pm$0.00     1.92$\pm$0.00     1.12$\pm$0.00     0.95$\pm$0.00     nan$\pm$nan     0.88$\pm$0.01     0.78$\pm$0.00

Basketball finer(2001)     0.81$\pm$0.00     1.69$\pm$0.00     2.06$\pm$0.00     1.41$\pm$0.06     0.86$\pm$0.00     1.25$\pm$0.00     1.18$\pm$0.00     2.03$\pm$0.00     1.08$\pm$0.00     0.97$\pm$0.00     nan$\pm$nan     0.86$\pm$0.01     0.73$\pm$0.00

Basketball finer(2002)     0.87$\pm$0.00     1.75$\pm$0.00     1.86$\pm$0.00     1.43$\pm$0.08     0.89$\pm$0.00     1.20$\pm$0.00     1.13$\pm$0.00     2.03$\pm$0.00     1.07$\pm$0.00     0.92$\pm$0.00     nan$\pm$nan     0.83$\pm$0.01     0.77$\pm$0.01

Basketball finer(2003)     0.87$\pm$0.00     1.78$\pm$0.00     1.98$\pm$0.07     1.46$\pm$0.09     0.91$\pm$0.00     1.18$\pm$0.00     1.14$\pm$0.00     2.00$\pm$0.00     1.02$\pm$0.00     0.95$\pm$0.00     nan$\pm$nan     0.88$\pm$0.02     0.78$\pm$0.00

Basketball finer(2004)     0.77$\pm$0.00     1.71$\pm$0.06     1.87$\pm$0.00     1.41$\pm$0.06     0.80$\pm$0.00     1.17$\pm$0.00     1.13$\pm$0.00     1.98$\pm$0.02     0.95$\pm$0.00     0.88$\pm$0.00     nan$\pm$nan     0.84$\pm$0.01     0.71$\pm$0.01

Basketball finer(2005)     0.84$\pm$0.00     1.82$\pm$0.00     1.93$\pm$0.00     1.38$\pm$0.06     0.88$\pm$0.00     1.14$\pm$0.00     1.09$\pm$0.00     2.00$\pm$0.00     1.08$\pm$0.00     0.95$\pm$0.00     nan$\pm$nan     0.86$\pm$0.01     0.75$\pm$0.01

Basketball finer(2006)     0.86$\pm$0.00     1.76$\pm$0.00     1.97$\pm$0.00     1.40$\pm$0.07     0.85$\pm$0.00     1.21$\pm$0.00     1.11$\pm$0.00     1.96$\pm$0.00     1.06$\pm$0.00     0.94$\pm$0.00     nan$\pm$nan     0.88$\pm$0.02     0.76$\pm$0.00

Basketball finer(2007)     0.86$\pm$0.00     1.85$\pm$0.00     1.97$\pm$0.14     1.39$\pm$0.05     0.93$\pm$0.00     1.15$\pm$0.00     1.09$\pm$0.00     1.92$\pm$0.00     0.95$\pm$0.00     0.93$\pm$0.00     nan$\pm$nan     0.87$\pm$0.01     0.80$\pm$0.01

Basketball finer(2008)     0.85$\pm$0.00     1.72$\pm$0.00     1.98$\pm$0.00     1.36$\pm$0.08     0.88$\pm$0.00     1.20$\pm$0.00     1.13$\pm$0.00     1.96$\pm$0.00     0.99$\pm$0.00     0.91$\pm$0.00     nan$\pm$nan     0.86$\pm$0.02     0.78$\pm$0.00

Basketball finer(2009)     0.84$\pm$0.00     1.71$\pm$0.00     2.00$\pm$0.04     1.37$\pm$0.04     0.90$\pm$0.00     1.17$\pm$0.00     1.12$\pm$0.00     2.06$\pm$0.00     0.99$\pm$0.00     0.91$\pm$0.00     nan$\pm$nan     0.85$\pm$0.01     0.75$\pm$0.00

Basketball finer(2010)     0.82$\pm$0.00     1.68$\pm$0.00     1.98$\pm$0.00     1.34$\pm$0.06     0.84$\pm$0.00     1.10$\pm$0.00     1.13$\pm$0.00     1.97$\pm$0.00     0.94$\pm$0.00     0.92$\pm$0.00     nan$\pm$nan     0.85$\pm$0.01     0.75$\pm$0.00

Basketball finer(2011)     0.85$\pm$0.00     1.65$\pm$0.00     1.96$\pm$0.00     1.36$\pm$0.06     0.87$\pm$0.00     1.12$\pm$0.00     1.14$\pm$0.00     2.01$\pm$0.00     0.96$\pm$0.00     0.89$\pm$0.00     nan$\pm$nan     0.87$\pm$0.01     0.77$\pm$0.00

Basketball finer(2012)     0.80$\pm$0.00     1.68$\pm$0.00     1.97$\pm$0.00     1.37$\pm$0.07     0.83$\pm$0.00     1.17$\pm$0.00     1.10$\pm$0.00     1.91$\pm$0.00     0.93$\pm$0.00     0.89$\pm$0.00     nan$\pm$nan     0.83$\pm$0.01     0.74$\pm$0.01

Basketball finer(2013)     0.83$\pm$0.00     1.73$\pm$0.00     2.06$\pm$0.00     1.37$\pm$0.07     0.88$\pm$0.00     1.15$\pm$0.00     1.13$\pm$0.00     1.97$\pm$0.00     1.01$\pm$0.00     0.92$\pm$0.00     nan$\pm$nan     0.85$\pm$0.00     0.78$\pm$0.01

Basketball finer(2014)     0.84$\pm$0.00     1.77$\pm$0.19     2.07$\pm$0.00     1.42$\pm$0.09     0.86$\pm$0.00     1.18$\pm$0.00     1.13$\pm$0.00     1.97$\pm$0.00     1.02$\pm$0.00     0.88$\pm$0.00     nan$\pm$nan     0.87$\pm$0.01     0.78$\pm$0.00

Football(2009)     0.61$\pm$0.00     1.44$\pm$0.44     0.93$\pm$0.00     0.67$\pm$0.07     0.80$\pm$0.00     0.93$\pm$0.00     1.05$\pm$0.00     1.80$\pm$0.09     0.80$\pm$0.00     0.66$\pm$0.00     1.55$\pm$0.16     0.75$\pm$0.06     0.61$\pm$0.00

Football(2010)     1.19$\pm$0.00     1.81$\pm$0.15     1.54$\pm$0.00     1.18$\pm$0.04     1.29$\pm$0.00     1.34$\pm$0.00     1.37$\pm$0.00     1.84$\pm$0.13     1.24$\pm$0.00     1.17$\pm$0.00     1.94$\pm$0.20     0.90$\pm$0.02     0.95$\pm$0.05

Football(2011)     0.80$\pm$0.00     1.57$\pm$0.37     0.95$\pm$0.00     0.86$\pm$0.04     0.87$\pm$0.00     0.99$\pm$0.00     1.02$\pm$0.00     1.60$\pm$0.00     0.92$\pm$0.00     0.85$\pm$0.00     1.80$\pm$0.19     0.83$\pm$0.03     0.80$\pm$0.01

Football(2012)     0.97$\pm$0.00     1.50$\pm$0.03     1.41$\pm$0.00     0.99$\pm$0.05     0.89$\pm$0.00     0.94$\pm$0.00     0.99$\pm$0.00     1.65$\pm$0.00     1.02$\pm$0.00     0.86$\pm$0.00     1.73$\pm$0.18     0.75$\pm$0.03     0.80$\pm$0.08

Football(2013)     0.75$\pm$0.00     1.64$\pm$0.10     0.78$\pm$0.00     0.77$\pm$0.05     0.68$\pm$0.00     0.92$\pm$0.00     0.87$\pm$0.00     1.93$\pm$0.09     0.90$\pm$0.00     0.75$\pm$0.00     1.59$\pm$0.11     0.64$\pm$0.04     0.56$\pm$0.00

Football(2014)     1.12$\pm$0.00     1.81$\pm$0.18     1.57$\pm$0.00     1.16$\pm$0.01     1.09$\pm$0.00     1.27$\pm$0.00     1.20$\pm$0.00     1.83$\pm$0.11     1.12$\pm$0.00     1.08$\pm$0.00     1.72$\pm$0.20     0.96$\pm$0.12     0.96$\pm$0.07

Football finer(2009)     0.71$\pm$0.00     1.78$\pm$0.00     0.93$\pm$0.00     0.79$\pm$0.10     0.71$\pm$0.00     1.05$\pm$0.00     1.10$\pm$0.00     1.89$\pm$0.05     0.80$\pm$0.00     0.66$\pm$0.00     1.91$\pm$0.17     0.76$\pm$0.18     0.65$\pm$0.02

Football finer(2010)     1.29$\pm$0.00     1.63$\pm$0.02     1.44$\pm$0.00     1.31$\pm$0.09     1.29$\pm$0.00     1.37$\pm$0.00     1.49$\pm$0.00     1.96$\pm$0.00     1.24$\pm$0.00     1.17$\pm$0.00     2.11$\pm$0.01     1.00$\pm$0.01     0.99$\pm$0.02

Football finer(2011)     0.87$\pm$0.00     1.58$\pm$0.02     1.07$\pm$0.00     0.93$\pm$0.04     0.92$\pm$0.00     1.02$\pm$0.00     1.14$\pm$0.00     1.87$\pm$0.00     0.92$\pm$0.00     0.85$\pm$0.00     2.14$\pm$0.02     0.92$\pm$0.16     0.84$\pm$0.02

Football finer(2012)     0.97$\pm$0.00     1.76$\pm$0.18     1.10$\pm$0.00     0.99$\pm$0.05     0.92$\pm$0.00     1.10$\pm$0.00     1.20$\pm$0.00     2.03$\pm$0.06     1.02$\pm$0.00     0.86$\pm$0.00     2.15$\pm$0.01     0.93$\pm$0.07     0.86$\pm$0.03

Football finer(2013)     0.90$\pm$0.00     1.57$\pm$0.01     0.87$\pm$0.00     0.85$\pm$0.06     0.73$\pm$0.00     0.99$\pm$0.00     1.07$\pm$0.00     2.01$\pm$0.00     0.90$\pm$0.00     0.75$\pm$0.00     1.94$\pm$0.14     0.73$\pm$0.19     0.57$\pm$0.01

Football finer(2014)     1.16$\pm$0.00     1.74$\pm$0.04     1.57$\pm$0.00     1.19$\pm$0.04     1.05$\pm$0.00     1.23$\pm$0.00     1.23$\pm$0.00     1.68$\pm$0.00     1.12$\pm$0.00     1.08$\pm$0.00     2.09$\pm$0.17     1.00$\pm$0.00     1.00$\pm$0.03

Result table on $\mathcal{L}_\text{upset, naive}$ for individual directed graphs, averaged over 10 runs, and plus/minus one standard deviation. The best is marked in bold red while the second best is highlighted in underline blue. When MVR could not generate results after a week, we omit the results and fill in “NAN" here.

Data      SpringRank     SyncRank     SerialRank     BTL     DavidScore     Eig.Cent.     PageRank     RankCent.    SVD_RS     SVD_NRS   MVR       GNNRank-N     GNNRank-P

HeadToHead     0.25$\pm$0.00     0.48$\pm$0.00     0.50$\pm$0.00     0.28$\pm$0.00     0.29$\pm$0.00     0.37$\pm$0.00     0.34$\pm$0.00     0.50$\pm$0.01     0.45$\pm$0.00     0.36$\pm$0.00     nan$\pm$nan     0.27$\pm$0.00     0.24$\pm$0.00

Finance     0.41$\pm$0.00     0.50$\pm$0.00     0.40$\pm$0.00     0.45$\pm$0.00     0.41$\pm$0.00     0.44$\pm$0.00     0.44$\pm$0.00     0.47$\pm$0.00     0.41$\pm$0.00     0.41$\pm$0.00     nan$\pm$nan     0.41$\pm$0.00     0.40$\pm$0.00

Animal     0.13$\pm$0.00     0.40$\pm$0.06     0.58$\pm$0.11     0.11$\pm$0.00     0.08$\pm$0.00     0.14$\pm$0.00     0.16$\pm$0.00     0.49$\pm$0.00     0.26$\pm$0.00     0.13$\pm$0.00     0.50$\pm$0.08     0.10$\pm$0.02     0.06$\pm$0.00

Faculty: Business     0.10$\pm$0.00     0.21$\pm$0.00     0.30$\pm$0.00     0.10$\pm$0.00     0.12$\pm$0.00     0.12$\pm$0.00     0.12$\pm$0.00     0.50$\pm$0.01     0.17$\pm$0.00     0.12$\pm$0.00     0.19$\pm$0.01     0.10$\pm$0.00     0.09$\pm$0.00

Faculty: CS     0.08$\pm$0.00     0.24$\pm$0.02     0.35$\pm$0.00     0.08$\pm$0.00     0.15$\pm$0.00     0.13$\pm$0.00     0.11$\pm$0.00     0.50$\pm$0.07     0.23$\pm$0.00     0.15$\pm$0.00     0.22$\pm$0.02     0.08$\pm$0.01     0.08$\pm$0.00

Faculty: History     0.08$\pm$0.00     0.14$\pm$0.00     0.54$\pm$0.20     0.08$\pm$0.00     0.15$\pm$0.00     0.10$\pm$0.00     0.09$\pm$0.00     0.53$\pm$0.08     0.24$\pm$0.00     0.10$\pm$0.00     0.21$\pm$0.04     0.07$\pm$0.00     0.07$\pm$0.00

Basketball(1985)     0.19$\pm$0.00     0.40$\pm$0.00     0.53$\pm$0.00     0.23$\pm$0.02     0.19$\pm$0.00     0.22$\pm$0.00     0.23$\pm$0.00     0.48$\pm$0.00     0.25$\pm$0.00     0.22$\pm$0.00     nan$\pm$nan     0.19$\pm$0.00     0.18$\pm$0.00

Basketball(1986)     0.19$\pm$0.00     0.45$\pm$0.00     0.50$\pm$0.00     0.24$\pm$0.01     0.19$\pm$0.00     0.22$\pm$0.00     0.22$\pm$0.00     0.49$\pm$0.00     0.27$\pm$0.00     0.21$\pm$0.00     nan$\pm$nan     0.20$\pm$0.00     0.17$\pm$0.00

Basketball(1987)     0.21$\pm$0.00     0.45$\pm$0.00     0.47$\pm$0.00     0.25$\pm$0.00     0.21$\pm$0.00     0.25$\pm$0.00     0.22$\pm$0.00     0.48$\pm$0.00     0.25$\pm$0.00     0.23$\pm$0.00     nan$\pm$nan     0.21$\pm$0.00     0.19$\pm$0.00

Basketball(1988)     0.19$\pm$0.00     0.42$\pm$0.00     0.48$\pm$0.00     0.23$\pm$0.01     0.19$\pm$0.00     0.22$\pm$0.00     0.21$\pm$0.00     0.48$\pm$0.00     0.24$\pm$0.00     0.21$\pm$0.00     nan$\pm$nan     0.19$\pm$0.00     0.17$\pm$0.00

Basketball(1989)     0.19$\pm$0.00     0.44$\pm$0.00     0.47$\pm$0.00     0.24$\pm$0.01     0.19$\pm$0.00     0.20$\pm$0.00     0.21$\pm$0.00     0.47$\pm$0.00     0.25$\pm$0.00     0.23$\pm$0.00     nan$\pm$nan     0.19$\pm$0.00     0.17$\pm$0.00

Basketball(1990)     0.19$\pm$0.00     0.42$\pm$0.00     0.48$\pm$0.00     0.22$\pm$0.02     0.20$\pm$0.00     0.23$\pm$0.00     0.22$\pm$0.00     0.49$\pm$0.00     0.23$\pm$0.00     0.21$\pm$0.00     nan$\pm$nan     0.19$\pm$0.00     0.17$\pm$0.00

Basketball(1991)     0.20$\pm$0.00     0.45$\pm$0.00     0.51$\pm$0.00     0.23$\pm$0.02     0.19$\pm$0.00     0.22$\pm$0.00     0.21$\pm$0.00     0.49$\pm$0.00     0.25$\pm$0.00     0.22$\pm$0.00     nan$\pm$nan     0.19$\pm$0.00     0.18$\pm$0.00

Basketball(1992)     0.19$\pm$0.00     0.43$\pm$0.00     0.47$\pm$0.00     0.21$\pm$0.02     0.18$\pm$0.00     0.21$\pm$0.00     0.20$\pm$0.00     0.50$\pm$0.00     0.24$\pm$0.00     0.21$\pm$0.00     nan$\pm$nan     0.18$\pm$0.00     0.17$\pm$0.00

Basketball(1993)     0.19$\pm$0.00     0.42$\pm$0.00     0.51$\pm$0.00     0.22$\pm$0.02     0.19$\pm$0.00     0.21$\pm$0.00     0.21$\pm$0.00     0.48$\pm$0.00     0.25$\pm$0.00     0.21$\pm$0.00     nan$\pm$nan     0.19$\pm$0.00     0.17$\pm$0.00

Basketball(1994)     0.19$\pm$0.00     0.42$\pm$0.00     0.50$\pm$0.00     0.19$\pm$0.02     0.18$\pm$0.00     0.20$\pm$0.00     0.21$\pm$0.00     0.51$\pm$0.00     0.23$\pm$0.00     0.21$\pm$0.00     nan$\pm$nan     0.19$\pm$0.00     0.17$\pm$0.00

Basketball(1995)     0.19$\pm$0.00     0.44$\pm$0.00     0.47$\pm$0.00     0.21$\pm$0.02     0.19$\pm$0.00     0.21$\pm$0.00     0.22$\pm$0.00     0.50$\pm$0.00     0.24$\pm$0.00     0.22$\pm$0.00     nan$\pm$nan     0.19$\pm$0.00     0.18$\pm$0.00

Basketball(1996)     0.21$\pm$0.00     0.42$\pm$0.00     0.51$\pm$0.00     0.24$\pm$0.02     0.20$\pm$0.00     0.23$\pm$0.00     0.23$\pm$0.00     0.51$\pm$0.00     0.27$\pm$0.00     0.24$\pm$0.00     nan$\pm$nan     0.21$\pm$0.00     0.19$\pm$0.00

Basketball(1997)     0.20$\pm$0.00     0.43$\pm$0.00     0.49$\pm$0.00     0.24$\pm$0.01     0.21$\pm$0.00     0.23$\pm$0.00     0.23$\pm$0.00     0.47$\pm$0.00     0.24$\pm$0.00     0.23$\pm$0.00     nan$\pm$nan     0.21$\pm$0.00     0.19$\pm$0.00

Basketball(1998)     0.19$\pm$0.00     0.42$\pm$0.00     0.48$\pm$0.00     0.24$\pm$0.01     0.20$\pm$0.00     0.22$\pm$0.00     0.21$\pm$0.00     0.48$\pm$0.00     0.24$\pm$0.00     0.22$\pm$0.00     nan$\pm$nan     0.20$\pm$0.00     0.18$\pm$0.00

Basketball(1999)     0.21$\pm$0.00     0.39$\pm$0.00     0.50$\pm$0.00     0.24$\pm$0.02     0.20$\pm$0.00     0.23$\pm$0.00     0.24$\pm$0.00     0.47$\pm$0.00     0.29$\pm$0.00     0.24$\pm$0.00     nan$\pm$nan     0.21$\pm$0.00     0.18$\pm$0.00

Basketball(2000)     0.21$\pm$0.00     0.44$\pm$0.00     0.49$\pm$0.00     0.25$\pm$0.01     0.21$\pm$0.00     0.23$\pm$0.00     0.23$\pm$0.00     0.48$\pm$0.00     0.28$\pm$0.00     0.23$\pm$0.00     nan$\pm$nan     0.21$\pm$0.00     0.19$\pm$0.00

Basketball(2001)     0.19$\pm$0.00     0.43$\pm$0.00     0.51$\pm$0.00     0.23$\pm$0.02     0.19$\pm$0.00     0.22$\pm$0.00     0.21$\pm$0.00     0.50$\pm$0.00     0.26$\pm$0.00     0.23$\pm$0.00     nan$\pm$nan     0.19$\pm$0.00     0.18$\pm$0.00

Basketball(2002)     0.20$\pm$0.00     0.42$\pm$0.00     0.48$\pm$0.00     0.23$\pm$0.01     0.20$\pm$0.00     0.21$\pm$0.00     0.23$\pm$0.00     0.49$\pm$0.00     0.26$\pm$0.00     0.22$\pm$0.00     nan$\pm$nan     0.20$\pm$0.00     0.18$\pm$0.00

Basketball(2003)     0.20$\pm$0.00     0.46$\pm$0.00     0.51$\pm$0.00     0.24$\pm$0.02     0.20$\pm$0.00     0.24$\pm$0.00     0.23$\pm$0.00     0.48$\pm$0.00     0.25$\pm$0.00     0.23$\pm$0.00     nan$\pm$nan     0.21$\pm$0.00     0.19$\pm$0.00

Basketball(2004)     0.19$\pm$0.00     0.42$\pm$0.00     0.50$\pm$0.03     0.22$\pm$0.02     0.19$\pm$0.00     0.21$\pm$0.00     0.22$\pm$0.00     0.49$\pm$0.00     0.23$\pm$0.00     0.22$\pm$0.00     nan$\pm$nan     0.19$\pm$0.00     0.17$\pm$0.00

Basketball(2005)     0.19$\pm$0.00     0.45$\pm$0.00     0.49$\pm$0.01     0.24$\pm$0.01     0.20$\pm$0.00     0.21$\pm$0.00     0.23$\pm$0.00     0.47$\pm$0.00     0.26$\pm$0.00     0.23$\pm$0.00     nan$\pm$nan     0.20$\pm$0.00     0.18$\pm$0.00

Basketball(2006)     0.20$\pm$0.00     0.44$\pm$0.00     0.50$\pm$0.00     0.21$\pm$0.02     0.19$\pm$0.00     0.22$\pm$0.00     0.22$\pm$0.00     0.50$\pm$0.00     0.26$\pm$0.00     0.23$\pm$0.00     nan$\pm$nan     0.21$\pm$0.00     0.19$\pm$0.00

Basketball(2007)     0.20$\pm$0.00     0.47$\pm$0.00     0.48$\pm$0.02     0.24$\pm$0.00     0.21$\pm$0.00     0.22$\pm$0.00     0.22$\pm$0.00     0.49$\pm$0.00     0.23$\pm$0.00     0.22$\pm$0.00     nan$\pm$nan     0.21$\pm$0.00     0.19$\pm$0.00

Basketball(2008)     0.20$\pm$0.00     0.44$\pm$0.00     0.50$\pm$0.00     0.22$\pm$0.02     0.20$\pm$0.00     0.22$\pm$0.00     0.23$\pm$0.00     0.48$\pm$0.00     0.24$\pm$0.00     0.23$\pm$0.00     nan$\pm$nan     0.21$\pm$0.00     0.20$\pm$0.00

Basketball(2009)     0.19$\pm$0.00     0.43$\pm$0.00     0.51$\pm$0.00     0.24$\pm$0.00     0.19$\pm$0.00     0.21$\pm$0.00     0.21$\pm$0.00     0.47$\pm$0.00     0.24$\pm$0.00     0.22$\pm$0.00     nan$\pm$nan     0.19$\pm$0.00     0.18$\pm$0.00

Basketball(2010)     0.20$\pm$0.00     0.39$\pm$0.00     0.49$\pm$0.00     0.21$\pm$0.02     0.19$\pm$0.00     0.23$\pm$0.00     0.23$\pm$0.00     0.51$\pm$0.00     0.23$\pm$0.00     0.23$\pm$0.00     nan$\pm$nan     0.21$\pm$0.00     0.18$\pm$0.00

Basketball(2011)     0.20$\pm$0.00     0.41$\pm$0.00     0.49$\pm$0.00     0.21$\pm$0.02     0.20$\pm$0.00     0.22$\pm$0.00     0.22$\pm$0.00     0.51$\pm$0.00     0.24$\pm$0.00     0.22$\pm$0.00     nan$\pm$nan     0.20$\pm$0.00     0.18$\pm$0.00

Basketball(2012)     0.19$\pm$0.00     0.45$\pm$0.00     0.49$\pm$0.00     0.22$\pm$0.02     0.19$\pm$0.00     0.21$\pm$0.00     0.21$\pm$0.00     0.49$\pm$0.00     0.22$\pm$0.00     0.21$\pm$0.00     nan$\pm$nan     0.19$\pm$0.00     0.17$\pm$0.00

Basketball(2013)     0.20$\pm$0.00     0.43$\pm$0.00     0.50$\pm$0.01     0.24$\pm$0.02     0.20$\pm$0.00     0.22$\pm$0.00     0.22$\pm$0.00     0.49$\pm$0.00     0.25$\pm$0.00     0.23$\pm$0.00     nan$\pm$nan     0.20$\pm$0.00     0.19$\pm$0.00

Basketball(2014)     0.20$\pm$0.00     0.43$\pm$0.00     0.52$\pm$0.00     0.22$\pm$0.02     0.20$\pm$0.00     0.22$\pm$0.00     0.23$\pm$0.00     0.48$\pm$0.00     0.25$\pm$0.00     0.22$\pm$0.00     nan$\pm$nan     0.21$\pm$0.00     0.19$\pm$0.00

Basketball finer(1985)     0.19$\pm$0.00     0.41$\pm$0.00     0.49$\pm$0.02     0.36$\pm$0.01     0.21$\pm$0.00     0.29$\pm$0.00     0.29$\pm$0.00     0.49$\pm$0.00     0.25$\pm$0.00     0.22$\pm$0.00     nan$\pm$nan     0.20$\pm$0.00     0.18$\pm$0.00

Basketball finer(1986)     0.19$\pm$0.00     0.45$\pm$0.00     0.50$\pm$0.00     0.36$\pm$0.02     0.21$\pm$0.00     0.29$\pm$0.00     0.29$\pm$0.00     0.50$\pm$0.00     0.27$\pm$0.00     0.21$\pm$0.00     nan$\pm$nan     0.20$\pm$0.00     0.17$\pm$0.00

Basketball finer(1987)     0.20$\pm$0.00     0.45$\pm$0.00     0.47$\pm$0.00     0.35$\pm$0.01     0.22$\pm$0.00     0.29$\pm$0.00     0.30$\pm$0.00     0.49$\pm$0.00     0.25$\pm$0.00     0.23$\pm$0.00     nan$\pm$nan     0.21$\pm$0.01     0.19$\pm$0.00

Basketball finer(1988)     0.19$\pm$0.00     0.45$\pm$0.00     0.48$\pm$0.00     0.36$\pm$0.03     0.21$\pm$0.00     0.31$\pm$0.00     0.30$\pm$0.00     0.49$\pm$0.00     0.24$\pm$0.00     0.21$\pm$0.00     nan$\pm$nan     0.20$\pm$0.00     0.18$\pm$0.00

Basketball finer(1989)     0.19$\pm$0.00     0.42$\pm$0.00     0.46$\pm$0.00     0.36$\pm$0.01     0.21$\pm$0.00     0.28$\pm$0.00     0.29$\pm$0.00     0.49$\pm$0.00     0.25$\pm$0.00     0.23$\pm$0.00     nan$\pm$nan     0.20$\pm$0.01     0.18$\pm$0.00

Basketball finer(1990)     0.20$\pm$0.00     0.42$\pm$0.00     0.48$\pm$0.00     0.36$\pm$0.01     0.21$\pm$0.00     0.32$\pm$0.00     0.29$\pm$0.00     0.50$\pm$0.00     0.23$\pm$0.00     0.21$\pm$0.00     nan$\pm$nan     0.20$\pm$0.01     0.18$\pm$0.00

Basketball finer(1991)     0.20$\pm$0.00     0.46$\pm$0.00     0.51$\pm$0.00     0.34$\pm$0.02     0.21$\pm$0.00     0.35$\pm$0.00     0.33$\pm$0.00     0.49$\pm$0.00     0.25$\pm$0.00     0.22$\pm$0.00     nan$\pm$nan     0.21$\pm$0.00     0.18$\pm$0.00

Basketball finer(1992)     0.18$\pm$0.00     0.43$\pm$0.00     0.47$\pm$0.00     0.33$\pm$0.01     0.19$\pm$0.00     0.31$\pm$0.00     0.30$\pm$0.00     0.47$\pm$0.00     0.24$\pm$0.00     0.21$\pm$0.00     nan$\pm$nan     0.19$\pm$0.00     0.17$\pm$0.00

Basketball finer(1993)     0.19$\pm$0.00     0.42$\pm$0.00     0.51$\pm$0.00     0.34$\pm$0.01     0.20$\pm$0.00     0.29$\pm$0.00     0.27$\pm$0.00     0.49$\pm$0.00     0.25$\pm$0.00     0.21$\pm$0.00     nan$\pm$nan     0.20$\pm$0.00     0.17$\pm$0.00

Basketball finer(1994)     0.18$\pm$0.00     0.42$\pm$0.00     0.50$\pm$0.00     0.34$\pm$0.02     0.19$\pm$0.00     0.31$\pm$0.00     0.27$\pm$0.00     0.49$\pm$0.00     0.22$\pm$0.00     0.21$\pm$0.00     nan$\pm$nan     0.19$\pm$0.00     0.17$\pm$0.00

Basketball finer(1995)     0.20$\pm$0.00     0.44$\pm$0.00     0.47$\pm$0.00     0.34$\pm$0.02     0.21$\pm$0.00     0.30$\pm$0.00     0.28$\pm$0.00     0.48$\pm$0.00     0.24$\pm$0.00     0.22$\pm$0.00     nan$\pm$nan     0.20$\pm$0.00     0.18$\pm$0.00

Basketball finer(1996)     0.20$\pm$0.00     0.42$\pm$0.00     0.49$\pm$0.00     0.36$\pm$0.02     0.22$\pm$0.00     0.30$\pm$0.00     0.30$\pm$0.00     0.49$\pm$0.00     0.27$\pm$0.00     0.24$\pm$0.00     nan$\pm$nan     0.22$\pm$0.00     0.19$\pm$0.00

Basketball finer(1997)     0.21$\pm$0.00     0.44$\pm$0.00     0.49$\pm$0.00     0.35$\pm$0.01     0.21$\pm$0.00     0.30$\pm$0.00     0.29$\pm$0.00     0.51$\pm$0.00     0.24$\pm$0.00     0.23$\pm$0.00     nan$\pm$nan     0.21$\pm$0.00     0.19$\pm$0.00

Basketball finer(1998)     0.20$\pm$0.00     0.42$\pm$0.00     0.48$\pm$0.00     0.34$\pm$0.02     0.21$\pm$0.00     0.29$\pm$0.00     0.28$\pm$0.00     0.48$\pm$0.00     0.24$\pm$0.00     0.22$\pm$0.00     nan$\pm$nan     0.20$\pm$0.00     0.18$\pm$0.00

Basketball finer(1999)     0.20$\pm$0.00     0.41$\pm$0.00     0.50$\pm$0.00     0.34$\pm$0.02     0.22$\pm$0.00     0.29$\pm$0.00     0.28$\pm$0.00     0.50$\pm$0.00     0.29$\pm$0.00     0.24$\pm$0.00     nan$\pm$nan     0.21$\pm$0.00     0.18$\pm$0.00

Basketball finer(2000)     0.21$\pm$0.00     0.44$\pm$0.00     0.49$\pm$0.00     0.35$\pm$0.01     0.23$\pm$0.00     0.32$\pm$0.00     0.30$\pm$0.00     0.48$\pm$0.00     0.28$\pm$0.00     0.24$\pm$0.00     nan$\pm$nan     0.22$\pm$0.00     0.19$\pm$0.00

Basketball finer(2001)     0.20$\pm$0.00     0.42$\pm$0.00     0.51$\pm$0.00     0.35$\pm$0.01     0.21$\pm$0.00     0.31$\pm$0.00     0.30$\pm$0.00     0.51$\pm$0.00     0.27$\pm$0.00     0.24$\pm$0.00     nan$\pm$nan     0.21$\pm$0.00     0.18$\pm$0.00

Basketball finer(2002)     0.22$\pm$0.00     0.44$\pm$0.00     0.47$\pm$0.00     0.36$\pm$0.02     0.22$\pm$0.00     0.30$\pm$0.00     0.28$\pm$0.00     0.51$\pm$0.00     0.27$\pm$0.00     0.23$\pm$0.00     nan$\pm$nan     0.21$\pm$0.00     0.19$\pm$0.00

Basketball finer(2003)     0.22$\pm$0.00     0.45$\pm$0.00     0.50$\pm$0.02     0.36$\pm$0.02     0.23$\pm$0.00     0.29$\pm$0.00     0.29$\pm$0.00     0.50$\pm$0.00     0.26$\pm$0.00     0.24$\pm$0.00     nan$\pm$nan     0.22$\pm$0.00     0.19$\pm$0.00

Basketball finer(2004)     0.19$\pm$0.00     0.43$\pm$0.01     0.47$\pm$0.00     0.35$\pm$0.01     0.20$\pm$0.00     0.29$\pm$0.00     0.28$\pm$0.00     0.49$\pm$0.00     0.24$\pm$0.00     0.22$\pm$0.00     nan$\pm$nan     0.21$\pm$0.00     0.18$\pm$0.00

Basketball finer(2005)     0.21$\pm$0.00     0.46$\pm$0.00     0.48$\pm$0.00     0.34$\pm$0.01     0.22$\pm$0.00     0.29$\pm$0.00     0.27$\pm$0.00     0.50$\pm$0.00     0.27$\pm$0.00     0.24$\pm$0.00     nan$\pm$nan     0.21$\pm$0.00     0.19$\pm$0.00

Basketball finer(2006)     0.21$\pm$0.00     0.44$\pm$0.00     0.49$\pm$0.00     0.35$\pm$0.02     0.21$\pm$0.00     0.30$\pm$0.00     0.28$\pm$0.00     0.49$\pm$0.00     0.27$\pm$0.00     0.23$\pm$0.00     nan$\pm$nan     0.22$\pm$0.01     0.19$\pm$0.00

Basketball finer(2007)     0.21$\pm$0.00     0.46$\pm$0.00     0.49$\pm$0.03     0.35$\pm$0.01     0.23$\pm$0.00     0.29$\pm$0.00     0.27$\pm$0.00     0.48$\pm$0.00     0.24$\pm$0.00     0.23$\pm$0.00     nan$\pm$nan     0.22$\pm$0.00     0.20$\pm$0.00

Basketball finer(2008)     0.21$\pm$0.00     0.43$\pm$0.00     0.49$\pm$0.00     0.34$\pm$0.02     0.22$\pm$0.00     0.30$\pm$0.00     0.28$\pm$0.00     0.49$\pm$0.00     0.25$\pm$0.00     0.23$\pm$0.00     nan$\pm$nan     0.21$\pm$0.00     0.20$\pm$0.00

Basketball finer(2009)     0.21$\pm$0.00     0.43$\pm$0.00     0.50$\pm$0.01     0.34$\pm$0.01     0.22$\pm$0.00     0.29$\pm$0.00     0.28$\pm$0.00     0.52$\pm$0.00     0.25$\pm$0.00     0.23$\pm$0.00     nan$\pm$nan     0.21$\pm$0.00     0.19$\pm$0.00

Basketball finer(2010)     0.20$\pm$0.00     0.42$\pm$0.00     0.49$\pm$0.00     0.33$\pm$0.02     0.21$\pm$0.00     0.28$\pm$0.00     0.28$\pm$0.00     0.49$\pm$0.00     0.24$\pm$0.00     0.23$\pm$0.00     nan$\pm$nan     0.21$\pm$0.00     0.19$\pm$0.00

Basketball finer(2011)     0.21$\pm$0.00     0.41$\pm$0.00     0.49$\pm$0.00     0.34$\pm$0.01     0.22$\pm$0.00     0.28$\pm$0.00     0.28$\pm$0.00     0.50$\pm$0.00     0.24$\pm$0.00     0.22$\pm$0.00     nan$\pm$nan     0.22$\pm$0.00     0.19$\pm$0.00

Basketball finer(2012)     0.20$\pm$0.00     0.42$\pm$0.00     0.49$\pm$0.00     0.34$\pm$0.02     0.21$\pm$0.00     0.29$\pm$0.00     0.28$\pm$0.00     0.48$\pm$0.00     0.23$\pm$0.00     0.22$\pm$0.00     nan$\pm$nan     0.21$\pm$0.00     0.18$\pm$0.00

Basketball finer(2013)     0.21$\pm$0.00     0.43$\pm$0.00     0.52$\pm$0.00     0.34$\pm$0.02     0.22$\pm$0.00     0.29$\pm$0.00     0.28$\pm$0.00     0.49$\pm$0.00     0.25$\pm$0.00     0.23$\pm$0.00     nan$\pm$nan     0.21$\pm$0.00     0.20$\pm$0.00

Basketball finer(2014)     0.21$\pm$0.00     0.44$\pm$0.05     0.52$\pm$0.00     0.36$\pm$0.02     0.22$\pm$0.00     0.30$\pm$0.00     0.28$\pm$0.00     0.49$\pm$0.00     0.26$\pm$0.00     0.22$\pm$0.00     nan$\pm$nan     0.22$\pm$0.00     0.20$\pm$0.00

Football(2009)     0.15$\pm$0.00     0.36$\pm$0.11     0.23$\pm$0.00     0.17$\pm$0.02     0.20$\pm$0.00     0.23$\pm$0.00     0.26$\pm$0.00     0.45$\pm$0.02     0.20$\pm$0.00     0.16$\pm$0.00     0.39$\pm$0.04     0.19$\pm$0.01     0.15$\pm$0.00

Football(2010)     0.30$\pm$0.00     0.45$\pm$0.04     0.39$\pm$0.00     0.30$\pm$0.01     0.32$\pm$0.00     0.34$\pm$0.00     0.34$\pm$0.00     0.46$\pm$0.03     0.31$\pm$0.00     0.29$\pm$0.00     0.49$\pm$0.05     0.30$\pm$0.01     0.29$\pm$0.00

Football(2011)     0.20$\pm$0.00     0.39$\pm$0.09     0.24$\pm$0.00     0.22$\pm$0.01     0.22$\pm$0.00     0.25$\pm$0.00     0.25$\pm$0.00     0.40$\pm$0.00     0.23$\pm$0.00     0.21$\pm$0.00     0.45$\pm$0.05     0.22$\pm$0.01     0.20$\pm$0.00

Football(2012)     0.24$\pm$0.00     0.38$\pm$0.01     0.35$\pm$0.00     0.25$\pm$0.01     0.22$\pm$0.00     0.24$\pm$0.00     0.25$\pm$0.00     0.41$\pm$0.00     0.25$\pm$0.00     0.22$\pm$0.00     0.43$\pm$0.04     0.20$\pm$0.02     0.21$\pm$0.00

Football(2013)     0.19$\pm$0.00     0.41$\pm$0.03     0.19$\pm$0.00     0.19$\pm$0.01     0.17$\pm$0.00     0.23$\pm$0.00     0.22$\pm$0.00     0.48$\pm$0.02     0.22$\pm$0.00     0.19$\pm$0.00     0.40$\pm$0.03     0.16$\pm$0.01     0.14$\pm$0.00

Football(2014)     0.28$\pm$0.00     0.45$\pm$0.05     0.39$\pm$0.00     0.29$\pm$0.00     0.28$\pm$0.00     0.32$\pm$0.00     0.30$\pm$0.00     0.46$\pm$0.03     0.28$\pm$0.00     0.27$\pm$0.00     0.43$\pm$0.05     0.24$\pm$0.01     0.26$\pm$0.01

Football finer(2009)     0.18$\pm$0.00     0.45$\pm$0.00     0.23$\pm$0.00     0.20$\pm$0.03     0.18$\pm$0.00     0.26$\pm$0.00     0.27$\pm$0.00     0.47$\pm$0.01     0.20$\pm$0.00     0.16$\pm$0.00     0.48$\pm$0.04     0.19$\pm$0.05     0.16$\pm$0.01

Football finer(2010)     0.32$\pm$0.00     0.41$\pm$0.01     0.36$\pm$0.00     0.33$\pm$0.02     0.32$\pm$0.00     0.34$\pm$0.00     0.37$\pm$0.00     0.49$\pm$0.00     0.31$\pm$0.00     0.29$\pm$0.00     0.53$\pm$0.00     0.31$\pm$0.02     0.29$\pm$0.00

Football finer(2011)     0.22$\pm$0.00     0.40$\pm$0.01     0.27$\pm$0.00     0.23$\pm$0.01     0.23$\pm$0.00     0.25$\pm$0.00     0.28$\pm$0.00     0.47$\pm$0.00     0.23$\pm$0.00     0.21$\pm$0.00     0.53$\pm$0.00     0.23$\pm$0.04     0.21$\pm$0.01

Football finer(2012)     0.24$\pm$0.00     0.44$\pm$0.04     0.27$\pm$0.00     0.25$\pm$0.01     0.23$\pm$0.00     0.27$\pm$0.00     0.30$\pm$0.00     0.51$\pm$0.01     0.25$\pm$0.00     0.22$\pm$0.00     0.54$\pm$0.00     0.24$\pm$0.02     0.21$\pm$0.01

Football finer(2013)     0.22$\pm$0.00     0.39$\pm$0.00     0.22$\pm$0.00     0.21$\pm$0.02     0.18$\pm$0.00     0.25$\pm$0.00     0.27$\pm$0.00     0.50$\pm$0.00     0.22$\pm$0.00     0.19$\pm$0.00     0.49$\pm$0.04     0.18$\pm$0.05     0.14$\pm$0.00

Football finer(2014)     0.29$\pm$0.00     0.44$\pm$0.01     0.39$\pm$0.00     0.30$\pm$0.01     0.26$\pm$0.00     0.31$\pm$0.00     0.31$\pm$0.00     0.42$\pm$0.00     0.28$\pm$0.00     0.27$\pm$0.00     0.52$\pm$0.04     0.27$\pm$0.01     0.27$\pm$0.02

Result table on $\mathcal{L}_\text{upset, ratio}$ for individual directed graphs as input, averaged over 10 runs, and plus/minus one standard deviation. The best is marked in bold red while the second best is highlighted in underline blue. MVR could not generate scores, so we omit the results.

Data      SpringRank     SyncRank     SerialRank     BTL     DavidScore     Eig.Cent.     PageRank     RankCent.     SVD_RS     SVD_NRS    GNNRank-N     GNNRank-P

HeadToHead     0.86$\pm$0.00     0.97$\pm$0.00     0.97$\pm$0.00     0.71$\pm$0.01     0.89$\pm$0.00     0.98$\pm$0.04     0.83$\pm$0.00     1.19$\pm$0.09     1.14$\pm$0.00     0.95$\pm$0.00     0.68$\pm$0.00     0.94$\pm$0.00

Finance     0.26$\pm$0.00     0.27$\pm$0.00     0.27$\pm$0.00     0.28$\pm$0.00     0.64$\pm$0.00     0.27$\pm$0.00     0.26$\pm$0.00     0.59$\pm$0.00     0.26$\pm$0.00     0.26$\pm$0.00     0.26$\pm$0.00     0.27$\pm$0.00

Animal     0.42$\pm$0.00     0.80$\pm$0.02     0.88$\pm$0.00     0.22$\pm$0.00     0.41$\pm$0.00     0.43$\pm$0.14     0.50$\pm$0.00     1.34$\pm$0.00     0.62$\pm$0.00     0.42$\pm$0.00     0.24$\pm$0.03     0.66$\pm$0.00