PaperlayerView exact revision on arXiv

Source-linked AI summary

Inductive Representation Learning on Temporal Graphs

Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, Kannan Achan

arXiv:2002.07962v1cs.LGstat.ML

TL;DR

Temporal graph representation learning must handle evolving topology, temporal features, and embeddings for unseen nodes. The paper proposes TGAT, combining self-attention with Bochner-based functional time encoding, and reports stronger performance across transductive and inductive tasks. Its scope includes a simplifying treatment of recurring interactions.

  • Problem

    Temporal graph learning must represent continuous-time dynamics, temporal constraints, and evolving node and topological features while supporting inductive embeddings for unseen nodes.

  • Method

    TGAT combines self-attention with a Bochner-theorem-based functional time encoding to aggregate temporal neighborhoods and learn time-feature interactions.

  • Results

    TGAT achieves state-of-the-art performance across transductive and inductive temporal learning tasks, with at least 5% higher accuracy and average precision than upgraded GraphSAGE-LSTM and GAT in inductive learning.

  • Takeaways & Limitations

    The approach provides time-aware embeddings for observed and unseen nodes through a single network forward pass and captures temporal-feature signals in node and topological features.

  • Takeaways & Limitations

    Recurring interactions between the same nodes are not explicitly distinguished in the notation for presentation clarity.

Abstract

from arXiv · show

Inductive representation learning on temporal graphs is an important step toward salable machine learning on real-world dynamic networks. The evolving nature of temporal dynamic graphs requires handling new nodes as well as capturing temporal patterns. The node embeddings, which are now functions of time, should represent both the static node features and the evolving topological structures. Moreover, node and topological features can be temporal as well, whose patterns the node embeddings should also capture. We propose the temporal graph attention (TGAT) layer to efficiently aggregate temporal-topological neighborhood features as well as to learn the time-feature interactions. For TGAT, we use the self-attention mechanism as building block and develop a novel functional time encoding technique based on the classical Bochner's theorem from harmonic analysis. By stacking TGAT layers, the network recognizes the node embeddings as functions of time and is able to inductively infer embeddings for both new and observed nodes as the graph evolves. The proposed approach handles both node classification and link prediction task, and can be naturally extended to include the temporal edge features. We evaluate our method with transductive and inductive tasks under temporal settings with two benchmark and one industrial dataset. Our TGAT model compares favorably to state-of-the-art baselines as well as the previous temporal graph embedding approaches.

1 INTRODUCTION

Temporal graph representation learning must model continuous-time dynamics, temporal constraints, and evolving node or topological features while inductively embedding unseen nodes. The paper combines self-attention with functional time encoding and evaluates the approach across temporal prediction and classification settings.

  • Motivation: Static graph representations miss temporal information when interactions evolve over time.Temporal graphs arise in social, citation, question answering, and user-item interaction systems, where treating the final state as static can be inappropriate.
  • Challenges: Temporal embeddings should be functions of continuous time, not only projections of topology and node features.This requires operating beyond an ordinary vector space to represent temporal dynamics.
  • Challenges: Neighborhood aggregation must obey temporal constraints so message-passing paths respect interaction chronology.The appropriate information flow depends on the prediction time rather than solely on graph connectivity.
  • Challenges: Temporal patterns can affect both topology and node features, including diminishing influence from old interactions and recurrent interaction behavior.These patterns should be captured by the node embeddings.
  • Approach: The proposed architecture combines self-attention with Bochner-based functional time encoding to inductively produce time-aware embeddings in one forward pass.It targets embeddings for unseen and observed nodes as temporal graphs evolve.
  • Evaluation: The evaluation covers transductive and inductive future link prediction, dynamic node classification, ablations, and sensitivity analysis.The experiments compare temporal and non-temporal node embeddings and examine the proposed components.

2 RELATED WORK

