Sparse random hypergraphs: Non-backtracking spectra and community
detection
- URL: http://arxiv.org/abs/2203.07346v4
- Date: Fri, 26 Jan 2024 14:19:26 GMT
- Title: Sparse random hypergraphs: Non-backtracking spectra and community
detection
- Authors: Ludovic Stephan and Yizhe Zhu
- Abstract summary: 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.
- Score: 10.503525445174464
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the community detection problem in a sparse $q$-uniform
hypergraph $G$, assuming that $G$ is generated according to the Hypergraph
Stochastic Block Model (HSBM). 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. (2015). We characterize the spectrum of the non-backtracking operator for
the sparse HSBM and provide an efficient dimension reduction procedure using
the Ihara-Bass formula for hypergraphs. As a result, community detection for
the sparse HSBM on $n$ vertices can be reduced to an eigenvector problem of a
$2n\times 2n$ non-normal matrix constructed from the adjacency matrix and the
degree matrix of the hypergraph. To the best of our knowledge, this is the
first provable and efficient spectral algorithm that achieves the conjectured
threshold for HSBMs with $r$ blocks generated according to a general symmetric
probability tensor.
Related papers
- Community detection with the Bethe-Hessian [8.890988784292926]
We provide the first rigorous analysis of the Bethe-Hessian spectral method in the sparse block model (SBM)
We show that the number of negative outliers of the Bethe-Hessian matrix can consistently estimate the number of blocks above the Kesten-Stigum threshold.
We also establish the concentration of the locations of its outlier negative eigenvalues, and weak consistency can be achieved via a spectral method based on the Bethe-Hessian matrix.
arXiv Detail & Related papers (2024-11-05T06:18:37Z) - Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
We study the generalized low-rank matrix bandit problem, proposed in citelu2021low under the Generalized Linear Model (GLM) framework.
To overcome the computational infeasibility and theoretical restrain of existing algorithms, we first propose the G-ESTT framework.
We show that G-ESTT can achieve the $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret while G-ESTS can achineve the $tildeO
arXiv Detail & Related papers (2024-01-14T14:14:19Z) - 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) - Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
Detection of a planted dense subgraph in a random graph is a fundamental statistical and computational problem.
We consider detecting the presence of a planted $Gr(ngamma, n-alpha)$ subhypergraph in a $Gr(n, n-beta) hypergraph.
Our results are already new in the graph case $r=2$, as we consider the subtle log-density regime where hardness based on average-case reductions is not known.
arXiv Detail & Related papers (2023-04-17T10:38:08Z) - Community Detection in the Hypergraph SBM: Exact Recovery Given the
Similarity Matrix [1.74048653626208]
We study the performance of algorithms which operate on the $similarity$matrix $W$, where $W_ij$ reports the number of hyperedges containing both $i$ and $j$.
We design a simple and highly efficient spectral algorithm with nearly linear runtime and show that it achieves the min-bisection threshold.
arXiv Detail & Related papers (2022-08-23T15:22:05Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
We propose a novel method named Multi-block-probe Variance Reduced (MSVR) to alleviate the complexity of compositional problems.
Our results improve upon prior ones in several aspects, including the order of sample complexities and dependence on strongity.
arXiv Detail & Related papers (2022-07-18T12:03:26Z) - Nonbacktracking spectral clustering of nonuniform hypergraphs [2.408714894793063]
We study spectral clustering for nonuniform hypergraphs based on the hypergraph nonbacktracking operator.
We propose an alternating algorithm for inference in a hypergraph blockmodel via linearized belief-propagation.
arXiv Detail & Related papers (2022-04-27T01:14:06Z) - 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) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
We use kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process.
We derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator.
We prove minimax lower bounds over sub-classes of MRPs.
arXiv Detail & Related papers (2021-09-24T14:48:20Z) - 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) - Quantum algorithms for spectral sums [50.045011844765185]
We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices.
We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
arXiv Detail & Related papers (2020-11-12T16:29:45Z)
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.