# Neural-prior stochastic block model

Duranthon
Statistical Physics of Computation laboratory (SPOC)
EPFL, Lausanne, Switzerland Lenka Zdeborová
Statistical Physics of Computation laboratory (SPOC)
EPFL, Lausanne, Switzerland

###### Abstract

The stochastic block model (SBM) is widely studied as a benchmark for graph
clustering aka community detection. In practice, graph data often come with
node attributes that bear additional information about the communities.
Previous works modeled such data by considering that the node attributes are
generated from the node community memberships. In this work, motivated by a
recent surge of works in signal processing using deep neural networks as
priors, we propose to model the communities as being determined by the node
attributes rather than the opposite. We define the corresponding model; we
call it the neural-prior SBM. We propose an algorithm, stemming from
statistical physics, based on a combination of belief propagation and
approximate message passing. We analyze the performance of the algorithm as
well as the Bayes-optimal performance. We identify detectability and exact
recovery phase transitions, as well as an algorithmically hard region. The
proposed model and algorithm can be used as a benchmark for both theory and
algorithms. To illustrate this, we compare the optimal performances to the
performance of simple graph neural networks.

Keywords: stochastic block model SBM, generative priors, belief propagation
BP, approximate message passing AMP, a benchmark for GNN

##  1 Introduction

The stochastic block model (SBM) is widely studied as a benchmark for graph
clustering aka community detection, see e.g. reviews Fortunato (2010); Abbe
(2017); Peixoto (2019). The standard version of the stochastic block model
observed a graph of connections and the goal is to recover the communities
from the knowledge of the graph.

However, in practice, graph data often come with node attributes that bear
additional information about the communities. In such a case there are several
sources of information on communities one can use: the structure of the graph
(as in the standard SBM), and the features or attributes of the nodes. Past
work developed algorithms and models accounting for such node information.
Among the well-known is the CESNA model of Yang et al. (2013) where the
attributes are generated via logistic regression on the community membership.
Another model that recently became popular in the context of benchmarking
graph neural networks (e.g. Chien et al. (2021); Fountoulakis et al. (2022);
Tsitsulin et al. (2021)) is the contextual SBM Binkiewicz et al. (2017);
Deshpande et al. (2018), where communities determine centroids for a Gaussian
mixture model generating the node-features. In both these examples, the node
attributes are generated via conditioning on the community label of the node.

In signal processing, another separate line of work, that witnesses a surge of
interest, is modeling signals as the output of a deep generative neural
network; for recent reviews see e.g. Ongie et al. (2020); Shlezinger et al.
(2020). Deep generative neural networks can be trained on data, and due to
their expressivity are able to capture generic structural properties of the
signal. In community detection the signal can be seen as the community
memberships; following the line of work on deep generative priors it is hence
of interest to propose a model where the node attributes are an input of a
generative neural network and the node community memberships are the output
thereof. In this work, motivated by a recent surge of works in signal
processing using deep neural networks as priors, we propose to model the
communities as being determined by the node attributes rather than the
opposite. We define the corresponding model; that we call the neural-prior
SBM.

One of the attires of the stochastic block model is that it is amenable to
exact statistical analysis of what is the best achievable performance from an
information-theoretic and from algorithmic point of view. This has led to a
line of work, originating in statistical physics, where statistical and
computational thresholds are analyzed; see e.g. Decelle et al. (2011b); Abbe
et al. (2015); Abbe (2017). It is valuable to have a solvable case for which
we know what is statistically and algorithmically achievable; because in the
context of modern machine learning, it is rarely known if or how much the
observed performance can be further improved. Asymptotically exact analysis of
the detectability threshold was also performed for the contextual stochastic
block model Deshpande et al. (2018); Lu and Sen (2020). The main topic of the
present paper is the statistical physics analysis of optimal algorithmic
performance for a simplified version of the proposed neural-prior stochastic
block model that we call the generalized-linear-model SBM (GLM–SBM).

The GLM–SBM model we propose can be used for benchmarking graph neural
networks (GNNs). Since the model is analyzable, we can compare the performance
of the evaluated GNN to the optimal algorithmic performance in a non-trivial
high-dimensional setting. We treat both the unsupervised and the semi-
supervised cases and accompany our paper with an implementation that can be
readily used for comparison by GNN developers. As far as we found, a model
similar to the neural-prior SBM, we propose here, has been used in Cho et al.
(2022). In that work it is used as a building block for a large neural
network; it was not analyzed per se.

A large part of this paper is dedicated to the asymptotic analysis of the
GLM–SBM model. We identify how the detectability phase transition well known
from the SBM changed under the presence of the GLM-prior. We also unveil an
exact recovery phase transition that happens when the prior on the latent
variables of the GLM is binary, while the average degree of the SBM remains
finite. Such an exact recovery phase at a finite average degree came to us as
a surprise and we find it rather remarkable in view of the fact that without
the GLM prior exact recovery in the standard SBM is only possible for degrees
growing logarithmically with the system size Abbe et al. (2015); Abbe (2017).
The exact recovery transition is discontinuous and makes the problem
algorithmically challenging posing a nice set of parameters that can serve as
a benchmark in the attempt of improving graph-neural networks.

##  2 The neural-prior stochastic block model

###  2.1 Definition

We consider a set $V$ of $|V|=N$ nodes, a graph $G(V,A)$ on those nodes. Nodes
have features/attributes $F_{\mu}\in\mathbb{R}^{M}$ of dimension $M$,
$\mu=1\dots,N$. The features and the graphs are observed. We aim to divide the
set of nodes into $q$ communities with labels $s_{\mu}\in\\{1,\dots,q\\}$ in
such a way that (a) the graph structure correlates with the labels, e.g. nodes
being in the same community are more likely to be connected, and (b) the node
attributes $F_{\mu}$ are correlated with the labels.

##### SBM:

In the stochastic block model the edges $A_{\mu\nu}$ of the graph $G$ are
generated conditioned on the group memberships $s_{\mu}$; we consider the
following rule:

