Revisiting Link Prediction: a data perspective

Response: We thank the reviewer for the concerns on the readability. We are also glad to see that the reviewer appreciates "our paper showing a very significant result and contribution".

For the readability issue, we worked hard to improve the writing to make the revision self-contained. The reviewer can directly see our new updated revision that is better self-contained. If you still have any concerns, please let us know immediately, and we will make sure that the paper is self-contained with clear writing. In the following part, we first summarize your questions, explain them in detail, and show our improvement in the revision. Besides, we carefully check all the appendix sections to avoid missing any important parts of the paper in the main content. If you still have any concerns about the readability, please let us know. We are eager to make sure the paper is self-contained within the 9-page limitation to meet the standard for ICLR.

Questions are summarized and retold as follows: Questions are majorly three-fold: (1) The main paper lacks some important details about parameters $r$ and $\beta$. (2) Limitation, broader impact, and future works are in Appendix G, H, and I" (3) I understand the main idea of the theoretical model and its importance in the paper, but this is not used in the experiment section of the main paper. We then provide explanations and the corresponding revision to those three questions step by step.

Question1: The main paper lacks some important details about the parameter $r$ and $\beta$.

Response1: Thanks for pointing out this issue. In the original paper, we put most detailed explanations of symbols and parameters in Section 3.2 when we first introduce the latent space model. However, we do not repeat the detailed meanings of those parameters or notify the reader where they can find the detailed explanations in each lemma and proposition. We have made the change in the modification accordingly to avoid potential confusion.

The detailed explanation of those parameters is as follows. We first clarify that all those parameters are only utilized for the theoretical analysis, corresponding to different intrinsic properties of datasets. They show no relevance in training a deep model process. Therefore, all those stuff in the theoretical analysis should be called parameters, not hyperparameters.

Detail explanation for parameter $r$ is as follows.

$r_i$ is a connecting threshold parameter corresponding to node $i$.With $\alpha = +\infty$, $\frac {1}{1+ e^ {\alpha (d_{ij}-\max\{r_{i},r_{j}\})}}=0$ if $d_{ij} > \max\{r_i, r_j\}$, otherwise it equals to $1$. Therefore, a large $r_i$ indicates node $i$ is more likely to form edges, leading to a potentially larger degree. Nodes in the graph can be associated with different $r$ values, allowing us to model graphs with various degree distributions. Such flexibility enables our theoretical model to be applicable to more real-world graphs.

The detailed discussion of parameter $r$ can be found at the beginning of Section 3.2 theoretical model.

Detail explanation for parameter $\beta$ is as follows.

Feature perspective provides complementary information, considering two nodes with high feature proximity but located distantly in the latent space should also be potentially connected. In line with this, we introduce the feature proximity parameter $\beta_{ij}$ in the latent space. A larger $\beta_{ij}$ indicates more likely for node $i$ and $j$ to be connected.

The detailed discussion of parameter $\beta$ in Section 3.2 can be found on, the 4th line of page 5, starting with (ii). Moreover, $\beta$ is a feature proximity parameter in the theoretical model which does not have a direct calculation formulation. It is just for the theoretical analysis. In the experiment part, we calculate the heuristic method, FH, corresponding to feature proximity $\beta$ for calculation. Details in the paper are shown in Section 3.1.

Our modification in the revision: We carefully check whether there is a description each time we mention each parameter. We add a simple description each time we mention the parameter and let the reader see more details in the corresponding part in section 3.2 of the main paper. The newly added content is as follows

$r_i$ is a connecting threshold parameter corresponding to node $i$ while a large $r_i$ indicates node $i$ is more likely to form edges. A more detailed description of $r$ can be found under Eq.(1). $\beta_{ij}$ is the feature proximity parameter between nodes $i$ and $j$ in the latent space while a large $\beta_{ij}$ indicates large feature proximity. A more detailed description of $\beta$ can be found in Section 3.2.

Dear reviewer cwp2, 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.

Question1: What is the role of heterophily when calculating Feature proximity? Moreover, could you give an example in the homophilic graph that FP and LSP are conflictive or FP and GSP are conflictive. I am asking this because I feel the conflict comes from the different link-forming mechanisms where FP is just not appropriate

Response: Thanks for your question about the role of heterophily when calculating feature proximity. We are not quite sure whether we exactly understand some details of your question. Therefore, we will first retell your question and answer it accordingly. If there exists any misunderstanding, please let us know, we are happy to solve all your valuable concerns and improve our paper accordingly.

