TimeGraphs: Graph-based Temporal Reasoning

Paridhi Maheshwari, Hongyu Ren, Yanan Wang, Rok Sosic, Jure LeskovecarXiv 2024 · DOI · OpenReview

TL;DR

This paper introduces TimeGraphs, a novel hierarchical graph-based approach for temporal reasoning that adaptively focuses computational resources on dynamic events, outperforming traditional sequence-based methods. By constructing a multi-level event hierarchy using self-supervised learning, TimeGraphs efficiently captures complex, unevenly distributed dynamics in real-world systems, achieving state-of-the-art results on various temporal reasoning tasks.

What Problem Does This Paper Address?

Many real-world systems, from sports to traffic, involve complex interactions that evolve over time. Representing and reasoning about these dynamic behaviors is crucial for tasks like event prediction and recognition. Existing methods often rely on simple sequence-based models or graph neural networks that treat all time steps equally. This is inefficient because the dynamics in these systems are rarely uniform; some moments are packed with critical information, while others are relatively static. This uniform processing wastes computational power and can lead to overlooking crucial, fast-paced events or struggling to capture long-term dependencies. The paper aims to address this by developing a method that can adaptively reason across different time scales, focusing on moments of high activity.

Methods

TimeGraphs proposes a novel approach to temporal reasoning by representing dynamic interactions as a hierarchical temporal graph. Instead of processing every time step uniformly, TimeGraphs builds a multi-level event hierarchy.

  1. Input Representation: The input is a sequence of frame-wise scene graphs, capturing entities (players, objects) and their spatial relationships. Temporal edges are added to connect entities across consecutive frames.
  2. Hierarchical Event Model (Self-Supervised Pre-training): A key innovation is the use of a self-supervised graph pooling method called Vertex Infomax Pooling (VIPool). This method learns to identify "supernodes" that maximally represent their local neighborhoods. By optimizing mutual information, VIPool constructs a hierarchy of events, where higher levels abstract more complex patterns. This pre-training is task-agnostic.
  3. Temporal Knowledge Graph Construction: The pre-trained event model is used to build the temporal knowledge graph. Level 0 of the graph consists of the input graphs. Higher levels are formed by creating "supernodes" that aggregate information from lower-level nodes, creating a hierarchical structure. This allows for adaptive reasoning, ascending to higher levels when dynamics are sparse and descending to finer levels when dynamics are dense.
  4. Downstream Task Fine-tuning: The constructed temporal knowledge graph is then used to train a graph neural network (specifically, a relational-GCN in their experiments) for downstream tasks like event prediction and classification. An optional end-to-end training approach is also presented, jointly optimizing the event model and the downstream classifier.

Datasets

The paper evaluates TimeGraphs on several datasets involving complex, dynamic agent interactions:

  • Google Research Football Simulator: Generates full-game football matches with varying team strategies. Input graphs represent players and the ball, with edges based on spatial proximity.
  • Resistance Game: A multi-user social game dataset capturing individual player features (facial actions, speaking) and pairwise probabilities. Graphs represent players and their interactions over rounds.
  • MOMA (Multi-Object Multi-Actor Activity Parsing): A video-based human activity classification dataset with hierarchical annotations (activities, sub-activities, atomic actions). Scene graphs from video frames are used, with temporal edges linking actors/objects across frames.

Key Insights and Ideas

  • Adaptive Reasoning is Key: The core insight is that temporal dynamics are unevenly distributed, and models should adapt their focus accordingly. Uniform processing is inefficient and can miss critical information.
  • Hierarchy Uncovers Latent Structure: Building a hierarchical representation of events allows the model to capture patterns at multiple scales, from short-term interactions to long-term game dynamics.
  • Self-Supervision for Unsupervised Discovery: The use of self-supervised learning (VIPool) to construct the event hierarchy is crucial, as ground truth for higher-level events is often unavailable. This allows the model to autonomously discover meaningful temporal structures.
  • Graphs as a Natural Representation: Temporal sequences of graphs are a powerful way to model complex agent interactions, capturing both spatial and temporal dependencies.

Key Results

  • State-of-the-Art Performance: TimeGraphs achieved state-of-the-art results across all evaluated datasets for event prediction and recognition tasks.
  • Significant Improvement: Performance increases of up to 12.2% (on the EM metric for Resistance games) were observed compared to existing approaches.
  • Efficiency and Robustness: The hierarchical approach leads to more efficient reasoning and demonstrates robustness in scenarios with data sparsity.
  • Zero-Shot Generalization: Experiments suggest TimeGraphs has capabilities for zero-shot generalization.
  • End-to-End Benefits: End-to-end training of the event model and classifier showed improved performance, highlighting the value of the hierarchical event representation as an intermediate step.
  • Ablation Studies: Removing supernodes or temporal edges from the graph structure led to performance degradation, confirming the importance of the hierarchical and temporal components.

Limitations and Future Work

  • Computational Cost of Pre-training: While the approach is efficient for downstream tasks, the self-supervised pre-training of the event model can be computationally intensive.
  • Scalability to Extremely Large Graphs: While the approach is designed to be scalable and incremental, handling extremely large and dense graphs might still pose challenges.
  • Future Work: The authors suggest exploring the application of TimeGraphs to other domains with complex temporal dynamics, such as robotics, recommendation systems, and financial forecasting. Further research could also focus on more advanced self-supervised objectives for hierarchy construction and exploring different graph neural network architectures for downstream tasks.

Summary updated

Abstract

Many real-world systems exhibit temporal, dynamic behaviors, which are captured as time series of complex agent interactions. To perform temporal reasoning, current methods primarily encode temporal dynamics through simple sequence-based models. However, in general these models fail to efficiently capture the full spectrum of rich dynamics in the input, since the dynamics is not uniformly distributed. In particular, relevant information might be harder to extract and computing power is wasted for processing all individual timesteps, even if they contain no significant changes or no new information. Here we propose TimeGraphs, a novel approach that characterizes dynamic interactions as a hierarchical temporal graph, diverging from traditional sequential representations. Our approach models the interactions using a compact graph-based representation, enabling adaptive reasoning across diverse time scales. Adopting a self-supervised method, TimeGraphs constructs a multi-level event hierarchy from a temporal input, which is then used to efficiently reason about the unevenly distributed dynamics. This construction process is scalable and incremental to accommodate streaming data. We evaluate TimeGraphs on multiple datasets with complex, dynamic agent interactions, including a football simulator, the Resistance game, and the MOMA human activity dataset. The results demonstrate both robustness and efficiency of TimeGraphs on a range of temporal reasoning tasks. Our approach obtains state-of-the-art performance and leads to a performance increase of up to 12.2% on event prediction and recognition tasks over current approaches. Our experiments further demonstrate a wide array of capabilities including zero-shot generalization, robustness in case of data sparsity, and adaptability to streaming data flow.
BibTeX
@misc{maheshwari2024timegraphs,
  author = {Paridhi Maheshwari and Hongyu Ren and Yanan Wang and Rok Sosic and Jure Leskovec},
  title = {{TimeGraphs: Graph-based Temporal Reasoning}},
  year = {2024},
  eprint = {2401.03134},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2401.03134},
}
Figure