Matrix Completion on Graphs

By Vassilis Kalofolias, Xavier Bresson, Michael M. Bronstein, Pierre Vandergheynst. 2014

182 citations recorded by the source corpus.

The problem of finding the missing values of a matrix given a few of its entries, called matrix completion, has gathered a lot of attention in the recent years. Although the problem under the standard low rank assumption is NP-hard, Cand\`es and Recht showed that it can be exactly relaxed if the number of observed entries is sufficiently large. In this work, we introduce a novel matrix completion model that makes use of proximity information about rows and columns by assuming they form communities. This assumption makes sense in several real-world problems like in recommender systems, where there are communities of people sharing preferences, while products form clusters that receive similar ratings. Our main goal is thus to find a low-rank solution that is structured by the proximities of rows and columns encoded by graphs. We borrow ideas from manifold learning to constrain our solution to be smooth on these graphs, in order to implicitly force row and column proximities. Our matrix recovery model is formulated as a convex non-smooth optimization problem, for which a well-posed iterative scheme is provided. We study and evaluate the proposed matrix completion on synthetic and real data, showing that the proposed structured low-rank recovery model outperforms the standard matrix completion model in many situations.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Statistical Learning Theory, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Statistical Learning Theory

In Signal Processing

Citations in the corpus

Geometric Deep Learning on Graphs and Manifolds Using Mixture Model CNNs (2016, methodology): “an operator as a generalization of the Fourier basis. Constructions such as wavelets [14, 18, 21, 39, 45] or algorithms such as dictionary learning [62], Lasso [9], PCA [43, 44], or matrix completion [23] originally developed for the Euclidean domain, were also applied to graph-structured data. Deep”
Geometric Matrix Completion with Recurrent Multi-Graph Neural Networks (2017, methodology): “Geometric matrix completion An alternative relaxation of the rank operator in (1) is to constraint the space of solutions to be smooth w.r.t. some geometric structure of the matrix rows and columns (Ma et al., 2011; Kalofolias et al., 2014; Rao et al., 2015; Benzi et al., 2016).”
Geometric Deep Learning: Going beyond Euclidean data (2016, background): “structure into matrix completion problems [94], [95], [96], [97] in the form of column- and row graphs representing similarity of users and items, respectively (see Figure 4).”
A Harmonic Extension Approach for Collaborative Ranking (2016, methodology): “The weight matrix W plays an important role in our algorithm as well as other graph-based approaches (Zhu et al., 2003; Sarwar et al., 2001; Kalofolias et al., 2014).”
CayleyNets: Graph Convolutional Neural Networks With Complex Rational Spectral Filters (2017, methodology): “[15, 31] 1.653 GMC [16] 0.996 GRALS [26] 0.945 sRGCNN Cheby [24] 0.929 sRGCNN Cayley 0.922 Table 3: Test accuracy of different methods on the CORA dataset.”
Dual-Primal Graph Convolutional Networks (2018, unknown): “MovieLens Flixster Douban Yahoo IMC [22, 45] 1.653 – – – GMC [24] 0.996 – – – MC [9] 0.973 – – – GRALS [39] 0”
Song recommendation with non-negative matrix factorization and graph total variation (2016, methodology): “Collaborative filtering models are known to perform better as more observed ratings are available [9].”
Self-Adaptive Matrix Completion for Heart Rate Estimation from Face Videos under Realistic Conditions (2016, methodology): “In this paper, we were inspired by [16, 15, 1] in modeling the temporal smoothness of the HR signal.”
Fast Robust PCA on Graphs (2015, unknown): “We refer to such models as factorized models .”
How to Learn a Graph from Smooth Signals (2016, methodology): “As the objective functions of both models are proper, convex, and lowersemicontinuous, our algorithms are guaranteed to converge to the minimum (Komodakis and Pesquet 2014).”
Collaborative Filtering with Graph Information: Consistency and Scalable Methods (2015, methodology): “There are some works developing algorithms for the situation with partially observations [12, 26, 27]; however, none of them provides statistical guarantees.”
Deep Models of Interactions Across Sets (2018, unknown): “MC (Cand`es & Recht, 2009) 0.973 GMC (Kalofolias et al., 2014) 0.996 GRALS (Rao et al., 2015) 0.945 sRGCNN (Monti et al., 2017) 0.929 Factorized EAE (ours) 0.920 GC-MC (Berg et al., 2017) 0.910 Self-Supervised Model (ours) 0.910”