Inherent Limits on Topology-Based Link Prediction
Authors: Justus Isaiah Hibshman
Tim Weninger
Venue: Accepted by TMLR ()

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.

Published in Transactions on Machine Learning Research (06/2023)
Inherent Limits on Topology-Based Link Prediction
Justus Isaiah Hibshman
jlvbshraa Crd edu
Department of Computer Science and Engineering University of Notre Dame
Tim Weninger
tweninger@nd.c edu
Department of Computer Science and Engineering University of Notre Dame
Reviewed on OpenReview: Atips: // openreview. net/ formfo id- 1zL.38dPu.1
Abstract
Link prediction systems (e.g. recommender systems) typically use graph topology as one of their main sources of information. However, automorphic symmetries in graphs limit how informative topology is for link prediction. We calculate hard upper bounds on how well graph topology alone enables link prediction for wide variely of real-world graphs. We find that in the sparsest of these graphs the upper bounds are surprisingly low, thereby demonstrating that prediction systems sparse graph data inherently limited and require information in addition to the graph topology.
1 Introduction
Graph-based link prediction systems are widely used recommend wide variety of products and services. Whenever shopping website predicts what you will buy next based what you and others like you have previously bought, that's link prediction. Whenever 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 suffi- cient 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 lopology; whenever graph possesses symmetries (t.e. automorphisms) in its topology, then the graph's 's topology does not contain enough information to guarantec correct selection of the missing edges. This raises two foundational questions in machine learning on graphs:
1. What are the inherent limits graph structure's predictability?
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 graph's topology alone can provide to link prediction algorithm; that forms one kind of inherent limit on structure's predictibility. In particular, 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 oers can begin to answer question 2 by comparing contemporary link prediction systems' scores to these upper bounds.
calculate hard upper limits how well algorithm using only
To caleulate an upper bound that will hold regardless of the link prediction algorithm used, we calculate upper limit on the performance of an idealized algorithm presented with much information about the

---

Published in Transactions on Machine Learning Research (06/2023)
Original Graph with Three Hidden Links
Same Graph Anonymized and with Three Links Removed
Three of Eight Equally Valid Reconstructions
b
b
q
e
Toy example graph with three held-out edges for what we call the known-topology link prediction task. The link predictor knows that must pick edges (a, b), ea, and (e, f), but does not know for certain which nodes in the anonymized graph correspond to b, G, e, J. In this case, there exist eight equally plausíble 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.
Figure 1:
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 ro-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. Imagine you shown both link prediction task and the answer to the same task (i.e. the links one must predict); in Fig, | the solution edges are (a,b), (a,e), and 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 f), but you do not know for certain which node e nor which node is f.
The anonymized graph is, by itself, effectively identical to the data that algorithm would be given for the regular link prediction task. We call the task of doing link prediction the anonymized graph after having seen the un-anonymized solution the knowve-lopooogy link prediction lask. As we hinted above, and Figure shows, symmetries in the graph can render several possible rdge-predictions structurally identical and therefore equally valid. It is from these symmetrics that performance is limited even on the known- topology task.
Of course, in practice, most systems will perform much worse 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, simple model like triadic closure assumess that the likelihood of an edge is proportionate to the number of triangles the edge would be involved in (Bianconi et al. (2014); Klimek & Thurner (2013); Jin et al. (2001); Davidsen et al. (2002)). 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 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 knoon-topology link prediction task because it enables to establish limits that exists in the data itself, without making any assumptions about the link prediction algorithm.
After discussing some related work in Section 2 and defining our formalisms in Section 3 we discuss some formal properties of link predictors as well as quantitative link prediction evaluation metrics (ROC and AUPR) in Scction 4 Scction 5 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 performance for the standard
2

---

