Neural Common Neighbor with Completion for Link Prediction
Authors: Xiyuan Wang
Haotong Yang
Muhan Zhang
Venue: ICLR 2024 poster (2024)
Keywords: Graph Neural Network
Link Prediction
Primary area: learning on graphs and other geometries & topologies
TL;DR: A novel architecture for link prediction with outstanding performance and scalability. It is further enhanced by solving graph incompleteness problem.

Abstract: In this work, we propose a novel link prediction model and further boost it by studying graph incompleteness. First, We introduce MPNN-then-SF, an innovative architecture leveraging structural feature (SF) to guide MPNN's representation pooling, with its implementation, namely Neural Common Neighbor (NCN). NCN exhibits superior expressiveness and scalability compared with existing models, which can be classified into two categories: SF-then-MPNN, augmenting MPNN's input with SF, and SF-and-MPNN, decoupling SF and MPNN. Second, we investigate the impact of graph incompleteness---the phenomenon that some links are unobserved in the input graph---on SF, like the common neighbor. Through dataset visualization, we observe that incompleteness reduces common neighbors and induces distribution shifts, significantly affecting model performance. To address this issue, we propose to use a link prediction model to complete the common neighbor structure. Combining this method with NCN, we propose Neural Common Neighbor with Completion (NCNC). NCN and NCNC outperform recent strong baselines by large margins, and NCNC further surpasses state-of-the-art models in standard link prediction benchmarks.

