Temporal Inductive Logic Reasoning over Hypergraphs

Yuan Yang, Siheng Xiong, Ali Payani, J. Clayton Kerce, Faramarz Fekri, Haoliang Sun, Yongshun Gong

Abstract

Automated reasoning in real-world scenarios often requires handling multi-entity interactions and events with specific durations. Traditional reasoning models, typically based on binary Knowledge Graphs (KGs), fail to capture these higher-order relations and the nuances of time intervals. This paper presents TILR, a novel framework designed for inductive logic reasoning over temporal hypergraphs. By integrating a Multi-start Random B-walk (MRBW) for hypergraph traversal and Allen’s interval algebra for temporal modeling, TILR can learn complex, interpretable logic rules. Experimental results on procedural datasets like YouCook2-HG and nuScenes-HG show that TILR significantly outperforms existing graph-based and logic-based models, providing both superior accuracy and human-readable explanations.

Introduction

Most existing automated reasoning frameworks operate on Knowledge Graphs (KGs), which represent facts as simple binary relations (e.g., Father(Bob, Amy)). However, many real-world processes are inherently more complex. For instance, in a cooking scenario, "mixing onion, garlic, and oil" involves a 3-ary relation that cannot be accurately reduced to binary pairs without losing structural information. Furthermore, events in these processes often have durations—like "sautéing for 5 minutes"—rather than being instantaneous points in time.

To address these challenges, the authors propose representing data as temporal hypergraphs, where edges connect an arbitrary number of nodes and are associated with specific start and end times. The goal is to learn logic rules directly from these structures to predict future events or missing facts.

Methodology: Reasoning on Hypergraphs

The TILR framework introduces several key innovations to enable effective reasoning over temporal hypergraphs:

Multi-start Random B-walk (MRBW)

Standard random walks move sequentially from node to node. In a hypergraph, however, a hyperedge might require multiple "input" nodes to be active before it can be traversed—a concept known as B-connectivity. For example, you cannot perform a "mix" operation until all ingredients are present. The MRBW algorithm maintains a set of active nodes and only "triggers" a hyperedge once all its required head nodes have been collected.

Figure 4: A hypergraph representation of a cooking procedure, showing how multiple ingredients (nodes) are combined through operations (hyperedges) like Mix and Sauté over specific time intervals.

Temporal Interval Algebra

Instead of treating time as discrete points, TILR employs Allen’s Interval Algebra, which defines 13 distinct relations (e.g., Before, Meets, Overlaps, During) to describe how two time intervals interact. This allows the model to learn rules such as "If event A happens during event B, then event C follows," providing a much richer temporal context than simple timestamps.

Differentiable Rule Learning

TILR is formulated as a differentiable model ($TILR_\theta$) that uses a path-consistency algorithm to resolve temporal constraints. It learns to weight the most predictive logic rules using a cross-entropy loss, allowing the system to automatically discover the most important sequences of events for a given task.

Figure 5: Illustration of B-graphs and B-paths. A valid B-path ($R_1, R_3$) requires all source nodes of a hyperedge to be reached before proceeding, whereas an invalid path ($R_2$) fails this condition.

Evaluation and Results

The authors introduced two new benchmarks to evaluate TILR: YouCook2-HG (procedural cooking) and nuScenes-HG (autonomous driving).

Key Findings

  • Performance: On YouCook2-HG, TILR achieved a Mean Reciprocal Rank (MRR) of 0.72, nearly doubling the performance of the best logic-based baseline, Drum (0.40), and significantly outperforming Graph Neural Networks (0.37).
  • Structural Advantage: Reasoning directly on the native hypergraph yielded a 30% improvement over models that "flattened" the data into standard binary graphs.
  • Interpretability: Unlike "black-box" neural models, TILR generates human-readable rules. For example, it can explicitly define the steps for a recipe: Remove layers from onion AND cut onion BEFORE mixing with flour BEFORE frying.

Conclusion

TILR represents a significant advancement in temporal reasoning by treating hypergraphs as a "natural" representation for procedural logic. By enforcing B-connectivity during traversal and utilizing interval algebra, it captures the inherent logic of complex multi-entity events. Future work will focus on extending the model to handle many-to-many hyperedges and improving the automated extraction of predicates from raw data.

Summary updated

BibTeX
@inproceedings{yang2024temporal,
  author = {Yuan Yang and Siheng Xiong and Ali Payani and J. Clayton Kerce and Faramarz Fekri and Haoliang Sun and Yongshun Gong},
  title = {{Temporal Inductive Logic Reasoning over Hypergraphs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=STSv7PXip8},
}
Figure