Optimal Inference in Contextual Stochastic Block Models
Authors: O Duranthon
Lenka Zdeborova
Venue: Accepted by TMLR ()

Abstract: The contextual stochastic block model (CSBM) was proposed for unsupervised community detection on attributed graphs where both the graph and the high-dimensional node information correlate with node labels. In the context of machine learning on graphs, the CSBM has been widely used as a synthetic dataset for evaluating the performance of graph-neural networks (GNNs) for semi-supervised node classification. We consider a probabilistic Bayes-optimal formulation of the inference problem and we derive a belief-propagation-based algorithm for the semi-supervised CSBM; we conjecture it is optimal in the considered setting and we provide its implementation. We show that there can be a considerable gap between the accuracy reached by this algorithm and the performance of the GNN architectures proposed in the literature. This suggests that the CSBM, along with the comparison to the performance of the optimal algorithm, readily accessible via our implementation, can be instrumental in the development of more performant GNN architectures.

Published in Transactions on Machine Learning Research (03/2024)
Optimal Inference in Contextual Stochastic Block Models
O. Duranthon and L. Zdeborová
Statistical Physics of Computation laboratory, École polytechnique fédérale de Lausanne (EPFL), Switzerland firstname. lastnamedepfl.ch
Reviewed on OpenReview:
Abstract
The contextual stochastic block model (CSBM) was proposed for unsupervised community detection altributed graphs where both the graph and the high-dimensional node in- formation correlate with node labels. In the context of machine learning on graphs, the CSBM has been widely used synthetic dataset for evaluating the performance of graph- neural networks (GNNs) for semi-supervised node classification. We consider probabilistic Bayes-optimal formulation of the inference problem and we derive a optimal in the considered setting
algorithm for the semi-supervised CSBM; we conjecture and we provide its implementation. We show that there can be a considerable gap between the accuracy reached by this algorithm and the performance of the GNN architectures proposed in the literature. This suggests that the CSBM, along with the comparison to the performance of the optimal algorithm, readily accessible via our implementation, can be instrumental in the development of more performant GNN architectures.
1 Introduction
In this paper we are interested in the inference of a latent community structure given the observation of a sparse graph along with nigh-dimensional node covariates, correlated with the same latent communities. With the same interest, the authors of Yan & Sarkar (2021); Deshpande et al. (0088) introduced the contextual stochastic block model (CSBM) (SBM) for community detection. The CSBM accounts for the presence of node covariates; it models them high-dimensional Gaussian mixture where cluster labels coincide with the community labels and where the centroids are latent variables. Along the lines of thcorotical results established in the past decade for the SBM, see e.g. the review Abbe (2017) and references therein, authors of Deshpande et al. (2018) and later Lu & Sen (2020) study the detectability threshold in this model.
extension of the well-known and broadly studied stochastic block model
Our motivation to study the CSBM is due to the interest this model has recently received in the community developing and analyzing graph neural networks (GNNs). Indeed, this model provides idealized synthetic dataset on which graph neural networks can be conveniently evaluated and benchmarked. Tt has been used, for instance, in [aranwal et al. (2021); Kimon and test theoretical results on graph convolutional networks or graph-attention neural networks. In Wu et al. (2023) the CSBM was used to study over-smoothing GNNs and in Wei al. (2022) to study the role of non-rinc.rt.. As synthetic dataset the CSBM has also been utilized Cong et al. (2021) p for supporting icalretical results on depth in graph convolutional networks and in Chien al. (2021); ); Fu et al. (2021); ); Lei et al. (2022) for evaluating
Kimon et al. (2022): Javaloy et al. (2023): ; Shi et al. (2023) to establish
GNN architectures. Some of the above works study the CSBM in the unsupervised case; however, more often they study it in the semi-supervised case where on top of the network and covariates we observe the membership of a fraction of the nodes.
While many of the above-cited works use the CSBM as a benchmark and evaluate GNNs on it, they do not compare to the optimal performance that tractably achievable in the CSBM. A similar situation happened in the past for the stochastic block model. Many works were published proposing novel community detection algorithms and evaluating them against each other, see e.g. the review Fortunato (2010) and references

---

