Matrix Completion With Hypergraphs: Sharp Thresholds and Efficient Algorithms

Zhongtian Ma, Qiaosheng Zhang, Zhen Wang
Proceedings of the Third Learning on Graphs Conference, PMLR 269:34:1-34:30, 2025.

Abstract

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 \ast sharp threshold\ast 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 \textasciigrave \textasciigrave quality”of hypergraphs, enabling us to \ast quantify\ast 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v269-ma25a, title = {Matrix Completion With Hypergraphs: Sharp Thresholds and Efficient Algorithms}, author = {Ma, Zhongtian and Zhang, Qiaosheng and Wang, Zhen}, booktitle = {Proceedings of the Third Learning on Graphs Conference}, pages = {34:1--34:30}, year = {2025}, editor = {Wolf, Guy and Krishnaswamy, Smita}, volume = {269}, series = {Proceedings of Machine Learning Research}, month = {26--29 Nov}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v269/main/assets/ma25a/ma25a.pdf}, url = {https://proceedings.mlr.press/v269/ma25a.html}, abstract = {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 \ast sharp threshold\ast 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 \textasciigrave \textasciigrave quality”of hypergraphs, enabling us to \ast quantify\ast 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.} }
Endnote
%0 Conference Paper %T Matrix Completion With Hypergraphs: Sharp Thresholds and Efficient Algorithms %A Zhongtian Ma %A Qiaosheng Zhang %A Zhen Wang %B Proceedings of the Third Learning on Graphs Conference %C Proceedings of Machine Learning Research %D 2025 %E Guy Wolf %E Smita Krishnaswamy %F pmlr-v269-ma25a %I PMLR %P 34:1--34:30 %U https://proceedings.mlr.press/v269/ma25a.html %V 269 %X 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 \ast sharp threshold\ast 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 \textasciigrave \textasciigrave quality”of hypergraphs, enabling us to \ast quantify\ast 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.
APA
Ma, Z., Zhang, Q. & Wang, Z.. (2025). Matrix Completion With Hypergraphs: Sharp Thresholds and Efficient Algorithms. Proceedings of the Third Learning on Graphs Conference, in Proceedings of Machine Learning Research 269:34:1-34:30 Available from https://proceedings.mlr.press/v269/ma25a.html.

Related Material