Abstract
In matrix factorization, available graph side-information may not be well suited for the matrix completion problem, having edges that disagree with the latent-feature relations learnt from the incomplete data matrix. We show that removing these contested edges improves prediction accuracy and scalability. We identify the contested edges through a highly-efficient graphical lasso approximation. The identification and removal of contested edges adds no computational complexity to state-of-the-art graph-regularized matrix factorization, remaining linear with respect to the number of non-zeros. Computational load even decreases proportional to the number of edges removed. Formulating a probabilistic generative model and using expectation maximization to extend graph-regularised alternating least squares (GRALS) guarantees convergence. Rich simulated experiments illustrate the desired properties of the resulting algorithm. On real data experiments we demonstrate improved prediction accuracy with fewer graph edges (empirical evidence that graph side-information is often inaccurate). A 300 thousand dimensional graph with three million edges (Yahoo music side-information) can be analyzed in under ten minutes on a standard laptop computer demonstrating the efficiency of our graph update.
Introduction
Matrix Factorization (MF) is a cornerstone of modern recommender systems and data restoration. To address the extreme sparsity of real-world datasets, researchers frequently incorporate Side Information (SI), typically represented as a graph where edges denote similarities between entities. However, these graphs are often noisy or task-irrelevant; for instance, social connections do not always translate to shared consumer preferences.
Standard graph-regularized methods treat these external graphs as ground truth, forcing latent features to align with potentially "contested" edges. This paper introduces GPMF (Graph-based Prior Probabilistic Matrix Factorization), a method that dynamically identifies and prunes these contested edges. By treating the graph as a flexible prior rather than a fixed constraint, GPMF improves both prediction accuracy and computational scalability.
Methodology: GPMF and GRAEM
The authors propose a probabilistic generative model that places Gaussian priors over latent feature matrices, with the prior's precision matrix linked to the graph's Laplacian. Optimization is achieved through GRAEM (Graph-regularized Alternating EM).
The core innovation lies in the M-step, where the algorithm identifies edges corresponding to negative correlations between latent features. To maintain efficiency, the authors utilize a Graphical Lasso (GLASSO) approximation. By assuming column-wise independence and employing sparse Cholesky factorization, the graph update remains $O(N)$ relative to the number of non-zero entries. This ensures that the identification and removal of edges adds no additional computational complexity and actually reduces the load in subsequent iterations by simplifying the graph.
Experimental Evaluation
GPMF was benchmarked against state-of-the-art methods, including GRALS and KPMF, across synthetic and large-scale real-world datasets such as Flixster, Douban, and Yahoo Music.
Key Results
- Accuracy through Pruning: Removing contested edges consistently improved RMSE. On the Douban dataset, GPMF achieved the lowest RMSE (0.7497). In several experiments, the model pruned up to 55% of the provided edges to achieve optimal results.
- Robustness to Noise: While standard methods like GRALS can underperform compared to simple MF when graph quality is low, GPMF is robust. It prunes low-quality graphs until performance is at least equivalent to standard Probabilistic Matrix Factorization (PMF).
- Scalability: The method demonstrated remarkable efficiency, analyzing the Yahoo Music dataset (300,000 dimensions and 3 million edges) in under ten minutes on a standard laptop.
Conclusion
GPMF demonstrates that in the context of side-information, "less is more." By using latent features as a "truth filter" for noisy external graphs, the model achieves superior accuracy. The efficient GLASSO approximation ensures that this robustness is achieved without sacrificing the linear scalability required for massive real-world applications. Future work will explore applying this contested-edge logic to deep learning-based matrix completion architectures.
Summary updated