Pure Message Passing Can Estimate Common Neighbor for Link Prediction

We first want to appreciate the reviewer's extensive feedback, which is extremely valuable to us given the large volume of review loads this year. We also very appreciate the reviewer's positive feedback on the importance of the problem we address, especially acknowledging the importance of trade-off between expressivity and efficiency for link prediction tasks. We will address the following points in the rebuttal:

W1: Comparison with ELPH/BUDDY

Due to the space limit, we post this rebuttal as the "global" rebuttal on the very top of the page. Please refer to the global rebuttal for the detailed response.

W1 (cont.) Issues about Appendix F.1

We apologize for the any confusion in Appendix F.1. In Appendix F.1, we find that ELPH's MinHash/HyperLogLog can introduce a high variance of estimation compared to MPLP. We address the reviewer's concerns as follows:

For example, is it on all test samples? Positive and negative?

We report the estimation quality on a set of both positive and negative edges. For positive edges, we use all the training edges. For negative edges, we randomly sample the same number of negative edges as the positive edges. We keep the edges consistent across MPLP and ELPH to ensure a fair comparison.

In MPLP, we use the shortcut removal technique to avoid the distribution shift problem. For a more fair comparison, we also implement the shortcut removal technique for ELPH in Appendix F.1. We will clarify this in the revised version.

the authors don't specify the # of hops used when estimating the counts for ELPH/BUDDY.

For ELPH, we use the node signatures of 2-hop neighbors to get estimations for #(1,1), #(1,0), #(1,2), #(2,2) and #(2,0). Since the estimation variance becomes higher for both MPLP and ELPH at the #(2,2) and #(2,0), we did not report the variance beyond 2-hop neighbors. It is very interesting to learn from the reviewer that setting hops=3 can help improve the performance, where we thought that the variance would be too high to be useful. In our experiments, the performance gain from 3-hop neighbors of MPLP(+) is marginal.

Most importantly, the authors only compare to MPLP and not MPLP+

MPLP+ is different from MPLP/ELPH/BUDDY in that MPLP+ estimates the number of walks between two nodes rather than the number of nodes like MPLP/ELPH/BUDDY. Therefore, to have an apple-to-apple comparison, we can only compare MPLP to ELPH in Appendix F.1 to evaluate the quality of estimating number of nodes.

W2

We apologize for any confusion about the efficiency of MPLP+. MPLP+ is similar to BUDDY and can also cache the node signature during the inference time. In Appendix D.3, we discuss the detail of benchmarking the inference time for both BUDDY and MPLP+.

While theoretically, MPLP+ and BUDDY should have similar efficiency. However, the implementation of two methods causes the efficiency discrepancy. For MPLP(+), we utilize pytorch_sparse to implement the message-passing, which is built on [3]. BUDDY utilizes pytorch_scatter to implement its message-passing, which is both slower and more memory-hungry compared to the sparse-dense matrix (Spmm) opeartion in MPLP(+).

In fact, we also submit a Pull Request in BUDDY's Github repo to change its message-passing implementation to Spmm. Even though BUDDY with Spmm shows comparable efficency as MPLP+, it still exhibits higher estimation variance (Appendix F.1.) and lower overall performance (Table 1/2) compared to MPLP(+).

[3] Design Principles for Sparse Matrix Multiplication on the GPU.

W3

Thank you for pointing this out. We discuss in the paper that our link prediction framework shares a similar spirit of learning structural representation as ELPH/BUDDY. However, beyond ELPH/BUDDY, MPLP(+) proposes several distinct components (Shortcut Removal, Norm Scaling, One-hot hubs, walk-based counting) that significantly boost the model performance with a totally different but simple node/walk-estimation mechanism (quasi-orthogonal vectors).

W4

We appreciate the reviewer's constructive suggestion. We do not include the Cora/Citeseer/Pubmed in our main experiment because recent studies[4,5] and we find that these three datasets overwhelmingly rely on the node attributes for link prediction tasks. An MLP without graph structural information can already achieve comparable performance as GNNs on these three datasets. This makes them not sensitive enough between different link prediction methods.

For HeaRT setting, we will report the results on all datasets in a revised version.

[4] Linkless Link Prediction via Relational Distillation

[5] Evaluating Graph Neural Networks for Link Prediction: Current Pitfalls and New Benchmarking

Q1

Please refer to rebuttal for W1 (cont.) Issues about Appendix F.1.

Q2

Please refer to rebuttal for W2.

Q3

Please refer to rebuttal for W1.

Q4

We thank the reviewer for the suggestion. We will include BUDDY's results into the main tables to make it more clear.

---

