# Inherent Limits on Topology-Based Link Prediction

Justus Isaiah Hibshman<EMAIL_ADDRESS>University of Notre Dame  Tim Weninger
<EMAIL_ADDRESS>University of Notre Dame

###### Abstract

Link prediction systems (e.g. recommender systems) typically use graph
topology as one of their main sources of information. However, automorphisms
and related properties of graphs beget inherent limits in predictability. We
calculate hard upper bounds on how well graph topology alone enables link
prediction for a wide variety of real-world graphs. We find that in the
sparsest of these graphs the upper bounds are surprisingly low, thereby
demonstrating that prediction systems on sparse graph data are inherently
limited and require information in addition to the graph topology.

##  I Introduction

Graph-based link prediction systems are widely used to recommend a wide
variety of products and services. Whenever a shopping website predicts what
you will buy next based on what you and others like you have previously
bought, that’s link prediction. Whenever a social media network suggests that
you might know someone, that’s link prediction. Link prediction is the well-
studied task of predicting connections between entities amidst a network (aka
“graph”) of entity-entity connections.

Usually, these recommendations are based on a combination of node features and
the topology (i.e. the link-structure) of the graph-data. One might assume
that the node features or the topology contain sufficient information for an
ideal link prediction system using that information to perfectly select the
missing connections. However, we show this to be false for graph topology;
whenever a graph possesses symmetries (i.e. automorphisms) in its topology,
then the graph’s topology does not contain enough information to guarantee
correct selection of the missing edges. This raises two foundational questions
in machine learning on graphs:

  1. 1.

What are the inherent limits on a graph structure’s predictability?

  2. 2.

Do contemporary systems approach these performance limits?

The goal of the present work is to help answer these questions. To do so, we
investigate how much information a graph’s topology alone can provide to a
link prediction algorithm; that forms one kind of inherent limit on a
structure’s predictibility. In particular, we calculate hard upper limits on
how well an algorithm using only topology information can score in standard
link prediction metrics (AUC and AUPR). Our upper bounds hold for _any and
all_ link prediction algorithms and thus are bounds on the informativeness of
the topology data itself. Given these limits, we and others can begin to
answer question 2 by comparing contemporary link prediction systems’ scores to
these upper bounds.

To calculate an upper bound that will hold regardless of the link prediction
algorithm used, we calculate an upper limit on the performance of an idealized
algorithm presented with as much information about the solution as possible.
Specifically, we imagine showing the algorithm the graph _and_ the solution
set of missing edges; then we imagine removing or scrambling the nodes’ labels
and asking the algorithm to predict the solution on the re-labeled graph. We
call the process of removing or randomly permuting the nodes’ labels
“anonymizing” the graph.

For example, consider the following scenario illustrated in Fig. 1: Imagine
you are shown both a link prediction task and the answer to the same task
(i.e. the links one must predict); in Fig. 1, the solution edges are $(a,b)$,
$(a,e)$, and $(e,f)$. Now imagine further that you are asked to perform link
prediction on an anonymized version of the same problem, then asked to predict
which edges are missing. You know, for instance, that you must select edge
$(e,f)$, but you do not know for certain which node is $e$ nor which node is
$f$.

The anonymized graph is, by itself, effectively identical to the data that an
algorithm would be given for the regular link prediction task. We call the
task of doing link prediction on the anonymized graph after having seen the
un-anonymized solution _the known-topology link prediction task_. As we hinted
above, and as Figure 1 shows, _symmetries_ in the graph can render several
possible edge-predictions structurally identical and therefore equally valid.
It is from these symmetries that performance is limited even on the known-
topology task.

Of course, in practice, most systems will perform much worse at the standard
link prediction task than an ideal algorithm could perform at the known-
topology task. Any link prediction algorithm will have some inherent, implicit
modeling assumptions about the graph. For example, a simple model like triadic
closure assumes that the likelihood of an edge is proportionate to the number
of triangles the edge would be involved in bianconi2014triadic ;
klimek2013triadic ; jin2001structure ; davidsen2002emergence . Expressed in a
Bayesian fashion, we can think of a link prediction algorithm as
conditionalizing on evidence, where the data the algorithm sees is its
evidence and the algorithm’s inherent assumptions form its prior. One could
think about an algorithm performing the known-topology link prediction task as
an algorithm doing standard link prediction with a perfect prior (i.e. 100%
confidence on the correct graph). We focus on the known-topology link
prediction task because it enables us to establish limits that exists in the
data itself, without making _any_ assumptions about the link prediction
algorithm.

abcdefvutsrqOriginal Graph withThree Hidden LinksSame Graph Anonymizedand with
the ThreeLinks RemovedThree of Eight EquallyValid
Reconstructionsaecdbfaefdbcacbdfe Figure 1:  Toy example graph with three
held-out edges for what we call the known-topology link prediction task. The
link predictor knows that it must pick edges $(a,b)$, $(a,e)$, and $(e,f)$,
but does not know for certain which nodes in the anonymized graph correspond
to $b$, $c$, $e$, or $f$. In this case, there exist eight equally plausible
edge sets that would turn the anonymized graph into a graph isomorphic to the
original. However, only one of these eight is “correct” from the perspective
of standard link prediction evaluation. Note that each of these eight
candidate edge sets correspond to a different interpretation of the node
labels in the anonymized graph.

After discussing some related work in Section II and defining our formalisms
in Section III, we discuss some formal properties of link predictors as well
as quantitative link prediction evaluation metrics (ROC and AUPR) in Section
IV. Section V provides a formula for taking any specific link prediction task
(i.e. any (graph, missing edge set) pair) and calculating the max possible
scores a link predictor could achieve on the known-topology version of the
task, thereby establishing an upper bound on performance for the standard
version of the task. We leave the proof that our formula gives the maximum
score in the Appendix. In Section VI we introduce our experiments, which
consist of calculating link prediction score limits for various real-world
graphs; this includes both our main known-topology task limit _and_ various
lower limits that appear on the known-topology task when the link prediction
algorithm only uses a subset of its available information (a $k$-hop
neighborhood) to predict whether a link will appear. Section VII shows our
results. We find that on sparse graphs commonly used for link prediction, the
limits are surprisingly low. Then in Section VII.2 we observe how a famous
graph neural network’s reported results are _above_ the performance limits and
discuss how this is likely due to a common mistake in correctly measuring
AUPR. Lastly, we discuss ways to generalize our analysis in Section VIII.

##  II Related Work

###  II.1 Link Prediction

The link prediction task is widely studied, almost to the point of being
ubiquitous for graph research. It was introduced by Liben-Nowell and Kleinburg
liben2003link . Given a graph, the task is to predict which edges (i.e. links)
might be missing, either because the data is incomplete or because more edges
will appear in the future.

Early models for link prediction tended to rely on certain assumptions, such
as that of “triadic closure,” the assumption that if A connects to B and B
connects to C, then A is also likely to connect to C jin2001structure ;
davidsen2002emergence ; klimek2013triadic ; bianconi2014triadic ;
adamic2003friends .

Then, following the historical trend of machine learning in general, link
prediction models grew in complexity both in their features and in their
classifiers al2006link ; martinez2016survey  until neural networks eventually
began to outperform other methods zhou2020graph ; wu2020comprehensive .

###  II.2 Predictability Limits

To our knowledge, this is the first work to quantify a maximal performance
score that link predictors can obtain on a given task. Other work in
predictibility has focused on measures of predictibility distinct from
evaluation scores. For instance, Abeliuk et. al. study how the predictability
of time-series data degrades as the amount of data available decreases; they
quantify predictability in terms of permutation entropy and signal self-
correlation, as well as actual prediction performance of specific models
abeliuk2020predictability . Permutation entropy has also been found to be
useful to measure predictability in ecology and physics, and
self(auto)-correlation in finance abeliuk2020predictability ;
bandt2002permutation ; garland2014model ; lim2013us .

