# Large Deviations of Semi-supervised Learning in the Stochastic Block Model

Hugo Cui  Luca Saglietti  Lenka Zdeborová  SPOC laboratory,Physics Department,
École Polytechnique Fédérale de Lausanne.

###### Abstract

In community detection on graphs, the semi-supervised learning problem entails
inferring the ground-truth membership of each node in a graph, given the
connectivity structure and a limited number of revealed node labels. Different
subsets of revealed labels can in principle lead to higher or lower
information gains and induce different reconstruction accuracies. In the
framework of the dense stochastic block model, we employ statistical physics
methods to derive a large deviation analysis for this problem, in the high-
dimensional limit. This analysis allows the characterization of the
fluctuations around the typical behaviour, capturing the effect of correlated
label choices and yielding an estimate of their informativeness and their
rareness among subsets of the same size. We find theoretical evidence of a
non-monotonic relationship between reconstruction accuracy and the free energy
associated to the posterior measure of the inference problem. We further
discuss possible implications for active learning applications in community
detection.

##  I Introduction

Many problems in data science require learning from graph data, where
relational as well as local information might be available. Leveraging on the
graph structure is often sufficient for inferring a plausible partition of the
nodes into a finite number of communities [1, 2, 3], each characterized by
different internal and external connectivities. In some cases, the community
reconstruction accuracy can be further improved by accessing the labels (i.e.,
ground truth community assignments) of a selected subset of nodes. This semi-
supervised learning setting is especially relevant when the hidden labels are
expensive and time-consuming to obtain, which is often the case in real world
applications [4, 5, 6].

Inference processes on graphs are intrinsically based on a modeling assumption
for the graph generation process. The stochastic block model (SBM) can
arguably be seen as the canonical probabilistic model for graphs displaying a
community structure [2, 7, 8], able to capture the typical features of both
assortative and disassortative graphs. In an instance of an SBM, with $N$
nodes and $r$ communities, one assumes the existence of a planted community
assignment and that each edge in the graph is independently added with a
probability that is function solely of the hidden labels of the involved
nodes. Depending on the scaling of the edge probability with $N$, the SBM
framework can be employed for modeling both dense and sparse graphs. In this
work, we focus our analysis on the dense case, which simplifies the
statistical physics description, in the high dimensional limit $N\to\infty$,
by means of the replica method [9]. In this setting, the theoretically
interesting regime, leading to non-trivial inference, is one where the graph
connectivity only retains a weak $\mathcal{O}(1/\sqrt{N})$ dependence on group
membership [10].

The semi-supervised setting in the SBM was previously considered in [11, 12,
13]. A crucial assumption in these works, however, is that the fraction of
disclosed labels $\\{x_{i}\\}_{i\in\mathcal{S}}$, where $\mathcal{S}$ is a
revealed subset of cardinal $|\mathcal{S}|=nN$ and $0<n<1$, is chosen
uniformly at random among all nodes. While this assumption is the simplest one
from a theoretical point of view, in realistic settings the data collection
process is often far from random. In fact, a wide variety of techniques
ranging from centrality-based heuristics to more refined and expensive active
learning strategies [4, 5, 6], could be employed in order to select node
labels that are less redundant and carry more information than randomly
sampled ones.

In the present work, we depart from the typical (random) choice of the subset
and we study the large deviation properties of semi-supervised learning in the
SBM model. The theoretical goal is to characterize how correlations in the
choice of the labelled nodes can impact the associated inference performance.
In order to do this, we compare all possible revealed subsets of a given size
$n$ and organize them in a statistical mechanical ensemble, where the
associated free energy (i.e., log posterior measure) plays the role of an
effective energy function [14]. We can then obtain an estimate of the subset-
entropy, i.e., the exponential rate of the number of subsets that achieve a
given value of the free energy. This subset-entropy can be regarded as a
characterization of the rareness of atypical subsets. We then discuss the
relationship between free energy and reconstruction accuracy.

From the point of view of the replica method, studying the large deviations
entails a computation akin to a 1RSB in structure [15, 16]: the free entropy
of the model and the entropy of labelled subsets are linked by a Legendre
transform controlled by a temperature ($\beta$ in the following). In order to
simplify the calculations, we restrict our analysis to the Bayes-optimal
inference setting, where the parameters of the generative model are known and
matched in the inference model. In fact, in this setting the Nishimori
identities [17, 18] guarantee replica symmetry to hold at least for the
equilibrium solutions of the system. In the out-of-equilibrium settings
spanned by the large deviation, however, the Nishimori conditions can be
violated. We thus provide a stability analysis, checking for the appearance of
possible replica symmetry breaking phenomena [19, 20]. The calculations are
presented for a more general class of planted inference problems (containing
the SBM as a special case), namely symmetric low-rank matrix factorization
problems [21]. This more general framework can be useful for a direct
connection with different machine learning applications, ranging from PCA to
high-dimensional Gaussian mixture clustering [22].

The main results we obtain can be summarized as follows:

  * •

Using the replica method, we compute the entropy of ways to disclose a
fraction $n$ of nodes yielding a given value of the free energy. We provide
results for the case of a dense SBM with two balanced communities [21, 22].

  * •

We provide evidence of a non-monotonic dependence between the free energy and
the reconstruction accuracy for high values of SNR, which we found somewhat
unexpected.

  * •

We discuss the consequences for active community detection where one is free
to choose the subset of nodes for which labels will be revealed. In
particular, we unveil that maximizing the free energy is not always the best
criterion to select subsets leading to maximal reconstruction accuracy. We
illustrate this point by implementing Monte-Carlo selection strategies based
on the Thouless-Anderson-Palmer (TAP) [23] evaluation of the free energy and
discussing their performance.

The remainder of the paper is organized as follows: in section II, we formally
introduce the models analyzed in this work and define the large deviation
framework. In section III we outline the replica computation of the subset-
entropy, which is the main result of this paper. In section IV, we show the
predictions obtained from the large deviation analysis, describing the
interplay between subset-entropy, free-energy and inference performance. In
section V, we provide some derivation details and the results of the stability
analysis associated to the replica symmetric ansatz. Finally, in section VI,
we discuss possible implications of our results for active learning in
community detection, comparing our predictions with MCMC simulations in finite
size graphs.

##  II Setting

###  II.1 Community detection in the SBM

##### The inference problem

The stochastic block model on $N$ individuals and $r$ communities is a
commonly used generative probabilistic model for graphs displaying community
structure. In the SBM, each individual is first assigned independently at
random to a community $x_{i}\in\llbracket 1,r\rrbracket$ according to a prior
$P_{X}(\cdot)$. Between each pair of individual $(i,j)$, an edge is then
created with probability $P_{\mathrm{out}}(y_{ij}=1|x_{i},x_{j})$, where
$y_{ij}=\mathbbm{1}_{(ij)\in E}$ is the $i,j$ component of the adjacency
matrix of the resulting graph. In the community detection problem on the
obtained graph, the statistician aims at inferring back the community of each
individual $\bm{X}=(x_{i})_{1\leq i\leq N}$ from the sole knowledge of the
graph structure, or, equivalently, its adjacency matrix $\bm{Y}$.

##### SBM with two balanced communities

While the following derivation is detailed for generic SBM, we choose to
illustrate our results for a dense SBM with two balanced communities of
respective average sizes $N\rho$ and $N(1-\rho)$ and same average connectivity
[22, 21]. More precisely, the dense SBM with two balanced communities is
specified, for any $\rho,p\in(0,1),~{}\mu\geq 0$, by the prior

$\displaystyle P_{X}(\cdot)=\rho\delta(\cdot-x_{+})+(1-\rho)\delta(\cdot-
x_{-}),$ (1)

and the posterior

$\displaystyle
P_{\mathrm{out}}(y|x,x^{\prime})=\delta_{y,1}\left(p+\mu\frac{xx^{\prime}}{\sqrt{N}}\right)+\delta_{y,0}\left(1-p-\mu\frac{xx^{\prime}}{\sqrt{N}}\right),$
(2)

with the shorthands $x_{+}:=\sqrt{(1-\rho)/\rho},~{}x_{-}=-1/x_{+}$ labelling
the two communities. Therefore, two individuals pertaining to communities
$x\in\\{x_{+},x_{-}\\}$ and $x^{\prime}\in\\{x_{+},x_{-}\\}$ are connected
with probability $p+\mu xx^{\prime}/\sqrt{N}$, thereby defining a graph where
edges link connected individuals. Notice that, in order to obtain an inference
problem where the performance is neither as bad as random guessing nor perfect
the difference between inter and intra-community connectivities needs to be
small, of order $\mathcal{O}(1/\sqrt{N})$. The special case of an SBM with two
balanced communities makes for a non-trivial inference problem, as the prior
(1) and posterior (2) imply that nodes in both communities have the same
connectivity, and that therefore no information on the community can be easily
accessed based on the sole degree of a node.

For the standard SBM problem with two balanced communities, [22, 21] evidenced
the presence of a phase transition for some value of $\Delta=p(1-p)/\mu^{2}$
depending on $\rho$, above which no reconstruction is information-
theoretically possible. This transition is of first order if
$\rho\in(0,\frac{1}{2}-\frac{1}{\sqrt{12}})\cup(\frac{1}{2}+\frac{1}{\sqrt{12}},1)$,
and is of second order otherwise. In the semi-supervised setting where a non-
zero fraction of nodes $n>0$ is disclosed [13], instead, partial community
reconstruction is always achievable, the second order phase transition is
smeared out, and first order phase transition shrinks and disappears in the
tri-critical point as the number of revealed nodes increases.

##### Symmetric matrix factorization

An SBM can be recast more generally into a low rank symmetric matrix
factorization problem [22, 21]. In what follows, this formalism shall be
employed for the sake of generality, while results will be given and discussed
for the special case of the SBM. In the setting of symmetric matrix
factorization, the matrices $\bm{X}^{0}$ and $\bm{Y}$ are generated according
to the Markov chain $\bm{X}^{0}\rightarrow\bm{W}^{0}\rightarrow\bm{Y}$, with

$\displaystyle\bm{X}^{0}\in\mathbb{R}^{N\times r}\overset{d}{=}P_{X}(\cdot)$
(3) $\displaystyle\bm{W}^{0}\in\mathbb{R}^{N\times
N}=\frac{1}{\sqrt{N}}\bm{X}^{0}\bm{K}\bm{X}^{0T}$ (4)
$\displaystyle\bm{Y}\in\mathbb{R}^{N\times
N}\overset{d}{=}P_{\mathrm{out}}(\cdot|\bm{W}^{0}),$ (5)

where $\bm{K}\in\mathcal{S}_{\mathbb{R}}^{r\times r}$ is a given symmetric
matrix [21], and the thermodynamic limit $N\to\infty,r=\mathcal{O}(1)$ is
assumed. For the particular case of an SBM, the matrix $\bm{X}^{0}$ is the
horizontal stack of the indicator vectors $\bm{x}_{i}$ for each individual
$i$, with $(\bm{x}_{i})_{q}=1$ iff $i$ belongs to community $q$, and $0$
otherwise. The prior $P_{X}(\cdot)$ is assumed to be row-wise separable (which
corresponds to independently assigned communities in the SBM), i.e. to
factorize on the rows $\\{\bm{x}_{i}^{0}\\}_{i=1}^{N}$ of $\bm{X}^{0}$,

$P_{\bf X}(\bm{X}^{0})=\prod\limits_{i}^{N}P_{X}(\bm{x}^{0}_{i}).$ (6)

The posterior $P_{\mathrm{out}}(\cdot|\bm{W})$ is assumed to factorize on all
matrix components (note that, for simplicity, the same notation is kept)

$P_{\mathrm{out}}(\bm{Y}|\bm{W})=\prod\limits_{i,j}P_{\rm{out}}(Y_{ij}|W_{ij}).$
(7)

This assumption corresponds in the context of the SBM to edges being generated
independently. The inference problem is to estimate the ground truth value of
$\bm{X}$, $\bm{X}^{0}$ (up to a permutation of the columns), that was used to
generate $\bm{Y}$ with the sole knowledge of $\bm{Y}$ and of the parameter
$\bm{K}$. This can naturally be carried out using the Bayes rule, considering
the posterior measure $P(\bm{X}|\bm{Y})$. In the language of statistical
physics, this probability defines a Hamiltonian

