PaperlayerView exact revision on arXiv

Source-linked AI summary

Dynamic Graph Representation Learning via Self-Attention Networks

Aravind Sankar, Yanhong Wu, Liang Gou, Wei Zhang, Hao Yang

arXiv:1812.09430v2cs.LGcs.SIstat.ML

TL;DR

Graph representation methods largely target static graphs, while real-world graphs evolve and require representations that capture both structure and temporal behavior. DySAT uses self-attention over structural neighborhoods and historical representations, and it improves dynamic link prediction over several state-of-the-art baselines. The method averages a 3.6% macro-AUC gain across four benchmarks and shows more stable performance across time steps.

  • Problem

    Existing graph representation methods mainly focus on static graphs, while dynamic graphs require embeddings that preserve structural proximity and temporal dependencies.

  • Method

    DySAT jointly applies self-attention over structural neighborhoods and historical node representations to learn dynamic node embeddings.

  • Results

    DySAT achieves a 3.6% macro-AUC improvement on average over several state-of-the-art baselines across four dynamic link-prediction benchmarks.

  • Takeaways & Limitations

    Self-attentional modeling of structural and temporal information provides a strong approach for dynamic graph representation learning and link prediction.

  • Takeaways & Limitations

    The experiments use graphs without node features, and storing each snapshot's adjacency matrix in memory may create scaling challenges for large graphs.

Abstract

from arXiv · show

Learning latent representations of nodes in graphs is an important and ubiquitous task with widespread applications such as link prediction, node classification, and graph visualization. Previous methods on graph representation learning mainly focus on static graphs, however, many real-world graphs are dynamic and evolve over time. In this paper, we present Dynamic Self-Attention Network (DySAT), a novel neural architecture that operates on dynamic graphs and learns node representations that capture both structural properties and temporal evolutionary patterns. Specifically, DySAT computes node representations by jointly employing self-attention layers along two dimensions: structural neighborhood and temporal dynamics. We conduct link prediction experiments on two classes of graphs: communication networks and bipartite rating networks. Our experimental results show that DySAT has a significant performance gain over several different state-of-the-art graph embedding baselines.

1 INTRODUCTION

Dynamic graphs require representations that preserve neighborhood structure while modeling temporal evolution, but prior methods often focus on static structure or temporal smoothness. DySAT addresses this gap with self-attention over structural neighborhoods and historical representations, achieving improved dynamic link prediction.

  • 1 INTRODUCTION: Dynamic graph embeddings must capture both structural proximity and temporal dependencies as nodes and links evolve, emerge, disappear, and reorganize over time.These dynamics include changing communities and distinct node-level evolutionary behaviors.
  • 1 INTRODUCTION: Prior dynamic representation methods commonly enforce smoothness between adjacent snapshots, which may fail for nodes with substantially different evolutionary behaviors.Some prior approaches also focus on limited structural proximity rather than broader neighborhood structure.
  • 1 INTRODUCTION: DySAT applies self-attention along structural-neighborhood and temporal dimensions to model neighbors and relevant historical representations.Its temporal attention captures dependencies at fine-grained node-level granularity rather than imposing only temporal smoothness.
  • 1 INTRODUCTION: DySAT achieves significant performance gains over state-of-the-art baselines, averaging 3.6% macro-AUC improvement across four dynamic link-prediction benchmarks.The benchmarks include two email communication networks and two bipartite rating networks.

2 RELATED WORK

Related work spans static graph embeddings, dynamic graph methods, and self-attention architectures. DySAT combines these directions by using self-attention to aggregate neighborhoods and historical representations while targeting representation quality from temporal structure.

  • 2 RELATED WORK: Static graph representation methods include spectral dimensionality reduction, Skip-gram approaches, and graph neural networks based on generalized convolutions.
  • 2 RELATED WORK: Dynamic graph embedding methods commonly use temporal smoothness, triadic closure, recurrent architectures, or incremental updates to model evolving graphs.Their goals and capabilities differ, including stability, temporal reasoning, or online efficiency.
  • 2 RELATED WORK: DySAT uses self-attention over neighbors and historical representations to capture relevant temporal contexts and improve dynamic node representation quality.This differs from approaches focused primarily on online updates or tracing link evolution.

3 PROBLEM DEFINITION

The paper defines a dynamic graph as a sequence of weighted snapshots and seeks time-indexed node embeddings that preserve both local structure and prior evolutionary behavior.

  • 3 PROBLEM DEFINITION: A dynamic graph is represented as a sequence of weighted undirected snapshots G = {G_1, ..., G_T}, with shared nodes and time-specific links and adjacency matrices.
  • 3 PROBLEM DEFINITION: The objective is to learn a d-dimensional representation e_v^t for each node v at each time step t.
  • 3 PROBLEM DEFINITION: Each representation should preserve the node's local graph structure and evolutionary behavior before time t.

4 DYNAMIC SELF-ATTENTION NETWORK

