{"id":"5fe742b1-ad49-4fec-b3ee-39bebd9bcd9f","arxiv_id":"2502.00514","paper_version":3,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Changepoint detection in preferential attachment networks is impossible when the change occurs in the last o(√n) steps, resolving the Bet-Castro-van der Hofstad conjecture.","lead":"In a preferential attachment network, if the attachment rule changes only within the last o(√n) time steps, no statistical test based on the final snapshot can detect the change, proving a 2023 conjecture. The paper also shows no estimator can locate the changepoint with error smaller than √n, making the best-known estimator optimal.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 5.6's stochastic domination is the load-bearing step; its conditional-independence and union-bound arguments appear incomplete for vertices with previously discovered hidden children.","rationale":"The reader's weakest assumption correctly identifies Lemma 5.6 as the technical core. My reading of the proof of Proposition 5.2 confirms that every subsequent bound depends on that lemma: Efron-Stein needs E[|C(v_t)|^2]=O(1), and Proposition 5.4 obtains it only through the subcritical branching-process domination. The specific weakness I find is sharper than the reader's formulation: the asserted conditional independence of type-(i) and type-(ii) counts is used to justify that |N_t^l| is dominated by the sum of a Binomial and a Geometric. But the conditioning in Lemma 5.6 does not fix the graph before v_l's arrival; it fixes a partial BFS tree. That partial tree can already contain late vertices adjacent to v_l, raising v_l's current degree and therefore increasing the conditional attachment rates for the remaining type-(ii) slots. The product in Eq. (13) starts at degree m, so it does not obviously cover this case. Without a direct conditional tail bound accounting for r hidden children, or a valid independence argument, the stochastic domination is not established. This is a genuine gap in the written proof, though it may be repairable: a direct union bound over remaining slots that includes r, or a suitable negative-association argument, could restore Lemma 5.6. Because the main theorem's correctness is not disproved but the most load-bearing technical step is currently unverified, the appropriate verdict is CONDITIONAL rather than outright ACCEPT or REJECT. The remainder of the paper, including the likelihood-ratio expression and the interpolation argument, is coherent and does not raise comparable concerns.","tokens_in":18974,"tokens_out":39213,"duration_ms":420782,"concrete_test":"Re-derive Eq. (13) without the conditional-independence assertion. Fix a BFS state in which r >= 0 late vertices are already in T_{t-1} and are adjacent to v_l, so deg(v_l) = m + r when N_t^l is sampled. Bound P(#{remaining type-(ii) neighbors of v_l} >= k | r) by a union bound over the remaining m(N - |T|) edge slots, using per-slot probability at most (m + r + j)/M with j <= k - 1. If this tail is not at most (2mN/n)^k for some r occurring with positive probability, Lemma 5.6 fails and Proposition 5.4 must be re-proved. If the bound holds for all r, replace the unproved independence in Lemma 5.6 by this direct domination; the theorem is then unaffected.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Theorem 2.3 rests on Proposition 4.1's variance bound Var[S]=O(1/N), proved by Efron-Stein in Section 5. The crucial link is Proposition 5.4 via Lemma 5.6, which asserts that at every BFS step the number |N_t^l| of new late neighbors of leaf v_l is stochastically dominated by X = Binom(m, 2N/n) + Geo(1 - 2mN/n). The proof splits |N_t^l| into type-(i) vertices (late parents of v_l) and type-(ii) vertices (later vertices attaching to v_l), bounds each tail separately, and then states that 'the numbers of type (i) and type (ii) vertices in N_t^l are conditionally independent.' This assertion is not proved and is not immediate. Conditioning on the BFS tree T_{t-1} and earlier sets N_t^1,...,N_t^{l-1} can reveal late vertices already discovered via other leaves that are also adjacent to v_l; such 'hidden children' increase deg(v_l) from m to m+r. For the remaining type-(ii) slots, the per-slot attachment probability is then at most (m+r+j)/M, not (j+1)/M, so the product bound in Eq. (13), which starts at j=0, does not account for this increase. Moreover, marginal stochastic domination of each type by its own geometric/binomial law does not imply that the sum is dominated by the independent sum Y+Z without an independence or negative-association argument. If Lemma 5.6 fails, the bound E[|C(v_t)|^2]=O(1) is unsupported and Proposition 4.1 cannot be concluded. The surrounding proof (interpolation, data processing, likelihood-ratio counting in Proposition 5.1) appears sound; the soft spot is localized to Lemma 5.6.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies changepoint detection and localization in preferential attachment models with affine attachment function, where a single final snapshot of the network is observed. The main results are Theorem 2.3, asserting that if the changepoint occurs at time τ_n with n - τ_n = o(√n), then the total variation distance between the null distribution P_n and the alternative distribution Q_{n,τ_n} tends to 0, so every test is asymptotically powerless; and Theorem 2.4, asserting that no estimator can locate the changepoint within o(√n) with non-vanishing probability uniformly over τ_n ∈ [εn, n]. The proof strategy interpolates the changepoint one step at a time, reveals the network history up to time n - N with Δ^2 ≪ N ≪ n, derives a closed-form likelihood ratio (Proposition 5.1), and bounds its variance by the Efron-Stein inequality (Proposition 4.1). The variance bound relies on a stochastic domination of component sizes by a subcritical branching process (Lemma 5.6 and Proposition 5.4). The paper is well structured and largely self-contained, with the main theorems stated precisely and the proof organized into explicit propositions and lemmas.","tokens_in":19310,"tokens_out":12995,"duration_ms":130488,"significance":"If correct, this is a substantial contribution: it resolves Conjecture 3.2 of Bet et al. and proves that the Bhamidi et al. changepoint estimator is order-optimal, establishing a sharp √n threshold for both detection and localization. The proof is ambitious and contains several elegant and reusable ideas, especially the interpolation over changepoint times, the partial-revelation likelihood ratio in Proposition 5.1, and the coupling via a subcritical branching process in Lemma 5.6-5.7. The paper also gives a clean reduction from localization impossibility to detection impossibility via a data-processing inequality, which is a nice structural step. However, the load-bearing stochastic-domination lemma (Lemma 5.6) is not fully proved as written; the issues identified below affect the central variance bound and hence the main theorems, so the manuscript requires nontrivial revision before it can be accepted.","major_comments":[{"comment":"The union bound for the number of type (ii) vertices conditions on a realization of T_{t-1} and N_t^1,...,N_t^{l-1}. These conditioning sets may contain vertices that are adjacent to v_l but were revealed through earlier leaves (\"hidden children\"). Each such vertex increases deg(v_l) from m to m+r, so the probability that a later vertex attaches to v_l is bounded by (m+r+δ)/D, not by (j+1)/M as the product in Eq. (13) assumes. Since Eq. (13) starts the product at j=0 and does not incorporate r, the bound is not valid uniformly over the conditioning events. This matters because the geometric domination in Eq. (14) is the exact input used to obtain the exponential tail in Proposition 5.4 and hence the O(1/N) variance bound in Proposition 4.1.","section":"Lemma 5.6, Eq. (13)"},{"comment":"The assertion that \"the numbers of type (i) and type (ii) vertices in N_t^l are conditionally independent\" is stated without proof and is not immediate from the preferential attachment dynamics. Both counts depend on the current degree of v_l and on which vertices have already been revealed; in particular, a large number of type (i) neighbors increases the current degree of v_l and therefore increases the rate of later type (ii) attachments. Marginal stochastic domination of each count does not imply that the sum is dominated by the independent sum Y+Z in Definition 5.5 without an additional independence or negative-association argument. Since this is the crucial step connecting the BFS component to the subcritical branching process, the proof needs an explicit coupling or a different argument at this point.","section":"Lemma 5.6, sentence after Eq. (14)"}],"minor_comments":[{"comment":"The name \"Cauchy-Schwartz\" should be \"Cauchy-Schwarz\".","section":"Section 4, proof of Theorem 2.3"},{"comment":"The phrase \"the first k times that v_l is attached by later vertices\" is ambiguous when m>1, since v_l can receive several edges from the same vertex at one arrival time. If \"times\" means vertex arrivals, the per-time probability is at most m(j+1)/M and the binomial coefficient should be (N choose k), with an extra factor m^k; if \"times\" means edge arrivals, the text should say so explicitly. The final bound (mN/M)^k is correct in either case, but the counting should be clarified.","section":"Lemma 5.6, Eq. (13)"},{"comment":"In the definition of the encoder, the symbol K_{t,i} is first used as the size of the multi-set ⃗E_{t,i} but the text writes \"∆= K_{t,i}\"; this appears to be a typographical error for \"=: K_{t,i}\".","section":"Section 5, encoder definition"},{"comment":"In Eq. (2), the notation Q_{τ_n,τ_n} and Q_{τ_n,σ_n} is slightly confusing because the first subscript normally denotes the network size; the text later clarifies that these are distributions of the snapshot at time τ_n, but this should be stated at the point of first use.","section":"Proof of Theorem 2.4"}],"recommendation":"major_revision","confidential_remarks":"The paper is well within the scope of a probability journal and the conjecture resolution is significant. The main concern is localized to Lemma 5.6; if the authors can close the stochastic-domination argument by accounting for hidden children and by supplying a valid independence or coupling step, the paper should be suitable for publication. I do not see other obstacles to the central claim, but the present proof of Proposition 4.1 is not complete as written."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Let me get to the point. This paper is the one that closes Bet et al.'s conjecture: if the changepoint is within o(\\sqrt{n}) of the end, no test based on the final snapshot can have Type I+II errors bounded away from 1. It also proves the corresponding localization lower bound, so the O(\\sqrt{n}) estimator of Bhamidi et al. is order-optimal. That is a real result and the paper deserves a serious referee.\n\nWhat's good: the proof structure is thoughtful. The interpolation trick reduces the general late-changepoint case to a single-step change at n-1; revealing history up to n-N simplifies the likelihood ratio; Proposition 5.1 gives a clean closed form; the Efron-Stein bound then reduces everything to controlling the second moment of a connected component size. The writing is careful, the propositions are stated precisely, and the known prior work is cited properly.\n\nThe soft spot is Lemma 5.6. This is the load-bearing stochastic domination step: the claim that the number of new late neighbors discovered from a leaf is dominated by Binomial + Geometric. As written, the argument has two gaps. First, the proof asserts that the counts of type (i) and type (ii) vertices are conditionally independent. That is not established, and in fact the two quantities are positively correlated through the leaf's current degree. Second, the union bound in Eq. (13) starts attachment probabilities at (j+1)/M, assuming the leaf's degree is still m. But once we condition on the previous BFS layers and earlier leaves' neighbor sets, some later vertices adjacent to the leaf may already have been discovered. That raises its degree from m to m+r and makes the waiting time stochastically smaller than the Geometric bound. Without a correct domination, the variance bound O(1/N) in Proposition 4.1 does not follow, and Theorem 2.3 is unsupported.\n\nIs this fatal? Not necessarily. The conjecture is plausible and the surrounding machinery is sound. But as written, the proof has a real gap at a critical junction. It needs to be fixed, either by a genuinely careful coupling or by a different exploration process that avoids the hidden-children problem. I would not certify the proof as it stands.\n\nWho should read it? Anyone working on information-theoretic limits for network inference or on preferential attachment models. It is a good paper to discuss in a reading group precisely because the gap is instructive.\n\nMy recommendation: yes, send to peer review. The result is important enough that referees should dig into Lemma 5.6. If the lemma can be repaired, this will be a very good paper. If it cannot, the conjecture remains open.","headline":"Strong paper resolving a real conjecture, but the stochastic domination lemma at the heart of the proof has a genuine gap that needs repair.","tokens_in":19894,"tokens_out":4043,"would_cite":false,"duration_ms":38475,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","60J80","62F03"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that when the attachment parameter changes within the last $o(\\sqrt{n})$ steps of a growing preferential attachment network, no test based solely on the final snapshot can detect the change: the total variation distance…","keywords":["preferential attachment","changepoint detection","total variation distance","likelihood ratio","second moment method","Efron-Stein inequality","branching process","single network snapshot"],"falsifier":"Simulate the conditional null model for moderate $n$ and estimate $\\mathrm{Var}[S] = \\mathrm{Var}[(1/N)\\sum_v |C(v)| \\lambda_v X_v]$ or the component-size tail $P[|C(v)| \\geq k]$ for a window $N$ with $n - \\tau_n = 1$: a decay slower than $1/N$, or a tail exceeding $2e^{-k+1}$, would expose a failure in the branching-process domination and invalidate the theorem.","tokens_in":18740,"feed_emoji":"🕸️","tokens_out":15416,"duration_ms":119981,"temperature":0.7,"pith_summary":"The paper resolves a conjecture on changepoint detection in preferential attachment networks. It shows that if the network's attachment rule changes at time $n - o(\\sqrt{n})$, the final snapshot contains too little information for any statistical test to distinguish the changed network from one that never changed. The proof bounds the total variation distance between the two snapshot distributions and shows that it vanishes, so the best possible test is no better than random guessing. It also proves that no estimator can locate the changepoint with error $o(\\sqrt{n})$, matching the known $O(\\sqrt{n})$ estimator and settling the localization threshold. A reader should care because this identifies a fundamental information limit: in the late-change regime, no clever use of network structure can beat random guessing.","feed_headline":"Changepoints in the last o(√n) growth steps are undetectable","feed_subtitle":"The paper proves that a single final snapshot cannot beat random guessing for very late changes.","key_machinery":"The argument is carried by an exact likelihood-ratio formula between the changed and unchanged conditional models after revealing the network history up to time $M = n - N$ with $\\Delta^2 \\ll N \\ll n$. For a single late changepoint ($\\tau_n = n-1$), the likelihood ratio is $C_1 \\frac{1}{N} \\sum_{v \\in V_n \\setminus V_M} |C(v)| \\lambda_v X_v$, where $C(v)$ is the connected component of vertex $v$ in the subgraph of late vertices, $\\lambda_v$ is the probability that $v$ is the last vertex to arrive given its component, and $X_v$ is the ratio of attachment probabilities under the changed versus unchanged rule. The proof controls the second moment of this ratio using the Efron–Stein inequality; the key variance estimate $\\mathrm{Var}[S] = O(1/N)$ rests on showing that the size of a late vertex's component is stochastically dominated by a sub-critical branching process with offspring distribution $\\mathrm{Binomial}(m, 2N/n)$ plus $\\mathrm{Geometric}(1 - 2mN/n)$. An interpolation triangle inequality reduces a change $\\Delta$ steps before the end to $\\Delta$ one-step changes, so the one-step bound $O(1/\\sqrt{N})$ with $N \\gg \\Delta^2$ yields the theorem.","core_discovery":"The central discovery is Theorem 2.3: for fixed $m \\geq 1$ and $\\delta \\neq \\delta'$, if $\\tau_n$ satisfies $n - \\tau_n = o(\\sqrt{n})$, then $\\mathrm{TV}(Q_{n,n}, Q_{n,\\tau_n}) = o(1)$, where $Q_{n,\\tau_n}$ is the distribution of the final snapshot when the attachment shift changes from $\\delta$ to $\\delta'$ at time $\\tau_n$. Since the minimum achievable sum of Type-I and Type-II errors equals one minus total variation, this makes every test asymptotically powerless. Theorem 2.4 extends the result to estimation: no estimator based on the snapshot can satisfy $|\\hat{\\tau}_n - \\tau_n| = o(\\sqrt{n})$ with non-vanishing probability uniformly over $\\tau_n \\in [\\varepsilon n, n]$. Together these results confirm the conjecture raised in [7] and show that the estimator proposed in [8], which attains $O(\\sqrt{n})$ error, is order-optimal.","pith_inferences":["The proof's dependence on an explicit encoding suggests the $\\sqrt{n}$ threshold is a property of the hidden arrival order rather than of the affine attachment rule; the same interpolation and Efron–Stein strategy should transfer to polynomial or arbitrary attachment functions once an analogous encoding and branching domination are available.","The theorem does not pin down the constant: for $\\Delta = c\\sqrt{n}$, weak detection is possible, but the exact range of $c$ where tests remain essentially powerless, and the optimal constant in the $\\sqrt{n}$ localization error, remain open.","The impossibility applies strictly to a single final snapshot with no side information; repeated snapshots, vertex timestamps, or node metadata would bypass the information limit identified here."],"forward_implications":["The minimum-degree test of [7] is optimal up to constants: it detects strongly when $n-\\tau_n = \\omega(\\sqrt{n})$, detects weakly when $n-\\tau_n = \\Omega(\\sqrt{n})$, and the new result shows nothing can detect when $n-\\tau_n = o(\\sqrt{n})$.","Any estimator of the changepoint from the final snapshot has worst-case error at least of order $\\sqrt{n}$ uniformly over $\\tau_n \\in [\\varepsilon n, n]$, so the $O(\\sqrt{n})$ accuracy of the estimator in [8] cannot be improved in rate.","The impossibility is information-theoretic rather than computational: even a test that uses all degrees and all subgraph structure of the snapshot fails in the $o(\\sqrt{n})$ regime.","The result remains true if the observer is also given the entire network history up to any time $t$ satisfying $\\Delta^2 \\ll n-t \\ll n$, so the barrier is intrinsic to the late-vertex structure of the snapshot."],"supporting_citations":[{"why":"States the detection threshold conjecture and supplies the minimum-degree test that the result proves optimal.","marker":"[7]"},{"why":"Establishes the earlier impossibility for very short late windows that the new proof extends to the full $o(\\sqrt{n})$ regime.","marker":"[28]"},{"why":"Provides the $O(\\sqrt{n})$ changepoint estimator whose order-optimality follows from the new lower bound.","marker":"[8]"},{"why":"Supplies the Efron–Stein inequality used to bound the variance of the likelihood ratio.","marker":"[10]"},{"why":"Supplies the data-processing inequality used to reduce far-away changepoints to one-step changes.","marker":"[33]"},{"why":"Surveys the second-moment method for likelihood ratios that the proof adapts to the snapshot model.","marker":"[42]"}],"fun_headline_variants":["Undetectable late changepoints in growing networks","Proof: late changepoints are invisible in final snapshots","Changepoint conjecture resolved: o(√n) window is blind","No test can spot very late changepoints in snapshots","Proved: Late changepoints are invisible to every test"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof's variance bound rests on Lemma 5.6's claim that a late vertex's component is stochastically dominated by a sub-critical branching process with independent $\\mathrm{Binomial}(m, 2N/n)$ and $\\mathrm{Geometric}(1 - 2mN/n)$ offspring; if the conditional independence or the union bound behind that domination fails, the $O(1/N)$ variance estimate and the total-variation conclusion do not follow.","fun_headline_variants_meta":{"raw":{"variants":["Undetectable late changepoints in growing networks","Proof: late changepoints are invisible in final snapshots","Changepoint conjecture resolved: o(√n) window is blind","No test can spot very late changepoints in snapshots","Proved: Late changepoints are invisible to every test"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001029,"raw_usage":{"total_tokens":4356,"prompt_tokens":987,"completion_tokens":3369,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":603,"completion_tokens_details":{"reasoning_tokens":3283}},"tokens_in":603,"tokens_out":3369,"duration_ms":21593,"temperature":1.0,"reasoning_tokens":3283,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T18:41:37.327932+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate the conditional null model for moderate $n$ and estimate $\\mathrm{Var}[S] = \\mathrm{Var}[(1/N)\\sum_v |C(v)| \\lambda_v X_v]$ or the component-size tail $P[|C(v)| \\geq k]$ for a window $N$ with $n - \\tau_n = 1$: a decay slower than $1/N$, or a tail exceeding $2e^{-k+1}$, would expose a failure in the branching-process domination and invalidate the theorem.","supporting_citations":[{"cited_title":"Detecting a late changepoint in the preferential attachment model","cited_arxiv_id":"2310.02603","evidence_quote":"States the detection threshold conjecture and supplies the minimum-degree test that the result proves optimal."},{"cited_title":"On the impossibility of detecting a late change-point in the preferential attachment random graph model","cited_arxiv_id":"2407.18685","evidence_quote":"Establishes the earlier impossibility for very short late windows that the new proof extends to the full $o(\\sqrt{n})$ regime."},{"cited_title":"Change point detection in network mod- els: Preferential attachment and long range dependence","cited_arxiv_id":null,"evidence_quote":"Provides the $O(\\sqrt{n})$ changepoint estimator whose order-optimality follows from the new lower bound."},{"cited_title":"Concentration Inequalities - A Nonasymptotic Theory of Independence","cited_arxiv_id":null,"evidence_quote":"Supplies the Efron–Stein inequality used to bound the variance of the likelihood ratio."},{"cited_title":"Information theory: From coding to learning","cited_arxiv_id":null,"evidence_quote":"Supplies the data-processing inequality used to reduce far-away changepoints to one-step changes."}],"review_version":1}