MLGLP: Multi-Scale Line-Graph Link Prediction based on Graph Neural Networks

We are truly grateful for your insightful feedback, which has played a crucial role in enhancing and refining our work. In the following, we provide comprehensive responses to address the concerns and questions you raised under Weaknesses (W) and Questions (Q).

$**(W1):**$ Thank you for your helpful feedback. To address this comment, we have carefully reviewed the paper and have corrected all the textual errors.

$**(W2):**$ Thank you for your feedback on the baselines. In the revised version, we will update the baselines to include more recent and relevant methods to better reflect the current state of the field.

$**(W3):**$ Thank you for your feedback. While the concept of converting to a line graph may appear similar to LGLP, our method, unlike LGLP, which focuses on a single scale, incorporates a multi-scale framework. This enables it to capture richer and more diverse structural information across various scales of the graph. Additionally, as highlighted in the paper, our approach outperforms existing methods like LGLP in terms of accuracy.

$**(Q1):**$ Thank you for highlighting the numerous works on link prediction in line graphs. While existing methods have contributed significantly to the field, our proposed MLGLP (Multi-Scale Line Graph Link Prediction) framework offers key distinctions:

It is a $**Multi-Scale Framework**$, Unlike traditional methods that focus on a single level of representation, MLGLP incorporates multiple scales to capture both local and global structural patterns in the line graph. This enables a more comprehensive understanding of the graph's topology, resulting in improved link prediction performance across diverse datasets.

MLGLP leverages rich structural patterns from different scales to maintain robust performance. As shown in our ablation studies, each scale contributes uniquely to the model's robustness, outperforming single-scale methods in capturing nuanced link dependencies.

$**(Q2):**$ Thank you for the suggestion regarding the inclusion of recent baselines like BUDDY, NCNC, and PEG. Thank you for your valuable feedback. In the revised version of the paper, we will certainly include a comparison of MLGLP alongside other methods such as PEG, BUDDY, and NCNC. We are confident that these additions will help validate the efficacy of MLGLP, and we will ensure these clarifications are incorporated in the revision. It is important to highlight that, as mentioned in Table 1 of the paper $**[1]**$, for $**Cora**$, the best $**AUC**$ for $**PEG**$ without using node features is $**90.78 ± 0.09**$, while for $**MLGLP**$, the AUC is $**95.79**$, as highlighted in $**Table 7**$ of the appendix. These results demonstrate the significant improvement of MLGLP over existing methods, including PEG, in terms of performance.

We chose to compare MLGLP with LGLP as a baseline for the following reasons, despite other methods being noteworthy in the field.

1. LGLP is relevant to our method as it was a leading approach in GNN-based link prediction when our work began. Both LGLP and MLGLP focus on direct edge representations using localized subgraphs, making them conceptually similar. In contrast, methods like PEG, Buddy, and NCNC rely on node embeddings for edge prediction, making them less directly comparable to MLGLP.

2. Subgraph-based methods like LGLP, MLGLP, and SEAL have the advantage of localized computation, making them more efficient during inference compared to whole-graph approaches like PEG [2]. Including methods with similar computational paradigms ensures a fair evaluation.

3.LGLP, MLGLP, and SEAL explicitly generate edge-specific embeddings, which are better suited for link prediction tasks. In contrast, PEG, Buddy, and NCNC produce node embeddings and infer edge relationships indirectly, which might limit their performance for certain edge-centric tasks.

$**(Q3):**$ Thank you for your insightful question. The overlap in the t-SNE visualizations (Figure 5) does not indicate poor performance in link prediction. t-SNE, a dimensionality reduction technique, may not always preserve local structures, leading to some overlap even when the model performs well. To address this, we added t-SNE results for LGLP and SEAL in the appendix. Further evidence of MLGLP's effectiveness is shown in the line graph link prediction task, where our method outperforms the baselines in classification accuracy and AUC, despite the overlap in the t-SNE plot. This demonstrates that MLGLP effectively distinguishes between positive and negative links in a higher-dimensional space.

REFERENCES: [1] Wang H, Yin H, Zhang M, Li P. Equivariant and stable positional encoding for more powerful graph neural networks. arXiv preprint arXiv:2203.00199. 2022. [2] Zhang, S., Liu, Y., Sun, Y., & Shah, N. Graph-less Neural Networks: Teaching Old MLPs New Tricks Via Distillation. In Proceedings of the ICLR, 2022.

We have conducted additional experiments comparing NCNC[1] with our method (MLGLP), and the results demonstrate the superiority of our method compared to NCNC. We found that NCNC is highly sensitive to node features, which affects its performance in scenarios with limited or absent node attributes. The results are as follows:

$**Comparison Results**$

$**Cora**$

