PaperlayerView exact revision on arXiv

Source-linked AI summary

E-LSTM-D: A Deep Learning Framework for Dynamic Network Link Prediction

Jinyin Chen, Jian Zhang, Xuanheng Xu, Chengbo Fu, Dan Zhang, Qingpeng Zhang, Qi Xuan

arXiv:1902.08329v1cs.SIcs.LG

TL;DR

Dynamic network link prediction must model future structure when links appear and disappear over time, but existing methods often have limited accuracy or focus only on additions. The paper proposes an end-to-end E-LSTM-D model combining encoder-decoder structure with stacked LSTM layers to learn spatial and temporal features. Experiments on real-world datasets report that E-LSTM-D outperforms baseline methods and achieves state-of-the-art performance.

  • Problem

    Dynamic network link prediction must forecast future links and their disappearance from historical graphs, while many existing methods focus only on added links.

  • Method

    E-LSTM-D integrates an encoder-decoder architecture with stacked LSTM layers to learn low-dimensional network representations and temporal dependencies end to end.

  • Results

    E-LSTM-D significantly outperforms the compared dynamic network link prediction methods and achieves state-of-the-art performance across the reported experiments.

  • Takeaways & Limitations

    The model can predict links that appear or disappear, support long-term prediction with slight performance drops, and adapt to networks of different scales through structure tuning.

Abstract

from arXiv · show

Predicting the potential relations between nodes in networks, known as link prediction, has long been a challenge in network science. However, most studies just focused on link prediction of static network, while real-world networks always evolve over time with the occurrence and vanishing of nodes and links. Dynamic network link prediction thus has been attracting more and more attention since it can better capture the evolution nature of networks, but still most algorithms fail to achieve satisfied prediction accuracy. Motivated by the excellent performance of Long Short-Term Memory (LSTM) in processing time series, in this paper, we propose a novel Encoder-LSTM-Decoder (E-LSTM-D) deep learning model to predict dynamic links end to end. It could handle long term prediction problems, and suits the networks of different scales with fine-tuned structure. To the best of our knowledge, it is the first time that LSTM, together with an encoder-decoder architecture, is applied to link prediction in dynamic networks. This new model is able to automatically learn structural and temporal features in a unified framework, which can predict the links that never appear in the network before. The extensive experiments show that our E-LSTM-D model significantly outperforms newly proposed dynamic network link prediction methods and obtain the state-of-the-art results.

I. INTRODUCTION

Dynamic network link prediction targets future network structure as nodes and links change over time. The paper proposes E-LSTM-D to learn structural and temporal features jointly and reports state-of-the-art performance across experiments.

  • Motivation: Dynamic networks evolve as nodes appear or disappear and links vanish or recover, making link prediction important for analyzing changing relationships.Applications include online social networks, disease contagion, and protein-protein interactions.
  • Related Work: Existing similarity indices and embedding-based methods have limited ability to model temporal changes, and many methods predict only added links.The paper also identifies separate link representation and binary-classification stages as less unified.
  • Proposed Approach: E-LSTM-D combines an encoder-decoder architecture with stacked LSTM layers to learn network representations and temporal evolution patterns end to end.The model targets links that may appear or disappear and addresses high dimensionality, non-linearity, and sparsity.
  • Contributions: E-LSTM-D supports long-term prediction with only slight performance drops and can be adapted to networks of different scales by tuning layer sizes.It predicts both appearing and disappearing links, whereas most existing methods focus on appearing links.
  • Contributions: The paper introduces Error Rate alongside AUC to provide a more comprehensive evaluation of dynamic network link prediction.The evaluation compares E-LSTM-D with five baseline methods across various metrics.

II. METHODOLOGY

Dynamic network link prediction maps a sequence of historical snapshot graphs to the next graph. E-LSTM-D uses an encoder, stacked LSTM, and decoder to represent graph structure, learn temporal dependencies, and reconstruct the future graph.

  • Problem Definition: A dynamic network is represented as snapshot graphs sampled at fixed intervals, with each graph encoding links through its adjacency matrix.The adjacency matrix records directed links with binary entries.
  • Problem Definition: Dynamic network link prediction learns a function that maps the sequence S={G_t−N, ..., G_t−1} to the future graph G_t.The objective is to identify links most likely to appear or disappear in the next timespan.
  • E-LSTM-D Framework: The encoder converts graph inputs into lower-dimensional structural representations, while the decoder maps extracted features back to the original graph space.This architecture addresses high-dimensional, nonlinear, and sparse network structure.
  • E-LSTM-D Framework: A stacked LSTM between the encoder and decoder learns temporal dependencies and long-term patterns across successive network snapshots.The LSTM uses forget, input, and output gates to process time-varying information.