$P_{\rm SBM}(A_{\mu\nu}=1|s_{\mu},s_{\nu})=\left\\{\begin{array}[]{r c
l}c_{i}/N&\mathrm{if}&s_{\mu}=s_{\nu},\\\ c_{o}/N&\mathrm{if}&s_{\mu}\neq
s_{\nu},\end{array}\right.$ (1)

and $A_{\mu\nu}=0$ otherwise. Here $c_{i}$ and $c_{o}$ are the affinity
coefficients common to the SBM. We define the affinity matrix whose elements
are $c_{s,t}=c_{i}\delta_{s=t}+c_{o}\delta_{s\neq t}$. We note that the
literature often considers a more general SBM where the affinity matrix has
arbitrary elements. The model and analysis proposed in this work could be
readily generalized to that case. We consider a slightly restricted version of
the SBM purely for simplicity. In the SBM the ground truth group memberships
$s_{\mu}$ are generated at random from a prior that only accounts for the
sizes of the $q$ groups. The node attributes $F$ are simply ignored in the
SBM.

##### Neural-prior SBM:

In neural-prior SBM, that we define here, the group memberships $s_{\mu}$ can
be a generic function on the attributes $F_{\mu}$. Such a function can be
represented by a deep neural network and learned from ground-truth data. The
training data would be pairs $\\{F_{\mu},s_{\mu}\\}$ where attributes act as
the neural network inputs and the group memberships as output labels. For
instance, for a $L$-layer fully connected neural network this reads

$s_{\mu}=\varphi^{(L)}\big{(}W^{(L)}\dots\varphi^{(2)}\big{(}W^{(2)}\varphi^{(1)}(W^{(1)}F))\dots)$
(2)

for the last activation function $\varphi^{(L)}$ chosen as in multi-class
classification tasks.

The aim of this paper is to provide a benchmark model where the optimal
performance can be analyzed asymptotically exactly. For this we need to (a)
define the corresponding asymptotic limit, (b) consider a simple neural
network prior that is amenable to asymptotic analysis. We will also limit
ourselves to consider community detection with two groups of the same size
only, $q=2$ (this is not a strong limitation, but is considered in the follow-
up for simplicity). With this in mind, in the rest of the paper, we will
consider the following model generating the group memberships $s_{\mu}$.

##### GLM–SBM:

In order to make analysis amenable we will consider the features $F$ to be
random and drawn independently as $F_{\mu l}\sim\mathcal{N}(0,1/M)$. We then
consider $M$ latent variables $w_{l}\sim P_{w}$, $l=1,\dots,M$ and generate
the community memberships as

$s_{\mu}=\mathrm{sign}\big{(}\sum_{l}^{M}F_{\mu l}w_{l}\big{)}$ (3)

This corresponds to a single-layer neural network with a sign activation
function. Such a neural network is also often referred to as the generalized
linear model (GLM) or as the perceptron. We will hence call this variant of
the neural-prior SBM the GLM–SBM.

Concerning the asymptotic limit, we work in the challenging sparse case of
SBM. We parameterize the SBM by the standard parameterization

$c_{i}=c+\sqrt{c}\lambda\quad,\quad c_{o}=c-\sqrt{c}\lambda$ (4)

We then consider $N\to\infty$ with $c=(c_{i}+c_{o})/2=\mathcal{O}(1)$ is the
average degree, and $\lambda=\mathcal{O}(1)$ is the signal-to-noise ratio. We
further work in the high-dimensional limit of the GLM where
$N/M=\alpha=\mathcal{O}(1)$, with $\alpha$ being the aspect ratio that will
play a role of another signal-to-noise ratio. This is because the higher
$\alpha$ the more correlation there is between the group memberships and the
easier the community detection should be.

The GLM–SBM differs from the SBM because communities are not independent,
conditionally on the features. For instance, in the extreme case $M=1$, all
memberships are known, up to a global flip given by $w_{1}$; that is to say,
they are all very strongly correlated. The GLM–SBM tends toward a SBM when
$\alpha\to 0$. Indeed, for large $M$, $\sum_{l}^{M}F_{\mu l}w_{l}$ tend to
independent Gaussian variables.

###  2.2 Related work

Anticipating the asymptotic analysis that we are aiming at, we note that such
an analysis has been done for the standard SBM in Decelle et al. (2011b, a)
using the belief propagation algorithm and the cavity method from statistical
physics for the asymptotic analysis of its behavior. Concerning semi-
supervised learning in the SBM, the information coming from the semi-
supervision is readily incorporated into the analysis of the above papers as
has been done in Zhang et al. (2014).

The predictions of Decelle et al. (2011b, a) have then been partially
established rigorously see e.g. Mossel et al. (2015, 2018); Abbe (2017); Coja-
Oghlan et al. (2017). However, the full conjecture of Decelle et al. (2011b,
a) about the asymptotic exactness of their analysis remains an open question
from the mathematical point of view. In this paper, we will use the same
techniques as Decelle et al. (2011b, a) anticipating a follow-up work putting
the conjectures about optimality on a rigorous basis. For the GLM, which is
defined by a dense graphical model, the rigorous analysis is simpler and was
carried out in Barbier et al. (2019).

The analysis of the GLM–SBM requires to _glue_ the two graphical models using
the GLM as the prior for the SBM, and the SBM as a source of uncertainty of
the outputs of the GLM. Such a glueing of two dense exactly solvable graphical
models for developed in Manoel et al. (2017) with rigorous justifications
given in Gabrié et al. (2018); Aubin et al. (2019); Gerbelot and Berthier
(2021). Our work is the first one, as far as we are aware, where a sparse
graphical model (the SBM) is glued to a dense graphical model (the GLM). This
can be done heuristically and is conjectured asymptotically exact along the
lines of the works of Decelle et al. (2011b, a). A complete rigorous
justification would have to be preceded by the proof of the conjecture for the
SBM that is still open.

The contextual stochastic block model (CSBM) introduced and studied
theoretically in Binkiewicz et al. (2017); Deshpande et al. (2018) is another
version of the SBM incorporating node information. In the CSBM the node
information is modeled via a Gaussian mixture model with each community having
their own centroid. From the analysis point of view, this model takes into
account two sources of observation about the latent variables – the community
memberships. This is hence different from the GLM–SBM where one model serves
as a prior for the other instead of as an independent source of information.
Modulo this difference, some of the analysis performed for the CSBM is related
to our work. Notably, the detectability threshold and the linearized message
passing algorithm presented in Deshpande et al. (2018); Lu and Sen (2020) are
obtained in a similar manner in which we obtain the detectability phase
transition and the linearized algorithm. We note that the semi-supervised
version of the CSBM has not been analyzed, but this could be done rather
straightforwardly using the same methods as in Zhang et al. (2014).

##  3 Bayes-optimal estimation of communities

We consider the GLM–SBM as defined above and aim to analyze the Bayes-optimal
inference of the community structure. We will consider in general the semi-
supervised setting where next to the structure of the graph $A$ and the
covariates $F$ we observe the communities for a subset $\Xi$ of the nodes,
$\rho=|\Xi|/N$. We denote by $s$ the vector of unobserved nodes and $s_{\Xi}$
the vector of observed nodes. The unsupervised case is then recovered as the
special case where $\Xi$ is an empty set, $\rho=0$.

The analysis of this paper is set in the so-called Bayes-optimal setting where
we know the details of the GLM–SBM model. The only quantity that we do not
observe is the ground truth values of the latent variables $w$ that generate
the group memberships $s$. For the group memberships, we only observe a
fraction $\rho$ of them in the semi-supervised setting and none of them in the
unsupervised setting.

The optimal inference is then done using the posterior distribution over the
unobserved communities

$P(s|A,s_{\Xi},F)=\frac{P(A|s,s_{\Xi},F)P_{\rm
prior}(s|s_{\Xi},F)}{Z(A,s_{\Xi},F)}=\frac{P_{\rm
prior}(s|s_{\Xi},F)}{Z(A,s_{\Xi},F)}\prod_{\mu<\nu}P_{\rm
SBM}(A_{\mu\nu}|s_{\mu},s_{\nu})$ (5)

where $Z(A,F,s_{\Xi})$ is the normalization constant. We used here the
definition of the GLM–SBM model that implies
$P(A|s,s_{\Xi},F)=P(A|s,s_{\Xi})$. For GLM–SBM the prior on $s$ is

$P_{\rm
prior}(s|s_{\Xi},F)=\frac{1}{Z(s_{\Xi},F)}\int\mathrm{d}w\,P_{w}(w)\prod_{\mu}\Big{[}P_{s,\mu}(s_{\mu})P_{0}(s_{\mu}|\sum_{l}^{M}F_{\mu
l}w_{l})\Big{]}$ (6)

where we define $P_{0}(t|z)=\delta_{t=\mathrm{sign}(z)}$ the output
distribution and $P_{s,\mu}$ the additional prior distribution, which is used
to inject information about the membership of node $\mu$:

$P_{s,\mu}(t)=\left\\{\begin{array}[]{r c
l}\delta_{t=s_{\mu}}&\mathrm{if}&\mu\in\Xi,\\\
1/2&\mathrm{if}&\mu\notin\Xi.\end{array}\right.$ (7)

In eq. (6) we marginalize over the latent variable $w$. However, since the
estimation of the latent variable $w$ is crucial in order to exploit the full
power of the prior (6) it will be instrumental to consider the posterior as a
joint probability of the unobserved nodes and the latent variable

$P(s,w|A,s_{\Xi},F)=\frac{P_{w}(w)}{\tilde{Z}(A,s_{\Xi},F)}\prod_{\mu}\Big{[}P_{s,\mu}(s_{\mu})P_{0}(s_{\mu}|\sum_{l}^{M}F_{\mu
l}w_{l})\Big{]}\prod_{\mu<\nu}P_{\rm SBM}(A_{\mu\nu}|s_{\mu},s_{\nu})$ (8)

$\tilde{Z}$ is the Bayesian evidence. We define the free entropy of the
problem as its logarithm:

$\phi(A,s_{\Xi},F)=\frac{1}{N}\log\tilde{Z}(A,s_{\Xi},F)$ (9)

We seek an estimator $\hat{s}$ that maximizes the overlap with the ground
truth. The Bayes-optimal estimator $\hat{s}$ that maximizes it is given by

$\hat{s}_{\mu}^{\mathrm{MMO}}=\operatorname*{argmax}_{t}\,p_{\mu}(t)$ (10)

where $p_{\mu}$ is the marginal posterior probability of node $\mu$. Using the
ground truth values $s_{\mu}$ of the communities the maximal mean overlap is
then computed as

$\mathrm{MMO}=\frac{1}{N}\sum_{\mu=1}^{N}\delta_{\hat{s}_{\mu}^{\mathrm{MMO}},s_{\mu}}$
(11)

To estimating the latent variable $w$, we consider minimizing the mean squared
error via the MMSE estimator

$\hat{w}_{l}^{\mathrm{MMSE}}=\int\mathrm{d}s\mathrm{d}w\,P(s,w|A,s_{\Xi},F)w_{l}$
(12)

i.e. $\hat{w}^{\mathrm{MMSE}}$ is the mean of the posterior distribution.
Again using the ground truth values $w_{l}$ of the latent variables the MMSE
is then computed as

$\mathrm{MMSE}=\frac{1}{M}\sum_{l=1}^{M}(\hat{w}_{l}^{\mathrm{MMSE}}-w_{l})^{2}$
(13)

The problem is invariant by a global sign flip of $s$ and $w$ so in practice
we measure the following overlaps

$q_{S}=\frac{|\hat{s}\cdot s|}{N}\quad,\quad q_{W}=\frac{|\hat{w}\cdot
w|}{||\hat{w}||_{2}||w||_{2}}$ (14)

In general, the Bayes-optimal estimation requires the evaluation of the
averages over the posterior that is in general exponentially costly in $N$ and
$M$. In the next section, we will derive the AMP–BP algorithm and argue that,
in the limit $N\to\infty$ and $M\to\infty$ with $N/M=\alpha={\cal O}(1)$ and
all other parameters being of ${\cal O}(1)$ this algorithm approximates the
MMSE and MMO estimators with an error that vanishes. We give more precise
statements below.

##  4 The AMP–BP algorithm

To retrieve the communities for the GLM–SBM, our main results rely on an
algorithm that we call AMP–BP. We conjecture that in the large system size,
this algorithm cannot be beaten by another polynomial algorithm. We can also
extract the so-called hard phases where the randomly initialized algorithm
fails, but an exponentially costly algorithm would succeed; we do this using
an informed initialization and the free entropy. We then analyze the
performance of the algorithm and the associated phase transitions.

###  4.1 Algorithm

The algorithm is based on belief propagation (BP) and approximate message-
passing (AMP). BP was used to solve SBM in Decelle et al. (2011b) and
conjectured asymptotically optimal among efficient algorithms in doing so. AMP
was used to solve GLM, see e.g. Donoho et al. (2009); Krzakala et al. (2012),
and again conjectured asymptotically optimal among efficient algorithms in
doing so with strong evidence for this being provided by Celentano et al.
(2021). We glue these two algorithms together along the lines of Manoel et al.
(2017); Aubin et al. (2019) to solve the GLM–SBM; we call the resulting
algorithm AMP–BP. Using statistical physics arguments analogous to those in
Decelle et al. (2011b); Krzakala et al. (2012) we conjecture that it provides
asymptotically optimal performance in the considered cases.

We derive the AMP–BP algorithm for the GLM–SBM starting from the factor graph
of the problem:

$\textstyle{w_{l}}$$\scriptstyle{\chi_{w}^{l\to\mu}}$$\scriptstyle{\psi_{s}^{\mu\to\mu}}$$\textstyle{s_{\mu}}$$\scriptstyle{\chi_{s}^{\mu\to\nu}}$$\scriptstyle{\psi_{s}^{\mu\to\nu}}$$\textstyle{w_{m}}$$\scriptstyle{\psi_{w}^{\nu\to
m}}$$\scriptstyle{\chi_{s}^{\nu\to\nu}}$$\textstyle{s_{\nu}}$

The $\chi$s and $\psi$s are probability distributions on the variables $s$ and
$w$; they are called cavity messages. We write the belief-propagation (BP)
equations for these distributions that read:

$\displaystyle\chi_{w_{l}}^{l\to\mu}$ $\displaystyle\propto
P_{w}(w_{l})\prod_{\nu\neq\mu}\psi_{w_{l}}^{\nu\to l}$ (15)
$\displaystyle\psi_{w_{l}}^{\nu\to l}$
$\displaystyle\propto\sum_{s_{\nu}}\chi_{s_{\nu}}^{\nu\to\nu}\int\prod_{m\neq
l}\left(\mathrm{d}w_{m}\chi_{w_{m}}^{m\to\nu}\right)P_{0}(s_{\nu}|F_{\nu}\cdot
w)$ (16) $\displaystyle\psi_{s_{\nu}}^{\nu\to\nu}$
$\displaystyle\propto\int\prod_{m}\left(\mathrm{d}w_{m}\chi_{w_{m}}^{m\to\nu}\right)P_{0}(s_{\nu}|F_{\nu}\cdot
w)$ (17) $\displaystyle\chi_{s_{\mu}}^{\mu\to\mu}$ $\displaystyle\propto
P_{s,\mu}(s_{\mu})\prod_{\nu\neq\mu}\psi_{s_{\mu}}^{\nu\to\mu}$ (18)
$\displaystyle\chi_{s_{\mu}}^{\mu\to\nu}$ $\displaystyle\propto
P_{s,\mu}(s_{\mu})\psi_{s_{\mu}}^{\mu\to\mu}\prod_{\eta\neq\mu,\nu}\psi_{s_{\mu}}^{\eta\to\mu}$
(19) $\displaystyle\psi_{s_{\nu}}^{\mu\to\nu}$
$\displaystyle\propto\sum_{s_{\mu}}\chi_{s_{\mu}}^{\mu\to\nu}P_{\rm
SBM}(A_{\mu\nu}|s_{\mu},s_{\nu})$ (20)

The proportionality signs $\propto$ denote that all the messages are non-
negative numbers summing to one over their lower indices, the corresponding
normalization factors being omitted in our notation.

These BP equations still include a high-dimensional integral and hence cannot
be implemented efficiently. We simplify them to obtain AMP–BP by using the
central limit theorem on the dense side of the graphical model and keeping
only the means and variances of the resulting Gaussians. This is standard in
the derivation of the AMP algorithm, see e.g. Krzakala et al. (2012). The
details of this derivation are given in appendix A.

In order to state the final algorithm, we introduce the denoising function:

$g_{o}(\omega,\chi,V)=\frac{\int\mathrm{d}z\sum_{s}\chi_{s}P_{0}(s|z)(z-\omega)e^{-(z-\omega)^{2}/2V}}{V\int\mathrm{d}z\sum_{s}\chi_{s}P_{0}(s|z)e^{-(z-\omega)^{2}/2V}}$
(21)

We define the input functions as

$f_{a}(\Lambda,\Gamma)=\frac{\int\mathrm{d}w\,P_{w}(w)we^{-\Lambda
w^{2}/2+\Gamma w}}{\int\mathrm{d}wP_{w}(w)e^{-\Lambda w^{2}/2+\Gamma
w}}\quad,\quad f_{v}(\Lambda,\Gamma)=\partial_{\Gamma}f_{a}(\Lambda,\Gamma)$
(22)

We denote by $Z$s the normalization factors obtained so that the messages sum
to one over their lower indices.

To give some intuition we explain what are the variables AMP–BP employs.
$a_{l}$ is an estimation of the posterior mean of $w_{l}$, $v_{l}$ is an
estimation of its variance; $\omega_{\mu}$ is an estimation of the mean of
$\sum_{l}F_{\mu l}w_{l}$ and $V$ an estimation of its variance.
$\psi_{s_{\mu}}^{\mu\to\mu}$ is a marginal distribution on $s_{\mu}$, as
estimated by the AMP on the GLM side, while $\chi_{s_{\mu}}^{\mu\to\mu}$ is
the distribution as estimated by the BP on the SBM side. $\Gamma_{l}$ is a
proxy for estimating the mean of $w_{l}$ in absence of the prior $P_{w}$ and
$\Lambda$ is for the variance. $h_{t}$ can be interpreted as an external field
enforcing the nodes not to be in the same group; $\chi_{s_{\mu}}^{\mu\to\nu}$
is a marginal distribution on $s_{\mu}$ (these variables are the messages of a
sum-product message-passing algorithm) and $\chi_{s_{\mu}}^{\mu}$ is the
estimated posterior marginal on $s_{\mu}$, that we are interested in.

The AMP–BP algorithm reads:

AMP–BP

0: features $F_{\mu l}$, graph $G$, affinity matrix $c_{s,t}$, prior
information $P_{s,\mu}$.

Initialize $a_{l}^{(0)}=\epsilon_{l}$, $v_{l}^{(0)}=1$, $g_{o,\mu}^{(0)}=0$,
$\chi_{s_{\mu}}^{\mu\to\nu,(0)}=\frac{1}{2}+s_{\mu}\epsilon^{\mu\to\nu}$,
$\chi_{s_{\mu}}^{\mu\to\mu,(0)}=\frac{1}{2}$,
$\chi_{s_{\mu}}^{\mu,(0)}=\frac{1}{2}$, $t=0$; where $\epsilon$s are zero-mean
small random variables.

repeat

AMP update of $\omega_{\mu},V_{\mu}$ $\displaystyle
V^{(t+1)}\leftarrow\frac{1}{M}\sum_{l}v_{l}^{(t)}$
$\displaystyle\omega_{\mu}^{(t+1)}\leftarrow\sum_{l}F_{\mu
l}a_{l}^{(t)}-V^{(t+1)}g_{o,\mu}^{(t)}$

AMP update of $\psi^{\mu\to\mu},g_{o,\mu},\Lambda,\Gamma_{l}$
$\displaystyle\psi_{s_{\mu}}^{\mu\to\mu,(t+1)}\leftarrow\int\frac{\mathrm{d}zP_{0}(s_{\mu}|z)}{\sqrt{2\pi
V^{(t+1)}_{\mu}}}e^{-\frac{(z-\omega^{(t+1)}_{\mu})^{2}}{2V^{(t+1)}_{\mu}}}$
$\displaystyle g_{o,\mu}^{(t+1)}\leftarrow
g_{o}(\omega_{\mu}^{(t+1)},\chi^{\mu\to\mu,(t)},V^{(t+1)})$
$\displaystyle\Lambda^{(t+1)}\leftarrow\frac{1}{M}\sum_{\mu}g_{o,\mu}^{2,(t+1)}$
$\displaystyle\Gamma_{l}^{(t+1)}\leftarrow\Lambda^{(t+1)}a_{l}^{(t)}+\sum_{\mu}F_{\mu
l}g_{o,\mu}^{(t+1)}$

AMP update of the estimated marginals $a_{l},v_{l}$ $\displaystyle
a_{l}^{(t+1)}\leftarrow f_{a}(\Lambda^{(t+1)},\Gamma_{l}^{(t+1)})$
$\displaystyle v_{l}^{(t+1)}\leftarrow
f_{v}(\Lambda^{(t+1)},\Gamma_{l}^{(t+1)})$

BP update of the field $h$ $\displaystyle
h_{s}^{(t+1)}\leftarrow\frac{1}{N}\sum_{\mu}\sum_{s_{\mu}}c_{s,s_{\mu}}\chi_{s_{\mu}}^{\mu,(t)}$

BP update of the messages $\chi^{\mu\to\nu}$ for $(\mu\nu)\in G$ and of the
marginals $\chi^{\mu}$
$\displaystyle\chi_{s_{\mu}}^{\mu\to\nu,(t+1)}\leftarrow$
$\displaystyle\frac{P_{s,\mu}(s_{\mu})}{Z^{\mu\to\nu}}e^{-h_{s_{\mu}}^{(t+1)}}\mkern-6.0mu\psi_{s_{\mu}}^{\mu\to\mu,(t+1)}$
$\displaystyle\;\prod_{\eta\in\partial\mu\backslash\nu}\sum_{s_{\eta}}c_{s_{\eta},s_{\mu}}\chi_{s_{\eta}}^{\eta\to\mu,(t)}$
$\displaystyle\chi_{s_{\mu}}^{\mu,(t+1)}\leftarrow$
$\displaystyle\frac{P_{s,\mu}(s_{\mu})}{Z^{\mu}}e^{-h_{s_{\mu}}^{(t+1)}}\mkern-6.0mu\psi_{s_{\mu}}^{\mu\to\mu,(t+1)}$
$\displaystyle\quad\prod_{\eta\in\partial\mu}\sum_{s_{\eta}}c_{s_{\eta},s_{\mu}}\chi_{s_{\eta}}^{\eta\to\mu,(t)}$

BP update of the SBM-to-GLM messages $\chi^{\mu\to\mu}$
$\displaystyle\chi_{s_{\mu}}^{\mu\to\mu,(t+1)}\leftarrow$
$\displaystyle\frac{P_{s,\mu}(s_{\mu})}{Z^{\mu\to\mu}}e^{-h_{s_{\mu}}^{(t+1)}}$
$\displaystyle\quad\prod_{\eta\in\partial\mu}\sum_{s_{\eta}}c_{s_{\eta},s_{\mu}}\chi_{s_{\eta}}^{\eta\to\mu,(t)}$

$t\leftarrow t+1$

until convergence of $a_{l},v_{l},\chi^{\mu}$

estimated mean $a_{l}$ and variance $v_{l}$ of $w_{l}$ and marginal
distribution $\chi^{\mu}$ of $s_{\mu}$.

We provide an implementation of AMP–BP in the supplementary material. It is
also available from our repository.111gitlab.epfl.ch/spoc-idephics/glm-sbm

We draw attention to the output function $g_{o}$ that covers the difference
between AMP for GLM–SBM and AMP for GLM alone. In AMP for GLM alone $g_{o}$
depends on the observed labels while here we use their estimated marginals. On
the other side, the difference between BP for GLM–SBM and BP for SBM alone are
the messages $\psi^{\mu\to\mu}$ in BP update. $\psi^{\mu\to\mu}$ can be
interpreted as the conditional probability of $s_{\mu}$ given $w$ without SBM.

##### Estimators.

The Bayes-optimal estimators of $s$ and $w$ are obtained according to eqs.
(10) and (12). Expressed using the AMP–BP messages they become

$\hat{s}^{\rm
AMP–BP}_{\mu}=\mathrm{sign}(2\chi_{+}^{\mu}-1)\quad,\quad\hat{w}^{\rm
AMP–BP}_{l}=a_{l}$ (23)

where $\chi_{+}^{\mu}$ is the estimated marginal probability of the event
$s_{\mu}=+1$ and $a_{l}$ is the estimated mean of $w_{l}$.

##### Free entropy.

We express also the free entropy $\phi$ in terms of the messages and variables
of AMP–BP at the fixed point; it is called the Bethe free entropy
$\phi_{\mathrm{Bethe}}$. The derivation from the factor graph is done in
appendix B. Up to a term that diverges with $N$ we obtain that the Bethe free
entropy is

$\displaystyle\phi_{\mathrm{Bethe}}$
$\displaystyle=\phi_{\mathrm{SBM}}+\phi_{\mathrm{GLM}}$ (24)
$\displaystyle\phi_{\mathrm{SBM}}$
$\displaystyle=\frac{1}{N}\sum_{\mu}\log\sum_{s_{\mu}}P_{s,\mu}(s_{\mu})e^{-h_{s_{\mu}}}\prod_{\eta\in\partial\mu}\sum_{s_{\eta}}c_{s_{\eta},s_{\mu}}\chi_{s_{\eta}}^{\eta\to\mu}$
$\displaystyle\quad{}-\frac{1}{N}\sum_{(\mu\nu)\in
G}\log\sum_{s_{\mu},s_{\nu}}c_{s_{\mu},s_{\nu}}\chi_{s_{\mu}}^{\mu\to\nu}\chi_{s_{\nu}}^{\nu\to\mu}+\frac{c}{2}$
(25) $\displaystyle\phi_{\mathrm{GLM}}$
$\displaystyle=\frac{1}{N}\sum_{\mu}\log\int\frac{\mathrm{d}z_{\mu}}{\sqrt{2\pi
V_{\mu}}}\,\sum_{s_{\mu}}\chi_{s_{\mu}}^{\mu\to\mu}P_{o}(s_{\mu}|z_{\mu})e^{-(z_{\mu}-\omega_{\mu})^{2}/2V_{\mu}}$
$\displaystyle\quad{}+\frac{1}{N}\sum_{l}\log\int\mathrm{d}w_{l}P_{w}(w_{l})e^{-\Lambda_{l}w_{l}^{2}/2+\Gamma_{l}w_{l}}$
$\displaystyle\quad{}+\frac{1}{N}\left(\sum_{l}\frac{\Lambda_{l}}{2}(a_{l}^{2}+v_{l})-\Gamma_{l}a_{l}+\sum_{\mu}\frac{(\omega_{\mu}-\sum_{l}F_{\mu
l}a_{l})^{2}}{2V_{\mu}}\right)$ (26)

If the AMP–BP has more than one fixed point then the free entropy serves to
select the fixed point of AMP–BP that corresponds to Bayes-optimal
performance. It is the one with the largest free entropy that should be
selected.

We compare later the free entropy of the fixed point of AMP–BP to the free
entropy of the fully informative point where $q_{S}=q_{W}=1$. We write it
$\phi_{\mathrm{info}}$. At this point the messages are delta functions of the
ground truth; we can derive $\phi_{\mathrm{info}}$ directly from the factor
graph and it reads

$\phi_{\mathrm{info}}=\frac{1}{\alpha}\mathbb{E}_{P_{w}}\log
P_{w}+\frac{1}{N}\sum_{(\mu\nu)\in G}\log
c_{s_{\mu},s_{\nu}}-\frac{c}{2}-(1-\rho)\log 2$ (27)

###  4.2 Asymptotic optimality conjecture.

We conjecture that AMP–BP gives the Bayes-optimal estimator for GLM–SBM in the
following sense.

We define the two possible initializations: (a) random initialization, where
we initialize the messages randomly according to their prior distribution,
adding no information, as described in the algorithm above; and (b) informed
initialization, where we initialize the estimators to delta functions of the
true values of $s$ and $w$.

We consider the fixed point of AMP–BP that has the largest Bethe free entropy
$\phi_{\mathrm{Bethe}}$. We argue that it suffices to check the random and
informed initializations to find all the relevant fixed points.

We conjecture that, asymptotically exactly, the AMP–BP fixed point that has
the largest $\phi_{\mathrm{Bethe}}$ provides the Bayes-optimal estimators for
the GLM–SBM model. Its overlap $q_{S}$ is asymptotically equal to the Bayes-
optimal MMO overlap and $\phi_{\mathrm{Bethe}}$ is equal to $\phi$, with high
probability as $N\to+\infty$. This is aligned with the same conjecture for BP
and the standard SBM from Decelle et al. (2011a) and the proofs of this
property for the AMP algorithm and the pure GLM model in Barbier et al.
(2019).

##  5 Bayes-optimal estimation with AMP–BP and phase transitions

###  5.1 Gaussian prior, 2nd order transition to partial recovery

In this subsection we consider the GLM prior $P_{w}$ to be a standard
Gaussian. The GLM then produces binary labels, the group memberships, with the
same probability of being in each of the groups.

We conjecture that for this prior the fixed point of AMP–BP reached from
random initialization always corresponds to the Bayes-optimal estimation and
no computationally hard phase is present. We observe that the algorithm
converges to the same fixed point for the two possible initializations. In
Fig. 7 in the appendix E we illustrate that the system size we use is close
enough to the thermodynamical limit in the sense that the change in the curves
is small when the size is changed.

The accuracy AMP–BP achieves is depicted in Figs. 1 (unsupervised case) and 8
(semi-supervised case, in appendix E). We observe that the larger the snr
$\lambda$ or the aspect ratio $\alpha$ the better the recovery. The recovery
is eased when community memberships are explained by a few features i.e. when
$\alpha$ is large.

Figure 1:  _Left and right:_ overlaps $q_{S}$ (group membership estimation)
and $q_{W}$ (the GLM latent vector estimation) of the fixed point of AMP–BP,
vs $\lambda$ for a range of compression ratios $\alpha$. Vertical dashed
lines: theoretical thresholds $\lambda_{c}$ to partial recovery, eq. (29).
$N=10^{4}$, $c=5$, $P_{w}$ Gaussian. We run ten experiments per point.
_Inset:_ we plot the ten data points and their mean.

In the unsupervised case, we observe a phase transition from a non-informative
fixed point $q_{S}=q_{W}=0$ to an informative fixed point $q_{S}>0,q_{W}>0$.
The transition is located at a particular critical threshold $\lambda_{c}$.
This transition is well known for standard SBM, which is recovered here in the
$\alpha\to 0$ limit, where $\lambda_{c}=1$ for $q=2$. The transition is of 2nd
order; this means that the overlaps vary continuously with respect to
$\lambda$. In the semi-supervised case the 2nd order transition disappears.

##### Linearization, spectral algorithm.

$\lambda_{c}$ can be computed by a linear stability analysis of the non-
informative fixed point of AMP–BP: at a given $\lambda$, if the algorithm is
not stable it will move away from the non-informative fixed point to the
informative fixed point. The linearization of the algorithm is done in
appendix C. We obtain the following update equation:

$x^{\mu\to\nu,(t+1)}=\frac{\lambda}{\sqrt{c}}\left(\sum_{\eta\in\partial\mu\backslash\nu}x^{\eta\to\mu,(t)}+\frac{2}{\pi}\sum_{\eta}(FF^{T}-I_{N})_{\mu,\eta}\sum_{\rho\in\partial\eta}x^{\rho\to\eta,(t-1)}\right)$
(28)

where the $x$s are real random variables and $(FF^{T})_{\mu\nu}=\sum_{l}F_{\mu
l}F_{\nu l}$. Taking the variance of this equation and averaging over the
realizations of the graph we obtain the stability criterion

$1=\lambda_{c}^{2}\left(1+\frac{4\alpha}{\pi^{2}}\right)\,.$ (29)

Eq. (28) can be interpreted as a spectral algorithm; we apply iteratively a
linear operator to the variables

$x=\frac{\lambda}{\sqrt{c}}\left(B+G\tilde{B}\right)x$ (30)

where

$B_{\mu\to\nu,\rho\to\eta}=\delta_{\mu=\eta}(1-\delta_{\rho=\nu})\quad,\quad
G_{\mu\to\nu,\eta}=\frac{2}{\pi}(FF^{T}-I_{N})_{\mu,\eta}\quad,\quad\tilde{B}_{\eta,\mu\to\rho}=\delta_{\rho=\eta}$
(31)

$B$ is the non-backtracking matrix Krzakala et al. (2013). Such a spectral
algorithm will share the phase transition at snr given by eq. (28). The study
of the resulting overlap is also of interest, but we do not consider it in the
present article.

###  5.2 Binary prior, 1st order transition to exact recovery

In this subsection the GLM prior is considered to be
$P_{w}=(\delta_{w=1}+\delta_{w=-1})/2$ Rademacher. This still produces two
groups with unbiased sizes.

The fixed point AMP–BP achieves from a random initialization is depicted on
Figs. 2 and 9 (in appendix E). We observe it admits the same transition to
partial recovery at $\lambda_{c}$, eq. (29), as the Gaussian prior does; this
is also predicted by the linearization of the previous part.

Figure 2:  _Left and right:_ overlap $q_{S}$ and free entropy
$\phi_{\mathrm{Bethe}}-\phi_{\mathrm{info}}$ of the fixed point of AMP–BP, vs
$\lambda$ for several compression ratios $\alpha$. $N=10^{4}$, $c=5$, $P_{w}$
Rademacher, $\rho=0$. We run ten experiments per point; the median is plotted
and the error bars are the difference between the 0.85th and 0.15th quantiles.
_Insets:_ we plot the median and the ten data points. We use damping for
AMP–BP: we interpolate taking 1/4 of the values at $t+1$ and 3/4 of the values
at $t$.

For values of $\alpha>\alpha_{\mathrm{algo}}$ (that we determine below), we
observe another transition; it is discontinuous, from partial recovery
$q_{S}>0,q_{W}>0$ to exact recovery $q_{S}=q_{W}=1$. There is a value
$\lambda_{\mathrm{algo}}$ such that for $\lambda>\lambda_{\mathrm{algo}}$
randomly initialized AMP–BP recovers the group memberships exactly for all
nodes. The overlap $q_{S}$ does not vary continuously at
$\lambda_{\mathrm{algo}}$; over the many independent trials we observe that
there is an interval of overlaps below 1 that cannot be reached by AMP–BP for
any $\lambda$.

Discontinuous thresholds are related to the existence of several fixed points
of AMP–BP and to first-order phase transitions. A 1st order phase transition
is located by comparing the free entropies $\phi_{\mathrm{Bethe}}$ of the
various fixed points. We notice that next to the AMP–BP fixed point that is
reached from a random initialization, the exact recovery point is a fixed
point at all values of $\lambda$ and $\alpha$ (still considering $P_{w}$
binary). In the region of $\lambda$ and $\alpha$ where these two fixed points
differ we need to compare their free entropies. The fixed point with larger
free entropy describes the Bayes-optimal performance that can in general be
better than the one of AMP–BP. The difference between the free entropies of
the fixed point reached by AMP–BP from random initialization and the
informative fixed point is depicted on the rhs of Fig. 2. We see that for
$\lambda<\lambda_{\rm IT}$ the fixed point reached from random initialization
has larger free entropy $\phi_{\mathrm{Bethe}}>\phi_{\mathrm{info}}$ and hence
describes the optimal performance. In the region $\lambda_{\rm
IT}<\lambda<\lambda_{\rm algo}$ the informative fixed point has larger free
entropy $\phi_{\mathrm{info}}>\phi_{\mathrm{Bethe}}$, but randomly initialized
AMP–BP does not reach it. This is an algorithmically hard phase where exact
recovery is statistically possible, but the AMP–BP algorithm is sub-optimal.
At the same time the AMP–BP algorithm is conjectured optimal among efficient
algorithms Gamarnik et al. (2022) and thus the hardness of this phase is
believed to be intrinsic. For $\lambda>\lambda_{\rm algo}$ we only find the
exact recovery fixed point.

An exact recovery for the standard SBM is only achievable for graphs of
average degrees $c$ diverging logarithmically with the size of the system Abbe
et al. (2015), where the logarithm comes from a type of coupon collector
problem. The existence of an exact recovery phase in graphs of constant
degrees is novel as far as we know. It nicely illustrates the power of the GLM
prior that is able to induce it. It is well known that a 1st order phase
transition appears for GLM alone with binary weights and known labels Györgyi
(1990); Sompolinsky et al. (1990); Barbier et al. (2019). We note, however,
that in the GLM–SBM the labels are not observed directly but via the graph. It
is thus not a priori clear that an exact recovery phase can appear. Without
our analysis its existence would not be easy to anticipate.

Let us finally derive the values $\alpha_{\mathrm{algo}}$ above which the
exact recovery phase exists. We consider the limit $\lambda=\sqrt{c}$; then
the graph $G$ consists of two disconnected components, one for each community;
and AMP–BP performs as AMP for GLM alone, up to a global sign. We take into
account the proportion $e^{-c}$ of nodes that are isolated and do not bring
information. We obtain that

$\alpha_{\mathrm{algo}}=\alpha_{\mathrm{algo,\,perceptron}}\left(1-e^{-c}\right)^{-1}$
(32)

where $\alpha_{\mathrm{algo,\,perceptron}}\approx 1.493$ is the algorithmic
critical compression ratio of the binary perceptron Barbier et al. (2019).
Similarly the $\lambda_{\rm IT}$ will exist above

$\alpha_{\mathrm{IT}}=\alpha_{\mathrm{IT,\,perceptron}}\left(1-e^{-c}\right)^{-1}$
(33)

where $\alpha_{\mathrm{algo,\,perceptron}}\approx 1.249$ is the information-
theoretic critical threshold of the binary perceptron Györgyi (1990);
Sompolinsky et al. (1990); Barbier et al. (2019).

The 1st order phase transition $\lambda_{\rm IT}$ and its spinodal
$\lambda_{\rm algo}$ are still present in the semi-supervised case $\rho>0$,
for small values of $\rho$, see Fig. 9 in appendix E, contrary to the 2nd
order phase transition to partial recovery that vanishes in the semi-
supervised case. Moreover, for
$\rho>\alpha_{\mathrm{algo,perceptron}}/\alpha$, perfect recovery is achieved
at any $\lambda$, because one has enough train labels to infer $w$.

##  6 Analysis in the dense limit

As in Decelle et al. (2011a, b) for the sparse SBM, the analysis of the AMP–BP
is based on the numerical investigation of the fixed points and their free
entropies on systems large enough that the behavior is representative of the
large-size limit. This is also at the basis of the mathematical difficulty to
establish this prescription rigorously. At the same time, a dense version of
the SBM has been proposed and studied fully rigorously in Lesieur et al.
(2017); Miolane (2017). This rigorous analysis has then been extended to
include the GLM prior in Aubin et al. (2019) that studies a generic instance
of low-rank matrix factorization problem with a generative prior. We hence
study the phenomenology of the AMP–BP algorithm in the limit of large degree
$c$, where it becomes a special case of the framework developed in Aubin et
al. (2019).

The dense limit is defined by taking $p_{i},p_{o}=\mathcal{O}(1)$ and
$p_{i}-p_{o}=\mathcal{O}(1/\sqrt{N})$. SBM is then a low-rank matrix
factorization problem. It is parameterized by its signal-to-noise ratio
$\Delta_{I}$ (which is defined as the inverse variance of an equivalent
additive Gaussian channel). We need $\Delta_{I}$ as a function of the
parameters of the SBM, that is to say to equalize their signal-to-noise
ratios. We compute the Fisher information of the channel $P_{\rm
SBM}(A_{\mu\nu}=1|x_{\mu\nu})=\frac{1}{N}c_{o}+\frac{1}{\sqrt{N}}(c_{i}-c_{o})x_{\mu\nu}$,
where $x_{\mu\nu}=\frac{\delta_{s_{\mu}=s_{\nu}}}{\sqrt{N}}$ is taken to zero.
The mapping is then

$\Delta_{I}=\frac{1}{4}\frac{N(p_{i}-p_{o})^{2}}{p_{o}(1-p_{o})}=\frac{c\lambda^{2}}{c-\sqrt{c}\lambda}+\mathcal{O}\left(\frac{c}{N}\right)$
(34)

where $p_{i}=c_{i}/N$ and $p_{o}=c_{o}/N$. It is of order one in both sparse
case and dense case. Also, we add the factor $1/4$ to obtain a phase
transition at $\Delta_{I}=1$ in the dense case when $\alpha=0$. In the
following $\rho=0$.

Authors of Aubin et al. (2019) give the algorithm corresponding to the dense
case of AMP–BP algorithm. We reproduce it in appendix D. Its performances can
be tracked by a few scalar equations that are named state evolution (SE)
equations. For $P_{w}$ Rademacher they read:

$\displaystyle q_{w}^{t+1}$
$\displaystyle=\mathbb{E}_{\xi}\left[Z_{w}\left(\sqrt{\hat{q}^{t}_{w}}\xi,\hat{q}^{t}_{w}\right)f_{w}\left(\sqrt{\hat{q}^{t}_{w}}\xi,\hat{q}^{t}_{w}\right)^{2}\right]$
(35) $\displaystyle\hat{q}_{w}^{t}$
$\displaystyle=\alpha\mathbb{E}_{\xi,\eta}\left[Z_{o}\left(\sqrt{q^{t}_{s}\Delta_{I}}\xi,q^{t}_{s}\Delta_{I},\sqrt{q^{t}_{w}}\eta,1-q^{t}_{w}\right)f_{o}\left(\sqrt{q^{t}_{s}\Delta_{I}}\xi,q^{t}_{s}\Delta_{I},\sqrt{q^{t}_{w}}\eta,1-q^{t}_{w}\right)^{2}\right]$
(36) $\displaystyle q_{s}^{t+1}$
$\displaystyle=\mathbb{E}_{\xi,\eta}\left[Z_{o}\left(\sqrt{q^{t}_{s}\Delta_{I}}\xi,q^{t}_{s}\Delta_{I},\sqrt{q^{t}_{w}}\eta,1-q^{t}_{w}\right)f_{s}\left(\sqrt{q^{t}_{s}\Delta_{I}}\xi,q^{t}_{s}\Delta_{I},\sqrt{q^{t}_{w}}\eta,1-q^{t}_{w}\right)^{2}\right]$
(37)

where $q_{s}$ and $q_{w}$ are the s- and w-overlaps, $\Delta_{I}$ is the
signal-to-noise ratio of the problem, $\xi$ and $\eta$ are standard Gaussians
and

$\displaystyle Z_{w}(\gamma,\Lambda)$
$\displaystyle=e^{\Lambda/2}\cosh\gamma\quad,\quad
f_{w}(\gamma,\Lambda)=\partial_{\gamma}\log Z_{w}$ (38) $\displaystyle
Z_{o}(B,A,\omega,V)$
$\displaystyle=e^{-A/2}(\cosh(B)+\sinh(B)\mathrm{erf}(\omega/\sqrt{2V}))$ (39)
$\displaystyle f_{o}(B,A,\omega,V)$ $\displaystyle=\partial_{\omega}\log
Z_{o}\quad,\quad f_{s}(B,A,\omega,V)=\partial_{B}\log Z_{o}$ (40)

Aubin et al. (2019) gives also the free entropy of the fixed point of the
algorithm for the dense problem. It reads

$\phi_{\mathrm{Bethe,d}}(q_{s},q_{w},\hat{q}_{w})=-\frac{\Delta_{I}}{4}q_{s}^{2}-\frac{1}{2\alpha}\hat{q}_{w}q_{w}+\psi_{o}(\Delta_{I}q_{s},q_{w})+\frac{1}{\alpha}\psi_{w}(\hat{q}_{w})$
(41)

where

$\displaystyle\psi_{o}(\Delta_{I}q_{s},q_{w})$
$\displaystyle=\mathbb{E}_{\xi,\eta}\,\mathrm{xlogx}\,Z_{o}\left(\sqrt{\Delta_{I}q_{s}}\xi,\Delta_{I}q_{s},\sqrt{q_{w}}\eta,1-q_{w}\right)$
(42) $\displaystyle\psi_{w}(\hat{q}_{w})$
$\displaystyle=\mathbb{E}_{\xi}\,\mathrm{xlogx}\,Z_{w}\left(\sqrt{\hat{q}_{w}}\xi,\hat{q}_{w}\right)$
(43)

xlogx being the function $x\to x\log x$.

The convergence to the dense limit is quite fast; the large degree results are
close to the observed results even for $c$ quite small. Numerically it appears
that $c\approx 20$ is enough ($N=10^{4}$) to already observe quite small
difference, see Fig. 3.

Figure 3:  _Left and right:_ overlap $q_{S}$ and free entropies
$\phi_{\mathrm{Bethe}}-\phi_{\mathrm{info}}$ and
$\phi_{\mathrm{Bethe,d}}-\phi_{\mathrm{info,d}}$ of the fixed point of AMP–BP
and of the SE equations of the dense limit, vs $\Delta_{I}$ for several
average degrees $c$s. We generate instances of GLM–SBM according to the
$\lambda$ obtained by inverting eq. (34). $N=10^{4}$, $\alpha=3$, $P_{w}$
binary. For AMP–BP we run ten experiments per point; for the SE equations one
experiment. The median is plotted and the error bars are the difference
between the 0.85th and 0.15th quantiles. _Insets:_ we plot the median and the
ten data points. We use damping. For SE, the slight decrease of the free
entropy at large $\Delta_{I}$ is due to numerical imprecision.

The fully informative fixed point is
$(q_{s},\hat{q}_{w},q_{w})=(1,+\infty,1)$. Its free entropy is

$\phi_{\mathrm{info,d}}=-\frac{\log 2}{\alpha}+\frac{\Delta_{I}}{4}$ (44)

The analysis of the system of SE equations is done in appendix D; we summarize
the four main points: (a) the fully informative fixed point is stable for all
$\Delta_{I}$; (b) the width of its stability domain shrinks to zero when
$\Delta_{I}$ tends to zero; (c) a general necessary condition to observe a
fully informative fixed point is that $P_{w}$ does not admit everywhere a
twice differentiable density; (d) the algorithmic critical compression ratio
$\alpha_{\mathrm{algo,d}}$ is close to $\alpha_{\mathrm{algo,preceptron}}$.

We also obtain an approximation for the critical point $\lambda_{c}$ of the
transition to partial recovery. Aubin et al. (2019) gives us that in the dense
limit, the critical snr is

$\Delta_{I,c}=\left(1+4\frac{\alpha}{\pi^{2}}\right)^{-1}$ (45)

The limit $c=\omega(1)$ large gives
$\lambda_{c}=\left(1+{4}\alpha/{\pi^{2}}\right)^{-1/2}+\mathcal{O}(c/N)$, as
predicted by the linearization.

##  7 Comparison of performance with standard GNNs on GLM–SBM

GLM–SBM can be used as a benchmark for clustering or classification tasks on
attributed graphs. We compare two simple baselines with AMP–BP. We show that
GLM–SBM is simple to define yet challenging algorithmically, in particular in
the case of binary prior close to the first order phase transition.

##### An unsupervised baseline.

The algorithm is inspired by graph convolution networks; it performs binary
clustering. We compare its performances to the optimal ones given by AMP–BP.
Its performances are shown on Figs. 4 left ($P_{w}$ binary) and 10 left
($P_{w}$ Gaussian, in appendix E).

Data is generated according to the GLM–SBM. We stack the features $F_{\mu l}$
into vectors $F_{\mu}^{(0)}\in\mathbb{R}^{M}$ or a matrix
$F\in\mathbb{R}^{N\times M}$. The observed graph $G$ is used for the
convolution steps.

We compute $n$ steps of graph convolution on the features; perform PCA on the
transformed features and keep the largest component; threshold its left vector
to obtain the membership of each node. Formally, we consider the features
$F_{\mu}^{(0)}\in\mathbb{R}^{M}$; we apply $n$ times

$F_{\mu}^{(t+1)}=F_{\mu}^{(t)}+a\sum_{\nu\in\partial\mu}F_{\nu}^{(t)}$ (46)

where $a$ is a scalar. We apply PCA on the new matrix $\hat{F}$ whose rows are
$F_{\mu}^{(n)}$. Writing $u\in\mathbb{R}^{N}$ the left vector of its largest
component, the estimator is $\hat{s}=\mathrm{sign}(u)$. We tune $n$ and $a$
empirically to optimize the recovery. We observe that roughly it depends on
$n$ and $a$ only by their product $an$. Also, the optimal $a$ scales like
$1/c$.

Figure 4:  Overlap $q_{S}$ of the baseline algorithms, vs $\lambda$. We
compare to the overlap obtained by AMP–BP. _Left:_ unsupervised; for the
parameters of the graph convolution we choose $a=0.1$ and $n=4$. _Right:_
semi-supervised; for the hyperparameters of the GNN we choose $n=2$,
$N_{\mathrm{hidden}}=20$, learning rate $3.10^{-4}$ and L2 penalty $10^{-3}$.
The train set is $\rho=1/10^{\mathrm{th}}$ of the nodes. $N=10^{4}$, $c=5$,
$P_{w}$ binary. We run ten experiments per point.

##### A semi-supervised baseline.

The algorithm is a simple GNN, trained in a semi-supervised way for node
classification.

Again data is generated according to the GLM–SBM, with $\rho=1/10$. We stack
the features $F_{\mu l}$ into vectors $F_{\mu}^{(0)}\in\mathbb{R}^{M}$. We use
the observed graph $G$ for the message-passing steps.

The GNN is made of a two-layer perceptron and a readout layer for the binary
classification. It reads:

$F_{\mu}^{(t+1)}=F_{\mu}^{(t)}+B\,\mathrm{relu}\left(A\sum_{\nu\in\partial\mu}F_{\nu}^{(t)}\right)\quad,\quad\hat{s}_{\mu}=w^{T}F_{\mu}^{(n)}$
(47)

where $A$ is $N_{\mathrm{hidden}}\times M$ learnable, $B$ is $M\times
N_{\mathrm{hidden}}$ learnable, $w\in\mathbb{R}^{M}$ learnable and $n$ is the
number of steps. We train it given the labels of the subset of nodes $\Xi$. We
use gradient descent with logistic loss, momentum and L2 regularization. We do
not fine-tune the hyperparameters. Its performances are shown on Figs. 4 right
($P_{w}$ binary) and 10 right ($P_{w}$ Gaussian, in appendix E).

We also performed experiments where the GNN is made of a single-layer
perceptron (no relu), as Cheng et al. (2022) does on CSBM. The performances
are similar to the multi-layer perceptron, but it requires much more
parameters to be trained ($M^{2}$ vs $MN_{\mathrm{hidden}}$, and we take
$N_{\mathrm{hidden}}=\mathcal{O}(1)$).

##### Conclusion on the comparison.

As to the GLM–SBM dataset, Fig. 4 illustrates that, both in the unsupervised
and the semi-supervised settings, the baseline methods have a considerable gap
to the optimal performances given by the AMP–BP algorithm. The GLM–SBM setting
is hence suitable to develop GNN algorithms that are able to provide higher
accuracy.

As to the AMP–BP algorithm, it is very scalable. It has a running time similar
to the GNN-based approaches, around a few minutes per point on Figs. 1 or 2
(including the ten experiments). Its complexity is $\mathcal{O}(NM)$ in time
and in memory. This is the smallest any algorithm can do, for reading the
input. The number of steps needed for convergence does not depend on $N$.

##  8 Conclusions

We propose a model of attributed graphs. It is a sparse SBM where the nodes
carry features that determine their community memberships. We solve it, in the
sense that we derive an algorithm that is conjectured to perform optimally
among polynomial algorithms. We analyze a linearization of the algorithm and
the dense limit of the model. The model, yet simple, exhibits a rich
phenomenology with detectable and exact recovery phase transitions. It can be
used as a challenging benchmark for graph-neural networks.

In the analysis of this paper we only considered two groups. For more than two
groups, $q>2$, the analysis can also be done by writing an AMP–BP algorithm;
just, the AMP-side would need to correspond to a single-layer network with
multi-class output. The AMP for such a model has been written and studied in
Cornacchia et al. (2022) and one would have to merge it with the BP of Decelle
et al. (2011a). Another generalization that would be possible to analyze is
when the attributes $F$ are drawn from a Gaussian with a generic covariance.
This can be done along the lines of Loureiro et al. (2021). On the other hand
considering as a prior the multi-layer neural network (2) with learned weights
$W$ would be more challenging; a corresponding AMP algorithm that would
provide an asymptotically exact solution is not known.

A future direction of work could also be to theoretically analyze the learning
of GLM–SBM by a GNN, i.e. to give insights on the generalization performance
of the neural network of part 7; as Cheng et al. (2022) does for a perceptron-
based graph convolution network on CSBM. This would be interesting because few
theoretical works address the generalization ability of GNNs.

Acknowledgments and Disclosure of Funding

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

##  Appendix A Derivation of the algorithm

We write belief propagation for this problem. We start with the factor graph.
It contains six different messages:

$\textstyle{w_{l}}$$\scriptstyle{\chi_{w}^{l\to\mu}}$$\scriptstyle{\psi_{s}^{\mu\to\mu}}$$\textstyle{s_{\mu}}$$\scriptstyle{\chi_{s}^{\mu\to\nu}}$$\scriptstyle{\psi_{s}^{\mu\to\nu}}$$\textstyle{w_{m}}$$\scriptstyle{\psi_{w}^{\nu\to
m}}$$\scriptstyle{\chi_{s}^{\nu\to\nu}}$$\textstyle{s_{\nu}}$

These messages satisfy these equations:

$\displaystyle\chi_{w_{l}}^{l\to\mu}$ $\displaystyle\propto
P_{w}(w_{l})\prod_{\nu\neq\mu}\psi_{w_{l}}^{\nu\to l}$ (48)
$\displaystyle\psi_{w_{l}}^{\nu\to l}$
$\displaystyle\propto\sum_{s_{\nu}}\chi_{s_{\nu}}^{\nu\to\nu}\int\prod_{m\neq
l}\left(\mathrm{d}w_{m}\chi_{w_{m}}^{m\to\nu}\right)P_{0}(s_{\nu}|F_{\nu}.w)$
(49) $\displaystyle\psi_{s_{\nu}}^{\nu\to\nu}$
$\displaystyle\propto\int\prod_{m}\left(\mathrm{d}w_{m}\chi_{w_{m}}^{m\to\nu}\right)P_{0}(s_{\nu}|F_{\nu}.w)$
(50) $\displaystyle\chi_{s_{\mu}}^{\mu\to\mu}$ $\displaystyle\propto
P_{s,\mu}(s_{\mu})\prod_{\nu\neq\mu}\psi_{s_{\mu}}^{\nu\to\mu}$ (51)
$\displaystyle\chi_{s_{\mu}}^{\mu\to\nu}$ $\displaystyle\propto
P_{s,\mu}(s_{\mu})\psi_{s_{\mu}}^{\mu\to\mu}\prod_{\eta\neq\mu,\nu}\psi_{s_{\mu}}^{\eta\to\mu}$
(52) $\displaystyle\psi_{s_{\nu}}^{\mu\to\nu}$
$\displaystyle\propto\sum_{s_{\mu}}\chi_{s_{\mu}}^{\mu\to\nu}P_{\rm
SBM}(A_{\mu\nu}|s_{\mu},s_{\nu})$ (53)

We can plug $\psi$ messages into the $\chi$ to obtain, for the GLM part:

$\chi_{w_{l}}^{l\to\mu}=\frac{P_{w}(w_{l})}{Z^{l\to\mu}}\prod_{\nu\neq\mu}\left[\sum_{s_{\nu}}\chi_{s_{\nu}}^{\nu\to\nu}\int\prod_{m\neq
l}\left(\mathrm{d}w_{m}\chi_{w_{m}}^{m\to\nu}\right)P_{0}(s_{\nu}|F_{\nu}.w)\right]\
$ (54)

the marginals

$\chi_{w_{l}}^{l}=\frac{P_{w}(w_{l})}{Z^{l}}\prod_{\nu}\left[\sum_{s_{\nu}}\chi_{s_{\nu}}^{\nu\to\nu}\int\prod_{m\neq
l}\left(\mathrm{d}w_{m}\chi_{w_{m}}^{m\to\nu}\right)P_{0}(s_{\nu}|F_{\nu}.w)\right]\
$ (55)

where the $Z$s are normalization factors; and for the SBM part:

$\chi_{s_{\mu}}^{\mu\to\nu}\propto
P_{s,\mu}(s_{\mu})\psi_{s_{\mu}}^{\mu\to\mu}\prod_{\eta\neq\mu,\nu}\sum_{s_{\eta}}\chi_{s_{\eta}}^{\eta\to\mu}P_{\rm
SBM}(A_{\mu\eta}|s_{\mu},s_{\eta})$ (56)

the marginals

$\chi_{s_{\mu}}^{\mu}\propto
P_{s,\mu}(s_{\mu})\psi_{s_{\mu}}^{\mu\to\mu}\prod_{\eta\neq\mu}\sum_{s_{\eta}}\chi_{s_{\eta}}^{\eta\to\mu}P_{\rm
SBM}(A_{\mu\eta}|s_{\mu},s_{\eta})$ (57)

and

$\chi_{s_{\mu}}^{\mu\to\mu}\propto
P_{s,\mu}(s_{\mu})\prod_{\nu\neq\mu}\sum_{s_{\nu}}\chi_{s_{\nu}}^{\nu\to\mu}P_{\rm
SBM}(A_{\mu\nu}|s_{\mu},s_{\nu})$ (58)

###  A.1 SBM

We can apply the standard simplifications for sparse SBM Decelle et al.
(2011b), Zdeborová and Krzakala (2016). We consider only messages on $G$. This
gives

$\displaystyle\chi_{s_{\mu}}^{\mu\to\mu}$
$\displaystyle=\frac{1}{Z^{\mu\to\mu}}P_{s,\mu}(s_{\mu})e^{-h_{s_{\mu}}}\prod_{\eta\in\partial\mu}\sum_{s_{\eta}}c_{s_{\eta},s_{\mu}}\chi_{s_{\eta}}^{\eta\to\mu}$
(59) $\displaystyle\chi_{s_{\mu}}^{\mu\to\nu}$
$\displaystyle=\frac{1}{Z^{\mu\to\nu}}P_{s,\mu}(s_{\mu})\psi_{s_{\mu}}^{\mu\to\mu}e^{-h_{s_{\mu}}}\prod_{\eta\in\partial\mu\backslash\nu}\sum_{s_{\eta}}c_{s_{\eta},s_{\mu}}\chi_{s_{\eta}}^{\eta\to\mu}$
(60)

and the marginals

$\chi_{s_{\mu}}^{\mu}=\frac{1}{Z^{\mu}}P_{s,\mu}(s_{\mu})\psi_{s_{\mu}}^{\mu\to\mu}e^{-h_{s_{\mu}}}\prod_{\eta\in\partial\mu}\sum_{s_{\eta}}c_{s_{\eta},s_{\mu}}\chi_{s_{\eta}}^{\eta\to\mu}$
(61)

where
$h_{s}=\frac{1}{N}\sum_{\mu}\sum_{s_{\mu}}c_{s,s_{\mu}}\chi_{s_{\mu}}^{\mu}$.

###  A.2 GLM

For the GLM, we follow closely Zdeborová and Krzakala (2016).

####  A.2.1 r-BP

We apply first the simplifications that lead to r-BP. We define and consider
the inner part of the $\chi_{w_{l}}^{l\to\mu}$ message:

$\tilde{\psi}_{w_{l}}^{\nu\to
l}=\sum_{s_{\nu}}\chi_{s_{\nu}}^{\nu\to\nu}\int\prod_{m\neq
l}\left(\mathrm{d}w_{m}\chi_{w_{m}}^{m\to\nu}\right)P_{0}(s_{\nu}|F_{\nu}.w)$
(62)

We set $z_{\nu}=F_{\nu l}w_{l}+\sum_{m\neq l}F_{\nu m}w_{m}$. By independence
of the $w$ the partial sum behaves like a Gaussian with mean and variance

$\omega_{\nu\to l}=\sum_{m\neq l}F_{\nu m}a_{m\to\nu}\quad,\quad V_{\nu\to
l}=\sum_{m\neq l}F^{2}_{\nu m}v_{m\to\nu}$ (63)

with

$a_{m\to\nu}=\int\mathrm{d}w_{m}\chi_{w_{m}}^{m\to\nu}w_{m}\quad
v_{m\to\nu}=\int\mathrm{d}w_{m}\chi_{w_{m}}^{m\to\nu}w^{2}_{m}-a_{m\to\nu}^{2}$
(64)

We replace the integral over all $w$s by a Gaussian integral over $z_{\nu}$;
we obtain

$\tilde{\psi}_{w_{l}}^{\nu\to
l}=\sum_{s_{\nu}}\chi_{s_{\nu}}^{\nu\to\nu}\int\frac{\mathrm{d}z_{\nu}}{\sqrt{2\pi
V_{\nu\to l}}}e^{-(z_{\nu}-F_{\nu l}w_{l}-\omega_{\nu\to l})^{2}/2V_{\nu\to
l}}P_{0}(s_{\nu}|z_{\nu})$ (65)

We can simplify. $F_{\nu l}$ is small, we expand the exponential:

$e^{-\frac{(z_{\nu}-F_{\nu l}w_{l}-\omega_{\nu\to l})^{2}}{2V_{\nu\to
l}}}=e^{-\frac{(z_{\nu}-\omega_{\nu\to l})^{2}}{2V_{\nu\to
l}}}\left(1-\frac{F_{\nu l}^{2}w_{l}^{2}}{2V_{\nu\to
l}}+\frac{(z_{\nu}-\omega_{\nu\to l})F_{\nu l}w_{l}}{V_{\nu\to
l}}+\frac{(z_{\nu}-\omega_{\nu\to l})^{2}F_{\nu l}^{2}w_{l}^{2}}{2V_{\nu\to
l}^{2}}\right)$ (66)

We introduce the denoising function; its expression differs from the one of
Zdeborová and Krzakala (2016):

$g_{o}(\omega,\chi,V)=\frac{\int\mathrm{d}z\sum_{s}\chi_{s}P_{0}(s|z)(z-\omega)e^{-(z-\omega)^{2}/2V}}{V\int\mathrm{d}z\sum_{s}\chi_{s}P_{0}(s|z)e^{-(z-\omega)^{2}/2V}}$
(67)

So

$\tilde{\psi}_{w_{l}}^{\nu\to l}\propto\left(1-\frac{F_{\nu
l}^{2}w_{l}^{2}}{2V_{\nu\to l}}+g_{o}F_{\nu
l}w_{l}+\frac{1}{2}(\frac{1}{V_{\nu\to
l}}+\partial_{\omega}g_{o}+g_{o}^{2})F_{\nu l}^{2}w_{l}^{2}\right)$ (68)

where we evaluate $g_{o}$ in $(\omega_{\nu\to l},\chi^{\nu\to\nu},V_{\nu\to
l})$. We exponentiate:

$\tilde{\psi}_{w_{l}}^{\nu\to l}\propto e^{g_{o}F_{\nu
l}w_{l}+\frac{1}{2}\partial_{\omega}g_{o}F_{\nu l}^{2}w_{l}^{2}}$ (69)

We take the product of the $\tilde{\psi}$ to obtain

$\chi_{w_{l}}^{l\to\mu}\propto
P_{w}(w_{l})e^{-\Lambda_{l\to\mu}w_{l}^{2}/2+\Gamma_{l\to\mu}w_{l}}$ (70)

where

$\Lambda_{l\to\mu}=-\sum_{\nu\neq\mu}\partial_{\omega}g_{o}(\omega_{\nu\to
l},\chi^{\nu\to\nu},V_{\nu\to l})F^{2}_{\nu
l}\quad,\quad\Gamma_{l\to\mu}=\sum_{\nu\neq\mu}g_{o}(\omega_{\nu\to
l},\chi^{\nu\to\nu},V_{\nu\to l})F_{\nu l}$ (71)

We close the loop defining the input functions

$f_{a}(\Lambda,\Gamma)=\frac{\int\mathrm{d}w\,P_{w}(w)we^{-\Lambda
w^{2}/2+\Gamma w}}{\int\mathrm{d}wP_{w}(w)e^{-\Lambda w^{2}/2+\Gamma
w}}\quad,\quad f_{v}(\Lambda,\Gamma)=\partial_{\Gamma}f_{a}(\Lambda,\Gamma)$
(72)

so

$a_{l\to\mu}=f_{a}(\Gamma_{l\to\mu},\Lambda_{l\to\mu})\quad,\quad
v_{l\to\mu}=f_{v}(\Gamma_{l\to\mu},\Lambda_{l\to\mu})$ (73)

The mean and the variance of the marginals are estimated by

$a_{l}=f_{a}(\Gamma_{l},\Lambda_{l})\quad,\quad
v_{l}=f_{v}(\Gamma_{l},\Lambda_{l})$ (74)

where

$\Lambda_{l}=-\sum_{\nu}\partial_{\omega}g_{o}(\omega_{\nu\to
l},\chi^{\nu\to\nu},V_{\nu\to l})F^{2}_{\nu
l}\quad,\quad\Gamma_{l}=\sum_{\nu}g_{o}(\omega_{\nu\to
l},\chi^{\nu\to\nu},V_{\nu\to l})F_{\nu l}$ (75)

We obtain also the expression of the GLM-to-SBM message

$\psi_{s_{\mu}}^{\mu\to\mu}=\frac{1}{\sqrt{2\pi
V_{\mu}}}\int\mathrm{d}zP_{0}(s_{\mu}|z)e^{-(z-\omega_{\mu})^{2}/2V_{\mu}}$
(76)

where

$\omega_{\mu}=\sum_{m}F_{\mu m}a_{m\to\mu}\quad,\quad
V_{\mu}=\sum_{m}F^{2}_{\mu m}v_{m\to\mu}$ (77)

####  A.2.2 Time indices

There are two possibilities for mixing the GLM part and the SBM part:

$\textstyle{a,v^{(t)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\omega,V^{(t+1)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\Gamma,\Lambda^{(t+1)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{a,v^{(t+1)}}$$\textstyle{\psi^{(t+1)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{g_{o}^{(t+1)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\chi^{(t)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\chi^{(t+1)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$

or

$\textstyle{a,v^{(t)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\omega,V^{(t+1)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\Gamma,\Lambda^{(t+1)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{a,v^{(t+1)}}$$\textstyle{\psi^{(t+1)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{g_{o}^{(t+1)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\chi^{(t)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\chi^{(t+1)}}$

We try both; we do not observe any numerical difference.

####  A.2.3 AMP

Then we go from r-BP to AMP. We remove the dependence of the messages on the
target. We keep only the marginals. The derivation is given by Zdeborová and
Krzakala (2016). We obtain that

$\displaystyle V^{(t+1)}_{\mu}$ $\displaystyle=\sum_{l}F_{\mu
m}^{2}v_{l}^{(t)}$ (78) $\displaystyle\omega_{\mu}^{(t+1)}$
$\displaystyle=\sum_{l}F_{\mu l}a_{l}^{(t)}-V^{(t+1)}_{\mu}g_{o,\mu}^{(t)}$
(79) $\displaystyle g_{o,\mu}^{(t+1)}$
$\displaystyle=g_{o}(\omega_{\mu}^{(t+1)},\chi^{\mu\to\mu,(t)},V_{\mu}^{(t+1)})$
(80) $\displaystyle\Lambda^{(t+1)}_{l}$ $\displaystyle=-\sum_{\mu}F_{\mu
l}^{2}\partial_{\omega}g_{o}(\omega_{\mu}^{(t+1)},\chi^{\mu\to\mu,(t)},V^{(t+1)}_{\mu})$
(81) $\displaystyle\Gamma_{l}^{(t+1)}$
$\displaystyle=\Lambda^{(t+1)}_{l}a_{l}^{(t)}+\sum_{\mu}F_{\mu
l}g_{o,\mu}^{(t+1)}$ (82)

####  A.2.4 Further simplifications

$F_{\mu m}^{2}$ self-averages. We can replace it by its average $1/M$ in eqs.
(78) and (81). So $\Lambda$ and $V$ become scalars. Also, on average,
$-\partial_{\omega}g_{o,\mu}=g_{o,\mu}^{2}$. We obtain the algorithm given in
the main part.

##  Appendix B Free entropy

We start with the factor graph. The Bethe free entropy is the sum of the free
entropies of the nodes plus the factors minus the edges i.e.

$\displaystyle N\phi_{\mathrm{Bethe}}$
$\displaystyle=\sum_{\mu}\phi^{\mu}+\sum_{l}\phi^{l}+\sum_{\mu<\nu}\phi^{\mu\nu}+\sum_{\mu}\phi^{\mu\mu}$
$\displaystyle\quad{}-\sum_{\mu\neq\nu}\phi^{\mu\to\nu}-\sum_{\mu}\phi^{\mu\to\mu}-\sum_{l,\mu}\phi^{l\to\mu}$

where

$\displaystyle\phi^{\mu}$
$\displaystyle=\log\sum_{s_{\mu}}P_{s,\mu}(s_{\mu})\psi_{s_{\mu}}^{\mu\to\mu}\prod_{\nu\neq\mu}\psi_{s_{\mu}}^{\nu\to\mu}=\log
Z^{\mu}\prod_{\nu\neq\mu}\frac{1}{Z^{\nu\to\mu}_{\psi}}$ (83)
$\displaystyle\phi^{l}$
$\displaystyle=\log\int\mathrm{d}w_{l}\,P_{w}(w_{l})\prod_{\mu}\psi_{w_{l}}^{\mu\to
l}=\log Z^{l}\prod_{\mu}\frac{1}{Z^{\mu\to l}_{\psi}}$ (84)
$\displaystyle\phi^{\mu\nu}$
$\displaystyle=\log\sum_{s_{\mu},s_{\nu}}\chi_{s_{\mu}}^{\mu\to\nu}\chi_{s_{\nu}}^{\nu\to\mu}P(A_{\mu\nu}|s_{\mu},s_{\nu})$
(85) $\displaystyle\phi^{\mu\mu}$
$\displaystyle=\log\sum_{s_{\mu}}\int\prod_{m}\left(\mathrm{d}w_{m}\chi_{w_{m}}^{m\to\mu}\right)\chi_{s_{\mu}}^{\mu\to\mu}P_{0}(s_{\mu}|F_{\mu}.w)$
(86) $\displaystyle\phi^{\mu\to\nu}$
$\displaystyle=\log\sum_{s_{\mu}}\chi_{s_{\mu}}^{\mu\to\nu}\psi_{s_{\mu}}^{\nu\to\mu}=\log\frac{1}{Z_{\psi}^{\nu\to\mu}}+\phi^{\mu\nu}$
(87) $\displaystyle\phi^{\mu\to\mu}$
$\displaystyle=\log\sum_{s_{\mu}}\chi_{s_{\mu}}^{\mu\to\mu}\psi_{s_{\mu}}^{\mu\to\mu}=\log\frac{1}{Z^{\mu\to\mu}}+\phi^{\mu}$
(88) $\displaystyle\phi^{l\to\mu}$
$\displaystyle=\log\int\mathrm{d}w_{l}\chi_{w_{l}}^{l\to\mu}\,\psi_{w_{l}}^{\mu\to
l}=\log\frac{1}{Z_{\psi}^{\mu\to l}}+\phi^{\mu\mu}$ (89)

This simplifies to

$\displaystyle N\phi_{\mathrm{Bethe}}$ $\displaystyle=\sum_{\mu}\log
Z^{\mu\to\mu}+\sum_{l}\log
Z^{l}-\sum_{\mu<\nu}\phi^{\mu\nu}+(1-M)\sum_{\mu}\phi^{\mu\mu}$ (90)

On the SBM side, we have Zdeborová and Krzakala (2016)

$\displaystyle Z^{\mu\to\mu}$
$\displaystyle=\sum_{s_{\mu}}P_{s,\mu}(s_{\mu})e^{-h_{s_{\mu}}}\prod_{\eta\in\partial\mu}\sum_{s_{\eta}}c_{s_{\eta},s_{\mu}}\chi_{s_{\eta}}^{\eta\to\mu}$
(91) $\displaystyle\sum_{\mu<\nu}\phi^{\mu\nu}$
$\displaystyle=\sum_{(\mu\nu)\in
G}\log\sum_{s_{\mu},s_{\nu}}c_{s_{\mu},s_{\nu}}\chi_{s_{\mu}}^{\mu\to\nu}\chi_{s_{\nu}}^{\nu\to\mu}-N\frac{c}{2}$
(92)

On the GLM side, we have

$\displaystyle\phi^{\mu\mu}$
$\displaystyle=\log\int\frac{\mathrm{d}z_{\mu}}{\sqrt{2\pi
V_{\mu}}}\,\sum_{s_{\mu}}\chi_{s_{\mu}}^{\mu\to\mu}P_{o}(s_{\mu}|z_{\mu})e^{-(z_{\mu}-\omega_{\mu})^{2}/2V_{\mu}}$
(93) $\displaystyle\log Z^{l}$ $\displaystyle=\sum_{\mu}\log\hat{Z}^{\mu\to
l}+\log\int\mathrm{d}w_{l}P_{w}(w_{l})e^{-\Lambda_{l}w_{l}^{2}/2+\Gamma_{l}w_{l}}$
(94)

We compute $\log\hat{Z}^{\mu\to l}$ as a function of the target-free elements
(we start using that $\omega_{\mu\to l}=\omega_{\mu}-F_{\mu l}a_{l\to\mu}$ and
$V_{\mu\to l}=V_{\mu}-F_{\mu l}^{2}v_{l\to\mu}$ and expanding). This gives:

$\displaystyle\sum_{l,\mu}\log\hat{Z}^{\mu\to l}$
$\displaystyle=M\sum_{\mu}\phi^{\mu\mu}+\sum_{l}\frac{\Lambda_{l}}{2}(a_{l}^{2}+v_{l})-\Gamma_{l}a_{l}+\sum_{\mu}\frac{(\omega_{\mu}-\sum_{l}F_{\mu
l}a_{l})^{2}}{2V_{\mu}}$ (95)

which is what Krzakala et al. (2014) gives (taking $\Sigma_{l}=1/\Lambda_{l}$
and $R_{l}=\Gamma_{l}/\Lambda_{l}$). Finally, we obtain that the free entropy
$\phi$ is exactly the sum of the free entropies of the two sub-problems:

$\displaystyle\phi_{\mathrm{Bethe}}$
$\displaystyle=\phi_{\mathrm{SBM}}+\phi_{\mathrm{GLM}}$ (96)
$\displaystyle\phi_{\mathrm{SBM}}$
$\displaystyle=\frac{1}{N}\sum_{\mu}\log\sum_{s_{\mu}}P_{s,\mu}(s_{\mu})e^{-h_{s_{\mu}}}\prod_{\eta\in\partial\mu}\sum_{s_{\eta}}c_{s_{\eta},s_{\mu}}\chi_{s_{\eta}}^{\eta\to\mu}$
$\displaystyle\quad{}-\frac{1}{N}\sum_{(\mu\nu)\in
G}\log\sum_{s_{\mu},s_{\nu}}c_{s_{\mu},s_{\nu}}\chi_{s_{\mu}}^{\mu\to\nu}\chi_{s_{\nu}}^{\nu\to\mu}+\frac{c}{2}$
(97) $\displaystyle\phi_{\mathrm{GLM}}$
$\displaystyle=\frac{1}{N}\sum_{\mu}\log\int\frac{\mathrm{d}z_{\mu}}{\sqrt{2\pi
V_{\mu}}}\,\sum_{s_{\mu}}\chi_{s_{\mu}}^{\mu\to\mu}P_{o}(s_{\mu}|z_{\mu})e^{-(z_{\mu}-\omega_{\mu})^{2}/2V_{\mu}}$
$\displaystyle\quad{}+\frac{1}{N}\sum_{l}\log\int\mathrm{d}w_{l}P_{w}(w_{l})e^{-\Lambda_{l}w_{l}^{2}/2+\Gamma_{l}w_{l}}$
$\displaystyle\quad{}+\frac{1}{N}\left(\sum_{l}\frac{\Lambda_{l}}{2}(a_{l}^{2}+v_{l})-\Gamma_{l}a_{l}+\sum_{\mu}\frac{(\omega_{\mu}-\sum_{l}F_{\mu
l}a_{l})^{2}}{2V_{\mu}}\right)$ (98)

##  Appendix C Linearization and partial recovery threshold

We take $P_{s,\mu}(s)=1/2$. The non-informative point $q_{S}=q_{W}=0$ is a
fixed point of the AMP–BP algorithm. At this point, we have
$\chi^{\mu\to\nu}=\frac{1}{2}$, $\chi^{\mu\to\mu}=\frac{1}{2}$,
$\chi^{\mu\to\nu}=\frac{1}{2}$, $a_{l}=0$, $v_{l}=1$, $\omega_{\mu}=0$, $V=1$,
$\psi^{\mu\to\mu}=\frac{1}{2}$, $g_{o,\mu}=0$, $\Lambda=0$ and $\Gamma_{l}=0$.

We linearize the equations of the algorithm around this point. We write
$|_{*}$ the evaluation of functions in this point. We have

$\displaystyle\delta\chi^{\mu\to\nu,(t+1)}$
$\displaystyle=\sum_{\eta\in\partial\mu\backslash\nu}\frac{1}{2}\left(\frac{c_{.,.}}{c}-1\right)\delta\chi^{\eta\to\mu,(t)}+\partial_{\omega}\psi^{\mu\to\mu}|_{*}\delta\omega_{\mu}^{(t+1)}+\partial_{V}\psi^{\mu\to\mu}|_{*}\delta
V^{(t+1)}$ (99) $\displaystyle\delta\chi^{\mu\to\mu,(t+1)}$
$\displaystyle=\sum_{\eta\in\partial\mu}\frac{1}{2}\left(\frac{c_{.,.}}{c}-1\right)\delta\chi^{\eta\to\mu,(t)}$
(100) $\displaystyle\delta a_{l}^{(t+1)}$
$\displaystyle=\partial_{\Lambda}f_{a}|_{*}\delta\Lambda^{(t+1)}+\partial_{\Gamma}f_{a}|_{*}\delta\Gamma_{l}^{(t+1)}$
(101) $\displaystyle\delta v_{l}^{(t+1)}$
$\displaystyle=\partial_{\Lambda\Gamma}f_{a}|_{*}\delta\Lambda^{(t+1)}+\partial_{\Gamma\Gamma}f_{a}|_{*}\delta\Gamma_{l}^{(t+1)}$
(102) $\displaystyle\delta g_{o,\mu}^{(t+1)}$
$\displaystyle=\partial_{\omega}g_{o}|_{*}\delta\omega_{\mu}^{(t+1)}+\nabla_{\chi}g_{o}|_{*}\delta\chi^{\mu\to\mu,(t+1)}+\partial_{V}g_{o}|_{*}\delta
V^{(t+1)}$ (103)

where we write $c_{.,.}$ for the affinity matrix and where we have used the
standard linearization for SBM. We have also

$\displaystyle\delta\omega_{\mu}^{(t+1)}$ $\displaystyle=\sum_{l}F_{\mu
l}\delta a_{l}^{(t)}-\delta V^{(t+1)}g_{o}|_{*}-V|_{*}\delta g_{o,\mu}^{(t)}$
(104) $\displaystyle\delta V^{(t+1)}$ $\displaystyle=\frac{1}{M}\sum_{l}\delta
v_{l}^{(t)}$ (105) $\displaystyle\delta\Lambda^{(t+1)}$
$\displaystyle=\frac{2}{M}\sum_{\mu}g_{o}|_{*}\delta g_{o,\mu}^{(t+1)}$ (106)
$\displaystyle\delta\Gamma_{l}^{(t+1)}$
$\displaystyle=\delta\Lambda^{(t+1)}a_{l}|_{*}+\Lambda|_{*}\delta
a_{l}^{(t)}+\sum_{\mu}F_{\mu l}\delta g_{o,\mu}^{(t+1)}$ (107)

We simplify: $g_{o}|_{*}=0$, $\partial_{\omega}g_{o}|_{*}=0$,
$\partial_{V}g_{o}|_{*}=0$, $\partial_{V}\psi|_{*}=0$ and
$\partial_{\Gamma}f_{a}|_{*}=1$ (for $P_{W}$ both Gaussian or Rademacher). We
compute that
$\partial_{\omega}\psi|_{*}=\frac{1}{\sqrt{2\pi}}\left(\begin{smallmatrix}1\\\
-1\end{smallmatrix}\right)$ and
$\nabla_{\chi}g_{o}|_{*}=\frac{2}{\sqrt{2\pi}}\left(\begin{smallmatrix}1\\\
-1\end{smallmatrix}\right)^{T}$. We assemble equations together:

$\displaystyle\delta\chi^{\mu\to\nu,(t+1)}$
$\displaystyle=\sum_{\eta\in\partial\mu\backslash\nu}\frac{1}{2}\left(\frac{c_{.,.}}{c}-1\right)\delta\chi^{\eta\to\mu,(t)}+\partial_{\omega}\psi|_{*}\left(\sum_{l}F_{\mu
l}\delta a_{l}^{(t)}-\nabla_{\chi}g_{o}|_{*}\delta\chi^{\mu\to\mu,(t)}\right)$
(108) $\displaystyle\delta\chi^{\mu\to\nu,(t+1)}$
$\displaystyle=\sum_{\eta\in\partial\mu\backslash\nu}\frac{1}{2}\left(\frac{c_{.,.}}{c}-1\right)\delta\chi^{\eta\to\mu,(t)}$
$\displaystyle\quad{}+\sum_{\eta,l}F_{\mu l}F_{\eta
l}(\partial_{\omega}\psi|_{*}.\nabla_{\chi}g_{o}|_{*})\delta\chi^{\eta\to\eta,(t)}-(\partial_{\omega}\psi|_{*}\nabla_{\chi}g_{o}|_{*})\delta\chi^{\mu\to\mu,(t)}$
(109) $\displaystyle\delta\chi^{\eta\to\eta,(t)}$
$\displaystyle=\sum_{\rho\in\partial\eta}\frac{1}{2}\left(\frac{c_{.,.}}{c}-1\right)\delta\chi^{\rho\to\eta,(t-1)}$
(110)

The matrices $\frac{1}{2}\left(\frac{c_{.,.}}{c}-1\right)$ and
$\partial_{\omega}\psi|_{*}\nabla_{\chi}g_{o}|_{*}$ share the same
eigenvectors. They have one null eigenvalue and one positive:
$\frac{c_{i}-c_{o}}{2c}=\frac{\lambda}{\sqrt{c}}$ and $\frac{2}{\pi}$. We
project to obtain

$\displaystyle x^{\mu\to\nu,(t+1)}$
$\displaystyle=\frac{\lambda}{\sqrt{c}}\left(\sum_{\eta\in\partial\mu\backslash\nu}x^{\eta\to\mu,(t)}+\frac{2}{\pi}\sum_{\eta}(FF^{T})_{\mu,\eta}\sum_{\rho\in\partial\eta}x^{\rho\to\eta,(t-1)}-\frac{2}{\pi}\sum_{\eta\in\partial\mu}x^{\eta\to\mu,(t-1)}\right)$
(111) $\displaystyle x^{\mu\to\nu,(t+1)}$
$\displaystyle=\frac{\lambda}{\sqrt{c}}\left(\sum_{\eta\in\partial\mu\backslash\nu}x^{\eta\to\mu,(t)}+\frac{2}{\pi}\sum_{\eta}(FF^{T}-I_{N})_{\mu,\eta}\sum_{\rho\in\partial\eta}x^{\rho\to\eta,(t-1)}\right)$
(112)

where $(FF^{T})_{\mu\nu}=\sum_{l}F_{\mu l}F_{\nu l}$.

We obtain the threshold $\lambda_{c}$ of partial recovery taking the variance
of the expression 112, discarding the time indices. We use that
$(FF^{T}-I_{N})^{2}_{\mu,\nu}$ averages to $1/M$ if $\mu\neq\nu$ and to
$\mathcal{O}(1/M)$ otherwise. We obtain:

$\displaystyle 1$
$\displaystyle=\lambda_{c}^{2}\left(1+\frac{4\alpha}{\pi^{2}}\right)$ (113)

##  Appendix D Dense limit

We consider the limit $c$ large. GLM–SBM is equivalent to a low-rank matrix
factorization problem with a generative prior. It has been studied in Aubin et
al. (2019). We follow it closely.

We set $p_{o}=c_{o}/N$ and $p_{i}=c_{i}/N$ of order one and
$\mu=\sqrt{N}(p_{i}-p_{o})$ of order one. The effective inverse noise of the
SBM is Lesieur et al. (2017)

$\Delta_{I}=\frac{\mu^{2}}{p_{o}(1-p_{o})}$ (114)

###  D.1 Algorithm

We reproduce here the algorithm given by Aubin et al. (2019); we simplify it
for a binary output channel and $P_{w}$ Rademacher; and we complete it with
the semi-supervised case. In the dense limit BP can be approximated by AMP and
our algorithm AMP–BP becomes AMP–AMP.

We set, as in part 6:

$\displaystyle Z_{w}(\gamma,\Lambda)$
$\displaystyle=e^{\Lambda/2}\cosh\gamma\quad,\quad
f_{w}(\gamma,\Lambda)=\partial_{\gamma}\log Z_{w}$ (115) $\displaystyle
Z_{o,\mu}(B,A,\omega,V)$ $\displaystyle=\left\\{\begin{array}[]{r c
l}e^{-A/2+s_{\mu}B}\frac{1}{2}(1+s_{\mu}\mathrm{erf}(\omega/\sqrt{2V}))&\mathrm{if}\;s_{\mu}\in
s_{\Xi}\\\
e^{-A/2}(\cosh(B)+\sinh(B)\mathrm{erf}(\omega/\sqrt{2V}))&\mathrm{else}\end{array}\right.$
(118) $\displaystyle f_{o,\mu}(B,A,\omega,V)$
$\displaystyle=\partial_{\omega}\log Z_{o,\mu}\quad,\quad
f_{s,\mu}(B,A,\omega,V)=\partial_{B}\log Z_{o,\mu}$ (119)

We define the input matrix

$S_{\eta\nu}=\mu\frac{1}{1-p_{o}}\left(\frac{Y_{\eta\nu}}{p_{o}}-1\right)$
(120)

where $Y$ is the observed adjacency matrix; $Y_{\eta\nu}=1$ if there is an
edge between $\eta$ and $\nu$, 0 otherwise.

In the following $a_{l}$ and $v_{l}$ are estimators of the mean and the
variance of $w_{l}$; $\sigma_{\mu}$ and $\Sigma_{\mu}$ the mean and the
variance of $s_{\mu}$.

AMP–AMP

0: features $F_{\mu l}$, input matrix $S_{\eta\nu}$, effective inverse noise
$\Delta_{I}$, prior information $P_{s,\mu}$.

Initialize $a_{l}^{(0)}=\epsilon_{l}$, $v_{l}^{(0)}=1$,
$\sigma_{\nu}^{(0)}=\epsilon_{\nu}$, $\Sigma_{\nu}^{(0)}=1$,
$g_{o,\mu}^{(0)}=0$, $t=0$; where $\epsilon$s are zero-mean small random
variables.

repeat

AMP update of $\omega_{\mu},V_{\mu}$ $\displaystyle
V^{(t+1)}\leftarrow\frac{1}{M}\sum_{l}v_{l}^{(t)}$
$\displaystyle\omega_{\mu}^{(t+1)}\leftarrow\sum_{l}F_{\mu
l}a_{l}^{(t)}-V^{(t+1)}g_{o,\mu}^{(t)}$

AMP update of $g_{o,\mu},\Lambda,\Gamma_{l}$ $\displaystyle
g_{o,\mu}^{(t+1)}\leftarrow f_{o,\mu}$
$\displaystyle(B_{\mu}^{(t+1)},A^{(t+1)},$
$\displaystyle\quad\omega_{\mu}^{(t+1)},V^{(t+1)})$
$\displaystyle\Lambda^{(t+1)}\leftarrow\frac{1}{M}\sum_{\mu}g_{o,\mu}^{2,(t+1)}$
$\displaystyle\Gamma_{l}^{(t+1)}\leftarrow\Lambda^{(t+1)}a_{l}^{(t)}+\sum_{\mu}F_{\mu
l}g_{o,\mu}^{(t+1)}$

AMP update of the matrix factorization part  $\displaystyle
A^{(t+1)}\leftarrow$
$\displaystyle\frac{\Delta_{I}}{N}\sum_{\eta}\sigma_{\eta}^{2,(t)}$
$\displaystyle B_{\mu}^{(t+1)}\leftarrow$
$\displaystyle\frac{1}{\sqrt{N}}\sum_{\eta}S_{\mu\eta}\sigma_{\eta}^{(t)}$
$\displaystyle\quad{}-\frac{\Delta_{I}}{N}\sum_{\eta}\Sigma_{\eta}^{(t)}\sigma_{\mu}^{(t-1)}$

AMP update of the estimated marginals $a_{l},v_{l}$ $\displaystyle
a_{l}^{(t+1)}\leftarrow f_{w}(\Lambda^{(t+1)},\Gamma_{l}^{(t+1)})$
$\displaystyle
v_{l}^{(t+1)}\leftarrow\partial_{\Gamma}f_{w}(\Lambda^{(t+1)},\Gamma_{l}^{(t+1)})$

AMP update of the estimated marginals $\sigma_{\nu},\Sigma_{\nu}$
$\displaystyle\sigma_{\mu}^{(t+1)}\leftarrow f_{s,\mu}$
$\displaystyle(B_{\mu}^{(t+1)},A^{(t+1)},$
$\displaystyle\quad\omega_{\mu}^{(t+1)},V^{(t+1)})$
$\displaystyle\Sigma_{\mu}^{(t+1)}\leftarrow\partial_{B}f_{s,\mu}$
$\displaystyle(B_{\mu}^{(t+1)},$
$\displaystyle\;A^{(t+1)},\omega_{\mu}^{(t+1)},V^{(t+1)})$

$t\leftarrow t+1$

until convergence of $a_{l},v_{l},\sigma_{\mu},\Sigma_{\mu}$

estimated mean $a_{l}$ and variance $v_{l}$ of $w_{l}$, estimated mean
$\sigma_{\mu}$ and variance $\Sigma_{\mu}$ of $s_{\mu}$

###  D.2 Analysis of the SE equations near the full recovery point

The state evolution equations are given in section 6, eqs. (35)-(37). We study
the conditions of stability for the fully informative fixed point
$(q_{s},\hat{q}_{w},q_{w})=(1,+\infty,1)$.

We use the following notation for the update:

$(q_{s},\hat{q}_{w},q_{w})^{t+1}=(f_{1}(r,s),f_{2}(r,s),f_{3}(t))\quad,\quad(r,t,s)=(\Delta_{I}q_{s}^{t},\hat{q}_{w}^{t+1},q_{w}^{t})$
(121)

where the $f_{i}$ are given by the SE update equations:

$\displaystyle f_{1}(r,s)$
$\displaystyle=\mathbb{E}_{\xi,\eta}\left[e^{-r/2}\frac{\left(\sinh(\sqrt{r}\xi)+\cosh(\sqrt{r}\xi)\mathrm{erf}\left(\sqrt{\frac{s}{2(1-s)}}\eta\right)\right)^{2}}{\cosh(\sqrt{r}\xi)+\sinh(\sqrt{r}\xi)\mathrm{erf}\left(\sqrt{\frac{s}{2(1-s)}}\eta\right)}\right]$
(122) $\displaystyle f_{2}(r,s)$
$\displaystyle=\alpha\mathbb{E}_{\xi,\eta}\left[e^{-r/2}\frac{\sinh^{2}(\sqrt{r}\xi)\frac{2}{\pi(1-s)}e^{-\eta^{2}\frac{s}{1-s}}}{\cosh(\sqrt{r}\xi)+\sinh(\sqrt{r}\xi)\mathrm{erf}\left(\sqrt{\frac{s}{2(1-s)}}\eta\right)}\right]$
(123) $\displaystyle f_{3}(t)$
$\displaystyle=\mathbb{E}_{\xi}\left[e^{-t/2}\sinh(\sqrt{t}\xi)\tanh(\sqrt{t}\xi)\right]$
(124)

where $\xi$ and $\eta$ are standard Gaussians.

We expand around $(1,+\infty,1)$; we use the parametrization
$(r,t,s)=(\Delta_{I}+\epsilon_{r},1/\epsilon_{t}^{2},1-\epsilon_{s}^{2})$.

##### – $f_{3}$ –

We expand the integrand in $f_{3}$ around $+\infty$. This is valid only for
$\sqrt{t}\xi=\xi/\epsilon_{t}\gg 1$; so we introduce a cut-off $\delta$ such
that both $\delta=o(1)$ and $\delta=\omega(\epsilon_{t})$. For $\xi>\delta$ we
use the asymptotic
$\sinh(x)\tanh(x)=\frac{1}{2}e^{x}-\frac{3}{2}e^{-x}+o(e^{-x})$; for
$\xi<\delta$ we develop the Gaussian density to the first (constant) order.
Then

$\displaystyle f_{3}(1/\epsilon_{t}^{2})$
$\displaystyle=e^{-1/2\epsilon_{t}^{2}}\,2\left(\int_{0}^{\infty}\frac{\mathrm{d}\xi}{\sqrt{2\pi}}\,e^{-\xi^{2}/2}\left(\frac{1}{2}e^{\xi/\epsilon_{t}}-\frac{3}{2}e^{-\xi/\epsilon_{t}}\right)-\int_{0}^{\delta}\frac{\mathrm{d}\xi}{\sqrt{2\pi}}\,\left(\frac{1}{2}e^{\xi/\epsilon_{t}}-\frac{3}{2}e^{-\xi/\epsilon_{t}}\right)\right)$
$\displaystyle\quad{}+e^{-1/2\epsilon_{t}^{2}}\,2\int_{0}^{\delta}\frac{\mathrm{d}\xi}{\sqrt{2\pi}}\,\sinh(\xi/\epsilon_{t})\tanh(\xi/\epsilon_{t})$
(125)
$\displaystyle=\frac{1}{2}\left(1+\mathrm{erf}\left(\frac{1}{\sqrt{2}\epsilon_{t}}\right)\right)-\frac{3}{2}\left(1-\mathrm{erf}\left(\frac{1}{\sqrt{2}\epsilon_{t}}\right)\right)$
$\displaystyle\quad{}-2e^{-1/2\epsilon_{t}^{2}}\epsilon_{t}\int_{0}^{\delta/\epsilon_{t}}\frac{\mathrm{d}\xi}{\sqrt{2\pi}}\,\left(\frac{1}{2}e^{\xi}-\frac{3}{2}e^{-\xi}\right)+2e^{-1/2\epsilon_{t}^{2}}\epsilon_{t}\int_{0}^{\delta/\epsilon_{t}}\frac{\mathrm{d}\xi}{\sqrt{2\pi}}\,\sinh(\xi)\tanh(\xi)$
(126) $\displaystyle=1-C_{3}\epsilon_{t}e^{-1/2\epsilon_{t}^{2}}$ (127)
$\displaystyle\quad\quad
C_{3}=2\left(\sqrt{\frac{2}{\pi}}+\int_{0}^{\infty}\frac{\mathrm{d}\xi}{\sqrt{2\pi}}\,\left(\frac{1}{2}e^{\xi}-\frac{3}{2}e^{-\xi}-\sinh(\xi)\tanh(\xi)\right)\right)\approx
1.3$ (128)

where in the last lines we expanded the error function around $+\infty$.

##### – $f_{1}$ –

We use the shorthand notation

$\displaystyle g(x,y)$
$\displaystyle=\frac{\left(\sinh(x)+\cosh(x)\,\mathrm{erf}(y)\right)^{2}}{\cosh(x)+\sinh(x)\,\mathrm{erf}(y)}$
(129) $\displaystyle f_{1}(r,s)$
$\displaystyle=\mathbb{E}_{\xi,\eta}\left[e^{-r/2}g\left(\sqrt{r}\xi,\eta\sqrt{\frac{s}{2(1-s)}}\right)\right]$
(130)

Expanding the function is difficult: we can obtain quite easily that

$f_{1}(\Delta_{I}+\epsilon_{r},1-\epsilon_{s}^{2})=1-C_{1}(\Delta_{I})\epsilon_{s}+\mathcal{O}(\epsilon_{r}\epsilon_{s},\ldots)$
(131)

but the function $C_{1}(\Delta_{I})$ is harder to obtain. Rather we compute
directly the derivative to the constant order:

$\displaystyle\partial_{\epsilon_{s}}f_{1}(\Delta_{I}+\epsilon_{r},1-\epsilon_{s}^{2})$
$\displaystyle=-C_{1}(\Delta_{I})$ (132)
$\displaystyle=\mathbb{E}_{\xi,\eta}\left[e^{-(\Delta_{I}+\epsilon_{r})/2}\frac{-\eta}{\sqrt{2}\epsilon_{s}^{2}}\frac{2}{\sqrt{\pi}}e^{-\eta^{2}/2\epsilon_{s}^{2}}\partial_{y}g\left(\sqrt{\Delta_{I}+\epsilon_{r}}\xi,\frac{\eta}{\sqrt{2}\epsilon_{s}}\right)\right]$
(133)
$\displaystyle=-\mathbb{E}_{\xi,\eta}\left[e^{-(\Delta_{I}+\epsilon_{r})/2}\eta\sqrt{\frac{2}{\pi}}\partial_{y}g\left(\sqrt{\Delta_{I}+\epsilon_{r}}\xi,\frac{\eta}{\sqrt{2}}\right)\right]+\mathcal{O}(\epsilon_{s})$
(134)

So
$C_{1}(\Delta_{I})=\sqrt{\frac{2}{\pi}}\mathbb{E}_{\xi,\eta}\left[e^{-\Delta_{I}/2}\eta\partial_{y}g\left(\sqrt{\Delta}_{I}\xi,\eta\right)\right]$.

##### – $f_{2}$ –

We introduce

$\displaystyle h(x,y)$
$\displaystyle=\frac{\sinh^{2}(x)}{\cosh(x)+\sinh(x)\mathrm{erf}(y/\sqrt{2})}$
(135) $\displaystyle f_{2}(r,s)$
$\displaystyle=\alpha\mathbb{E}_{\xi,\eta}\left[e^{-r/2}\frac{2}{\pi(1-s)}e^{-\eta^{2}\frac{s}{1-s}}h\left(\sqrt{r}\xi,\eta\sqrt{\frac{s}{1-s}}\right)\right]$
(136)

The first order is enough since it is not constant; we have:

$\displaystyle f_{1}(\Delta_{I}+\epsilon_{r},1-\epsilon_{s}^{2})$
$\displaystyle=\frac{\alpha}{\epsilon_{s}^{2}}\mathbb{E}_{\xi,\eta}\left[e^{-(\Delta_{I}+\epsilon_{r})/2}\frac{2}{\pi}e^{-\eta^{2}\frac{1-\epsilon_{s}^{2}}{\epsilon_{s}^{2}}}h\left(\sqrt{\Delta_{I}+\epsilon_{r}}\xi,\eta\sqrt{\frac{1-\epsilon_{s}^{2}}{\epsilon_{s}^{2}}}\right)\right]$
(137)
$\displaystyle=\frac{\alpha}{\epsilon_{s}}\mathbb{E}_{\xi,\eta}\left[e^{-\Delta_{I}/2}\frac{\sqrt{2}}{\pi}h\left(\sqrt{\Delta}_{I}\xi,\frac{\eta}{\sqrt{2}}\right)+\mathcal{O}(\epsilon_{r},\epsilon_{s})\right]$
(138)

So

$f_{1}(\Delta_{I}+\epsilon_{r},1-\epsilon_{s}^{2})=\frac{\alpha}{\epsilon_{s}}C_{2}(\Delta_{I})\quad,\quad
C_{2}(\Delta_{I})=\frac{\sqrt{2}}{\pi}\mathbb{E}_{\xi,\eta}\left[e^{-\Delta_{I}/2}h\left(\sqrt{\Delta}_{I}\xi,\frac{\eta}{\sqrt{2}}\right)\right]$
(139)

$C_{2}(\Delta_{I})$ is positive for all $\Delta_{I}$.

####  D.2.1 Stability

We obtain the following update of the perturbation:

$\begin{pmatrix}\epsilon_{r}\\\ \epsilon_{t}\\\
\epsilon_{s}\end{pmatrix}\to\begin{pmatrix}-\Delta_{I}C_{1}(\Delta_{I})\epsilon_{s}\\\
\sqrt{\epsilon}_{s}/\sqrt{\alpha C_{2}(\Delta_{I})}\\\
\sqrt{C}_{3}\sqrt{\epsilon}_{t}e^{-1/4\epsilon_{t}^{2}}\end{pmatrix}$ (140)

We consider only the $s$ variable because $r$ does not affect the dynamics and
the initialization is done on $r$ and $s$, $t$ being inferred then. We have

$\epsilon_{s}^{t+1}=\sqrt{C_{3}}\sqrt[4]{\frac{\epsilon_{s}^{t}}{\alpha
C_{2}(\Delta_{I})}}e^{-\alpha C_{2}(\Delta_{I})/4\epsilon_{s}^{t}}$ (141)

which is stable for all $\alpha$ and $\Delta_{I}$.

Numerically, however, instability can be detected: for $\epsilon_{s}$ large
enough the system diverges from the fully informative fixed point. We compute
numerically the limiting $\epsilon_{s}^{*}$, such that
$\epsilon_{s}^{t+1}=\epsilon_{s}^{t}$; we find that $\epsilon_{s}^{*}$ tends
to zero fast for $\Delta_{I}$ or $\mu$ going to zero.

Figure 5: The limiting perturbation
$2\log_{10}(\epsilon_{s}^{*})=\log_{10}(1-q_{w}^{*})$ to the fixed point vs
$\mu$ for some $\alpha$s. $p_{o}=1/2$. These are the fixed points of eq.
(141). When initialized above the curves, the system diverges from the fully-
informative fixed point. When the snr $\Delta_{I}=\mu^{2}/p_{o}(1-p_{o})$
tends to 0, the size of the attraction basin shrinks to 0.

In the Gaussian case we have $f_{3}(t)=t/(1+t)$ and so
$\epsilon_{s}^{t+2}=\epsilon_{t}^{t+1}=\sqrt{\epsilon_{s}^{t}}/\sqrt{\alpha
C_{2}(\Delta_{I})}$; so this fixed point is unconditionally not stable.

####  D.2.2 Generalization of the prior

We ask for which prior $P_{w}$ the fully-informative point is stable. We
recall that

$f_{3}(t)=\mathbb{E}_{\xi}\left[\left(\int\mathrm{d}w\,wP_{w}(w)e^{-tw^{2}+\sqrt{t}\xi
w}\right)^{2}\left(\int\mathrm{d}w\,P_{w}(w)e^{-tw^{2}+\sqrt{t}\xi
w}\right)^{-1}\right]$ (142)

We assume that $\mathbb{E}_{P_{w}}w^{2}=\rho_{w}^{2}=1$.

We show that if $P_{w}$ admits everywhere a density twice differentiable, then
the fully-informative fixed point is unstable. Indeed, at large $t$ we have:

$\displaystyle f_{3}(t)$
$\displaystyle=\mathbb{E}_{\xi}\left[\frac{1}{\sqrt{t}}e^{\frac{1}{2}\xi^{2}}\left(\int\mathrm{d}w\,\left(\frac{w}{\sqrt{t}}+\frac{\xi}{\sqrt{t}}\right)P_{w}(\frac{w}{\sqrt{t}}+\frac{\xi}{\sqrt{t}})e^{-\frac{1}{2}w^{2}}\right)^{2}\right.$
$\displaystyle\quad\quad\quad\left.\left(\int\mathrm{d}w\,P_{w}(\frac{w}{\sqrt{t}}+\frac{\xi}{\sqrt{t}})e^{-\frac{1}{2}w^{2}}\right)^{-1}\right]$
(143)
$\displaystyle=\frac{1}{\sqrt{t}}\int\mathrm{d}\xi\,\left(\int\frac{\mathrm{d}w}{\sqrt{2\pi}}\,e^{-\frac{1}{2}w^{2}}\left(\frac{w}{\sqrt{t}}+\frac{\xi}{\sqrt{t}}\right)\left(P_{w}(\frac{\xi}{\sqrt{t}})+\frac{w}{\sqrt{t}}P^{\prime}_{w}(\frac{\xi}{\sqrt{t}})\right)\right)^{2}$
$\displaystyle\quad\left(\int\frac{\mathrm{d}w}{\sqrt{2\pi}}\,e^{-\frac{1}{2}w^{2}}\left(P_{w}(\frac{\xi}{\sqrt{t}})+\frac{w^{2}}{2t}P^{\prime\prime}_{w}(\frac{\xi}{\sqrt{t}})\right)\right)^{-1}$
(144)
$\displaystyle=\int\mathrm{d}x\,\left(xP_{w}(x)+\frac{1}{t}P^{\prime}_{w}(x)\right)^{2}\left(P_{w}(x)+\frac{1}{2t}P^{\prime\prime}_{w}(x)\right)^{-1}$
(145) $\displaystyle=1-\mathcal{O}(1/t)$ (146)

and obtain an equation similar to the one of the Gaussian case:
$\epsilon_{s}^{t+2}=C^{\prime}\sqrt{\epsilon_{s}^{t}}$, $C^{\prime}>0$, which
is unstable.

####  D.2.3 Large snr

We give an implicit value for the critical compression ratio
$\alpha_{\mathrm{algo,d}}$. We take the limit $\Delta_{I}\gg 1$ and seek
whether the SE updates converge to the fully informative point.

We can simplify the SE equations to one scalar equation. We expand on
$r=\Delta_{I}q_{s}\gg 1$. We have $q_{s}=f_{1}(r,s)\to 1$ for all $s$. As to
$q_{z}$ and $\hat{q}_{z}$, we have

$f_{2}(s)=\alpha\frac{2}{\pi}\frac{1}{\sqrt{1-s^{2}}}\mathbb{E}_{\eta}\left[1-\mathrm{erf}\left(\eta\sqrt{\frac{s}{2(1+s)}}\right)^{2}\right]^{-1}$
(147)

We plug $f_{2}$ and $f_{3}$ together. The fixed points are the $s$ that
satisfy the equation $s=f_{3}(f_{2}(s))$. The function $f_{3}\circ f_{2}$ is
plotted in the following figure.

Figure 6: Update function $f_{3}(f_{2}(s))$ vs $s$ for many $\alpha$s. It
describes the SE equations at large snr. For $\alpha\approx 1.5$ the curve is
tangent to the identity at $s\approx 0.9$; for greater $\alpha$ there is only
one fixed point, the perfect recovery one.

For $\alpha>\alpha_{\mathrm{algo,d}}\approx 1.5$ the updates lead to perfect
recovery $s=1$, starting from any $s$. For $\alpha<\alpha_{\mathrm{algo,d}}$,
perfect recovery is possible only starting from $s$ close to 1; otherwise the
iterations lead to a sub-optimal fixed point.

##  Appendix E Supplementary figures

Figure 7:  Thermodynamic limit. Overlap $q_{S}$ of the fixed point of the
algorithm AMP–BP, vs $\lambda$ for a range of population sizes $N$.
$\alpha=3$, $c=5$, $P_{w}$ Gaussian. We run one hundred ($N$ small) or ten
experiments ($N$ large) per point. _Insets:_ we plot the standard deviation
over the experiments. Figure 8:  Semi-supervised. Test overlap $q_{S}$ of the
fixed point of AMP–BP, vs $\lambda$ for a range of compression ratios
$\alpha$. The proportion of train nodes is $\rho$. Semi-supervised always
performs better than unsupervised. $N=10^{4}$, $c=5$, $P_{w}$ Gaussian. We run
ten experiments per point. Figure 9:  Semi-supervised, binary prior. _Left and
right:_ test overlap $q_{S}$ and free entropy
$\phi_{\mathrm{Bethe}}-\phi_{\mathrm{info}}$ of the fixed point of the
algorithm AMP–BP, vs $\lambda$ for several compression ratios $\alpha$.
$N=10^{4}$, $c=5$, $P_{w}$ Rademacher, $\rho=0.1$. We run ten experiments per
point; the median is plotted and the error bars are the difference between the
0.85th and 0.15th quantiles. _Insets:_ we plot the median and the ten data
points. We use damping for AMP–BP: we interpolate taking 1/4 of the values at
$t+1$ and 3/4 of the values at $t$.

Figure 10:  Baselines, Gaussian prior. Overlap $q_{S}$ of the baseline
algorithms, vs $\lambda$. We compare to the overlap obtained by AMP–BP.
_Left:_ unsupervised; for the parameters of the graph convolution we choose
$a=0.1$ and $n=4$. _Right:_ semi-supervised; for the hyper-parameters of the
GNN we choose $n=2$, $N_{\mathrm{hidden}}=20$, learning rate $3.10^{-4}$ and
L2 penalty $10^{-3}$. The train set is $\rho=1/10^{\mathrm{th}}$ of the nodes.
$N=10^{4}$, $c=5$, $P_{w}$ Gaussian. We run ten experiments per point.

## References

  * Abbe (2017) Emmanuel Abbe.  Community detection and stochastic block models: recent developments.  _The Journal of Machine Learning Research_ , 18(1):6446–6531, 2017.
  * Abbe et al. (2015) Emmanuel Abbe, Afonso S Bandeira, and Georgina Hall.  Exact recovery in the stochastic block model.  _IEEE Transactions on information theory_ , 62(1):471–487, 2015.
  * Aubin et al. (2019) Benjamin Aubin, Bruno Loureiro, Antoine Maillard, Florent Krzakala, and Lenka Zdeborová.  The spiked matrix model with generative priors.  In _Advances in Neural Information Processing Systems_ , 2019.  arxiv:1905.12385.
  * Barbier et al. (2019) Jean Barbier, Florent Krzakala, Nicolas Macris, Léo Miolane, and Lenka Zdeborová.  Optimal errors and phase transitions in high-dimensional generalized linear models.  _Proceedings of the National Academy of Sciences_ , 116(12):5451–5460, 2019.
  * Binkiewicz et al. (2017) Norbert Binkiewicz, Joshua T. Vogelstein, and Karl Rohe.  Covariate-assisted spectral clustering.  _Biometrika_ , 104(2):361–377, 2017.  arxiv:1411.2158.
  * Celentano et al. (2021) Michael Celentano, Chen Cheng, and Andrea Montanari.  The high-dimensional asymptotics of first order methods with random data.  _arXiv preprint arXiv:2112.07572_ , 2021.
  * Cheng et al. (2022) Shi Cheng, Liming Pan, Hong Hu, and Ivan Dokmanić.  Statistical mechanics of generalization in graph convolution networks.  2022\.  arxiv:2212.13069.
  * Chien et al. (2021) Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic.  Adaptive universal generalized pagerank graph neural network.  In _International Conference on Learning Representations_ , 2021.  arxiv:2006.07988.
  * Cho et al. (2022) Sungjun Cho, Seonwoo Min, Jinwoo Kim, Moontae Lee, Honglak Lee, and Seunghoon Hong.  Transformers meet stochastic block models: Attention with data-adaptive sparsity and cost.  In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, _Advances in Neural Information Processing Systems_ , 2022.  URL https://openreview.net/forum?id=w_jvWzNXd6n.
  * Coja-Oghlan et al. (2017) Amin Coja-Oghlan, Florent Krzakala, Will Perkins, and Lenka Zdeborová.  Information-theoretic thresholds from the cavity method.  In _Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing_ , pages 146–157, 2017.
  * Cornacchia et al. (2022) Elisabetta Cornacchia, Francesca Mignacco, Rodrigo Veiga, Cédric Gerbelot, Bruno Loureiro, and Lenka Zdeborová.  Learning curves for the multi-class teacher-student perceptron.  _Machine Learning: Science and Technology_ , 2022.
  * Decelle et al. (2011a) Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová.  Inference and phase transitions in the detection of modules in sparse networks.  _Physical Review Letters_ , 107(6):065701, 2011a.
  * Decelle et al. (2011b) Aurélien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová.  Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications.  _Phys. Rev. E_ , 84, 2011b.  arxiv:1109.3041.
  * Deshpande et al. (2018) Yash Deshpande, Subhabrata Sen, Andrea Montanari, and Elchanan Mossel.  Contextual stochastic block models.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 31, 2018.  arxiv:1807.09596.
  * Donoho et al. (2009) David L Donoho, Arian Maleki, and Andrea Montanari.  Message-passing algorithms for compressed sensing.  _Proceedings of the National Academy of Sciences_ , 106(45):18914–18919, 2009.
  * Fortunato (2010) Santo Fortunato.  Community detection in graphs.  _Physics reports_ , 486(3-5):75–174, 2010.
  * Fountoulakis et al. (2022) Kimon Fountoulakis, Dake He, Silvio Lattanzi, Bryan Perozzi, Anton Tsitsulin, and Shenghao Yang.  On classification thresholds for graph attention with edge features.  arxiv:2210.10014, 2022.
  * Gabrié et al. (2018) Marylou Gabrié, Andre Manoel, Clément Luneau, Nicolas Macris, Florent Krzakala, Lenka Zdeborová, et al.  Entropy and mutual information in models of deep neural networks.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Gamarnik et al. (2022) David Gamarnik, Cristopher Moore, and Lenka Zdeborová.  Disordered systems insights on computational hardness.  _Journal of Statistical Mechanics: Theory and Experiment_ , 2022(11):114015, 2022.
  * Gerbelot and Berthier (2021) Cédric Gerbelot and Raphaël Berthier.  Graph-based approximate message passing iterations.  _arXiv preprint arXiv:2109.11905_ , 2021.
  * Györgyi (1990) Géza Györgyi.  First-order transition to perfect generalization in a neural network with binary synapses.  _Physical Review A_ , 41(12):7097, 1990.
  * Krzakala et al. (2012) Florent Krzakala, Marc Mézard, Francois Sausset, Yifan Sun, and Lenka Zdeborová.  Probabilistic reconstruction in compressed sensing: algorithms, phase diagrams, and threshold achieving matrices.  _Journal of Statistical Mechanics: Theory and Experiment_ , 2012(08), aug 2012.  arxiv:1206.3953.
  * Krzakala et al. (2013) Florent Krzakala, Cristopher Moore, Elchanan Mossel, Joe Neeman, Allan Sly, Lenka Zdeborová, and Pan Zhang.  Spectral redemption in clustering sparse networks.  _Proceedings of the National Academy of Sciences_ , 110(52), 2013\.
  * Krzakala et al. (2014) Florent Krzakala, Andre Manoel, Eric W. Tramel, and Lenka Zdeborová.  Variational free energies for compressed sensing.  In _2014 IEEE International Symposium on Information Theory_ , pages 1499–1503, 2014.  arxiv:1402.1384.
  * Lesieur et al. (2017) Thibault Lesieur, Florent Krzakala, and Lenka Zdeborová.  Constrained low-rank matrix estimation: Phase transitions, approximate message passing and applications.  _Journal of Statistical Mechanics: Theory and Experiment_ , 2017(7):073403, 2017.
  * Loureiro et al. (2021) Bruno Loureiro, Cedric Gerbelot, Hugo Cui, Sebastian Goldt, Florent Krzakala, Marc Mezard, and Lenka Zdeborová.  Learning curves of generic features maps for realistic datasets with a teacher-student model.  _Advances in Neural Information Processing Systems_ , 34:18137–18151, 2021.
  * Lu and Sen (2020) Chen Lu and Subhabrata Sen.  Contextual stochastic block model: Sharp thresholds and contiguity.  _arXiv preprint arXiv:2011.09841_ , 2020.
  * Manoel et al. (2017) Andre Manoel, Florent Krzakala, Marc Mézard, and Lenka Zdeborová.  Multi-layer generalized linear estimation.  In _2017 IEEE International Symposium on Information Theory (ISIT)_ , pages 2098–2102. IEEE, 2017.
  * Miolane (2017) Léo Miolane.  Fundamental limits of low-rank matrix estimation: the non-symmetric case.  _arXiv preprint arXiv:1702.00473_ , 2017.
  * Mossel et al. (2015) Elchanan Mossel, Joe Neeman, and Allan Sly.  Reconstruction and estimation in the planted partition model.  _Probability Theory and Related Fields_ , 162:431–461, 2015\.
  * Mossel et al. (2018) Elchanan Mossel, Joe Neeman, and Allan Sly.  A proof of the block model threshold conjecture.  _Combinatorica_ , 38(3):665–708, 2018.
  * Ongie et al. (2020) Gregory Ongie, Ajil Jalal, Christopher A Metzler, Richard G Baraniuk, Alexandros G Dimakis, and Rebecca Willett.  Deep learning techniques for inverse problems in imaging.  _IEEE Journal on Selected Areas in Information Theory_ , 1(1):39–56, 2020.
  * Peixoto (2019) Tiago P Peixoto.  Bayesian stochastic blockmodeling.  _Advances in network clustering and blockmodeling_ , pages 289–332, 2019.
  * Shlezinger et al. (2020) Nir Shlezinger, Jay Whang, Yonina C Eldar, and Alexandros G Dimakis.  Model-based deep learning.  _arXiv preprint arXiv:2012.08405_ , 2020.
  * Sompolinsky et al. (1990) Haim Sompolinsky, Naftali Tishby, and H Sebastian Seung.  Learning from examples in large neural networks.  _Physical Review Letters_ , 65(13):1683, 1990\.
  * Tsitsulin et al. (2021) Anton Tsitsulin, Benedek Rozemberczki, John Palowitch, and Bryan Perozzi.  Synthetic graph generation to benchmark graph learning.  In _Workshop on Graph Learning Benchmarks_ , 2021.  arxiv:2204.01378.
  * Yang et al. (2013) Jaewon Yang, Julian McAuley, and Jure Leskovec.  Community detection in networks with node attributes.  In _2013 IEEE 13th international conference on data mining_ , pages 1151–1156. IEEE, 2013.
  * Zdeborová and Krzakala (2016) Lenka Zdeborová and Florent Krzakala.  Statistical physics of inference: Thresholds and algorithms.  _Advances in Physics_ , 65(5):453–552, 2016.
  * Zhang et al. (2014) Pan Zhang, Cristopher Moore, and Lenka Zdeborová.  Phase transitions in semisupervised clustering of sparse networks.  _Physical Review E_ , 90(5):052802, 2014.