acceptodds
Under review as a conference paper at ICLR 2027

What Structure Buys in Network Change-Point Localization

Abstract

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 ; for aligned disjoint aggregations the same lower bound holds with the number of structural cells in place of . 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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Network change-point localization, dynamic networks, structural representations, minimax localization, adaptive representation selection, Bernoulli networks, graph change detection, oracle inequalities.

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_JEgVOpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The paper describes change-point detection in dynamic networks providing different asymptotic bounds on the estimated change-point location depending on different features of the network as a linear function of the edges. This is my best guess at understanding the purpose of the paper as the writing and notation did not explain the research problem adequately. Numerous missing definitions or undefined notation meant that the entire section of the theory (Section 2-5) was meaningless as written. Without this it is impossible to judge the quality of the empirical evidence in the simulation and real data experiments.

Critical strengths

None. That is not to say there is no merit to this work. It is just impossible to determine given the current manuscript.

Critical weaknesses

Poor introduction to the proposed problem with missing definitions and undefined notation. Even with a background in dynamic network analysis, it was impossible to understand the theory given all the missing information. I strongly believe that promises of improvement through the rebuttal will not be enough to address my concerns that this can achieve ICLR standards without undertaking another full ICLR review process.

Questions for authors

None

3 comments
AuthorsOpenReview ↗

Response to JEgV: Improving the exposition by clarifying the problem, defining notations, and reorganizing the presentation

Summary. Thank you for emphasizing the need for a clear problem statement and complete definitions. We truly believe that your comment has bought the most substantial improvement to the quality of our paper. We have now rewritten the introduction and model section, reorganized the main text around one central result, and drawn the motivating example as a new schematic figure (Figure 1). The revised PDF has ten pages of main text. Blue identifies substantive additions, including the worked example and Figure 1; editorial revisions and reorganization appear in black.

1. The problem and what the estimator knows

We observe TT independent networks on the same nn labeled vertices. At one unknown time the edge-probability matrix changes from P1P_1 to P2P_2. A change is assumed to exist, and the goal is to estimate its location, with loss ∣τ^−τ∣|\hat\tau-\tau|.

The introduction builds the question from one example, drawn in Figure 1 (p. 2): 96 vertices in four supplied groups, giving 4,560 edges and ten group-pair cells. If both probability matrices are constant on each cell, ten normalized cell sums keep the entire squared jump (panel b), without knowing the jump signs, jump magnitudes or change time. The diagram describes the normalization in words and uses no notation requiring later definitions. Panel (c) makes the value of the supplied groups visible: normalized cell sums retain the full jump even when opposing changes cancel in the degree vector. The text then separates three settings: supplied structure, a fixed summary of an arbitrary network, and a summary learned from data.

Where: Section 1 and Figure 1 (pp. 1–2).

2. Definitions before every statement

Section 2 defines the adjacency matrices, edge vectors, independence assumptions, probability cap, admissible change locations, scan trimming and loss before the first result. Norms, constants and comparison notation come before the formal bounds, and cell sizes are defined where the structured class is introduced.

QuantityMeaning
T,n,DT,n,DSnapshots, vertices, possible edges D=(n2)D=\binom n2
τ\tauLast pre-change time
ρ\rhoUpper bound on probabilities in both regimes
Δ,δ2\Delta,\delta^2Edge-vector jump; δ2=∥P2−P1∥F2=2∥Δ∥2\delta^2=\Vert P_2-P_1\Vert_{\rm F}^2=2\Vert\Delta\Vert^2
F,dF,κF2F,d_F,\kappa_F^2Linear feature map, its rank, retained jump ∥FΔ∥2\Vert F\Delta\Vert^2
aF,Nb,Nmin⁡a_F,N_b,N_{\min}Retained fraction, edges in cell bb, smallest cell

The corrected contrast is introduced through its purpose. In Bernoulli networks a mean change also changes the variance, so the raw squared CUSUM can peak away from the true location, and the distinct-index contrast removes that variance term.

Where: Section 2 (pp. 3–4), with the contrast in Equation (3) and Proposition 1.

