Decomposing Temporal High-Order Interactions via Latent ODEs

Shibo Li, Robert M. Kirby, Shandian ZheICML 2022 · OpenReview

TL;DR

THIS-ODE is a novel framework that uses latent Ordinary Differential Equations (ODEs) to model high-order interactions (e.g., user-product-store) over continuous time. By parameterizing the time derivative with a neural network and utilizing a clever "time alignment" trick for computational efficiency, it captures complex, non-linear dynamics far better than traditional tensor decomposition methods. This approach leads to state-of-the-art accuracy, particularly in long-term predictions.

The Challenge of Temporal High-Order Interactions

In the real world, interactions between multiple objects—such as a customer buying a specific item at a particular store—do not happen in a vacuum; they occur at specific moments in time. Analyzing these "high-order interactions" is typically the domain of tensor decomposition, which learns low-dimensional embeddings for each object to predict future behavior.

However, most existing methods struggle to properly incorporate the "time" dimension. They generally fall into one of three traps:

  1. Ignoring time entirely, resulting in static models.
  2. Binning time into discrete steps (e.g., "Week 1", "Week 2"), which loses fine-grained detail and fails to handle irregular timestamps.
  3. Using simple functions (like linear trends or polynomial splines) that are too rigid to capture messy, non-linear realities like heart rate fluctuations or environmental changes.

The authors aim to bridge this gap by creating a model that treats interaction results as continuous trajectories governed by underlying physical or behavioral laws.

Methods: Introducing THIS-ODE

The authors propose THIS-ODE (Temporal High-order Interaction decompoSition via Latent ODEs).

The Core Model

Instead of predicting a static value, the result of an interaction $i$ at time $t$, denoted as $m_i(t)$, is modeled as the solution to an ODE:

$$\frac{dm_i(t)}{dt} = f(m_i(t), \mathbf{v}_i, t)$$

Here, $\mathbf{v}_i$ represents the embeddings of the participating objects. The key innovation is using a Neural Network (NN) to represent the derivative function $f$. This allows the model to learn virtually any complex temporal dynamic directly from the data. The initial state $m_i(0)$ is also determined by the object embeddings.

Graphical representation of THIS-ODE

Computational Efficiency

Solving ODEs for every interaction in a large dataset is computationally expensive. The authors introduce two main technical optimizations to make THIS-ODE scalable:

  • Forward Sensitivity Analysis: To train the model, gradients are required. While many Neural ODE papers use the "adjoint method," the authors demonstrate that because their interaction states are scalars (dimension $d=1$), forward sensitivity is just as efficient and much easier to implement.
  • Time Alignment via Integral Transform: In a typical mini-batch, interactions happen at different times ($t_1, t_2, \dots$). Normally, you would have to solve the ODE separately for each unique timestamp. The authors use a mathematical transformation to "stretch" or "shrink" time for each interaction so they all effectively end at the same point ($t_e=1$). This allows them to solve the entire mini-batch as one large, parallelized system on a GPU.

Key Insights

  • Embeddings as "Physical Constants": By making the ODE's behavior dependent on object embeddings, the model forces those embeddings to capture the "essence" of how an object influences temporal change. For example, a "fast" exercise type would have an embedding that results in a high derivative for heart rate.
  • Continuous is Better than Discrete: The failure of "binning" becomes obvious in extrapolation (predicting the future). Discrete models cannot easily generalize beyond the time steps they have seen, whereas an ODE defines a continuous law that can be projected forward indefinitely.
  • The Scalar Advantage: The choice of forward sensitivity over the adjoint method is a great example of choosing the right tool for the specific dimensionality of the problem, rather than blindly following popular deep learning trends.

Datasets and Key Results

The model was evaluated on one synthetic benchmark (Spiral Interactions) and four diverse real-world datasets: Fit Record (heart rate), Beijing Air (pollutants), Server Room (temperature), and Indoor Condition (humidity/temperature).

THIS-ODE consistently outperformed ten state-of-the-art baselines, including GP-based and RNN-based tensor models.

  • Synthetic Accuracy: On the spiral task, THIS-ODE achieved an RMSE of 0.0148 for interpolation, compared to 0.1004 for the next best neural baseline (NTF-Time).
  • Qualitative Recovery: THIS-ODE almost perfectly overlaps with the ground-truth spiral, even in "extrapolation" zones where no training data existed. Baselines like GPTF-Time completely lose the trajectory.
Recovered spirals in interpolation and extrapolation
  • Real-World Performance: Across all four real-world datasets, THIS-ODE provided the lowest error. In the "Server Room" temperature prediction task, it often reduced the error by more than 50% compared to traditional temporal tensor methods.

Limitations and Future Work

While highly effective, THIS-ODE has a few limitations:

  • Computational Overhead: Even with time alignment, solving ODEs is slower than simple matrix multiplications. The time complexity scales linearly with the number of integration steps required by the solver.
  • State Independence: Currently, the model assumes the trajectory of one interaction is independent of others (except through shared embeddings). Future work could explore "coupled" ODEs where one interaction event triggers changes in another.
  • Uncertainty: The current model provides point estimates. Integrating Stochastic Differential Equations (SDEs) could help quantify prediction uncertainty in the future.

Summary updated

Abstract

High-order interactions between multiple objects are common in real-world applications. Although tensor decomposition is a popular framework for high-order interaction analysis and prediction, most...
BibTeX
@inproceedings{li2022decomposing,
  author = {Shibo Li and Robert M. Kirby and Shandian Zhe},
  title = {{Decomposing Temporal High-Order Interactions via Latent ODEs}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=6iX-1XoVRL},
}
Figure