• $NCNC$
  • $Node Feature$: AUC = 95.72%, AP = 95.89%
  • Random Node Feature: $**AUC = 70.78 \\% **$, $**AP = 75.16 \\% **$
  • Onehot-degree-node - Node Feature: AUC = 85.06%, AP = 88.34%
• $MLGLP$: $**AUC = 95.79\\%**$, $**AP = 96.23\\%**$

$**NSC**$

• $NCNC$
  • Random Node Feature: AUC = 59.76 %, AP = 56.87%
  • Onehot-degree-node - Node Feature: $**AUC = 95.39\\%**$, $**AP = 96.95\\%**$
• $MLGLP$: $**AUC = 99.68\\%**$, $**AP = 99.89\\%**$

$**USAir**$

• $NCNC$
  • Random Node Feature: AUC = 56.30%, AP = 53.57%
  • Onehot-degree-node - Node Feature: $**AUC = 96.88\\%**$, $**AP = 96.24\\%**$
• $MLGLP$: $**AUC = 98.31\\%**$, $**AP = 98.28\\%**$

$**Router**$

• $NCNC$
  • Random Node Feature: AUC = 72.26%, AP = 68.78%
  • Onehot-degree-node - Node Feature: $**AUC = 96.07\\%**$, $**AP = 96.26\\%**$
• $MLGLP$: $**AUC = 99.11\\%**$, $**AP = 99.20\\%**$

$**Advantages of MLGLP**$

• $**Independence from Node Features**$
• $**Inference time Efficiency**$
• $**Task-Specific Design**$

As mentioned in the NCNC paper[1], NCNC outperforms PEG and BUDDY. Therefore, I have compared our method to NCNC. We will include detailed comparisons in the camera-ready version to further illustrate these distinctions and validate our method against NCNC, PEG, and BUDDY.

We hope this clarification addresses your concerns and would greatly appreciate it if you could reevaluate our contribution in light of these new results. Thank you for your time and consideration.

Reference: [1] Wang X, Yang H, Zhang M. Neural common neighbor with completion for link prediction. arXiv preprint arXiv:2302.00890. 2023 Feb 2.

Thank you for your reply. I still have four concerns:

1. In the case of datasets with existing features, such as Cora, please explain why you still use Random Node Feature and Onehot-degree-node - Node Feature instead of just Node Feature.
2. Why don't you add Citeseer's results to the comparison in Section 5.2, but only use Citeseer in the ablation experiment?
3. In the experiment in Section 5.2, what feature creation method did you use for GNN for datasets without existing features? This is not explained in the paper.
4. In the NCNC paper, most of the datasets they used are different from the datasets you used in this paper. How do you judge that PEG and BUDDY are still inferior to NCNC in different scenarios?

We truly value your insightful feedback, which has played a crucial role in enhancing and refining our work. Below, we offer detailed responses to address the concerns you raised in the Weaknesses and Questions section.

$**(W1-Q1):**$ The performance disparity between MLGLP and LGLP in the early epochs, as observed in both training loss and AUC, can be explained by several potential factors:

$**Complexity and Feature Length:**$ The three-scale architecture in MLGLP increases the feature size (three times that of LGLP), leading to a higher-dimensional input space. While this enhances expressiveness, it can cause slower optimization in the initial epochs due to the larger number of parameters to adjust and the need for the model to learn to utilize the multi-scale features effectively.

$**Regularization and Generalization:**$ The additional multi-scale structure introduces a form of implicit regularization, which might slow early training but results in better generalization as training progresses. This delayed payoff is a trade-off, as demonstrated by the superior performance of MLGLP in later epochs and final metrics.

I would argue that while LGLP performs marginally better in early epochs, MLGLP's multi-scale design offers several compelling advantages:

$**Higher Expressiveness:**$ Multi-scale representations allow MLGLP to capture both global and local graph structures simultaneously, uncovering complex relationships that LGLP's single-scale approach cannot handle. This explains why MLGLP consistently outperforms LGLP in terms of final AUC and training loss.

$**Broader Applicability:**$ Multi-scale approaches are better suited for diverse datasets with varying structural characteristics, making MLGLP more robust and generalizable across different graph types.

$**Experimental Results:**$ Despite slower initial improvement, MLGLP achieves better final performance across all metrics (AUC, training loss). This highlights its superiority in learning richer and more accurate graph representations. While LGLP plateaus early, MLGLP continues to improve steadily throughout the training process. This suggests that MLGLP learns more meaningful representations over time, justifying its increased complexity.

$**(W2-Q2)**:$ Figure 5 presents the t-SNE visualizations for our proposed method, showcasing the results and demonstrating that the features learned by our model can be easily classified. However, we acknowledge that the figure currently lacks comparisons with state-of-the-art (SoTA) methods. To address this, we have added additional visualizations in the appendix, which compare MLGLP’s clustering results with those of SoTA methods such as LGLP and SEAL. These additional comparisons provide a more comprehensive assessment of MLGLP’s performance and ensure a fair and direct comparison with existing methods.