3. One visible central claim, with its proof idea

Over unrestricted changes, the worst-case expected error of every estimator is at least of order min⁡{T,ρ/δ2+Dρ2/(Tδ4)}\min\{T,\rho/\delta^2+D\rho^2/(T\delta^4)\} in the stated signal range (Theorem 2): a scalar term plus the cost of an unknown DD-dimensional direction. With dd supplied aligned cells, dd replaces DD (Theorem 3), and normalized cell sums attain this up to logarithms under the aggregation condition (Corollary 4). Section 3.2 explains the new proof step in plain terms before the appendix proof, and Section 4 states what the closest prior results already show.

Where: Section 3 (pp. 4–5); Section 4 (pp. 5–6); Appendix D (p. 20).

4. Experiments tied to these claims

Table 2 defines each method’s input before any result. The three studies each examine a central claim: preserving the jump explains the benefit of a summary (Section 6.1); supplied structure changes the relevant dimension, tested by varying network size, group count and imbalance at fixed signal (Section 6.2); and learned representations deliver measurable localization gains at a common sample budget (Section 6.3). The equal-budget comparison shows improvement over raw edges in eight of nine settings.

Suggested reading path. Section 1 with Figure 1, then Section 2, Theorems 2–3 with Corollary 4, and Section 3.2.

The revision now provides a complete reading path from the problem statement and defined notation to the main results and empirical evidence. We would be grateful if you could reassess the revised manuscript and consider updating your score in light of these completed changes.

Thank you for your response. Looking at the revised version of the document, there is a marked improvement in the quality of the paper. Sections 1 and 2 vastly clarify the problem, enough to better understand the intention of Theorems 2 & 3, and I have improved my rating.

However, to fully appreciate all of the additional material and structural changes would take a full re-read with limited time remaining in the rebuttal process. I do not want to reduce my confidence in my score below a broad familiarity with the topic (2), so I will aim to comment again later when I have more time available to reassess.

AuthorsOpenReview ↗

Connecting the original contribution to the clearer presentation and new evidence

Thank you for revisiting the manuscript and updating your assessment. Your comments on exposition directly guided our rewriting of Sections 1 and 2. Needless to say, we appreciate your recognition of the improvement. We also understand the time required to assess a substantial revision.

The central scientific message remains the one in the submitted paper: aligned network structure can improve change-point localization by reducing the uncertainty about the change direction while preserving the change signal. Revised Theorems 2–3 correspond to submitted Theorems 6–7, and revised Corollary 4 corresponds to submitted Corollary 8. The revised presentation brings these results together earlier and makes their interpretation and connection to the statistical problem more explicit. The additional analysis and experiments develop and support this same central message.

To make any further reassessment easier, we suggest three focused pointers beyond Sections 1 and 2:

  • How the main results fit together — Section 3 and Corollary 4, pp. 4–5. The lower bounds identify the cost of an unknown change direction and how supplied aligned groups reduce it. Corollary 4 supplies the corresponding achievable rate, matching the structured benchmark up to logarithmic factors under the stated conditions.
  • The key lower-bound argument — Section 3.2, p. 5. This short explanation shows how the proof accounts for learning the change direction from the observed sequence, which is essential to establishing the dimension-dependent localization cost.
  • What the new experiments demonstrate — Tables 3–4, pp. 9–10. The controlled experiments isolate network size, group count, and imbalance. The common-budget experiment then examines learned structure: the learned/selected representation improves localization over raw edges in eight of nine settings, using the same total number of observations.

If a particular assumption, proof step, or experimental comparison would benefit from further explanation, we would be happy to address it directly here with a focused explanation and a precise manuscript reference.

Thank you again for your constructive feedback and continued consideration.

