Spiked Laplacian Graphs: Bayesian Community Detection in Heterogeneous Networks.

In the network data analysis, it is common to encounter a large population of graphs: each has a small-to-moderate number of nodes but together, they show substantial variation from one graph to another. The graph Laplacian, a linear transform of the adjacency matrix, is routinely used in community detection algorithms; however, it is limited to single graph analysis and lacks uncertainty quantification. In this article, we propose a generative graph model called `Spiked Laplacian Graph'. Viewing each graph as a transform of the degree and Laplacian, we model the Laplacian eigenvalues as an increasing sequence followed by repeats of a flat constant. It effectively reduces the number of parameters in the eigenvectors and allows us to exploit the spectral graph theory for optimal graph partitioning. The signs in these orthonormal eigenvectors encode a hierarchical community structure, eliminating the need for iterative clustering algorithms. The estimator on the communities inherits the randomness from the posterior of eigenvectors. This spectral structure is amenableto a Bayesian non-parametric treatment that tackles heterogeneity. Theory is established on the trade-off between model resolution and accuracy, as well as the posterior consistency. We illustrate the performance in a brain network study related to working memory. KEYWORDS: Hierarchical Community Detection, Isoperimetric Constant, Mixed-Effect Eigendecomposition, Normalized Graph Cut, Stiefel Manifold.