Revisiting Link Prediction: a data perspective
Authors: Haitao Mao
Juanhui Li
Harry Shomer
Bingheng Li
Wenqi Fan
Yao Ma
Tong Zhao
Neil Shah
Jiliang Tang
Venue: ICLR 2024 poster (2024)
Keywords: Link Prediction;Graph Neural Network
Primary area: learning on graphs and other geometries & topologies
TL;DR: We provide in-depth analysis on link prediction from a dataset perspective.

Abstract: Link prediction, a fundamental task on graphs, has proven indispensable in various applications, e.g., friend recommendation, protein analysis, and drug interaction prediction. However, since datasets span a multitude of domains, they could have distinct underlying mechanisms of link formation. Evidence in existing literature underscores the absence of a universally best algorithm suitable for all datasets. In this paper, we endeavor to explore principles of link prediction across diverse datasets from a data-centric perspective. We recognize three fundamental factors critical to link prediction: local structural proximity, global structural proximity, and feature proximity. We then unearth relationships among those factors where (i) global structural proximity only shows effectiveness when local structural proximity is deficient. (ii) The incompatibility can be found between feature and structural proximity. Such incompatibility leads to GNNs for Link Prediction (GNN4LP) consistently underperforming on edges where the feature proximity factor dominates. Inspired by these new insights from a data perspective, we offer practical instruction for GNN4LP model design and guidelines for selecting appropriate benchmark datasets for more comprehensive evaluations.

Published as a conference paper at ICLR 2024
REVISITING LINK PREDICTION: A DATA PERSPECTIVE
Haitao Mao': Juanhui Li', Harry Shomer', Bingheng LiP, Wenqi Fan Yao Ma², Tong Zhao², Neil Shah and Jiliang Tang' Michigan State University
The Chinese University of Hong Kong, Shenzhen 3 Hong Kong Polytechnic University
Rensselaer Polytechnic Institute $ Snnap Inc.
(haitaoma, ii juanh1, shomerha, tangjili Emmuu.edu libingheng@cull cuhk. edu on wenqi. fanêpol yu. yu. edu. hk, may pay130rpp 30rpi edu, (tzhao, nshah @snap. com
ABSTRACT
Link prediction, a fundamental task on graphs, has proven indispensable various applications, e.g., friend recommendation, protein analysis, and drug interaction prediction. However, since datasets span a multitude of domains, they could have distinct underlying mechanisms of link formation. Evidence in existing literature underscores the absence of a universally best algorithm suitable for all datasets. In this paper, we endeavor explore principles of link prediction across diverse datasets from a data-centric perspective. We recognize three fundamental factors critical to link prediction: local structural proximity, global structural proximity, and feature proximity. We then unearth relationships among those factors where (i global structural proximity only shows effectiveness when local structural proximity is deficient. (ii) The incompatibility can be found between feature and structural proximity. Such incompatibility leads to GNNs for Link Prediction (GNN4LP) consistently underperforming on edges where the feature proximity factor dominates. Inspired by these new insights from a data perspective, we offer practical instruction for GNN4LP model design and guidelines for selecting appropriate benchmark datasets for more comprehensive evaluations.
INTRODUCTION
Graphs are essential data structures that use links to describe relationships between objects. Link prediction, which aims find missing links within a graph, fundamental task in the graph domain. Link prediction methods aim to estimate proximity between node pairs, often under the assumption that similar nodes are inclined to establish connections. Originally, heuristic meth- ods (Zhou et al., 2009; Katz, 1953) were proposed to predict link existence by employing handcrafted proximity features to extract important data factors, e.g., local structural proximity and feature proximity. For example, Common Neighbors(CN) algorithm (Zhou et al., 2009) assumes that node pairs with more overlapping between one-hop neighbor nodes are more likely to be connected. To mitigate the necessity for handcrafted features, Deep Neural Networks utilized to automatically extract high-quality proximity features. In particular, Graph Neural Networks (GNNs) (Kipf & Welling, 2017; 2016; Hamilton al., 2017) become increasingly popular owing to their excellence in modeling graph data. Nonetheless, vanilla GNNs fall short in capturing pairwise structural infor- mation (Zhang al., 2021: Liang et al., 2022), e.g., neighborhood-overkkg modest performance in link prediction. To address these shortcomings. Graph Neural Networks for Link (oN.iiionGGNNNP)))))) proposed to incorporate different inductive biases revolving pairwise structural information.
features, achieving
& Chen, 2018; Wang al., 2022: Chamberlain et al., 2023) are
New designs on GNN4LP models strive to improve vanilla GNN to capture diverse pairwise data patterns, e.g., local structural patterns (Yun et al., 2021; Wang et al., 2023), the number of paths (7hu et al., 2021b), and structural position (Zhang & Chen, 2018). These models have found wide applicability across myriad of real-world graph problems from multiple domains, e.g., paper recommendation, drug interaction prediction, and protein analysis (Kovács et al., 2019; Hu et al., 2020). A recent benchmark (Li et al., 2023) evaluates the performance of GNN4LP models datasets from diverse domains, and finds performance disparity as there is no universally best- rest-performing
Work was partially done while the author was research assistant The Hong Kong Polytechnic University.

---

Published as a conference paper at ICLR 2024
GNN4LP model, observing that even vanilla GCN can achieve best performance on certain datasets. (AbuOda et al., 2020; Chakrabarti, 2022) reveal similar phenomena across heuristic algorithms. We conjecture the main reasons for such phenomena are that (i) From model perspective, different models often have preferred data patterns due to their distinct capabilities and inductive biases. (ii) From data perspective, graphs from different domains could originate from distinct underlying mechanisms of link formation. Figure illustrates this disparity in the number of CNs on multiple benchmark datasets', Notably, edges in the OGBL-PPA and OGBL-DDI datasets tend to have many CNs. Considering both model and data perspectives, performance disparity becomes evident where certain models perform well when their preferred data patterns align with particular data mechanisms on particular datasets, but others do not. This suggests that both model and data perspectives are significant to the success of link prediction. While mainstream research focuses on designing better models (Zhang & Chen, 2018; 8; Zhang et al., 2021), we opt to investigate a data-centric perspective on the development of link prediction. Such a perspective can provide essential guidance on model design and benchmark dataset selection for comprehensive evaluation.
To analyze link prediction from a data-centric perspective, we must first understand the underlying data factors across different datasets. To achieve these goals, our study proceeds as follows: (i) Drawing inspiration from well-established literature (Huang et al., 2015; McPherson et al., 2001) in network analysis, we pinpoint three key data factors for link prediction: local structural proximity, global structural proximity, and feature proximity. Comprehensive empirical analyses confirm the importance of these three factors. (ii) In line with empirical analysis, we present latent space model for link prediction, providing theoretical guarantee on the effec- tiveness of the empirically identified data factors. (iii) We conduct an in-depth analysis of relationships among data factors on the latent space model. Our analysis reveals the presence of incom- patibility between feature proximity and local structural proximity. This suggests that the occurrence of both high feature similarity and high local structural similarity within a single edge rarely happens. Such incompatibility sheds light on an overlooked vulnerability in GNN4LP models: they typically fall short in predicting links that primarily arise from feature proximity. (iv) Building upon the systematic understandings, we provide guidance for model design and benchmark dataset selection, with opportunities for link prediction.
Pubmed
ogbi ppa ogbl-ddi
ogbl-colleib
1.0
Propotion
0.4
0.2
(0-1)
(1-3)
(3-10)
(0-25)125-1m0)
Figure 1: Distribution disparity of
Common Neighhors across datasets.
2 RELATED WORK
Link prediction aims to complete missing links in graph, with applications ranging from knowledge graph completion (Nickel et al., 2015) to e-commerce recommendations (Huang et al., 2005). While heuristic algorithms with deep learning techniques have shown superior performance in recent years.
once predominant, Graph Neural Networks for Link Prediction (GNN4LP)
Heuristic algorithms, grounded in the principle that similar nodes more likely connect, encompass local structural heuristics like Common Neighbor and Adamic Adar (Adamic & Adar, 2003), global structural heuristics like Katz and SimRank (Jeh & Widom, 2002; Katz, 1953), and feature proximity heuristics(Nicke) et al., 2014; Zhao et al., 2017) integrating additional node features.
GNN4LP built on basic GNNs (Kipf & Welling, 2016; 2017) which learn single node structural representation by aggregating neighborhood and transforming features recursively, equipped with pairwise decoders. GNN4LP models augment vanilla GNNs by incorporating more complicated pairwise structural information inspired by heuristic methods. For instance, NCNC (Wang et al., 2023) and NBFNet (Zhu et al., 2021b) generalize CN and Katz heuristics with neural functions to incorporate those pairwise information, thereby achieving efficiency and promising performance. A more detailed discussion on heuristics, GNNs, and principles in network analysis is in Appendix A.
Mooe evidence on other data properties can he found in Appendix F.
2

---