Reviewer_kr6dOpenReview ↗
Rating
3
Confidence
1
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The manuscript studies the location of a single change in a sequence of independent Bernoulli networks. Its central question is whether structural summaries—such as degrees or sums over known edge groups—can improve localization. The unrestricted lower-bound benchmark is [ R_D=\min\left{T,\frac{\rho}{\delta^2} +\frac{D\rho^2}{T\delta^4}\right}, ] where (T) is the sequence length, (D) is the number of possible edges, (\rho) bounds the edge probabilities, and (\delta) measures the magnitude of the change. The first term reflects the difficulty of determining when the change occurred; the second captures the additional difficulty posed by an unknown high-dimensional change direction. For known aligned aggregations, the paper replaces (D) with the number of structural cells and establishes corresponding upper bounds up to logarithmic factors. These claims concern localization when one change is assumed to exist. The intuitive contribution is clear: pooling edges helps by reducing random fluctuations while preserving their collective change. If the grouping combines changes that cancel each other out, the mean signal can disappear. The paper quantifies this tradeoff and connects it to estimated partitions, frozen nonlinear features, and sample splitting.

Critical strengths

S1. Theorem 6 and Theorem 7 concern a limitation of every estimator over the specified parameter class, rather than merely explaining the behavior of the proposed contrast.

S2. In a Bernoulli model, changing an edge probability also changes its variance. Equation (2) and Appendix A correctly show that this can move the population maximizer of ordinary squared CUSUM away from the true change.

S3. The structured minimax comparison is valid within its stated scope. For normalized disjoint cell sums, the feature rows are orthonormal, and a cell-constant jump is preserved exactly. Consequently, the structural dimension becomes the number of cells while the signal norm is retained.

Critical weaknesses

W1. The paper does not discuss another closely related result: Kovács et al. (2024), (“Optimistic Search: Change Point Estimation for Large-scale Data via Adaptive Logarithmic Queries,”) already derive a similar two-term localization bound for Gaussian data and use odd/even sample splitting. Their work leaves the corresponding high-dimensional optimality question open, so it does not establish the paper’s main Bernoulli lower-bound result. However, it should be included in the discussion of novelty.

W2. The authors should add a small experiment that varies the network size and the number of structural groups while keeping the relevant signal and noise levels comparable. Testing unequal group sizes would also help clarify the role of the smallest edge group.

Questions for authors

N/A

3 comments
AuthorsOpenReview ↗

Response to Reviewer kr6d: Comparison with literature and controlled experiment on network strcutures

Summary. Thank you for the reference and for the experiment design. We added Kovács et al. (2024) with an explicit statement of what it already establishes, and we ran the controlled study you proposed, varying network size, group count and group imbalance at fixed total signal (Section 6.2, Table 3, Figure 4). The results you highlighted as Theorems 6 and 7 are now Theorems 2 and 3, and the variance-drift analysis behind Equation (2) is in Appendix B.

W1: Kovács et al. (2024)

In the dense specialization of their Theorem 6 (fixed segment fractions, coordinate variance σ2\sigma^2, squared mean jump ss), the integer-scale upper rate is σ2/s+dσ4/(Ts2)\sigma^2/s+d\sigma^4/(Ts^2) up to iterated logarithms, and their Section 5.1 uses odd/even splitting. We now credit both directly.

Our contribution is the lower-bound side in the Bernoulli setting. The term Dρ2/(Tδ4)D\rho^2/(T\delta^4) is unavoidable over unrestricted changes, a supplied partition into dd aligned cells replaces DD by dd, and normalized cell sums match that structured benchmark up to logarithms. The new step conditions on the post-change observations shared by nearby alternatives, which carry information about the random jump signs.

Where: Section 1; Section 4 and Table 1 (pp. 5–6); Appendix A.1 (p. 13).

W2: Network size, group count and unequal groups at controlled signal

Each configuration has 200 replicates, T=160T=160, τ=64\tau=64, cap ρ=0.20\rho=0.20, pre-change probability 0.15 on every edge, and independent cell signs with hb=sbδ2/(2dbNb)h_b=s_b\sqrt{\delta^2/(2d_{\rm b}N_b)}. This fixes ∥P2−P1∥F2=δ2\Vert P_2-P_1\Vert_{\rm F}^2=\delta^2 exactly, gives each cell equal jump energy and gives full retention by the block map. All probabilities lie in [0.10,0.20][0.10,0.20], and the baseline block covariance is 0.1275Idb0.1275I_{d_{\rm b}}.

