A Topological Perspective on Demystifying GNN-Based Link Prediction Performance

=====Weakness=====

Thanks for sharing another SOTA baseline Subgraph sketch: ELPH and BUDDY, we have run their code, and here are the updated results for Table 1:

We download the most latest version of the BUDDY code and also modify it based on our reweighting strategy. We can see that equipping BUDDY with the reweighting could still enhance its link prediction performance. As running BUDDY on Citation2 cannot fit on our machine with 128 G RAM, we are currently working on getting another machine to run it. We will update the results once we have on Citation2.

As you can see, equipping our strategy achieves higher performance than SOTA LP methods such as BUDDY.

=====================

=====Question 1=====

Thank you for the question. As listed in Eq. (2), we calculate ATC in the following steps:

• Firstly, we initialize node embeddings by sampling from a d-dimensional multivariate normal distribution with zero mean

• Secondly, we perform message-passing K times, summarize the adjacency matrices from the power of 1 to K, and obtain the propagated embeddings for each node.

• Thirdly, we compute each node's embedding similarity to each neighbor and average them to calculate the ATC.

Our paper has justified the theoretical connection between ATC and TC by proving the linear relationship between TC and the mean value of ATC in Theorem 1 in Section 3.4

=====================

=====Question 3=====

We really appreciate the reviewer's observation about the definition of cold-start nodes in our paper. Following the suggestion, we conduct a systematic literature review about the definition of cold-start nodes in the context of link prediction. We first present the summary of the definition of cold-start nodes in existing literature as follows:

From the above summary, we can see that:

(1) conventional link prediction papers work on cold-start problems at the link level and define the cold-start link as the newly joined one with little or no topological information available.

(2) some node-level works such as recommender systems define the cold-start nodes/users as the newly joined ones with sparse interactions.

[1] Wang, Zhiqiang, et al. "An approach to cold-start link prediction: Establishing connections between non-topological and topological information." IEEE Transactions on Knowledge and Data Engineering 28.11 (2016): 2857-2870.

[2] Han, Xiao, et al. "Link prediction for new users in social networks." 2015 IEEE International Conference on Communications (ICC). IEEE, 2015.

[3] Yan, Ming, et al. "Friend transfer: Cold-start friend recommendation with cross-platform transfer learning of social knowledge." 2013 IEEE International Conference on Multimedia and Expo (ICME). IEEE, 2013.

[4] Xu, Linchuan, et al. "On learning mixed community-specific similarity metrics for cold-start link prediction." Proceedings of the 26th International Conference on World Wide Web Companion. 2017.

[5] Leroy, Vincent, B. Barla Cambazoglu, and Francesco Bonchi. "Cold start link prediction." Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. 2010.

[6] Ge, Liang, and Aidong Zhang. "Pseudo cold start link prediction with multiple sources in social networks." Proceedings of the 2012 SIAM International Conference on Data Mining. Society for Industrial and Applied Mathematics, 2012.

[7] Li, Yunqi, et al. "User-oriented fairness in recommendation." Proceedings of the Web Conference 2021. 2021.

[8] Rahmani, Hossein A., et al. "Experiments on generalizability of user-oriented fairness in recommender systems." Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval. 2022.

[9] Wei, Tianxin, and Jingrui He. "Comprehensive fair meta-learned recommender system." Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2022.

[10] Dong, Manqing, et al. "Mamo: Memory-augmented meta-optimization for cold-start recommendation." Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining. 2020.

[11] Hao, Bowen, et al. "Pre-training graph neural networks for cold-start users and items representation." Proceedings of the 14th ACM International Conference on Web Search and Data Mining. 2021.

[12] Wang, Hongwei, et al. "Multi-task feature learning for knowledge graph enhanced recommendation." The world wide web conference. 2019.

=====Question 3=====

=====Question 3=====

From the above summary, we can see that:

(1) conventional link prediction papers work on cold-start problems at the link level and define the cold-start link as the newly joined one with little or no topological information available.

(2) some node-level works such as recommender systems define the cold-start nodes/users as the newly joined ones with sparse interactions.

