Learning Temporal Attention in Dynamic Graphs with Bilinear Interactions

Boris Knyazev, Carolyn Augusta, Graham W. TaylorarXiv 2019 · OpenReview

Abstract

Reasoning about graphs evolving over time is a challenging concept in many domains, such as bioinformatics, physics, and social networks. We consider a common case in which edges can be short term interactions (e.g., messaging) or long term structural connections (e.g., friendship). In practice, long term edges are often specified by humans. Human-specified edges can be both expensive to produce and suboptimal for the downstream task. To alleviate these issues, we propose a model based on temporal point processes and variational autoencoders that learns to infer temporal attention between nodes by observing node communication. As temporal attention drives between-node feature propagation, using the dynamics of node interactions to learn this key component provides more flexibility while simultaneously avoiding issues associated with human-specified edges. We also propose a bilinear transformation layer for pairs of node features instead of concatenation, typically used in prior work, and demonstrate its superior performance in all cases. In experiments on two datasets in the dynamic link prediction task, our model often outperforms the baseline model that requires a human-specified graph. Moreover, our learned attention is semantically interpretable and infers connections similar to actual graphs.

Introduction

In many real-world scenarios, graphs are not static; they evolve dynamically. Consider a social network where users exchange messages (short-term events) while maintaining stable friendships (long-term associations). Most existing models for dynamic graphs rely on human-specified edges to define this long-term structural backbone. However, manual labeling is both expensive and potentially suboptimal for specific predictive tasks—for instance, a "friendship" label might not be the most accurate predictor of future communication patterns.

The model learns to infer temporal attention (bottom) by observing a sequence of discrete interaction events (top).

This research addresses two primary limitations in current dynamic graph modeling: the dependency on manual structural labels and the limited expressiveness of standard feature interaction methods. By inferring the underlying "true" graph structure from observed interactions and employing more sophisticated feature fusion, the proposed model offers a more flexible and accurate approach to dynamic link prediction.

Methodology

The proposed framework builds upon DyRep, which utilizes temporal point processes to model graph evolution. Two major innovations are introduced: the Latent Dynamic Graph (LDG) and Bilinear Interaction Layers.

Latent Dynamic Graph (LDG)

Instead of relying on a fixed, human-provided adjacency matrix, the model employs an encoder inspired by Neural Relational Inference (NRI). This encoder performs two passes of node-to-edge and edge-to-node mappings to infer a "temporal attention" matrix ($S^t$). This matrix represents a learned, evolving graph that governs how information propagates between node embeddings over time.

System architecture comparing the baseline DyRep approach with the proposed LDG model, highlighting the update mechanisms for node embeddings and temporal attention.

Bilinear Interaction Layers

Standard models typically combine node features by simple concatenation ($[z_u, z_v]$). This research replaces concatenation with a bilinear form ($z_u^T \Omega z_v$) in both the encoder and the conditional intensity function. This allows for multiplicative interactions across all dimensions of node embeddings, providing a richer representation of node compatibility and relationship strength.

The model is trained using a Variational Autoencoder (VAE) approach. The learned attention is regularized against a prior (uniform or sparse) using Kullback-Leibler (KL) divergence, ensuring the inferred structure remains manageable and interpretable.

Experimental Evaluation

The model was evaluated on two real-world dynamic datasets:

  1. Social Evolution: Tracks the daily interactions (SMS, calls, proximity) of 83 students, paired with survey-based "friendship" labels.
  2. GitHub: A larger dataset involving 284 users and their technical interactions (forks, pushes, commits). This dataset tests the model's ability to handle sparse associations and high-frequency communication.

Key Results

  • Social Evolution: The Bilinear DyRep using the "CloseFriend" graph achieved a Mean Average Rank (MAR) of 11.0, significantly better than the 16.0 achieved by the standard concatenation version. Notably, the LDG (learned sparse) model achieved a competitive MAR of 12.7 without requiring any human labels.
  • GitHub: The improvement was more pronounced. The baseline DyRep yielded a MAR of 100.3, whereas the LDG model—augmented with bilinear interactions and a frequency bias—reduced this to 43.0.
  • Hits@10: On the Social Evolution dataset, the bilinear model improved the probability of the true event appearing in the top 10 predictions from 47% to 59%.

Discussion and Insights

The experiments yield several critical insights. First, learned structure can outperform human labels, as seen in the GitHub results where the inferred attention was more predictive than the "Follow" network. Second, bilinear forms are consistently superior to concatenation, likely because they capture complex non-linear relationships that additive concatenation misses.

Furthermore, the learned temporal attention ($S^t$) demonstrated semantic interpretability. In the Social Evolution dataset, the model "discovered" social structures that closely mirrored the actual "CloseFriend" network, despite having no access to those labels during training.

Limitations and Future Work

While effective, the NRI-style encoder's complexity—requiring all-pairs interaction considerations—may limit scalability to very large graphs. Additionally, while "frequency bias" (predicting links based on past interaction frequency) is a strong baseline, it may be overoptimistic during sudden network shifts. Future work will explore more efficient encoders and better integration of long-term habits with short-term dynamics, as well as extending the model to predict specific interaction types.

Summary updated

Abstract

Reasoning about graphs evolving over time is a challenging concept in many domains, such as bioinformatics, physics, and social networks. We consider a common case in which edges can be short term interactions (e.g., messaging) or long term structural connections (e.g., friendship). In practice, long term edges are often specified by humans. Human-specified edges can be both expensive to produce and suboptimal for the downstream task. To alleviate these issues, we propose a model based on temporal point processes and variational autoencoders that learns to infer temporal attention between nodes by observing node communication. As temporal attention drives between-node feature propagation, using the dynamics of node interactions to learn this key component provides more flexibility while simultaneously avoiding issues associated with human-specified edges. We also propose a bilinear transformation layer for pairs of node features instead of concatenation, typically used in prior work, and demonstrate its superior performance in all cases. In experiments on two datasets in the dynamic link prediction task, our model often outperforms the baseline model that requires a human-specified graph. Moreover, our learned attention is semantically interpretable and infers connections similar to actual graphs.
BibTeX
@misc{knyazev2019learning,
  author = {Boris Knyazev and Carolyn Augusta and Graham W. Taylor},
  title = {{Learning Temporal Attention in Dynamic Graphs with Bilinear Interactions}},
  year = {2019},
  eprint = {1909.10367},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1909.10367},
}
Figure