Temporal Inductive Logic Reasoning

Yuan Yang, Siheng Xiong, James Clayton Kerce, Faramarz Fekri

Abstract

Reasoning about complex, real-world events requires understanding both multi-entity interactions and the temporal durations over which they occur. Traditional Knowledge Graphs (KGs) often simplify these interactions into binary relations with single timestamps, losing critical context. We present TILR (Temporal Inductive Logic Reasoning), a framework designed to learn interpretable logic rules from temporal hypergraphs. By utilizing a novel random walk algorithm and Allen’s interval algebra, TILR effectively reasons across $n$-ary relations and time intervals, outperforming existing Inductive Logic Programming (ILP) methods on procedural and spatial datasets.

Introduction: The Challenge of Real-World Reasoning

Most automated reasoning systems operate on Knowledge Graphs where data is represented as simple triples (e.g., Subject-Predicate-Object). While effective for static facts, this format is inadequate for dynamic, multi-step processes like cooking or autonomous driving. Two primary limitations exist:

  1. Higher-Order ($n$-ary) Relations: Many actions involve multiple entities simultaneously. For instance, "mixing" requires a bowl, ingredients, and a tool. This necessitates a hypergraph structure where a single hyperedge can connect multiple nodes.
  2. Temporal Intervals: Real-world events have durations. Representing "sautéing" as a single point in time ignores its relationship to concurrent or subsequent actions (e.g., "adding spices during sautéing").
The TILR pipeline extracts temporal hypergraphs from procedural data, such as cooking videos, to enable logic-based reasoning.

Existing ILP tools typically ignore time or "flatten" hypergraphs into standard graphs, which discards the inherent structure of complex interactions.

Methodology: TILR Framework

TILR is a backward-chaining ILP method specifically engineered for temporal hypergraphs. It introduces three core innovations to handle the complexity of $n$-ary temporal data.

Multi-start Random B-walk (MRBW)

In a hypergraph, reaching a target node often requires multiple "input" nodes (B-connectivity). For example, to start a "sauté" event, one needs an onion, oil, and a pan. The MRBW algorithm maintains a set of active nodes and only traverses a hyperedge when all its required head nodes have been visited. This ensures that the learned paths are logically sound within the hypergraph structure.

B-connectivity in hypergraphs requires all head nodes of an edge to be visited for a path to be considered valid.

Temporal Generalization via Allen’s Interval Algebra

Rather than relying on discrete timestamps, TILR employs Allen’s 13 interval relations (e.g., Before, Meets, Overlaps, Contains). This allows the model to learn sophisticated temporal rules, such as: "If Event A starts Event B and Event B is before Event C, then A must be before C."

Path-Consistency and Differentiable Learning

To maintain mathematical rigor across long event chains, TILR incorporates a path-consistency algorithm to prune impossible temporal combinations. The final model, $TILR_\theta$, is differentiable, allowing it to use gradient descent to identify the most significant logic paths for explaining observed data.

Datasets and Evaluation

To evaluate TILR, the authors introduced two new benchmarks:

  • YouCook2-HG: A dataset of 89 recipes mapping $n$-ary steps and time intervals from cooking videos.
  • nuScenes-HG: A dataset derived from autonomous driving data, describing spatial and temporal relationships between vehicles and pedestrians.

Key Results and Insights

TILR demonstrated significant improvements over standard Graph Neural Networks (GNNs) and state-of-the-art ILP methods like NeuralLP and Drum.

  • Accuracy Gains: On the YouCook2-HG dataset, TILR achieved a Mean Reciprocal Rank (MRR) of 0.72, nearly doubling the performance of the best baseline (Drum, 0.40) which operated on flattened data.
  • The Value of Hypergraphs: Reasoning directly on hypergraphs provided a 30% performance boost compared to flattened ordinary graphs, proving that $n$-ary structure preservation is vital.
  • Interpretability: Unlike "black-box" models, TILR generates human-readable first-order logic rules. This transparency allows users to verify the model's reasoning—for example, confirming it identifies a "BLT sandwich" by the specific sequence of putting mayo on bread, adding toppings, and covering it.

Conclusion

TILR represents a significant step forward in temporal reasoning by bridging the gap between symbolic logic and complex graph structures. While currently optimized for B-graphs (many-to-one hyperedges), its success in procedural and spatial domains highlights the importance of preserving $n$-ary relations and temporal intervals in machine learning models.

Summary updated

Abstract

Inductive logic reasoning is one of the fundamental tasks on graphs, which seeks to generalize patterns from the data. This task has been studied extensively for traditional graph datasets such as knowledge graphs (KGs), with representative techniques such as inductive logic programming (ILP). Existing ILP methods typically assume learning from KGs with static facts and binary relations. Beyond KGs, graph structures are widely present in other applications such as video instructions, scene graphs and program executions. While inductive logic reasoning is also beneficial for these applications, applying ILP to the corresponding graphs is nontrivial: they are more complex than KGs, which usually involve timestamps and n-ary relations, effectively a type of hypergraph with temporal events. In this work, we study two of such applications and propose to represent them as hypergraphs with time intervals. To reason on this graph, we propose the multi-start random B-walk that traverses this hypergraph. Combining it with a path-consistency algorithm, we propose an efficient backward-chaining ILP method that learns logic rules by generalizing from both the temporal and the relational data.
BibTeX
@inproceedings{yang2024temporal,
  author = {Yuan Yang and Siheng Xiong and James Clayton Kerce and Faramarz Fekri},
  title = {{Temporal Inductive Logic Reasoning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=STSv7PXip8},
}
Figure