Thank you once again for your valuable suggestion. We will incorporate these updates in the revised paper to more effectively demonstrate the efficacy of MLGLP in relation to current approaches.

$**(W3-Q3)**:$ Thank you for your feedback. In response to your comment, we have made the necessary modifications. Specifically, we have addressed the presentation issues, including the dangling "However" above Table 3 in Section 6. We have corrected this and ensured that the text flows more smoothly and clearly.

We sincerely appreciate the time you’ve taken to review our work. We are glad that the additional information and clarifications addressed the concerns raised.

We have conducted additional experiments comparing NCNC[1] with our method, and the results demonstrate the superiority of our method compared to NCNC. The results are as follows:

$**Comparison Results**$

$**Cora dataset**$

• $NCNC$
  • $Node Feature$: AUC = 95.72%, AP = 95.89%
  • Random Node Feature: $**AUC = 70.78 \\% **$, $**AP = 75.16 \\% **$
  • Onehot-degree-node - Node Feature: AUC = 85.06%, AP = 88.34%
• $MLGLP$: $**AUC = 95.79\\%**$, $**AP = 96.23\\%**$

$**NSC dataset**$

• $NCNC$
  • Random Node Feature: AUC = 59.76 %, AP = 56.87%
  • Onehot-degree-node - Node Feature: $**AUC = 95.39\\%**$, $**AP = 96.95\\%**$
• $MLGLP$: $**AUC = 99.68\\%**$, $**AP = 99.89\\%**$

$**USAir dataset**$

• $NCNC$
  • Random Node Feature: AUC = 56.30%, AP = 53.57%
  • Onehot-degree-node - Node Feature: $**AUC = 96.88\\%**$, $**AP = 96.24\\%**$
• $MLGLP$: $**AUC = 98.31\\%**$, $**AP = 98.28\\%**$

$**Router dataset**$

• $NCNC$
  • Random Node Feature: AUC = 72.26%, AP = 68.78%
  • Onehot-degree-node - Node Feature: $**AUC = 96.07\\%**$, $**AP = 96.26\\%**$
• $MLGLP$: $**AUC = 99.11\\%**$, $**AP = 99.20\\%**$

$**Advantages of MLGLP**$

• $**Independence from Node Features:**$ MLGLP does not require node attributes, making it highly effective in featureless settings or when node features are limited
• $**Inference time Efficiency: **$ By focusing on localized subgraphs, MLGLP avoids the high latency of full-graph message passing, resulting in faster inference.
• $**Task-Specific Design:**$ MLGLP captures pairwise structural relationships through h-hop enclosing subgraphs, making it well-suited for link prediction tasks, unlike NCNC, which may miss such dependencies.

We hope that these results will contribute to the reevaluation of our work. Thank you again for your time and consideration.

Reference: [1] Wang X, Yang H, Zhang M. Neural common neighbor with completion for link prediction. arXiv preprint arXiv:2302.00890. 2023 Feb 2.

We sincerely appreciate your thoughtful feedback, which has been invaluable in refining and improving our work. Below, we provide detailed responses to address the concerns you raised in Weaknesses (W) and Questions (Q).

$**(W1)**$: All the mentioned issues are now addressed and corrected in the revised version

$**(W2)**$: We appreciate the reviewer highlighting the discrepancy in the Average Precision (AP) of GAE on the Cora dataset compared to the results reported in the original paper.

After revisiting our experiments and methodology, we would like to clarify the following points to address this concern: The observed discrepancy may stem from differences in implementation details, hyperparameter tuning, or data preprocessing. While we endeavored to align closely with the original GAE paper, minor variations in hyperparameters, preprocessing steps, or evaluation splits could have contributed to the difference in AP. To address this issue transparently and maintain credibility, we will Include additional details about our experimental setup in the final version of the paper.

$**(W3)**$: We appreciate your feedback and will enhance the time complexity analysis, as well as include training time comparisons in the revised paper.

$**(W4)**$: Thank you for your feedback. AA is a foundational baseline for link prediction, and while simple, it provides valuable comparison. We also include modern subgraph-based methods for a comprehensive evaluation.

$**(W5)**$: Thank you for pointing out the lack of ablation studies in our paper. We indeed have conducted an ablation study to compare the effect of multi-scale and line graph components $(Table 3)$. In our study, $Scale-1$ corresponds to only using a line graph component, and SEAL is used when only the first scale is applied, without the line graph transformation. We will revise the paper to include this clarification and correct the notation to reflect these details more clearly.

We appreciate your suggestion and will ensure that the revised version explicitly describes the ablation study and compares the final concatenation method to help readers better understand the contributions of each component.

