Scalable Tucker Factorization for Sparse Tensors - Algorithms and Discoveries

Given sparse multi-dimensional data (e.g., (user, movie, time; rating) for\nmovie recommendations), how can we discover latent concepts/relations and\npredict missing values? Tucker factorization has been widely used to solve such\nproblems with multi-dimensional data, which are modeled as tensors. However,\nmost Tucker factorization algorithms regard and estimate missing entries as\nzeros, which triggers a highly inaccurate decomposition. Moreover, few methods\nfocusing on an accuracy exhibit limited scalability since they require huge\nmemory and heavy computational costs while updating factor matrices. In this\npaper, we propose P-Tucker, a scalable Tucker factorization method for sparse\ntensors. P-Tucker performs alternating least squares with a row-wise update\nrule in a fully parallel way, which significantly reduces memory requirements\nfor updating factor matrices. Furthermore, we offer two variants of P-Tucker: a\ncaching algorithm P-Tucker-Cache and an approximation algorithm\nP-Tucker-Approx, both of which accelerate the update process. Experimental\nresults show that P-Tucker exhibits 1.7-14.1x speed-up and 1.4-4.8x less error\ncompared to the state-of-the-art. In addition, P-Tucker scales near linearly\nwith the number of observable entries in a tensor and number of threads. Thanks\nto P-Tucker, we successfully discover hidden concepts and relations in a\nlarge-scale real-world tensor, while existing methods cannot reveal latent\nfeatures due to their limited scalability or low accuracy.\n