Link Prediction without Graph Neural Networks
Authors: Zexi Huang
Mert Kosan
Arlei Lopes da Silva
Ambuj Singh
Venue: Submitted to ICLR 2023 (2023)
Keywords: Link Prediction
Graph Neural Networks
Graph Learning
Topological Heuristics

Abstract: Link prediction, which consists of predicting edges based on graph features, is a fundamental task in many graph applications. As for several related problems, Graph Neural Networks (GNNs), which are based on an attribute-centric message-passing paradigm, have become the predominant framework for link prediction. GNNs have consistently outperformed traditional topology-based heuristics, but what contributes to their performance? Are there simpler approaches that achieve comparable or better results? To answer these questions, we first identify important limitations in how GNN-based link prediction methods handle the intrinsic class imbalance of the problem---due to the graph sparsity---in their training and evaluation. Moreover, we propose Gelato, a novel topology-centric framework that applies a topological heuristic to a graph enhanced by attribute information via graph learning. Our model is trained end-to-end with an N-pair loss on an unbiased training set to address class imbalance. Experiments show that Gelato is 145% more accurate, trains 11 times faster, infers 6,000 times faster, and has less than half of the trainable parameters compared to state-of-the-art GNNs for link prediction.

Under review as a conference paper at ICLR 2023
LINK PREDICTION WITHOUT GRAPH NEURAL NET- WORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Link prediction, which consists of predicting edges based on graph features, is fundamental task in many graph applications. As for several related problems, Graph Neural Networks (GNNs), which are based on an attribute-centric message- passing paradigm, have become the predominant framework for link prediction. GNNs have consistently outperformed traditional topology-basee hcuristics, but what contributes to their performance? Are there simpler approaches that achieve comparable better results? To answer these questions, we first identify impor- tant limitations in how GNN-based link prediction methods handle the intrinsic class imbalance of the problem due the graph sparsity-in in their training and evaluation. Moreover, we propose Gelato, a novel topology-centrie framework that applies a topological heuristic to a graph enhanced by attribute information via graph learning. Our model is trained end-to-end with an N-pair loss on an unbiased training set to address class imbalance. Experiments show that Gelato is 145% more accurate, trains 11 times faster, infers 6,000 times faster, and has less than half of the trainable parameters compared to state-of of ttthhe-rr art GNNs for link prediction.
INTRODUCTION
Machine learning on graphs supports various structured-data applications including social network
analysis (Tang et al. 2008 Li et al. 2017 Qiu et al.] 2018b), recommender systems (Jamali &
Ester] 22099; Monti et | Wang et al. 2019a), natural language processing (Sun et al. [2018a]
Sahu et al. 2019, Yao et al. 2019). and physics modeling (Sanalez-Gonzzlez et | 2018) Ivanovic Pavone 2019 da Silva et al. (020). Among the graph-related tasks, one could argue that link
prediction [Li & Zhou 2011: Martínez et al. 2016) is the most fundamental one. This is because
link prediction not only has many concrete applications (Qi et al. 2006 Liben-Nowell & Kleinberg
2007: Koren et al. 2009) but can also be considered (implicit or expliiit) step of the graph-based
machine learning pipeline (Martin et al. 2016 Bahulkar et al. 2018 Wilder et al. 2019 as the observed graph is usually noisy and/or incomplete.
In recent years, Graph Neural Networks (GNNs) (Kipf & Welling 2017: Hamilton et al. 2017 Veličković et al. 2018) have emerged as the predominant paradigm for machine learning on graphs.
Similar to their great success in node classification (Klicpera et al. 2018 [Wu et al. 2019 Zheng et al.
2020) and graph classification (Ying et al. [2018] Zhang
201 Sa Morris al. 2019). GNNs have
been shown to achieve state-of-the-art link prediction performance (Zhag & Chen 2018 Yun et al.)
2021 Pan al. 2022). Compared to classical approaches that rely on expert-designed heuristics to
extract topological information (e.g., Common Neighbors (Newman 2001), Adamic-Ada (Adamic Adar 2003). Preferential Attachment (Barabási et al.) (2002), GNNs have the potential discover new heuristics via supervised learning and the natural advantage of incorporating node attributes.
However, there is little understanding of what factors contribute to the success of GNNs in link prediction, and whether simpler alternatives can achieve comparable performance- as recently found for node classification (Huang et al.) 2020). GNN-based methods approach link prediction as a binary classification problem. Yet different from other classification problems, link prediction deals with extremely class- imbaslaned data due to the sparsity of real-world graphs. We argue that class imbalance should be accounted for in both training and evaluation of link prediction. In addition, GNNs combine topological and attribute information by learning appology-smoohhnne attributes (embeddings) via message-passing (Li al. 2018.. This attribute-centric mechanism has been proven

---

Under review as a conference paper at ICLR 2023
O K
O
ZZZ
ZZZ
(a) Link prediction for attributed graphs
(b) GNN: topology + attributes
(c) Gelato: attributes + topology
Figure I: GNN incorporates topology into attributes via message-passing, which is effective for tasks on the topology. Link prediction, however, is a task for the topology, which motivates the design of Gelato-a novel framework that leverages graph learning to incopporate attributes into topology.
effective for tasks on the topology such as node classification (Ma et al. 2020), but link prediction is a task for the topology, which naturally motivates topology-centric paradigms (see Figure T).
The goal of this paper is to address the key issues raised above. We first show that the evaluation of GNN-based link prediction pictures an overly optimistic view of model performance compared to the (more realistic) imbalanced setting. Class imbalance also prevents the generalization of these models due to bias in their training. Instead, we propose the use of the N-pair loss with an unbiased set of training edges to account for class imbalance. Moreover, we present Gelato, novel framework that combines topological and attribute information for link prediction. As a simpler graph learning to incorporate node attributes
alternative to GNNs, model applies topology-centoe directly into the graph structure, which is given as input to a topological heuristic, Autocovariance, for link prediction. Extensive experiments demonstrate that our model significantly outperforms state-of-ther thtt-ot-the-at GNN-based methods in both accuracy and scalability.
To summarize, our contributions are: (1) scrutinize the training and evaluation of supervised link prediction methods and identify their limitations in handling class imbalance; (2) we propose a simple, effective, and efficient framework combine topological and attribute information for link prediction without using GNNs; and (3) we introduce an N-pair link prediction loss combined with an unbiased set of training edges that we show to be more effective at addressing class imbalance.
LIMITATIONS IN SUPERVISED LINK PREDICTION EVALUATION & TRAINING
Supervised link prediction is often formulated as binary classification problem, where the positive (or negative) class includes node pairs connected (or not connected) by a link. key difference between link prediction and typical classification problems (e.g., node classification) is that the two classes in link prediction are extremely imbalanced, since most real-worle graphs of interest are sparse (see Table Tp. However, we find that class imbalance is not properly addressed in both evaluation and training of existing supervised link prediction approaches, as discussed below.
Link prediction evaluation. Area Under the Receiver Operating Characteristic Curve (AUC) and Average Precision (AP) are the two most popular evaluation metrics for supervised link predic-
tion (Kipf & Welling 2016 Zhang & Chen, 2018 Chami et al.] 2019; Zhang et al.) 202T Cai
et al. | et al., 2021 Zhu Zhu et al. 2021 Chen et al. 2022 Pan et al. 2022). We first ar- gue that, as in other imbalanced classification problems (Saito & Rehmsmeier 2015). AUC is
not an effective evaluation metric for link prediction as it is biased towards the majority class (non-edges). On the other hand, AP and other rank-based metrics such as Hits lits@k-uuse in Open Graph Benchmark (OGB) (Hu et al., 2200)) are effective for imbalanced classification evaluated on a test set that follows the original class distribution. Yet. existing link prediction methods (Kipf & Welling, 2016; Zhang & Chen 20118] Cai et al., 202T;: Zhu et al.] [202]] Pan al. 2022) compute AP on test set that contains all positive test pairs and only an equal number of random negative pairs. Similarly, OGB computes Hits @ k against very small subset of random negative pairs. We term these approaches biased testing as they highly overestimate the ratio of positive pairs in the graph. Evaluation metrics based on these biased test sets provide overly optimistic measurement of the actual performance unbiased testing, where every negative pair is included in the test set. In fact, in real applications where test positive edges are not known priori, it is impossible to construct those biased test sets to begin with. Below, we also present an illustrative example of the misleading performance evaluation based on biased testing.
2

---