Change (MAE; SEs in Table 3)Raw edgesBlock sums
n=64→192n=64\to192, K=4K=4, δ2=0.6\delta^2=0.618.150 → 26.5601.350 → 1.585
K=2,4,8K=2,4,8, n=96n=96, δ2=0.06\delta^2=0.0631.410, 29.050, 27.49013.460, 18.405, 23.360
Sizes (24,24,24,24), (12,20,28,36), (6,18,30,42); δ2=0.6\delta^2=0.622.875, 20.505, 24.0201.415, 1.195, 1.410
  • Network size. The block dimension stays at 10 while DD grows from 2,016 to 18,336. Raw error rises by 8.410 (SE 1.766); block error changes by 0.235 (SE 0.230).

  • Group count. With db=3,10,36d_{\rm b}=3,10,36, block error rises by 9.900 (SE 1.649) from K=2K=2 to K=8K=8.

  • Imbalance. Block MAE remains stable across the tested group sizes: 1.415, 1.195 and 1.410, with most unequal minus balanced equal to −0.005 (SE 0.255). This is consistent with the normalization: dividing by Nb\sqrt{N_b} keeps each coordinate’s variance at most ρ\rho. The theory makes the role of cell size explicit through the aggregation condition and admissible jump range. We report both the smallest cells (276, 66 and 15 edges) and Nmin⁡Tρ/log⁡(eT)≥79N_{\min}T\rho/\log(eT)\ge79, linking the experiment directly to these quantities.

The full design has 38 configurations and 7,600 unique sequences, with all four methods and all signal levels reported.

Where: Section 6.2, Table 3 and Figure 4 (pp. 7–9); the imbalance argument in Section 3.1 (p. 5); Appendix H.2 (p. 27) and Tables 7–9 (pp. 28–29).

We hope the expanded comparison and controlled experiments address both concerns you raised. We would appreciate your reassessing the revised paper and considering an update to your score in light of these additions.

AuthorsOpenReview ↗

Follow up: Adding the requested controlled experiments and clarifying the Kovács comparison

Thank you again for suggesting the controlled experiments and the comparison with Kovács et al. We wanted to provide a brief pointer to the completed additions as the discussion period approaches its close.

The central results you highlighted remain at the heart of the paper: submitted Theorems 6–7 are now Theorems 2–3, with the corresponding structured upper bound in Corollary 4. The revision makes their interpretation more explicit and adds the evidence you requested.

  • Controlled experiments — Table 3 and Figure 4, p. 9. We vary network size, group count, and group imbalance while holding total signal fixed. For example, increasing the number of vertices from 64 to 192 with four groups raises raw-edge localization error from 18.150 to 26.560, while block-sum error changes from 1.350 to 1.585. The adjacent comparisons isolate group count and imbalance.
  • Kovács et al. — Section 4 and Table 1, pp. 5–6. We explicitly credit their Gaussian two-term upper bound and sample splitting, and explain the role of our Bernoulli lower bounds and the comparison between unrestricted and supplied-group classes.

Could you please let us know whether these additions address the two concerns in your review? We would be happy to clarify the experimental design or theoretical comparison directly here. If they resolve your concerns, we would be grateful for your reconsideration of the assessment and score.

AuthorsOpenReview ↗

Follow-up on the requested experiments and prior-work comparison

Thank you again for your constructive suggestions. As the discussion approaches its close, could you let us know whether the controlled experiments on network size, group count, and imbalance (Table 3 and Figure 4, p. 9), together with the explicit Kovács et al. comparison (Section 4 and Table 1, pp. 5–6), address the two concerns in your review?

As the discussion period is nearing its end we would appreciate your updated assessment and would be happy to clarify any specific point during the remaining discussion.