$\mathcal{H}_{\bm{Y}}(\bm{X})=-\ln P_{\bf X}(\bm{X})-\ln P_{\rm
out}(\bm{Y}|\bm{W})+\ln P(\bm{Y})$ (8)

see [7, 22, 21]. The rows of $\bm{X}$ play the role of spin variables, while
$\bm{Y}$ acts as a quenched disorder. The Gibbs measure associated with
Hamiltonian (8) is

$\mu_{\bm{Y}}(\bm{X})=\frac{1}{Z_{\bm{Y}}}e^{-\mathcal{H}_{\bm{Y}}(\bm{X})},$
(9)

the normalization factor being called the partition function. The quenched
free energy associated is defined as

$\displaystyle f$ $\displaystyle=-\mathbb{E}_{\bm{X}^{0},\bm{Y}}\ln
Z_{\bm{Y}}$ $\displaystyle=-\mathbb{E}_{\bm{X}^{0},\bm{Y}}\ln\int
d\bm{X}e^{-\mathcal{H}_{\bm{Y}}(\bm{X})}.$ (10)

###  II.2 Large deviations of the free energy under partial disclosure of the
ground truth

We are interested in the deviations of the free energy (II.1) when certain
rows of the ground truth $\bm{X}^{0}$,
$\\{\bm{x}_{i}^{0}\\}_{i\in\mathcal{S}}$, are disclosed. We denote with
$\mathcal{S}$ a subset of $\llbracket 1,N\rrbracket$ of given cardinal
$|\mathcal{S}|=nN$. This is tantamount to replacing the prior (6) by

$P^{\mathcal{S}}_{\bf
X}(\bm{X})=\prod\limits_{i}^{N}\Big{(}\sigma_{i}\delta(\bm{x}_{i}-\bm{x}^{0}_{i})+(1-\sigma_{i})P_{X}(\bm{x}_{i})\Big{)},$
(11)

where $\sigma_{i}=\mathbbm{1}_{i\in\mathcal{S}}$ is the indicator function of
$i$ pertaining to the disclosed rows in $\mathcal{S}$. The goal of the present
work is to evaluate, given a certain cardinal $n=|\mathcal{S}|/N$ and a given
value of free energy $f$, the subset-entropy $\Sigma(n,f)$, i.e. the
logarithmic number of ways to select a subset $\mathcal{S}$ of intensive
cardinal $n$ so that the free energy is equal to $f$. While obtaining directly
this quantity is not straightforward, a viable method for its evaluation is by
means of a Legendre transform [14, 16]. First, we evaluate the grand canonical
free entropy

$\displaystyle\Phi(\beta,\phi)$
$\displaystyle=\mathbb{E}_{\bm{X}^{0},\bm{Y}}\ln\sum\limits_{\\{\sigma_{i}\\}_{i=1}^{N}}\Bigg{[}\int
d\bm{X}P^{\mathcal{S}}_{X}(\bm{X})\frac{P_{\mathrm{out}}(\bm{Y}|\bm{W})}{P_{\mathrm{out}}(\bm{Y}|\bm{0})}\Bigg{]}^{\beta}e^{\phi\sum\limits_{i}^{N}\sigma_{i}}.$
(12)

In (II.2) $\beta$ plays the role of a (possibly negative) inverse temperature,
and $\phi$ is a chemical potential controlling the cardinal of the subset. As
mentioned before, the components of $\bm{Y}$ act as quenched disorder, while
selection variables $\sigma$ act as annealed disorder, whose fluctuation
timescale differs from the annealed spins $\bm{x}_{i}$ by a factor controlled
by $\beta$. In high dimensions, the free-entropy $\Phi$ is expected to
concentrate:

$\Phi(\beta,\phi)=\underset{n,f}{\rm{extr}}~{}\Sigma(n,f)-\beta f+\phi n,$
(13)

where $f,n$ are the dominant values of free-energy and cardinality at the
given $\beta$ and $\phi$. Inverting the Legendre transform yields the sought
subset-entropy function, as

$\Sigma(n,f)=\underset{\beta,\phi}{\rm{extr}}~{}\Phi(\beta,\phi)+\beta f-\phi
n.$ (14)

##  III Replica computation

###  III.1 Replica trick

The free entropy (II.2) can be computed using the replica method [15, 24, 20].
Calling $\Xi$ the argument of the logarithm in (II.2), a simple mathematical
identity allows one to rewrite the expression as:

$\mathbb{E}_{\bm{X}^{0},\bm{Y}}\ln\Xi=\underset{s\rightarrow
0}{\rm{lim}}\frac{1}{s}\ln\mathbb{E}_{\bm{X}^{0},\bm{Y}}\Xi^{s}.$ (15)

Assuming an integer value of $\beta$, the free entropy (II.2) can then be
fully rewritten in terms of replicas of the original system:

$\displaystyle\Phi(\beta,\phi)$ $\displaystyle=\underset{s\rightarrow
0}{\mathrm{lim}}\frac{1}{s}\int\prod\limits_{i=1}^{N}d\bm{x}^{0}_{i}P_{X}(\bm{x}^{0}_{i})\prod\limits_{i\leq
j}dY_{ij}P_{\mathrm{out}}(Y_{ij}|0)e^{g(Y_{ij}|W^{0}_{ij})-g(Y_{ij}|0)}$
$\displaystyle\sum\limits_{\\{\sigma_{i}^{a}\\}}\int\prod\limits_{a=1}^{s}\prod\limits_{\alpha=1}^{\beta}\prod\limits_{i=1}^{N}d\bm{x}_{i}^{a\alpha}((1-\sigma_{i}^{a})P_{X}(\bm{x}_{i}^{a\alpha})+\sigma_{i}^{a}\delta(\bm{x}_{i}^{a\alpha}-\bm{x}^{0}_{i}))\prod\limits_{i\leq
j}e^{\sum\limits_{a\alpha}g(Y_{ij}|W_{ij}^{a\alpha})-g(Y_{ij}|0)}e^{\phi\sum\limits_{a,i}\sigma_{i}^{a}}.$
(16)

Following [22, 21], we have adopted the notation

$g(\bm{Y}|\bm{W})\overset{\rm{def}}{=}\ln P_{\rm{out}}(\bm{Y}|\bm{W}),$ (17)

with $g$ thereby corresponding to the spin-spin interaction part of the
Hamiltonian (8). Note the presence of two levels of replications: the first
replica index $a$ runs over $\llbracket 1,s\rrbracket$ and corresponds to the
replication introduced by the trick (15). The second replication index
$\alpha$ is on the other hand induced by the $\beta$ power in (II.2). Note
that, at the end of the computation we will restore the initial continuous
temperature via an analytical continuation to any value $\beta\in\mathbb{R}$.
For the sake of compactness, we index the ground truth spins
$\\{\bm{x}_{i}^{0}\\}_{i=1}^{N}$ with the replica index $a=0$ (and set
accordingly $\sigma_{i}^{0}=0$ for all $i$ for coherence). We also denote the
effective prior
$((1-\sigma_{i}^{a})P_{X}(\bm{x}_{i}^{a\alpha})+\sigma_{i}^{a}\delta(\bm{x}_{i}^{a\alpha}-\bm{x}^{0}_{i}))$
as $P^{\sigma^{a}_{i}}_{X}(\bm{x}_{i}^{a\alpha})$, with $\mathcal{S}_{a}$ the
$a^{\rm{th}}$ replica of subset $\mathcal{S}$.

###  III.2 Channel universality

Expanding the interaction term up to $\mathcal{O}\left(\frac{1}{N}\right)$ we
get:

$\displaystyle
e^{\sum\limits_{a\alpha}g(Y_{ij}|W_{ij}^{a\alpha})-g(Y_{ij}|0)}$
$\displaystyle=1+\partial_{W}g(Y_{ij}|0)\sum\limits_{a\alpha}W_{ij}^{a\alpha}+\frac{1}{2}\partial_{W}^{2}g(Y_{ij}|0)\sum\limits_{a\alpha}(W_{ij}^{a\alpha})^{2}$
$\displaystyle+\frac{1}{2}(\partial_{W}g(Y_{ij}|0))^{2}\sum\limits_{a\alpha,c\gamma}W_{ij}^{a\alpha}W_{ij}^{c\gamma}+o\Bigg{(}\frac{1}{N}\Bigg{)}.$
(18)

It can be further shown [22, 21] that

$\displaystyle\int P_{\mathrm{out}}(y)dy\partial_{W}g(Y_{ij}|0)=0$ (19)
$\displaystyle\int
P_{\mathrm{out}}(y)dy(\partial^{2}_{W}g(Y_{ij}|0)+\partial_{W}g(Y_{ij}|0)^{2})=0.$
(20)

Moreover, defining the effective noise also known as Fisher score $\Delta$ as

$\displaystyle\frac{1}{\Delta}=\mathbb{E}_{P(.|0)}((\partial_{W}g(Y_{ij}|0))^{2}),$
(21)

the replica free entropy (III.1) can be cast into the form

$\displaystyle\Phi(\beta,\phi)=$
$\displaystyle\sum\limits_{\\{S_{i}^{a}\\}}\int\prod\limits_{a\alpha}\prod\limits_{i=1}^{N}d\bm{x}_{i}^{a\alpha}P^{\sigma^{a}_{i}}_{X}(\bm{x}_{i}^{a\alpha})$
$\displaystyle
e^{\frac{1}{2\Delta}\sum\limits_{i,j}\sum\limits_{a\alpha<c\gamma}W_{ij}^{a\alpha}W_{ij}^{c\gamma}}e^{\phi\sum\limits_{a,i}\sigma_{i}^{a}}.$
(22)

Note that all dependence with respect to the output measure $P_{\rm{out}}$ has
been subsumed into the effective noise $\Delta$. In previous work, this
property has been referred to as channel universality [22, 21, 10], and allows
connections between apparently disparate inference problems.

###  III.3 Casting as a saddle-point problem

It is possible to rewrite the computation of $\Phi(\beta,\phi)$ as a saddle-
point problem. To that end, define the overlap tensor

$\displaystyle\bm{R}_{a\alpha,c\gamma}=\frac{1}{N}\sum\limits_{i=1}^{N}\bm{x}_{i}^{a\alpha}(\bm{x}_{i}^{c\gamma})^{T}\in(\mathbb{R}^{r\times
r})^{(s\times\beta)\times(s\times\beta)}.$ (23)

$\bm{R}$ is a $(s\times\beta)\times(s\times\beta)$ block matrix with blocks in
$\mathbb{R}^{r\times r}$. Arguably, the overlap matrix is mathematically ill
defined outside of the replica trick setup, as $s\rightarrow 0$ and $\beta$ is
a (potentially negative) real number. A notable property of $\bm{R}$ following
from its definition (23) is its symmetry up to transposition with respect to
its first two indices,

$\displaystyle\bm{R}_{a\alpha,c\gamma}=(\bm{R}_{c\gamma,a\alpha})^{T}.$ (24)

This property allows one to compactly rewrite the interaction Hamiltonian as

$\displaystyle\sum\limits_{i,j}\sum\limits_{a\alpha<c\gamma}W_{ij}^{a\alpha}W_{ij}^{c\gamma}=N\sum\limits_{a\alpha<c\gamma}\mathrm{tr}(\bm{R}_{a\alpha,c\gamma}\bm{K}\bm{R}_{c\gamma,a\alpha}\bm{K}).$
(25)

The final step in order to rewrite (III.2) as an extremization problem is to
introduce the Fourier representation of a Dirac’s delta function, enforcing
definition (23):

$\displaystyle 1=$ $\displaystyle\int\prod\limits_{a\alpha\leq
c\gamma}d\bm{R}_{a\alpha,c\gamma}d\bm{\hat{\bm{R}}}_{a\alpha,c\gamma}$
$\displaystyle e^{-N\sum\limits_{a\alpha\leq
c\gamma}\mathrm{tr}\left(\hat{\bm{R}}_{a\alpha,c\gamma}(\bm{R}_{a\alpha,c\gamma}-\frac{1}{N}\sum\limits_{i=1}^{N}\bm{x}_{i}^{a\alpha}\bm{x}_{i}^{c\gamma
T})^{T}\right)}.$ (26)

