{"id":"72ebf2c6-f9a8-454f-b786-68b4506c66c1","arxiv_id":"2504.16279","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For m unlabeled Gaussian networks, correlation is detectable above roughly rho^2 = (8/m) log n / n and undetectable below roughly rho^2 = (4/(m-1)) log n / n, with the gap between these bounds left open for m>2.","lead":"The paper derives detection thresholds for deciding whether several unlabeled Gaussian weighted graphs share a hidden node alignment. It extends a known two-graph result to any fixed number of graphs and shows a regime where multiple graphs can detect correlation even though two graphs alone cannot.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Abstract's 'sharp threshold' and 'no detection-recovery gap' claims are contradicted by the paper's own theorems for m > 2: the constants 8/m and 4/(m-1) differ by a factor 2(m-1)/m, and Section III states the gap is open.","rationale":"I took Theorems 2 and 3 as the substance and checked them end to end. Theorem 2's proof is valid: the reduction to the identity-aligned statistic T* is legitimate because T is invariant under simultaneous relabeling; the Hanson-Wright bound with Lemma 6's eigenvalues gives P(T* ≤ μ - n^c) = exp(-Ω(n^{2c-2})) = o(1); and the null-side union bound over (n!)^{m-1} profiles cancels the leading exponent n(m-1) log n precisely at ρ² = 8 log n/(m(n-1)), leaving o(1). The m=3 impossibility proof is rigorous: π*_21 is independent of (X2, X3, π*_23) because (π*_12, π*_13) → (π*_12, π*_23) is a bijection and the law of (X2, X3) given the profile depends only on π*_23; the conditional mean E[X1 | aligned edges] = ρ(x2+x3)/(1+ρ) and the Markov chain X1 - X23 - (X2, X3, π*_23) - S check out; the TV chain (a)-(e) is valid with each slack bounded by ε_n. For general m, the sketch is condensed but correct: the aligned sum X2:m consists of m-1 pairwise-ρ entries, so Var(X2:m) = (m-1)(1+(m-2)ρ) and Cov(X1, X2:m) = (m-1)ρ, yielding ρ' = ρ√(m-1)/√(1+(m-2)ρ); the conditional mean formula ρ·X2:m/(1+(m-2)ρ) confirms dependence only through the sum; and (ρ')² ≤ (m-1)ρ² ≤ (4 - (m-1)ε) log n/n, so the two-graph base case applies with margin. Thus the reduction does not lose latent-permutation information in a way that weakens the bound. The genuine soft spot is the abstract: for m > 2 the constants differ by 2(m-1)/m, no sharp threshold is established, and 'no detection-recovery gap' would require the detection threshold to be exactly 8/m, which is not proven. The body's own text disclaims both. This is an internal inconsistency, not a disagreement with external consensus. The theorems' contribution (matching 1/m and 1/(m-1) dependence) survives scrutiny, so conditional acceptance with a corrected abstract remains the right verdict; hence UNCHANGED.","tokens_in":13006,"tokens_out":40338,"duration_ms":301893,"concrete_test":"Decisive check for the sharpness concern: evaluate the ratio of the two thresholds' constants, r(m) = (8/m) / (4/(m-1)) = 2(m-1)/m, for m = 3, 4, 5 (r = 4/3, 3/2, 8/5). Since r(m) > 1 for every m > 2, there is a window of ρ² in which the theorems make no claim either way; together with Section III's explicit 'open problem' sentence, this refutes the abstract's 'sharp threshold' and 'no detection-recovery gap' assertions based on the paper's own results, independent of proof details. Secondary check on the sketched induction: write out the general-m conditional-distribution step—E[X1 | aligned X2..Xm] = ρ·X2:m/(1+(m-2)ρ) with conditional variance 1 - (m-1)ρ²/(1+(m-2)ρ)—and confirm it reproduces ρ' = ρ√(m-1)/√(1+(m-2)ρ); if it does, the sketch is sound.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central advertised claim—a sharp information-theoretic detection threshold with no detection-recovery gap for every fixed m ≥ 2 (abstract)—is not supported by the paper's own theorems when m > 2. Theorem 2 achieves strong detection for ρ² ≥ (8/m) log n/(n-1), whereas Theorem 3 rules out weak detection only for ρ² ≤ (4/(m-1) - ε) log n/n. The constants differ by the factor 2(m-1)/m, which exceeds 1 for every m > 2, so the two bounds do not meet and no single sharp threshold is identified. Section III's penultimate paragraph concedes exactly this: 'the thresholds in (2) and (3) differ by a multiplicative factor of 2(m-1)/m. Closing the gap when m > 2 to establish a sharp detection threshold is an open problem.' The related 'no detection-recovery gap' assertion is likewise unsupported for m > 2: recovery is achievable at the Theorem 2 constant (per [19]), but detection is not ruled out in the window (4/(m-1), 8/m)·log n/n, so a nonzero gap is possible. This is an internal inconsistency between the abstract and the body's own limitation statement. Separately, the reader's concern about the sketched general-m reduction in Section VI was checked in good faith; the missing derivation is fillable—the conditional mean of X1 given the aligned X2..Xm is ρ·(aligned sum)/(1+(m-2)ρ), depending only on X2:m, the induced two-graph correlation is ρ' = ρ√(m-1)/√(1+(m-2)ρ), and (ρ')² ≤ (4-ε') log n/n follows from the theorem's hypothesis. The m=3 template (coupling, S, Markov property, TV chain) extends cleanly, so the lossy-reduction worry does not land; the sharpness overclaim is the load-bearing problem.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies hypothesis testing for m≥2 complete weighted graphs on n nodes with Gaussian edge weights. Under the null hypothesis H0, all edge weights are independent standard Gaussians; under the alternative H1, the graphs have a latent permutation alignment and each pair of corresponding edge weights has correlation ρ. The paper analyzes the generalized likelihood ratio statistic and proves (Theorem 2) that strong detection is achievable when ρ² ≥ 8 log n/(m(n−1)), and (Theorem 3) that weak detection is impossible when ρ² ≤ (4/(m−1)−ε) log n/n for any fixed m. The proof of Theorem 2 uses a Gaussian Hanson-Wright bound; the proof of Theorem 3 is by induction on m, reducing to the two-graph result of Wu, Xu, and Yu, with the m=3 case written out in detail and the general-m case sketched. The abstract claims a sharp information-theoretic threshold and a no detection-recovery gap.","tokens_in":13412,"tokens_out":13308,"duration_ms":115441,"significance":"The m>2 results, if fully proved, are of definite interest: they provide the first detection bounds for multiple unlabeled Gaussian graphs and establish a side-information regime in which two graphs alone cannot be detected as correlated but m>2 graphs can. The proof of Theorem 2 is careful, the eigenvalue computation in Lemma 6 checks out, and the m=3 impossibility proof is detailed and appears sound. However, the abstract overstates the results: the sharp-threshold and no-gap conclusions are not established for m>2, and the general-m lower-bound proof is only sketched. The paper's own Section III acknowledges the gap, so the issue is fixable but must be addressed before publication.","major_comments":[{"comment":"The abstract claims that the paper 'identifies the sharp information-theoretic threshold for detection' and that the model 'has no detection-recovery gap.' These claims are contradicted by the paper's own theorems for m>2. Theorem 2 gives strong detection for ρ² ≥ (8/m) log n/(n−1), while Theorem 3 rules out weak detection only for ρ² ≤ (4/(m−1)−ε) log n/n; the constants differ by the factor 2(m−1)/m, which exceeds 1 for every m>2. Section III explicitly states: 'Closing the gap when m>2 to establish a sharp detection threshold is an open problem.' The no-detection-recovery-gap assertion is also not implied by Theorems 2 and 3, since recovery at the Theorem 2 constant (per [19]) does not rule out a detection gap in the window between the two bounds. Please revise the abstract and the framing of the introduction to present Theorems 2 and 3 as upper and lower bounds with an explicit gap for m>2.","section":"Abstract; Section III, Eqs. (2)-(3)"},{"comment":"For general m>3, Theorem 3 is not actually proved. The text says that X2,...,Xm are 'essentially replaced' by a single aligned-sum matrix X_{2:m} and that after scaling, the pair (X1,X_{2:m}) is exactly the two-matrix Gaussian model with correlation ρ′ = ρ√(m−1)/√(1+(m−2)ρ), but no derivation is given for this reduction. Every constant in Theorem 3 and the induction step depend on this claim. The m=3 template shows the needed ingredients (the coupling via S, the Markov property, the TV inequality chain, and the check (ρ′)² ≤ (4−ε′) log n/n), but for general m these are summarized in a few sentences. Please provide a complete proof for general m>3, including the definition and scaling of X_{2:m}, the conditional distribution of X1 given X_{2:m}, the verification of the ρ′ bound, and the induction step from m−1 to m.","section":"Section VI, proof of Theorem 3 (final paragraph)"},{"comment":"The paper's use of [19] to support the 'no detection-recovery gap' conclusion needs to be qualified. Reference [19] is an external preprint that appeared after this submission, and the present manuscript does not verify its recovery threshold. Even accepting [19], a no-gap statement requires the detection lower bound to match the recovery threshold, which is exactly what Theorem 3 does not provide for m>2. Please either prove the relevant comparison or remove the no-gap claim from the abstract.","section":"Section III, penultimate paragraph; abstract no-gap claim"}],"minor_comments":[{"comment":"There are several typos to fix: 'Previou sly' and 'independen t' in the abstract, 'V ery' in Section I, 'eigvenvalue' in Section V, 'impove' in the acknowledgments, and 'rariables' in reference [45].","section":"Throughout"},{"comment":"Please state explicitly that 0 ≤ ρ < 1; the covariance matrix Σ = (1−ρ)I + ρE and the formula for Σ^{-1}−I require this parameter range.","section":"Section II"},{"comment":"The notation X_{2:m} is used before it is defined; please define the aligned-sum matrix in the preliminaries or at the start of Section VI.","section":"Section VI, final paragraph"},{"comment":"In the displayed formulas near the threshold τ = C(n,2)C(m,2)ρ − n^c, the term 'nc' appears where n^c is clearly intended; please correct the typesetting.","section":"Section V, proof of Theorem 2"},{"comment":"The proof of Theorem 3 uses both ε and ǫ for the same constant; please unify the notation and state explicitly that ε′ in the reduction is a positive constant possibly different from ε.","section":"Section III and Section VI"},{"comment":"The remark about extending necessary conditions to Erdős-Rényi graphs is informal and not developed; consider moving it to a discussion section or removing it.","section":"Section III, penultimate paragraph"}],"recommendation":"major_revision","confidential_remarks":"I think the paper is worth pursuing. The main obstacles are the abstract's overclaims and the incomplete general-m proof of Theorem 3; both are fixable. I verified the m=3 reduction and the ρ′ formula, and the missing general-m derivation appears fillable. The paper is within scope for math.ST and, once revised, could make a solid contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things about this paper. First, the main results are genuinely new and mostly sound: for m>2 correlated Gaussian graphs, the generalized likelihood ratio test achieves strong detection when rho^2 >= 8 log n/(m(n-1)), and weak detection is impossible when rho^2 <= (4/(m-1)-eps) log n/n. That side-information regime—where two graphs fail but m>2 succeed—is real and worth having. Second, the abstract oversells it. The constants differ by a factor 2(m-1)/m, which is >1 for every m>2, so there is no sharp threshold in the paper. The body's Section III openly says closing the gap is open. Similarly, the \"no detection-recovery gap\" claim in the abstract is not established here; it relies on a recent recovery threshold from [19] and a constant that matches only the achievability side. This is not a fatal flaw, but it is an internal inconsistency the authors will have to fix.\n\nWhat I like: the upper-bound proof is careful, with an explicit Hanson-Wright variant and constants that check out. The lower-bound proof for m=3 is written out in detail, using the coupling and Markov structure correctly. The induction step is plausible, and the general-m reduction to a two-matrix problem actually works—the conditional mean of X1 given the aligned sum X2:m depends only on that sum, and the induced correlation rho' = rho sqrt(m-1)/sqrt(1+(m-2)rho) is correct. I checked the algebra; the stress-test note is right that the lossy-reduction worry does not land. The paper's citations are appropriate: the base case is Wu-Xu-Yu, and the recovery threshold from [19] is external, not a recycled conclusion.\n\nSoft spots, in proportion: the general-m proof is sketched as \"similar\" after m=3; I believe it is fillable, but as written it is a sketch and should be either expanded or explicitly labeled as such. The bigger soft spot is the abstract, which overshoots the theorems. That is repairable without changing the proofs.\n\nWho gets value: anyone working on graph alignment, multiple-network correlation, or detection-recovery thresholds. It is a narrow but legitimate step forward. I would take it as a serious referee assignment and expect it to be accepted after revision; the burden is on the authors to align the abstract with the actual statements and to make the general-m induction complete enough for the reader to verify.","headline":"The paper's real contribution—new detection bounds for m>2 unlabeled Gaussian graphs and the side-information regime—is solid, but the abstract overclaims a \"sharp threshold\" and \"no detection-recovery gap\" that the paper's own theorems contradict.","tokens_in":13932,"tokens_out":1277,"would_cite":true,"duration_ms":14057,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62H15","05C80","62F03"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper pins down when m unlabeled Gaussian graphs can be detected as correlated despite hidden vertex relabelings, and finds a regime where two graphs fail but several succeed.","keywords":["correlation detection","unlabeled graphs","Gaussian random graphs","hypothesis testing","generalized likelihood ratio","sharp threshold","graph alignment","total variation distance"],"falsifier":"Write out the joint law of $(X^1, X^{2:m})$ under the planted model for $m=4$ and compare it with the claimed two-matrix Gaussian law with correlation $\\rho\\sqrt{3/(1+2\\rho)}$; if the cross-moments or the covariance structure differ, the compression step is only approximate and the constants in the converse would need re-examination. A simulation check would be to estimate the total-variation distance between $X^1$ and $X^{2:m}$ at $\\rho^2=(4/3-\\varepsilon)\\log n/n$ and see whether it vanishes as $n$ grows.","tokens_in":12777,"feed_emoji":"📊","tokens_out":9730,"duration_ms":85995,"temperature":0.7,"pith_summary":"Consider m complete graphs on n nodes whose edge weights are standard Gaussians, either independent or correlated through a hidden alignment of the nodes. The paper asks at what correlation strength a test can tell the two cases apart even though the node labels are unknown. It gives a sufficient condition, $\\rho^2 \\geq 8\\log n/(m(n-1))$, under which a generalized likelihood-ratio test achieves strong detection, and a necessary condition, $\\rho^2 \\leq (4/(m-1)-\\varepsilon)\\log n/n$, under which no test can beat random guessing. The discovery that matters is that the sufficient condition decays like $1/m$: adding graphs lowers the required correlation, so there is a side-information regime where two graphs alone are useless but $m>2$ graphs allow reliable detection.","feed_headline":"Adding graphs lowers the detection threshold for hidden alignment","feed_subtitle":"For m unlabeled Gaussian networks, new bounds reveal a regime where two graphs fail but several succeed.","key_machinery":"The central object is the generalized likelihood ratio $T$, which replaces the intractable average over all permutation profiles by the maximum over alignments of the log-likelihood ratio; up to constants this maximum equals the sum of aligned edge-weight products across all pairs of graphs. Two tools carry the argument: a tail bound for Gaussian quadratic forms with explicit constants, used to control both the null probability that the statistic exceeds its threshold and the planted probability that it falls below; and a genie-aided reduction for the converse, in which graphs $X^2,\\dots,X^m$ are aligned to $X^2$ and summed into a single matrix $X^{2:m}$. The reduction asserts that $X^1$ and a scaled $X^{2:m}$ follow the two-matrix model with correlation $\\rho\\sqrt{(m-1)/(1+(m-2)\\rho)}$, so the already-solved $m=2$ case can be invoked inductively.","core_discovery":"For fixed $m\\ge2$, the generalized likelihood-ratio statistic\n$$T=\\max_{\\pi_{12},\\dots,\\pi_{1m}}\\sum_{i<j}\\sum_{k<\\ell} X^k_{\\pi_{1k}(i),\\pi_{1k}(j)}X^\\ell_{\\pi_{1\\ell}(i),\\pi_{1\\ell}(j)}$$\ndrives strong detection once $\\rho^2 \\ge 8\\log n/(m(n-1))$, and weak detection is impossible once $\\rho^2 \\le (4/(m-1)-\\varepsilon)\\log n/n$ for any $\\varepsilon>0$. For $m=2$ these recover the known sharp threshold; for $m>2$ the two bounds differ by a multiplicative factor $2(m-1)/m$, and closing that gap is left open. The lower-bound proof proceeds by induction on $m$, compressing the last $m-1$ graphs into one aligned-sum matrix and showing that, after scaling, $(X^1,X^{2:m})$ is the two-graph Gaussian model with effective correlation $\\rho'=\\rho\\sqrt{(m-1)/(1+(m-2)\\rho)}$. The paper thus claims that each additional graph contributes a fresh independent view of the same latent alignment.","pith_inferences":["A natural conjecture, not advanced by the paper, is that the true threshold is $8\\log n/(m(n-1))$ for all $m$, matching the recovery threshold; if so, the converse constant $4/(m-1)$ is loose and the gap is a proof artifact.","The effective-correlation formula $\\rho'=\\rho\\sqrt{m-1}$ suggests the detection signal grows with the number of graphs, making the problem analogous to combining multiple noisy measurements of the same alignment; one could test this by measuring empirical total-variation distance for $m=3,4$ at fixed $\\rho^2 n/\\log n$.","The same aligned-sum compression might transfer to Gaussian feature-vector databases, where the multi-database detection limit would then be the two-database limit with an amplified correlation; this is an extrapolation beyond the graph setting."],"forward_implications":["For every fixed $m\\ge2$, strong detection of a shared latent alignment is achievable by the generalized likelihood-ratio test once $\\rho^2 \\ge 8\\log n/(m(n-1))$.","For $\\rho^2 \\le (4/(m-1)-\\varepsilon)\\log n/n$, the total-variation distance between the null and planted distributions vanishes, so no test, efficient or not, can outperform random guessing.","For each $m>2$ the gap between these bounds creates a provable side-information regime: correlations that two graphs are incapable of detecting become strongly detectable when $m$ graphs are available.","Combined with the known recovery threshold for this Gaussian multi-graph model, the achievability result places detection and recovery at the same correlation scale, meaning there is no regime in which correlation is detectable but the alignment cannot be recovered.","The induction underlying the converse offers a route to lift two-graph impossibility results for related graph models to $m\\ge3$."],"supporting_citations":[{"why":"Establishes the sharp two-graph Gaussian detection threshold that serves as both the base case of the induction and the target model for the compression step.","marker":"[1]"},{"why":"Supplies the multi-graph recovery threshold used to conclude that detection and recovery occur at the same correlation scale in this model.","marker":"[19]"},{"why":"Provides the quadratic-form tail bound that Proposition 4 adapts with explicit constants to control the error probabilities in the achievability proof.","marker":"[45]"}],"fun_headline_variants":["More graphs lower the detection threshold for hidden alignment","Sharp threshold found for detecting correlation across multiple graphs","Extra graphs reveal hidden alignment when two graphs fail","Multiple Gaussian networks sharpen detection threshold"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The converse relies on replacing graphs 2 through m by their aligned sum and treating the result, after scaling, as exactly the two-graph Gaussian model; the paper writes this reduction out for m=3 and states, rather than fully derives, the general-m version.","fun_headline_variants_meta":{"raw":{"variants":["More graphs lower the detection threshold for hidden alignment","Sharp threshold found for detecting correlation across multiple graphs","Extra graphs reveal hidden alignment when two graphs fail","Multiple Gaussian networks sharpen detection threshold"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000212,"raw_usage":{"total_tokens":1425,"prompt_tokens":960,"completion_tokens":465,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":576,"completion_tokens_details":{"reasoning_tokens":418}},"tokens_in":576,"tokens_out":465,"duration_ms":4891,"temperature":1.0,"reasoning_tokens":418,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:08:14.142824+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Write out the joint law of $(X^1, X^{2:m})$ under the planted model for $m=4$ and compare it with the claimed two-matrix Gaussian law with correlation $\\rho\\sqrt{3/(1+2\\rho)}$; if the cross-moments or the covariance structure differ, the compression step is only approximate and the constants in the converse would need re-examination. A simulation check would be to estimate the total-variation distance between $X^1$ and $X^{2:m}$ at $\\rho^2=(4/3-\\varepsilon)\\log n/n$ and see whether it vanishes as $n$ grows.","supporting_citations":[{"cited_title":"Testing correlation of unlabel ed random graphs,","cited_arxiv_id":null,"evidence_quote":"Establishes the sharp two-graph Gaussian detection threshold that serves as both the base case of the induction and the target model for the compression step."},{"cited_title":"The feasibility of multi-graph alignment: a Bayesian approach","cited_arxiv_id":"2502.17142","evidence_quote":"Supplies the multi-graph recovery threshold used to conclude that detection and recovery occur at the same correlation scale in this model."},{"cited_title":"A Bound on tail probabilit ies for quadratic forms in independent random rariables,","cited_arxiv_id":null,"evidence_quote":"Provides the quadratic-form tail bound that Proposition 4 adapts with explicit constants to control the error probabilities in the achievability proof."}],"review_version":1}