Published as a conference paper at ICLR 2024
3 MAIN ANALYSIS
In this section, we conduct analyses to uncover the key data factors for link prediction and the underlying relationships among those data factors. Since underlying data factors contributing to link formation are difficult to directly examine from datasets, we employ heuristic algorithums as a lens reflect their relevance. Heuristic algorithms calculate similarity scores derived from different data factors to examine the probability of whether two nodes should be connected. They are well- suited for this analysis they are simple and interpretable, rooted in principles from network analysis (Murase et al., 2019; Khanam et al., 2020). Leveraging proper-selected heuristic algorithms and well estaallsttl literature network analysis, we endeavor to elucidate the underlying data factors for link prediction.
Organization. Revolving on the data perspective for link prediction, the following subsections are organized as follows. Section 3.1 focuses on identifying and empirically validating the key data factors for link prediction using corresponding heuristics. In line with the empirical significance of those factors, Section 3.2 introduces theoretical model for link prediction, associating data factors with node distances within latent space. Links are more likely to be established between nodes with small latent distance. Section 3.3 unveils the relationship among data factors building upon the theoretical model. We then clearly identify an incompatibility between local structural proximity and feature proximity factors. Specifically, incompatibility indicates it is unlikely that the occurrence of both large feature proximity and large local structural proximity within a single edge, Section 3.4 highlights overlooked limitation of GNN4LP models stemming from this incompatibility.
Preliminaries & Experimental Setup. 9 = (V, E) is an undirected graph where and & are the set of N nodes and |&] edges, respectively. Nodes can be associated with features X Rgnxd, where d is the feature dimension. We conduct analysis on CORA, CITESEER, PUBMED, OGBL-COLLAB, OGBL-PPA, and DDBL-DDI datasets (Hu al., 2020; McCallum al., 2000) with the same model setting recent benchmark (Li et al., 2023). Experimental and dataset details are in Appendix K and J, respectively.
3.1 UNDERLYING DATA FACTORS ON LINK PREDICTION
Motivated by well-established understandings network analysis (Daud et al., 2020; Wang & Le, 2020; Kumar et al., 2020) and heuristic designs (Adamic & Adar, 2003; Katz, 1953), conjecture that there are three key data factors for link prediction.
(1) Local structural proximity (LSP) (Newman, 2001) corresponds to the similarity of immediate neighborhoods between two nodes. The rationale behind LSP is rooted in the principle of triadic closure (Huang al., 2015), which posits that two nodes with more common neighbors have higher probability of being connected. Heuristic algorithms derived from the LSP perspective include CN, RA, and AA (Adamic & Adar, 2003), which quantify overlap between neighborhood node sets. We mainly focus on common neighbors (CN) in the following discussion. The CN score for nodes i and is calculated as [T) (())), where I'(-) denotes the neighborhood set. More analysis on other related heuristics revolving around LSP, c.g., RA, AA, can be found in Appendix C.5.
(2) Global structural proximity (GSP) (Katz, 1953; Jeh & Widom, 2002) goes beyond immediate neighborhoods between two nodes by considering their global connectivity. The rationale behind GSP that two nodes with more paths between them have a higher probability of being connected. Heuristic algorithms derived from GSP include SimRank, Katz, and PPR (Brin & Page, 2012), to extract the ensemble of paths information. We particularly focus on the Katz heuristic the following discussion. The Katz score for nodes and j is calculated as E X Illpahs (i. where
A < 1 is damping factor, indicating the importance of the higher-order information. |paths (4) (i, counts the number length-/ paths between and j.
(3) Feature proximite ty (FF) (Murase et al., 2019) corresponds to the feature similarity be- tween nodes. The rationale behind FP is the principle of feature homophily (Khanam et al., 2020; Evtushenko & Kleinberg, 2021), which posits two nodes with more similar individual characteristics have a higher probability of being connected. There are many heuristic algorithms (Tang et al., 2013; Zhao et al., 2017) derived from the FP perspective. Nonetheless, most of them combine FP in addition to the above structural proximity, leading to difficulties for analyzing FP solely. Hence, we derive a simple heuristic called feature homophily (FH) focusing only feature proximity solely for ease of
3

---

Published as a conference paper at ICLR 2024
GSP
0.0015
0.0021
CSP
0.85
0.00035
0.00013
CSP
CSP
0.54
3.3e
0.0099
0.8
0 002
LSP
O. 0.00085
0
0.00017
LSP
4.2c-05
0.52
LSP
2:5e-07
0.65
F8
0.0023
00000
0.63
0.0002
0001
GSP
LSP
FP
GSP
LSP
FP
GSP
LSP
GSP
LSP
PUBMED
(b) OGBL-COLLAB
(c) OGBL--DI
(d) OGBL-PPA
Figure 3: Overlapping ratio between top-ranked edges on different heuristic algorithms. Diagonals are the comparison between two heuristics within the same factor, while others compare heuristics from different factors. FP is ignored OGBL-DDI and OGBL-PPA due no or weak feature quality, MRR selected as the metric. More results on hit@ 10 metric can be found in Appendix D.
analysis. The FH score between nodes i and j is calculated as dis(x;, where H. corresponds to the node feature, and dis(-) is a distance function. We particularly focus on FH with cosine distance function in the following discussion. Notably, details on all the heuristics mentioned above can be found in Appendix A and B. To understand the importance of those data factors, we aim to answer the following questions: (i) Does each data factor indeed play key role in link prediction? (ii) Does each factor provide unique information instead of overlapping information?
We first concentrate on examining the significance of each afore- mentioned factor for link prediction, based on well-established principles from network analysis. We exhibit the performance of heuristic algorithms in Figure 2. We make the following observations: (i) For datasets from the academic domain, CORA, CITESEER, PUBMED, and OGBL-COLLAB, we find that heuristics for different factors can achieve satisfying performance. The Katz corresponding the GSP factor consistently outperforms other heuristics. Explanations of the phenomenon are further presented in the following Section 3.3. (ii) For OGBL-DDI and OGBL-PPA datasets, CN heuristic corresponding to the LSP fac- tor consistently performs best while FH performs poorly. We conjecture that this is due to low feature quality. For instance, node features for OGBL--PA are one-hot vector corresponding to different categories. (iii) No single heuristic algorithm consistently outperforms across all datasets, indicating data disparity; detailed discussions are in Section 4.2. The effectiveness of heuristics is very data-specific which further highlights the importance of investigating link prediction from data perspective.
LSP
GSP
FP
60
Hit
40
20
Cora
Citesaer
Pubmed
collab
ddi
ppa
Figure 2: Performance of heuristics corresponding to different factors.
We further investigate the relationship between heuristics from the same and different data factors. Details on the heuristic selection are in Appendix B. This includes whether heuristics from the same data factor provide similar information for link prediction and whether those from different data factors could offer unique perspectives. To this end, we examine disparities in predictions among different heuristies. Similar predictions imply that they provide similar information, while divergent predictions indicate that each factor could provide unique information. Predictions for node pairs can be arranged descending order according to the predicted likelihood of them being connected. We primarily focus on top-ranked node pairs since they are likely to be predicted as links. Thus, they can largely determine the efficacy of the corresponding algorithm. If two algorithms produce similar predictions, high-lits ligelliiklihodd edges should have a high overlap. Else, their overlap should be low.
Experimental results are shown in Figure Due to the low feature quality, we exclude OGBI.-DDI and OGBL--PA datasets we conduct analyses on all three factors. It focuses on the overlapping ratio between the top ranking (25%) node pairs of two different heuristics either from the same data factor or different data factors. We make the following observations: (i) Comparing two heuristics from the same factor, i.e., the diagonal cells, we observe that high- ligellieelihodd edges for one heuristic are top-ranked in the other. This indicates heuristics from the same data factor capture similar information. (ii) Comparing two heuristics derived from different factors, We can observe that the overlapping of top-ranked edges is much lower, especially when comparing GSP and FP, as well as LSP and FP.
4

---

Published as a conference paper at ICLR 2024
Though GSP and LSP factors have a relatively high overlapping in top-ranked edges, the overlapping is still much smaller than that for heuristics from the same factor. These observations suggest that (i) selecting one representative heuristic for one data factor could be sufficient heuristics from the same factors share similar predictions, and (ii) different factors are unique as there is little overlap in predictions, More analyses are in Appendix E and F.
3.2 THEORETICAL MODEL FOR LINK PREDICTION BASED ON UNDERLYING DATA FACTORS
In this subsection, we rigorously propose a theoretical model for link prediction based on the important data factors empirically analyzed above. We first introduce a latent space model and then theoretically demonstrate that the model reflects the effectiveness of LSP, GSP, and FP factors. All proof's can be found in Appendix C given space constraints.
The latent space model (Hoff et al., 2002) has been widely utilized in many domains, e.g., sociology and statistics. It is typically utilized to describe proximity in the latent space, where nodes with close in the latent space are likely share particular characteristics. In our paper, we propose a latent space model for link prediction, describing a graph with N nodes incorporating both feature and structure proximity, where each node is associated with a location in a D-dimensional latent space. Intuitions on modeling feature and structure perspectives are shown as follows. (i) Structural perspective is of primarily significance in link prediction. In line with this, the latent space model connects the link prediction problem with the latent node pairwise distance d, where d is strongly correlated with structural proximity. A small dij indicates two nodes and j sharing similar structural characteristics, with a high probability of being connected. (ii) Feature perspective provides complementary information, additionally considering two nodes with high feature proximity but located distantly in the latent space should also be potentially connected. In line with this, introduce the feature proximity parameter Sig in the latent space. A larger Big indicates more likely for node and to be connected. Considering feature and structural perspectives together, we develop an undirected graph model inspired by (Sarkar et al., 2011). 1). Detailed formulation is as follows:
+ calds maxtrrrr (1 - -eg) di S max(rarry
P(i ~ j(dds) =
(I)
3ig
di > max(rary)
where P(i ~ j]ds;) depicts the probability of forming an undirected link between i and j (i ~ j). predicated on both the features and structure. The latent distance di indicates the structural likelihood of link formation between i and j. The feature proximity parameter 3ig E [0. 1] additionally introduces the influence from the feature perspective. Moreover, the model has two parameters and r. a > 0 controls the sharpness of the function. To ease the analysis, we set a = +oo. Discussions on when a # +00 are in Appendix C.6. r; is connecting threshold parameter corresponding to node i. With a = +00, I+c (Fa-7 0 if dij= > max(rı, otherwise it equals to 1. Therefore, large r; indicates node i is more likely to form edges, leading potentially larger degree. Nodes in the graph can be associated with different r values, allowing us to model graphs with various degree distributions. Such flexibility enables our theoretical model to be applicable to more real-world graphs. We identify how the model can reveal different important data factors in link prediction. Therefore, we (i) derive heuristic scores revolving around each factor in the latent space and (ii) provide a theoretical foundation suggesting that each score can offer a suitable bound for the probability of link formation. Theoretical results underscore the effectiveness of each factor.
Effectiveness of Local Structural Proximity (LSP). We first derive the common neighbor (CN) score on the latent space model. Notably, since we focus on the local structural proximity, the effect of the features is ignored. We therefore set the FP parameter 8, = 0, for ease of analysis. Considering two nodes i and j. a common neighbor node & can be described as a node connected to both nodes i and j. In the latent space, it should satisfy both du < max {rx, r& and dej < max (Tk, T3 }. which lies in the intersection between two balls, V(max (rr, } and V (mmax ry), Notably, V(r)= = V()), is the volume of a radius r, where V(1) is the volume of a unit radius hypersphere. Therefore, the expected number of common neighbor nodes is proportional to the volume of the intersection between two balls. Detailed calculations are in Appendix C. With the volume in the latent space, we then derive how CN provides a meaningful bound on the structural distance day.
5

---

Published as a conference paper at ICLR 2024
Proposition (latent space distance bound with CNs). For any 5 0. with probability at least
1 1626 26, we have dej- S 2 maa [tr/N- V(I)
2/D
wheree Tkj is the number of common neighbors between nodes and j, 1. = max Fr, m h. and (1) is the volume of a unit radius hypersphere in D dimensional space, i8 lerm independent Tkj- It vanishes as the number of nodes N grows.
Proposition indicates that a large number of common neighbors Ti results in smaller latent distance dyy, leading high probability for an edge connection. We then extend the above analysis on local structure to global structure with more complicated structural patterns.
Effectiveness of Global Structural Proximity (GSP), We first derive the number of paths between node and on the latent space. Notably, most heuristics on the GSP factor can be viewed as weighted number of paths. The key idea is to view each common neighbor node as a path with length e = 2, serving the basic element for paths with length E > 2. We denote that the nodes i, j are linked through path of length f, i.e., i = kg k1 ~ ~ kt-1 ~ ke = J. As we assume each node is only associated with its neighborhood, the probability that the path P(ko- ~ h1 ~ ~.... kt-1 ~ ke) exists can be easily bounded by decomposition of P(ko ~ h ~ k2). 122 ~)) kg) P(ks 1 ~ ke) II 11 P(ke-1; hig ke+1). ). Notably, each element the common neighbor probability discussed Proposition I, equivalent to the path with & = 2. We then calculate the volume of the number of paths and derive how it bound the latent distance daj.
Proposition (latent space distance bound with the number of paths), For any ō > O, with probability
at least 28, we have dij S Enh'' In +2 maxx
wweeee me () is the number of paths of length between and j in D dimensional Euclidean space. M (1,-.. is the set of intermediate nodes.
TM
((N.6) c(N,5.2)
D0-11)
Proposition indicates that a large number of paths 77 (i..j) results a smaller latent distance dej. leading to high probability for edge connection. It demonstrates the effectiveness of GSP factor.
Effectiveness of Feature Proximity (FP). We next focus on the role of FP parameter 9:y- In particular, we extend Proposition 1 which ignored the FP with 3, O, to B.j [0, 1]. This allows distant nodes in the latent space to be connected with each other they share similar features. Specifically, two nodes i, with latent distance di Tmaz (ra, } are connected each other with a probability Aij- Instead of defining that there is no edge connected with = when di- > max(r;, ri nodes are instead connected with probability of B.j. This provides connection probability for node pairs with high FP. Revolving on the additional consideration of FP, we show the proposition as follows: Proposition 3 (latent space distance bound with feature proximity). For any 5 > O, with probability
at least 1 - 26, we have dej S 2V rma - (B)11) (B,(1--Arr.ra Mrrr) A V(1)
2/D
where Big measures feature proximity between and j. rij maz(ri, and (() is the volume of a unit radius hypersphere in D dimensional Euclidian space. A(r j, dig) is the volume of intersection of two balls of V (r.) and (Ty)) in latent space, corresponding to the expectation of common neighbors.
We can observe that when A rj: rj:))) is fixed, a larger Big leads tighter bound with close distance in the latent space. Proposition 3 indicates that a high FP results in a small latent distance dej leading to a high probability for an edge connection. Notably, the conclusion could easily extend two Proposition 2 on global structural proximity with details in Appendix C.4. The above theoretical results indicate the significance of the three data factors.
3.3 INTRINSIC RELATIONSHIP AMONG UNDERLYING DATA FACTORS
In this subsection, conduct rigorous analysis elucidating the intrinsic relationship among different factors, upon the theoretical model. Our analyses are two-fold: (i) the relationship between structural factors, i.e., LSP and GSP; and (ii) the relationship between factors focusing feature and structure, ie., FP and LSP, FP and GSP. Proof details are in Appendix C.
The relationship between local and global structural proximity. To consider both local and global structural factors, we treat the CN algorithm as the number of paths ne(i.)) with length = 2. Therefore, analysis between local and global structural factors can be regarded as the influence of

---