Related graph representation methods include spectral models conditioned on graph spectra and localized neighborhood-aggregation methods that are not restricted to the training graph. The section also introduces positional encodings and scaled dot-product self-attention as foundations for the paper’s temporal architecture.

  • Graph representation learning: Spectral graph embedding models operate through graph spectral representations and are not directly extendable to temporal graphs.Their training and inference are conditioned on the specific graph spectrum.
  • Graph representation learning: GAT, GraphSAGE, and MoNET use localized neighborhood aggregation and are not restricted to the training graph.GraphSAGE and GAT also provide flexibility for inductive representation learning.
  • Self-attention mechanism: Self-attention combines entity embeddings or features with positional encodings before applying attention.The positional encoding assigns a vector to each sequence position.
  • Self-attention mechanism: Scaled dot-product attention aggregates value representations using weights determined by query-key interactions.Queries, keys, and values are projections of the embedded entity sequence, and the output is a hidden representation.

3 TEMPORAL GRAPH ATTENTION NETWORK ARCHITECTURE

TGAT combines learnable functional time encoding with self-attention to aggregate temporal neighborhoods and model interactions between node features and time. Stacked layers produce time-aware embeddings that support inductive inference for observed and unseen nodes.

  • 3.1 FUNCTIONAL TIME ENCODING: TGAT learns a functional mapping from time into a finite-dimensional vector space, replacing positional encoding in self-attention.The mapping is designed to support differentiable optimization and is compatible with backpropagation.
  • 3.1 FUNCTIONAL TIME ENCODING: Bochner’s theorem represents the continuous translation-invariant temporal kernel through a non-negative measure, enabling its approximation with sampled frequency features.The kernel depends on time differences, and Monte Carlo integration approximates the resulting expectation.
  • 3.2 TEMPORAL GRAPH ATTENTION LAYER: TGAT aggregates temporal-neighborhood representations and timestamps through self-attention, whose query, key, and value projections capture time-feature interactions.The attention mechanism uses relative timespans under the translation-invariant kernel assumption.
  • 3.5 COMPARISONS TO RELATED WORK: The approach directly learns functional time representations instead of snapshot sequences or time-constrained random walks, while jointly modeling temporal-feature interactions.The time encoding is compatible with self-attention and can be optimized with the network parameters.
  • 3.2 TEMPORAL GRAPH ATTENTION LAYER: Stacking TGAT layers extends aggregation from one-hop neighborhoods to L-hop neighborhoods while preserving chronological message-passing order.The architecture supports multi-head attention and does not restrict neighborhood size.
  • 3.5 COMPARISONS TO RELATED WORK: TGAT inference is entirely inductive: explicit time-dependent embeddings can be computed for observed and unseen nodes at any timestamp through a network forward pass.The computations can be parallelized across nodes as the graph evolves.

4 EXPERIMENT AND RESULTS

The experiments evaluate TGAT on transductive and inductive temporal link prediction, dynamic node classification, and ablations across two benchmark and one industrial dataset. TGAT achieves strong results across tasks, with temporal attention and functional time encoding contributing to performance.

  • Experimental setting: TGAT is evaluated on transductive and inductive tasks using two benchmark datasets and one large-scale industrial dataset.The datasets contain temporal interactions, evolving labels, and new nodes or edges.
  • Experimental setting: The experiments use chronological 70%-15%-15% train-validation-test splits based on node interaction timestamps.Future links are predicted after the training observations to preserve temporal constraints.
  • Baselines and tasks: TGAT is compared with graph embedding, temporal, inductive, and temporally adapted attention baselines, including GAE, VGAE, node2vec, DeepWalk, GraphSAGE-LSTM, and GAT.Additional ablations include Const-TGAT, GAT+T, and GraphSAGE+T.
  • Results: TGAT significantly improves inductive accuracy and average precision over upgraded GraphSAGE-LSTM and GAT by at least 5% for both metrics.In transductive learning, TGAT consistently outperforms all baselines across datasets.
  • Results: TGAT’s time-aware embeddings support dynamic node classification, while GAT’s advantage over Const-TGAT indicates that temporal attention weights are useful.The ablation results further indicate that functional time encoding captures temporal signals.
  • Attention analysis: Attention analysis shows less weight for more distant interactions and greater weight for recurring neighbors when predicting farther-future interactions.The authors relate these patterns to the influence of recent and repeated actions on future user interests.

