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

arXiv: https://arxiv.org/abs/2506.03657 · HTML: https://mlsanity.com/paper/2506.03657/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 35 references that are in the map.
- First posted on arXiv 4 Jun 2025.

## Builds on (most cited first, 13 of 13)

- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Robust and computationally feasible community detection in the presence of arbitrary outlier nodes](https://mlsanity.com/paper/1404.6000/) (2014)
- [Convex Relaxation Methods for Community Detection](https://mlsanity.com/paper/1810.00315/) (2018)
- [Graph powering and spectral robustness](https://mlsanity.com/paper/1809.04818/) (2018)
- [A Robust Spectral Clustering Algorithm for Sub-Gaussian Mixture Models with Outliers](https://mlsanity.com/paper/1912.07546/) (2019)
- [Robust Estimation for Random Graphs](https://mlsanity.com/paper/2111.05320/) (2021)
- [Learning Communities in the Presence of Errors](https://mlsanity.com/paper/1511.03229/) (2015)
- [Variational Inference for Stochastic Block Models from Sampled Data](https://mlsanity.com/paper/1707.04141/) (2017)
- [Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptions](https://mlsanity.com/paper/2305.10227/) (2023)
- [Robustness of spectral methods for community detection](https://mlsanity.com/paper/1811.05808/) (2018)
- [Epidemic spreading on complex networks with community structures](https://mlsanity.com/paper/1611.06092/) (2016)
- [Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust](https://mlsanity.com/paper/2405.16663/) (2024)

## Abstract (arXiv)

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.