Robust matrix completion for discrete rating-scale data

• Toulouse Business School, Toulouse, France [a.archimbaud@tbs-education.fr]

• Erasmus University Rotterdam, Rotterdam, The Netherlands [alfons@ese.eur.nl]

• Maastricht University, Maastricht, The Netherlands [i.wilms@maastrichtuniversity.nl]

Keywords: Latent low-rank regularization – Missing data – Outliers – Recommender systems – Surveys.

1 Introduction

In recent years, there has been significant interest in matrix completion. The goal of matrix completion aims to predict the unknown entries of a partially observed matrix using its known elements, typically enforcing a low-rank constraint, while minimizing a specific criterion such as the mean squared error. Although common applications feature discrete rating-scale data, such as user-product rating matrices in recommender systems or surveys in the social and behavioral sciences, methods for matrix completion are almost always designed for and studied in the context of continuous data. Furthermore, only a small subset of the literature considers matrix completion in the presence of corrupted observations despite their common occurrence in practice. Examples include attacks on recommender systems (i.e., malicious users deliberately manipulating ratings to influence the recommender system to their advantage), or careless respondents in surveys (i.e., respondents providing answers irrespective of what the survey asks of them due to a lack of attention).

To fill these gaps, we introduce a novel matrix completion algorithm that is tailored towards the discrete nature of rating-scale data and robust to the presence of corrupted observations. Furthermore, we investigate the performance of our proposed method and several competing approaches through simulation studies using discrete rating-scale (rather than continuous) data and under various missing data mechanisms and types of corrupted observations. Our working paper version of this work is available in Archimbaud et al. [2024] and our implementation in the add-on package rdmc [Alfons and Archimbaud, 2024] for the statistical computing environment R [R Core Team, 2024]. The main part of the code is thereby written in C++ to improve computational efficiency.

2 A robust procedure for discrete matrix completion

2.1 Notations

Suppose that we observe an incomplete rating matrix $X$ of $n$ rows (representing individuals providing the ratings) and $p$ columns (representing the rated items) with elements $X_{ij}\in {𝒞}_j=\{c_1^j,\mathrm{\dots },c_K^j\}\subset ℝ$, where $K$ denotes the number of discrete rating categories and for $j=1,\mathrm{\dots },p$. Let $\mathrm{\Omega }$ denote the index set of observed entries in $X$ and define the projection $P_{\mathrm{\Omega }}$ to be the $(n\times p)$-dimensional matrix whose elements are given by

2.2 Problem definition

The general problem consists on finding a $(n\times p)$-dimensional matrix $L$ such that:

$$L_{i,j}=X_{i,j}$$

for all $(i,j)\in \mathrm{\Omega }$.

To solve this problem, the sparsity or low-rank matrix assumption is essential, otherwise it is not possible to find a solution. The rank minimization problem, without knowing the rank information, can be written such as:

Solving this general problem with this rank constraint is NP-hard since the rank function is non differentiable. Usual approaches use surrogate functions for the rank as for example the convex relaxation via the nuclear norm.

In order to address both of the main drawbacks of the popular matrix completion methods, we want to add a discrete constraint as in Huang et al. [2013] and generalize the $l_1$ norm to a (pseudo-)norm based on a robust loss function $\rho$ (see also Tang and Guan [2020]):

$\underset{L}{\min }$ ${||P_{\mathrm{\Omega }}(X)-P_{\mathrm{\Omega }}(L)||}_{\rho }+\lambda {||L||}_{*}$

subject to $L_{i,j}\in 𝒟$

with $𝒟=c_1,\mathrm{\dots },c_K$.

However, this problem might not have any solution because both the rank constraint and the discrete constraint are not necessarily fulfilled simultaneously. To resolve this issue, an ancillary continuous matrix $Z$ can be introduced such that the discreteness constraint operates on $L$ and the nuclear norm constraint on $Z$, while ensuring that $L$ and $Z$ remain as close as possible. Putting all of this together, we obtain the following optimization problem in augmented Lagrangian form:

$\underset{L,Z}{\min }$

subject to $L_{i,j}\in 𝒟$

where ${⟨\cdot ,\cdot ⟩}_F$ denotes the Frobenius inner product, $\mathrm{\Theta }$ is a multiplier adjusting for the discrepancy between $L$ and $Z$, and $\mu$ is an additional regularization parameter.

3 Results and conclusion

We conduct an extensive simulation study in a comprehensive framework to investigate the performance of our proposed method compared with median imputation and the widely-used procedure Soft-Impute [Mazumder et al., 2010, Hastie et al., 2015]. We also include variants of those methods that discretize the obtained predictions to the given rating scale. We focus our analysis under various types of corrupted observations and different type of missingness mechanisms (missing completely at random - MCAR - or not at random - MNAR). To perform this evaluation, we propose to go beyond the standard metrics such as the root mean squared error which are not well suited for evaluation on discrete data, nor data containing corrupted observations.

Results demonstrate that the proposed method protects well against corrupted observations—such as attacks with fake user profiles on recommender systems or careless respondents in surveys—while paying only a small price in terms of performance in the absence of corrupted observations. Two empirical applications further highlight the practical relevance of the method. In addition, we contribute to the literature by providing an analysis that is fully reproducible and based only on open-source software, addressing the recent call for this by LeBlanc et al. [2024] and following the best practices mentioned in Ekstrand et al. [2011].