<figure><img src="image_1.png" /></figure>

HAL
open science

# Robust estimation and outlier detection for Stochastic Block Models via subgraph search

Leonardo Martins Bianco, Christine Keribin, Zacharie Naulet

► To cite this version:

Leonardo Martins Bianco, Christine Keribin, Zacharie Naulet. Robust estimation and outlier detection for Stochastic Block Models via subgraph search. 2025. hal-05446755

HAL Id: hal-05446755

https://inria.hal.science/hal-05446755v1

Submitted on 7 Jan 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
Robust estimation and outlier detection for
Stochastic Block Models via subgraph search

L. MARTINS BIANCO ¹, Ch. KERIBIN ¹, Z. NAULET ²

¹Université Paris-Saclay, CNRS, Inria, Laboratoire de mathématiques d'Orsay,
France

²Université Paris-Saclay, INRAE, MaIAGE, Jouy-en-Josas, France

CMStatistics 2025, London- December 15, 2025

<figure><img src="image_3.png" /></figure>
## Introduction

### A theoretical result

### The SUBSEARCH algorithm
Graph: $G = (V, E)$

where $V = \{1, ..., n\}$ set of nodes; $E \subset V \times V$ set of edges

* Adjacency matrix: $A \in \{0, 1\}^{n \times n}$

* $A_{ij} = 1$ if $(i, j) \in E$; 0 otherwise

* symmetric (undirected graph)