Published as a conference paper at ICLR 2024
NEURAL COMMON NEIGHBOR WITH COMPLETION FOR LINK PREDICTION
Xiyuan Wang!.
Haotong Yang" 12.3
Muhan Zhang
wangxi gruan@pku.edu edu..ueedd.com edu.cn on
Paot.ongyang@pkuu edu cn
muhan@ edu cn
Institute for Artificial Intelligence, Peking University.
School of Intelligence Science and Technology, Peking University. 3 Key Lab of Machine Perception (MoE)
ABSTRACT
In this work, we propose a novel link prediction model and further boost it by studying graph incompleteness. First, introduce MPNN-then-SF, inno- vative architecture leveraging structural feature (SF) to guide MPNN's repre- sentation pooling, with its implementation, namely Neural Common Neighbor (NCN). NCN exhibits superior expressiveness and scalability compared with ex- isting models, which can be classified into two categories: SF-then-MPNN, aug- menting MPNN's input with SF, and SF-and-MPNN, decoupling SF and MPNN, Second, we investigate the impact of graph incompleteness the phenomenon that some links are unobserved in the input graph-on SF, like the common neigh- bor. Through dataset visualization, we observe that incompleteness reduces com- mon neighbors and induces distribution shifts, significantly affecting model per- formance. To address this issue, we propose to use a link prediction model to complete the common neighbor structure. Combining this method with NCN, we propose Neural Common Neighbor with Completion (NCNC), NCN and NCNC outperform recent strong baselines by large margins, and NCNC further surpasses state-of-ther art models in standard link prediction benchmarks. Our code is avail- able htttts::/ggthhtta com/ wwtp:/raaaPKO/Meeuaaaaaooo http://eeuur...ommoooeo......oo.
INTRODUCTION
Link prediction is a crucial task in graph machine learning, find- ing applications in various domains, such recommender sys-
tems (Zhang & Chen 2020), knowledge graph completion (Zhu
et al., 2021), and drug interaction prediction (Souri et al.] (022).
Graph Neural Networks (GNNs) have gained prominence in link prediction tasks, with Graph Autoencoder (GAE) (Kipf & Welling 2016) being a notable representation. GAE utilizes Message Pass- ing Neural Network (MPNN) (Gimerr et 2017) representations of two individual target nodes to predict link existence. However, Zhang al. (002)) point out limitation GAE: it overlooks pair- wise relations between target nodes. For example, in Figure [ GAE always produces the same prediction for two links (E1, U2)
The failure of MPNN in link prediction task. V2 and v3 have equal MPNN node representations due to symmetry. However, with different pairwise rela- tions, (U1, 222 and (21, v3) should have different repre- sentations.
Figure 1:
and (V,, v3)) despite their differing pairwise relationships, because MPNN generates identical representations for nodes U2, Ut due to graph symmetry. Nevertheless, the two links have different struc- tural features. For example, v and U2 have a common neighbor 14,
while i and vs do have any. Therefore, various methods combine struetural feature (SF) and MPNN for better expressivity and have dominated the link prediction task (Zhang el al. 2021 Yun
al. 2021 Chamberlain et al. 2023
"Correspondence Muhan Zhang.

---

Published as a conference paper at ICLR 2024
However, models combining SF and MPNN still have much room for improvement. They can generally be concluded into two architectures:
MPNNN and SF-and-MPNN, as shown in Figure 2 SEAL (hang & Chen, 2018) adds target-link-seeeffee hand-crafted fea- tures to the node features of the input graphs of MPNN, whose output node representations then pooled to produce link representations. SEAL belongs to the SF-then-MPNN archi- tecture, which leverages SF to augment the input graph of MPNN. Though SF-then-MPNN models achieve provably high expressivity (Zhang al. 2021), they require running MPNN
on different graph for each target link, resulting in significant computational overhead. In contrast, Neo-GNN (Yun et al.) (021)) and
BUDDY (Chamberlain et al.) (202)) decouple (1)
SF
MPNN
Au
the structural feature from MPNN. They di-
rectly incorporate manually created pairwise features with individual node representations produced by MPNN as link representations, ne- cessitating only a single run of MPNN on the original graph. These models fall under the SF-and-MPNN category, where structural fea- tures and MPNN independent. Such meth- ods have limited expressivity. For example. SEAL can capture the representations of com- mon neighbor nodes, while BUDDY can only count the number of common neighbors.
SF
Åsj
(2)
MPNN
MPNN
Ag
Archtectures for combining SF and MPNN. denote the input graph structure. Ex- isting works are (I) SF-then-MPNN (2) SF-and- MPNN architectures. We propose a completely new architecture (3) MPNN-then-SF.
Figure 2:
To solve the drawback of the two architectures above, we propose MIPNN-then-SS architecture, which initially applies MPNN the original graph and then uses structural features to guide the pooling of node representations. This approach offers strong expressivity and scalability: similar to SF-then-MPNN models, MPNN-then-SF can capture the node features of common neighbors, and similar to SF-and-MPNN models, it runs MPNN only once for all target links. We introduce the Neural Common Neighbor (NCN) as an instantiation of the MPNN-then-SH architecture. In experiments, NCN outperforms existing models in both scalability and performance.
Furthermore, since NCN heavily relies common neighbor structure, which is significantly af- fected by graph incompleteness, we also investigate the impact of incompleteness. Graph incom- pleteness is ubiquitous in link prediction tasks because the goal is predict unobserved edges not present in the input graph. We empirically observe that incompleteness reduces the number of com- mon neighbor and leads shift in the distribution of common neighbor between the training and test sets. These phenomena collectively lead to performance degradation. To mitigate this issue, we first employ NCN to complete the common neighbor structure and then apply NCN to the completed graph. In experiments, this method significantly improves the performance of NCN.
In conclusion, our contributions are as follows:
We introduce the Neural Common Neighbor (NCN) for link prediction using the MPNN-then-SF architecture, demonstrating superior performance and scalability compared to existing models.
We analyze the impact of graph incompleteness and propose Neural Common Neighbor with Complction (NCNC), which completes the input common neighbor structure and applies NCN to the completed graph. NCNC outperforms state-ofthhe-ee models.
2 PRELIMINARY
We consider an undirected graph G EV, where V = (1, represents set of n nodes, E C V x V denotes the set of edges, X E R is a node feature matrix whose v-th row X, is the feature of node v, and adjacency matrix A E Ba is symmetric matrix, whose (u, v) element is 1 (u, v) E E and 0 otherwise. The degree of node u is d(u, A) := Σ Aue- nodes connected to u, N(u, A) = {ule E V, 0}. For simplicity
Node u's neighbors of notations, we use Nu)) to denote N(u, A) when is fixed. Common neighbor means nodes connected to both and j: (()
2

---

Published as a conference paper at ICLR 2024
High Order Neighbor. We define A' as a high-order adjacency matrix, where A'ee represents the number of walks of length between nodes u and v in graph A. N(u, A') = fule E V, A' > 0} denotes the set of nodes connected to by a walk of length / in graph A. equivalent to the neighbors in higher-order adjacency. Ni(u, A) denotes the set of nodes whose shortest path distance to u in graph A is 1. Existing works define high-order neighbors generally, the neighborhood of u can be expressed as Ni, (u, A'²), returning all nodes with a shortest path distance of I to in the high-order graph A'2, We use Ni. (u) to denote Nr, (u, A'2) when A is fixed. Given a target link (i.j), their general neighborhood overlap is given by No (i) n N (i), and their neighborhood difference is given by N/. (i) (i)-
either (u,, A') or (u, A). More
Network (MPNN). Comprising message passing layers, MPNN GGimer et al. 2017 is common GNN framework. The kt layer is as follows.
Message Passing
Neural
h (k) (h!* (k-1), AGG AI ( (()))),
(1)
where h( is the representation of node e the 1.th layer, U(K), (k()) are functions like multi-layer perceptron (MIP), and AGG denotes an aggregation function like sum or max. The initial node rep-
resentation h is node feature X,. In each message passing layer, information aggregated from neighbors to update the node representation. The final node representations produced by MPNN are the output of the last message passing layer, denoted as MPNN X) h(kk)
RELATED WORK
3.1 LINK PREDICTION MODEL
There are three primary categories of link prediction models. Node embedding methods (Perozzi al. 2014: Grover & Leskovec 2016 Tang et al., 2015) map each node to an embedding vector and combine the embeddings of target nodes to predict link. Link prediction heuristics (Liben
Nowell & Kleinberg 2003; Barabási Albert 1999, Zhou et al., [2099] AAdamic & Adar 2003) develop hand-crafted structural features. GNNs utilize Graph Neural Networks to predict link ex- istence. Among these GNNs, Graph Autoencoder (GAE) (Kipf & Welling/ 2016) uses the inner product of the MPNN representations of two target nodes, (MPNN(i, the representations of link (i,j). It uses MPNN only and thus fails to capture pairwise relations between nodes. In contrast, various GNNs combining MPNN and structural features (Zhang & Chen 2018 Yun et al.] 2021 Chamberlain et al. 2023) have achieved state-of-the performance. Take SEAL (Zhang & Chen 2018) as example. For target link (i, SEAL initially augments node feature X by concatenating each node's shortest path distance to (i, and extracts a k--opp subgraph from the whole graph, generating augmented node feature X' and adjacency A', respec- tively. Subsequently, SEAL applies MPNN to this subgraph and use the sum of node representations within it, Σ,, MPNN u, A', X'). as the target link representation. Other models employ a distinct approach to incorporate structural features. Neo-GNN Yunn et al., 2021) and BUDDY (Chamberlain al., 2023), for instance, directly apply MPNN to the original graph and concatenate structural features, such as the count of common neighbors, with the Hadamard product of target node MPNN representations, MPNN(i, A, X) @ MPNN (j, A, X)) [stuctural features.
MPNN(J, X)), as
3.2 STRUCTURAL FEATURE
Structural features for link prediction vary among models but are generally based on neighbor- hood overlap. Notable heuristies, such as Common Neighbor (CN), Resource Allocation (RA), and Adamic Adar (AA), use first-order common neighbors to compute scores for a target link (i,
CN(i,)
Σ 1, RA(i,))
Σ NE
AA(I,))
Σ
d(u)'
log d(u)
NENDNNA
WENgTNG
Beo-GNN Yunn et al. 1021 and BUDDY (Chamberlain et al.) 2023) extend these heuris- ties by utilizing higher-order neighbors. Neo-
Table 1: Summaay of existing models using Equa- tion (5). FO and HO denote first-order and high- order neighbors, respectively. O and - denote set intersection and difference, respectively.
3
Model Neighbor e
g(x) f(x)
CN
FO
1
1
Heuristics
RA
FO
1/x
AA
FO
1/log
(log(r)

---

Published as a conference paper at ICLR 2024
GNN computes features for high-order neigh- borhood overlap N (1', as follows,
Σ
Ad((),,
(3)
(O)N(())
where f is learnable function of node de- gree di (.). BUDDY (Chamberlain et al. 2023 further utilize high-order neighborhood difference. It computes overlap features {ai, (2, (1, 1,
2, k} and difference features (). ()( 1,,,, 1,,,...,
k...,]] as follows:
(..))
Σ
1, b((i,))=
Σ
(4)
MENT, (ON))6))
00 Up N3.0
All these pairwise features can be summarized into the following framework.
Σ
s(43)s(4())(dt)))
(5)
weNt (oa
where (1) and O) denote the general neighhorhood of and j. ① is operator like intersection or difference, and S,g are node degree and high-order adjacency weight functions, re- spectively. Details how this framework unify existing structure features are shown in Table
3.3 INCOMPLETENESS OF GRAPH
The primary aim of the link prediction task is to forecast unobserved edges, inherently making the input graph incomplete. Nevertheless, graph incompleteness significantly impact structural features, such as common neighbors, and models based on them. This issue has drawn attention in prior works. Yang al. (2022) examined how unobserved links could distort evaluation scores, with specific focus on metrics and benchmark design, while our research concentrates on model design. Dong
(2022) explored the consequences of the presence of target links, whereas our emphasis lies in understanding how incompleteness affects common neighbor- based features. Outside the domain of link prediction, Zhao al. (2023) and Zhao et al. (2021) add edges predicted by GAE to the input graph of GNNs. However, their primary objective was node classification tasks, aiming to enhance edges between nodes of the same class while diminishing others. In contrast, our research addresses distribution shifts and information loss stemming from graph incompleteness, offering unique completion methods and insights tailored for link prediction.
NEURAL COMMON NEIGHBOR
Structural features (SF), such common neighbors, commonly employed in link prediction models. Existing approaches combine SF with Message Passing Neural Networks (MPNN) in two manners (illustrated in Figure p SF-then-MPNN and SF-and-MPNN. However, these approaches exhibit limitations in terms of either scalability or expressivity. To address these issues compre- hensively, we introduce a novel architecture, MPNN-then-SE: which offers unique blend of high expressivity and scalability. Subsequently. we present concrete instantiation of this architecture, Neural Common Neighbor (NCN). All proofs for theorems in this section are in Appendix A
4.1 NEW ARCHITECTURE COMBINING MPNN AND SF
V2
In Figure 2 we categorize existing methods into two architectures:
SF-then-MPNY This category includes SEAL ZZang & Chen 2018) and NBFNet (Zhu et al., 2021). In this approach, the input graph is initially enriched with structural features and then fed into the MPNN, which allows MPNN to leverage SF and have provable expressivity (Zhang& & Chen 2018). However, the drawback is that structural features change with target link, necessitating MPNN to be re-run for each link, resulting in lower scalability.
V
Figure 3: White, green, and yellow colors represent node features 0, 1, and 2, respec- tively. Both links (vi, v2) and (vi, U3) have one com- mon neighbor, making indistinguishable for exist- ing ST-and-MPNN models.
4

---

Published as a conference paper at ICLR 2024
MP-Nnd-MPNN: This category encompasses models like NeoGNN Yun et al. 2021) and BUDDY (Chamberlain et al.) 2023). Here, MPNN takes the original graph as input and runs only once for all target links, leading to high scalability. However, SF are directly concatenated to the final representations and thus detached from MPNN, leading to reduced expressivity.
From these two architectural paradigms, it becomes apparent that feeding the original graph to MPNN is essential for achieving high scalability. Moreover, the coupling between SF and MPNN remains a crucial factor for expressivity. Thus, we introduce a new architecture: MPNN-then-SF: This ap- proach initially runs MPNN on the original graph and then employs structural features to guide the pooling of MPNN features, requiring only one MPNN run and enhancing expressivity. The specific representation of the target link (i.j) is as follows:
Pool (MPNN X) E S}),
(6)
where Pool is pooling function mapping multiset of node representations to single set represen- tation, and S is a node set related to the target link. Multiple node sets can be used in conjunction to produce concatenated representations. This flexible framework can express various models. When using target nodes and j as S and Hadamard product as Pool, it can express GAE:
MPNN(i, A, X) @ (PNN(J, A, X).
Alternatively, we can choose S combinations of high-order neighbor sets of i and j. leading to the following form (see Appendix A.I for the detailed derivation.):
Σ
9 (944 (M,
(8)
VENT
where g a function transforming the edge weight in high-order adjacency matrix. This framework exhibits stronger expressivity than existing SF-and-MPNN models.
Theorem 1. Combination of Equation 7 and Equation S are strictly more expressive than MPNN- only model: GAE, SF-only models: CN, RA, AA, and MPNN-and-SH models: Neo-GNN, BUDDY.
A key factor contributing to its higher expressivity is the coupling of MPNN and SF. While SF- and-MPNN typically only counts the number of common neighbors, MPNN-then-SN similar to SF- then-MPNN, can capture node properties of these common neighbors. As shown in Figure 3 node tuples (vi, U2) and (V), v2) have the same number of common neighbors. However, their common neighbors have different node features, allowing MPNN-then-SF and ST-then-MPNN to distinguish them, a capability that -F-and-MPNN lacks.
4.2 NEURAL COMMON NEIGHBOR
We will now present an implementation for the MPNN-then-SF framework. Notably, the previ- ous models NeoGNN (Yun et al. 2021) and BUDDY (Chamberlain et al. (023) all incorporate higher-order neighbors into their architectures, resulting significant performance improvements. Surprisingly, in our experiments, we observed that the gains achieved by explicitly considering higher-order neighbors were marginal once we introduced MPNN into the framework (as discussed in Section 6.3) We speculate that this marginal improvement arises because MPNN implicitly learns information related to higher-order neighbors. Therefore, considering scalability, we opt to utilize only the target nodes and their first-order common neighbors as the node set, leading to the development of our NCN model:
NCN(i.,.A.,) A, = MPNN(i, A, X) O MPNN(J, A,
Σ MPNN(u, A, (EN()NN)))
(9)
where ((An)) and g(Aja) are constants and ignored, and | denotes concatenation. It has high expressivity.
Theorem 2. NCN is strictly more expressive than GAE, CN, RA, AA. Moreover, Neo-GNN and BUDDY are not more expressive than NCN.
5

---

Published as a conference paper at ICLR 2024
test, complete training, complete
test, incomplate training, inčomplete
test, complete training, complete
test. incomplete training.. incomplete 0.6
0.5
0.9
0.7
0.4
0.8
0.6-
Density
0.3
Hitsie50
0.7
0.4
0.5
Mitsie00
0.5
0.2
0.6
8
0.2-
0.1
0.5
0.0
training
0.0
4
training
Number of common neighbor
Number common neighbor
(a)
(b)
(c)
(d)
Figure 4: Visualization of incompleteness on datasets. The incomplete graph only contains edges
in the training set, and the complete graph further contains edges in the validation and test set. (a)
and (b) visualize the ogbl-collab dataset. (c) and (d) visualize the Cora dataset. (a) and (c) are for
distributions of the number of common neighbors of the training edges and test edges. (b) and (d) show performance of CN on the training set and test set.
To elaborate, in certain scenarios where the properties of common neighbors hold significant impor- tance, NCN outperforms both BUDDY and Neo-GNN in expressiveness.
As our first major contribution, NCN represents straightforward yet potent model for combining structural features and MPNNs. It operates as an implicit high-order model by aggregating first- order common neighbors, each of which implicitly learns higher-order information through MPNN. comprehensive analysis of time complexity is in Appendix E
NEURAL COMMON NEIGHBOR WITH COMPLETION
While NCN outperforms existing models, it relies heavily the common neighbor structure, which the incompleteness of the graph can notably influence. For instance, in cases where node pairs lack common neighbors, NCN essentially degenerates to GAE, rendering unable leverage structural features. Although the absence of common neighbors can suggest that link is unlikely to exist, certain node pairs may possess common neighbors the ground truth that remain unobserved in the input graph due to graph incompleteness. Graph incompleteness is ubiquitous in link prediction tasks, given that the objective is to predict unobserved edges. However, few studies have delved into this issue. In this section, we initially demonstrate that incompleteness can result in the loss of common neighbor information, distribution shifts between the training and test sets, and the con- sequent deterioration of model performance. We propose straightforward yet effective method to tackle these challenges: common neighbor completion (CNC). CNC completes unobserved com- mon neighbors using a link prediction model. With the introduction of CNC, we enhance NCN and introduce Neural Common Neighbor with Completion (NCNC).
5.1 INCOMPLETENESS VISUALIZATION
To illustrate the challenges posed by incompleteness, we analyze two common datasets: ogbl- collab (Hu et al., 2020) and Cora (Yang et al. 2016). We refer to the graph containing only the edges from the training set as the incomplete graph, while the one encompassing edges from the training. validation, and test sets is termed the complete graph.
Given the pivotal role of common neighbor information our NCN model and other link prediction models, we visualize the distribution of the number of common neighbors for training/test edges in both complete and incomplete graphs separately Figure 4 (a)(c). To assess how incompleteness impacts model performance, we present the performance of CN model (as shown in Section 3.2) in four distinct scenarios in Figure (b)
(d). We observe the following effects of incompleteness:
Loss of Common Neighbors. Figure(4c) illustrates that in the incomplete graph, there are fewer common neighbors for both training and test sets, as indicated by the comparison between the blue (green) and red (orange) lines. When comparing the incomplete and complete graphs, it becomes evident that the incomplete graph suffers from a loss of common neighbor information due to in- completeness. Additionally, more links have common neighbors all.
Common Neighbor Distribution Shift. A noticeable distribution shift between the training and test sets is evident in the incomplete graph of the ogbl-collab dataset, seen in the comparison

---

Published as a conference paper at ICLR 2024
between the blue and green lines in Figure 4 a). This shift disappears when the graph is complete (the red and orange lines), indicating that incompleteness is the cause. Such a substantial distribution shift between training and test links could pose challenges in model generalization. This distribution shift is related to the dataset split method. Ogbl-collab is splitted based on the timestamp of edges, and the test edges all belong to the same year. Consequently, compared to the training edges, test edges exhibit stronger correlations with other test edges, resulting in a greater loss of common neighbor when these test edges are absent from the incomplete graph. Conversely, the Cora dataset is randomly splitted, so training and test edges lose a similar ratio of common neighbors and does not exhibit distribution shifts (Figure 4c)
Performance Degradation. The performance of CN aligns with the common neighbor distribu- tion. In the ogbl-collab dataset, the common neighbor distribution is nearly identical for the training set in both the complete and incomplete graphs, as is the performance (See Figure 4 (b)). However, test performance on the incomplete graph decreases significantly as the test distribution changes. Similar trends are observed in the Cora dataset, with test and training scores declining incom- plete graphs when the common neighbor distribution changes compared to the complete graph.
Remark. Note that while common neighbor distribution changes may not fully account for the differences between complete and incomplete graphs, they offer valuable insights into how incom- pleteness alters the input graph structure for other learnable models. Despite CN is non-learable and generraalliz,,,, its calculation for target edge doesn't 't involve the edge itself, thereby avoid- ing data leakage concerns. These findings suggest that having a more complete input graph could yield superior link prediction models. However, in practice, we only work with the incomplete input graph, necessitating exploring other mitigation methods for these issues.
5.2
COMMON NEIGHBOR COMPLETION
Motivated by the analysis above, we address graph incompleteness issues with a two-step method:
Soft Completion of Common Neighbors. We start by softly completing the input graph with link prediction model, such as NCN. However, instead of completing all edges in the entire graph, which can be impractical for large graphs, we focus specifically on common neighbor links. We compute the probability that a node u serves as a common neighbor for a node tuple (i,j) as follows:
if (1, n A().A) if ((,A))
Ai
Putj
(10)
Ayu IfuEN(i.A-
otherwise
where Åie represents the predicted existence probability of link ui) by the model. The idea is that u is a common neighhor of (i,j) iff both edges (i, u) and (j, u) exist. If one of these edges is unob- served, we use NCN to predict its link existence probability, which we also use as the probability of u being a common neighbor. In the rare case where both (i, u) and (j, u) are unobserved, we set the probability O. This technique is called "Common Neighbor Completion" (CNC).
Reapplication of NCN on the Completed Graph. Following CNC, we apply the NCN model again on the graph that has been completed using the soft common neighbor weights Puij- This final model is named Neural Common Neighbor with Completion (NCNC) and is defined as:
NCNC(I, 5, A, X)= = MPNN(1, A, X) O MPNN(J, XII
Σ MEN(UUN()
Pug,MPN((,, A, X).
(11)
Notably, the input graph of MPNN still takes the original graph as input, allowing it to run only once for all target links, thus maintaining high scalability. While Put be predicted using any link prediction model, weak models may not accurately recover the unobserved common neighbor structure. Therefore, in practice, we employ NCN to complete it.
In addition to addressing distribution shifts and common neighbor loss, NCNC also solves the prob- lem that NCN can degrade to GAE when node pairs lack common neighbors. With NCNC, common
7

---

Published as a conference paper at ICLR 2024
Table 2: Results on link prediction benchmarks. The format is average score + standard deviation.
OOM means out of GPU memory.
Cora
Citeseer
Pubmed
Collab
PPA
Citation2
DDI
Metric
HR @ 100
HR@ 100
HR@ 100
HR@50
HR @ 100
MRR
HR
CN
33.92:0.46
29.7910.90
23.13 13
56.4420.00
27 60.0000000
51.47=0.00
17.73:0.00
AA
35.1911.33 39.8
27.38
64.35:10.0 00
51.8920.0 00.0000000
18.61:0.00
RA
41.07=0.45
33.56+0.17
27.03=0.35
64.00=0.000
49.33++0.00
51.98=00.0
27.60=0..00
GCN
67.0812.94 6..79 65
1.
44.75:1107
18.6711.32
84.7410.21
37.07:5.07
SAGE
55.02:14.0 03
37.01
39.66 7.
48.10
16.5512.40
02.60
53.90
SEAL
81.71:1.00
83.89
1.35
64.74
18.80
87.67
30.56:3.86
NBFnet
71.65+2..2
14.07
9..73
OOM
0OM
OOM
4.00
Neo-GNN
10.42+1.3
84.67
13.9
57.52+0.37
49.13
87.26
63.57
BUDDY
88.00+0.44
92.93+0.27
74.10=0.78
65.9440.58
49.85
87.56=0.11
78.51+1.30
NCN
89.05
11.5611.48
19.05=1.16
64.7640..8
61. 1940..8
88. =0.09
82.3226.10
NCNC
89. $9.65-1
93. 93.47 +..995
81. :0.9
66. 0.
61. 72.
49.12+0..4
84. #3.07
Table 3: Ablation study on link prediction benchmarks.
Cora
Citeseer
Pubmed
Collab
PPA
Citation2
DDI
Metric
HR@ 100
HR@ 100
HR@ 100
HR@50
HR @ 100
MRR
HR@20
CN
33.92
29. 19.
23.13
56, 0.000
27 97.65.0.00
=1.47=0000 17.73
GAE
89.01+132
91.78
78.81
49.49 79.95=0.09 36.9610.95
61.53
GAE+CN
88.61
91.7540.98
7..04
64.4710.11 40.83 87.81=0.06 85.71
NCN2
88,87
91.36+1.02
80.21+0.78
65.43+0.46
OOM
0OM
OOM
NCN-diff
89.12+1.04
91.96+1.23
80.28
64.08
57.86+1120 86.68-0.1 18.67
NCN
89.05 91.56+1.43 79.05=1.16
64.7610.87
61.1940.66 88.09=0.00
82.3226.10
NCNC 89.65 93.47 81.29 60.71 61.42+0.77 89.12=u.40 84.11#3.67
neighbors are always completed, and the model only degenerates to GAE when both target nodes are isolated nodes. In such cases, where no structural features can be utilized, relying solely on the target node representations is reasonable. For a visual demonstration of CNC's effect, please refer to Appendix [ which illustrates how NCN can make more precise predictions by completing common neighbors for node pairs with observed common neighbors.
EXPERIMENT
In this section, we extensively evaluate the performance of both NCN and NCNC. Detailed experi- mental settings are included Appendix D
We use seven popular real-world link prediction benchmarks. Among these, three are Planctoid citation networks: Cora, Citeseer, and Pubmed (Yang et al. (016). Others are from Open Graph Benchmark (Hu et al., (2200): ogbl-collab, ogbl-ppa, ogbl-citation2, and ogbl-ddi. Their statistics and splits are shown Appendix B
6.1 EVALUATION ON REAL- WORLD DATASETS
In our evaluation real-world datasets, we employ range of baseline methods, encompassing traditional heuristies like CN (Barabási Albert 1999), RA (Zhou et al., 2009), and AA (Adamic
& Adar, 2003), as well as GAE models, such as GCN Kiipf & Welling 2017) and SAGE (Hamilton ctt al. 2017). Additionally, we consider SF-thhenMPPN models, including SEAL (Zhang & Chen -F-NNd-MPNN models like Neo-GNN Yun al. and BUDDY (Chamberlain et al. 2023). The baseline results are sourced from (Chamberlain
2018 and NBFNet (Zhu al.] (221), ,, well
2021
2023).
Our models consist of NCN and NCNC. Their architectures detailed in Appendix
NCN surpasses all baselines on 5/7 datasets and exhibits an average score improvement of 5% compared to BUDDY, the most competitive baseline.
The experimental results are presented Table 2
8

---

Published as a conference paper at ICLR 2024
Even the remaining two datasets, NCN outperforms all baselines except BUDDY. These impres- sive results underscore the outstanding expressivity of our MPNN-then more, NCNC enhances performance by additional 2%, emerging as the rop-perfomming method on all datasets. Notably, on ogbl-ppa, NCNC achieves an HR @ 100 score 61.42%, surpassing the strongest baseline BUDDY by a substantial margin of over 10%. It's worth mentioning that models outperform node embedding techniques (Perozzi et al. 2014; Grroerr& & Leskovec) [0166]
architecture. Further-
Tang et al. 2015) and other GNNs lacking pairwise features (Wang 2021 (see Appendix G
2022) significantly
6.2 SCALABILITY
We compare the inference time and GPU memory on ogbl-collab Figure S
NCN and NCNC
have similar computation overhead to GAE, they both need to run MPNN only once. In contrast, SEAL, which reruns MPNN for each tar- get link, takes 86 times more time compared with NCN with a small batch
SEAL
Neo-GNN
GAE
NCN
NCNC
CN
10
10
GPU memory/GB
size 2048, and the disad- vantage will be more sig-
time!s
10
100
nificant with a larger batch size. Surprisingly, BUDDY and Neo-GNN are slower than NCN. The reason is that it uses pairwise fea- tures depending high or- der neighbors that are much more time-consuming than common neighbor. NCN and NCNC also achieve low GPU memory consumption. We also conduct scalability comparisons on other datasets and observe the same results (see (F)
10
10a
10a
10
batch size
batch size
Figure Inference time and GPU memory on ogbl-collab. The pro- cess we measure includes preprocessing and predicting one batch of test links. As shown in Appendix B relation between time y and batch size t is y B Ct, where B, C' are model-specific constants. SEAL has out-of-memory problem and only uses small batch sizes.
6.3 ABLATION ANALYSIS
To assess the effectiveness of the NCNC design, conducted a comprehensive ablation analysis, as presented in Table B
Starting with GAE, which relies solely node representations, introduced GAE+CN, which in- corporates Common Neighbor (CN) as pairwise features. Remarkably, GAE+CN outperforms GAE by 70% Open Graph Benchmark (OGB) datasets, illustrating the importance of structural fea- tures, Furthermore, NCN exhibits a 5.5% score increase over G GAE+CN, highlighting the advantages of the MPNN-then-SI architecture over the MPNN-and-SF architecture.
We also explore variants of NCN, namely NCN-diff and NCN2. In NCN-diff, we include neigh- borhood difference information by summing the representations of nodes in Nii, A) N(j. A) and N Njj. A) - . (i, while NCN2 incorporates high-order neighborhood overlap using (i,, A²) n N A) and (ii, A) A²). Notably, NCN, NCN-diff, and NCN2 exhibit similar performances across most datasets, suggesting that first-order neighborhood overlap might be sufficient. However, NCN-diff achieves a lower score on the DDI dataset, possibly because the high node degree DDI introduces noisy and uninformative neighborhood difference information.
7 CONCLUSION
In this work, we introduce Neural Common Neighbor (NCN), scalable and robust model for link prediction that harnesses the power of learnable pairwise features. Additionally, we address the chal- lenge of graph incompleteness by identifying and visualizing common neighbor loss and distribution shifts stemming from this issue. To mitigate these problems, we introduce the Common Neigh- bor Completion (CNC) technique. Combining CNC with NCN, our final model, Neural Common

---

Published as a conference paper at ICLR 2024
Neighbor with Completion (NCNC), outperforms ofateoof-the-at baselines across various datasets in terms of both speed and prediction performance.
8 LIMITATIONS
Though we propose MPNN-then-SF framework, we do not exhaust the design space and only pro- pose implementation, NCN, and its variants NCN2 and NCN-diff in ablation study. Moreover, while we only analyze the impact of incompleteness on common neighbor structures, graph incom- pleteness can also affect other structural features. Additionally, the proposed completion method has the potential to be generalized to address other structural features. Our future research will ex- and the broader implications of incompleteness on various plore the design space of MPNN- structural features.
REPRODUCIBILITY STATEMENT
Our code is available at https://git /tit://b..uub..... http:s//ggghhbb..ommrrrrrraaaeee Proofs of all theorems in the maintext are in Appendix
ghbor
ACKNOWLEDGEMENT
This work is partially supported by the National Key R&D Program of China (2022ZD0160303), the National Natural Science Foundation of China (62276003), and Alibaba Innovative Research Program.
REFERENCES
Lada A Adamic and Eytan Adar. Friends and neighbors on the web. Social networks, 25(3)2211-230, 2003.
Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama, Optuna: A next-generation hyperparameter optimization framework. In KDD, pp. 2623-2631, 2019.
Albert-Láázı6 Barabási and Réka Albert. Emergence of scaling in random networks. science, 286 (5439):509-512, 1999.
Benjamin Paul Chamberlain, Sergey Shirobokov, Emanuele Rossi, Fabrizio Frasca, Thomas Markovich, Nils Hammerla, Michael M. Bronstein, and Max Hansmire. Graph neural networks for link prediction with subgraph sketching. ICLR, 2023.
Kaiwen Dong, Yijun Tian, Zhichun Guo, Yang Yang, and Nitesh V. Chawla. Fakeedge: Alleviate dataset shift in link prediction. In LoG, volume 198, pp. 56. PMLR, 2022.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv: 0003::900.0000 00940222.., 2019.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In ICML, pp. 1263-1272, 2017.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. KDD, pp- 855-864. ACM, 2016.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning large graphs. NewrlPS, pp. 1025-1035, 2017.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovee. Open graph benchmark: Datasets for machine learning on graphs. NewrIPS, 2020.
Thomas N. Kipf and Max Welling, Variational graph auto-encoders. CoRR, abs/161 1.07308. 2016.
10

---

Published as a conference paper at ICLR 2024
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net-
works. In ICLR, 2017.
David Liben- and Jon Kleinberg. The link prediction problem for social networks. In Inter- national conference on Information and knowledge management, pp- 556-559, 2003.
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. NeurIPS, 32, 2019.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: online learning social representa- tions. In KDD, pp. 701-710. ACM, 2014.
E. Amiri Souri, Roman Laddach, S. N. Karagiannis, Lazaros G. Papageorgiou. and Sophia Tsoka. Novel drug-target interactions via link prediction and network embedding. BMC Bioinform., 23 (1):121, 2022.
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang. Jun Yan, and Qiaozhu Mei. LINE: large-scale information network embedding. Aldo Gangemi, Stefano Leonardi, and Alessandro Panconesi (eds.), WWW, pp. 1067-1077, 2015.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
Zhitao Wang, Yong Zhou, Litao Hong, Yuanhang Zou, Hanjing Su, and Shouzhi Chen. Pairwise learning for neural link prediction. CoRR, abs/2 2as/21122 12.02936, 2021.
Zixiao Wang, Yuluo Guo, Jin Zhao, Yu Zhang, Hui Yu, Xiaofei Liao, Hai Jin, Biao Wang, and Ting Yu. GIDN: A lightweight graph inception diffusion network for high-efficient link prediction. CoRR, abs/2210.01301, 2022.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2019.
Haotong Yang, Zhouchen Lin, and Muhan Zhang. Rethinking knowledge graph evaluation under the open-world assumption. pp. 13683-13694, 2022.
Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. Revisiting supervise learning with graph embeddings. In Proceedings of the 33nd International Conference on Machine Learn- ing, volume 48, pp. 40-48, 2016.
Seongjun Yun, Seoyoon Kim, Junhyun Lee, Jaewoo Kang, and Hyunwoo J. Kim. Neo-gnns: Neigh- borhood overlap-awand aware graph neural networks for link prediction. In NeurlPS, pp. 13683-13694, 2021.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. NeurIPS, 31: 5165-5175, 2018
Muhan Zhang and Yixin Chen. Inductive matrix completion based on graph neural networks. In ICLR, 2020.
Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: theory of using graph neural networks for multi-node representation learning. NeurIPS, 34:9061-9073, 2021.
Jianan Zhao, Qianlong Wen, Mingxuan Ju, Chuxu Zhang, and Yanfang Ye. Self-supervised graph structure refinement for graph neural networks. In WSDM, pp. 159-167, 2023.
Tong Zhao, Yozen Liu, Leonardo Neves, Oliver J. Woodford, Meng Jiang. and Neil Shah. Data augmentation for graph neural networks. In AAAI, pp. 11015-11023, 2021.
Tao Zhou, Linyuan Lü, and Yi-Cheng Zhang. Predicting missing links via local information. The European Physical Journal B, 71(())623-630 2009.
Zhaocheng Zhu, Zuobai Zhang, Louis-Pascal A. C. Xhonneux, and Jian Tang. Neural bellman- ford networks: A general graph neural network framework for link prediction. In NeurlPS, pp- 14476-99490, 2021.
11

---

Published as a conference paper at ICLR 2024
A PROOF
A.1 DERIVATION OF EQUATION
The MPNN-then-SPP architecture is as follows,
Pool (MPNN A, E
(12)
Let Sab be the following set,
a (N) a (2) n {u VIA a nu VI4 b}.
(13)
Then, for Sab. we set the pooling function to sum and multiplied with (()) where g is a function with high-order adjacency edge weight input. Then the MPNN-then-S3 architecture express,
g(a)g(6)MPPN((L X)
(14)
NES
Simply sums the feature of all Sat leads
Σ
g (.,)) X).
(15)
WE NEN (1)
A.2 PROOF OF THEOREM 1
AND
Here, we present the theoretical proof MPNN-then-SIT higher expressivity. We say algorithm A is strictly more expressive than algorithm B when A can differentiate all pairs of links that B can differentiate, while there exists a pair of links that can distinguish while B cannot. We first prove the more expressive results by simulating other models with SF-then-MPNN and NCN then prove the strictness by constructing an example.
Lemma 1. Equation 7 and NCN are more expressive than Graph Autoencoder (GAE)
Proof. Graph Autoencoder's prediction for link (i, j) is (MPNN X), MPNN A, X)). So directly sum Equation leads to GAE. Equation is part of NCN, so NCN can also express GAE.
Lemma 2. NCN more expressive than CN,RA, and AA. Combination of Equation Znd Equation is more expressive than CN,RA,A, BUDDY and Neo-GNN
Proof. As MPNN can learn arbitrary functions of node degrees, NCN can express Equation and Equation 8 can express the general form of structure feature
Furthermore, we construct an example in Figure 3 that graph, 822 and Ut are symmetric and thus have the same MPNN representation, GAE cannot distinguish (U1, U2) and v3). Moreover, (Wi, 02) and (Ua, 03)) are symmetric if the node feature is ignored, so CN, RA, AA, Neo-GNN, BUDDY cannot distinguish them. However, (U1, U2) have common neighbor with feature and (M), 13) have a common neighbor with feature 1, so NCN can distinguish them.
B DATASET STATISTICS
The statistics of each dataset are shown in Table
Random splits use 70% 00%/10%/200 edges for training/valiiatiionness set respectively. Different from others, the collab dataset allows using validation edges as input test set.
C MODEL ARCHITECTURE
This section concludes our methods in Section 4 and Section 5
Given input graph A, node feature matrix X, and target links ((11.j)) (12, f2), (ds,jt)), our models consist of three steps: target link removal, MPNN, and predictor. NCN and NCNC only differ in the last step. The model architecture is visualized in Figure
12

---

Published as a conference paper at ICLR 2024
Table 4: Statistics of dataset.
Cora
Citeseer
Pubmed
Collab
PPA
DDI
Citation2
#Nodes
2,708
3,327
18,717
235,868
576,289
4,267
2,927,963
#Edges
5,278
4,676
44,327
1,285,465
30,326,273 fixed
1,334,889 fixed
30,561,187
splits
random 3.9
random 2.74
random 4.5
fixed
fixed
average degree
5.45
52.62
312.84
10.44
(l.f)
M
A
TLR
Ā
P
predictor
As
N
X
(L.)
(a)
(i.f)
NCN
h4 O h4j
M
NCNC
hy O h2
h
Σ bx
L
Ai
Σ
h
Aute
Ayahe
P
Asj
Ara-1 Aya=1
1
Ave Ane
NCN
(..R)...)
(b)
Figure 6: Architecture of our models. (a) The overall architecture. Given node feature X, adjacency matrix A and target link (i,j), models first set Ag 0 Target link removal, TLR). Then, A, X are fed to vanilla MPNN for node representations produces Auj. the probability that edge (i,j) exists. (b) The NCN predictor. It uses node represen- tations of target nodes j and their common neighbors produce edge representations. Then, (c) The NCNC predictor. It first uses NCN to predict unobserved links Au Ask, which is then used to complete unobserved common neighbors.
With (1,j), h, and A as input, the predictor
feeds the edge representation to an MLP to produce the final prediction.
Target link removal. We make no changes to the input graph in the validation and test set where the target links are unobserved. In the training set, we remove target links from A. Let A denote the processed graph. This method is detailed in Section
MPNN. We use MPNN produce node representations For each node
h = MPNN(i, A, X).
(16)
For all target links, MPNN needs to run only once.
Predictor. Predictors use the node representations and graph structure to produce link prediction.
Link representations of NCN are follows,
Zig (h; Ohil
Σ hw),
(17)
N).A)
where || means concatenation, Zij is the representation of link (i,j). z,y composed of two compo- nents: two nodes' presentation h4 @ hy and representations of nodes within the common neighbor set. The former component often used in link prediction models (Kipf & Welling 2016 Yun
et al., 2021; Chamberlain et al. 2023), while we propose the latter one for the first time. Link representations are then used to produce link existence probability.
Å sigmoid(MIPP((
(18)
13

---

Published as a conference paper at ICLR 2024
Table 5: Total time(s) needed in one run
Cora Citeseer Pubmed Collab
PPA
Citation2
DDI
NCN
28
320
9375
7123
546
NCNC
15
27
54
730
77385
5170
1785
Table 6: Scalability comparison. h, h. h": the complexity of hash function in BUDDY, where are all d. F: the dimension of node representations. When predicting the target links, time and space complexity of existing models can be expressed as O Ct) and O(D + E1) respectively.
Architecture
Method
B
C
D
MPNN only
GAE
ndF + mFF
F²
nF
MPNN-and-ST
Neo-GNN
ndF + nF + nd'
d' + r²²
oF
+ ndd
d' F F h'
BUDDY
ndF + nh
h' F
nF nh"
UF-then-MPNN
SEAL
0
d' +1 F + d" p2
0
d''11 F
MPNN-then-S5
NCN
ndF + nF
dF + F2
nF
dF d²
NCNC
ndl + nd
de F' + d1222
mF
where Aij is the probability that link (t,j) exists.
NCNC has similar form. The only difference is that EIEN(AAINNG...) hu in Equation replaced with the follow form:
17 is
Σ
hn
Σ
Aicha + Σ Ajuhu-
(19)
MEN(..A) (NE,A)
(EN(s.))- N(J.))
((SA))
where Ass is the link existence probability produced NCNC.
D EXPERIMENTAL SETTINGS
Computing infrastructure. We leverage Pytorch Geometric (Fey Lenssen 2019) and Py- torch (Paszke et al. 2019) for model development. All experiments are conducted an Nvidia 4090 GPU on a Linux server.
Baselines. We directly use the results reported in (Chamberlain et al. 2023
Model hy perparameeerr. We use optuna (Akiba et al. 2019) to perform random searches. Hyper- parameters were selected to maximize validation score. The best hyperparameters selected for each model can be found in our code.
Training process. We utilize Adam optimizer to optimize models and set epoch upper bound 100. All results our models are provided from runs with random seeds.
Computation cost The total time of each main experiment is shown in Table 5 Reproducing all main results takes 280 GPU hours.
E TIME AND SPACE COMPLEXITY
Let t denote the number of target links, denote the number of nodes in the graph, and denote the maximum node degree. Existing models' time and space complexity can be expressed in O(B + Ct) and O(D Et) respectively, where B, C, D, E are irrelevant to t. B, C, D, E of models are summarized in Table 6 The derivation the complexity is as follows. As NCN, GAE, and GNN with separated structural features MPNN the original graph, they share similar ndF nF2 B. Specifically, BUDDY (Chamberlain et al. 2203) uses a simplified MPNN with ndF B. Moreover, Neo-GNN needs to precompute high order graph A', which takes ((dd)) time and space.
14

---

Published as a conference paper at ICLR 2024
BUDDY
Neo-GNN
SEAL
Neo-GNN
GAF
NCH
NCNC
10a
GPU momory/cs
100
mamory/Cii
100
10
10
umels
10
10-2
1
10
10-3
10
10a
16
batch
batch
batch
size
(a) Cora
(b) Citeseer
BUDDY
SEAL
Neo-GNN
GAE
NCN
NCNC
SEAL
NCN
NCNC
10
GPV memoryyra
10a
memory/Go
10-
tmmes
10
timels
10a
20
20
10
10-2
10-1
10-2
102
10a
10
size
(c)
Pubmed
(d) Oghl-ppa
BUDDY
SEAL
Neo-GNN
GAE
NCN
NCNC
SEAL
Neo CNN
GAE
NCN
NCNC
GPU memoryyCG
10
memoryy/G
10a
timels
timols
101
10a
10
10
10-2
10
10-1
10
10
10
10*
10a
batch
batch
batch
(c) Ogbl-ddi
(l Oghl-citation2
Figure 7: Inference time and GPU memory on datasets. The process we measure includes prepro- cessing, MPNN, and predicting one batch of test links.
BUDDY needs to hash each node and takes ((nh) time and O(nh') space. In contrast, B of SEAL is as it does not run MPNN on the original graph. For each target link, vanilla GNN only needs to feed the feature vector to MI. for each link,
F22 Besides GAE's operation, BUDDY further needs to hash the structure for structural features, whose complexity is complex but higher than d per edge, and Neo-GNN computes pairwise feature with Odd') complexity, where is the number of hop Neo-GNN consider. NCN needs to compute common neighbor: (d)), pool node embeddings: (dF)), and feed MLP: ( NCNC-1 runs NCN for each potential common neighbor: O(F² + d(dF + F²)) O + d Similarly, NCNC-K runs ((d) times NCNC- (K (), so its time complexity is O + d F²). For each target link, SEAL segregates subgraph of size O(d") and runs MPNN on it, so C = d F2 + d'+1 F, where is the number of hops of the subgraph.
F SCALABILITY COMPARISON ON DATASETS
The time and memory consumption models on different datasets are shown Figure On these datasets, we observe results similar to those the ogbl-collab dataset in Section 6.2 NCN achieves similar computation overhead to GAE; NCNC usually scales better than Nco- SEAL's scal- abilty is the worst. However, consumption with small batch sizes, because the whole graph ogbl-citation2 is large, on which MPNN is expensive, while SEAL only runs MPNN small subgraphs sampled from the whole graph, leading to lower overhead.
the ogbl-citation2 dataset, SEAL has the lowest GPU memory
G COMPARISON WITH OTHER LINK PREDICTION MODELS
Node embedding methods The main advantage of GNN methods is that they keep permutation equivariance. In other words, these methods can give isomorphic links (links with the same struc- ture) the same prediction. In contrast, node embedding methods, such Node2Vec (Grover &
15

---

Published as a conference paper at ICLR 2024
Table Results on link prediction benchmarks. The format is average score + standard deviation. NCN+tricks means NCN with tricks of PLNLP.
Collab
PPA
Citation2
DDI
Metric
Ho
Hits@ 100
MRR
NCN
64.76 + 0.87
61.19 0.85
88.64 0.14
82.32 = 6.10
NCNC
66.61 + 0.71
+ 01.4200:1
89.12 + 0.40
84.11 + 3.67
Node2 Vec
41.36 = 0.69
27.83 2.02
53.47 + 0.12
21.95 + 1.58
DeepWalk
50.37 + 0.34
28.88 + 1.53
84.48 + 0.30
26.42 6.10
LINE
55.13 + 1.35
26.03 + 2.55
82.33 0.52
10.15 1.69
PLNLP
70.59 = 0.29
32.38 + 2.58
84.92 0.29
90.88 = 3.13
GIDN
70.96 0.55
NCN+tricks
68.04 = 0.42
90.83 = 2.83
3
3
3
4
4
4
O
O
5
2
2
2
Observed Graph Prediction: 0.1737
Graph After Completion Prodiction: 0,5999
Full Graph Ground Truth: 1
Figure 8: Visualization of how NCNC works. The example is from the Cora dataset, citation graph. The target link is (0, Models should produce high link existence probability. However, in the observed graph, link (0, 5) is missing, and (0, 1) thus has no common neighbor. So NCN predicts that the link is not likely exist. However, for NCNC, it first completes common neighbors (see green lines). Therefore, NCNC predicts that (0, 1) is more likely to exist. Note that NCNC completes common neighbors by probability, and we only plot completion with probability ù 0.5 here. And the two completions
with about 0.95 probability. Though the common neighbor 2 completed by the model does not exist in the full graph, the full graph here only means a graph with all training, validation, and test edges, and the citation relation in the graph may still need to be completed.
Leskovee 2016), LINE (Tang al. 2015), and DeepWalk (Perozzi al. 2014), will produce dif- ferent results for isomorphic links, leading to potentially bad generalization.
We also compare method with representative node embedding methods ogb datasets in Ta- 7 NCN and NCNC outperform node embedding methods significantly on all datasets, indicating the advantages of MPNNs considering pairwise features for link prediction.
Other GNNs Instead of representations of pairwise relations, PLNLP (Wang al. 2021 and GIDN (Wang et al. (022) boost GNNs on link prediction tasks by training tricks like loss function and data augmentation. These tricks are orthogonal to our model design. In experiments (Table 7 compared with PINLP, NCN achieves 89% performance gain ogbl-ppa and 20% gain average. As GIDN only conducts experiment on one dataset ogbl-collab, the comparison not complete. Moreover, tricks of PLNLP can also boost our models.
H CNC EXAMPLE
Figure provides example from Cora dataset how CNC works.
16

---

Published as a conference paper at ICLR 2024
I ABLATION OF MPNN
Here we provide an ablation study on the MPNN used in NCN. The results are shown in Table g
The MPNN model includes GIN (Xu al. 2019). GraphSage (Hamilton al. 2017). MPNN with
max aggregation, GCN (Kipf & Welling 2017), and GAT (Velickovic et al. 2018 Though the
performance of NCN is sensitive to the MPNN model, NCN achieves performance gain with all GNNs compared with GraphAutoencoder (GAE).
Table 8: Ablation study MPNN.
Dataset
Model
GIN
GraphSage
max
GCN
GAT
Cora
GAE
70.45
70.5941.70
61.63
89.01
83.3612.54
NCN
70.62=1.68 70.94
66.53+2.27
89.05+0.99 969
83.9342.08 03
Citeseer
GAE
61.21+1.18
61.23+1..2
53.02+3.75
91.78++0.11
68.4942.75
NCN
61.58=1.18
61.95=1.05
53.40+2.31
91.56+1.43
69.27
Pubmed
GAE
59.00
57. 57.20
55.0811.44
78.81 1:164
74.44
NCN
59.06.0.49
58.0610069
56.3210.77
79.05:1.116
74.43
collab
GAE
38.94
28. 28.1140.26
27.08+0.61
36. 36.9640.95
OOM
NCN
64.3840.00
63.9440.43
64.1940.18
64.7640.87
OOM
ppa
GAE
18.20
11.79+1.02
20.8640.81
19. 19.4944075
OOM
NCN
47.94
56.41
57.3140.30
61.1940.88
0OM
J CHOICE OF METRICS
We test our model in different metrics. The results are shown in Table 9 In total, NCN achieves I best score (in bold), NCNC achieves 22 best score, and our strongest baseline achieves best score. Therefore, our NCN and NCNC still outperforms basclines in different metrics.
Table 9: Models' performance with various metrics. BUDDY is strongest baseline. Blanks mean unfinished experiments due to time constraints.
Cora
Citeseer
Pubmed
Collab
PPA
Citation2
DDI
hit@1
NCN
16. 24 29.32
7.03_a.10
4.94_2.95
5.91_4.11
83.7949.00
0.24
NCNC
10.90411.40 32.45
8.
9.82_2.48
7.78
0.1640.07
BUDDY
11.74 20.87+12.12
2.97=2.02
10.71+0.64
2.29-1.26
2.40=4.51
hit@3
NCN
29.52 19.98
19.16-4.39
11.07
26.32
15.3223.31
92.4110.06
1.5443.43
NCNC
25.04 50.49
21.07 17.58 15.48
21.07
16.58.0.60
0.59
BUDDY
32.67
41.1649.12
10.41
16.25+1.09 7.75-0.48
10.84
hit@ 10 NCN
55.8724.40
69.65
13.05
34.61 15.00
13.51
25.76
96.5010.00
10.01
NCNC 53.78-7.33
69.59
34.29
26.67 43.22-6.19
26.
26.67+1..1
45.61414.12
BUDDY
50.98 23.46
67 67.0542.89
23.92
53.11
20.86
17.41
52. 12.70++.00
hit@: 20
NCN 68.31 13.00
78.02.1.0
50.9443.11
55.87
37.57 11.98
97.87
82.55-44.08
NCNC
67.10
79.05 68
51.4223.81
57.8323.14
35.00=2.22
83.924s.
BUDDY
61.92_2.67
76.15
34.75
59.06-0.57
27.28
78.1444..23
hit@:50 50
NCN 80.85
86.33
67.77
64.45
51.54
99.01 +0.02
94.17 4:036
NCNC
$1.36-1.80
88. 18.60+1.57
69.
69.2522.a7
66.
20.88
48.66
48.6620.18
94.85-20.0
BUDDY
76.64-2.45
85.4612.17
55.75
66.09
39.99-n.02
92.17
hit@ 100 100 NCN
89.1441.04
79.5641.11 91.8241..4
67.2540.15
61.25
99.51
97.09440.43
NCNC
89.05
93.13411 1
81.18 + 14
71.96
62.02.0.74
97.60
BUDDY
81.82=1.96
91.4811.15
70.92
70.53
48.07
95.38
mtr
NCN 29.20
43.93+12.8
17. 17.4413.40
13. 13.48 13.76
88.62 08.62210.5
5.48
NCNC
23.55-9.65
45.64
15.63
17.68
14.37
8.61
BUDDY
27.28-4.11
35.77 19.59
10.79 12.61
18.97.0.55
7.47-0.00
13.53
17


Reviews:
[{"review_id": "fbKYP9ogFl", "reviewer": "Reviewer_Ztrp", "summary": "This paper addresses the challenge of GNN-based link prediction, presenting a new framework MPNN-then-SF, aimed at enhancing the expressiveness of structure feature-based link prediction methods. The framework, operationalized through the NCN implementation, incorporates common neighbor features beyond simple counts. This work also tackles the issue of graph incompleteness that can lead to suboptimal link prediction results. The authors propose a common neighbor completion strategy to enrich the input graph. Experimental findings indicate that this methodology outperforms baseline models significantly.", "questions": "See weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThe proposed MPNN-then-SF framework innovatively incorporates common neighbor features beyond simple counts, enhancing the expressiveness of the graph-based link prediction model. NCNC further addresses the problem of graph incompleteness through the common neighbor completion module.\n2.\tThe exploration into how graph completeness affects prediction outcomes is insightful. It underscores the importance of a comprehensive input graph for robust link prediction, setting the stage for further research in this area. \n3.\tThe results, as evidenced by Table 2 and Figure 5, show considerable improvements in expressiveness and scalability. The detailed analysis in Table 3 underscores the contribution of each component within the proposed framework, validating its effectiveness.", "weaknesses": "1.\tWhile Figure 5 suggests that inference time does not increase significantly, calculating P_{uij} values for all node pairs could, in theory, create a computational burden. The paper would benefit from a more detailed explanation of this process. Is there a mechanism, such as pre-calculation or an efficient online algorithm, that mitigates the computational load during the inference phase? \n2.\tThe paper reveals that a first-order neighborhood is adequate by comparing NCN and NCN2 models. However, the potential of incorporating a broader neighborhood scope remains unclear. Could extending the common neighbor completion (CNC) to consider 2-hop neighbors improve performance significantly? It would be beneficial for the paper to discuss the implications of such an extension and, if possible, to present experimental results from implementing a 2-hop neighbor completion, referred to as NCNC, for a thorough comparison.", "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": "", "extra_scores": {}}, {"review_id": "nas8kMt8mt", "reviewer": "Reviewer_tCCB", "summary": "In this paper, the authors propose a novel link prediction model called NCN. Unlike prior works, which can be classified into SF-then-MPNN and SF-and-MPNN categories, NCN introduces a novel architecture, MPNN-then-SF, that overcomes the defects of the previous two methods and offers a unique combination of high expressivity and scalability. Further addressing the Common Neighbor (CN) distribution shift problem caused by the graph incompleteness in existing link prediction settings, the authors introduce the Common Neighbor Structure Completion module to enhance NCN's performance. Finally, through extensive experiments on seven commonly used link prediction datasets, the author demonstrates the model's effectiveness and establishes it as the new state-of-the-art model for link prediction tasks.", "questions": "How does the method behave on graphs without node features?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The paper is well-written, and the idea is easy to follow. For most claims, the paper provides either theoretical proofs or empirical results to support them, demonstrating its soundness.\n\n- Extensive experiments have been conducted on commonly used link prediction benchmark datasets, with most baselines being competitive. The paper also includes details about efficiency statistics (time and resource consumption) and parameter settings.\n\n- The observation regarding the CN distribution shift is very interesting and could inspire future work aimed at improving the performance of link prediction models by addressing this issue.", "weaknesses": "There are some minor issues with notation. For example, in Equation 6, why are double brackets used, \"{{\" and \"}}\"? In Equation 9, it would be better to explain the symbol \"||\" as concatenation again, as the definition of \"||\" is provided at the end of section 3.1, which is quite far away and might cause confusion for readers.", "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": "", "extra_scores": {}}, {"review_id": "QUkGeVfFGh", "reviewer": "Reviewer_nThn", "summary": "In this paper, the authors propose a novel link framework, which they combine the MPNN and the SF. It is interesting to investigate the combination of the MPNN and the SF. However, the authors mainly compare their method against solely using the MPNN and solely using the SF. Another issue lies in the time complexity analysis. It would much better to report the time complexity of their paper compared to solely using the MPNN and the SF and the other combination methods.", "questions": "Firstly, in the introduction section, the authors have described three ways to combine the MPNN and the SF. However, there are no clear comparisons among these approaches. For example, what use cases fit each approach, and what is the complexity cost of each way? Second, the description of their approach is in Section 3.2, which is very simple and straightforward. I expect more analysis on why the proposed method is better than other combinations, instead of proving why the proposed method is better than solely using the MPNN and solely using the SF. For the experiment, I consider the proposed framework to be a general framework that can be applied to various GNNs. Therefore, I expect to see the results of employing the proposed method in different GNNs to verify the generalizability of the proposed method. Moreover, I also want to ask the authors why to report the results in terms of different evaluation metrics in Table 3. Could you please provide a completed version in the appendix? Also, in Table 3, we can see in some datasets such as Core, CIteseer, and Pubmed, there is very slight difference between GAE and NCN. I highly recommend the authors to further investigate the best use cases of the proposed method. Furthermore, it would be very interesting to summarize a table that includes the pros, the cons, and the best use cases, the worse use cases of different combinations in Figure 2. In Section 6.2, the authors report the memory costs, I highly recommend the authors to report the time complexity cost of applying the proposed methods against solely applying the MPNN and solely applying the SF, as the time complexity is quite crucial to determine whether a model can be applied online or not. \nOverall, I do not think this paper is ready for publication for this version. Please correct me if I have some misunderstanding.", "limitations": "", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. It is interesting to study the combination of the MPNN and the SF. \n2. It is great to see the improvement of the proposed method against the baselines. \n3. Summarizing the limitations is always encouraged.", "weaknesses": "1. The theoretical analysis is mainly on the comparison between the combinations of the MPNN and the SF against solely using the MPNN and the SF. \n2. There is no complexity analysis.\n3. There is no clear comparisons among different combinations (as shown in Figure 2).", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)