Hypergraph Spectral Clustering in the Weighted Stochastic Block Model

Abstract

Spectral clustering is a celebrated algorithm that partitions objects based on pairwise similarity information. While this approach has been successfully applied to a variety of domains, it comes with limitations. The reason is that there are many other applications in which only \emph{multi}-way similarity measures are available. This motivates us to explore the multi-way measurement setting. In this work, we develop two algorithms intended for such setting: Hypergraph Spectral Clustering (HSC) and Hypergraph Spectral Clustering with Local Refinement (HSCLR). Our main contribution lies in performance analysis of the poly-time algorithms under a random hypergraph model, which we name the weighted stochastic block model, in which objects and multi-way measures are modeled as nodes and weights of hyperedges, respectively. Denoting by $n$ the number of nodes, our analysis reveals the following: (1) HSC outputs a partition which is better than a random guess if the sum of edge weights (to be explained later) is $\Omega (n)$; (2) HSC outputs a partition which coincides with the hidden partition except for a vanishing fraction of nodes if the sum of edge weights is $\omega (n)$; and (3) HSCLR exactly recovers the hidden partition if the sum of edge weights is on the order of $n\log n$. Our results improve upon the state of the arts recently established under the model and they firstly settle the order-wise optimal results for the binary edge weight case. Moreover, we show that our results lead to efficient sketching algorithms for subspace clustering, a computer vision application. Lastly, we show that HSCLR achieves the information-theoretic limits for a special yet practically relevant model, thereby showing no computational barrier for the case.

16 pages; 3 figures

References in corpus (29)

• Robust Recovery of Subspace Structures by Low-Rank Representation
• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• User-friendly tail bounds for sums of random matrices
• Spectral redemption: clustering sparse networks
• Spectral clustering and the high-dimensional stochastic blockmodel
• Consistency of spectral clustering in stochastic block models
• Random hypergraphs and their applications
• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• Fast Algorithms for Robust PCA via Gradient Descent
• Provable Tensor Factorization with Missing Data
• Alignment and integration of complex networks by hypergraph-based spectral clustering
• Consistency of Spectral Hypergraph Partitioning under Planted Partition Model
• Finding One Community in a Sparse Graph
• Spectral MLE: Top-$K$ Rank Aggregation from Pairwise Comparisons
• Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms
• Greedy Subspace Clustering
• Achieving Optimal Misclassification Proportion in Stochastic Block Model
• Information-theoretic thresholds for community detection in sparse networks
• Information-theoretic thresholds for community detection in sparse networks
• Spectral Detection on Sparse Hypergraphs
• Uniform Hypergraph Partitioning: Provable Tensor Methods and Sampling Techniques
• Information-theoretic bounds for exact recovery in weighted stochastic block models using the Renyi divergence
• Community Detection via Random and Adaptive Sampling
• Spectral Thresholds in the Bipartite Stochastic Block Model
• Non-Reconstructability in the Stochastic Block Model
• Community Recovery in Graphs with Locality
• Evolution of high-order connected components in random hypergraphs
• Optimal Rates for Community Estimation in the Weighted Stochastic Block Model

Cited by in corpus (21)

• Networks beyond pairwise interactions: structure and dynamics
• Introducing Hypergraph Signal Processing: Theoretical Foundation and Practical Applications
• Stochastic Block Model for Hypergraphs: Statistical limits and a semidefinite programming approach
• Randomizing hypergraphs preserving degree correlation and local clustering
• Exact Recovery in the Hypergraph Stochastic Block Model: a Spectral Algorithm
• Community detection for weighted bipartite networks
• Robust Hypergraph Clustering via Convex Relaxation of Truncated MLE
• Testing Community Structures for Hypergraphs
• A Sharp Blockwise Tensor Perturbation Bound for Orthogonal Iteration
• Strong Consistency of Spectral Clustering for the Sparse Degree-Corrected Hypergraph Stochastic Block Model
• Nonparametric Modeling of Higher-Order Interactions via Hypergraphons
• Estimating the number of communities in weighted networks
• Community Detection in General Hypergraph via Graph Embedding
• Multiway Spherical Clustering via Degree-Corrected Tensor Block Models
• Model-based clustering in simple hypergraphs through a stochastic blockmodel
• Multilayer hypergraph clustering using the aggregate similarity matrix
• Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model
• Exact Recovery in the General Hypergraph Stochastic Block Model
• Binary Classification with XOR Queries: Fundamental Limits and An Efficient Algorithm
• Information Limits for Detecting a Subhypergraph
• Information Theoretic Limits of Exact Recovery in Sub-hypergraph Models for Community Detection