Neo-GNNs: Neighborhood Overlap-aware Graph Neural Networks for Link Prediction
Year: 2022

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.

heading: 1 Introduction
text: Graph-structured data is ubiquitous in a wide range of domains ranging from social network analysis [1, 2, 3] to biology [4, 5, 6, 7] and computer vision [8, 9, 10]. 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 or 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-based methods, and achieved state-of-the-art performance on various tasks, such as node classification [11, 12, 13, 14, 15], graph classification [16, 17, 18, 19, 20], and graph generation [21, 22, 23, 24].
However, in link prediction, traditional heuristic methods still show competitive performance compared to GNNs, which often even outperform GNNs. This is because structural information, (e.g., overlapped neighborhoods, degrees, and shortest path), is crucial for link prediction whereas GNNs heavily rely on 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, we propose Neighborhood Overlap-aware Graph Neural Networks (NeoGNNs) 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-GNNs measure the existence of links by considering the structural features of overlapped neighbhorhoods via neighbhorhood
∗corresponding author
35th Conference on Neural Information Processing Systems (NeurIPS 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-art 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 (Neo-GNNs) 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. (iii) Our extensive experiments on Open Graph Benchmark datasets (OGB) demonstrate that Neo-GNNs consistently achieve state-of-the-art performance in link prediction.

heading: 2 Related Works
text: 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 [11], GraphSAGE [26], 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 a limitation of the expressive power that is upper-bounded by the 1-Weisfeiler-Lehman (1-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 [11, 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. 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 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 are extremely effective for link prediction. However, they require manually designed structural information for each heuristic method. To overcome this limitation, embedding-based methods have been proposed. They learn node embeddings based on 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 walk-based 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 to 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 in 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.

heading: 3 Methods
text: The goal of our framework, Neighborhood Overlap-aware Graph Neural Networks (Neo-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 overlap-based heuristic methods, and then introduce Neo-GNNs.

heading: 3.1 Preliminaries
text: Notations. Consider an undirected graph G = (V, E) with N nodes, where V = {v1, v2, . . . , vN} represents a set of nodes and E = {eij | vi, vj ∈ V} represents a set of edges where the nodes vi, vj ∈ V are connected. The adjacency matrix A ∈ RN×N is defined by Aij = 1 if eij ∈ E and 0 otherwise. The degree matrix D ∈ RN×N is a diagonal matrix defined by Dii = ∑ j Aij . The nodes of G have their own feature vectors xi ∈ RF (i ∈ {1, 2, . . . , N}), with X ∈ RN×F denoting the collection of such vectors in a matrix form.
Graph Neural Networks for Link Prediction. Given a graph G and a feature matrix X , graph neural networks learn meaningful node representations by an iterative aggregation of transformed representations of neighbor nodes in each l-th GNN layer as follows:
H(l+1) = σ ( ÃGNNH (l)W (l) ) , (1)
where ÃGNN ∈ RN×N is the adjacency matrix normalized in different ways depending on each GNN architecture (e.g., D̃− 1 2 (A+ I)D̃− 1 2 ), W (l) ∈ Rd
(l)×d(l+1) is a trainable weight matrix, and H(0) is the node feature matrix X ∈ RN×F . After stacking L GNN layers, node representations H(L) are then used to predict existence of each link (i, j):
ŷij = σ(s(h (L) i , h (L) j )), (2)
where s(·, ·) is a function, e.g., inner product or MLP, and h(L)i is the representation of the node i from H(L).

heading: 3.2 Neighborhood Overlap-based Heuristic Methods
text: Heuristic methods for link prediction measure the score of given node pairs based on 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 to 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 v as
SCN (u, v) = |N (u) ∩N (v)| = ∑
k∈N (u)∩N (v)
1. (3)
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) [31] measures the score of link (u, v) by counting the inverse degrees of common neighbors between node u and v as
SRA(u, v) = ∑
k∈N (u)∩N (v)
1
dk , (4)
where dk denotes the degree of node k. Adamic-Adar has a relatively decreased penalty for higher degree compared to RA by using the reciprocal logarithm of common neighbors’ degrees between
node u and v as
SAA(u, v) = ∑
k∈N (u)∩N (v)
1
log dk . (5)
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, 1d , 1 log d . 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 of both GNNs and heuristic methods, we propose Neighborhood Overlapaware 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.

heading: 3.3 Neighborhood Overlap-aware Graph Neural Networks
text: 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, 1d , 1 log d . To generalize and learn these structural features, we propose Structural feature generator Fθ which learns to generate structural
features of each node using an only adjacency matrix A ∈ RN×N of the graph as
xstructi = Fθ(Ai) = fθnode ∑ j∈Ni fθedge(Aij)  , (6) where xstructi is a structural feature value of the node i and Fθ is a learnable function comprised of two MLPs, fθnode and fθedge , for nodes and edges, respectively. That is to 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 fθnode is a reciprocal of the logarithm function, i.e., f(x) = 1 log x , and fθedge is an identity function, i.e., f(x) = x, then Structural feature generator Fθ can generate the exactly same structural feature as the features used in Adamic-Adar method.
Based on the generated structural features of each node, the next process is to 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 a 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, to maintain the respective features of each node after aggregation, we construct a diagonal matrix Xstruct ∈ RN×N using the structural feature vector xstruct ∈ RN×1 as Xstruct = diag(xstruct). (7) Then, to consider the number of overlapped neighbors, we aggregate features of neighborhoods by multiplying an unnormalized adjacency matrix A as
Z = AXstruct. (8)
Now, each i-th row vector of Z, zi, involves all the features of node i’s neighboring nodes individually. If 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., zTi zj = ∑ k∈N (i)∩N (j) (x struct k ) 2.
Furthermore, to consider multi-hop overlapped neigbhors, we extend (8) to multi-hop settings as follows:
Z = gΦ ( L∑ l=1 βl−1AlXstruct ) , (9)
where β denotes a hyper-parameter controlling how much weight is given to close neighbors versus distant neighbors and gΦ is a MLP which controls the scale of representations Z. Since node representations Z are based on only structural information, we compute feature-based node representations H ∈ RN×d ′ using the conventional feature-based GNNs as
H = GNN(X, ÃGNN ;W ), (10)
where X ∈ RN×F denotes the raw feature matrix, ÃGNN denotes a normalized adjacency matrix, and W is the parameter for GNNs. Then given a 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:
ŷij = α · σ(zTi zj) + (1− α) · σ(s(hi, hj))), (11)
Based on (12), we jointly train our proposed model and individual models using three standard (binary) cross-entropy losses
L = ∑
(i,j)∈D
( λ1BCE(ŷij , yij) + λ2BCE(σ(z T i zj), yij) + λ3BCE(σ(s(hi, hj)), yij) ) , (12)
where BCE(·, ·) denotes binary cross entropy loss and λi are the weights.
Computational Complexity. Our proposed model uses the N × N matrix Xstruct for neigbhorhood overlap detection, which generally takes O(N |E|L) computational time to compute node representations Z in (9), where |E|L denotes a number of edges connected up to L-hop. To solve this high complexity issue, we represent matrices Xstruct and Z as the sparse matrix form and the computational time becomes just O(|E|L). Also, as we can pre-compute the set of adjacency matrices {Al}Ll=1 in (9), thus there is no additional cost to calculate the powers of the adjacency matrix during training and inference.

heading: 4 Experiments
text: In this section, we evaluate the benefits of our method against state-of-the-art 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 heuristic methods.

heading: 4.1 Experiment Settings
text: Datasets. We evaluate the effectiveness of our Neo-GNNs for link prediction on Open Graph Benchmark datasets [41] (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 1.
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-Collab, OGB-DDI, each model ranks positive test edges against randomly-sampled negative edges, and computes the ratio of positive test edges that are ranked at K-th place or above (Hits@K). In OGB-Citation2, the evaluation metric is 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.
Baselines. To demonstrate the effectiveness of our Neo-GNNs in link prediction, we compare Neo-GNNs with three heuristic link prediction methods, three embedding-based methods, and five GNN-based models. For heuristic methods, we used three well-known neighborhood-overlap 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-based methods, we used Matrix Factorization, Node2Vec [42], and Multi-Layer Perceptron (MLP). Furthermore, we compare our method to GNN-based models, GCN [11], 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 overlap-based heuristic method,i.e., 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 [44] and the implementation in the official github repository for SEAL. We set the number of layers to 3 and latent dimensionality to 256 for all GNN-based models. To train our method, we used GCN as a feature-based GNN based model and all MLP models in our Neo-GNNs consist of 2 fully connected layers. We jointly trained feature-based GNNs and Neo-GNNs. Since a GNN model requires more epochs for convergence than that of Neo-GNNs on OGB-PPA, and OGB-DDI, we adopted pre-trained GCN to handle this issue. In OGB-Citation2, due to memory issue, we fix the fθedge as the identity function. For fair comparison, we reported performances of
all baselines and our Neo-GNNs as 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 a Quadro RTX (48GB).

heading: 4.2 Results on Link Prediction
text: 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 OGBCitation2. In OGB-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 Neo-GNNs consistently achieve state-ofthe-arts performance across all datasets. Especially, Neo-GNNs 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 OGB-Citation2 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-based heuristic methods on OGB-PPA and OGB-Collab. 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 to 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 to each data. Instead, Neo-GNNs adaptively combine Neo-GNNs and GCN for each dataset using the learnable parameter α, which shows even higher performance than each performance of Neo-GNNs and GCN. We further analyze the effectiveness of α in 4.2

heading: 4.3 Ablation Studies
text: 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 multihop overlapped neighborhoods. Specifically, we investigate the effectiveness of two hyper-parameters, the decaying factor β and the maximum hop L, related to multi-hop overlapped neighborhoods.
Neo-GNNs without GCN. To measure the effectiveness of Neo-GNNs itself, we perform an ablation study on four datasets, as shown in Table 3. We can see that 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. This shows that utilizing key structrual information about overlapped neighbors is crucial for link prediction.
Effectiveness of the parameter α. 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 α. As shown in Table 3, α varies for each dataset, which indicates that α 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 β, on OGB-Collab dataset. First, as shown in Figure 2, 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, β controls how much to reduce the effects of neighborhoods when the distance increases. As shown in Figure 2, 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 β.

heading: 4.4 Analysis on learning neighborhood overlap-based heuristic methods
text: As we discussed in Sec 3.3, our Neo-GNNs generalize several neighborhood overlap-based heuristic methods, (e.g., Common Neighbors, Adamic 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 a 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 are proportional to performances of each heuristic method (49.33, 32.45, and 27.65), which learn the best heuristic method.

heading: 5 Conclusion
text: We introduced Neighborhood Overlap-based Graph Neural Networks (Neo-GNNs) that learn and utilize structural information, which is a key element in link prediction. Neo-GNNs learn useful structural 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 neigbhorhood overlap-based heuristic methods and handle overlapped multi-hop neigbhorhoods. 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-based heuristic methods and improve the scalability with efficient sparse matrix computation.

heading: 6 Acknowledgement
text: This work was supported by the following funding sources: National Research Foundation of Korea (NRF-2020R1A2C3010638, NRF-2014M3C9A3063541); ICT Creative Consilience program(IITP2021-2020-0-01819) supervised by the IITP; Samsung Research Funding & Incubation Center of Samsung Electronics under Project Number SRFC-IT1701-51.

Review summaries:
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.

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.

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.