Under review as a conference paper at ICLR 2023
Example: Consider a graph with 10k nodes, 100k edges, and 99.9M disconnected (or negative) pairs. A (bad) model that ranks 1M false positives higher than the true edges achieves 0.99 AUC and 0.95 in AP under biased testing with equal negative samples. (Detailed computation in Appendix A
The above discussion motivates more representative evaluation setting for supervised link prediction. Specifically, we argue for the use of rank-based evaluation metrics-AIl Precision @ k (Lü & Zhou 2011), and Hits@ k (Bordes et al., (013) with wnbiased testing. where positive edges are ranked against all negative pairs. These metrics have been widely applied in related problems, such as unsupervised link prediction (Lü & Zhou 2011 Ou et al. 2016; ZZhang et al., 2018b Huang et al. 2021), knowledge graph completion (Bordes et al. [013] Yang et al. [0115] Sun et al. 2018b). and information retrieval (Schütze et al. 2008), where class imbalance is also significant. In our experiments, we will illustrate how these evaluation metrics combined with unbiased testing provide drastically different and more informative performance evaluation compared to existing approaches.
Link prediction training. Following the formulation of supervised link prediction as binary classifi- cation, most existing models adopt the binary cross entropy loss to optimize their parameters (Kipf &
Welling 2016, 2016:ZZhag & Chen 2018 2018|Chami |Chami et al. 2019; Zhang et al. 2021 Yan et al. 2021 Yun et al. 2021 Zhu et 2021 Chen et al.] 2022). To deal with class imbalance, these approaches downsample the negative pairs to match the number of positive pairs in the training set (biased training). We highlight two drawbacks of biased training: (1) it induces the model to overestimate the probability of positive pairs, and (2) it discards potentially useful evidence from most negative pairs. Notice that the first drawback is often hidden by biased testing. Instead, this paper proposes the use of unbiased training, where the ratio of negative pairs in the training set is the same as in the input graph. To train our model in this highly imbalanced setting, we apply the N-pair loss for link prediction instead of the cross entropy loss (Section 3.3
3 METHOD
Notation and problem. Consider an attributed graph G EV, where V is the set of n nodes, E is the set of m edges (links), and X = (z), ..., TT.) E Rn collects r-dimensional node attributes. The topological (structural) information of the graph is represented by its adjacency matrix A E RRax, with Aue > 0 if an edge of weight Aue connects nodes u and v and Aur = 0, otherwise. The (weighted) degree of node u is given as da = E..Au, Aue and the corresponding degree vector (matrix) denoted as d R. (D E I=).).. The volume of the graph is vol(G') Σn, du Our goal is to infer missing links in G' based on its topological and attribute information, A and X.
Model overview. Figure 2 provides an overview of our link prediction model. It starts with a topology-centric graph learning phase that incorporates node attribute information directly into the graph structure via a Multi-layer Perceptron (MLP). We then apply a topological heuristic, Autocovariance (AC), to the attribute-enhanced graph to obtain pairwise score matrix. Node pairs with the highest scores are predicted as (positive) links. The scores for training pairs are collected to compute N-pair loss. Finally, the loss is used to train the MLP parameters in an end-to-end manner. We named our model Gelato (Graph gnhancement for link prediction with autocovariance). Gelato represents a paradigm shift in supervised link prediction by combining graph encoding of attributes with a topological heuristic instead of relying on increasingly popular GNN-basee embeddings.
3.1 GRAPH LEARNING
The goal of graph learning is generate an enhanced graph that incorporates node attribute infor- mation into the topology. This can be considered as the "dual" operation of message-passin passing in GNNs, which incorporates topological information into attributes (embeddings). We argue that graph learning is the more suitable scheme to combine attributes and topology for link prediction, since link prediction is task for the topology itself (as opposed to other applications such as node classification).
Specifically, our first step of graph learning is to augment the original edges with set of node pairs based on their (untrained) attribute similarity (i.e., adding an r-neighborhood graph):
E + {u, v) s(Za, xx) > }
(1)
where s(-) can be any similarity function (we use cosine in our experiments) and 6, is a threshold that determines the number of added pairs ratio 17 of the original number of edges m.
3

---