Based on the above literature review, we answer the question 3 as follows:

Following the above second paradigm, we study the cold-start link prediction at the node level since our paper targets demystifying the varying link prediction performance. Therefore, we follow some conventional literature [1-3] in that paradigm and generally deem the nodes with few degrees are cold-start ones. Concretely, in Figure 4(b)-(e), we change the degree threshold from 1 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 low-degree groups generally have higher performance than nodes in the high-degree groups.

The above observation has two promising insights compared with conventional literature:

(1) Many existing recommendation-based papers define cold-start users/nodes as the ones with few/little interactions/topological signals. However, our paper empirically justifies such a group of nodes even exhibiting higher performance in LP

We justify the above observation 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 [4].

(2) Many existing node classification papers [5-7] find nodes with low degrees have lower performance. However, our work sheds new insights on the link prediction where nodes with lower degrees actually possess higher performance.

We justify the above observation 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 to obtain the supervised signals from labeled nodes in the same class [8]. For link prediction, the ground-truth class for each node is actually its testing neighbors and hence there is no implicit biasing assumption that high-degree nodes would obtain more supervised signals.

We include the above systematical literature review with a discussion about our observation on the cold-start problem in the Appendix B.

Note that the above analysis makes another significant contribution by summarizing the cold-start definition and sheds new insights on future works addressing cold-start/sparsity issues in link prediction.

[1] Dong, Manqing, et al. "Mamo: Memory-augmented meta-optimization for cold-start recommendation." Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining. 2020.

[2] Li, Yunqi, et al. "User-oriented fairness in recommendation." Proceedings of the Web Conference 2021. 2021.

[3] Hao, Bowen, et al. "Pre-training graph neural networks for cold-start users and items representation." Proceedings of the 14th ACM International Conference on Web Search and Data Mining. 2021.

[4] Zhaok, Xiangyu, et al. "Autoemb: Automated embedding dimensionality search in streaming recommendations." 2021 IEEE International Conference on Data Mining (ICDM). IEEE, 2021.

[5] Tang, Xianfeng, et al. "Investigating and mitigating degree-related biases in graph convoltuional networks." Proceedings of the 29th ACM International Conference on Information & Knowledge Management. 2020.

[6] Liu, Zemin, Trung-Kien Nguyen, and Yuan Fang. "Tail-gnn: Tail-node graph neural networks." Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. 2021.

[7] Wang, Ruijia, et al. "Uncovering the Structural Fairness in Graph Contrastive Learning." Advances in Neural Information Processing Systems 35 (2022): 32465-32473.

[8] Chen, Deli, et al. "Topology-imbalance learning for semi-supervised node classification." Advances in Neural Information Processing Systems 34 (2021): 29885-29897.

=====Question 3=====

We have uploaded the final revised paper based on suggestions from all other reviewers and have reworded the content involving the cold-start part.

Basically, we clarify that we are mainly working on degree-related issues in link prediction, not strictly on cold-start problems. We really appreciate reviewer's sharp observation on this.

We really thank the reviewer for asking about the effectiveness and efficiency of our proposed method. Our proposed strategy is a model-agnostic strategy that can be applied to existing LP models. Therefore, we compare the link prediction performance of many existing baselines (including state-of-the-art ones) with their augmented versions by our method. We visualize their performance as follows:

We can see the performance after equipping our reweighting strategy increases for most cases.

Moreover, we compare the efficiency (in running time (s)) of the baselines before/after equipping our strategies as follows:

We can find that equipping our strategy would only marginally increase the running time. This is because we only periodically update the edge weight and when calculating the weight using the node embeddings, we directly use the cached one obtained from the message-passing during the training stage.

=====================

Dear reviewer QpHH, as today is the final day of our discussion, we appreciate the opportunity to engage with you. If you have any remaining questions or concerns, please don't hesitate to share them with us; we will be happy to respond. Thank you.

=====Question 3=====