Reviewer_kfFzOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper studies when structural information improves localization of a change in a sequence of networks. For independent Bernoulli networks with one change, it analyzes summaries that reduce dimension while retaining the change signal. The main contributions are finite-sample localization bounds and lower bounds showing when the reduction in dimension provides a statistical advantage, particularly for a known grouping of edges.

Critical strengths
  • Understanding when a network summary improves localization, and when it discards useful information, is a relevant question.
  • The lower bounds appear to provide a useful contribution beyond the existing upper-bound analyses. The main arguments look coherent, and the experiments illustrate both beneficial and harmful compression.
Critical weaknesses
  • Unclear motivation and setting: The introduction moves quickly into rates and comparisons with existing methods without adequately introducing the statistical problem. The reader is expected to understand the distinction between a structural model, a fixed network summary, and a representation learned from data. A simple example explaining what is known and what must be estimated would make the setting much clearer.
  • Inadequate comparison with prior results: Wang, Yu, and Rinaldo already study localization in independent Bernoulli networks and exploit structure. Wang and Shao provide a closely related statistic and the dimension-dependent error scale underlying the upper bound. The paper explicitly acknowledges these connections, and the new lower bounds address an additional regime. However, a direct comparison of assumptions and conclusions is needed to explain the significance of this advance.
  • Unfocused presentation: The lower bounds compete with general linear maps, nonlinear representations, sample splitting, and numerous experimental checks. Some passages also refer to earlier confounds and revisions without providing useful context. The paper would benefit from a more focused explanation of the central result and the proof idea that distinguishes it from existing analyses.
  • Unclear consequences when structure is unknown: Outside the known-grouping example, the benefit of a representation depends on how much of the unknown change it preserves. The sample-splitting result ensures valid evaluation, but does not show that the selected representation is useful or close to the best choice. These limitations are acknowledged, but the practical implications of the analysis remain insufficiently explained.
Questions for authors
  • How do the assumptions, signal regimes, and conclusions differ from those of Wang, Yu, and Rinaldo?
  • What is the main additional argument needed for the new lower bound, and why is it not implied by the earlier localization results?
  • Can the authors give a concrete example where the theory helps choose a network summary without already knowing the change direction or the correct grouping?
5 comments
AuthorsOpenReview ↗

Response to Reviewer kfFz (1/2): Clarifying structural information and positioning our localization results

Summary. Thank you for your questions on how structural information enters the problem. They motivated a clearer presentation of supplied structure, fixed summaries and learned summaries. We rewrote the introduction around one concrete example, now also drawn as Figure 1, and moved the lower-bound comparison to the center of the main text. We also added a direct comparison with Wang, Yu and Rinaldo (Section 4), a fully specified group-learning rule (Proposition 12) and an equal-budget study of learned structure (Section 6.3). Locations refer to the revised PDF.

W1: Motivation; known, fixed and learned structure

Take 96 vertices in four supplied groups: 4,560 edges and ten group-pair cells. Suppose both probability matrices are constant on each cell. The groups are known; the cell levels, the signs and sizes of their jumps, and the change time are unknown. For a cell with NbN_b edges and per-edge jump hbh_b, summing its edges and dividing by Nb\sqrt{N_b} gives a feature. The ten features retain squared jump ∑bNbhb2=∥Δ∥2\sum_bN_bh_b^2=\Vert\Delta\Vert^2, where Δ\Delta is the edge-vector jump. They can be computed without knowing the jump signs or magnitudes. An estimator that sees every edge can compute the same sums. The supplied partition improves localization by restricting the possible change directions while preserving the full jump.

SettingSupplied or estimatedWhat we show
Supplied aligned groupsPartition known; means and change time unknownLower bound with dd in place of DD; cell sums attain it up to logarithms
Fixed map, arbitrary networkMap fixed in advance; no alignment assumedError depends on retained signal as well as dimension
Learned or selected mapGroups or map estimated from a pilot or the even snapshotsRecovery transfers to localization; splitting gives conditional validity

Where: Section 1 and Figure 1 (pp. 1–2); Section 2 (from p. 3); Theorems 2–3 and Corollary 4 (p. 4).

