{"id":"13621b18-9103-4747-8f97-7874f9a9d41a","arxiv_id":"2505.08251","paper_version":4,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":9,"one_line_summary":"MASO and GeoDe are proposed to recover communities in latent-geometry SBMs, and their empirical gains are not backed by guarantees that apply to the actual algorithms.","lead":"Two new methods, a motif-attention spectral operator and an iterative denoiser, are claimed to improve community recovery in networks with hidden geometric noise. The empirical results look strong, but the theoretical guarantees rest on assumptions that are not shown to hold for the implemented methods.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.1's proof relies on a false independence claim in Lemma C.3: the summands Y_e share two-hop edges, so the matrix Bernstein bound is inapplicable.","rationale":"The reader identifies the missing proof that PPMI embeddings concentrate to the assumed rho_in/rho_out structure. That is a legitimate gap between the algorithm and the theorem's hypotheses. However, I find a more direct problem inside Theorem 3.1's proof: Lemma C.3's matrix Bernstein argument requires the summands Y_e to be independent, but \\tilde W_{ij} includes products of edge indicators along two-hop paths, so shared vertices induce dependence. This is not a minor technicality; it invalidates the stated concentration bound and therefore the Davis-Kahan step and the exact-recovery conclusion. Even if the embedding structure were proven, the current proof would not establish the guarantee. The paper contains no code or reproducibility artifact, but the central scientific claim is the theoretical guarantee, and that claim is currently unsupported by the written proof. I am not arguing the theorem is false; I am arguing the provided argument is internally inconsistent at a load-bearing step. Since the reader's verdict is already REJECT and my concern reinforces that conclusion, I recommend no change to the verdict. I would encourage the authors to either repair Lemma C.3 with a correct concentration argument (e.g., via a dependent random-matrix inequality or a different decomposition) or clearly state the PPMI-to-cosine-structure assumption as an open condition rather than a proved one.","tokens_in":17453,"tokens_out":6960,"duration_ms":68031,"concrete_test":"Analytically verify the independence claim in Lemma C.3: expand \\tilde W_{ij} and \\tilde W_{i\\ell} for edges sharing vertex i and compute E[\\tilde W_{ij} \\tilde W_{i\\ell}] - E[\\tilde W_{ij}] E[\\tilde W_{i\\ell}] under the latent-kernel SBM. Because both expressions contain the common factor A_{ik} for k\\ne i,j,\\ell through X_{ij} and X_{i\\ell}, the covariance is generically nonzero; if so, the summands Y_e are not independent and the matrix Bernstein bound in Lemma C.3 cannot be applied, so the proof of Theorem 3.1 fails at that step.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The MASO exact-recovery guarantee rests on Lemma C.3 (concentration of \\tilde W - E\\tilde W), which invokes Tropp's matrix Bernstein on the decomposition E = \\sum_e Y_e with Y_e = (\\tilde W_{ij} - E\\tilde W_{ij})(e_i e_j^T + e_j e_i^T). The proof asserts 'Independent edges give independent matrices {Y_e}' (Appendix C.3). This is false: \\tilde W_{ij} = (1-\\beta) A_{ij} e^{\\langle z_i,z_j\\rangle/\\sqrt d} + \\beta A_{ij} e^{\\langle z_i,z_j\\rangle/\\sqrt d} \\sum_{k\\ne i,j} A_{ik} A_{kj} e^{(\\langle z_i,z_k\\rangle+\\langle z_k,z_j\\rangle)/\\sqrt d}, so \\tilde W_{ij} depends on every two-hop edge incident to i or j. Hence Y_{\\{i,j\\}} and Y_{\\{i,\\ell\\}} share the edge indicators A_{ik} for all k and are dependent. The matrix Bernstein hypothesis is violated, and the claimed \\|E\\|_2 = O(\\sqrt{\\log n}) is unsupported. Without Lemma C.3, Lemma C.5 and Theorem 3.1 do not follow. This is an internal inconsistency in the proof, independent of the separate gap that the PPMI embeddings in Section 3.2 are never shown to satisfy the \\rho_in/\\rho_out inner-product structure assumed in Theorem 3.1.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes two algorithms for community recovery in a latent-kernel stochastic block model with two communities: MASO, a motif-attention spectral operator built from PPMI embeddings and triangle-motif weighting, and GeoDe, an iterative geometric denoising scheme that alternately reweights edges based on community and geometry confidence. The main theoretical claims are that MASO achieves exact recovery when the classical SBM threshold (sqrt(c(σ)a) - sqrt(c(σ)b))^2 > 2 holds, and that GeoDe converges almost surely to the latent SBM weight matrix, yielding exact recovery under a spectral-gap condition. Empirical results are reported on synthetic latent-kernel SBMs and on a 2000-node Amazon co-purchasing subgraph, where GeoDe+MASO is said to improve belief propagation's accuracy from 0.507 to 0.911. The paper also states exact and weak recovery thresholds for the latent-kernel SBM based on a claimed contiguity reduction to the classical SBM.","tokens_in":17868,"tokens_out":8153,"duration_ms":76918,"significance":"If the theoretical claims were correct, the paper would be significant: it would provide a spectral method with exact-recovery guarantees in geometrically-noised SBMs and an unsupervised denoiser that substantially improves belief propagation on a real network. The empirical demonstration on the Amazon metadata subgraph is a useful data point, and the authors provide reproducible parameter tables and significance tests. However, the theoretical backbone is not sound: the two main theorems rest on unverified or circular assumptions, and a central concentration lemma contains a false independence claim. The claimed theoretical contributions are therefore not established, and the empirical evaluation alone is too limited to carry the paper.","major_comments":[{"comment":"The proof claims that 'Independent edges give independent matrices {Y_e}', but this is false. The definition of \\tilde W_{ij} includes X_{ij} = \\sum_{k \\neq i,j} W_{ik} W_{kj}, so \\tilde W_{ij} depends on the two-hop edge indicators A_{ik} and A_{kj}. Consequently Y_{ij} and Y_{i\\ell} are dependent because they share the indicators A_{ik} for k \\neq i,j,\\ell. Tropp's matrix Bernstein inequality cannot be applied to E = \\sum_e Y_e. The asserted bound \\|E\\|_2 = O(\\sqrt{\\log n}) is unsupported, and Lemma C.5 and Theorem 3.1, which rely on this concentration result, do not follow.","section":"Appendix C.3, Lemma C.3"},{"comment":"The theorem fixes normalized embeddings with \\langle z_i,z_j\\rangle = \\rho_{\\rm in} for same-community pairs and \\rho_{\\rm out} for different-community pairs. However, the MASO construction in Section 3.2 uses random-walk PPMI followed by truncated SVD, and the paper never proves that this construction produces embeddings with the assumed two-point inner-product structure under the latent-kernel SBM. As stated, the exact-recovery guarantee applies to an abstract embedding model, not to the implemented MASO operator.","section":"Section 3.3, Theorem 3.1"},{"comment":"The theorem assumes A = W^* + G^* with G^* \\geq 0 and diagonal projectors C and G satisfying C G^* = 0 and G W^* = 0. These assumptions directly encode the desired conclusion: W^* is the latent SBM matrix and G^* is geometry noise that is orthogonal to it. The proof then shows that a linear recursion of the form W^{(t+1)} = (I - \\lambda_C^{(t)} C - \\lambda_G^{(t)} G)W^{(t)} + \\lambda_C^{(t)} C W^* - \\lambda_G^{(t)} G G^* converges to W^*. But Algorithm 1 does not implement this recursion: it applies multiplicative reweighting to the union sets S = S_C \\cup S_G and B = B_C \\cup B_G, with separate shrink and boost factors. The theorem therefore does not analyze GeoDe and does not establish convergence from a latent-kernel SBM.","section":"Section 4.1, Theorem 4.1"},{"comment":"The proof states that 'for fixed D the variables (\\Delta_{ij})_{(i,j) \\in D} are independent'. This is false whenever D contains pairs sharing a vertex, because \\Delta_{ij} and \\Delta_{i\\ell} both depend on the latent position x_i. The Hoeffding bound and the subsequent union bound therefore do not establish the claimed contiguity between the latent-kernel SBM and the classical SBM. The reduction that underlies the recovery thresholds stated in Section 2.2 is not proven.","section":"Appendix C.1, Theorem C.1"},{"comment":"The rank-2 representation S = \\alpha \\mathbf{1}\\mathbf{1}^\\top + \\beta^* g g^\\top does not follow from the expressions in Lemma C.2. In Lemma C.2, the expected same-community weight contains (n_+ - 2) w_{\\rm in}^2 + n_- w_{\\rm out}^2 and the different-community weight contains (n-2) w_{\\rm in} w_{\\rm out}; substituting these into the claimed formula yields an identity only under additional balanced-size and small-w approximations that are not stated. The eigen-gap \\gamma = \\Theta(\\log n) is therefore not established.","section":"Appendix C.4, Lemma C.4"}],"minor_comments":[{"comment":"The exact and weak recovery thresholds are stated in the main text as facts, but the contiguity result on which they depend (Theorem C.1) is flawed as noted in major comment 4.","section":"Section 2.2"},{"comment":"The theorem requires \\sum_t \\lambda_C^{(t)} = \\infty and \\sum_t (\\lambda_C^{(t)})^2 < \\infty, but only \\sum_t (\\lambda_G^{(t)})^2 < \\infty is imposed. The claimed contraction of the G-component is not justified by the stated conditions.","section":"Section 4.1, step-size schedule"},{"comment":"The proof identifies the second eigenvector of S with g/\\|g\\| and uses \\|g\\|^2 = n. This holds only for exactly balanced communities, whereas Definition 2.1 draws labels independently with equal probability, so n_+ is random and only approximately n/2.","section":"Appendix C.5, Lemma C.5"},{"comment":"The claim that MASO maintains perfect recovery up to \\sigma \\geq 0.5 is based on Figure 1 without error bars; the numerical values and the definition of 'perfect' (exact labels up to permutation) should be stated explicitly.","section":"Section 5.1"},{"comment":"Reference [15] is dated 2025 but corresponds to a 2014 arXiv preprint (arXiv:1406.1880); please correct the bibliographic details.","section":"Reference [15]"},{"comment":"The p-values for the Amazon experiment are reported, but the procedure for computing them (test statistic, null model, number of trials) is not described.","section":"Section 5.2"},{"comment":"The thresholds and strengths are defined in Algorithm 1 but default values appear only in Appendix E.3; the main text should summarize the default parameter choices to make the experiments reproducible without reading the appendix.","section":"Algorithm 1"}],"recommendation":"reject","confidential_remarks":"The manuscript contains multiple internal inconsistencies that are not presentation issues: the independence claims in Lemma C.3 and Theorem C.1 are demonstrably false, Theorem 4.1 assumes the decomposition it purports to prove, and Theorem 3.1's guarantee does not cover the implemented embedding procedure. These are load-bearing gaps in the central theoretical claims. The empirical evaluation is limited to small synthetic graphs and one real dataset, and it cannot compensate for the absence of valid guarantees. Substantial new analysis would be needed to make the claims rigorous; within the manuscript's current scope, I do not see a path to acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the core algorithms—MASO's blend of PPMI embeddings, attention, and triangle-based reweighting, and GeoDe's alternating C/G-step denoiser—are genuinely novel combinations and are worth thinking about. Second, the formal guarantees are not. Both Theorem 3.1 and Theorem 4.1 prove results for assumptions that the authors never connect to the implemented algorithms, and at least one key lemma in the proof of Theorem 3.1 is wrong.\n\nWhat is actually new: the operational ideas. MASO builds multi-hop co-occurrence features, applies a softmax-style attention to one-hop affinities, then reinforces with two-hop triangle support. GeoDe alternates between community and geometry spectral clustering to decide which edges to shrink or boost. That is a reasonable toolbox for noisy latent-geometric networks, and the synthetic results suggest it helps, though without code or standard deviations it is hard to know how much is careful tuning.\n\nNow the soft spots, in order of severity.\n\n(1) The proof of Theorem 3.1 depends on Lemma C.3, which claims that the sum over edges of the centered weight deviations can be handled by matrix Bernstein because 'independent edges give independent matrices.' That is false. The weights \\tilde W_{ij} depend on all two-hop edges incident to i and j, so Y_{ij} and Y_{i\\ell} share the edge indicators A_{ik}. The independence assumption fails, and the O(√log n) bound on the noise matrix is unsupported. Without it, the Davis–Kahan step and the exact-recovery claim do not follow.\n\n(2) Even if Lemma C.3 were fixed, Theorem 3.1 assumes the PPMI embeddings have exact inner products ρ_in/ρ_out. The paper never proves that the random-walk PPMI plus truncated SVD construction in Section 3.2 produces such a structure. So the theorem does not cover the implemented MASO.\n\n(3) Theorem 4.1 is about a linear stochastic-approximation recursion on a decomposition A = W* + G* with orthogonal projectors. The actual GeoDe update uses thresholded reweighting based on spectral clustering outputs, and the decomposition is not a consequence of the latent-kernel SBM. The theorem is essentially a proof of convergence for a different algorithm.\n\n(4) The contiguity proof in Appendix C.1 uses Hoeffding on kernel deviations Δ_ij that are not independent when pairs share a vertex. This is likely fixable with a more careful concentration bound, but as written it is another gap.\n\nThe empirical work is substantial in scope but light on reproducibility: no code, no standard deviations, and many hand-set hyperparameters. The Amazon experiment uses a subgraph where belief propagation is at chance (p=1.00), so the headline '79.7% improvement' is less impressive than it sounds.\n\nWho this is for: someone working on practical spectral clustering for noisy networks might find the heuristics useful; someone looking for a rigorous recovery threshold will not find it here. The paper deserves serious peer review—the ideas are not routine and the flaws are fixable in principle—but only after the authors prove the PPMI structure, correct the concentration argument, and match the GeoDe analysis to the actual update rule. I would not cite it as a proven result, but I'd read a revised version.","headline":"Novel algorithmic combination with two load-bearing proof gaps and a theory that never connects to the implemented methods; worth a serious referee, but not citable as proven.","tokens_in":18370,"tokens_out":4302,"would_cite":false,"duration_ms":40985,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Two-stage spectral pipeline achieves exact community recovery in noisy latent-kernel stochastic block models at the classical sharp threshold, and lifts belief propagation's accuracy to 91.1% on Amazon.","keywords":["community recovery","stochastic block model","latent-space graph model","spectral clustering","geometric denoising","belief propagation","motif attention","exact recovery"],"falsifier":"Take a latent-kernel SBM with parameters satisfying $(\\sqrt{c(\\sigma)a}-\\sqrt{c(\\sigma)b})^2>2$, compute the PPMI/SVD embeddings exactly as in Section 3.2, and measure the inner-product distributions for same-community versus different-community pairs. If those distributions overlap—so $\\rho_{\\mathrm{out}}$ is not strictly below $\\rho_{\\mathrm{in}}$—Theorem 3.1's precondition is violated, and a failure of MASO's exact recovery on graphs where the threshold holds would refute the claim that the guarantee covers the implemented algorithm.","tokens_in":17183,"feed_emoji":"🕸️","tokens_out":8909,"duration_ms":72999,"temperature":0.7,"pith_summary":"Community recovery—finding which nodes share a hidden group when edges also depend on unobserved geometric positions—is the task here. The paper proposes two linked tools: MASO, a spectral operator that weights edges by multi-hop co-occurrence and triangle support, and GeoDe, an iterative reweighting loop that alternately trusts community and geometry evidence. It claims that together they recover every label with high probability in a latent-kernel stochastic block model whenever $(\\sqrt{c(\\sigma)a}-\\sqrt{c(\\sigma)b})^2 > 2$, the sharp exact-recovery threshold of the underlying SBM. On a 2000-node Amazon product-metadata subgraph, using GeoDe+MASO as a denoising front end raises belief propagation's accuracy from 0.507 to 0.911, a 79.7% relative gain. A sympathetic reader would take the paper's central assertion to be that geometric noise can be stripped away algorithmically, not just absorbed into a noisier SBM.","feed_headline":"Denoising step lifts community recovery from 51% to 91%","feed_subtitle":"The GeoDe+MASO denoiser lifts belief propagation accuracy from 0.507 to 0.911 on Amazon metadata.","key_machinery":"MASO (Motif-Attention Spectral Operator) builds random-walk PPMI embeddings, rescales adjacency weights by attention $A_{ij}\\exp(\\langle z_i,z_j\\rangle/\\sqrt{d})$, and mixes in triangle support $X_{ij}=\\sum_{k\\neq i,j}W_{ik}W_{kj}$ via $\\tilde W_{ij}=(1-\\beta)W_{ij}+\\beta W_{ij}X_{ij}$, then spectrally clusters the normalized Laplacian $H=D^{-1/2}\\tilde W D^{-1/2}$. GeoDe (Iterative Geometric Denoising) alternates a community-inference step and a geometry-inference step, shrinking low-confidence and boosting high-confidence edges under a decaying schedule until the weight matrix approaches a clean SBM. The load-bearing identity is the conditional expectation $\\mathbb{E}[\\tilde W_{ij}\\mid z_i,z_j]$ from Lemma C.2, which shows the mixed weights concentrate around two values with an eigen-gap $\\Theta(\\log n)$; all recovery guarantees flow from that gap plus a matrix-Bernstein concentration bound and Davis–Kahan perturbation.","core_discovery":"The paper's central claim is that exact community recovery in a latent-kernel SBM—where each edge probability is multiplied by a Gaussian kernel on latent positions—is achievable by a two-stage pipeline at the same sharp threshold as the classical SBM. The theorem states that if the embeddings entering MASO have a fixed cosine structure (inner product $\\rho_{\\mathrm{in}}$ for same-community pairs, $\\rho_{\\mathrm{out}}$ for different-community pairs), then the second eigenvector of the mixed motif-attention Laplacian followed by one local-flip pass recovers all labels with probability $1-o(1)$ whenever $(\\sqrt{c(\\sigma)a}-\\sqrt{c(\\sigma)b})^2>2$. It also claims GeoDe converges almost surely to the underlying SBM weight matrix under a stochastic-approximation schedule, provided the community and geometry edge sets are disjoint. Empirically the paper reports perfect recovery on synthetic graphs for noise $\\sigma\\ge 0.25$, and the Amazon validation shows the denoiser transfers to belief propagation.","pith_inferences":["A testable extension the paper leaves implicit: the same two-stage denoiser should also boost non-spectral base algorithms, so running GeoDe before semidefinite-programming recovery would separate the denoising benefit from the base method.","The fixed-cosine-embedding assumption in Theorem 3.1 is strong enough that a direct empirical check—computing the inner-product distributions of PPMI/SVD embeddings on synthetic latent-kernel SBMs—would reveal whether the guarantee covers the implemented MASO or only an idealized version.","The reduction to a rescaled SBM suggests that latent-kernel versions of other recovery problems, including weak recovery and $K$-community models, should inherit the classical phase transitions with only $a,b$ replaced by $c(\\sigma)a,c(\\sigma)b$; the paper does not prove this extension."],"forward_implications":["If Theorem 3.1 holds, MASO achieves exact recovery exactly under the classical SBM threshold, so the asymptotic community-recovery limit is unaffected by geometric noise.","If Theorem 4.1 holds, GeoDe turns a latent-kernel SBM graph into a near-classical SBM, so downstream spectral or message-passing methods behave as if geometry were absent.","The Amazon experiment implies that real networks with latent-geometric edge formation can be preprocessed by GeoDe to unlock near-perfect label recovery in belief propagation without labeled data.","Because the threshold depends on $c(\\sigma)$, geometric noise renormalizes the effective signal from $(a-b)$ to $c(\\sigma)(a-b)$; denser graphs or larger bandwidths are then needed to compensate."],"supporting_citations":[{"why":"Supplies the spectral-clustering framework and exact-recovery threshold for balanced two-block SBMs that the paper extends.","marker":"[4]"},{"why":"Provides the belief-propagation and Kesten–Stigum threshold analysis used as baseline and recovery benchmark.","marker":"[5]"},{"why":"Introduces the geometric block model where triangle counting achieves near-optimal detection, motivating the noise model.","marker":"[10]"},{"why":"Bethe–Hessian operator used as a spectral baseline that collapses under geometric noise.","marker":"[15]"},{"why":"Motif-Laplacian baseline and triangle-motif counting used in MASO's motif weighting.","marker":"[16]"},{"why":"Matrix Bernstein inequality used to prove the spectral-norm concentration of the noise matrix in Lemma C.3.","marker":"[19]"},{"why":"Davis–Kahan sine-theta theorem used to convert the eigen-gap into a label-error bound.","marker":"[20]"},{"why":"Contiguity/impossibility results used to establish the lower direction of the exact- and weak-recovery thresholds.","marker":"[21]"},{"why":"Belief propagation algorithm used as a real-world baseline that GeoDe boosts.","marker":"[24]"},{"why":"Amazon product metadata dataset from which the 2000-node validation subgraph is constructed.","marker":"[18]"}],"fun_headline_variants":["GeoDe+MASO lifts community recovery to 91% on noisy SBM","Denoising step yields exact recovery in noisy stochastic block models","Attention spectral operator plus denoising beats existing SBM methods","Perfect community recovery on synthetic graphs down to sigma 0.25","Fusion denoiser improves belief propagation by 79.7% on Amazon data"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the embeddings fed into MASO have a fixed cosine geometry—same-community pairs always closer than different-community pairs—and the paper does not prove its random-walk PPMI plus SVD construction actually produces embeddings with that structure.","fun_headline_variants_meta":{"raw":{"variants":["GeoDe+MASO lifts community recovery to 91% on noisy SBM","Denoising step yields exact recovery in noisy stochastic block models","Attention spectral operator plus denoising beats existing SBM methods","Perfect community recovery on synthetic graphs down to sigma 0.25","Fusion denoiser improves belief propagation by 79.7% on Amazon data"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000603,"raw_usage":{"total_tokens":2774,"prompt_tokens":865,"completion_tokens":1909,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":481,"completion_tokens_details":{"reasoning_tokens":1823}},"tokens_in":481,"tokens_out":1909,"duration_ms":13950,"temperature":1.0,"reasoning_tokens":1823,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T21:59:44.543335+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a latent-kernel SBM with parameters satisfying $(\\sqrt{c(\\sigma)a}-\\sqrt{c(\\sigma)b})^2>2$, compute the PPMI/SVD embeddings exactly as in Section 3.2, and measure the inner-product distributions for same-community versus different-community pairs. If those distributions overlap—so $\\rho_{\\mathrm{out}}$ is not strictly below $\\rho_{\\mathrm{in}}$—Theorem 3.1's precondition is violated, and a failure of MASO's exact recovery on graphs where the threshold holds would refute the claim that the guarantee covers the implemented algorithm.","supporting_citations":[{"cited_title":"The Geometric Block Model","cited_arxiv_id":"1709.05510","evidence_quote":"Introduces the geometric block model where triangle counting achieves near-optimal detection, motivating the noise model."},{"cited_title":"Reconstruction and estimation in the planted partition model","cited_arxiv_id":null,"evidence_quote":"Contiguity/impossibility results used to establish the lower direction of the exact- and weak-recovery thresholds."},{"cited_title":"The dynamics of viral marketing","cited_arxiv_id":null,"evidence_quote":"Amazon product metadata dataset from which the 2000-node validation subgraph is constructed."}],"review_version":1}