PaperlayerView exact revision on arXiv

Source-linked AI summary

GC-LSTM: Graph Convolution Embedded LSTM for Dynamic Link Prediction

Jinyin Chen, Xueke Wang, Xuanheng Xu

arXiv:1812.04206v2cs.SIphysics.soc-ph

TL;DR

Dynamic link prediction must model evolving network structure rather than relying only on static snapshots. GC-LSTM embeds GCN within LSTM cells to learn snapshot structure and temporal features, and it predicts appearing, disappearing, and constant links. Experiments report that it outperforms current state-of-the-art methods across multiple metrics.

  • Problem

    Dynamic link prediction aims to predict future linkage status from historical network information, but static methods overlook temporal evolution.

  • Method

    GC-LSTM is an end-to-end encoder-decoder model that embeds GCN into LSTM cells, using GCN for snapshot structure and LSTM for temporal characteristics.

  • Results

    GC-LSTM significantly outperforms current state-of-the-art methods and performs better across reported AUC, GMAUC, and ER measures.

  • Takeaways & Limitations

    The model predicts the whole dynamic network, including links that appear, disappear, or remain constant.

  • Takeaways & Limitations

    The paper identifies scalability to networks with hundreds of thousands of nodes and links as a practical boundary requiring further work.

Abstract

from arXiv · show

Dynamic link prediction is a research hot in complex networks area, especially for its wide applications in biology, social network, economy and industry. Compared with static link prediction, dynamic one is much more difficult since network structure evolves over time. Currently most researches focus on static link prediction which cannot achieve expected performance in dynamic network. Aiming at low AUC, high Error Rate, add/remove link prediction difficulty, we propose GC-LSTM, a Graph Convolution Network (GC) embedded Long Short Term Memory network (LTSM), for end-to-end dynamic link prediction. To the best of our knowledge, it is the first time that GCN embedded LSTM is put forward for link prediction of dynamic networks. GCN in this new deep model is capable of node structure learning of network snapshot for each time slide, while LSTM is responsible for temporal feature learning for network snapshot. Besides, current dynamic link prediction method can only handle removed links, GC-LSTM can predict both added or removed link at the same time. Extensive experiments are carried out to testify its performance in aspects of prediction accuracy, Error Rate, add/remove link prediction and key link prediction. The results prove that GC-LSTM outperforms current state-of-art method.

1 Introduction

Dynamic network link prediction uses historical graph snapshots to predict future linkage status, addressing the temporal evolution that static methods overlook. GC-LSTM integrates graph convolution within LSTM cells to learn snapshot structure and temporal features, while predicting links that appear, disappear, or remain constant.

  • Motivation: Dynamic network link prediction predicts future linkage status from historical network information.Dynamic networks are modeled as chronological graph sequences with fixed nodes and changing links.
  • GC-LSTM: GC-LSTM embeds GCN into LSTM cells to combine structural feature learning from each snapshot with temporal feature learning.The design targets unified processing of spatio-temporal network data.
  • Motivation: Static methods analyze individual snapshots and therefore ignore temporal information needed to capture network evolution patterns.
  • Results: Experiments report that GC-LSTM significantly outperforms current state-of-the-art methods across various metrics.
  • GC-LSTM: GC-LSTM predicts links that are going to appear, disappear, or remain constant, rather than only added links.

2 Related Work

Related work includes similarity-based, machine-learning, and deep-learning approaches to dynamic link prediction. The paper positions GC-LSTM as a method that jointly integrates snapshot structure, temporal evolution, and whole-network information.

  • Method categories: Dynamic link prediction methods include similarity-based and machine/deep-learning-based approaches.
  • Similarity-based methods: Similarity-based methods estimate connection likelihood from topology, using local or global structural information.Examples include common neighbors and Katz-style global similarity indexes.
  • Learning-based methods: Prior methods include supervised classifiers, time-weighted random walks, relational-GCN, NetworkGAN, and GCN+GAN models.
  • Problem formulation: Dynamic link prediction must learn temporal features from previous snapshots in addition to each snapshot’s structural features.
  • GC-LSTM: GC-LSTM extracts structural and temporal features for whole-snapshot prediction instead of focusing only on node pairs.The stated goal is to integrate global information automatically.
  • Problem formulation: Dynamic link prediction is formulated as learning from T previous graph snapshots to predict the probability of all links at the next time.

3 Methodology