Scholars have also analyzed predictability limits in other domains. For
instance, some have used notions of entropy to measure predictability limits
on human travel lu2013approaching ; song2010limits  and disease outbreaks
scarpino2019predictability . Predictability is related to system complexity
and chaos boffetta2002predictability . For instance, minute uncertainties on
initial conditions can greatly limit one’s ability to make accurate weather
forecasts zhang2019predictability .

Others have done excellent work on the related but distinct case that the
ground truth (i.e. correct output) itself is uncertain or inherently fuzzy.
For instance, in these sorts of settings one might need an alternate way of
scoring a classifier, such as Survey Equivalence resnick2021survey . Rather
than fuzzy ground-truth, the present work focuses on cases where the correct
output is clearly known during evaluation, but where limits in predictibility
come from symmetries within the input data.

##  III Formalisms

###  III.1 Graphs

We represent a graph $G$ as $G=(V,E)$ where $V$ is the set of vertices (i.e.
nodes) and $E$ is the set of edges. The edges are pairs of vertices. If the
graph’s connections are considered to have a direction, we say that
$E\subseteq V\times V$ and that the graph’s _non-edges_ are $(V\times
V)\setminus E$. If the connections do not have a direction, then the edges are
unordered pairs: $E\subseteq\\{\\{a,b\\}\ |\ (a,b)\in V\times V\\}$. However,
for simplicity, it is standard to always write $(a,b)$ rather than $\\{a,b\\}$
even when talking about undirected graphs. An edge of the form $(a,a)$ is
called a _self-loop_.

###  III.2 Isomorphisms

Given two graphs $G_{1}=(V_{1},E_{1})$ and $G_{2}=(V_{2},E_{2})$, we say that
they are isomorphic if there exists a way to align the two graphs’ vertices so
that the structures overlap perfectly. Formally, $G_{1}$ and $G_{2}$ are
isomorphic (expressed as $G_{1}\cong G_{2}$) if there exists a bijection
between the vertices $f:V_{1}\rightarrow V_{2}$ such that $(a,b)\in
E_{1}\leftrightarrow(f(a),f(b))\in E_{2}$. In this case the function $f$ is
called an _isomorphism_. In this paper, whenever we refer to two graphs as
being equivalent or identical we mean that they are isomorphic.

If $f$ is an isomorphism between two graphs $G_{1}$ and $G_{2}$ we will
sometimes denote this as $G_{1}\cong_{f}G_{2}$.

###  III.3 Automorphism Orbits

Within the context of a single graph, the automorphism orbit of an object
(i.e. a vertex or an edge) captures its equivalence with other objects in the
graph. Two objects are in the same orbit if and only if the data _in no way_
distinguishes between the two objects.

An _automorphism_ of a graph is an isomorphism of the graph with itself. That
is, an automorphism of a graph $G=(V,E)$ is a bijective function
$f:V\rightarrow V$ such that:

$(a,b)\in E\leftrightarrow(f(a),f(b))\in E$

The set of all automorphisms of a graph $G$ form the _automorphism group_ of
the graph and is denoted $\text{Aut}(G)$.

The _automorphism orbits_ of a graph typically refer to collections of
equivalent vertices; however, they can also refer to collections of equivalent
edges. The orbit of a vertex $a$ in graph $G$ is the set
$\text{AO}_{G}(a)=\\{f(a)\ |\ f\in\text{Aut}(G)\\}$. Similarly, the orbit of
an edge $e=(a,b)$ in graph $G$ is the set $\text{AO}_{G}(e)=\\{(f(a),f(b))\ |\
f\in\text{Aut}(G)\\}$. Note that $a\in\text{AO}_{G}(a)$ and
$e\in\text{AO}_{G}(e)$ due to the trivial automorphism $f(x)=x$.

We can even consider the orbits of _non-existent_ edges (i.e. non-edges). Let
$(a,b)\notin E$ be an edge which is not in $G$. We can still define the orbit
of $(a,b)$ to be $\\{(f(a),f(b))\ |\ f\in\text{Aut}(G)\\}$. These orbits are
collections of edges not in $G$ which are equivalent to each other given $G$.

###  III.4 Induced Subgraphs

Given graph $G=(V,E)$ and a subset of the graph’s vertices $S\subseteq V$, we
can define $G$’s _induced subgraph_ on $S$ to be a graph with $S$ as its
nodeset and the edges in $G$ that connect nodes in $S$. Formally:
$G(S)=(S,\\{(a,b)\ |\ (a,b)\in E\land a\in S\land b\in S\\})$.

###  III.5 K-hop Walks

Given two vertices $x,y\in V$, a _$k$ -hop walk_ from $x$ to $y$ is a sequence
$\langle w_{0},w_{1},w_{2},...,w_{k-1},w_{k}\rangle$ where $x=w_{0}$,
$y=w_{k}$, and $(x_{i-1},x_{i})\in E$ for all $i$ from 1 to $k$. For
convenience, we define a “zero-hop” walk to be a single-node “sequence”
$\langle w_{0}\rangle$, representing a “no-steps-taken” journey from $x$ to
itself.

###  III.6 K-hop Neighborhoods

In practice, most link prediction algorithms do not use the entire graph when
predicting the probability of edge membership. Rather, they tend to use local
context. We formalize one intuitive notion of local context here that will be
used throughout the paper.

Given a node or an edge, we can consider the nodes surrounding the entity to
be the collection of nodes you could reach by beginning at the node (or the
edge’s endpoints), and taking up to $k$ steps (aka “hops”) across edges for
some value $k$. We can express this formally as follows:

Given a node $x\in V$, we define its _$k$ -hop neighborhood nodes_ $N_{k}(x)$
to be the set of all nodes within $k$ or fewer steps of $x$. Formally,
$N_{k}(x)=\\{y\ |\ \text{There exists an }l\text{-hop walk from }x\text{ to
}y\text{ where }l\leq k\\}$.

When we consider an edge or a non-edge $(a,b)$, we define its $k$-hop
neighborhood nodes to be the union of the two endpoints’ $k$-hop neighborhood
node sets: $N_{k}((a,b))=N_{k}(a)\cup N_{k}(b)$.

Finally we can define the _$k$ -hop neighborhood subgraph_ (or simply “$k$-hop
neighborhood”) for an edge or non-edge $e=(a,b)$. It is the induced subgraph
on $e$’s $k$-hop neighborhood nodes: $G_{k}(e)=G(N_{k}(e))$.

###  III.7 Anonymized Graphs

Given a graph $G=(V,E)$, an _anonymized version_ of $G$ is another graph $H$
isomorphic to $G$ with no particular relation between $G$’s node labeling and
$H$’s node labeling. More specifically, to get an anonymized copy of $G$, you
can select a random permuation $\pi:V\rightarrow V$; your anonymized graph is
then $H=(V,\\{(\pi(a),\pi(b))\ |\ (a,b)\in E\\})$.

###  III.8 Canonical Forms

A canonical form of a graph $G$ is a representation of $G$ that is produced in
a way invariant to the node ordering of $G$. The idea of a canonical form is
used by practical graph isomorphism algorithms such as Nauty and Traces
mckay2014practical ; they work by first converting two graphs $G_{1}$ and
$G_{2}$ to canonical forms $C_{1}$ and $C_{2}$ respectively, then perform a
trivial check to see if $C_{1}$ and $C_{2}$ are identical.

In other words, canonical forms are defined in terms of the algorithm that
creates them. An algorithm $A$ produces canonical forms for graphs if, for all
pairs of graphs $G$ and $H$, $A(G)=A(H)$ if and only if $G$ is isomorphic to
$H$. The canonical form of $G$ with respect to $A$ is $A(G)$.

##  IV Link Predictors and Their Evaluation

###  IV.1 Link Predictors

