# On consistency of constrained spectral clustering under representation-aware stochastic block model

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 63 references that are in the map.
- First posted on arXiv 3 Mar 2022.

## Builds on (most cited first, 21 of 21)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Fair Algorithms for Clustering](https://mlsanity.com/paper/1901.02393/) (2019)
- [Guarantees for Spectral Clustering with Fairness Constraints](https://mlsanity.com/paper/1901.08668/) (2019)
- [Proportionally Fair Clustering](https://mlsanity.com/paper/1905.03674/) (2019)
- [Individual Fairness for k-Clustering](https://mlsanity.com/paper/2002.06742/) (2020)
- [Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms](https://mlsanity.com/paper/1612.07925/) (2016)
- [Clustering without Over-Representation](https://mlsanity.com/paper/1905.12753/) (2019)
- [On the cost of essentially fair clusterings](https://mlsanity.com/paper/1811.10319/) (2018)
- [Achieving Optimal Misclassification Proportion in Stochastic Block Model](https://mlsanity.com/paper/1505.03772/) (2015)
- [Layer aggregation and reducibility of multilayer interconnected networks](https://mlsanity.com/paper/1405.0425/) (2014)
- [Covariate-assisted spectral clustering](https://mlsanity.com/paper/1411.2158/) (2014)
- [Consistency of Spectral Hypergraph Partitioning under Planted Partition Model](https://mlsanity.com/paper/1505.01582/) (2015)
- [Detecting Overlapping Communities in Networks Using Spectral Methods](https://mlsanity.com/paper/1412.3432/) (2014)
- [A simple SVD algorithm for finding hidden partitions](https://mlsanity.com/paper/1404.3918/) (2014)
- [Distributional Individual Fairness in Clustering](https://mlsanity.com/paper/2006.12589/) (2020)
- [Uniform Hypergraph Partitioning: Provable Tensor Methods and Sampling Techniques](https://mlsanity.com/paper/1602.06516/) (2016)
- [Compressive Spectral Clustering](https://mlsanity.com/paper/1602.02018/) (2016)
- [A Generic Sample Splitting Approach for Refined Community Recovery in Stochastic Block Models](https://mlsanity.com/paper/1411.1469/) (2014)
- [Constrained 1-Spectral Clustering](https://mlsanity.com/paper/1505.06485/) (2015)

## Abstract (arXiv)

Spectral clustering is widely used in practice due to its flexibility, computational efficiency, and well-understood theoretical performance guarantees. Recently, spectral clustering has been studied to find balanced clusters under population-level constraints. These constraints are specified by additional information available in the form of auxiliary categorical node attributes. In this paper, we consider a scenario where these attributes may not be observable, but manifest as latent features of an auxiliary graph. Motivated by this, we study constrained spectral clustering with the aim of finding balanced clusters in a given textitsimilarity graph G, such that each individual is adequately represented with respect to an auxiliary graph R (we refer to this as representation graph). We propose an individual-level balancing constraint that formalizes this idea. Our work leads to an interesting stochastic block model that not only plants the given partitions in G but also plants the auxiliary information encoded in the representation graph R. We develop unnormalized and normalized variants of spectral clustering in this setting. These algorithms use R to find clusters in G that approximately satisfy the proposed constraint. We also establish the first statistical consistency result for constrained spectral clustering under individual-level constraints for graphs sampled from the above-mentioned variant of the stochastic block model. Our experimental results corroborate our theoretical findings.