We have absorbed the imaginary factor $i$ into the definition of the Fourier
conjugate $\hat{\bm{R}}$ and omitted some subdominant terms induced by the
normalization of the Dirac Fourier transform in the exponential. Then (III.2)
can be compactly rewritten as

$\displaystyle\Phi(\beta,\phi)=\int\prod\limits_{a\alpha\leq
c\gamma}d\bm{R}_{a\alpha,c\gamma}d\bm{\hat{\bm{R}}}_{a\alpha,c\gamma}e^{N\ln
I(\bm{\hat{\bm{R}}})+NT(\bm{R},\hat{Q)}}$

with

$\displaystyle I(\bm{\hat{\bm{R}}})$
$\displaystyle=\sum\limits_{\sigma^{a}}\int\prod\limits_{a\alpha}d\bm{x}^{a\alpha}P^{\sigma^{a}}_{X}(\bm{x}^{a\alpha})e^{\sum\limits_{a\alpha\leq
c\gamma}\mathrm{tr}\left(\hat{\bm{R}}_{a\alpha,c\gamma}\bm{x}^{c\gamma}\bm{x}^{a\alpha
T}\right)}e^{\phi\sum\limits_{a}\sigma^{a}}$ (27)

and

$\displaystyle T(\bm{R},\hat{\bm{R}})$
$\displaystyle=\frac{1}{2\Delta}\sum\limits_{a\alpha<c\gamma}\mathrm{tr}(\bm{R}_{a\alpha,c\gamma}\bm{K}\bm{R}_{c\gamma,a\alpha}\bm{K})$
$\displaystyle-\sum\limits_{a\alpha\leq
c\gamma}\mathrm{tr}(\hat{\bm{R}}_{a\alpha,c\gamma}\bm{R}_{a\alpha,c\gamma}^{T}).$
(28)

Equation (III.3) suggests to employ a saddle-point type approximation to
compute the free entropy $\Phi(\beta,\phi)$ as

$\displaystyle\Phi(\beta,\phi)=\underset{\bm{R},\bm{\hat{\bm{R}}}}{\mathrm{extr}}\left[T(\bm{R},\hat{\bm{R}})+\ln
I(\bm{\hat{\bm{R}}})\right],$ (29)

with the extremization carried out over the matrix $\bm{R}$ and its Dirac
conjugate $\hat{\bm{R}}$.

###  III.4 RS ansatz

As written in (29), the extremization must be carried out in
$((\mathbb{R}^{r\times r})^{(s\times\beta)\times(s\times\beta)})^{2}$ and is
nor mathematically well-defined nor tractable. Progress can be made [20, 15,
24] by making an assumption on the form of the overlap matrices extremizing
(III.3). We here assume the simplest, and most common ansatz, the Replica
Symmetric (RS) ansatz. The RS ansatz in our case is readily amenable to
physical interpretation. Assuming replica symmetry in the large deviations
setting amounts to assuming that any two variables seeing the same disorder
$\\{\sigma_{i}^{a}\\}_{i=1}^{N}$ (i.e. same $a$ index) have the same $r\times
r$ overlap, while two seeing different disorders (viz. different $a$ index)
possess a distinct and unique overlap:

$\displaystyle\bm{R}^{0,0}=\bm{r}^{0},$
$\displaystyle\bm{\hat{\bm{R}}}^{0,0}=\bm{\hat{r}}^{0}$ (30)
$\displaystyle\bm{R}^{a\alpha,a\alpha}=\bm{r},$
$\displaystyle\bm{\hat{\bm{R}}}^{a\alpha,a\alpha}=\bm{\hat{r}}$ (31)
$\displaystyle\bm{R}^{0,a\alpha}=\bm{m},$
$\displaystyle\bm{\hat{\bm{R}}}^{0,a\alpha}=\bm{\hat{m}}$ (32)
$\displaystyle\bm{R}^{a\alpha,a\gamma}=\bm{Q},$
$\displaystyle\bm{\hat{\bm{R}}}^{a\alpha,a\gamma}=\bm{\hat{Q}}$ (33)
$\displaystyle\bm{R}^{a\alpha,c\gamma}=\bm{q},$
$\displaystyle\bm{\hat{\bm{R}}}^{a\alpha,c\gamma}=\bm{\hat{q}}$ (34)

This ansatz can be simplified by setting the gradient with respect to
components of $\bm{R}$ to $0$ in (III.3)
$\partial_{\bm{R}_{a\alpha,c\gamma}^{\mu\nu}}\Phi{=}0$. Since all dependence
on $\bm{R}$ in $\Phi(\beta,\phi)$ is contained in $T(\bm{R},\hat{\bm{R}})$,
this saddle point condition implies

$\partial_{\bm{R}_{a\alpha,c\gamma}^{\mu\nu}}T(\bm{R},\hat{\bm{R}})=\mathbbm{1}_{a\alpha\neq
c\gamma}\frac{1}{\Delta}(\bm{K}\bm{R}_{a\alpha,c\gamma}\bm{K})^{\mu\nu}-\hat{\bm{R}}_{a\alpha,c\gamma}^{\mu\nu}{=}0.$
(35)

So the components of the conjugate tensor $\hat{\bm{R}}$ are actually related
to those of the overlap tensor $\bm{R}$ by

$\displaystyle\hat{\bm{r}}^{0}=\hat{\bm{r}}=0,$ (36)
$\displaystyle\hat{\bm{m}}=\frac{1}{\Delta}\bm{K}\bm{m}\bm{K},$ (37)
$\displaystyle\hat{\bm{Q}}=\frac{1}{\Delta}\bm{K}\bm{Q}\bm{K},$ (38)
$\displaystyle\hat{\bm{q}}=\frac{1}{\Delta}\bm{K}\bm{q}\bm{K}.$ (39)

Note that, in Bayes-optimal inference, replica symmetry is usually guaranteed
to hold by the Nishimori identities [18]. However, these identities only apply
to the equilibrium solutions of the system, obtained at $\beta=0$ in our
framework. Therefore this simplifying RS ansatz needs to be validated through
a stability analysis (presented in section V).

###  III.5 Replica free entropy

The term $T(\bm{R},\hat{\bm{R}})$ can be evaluated explicitly using the RS
ansatz (30)-(34) and using the relations (36)

$\displaystyle T(\bm{R},\hat{\bm{R}})=$
$\displaystyle-s\frac{\beta}{2\Delta}\mathrm{tr}(\bm{m}\bm{K}\bm{m}^{T}\bm{K})-s\frac{\beta(\beta-1)}{4\Delta}\mathrm{tr}(\bm{Q}\bm{K}\bm{Q}^{T}\bm{K})$
$\displaystyle-\frac{\beta^{2}}{2\Delta}\frac{s(s-1)}{2}\mathrm{tr}(\bm{q}\bm{K}\bm{q}^{T}\bm{K})$
(40)

We can expand the exponent in $I(\bm{\hat{\bm{R}}})$ as follows:

$\displaystyle e^{\sum\limits_{a\alpha\leq
c\gamma}\mathrm{tr}\left(\hat{\bm{R}}_{a\alpha,c\gamma}\bm{x}^{c\gamma}\bm{x}^{a\alpha
T}\right)}$
$\displaystyle=\mathbb{E}^{\mathcal{N}(0,1)}_{\bm{\xi}}\prod\limits_{a}\mathbb{E}^{\mathcal{N}(0,1)}_{\bm{\lambda}_{a}}e^{(\bm{x}^{0})^{T}\bm{\hat{m}}\sum\limits_{a\alpha\neq
0}\bm{x^{a\alpha}}-\frac{1}{2}\sum\limits_{a\alpha\neq
0}(\bm{x^{a\alpha}})^{T}\bm{\hat{Q}}\bm{x^{a\alpha}}}$ $\displaystyle\times
e^{+\sum\limits_{a\neq
0}\lambda_{a}(\hat{\bm{Q}}-\hat{\bm{q}})^{\frac{1}{2}}\sum\limits_{\alpha}\bm{x^{a\alpha}}+\bm{\xi}^{T}\bm{\hat{q}}^{\frac{1}{2}}\sum\limits_{a\alpha\neq
0}x^{a\alpha}}.$ (41)

We introduced two Hubbard-Stratonovitch fields $\bm{\xi}$ and
$\\{\bm{\lambda_{a}}\\}_{a=1}^{s}$ to linearise the exponent.

$\displaystyle
I(\bm{\hat{\bm{R}}})=\sum\limits_{\sigma^{a}}\mathbb{E}^{\mathcal{N}(0,1)}_{\bm{\xi}}\prod\limits_{a}\mathbb{E}^{\mathcal{N}(0,1)}_{\bm{\lambda}_{a}}\prod\limits_{a\alpha}d\bm{x}^{a\alpha}P_{X}^{\sigma_{a}}(\bm{x}^{a\alpha})$
$\displaystyle\times e^{(\bm{x}^{0})^{T}\bm{\hat{m}}\sum\limits_{a\alpha\neq
0}\bm{x^{a\alpha}}-\frac{1}{2}\sum\limits_{a\alpha\neq
0}(\bm{x^{a\alpha}})^{T}\bm{\hat{Q}}\bm{x^{a\alpha}}}$ $\displaystyle\times
e^{+\sum\limits_{a\neq
0}\lambda_{a}(\hat{\bm{Q}}-\hat{\bm{q}})^{\frac{1}{2}}\sum\limits_{\alpha}\bm{x^{a\alpha}}+\bm{\xi}^{T}\bm{\hat{q}}^{\frac{1}{2}}\sum\limits_{a\alpha\neq
0}x^{a\alpha}}$
$\displaystyle=\mathbb{E}^{\mathcal{N}(0,1)}_{\bm{\xi}}\mathbb{E}^{P_{X}}_{\bm{\bm{x}^{0}}}$
$\displaystyle\Bigg{[}\sum\limits_{\sigma=0,1}e^{\phi\sigma}\mathbb{E}^{\mathcal{N}(0,1)}_{\bm{\lambda}}\Bigg{\\{}\int
d\bm{x}((1-\sigma)P_{X}(\bm{x})+\sigma\delta(\bm{x}-\bm{x}^{0}))$
$\displaystyle
e^{-\frac{1}{2}\bm{x}^{T}\hat{\bm{Q}}\bm{x}+((\bm{x}^{0})^{T}\bm{\hat{m}}+\bm{\lambda}^{T}(\bm{\hat{Q}}-\bm{\hat{q}})^{\frac{1}{2}}+\bm{\xi}^{T}\bm{\hat{q}}^{\frac{1}{2}})\bm{x}}\Bigg{\\}}^{\beta}\Bigg{]}^{s}.$
(42)

This allows to explicitly write the free entropy (III.1) as an extremization
problem on $\mathbb{R}^{r\times r}$. Using the shorthand

$\displaystyle
h(\bm{x})\overset{\rm{def}}{=}-\frac{1}{2}\bm{x}^{T}\hat{\bm{Q}}\bm{x}+((\bm{x}^{0})^{T}\bm{\hat{m}}+\bm{\lambda}^{T}(\bm{\hat{Q}}-\bm{\hat{q}})^{\frac{1}{2}}+\bm{\xi}^{T}\bm{\hat{q}}^{\frac{1}{2}})\bm{x},$
(43)

the free entropy is given by

