Title: Spectral clustering with higher-order structures under a superimposed stochastic block model
Authors: Subhadeep Paul - The Ohio State University (United States) [presenting]
Abstract: Higher-order subgraphs or motif structures are increasingly important in network studies to understand functionality, regulation, and control of complex networks. We consider the problem of community detection in a complex network based on such higher-order structures. We propose a Superimposed Stochastic Block Model (SupSBM), a random graph model with community structure that allows dependence among the network edges and leads to the presence of higher-order structures yet remaining mathematically tractable. The model is based on a signal and noise superimposition framework where certain higher-order structures are directly generated from a signal random graph model, and superimposed with edges generated randomly from a noise random graph model. We then analyze the performance of the recently proposed higher-order spectral clustering method. We prove non-asymptotic upper bounds for the error of community detection using the method under a SupSBM where the signal component consists of triangle motifs and the noise component consists of undirected edges. As part of our analysis, we also derive error bounds of the higher-order spectral clustering method under the ordinary SBM and the triangle hypergraph SBM. Finally, under the non-uniform hypergraph SBM where one observes edges and triangle hyperedges distinctly, we obtain a criterion to choose between spectral clustering using edges or triangle hyperedges.