Thanks again for your comments and diligence in reviewing our work. We hope our responses have addressed your concerns. If so, we hope that you will consider raising your score. If there are any notable points unaddressed, please let us know and we will be happy to respond.

Proof Sketch for MPLP's Expressiveness over NCN:

We present a proof sketch to show that MPLP is more expressive than NCN, specifically because MPLP can enable weighted node counting by Norm Scaling technique (Sec 4.1). Consider a $n_1 \times n_1$ rook's graph and a $n_2 \times n_2$ rook's graph, where $n_1 \neq n_2$. These two graphs are strongly regular graphs, but with different node degrees. Also any non-adjacent nodes in rook's graph will have two common neighbors. We investigate if NCN/MPLP can encode the non-adjacent node pair in $n_1 \times n_1$ rook's graph differently from the non-adjacent node pair in $n_2 \times n_2$ rook's graph.

For NCN, (1) the GNN encoder (GCN/SAGE) will generate the same representation for all nodes due to regular graphs; (2) all the non-adjacent node pairs will have two common neighbors, leading to the same NCN score.

For MPLP, because $n_1 \neq n_2$, the Norm Scaling technique will assign different norms to the quasi-orthogonal vectors of nodes in $n_1 \times n_1$ and $n_2 \times n_2$ rook's graphs. Therefore, the non-adjacent node pairs in $n_1 \times n_1$ and $n_2 \times n_2$ rook's graphs will have different MPLP representation due to the weighted node counting. This shows that MPLP is more expressive than NCN.

We appreciate the reviewer's feedback. We address the following points in your feedback:

Empirical advantages of MPLP+'s Norm Scaling and Shortcut Removal. Q2

We thank the reviewer for the insightful comments. In our previous response, we have discussed the theoretical advantages of Norm Scaling and Shortcut Removal. The ablation study in Table 7/8 shows that these two techniques can effectively boost the MPLP's performance, depending on the dataset. We also show in Appendix F.1 that MPLP(+) has better estimation accuracy compared to ELPH/BUDDY.

Here, we further investigate the empirical advantages of Norm Scaling and Shortcut Removal in MPLP+ especially on PPA and Citation2 dataset. We keep all the other hyperparameters the same as the main experiments, and only remove Norm Scaling for PPA and Shortcut Removal for Citation2. The results are shown in the table below:

As shown in the table, the performance of MPLP+ drops significantly when removing Norm Scaling on PPA. This indicates that Norm Scaling is crucial for capturing the nuanced structural information in the PPA dataset and the driving factor boosting the performance of MPLP+. On the other hand, the performance of MPLP+ decreases when removing Shortcut Removal on Citation2. This suggests that Shortcut Removal is essential for avoiding the distribution shift problem in the Citation2 dataset. Interestingly, the degenerated performance of MPLP+ is close to BUDDY when removing Norm Scaling on PPA and Shortcut Removal on Citation2. This empirically demonstrates that Norm Scaling and Shortcut Removal are effective techniques for improving the performance of MPLP+ over BUDDY.

Since NCN uses the common neighbors' node representation as link representation, it is not directly comparable to MPLP(+). Therefore, it is difficult to conclude that Norm Scaling and Shortcut Removal are not effective for MPLP(+) because NCN cannot exploit the node degree information and shortcut removal technique. We will include this empirical analysis in the revised version.

In fact, MPLP+ with Norm Scaling can be more expressive than NCN. We include a proof sketch in the end of the response.

The more expressive MPLP can face more severe distribution shift problems than NCN (Sec 5.3.2 in [2]). Therefore, the Shortcut Removal technique is more crucial for MPLP to avoid the distribution shift problem compared to NCN.

[2] FakeEdge: Alleviate Dataset Shift in Link Prediction

Other concerns

We greatly appreciate the reviewer's suggestions. We will revise the paper to more explicitly indicate the walk-based counting mechanism of MPLP+ and the reference of the proposed techniques of MPLP(+). We will also include a discussion when comparing the efficiency results between BUDDY and MPLP.

Q1: Estimation quality of MPLP+

We thank the reviewer for the suggestion. Similar to experiments in Appendix F.1, we include the experimental results for the walk estimation quality of MPLP+ on Collab below:

Since there is no other baseline counting walk on graph, we can only investigate the results by itself. As shown in the table, the walk estimation quality of MPLP+ becomes worse when hops increase. This is because with longer hops, the number of walks between two nodes increases exponentially, leading to a higher estimation variance. When it comes to the #(2,2), the estimation variance becomes too high to be useful. Therefore, we observe that the performance gain from 3-hop above neighbors of MPLP(+) is marginal. In the meantime, increasing the signature dimension $F$ can help reduce the estimation variance. We will include this analysis in the revised version.

