Matrix Completion with Hypergraphs:Sharp Thresholds and Efficient Algorithms

Title: Matrix Completion with Hypergraphs: Sharp Thresholds and Efficient Algorithms

Problem Statement
This paper addresses the problem of exactly recovering a binary rating matrix (entries $+1$ or $-1$) representing user preferences for items, given only a sub-sampled set of observed ratings. Unlike traditional matrix completion, this work incorporates side information in the form of social graphs and social hypergraphs. The underlying model assumes that users are partitioned into $K$ disjoint clusters, where users within the same cluster share identical rating vectors (homophily). The observations consist of:

1. A sub-sampled rating matrix $U$ where entries are sampled with probability $p$ and potentially flipped with noise probability $\theta$.
2. A social graph $G$ generated via the Stochastic Block Model (SBM).
3. A collection of social hypergraphs $\{HG_d\}$ generated via the Hypergraph Stochastic Block Model (HSBM), capturing high-order relationships among users (e.g., chat groups) that standard graphs cannot represent.

The objective is to determine the minimum sample probability $p$ required to achieve exact matrix completion and to develop an algorithm that attains this limit.

Methodology
The authors propose a computationally efficient algorithm named MCH (Matrix Completion with Hypergraphs), which operates in three stages:

1. Partial Cluster Recovery: The algorithm constructs a weighted adjacency matrix $A$ by aggregating information from the social graph and hypergraphs. It applies spectral clustering to $A$ to obtain an initial, coarse estimate of the user clusters.
2. Rating Vector Estimation: Using the initial cluster estimates and the observed entries in the sub-sampled matrix, the algorithm estimates the nominal rating vector for each cluster using a majority rule.
3. Iterative Refinement: The algorithm iteratively refines the cluster assignments. In each iteration, every user is reassigned to the cluster that maximizes a local score combining the hypergraph connectivity (number of hyperedges crossing the user and the cluster) and the consistency of the user's observed ratings with the estimated cluster rating vector. This process repeats for $T = O(\log n)$ iterations.

Theoretical analysis relies on information-theoretic bounds and large deviation techniques to characterize the performance of the estimator.

Key Contributions

1. Algorithm Development: The paper introduces MCH, an algorithm that effectively leverages both social graphs and hypergraphs. It demonstrates that MCH achieves exact matrix completion with high probability when the sample probability exceeds a specific threshold.
2. Sharp Threshold Characterization: The authors establish an information-theoretic lower bound on the sample probability required for exact recovery. They prove that the sufficient condition for MCH to succeed matches this necessary condition, thereby identifying a sharp threshold $p^*$. This threshold is a function of the "quality" of the hypergraphs (defined by the separation between intra-cluster and inter-cluster connection probabilities).
3. Quantification of Hypergraph Utility: The work provides a theoretical framework to quantify the reduction in sample complexity gained by exploiting hypergraph information. The optimal sample probability $p^*$ is shown to be a decreasing function of the hypergraph quality, demonstrating that higher-quality hypergraphs allow for exact recovery with fewer observed matrix entries.
4. Empirical Validation: Extensive experiments on synthetic datasets validate the theoretical phase transition phenomenon. Furthermore, experiments on a semi-real dataset (the contact-high-school network with both graphs and hyperedges) show that MCH outperforms state-of-the-art matrix completion algorithms, including those utilizing only graph information.

Results

• Theoretical: Under a symmetric setting (equal cluster sizes), the paper proves that exact recovery is possible if and only if the sample probability $p$ exceeds the threshold $p^*$. The threshold is given by:
  $$p^* = \max \left\{ \frac{\log n - \sum_{d=2}^W \binom{n-1}{d-1} K^{1-d} (\sqrt{\alpha_d} - \sqrt{\beta_d})^2}{(\sqrt{1-\theta} - \sqrt{\theta})^2 \gamma m}, \frac{K \log m}{(\sqrt{1-\theta} - \sqrt{\theta})^2 n} \right\}$$
  where $\alpha_d$ and $\beta_d$ are the connection probabilities within and between clusters for $d$-uniform hypergraphs, and $\gamma$ represents the minimal Hamming distance between cluster rating vectors.
• Experimental: On synthetic data, the empirical error probability drops to zero once the normalized sample probability exceeds 1, confirming the sharp threshold. On the semi-real dataset, MCH achieves lower Mean Absolute Error (MAE) compared to competitors like SocialMF, GraphRec, and the spectral clustering method by Ahn et al. [11]. The advantage of MCH becomes more pronounced as the quality of the underlying social graph decreases, highlighting the specific value added by hypergraph information.

Significance
The paper claims to provide the first theoretical insights into the utility of hypergraph information in recommender systems and matrix completion. While prior works have demonstrated the empirical effectiveness of hypergraphs, this study rigorously quantifies the "gain" provided by hypergraphs in terms of sample efficiency. By establishing a sharp threshold, the authors demonstrate that hypergraphs are not merely heuristic improvements but fundamentally alter the information-theoretic limits of the problem, enabling exact recovery with significantly fewer samples when high-order user interactions are available. The work bridges the gap between practical recommender system design and information-theoretic limits, offering a provably optimal algorithm for settings involving complex social structures.