1) Encoder-decoder architecture:

The E-LSTM-D architecture combines an encoder, stacked LSTM, and decoder to learn nonlinear network structure and temporal evolution before reconstructing the target snapshot.

  • Encoder-decoder architecture: The encoder projects high-dimensional graph data into lower-dimensional vectors that characterize local network structure.The encoder uses multiple nonlinear layers, while the supervised decoder maps latent features back toward the target adjacency matrix.
  • Encoder-decoder architecture: The decoder mirrors the encoder and transforms latent features into a fixed-shape reconstruction under supervision from the target adjacency matrix.Its output layer uses sigmoid activation, with one unit for each network node.
  • Stacked LSTM: LSTM addresses the encoder-decoder's inability to capture time-varying characteristics by learning long-term dependencies through forget, input, and output gates.These gates regulate retained, added, and exported information in the cell state.
  • Stacked LSTM: Stacked LSTM is inserted between encoder and decoder to learn patterns in how the network evolves over time.It processes temporal signals through multiple LSTM cells and passes the resulting hidden representation to the next training step.
  • Encoder-decoder architecture: The encoder reduces each graph's dimension, keeping stacked-LSTM computation manageable while complementing its temporal modeling.The architecture combines structural compression with sequential processing.

C. Balanced Training Process

The balanced training process modifies the loss to emphasize existing links in sparse adjacency matrices, combines regularization, and optimizes the model through forward and backward propagation.

  • Balanced loss: The proposed loss penalizes errors on existing links more heavily than errors on nonexistent links to address adjacency-matrix sparsity.The penalty matrix assigns β > 1 to non-zero target entries and 1 to zero entries.
  • Balanced loss: The total objective adds an L2 regularizer to the weighted reconstruction loss, with α controlling the tradeoff.The regularizer is intended to prevent overfitting.
  • Output processing: The decoder applies sigmoid outputs and thresholds values at 0.5 to produce a binary adjacency matrix.Predictions at or above 0.5 indicate a link; lower values indicate no link.
  • Optimization: Training performs forward propagation to compute loss, then back propagation updates the model parameters through partial derivatives.The procedure accounts for recurrent cell states when differentiating weights in LSTM cells.
  • Optimization: The learning rate is set to 1e-3 in the reported experiments.This parameter controls the weight-update step.

III. EXPERIMENTS

The study evaluates E-LSTM-D on five benchmark datasets and compares it with four baseline methods.

  • III. EXPERIMENTS: The proposed E-LSTM-D is evaluated on five benchmark datasets against four baseline methods.These experiments constitute the paper's empirical evaluation.

A. Datasets

The experiments use five real-world dynamic human-contact networks spanning face-to-face proximity, email, online-forum, and mailing-list interactions, with snapshots prepared for temporal prediction.

  • A. Datasets: The five datasets are real-world dynamic human-contact networks in which nodes represent humans and links represent their contacts.The contacts include face-to-face proximity, emailing, and related interactions.
  • A. Datasets: CONTACT records face-to-face proximity using wireless devices, with observations collected every 20 seconds.Multiple edges can occur within the same interval when multiple contacts are observed.
  • A. Datasets: ENRON and RADOSLAW represent email networks, with interaction records spanning nearly 6 and 9 months, respectively.Each node is an employee and each link records an email sent between employees.
  • A. Datasets: FB-FORUM is an online student social network whose records span more than 5 months.Links represent interactions such as messages between users.
  • A. Datasets: LKML is constructed from Linux kernel mailing-list replies among 2,210 users, using activity recorded from 2007-04-01 to 2013-12-01.Experiments use both long-term and short-term versions of the network.
  • A. Datasets: Each dataset is split into 320 time-ordered snapshots with input sequence length N = 10 after removing links absent from the following 8 intervals.Snapshot intervals vary by dataset timespan.

B. Baseline Methods