GC-LSTM models dynamic networks by combining graph convolution for snapshot structure with LSTM-based temporal learning. It encodes historical adjacency matrices and decodes the resulting representation into a predicted network.

  • 3.1 Problem Definition: GC-LSTM uses previous adjacency matrices {At−T, · · · , At−1} to predict the adjacency matrix At at time t.Each adjacency-matrix entry indicates whether a link exists between two nodes.
  • 3.2 Overall Framework: The decoder is a fully connected network that maps the final hidden representation ht back to the original network space.Its output is a probability matrix representing predicted link states.
  • 3.3 GC-LSTM Model: The encoder embeds graph convolution into LSTM cells to learn structural and temporal features from dynamic-network snapshots.Graph convolution operates on the LSTM hidden state h and cell state c, integrating neighborhood structure with temporal state updates.
  • 3.3 GC-LSTM Model: GC-LSTM adapts graph convolution to directed networks by redefining the Laplacian and using a Chebyshev-polynomial graph filter.The directed Laplacian uses the adjacency and degree matrices, while K controls the graph-convolution order.
  • 3.3 GC-LSTM Model: The graph-convolution order K determines the neighborhood range used for structural information, with K=1 using first-order neighbors.The model sets K to 3 to balance performance and efficiency; graph convolution on c follows the same operation as on h with a different input state.

4 Experiments

Experiments compare GC-LSTM with established static and dynamic baselines across multiple real-world dynamic networks using several link-prediction metrics. GC-LSTM generally performs best, especially for error rates, combined added/removed-link evaluation, long-term prediction, and important links.

  • Experimental setup: GC-LSTM is evaluated against node2vec, TNE, ctRBM, GTRBM, and DDNE on several real benchmark dynamic networks.The evaluation uses AUC, GMAUC, ER, ER+, and ER− as performance indicators.
  • Dynamic prediction results: GC-LSTM outperforms all baseline methods on ER, ER+, and ER−, although TNE achieves better AUC and GMAUC on FB-FORUM and LKML.GC-LSTM performs better than other dynamic prediction models on all datasets in most cases, particularly on GMAUC.
  • Model comparison: GC-LSTM combines graph convolution for snapshot structure learning with LSTM-based temporal learning, using an embedded architecture rather than simply stacking the two components.The model is designed to learn spatio-temporal features from dynamic network sequences.
  • Error analysis: Most methods produce larger ER than ER+ in sparse networks, while GC-LSTM keeps both ER+ and ER− below the corresponding baseline values in most cases.The analysis links the imbalance to methods predicting more invalid than existent links, especially for node2vec.
  • Temporal performance: Long-term prediction becomes harder as AUC and GMAUC decrease while ER, ER+, and ER− increase over time; performance remains relatively stable on periodically evolving RADOSLAW and LKML.The reported trend is attributed to uncertainty in network evolution over longer periods.
  • Prediction of important links: GC-LSTM has the lowest ER in most short- and long-term important-link evaluations, and its ER on the top 10% important links is lower than on all links.This indicates stronger reported performance on important links than on less important ones.

5 Conclusion

GC-LSTM is presented as an encoder-decoder model combining GCN for snapshot structure and LSTM for temporal characteristics in dynamic link prediction. Experiments report advantages across several metrics and important-link prediction, while scalability and computational cost remain concerns.

  • 5 Conclusion: GC-LSTM combines GCN-based snapshot structure learning with LSTM-based temporal learning in an encoder-decoder architecture.A fully connected decoder maps the extracted spatio-temporal features back to the original space.
  • 5 Conclusion: GC-LSTM’s important-link evaluation concerns the top 10% of links ranked by DC and EBC.Table 4 reports prediction ER for these important links.
  • 5 Conclusion: The model’s applicability to very large dynamic networks remains a future focus, including networks with hundreds of thousands of nodes and links.The conclusion identifies accelerating the model and large-scale dynamic-link prediction as future work.
  • 5 Conclusion: The model outperforms traditional link-prediction methods on AUC, GMUUC, and ER across experiments.The conclusion also reports better performance for important links characterized by DC and EBC in most cases.

Compliance with Ethical Standards

The paper states that it involved no studies with human participants or animals and reports no conflict of interest. It also notes computational limitations related to pre-training.

  • Compliance with Ethical Standards: The article reports no studies involving human participants or animals.
  • Compliance with Ethical Standards: GC-LSTM requires pre-training, resulting in relatively high time complexity.The authors identify accelerating the model as future work.
  • Compliance with Ethical Standards: The authors declare that they have no conflict of interest.
Loading 1812.04206v2…