Matrix Completion via Factorizing Polynomials
This work addresses the challenge of data sparsity in real-world recommendation systems by leveraging implicit higher-order interactions, offering an incremental improvement over prior matrix factorization methods.
The paper tackles the problem of predicting unobserved entries in sparse matrices for recommendation systems by incorporating higher-order implicit information from graph transition probabilities, resulting in a method that outperforms existing approaches using explicit side information, second-order implicit information, and sometimes deep neural networks.
Predicting unobserved entries of a partially observed matrix has found wide applicability in several areas, such as recommender systems, computational biology, and computer vision. Many scalable methods with rigorous theoretical guarantees have been developed for algorithms where the matrix is factored into low-rank components, and embeddings are learned for the row and column entities. While there has been recent research on incorporating explicit side information in the low-rank matrix factorization setting, often implicit information can be gleaned from the data, via higher-order interactions among entities. Such implicit information is especially useful in cases where the data is very sparse, as is often the case in real-world datasets. In this paper, we design a method to learn embeddings in the context of recommendation systems, using the observation that higher powers of a graph transition probability matrix encode the probability that a random walker will hit that node in a given number of steps. We develop a coordinate descent algorithm to solve the resulting optimization, that makes explicit computation of the higher order powers of the matrix redundant, preserving sparsity and making computations efficient. Experiments on several datasets show that our method, that can use higher order information, outperforms methods that only use explicitly available side information, those that use only second-order implicit information and in some cases, methods based on deep neural networks as well.