---

We hope that we have addressed your concerns. Please let us know if there are any other concerns. We will be happy to respond.

Thanks for the detailed response. I list my further comments below.

| However, BUDDY cannot perform a weighted counting due to the mechanism of MinHash and HyperLogLog.

I agree with this in relation to BUDDY. But I'm skeptical that this is actually important. Of course RA/AA do better than just CN, but let's consider NCN. It doesn't consider the degree of the CNs and does very well. Of course one can argue that maybe the degree information get's encoded in the node representations in NCN but we don't really know since it's not explicit in any way. So I'm technically not disagreeing with your claim, but I'm unsure if the proof really exists to claim that this matters.

| ELPH/BUDDY can cause a distribution shift problem, while MPLP will not

I agree in theory, but in practice recent work has shown that the effect of this distribution shift is quite minimal. NCN/NCNC also removes the link during training. On the OGB datasets, their studies show the effect is minimal, at best (Note: The results are only in an older version of the paper here in Table 3 under NoTLR). Also [1] below studies the problem and conclude that it really only effects nodes of lower degree. They show that the overall performance on ogbl-collab and ogbl-citation2 is barely changed when removing target links.

So again, I'm not disagreeing with you and I agree that this is a plus for MPLP/MPLP+. I'm just skeptical that it matters a lot in practice.

[1] Zhu, Jing, et al. "Pitfalls in link prediction with graph neural networks: Understanding the impact of target-link inclusion & better practices." Proceedings of the 17th ACM International Conference on Web Search and Data Mining. 2024.

| In our experiments, the performance gain from 3-hop neighbors of MPLP(+) is marginal.

Interesting. It's likely dataset dependent.

| While theoretically, MPLP+ and BUDDY should have similar efficiency. However, the implementation of two methods causes the efficiency discrepancy.

Ok, that makes sense. Please include a discussion of this when showing the efficiency results in the paper. As the current results are misleading.

| We do not include the Cora/Citeseer/Pubmed in our main experiment because recent studies[4,5] and we find that these three datasets overwhelmingly rely on the node attributes for link prediction tasks.

Ok, that's fair.

| However, beyond ELPH/BUDDY, MPLP(+) proposes several distinct components (Shortcut Removal, Norm Scaling, One-hot hubs, walk-based counting)

I thank the reviewers for the clarification.

However, I'm not disagreeing that the mechanism for estimating nodes/walk counts is different. That is a notable achievement. My point was regarding, as you mentioned, the "spirit" of the method being quite similar. That is still true. Furthermore, some of the components mentioned such as shortcut removal aren't proposed by this paper. In fact, it's used by multiple link prediction methods. This is also true for norm scaling where the authors explicitly refer to [12, 25] in their paper (line 246). To be clear, this isn't a bad thing, but I think the authors should be clear in their paper about what specifically they propose that's novel.

| MPLP+ estimates the number of walks between two nodes

Thanks for the clarification. I recommend the authors make this a little more explicit in their paper, as when introducing MPLP+ it's only mentioned briefly on line 294.

Furthermore, in my opinion, the fact that MPLP+ uses walk-based features raises 2 more questions:

Q1: How well does it estimate walk of disparate lengths? I recommend the authors try to incorporate this into future versions of their paper. Because as of now, we really don't know how well it actually estimates the walks. This matters because it will give us some understanding on whether estimating these counts is actually important and driving the performance gain.

Q2: It doesn't explain to me why MPLP+ can perform so well. In general, MPLP+ tends to do slightly worse than MPLP across almost all datasets. Naively, this would suggest that if it were computationally feasible to run on ogbl-ppa, it would also do very well ~65 Hits@100. But this would still be much much higher than the performance of BUDDY on ogbl-ppa which is ~49. A similar observation stands for ogbl-citation2. I know this is hypothetical as the results don't exist, but I would find it hard to believe that estimating the node counts slightly better would lead to such a huge increase. Also, we don't really have any reason to expect that using walks in MPLP+ would help on the OGBs. In [33] they show that Katz (which just weights these walks) always does same/worse than RA/AA. So that likely can't explain it either for just MPLP+.

Basically, as I mentioned in my original review, I don't really understand why MPLP/MPLP+ does so well, especially compared to BUDDY. Because of that I'll keep my score.

We first want to express our gratitude for the reviewer's comment that the reviewer "enjoyed reading this work". For us, it is the most rewarding feedback to know that our work is well-received. We will address the following points in the rebuttal:

Q1

