{"id":"e42e882a-358a-4731-be48-f3d51ea5ce73","arxiv_id":"1908.01823","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A graphon-estimation-based screening and thresholding procedure detects multiple change-points in dynamic networks, achieving a faster rate than simple averaging when the number of nodes exceeds the number of time points.","lead":"This paper presents a method for finding change-points in networks that evolve over time, by first estimating the underlying connection probabilities with a smoothing step and then scanning for abrupt changes. It offers theoretical guarantees and shows better performance than an existing graph-based test in simulations and on a real Bluetooth proximity dataset.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.1 proof gap: event xi_n does not preclude multiple h-local maxima near a true change-point, so J_hat=J does not follow from Delta*/Delta_D>1 alone.","rationale":"After working through the proofs, the MNBS estimation bound in Theorem 3.2 appears internally consistent under its stated assumptions. The vulnerability is in the proof of Theorem 4.1: the event xi_n is too weak to force J_hat=J. The proof establishes a surjection from the estimated change-point set to the true change-point set, but not injectivity. For a true change-point tau, the missing control is on D(t,h) for t within h of tau but t != tau. When h is large, as recommended in practice with h = sqrt(T), the curvature of the true scan statistic around tau is O(Delta*/h), while the estimation noise in D is O(sqrt(Delta* err)); the ratio can be large once h >> (log n)^{delta_0/2}. Under the theorem's separation condition Delta*/Delta_D > 1, this is not excluded, so the claimed consistency is not established by the given argument. This concern is distinct from the reader's temporal-dependence worry: that is an external-validity limitation, while this is an internal proof gap. The simulations and tuning recommendations may avoid the problem empirically, but the theorem's statement requires either a stronger signal condition or a separate argument ruling out multiple local maxima. I therefore keep the overall verdict conditional, with the primary condition being a corrected proof of Theorem 4.1.","tokens_in":25826,"tokens_out":40211,"duration_ms":403096,"concrete_test":"Re-derive the implication in the proof of Theorem 4.1 with an augmented event that also requires D(tau,h) > D(t,h) for all t in [tau-h+1, tau+h-1] \\ {tau}, and compute the minimal Delta*/Delta_D needed to make this event hold with probability tending to 1 using the Theorem 3.2 error bounds. If the required condition is Delta* >> Delta_D * h^2 (log n)^{-delta_0} (or any condition stronger than >1), then Theorem 4.1's separation condition is insufficient as stated. A complementary simulation would use a single change-point with n=2000, T=500, h=22, Delta* = 1.5 Delta_D and check whether J_hat > 1 occurs at a non-negligible rate.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Section 4.2's proof of Theorem 4.1 defines xi_n = (intersection over true change-points A_tau) intersection (intersection over flat points B_t) and claims xi_n implies {J_hat=J} intersection {J within J_hat +/- h}. The argument shows (i) every point in J_hat lies within h of exactly one true change-point and (ii) every true tau has at least one h-local maximizer in [tau-h+1, tau+h-1] with D > Delta_D. It does not show that this local maximizer is unique. For t = tau +/- k with 1 <= k < h, the true scan statistic is ((h-k)/h)^2 Delta_j, which can exceed Delta_D when Delta*/Delta_D is any constant greater than 1. The separation between D(tau,h) and D(tau +/- 1,h) is about 2 Delta*/h, while the estimation noise in D is of order sqrt(Delta* * err), with err = (log n)^{1/2}/(n^{1/2} h^{1/2}). Since Delta_D / err = (log n)^{delta_0}, the noise-to-curvature ratio is about h (log n)^{-delta_0/2}; for h much larger than (log n)^{delta_0/2}, the noise dominates and additional local maxima above Delta_D are not excluded by xi_n. The proof therefore does not establish J_hat=J under Delta*/Delta_D>1 alone; a stronger signal condition or a new argument controlling D(t,h) on the entire h-neighborhood is needed.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a multiple change-point detection procedure for dynamic networks, built on a modified neighborhood smoothing (MNBS) estimator for the link probability matrix. Section 3 introduces MNBS for repeated observations of a network and proves an error bound (Theorem 3.2) under a piecewise Lipschitz graphon model. Section 4 develops a screening-and-thresholding algorithm based on local MNBS estimates over windows of size h, with a detection threshold ΔD, and states a consistency result (Theorem 4.1): under h < D*/2 (D* the minimum segment length) and lim Δ*/ΔD > 1, the procedure satisfies P({Ĵ = J} ∩ {J ⊂ Ĵ ± h}) → 1, i.e., exact recovery of the number of change-points and window-localized estimation of their positions. Numerical experiments on synthetic stochastic block model dynamics and an MIT proximity network illustrate the method's practical performance, with comparisons to graph-based scan methods.","tokens_in":26176,"tokens_out":15003,"duration_ms":142008,"significance":"If the main results are correct, the paper makes a valuable contribution to change-point detection in dynamic networks: it proposes a nonparametric approach that exploits network structure, provides a graphon-estimation error rate that improves with both n and T, and uses a d_{2,∞}-based signal measure that is weaker than Frobenius-norm conditions used in earlier work. The theorems are stated in a parameter-free way (holding for any positive tuning constants B0, D0, δ0), which is a strength, and the numerical comparisons show competitive or superior performance relative to existing methods. However, the central consistency theorem (Theorem 4.1) has a proof gap concerning the uniqueness of local maximizers, which is load-bearing for the claimed exact recovery of the change-point set; the stated signal condition is insufficient as written for the conclusion to follow.","major_comments":[{"comment":"The event ξ_n only controls D(t,h) at exact change-points τ ∈ J and at h-flat points t ∈ F_h. It does not control D(τ±k,h) for 1 ≤ k < h, because those indices are not h-flat. Consequently, the proof does not rule out multiple h-local maximizers above ΔD within the same h-neighborhood of a true change-point. The argument establishes that each estimated point has exactly one true change-point within distance h and each true change-point has at least one estimated point within distance h, but it does not establish that each true change-point has at most one estimated point. The claimed implication ξ_n ⇒ {Ĵ = J} therefore does not follow. The issue is not merely technical: under the stated condition lim Δ*/ΔD > 1, the deterministic signal near a true change-point decays as (1 − k/h)^2 Δ*, so D(τ,h) − D(τ+1,h) is of order Δ*/h, while the estimation noise in D is of order √(Δ* err) with err = (log n)^{1/2}/(n^{1/2} h^{1/2}). The noise-to-signal ratio for this decrement is of order h (log n)^{−δ0/2}, which diverges when h grows faster than (log n)^{δ0/2}. Thus, for large h, the event ξ_n does not preclude additional local maxima above ΔD near a single true change-point, and the conclusion {Ĵ = J} is not established by the given proof. A stronger signal condition (e.g., Δ*/ΔD growing with h) or a new argument controlling D(t,h) on the entire h-neighborhood is needed.","section":"Section 9, proof of Theorem 4.1"},{"comment":"The theorem and the algorithm description lack explicit boundary assumptions. The scan statistic D(t,h) is defined only for t = h, ..., T−h, but the definition of an h-local maximizer in Section 4.1 requires comparing D(x,h) with D(t,h) for all t in [x−h+1, x+h−1]; for x near the boundaries, this interval includes indices where D(t,h) is not defined. Similarly, Theorem 4.1 does not state that the true change-points lie in [h, T−h], which is necessary for the windows used in the proof to be fully observed. These conditions should be made explicit, and the proof should address the boundary cases or exclude them by assumption.","section":"Section 4.1 and Theorem 4.1"}],"minor_comments":[{"comment":"In the concluding paragraph of the proof, “for any point ˆτ∈J” should read “for any point ˆτ∈Ĵ”, since J denotes the true change-point set and Ĵ the estimated set.","section":"Section 9, proof of Theorem 4.1"},{"comment":"The notation “J⊂: Ĵ±h” is confusing; suggest writing the coverage condition explicitly as: for each j = 1, ..., J, there exists ␣τ_j ∈ Ĵ with |␣τ_j − τ_j| < h, and |Ĵ| = J.","section":"Theorem 4.1"},{"comment":"The text says “The performance of MNBS and CZ are summarized in Table 6”, but the displayed table in the main text is Table 1; the cross-reference should be corrected.","section":"Section 5.1"},{"comment":"The abstract claims a faster convergence rate in detecting change-points compared with an algorithm that simply averages information across time, but Theorem 4.1 provides only window-consistency with no rate for localization error, and no formal detection-rate comparison with an averaged-information detector is given. The claim is supported for graphon estimation (Theorem 3.2) but not for change-point detection; consider rewording or supplying a formal rate statement.","section":"Abstract and Section 3"}],"recommendation":"major_revision","confidential_remarks":"The gap in the proof of Theorem 4.1 is substantial: the uniqueness of h-local maximizers near a true change-point is not established, and the stated condition Δ*/ΔD > 1 appears insufficient in general when h grows with n. This is the central theoretical claim of the paper, so the authors need to either strengthen the signal condition, add a more refined argument, or weaken the theorem to a two-sided Hausdorff-type guarantee. The MNBS estimation result (Theorem 3.2) and the numerical study are valuable, so a major revision rather than rejection seems appropriate if the theorem can be repaired."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read this one. It's a strong candidate for peer review, but the main theorem has a genuine proof gap that needs to be addressed before publication.\n\nThe paper extends the neighborhood smoothing estimator of Zhang, Levina and Zhu (2017) from a single network to repeated observations, and adds a screening-and-thresholding change-point detection procedure. The MNBS estimator's error rate improves with both n and T, which is a meaningful advance for large dynamic networks. The consistency theorems are proved in detail via standard concentration arguments, and the theory is parameter-free in the sense that consistency holds for any positive tuning constants. The simulations are extensive, comparing against the Chen-Zhang graph-based test, and the real data example is a nice touch. The 'model-free' description is too strong: the theory relies on piecewise Lipschitz graphons with i.i.d. latent variables and independent snapshots across time. That's nonparametric within the graphon family, not model-free.\n\nThe main problem is the proof of Theorem 4.1. The event xi_n only controls the scan statistic D(t,h) at true change-points and at flat points (points whose h-window contains no change-point). It does not control D(t,h) for other non-flat points near a change-point. To conclude J_hat = J, you need to rule out multiple h-local maximizers above the threshold within the same h-neighborhood of a true change-point. The proof doesn't do that. For t = tau + k with k < h, the true (noiseless) scan statistic is ((h-k)/h)^2 Delta_j, which can exceed Delta_D even when Delta*/Delta_D > 1 by an arbitrarily small margin. The separation between adjacent D(t,h) values is about 2 Delta*/h, while the estimation noise is of order sqrt(Delta* * err). For h much larger than (log n)^{delta_0/2}, the noise dominates and multiple local maxima can appear. So as stated, the proof doesn't establish J_hat = J from the assumed signal condition alone. The theorem may still be true with a stronger signal condition, or with a uniform bound on D(t,h) over the whole h-neighborhood, but that needs to be supplied.\n\nMinor point: the independence across time assumption is restrictive. Real dynamic networks often have temporal dependence, and the paper doesn't address it. That's a limitation, not a mistake.\n\nBottom line: this is a serious paper, the gap is fixable, and it deserves a proper peer review. I'd send it out, with referees asked to focus on the proof of Theorem 4.1.","headline":"A solid methodological extension of neighborhood smoothing to dynamic networks with a real, fixable gap in the proof of the main consistency theorem.","tokens_in":26653,"tokens_out":3522,"would_cite":false,"duration_ms":32939,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62G20","62H12","62M10"],"pacs":[],"model":"deepseek-v4-flash","headline":"A two-stage graphon-smoothing procedure consistently recovers the number and locations of change-points in dynamic networks.","keywords":["change-point detection","dynamic networks","graphon estimation","neighborhood smoothing","link probability matrix","scan statistics","consistency","stochastic block model"],"falsifier":"Generate a dynamic network from a stochastic block model where node memberships gradually drift across time (e.g., a small fraction of nodes switch blocks between segments), or where adjacency matrices are generated with first-order temporal dependence at fixed $P$; then run the MNBS procedure with $h=\\sqrt{T}$ and check empirically whether the estimated change-point set still satisfies the sure-coverage event. A clean calculation would also verify the threshold condition: if $\\Delta_*/\\Delta_D \\le 1$, the proof's key inequality fails and the procedure should lose detection power, so a simulation at the boundary $\\Delta_*/\\Delta_D$ just below 1 provides a direct test.","tokens_in":25646,"feed_emoji":"🕸️","tokens_out":4443,"duration_ms":42164,"temperature":0.7,"pith_summary":"The paper proposes a two-stage procedure for detecting when the link structure of a network changes over time. First, it estimates the underlying link probability matrix in each time window using a modified neighborhood smoothing (MNBS) estimator that averages adjacency matrices across time while shrinking the smoothing neighborhood. Second, it scans local windows, computes a $d_{2,\\infty}$ distance between the two estimated matrices, and thresholds local maximizers. The paper proves that, under a piecewise Lipschitz graphon model, the procedure consistently recovers the true number and window-localized positions of all change-points, and that the estimation error decreases with both the number of nodes and the number of temporal snapshots. The practical payoff is a model-free detector that exploits network structure rather than collapsing networks to scalar summaries.","feed_headline":"Smoothing network snapshots reveals every change-point","feed_subtitle":"A graphon-based detector recovers both the number and locations of change-points, faster when nodes outnumber time points.","key_machinery":"The central object is the modified neighborhood smoothing (MNBS) estimator, a temporal extension of neighborhood smoothing: for each node $i$, form a neighborhood $N_i$ of nodes with similar row-wise connection patterns in the averaged adjacency matrix $\\bar{A} = (1/T)\\sum_t A^{(t)}$, using a distance measure $\\tilde{d}(i,i') = \\max_{k \\neq i,i'} |\\langle \\bar{A}_{i\\cdot} - \\bar{A}_{i'\\cdot}, \\bar{A}_{k\\cdot} \\rangle|$, then estimate $P_{ij}$ by averaging $\\bar{A}_{i'j}$ over $i' \\in N_i$. The key modification is shrinking the neighborhood quantile $q$ from $C(\\log n/n)^{1/2}$ to $C\\log n/(n^{1/2}\\omega)$, trading increased variance (compensated by averaging over $T$ snapshots) for reduced bias. The detection stage uses the $d_{2,\\infty}$ distance between MNBS estimates from windows before and after each time $t$, followed by thresholding of local maximizers.","core_discovery":"The paper establishes that change-point detection in a dynamic network can be reduced to estimating link probability matrices and then scanning for differences. The MNBS estimator pools $T$ adjacency matrices, shrinking the neighborhood size from $q \\sim (\\log n/n)^{1/2}$ in the single-network NBS to $q \\sim \\log n/(n^{1/2}\\omega)$ with $\\omega = \\min(n^{1/2}, (T\\log n)^{1/2})$, achieving $d_{2,\\infty}(\\tilde{P}, P)^2 = O(\\log n/(n^{1/2}\\omega))$. The detection procedure then computes $D(t,h) = d_{2,\\infty}(\\tilde{P}_{t1,h}, \\tilde{P}_{t2,h})^2$ on a sliding window of length $h$, collects $h$-local maximizers, and keeps those above a threshold $\\Delta_D$ of order $(\\log n)^{1/2+\\delta_0}/(n^{1/2}h^{1/2})$. Theorem 4.1 states that if $h < D_*/2$ (the minimal segment length halved) and the minimum signal $\\Delta_*$ exceeds the threshold asymptotically, then $P(\\{\\hat{J} = J\\} \\cap \\{J \\subset \\hat{J} \\pm h\\}) \\to 1$; if the signal is strong enough, setting $h=1$ recovers exact change-point locations, in contrast to the classical $O_p(1)$ localization error for scalar time series.","pith_inferences":["If the graphon model is right, the principle of shrinking smoothing neighborhoods in proportion to available temporal samples could extend to other dynamic-network tasks such as community detection or link prediction, where repeated observations should reduce bias rather than only variance.","The fixed, i.i.d. latent-position assumption is a natural stress point; a testable extension would allow small, smooth drift in latent positions between segments and ask how much drift the $d_{2,\\infty}$ separation condition can tolerate before consistency breaks.","The rates are derived for undirected networks; adapting MNBS to directed or weighted networks would require redefining the distance measure and the bias-variance decomposition, but the screening-thresholding structure would likely survive.","The window constraint $h < D_*/2$ and the practical recommendation $h = \\sqrt{T}$ mean that segments shorter than $2\\sqrt{T}$ may be missed; a sensitivity analysis of the $h$-versus-$D_*$ trade-off would clarify the procedure's practical limits."],"forward_implications":["When nodes outnumber time points ($n > T$), the detection rate improves with both $n$ and $T$, beating methods that average the network into a single time series.","Exact localization (zero error) becomes possible when the change signal is strong enough, unlike classical time-series change-point detection where localization error is $O_p(1)$.","The procedure is model-free within the graphon class, covering Erdős–Rényi and stochastic block models as special cases.","The same MNBS estimates provide post-hoc network estimation, so detection and estimation come from one pipeline.","The separation condition is stated in $d_{2,\\infty}$ norm, which is weaker than Frobenius-norm separation used in prior work, so changes affecting few nodes (e.g., one node switching membership) remain detectable."],"supporting_citations":[{"why":"Supplies the original neighborhood smoothing estimator and the piecewise Lipschitz graphon framework that MNBS extends to the temporal setting.","marker":"[39]"},{"why":"Provides the universal singular value thresholding method and matrix concentration inequalities used in the modified USVT alternative and in bounding estimation error.","marker":"[6]"},{"why":"Serves as the graph-based nonparametric testing baseline that MNBS is compared against in simulations and on the MIT proximity data.","marker":"[7]"},{"why":"Offers the information-theoretic change-point detection approach for sparse dynamic networks that the paper contrasts with its network-aware, post-hoc-estimating procedure.","marker":"[34]"},{"why":"Supplies the MIT proximity network data set used in the real data application illustrating the procedure.","marker":"[9]"},{"why":"Establishes the classical $O_p(1)$ localization error for scalar time-series change-points, which the paper contrasts with exact localization under strong signals.","marker":"[37]"},{"why":"Defines the Boysen distance used to measure under- and over-segmentation errors in the numerical evaluations.","marker":"[5]"}],"fun_headline_variants":["Graphon estimation spots network change-points faster","Dynamic network change-point detection via graphon smoothing","Smoothing link probabilities reveals network shifts","Faster change-point detection when nodes outnumber time steps","Graphon-based screening finds every change-point in dynamic networks"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof assumes that within each time segment every edge probability is a piecewise Lipschitz function of fixed, i.i.d. latent node positions, and that network snapshots are independent across time; if node roles drift over time or snapshots are temporally dependent, the bias and variance bounds, and with them the detection consistency proof, collapse.","fun_headline_variants_meta":{"raw":{"variants":["Graphon estimation spots network change-points faster","Dynamic network change-point detection via graphon smoothing","Smoothing link probabilities reveals network shifts","Faster change-point detection when nodes outnumber time steps","Graphon-based screening finds every change-point in dynamic networks"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000572,"raw_usage":{"total_tokens":2760,"prompt_tokens":1058,"completion_tokens":1702,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":674,"completion_tokens_details":{"reasoning_tokens":1628}},"tokens_in":674,"tokens_out":1702,"duration_ms":13138,"temperature":1.0,"reasoning_tokens":1628,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:01:54.378628+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Generate a dynamic network from a stochastic block model where node memberships gradually drift across time (e.g., a small fraction of nodes switch blocks between segments), or where adjacency matrices are generated with first-order temporal dependence at fixed $P$; then run the MNBS procedure with $h=\\sqrt{T}$ and check empirically whether the estimated change-point set still satisfies the sure-coverage event. A clean calculation would also verify the threshold condition: if $\\Delta_*/\\Delta_D \\le 1$, the proof's key inequality fails and the procedure should lose detection power, so a simulation at the boundary $\\Delta_*/\\Delta_D$ just below 1 provides a direct test.","supporting_citations":[{"cited_title":"Estimating network edge probabilities by neighbour- hood smoothing","cited_arxiv_id":null,"evidence_quote":"Supplies the original neighborhood smoothing estimator and the piecewise Lipschitz graphon framework that MNBS extends to the temporal setting."},{"cited_title":"Matrix estimation by universal singular value thresholding","cited_arxiv_id":null,"evidence_quote":"Provides the universal singular value thresholding method and matrix concentration inequalities used in the modified USVT alternative and in bounding estimation error."},{"cited_title":"Graph-based change-point detection","cited_arxiv_id":null,"evidence_quote":"Serves as the graph-based nonparametric testing baseline that MNBS is compared against in simulations and on the MIT proximity data."},{"cited_title":"Optimal Change Point Detection and Localization in Sparse Dynamic Networks","cited_arxiv_id":"1809.09602","evidence_quote":"Offers the information-theoretic change-point detection approach for sparse dynamic networks that the paper contrasts with its network-aware, post-hoc-estimating procedure."},{"cited_title":"Eagle, A","cited_arxiv_id":null,"evidence_quote":"Supplies the MIT proximity network data set used in the real data application illustrating the procedure."},{"cited_title":"Approximating the distribution of the maximum likelihood estimate of the change-point in a sequence of independent random variables","cited_arxiv_id":null,"evidence_quote":"Establishes the classical $O_p(1)$ localization error for scalar time-series change-points, which the paper contrasts with exact localization under strong signals."},{"cited_title":"Consistencies and rates of convergence of jump-penalized least squares estimators","cited_arxiv_id":null,"evidence_quote":"Defines the Boysen distance used to measure under- and over-segmentation errors in the numerical evaluations."}],"review_version":1}