W2 and Q1: Wang, Yu and Rinaldo; Wang–Shao

For one change with segments of order TT, the local-refinement condition of Wang, Yu and Rinaldo (2021) reads Tδ2≳rWnρlog⁡2+2ξTT\delta^2\gtrsim r_{\rm W}n\rho\log^{2+2\xi}T, with error ρlog⁡2T/δ2\rho\log^2T/\delta^2, where rWr_{\rm W} is their rank parameter; they also assume nρ≥log⁡nn\rho\ge\log n and suitable initialization. With unrestricted rank rW≍nr_{\rm W}\asymp n this requires Tδ2≳ρDT\delta^2\gtrsim\rho D up to logarithms, which is the upper end of the range ρD≲Tδ2≲ρD\rho\sqrt D\lesssim T\delta^2\lesssim\rho D where our dimension term dominates. The two results fit together: theirs gives the scalar rate under strong signal, and ours shows what is unavoidable below it. Section 4 also distinguishes the roles of rank restrictions and supplied structural information in the respective parameter classes.

Wang and Shao (2023) supply the distinct-index contrast and the covariance-dependent scale ∥ΣF∥F2/(TκF4)\Vert\Sigma_F\Vert_{\rm F}^2/(T\kappa_F^4) under additive i.i.d. noise, whereas Bernoulli covariances move with the mean. Section 2 states the exact algebraic relation between their statistic and ours. Kovács et al. (2024) give a two-term Gaussian upper bound and odd/even splitting, and we credit both.

Where: Section 4 and Table 1 (pp. 5–6); Appendix A.1 (p. 13).

AuthorsOpenReview ↗

Response to Reviewer kfFz (2/2): Explaining the lower bound and demonstrating gains from learned structure

W3 and Q2: The central result and the new lower-bound step

The main claim is the unrestricted lower benchmark RD=min⁡{T,ρ/δ2+Dρ2/(Tδ4)}R_D=\min\{T,\rho/\delta^2+D\rho^2/(T\delta^4)\} and its dd-cell counterpart RdR_d, both over all estimators that observe the full sequence, in the theorems’ stated ranges. Normalized cell sums attain RdR_d up to logarithms under the aggregation condition.

The proof combines a fixed-direction construction for the scalar term with a random-sign construction for the dimension term. For the latter, we draw one sign per edge and compare two change locations uu apart. The two alternatives share a post-change suffix, and those observations carry information about the signs, so a localization proof must account for them. We condition on the suffix. With baseline p=3ρ/4p=3\rho/4, amplitude a=δ/2Da=\delta/\sqrt{2D} and c=a2/{p(1−p)}c=a^2/\{p(1-p)\}, the posterior sign mean mm after bb suffix observations satisfies Em2≤2bc\mathbb E m^2\le2bc, and this yields

KL(M0∥M1)≤C uTδ4/(Dρ2)(Tc≤1).\mathrm{KL}(M_0\Vert M_1)\le C\,uT\delta^4/(D\rho^2)\qquad(Tc\le1).

Choosing u≍min⁡{T,Dρ2/(Tδ4)}u\asymp\min\{T,D\rho^2/(T\delta^4)\} keeps the alternatives indistinguishable, and one sign per cell gives the dd-cell version. Accounting for information about the direction outside the disputed interval is the localization-specific step that establishes the necessity of this term.

The main text now runs from the model to the lower bounds and structured upper bound, the proof idea, the closest work, learned structure and the experiments.

Where: Section 3 (pp. 4–5); proof idea in Section 3.2 (p. 5); full proof in Appendix D (p. 20).

Q3: Choosing groups without knowing the direction or the grouping

