Community detection with the Bethe-Hessian

• URL: http://arxiv.org/abs/2411.02835v1
• Date: Tue, 05 Nov 2024 06:18:37 GMT
• Title: Community detection with the Bethe-Hessian
• Authors: Ludovic Stephan, Yizhe Zhu,
• Abstract summary: 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.
• Score: 8.890988784292926
• License:
• Abstract: The Bethe-Hessian matrix, introduced by Saade, Krzakala, and Zdeborov\'a (2014), is a Hermitian matrix designed for applying spectral clustering algorithms to sparse networks. Rather than employing a non-symmetric and high-dimensional non-backtracking operator, a spectral method based on the Bethe-Hessian matrix is conjectured to also reach the Kesten-Stigum detection threshold in the sparse stochastic block model (SBM). We provide the first rigorous analysis of the Bethe-Hessian spectral method in the SBM under both the bounded expected degree and the growing degree regimes. Specifically, we demonstrate that: (i) When the expected degree $d\geq 2$, the number of negative outliers of the Bethe-Hessian matrix can consistently estimate the number of blocks above the Kesten-Stigum threshold, thus confirming a conjecture from Saade, Krzakala, and Zdeborov\'a (2014) for $d\geq 2$. (ii) For sufficiently large $d$, its eigenvectors can be used to achieve weak recovery. (iii) As $d\to\infty$, we establish the concentration of the locations of its negative outlier eigenvalues, and weak consistency can be achieved via a spectral method based on the Bethe-Hessian matrix.

Related papers

• Low-rank Bayesian matrix completion via geodesic Hamiltonian Monte Carlo on Stiefel manifolds [0.18416014644193066]
  We present a new sampling-based approach for enabling efficient computation of low-rank Bayesian matrix completion. We show that our approach resolves the sampling difficulties encountered by standard Gibbs samplers for the common two-matrix factorization used in matrix completion. Numerical examples demonstrate superior sampling performance, including better mixing and faster convergence to a stationary distribution.
  arXiv  Detail & Related papers  (2024-10-27T03:12:53Z)
• Provable Benefit of Annealed Langevin Monte Carlo for Non-log-concave Sampling [28.931489333515618]
  We establish an oracle complexity of $widetildeOleft(fracdbeta2cal A2varepsilon6right)$ for simple annealed Langevin Monte Carlo algorithm. We show that $cal A$ represents the action of a curve of probability measures interpolating the target distribution $pi$ and a readily sampleable distribution.
  arXiv  Detail & Related papers  (2024-07-24T02:15:48Z)
• Sparse PCA with Oracle Property [115.72363972222622]
  We propose a family of estimators based on the semidefinite relaxation of sparse PCA with novel regularizations. We prove that, another estimator within the family achieves a sharper statistical rate of convergence than the standard semidefinite relaxation of sparse PCA.
  arXiv  Detail & Related papers  (2023-12-28T02:52:54Z)
• A Family of Bipartite Separability Criteria Based on Bloch Representation of Density Matrices [7.6857251828091595]
  We study the separability of bipartite quantum systems in arbitrary dimensions based on the Bloch representation of density matrices. We present two separability criteria for quantum states in terms of the matrices $T_alphabeta(rho)$ and $W_ab,alphabeta(rho)$ constructed from the correlation tensors in the Bloch representation.
  arXiv  Detail & Related papers  (2023-04-30T12:11:51Z)
• Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
  We propose a novel semi-supervised subspace clustering method, which is able to simultaneously augment the initial supervisory information and construct a discriminative affinity matrix. Comprehensive experimental results on six commonly-used benchmark datasets demonstrate the superiority of our method over state-of-the-art methods.
  arXiv  Detail & Related papers  (2022-05-21T01:47:17Z)
• 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)
• 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)
• 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)
• Searching for exceptional points and inspecting non-contractivity of trace distance in (anti-)$\mathcal{PT}\!-$symmetric systems [0.0]
  Non-Hermitian systems with parity-time ($mathcalPT$) symmetry and anti-$mathcalPT$ symmetry give rise to exceptional points (EPs) We propose a powerful and easily computable tool, based on the Hilbert-Schmidt speed (HSS), which does not require the diagonalization of the evolved density matrix. We find that the trace distance, a measure of distinguishability of two arbitrary quantum states, may be non-contractive under the non-Hermitian evolution of the system.
  arXiv  Detail & Related papers  (2021-01-12T18:42:52Z)
• Relative Error Bound Analysis for Nuclear Norm Regularized Matrix Completion [101.83262280224729]
  We develop a relative error bound for nuclear norm regularized matrix completion. We derive a relative upper bound for recovering the best low-rank approximation of the unknown matrix.
  arXiv  Detail & Related papers  (2015-04-26T13:12: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.