Streaming Factor Trajectory Learning for Temporal Tensor Decomposition

Summary

In traditional tensor decomposition, the factor of decomposition is static. Therefore, it was not possible to fit time-evolving data well. This paper develops SFTL using a Gaussian process to capture the time-developing trajectory of the factors. Their naive implementation would have increased computational complexity. Therefore, they reduce the computational complexity by replacing the Matern kernel in GP with an SDE.

Strengths

- Standard tensor decomposition can only extract linear patterns. SFTL, however, uses a Gaussian process to extract nonlinear features in the time direction. - Elegant techniques are used to reduce the computational complexity. It is unfortunate that these techniques are not applicable to non-matern kernels, i.e., RBF kernels. - They provide a theoretical discussion of the computational complexity of the proposed method and include additional experimental results in the appendix. - Notation of the symbols is clear and not misleading. The paper is well written. - It is good to have a discussion about the sensitivity of hyperparameters.

Weaknesses

There are some known tricks to reduce the computational complexity of the Gaussian process from O(n^3), such as Inducing Variable Method, Deterministic Training Conditional (DTC) Approximation, and Fully Independent Training Conditional (FITC) Approximation. All of these tricks can be adapted to non-Matern kernels. With these tricks, I think it is possible to achieve fast computations without Hartikainen's elegant tricks. Although the elegant method of this paper is to be evaluated, it is a drawback that there is no comment on this point.

Questions

- I struggled to understand Fig 1. Since there are 3 trajectories in Fig 1, does this correspond to the SFTL for a tensor that has three 3 modes? - In my understanding, the size of vec(z) depends on the rank R, where R is a hyperparameter. In Algorithm 1, R is not included in Input. That point needs to be clarified. - In section 6.1, the word `node` suddenly appears, but I am unclear what this means. My understanding is that the input to the experiment in section 6.1 is a full-rank 2x2 time-evolving matrix with noise, is this correct?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

The authors appropriately mention in the Appendix that the speedup of the proposed method is only applicable to Matern kernels.

Summary

The authors highlight that real-world tensor data often includes time information, representing the timestamps of interactions between objects in different modes. However, most existing decomposition methods for tensors with temporal information only estimate static factors for each object and cannot capture the temporal variation of the factors. To address this limitation, the authors introduce Streaming Factor Trajectory Learning (SFTL), which can efficiently handle data streams and estimate the temporal evolution of objects' representation without storing or re-accessing previous data. They use a Gaussian process (GP) prior to model the factor trajectory of each object as a function of time. GPs are flexible nonparametric function priors that can capture complex temporal dynamics. The factor trajectories are combined using either the CANDECOMP/PARAFAC (CP) or Tucker decomposition to sample the tensor entry values at any given time. The authors evaluate SFTL using both simulation studies and real-world temporal tensor datasets. In the simulation studies, SFTL recovers nonlinear factor trajectories and provides reasonable uncertainty estimation. When applied to real-world datasets for missing value prediction, SFTL consistently outperforms state-of-the-art streaming CP and Tucker decomposition algorithms in both online and final predictive performance. In some cases, SFTL even surpasses the prediction accuracy of recent static decomposition methods that require multiple passes through the dataset. The learned factor trajectories from a real-world dataset also exhibit interesting temporal evolution.

Strengths

The main advantage of this method is its computational efficiency. To overcome the computational challenges of the GP's covariance matrix computation in streaming inference, they employ spectral analysis to convert the GP into a linear time-invariant (LTI) stochastic differential equation (SDE). This conversion enables them to transform the SDE into an equivalent state-space prior over the factor states at observed timestamps, simplifying posterior inference and making it computationally efficient. In addition, they increase the scalability of tensor decomposition as in the following. They leverage the chain structure of the state-space prior and utilize the conditional expectation propagation framework to develop an efficient online filtering algorithm. This algorithm allows for the estimation of a decoupled running posterior of the involved factor states when new entries at a new timestamp arrive. The decoupled Gaussian estimate enables independent and parallel computation of the full posterior of each factor trajectory without revisiting previous data. The method scales linearly with the number of observed timestamps.

Weaknesses

I think the paper is not so clear and it is hard to follow the contribution especially in Section 3 and 4. The simulation study looks fine, but not a big difference is observed between SOTA and the STL on the real-world applications. Besides the real-world applications are not explained, so it is also not clear to understand what are the application areas of this method.

Questions

