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

Authors: Manizheh Ranjbar, Mahdi Jalili, Xiaodong Li, Parham Moradi DW
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords: link prediction, graph neural network, multi-scale graph, line graph, complex network.

Abstract:
This manuscript proposes a multi-scale link prediction approach based on Graph Neural Networks (GNNs). The proposed method - Multi-Scale Line-Graph Link Prediction (MLGLP) - learns the graph structure and extracts effective representative features of graph edges to address challenges such as information loss and handle multi-scale information. This approach utilizes embedding vectors generated by GNNs from enclosing subgraphs. While expanding GNN layers can capture more intricate relations, it often leads to overs-smoothing. To mitigate this issue, we propose constructing coarse-grained graphs at three distinct scales to uncover complex relations. To apply multi-scale subgraphs in GNNs without using pooling layers that lead to information loss, we convert each subgraph into a line-graph and reformulate the task as a node classification problem. The hierarchical structure facilitates exploration across various levels of abstraction, fostering deeper comprehension of the relationships and dependencies inherent within the graph. The proposed method is applied on link prediction problem, which can be modelled as a graph classification problem. We perform extensive experiments on several well-known benchmarks and compare the results with state-of-the-art link prediction methods. The experimental results demonstrate the superiority of our proposed model in terms of average precision and area under the curve.

Decision: reject
Reviewer scores: 5, 6, 3

Reviews and discussion:
<thread>
creation date:
1730104050764

thread_type:
official_review

<thread_object>
creator: reviewer_lufz

<content>
summary:
This paper proposed a link prediction method named Multi-Scale line-graph Link Prediction (MLGLP). MLGLP used three scales to capture information at a different level of granularity. The link prediction problem is defined as a node classification problem on a line graph, which facilitates a deeper understanding of relationships within the graph. Experiments conducted on several benchmark datasets validated the effectiveness of MLGLP.

strengths:
1. The authors use multi-scale subgraphs for link prediction to capture graph information at different granularities. The approach is interesting.
2. The authors transform the link prediction problem into a node classification problem on a line graph, which better addresses the issue of link representation.
3. The proposed method outperforms existing methods in the experiments.

weaknesses:
1. This paper appears to be an unfinished draft, containing many textual errors (e.g., the beginning of line 349 lacks capitalization, and line 372 is missing a period) and missing sentences (e.g., line 510).
2. The baselines chosen in this paper are outdated.
3. The paper lacks novelty, as the proposed module is superficial and easy to conceive. The proposed method for converting to line graph is very similar to LGLP.

questions:
1. There are many papers on link prediction in line graphs; can you explain what distinguishes MLGLP from them?
2. It's necessary to use the latest methods as baselines, such as BUDDY[1], NCNC[2], and PEG[3].
3. I have doubts about the visualization results; in Figure 5, the blue and red points seem to overlap, indicating that MLGLP cannot distinguish between positive and negative samples. An explanation is needed.

Reference:
[1] Chamberlain BP, Shirobokov S, Rossi E, Frasca F, Markovich T, Hammerla N, Bronstein MM, Hansmire M. Graph neural networks for link prediction with subgraph sketching. arXiv preprint arXiv:2209.15486. 2022 Sep 30.
[2] Wang X, Yang H, Zhang M. Neural common neighbor with completion for link prediction. arXiv preprint arXiv:2302.00890. 2023 Feb 2.
[3] 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 Mar 1.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730448850317

thread_type:
official_review

<thread_object>
creator: reviewer_soch

<content>
summary:
The paper tackles oversmoothing in Graph Neural Networks by proposing the use of coarse-grained graphs at three scales to capture complex relationships. Instead of pooling layers, the authors convert subgraphs into line-graphs and reformulate the task as node classification, enhancing the exploration of relationships. Applied to link prediction as a graph classification problem, the method shows superior performance over existing methods in terms of average precision and area under the curve in extensive benchmark tests.

strengths:
* This paper introduces Multi-Scale Line-graph Link Prediction (MLGLP), a GNN approach that learns graph structures and features from edges, tackling information loss and multi-scale challenges.
* The method constructs coarse-grained graphs at three scales to uncover complex data relationships and converts them into line graph representations, allowing for node embedding learning and reformulating link prediction as node classification.
* Experimental results show significant performance improvements over heuristics, embeddings, and various GNN link prediction methods.