Under review as a conference paper at ICLR 2023
Input graph
Enhanced graph
Predicted links
Eg
L(0)
Graph learning
Topological heuristic
N-pair loss
B(ab)
Sec.
(L)(@)
Autocovariance
Link ranking
Figure 2: Gelato applies graph learning to incorporate attribute information into the topology via an MLP. The learned graph is given to a topological heuristic that predicts edges between node pairs with high Autocovariance similarity. The parameters of the MLP are optimized end-to-ent using the N-pair loss. Experiments show that Gelato outperforms state-of-the-art GNN-based link prediction methods.
A simple MLP then maps the pairwise node attributes into a trained edge weight for every edge in E: Wae = MLP(( mul: []: 9)
(2)
where [ æy] denotes the concatenation w. and H, and 0 contains the trainable parameters. For undirected graphs, we instead use the following permutation invariant operator (Chen et al. 2014
Wuv MLP((z + xpi IT, =x,l]:0)
The final edge weights of the enhanced graph are weighted combination of the topological weights, the untrained weights, and the trained weights:
Auo a + (1 (Bw
(3)((zu;
(4)
where a and 3 are hyperparameters. The enhanced adjacency matrix À is then fed into topological heuristic for link prediction introduced in the next section. Note that the MLP is not trained directly to predict the links, but instead trained end-to-end to enhance the input graph given to the topological heuristic. Also note that the MLP can be easily replaced by more powerful model such GNN, but the goal of this paper is to demonstrate the general effectiveness of our framework and we will show that even a simple MLP leads to significant improvement over the base heuristic.
3.2 TOPOLOGICAL HEURISTIC
Assuming that the learned adjacency matrix Á incorporates both structural and attribute information, Gelato applies topological heuristic to Á. Specifically, adopt Autocovariance, which has been shown to achieve state-of-the-an link prediction results for non-attributed graphs (Huang et al. 2021).
Autocovariance is random- walk based similarity metric. Intuitively, it measures the difference between the co-visiting probabilities for a pair of nodes truncated walk and an infinitely long walk. Given the enhanced graph G, the Autocovariance similarity matrix E Raxn is given as
R D (ī-
dd
(5)
Gol(G)
VG)
where E No is the scaling parameter of the truncated walk. Each entry Ruv represents similarity score for node pair (u, v) and top similarity pairs are predicted as links. Note that Ruv only depends on the (-hop enclosing subgraph of (u, v) and can be easily differentiated with respect to the edge fact, Gelato could be applied with any differentiable topological heuristic even combination of them. In experiments (Section 4.2) will show that Autocovariance alone enables state-of tftt--of-the-art the- link prediction performance.
weights in the subgraph.
Next, we introduce how train our model parameters with supervised information.
3.3 N-PAIR LOSS AND UNBIASED TRAINING
As we have mentioned in Section 2 current supervised link prediction methods rely on biased training and the cross entropy loss (CE) to optimize model parameters. Instead, Gelato applies the N-pair
4

---

Under review as a conference paper at ICLR 2023
loss (Sohn 2016) that is inspired by the metric learning and Cearning-to-rame literature (McFee & Lanckriet 2010; Cakir et al. 2019 Revaud et al. 2019 Wang et al. (019b) to train the parameters of our graph learning model (see Section (.11) from highly imbalanced unbiased training data.
The N-pair loss (NP) contrasts each positive training edge (u, v) against a set of negative pairs (u, v). It is computed as follows:
exp(Rwe)
L( =
Σ
log exp(Run) + + ((n Exp(Rm)
(6)
(a,e)EE
Intuitively, [()) is minimized when each positive edge (u, v) has a much higher similarity than its contrasted negative pairs: Rae > Rpg. V(p.g) q) E -N NN, v). Compared to CE, NP is more sensitive to negative pairs that have comparable similarities to those of positive pairs-they are more likely to be false positives. While NP achieves good performance in our experiments, alternative losses from the learning-to- to-ning literature (Freund et al. 2003] Xia et al. 2008 Bruch (021)) could also be applied.
Gelato generates negative samples N Nu, v) using unbiased training. This means that N N(u, v) is a random subset of all disconnected pairs in the training graph, and (u, e)] is proportional to the ratio of negative pairs over positive ones. In this way, we leverage more information contained in negative pairs compared to biased training. Note that, similar to unbiased training, (unsupervised) topological heuristics implicitly use information from all edges and non-edges. Also, unbiased training can be combined with adversarial negative sampling methods (Cai & Wang, 2018:) Wann et al. 2018) from the knowledge graph embedding literature to increase the quality of contrasted negative pairs.
Complexity analysis. The only trainable component in model is the graph learning MLP with O(rh + uh²) parameters-wiiee and h is the number of neurons per layer. Notice that the number of parameters is independent of the graph size. Constructing the c-neighborhood graph based on cosine similarity can be done efficiently using hashing and pruning (Satuluri & Parthasarathy 2012 Anastasiu & Karypis 2014) 4). Computing the enhanced adjacency matrix with the MLP takes (1++))mr) time per epoch-where
r is the number of node features, is the number of hidden layers,
m [E| and the ratio of edges added to E from the e-neighborhood graph. We apply sparse matrix multiplication to compute entries of the t-step AC in O + 7)mm) time. Note that unlike recent RNN-based approaches (Zhang & Chen 2018 Liu et al. 2020 Pan al. 2022) that generate
distinctive subgraphs for each link (e.g., via the labeling trick), enclosing subgraphs for links in Gelato share the same information (i.e., learned edge weights), which significantly reduces the computational
cost. Our experiments will demonstrate Gelato's 's efficiency in training and inference.
4 EXPERIMENTS
We provide empirical evidence for our claims regarding supervised link prediction and demonstrate the accuracy and efficiency of Gelato. Our implementation is anonymously available at https //anonymous. 4open. science/://eeatttt
4.1 EXPERIMENT SETTINGS
Datasets. Our method is evaluated on five attributed graphs commonly used as link prediction benchmark (Chami et al. 2019 Zhang al. 2021 Yan et al. 2021 Zhu al. [2021] Chen et al. 2022 Pan et al. 2022
Table shows dataset statistics-sed Appendix B for dataset details.
Table summary of dataset statistics.
#Nodes
#Edges
#Attributes
Avg. degree
Density
CORA
2,708
5,278
1,433
3.90
0.14%
Yang et al.
2016
CITESEER
3.327
4,552
3,703
2.74
0.08%
PUBMED
19.717
44.324
500
4.50
0.02%
PHOTO
7,650
119,081
745
31.13
0.41%
Shchur et al. 2018
COMPUTERS
13.752
245,861
767
35.76
0.26%
Baselines. For GNN-based link prediction. we include six state-of-ther thr---rr methods published in the
past two years: LGGNN (Zhang et al.] 2021), TLCC-NN (Yan et al., 2021), Neo-GNN (Yun al.
5

---

Under review as a conference paper at ICLR 2023
2021), NBFNet (Zhu al. 2021), BScNets (Chen al. 2022), and WalkPool Pan al.
2022).
as well as three pioneering works
GAE Kippf & Welling 2016), SEAL (Zhagg Chen 2018).
consider Common Neighbors (CN) Newman 200T). Adamic Adar (AA) ) (Adamic & Adar 2003). Resource Allocation
and HGCN (Chami et al. 2019). For topological link prediction heuristics,
(RA) (Zhou et al. 2009), and Autocovariance (AC) (Huang al. 2021 the base heuristic in
model. To demonstrate the superiority of the proposed end-to-end model, we also include an MLP trained directly for link prediction, the cosine similarity (Cos) between node attributes, and AC on top of the respective weighted/augmented graphs (i.e., two-stage approaches) as baselines.
Hyperparameters. For Gelato, we tune the proportion of added edges 1) from (0.0, 0.25, 0.5, 0.75, 1.0), the topologiaa weight a from {0.0, 0.25, 0.5, 0.75}, and the trained weight 3 from {0.25, 0.5, 0.75, 1.0), with a sensitivity analysis included in Appendix C All other settings are fixed across datasets: MLP with one hidden layer of 128 neurons, AC scaling parameter = 3, Adam optimizer (Kingma & Ba, 2013) with a learning rate of 0.001, a dropout rate of 0.5, and unbiased training without downsampling. For basclines, we use the same hyperparameters in their papers.
Chammi Link prediction setting. Following Kipt Welling (2016); Zhang & Chen (018): Chami al. (2019); Zhang et al.) (202T); [Chen et al. (2022); Pan et al. (2022), we randomly split edges into 85%/5% for training. validation, and testing. As argued in Section [ to better reflect the performance in real-world applications, proportion of positive edges among the top of all testing pairs, Hits@k (hits@kk)ratioo of positive edges individually ranked above kth place against all negative pairs, and Average Precision (AP) area under the pecision-recall curve, as evaluation metrics. We report results from 10 runs with random seeds ranging from to 10. More detailed experiment settings can be found in Appendix D
adopt unbiased testing and use Precision@ @ (prec -)
4.2 LINK PREDICTION PERFORMANCE
Table summarizes the link prediction performance in terms of the mean and standard deviation of AP of all methods. Figure and Figure show results based on prec& and hits@k for varying values.
Table 2:
Link prediction performance comparison (mean std AP). Gelato consistently outperforms GNN-based methods, topologiaal heuristics, and two-stage approaches combining attributeshtopologyy
CORA
CITESEER
PUBMED
РHоТО
COMPUTERS
GAE
0.27 = 0.02
0.66 0.11
0226:0.00
0.28 0.02
0.30 + 0.02
SEAL
0.74
0.91 0.66
8**
0.86
6.84
HGCN
0.03
0.14
0.05
2.11
= 0.14
LGCN
1.14
0.09
0.44
0.05
1.96 0.03
GNN
TLC-GNN
0.29
0.35
OOM
1.17
OOM
Neo-GNN
2.65
1.36
1.21 0.14
10.83
6.75"
NBFNet
0.36
0.22
8**
11.99 + 1.60
#**
BSeNets
0.32
0.06
+
2.47 0.118
1.45 = 0.10
WalkPool
2.04
0.11
1.31"
0OM
00M
CN
0.74 0.00
0.00
7.00
0.00
Topological
AA
0.00
1.24
0.00
9.67
6.00
RA
0.00
1.19
0.00
7.71 1.07
Hcuristics
AC
2.00
2.00
2.50
16.63 0.00
11.64
MLP
0.05
0.09
0.04
1.01
0.41 = 0.23
Cos
0.42
1.89
0.07 0.00
0.11
0.07 # 0.00
Attributes
MLP+AC
3.24 0.03
1.05
2.06
0.22
11.25 # 0.13
Topology
Cos+AC
3.60
4.00
0.01
5.20 10.01
MLP+Cos+AC
3.39 =
0.15
0.55 2
10.88
Gelato
3.90 0.03
4.55 + 0.02
2.88 0.09
25.68 + 0.53
18.77 + 0.19
Run only once as each run takes ~10 hrs; #** Each run takes 1000 hrs:
OOM: Out Of Memory.
First, we want to highlight the drastically different performance of GNN-based methods compared to those found in the original papers (Zhang al. 2021 Yan et al. 2021: Yun al. 2021: Zhu et al. |021] Chen et al. [202 Pan et al. 2022) and reproduced in Appendix While they achieve AUC/AP scores of often higher than 90% under biased lesting, here most of them underperform even

---

Under review as a conference paper at ICLR 2023
the simplest topological heuristics such Common Neighbors under unbiased testing. These results support our arguments from Section 2 that evaluation metrics based on biased testing can produce mis- leading results compared to unbiased testing. The overall best performing GNN model is Neo-GNn which directly generalizes the pairwise topological heuristics. Yet still, it consistently underperforms AC, a mandom-walk based heuristic that needs neither node attributes nor supervision/trainnn..
We then look at two-stage combinations of AC and models for attribute information. We observe noticeable performance gains from combining attribute cosine similarity and AC in CORA and CITE- SEER but not for other datasets. Other two-stage approaches achieve similar or worse performance.
Finally, Gelato significantly outperforms the best GNN-based model with average relative gain of 145.2% % and AC with gain of 52.6% in terms of similar results were obtained for prec k and hits@k. This validates our hypothesis that a simple MLP can effectively incorporate node attribute information into the topology when our model is trained end-to-end. Next, we will provide insights behind these improvements and demonstrate the efficiency of Gelato on training and inference.
Cora
CiteSeer
PubMed
Photo
Computers
20
Precigk (%)
30
10
32
20-
16
100
100
(96
Figure 3: Link prediction performance in terms of precãk for varying values of l (as percentages of test edges). With few exceptions, Gelato outperforms the baselines across different values of
Cora
CiteSeer
PubModd
Photo
Computers
56
18
12
Hisikk
28
10
1.4
8
(K0000)
Figure 4: Link prediction performance in terms of hits@k for varying values of k. With few exceptions, Gelato outperforms the baselines across different values of kt
4.3 VISUALIZING GELATO LINK PREDICTION PROCESS
To better understand the performance Gelato, we visualize the input adjacency matrix and node attributes (in terms of pairwise Euclidean distance), the final prediction scores Figure The results are based on subgraph of PHOTO containing the top 1 160 nodes belonging to the first class sorted in decreasing order of their (within-class) degree.
adjacency matrix, and the
(a) Input adj. matrix
(b) Attribute distance
(c) Enhanced adj. matrix
(d) Gelato prediction
220
220
160
100
1.0
760
Edge
Nonedge
10
15
70
0.0
81
07
03
04
10
70
30
Figure 5: Illutraaionn of the link prediction process of Gelato. Graph learning effectively incorporates node attributes into topology and AC on the enhanced graph enables ofate-of-the-art link prediction.
7

---

Under review as a conference paper at ICLR 2023
We observe that the graph learning module of Gelato generates more informative adjacency matrix (Figure 5c) by incorporating node attributes (Figure 5b) into the input adjacency matrix (Figure Sa). This can be seen from the weii-weig of the edges connecting the high-degree nodes with larger attribute distances (matrix entries 0)-0 and especially 0-10) and the up-weighting of those connecting medium-degres nodes with smaller distances (40-80). Applying the topological heuristic, Autocovari- ance, to this enhanced adjacency matrix thus leverages the advantages from both worlds (Figure 5d). not only covers most true edges between high-degree nodes AC captures node degree distribu- tions (Huang et al. (021) but also avoids false predictions for connections between high-degree and low-degree nodes thanks to the attribute- bassutee-baeddeee edge down-went weinhweigg enabling state-of of-the-art link pre- diction performance for attributed graphs. A detailed analysis of the improvements of Gelato over the vanilla AC and comparisons with the GNN-based link prediction process is included in Appendix
4.4 LOSS AND TRAINING SETTING
In this section, we demonstrate the advantages of the proposed N-pair loss and unbiased training for supervised link prediction. Figure shows the training and validation losses and preci 100% (our validation metric) in training Gelato based on the cross entropy (CE) and N N-pair (NP) losses under biased and unbiased training respectively. The final test AP scores are shown in the titles.
CE blased: 14.87% :lase%:14.87%-
1.41%
NP blased: 19.63% 0.38%
CE unblased 23.66% 1.01% NP unblased: : 20.5%%
%
Train
74
0.42
50 0.05
26.5 0.3-
20 2.0
0.30
14.0
17.0 1.0
19 10.0
100% (9)
Valld
0.00
9.5
14.5 0.5
12 7.3
0.0
50
200
50
100
1.50
200
250
50
150
200
250
50 150
Epochs
Loss
Precgic
Figure 6: Training of Gelato based on different losses and training settings for PHOTO with test AP (mean + std) shown in the titles. Compared with the cross entropy loss, the N-pair loss with unbiased training is a more consistent proxy for unbiased testing metrics and leads to better peak performance.
In the first column (CE with biased training), different from the training, both loss and precision for (unbiased) validation decrease. This leads even worse test performance compared the untrained base model (i.e.. AC). In other words, albeit being the most popular loss function for supervised link prediction, CE with biased training does not generalize unbiased testing. On the contrary, as shown in the second column, the proposed NP loss with biased training equivalent to the pairwise logistic loss (Burges al. 2005) is a more effective proxy for unbiased testing metries.
The right two columns show results with unbiased training, which is better for CE as more negative pairs are present the training set (with the original class ratio). On the other hand, NP is more con- sistent with unbiased evaluation metrics, leading to 8.5% better performance. This is because, unlike CE, which optimizes positive and negative pairs independently. NP contrasts negative pairs against positive ones, giving higher importance negative pairs that are more likely to be false positives.
An ablation study of Gelato is included Appendix G While all supervised baselines originally adopt biased training. also implement the same unbiased training (and N N-pair loss) Gelato for those that are scalable in Appendix results are consistent with the ones discussed in Section 4.2
4.5 RUNNING TIME
We compare Gelato with other supervised link prediction methods in terms of running time for PHOTO in Table 3 As the only method that applies unbiased training with more negative samples-Gell
8

---

Under review as a conference paper at ICLR 2023
shows a competitive training speed that is 11x faster than the best performing GNN-based method, Neo-GNN. In terms of inference time, Gelato is much faster than most baselines with a 6,000x speedup compared to Neo-GNN. We further observe more significant efficiency gains for Gelato over Neo-GNN for larger datasets-ed 14x (training) and 25,000 (testing) for COMPUTERS.
Table 3: Training and inference time comparison between supervised link prediction methods for PHOTO. Gelato has competitive training time (even under unbiased training) and is significantly faster than most baselines in terms of inference, especially compared to the best GNN model, Neo-GNN.
GAE
SEAL
HGCN
LGCN
TLC-GNN
Neu-GNN
NBINet
BScNets
MLP
Gelato
Training Testing
1,022
11,493
92
56
42,440
14,807
30,896
115
232
1,265
0.031
380
0.093
0.099
5.722
346
76,737
0.394
1.801
0.057
5 RELATED WORK
Topological heuristies for link prediction. The early link prediction literature focuses on topology- based heuristics. This includes approaches based on local (e.g., Common Neighbors (Newman 2001), Adamic Adar (Adamic & Adar (003). and Resource Allocation (Zhou et al., 2009)) and higher-order (e.g.. Katz (Katz) 1953), PageRank (Page et al., 1999). and SimRank (Jeh & Widom 2002)) information. More recently, random-wall wwak based graph embedding methods, which learn vector representations for graph data (Perozzi et al. 2014) Grover& & Leskovec (016)] Huang et al. (021). ) have achieved promising results in graph machine learning tasks. Popular embedding approaches. such as Deep Welk (Perozzi et al., 2014) and node2vec (Grover & Leskoved (2166), have been shown to implicitly approximate the Pointwise Mutual Information similarity (Qiu al. 2018a), which can also be used as link prediction heuristic. This has motivated the investigation of alternative similarity metrics such as Autocovariance (Delvenne et al. 2010: Huang et al.) 2021 2022). However, these heuristics are unsupervised and cannot take advantage of data beyond the topology.
Graph Neural Networks for link prediction. GNN-based link prediction addresses the limitations of topological heuristics by training a neural network to capture both topological and attribute information and potentially learn new heuristics via supervised learning. GAE (Kipf & Welling 2016) combines graph convolution network (Kipf & Welling 2017) and an inner product decoder based on node embeddings for link prediction. SEAL (Zhang & Chen 2018) models link prediction as
binary subgraph classification problem codge/non-edger and follow-up up work (e.g.. SHHF (Liu et al.,
2020), WalkPool (Pan et al., (022)) investigates different pooling strategies. Other recent approaches for GNN-based link prediction include learning representations in hyperbolic space (e.g.. HGCN (Chami et al. 2019)). LGCN (Zhang et al. 202I)), generalizing topological heuristics (c.g., Neo-GNN YYun al. 2021), NBFNet (Zhu al. 202 )) and incorporating additional topological features (c.g.. TL.C-GNN (Yan et al. 2021). BScNets (Chen et al. 22022)) Motivated by the growing popularity of GNNs for link prediction, this work investigates key questions regarding their training, evaluation, and ability to learn effective topological heuristics directly from data. We propose Gelato, which is simpler, more accurate, and faster than the state-of-the-art GNN-based link prediction methods.
Graph learning. Gelato learns graph that combines topological and attribute information. Graph learning also enables the application of GNNs when the graph is unavailable, noisy, or incomplete. LDS (Franceschi et al. 2019) jointly learns probability distribution over edges and GNN parameters. IDGL (Chen et al.) 2020) and EGLN (Yang et al., 202T) alternate between optimizing the graph and embeddings for gode/graph classification and collaborative filtering. [Singh et al. (021) proposes two-stage link prediction by augmenting the graph as a preprocessing step. In comparison, Gelato effectively learns a graph in an end-to-end manner by minimizing the loss of topological heuristic.
6 CONCLUSION
This work sheds light on key limitations in how GNN-based link prediction methods handle the intrinsic class imbalance of the problem and presents more effective and efficient ways to combine attributes and topology. Our findings might open new research directions machine learning for graph data, including a better understanding of the advantages of increasingly popular and sophisticated deep learning models compared to more traditional and simpler graph-based solutions.
9

---

Under review as a conference paper at ICLR 2023
ETHICS STATEMENT
Link prediction might be used to disclose private user information (e.g. in social and communication networks). Further research is needed to better protect such sensitive information and prevent its misuse by governments, corporations, and other possibly ill-intentioned parties.
REPRODUCIBILITY STATEMENT
Our code is anonymously available at https:://////....... htttp:://nooyymottt /aannnmoooosssso.o 4open sci ence/r/Gell ato which includes a reference implementation artifacts, tuned hyperparameters, and detailed instruction for reproducing our results. Our main findings- Table 2. Figure 3) and Figure 4 can be reproduced with one line of code using our repository. In addition, detailed description of the datasets can be found in Appendix [ detailed discussion on hyperparameter choices can be found in Appendix C and detailed experiment settings and reference of baseline repositories can be found in Appendix
the proposed model, dataset splits, pretrained model
REFERENCES
Lada A Adamic and Eytan Adar. Friends and neighbors on the web. Social networks, 25(3):211-20,, 2003.
David C Anastasiu and George Karypis. L2ap: Fast cosine similarity search with prefix 1-2 norm bounds. In ICDE, 2014.
Ashwin Bahulkar, Boleslaw K Szymanski, N Orkun Baycik, and Thomas C Sharkey. Community detection with edge augmentation in criminal networks. In ASONAM, 2018.
Albert-Laszlo Barabási, Hawoong Jeong, Zoltan Néda, Erzsebet Ravasz, Andras Schubert, and Tamas Viesek. Evolution of the social network of scientific collaborations. Physica A: Statistical mechanics and its applications, 31 (33((4))590--) 614, 2002.
Antoine Bordes, Nicolas Usunier, Alberto García -uráán Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In NeurlPS, 2013.
Sebastian Bruch. An alternative cross entropy loss for learning-to-rank. In WebConf. 2021.
Chris Burges, Tal Shaked, Erin Renshaw, Ari Lazier, Matt Deeds, Nicole Hamilton, and Greg Hullender. Learning to rank using gradient descent. In ICML, 2005.
Lei Cai, Jundong Li. Jie Wang, and Shuiwang Ji. Line graph neural networks for link prediction. IEEE TPAMI, 2021.
Liwei Cai and William Yang Wang. Kbgan: Adversarial learning for knowledge graph embeddings. In ACL, 2018
Fatih Cakir, Kun He, Xide Xia, Brian Kulis, and Stan Sclaroff. Deep metric learning to rank. In CVPR, 2019.
Ines Chami, Zhitao Ying, Christopher Ré, and Jure Leskovec. Hyperbolic graph convolutional neural networks. In NeurIPS, 2019.
Xu Chen, Xiuyuan Cheng, and Stéphane Mallat. Unsupervised deep haar scattering graphs. NeurlPS, 2014.
Yu Chen, Lingfei Wu, and Mohammed Zaki. Iterative deep graph learning for graph neural networks: Better and robust node embeddings. In NeurlPS, 2020.
Yuzhou Chen, Yulia R Gel, and Vincent Poor. Bsenets: Block simplicial complex neural networks. In AAAI, 2022.
Arlei Lopes da Silva, Furkan Kocayusufoglu, Saber Jafarpour, Francesco Bullo, Ananthram Swami, and Ambuj Singh. Combining physics and machine learning for network flow estimation. In ICLR, 2020.
10

---

Under review as a conference paper at ICLR 2023
J-C Delvenne, Sophia N Yaliraki, and Mauricio Barahona. Stability of graph communities across time scales. PNAS, 107(29::1755-12766) 2010.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He. Learning discrete structures for graph neural networks. In JCML, 2019.
Yoav Freund, Raj Iyer, Robert E Schapire, and Yoram Singer. An efficient boosting algorithm for combining preferences. JMLR, 9(Nov):933-969, 2003.
C Lee Giles, Kurt D Bollacker, and Steve Lawrence. Citeseer: An automatic citation indexing system. In ACM conference on Digital libraries, 1998.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In SIGKDD, 2016.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NeurIPS, 2017.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In NeurIPS, 2020.
Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin R Benson. Combining label propagation and simple models out-performs graph neural networks. ICLR, 2020.
Zexi Huang, Arlei Silva, and Ambuj Singh. A broader picture of random-walk based graph embedding. In SIGKDD, 2021.
Zexi Huang, Arlei Silva, and Ambuj Singh. Pole: Polarized embedding for signed networks. In WSDM, 2022.
Boris Ivanovic and Marco Pavone. The trajectron: Probabilistic multi-agent trajectory modeling with dynamic spatiotemporal graphs. In ICCV, 2019.
Mohsen Jamali and Martin Ester. Trustwalker: a random walk model for combining trust-based and item-based recommendation. In SIGKDD, 2009.
Glen Jeh and Jennifer Widom. Simrank: measure of structural-context similarity. In SIGKDD, 2002.
Leo Katz. A new status index derived from sociometric analysis. Psychometrika, 18(1):39-433 1953.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. In ICLR, 2015.
Thomas Kipf and Max Welling, Variational graph auto-encoders. arXiv preprint 1e..iv:661..724. 2016.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In ICLR, 2018.
Yehuda Koren, Robert Bell, and Chris Volinsky. Matrix factorization techniques for recommender systems. Computer, 42(8):30-37, 2009.
Cheng Li, Jiaqi Ma. Xiaoxiao Guo, and Qiaozhu Mei. Deepcas: An end-to-end predictor of information cascades. In WebConf, 2017.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In AAAI, 2018

---

Under review as a conference paper at ICLR 2023
David Liben-Nowell and Jon Kleinberg. The link iink-prediction problem for social networks. Journal of the American society for information science and technology. 58(7):101--0011, 2007.
Zheyi Liu, Darong Lai, Chuanyou Li, and Meng Wang. Feature fusion based subgraph classification for link prediction. In CIKM, 2020.
Linyuan Lü and Tao Zhou. Link prediction in complex networks: A survey. Physica A: statistical mechanics and its applications, 390(6): 1100))1111111100000 2011.
Jiaqi Ma, Bo Chang, Xuefei Zhang, and Qiaozhu Mei. Copulagnn: towards integrating representa-
tional and correlational roles of graphs in graph neural networks. In ICLR, 2020.
Travis Martin, Brian Ball, and Mark EJ Newman, Structural inference for uncertain networks. Physical Review E, 93(1):012306 2016.
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.
Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton Van Den Hengel. recommendations on styles and substitutes. In SIGIR, 2015.
Image-based
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3(2):127-163, 2000.
Brian McFee and Gert Lanckriet. Metric learning rank. In ICML, 2010.
Federico Monti, Michael Bronstein, and Xavier Bresson. Geometric matrix completion with recurrent multi-graph neural networks. In NeurIPS, 2017.
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 AAAI, 2019.
Mark EJ Newman. Clustering and preferential attachment growing networks. Physical review E, 64(2):025102, 2001.
Mingdong Ou, Peng Cui, Jian Pei, Ziwei Zhang, and Wenwu Zhu. Asymmetric transitivity preserving graph embedding. In SIGKDD, 2016.
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999.
Liming Pan, Cheng Shi, and Ivan Dokmanić. Neural link prediction with walk pooling. In ICLR, 2022.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. In NeurlPS, 2019.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions. In SIGKDD, 2014.
Yanjun Qi. Ziv Bar-Joseph, and Judith Klein-Seethand Seii--eettarammn. Evaluation of different biological data and computational classification methods for use protein interaction prediction. Proteins: Structure, Function, and Bioinformatics, 63(3):490-500 2006.
Jiczhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec. In WSDM, 2018a. 8a.
Jiezhong Qiu, Jian Tang, Hao Ma, Yuxiao Dong, Kuansan Wang, and Jie Tang. Deepinf: Social influence prediction with deep learning. SIGKDD, 2018b.
Jerome Revaud, Jon Almazán, Rafael S Rezende, and Cesar Roberto de Souza. Learning with average precision: Training image retrieval with listwise loss. In ICCV, 2019.
12

