Can GNNs Learn Heuristic Information for Link Prediction?
Authors: Shuming Liang
Yu Ding
Zhidong Li
Bin Liang
siqi zhang
Yang Wang
Fang Chen
Venue: Submitted to ICLR 2023 (2023)
Keywords: link prediction
graph neural networks
heuristics

Abstract: Graph Neural Networks (GNNs) have shown superior performance in Link Prediction (LP). Especially, SEAL and its successors address the LP problem by classifying the subgraphs extracted specifically for candidate links, gaining state-of-the-art results. Nevertheless, we question whether these methods can effectively learn the information equivalent to link heuristics such as Common Neighbors, Katz index, etc. (we refer to such information as heuristic information in this work). We show that link heuristics and GNNs capture different information. Link heuristics usually collect pair-specific information by counting the involved neighbors or paths between two nodes in a candidate link, while GNNs learn node-wise representations through a neighborhood aggregation algorithm in which two nodes in the candidate link do not pay special attention to each other. Our further analysis shows that SEAL-type methods only use a GNN to model the pair-specific subgraphs and also cannot effectively capture heuristic information. To verify our analysis, a straightforward way is to compare the LP performance between existing methods and a model that learns heuristic information independently of the GNN learning. To this end, we present a simple yet light framework ComHG by directly Combining the embeddings of link Heuristics and the representations produced by a GNN. Experiments on OGB LP benchmarks show that ComHG outperforms all top competitors by a large margin, empirically confirming our propositions. Our experimental study also indicates that the contributions of link heuristics and the GNN to LP are sensitive to the graph degree, where the former is powerful on sparse graphs while the latter becomes dominant on dense graphs.

Under review as a conference paper at ICLR 2023
CAN GNNS LEARN HEURISTIC INFORMATION FOR LINK PREDICTION?
Anonymous authors Paper under double-blind review
ABSTRACT
Graph Neural Networks (GNNs) have shown superior performance in Link Predie- tion (LP). Especially, SEAL and its successors address the LP problem by classi- fying the subgraphs extracted specifically for candidate links, gaining state-of-the- art results. Nevertheless, the information equivalent to link heuristics such as Common Neighbors, Katz in- dex, etc. (we refer to such information as heuristic information in this work). We show that link heuristics and GNNs capture different information. Link heuris- ties usually collect pair-specific information by counting the involved neighbors or paths between two nodes in a candidate link, while GNNs learn node-wise rep- resentations through neighborhood aggregation algorithm in which two nodes in the candidate link do not pay special attention to each other. Our further anal- ysis shows that SEAL-type methods only use GNN to model the pair-specific subgraphs and also cannot effectively capture heuristic information. To verify our analysis, a straightforward way is to compare the LP performance between exist- ing methods and model that learns heuristic information independently of the GNN learning. To this end, we present a simple yet light framework ComHG! by directly Combining the embeddings of link Heuristics and the representations produced by a GNN. Experiments on OGB LP henchmarks show that ComHG outperforms all top competitors by large margin, empirically confirming propositions. Our experimental study also indicates that the contributions of link heuristics and the GNN LP are sensitive the graph degree, where the former is powerful on sparse graphs while the latter becomes dominant on dense graphs.
question whether these methods can effectively learn
INTRODUCTION
Link Prediction (LPP), aiming at predicting the existence likelihood of a link between a pair of nodes in graph, is prominent task in graph-based data mining (Kumar et al., 2020). It has wide range of beneficial applications, such as recommender systems (Wu et al., 2021), molecular interaction prediction (Huang et al., 2020), and knowledge graph completion (Li al., 2022).
Throughout the history of LP research, a number of link heuristics have been defined, such as Com- mon Neighbors (CN), Katz index (Katz, 1953), etc. link heuristic usually describes specific fact or hypothesis that gives the best interpretation to a statistical pattern in link observations (Martínez et al., 2016). The effectiveness of many link heuristics has been confirmed in various real-world L. applications (L.bben-Nowell & Kleinberg, 2007; Zhou et al., 2009; Martínez et al., 2016).
Recently, graph representation learning has been proven powerful for LP (Perozzi et al., 2014; Zhang & Chen, 2018; Yun et al., 2021). Among the approaches in this domain, Graph Neural Networks (GNNs) have demonstrated stronger LP performance than others like node embedding methods based positional encoding (Perozzi al., 2014; Galkin et al., 2021). Modern prevalent GNNs like GCN (Kipf& & Welling, 2017), GAT (Veličković et al., 2018), etc. follow a form neighborhood information aggregation algorithm in which each node's representation is updated by aggregating the representations of this node and its neighbors. In this paper, we use the term GNNs to refer to such aggregation-basen GNNs.
Our code is available at httpt:t////........ / http:tt..oo//tttttinggg/oooo///e

---

Under review as a conference paper at ICLR 2023
Link beuristics are defined by counting the involved neighbors or paths between two nodes.
GNNss leern bode-wise regresentations aggregating
Link?
link?
neighborhood information.
Figure I: An illustration of the difference between link heuristics and aggregation-base based GNNs.
In the literature, several LP-specific methods based on GNNs have been proposed, such as SEAL (Zhang& & Chen, 2018), GraiL. (Teru et al., 2020) and NBFNet (Zhu al., 2021). In particular, SEAL and its follow-up works (Zhang & Chen, 2018; Li et al., 2020; Teru et al., 2020; Yin et al., 2022) predict the link likelihood between two nodes through classifying the subgraph extracted specifically for this target pair of nodes (we refer to such subgraph as pair-specific subgraph). SEAL-type methods also label every node in the pair-specific subgraph according the relationship of the node to the target pair of nodes (Zhang et al., 2021). The pair-specific subgraphs together with the node labeling help SEAL-type methods learn better link representations than other methods, attaining state-of-the-art LP performance.
Despite all successes achieved by existing GNN-based LP methods, we are still curious about the question: whether these methods can effectively learn the information equivalent to link heuristics (i.e., heuristic information) for LP? Our analysis and experiments suggest a negative answer.
Contributions. In this work, we show that traditional link heuristics and GNNs capture different information. As illustrated in Figure I, link heuristics are typically defined based on the number of involved nodes or paths between pair of nodes. They are pair-specific. By comparison, GNN updates the representation of a node by aggregating the representations of this node and its neighbors, where none of the neighbors is treated particularly. The learned nodes' representations are node-level. GNNs pay more attention to what information every node has, while link heuristics focus more on how many shared neighbors or paths are between pair of nodes.
The difference between link heuristics and GNNs means that classical GNN-based LP methods sim- ply combining the node-wise wise representations of two nodes in a candidate link into link representa- tion can hardly learn heuristic information. Moreover, we find that SEAL-type methods also cannot effectively capture heuristic information. Briefly, despite the help of the pair-specific subgraph and node labeling techniques, SEAL-type methods still use a GNN (c.g., DGCNN (Zhang et al., 2018) in SEAL (Zhang& & Chen, 2018), R-GCN (Schlichtkrull et al., 2018) in GraiL (Teru et al., 2020)) to perform graph representation learning, where the GNN inherently lacks the model ability to learn heuristic information. Meanwhile, the labeling features of nodes are mixed in the neighborhood aggregation process of the GNN and the heuristic information embedded in the labeling features cannot be effectively kept the learned node representations.
A simple way to verify our propositions is to study the LP performance of a model that separates the heuristic information learning and the GNN-based representation learning. Therefore, we present a light LP framework ComHI by Combining link Heuristics and the GNN. In ComHG, various link heuristics are encoded into trainable embeddings and combined with the representations produced by GNN, followed by predictor that takes the combinations input to perform the final pre- diction. We conduct experiments on four OGB LP benchmark datasets (Hu et al., 2020). ComHG significantly outperforms all previous methods all datasets. The strong results confirm that link heuristics and the GNN capture different yet effective information for I.,, and suggest that combin- ing both of them can boost LP performance. The results also empirically verify our analysis of the limitations of existing GNN-based LP methods in learning heuristic information. Furthermore, our experimental study shows that link heuristics could contribute more LP performance on sparse graphs while GNN- representation learning becomes dominant on dense graphs.
2 PRELIMINARIES
Without loss of generality, we demonstrate our work homogeneous graphs. Let G E) denote a graph G with N nodes, where V is the set of nodes, [V] = N, and E is the set of edges node
between the nodes in V. A set of nodes connected directly neighborhood set of u and is denoted as r,.. The degree of a node v is defined as the number of edges connected to this node. The degree of graph is defined as the average degree of all nodes.
V is the first-order
2

