PaperlayerView exact revision on arXiv

Source-linked AI summary

GCN-GAN: A Non-linear Temporal Link Prediction Model for Weighted Dynamic Networks

Kai Lei, Meng Qin, Bo Bai, Gong Zhang, Min Yang

arXiv:1901.09165v1cs.SIcs.LGcs.NI

TL;DR

The paper addresses temporal link prediction for weighted dynamic networks, where existing approaches often overlook informative edge weights and nonlinear temporal behavior. GCN-GAN combines GCN, LSTM, and GAN to model topology and evolution while generating future weighted snapshots, and experiments on four datasets report consistent improvements over competitors.

  • Problem

    Temporal link prediction remains challenging because many approaches focus on unweighted links or linear models, despite informative edge weights and nonlinear network transformations.

  • Method

    GCN-GAN combines GCN for snapshot topology, LSTM for evolving patterns, and GAN for generating the next weighted network snapshot.

  • Results

    Experiments on four datasets consistently show GCN-GAN outperforming competing methods for weighted dynamic-network temporal link prediction.

  • Takeaways & Limitations

    The model provides a unified approach for predicting dynamics such as mobility, traffic, and topology in weighted dynamic networks.

Abstract

from arXiv · show

In this paper, we generally formulate the dynamics prediction problem of various network systems (e.g., the prediction of mobility, traffic and topology) as the temporal link prediction task. Different from conventional techniques of temporal link prediction that ignore the potential non-linear characteristics and the informative link weights in the dynamic network, we introduce a novel non-linear model GCN-GAN to tackle the challenging temporal link prediction task of weighted dynamic networks. The proposed model leverages the benefits of the graph convolutional network (GCN), long short-term memory (LSTM) as well as the generative adversarial network (GAN). Thus, the dynamics, topology structure and evolutionary patterns of weighted dynamic networks can be fully exploited to improve the temporal link prediction performance. Concretely, we first utilize GCN to explore the local topological characteristics of each single snapshot and then employ LSTM to characterize the evolving features of the dynamic networks. Moreover, GAN is used to enhance the ability of the model to generate the next weighted network snapshot, which can effectively tackle the sparsity and the wide-value-range problem of edge weights in real-life dynamic networks. To verify the model's effectiveness, we conduct extensive experiments on four datasets of different network systems and application scenarios. The experimental results demonstrate that our model achieves impressive results compared to the state-of-the-art competitors.

I. INTRODUCTION

The paper frames prediction across mobility, traffic, and topology systems as temporal link prediction, focusing on weighted dynamic networks with nonlinear temporal behavior. It proposes GCN-GAN, combining graph, sequence, and adversarial modeling, and evaluates it across four datasets.

  • Challenges: Existing approaches often target application-specific scenarios, unweighted links, or linear temporal transformations, limiting their coverage of weighted nonlinear dynamics.Link weights may encode delay, flow, signal strength, or distance, while network formation is commonly nonlinear over time.
  • Problem formulation: Temporal link prediction models network-system dynamics by constructing the next graph snapshot from previous time slices.The formulation applies to systems such as data-center traffic and other dynamic networks.
  • Proposed model: GCN-GAN uses GCN to capture snapshot topology, LSTM to model evolving network patterns, and GAN to generate the next weighted graph snapshot.The generator predicts next-slice weighted links from historical data, while the discriminator distinguishes generated links from real records.
  • Evaluation: The paper introduces edge-wise KL-divergence and mismatch rate alongside MSE to assess sparsity and wide value ranges in edge weights.These metrics complement standard prediction error by examining weighted-network properties.
  • Evaluation: Across four datasets, GCN-GAN consistently outperforms competing methods for temporal link prediction in weighted dynamic networks.The experiments cover different network systems and application scenarios.

II. RELATED WORK

Prior work models dynamic networks through temporal link prediction, but conventional approaches often use linear representations and focus on unweighted or application-specific settings.

  • Limitations of prior work: Most existing techniques target specific application scenarios, limiting their generalization across different network systems.Examples include traffic forecasting and user-location prediction in particular network contexts.
  • Temporal link prediction: Temporal link prediction represents network-system dynamics as graph evolution over successive snapshots.Prior methods include collapsed-network, tensor-factorization, and graph-regularized NMF approaches.
  • Limitations of prior work: Traditional approaches often collapse successive snapshots or factorize them with linear models, potentially discarding temporal information and nonlinear dynamics.Collapsed networks combine multiple snapshots into one representation, while tensor and NMF methods use factorization-based temporal modeling.
  • Limitations of prior work: Many nonlinear approaches still address unweighted networks, whereas weighted networks encode information such as delay, flow, signal strength, or distance.The limitation concerns methods that predict link existence without modeling informative edge weights.
  • Problem definition: The paper considers undirected weighted dynamic networks whose snapshots share a node set and whose weighted topology is represented by symmetric adjacency matrices.An adjacency entry equals the edge weight when a link exists and zero otherwise.
  • Problem definition: Given l + 1 historical adjacency matrices, the task is to construct the topology of the next time slice using a prediction model f.The input sequence spans A_τ−l through A_τ, and the output is the predicted snapshot Ã_τ+1.

