PaperlayerView exact revision on arXiv

Source-linked AI summary

Temporal Graph Offset Reconstruction: Towards Temporally Robust Graph Representation Learning

Stephen Bonner, John Brennan, Ibad Kureshi, Georgios Theodoropoulos, Andrew Stephen McGough, Boguslaw Obara

arXiv:1811.08366v1cs.SIcs.LG

TL;DR

Many graph representation models ignore temporal evolution, weakening predictions when graph structure changes. The paper trains unsupervised graph-convolutional representations to reconstruct future graph states, and reports stronger future link prediction than non-temporal baselines, including a 38% improvement on a real-world dataset.

  • Problem

    Most graph representation learning approaches focus on current structure and ignore temporal evolution, limiting their ability to predict future graph states.

    Source: §I · p. 1

  • Method

    The paper combines graph convolutional neural networks with temporal offset reconstruction, training vertex representations to predict a later graph state without labels.

    Source: §I · pp. 1–2, C. Graph Convolutions · p. 4

  • Results

    The temporally offset methods generally outperform non-temporal baselines for future link prediction, with the approach outperforming non-temporal baselines by 38% on a real-world dataset.

    Source: 1) Evolution Pattern Prediction · pp. 7–8, 2) Future Link Prediction · p. 8

  • Takeaways & Limitations

    Explicitly training representations to predict future graph states produces representations that perform better on later-time-point predictions.

    Source: §I · p. 2, §VI · p. 9

    The authors identify future work in replacing identity-matrix inputs with topological vertex properties and replacing GCNs with inductive models that support changing vertex counts.

    Source: §VI · p. 9

Abstract

from arXiv · show

Graphs are a commonly used construct for representing relationships between elements in complex high dimensional datasets. Many real-world phenomenon are dynamic in nature, meaning that any graph used to represent them is inherently temporal. However, many of the machine learning models designed to capture knowledge about the structure of these graphs ignore this rich temporal information when creating representations of the graph. This results in models which do not perform well when used to make predictions about the future state of the graph -- especially when the delta between time stamps is not small. In this work, we explore a novel training procedure and an associated unsupervised model which creates graph representations optimised to predict the future state of the graph. We make use of graph convolutional neural networks to encode the graph into a latent representation, which we then use to train our temporal offset reconstruction method, inspired by auto-encoders, to predict a later time point -- multiple time steps into the future. Using our method, we demonstrate superior performance for the task of future link prediction compared with none-temporal state-of-the-art baselines. We show our approach to be capable of outperforming non-temporal baselines by 38% on a real world dataset.

I. INTRODUCTION

Graph representation learning usually models structural relationships while overlooking how graphs evolve, limiting future-state prediction. This paper introduces temporal offset reconstruction and graph convolutional models designed to encode future graph dynamics.

I. INTRODUCTION

  • Most graph representation learning approaches ignore temporal evolution, leaving models without a concept of how graphs will change in the future.This limitation matters when models trained on historical graphs are applied after the underlying structure has changed.Source: §I · p. 1
  • Graph convolutional neural networks are combined with temporal offset reconstruction to capture dynamics in evolving graphs without relying only on static structure.The paper presents this combination as an unsupervised graph-convolution-based model.Source: §I · p. 2
  • Temporal offset reconstruction trains vertex representations to predict a future graph state rather than reconstructing the current state.The method adds temporal information to structural representations by explicitly offsetting input and target graph states.Source: §I · p. 2
  • The work evaluates future link prediction on synthetic and empirical benchmark graph datasets and releases code and experimentation scripts for reproducibility.The experiments cover evolutionary graphs and are accompanied by open-source PyTorch implementations.Source: §I · p. 2

II. RELATED WORKS

Prior graph representation methods include matrix factorization, random-walk, graph-neural, and auto-encoder approaches, while temporal language embeddings model evolution in another domain. These methods motivate temporal graph representations but leave graph-specific temporal prediction comparatively open.

A. Graph Representation Learning

  • Graph representation learning has progressed from matrix factorization and random-walk embeddings to graph neural networks and unsupervised auto-encoders.These approaches learn lower-dimensional vertex representations for downstream analysis, with GCN auto-encoders achieving strong citation-graph link prediction results.Source: A. Graph Representation Learning · p. 2
  • Graph-specific representation learning has historically emphasized structural prediction, while the paper targets representations that account for future graph evolution.The related methods provide structural or neural foundations but do not establish the paper’s temporal offset objective.Source: A. Graph Representation Learning · p. 2, 1) Natural Language Temporal Embeddings · p. 2