Published in Transactions on Machine Learning Research (03/2024)
there-in. The work of Decelle et al. (2011) changed that situation by conjecturing that specific variant of the belief propagation algorithm provides the optimal performance achievable tractably in the large size limit. A line of work followed where new algorithms, including early GNNs (Chen et al. 2020), were designed to approach or match this predicted thcoretical limit.
The goal of the present work to provide belief-propggation-bess algorithm, which we call AMP-BB BP, for the semi-supervised CSBM. It is able to deal with noisy-labels; it can estimate the parameters of the model and we propose a version of it for multiple unbalanced communities. We conjecture AMP-BP has optimal performance among tractable algorithms in the limit of large sizes. We provide a simple-to-use implementation of the algorithm (attached in the Supplementary Material) so that rescarchers in GNNs who use CSBM as benchmark can readily compare to this baseline and get an idea of how far from optimality their methods are. We also provide a numerical section illustrating this, where we compare the optimal inference CSBM with the performance of some of state-of-the-art GNNs. We conclude that indeed there is still a considcrable gap between the two; and we hope the existence of this gap will inspire follow-up work in GNNs aiming to close it.
Related work Previous works deal with optimal inference in CSBM. Tn a setting with low-dimensional features there is Braun et al. (2022) that is unsupervised for multi-community;; it does not require hyper- paramcter tuning but it focuses exact recovery when the graph signal-to-noise ratio grows with number of nodes. Abbb et al. (0022) proposes an optimal spectral algorithm for unsupervised binary CSBM in the case of growing degrees. There is also Baranwal et al. (2023) that determines a localy-optimal semi-supervised classifier and shows it can interpreted as a GNN. In the same higl-dimensional setting as ours, there are Lu & Sen (020)) and the belief paaeeefpooaggain-bbaeea based algorithm Deshpande et al. (2018); they are unsupervised
and need the right parameters of the model; we discuss them more detail further. Works on optimality in
related models of SBMs with features include Duranthon & Zdeborová (2023), where the group memberships
are a generic function of the features.
We consider the CSBM in semi-supervised high-dimensional sparse setting. Semi-supervision is necessary because we want to compare to empirical risk minimizers such that GNNs; they require fraction of train labels to be trained. In the regime where the features are high-dimensional, many quantities of interest. converge to deterministic values and allow a precise analysis, as opposed to low-dimensional features. We choose a sctting with a sparse graph because this is closer to what in practice rescarchers in GNNs use. The setting where the graph is dense is theoretically easier to deal with (e.g. it has been analyzed in Deshpande et al. 2018) and Shi et al. (2023)) and we provide the corresponding optimal algorithm in appendix.
2
Setup
2.1
Contextual stochastic block model (CSBM)
We consider a set V of [V|= N nodes and graph G(V, F.) those nodes. Fach of the nodes belongs to one of two groups: u, E {1, for i two balanced groups: u; is Rademacher. We make this choice following previous papers that used CSBM to study graph neural networks. We note, however, that multiple communities or arbitrary sizes can be readily considered, as done for the SBM in Decelle et al. (2011) and for the high-dimensional Ganssian mixture c.g. in Lesieur et al. (2017). In appendix D we define the unbalanced mulity-commuiity setup and provide the corresponding AMP BP algorithm.
I, We draw their memberships independently, and we consider
The graph is generated according to stochastic block model (SBM):
c//N if u, u= uy. Co. N if u, + Ujz
P(Ag 1/24, uy) =
(1)
and Ag 0 otherwise. 6; E R and co are the two affinity coefficients common to the SBM. We stack them in the matrix C C= (2 %
2

---

Published in Transactions on Machine Learning Research (03/2024)
We also consider cesbure/attribute/eee covvrriaae B RRPx of dimension P on the N nodes. They generated
according to a high-dimensional Gaussian mixture model:
H Uguu + Zza
BB:
(2)
for B = l...., P, where tig ~ [0, 1) determines the randomly drawn centroids, Ze; is standard Gaussian noise and ja is the strength of the signal. We precise that there are two centroids: the features of the nodes in the +1 group are centered at V while the features of the -1 group are centered edges and the feature matrix are observed. We aim to retrieve the groups u4.
V The
We work in the sparse limit of the SBM: the average degree of the graph A is d = (1). We paramcterize the SBM via the signal-lo-noise ratio A:
G =
co =d=
(3)
We further work in the high- digh-dimensional limit of the CSBM. We take both N and P going to infinity with a = N/P: (1) and μ O(1)
We define E as the set of revealed training nodes, that are observed. We set p= |I/N; P == for unsupervised learning. We assume is drawn independently with respect to the group memberships. We define P0, an additional node-dependant prior. It is used to inject information about the memberships of the observed nodes:
Pu,(s)= = {
6n,u, if iEE, 1/2 E
(4)
2.2 Bayes-optimal estimation
We use Bayesian framework to infer optimally the group membership from the observations A, B,E. E. The posterior distribution over the nodes u (u;); is
P(uAA,BEE) = Z,A,B,E)
(5)
II, (u.) = B(A,
II P(Acylu Kc
/ II Py
(Bs frau:))
(6)
3, V2T
where Z(A, B, B,E) E) the normalization constant and Py = (0, 1) is the prior distribution on v. eq. 6
we marginalize over the latent variable = (mz) However, since the estimation of the latent variable v is crucial to infer u, it will be instrumental to consider the posterior as joint probability of the unobserved nodes and the latent variable:
P(u, A,A, II, (t,((), II (vg)
1 1B v
II P(Aglus Uz)
II
Z(A,
V2m
8,
where Z(A, B,E) is the Bayesian evidence. We define the free entropy of the problem as its logarithm:
1 N
MA
log Z(A,
(8)
We seek an estimator that maximizes the mean overlap MO with the ground truth. The Bayes-optimal estimator à that maximizes it is given by
N
MO( = Σ P(W,A,
Σ
8 8agm
a
MMO = ar argmax (t),),
(9)
N
f=#1
a
3

---

Published in Transactions on Machine Learning Research (03/2024)
where P: is the marginal posterior probability of node i i.c. pt(t) E latent variable v, we consider minimizing the mean squared error MSF via the MMSE estimator
To estimate the
MSE - f du u| B,
/
1 P
[03 (0g 8=1
23)²
f de Σ u( B,
(10)
i.e. MMSE is the mean of the posterior distribution. Using the ground truth values u, of the communities and 2g of the latent variables, the maximal mean overlap MMO and the minimal mean squared error MMSE are then computed as
MMO Σ
8 aaMo
MMSE
1 P
Σ
MMSE 00
-uz)²
(11)
In practice, measure the following test overlap between the estimates à; and the ground truth variables uy:
qu 1 1/2 iu (1 P)N
qU 1/2
max
Σ i
5un V
(12)
where we rescale du obtain an overlap between 0 (random guess) and 1 (perfect recovery) and take into account the invariance by permutation of the two groups in the unsupervised case p 0.
In general, the Bayes-optimal estimation requires the evaluation of the averages over the posterior that is in general exponentially costly in N and P. In the next section, we derive the AMP BP algorithm. We argue that the estimators à and è it computes converge to the MMO and MMSE estimators with a vanishing error: P( Φ Σ, dapnoo & < - e) x and P E, 0z)² > c) N
for any e > with
N/P a= (1) and all other parameters being of ((1).
Detectability threshold and the effective signal-to-noise ratio Previous works on the inference the CSBM DDehpande et al. 2018 Lu & Sen 2020) established detectability threshold in the unsupervised case, p 0, to be
X = 1.
(13)
meaning that for a signal-to-noise ratio smaller than this, it is any correlation with the ground truth communities. On the other hand, for snr larger than this, the works Deshpande et al. (2018): Lu & Sen (2020) demonstrate algorithms that are able to obtain a positive correlation with the ground truth communities.
impossible to obtain
This detectability threshold also intuitively quantifies the interplay between the parameters, the graph-related snr and the covariates-related sur 4²/a. Small y² /a generates benchmark where the graph structure carries most of the information; while small À generates a benchmark where the information from the covariates dominates; and if want both to be comparable, we consider both comparable. The combination from eq. (13) plays the role of an overall effective snr and thus allows tuning the benchmarks between regions where getting good performance is challenging easy.
The threshold
13 reduces to the one well known in the pure SBM (Decelle et al. 2011 when == 0 and to the one well known in the unsupervised high-dimensional Gaussian mixture (Lesieur et al. 2016 when À = 0.
3
The AMP-BP Algorithm
We derive the AMP BP algorithm starting from the factor graph representations of the posterior
8-+1
U1
x
4

---

Published in Transactions on Machine Learning Research (03/2024)
The factor graph has two kinds of variable nodes, one kind for u and the other one for u. The factors are of two types, those including information about the covariates B that form a fully connected bipartite graph between all the components of u and v, and those corresponding to the adjacency matrix A that form a fully connected graph between the components of u.
We write the belief-propagation (BP) algorithm for this graphical model (Yedidia et al. 2003 Mézard & Montanari 2009). It iteratively updates the so-called messages xs and vs. These different messages can be interpreted as probability distributions the variables u, and By conditioned on the absence of the target node in the graphical model. The iterative equations read (Yedidia et al. 2003 Mézard & Montanari
2009
xa-i Pv (v(3g)
v II
wigh x / d
xus xaxi e 12
(14)
Us
Xat x Pu.(us)
II
k-H
Wh x Σ
1 PesiP(AA P(Ais U1i U4))
(15)
34
Xay x Pug((t)
II 847
Vaj
V0n
x Σ
Xuy - - (B,, w ) 1/
(16)
kzj
where waz = / vou for all i and 3 and where the proportionality sign or means up to the normalization factor that ensures the message sums to one over its lower index.
We conjecture that the BP algorithm is asymptotically exact for CSBM. BP is exact on graphical models that are trees, which the one of CSBM is clearly not. The graphical model of CSBM, however, falls into the category of graphical model for which the BP algorithm for Bayes-optimal inference is conjectured to provide asymptotically optimal performance in the sense that, in the absence of first-order phase transitions, the algorithm iterated from random initialization reaches a fixed point whose marginals are equal to the true marginals of the postcrior the leading order in N.
This conjecture is supported by previous literature. The posterior 77) of the CSBM is composed of two parts that are independent of each other conditionally the variables u, the SBM part depending on A, and the Gaussian mixture part depending on B. Previous literature proved the asymptotic optimality of the corresponding AMP for the Gaussian mixture part in Dia et al. (2016). As to the SBM part, the asymptotic optimality of BP (Decelle et al. 2011) was proven for the binary semi-supervised SBM in Yu & Polyanskiy (2022). Because of the conditional independence, the optimality is expected to be preserved when we concatenate the two parts into the CSBM. For the sparse standard SBM in the unsupervised case the conjecture remains mathematically open.
The above BP equations can be simplified in the leading order in N to obtain the AMP BP algorithm. The details of this derivation are given in appendix A This is done by expanding in w in part accounting for the high- digh-dimensional Gaussian mixture side of the graphical model. This is standard in the derivation of the AMP algorithm, see c.g. Lesieur et al. (2017). On the SBM side the contributions of the non-edges are concatenated into an effective field, just as it is done for the BP on the standard SBM in Decelle et al. (201I). The AMP-BP algorithm then reads as in Algorithm I A version of the algorithm for an unbalanced molitytcommmnity setup is given in section D in the appendix.
To give some intuitions we explain what are the variables AMP BP employs. The variable 0s is an estimation of the posterior mean of tg. whereas σy of its variance. The variable i; is an estimation of the posterior mean of Ui, oy of its variance. Next Bi is proxy for estimating the mean of vy in the absence of the Gaussian mixture part, Ay for its variance; Bi is proxy for estimating the mean of u, in absence of the SBM part, Ay for its variance. Further ha can be interpreted as an external field to enforce the nodes not to be in the same group; X4 is a marginal distribution on (these variables are the messages of a sum-product message-passing algorithm); and x4. is the marginal probability that node is +1, that we are interested in.
The AMP-BP BP algorithm can be implemented very efficiently: it takes O(NP) in time and memory, which is the minimum to read the input matrix B. Empirically, the number of steps to converge does not depend on N and is of order ten, as shown Fig. t in appendix F We provide fast implementation of AMP BP
5

---

Published in Transactions on Machine Learning Research (03/2024)
features B3 E RPxN, observed graph G, afsinity matrix C, prior information Pr...
Input:
Estimation of the field h
Initialization: for (it) E G, X (-())) = Pu.((+) +
Cu, 1 l0k (1)
hu 1 Σ ΣΣ N
cht,, ( -P c², 0/ = e² ,=, where
et, and e" are small centered random variables in IR.
i
h - + log Pu,((u) + uB
Repeat until convergence:
C,. being the affinity between groups u and t. BP update of the messages x² for (ij) E G and of marginals x*
o = - a(.).
X+ x to (h+ h'
AMP estimation of 0
Co 2o22 X kmi
Σ log
k k-i.(() x+
Ci 2Xv
kEARY
U Au
(1).2
N
x4 = (h+
-h-+
h )-)((() Co co + X-
By V 1
Brtuf (8)
1
E o6
Σ log kedi
N
N
G 22 k+
(1+1) / + Au)
where σxœ) = 1/(1 e) is the sigmoid and di are the nodes connected to i. BP estimation of à
ov 1/(1 + Au)
AMP estimation
1 t 2x- -1
(+1)
By V N
Σ Barolett) (++1)
o (1)
Update time L 1+1
Output: estimated groups sign(d.).
A Algorithm 1: The AMP BP algorithm.
written in Python in the supplementary material and in our repository The algorithm can be implemented in terms of fast vectorized operations as to the AMP part; and, as to the BP part, vectorization is possible thanks to an encoding of the sparse graph in an O(Nd) x (dd) array with a padding node. Computationally, running the code for a single experiment, N x 10d,, a = and d = 5 takes around one minute on one CPU core.
We cross-check the validity of the derived AMP-BP algorithm by independent Monte-Carlo simulations. We sample the posterior distribution 7 with the Metropolis algorithm; the estimates for the communities are then (i uf), u' being the different samples. As shown on Fig. 7 in appendix F the agreement with AMP BP is very good except close to small qu, i.e. close to the phase transition, where the Markov chain seems to take time to converge.
Related work on message passing algorithms in CSBM The AMP-BP algorithm was stated for the unsupervised CSBM in section 6 of Deshpande et al. (2018) where it was numerically verified that it indeed presents the rnformation-theoreee performance this algorithm besides checking its delectability threshold. In particular, the authors did not comment on the asymptotic optimality of the accuracy achieved by this algorithm. Rather, they linearized it and studied the detectability threshold of this simplified lincarized version that is amenable to analysis
threshold (13). In that paper, little attention was given to the
citthb.epfl.ch//ppee wwwpsppooo-ddepiss/ssm...

---

Published in Transactions on Machine Learning Research (03/2024)
1.0
N=3x10'
10
N=
0.8
==3x10
0.8
N= 10
N- 10
N= 3 10*
0.6
0.4
0.2
0.0
0.0
0.5
1.0
2.0
1.5
A
Figure 1: Convergence. to the high- highh-dimensional limit. Overlap qu of the fixed point of AMP-BP the sur À for several system sizes N. Left: unsupervised case, 0. Right: semi-supervised, p 0.1. The other parameters are a 10, p= = 4, d = 5. We run ten experiments per point.
via random matrix theory. This threshold matches the information-theoreliine detectability threshold that later established in Lu & Sen (020)). The linearized version of the AMP -BP algorithm is spectral algorithm; it has sub-optimal accuracy, as we will illustrate below in section 3 We also note that the work Lu & Sen (2020) considered another algorithm based on self-avoiding walks. It reaches the threshold but it is not optimal in terms the overlap in the detectable phase or in the semi-supervised case, nor in terms of efficiency since it quasi-polynomial. Authors of Deshpande et al. (2018): Lu & Sen (2020) have not considered the semi-supervised case of CSBM, whereas that is the case that has been mostly used as a benchmark in the more recent GNN literature.
Bayes-optimal performance run AMP BP and show the performance it achieves. Since the conjecture of optimality of AMP-BP applies to the considered high-dimensional limit, first check how fast the performance converges to this limit. In Fig. I we report the achieved overlap when increasing the size N to +oo while keeping the other stated parameters fixed. We conclude that taking N 3 x 10 is already close to the limit; finite-size effects are relatively small.
Fig. 2 shows the performance for several different values the ratio a = N/P between the size of the graph N and the dimensionality of the covariates P. Its left panel shows the transition from a non-informative fixod point qu to an informative fixed point gu >> that becomes sharp in the limit of large sizes. It occurs in the unsupervised regime p 0 for a large enough. The transition is located at the critical threshold A given by eq. (13) This threshold is shared by AMP-BP and the spectral algorithm of Deshpande et al. (2018) in the unsupervised case. The transition is of 2nd order, meaning the overlaps vary continuously with respect to X. As expected from statistical physics, the finite size effects are stronger close to the threshold; this means that the variability from one experiment to another one larger when close to Ae-
The limit a - +00, in our notation, leads back to the standard SBM, and the phase transition at À in that limit. Taking S 2² or adding supervision p > 0 (Fig. - right) makes the 2nd order transition in the optimal performance disappear.
The spectral algorithm given by Deshpande et al. 2018 is sub-optimal. In the unsupervised case, it is linear approximation of AMP-BP, and the performances the two are relatively close. In the semi-supervised case, a significant gap appears bocause the spectral algorithm does not naturally use the additional information given by the revealed labels; it performs as
Dense limit We can consider the dense limit the CSBM where the average degree goes infinity. In this limit the SBM equivalent to low-rank matrix factorization problem and can be rigorously analyzed. The Bayes-optimality of the belief propagation-based algorithm then provable.

---

Published in Transactions on Machine Learning Research (03/2024)
1.0
0.8
0.6
907
Ae
0.4
=
10
0.2
spectral alg.
0.0
0.5
1.0
2.0
0.0
0.5
1.0
1.5
Figure 2: Performances of AMP-BB BP and of the spectral algorithm of Deshpande et al. (2018) sec. 4. Overlap qu of the fixed point of the algorithms, vs sur X for a range ratios a. Left: unsupervised, = 0; right: semi-supervised, p = 0.1. Vertical dashed lines on the left: theoretical thresholds A. partial recovery, 10a p² 4, d= 5. We run ten experiments per point.
eq. 13 N
The dense limit is defined by c; and co of order N and G - VvN. The adjacency matrix A can be approximated by noisy rank-one matrix [esieeu et al., 2017 Deshpande et al. 2018
Aij
N u + Eij
(17)
where the Ei are standard independent normals. The CSBM is then joint uu and ue matrix factorization problem. The BP on the SBM is approximated by an AMP algorithm; and one can glue the two AMPs. One can prove that the resulting AMP AMP algorithm is Bayes-optimal.
We state in appendix the AMP-AMP algorithm for CSBM and provide state evolution (SF) equations.
The rank-one approximation is valid for average degrees moderately large. Numerical simulations show that d 2 20 is enough at N 10 (Duranthnn & Zdeborová 2023 Shi et al. 2023
Parameter estimation and Bethe free entropy In case the parameters = (c,, Co, 11) of the CSBM (EM). This was proposed Decelle et al. (2011) for the affinity coefficients and the group sizes of the SBM. In the Bayesian framework, one has to find the most probable value of 0. This is equivalent to maximizing the free entropy d over
are known they can be estimated using expectationn-mxxiivaatiii
The exact free entropy é is not easily computable because this requires integrating over all configurations. Tt can be computed thanks to AMP-BP: at a fixed point of the algorithm, can be expressed from the values of the variables. It is then called the Bethe free entropy Bethe in the literature. The derivation is presented in appendix Bethe converges in probability to in the large N limit: for any e > 0, P(Lo @f Bethe
> E) + 0.
N-+00
For compactness, we write f
1-t and pack the connectivity coefficients in the matrix C. We have
N Bathe N
+ Σ
log Σ
II kEDS
Cu.et kii
log Σ Cu.X its (U)EG
Σ
(18)
2
16
w.t
B
log(1 + Ao)
Σ
(VV
N 1 10 02 + Roo 10a---233 (8323)
11
2
1 - Au
5
8

---

Published in Transactions on Machine Learning Research (03/2024)
1.0
0.8
@ 0.6
0.4
GPR--GNN AMP-BP
logistic resgressoon
0.2
11.00
-0.75
-.50
-0.25
0.00
0.25
0.50
0.75
1.00
1..0 00.5 -0.50
0.25
0.00
0.25 0.50 0.75 1.00
Figure 3: Comparison against CPR-GNN Chien et al. 2021). Overlap qu achieved by the algorithms,
& = 2 arctan( Left: few nodes revealed p == 0.025; right: more nodes revealed = 0.6. For GPR-GNN
plot the results of Fig. 2 and tables and 6 from Chien et al. 2021 N 10 2.5, 3.25, d = 5. We run len experiments per point for AMP-BI
where Ry Ag and By are given by the algorithm. One can then estimate the parameters by numerically maximizing o(0) (ethe or more efficiently iterating the extremality condition Veg =0, given in appendix which become equivalent to the expectation-maxxiiiatioo algorithm.
B
The Bethe free entropy is also used to determine the location of a first-order phase transition in case the AMP-BP algorithm has a different fixed point when rumning from the random initialization as opposed to running from the initialization informed by the ground truth values of the hidden variables u, v. In analogy with the standard SBM (Decelle et al. 2011) and the standard high-dimensional Gaussian mixture (Lesieur ett al.] 2016 2017), first-order transition expected appear when there are multiple groups or when one of the two groups much smaller than the other. We only study the case of two balanced groups where we observed these two initializations converge to the same fixed point in all our experiments.
Semi-supervision and noisy labels Semi-supervised AMP BP can be straight generalized to deal with noisy labels, thanks the Bayesian framework consider. It is sufficient to set the semi-supervised prior Pus to the actual distribution of the labels. For instance, if the observed label of the train node i is the true u, with probability q and -u, otherwise, then Pu,,(s) = =6..u, + (1 g)0,,-u..
4
Comparison against graph neural networks
AMP BP gives upper bounds for the performance of any other algorithm for solving CSBM. It is thus highly interesting to compare to other algorithms and to see how far from optimality they are.
4.1
Comparison GPR-GNN from previous literature
CSBM has been used as synthetic benchmark many times (Chien et al. 2021 Cong et al. 2021 Fu et al.
2021
Lei et al. 2022 to assess new architectures of GNNs or new algorithms. These works do not compare their results optimal performances. We propose to do so. As an illustrative example, we reproduce the experiments from Fig. 2 of the well-known work Chien et al. (2021).
Authors of Chien ct al. 2021 proposed GNN based GPR-CNN. The authors Lest it on CSBM for node classification and show it has better accuracy than many other models, for both À > 0 (homophilic graph) and À < 0 (heterophilic graph). We reproduce their results in Fig. Tig.3am and compare them to the optimal performance given by AMP--BP The authors of Chien et al. (001 different parameterization of the CSBM: they consider 22 n²
generalized PageRank method; it is called
and yp arctan Ava

---

Published in Transactions on Machine Learning Research (03/2024)
1.0
0.8
0.4
AMP-BP
logistic rop.
0.2
K=2
graph con7.
K=J
general com..
N 10"
1.0
Figure 4: Comparison to GNNs of various urchiteclures and convergence to high-ddmennsonall limil. Overlap achieved by the GNNs, vs the smr X. Left: general convolution for different numbers of layers K; middle; for different types of convolutions, at the best K (the detailed results for every K are reported on Fig. of appendix right: general convolution at K = for different sizes N. The other parameters are N = x 10 a = 10, 1 4, 5, p = 0.1. We run five experiments per point.
We see from Fig. that this sfate-of-thh-art GNN can be far from optimality. For the worst parameters in the figure, GPR-GNN reaches an overlap 50% lower than the accuracy of AMP BP. Fig. left shows that the gap is larger when the training labels are scarce, at p p= 2.5%. When enough data points are given (p 60%, right), GPR-GNN is rather close to optimality. However, this set of parameters seems easy since ;p simple logistic regression is also close to AMP-BP.
Authors of Chien et al. [0021 Fu et al. 2021 Lei et al. 2022) take > 0 thus considering only parameters in the detectable regime. We argue is more suitable for unsupervised learning than for semi-supervised because the labels then carry little additional information. From left to right on Fig. 3 we reveal more than one-half of the labels but the optimal performance increases by at most 4%. To have a substantial difference between unsupervised and semi-supervised one should take A 42 /a < 1, as we do in Fig. 2 This regime would then be more suitable to assess the learning by empirical risk minimizers (ERMss such GNNs. We use this regime in the next section.
4.2 Baseline graph neural networks
In this section, we evaluate the performance a range baseline GNNs on CSBM. We show again that the GNNs we consider do not reach optimality and that there room for improving these architectures. We consider the same task as before: on a single instance of CSBM a fraction p of node labels are revealed and the GNN must guess the hidden labels. As to the parameters of the CSBM, work in the regime where supervision is necessary for good inference; i.e. we take 2²/a < 1.
We use the architectures implemented by the GraphGym package YYuu et al. 2020). It allows to design the intra-layer and lnter-layer architecture of the GNN in a simple and modular manner. The parameters we considered are the number K of message-passing layers, the convolution operation (among graph convolution, general convolution and graph-attention convolution) and the internal dimension h. We fixed 64; we tried higher values for al. K 2, but we observed slight or no differences. One GNN is trained to perform node classification one instance of CSBM the whole graph, given the set E\t of revealed nodes. It is evaluated on the remaining nodes. More details on the architecture and the training are given in appendix
Fig. 4 shows that there is a gap between the optimal performance and the one of all the architect we tested. The GNNs reach an overlap of at least about ten per cent lower than the optimality, They are close the optimality only near X vd when the two groups are very well separated. The gap larger at small X. At small it may be that the GNNs rely too much on the graph while it carries little information: the logistic regression only the node features and performs better.
10

---

Published in Transactions on Machine Learning Research (03/2024)
The shown results are close to being asymptotic in the following sense. Since CSBM is synthetic dataset we can vary N, train different GNNs and check whether their test accuracies are the same. Fig 4 right shows that the test accuracies converge to a limit at large N and taking N = 3 x 10 is enough to work in this large-size limit of the GNNs on CSBM.
These experiments lead to another finding. We observe that there is an optimal number K of message-passing layers that depends on X. Having K too large mixes the covariates of the two groups and diminishes the performance. This effect seems to be mitigated by the attention mechanism: In Fig. [ right of appendix F] the performance of the graph-attention GNN increases with K at every X.
It is an interesting question whether the optimum performance can be reached by a GNN. One could argue that
is a sophisticated algorithm tailored for this problem, while GNNs are more generic. However, Fig. f shows that even logistic regression can be close to optimality at x=
We study the effect of the training labels. We consider a sctting where /²/a < 1 so supervision is necessary for À < 1. We check this is the case by letting the training ratio p going to on Fig. in appendix F We observe the resulting accuracies qu of AMP-BP and the GNNs drop to 0. The transition seems to be sharp. AMP-BP always performs better as expected.
4.3 Comparison to Baranwal et al. (2023), a locally Bayes-optimal architecture
The authors of Baranwal al. 2023 propose a GNN whose architecture implements the locally Bayes-optimal classifier for CSBM. Given a node they consider only its neighborhood; since the graph sparse, it is tree-like and the likelihood of the node has simple analytical expression. They parameterize a part of this classifier by multi-layer perceptron that is trained and connectivity matrix between communtiies is also learned. The resulting architecture is a GNN with a specific agregation function. The authors did not name it; we propose the name clipGNN. They set 1 the size of the neighborhoods it processes and L the number of layers of the perceptron. At / = 0 there is no agregation and clipGNN is a multi-layer perceptron classifying a Gaussian mixture.
The sctting Baranwal et al. (0033) considers a bit different: clipGNN was derived in a low-dimensional setting P ((). Yet, for large P it can be run and its local Bayes-optimality should remain valid. For fairness take P small or not too large. We have to scale μ the snr of the Gaussian mixture accordingly. According to 13) we shall take n²² of order = N/P.
The comparison can be seen on Fig. 5
AMP BP is considerably better for all parameters we tried. The results are similar to Fig. left in the sense that increasing the neighborhood size / increases the performance of their architecture, but there is still a large gap to reach the performances of AMP AP..BP Their architecture works closer to AMP-BP at large a i.. small P.
5 Conclusion
We provide the AMP-BP algorithm to solve the balanced CSBM with two groups optimally asymptotically in the limit of large dimension in both the unsupervised and semi-supervised cases. We show a sizable difference between this optimal performance and the one of recently proposed GNNs to which we compare. We hope that future works using CSBM as an artificial dataset will compare to this optimal AMP-BP algorithm, and we expect that this will help in developing more powerful GNN architectures and training methods.
An interesting future direction of work could be to generalize the results of Shi al. (0023 on the theoretical performance of one-layer graph-ccnnolutionn GNN trained on CSBM.
Another promising direction would be unrolling AMP- BP to form new architecture of GNN, as Chen et al. (2020) did for BP for SBM and Borgerding et al. 2017) for AMP in compressed sensing, and see if it can close the observed algorithmic gap. We expect this new architecture of GNN to be based on non-backtracking walks and to incorporate skip connections between its layers.
Acknowledgement
We acknowledge funding from the Swiss National Science Foundation grant SMArtNet (grant number 21 212049).
11

---

Published in Transactions on Machine Learning Research (03/2024)
1.0
1.0
clipGNN, ==
clipGNN, /
clipGNN.
clipGNN,
0.8
clipGNN,
0.8
ClipGNN, =
clipGNN, /
clipGNN, /-7
clipGNN,
0.6
AMP-BP
AMP-BP
0.4
0.4
0.0
0.0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
Figure 5: Comparison against GNN Baranwal et al. 2025). Overlap qu achieved by the algorithms, vs
X. is the size of the neigborhood clipGNN processes. Left: μ 50 and a = i.e. P = 200; right: μ²² 500 and a 500 i.e. 20. The other parameters are N 10 (N 5 100 for the two largest 1), p 0.05,
d 5, L 1. For clipGNN point.
the code kindly provided by the authors;
five experiments per
References
Emmanuel Abbé. Community detection and stochastic block models: recent developments. The Journal of Machine Learning Research, 18(1):6446-6) 6531, 2017. 1rxiv:1703.10144
Emmanuel Abbé, Jianqing Fan, and Kaizheng Wang. An lp theory of pea and spectral clustering. Annals of statistics, 50(4):2359 2385, 2022. arXiv:2006.14062
Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Graph convolution for semi-supervised classification: Improved linear separability and out-of-distribution generalization. In Proceedings of the 38th International Conference on Machine Learning, 2021. arxiv:2102.06966.
Aseem Baranwal, Aukosh Jagannath, and Kimon Fountonlakis. Optimality message-passing architectures for sparse graphs. 2023. arxiv:2305. 10391.
Mark Borgerding, Philip Schniter, and Sundeep Rangan. AMP-inspired deep networks for sparse linear inverse problems. IEEE Transactions Signal Processing, 65(16):4293-430) 2017. arxiv:1612.01188..
Guillaume Braun, Hemant Tyagi, and Christophe Biernacki. An iterative clustering algorithm for the contextual stochastic block model with optimality guarantees. In International conference on learning representations, 2022. arXiv:2112.1046:
Zhengdao Chen, Lisha Li, and Joan Bruna. Supervised community detection with line graph neural networks. In International conference on learning representations, 2020. arX1v:1705.08415.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptative universal generalized pagerank graph neural network. In International Conference Learning Representations, 2021. arxiv:2006.07000
Weilin Cong, Morteza Ramezani, and Mehrdad Mahdavi. On provable benefits of depth in training graph con- volutional networks. In 35th Conference on Neural Information Processing Systems, 2021. arxiv:2110.15174.
Aurdlien Docelle, 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, 2011. arxiv:11008 109.3041.
12

---

Published in Transactions on Machine Learning Research (03/2024)
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 (eds.), Advances in Neural Information Processing Systems, volume 31, 2018. arxiv:180700999.
Mohamad Dia, Nicolas Macris, Florent Krzakala, Thibault Lesieur, Lenka Zdeborová, et al. Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula. Advances in Neural Information Processing Syslems, 29, 2016. arxiv:1606.04142.
O Duranthon and L Zdeborová. Neural-prior stochastic block model. MLST, 2023. arxiv:2303009995.
Santo Fortunato. Community detection in graphs. Physics reports, 486(3-5):75 174, 2010. arXiv:0906.0612
Guoji Fu, Peilin Zhao, and Yatao Bian. p-Laplacian based graph neural networks. In Proceedings of the 39th International Conference on Machine Learning, 2021. arxiv:2111.07337.
Adrián Javaloy, Pablo Sanchez-Martin Amit Levi, and Isabel Valera. Learnable graph convolutional attention networks. In International Conference on Learning Representations, 2023. arxiv:2211.11853
Fountoulakis Kimon, Dake He, Silvio Lattanzi, Bryan Perozzi, Anton Tsitsulin, and Shenghao Yang. On classification thresholds for graph attention with edge features. 2022. arxiv:2210.10011
Runlin Lei, Zhen Wang, Yaliang Li, Bolin Ding, and Zhewei Wei. EvenNet: Ignoring odd-hop neighbors improves robustness of graph neural networks. In 36th Conference on Neural Information Processing Systems, 2022. arxiv:2205.13892
Thibault Lesieur, Caterina De Bacco, Jess Banks, Florent Krzakala, Cris Moore, and Lenka Zdeborová. Phase transitions and optimal algorithms in high-dimensional gaussian mixture clustering. In 2016 54th Annual Allerton Conference Communication, Control, and Computing (Allerton), pp. 601-608. IEEE, 2016. arxiv:1610.02918.
Thibault Lesieur, Florent Krzakala, and Lenka Zdeborová. Constrained low-rank matrix estimation: Phase transitions, approximate mossage passing and applications. Journal of Statistical Mechanics: Theory and Experiment, 2017(7):073403, 2017. arxiv:1701.00858.
Chen Lu and Subhabrata Sen. Contextual stochastic block model: Sharp thresholds and contiguity. 2020. arXiv:2011.09841.
Marc Mézard and Andrea Montanari. Information, physics, and computation. Oxford University Press, 2009.
Cheng Shi, Liming Pan, Hong Hu, and Ivan Dokmanić. Homophily modulates double descent generalization in graph convolution networks. PNAS, 121(8), 2023. arXiv:2212.13069.
Rongzhe Wei, Haoteng Yin, Junteng Jia, Austin Benson, and Pan Li. Understanding non-linearity graph neural networks from the Bayesian-inference perspective. In Conference on Neural Information Processing Systems, 2022. arxiv:2207.11311.
Xinyi Wu, Zhengdao Chen, William Wang, and Ali Jadbabaie. A non-asymptotic analysis of oversmoothing in graph neural networks. In International Conference on Learning Representations, 2023. arxiv:2212.10701.
Bowei Yan and Purnamrita Sarkar. Covariate regularized community detection in sparse graphs Journal of the American Statistical Association, 116(334):734-745, 2021. arxiv:1607.0267:
Jonathan Yedidia, William T Freeman, Yair Weiss, al. Understanding belief propagation and its generalizations. Exploring artificial intelligence in the new millennium, 8(236-239)00018 9448, 2003.
Jiaxuan You, Rex Ying, and Jure Leskovec. Design space for graph neural networks. In 34th Conference on Neural Information Processing Systems, 2020. arxiv:2011.06s
Qian Yu and Yury Polyanskiy. Ising model on locally tree-like graphs: Uniqueness of solutions to cavity equations. 2022. 1..2222211.15242.
13

---

Published in Transactions on Machine Learning Research (03/2024)
A Derivation of the algorithm
We recall the setup. We have nodes u, in {-1, P coordinates U/ in R; we are given the Px x N matrix BBs = ugu + Zai, where Zes is standard Gaussian, and we are given a graph whose edges As E (0 are drawn according to P(Aniu u,) & C'Asi (1 Cu..
We define upi V uou, and eg(B,w) = (B-w)²/2 the output channel. Later approximate the output Ba Tue
channel by its expansion near 0; we have:
0g ow
(w 0) = Bgs and
(w = 0))
Lg g = 0) B - 1.
We write belief propagation for this problem. We start from the factor graph of the problem:
U9
U1
Qry
There are six different messages that stem from the factor graph; they are:
Xutt x Pu,(( II 1-- ak+
(19)
Kii
Vu;
x
Σ
5-ه P(Asg Uus. Ug))
(20)
ue
6-3 Xui
x Pu,((us)
k-i
(21)
7$0
1+0 ((( Xue
(22)
x x Pv(ug) II
(23)
J+1
w x f dug Xus -
(24)
where the proportionality sign x means up to the normalization factor that insures the message sums to one over its lower index.
We simplify these equations following closely Lesieur et al. 2017 and Decelle et al. 2011
A.1 Gaussian mixture part
We parameterize messages and 24 as Gaussians expanding g
2 Σ
Xus i- ( (B Br + (B3, 1)
(25)
dug a (1 Ba + +B3, 1)w33//2
(26)
we define
0/10 = / ddxx-ti
of q"= = f /dux Aix0- -1g_.)
(27)
i Σ X
o Σ X
/ (u² az
(28)
14

---

Published in Transactions on Machine Learning Research (03/2024)
assemble products of messages in the target-dependent elements
Σ
Byrd 1 BU VN
P N
Σ
B
(29)
N
7F8
171
A/
P
Σ
B²
(B3g () + +oV-
(30)
N
TAB
A
P N
Σ
03 (B)) - 1) + tz
(31)
and in the larget-independent elements
Bi
B3:0g-1 ; By V N
P Σ Baz0j-n
(32)
AV
B B (B 1) 1) + ov o
(33)
N
B
A
Σ
B
(B3 1)(03 + of
(34)
N
we can write the messages of eq.
19
and
close form as
1-d x Pu.lu,)euujj u.
12/2 /2 II Σ
J- P(Axaluu ue)
(35)
x x (u ub - 12
Xua
P-Ass(A us)
(36)
Xe x Pv( -1gAA
(37)
Since we sum over = +1, the Ays can be absorbed in the normalization factor and can omit them.
A.2 SBM part
We work out the SBM part using standard simplifications. We define the marginals and their fields by
Xu, x Pu,:(u)e
II
k-i P(Ass ui)
(38)
kØi uk
ha; = N
1
ΣΣ
Cu
(39)
4 Ub
Simplifications give
5-+ =xy,
Xm,
if iii & ; else
(40)
2 Pu.luu)euBBi -hu: II Σ Cu X ki
(41)
kg0s/j
Xu, x Pu.ilu)euBii lou: II Σ Cuz. Xus
(42)
kEDs ue
x2+ x Bu
e Ruu II Σ
(43)
REDi Mk
15

---

Published in Transactions on Machine Learning Research (03/2024)
A.3 Update functions
The estimators can be updated thanks to the functions
()) = [ de PaP(vv) exp (Bu /2
f du Pv (v) exp (Bv Au2 = (/(A+1 +
(44)
(u B,X) = nn uP uPuu;(1) exp (Bu) Xu
(45)
Σn (u,)(u) exp (Bu) Xa
0BfU fö
(46)
The update is
0/ fv -1 BB0+)
ov = (Af BBO
(47)
0 (A BV (2))
dU
.-8 OBS 1-3 1B7,,
(48)
where Ra = hhu IIKE Ens Cux kii
A.4 Time indices
We mix the AMP part and the BP part in this manner:
0,
U
Au, By ;0,
00,00 20,00
((+1)
Av, ((+1)
û, dU
(++1)
=
(t)
X, h (++
X (++1)
where the dashed lines mean that 0;41 and x* are close. We precise this statement in the next section.
A.5 Additional simplifications preserving asymptotic accuracy
We introduce the target-independent estimators
03 = fv BB)
of = Osfv BB) of (A X*)
(49)
4, = lo By, Σ ux
(50)
This makes the message of eq. 43 redundant: can directly express ú' the estimator of the AMP side, as simple function of X the estimator of the BP side.
We express the target-independent As and Bs as function of these. We evaluate the difference between the larget-independent and the larget-dependent estimators and we obtain
A A1(+11
A
A
(.(+11 = A (t+11(
(51)
B+((+1
Bgg
(++1) (t+1)
11
B (.(++1) (0)
(52)
N
N
BB,(+11)
Σ
B
BB(ū(t)
Σ
B2
i(tt) (t)
0g
(53)
N
N
16

---

Published in Transactions on Machine Learning Research (03/2024)
We further notice that B3, concentrate one; this simplifies the equations to
ACt1)
1 N
(r+1)),
A
N Σ
a
12+1)
(54)
B
H
B
((++1)
vv
11(++1)
(55)
N 3
N
B
Σ
Bartt
(t)
(((t) (1)
(56)
N
N
The As do not depend on the node then; this simplifies ov:
ov a((+1) of ((t1)) Bū Ba((++1)
I(+1)) = 1/(1 + 1
(57)
(58)
g
By
H V
Σ
(t+1)
P (1+1) a ov
a(0
(59)
N
Last, express all the updates in function of Xu=+1, having Xu=-1 1 Xu=+1. This gives the algorithm in the main part.
B Free entropy and estimation of the parameters
To compute Bethe free entropy we start from the factor graph. Factor nodes are between two variables so the free entropy is
No = ΣΦ: oi - Σ
(15)
+
Σ
Σ
(13))
(60)
iej
B
(18)
with
di = log Σ
Pu.a (u:)
2
B
(61)
thi
(13) log E P(Ayg) Mes (u)xxu
Xus
(62)
ΦB log I dog (v())) II 2
(63)
((3)) log Σ
/ dug e (B3c)) i- B+b Xus Xus
(64)
We use the same simplification as above to express these quantities in terms of the estimators returned by AMP BP. This is standard computation; we follow Lesieur et al. (2017) and Decelle et al. (2011). The parts &i and de on the variables involves the normalization factors of the marginals à, and 6g:
6 =
Av
+ log Σ M
Σ
Cu K+i
(65)
2
x=
kED:
1=21
0g log / du Bu) B Any
1
B
-log(1 Ao)
(66)
2
1 1 Au
17

---

Published in Transactions on Machine Learning Research (03/2024)
where before
b2 = hu + +og (u.:(u) + uBy
(67)
1 ttē
hy
C.. 1=
(68)
N
2
Bi
1
B3:0g
1
(69)
a
B
P
# B BBcú.
Σ و100g
(70)
N
N
Av
Au
N n
M Σ
(71)
N
(72)
Then, the edge contributions can be expressed using standard simplifications for SBM:
Σ )(S))
Σ log
Σ Cu. xt N²
(73)
(iJEG
For the Gaussian mixture side, we use the same approximations as before, expanding in w, integrating over the messages and simplifying. We remove the constant part g(B,0) obtain
(1a) = V Bosdga - M
N (63ot + añov + 1 00300)
(74)
Last we replace Av by its expression and o' =1
=1 - uif we assemble the previous equations and we obtain
d
Nò -o=
Σ log
1 II Σ
Cu,iX Rosi
Σ
log
Cu, x "xi"" i-
(75)
kEOi
(W)EG
+ Σ 2 1 Au
B
log(1 + +Au)
-
Σ 1
(V
1 BB:dgu N
H
11 (- 02
+ iifov - [03
N 2
3
Parameter cstimation In case the parameters 0 == (c,, Cos p)) of the CSBM are not known, their actual values are those that maximize the free entropy. This must be understood in this manner: generate an instance of CSBM with parameters 8"; we compute the fixed point of AMP-BP at f and compute o(0); then Φ is maximal at 0= 0"
One can find 0* thanks to grid search and gradient ascent on Φ. We compute the gradient of the free entropy & with respect to the parameters (c,, co: p). This requires some care: at the fixed point, the messages (i.e. X. a, and ov) extremize o and therefore its derivative with respect them is null. We have
0g
1
Σ (U)EG
EX Eng. CusXa
(76)
N
0 = 4
1
+
Σ
En Xu X Jot
(77)
N
Ene CusXa ( X1
(U)EG
0,0 = 2N
Σ 4
Bacigs -
-3---0 Σ
1
a
(78)
VAN
We emphasize that in these equations the messages are the fixed point of AMP-BP run at (ce Co. At each iteration one has to run again AMP-BP with the new estimate of the parameters.
18

---

Published in Transactions on Machine Learning Research (03/2024)
A clever update rule is possible. We equate the gradient of & to zero and obtain that:
4 4 N
Σ
ix
(79)
Ens Cu.XX "x."" x
(K))E
En Cu, -u xx
Co
Σ
Ene CuiXa xte"""
(80)
(W)EG
Li Br:0gu
(81)
E + Σ. 02
These equations can be interpreted as the update of a maximizattion-expetaation algorithm: we enforce the parameters to be equal to the value estimated by AMP BP.
We remark that these updates are those of standard SBM and Gaussian mixture. The difference with CSBM appears only implicitly in the fixed-point messages.
C
Dense limit
We state the dense limit of the CSBM and the associated belief propagation-basel algorithm.
The dense limit is defined by an average degree d = (c: + co)/2 x co of order N and G; - Co vvN. The adjacency matrix A can be approximated by a noisy ran matrix whose noise is related to the parameters of the SBM (Lesieur et al.] 2017 Deshpande al. 2018 The dense CSBM a joint low-rank matrix factorization problem.
One can write belief propagation for this composed problem and simplify them done in part The resulting algorithm is made of two AMP parts that exchange messages. We call it AMP-AMP.
To state the algorithm we need to introduce a transformed adjacency matrix and an inverse noise
Sij = 2 ( 1
Ai 1-1 -
v2
A
= 4d(1 d)
(82)
where d= d/N O(1) and A being the binary adjacency matrix. We define the input function
(u(B,Pt) = Ev=+1 Pu(uuee"
(83)
Em=i1 Per Purlu)eB
The algorithm then stated in Algorithm 2
The performance of this algorithm can be tracked by a few scalar equations called state evolution (SE) equations. We define the order parameters
m
Σ N
m
Σ
Ug.
(84)
M
3
1
These are the overlaps (or magnetizations) of the estimates step with respect to the ground truth. The SE for AMP-AMP CSBM read
m' |1 m A
(85)
a
m = p (1 (1-pp --,))uuo,w
taanh (m''u + Vnnw) u²]
(86)
m++1 jum
(87)
++ J
where d Rademacher and W is a standard scalar Gaussian.
On can prove rigorously that AMP-AMP follows these SE equations, establish its performances and prove that they are Bayes-optimal.
19

---

Published in Transactions on Machine Learning Research (03/2024)
Input: features Be E RPNN, transformed adjacency matrix S, prior information Pr.
9 g Bl/ 0 + Au)
ov - 1V11 + Av)
Initialization: a 2+) 1 + c¹. 0g = c²: 0, where e' and ex are small centered random variables in R. Repeat until convergence:
AMP estimation of à
Bi
P Σ
Bartletl)
_ oov!!
a
ob 1 0/3
(1).2
B
Beu =
V
A Sk
1]
Σ
o
AMP estimation of
VN
N
k
k
Au
(2).2
N
((+1) = Su(Biu + By, Pv.))
B
1 V N
Σ
B
(t)
Update time +
N
Output: estimated groups sign(ú.).
Algorithm 2: The AMP-AMP algorithm.
Multiple unbalanced communities
We state a more general formulation of AMP BP in case there are multiple communities.
We consider r O(1) unbalanced groups; they are encoded by the canonical base vectors of IR" i.e., for == N, u; E (11,0,0....) (0. (0.1............ We assume they are drawn independantly according to Po for all i.
We consider symmetric connectivity matrix C' E gexr and the graph is generated by
P(Ac 1/u;, uz) = /uang/N
(88)
where we used the notation Cur.uy for uf Cuy. The fcatures are
H T N
Bs
UB ug
Zzs
(89)
for 3 = 1 P, where U3 ~ NO0 Id,) determine the randomly drawn centroids and Zz: is standard Gaussian noise. The semi-supervised prior is
Pu. =
8 if ieE.
(90)
Po(() if i
We work in the high-dimensional regime N + 0o, N/P ==)===00),==001 0(1) and the coefficients of C of order one.
We derive the resulting AMP-BP algorithm following Decelle et al. 2011 on the SBM side and Lesieur et al. (2016) on the high-dimensional Gaussian mixture side. One needs to merge these two algorithms along the same lines we did for the case r = 2. In the following we consider variables 0, and 0g RT. The resulting algorithm stated in Algorithm
E Details on numerical simulations
To define and train the GNNs use the package provided by You et al. 2020 generation of the CSBM dataset.
We implemented the
20

---

Published in Transactions on Machine Learning Research (03/2024)
Input: features B, adjacency matrix A, affinity ma- trix C, prior information Pu...
Estimation of the field h
Initialization: for (if) E G, Xa,
(-)((0) = c +
(u)( a E. (s), 0a ca = 0, where
he = N
ΣΣ Cs,u,
Xu;
(.(0
e and Ea zero-mean small random variables in R".
91
BP update of the messages x for (ij) G and of marginals x*
Repeat until convergence:
o = diag(ū; a000 0;
T.())
(+i((t+1 t Pu.((s) B Av -
diag(s) being the r x r diagonal matrix filled with 8.
7i-3
AMP update
II EC k+1.(1))
kEBRV ME
Au N
T.00
X Pu,(s)) -hatt Av8/2
Z
Bi V N
1 Σ
B a (1)
11
Eobafe
II Ca
N
RED:
a(++) + (I, + Au) - Bi
Øy == = (T, + Au)
3 and Z' being normalization factors. BP estimation of á
AMP estimation of
Av = N
1
Σ
(T) 3
a(t+1) Σ uuxe
3
B
By BBse i
Update time ++++1. Output: estimated means ú and Ca-
3
Algorithm 3: The multi-commmnnity AMP- BP algorithm.
Intra-layer parameters: we take the internal dimension h 64; we use batch normalization; no dropout; PRcLU activation; add aggregation; convolution operation in (gencralconv, genconv, gatconv) (as defined in the config.py file).
Inter-layer design: we take K E f1,2,3,4) layers of messago-passing: no pre-process layer; one post- process layer; stack connection.
The batch size is one, we train on the entire graph, revealing a proportion of labels; the learning rate x 10-3; we train for forty epochs with Adam;; weight decay x 10-4.
Training configuration:
For each experiment, we run five independent simulations and report the average of the accuracies at the best epochs.
For the logistic regression, we consider only x= 0. We train using gradient descent. We use T.2 regularization over the weights and we optimize over its strength.
21

---

Published in Transactions on Machine Learning Research (03/2024)
F Supplementary figures
F.1 The AMP-BP algorithm
We provide experimental evidence showing that for AMP BP the number of steps to converge does not. depend on N and is order ten.
N=3x 10a
N- 10
convergence time
Hip
N x 10
N- 10a
10
0.0
0.5
1.0
1.5
2.0
A
Figure Convergence time of AMP-BP. Average number of iterations for AMP-BP to converge. Convergence is achieved when the overlap Yu varies by less than 10-3 between two iterations. a 10, n²2 4, p = 0.1, d 5. We run ten experiments per point.
We check the correctness of the AMP BP we derived with Monte-Carle simulations. They give very close results.
1.0
O, AMP BP
P=0, MCMC
0.8
+ 0.1, AMP BP
p= O.I, MCMC
0.6
0.4
0.2
0.0
0.0
0.5
1.0
1.5
2.0
Monte- Carlo sinulation. Overlap qu obtained by AMP BP and by sampling the posterior thanks to the Metropolis algorithm (MCMC), X. N 10 per point.
Figure 7:
10, n²² 4, d= 5. We run five experiments
22

---

Published in Transactions on Machine Learning Research (03/2024)
F.2 Comparison against graph neural networks
We compare the performance of range of baselines GNNs to the optimal performances CSBM.
We report the results of section 4.2 for two supplementary types of convolution. The experiment is the same as the one illustrated by Fig. left, where we train a GNN on CSBM for different number layers at many surs Fig. is summarized in Fig. middle, where we consider only the best K at each X.
1.0
1.0
0.6
0.6
96
96
0.4
0.4
AMP-BP
logistic regression
0.2
K I
K- 2
K=
K ==4 4
0.0
0.0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
À
Figure Comparison GNNs of various architectures. Overlap du achieved by the GNNs, vs the sor X for different numbers of layers K. Left: graph convolution; right: graph-attention convolution. The other parameters are N = 3 10 10, 2r² 4, d = 5, 0.1. We run five experiments per point.
We let going to zero to obscrve the effect of the training labels and how the accuracy diminishes.
0.3
0.2
0.1
AMP BP
0.0
GNN
0.0
0.1
0.2
0.3
0.4
Figure 9: Effect of training labels. Overlap qU vs p. for AMP-BP and GNN (general convolution, K 2). The other parameters are N 3 104 X 0.5, a 10, , 4, 5. We run ten experiments per point for AMP BP, five for the GNN.
23


Reviews:
[{"review_id": "OT7t7nrSPi", "reviewer": "Reviewer_SS76", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The problem of providing an optimal algorithm for comparing the performance of GNNs in setups where they are often applied, i.e., semi-supervised classification and with nodes covariates, is of interest - previously, optimal algorithms often did not include one of the two. \n- The paper is generally well-written and easy to follow.\n- The novel algorithm has been implemented by the authors and made available (though I cannot see since it is removed by the double blinded review) so that users of GNNs can easily compare to it in their empirical performance study.\n- The paper contains an empirical study of the performance of the novel BP algorithm against recent GNNs.\n\nWeaknesses:\n- The contribution is slightly incremental, since to my understanding the BP algorithm for the semi-supervised setting is very close to the one for unsupervised classification proposed by Deshpande et al. (2018). Otherwise maybe the differences should be more clearly highlighted.\n- The considered setup lacks some justification. Why is the semi-supervised/sparse/high-dimensional setting so important? It is also not easy to follow in the introduction in which (sub)cases there already exist some optimal or supposedly optimal algorithms. The literature review is missing some important references beyond BP algorithms. \n- The concept of optimality which qualifies the algorithm is not formally defined in the paper. Besides, except for intuitions on why the algorithm should be optimal in this context, there is no proof or sketch of proof.\n- The algorithm is only derived and tested for the case of k=2 balanced communities although the authors underline that an extension to the case of k>2 would be straightforward. An implementation of the general case would add much more value to me. \n- There are quite a few imprecisions and things missing in the definitions of the model and notations.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors derive a new belief propagation (BP) algorithm for the semi-supervised node classification problem in attributed networks. This algorithm is conjectured to be optimal in the contextual stochastic block model, a random graph model with community structure and nodes covariates often used to generate synthetic data and benchmark Graph Neural Network (GNN) algorithms. The authors empirically show that there is a gap of performance between the BP algorithm and SOTA GNNs.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Requested changes:\n- The authors should review the first section (maybe adding a separate section for the literature review) to include references on optimal methods for semi-supervised and unsupervised node classification in the CSBM and closely related models (e.g., feature-adjusted stochastic block model). Some references are included in Sections 2 and 3 but this reduces the overall clarity.\n- The authors should correct the introduction of formal notations and clarify the description of the model in Section 2.2. For instance the latent variable v and the group memberships u are not previously defined. Equations 9 and 10 are also unclear: p_i(t) is not defined and I do not understand why (10) gives the MMSE estimator.\n- The authors should reformat Section 3: the notations in the diagram at the start of the section are not coherent with the following equations (14), (15), (16). The algorithm on p.5 should be better isolated from the rest of the text and maybe written in single column to make it clearer. Also it is not formal to write “the $\\epsilon$s”, etc.\n- I think the contributions should be strengthened, e.g., by proving the optimality, a more general version of the algorithm, or by adding experimental results. For instance it would be interesting to compare the BP algorithm in settings with noisy labels or mis-specified settings where it can underperform.\n- Some clarifications are needed: What does “approximated asymptotically exactly” on p.8 mean? Why in Figures 4 and 5 the number of layers and neighborhood sizes in the GNNs are not validated hyperparameters?", "broader_impact_concerns": "I have no concern about the broader impact.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "NF7j4YRvXR", "reviewer": "Reviewer_S61R", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The authors make a compelling case for comparing GNN approaches with \"simpler\" methods. I agree with them that methods such as this could help inspire better GNN algorithms. \n- The paper is well-organized and clearly written. \n- An implementation of the algorithm is provided. \n\n\nWeaknesses:\n- It is conjectured that the proposed algorithm is optimal, but no proof is provided.\n- The conjecture pertains to a particular subsubset of graphs generated by the CSBM. \n- The proposed algorithm could return solutions that are far from the optimal. The authors do not discuss these cases and what practitioners should look out for.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This manuscript proposes an algorithm for classifying nodes in graphs generated under the contextual stochastic block model (CSBM). A conjecture is put forth that the algorithm's predictions approach the ground truth with an error that vanishes in the limit of infinite nodes N and infinite node features P with constant ratio N/P. This conjecture is supported by an argument and experiments. \n\nFinally, the code for this algorithm is provided in supplementary materials, so that it can be used as a benchmark with which to compare popular graph neural network (GNN) graph node classifiers.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Equation 2, which defines the generative model, seems to have errors? The writing and notation was difficult to parse.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "BZZTDlAfHc", "reviewer": "Reviewer_hkt1", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n(+) Great literature review, which clearly demonstrated the contribution of this work on top of existing literature.\n\n(+) Extensive experiments and comparison with GNNs, including those specialized to cSBM such as Baranwal et al. (2023). \n\n(+) The key message that existing GNN is still sub-optimal, at least for cSBM.\n\n(+) The paper is very well-written.\n\nWeaknesses:\n\nI think this work is great and the weaknesses below should not be used as an objection to its acceptance.\n\n(-) While well-motivated, the optimality of the proposed algorithm is not proven.\n\n(-) The work raises the problem of \"GNN is sub-optimal\" by showing that AMP-BP outperforms GNNs. However, it does not discuss how we can modify GNN based on the lesson we learned from AMP-BP. I think the work can be even better if a discussion and preliminary attempt to improve GNNs are included.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors study the algorithm, AMP-BP, which is conjectured to achieve the optimal node classification accuracy on the contextual stochastic blockmodel (cSBM). The method is extensively tested and compared with graph neural networks (GNNs), which has demonstrated the performance gap between existing GNNs to a potential optimal performance for cSBM. A simple-to-use implementation is also provided.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "It would be great if the two (especially the last) weaknesses could be addressed. Yet it is also fine in its current form.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper was reviewed by three expert reviewers. All reviewers recommended acceptance of the paper and I agree with them. The reviewers initially complained about the clarity of the paper, and the authors made efforts to improve the presentation in the revision. All three reviewers also raised concerns regarding the use of the term "optimal" in the title and throughout the paper. The authors made clear in their response that the optimality of BP for the simpler sparse SBM has not been proven yet and is still a conjecture. I am thus recommending that the authors modify the title of the paper and replace the word "optimal", which seems somewhat misleading, with other terms/phrases that indicate that optimality actually remains a conjecture. For example, the authors could use the terms "towards optimal inference", but I leave this decision to the authors.
Decision: Accept (poster)