Thanks for the question. We measure the link prediction performance of each node following existing works in recommender systems [1]. The high-level idea is for each node, we compute its pairwise link prediction score with all other nodes and rank them. Then we check the overlap of the top-K of the ranked other nodes with the top-K of the ground-truth neighbors of this node. In this way, we define Recall/Precision/F1/NDCG/MRR/Hits@K for each node and group this performance based on nodes in different TC groups. More details can be seen in Appendix B.

[1] He, Xiangnan, et al. "Lightgcn: Simplifying and powering graph convolution network for recommendation." Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval. 2020.

As another benefit, evaluating in this way avoids any sampling bias. Previously in evaluating each link prediction performance, we randomly sampled negative node pairs and compared their link prediction score with the ground one, which might suffer from bias by only sampling a tiny portion from all negative pairs, the number of which is quadratic to the total number of nodes in the network. However, our node-centric evaluation metric avoids this issue since for each node, we rank its ground-truth neighbors against all other nodes. We provide this discussion in Appendix B.

=====================

=====Question 1=====

We sincerely thank the reviewer for the sharp observation of the issue in our time complexity analysis. We first clarify this complexity analysis in two cases. The first one is the time complexity of calculating approximated topological concentration. The second one is the time complexity of applying TC-inspired reweight to the message-passing of GNNs. We discuss them in the following respectively:

For the time complexity of calculating approximated topological concentration, we:

• Firstly, we initialized each node embedding sampled from d-dimensional standard multi-normal Gaussian distribution, taking $O(|V|d)$ time
• Secondly, we perform message-passing K times, taking $O(K(|E| + |V|)d)$ time if using sparse operator [1]
• Thirdly, we summerize the propagated embeddings from $k = 1$ to $k = K$, taking $O(k|V|d)$.
• Lastly, we calculate the ATC by calculating the embedding similarity of each node to each of its neighbors, taking $O(|V|d)$.

It takes $O(K(|E| + |V|)d)$ time, which is far more efficient than the original TC computation. And we further verify it empirically in Figure 6.

For the time complexity of the TC-based edge reweighting method, we have an additional step to periodically update the edge weight based on the node embeddings obtained during the training process. However, the node embedding used for updating the edge weight can be directly borrowed from the most recent epoch as long as we cache it. Then, the only additional computation is the group-based softmax-nomralization. However, as shown in Algorithm 1 in Appendix G, we only periodically updated the edge weight; hence, the extra computational is pretty affordable.

=====================

=====Question 4=====

We thank the reviewer for the excellent suggestion and experiment by reweighting the neighbors based on their connection level to the training neighbors or the validation neighbors. We indeed find that the performance improves more if we reweight based on validation neighbors closer to the training neighbors. We put the results as follows:

In the above Table, we can see that reweighting by training edges and validation edges can both lead to higher performance. Even more, reweighting by validation edges leads to more considerable performance gain, which aligns with our expectation that the distribution of validation edges is closer to testing edges due to the shorter time interval.

=====================

=====Question2=====

Thanks for asking about the effect of our method on subgraph-based methods. Here we choose the SOTA subgraph-based one BUDDY and augment it with our proposed reweighting strategy in Appendix H. We present the updated results in Table 1:

We download the most latest version of the BUDDY code and also modify it based on our reweighting strategy. We can see that equipping BUDDY with the reweighting could still enhance its link prediction performance. As running BUDDY on Citation2 cannot fit on our machine with 128 G RAM, we are currently working on getting another machine to run it. We will update the results once we have them on Citation2. But based on the results on most of the datasets, we can still see the positive impact of our reweighting strategy on most of the datasets.

=====================

We really thank the reviewer for taking care of the efficiency of our method. We have addressed this partially from the analysis point of view in our reply to question 1 above. Here we further empirically verify the efficiency by conducting running time comparison (s) among multiple baselines as below:

We can find that equipping our reweighting strategy only induces marginal time complexity compared with its corresponding baseline. This is because, as we justified in the response above,

(1) we only update the weight for each existing edge, which is linear to the size of the graph

(2) we only periodically update rather than every epoch.

(3) we directly use the cached node embeddings rather than computing from scratch.

=====Weakness 1=====