DySAT combines structural self-attention over snapshot neighborhoods with temporal self-attention over node histories to learn dynamic representations. Its architecture feeds structural features into temporal modeling and trains representations using graph-context prediction.

  • Structural attention: Structural attention aggregates immediate-neighbor representations within each snapshot, using learned normalized coefficients to weight neighbors’ contributions.The layer transforms node representations and produces outputs encoding local structural properties.
  • Temporal attention: Temporal attention uses each node’s current representation to attend over historical representations while preserving autoregressive temporal order.A mask prevents attention from future time steps, and the layer captures dependencies across representations of the same node.
  • Multi-head attention: Multi-head attention is applied in both structural and temporal layers, with multiple heads jointly attending to different subspaces before concatenation.Structural attention operates within one snapshot, whereas temporal attention spans multiple time steps.
  • Architecture: DySAT stacks structural and temporal self-attention blocks, followed by graph-context prediction, to generate latent node representations at each time step.The structural block operates on graph snapshots, while the temporal block models representations across time.
  • Graph context prediction: Graph-context prediction trains dynamic representations to preserve local structure by predicting neighborhood nodes and encouraging random-walk co-occurring nodes to have similar representations.The objective uses binary cross-entropy at each time step, with negative sampling balancing positive and negative examples.

5 EXPERIMENTS

DySAT is evaluated for dynamic link prediction on four public benchmarks spanning communication and bipartite rating networks, using AUC-based comparisons with static and dynamic embedding baselines. It achieves consistent gains across datasets, remains relatively stable over time, and adds modest temporal-attention runtime cost.

  • 5.1 DATASETS: The evaluation uses four dynamic benchmarks: Enron and UCI communication networks, plus Yelp and MovieLens bipartite rating networks.Each dataset is represented by graph snapshots formed from interactions observed in fixed-length time windows.
  • 5.2 EXPERIMENTAL SETUP: The task predicts links at Gt+1 from node representations learned through snapshots {G1, . . . , Gt}, evaluated with AUC after logistic-regression classification.Evaluation examples contain equal numbers of links and randomly sampled non-links, with results averaged over 10 randomized runs.
  • 5.4 EXPERIMENTAL RESULTS: DySAT achieves consistent gains of 3–4% macro-AUC over the best baseline across all datasets.Models are trained through each snapshot and evaluated on the next snapshot; Table 2 reports micro- and macro-averaged AUC across time steps.
  • 5.4 EXPERIMENTAL RESULTS: DySAT maintains more stable performance across time steps, while static embedding methods show drastic drops at some Enron and UCI time steps.Figure 2 compares DySAT with static and dynamic embedding models across multiple time steps.
  • 5.4 EXPERIMENTAL RESULTS: On ML-10M, DySAT takes 0.72 seconds per mini-batch versus 0.51 seconds without temporal attention, indicating a relatively low temporal-attention cost.The measurement uses an Nvidia Tesla V100 GPU and 28 CPU cores.

6 DISCUSSION

The discussion relates DySAT’s performance to the expressive aggregation of GraphSAGE and the temporal behavior of competing methods. It also identifies memory scaling as a current constraint and motivates incremental, memory-efficient extensions.

  • 6 DISCUSSION: GraphSAGE performs comparably to DynamicTriad across datasets despite being trained only on static graphs.The authors conjecture that combining structural and temporal modeling with expressive multi-head attention contributes to DySAT’s stronger performance.
  • 6 DISCUSSION: Static node2vec remains consistent without temporal information, while the authors identify sampling techniques as a direction for improving DySAT.This observation is presented alongside the conjecture that expressive aggregation helps explain DySAT’s gains.
  • 6 DISCUSSION: DySAT’s adjacency storage keeps every snapshot in memory, which may create memory challenges when scaling to large graphs.The authors plan memory-efficient mini-batch training and introduce IncSAT as an incremental extension targeting computation and memory cost.
  • 6 DISCUSSION: DySAT also reports significant relative improvements of 6% AUC on average for multi-step link prediction over existing methods.This result is reported as an additional experiment in Appendix C.

7 CONCLUSION

The paper concludes that DySAT represents dynamic graphs through self-attention over structural neighborhoods and historical representations. Ablations and head-count sensitivity analyses support the contributions of both attention dimensions, while the framework remains aimed at node-feature-free graph settings.

  • 7 CONCLUSION: DySAT computes dynamic node representations by attending over structural neighborhoods and historical node representations.The architecture is intended to capture temporal evolutionary patterns in graph structures.
  • 7 CONCLUSION: The experiments use graphs without node features, although the authors state that DySAT can be generalized to feature-rich graphs.Continuous-time generalization is identified as another direction for incorporating finer temporal variation.
  • A.1 EFFECTIVENESS OF SELF-ATTENTION: Removing structural or temporal attention lowers performance relative to DySAT, which achieves a 3% average Macro-AUC gain over the ablated variants.The structural block can capture some temporal evolution even without explicit temporal modeling, but removing it decreases performance on most datasets.
  • A.1 EFFECTIVENESS OF SELF-ATTENTION: DySAT benefits from multi-head attention in both structural and temporal layers, with performance stabilizing at 8 heads.The sensitivity analysis varies structural and temporal head counts independently from 1 to 16 on UCI and Yelp.