1) Natural Language Temporal Embeddings:

  • Temporal language embedding methods model changing word usage through aligned snapshots or dynamic Bayesian embeddings that predict contextual change.The cited approaches include orthogonal Procrustes alignment and variational inference for smoothly evolving representations.Source: 1) Natural Language Temporal Embeddings · pp. 2–3

2) Graph Specific Temporal Embeddings:

Existing temporal graph embeddings use temporal walks, adjacency-matrix factorization, or supervised GCNs, but generally do not explicitly predict future graph states. The paper motivates a future-reconstruction objective because graph changes can degrade predictions over time.

2) Graph Specific Temporal Embeddings:

  • Temporal graph embedding methods broadly divide into temporal-walk and adjacency-matrix-factorization approaches.This taxonomy frames the comparison between trajectory-based models and dynamic auto-encoder methods.Source: 2) Graph Specific Temporal Embeddings · p. 3
  • Temporal-walk methods capture historical trajectories or edge changes, but examples require manual time-window choices or do not reliably predict future graph states.STWalk is not end-to-end and requires selecting how many previous time steps to use, while NetWalk targets streaming anomaly detection.Source: 2) Graph Specific Temporal Embeddings · p. 3
  • DynGEM transfers knowledge between snapshots and expands its auto-encoder as graphs grow, but reconstructs the current graph rather than explicitly predicting the future.Its PropSize heuristic adds neurons for increasing graph size while reusing previous weights.Source: 2) Graph Specific Temporal Embeddings · p. 3
  • Existing temporal GCN approaches are supervised and do not explicitly use the models to predict future graph states.This leaves an unsupervised future-prediction setting insufficiently addressed.Source: 2) Graph Specific Temporal Embeddings · p. 3

A. Motivation

  • Models trained on historical graph data may lose predictive performance as the graph continues to change over time.The motivation is especially relevant to recommender systems that use graph convolutions for future events.Source: A. Motivation · pp. 3–4

B. Temporal Graph Offset Reconstruction

Temporal graph offset reconstruction uses one graph snapshot to learn vertex representations whose output predicts a later snapshot without labels, precomputed features, or random-walk preprocessing. GCNs provide the graph encoder by aggregating normalized neighborhood information across layers.

B. Temporal Graph Offset Reconstruction

  • Temporal offset reconstruction maps an input graph G_i to a representation that predicts a later graph G_i+δ using the input and target snapshots.The intended procedure avoids preprocessing, precomputed vertex features, and labels.Source: B. Temporal Graph Offset Reconstruction · p. 4

C. Graph Convolutions

  • The GCN layer applies normalized adjacency propagation, learned weights, and a nonlinear activation to produce successive vertex representations.The normalized adjacency incorporates the graph adjacency, degree normalization, and self-connections.Source: C. Graph Convolutions · p. 4
  • GCNs encode each vertex by aggregating information from its neighborhood using adjacency matrices and vertex features, with the identity matrix used when features are absent.Stacking layers expands the receptive field from one-hop neighborhoods to multiple hops.Source: C. Graph Convolutions · p. 4

B. Temporal Graph Offset Reconstruction

D. Model Overview

The paper defines non-probabilistic and variational temporal-offset graph auto-encoders that encode the current graph to reconstruct a future snapshot. Both use GCN-based latent representations and inner-product decoding, while TO-GVAE samples embeddings from a learned Gaussian distribution.

  • Both models are trained to reconstruct a future graph state rather than merely capture the current graph structure.Source: D. Model Overview · p. 4
  • TO-GAE encodes A_i with a GCN into Z_i and predicts graph structure at future offset δ through a sigmoid of Z_iZ_i^T.Source: D. Model Overview · p. 4
  • TO-GVAE learns a distribution over vertex embeddings rather than directly learning Z, using GCN-derived mean and variance parameters for Gaussian sampling.Source: D. Model Overview · pp. 4–5
  • In TO-GVAE, separate GCN layers estimate the mean and variance from a shared initial GCN layer, approximating p(A_i+δ|Z_i).Source: D. Model Overview · p. 5
  • The variational model uses an inner product between latent vertex representations to generate predictions for the next graph snapshot.Source: D. Model Overview · p. 5
  • TO-GVAE training directly optimizes a variational lower bound over the model parameters, using a Gaussian prior for p(Z_i).Source: D. Model Overview · p. 5

E. Model Parameters and Training Procedure

Both models use two-layer graph convolutions and are trained with full-batch ADAM for 50 epochs, with L2 regularization added to improve performance.

IV. EXPERIMENTAL SETUP

The experiments evaluate temporal graph representations through evolution-pattern and future-link prediction on changing graph snapshots. Performance is assessed with AUC and AP, where larger values are better.

A. Evaluation Overview and Methodology

B. Performance Metrics

  • B. Performance Metrics: The study evaluates binary edge predictions with AUC and mean average precision, and higher values indicate better performance.Source: B. Performance Metrics · p. 5