We really appreciate the reviewer for pointing out the potential notation confusion. Since this work evaluates the link prediction performance on training/validation/testing links and also studies the distribution shift issue in node-link prediction, we need to separately denote them as Training (TR), Validation (Val), Testing (Te). These notations have also been frequently used in other works such as the following ones:

[5] Jin, Wei, et al. "Empowering Graph Representation Learning with Test-Time Graph Transformation." The Eleventh International Conference on Learning Representations. 2022.

[6] Bai Y, Chen M, Zhou P, et al. How important is the train-validation split in meta-learning?[C]//International Conference on Machine Learning. PMLR, 2021: 543-553.

=====================

=====Weakness 2=====

Thanks for sharing the insight! We do admit that LP performance cannot be reduced to two node problems and our work does not study the relation between the node characteristics and the performance of each link. Instead, our work studies the link prediction performance at the node level (see Appendix B for the difference in evaluation link prediction performance between the link level and the node level). We aim to study the relation between the local topology of each node and the link prediction performance of that node. Moreover, when we study the local topology of each node, we never reduce it to just that node nor the two nodes but instead, we study the interaction between the local topology of that node and the local topology of the neighbors of that node.

We motivate this study as follows:

(1) Real-world applications: In social networks such as Facebook and e-commerce platforms such as Amazon, we care more about the user experience of each individual user than each specific social interaction or transaction. To maintain or even improve the user experience (in link prediction problem, it is to maintain a high link prediction performance for each node), the very first thing to do is to understand which nodes might have lower LP performance (which users might have worse user experience) and further identify its rooting reason on why these nodes have lower LP performance. Understanding the latent factors influencing the node LP performance would help these platforms detect early those poor-performing users and correspondingly develop user-specific strategies to enhance their experience (LP performance). This also corresponds exactly to what we did in this paper. As shown in Figure 3, we find that node LP performance is highly correlated to its TC and our TC-based reweighting strategy could enhance nodes’ LP performance to a certain extent.

(2) Our study is also important from the perspective of fairness. Previous works [7,8] study the degree-related bias in node classification and knowledge graph completion. Only a few works [9] observe the degree-related bias in link prediction. However, they did not systematically study the underlying reason for this issue.

[7] Tang, Xianfeng, et al. "Investigating and mitigating degree-related biases in graph convolutional networks." Proceedings of the 29th ACM International Conference on Information & Knowledge Management. 2020.

[8] Shomer, Harry, et al. "Toward Degree Bias in Embedding-Based Knowledge Graph Completion." Proceedings of the ACM Web Conference 2023. 2023.

[9] Wang, Yu, and Tyler Derr. "Degree-Related Bias in Link Prediction." 2022 IEEE International Conference on Data Mining Workshops (ICDMW). IEEE, 2022.

(3) In addition, characterizing node LP performance is very important in rethinking the cold-start issue. Previously, the widely adopted notion in LP is that nodes with lower degrees have lower LP performance, and many existing works develop techniques to enhance LP performance for nodes with lower degrees in node classification. However, our work, for the very first time, breaks this conventional notion in Figure 1. The observation that low-degree nodes do not necessarily have lower link prediction performance would significantly influence future work studying cold-start issues and low-performing nodes in link prediction tasks.

=====================

=====Weakness 2=====

Moreover, we appreciate the reviewer sharing this excellent literature [1]. We have thoroughly gone through it. The claimed “two-node problem” here refers to only aggregating two-node representations directly learned by basic GNNs like GAE. We acknowledge that this would inform the problem of missing topological-relational information. However, we want to emphasize that, at any place in our work, we did not claim that we characterize the link prediction performance of each node only by itself and some other nodes. Conversely, our proposed node-level topological metric, Topological Concentration (TC), indicates the intersection between the subgraph around that node and the subgraph around the neighbors of that node, which explicitly considers the topological-relational information.

Furthermore, we want to highlight some connections between [1] and ours, which further justifies the motivation for using TC in characterizing node link prediction performance. Both works study LP tasks and investigate the underlying reason for successfully performing LP. However, [1] focuses on the performance at each node pair (link level), while ours focuses on the performance at the node level. Therefore, the labeling trick proposed in [1] captures the topological characteristics of each node pair, while our TC essentially captures the topological attributes of each node. Even more, a level of subgraph overlap between the node and its neighbors would equal the high TC of that node.

