Covariate-assisted spectral clustering

Abstract

Biological and social systems consist of myriad interacting units. The interactions can be represented in the form of a graph or network. Measurements of these graphs can reveal the underlying structure of these interactions, which provides insight into the systems that generated the graphs. Moreover, in applications such as connectomics, social networks, and genomics, graph data are accompanied by contextualizing measures on each node. We utilize these node covariates to help uncover latent communities in a graph, using a modification of spectral clustering. Statistical guarantees are provided under a joint mixture model that we call the node-contextualized stochastic blockmodel, including a bound on the mis-clustering rate. The bound is used to derive conditions for achieving perfect clustering. For most simulated cases, covariate-assisted spectral clustering yields results superior to regularized spectral clustering without node covariates and to an adaptation of canonical correlation analysis. We apply our clustering method to large brain graphs derived from diffusion MRI data, using the node locations or neurological region membership as covariates. In both cases, covariate-assisted spectral clustering yields clusters that are easier to interpret neurologically.

28 pages, 4 figures, includes substantial changes to theoretical results

References in corpus (2)

• Community Detection in Networks with Node Attributes
• Multimodal diffusion geometry by joint diagonalization of Laplacians

Cited by in corpus (38)

• Structure and inference in annotated networks
• Community detection in node-attributed social networks: a survey
• Exponential-Family Models of Random Graphs: Inference in Finite-, Super-, and Infinite Population Scenarios
• A Survey on Theoretical Advances of Community Detection in Networks
• Detection of Community Structures in Networks with Nodal Features based on Generative Probabilistic Approach
• Network cross-validation by edge sampling
• Consistent structure estimation of exponential-family random graph models with block structure
• Large-scale estimation of random graph models with local dependence
• Community detection with nodal information
• Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities
• Community Detection in Networks with Node Features
• Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization
• Prediction models for network-linked data
• Covariate Regularized Community Detection in Sparse Graphs
• Detecting Latent Communities in Network Formation Models
• Community Detection with Contextual Multilayer Networks
• Matched bipartite block model with covariates
• An Annotated Graph Model with Differential Degree Heterogeneity for Directed Networks
• Neural-prior stochastic block model
• Efficient inference in stochastic block models with vertex labels
• Discovering Political Topics in Facebook Discussion threads with Graph Contextualization
• AutoGFI: Streamlined Generalized Fiducial Inference for Modern Inference Problems in Models with Additive Errors
• A Time-Varying Network for Cryptocurrencies
• Euclidean Representation of Low-Rank Matrices and Its Statistical Applications
• An ${\ell }_p$ theory of PCA and spectral clustering
• Subsampling Spectral Clustering for Large-Scale Social Networks
• Quantifying metadata relevance to network block structure using description length
• Equipping SBMs with RBMs: An Explainable Approach for Analysis of Networks with Covariates
• clusterNOR: A NUMA-Optimized Clustering Framework
• Interpretable Stochastic Block Influence Model: measuring social influence among homophilous communities
• Mutual Information in Community Detection with Covariate Information and Correlated Networks
• Consistent Spectral Clustering of Network Block Models under Local Differential Privacy
• Clustering Network Tree Data From Respondent-driven sampling with application to opioid users in New York City
• Vector Quantized Spectral Clustering applied to Soybean Whole Genome Sequences
• knor: A NUMA-Optimized In-Memory, Distributed and Semi-External-Memory k-means Library
• High-dimensional Gaussian graphical model for network-linked data
• CALF-SBM: A Covariate-Assisted Latent Factor Stochastic Block Model
• Logistic Regression Augmented Community Detection for Network Data with Application in Identifying Autism-Related Gene Pathways