The study compares E-LSTM-D with node2vec and four dynamic network link prediction baselines, using established embedding, temporal, generative, boosting, and recurrent approaches.

  • Baseline set: The evaluation compares E-LSTM-D with node2vec, TNE, ctRBM, GTRBM, and DDNE.The baselines include static network embedding and methods designed to model temporal dependencies.
  • Baseline mechanisms: node2vec maps network nodes into lower-dimensional vectors, with shorter distances indicating higher connection probability.
  • Baseline mechanisms: TNE models network evolution as a Markov process and obtains node embeddings through matrix factorization.
  • Baseline mechanisms: ctRBM generates node vectors from temporal connections and predicts future links using neighbor information.
  • Baseline mechanisms: GTRBM combines temporal restricted Boltzmann machines with gradient-boosting decision trees to learn hidden dynamic patterns.
  • Baseline mechanisms: DDNE uses a GRU encoder for historical information and decodes concatenated snapshot embeddings into a future network structure.

C. Evaluation Metrics

The evaluation uses AUC and GMAUC together with a newly defined Error Rate to assess dynamic network link prediction under sparsity and changing links.

  • Metrics: AUC measures whether existing links receive higher scores than nonexistent links, with values closer to 1 indicating more informative prediction.
  • Metrics: The experiments use AUC, GMAUC, and a newly defined Error Rate to evaluate E-LSTM-D and baseline methods.
  • Evaluation procedure: Nonexistent links are randomly sampled in equal number to existing links before metric calculation, reducing sparsity effects.
  • Metrics: GMAUC combines PRAUC for new links and AUC for observed links through their geometric mean.PRAUCnew measures new links, while AUCprev measures observed links.
  • Metrics: Error Rate is the ratio of mispredicted links Nfalse to truly existing links Ntrue.Unlike SumD, it accounts for the number of truly existing links.

D. Experimental Results

Across five datasets, E-LSTM-D generally outperforms the baselines for short- and long-term dynamic link prediction, while longer horizons reduce performance and important links are easier to predict.

  • Overall performance: E-LSTM-D generally outperforms all baselines across large and small, dense and sparse networks for both short- and long-term prediction.
  • Error analysis: E-LSTM-D achieves the best reported DNLP performance on Error Rate, while node2vec produces relatively large Error Rates from predicting too many links.
  • Prediction horizon: AUC and GMAUC generally decrease while Error Rate increases as the prediction horizon Δ grows.The trend indicates that long-term structural prediction is more difficult for most dynamic networks.
  • Prediction horizon: RADOSLAW, FB-FORUM, and LKML show relatively stable long-term prediction performance, associated with comparatively periodic network evolution.
  • Important links: Error Rates for the top 10% important links are much smaller than for all links across the five networks and methods.Importance is measured using degree centrality and edge betweenness centrality.

E. Beyond Link Prediction

Beyond link prediction, E-LSTM-D produces node embeddings that transfer to node classification, while model complexity affects Error Rate more clearly than AUC or GMAUC.

  • Transferability: E-LSTM-D embeddings obtained during link prediction can also effectively support node classification on the karate club dataset.The result is presented as evidence of transferability of the learned representations.
  • Sensitivity factors: The model’s performance is mainly determined by its structure, historical snapshot length N, and penalty coefficient β.
  • Model structure: Reducing the number of units in the first encoder layer slightly lowers performance.
  • Model structure: Adding an encoder layer yields no significant AUC or GMAUC improvement but can lower Error Rates as model complexity increases.

2) Influence of historical snapshot length:

Historical snapshot length trades information against computational cost, with the experiments selecting N = 10 as a practical balance. The model’s broader applicability still has computational and transferability boundaries identified for future work.

  • Influence of historical snapshot length:: A longer history can add information but may contribute little current influence while increasing computational complexity.The study varies historical snapshot length from 5 to 25 to balance efficiency and performance.
  • Influence of historical snapshot length:: AUC and GMAUC increase most from N = 1 to 10, while Error Rate decreases most from N = 1 to 20.Beyond these ranges, the metrics remain almost unchanged for most dynamic networks, motivating N = 10 in earlier experiments.
  • Influence of the penalty coefficient:: The penalty coefficient β is kept relatively small, with β ∈(1, 2] varied by dataset to obtain optimal results.Performance is generally stable as β changes, although some datasets show slightly larger GMAUC and smaller Error Rate with increasing β.
  • Model context: E-LSTM-D learns low-dimensional, nonlinear, and temporal features from successive snapshots in an end-to-end encoder-decoder model.The model uses a stacked LSTM to make fuller use of historical information and capture network-evolution patterns.
  • Future scope: Future work targets layered dynamic networks, lower computational complexity for large-scale networks, and broader transferability across tasks.These directions mark the current scope boundaries of the model.
Loading 1902.08329v1…