{"id":"505eb0be-47ea-44c0-b6a5-fe2128155109","arxiv_id":"2506.03657","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":7,"one_line_summary":"SubSearch uses simulated annealing to select a subgraph that best matches a stochastic block model, giving robust parameter estimates and outlier detection under node corruption.","lead":"SubSearch is a new algorithm that finds a clean subgraph of a corrupted network and fits a stochastic block model to it, using simulated annealing to search many candidate subgraphs. It recovers connection probabilities and flags the nodes responsible for the network's deviation from the model, including on a real jazz collaboration graph where standard spectral clustering fails.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"SubSearch minimizes only c(S), while Theorem 3.1's error bound is governed by c(S)/min_k |S_k∩Ω_k∩F|; nothing in the objective or the SA schedule keeps the overlap denominator large, so the advertised O(n^{-1/2}) guarantee can fail for the returned subgraph.","rationale":"I read the paper in good faith as proposing a robust SBM parameter estimator by minimizing the spectral fit of a size-(1-γ)n subgraph. Theorem 3.1 is a plausible deterministic bound, and the balanced synthetic experiments are consistent with it. The load-bearing gap is the link between the optimized quantity and the theorem's denominator. The reader's weakest_assumption identifies exactly this gap; my concern sharpens it: the failure is not merely 'could happen' but is a concrete regime (imbalanced communities, adversary targeting the smallest community) where low cost and small overlap are compatible. The proposed experiment would distinguish a benign numerical issue from a structural one. I do not see an internal inconsistency in the theorem itself, and the paper's code and reproducibility are positive evidence. The verdict should remain conditional: the idea is worth developing, but the central guarantee is not yet delivered for the returned subgraph. Secondary issues (deferred proof, best-of-three selection, geometric cooling) reinforce the same conditional status without changing it.","tokens_in":11750,"tokens_out":7160,"duration_ms":80615,"concrete_test":"Run SubSearch on a synthetic SBM with K=3 and imbalanced communities, e.g., n=300, sizes 150/120/30, within-community probability 0.6 and cross probability 0.2; corrupt γ=0.2 of nodes, drawing a large fraction of the corruptions from the smallest community. Repeat with at least 10 seeds, using the paper's default settings, and record min_k |S_k∩Ω_k∩F|, c(S), and the error of the estimated Γ for the small community. If the returned S has min overlap below 0.05n while c(S) remains O(√n), then the denominator condition in Theorem 3.1 is not enforced by the objective and the O(n^{-1/2}) claim does not follow; if min overlap stays Θ(n) in this targeted setting, the concern is resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central guarantee is Theorem 3.1, whose RHS is K^2/min_k |S_k∩Ω_k∩F| times (max_k Γ_kk + ||A_F - E[A]_F|| + ||A_S - Qhat(S)||). SubSearch minimizes the last term, c(S)=||A_S - Qhat(S)||, over S of size (1-γ)n; it does not evaluate or constrain the denominator. A subgraph can achieve low c(S) by dropping or merging a small community: when the true community is small, the spectral-norm penalty of absorbing it into a larger fitted block can be modest relative to the residual of the large blocks, while min_k |S_k∩Ω_k∩F| collapses. Then the theorem's RHS no longer decays as O(n^{-1/2}), even if c(S)=O(√n). The paper's heuristic that few outliers cannot conspire (Section 3.2) controls bias once a good S is given; it does not control the optimizer's choice of S. Section 4.2's Figure 3b measures the cost-to-overlap ratio only in balanced synthetic graphs and does not establish that the algorithm returns an S with Ω(n) overlap under targeted or imbalanced corruption. Additionally, Algorithm 1 uses geometric cooling, so even the low-cost premise is only heuristic; Proposition 3.2 requires logarithmic cooling.","agreement_with_reader":"agree"},"referee_report":null,"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"SubSearch is a genuinely useful practical method with an honest but incomplete theoretical story. What is new: a K>1 generalization of the Acharya et al. bound, a simulated-annealing search over fixed-size subgraphs with a spectral cost, and outlier detection that goes beyond degree pruning. The code is public, the experiments are reproducible, and the authors are candid about the proof being in the supplement and about the geometric cooling schedule being a heuristic. That honesty earns credit.\n\nThe stress-test concern lands. Theorem 3.1's error bound has a denominator, min_k |S_k ∩ Omega_k ∩ F|, that must stay Omega(n) for the O(n^{-1/2}) rate. But the algorithm minimizes only c(S) = ||A_S - Qhat(S)||. Nothing in the objective or the annealing schedule prevents the search from dropping a small community: if a community is small, absorbing it into a larger block can reduce the spectral residual while collapsing the overlap term. The heuristic about few outliers conspiring is about bias once a good S is given, not about the optimizer's choice. Section 4.2's Figure 3b only checks balanced graphs. So the advertised guarantee is not actually established for the subgraph the algorithm returns. This is a real gap, but it is addressable — either by proving a lower bound on the overlap under some conditions, or by adding an explicit overlap/balance penalty to the cost and testing on imbalanced and targeted corruption.\n\nThe experiments are thinner than the text suggests: 10 graphs per gamma, best-of-three selection, a Beta perturbation model that may not be adversarial, and no comparison against the stronger related estimators (Chen et al. SoS, Jana et al.). The single-run example is illustrative, not evidence of general behavior. These are soft spots, not fatal flaws.\n\nVerdict: the paper deserves a serious referee. The method is novel enough, the code and experiments are real, and the theoretical gap is clearly identified by the authors' own framing (they say the bound \"motivates\" the cost, not that the algorithm achieves it). A good referee will push for a revised version that either closes the overlap gap or states plainly what is heuristic. I'd bring it to a reading group focused on robust network analysis, and I'd cite it if I worked on that topic. Send it to peer review.","headline":"SubSearch is a genuinely useful practical method with an honest but incomplete theoretical story: the bound needs an overlap term that the algorithm never controls, so the advertised rate is not actually guaranteed for the returned subgraph.","tokens_in":718,"tokens_out":1706,"would_cite":true,"duration_ms":32564,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62H30","62F35","05C80"],"pacs":[],"model":"deepseek-v4-flash","headline":"Searching subgraphs of a corrupted network recovers its block-model parameters and flags the nodes that break the model.","keywords":["stochastic block model","robust estimation","outlier detection","node adversarial corruption","simulated annealing","spectral norm","subgraph search","community detection"],"falsifier":"Fix an SBM with three communities in very unequal sizes, corrupt the smallest community heavily, run SubSearch with the recommended hyperparameters on many repetitions, and measure min_k |S_k ∩ Ω_k ∩ F| and the actual parameter error on the returned subgraph; if the cost stays low while this overlap is small and the error does not decay as O($n^{{−1/2}}$), the practical claim fails.","tokens_in":11560,"feed_emoji":"🔍","tokens_out":4838,"duration_ms":45187,"temperature":0.7,"pith_summary":"This paper tries to establish that the community structure and connection probabilities of a Stochastic Block Model can still be recovered from a network in which an adversary has tampered with the edges of a fraction of nodes. The central proposal, SubSearch, keeps every candidate solution the same size—a subgraph containing (1−γ)n nodes—and searches that space with simulated annealing to minimize the spectral mismatch between the observed subgraph adjacency matrix and the block model's estimated expectation. The paper proves an error bound that ties this spectral mismatch to parameter-estimation error, up to a factor that shrinks like the inverse of the smallest community overlap inside the chosen subgraph. If the claim holds, robust parameter estimation and interpretable outlier detection are achievable under a mild budget of corruption, going beyond pruning high-degree nodes.","feed_headline":"Subgraph search recovers hidden communities in corrupted networks","feed_subtitle":"A simulated-annealing search over subgraphs estimates block-model parameters and flags outlier nodes that break the fit.","key_machinery":"The load-bearing object is the cost function c(S)=||A_S−Qhat(S)||, the spectral norm of the difference between the adjacency matrix restricted to a subgraph S and Qhat(S)=SΓhatS^T, the block-model approximation built from the empirical connectivity matrix on that subgraph. This cost appears in the numerator of the Theorem 3.1 bound; SubSearch is a simulated-annealing procedure whose neighborhood moves swap one node inside the current subgraph for an adjacent node outside it, keeping |S| fixed at (1−γ)n, so that a lower cost reflects a genuinely better-fitting subgraph rather than a smaller one. The temperature schedule starts adaptively high and cools geometrically, and the algorithm returns the lowest-cost subgraph, which is then used to estimate Γ and to flag the excluded nodes as outliers.","core_discovery":"The paper's central claim is that minimizing c(S)=||A_S−Qhat(S)|| over subgraphs S of size (1−γ)n yields an estimator of the connectivity matrix Γ whose error is controlled by Theorem 3.1: the sum over pairs of communities of |Γ_kl−GammaHat_kl| is at most $K^{2}$/(min_k |S_k ∩ Ω_k ∩ F|) times (max_k Γ_kk + ||A_F−E[A]_F|| + ||A_S−Qhat(S)||). The first two terms are intrinsic to the sample and decay or stay bounded; the only term the algorithm controls is the spectral mismatch on S. The paper argues that when this mismatch mimics the inlier block-model behavior, the error decays as O($n^{{−1/2}}$), and experiments show SubSearch's error close to the oracle (0.05 versus 0.02 in a single-run comparison) while filtering and pruning baselines fail.","pith_inferences":["The bound's denominator min_k |S_k ∩ Ω_k ∩ F| is not optimized by the cost function, so the practical guarantee hinges on whether simulated annealing's low-cost subgraphs also preserve all communities; a reader could test this by comparing returned subgraphs to planted communities in synthetic graphs across community-size imbalances.","The same search-over-subgraphs idea could be applied to degree-corrected SBMs or other generative models by changing the estimated Qhat, though the paper does not establish theory for that.","The runtime comparison (14 minutes versus seconds) suggests the robustness price is substantial; scaling to tens of thousands of nodes would likely require a faster move proposal or warm starts, which the paper only mentions as a belief."],"forward_implications":["If correct, SubSearch extends robust parameter estimation to stochastic block models with K>1, the regime where previous single-community filtering fails or removes too many inliers.","The same run provides an outlier set: nodes left out of the best subgraph are candidates responsible for model deviation, including moderate-degree nodes that degree pruning misses.","Under the conditions stated after Theorem 3.1, estimation error decays as O(n^{−1/2}) in graph size for a fixed corruption fraction γ.","The method is applicable to real graphs where spectral clustering alone fails, as demonstrated on the jazz collaboration network by recovering three collaboration groups.","The theoretical guarantee is not tied to a specific clustering algorithm; any clustering producing the partition S_1,...,S_K inside S feeds the bound."],"supporting_citations":[{"why":"Establishes the K=1 precursor bound and the filtering algorithm that SubSearch generalizes to multiple communities.","marker":"Acharya et al. (2022)"},{"why":"Supplies the consistency result used to bound the inlier spectral norm ||A_F−E[A]_F|| and the spectral clustering baseline.","marker":"Lei and Rinaldo (2015)"},{"why":"Defines the stochastic block model whose connectivity parameters SubSearch estimates.","marker":"Holland et al. (1983)"},{"why":"Introduces simulated annealing, the optimization engine of SubSearch.","marker":"Kirkpatrick et al. (1983)"},{"why":"Provides the convergence result for simulated annealing quoted as Proposition 3.2.","marker":"Mitra et al. (1986)"},{"why":"Supplies the jazz collaboration dataset used in the real-graph experiment.","marker":"Gleiser and Danon (2003)"},{"why":"Offers an alternative Sum-of-Squares robust estimation approach that the paper positions against in related work.","marker":"Chen et al. (2024)"}],"fun_headline_variants":["SubSearch: robust SBM estimation and outlier detection","Subgraph search finds communities in corrupted graphs","Robust community detection by searching subgraphs","Outlier detection for stochastic block models made robust","Subgraph search cleans up noisy network data"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole guarantee rests on the subgraph returned by the search still containing most inliers of every community; the cost function being minimized has no explicit term for that overlap, so a bad search outcome would make the denominator in the error bound small and the advertised O($n^{{−1/2}}$) error no longer follow.","fun_headline_variants_meta":{"raw":{"variants":["SubSearch: robust SBM estimation and outlier detection","Subgraph search finds communities in corrupted graphs","Robust community detection by searching subgraphs","Outlier detection for stochastic block models made robust","Subgraph search cleans up noisy network data"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000474,"raw_usage":{"total_tokens":2326,"prompt_tokens":888,"completion_tokens":1438,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":504,"completion_tokens_details":{"reasoning_tokens":1369}},"tokens_in":504,"tokens_out":1438,"duration_ms":12209,"temperature":1.0,"reasoning_tokens":1369,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T10:57:29.010048+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Fix an SBM with three communities in very unequal sizes, corrupt the smallest community heavily, run SubSearch with the recommended hyperparameters on many repetitions, and measure min_k |S_k ∩ Ω_k ∩ F| and the actual parameter error on the returned subgraph; if the cost stays low while this overlap is small and the error does not decay as O($n^{{−1/2}}$), the practical claim fails.","supporting_citations":[{"cited_title":"T., and Zhang, H","cited_arxiv_id":null,"evidence_quote":"Establishes the K=1 precursor bound and the filtering algorithm that SubSearch generalizes to multiple communities."},{"cited_title":"D., and Vecchi, M","cited_arxiv_id":null,"evidence_quote":"Introduces simulated annealing, the optimization engine of SubSearch."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the convergence result for simulated annealing quoted as Proposition 3.2."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the jazz collaboration dataset used in the real-graph experiment."},{"cited_title":"Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust","cited_arxiv_id":"2405.16663","evidence_quote":"Offers an alternative Sum-of-Squares robust estimation approach that the paper positions against in related work."}],"review_version":1}