SubSearch: Robust Estimation and Outlier Detection for Stochastic Block Models via Subgraph Search

Christine Keribin (LMO); Leonardo Martins Bianco (LMO); MaIAGE); Zacharie Naulet (INRAE

SubSearch: Robust Estimation and Outlier Detection for Stochastic Block Models via Subgraph Search

T0 review · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Searching subgraphs of a corrupted network recovers its block-model parameters and flags the nodes that break the model.

desk verdict 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. read the letter →

arxiv 2506.03657 v1 pith:KJW7Q3CJ submitted 2025-06-04 stat.ML cs.LG

Leonardo Martins Bianco (LMO) , Christine Keribin (LMO) , Zacharie Naulet (INRAE , MaIAGE) This is my paper

classification stat.MLcs.LG MSC 62H3062F3505C80

keywords stochasticblockmodelrobustestimationoutlierdetectionnodeadversarialcorruptionsimulatedannealingspectralnormsubgraphsearchcommunity

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

The 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.

The 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.

Verdict: 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main error bound and objective are logically independent, and the flagged overlap gap is a correctness risk rather than a circular reduction.

full rationale

The paper's derivation chain is not circular. Theorem 3.1 is a standalone bound whose right-hand side contains the true parameter (max_k Gamma_kk), the inlier fluctuation term, and the algorithm's cost c(S)=||A_S - Qhat(S)||. Minimizing c(S) is justified as controlling the only term under the algorithm's choice, and the paper explicitly qualifies this with the additional assumptions c(S)=O(sqrt(n)) and overlap = O(n) without claiming the optimizer enforces the overlap condition. The convergence statement Proposition 3.2 is an independently cited result of Mitra et al. with no author overlap, and the paper immediately notes that Algorithm 1 uses a geometric cooling schedule that lacks those guarantees. The scalar Qhat(S) being computed on the same subgraph S whose cost is minimized is inherent to a fitting objective, and the paper does not present that self-consistency as an independent prediction. Experimental comparisons to an oracle, filtering, and pruning baselines provide external calibration. The reviewer concern about the unconstrained denominator min_k |S_k cap Omega_k cap F| is a substantive robustness/correctness gap, but it is not a circular derivation: the paper does not formally claim that the returned subgraph satisfies the theorem's overlap condition, only that the bound motivates the objective and that experiments illustrate the ratio. No fitted input is renamed as a prediction, no load-bearing self-citation appears, and no uniqueness claim is imported from the authors' own prior work.

Assumptions & free parameters 7 free parameters · 5 assumptions · 0 invented entities

No new entities are introduced; outlier and inlier nodes are standard corruption-model objects, and the subgraph is a subset of existing nodes. The central claim rests mainly on tuning hyperparameters and on the unverified assumption that the objective's minimizer also preserves community overlap.

free parameters (7)

Corruption fraction gamma = 0.10-0.40 in experiments; 0.3 in single run
The algorithm fixes subgraph size to (1-gamma)n and Markov chain length to gamma*n; misspecification changes the candidate space. The paper assumes gamma is known.
Cooling rate c = 0.99
Geometric cooling schedule T_{t+1}=c*T_t; no theoretical guarantee at this rate. Chosen from SA practice.
Number of outer iterations t_max = 1000
Stopping horizon; affects solution quality and runtime.
Markov chain length for each temperature = L_t=gamma*n (e.g., 60 for n=200, gamma=0.3)
Number of neighbor proposals per temperature; set equal to the number of outliers.
Stopping tolerance and patience = epsilon=1e-4, ttol=25
Stops when maximal absolute cost variation over 25 chains is below tolerance.
Initial temperature T0 = Adaptive through acceptance-rate heuristic (2.25 in single-run)
Multiplied by 1.5 until acceptance near 1; impacts the exploration phase.
Random seed = 12345
Used for all simulated annealing experiments; reproducibility aid, but also a fixed choice that may mask run-to-run variation.

assumptions (5)

domain assumption Graph is generated by an SBM with known number of communities K and positive community sizes.
Used throughout Section 2 to define the target Gamma and the expectation E[A]=Q-diag(Q).
domain assumption Corruption is node-adversarial: an adversary arbitrarily modifies the adjacencies of up to gamma*n nodes, with gamma known.
Problem statement in Section 2; the subgraph size (1-gamma)n is derived from this budget, and the theorem's inlier set F is defined by it.
standard math For the inlier subgraph, ||A_F - E[A]_F|| = O(sqrt((1-gamma)n)), using spectral clustering consistency of Lei and Rinaldo (2015).
Invoked in Section 3.1 to argue the first two terms in Theorem 3.1 are O(sqrt(n)) and independent of S.
ad hoc to paper Simulated annealing with the implemented geometric cooling converges to a global optimum, despite Proposition 3.2 only covering inverse-logarithmic cooling.
Section 3.2 admits faster schedules are used in practice without guarantees; the method's success depends on this.
ad hoc to paper There exists a size-(1-gamma)n subgraph with spectral cost O(sqrt(n)) and overlap min_k |S_k ∩ Omega_k ∩ F| = O(n).
The argument after Theorem 3.1 requires both conditions to reach O(n^-1/2) error, but the objective only enforces the first; Fig. 3b verifies the ratio empirically for one configuration.

how reviews work

0 comments

Cite this review

Pith. "Pith review of SubSearch: Robust Estimation and Outlier Detection for Stochastic Block Models via Subgraph Search." pith.science (2026). https://pith.science/paper/KJW7Q3CJ

@misc{pith2026250603657,
  author       = {Pith},
  title        = {Pith review of: SubSearch: Robust Estimation and Outlier Detection for Stochastic Block Models via Subgraph Search},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KJW7Q3CJ}},
  note         = {Machine review of arXiv:2506.03657}
}