A link predictor is essentially a binary classifier for non-edges. It produces
a verdict indicating whether the (non-)edge is or should be a member of the
graph or not.

Let $G=(V,E)$ be a graph and $\bar{E}$ be the set of non-edges in $G$; that
is, $\bar{E}=\\{(a,b)\ |\ a,b\in V\land(a,b)\notin E\\}$. A hard link
predictor (i.e. hard binary classifier) for $G$ and $\bar{E}$ is a function
$\ell_{G}:\bar{E}\rightarrow\\{\texttt{Positive},\texttt{Negative}\\}$ that
gives a non-edge a label (Positive/Negative). A soft link predictor (i.e. soft
binary classifier) for $G$ and $\bar{E}$ is a function
$\ell_{G}:\bar{E}\rightarrow\mathbbm{R}$ that gives a non-edge a score. The
higher the score, the more likely the non-edge is considered to be one of the
Positives; the lower the score, the more likely the non-edge is considered to
be a Negative. The function may be the result of training a model on a
collection of correct edges/non-edges via manual parameter tuning, statistical
analysis, or any number of other methods.

In practice, soft classifier scores are often turned into hard labels by
picking a threshold value $t$ and giving all entities with a score $\geq t$
the Positive label and all others the Negative label.

####  IV.1.1 Our Assumptions

For convenience in our subsequent analysis, we make an assumption about how
link predictors operate. However, we also explain why a performance bound for
this kind of link predictor is ultimately a bound on all link predictors.

Our key assumption is that whenever a link predictor uses graph topology
information $I$ to give an edge $e$ a score, it would have given edge $e$ the
exact same score if any of the graph nodes in $I$ had been labeled
differently. In other words, the predictor’s output is permutation-invariant
on its input.

At first glance, this might sound like a big assumption, but there are only
two ways that an algorithm which is not permutation-invariant can get a better
score than an algorithm that is permutation-invariant:

  * •

Case 1: The input graph’s node ordering was based on some property of the
solution graph.

  * •

Case 2: The input ordering had no significance, but the algorithm gets lucky
arbitrarily due to the input (and would have performed worse given a different
arbitrary node input ordering).

Concerning Case 1: Nobody should want algorithms that make use of the kind of
data in Case 1, because that data is not available in real-world link
prediction settings (e.g. a sales website cannot use a node ordering based on
what products you _will_ buy).

Concerning Case 2: The possibility that an algorithm could get lucky is not a
meaningful counter-example to a performance limit111Technically, there is one
counter-example to this claim which might be of interest to the theoretically-
minded reader. Due to non-linearities in how link prediction scores are
calculated, an algorithm that coordinates its predictions across edges might
manage to increase the expected value of its link prediction score even though
in some cases it will still perform worse than a permutation-invariant
algorithm. For example, in Figure 1 an optimal algorithm meeting our
assumptions would give edges $(v,u)$, $(v,r)$, $(v,t)$, and $(v,q)$ in the
anonymized graph each a $\frac{1}{2}$ probability score of being an edge. A
non-permutation-invariant algorithm could give edges $(v,t)$ and $(v,q)$ each
a probability score of 1 and edges $(v,u)$, $(v,r)$ a score of zero; this kind
of prediction would do better half the time (i.e. on half the anonymizations)
and worse half the time, but might have a higher expected performance score
overall. We consider this sort of case to be exotic enough that it is not
relevant to our analysis..

Consequently, our performance bound is effectively a bound for all link
prediction algorithms - not just permutation-invariant ones.

For those who find these concepts interesting, we note that the notion of
permutation invariance has been explored in the graph neural network (GNN)
literature. For example, see the seminal work of Haggai Maron, who studies
what permutation-invariant architectures enable networks to do
maron2019universality ; maron2019provably ; maron2018invariant . Much of the
GNN research is focused on limits that different architectures impose or what
architectures enable – for example, that simple message passing has a power
equivalent to the 1-dimensional Weisfeiler Lehman algorithm
morris2019weisfeiler  – whereas our work in this paper asks what limits are in
the data itself regardless of which architecture is used.

####  IV.1.2 Edge Equivalence

Our assumption from Section IV.1.1 could be rephrased as, “If a link predictor
is given the exact same information about two different non-edges (same up to
isomorphism), then it gives those two edges the same score.” Using this
assumption, we can partition edges into cells based on whether or not a link
predictor is given the same information about the edges – same information
$\leftrightarrow$ same cell.

When a link predictor $\ell$ for a graph $G$ uses the context of the entire
graph to give an edge a score, then two edges are guaranteed to get the same
score if $G$’s topology in no way distinguishes between the two. Formally,
this means that two edges are guaranteed to get the same score if they are in
the same automorphism orbit:
$e_{1}\in\text{AO}_{G}(e_{2})\rightarrow\ell(e_{1})=\ell(e_{2})$

Often, link predictors use a local context surrounding an edge to give it a
score rather than using the entire graph as context. If we assume that a link
predictor uses at most the $k$-hop neighborhood surrounding an edge to give
the edge its score, then we get that when two edges have equivalent $k$-hop
neighborhoods and when those edges have the same role within the $k$-hop
neighborhoods, then the edges get the same score. Formally, this can be
expressed as: $\left(\exists f.\ G_{k}(e_{1})\cong_{f}G_{k}(e_{2})\land
f(e_{1})=e_{2}\right)\rightarrow\ell(e_{1})=\ell(e_{2})$

Note that by definition $e_{1}\in\text{AO}_{G}(e_{2})$ implies $\left(\exists
f.\ G_{k}(e_{1})\cong_{f}G_{k}(e_{2})\land f(e_{1})=e_{2}\right)$ for any $k$.
In other words, if two edges are equivalent in the context of the entire
graph, then they are guaranteed to be equivalent when considered in context of
their $k$-hop neighborhoods.

###  IV.2 Performance Scores for Link Predictors

In practice, almost all link prediction classifiers are soft classifiers.
There are a number of nuances to how these classifiers are scored that are
worth highlighting here.

Remember that a soft classifier can be converted into a hard (i.e. binary)
classifier by predicting “yes” when the soft classifier’s output is above a
certain threshold and “no” otherwise. Researchers tend to evaluate the soft
predictors across a range of different thresholds. Each (soft predictor,
threshold) pair represents a possible hard link predictor. Thus performance of
a soft predictor can be considered to be the goodness of the collection of
hard predictors it offers. This can be measured in terms of different
criterion. One common criterion is the relationship between a predictor’s True
Positive Rate (TPR) and False Positive Rate (FPR), which generates the widely
used ROC curve; the ROC score is the area under the ROC curve. Another common
criterion is the relationship between the predictor’s Precision and Recall,
which leads to the Precision-Recall curve and its corresponding metric of Area
Under the Precision-Recall curve (AUPR). For an in-depth analysis exploring
the relationship between ROC curves and Precision-Recall curves, we recommend
the paper by Davis and Goadrich davis2006relationship .

When converting a set of (TPR, FPR) or (Precision, Recall) points into a
curve, an interpolation between points represents a way of combining the two
hard classifiers (the two points) into a new hard classifier. This can be done
by picking a value $\alpha\in[0,1]$ and tossing an $\alpha$-weighted coin
every time an entity is scored to decide which of the two hard classifiers to
use for the entity. This is implicitly how we as well as Davis and Goadrich
perform interpolation. It turns out that the popular trapezoidal interpolation
is incorrect for Precision-Recall space, because hard classifiers cannot be
combined to get precision-recall pairs that interpolate linearly
davis2006relationship .

Sometimes, rather than calculate the AUPR curve exactly, it can be
approximated with a measure called Average Precision (AP). Rather than doing a
complex interpolation between two precision-recall points, Average Precision
simply uses the precision of the rightmost point (the point with the higher
recall).

##  V Optimal Prediction Performance