Published in Transactions on Machine Learning Research (06/2023)
version of the task. We leave the proof that our formula gives the maximum in the Appendix. In Section + 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 prodiction algorithm only uses a subset of its available information (a k-hop neighborhood) lo predict whether a link will appear. Section 7 shows our results. We find that on sparse graphs commonly used for link prediction, the limits are surprisingly low. Then Section 7.2 we observe how famous graph neural network's reported results are above the performance limits and discuss how this is likely due to common mistake in correctly measuring AUPR. Lastly, we discuss ways to generalize our analysis in Section g
2
Related Work
2.1 Link Prediction
The link prediction task is widely studied, almost to the point of being ubiquitous for graph research. It was introduced by Liwen-Nowell & Kleinberg (003)) Given 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 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 (Jin et al.
(2001b; 0s Davidsen et al. (2002]; Klimek & Thurner (2013 Bianconi et al. [0044] Adamic & Adar (2003)) )
Then, following the historical trend of machine learning in general, link prediction models grew in complexity
both in their features and in their classifiers (A) Hasan et al. (2006): Martínez et al. (2016) until neural
networks eventually began to outperform other methods (Zhou et al. (2020); Wu et al. (2020)
2.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 prodictability of timo-series data degrades as the amount of data available decreases; they quantify predictability signal self-correlation, Permutation entropy has also been found to be useful to measure predictability in ecology and physics, and
terms of permutation entropy and well actual prediction performance of specific models (Abeliuk al. (2020) ).
celffaato)-orrreaation in finance (Abeliuk et al. 20200 Bandt & Pompe (002)) Garland et al. (2014] Lim
et al. 2013)).
Scholars have also analyzed predictability limits in other domains. For instance, some have used notions of entropy to measure predictability limits on human travel (Lu et al. (013)) Song et al. (2010)) and disease outbreaks (Scarpino & Petri (2019)). Predictability related to system complexity and chaos (Boffetta) et al. (002)). For instance, minute uncertainties on initial conditions can greatly limit one's ability to make
accurate weather forecasts (Zhang et al. (2019)).
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 (Resnick et al. 2. 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 symmetrics within the input data.
3

---

Published in Transactions on Machine Learning Research (06/2023)
3 Formalisms
3.1 Graphs
We represent a graph G as G = (V, E') where V is the set of vertices (í.e. nodes) and E is the set of edges. The edges are pairs of verticos. If the graph's connections are considered to have a direction, we say that E S V x and that the graph's non-edges are (V V) E. If the connections do not have a direction, then the edges are unordered pairs: S [{a,b] (a.
V}. However, for simplicity, it standard always write (a, b) rather than {a, 63 even when talking about undirected graphs. An edge of the form (a, a) is called self-loop.
3.2 Isomorphisms
Given two graphs G1 = (V1, E1) and G2 = (V2, E2), we say that they are isomorphic if there exists a way to align the two graphs' vertices so that the structures overlap perfectly. Formally, G1 and G2 are isomorphic (expressed
G1 = G2) if there exists a bijection between the vertices f V1 - V/2 such that (a,b) E Ei + (f(a), f(b)) Eg. In this case the function called an isomorphism. In this paper, whenever refer to two graphs as being equivolent identical we mean that they are isomorphic.
If f is an isomorphism between two graphs G1 and G2 we will sometimes denote this as G1 2 Gz.
3.3 Automorphism Orbits
Within the context of a single graph, the antomorphism orbit 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 the data in way distinguishes between the two objects.
An automorphism of graph is an isomorphism of the graph with itself. That is, an automorphism of graph G = (V,E) E) is a bijective function f V + V such that:
E (f(a), E
The set of all automorphisms of a graph G form the automorphism group of the graph and is denoted 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 vertex Aut(G)). Similarly, the orbit of an edge e = (a, b) in graph G the set AOo(e) ((f(a). f Aut Note that AOo(a) and AOa(e) due to the trivial automorphism f(x)
graph is the set AO = {f(a) f e
We can consider the orbits of non-eristent edges (L.e. non-edges). Let (a, b) & E be an edge which is not in G. We can still define the orbit of (a, b) to be (f((), I Aut(G)). These orbits are collections of edges not in G which are equivalent to each other given G.
3.4 Induced Subgraphs
Given graph G (V, E) and subset of the graph's vertices S V, can define G's induced subgraph S to be graph with S as its nodeset and the edges in G that connect nodes in S, Formally: G(S) (S, ((a,b) b) (a,b) EAGESADESS
3.5 K-hop Walks
Given two vertices x, y E V, a ke-hop walk from to y is a sequence (Wo, W1, W2, 11 1, Wx) where x wig. y = wk. and (x)-1,24) E E for all i from to k. For convenience, we define a "zero-hop" walk to be a single-node "sequence" (wo), representing "no-steps-taken" journey from to itself.

---

Published in Transactions on Machine Learning Research (06/2023)
3.6 K-hop Neighborhoods
In practice, most link prediction algorithms do not use the entire graph when prodicting the probability of edge membership. Rather, they lend to use local context. We formalize one intuilive 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 lo steps (aka "hops") across odges for some value k. We can express this formally as follows:
Given a node x V,, we define its k-hop neighborhood nodes N₂(x)) to be the set of all nodes within & fewer steps of z. Formally, Nx(x)= = {y There exists I-hop walk from to y where / 1 k).
When we consider an edge or non-cdge (a, we define its k-hop neighborhood nodes to be the union of the two endpoints' k-hop neighborhood node sets: Na((a, b)) (a( U (b).).
Finally we can define the k-hop neighborhood subgraph (or simply "k- hop neighborhood") for an edge or non-odge e = (a, b). It is the induced subgraph on e's k-hop neighborhood nodes: Gx(e) = G(Nx(e)).
3.7 Anonymized Graphs
Given a graph G = 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 क + V; your anonymized graph then H (V, {(T(A), (a, e E}).
3.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 canonical form is used by practical graph isomorphism algorithms such as Nauty and Traces (McKay & Piperno (2014)); they work by first converting two graphs G1 and G2 canonical forms Cj and C2 respectively, then perform a trivial check to see Ci and C2 identical.
In other words, canonical forms 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 is A(G).
4 Link Predictors and Their Evaluation
4.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 be the set of non-edges G; that is, E {(a, b) a, e E}. A hard link predictor (i.e. hard binary classifier) for G and É is a function E: E (Positive, Negative) that gives non-edge label (Positive/Negaaivve) A soft link predictor (i.e. soft binary classifier) for G and E is function é: E + R that gives 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-ert non-egees 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 threshold value and giving all entities with score 2 the Positive label and all others the Negative label.
5

---

Published in Transactions on Machine Learning Research (06/2023)
4.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 ultimately a bound on all link predictors.
Our key assumption is that whenever link predictor uses graph topology information I to give edge score, it would have given edge the exact same score if any of the graph nodes in / had been labeled differently. In other words, the predictor's output is permutation-invarian
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 inntuttttioo-inaaianttt can get a better score than an algorithm that is ioauutation-invarian
Casc 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 impul (and would have performed worse given different arbilrary 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 avaílable in real-world link prediction scttings (e.g. a sales website cannot use node ordering based on what products you will buy).
Concerning Case 2: The possibility that an algorithm could get lucky is not meaningful counter-example to performance limit
Consequently, our performance bound is effectively a bound for all link prediction algorithms not just permutation-invariie 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-invarian Much of the GNN research 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 (Morris et al. (2019h) whereas our work in this paper asks what limits are in the data itself regardless of which architecture is used.
architectures enable networks to do (Maron al.) (2019b 2018)).
4.1.2 Edge Equivalence
Our assumption from Section 4.1.1 could be rephrasod as, "If a link predictor 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, can partition edges into cells based on whether not link predictor is given the same information about the edges same information ++ same cell.
When a link predictor 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 G's topology in no way distinguishes between the two. Formally, this means that two edges are guaranteed get the same score if they are in the same automorphism orbit: 61 E (02(ee) f(e))= f(e2)
local context surrounding edge to give it score rather than using the entire graph context. If we assume that 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
Often, link predictors
Teehhiiallyy there is counter-cxample to this claim which might be of interest to the thooretically-minded reader. Due to non-linearitien in how link prediction scores are calculated, 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 permutation-invariint algurithm. For example, Figure I an optimal algorithm meeting our usumptions would give edges (v,a), (e,r), (v, (), and (e.g) in the anonymized graph each probability score of being edge. A non-perrmatation-nnaaaial algorithm could give odges (v,t) and (e, g) each a probability score of 1 and edges (v, a), (v,r) a score of zero; this kind of prediction would do better half the time (Le. half the anonymizations) and worse half the time, but might have higher expected performance score overall. We consider this of case to exotic enough that it relevant. to our analysis.

---

Published in Transactions on Machine Learning Research (06/2023)
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: (3f. Ge(E1) y Gk(e2) A(e))) = 62) - f(e)) = f(e2)
Note that by definition e₁ E AOa(e2) implies (3f. Gk(E1) E5 Gx(ez) f(ei) ((ei) = e2) 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.
4.2 Performance Scores for Link Predictors
In practice, almost all link prediction classifiers are soft classifiers. There are number of nuances to how these classifiers are scored that are worth highlighting here.
Remember that 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 prodictors it offers. This can be mcasured in terms of diffcrent 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-Reeit curve and its corresponding metric of Area Under the Precision-Reced curve (AUPR). For an in-depth analysis exploring the relationship between ROC curves and Precision-Recal curves, we recommend the paper by Davis & Goadrich (2006).
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 new hard classifier. This can be done by picking value [0, 1] and tossing a-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 Recall space, because hard classifiers cannot be combined to get precision-recall pairs that interpolate linearly (Davis & Goadrich| (2006)).
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).
5 Optimal Prediction Performance
Here we offer the actual formulae for calculating the optimal ROC and AUPR scores soft classifier can obtain.
Recall from Section 4.1.1 that there will be some edges which are topologically identical to each other and thus which will each 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 4.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 cach other 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 G E) and its non-edges E, as well as some link-prediction algorithm, we can consider the relevant partitioning of E into & cells C1, C2,, Ck- 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 a mixed cell get the same score, they cannot all have correct scores. For a cell C,, we denote the number of positives in the cell as ps, the number of negatives in the cell ni, and the the total number of elements in the cell as 4 = Pt n4 = [Ca]
7

---

Published in Transactions on Machine Learning Research (06/2023)
For given partitioning C through Ck. prove in the Appendix that the optimal ROC and AUPR scores soft classifier can obtain equals the ROC/AUPR scores obtained from classifier e: F -> I which satisfies the following property:
visijsk e Cn e' C' (e(e) 2 e(e))
Pi 4 1j
Pj
(1)
Note that within cell C₁ the probability that an element is a positive just P: Thus a classifier that scores non-odges with the probability they're positives will get 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 makes use of. Then we order those cells according to their density of positives (É.e. according to ).) 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: //githb..co com www.:/tteeeillowwyyoooooooooeeee
Prediction_ Limitss
For the formulae below, assume that the cells C through C. are ordered such that i S 2 1
To give the ROC and AUPR formulae in terms of this partitioning, need just bit more notation. Define cumulative sums Po 0 and P: = Σj= Pj for 1 < < k. Similarly, define cumulative sums To 0 and T, = ンjー t for $ < k. And again, No = 0 and N; = Σラ n, for < S k. Define T = Tk, P = Pk. and N NA. Note that |Ra = N (total number of non-edges total number of things classified negatives + positives). We now get the following formula for ROC:
Max ROC
Σ
k N
P:
+
N
(2)
P
2N
The formula for AUPR is messier due to the need for proper interpolation between precision-recal points discussed above in Section 4.2 but it. still easy to calculate:
Max AUPR =
Σ
Pi Pi P
[+
P
Ti-1
In
T T
(3)
l
pi
li
Note that there division-by- twvision-yyzzero issues with this formula due to the following facts: When p: 0, the entire expression becomes zero. Further t; always > O. Lastly, when T;-1 = 0, then P,-1 0, and because lim x In _ lim (In(1) - In(x)) 0, we do not get a division by zero issue with T;-1-
Equipped with these formulae, we can now begin to calculate the maximum possible performance scores on actual prediction tasks.
As mentioned above, Average Precision (AP) is sometimes used approximate AUPR. However, the nice result 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.
6 Methodology
Our main experiment calculate how maximum link prediction scores vary with the amount of information given an idcalized algorithm. We run this test on a wide variety of real-world graphs. The procedure runs follows:
8

---

Published in Transactions on Machine Learning Research (06/2023)
Graph
Dir
Weighted
[V]
[
#
SL
AD
CC
Diam
ASP
Species 1 Brain
D
U
65
1139
0
35.0
.575
1.83
Highschool Friendships 2
D
W
70
366
0
10.5
.362
12
3.90
Foodweb 2
D
0
183
2476
18
27.1
.173
1.84
Jazz Collaboration 2
U
0
198
5484
0
55.4
.617
2.22
Faculty Hiring (C.S.)
D
W
206
2929
124
28.4
.214
2.88
Congress Mentions 22
D
W
219
586
2
5.35
.160
12
4.48
Medical Innovation [2]
D
U
241
1098
0
9.11
.210
3.26
C-Elegans Metabolic 2
U
U
453
2025
0
8.94
.646
2.66
USA Top 500 Airports (2002)
(3]
D
U
500
5960
0
23.8
.617
2.99
Eucore Emails [4]
D
U
1005
24929
642
49.6
.366
2.65
Roget Concepts [3]
D
U
1010
5074
1
10.0
.108
14
4.89
CCSB-YII [5]
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)
D
U
1574
28236
0
35.9
.489
3.20
Collins Yeast [3]
U
U
1622
9070
0
11.2
.555
15
5.53
Cora Citation
D
U
2708
5429
0
4.01
.131
15
4.53
Citeseer Citation
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
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 = (UneDirected, Weighted = (Un) Weighted, # SL = # Self-loops, AD = Average Degree, CC =
Average Clustering Coefficient, Diam Diameter, ASP Average of all Shortest Path Lengths
Sources: [1]: Rossi Ahmed (2015 []]: Kunegis 2013),
[3]: Clauset et al. 2016). [4]: Leskovec & Krevl
(2014h, [5]: Yu et al. (2008), [6]: Myers (2003)
Begin with graph G (V, and an edge removal probability p (we set p + 0.1).
Define the set of negatives N as all edges not in G.
3. Remove each edge in G with probability (independently and add the removed edges to the set of positives P. Call the resulting graph H + (V,E) P).
4. Get (hashod) canonical representation for each non-edge's automorphism orbit in H.
Use the collected information to calculate the maximum scores via equations and
6. Assign & t-1
7. Get (hashed) canonical representation of the k-hop neighborhood for each non-edge in H where the non-edge's endpoints given distinct color from the rest of the nodes.
Use the collected information to calculate the maximum scores when using at most hops of infor- mation about non-edge.
the performance limit just obtained from step S is equal to (or within 0.005 of) the performance limit obtained from step 5. then stop. Otherwise, assign <- le + and go 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 prodictability. We get the mean value and 95% confidence interval for each distinct value of
We tested the link prediction limits wide variety of real-world graphs. They are listed in Table 1

---

Published in Transactions on Machine Learning Research (06/2023)
7 Results
7.1 Sparsity Tends to Lower the Upper-Bound 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, found that on the sparsest graphs the results told different and very interesting story.
We show the results for the four spansest graphs: the Cora and Citeseer citation (sub)graphs, the CCSB-YI YTI 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 prodiction papers often report ROC scores, link predictors can easily get large ROC scores due to the class imbalance (the sheer number of non-edges) (Yang) et al. 2015
In summary, our results give good evidence that when data becomes sparse cnough, graph toplogy alone is severely limited in its ability to indicate a difference between genuine and fake missing edges.
7.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 (Kipf & Welling (2016)
This will help us discern how well link predictors are making use of the topology information available to them. Though this model is 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 (Chen et al. (2020):
Fey et al. (222)) ). In the original GCNAE paper, the authors lested 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 Citescer network were well above our upper bound, indicating that there was 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 (Yang et al. (2015)). 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 (Yang et al. (2015)). If we downsample the number of negative edges to one negative edge per positive edge when calculating the AP limits, we get that the GCNAF'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 lests 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 link prediction algorithm to always treat that difference as significant? We propose some future work in Section 8.1 for exploring how the upper limit on performance changes when the resolution of the data is bit blurrier, thereby reducing this noise.
10

---

Published in Transactions on Machine Learning Research (06/2023)
Cora ML Citations
Citeseer Citations
Upper Bound on AUPR Score
1
1
0.5
0.5
0
0
2
1
2
CCSB-YIL
USA Powergrid
Upper Bound on AUPR Score
1
1
0.5
0.5
0
2
3
1
3
4
6
Number of Hops (k)) of Information
Number of Hops (I:) Information
Congress
Roget
MySQL
Collins Yeast
Roman Roads
AUPR Lim.
0.5
0
2
2
2
2
2
Species
Highschool
Foodweb
Jazz
Faculty
AUPR Lim.
0.5
1
1
Medical
C-Elegans
500 Airports
Eucore
USA Airports
AUPR Lim.
0.5
1
1
1
Num. Hops
Num. Hops
Num. Hops
Num. Hops
Num. Hops
Figure 2: Hard upper bounds link prediction performance it varies with the amount of information given to link prediction algorithm. The horizontal line shows the limit when using the entire graph (k: oo). 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.
11

---

Published in Transactions on Machine Learning Research (06/2023)
Graph
GCNAE ROC
ROC Bound
Upper-
GONAE AP
AP Bound
Upper-
AP Upper-Bound
(1:1 Downsampling)
Cora
0.843 + 2e-4
0.99992 + 3e-5
0.881 E le-4
0.903 + 0.020
0.99999 + 9e-6
Citeseer
0.787 = 2e-4
0.9981 = 3e-4
0.841 + le-4
0.686 + 0.019
0.9989 = 5e-4
Table 2: Comparison to the GCNAF's Reported Results The + 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 notable gap between the hypothetical ideal performance and state of the art topology-based performance. We discuss this more in Soc. 7.2 Note: These results are for undirected versions the graphs, whereas the results in Fig, 2 are for the directed versions (GCNAD AE 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.
7.2.1 Confirming 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 (~77% and ~84% respectively) were similar to the paper's reported results, but the average AP scores were much lower (just ~1.2% and ~..4% respectively). These extremely low scores do not mcan that GCNAE is performing poorly, for true AP is much harsher and informative link prediction metric than ROC, and other GNN models get similar scores on similar datasets (Yang et al.
(015 Hibshman et al. 2021
8 Discussion
8.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 particular binary classification task (ie. link prediction) varies with the amount of information available to the classifier. At 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 algorithun 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 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 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 relation by using a distance measure cluster test inputs and then defining equality 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 casily 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 graph where each edge is present independently with some probability p and then randomly hiding some
12

---

Published in Transactions on Machine Learning Research (06/2023)
fraction of the edges to create link prediction task. Such random graph will likely have global symmetry (Erdós et al. (1960)), 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 cach edge to be equally likely, because that 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, data resolution that successfully filters out noise can simultancously be relevant and provide non-trivial upper bound optimal performance.
8.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 optimal performance.
We also observed that a state of the art topology-base 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 way to obtain performance upper bounds at varying degrees of blurring the noise would provide further insights.
Acknowledgments
This research is supported by grants from the US National Science Foundation (#1652492 and # 1822939))
Thank you to the reviewers for their thoughtful feedback.
References
Andrés Abeliuk, Zhishen Huang, Emilio Ferrara, and Kristina Lerman. Predictability limit of partially observed systems. Scientific reports, 10(1):1-11) 10, 2020.
Lada A Adamic and Eytan Adar. Friends and neighbors on the web. Social networks, 25(3):211 230, 2003.
Mohammad Al Hasan, Vineet Chaoji, Saced Salem, and Mohammed Zaki. Link prodiction using supervisod learning. In SDM06: workshop on link analysis, counter-terrorism and securily, volume 30, pp. 798 805, 2006.
Owen Astrachan. Bubble sort: an archaeological algorithmic analysis. ACM Sigese Bulletin, 35(1):1-5, 2003.
Christoph Bandt and Bernd Pompe. Permutation entropy: a natural complexity measure for time series. Physical review letters, 88(17):174102, 2002.
Ginestra Bianconi, Richard K Darst, Jacopo lacovacci, and Santo Fortunato. Triadic closure as a basic generating mechanism of communities in complex networks. Physical Review E, 90(4):042806, 2014.
Guido Bolfetta, Massimo Cencini, Massimo Falcioni, and Angelo Vulpiani. Predictability: way to charac- terize complexity. Physics reports, 356(6):367-41) 2002.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International conference on machine learning, pp. 1725 1735. PMLR, 2020.
Aaron Clauset, Ellen Tucker, and Matthias Sainz. The colorado index of complex networks (2016). URL hllps:/ /icon. colorado. edu, 2016.
13

---

Published in Transactions on Machine Learning Research (06/2023)
Jörn Davidsen, Holger Ebel, and Stefan Bornholdt. Emergence of small world from local interactions: Modeling acquaintance networks. Physical review letters, 88(12):128701, 2002.
Jesse Davis and Mark Goadrich. The relationship between precision-recall and roc curves. In Proceedings of the 23rd international conference on Machine learning, pp. 233 240, 2006.
Paul Erdös, Alfred Rényi, et al. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5 (1):17-60, 60, 1960.
Matthias Fey, Jan E. Lenssen, Frank Weichert, and Jure Leskovec. Gnnautoscale: Scalable and expressive graph neural networks via historical embeddings. International Conference on Machine Learning, pp. 3294 3304. PMLR, 2021.
Joshua Garland, Ryan James, and Elizabeth Bradley. Model-free quantification of time-series predictability. Physical Review E, 90(5))052910, 2014.
Justus Isaiah Hibshman, Daniel Gonzalez, Satyaki Sikdar, and Tim Weninger. Joint subgraph-to--subraap transitions: Generalizing triadic closure for powerful and interpretable graph modeling. In Proceedings of the 14th ACM International Conference on Web Search and Dala Mining, pp. 2021.
Emily M Jin, Michelle Girvan, and Mark EJ Newman. Structure of growing social networks. Plysical review E, 64(4)004 2001.
Thomas N Kipf and Max Welling. Variational graph auto-cncoders. NIPS Workshop on Bayesion Deep Learning, 2016.
Peter Klimek and Stefan Thurner. Triadic closure dynamics drives scaling laws in social multiplex networks. New Journal of Physics, 15(6):063008, 2013.
Jérôme Kunegis. KONECT The Koblenz Network Collection. In Proc. Int. Conf. on World Wide Web Companion, pp. 1343 1350, 2013. URL http:://a) acm. www.eorgggiiioo org/citation. cfm?id=2488817
Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. stanford. edu/data, June 2014.
David Liben-Nowell and Jon Kleinberg. The link prediction problem for social networks. Proceedings of the twelfth international conference on Information and knowledge managemend, pp. 556 559, 2003.
Kian-Ping Lim, Weiwei Luo, and Jae Kim. Are us stock index returns predictable? evidence from automatic autocorrelation-base tests. Applied Economics, 45(8):953 962, 2013.
Xin Lu, Erik Wetter, Nita Bharti, Andrew J Tatem, and Linus Bengtsson. Approaching the limit of pre- dictability in human mobility. Scientific reports, 3(1):1-9, 2013.
Haggai Maron, Heli HammH Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. arXiv preprint ar Xio: 1812. 0.0902, 2018.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances in neural information processing systems, 32, 2019a.
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. In International conference on machine learning, pp. 4363-4333333 4371. PMLR, 2019b.
Victor Martínez, Fernando Berzal, and Juan-Carlos Cubero. survey of link prediction in complex networks. ACM computing surveys (CSUR), 49(4):1-33, 2016.
Brendan D McKay and Adolfo Piperno. Practical graph isomorphism, ii. Journal of symbolic computation, 60:94-112, 2014.
14

---

Published in Transactions on Machine Learning Research (06/2023)
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, pp. 4602 2209, 2019.
Christopher R Mycrs. Software systems as complex networks: Structure, function, and evolvability of software collaboration graphs. Physical review E, 68(4):046116, 2003.
Paul Resnick, Yuqing Kong, Grant Schoenebeck, and Tim Weninger. Survey equivalence: A procedure for measuring classifier accuracy against human labels. orXiv preprint arXiv:2106.01255 2021.
Ryan Rossi and Nesreen Ahmed. The network data repository with interactive graph analytics and visualization. In Tiitty-ninth AAAI conference on artificial intelligence, 2015. URL https://
netxorkrepository. com
Samuel V Scarpino and Giovanni Petri. On the predictability of infectious disease outbreaks. Nature communications, 10(1):1-8, 8, 2019.
Chaoming Song, Zehui Qu, Nicholas Blumm, and Albert-László Barabási. Limits of predictability in human mobility. Science, 327 (2765))):11088 1021, 2010.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chenggi Zhang, and S Yu Philip. A comprehensive survey graph neural networks. IEEE transactions on neural networks and learning systems, 32(1):4-22 24, 2020.
Yang Yang, Ryan N Lichtenwalter, and Nitesh V Chawla. Evaluating link prediction mothods. Knowledge and Information Systems, 45(3):751 782, 2015.
Haiyuan Yu, Pascal Braun, Muhammed A Yıldrım Irma Lemmens, Kavitha Venkatesan, Julie Sahalie, Tomoko Kishhana- 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.
Fuqing Zhang, Y Qiang Sun, Linus Magmusson, Roberto Buizza, -hian-Jiann Lin, Jan-Hucy Chen, and Kerry Emanuel. What is the predictability limit. of midlatilude weather? Journal of the Almospheric Sciences, 76(4):1077-1091, 2019.
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.
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--quuiaaelt non-edge types in the partition of non-e.ges).
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 soft classifier into various hard classifiers, then without loss of generality assigns a distinct score to each cell; if did not, then could just consider the cells given the same scores as being the same cell with a larger total size and larger number of positives.
let L1, 41,42,-.,4 l be the total sizes of the cells, where the cells are ordered by the score gives to them (t1 is the total size the cell with the highest score). Likewise, let Pl, P1.P2.... Ph be the number of positives in the respective cells. For notational convenience, we define to = Po
As in Section 5
Let T: Σj 1jz P. =E and N, T, Pt. Also define T Tk, P = Pk, and N No-
15

---

Published in Transactions on Machine Learning Research (06/2023)
Assume for sake of contradiction that there exists an i E [k 1] such that Pitt Now imagine #:-1 alternate classifier s* that gives the exact same scores s except that reverses the scores for the i'th and (i + 1) cells.
Then get new set of variables 11......., i and Pi,P2, ...,,,.... Pk well as corresponding Tj Pj. and Nj where the values correspond to the cells as ordered by classifier s*. Due to the definition of s* f = tj and
Pj = Pp for all j except j E fi,i+ + 1]. in which case t = f+1 4,41 = t. P: = Pi+1 and Pi+t = P.- Once again, for notational simplicity we pad the beginning of these lists with to = p = 0.
This gives total of k (true positive rate, false positive rate) pairs (i.e. (TPR, FPR) pairs). The false positive rate the x axis of the curve and the true positive rale the y axis.
Pa for j E 10.1,...,K? True Positive Rate j for (i.e. TPR;) = P
Nj N
False Positive Rate j for (i.c. FPRj) = for j E (0, (0,1.....
Likewise for s* have:
pj p
True Positive Rate j for s" (i.e. TPR))
for j E 10, (0.1....,A) }}
Nj N
False Positive Rate j for s* (i.e. FPR.)
for j E (0.1,...,k)
The ROC curve then interpolates lincarly between these points. Note that by definition TPR, TPR FPR, FPRj and TPR, TPR; FPR, FPR 1.
We can consider the interpolation between the j'th (TPR, FPR) point and the 1i+t) (TPR, FPR) point as corresponding to variable a E [0, where:
Pj op3+1
TPR
P
N, + a(t;+1 P)+1)
FPR,.0
N
This leads to the following:
Pi+1
TPR
do
p
and separately:
N. N.FRR N₂ a
t++1 PJ+1
N
dFPR,, 1i+1 Pj+1
Using the chain rule gives us:
d TPR dFPR, j,a da
da dTPRj,a N Pj+1
dFPRja
P
t Pj+1
16