---

Under review as a conference paper at ICLR 2023
Problem formulation. Link prediction is pair-specific problem, aiming estimate the likeli- hood of the existence of an unknown edge Eyu & E between two nodes v, u E V. We denote the existence likelihood of Eva You and refer nodes v, u as the target pair of nodes.
Link heuristics. Link heuristics mainly extract the struc- tural information between pair of nodes (Martínez et al., 2016). Shortest Path Distance (SPD) is a basic link heuris- tic that follows the underlying intuition that the distance between two related nodes should be short. Table 1 lists five most widely-used link heuristics. Specifically, Com- mon Neighbors (CN) is defined as the size of the intersec- tion between the first-order neighborhood sets of two nodes. Jaccard coefficient (Jaccard, 1901) normalizes the CN by the size of the union of the two nodes' neighborhood sets. AdamicAdar (Adamic & Adar, 2003) and Resource Alloca- tion (RA) (Zhou et al., 2009) both suppress the contribution of nodes by penalizing each node in common neighbors with its degree. Katz, index (Katz, 1953) counts all paths between
Table 1: Classical link heuristics for the node pair (u, u).
Heuristic
Definition
CN
Jaccard
[rrrul [eCFul
AdamicAdar
EseronTe logits]
RA
Exeronis TTa
Katz
E H'athhh
a pair of nodes with weights, where { (path yu I is the size of the set of all paths between node u and (!)
u with the length of and 3 a damping factor where < 3 < 1.
Definition 1. The core function most link heuristics is the set operation of two sets related to two nodes. We define the generalized function for such link heuristics as
Heuristic(v, v, V) (S..OP(S.....))
where (ETOP(..)) is a set operation (e.g., intersection) applied on two sets. S, and S, are the sets related node and u, respectively. f f-) is a function applied on the result of (ETOP(:)))
Many commonly-used link heuristics can be expressed with Equation 1. For example. in CN, S F. S, is T.. SETOP(s is the intersection of S. and S., and f()) obtains the cardinality of the set given by SETOP S.). In Katz index, S, is the set of all paths that contain node & the set of all paths that contain node u, and SETOP(S,, S.) outputs (path,..) } that the set of all paths between node v and u. f(.) sums 3² (path!)) H over different path length I, where } S. (pathhu.)
Definition 2 (Heuristic information). In this work, we say that the information captured by link heuristics is heuristic information.
Graph Neural Networks (GNNs). Modern GNNs iteratively update the representation of each node in a graph by aggregating representations of its neighbors and its own (Corso et al., 2020). Formally, the representation of node v given by the 1-th layer of a GNN is
h AGGREGATE( (( (n10-)) V ET, (.)))
where (0) is initialized with the feature vector of node v. the function AGGREGATE()) is in- stantiated as a pooling operation over a set of node representations, such as MAX, MEAN, or attention-based SUM (Hamilton al., 2017: Veličković et al., 2018). For simplicity, we omit the residual connections, activation functions, etc. In this paper, we use the term GNNs to refer to such aggregation-basee GNNs unless otherwise stated.
Remark 1. The representations learned by GNNs are node-wise.
3
CAN EXISTING GNN-BASED LP METHODS EFFECTIVELY LEARN HEURISTIC INFORMATION?
In this section, we first show the difference between link heuristics and GNNs, and then present our analysis of the limitations of existing GNN-hased IPP methods in learning heuristic information. Proposition 1. The information captured by link heuristics is different from that embedded in the node representations learned by GNNs.
3

---

