Matrix Completion on Graphs

Introduction

How to reconstruct signals exactly from very few measurements? This central question in signal processing has been extensively studied in the last few years and has triggered a fast emerging field of research, namely compressed sensing. Exact recovery from few measurements is actually possible if the signal is sparse in some representation domain. A related essential question has been recently considered for matrices: is it possible to reconstruct matrices exactly from very few observations? It appears that exact recovery is also possible in this setting if the matrix is low-rank. The problem of low-rank recovery from sparse observations is referred as the matrix completion problem. Several important real-world problems can be cast as a matrix completion problem, including remote sensing , system identification and recommendation systems . Throughout the paper, we will consider the recommendation system problem as an illustration of the matrix completion problem. Such systems have indeed become very common in many applications such as movie or product recommendation (e.g. Netflix, Amazon, Facebook, and Apple). The Netflix recommendation system tries to predict ratings of movies never seen by users. Collaborative filtering is widely used today to solve this problem , inferring recommendations by finding similar rating patterns and using them to complete missing values. This is typically a matrix completion problem where the unknown values of the matrix are computed by finding a low-rank matrix that fits the given entries.

How much information is needed for the exact recovery of low-rank matrices? In the case of random uniformly sampled entries without noise, Candès and Recht showed in that, to guarantee perfect recovery, the number of observed entries must be larger than $cn^{1.2}r\log n$ for $n\times n$ matrices of rank $r$ (this bound has been refined more recently, see and references therein). The case of noisy observations was studied in , while a non-uniform sampling setting was considered in . In this work, we propose to use additional information about rows and columns of the matrix to further improve the matrix completion solution.

In the standard matrix completion problem, rows and columns are assumed to be completely unorganized. However, in many real-world problems like the Netflix problem, there exist relationships between users (such as their age, gender, hobbies, education, etc) and movies (such as their genre, release year, actors, origin country, etc). This information can be taken advantage of, since people sharing the same tastes for a class of movies are likely to rate them similarly. We make use of graphs to encode relationships between users and movies and we introduce a new reconstruction model called matrix completion on graphs. Our main goal is to find a low-rank matrix that is structured by the proximities between users and movies. Introducing structure in sparse recovery problems is not new in the literature of compressed sensing , while similar structure inducing regularization has been proposed for factorized models for matrix completion . Yet, introducing structures via graphs in the convex low-rank matrix recovery setting is novel to the best of our knowledge. We note that a large class of recommendation systems, called content-based filtering, use graphs and clustering techniques to make predictions . Along this line, our proposed methodology can be seen as a hybrid recommendation system that combines collaborative filtering (low-rank property) and content-based filtering (graphs of users and movies).

Original matrix completion problem

The problem of matrix completion is to find the values of an $m\times n$ matrix $M$ given a sparse set $\Omega$ of observations $M_{ij}:(i,j)\in\Omega\subseteq\{1,\ldots,m\}\times\{1,\ldots,n\}$. Problems of this kind are often encountered in collaborative filtering or recommender system applications, the most famous of which is the Netflix problem, in which one tries to predict the rating that $n$ users (columns of $M$) would give to $m$ films (rows of $M$), given only a few ratings provided by each user. A particularly popular model is to assume that the ratings are affected by a few factors, resulting in a low-rank matrix. This leads to the rank minimization problem

Under the assumption that $M$ is sufficiently incoherent, if the indices $\Omega$ are uniformly distributed and $|\Omega|$ is sufficiently large, the minimizer of (2) is unique and coincides with the minimizer of (1) . If in addition the observations are contaminated by noise, one can reformulate problem (2) as

Matrix completion on graphs

Low rank implies the linear dependence of rows/columns of $M$. However, this dependence is unstructured. In many situations, the rows/columns of matrix $M$ possess additional structure that can be incorporated into the completion problem in the form of a regularization. In this paper, we assume that rows/columns of $M$ are given on vertices of graphs. In the Netflix example, the users (columns of $M$) are the vertices of a “social graph” whose edges represent e.g. friendship or similar tastes relations. Thus, it is reasonable to assume that connected users would give similar movie ratings, i.e., interpreting the ratings as an $m$-dimensional vector-valued function on the $n$ vertices of the social graph, such a function would be smooth.

Low rank promoted by the nuclear norm implies sparsity in the space of outer products of the singular vectors, i.e., in the singular value decomposition $X=\sum_{k}\sigma_{k}u_{k}v_{k}^{\top}$ only a few coefficients $\sigma_{i}$ are non-zero. Recent works proposed imposing additional structure constraints, considering matrices that are simultaneously low-rank (i.e., sparse in the space of singular vectors outer products) and sparse (in the original representation). Our regularization can also be considered as a kind of simultaneously structured model. The column smoothness prior (4) makes the rows of $X$ be close to the eigenvectors of the column graph Laplacian $L_{c}$, i.e., each row of $X$ can be expressed as a linear combination of a few eigenvectors of $L_{c}$. This can be interpreted as row-wise sparsity of $X$ in the column graph Laplacian eigenbasis. Similarly, the row smoothness prior results in column-wise sparsity of $X$ in the row graph Laplacian eigenbasis. Overall, the whole model (5) promotes simultaneous sparsity of $X$ in the singular vectors outer product space, and row/column-wise sparsity in the respective Laplacian eigenspaces.