---

Under review as a conference paper at ICLR 2023
Sunil Kumar Sahu, Fenia Christopoulou, Makoto Miwa, and Sophia Ananiadou. Inter-sentence relation extraction with document-level graph convolutional neural network. In ACL, 2019.
Takaya Saito and Mare Rehmsmeier. The precision-recall plot is more informative than the roc plot when evaluating binary classifiers on imbalanced datasets. PloS one, 10(3)=e01 18432, 2015.
Alvaro Sanchez-Gonzalez, Nicolas Heess, Jost Tobias Springenberg. Josh Merel, Martin Riedmiller, Raia Hadsell, and Peter Battaglia. Graph networks as learnable physics engines for inference and control. In JCML, 2018.
Venu Satuluri and Srinivasan Parthasarathy. Bayesian locality sensitive hashing for fast similarity search. In VLDB, 2012.
Hinrich Schütze, Christopher D Manning, and Prabhakar Raghavan. Introduction to information retrieval, volume 39, Cambridge University Press Cambridge, 2008.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):93-995 2008
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint wwXiv:/81.00886 2018.
Abhay Singh, Qian Huang, Sijia Linda Huang, Omkar Bhalerao, Horace He, Ser-Nam Lim, and Austin R Benson. Edge proposal sets for link prediction. arXiv preprint arXiv:2106. 15810, 2021.
Kihyuk Sohn. Improved deep metric learning with multi-class n-pair loss objective. NeurIPS, 2016.
Haitian Sun, Bhuwan Dhingra, Manzil Zaheer, Kathryn Mazaitis, Ruslan Salakhutdinov, and William Cohen. Open domain question answering using early fusion of knowledge bases and text. In EMNLP, 2018a
Zhiqing Sun, Zhi-Hong Deng, Yun Nie, and Jian Tang. Rotate: Knowledge graph embedding by relational rotation in complex space. In ICLR, 2018b.
Jie Tang, Jing Zhang, Limin Yao, Juanzi Li. Li Zhang, and Zhong Su. Arnetminer: extraction and mining of academic social networks. In SIGKDD, 2008
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
Peifeng Wang, Shuangyin Li, and Rong Pan. Incorporating gan for negative sampling in knowledge representation learning. AAAI, 2018.
Xiang Wang, Xiangnan He, Yixin Cao, Meng Liu, and Tat-Seng Chua. Kgat: Knowledge graph attention network for recommendation. SIGKDD, 2019a.
Xinshao Wang, Yang Hua, Elyor Kodirov, Guosheng Hu, Romain Garnier, and Neil M Robertson. Ranked list loss for deep metric learning. In ICCV, 2019b.
Bryan Wilder, Eric Ewing, Bistra Dilkina, and Milind Tambe, End to end learning and optimization on graphs. NeurIPS, 2019.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty. Tao Yu, and Kilian Weinberger. Simplify- ing graph convolutional networks. In ICML, 2019.
Fen Xia, Tie- Yan Liu, Jue Wang, Wensheng Zhang, and Hang Li. Listwise approach to learning to rank: theory and algorithm. ICML, 2008
Zuoyu Yan, Tengfei Ma, Liangcai Gao, Zhi Tang, and Chao Chen. Link prediction with persistent homology: An interactive view. In ICML., 2021.
Bishan Yang, Scott Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference in knowledge bases. In ICLR, 2015.
13

