Neo-GNNs: Neighborhood Overlap-aware Graph Neural Networks for Link Prediction
Authors: Seongjun Yun
Seoyoon Kim
Junhyun Lee
Jaewoo Kang
Hyunwoo J. Kim
Venue: NeurIPS 2021 Poster (2021)
Keywords: Graph Neural Networks
Link Prediction
Graph Structure
Common Neighbors

Abstract: Graph Neural Networks (GNNs) have been widely applied to various fields for learning over graph-structured data. They have shown significant improvements over traditional heuristic methods in various tasks such as node classification and graph classification. However, since GNNs heavily rely on smoothed node features rather than graph structure, they often show poor performance than simple heuristic methods in link prediction where the structural information, e.g., overlapped neighborhoods, degrees, and shortest paths, is crucial. To address this limitation, we propose Neighborhood Overlap-aware Graph Neural Networks (Neo-GNNs) that learn useful structural features from an adjacency matrix and estimate overlapped neighborhoods for link prediction. Our Neo-GNNs generalize neighborhood overlap-based heuristic methods and handle overlapped multi-hop neighborhoods. Our extensive experiments on Open Graph Benchmark datasets (OGB) demonstrate that Neo-GNNs consistently achieve state-of-the-art performance in link prediction.


Neo-GNNs: Neighborhood Overlap-aware Graph Neural Networks for Link Prediction
Seongjun Yun, Seoyoon Kim, Junhyun Lee, Jaewoo Kang", Hyunwoo J. Kim"
Department of Computer Science and Engineering Korea University
(ysj5419, sykim45, Ijhyun333, kangj. hyunwoojkim) @ @oorea.ac.rr
Abstract
Graph Neural Networks (GNNs) have been widely applied to various fields for learning over graph graph-structured data. They have shown significant improvements over traditional heuristic methods in various tasks such as node classification and graph classification. However, since GNNs heavily rely on smoothed node features rather than graph structure, they often show poor performance than simple heuris- tic methods link prediction where the structural information, e.g., overlapped neighborhoods, degrees, and shortest paths, is crucial. To address this limitation, we propose Neighborhood Overlap-awarc Graph Neural Networks (Nco-GNNs) that learn useful structural features from adjacency matrix and estimate over- lapped neighborhoods for link prediction. Our Neo-GNNs generalize neighborhood overlap-basee based heuristic methods and handle overlapped multi-hop neighborhoods. Our extensive experiments on Open Graph Benchmark datasets (OGB) demonstrate that Neo-GNNs consistently achieve state-of-the-art performance in link prediction.
1 Introduction
Graph-structured data is ubiquitous in a wide range of domains ranging from social network analysis B to biology 6 and computer vision |
g [0] In recent years, numerous variants of Graph neural networks (GNNs) have been proposed for learning representations over graph-structured data. GNNs learn low dimensional representations of nodes graphs via iterative aggregation of features from neighbors using non-linear transformations. In this manner, GNNs have shown significant improvements over traditional methods, e.g., heuristic methods and embedding-basee methods, and achieved state-of-the-an performance on various tasks, such as node classification
13 14 15), graph classification [6
19 20 and graph generation 2
22
2
24
However, in link prediction, traditional heuristic methods still show competitive performance com- pared to GNNs, which often outperform GNNs. This is because struetural information, (e.g., overlapped neighborhoods, degrees, and shortest path). is crucial for link prediction whereas GNNs heavily rely smoothed node features rather than graph structure. Recently, SEAL 25 has been proposed to consider structural information for link prediction by utilizing the relative distance between the target node pair and their neighborhoods. Nonetheless, SEAL requires the expensive computational cost to apply a GNN independently to an extracted subgraph for each target node pair.
To address this limitation, GNNs) that are designed to consider key structural information regarding links without manual processes. Specifically, instead of using input node features, Neo-GNNs first learn to generate useful structrual features for each node from an adjacency matrix. Then Neo-GNNG measure the existence of links by considering the structural features of overlapped neighbhorhoods via neighbhorhood
propose Neighborhood Overlap-aware Graph Neural Networks (Neo-
corresponding author
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

overlap-aware aggregation scheme. Finally, to consider both structural information and input node features, our proposed model adaptively combines scores from Neo-GNNs and feature-based GNNs in an end-to-end fashion. We show that Neo-GNNs consistently outperform both state-of-the-an GNNs and heuristic methods on four Open Graph Benchmark datasets (OGB) for link prediction. Furthermore, Our Neo-GNNs generalize the neighborhood overlap-based heuristic methods which measure the likelihood of the link based on manually designed structural information of overlapped neighbors.
Our contributions are as follows: (i) We propose Neighborhood Overlap-aware Graph Neural Networks NNo-GNNNs that learn useful structural features from an adjacency matrix and estimate overlapped neighborhoods for link prediction. (ii) Neo-GNNs generalize neighborhood overlap- based heuristic methods and handle overlapped multi-hop neighborhoods. (ii) Our extensive experi- ments on Open Graph Benchmark datasets (OGB) demonstrate that Neo-GNNN consistently achieve state-of-the-ar performance in link prediction.
2
Related Works
Graph Neural Networks. GNNs have been designed to learn node representations by using neural networks on graph topology. Among deep learning based approaches. the message passing scheme is dominantly used in recent studies such as GCN [II], GraphSAGE (6]. and GAT [12. Due to the iterative aggregation step, each node representation vector can have information of neighbor nodes in multi-hop relationships required for downstream tasks. However, there is limitation of the expressive power that is upper-bounded by the I-Weisfeiler-Lehman (I-WL) graph isomorphism test. To overcome this limitation, recent works have tried to boost the expressive power of GNNs by augmenting node features with ordering vectors or position-aware vectors [1] 27 28 The main purpose of these works is to complement GNNs with structural information which is crucial for prediction tasks. Our study focuses on adaptively incorporating structural information to GNNs for the link prediction task.
Link prediction has been studied in various ways. Conventionally, diverse heuristic methods have been proposed for link prediction. They basically measure the scores of given node pairs based on structural information e.g., overlapped neighbors and shortest path, about the pair of nodes. Common neighbors and preferential attachment (29) exploit structural information about one-hop neighbors to compute the score. To consider more than one-hop relationships, second-order
Link Prediction.
heuristic methods (e.g., Adamic-Adar (30) and resource allocation (31) ) and higher-order heuristic
methods (e.g., Katz [32] PageRank [33] and SimRank (34) have been proposed. Heuristic methods extremely effective for link prediction. However, they require manually designed structural information for each heuristic method. To overcome this limitation, embedding-basee basedd methods have been proposed. They learn node embeddings based connections between nodes and compute similarity scores using the embeddings. Typically, Matrix factorization [35] learns node embeddings by decomposing an adjacency matrix of the graph. Random bask- embedding methods such as Deepwalk [36], and node2vec (37] learn node embeddings by applying the Skip-Gram (38] techniques on the random walks. LINK 39) learns to classify the existence of links based on each row in the adjacency matrix, which includes connectivity information. Since the performance of the embedding methods depends on the sparsity of the input graph, it is hard regard these methods as generalized ones. Recently, with the success of GNNs in learning graph representations, there have been several attempts to apply them to the link prediction task. Typically, GAE and VGAE [40 learn node representations through GCN to reconstruct the input graph in the auto-encoder framework. Based on the GAE, various GNN architectures have been applied to link prediction. On the other hand, SEAL (25) reformulated the link prediction task to the classification of enclosing subgraphs. Instead of directly predicting the link, enclosing graphs are sampled around each target link to compose dataset and SEAL performs the graph classification task. Due to the node labeling step to mark nodes' different roles an enclosing subgraph. SEAL has better performance than GAE even though both are GNN-based methods. However, constructing subgraphs is inefficient because it requires a large amount of computation, whereas our model is as efficient as GAE and can consider structural information like SEAL.

---

3 Methods
The goal of our framework, Neighborhood Overlap-aware Graph Neural Networks (Nco-GNNs), is to learn useful structural features from an adjacency matrix and estimate overlapped neighbors for link prediction. We begin with defining the basic notions of graph neural networks for link prediction and review neighborhood perlap-based heuristic methods, and then introduce Neo-GNNs.
3.1 Preliminaries
Notations. Consider an undirected graph (V,E) with N nodes, where V/ {ur, U2..... UN represents set of nodes and & = {eg 0, Uy E }} represents a set of edges where the nodes U; V are connected. The adjacency matrix A E R-N is defined by Aij 1 i eij
& and O otherwise. The degree matrix D E R N*N is diagonal matrix defined by D; Σ5 Aig- The nodes
eij
of G have their own feature vectors E RR" (i E (1,2...., with X E R Nx denoting the collection of such vectors in a matrix form.
Graph Neural Networks for Link Prediction. Given a graph G and feature matrix X, graph neural networks learn meaningful node representations by an iterative aggregation of transformed representations of neighbor nodes in each 1-th GNN layer as follows:
H(+1) (ACNNH+
(1)
where ÂONN E RNN NXN is the adjaceney matrix normalized in different ways depending on each GNN architecture (e.g. D- + D)) w E R xd()+)) is trainable weight matrix, and H7 is
the node feature matrix X R N~ After stacking L GNN layers, node representations H
then used to predict existence of each link (1.
のU = (s(h)) (.n,,, ()))))
where s(.,)) is a function, egg. inner product or MLP, and (T)) is the representation of the node i from (L))
3.2 Neighborhood Overlap-based Heuristic Methods
Heuristic methods for link prediction measure the score of given node pairs based structural information about the node pairs, e.g., shortest path, degree, and common neighbors. Although GNNs outperform existing traditional heuristic methods in various graph tasks, in link prediction, since GNNs heavily rely on smoothed node features rather than graph structure, the heuristic methods often show competitive performance compared GNNs. Especially, neighborhood overlap- based heuristic methods are straightforward yet highly effective, even better than GNN models in several datasets, e.g., ogbl-collab and ogbl-ppa. Typical neighborhood overlap-based heuristic methods are Common Neighbors, Resource Allocation (RA) (31), and Adamic Adar [30]. The Common Neighbors method measures the score of link (u, v) by counting the number of common neighbors between node u and e as
ScN(u, v) (N())
Σ
1.
(3)
(EN(W))N(
The Common Neighbors method is simple and effective, but has a limitation that equally weighs the importance of each common neighbor. To solve this issue, several heuristic methods e.g., Resource Allocation, and Adamic-Adar measure the score for the link by considering the importance of each common neighbor. From the intuition that neighbor nodes with lower degrees are more significant, they give more weight to neighbors with lower degrees. Specifically, Resource Allocation (RA) [1 measures the score of link (u, v) by counting the inverse degrees of common neighbors between node and
SRA(U,
Σ
(4)
de
(EN(W)NN())
where de denotes the degree of node k. Adamic-Ade has a relatively decreased penalty for higher degree compared to RA by using the reciprocal logarithm of common neighbors' degrees between
3

---

GNN(X, WONN;
OSI
(a)
diago
y/
c
Aum
strwet
Fo
X
Xateet
B
trast
B
X
mm
(a)
(b)
Cc)
(d)
Figure I: The Neo-GNNs framework for link prediction. Neo-GNNs learn useful structural features from an adjacency matrix and estimate similarity scores based on overlapped neighborhoods. (a)
Neo-GNNs first generate the structural feature vector sstruct E R Nx1 from an adjacency matrix
A E R N by using Structural feature generator Fe, i.e., (A). Then to consider only features of overlapped neighbors between nodes, (b) Neo-GNNs construct diagonal matrix Xstract R N and (c) aggregate the features of multi-hop neighborhoods by multiplying the sum of powers of adjacency matrices, ie., E 3'-1 A'. Finally, two node representations Z and H, respectively from Neo-GNNs and feature- GNNs, used to (d) compute similarity scores and combined adaptively with the learnable parameter c..
node and
SA)(U,))=
Σ
(5)
log dz
kEA(W)nW(e)
These heuristic methods show comparable performance to GNNs for link prediction.
However, they have two limitations. First, each heuristic method uses manually designed structural features of neighborhoods, e.g., 1, d' logd This requires the manual choice by domain experts to select the best heuristic method for each dataset. Second, they only consider structural similarity. While the GNNs do not use graph structures well compared to using node features, heuristic methods cannot utilize the node features for link prediction.
To address the limitations both GNNs and heuristic methods, we propose Neighborhood Overlap- aware Graph Neural Networks (Neo-GNN), that learn useful structural features from an adjacency matrix and estimate overlapped neighborhoods for link prediction, and adaptively combine with the conventional feature-based GNNs in an end-to-end fashion.
3.3 Neighborhood Overlap-aware Graph Neural Networks
We now introduce Neighborhood Overlap-aware Graph Neural Networks (Neo-GNNs) for link prediction. We first explain how Neo-GNNs learn and utilize structural information for link prediction and then explain the process of adaptively combining with the feature-based GNNs.
Neo- GNNs consist of two key components: (1) Structural feature generator and (2) neighborhood overlap-aware aggregation scheme. First, as we discussed in section 3.2, each heuristic method uses manually designed structural features of neighborhoods, 1, 7 a To generalize and learn these structural features, propose Structural feature generator Fe which learns to generate structural

---

using the structural feature features of each node using an only adjacency matrix A E R N of the graph
1 aetruct = =o((A)) = fornda
Σ jEN;
fordge (Ais)
(6)
where a. axtruct is a structural feature value the node and F9 is a learnable function comprised of two MLPs, fonoee and fo for nodes and edges, respectively. That is say, Neo-GNNs take only an adjacency matrix A as an input to generate the most beneficial structural features. This input adjacency matrix A can be replaced with the combination of powers of adjacency matrices. Now, Structural feature generator Fø can generate structural features for each heuristic method. For example, if fen is reciprocal of the logarithm function, i... f(x) = log and føzage is an identity function, i.e., f(x)) x, then Structural feature generator Fo can generate the exactly same structural feature the features used in Adamic Adar method.
Based on the generated structural features of each node, the next process calculate the similarity score that considers only structural features of overlapped neighbors between given nodes. Note that conventional GNNs cannot compute this score due to two reasons: the normalized adjacency matrix and the lower dimension of hidden representations than the number of nodes (i.e., d < N). The normalized adjacency matrix hinders GNNs counting number of neighborhoods and the low dimension makes features of each neighborhoods indistinguishable after aggregation, which cannot detect the neighborhoods overlap. We propose the neighborhood overlap-aware aggregation scheme to calculate neighborhood overlap-aware score. First, maintain the respective features of each node after aggregation, construct diagonal matrix X sstruct vector x struct E R x1
R N.N
xatruct diag(("") (xrtuet.).
Then, to consider the number of overlapped neighbors, aggregate features of multiplying an unnormalized adjacency matrix A as
neighborhoods by
AXetract
Now, each i-th row vector of Z, 2,. involves all the features of node i's neighboring nodes individually. we compute the inner product of two row vectors in Z, then we can compute the scores with the only overlapped neighborhoods, which equals the sum of square of structural feature values of overlapped neighborhoods, i.e., x žj EKEN(ONNG) (Igtratt)?
Furthermore, to consider multi-hop overlapped neighhors, we extend (8) multi-hop settings as follows:
L Σ
A' xttruct
7 = go
where 3 denotes hyper-parameter controlling how much weight is given close neighbors versus distant neighbors and go is a MLP which controls the scale of representations Z. Since node repre- sentations Z are based on only structural information, compute feature-based node representations H. R. Nxd' using the conventional feaeere-based GNNs as
H = GNN(X, AGNN; W),
(10)
where X E R NxF denotes the raw feature matrix, ÂGNN denotes normalized adjacency matrix, and W the parameter for GNNs. Then given link (i.j), Neo-GNNs calculate both similarity scores from each representation matrix Z and H and compute the convex combination of two scores by a trainable parameter as follows:
Úi a a( 2,) + (1 - a)) a(s(h,,hy)))
(11)
Based 12), jointly train our proposed model and individual models using three standard (binary) cross-entropy losses
C Σ (A we) d2 (2))) + (ACCC(((() + (ND)D
(12)
where BCE(.,) denotes binary cross entropy loss and x are the weights.
5

---

Table 1: Statistics and evaluation metrics of OGB link prediction datasets.
Dataset
#Nodes
#Edges
Avg. node deg.
Density
Split ratio
Metric
OGB-PPA
576,289
30,326,273
73.7
0.018%
70/20/10
@itx@ 100
OGB- COLLAB
235,868
1,285,465
8.2
0.0046%
92/4/4
55
OGB-DDI
4,267
1,334,889
500.5
14.67%
80/10/10
Hits@
2,927,963
30,561,187
20.7
0.000366
98/1/1
MRR
Computational Complexity. Our proposed model uses the N N matrix X Xstruct for neigb- horhood overlap detection, which generally takes ( Elr,) computational time to compute node representations in ( where (ε] r. denotes a number of edges connected up to L-hop. To solve this high complexity issue, we represent matrices X sstruct and Z as the sparse matrix form and the computational time becomes just (((E])) Also, as we can pre-compute the set of adjacency matrices {1 in (9). thus there is no additional cost to calculate the powers of the adjacency matrix during training and inference.
4 Experiments
In this section, we evaluate the benefits of our method against toate--o-thh-aar models on link prediction benchmarks. Then we analyze the contribution of each component in Neo-GNNs and show how Neo-GNNs can actually generalize and learn neighborhood overlap-based basedd heuristic methods.
4.1 Experiment Settings
Datasets. We evaluate the effectiveness of our Neo-GNNs for link prediction on Open Graph Benchmark datasets [4] (OGB) : OGB-PPA, OGB-Collab, OGB-DDI, OGB-Citation2. Note that
OGB-Collab contains multiple edges. Detailed statistics of each dataset are summarized in Table
Evaluation. The evaluation for link prediction is based on the ranking performance of positive test edges over negative test edges. Specifically, in OGB-PPA OGB-Collar ranks positive test edges against randolly-sampled negative edges, and computes the ratio of positive test edges that are ranked at K-th place or above (Hits @ K). In (GB-Citationn, the evaluation metric Mean Reciprocal Rank (MRR), where the reciprocal rank of the true link among the negative candidates is calculated for each source node, and then the average is taken over all source nodes.
OGB-DDI, each model
Baselines. To demonstrate the effectiveness of our Neo-GNNs in link prediction, we compare Neo-GNNs with three heuristic link prediction methods, three ombedding-basse methods, and five GNN-based models. For heuristic methods, we used three well-known neighborhood-overle based heuristic methods, Common Neighbors, Adamic Adar (30), and Resource Allocation [31]. Without learning process, they predict links by utilizing each designed structural information regarding overlapped neighborhoods. For embedding-
methods, we used Matrix Factorization, Node2 Vec 42 and Multi-Layer Perceptron (MLP). Furthermore, we compare our method to GNNN-baee models, GCN [T]], GraphSAGE 26). JK-Net [43] GAT [12], and SEAL [25. GCN, GraphSAGE, JK-Net, and GAT compute representations for each node and predict target links by measuring the similarity score between the source and target node of the target links. SEAL extracts enclosing
subgraphs around target links and predict target links based on representations of the enclosing subgraphs as graph classification.
Implementation Details. We reimplemented neighborhood wverlap-based heuristic method.i.c.. Common neighbors. Adamic Adar, and Resource allocation from the referenced papers by using PyTorch. For Node2Vec, GCN, GraphSAGE, JK-Net, and GAT, we used the implementation in PyTorch Geometric [4]] and the implementation in the official github repository for SEAL. We set the number of layers 3 and latent dimensionality to 256 for all GNN-based models. To train our method, we used GCN as feature- based GNN based model and all MLP models in our Neo-GNNs consist of fully connected layers. We jointly trained reature-based GNNs and Neo-GNNs. Since GNN model requires more epochs for convergence than that of Neo-GNNs OGB-PPA, and OGB-DDI, we adopted pre-trained GCN handle this issue. In issue, we fix the feaa.e as the identity function. For fair comparison, reported performances of
due to memory

---

Table Link prediction performances (%) of our Beo-GNNs and baselines on Open Graph Bench- mark (OGB) datasets. Each number is the average performance for 10 random initialization of the experiments. OOM denotes "out of memory'. Bold indicates the second best performance and
underline indicates the best performance.
Method
OGB-PPA PPA
OGB-COLLAB
OGB-DDI
OGB-CITATION
Common Neighbors
27.65 + 0.00
50.06 0.00
17.73 + 0.00
76.20 + 0.00
Adamic Adar
32.45 = 0.00
53.00 = 0.00
18.61 0.00
76.12 + 0.00
Resource Allocation
49.33 + 0.00
52.89 + 0.00
6.23 + 0.00
76.20 + 0.00
Matrix Factorization
27.83 + 2.02
38.74 + 0.30
17.92 + 3.57
53.08 + 4.19
Vode2Vec
17.24 = 0.76
41.36 = 0.69
21.95 + 1.58
53.47 + 0.12
MLP
0.47 + 0.05
19.98 + 0.96
N/A
28.99 + 0.16
GCN
16.98 = 1.33
47.01 = 0.79
44.60 + 8.87
84.79 + 0.24
GraphSAGE
13.93 = 2.38
48.60 0.46
48.01 9.02
82.64 + 0.01
JK-Net
11.40 + 2.04
48.84 0.83
57.98 6.88
OOM
GAT
0OM
44.89 = 1.23
29.51 6.40
00M
SEAL
18.15
54.37 + 0.02
26.25 + 6.00
86.32 + 0.52
Neo-GNN
49.13 = 0.60
57.52 = 0.37
63.57 3.52
87.26 + 0.84
all baselines and our Neo- Roo- the mean and the standard deviation of performances from 10 independent runs, where each seed is from 0 to 9. The experiments are conducted on a RTX 3090 (24GB) and Quadro RTX (48GB).
4.2 Results on Link Prediction
Table 2 shows link prediction results of the baselines and Neo-GNNs on Open Graph Benchmark (OGB) datasets. We use GCN to adaptively combine with Neo-GNNs across all datasets except OGB- Citation2. In NGB-Citation2. since GCN requires 46 GB memory to train, we trained our Neo-GNNs without GCN. As shown in Table 2 we can observe that NNo- consistently achieve of the-arts performance across all datasets. Especially, Neo-GNNG show significant improvements on OGB-Collab and OGB-DDI, where the improvements of Neo-GNNs over the best baseline are 5.4% and 9.6%, respectively. Furthermore, note that Neo- GNNs achieved state-of-the-art performance in DGB-Citation without GCN, that is, by using only graph structures without input node features. Interestingly, conventional feature-based GNNs show poor performance with a huge gap than that of neighborhood overlap- heuristic methods OGB-PPA and OGB-Colla This implies that feature-based GNNs have a difficulty in directly utilizing structural information e.g., degree and overlapped neighbors, for link prediction. According to this implication, Neo-GNNs and SEAL are able to learn structural information, thus these methods accomplish better performance than conventional GNNs do. Moreover, Neo-GNNs and SEAL even show good performance compared to the heuristic methods in all datasets as they can capture structural information that the heuristic methods utilize. Although SEAL shows good performance compared heuristic methods, SEAL shows poor performance than feature-based GNNs in OGB-DDI. One possible interpretation is that SEAL cannot adaptively utilize the input node features and structural features according each data. Instead, Nco-GNNs adaptively combine Neo-GNNs and GCN for each dataset using the learnable parameter a, which shows even higher performance than each performance of Neo-GNNs and GCN. We further analyze the effectiveness of a in
Neo-GNNs
4.3 Ablation Studies
We present ablation experiments to identify the benefits of different components of Neo-GNNs. First, we evaluate our Neo-GNNs without GCN and examine the effectiveness of the parameter that adaptively combine scores from Neo-GNNs and GCN. Then we study the effects of considering multi- hop overlapped neighborhoods. Specifically, we investigate the effectiveness of two hyper-parameters, the decaying factor B and the maximum hop L, related to multi-hop overlapped neighborhoods.
7

---

Table 3: Ablation study analyzing the significance of Neo- Meo-GNNs on the OGB-PPA, OGB-Collab, OGB-DDI, and DGB-Citation2 datasets for link prediction. a denotes the attention weight of Neo-GNNs' scores.
Neo-GNN (w/ GCN)
Neo-GNN (w/o GCN)
Dataset
a
GCN
PPA
0.98 + 0.003
49.13 + 0.60
48.63 = 0.88
16.98 = 1.33
COLLAB
0.57 + 0.130
57.52 + 0.37
55.70 = 0.24
47.01 = 0.79
DDI
0.48 + 0.015
63.57 + 3.52
17.38 + 4.05
44.60 8.87
CITATION2
N/A
0OM
87.26 + 0.84
84.79 0.24
Figure 2: Link prediction results on the OGB-Collab dataset by varying the maximum hop L (left) and the decaying factor (right).
60
Mype
Test Hits@
Test Hits@50
40
40
30
B-1.0
p-0.1
20
L=2
8-0.01
6-0.001
10
10
20
30
40
50 10
0
20
40
60
60
100
Epochs
Epochs
(a) Maximum hop
(b) Decaying factor 3
Neo-GNNs without GCN. To measure the effectiveness of Neo- Neo-GNNs itself, we perform an ablation study on four datasets, as shown in Table We can see that Nco-GNNs (w/o GCN) still show the state-of-the-art performances compared to baselines except OGB-DDI, Note that Neo-GNNs (w/o GCN) only use graph structures and outperform other GNNs whereas other GNNs use both input features and graph structures. This shows that utilizing key structrual information about overlapped neighbors is crucial for link prediction.
Effectiveness of the parameter a. To consider both structural information and input features, our proposed model predict similarity scores from the convex combination of two scores from Neo-GNNs and GCN by the trainable parameter a. As shown in Table a varies for each dataset, which indicates that a properly adjusts the weight of structural information and features for each dataset. With the combining process, Neo-GNNs (w/ GCN) consistently show better performance than performances of individual model, i.e., Neo-GNN (w/o GCN) and GCN. Especially, in OGB-DDI, Neo-GNN (w/o GCN) and GCN show less than 50, but the combined model Neo-GNN (w/ GCN) shows 42% and 80% improved performance compared to each model.
Effectiveness of multi-hop overlapped neighborhoods. We study the effectiveness of multi-hop overlapped neighborhoods by investigating effects of two hyper-parameters. L and B3, on OGB-Collab dataset. First, shown in Figure if Neo-GNNs only consider 1-hop ovelapped neighbhors, i.e.,
L = 1. Neo-GNNs converge faster than other cases considering multi-hop overlapped neighbors. However, the best performance is lower than the others, which shows that multi-hop overlapped neighborhoods enhance the performance of Neo-GNNs for link prediction. Second, 3 controls how much reduce the effects of neighborhoods when the distance increases. As shown in Figure as decreases, Neo-GNNs converge slowly but eventually show similar performance. This means that if multi-hop overlapped neighbors are informative, then Neo-GNNs achieve good performance robustly to the value of B.
4.4 Analysis on learning neighborhood overlap-based heuristic methods
As we discussed Sec 3.3 our Neo-GNNs generalize several neighborhood overlap-based heuristic methods, (e.g., Common Neighbors, Adamie Adar, and Resource Allocation). Further, in this section,

---

we show that Neo-GNNs (w/o GCN) directly learn each neighbhorhood overlap-based heuristic method and implicitly learn the best one among three heuristic methods on OGB-PPA dataset. We first trained Neo-GNNs to fit the scores from each heuristic method on the train set of OGB-PPA. Then we measure the Spearman correlations by using ranks of test edges from each model. We analyze rank correlations between Neo-GNNs and three heuristic methods based on 50000 sampled test edges in Figure 3 As shown in Figure 3 Neo-GNNs show a strong correlation with other heuristic methods. That is, Neo-GNNs can learn each heuristic method. Next, to show that Neo-GNNs learn the most desirable heuristic method depending on datasets, we compute Spearman correlations between ranks from trained Neo-GNNs on OGB-PPA dataset and the heuristic methods. As result, correlation scores between Neo-GNNs and Resource Allocation, Adamic Adar, and Common Neighbors are 0.9627, 0.9277, and 0.8982, respectively. We can see that correlation scores proportional to performances of each heuristic method (49.33, 32.45, and 27.65), which learn the best heuristic method.
Ranks of Resource Allocation
3M
Ranks of Common Neighbors
Ranks of Adamic Adar
2.5M
2.5M
2.5M
2M
2M
1.5M
1.5M
1M
1M
0.5M5M
IM
1.3M
2M
2.3M
3M
0.
0.5
IM
1.5M
2M 2.5M
3M
0.585M
1M
1.5M
2M
2.5M
3M
Ranks of Neo-GNNs
Ranks of Neo-GNNs
Ranks of Neo-GNNs
(a) Resource Allocation (0.9913)
(b) Adamic Adar (0.9969)
(c) Common Neighbors (1.0)
Ranks of Resource Allocation
3M
Ranks of Common Nelghbors
Ranks of Adamic Adar
2.5M
2.5M
2M
2M
1.5M
1.5M
1.5M
1M
0.5M
0.50L
0.58 5M
2.5M Ranks of Neo-GNNs
1M
1.5M 2M
3M
IM
1.58
2M
2.5M
3M
1M
1.5M
2M
2.5M 3M
Ranks of Neo-GNNs
Ranks of Neo-GNNs
(d) Resource Allocation (0.9627)
(c) Adamic Adar (0.9277)
(f) Common Neighbors (0.8982)
Figure 3: Comparison of rank correlation between our Neo-GNNs and three neighborhood overlap- based heuristic methods on OGB-PPA. We evaluate a rank correlation on positive test edges after ranking the entire test edge prediction scores. We visualize rank correlation using randomly sampled 50,000 positive test edges. The 3(a) ((b) 3(c) show rank correlation when Neo-GNNs (w/o GCN) fit to scores of each heuristic method. ((d) 3(e) (3)) ((F)ppeeenn the rank correlation between Neo-GNNs (w/o GCN) and each heuristic method upon OGB-PPA. The number in parentheses indicates Spearman Correlation coefficient.
5 Conclusion
We introduced Neighborhood Overlap- bbaee Graph Neural Networks (Neo-GNNs) that learn and utilize structural information, which is key element in link prediction. Neo-GNNs learn useful struc- tural features from an adjacency matrix and estimate overlapped neighborhoods for link prediction. We also adaptively combine Neo-GNNs and feature-based GNNs to consider both structural features and input node features. Furthermore, our Neo-GNNs generalize several neighhorhood overlap-based heuristic methods and handle overlapped multi-hop neighhorhoods. Extensive experiments on four Open Graph Benchmark (OGB) datasets demonstrate that Neo-GNNs consistently acheive state-

---

of-the-art performance on four OGB datasets in link prediction. In future work, we plan to further develop Neo-GNNs to generalize more link prediction-baus baseed heuristic methods and improve the scalability with efficient sparse matrix computation.
6
Acknowledgement
This work was supported by the following funding sources: National Research Foundation of Korea (NRF-2020R IA2C3010638, 2021-2020-00018133 supervised by the ITTP; Samsung Research Funding & Incubation Center of Samsung Electronics under Project Number SRFC-ITI701-51.
ICT Creative Consilience program (ITP..
References
[1] Jiezhong Qiu, Jian Tang, Hao Ma, Yuxiao Dong, Kuansan Wang, and Jie Tang. Deepinf: Social influence prediction with deep learning. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD), pages 21 11-2-2199, 2018
[2] Lei Tang and Huan Liu. Graph mining applications social network analysis. In Managing and Mining Graph Data, pages 487-513, Springer, 2010.
[3] Hao Wang, Tong Xu, Qi Liu, Defu Lian, Enhong Chen, Dongfang Du, Han Wu, and Wen Su. Mene: An end-to-end framework for learning multiple conditional network representations of social network. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery Data Mining (KDD), pages 0064-1072, 2019.
[4] Nicola De Cao and Thomas Kipf. Molgan: An implicit generative model for small molecular graphs. arXiv preprint arXiv: 1973, 2018.
[5] David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alan Aspuru-Guzik, and Ryan P Adams. Convolutional networks on graphs for learning molecular fingerprints. Advances in Neural Information Processing Systems (NeurIPS) 28, pages 1224-2232 Curran Associates, Inc., 2015.
[6] Alex Fout, Jonathon Byrd, Basir Shariat, and Asa Ben-Hur. Protein interface prediction using graph convolutional networks. In Advances in Neural Information Processing Systems (NeurIPS) 30, pages 6530-6539. Curran Associates, Inc., 2017.
[7] Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning, Proceedings Machine Learning Research, pages 1263-
1272, 2017.
[8] Helisa Dhamo, Azade Farshad, Iro Laina, Nassir Navab, Gregory D. Hager, Federico Tombari, and Christian Rupprecht. Semantic image manipulation using scene graphs. In The IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 5213-5222. 2020.
[9] Charles R Qi, Hao Su, Kaichun Mo, and Leonidas Guibas. Pointnet: Deep learning on point sets for 3d classification and segmentation. In Proceedings the IEEE conference on computer vision and pattern recognition, pages 652-660, 2017.
[10] Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay Sarma, Michael M Bronstein, and Justin M Solomon. Dynamic graph enn for learning on point clouds. Acm Transactions On Graphics (tog), 38(5):1-12, 2019.
[11] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In Internationall Conference on Learning Representations, 2017.
[12] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 1700 10903, 2017.
[13] Johannes Klicpera, Stefan WeiB enberger, and Stephan Günnemann. Diffusion improves graph learning. In Advances in Neural Information Processing Systems (NeurIPS) 32, pages 33333-13355. Curran Associates, Inc., 2019.
10

---

[14] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In Proceedings of the 37th International Conference on Machine Learning (ICML), pages 1725-1735, 2020.
[15] Cheng Zheng, Bo Zong, Wei Cheng, Dongjin Song. Jingchao Ni, Wenchao Yu, Haifeng Chen, and Wei Wang. Robust graph representation learning via neural sparsification. In Proceedings of the 37th International Conference Machine Learning (ICML), pages 1 11458-11444 1148, 2020.
[16] Muhan Zhang. Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[17] Rex Ying, Jiaxuan You, Christopher Morris, Xiang Ren, William L Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling, arXiv preprint 1806: 08804, 2018.
[18] Junhyun Lee, Inyeop Lec, and Jaewoo Kang. Self-attention graph pooling. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning. PMLR, 2019.
[19] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint orXiv://80..00
2018.
[20] Seongmin Ok. A graph similarity for deep learning. Advances in Neural Information Processing Systems (NeurIPS) 33, pages 1-12. Curran Associates, Inc., 2020.
[21] Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. In International Conference on Machine Learning, pages 2323-2332 PMLR, 2018
[22] Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Hierarchical generation of molecular graphs using structural motifs. In Proceedings of the 37th International Conference on Machine Learning (ICML), pages 4839-4844 2020.
[23] Jenny Liu, Aviral Kumar, Jimmy Ba, Jamie Kiros, and Kevin Swersky. Graph normalizing flows. In Advances in Neural Information Processing Systems (NeurIPS) 32, pages 13556-13566. Curran Associates, Inc., 2019.
[24] Jiaxuan You, Bowen Liu, Rex Ying, Vijay Pande, and Jure Leskovec. Graph convolutional policy network for goal-directed molecular graph generation. In Advances in Neural Information Processing Systems (NeurIPS) 31, pages 6412-6422. Curran Associates, Inc., 2018.
[25] Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Advances in Neural Information Processing Systems, pages 5165-5175. 2018.
[26) William Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus. S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30, pages 1024-1034. Curran Associates, Inc., 2017.
[27] Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. International Conference on Learning Representations, 2018
[28] Jiaxuan You, Rex Ying, and Jure Leskovec. Position-avee aware graph neural networks. In Interna- tional Conference on Machine Leariing pages 7134-7143. PMLR, 2019.
[29] Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. science, 286(5439):599-512 1999.
[30] Lada A Adamic and Eytan Adar. Friends and neighbors on the web. Social networks, 25(3):211- 230, 2003.
[31] Tao Zhou, Linyua Lü, and Yi-Cheng Zhang. Predicting missing links via local information. The European Physical Journal B, (1(())6233663))) 2009.

---

[32] Leo Katz. A new status index derived from sociometric analysis. Psychometrika, 18(1):39-4) 1953.
[33] Sergey Brin and Lawrence Page. Reprint of: The anatomy of a large-scale hypertextual web search engine. Computer nefworks, 56(1 8):3825-3832 2012.
[34] Glen Jeh and Jennifer Widom. Simrank: measure of structural-context similarity. In Proceed- ings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 538-543, 2002.
[35] Yehuda Koren, Robert Bell, and Chris Volinsky, Matrix factorization techniques for recom- mender systems. Computer, 42(8):30-37, 2009.
[36] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 701-710, 2014.
[37] Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. Network embedding as matrix factorization: Unifying deepwalk, line, ptc, and node2vec. In Proceedings of the eleventh ACM international conference web search and data mining, pages 159-467, 2018.
[38] Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation of word representations in vector space. arXiv preprint arXiv: 1eXivv1301..0 1301.3711 2013.
[39] Elena Zheleva and Lise Getoor. To join or not to join: The illusion of privacy in social networks with mixed public and private user profiles. In Proceedings of the 18th International Conference on World Wide Web, WWW '09, page 531-540, 2009.
[40] Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXiv:1611.07300 2016.
[41] Weihua Hu, Matthias Fey, Marinka Zitiik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs. arXiv preprint arXiv:2005.00687 2020.
[42] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 855-864, 2016.
[43] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference on Machine Learning, pages 5453-5462. PMLR, 2018.
[44] Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
12


Reviews:
[{"review_id": "yYeA1VPFpvW", "reviewer": "Reviewer_9RGy", "summary": "This work added a model into GNN to improve link prediction. The connection is a weighted combination of the model's output and GNN's output in the scoring function (scoring a predicted link).  The paper claims that this model computes the number of overlapped neighbors. Experiments show the combination improves the performance.", "questions": "", "limitations": "", "rating": 5, "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": "Originality: It is an incremental approach with lots of things that are not clearly explained.\n\n- Eq.(8) aggregates features of neighbors but why it can \"count the number of overlapped neighbors\"?\n- What is \"overlapped neighbors\"?  It seems to be a pair-wise concept that measures the relationship between two nodes (overlapped neighbors of the two nodes). However, I am not seeing any pair-wise measurement in the equations.\n- Why choose the number of overlapped neighbors, when there has been multiple kinds of heuristics-based measurements (as discussed in Section 3.2)? \n- There should be more essential methods to make a GNN model be aware of overlapped neighbors/subgraph.  Creating two models and connecting at the last layer is probably the most trivial idea. I suggest the authors to incorporate the overlapping subgraph into the convolutional operation in Eq.(10).\n- Even though the models could be connected and jointly trained, it is not clear whether the model parameters are shared. Is \\Theta in Eq.(9) used in Eq.(10)?\n\nQuality: I have serious concern about the motivation of the work and thus feel the quality of the proposed method and experimental results is questionable.\n\nClarity: The incremental idea is not hard to follow.\n\nSignificance: Very little impact. There was not theoretical analysis that proved that the structural information about overlapping neighbors would be hardly learned by the existing GNN.\n\n*** The authors have clarified all of the points with either new results or explanations in the multi-rounds discussion. No matter the work is accepted or further reviewed, the authors are highly encouraged to add the new results and explanations into the paper. ***\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not included or discussed in the paper.", "review_text": "", "extra_scores": {"ethical_concerns": "I don't have any concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1 hour"}, "extra_text": {}}, {"review_id": "rrq60isp-qn", "reviewer": "Reviewer_yBWB", "summary": "The paper proposes to use simple functions learned from the adjacency matrix of a graph to boost the performance of GNNs. This overcomes the problem of using traditional heuristics which are effective but must be computed manually. The proposed approach is simple and the experiments over the quite challenging datasets of the OGB show that it is rather effective. I have some concerns regarding the latter which is why my current score is only slightly below the threshold, but maybe the authors can resolve those.", "questions": "", "limitations": "", "rating": 7, "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": "(+)\n\n- The proposed approach is simple but effective which is quite nice. It is so simple that I wonder if there is existing work which the authors and I are missing, but maybe the other reviewers can confirm that this is not the case.\n\n- Generally, the paper is well-written and I have few to criticise. The approach is described in detail, related work is covered, and the experiments are overall thorough. In particular, the latter show that their learned functions correlate with well-known traditional heuristics.\n\n(-)\n\n- To me, it is not clear why the authors use a GNN for learning from the features. In particular, they argument a lot that GNNs fail to learn the structure (which is a strong claim btw), so why use a GNN at all and not a simple MLP?\n\n- The SAGE number reported in the table is worse than the one reported in the OGB paper. Did you try with the parameters they use there? There is further GraphSAGE+anchor distance on the leaderboard, whose ogbl-ddi score (0.8239) is considerably better than the one for NeoGNN. And it is quite related given that it also considers a structural feature.\n\n- 260: \"Neo-GNNs (w/o GCN) still show the state-of-the-art performances compared to baselines except OGB-DDI. Note that Neo-GNNs (w/o GCN) only use graph structures and outperform other GNNs whereas other GNNs use both input features and graph structures..\" -- To the best of my knowledge, it is the DDI dataset that does not contain node features, but uses randomly initialized ones. In this regard, I wonder about the conclusion of the authors. To me it seems that the other GNNs obviously manage to use the structure to make something out of the random initial features.\n\n- I do not think it is fair to fix the numbers of GNN layers to 3. Especially over these OGB datasets, my personal experience shows that they work often better with several more layers. And at least JK-Net should be able to achieve good scores (while others might suffer from over-smoothing). Did you get similar scores with more layers?\n\n-------------------------------\nQuestions & Smaller Comments\n-------------------------------\n\n- Figure 2: Did you check if the trends are similar on the other datasets?\n- Which L is used in Figure 2b?\n- 107: s does not necessarily have to be a similarity function \n- 166: Do you really count the number of neighbours here?\n- 169ff: Is this just additional information or important in some regard. To me, the remark is somehow confusing.\n- 199: You mean multiple edge types? (edges of course)\n- I think the LINK model from Zheleva and Getoor (\"To join or not to join: The illusion of privacy in social networks with mixed public and private user profiles\", 2009) would be worth mentioning as related work.\n\n-------------------------------\nedit: I adapted the score based on the responses in the rebuttal", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "Sjd8MXu4Zse", "reviewer": "Reviewer_cNTF", "summary": "This paper proposes a neighborhood-overlap-aware GNN for link prediction. Traditional GNNs cannot detect the overlap of two nodes when combining the two embeddings as a link representation, which is crucial for link prediction since many successful heuristics such as common neighbor relies on such overlap measure. SEAL leveraging a distance-based node labeling solves this problem (detecting overlap and correlation between two nodes), yet requires extracting a subgraph for each target link thus is computationally more expensive than traditional GNNs. This paper tackles the problem by explicitly combining a learnable overlap measurement function (to simulate overlap-based heuristics) and a traditional GNN (to learn node features), and achieves highly competitive performance with SEAL and outperforms heuristic methods.", "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": "Originality: The proposed method can learn node overlapping, which is not feasible in traditional GNNs. It also avoids SEAL's subgraph extraction step, thus is more efficient. The combination of a learnable neighborhood overlap function and a GNN is novel, and works well on the link prediction problem over several OGB datasets.\n\nQuality: The paper is technically sound. The techniques are simple and effective.\n\nClarity: The paper is generally well written. However, there are several mistakes and inaccuracies in the statements. 1) \"SEAL requires inefficient computational cost to manually measure the relative distance for each target node pair and still shows limited performance compared to heuristic methods\". This is not true. SEAL outperforms almost all heuristics in its original paper, and the bottleneck of SEAL's computation is applying a GNN independently to each extracted subgraph. The distance calculation is negligible. 2) \"However, there is a limitation of the expressive power that is upper-bounded by the 1-Weisfeiler-Lehman (1-WL) graph isomorphism test. That is, some subgraphs are indistinguishable if they are symmetric or isomorphic\" This is wrong. We **want** isomorphic subgraphs to be indistinguishable by GNNs. However, some non-isomorphic graphs indistinguishable by 1-WL are also indistinguishable by GNNs lead to the expressivity bottleneck. 3) \"Random walk-based embedding methods such as Deepwalk [37], LINE [38], and node2vec [39] ...\" LINE is not based on random walk, but first and second-order neighborhood. 4) \"Note that conventional GNNs cannot compute this score due to two reasons: the normalized adjacency matrix and the low dimension of hidden representations.\" This is not true. Conventional GNNs cannot compute the overlap because they independently learn two nodes' neighborhood without modeling their correlations. See [1]. You may perform an experiment replacing the normalized adjacency matrix with unnormalized one in conventional GNNs and increase the hidden representations to verify whether the statement is correct. 5) Eq (8) is not an \"aggregation\" of neighbor features (although it looks like). It is simply lifting the node features to the corresponding edges. I would not call this an aggregation.\n\nSignificance: This paper illustrates the importance of detecting overlap in link prediction, which is significant.\n\n[1] Zhang, M., Li, P., Xia, Y., Wang, K., & Jin, L. (2020). Revisiting graph neural networks for link prediction. arXiv preprint arXiv:2010.16103.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "One potential concern is that overlap-based heuristics are only one specific type of successful heuristics for link prediction. There are other types of heuristics such as PPR, preferential attachment, etc, which are not based on overlaps. The proposed method generally cannot learn such heuristics in my opinion. I suggest doing another set of experiments on the traditional link prediction datasets used in the SEAL paper to demonstrate the limitation of the proposed method for learning general heuristics. It may be the case that the OGB datasets happen to be very suitable for overlap-based heuristics. I suggest pointing out when the proposed method works well and when it does not.\n\nI give a weak accept conditioned that the authors can address the \"Clarity\" in the main review and discuss the limitation of the proposed method. I will increase my score accordingly if the authors well address these concerns.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a novel GNN architecture for link prediction based on neighbourhood overlap. 
The authors provided a detailed rebuttal including additional experimental results requested by the reviewers. There has been an extensive follow-up discussion. While doubts remain about clarity of the presentation, the AC believe this can be improved in the final version according to the discussion with the reviewers and their recommendations. We recommend accepting the paper.  
Decision: Accept (Poster)