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 fundamental technique in recommender systems and bioinformatics, used to predict missing values in large, sparse datasets—such as user ratings for movies or gene-protein interactions. To improve performance in highly sparse scenarios, researchers often incorporate "side-information" in the form of a graph. This graph typically encodes prior knowledge about similarities between entities, such as a social network where friends are assumed to have similar tastes.

However, these graphs are frequently "noisy." A social connection does not always imply shared preferences. When a graph edge connects two entities that the primary data suggests are dissimilar, it becomes a contested edge. Forcing a model to respect these edges can degrade prediction accuracy. This paper introduces a scalable probabilistic framework to identify and prune these contested edges dynamically.

The Problem of Contested Edges

Standard graph-regularized MF methods treat the provided side-information as ground truth. If User A and User B are connected in the graph, the model penalizes differences in their latent features. The issue arises when the graph's topology conflicts with the patterns observed in the primary data matrix.

Illustration of contested edges: Users $u_4$ and $u_5$ have opposing rating patterns, making their graph connection "contested" and subject to removal.

As shown in the figure above, while $u_1$ and $u_2$ share similar ratings, $u_4$ and $u_5$ exhibit inverse preferences (e.g., high vs. low ratings for movies $m_4$ through $m_7$). A graph edge between $u_4$ and $u_5$ would mislead the model, whereas the edge between $u_1$ and $u_2$ is consistent with the data.

Methodology: GPMF and GRAEM

The authors propose Graph-based Prior Probabilistic Matrix Factorization (GPMF), a generative model that treats the graph itself as a variable to be optimized. To solve this, they introduce GRAEM (Graph-regularized Alternating EM), which consists of two main steps:

  1. E-Step (Expectation): Estimates latent features by generalizing the state-of-the-art Graph-regularized Alternating Least Squares (GRALS) algorithm. This ensures the method remains computationally efficient and theoretically sound.
  2. M-Step (Maximization): Updates the graph by identifying contested edges. An edge is considered contested if the latent features of the connected nodes show a negative correlation despite the graph suggesting they should be similar.

To maintain scalability for massive datasets, the authors utilize a Graphical Lasso (GLASSO) approximation. By employing sparse Cholesky factorization and thresholding, they can prune edges in $O(N)$ time, where $N$ is the number of non-zero entries. This linear complexity allows the algorithm to handle graphs with millions of nodes and edges.

Experimental Evaluation

The model was evaluated on both synthetic data (to test robustness against controlled noise) and large-scale real-world datasets, including Flixster, Douban, MovieLens 20M, and Yahoo Music (300k nodes, 3M edges).

Key Findings

  • Efficiency and Scalability: The GRAEM algorithm processed the massive Yahoo Music dataset in under ten minutes on a standard laptop. Notably, pruning edges makes the graph sparser, which actually reduces the computational cost of subsequent iterations—an "efficiency paradox" where more complex modeling leads to faster execution.
  • Improved Accuracy: GPMF consistently outperformed non-adaptive methods. For instance, on the Flixster dataset, it achieved an RMSE of 0.8857, significantly better than the 0.9152 achieved by standard GRALS.
  • Robustness to Noise: In experiments with MovieLens 20M, as the initial graph was made noisier (by increasing the number of nearest neighbors), standard methods saw performance degradation. In contrast, GPMF maintained high accuracy by successfully pruning the irrelevant edges.

Conclusion

This work demonstrates that "cleaning" side-information is often more effective than simply regularizing against it. By identifying contested edges through a scalable probabilistic approach, GPMF provides a robust solution for matrix completion tasks where side-information may be unreliable. While the current GLASSO approximation identifies a significant portion of corrupted edges, future research could explore even more refined graph update strategies to further enhance recommendation quality.

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 $\textit{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