Here we offer the actual formulae for calculating the optimal ROC and AUPR
scores a soft classifier can obtain.

Recall from Section IV.1.1 that there will be some edges which are
topologically identical and thus which will both get the same score from a
link predictor. This fact forms a limit on the ability of the link predictor
to separate positive edges from negative edges. As we discussed in Section
IV.1.2, given whatever topological information an algorithm uses, we can
partition the edges into cells, where each cell is one of the sets of edges
that must all be given the same score as eachother by the algorithm; when the
algorithm uses the entire graph as data to help it score an edge, then the
relevant partition is formed by grouping the edges according to their
automorphism orbits.

Given a graph $G=(V,E)$ and its non-edges $\bar{E}$, as well as some link-
prediction algorithm, we can consider the relevant partitioning of $\bar{E}$
into $k$ cells $C_{1}$, $C_{2}$, …, $C_{k}$. A cell might contain only
positive edges (i.e. only edges the link predictor should give a high score
to), only negative edges, or a mixture. It’s from mixed cells that performance
limits arise: since all elements in a mixed cell get the same score, they
cannot all have correct scores. For a cell $C_{i}$, we denote the number of
positives in the cell as $p_{i}$, the number of negatives in the cell as
$n_{i}$, and the the total number of elements in the cell as
$t_{i}=p_{i}+n_{i}=|C_{i}|$.

For a given partitioning $C_{1}$ through $C_{k}$, we prove in the Appendix
that the optimal ROC and AUPR scores a soft classifier can obtain equals the
ROC/AUPR scores obtained from a classifier
$\ell:\bar{E}\rightarrow\mathbbm{R}$ which satisfies the following property:

$\forall 1\leq i,j\leq k.\ \forall e\in C_{i},\ e^{\prime}\in C_{j}.\
\Big{(}\ell(e)\geq\ell(e^{\prime})\Big{)}\leftrightarrow\left(\frac{p_{i}}{t_{i}}\geq\frac{p_{j}}{t_{j}}\right)$
(1)

Note that within a cell $C_{i}$, the probability that an element is a positive
is just $\frac{p_{i}}{t_{i}}$. Thus a classifier that scores non-edges with
the probability they’re positives will get an optimal score – optimal given
the topological information that the algorithm uses to distinguish non-edges.

This property of optimal classifiers permits us to easily compute the maximal
ROC/AUPR scores that any algorithm could have obtained on a given dataset and
task. All we need to do is find the partitioning of non-edges into cells that
are topoligically equivalent given the data the link predictor has at hand.
Then we order those cells according to their density of positives (i.e.
according to $\frac{p_{i}}{t_{i}}$). Given that ordering, we use the standard
ROC and AUPR formulae to calculate what scores would be obtained by an optimal
classifier. We provide code both for proper AUPR calculation and for optimal
ROC/AUPR scores at https://github.com/SteveWillowby/Link_Prediction_Limits.

For the formulae below, assume that the cells $C_{1}$ through $C_{k}$ are
ordered such that $i\leq
j\rightarrow\frac{p_{i}}{t_{i}}\geq\frac{p_{j}}{t_{j}}$.

To give the ROC and AUPR formulae in terms of this partitioning, we need just
a bit more notation. Define cumulative sums $P_{0}=0$ and
$P_{i}=\sum_{j=1}^{i}p_{j}$ for $1\leq i\leq k$. Similarly, define cumulative
sums $T_{0}=0$ and $T_{i}=\sum_{j=1}^{i}t_{j}$ for $1\leq i\leq k$. And again,
$N_{0}=0$ and $N_{i}=\sum_{j=1}^{i}n_{i}$ for $1\leq i\leq k$. Define
$T=T_{k}$, $P=P_{k}$, and $N=N_{k}$. Note that $|\bar{E}|=T=N+P$ (total number
of non-edges = total number of things classified = negatives + positives). We
now get the following formula for ROC:

$\text{Max ROC}=\sum_{i=1}^{k}\frac{p_{i}}{P}\cdot\frac{N_{i}+N_{i-1}}{2N}$
(2)

The formula for AUPR is messier due to the need for proper interpolation
between precision-recall points discussed above in Section IV.2, but it is
still easy to calculate:

$\text{Max
AUPR}=\sum_{i=1}^{k}\frac{p_{i}}{P}\cdot\frac{p_{i}}{t_{i}}\cdot\left(1+\left(\frac{P_{i-1}}{p_{i}}-\frac{T_{i-1}}{t_{i}}\right)\cdot\ln\left(\frac{T_{i}}{T_{i-1}}\right)\right)$
(3)

Note that there are no division-by-zero issues with this formula due to the
following facts: When $p_{i}=0$, the entire expression becomes zero. Further
$t_{i}$ always $>0$. Lastly, when $T_{i-1}=0$, then $P_{i-1}=0$, and because
$\lim_{x\rightarrow 0^{+}}x\ln\frac{1}{x}=\lim_{x\rightarrow
0^{+}}x\left(\ln(1)-\ln(x)\right)=0$, we do not get a division by zero issue
with $T_{i-1}$.

Equipped with these formulae, we can now begin to calculate the maximum
possible performance scores on actual prediction tasks.

As we mentioned above, Average Precision (AP) is sometimes used to approximate
AUPR. However, the nice result we prove for ROC and AUPR concerning the edge
partioning order does _not_ hold for AP. Fortunately, our upper bound on AUPR
is also an upper bound on AP, so we can still upper-bound the AP scores that
one might obtain. We provide a short proof of this in the Appendix.

##  VI Methodology

Our main experiment is to calculate how maximum link prediction scores vary
with the amount of information given to an idealized algorithm. We run this
test on a wide variety of real-world graphs. The procedure runs as follows:

  1. 1.

Begin with a graph $G=(V,E)$ and an edge removal probability $p$ (we set
$p\leftarrow 0.1$).

  2. 2.

Define the set of negatives $N$ as all edges not in $G$.

  3. 3.

Remove each edge in $G$ with probability $p$ (independently) and add the
removed edges to the set of positives $P$. Call the resulting graph
$H\leftarrow(V,E\setminus P)$.

  4. 4.

Get a (hashed) canonical representation for each non-edge’s automorphism orbit
in $H$.

  5. 5.

Use the collected information to calculate the maximum scores via equations 2
and 3.

  6. 6.

Assign $k\leftarrow 1$.

  7. 7.

Get a (hashed) canonical representation of the $k$-hop neighborhood for each
non-edge in $H$ where the non-edge’s endpoints are given a distinct color from
the rest of the nodes.

  8. 8.

Use the collected information to calculate the maximum scores when using at
most $k$ hops of information about a non-edge.

  9. 9.

If the performance limit just obtained from step 8 is equal to (or within
0.005 of) the performance limit obtained from step 5, then stop. Otherwise,
assign $k\leftarrow k+1$ and go to step 7.

We perform the above procedure multiple times for each graph. Each iteration
corresponds to different, random possible sets of missing edges; each set of
missing edges can be slightly different in terms of the limit on its
predictability. We get the mean value and 95% confidence interval for each
distinct value of $k$.

We tested the link prediction limits on a wide variety of real-world graphs.
They are listed in Table 1.

