Matrix Completion from Power-Law Distributed Samples

Raghu Meka, Prateek Jain, Inderjit S. DhillonNeurIPS 2009 · OpenReview

Overview

This paper introduces Information Cascading Matrix Completion (ICMC), a novel algorithm designed to solve the low-rank matrix completion problem when data is sampled according to "power-law" distributions. These skewed patterns are typical of real-world datasets like Netflix or Yahoo Music. Unlike traditional methods that assume uniform sampling, ICMC leverages a graph-theoretic "infection" process to recover missing entries faster and more accurately on realistic, non-uniform networks.

The Problem: Uniform vs. Power-Law Sampling

Matrix completion is the mathematical art of filling in the blanks of a massive table—such as a user-movie ratings matrix—based on only a few known entries. This relies on the assumption that the underlying structure is "low-rank," meaning a small number of latent factors explain most of the data.

Most theoretical breakthroughs in this field rely on a critical assumption: that the known entries are sampled uniformly at random. In graph theory terms, they assume the sampling pattern looks like an Erdős-Rényi random graph.

However, real-world data is rarely uniform. A few popular movies receive millions of ratings, while the vast majority receive almost none. This creates a "power-law" distribution where a few "hubs" (high-degree nodes) dominate the network.

Power-law distributions in real-world datasets

Existing algorithms often struggle with these skewed distributions, either requiring far more data than necessary or failing to converge efficiently.

The ICMC Method: An "Infection" Cascade

The authors propose ICMC, which treats matrix completion as a cascading process on a bipartite graph. The approach can be broken down into a few intuitive steps:

  1. The Infection Metaphor: Imagine a few rows of the matrix are "infected" (their values are known).
  2. Spreading the Knowledge: If a column has at least $k$ edges (known entries) connecting to infected rows, we can set up a system of linear equations to solve for that column's latent factors. Once solved, that column also becomes "infected."
  3. Iterative Recovery: The process then flips: newly infected columns help solve for uninfected rows. This "cascade" continues until the entire matrix is recovered.
  4. Refinement: To handle real-world noise, the authors use regularized least squares instead of simple linear solvers, providing a fallback to Alternating Least Squares (ALS) for any nodes the cascade fails to reach.

The beauty of this approach is its simplicity. While traditional methods use complex convex optimization (like trace-norm minimization), ICMC reduces the problem to solving local linear systems, making it computationally inexpensive.

Key Insights and Results

The authors evaluated ICMC using both synthetic data (Erdős-Rényi, Chung-Lu-Vu, Preferential Attachment, and Forest-Fire models) and real-world data (the Netflix Prize and Yahoo Music datasets).

  • Hubs are Assets, Not Liabilities: In uniform sampling, every node is equally helpful. In power-law graphs, "hubs" act as super-spreaders of information, allowing the "infection" to cover the matrix much faster.
  • Graph Structure Matters: This is one of the first methods to explicitly exploit the link structure of the sampling graph rather than treating the missing entries as a generic optimization constraint.
  • Worst-Case Uniformity: Interestingly, the "standard" Erdős-Rényi (uniform) graph is actually the worst-case scenario for this algorithm because it lacks the high-degree hubs that drive the cascade.
RMSE comparison across different random graph models

As shown in the synthetic evaluations, ICMC consistently achieves significantly lower Root Mean Square Error (RMSE) than state-of-the-art methods like Singular Value Thresholding (SVT) and Spectral Matrix Completion (SMC) on power-law models (CLV, PA, Forest-Fire). Conversely, it performs poorly on the uniform Erdős-Rényi model.

When applied to the massive Netflix dataset, ICMC (at rank 20) achieved a comparable error rate to the popular ALS method but was ~40x faster (1,590 seconds vs. 61,500 seconds). Furthermore, the authors provide a theoretical proof that ICMC achieves exact recovery for the CLV model with an optimal number of entries.

Limitations and Future Work

While highly efficient for specific data structures, ICMC has limitations:

  • Sensitivity to Uniformity: The algorithm thrives on "clumpiness" and performs poorly on perfectly uniform graphs compared to trace-norm methods.
  • Noise and Rank: While regularization helps handle noise, a very high level of noise or a poorly estimated rank ($k$) can stall the cascade.
  • Initialization: The algorithm requires a good starting set of "infected" nodes. While using high-degree nodes is a practical heuristic, finding the absolute optimal starting set is an NP-hard problem.

Ultimately, the authors suggest using ICMC as a "warm start" for other optimization methods, combining its incredible speed with the fine-tuned accuracy of gradient-based approaches.

Summary updated

Abstract

The low-rank matrix completion problem is a fundamental problem with many important applications. Recently, Candes & Recht, Keshavan et al. and Candes & Tao obtained the first non-trivial theoretical results for the problem assuming that the observed entries are sampled uniformly at random. Unfortunately, most real-world datasets do not satisfy this assumption, but instead exhibit power-law distributed samples. In this paper, we propose a graph theoretic approach to matrix completion that solves the problem for more realistic sampling models. Our method is easier to analyze than previous methods with the analysis reducing to computing the threshold for complete cascades in random graphs, a problem of independent interest. By analyzing the graph theoretic problem, we show that our method achieves exact recovery when the observed entries are sampled from the Chung-Lu-Vu model, which can generate power-law distributed graphs. We also hypothesize that our algorithm solves the matrix completion problem from an optimal number of entries for the popular preferential attachment model and provide strong empirical evidence for the claim. Furthermore, our method is easier to implement and is substantially faster than existing methods. We demonstrate the effectiveness of our method on examples when the low-rank matrix is sampled according to the prevalent random graph models for complex networks and also on the Netflix challenge dataset.
BibTeX
@inproceedings{meka2009matrix,
  author = {Raghu Meka and Prateek Jain and Inderjit S. Dhillon},
  title = {{Matrix Completion from Power-Law Distributed Samples}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2009},
  url = {https://openreview.net/forum?id=S14QKLZ_-r},
}
Figure