read the original abstract

Community detection is a fundamental task in graph analysis, with methods often relying on fitting models like the Stochastic Block Model (SBM) to observed networks. While many algorithms can accurately estimate SBM parameters when the input graph is a perfect sample from the model, real-world graphs rarely conform to such idealized assumptions. Therefore, robust algorithms are crucial-ones that can recover model parameters even when the data deviates from the assumed distribution. In this work, we propose SubSearch, an algorithm for robustly estimating SBM parameters by exploring the space of subgraphs in search of one that closely aligns with the model's assumptions. Our approach also functions as an outlier detection method, properly identifying nodes responsible for the graph's deviation from the model and going beyond simple techniques like pruning high-degree nodes. Extensive experiments on both synthetic and real-world datasets demonstrate the effectiveness of our method.

Figures

Figures reproduced from arXiv: 2506.03657 by the authors.

**Figure 2.** Results for single-run experiments [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗

**Figure 3.** Results for multi-run experiments. of perturbation γ = [0.10, 0.15, . . . , 0.40], then generate graphs per gamma = 10 graphs for each amount of corruption. The estimation error is impacted by the variability of the graph generated and by the intrinsic randomness of the algorithm used. To isolate the impact due to the first of these effects from the second, we run each method runs per graph = 3 times per graph an… view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: Results for real data experiment [PITH_FULL_IMAGE:figures/full_fig_p009_4.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

28 extracted references · 22 canonical work pages

[1]

Abbe, E., Boix-Adserà, E., Ralli, P., and Sandon, C. (2020). Graph powering and spectral robustness. SIAM Journal on Mathematics of Data Science , 2(1):132–157

work page 2020
[2]

T., and Zhang, H

Acharya, J., Jain, A., Kamath, G., Suresh, A. T., and Zhang, H. (2022). Robust estimation for random graphs. In Loh, P.-L. and Raginsky, M., editors, Proceedings of Thirty Fifth Conference on Learning Theory , volume 178 of Proceedings of Machine Learning Research , pages 130--166. PMLR

work page 2022
[3]

Cai, T. T. and Li, X. (2015). Robust and computationally feasible community detection in the presence of arbitrary outlier nodes

work page 2015
[4]

Chen, H., Ding, J., Hua, Y., and Steurer, D. (2024). Private edge density estimation for random graphs: Optimal, efficient and robust. arXiv preprint arXiv:2405.16663

work page Pith review arXiv 2024
[5]

Delahaye, D., Chaimatanan, S., and Mongeau, M. (2019). Simulated annealing: From basics to applications. Handbook of metaheuristics , pages 1--35

work page 2019
[6]

Diakonikolas, I., Kamath, G., Kane, D., Li, J., Moitra, A., and Stewart, A. (2019). Robust estimators in high-dimensions without the computational intractability. SIAM Journal on Computing , 48(2):742--864

2019
[7]

M., Li, J., Moitra, A., and Stewart, A

Diakonikolas, I., Kamath, G., Kane, D. M., Li, J., Moitra, A., and Stewart, A. (2021). Robustness meets algorithms. Commun. ACM , 64(5):107–115

work page 2021
[8]

Ding, J., d'Orsi, T., Hua, Y., and Steurer, D. (2023). Reaching Kesten - Stigum Threshold in the Stochastic Block Model under Node Corruptions . arXiv:2305.10227 [cs, stat]

work page Pith review arXiv 2023

Show all 28 references

[9]

Gleiser, P. M. and Danon, L. (2003). Community structure in jazz. Advances in complex systems , 6(04):565--573

2003
[10]

H., and Johnson, A

Henderson, D., Jacobson, S. H., and Johnson, A. W. (2003). The theory and practice of simulated annealing. Handbook of metaheuristics , pages 287--319

2003
[11]

W., Laskey, K

Holland, P. W., Laskey, K. B., and Leinhardt, S. (1983). Stochastic blockmodels: First steps. Social Networks , 5(2):109--137

1983
[12]

Jana, S., Fan, J., and Kulkarni, S. (2024). A general theory for robust clustering via trimmed mean. arXiv preprint arXiv:2401.05574

2024 arXiv
[13]

and Newman, M

Karrer, B. and Newman, M. E. (2011). Stochastic blockmodels and community structure in networks. Physical Review E—Statistical, Nonlinear, and Soft Matter Physics , 83(1):016107

2011
[14]

D., and Vecchi, M

Kirkpatrick, S., Gelatt Jr, C. D., and Vecchi, M. P. (1983). Optimization by simulated annealing. science , 220(4598):671--680

1983
[15]

V., and Krishna, P

Lalwani, D., Somayajulu, D. V., and Krishna, P. R. (2015). A community driven social recommendation system. In 2015 IEEE International conference on big data (big data) , pages 821--826. IEEE

2015
[16]

and Rinaldo, A

Lei, J. and Rinaldo, A. (2015). Consistency of spectral clustering in stochastic block models . The Annals of Statistics , 43(1):215 -- 237

2015
[17]

Li, X., Chen, Y., and Xu, J. (2021). Convex relaxation methods for community detection

2021
[18]

Macqueen, J. (1967). Some methods for classification and analysis of multivariate observations. In Proceedings of 5-th Berkeley Symposium on Mathematical Statistics and Probability/University of California Press

1967
[19]

Makarychev, K., Makarychev, Y., and Vijayaraghavan, A. (2016). Learning communities in the presence of errors. In Feldman, V., Rakhlin, A., and Shamir, O., editors, 29th Annual Conference on Learning Theory , volume 49 of Proceedings of Machine Learning Research , pages 1258--...

2016
[20]

Mitra, D., Romeo, F., and Sangiovanni-Vincentelli, A. (1986). Convergence and finite-time behavior of simulated annealing. Advances in applied probability , 18(3):747--771

1986
[21]

Sangkaran, T., Abdullah, A., and Jhanjhi, N. (2020). Criminal community detection based on isomorphic subgraph analytics. Open Computer Science , 10(1):164--174

2020
[22]

and Malik, J

Shi, J. and Malik, J. (2000). Normalized cuts and image segmentation. IEEE Transactions on pattern analysis and machine intelligence , 22(8):888--905

2000
[23]

R., Sarkar, P., and Hanasusanto, G

Srivastava, P. R., Sarkar, P., and Hanasusanto, G. A. (2021). A Robust Spectral Clustering Algorithm for Sub - Gaussian Mixture Models with Outliers . arXiv:1912.07546 [cs, math, stat]

2021 arXiv
[24]

Stegehuis, C., Van Der Hofstad, R., and Van Leeuwaarden, J. S. (2016). Epidemic spreading on complex networks with community structures. Scientific reports , 6(1):29748

2016
[25]

and Massouli \'e , L

Stephan, L. and Massouli \'e , L. (2019). Robustness of spectral methods for community detection. In Conference on Learning Theory , pages 2831--2860. PMLR

2019
[26]

Tabouy, T., Barbillon, P., and Chiquet, J. (2020). Variational inference for stochastic block models from sampled data. Journal of the American Statistical Association , 115(529):455--466

2020
[27]

J., Aarts, E

Van Laarhoven, P. J., Aarts, E. H., van Laarhoven, P. J., and Aarts, E. H. (1987). Simulated annealing . Springer

1987
[28]

Von Luxburg, U. (2007). A tutorial on spectral clustering. Statistics and computing , 17:395--416

2007

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Abbe, E., Boix-Adserà, E., Ralli, P., and Sandon, C. (2020). Graph powering and spectral robustness. SIAM Journal on Mathematics of Data Science , 2(1):132–157

work page 2020

[2] [2]

T., and Zhang, H

Acharya, J., Jain, A., Kamath, G., Suresh, A. T., and Zhang, H. (2022). Robust estimation for random graphs. In Loh, P.-L. and Raginsky, M., editors, Proceedings of Thirty Fifth Conference on Learning Theory , volume 178 of Proceedings of Machine Learning Research , pages 130--166. PMLR

work page 2022

[3] [3]

Cai, T. T. and Li, X. (2015). Robust and computationally feasible community detection in the presence of arbitrary outlier nodes

work page 2015

[4] [4]

Chen, H., Ding, J., Hua, Y., and Steurer, D. (2024). Private edge density estimation for random graphs: Optimal, efficient and robust. arXiv preprint arXiv:2405.16663

work page Pith review arXiv 2024

[5] [5]

Delahaye, D., Chaimatanan, S., and Mongeau, M. (2019). Simulated annealing: From basics to applications. Handbook of metaheuristics , pages 1--35

work page 2019

[6] [6]

Diakonikolas, I., Kamath, G., Kane, D., Li, J., Moitra, A., and Stewart, A. (2019). Robust estimators in high-dimensions without the computational intractability. SIAM Journal on Computing , 48(2):742--864

2019

[7] [7]

M., Li, J., Moitra, A., and Stewart, A

Diakonikolas, I., Kamath, G., Kane, D. M., Li, J., Moitra, A., and Stewart, A. (2021). Robustness meets algorithms. Commun. ACM , 64(5):107–115

work page 2021

[8] [8]

Ding, J., d'Orsi, T., Hua, Y., and Steurer, D. (2023). Reaching Kesten - Stigum Threshold in the Stochastic Block Model under Node Corruptions . arXiv:2305.10227 [cs, stat]

work page Pith review arXiv 2023