5 CONCLUSION AND FUTURE WORK

The paper concludes that TGAT provides time-aware inductive representation learning for temporal graphs through self-attention and functional time encoding. It also identifies visualization, interpretability, and broader adaptation of the encoding technique as future directions.

  • Conclusion: TGAT combines self-attention with a theoretically grounded functional time encoding to capture temporal-feature signals in node and topological features.The approach is designed for inductive representation learning on temporal graphs.
  • Future work: The authors identify model-interpretation tools and efficient visualization of evolving graph dynamics and temporal representations as future work.They also note potential for adapting functional time encoding to other deep learning methods in temporal graphs.

A.1 PROOF FOR CLAIM 1

The proof establishes a uniform bound for the difference between the learned score and its target kernel over the temporal domain. It uses unbiasedness, translation invariance, finite covering, bounded trigonometric functions, and concentration bounds.

  • Proof strategy: The proof defines the score difference over a bounded temporal interval and seeks a uniform upper bound for it.Translation invariance reduces the dependence to the time difference t1−t2.
  • Proof strategy: The score is treated as an unbiased estimator of the target kernel, allowing the proof to control deviations around the kernel.The proof explicitly uses E[S(t1,t2)] = K(t1,t2).
  • Uniform control: A finite cover of the temporal domain and a bound on the gradient are used to extend pointwise control across the interval.The maximum gradient norm L∆ bounds variation within each covered region.
  • Concentration bound: Hoeffding’s inequality controls deviations at cover points because the trigonometric terms are bounded between −1 and 1.A union bound then combines the events over the finite cover.
  • Final step: The proof applies Markov inequality and then solves the resulting bound to obtain the stated claim.The selected sample size N is substituted back into the bound before solving for d.

A.2 COMPARISONS BETWEEN THE ATTENTION MECHANISM OF TGAT AND GAT

TGAT differs from GAT in both its attention formulation and its treatment of temporal interactions. TGAT uses transformed dot products between hidden factors and time embeddings, whereas GAT uses a parameter vector with LeakyReLU.

  • A.2 COMPARISONS BETWEEN THE ATTENTION MECHANISM OF TGAT AND GAT: GAT uses a parameter vector and LeakyReLU, while TGAT uses linear transformations followed by dot products for attention weights.The two mechanisms therefore compute αij differently.
  • A.2 COMPARISONS BETWEEN THE ATTENTION MECHANISM OF TGAT AND GAT: TGAT’s dot-product attention captures pair-wise interactions between hidden factors and time embeddings.The formulation is tied to the temporal encoding’s kernel-based inner-product decomposition.
  • A.2 COMPARISONS BETWEEN THE ATTENTION MECHANISM OF TGAT AND GAT: Equipping GAT with the same time encoding still yields inferior performance to TGAT across Tables 1, 2, and 3.The comparison concerns the practical performance of the attention mechanisms under shared time encoding.

A.3 DETAILS ON DATASETS AND PREPROCESSING

The experiments use two one-month interaction benchmarks and one industrial customer-product graph, with chronological temporal splits and masked unseen nodes for inductive evaluation. Dataset statistics and edge percentages are reported with approximations where unseen-node sampling affects the counts.

  • A.3 DETAILS ON DATASETS AND PREPROCESSING: Reddit contains 11,000 nodes and around 700,000 timestamped user-subreddit interactions collected over one month.User posts provide 172-dimensional LIWC features.
  • A.3 DETAILS ON DATASETS AND PREPROCESSING: Wikipedia contains approximately 9,300 nodes and around 160,000 timestamped user-page interactions collected over one month.User edits provide 172-dimensional LIWC features and dynamic banned-status labels.
  • A.3 DETAILS ON DATASETS AND PREPROCESSING: The industrial graph contains approximately 170,000 customer and product nodes with around 2 million timestamped purchases over one month.Customers have business labels, while preprocessing maps available features into a 100-dimensional vector space.
  • A.3 DETAILS ON DATASETS AND PREPROCESSING: Graphs are split chronologically into 70%-15%-15% training, validation, and testing periods using edge timestamps.Approximately 10% of nodes are masked during training and treated as unseen through validation and testing.
  • A.3 DETAILS ON DATASETS AND PREPROCESSING: Static baselines use training edges to construct undirected graphs, with recurrent-edge handling and averaged user features adapted by method.GAE and VGAE use averaged post or edit vectors, or all-zero user features for the industrial dataset.
  • A.3 DETAILS ON DATASETS AND PREPROCESSING: Dynamic node classification predicts user bans or customer business labels at different time points, using stratified sampling because of label imbalance.The same temporal training, validation, and testing datasets are used for this downstream task.

