A Topological Perspective on Demystifying GNN-Based Link Prediction Performance
Authors: Yu Wang
Tong Zhao
Yuying Zhao
Yunchao Liu
Xueqi Cheng
Neil Shah
Tyler Derr
Venue: ICLR 2024 poster (2024)
Keywords: Link prediction; Graph Topology; Graph Neural Network ; Cold-start Issues
Primary area: learning on graphs and other geometries & topologies
TL;DR: We propose a new node-level topological metric, Topological Concentration, to understand the relationship between node local topology and its GNNs' link prediction performance

Abstract: Graph Neural Networks (GNNs) have shown great promise in learning node embeddings for link prediction (LP). While numerous studies improve the overall GNNs' LP performance, none have explored their varying performance across different nodes and the underlying reasons. To this end, we demystify which nodes perform better from the perspective of their local topology. Despite the widespread belief that low-degree nodes exhibit worse LP performance, we surprisingly observe an inconsistent performance trend. This prompts us to propose a node-level metric, Topological Concentration (TC), based on the intersection of the local subgraph of each node with the ones of its neighbors. We empirically demonstrate that TC correlates with LP performance more than other node-level topological metrics, better identifying low-performing nodes than using degree. With TC, we discover a novel topological distribution shift issue in which nodes' newly joined neighbors tend to become less interactive with their existing neighbors, compromising the generalizability of node embeddings for LP at testing time. To make the computation of TC scalable, We further propose Approximated Topological Concentration (ATC) and justify its efficacy in approximating TC with reduced computation complexity. Given the positive correlation between node TC and its LP performance, we explore the potential of boosting LP performance via enhancing TC by re-weighting edges in the message-passing and discuss its effectiveness with limitations. Our code is publicly available at https://github.com/YuWVandy/Topo_LP_GNN.

