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:
- 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.
- 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").
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.
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