The weight matrix $W$ in theorem 3.1 does not have any specific role for holding the theorem. We just keep it here because the standard GCN/SAGE formulation has the weight matrix. If we remove the weight matrix $W$, the entire theorem will still hold, except that the constant $C$ will be different as $C = \sigma^2_{node}F$. In other words, the untrained zero-mean-initialized weight matrix $W \in \mathbb{R}^{F^{\prime} \times F}$ will only introduce a scaling factor to the expectation of the inner product.

Q2

We appreciate the reviewer's suggestion. Generally, it is challenging to provide a fair evaluation of training times for different methods due to variations in learning rates, batch sizes, and early stopping criteria. Since the size of trainable parameters in GNNs is relatively small compared to other deep learning models, training time is usually not a bottleneck. Most of the computational cost in GNNs comes from processing the graph structure (See Table 1 in [7]), such as message passing[1,2] or the labeling trick[3] for link prediction. Therefore, inference time can be used as a proxy for the computational cost of training models. In the Figure 4 of experimental section, MPLP is shown to be more efficient than other methods in terms of inference time, indirectly indicating that MPLP is more computationally efficient than other methods.

Q3

We thank the reviewer for the suggestion. We follow the evaluation protocol of previous works[4,5] to ensure a fair comparison. While we acknowledge that other metrics like AUC-ROC and AUC-PR are important for evaluating link prediction tasks, recent studies[6] have shown that performance evaluated by AUC-ROC and AUC-PR is nearly saturated for most methods. Therefore, we focus on the evaluation of MRR and Hits@K, which are more sensitive to the performance differences between methods.

[1] SIGN: Scalable Inception Graph Neural Networks

[2] Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks

[3] Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning.

[4] Open Graph Benchmark: Datasets for Machine Learning on Graphs

[5] Graph Neural Networks for Link Prediction with Subgraph Sketching

[6] Neural Link Prediction with Walk Pooling

[7] MLPInit: Embarrassingly Simple GNN Training Acceleration with MLP Initialization

---

We hope that we have addressed your concerns. If we have left any notable points of concern unaddressed, please let us know, and we will be happy to respond.

We thank the reviewer for the feedback. We will address the following points in the rebuttal:

W1

We apologize for any confusion regarding MPLP. MPLP aims to count the number of nodes at varying distances from a target node pair. Compared to pre-computed heuristics like Common Neighbor, MPLP is significantly more efficient in terms of both time and space complexity. In a graph with $N$ nodes, pre-computed common neighbors require $O(N^2)$ space to store all pairwise information, whereas MPLP only requires linear space $O(NF)$, where $F \ll N$ represents the node signature dimension. Regarding time complexity, MPLP can be seen as an approximation of the labeling trick[2], trading off variance for efficiency. Generally, MPLP is more scalable for large-scale graphs.

Unlike NCN[1], MPLP considers not only the common neighbors but also the nodes beyond the 1-hop neighborhood. This makes MPLP more expressive and powerful in capturing structural representation than NCN. The experimental results in our paper demonstrate the effectiveness of MPLP in link prediction tasks.

W2

We appreciate the reviewer's suggestion. In fact, our quasi-orthogonal (QO) vectors are used to build a link structural representation rather than positional encoding [5]. There are distinct differences between position encoding and our QO vectors:

1. Unlike typical position encodings[3,4] designed for graph-level tasks, our QO vectors are specifically targeted for link prediction tasks. Position encodings represent the relative position of each node in the graph, whereas our QO vectors cannot represent individual node positions but can be decoded to represent pairwise structural representation for link prediction tasks.

2. When applying position encodings to link prediction tasks, most of them are limited to transductive settings. This is because position encodings represent node position within a specific graph. If graph changes, the position encodings should also change. However, our QO vectors can be decoded as a structural representation and applied in both transductive and inductive settings.

We will add a detailed comparison between QO vectors and position encodings in the revised version.

W3

We apologize for any confusion regarding the scalability of MPLP. MPLP is designed to have greater scalability for large-scale graphs compared to methods like labeling tricks[2]. Each node is assigned a random quasi-orthogonal vector of dimension $F \ll N$. These vectors do not need to be strictly orthogonal but should be orthogonal in expectation. Therefore, MPLP is scalable for large-scale graphs.

[1] Neural Common Neighbor with Completion for Link Prediction.

[2] Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning.

[3] Graph Inductive Biases in Transformers without Message Passing.

[4] Rethinking the Expressive Power of GNNs via Graph Biconnectivity.

[5] On the Equivalence between Positional Node Embeddings and Structural Graph Representations.

---

We hope that we have addressed your concerns, and that you will consider raising your score. If we have left any notable points of concern unaddressed, please let us know, and we will be happy to respond.