Graph | Dir | Weighted | $|V|$ | $|E|$ | # SL | AD | CC | Diam | ASP
---|---|---|---|---|---|---|---|---|---
Species 1 Brain [1] | D | U | 65 | 1139 | 0 | 35.0 | .575 | 4 | 1.83
Highschool Friendships [2] | D | W | 70 | 366 | 0 | 10.5 | .362 | 12 | 3.90
Foodweb [2] | D | U | 183 | 2476 | 18 | 27.1 | .173 | 6 | 1.84
Jazz Collaboration [2] | U | U | 198 | 5484 | 0 | 55.4 | .617 | 6 | 2.22
Faculty Hiring (C.S.) | D | W | 206 | 2929 | 124 | 28.4 | .214 | 7 | 2.88
Congress Mentions [2] | D | W | 219 | 586 | 2 | 5.35 | .160 | 12 | 4.48
Medical Innovation [2] | D | U | 241 | 1098 | 0 | 9.11 | .210 | 9 | 3.26
C-Elegans Metabolic [2] | U | U | 453 | 2025 | 0 | 8.94 | .646 | 7 | 2.66
USA Top 500 Airports (2002) [3] | D | U | 500 | 5960 | 0 | 23.8 | .617 | 7 | 2.99
Eucore Emails [4] | D | U | 1005 | 24929 | 642 | 49.6 | .366 | 7 | 2.65
Roget Concepts [3] | D | U | 1010 | 5074 | 1 | 10.0 | .108 | 14 | 4.89
CCSB-YI1 [5] | U | U | 1278 | 1641 | 168 | 2.57 | .045 | 14 | 5.36
MySQL Fn. Calls [6] | D | U | 1501 | 4212 | 13 | 5.61 | .078 | 18 | 5.36
USA Airports (2010) [3] | D | U | 1574 | 28236 | 0 | 35.9 | .489 | 9 | 3.20
Collins Yeast [3] | U | U | 1622 | 9070 | 0 | 11.2 | .555 | 15 | 5.53
Cora Citation [1] | D | U | 2708 | 5429 | 0 | 4.01 | .131 | 15 | 4.53
Citeseer Citation [1] | D | U | 3264 | 4536 | 0 | 2.78 | .072 | 10 | 2.64
Roman Roads (1999) [3] | D | U | 3353 | 8870 | 0 | 5.29 | .025 | 57 | 25.3
USA Powergrid [3] | U | U | 4941 | 6594 | 0 | 2.67 | .080 | 46 | 19.0
Table 1: Graphs used for tests – The edge count does not include self-loops,
which are listed separately – Key: Dir = (Un)Directed, Weighted =
(Un)Weighted, # SL = # Self-loops, AD = Average Degree, CC = Average
Clustering Coefficient, Diam = Diameter, ASP = Average of all Shortest Path
Lengths –
Sources: [1]: networkrepository , [2]: konect , [3]: clauset2020colorado ,
[4]: snapnets , [5]: yu2008high , [6]: myers2003software

##  VII Results

###  VII.1 Sparsity Tends to Lower the Upper-Bound

We found that on most graphs, the upper bounds were near 100%, even when using
1-hop neighborhoods; we suspect that this is because when degrees are high
enough there is still a large number of possible 1-hop neighborhoods such that
the hypothetical optimal algorithm can take advantage of the slightest
difference between neighborhoods. However, we found that on the sparsest
graphs the results told a different and very interesting story.

$1$$2$$3$$0$$0.5$$1$Upper Bound on AUPR ScoreCora ML
Citations$1$$2$$3$$4$$0$$0.5$$1$Citeseer Citations$1$$2$$3$$0$$0.5$$1$Number
of Hops ($k$) of InformationUpper Bound on AUPR ScoreCCSB-
YI1$1$$2$$3$$4$$5$$6$$7$$0$$0.5$$1$Number of Hops ($k$) of InformationUSA
Powergrid

$1$$2$$0$$0.5$$1$AUPR Lim.Congress$1$$2$Roget$1$$2$MySQL$1$$2$Collins
Yeast$1$$2$Roman Roads

$1$$0$$0.5$$1$AUPR Lim.Species
1$1$Highschool$1$Foodweb$1$Jazz$1$Faculty$1$$0$$0.5$$1$Num. HopsAUPR
Lim.Medical$1$Num. HopsC-Elegans$1$Num. Hops500 Airports$1$Num.
HopsEucore$1$Num. HopsUSA Airports

Figure 2: Hard upper bounds on link prediction performance as it varies with
the amount of information given to a link prediction algorithm. The horizontal
line shows the limit when using the entire graph ($k=\infty$). Ten percent of
the graph’s edges were randomly selected as test edges. The multiple points at
a single value of $k$ are from different sets of randomly chosen test edges;
left-right jitter is employed to aid in visualization. Error bars are 95%
confidence intervals.

We show the results for the four sparsest graphs: the Cora and Citeseer
citation (sub)graphs, the CCSB-YI1 Protein-Protein Interaction graph, and a US
Powergrid network. The results are in Figure 2. In particular, we focus on the
AUPR values, because even though link prediction papers often report ROC
scores, link predictors can easily get large ROC scores due to the class
imbalance (the sheer number of non-edges) yang2015evaluating .

In summary, our results give good evidence that when data becomes sparse
enough, graph toplogy alone is severely limited in its ability to indicate a
difference between genuine and fake missing edges.

###  VII.2 Negative Sampling Methodologies Produce Artificially High Scores

We were curious to see how these fundamental limits compared to reports of
link prediction performance. As a small case study, we considered the seminal
Graph Convolutional Neural Network Auto-Encoder (GCNAE), a widely used and
referenced model that can perform topology-only link prediction
kipf2016variational . This will help us discern how well link predictors are
making use of the topology information available to them. Though this model is
a little bit “old” in the fast-paced world of graph neural networks, its
performance is still within just a few percentage points of modern GNN
performance chen2020simple ; fey2021gnnautoscale . In the original GCNAE
paper, the authors tested their model on undirected versions of the Cora and
Citeseer citation networks. They reported ROC scores and AP scores.

We found that the AP scores they reported for the Citeseer network were well
_above_ our upper bound, indicating that there was a difference in the
calculated AP. To understand this, we looked at the GCNAE code and found that
in its tests the number of negative edges was downsampled to one negative test
edge per positive test edge. This sort of downsampling is common when
performing link prediction evaluation with AP or AUPR; however downsampling
tends to boost the AP and AUPR scores significantly relative to what they
would have been if the full set of negatives was used in testing
yang2015evaluating . The GCNAE paper itself does not specify that downsampling
occurred.

By contrast, the paper’s reported ROC scores are well below our upper bound on
ROC. This makes sense as the ROC score is not affected by downsampling
yang2015evaluating . If we downsample the number of negative edges to one
negative edge per positive edge when calculating the AP limits, we get that
the GCNAE’s AP performance is also well below the upper bound. We show the
numeric results in Table 2.

The point of this case study is twofold. Firstly, a metric (e.g. AP) may have
different meanings depending on how it is used, and our methodology may be
able to help retroactively determine which approach was used if the original
paper does not specify.

Secondly, and perhaps of greater interest, state of the art link prediction
systems using the topology of a network do not reach the topology-based upper
limit on performance. We take this to suggest either that state of the art
link prediction systems have room for improvement in their use of graph
topology _or_ that what structurally differentiates the $k$-hop neighborhoods
of true edges from the $k$-hop neighborhoods of false edges in our tests is
basically noise that an algorithm should not pay attention to if it wishes to
generalize well. After all, if for example the 1-hop neighborhoods of two
different non-edges both have 20 edges per neighborhood and differ in only one
place, should we expect a link prediction algorithm to always treat that
difference as significant? We propose some future work in Section VIII.1 for
exploring how the upper limit on performance changes when the resolution of
the data is a bit blurrier, thereby reducing this noise.