Published as a conference paper at ICLR 2024
((,,j) on different lengths L. The key for the proof is to identify the effect of l by bounding other terms related with & in Proposition 2, ie., me(i,j) and c(N, 6, f). We also ignore the feature effect to ease the structural analysis.
Lemma 1 (latent space distance bound with local and global structural proximity). For any > O. D(i-1)
with probability at least 1 - 28, we have dip S Em In + 2 ra
(V -
where En=o Fa T'M serve as independent variables that do not change with E.
Given the same number of paths ne with different lengths l, a small l provides much tighter bound with close distance in the latent space. The bound becomes exponentially loose with the increase of
l as the hop in (V VNiiq/// -1
acts as an exponential coefficient. This indicates that (i)
When both LSP and GSP are sufficient, LSP can provide tighter bound, indicating more important role. (ii) When LSP is deficient, e.g., the graph is sparse with not many common neighborhoods, GSP can be more significant. The theoretical understanding
also align with our empirical observations in Section 3.1. Figure 2 illustrates that (i) heuristics derived from GSP perform better on sparse graphs with deficient common neighbors shown in Figure 1. (ii) The heuristics derived from LSP perform better on the dense graph, i.e., OGBI--DII and OGBI.-PPA with more common neighbors.
The relationship between structural and feature prox- imity, Our analysis then focuses on the interplay between feature and structural proximity. The key for the proof is to
BUDDY
NcoGNN
local
global
0.2
Difforence model SAGE
recognize how feature proximity could affect the number
of common neighbors derived from the LSP factor.
0.1
Lemma (Incompatibility between LSP and FP factors). For any 5= > O, with probability at least 26, we have
0.0
0.0
Miy 1- By +1++,e), where Tkj and 3.g are the number of common neighbor nodes and feature proximity between modes i and j. d' < 0 is independent variable that does not change with Bey and Tay- Ts is negatively correlated with Big.
-0.1
feat
struct
feat
struct
Figure Performance comparison between GNN4LP models and SAGE on the OGBL- COLLIAB dataset. Bars represent the perfor- mance gap node pairs dominated by fea- ture and structural proximity, respectively. Figures correspond to compare FP with GSP and LSP. respectively
Lemma 2 demonstrates that node pairs with a large num- ber of common neighbors The tend to have low feature proximity By and vice versa. Such findings underscore the incompatibility between LSP and feature proximity, where it is unlikely that both large LSP and FP co-exist a single node pair. It challenges the conventional wisdom, which posits that LSP tends connect people, reinforcing existing FP,, e.g., connecting people with similar characteristics. However, our findings suggest that LSP could offset the feature proximity. One intuitive explanation of such phenomenon from social network literature (Abebe et al., 2022) is that, in contexts with FP, similar individuals tend to connect. Thus, if nodes with common neighbors (mutual friends) do not have a link connected, their features may be quite different. The new edge forms between those nodes with high LSP actually connect individuals with low FP. A similar relationship is also established between GSP and FP with proof in Appendix C.4.
3.4 AN OVERLOOKED VULNERABILITY IN GNN4LP MODELS INSPIRED FROM DATA FACTORS
In this subsection, we delve into how the incompatibility between structural proximity and feature proximity affects the effectiveness of GNN4LP models. These models are inherently designed to learn pairwise structural representation, encompassing both feature and structural proximity. Despite their strong capability, the incompatibility between structural and feature factors leads to potentially conflicting training signals. For example, while structural proximity patterns may imply likely link between two nodes, feature proximity patterns might suggest the opposite. Therefore, it seems challenging for single model to benefit both node pairs with feature proximity factor and those with the structural ones. Despite most research primarily emphasizing the capability of GNN4LP models on structural proximity, the influence of incompatibility remains under-explored.
7

---

Published as a conference paper at ICLR 2024
X feat
GNNI
Reodout
4B
GNN
Revelod
Score
Sore
Xreat
dral
X drrn
1-1r
Reodoud22
(a) Original coupling SEAL model architecture
(b) Proposed decoupled SEAL model architecture
Figure 5: The original SEAL and the proposed decoupled SEAL architectures. Xeeat and Xami the original node feature and the structural embedding via Double-Radius Node Labeling.
To validate our statement, we conduct experiments to compare the performance of vanilla GNNs, c.g., SAGE and GCN, with the advanced GNN4LP models including Buddy, NeoGNN, and NCNC. The fundamental difference between GNN4LP models and vanilla GNNs is that vanilla GNNs only learn single-node structural representation with limitations in capturing pairwise structural factors while GNN4LP models go beyond. Such comparison sheds light on examining how the key capacity of GNN4LP, i.e. capturing pairwise structural factor, behaves along the incompatibility. Comparisons conducted on node pairs dominated by different factors, represented node pairs E, E and \E with only structural proximity and only feature proximity accurately predicted, respectively, & and E denote node pairs accurately predicted with structural proximity and feature proximity, respectively. Experimental results are presented in Figure 4, where the x-axis indicates node pairs dominated by different underlying factors. The y-axis indicates the performance differences between GNN4LP models and vanilla GraphSAGE. More results on GCN can be found in Appendix E. A notable trend is that GNN4LP models generally outperform vanilla GNNs on edges governed LSP and GSP while falling short in those on feature proximity. This underlines the potential vulnerability of GNN4LP models, especially when addressing edges primarily influenced by feature proximity. This underlines the overlooked vulnerability of GNN4LP models on node pairs dominated by the FP factor due the incompatibllity between feature and structural proximity.
4 GUIDANCE FOR PRACTITIONERS ON LINK PREDICTION
In this section, we provide guidance for the new model design and how to select benchmark datasets for comprehensive evaluation, based on the above understandings from data perspective.
4.1 GUIDANCE FOR THE MODEL DESIGN
In Section 3, we highlight the incompatibil- ity between structural and feature proxim- ity factors in influencing GNN4LP models. When both structural and feature factors come into play simultancously. there is a potential for them to provide conflicting supervision to the model. Such understand- ing suggests that the model design should learn the feature proximity factors and pair- wise structural ones independently before integrating their outputs, in order to mitigate such incompatibility. In particular, we apply such a strategy to the SEAL (Zhang & Chen, 2018), a representative GNN4LP model. Different from the vanilla GNNs only utilizing original node features Xfeat as feature input, it additionally employs local structural features Xarnt by double-radius node labeling (DRNL) based on their structural roles. X feut and Xarnt are concatenated and then forwarded to one single GNN, as depicted in Figure 5(a). Therefore, the GNN must wrestle with the incompatibility between FP and structural factors. Guided by the above understanding, we propose the decoupled SEAL, which separates the original node features X and local structural features Xarat into different GNNs. Each dedicated GNN could learn either feature patterns or pairwise structural patterns separately. The decoupled model architecture is depicted in Figure 5(b). Experimental results comparing the original SEAL and proposed decoupled SEAL illustrated in Figure 6(a). Notably, decoupled
decoupe
origin Pubmed
decouple cullab
Dicference in hnt
Bundel SACE
30
40
Core
Ciledwer Pubmed collab
Teal struct
Teal struct
(a) Performance on original (b)
Comparison between
and decoupled SEAL.
SEAL models and SAGE.
Figure 6: Effectiveness of proposed decoupled SEAL comp.
8

---

Published as a conference paper at ICLR 2024
SEAL consistently outperforms, with gains reaching up to 1.03% on the large COBL-COLLAB dataset. Furthermore, Figure 6(b) shows comparisons with GraphSAGE, following the same setting with Figure 4. The decoupled SEAL demonstrates reduced performance drop node pairs dominated by the FP factor with a larger gain on those by structural factors. Code is available at here.
Table 1: The @it@ 10 performance on the newly selected datasets.
CN
Katz
FH
MLP
SAGE
BUDDY
POWER PHOTO
12.88
29.85
NA
5.03 + 0.88
6.99 + 1.16
19.88 + 1.37
18.34
7.07
13.78
12.37 + 4.13
18.61 + 5.97
18.09 + 2.52
4.2 GUIDANCE FOR BENCHMARK DATASET SELECTION
With the recognized data factors and their relationships, we enumerate all potential combinations among different data factors, illuminating the complete dataset landscape. It allows to categorize prevalent datasets and pinpoint missing scenarios not covered by those datasets. Consequently, we introduce new datasets addressing those identified gaps and offer guidance for practitioners on more comprehensive benchmark dataset selection. In particular, we recognize datasets into four categories considering two main aspects: (i) From the feature perspective, we verify whether FP dominates, indicated with decent performance on FH. (ii) From the structural perspective, we verify whether GSP dominates, indicated by whether a GSP heuristic can provide additional improvement over LSP (if not, then L.P dominates). Section 3.3 demonstrates that such scenario happens when LSP is inadequate. Therefore, there are four categories including category 1: both LSP and FP factors dominate. Category 2: Only LSP factor dominates. Category 3: both GSP and FP factors dominate. Category 4: Only GSP factor dominates. Evidence in Figure helps to categorize existing benchmarking datasets. The prevalent datasets like CORA, CITESEER and PUBMED are in category with both GSP and FP factors dominating, while datasets like OGBL-DDI and OGBL-PPA primarily are in category 2, focusing on the LSP factor. We can then clearly identify that two significant dataset categories, and 4, are not covered on existing datasets.
To broaden for more comprehensive evaluation beyond existing benchmark datasets, we introduce more datasets to cover these categories.... This includes the unfeatured POWER dataset in category 4 and the PHOTO dataset in category 1. The categorizations of these datasets are confirmed through experimental results illustrated in Table 1. We observe: (i) For the POWER dataset with only GSP matters, the Katz significantly outperforms other algorithms, even the GNN4LP model, BUDDY. (ii) Deep models do not show superior performance on both datasets, indicating that success focusing on existing datasets cannot extend to the new ones, suggesting potential room for improvement. We can then provide the following guidance for benchmarking dataset selection for practitioners: (i) selecting algorithms that perform best on the datasets belonging to the same category as the proposed one. (ii) selecting datasets from their own domain rather than datasets from other domains. To help with that, we collect most of the existing datasets for link prediction covering most domains including biology, transportation, web, academia, and social science, assisting in more comprehensive evaluation aligning with real-world scenarios. Details on all datasets are in Appendix D and the repository.
5 CONCLUSION
In this work, we explore link prediction from a data perspective, elucidating three pivotal factors: LSP, GSP, and FP. Theoretical analyses uncover the underlying incompatibility. Inspired by incompatibility. our paper shows a positive broader impact as we identify the overlooked biased prediction in GNN4LP models and show the potential solution to address this issue. Our understanding provides guidance for the new model design and how to select benchmark datasets for comprehensive evaluation. Such understanding also gains insights for future direction including (1) adding more careful discussion on the above faimess issue and (2) designing specific GNN4LP models for datasets in different dataset categories mentioned in Sec 4.2. Nonetheless, our paper shows minor limitations as we make the assumption that the feature proximity is an additional noise parameter rather than adaptively combining that information in the same subspace in theoretical analysis. A more comprehensive discussion on Limitation, broader impact, and future works in Appendix G,H, and I.

---

Published as a conference paper at ICLR 2024
6 ACKNOWLEDGEMENT
This research is supported by the National Science Foundation (NSF) under grant numbers CNS 2246050, IIS IIS1845081, IIS2212033 IIS2212144, IIS- IIS-2406648, IIS-2406647, IOS2107215, DUE 2234015, DRL 2025244 and IOS2035472. the Army Research Office (ARO) under grant num- ber 191 the Home Depot, Cisco Systems Inc, Amazon Faculty Award, John- son&Johnson, JP Morgan Faculty Award and SNAP.
REFERENCES
Rediet Abebe, Nicole Immorlica, Jon Kleinberg, Brendan Lucier, and Ali Shirali. On the effect of triadic closure on network segregation. In Proceedings of the 23rd ACM Conference on Economics and Computation, pp. 249-2844 2022.
Ghadeer AbuOda, Gianmarco De Francisci Morales, and Ashraf Aboulnaga. Link prediction via higher-order motif features. Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2019, Würzburg, Germany, September 16 16-20, 2019, Proceedings, Part I. pp. 412-429. Springer, 2020.
Robert Ackland et al. Mapping the us political blogosphere: Are conservative bloggers more prominent? BlogTalk Downunder 2005 Conference. Sydney. BlogTalk Downunder 2005 Conference, Sydney, 2005.
Lada A Adamic and Eytan Adar. Friends and neighbors on the web. Social networks, 25(3):211-230, 2003.
Aili Asikainen, Gerardo lñiguez, Javier Freña-Carrión Kimmo Kaski, and Mikko Kivelä. Cumulative effects of triadic closure and homophily in social networks. Science Advances, 6(19):eaxx730, 2020.
Vladimir Batagelj and Andrej Mrvar, 2006. networks data/.
http://vlado fmf. uni mini--1j.. 11.11..... sii.sii....................... si/bub//
Sergey Brin and Lawrence Page. Reprint of: The anatomy of large-scale hypertextual web search engine. Computer networks, 56(18):382533833, 2012.
Deepayan Chakrabarti. Avoiding biases due similarity assumptions in node embeddings. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 56 65, 2022.
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. In ICLR, 2023.
Sergio Currarini, Matthew O Jackson, and Paolo Pin. An economic model of friendship: Homophily, minorities, and segregation. Econometrica, -7(4):1003-1043 2009.
Nur Nasuha Daud, Siti Hafizah Ab Hamid, Muntadher Saadoon, Firdaus Sahran, and Nor Badrul Anuar. Applications of link prediction in social networks: A review. Journal of Network and Computer Applications, 166: 1667162 2020.
Yuxiao Dong, Reid A Johnson, Jian Xu, and Nitesh V Chawla. Structural diversity and homophily: A study across more than one hundred big networks. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 807-816, 2017.
Anna Evtushenko and Jon Kleinberg. The paradox of second-order homophily in networks. Scientific Reports, 11(1):13366 2021.
Hao-Ming Fu, Patrick Poirson, Kwot Sin Lee, and Chen Wang. Revisiting neighborhood- link prediction for collaborative filtering. In Companion Proceedings of the Web Conference 2022, pp. 1009-1018, 2022.
10

---

Published as a conference paper at ICLR 2024
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.
Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang, and Reza Zadeh. Wtf: The who follow service twitter. In Proceedings of the 22nd international conference World Wide Web, pp. 505-514, 2013.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems. 30, 2017.
Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, Yongdong Zhang, and Meng Wang. Lightgen: Simplifying and powering graph convolution network for recommendation. In Proceedings of the 43rd International ACM SIGIR conference on research and development Information Retrieval, pp. 2020.
Peter D Hoff, Adrian Raftery, and Mark S Handcock. Latent space approaches to social network analysis. Journal of the american Statistical association, 17(460):1090-1099 2002.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs. Advances in neural information processing systems, 11:22118-22133 2020.
Hong Huang, Jie Tang, Lu Liu, JarDer Luo, and Xiaoming Fu. Triadic closure pattern analysis and prediction in social networks. IEEE Transactions on Knowledge and Data Engineering, 27(12): 3374-3389 2015.
Hong Huang, Yuxiao Dong, Jie Tang, Hongxia Yang, Nitesh V Chawla, and Xiaoming Fu. Will triadic closure strengthen ties in social networks? ACM Transactions Knowledge Discovery from Data (TKDD), 12(3):1-25, 2018.
Zan Huang, Xin Li, and Hsinchun Chen. Link prediction approach to collaborative filtering. In Proceedings of the 5th ACM/IEEECC joint conference on Digital libraries, pp. 141-142, 2005.
Paul Jaccard. Distribution comparée de la flore alpine dans quelques régions des alpes occidentales et orientales. Bulletin de la Murithienne, (31):81-92, 1902.
Glen Jeh and Jennifer Widom. Simrank: measure of structural-contex similarity. In Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 538 543, 2002.
Leo Katz. A new status index derived from sociometric analysis. Psychometrika, 18(1):39 43, 1953.
Kazi Zainab Khanam, Gautam Srivastava, and Vijay Mago. The homophily principle in social network analysis. arXiv preprint arXiv:2008. 10383, 2020.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint ArXiv:1412.660 2014.
Thomas N Kipf and Max Welling. Variational graph auto-encoders. NIPS Workshop on Bayesian Deep Learning, 2016.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
Lecheng Kong, Yixin Chen, and Muhan Zhang. Geodesic graph neural network for efficient graph representation learning. Advances in Neural Information Processing Systems, 35:5896-5909, 2022.
István A Kovács, Katja Luck, Kerstin Spirohn, Yang Wang, Carl Pollis, Sadie Schlabach, Wenting Bian, Dae- Kyum Kim, Nishka Kishore, Tong Hao, et al. Network- beased prediction of protein interactions. Nature communications, 10(1):1240, 2019.

---

Published as a conference paper at ICLR 2024
Ajay Kumar, Shashank Sheshar Singh, Kuldeep Singh, and Bhaskar Biswas. Link prediction techniques, applications, and performance: A survey. Physica A: Statistical Mechanics and its Applications, 553: 553:124289, 2020.
Jure Leskovec and Julian Mcauley. Learning to discover social circles ego networks. Advances in neural information processing systems, 25, 2012.
Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. In Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery data mining, pp. 177-187, 2005.
Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graph evolution: Densification and shrinking diameters. ACM transactions on Knowledge Discovery from Data (TKDD), 1(1):2-es, 2007.
Jure Leskovec, Kevin J Lang, Anirban Dasgupta, and Michael W Mahoney. Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Mathematics, 6(1 1129:122,,, 2009.
Jure Leskovec, Daniel Huttenlocher, and Jon Kleinberg. Signed networks in social media. In Proceedings of the SIGCHI conference on human factors in computing systems, pp. 1361-1370, 2010.
Juanhui Li, Harry Shomer, Haitao Mao, Shenglai Zeng, Yao Ma. Neil Shah, Jiliang Tang, and Dawei Yin. Evaluating graph neural networks for link prediction: Current pitfalls and new benchmarking. arXiv preprint arXiv:2306. 10453, 2023.
Shuming Liang, Yu Ding, Zhidong Li, Bin Liang, Yang Wang, Fang Chen, et al. Can gnns learn heuristic information for link prediction? 2022.
Haoyu Liu, Ningyi Liao, and Siqiang Luo. Simga: A simple and effective heterophilous graph neural network with efficient global aggregation. arXiv preprint ExXiv:2305.09958 2023.
Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample variance penaliza- tion. arXiv preprint arXiv:0907.3740, 2009.
Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton Van Den Hengel. Image-based recommendations styles and substitutes. In Proceedings of the 38th international ACM SIGIR conference on research and development in information retrieval, pp. 43-52, 2015.
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3:127-163, 2000.
Colin McDiarmid et al. On the method of bounded differences. Surveys in combinatorics, 141(1): 148-188, 1989.
Miller McPherson, Lynn Smith-Lovin, and James M Cook. Birds of a feather: Homophily in social networks. Annual review sociology, 27(14:415-444 2001.
Yohsuke Murase, Hang Hyun Jo, János Török, János Kertész, Kimmo Kaski, et al. Structural transition in social networks. 2019.
Mark EJ Newman. Clustering and preferential attachment growing networks. Physical review E, 64(2):025102, 2001.
Mark EJ Newman. Finding community structure in networks using the eigenvectors of matrices. Physical review F, 74(3):036104, 2006.
Maximilian Nickel, Xueyan Jiang, and Volker Tresp. Reducing the rank in relational factorization models by including observable patterns. Advances in Neural Information Processing Systems, 27, 2014.
Maximilian Nickel, Kevin Murphy, Volker Tresp, and Evgeniy Gabrilovich. A review of relational machine learning for knowledge graphs. Proceedings of the IEEE, 104(1):11-33) 11-33, 2015.
12

---

Published as a conference paper at ICLR 2024
Tore Opsahl. Triadic closure in two-mode networks: Redefining the global and local clustering coefficients. Social networks, 35(2):159 167-9996666226000 2013.
Rose Oughtred, Chris Stark, Bobby-Joe Breitkreutz, Jennifer Rust, Lorrie Boucher, Christie Chang, Nadine Kolas, Lara O'Donnell, Genie Leung, Rochelle McAdam, et al. The biogrid interaction database: 2019 update. Nucleic acids research, 47(D1):D529-DD D541,, 2019.
Tolutola Oyetunde, Muhan Zhang, Yixin Chen, Yinjie Tang, and Cynthia Lo. Boostgapfill: improving the fidelity of metabolic network reconstructions through integrated constraint and pattern-based methods. Bioinformatics, 33(4):608-611, 2017.
Matthew Richardson, Rakesh Agrawal, and Pedro Domingos. Trust management for the semantic web. In International semantic Web conference, pp. 351 Springer, 2003.
Ryan A Rossi, Anup Rao, Sungchul Kim, Eunyee Koh, and Nesreen Ahmed. From closing triangles to closing higher-order motifs. In Companion Proceedings of the Web Conference 2020, pp. 42 42-43, 2020.
Pumnamrita Sarkar, Deepayan Chakrabarti, and Andrew W Moore. Theoretical justification of popular link prediction heuristics. In UCAI proceedings-innemmationll joint conference on artificial intelligence, volume 22, pp. 2722, 2011.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv: 1811881116666 2018.
Jiliang Tang, Huiji Gao, Xia Hu, and Huan Liu. Exploiting homophily effect for trust prediction. In Proceedings of the sixth ACM international conference on Web search and data mining, pp. 53 53-62, 2013.
Gergö Tóth, Johannes Wachs, Riccardo Di Clemente, Ákos Jakobi, Bence Ságvári, János Kertész, and Balázs Lengyel. Inequality is rising where social network segregation interacts with urban topology. Nature communications, 12(1):1143, 2021.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks, stat, 1050:20, 2017.
Christian Von Mering, Roland Krause, Berend Snel, Michael Cornell, Stephen G Oliver, Stan- ley Fields, and Peer Bork. Comparative assessment of large-scale data sets of protein-protein interactions. Nature, 417(6887:399-4003 2002.
Haorui Wang, Haoteng Yin, Muhan Zhang, and Pan Li. Equivariant and stable positional encoding for more powerful graph neural networks. arXiv preprint 2XXix22033.00199 2022.
Hui Wang and Zichun Le. Seven-layer model in complex networks link prediction: A survey. Sensors, 20(22):6560, 2020.
Xiang Wang, Xiangnan He, Meng Wang, Fuli Feng, and Tat-Seng Chua. Neural graph collaborative filtering. In Proceedings of the 42nd international ACM SIGIR conference Research and development in Information Retrieval, pp. 165-174,77 2019a
Xiyuan Wang, Haotong Yang, and Muhan Zhang. Neural common neighbor with completion for link prediction. arXiv preprint arXiv:2302.00899, 2023.
Yue Wang, Lei Chen, Yulin Che, and Qiong Luo. Accelerating pairwise simrank estimation over static and dynamic graphs. The VLDB Journal, 28:99-122. 122, 2019b.
Duncan J Watts and Steven H Strogatz. Collective dynamics of 'small-world" networks. nonttwosrrddnettwrrk.. nature, 393 (6684):440-442, 1998.
Wei Wu, Bin Li, Chuan Luo, and Wolfgang Nejdl. Washing-acceleratee graph neural networks for link prediction. In Proceedings of the Web Conference 2021, pp. 2910-2920, 2021.
Cheng Yang. Zhiyuan Liu, Deli Zhao, Maosong Sun, and Edward Y Chang. Network representation learning with rich text information. In IJCAI, volume 2015, pp. 2111-2117, 2015.
13

---

Published as a conference paper at ICLR 2024
Jaewon Yang and Jure Leskovec. Defining and evaluating network communities based on ground -rouudd-rruh..... In Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics, pp. 1-8, 2012.
Haoteng Yin, Muhan Zhang, Yanbang Wang, Jianguo Wang, and Pan Li. Algorithm and system co-design for efficient subgraph-based graph representation learning. arXiv preprint arXiv:2202. 13538, 2022.
Haoteng Yin, Muhan Zhang, Jianguo Wang, and Pan Li. Surel+: Moving from walks to sets for scalable subgraph-bas based graph representation learning. arXiv preprint arXiv:2303.03379, 2023.
Seongjun Yun, Scoyoon Kim, Junhyun Lee, Jacwoo Kang, and Hyunwoo Kim. Neo-gnns: Neigh- borhood overlap- aware graph neural networks for link prediction. Advances in Neural Information Processing Systems, 34:13683-13694, 2021.
Akbar Zaheer and Giuseppe Soda. Network evolution: The origins of structural holes. Administrative Science Quarterly, 54(1):1-31, 2009.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. arXiv preprint 1xXiv:197.004933 2019.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in neural information processing systems, 31, 2018.
Muhan Zhang, Zhicheng Cui, Shali Jiang, and Yixin Chen. Beyond link prediction: Predicting hyperlinks in adjacency space. In Proceedings of the AAAI Conference on Artificial Intelligence, 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.
He Zhao, Lan Du, and Wray Buntine. Leveraging node attributes for incomplete relational data. In International conference on machine learning, pp. 4072-4081. PMLR, 2017.
Tao Zhou, Linyuan Lü, and Yi-Cheng Zhang, Predicting missing links via local information. The European Physical Journal B. 7. 71:623-630, 2009.
Yangze Zhou, Gitta Kutyniok, and Bruno Ribeiro. Ood link prediction generalization capabilities of message-passing gnns in larger test graphs. Advances in Neural Information Processing Systems, 35:20257-20272, 2022.
Fanwei Zhu, Yuan Fang, Kai Zhang, Kevin Chang, Hongtai Cao, Zhen Jiang, and Minghui Wu. Unified and incremental simrank: Index-free approximation with scheduled principle. IEEE Transactions on Knowledge and Data Engineering, 2021a
Zhaocheng Zhu, Zuobai Zhang, Louis-Pascal Xhonneux, and Jian Tang. Neural bellman-foo networks: A general graph neural network framework for link prediction. Advances in Neural Information Processing Systems, 14:29476-294999 2021b.
Zhaocheng Zhu, Xinyu Yuan, Louis-Pasch Xhonneux, Ming Zhang, Maxime Gazeau, and Jian Tang. Learning to efficiently propagate for reasoning on knowledge graphs. arXiv preprint urXiv:2206.04798 04798, 2022.
14

---

Published as a conference paper at ICLR 2024
Appendix
Table of Contents
A Related work
16
B Details heuristic algorithms
17
C Theoretical analysis on the graph latent space model
18
C.I. Extended Latent space model for link prediction
18
C.2 The effectiveness of local structural proximity (LSP)
19
The effectiveness global structural proximity (GSP)
20
C.4 The effectiveness of feature proximity
(FP) & relationship with feature proximity
23
C.S Theoretical analysis for other local structral heuristics
24
C.6 Non-deterministic case for latent space model
25
D Descriptions on more datasets
27
E Additional results main analysis
F Additional analysis among data factors
29
G Limitation
29
H Broader Impact
31
Future Direction
33
Datasets details
34
K Experimental Settings & model performance
35
K.1 Experimental Settings
35
K.2 Model performance
36
15

---

Published as a conference paper at ICLR 2024
A RELATED WORK
Link prediction is fundamental task in graph analysis. It seeks to determine the probability of a connection between two nodes in graph, leveraging both the existing graph topology and node features. This task plays a critical role in variety of applications, such as improving knowledge graph completion (Nickel et al., 2015), enhancing metabolic networks (Oyetunde et al., 2017), suggesting potential friends in social media platforms (Adamic & Adar, 2003; Gupta et al., 2013), predicting protein-protein protein interactions (Kovács et al., 2019), and refining e-commerce recommendations (Huang et al., 2005). Heuristic algorithms initially dominated, serving as the primary methodology, due to their simplicity, interpretability, and scalability. Then, GNNs are introduced which leverages the power of deep learning. It allows for automatic feature extraction with superior performance.
Heuristic algorithms are based on the hypothesis that nodes with higher similarity have increased probability of connection. The proximity score between two nodes represents their potential con- nection probability. This score is tailored to the characteristics of specific node pairs, viewed from various perspectives. Generally, there are three types of heuristic approaches to measure the proximity and the formal definition of some representative ones are listed in Table 2. (1) Local structural heuristies. This category includes four prevalent algorithms: Common Neighbor (CN) (Newman, 2001), Jaccard (Jaccard, 1902), Adamic Adar (AA) (Adamic & Adar, 2003) and Resource Alloca- tion (RA) (Zhou et al., 2009). These methods are fundamentally based on the assumption that nodes sharing more common neighbors are more likely to connect. AA and RA are weighted variants of common Neighbors. Typically, they incorporate node degree information, emphasizing that nodes with a lower degree have a higher influence. (2) Global structural proximity heuristics. This category includes algorihms Katz (Katz, 1953), SimRank (Jeh & Widom, 2002), and Personalized PageRank (PPR) (Brin & Page, 2012) in the graph. They consider the global structural patterns with the number of paths between two nodes, where more paths indicate high similarity and are more likely to connect. Specifically, Katz counts the number of all paths between two nodes, emphasizing shorter paths by penalizing longer ones with factor. SimRank assumes that two nodes are similar if they are linked to similar nodes, and PPR produces ranking personalized to a particular node based on the random walk. (3) Feature proximity heuristies is available when node attributes are available, incorporating the side information about individual nodes. (Nickel et al., 2014; Zhao et al., 2017) combines graph structure with latent features and explicit features for better performance.
Graph Neural Networks Graph Neural Networks (GNNs) have emerged as powerful technique in Deep Learning, specifically designed for graph-structured data. They address the limitations of traditional neural networks in dealing with irregular data structures. GNNs learn node representations by aggregating neighborhood and transforming features recursively.
Graph Neural Networks (Kipf & Welling, 2017: 2016; Hamilton et al., 2017; Velickovic et al., 2017) aim to learn high-quality features from data instead of predefined heuristies developed with domain knowledge. Despite satisfying results in many tasks via utilizing structural information, (Zhang & Chen, 2018; Zhang et al., 2021; Liang et al., 2022) find that vanilla GNNs are still sub-optimal suffering from disability on capturing important pairwise patterns for Link Prediction, e.g., Common Neighborhood. Graph Neural Networks for Link Prediction (GNN4LP) (Zhang & Chen, 2018; Zhang al., 2021; Yun et al., 2021: Wang et al., 2022; 2023; Chamberlain et al., 2023; Zhu al., 2021b) are then proposed which incorporates different inductive bias to capturing more pairwise information. SEAL (Zhang& & Chen, 2018). Neo-GNN (Yun et al., 2021) and NCNC (Wang et al., 2023) involve knowledge. BUDDY (Chamberlain et al., 2023), and NBFNet (Zhu
more neighbor-overrappiin et al., 202 1b) exploit the higher order structural information, e.g., number of paths between nodes. Nonetheless, advanced GNN4LP models with better effectiveness usually have more complicated model designs, leading to the efficiency issue. (Yin et al., 2022; 2023; Wu et al., 2021: 7hu et al., 2022; Kong et al., 2022) are then proposed to improve efficiency via approximating methods, c.g.. hashing algorithm, A algorithm, and random walk approximations.
The node embedding models (Yang et al., 2015; Grover & Leskovec, 2016) are graph learning algorithms used to transform the nodes of a graph into low-dimensional vectors, capturing the network topology and the node feature properties. This approach learns representations through data-driven algorithms, enabling effective capturing of complex patterns within the graph structure and node features for link prediction. For instance, Node2Vec (Grover & Leskovec, 2016) captures
16

---

Published as a conference paper at ICLR 2024
both local and global structural proximity while TADW (Grover & Leskovec, 2016) [3] captures both local structural proximity and feature proximity.
Notably, our paper provides comprehensive analysis with the latent space model to understand the important data factors for the link prediction task and how different link prediction algorithms work. The analysis can be used to understand all the above algorithms including graph embedding algorithms, GNNs, and heuritics in a holistic manner.
Principles in Link Prediction & Network Analysis Over the years, various theories and expertise knowledge have emerged to understand and predict links in networks. We typically review the foundational theories shaping the landscape of link prediction and network analysis. Moreover, provide a detailed comparison with particular works.
Homophily (Khanam et al., 2020) is long-standing principle in social network analysis, stemming from the shared beliefs and thoughts of individuals. It suggests that people with aligned perspectives are likely to connect with one another, despite potential differences in their social position. (Murase et al., 2019; Evtushenko & Kleinberg, 2021; Khanam et al., 2020; Currarini et al., 2009; McPherson et al., 2001) provide further study illustrating how homophily induced different phenomenons in social networks.
Tradic closure (Huang et al., 2015) another fundamental concept in social network analysis, stemming from that friends of friends become friends themselves. It suggests that two individuals, who have a mutual friend, become connected themselves. (Dong et al., 2017; Rossi et al., 2020; Huang et al., 2018; Opsahl, 2013) provide further study illustrating how homophily induced different phenomenons in social networks. (Sarkar et al., 2011) theoretically proves the effectiveness of heuristics algorithms. The key differences between our work and (Sarkar et al., 2011) are follow: 1. (Sarkar et al., 2011) assumes nodes are with the same degree in most cases, while our model can adapt to graphs with all kinds of degree distribution. 2. (Sarkar et al., 2011) only focuses on the structural perspective while our model considers both effects from feature and structural 3. (Sarkar al., 201 1) focuses on the deterministic model while the non-deterministic one is largely ignored.
More recently, (Murase et al., 2019; Asikainen et al., 2020; Abebe et al., 2022) focus on investigating the interplay between the role of the tradic closure and homophily. (Asikainen al., 2020) first demonstrate that triadic closure intensifies the impacts of homophily. Nonetheless, (Abebe et al., 2022) points out that (Asikainen et al., 2020) builds on the existence of sufficient tradic closure rather than considering the tradic closure and homophily simultaneously. With a modest modification, (Abebe et al., 2022) finds that tradic closure can introduce individuals to those unlike themselves, consequently reducing segregation. The key differences between our work and (Abebe et al., 2022) are as follows: (I) (Abebe et al., 2022) typically focuses on alleviating the effects of segregation (Tóth et al., 2021) via the tradic closure rather than the link prediction task in work. (2) (Abebe et al., 2022) focuses on the typical graph model in social science, while our work aims to understand link prediction in various domains.
Despite those principles focusing on network analysis, more theories and principles are proposed revolving around deep learning models, especially for GNN4LP models. (Zhang & Chen, 2018) pro- poses the 7-decaying heuristic theory indicating that subgraph GNN can capture sufficient structural information for link prediction. (Zhang al., 2021) proposes the labeling trick theory indicating how to identify the most structural node representation. (Zhou et al., 2022) revolves around the size stability of inductive OOD link prediction problem from causal perspective.
B DETAILS ON HEURISTIC ALGORITTMS
We then explain more implementation details on those heuristics as follows:
Katz. < is a damping factor, indicating the importance of the higher-order information. We set À~ = 0.1 in our implementation. Ipaths !) j)l counts the number of length-/ paths between i and j. We compute the Katz index (Katz, 1953) by approximating the closed-form solution + +... A", where S is the score matrix. We utilize S = (I - XA)- - I with XA + 22 + .....
x 0.05 and
3 in our implementation.
PPR. [m is the stationary distribution probability of j under the random walk from i with restart, more details in Brin & Page (2012). We adapt 1e-3 as the stop criterion.
17

---

Published as a conference paper at ICLR 2024
Table Popular heuristics for link prediction, where F(i) denotes the neighbor vertex i.
Name
Formula
Factor
common neighbors (CN)
n())
LSP
Adamic-Ade (AA)
Exer Exer(nnr)) log (1()))
LSP
resource allocation (RA)
ExTrgrrT Tray
LSP
Katz
Σ 2
X Xlpaths ((, (4,5))
GSP
Personal PageRank (PPR)
[oy]e
GSP
Coen
SimRank
GSP
Feature Homophily (FH)
2,)
FP
SimRank. We utilize the efficient framework (Zhu et al., 2021a) with the LocalPush SimRank algorithm (Wang et al., 2019b). Code is available at https://gtthu..com// comm/USSim2000//Smmm22200
FH. It estimates the node feature similarity between a pair of nodes. Different feature distance metrics can be utilized for estimation. Typically, we include two feature distance metrics: cosine distance and Euclidean distance.
Couble-Radius Node Labeling, It aims to extract the position information based on the source and target nodes and j. can be calculated as: fi(i) + min(dz, dy) + (d/2)[(d/2) (d%2) 1] where dz = d(i, .r,, dy = d(y,"), i). j(i,j) is the node with a distance i to the source node and distance j to the target node.
Heuristic selection In section 3, we majorly focus one default heuristic for each factor, which are CN for LSP, Katz for GSP, and FH for FP. Moreover, for experiments Section 3.1, we make a comparison between two heuristies from the same factors. The details for the second heuristic are RA for LSP, PPR for GSP. For FP factor, the default one is with cosine distance while the second one with Euclidean distance.
C THEORETICAL ANALYSIS ON THE GRAPH LATENT SPACE MODEL
In Section 3.2, we introduce the latent space model and theoretically verify the effectiveness of heuristic algorithms derived from three factors: local structural proximity (LSP), global structural proximity (GSP), and feature proximity (FP). In this section, provide all the proof details in Section 3.2 and 3.3 on the signifiance of the data factors and their underlying relationship. In particular, the following proof is inspired by the latent model proposed in (Sarkar al., 2011). The main differences between our model and (Sarkar et al., 201 are two-fold with better alignment to the real-world scenario. (1) Our model can easily extend to graphs under arbitrary degree distributions in (Sarkar et al., 201 1) rather than only considering regular graphs with the same node degree. (2) Our model adds node features into consideration rather than only considering unfeatured graphs in (Sarkar et al., 2011). Moreover, we provide a deep analysis of the interplay between feature and structure proximity.
C.1 EXTENDED LATENT SPACE MODEL FOR LINK PREDICTION
To ease the analysis, utilize the latent space model as the data assumption showing follows: Definition (Latent space model for link prediction). The generated nodes are uniformly distributed in D dimensional Euclidean space. Each node possesses a subordinate radius r and corresponding volume (rr). For any nodes i, The probability of link formation P(i m j) is determined by the radius (14, and distance dij of the nodes its ends.
V) (()))) where V(r) is the volume of radius and (1) is the volume of unit radius hypersphere.
2)Deg(t) (T(r:), where Deg(i) is degree of node and N is the total number of nodes.
18

---

Published as a conference paper at ICLR 2024
P(i P(inj(ddy)= 1/ (adu---akaaaariaaa mox(rer)))) where P(i ~ j|dız) depicts the probability of forming a unidirectional link between and j (i ~ j), a > 0 controls the sharpness of the function and r determines the threshold.
In order normalize the probabilities, we assume that all points lie inside unit volume hypersphere
in dimensions. The maximum FMAX satisfies ((rMAx) = V(1)rMA = 1, i.e., TMAX = L )1/D. For any node i,j in graph, we define the volume of intersection of two balls of V (ri) and (a ((ry) A(ri, Ty, diz), which can be bounded using hypersphere as:
Pr +r dij -
A (ri,Ted
[ij 2 2
D/2
mar
(2)
2
V(1)
where 1i plna max(ri 3 and (2. above bridges A(ri, Ty diz) and dip through the volume of hypersphere.
The latent space model above is well-fitted for link prediction because the distance d,j in the model portrays the probability of forming a link between node and j. and for a given node, the most likely node it would connect is the non-neighbor the smallest distance. In addition, Deg(i)
(r;)) describes the sum of the first-order link neighbors the node. Our latent space model can be applied the dataset where nodes are distributed independently in some latent metric space; given the positions links are independent of each other.
C.2 THE EFFECTIVENESS OF LOCAL STRUCTURAL PROXIMITY (LSP)
Proposition (latent space distance bound with CNs). For any 0, with probability at least
(Ni//N-e)) 2/D
1 - 25, we have diş- S 2/ raa
V(I) ((11
where Thū is the number of common neighbors
between nodes and j. ri = max (re, r and (11) is the volume of unit radius hypersphere in
D dimensional space. is term independent of Mi-- vanishes as the number of nodes N grows.
Note N(i) as the of neighbors of node and let Y2 be random variable depending on the position of point k which is I if & E ((1) (N))), and otherwise. Therefore, we have
Saade P(i~ djj ~ dry) P (lik,, djk dry) (d.y)
E [Y dey P(i k~ dij)
A(r,, d4j)
(3)
For the sake of brevity, denote E [Yg dsyl E [Vr]. It can be easy observed that Σ ie., the common neighbour number (CN) of node and j, denoted as Mij here. Through empirical Bernstein bounds (Maurer & Pontil, 2009), have
k= Yz Mij.
N
2 varn (Y) log 2/6
7 log 2/8 3(N - -1]
P
Σ
Y2/N - E(Y 2
< 20
(4)
N
where var (Y) nh (1-mh//N is the sample variance of Y. Setting log 2/8 3(V-1)
22 log 2/8 2/8 N
N-1
Ml - - A A
Thi N
+ 2 1 - 26
(5)
N
Combining Eq. (2) and equation above, we can get the bounds of di₃ as:
1i tr
dij
T2 N
V(1)
S
+c
2
dij
2
D/2
Ti
(6)
V(I) Z
2
N
19

---

Published as a conference paper at ICLR 2024
ie.,
1g/N +6 V(1)
1/D
Taj /N V(1)
2/
74 P -
de S 2
13
mar
(7)
The R.H.S of the above equation, Le., the upper bound of dı decreases as 7i increases. In other words, the greater CN number Ol of two nodes i.j will cause the upper bound on the distance di between them decrease more, thus indicating the effectiveness of local structural proximity.
Notably, the above theoretical analysis can be easily extended to many other local heuristics, e.g.. RA, AA (Zhou al., 2009), which can be viewed as weighted version for common neighbors. The key to extending proof to those heuristics is to change the definition of Y₁ mainly distinguished from CN by their weight design, can also be proven the existence of similar conclusions. Details show in section C.5
C.3 THE EFFECTIVENESS OF GLOBAL STRUCTURAL PROXIMITY (GSP)
Proposition (latent space distance bound with the number of paths), For any > 0, with probubility
where me (e().) is the number of paths of length E between and j in D dimensional Euclidean space. M {1,..., the set of intermediate nodes.
at least 1 - 26, we have dij S En= I' +2 TM Tp (5.j))
o(N,522)
In this session, analyze how dı can be upper- upper-bounded through the number of simple E-hop paths. Definition 1. (simple path and set) Given node i, j in graph G(V, E), define a simple path of length i between i, as path(i, (i, ki, k2, 22)), such that ~ kn K2
ke ~ and Sr(i, as
the set of all possible path(i, k1, k2, 2)), (k1, k2. k1-2) E
ke-2: E Se(i, Let (i, Ki,ki, Ki,, k)) be random variable which is if (i, (i, kyy and 0 else. We denote ne (1,5) as the number of paths of length & between and j.
ne(i,
Σ
Y
dij)
(8)
Ae.... 2ES(C-2
Our goal is to infer bounds on diy given the observed number of ()). We first bound the maximum degree A follows.
Lemma 1. A < N (1 (1+V-21nd)) 22nd/N with probability at least 1 -
Proof: The degree Deg(k) of any node is a binomial random variable with expectation E[Deg(k)] NV(rk), where V(rx) is the volume of hypersphere of radius rk- Thus, us- ing the Chernoff bound, Deg(k) < (V (1+ V 22
NV(r)) holds with probability at least
1 6. Applying the union bound on all nodes yields the desired proposition, i.e., A < -2lnd NV(rMAX) (1 (F(Ma)))
( (1=
N
Next, we use A bound the maximum possible value of (i..)) Lemma 2. For any graph with maximum degree A, we have: ne(i, S 8-1
This can be proved using simple inductive argument. the graph is represented by adjacency matrix M, then the number of length & paths between and j is given by (i. Trivially M3 can be at most A. This happens when both and j have degree A, and their neighbors form a perfect matching. Assuming this is true for all m < E, have: M (i,j) E, M (i, ( (p.j) s
Proof:
A E, M(ip) 4
Lemma 3. For & < A, me
XN) T1 (1.j XI,..., & Xp.... XN) s s( (e-
2-2
Proof: The largest change in m7(-)) occurs when node p was originally unconnected to any other node, and is moved position where it maximally add to the number of é-hop paths between
20

---

Published as a conference paper at ICLR 2024
i and] j (or vice versa). Consider all paths where p is m hops from i (and hence { - hops from
j From Lemma 2, the number of such paths can be at most A Am-1. f---11 A f Since m E {1....,,- 1},
the maximum change is (e (e-11) 1) A 2
Define j) as the probability of observing an l-hop path between points and j. Next, we compute the expected number of f-hop paths.
Theorem 1. E [v)(i,,)) S A II A (1:pxr, (des - (1---11)),) where x4 is defined
as max 0).
Proof:
Consider an ê-hop path between j, for clarity of notation, let us denote the distances
di de etc. by a1, a1,02, up dz-1 and radius ri, TKa."" , by ro, '.. .rE-1. We also denote the distances dykı dykg, etc. by d1, d2, , Note r = maxx(r)-1.r,).. E f1,2.... , 2-11 1}
From the triangle inequality, de-2 S ae-1 + at S re-1 + re, and by induction, dx S E/ Em==++ mm- Similarly, d1 2 (diy a1)_ 2 (dy re)4 and by induction, d2 2 (dis - (hh- Tm) +
Pe(i, = P (i ~ 11 ..... ~ 1 ~) j dij)
((1 sn..... nat S r/-11 dij)
P (a1 S sr,,..... ae-1 S 121
dh. d.., dis)
Emn-rm
P(a S di dis)... P Pa SS 0 S1/ de-2)
dd-2-=(dy
Enmdra)
di di=(du--o
6-3
A
F
T'm dis
X A
1/2
Tmi (dis - ro)+ x x... x A re-1: (dis
Σ rn)+
m=2
m=3
n=0
2
A
Tmm
dij
Σ
Tn
m=
n=0
Since there can be at most A e-1 possible paths (from Lemma 2), the theorem statement follows.
11 A (rie Eimpur T'm (di) ) + VN
(e-1) 15
Theorem 2. me(i.)) S
VN(1+V/ (1+v= 2ln
(N + --2V2 with probability at least - (1-25).
Proof: From McDiarmid's incquality (McDiarmid et al., 1989), we have:
N Nln(1/8)
m((i,) < E (ne(i. (2- 8-2
(10)
N (1 A
< E (ne(i.))
(11)
2
T--1
2
N Nln(1/8)
SA-1
A
mm
dij
Σ
I'n
+
(12)
2
m=p+1
n=0
p
dij
p-2
Σ
I'n
+
N 1n(1/))
(N +
VV+V-NNInd
2N Ind
8-1
m=p+1
n=0
(13)
The inequality above can be rewritten as:
Σ I' )
p-2
(((.)))s(((c
II A
P
Σ
Ti
dij
+ b(N, +66(N06
(14)
p=1
m=p+1
n=0
21

---

Published as a conference paper at ICLR 2024
where c(N,5,E) and b(N, 6) contain coefficients that do not vary with dy. Note rp max(r Em Em=441 J. and dij can be upper-bounded through the number of simple ε-hop paths () with Eq. (2).
D/2
p-2 dij
mm=
Fin
(e(.)) & 2)
maz
+
+ 6(N,6)
p
2
pm
27
D/2
dij
-n= I'
c(N,6,8)
+ b(N,5)
27
D/2
S (,
dij
n I'
+ +b(N,8) AM (1,..,, (6-
M
2
11/-1)/2
I ((N,88,)
max M
dig
>
M-
I'n
+ b(N.6)
2
i...
M-2
(e(i..) b(N,
de S
Σ On + +2
max
(15)
((,
Since b is ignorable, we can observe the upper bound decreases as 77 (1. increases which implies the effectiveness of GSP as well.
The relationship between global structural proximity (GSP) and local structural proxim- ity (LSP)
The detailed proof of the relationship between global and local structural proximity is shown as follows. The key to view the CN algorithm as the count on the number paths (e(j.) with length 2
Lemma 4 (latent space distance bound with local and global structural proximity). For any ò >>> O.
with probability at least 28, we have dig S M-2 on + 2/13"
maz TM
(V
15(-11
where Σ MM- Yn, I' serve independent variables that do not change with t.
Proof: Replace and in Eq. (15), obeserve that
M
N ln((1/)
me(j.)
DD²-1
dg <
+
IM
2
(N + VV In
(16)
n=0
N In(1/8)
A
On +
TM
mar
2
N 2N
(17)
D(F-1
M-2
Nln(1/8) 2
Tn +2
IM
(18)
n=U
1 1+
-2 2 N
2
M-2
NIn(1/8)
On + 2,
(19)
2
n=0
22

---

Published as a conference paper at ICLR 2024
DiC
Since &
acts as an exponential coefficient, the upper bound of di grows surprisingly fast rate increases (i.e. the order of the structure's proximity goes higher), which makes the effectiveness of structure proximity much weaker.
C.4 THE EFFECTIVENESS FEATURE PROXIMITY (FP) RELATIONSHIP WITH FEATURE PROXIMITY
Proposition 3 (latent space distance bound with feature proximity). For any ā > O, with probability
Tiyr maa (B:alI- (d))) ((wasss))) 2/D
where Big measures feature proximity between and j. rij = max(ri, r5} and ((1) the volume of a unit radius hypersphere in D dimensional Euclidean space. A(ri, rj diy) is the volume of intersection of two balls of (r.)) and (T;)) in latent space, corresponding the expectation of common neighbors.
least 1 26, we have di S 2
22
V(1)
For graphs with node features, feature proximity (FP) is also often used as a similarity measure. In this section, briefly analyze the effect of FP dij. Since FP is not directly related to the spatial concepts of the individuals in the model (e.g.. radius r, distance d), we can think of as a noise parameter that affects the probability of connecting edge of two nodes. According the original deterministic model, i ~ j iff dij < (r ry). J. relies almost exclusively on structural proximity. The introduction of the FP can serve as noise parameter Big extend the deterministic model further into a non-deterministic model, i.e. with probability 1 1- -By (otherwise). Now, the probability of having a common neighbor between node j will be Ag,, (ra,Tj diz) = Big + B.z) (ra, Fy, diz). Substituting As., (Tis y, dsy) for A(r,, ryy dez) in Eq. (2), we have:
with probability Big E (0, (if dij > max(T:, T3 }j)), or
Tt + dig
D
Ag (TaTT, V(1)
dij 2
2
D/2
<
<
mar 13
(20)
2
The upper bound of diÿ is
[1y(11 A (r.. dry)) + (r., dey) 2/D
dig S 2
rman
(21)
V(1)
An increase FP value Big can reduce the upper bound of daj, which reveals the effectiveness of FP. Since A (ri, dey) E 1) and B E (0, 1).
The relationship between local structural proximity (LSSP) and feature proximity (FP):
Lemma 5 (Incompatibility between LSP and FP factors). For any 5 > O, with probability at least 1 - 26, have Thj I-B3 + where mi and Bij the number of common neighbor nodes and feature proximity between nodes and j. e' 0 is an independent variable that does not change with 3gj and my-- Mij is negatively correlated with Biz-
Proof: Combining Eq. (5) and Eq. (21), we have for any 8 > O, with probability at least 25,
d3 $ Udi = 2/ rmaz (Bi)
BBg +
Biy) Ti E)
2/D
(22)
(())
where (Y) (oa 2/6
7 log 2/6
3 MJN-1y- varx m1 is the sample variance of Y and N-1
N Mi represents the common neighbour number between node and j. Eq. (22) can be rewritten as:
d' (Udd r maz .N)
Ti =
+ N(1+6)
(23)
Bij
23

---

Published as a conference paper at ICLR 2024
where
Udy 13)012 N
c 2i mas .N)
mas (L) man
(r
(24)
dij )2))2/112 N
(25)
13
= (V ((I)
(26)
Since 3 (0, 1), can learn from Eq. (23) that numerically, flÿ decreases as Biy increases, and vice-versa. It indicates that when the ground truth di is determined, we can learn from Eq. (23) that there conflict between LSP Thy and FP Byy= these cannot be increased at the same time.
The relationship between global structural proximity (GSH) and feature proximity (FP)
After the introduction of feature proximity into the model, we can rewrite Eq. (14) as:
(-1
p
Te(1.) & c(N
As
Tmm
dij
Σ
In
+
b(N, 6)
p=1
m=p+1
n=D
2-1
p-2
=c(N88,0
II p=1
Big (1
Big)
pp
Σ
mmm
dij
I'
6(N.6)
m=pt1
n=0
1//2
f-1
dij
- > p- m= I'n
< (,
II p=1
Big + (1 Bis)
mma
+ +(N
2
D/27
dij DM-
M-2 In
2
-m=
$c(NN8.8)
Bis + (1 Bis))
TM
mar
+ b(N,8)
MM (1, (1,1..,-11)
2
(27)
i..
me(i.j)- (N.5) ((N...))
1/(R-1)
2/D
-1
dig S Ud,
Σ n=0
Yn +2
IM
8.g
(28)
i...
1/(e-1)
(e(f.))-(NN.)
-1
c(N,6,0)
Bij 1
(29)
27 D/2
Ua,
---2 Tn
man
Since Tc(i.))-(NNd) > We can learn from Eq. (23) that numerically, Be(i, decreases as Thj c(N,5,8)
increases, and vice-versa. It indicates that there is conflict between GP πky and FP Byy: these two cannot be increased at the same time.
C.5 THEORETICAL ANALYSIS FOR OTHER LOCAL STRUCTRAL HBURISTICS
Except for common neighbor number(CNN, there are still many local heuristics metries, e.g. RA, and AA. In this session, we will analyze the relationship between dy and them which gives a broader account of the effectiveness of local structural proximity (LSP). We define RA and AA between node i and j as ni
my = -xeT(Z)T(()) Tog(Deg(k] Note min ming Deg(k), A (()) and max mmxx(Degay) max; Deg(k), k ((z))
RA Exer())N(()) Deg(R] and AA
24

---

Published as a conference paper at ICLR 2024
For RA, let Ys be random variable depending the position of point k, which is Yx Deg(() if
E (1) (J), and otherwise. Therefore we have:
/. Deg(k) P k~j dij)
E [ d:y
=f Jandd (kg(k)
(( ~ k drw P k dz)) P (daas dse I | d (des)
(30)
A(ri; ry, des)
min
For the sake of brevity, we denote E 1 diy] as [Y&)) Similarly, we can obtain:
max maxggD A(ri, Ty dej) E [Ya] S min(Degzy)
Alri, dij)
(31)
It can be easy observed that En=o k= Y n i.e. the RA number of node and j. denoted as Mi here. Through empirical Bernstein bounds (Maurer Pontil, 2009), we have:
R2
/2 varx (Y) log 2/5
7 7og 2/8
P
Yo/N E
20
(32)
N
3(N 11]
Ba (1- 2.
BAANN (N)
var (Y) (Y) log
where varN(Y)
is the sample variance of Y. Setting
N-1
N
7log 2/6
3(N-1)
RA
RA Bh
Mi
P
N
-
c
E S
N
+
c
2 1
25
(33)
Combining Eq. (2) and equation above, we can get the bounds of dij
V(1)
Ti + ry
dij
D
RA
+
E
max (Deg
2
N
(34)
V(I)
dij
2
D/2
13
RA
min(Degay)
N
i...
RA N c Th
1/D
RA my V(1) mai(megnnDD
RR/N-C -C
2/D
Y3 + -
S dij 52
mar
(35)
V(1)/ max(Degg...
In fact, we make more accurate approximation in Eq. (30) if the degree distribution of the graph known in advance. Similarly, we can provide a proof for AA, with the only difference that Yg in AA becomes Y& (og(()(() if & E ((11) nW(),, and 0 otherwise.
C.6 NON-DETERMINISTIC CASE FOR LATENT SPACE MODEL
In this section, we extend our previous analysis based on the infinite values of (a - +0o) in Eq. (I) with finite a. It could help generalize our conclusion to more diverse graphs with different underlying mechanisms.
The core idea underlying almost all of our previous results has been the computation of the probability of two nodes and j having a common neighbor. For the deterministic case, this is simply the area of intersection of two hyperspheres. A(r:, Ty, dzz). However, in the non-deterministic case, there is no such intuitive equivalence. Therefore, our primary goal is to find the representation in the latent space model associated with common neighbor 7/j- The analysis is similar with section C.3 Set / 0 and P(i ~ jl (ddy) 1/ (1+ e" (diy rmaa)) depicts the probability of forming undirected link between and j (i ~ j), influenced by both feature and structure. From the triangle inequality, we have da dij djs, and du > max(di dik, dik diz).
25

---

Published as a conference paper at ICLR 2024
Note ((i) as the of neighbors of node and let Yx be random variable depending the position of point k, which if E (i) (i), and otherwise. Therefore, we have:
E [Yx
dej
P ~ j dis)
Pi k dax) P ~ djw) P (dau, dzs dis) d (dis)
plu
munefdy imuxddyydgaddde dg ddyd + ealdhe- uiuua 1 e ald aadd d (daa) (dzx)
des
1 eadik---ss d (dit) (djx)
diy-
1 + calda-raa
dig distdy
1
aldde - Tmaey (dos) (dgx)
1 caldua-r
d1s
dsh dis
1
+ -jjmn (d.xx) d (dzx) +
1 ealdd (raaa)
-r(x0)) + cadna-rga d (dix)) d (dzz)
1 1 eodld calda
d:s
d (dstt) fr + ca(dheeraa
1
do + caldie-ra d (ddxt) for
to0
1
1 oldd--ar))) d (ddzk)
(rriaa a.) +
caldu-naa mnaary d (ditt) (ra a) (Notation for brevity)
+ caldu
dai
1 1 10 ca(l+2d:))
(1(ri .0) + log
01 (r a.)
= ei (y mna mar a) (e2(rit max maa
,ith .x) (1+ 2d:z)) (Notation for brevity)
(36)
where ej ermm rrike a),, 22(rm Jik mas, ,a) >> are independent items which do not vary with dg.
For the sake of brevity, we denote E [Y d.yl as E [Ya]. It can be easy observed that Σ Yx = 7kj ie.. the common neighbour number (CN) of node i and j. denoted Mhi here. Through empirical Bernstein bounds (Maurer & Pontil, 2009), we have:
N Σ
2 2varN(Y) log 2/6
7 log 2/8
P
Y2/N - E(Y)] 2
< 20
(37)
N
3(N 11]
where var (Y) =
Ful1 mn is the sample variance of Y. Setting e N-1
v log 2/6
N
7 2/8
3(V-1)
P
<
E
V
<
Th N
2 21 - 20
(38)
N
Combining Eq. (36) and Eq. (38), we can further obtain that for any 8 > O, with probability at least
1 28.
Ma N
< E Yil S e1
marr rijk
maz a)) (e2(r mas man a) (1+2d.y)
(39)
i..,
+ 1 dif < 2e Rei(rmaa .T a) 2 (1-
RR/N-
mar mar Ti .))
(40)
From the above analysis, we can obtain two conclusions in the non-deterministic model (finite a) 1) An analogous proposition 1, which centers on the fact that the upper bound of dy decreases as T/s increases. 2) We have succeeded in finding
upper bound on E [Yr]] (with d,y) in the latent space model, which allows us to similarly obtain all the conclusion of the deterministic model, i.c., the theoretical analyses derived from our model are not constrained by
26

---

Published as a conference paper at ICLR 2024
D DESCRIPTIONS ON MORE DATASETS
To ensure the diversity and completeness of our analysis, collect datasets from many different domains, e.g., biology (Watts & Strogatz, 1998; Zhang et al., 2018: Von Mering et al., 2002; Oughtred al., 2019), transport (Batagelj & Mrvar, 2006: Watts & Strogatz, 1998), web (Ackland et al., 2005; Leskovec et al.. 2009; Yang & Leskovec, 2012), academic (Newman, 2006; Leskovec et al., 2007; 2005; Yang & Leskovee, 2012) and social networks (Leskovec & Mcauley, 2012; Leskovec et al., 2010; Richardson et al., 2003). With the domain diversity, the graphs in our datasets also cover large range of types and sizes. Their types include the weighted and the unweighted, the directed and the undirected. The number of nodes in graphs varies from 10 to 10%, while the number of edges varies from 103 to 10". Below is a detailed description of the datasets used:
Selected datasets We first present the selected datasets with ignored factors in the existing bench- marking datasets as mentioned in Section 4.2. The statistics of selected domain datasets are listed in table 3. Power (Watts& & Strogatz, 1998) an electrical grid of western US. Each node represents a tion, and each edge represents a power line between two connected stations. Amazon-phote (Shchur al., 2018) is a portion of the Amazon co-pu co-purchase graph (MeAuley et al., 2015) in which nodes symbolize products. The presence of an edge between two nodes suggests that these products are often purchased together. The features of each node are derived from product reviews using a bag-of-words encoding. Reddit (Zeng et al., 2019) is an undirected graph from the online discussion forum. The nodes represent post, while the edges indicate posts commented by the same user. The node features the bag-of-word representation of the forum. Flicker (Zeng et al., 2019) is an undirected graph originating from NUS-wide. The nodes represent one image uploaded to Flickr, while the edges indicate two images share some common properties (e.g.. same geographic location, same gallery, comments by the same user, etc.). The node features the 5000dimensional bag-of-word representation of the images provided by NUS-wide:
Table 3: Selected Datasets Statistics.
Power
Reddit
Amazon Photo
Flicker
#Nodes
4,941
232,965
7,650
334,863
#Edges
6,594
1 114,615,892
238, 162
899,756
#Feature
NA
602
745
500
Mean Degree
2.67
98.38
6.21
5.69
Split Ratio
80/10/10
80/10/10
80/10/10
80/10/10
Domains
Transport
Social
Web
Social
Table 4: Web Domain Datasets Statistics.
PB
Email-Enron
Amazon Photo
Amazon
Google
#Nodes
1,222
36,692
7,650
334,863
875,713
#Edges
16,714
183,831
238,162
899,756
5,105,039
Mean Degree
27.36
10.02
6.21
5.69
116.49
Split Ratio
80/10/10
80/10/10
80/10/10
80/10/10
80/10/10
Domains
Web
Web
Web
Web
Web
Biology Domain C.ele (Watts & Strogatz, 1998) is an undirected and unweighted neural network of C. elegans. The nodes represent neurons and each edge represents there exists a pathway between two connected neurons. E.coli (Zhang et al., 2018) is an undirected, unweighted metabolic network in E. coli. The nodes represent participating metabolites, and the edges indicate that two connected metabolites interact. Yeast (Von Mering al.. 2002) is an undirected and unweighted protein- protein interaction network in yeast. The nodes represent different kinds of proteins and the edges indicate two proteins interact. The statistics of biology domain datasets are listed in table 5.
27

---

Published as a conference paper at ICLR 2024
Transport Domain USAir (Batagelj & Mrvar, 2006) is weighted, directed network of US Airlines, in which nodes represents airports while weighted edges indicate airline frequency between two airports. Power (Watts & Strogatz, 1998) is electrical grid of western US. Each node represents a station, and each edge represents a power line between two connected stations. The statistics of transport domain datasets are listed in table 6.
Web Domain PB (Ackland al., 2005) is a directed network of US political blogs, where the nodes represent blogs and the directed edges represent links from one blog to another. Email- Enron (Leskovec et al., 2009) is directed, unweighted graph covering around half million emails. The nodes represent email addresses, and the edges indicate that an address sends an email to another. Amazon (Yang & Leskovec, 2012) is an undirected and unweighted graph constructed by Amazon shopping data. The nodes represent products while the edges indicate two connected nodes are used to be bought together. Google (Leskovec et al., 2009) a directed, unweighted graph of website hyperlinks. The nodes represent websites, while the edges indicate that website has link to another. The statistics of web domain datasets are listed in table 4.
Academic Domain NS (Newman, 2006) is an unweighted and undirected network of collaboration of researchers in network science, where nodes represent scientists and edges represent collaborating relationships. Ca-AstroPh (Leskovec et al., 2007) is an undirected, unweighted collaboration network from the e-print arXiv and covers scientific collaborations between authors papers submitted to Astro Physics category. The nodes represent authors and the edges represent the co-authorship. Ca- MatCondMat (Leskovec et al., 2007) is an undirected, unweighted collaboration network from the e-print arxiv and covers scientific collaborations between authors papers submitted to Condense Matter category. The nodes represent authors and the edges represent the co-authorship. Cit- HepPh (Leskovec al., 2005) is directed and unweighted citation graph from the e-print arXiv. The nodes represent papers and the edges indicate that a paper is cited by another. DBLP (Yang & Leskovee, 2012) is an undirected, unweighted collaboration network from the computer science domain. The nodes represent authors and the edges represent the co-authorship. The statistics of academic domain datasets are listed in table 7.
Social Domain Facebook (Leskovec & Mcauley, 2012) a undirected, unweighted social network. The nodes represent users, and the edges represent friendship relation between any two users. Vote (Leskovec et al., 2010) is a directed, unweighted graph of a wiki vote. The nodes represent participants, while the edges indicate the participants vote for one another. Epinions (Richardson et al., 2003) is a directed, unweighted who-trust- whom online social network on which users could decide whether to "trust" each other. Each node represents user, and each edge indicates whether user trusts another or not. Slashdot (Leskovec et al., 2010) is an directed, weighted social network. The nodes represent users, while the edges indicate whether the user thinks another is friend or foe. The statistics of social domain datasets are listed in table 8. Reddit (Zeng et al., 2019) is an undirected graph from the online discussion forum. The nodes represent post, while the edges indicate posts commented by the same user. The node features the bag-of-word representation of the forum. Flicker (Zeng et al., 2019) an undirected graph originating from NUS-widk The nodes represent one image uploaded to Flickr, while the edges indicate two images share some common properties (e.g., same geographic location, same gallery, comments by the same user, etc.). The node features the 500-dimensional bag-of-word representation of the images provided by NUS-wide. Amazon-photo (Shchur et al., 2018) is a portion of the Amazon co- porchac graph (McAuley et al., 2015) in which nodes symbolize products. The presence of edge between two nodes suggests that these products are often purchased together. The features of each node are derived from product reviews using bag-of-worre encoding.
E ADDITIONAL RESULTS IN MAIN ANALYSIS
Additional analysis on whether heuristics offer unique perspectives In Section 3.1, we conduct an analysis on the complementary effect of different factors. Additional results on Cora and CiteSeer are shown in Figure 7. More results with Hit@ 10 metric can be found in Figures 8 and 9. Similar observations can be found.
28

---

Published as a conference paper at ICLR 2024
Table Biology Domain Datasets Statisties.
C.ele
E.coli
Yeast
#Nodes 297
1,805
2,375
#Edges
2,148
14,660
11,693
Mean Degree
14.46
12.55
9.85
Split Ratio
80/10/10
80/10/10 Biology
80/10/10 Biology
Domains
Biology
Table 6: Transport Domain Datasets Statistics.
USAir
Power
#Nodes
332
4,941
#Edges
2,126
6,594
Mean Degree
12.82
2.67
Split Ratio
80/10/10
80/10/10
Domains
Transport
Transport
Additional analysis the overlooked weakness in GNN4LP models In Section 3.4, conduct an analysis that find the overlooked weakness in GNN4LP models. Additional comparison results with GraphSAGE are shown in Figure ??. Results of the comparison with GCN are shown in Figure 10. Similar observations can be found.
Data Analysis section 1, we exhibit the data disparity via the distribution of CN scores on different datasets. In this section, provide more analysis across GSP, LSP, and FP factors in Figure 11. Similar data disparities can be found. Similar observations can be found.
F ADDITIONAL ANALYSIS AMONG DATA FACTORS
In Section 3.1, we analyze the significance of link prediction and the complementary effect among them. In this section, we provide further analysis for integrating all these factors for holistic view. We ultimately investigate whether those data factors could provide a complete view for link prediction with no neglected factors. Typically, we examine whether heuristics derived from different data factors share similar hard negative pairs. The hard negative pairs, the top-ranked negative pairs, pose the main obstacle to link prediction. The negative pair set can denoted as & where i indicates the i-th heuristic algorithm. We conduct experiments examine the proportion of hard negative edges remaining after including more data factors. The experimental results are shown in Figure 12. The y-axis is the proportion of remaining hard negative edges. It can be calculated as [nacSEal where is [Ea the set of heuristic algorithms, Eg is the hard negative edges of the basis heuristic algorithm. The x-axis indicates heuristic algorithms derived from different data factors. Looking x-axis from left to right, gradually add new heuristics into the candidate heuristic set, beginning with single basic algorithm. We can find that when adding each heuristic with a new factor, e.g., adding CN algorithm, the ideal performance increases substantially, indicating the significance of each factor and its complementary effects. Such observations indicate a complete view of those three factors with factor neglected.
G LIMITATION
is important to acknowledge certain limitations our work despite our research providing valuable insights on unveiling the underlying factors across different datasets for the link prediction. Notably, there are a series of heuristic algorithms revolving around each factor while we only focus on a few typical ones. To this end, show experimental results in Section 3.1. It provides more concrete discussion on the overlapping of heuristic algorithms revolving around the same factors. Nonetheless, there may still remain potential for some ignored heuristic algorithms.
29

---

Published as a conference paper at ICLR 2024
GSP
GSP
0.68
0.019
0.014
0.73
0.0068
0.022
LSP
LSP
0.023
0.74
0.014
0.026
0.75
0.014
FP
0.012
0.0059
0.57
FP
0.021
0.011
0.64
GSP
LSP
FP
GSP
LSP
FP
Cora
(b) Citeseer
Figure 7: Overlapping ratio between top ranking edges (top 25%) on different heuristic algorithms. Diagonals are the comparison between two heuristies within the same factor, while others compare between heuristics derived from different factors. Experiments are conducted the hit @ 10 metric
GSP
GSP
0.68
0.44
0.052
0.73
0.32
0.016
LSP
LSP
0.49
0.74
0.29
0.35
0.75
0.19
FP
0.029
0.31
0.57
FP
0.027
0.23
0.64
GSP
LSP
FP
GSP
LSP
FP
(a) Cora
(b) Citeseer
GSP
GSP
0.65
0.32
0.025
0.85
0.45
0.38
LSP
LSP
0.4
0.8
0.2
0.37
0.66
0.32
FP
0.031
0.23
0.55
FP
0.42
0.36
0.73
GSP
LSP
FP
GSP
LSP
FP
(c) Pubmed
(d) Ogbl-collab
Figure 8: Overlapping ratio between top ranking edges (top 25%) on different heuristic algorithms utilizing Hit@ 10 metric. Experiments conducted on Cora. Citeseer, Pubmed and Ogbl-collab. Diagonals are the comparison between two heuristics within the same factor, while others compare between heuristics derived from different factors.
30

---

Published as a conference paper at ICLR 2024
Table 7: Academic Domain Datasets Statistics.
NS
Ca-AstroPh
Ca-ConMat
Cit-HepPh
DBLP
#Nodes
1,589
18,772
23,133
34,546
317,080
#Edges
2,742
5,105,039
93,497
421,578
1,049,866
Mean Degree
3.45
543.90
8.08
24.41
6.62
Split Ratio
80/10/10
80/10/10
80/10/10 Academic
80/10/10
80/10/10
Domains
Academic
Academic
Academic
Academic
Table 8: Social Domain Datasets Statistics.
Facebook
Vote
Epinions
Slashdot
Reddit
Flickr
#Nodes
4,039
7,115
75,879
82,140
232,965
89,250
#Edges
88,234
103,689
508,837
549,202
1 114,615,992
925,872
Mean Degree
43.69
29.15
13.41
13.37
98.38
20.75
Split Ratio
80/10/10
80/10/10
80/10/10
80/10/10
80/10/10
80/10/10
Domains
Social
Social
Social
Social
Social
Social
In order to facilitate a more feasible theoretical analysis, we have made several assumptions, the most significant is that separately examine the effect from feature and structure. Typically, model the feature proximity as an additional noise parameter. The correlation between feature and structure perspectives is only analyzed on the confiit on their effects on link prediction. Such an assumption is subject to notable drawback since it ignores the correlation between features and existing structural information. It restricts the generality of our theoretical analysis. Moreover, when analyzing the effectiveness of global structural proximity with the number of paths rather than the number of random walks. Paths are deterministic and non-repetitive sequences connecting two points, while random walks are probabilistic sequences with repeat. Extension to the random walks should be the next step.
Our current findings lay strong foundation for further exploration. It is worth mentioning that our theoretical analysis predominantly focuses on data perspective. We only show an empirical comparison between vanilla GNN and GNN4LP models, while lacking theoretical analysis from model perspective. The major obstacle is that the GNN4LP model design is too diverse, making difficult analyze comprehensively.
We hope that these efforts will contribute significantly to the Link Prediction research community. Moving forward, aspire broaden our findings encompass more advanced GNN4LP algorithm design, with particular emphasis on the conflict effects on feature similarity and structural similarity. Besides, the guidance we provided on the dataset selection depends entirely on the existing but ignored datasets. We acknowledge that there may still be graphs with distinguishing properties from domains not considered in our work.
H BROADER IMPACT
Link prediction is of the fundamental tasks with multiple applications in the graph domain. Recently, various GNN4LP models have been proposed with state-of-the-art performance. A key aspect of GNN4LP models is capture pairwise structural information, e.g. neighborhood over- lapping features. In this study, we find that, despite GNN4LP models being more expressive to capture pairwise structural patterns, they inherently reveal performance degradation on those edges without sufficient pairwise structural information. Such characteristics may lead to biased test prediction. For example, social media utilize GNN4LP models to recommend friends a social network, introverts with fewer friends will receive low-quality recommendations. Such flaws lead to bad experiences with obstacles for introverts. Therefore, a vicious spiral happens leading to worse situations. Our research offers understanding of these limitations rather than introducing methodology or approach. We identify the overlooked problem and show the potential solution to address this issue. Consequently, do not foresee any negative broader impacts stemming from
31

---

Published as a conference paper at ICLR 2024
GSP
GSP
0.67
0.27
0.55
0.2
LSP
LSP
0.35
0.52
0.22
0.65
GSP
LSP
GSP
LSP
(a) Oghl-ddi
(h) Ogbl-ppa
Figure 9: Overlapping ratio between top ranking edges (top 25%) on different heuristic algorithms utilizing hit@ 10 metric. Experiments are conducted on Ogbl-ppa and Ogbl-ddi. Diagonals are the comparison between two heuristics within the same factor, while others compare between heuristics derived from different factors.
BUDDY
NeoGNN
NCNC
BUDDY
NeoGNN
NCNC global
local
global
local
0.1
0.1
Difference in hit model GCN
Difference in hit model GCN
0.0
0.0
-0.1 -0.1
-0.1
-0.2
Teat
struct
Teat
struct
Teat
struct
Teat
struct
(a) Cora
(b) Citeseer
BUDDY
NeoGNN
NCNC
BUDDY
NeoGNN
NCNC
local
global
local
global
Difference in hit model -GCN
0.2
Difference in hit model GCN
0.2
0.1
0.0
0.0
0.0
0.0
-0.1
feat
struct
feat
struct
Teat
struct
feat
struct
(c) PubMed
(d) ogbl-collab
Figure 10: Performance comparison between GNN4LP models and vanilla GCN. Two bar groups rep-
resent the performance gap on node pairs dominated by feature and structural proximity, respectively. Two sub-figures correspond compare FP with GSP and LSP, respectively. Vanilla GraphSAGE often outperforms GNN4LP models on node pairs dominated by feature proximity while GNN4LP models outperform those dominated by structural proximity.
our findings. We expect our work to contribute significantly to the ongoing research efforts aimed at enhancing the versatility and fairness of GNN models when applied to diverse data settings.
32

---

Published as a conference paper at ICLR 2024
Cora Citeseer
Pubmed ogbl-collab
ogbl-ppa ogbl-ddl
Cora
Pubmed
Citeseer
ogbl-collab
Propotion
Propotion
0
3
(a)
(b) FH
Cora
Pubmed
ogbl-ppa
Cora
Pubmed
ogbl-pps ogbl-ddi
Citeseer
ogbl-collab
ogbl-ddi
Citeseer
ogbl-collab
Propotion
Propotion
3
5
(c) SimRank
(d) PPR
Figure 11: Distribution disparity of different heuristic scores across datasets
Pubmed
Cora Cihesees
Pubmed collab
Cress
Pulmed cillab
Cileseec
remaining ratio
1.0
remaining ratio
1.0
0.8
0.8
0.8
remains
0.66
0.6
0.2
GSP
LSP
FP
GSP
FP
(a) FP
(b) GSP
(c) LSP
Figure 12: The impact various heuristic algorithms on the proportion of remaining hard negative edges. The y-axis depicts the remaining hard negative proportion, calculated as [NtesEa where & represents hard negative edges from the basic heuristic, the title for each subfigure. Moving from left to right on the x-axis, more heuristics are incrementally added, starting from a basic one.
[ol
I FUTURE DIRECTION
In section 1, we show how our understanding can help guide the model design and dataset selections. worth noting that our findings can derive new understandings and inspire us identify new problems in link prediction with future opportunities. We further illustrate more understanding and initial thoughts on the future of link prediction as follows.
Dataset categorization for Link Prediction. In work, we identify datasets with different data factors based on the performance of the test set, and ease analysis. However, test edges are not available in real-world scenarios. How to identify data factors becomes essential problem. One potential direct solution to utilize the validation set. After identifying the correct direction, we can then select suitable model for link prediction.
33

---

Published as a conference paper at ICLR 2024
Specific GNN4LP design for graphs in particular domain. instead of viewing the link prediction as a whole problem, we suggest decoupling this problem and designing specific models for graphs with different factors. For instance, the specific GNN4LP model should be designed for dense graphs like OGBI--DII and OGBI.-PPA.
Automatic Machine Learning Link Prediction. With specifie model designs graphs with different categories, we can then combine all those components for automatical model architecture selection. The selected model should be able adaptively decide what type of factors to use, thereby tailoring the pairwise encoding to each individual. It also allows non-experts to benefit from data-driven insights without expert knowledge.
Inherent connection between node classification and link prediction. Notably, homophily is concept popularly discussed in node classification while it is largely ignored in GNN4LP models. The interplay between homophily in link prediction and node classification is a chicken-egg problem. More specifically, link prediction considers that nodes with similar features are likely be connected. In contrast, node classification considers nodes connected are likely to share similar features. Such a relationship indicates that the principles for node classification and link prediction may benefit from each other. Recently, there has been attempt (Liu et al., 2023) utilizing principle in link prediction for node classification. Nonetheless, there is still lack of exploration on the other side, utilizing the principle of node classification for link prediction.
Fairness problem in Link Prediction. In section 3.4, we find the drawback of GNN4LP models over vanilla GNNs. While the overall performance is promising, GNN4LP models may not be satisfying. However, such bias leads to can potentially affect the fairness of the models in real-world applications as discussion in Appendix H. There should be systematical task design for the fairness problem on link prediction.
Extension to Network Evolution. Network evolution (Zaheer & Soda, 2009) is about understanding and modeling how networks change over time. This includes the formation of new links as well as the deletion of existing ones. The link prediction considers the network at fixed point in time and doesn't I account for how the network might evolve and grow temporally. Moreover, link prediction generally only considers link addition while ignoring the link deletion. We leave extending our understanding of link prediction to network evolution as the future work. The core future steps for extension are:
link deletion: Despite considering node pairs with high proximity to be more likely to be connected, we need to extend verify that node pairs with low proximity are more likely to be deleted.
Temporal feature: Network evolution introduces the time-series feature, considers capturing the time evolution features of link occurrences, and predicts the link occurrence probability. Temporal proximity will be an additional data factor besides the existing three data factors.
More application in recommendation. The recommendation (Fu et al., 2022; Wang et al., 2019a; He et al., 2020) can be viewed as a particular link prediction problem on the bipartite graph between users and items. Nonetheless, the graph is generally much more sparse. The mechanism underlying such a specific link prediction problem remains unknown.
J DATASETS DETAILS
Table 9; Datasets Statistics.
Cora
Citeseer
Pubmed
ogbl-collab
ogbl-ddi
ogbl-ppa
#Nodes
2,708
3,327
18,717
235,868
4,267
576,289
#Edges
5,278
4,676
44,327
1,285,465
1,334,889
30,326,273
Mean Degree
3.9
2.81
4.74
10.90
625.68
105.25
Split Ratio
85/5/10
85/5/10
85/5/10
92/4/4
80/10/10
70/20/10
Domains
Academic
Academic
Academic
Academic
Chemistry
Biology
34

---

Published as a conference paper at ICLR 2024
The basic dataset statisties are shown in Table 9. Notably, three planetoid datasets, CORA, CITESEER, and PUBMED are smaller toy datasets while OGB datasets (Hu et al., 2020) have much more nodes and edges. We include most of the OGB datasets except for ogbl-citation2. The reason is that the standard evaluation method for ogbl-citation2 is different from other datasets (1) Most datasets adopt shared negative sample setting where all positive samples share the same negative sample set. In contrast, each positive sample in ogbl-citation2 corresponds to an individual negative sample set. (2) The ogbl-citation2 dataset utilizes MRR as the default evaluation metric rather than @ir@ K in other datasets. Moreover, we can still achieve a convincing empirical conclusion without ogbl- ogbl-citation2 since there still remain four citation graphs with varied sizes.
For the data split, we adapt the fixed split with percentages 85/5/10% for planetoid datasets, which can be found at http:///ihuub..oomuuuuu//// provided by the OGB benchmark (Hu et al., 2020).
For OGB datasets, we use the fixed splits
K
EXPERIMENTAL SETTINGS & MODEL PERFORMANCE
K.1 EXPERIMENTAL SETTINGS
We provide implementation details in the following section. Code for our paper can be found in https:/anonnyous.4oom www.ouus.oppe.scinneeeeeeeeeeeee Seaancee/LiinPPPdiitio------ Notably, we adopt all the settings and implementation from the recent Link Prediction benchmark (Li et al., 2023) for a fair comparison. Codes can be found at httpgggiuuhhoo//uuuuuii2i/
More details are shown as follows.
Training Settings. The binary cross entropy loss and Adam optimizer (Kingma & Ba, 2014) are utilized for training. For each training positive sample, we randomly select one negative sample for training. Each model is trained with maximum of 9999 epochs with the early stop training strategy. We set the early stop epoch to 50 and 20 for planetoid and OGB datasets, respectively.
Evaluation Settings For OGB datasets, utilize the default evaluation metrics provided by (Hu et al., 2020), which are Hits @ 50, Hits 20, Hits 100 for OGBL-COLLAB OGBL-DDI, and OGBL-PPA datasets, respectively. For planetoid datasets, we utilize Hit@1 10 as the evaluation metric.
Hardware Settings The experiments are performed on one Linux server (CPU: Intel(R) Xeon(R) CPU E5-0 v4 @ @2.60GHz, Operation system: Ubuntu 16.04.6 LTS). For GPU resources, eight NVIDIA Tesla V100 cards are utilized The Python libraries we use to implement our experiments are PyTorch 1.1 and PyG 2.0.p..
Hyperparameter Settings. For deep models, the hyparameter searching range is shown in Table 10. The general hyperparameter search space is shown in Table 10. The weight decay, number of model and prediction layers, and the embedding dimension are fixed. Notably, several exceptions occur in the general search space resulting significant performance degradations. Adjustments are made with the guidance of the optimal hyperparameters published in the respective source codes. This includes:
NCNC (Wang et al., 2023): When training on OGBI.-DDI, we adhere to the suggested optimal hyperparameters used in the source code. Specifically, we the number of model layers to be 1, and we don't apply the pretraining for NCNC to facilitate a fair comparison.
SEAL (Zhang & Chen, 2018): Due to the computational inefficiency of SEAL, when training CORA, CITESEER and PUBMED, further fix the weight decay to O. Furthermore, adhere to the published hyperparameters 3 and fix the number of model layers to be 3 and the embedding dimension be 256.
BUDDY (Chamberlain et al., 2023): When training on OGBL-PPA, incorporate the RA and normalized degree as input features while excluding the raw node features. This is based on the optimal hyperparameters published by the authors."
35

---

Published as a conference paper at ICLR 2024
Table 10: Hyperparameter Search Ranges
Datusel
Learning Rate
Dropout
Weight Decay
Model Layers
Prediction Layers
Embedding Dim
Cora
(0.01. 0.001)
(0.1, 0.3, 0.5)
(1c-4, le-7, 0)
(1, 3)
21,
(128, 256)
Citesecr
(0.01. 0.001)
00.1, 0.5)
(1c-4, Ic-7, 0)
(1, 3)
(1
(128, 256)
Pubmed
(0.01. 0.001)
(0.1.03.0.5)
(Ic-4, Ie-7, 0)
(1,
(1,
(128, 256)
ogbl-collab
(0.01, 0.001)
(0, 0.3, 0.5)
0
3
256
ogbl-ddi
(0.01, 0.001)
(0, 0.5)
3
256
ogbl-ppa
(0.01, 0.001)
(0, 0.3, 0.5)
256
K.2 MODEL. PERFORMANCE
We include baseline models that are both representative and scalable most datasets. Models like NBFNet (Zhu et al., 2021b) are not included since they meet severe out-of-memory issue on those larger OGB datasets. The detailed model performance is shown in Table 11, Since the ogbi-ddi has no node features, we mark the MLP results with a "N/A". Notably, there is no consistent winning solution across different settings. All results except for SimRank, PPR, and FH are from Li al. (2023).
Table 11: Model performance on Cora, CiteSeer, Pubmed, and OGB datasets.
Cora
Citeseer
Pubmed
Ogbl-collab
Ogbl-ddi
Ogbl-ppa
CN
42.69
35.16
27.93
61.37
17.73
27.65
AA
42.69
35.16
27.93
64.17
18.61
32.45
42.69
35.16
27.93
63.81
6,23
49.33
Katz
51.61
57.36
42.17
64,33
17.73
27.65
SimRank
50.28
52.52
37.03
21.75
OOM
OOM
PPR
32.96
31.88
32.84
54.53
7.19
4.97
FH
47.13
48.19
34.57
23.92
4.74
NA
MLP
53.59 + 3.57
69.74 + 2.19
34.01 + 4.94
35.81 + 1.08
N/A
0.45 + 0.04
GCN
66.11 + 4.03
74.15 + 1.70
56.06 1 4.83
54.96 + 3.18
49,90 + 7.23
29.57 + 2,90
SAGE
63.66 + 4.98
78.06 + 2.26
48.18 4.60
59.44
1.37
49.84 + 15.56
41.02 = 1.94
NeoGNN
64.10 4.31
69.25
1.90
20.95 6.03
48.45 1.01
BUDDY
59.47 1: 5.49
2.27
46.62
4.58
64.59 1 0.46
29.60 4.75
47.33 1.96
NCNC
75.07 + 1.95
82.64 1.40
61.89 3.54
65.97 = 1.03
70.23 + 12.11
62.64 = 0.79
36


Reviews:
[{"review_id": "zqytyfyWKc", "reviewer": "Reviewer_zuoh", "summary": "This paper studies the reasons why GNNs largely fail to deliver on the task conventionally called \"link prediction\", which is the task of recovering, rather than \"predicting\", missing links in a graph, from a data-oriented perspective. It suggests than the task of link recovery depends on three factors, namely the local structral proxmimity of nodes, their global structural proximity, and their feature proximity, and examines how these three factors interrelate. The core finding of the study is that conventional GNNs for link prediction fail when the feature proximity factor becomes dominant. Given these insights, the paper offers advice on how one could select data for selecting benchmark data to evaluation GNNs for link recovery.", "questions": "Is the proposed latent space different from a node embedding, and if so, why?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 1, "strengths": "Drawing from previous work, the paper suggests and reconfirms the importance of three key factors underlying the task of link recovery and proposes a latent space model that effectively embeds nodes in a D-dimensional space, which is used to analyze the relationships among the proposed data factors, revealing an underlying tension between feature proximity and local structural proximity, in other words, the fact that co-occurrence of both high feature similarity and high local structural similarity rarely happens. This is an interesting empirical finding.", "weaknesses": "The core finding of the paper is the features should also be taken in consideration. This finding has been known to the community, especially when it comes to using embeddings for link recovery. The proposed latent space model looks suspiciously similar to a node embedding used for link recover. As such, it calls for comparison with state-of-the-art works on embeddings for that purpose, which examine pretty much the same issues as this paper. Such a comparison or even discussion of the relationship and underlying novelty is missing.", "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": "EMRXyylcYE", "reviewer": "Reviewer_Rht2", "summary": "This paper explores the principles of link prediction in graphs from a data-centric perspective. It identifies three critical factors for link prediction: local structural proximity, global structural proximity, and feature proximity. The paper reveals relationships among these factors and highlights an incompatibility between feature proximity and local structural proximity. This insight has implications for the performance of Graph Neural Networks for Link Prediction (GNN4LP) models. The study offers practical guidance for model design and benchmark dataset selection in the field of link prediction.", "questions": "see the weaknesses", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1.  The paper takes a unique data-centric approach to the problem of link prediction, shifting the focus from model design to understanding the underlying data factors. This perspective is essential for providing valuable insights into the link prediction task and guiding future research.\n2.  The paper identifies and empirically validates three critical factors for link prediction: local structural proximity, global structural proximity, and feature proximity. This systematic analysis enhances our understanding of what influences link formation in graphs, contributing to a more comprehensive approach to link prediction.\n3. The revelation of an incompatibility between feature proximity and local structural proximity in link prediction is a significant finding. It highlights a vulnerability in existing GNN4LP models and suggests that certain links, primarily driven by feature similarity, may be challenging to predict accurately. This insight provides researchers with a new perspective on model limitations and opportunities for improvement.", "weaknesses": "1. The paper introduces a latent space model for link prediction and provides theoretical guarantees for the identified data factors. Nonetheless, why to use such model is still so clear and motivated\n2. Instead of hit metric, mrr is also very important for link prediction. It could be better if there is additional analysis on MRR\n3. The work somehow shows correlation with the network evolution. Can you add some detailed discussion with the network evolution especially the dynamic case?", "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": "99RIcWcRmR", "reviewer": "Reviewer_wtEd", "summary": "This is a benchmark paper on link prediction. The authors experiment comprehensively and come to some interesting obervations. In the first part, the authors analyze the data perspective from three heuristics (1)Local structural proximity(LSP) (2)Global structural proximity(GSP) (3) Feature proximity(FP). Two natural questions are studied: how much does each help and whether they have overlappings. Then the authors introduce a latent space model and then theoretically demonstrate that the model reflects the effectiveness of LSP, GSP, and FP factors.  Then, based on the undetstandings of the heuristic groups, the authors provide practical guidelines from model and data perspective.", "questions": "1. What is the role of heterophily when calculating Feature proximity? Moreover, could you give an example in homophilic graph that FP and LSP are conflictive or FP and GSP are conflictive. I am asking this because I feel the conflict comes from the different link forming mechanism where FP is just not appropriate.\n2. I am not quite sure but I think NeurIPS D&B track and TMLR might be more appropriate venues.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The writing is easy to follow and the paper presentation is clear\n2. The overall motivation is clear and the work is comprehensive. Both experiments and analysis look good.", "weaknesses": "I'd thank the authors to elaborate more on my questions below.", "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": "23VYGivakH", "reviewer": "Reviewer_cwp2", "summary": "The paper analyzes link prediction across diverse datasets from a data-centric perspective. Specifically, it considers that a link can be generated through Local structural proximity (LSP), Global structural proximity (GSP), and Feature proximity (FP). The experiments show discrepancies in the top-ranked edges according to the selected features. The paper suddenly changes to the proposition of a model based on feature proximity, latent node pairwise distance, and some hyperparameters. The paper supports this model claiming that node pairs with a large number of common neighbors tend to have low feature proximity and vice versa, and that this phenomenon is given once the network has been already formed over time. Finally, the paper suggests considering the feature space and structural space by different models and combining them at the end.", "questions": "Can you make the paper readable by itself using 9 pages in length?\nThanks for changing the paper.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "The paper shows a very significant result and contribution, that LSP, GSP, and FP should be considered differently when they are used for link prediction. More details about this conclusion are given, and it will be important to clearly define the time in this conclusion. As it is mentioned in the paper, the claim is based on a given network, that has already made several connections among them. \n\nThe proposition of the new theoretical model is interesting but not so novel. I mean, while the combination of LSP, GSP, and FP has been largely considered, the novelty is the inclusion of these characteristics in a different factor (more important to FP when nodes have a large distance and vice versa).", "weaknesses": "Readability. As it is stated in the submission instructions \"reviewers are not required to read the appendix\". In this case, I did not read the appendix. For this reason, I could understand specific details from the paper. While I understand the main idea, there are details, such as the parameter r that I could not understand. Unfortunately, the paper uses the appendix to explain very important parts of the paper; for example: \"Limitation, broader impact, and future works are in Appendix G, H, and I\". So, if you can not reduce and contain the paper to 9 pages, I suggest you submit the paper to a journal, instead of a conference. Note, I usually read the appendices of the paper. They usually have important proof and complementary results, but in this case, it is being used as a main part of the paper. \n\nThe details of the theoretical models are not explained in the main paper. There are several details without any type of information, for example, the parameter r. It seems then rather than a parameter, r is a hyperparameter, but no details about this are given in the main paper. I have similar issues with the \\beta parameter/hyperparameter, which is described as a feature proximity parameter, but no details about its calculation or suggestion are given. \n\nI understand the main idea of the theoretical model and its importance in the paper, but this is not used in the experiment section of the main paper.", "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)