What Structure Buys in Network Change-Point Localization

Structural summaries can reduce the stochastic complexity of network change-point localization, but they can also erase the change. We study this tradeoff for one change in independent Bernoulli networks. Over unrestricted networks we prove the two-term minimax lower bound $\min \{T,\rho /{\delta }^2+D{\rho }^2/(T{\delta }^4)\}$; for aligned disjoint aggregations the same lower bound holds with the number of structural cells in place of $D$. We see that valid side information can reduce an intrinsic dimension-dependent localization cost. A finite-sample analysis of the closely related Wang–Shao distinct-index contrast gives matching upper rates up to logarithms for aligned aggregation classes, while a deterministic misclustering lemma quantifies signal loss from an estimated partition. We also give results for general fixed linear maps, bounded frozen nonlinear features, and finite-library validity under an order-preserving parity split. Our experiments exhibit both sides of the retained-signal tradeoff, operationalize learned and selected structure, validate canonical raw-input baselines at strong signal, explain null-like boundary concentration of uninformative representations, and show calendar-robust late-September localization in Enron.