{"id":"31f7576e-a9af-4ece-a49b-dba6993f16c1","arxiv_id":"2412.16457","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"An approximate message passing algorithm provably recovers the latent matching between correlated Gaussian matrices under adversarial principal-minor corruption of size n/(log n)^20.","lead":"This paper gives a polynomial-time algorithm that recovers the hidden vertex matching between two correlated Gaussian random matrices even when an adversary corrupts a small unknown square block of each matrix. If correct, it is the first efficient graph-matching algorithm with a formal guarantee against adversarial corruption of size n over poly(log n).","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The proof of Claim G.1, the two-matrix conditional Gaussianity that drives Lemma 14, is delegated to Ding-Li 2025+ and not supplied; Lemma 14, Lemma 4, and Proposition 2 collapse without it.","rationale":"I examined the strongest claim (Theorem 1.3) and the proof architecture. The algorithm's success hinges on Proposition 2, which rests on Lemmas 4 and 5. Lemma 5 is a clean-versus-corrupted comparison that uses the smoothness of φ and the bounds of Lemma 14; its proof is present and appears correct modulo algebraic details. Lemma 4, however, is proved via the concentration induction of Lemma 14, whose engine is Claim G.1. Claim G.1 is a two-matrix conditional Gaussianity statement; it is neither proved nor sketched in this paper, and it is cited to a separate forthcoming work (Ding-Li 2025+) with the note that the proof 'can be easily adapted' to the smooth φ. I have not found a contradiction in the paper: the Taylor-expansion steps in G.1.2–G.1.4 are consistent with a Lipschitz smooth φ, and the rate bookkeeping (Δ_t, K_t, t*) closes. The gap is one of omitted proof at the exact point where the correlation between A and B is handled, which is the novel technical difficulty of the paper. I considered other concerns—the union bound in Lemma 3 uses a loose error ϵn·N(π) but is valid since the true error is O(ϵ^2n^2) ≤ ϵn; Lemma 10's delegation is standard but less central; the running time is polynomial for constant ρ. None of these changes the verdict. Since the central technical lemma is delegated and not verifiable from the manuscript alone, the appropriate verdict remains CONDITIONAL: accept only if the proof of Claim G.1 is supplied and checked. My read does not change the reader's CONDITIONAL verdict.","tokens_in":31144,"tokens_out":15808,"duration_ms":129767,"concrete_test":"Write out the full proof of Claim G.1 for the smooth φ of Definition B.1, adapting Ding-Li (2025+) Proposition 3.4 to the two-matrix correlated setting; verify the Gaussian-variance rate 1+O(K_t^{20}Δ_t) and perturbation rate O(K_t^{40}Δ_t^2) with explicit constants. If the adaptation is impossible without extra assumptions on φ, the central claim of the paper is unproven; if it goes through, the conditional acceptance is justified.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Claim G.1 in Appendix G.1 is the linchpin of Lemma 14 (the concentration event E_t, Eq. (G.3)) and therefore of Lemma 4 and Proposition 2. It asserts that conditioned on F_t = σ(f(s),g(s),h(r),ℓ(r): s ≤ t, r ≤ t−1), the rows of h(t) and ℓ(t) are jointly distributed as independent Gaussians with variance 1+O(K_t^{20}Δ_t) plus Gaussian perturbations δ,κ with variance O(K_t^{40}Δ_t^2). This is a two-matrix conditional Gaussian statement: the conditioning sigma-field contains nonlinear functions of the correlated matrix B (and of previous A- and B-iterates), so the classical single-matrix AMP conditioning lemma does not apply directly. The paper does not prove Claim G.1; it states that the proof is established in Ding and Li (2025+) for a step-function denoiser and 'can be easily adapted' to the smooth φ of Definition B.1, then omits the adaptation. The adaptation is not obviously one-line: the original proof must control the influence of the A–B correlation through the conditioning, and the new φ has bounded derivatives (Definition B.1) rather than a step shape, so every Taylor-expansion and Gaussian-perturbation step needs to be re-derived with explicit constants matching the O(K_t^{20}Δ_t) and O(K_t^{40}Δ_t^2) rates. Items (5)–(7) of Lemma 14, the vertex-set localization bounds, and the final signal-strength bound ⟨h_i^{(t*)},ℓ_i^{(t*)}⟩ ≥ 0.9K_{t*}ε_{t*} in Lemma 4 all depend on this claim. If Claim G.1 fails or requires additional hypotheses, Lemma 14, Lemma 4, Lemma 5, and hence Theorem 2.1 are unsupported. This is a delegated-proof gap, not a demonstrated contradiction; the theorem is plausible, but the central analysis is not self-contained.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies exact matching recovery for a pair of correlated Gaussian Wigner matrices (A,B) with latent permutation pi*, under adversarial perturbations E,F supported on an unknown epsilon n by epsilon n principal minor of each matrix. The main result (Theorems 1.3 and 2.1) states that for constant rho in (0,1) and epsilon = o((log n)^{-20}), there is an O(n^C) algorithm that outputs pi* with probability 1-o(1). The algorithm combines a preprocessing and spectral cleaning step (Ivkov-Schramm), a spectral subroutine that constructs matrices Phi(t), Psi(t) and random beta(t), a vector AMP iteration with a smooth denoiser phi, and a seeded graph matching finishing step. The proof proceeds by comparing the corrupted iterates (hat f, hat g) to clean iterates (f, g) through Lemmas 4 and 5, where Lemma 4 is a concentration estimate for the clean AMP iterates driven by a conditional Gaussian claim (Claim G.1).","tokens_in":31572,"tokens_out":18297,"duration_ms":155867,"significance":"If the main theorem is correct, the paper gives the first polynomial-time random graph matching algorithm robust to n^{1-o(1)} adversarial principal-minor perturbations in the correlated Gaussian Wigner model, a qualitative improvement over prior non-robust algorithms. The spectral cleaning lemma, the seeded matching step, and the clean-vs-corrupted comparison framework are presented in substantial detail, and the running time analysis is concrete. The central caveat is that the proof rests on a conditional Gaussian characterization that is not proved in this manuscript and, as stated, appears internally inconsistent; the significance is therefore conditional on repairing that argument.","major_comments":[{"comment":"As stated in (G.7), the claim asserts that, conditional on F_t, (h(t), l(t)) has the law of (G+delta, H+kappa) with G and H independent Gaussians of variance 1+O(K_t^{20} Delta_t) and with delta, kappa of variance O(K_t^{40} Delta_t^2). Under this statement the cross-covariance between h_i and l_i is O(K_t^{40} Delta_t^2), which cannot account for the signal <h_i^{(t*)}, l_i^{(t*)}> >= 0.9 K_{t*} epsilon_{t*} used in Lemma 4, nor for the expectation Psi^{(t+1)} in the proof of Item (3) of Lemma 14, since E[phi(Sigma G beta_i) phi(Sigma H beta_j)] would be O(K_t^{20} Delta_t) rather than Psi^{(t+1)}_{ij}. The claim needs a precise statement of the joint covariance of G and H, or an explicit cross term, together with a proof of that statement. The current text delegates the proof to Ding and Li (2025+) for a step-function denoiser and says it can be easily adapted to the smooth phi of Definition B.1, but no adaptation is given. Since Lemma 14, Lemma 4, and Proposition 2 all rest on this assertion, this is a load-bearing gap.","section":"Appendix G.1, Claim G.1 and Section G.2"},{"comment":"The four concentration estimates (C.7)-(C.10) are asserted to follow from (Ding and Li, 2025+, Proposition 2.4), and no proof is provided in this manuscript. These estimates are used in the proof of Lemma 9 to control Phi^{(t+1)} and Psi^{(t+1)} and to ensure that the spectral recursion (2.7) holds with positive probability, which is what makes Algorithm 3 well-defined. Please include the full argument or, at minimum, a precise statement of the cited proposition and a verification that its constants match the choices in (2.8)-(2.9).","section":"Appendix C, Lemma 10"}],"minor_comments":[{"comment":"The text repeatedly uses 'principle minor' where 'principal minor' is intended; please correct throughout.","section":"Abstract and Definition 1.2"},{"comment":"The proof says each I_t is 'stochastically dominated by a Bernoulli random variable with parameter 1/2', but the argument shows P(I_t=1) >= 1/2 on the high-probability event, so I_t stochastically dominates a Bernoulli(1/2). The subsequent binomial bound is correct, but the wording should be fixed.","section":"Appendix A, proof of Lemma 6"},{"comment":"The loop condition 'while K_t <= exp{(log log n)^2}' is inconsistent with the stopping time t* defined in (2.12) as the first t with K_t >= (log n)^{1.1}, since exp{(log log n)^2} is much larger than (log n)^{1.1}. As written, the algorithm continues beyond t*, while all proofs in Appendices G-I are only for t <= t*. The condition should presumably be 'while K_t < (log n)^{1.1}'.","section":"Algorithm 3, line 10"},{"comment":"In the proof of Item (5) of Lemma 14, the notation f^{(t+1)}_{W x [K_t]} should be f^{(t+1)}_{W x [K_{t+1}]}; the subsequent sum is over i <= K_{t+1}, and the same notational slip appears for g^{(t+1)}.","section":"Appendix G.1.4"},{"comment":"The existence of a smooth phi satisfying all the listed properties is asserted but no construction is given. A short example, such as a suitably rescaled cosine, would make the definition self-contained.","section":"Appendix B, Definition B.1"},{"comment":"The sentence 'involves solving certain linear equations with coefficients depends on depend on all prior AMP iterations' contains duplicated text and should be edited.","section":"Section 1.2"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is transparent about its reliance on Ding and Li (2025+, 2023) and Ivkov and Schramm (2025), but the key conditional Gaussian lemma is delegated to a companion work that is not yet available. The statement of Claim G.1 as written cannot be correct without a cross-covariance term. I would recommend that the authors supply the missing proof or restate the claim precisely, and fix the algorithm pseudocode, before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing to know: the robustness guarantee is new and worth taking seriously. Theorem 1.3 gives exact recovery under adversarial principal-minor corruption of size n/poly(log n) for correlated Gaussian Wigner matrices, and I believe that's the first efficient algorithm with such a guarantee. The paper is honest about its ancestry: Remark 1 says the AMP iteration is essentially Ding-Li's, and the genuinely new pieces are the spectral subroutine independent of the AMP state and the smooth denoiser that makes corruption bounds tractable. That framing is right, and the proof architecture is coherent: clean-case concentration (Lemma 14), corruption comparison (Lemma 5), then seeded finishing. The writing is clear and the appendix gives full algorithms.\n\nThe soft spot is where the reader's stress test points: Claim G.1 in Appendix G.1 is the load-bearing conditional Gaussianity statement for the two-matrix iteration. It is not proved here. The text says it is established in Ding-Li 2025+ for a step-function denoiser and \"can be easily adapted\" to the smooth phi. That adaptation is not obviously one line. The conditioning sigma-field contains nonlinear functions of both correlated matrices, so the standard single-matrix AMP lemma doesn't apply directly. The variance rates O(K_t^20 Delta_t) and O(K_t^40 Delta_t^2) need to be re-derived for the new denoiser with explicit constants, and Items (5)-(7) of Lemma 14, then Lemma 4 and Proposition 2, all rest on it. This is a gap, not a demonstrated contradiction; the theorem is plausible and the rest of the induction is careful. I'd want a referee to check Claim G.1 carefully before accepting. A second, smaller delegation: Lemma 10 (beta-matrix concentration) is cited to Ding-Li Prop 2.4 without proof; that one is lower risk since it's about independent random signs, but it should be supplied in a revision.\n\nThe self-citation pattern is worth a note but not a red flag. The paper repeatedly points to the author's prior work with Ding, and that is legitimate when the cited results are real; but here the central analysis is not self-contained, so a reader cannot fully verify the main theorem from the paper alone. The abstract's claim of being first under adversarial n^{1-o(1)} perturbations appears accurate, and the citation list covers the relevant literature.\n\nBottom line: this is a paper for specialists in random graph matching, AMP, and robust estimation. It deserves a serious referee and is probably right, but the proof needs completion or independent verification of the delegated lemmas. I'd send it to review, with an explicit request to verify Claim G.1.\n\nRecommendation: engage with it; accept only conditional on the missing proof of Claim G.1 (and ideally Lemma 10) being supplied.","headline":"First robust dense graph matching guarantee that looks new, but the proof's central conditional Gaussian claim is delegated to prior work and needs verification before I'd trust the main theorem.","tokens_in":32092,"tokens_out":3299,"would_cite":true,"duration_ms":29042,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","60B20","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that a vector approximate message passing algorithm recovers the exact latent matching between two correlated Gaussian Wigner matrices in polynomial time even when an adversary corrupts an unknown principal minor of size…","keywords":["random graph matching","Gaussian Wigner model","vector approximate message passing","adversarial robustness","spectral cleaning","matching recovery","dense random graphs","polynomial-time algorithm"],"falsifier":"Run the AMP iteration on simulated correlated Gaussian Wigner matrices with $n$ around $10^4$, fix one past iterate, and test whether each row of $h^{(t)}$ and $\\ell^{(t)}$ is conditionally Gaussian with variance $1 + O(K_t^{20}\\Delta_t)$ and perturbations of size $O(K_t^{40}\\Delta_t^2)$; a statistically significant deviation in the conditional tails or variances would break Lemma 14 and with it the polynomial-time guarantee.","tokens_in":30916,"feed_emoji":"🎯","tokens_out":11605,"duration_ms":93326,"temperature":0.7,"pith_summary":"The paper aims to establish that the exact latent matching between two correlated Gaussian Wigner matrices can be recovered in polynomial time even when both observed matrices have been adversarially corrupted on an unknown $\\epsilon n \\times \\epsilon n$ principal minor, for any fixed correlation $\\rho \\in (0,1)$ and any $\\epsilon = o((\\log n)^{-20})$. The proposed algorithm combines a spectral-cleaning preprocessing step with a vector approximate message passing iteration whose time-dependent matrix multiplication grows the feature dimension and cancels correlation across steps. If the main theorem is correct, it is the first efficient random-graph-matching-style algorithm that is robust to adversarial perturbations of size $n^{1-o(1)}$, a regime in which earlier spectral and subgraph-enumeration methods can be derailed by planted structure. A seeded refinement step then upgrades the almost exact output to the exact permutation with probability tending to one.","feed_headline":"Robust AMP recovers hidden matchings despite n^{1-o(1)} corruption","feed_subtitle":"An unknown n/(log n)^20 block can be adversarially edited while exact vertex recovery still succeeds in polynomial time.","key_machinery":"The load-bearing object is a vector approximate message passing (vector AMP) iteration with a smooth, bounded, mean-zero denoiser $\\varphi$, together with the Gram matrices $\\Phi^{(t)}$ and $\\Psi^{(t)}$ that track $\\langle f^{(t)}, f^{(t)}\\rangle$ and $\\langle f^{(t)}, g^{(t)}\\rangle$. At each step a random near-orthogonal matrix $\\beta^{(t)}$ expands the feature dimension from $K_t$ to $K_{t+1} \\approx K_t^2$, and a spectral subroutine builds $\\Xi^{(t)}$ that approximately diagonalizes both $\\Phi^{(t)}$ and $\\Psi^{(t)}$, which cancels the correlations between successive iterations and makes the Onsager correction vanish. The iteration is designed so that the signal-to-noise ratio $K_t \\varepsilon_t^2$ doubles at each step; the proof controls the clean iteration by a concentration lemma and bounds the corruption effect by a comparison lemma between the corrupted and clean outputs.","core_discovery":"The central discovery, stated as Theorem 1.3 and Theorem 2.1, is that for constant $\\rho \\in (0,1)$ and $\\epsilon = o((\\log n)^{-20})$, Algorithm 3 runs in $O(n^C)$ time with $C = C(\\rho)$ and outputs $\\pi^*$ with probability $1-o(1)$ under $\\epsilon$-corrupted Gaussian Wigner observations. The algorithm first symmetrizes the observations and zeroes out at most $4\\epsilon n$ rows and columns by spectral cleaning, then runs a vector-AMP iteration from $K_0$ seed vertices. The iteration maintains Gram matrices $\\Phi^{(t)}$ and $\\Psi^{(t)}$ that track the covariance of the message features and their cross-covariance; the signal-to-noise ratio $K_t \\varepsilon_t^2$ is shown to grow doubly exponentially and reach $\\gg (\\log n)^{1.01}$ by time $t_*$. At that point the linear assignment step matches all but $O(n/\\log n)$ vertices, and a seeded graph matching routine finishes the exact recovery.","pith_inferences":["One direction the paper leaves open is whether the corruption tolerance can be raised to a constant fraction $\\epsilon$; since the bottlenecks are logarithmic factors, a sharper concentration induction on the same architecture would be the natural route.","A testable extension is to dense correlated Erdős–Rényi graphs with constant edge density: the smooth-denoiser AMP and spectral cleaning may transfer once the Bernoulli observation noise is handled in the comparison lemma.","The proof's concentration argument rests on a deferred conditional-Gaussianity claim; if that claim holds, the same analysis should apply to other bilinear AMP iterations with correlated random matrices, while if it fails, the entire induction would need replacement."],"forward_implications":["Exact matching recovery holds in $O(n^C)$ time whenever the correlation is a fixed constant and the adversarial block has size $n/(\\log n)^{20}$ or smaller.","This is the first efficient random graph matching type algorithm robust to adversarial perturbations of size $n^{1-o(1)}$; previous efficient methods relied on spectral or subgraph-counting tools that planted cliques can destabilize.","The AMP iteration has a vanishing Onsager correction, so the standard message-passing state evolution applies despite the correlated two-matrix setting.","The output of the AMP phase is an almost exact matching, and the seeded matching algorithm upgrades it to exact matching with probability tending to one.","The robustness guarantee holds for dense Gaussian Wigner observations; the accompanying scoring statistic selects the true permutation among all candidate seed pairs."],"supporting_citations":[{"why":"Supplies the underlying iterative random graph matching algorithm and Claim G.1, the conditional-Gaussianity result adapted here to a smooth denoiser.","marker":"Ding and Li (2025+, 2023)"},{"why":"Supplies the spectral cleaning procedure that zeroes out the corrupted rows and columns while keeping the operator norm at $O(\\sqrt{n})$.","marker":"Ivkov and Schramm (2025)"},{"why":"Supplies the seeded graph matching algorithm used to upgrade the almost exact AMP output to exact matching.","marker":"Barak et al. (2019)"},{"why":"Supplies the cycle-statistics lemma used to prove that the true permutation maximizes the final overlap statistic even under corruption.","marker":"Wu et al. (2022)"},{"why":"Supplies the spectral norm concentration bound for matrices with i.i.d. sub-Gaussian entries used throughout the spectral cleaning analysis.","marker":"Vershynin (2018)"},{"why":"Supplies the Gaussian projection framework for AMP state evolution invoked in the discussion of conditioning and Onsager correction.","marker":"Bayati and Montanari (2011)"}],"fun_headline_variants":["AMP algorithm matches dense graphs despite n^{1-o(1)} corruptions","Exact matching recovery under adversarial noise via AMP","Robust AMP recovers hidden matchings in dense graphs","First efficient robust random graph matching algorithm","Polynomial-time exact matching under n^{1-o(1)} adversarial edits"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole concentration argument depends on the assertion in Claim G.1 that, after conditioning on the past iterates, the rows of the message matrices are independent Gaussians with variance $1 + O(K_t^{20}\\Delta_t)$ plus tiny Gaussian perturbations; the paper does not prove this for the correlated two-matrix iteration and instead refers to a companion work that it says 'can be easily adapted'.","fun_headline_variants_meta":{"raw":{"variants":["AMP algorithm matches dense graphs despite n^{1-o(1)} corruptions","Exact matching recovery under adversarial noise via AMP","Robust AMP recovers hidden matchings in dense graphs","First efficient robust random graph matching algorithm","Polynomial-time exact matching under n^{1-o(1)} adversarial edits"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000577,"raw_usage":{"total_tokens":2761,"prompt_tokens":1027,"completion_tokens":1734,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":643,"completion_tokens_details":{"reasoning_tokens":1651}},"tokens_in":643,"tokens_out":1734,"duration_ms":12003,"temperature":1.0,"reasoning_tokens":1651,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T10:34:25.526281+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the AMP iteration on simulated correlated Gaussian Wigner matrices with $n$ around $10^4$, fix one past iterate, and test whether each row of $h^{(t)}$ and $\\ell^{(t)}$ is conditionally Gaussian with variance $1 + O(K_t^{20}\\Delta_t)$ and perturbations of size $O(K_t^{40}\\Delta_t^2)$; a statistically significant deviation in the conditional tails or variances would break Lemma 14 and with it the polynomial-time guarantee.","supporting_citations":[{"cited_title":"Fast, robust approximate message passing","cited_arxiv_id":null,"evidence_quote":"Supplies the spectral cleaning procedure that zeroes out the corrupted rows and columns while keeping the operator norm at $O(\\sqrt{n})$."},{"cited_title":"( N early) efficient algorithms for the graph matching problem on correlated random graphs","cited_arxiv_id":null,"evidence_quote":"Supplies the seeded graph matching algorithm used to upgrade the almost exact AMP output to exact matching."},{"cited_title":"High-dimensional probability: An introduction with applications in data science","cited_arxiv_id":null,"evidence_quote":"Supplies the spectral norm concentration bound for matrices with i.i.d. sub-Gaussian entries used throughout the spectral cleaning analysis."}],"review_version":1}