$\displaystyle\Phi(\beta,\phi)$
$\displaystyle=\underset{\bm{m},\bm{Q},\bm{q}}{\mathrm{extr}}~{}~{}-\frac{\beta}{2\Delta}\mathrm{tr}(\bm{m}\bm{K}\bm{m}^{T}\bm{K})$
$\displaystyle-\frac{\beta(\beta-1)}{4\Delta}\mathrm{tr}(\bm{Q}\bm{K}\bm{Q}^{T}\bm{K})+\frac{\beta^{2}}{4\Delta}\mathrm{tr}(\bm{q}\bm{K}\bm{q}^{T}\bm{K})$
$\displaystyle+\mathbb{E}^{\mathcal{N}(0,1)}_{\bm{\xi}}\mathbb{E}^{P_{X}}_{\bm{\bm{x}^{0}}}\ln\Bigg{[}\mathbb{E}^{\mathcal{N}(0,1)}_{\bm{\lambda}}e^{\phi}e^{\beta
h(\bm{x}^{0})}$
$\displaystyle+\mathbb{E}^{\mathcal{N}(0,1)}_{\bm{\lambda}}\Bigg{\\{}\int
d\bm{x}\frac{P_{X}(\bm{x})}{P_{X}(\bm{x}^{0})}e^{h(\bm{x})}\Bigg{\\}}^{\beta}\Bigg{]}.$
(44)

####  III.5.1 Saddle point equations

The extremization in (III.5) can be carried out by explicitly writing the
zero-gradient conditions on each of the order parameters
$\bm{m},\bm{Q},\bm{q}$ and iterating them until convergence. The zero-gradient
condition are in the general case hard to compute, since they involve matrix
derivatives. Though we believe that progress can be made in some particular
cases where the matrix structure of the order parameters is known (for example
if the prior is invariant over the permutation group $\mathfrak{S}(\llbracket
1,r\rrbracket)$ ), we restrict ourselves in this manuscript to the scalar
$r=1$ case and leave the generic matrix gradient derivation to future work.
For $r=1$, the saddle-point equations read:

$\displaystyle
h(x)-\frac{Qx^{2}}{2\Delta}+\frac{x}{\Delta^{\frac{1}{2}}}\left(\frac{x^{0}m}{\Delta^{\frac{1}{2}}}+\lambda(Q-q)^{\frac{1}{2}}+\xi
q^{\frac{1}{2}}\right)$ (45) $\displaystyle Z_{x}=\int dxP_{X}(x)e^{h(x)}$
(46) $\displaystyle f_{x}=\frac{1}{Z_{x}}\int dxxP_{X}(x)e^{h(x)}$ (47)
$\displaystyle
m=\mathbb{E}^{\mathcal{N}(0,1)}_{\xi}\mathbb{E}^{P_{X}}_{x^{0}}\frac{\mathbb{E}^{\mathcal{N}(0,1)}_{\lambda}\Big{[}e^{\phi}(x^{0})^{2}e^{\beta
h(x^{0})}+Z_{x}^{\beta}f_{x}x^{0}\Big{]}}{\mathbb{E}^{\mathcal{N}(0,1)}_{\lambda}\Big{[}e^{\phi}e^{\beta
h(x^{0})}+Z_{x}^{\beta}\Big{]}}$ (48) $\displaystyle
Q=\mathbb{E}^{\mathcal{N}(0,1)}_{\xi}\mathbb{E}^{P_{X}}_{x^{0}}\frac{\mathbb{E}^{\mathcal{N}(0,1)}_{\lambda}\Big{[}e^{\phi}(x^{0})^{2}e^{\beta
h(x^{0})}+Z_{x}^{\beta}f_{x}^{2}\Big{]}}{\mathbb{E}^{\mathcal{N}(0,1)}_{\lambda}\Big{[}e^{\phi}e^{\beta
h(x^{0})}+Z_{x}^{\beta}\Big{]}}$ (49) $\displaystyle
q=\mathbb{E}^{\mathcal{N}(0,1)}_{\xi}\mathbb{E}^{P_{X}}_{x^{0}}\Bigg{(}\frac{\mathbb{E}^{\mathcal{N}(0,1)}_{\lambda}\Big{[}e^{\phi}x^{0}e^{\beta
h(x^{0})}+Z_{x}^{\beta}f_{x}\Big{]}}{\mathbb{E}^{\mathcal{N}(0,1)}_{\lambda}\Big{[}e^{\phi}e^{\beta
h(x^{0})}+Z_{x}^{\beta}\Big{]}}\Bigg{)}^{2}$ (50)

##### Saddle point equations for the SBM with two balanced communities

We give the specialization of the saddle-point equations (45)-(50) for the SBM
with two balanced communities defined by (1) and (2). The effective noise
$\Delta$ in this case is [22, 21]

$\displaystyle\Delta=\frac{p(1-p)}{\mu^{2}}.$ (51)

Since the SBM with two balanced communities is a particular case of $r=1$
factorization, all order parameters are scalars. Define the quantities

$\displaystyle Z_{x}=\rho e^{h_{+}}+(1-\rho)e^{h_{-}}$ (52) $\displaystyle
f_{x}=\frac{1}{Z_{x}}(\rho x_{+}e^{h_{+}}+(1-\rho)x_{-}e^{h_{-}})$ (53)
$\displaystyle
h_{+}=-\frac{1}{2\Delta}Qx_{+}^{2}+\Big{(}\frac{mx^{0}}{\Delta}+\frac{\lambda\sqrt{Q-q}}{\sqrt{\Delta}}+\frac{\xi\sqrt{q}}{\sqrt{\Delta}}\Big{)}x_{+}$
(54) $\displaystyle
h_{-}=-\frac{1}{2\Delta}Qx_{-}^{2}+\Big{(}\frac{mx^{0}}{\Delta}+\frac{\lambda\sqrt{Q-q}}{\sqrt{\Delta}}+\frac{\xi\sqrt{q}}{\sqrt{\Delta}}\Big{)}x_{-}$
(55) $\displaystyle\beta
h_{0}=-\frac{\beta}{2\Delta}Q(x^{0})^{2}+\beta\Big{(}\frac{mx^{0}}{\Delta}+\frac{\xi\sqrt{q}}{\sqrt{\Delta}}\Big{)}x^{0}+\frac{Q-q}{2\Delta}\beta^{2}(x^{0})^{2}$
(56)

For readability, we dropped in the notations of $Z_{x},f_{x},h_{\pm},h_{0}$
the dependence on the order parameters $q,Q,m$, $x^{0}$ and the Hubbard-
Stratonovitch fields $\xi,\lambda$. Using these shorthands, the updates read

$\displaystyle
m=\mathbb{E}^{\mathcal{N}(0,1)}_{\xi}\mathbb{E}^{P_{X}}_{x^{0}}\frac{e^{\phi+\beta
h_{0}}(x^{0})^{2}+\mathbb{E}^{\mathcal{N}(0,1)}_{\lambda}Z_{x}^{\beta}f_{x}x^{0}}{e^{\phi+\beta
h_{0}}+\mathbb{E}^{\mathcal{N}(0,1)}_{\lambda}Z_{x}^{\beta}},$ (57)
$\displaystyle
Q=\mathbb{E}^{\mathcal{N}(0,1)}_{\xi}\mathbb{E}^{P_{X}}_{x^{0}}\frac{e^{\phi+\beta
h_{0}}(x^{0})^{2}+\mathbb{E}^{\mathcal{N}(0,1)}_{\lambda}Z_{x}^{\beta}f_{x}^{2}}{e^{\phi+\beta
h_{0}}+\mathbb{E}^{\mathcal{N}(0,1)}_{\lambda}Z_{x}^{\beta}},$ (58)
$\displaystyle
q=\mathbb{E}^{\mathcal{N}(0,1)}_{\xi}\mathbb{E}^{P_{X}}_{x^{0}}\Bigg{(}\frac{e^{\phi+\beta
h_{0}}x^{0}+\mathbb{E}^{\mathcal{N}(0,1)}_{\lambda}Z_{x}^{\beta}f_{x}}{e^{\phi+\beta
h_{0}}+\mathbb{E}^{\mathcal{N}(0,1)}_{\lambda}Z_{x}^{\beta}}\Bigg{)}^{2}.$
(59)

Figure 1: Subset-entropy $\Sigma(n,f)$ (upper) and typical magnetization
$m(n,f)$ (lower) for small effective noise $\Delta=0.5$ (top plot) and
critical effective noise $\Delta=1$ (bottom plot), and disclosed fractions
$n\in\\{0.1,~{}0.3,~{}0.5\\}$. Solid lines correspond to asymptotic
predictions in the large $N$ limit as given by the large deviations. Dashed
lines correspond to simulations averaged over $20$ instances of SBM with
$N=50$ nodes, by repeatedly drawing for each instance subsets of intensive
size $n$ at random $10^{7}$ times and evaluating $f,m$ for each draw using the
TAP [23, 10] algorithm.

##  IV Results

In this section we display the results of the presented large deviation
analysis. In section III, starting from a high-dimensional problem, we derived
an analytical expression for the free-entropy that only depends on a small
$\mathcal{O}(1)$ set of overlap parameters. The saddle-point values of these
parameters, obtained by extremizing the free-entropy, can now be used to
predict relevant metrics of the inference performance in large SBM instances.

In particular, through a Legendre transform, we can look at the free-
energy/subset-entropy curves, spanning among all possible choices for the
subset of revealed nodes at fixed cardinality $n$. The subset-entropy is
linked to the rareness of the correlated subset selections, and can be
interpreted as a measure of the probability of randomly sampling a subset with
given $n,f$ [16]. The maxima of the curves represent the typical choice of
revealed nodes, and the associated value of the log-posterior in the semi-
supervised inference problem. In high dimensions, all fluctuations around the
typical free energy are exponentially suppressed and thus extremely unlikely
in large instances. In Fig. 1, upper panels, we show the analytic curves,
compared with the numerical results in dimension $N=50$ (the small size allows
rare events to be observed in reasonable simulation time, with $10^{7}$
samples). Note that negative values of the subset-entropy are completely
unphysical, and signal a problem in the assumptions made in the replica
computation. We look further into this problem in section V.

Since the free-energy is not immediately interpretable as a performance
measure in the SBM setting, we need a different way of characterizing the
difficulty of the semi-supervised learning problem associated to a given set
of labelled nodes. A natural measure of the helpfulness of disclosing a set
$\mathcal{S}$ is the mean reconstruction error, i.e. the overlap of the
inferred rows of $\bm{X}$ with those of the ground truth $\bm{X}^{0}$, with
respect to the Bayes posterior measure $P(\bm{X}|\bm{Y})$,

$\mathrm{tr}\,\bm{m}=\frac{1}{N}\sum\limits_{i=1}^{N}\mathbb{E}_{\bm{x}}^{P(\bm{X}|\bm{Y})}\left[\bm{x}_{i}^{T}\bm{x}_{i}^{0}\right].$
(60)

Note that for rank one problems, $\mathrm{tr}\,\bm{m}$ just reduces to $m$.
Smart choices for $\mathcal{S}$ lead to easier inference problems and
therefore, on average, to better inference of the planted community assignment
(signalled by a larger mean overlap).

In the lower panels in Fig. 1, we show the reconstruction overlap obtained in
correspondence of different revealed subsets, and the corresponding numerical
simulations at $N=50$. A first observation is that very rare node selections
can lead to much higher information gains, which justifies the implementation
of algorithmic strategies for their identification. Surprisingly, we also find
that the relationship between the free-energy associated to the posterior
measure of the inference problem and $m$ is not always monotonous, depending
on the value of the SNR. In particular, at high SNR (small noise $\Delta=0.5$)
the overlap with the signal increases with the free energy for all fraction of
disclosed nodes $n$. However, when the SNR approaches the critical value
($\Delta=1$), the subset selections with the highest possible free energy are
no longer associated with a better reconstruction. Note that this non-
monotonous dependence is not an artifact of the RS replica analysis, as it is
observed even for ranges of $n$ where the RS fixed point (III.5) is stable,
see section V, and in the finite size experiments presented in section VI.
This finding highlights the non-trivial role played by the noise in the
problem of inferring the correct membership of the nodes (cfr. with the
noiseless setting in [16]).

##  V Stability of the RS assumption

The RS ansatz (30)-(34) is expected to hold when the configurations dominating
the large deviation measure (II.2) do not deviate too much from the typical
ones. For other regions in the $\beta,\phi$ plane however, the matrices
extremizing (III.3) may develop more involved structure, and further steps of
Replica Symmetry Breaking [19, 20] might be needed. In this section, the
stability of the assumption under an infinitesimal 1RSB perturbation (30)-(34)
is investigated.