---

Under review as a conference paper at ICLR 2023
Yonghui Yang, Le Wu, Richang Hong, Kun Zhang, and Meng Wang. Enhanced graph learning for collaborative filtering via mutual information maximization. In SIGIR, 2021.
Zhilin Yang. William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In ICML, 2016.
Liang Yao, Chengsheng Mao, and Yuan Luo. Graph convolutional networks for text classification. In AAAL, 2019.
Zhitao Ying, Jiaxuan You. Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hicrarchical graph representation learning with differentiable pooling. NeurIPS, 2018.
Seongjun Yun, Seoyoon Kim, Junhyun Lee, Jaewoo Kang, and Hyunwoo J Kim. Neo-gnns: Neigh- borhood overlap-aware graph neural networks for link prediction. In NewrIPS, 2021.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. NeurIPS, 2018.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In AAAI, 2018a.
Yiding Zhang, Xiao Wang, Chuan Shi, Nian Liu, and Guojie Song. Lorentzian graph convolutional networks. In WebConf, 2021.
Ziwei Zhang, Peng Cui, Xiao Wang, Jian Pei, Xuanrong Yao, and Wenwu Zhu. Arbitrary-order proximity preserved network embedding. In SIGKDD, 2018b.
Cheng Zheng, Bo Zong, Wei Cheng, Dongjin Song, Jingehao Ni, Wenchao Yu, Haifeng Chen, and Wei Wang. Robust graph representation learning via neural sparsification. In ICML, 2020.
Tao Zhou, Linyuan Lü, and Yi-Cheng Zhang. Predicting missing links via local information. The European Physical Journal B, 71 71(4):623-66 -300, 2009.
Zhaocheng Zhu, Zuobai Zhang, Louis-Pasee Xhonneux, and Jian Tang. Neural bellman-ford networks: general graph neural network framework for link prediction. In NeurIPS, 2021.
14