C. Datasets

The evaluation combines empirical datasets with synthetic temporal trajectories generated by controllable rewiring processes. The rewiring changes connectivity while preserving the graph’s vertex and edge counts.

C. Datasets

  • C. Datasets: The Cora and Citeseer figures report AUC and AP for whole graphs and for newly altered edges under 25% configuration rewiring per time step.Source: Figure 1 · p. 6, Figure 2 · p. 6
  • C. Datasets: Synthetic temporal trajectories are generated for datasets without inherent temporal information, while cit-HepPh is divided into six timeline-based snapshots.Source: C. Datasets · pp. 5–6

D. Random Rewire Process

  • D. Random Rewire Process: Random rewiring alters edge endpoints through a controllable process while preserving the total numbers of vertices and edges.Source: D. Random Rewire Process · p. 6
  • D. Random Rewire Process: Erdős rewiring moves topology toward uniformly distributed edges between vertices.Source: D. Random Rewire Process · p. 6
  • D. Random Rewire Process: Configuration rewiring approximately preserves each vertex’s degree, producing a graph with a similar degree distribution to the original.Source: D. Random Rewire Process · p. 6

E. Baseline Approaches

Across simulated graph-evolution experiments, temporal-offset methods generally outperform non-temporal baselines, with advantages widening under larger topological perturbations.

E. Baseline Approaches

1) Evolution Pattern Prediction:

  • For Cora with smaller perturbations, temporal-offset methods show a large AUC increase on new edges while also exceeding baselines on the full graph.The full-graph result indicates that temporal-offset training does not harm prediction of edges that have not changed.Source: 1) Evolution Pattern Prediction · p. 7, Figure 3 · p. 7
  • On Citeseer with smaller perturbations, temporal-offset methods continue to beat baselines, with the variational approach often strongest for new-edge prediction.Figure 4 evaluates AUC and AP for the whole graph and altered edges under a 50% rewire chance.Source: 1) Evolution Pattern Prediction · p. 7, Figure 4 · p. 7
  • Temporal-offset methods generally outperform baselines on Cora and Citeseer, including predictions over unchanged and newly altered edges.The results cover both smaller and larger rewire probabilities and evaluate whole graphs as well as new edges.Source: 1) Evolution Pattern Prediction · pp. 7–8
  • With larger perturbations, the performance gap between temporal-offset methods and baselines increases, including predictions several future snapshots after training.This pattern holds for both Cora and Citeseer and for unchanged and new edges.Source: 1) Evolution Pattern Prediction · pp. 7–8, Figure 5 · p. 8, Figure 6 · p. 8

2) Future Link Prediction:

Temporal offset training is more robust than competing approaches when graph topology changes substantially between snapshots. The non-probabilistic temporal offset model consistently outperforms the variational approach in these rewiring experiments.

2) Future Link Prediction:

  • At 50% rewiring, temporal offset training is more robust on Cora and Citeseer, particularly by AUC, with the non-probabilistic model performing best across both datasets.The experiment uses Erdős-based random rewiring between graph snapshots and reports results for only new edges.Source: 2) Future Link Prediction · p. 8
  • With all edges eligible for rewiring, temporal offset approaches generally show greater new-edge prediction performance, especially early in the time series.Figure 6 evaluates the setting where every edge may be rewired between snapshots.Source: 2) Future Link Prediction · p. 8
  • The authors hypothesize that the variational model overfits non-rewired original edges, reducing its ability to learn the Erdős rewiring pattern.Source: 2) Future Link Prediction · p. 8

B. Empirical Time-Series

On cit-HepPh, temporally offset models outperform baselines for both evolution pattern prediction and future link prediction, while the conclusion frames future-target training as the central mechanism.

1) Evolution Pattern Prediction:

  • Temporally offset methods significantly outperform baselines on whole-graph and new-edge evolution pattern prediction for cit-HepPh.The performance gap is larger than in the synthetic results, and the variational temporally offset model is often strongest at later time points.Source: 1) Evolution Pattern Prediction · p. 8, Table II · p. 9

2) Future Link Prediction:

  • Temporally offset approaches outperform baselines on cit-HepPh future link prediction, although the non-probabilistic model usually exceeds the variational model.All approaches retain good predictive performance at later time points, with smaller differences than in evolution pattern prediction.Source: 2) Future Link Prediction · p. 8, Table III · p. 9

VI. CONCLUSION

  • The paper learns vertex representations for future-time prediction by explicitly training graph-specific neural networks with temporal offset reconstruction.Experiments cover both real-world and synthetic evolving graph datasets.Source: §VI · p. 9

Related papers

Loading 1811.08366v1…