Optimization

Algorithm. Problems like (5) containing non-differential terms cannot be tackled efficiently with a direct approach, while proximal based methods can be applied. We use the Alternating Direction Method of Multipliers (ADMM) that has seen great success recently (other choices could include f.e. fast iterative soft thresholding ) by first introducing the equivalent splitting version of (5)

Eventually the convergence of the proposed ADMM algorithm (7)-(9) can be studied (and likely proved) with different mathematical approaches, for example .

Computational complexity. The overall complexity of the algorithm is dominated by the computation of the nuclear proximal solutions by SVD, whose complexity is $O(mn^{2})$ per iteration for $m>n$ . The computational complexity of the CG algorithm is $O(kmn)$ for $k$-NN graphs.

Numerical experiments

We start the evaluation of our matrix recovery model with a synthetic Netflix-like dataset, to study the behavior of model under controlled conditions. The artificial dataset $M$ is generated such that if fulfills two assumptions: (1) $M$ is low-rank and (2) its columns and rows are respectively smooth w.r.t. the column graph $G_{c}$ and the row graph $G_{r}$. Figure 1(a) shows our synthetic dataset. It is inspired by the problem of movie recommendations as elements of $M$ are chosen to be integers from $\{1\ldots 5\}$ like in the Netflix prize problem. The matrix in Fig. 1(a) is noiseless, showing the ideal ratings for each pair of user and movie groups.

The row graph $G_{r}$ of the matrix $M$ is constructed as follows. The rows of $M$ are grouped into $10$ communities of different sizes. We connect nodes within a community using a $3$-nearest neighbors graph and then add different amounts of erroneous edges, that is, edges between vertices belonging to different communities. The erroneous edges form a standard Erdős-Rényi graph with variable probability. We follow the same construction process for the column graph $G_{c}$ that contains $12$ communities. For both graphs, binary edge weights are used. The intuition behind this choice of graphs is that users form communities of people with similar taste. Likewise, movies can be grouped according to their type, so that movies of the same group obtain similar ratings. The users graph is depicted in Fig 1(b), where nodes of the same community are clustered together. Note that matrix $M$ in Fig. 1(a) has rank equal to the minimum of user communities and the movie communities, in this case $10$.

Two standard assumptions often made in the literature on matrix completion are that the observed elements of the matrix are sampled uniformly at random, and that the reconstructed matrix is perfectly low-rank (the case that we call noiseless). Noiseless case. We test the performance of our method in this setting, comparing it to the standard nuclear norm-based matrix completion (a particular case of our problem with $\gamma_{c}=\gamma_{r}=0$) and to a method that uses only the graphs ($\gamma_{n}=0$). We reconstruct the matrix $M$ using different levels of observed values and report the reconstruction root mean squared error (RMSE) on a fixed set of $35\%$ of the elements that was not observed. The result is depicted in Fig 2(a). We use graphs with $10\%$, $20\%$, and $30\%$ of erroneous edges. Noisy graphs alone (green lines) perform poorly compared to the nuclear norm reconstruction (blue line). However, when we use both graphs and nuclear norm (red lines), we obtain results that are better than any of the two alone.

Noisy case. We add noise to $M$ using a discretized Laplacian distribution. This type of noise models the human tendency to impulsively over- or under-rate a movie. In this case, the matrix that we try to reconstruct is close to low-rank, and the nuclear norm is still expected to perform well. As we see in Fig. 2(b) though, if we have high-quality graphs (green line with $10\%$ erroneous edges), we can expect the same reconstruction quality of the nuclear norm regularization by using just half of the number of observations and only with the graph smoothness terms (green dashed line), that computationally is much cheaper to run. In this figure, the dashed black line designates the level of added noise in the data. Note also that even if we use connectivity information of relatively bad quality (green dashed line with $30\%$ wrong edges), we can still benefit by combining the smoothness and the low-rank regularization terms (solid red line). Therefore the combination of nuclear and graph is robust to graph construction errors for low levels of observation. However, when the observation level is high enough ($>50\%$ for this specific size of matrices - note that this number may vary significantly depending on the matrix size), this benefit is lost (solid red line) and the nuclear norm regularizer (blue line) works better without the graph smoothness terms.