---

Under review as a conference paper at ICLR 2023
A ANALYSIS OF LINK PREDICTION EVALUATION METRICS WITH DIFFERENT TEST SETTINGS
In Section 2
we present example scenario where bad link prediction model that ranks 1M false positíves higher than the 100k true edges achieves good AUC/AP with biased testing. Here, we provide the detailed computation steps and compare the results with those based on unhiased testing.
Figure 7a Figure 76 show the receiver operating characteristic (ROC) and precision-recal (PR) curves for the model under biased testing with equal negative samples. Due the downsampling, only 100k
100k (out of 99.9M) negative pairs are included in the test set, among which only 99.9M x 1M R 1k pairs are ranked higher than the positive edges. In the ROC curve, this means that once the false positive rate reaches 1k 0.99. Similarly, in the PR curve, when the recall reaches 1.0, the precision is Tk+ TOoK to an overall AP score of ~0.95.
Took = 0.01, the true positive rate would reach 1.0, leading to an AUC score of 100k
RJ 0.99, leading
By comparison, as shown Figure 7c when the recall reaches 1.0, the precision under unbiased
100k testing is only IM-+100k ~ 0.09, leading to an AP score of ~0.05. This demonstrates that evaluation metrics based on biased testing provide an overly optimistic measurement of link prediction model performance compared to the more realistic unbiased testing setting.
(a) ROC
(b) under biased testing
(c) under unbiased testing
1.0
1.0
AP 0.05
0.99
pos rate
0.8
0.8
0.8
Precision
Precision
0.6
0.2
0.09
AUC
0.99
AP
0.95
00.010.2
0.4
0.6
0.8
1.0
0.2
0.4
0.6
0.8
1.0
0
0.2
0.4
0.6
0.8
1.0
positive
Recall
Recall
Figure 7: Receiver operating characteristic and precision- recall curves for the bad link prediction model that ranks IM false positives higher than the 100k true edges. The model achieves 0.99 in AUC and 0.95 AP under biased testing, while the more informative performance evaluation metric, Average Precision (AP) under unbiased lesting, is only 0.05.
B DESCRIPTION OF DATASETS
We use the following datasets in our experiments (with their statistics in Table 1
CORA (McCallum al. 2000) and CiteSeer (Giles et al. 1998) are citation networks where nodes represent scientific publications (classified into seven and six classes, respectively) and edges represent the citations between them. Attributes of each node is a binary word vector indicating the absence/presence of the corresponding word from a dictionary.
PUBMED (Sen et al. 2008) is a citation network where nodes represent scientific publications (classified into three classes) and edges represent the citations between them. Attributes of each node is a TF/ID weighted word vector.
PHOTO and COMPUTERS are subgraphs the Amazon co-purchase graph (McAuley et al., 2015) where nodes represent products (classified into eight and ten classes, respectively) and edges imply that two products are frequently bought together. Attributes of each node is bag-of-word vector encoding the product review.
We use the publicly available version of the datasets from the www.oeerrgeemmtiiiccc...... library (Fey Lenssen 2019) (under the MIT licence) curated by Yang al. (2016) and Shehur al. (0188.
15

---

Under review as a conference paper at ICLR 2023
C SELECTED HYPERPARAMETTE AND SENSITIVITY ANALYSIS
The selected hyperparameters of Gelato for each dataset are recorded in Table and sensitivity analysis of 1) and or and / are shown in Figure and Figure 9 respectively for PHOOO and CORA.
Table 4: Selected hyperparameters of Gelato.
CoRa
CiTeSEER
PURMED
PHOтO
COMPUTERS
Proportion of added edges
0.5
0.75
0.0
0.0
0.0
Topological weight
0.5
0.5
Trained weight |
0.25
0.5
1.0
1.0
1.0
PHOTO performance
(b) CORA performance
25.8
32.4
4.00
12.0
25.2
31.8
Prec@ 100%% (%)
3.75
11.2
100% (%)
@rec@ 00%
AP (%)
24.6
31.2
3.50
10.4
24.0
30.6
3.25
9.6
23.4
30.0
3.00
8.8
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
n
Figure 8: Performance of Gelato with different values of r).
(a) РHотO AP performance
(b) PHоTO prec 100% performance
32
25
1.0
25.68
23.43
21.33
18.59
1.0
32.13
30.88
29.53
26.82
23
30
0.75
23.98
19.96
0.75
1rec@10m 100%
29
21
28
21.02
19.83
18.54
29.54
28.38
25.62
27
-19
0.25
17.08
17.34
17.20
16.93
0.25
25.53
25.82
25.59
24.99
17
25
0.0
0.25
0.5
0.75
0.0
0.25
0.5
0.75
(c) CORA AP performance
(d) CORA prec 100% performance
3.8
2.26
3.12
3.47
11
10
0.75
2.63
3.28
3.52
3.51
0.75
9.26
10.02
10.27
9.68
9
100%
3.0
Prec@100
0.5
2.86
3.54
3.81
3.60
10.11
10.89
11.01
9.81
2.6
7
2.10
2.96
3.90
3.68
0.25
5.07
8.98
11.67
9.56
2.2
0.0
0.25
0.5
0.75
0.0
0.25
0.75
Figure 9: Performance of Gelato with different combinations of a and 3.
16

---

Under review as a conference paper at ICLR 2023
For most datasets, we find that simply setting 3 = 1.0 and 17 0.0 leads to the best performance, corresponding to the scenario where no edges based on cosine similarity are added and the edge weights completely learned by the MLP. For CORA and CITESEER, however,
first notice that adding edges based on untrained cosine similarity alone leads to improved performance (see Table 2) which motivates to set 1) 0.5 0.5/0.75. In addition,
find that large trainable weight 3 leads to overfitting of the model as the number of node attributes is large while the number of (positive) edges is small for CORA and CITESEER (see Table 1p. We address this by decreasing the relative importance of trained edge weights (6 0.25/0.5) and increasing that of the topological edge weights (a 0.5), which leads better generality and improved performance. Based on our experiments, these hyperparameters can be easily tuned using simple hyperparameter search techniques, such as line search, using a small validation set.
D DETAILED EXPERIMENT SETTINGS
Data splits for unbiased training and unbiased testing. We first randomly (with seed 0) split the edges E of the original graph into Etrain Eaaisd and Ejest for training, validation, and testing.
Then, we set the negative pairs in these three sets as (1) traain = E + Etatid + Ejests (2)
Eriatid = E + Fieat and (3) Erest = EE, where E is the set of all negative pairs (excluding self-loops) in the original graph. Notice that the validation and testing positive edges are included in the negative training set, and the testing positive edges are included in the negative validation set. These inclusions simulate the real-worts scenario where the testing edges (and the validation edges) are unobserved during validation (training). For large graphs, one can downsample both positive and negative pairs to maintain the same class ratio as the input graph for training and testing.
Positive masking. For unbiased training, a trick similar to negative injection (Zhang & Chen 2018) in biased training is needed to guarantee model generalizability. Specifically, we divide the training positive edges into batches and during the training with each batch Es, we only feed in the residual edges E - Es to the model. This setting simulates the testing phase, where the model is expected to predict edges without using their own connectivity information. We term this trick positive masking.
Other implementation details. We add self-loops to the enhanced adjacency matrix to ensure that each node has valid transition probability distribution that is used in computing Autocovariance. The self-loops are added to all isolated nodes in the training graph for PUBMED, PhOTO, and COMPUTERS, and to all nodes for CORA and CITESEER. Following the postprocessing of the Autocovariance matrix for embedding in Huang et al. (2021), we standardize Gelato similarity scores before computing the loss. For training with the cross entropy loss, we further add a linear layer with the sigmoid activation function to map our prediction score to a probability. We optimize our model with gradient descent via autograd in pytorch (Paszke al. 2019). We find that the gradients are sometimes invalid when training our model (especially with the cross entropy loss), and we address this by skipping the parameter updates for batches leading to invalid gradients. Finally, we use prec@1 1 00% on the (unbiased) validation set as the criteria for selecting the best model from all training epochs. The maximum number of epochs for CORA/CCTESEER/PPRR..E. and PIloto/CoMPUTERS are set to be 100 and 250, respectively.
Experiment environment. We run our experiments in an a2- higghhgguuu---- 1g node of the Google Cloud Compute Engine. It has one NVIDIA A A100 GPU with 40GB HBM2 GPU memory and 12 Intel Xeon Scalable Processor (Cascade Lake) 2nd Generation vCPUs with 85GB memory.
Reference of baselines. We list link prediction baselines and their reference repositories we use in our experiments in Table 5) Note that we had to implement the batched training and testing for several baselines their original implementations do not scale to unbiased training and unbiased testing without downsampling.
Number of trainable parameters. The only trainable component in Gelato is the graph learning MLP, which for Photo o has 208,133 130 parameters. By comparison, the best performing GNN- based method, Neo-GNN, has more than twice the number of parameters (455,200).
17

---

