Exact recovery for the non-uniform Hypergraph Stochastic Block Model
- URL: http://arxiv.org/abs/2304.13139v2
- Date: Thu, 20 Jul 2023 21:21:46 GMT
- Title: Exact recovery for the non-uniform Hypergraph Stochastic Block Model
- Authors: Ioana Dumitriu, Haixiao Wang
- Abstract summary: We consider the community detection problem in random hypergraphs under the non-uniform hypergraph block model.
By aggregating information from all the uniform layers, we may obtain exact recovery even in cases when this may appear impossible if each layer were considered alone.
- Score: 0.0
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Consider the community detection problem in random hypergraphs under the
non-uniform hypergraph stochastic block model (HSBM), where each hyperedge
appears independently with some given probability depending only on the labels
of its vertices. We establish, for the first time in the literature, a sharp
threshold for exact recovery under this non-uniform case, subject to minor
constraints; in particular, we consider the model with multiple communities ($K
\geq 2$). One crucial point here is that by aggregating information from all
the uniform layers, we may obtain exact recovery even in cases when this may
appear impossible if each layer were considered alone. Two efficient algorithms
that successfully achieve exact recovery above the threshold are provided. The
theoretical analysis of our algorithms relies on the concentration and
regularization of the adjacency matrix for non-uniform random hypergraphs,
which could be of independent interest. We also address some open problems
regarding parameter knowledge and estimation.
Related papers
- Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
We present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms.
In particular, we present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms.
arXiv Detail & Related papers (2023-12-19T13:17:43Z) - Strong consistency and optimality of spectral clustering in symmetric
binary non-uniform Hypergraph Stochastic Block Model [0.0]
We study the unsupervised classification problem in random hypergraphs under the non-uniform emphHypergraph Block Model (HSBM)
We find that strong consistency is achievable by aggregating information from all uniform layers, even if it is impossible when each layer is considered alone.
arXiv Detail & Related papers (2023-06-12T03:38:25Z) - Multilayer hypergraph clustering using the aggregate similarity matrix [0.7373617024876725]
We consider the community recovery problem on a multilayer variant of the hypergraph block model (HSBM)
In this work, we investigate a semidefinite programming (SDP) approach and obtain information-theoretic conditions on the model parameters that guarantee exact recovery.
arXiv Detail & Related papers (2023-01-27T11:15:46Z) - Semi-Supervised Clustering of Sparse Graphs: Crossing the
Information-Theoretic Threshold [3.6052935394000234]
Block model is a canonical random graph model for clustering and community detection on network-structured data.
No estimator based on the network topology can perform substantially better than chance on sparse graphs if the model parameter is below a certain threshold.
We prove that with an arbitrary fraction of the labels feasible throughout the parameter domain.
arXiv Detail & Related papers (2022-05-24T00:03:25Z) - Optimal Clustering with Bandit Feedback [57.672609011609886]
This paper considers the problem of online clustering with bandit feedback.
It includes a novel stopping rule for sequential testing that circumvents the need to solve any NP-hard weighted clustering problem as its subroutines.
We show through extensive simulations on synthetic and real-world datasets that BOC's performance matches the lower boundally, and significantly outperforms a non-adaptive baseline algorithm.
arXiv Detail & Related papers (2022-02-09T06:05:05Z) - Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model [6.681901523019242]
We consider the community detection problem in random hypergraphs under the nonuniform hypergraph block model (HSBM)
We provide a spectral algorithm that outputs a partition with at least a $gamma$ fraction of the vertices classified correctly, where $gammain depends on the signal-to-noise ratio (SNR) of the model.
The theoretical analysis of our algorithm relies on the concentration and regularization of the adjacency matrix for non-uniform random hypergraphs, which can be of independent interest.
arXiv Detail & Related papers (2021-12-22T05:38:33Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
Clustering is a fundamental primitive in unsupervised learning.
Recent work has established lower bounds against the class of low-degree methods.
We show that, perhaps surprisingly, this particular clustering model textitdoes not exhibit a statistical-to-computational gap.
arXiv Detail & Related papers (2021-12-07T18:50:17Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits.
Specifically, we consider a neutral atom quantum computer and propose a full stack approach for correlation clustering.
We show the qudit implementation is superior to the qubit encoding as quantified by the gate count.
arXiv Detail & Related papers (2021-06-22T11:07:38Z) - Exact Recovery in the General Hypergraph Stochastic Block Model [92.28929858529679]
This paper investigates fundamental limits of exact recovery in the general d-uniform hypergraph block model (d-HSBM)
We show that there exists a sharp threshold such that exact recovery is achievable above the threshold and impossible below it.
arXiv Detail & Related papers (2021-05-11T03:39:08Z) - Spectral clustering under degree heterogeneity: a case for the random
walk Laplacian [83.79286663107845]
This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree.
In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
arXiv Detail & Related papers (2021-05-03T16:36:27Z)
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.