Matrix Completion with Hypergraphs:Sharp Thresholds and Efficient Algorithms

• URL: http://arxiv.org/abs/2401.08197v2
• Date: Wed, 17 Jan 2024 13:42:40 GMT
• Title: Matrix Completion with Hypergraphs:Sharp Thresholds and Efficient Algorithms
• Authors: Zhongtian Ma, Qiaosheng Zhang and Zhen Wang
• Abstract summary: 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 emphsharp threshold on the sample probability for the task of exactly completing the rating matrix. We develop a computationally efficient matrix completion algorithm that effectively exploits the observed graphs and hypergraphs.
• Score: 5.405890484609721
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 \emph{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 \emph{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.

Related papers

• Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning [53.445068584013896]
  We study matrix estimation problems arising in reinforcement learning (RL) with low-rank structure. In low-rank bandits, the matrix to be recovered specifies the expected arm rewards, and for low-rank Markov Decision Processes (MDPs), it may for example characterize the transition kernel of the MDP. We show that simple spectral-based matrix estimation approaches efficiently recover the singular subspaces of the matrix and exhibit nearly-minimal entry-wise error.
  arXiv  Detail & Related papers  (2023-10-10T17:06:41Z)
• Matrix Completion from General Deterministic Sampling Patterns [28.116011361245224]
  We establish theoretical guarantee for the exact and approximate low-rank matrix completion problems. We show that the algorithm can be successful as the observation graph is well-connected and has similar node degrees.
  arXiv  Detail & Related papers  (2023-06-04T07:01:31Z)
• Bures-Wasserstein Means of Graphs [60.42414991820453]
  We propose a novel framework for defining a graph mean via embeddings in the space of smooth graph signal distributions. By finding a mean in this embedding space, we can recover a mean graph that preserves structural information. We establish the existence and uniqueness of the novel graph mean, and provide an iterative algorithm for computing it.
  arXiv  Detail & Related papers  (2023-05-31T11:04:53Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  We propose a bi-level optimization approach for learning the optimal graph structure. We also explore a low-rank approximation model for further reducing the time complexity.
  arXiv  Detail & Related papers  (2022-05-06T03:37:00Z)
• Sparse random hypergraphs: Non-backtracking spectra and community detection [10.503525445174464]
  We prove that a spectral method based on the non-backtracking operator for hypergraphs works with high probability down to the generalized Kesten-Stigum detection threshold conjectured by Angelini et al. This is the first provable and efficient algorithm that achieves the conjectured threshold for HSBMs with $r$ blocks generated according to a general symmetric probability tensor.
  arXiv  Detail & Related papers  (2022-03-14T17:45:03Z)
• Matrix Completion with Hierarchical Graph Side Information [39.00971122472004]
  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. We conduct extensive experiments on synthetic and real-world datasets to corroborate our theoretical results.
  arXiv  Detail & Related papers  (2022-01-02T03:47:41Z)
• Bayesian Graph Contrastive Learning [55.36652660268726]
  We propose a novel perspective of graph contrastive learning methods showing random augmentations leads to encoders. Our proposed method represents each node by a distribution in the latent space in contrast to existing techniques which embed each node to a deterministic vector. We show a considerable improvement in performance compared to existing state-of-the-art methods on several benchmark datasets.
  arXiv  Detail & Related papers  (2021-12-15T01:45:32Z)
• HyperSF: Spectral Hypergraph Coarsening via Flow-based Local Clustering [9.438207505148947]
  We propose an efficient spectral hypergraph coarsening scheme (HyperSF) for preserving the original spectral (structural) properties of hypergraphs. Our results show that the proposed hypergraph coarsening algorithm can significantly improve the multi-way conductance of hypergraph clustering.
  arXiv  Detail & Related papers  (2021-08-17T22:20:23Z)
• Bayesian matrix completion with a spectral scaled Student prior: theoretical guarantee and efficient sampling [0.30458514384586394]
  A spectral scaled Student prior is exploited to favour the underlying low-rank structure of the data matrix. We show that our approach enjoys a minimax-optimal oracle inequality which guarantees that our method works well under model misspecification.
  arXiv  Detail & Related papers  (2021-04-16T16:03:43Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  We introduce a novel learning problem for dense subgraph discovery. We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability. We then design a more scalable algorithm with a theoretical guarantee.
  arXiv  Detail & Related papers  (2020-06-24T11:37:33Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.