Under review as a conference paper at ICLR 2023
Table 5: Reference of baseline code repositories.
Bascline
Repository
GAE
Kipf & Welling
2017
SEAL
Zhang Chen
2018
https:/
higgs//ggiiuuuoco//aaaaaaaaaaaa OGB
HGCN
Caam al.
LGCN Zhang et al.
2021
TLC-GNN
Yan et al
2021
Neo-GNN
Yun et
2021
NBFNet Zhu
2021
BSeNets CChen et 202
WalkPool Pann et al.
2022
AC (Huang et al.
2021
E RESULTS BASED ON AUC SCORES
As we have argued in Section 2 AUC is not effective evaluation metric for link prediction (even under unbiased testing) as it is biased towards the majority class. In Table 6 we report the AUC scores for different methods under unbiased lesting. These results, while being consistent with those found in the link prediction literature, disagree with those obtained using the rank-based evaluation metrics under unbiased testing.
Table 6: Link prediction performance comparison (mean + std AUC), AUC results conflict with other evaluation metrics, presenting a misleading view of the model performance for link prediction.
CORA
CITESEER
PUBMED
PHOTO
COMPUTERS
GAE
87.30 0.22
87.48 = 0.39
94.10 0.22
77.59 + 0.73
79.36 0.37
SEAL
91.82 + 1.08
90.37 0.91
98.85 + 0.04
98.7
HGCN
92.60 0.29
92.39 1.39000 0.61
94.4
96.08 + 0.08
97.86 + 0.10
LGCN
9.26
0.77
95.80 0.03
98.36 0.01
97.81 = 0.01
GNN
TLC-GNN
9.95
0.78
OOM
98.20 0.08
OOM
Neo-GNN
9..77
90.25 0.80
90.43 + 1.37
98.74
98.34"
NBFNet
86.06
85.10 0.32
98.29 + 0.35
BSeNets
9.45
89.62 1.05
97.48 0.07
98.68 + 0.06
98.41 = 0.05
WalkPool
92.33 0.30
90.73 # 0.42
98.66
0OM
OOM
CN
71.15 0.00
66.91 # 0.00
6.00
96.73 + 0.00
96.15 = 0.00
Topological Heuristics
AA
1
66.92 # 0.00
0.00
97.02 + 0.00
96.58 + 0.00
RA
71.22 0.00
66.93 0.00
97.20 0.00 6.009
96.82 0.00
AC
75.41 0.00
72.41 0.00
0.00
98.24 + 0.00
96.86 0.00
MLP
0.36
87,89
2.05
87.89
91.24
88.84
Cos
79.06 - 0.00
89.86
0.00
71.46 8.004
71.68 0.00
Attributes
MLP+AC
79.77 0.03
82.26
98.02 6.771
96.69 0.05
Topology
Cos+AC
86.34 0.00
89.29
0.00
7.00
97.28 0.00
96.26 0.00
MLP+Cos++AC
86.90 + 0.14
89.42 0.09
75.78
97.27 0.01
96.24 0.01
Gelato
83.12 + 0.06
88.38 0.02
64.93 0.06
98.01 + 0.03
96.72 + 0.04
Run only once as each run takes 100 hrs;
Each run takes >> 1000 hrs:
OOM: Out Of Memory.
18

---

Under review as a conference paper at ICLR 2023
F VISUALIZING LINK PREDICTION PROCESSES
In this section, build upon the discussion in Section 4.3 and present more detailed analysis of the improvements of Gelato over Autocovariance based on the input graph and comparisons with the link prediction process of the best GNN-based baseline (Neo-GNN) in Figure 10
Figure 10a shows the input adjacency matrix for the subgraph of PHOTO containing the top 160 nodes belonging the first class sorted in decreasing order of their (within-class) degree. Figure 10b illustrates the enhanced adjacency matrix learned by Gelato's MLP. Comparing it with the Euclidean distance between node attributes in Figure 10c| we see that our enhanced adjacency matrix effectively incorporates attribute information. More specifically, connecting the high-degree nodes with larger attribute distances (matrix entries 0-40 and especially 0-10) and the up-weighting of those connecting medium-degree nodes with smaller attribute distances (40-80). In Figure 10d and Figure 10c we see the corresponding AC scores based on the input and the enhanced adjacency matrix (Gelato). Since AC captures the degree distribution of nodes (Huang et al.) 2021), the vanilla AC scores greatly favor high-degree nodes (0-40). By comparison, thanks to the down-weighting, Gelato assigns relatively lower scores to edges connecting them to low-degree nodes (60-160), while still capturing the edge density between high-degree nodes (0-40). The immediate result of this is the significantly improved precision as shown in Figure 10h compared to Figure 10g Gelato covers many positive edges in the high-degree region as AC while making far fewer wrong predictions for connections involving low-degree nodes.
notice the down-weighting of the edges
The prediction probabilities and predicted edges for Neo-GNN are shown in Figure 10fland Figure 10i respectively. Note that while it predicts edges connecting high-degree node pairs (0-40) with high probability, similar values are assigned to many low-degree pairs (80-160) as well. Most of those predictions are wrong, both in the low-degree region of Figure 10] also in other low-degree parts of the graph that are not shown here. This analysis supports our claim that Gelato is more effective at combining node attributes and the graph topology, enabling state-of-the-art link prediction.
G ABLATION STUDY
We have demonstrated the superiority of Gelato its individual components and two-stage approaches in Table and analyzed the effect of losses and training settings Section 4.4 Here, we collect the results with the same hyperparameter setting as Gelato and present comprehensive ablation study in Table 7 Specifically, Gelato MLP (AC) represents Gelato without the MLP (Autocovariance) component, i.e., only using Autocovariance (MLP) for link prediction. Gelato NP (UT) replaces the proposed N- N-pair loss (unbiased training) with the cross entropy loss (biased training) applied by the baselines, and Gelato NP+UT replaces both the loss and the training setting.
Table 7: Results of the ablation study based AP scores. Each component of Gelato plays important role in enabling state-of-the-ee link prediction performance.
CORA
CITESEER
PUBMED
PHOTO
COMPUTERS
Gelato MLP
2.43 = 0.00
2.65 0.00
0.00
16.63 = 0.00
11.64 # 0.00
Gelato AC
1.94
0.37
0.83
7.45
4.09 = 0.16
Gelato NP+UT
1.16
0.224
1..87
9.77 = 2.67
Gelato NP
1.96
1.77
0.32
19.63
9.84
Gelato UT
3.07
0.05
0.09
23.66
11.59 = 0.35
Gelato
3.90
4.05
0.09
25.68 0.53
18.77 = 0.19
We observe that removing either MLP or Autocovariance leads to inferior performance, as the corresponding attribute topology information would be missing. Further, to address the class imbalance problem of link prediction, both the N-pair loss and unbiased training are crucial for effective training of Gelato.
19

---

Under review as a conference paper at ICLR 2023
(a) Input adjacency matrix
(b) Enhanced adjacency matrix
(c) Attribute Enclidean distance
120
160
ao
120
160
40
120
160
80
80
80
120
120
120
Edge
Nonsoge
0.1
0.2
0.4
0.5
20
25
(d) AC scores
(c) Gelato scores
(f) Neo-GNN predictions
120
120
40
40
40
80
80
180
160
10
15
25
30
10
25
30
0.995
0.995 0.997 0.998 0.999
1.000
(g) AC predicted edges
(h) Gelato predicted edges
Neo-GNN predicted edges
80
120
160
80
120
160
120
160
80
80
80
120
120
120
Thue pastive
Faise positive
True postive
False posttvve
True positive
False pos tive
Figure 10: Illustration of the link prediction process of Gelato, AC, and the best GNN-based approach, Neo-GNN, on subgraph of PHOТO. Gelato effectively incorporates node attributes into the graph structure and leverages topological heuristics enable state-of-the-an link prediction.
20

---

Under review as a conference paper at ICLR 2023
H BASELINE RESULTS WITH UNBIASED TRAINING
Table 8 summarizes the link prediction performance in terms of mean and standard deviation of AP for Gelato and the baselines using unbiased training without downsampling and the cross entropy loss, and Figure and Figure 12 show results based on precak and hils@k for varying k values.
Table 8: Link prediction performance comparison (mean + std AP) with supervised link prediction methods using unbiased training. While we observe noticeable improvement for some baselines (e.g.. BScNets), Gelato still consistently and significantly outperform the baselines.
CORA
CiTeSBER
PUBMED
PHOTO
COMPUTERS
GAE
0.33 # 0,21
0.69 = 0.18
0,63
1.36 + 3.38
7.91
SEAL
2.24"
1.11"
*е*
#**
**9
HGCN
0.54 0.23
1,02 = 0.05
0,41
3,27 + 2.97
2.60
LGCN
1.08
1,45 = 0.09
0.55
2,90 0.26
1.13
GNN
TLC-GNN
0.68 0.16
0.61 0.19
OOM
2,95 + 1.50
OOM
Neo-GNN
2.76 0.36
1,80 + 0.22
NBFNet
*8*
BSeNets
1.25
1.27 + 0.20
0.47
8.54 + 1.55
4.40"
WalkPool
OOM
OOM
CN
1.00
0.36 0.04
7.73 + 0.00
5.09 = 0.00
Topological Hcuristics
AA
2.00
1.04
0.00
9.67 0.00
6.52
RA
2.00
1.19
10.77 0.30
7.71 0.00
AC
2.65 0.00
2.50
16.63 0.00
11.64 0.00
MLP
1.67 0.27
0.12
1.15
1.19 0.46
Cos
0.42 0.00
1.89
0.07 0.00
0.11
0.07 0.00
Attributes
MLP+AC
0.63 0.63 = 0.32
1.17 1.40
11.88 0.83
8.73 0.45
Topology
Cos+AC
3.60 # 0.00
4,46 1.66
0.51 + 0.00
10.01 # 0.00
5.20 = 0.00
MLP+Cos+AC
3.80 = 0.01
0.03
0.77 0.01
12.80
7.57 = 0.02
Gelato
3.90 # 0.03
4.55 + 0.02
2.88 + 0.09
25.68 + 0.53
18.77 + 0.19
Run only once as each run takes 1000 hrs;
Each run takes >> 1000 hrs;
OOM: Out Of Memory.
Cora
CiteSeer
PubMed
Photo
Computers
Preciak
15
15
18
48
20
10
12
32
20
40
60
80
100
20
40
00
80
100
20
40
60
80
1.00
20
40
60
80
100
20
40
00
100
GAB
SEAL
MGCH
LGCN
TLC GNN
N:0 GNNN
-
NNFFNCC
-
BSchets
WolloPool
AC
Goldto
Figure 11: Link prediction performance in terms of prec@k (in percentage) for varying values of with baselines using unbiased training. While we observe noticeable improvement for some baselines (e.g., BScNets), Gelato still consistently and significantly outperform the baselines.
Cora
CiteSeer
PubMed
Photo
Computers
Htsokk (9)
42-
20
28
16
14
25
C-CEN
Nec-CMNN
+
BSG Narts
WillePool
AC
Golato
Figure 12: Link prediction performance in terms of hits@A (in percentage) for varying values of with basclines using unbiased training. While we observe noticeable improvement for some baselines (e.g., BScNets), Gelato still consistently and significantly outperform the baselines.
21

