On the Minimax Misclassification Ratio of Hypergraph Community Detection

DOI10.1109/TIT.2019.2928301MaRDI QIDQ5211562zbMATH OpenOpenAlexFDO

Authors I. Eli Chien, Chung-Yi Lin, I-Hsiang Wang

Publication date 28 January 2020

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1802.00926

Mathematics Subject Classification ID

Detection theory in information and communication theory (94A13)

Abstract: Community detection in hypergraphs is explored. Under a generative hypergraph model called "d-wise hypergraph stochastic block model" (d-hSBM) which naturally extends the Stochastic Block Model from graphs to d-uniform hypergraphs, the asymptotic minimax mismatch ratio is characterized. For proving the achievability, we propose a two-step polynomial time algorithm that achieves the fundamental limit. The first step of the algorithm is a hypergraph spectral clustering method which achieves partial recovery to a certain precision level. The second step is a local refinement method which leverages the underlying probabilistic model along with parameter estimation from the outcome of the first step. To characterize the asymptotic performance of the proposed algorithm, we first derive a sufficient condition for attaining weak consistency in the hypergraph spectral clustering step. Then, under the guarantee of weak consistency in the first step, we upper bound the worst-case risk attained in the local refinement step by an exponentially decaying function of the size of the hypergraph and characterize the decaying rate. For proving the converse, the lower bound of the minimax mismatch ratio is set by finding a smaller parameter space which contains the most dominant error events, inspired by the analysis in the achievability part. It turns out that the minimax mismatch ratio decays exponentially fast to zero as the number of nodes tends to infinity, and the rate function is a weighted combination of several divergence terms, each of which is the Renyi divergence of order 1/2 between two Bernoulli's. The Bernoulli's involved in the characterization of the rate function are those governing the random instantiation of hyperedges in d-hSBM. Experimental results on synthetic data validate our theoretical finding that the refinement step is critical in achieving the optimal statistical limit.

Cited in

(12)

• Exact recovery in the hypergraph stochastic block model: a spectral algorithm
• A sharp blockwise tensor perturbation bound for orthogonal iteration
• Multilayer hypergraph clustering using the aggregate similarity matrix
• Community detection in the sparse hypergraph stochastic block model
• Community Detection in General Hypergraph Via Graph Embedding
• Consistent Estimation of the Number of Communities via Regularized Network Embedding
• Directed Community Detection With Network Embedding
• Connectivity of random hypergraphs with a given hyperedge size distribution
• Model-based clustering in simple hypergraphs through a stochastic blockmodel
• Sparse random hypergraphs: non-backtracking spectra and community detection
• Optimal and exact recovery on the general nonuniform hypergraph stochastic block model
• Partial recovery and weak consistency in the non-uniform hypergraph stochastic block model

This page was built for publication: On the Minimax Misclassification Ratio of Hypergraph Community Detection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5211562)