For any fixed disorder $\\{\sigma_{i}\\}_{i=1}^{N}$, the inference problem
associated to the $\beta$ replicas evolving in this disorder is Bayes optimal
[10] and therefore RS is expected to hold at that level of replication, i.e.
$\alpha$ indices are RS. It may, however, be the case that clusters form in
the $\sigma$ space, yielding a 1RSB-type landscape for the first replication
level (index $a$). The $a$ index must then be differentiated into a double
$(a^{\prime}\in\llbracket 1,\frac{s}{\tau}\rrbracket,a\in\llbracket
1,\tau\rrbracket)$ index. The parameter $\tau$ is called in this context the
Parisi parameter. In the following, $a^{\prime}$ labels the 1RSB cluster of
the disorder configuration $\mathcal{S}^{a^{\prime},a}$, while the $a$ index
differentiates disorder configurations within a same 1RSB cluster.

###  V.1 1RSB perturbation to the RS ansatz

We consider a perturbation to the ansatz (30)-(34) of a 1RSB form:

$\displaystyle\bm{R}^{0,0,0}=\bm{r}^{0},$
$\displaystyle\bm{\hat{\bm{R}}}^{0,0,0}=\bm{\hat{r}}^{0}$ (61)
$\displaystyle\bm{R}^{a^{\prime}a\alpha,a^{\prime}a\alpha}=\bm{r},$
$\displaystyle\bm{\hat{\bm{R}}}^{a^{\prime}a\alpha,a^{\prime}a\alpha}=\bm{\hat{r}}$
(62) $\displaystyle\bm{R}^{0,a^{\prime}a\alpha}=\bm{m},$
$\displaystyle\bm{\hat{\bm{R}}}^{0,a^{\prime}a\alpha}=\bm{\hat{m}}$ (63)
$\displaystyle\bm{R}^{a^{\prime}a\alpha,a^{\prime}a\gamma}=\bm{Q},$
$\displaystyle\bm{\hat{\bm{R}}}^{a^{\prime}a\alpha,a^{\prime}a\gamma}=\bm{\hat{Q}}$
(64)
$\displaystyle\bm{R}^{a^{\prime}a\alpha,a^{\prime}c\gamma}=\bm{q}+\bm{\epsilon},$
$\displaystyle\bm{\hat{\bm{R}}}^{a^{\prime}a\alpha,a^{\prime}a\gamma}=\bm{\hat{q}}+\hat{\bm{\epsilon}}$
(65) $\displaystyle\bm{R}^{a^{\prime}a\alpha,c^{\prime}c\gamma}=\bm{q},$
$\displaystyle\bm{\hat{\bm{R}}}^{a\alpha,c\gamma}=\bm{\hat{q}}$ (66)

$\bm{\epsilon}$ is a small perturbation. All components of the matrix
$\bm{\epsilon}$ are expected to be positive and assumed $o(1)$, since spins
pertaining to the same RSB cluster should have greater overlap than spins
coming from distinct clusters. Note that relations (36) still hold, with the
addition of a similar equation for $\bm{\epsilon}$

$\hat{\bm{\epsilon}}=\frac{1}{\Delta}\bm{K}\bm{\epsilon}\bm{K}.$ (67)

The RS assumption of section III is not valid if a perturbation of the form
(61)-(66) does cause the fixed-point defined by (45)-(50) to become unstable.

###  V.2 1RSB free entropy

The computation follows the same lines of the one presented above in III.5. At
the end, one gets for the trace term $T(\bm{R},\hat{\bm{R}})$

$\displaystyle T(\bm{R},$ $\displaystyle\hat{\bm{R}})$
$\displaystyle=-s\frac{\beta}{2\Delta}\mathrm{tr}(\bm{m}\bm{K}\bm{m}^{T}\bm{K})-s\frac{\beta(\beta-1)}{4\Delta}\mathrm{tr}(\bm{Q}\bm{K}\bm{Q}^{T}\bm{K})$
$\displaystyle-s\frac{\beta^{2}(\tau-1)}{4\Delta}\mathrm{tr}((\bm{q}+\bm{\epsilon})\bm{K}(\bm{q}+\bm{\epsilon})^{T}\bm{K})$
$\displaystyle-\frac{(\beta\tau)^{2}(\frac{s}{\tau}(\frac{s}{\tau}-1))}{4\Delta}\mathrm{tr}(\bm{q}\bm{K}\bm{q}^{T}\bm{K}),$
(68)

while the channel term $I(\hat{\bm{R}})$ reads

$\displaystyle e^{\sum\limits_{a^{\prime}a\alpha\leq
c^{\prime}c\gamma}\mathrm{tr}\left(\hat{\bm{R}}_{a^{\prime}a\alpha,c^{\prime}c\gamma}\bm{x}^{c^{\prime}c\gamma}\bm{x}^{a^{\prime}a\alpha
T}\right)}$
$\displaystyle=\mathbb{E}^{\mathcal{N}(0,1)}_{\bm{\xi}}\prod\limits_{a^{\prime}=1}\mathbb{E}^{\mathcal{N}(0,1)}_{\bm{\lambda}_{a^{\prime}}}\prod\limits_{a^{\prime}a}\mathbb{E}^{\mathcal{N}(0,1)}_{\bm{\eta}_{a^{\prime}a}}e^{(\bm{x}^{0})^{T}\bm{\hat{m}}\sum\limits_{a^{\prime}a\alpha\neq
0}\bm{x^{a^{\prime}a\alpha}}}$ $\displaystyle\times
e^{-\frac{1}{2}\sum\limits_{a^{\prime}a\alpha\neq
0}(\bm{x^{a^{\prime}a\alpha}})^{T}\bm{\hat{Q}}\bm{x^{a^{\prime}a\alpha}}+\sum\limits_{a^{\prime}a}\bm{\eta}_{a^{\prime}a}^{T}(\hat{\bm{Q}}-\hat{\bm{q}}-\hat{\bm{\epsilon}})^{\frac{1}{2}}\sum\limits_{\alpha}\bm{x}^{a^{\prime}a\alpha}}$
$\displaystyle\times
e^{+\sum\limits_{a^{\prime}}\bm{\lambda}^{T}_{a^{\prime}}\hat{\bm{\epsilon}}^{\frac{1}{2}}\sum\limits_{a\alpha}\bm{x^{a^{\prime}a\alpha}}+\bm{\xi}^{T}\bm{\hat{q}}^{\frac{1}{2}}\sum\limits_{a\alpha\neq
0}x^{a\alpha}}.$ (69)

Here, $\bm{\xi}$,
$\\{\bm{\lambda_{a^{\prime}}}\\}_{a^{\prime}=1}^{\frac{s}{\tau}}$ and
$\\{\bm{\eta_{a^{\prime}a}}\\}_{a^{\prime},a\in\llbracket
1,\frac{s}{\tau}\rrbracket\times\llbracket 1,\tau\rrbracket}$ are again
Hubbard Stratonovitch fields following a normal distribution. Rearranging the
terms, we get

$\displaystyle I(\hat{\bm{R}})=$
$\displaystyle\frac{s}{\tau}\mathbb{E}^{\mathcal{N}(0,1)}_{\bm{\xi}}\mathbb{E}^{P_{X}}_{\bm{x}^{0}}\ln\Bigg{\\{}\mathbb{E}^{\mathcal{N}(0,1)}_{\bm{\lambda}}\Bigg{[}\mathbb{E}^{\mathcal{N}(0,1)}_{\bm{\eta}}e^{\beta
h(\bm{x}^{0})}$
$\displaystyle+\mathbb{E}^{\mathcal{N}(0,1)}_{\bm{\eta}}\Big{(}\int
d\bm{x}P_{X}(\bm{x})e^{h(\bm{x})}\Big{)}^{\beta}\Bigg{]}^{\tau}\Bigg{\\}}$
(70)

with

$\displaystyle h(\bm{x})\overset{\rm{def}}{=}$
$\displaystyle-\frac{1}{2\Delta}\bm{x}^{T}\bm{Q}\bm{x}+\frac{1}{\Delta^{\frac{1}{2}}}\Big{(}\frac{1}{\Delta^{\frac{1}{2}}}\bm{x}^{0T}\bm{m}+\bm{\eta}^{T}(\bm{Q}-\bm{q}-\bm{\epsilon})^{\frac{1}{2}}$
$\displaystyle+\bm{\lambda}^{T}\bm{\epsilon}^{\frac{1}{2}}+\bm{\xi}^{T}\bm{q}^{\frac{1}{2}}\Big{)}\bm{x}.$
(71)

The 1RSB free entropy then reads

$\displaystyle\Phi(\beta,\phi)^{1\rm{RSB}}=-\frac{\beta}{2\Delta}\mathrm{tr}(\bm{m}\bm{K}\bm{m}^{T}\bm{K})-\frac{\beta(\beta-1)}{4\Delta}\mathrm{tr}(\bm{Q}\bm{K}\bm{Q}^{T}\bm{K})-\frac{\beta^{2}(\tau-1)}{4\Delta}\mathrm{tr}((\bm{q}+\bm{\epsilon})\bm{K}(\bm{q}+\bm{\epsilon})^{T}\bm{K})+\frac{\beta^{2}\tau}{4\Delta}\mathrm{tr}(\bm{q}\bm{K}\bm{q}^{T}\bm{K})$
$\displaystyle+\frac{1}{\tau}\mathbb{E}^{\mathcal{N}(0,1)}_{\bm{\xi}}\mathbb{E}^{P_{X}}_{\bm{x}^{0}}\ln\Bigg{\\{}\mathbb{E}^{\mathcal{N}(0,1)}_{\bm{\lambda}}\Bigg{[}\mathbb{E}^{\mathcal{N}(0,1)}_{\bm{\eta}}e^{\beta
h(\bm{x}^{0})}+\mathbb{E}^{\mathcal{N}(0,1)}_{\bm{\eta}}\Big{(}\int
d\bm{x}P_{X}(\bm{x})e^{h(\bm{x})}\Big{)}^{\beta}\Bigg{]}^{\tau}\Bigg{\\}}.$
(72)

###  V.3 Stability analysis

Figure 2: Subset-entropy curves for an SBM (1)(2) with $\Delta=1$, see also
Fig. 1. Regions where the RS fixed point (30)-(34) is stable (as evaluated
using the stability condition (78)) are represented in solid lines; unstable
regions are dashed.

The 1RSB free entropy (V.2) can be expanded in orders of
$\bm{\epsilon}^{\frac{1}{2}}$,

$\displaystyle\Phi(\beta,\phi)^{1\rm{RSB}}=$
$\displaystyle\Phi^{(0)}(\beta,\phi)+\mathrm{tr}(\bm{\epsilon}^{\frac{1}{2}}\Phi^{(\frac{1}{2})}(\beta,\phi))+\mathrm{tr}(\bm{\epsilon}\Phi^{(1)}(\beta,\phi))+o(\bm{\epsilon}),$
(73)

with the zeroth order term corresponding to the RS free entropy introduced in
equation (III.5). The computation of order $\bm{\epsilon}^{\frac{1}{2}}$ terms
and above requires the computation of matrix derivative and is in general hard
to evaluate without further assumption on the structure of $\bm{\epsilon}$. We
now restrict ourselves to the special case analyzed in this work, namely to
rank $r=1$ where all order parameters are scalars.

In the rank 1 case, introducing the shorthand

$\displaystyle\mathcal{Z}(z)\overset{\rm{def}}{=}e^{\phi-\frac{\beta}{2\Delta}Q(x^{0})^{2}+\beta
z\times x^{0}}+\left(\int dxP_{X}(x)e^{-\frac{1}{2\Delta}Qx^{2}+z\times
x}\right)^{\beta},$ (74)

with

$\displaystyle
z\overset{\rm{def}}{=}\frac{1}{\Delta^{\frac{1}{2}}}\left(\frac{1}{\Delta^{\frac{1}{2}}}x^{0}m+\eta(Q-q)^{\frac{1}{2}}+\xi
q^{\frac{1}{2}}\right),$ (75)

the expansion can be carried out up to order $\epsilon$. It can be shown that
$\Phi^{(\frac{1}{2})}(\beta,\phi)=0$ while

