# Matrix Completion with Hypergraphs:Sharp Thresholds and Efficient Algorithms

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 51 references that are in the map.
- First posted on arXiv 16 Jan 2024.

## Builds on (most cited first, 15 of 15)

- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [Exact Recovery in the Stochastic Block Model](https://mlsanity.com/paper/1405.3267/) (2014)
- [Hypergraph Contrastive Collaborative Filtering](https://mlsanity.com/paper/2204.12200/) (2022)
- [Contact patterns in a high school: a comparison between data collected using wearable sensors, contact diaries and friendship surveys](https://mlsanity.com/paper/1506.03645/) (2015)
- [Generative hypergraph clustering: from blockmodels to modularity](https://mlsanity.com/paper/2101.09611/) (2021)
- [Multi-Behavior Hypergraph-Enhanced Transformer for Sequential Recommendation](https://mlsanity.com/paper/2207.05584/) (2022)
- [Self-Supervised Hypergraph Transformer for Recommender Systems](https://mlsanity.com/paper/2207.14338/) (2022)
- [Consistency Thresholds for the Planted Bisection Model](https://mlsanity.com/paper/1407.1591/) (2014)
- [Stochastic Block Model for Hypergraphs: Statistical limits and a semidefinite programming approach](https://mlsanity.com/paper/1807.02884/) (2018)
- [Optimal Cluster Recovery in the Labeled Stochastic Block Model](https://mlsanity.com/paper/1510.05956/) (2015)
- [Exact Recovery in the General Hypergraph Stochastic Block Model](https://mlsanity.com/paper/2105.04770/) (2021)
- [Matrix Completion with Hierarchical Graph Side Information](https://mlsanity.com/paper/2201.01728/) (2022)
- [MC2G: An Efficient Algorithm for Matrix Completion with Social and Item Similarity Graphs](https://mlsanity.com/paper/2006.04373/) (2020)
- [Community Recovery in Graphs with Locality](https://mlsanity.com/paper/1602.03828/) (2016)
- [Discrete-Valued Latent Preference Matrix Estimation with Graph Side Information](https://mlsanity.com/paper/2003.07040/) (2020)

## Abstract (arXiv)

This paper considers the problem of completing a rating matrix based on sub-sampled matrix entries as well as observed social graphs and hypergraphs. We show that there exists a sharp threshold on the sample probability for the task of exactly completing the rating matrix -- the task is achievable when the sample probability is above the threshold, and is impossible otherwise -- demonstrating a phase transition phenomenon. The threshold can be expressed as a function of the ``quality'' of hypergraphs, enabling us to quantify the amount of reduction in sample probability due to the exploitation of hypergraphs. This also highlights the usefulness of hypergraphs in the matrix completion problem. En route to discovering the sharp threshold, we develop a computationally efficient matrix completion algorithm that effectively exploits the observed graphs and hypergraphs. Theoretical analyses show that our algorithm succeeds with high probability as long as the sample probability exceeds the aforementioned threshold, and this theoretical result is further validated by synthetic experiments. Moreover, our experiments on a real social network dataset (with both graphs and hypergraphs) show that our algorithm outperforms other state-of-the-art matrix completion algorithms.