# Matrix Completion on Graphs

arXiv: https://arxiv.org/abs/1408.1717 · HTML: https://mlsanity.com/paper/1408.1717/

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Aug 2014.

## Built on by (most cited first, 26 of 26)

- [On the Unreasonable Effectiveness of Feature propagation in Learning on Graphs with Missing Node Features](https://mlsanity.com/paper/2111.12128/) (2021)
- [Graph Filters for Signal Processing and Machine Learning on Graphs](https://mlsanity.com/paper/2211.08854/) (2022)
- [Spiking Graph Convolutional Networks](https://mlsanity.com/paper/2205.02767/) (2022)
- [Correlating sparse sensing for large-scale traffic speed estimation: A Laplacian-enhanced low-rank tensor kriging approach](https://mlsanity.com/paper/2210.11780/) (2022)
- [Matrix Completion with Cross-Concentrated Sampling: Bridging Uniform Sampling and CUR Sampling](https://mlsanity.com/paper/2208.09723/) (2022)
- [Inductive Matrix Completion Using Graph Autoencoder](https://mlsanity.com/paper/2108.11124/) (2021)
- [Temporal Graph Signal Decomposition](https://mlsanity.com/paper/2106.13517/) (2021)
- [Nonparametric Matrix Estimation with One-Sided Covariates](https://mlsanity.com/paper/2110.13969/) (2021)
- [Matrix Completion with Hierarchical Graph Side Information](https://mlsanity.com/paper/2201.01728/) (2022)
- [Bayesian Low-rank Matrix Completion with Dual-graph Embedding: Prior Analysis and Tuning-free Inference](https://mlsanity.com/paper/2203.10044/) (2022)
- [Combining Explicit and Implicit Regularization for Efficient Learning in Deep Networks](https://mlsanity.com/paper/2306.00342/) (2023)
- [DeMuon: A Decentralized Muon for Matrix Optimization over Graphs](https://mlsanity.com/paper/2510.01377/) (2025)
- [MoReL: Multi-omics Relational Learning](https://mlsanity.com/paper/2203.08149/) (2022)
- [Multilinear Kernel Regression and Imputation via Manifold Learning](https://mlsanity.com/paper/2402.03648/) (2024)
- [Incomplete Graph Learning: A Comprehensive Survey](https://mlsanity.com/paper/2502.12412/) (2025)
- [Matrix Decomposition on Graphs: A Functional View](https://mlsanity.com/paper/2102.03233/) (2021)
- [On the Fundamental Limits of Matrix Completion: Leveraging Hierarchical Similarity Graphs](https://mlsanity.com/paper/2109.05408/) (2021)
- [Scalable unsupervised alignment of general metric and non-metric structures](https://mlsanity.com/paper/2406.13507/) (2024)
- [Graph-Based Matrix Completion Applied to Weather Data](https://mlsanity.com/paper/2306.08627/) (2023)
- [Multi-Channel Hypergraph Contrastive Learning for Matrix Completion](https://mlsanity.com/paper/2411.01376/) (2024)
- [eGHWT: The Extended Generalized Haar-Walsh Transform](https://mlsanity.com/paper/2107.05121/) (2021)
- [Tensor Completion Leveraging Graph Information: A Dynamic Regularization Approach with Statistical Guarantees](https://mlsanity.com/paper/2310.02543/) (2023)
- [Matrix Completion with Graph Information: A Provable Nonconvex Optimization Approach](https://mlsanity.com/paper/2502.08536/) (2025)
- [On the Impact of Downstream Tasks on Sampling and Reconstructing Noisy Graph Signals](https://mlsanity.com/paper/2509.10874/) (2025)
- [GOMA: Toward Structure-Driven Multimodal Alignment from a Graph Signal Smoothing Perspective](https://mlsanity.com/paper/2605.15723/) (2026)
- [Graph-Regularized Low-Rank Matrix Completion by Variable Projection](https://mlsanity.com/paper/2607.09546/) (2026)

## Abstract (arXiv)

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.