# Covariate-assisted spectral clustering

arXiv: https://arxiv.org/abs/1411.2158 · HTML: https://mlsanity.com/paper/1411.2158/

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Nov 2014.

## Built on by (most cited first, 29 of 29)

- [Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization](https://mlsanity.com/paper/2102.06966/) (2021)
- [Graph Attention Retrospective](https://mlsanity.com/paper/2202.13060/) (2022)
- [Effects of Graph Convolutions in Multi-layer Networks](https://mlsanity.com/paper/2204.09297/) (2022)
- [Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities](https://mlsanity.com/paper/2107.06767/) (2021)
- [Understanding Non-linearity in Graph Neural Networks from the Bayesian-Inference Perspective](https://mlsanity.com/paper/2207.11311/) (2022)
- [Revisiting Robustness in Graph Machine Learning](https://mlsanity.com/paper/2305.00851/) (2023)
- [Consistency of Constrained Spectral Clustering under Graph Induced Fair Planted Partitions](https://mlsanity.com/paper/2105.03714/) (2021)
- [An iterative clustering algorithm for the Contextual Stochastic Block Model with optimality guarantees](https://mlsanity.com/paper/2112.10467/) (2021)
- [A Metadata-Driven Approach to Understand Graph Neural Networks](https://mlsanity.com/paper/2310.19263/) (2023)
- [Learning Posterior Predictive Distributions for Node Classification from Synthetic Graph Priors](https://mlsanity.com/paper/2604.19028/) (2026)
- [Fundamental limits for rank-one matrix estimation with groupwise heteroskedasticity](https://mlsanity.com/paper/2106.11950/) (2021)
- [Exact Community Recovery in Correlated Stochastic Block Models](https://mlsanity.com/paper/2203.15736/) (2022)
- [Exact Recovery and Bregman Hard Clustering of Node-Attributed Stochastic Block Model](https://mlsanity.com/paper/2310.19854/) (2023)
- [Deep Cut-informed Graph Embedding and Clustering](https://mlsanity.com/paper/2503.06635/) (2025)
- [On Classification Thresholds for Graph Attention with Edge Features](https://mlsanity.com/paper/2210.10014/) (2022)
- [A Spectral Analysis of Graph Neural Networks on Dense and Sparse Graphs](https://mlsanity.com/paper/2211.03231/) (2022)
- [Bayesian community detection for networks with covariates](https://mlsanity.com/paper/2203.02090/) (2022)
- [Neural-prior stochastic block model](https://mlsanity.com/paper/2303.09995/) (2023)
- [Non-Convex Joint Community Detection and Group Synchronization via Generalized Power Method](https://mlsanity.com/paper/2112.14204/) (2021)
- [Learning Joint and Individual Structure in Network Data with Covariates](https://mlsanity.com/paper/2406.08776/) (2024)
- [A graph representation based on fluid diffusion model for data analysis: theoretical aspects and enhanced community detection](https://mlsanity.com/paper/2112.04388/) (2021)
- [Generator-based Graph Generation via Heat Diffusion](https://mlsanity.com/paper/2602.03612/) (2026)
- [On consistency of constrained spectral clustering under representation-aware stochastic block model](https://mlsanity.com/paper/2203.02005/) (2022)
- [Perfect Spectral Clustering with Discrete Covariates](https://mlsanity.com/paper/2205.08047/) (2022)
- [Dynamic Network Sampling for Community Detection](https://mlsanity.com/paper/2208.13921/) (2022)
- [Hypothesis testing on invariant subspaces of non-diagonalizable matrices with applications to network statistics](https://mlsanity.com/paper/2303.18233/) (2023)
- [Community Detection for Contextual-LSBM: Theoretical Limitations of Misclassification Rate and Efficient Algorithms](https://mlsanity.com/paper/2501.11139/) (2025)
- [Covariate-assisted graph matching](https://mlsanity.com/paper/2512.11761/) (2025)
- [A Subsampled Davis-Kahan Bound for Large-Scale Eigenspace Estimation](https://mlsanity.com/paper/2609.09211/) (2026)

## Abstract (arXiv)

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.