weaknesses:
* The comparison of training loss and AUC among LGLP, SEAL, and MLGLP demonstrates improved loss for MLGLP relative to the baselines, yet it remains unclear why MLGLP performs weaker than LGLP in the early epochs. Further clarification on this aspect would enhance the analysis.
* Figure 5 provides valuable visual insights; however, it lacks comparisons with state-of-the-art (SoTA) methods, hindering a fair assessment of MLGLP's performance. The authors should clarify whether the identified clusters correspond to meaningful patterns and provide an experimental analysis to support this.
* There are several presentation issues that require careful proofreading. For instance, Section 6 contains a dangling "However" above Table 3 that should be addressed.

questions:
See the weakness feedback
</content>
</thread_object>

</thread>
<thread>
creation date:
1730625315943

thread_type:
official_review

<thread_object>
creator: reviewer_hdsk

<content>
summary:
This manuscript presents Multi-Scale Line-Graph Link Prediction (MLGLP), a multi-scale link prediction method using Graph Neural Networks (GNNs). MLGLP learns graph structures and extracts edge features to address information loss and capture complex relationships. By constructing coarse-grained graphs at three scales and converting subgraphs into line graphs, it reformulates the task as node classification. Extensive experiments on benchmark datasets demonstrate that MLGLP outperforms state-of-the-art link prediction methods in average precision and area under the curve.

strengths:
1. The proposed method demonstrates excellent performance, significantly improving results across various datasets.
2. The approach appears to be straightforward to follow.

weaknesses:
1. There are some notation issues; the model name is inconsistently defined throughout the paper, sometimes referred to as MLGLP, other times as MSGL or MSLGLP (as noted in the caption of Table 3), and occasionally as MSLG (in section 5.1). Additionally, the tables display varying levels of decimal precision (sometimes three decimal places, sometimes two), which should be standardized.
2. There are concerns regarding baseline comparisons. For instance, the AP of GAE on the Cora dataset should be significantly higher than that of GCN based on the original paper, yet the authors report it being lower by ten points in their experiments, which needs to be explained to maintain credibility.
3. The method involves sampling subgraphs, converting them to line graphs, and then performing node classification, which appears to result in high time complexity. Although the authors analyze time complexity, the discussion is not in-depth. They should compare it with the time complexity of two other subgraph-based methods and also include training time comparisons.
4. The baselines compared in the paper seem somewhat outdated; for example, reference [1] proposes a line graph-based method for link prediction.
5. The core innovation of this paper appears to be the application of multi-scale and line graph concepts to link prediction tasks. However, the paper lacks ablation studies on these two components, such as whether the line graph contributes to performance improvement, and it does not compare the final concatenation method. This makes it difficult to ascertain the key factors driving the model's improved performance.
[1]Zhang Z, Sun S, Ma G, et al. Line graph contrastive learning for link prediction[J]. Pattern Recognition, 2023, 140: 109537.

questions:
1. What explanation can the authors provide for the discrepancy in AP values between GAE and GCN on the Cora dataset?
2. Could the authors offer a more detailed analysis of the time complexity of their method compared to other subgraph-based approaches?
3. Can the authors conduct ablation studies to assess the individual contributions of the multi-scale and line graph components to the overall performance of the model?
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper proposes to incorporate multi-scale graph representations and transform link prediction into a node classification problem on line graphs. The core innovation, utilizing multi-scale subgraphs and line graphs for link prediction, lacks sufficient novelty. The approach is conceptually similar to existing methods such as LGLP, with incremental improvements rather than groundbreaking advancements. Besides, the choice of baselines is outdated, and the justification for omitting recent methods such as PEG, BUDDY, and NCNC is insufficient. While comparisons to NCNC were later added, they rely on indirect evaluations rather than comprehensive experimental results across shared datasets. Important datasets like Citeseer are inconsistently reported, with their results included in ablation studies but not in main comparisons. Additionally, the feature creation methods for GNNs on datasets without node features are not clearly explained, leaving critical gaps in the experimental setup. While the paper explores a promising direction and demonstrates some empirical improvements, it fails to meet the bar for originality, rigor, and clarity expected at ICLR. Strengthening the method’s theoretical contributions, providing thorough comparisons with up-to-date baselines, and significantly improving the presentation will enhance the paper’s impact in future submissions.