A.4 EXPERIMENT SETUP FOR BASELINES

Baseline experiments standardize embedding dimensions and tune method-specific architectures or random-walk settings using validation performance. Temporal and inductive baselines are evaluated with adaptations for temporal subgraph batching and dynamic node classification.

  • A.4 EXPERIMENT SETUP FOR BASELINES: All baselines use node embedding dimension d = 100 for consistency with TGAT.This provides a common representation size across methods.
  • A.4 EXPERIMENT SETUP FOR BASELINES: GAE and VGAE compare one, two, and three graph-convolutional encoder layers with ReLU activations and 200-dimensional hidden layers.Two layers outperform one, while adding a third produces almost identical results for both models.
  • A.4 EXPERIMENT SETUP FOR BASELINES: CTDNE selects temporal random-walk length by validation and adopts uniform temporal edge sampling based on prior findings.A walk length of 80 gives slightly better validation performance in this setup.
  • A.4 EXPERIMENT SETUP FOR BASELINES: GraphSAGE and GAT use temporal subgraph batching, while GraphSAGE is limited to the 20 most recent sampled edges per aggregation layer.This accommodates the fixed-neighborhood design of GraphSAGE while matching the temporal training setting.
  • A.4 EXPERIMENT SETUP FOR BASELINES: Dynamic node classification uses inductively computed current embeddings for GraphSAGE and GAT, whereas transductive baselines combine fixed embeddings with interacting-node embeddings.The resulting embeddings are used as features for classification.

A.5 IMPLEMENTATION DETAILS

The implementation combines official or established software components with PyTorch implementations for temporal GraphSAGE, GAT, and the proposed model. Downstream classification uses a shared MLP training procedure with regularization and early stopping.

  • A.5 IMPLEMENTATION DETAILS: Node2vec, DeepWalk, GAE, and VGAE use official or established implementations, while temporal GraphSAGE, GAT, and TGAT are implemented in PyTorch.The temporal implementations accommodate temporal settings and edge features.
  • A.5 IMPLEMENTATION DETAILS: A three-layer MLP consumes node embeddings for downstream classification across all three datasets.The classifier uses Glorot initialization and the Adam SGD optimizer.
  • A.5 IMPLEMENTATION DETAILS: The ℓ2 regularization parameter λ is selected from {0.001, 0.01, 0.05, 0.1, 0.2}, with early stopping applied during training.Regularization is selected case by case.

A.6 SENSITIVITY ANALYSIS AND EXTRA ABLATION STUDY

Sensitivity analyses find that TGAT is relatively stable across attention-head counts, while two layers improve results over one. Functional-encoding choices have comparable outcomes, but flow-based methods train more slowly; uniform neighborhood dropout slightly outperforms inverse-timespan sampling.

  • Extra ablation study: Flow-based and non-parametric functional-encoding methods achieve highly comparable outcomes, but flow-based methods require longer training.Flow-based models sample during each training batch; carefully tuned versions might improve results, but that possibility remains future work.
  • Sensitivity analysis: Three attention heads and two TGAT layers give the best accuracy and AP, while results remain relatively stable across head counts.Two layers aggregate information from the two-hop neighborhood and significantly improve results over a single layer.
  • Extra ablation study: Uniform neighborhood dropout slightly outperforms inverse-timespan sampling in the ablation study.Inverse-timespan sampling slows training, particularly on large graphs, but may better capture recent interactions for some tasks.
Loading 2002.07962v1…