$**(Q1)**$: As noted in the $\textbf {PEG[1]}$ paper, the performance of GAE is highly dependent on the input features used for training. For example, Table 1 of PEG demonstrates that the performance of VGAE (a variant of GAE) on the Cora dataset can vary significantly depending on the input features, with AP $** scores ranging from 55.68 to 89.89**$. This underscores the sensitivity of GAE-based methods to feature selection, which may lead to performance variations across different experimental setups.

$**(Q2)**$: As mentioned in $\textbf {[2]}$, GNNs face significant inference latency due to graph dependencies, scaling with $O(RL)$, where $R$ is the graph's average degree and $L$ is the number of layers.

Node-based methods like GAE and CGN have higher inference times compared to subgraph-based methods, which focus on extracted subgraphs, reducing latency.

When compared to subgraph-based methods:

• SEAL operates directly on subgraphs without line graph conversion, resulting in lower time complexity than our method.
• LGLP includes subgraph extraction and line graph conversion, sharing a similar time complexity to our approach, though ours is slightly higher due to additional processing.

However, our method achieves higher accuracy by mitigating information loss inherent in SEAL and LGLP during subgraph extraction or line graph conversion. Thus, while SEAL and LGLP are faster, our method balances slightly higher complexity with improved accuracy.

$**(Q3)**$: Thank you for the suggestion. We have conducted ablation studies to evaluate the individual contributions of the multi-scale and line graph components to the overall performance. The results are summarized in Table 3, where 'Scale-1' corresponds to the line graph component, and the other scales represent different structural levels within the multi-scale framework.

From the results, it is evident that each scale contributes uniquely to the model's performance. For instance, 'Scale-1' (line graph) demonstrates strong results on datasets like NSC and Router, achieving high AP and AUC scores. However, combining all scales ('All' method) consistently yields the best performance across most datasets, such as USAir and Celegans, confirming the effectiveness of the multi-scale approach. This highlights the importance of capturing diverse structural patterns for robust graph representation.

Reference:

[1] Wang H, Yin H, Zhang M, Li P. Equivariant and stable positional encoding for more powerful graph neural networks. arXiv preprint arXiv:2203.00199. 2022.

[2] Zhang, S., Liu, Y., Sun, Y., & Shah, N. Graph-less Neural Networks: Teaching Old MLPs New Tricks Via Distillation. In Proceedings of the International Conference on Learning Representations, 2022.

We are pleased that our response has addressed your concerns, and we deeply appreciate the time and effort you have dedicated to reviewing our work.

We have conducted additional experiments comparing NCNC[1] with our method, and the results demonstrate the superiority of our method compared to NCNC. The results are as follows:

$**Comparison Results**$

$**Cora dataset**$

• $NCNC$
  • $Node Feature$: AUC = 95.72%, AP = 95.89%
  • Random Node Feature: $**AUC = 70.78 \\% **$, $**AP = 75.16 \\% **$
  • Onehot-degree-node - Node Feature: AUC = 85.06%, AP = 88.34%
• $MLGLP$: $**AUC = 95.79\\%**$, $**AP = 96.23\\%**$

$**NSC dataset**$

• $NCNC$
  • Random Node Feature: AUC = 59.76 %, AP = 56.87%
  • Onehot-degree-node - Node Feature: $**AUC = 95.39\\%**$, $**AP = 96.95\\%**$
• $MLGLP$: $**AUC = 99.68\\%**$, $**AP = 99.89\\%**$

$**USAir dataset**$

• $NCNC$
  • Random Node Feature: AUC = 56.30%, AP = 53.57%
  • Onehot-degree-node - Node Feature: $**AUC = 96.88\\%**$, $**AP = 96.24\\%**$
• $MLGLP$: $**AUC = 98.31\\%**$, $**AP = 98.28\\%**$

$**Router dataset**$

• $NCNC$
  • Random Node Feature: AUC = 72.26%, AP = 68.78%
  • Onehot-degree-node - Node Feature: $**AUC = 96.07\\%**$, $**AP = 96.26\\%**$
• $MLGLP$: $**AUC = 99.11\\%**$, $**AP = 99.20\\%**$

$**Advantages of MLGLP**$

• $**Independence from Node Features:**$ MLGLP does not require node attributes, making it highly effective in featureless settings or when node features are limited
• $**Inference time Efficiency: **$ By focusing on localized subgraphs, MLGLP avoids the high latency of full-graph message passing, resulting in faster inference.
• $**Task-Specific Design:**$ MLGLP captures pairwise structural relationships through h-hop enclosing subgraphs, making it well-suited for link prediction tasks, unlike NCNC, which may miss such dependencies.

We hope these new experiments provide additional insight and further validate our approach, leading to a positive reevaluation of our work.

Reference: [1] Wang X, Yang H, Zhang M. Neural common neighbor with completion for link prediction. arXiv preprint arXiv:2302.00890. 2023 Feb 2.