Source-linked AI summary
Matrix Completion on Graphs
Vassilis Kalofolias, Xavier Bresson, Michael Bronstein, Pierre Vandergheynst
TL;DR
Matrix completion seeks to recover missing matrix entries from sparse observations, but standard low-rank recovery can struggle with non-uniform sampling. The paper combines low-rank nuclear-norm recovery with graph smoothness over rows and columns, and reports improved performance over standard matrix completion in many synthetic and real-data settings.
Problem
Matrix completion must recover missing entries from sparse observations, while standard formulations rely on sampling conditions that can be unrealistic, including problematic non-uniform patterns.
Method
The method encodes row and column proximities as graphs, adds graph-smoothness regularization to low-rank recovery, and solves the resulting convex non-smooth problem with an iterative ADMM scheme.
Results
Experiments on synthetic and real data show that the structured low-rank model outperforms standard matrix completion in many situations.
Takeaways & Limitations
Combining collaborative filtering with content-based graph information provides a unified recommendation model that can improve matrix recovery.
Takeaways & Limitations
The approach remains bounded by assumptions and unresolved scope: pathological sampling patterns can be unhandled, and convergence of the proposed ADMM algorithm is presented as a subject for further study.
Abstract
from arXiv · showhide
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.
1 Introduction
Matrix completion extends compressed sensing to recovering low-rank matrices from sparse observations. This paper adds row and column proximity information, encoded by graphs, to improve structured recovery.
- Matrix completion asks whether a matrix can be exactly reconstructed from few observations when it is low-rank.
- Classical results show exact low-rank recovery under sufficiently many uniformly sampled observations, with bounds involving matrix size and rank.For n × n matrices of rank r, the stated bound exceeds cn^1.2r log n.
- The proposed model uses additional information about relationships among rows and columns to improve matrix completion.
- Graphs encode row and column relationships, encouraging a low-rank solution structured by user and movie proximities.
- Manifold-learning ideas impose graph smoothness, yielding a convex non-smooth optimization problem with an associated iterative solver.The paper evaluates the method on synthetic and real data.
2 Original matrix completion problem
Standard matrix completion recovers missing entries by combining sparse observations with a low-rank assumption, but its guarantees rely on sampling conditions that can be unrealistic in practice.
- Matrix completion infers an m × n matrix from a sparse set of observed entries, commonly modeling ratings as low-rank.This formulation appears in collaborative filtering and recommender systems.
- The NP-hard rank-minimization formulation is commonly replaced by nuclear-norm minimization.The nuclear norm is the convex surrogate based on the singular values of X.
- Under incoherence and sufficiently large uniform sampling, nuclear-norm minimization uniquely recovers the rank-minimization solution.
- With noisy observations, the formulation adds a data-fidelity loss to nuclear-norm regularization, and the reconstruction error can be bounded by the noise norm.
- Uniform sampling is unrealistic: unequal rating frequencies can sharply worsen observation requirements, while missing an entire row or column cannot be handled.Weighted nuclear norms can improve performance under non-uniform sampling, but pathological patterns remain unsupported.
3 Matrix completion on graphs
Matrix completion on graphs augments low-rank structure with smoothness over row and column graphs. Graph Dirichlet regularization encodes proximity information while retaining a structured recovery formulation.
- Low rank captures linear dependence among rows and columns but does not represent their additional relational structure.
- The proposed model represents matrix rows and columns on weighted graphs whose edges encode relationships such as friendship or similar tastes.
- Graph Laplacians and Dirichlet seminorms measure smoothness for columns and rows, respectively.These smoothness terms are added as regularizers to the matrix completion problem.
- The resulting regularization can be viewed as combining low-rank structure with additional graph-based structure.
- Column smoothness encourages matrix rows to align with combinations of a few eigenvectors of the column-graph Laplacian.
4 Optimization
The proposed matrix-completion optimization uses ADMM to split the convex non-smooth problem into subproblems that can be solved exactly or approximately. Nuclear-norm minimization uses singular-value thresholding, while the graph-regularized update requires solving a linear system.
- ADMM: ADMM splits the convex non-smooth optimization problem and does not require exact solutions for its iterative subproblems.The method introduces an equivalent splitting and uses an augmented Lagrangian to handle the equality constraint.
- Convergence: Convergence of the proposed ADMM algorithm can be studied, and likely proved, using different mathematical approaches.The passage presents convergence as an analyzable property rather than supplying a completed proof.
- Sub-optimization problems: The X-update minimizes a nuclear-norm objective and has a closed-form singular-value soft-thresholding solution.The update applies softγn/ρ to the singular values obtained from the SVD of the current matrix.
- Sub-optimization problems: The Y-update incorporates observed entries and graph Laplacian regularization, producing a linear system in vec(Y).The system combines the observation operator, row and column Laplacians, and the ADMM penalty term.
- Sub-optimization problems: The resulting system matrix is symmetric positive semidefinite, allowing conjugate gradients to compute a fast approximate solution.The positive-semidefinite structure follows from the Kronecker products of positive-semidefinite matrices.
- Computational complexity: The algorithm’s per-iteration complexity is dominated by nuclear proximal computations, with O(mn^2) complexity for m > n, while CG costs O(kmn) on k-NN graphs.These complexity bounds describe the main SVD and graph-solver costs separately.
5 Numerical experiments
Experiments on synthetic and MovieLens data evaluate graph-regularized matrix completion under uniform and non-uniform sampling. Combining nuclear-norm and graph-smoothness terms generally improves recovery, with benefits depending on graph quality and observation density.
- Synthetic ‘Netflix’ dataset: The synthetic Netflix-like matrix is low-rank, graph-smooth, and constructed from row and column communities with controlled erroneous edges.Rows form 10 communities and columns form 12 communities; within-community 3-nearest-neighbor edges are augmented with cross-community erroneous edges.
- Recovery quality versus number of observations: Under uniform sampling, combining graph smoothness with nuclear-norm regularization outperforms either nuclear-norm or graph-only recovery across tested graph-error levels.Evaluation uses RMSE on a fixed 35% held-out set and graphs containing 10%, 20%, or 30% erroneous edges.
- Recovery quality versus number of observations: With noisy observations, high-quality graphs can match nuclear-norm recovery using half as many observations, while combined regularization remains useful with moderately erroneous graphs at low observation levels.For the tested matrix size, the combined method loses its advantage above 50% observations, where nuclear-norm regularization performs better alone.
- Recovery quality versus number of observations: Under non-uniform sampling, all methods suffer, but nuclear-norm recovery is surpassed by a high-quality graph only after 35% observations.The sampling scheme independently draws users and movies from power-law distributions and repeats the process to control density.
- Movielens dataset: MovieLens experiments use a 500 × 500 submatrix with graph features derived from ratings outside the submatrix and construct graphs using shared-rating distances.The graphs use an ϵ-neighborhood with Gaussian edge weights; the reported reconstruction evaluation uses a 39.4% observed submatrix split into training and test sets.
- Movielens dataset: On MovieLens, the combined model generally performs best, graph regularization alone is best at 1% observations, and nuclear norm matches the combined model at 32%.The evaluation uses 5-fold cross-validation for parameter selection and a fixed 7.4% test set.
6 Conclusion
The work improves standard low-rank matrix recovery by incorporating similarity information about rows and columns, using a unified graph-structured model and an iterative solver.
- Similarity information about rows and columns further improves standard low-rank matrix recovery.
- The model seeks a low-rank solution structured by row and column proximities that form communities.
- The approach combines collaborative filtering and content-based filtering in one recommendation model.
- A convex non-smooth optimization problem is solved with a well-posed iterative ADMM scheme using nuclear proximal operators and approximate linear-system solutions.
- Experiments on artificial and real data suggest improved performance, robustness to graph construction, and robustness to non-uniform observation sampling.