Published as a conference paper at ICLR 2024
A TOPOLOGICAL PERSPECTIVE ON DEMYSTIFYING CNN-BASED LINK PREDICTION PERFORMANCE
Yu Wang', Tong Zhao?, Yuying Zhao', Yunchao Liu', Xueqi Cheng', Neil Shah?, Tyler Derr'
Vanderbilt University Snap Inc. (yu. wang. , 1, yuying. zhao, yunchac.... 1iu, xweqi. tyler. www.reeeeeeveeeeritt...o (tzaac, nshah) (acaph)ssap....
ABSTRACT
Graph Neural Networks (GNNs) have shown great promise in learning node em- beddings for link prediction (LP). While numerous studies improve the overall GNNs' LP performance, none have explored their varying performance across different nodes and the underlying reasons. To this end, we demystify which nodes perform better from the perspective of their local topology. Despite the widespread belief that low-degree nodes exhibit worse LP performance, we sur- propose
prisingly observe inconsistent performance trend. This prompts a node-level metric, Topological Concentration (TC), based on the intersection of the local subgraph of each node with the ones of its neighbors. We empiri- cally demonstrate that TC correlates with LP performance more than other node- level topological metrics, better identifying low-performing nodes than using de- gree. With TC, we discover a novel topological distribution shift issue in which nodes' newly joined neighbors tend become less interactive with their exist- ing neighbors, compromising the generalizability of node embeddings for LP at testing time. To make the computation of TC scalable, We further propose Ap- proximated Topological Concentration (ATC) and justify its efficacy in approxi- mating TC with reduced computation complexity. Given the positive correlation between node TC and its LP performance, we explore the potential of boosting LP performance via enhancing TC by re-weighting edges in the message- peessage-aassing and discuss its effectiveness with limitations. Our code is publicly available at https://github.com/ Y Vandy/Topo LP GNN
INTRODUCTION
Recent years have witnessed unprecedented success in applying link prediction (LP) in real-world applications (Ying et al.] [2088] Rozemberczki et al. (022). Compared with heuristic- based (Brin &
Liben-Nowell & Kleinberg (203)) and shallow embedding- based LP approaches (Per- 2014 Grover & Leskovee 2016). GNN-based ones (Zhang & Chen 2018 Chamber- lain et al.
Page
1998
077i et al.
2022) have achieved thate-of-the-art (SOTA) performance; these methods first learn node/subgraph embeddings by applying linear transformations with message-passing and a de- coder/pooling layer to predict link scores/subgraph class. While existing works are dedicated to boosting overall LP performance (Zhao al. 2022 Chen al. (021b) by more expressive message- passing or data augmentation. it is heavily under-explored whether different nodes within a graph would obtain embeddings of different quality and have varying LP performance.
Previous works have explored GNNs' varying performance on nodes within graph, considering factors like local topology (e.g., degree and homophilyhhetrrophit) (Tang et al. 2020 Mao et al., 2023), feature quality (Taguchi et al.] (2021), and class quantity (Zhao et al. 202 While these studies have provided significant insights, their focus has primarily remained on node/graph-Ievel tasks, leaving the realm of LP unexplored. A more profound examination of the nary-narying LP performance can enhance our comprehension of network dynamics (Liben-Nowel) & Kleinberg, 2003), facilitate timely detection of nodes with ill-topology (Lika et al.) 2014), and inspire cus- tomized data augmentation for different nodes (Zhao et al. (2021b). Recognizing the criticality of studying the node-varying LP performance and the apparent gap in the existing literature, we ask:
Can we propose metric that measures GNNs' varying L.P performance across different nodes?

---

Published as a conference paper at ICLR 2024
Preciise
NDCG
Reail
XBOX
Iiles
3.59
1454
190, 1891
[168.20
[24),000
400)
[9.
[9)
19,39
(3,37) [It (3,,5) (5,39) 1st (at.a
Grasply
Groap Trantey Deam
Collab Performance degree groups
(b) Citation2 Performance degree groups
10.70
(12,10) 114,10 11A, (1K,3]
Greepite Teth
Tranitng 7rth Heginn
(c) Collab - Performance for low-degree groups
(d) Citation2 - Performance for low-degree groups
Figure 1: Average LP performance of nodes across different degree groups based on Degree node degree by training edges) on Collab/Citation2. In (a)-(b), Performance@ @ 10 does not increase as the node degree increases. In (c)-(d), few/lower-degree nodes do not perform worse than their higher-degree counterparts. Detailed experimental setting included in Appendix F
To answer analogous question in node classification, prior works observed that GNNs perform better on high-degree nodes than low-degree nodes (Tang et al.] 2020 Liu et al.] 2021I. Simi- larly, the persistent sparse topology issue in the general LP domain and recommender systems (Hao et al., [021] [i et af., (202T) indicates that nodes with zero-to-low degrees lag behind their high- degree counterparts. However, as surprisingly shown in Figure [a)-(b), GNN-based LP on these two large-scale social networks does not exhibit a consistent performance trend as the node degree increases. For example, the performance 10 on Collab under all evaluation metrics decreases as the node degree increases, while on Citation2, performance @ 10 first increases and then decreases. This counter-intuitive observation indicates the weak correlation between the node degree and LP performance, which motivates to design a more correlated metric to answer the above question.
Following (Zhang& Chen 2018) that the link formation between each pair of nodes depends on the interaction between their local subgraphs, we probe the relation between the local subgraphs around each node and its GNN-based LP performance. Specifically, we propose Topological Concentration (TC) and its scalable version, Approximated Topological Concentration (ATC), to measure the topo- logical interaction between the local subgraph of each node and the local subgraphs of the neighbors of that node. Our empirical observations show that TC offers superior characterization of node LP performance in GNNs, leading to 10% more correlation with LP performance and roughly 200% increase in the performance gap between the identified under-performed nodes and their counterparts than degree. Moreover, with TC. we discover a novel topological distribution shift (TDS) in which newly joined neighbors of node tend become less interactive with that node's existing neigh- bors. This TDS would compromise the generalizability of the learned node embeddings in LP at the testing time. Given the closer correlation between TC and I.P performance, we reweigh the edges in message-passing to enhance TC and discuss its efficacy/limitaiions in boosting LP performance. Our contributions are summarized as follows:
We propose Topological Concentration (TC) and demonstrate it leads to 10% more correlation with LP performance and roughly 200% increase the performance gap between the identified pnder-performed nodes and their counterparts than node degree, shedding new insights degree- related issues in LP. We further propose Approximated Topological Concentration (ATC) and demonstrate it maintains high correlations to the LP performance similar to TC while significantly reducing the computation complexity.
We uncover a novel Topological Distribution Shift (TDS) issue according to TC and demonstrate its negative impact at the node/graph level for link prediction at the testing time. Moreover, we discover that different nodes within the same graph can have varying amounts of TDS.
We design TC-inspired pessage-passingg where node aggregates more from neighbors that have more connections to the local subgraph of that node, which can enhance the node't 's weighted TC. We observe this empirically boosts I.P performance and lastly discuss its noncausal limitations.
2

---

Published as a conference paper at ICLR 2024
2 RELATED WORK
Varying Performance of GNNs on Node/Graph Classification. GNNs' efficacy in classifica- tion differs across nodes/graphs with varying label quantity (e.g.. imbalanced node/graph classifica-
tion (Zhao et al.] [ Wang et al. (022b]) and varying topology quality (e.g.. long-tailed (Tang ct al. 2020; Liu et al. [202] Wheterophily node classification (Zhu et al. 2020, Mao et al.) 2023 ). To enhance GNNs' performance for the disadvantaged nodes/graphs in these two varying conditions, previous works either apply data augmentations to derive additional supervision (Wang et al. 2021
Park et al., (021) or design expressive graph convolutions to mitigate structural bias (Zhu et al. 2021 |Han et al., 2023). However, none of them tackle the varying performance of nodes in LP. We fill this gap by studying the relationship between node LP performance and its local topology.
GNN-based LP and Node-Centric Evaluation. GNN-based LP works by first learning node em- beddings/subgraph embeddings through linear transformation and message-passing. and then ap- plying the scoring function to predict link probability/subgrahh class (Zhang & Chen 2018 Yin
ct al. 2022; Wang et al. 2022c Tan ct al. 2023). It has achieved new SOTA performance owing to using the neural network to extract task-related information and the message-passing to encode the topological properties (e.g.. common neighbors) (Yun et al. [202]] Chamberlain et al.) (022). Existing GNN-based LP baselines evaluate performance by computing the average rank of each link against the randomly sampled negative links (Hu et al. (020). However, because these sam- pled negative links only count a tiny portion of the quadratic node pairs, this evaluation contains positional bias (Li et al. 2023). In view of this issue, we leverage the node-centric evaluation met- @ K) that are frequently used in recommender systems (Gori ct al. 2007 He et al. 2020) and rank each node against all other nodes in predicting the incoming neighbors. Detailed definitions of these evaluation metrics are provided in Appendix C
rics
Varying Performance of GNNs on LP. As LP nowadays has been heavily used to enhance user
experience in social/e-commerce recommendations (Fan et al. 2019: Zhao et al., (023). studying its varying performance across different users has real-world applications /hho et al. (2024) such as identifying users with ill-topology. Although no efforts have been investigated into the mode-varying performance in GNN-based LP, prior work (Li et al., 2021: Rahmani et al.) 2022 Guo et al. 2024)
have investigated the relation of node-varying I.P performance with its degree, and both claimed that users/nodes with higher activity levels/degrees tend to possess better recommendation performance than their less active counterparts, which also aligns with observations in GNN- node classi- fication (Tang et al. 2020 Liu et al., 2021). However, Figure [c)(d) has already raised concern over the validity of this claim in LP. We tollow (Wang & Der 2022) and theoretically discover that some node-centric evaluation metrics have degree-related bias in Appendix D.2] implying that the GNNs' varying LP performance could be partially attributed to the choice of evaluation metrics. To mitigate this bias, we employ a full spectrum of evaluation metrics and find that degree is not so correlated with the node IPP performance. This motivates us to devise better topological metric than the degree. Note that although some prior works also define cold-start nodes to be the ones with few degrees, we systematically review their connections and differences in Appendix B
3 TOPOLOGICAL CONCENTRATION
3.1 NOTATIONS
Let G (V,E,X) be attributed graph, where V V= (0]"% is the set of n nodes (i.e., n = PD and E C VV x V is the set of m observed training edges (i.e., m = =1E) with esj denoting the edge between the node vi and ej. and X E Raxd represents the node feature matrix. The observed adjacency matrix of the graph is denoted as A E {0, 1]mxn with Aij = 1 an observed edge exists between node i; and by and Aij = 0 otherwise. The diagonal matrix of node degree is notated as D E ==x" with the degree of node v, being d: D Σn= A.y. For the LP task, edges are usually divided into three groups notated as T = [Train, Val, Test). i.e., training, validation, and testing sets, respectively. We denote NV. E T as node v, 's 1-hop neighbors according to edge group t. Furthermore, we denote the set of nodes that have at least one path of length & to node i based on observed training edges as HP and naturally H, = Trin, Note that H, n 7 is not necessarily empty since neighbors that are h -hops away from i could also have paths of length k reaching e.. We collect U neighbors at all different hops until K to form the K K-hop computation tree centered U, S.K (H} Ik=1- We summarize all notations in Table 2 in Appendix A
K
3

---

Published as a conference paper at ICLR 2024
Center Node (a) Topological Concentration
Ihop Neighbor
2-hop Neighbor
3-hop Neighbor
(b) Intersection between computational tree
Xg noc?
xq no
1/2""
XG nx
263 n3
Triungle-hased Concentration
(d) Square-based Concentration
Observed Link (Train)
Incoming Link (Val)
Figure 2: (a)-(b): us's Topological Concentration: we calculate the average intersection between vs's computation tree and each of vj's neighbor's 's computation tree. The intersection between two computation trees is the ratio of the observed intersections to all possible intersections. (c)-(d): two specifications of TC, corresponding to social and e-commerce networks. A higher triangle/square- based concentration indicates
triangles/squares are formed among do 's local subgraph.
3.2
TOPOLOGICAL CONCENTRATION INTUITION AND FORMALIZATION
As the link formation between a node pair heavily depends on the intersection between their lo- cal subgraphs (Zhang & Chen 2018 Chamberlain et al. 2022), we similarly hypothesize that the predictability of node's neighbors relates to the intersection between this node's subgraph and the subgraphs of that node's ' neighbors, e.g., the prediction of the links {(i.jx)) in Figure a(a) depends on the intersection between S.K and {S 12 A higher intersection leads to higher LP performance. For example, in Figure ())-(d), vo neighbors closely interact with themselves while 16 neighbors do not, posing different topological conditions for the LP on tp and 16- From graph heuristics perspective, to shares common neighbors U1 12 U3 with its incoming validation neighbors 24, ity while i/ shares no neighbors with v4, v/.. From the message- message-passing perspective, the prop- agated embeddings of vo and U4, U/ share common components since they all aggregate } embeddings while vi and v'y, 0'g do not share any common embeddings among {vk When the subgraph (i.e., computation tree) surrounding node increasingly overlaps with the subgraphs of its neighbors, more paths originating from that node are likely to loop nearby and eventually return to it, resulting in a more dense/concentrated local topology for that node. Inspired by this observation, we introduce Topological Concentration to measure the average level of intersection among these local subgraphs as follows:
Definition 1. Topological Concentration (TC): The Topological Concentration C for node v E V is defined as the average intersection between ve 'ss K-hop computation tree (SK) and the computation trees of each of U, type neighbors:
EK Ekz ghi ghi th -2 n n4
C.K.t = (S ) = No N!
(I)
1 ghr - 2 172//1
EkI=1 -kz=1
Ve, V, Vt E T. where I(S S5²) quantifies the intersection between the K KChopp computation trees around and uy and is decomposed into the ratio of the observed intersections (7 n 7 to the total possible intersections g(H4,1) 34/² between neighbors that are 1 and K2 hops away as shown in F b). +k2-+ accounts for the exponential discounting effect the hop increases. The normalization term g a function of the size of the computation trees of node c;, By (Fu al.) 2022). Although computation trees only consist of edges from the training set, vs's neighbors A in Eq. I could come from trainingvalidattion/esstng sets, and we term the corresponding TC as TC Train aal Tes and their values as C. C.K. K.Va C. Iest
We verify the correlation between
TC and the node I.P performance in Section
3.3
4

---

Published as a conference paper at ICLR 2024
Prechieo
Degres Tran
Subgraph Demityy
(92.09
(a) TC
Citeseer
8.15
025
Choser
Pakned
8.00
0.21
Reptll
Vide
Culib
0.13
0.39
Te:lish
(d) Citation2
(c) Performance vs TC at Graph Level
Figure 3: (a)/(d): The average LP Performance of nodes on Collab/Citation2 monotonically in- creases as the Tran increases. (b)/(c): TC mostly achieves the highest Pearson Correlation with LP performance on Citeseer/Vole than Degree-Taine and Subgraph Density metrics. (e): performance is positively correlated to TC across different network datasets. The deviation of Collab under both GCN and LightGCN baselines from the primary linear trend might be attributed to the duplicated edges in the network that create the illusion of higher Th
3.3 TOPOLOGICAL CONCENTRATION OBSERVATION AND ANALYSIS
In this section, we draw three empirical observations to delve into the role of TC in GNN-based LP. For all experiments, we evaluate datasets with only the topology information using LightGCN and those also with node features using GCN/SAGE (Kipf & Welling 2016 Hamilton et al., 2017; He al. 2020 Detailed experimental settings described in Appendix Please note that while the findings illustrated in this section are limited to the presented datasets due to page limitation, more comprehensive results included in Appendix G
Obs. 1. TC correlates to LP performance more than other node topological properties. In Figure (a)/(d), we group nodes in Collab/Citation2 based their TC and visualize the erage performance of each group. Unlike Figure [b)), where there is no apparent relationship between the performance and the node degree, the performance almost monotonically increases as the node TC Train increases regardless of the evaluation metrics. This demonstrates the capability of Tra in characterizing the quality of nodes' local topology for their LP performance. More- over, we quantitatively compare the Pearson Correlation of the node LP performance with TCaaiin and other commonly used node local topological properties, Degree Train (i.e., the number of training edges incident node) and SubGraph Density (i.e., the density of the 1-hop training subgraph centering around a node). As shown Figure (c)). TC almost achieves the highest Pearson Conrelation with the node LP performance across every evaluation metric than the other two topo- logical properties except for the precision metric. This is due to the degree-relate implicitly encoded in the precision metric, i.e., even for the untrained link predictor, the precision of a node still increases linearly as its degree increases, as proved in Theorem 3 Note that the node's 1-hop Subgraph Density equals its local clustering coefficient (LCC), and previous work (Pan) et al. 2022) has observed its correlation with node LP performance. To justify the advantages of Additionally, Figure 3 (e) shows that T also positively correlated with LP performance across various networks, depicting preliminary benchmark for GNNs' LP performance the graph level (Palowitch et al.) (022). The
Trin
evaluation bias
Temm over LCC, we provide a concrete example Appendix E
LightGCN architecture exhibits steeper slope than GCN, as it relies exclusively on network topol- ogy without leveraging node features and thus more sensitive to changes in the purely topological metric, TC. The deviation of Collab under both GCN and LightGCN basclines from the primary linear trend might attributed the duplicated edges the network that create the illusion of higher Tran (Hu et al. 2020
Due GPU memory limitation, choose SAGE for Citation2.
5

---

Published as a conference paper at ICLR 2024
Predidee
NOCG
Recll
MRR
1.21 0nd
8:3 ODE
0.50
0445
MAB
4M45
035
8-000 (D0 640 poLLE0 K.N.L
sie.se xn sue xacon jui.so
Nati Groap by Regine
Degroe
(i) Collab
(b) Collab
(c) Collab
000
00777
0.00
0.05
004
8.000 BoG Uo Das Dol Kun BLD INLGH DUAKIN BINKR AAL
Degin Thrnshe
Degrea
(d) Citation2
(e) Cilation2
Citation2
Figure 4: (a)/(d): The average LP performance of nodes with extremely low TC on Col- lab/Citation2 almost monotonically increases as TC increases. (b)/(e): Nodes with lower Degree Train surprisingly perform better than their higher degree counterparts (Blue curves). In con- trast, non-concentrated nodes identified by owning lower TCTmiin in most cases perform worse than their concentrated counterparts (Red curves). (c)/(f): As node Degree Train increases, the ratio of nodes owning higher Thin increases first and then decreases, corresponding to the observed first- and-then--eereaasing performance trend in Figure (())))
Obs. 2. TC better identifies low-performing nodes than degree, and lower-degree nodes may not necessarily have lower LP performance.
As previously shown in Figure [c)(d), when the node degree at the very low regime, we do not observe striet positive relationship between node Degree Train and its LP performance. For example, the node Recal//RR//NDGG 10 in Collab decreases as Degree Train increases and Hits /F1/Precision 10 first increases and then decreases. These contradicting observations fa- cilitate our hypothesis that the degree might not fully capture the local topology in characterizing the underperforming nodes. Conversely, Figure (f)((d) on Collab/Citation,. nodes with lower TC almost always have worse LP performance under all evaluation metrics except when Tain between [0, 0.02). For this extreme case, we ascribe to the distribution shift as nodes with ex- tremely low TC generally have a decent TC (shown in Figure 20 and sustain a reasonable LP performance. We thoroughly investigate this distribution shift issue in Obs. Furthermore, we select nodes with Degree Tran from to 10 and group them into Loowerdegree/HHihher-ggre Similarly, we select nodes with Thaa from 0.01 to 0.1 and group them into "Concentrated/Non Concentrated'. We compare their average LP performance
Collab/Citation2 in Figure 4 b)/(e..
Intriguingly, Lower-degree nodes always perform better than their Higher-degre counterparts across all Degree Train thresholds. This brings nuances into the conventional understanding that nodes with Train
weaker topology (lower degree) would yield inferior performance (Li et al.) 2021] Tang et al.) 2020) Liu et al. 2021). In contrast, with our defined Ta conn-cnnenttated nodes (lower TC Irain) gen- erally underperform by a noticeable margin than their concentrated counterparts (higher TC
We further visualize the relation between Degree and TC in Figure 4 c))((). When node Degree Train increases from to 4, the ratio of nodes owning higher Tr also increases because these newly landed nodes start forming interactions and create their initial topological context. Since we have already observed the positive correlation of Traa to nodes' LP performance previously, the LP performance under some evaluation metrics also increases as the Degree Train initially in- creases from 0 to 4 observed in Figure I (dd). When Degree Train increases further beyond 5, the ratio nodes owning higher Th gradually decreases, leading to the decreasing performance ob- served in the later stage of Figure I cd).). This decreasing TC is because, for high Degree Train nodes, their neighbors are likely to in different communities and share fewer connections among themselves. For example, in social networks, high-activity users usually possess diverse relations in different online communities, and their interacted people are likely from significantly different domains and hence share less common social relations themselves Zhao et al. (2021c 2024).

---

Published as a conference paper at ICLR 2024
Trabs DC3 Valdadax Bur
Predsinn
NOCG
0.2
Ite
Dreaiy
0.0-
-02
Clown
-10
-0.5
[-9,,,033
(06,10)
TC
TC Te
Figure 5: (a) Hits @ of predicting training/validatioontesing edges on Cora/ChteeerrCoollab The gap between validation and testing performance is much bigger on Collab than on Cora/Citeseer. (b) Compared with Cora/Citeseer where edges randomly split, the distribution of the difference between TC and TC shifts slightly right on Collab where edges are split according to time, indicating the interaction between training and testing neighbors become less than the one between training and validation neighbors. (c) As the gap between TC and TC increases for different nodes, their corresponding performance gap also increases, demonstrating TDS varies among dif- ferent nodes even within the same graph.
Obs. 3. Topological Distribution Shift compromises the LP performance at testing time, and TC can measure its negative impact at both graph and node level. In real-world LP scenarios, new nodes continuously join the network and form new links with existing nodes, making the whole network evolve dynamically (Ma et al.) 2020 Rossi et al. 2020). Here, we discover a new Topo- logical Distribution Shift (TDS) issue, i.e., as time goes on, the newly joined neighbors of a node become less interactive with that node's 's old neighbors. Since the edges serving message-passe and providing supervision only come from the training set, TDS would compromise the capability of the learned node embeddings for predicting links in the testing set. As verified in ( the performance gap between validation and testing sets on Collab where edges are split according to time is much more significant than the one Cora/Citeseer where edges are split randomly. Note that the significantly higher performance on predicting training edges among all these three datasets is because they have already been used in the training phase (Wang et al. (023), and this distribu- tion shift is different from TDS. As TC essentially measures the interaction level among neighbors of particular node, we further visualize the distribution of the difference between TC and Te in Figure ((b). We observe slight shift towards the right on Collab rather than on Cora/Citeseer, demonstrating nodes' testing neighbors become less interactive with their training neighbors than their validation neighbors. Figure c further demonstrates the influence of this shift at the node level by visualizing the relationship between TDS and the performance gap. We can see that as the strength of such shift increases (evidenced by the larger difference between TC and TCTstt, the performance gap also increases. This suggests that nodes within the same graph display varying levels of TDS. As one potential application, we can devise adaptive data valuation techniques or message- message-passing mechanisms to selectively use neighborhood information (i.c., emphasize less on stale edges in LP Chamberlain et al. (2022) did). We demonstrate use-case in Appendix K
3.4 TOPOLOGICAL CONCENTRATION: COMPUTATIONAL COMPLEXITY AND OPTIMIZATION
Calculating TC following Eq. (T) involves counting the intersection between two neighboring sets that are different hops away from the centering nodes in two computation trees. Assuming the average degree of the network is d, the time complexity of computing C.K for all nodes in the network is O(E _ Ek=1 min(@*, , = O(K*&E|)) Rs O(K?V)²) for sparse networks, which increases quadratically the size of the network increases and is hence challenging for large- scale networks. To handle this issue, we propagate the randomly initialized Gaussian embeddings in the latent space approximate TC in the topological space and propose Approximated Topological Concentration as follows:
Definition 2. Approximated Topological Concentration (ATC): Approximated topological con- centration K.Kt for U; E V is the average similarity between v; and its neighbors' embeddings initialized from Gaussian Random Projection (Chen el al. 2019 followed by row-normalized gruph diffusion A Gastteiger et al. 2019), with Φ as the similarity metric function:
K
KK (N,,
- AAAR R~ N~0 Σd)
(2)

---

Published as a conference paper at ICLR 2024
Theorem 1. Assuming 9 9(HH, 12, 7 117, in Eq. 1 and let o be the dot-product based similarity metric (He et al. 2020 then node vi's I-layer Topological Concentration C/*²t is linear correlated with the mean value of the I-layer Approximated Topological Concentration PōKa as:
Ct'² = d HB., (, (B)) = =d
(3)
where E! E Ruxd denotes the node embeddings after 1 1-layer SAGE-style message-passingg and d is the embedding dimension. The full proof is in Appendix [D] This theorem bridges the gap between TC defined in the topological space and ATC defined in the latent space, which theoretically justifies the effectiveness of this approximation. Computationally, obtaining node embeddings N in Eq. 2 free from optimization, and the graph diffusion can be efficiently executed via power iteration, which reduces the complexity to [ + [VD). Note that although we only demonstrate the approximation power for the case of 1-layer message-pant paagaggg... we empirically verify the efficacy for higher-layer message-passing in the following.
R1p
We compare TC and ATC under various number of hops in terms of their computational time and their correlation with LP performance in Figure 6 As the number of hops increases, the running time for computing TC increases exponen- tially (especially for large-scale datasets like Col- lab, we are only affordable to compute its TC up to hops) while ATC stays roughly the same. This aligns with the quadratic/linear time complex- ity V (D))) we derived earlier for TC/ATC. Moreover, ATC achieves similar level of correlation to TC at all different hops. For both TC and ATC, their correlations to LP performance increase as the number of hops K used in Eq. DD.E 2 increases. This is because larger K enables us to capture intersections among larger subgraphs and hence accounts for more common neighbor signals (Chamberlain et al. 2022). We include comprehensive analysis including (A)TC" in Appendix
Leg Honning lineil
Informmne
Nanther Hops
Namber Bogs
Figure 6: ATC maintains similar level of correlation to TC while significantly reducing the computational time.
4 TOPOLOGICAL CONCENTRATION BOOSTING GNNs' LP PERFORMANCE
From the aforementioned observations, TC consistently exhibits a stronger correlation with GNNs' LP performance than other commonly used node topological metrics. This insight motivates us to explore the potential of boosting GNNs' LP performance via enhancing Train Specifically, we propose to vary the edge weight used in peessage-passing by aggregating more information from neighbors that contribute more to TC We theoretically prove this way could enhance I-layer TC in Theorem 4nd empirically verify it in Figure a Since neighbors owning more connec- tions with the whole neighborhood have higher LP scores with the average neighborhood embed- dings, we update the adjacency matrix used for message-passtene as:
exp(se, INT-"11-1
A
lj + Ey= explse, (N; . " ifAg Ye., Ui E V,
(4)
0,
ifA =
where H fe, (AT-1, X) is the node embeddings obtained from GNN model fe,, N A is the average neighborhood embeddings by performing one more SAGE-style propagation, y is the weight coefficient, A A, and ge, is the link predictor. The detailed algorithm is pre- sented in Appendix H Note that this edge reweighting strategy directly operates on the original adja- cency matrix and hence shares the same time/space complexity as the conventional
pesssage-passing O(Ld(EE + VI)) with L being the number of message- message-passing layers. For baselines obtaining node embeddings without using sesssage-assiig such as BUDDY Chamberlain et al. (2022), we reweigh edges in computing the binary cross entropy loss in the training stage. More details are attached Appendix [ Specifically, we equip four baselines, GCNISAGE//CNIUDDDY with our designed edge reweighting strategy and present their LP performance in Table II Appendix F thoroughly describes the experimental settings. For GCN, SAGE and BUDDY, equipping with our proposed edge reweighting strategy enhances their LP performance in most cases. This demonstrates that by pushing up the Than of the whole graph, the LP performance can be boosted to a certain level, which also verified by the increasing TC shown in Figure (a). We hypothesize that neighbors
8

---

Published as a conference paper at ICLR 2024
Table 1: Results on LP benchmarks. Xyw denotes weighted message- passsng added to baseline X.
Cora Hits@ 100
Citeseer
Puhmed Hits@100
Collab Ho
Collab Hi
Citation2
Reptile Hits@
Vole
Baseline
Hits@
Hits 6 100
GCN
70.63-00.67
65.96+2.112
69.35++1002 02
49.52:40.52
58.00=00.27
84.42-0.055
65.52-2.73
73.84+0.98
GCN
1.298:11.28
14,40=:1.11
68.87:-0.99
52.85-20.14
60.57=00.38
85.34=0.30
70.79=2.00
74.50=00.44
SAGE
74,27=2.08
61.57:+3.28
66.25++1000
.8
50.01+00.50
57.06=0.066
80.44=0.10
72.59=3.19
80.55+1..5
SAGiEr
74.624:2.30
89.89:11.66 1,66
66.77:1:0.9
52.59:10.37
59.26=#0.08
80.61=0.10
74.35=3.20
01.27::0.96
NCN
87.73=1.41
90,93+-0.83
1.550
54,43++0.17
65.34+00.03
88.64=0.14
68.37=3.57
66.10=1.11
NCN
87.95-4:1.30
91.86:1-0.22
76.51:11.41
54.16:1:.:24
65.41
00M
73.81
67.32-4-.81
BUDDY
84,82
91,44:11.14
74.46.13.32
55.73:10.16
66.25:10.28
0.110
74.69 74.69-7.555
83.37:11.05 47.20=4.10
BUDDY mM
85.06-1 1.81
91.86-1-1.00
25.74442.03
56.17:10..2
66.31
88.45
84.6441.22
Note that for Citation,, due to memory limitation, we directly take the result from the original NCN puper (Wang et al. 2023 Different from Collah only using training edges message passing for evaluating testing performance, we also allow validation edges in Collab"..
connecting more to the overall neighborhood likely have greater interactions with incoming neigh- bors. Thus, aggregating more information from them inherently captures the common neighbor signals of these incoming neighbors. Meanwhile, as NCN already explicitly accounts for this com- mon neighbor signal in its decoder, the performance gains from strategy relatively modest. Furthermore, the positive trend observed in Figure ( verifies that the larger enhancement in node TC leads to larger performance boost in its Hits @ 10. However,
note that LP performance is evaluated on the incoming testing neighbors rather than training neighbors, so TC is more of correlated metric than causal. To illustrate, consider an extreme case where node u; has training neighbors forming a complete graph with no connection to its incoming neighbors. In such sce- nario, even if we achieve the maximum Th and significantly high training performance, still hardly generalizes to predicting testing links. This could be reflected in the inconsistent trend in Figure 21 22 in Appendix G.7 In addition, Figure ( verifies the assumption made in Theorem and in the reweighting model design that nodes with larger TCTmin have higher average embedding similarity to their neighbors.
SAGE-IT
SA
SAGE-Te
Se
0.25
100255
000-
yel CR
401
1006
Tialning spach
Change TC" beforwlffee reweighting
spoch
(e) Training Process of SAGE
(b) SAGE
(0) LighIGNN
Figure 7: (a) Change of 50 and Reweighted TC along the training process in SAGE. (b) Nodes with enhanced Tranann exhibit higher performance. (c) Embedding similarity during LightGCN training increases faster and higher for nodes with higher TC
CONCLUSION
Although many recent works have achieved unprecedented success in enhancing link prediction (LP) performance with GNNs, demystifying the varying levels of embedding quality and LP performance across different nodes within the graph is heavily under-explored yet fundamental. In this work, take the lead in understanding the nodes' varying performance from the perspective of their local topology. Given the connection between link formation and the subgraph interaction, we propose Topological Concentration (TC) and demonstrate its superiority in characterizing node LP performance and identifying low- oww-peforming nodes by specifically verifying its higher performance correlation than other node-centric topological metrics. Moreover, we discover novel topological distribution shift (TDS) issue by observing the changing LP performance over time and demonstrate the capability of using TC to measure this distribution shift. Our work offers the community strong insights into which local topology enables nodes to have better LP performance with GNNs. In the future, we plan to investigate the causal relationship between TC and LP. Additionally, we aim to utilize TC for data valuation to select consistently crucial edges in dynamic link prediction.
LEGNONTES
This research supported by the National Science Foundation (NSF) under grant number II$2239881 and by Snap Inc.

---

Published as a conference paper at ICLR 2024
REFERENCES
Sergey Brin and Lawrence Page. The anatomy of a large-scale hypertextual web search engine. Computer networks and ISDN systems, 30(1-7):007-11,, 1998.
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. arXiv preprint arXiv:2209. 15486, 2022.
Deli Chen, Yankai Lin, Guangxiang Zhao, Xuancheng Ren, Peng Li, Jie Zhou, and Xu Sun. Topology-imballe imbalance learning for semi-supervised node classification. Advances in Neural In- formation Processing Systems, 34:29885-29897, 2021a.
Haochen Chen, Syed Fahad Sultan, Yingtao Tian, Muhao Chen, and Steven Skiena. Fast and ac- curate network embeddings via very sparse random projection. In Proceedings of the 28th ACM international conference information and knowledge management, pp. 399 408, 2019.
Huiyuan Chen, Lan Wang, Yusan Lin, Chin-Chis Michael Yeh, Fei Wang, and Hao Yang. Structured graph convolutional networks with stochastic masks for recommender systems. In Proceedings of the 44th International ACM SIGIR Conference Research and Development in Information Retrieval, pp. 614-623, 2021b.
Manging Dong, Feng Yuan, Lina Yao, Xiwei Xu, and Liming Zhu. Mamo:
meta-optimization for cold-start recommendation. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 688-697, 2020.
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In The world wide web conference, pp. 417-426, 2019.
Mao-Ming Fu, Patrick Poirson, Kwot Sin Lee, and Chen Wang. Revisiting neighborhood-bassed link prediction for collaborative filtering. Companion Proceedings of the Web Conference 2022, pp. 1009-1018, 2022.
Johannes Gasteiger, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learning. Advances neural information processing systems, 32, 2019.
Liang Ge and Aidong Zhang. Pseudo cold start link prediction with multiple sources in social networks. In Proceedings of the 2012 SIAM International Conference on Data Mining, pp. 768- 779. SIAM, 2012.
Marco Gori, Augusto Pucci, Roma, and I Siena. Itemrank: A random- walk based scoring algo- rithm for recommender engines. In IJCAI, volume 7, pp. 7766-2771 2007.
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, 864, 2016.
Zhichun Guo, Tong Zhao, Yozen Liu, Kaiwen Dong, William Shiao, Neil Shah, and Nitesh V Chawla. Node duplication improves cold-start link prediction. arXiv preprint arX7v:240..09711, 2024.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Haoyu Han, Xiaorui Liu, Li Ma, MohamadAli Torkamani, Hui Liu, Jiliang Tang, and Makoto Ya- mada. Structural fairness-aware active learning for graph neural networks. In The Twelfth Inter- national Conference on Learning Representations, 2023.
Xiao Han, Leye Wang. Son N Han, Chao Chen, Noël Crespi, and Reza Farahbakhsh. Link prediction for new users in social networks. In 2015 IEEE International Conference on Communications (ICC), pp. 1250-1255. IEEE, 2015.
Bowen Hao, Jing Zhang, Hongzhi Yin, Cuiping Li, and Hong Chen. Pre-training graph neural net- works for star-start users and items representation. In Proceedings of the 14th ACM International Conference Web Search and Data Mining, pp. 265-273, 2021.
10

---

Published as a conference paper at ICLR 2024
Xiangnan He, Kuan Deng, Xiang Wang. Yan Li, Yongdong Zhang, and Meng Wang. Lightgen: Simplifying and powering graph convolution network for recommendation. Proceedings of the 43rd International ACM SIGIR conference research and development in Information Retrieval, pp. 639-648, 2020.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 53:22118-2211 2020.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: 1609000977 2016.
Sang Gyu Kwak and Jong Hae Kim. Central limit theorem: the cornerstone of modern statistics. Korean journal anesthesiology, 70(2): 144-156,, 2017.
Vincent Leroy, B Barla Cambazoglu, and Francesco Bonchi. Cold start link prediction. In Pro- ceedings of the 16th ACM SIGKDD international conference Knowledge discovery and data mining, pp. 393-402, 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 benchmark- ing, arXiv preprint arXiv:2306. 10453, 2023.
Yunqi Li, Hanxiong Chen, Zuohui Fu, Yingqiang Ge, and Yongfeng Zhang. User-oriented fairness in recommendation. In Proceedings of the Web Conference 2021, pp. 624-632, 2021.
David Liben-Nowell and Jon Kleinberg. The link prediction problem for social networks. In Pro- ceedings of the twelfth international conference on Information and knowledge management, pp. 556 256-559,45 2003.
Blerina Lika, Kostas Kolomvatsos, and Stathes Hadjjefthymiades. Facing the cold start problem in recommender systems. Expert systems with applications, 41 41(4):2065-200 2014.
Zemin Liu, Trung-Kien Nguyen, and Yuan Fang. Tail-gnn: Tail-node graph neural networks. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp- 1109 1119, 2021.
Yao Ma, Ziyi Guo, Zhaocun Ren, Jiliang Tang, and Dawei Yin. Streaming graph neural networks. In Proceedings of the 43rd international ACM SIGIR conference on research and development in information retrieval, pp. 719-728, 2020.
Haitao Mao, Zhikai Chen, Wei Jin, Haoyu Han, Yao Ma, Tong Zhao, Neil Shah, and Jiliang Tang. Demystifying structural disparity in graph neural networks: Can one size fit all? arXiv preprint arXiv:2306.01323, 2023.
Mark EJ Newman. Clustering and preferential attachment in growing networks. Physical review E, 64(2):025102, 2001.
John Palowitch, Anton Tsitsulin, Brandon Mayer, and Bryan Perozzi. Graphworld: Fake graphs bring real insights for gnns. Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 3691-3701, 2022.
Liming Pan, Cheng Shi, and Ivan Dokmanić. Neural link prediction with walk pooling. Interna- tional Conference on Learning Representations, 2022.
Joonhyung Park, Jaeyun Song, and Eunho Yang. Graphens: Neighbor ego network synthesis for tions, 2021.
node classification. In International Conference Learning Representa-
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701-710, 2014.

---

Published as a conference paper at ICLR 2024
Hossein A Rahmani, Mohammadmehdi Naghiaei, Mahdi Dehghan, and Mohammad Aliannejadi. Experiments on generalizability of user-oriented faimesss in recommender systems. Proceed- ings of the 45th International ACM SIGIR Conference Research and Development in Informa- fion Retrieval, pp. 2755-2764, 2022.
Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico Monti, and Michael Bronstein. Temporal graph networks for deep learning on dynamic graphs. arXiv preprint arXiv:2006. 10637, 2020.
Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In AAAI, 2015.
com
Benedek Rozemberezki, Charles Tapley Hoyt, Anna Gogleva, Piotr Grabowski, Klas Karis, Andrej Lamov, Andriy Nikolov, Sebastian Nilsson, Michael Ughetto, Yu Wang, Tyler Derr, and Ben- jamin M. Gyori. Chemicalx: A deep learning library for drug pair scoring. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 3819-3828, 2022.
MN Sanders. Characteristic function of the central chi-squared distribution, 2009.
Hibiki Taguchi, Xin Liu, and Tsuyoshi Murata. Graph convolutional networks for graphs containing missing features. Future Generation Computer Systems, 1 117:155-168, 2021.
Qiaoyu Tan, Xin Zhang, Ninghao Liu, Daochen Zha, Li Li, Rui Chen, Soo-Hyun Choi, and Xia Hu. Bring your own view: Graph neural networks for link prediction with personalized subgraph selection. Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining, pp. 625 633, 2023.
Xianfeng Tang. Huaxiu Yao, Yiwei Sun, Yiqi Wang. Jiliang Tang. Charu Aggarwal, Prasenjit Mitra, and Suhang Wang. Investigating and mitigating degree-relatee related biases in graph convoltuional net- works. In Proceedings of the 29th ACM International Conference on Information & Knowledge Manugement, pp. 1435-1444, 2020.
Hongwei Wang, Fuzheng Zhang, Miao Zhao, Wenjie Li, Xing Xie, and Minyi Guo. Multi-task fea- ture learning for knowledge graph enhanced recommendation. In The world wide web conference, pp. 2000-2010, 2019.
Ruijia Wang, Xiao Wang, Chuan Shi, and Le Song. Uncovering the structural fairness graph con- trastive learning. Advances in Neural Information Processing Systems, 35:32465-3244 2022a.
Xiyuan Wang, Haotong Yang, and Muhan Zhang. Neural common neighbor with completion for link prediction. arXiv preprint 23Xi::23022008900. 2023.
Yiwei Wang, Wei Wang, Yuxuan Liang, Yujun Cai, and Bryan Hooi. Mixup for node and graph classification. In Proceedings of the Web Conference 202/, pp. 3663-3674, 2021.
Yu Wang and Tyler Derr. Degree-related bias in link prediction. In 2022 IEEE International Con- ference on Data Mining Workshops (ICDMW), pp. 757-758. IEEE, 2022.
Yu Wang, Yuying Zhao, Neil Shah, and Tyler Derr. Imbalanced graph classification via graph-of- graph neural networks. In Proceedings of the 1 ACM International Conference Information & Knowledge Management, pp. 2067-2076, 2022b.
Yu Wang, Yuying Zhao, Yi Zhang, and Tyler Derr. Collaboration-aware graph convolutional net- works for recommendation systems. arXiv preprint arXiw:2207.062221 2022c.
Zhiqiang Wang. Jiye Liang, Ru Li, and Yuhua Qian. An approach to cold-start link prediction: Es- tablishing connections between non-topological and topological information. IEEE Transactions on Knowledge and Data Engineering, 28(11):2857-287) 2016.
Tianxin Wei and Jingrui He. Comprehensive fair meta-learned recommender system. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1989- 1999, 2022.
12

---

Published as a conference paper at ICLR 2024
Linchuan Xu, Xiaokai Wei, Jiannong Cao, and Philip S Yu. On learning mixed community- sppecfiiippeiieeee similarity metrics for cold-start link prediction. In Proceedings of the 26th International Confer- ence on World Wide Web Companion, pp. 861-862, 2017.
Ming Yan, Jitao Sang, Tao Mei, and Changsheng Xu. Friend transfer: Cold-start friend recommen- dation with cross-platform transfer learning of social knowledge. In 2013 IEEE International Conference on Multimedia and Expo (ICME). pp. 1-6. IEEE, 2013.
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.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 974 983, 2018.
Seongjun Yun, Seoyoon Kim, Junhyun Lee, Jaewoo Kang, and Hyunwoo J Kim. Neo-gnns: Neigh- borhood overlap-awan graph neural networks for link prediction. Advances in Neural Information Processing Systems, 16633113364 2021.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in neural information processing systems, 31, 2018.
Tianxiang Zhao, Xiang Zhang, and Suhang Wang. Graphsmote: Imbalanced node classification graphs with graph neural networks. In Proceedings of the 14th ACM international conference on web search and data mining, pp. 833-841, 2021a.
Tong Zhao, Yozen Liu, Leonardo Neves, Oliver Woodford, Meng Jiang, and Neil Shah. Data aug- mentation for graph neural networks. In Proceedings of the aaai conference on artificial intelli- gence, volume 35, pp. 1015--1023, 2021b.
Tong Zhao, Gang Liu, Daheng Wang, Wenhao Yu, and Meng Jiang. Learning from counterfactual links for link prediction. In International Conference Machine Learning, pp. PMLR, 2022.
Xiangyu Zhao. Haochen Liu, Wenqi Fan, Hui Liu, Jiliang Tang, Chong Wang, Ming Chen, Xudong Zheng, Xiaobing Liu, and Xiwang Yang. Autoemb: Automated embedding dimensionality search in streaming recommendations. In 2021 IEEE International Conference on Data Mining (ICDM), pp. 896-905. IEEE, 2021c.
Xiangyu Zhao, Haochen Liu, Hui Liu, Jiliang Tang. Weiwei Guo, Jun Shi, Sida Wang, Huiji Gao, and Bo Long. Autodim: Field-aware embedding dimension searchin recommender systems. In Proceedings of the Web Conference 202/, pp. 3015-3022, 2021d.
Yuying Zhao, Yu Wang, Yunchao Liu, Xueqi Cheng, Charu Aggarwal, and Tyler Derr. Fairness and diversity in recommender systems: a survey. arXiv preprint arXiv:2307.04644 2023.
Yuying Zhao, Minghua Xu, Huiyuan Chen, Yuzhong Chen, Yiwei Cai, Rashidul Islam, Yu Wang, and Tyler Derr. Can one embedding fit all? multi-interest learning paradigm towards improving user interest diversity faireess. arXiv preprint wwXiv:2402.134955 2024.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33:7793-7888 2020.
Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra. Graph neural networks with heterophily. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pp. 11 1118-111766 2021.
13

---

Published as a conference paper at ICLR 2024
Appendix
Table of Contents
Notations
15
B Review of the cold-start issue in link prediction and recommender systems
16
Link-centric and Node-centric Evaluation Metrics
Link-Centric Evaluation
Node-Centric Evaluation
D
Proof of Theorems
18
D.1
Approximation power of ATC for TC
18
D.2
Degree-related Bias of Evaluation Metrics
19
D.3
Reweighting by LP Score Enhance 1-layer TC
21
E
Example demonstrating the advantages over LCC
F
Datascts and Experimental Settings
23
F1 Dataset Introduction and Statistics
23
F2
Hyperparameter Details
23
Additional Results
24
G.1
Link prediction performance grouped by TC
................................
24
Link prediction performance grouped by TC Train
................................
25
G.3
Link prediction performance grouped by Degree
................................
26
G.4
Link prediction performance grouped by Degree
27
G.5
Relation between LP performance and TC at Graph-level
28
G.6
Relation between Trara and TC Test
28
Difference in TC vs Difference in Performance before/alier app ying reweighting
28
G.8
Correlation of the performance with TC and Degree
28
Edge Reweighting Algorithm
37
Reweigh edges for baselines without message-pasinn passing
37
Comparing the Efficiency between baseline and their augmented version by TC
38
Reweighting training neighbors based on their connections training neighbors or validation neighbors
38
Explaining why the curve of link prediction performance has several fast down aa)
39
14

---

Published as a conference paper at ICLR 2024
A
NOTATIONS
This section summarizes notations used throughout this paper.
Table 2: Notations used throughout this paper.
Notations
Definitions or Descriptions
(V,Ex)
Graph with node set V. edge set and node feature X Number of nodes
m, n
[ and number of edges = |&| Node us and the edge Eij between node and Adjacency matrix A, indicates an edge Eij between 0ey V/ Row-based normalized graph adjacency matrix A
Eij
A
A
A
GCN-based normalized graph adjacency matrix A = D 0.5 AD 0.5
A'
Updated adjacency matrix at iteration / Diagonal degree matrix D = Σ}= Aij
D d
Average degree of the network
T = (Trai,, Val. Test
Set of irraiing/Valldationn Seliidaation//estinng edge groups
Degree TaiTee
Degree based on Training/ Training/Validation Validation/ Topological Concentrations that quantify intersections
Edges
TC Vaiin//aallee
with Training/Validation/ Walidation/Testiii
neighbors
A H. S/K (7/ Jkm OKii CKK
Node V T-hop neighbors of type I, E
Nodes having at least one path of length & to U, based on training edges Errain K-hop computational tree centered the node v; (Approximated) Topological concentration for node eú considering the intersection among K -hop computational trees among its type t neighbors.
E Ry
Embedding of the node v; after -ly-l message-passing Sample from gaussian random variable (0, 1/d)
go E,
Link predictor parameterized by θ
Predicted and ground-truie neighbors of node Us
HG
Hypergeometric distribution
LP (A)TC TDS B
Link Prediction
(Approxminated) Topological Concentration Topological Distribution Shift
Exponential discounting effect as the hop increases Weighted coefficient of layer k in computing ATC
p
Mean of the distribution
L
Number of message-passiing layers
Coefficients measuring the contribution of updating adjacency matrix
15

---

Published as a conference paper at ICLR 2024
B REVIEW OF THE COLD-START ISSUE IN LINK PREDICTION AND RECOMMENDER SYSTEMS
One line of the research eeroy al. 2010 Ge & Zhang 2012 Yan al. 2013 Han et al. 2015 Wang et al. 2016 Xu et al. 2017) defines the cold-start nodes as the ones with little to no topo- logical information (isolated user) and augment these disadvantaged groups with auxiliary infor- mation, e.g., user profile/rich text information, community information, and group membership. Specifically, YYan al. 2013) derive the auxiliary information based on the interactions of these disadvantageous nodes/users from their cross platform behaviors. (Leroy et al. 2010) constructs the probabilistic graph and then refines it by considering the transitivity the contract relationship. (Ge & Zhang 2012) incorporates feature selection and regularization to avoid overfitting. The other
line of research (Wang et al. 2019 Dong et al. 2020 Li et al., 2021 Hao et al.) 2021 Rahmani ct al. 2022. Wei & He 2022) studies the cold-start issue from the perspective in recommender systems. They usually define cold-start nodes/users as the ones with uo-to-sparse/low activitics. (Li al. 2 Rahmani et al., 2022) devises re-ranking strategy by optimizing the performance gap between low-activity and high-activity users. (Dong et al.) 2020); Wei & He 2022) design multiple meta-learning frameworks to learn user preferences based his/her few past interactions. (Wang et al.
2019) uses knowledge graph embedding to assist with recommendation tasks for low-activity users while (Hao al., (02I) trains GNNs to adapt to cold-start nodes by mimicking the cold-start scenario for warm users.
Following the above second line of research, we study the cold-start link prediction the node level since our paper targets demystifying the varying link prediction performance across different nodes. Therefore, we follow some conventional literature (Wang al.) 2019; Dong et al. 2020 Li et al. 2021] Wei & He 2022) and deem the nodes with generally few degrees cold-start ones. Particularly, in Figure ((b)(e), we change the degree threshold from to 10, divide nodes into two groups at each degree threshold, and further visualize the average performance for each group. We can see that nodes in the lower-degree groups generally have higher performance than nodes in the higher-degree groups. The above observation has two promising insights compared with conventional literature:
(1) Many existing recommendation- eet al. 2021 Newman 2001) define cold-start users/nodes as the ones with few/little interac- tions/topological signals. However, our paper empirically demonstrates that nodes with lower degrees even exhibit higher LP performance.
papers (Wang et al., 2019; Dong al. 2020 Li
(2) Many existing node classification papers (Tang et al. 2020 Chen et al. 2021a Wang et al., 2022a) find nodes with low degrees have lower performance. However, our work sheds new insights into the degree-related bias in link prediction where nodes with lower degrees can actually possess higher performance.
We justify the above 1st insight by relating to real-world scenarios where users with high degrees usually tend to possess diverse interests (nodes with higher degrees may tend to belong to diverse communities) and therefore, using the equal capacity of embedding cannot equally characterize all of their interests (Zhao et al. 2021d).
We justify the above 2nd insight by relating to the inherent difference between the mechanism of node classification and the mechanism of link prediction. For node classification, high-degree nodes are more likely obtain the supervised signals from labeled nodes in the same class (Chen et al., 2021a). For link prediction, the ground-truth class for each node is actually its testing neighbors and hence when performing message-passing, beneficial supervision signals are not guaranteed to be captured more by high-degree nodes.
In our paper, we focus on the performance difference between low-degree nodes and high-degree nodes rather than the cold-start issue. However, if we also consider cold-start nodes as the ones with sparse interactions as some previous work did (Li et al. 2021 Rahmani et al. 2022). then our analysis and observation can also apply there.
16

---

Published as a conference paper at ICLR 2024
C LINK-CENTRIC AND NODE-CENTRIC EVALUATION METRICS
In addition to the conventional link-centric evaluation metrics used in this work, node-centric evalu- ation metrics are also used to mitigate the positional bias caused by the tiny portion of the sampled negative links. We introduce their mathematical definition respectively as follows:
C.I
EVALUATION
Following (Hu et al. 2020), we rank the prediction score of each link among set randomly sampled negative node pairs and calculate the link-centric evaluation metrie Hits@ K as the ratio of positive edges that are ranked at K -laace or above. Note that this evaluation may cause bias as the sampled negative links only count tiny portion of the quadratic node pairs (Li et al.) 2023) Hereafter, we introduce the centric evaluation metrics and specifically denote the node-level Hit ratio Hits @ K to differentiate it from the link-centric evaluation metric Hits@K.
C.2 CEDERCENTRIC EVALUATION
For each node E V, the model predicts the link formation score between and every other node, and selects the top-K nodes to form the potential candidates &. Since the ground-truth candidates for node U; is Aftest (hereafter, we notate as &s), compute the Recall (R), Precision (P), F1, NDCG (N), MRR and Hits of o follows:
E 1
EN K
RyK,
POK;
(5)
E,1
1fu E(E.EE( N@K; Ek=1
FIOK 2 n Ed K + [&i1
(kg,(k+1)
Ek=1 (o
MRR@K, min (E, Rank,
Hits N @K; = 111;; n
(7)
where of denotes vú 's th preferred node according to the ranking of the link prediction score, Rank, the ranking of the node and is the indicator function equating 0 if the intersection between Ei & is empty otherwise 1. The final performance of each dataset averaged across each node:
X@K = EE..v E FI,,, MRR, Hits N
(8)
Because for each node, the predicted neighbors will be compared against all the other nodes, there no evaluation bias compared with the link-centric evaluation where only set of randomly selected negative node pairs are used.
17

---

Published as a conference paper at ICLR 2024
D PROOF OF THEOREMS
D.1 APPROXIMATION POWER OF ATC FOR TC
H 11355 in Eq. 1 and let & be the dot-product based similarity metric (He et al. 2020 then node vi 's I-layer Topological Concentration C; it is linear correlated with the mean value of the 1-layer Approximated Topological Concentration PoRa as:
Theorem 1 Assuming 9(H 11
C. d -x
d Pa..
where E' R denotes the node embeddings after 1-layer SAGE-style message-passinng over the node embeddingg R ~~ (02, )
Proof. Assuming without loss of generalizability that the row-normalized adjacency matrix Á D- A is used in aggregating neighborhood embeddings. We focus on randomly selected node E, e Rd, Ve, and its I-layer ATC given by Eq. 2 is:
Th11 E B (E))
E = =E, E [ (ÄR),
1 p [ |Trrain N NTain
Σ
R
Σ R
E
=E
Σ
(Rm) Rn
[NTrrain |
(um ENN Tom x
(Rm) Rr +
Σ
(Rs)
R
[7 17
(Co Uh JEA iiin X Iean of
Tye EEA Miniiii DA Tinis
Common neighbor embeddingg pairs
Non-common neighbor embedding pairs
(10) Note that the first term is the dot product between any pair of two non-common neighbor em- beddings. which is essentially the dot product between two independent samples from the same multivariate Gaussian distribution (note that here we do not perform any training optimizution, so the embeddings of different nodes are completely independent). By central limit theorem (Kwak) & Kim 2017). the first term approaches the standard Gaussian distribution with as the mean, i.e., (.(.,/((...)) RR. O. In contrast, the second term is the dot product between any Gaussian- distributed sample and itself, which can be essentially characterized as the sum of squares of independent standard normal random variables and hence follows the chi-squared distribution with d degrees of freedom, i.e., (Rt) R& xa (Sanders, 2209).. By Central Limit Theorem, P( xàx < 2) = ()) and hence lim x3 = (d,, 2d), i.c., ((R.) = d. V2d
lim
Then we obtain the mean value of E Be (EJ)
RJ E. PoL. = Ma (BJ)
N
H H
(MS
(em. NENiin Ani TR...RR. om pf
R. + #S "Eggextann (Ra) T R..)
dlA.Tmiin N.Tiiann
d nH!)
E E
Ey eN 111111
dct.
|7 117
(11)
The first approximation holds assuming all nodes share the same degree. The second approxi- mation holds since we set d to be at least 64 for all experiments in this paper. We next perform Monte-Carlo Simulation to verify that by setting = 64, the obtained distribution is very similar to
the Gaussian distribution. Assuming without loss of generality that the embedding dimension is 64 with the mean vector μ = 084 e 04 and the identity covariance matrix 64 = I E 664x64 we randomly sample 1000 embeddings from M(,, E).
18

---

Published as a conference paper at ICLR 2024
We visualize the distributions of the inner product between the pair of non-common neighbor em- beddings, i.., the first term in Eq. (10) (Rm) Rn. Um F Un. and the pair of common neighbor embeddings, i... the second term in Eq. 10 (R&) Uk AA A,Tiiin in Figure 8 We
can see that the distribution of the dot product between the pair of non-common neighbor embed- dings behaves like Gaussian distribution centering around In contrast, the distribution of the dot product between the pair of common neighbor embeddings behaves like chi-square distribution of degree 64, which also centers around 64, and this in turn verifies the Gaussian approximation. Note that the correctness of the first approximation in Eq. [1] relies on the assumption that the average of the inverse of the node's neighbors should be the same across all nodes. Although it cannot be theoretically satisfied, we still empirically verify the positive correlation between TC and the link prediction performance shown in Figure
The above derivation bridges the gap between the Topological Concentration (TC) defined in the topological space and the Approximated Topological Concentration (ATC) defined in the latent space, which theoretically justifies the approximation efficacy of ATC.
Commont niightr poins
Chi-dizihation deguse Nevscmarror naightr parz
2.00
Desily
0.00
010
0.01
0.00
-50
Figure 8: The distribution of the inner product between common neighbor pairs is statistically higher than that between non-common neighbor pairs.
D.2 DEGREE-RELATED BIAS OF EVALUATION METRICS
One previous work (Wang& & Der 2022 has empirically shown the degree-related bias of evaluation metries used in link prediction models. Following that, we go one step further and theoretically derive the concrete format of the evaluation bias in this section. We leverage untrained link prediction model to study the bias. This avoids any potential supervision signal from training over observed links and enables same degree may end up with different performances, i.e., X@K; * X@K, d, = dj. we model X@K id random variable and expect to find the relationship between its expectation and the node degree d, i.e., f: ((X@ K|d) = f(d).
to study the evaluation bias exclusively. Since nodes with the
Following many existing ranking works (He al.. 2020 Chen et al. 2021b), we assume without loss of generalizability that the link predictor T ranking the predicted neighbors based on their embedding similarity with embeddings noted as E, then we have:
Lemma 1. For any untrained embedding- link predictor 9, given the existing k: 1-11 pre- dicted neighbors for the node U, E V, the w predicted neighbor is generated by randomly selecting a node without replacement from the remaining nodes with equal opportunities, i.e., P(uog = volfus Uo?, ........11) 1) -... N N-(K-1)
Without any training, Lemma D trivially holds since embeddings of all nodes are the same, which trivially leads to the following theorem:
Theorem 2. Given the untrained embedding- link predictor P, the size of the intersection between any node's 's predicted list E, and its ground-truth list follows hypergeometric distribu- tion: E3, n Eg| HG(VV, , K, (E)) where [V] is the population size (the whole node space), K is
19

---

Published as a conference paper at ICLR 2024
the number of trials and [E]] is the number of successful states (the number of node's 's ground-trutt truth neighbors).
Proof. Given the ground-truti node neighbors ε, the predicted neighbors E. = {eat }K is formed by selecting one node at time without replacement times from the whole node space V. Since any selected node Cst can be classified into one of two mutually exclusive categories & or VLE, and by Lemma D we know that for any untrained link predictor, each unselected node has an equal opportunity to be selected in every new trial, we conclude that [&; & HD(()) K, (&,)) and by default E((E, n ( = E M = K 1 Ed
Furthermore, we present Theorem 3 to state the relationships between the LP performance under each evaluation metric and the node degree:
Theorem 3. Given that E, E follows hyper-geomerie distribution, we have:
K 0E(R@K(d) O.
E(R@K(d)-
(12)
N Od
E(P@KId) ad @E(P@K(d) N 0d N
(13)
E(F1@K()) = 2K ad 0E(FI@K(d) 2aK2 N K + ad'
(14)
3d N (K + ad)?
od @E(N@K(d) B(N@Kld) N
(15)
Od
N
Proof.
E. K
E ES
EQEE n E,
K
E(ROK|d) = E(
(16)
[3
N
[1 K
E n E(P@K,|d) E( K
E(IE, Edl
[V]
ad
(17)
K
N
21, Ed K + E,1
2K ad
E(FI@K,/1) E(
(18)
+ +ad
K + ad
I I((.E((ENE:))
EOCK I K
ΣK k=
E(N@K,ld) = E(
10
k=
logg (1++1)
(19)
Σ logg(k + 11
K
ΣR
To calculate the numerator DCG, i.c., E(EK] 1 in Eq. we model the link pre- 1oRz(k+1)
diction procedure as 1) randomly select K nodes from the whole node space V: 2) calculate [,, i.e. how many nodes among the selected nodes E, are in the ground-truth neighborhood list E.: 3) randomly select [č n E slots to position nodes in &, be mathematically formulated as:
n E, and calculate DCG. The above steps can
C(N ad, K -i)C(ad, i) C(N,K) K)
C(K,)
Σ
PO
POOKK
(K.))
1
(K.) jk
= =]
(20)
logo (k: +1)
20

---

Published as a conference paper at ICLR 2024
where O(K,) {0, ())(()))) represents all C(K, i) possible positional indices of putting nodes
into K candidate slots. Specifically ofx.0) E {0, 1j. indicates the jth positional configuration of nodes where O [K.)) O/ 1 an node is positioned at slot and O(K,y otherwise. Since our link
jkb
fk
predictor has no bias in positioning nodes in the slots by Lemma
we have p(0)) (K.)) c(K.))
and Eq. (20) can be transformed as:
K C(N ad, i)C(ad,)) C(N,K)
C(K,)) K
1 (K.8) =1 [0
(21)
i(K, j=1
log2 (A: + +
We know that only when the hthh slot is positioned node have 0 (K,4) O total C(K, 1) selections, every candidate slot k E 21.2,... K} would be selected C(K 1. 1) times to position node, which hence leads to:
and among the
jk
C(K.) K 1 (K.0 =1
K C(K - 1,5 1) logz(k: (k + 1)
(22)
loga (k 1)
We then substitute Eq. 22
into Eq.
21 as:
C(N ad, K i)C(ad. 1
C(K 1,i
K)
C(K,i)
loga (k: +1
k=1
(23)
C(N - ad, K - i)C(ad,)) i) C(K - 1,i 1) C(N,K)
K
C(K,i)
logz (k
k=1
Further substituting Eq. 23 into Eq. 19 we finally get:
C(N ad, K i)C(ad, 8) C(K - 1, 1)
E(N@Kld)
C(N,K)
C(K,i) i)
(K (K-1)
C(N ad, K - -i)C(ad,
[1-1)(K- -I)
C(N,K)
K! a(K-ij)
(24)
0=
C(N ad, K - i)C(add)) i)
1 ad
K ad
K
C(N,K) K)
K
N
E(ENE))
Based on Theorem 3 Precision, FI, and NDCG increase as node degree increases even when no observed links are used to train the link predictor, which informs the delaee-related evaluation bias and causes the illusion that high-degree nodes are more advantageous than low-degree ones observed in some previous works (Li et al. 2021 Rahmani et al. 2022).
D.3 REWEIGHTING BY LP SCORE ENHANCE 1-LAYER TC
Theorem 4. Taking the normalization term g 9(H ((HA)),)))) |H! and also assume that higher link prediction score Sij between vi and its neighhor Uj corresponds to more number of connections
between Vj and the neighborhood ATTrain Le., Sij > Su. WW Train n.V! >
Traiian
Ach rl. Train Veg, Uk EN, 1 then we have:
S H7 n nH)
[7] n nH
C.. T..rri
Σ
2 Ey Bu NTrai
C.. Train
C..Tiain
(25)
174
21

---

Published as a conference paper at ICLR 2024
Proof. By definition, we have Hy N². formed as:
A.l.Train Train then the computation of 1-layer TC is trans-
Wy Wrtrain n AATrran
C I. Train -e (() S/)) = o .
E ~ prain (WV, (T..rain (N,
WTTrain
(26)
On the other hand, we similarly transform weighted TC as:
Train
Σ
(S
n.N.taaia).
(27)
W I
Ay Train
By the relation that:
Su Sike IN Train N,N
W.
Train n.
Veg, Uo E N,, Train,1
(28)
Then have:
Cl,Train C.
(29)
Moreover, we include Figure to illustrate the idea of enhancing TC via assigning higher weights to edges connecting neighbors that have higher connections to the whole neighborhoods. We can see this case, weighted TC in Figure a(a is naturally higher than the one Figure (
V
Vo
V1
V2
V3
V4
V5
D1
V2
V3
V44
V5
(a)
(b)
Figure 9: (a) Increasing the weight of neighbors that have more connections with the whole neigh- borhood while (b) increasing the weight of neighbors that have fewer connections with the whole neighborhood. (a) would increase the weighted TC while (b) would not
E EXAMPLE DEMONSTRATING THE ADVANTAGES OF TC OVER LCC
According to the definition of local clustering coefficient (LCC) and TC, we respectively calculate their values for node Vi in Figure 10 U2, U3, 04 do not have any connec- tion among themselves, indicating node prefer inter- acting with nodes coming from significantly different do- main/community. Subsequently, the incoming neighbors Us 0g of i1 are likely to also come from other communi- ties and hence share no connections with U2 f3. which leads to the ill topological condition for predicting links of However, in this case, the clustering coefficient still maintains 0.5 because of the connections between U1 and 02/Vy /// Vaa which cannot precisely capture the ill-topology of v this case. Conversely, our Trai equals 0, re- flecting the ill topological condition of vi-
V1
12
V33
V/
V/
V
Lee Trainn 0.5,
Tc Train 0.0
(a)
Figure 10: Comparison of TC and LCC
22

---

Published as a conference paper at ICLR 2024
F DATASETS AND EXPERIMENTAL SETTINGS
This section introduces datasets and experimental settings used in this paper.
F.1 DATASET INTRODUCTION AND STATISTICS
We use five widely employed datasets for evaluating the link prediction task, including four citation networks: Cora, Citeseer, Pubmed, and Citation2, and human social network Collab. We further introduce two real-world animal social networks, Reptile and Vole, based on animal interactions.
Cora/Citeseer/Pummen
Following (Zhao et al. 2022 Chamberlain et al., 2022] Wang et al., )023). we randomly split edges into 70%/10%//00 so that there no topological distribution shift in these datasets. We use Hits @ 100 to evaluate the final performance.
Collab/Citation2: We leverage the default edge splitting from OGBL. (Hu et al. 2020). These two datasets mimic the real-life link prediction scenario where testing edges later joined in the network than validation edges and further than training edges. This would cause the topological distribution shift observed the Obs.3 of Section 3.3 For Collab, different from (Chamberlain et al., 2022] [Wag et al., (023), our setting does not allow validation edges to join the network for message- passing when evaluating link prediction performance. Therefore, the edges used for message- passing and supervision come from edges in the training set. In addition, we also consider widely used setting in prior work where the validation edges would be allowed in message-passing when evaluating in the testing stage and we term this one on Collab as Collab* (Wang al. 2023 Chamberlain et al., 2022).
we obtain the dataset from Network Repository (Rossi & Ahmed 2015). To con- struct this network, a bipartite network was first constructed based on burrow use an edge connecting a tortoise node to a burrow node indicated a burrow used by the individual. Social networks of desert tortoises were then constructed by the bipartite network into single-mode projection tortoise nodes. Node features are initialized by trainable embedding layer, and we leverage the same edge splitting 70%%/0%//0%% for
Reptile/Vole:
Table 3: Statistic of datasets used for evaluating link prediction.
Network Domain
Dataset
Nodes
EEdges
Split Type
Metric
Split Ratio
Cora 2,708
3,278
Random
Hits@ 100
70/1020%
Citeseer
3,327
4.676
Random
Hits@ 100
70/10/20%
Citation Network
Pubmed
18.717
44,327
Random
Hits@
70/10/20%
Citation2
2,927.963 .663
30,561,187
Time
MRR
Default
Social Network
Collab
235,868
1,285,465
Time
H5
Default
Reptile
787
Random
70/10/203
Animal Netwark
Vole
1480
3935
Random
Hits@ 100
70/10/20%
F.2 HYPERPARAMETER DETAILS
For all experiments, we select the best configuration on validation edges and report the model per- formance testing edges. The search space for the hyperparameters of the CCN/SAGF//LightCCC baselines and their augmented variants GCN,./SSA............
are: graph convolutional layer (1, 2, 3). hidden dimension of graph encoder {64, 128, 256), the learning rate of the encoder and predic- tor {0.001, 0.005, 0.01). dropout {0.2, 0.5, 0.8). training epoch { 550, 500, 1000). batch size (256, 1152, 64 1024] (Hu et al., 2020; Chamberlain et al., 2022 Wang et al., 2023). weights 11 10, 20, 50 warm up epochs Twaam E
E {0.5. 1, 2, 2, 4]. the update interval 21,2,5, 10, 30, 50). For baseline NCN we directly run their code using their default best- performing configurations on Cora/Citeseer/PbmeeeCC itation, we directly take the result from the original paper. We use cosine similarity metric as the similarity function & in computing ATC.
but for Citation2, due to memory lim-
23

---

Published as a conference paper at ICLR 2024
G ADDITIONAL RESULTS
To demonstrate that the observations made previously in Section 3 datasets, here we present the comprehensive results on all datasets we study in this paper as follows.
also generalize to other
G.1 LINK PREDICTION PERFORMANCE GROUPED BY TC
TelCCo LAMGGN
Pubeea LABSEN
(h OCN
10 LABEGON
Figure 11: LP performance grouped by Te for all nodes
Prociim
NHOG
Reudl
MIK
Figure 12: LP performance grouped by Test for low Test nodes
24

---

Published as a conference paper at ICLR 2024
G.2 LINK PREDICTION PERFORMANCE GROUPED BY Tran
Figure LP performance grouped by Trarain for all nodes
Peineeh GDN
Co Ligetes
Figure 14: LP performance grouped by Train for low TC nodes
25

---

Published as a conference paper at ICLR 2024
G.3 LINK PREDICTION PERFORMANCE GROUPED BY DEGREE" Test
5CD ECO
1300
MiPhbeed
Figure 15: LP performance grouped by Degree Test for all nodes
Test
Rejelll LigHOCN
C.
Figure 16: LP performance grouped by Degree Test for low Test-Degree nodes
26

---

Published as a conference paper at ICLR 2024
G.4
LINK PREDICTION PERFORMANCE GROUPED BY DEGREE Train
Procide
Reall
VIR BB
AAGE
(OYAL LANSEN
SoPhbeed LANGGEN
P. GCX
Figure 17: LP performance grouped by Degree Train for all nodes
Tole Crve
Regiell JANGEEN
Polwed LigHOEN
Polee GIS
Figure 18: LP performance grouped by Degree Train for low Degree Train nodes
27

---

Published as a conference paper at ICLR 2024
G.5 RELATION BETWEEN LP PERFORMANCE AND TC GRAPH-LEVEL
Swit
Tr
Tears
Trars
Trans
Tears
Figure 19: Relation between LP performance and TC Graph-level
G.6 RELATION BETWEEN Trar AND Test
1C110
30
Figure 20: Relation between Trana and TC on Collab/Citation2
G.7 DIFFERENCE IN TC vs DIFFERENCE IN PERFORMANCE BEFORE/AFTER APPLYING REWEIGHITING
G.8
CORRELATION OF THE PERFORMANCE WITH TC AND DEGREE
Here we present the comprehensive correlation of the performance with TC and Irin As the performance is evaluated under different K, further define the absolute av- erage/the typical average correlation across different K values to reflect the absolute correlation strength/the consistency of the correlation average:
Absolute Avg. Xa-
1
Σ
|
Basic Avg. Avg-xax
1
Σ
X@k
4
4
20,5,00,00,50
(5,10,0000500
28

---

Published as a conference paper at ICLR 2024
2.01
(400 20011
1ast oan
rase and
coat cast eat, Ban seas osn
rest alti
Fata cwrl
elat een
ureg
alnu Lea.
(aoi oall mon,eay aay non (18)
eon eit ban (9aM ais
mnt
ram
220
Euke
(l0% una)
andy Fass cou endi (ral) (e.) pau (80% dre))
Loo, and
(ast as0
Galo (e9)
eun dadi 68
(8
Nww car
tue-
Exees
Goee
600
(oop cost
mat nany
(609 (o8)
(2.9) (le))
Loxt Jit (aaa dog
daal (Pa) nan
(asy dtel)
201 reat
(015), (159
matt
(9th
dooteon namy
Lang
caist dan
(Bat, wan
(dac,
rank moot eon
(991,
(819) (899,699))
Tatesition (tan
mfat cuny
didk-oal (1i6k.0 (18))
can
eRat end (8 4:09
Extt
Exme
colt 2.00
forn 4.0
(010 slog
cattz titat sto1
most dan
(Pa) caa
edeat abas)
Edto, dan thot cat)
dn oso
eat 000
rent (an thatl oon
in 2189
10
Figure 21: Relation between TC Train
and Te on Collab by running GCN
0.24
600
Gesp. 4.911
Eddit cas
(.3.0.3)
(eop 4000
clss Ei
M.K.0.. 2.3)
com sal
elos 6.10 e es e.
Blx 4.30
Edot cusy
e20
el a.
cein 40t1
past stay
(R.22 4.55
100'09
E.
Fath ausl
Elt (14)
9.5
19.24 eal
(om dll))
rade 511)
(8.5 a3
ram alie
(aad s1e))
di eun
(6.0) ale)
(aah) craa
630
ram att
030
(8.58 4555
1e.7
(8.54
Son
1922 wap
Jao) Lart aig
1033 LB
Lest dog
(aet dugg
(0%
sally
2.3
vatet
calan
Tecmn ta
ii) Lodn,
(8.3...0) 333
el
reo) ael)
89.0 83e
rntor.000 d0g)
(.0% (16))
(d. slo)
88 (3)
18 A30 9.
10.35
88.6
Figure 22: Relation between Tran and Te Collab by running SAGE
29

---

Published as a conference paper at ICLR 2024
Table 4: The correlation between TC (Degree and the GCN's LP performance Collab. We note that the formal definitions of Absolute Avg. and Basic Avg. provided in
Section G.8 and they represent the average absolute and simple average correlation, respectively, across the range of @ K for the given metric; these are also then calculated overall.
Metric
@5
@ 10
@ 20
@
Absolute Avg.
Basic Avg.
Precision
0.2252
0.1925
0.1353
0.0578
0).1577
0.1527
0.2601
0.2364
0.1733
0.0790
0.1872
0.1872
TC
NDCG
0.2279
0.2427
0.2375
0.2206
0.2322
0,2322
Recall
0.2296
0.2358
0.2156
0.1754
0.2141
0,2141
Hits N
0.2057
0.1800
0.1328
0.0717
0.1476
0.1476
MRR
0.2044
0.2044
0.2044
0.1867
0.1867
Precision
0.2573
0.2832
0.2788
0.2387
0.2645
0.2645
F1
0.2425
0.2901
0.2991
0.2641
0.2740
0,2740
NDCG
0,2066
0.2330
0.2521
0.2624
0.2385
0.2385
TC
Recall
0.1742
0.2179
0.2428
0.2514
0.2216
0.2216
Hits
0.2445
0.2674
0,2720
0.2620
0.2615
0.2615
MRR
0.2350
0.2350
0.2350
0,2520
0,2520
Precision
0,5184
0.5437
0.5107
0.4127
0.4964
0.4964
F1
0.5858
0.6311
0.5964
0.4799
0.5733
0.5733
NDCG
0.5443
0.6282
0.6706
0.6902
0.6333
0.6333
Test
Recall
0.5644
0.6753
0.7324
0.7533
0.6814
0.6814
Hits
0.5272
0.5816
0.5924
0.5720
0.5683
0.5683
MRR
0.5085
0.5085
0.5085
0.5905
0.5905
Precision
-0.1261
-0.0829
0.0006
0.1440
0.0884
-00161
F1
-0.1997
-0.1663
-0.0813
0.0812
0.1321
-0.0115
NDCG
-0.1822
-0.2017
-0.1985
-0.1750
0.1894
-0.1894
Degree Train
Recall -0.2183
-0.2288
-0.2118
-0.1681
0.2068
-0.2068
Hits
-0.1395
-0.1164
-0.0658
0.0055
0.0818
-0.0791
MRR
-0.1349
-0.1349
-0.1349
0.1397
-0.1166
Precision
0.0047
0.0472
0.1117
0.2141
0.0944
0.0944
F1
-0.0823
-0.0469
0.0200
0.1416
0.0727
0.0081
NDCG
-0.0608
-0.0803
-0.0838
-0,0736
0.0746
-0.0746
Degree Val
Recall
-0.
-0. 1296
-0.1269
-0.1100
0.1217
-0.1217
Hits
-0.0063
0.0171
0.0481
0.0848
0.0391
0.0359
MRR
-0.0108
-0.0108
-0.0108
0.0805
-0.0116
Precision
0.1075
0.1833
0.2924
0.4617
0.2612
0.2612
F1
-0,0669
0.0043
0.1249
0.3375
0.1334
0.1000
NDCG
-0.034
-0.0723
-0.0814
-0.0668
0.0636
-0.0636
Degree Test
Recall
-0.1678
-0.1856
-0.187
-0.1724
0.1782
-0.1782
0.0785
0.1
0.1407
0.1718
0.1253
0.1253
MRR
0.0727
0.0727
0.0727
0.1524
0,0489
Precision
0.2199
0.1646
0.0875
-0.0033
0.1198
0.1162
F1
0.2806
0.2259
0.1353
0.0161
0.1645
0.1645
NDCG
0.2811
0.2891
0.2748
0.2491
0.2735
0,2735
Subgraph Density
Recall
0.2911
0.2783
0.2399
0.1834
0.2482
0.2482
H
0.2265
0.1842
0.1196
0.0423
0.1432
0.1432
MRR
0.2331
0.2331
0.2331
0.1898
0.1891
30

---

Published as a conference paper at ICLR 2024
Table 5: The correlation between /CC" on Citation2. We note that the formal definitions of Absolute Avg. and Basic Avg. provided in Section G.8 and they represent the average absolute and simple average correlation, respectively, across the range of @ @K for the given metric; these are also then calculated overall.
and the GCN's LP performance
Metric
@
@ 10
@ 20
@
Absolute Avg.
Basic Avg.
Precision
0.0839
0.1312
0.1784
0.2157
0).1523
0.1523
0.0849
0.1323
0.1795
0.2165
0.1533
0.1533
NDCG
0.0773
0.1164
0.1585
0.2012
0.1384
0.1384
TC
Recall
0.0860
0.1346
0.1845
0.2265
0.1579
0.1579
Hits N
0.0840
0.1314
0.1791
0.2182
0.1532
0.1532
MRR
0.1229
0.1229
0.1229
0.1510
0.1510
Precision
0.0575
0.0868
0.1200
0.1479
0.1031
0.1031
F1
0.0581
0.0874
0.1206
0.1484
0.1036
0.1036
NDCG
0.0545
0.0790
0.1078
0.1377
0.0948
0.0948
TC
Recall
0.0586
0.0884
0.1231
0.1540
0.1060
0.1060
Hits
0.0574
0.0870
0.1206
0.1500
0.1038
0.1038
MRR
0.0846
0.0846
0.0846
0.1022
0.1022
Precision
0,1797
0.2541
0.3313
0.3996
0.2912
0,2912
F1
0.1812
0.2558
0.3328
0.4008
0.2927
0,2927
NDCG
0.1706
0.2365
0.3071
0.3825
0.2742
0.2742
Test
Recall
0.1829
0.2599
0.3401
0.4141
0.2993
0.2993
Hits
0.1797
0.2550
0.3331
0.4048
0.2932
0,2932
MRR
0.2512
0.2512
0.2512
0.2901
0.2901
Precision
-0,0288
-0.0406
-0.0536
-0.0689
0.0480
-0.0480
F1
-0.0295
-0.0415
-0.0546
-0.0699
0.0489
-0.0489
NDCG
-0,0285
-0.0394
-0,0522
-0.0692
0,0473
-0.0433
Degree Train
Recall -0.0305
-0.0436
-0.0589
-0.0791
0.0530
-0.0530
Hits
-0.0289
-0.0408
-0.0540
-0.0708
0.0486
-0.0486
MRR
-0.0421
-0.0421
-0.4211
0.0492
0.0492
Precision
0.0161
0.0229
0.0300
0.0393
0.0271
0.0271
F1
0.0156
0.0220
0.0289
0.0381
0.0262
0.0262
NDCG
0.0150
0.0199
0.0248
0.0305
0.0226
0.0226
Degree Val
Recall
0.0150
0.0203
0.0252
0.0301
0.0227
0.0227
Hits
0.0161
0.0232
0.0300
0.0384
0.0269
0.0269
MRR
0.0234
0.0234
0.0234
0.0251
0.0251
Precision
0.0060
0.0113
0.0190
0.0364
0.0182
0.0182
F1
-0,0009
0.0047
0.0128
0.0314
0,0125
0.0120
NDCG
-0.0086
-0.0113
-0.0147
-0.0185
0.0133
-0.0133
Degree Test
Recall
-0.0135
-0.0185
-0.0251
-0.0344
0.0229
-0.0229
0.0051
0.0081
0.0120
0.0159
0.0103
0.0103
MRR
0.0104
0.0104
0.0104
0.0154
0.0009
Precision
0.0809
0.1217
0.1607
0.1916
0.1387
0.1387
F1
0.0823
0.1231
0.1621
0.1926
0.1400
0.1400
NDCG
0.0761
0.1111
0.1476
0.1853
0.1300
0.1300
Subgraph Density
Recall
0.0842
0.1268
0.1691
0.2063
0.1466
0.1466
Hits
0.0811
0.1219
0.1618
0.1956
0.1401
0.1401
MRR
0.1144
0.1144
0.1144
0.1391
0.1391
31

---

Published as a conference paper at ICLR 2024
Table 6: The correlation between /TC DDegree and the GCN's LP performance Cora. We note that the formal definitions of Absolute Avg. and Basic Avg. provided in
Section G.8 and they represent the average absolute and simple average correlation, respectively, across the range of @ K for the given metric; these are also then calculated overall.
Metric
@
@ 10
@ 20
@
Absolute Avg.
Basic Avg.
Precision
0.0985
0.1006
0.1238
0.1571
0.12T0
0.12T0
0.0989
0.1042
0.1239
0.1597
0.1217
0.1217
NDCG
0.0933
0.0990
0.1088
0.1306
0.1079
0.1079
TC
Recall
0.1020
0.1042
0.1162
0.1568
0.1198
0.1198
Hits N
0.0961
0.1000
0.1226
0.1617
0.1201
0.1201
MRR
0.0869
0.0869
0.0869
0.1181
0.1181
Precision
0.0342
0.0456
0.0840
0.0903
0.0635
0.0635
F1
0.0296
0.0406
0.0820
0.0907
0.0607
0.0607
NDCG
0.0215
0.0259
0.0446
0.0526
0.0362
0.0362
TC
Recall
0.0257
0.0322
0.0724
0.0841
0.0536
0.0536
Hits
0.0331
0.0413
0.0742
0.0932
0.0605
0.0605
MRR
0.0291
0.0291
0.0291
0.0549
0.0549
Precision
0.4694
0.4702
0.4667
0.3977
0.4510
0,4510
F1
0.4952
0.4964
0.4948
0.4216
0,4770
0,4770
NDCG
0.4970
0.5239
0.5551
0.5759
0.5380
0.5380
Test
Recall
0.4941
0.5109
0.5448
0.5347
0.5211
0.5211
Hits
0.4749
0.4909
0.5130
0.4866
0.4914
0.4914
MRR
0.4920
0.4920
0.4920
0.4957
0.4957
Precision
0.0751
0.0970
0.1701
0.3268
0.1673
0.1673
F1
-0.0039
0.0237
0.0938
0.2549
0.0941
0.0921
NDCG
-0,0156
-0.0276
-0.0283
-0,0191
0,0227
-0.0227
Degree Train
Recall -0.0432
-0.0547
-0.0568
-0.0529
0.0519
-0.0519
Hits
0.0656
0.0650
0.0862
0.1135
0.0826
0.0826
MRR
0.0307
0.0307
0.0307
0.0837
0.0837
Precision
0.0433
0.0623
0.1138
0.2248
0.1111
0.1111
F1
-0.0230
0.0012
0.0508
0.1634
0.0596
0.0481
NDCG
-0.0235
-0.0336
-0.0369
-0.0361
0.0325
-0.0325
Degree Val
Recall
-0.0570
-0.0648
-0.0689
-0.0784
0.0673
-0.0673
Hits
0.0253
0.0222
0.0308
0.0431
0.0304
0.0304
MRR
0.0144
0.0144
0.0144
0.0602
0.0179
Precision
0.1669
0.2104
0.3046
0.4890
0.2927
0.2927
F1
0.0537
0.1111
0.2127
0.4149
0.1981
0.1981
NDCG
0.0004
-0.0104
-0.0082
0.0060
0.0063
-0.0031
Degree Test
Recall
-0.0599
-0.0702
-0.0760
-0.0781
0.0711
-0.0711
0.1406
0.1487
0.1624
0.1865
0.1596
0.1596
MRR
0.1116
0.1116
0.1116
0.1455
0.1153
Precision
0.0794
0.0900
0.0796
0.0381
0.0718
0.0718
F1
0.1088
0.1189
0.1066
0.0580
0.0981
0.0981
NDCG
0.1157
0.1378
0.1543
0.1674
0.1438
0.1438
Subgraph Density
Recall
0.1330
0.1690
0.2015
0.2272
0.1827
0.1827
H
0.0851
0.1
0.1257
0.1385
0.1151
0.1151
MRR
0.0976
0.0976
0,0976
0.1223
0.1223
32

---

Published as a conference paper at ICLR 2024
Table 7: The correlation between /TC on Citeseer. We note that the formal definitions of Absolute Avg. and Basic Avg. provided in Section they represent the average absolute and simple average correlation, respectively, across the range of @ K for the given metric; these are also then calculated overall.
and the GCN's LP performance
Metric
@
@ 10
@.0
60
Absolute Avg.
Basic Avg.
Precision
0.3330
0.3735
0.3898 0.3830
0.3698
0.3698
0.3324
0.3803 0.4056 0.4049
0.3808
0.3808
TC
NDCG
0.2831
0.3226 0.3570 0.3879
0.3377
0.3377
Recall
0.3001
0.3481 0.3920 0.4295
0.3674
0.3674
Hits N
0.3386
0.3901 0.4287 0.4603
0.4044
0.4044
MRR
0.3194
0.3194
0.3194
0.3720
0.3720
Precision
0.2796 0.2962
0.3224 0.3229
0.3053
0.3053
F1
0.2756
0.2947 0.3291 0.3365
0.3090
0,3090
NDCG
0.2508
0.2662 0.2929 0.3118
0.2804
0.2804
TC
Recall
0.2491
0.2585 0.2928 0.3086
0.2773
0.2773
Hits N
0.2801
0.3049 0.338 0.3496
0.3182
0.3182
MRR
0.2763
0.2763
0.2763
0.2980
0.2980
Precision
0.6786 0.698
0.6745 0.6220
0.6683
0.6683
F1
0.7157
0.7385 0.7207 0.6678
0.7107
0.7107
NDCG
0.7037
0.7540 0.7946 0.8300
0.7706
0.7706
Tesest
Recall
0.7299
0.7797 0.8258 0.8588
0.7986
0.7986
0.7127
0.7595 0.7979 0.8216
0.7729
0.7729
MRR
0.7070
0.7070
0.7070
0.7442
0.7442
Precision
0.2472 0.3523 0.4591 0.5861
0.4112
0.4112
F1
0.1867 0.2727 0.3872 0.5408
0.3469
0.3469
NDCG
0.1303 0.1645 0.2022 0.2475
0.1861
0.1861
Degree Train
Recall
0.1144
0.1532 0.2047 0.2591
0.1829
0.1829
Hits
0.2538
0.3181 0.3581 0.3886
0.3297
0.3297
MRR
0.2227
0.2227
0.2227
0.2913
0.2913
Precision
0.1431
0.1866
0.2255 0.277
0,2081
0.2081
0.1147
051582 0.2053 0,2693
0.1869
0.1869
NDCG
0.0845
0.1014 0.1194 0.1429
0.1121
0.1121
Degree
Recall
0.0693
0.0880 0.1113 0.1411
0.1024
0.1024
Hits
0.1438 0.1683 0.1857 0.2148
0.1782
0.1782
MRR
0.1366
0.1366
0.1366
0.1575
0.1575
Precision
0.3052 0.4412 0.5704 0.7223
0.5098
0.5098
F1
0.1919
0.3133 0.4639 0.6597
0.4072
0,4072
NDCG
0.0949 0.1220 0. 1.1548 0.1975
0.1423
0.1423
Degree
Recall
0.0323
0.0562 0.0909 0.1314
0.0777
0.0777
0.2745
0.3258 0,3378 0.3369
0.3188
0.3188
MRR
0.2444
0.2444
0.2444
0.2911
0.2911
Precision
0.1559
0.1412 0.1168 0.0858
0.1249
0.1249
F1
0.1867
0.1699 0.1420 0.1035
0.1505
0.1505
NDCG
0.2006
0.2097 0.2176 0.2235
0,2129
0.2129
Subgraph Density
Recall
0.2218
0.2289 0.2411 0.2491
0.2352
0.2352
0.1768 0.1799 0.1982 0.2097
0.1912
0.1912
MRR
0.1759
0.1759
0.1759
0.1829
0.1829
33

---

Published as a conference paper at ICLR 2024
Table 8: The correlation between "TT and the GCN's LP performance on Pubmed. We note that the formal definitions of Absolute Avg. and Basic Avg. provided in Section G.8 and they represent the average absolute and simple average correlation, respectively, across the range of @ @ for the given metric; these are also then calculated overall.
Metric
@5
@ 10
@ 20
@
Absolute Avg.
Basic Avg.
Precision
0.1981
0.23588
0.2681
0.2924
0).2486
0.2486
0,1690
0.2216
0.2652
0.2961
0.2380
0.2380
TC
NDCG
0.1195
0.1379
0.1600
0.1831
0.1501
0.1501
Recall
0.0917
0.1142
0.1336
0.1397
0.1198
0.1198
Hits N
0.1932
0.2267
0.2485
0.2513
0.2299
0.2299
MRR
0.1920
0.1920
0.1920
0.1973
0.1973
Precision
0.1769
0.2180
0.2653
0.3134
0.2434
0.2434
F1
0.1253
0.1815
0.2462
0.3092
0.2156
0,2156
NDCG
0.0780
0.0846
0.1046
0.1303
0.0994
0.0994
TC
Recall
0.0417
0.0503
0.0672
0.0804
0.0599
0.0599
Hits
0.1627
0.1882
0.2068
0.2077
0.1914
0.1914
MRR
0.1607
0.1607
0.1607
0.1619
0.1619
Precision
0.3769
0.3989
0.4078
0.3909
0.3936
0.3936
F1
0.4011
0.4258
0.4329
0.4088
0.4172
0,4172
NDCG
0.3902
0.4231
0.4547
0.4870
0.4388
0.4388
Test
Recall
0.3809
0.4080
0.4286
0.4335
0.4128
0.4128
Hits
0.3923
0.4247
0.4463
0.4436
0.4267
0.4267
MRR
0.4097
0.4097
0.4097
0.4178
0,4178
Precision
0.2433
0.3108
0.3761
0.4849
0,3538
0.3538
F1
0.1019
0.1970
0.2987
0.4456
0.2608
0.2608
NDCG
0.0477
0.0366
0.0441
0,0715
0,0500
0,0500
Degree Train
Recall -0.0402
-0.0386
-0.0385
-0.0357
0.0383
-0.0383
Hits
0.2080
0.2404
0.2504
0.2612
0.2400
0.2400
MRR
0.2051
0.2051
0,2051
0.1886
0.1733
Precision
0.1823
0.2290
0.2849
0.3681
0.2661
0.2661
F1
0.0676
0.1368
0.2220
0.3359
0.1906
0.1906
NDCG
0.0293
0.0164
0.0221
0.0407
0.0271
0.0271
Degree Val
Recall
-0.0429
-0.0466
-0.0459
-0.0476
0.0458
-0.0458
Hits
0.1536
0.1749
0.1831
0.1872
0.1747
0.1747
MRR
0.1573
0.1573
0.1573
0.1408
0.1225
Precision
0.3073
0.3898
0.4719
0.6133
0.4456
0.4456
F1
0.1251
0.2423
0.3716
0.5624
0.3254
0.3254
NDCG
0.0588
0.0406
0.0480
0.0821
0.0574
0.0574
Degree Test
Recall
-0.0537
-0.0565
-0.0605
-0.0575
0.0571
-0.0571
0.2615
0.2966
0.3030
0.3099
0,2928
0,2928
MRR
0.2556
0.2556
0.2556
0,2356
0.2128
Precision
0.1002
0.0746
0.0414
-0.0146
0.0577
0.0504
F1
0.1732
0.1319
0.0792
0.0030
0.0968
0.0968
NDCG
0.2146
0.2307
0.2357
0.2344
0.2289
0.2289
Subgraph Density
Recall
0.2475
0.2547
0.2540
0.2428
0.2498
0.2498
H
0.1343
0.1330
0.1338
0.1288
0.1325
0.1325
MRR
0.1430
0.1430
0. 0.1430
0.1531
0.1517
34

---

Published as a conference paper at ICLR 2024
Table 9: The correlation between
(Degree and the GCN's LP performance Vole. We note that the formal definitions of Absolute Avg. and Basic Avg. provided in
Section G.8 and they represent the average absolute and simple average correlation, respectively, across the range of @ K for the given metric; these are also then calculated overall.
Metric
@5
@ 10
@02
@
Absolute Avg.
Basic Avg.
Precision
0.2725
0.2710
0.2648
0.22887
01.2593
0.2593
0.2985
0.2981
0.2869
0.2401
0.2809
0.2809
TC
NDCG
0.2714
0.3012
0.3300
0.3497
0.3131
0.3131
Recall
0.2946
0.3267
0.3677
0.3917
0.3452
0.3452
Hits N
0.3113
0.3307
0.3694
0.3988
0.3526
0.3526
MRR
0.2721
0.2721
0.2721
0.3102
0.3102
Precision
0.1375
0.1717
0.1847
0.1721
0.1665
0.1665
F1
0.1233
0.1690
0.1871
0.1739
0.1633
0.1633
NDCG
0.0931
0.1201
0.1403
0.1479
0.1254
0.1254
TC
Recall
0.0825
0.1251
0.1570
0.1548
0.1299
0.1299
Hits
0.1347
0.1558
0.1815
0.1814
0.1634
0.1634
MRR
0.1219
0.1219
0.1219
0.1497
0.1497
Precision
0,5547
0.4822
0.3937
0.2527
0.4208
0,4208
F1
0.6498
0.5597
0.4449
0.2742
0,4822
0,4822
NDCG
0.7395
0.7712
0.7954
0.8030
0.7773
0.7773
Test
Recall
0.7325
0.7384
0.7367
0.6812
0.7222
0.7222
Hits
0.6470
0.6529
0.6452
0.6016
0.6367
0.6367
MRR
0.6950
0.6950
0.6950
0.6078
0.6078
Precision
0.2103
0.2728
0.3620
0.4508
0.3240
0.3240
F1
0.1387
0.2253
0.3391
0.4508
0.2885
0.2885
NDCG
0.0180
0.0352
0.0760
0.1222
0,0629
0,0629
Degree Train
Recall
0.0238
0.0479
0.1111
0.1993
0.0955
0.0955
Hits
0.1688
0.1977
0.2551
0.2989
0.2301
0.2301
MRR
0.0512
0.0512
0.0512
0.2002
0.2002
Precision
0.0312
0.0747
0.1182
0.1758
0.1000
0.1000
F1
-0.0135
0.0414
0.0989
0.1685
0.0806
0.0738
NDCG
-0.0527
-0.0455
-0.0336
-0.0153
0.0368
-0.0368
Degree Val
Recall
-0.0670
-0.0487
-0.0309
0.0059
0.0381
-0.0352
Hits
0.0077
0.0180
0.0368
0.0599
0.0306
0.0306
MRR
-0.0215
-0.0215
-0.0215
0.0572
0.0265
Precision
0.3731
0.5111
0.6562
0.8126
0.5883
0.5883
F1
0.2040
0.3944
0.5926
0.7916
0.4957
0.4957
NDCG
0.0004
0.0257
0.0722
0.1330
0.0578
0.0578
Degree Test
Recall
-0.0942
-0.0697
-0.0301
0.0419
0.0590
-0.0380
0.2320
0.2604
0.2731
0.2529
0.2546
0.2546
MRR
0.1642
0.1642
0.1642
0,29TI
0.2717
Precision
0.0744
0.0369
-0.0119
-0.0815
0.0512
0.0045
F1
0.1372
0.0860
0.0187
-0.0689
0.0777
0.0433
NDCG
0.2205
0.2341
0.2398
0.2398
0.2336
0,2336
Subgraph Density
Recall
0.2178
0.2366
0.2495
0.2545
0.2396
0.2396
H
0.1206
0.1493
0.1688
0.2138
0.1631
0.1631
MRR
0.2026
0.2026
0.2026
0.1530
0.1368
35

---

Published as a conference paper at ICLR 2024
Table 10: The correlation between TC /CT= and the GCN's LP performance Reptile. We note that the formal definitions of Absolute Avg. and Basic Avg. provided in Section G.8 and they represent the average absolute and simple average correlation, respectively, across the range of @ K for the given metric; these are also then calculated overall.
Metric
@
@ 10
@.0
Absolute Avg.
Basic Avg.
Precision
0.5189
0.5084 0).4977 0.5009
0.5065
0.5065
0.5420
0.5307 0.5146 0.5090
0.5241
0.5241
NDCG
0.5298 0.5502 0.5636 0.5741
0,5544
0,5544
TC
Recall
0.5097
0.5176 0.5343 0.5475
0.5273
0.5273
Hits N
0.5208 0.5278 0.5407 0.5502
0.5349
0.5349
MRR
0.5300
0,5300
0.5300
0.5294
0.5294
Precision
0.3994 0.4316 0.4550 0.4647
0,4377
0,4377
F1
0.3753
0.4250 0.4573 0,4670
0,4312
0,4312
NDCG
0.3183
0.3535 0.3790 0.3909
0.3604
0.3604
TC
Recall
0.2670
0.3085 0.3525 0.3744
0.3256
0.3256
Hits N
0.3213
0.3483 0.3675 0.3840
0.3553
0.3553
MRR
0.3666
0.3666
0.3666
0.3820
0.3820
Precision
0.7083 0.7000 0.6739 0.6506
0.6832
0.6832
F1
0.7898
0.7629 0.7138 0.6678
0.7336
0.7336
NDCG
0.8475
0.8897 0.9029 0.9072
0.8868
0.8868
Tesest
Recall
0.8573
0.8858 0.8931 0.8759
0,8780
0,8780
0.8276 0.8566 0.8604 0.8495
0.8485
0.8485
MRR
0.8163
0.8163
0.8163
0,8060
0,8060
Precision
0.4998 0.5294 0.5664 0,5947
0.5476
0.5476
F1
0.5082
0.5411 0.5788 0.6017
0.5575
0.5575
NDCG
0.4247
0.4572 0.4914 0.5120
0,4713
0.4713
Degree Train
Recall 0.4338
0.4598 0.5201 0.5615
0.4938
0.4938
Hits
0.4998
0.5073 0.5391 0.5664
0.5282
0.5282
MRR
0.4369
0.4369
0.4369
0.5197
0.5197
Precision
0.3185
0.3577 0.3797 0.3924
0.3621
0.3621
0.3022
0.3546 0.3840 0.3956
0.3591
0.3591
NDCG
0.2285
0.2617 0.2858 0.2985
0.2686
0.2686
Degree
Recall
0.1997
0.2384 0.2830 0.3093
0.2576
0.2576
Hits
0.2729
0.2938 0.3165 0.3339
0.3043
0.3043
MRR
0.2677
0.2677
0.2677
0.3103
0,3103
Precision
0.6833
0.7492 0.7935 0.8118
0.7595
0.7595
F1
0.5477
0.6726 0.7556 0.7968
0.6932
0.6932
NDCG
0.3062 0.3404 0.3676 0.3790
0.3483
0.3483
Degree
Recall
0.1840
0.2103 0.2429 0.2532
0.2226
0.2226
0.3940 0.3555 0.3381 0.3283
0.3540
0.3540
MRR
0.4468
0.4468
0.4468
0.4755
0.4755
Precision
0.2482
0.2491
0.2211 0.2022
0,2302
0.2302
F1
0.2943
0.2849 0.2420 0.2108
0.2580
0.2580
NDCG
0.3560
0.3819 0.3792 0.3765
0.3734
0).734
Subgraph Density
Recall
0.3588
0.3928 0.3777 0.3607
0.3725
0.3725
0.3440 0.3891 0.3837 0.3745
0.3728
0,3728
MRR
0.3510
0.3510
0.3510
0.3214
0.3214
36

---

Published as a conference paper at ICLR 2024
H EDGE REWEIGHTING ALGORITHM
Here present edge reweigting algorithm to enhance the link prediction performance by mod- ifying the graph adjacency matrix in pessage-passinge We normalize the adjacency matrix to get A and A as defined the algorithm below.
Algorithm 1:
Edge Reweighting to Boost LP performance
Input:
The input training graph (A, X, Ehrim, D), graph encoder fe,, link predictor ge, update interval training epochs 7', warm up epochs 1 and weights y for combining original adjacency
matrix and the updated adjacency matrix. The validation adjacency/degree matrix Val /D that only includes edges in the validation set.
Compute the normalized adjacency matrices Ä = D-0.5 AD D =D A
Na A
A
for I,.... do
1% + or T then L A = -
paaggigg and LP update model parameters for mini-batch of edges Ed C Train do Sample negative edges Eh.-, s.t., |8 (8 Compute node embeddings H 5 (A',X) X)
Compute link prediction scores E = S0p (H; V(i,) E Thin
_b Ed Eerfees log EJj + E EE log(1 E,,)
10
Update θ - O oo--- Cb. 07 + 0 V Vo;- - bbr
11
/. Update ad acency matrix to enhance weighted TC if 7%4 == ond + Twarm then
Compute node embeddings H" = fo; (A X);
13
14
Using training neighbors to reweigh then Average pooling the neighborhood embeddings N AH if Using validation neighbors to reweigh then Average pooling the neighborhood embeddings N Vil H
15
16
17
exploe; (NI
18
Compute the link prediction scores ST, = ΣT= explae (NÇ.
Update the adjacency matrix A Ā 757
Return: A" .00
20
I REWEIGH EDGES FOR BASELINES WITHOUT MESSAGE-PASSING
we enhance node Ta by reweighing the edges in wessagg-passing. However, for some state-of-the ofte--of-theaat baselines Chamberlain et al. (2022) that directly employ the neural transformation rather than message- message-passing to obtain node embeddings, reweigh edges in computing the binary cross entropy loss in the training stage as follows:
As discussed in Section 4
C
(wiy
Σ Gi E
log E, + Wmn
Σ Cmn EE
log(1 E E,,)))
(30)
Eyeet
where Wij = (N, quantifies the edge weight between e; and vú with or being the Sigmoid function and being the cosine similarity. N; is the node embedding of o; obtained in Eq. 2
37

---

Published as a conference paper at ICLR 2024
Table 11: Comparing the efficiency (s) between X and our proposed X
Baseline
Cora
Citeseer Pubmed Collab Reptile
Vole
GCN
19,5
15.5
158.4
2906
18.3
53.8
GCN
21.1
17.2
158.5
2915
17.0
53.0
SAGE
22.3
17.0
189.8
2970
20,9
61.2
SAGEnw
23.8
20.5
192.4
2982
21.7
61.9
BUDDY
3.41
4.51
15.51
906.18
2.50
4.99
BUDDY, 3.98
4.92
14.56
907.52
2.62
5.06
J COMPARING THE EFFICIENCY BETWEEN BASELINE AND THEIR AUGMENTED VERSION BY TC
Here we compare the running time (s) of each baseline and their corresponding augmented ver- sion by uniformly testing them on the same machine in Table 11 We can see that equipping our proposed rewcighting strategy could enhance the performance but only lead to marginal computa- tional overhead. This is because firstly, we only change the weight of existing edges and hence the number of edge weights be calculated is linear to the network size. Secondly, we leverage the pre-computed node embeddings to compute the edge weights. Thirdly, only periodically update the edge weights.
K REWEIGHTING TRAINING NEIGHBORS BASED ON THEIR CONNECTIONS TO TRAINING NEIGHBORS OR VALIDATION NEIGHBORS
As discussed in Obs. 3, due to the topological distribution shift, the newly joined neighbors of one node become less and less connective to the previous neighbors of that node. Therefore, the train- ing neighbors of one node share fewer connections with the testing neighbors of that node than the validation neighbors. This motivates us to further improve our reweighting strategy based on vali- dation neighbors rather than training neighbors. The intuition is that when performing message- passing to aggregate training neighbors' information for each node, we want to incorporate those training neighbors with more connections to that node's validation neighbors instead of those training neighbors with more connections to that node's training neighbors. Technically, we include additional steps 14-17 to consider two scenarios in Algorithm (1) reweighting based on the connections of training neighbors to training neighbors and (2) reweighting based the connections of training neighbors validation neighbors. We experiment on Collab to compare the the performance of reweighting based on validation neighbors is higher than reweighting based on training neighbors. This demonstrates that the validation neighbors are more connected to the testing neighbors, justifying the existence of the topologiaal distribution shift.
performance of these two scenarios in Table 12 We
Table 12: Comparing the link prediction performance on Collab between reweighting based on training neighbors and reweighting based on validation neighbors
GCN Train
SAGE
Performance
No
Val
No
Train
Val
H5
18,94 1.20
19. 19.48+0.75
22.36:20.22
11.25=1.24
20.52:2.35
24.34+0.07
Hits 10
31.2443.44
32.69=1.00
35.15+2.42
26.41+1.88
31.2843.52
37.15+2.44
Hits @
50.12+0.22
52.77=1.00
53.24:0.22
49.68+0.25
51.87+0.10
52.69+0.26
Hits @ 100
54.44+0.49
56.89=0.17
57.28+0.10
54.69=0.18
56.59+0.19
57.27+0.25
38

---

Published as a conference paper at ICLR 2024
L EXPLAINING WHY THE CURVE OF LINK PREDICTION PERFORMANCE HAS SEVERAL FAST DOWN IN FIGURE (A)
Here we delve deep into the reason why encounter several fast-down performances in Figure We ascrihe it to the weight clip We hypothesize that the loss landscape has several local minimums and hence by weight clipping with higher upper bound constraints, our learning step would be also larger so that the model could jump out of its original local optimum and keep finding some other better local optimum, which corresponds to the fast downtrend (first jump away from one local minimum and then find another better local minimum). We further empirically verify our hypothesis by visualizing the performance curve for each training process with different clipping weights in Figure 23 We can clearly see that as the clipping threshold becomes lower (upper bound decreases), we observe less fast downtrend decreases.
Tral-OC
400
al 180
Traising
spech
Traisleg-ppo spoch
speck
Clip
Clip
Clip
Clip
Figure 23: From left right, constrain GCN-based link predictor with fewer upper bounds by clipping using lower threshold. We can see the number of performance fast downtrend decreases. We hypothesize that the loss landscape has several local minimums and hence by weight clipping with lower upper bounds, our learning step would be also smaller so that the model could not jump of its origin local optimum and hence end up with fewer fast downtrends.
Following the publically available implementation on GCN/SAGE on Collab link prediction, employ the weight clip every time after parameter update
39


Reviews:
[{"review_id": "CDcOpnTfsH", "reviewer": "Reviewer_1hhc", "summary": "This paper proposes a new metric called Topological Concentration (TC) for GNN-based link prediction. The authors also discover a novel topological distribution shift issue and use TC to quantify this shift and its negative impact. They design a message-passing scheme that reweights the edges based on the contribution of the neighbors. They show that this scheme can enhance TC and boost link prediction performance to some extent.", "questions": "See Weaknesses.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper proposes a novel metric, Topological Concentration (TC), to measure the varying link prediction performance across different nodes.\n- It demonstrates the superiority of TC over other node topological properties, such as degree and subgraph density.\n- It explores the potential of boosting GNNs’ LP performance by enhancing TC via re-weighting edges in message-passing.", "weaknesses": "- The writing is unclear and hard to follow. The notations are confusing. The paper uses similar symbols for some concepts, such as ${TC}^{TR}$, ${TC}^{Tr}$, ${Tc}^{Tr}$, which are hard to distinguish. The paper also uses uncommon abbreviations for training and testing sets, such as Tr and Te.\n- The motivation of probing the node characteristic for LP is questionable. The paper does not explain why this is a meaningful problem, given that [1] has proven that LP cannot be reduced to two node problems.\n- The definition of Topological Concentration is complicated and the rationality is not obvious. The paper uses a complex formula to find the intersection of subgraphs at different hops, but does not justify its choice, such as the exponential decaying coefficients. Why don't you define $\\mathcal{H}_i^k$ as $k$-hop neighbors, which is more clear and straightforward?\n- The organization is confusing. The paper switches between different topics without clear transitions. For example, it introduces TC in section 3.2, then discusses cold-start nodes and distribution shift in section 3.3, and then returns to TC in section 3.4.\n- Obs.2 and Obs. 3 in section 3.3 seem irrelevant for the proposed model and discussion. The paper does not explain how these observations inform the design or evaluation of the edge reweighting strategy.\n- The technical novelty is limited. The paper only proposes edge reweighting as a strategy to enhance LP performance, which is a common technique in LP [2][3]. The paper does not compare or contrast its strategy with existing methods.\n- The experiment in this paper is weak. You only show the relative gain of GCN/SAGE/NCN with reweighting, but you do not compare with the SOTA LP methods like BUDDY [4]. Your result is not competitive, as you only achieve 54% Hits@50 on Collab. Why do you not include experiments on other OGB datasets like ogbl-ddi and ogbl-ppa?\n- The paper lacks ablation studies or case studies to demonstrate the effectiveness of the reweighting strategy. You could also provide some qualitative analysis or visualization to show how the reweighting strategy affects the prediction results.\n- The font in every figure is too small to read, and the figures are not well-designed.\n\n[1] Zhang, M., Li, P., Xia, Y., Wang, K., & Jin, L. (2021). Labeling trick: A theory of using graph neural networks for multi-node representation learning. In NeurIPS.\n\n[2] Huang, Z., Kosan, M., Silva, A., & Singh, A. (2023). Link Prediction without Graph Neural Networks. arXiv preprint arXiv:2305.13656.\n\n[3] Pan, L., Shi, C., & Dokmanić, I. (2022). Neural link prediction with walk pooling. In ICLR.\n\n[4] Chamberlain, B. P., Shirobokov, S., Rossi, E., Frasca, F., Markovich, T., Hammerla, N., … & Hansmire, M. (2023). Graph neural networks for link prediction with subgraph sketching. In ICLR.", "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": "xyIlnZvApl", "reviewer": "Reviewer_6TYH", "summary": "The authors identify a gap in understanding how different nodes in a graph achieve varying LP performance. They propose the Topological Concentration (TC) and its scalable version, Approximated Topological Concentration (ATC) metrics, which offer a more accurate measurement of the correlation between local subgraph structure and LP performance compared to traditional node degrees. Surprisingly, the paper reveals a counterintuitive observation that LP performance does not consistently increase with node degree, challenging conventional wisdom. Additionally, the paper uncovers a Topological Distribution Shift (TDS) issue, which impacts LP generalizability and highlights the importance of TC in understanding node-level LP performance. The authors propose TC-inspired message-passing techniques to enhance LP performance by focusing on well-connected neighbors within a node's computational tree. Overall, this research contributes valuable insights into LP performance variation and cold-start issues in GNNs, with potential implications for improving network dynamics and LP strategies.", "questions": "* Can you measure the time complexity through experiments? I guess the time consumption will not be so close to the original method.\n\n* NCN already explicitly accounts for this common neighbor signal in its decoder, the performance gains from our strategy are relatively modest. So why don't you choose another subgraph-based method because I'm curious what's your strategy's effect on subgraph-based methods that don't explicitly use common neighbor signals. \n\n* How to get the performances of link prediction of nodes with different TC? I mean one link has two nodes. For example for the results for nodes'TC in \\[0,0.2\\), does every link includes two nodes in that domain or just one node is enough?\n\n\n* Have you tried to make TC^{Tr} closer to TC^{VAL}, if wanting to make model more generalizing to prediciting test links. Because we may assume validation set has the same distribution of test set.\n* In Figure 7(a), why the curve of training original graph has several fast down of performances?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper's introduction of the Topological Concentration (TC) and Approximated Topological Concentration (ATC) metrics provides a new and innovative approach to addressing the variation in Link Prediction (LP) performance within Graph Neural Networks (GNNs). \n\n* The paper's observation that LP performance does not consistently increase with node degree challenges existing assumptions in the field. This counterintuitive finding sparks curiosity and adds an element of novelty to the research.\n\n* The paper proposed a new method to improve model's link prediction performances based on their TC and show empirical results.", "weaknesses": "* Discussion of the time complexity is not so good. The adjacent matrix are based on each layer's embedding, so the time consumption will be larger. Experiments on this are needed.\n* Subgraph-based methods as baselines are not so complete.", "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": "MecSV7NFif", "reviewer": "Reviewer_f1PG", "summary": "This paper proposes a metric \"Topological Concentration\" (TC) as a new measure for Link Prediction (LP) in GNNs.\nTP is basically the intersection of the subgraphs of extremal nodes $i$ ans $j$ of an edge $(i,j)$. A concept very similar\nto the common-neighbors heuristic. The authors claim \"With TC, newly joined neighbors of a node tend to become less \ninteractive with that node’s existing neighbors, compromising the generalizability of node embeddings for LP at the testing time\". \n\nThere is empirical evidence that GNNs perform better on high-degree nodes than on low-degree nodes. However, the authors \nobserve that this is not the case in LP. TC seems to find better correlations with LP performance (again, as common neighbors). \nTC also inspires a new message-passing strategy considering well-connected neighbors. \n\nThe authors highlight the good properties of their measure and propose how to compute it efficiently. ATC (approximated topological \nconcentration) relies on powers-hops of the transition matrix. This is $O(Kd(|E| + |V|))$, where $K$ is the maximum hop. \n\nThe experiments show that TC boosts the performance of LP in several basic baselines. No comparisons with subgraph-based baselines.", "questions": "* The ATC heavily depends on the powers of the transition matrix. In this regard, how do you fix $K$? Large values of $K$ lead to a matrix with constant rows (ergodicity theorem). \n* What are the computational advantages wrt subgraph-sketching, if any? \n* What is the expected gain in performance wrt to state-of-the-art LP methods beyond the common-neighbors heuristic?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "* Formalization of an intuition (common neighbors and subgraph-based methods for LP). \n* Nice empirical study on the properties of TC. \n* ATC is efficient.", "weaknesses": "* No comparison with state-of-the-art subgraph-based methods (e.g. subgraph sketching).", "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": "xW2cvV20U7", "reviewer": "Reviewer_QpHH", "summary": "This paper proposes a novel metric called Topological Concentration (TC) to demythify the varying performance of Graph Neural Networks (GNNs) in link prediction across different nodes. The authors demonstrate that TC has a higher correlation with link prediction performance than other node-level topological metrics like degree and subgraph density. They also uncover a novel Topological Distribution Shift (TDS) issue and propose an Approximated Topological Concentration (ATC) to address the computational complexity of TC. The paper concludes by exploring the potential of boosting link prediction performance via enhancing TC.", "questions": "- Could you please provide more details on the implementation of the Approximated Topological Concentration (ATC) and its theoretical justification for approximating TC? This would help to better understand the rationale behind the proposed method and its potential advantages over other approaches.\n\n- How do the proposed methods compare to other state-of-the-art link prediction techniques in terms of performance and computational efficiency? \n\n- What does the \"cold-start\" nodes mean? Please clarify the definition and implications of cold-start nodes in the context of link prediction. This would help to better understand the relevance and importance of addressing the cold-start problem in the proposed methods.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper introduces a new metric, Topological Concentration (TC), which provides a better characterization of node link prediction performance in GNNs than traditional metrics like degree and subgraph density.\n- The authors uncover a novel Topological Distribution Shift (TDS) issue and demonstrate its negative impact on link prediction performance at the node and graph levels.\n- The paper proposes an Approximated Topological Concentration (ATC) to address the computational complexity of TC, while maintaining high correlations to link prediction performance.\n- The authors explore the potential of boosting link prediction performance by enhancing TC through edge reweighting in message-passing and discuss its efficacy and limitations.", "weaknesses": "- The paper could benefit from a more comprehensive evaluation of the proposed methods on a wider range of datasets and benchmark tasks. This would help to establish the generalizability and robustness of the proposed techniques across different domains and problem settings.\n\n- The theoretical analysis of the relationship between TC and link prediction performance could be further strengthened with additional mathematical proofs or rigorous analysis. Providing a more solid theoretical foundation would increase the credibility and impact of the proposed methods.\n\n- The paper could discuss the limitations and potential biases of the proposed evaluation metrics, such as TC and ATC. Addressing these concerns would help to ensure that the results are reliable and that the methods are not overly sensitive to specific aspects of the data.\n\n- The paper could provide a more in-depth analysis of the cold-start problem and its relationship with the proposed metrics, as well as discuss potential strategies for addressing this issue. This would help to better understand the practical implications of the proposed methods and their potential to improve link prediction performance in real-world scenarios.", "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)