Network recovery from aggregated relational data: An impossibility theorem
Abstract
We prove an impossibility theorem for uniformly consistent recovery of labeled edge probabilities from complete aggregated relational data, even when the population count law identifies every probability. For any known partition into two equal trait groups, we consider an independent-edge logistic network with a balanced rank-one signal and unknown activity effects with bounded total dyadic energy. The signal amplitude is known and fixed at a small positive value. Every node reports its counts to both groups. The minimax mean squared error for the probability matrix remains bounded away from zero as the network grows, whereas it tends to zero under full adjacency on the same parameter class. The lower bound accounts for the dependence across the entire count array through a two-node oracle from which all observed counts can be reconstructed. Conditional binomial smoothing bounds the information about a local sign orientation, and an anchored many-bit construction converts these ambiguities into a nonvanishing normalized matrix loss. A mixed-cumulant identity recovers every edge probability from the population degree law, locating the obstruction in estimation from a single aggregated network rather than in population identification.
Related
- Community Detection from Aggregated Relational Data: Identifiability and Spectral Recovery
- Activity-Conditioned Residual Association from Aggregated Relational Data
- The No-Meaning Falsity: The Structural Impossibility of the Arbitrary Sign in Classical Arabic
- Tensor Network Moral Graph Recovery of Discrete Probability Distributions
- On the Impossibility of Estimating the Average Mixing Time
BibTeX
@misc{tseng2026network,
title = {{Network recovery from aggregated relational data: An impossibility theorem}},
author = {Yen-hsuan Tseng},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.07077},
eprint = {2609.07077},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.07077},
}
RIS
TY - UNPB
TI - Network recovery from aggregated relational data: An impossibility theorem
AU - Yen-hsuan Tseng
PY - 2026
DA - 2026/09/07
PB - arXiv
DO - 10.48550/arxiv.2609.07077
UR - https://arxiv.org/abs/2609.07077
AB - We prove an impossibility theorem for uniformly consistent recovery of labeled edge probabilities from complete aggregated relational data, even when the population count law identifies every probability. For any known partition into two equal trait groups, we consider an independent-edge logistic network with a balanced rank-one signal and unknown activity effects with bounded total dyadic energy. The signal amplitude is known and fixed at a small positive value. Every node reports its counts to both groups. The minimax mean squared error for the probability matrix remains bounded away from zero as the network grows, whereas it tends to zero under full adjacency on the same parameter class. The lower bound accounts for the dependence across the entire count array through a two-node oracle from which all observed counts can be reconstructed. Conditional binomial smoothing bounds the information about a local sign orientation, and an anchored many-bit construction converts these ambiguities into a nonvanishing normalized matrix loss. A mixed-cumulant identity recovers every edge probability from the population degree law, locating the obstruction in estimation from a single aggregated network rather than in population identification.
ER -