$\displaystyle\Phi^{(1)}(\beta,\phi)$
$\displaystyle=\frac{\tau-1}{\Delta}\left[-\beta^{2}q+\mathbb{E}^{\mathcal{N}(0,1)}_{\bm{\xi}}\mathbb{E}^{P_{X}}_{\bm{x}^{0}}\left(\frac{\mathbb{E}^{\mathcal{N}(0,1)}_{\eta}\mathcal{Z}^{\prime}(z)}{\mathbb{E}^{\mathcal{N}(0,1)}_{\eta}\mathcal{Z}(z)}\right)^{2}\right].$
(76)

This $o(\epsilon)$ correction yields another term in the saddle point
condition $\partial_{q}\Phi^{\mathrm{1RSB}}\overset{!}{=}0$. The zeroth order
part of this condition is identical to the RS saddle-point for $q$, and is
automatically satisfied, while requiring the $\mathcal{O}(\epsilon)$ part of
the gradient to be vanishing implies

$\displaystyle\epsilon=\frac{1}{\beta^{2}}\mathbb{E}^{\mathcal{N}(0,1)}_{\bm{\xi}}\mathbb{E}^{P_{X}}_{\bm{x}^{0}}\partial_{q}\left(\frac{\mathbb{E}^{\mathcal{N}(0,1)}_{\eta}\mathcal{Z}^{\prime}(z)}{\mathbb{E}^{\mathcal{N}(0,1)}_{\eta}\mathcal{Z}(z)}\right)^{2}\epsilon.$
(77)

If the term multiplying $\epsilon$ in the RHS has absolute value greater than
$1$, iterating the saddle point equation causes the perturbation to grow,
signalling a lack of stability of the RS fixed point. Expanding the derivative
the stability condition yields

$\frac{1}{\Delta\beta^{2}}\Bigg{|}\mathbb{E}^{\mathcal{N}(0,1)}_{\bm{\xi}}\mathbb{E}^{P_{X}}_{\bm{x}^{0}}\left(\frac{\mathbb{E}^{\mathcal{N}(0,1)}_{\eta}\mathcal{Z}^{\prime\prime}(z)}{\mathbb{E}^{\mathcal{N}(0,1)}_{\eta}\mathcal{Z}(z)}\right)^{2}-4\mathbb{E}^{\mathcal{N}(0,1)}_{\bm{\xi}}\mathbb{E}^{P_{X}}_{\bm{x}^{0}}\frac{(\mathbb{E}^{\mathcal{N}(0,1)}_{\eta}\mathcal{Z}^{\prime}(z))^{2}\mathbb{E}^{\mathcal{N}(0,1)}_{\eta}\mathcal{Z}^{\prime\prime}(z)}{(\mathbb{E}^{\mathcal{N}(0,1)}_{\eta}\mathcal{Z}(z))^{3}}+3\mathbb{E}^{\mathcal{N}(0,1)}_{\bm{\xi}}\mathbb{E}^{P_{X}}_{\bm{x}^{0}}\left(\frac{\mathbb{E}^{\mathcal{N}(0,1)}_{\eta}\mathcal{Z}^{\prime}(z)}{\mathbb{E}^{\mathcal{N}(0,1)}_{\eta}\mathcal{Z}(z)}\right)^{4}\Bigg{|}<1.$
(78)

##### Stability condition for the SBM with two balanced communities

We specialize the stability condition (78) to the two-balanced communities SBM
setup defined by (2) and (1). We employ the notation (52)-(56), with the
addition of

$V_{x}=\frac{1}{Z_{x}}(\rho
x_{+}^{2}e^{h_{+}}+(1-\rho)x_{-}^{2}e^{h_{-}})-f_{x}^{2},$ (79)

which can be seen as the variance of the measure $P_{X}(\cdot)e^{h(\cdot)}$,
as would naturally appear in an Approximate Message Passing setting for
example [22, 21, 10, 25]. We give here the expressions of
$\mathbb{E}^{\mathcal{N}(0,1)}_{\eta}\mathcal{Z},\mathbb{E}^{\mathcal{N}(0,1)}_{\eta}\mathcal{Z}^{\prime},\mathbb{E}^{\mathcal{N}(0,1)}_{\eta}\mathcal{Z}^{\prime\prime}$
that are involved in (78):

$\displaystyle\mathbb{E}^{\mathcal{N}(0,1)}_{\eta}\mathcal{Z}=e^{\phi+\beta
h_{0}}+\mathbb{E}^{\mathcal{N}(0,1)}_{\lambda}Z_{x}^{\beta},$ (80)
$\displaystyle\mathbb{E}^{\mathcal{N}(0,1)}_{\eta}\mathcal{Z}^{\prime}=\beta
x^{0}e^{\phi+\beta
h_{0}}+\beta\mathbb{E}^{\mathcal{N}(0,1)}_{\lambda}Z_{x}^{\beta}f_{x},$ (81)

and

$\displaystyle\mathbb{E}^{\mathcal{N}(0,1)}_{\eta}\mathcal{Z}^{\prime\prime}=$
$\displaystyle\beta^{2}(x^{0})^{2}e^{\phi+\beta h_{0}}$
$\displaystyle+\beta\mathbb{E}^{\mathcal{N}(0,1)}_{\lambda}\Big{(}(\beta-1)Z_{x}^{\beta}f_{x}^{2}+Z_{x}^{\beta}(V_{x}+f_{x}^{2})\Big{)}.$
(82)

These expression can be readily plugged back into (78) to yield the stability
condition for the SBM with two balanced communities.

##### Results

The evaluation of the stability condition (78) for the particular setting of
the SBM with two balanced communities is shown in Fig. 2. As expected, the
assumed replica symmetry is validated in proximity of the maximum of the
curves, corresponding to the typical case (with maximal subset-entropy)
obtained with uniform random sampling of the labelled nodes. On the other
hand, the results of the large deviation computation are not found to be exact
when the described events become very rare and the correlations grow too much.
Note that the curves become unstable before reaching negative values of the
subset-entropy, as expected. While a complete analysis of the fixed point of
the RSB free energy (V.2) (beyond infinitesimal perturbations from the RS
fixed point) would be needed in this case, it is numerically more involved and
we leave it for future work. Note, however, that RSB corrections are typically
small in magnitude [19] and the numerical simulations seem to be in good
agreement with the obtained theoretical predictions, despite the instability
of the ansatz.

Algorithm 1 MCf, MCm

Input: budget $n$, adjacency matrix $Y$, ground truth labels $\bm{X}^{0}$,
criterion$=m$ (MCm) or $f$ (MCf) evaluated using TAP, convergence criterion
$\epsilon$, max number of iteration $M$.

Initialize $\mathcal{S}$ randomly by subsampling $nN$ nodes uniformly at
random.

Initialize number of iterations $t=0$, difference $\delta=0$

while $\delta>\epsilon$ and $t<M$ do

$t=t+1$

sample $i\in\mathcal{S}$ at random and $j\in\llbracket
1,N\rrbracket\smallsetminus\mathcal{S}$ at random

name $\mathcal{S}^{\prime}=\mathcal{S}\smallsetminus\\{i\\}\cup\\{j\\}$

compute criterion($\mathcal{S}$’) using TAP (Algorithm 2)

if criterion($\mathcal{S}^{\prime}$)$>$criterion($\mathcal{S}$) then

$\mathcal{S}\leftarrow\mathcal{S}^{\prime}$

end if

end while

Algorithm 2 semi-supervised TAP

Input: disclosed subset $\mathcal{S}$, adjacency matrix $Y$ convergence
criterion $\epsilon$, max number of iteration $M$.

Initialize $\forall i,\hat{\bm{x}}_{i}^{t=0}\in\mathbb{R}^{r}\leftarrow
10^{-3}\mathcal{N}(0,\mathbbm{1}_{r})$

Initialize $\forall i,\bm{V}_{i}^{t=0}\in\mathbb{R}^{r}\leftarrow 0$

Initialize $\bm{U}^{t=0}\in\mathbb{R}^{r\times r}\leftarrow 0$

Initialize $\forall i,\bm{\sigma}_{i}^{t=0}\in\mathbb{R}^{r\times r}\leftarrow
0$

while
$\frac{1}{N}\sum\limits_{i}||\hat{\bm{x}}^{t}_{i}-\hat{\bm{x}}^{t-1}_{i}||>\epsilon$
and $t<M$ do

$\bm{\sigma}_{i}^{t+1}=\partial_{\bm{V}}f_{i}(\bm{U}^{t},\bm{V}_{i}^{t})$

$\hat{\bm{x}}_{i}^{t+1}=f_{i}(\bm{U}^{t},\bm{V}_{i}^{t})$

$\bm{U}^{t+1}=\frac{1}{N\Delta}\sum\limits_{k}(\bm{K}\hat{\bm{x}}_{k}^{t+1})(\bm{K}\hat{\bm{x}}_{k}^{t+1})^{T}$

$\bm{V}_{i}^{t+1}=\frac{1}{\sqrt{N}}\sum\limits_{k}S_{ik}\bm{K}\hat{\bm{x}}_{k}^{t+1}-\frac{1}{N\Delta}\sum\limits_{k}\bm{K}\bm{\sigma}_{k}^{t+1}\bm{K}\hat{\bm{x}}_{i}^{t}$

where

$f_{i}(\bm{U},\bm{V}_{i})=\frac{\int
d\bm{x}P^{\mathcal{S}}_{X|i}(\bm{x})\bm{x}e^{-\frac{1}{2}\bm{x}^{T}\bm{U}\bm{x}+\bm{x}^{T}\bm{V}_{i}}}{\int
d\bm{x}P^{\mathcal{S}}_{X|i}(\bm{x})e^{-\frac{1}{2}\bm{x}^{T}\bm{U}\bm{x}+\bm{x}^{T}\bm{V}_{i}}}$

$P^{\mathcal{S}}_{X|i}(\bm{x})=(\mathbbm{1}_{i\notin\mathcal{S}}P_{X}(\bm{x})+\mathbbm{1}_{i\in\mathcal{S}}\delta(\bm{x}-\bm{x}^{0}_{i}))$

$S_{ij}=\partial_{w}g(Y_{ij}|w)|_{w=0}$

end while

return

The free energy  $\displaystyle f$
$\displaystyle=-\sum\limits_{i}\mathrm{ln}\int
d\bm{x}P^{\mathcal{S}}_{X|i}(\bm{x})e^{-\frac{1}{2}\bm{x}^{T}\bm{U}\bm{x}+\bm{x}^{T}\bm{V}_{i}}$
$\displaystyle+\frac{1}{2N}\Bigg{[}\frac{1}{\sqrt{N}}\sum\limits_{i,k}S_{ik}\hat{\bm{x}}_{i}^{T}\hat{\bm{x}}_{k}-2\mathrm{tr}\left(\bm{U}\sum\limits_{k}\bm{\sigma}_{k}\right)$
$\displaystyle-\frac{1}{2\Delta
N}\sum\limits_{i,k}\mathrm{tr}\left(\bm{K}\hat{\bm{x}}_{i}\hat{\bm{x}}_{i}^{T}\bm{K}\hat{\bm{x}}_{k}\hat{\bm{x}}_{k}^{T}\right)\Bigg{]}$
(83)

The magnetization
$m=\frac{1}{N}\sum\limits_{i=1}^{N}\bm{x}_{i}^{0}\hat{\bm{x}}_{i}^{T}$

##  VI Consequences for active learning

Figure 3: SBM with two balanced communities (2)(1) with $N=10^{3}$ nodes and
low SNR ($\Delta=1.3$) (Upper) magnetizations $m$ achieved by the MCm and MCf
algorithms, benchmarked against random subset selection, for various budgets
$n$. All points are averaged over $40$ SBM instances. Maximizing $m$ and $f$
cease to be equivalent below $n^{\star}\approx 0.6$. For $n\lessapprox 0.3$
maximizing the free energy $f$ leads to sub-random performances in terms of
magnetization, signalling the onset of the relationship between $f$ and $m$
becoming non-monotonous, see Figs. 1 and 5 (Lower) free energies $f$ achieved
by the MCm and MCf algorithms (Algorithm 1), benchmarked against random subset
selection, and the highest achievable free energy predicted by the large
deviation (II.2) (light blue) $\mathrm{inf}\\{f|\Sigma(n,f)>0\\}$, see also
Fig. 1. MCf consistently returns the theoretical highest free energy.