Graph |  GCNAE ROC |  ROC Upper-Bound |  GCNAE AP |  AP Upper-Bound |  AP Upper-Bound (1:1 Downsampling)
---|---|---|---|---|---
Cora |  0.843 $\pm$ 2e-4 |  0.99992 $\pm$ 3e-5 |  0.881 $\pm$ 1e-4 |  0.903 $\pm$ 0.020 |  0.99999 $\pm$ 9e-6
Citeseer |  0.787 $\pm$ 2e-4 |  0.9981 $\pm$ 3e-4 |  0.841 $\pm$ 1e-4 |  0.686 $\pm$ 0.019 |  0.9989 $\pm$ 5e-4
Table 2: Comparison to the GCNAE’s Reported Results – The $\pm$ symbol
indicates the 95% confidence interval. We conclude that the GCNAE paper is
likely downsampling negative test edges in the process of calculating AP. More
importantly, once downsampling is factored in, there is a notable gap between
the hypothetical ideal performance and state of the art topology-based
performance. We discuss this more in Sec. VII.2. Note: These results are for
undirected versions of the graphs, whereas the results in Fig. 2 are for the
directed versions (GCNAE only does link prediction on undirected graphs).
Also, note that the version of Citeseer that the GCNAE paper used has some
extra nodes with no links, whereas the version we used for Fig. 2 does not.

####  VII.2.1 Confirming our Assumption

To verify that the discrepency between score and upper bound is indeed due to
downsampling negative edges, we ran the GCNAE code and obtained link
prediction scores when using all possible negative edges. The results
confirmed our hypothesis: When using the full set of negative test edges, the
average ROC scores we obtained for Citeseer and Cora ($\sim$77% and $\sim$84%
respectively) were similar to the paper’s reported results, but the average AP
scores were _much_ lower (just $\sim$1.2% and $\sim$1.4% respectively). These
extremely low scores do not mean that GCNAE is performing poorly, for true AP
is a much harsher and informative link prediction metric than ROC, and other
GNN models get similar scores on similar datasets yang2015evaluating ;
hibshman2021joint .

##  VIII Discussion

###  VIII.1 Applications, Extensions, and Limitations

In addition to the fact that our methodology gives insights about topology-
based link prediction, we believe the kind of analysis we offer in this paper
can be extended and expanded. We observed how maximum possible performance on
a particular binary classification task (i.e. link prediction) varies with the
amount of information available to the classifier. At a certain resolution,
inputs to the algorithm look identical. In our analysis, the differing
resolutions were the differing $k$ for the $k$-hop neighborhood subgraphs.
However, these resolutions could hypothetically be any reasonable
representation of the data.

If these kinds of equivalence partitions can be created at widely varying
resolutions for a classification tasks, then researchers will begin to be able
to say things like “our algorithm works as well on the full data as an optimal
algorithm would work on data of resolution $X$.”

The key ingredient for our analysis was that at a given resolution we were
able to partition the objects being classified (the non-edges) into cells of
equivalent objects; this let us calculate how well a hypothetical optimal
algorithm would perform on those cells. We were able to get this kind of
partitioning because our equality relation on two test objects was isomorphic
equivalence of the objects’ $k$-hop neighborhoods _and thus the relation was
transitive_. Yet we expect that even in cases where a transitive equality
relation is not immediately available, one could create such a relation by
using a distance measure to cluster test inputs and then defining equality as
being in the same cluster. The more fine-grained the clusters, the higher the
resolution of data given to the hypothetical optimal algorithm.

The main limit we are aware of for this kind of analysis is that at high data
resolution, noise can easily dominate the analysis. That is to say, at high
resolution, random noise tends to render each entity to be classified unique,
and thus the hypothetical, optimal algorithm with a perfect prior will be able
to correctly distinguish any two entities and get a perfect score.

For example, consider link prediction on pure noise: That is, consider the
process of randomly generating a graph where each edge is present
independently with some probability $p$ and then randomly hiding some fraction
of the edges to create a link prediction task. Such a random graph will likely
have no global symmetry erdHos1960evolution , so at high data resolution (e.g.
$k=3$) every non-edge will be unique and thus the hypothetical, optimal
algorithm with a perfect prior will obtain a perfect score, even though a
real-world algorithm that does not mystically foreknow the answer can do no
better than considering each edge to be equally likely, because that is in
fact how the graph was constructed.

Fortunately for our kind of analysis, real-world algorithms are usually
designed to ignore noise in the first place, so a data resolution that
successfully filters out noise can simultaneously be relevant and provide a
non-trivial upper bound on optimal performance.

###  VIII.2 Conclusion

We presented a methodology for calculating hard limits on how well a link
prediction algorithm could perform when using structural information only.
This helps analyze how much information graph structure does or does not
provide for link prediction. We found that very sparse graphs give rise to
significant inherent difficulties and therefore contain strong caps on optimal
performance.

We also observed that a state of the art topology-based link prediction method
performs well below the upper bound in some cases, which we believe either
means that the link prediction algorithms have serious room for improvement
_or_ that our test sometimes picks up on “noise” that indeed differentiates
edges from non-edges but which an algorithm should not be expected to pick up
on because that noise would not behave in any consistent or infer-able manner.
These observations prompted our discussion on further avenues of discovery and
extensions of our methodology; we expect that an analysis similar to ours
which finds a way to obtain performance upper bounds at varying degrees of
blurring the noise would provide further insights.

#### Acknowledgments