<figure><img src="image_4.png" /><figcaption>Jazz collaborations in New York, Chicago, and elsewhere [Gleiser '03]</figcaption></figure>
Graph: $G = (V, E)$
where $V = \{1, ..., n\}$ set of nodes; $E \subset V \times V$ set of edges

* Adjacency matrix: $A \in \{0, 1\}^{n \times n}$
  * $A_{ij} = 1$ if $(i, j) \in E$; 0 otherwise
  * symmetric (undirected graph)

* Graph clustering: define a node partition grouping nodes with similar connection pattern
  * inferring the *hidden* partition : community recovery
  * estimating the connectivity parameters

<figure><img src="image_5.png" /><figcaption>Jazz collaborations in New York, Chicago, and elsewhere [Gleiser '03]</figcaption></figure>
❖ A generative model: $(Z, A) \sim \text{SBM}_K(\pi, \Gamma)$

$$ \begin{cases} \mathbb{P}(Z_i = k) = \pi_k \\ \mathbb{P}(A_{ij} = 1 | Z_i = k, Z_j = l) = \Gamma_{kl} \end{cases} $$

$K \to \text{nb. of clusters}$

$\pi_k \to \text{weight of cluster } k, \sum_k \pi_k = 1$

$Z_i \to \text{ind. latent label, cluster of node } i$

$(\Omega_k = \{i : Z_i = k\})_{k=1,...,K}: \text{node partition into } K \text{ clusters}$

$\Gamma_{kl} \to \text{connectivity } k, l$

<figure><img src="image_6.png" /></figure>

❖ Methods with guarantees under SBM spectral [Lei & Rinaldo 15], SDP [Li et al. 21], variational approaches [Tabouy et al. 20]
corruption = adversarial node perturbations

1. $(Z, A_{\text{pure}}) \sim \text{SBM}_K(\pi, \Gamma)$

2. Adversary arbitrarily changes **edges** incident to an arbitrary set of $\gamma n$ **nodes** $\leftrightarrow$ outlier nodes

3. Corrupted $A$ is observed

<figure><img src="image_7.png" /></figure>
Developing robust algorithms producing reliable results even with adversarial node perturbations

* **weak recovery**: better than random guessing [Stephan & Massoulié '19]: spectral method; balanced communities; small $\gamma$; an hyperparameter difficult to set in practice

* **strong recovery**: the initial partition is recovered with high probability [Cai & Li '15]: penalized SDP problem; with known parameters [Liu & Moitra '22]: polynomial time algorithm (monotone perturbations) with known parameters

* **estimation**: ?
# The corrupted SBM: parameter estimation

Estimate $\Gamma$ under worst-case adversary

→

❖ Difficult problem:

▶ knowing the community structure is insufficient for parameter estimation

▶ identifying outliers causing the distortion of true parameters is non trivial

▶ robust community recovery requires prior knowledge of the SBM parameters

❖ For $K = 1$, solved by [Acharya et al. '22]

How to robustly estimate $\Gamma$ for $K > 1$?

→
Case of corrupted Erdös-Rényi graph (K=1)

[Acharya et al. '22]

❖ gives a certification bound on the estimation error on a corrupted SBM$_1(1, p)$

For a subset $S$ of nodes ($|S| > n/2$), let $A_S$ the restricted adjacency matrix and $\hat{p}_S$ the empirical edge density,

$$|\hat{p}_S - p| \le \frac{\|A_S - \hat{p}_S\|_{op}}{(1/2 - \gamma)n}$$

❖ iteratively optimizes this bound by sampling a node $i$ to remove according to $M(1, w)$, where $w$ is the vector of the squared entries of the normalized top eigenvector of $A_S - \hat{p}_S$.

► removes more outliers than inliers

► eventually makes the empirical density estimation correct
## Introduction

## A theoretical result

## The SUBSEARCH algorithm
Theoretical contribution: certification bound for $K > 1$

❖ Idea: find subgraph $S = S_1 \cup \dots \cup S_K$ excluding outliers

$$ \Rightarrow \quad \hat{\Gamma}_{kl} = \left( \sum_{i \in S_k, j \in S_l} A_{ij} \right) / |S_k||S_l| \quad \text{is a good estimator} $$

❖ Extend Acharya's error bound to $K > 1$

**Theorem** [Martins Bianco et al. '25] Let $S = S_1 \cup \dots \cup S_K$ be a subgraph, $\Omega_k$ the nodes in community $k$, $\mathcal{I}$ the inliers. Let $\hat{\Gamma}_{kl} = (\sum_{i \in S_k, j \in S_l} A_{ij}) / |S_k||S_l|$ and $\hat{Q}(S)_{ij} = \hat{\Gamma}_{S(i)S(j)}$. Then,

$$ \|\Gamma - \hat{\Gamma}\|_1 \le \frac{\|A_S - \hat{Q}(S)\|_{op}}{\min_{1 \le k \le K} |\Omega_k \cap S_k \cap \mathcal{I}|} $$
* Idea: find subgraph S excluding worst outliers

* SUBSEARCH algorithm, finding S by optimizing $c(S) := ||A_S - \hat{Q}(S)||_{op}$ via Simulated Annealing

* Code: github.com/leobianco/robust_estim_sbm
# Outline

## Introduction

## A theoretical result

## The SUBSEARCH algorithm
Explore the space $\mathcal{S}$ of subgraphs
$\mathcal{S} \subset G$ of size $(1 - \gamma)n$, to minimize
$c(\mathcal{S}) = \|A_{\mathcal{S}} - \hat{Q}(\mathcal{S})\|_{\text{op}}$

<figure><img src="image_8.png" /></figure>
Explore the space $\mathcal{S}$ of subgraphs
$\mathcal{S} \subset G$ of size $(1-\gamma)n$, to minimize
$c(\mathcal{S}) = \|A_{\mathcal{S}} - \hat{Q}(\mathcal{S})\|_{\text{op}}$

① Initialize: random subgraph $S_0$, high temperature $T_0$

<figure><img src="image_9.png" /></figure>
Explore the space $\mathcal{S}$ of subgraphs
$S \subset G$ of size $(1 - \gamma)n$, to minimize
$c(S) = \|A_S - \hat{Q}(S)\|_{\text{op}}$

① Initialize: random subgraph $S_0$, high temperature $T_0$

② Propose $S_{\text{candidate}}$: swap $i \in S_{\text{current}}$ with $j \notin S_{\text{current}}$

<figure><img src="image_10.png" /></figure>
Explore the space $\mathcal{S}$ of subgraphs
$S \subset G$ of size $(1 - \gamma)n$, to minimize
$c(S) = \|A_S - \hat{Q}(S)\|_{op}

① Initialize: random subgraph $S_0$, high temperature $T_0$

② Propose $S_{\text{candidate}}$: swap $i \in S_{\text{current}}$ with $j \notin S_{\text{current}}$

③ Accept or reject: compute
$\Delta = c(S_{\text{current}}) - c(S_{\text{candidate}})$,
accept with probability
$\min(1, \exp(\Delta/T_t))$

<figure><img src="image_11.png" /></figure>

$S_{\text{current}}$
Explore the space $\mathcal{S}$ of subgraphs
$S \subset G$ of size $(1 - \gamma)n$, to minimize
$c(S) = \|A_S - \hat{Q}(S)\|_{op}

① Initialize: random subgraph $S_0$, high temperature $T_0$

② Propose $S_{\text{candidate}}$: swap $i \in S_{\text{current}}$ with $j \notin S_{\text{current}}$

③ Accept or reject: compute
$\Delta = c(S_{\text{current}}) - c(S_{\text{candidate}})$,
accept with probability
$\min(1, \exp(\Delta/T_t))$

④ Cool down: $T_{t+1} = c T_t, c \approx 1$

<figure><img src="image_12.png" /></figure>

$S_{\text{current}}$
Explore the space $\mathcal{S}$ of subgraphs
$S \subset G$ of size $(1 - \gamma)n$, to minimize
$c(S) = \|A_S - \hat{Q}(S)\|_{op}

① Initialize: random subgraph $S_0$, high temperature $T_0$

② Propose $S_{\text{candidate}}$: swap $i \in S_{\text{current}}$ with $j \notin S_{\text{current}}$

③ Accept or reject: compute
$\Delta = c(S_{\text{current}}) - c(S_{\text{candidate}})$,
accept with probability
$\min(1, \exp(\Delta/T_t))$

④ Cool down: $T_{t+1} = c T_t, c \approx 1$

<figure><img src="image_13.png" /></figure>

$S_{\text{final}}$
1. Sample an **uncorrupted graph** from an SBM and $m = \lfloor yn \rfloor$ nodes to be the outliers.

2. For each outlier $i = 1, \dots, m$ and each $k = 1, \dots, K$, draw a **new connection probability** between that node and nodes in community $k$ using a **Beta distribution**, i.e., $\tilde{\Gamma}_{ik} \sim \mathcal{B}(\alpha, \beta)$.

Here, $\alpha$ and $\beta$ are chosen so that $\mathbb{E}[\tilde{\Gamma}_{ik}] = \Gamma_{z(i)k}$ and that the variance is the greatest possible (with the constraint that $\tilde{\Gamma}_{ik} \in [0, 1)$).

$\leftarrow$ deteriorates empirical density estimates while **avoiding** obvious variations of degree
Experiments on a single run: SUBSEARCH

❖ Parameters

► *n* = 200, *K* = 2, *γ* = 0.3 (*m* = 60 outliers)

► Γ₁₁ = Γ₂,₂ = 0.65, Γ₁₂ = 0.35

❖ Baselines

► *inliers*: estimation using the subgraph of inlier nodes with true community labels

► *pruning*: remove *m* nodes with the highest and lowest degrees from from each community; then recluster the graph

<figure><img src="image_14.png" /></figure>
Experiments on a single run : Acharya's filtering

<figure><img src="image_15.png" /></figure>

❖ Our approach goes beyond an incremental extension of Acharya's filtering that

► fails to decrease the error due to the lack of exploration

► cannot distinguish between outliers and misclassified inliers $\leftrightarrow$ excessive removal of inliers
Multi-run experiments: influence of γ

<figure><img src="image_16.png" /></figure>
Multi-run experiments: dependence with *n*

<figure><img src="image_17.png" /></figure>
Jazz Collaboration dataset

$n = 198; |E| = 2742$

<figure><img src="image_18.png" /></figure>

* SUBSEARCH identifies outlier nodes to be ignored, allowing to find the three main collaboration groups (bands in New York, Chicago, and other cities): $c(S_{SubSearch}) = 14.94$

* pruning baseline does not detect nodes with moderate degree perturbating the estimation : $c(S_{pruning}) = 21.11$
## ❖ we provide

* certification bound for the estimation of a SBM corrupted with adversarial node perturbations

* an algorithm for fitting SBM to corrupted networks while identifying potential outliers

* "exploring" the space of subgraphs ⇒ to find high quality fits

## ❖ perspectives

* deal with the denominator of the certification bound

* investigate the cost function's theoretical properties

* Can we provide faster rates?
Thank you!

❖ L. Martins Bianco, C. Keribin, and Z. Naulet.
Subsearch: Robust estimation and outlier detection for stochastic
block models via subgraph search, AISTATS 2025.

<figure><img src="image_19.png" /></figure>

github.com/leobianco/robust_estim_sbm