Matrix Completion on Graphs

Abstract

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ès 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.

Version of NIPS 2014 workshop "Out of the Box: Robustness in High Dimension"

References in corpus (3)

• A Simpler Approach to Matrix Completion
• Structured Variable Selection with Sparsity-Inducing Norms
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise

Cited by in corpus (42)

• Geometric deep learning: going beyond Euclidean data
• Graph Convolutional Matrix Completion
• Sampling Signals on Graphs: From Theory to Applications
• Fast Robust PCA on Graphs
• Deep Models of Interactions Across Sets
• Large Scale Graph Learning from Smooth Signals
• Correlating sparse sensing for large-scale traffic speed estimation: A Laplacian-enhanced low-rank tensor kriging approach
• Sparse Sampling for Inverse Problems with Tensors
• How to learn a graph from smooth signals
• Geometric deep learning on graphs and manifolds using mixture model CNNs
• Dual-Primal Graph Convolutional Networks
• Inductive Matrix Completion Based on Graph Neural Networks
• MC2G: An Efficient Algorithm for Matrix Completion with Social and Item Similarity Graphs
• Matrix Completion with Cross-Concentrated Sampling: Bridging Uniform Sampling and CUR Sampling
• Graph Sampling for Matrix Completion Using Recurrent Gershgorin Disc Shift
• Simultaneous imputation and disease classification in incomplete medical datasets using Multigraph Geometric Matrix Completion (MGMC)
• Orthogonal Inductive Matrix Completion
• Matrix completion and extrapolation via kernel regression
• Multi-dimensional Graph Fourier Transform
• Temporal Graph Signal Decomposition
• Tensor graph convolutional neural network
• On the Unreasonable Effectiveness of Feature propagation in Learning on Graphs with Missing Node Features
• Context-Aware Visual Compatibility Prediction
• Multi-Component Graph Convolutional Collaborative Filtering
• A Graph Signal Processing View on Functional Brain Imaging
• Generalization error bounds for kernel matrix completion and extrapolation
• Functional correspondence by matrix completion
• Spectral Geometric Matrix Completion
• Subspace Least Squares Multidimensional Scaling
• Geometric Matrix Completion: A Functional View
• Matrix Completion With Variational Graph Autoencoders: Application in Hyperlocal Air Quality Inference
• A Harmonic Extension Approach for Collaborative Ranking
• Learning Latent Features with Pairwise Penalties in Low-Rank Matrix Completion
• Low-rank Matrix Completion in a General Non-orthogonal Basis
• Learning Interpretable Disease Self-Representations for Drug Repositioning
• Matrix Decomposition on Graphs: A Functional View
• Going off the Grid: Iterative Model Selection for Biclustered Matrix Completion
• Robust On-line Matrix Completion on Graphs
• Inductive Matrix Completion Using Graph Autoencoder
• Node Attribute Generation on Graphs
• Error Analysis on Graph Laplacian Regularized Estimator
• Community Detection and Matrix Completion with Social and Item Similarity Graphs