This work was funded by grants from the US National Science Foundation
(#1652492 and #CCF-1822939).

## References

  * (1) Andrés Abeliuk, Zhishen Huang, Emilio Ferrara, and Kristina Lerman.  Predictability limit of partially observed systems.  Scientific reports, 10(1):1–10, 2020.
  * (2) Lada A Adamic and Eytan Adar.  Friends and neighbors on the web.  Social networks, 25(3):211–230, 2003.
  * (3) Mohammad Al Hasan, Vineet Chaoji, Saeed Salem, and Mohammed Zaki.  Link prediction using supervised learning.  In SDM06: workshop on link analysis, counter-terrorism and security, volume 30, pages 798–805, 2006.
  * (4) Owen Astrachan.  Bubble sort: an archaeological algorithmic analysis.  ACM Sigcse Bulletin, 35(1):1–5, 2003.
  * (5) Christoph Bandt and Bernd Pompe.  Permutation entropy: a natural complexity measure for time series.  Physical review letters, 88(17):174102, 2002.
  * (6) Ginestra Bianconi, Richard K Darst, Jacopo Iacovacci, and Santo Fortunato.  Triadic closure as a basic generating mechanism of communities in complex networks.  Physical Review E, 90(4):042806, 2014.
  * (7) Guido Boffetta, Massimo Cencini, Massimo Falcioni, and Angelo Vulpiani.  Predictability: a way to characterize complexity.  Physics reports, 356(6):367–474, 2002.
  * (8) Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li.  Simple and deep graph convolutional networks.  In International conference on machine learning, pages 1725–1735. PMLR, 2020.
  * (9) Aaron Clauset, Ellen Tucker, and Matthias Sainz.  The colorado index of complex networks (2016).  URL https://icon. colorado. edu, 2016.
  * (10) Jörn Davidsen, Holger Ebel, and Stefan Bornholdt.  Emergence of a small world from local interactions: Modeling acquaintance networks.  Physical review letters, 88(12):128701, 2002.
  * (11) Jesse Davis and Mark Goadrich.  The relationship between precision-recall and roc curves.  In Proceedings of the 23rd international conference on Machine learning, pages 233–240, 2006.
  * (12) Paul Erdős, Alfréd Rényi, et al.  On the evolution of random graphs.  Publ. Math. Inst. Hung. Acad. Sci, 5(1):17–60, 1960.
  * (13) Matthias Fey, Jan E Lenssen, Frank Weichert, and Jure Leskovec.  Gnnautoscale: Scalable and expressive graph neural networks via historical embeddings.  In International Conference on Machine Learning, pages 3294–3304. PMLR, 2021.
  * (14) Joshua Garland, Ryan James, and Elizabeth Bradley.  Model-free quantification of time-series predictability.  Physical Review E, 90(5):052910, 2014.
  * (15) Justus Isaiah Hibshman, Daniel Gonzalez, Satyaki Sikdar, and Tim Weninger.  Joint subgraph-to-subgraph transitions: Generalizing triadic closure for powerful and interpretable graph modeling.  In Proceedings of the 14th ACM International Conference on Web Search and Data Mining, pages 815–823, 2021.
  * (16) Emily M Jin, Michelle Girvan, and Mark EJ Newman.  Structure of growing social networks.  Physical review E, 64(4):046132, 2001.
  * (17) Thomas N Kipf and Max Welling.  Variational graph auto-encoders.  NIPS Workshop on Bayesian Deep Learning, 2016.
  * (18) Peter Klimek and Stefan Thurner.  Triadic closure dynamics drives scaling laws in social multiplex networks.  New Journal of Physics, 15(6):063008, 2013.
  * (19) Jérôme Kunegis.  KONECT – The Koblenz Network Collection.  In Proc. Int. Conf. on World Wide Web Companion, pages 1343–1350, 2013.
  * (20) Jure Leskovec and Andrej Krevl.  SNAP Datasets: Stanford large network dataset collection.  http://snap.stanford.edu/data, June 2014.
  * (21) David Liben-Nowell and Jon Kleinberg.  The link prediction problem for social networks.  In Proceedings of the twelfth international conference on Information and knowledge management, pages 556–559, 2003.
  * (22) Kian-Ping Lim, Weiwei Luo, and Jae H Kim.  Are us stock index returns predictable? evidence from automatic autocorrelation-based tests.  Applied Economics, 45(8):953–962, 2013.
  * (23) Xin Lu, Erik Wetter, Nita Bharti, Andrew J Tatem, and Linus Bengtsson.  Approaching the limit of predictability in human mobility.  Scientific reports, 3(1):1–9, 2013.
  * (24) Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman.  Provably powerful graph networks.  Advances in neural information processing systems, 32, 2019.
  * (25) Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman.  Invariant and equivariant graph networks.  arXiv preprint arXiv:1812.09902, 2018.
  * (26) Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman.  On the universality of invariant networks.  In International conference on machine learning, pages 4363–4371. PMLR, 2019.
  * (27) Víctor Martínez, Fernando Berzal, and Juan-Carlos Cubero.  A survey of link prediction in complex networks.  ACM computing surveys (CSUR), 49(4):1–33, 2016.
  * (28) Brendan D McKay and Adolfo Piperno.  Practical graph isomorphism, ii.  Journal of symbolic computation, 60:94–112, 2014.
  * (29) Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe.  Weisfeiler and leman go neural: Higher-order graph neural networks.  In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 4602–4609, 2019.
  * (30) Christopher R Myers.  Software systems as complex networks: Structure, function, and evolvability of software collaboration graphs.  Physical review E, 68(4):046116, 2003.
  * (31) Technically, there is one counter-example to this claim which might be of interest to the theoretically-minded reader. Due to non-linearities in how link prediction scores are calculated, an algorithm that coordinates its predictions across edges might manage to increase the expected value of its link prediction score even though in some cases it will still perform worse than a permutation-invariant algorithm. For example, in Figure 1 an optimal algorithm meeting our assumptions would give edges $(v,u)$, $(v,r)$, $(v,t)$, and $(v,q)$ in the anonymized graph each a $\frac{1}{2}$ probability score of being an edge. A non-permutation-invariant algorithm could give edges $(v,t)$ and $(v,q)$ each a probability score of 1 and edges $(v,u)$, $(v,r)$ a score of zero; this kind of prediction would do better half the time (i.e. on half the anonymizations) and worse half the time, but might have a higher expected performance score overall. We consider this sort of case to be exotic enough that it is not relevant to our analysis.
  * (32) Paul Resnick, Yuqing Kong, Grant Schoenebeck, and Tim Weninger.  Survey equivalence: A procedure for measuring classifier accuracy against human labels.  arXiv preprint arXiv:2106.01254, 2021.
  * (33) Ryan Rossi and Nesreen Ahmed.  The network data repository with interactive graph analytics and visualization.  In Twenty-ninth AAAI conference on artificial intelligence, 2015\.
  * (34) Samuel V Scarpino and Giovanni Petri.  On the predictability of infectious disease outbreaks.  Nature communications, 10(1):1–8, 2019.
  * (35) Chaoming Song, Zehui Qu, Nicholas Blumm, and Albert-László Barabási.  Limits of predictability in human mobility.  Science, 327(5968):1018–1021, 2010.
  * (36) Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip.  A comprehensive survey on graph neural networks.  IEEE transactions on neural networks and learning systems, 32(1):4–24, 2020.
  * (37) Yang Yang, Ryan N Lichtenwalter, and Nitesh V Chawla.  Evaluating link prediction methods.  Knowledge and Information Systems, 45(3):751–782, 2015.
  * (38) Haiyuan Yu, Pascal Braun, Muhammed A Yıldırım, Irma Lemmens, Kavitha Venkatesan, Julie Sahalie, Tomoko Hirozane-Kishikawa, Fana Gebreab, Na Li, Nicolas Simonis, et al.  High-quality binary protein interaction map of the yeast interactome network.  Science, 322(5898):104–110, 2008.
  * (39) Fuqing Zhang, Y Qiang Sun, Linus Magnusson, Roberto Buizza, Shian-Jiann Lin, Jan-Huey Chen, and Kerry Emanuel.  What is the predictability limit of midlatitude weather?  Journal of the Atmospheric Sciences, 76(4):1077–1091, 2019.
  * (40) Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun.  Graph neural networks: A review of methods and applications.  AI open, 1:57–81, 2020.

##  Appendix A Appendix - Proofs

###  A.1 Maximum ROC

Let $k$ be the number of distinct inputs to the classifier (i.e. the number of
cells of isomorphically-equivalent non-edge types in the partition of non-
edges).

Further, let $s$ be a classifier that achieves an optimal ROC score for these
cells. Because ROC is calculated with respect to the different (true positive
rate, false positive rate) pairs obtainable by using different score
thresholds to convert a soft classifier into various hard classifiers, then
without loss of generality $s$ assigns a distinct score to each cell; if $s$
did not, then we could just consider the cells given the same scores as being
the same cell with a larger total size and larger number of positives.

As in Section V, let $t_{1},t_{2},...,t_{k}$ be the total sizes of the cells,
where the cells are ordered by the score $s$ gives to them ($t_{1}$ is the
total size of the cell with the highest score). Likewise, let
$p_{1},p_{2},...,p_{k}$ be the number of positives in the respective cells.
For notational convenience, we define $t_{0}=p_{0}=0$.

Let $T_{i}=\sum_{j=0}^{i}t_{j}$, $P_{i}=\sum_{j=0}^{i}$, and
$N_{i}=T_{i}-P_{i}$. Also define $T=T_{k}$, $P=P_{k}$, and $N=N_{k}$.

Assume for sake of contradiction that there exists an $i\in[k-1]$ such that
$\frac{p_{i}}{t_{i}}<\frac{p_{i+1}}{t_{i+1}}$. Now imagine an alternate
classifier $s^{*}$ that gives the exact same scores as $s$ except that it
reverses the scores for the $i$’th and $(i+1)$’th cells.

Then we get a new set of variables $t_{1}^{*},t_{2}^{*},...,t_{k}^{*}$ and
$p_{1}^{*},p_{2}^{*},...,p_{k}^{*}$ as well as corresponding
$T_{j}^{*},P_{j}^{*},\text{and }N_{j}^{*}$ where the values correspond to the
cells as ordered by classifier $s^{*}$. Due to the definition of $s^{*}$,
$t_{j}=t_{j}^{*}$ and $p_{j}=p_{j}^{*}$ for all $j$ except $j\in\\{i,i+1\\}$,
in which case $t_{i}=t_{i+1}^{*}$, $t_{i+1}=t_{i}^{*}$, $p_{i}=p_{i+1}^{*}$,
and $p_{i+1}=p_{i}^{*}$. Once again, for notational simplicity we pad the
beginning of these lists with $t_{0}^{*}=p_{0}^{*}=0$.

This gives us a total of $k+1$ (true positive rate, false positive rate) pairs
(i.e. (TPR, FPR) pairs). The false positive rate is the x axis of the curve
and the true positive rate is the y axis.

$\text{True Positive Rate }j\text{ for }s\ (\text{i.e.
TPR}_{j})=\frac{P_{j}}{P}\text{ for }j\in\\{0,1,...,k\\}$

$\text{False Positive Rate }j\text{ for }s\ (\text{i.e.
FPR}_{j})=\frac{N_{j}}{N}\text{ for }j\in\\{0,1,...,k\\}$

Likewise for $s^{*}$ we have:

$\text{True Positive Rate }j\text{ for }s^{*}\ (\text{i.e.
TPR}_{j}^{*})=\frac{P_{j}^{*}}{P}\text{ for }j\in\\{0,1,...,k\\}$

$\text{False Positive Rate }j\text{ for }s^{*}\ (\text{i.e.
FPR}_{j}^{*})=\frac{N_{j}^{*}}{N}\text{ for }j\in\\{0,1,...,k\\}$

The ROC curve then interpolates linearly between these points. Note that by
definition
$\text{TPR}_{0}=\text{TPR}_{0}^{*}=\text{FPR}_{0}=\text{FPR}_{0}^{*}=0$ and
$\text{TPR}_{k}=\text{TPR}_{k}^{*}=\text{FPR}_{k}=\text{FPR}_{k}^{*}=1$.

We can consider the interpolation between the $j$’th (TPR, FPR) point and the
$(j+1)$’th (TPR, FPR) point as corresponding to a variable $\alpha\in[0,1]$
where:

$\text{TPR}_{j,\alpha}=\frac{P_{j}+\alpha p_{j+1}}{P}$

$\text{FPR}_{j,\alpha}=\frac{N_{j}+\alpha(t_{j+1}-p_{j+1})}{N}$

This leads to the following:

$\frac{\text{d}}{\text{d}\alpha}\text{TPR}_{j,\alpha}=\frac{p_{j+1}}{P}$

and separately:

$\alpha=\frac{N\cdot\text{FPR}_{j,\alpha}-N_{j}}{t_{j+1}-p_{j+1}}$

$\frac{\text{d}}{\text{d}\text{FPR}_{j,\alpha}}\alpha=\frac{N}{t_{j+1}-p_{j+1}}$

Using the chain rule gives us:

$\frac{\text{d}}{\text{d}\text{FPR}_{j,\alpha}}\text{TPR}_{j,\alpha}=\frac{\text{d}\alpha}{\text{d}\text{FPR}_{j,\alpha}}\cdot\frac{\text{d}\text{TPR}_{j,\alpha}}{\text{d}\alpha}=\frac{N}{P}\cdot\frac{p_{j+1}}{t_{j+1}-p_{j+1}}$

For $s^{*}$’s curve this becomes:

$\frac{\text{d}}{\text{d}\text{FPR}_{j,\alpha}^{*}}\text{TPR}_{j,\alpha}^{*}=\frac{N}{P}\cdot\frac{p_{j+1}^{*}}{t_{j+1}^{*}-p_{j+1}^{*}}$

Now, because $t_{j}$ and $t_{j}^{*}$ only differ at $j=i$ and $j=i+1$, and the
same holds for $p_{j}$, etc., and because the values at $i$ and $i+1$ are the
reverse of each other, then we can conclude that the $(i-1)$’th TPR-FPR point
is the same for both $s$ and $s^{*}$ as well as the $(i+1)$’th point. The only
difference is at the $i$’th point. To see that the $(i+1)$’th point is the
same, note that
$P_{i+1}=P_{i-1}+p_{i}+p_{i+1}=P_{i-1}^{*}+p_{i+1}^{*}+p_{i}^{*}=P_{i+1}^{*}$.

Further, because $\frac{p_{i}}{t_{i}}<\frac{p_{i}^{*}}{t_{i}^{*}}$ we obtain
that $\frac{p_{i}}{t_{i}-p_{i}}<\frac{p_{i}^{*}}{t_{i}^{*}-p_{i}^{*}}$ which
in turn means that:

$\frac{\text{d}}{\text{d}\text{FPR}_{i-1,\alpha}}\text{TPR}_{i-1,\alpha}<\frac{\text{d}}{\text{d}\text{FPR}_{i-1,\alpha}^{*}}\text{TPR}_{i-1,\alpha}^{*}$

In other words, the slope leading from the $(i-1)$’th point to the $i$’th
point is greater in $s^{*}$’s ROC curve than in $s$’s. Since both curves up to
and including their $(i-1)$’th point are identical, and since they are also
identical at the $(i+1)$’th point and thereafter, this means that $s^{*}$’s
curve has a larger area underneath it.

Ergo, we obtain a contradiction, for $s^{*}$ obtains a higher ROC score than
$s$. Thus the assumption must have been false. This means that $s$ orders the
cells such that $\frac{p_{j}}{t_{j}}>\frac{p_{j+1}}{t_{j+1}}$ for all
$j\in[k-1]$. In other words, $s$ completely sorts the cells as we intended to
show. $\hbox{}\nobreak\hfill\square$

###  A.2 Maximum AUPR

Davis and Goadrich have shown that if one ROC curve dominates another, then
the corresponding (properly interpolated) precision-recall curves yield the
same dominance [11]. Thus the AUPR result follows directly from our ROC result
above.

###  A.3 Maximum AP vs. Maximum AUPR

The nice ordering property we prove for ROC and AUPR does not hold for AP. For
example, consider the following three cells with number of (positives,
negatives) total: $\langle(10,0),(2,2),(9,7)\rangle$. Ordering these in
decreasing $\frac{\text{Positives}}{\text{Positives}+\text{Negatives}}$ yields
an AP of approximately 0.856 whereas ordering them in the order listed yields
an AP of approximately 0.858.

Fortunately, we can still calculate a hard upper limit on AP scores by simply
using the upper limit on the AUPR score. Remember our ordering rule for an
optimal curve: Order by
$\frac{\text{Positives}}{\text{Positives}+\text{Negatives}}$ in a descending
order. Remember also that via the ROC and AUPR proofs, we showed that given
_any_ AUPR curve obtained by some ordering of the cells where some pair of
cells disobeyed our ordering rule, you could get an AUPR curve that
_dominates_ it by swapping the ordering of the incorrect pair. Now, observe
that any curve which does not follow the ordering rule can be converted into
the curve that does by a succession of swaps where the swaps are of adjacent,
incorrectly ordered cells; this corresponds to the naive “bubble sort”
algorithm [4]. During this process of swaps, each new curve dominates the
former. Given that the last curve is the one corresponding to our ordering, it
follows that our optimal curve not only has a larger area underneath it than
any other curve, but it also _dominates_ any other curve. Last but not least,
note that if you follow the optimal AUPR curve from right to left (i.e. from
recall of 1 to recall of 0) that the curve never decreases in precision.

Now let us turn our attention to AP curves. Recall that an AP curve is
obtained in a very similar manner to an AUPR curve. In both cases you first
get a collection of precision-recall points given the ordering the classifier
gives to the cells (we call these precision-recall points the “base points”);
the only difference between AP and AUPR is in how the two kinds of curves
interpolate between adjacent base points. AP curves interpolate between any
two precision-recall points by using the precision from the point with the
higher recall.

We can observe two things: First, given our observations about the optimal
AUPR curve, regardless of the ordering of the cells used to get the base
points, all the base points of the AP curve are either on or are strictly
dominated by the points in the optimal AUPR curve. Second, as you move from
right to left along the interpolated AP points, the precision value remains
constant until you hit a new base point. By contrast, as we discusse above the
optimal AUPR curve’s precision value is either constant _or increasing_ as you
move from right to left. Thus any AP curve is always dominated by the ideal
AUPR curve. $\hbox{}\nobreak\hfill\square$