=====================

=====Weakness 4=====

Thank you for sharing your confusion. We want to highlight that the main contribution of this work is not using TC to design a better link prediction method (although we did in Section 3.5 to demonstrate the usage of TC) but to systematically study the performance discrepancy of link prediction performance across different nodes, proposing a metric to quantify it, and demonstrate the real-world importance of using this metric in studying LP. Following this line of story, we first introduce this metric, TC, in section 3.2. and then introduce the real-world importance of this metric in section 3.3 (we demonstrate its higher correlation than other metrics like degree, we demonstrate it can better identify low-performing nodes and we discover a new topological distribution shift issue using TC, all of which would inspire future research deepening our understanding of LP).

=====================

=====Weakness 3=====

Sorry for the confusion. Previous studies [1]-[2] have found that the structural features of the enclosed subgraph of the node pair are essential in determining the link prediction between that node pair. Following this same logic, we hypothesize that each node's link prediction heavily depends on the enclosed subgraph between the node and its neighbors. This exactly corresponds to the formula we propose in Eq. (1). For each neighbor of a specific node $v_j \sim \mathcal{N}_i^t$, we consider the interaction between the computational tree $\mathcal{S}_i^K$ and $\mathcal{S}_j^K$. We discussed the intuition and rationality of TC at the beginning of Section 3.2.

[1] Zhang, Muhan, and Yixin Chen. "Link prediction based on graph neural networks." Advances in neural information processing systems 31 (2018).

[2] Chamberlain, Benjamin Paul, et al. "Graph neural networks for link prediction with subgraph sketching." arXiv preprint arXiv:2209.15486 (2022).

=====================

=====Weakness 7=====

Thanks for sharing another SOTA baseline ELPH and BUDDY, we have run their code, and here are the updated results for Table 1:

We download the most latest version of the BUDDY code and also modify it based on our reweighting strategy. We can see that equipping BUDDY with the reweighting could still enhance its link prediction performance. As running BUDDY on Citation2 cannot fit on our machine with 128 G RAM, we are currently working on getting another machine to run it. We will update the results once we have them on Citation2

Moreover, our result on Collab is still competitive since different from subgraph sketching allowing validation edges used in message-passing when evaluating edges in the testing set, we strictly follow the conventional setting[1] avoiding using validation edges during testing time.

[1] Yun, Seongjun, et al. "Neo-gnns: Neighborhood overlap-aware graph neural networks for link prediction." Advances in Neural Information Processing Systems 34 (2021): 13683-13694. =====================

We really thank reviewer 1hhc for taking care of the readability of our work and we have constructed a comprehensive update to our paper throughout the discussion phase based on the suggestions from other reviewers. Now that all of them have joined the discussion, we have provided the updated version of our revised pdf file including all modifications. We apologize for not uploading a new PDF earlier, but did not want to cause confusion with multiple updates and just maintained all the changes in the comments until the end of this phase with the single updated PDF.

For the notations, we indeed admit that TC$^{\text{Tr}}$, TC$^{\text{Te}}$ are very confusion and have updated them to TC$^{\text{Train}}$ and TC$^{\text{Test}}$.

Moreover, we have increased the font size from 15 to 25 for all figure x/y tick labels. We really hope with such an larger font size, our work will be user-friendly for others to read.

Thank you for worrying about our motivation and the significance of studying the node-level link prediction problem.

We first justify why it is important to study the link prediction performance for each node as follows:

(1) Nowadays, the most important real-world application is to use link prediction to enhance user experience, e.g., social recommendation(Instagram, Twitter), video recommendation (TikTok), and e-commerce recommendation (amazon). Therefore, compared with only understanding the link prediction performance for each link, we actually care more about how different users/items (i.e., nodes) perform in the real world. Studying this problem would help us better understand what factors would affect the user experience of certain groups of users, help us early detect those potentially disadvantages groups and so can devise corresponding actions to mitigate (e.g., collect more data for those groups of users). This is even more important from the fairness perspective, e.g., how to ensure users with different interaction levels end up with equal recommendation performance.

