Perfect Spectral Clustering with Discrete Covariates

A structural pattern commonly observed in social networks is homophily, the tendency for two nodes sharing a certain trait to be more (or sometimes less) likely to form a connection [27]. Homophily may occur on any number of traits, observed or latent, and is known to confound problems of causal inference in the social sciences [38; 36; 11; 23]. Homophily, meanwhile, lies at the heart of such issues as segregation [37; 14], job access [21], and political partisanship [20], where homophily on observed traits may be the subject of estimation in its own right. In order to fully understand the effects of network patterns like observed homophily, we first need to separate them from further latent network structure. In the literature on community detection, latent structure is frequently recovered through a clustering process involving only the network edges, reserving node covariates to validate the clustering results in an approach that conflates latent structure with observed structure [32]. What we wish to do instead is to separate the latent from the observed structural patterns. To this end, we consider an extension of the stochastic block model (SBM) [16] that incorporates homophily on observed, discrete node covariates into a generalized linear model (GLM). We define this model, which we call the additive-covariate SBM (ACSBM), in Section 2. The model was previously studied by Mele et al. [29] and allows for flexible modeling choices in which latent communities take a block model structure, covariates may or may not depend on community membership, and the effects of homophily may be modeled through a range of link functions. We give an explicit representation of this model as an SBM (Proposition 1), which motivates the use of spectral clustering to estimate the latent structure.