Community Detection from Aggregated Relational Data: Identifiability and Spectral Recovery

Abstract

Aggregated relational data replaces a fully observed network with a compressed version, where survey respondents are asked questions such as ``How many of your friends belong to group $G$?''. We consequently only observe a matrix $R=OA$ of the adjacency matrix $A$ with a fixed design $O$. In this paper we understand the effects of this compression on community detection under degree-corrected stochastic block models. First, we give guarantees for when it is possible to recover the full network parameters, and then only just the communities under conditions on a diagonal corrected version of $\mathbb{E}[R]$, which can be used to inform experimental design. Secondly, we show that spectral clustering with single linkage exactly recovers communities when $n{\rho }_n\gtrsim K^2+K\log n$ when there are $K$ balanced communities under ``uniformly spread'' or near-orthogonal designs, and characterize more generally how the design influences rates of convergence. We also introduce second-order ``friends-of-friends'' queries and develop the corresponding theory.