---

Published in Transactions on Machine Learning Research (06/2023)
For s' curve this becomes:
N P5+1
TPR dFPR),a
P (j+1 P5+1
Now, because 1 and f only differ at j = and = 1, and the same holds for Pý, etc., and because the values at i and i + I 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) point is the same, note that P.+1 = P + + + Pi+1 Pi + + + P P++1-
P: Further, because
P. ?
we obtain that Pr 4-
p. P-
which in turn means that:
d TPR:-1,a
TPR:
dFPR,-1.a
dFPR
In other words, the slope leading from the (i- 1i-th point to the i'th point is greater in s*'s ROC curve TPR -PPR-TTRR,.. and aFPR,. TPR,,, -FPR_TPR,,.. aFPR: -----TPR,,... TTR;-1,. meaning that ss curve goes up more sharply first, and s's curve catches up with the exact same slope later. Since both curves up to and including their (i - 1)'th point are identical, and since they are also identical at the (++ 1)th point and thereafter, this means that s''s curve has a larger area underneath it.
than in s's. Furthermore, aFPR. TTR.-. aFPR: 10
Ergo, we obtain a contradiction, for obtains a higher ROC score than 8. Thus the assumption must have been false. This means that orders the cells such that Pi Parl for all j [k - 1]. In other words, completely sorts the cells as we intended to show.
By 1941
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 (Davis & Goadrich (2006)). 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: ((10, 0), (2, 2), (9, 7)). Ordering these in decrcasing Desgaaies yiclds an AP of approximately 0.856 whereas ordering them in the order listed yields an AP of approximately 0.858.
Positives
Fortunately, we can still calculate hard upper limit on AP scores by simply using the upper limit on the Positives AUPR score. Remember our ordering rule for an optimal curve: Order by PostuivesNeeattve in descending order. Remember also that via the ROC and AUPR proofs, 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 swaps where the swaps are of adjacent, incorrectly ordered cells; this corresponds to the naive "bubble sort" algorithm (Astrachan| (2003)). During this process of swaps, each new curve dominates the former. Given that the last curve the one correspouding to our ordering, it follows that our optimal curve not only has 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 a very similar manner an AUPR curve. In both cases you first get collection of precision-recall points given the ordering the classifier gives to the cells (we call these rrecision-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
17

---

Published in Transactions on Machine Learning Research (06/2023)
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 left along the interpolated AP points, the precision value remains constant until you hit new base point. By contrast, discusse above the optimal AUPR curve's precision value is either constant increasing you move from right to left. Thus any AP curve is always dominated by the ideal AUPR curve.
18


Reviews:
[{"review_id": "jdVa0PPCNS", "reviewer": "Reviewer_TEcm", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n \n-It is fascinating to discuss the marginality of the task of link prediction, focusing only on the topological information.\n\n-They experimentally show how the AUPR Score changes with the amount of information in the variety of graphs.\n\n-Furthermore, they experimentally showed that ROC and AP are calculated using Graph Convolutional Neural Network Auto-Encoder (GCNAE), and that a gap between the ROC and AP is observed.\n\n\nWeaknesses\n\n-This paper focuses on topologically-based link prediction, whereas there are many different problem settings for link prediction that are more common to use features. How to deal with feature information is sometimes the key to learning, and several non-topological features improve the accuracy of link prediction substantially as shown in existing work (e.g. Al Hasan, Mohammad, et al. \"Link prediction using supervised learning.\" SDM06: workshop on link analysis, counter-terrorism and security. Vol. 30. 2006.)\n\nOn the other hand, in this paper, the motivation should be more clear for discussing learning limitedness by restricting the discussion to topological information only.\n\n--Is this paper completely unrelated to the research stream with Graph Neural Networks? I would like to confirm that similar research questions have not been addressed in GNN literature.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers what inherently limits predictability in link prediction tasks, questioning whether graph automorphisms and related properties yield inherent limitations in predictability. For real-world graphs, they calculated upper bounds for whether graph topology alone can make link predictions. One finding was that predictions for datasets whose graphs are sparse are inherently limited and require information in addition to graph topology.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "\n1.The structure of the introductory section should be improved:\nFor example: \n\n-It is not clear until Section 3 that we see what the maximally informed link prediction task is mathematically, but it would be helpful if it is explained earlier.\n\n-The link prediction problem has a lot of existing research and history, but I feel that link prediction itself is not well explained.  It would be great if the authors give an explanation of link prediction itself and an introduction of existing studies and representative methods would be helpful. If there is anything that interferes with the flow of the discussion, create a Related Work. \n\n -A paragraph that concisely summarizes the contributions of the paper is needed. For example, how the proposed methodology gives insights about topology-based link prediction should be briefly described.\n\n-It would be easier to read if you include a reference to the structure of the paper.\n\n2. Experiments\n\nAlthough the paper found that sparseness is characteristic to differentiate on inherent limits, it would be interesting to explore other notions of graphs such as clustering coefficient or average degree might be related. I suspect these notions are not making much difference, but even so, the authors can provide such basic topological information and add them to the Table for graph data. \n", "broader_impact_concerns": "I don't see a problem on impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "hiN3xyIaFi", "reviewer": "Reviewer_sTw9", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "+ I found interesting the idea of studying the best possible result that can be achieved by methods that are invariant to permutations of the nodes. Especially on datasets that are still frequently used in the literature, e.g., Cora and CiteSeer. \n\n- I have some issues with the writing of the paper. Especially the Introduction and Section 4. The authors are trying to measure best possible performance among methods that are invariant to node permutations in the graph. So it seems that the symmetry that they are interested at is node permutations. This is a very well studied subject in GNN literature and others (see the work of Haggai Maron and citations to him). So I don't understand why the authors don't mention this clearly in the introduction and clearly re-frame their paper within this context? I would recommend to the authors to study the GNN literature more and place their work appropriately. \n\n- Section 4 is very hard to read. So I simply understood the high level idea and skipped the details. The authors need to provide further explanations about equations 1, 2 and 3, otherwise, these are very difficult to interpret. These are the most important and only mathematical results in this paper. \n\n- What's an anonymized version of a graph? It would be good to define any terminology that is used.\n- The word \"maximally\" is used but no concrete definition of what maximally means here is given. I get the idea that the authors utilize ground truth information for a specific labelling of the graph, but why is this \"maximal\"? Usually this kind of definition implies that the given information are provably better that any other given information, but is it the case here? It seems more appropriate to simply calls this \"informed link prediction\". \n- Typo \"maximially\" \n- It would have been very helpful if the \"Original graph\" in Fig 1 is plotted using the same 2D coordinates as in the other parts of the figure.\n- The definition of k-hop neighbours is very difficult to understand. It seems unnecessarily complex. \n- What's a \"canonical representation\"? \n\n- Lastly, one the most important weakness is the analysis and discussion compared to GCNAE. First, I observed that the authors make a lot of hypothesis about what could have been implemented in the GCNAE paper. However, with just a quick search I found the code for the paper https://github.com/tkipf/gae that includes the data splitting that was used and a lot of programming details. So I don't understand why the authors need to make all these assumptions.\n- Secondly, GCNAE without node features is not permutation equivariant. So I don't think it makes sense to check its performance in this setting where node permutation symmetries are important. The authors do mention this in their \"Caveats\" Section, but it is stated as hypothesis. As I mentioned earlier, there is a lot of work on this subject and I would recommend the authors to read the literature on GNNs for invariant and equivariant GNNs. \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors study upper bounds for common metrics like ROC and AUPR which are used for the task of link prediction within the class of methods that are invariant to permutations of the labels of nodes. \n", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See above.", "broader_impact_concerns": "No ethical concerns. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "VMloQQ7FDR", "reviewer": "Reviewer_s32G", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nS.1 This paper provides a new approach to analyse topology-based link prediction methods and the upper bounds will help the evaluation of link prediction methods.\n\nS.2 The experimental results show that sparse graphs contain strong caps on optimal performance, which will induce more consideration of other information beyond the topological structure for real sparse graphs during model design.\n \nS.3 The experimental analysis is detailed and clear, and the results are fully explained.\n\nWeaknesses:\n\nW.1 The current mainstream link prediction methods are not only based on graph topology, the relations and potential impact on these topology-beyond methods haven't been discussed in this paper.\n\nW.2 Only one topology-based link-prediction method is evaluated for Sec.6.2, the conclusions of Sec.6.2 are less convincing. \n\nW.3 The structure of the article is a little incoherent and not easy to understand. The motivation of proposed method is not clearly explained.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes hard upper bounds of link prediction performance based on topology, which brings new insight on analyzing the utilization of graph structure information for link prediction. The authors conduct experiments on a variety of real-world graphs to calculate how maximum link prediction scores vary with the amount of information based on proposed optimal prediction performance measurements. The experimental results demonstrate that link prediction methods on sparse graphs are inherently limited and require information besides the graph topology.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "There are several suggestions:\n1. The relations and potential impact on topology-beyond link prediction methods should be discussed in this paper.\n2. More topology-based methods need to be considered to provide more convincing conclusions.\n3. The article structure and writing need to be improved so that readers can understand the contribution of the article more easily.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: In agreement with the reviewers assessment, I believe that the paper makes some valuable contribution, yet needs some polishing and the inclusion of additional discussions before being accepted, according to the suggestions made by the reviewers, and as discussed in the authors' replies. I copy below the exchanges where additional discussion has been requested and the authors' constructive replies and suggestions as to how they intend to reply to these requests. I essentially ask the authors to implement the suggestions they laid out, with a particular emphasis on improving the paper's readability.

Reviewer 1
1.The structure of the introductory section should be improved: For example:

-It is not clear until Section 3 that we see what the maximally informed link prediction task is mathematically, but it would be helpful if it is explained earlier.

We see that the need for improved clarity is mentioned in all 3 reviews and intend to make a serious effort to improve these sections.

-The link prediction problem has a lot of existing research and history, but I feel that link prediction itself is not well explained. It would be great if the authors give an explanation of link prediction itself and an introduction of existing studies and representative methods would be helpful. If there is anything that interferes with the flow of the discussion, create a Related Work.

Precisely because there is so much research on the subject, we thought that the link prediction task is so well-known that it does not need to be re-explained or re-introduced. However, we are willing to adjust this aspect of the paper and add more exposition on the subject.

-A paragraph that concisely summarizes the contributions of the paper is needed. For example, how the proposed methodology gives insights about topology-based link prediction should be briefly described. -It would be easier to read if you include a reference to the structure of the paper.

Thanks for the feedback. We are happy to add these paragraphs.

Experiments
Although the paper found that sparseness is characteristic to differentiate on inherent limits, it would be interesting to explore other notions of graphs such as clustering coefficient or average degree might be related. I suspect these notions are not making much difference, but even so, the authors can provide such basic topological information and add them to the Table for graph data.

Thanks for this suggestion. When we revise the paper, we will add this sort of information.

Reviewer 2:
• I found interesting the idea of studying the best possible result that can be achieved by methods that are invariant to permutations of the nodes. Especially on datasets that are still frequently used in the literature, e.g., Cora and CiteSeer.

• I have some issues with the writing of the paper. Especially the Introduction and Section 4. The authors are trying to measure best possible performance among methods that are invariant to node permutations in the graph. So it seems that the symmetry that they are interested at is node permutations. This is a very well studied subject in GNN literature and others (see the work of Haggai Maron and citations to him). So I don't understand why the authors don't mention this clearly in the introduction and clearly re-frame their paper within this context? I would recommend to the authors to study the GNN literature more and place their work appropriately.

We will work to better frame our paper vis-a-vis the GNN literature. However, as we comment about above in response to Review 1:

“It [GNN research] is related, but not directly related as far as we know. For example, much of the research on the limits of GNNs [e.g. Haggai Maron] have to do with the correspondence between a GNN architecture and the power of a k-dimensional Weisfeiler Lehman (WL) algorithm. The family of WL algorithms are used to determine information about the graph’s symmetries up to isomorphism. Thus the GNN research considers how much of the available structural symmetry data a GNN architecture can take advantage of. Our research considers a different question: If all the symmetry data is available, what limits remain?”

Perhaps more importantly, we should also flag several factors that drastically mitigate the relevance of the fact that our proof is about node permutation-invariant algorithms.

A. There are only two ways that an algorithm which is not permutation-invariant can score better than an algorithm that is permutation-invariant:

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

A2. 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 input node ordering).

Concerning A1: Nobody should want algorithms to make use of the kind of data in A1 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 A2: The possibility that an algorithm could get lucky is not a meaningful counter-example to a performance limit.

Thus neither reason that an algorithm which is non-permutation-invariant could hypothetically surpass our bound is a meaningful reason. Consequently our bound is effectively an upper-bound for all link prediction algorithms – not just permutation-invariant ones.

• Section 4 is very hard to read. So I simply understood the high level idea and skipped the details. The authors need to provide further explanations about equations 1, 2 and 3, otherwise, these are very difficult to interpret. These are the most important and only mathematical results in this paper.

We see that the need for improved clarity is mentioned in all 3 reviews and intend to make a serious effort to improve these sections.
• What's an anonymized version of a graph? It would be good to define any terminology that is used.

Good point. We will make this clearer in the paper. Given a graph G, we think of an “anonymized” version as being a graph H that is isomorphic to G where no exact isomorphism between G and H is given. Thus the structure of the graph is preserved but the identity of a given node is not known (“anonymous”) except insofar as it is entailed by the structure.

• The word "maximally" is used but no concrete definition of what maximally means here is given. I get the idea that the authors utilize ground truth information for a specific labeling of the graph, but why is this "maximal"? Usually this kind of definition implies that the given information are provably better that any other given information, but is it the case here? It seems more appropriate to simply calls this "informed link prediction".

Good question. We called it “maximally informed” link prediction because the algorithm is given all possible structural information entailed by the problem alone (i.e. the solution graph itself showing which edges were removed). Any other source of information is either not strictly structural (e.g. text data related to nodes) or not entailed by the task alone (e.g. a node ordering based on an algorithm).

Thus, in terms of structural information, this is provably better simply because it is all the possible information. However, we think you are right that perhaps “maximally informed” is misleading because there are other kinds of non-structural data a link predictor could be given.

We could instead pick a name like “maximally informed structure-only link prediction,” but that’s a mouthful. We will brainstorm to try to come up with a better name.

• Typo "maximially"

• It would have been very helpful if the "Original graph" in Fig 1 is plotted using the same 2D coordinates as in the other parts of the figure.

We will make this change.

• The definition of k-hop neighbours is very difficult to understand. It seems unnecessarily complex.

Acknowledged. We will work to simplify this via some combination of:

1. Reducing the amount of formalism

2. Talking about walks of length k instead of recursive neighbor sets and defining induced subgraphs in their own preliminary section so that the notation is simpler

3. Something you suggest

• What's a "canonical representation"?

Good question. We will add an explanation to the paper. A “canonical representation” of a graph (or of a subgraph) is a representation of the graph that is produced in a way that is invariant to the original node ordering of the graph. This concept is used by practical graph isomorphism algorithms (e.g. Nauty and Traces); they work by first converting two graphs G1 and G2 to canonical forms C1 and C2 respectively, then perform the trivial check to see if C1 and C2 are identical.

• Lastly, one the most important weakness is the analysis and discussion compared to GCNAE. First, I observed that the authors make a lot of hypothesis about what could have been implemented in the GCNAE paper. However, with just a quick search I found the code for the paper https://github.com/tkipf/gae (https://github.com/tkipf/gae) that includes the data splitting that was used and a lot of programming details. So I don't understand why the authors need to make all these assumptions.

True. We were probably too lazy in this regard. We are now willing to extract the answers from their code.

• Secondly, GCNAE without node features is not permutation equivariant. So I don't think it makes sense to check its performance in this setting where node permutation symmetries are important. The authors do mention this in their "Caveats" Section, but it is stated as hypothesis. As I mentioned earlier, there is a lot of work on this subject and I would recommend the authors to read the literature on GNNs for invariant and equivariant GNNs.

There is a fairly straightforward way for us to address this concern. We can make a modified version of GCNAE that first randomly permutes the input node ordering and call it GCNAE'.

We strongly suspect that GCNAE' will report similar scores to the scores reported in the original paper. If it reports similar scores, this would show that the amount reported over our performance limit is not due to input ordering but rather due to down-sampling negative edges. If GCNAE' does not report similar scores, the new numbers will still be interesting and should be considered the most relevant scores due to the reasons we discuss above concerning A1.

Furthermore, actually running GCNAE and GCNAE' will enable us to see what its AP score actually is when calculated correctly.
Reviewer 3:
W.1 The current mainstream link prediction methods are not only based on graph topology, the relations and potential impact on these topology-beyond methods haven't been discussed in this paper.

For what it’s worth, we do not think of this as a weakness of the paper for the following reason: Our whole goal was to explore the limits of what can be inferred from the structure. Thus while we know that almost all modern link prediction methods make use non-structural data, that is almost beside the point of this study.

W.2 Only one topology-based link-prediction method is evaluated for Sec.6.2, the conclusions of Sec.6.2 are less convincing.

[We discuss how we can make section 6.2 more convincing in our response to Review 2’s last 2 points.]

We admit that it would be ideal to compare to more link prediction models. However, we also would like to point out that link prediction performance tends to be similar across GNN’s (within a few percent – whereas the amount by which GCNAE’s reported score was above the limit was 15%), and our goal in the paper was not to analyze GCNAE per-say but rather to show that:

“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 believe that both of these claims will be well-established through our updated analysis of GCNAE (see Reply to Review 2 -- Part 2).

However, we agree that we should at minimum add a note to the paper establishing the similarity between GCNAE and other models’ performance.

W.3 The structure of the article is a little incoherent and not easy to understand. The motivation of proposed method is not clearly explained.

We see that the need for improved clarity is mentioned in all 3 reviews and intend to make a serious effort to improve these sections.

Requested Changes
There are several suggestions

The relations and potential impact on topology-beyond link prediction methods should be discussed in this paper.

More topology-based methods need to be considered to provide more convincing conclusions.

The article structure and writing need to be improved so that readers can understand the contribution of the article more easily.

[See the above for our thoughts and intentions to address these concerns.]

Decision: Accept (poster)