---

Under review as a conference paper at ICLR 2023
We first note that unbiased training without downsampling brings serious scalability challenges to most GNN-based approaches, making scaling up to larger datasets intractable. For the scalable baselines, unbiased training leads to marginal (c.g., Neo-GNN) significant (e.g., BScNets) gains in performance. However, all of them still underperform the topological heuristic, Autocovariance, in most cases, and achieve much worse performance compared to Gelato. This supports claim that the topology-centric graph learning mechanism in Gelato is more effective than the attribute-centric message-passing in GNNs for link prediction, leading to state-of-the-ar performance.
As for the GNN-based baselines using both unbiased training and our proposed N-pair loss, we have attempted to modify the training functions of the reference repositories the baselines and managed to train SEAL, LGCN. Neo-GNNY and BScNet. However, despite our best efforts, we are unable to obtain better link prediction performance using the N-pair loss. We defer the further investigation of the incompatibility of our loss and the baselines to future research. On the other hand, we have observed significantly better performance for MLP with the N-pair loss compared to the cross entropy loss under unbiased training. This can be seen by comparing the MLP performance in Table 8 here and the Gelato AC performance Table 7 in the ablation study. The improvement shows the potential benefit of applying our training setting and loss other supervised link prediction methods.
We also show the training time comparison between different supervised link prediction methods using unbiased training without downsampling in Table 9 Gelato is the second fastest model, only slower than the vanilla MI.. This further demonstrates that Gelato is a more efficient alternative compared to GNNs.
Table 9: Training time comparison between supervised link prediction methods for PHOOO under unbiased training. Gelato, while achieving the best performance, is also the second most efficient method in terms of total training time, slower only than the vanilla MLP.
GAE
SEAL
HGCN
LOCN
TLC-GNN
Noo-GNN
NBFNet
BScNets
MLP
Gelato
Training
6,361
-550,000
1,668
1,401
53,304
5450,000
-550,000
2,323
744
1,285
22


Reviews:
[{"review_id": "r8S7k4rRcfI", "reviewer": "Reviewer_maA8", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper is a re-submission. I have previously reviewed and the authors made only minor changes without incorporating the feedback from their prior submission.\n\nThe paper rightly critises biased testing in homogenous graph link prediction and proposes to combine topological features with MLPs for this problem.", "summary_of_the_review": "A re-submission that doesn't adress the weaknessess from the last round of feedback (see Weaknessess section). Clear reject.", "strength_and_weaknesses": "Weaknesses:\n1. A low-effort re-submission!!\n2. Doesn't cite and compare to the relevant Knowledge graph link prediction literature, which for a long time now uses unbiased testing (i.e. the idea is not new) as well as failing to compare their loss function to negative sampling from the KG community.\n3. The benchmark datasets are simply not interesting anymore and are not sufficient to validate the empirical performance of their method, they should incorporate the homogenous graph link prediction datasets from OGB at least.\n\nStrengths:\n1. Method is efficient.\n2. Clear writing.\n3. Rightly criticises biased testing.\n4. Models that are compared against are representative.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "RAjCD5UCH-", "reviewer": "Reviewer_p64G", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper presents a model for link prediction without graph neural networks. The authors firstly examine existing benchmarks and argue they are biased towards positive links. Then, they propose an effective framework with graph structure learning with a topology heuristic. A series experiments show the superior performance of the proposed approach.", "summary_of_the_review": "I think this work provides an important contribution to \"graph-less\" neural networks for link prediction, but I feel like the motivation of this work needs further elaboration. Some claims on existing \"biased\" models are too strong.", "strength_and_weaknesses": "Strengths:\n+ This paper is easy to read and follow.\n+ The proposed strategy significantly outperforms existing benchmarks and especially improves efficiency.\n\nWeaknesses:\n- Several statements may be too strong to claim. For example: in Page 2 the authors claim existing approaches \"highly overestimate\" the ratio of positive pairs. I feels skeptical about this claim, as the negative pairs are randomly drawn rather than fixed. It is not clear to me why they are biased towards positive pairs. Similarly, I am not clear about why prior approaches need to construct a biased test dataset.\n- I in person believe there is a gap between the motivation and the model design. The only connection I can see is the objective Eq. (16) uses a full set of negative links, where prior approaches can do this as well.\n- Experimental results are not fully convincing. On several experiments (Cora, Citeseer, Pubmed) the improvements seem marginal. The overall dataset sizes are small. It seems that the model is very sensitive to the parameter $\\eta$. More explanations are needed. Also, more head-to-head ablation studies are needed. For example, I am curious whether the graph structure learning component (Attributes+Topology) can be used with conventional training schemes.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "H37WYohOFsi", "reviewer": "Reviewer_L8KX", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "In this work, the authors propose an interesting and novel technique towards solving the problem of link prediction in graphs without using GNN based approach which happens to be the predominant methodology at present. The authors also demonstrate training their model using an N-pair loss (akin to metric learning based loss) to address class imbalance in real-world graph datasets. The authors demonstrate the efficacy of their approach via empirical results.", "summary_of_the_review": "The authors present an interesting and lightweight approach towards solving the problem of link prediction. The main issues with the current work is the limited level of novelty and the heuristic aspects of the work which require more discussion and/or more work. ", "strength_and_weaknesses": "Here below are some associated strengths of the paper :\n\n1) Even though graph augmentation based techniques previously exist in the literature, the authors present an interesting perspective of solving the link prediction problem without using GNN explicitly. \n\n2) The authors highlight and make an effort to solve the class imbalance problem in graph datasets which hampers model performance significantly. \n\n3) The approach proposed is a lightweight one which can easily be incorporated and would potentially help model performance in the link prediction problem.\n\n4) The empirical results demonstrate the efficacy of the approach effectively.\n\nHere below are some associated weaknesses of the paper :\n\n1) While there is some merit in the approach presented and the expectation from the reviewer is that this current work might usher in a new field of work, in general the level of novelty of the current approach is incremental in nature and requires more refinement. For example, graph augmentation/enrichment is known in literature as well as metric learning based loss functions as well as the auto covariance based similarity matrix which has demonstrated excellent performance for link prediction based tasks.\n\n2) The approach felt pretty heuristic. In particular the approach is strongly dependent on a similarity metric/function and an associated threshold. The paper does not contain any discussion as to how to choose this similarity metric/function and the associated threshold in general. The authors themselves choose cosine similarity but does this work well in all scenarios. The current work requires more discussion in general. \n\n3) The current work should have included more baselines to compare against. \n\n4) The current work does not list any limitations and/or potential directions for improvement which would have significantly added to the value associated with the work. As mentioned earlier, the current work requires more discussion to be included in general. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "4sh1sI4HzU", "reviewer": "Reviewer_SSk7", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "The authors first the important limitations in how GNN-based link prediction methods handle the intrinsic class imbalance of the problem—due to the graph sparsity—in their training and evaluation. Moreover, the authors propose Gelato, a novel topology-centric framework that\napplies a topological heuristic to a graph enhanced by attribute information via graph learning. Gelato is trained end-to-end with an N-pair loss on an unbiased training set to address the class imbalance.", "summary_of_the_review": "Please refer to the above review comments for improvements.", "strength_and_weaknesses": "Pros: the authors scrutinize the training and evaluation of supervised link prediction methods and identify their limitations in handling class imbalance; the authors propose a simple, effective, and efficient framework to combine topological and attribute information for link prediction without using GNNs; and they introduce an N-pair link prediction loss combined with an unbiased set of training edges that we show to be more effective at addressing the class imbalance.\n\nCons: The authors only use some small datasets for evaluation, on which there do not exist standard splits for different methods to be evaluated in a standard manner. The authors are suggested to test their method on larger datasets such as OGBL ones to comprehensively evaluate their method.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject