Scalable Probabilistic Matrix Factorization with Graph-Based Priors

Jonathan Strahl, Jaakko Peltonen, Hiroshi Mamitsuka, Samuel Kaski

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).

Illustration of a rating matrix and the corresponding graph side-information. Contested edges (e.g., between $u_4$ and $u_5$) are identified and removed to improve model fidelity.

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.

Performance comparison of GPMF against baselines across various synthetic experimental settings: (a) graph fidelity, (b) observation noise, (c) data sparsity, and (d) latent dimensionality.

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

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.
BibTeX
@inproceedings{strahl2020scalable,
  author = {Jonathan Strahl and Jaakko Peltonen and Hiroshi Mamitsuka and Samuel Kaski},
  title = {{Scalable Probabilistic Matrix Factorization with Graph-Based Priors}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=KQn2dkfVzrk},
}
Figure