# Matrix Completion with Hierarchical Graph Side Information

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 84 references that are in the map.
- First posted on arXiv 2 Jan 2022.

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

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Statistical guarantees for the EM algorithm: From population to sample-based analysis](https://mlsanity.com/paper/1408.2156/) (2014)
- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Phase Retrieval via Wirtinger Flow: Theory and Algorithms](https://mlsanity.com/paper/1407.1065/) (2014)
- [Geometric Matrix Completion with Recurrent Multi-Graph Neural Networks](https://mlsanity.com/paper/1704.06803/) (2017)
- [Exact Recovery in the Stochastic Block Model](https://mlsanity.com/paper/1405.3267/) (2014)
- [Hierarchical Clustering: Objective Functions and Algorithms](https://mlsanity.com/paper/1704.02147/) (2017)
- [Phase Retrieval using Alternating Minimization](https://mlsanity.com/paper/1306.0160/) (2013)
- [Spectral redemption: clustering sparse networks](https://mlsanity.com/paper/1306.5550/) (2013)
- [Community detection thresholds and the weak Ramanujan property](https://mlsanity.com/paper/1311.3085/) (2013)
- [Low-Rank Matrix Completion: A Contemporary Survey](https://mlsanity.com/paper/1907.11705/) (2019)
- [Fast Algorithms for Robust PCA via Gradient Descent](https://mlsanity.com/paper/1605.07784/) (2016)
- [Hierarchical Block Structures and High-resolution Model Selection in Large Networks](https://mlsanity.com/paper/1310.4377/) (2013)
- [Achieving Optimal Misclassification Proportion in Stochastic Block Model](https://mlsanity.com/paper/1505.03772/) (2015)
- [Spectral MLE: Top-K Rank Aggregation from Pairwise Comparisons](https://mlsanity.com/paper/1504.07218/) (2015)
- [Clustering with Same-Cluster Queries](https://mlsanity.com/paper/1606.02404/) (2016)
- [Matrix Completion on Graphs](https://mlsanity.com/paper/1408.1717/) (2014)
- [Minimax Rates of Community Detection in Stochastic Block Models](https://mlsanity.com/paper/1507.05313/) (2015)
- [Community Detection and Classification in Hierarchical Stochastic Blockmodels](https://mlsanity.com/paper/1503.02115/) (2015)
- [Query Complexity of Clustering with Side Information](https://mlsanity.com/paper/1706.07719/) (2017)
- [Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery](https://mlsanity.com/paper/1501.05021/) (2015)
- [Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms](https://mlsanity.com/paper/1412.7335/) (2014)
- [Spectral Clustering via the Power Method -- Provably](https://mlsanity.com/paper/1311.2854/) (2013)
- [Reducing Crowdsourcing to Graphon Estimation, Statistically](https://mlsanity.com/paper/1703.08085/) (2017)
- [Clustering and Inference From Pairwise Comparisons](https://mlsanity.com/paper/1502.04631/) (2015)
- [Density Evolution in the Degree-correlated Stochastic Block Model](https://mlsanity.com/paper/1509.03281/) (2015)
- [Community Recovery in Graphs with Locality](https://mlsanity.com/paper/1602.03828/) (2016)
- [Collaborative Filtering with Social Local Models](https://mlsanity.com/paper/1704.05735/) (2017)

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

- [Taxonomy Tree Generation from Citation Graph](https://mlsanity.com/paper/2410.03761/) (2024)
- [Online Low Rank Matrix Completion](https://mlsanity.com/paper/2209.03997/) (2022)
- [Matrix Completion with Hypergraphs:Sharp Thresholds and Efficient Algorithms](https://mlsanity.com/paper/2401.08197/) (2024)
- [Online Matrix Completion: A Collaborative Approach with Hott Items](https://mlsanity.com/paper/2408.05843/) (2024)
- [Graph-Regularized Low-Rank Matrix Completion by Variable Projection](https://mlsanity.com/paper/2607.09546/) (2026)

## Abstract (arXiv)

We consider a matrix completion problem that exploits social or item similarity graphs as side information. We develop a universal, parameter-free, and computationally efficient algorithm that starts with hierarchical graph clustering and then iteratively refines estimates both on graph clustering and matrix ratings. Under a hierarchical stochastic block model that well respects practically-relevant social graphs and a low-rank rating matrix model (to be detailed), we demonstrate that our algorithm achieves the information-theoretic limit on the number of observed matrix entries (i.e., optimal sample complexity) that is derived by maximum likelihood estimation together with a lower-bound impossibility result. One consequence of this result is that exploiting the hierarchical structure of social graphs yields a substantial gain in sample complexity relative to the one that simply identifies different groups without resorting to the relational structure across them. We conduct extensive experiments both on synthetic and real-world datasets to corroborate our theoretical results as well as to demonstrate significant performance improvements over other matrix completion algorithms that leverage graph side information.