Thanks for your response. Unfortunately, my concerns about Weaknesses 1,2,3 remain unaddressed. The questions are as follows.

1. The authors claim that MPLP is more expressive and powerful than NCN, but I can not find the corresponding theoretical analysis.
2. The shortest path distance is a pairwise structural representation (heuristic metrics), as shown in NBFNet [6]. [3] shows that relative random walk probabilities (RRWP) can express the shortest path distance. Moreover, Resistance Distance encodings [4] are similar in my opinion. Moreover, the discussion with Laplace position encodings (LapPE) [7]---which are also orthogonal---is missing.
3. The graph-level classification is inductive. They first train GNNs on the training set of graphs and then infer on the test set of unseen graphs. Why are the position encodings limited to transductive settings?
4. If the random quasi-orthogonal vectors have dimension $F<<N$, then their expectations also have dimension $F<<N$. So why are they orthogonal in expectation? Can you provide the theoretical analysis or reference to prove that "these vectors do not need to be strictly orthogonal but should be orthogonal in expectation"?

[6] Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction. [7] Rethinking graph transformers with spectral attention.

We thank the reviewer for the feedback on our rebuttal. We address the following points in your feedback:

Concern 1

We show that MPLP is more expressive and powerful than NCN:

Expressiveness: We present a proof sketch to show that MPLP is more expressive than NCN, specifically because MPLP can enable weighted node counting by Norm Scaling technique (Sec 4.1). Consider a $n_1 \times n_1$ rook's graph and a $n_2 \times n_2$ rook's graph, where $n_1 \neq n_2$. These two graphs are strongly regular graphs, but with different node degrees. Also any non-adjacent nodes in rook's graph will have two common neighbors. We investigate if NCN/MPLP can encode the non-adjacent node pair in $n_1 \times n_1$ rook's graph differently from the non-adjacent node pair in $n_2 \times n_2$ rook's graph.

For NCN, (1) the GNN encoder (GCN/SAGE) will generate the same representation for all nodes due to regular graphs; (2) all the non-adjacent node pairs will have two common neighbors, leading to the same NCN score.

For MPLP, because $n_1 \neq n_2$, the Norm Scaling technique will assign different norms to the quasi-orthogonal vectors of nodes in $n_1 \times n_1$ and $n_2 \times n_2$ rook's graphs. Therefore, the non-adjacent node pairs in $n_1 \times n_1$ and $n_2 \times n_2$ rook's graphs will have different MPLP representation due to the weighted node counting. This shows that MPLP is more expressive than NCN.

powerful: In Table 1/2, we empirically show that MPLP(+) can achieve better performance than NCN on various datasets, which demonstrates the effectiveness of MPLP for link prediction tasks.

We thank the reviewer for pointing this out. We will include the proof in the revised version.

Concern 2

We thank the reviewer for the suggestion. RRWP, Resistance Distance encodings, and LapPE can all provide a pairwise structural representation, especially the distance information. Even though they are used for graph classification tasks, we also believe that there can be a connection between these encodings and link prediction tasks. This can be an interesting direction for future work. We will add a discussion on the connection between RRWP/Resistance Distance/LapPE and MPLP in the revised version, detailing how these positional encodings can also be decoded to provide pairwise structural representation, similar to MPLP, and potentially be used for link prediction tasks. For LapPE, we will also cover that it is derived from the orthogonal eigenvecotrs of the Laplacian matrix, while MPLP's quasi-orthogonal vectors are randomly initialized.

Concern 3

We apologize for any confusion regarding the inductive ability of positional encodings. Previously, we referred the positional encodings specifically to the one formally defined in [5]. However, the positional encodings, like RRWP/Resistance Distance/LapPE, contains both the positional information and the structural information (this is also discussed in Sec 2 of [3]). We will clarify this when discussing the connection between RRWP/Resistance Distance/LapPE and MPLP in the revised version.

[5] On the Equivalence between Positional Node Embeddings and Structural Graph Representations.

Concern 4

We apologize for the confusion regarding the orthogonality of the vectors. Consider two vectors $v_1$ and $v_2$ independently sampled from a standard normal distribution. The inner product of these two vectors $v_1^Tv_2$ is likely to be zero but not always. However, the expected value of the inner product is $E[v_1^Tv_2] = E[v_1]^TE[v_2] = 0$, which means that the vectors are orthogonal in expectation due to the independence of the vectors. This is why we refer to the vectors as quasi-orthogonal such that they are orthogonal from the probabilistic perspective. We will clarify this in the revised version.

---

We hope that we have addressed your concerns. If we have left any notable points of concern unaddressed, please let us know, and we will be happy to respond.