(2) More importantly, we want to highlight that we don't try to reduce the link prediction from link problems to node problems, we are only providing a new perspective on analyzing the link prediction performance from the node perspective. For our methods, we still follow the architecture of many baselines.

(3) Also, at any time, we do not claim that nodes with higher TC would tend to form more links with other nodes. What we can derive based on the definition of TC is nodes with higher TC tend to have neighbors that are more connective with themselves (a real-world case would be nodes with higher TC may correspond to certain users who share very consistent social intentions and hence usually form relations with others who also share relations (the neighbors of the higher TC user would connection with each other by themselves). This is very intuitive in reflecting the link prediction performance of each node since if the node's neighbors have very diverse community distributions, how can we leverage its training neighbors to predict testing neighbors who may have no connections with these training neighbors?

(4) At a very high level, we want to highlight that the most contribution of our paper is not to contribute a new SOTA method (as there are already quite a lot of well-established baselines such as BUDDY or NCNC or SEAL or NeoGNN), but the analysis perspective at the node level. In addition, we break the previous conventional notion [1-2] that low-degree nodes may perform worse than high-degree nodes and also observe the topological distribution shift issue that compromises the link prediction performance (which has also been concurrently observed in [3]). We strongly believe that all of these observations would enrich future research opportunities to further boost the LP community by analyzing the data rather than designing another model (essentially the data-centric AI).

[1] Liu, Zemin, Trung-Kien Nguyen, and Yuan Fang. "On Generalized Degree Fairness in Graph Neural Networks." arXiv preprint arXiv:2302.03881 (2023).

[2] Li, Yunqi, et al. "User-oriented fairness in recommendation." Proceedings of the Web Conference 2021. 2021.

[3] Wang, Xiyuan, Haotong Yang, and Muhan Zhang. "Neural Common Neighbor with Completion for Link Prediction." arXiv preprint arXiv:2302.00890 (2023).

We sincerely hope the reviewer to reconsider the motivation, the analysis, and the contribution of our work from the analysis perspective

We extremely appreciate reviewer 1hhc for the persistent interest in helping polish and improve our work!

We have systematically read previous papers [1]-[2] and indeed admit that they employ a setting on Collab by also using validation edges and gaining even higher performance. Following this awesome suggestion, we also modify our framework by including validation edges during the message-passing (the column Collab* in the table below) and we update the results as follows:

From the above Table column Collab*, we can see even including validation edges, our reweighting method still works in boosting the performance since here we still reweight the trailing edges in the message-passing and hence capture more useful neighbors that contribute more to the TC. However, we do admit that the performance improvement caused by our reweight method is weaker when equipping on the advanced LP baselines like NCN and BUDDY. This is reasonable since our reweighting essentially captures more network topology signals by aggregating more information from training neighbors who have more topology signals (common neighbors with the whole neighbors) and these captured signals can also be captured by BUDDY or NCN since they explicitly use network structure features (sketches) in their decoder.

We really appreciate the reviewer for bringing this experiment up to further boost our work!

[1] Chamberlain, Benjamin Paul, et al. "Graph neural networks for link prediction with subgraph sketching." arXiv preprint arXiv:2209.15486 (2022).

[2] Zhang, Muhan, et al. "Labeling trick: A theory of using graph neural networks for multi-node representation learning." Advances in Neural Information Processing Systems 34 (2021): 9061-9073.

We will update the above results in our final revised paper.

Actually, we observe that simple models here such as GCN and GCN$_{\text{rw}}$ are quite poor in performance compared to NCN or BUDDY. Furthermore, their respective augmented versions nearly always provide a consistent increase in performance.

We didn't include results on ogbl-ddi/ppa because studying node-centric LP performance on these two datasets may not quite make sense since, in real-world applications, we mostly care about user experience (node-level performance) for social networks. However, for biology such as protein-protein interaction networks, we actually want to recover every potential interaction. Therefore, it is not meaningful to study the node-centric perspective as we did in our paper on these datasets.