Distributed Incremental Tensor Tucker Decomposition

With the rapid development of social networks, e-commerce systems, and mobile terminal devices, massive and high-dimensional data is overwhelmingly increasing. A natural representation of high dimensional data is called tensor. Tensor Tucker decomposition is a fundamental machine learning method for multi-dimensional data analysis. Tensor Tucker decomposition aims at discovering the latent representations for the given tensor. It is widely used in many applications, such as recommendation systems, image compression, computer vision, to name but a few. Nevertheless, most traditional tensor decomposition methods could only handle static data, and are not suitable for dynamic data. Because those traditional methods could only re-compute the whole tensor decomposition from scratch whenever data grows. Besides, several incremental tensor Tucker decomposition methods focus on one-mode incremental tensor. However, the tensor in real life could be developed in multiple modes. To our knowledge, there is only one method suitable for multi-mode incremental tensor Tucker decomposition. Nevertheless, all the existing incremental tensor Tucker decomposition methods are designed for the standalone machine, and thus, they cannot handle large-scale dynamic incremental data efficiently. Considering the continuous expansion nature of data, it requires an efficient distributed incremental tensor Tucker decomposition method. Thus, this paper proposes a Distributed Incremental Tensor Tucker Decomposition method (DITTD for short), which is the first attempt to tackle this problem. Towards this, there are two main challenges. The first one is to achieve the load balancing among the workers in the distributed environment. DITTD firstly divides the incremental tensor based on its positional relationship with the previous one. Then, DITTD tries to generate the optimal partitioning result for the incremental tensor, such that the number of non-zero elements in each tensor partition is equal. However, the optimal tensor partitioning problem is proved to be NP-hard. Thus, DITTD utilizes two heuristic tensor partitioning methods to partition the incremental tensor as well as possible. One is the Greedy tensor Partitioning algorithm (GP for short), which greedily assigns partitioning boundaries and makes the number of non-zero elements in each tensor partition to be close to the optimal sum target. The other is the Max-min Matching tensor Partitioning algorithm (M2P), which iteratively assigns the tensor slice with the maximum number of non-zero elements into the tensor partition with the minimum number of non-zero elements. After the tensor partitioning, DITTD meets the second challenge, which is to compute the incremental tensor Tucker decomposition efficiently. DITTD provides a novel incremental Tucker decomposition computation method to avoid the explosion of intermediate data of Tucker decomposition. This method provides an equivalent conversion for the update rule of factor matrices and designs a row-wise computation strategy for the distributed Tucker decomposition. Based on the above-mentioned techniques, DITTD can reduce the computation of intermediate data and the network communication among the workers, and thus, DITTD improves the efficiency of the distributed Tucker decomposition for incremental tensor. Last but not the least, comprehensive experiments are conducted on both real and synthetic data sets. The experimental results show that our proposed method DITTD is at least 10× faster than the baseline method and scale well. © 2021, Science Press. All right reserved.