Proposition 12 gives a fully specified rule. Take an independent stationary pilot of T0T_0 networks with the same unknown groups, each with at least three vertices and a distinct probability profile. Form the mean adjacency Aˉ0\bar A^0, join u,vu,v when max⁡w∉{u,v}∣Aˉuw0−Aˉvw0∣≤2log⁡(2D/α)/(2T0)\max_{w\notin\{u,v\}}|\bar A^0_{uw}-\bar A^0_{vw}|\le2\sqrt{\log(2D/\alpha)/(2T_0)}, and use the connected components as groups. The rule uses neither the number of groups, the profile separation gg, the change time nor the direction. Writing gg for the minimum maximum-coordinate separation between distinct population profiles, if T0g2>8log⁡(2D/α)T_0g^2>8\log(2D/\alpha) the rule recovers the groups with probability at least 1−α1-\alpha, and under the aggregation condition the expected localization error is bounded by the known-group upper rate plus αT\alpha T. Lemma 10 and Corollary 11 connect group-estimation accuracy to localization through retained signal. Proposition 12 thus gives an explicit end-to-end pilot procedure, complemented by the spectral-learning experiments in Section 6.3.

Where: Section 5 (p. 6); Proposition 12 in Appendix A.3.2 (p. 16); Appendix A.3.1 (p. 15).

W4: Is a learned representation useful, beyond valid?

We address practical usefulness directly through a new equal-budget study. Proposition 13 and Corollary 14 establish conditional validity, and Table 4 measures the gains from learned representations using the same 160 snapshots for every arm. The even half learns spectral partitions (K=2,…,6K=2,\ldots,6) and selects among them, degrees and raw edges; the odd half localizes.

Selected/odd improves on raw/full in eight of nine settings, with paired pointwise 95% Monte Carlo intervals excluding zero in all eight. Representative MAEs from Table 4 are:

Design and squared signalRaw/fullSelected/odd
Block, δ2=0.6\delta^2=0.624.4804.750
Chung–Lu, δ2=1.8\delta^2=1.812.5108.940
Degree-blind, δ2=0.6\delta^2=0.623.0054.580

The matched comparisons also show how closely learning can track supplied structure. For block changes at the three signal levels, selected/odd MAEs are 4.750, 0.990 and 0.540, compared with 4.280, 0.860 and 0.360 for the supplied reference on the same odd observations.

In the degree-blind design, the selector chooses K=2K=2 in 79.5–87.5% of runs and retains 0.9996–1.0000 of the signal. This demonstrates that a learned grouping can preserve the change even when it is coarser than the four baseline groups. The fixed-K=4K=4 block candidate has mean misclustering below 3% across the three signal levels, with odd-sample MAE decreasing from 4.290 to 0.910 to 0.600 (Table 12). The full diagnostics connect these gains to retained signal and the pooled population profiles.

Where: Section 6.3 and Table 4 (pp. 9–10); Appendix H.3 (p. 29); Tables 10–12 (p. 30) and Table 18 (p. 39).

These revisions provide concrete answers to your questions on motivation, novelty and learned structure. We would be grateful if you could reassess the revised paper and consider updating your score in light of the added theory, experiments and exposition.

AuthorsOpenReview ↗

Follow up: Clarifying the original contribution and demonstrating the value of learned structure

Thank you again for your detailed comments. As the discussion period approaches its close, we wanted to highlight the revisions most directly connected to your questions.

The central contribution remains the submitted paper’s comparison between unrestricted network changes and changes aligned with supplied groups. Submitted Theorems 6–7 and Corollary 8 now appear together as Theorems 2–3 and Corollary 4. The revised exposition brings this comparison forward, while the additional analysis and experiments address your questions about its interpretation and practical use.

Three focused locations summarize these changes:

  • Contribution and relation to prior work — Sections 3.2–4 and Table 1, pp. 5–6. These explain the lower-bound argument and distinguish the Bernoulli localization benchmark from the existing upper bounds and strong-signal guarantees.
  • Learning unknown groups — Section 5, p. 6, and Proposition 12, p. 16. We give an explicit independent-pilot construction that recovers the groups without knowing their number or the change direction and transfers recovery to a localization guarantee under the stated conditions.
  • Practical usefulness — Table 4, p. 10. Using the same total observation budget, the learned/selected representation improves localization over raw edges in eight of nine settings.