Under review as a conference paper at ICLR 2023
Proof. Link heuristics are pair-specifie. The Heuristic(e, u, u V) in Equation is specific for the node pair (V, u). where the core function is a set operation of two sets S.). By comparison, GNN in Equation 2 learns node-wise representation h based a pooling operation over all elements in the set { ( v' E r, U {u}), where the GNN does not pay special attention to any particular node in r',. In other words, two nodes in candidate link do not pay special attention to each other in the GNN learning. The information extracted through a set operation of two sets is fundamentally different from that obtained by a pooling operation over the elements in one set.
In addition, link heuristics mainly extract structural information between a pair of nodes by calcu- lating the number of shared nodes paths. They generally take no account of node features. In contrast, GNNs learn node-level representations that are initialized with node features, where the structural information of the graph is mainly used for generating the neighborhood set Tu. I1
According to Proposition 1, we have the following corollary. Corollary 1. GNNs inherently lack the model ability to learn heuristic information, i.e., the repre- sentation of each node learned by GNN lacks heuristic information.
3.1 CLASSICAL GNN-BASED LP METHODS
direct way of applying a GNN to LP is to combine the learned node-wise representations two nodes in a candidate link into pair-wise link representation and then pass it into predictor. We refer to such applications as classical GNN-based LP methods (Hamilton et al., 2017; Veličković et al., 2018; Wang et al., 2021). Formally, the link likelihood of node pair (v, u) is
Dou PREDICTOR (COMBINE (n!.) (1,,,)))) (n))))
(3)
where L is the index of the last GNN layer, COMBINE(,,)) can be Hadamard production, concate- nation, etc., and (REDICTOR(.) is predictor like MLP. Proposition 2. Classical GNN-basee LP methods lack the ability to capture heuristic information.
Proof. The node-wise representations in Equation 3, i.c., (0) ( are learned by a GNN. Accord-
ing to Proposition I and Corollary 1, both (2) and (L) lack heuristic information. Meanwhile, the function COMBINE(->> in Equation 3 can hardly capture heuristic information like Equation 1, since this function does not involve any set operation on two sets related to node and node u.
Classical GNN-based LP methods in Proposition are different from GNNs Proposition 1. The former methods are downstream LP applications using the node representations learned by GNNs.
3.2 RETHINKING SEAL-TYPE METHODS
SEAL and its successors (Zhang & Chen, 2018; Li et al., 2020; Teru et al., 2020; Yin et al., 2022) address the LP problem by classifying the subgraphs that extracted specifically for candidate links. We use the term SEAL-rype methods to refer to these methods.
Subgraph preparation
Subgraph dassificationn
Theettie Extracting the subyraahh Labeling mach specific perificforss... (v, modes
GNN
Node-wise
Readout
Representation for(e,))
Predictor
- Pru
regresentations
Figure 2: The algorithm flow chart of SEAL-type methods.
We briefly describe the algorithm flow of SEAL-type methods. As shown Figure 2, given an entire graph & and target node pair (v, u), a h-hop enclosing subgraph (!h) with a set of nodes v(() {u' (Spd(o', v) S h or Spd(o', u) < h} is extracted from G. where Spd(.,-) calculates the shortest path distance between two nodes. Then, for each node in g(h) a node labeling trick (Zhang al.. 2021) is used to assign labeling vector the node its additional features according to its relationship to (v. u). the modeling stage, g(A)) fed into GNN model, and the node-wise repre- sentations of the nodes in (hh) are learned. Following the last layer of the GNN, readout function
4

---

Under review as a conference paper at ICLR 2023
READOUT(-) is employed over the learned node-wise representations of all nodes in VeA and then pair-specific representation for gou is produced. At last, a predictor PREDICTOR() takes this pair-specific representation as input perform LP for the node pair uv, u). Formally, the link likelihood of (v, u) predicted by SEAL-type methods is
Deu = PREDICTOR (READOUT (f (fng)
VV E F.u
(4)
The (EADOUT()) (e.g., SortPooling in SEAL (Zhang & Chen, 2018)) is typically used for graph- level classification, aiming to deal with size differences among graphs.
SEAL-type methods usually use a node labeling trick to add labeling features to each node in the pair-specific subgraph. The labeling features of a node describe the relationship of the node to the candidate link. Figure 3 shows an example of this, where the labeling features of a node are the shortest path distances from the node to the target pair of nodes. Zhang et al. (2021) show that such labeling features can help a GNN learn better representations for LP.
Despite the benefits brought by the pair-specific sub- graph and node labeling techniques, our following analysis shows that SEAL-type methods still suffer from issues in learning heuristic information.
(1.10)
OLD
(1:4)
(1.3)
2
W
link
(1,6
link?
Proposition 3. The labeling features of nodes contain heuristic information (e.g., SPD). However, the fea- tures of each node would be mixed with the features of other nodes in the neighborhood aggregation pro- cess of GNN and thus the heuristic information in the labeling features cannot be effectively kept in the learned node representations.
(L:))
LL
(1.4)
(L.3)
Positive link
Nagulive link
Figure 3:
Node labeling in SEAL-type methods. The left is pair-specific sub- graph for a positive link sample and the right is negative one. The labeling fea- tures are based on the SPDs from every node (here only show the first-order neigh- bors of node v or w) to the target pair of nodes. For example, on the left, the node with the labeling features (1, 10) indicates that the SPD from this node to node v and is 1 and 10, respectively.
Proof. We use an example to illustrate this. As shown in Figure 3, the labeling features of a node in a pair-specific subgraph are SPDs from this node to the target pair of nodes. in GNN is MEAN, then the aggregation of the la- beling features of the neighbors of node v would be equal to that of node w, i.e., MEAN((10, 3, 2, 13) =
the pooling method
MEAN( (4,6 6, 4, 3, 3)). This means that the labeling features of the neighbors of a node are mixed in the neighborhood aggregation process, and the distinct heuristic information in these labeling fea- tures is not effectively kept in the aggregated result. In other words, the aggregated results for node and w in the positive and negative link samples become indistinguishable Note that in practice, a GNN layer contains a series of complicated operations such as set-based pooling, linear and non- linear transformations, dropout, residual connection, etc. The heuristic information in the labeling features could be partially kept in the learned node representations.
Zhang et al. (2021) point out that the labeling features of nodes can help the GNN learn the heuristic information related to common neighbors. Their explanation is as follows. If node and are labeled, in the first iteration of the neighborhood aggregation in a GNN, only the common neighbors between node and u will receive the labeling messages from both and u; then in the second iteration, these common neighbors will pass such messages back to both v and u, which can encode the number of common neighbors into the representations of node e and u. However, we question this statement. In the second iteration in the explanation above, in addition to the common neighbors between v and u, the non-common neighbors of node also pass their messages back to u. The messages from all neighbors of v are then aggregated through set-based pooling (e.g.. MEAN) as shown in Equation 2. Such set-based aggregated result for node inherently cannot retain the information related to the number of common neighbors. The same goes for node u. Therefore, we have the following proposition.
Proposition 4. SEAL-type methods cannot guarantee that GNN can use the node labeling features to effectively encode the neighborhood based heuristic information into the node representations.
Propositions and 4 show that SEAL-type methods cannot effectively learn heuristic information embedded in the labeling features of nodes through GNNs. The main reason is that the GNNs
5

---

Under review as a conference paper at ICLR 2023
used in these methods are based the neighborhood information aggregation algorithm (e.g., DGCNN (Zhang et al., 2018) in SEAL (Zhang & Chen, 2018), R-GCN (Schlichtkrull et al., 2018) in GraiL (Teru et al., 2020)). The distinguishing labeling features are mixed and become indistin- guishable after the iterations of set-hased neighborhood aggregation.
Proposition 3. SEye-type methods cannot effectively learn heuristic information for LP.
Proof. We prove this by decomposing the entire algorithm of SEAL-type methods. As shown in Figure 2, the pair-specific subgraph extraction and the node labeling are the operations at the data preparation stage. Nevertheless, the modeling stage, SEAL-type methods still use GNN (c.g., DGCNN in SEAL (Zhang & Chen, 2018)) to learn node-wise representations (i.e., h// Equa- tion 4). Therefore, Proposition 1 and Corollary 1 still hold, and h.)) in Equation 4 lacks heuristic information. Furthermore. READOUT(.) in Equation can hardly capture heuristic information. READOUT(-) is pooling operation over all elements in one set (e.g.. SortPooling in SEAL (Zhang & Chen, 2018)), which is different from the set operation of two sets used in link heuristics in Equa- tion 1. Besides, Propositions 3 and 4 show that the heuristic information in the labeling features of nodes cannot be effectively kept in the learned node representations.
3.3 LIMITATIONS OF OTHER GNN-BASED LP METHODS
Most recently, Zhu et al. (2021) generalize several traditional path-based link heuristics into a path formulation and propose novel neural network NBFNet to approximate the path formulation. Dif- ferent from common GNNs that propagate and aggregate representations of nodes, NBFNet mainly utilizes the representations of edges between two nodes in a candidate link. NBFNet is a benefi- cial attempt to learn pair-wise heuristic information through representation learning. However, it suffers from some issues. First, NBFNet focuses on path-based heuristics like Katz index (Katz, 1953), while neglecting the neighborhood-based heuristics such as CN, RA (Zhou et al., 2009), etc. Second, the algorithm of NBFNet lacks the ability to utilize node-wise information such as node attributes and node embeddings. Besides, Yun et al. (2021) present Neo-GNN that weighted aggre- gates the LP score obtained by neighborhood based heuristics and the score predicted by a GNN. However, Neo-GNN does not path- base- heuristics.
LEARNING HEURISTIC INFORMATION INDEPENDENTLY OF THE GNN
Propositions 1-5 show that traditional link heuristics and GNNs capture different information, and existing GNN- based LP methods fail to effectively learn heuristic infor- mation. We validate these propositions by comparing the LP performance between existing methods and a model that learns heuristic information independently of the GNN learning. To this end, we present a simple yet light LP frame- work ComIIG by Combining link /euristics and the GNN.
Pou
Link predictor
Nyu
CONCAT
evu
COMBINE
CONCAT
4.1
ComHG: A SIMPLE YET LIGHT LP FRAMEWORK
hz
(sro) (0k) eyu e etc.
As shown in Figure 4, ComHG mainly consists of two sep- arate modules and a predictor. The GNN module produces a level link representation by combining the node-level representations of the target pair of nodes. The heuristic module encodes various link heuristics into trainable em- beddings and concatenates these embeddings. Then the link representation and the heuristic embedding are concatenated and passed into predictor for the final prediction.
GNN
Encoder
wise attributes, Node- wise embeddings, etc.
Pair-wise link heuristics: SPD, CN, Jaocard, daamicAdar, etc.
Figure 4: An overview of ComHG.
We emphasize that this work focuses on studying the limi- tations of existing GNN-based LP methods in learning heuristic information. The straightforward ComHG mainly serves as an examiner to validate our analysis. If Propositions 1-5 hold, ComHG would be expected achieve comparable superior performance to all existing I.P methods.

---

Under review as a conference paper at ICLR 2023
GNN module. We use GNN to perform graph representation learning. The GNN can be one of the existing GNNs such as GCN (Kipf& & Welling. 2017). GAT (Veličković et al., 2018), or even MLP. We use node attributes, node embeddings, etc. as the initial node features. The node embeddings are trainable at the training stage. The GNN outputs node-wise representations for all nodes. We then combine the representations of each target pair of nodes into pair-specific link representation. Formally, let L be the index of the last GNN layer. The link representation for node pair (u, u) is
P COMBINE (k!",, nn!
where COMBINE(..)) can be Hadamard production, concatenation, etc.
Heuristic embedding. Independently of the GNN module, ComHG encodes various link heuristics into trainable embeddings and then concatenates these embeddings. Leu be the concatenation of these embeddings for node pair (v, u). We have
Cru CONCAT (SPD)
(CN)
(RA)). Cun
where (SPD) Cou are trained along with the entire framework. Note that ComHG can consider various link heuristics, which is beneficial to tackle the issue that some link heuristics may only be effective some particular graphs (Kovács et al., 2019).
(CN) (RA): is the embedding of SPD, CN, and RA, respectively. These embeddings
Link predictor. In ComHG, concatenate the link representation hvw and the heuristic embedding Con and pass the concatenation into a predictor. Formally, the link likelihood of (v, u) is
Dou PREDICTOR (CONCAT (hour Eow))
We train ComHG using the loss based on negative sampling (Mikolov al., 2013; Hamilton al., 2017), i.e., L = -log( > llgg(1 De(ug), where the node pair (v, u) is positive link sample, (t%, u!) is a negative sample. is the number of negative samples for each positive link.
Computational complexity. ComHG computationally light. For the GNN module, ComHG can take advantage of existing light GNNs (Wu et al., 2019; Chiang et al., 2019). For link heuristics, most heuristics can be computed by matrix addition and multiplication on the adjacency matrix of graph. The complexity of the dense matrix addition and multiplication is O(N2) and O(N3), respectively. In the sparse setting, these complexities can be reduced to O(EE) (Gao et al., 2020), where |E] is the number of edges in graph. The generation of link heuristics in ComHG is light compared to SEAL-type methods (Zhang & Chen, 2018; Teru et al., 2020). In SEAL-type methods, the complexity of subgraph generation can be approximated of the entire graph and h is the highest hop of the subgraph. We can see that the complexity of SEAL-type methods increases exponentially as the hop of the pair-specific subgraph increases.
O(D*())), where D is the degree
In the following subsections, we present our experimental study.
4.2 EXPERIMENTAL SETUP
Datasets. We conduct experiments on four datasets: ogbl-ddi, ogbl-collab, ogbl-ppa, and oghl- citation2 from Open Graph Benchmark (OGB) (Hu et al., 2020). We DO NOT use previous widely-used datasets such as Cora, Citeseer, Pubmed, etc. because these datasets usually suffer from series of issues such as unrealistic and arbitrary data splits, small scale, and data leakage. Especially, Shchur et al. (2018) show that different data splits on such datasets lead to different re- sults in performance comparison among modern graph methods. By contrast, the OGB datasets are collected specifically for the LP task, which cover several realistic applications, span diverse scales (4K- 3M nodes), and come with standard evaluation procedures (Hu et al., 2020).
Comparison methods. We compare ComHG with several mainstream types of LP methods, includ- ing 1) heuristic methods: CN, AdamicAdar (Adamic & Adar, 2003), Katz (Katz, 1953); 2) graph representation learning methods (Non-GNN): Matrix Factorization (MF) (Menon & Elkan, 20, DeepWalk (Perozzi et al., 2014), NodePiece (Galkin et al., 2021): 3) GNN methods: GCN (Kipf & Welling, 2017), GraphSAGE (Hamilton et al., 2017), GAT (Veličković et al., 2018). JKNet (Xu et al.. 2018), LRGA+GCN (Puny et al., 2020), PLNLP (Wang et al., 2021), NBFNet (Zhu et al., 2021) and Neo-GNN (Yun et al., 2021); 4) SEAL-type methods: SEAL (Zhang & Chen, 2018),
7

---

Under review as a conference paper at ICLR 2023
Table 2: Results on sets of OGB LP datasets, Higher is better. The best in each column is in bold. The and indicate the top 1, 2, and 3 results given by previous methods.
ogbl-ddi
ogbl-collab Hits@ (%)
ogbl-ppa Hits 100 (%)
ogbl-citation2 MRR (%)
Method
Hits@20 (%)
CN
17.73 + 0.00
52.24 0.00
27.60 = 0.00
51.47 0.00
AdamicAdar
18.61 +: 0.00
54.09 0.00
32.45 + 0.00
51.89 0.00
Katz
15.32 + 0.00
0.00
53.77 + 0.00
26.28 + 0.00
16.73 0.00
Non-GNN
MF
13.68 4.75
38.86 0.29
32.29 = 0.94
51.86 + 4.43
DeepWalk
26.42 6.10
50.37 0.34
23.02 + 1.63
61.05 + 2.33
NodePiece
24.15 +.04
47.88 0.41
22.85 + 0.94
61.52 1.59
GCN
37.07 1: 5.07
44.75 1.07
18.67 + 1.32
84.74 +: 0.21
GraphSAGE
53.90 + 4.74
48.10
16.55 2.40
82.60 + 0.36
GAT
55.73 + 4.36
42.51
23.82
79.97 1.13
JKNet
57.98 6.88
1.88
2.33
84.28 1.38
GNN
LRGA+GCN
62.30 + 9.12
52.21 0.72
26.12
66.49 + 1.39
PLNLP
90.88 3.13
52.92 0.98
32.38 2.58
84.92 0.29
NBFNet
16.14
51.05 1 0.38
29.64 1 1.03
51.22 6.17
Nco-GNN
63.57 + 3.52
57.52 + 0.371
49.13 = 0.60
87.26 + 0.84
SEAL
30.56 1 3.86
54.71 + 0.49*
48.80 + 3.16
87.67 0.32
GraiL
31.76 + 4.24
54.19 + 0.52
47.25 + 2.84
86.59 + 0.58
SEAL-type
DEGNN
26.63 + 6.82
53.74 0.35
36.48 3.78
60.30 0.61
SUREL
32.31 + 1.15
54.37 0.46
53.23 1.03
88.83 0.18t
ComHG(MLP)
76,83 6.11
54.75 2.52
35.49 = 7.22
85.61 L.83
Ours
ComHG(GCC)
91.38 + 3.08
58.11 1.11
61.24 5.62
88 92.92 0.11
GGAT)(GAT)
92.15 + 3.62
58.03 + 1.21
59.85 + 5.09
88.23 0.38
GraiL (Teru et al., 2020), DEGNN (Li et al., 2020), SUREL (Yin et al., 2022). OGB officially hosts leaderboard". We present the results of these methods reported on this leaderboard the original papers. More experimental settings are provided in the Appendix.
4.3
MAIN RESULTS.
The main experimental results are presented in Table 2. ComHG outperforms all top competitors and achieves state-of-the-ard results on all datasets, demonstrating the effectiveness of the LP approach of learning heuristic information independently of the GNN learning.
As shown in Table 2, GNN-based LP methods usually perform better than non-GNN methods in- cluding heuristic methods and positional sacoding-basee embedding methods like DeepWalk and NodePiece. By comparison, ComHG outperforms all these methods, which could empirically sup- port our Propositions 1, 2 and confirm that GNN-based representation learning and human-defined link heuristics capture different yet effective information for LP.
SEAL-type methods show stronger performance than other previous methods on three datasets, demonstrating their success. However, our Propositions 4 and 5 indicate that such methods cannot effectively learn heuristic information. The results on ogbl-collab could empirically support these propositions. As shown on ogbl-collab in Table 2, heuristic methods including CN, AdamicAdar, and Katz significantly outperform most representation learning methods, indicating that heuristic information critical for LP on this dataset. Meanwhile, SEAL-type methods are only slightly bet- ter (0.62% in SEAL, 0.1% in GraiL, and 0.28% in SUREL) even worse (-0.35% in DEGNN) than the best heuristic AdamicAdar. By comparison, ComHG surpasses the AdamicAdar by 4%. The most likely explanation for this is that SEAL-type methods could not effectively learn the infor- mation equivalent to the link heuristics used in ComHG, considering that ComHG utilizes various link heuristies including SPD, CN, AdamicAdar, etc. Moreover, ComHG significantly exceeds the best SEAL-type methods by 60% and 8% on ogbl-ddi and ogbl-ppa, respectively. All these results demonstrate the superiority of the simple ComHG. The superiority is even more apparent when considering that ComHG is computationally lighter than SEAL-type methods.
leadeereeerrr_ree iikkropp/
8

---

Under review as a conference paper at ICLR 2023
We also evaluate three variants of ComHG where the GNN module uses MLP, GCN (Kipf & Welling, 2017) or GAT (Veličković et al., 2018). Table shows that ComHG(MLP) performs worst across all datasets among three variants, which emphasizes the importance of neighborhood infor- mation aggregation of the GNN, considering the fact that MLP updates each node's representation independently of other nodes. We note that ComHG(GAT) performs worse than ComHG(GCN) three datasets. This is probably because the graphs in the three datasets are large and the dimension of the representations used compute the attention coefficient GAT small, which limits the expressive power of GAT (a large dimension will dramatically increase the memory usage).
4.4 EFFECTS OF LINK HEURISTICS AND THE GNN.
During our experiments, we observe an interesting phenomenon in ComHG that the contributions of link heuristies and the GNN the LP performance vary dramatically according the graph degree. This phenomenon can also be seen in Table 2. For example, on ogbl-ddi with the graph degree of 500, the GNN-based methods such GraphSAGE (Hamilton al., 2017), GAT (Veličković al., 2018), etc. significantly outperform the heuristic methods like CN and AdamicAdar, In contrast, on ogbl-collab with the graph degree of only the simple heuristic CN and AdamicAdar methods perform even better than most representation learning methods.
To further investigate this phenomenon, we study the effects of link heuristics and the GNN in ComHG. Figure shows the results of ComHG using only link heuristics, only the GNN, and both of them. We can see that ComHG only using link heuristics per-
Link heuristirss only
GNNonly
Link heutstics +GNN
80%
22.15
60%
forms better on the sparse graph (i.e., ogbl-collab) but worse on the dense graphs than ComHG only using the GNN. This trend is consistent with the results ob- served in Table 2. Moreover, we find that ComHG using both link heuristics and the GNN yields signifi- cant performance improvement on sparse graphs (i.e., ogbl-collab and ogbl-citation2), while on the dense ogbl-ppa and ogbl-ddi, ComHG only using the GNN can achieve the best LP results.
40%
20%
ogla-coolab
ochi-ctatio22 Degrore 21
ophi- ppa Degrne 73
ogii--tii Deyme: 500
Dayne: 8
Figure 5: Performance of ComHG under different settings.
We explain these results as follows. For link heuristics, most link heuristics like CN, SPD, etc. are effective on sparse graphs but would become indistinguishable between positive and negative candidate links on dense graphs. For GNN-based representation learning, the representation of node in a dense graph would be better learned than that sparse graph since more neighboring nodes would attend the neighborhood aggregation in the dense graph. For example, in spare graph, a node v has only one neighbor w. The learning of the representation of node v in a GNN would only rely on the neighbor Then the learned representation of node would lack the ability to identify the relationships of to most of the other nodes in this sparse graph.
CONCLUSION
In this work, we showed that aggregation-based GNNs inherently lack the model ability to learn the information equivalent to traditional link heuristics. We provided in-depth analysis of why existing GNN- based LP methods cannot effectively learn heuristic information. With the purpose of validating our analysis, we introduced a light LP framework ComHG that learn heuristic infor- mation independently of the GNN learning. The promising results achieved by ComHG empirically confirm our propositions and demonstrate the importance of heuristic information for L.P.
Limitations and future work. We proved our propositions by analyzing the learning mechanism, algorithm architecture, and even an example. The proofs are not presented in a form of rigorous mathematical deduction. This is mainly because the node representations learned by GNNs not easy to interpret. In addition, ComHG developed mainly for validating our analysis. It simply combines the heuristic embedding and link representation separately produced by two modules. We believe that the power integrating heuristic information with the GNN is worth exploring in the future, especially for multiple-node tasks.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Lada A Adamic and Eytan Adar. Friends and neighbors on the web. Social networks, 25())211-230, 2003.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pp- 257-266, 2019.
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems, 2020.
Vijay Prakash Dwivedi, Chaitanya Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.00962 2020.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Mikhail Galkin, Jiapeng Wu, Etienne Denis, and William L Hamilton. Nodepiece: Compo- sitional and parameter-efficient representations of large knowledge graphs. arXiv preprint 1rXiv:2106.1214 2021.
Jianhua Gao, Weixing Ji, Zhaonian Tan, and Yueyan Zhao. A systematic survey of general sparse matrix-matrix multiplication. arXiv preprint arXiv:2002. 2020.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 855-864, 2016.
Will Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning on large graphs. In Advances neural information processing systems, pp. 1024-1034, 2017.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22118 18-22133, 2020.
Kexin Huang, Cao Xiao, Lucas M Glass, Marinka Zitnik, and Jimeng Sun. Skipgnn: predicting molecular interactions with skip-graph networks. Scientific reports, 10(1):1-16, 2020.
Paul Jaccard. Étude comparative de la distribution florale dans une portion des alpes et des jura. Bull Soc Vaudoise Sci Nut, 37:547-579, 1901.
Leo Katz. A new status index derived from sociometric analysis. Psychometrika, 18(1):39-43 -3, 1953.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization, arXiv preprint 1411v:1412.6988. 2014.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations (ICLR), 2017.
István Kováes, Katja Luck, Kerstin Spirohn, Yang Wang, Carl Pollis, Sadie Schlabach, Wenting Bian, Kyum Kim, Nishka Kishore, Tong Hao, et al. Network-hased prediction of protein interactions. Nature communications, 10(1):1-8, 2019.
Ajay Kumar, Shashank Sheshar Singh, Kuldeep Singh, and Bhaskar Biswas. Link prediction tech- niques, applications, and performance: survey. Physica A: Statistical Mechanics and its Appli- cations, 553: 1 24289,, 2020.
Pan Li, Yanbang Wang. Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. Advances in Neural Information Processing Systems, 33:4465 2020.
10

---

Under review as a conference paper at ICLR 2023
Zhifei Li, Yue Zhao, Yan Zhang, and Zhaoli Zhang. Multi-relational graph attention networks for knowledge graph completion. Knowledge- Based Systems, 251:109262, 2022.
Shuming Liang, Zhidong Li, Bin Liang, Yu Ding, Yang Wang, and Fang Chen. Failure prediction for large-scale water pipe networks using gnn and temporal failure series. In Proceedings of the 30th ACM International Conference Information & Knowledge Management, pp. 3955-3964, 2021.
David Liben-Nowell and Jon Kleinberg. The link-prediction problem for social networks. Journal of the American society for information science and technology, 1807):101--003 2007.
Víctor Martínez, Fernando Berzal, and Juan-Carlos Cubero. A survey of link prediction in complex networks. ACM computing surveys (CSUR), 19(4):1-33, 2016.
Aditya Krishna Menon and Charles Elkan. Link prediction via matrix factorization. In Joint eu- ropean conference on machine learning and knowledge discovery in databases, pp. 437-452. Springer, 2011.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado, and Jeff Dean. Distributed representa- tions of words and phrases and their compositionality. Advances in neural information processing systems, 26, 2013.
Bryan Perozzi, Rami AI-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701-710, 2014.
Omri Puny, Heli Ben-Hamu, and Yaron Lipman. Global attention improves graph networks gener- alization. arXiv preprint X10::00066008466 2020.
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. European semantic web conference, pp. 593-607. Springer, 2018.
Rico Sennrich, Barry Haddow, and Alexandra Birch. Neural machine translation of rare words with subword units. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). pp. 1715-1725, 2016.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv: 1.0.0888, 2018
Damian Szklarczyk, Annika L. Gable, David Lyon, Alexander Junge, Stefan Wyder, Jaime Huerta- Cepas, Milan Simonovic, Nadezhda Doncheva, John H Morris, Peer Bork, et al. String vl1: protein-protein association networks with increased coverage, supporting functional discovery in genome-wide experimental datasets. Nucleic acids research, 47D0)))6677-611, 2019.
Komal Teru, Etienne Denis, and Will Hamilton. Inductive relation prediction by subgraph reasoning. In International Conference on Machine Learning, pp. 9448-9457. PMLR, 2020.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. International Conference on Learning Representations, 2018.
Kuansan Wang, Zhihong Shen, Chiyuan Huang, Chieh-Han Wu, Yuxiao Dong, and Anshul Kanakia. Microsoft academic graph: When experts are not enough. Quantitative Science Studies, 1(1):396- 413, 2020.
Zhitao Wang, Yong Zhou, Litao Hong, Yuanhang Zou, and Hanjing Su. Pairwise learning for neural link prediction. arXiv preprint arXiv:2112.029336 2021.
David S Wishart, Yannick D Feunang, An C Guo, Elvis J Lo, Ana Marcu, Jason R Grant, Tanvir Sajed, Daniel Johnson, Carin Li, Zinat Sayeeda, et al. Drugbank 5.0: a major update to the drugbank database for 2018. Nucleic acids research, 46(D1):D1074-D1003 2018.

