Link prediction is a fundamental task in network analysis, yet existing methods face two key limitations: they capture edge relationships only indirectly through node-level comparisons and are sensitive to the severe class imbalance inherent in sparse graphs. Reformulating link prediction as node classification on line graphs addresses both issues by elevating edges to first-class entities, thereby enabling direct relationship modeling. This transformation, however, can lead to quadratic growth in the number of nodes and edges, rendering naive implementations computationally infeasible at scale. To address this challenge, we propose LineML, a scalable line graph framework built on three complementary components: (i) a GraphSAGE-based architecture for multi-hop structural aggregation, (ii) an adaptive metric learning module with degree-biased negative sampling to mitigate class imbalance, and (iii) a spectral pruning strategy combined with multi-GPU training to manage computational complexity. Evaluated on 18 benchmark datasets against 14 state-of-the-art baselines, LineML achieves the best average rank on social and biological networks with strong statistical dominance (Cliff’s <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\delta \ge 0.97$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>δ</mi> <mo>≥</mo> <mn>0.97</mn> </mrow> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$p < 0.01$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>p</mi> <mo><</mo> <mn>0.01</mn> </mrow> </math></EquationSource> </InlineEquation>), along with substantial improvements on citation networks. These gains are accompanied by up to a <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$4.6\times$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>4.6</mn> <mo>×</mo> </mrow> </math></EquationSource> </InlineEquation> reduction in training time on a single GPU and up to a <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$14\times$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>14</mn> <mo>×</mo> </mrow> </math></EquationSource> </InlineEquation> speedup on a dual-GPU system.

A line graph-based metric learning framework for robust link prediction in complex networks

期刊论文
发表日期：

2026年6月19日

查看全文

Adil Imad Eddine Hosni,
Islam Baira,
Badis Djamaa,
M’hamed Mataoui,
Abdellah Hamouda Sidhoum,
Hichem Merini,
Mohamed Chakib Amrani

摘要

Link prediction is a fundamental task in network analysis, yet existing methods face two key limitations: they capture edge relationships only indirectly through node-level comparisons and are sensitive to the severe class imbalance inherent in sparse graphs. Reformulating link prediction as node classification on line graphs addresses both issues by elevating edges to first-class entities, thereby enabling direct relationship modeling. This transformation, however, can lead to quadratic growth in the number of nodes and edges, rendering naive implementations computationally infeasible at scale. To address this challenge, we propose LineML, a scalable line graph framework built on three complementary components: (i) a GraphSAGE-based architecture for multi-hop structural aggregation, (ii) an adaptive metric learning module with degree-biased negative sampling to mitigate class imbalance, and (iii) a spectral pruning strategy combined with multi-GPU training to manage computational complexity. Evaluated on 18 benchmark datasets against 14 state-of-the-art baselines, LineML achieves the best average rank on social and biological networks with strong statistical dominance (Cliff’s $\delta \ge 0.97$ $δ \geq 0.97$ , $p < 0.01$ $p < 0.01$ ), along with substantial improvements on citation networks. These gains are accompanied by up to a $4.6\times$ $4.6 \times$ reduction in training time on a single GPU and up to a $14\times$ $14 \times$ speedup on a dual-GPU system.