Higher-Order Spectral Clustering under Superimposed Stochastic Block Model
arXiv:1812.06515
Abstract
Higher-order motif structures and multi-vertex interactions are becoming increasingly important in studies that aim to improve our understanding of functionalities and evolution patterns of networks. To elucidate the role of higher-order structures in community detection problems over complex networks, we introduce the notion of a Superimposed Stochastic Block Model (SupSBM). The model is based on a random graph framework in which certain higher-order structures or subgraphs are generated through an independent hyperedge generation process, and are then replaced with graphs that are superimposed with directed or undirected edges generated by an inhomogeneous random graph model. Consequently, the model introduces controlled dependencies between edges which allow for capturing more realistic network phenomena, namely strong local clustering in a sparse network, short average path length, and community structure. We proceed to rigorously analyze the performance of a number of recently proposed higher-order spectral clustering methods on the SupSBM. In particular, we prove non-asymptotic upper bounds on the misclustering error of spectral community detection for a SupSBM setting in which triangles or 3-uniform hyperedges are superimposed with undirected edges. As part of our analysis, we also derive new bounds on the misclustering error of higher-order spectral clustering methods for the standard SBM and the 3-uniform hypergraph SBM. Furthermore, for a non-uniform hypergraph SBM model in which one directly observes both edges and 3-uniform hyperedges, we obtain a criterion that describes when to perform spectral clustering based on edges and when on hyperedges, based on a function of hyperedge density and observation quality.
References in corpus (17)
- Emergence of scaling in random networks
- The structure and function of complex networks
- Community structure in social and biological networks
- Finding and evaluating community structure in networks
- Stochastic blockmodels and community structure in networks
- Higher-order organization of complex networks
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Fast community detection by SCORE
- Stochastic blockmodels with growing number of classes
- Multilayer motif analysis of brain networks
- Consistency of Spectral Hypergraph Partitioning under Planted Partition Model
- Inhomogeneous Hypergraph Clustering with Applications
- Achieving Optimal Misclassification Proportion in Stochastic Block Model
- Upper tails for arithmetic progressions in random subsets
- Orthogonal symmetric non-negative matrix factorization under the stochastic block model
- Community Detection in Hypergraphs, Spiked Tensor Models, and Sum-of-Squares
- Counting Motifs with Graph Sampling