Our current understanding of your question is two-fold: (1) How to describe the heterophily with the feature proximity factor? and (2) Does the conflict only happen when low FP(heterophily) but high LSP? How can the conflict happen when high FP(homophily) but low LSP? Can you show an example?

R1: Heterophily is the opposite to the well-known homophily concept in social science [1] with the principle "similarity breeds connection". More specifically, homophily indicates that nodes with larger feature similarity (high feature proximity). In contrast, heterophily indicates smaller feature similarity (small feature proximity). The ogbl-ddi dataset is the typical example where most node pairs are feature heterophilic as indicated in Figure 2.

R2: No, the conflict can also happen in the homophily case with high FP(homophily) and low LSP.

• We first clarify that there exists the case where node pairs with high FH but low LSP. The theoretical evidence and the empirical verification can be found in Lemma 2 and Figure 4, respectively. In Figure 4, we can observe that there is a large proportion of test node pairs that can be predicted correctly by heuristic-derived feature proximity (high FP) but predicted wrongly by heuristic derived local structural proximity (low LSP).
• We then explain more on why there exists the case feature-homophilic pairs that FP and LSP are conflictive. The key concept is, that link prediction is to predict the node pairs that aren't connected yet, excluding those node pairs that are already connected. When node pairs have both high FP and LSP, they are more likely to be with a link that exists already, rather than still unconnected for prediction. We are then to predict those unconnected node pairs without both high FP and LSP. In such cases, high FP or high LSP individually is strong evidence of a potential link connected. Therefore, in a homophilic graph, it is likely that the unconnected node pairs with high FP and low LSP(conflictive) have a high probability of being connected.
• We want to clarify that in the link prediction task, feature proximity and structural proximity are all important, rather than the feature proximity dominating this problem. Evidence can be found in proposition 1 and 3. The feature and structure are two perspectives that may not necessarily be aligned with each other. Similar thoughts can also be found in social network analysis[2].

[1] McPherson, M., Smith-Lovin, L., & Cook, J. M. (2001). Birds of a feather: Homophily in social networks. Annual Review of Sociology. [2] Abebe, Rediet, et al. "On the effect of triadic closure on network segregation." Proceedings of the 23rd ACM Conference on Economics and Computation. 2022.

Weakness2: I am not quite sure but I think NeurIPS D&B track and TMLR might be more appropriate venues.

Response: Thank you for suggesting alternative venues for our paper, including NeurIPS D&B track and TMLR. We appreciate and consider your suggestion according to our paper's focus and contributions. We agree that the NeurIPS D&B track and TMLR are prestigious venues with a strong focus on deep learning and machine learning research. We still believe that our paper is also well-suited for ICLR. The reason is that, despite our analysis being from a data perspective, we are not limited to empirical findings revolving on the new suitable datasets and benchmarking existing algorithms. Our paper focuses more on describing data with theoretical analyses derived from deep insight into the link prediction task.** Such understandings align with both the model perspective** (models to capture diverse pairwise data patterns, e.g., local structural patterns, the number of paths, and structural position) and the data perspective (data dominated by three factors: FP, LSP, and GSP). Our paper brings innovative understandings in the field of link prediction, a topic that aligns well with ICLR's focus on cutting-edge research in deep learning.

Dear reviewer wtEd, 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.

Weakness1: The paper introduces a latent space model for link prediction and provides theoretical guarantees for the identified data factors. Nonetheless, why using such a model is still so clear and motivated?

Response: Thanks for your great question about the motivation for the latent space model. The primary answer is that the latent space model is particularly suited for link prediction as it connects the likelihood of a link forming between two nodes to their proximity in a latent metric space. It is developed based on the most central principle in link prediction: Similarity breeds connection [6]. That is, there is a higher probability of forming a link if two nodes have similar characteristics.

The latent space model is a widely adopted theoretical model that helps design many real-world problems, especially for network analysis [1,2,3,4] and physics. Particularly, the latent space model in network analysis aims to locate network information in some latent space that can describe both local and global structures. The selected latent space can be Euclidean space [1], unit hypersphere space [5], and so on to describe different properties.