IV. METHODOLOGY

GCN-GAN combines graph convolution, recurrent temporal modeling, and adversarial generation to predict the next snapshot of a weighted dynamic network.

  • Model architecture: GCN-GAN has three main components: a GCN, an LSTM, and a GAN for temporal link prediction in weighted dynamic networks.The architecture contains a generative network G and a discriminative network D.
  • Temporal modeling: The model feeds GCN-derived representations from the historical snapshots into the LSTM to capture evolving patterns in the weighted dynamic graph.The GCN layer outputs a sequence of representations rather than a single snapshot embedding.
  • Model architecture: The generative network consists of a GCN hidden layer, an LSTM hidden layer, and a fully connected output layer, while D is a fully connected feedforward network.The GCN processes snapshot inputs and produces a sequence of representations for subsequent temporal modeling.
  • GCN hidden layer: The GCN extracts local topological characteristics from each graph snapshot before the representations are processed temporally.A separate GCN unit is maintained for each snapshot in the input sequence.
  • GCN hidden layer: A typical GCN applies a localized first-order spectral convolution to node features using the adjacency structure, followed by a fully connected transformation.The operation uses a normalized filter based on A + I_N, a weight matrix, and an activation function.

C. The LSTM Hidden Layer

The LSTM summarizes sequential graph representations for next-snapshot generation, while the GAN addresses limitations of direct MSE-based prediction for sparse, wide-range edge weights.

  • The LSTM Hidden Layer: The LSTM receives GCN representations of historical snapshots and learns their evolving patterns through sequential hidden states.Its recurrent cell combines current input with the previous hidden state using gated updates.
  • The LSTM Hidden Layer: The final hidden state is treated as a distributed representation of historical snapshots and passed to a fully connected layer to generate the next graph snapshot.The generated adjacency values initially lie in [0, 1] and are inverse-normalized to recover the network’s value range.
  • The LSTM Hidden Layer: Direct LSTM prediction commonly uses MSE loss, but MSE does not reflect the sparsity and wide-value-range characteristics of real network link weights.The paper identifies these properties as limitations for weighted dynamic-network prediction.
  • The Generative Adversarial Network: The GAN enhances LSTM’s generative capacity by training G and D in a minimax game over generated and real graph snapshots.D distinguishes generated snapshots from ground truth, while G seeks to make D misclassify its outputs.
  • The Generative Adversarial Network: The discriminative network uses a fully connected feedforward architecture and receives row-wise vectorizations of generated or ground-truth snapshots.Ground-truth snapshots are normalized to [0, 1] before entering D, matching G’s output range.
  • The Generative Adversarial Network: The generator maps noise and the historical snapshot sequence to the predicted next snapshot.The paper denotes this generative operation with G and the normalized snapshot sequence as its network input.

E. Model Optimization

GCN-GAN updates its parameters at each new time slice, pre-trains the generator for temporal consistency, and then uses WGAN adversarial training to generate and refine the next weighted snapshot.

  • Training and prediction: Because network topology evolves, GCN-GAN continually updates its parameters, giving snapshots nearer τ+1 greater relevance to the ground truth.
  • Training and prediction: At time slice τ, the model trains on preceding snapshots with Aτ as ground truth, then predicts Ãτ+1 from the latest sequence.The generated snapshot is renormalized from [0, 1] to the real edge-weight range.
  • Generator pre-training: Standard adversarial training alone may produce plausible but temporally inconsistent snapshots, so the generator is pre-trained to reconstruct the current graph.The pre-training uses previous snapshots and noise, with L2 regularization controlled by λ.
  • Adversarial training: WGAN adversarial training then enhances generation for sparse networks and edge weights spanning wide value ranges, with RMSProp alternating updates until convergence.
  • Prediction refinement: Post-processing symmetrizes the prediction, removes self-connections, and thresholds small values to reflect undirected-network structure and weight sparsity.

A. Datasets