Figure 4: SBM with two balanced communities (2)(1) with $N=10^{3}$ nodes and
high SNR ($\Delta=0.5$) (Upper) magnetizations $m$ achieved by the MCm and MCf
algorithms, benchmarked against random subset selection, for various budgets
$n$. All points are averaged over $40$ SBM instances. Maximizing $m$ and $f$
cease to be equivalent below $n^{\star}\approx 0.3$. (Lower) free energies $f$
achieved by the MCm and MCf algorithms (Algorithm 1), benchmarked against
random subset selection, and the highest achievable free energy predicted by
the large deviation (II.2) (light blue) $\mathrm{inf}\\{f|\Sigma(n,f)>0\\}$,
see also Fig. 1. MCf consistently returns the theoretical highest free energy.

It has been shown in [16] for perceptron learning that computing the maximal
free energy from large deviations could provide a valuable benchmark for
assessing the effectiveness and the limitations of active learning strategies.
We discuss in this section how much this relationship carries over (or
differs) in the case of active community detection in the SBM. In the active
community inference problem, the statistician is allowed to choose for which
subset of nodes (of size corresponding to a fraction $n$) the true communities
are revealed, and leverage on this additional knowledge to better infer the
ground truth community assignment. The goal is therefore to find an
algorithmic strategy for determining a set $\mathcal{S}$ with cardinal
$|S|=nN$ of individuals, from which the maximal amount of information can be
extracted once their true communities is revealed.

A first remark is that it would of course seem more natural to look directly
at the large deviation properties for the reconstruction error (60). Carrying
a large-deviation analysis (II.2) for $\mathrm{tr}\bm{m}$ is, however, a
challenging and still open problem. In [16], the free energy (II.1) associated
to an inference problem was proposed in the context of perceptron learning as
a possible proxy for the magnetization, with the advantage of having a
computable large deviation. It is therefore tempting to adopt the free energy,
$f$, as a measure of informativeness for the disclosed subset $\mathcal{S}$.
However, as evidenced in Fig. 1 and discussed in IV, for sufficiently noisy
problems (sufficiently large $\Delta$) and low budgets $n$, the free energy
ceases to be a monotonously increasing function of the magnetization $m$. As a
consequence, finding the subset $\mathcal{S}$ leading to largest free energy
is not always tantamount to finding the subset leading to maximal
magnetization.

In Fig. 3 and 4, the subsets leading to maximal $f$ (resp. $m$) were
numerically searched on an instance of a SBM community detection problem using
greedy Monte Carlo schemes, MCf (resp. MCm), see Algorithm 1. For each value
of the budget $n$, these schemes were initialized on a random subset of size
$nN$. At each iteration, a replacement of a selected node by an unselected
node was proposed: the resulting change in $f$ (or $m$) was evaluated by
estimating the posterior marginals using the Thouless-Anderson-Palmer (TAP)
message-passing inference algorithm [23, 22, 21] (Algorithm 2), and accepted
if leading to an increase of the objective. Though there exists a priori no
guarantee that TAP correctly computes the posterior marginals when some nodes
are disclosed, we found that the marginals returned by TAP stood in very good
agreement with those estimated using a standard (but slower) Monte-Carlo
sampling, see Fig. 6. The performance of the Monte Carlo schemes MCf and MCm
were contrasted with the one of random subset selection, and benchmarked
against the maximal attainable $f$ as extracted from the theoretical entropy
curve $\Sigma(n,f)$, in Fig. 1. The MCf maximization scheme consistently
returns for each budget $n$ the theoretical highest achievable free energy
predicted by our large deviation analysis,
$f_{\mathrm{max}}^{n}=\mathrm{argmax}\\{f|\Sigma(n,f)>0\\}$ (Fig. 1), see the
agreement of the dark blue and light blue curves in Figs. 4, 3. For the
considered values of $\Delta=0.5,~{}1.3$, there exists a budget $n^{\star}$
below which a gap between MCm and MCf appears: in particular, MCf does not
achieve the maximal magnetization, i.e. maximizing the free energy $f$ ceases
to be equivalent to maximizing the magnetization. Therefore, if an active
learning algorithm was capable of indirectly maximizing $f$, the obtained
performance would be sub-optimal. Moreover, note that the MCf algorithm
analyzed in this section exploits direct knowledge of all the ground-truth
labels, and cannot be applied in a realistic active learning setting. The
value of the budget $n^{\star}$ below which this discrepancy becomes
observable decreases for lower $\Delta$ (less noisy settings). The critical
values for the budgets, extrapolated from the large deviation, are shown in
Fig. 5. Note that, for the most noise settings, for instance $\Delta=1.3$ in
Fig. 3, selecting the subset $\mathcal{S}$ with largest $f$ even yields sub-
random performance in terms of magnetization for small budgets, signalling
that in this range of $n$ the magnetization and the free energy cease to
covary. By using a straightforward generalization of Algorithms 1,2, we
checked that an analogous phenomenon can also be traced in sparse SBMs [7]
when the noise level (controlled by the difference between the inter and intra
community connectivities) approaches the associated critical value.

Figure 5: Critical value of the budget $n$ at which non-monotonous
relationship between free-energy and reconstruction overlap can be observed,
as a function of the noise level $\Delta$.  Figure 6: Scatter plot of the
local magnetization for each node $x_{i}$ of a SBM (1)(2) on $N=50$ nodes as
estimated per TAP, versus its estimation using a standard Metropolis-Hastings
Monte Carlo sampling ($10^{7}$ iterations, and a $50$ steps are given to let
the system thermalize between every two sampled configurations). A selection
$\mathcal{S}$ corresponding to a large deviation of the free energy (Fig. 1)
$f\approx-0.0112$ is disclosed. Despite the correlations introduced by the
latter, the marginals given by TAP are consistent with the ones obtained with
Monte Carlo.

##  VII Conclusions

In this work, we considered the semi-supervised learning setting in the dense
SBM. Through a statistical physics analysis based on the replica method, we
derived an analytic description of the large deviation properties of the model
under the different possible choices of the subsets of labelled nodes. The
results of our computation show that there exists rare subsets with higher
(lower) information content with respect to typical samples, and allowed for a
characterization of the relationship between information content and rareness.
Moreover, we found that lower SNR levels in the inference problem can lead to
a non-monotonous relationship between the volume of the log-posterior measure
and the reconstruction accuracy associated to different subset selections. In
order to validate our theoretical predictions, we identified the regions of
stability for the replica symmetric ansatz (assumed in the calculations) and
we displayed different comparisons of our analytic results with numerical
simulations in finite graph instances. Finally, we discussed the connection of
the presented large deviation analysis with the active learning problem in
community reconstruction. We thus identified the region of parameters where
our analysis can yield a good approximation for the optimal performance
achievable with any active selection algorithm.

Possible future research directions involve looking at the algorithmic
implications of our analysis, especially in the case of sparse networks.
Moreover, the non-trivial finding of the impact of the SNR in selection
processes could be further explored in different settings (e.g., supervised
learning problems [16]) where active learning strategies are commonly
employed.

###### Acknowledgements.

We acknowledge funding from the ERC under the European Union’s Horizon 2020
Research and Innovation Program Grant Agreement 714608-SMiLe.