We then utilize the latent space model for link prediction, based on the important data factors, considering both feature and structure perspectives comprehensively. Each node is associated with a location in a D-dimensional latent space. The latent space for link prediction is typically utilized to describe node proximity mathematically, where nodes close in the latent space are likely to share particular characteristics. We can easily connect the distance in the latent space with the probability of forming a link. And the distance in the latent space can be approximated with different data factors. The theoretical model is utilized to mathematically formulate the graph data and link prediction task. Such mathematical description can help us conduct theoretical analysis and bring insights into the effectiveness of these data factors (Proposition 1,2,3) and the relationship between different factors (Lemma 1,2).

[1] Peter D Hoff, Adrian E Raftery, and Mark S Handcock. Latent space approaches to social network analysis. Journal of the american Statistical association, 97(460):1090–1098, 2002. [2] Sewell, Daniel K., and Yuguo Chen. "Latent space models for dynamic networks." Journal of the american statistical association 110.512 (2015): 1646-1657. [3] Smith, Anna L., Dena M. Asta, and Catherine A. Calder. "The geometry of continuous latent space models for network data." Statistical science: a review journal of the Institute of Mathematical Statistics 34.3 (2019): 428. [4] Gormley, Isobel Claire, and Thomas Brendan Murphy. "A latent space model for rank data." ICML Workshop on Statistical Network Analysis. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006. [5] Jiang, Diqiong, et al. "Sphere Face Model: A 3D morphable model with hypersphere manifold latent space using joint 2D/3D training." Computational Visual Media 9.2 (2023): 279-296. [6] McPherson, M., Smith-Lovin, L., & Cook, J. M. (2001). Birds of a feather: Homophily in social networks. Annual Review of Sociology.

Weakness2: Instead of hit metric, mrr is also very important for link prediction. It could be better if there is additional analysis on MRR

Response: We agree that MRR is also a very important metric. As such, we also add results with MRR. They are added to the revision in Appendix E: "ADDITIONAL RESULTS IN MAIN ANALYSIS". We observe that our existing conclusions are unchanged via the inclusion of MRR and in fact, are further verified.

Weakness1: The core finding of the paper is the features should also be taken into consideration.

R: Thanks for your concerns about the core findings of our paper. We want to re-clarify the contribution of our paper. Our paper does not aim to design a new deep-learning model to achieve state-of-the-art performance in link prediction (recovery). Instead, we aim to understand when link prediction algorithms work on particular graphs and when they do not, according to important factors leading to the future link formulation. To achieve this goal, we propose a theoretical latent space model to formally understand and analyze different data factors that influence GNN's performance. By identifying important data factors and how they affect the link prediction problem together, we can provide guidance for future GNN model design and dataset selection. Notably, taking features into consideration is not our core finding. We add features into consideration just to provide a more comprehensive understanding across all data factors which can easily be applied to all graphs. Moreover, our paper majorly focuses on GNN4LP models, the state-of-the-art models in link prediction, rather than node embedding methods with modest performance[4].

Our contribution is still significant in understanding link prediction on those graphs where node features are not available. In particular, we first exhibit the effectiveness of the local structural factor (proposition 1) and local structural factor (proposition 2). Then we find their underlying relationship: global structural proximity only shows effectiveness when local structural proximity is deficient in Lemma 1.

Weakness2 & Question: Is the proposed latent space different from a node embedding, and if so, why? What is the difference between the latent space from the node embedding? Can you make a comparison between the latent space model and node embedding models since the latent space model and node embedding models utilize latent space and embedding, respectively, for link recovery?

Response: Thanks for your great question about the connection between node embedding models and latent space models. Our primary answer is that they can not be directly compared as the latent space model is a theoretical model while the node embedding model is a concrete graph learning algorithm.

On the one hand, node embedding model is a concrete graph learning algorithm, similar to GNN4LP models. Node embedding models aim to learn node embedding to preserve important data properties for link prediction. Nonetheless, they are not the SOTA since GNN4LP can perform much better[4]. That is the reason why we focus on GNN4LP models. On the other hand, the latent space model is a theoretical model, which helps us understand the important data factors for the link prediction task and how different link prediction algorithms work. Hence, indeed, the latent space model can be used to understand the graph embedding algorithms as well as GNNs discussed in our paper. The theoretical latent space model cannot be directly applied and learned from data to achieve satisfying performance. It serves to better understand those algorithms applied for future collection. More details on the above explanations are as follows.

Dear reviewer zuoh, 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.