Non-uniform sampling. As noted in , the pattern of the observed values in real datasets does not usually follow a uniform distribution. In fact, the observations are such that the rating frequencies of users and movies closely follow power law distributions. In our experiment, we assume a simple generative process where users and movies are independently sampled from a power law, that is $pr\left(\textrm{sample}\{i,j\}\right)=1/ij$. This is a very sparse distribution with fixed expected number of observations, so we repeat this process identically $s$ times in order to control the overall density. Our final sampling is the logical OR operator of all these $s$ ‘epochs’, that follows the distribution $p\left(\{i,j\}\in\Omega\right)=1-\left(1-1/ij\right)^{s}.$ We find that this simple sampling scheme gives results close to the actual ratings of real datasets such as the MovieLens 10M that we use in the following. The results of our experiments for this setting are summarized in Fig. 3(a). Not surprisingly, all methods suffer from the non-uniformity of the sampling distribution. Still, the nuclear norm (blue line) crosses the line of a high-quality graph ($10\%$ green line) only after $35\%$ observations, while in the uniform case, Fig. 2(a), this happened for less than $20\%$ observed values. A similar behavior is exhibited for the noisy case, Fig. 3(b). There, the nuclear norm regularization quality is better than the medium-quality graph ($20\%$ green line) only for more than $45\%$ observations, while in the uniform case, Fig. 2(b), the corresponding percentage was $25\%$.

2 Movielens dataset

In this section, we report experiments on real data, which appear consistent with the results on the aforementioned artificial data. We work with the widely used MovieLens 10M dataset , containing ratings (‘stars’) from $0.5$ to $5.0$ (increments of $0.5$) given by 71,567 users for 10,677 movies. The density of the observations is $1.31\%$. In our experiments, we use a $500\times 500$ subset of the original matrix for the reconstruction evaluation. This serves two purposes: firstly, we can choose an arbitrary density of the submatrix, and secondly, we can use ratings outside of it as features for the construction of the column and row graphs, as detailed below (see Figure 4(a)). Furthermore, the effect of non-uniformity is weaker. The density of the observations is selected as follows. We sort the rows (users) and columns (movies) by order of increasing sampling frequency (Figure 4(b)). Then, users and movies are chosen to be close to the $99$-th and $95$-th percentile of their corresponding distributions.Since the number of movies in the full matrix is much smaller than the number of users, we keep more frequently rating users in order to have a dense features matrix when we create the users graph. The resulting $500\times 500$ matrix has $39.4\%$ observed values that correspond to the ratings that a user has given to a movie. After a row and column permutation, the original MovieLens 10M matrix $A$ is partitioned in blocks $A=[M,F_{u};F_{m},R]$, where $M$ is the $500\times 500$ matrix that we use for our experiments (Figure 4(a)). We treat $F_{u}$ as the users feature matrix, $F_{m}$ as the movies feature matrix and discard the remaining matrix $R$.

Results. We apply a standard cross-validation technique to evaluate the quality of our completion algorithm. For this purpose, the $39.4\%$ observations of the $500\times 500$ matrix are split into a fixed test set ($7.4\%$) and a varying size training set (from $1\%$ to $32\%$). We perform $5$-fold cross validation to select the parameters $\gamma_{n}$, $\gamma_{r}$ and $\gamma_{c}$ of our model (5) and only use the test set to evaluate the performance of the final models.

The recommendation error results are plotted in Fig. 5(b). The behavior of the algorithms is similar to the one exhibited by the noisy artificial data above (medium quality of graphs). For most observation levels our method combining nuclear norm and graph regularization (red line) clearly outperforms the rest. There are however two boundary phases that are noteworthy. When very few observations are available ($1\%$) there seems to be no benefit in adding the expensive nuclear norm term in the optimization problem, as the graph regularization alone (green line) performs best. On the other hand, for very dense observation levels ($32\%$) the nuclear norm (blue line) reaches the performance of the combined model. In general our combined model is very robust to observation sparsity, while the standard nuclear norm model performs worse even than the much cheaper graphs-only model for up to $8\%$ observations.

Conclusion

The main message of this work is that the standard low-rank matrix recovery problem can be further improved using similarity information about rows and columns. We solve an optimization problem seeking a low-rank solution that is structured by the proximity between rows and columns that form communities. As an application, our matrix completion model offers a new recommendation algorithm that combines the traditional collaborative filtering and content-based filtering tasks into one unified model. The associated convex non-smooth optimization problem is solved with a well-posed iterative ADMM scheme, which alternates between nuclear proximal operators and approximate solutions of linear systems. Artificial and real data experiments are conducted to study and validate the proposed matrix recovery model, suggesting that in real-life applications where the number of available matrix entries (ratings) is usually low and information about products and people taste is available, our model would outperform the standard matrix completion approaches. Specifically, our model is robust to graph construction and to non-uniformly sampling of observations. Furthermore, it significantly outperforms the standard matrix completion when the number of observations is small. The proposed matrix recovery algorithm can be improved in several ways. The effect of the non-uniformity of sampling matrix entries, as discussed in Sections 3 and 5.2, can be partially alleviated using a special weighting of the nuclear norm . The non-uniform sampling of user data points and movie data points from the corresponding manifolds, which influences the quality of graph Laplacians, can also be corrected using special graph normalizations . Furthermore, the optimization algorithm can be improved, firstly in terms of speed by using enhanced iterative schemes like . Secondly in terms of scalability, either by using distributed schemes like or by carrying out techniques from the recent work , which deals with nuclear norm for matrices with sizes much bigger than the Netflix dataset.

References