It would be particularly helpful to hear whether the direct comparison and the learned-structure results address your concerns about the contribution and practical usefulness. We would be happy to clarify any specific point here. If these additions resolve your concerns, we would be grateful for your reconsideration of the assessment and score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Revision overview: clearer exposition, explicit guarantees, and new experiments

We thank the reviewers for their detailed feedback. We have completed a revision that makes the central contribution easier to assess, develops an explicit group-learning guarantee, and adds experiments directly motivated by the reviews. The revised manuscript has ten pages of main text. Blue identifies substantive additions; editorial improvements and reorganization appear in black.

Central contribution

For one change in independent Bernoulli networks, we establish the two-term minimax lower benchmark

RD=min⁡{T,ρ/δ2+Dρ2/(Tδ4)},R_D=\min\{T,\rho/\delta^2+D\rho^2/(T\delta^4)\},

in the stated signal range. Here TT is the number of snapshots, DD the number of possible edges, ρ\rho the probability cap, and δ\delta the Frobenius jump. The second term quantifies the cost of an unknown high-dimensional change direction. When both regime means are constant on dd supplied edge groups, dd replaces DD in the lower bound, and normalized group sums attain the resulting benchmark up to logarithms under the aggregation condition.

What we changed in response to the reviews

  • A concrete introduction and definitions before the results. Sections 1–2 now introduce the problem through 96 vertices in four supplied groups: 4,560 edges represented by ten normalized group-pair sums. New Figure 1 shows how those sums preserve the full jump. The text clearly distinguishes supplied structure, fixed representations and learned representations, and defines the notation before the formal results (pp. 1–4).

  • A visible theoretical contribution and precise comparisons. Theorems 2–3 and Corollary 4 now anchor the main text. Section 3.2 explains the lower-bound step that accounts for information about the jump direction in the post-change observations shared by nearby alternatives. Section 4 and Table 1 compare assumptions and rates with Wang, Yu and Rinaldo, Wang–Shao, and the newly added Kovács et al. reference (pp. 4–6).

  • An explicit construction for learning groups. New Proposition 12 gives a fully specified independent-pilot procedure that learns the groups and their number under explicit profile-separation conditions. Lemma 10 and Corollary 11 connect group-estimation accuracy to retained signal and localization. The construction is summarized in Section 5 (p. 6), with the full results in Appendix A.3 (pp. 15–16).

  • Controlled experiments on the quantities in the theory. Following kr6d’s suggestion, we vary network size, group count and group imbalance at fixed total signal. The study covers 38 configurations and 7,600 unique sequences, with 200 replicates per configuration. Section 6.2, Table 3 and Figure 4 present the comparisons (pp. 7–9); Appendix H.2 gives the full grids.

  • Quantified gains from learned structure at a common budget. Addressing kfFz’s question about practical usefulness, the new paired comparison evaluates learning and selection using the same total budget of 160 snapshots. Selected representations improve on raw-edge localization in eight of nine settings, with paired pointwise 95% Monte Carlo intervals excluding zero in all eight. For the weak block change, MAE improves from 24.480 to 4.750. Section 6.3 and Table 4 report the results (pp. 9–10), with learning and selection diagnostics in Appendix H.3.

Numbering guide

Submitted versionRevised version
Theorems 6, 7Theorems 2, 3
Corollary 8Corollary 4
Lemma 9Lemma 10
Proposition 12, Corollary 13Proposition 13, Corollary 14
Theorem 2, Corollaries 3–5Theorem 5, Corollaries 6–8 (Appendix A)
Theorem 11Theorem 18 (Appendix F)
Proposition 14Proposition 15
Appendix A (variance drift)Appendix B
Appendix C (lower-bound proof)Appendix D

Equation (2) retains its number.

Suggested reading path

Section 1 with Figure 1; Section 2; Theorems 2–3 and Corollary 4; the proof idea in Section 3.2; and the prior-work comparison in Section 4. Sections 6.2–6.3 then provide the new experimental evidence. Our individual replies give a concern-by-concern account of the completed changes.

We would be grateful for the reviewers’ reassessment of the revised manuscript and consideration of updated scores in light of these additions.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.