A.2 SCALABILITY ANALYSIS

DySAT scales better than the RNN-based DynAERNN and learns dataset-dependent temporal attention patterns. Its attention emphasizes recent snapshots in Yelp but distributes weight more uniformly across UCI history.

  • Scalability analysis: 88 seconds versus 723 seconds per epoch at window size 10 shows DySAT trains substantially faster than DynAERNN on ML-10M.The authors attribute this advantage to parallelizable self-attention versus sequential RNN back-propagation.
  • Scalability analysis: Figure 4 compares DySAT and DynAERNN scalability and visualizes mean temporal attention weights for UCI and Yelp.The figure combines runtime comparison with a heatmap of learned temporal attention.
  • Temporal attention visualization: Yelp temporal attention is biased toward recent snapshots, whereas UCI attention is more uniformly distributed across historical snapshots.The authors relate this contrast to bursty, event-correlated Yelp ratings versus longer-spanning UCI communications.
  • Temporal attention visualization: The temporal-attention analysis examines historical snapshots used to predict links at each later time step.Each heatmap row represents attention weights over prior snapshots for one prediction time step.

B DYNAMIC NEW LINK PREDICTION

DySAT remains effective when evaluation is restricted to newly appearing links. It achieves consistent gains over the best baselines despite the greater difficulty of predicting links absent from the previous snapshot.

  • New-link results: DySAT achieves consistent relative gains of 3–5% Macro-AUC over the best baselines for dynamic new-link prediction.The evaluation uses four datasets and reports micro- and macro-averaged AUC scores.
  • Evaluation setup: New-link prediction is more difficult than predicting all links at the next time step, producing lower absolute performance for every method.Evaluation examples contain new links at Gt+1 and an equal number of sampled non-links.
  • Evaluation setup: Table 4 reports micro- and macro-averaged AUC with standard deviations for competing methods on dynamic new-link prediction.GraphSAGE results use the best-performing aggregator for each dataset.

C MULTI-STEP LINK PREDICTION

DySAT supports forecasting links across multiple future snapshots and performs strongly over the six-step horizon. It also outperforms baselines on links involving newly appearing nodes despite their limited history.

  • Multi-step forecasting: The multi-step evaluation trains models on earlier snapshots and uses the latest embeddings to forecast links in the final six snapshots.Performance is evaluated separately at each future time step.
  • Multi-step forecasting: DySAT achieves significant gains over all baselines and maintains stable link-prediction performance across six future time steps.All models show some performance decay over time, but static methods vary more than DySAT.
  • Unseen-node prediction: DySAT outperforms other baselines on most datasets for links involving new or previously unseen nodes.The evaluation focuses on links among nodes newly appearing at each time step and corresponding sampled non-links.
  • Unseen-node prediction: For a new node, neighboring nodes can transmit indirect temporal signals through structural attention despite the node’s absent history.The authors hypothesize that this signal contributes to DySAT’s improvements on unseen-node prediction.

E INCREMENTAL SELF-ATTENTION NETWORK

IncSAT extends DySAT for incremental learning by storing historical structural representations and applying temporal attention at the current snapshot. It performs comparably to DySAT while outperforming DynGEM, with self-attention remaining computationally parallelizable.

  • Incremental learning: Incremental graph representation learning restricts the model to the current snapshot and a summary of historical snapshots rather than full historical graphs.Stored intermediate representations summarize prior structural information.
  • IncSAT architecture: IncSAT applies structural self-attention only at the latest snapshot and temporal self-attention over stored historical representations.Historical structural outputs are loaded from previously saved models to produce current node embeddings.
  • Incremental results: IncSAT achieves comparable performance to DySAT on most datasets while significantly outperforming DynGEM with minimal hyper-parameter tuning.The comparison reports micro- and macro-averaged AUC with standard deviations.
  • Complexity and scalability: DySAT’s overall complexity is O(|V|T^2D + |V|TD^2 + |E_t|D), with the dominant temporal term fully parallelizable for GPU acceleration.The authors report DySAT as around ten times faster than RNN-based methods with GPUs.

H ADDITIONAL DATASET DETAILS

The study constructs dynamic-graph snapshots by aggregating interactions within time windows, using dataset-specific preprocessing and evaluation splits. The datasets cover communication and rating interactions across Enron, UCI, Yelp, and MovieLens.

  • Dynamic graphs are divided into snapshots using time windows designed to provide equitable interaction counts, with link weights equal to within-period interaction totals.This preprocessing supports both communication and rating datasets.
  • Communication Networks: Enron email communications are represented as 16 two-month snapshots, with five warm-up snapshots and 11 evaluation snapshots.Only emails involving Enron employees are retained.
  • Communication Networks: UCI private messages are converted into ten-day snapshots, while terminal snapshots lacking sufficient communications are discarded or merged.
  • Rating Networks: The Yelp rating network is restricted to Arizona restaurants, users and businesses with at least 15 ratings, and six-month snapshots over the study period.
  • Rating Networks: The MovieLens user-tag network captures tagging on rated movies through 13 snapshots formed with three-month windows across three years.
Loading 1812.09430v2…