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 𝔼[R], which can be used to inform experimental design. Secondly, we show that spectral clustering with single linkage exactly recovers communities when nρn≳ K2+Klog 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.
Related
- Activity-Conditioned Residual Association from Aggregated Relational Data
- Network recovery from aggregated relational data: An impossibility theorem
- Spectral Indistinguishability and Learning-Curve Identifiability in Quadratic Networks
- When Identical Rows Disagree: From Benchmark Identifiability to Replication-Robust Anomaly Detection
- A comparison of artificial neural networks and partial least squares modelling for the rapid detection of the microbial spoilage of beef fillets based on Fourier transform infrared spectral fingerprints
BibTeX
@misc{davison2026community,
title = {{Community Detection from Aggregated Relational Data: Identifiability and Spectral Recovery}},
author = {Andrew Davison and Owen G. Ward},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.03937},
eprint = {2610.03937},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.03937},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Community Detection from Aggregated Relational Data: Identifiability and Spectral Recovery
AU - Andrew Davison
AU - Owen G. Ward
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2610.03937
UR - https://arxiv.org/abs/2610.03937
AB - 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 𝔼[R], which can be used to inform experimental design. Secondly, we show that spectral clustering with single linkage exactly recovers communities when nρ_n≳ K^2+Klog 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.
ER -