Can you please explain the real-world applications (we only see the dataset names, but it is not sufficient to understand the application)? Can you also add how much gain you provide with STL compared to baselines, both in efficiency and accuracy, e.g. in percent? Can you please add more explanations to Figure 1? It is not so easy to understand how the overall method works from that figure.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

The authors can discuss more the scalability and the applicability of STL. What are the applications that STL can be used in real-world?

Summary

This paper studies the dynamic tensor factorization under the streaming data setting. In particular, the authors propose to use a state-space Gaussian process (GP) to parameterize the CP or Tucker factors as functions of time. To efficiently learn the GP and handle streaming data, an equivalent SDE and a conditional expectation propagation algorithm are then derived. For experiments, the authors show that the model can learn factor and tensor entry trajectories. Besides, it achieves good competition performance, even compared with model non-streaming settings.

Strengths

1. This work presents the first model that attempts to learn factor trajectories under streaming data setting. 2. The performance of completion is good. Even though the proposed model runs under the online setting, the error is smaller than many models that use the whole dataset.

Weaknesses

1. Although the problem setting is new in the tensor decomposition field, most techniques used in this work seem standard, such as state-space Gaussian process and expectation propagation. 2. The notations are too complex and hard to follow. There are too many super/sub-scripts and sometimes the meanings are unclear. For examples, for latent variables $z$, sometimes, the second subscript is the rank (e.g., in Line 128, $z^m_{j, r}(t)$, where $r$ is the rank). Then, in Line 141, it becomes the time stamp, e.g., $\bar{z}^m_{j, k}$ with $k$ being the time index.

Questions

1. In Equation 9, for the first Gaussian distribution, is the variance missing?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

None

Summary

The work proposes a new approach for the decomposition of a tensor with a temporal dimension. The developed method can apply to streaming data where decomposing the entire tensor from scratch would be prohibitive. The key idea is to model each entry (or parameter) in the decomposition factor as a function of time, thus representing a factor trajectory in time, and to assume that this function is sampled from a Gaussian process. Then, given the factor trajectories, initial tensor values are recovered by sampling from a specific Normal distribution.

Strengths

The paper is well-written and easy to follow. The authors clearly state the necessary background, problem, and notations. The considered problem of handling streaming data is relevant. However, many technical choices were left unjustified.

Weaknesses

The primary concerns are about (implicit) assumptions made in the paper: - Parameters of the decomposition factor are sampled from a GP with the same kernel. That says that the smoothness of the factor trajectories is assumed to be similar. That might be a restrictive assumption on the data the method is applied for, but it is not discussed. - Relates to the previous concern. Continuity in the latent space of the factors translates to the continuity in the space of the initial tensor values that follow from (1). In practice, a slight change in the factors might hugely affect the initial tensor values and vice versa. It would be essential to see the results of the method on more diverse problems, e.g., streaming point cloud data. - Finally, the trade-off between the decomposition rank and sustaining several Gaussian processes (i.e., better modeling of the factors). The rank R used in the experiments is relatively small. Some of the technical choices for the method are not well justified: - why is Gamma distribution used? - how are the hyperparameters of the models chosen? Do the data dictate those, or is there a reason for them? A simple baseline would tackle the problem as a regression task, thus possibly learned by a neural network. It would be great to add it as a baseline.

Questions

- The authors use CP and Tucker decomposition. Why Tensor Train or Tensor Ring decompositions, are not compared to or not used? For example, [1] propose a simple method incorporating temporal component into the decomposition. It is interesting to see the number of parameters comparison, compression time, and quality metrics. [1] T4DT: Tensorizing Time for Learning Temporal 3D Visual Data Mikhail Usvyatsov, Rafael Ballester-Rippoll, Lina Bashaeva, Konrad Schindler, Gonzalo Ferrer, Ivan Oseledets

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

2 fair

Limitations

The limitations arise from the set of assumptions made by the methods. Is this method applicable to the streaming 3D visual data, where the change in scenes might be significant from scene to scene? How the chosen rank R affects the quality, and what is the trade-off for it? These questions are not discussed in the paper though critical for the method to be applicable in practice.

what did you think of the authors' response?

The authors have provided a detailed response. Has it sufficiently addressed your concerns about their choice of priors and hyperparameters? If so, please revise your score and review to address it, and please acknowledge that you have read the authors' carefully written response regardless.

acknowledge and discuss the authors' detailed response

The authors have provided a detailed response, which includes new experimental results more exposition of the technical material. *Drop a comment in this thread with how their response changed your perspective on the submission.* Remember to also update your scores/reviews to reflect how your views have changed in light of the authors' response.