The study evaluates GCN-GAN on four dynamic-network datasets spanning wireless links, data-center flows, and human and vehicle mobility, while characterizing sparsity and weight-range challenges.

  • Dataset overview: Experiments use three real datasets and one simulation dataset, with dataset statistics including nodes, time slices, and maximum edge weight.
  • Dataset overview: UCSB measures wireless-mesh link quality, NumFabric simulates data-center flows, and KAIST and BJ-Taxi represent human and vehicle mobility.
  • Network construction: For UCSB and NumFabric, nodes are hosts and weights directly encode link quality or flow; mobility networks instead derive weights inversely from pairwise distances.
  • Dataset properties: Average zero-element proportions are 0.52, 0.92, 0.94, and 0.50 for UCSB, KASIT, BJ-Taxi, and NumFabric, respectively.
  • Dataset properties: Weighted prediction must distinguish zero entries from small positive weights because confusing absence with weak links can misallocate resources.
  • Dataset properties: Edge weights can span 0 to 20,000, and normalization may make small prediction errors produce large recovered-value MSE.
  • Dataset properties: In UCSB, Fig. 2 plots possible weight values w horizontally against log c(w), where c(w) counts edges having value w; many edges have small weights.

B. Evaluation Metrics

Evaluation combines conventional MSE with edge-wise KL-divergence and mismatch rate to assess prediction error, weight magnitudes, and edge-existence mistakes in sparse weighted networks.

  • Mean Square Error: MSE compares the predicted and ground-truth next adjacency matrices using the squared Frobenius error normalized by |V| × |V|.
  • Edge-wise KL-Divergence: Edge-wise KL-divergence addresses wide weight ranges by emphasizing relative magnitude differences that MSE may underrepresent among small weights.For example, the magnitude difference between 2 and 1 is treated as more important than between 2,000 and 1,990.
  • Edge-wise KL-Divergence: The edge-wise KL metric is computed from normalized ground-truth and predicted snapshot values, with zero-valued cases assigned divergence 0.
  • Mismatch Rate: Mismatch rate measures the proportion of edges whose predicted existence disagrees with the ground truth in a graph snapshot.It captures both predicting a positive weight for an absent edge and predicting zero for an existing edge.

C. Performance Evaluation

The evaluation compares GCN-GAN with six baselines across four datasets using MSE, edge-wise KL-divergence, and mismatch rate. GCN-GAN performs especially strongly on weighted-network sparsity and wide-value-range challenges.

  • Experimental setup: The study compares GCN-GAN with six baselines on four datasets using MSE, edge-wise KL-divergence, and mismatch rate.The baselines include ED, SVD, NMF, GrNMF, AM-NMF, and LSTM.
  • Experimental setup: The evaluation averages metric values over predicted snapshots generated through a continuously sliding window.The initial training uses the first (l +2) snapshots, followed by alternating training and prediction.
  • MSE results: Non-linear models achieve much better MSE scores than linear approaches, indicating stronger feature-learning ability.GCN-GAN obtains the best MSE scores on UCSB, KAIST, and NumFabric, and the second-best MSE in BJ-Taxi.
  • Weighted-network metrics: GCN-GAN outperforms all baselines on edge-wise KL-divergence and mismatch rate across the four datasets.These metrics were introduced to assess sparsity and the wide-value-range property of edge weights.

D. Case Study

The UCSB case study visualizes ground-truth and predicted adjacency matrices to examine weighted-link reconstruction. GCN-GAN preserves large weights and distinguishes zero values from small edge weights more effectively than LSTM.

  • Case-study setup: The case study compares ground-truth, GCN-GAN, and LSTM adjacency matrices for one UCSB graph snapshot.Heat maps visualize the three matrices in Fig. 3.
  • Visualization: Black denotes zero adjacency values, while color depth represents edge weights from relatively small dark-red values to large near-white values.Zero entries are assigned −200 for visualization.
  • Comparison: Both GCN-GAN and LSTM fit large edge weights well, but only GCN-GAN effectively separates zero values from small edge weights.LSTM confuses black zero values with dark-red small weights, whereas GCN-GAN reflects snapshot sparsity.

VI. CONCLUSION

The paper concludes that GCN-GAN addresses temporal link prediction for weighted dynamic networks by combining GCN, LSTM, and GAN capabilities. Experiments across four network-system datasets support its performance and handling of edge-weight sparsity and wide value ranges.

  • Conclusion: GCN-GAN combines GCN and LSTM representations with GAN-based weighted-link generation for temporal link prediction.The model targets dynamics prediction in mobility, traffic, and topology settings.
  • Conclusion: Across four datasets, GCN-GAN outperformed six competitors while addressing sparsity and wide-value-range properties of weighted dynamic networks.The conclusion presents these properties as central evaluation targets.
  • Future work: Future work will examine concrete deployment scenarios, communication-network measures, and temporal link prediction with an unfixed node set.These directions define the paper’s stated scope boundary.
Loading 1901.09165v1…