Bayesian Continuous-Time Tucker Decomposition

Shikai Fang, Akil Narayan, Robert M. Kirby, Shandian ZheICML 2022 · OpenReview

Tensor decomposition is a dominant framework for multiway data analysis and prediction. However, while practical data often contains timestamps for observed entries, existing tensor decomposition approaches struggle to model these temporal dynamics effectively. Bayesian Continuous-Time Tucker Decomposition (BCTT) is a novel framework that treats the "core" of a tensor as a continuous, time-varying function. By leveraging the connection between Gaussian Processes (GPs) and Stochastic Differential Equations (SDEs), BCTT achieves the flexibility of non-parametric modeling with the efficiency of linear-time inference, significantly outperforming traditional discrete-time or rigid parametric approaches.

The Challenge of Temporal Multiway Data

Multiway interaction data—such as a triplet of (user, item, store)—is ubiquitous across e-commerce, social networks, and academia. Crucially, these interactions happen at specific points in time. Existing tensor decomposition methods usually handle time in one of three suboptimal ways:

  1. Ignoring it: Treating the data as a single static snapshot.
  2. Binning: Grouping timestamps into crude buckets (e.g., "weeks" or "months"), which ignores dynamics happening within those buckets.
  3. Rigid Parametrics: Using simple functions like polynomial splines, which often fail to capture complex, non-linear shifts in behavior.

The core challenge is building a model flexible enough to capture any temporal pattern, yet efficient enough to handle large-scale datasets without falling into the $O(N^3)$ computational complexity trap of standard Gaussian Processes.

The BCTT Framework

BCTT extends the classical Tucker Decomposition. In a standard Tucker model, a large tensor is decomposed into factor matrices (representing nodes or entities) and a "core" tensor that defines how those factors interact. BCTT introduces several key innovations to make this dynamic:

Time-Varying Core: Instead of a static core, BCTT models each element of the tensor core as a function of time, $w(t)$, governed by a Gaussian Process prior. This allows the model to capture how the relationships between entities evolve, rather than just the entities themselves.

GP to SDE Transformation: To avoid the massive computational cost of GPs, the authors represent the temporal GP as a Linear Time-Invariant (LTI) Stochastic Differential Equation (SDE). This mathematical pivot transforms the problem into a state-space model (a Gaussian Markov chain).

Message Passing Inference

Message-Passing Inference: Because the state-space model is linear, the authors can use efficient message-passing techniques. As shown in the figure above, the inference scheme utilizes Kalman filtering for forward passes and RTS smoothing for backward passes. To handle the complex coupling between the static factors and the dynamic core, they employ Expectation Propagation (EP) combined with Conditional Moment Matching. This ensures the algorithm scales linearly—$O(N)$—with the number of observations.

Key Insights and Results

The authors evaluated BCTT on synthetic data and three real-world benchmarks: MovieLens100K (user-movie ratings), AdsClick (mobile ad clicks), and DBLP (bibliographic records).

  • Interactions, Not Just Factors, Change: Most dynamic models only let the latent factors change over time. BCTT allows the rules of interaction (the core) to change. For example, a user's general interest in a category might remain stable, but the market's trend for specific items within that category shifts.
  • Exact Inference via SDEs: By using the SDE representation, BCTT performs "full" GP inference. Unlike many "Sparse GP" methods that rely on approximations to save time, BCTT gets the benefits of the full kernel without the prohibitive $O(N^3)$ cost.
  • Interpretability: Despite being non-parametric, the model remains highly interpretable. Practitioners can visualize the continuous trajectories of specific interactions to see exactly when structural changes occur.
Time-Varying Core Trajectory

Empirically, BCTT consistently outperformed state-of-the-art baselines—including continuous-time CP models and RNN-based dynamic models—across all datasets in terms of Root Mean Square Error (RMSE) and Mean Absolute Error (MAE). Furthermore, on the DBLP dataset, BCTT successfully visualized a shift in the tensor core from "homogeneous" interactions to "heterogeneous" clusters, reflecting the increasing specialization of research topics over a decade.

Limitations and Future Directions

While powerful, BCTT has a few limitations. The current implementation focuses primarily on continuous observations (like ratings). While extending it to binary clicks or counts is theoretically straightforward, those specific likelihoods require further implementation. Additionally, Tucker decomposition's core size grows exponentially with the number of modes ($R^K$). While BCTT is highly efficient regarding the number of observations ($N$), very high-dimensional tensors with many modes might still face a "curse of dimensionality" regarding the core size.

Future work could explore integrating BCTT with deep learning architectures or utilizing non-stationary kernels within the SDE framework to better capture "bursty" or abrupt temporal changes.

Summary updated

Abstract

Tensor decomposition is a dominant framework for multiway data analysis and prediction. Although practical data often contains timestamps for the observed entries, existing tensor decomposition app...
BibTeX
@inproceedings{fang2022bayesian,
  author = {Shikai Fang and Akil Narayan and Robert M. Kirby and Shandian Zhe},
  title = {{Bayesian Continuous-Time Tucker Decomposition}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=Hluc0AcJNH},
}
Figure