S(3)CMTF: Fast, accurate, and scalable method for incomplete coupled matrix-tensor factorization

How can we extract hidden relations from a tensor and a matrix data simultaneously in a fast, accurate, and scalable way? Coupled matrix-tensor factorization (CMTF) is an important tool for this purpose. Designing an accurate and efficient CMTF method has become more crucial as the size and dimension of real-world data are growing explosively. However, existing methods for CMTF suffer from lack of accuracy, slow running time, and limited scalability. In this paper, we propose S(3)CMTF, a fast, accurate, and scalable CMTF method. In contrast to previous methods which do not handle large sparse tensors and are not parallelizable, S(3)CMTF provides parallel sparse CMTF by carefully deriving gradient update rules. S(3)CMTF asynchronously updates partial gradients without expensive locking. We show that our method is guaranteed to converge to a quality solution theoretically and empirically. S(3)CMTF further boosts the performance by carefully storing intermediate computation and reusing them. We theoretically and empirically show that S(3)CMTF is the fastest, outperforming existing methods. Experimental results show that S(3)CMTF is up to 930× faster than existing methods while providing the best accuracy. S(3)CMTF shows linear scalability on the number of data entries and the number of cores. In addition, we apply S(3)CMTF to Yelp rating tensor data coupled with 3 additional matrices to discover interesting patterns.