---

Under review as a conference paper at ICLR 2023
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In International conference on machine learning. pp- 6861-6871. PMLR, 2019.
Le Wu, Xiangnan He, Xiang Wang, Kun Zhang, and Meng Wang- A survey neural recommenda- tion: From collaborative filtering to content and context enriched recommendation. arXiv preprint 1rXiv:2/04.13030, 2021.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning graphs with jumping knowledge networks. In International conference on machine learning, pp. 5453-5462. PMLR, 2018.
Haoteng Yin, Muhan Zhang, Yanbang Wang, Jianguo Wang, and Pan Li. Algorithm and system co-design for efficient subgraph-based graph representation learning. arXiv:2202.13558, 2022.
arXiv preprint
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Yan Liu. Do transformers really perform badly for graph representation? Advances Neural Information Processing Systems, 34, 2021.
Seongjun Yun, Scoyoon Kim, Junhyun Lee, Jaewoo Kang, and Hyunwoo J Kim. Neo-gnns: Neigh- borhood overlap-aware graph neural networks for link prediction. Advances in Neural Information Processing Systems, 04:13663-13694, 2021.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in Neural Information Processing Systems, 31:5165-5175. 2018.
Muhan Zhang. Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Proceedings of the AAAI conference on artificial intelli- gence, volume 32, 2018.
Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: A theory of using graph neural networks for multi-node representation learning. Advances in Neural Information Processing Systems, 34:9061-9073, 2021.
Tao Zhou, Linyuan LU, and Yi-Cheng Zhang. Predicting missing links via local information. The European Physical Journal B, 71(4):623 ([3):623-630, 2009.
Zhaocheng Zhu, Zuobai Zhang, Louis-Pascas Xhonneux, and Jian Tang. Neural bellman-ford ford net- works: general graph neural network framework for link prediction. Advances in Neural Infor- mation Processing Systems, 34, 2021.
12

---

Under review as a conference paper at ICLR 2023
A
RELATED WORK
In this section, we briefly review several mainstream types of Link Prediction (I.P) methods. Most methods used in performance comparison in our experiments are also described here.
Heuristic methods. Traditional link heuristics are usually defined based on the number of the neighbors paths between pair of nodes (Martínez et al., 2016). Most heuristic LP methods are developed for specific applications and their effectiveness has been confirmed in real-world tasks (Liben-Nowell & Kleinberg. 2007; Martínez et al., 2016; Kovács et al., 2019). In general, heuristic methods are interpretable (i.c., a link heuristic describes a specifie fact or hypothesis to interpret a statistical pattern in link observations) and inductive (i.e., most link heuristics are independent of any particular node, and thus can naturally generalize to unseen nodes in the inductive LP (Zhu et al., 2021)). However, heuristic LP methods suffer from several issues. First, since many link heuristics are designed for specific graph applications, they may perform well only on a particular type of graphs (Kováes al., 2019). Second, their model capacity limited, considering that they mainly focus on the topological properties between target pairs of nodes but rarely leverage node features (Zhang & Chen, 2018).
Node embedding methods based on positional encoding, Node embedding methods are one class of graph representation learning methods. Such methods encode positional relationships between nodes into node embeddings. The similarity of nodes in the embedding space reflects the semantic similarity of nodes in the graph. These methods can partially encode the link heuristic information into node embeddings. Two nodes would have more similar embeddings if these two nodes are close to each other (path-based based information) and have many common neighbors (neighborhood- based information) than the two nodes that are far apart. Following the word embedding method (Mikolov et al., 2013), the models such as Deepwalk (Perozzi et al., 2014), Node2vec (Grover & Leskovec, 2016), etc. learn node embeddings by treating the nodes words and treating the sequences of modes generated based on links as sentences. Most recently, inspired by subword tokenization used in NLP (Sennrich et al., 2016), NodePiece (Galkin et al., 2021) explores parameter-efficient node embedding techniques and presents an anchor-based method to learn node embeddings. However, all these methods typically train embeddings in an unsupervised learning manner. Solely using such node embeddings for LP empirically perform poorly compared to other representation learning methods (e.g.. GNNs) and sometimes even worse than heuristic methods (Wang et al., 2021).
Graph neural networks. Recently, GNNs have demonstrated effectiveness in diverse real-world graph-based applications (Liang et al., 2021; Huang et al., 2020; Ying et al., 2021). number of GNN models have been proposed. GCN (Kipf & Welling, 2017) is graph convolutional network that learns node representations by summing the normalized representations from the first-order neighbors. GraphSAGE (Hamilton et al., 2017) samples and aggregates representations from local neighborhoods with pooling methods like MEAN, MAX, LSTM, etc. GAT (Veličković et al., 2018) introduces attention-basse GNN architecture. LRGA (Puny et al., 2020) incorporates Low- Rank global attention module to GNNs for improving their generalization power. These GNNs have demonstrated powerful LP performance by simply combining the node-level representations of two nodes in a candidate link into link representation. Wang et al. (2021) present a framework PLNLP that jointly uses the node-wise representations learned by a GNN. node embeddings obtained by positional encoding methods, and even the link representations produced by SEAL-type methods.
SEAL-type methods. SEAL-type methods have shown superior performance among existing LP approaches (Hu et al., 2020: Teru et al., 2020). SEAL (Zhang & Chen, 2018) extracts local en- closing subgraph for each candidate link and uses a GNN (Zhang et al., 2018) to classify these subgraphs for I.P. GraiL. (Teru et al., 2020) is developed for inductive knowledge graph reasoning. It a method similar to SEAL but it replaces SortPooling readout with MEAN -poolin.. DEGNN (Li et al., 2020) proposes a distance encoding GNN that comes with both theoretical guarantees and empirical efficiency. For LP, DEGNN uses a SEAL-type strategy but a different labeling technique. SUREL (Yin et al., 2022) proposes an algorithmic technique to improve the computational efficiency of subgraph generation in SEAL-type methods, where graph structures are decoupled into sets of walks that are used to generate pair- sair-specific subgraphs.
These LP methods have achieved great success. However, our analytical and experimental results show that these existing methods lack the model ability to effectively capture heuristic information.
13

---

Linux Under review as a conference paper at ICLR 2023
B MORE ON THE EXPERIMENTS
IMPLEMENTATION DETAILS
We implement ComHG using Py Torch and PyTorch Geometric (Fey & Lenssen, 2019). The model trained with Adam optimizer (Kingma & Ba, 2014). The learning rate is decayed following the ExponentialL method. We conduct all experiments for ogbl-ddi and ogbl-collab machine with 14-core CPU, 192G RAM, and NVIDIA Quadro P6000 (24G), and for ogbl-ppa and ogbl-citation2 on machine with 32-cores CPU, 512G RAM and NVIDIA A100 (40G). Table lists the configurations of ComHG for the best performance. We provide our code for reproducing the results at https://githubb.r www.astromingn/ooooe.
Table 3: Configurations of ComHG for the best performances.
ogbl-ddi
egbl-collab
ogbl-ppa
ogbl-citation2
GNN module
GAT
GCN
GCN
GCN
GNN layers
2
2
2
predictor
MLP
MLP
MLP
MLP
predictor layer
3
heuristics
SPD,CN.AA
SPD,AA
heuristic embedding dim
32
32
node embedding dim
512
256
Ir
0.003
0.002
0.001
0.001
Ir decay gamma
0.995
0.997
0.99
0.995
dropout rate
0.3
0.3
0.3
0.25
gradient clip norm batch size
5
10
5
100000
70000
100000
15000
B.2 DATASETS
In this work, we do not compare the LP performance among methods on previous small graph datasets such Cora, Citeseer, Pubmed (Zhu et al., 2021). This is mainly because the different split proportions of train, validation, and test sets these datasets would lead to dramatically dif- ferent comparison results (Dwivedi al., 2020). We refer readers to (Dwivedi et al., 2020) for more details about the issues of these traditional datasets.
Table Statistics of OGB LP datasets.
Dataset
#Nodes
#Edges
#Degree
ogbl-ddi
4, 267
1,334, 889
500
ogbl-collab
235, 868
1, 1,285, 465
ogbl-ppa
576, 289
30, 326, 273
73
ogbl-citation2
2, 927, 963
30, 561, 187
21
As alternative, conduct experiments four L.P datasets from OGB (Hu al., 2020). The statistics of datasets are summarized in Table 4.
ogbl-ddi is a homogeneous, unweighted, undirected graph built based a drug-drug interaction network (Wishart et al., 2018). In this graph, node represents drug and an edge describes an interaction between splits edges into train, validations, and test sets according to what proteins those drugs target in the body. The set composed of drugs that predominantly bind to different proteins from drugs in the train and validation sets, thereby evaluating the generalization capacity of the model for practically useful I.P.
drugs. The nodes in this graph do not have any features. OGB officially
ogbl-collab is an undirected graph extracted based on a collaboration network between authors from MAG (Wang et al., 2020). The nodes represent authors and the edges indicate the collabo- ration between authors. Every node has 128-dimensions features obtained by averaging the word embeddings papers that are published by the authors (Hu et al., 2020). Each edge comes with attribute, i.e., the year when the co-authored paper is published. The task is predict future author collaborations. The data is split according to time, aiming to simulate realistic application in collaboration recommendation.
14

---

Under review as a conference paper at ICLR 2023
ogbl-ppa is undirected, unweighted graph. Nodes represent proteins from 58 different species, and edges are biologically meaningful associations between proteins (Szklarezyk et al., 2019). The node features are obtained based the species. OGB splits the data according to the type of protein associations, which meets the practical needs.
ogbl-citation2 is directed graph built based the citations between subset of papers extracted from MAG (Wang et al., 2020). A node a paper and has 128-dimensional features obtained by summarizing word embeddings of its title and abstract. A directed edge indicates that one paper cites another. The data is split according to time for the purpose of simulating realistic application in citation recommendation.
15


Reviews:
[{"review_id": "yhkigXtF3ic", "reviewer": "Reviewer_iMgJ", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents a simple yet light framework, ComHG, to predict the existence of a link by directly combining embeddings of link heuristics (e.g., Adamic Adar, Katz, RA) and the representations from a GNN. The authors further analyze that existing SEAL-type GNNs cannot effectively capture heuristic information. Experiments on four Open Graph Benchmark datasets show the effectiveness of ComHG for link prediction compared to existing GNN-based methods and link heuristics.", "summary_of_the_review": "This paper presents a simple yet light framework for link prediction by directly combining embeddings of link heuristics and the representations from a GNN. The presentation of the paper is easy to follow, but the technical novelty is limited. ", "strength_and_weaknesses": "Strengths\n\n- The problems of GNN-based LP methods were analyzed through the comparison between the existing GNN-based LP methods and link heuristics.\n- Experiments show superior performances of ComHG compared to existing GNN-based methods and link heuristics.\n\nWeaknesses\n\n- My main concern is the lack of novelty. Rather than proposing a GNN that can learn link heuristics, the authors simply embed the results of link heuristics and leverage them for link prediction by concatenating with representations produced by GNNs.\n\n- Insufficient explanation of the proposed method. The author mentioned that embeddings of each heuristic method (SPD, CN, and RA) are fed into ComHG as inputs, but there is no specific explanation of how each method is embedded.\n\n- The performance of GNN only in the ablation study (Fig 5.) and the performance of baselines using only GNNs (e.g., GCN, GraphSAGE, JKNet, GAT) are inconsistent. Specifically, the performances of only using GNN in ogbl-ppa and ogbl-ddi datasets are 61.24 and 92.15, respectively while performances of the baselines using only GNNs are under 24 and 58. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "aH2hgPTC2p", "reviewer": "Reviewer_gAm5", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors question whether these methods can effectively learn the information equivalent to link heuristics such as Common Neighbors, Katz index, etc. (we refer to such information as heuristic information in this work). The authors show that link heuristics and GNNs capture different information. Link heuristics usually collect pair-specific information by counting the involved neighbors or paths between two nodes in a candidate link, while GNNs learn node-wise representations through a neighborhood aggregation algorithm in which two nodes\nin the candidate link do not pay special attention to each other.", "summary_of_the_review": "Please refer to the above points for improvements.", "strength_and_weaknesses": "Pros: The authors intuitively show that traditional link heuristics and GNNs capture different information. They analyze this finding in theory and conduct extensive experiments to distinguish the superior performance of their proposed method.\n\nCons: Authors mainly analyze the subgraph based graph neural networks and point out their limitations. There are also node-wise embedding based graph neural networks which are more efficient and effective than the subgraph based ones. The authors are suggested to discuss them in the motivation. Moreover, efficiency is another important metric for evaluation link prediction systems. The authors are suggested to evaluate the inference efficiency of their method.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "LW034cNU5w", "reviewer": "Reviewer_HJFA", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors proposes if GNNs (which typically take into account neighborhood information and aggregates then, can also utilize heuristic measures like pairwise node information for link Prediction tasks and whether that improves vanilla GNN for link Prediction. The author states through experiments that a combination of link heuristics and GNN-based neighborhood aggregation techniques results in comparatively better link Prediction than only vanilla GNN and heuristic-based models. \n", "summary_of_the_review": "I elaborate the strengths and weaknesses here:\n\nStrengths\n+ The background setting is established well for the importance of Link Prediction and its wide applications.  The authors have performed experiments on large datasets (typically Order of millions in nodes) and they have showcased empirically the comparative performance of their proposed methods w.r.t GNN based Link heuristic methods (like SOTA - SEAL), GNN based methods (SOTA - GraphSage).\n+ The ablation study at the end of the effect of link heuristics and GNN modules in the proposed method is well investigated and clearly shows how sparsity of the graph effects each of the components contribution. The authors provide a strong reasoning behind this phenomenon and its empirically showcased.\n+ Model complexity wise the author theoretically shows how their proposed method has less complexity than SOTA SEAL method.\n\n\nWeakness:\n\n-  Missing important baselines https://arxiv.org/abs/2110.04375, https://arxiv.org/abs/2012.08974\n\n- The question raised in the introduction part is valid but the authors do not clearly convey what methods like SEAL fail to capture which traditional link based heuristics capture. That information could setup a more strong motivational setting for the rest of the paper to follow . Why is it important to capture link based heuristics ? Does it show significant improvement than GNNs which fail to capture such info. If so any empirical reference or short writing as to why it is so. \n\n- The author mentions that through experimental results they are able to show the gap why link based heuristics are important for LP. It would have been nice to showcase the gap also theoretically. In link heuristics only a few classical methods are mentioned while other important link based heuristics like simrank / simrank* and it's variations are not mentioned. \n\n- The generalization into the set structure is a bit unconvincing like in typical simrank computations which takes into account recursiveness of its computation for all its neighbours. The fixed one hop is only assumed. Also the definition for setop nullifies there. \n\n- Proposition I. states that GNNs doent take into account the attenetion for a particular node or pairwise. However, models like GAT have been proposed to take that into account. What if GNNs that take into account edge reperesnetations like NBFNet ( although here it's mentioned for only node level representationsl) then do we require such heuristics any more ? What if we had hybrid of NBFNet edge emebeddings along with traditional node representation based GNNs. Does that solve the problem? Did the authors perform experiments on those? \n\n- Proposition I  is not convincing.  Do the authors share any examples where the pooling information over elements in one set don't contribute? A pooling information over a set of neighborhoods of a particular node will also have the inherent pooling information of the individual neighborhood nodes via message passing. Does that information. Not similar in essence to link Prediction tasks. If not can it theoretically be shown or via suitable examples. \n\n- Proposition II also lacks the same mathematical rigour and explanation as to why combine operation doesn't capture the same info as compared to a set intersection. \n\n- Proposition III is well explained via an example. However we can use weighted attentetion or weighted mean in the pooling strategy or other pooling strategies can also be used to countereffect the loss in information. Only SEAL GNN based LP was analysed. But not any other GNN based LP. For the propositions to hold it needs to be shown for all GNN based LPs and should be mathematically motivated as to which information gets missed if we have a clever pooling strategy. Also empirical results should be cited in those propositions stating whether SEAL based LP performs poorly for certain examples. \n\n- Does combHGs heuristic embedding not lose information since it basically a concatenation of node embeddings and as per previous propositions it should lose some information. The node embeddings might change later on due to the GNN pooling. It's not clear. \n\n- As per table 2 if GNN based LP produces better than traditional LPs then it contradicts the proposition that GN based LP fail to capture those heuristics which is a fundamental notion of this paper ( why such heuristics are important).\n\n- I think Hits are not so crucial metric in the context of LP, it does not capture the recall. MAP is better.\n", "strength_and_weaknesses": "Strengths:\n+ Good literature survey\n+ Experiments are performed with due diligence\n\nWeaknesses:\n- Several issues with experiments (see the detailed review)\n- Some important baselines (https://arxiv.org/abs/2110.04375, https://arxiv.org/abs/2012.08974) are missing\n- No code", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Dt3EThD0Slb", "reviewer": "Reviewer_ugPY", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose a light link prediction framework ComHG by combining link heuristics and the GNN. Link heuristics in CombHG are encoded into trainable embeddings and combined with the representations produced by a GNN.", "summary_of_the_review": "The authors are encouraged to address the issues raised in the above.", "strength_and_weaknesses": "Strengths of the paper:\nWell-written and easy to follow.\nExperiments are conducted on a number of datasets.\n\nWeaknesses and main concerns of the paper:\n\nThe authors claim that “the information captured by link heuristics is different from that embedded in the node representations learned by GNNs.”. What’s the relationship between the information by link heuristics and GNNs then? Are they independent to each other?\n\nIt is unclear why the authors only focus on link prediction but not other tasks such as node classification, as the inferred embeddings can be utilized in other tasks. \n\nIt is unclear if the link heuristics can be simply defined as in Equation (1).\n\nThe contribution of the proposed model, ComHG, is marginal, which is straightforward and built based on traditional GNN model and a traditional Encoder. In terms of GNN model and the Encoder models, the contribution is marginal.\n\nOther baselines can be taken into account for comparisons such as:\nBouritsas et al., Improving graph neural networks expressivity via subgraph isomorphism counting, TPAMI, 2022.\nFang et al., Structure-aware random fourier kernel for graphs, in NeurIPS 2021.\n\nAre there other information that are different from “link heuristic” and “node-wise attributes” that can be integrated into ComHG?\n\nOther minor concerns:\nThe first two paragraphs in the introduction section can be deleted, as most machine learning researchers have the background knowledge. (up to you)\n\nWhat’re the motivations to investigate the problem: whether the GNN-based LP methods can effectively learn the information equivalent to link heuristics for LP? Can the answers and analysis inspire research on other topics?\n\nCan we use graph neural network distillation techniques to address the task?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject