PaperlayerView exact revision on arXiv

Source-linked AI summary

Line Graph Neural Networks for Link Prediction

Lei Cai, Jundong Li, Jie Wang, Shuiwang Ji

arXiv:2010.10046v1cs.LG

TL;DR

Existing link prediction methods often classify pooled enclosing subgraphs, risking information loss. The paper instead transforms the original graph into a line graph, where edges become nodes and target-link features are learned directly. Across 14 datasets, the method consistently outperforms state-of-the-art baselines with fewer parameters and faster training.

  • Problem

    Link prediction methods commonly use graph pooling to obtain fixed-size features from enclosing subgraphs, which can incur information loss.

  • Method

    The method transforms the original graph into a line graph and solves link prediction as node classification using graph neural networks without pooling.

  • Results

    Across 14 datasets, the proposed method consistently outperforms baseline methods, including state-of-the-art models, while converging faster and using fewer parameters.

  • Takeaways & Limitations

    Learning target-link features directly in line-graph space provides an efficient alternative to pooled graph-classification approaches.

Abstract

from arXiv · show

We consider the graph link prediction task, which is a classic graph analytical problem with many real-world applications. With the advances of deep learning, current link prediction methods commonly compute features from subgraphs centered at two neighboring nodes and use the features to predict the label of the link between these two nodes. In this formalism, a link prediction problem is converted to a graph classification task. In order to extract fixed-size features for classification, graph pooling layers are necessary in the deep learning model, thereby incurring information loss. To overcome this key limitation, we propose to seek a radically different and novel path by making use of the line graphs in graph theory. In particular, each node in a line graph corresponds to a unique edge in the original graph. Therefore, link prediction problems in the original graph can be equivalently solved as a node classification problem in its corresponding line graph, instead of a graph classification task. Experimental results on fourteen datasets from different applications demonstrate that our proposed method consistently outperforms the state-of-the-art methods, while it has fewer parameters and high training efficiency.

I. RELATED WORK

Link prediction methods include heuristic, embedding, and deep learning approaches. Heuristics are manually designed and may not transfer across networks, while embedding methods can be affected by graph sparsity; deep learning learns link distributions automatically.

  • Link prediction models are grouped into heuristic, embedding, and deep learning methods.
  • Heuristic Methods: Heuristic methods compute similarity from target-node neighborhoods using first-, second-, or higher-order information.
  • Embedding Methods: Embedding methods learn node features from graph topology, but their performance can be affected when graphs become very sparse.
  • Deep Learning: Deep learning methods learn link distributions automatically, with SEAL converting link prediction into graph classification on enclosing subgraphs.

A. Problem Formulation

Link prediction seeks to identify potential or missing links in an undirected graph from its existing vertices, edges, or adjacency matrix.

  • Given an undirected graph G = (V, E), link prediction estimates potential or missing links that may appear in the foreseeable future.

B. Overall Framework

Deep learning link prediction typically extracts and labels an enclosing subgraph around two target nodes, then learns features from it to classify whether their link exists.

  • Enclosing subgraph extraction: An h-hop enclosing subgraph centered on two target nodes balances computation cost and prediction performance.
  • Node labeling: Node labeling identifies target nodes and marks the structural importance of other nodes before feature learning.
  • Feature learning and link prediction: Graph neural networks learn features from the labeled enclosing subgraph and use them to predict whether the target link exists.

C. Line Graph Neural Networks

The proposed line graph neural network transforms an enclosing subgraph so original edges become line-graph nodes, allowing target-link features to be learned directly without pooling. This converts link prediction into node classification while preserving edge information and maintaining efficient computation.

  • Line Graph Space Transformation: The enclosing-subgraph representation avoids fixed-size pooling, which otherwise loses information when subgraphs contain different numbers of nodes.
  • Line Graph Space Transformation: Line graph transformation represents adjacencies between original-graph edges, with each original edge becoming a line-graph node.
  • Line Graph Space Transformation: For a graph with n edges, its line graph has n nodes; conversion from G to L(G) has linear time complexity.
  • Node Label Transformation: For undirected graphs, edge attributes concatenate the minimum and maximum endpoint labels, making them invariant to endpoint order.
  • Node Label Transformation: In attributed graphs, endpoint node attributes are summed and combined with labels before serving as line-graph node attributes.
  • Feature Learning by Graph Neural Networks: Graph convolution learns each line-graph node embedding by aggregating one-hop line-graph neighbors, corresponding to two-hop information in the original graph.

D. The Proposed Algorithm

The proposed algorithm extracts a labeled enclosing subgraph, transforms it into a line graph, and applies graph neural networks to predict the target link.

  • Framework: The framework’s three components are not strictly restricted and can work well for most networks.The described components are enclosing-subgraph extraction, graph-topology labeling, and neural feature learning.
  • Enclosing Subgraph Extraction: The model extracts an h-hop enclosing subgraph around the target link before feature learning.A 2-hop enclosing subgraph is used to balance topology information and computation cost.
  • Node Labeling: A node-labeling function identifies the target nodes and encodes each node’s structural importance relative to them.The two target nodes receive label 1, disconnected nodes receive label 0, and other labels depend on shortest-path distances.
  • Line Graph Transformation: The enclosing subgraph is transformed into a line graph so graph neural networks can learn node embeddings for the target link.The algorithm generates edge attributes, constructs L(G_h), applies graph neural networks, and predicts link existence.

III. EXPERIMENTS

The experiments evaluate the proposed link-prediction method across 14 datasets using AUC and average precision as performance metrics.

  • Evaluation: The study evaluates the proposed method on 14 datasets using area under the curve and average precision.The code and datasets are stated to be released after publication.

A. Datatsets and Baseline Models

The experiments cover 14 datasets from six areas and compare the proposed model with heuristic, graph-embedding, and state-of-the-art baselines.

  • Datasets: The evaluation uses 14 datasets collected from six application areas and spanning different graph scales.Dataset details include node counts, link counts, average node degree, and graph type.
  • Baseline Models: The baselines include Katz, PageRank, SimRank, node2vec, and the state-of-the-art SEAL model.The first three are high-order heuristic methods, while node2vec is a graph-embedding method.

B. Experimental Setup

The setup varies the proportion of training links, tunes baseline parameters, and uses a matched neural architecture to compare the proposed method with SEAL.

  • Data Splits: The experiments use either 50% or 80% of existing links for positive training samples, with equal numbers of nonexistent links as negatives.Remaining existing links serve as positive test samples.
  • Baseline Configuration: Baseline parameters are tuned for best dataset performance, including fixed damping factors for Katz, PageRank, and SimRank.Node2vec uses 128-dimensional node embeddings.
  • SEAL Configuration: SEAL uses three graph convolution layers, sort pooling, one-dimensional convolutions, and fully connected classifier layers.The SEAL model is trained for 50 epochs on each dataset.
  • Proposed-Method Configuration: The proposed method uses the same graph neural network architecture for line-graph embeddings but omits graph pooling and one-dimensional convolution layers.It is trained for 15 epochs on each dataset and therefore has fewer parameters than SEAL.
  • Reported Metrics: Tables II and III report AUC and average precision comparisons using 80% training links.The tables compare the proposed method with the baseline methods.

C. Results and Analysis

Across plain and attributed graph link prediction experiments, LGLP consistently outperforms the baselines, remains effective with fewer training links, and converges faster than SEAL.

  • Plain Graph Link Prediction: LGLP consistently achieves better AUC and AP than all baselines, including SEAL, across 14 datasets.The results also report greater stability than other baseline methods.
  • Plain Graph Link Prediction: With 50% training links, LGLP significantly outperforms baselines on most datasets, with AUC and AP close to results using 80%.This evaluates performance under limited training samples.
  • Plain Graph Link Prediction: Across training fractions from 30% to 80%, LGLP outperforms all baseline methods and is not sensitive to the number of training samples.The comparison includes Katz, PageRank, SimRank, SEAL, and LGLP.
  • Attributed Graph Link Prediction: On attributed graphs, LGLP performance does not change significantly after incorporating node attributes, unlike the decreases observed for SEAL.The attributed-graph experiment uses the Cora dataset.
  • Convergence Speed Analysis: LGLP converges in 10 to 15 epochs, whereas SEAL takes 50 epochs, while using fewer model parameters.The speed comparison tracks training loss and test AUC across epochs.

IV. CONCLUSION

The paper proposes line graph neural networks for link prediction to learn target-link features directly without pooling. Experiments on 14 datasets show that the method outperforms baseline methods and converges faster than the state-of-the-art model.

  • IV. CONCLUSION: LGLP transforms the input graph into a line graph so target-link features can be learned directly without pooling.This design addresses information loss associated with pooling operations.
  • IV. CONCLUSION: On 14 datasets from different areas, LGLP outperforms all baseline methods, including state-of-the-art models.The conclusion reports a broad cross-dataset performance advantage.
  • IV. CONCLUSION: LGLP converges significantly faster than the state-of-the-art model.The method is designed to avoid pooling layers during target-link feature learning.
Loading 2010.10046v1…