Local Matrix Approximation based on Graph Random Walk

How to decompose a large global matrix into many small local matrices has been recently researched a lot for matrix approximation. However, the distance computation in matrix decomposition is a challenging issue, as no prior knowledge about the most appropriate feature vectors and distance measures are available. In this paper, we propose a novel scheme for local matrix construction without involving distance computation. The basic idea is based on the application of convergence probabilities of graph random walk. At first, a user-item bipartite graph is constructed from the global matrix. After performing random walk on the bipartite graph, we select some user-item pairs as anchors. Then another random walk with restart is applied to construct the local matrix for each anchor. Finally, the global matrix approximation is obtained by averaging the prediction results of local matrices. Our experiments on the four real-world datasets show that the proposed solution outperforms the state-of-the-art schemes in terms of lower prediction errors and higher coverage ratios.