## References

  * Kumaran and Chitrakala [2016] P. Kumaran and S. Chitrakala, Community formation based influence node selection for information diffusion in online social network, 2016 International Conference on Computing Technologies and Intelligent Data Engineering (ICCTIDE’16) , 1 (2016).
  * Abbe [2017] E. Abbe, Community detection and stochastic block models: recent developments, J. Mach. Learn. Res. 18, 177:1 (2017).
  * Traud  _et al._ [2011] A. L. Traud, P. Mucha, and M. Porter, Social structure of facebook networks, ArXiv abs/1102.2166 (2011).
  * Ping  _et al._ [2018] S. Ping, D. Liu, B. Yang, Y. Zhu, H. Chen, and Z. Wang, Batch mode active learning for node classification in assortative and disassortative networks, IEEE Access 6, 4750 (2018).
  * Liu  _et al._ [2020] J. Liu, Y. Wang, B. Hooi, R. Yang, and X. Xiao, Active learning for node classification: The additional learning ability from unlabelled nodes, ArXiv abs/2012.07065 (2020).
  * Gadde  _et al._ [2016] A. Gadde, E. E. Gad, A. S. Avestimehr, and A. Ortega, Active learning for community detection in stochastic block models, 2016 IEEE International Symposium on Information Theory (ISIT) , 1889 (2016).
  * Decelle  _et al._ [2011] A. Decelle, F. Krzakala, C. Moore, and L. Zdeborová, Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications, Physical review. E, Statistical, nonlinear, and soft matter physics 84 6 Pt 2, 066106 (2011).
  * Yan  _et al._ [2014] X. Yan, J. E. Jensen, F. Krzakala, C. Moore, C. Shalizi, L. Zdeborová, P. Zhang, and Y. Zhu, Model selection for degree-corrected block models, Journal of statistical mechanics 2014 5 (2014).
  * Mézard and Montanari [2002] M. Mézard and A. Montanari,  _Information,Physics and computation_ (Oxford University Press, 2002).
  * Zdeborová and Krzakala [2016] L. Zdeborová and F. Krzakala, Statistical physics of inference : thresholds and algorithms, Adv. Phys. 5, 453 (2016).
  * Eaton and Mansbach [2012] E. Eaton and R. A. Mansbach, A spin-glass model for semi-supervised community detection, in  _AAAI_ (2012).
  * Ver Steeg  _et al._ [2014] G. Ver Steeg, C. Moore, A. Galstyan, and A. Allahverdyan, Phase transitions in community detection: A solvable toy model, EPL (Europhysics Letters) 106, 48004 (2014).
  * Zhang  _et al._ [2014] P. Zhang, C. Moore, and L. Zdeborová, Phase transitions in semisupervised clustering of sparse networks, Physical review. E, Statistical, nonlinear, and soft matter physics 90 5-1, 052802 (2014).
  * Obuchi  _et al._ [2018] T. Obuchi, Y. Nakanishi-Ohno, M. Okada, and Y. Kabashima, Statistical mechanical analysis of sparse linear regression as a variable selection problem, Journal of Statistical Mechanics: Theory and Experiment 2018, 103401 (2018).
  * Parisi [1979] G. Parisi, Towards a mean field theory for spin glasses, Phys. Lett 73, 203 (1979).
  * Cui  _et al._ [2020] H. Cui, L. Saglietti, and L. Zdeborová, Large deviations for the perceptron model and consequences for active learning, ArXiv abs/1912.03927 (2020).
  * Nishimori [1980] H. Nishimori, Exact results and critical properties of the ising model with competing interactions, Journal of Physics C: Solid State Physics 13, 4071 (1980).
  * Nishimori [2001] H. Nishimori,  _Statistical physics of spin glasses and information processing_ (Oxford Science Publications, 2001).
  * Mézard  _et al._ [1984] M. Mézard, G. Parisi, N. Sourlas, G. Toulouse, and M. A. Virasoro, Replica symmetry breaking and the nature of the spin glass phase, J. Phys. France 45, 843 (1984).
  * Mézard  _et al._ [1986] M. Mézard, M. A. Virasoro, and G. Parisi,  _Spin Glass Theory and Beyond_ (World scientific Lecture Notes in Physics, 1986).
  * Lesieur  _et al._ [2015] T. Lesieur, F. Krzakala, and L. Zdeborová, Mmse of probabilistic low-rank matrix estimation: Universality with respect to the output channel, 53rd Annual Allerton Conference on Communication, Control, and Computing , 680 (2015).
  * Lesieur  _et al._ [2017] T. Lesieur, F. Krzakala, and L. Zdeborová, Constrained low-rank matrix estimation : phase transitions, approximate message passing and applications, Journal of Statistical Mechanics: Theory and Experiments , 073403 (2017).
  * Thouless  _et al._ [1977] D. J. Thouless, P. W. Anderson, and R. G. Palmer, Solution of solvable model of spin glass, Phil. Mag. 35, 593 (1977).
  * Parisi [1983] G. Parisi, Order parameter for spin glasses, Phys. Rev. Lett 50, 1946 (1983).
  * Krzakala  _et al._ [2012] F. Krzakala, M. Mézard, F. Sausset, S. Yifan, and L. Zdeborová, Probabilistic reconstruction in compressed sensing : Algorithms, phase diagrams and treshold achieving matrices, J. Stat. Mech. 2012, P08009 (2012).
  * Braverman  _et al._ [2021] V. Braverman, S. H.-C. Jiang, R. Krauthgamer, and X. Wu, Coresets for clustering in excluded-minor graphs and beyond, in  _Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)_ (SIAM, 2021) pp. 2679–2696.
  * Kushnir and Mirabelli [2020] D. Kushnir and B. Mirabelli, Active community detection with maximal expected model change, in  _AISTATS_ (2020).
  * Mézard and Montanari [2009] M. Mézard and A. Montanari, Information, physics, and computation (2009).
  * Mézard  _et al._ [1987] M. Mézard, G. Parisi, M. Virasoro, and D. Thouless, Spin glass theory and beyond (1987).
  * Rangan [2011] S. Rangan, Generalized approximate message passing for estimation with random linear mixing, in  _2011 IEEE International Symposium on Information Theory Proceedings_ (IEEE, 2011) pp. 2168–2172.
  * Wang  _et al._ [2016] X. Wang, B. Yang, and J. Huang, Survey of active learning for networked data (2016).
  * Allahverdyan and Galstyan [2009] A. Allahverdyan and A. Galstyan, Community detection with and without prior information, ArXiv abs/0907.4803 (2009).
  * Cheng  _et al._ [2014] J. Cheng, M. Leng, L. Li, H. Zhou, and X. Chen, Active semi-supervised community detection based on must-link and cannot-link constraints, PLoS ONE 9 (2014).
  * Fortunato [2009] S. Fortunato, Community detection in graphs, ArXiv abs/0906.0612 (2009).
  * Holland  _et al._ [1983] P. Holland, K. B. Laskey, and S. Leinhardt, Stochastic blockmodels: First steps, Social Networks 5, 109 (1983).
  * Saad and Nosratinia [2018] H. Saad and A. Nosratinia, Community detection with side information: Exact recovery under the stochastic block model, IEEE Journal of Selected Topics in Signal Processing 12, 944 (2018).
  * Kanade  _et al._ [2016] V. Kanade, E. Mossel, and T. Schramm, Global and local information in clustering labeled block models, IEEE Transactions on Information Theory 62, 5906 (2016).
  * Leng  _et al._ [2013] M. Leng, Y. Yao, J. Cheng, W. Lv, and X. Chen, Active semi-supervised community detection algorithm with label propagation, in  _DASFAA_ (2013).
  * Settles [2009a] B. Settles, Active learning literature survey (2009).
  * Tang and Liu [2010] L. Tang and H. Liu, Community detection and mining in social media, in  _Community Detection and Mining in Social Media_ (2010).
  * Ma  _et al._ [2020] T. Ma, Q. Liu, J. Cao, Y. Tian, A. Al-Dhelaan, and M. Al-Rodhaan, Lgiem: Global and local node influence based community detection, Future Gener. Comput. Syst. 105, 533 (2020).
  * Xin  _et al._ [2018] D. Xin, A. El-Kishky, D. Liao, B. Norick, and J. Han, Active learning on heterogeneous information networks: A multi-armed bandit approach, 2018 IEEE International Conference on Data Mining (ICDM) , 1350 (2018).
  * Wallsten [2007] K. Wallsten, Agenda setting and the blogosphere: An analysis of the relationship between mainstream media and political blogs, Review of Policy Research 24, 567 (2007).
  * Newman [2006] M. Newman, Modularity and community structure in networks., Proceedings of the National Academy of Sciences of the United States of America 103 23, 8577 (2006).
  * Bayati and Montanari [2011] M. Bayati and A. Montanari, The dynamics of message passing on dense graphs, with applications to compressed sensing, IEEE Transactions on Information Theory 57, 764 (2011).
  * Lewis and Gale [1994] D. D. Lewis and W. A. Gale, A sequential algorithm for training text classifiers, SIGIR 17, 3 (1994).
  * Karrer and Newman [2011] B. Karrer and M. Newman, Stochastic blockmodels and community structure in networks, Physical review. E, Statistical, nonlinear, and soft matter physics 83 1 Pt 2, 016107 (2011).
  * Antenucci  _et al._ [2019] F. Antenucci, F. Krzakala, P. Urbani, and L. Zdeborová, Approximate survey propagation for statistical inference, J. Stat. Mech. 2019, 023401 (2019).
  * Wu [2018] D. Wu, Pool-based sequential active learning for regression, IEEE (2018).
  * Tong and Koller [2000] S. Tong and D. Koller, Support vector machine active learning with applications to text classification, Journal of Machine Learning Reasearch 2, 45 (2000).
  * Rangan  _et al._ [2019] S. Rangan, P. Schniter, and A. K. Fletcher, vector approximate message passing, IEEE Transactions on Information Theory 65, 6664 (2019).
  * Cohn  _et al._ [1994] D. A. Cohn, L. E. Atlas, and R. E. Ladner, Improving generalization with active learning, Machine Learning 15, 201 (1994).
  * Dasgupta [2005] S. Dasgupta, Analysis of a greedy active learning strategy, NIPS 17, 337 (2005).
  * Hoi  _et al._ [2006] S. C. Hoi, R. Jin, J. Zhu, and M. R. Lyu, Batch mode active learning and its application to medical image classification, ICML 6, 417 (2006).
  * Dotsenko  _et al._ [1994] V. Dotsenko, S. Franz, and M. Mézard, Partial annealing and overfrustration in disordered systems, J. Phys. A: Math. Gen. 27, 2351 (1994).
  * Sherrington [1980] D. Sherrington, Ising replica magnets, J. Phys. A: Math. Gen. 13 (1980).
  * Urbani [2017] P. Urbani, Statistical physics of glassy systems: tools and applications, unpublished (2017).
  * Zhou [2019] H.-J. Zhou, Active online learning in the binary perceptron problem, Communications in Theoretical Physics 71, 243 (2019).
  * Freund  _et al._ [1992] Y. Freund, E. Shamir, H. S. Seung, and N. Tishby, Information, prediction, and query by committee, NIPS 5, 483 (1992).
  * Seung  _et al._ [1992] H. S. Seung, M. Opper, and H. Sompolinsky, Query by committee, COLT 5, 287 (1992).
  * Castellana and Zdeborová [2011] M. Castellana and L. Zdeborová, Adversarial satisfiability problem, J. Stat. Mech. 2011 (2011).
  * Sun  _et al._ [2011] N. Sun, J. Yi, P. Zhang, H. Shen, and H. Zhai, Deep learning topological invariants in band insulators, Phys. Rev. B 98 (2011).
  * Warmuth  _et al._ [2001] M. K. Warmuth, G. Rätsch, M. Mathieson, J. Liao, and C. Lemmen, Active learning in drug discovery, NIPS 14, 1449 (2001).
  * Barbier  _et al._ [2019] J. Barbier, F. Krzakala, N. Macris, L. Miolane, and L. Zdeborová, Optimal errors and phase transitions in high-dimensional generalized linear models, Proc. Nat. Ac. Sc. 116, 5451 (2019).
  * Krzakala  _et al._ [2014] F. Krzakala, A. Manoel, E. W. Tramel, and L. Zdeborová, Variational free energy for compressed sensing, ISIT , 1499 (2014).
  * McCallum and Nigam [1998] A. K. McCallum and K. Nigam, Employing em and pool-based active learning for text classification, ICML , 350 (1998).
  * Baldassi  _et al._ [2016] C. Baldassi, A. Ingrosso, C. Lucibello, L. Saglietti, and R. Zecchina, Local entropy as a measure for sampling solutions in constraint satisfaction problems, J. Stat. Mech. 2016 (2016).
  * Zhang  _et al._ [2019] L. Zhang, D.-Y. Lin, H. Wang, R. Car, and E. Weinan, Active learning of uniformly accurate interatomic potentials for materials simulation, Phys. Rev. Materials 3, 023804 (2019).
  * Settles [2009b] B. Settles,  _Active Learning Literature Survey_ , Computer Sciences Technical Report (2009).
  * Settles  _et al._ [2008] B. Settles, M. Craven, and S. Ray, Multiple-instance active learning, NIPS (2008).
  * Angluin [1988] D. Angluin, Queries and concept learning, Machine Learning 2, 319 (1988).
  * Atlas  _et al._ [1990] L. E. Atlas, D. A. Cohn, and R. E. Ladner, Training connectionist networks with queries and selective sampling, NIPS 2, 566 (1990).
  * Baldassi  _et al._ [2015] C. Baldassi, A. Ingrosso, C. Lucibello, L. Saglietti, and R. Zecchina, Subdominant dense clusters allow for simple learning and high computational performance in neural networks with discrete synapses., Physical review letters 115 12, 128101 (2015).
  * Dasgupta  _et al._ [2009] A. Dasgupta, A. Kalai, and C. Monteleoni, Analysis of perceptron-based active learning, Journal of Machine Learning research (2009).
  * Ma and et al. [2016] J. Ma and et al., Using deep learning to model the hierarchical structure and function of a cell, Nat. Meth. 15, 290 (2016).
  * Silver and et al. [2016] D. Silver and et al., Mastering the game of go with deep neural networks and tree search, Nat. 529, 484 (2016).
  * B.Zhu and et al. [2018] B.Zhu and et al., Image reconstruction by domain-transform manifold learning, Nat. 555, 487 (2018).
  * Carrasquilla and Melko [2017] J. Carrasquilla and R. Melko, Machine learning phases of matter, Nat. Phys. 529, 484 (2017).
  * A.Braunstein  _et al._ [2010] A.Braunstein, L.Dall’asta, G.Semerjian, and L.Zdeborová, The large deviations of the whitening process in random constraint satisfaction problems, J. Stat. Mech. 2016 (2010).
  * G.Carleo and et al. [2019] G.Carleo and et al., Machine learning and the physical sciences, ArXiv: 1903.10563 (2019).
  * Mitchell [1982] T. M. Mitchell, Generalization as search, Artificial intelligence 18, 203 (1982).
  * Schmidt  _et al._ [2019] J. Schmidt, M. Marques, S. Botti, and M. Marques, Recent advances and applications of machine learning in solid-state materials science, npj computational materials (2019).
  * Donoho  _et al._ [2009] D. L. Donoho, A. Maleki, and A. Montanari, Message-passing algorithms for compressed sensing, Proceedings of the National Academy of Sciences 106, 18914 (2009).
  * Hebb [1914] D. Hebb,  _The organization of Behavior : a Neuropsychological Theory_ (J.Wiley & Sons, 1914).
  * Engels and van den Broeck [2001] A. Engels and C. P. van den Broeck,  _Statistical mechanics of learning_ (Cambridge University Press, 2001).
  * Gardner and Derrida [1989] E. Gardner and B. Derrida, Three unfinished works on the optimal storage capacity of networks, Journal of Physics A: Mathematical and General 22, 1983 (1989).
  * Gardner and Derrida [1988] E. Gardner and B. Derrida, Optimal storage properties of neural network models, J. Phys. A: Math. Gen. 21, 271 (1988).
  * Krzakala  _et al._ [2013] F. Krzakala, F. Ricci-Tersenghi, L. Zdeborová, R. Zecchina, E. W. Tramel, and L. F. Cugliandolo,  _Statistical Physics, Optimization, Inference, and Message-Passing algorithms : Lecture Notes of the Les Houches Physics School_ (Oxford University Press, 2013).
  * Zdeborová and Krzakala [2015] L. Zdeborová and F. Krzakala, Statistical physics of inference: thresholds and algorithms, Advances in Physics 65, 453 (2015).