Exact recovery and Bregman hard clustering of node-attributed Stochastic Block Model
Authors: Maximilien Dreveton
Felipe Schreiber Fernandes
Daniel R. Figueiredo
Venue: NeurIPS 2023 poster (2023)
Keywords: community detection
stochastic block model
bregman divergence
TL;DR: This article derives information-theoretic threshold for exact recovery in node-attributed SBM with general interactions, and proposes an algorithm based on joint-likelihood maximisation to recover the communities.

Abstract: Classic network clustering tackles the problem of identifying sets of nodes (communities) that have similar connection patterns. However, in many scenarios nodes also have attributes that are correlated and can also be used to identify node clusters. Thus, network information (edges) and node information (attributes) can be jointly leveraged to design high-performance clustering algorithms. Under a general model for the network and node attributes, this work establishes an information-theoretic criteria for the exact recovery of community labels and characterizes a phase transition determined by the Chernoff-Hellinger divergence of the model. The criteria shows how network and attribute information can be exchanged in order to have exact recovery (e.g., more reliable network information requires less reliable attribute information). This work also presents an iterative clustering algorithm that maximizes the joint likelihood, assuming that the probability distribution of network interactions and node attributes belong to exponential families. This covers a broad range of possible interactions (e.g., edges with weights) and attributes (e.g., non-Gaussian models) while also exploring the connection between exponential families and Bregman divergences. Extensive numerical experiments using synthetic and real data indicate that the proposed algorithm outperforms algorithms that leverage only network or only attribute information as well as recently proposed algorithms that perform clustering using both sources of information. The contributions of this work provide insights into the fundamental limits and practical techniques for inferring community labels on node-attributed networks.

Exact recovery and Bregman hard clustering of node-attributed Stochastic Block Model
Maximilien Dreveton School of Computer and Communication Sciences EPFL, Lausanne, Switzerland maximilien drevetooneete] ch
Felipe S. Fernandes
Daniel R. Figuciredo
Systems Engineering and Computer Science Federal University of Rio de Janeiro
Systems Engineering and Computer Science Federal University of Rio de Janeiro Rio de Janeiro. Brazil danie eacoeelccs..om ufrj br
Rio de Janeiro, Brazil felipesc@cos ufrj br
Abstract
Network clustering tackles the problem of identifying sets of nodes (communities) that have similar connection patterns. However, in many scenarios, nodes also have attributes that correlated with the clustering structure. Thus, network information (edges) and node information (attributes) can be jointly leveraged to design nigh-performaace clustering algorithms. Under general model for the network and node attributes, this work establishes an information-theoree criterion for the exact recovery of community labels and characterizes phase transition determined by the Chernoff-Hoe Helliffee-llleerrrrrreee divergence the model. The criterion shows how network and attribute information can be exchanged in order have exact recovery (e.g.. more reliable network information requires less reliable attribute information). This work also presents iterative clustering algorithm that maximizes the joint likelihood, assuming that the probability distribution of network interactions and node attributes belong exponential families. This covers a broad range of possible interactions (e.g., edges with weights) and attributes (e.g., non- Gaussian models), well sparse networks, while also exploring the connection between exponential families and Bregman divergences. Extensive numerical experiments using synthetic data indicate that the proposed algorithm outperforms classic algorithms that leverage only network or only attribute information as well as state-of-the-ard algorithms that also leverage both sources information. The contributions of this work provide insights into the fundamental limits and practical techniques for inferring community labels on node-attributed networks.
Introduction
Community detection or network clustering-the task of identifying sets of similar nodes in network- fundamental problem in network analysis 4 [ 18), with applications diverse fields such as digital humanities, data science and biology. In the classic formulation, set of communities must be determined from the connection patterns among the nodes single network. simple random graph model with community structure, the Stochastic Block Model (SBM), has been the canonical model to characterise theoretical limitations and evaluate different community detection algorithms [
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

However, nodes of many real-world networks have attributes or features that can reveal their identity as an individual or within a group. For example, the age, gender and ethnicity of individuals in a social network [27]. the title, keywords and co-authors of papers in a citation network [32,, or the longitude and latitude of meteorological stations in weather forecast networks [] In some scenarios, such attributes can be leveraged alone to identify node communities (clusters) without even using the network.
Thus, a modern formulation for community detection must consider network information (edges) and node information (attributes). Indeed, recent works have designed community detection algorithms that can effectively leverage both sources of information to improve performance. Various methods have been proposed for clustering anteibeeri networks, including modularity optimisation [14, belief propagation [15), sion [33, semidefinite programming (37, spectral algorithms
algorithms [24] [4]. information flow compres-
2 7 25 and iterative likelihood based
methods g
fundamental problem in this new formulation fusing both sources of information: how important is network information in comparison to node information given problem instance? Intuitively, this depends on the noise associated with network edges and node attributes. For example, if edges are reliable then the clustering algorithm should prioritize them when determining the communities. However, most prior approaches adopt some form of heuristic when merging the two sources of information [14 16 37]. A rigorous approach to this problem requires a mathematical model, and one has been recently proposed.
The Contextual Stochastic Block Model (CSBM) is generalization of the SBM where each node has random attribute that depends its community label. While the model formulation is general (in terms of distribution for edges and attributes), CSBM has only been rigorously studied in the restrictive setting where the pairwise interactions are binary (edges are present not) and the node attributes are Gaussian 115). In this scenario, the phase transitions for exactly recovering the community labels and for detecting them better than a random guess has been established. Moreover, the comparison with the respective phase transitions in SBM [ and in Gaussian mixture model [I]] 26 (with no network) highlight the value of jointly leveraging network and node information in recovering community labels.
However, real networks often depart from binary edges and Gaussian attributes. Indeed, in many scenarios network edges have weights that reveal information about that interaction and nodes have discrete non-Gaussian attributes. This work tackles this scenario by considering CSBM where edges have weights and nodes have attributes that follow some arbitrary distributions. Under this general model, this work the first to characterise the phase transition for the exact recovery of community labels. In particular, the Chernoff -eerooff-lllliggeer divergence, initially defined just for binary networks [3), extended to this more general model. This divergence effectively captures the difficulty of distinguishing different communities and thus plays a crucial role in determining the limits of exact recovery. The analysis reveals an additional term in the divergence that quantifies the information provided by the attributes of the nodes. Moreover, it quantifies the trade-off between network and node information meeting the threshold for exact recovery.
The CSBM generates weighted networks that are complete (all possible edges are present) when edge weights follow a continuous distribution. However, most weighted real networks are sparse. To model sparse weighted networks and to provide a practical community detection algorithm, we consider CSBM whose weights belong to zero-inflated distributions. More precisely, we suppose that conditioned on observing an edge, the distribution of the weight of this edge belongs to an exponential family. Similarly, the node attribute distributions are also assumed to belong to an exponential family. Working with exponential families is motivated by two factors. Firstly. exponential families encompass a broad range of parametric distributions, including the commonly used Bernoulli, Poisson, Gaussian, or Gamma distributions. Secondly, there exists an intricate connection between exponential families of distributions and Bregman divergences, which has proven to be a powerful tool for developing algorithms across a variety of problems such as clustering, classification, and dimensionality reduction 6 13
This connection between Bregman divergences and exponential families has been previously explored in the context of clustering dense networks (all possible edges are present) (23]. In contrast, this work proposes an iterative algorithm that maximizes the log- likellhoooo of the model, for both dense and sparse networks. This is key difference with many previous works which either study only dense
2

---

weighted networks (9 [24] or binary networks with Gaussian attributes 15 34]. Simulations on synthetic networks demonstrate that our algorithm outperforms state-of-the-arr approaches in various settings, providing practical techniques for achieving accurate clustering results.
The article is structured follows. The relevant related work is discussed in Section 2 Section 3 introduces the model under consideration along with the main theoretical contributions on exact recovery. Section focuses on sparse networks with edge weights and node attributes drawn from exponential families and introduces an iterative algorithm for clustering such networks. Numerical results and comparisons to prior works are presented in Section and Section 6 concludes the paper.
Let Ber(p) denote a Bernoulli random variable (I.v.) with parameter p. Nor o) Gaussian n.v. with mean m and standard deviation ø, and Exp(A) an exponential r.v. with mean A-1 The notation [K] refers to the set (1,... ,K), while Ag. stands for the i-th row of matrix A.
Notations
2
Related work
2.1 Exact recovery in SBM with edge weights and node attributes
Community detection in classic SBM (binary edges) is a well-understood problem with strong theoretical results concerning exact recovery and efficient algorithms with guaranteed accuracy [1] However, extending the classic SBM to weighted networks (non-binary edges) with arbitrary distributions an ongoing research area. Most existing work in this scenario has been restricted to the homogeneous model"] where edge weights within and across communities are determined by two respective distributions. Moreover, existing works often restrict to categorical or real-valued weights [22 (6), or to multiplex networks (multiple edge types) with independent and identically distributed layers (29]. However, a recent work has provided strong theoretical foundation the homogeneous model with arbitrary distributions [5], highlighting the role of the Rényi divergence as the key informatioon-hhoreee quantity for the homogeneous model.
In non-homogeneous models, a more complex divergence called the Chernoff-Hellinger divergence quantity for exact community recovery [3]. However, the
the appropriate information-theom Hellinger divergence as originally defined in [3] for binary networks does not have an intuitive interpretation, and its extension to non-binary (weighted) networks is challenging. For example, the exact recovery threshold for non-homogeneous SBM whose edges are categorical random variables has been established 38). but this threshold expressed as a condition involving the minimization of mixture of Kullback-Leibler divergences over the space of probability distributions. Although the relationship between Kullback-Leible and Chernoff divergences are known (see for example [35] Theorem 30-32)), the specific technical lemma required to link them to the Chernoff- Helloffffeeeeerrreeeeeee divergence not straightforward (see 38 Claim 4)).
expression of the Chernoff-Hellinger
Another generalization of the SBM allows for nodes to have attributes that provide information about their community, such as the Contextual SBM (CSBM) [15]. The CSBM has only been rigorously studied in the setting where edges are binary and node attributes follow Gaussian distribution. In this scenario, the phase transition for exact recovery for the community labels has been established (2 & 15). A natural generalization is to investigate the model where network edges have weights and nodes have attributes that follow arbitrary distributions. Indeed, this one of the main contributions of this work: Expression (3.4) gives a straightforward yet crucial formula for the phase transition for exact recovery, also providing a natural interpretation for the influence both the network and node attributes. Moreover, Expression (3.4) also applies when no node attribute is available, thus providing the exact recovery threshold for non-homogeneous model and arbitrary edge weight distribution, a significant advancement in the state of the art.
2.2 Algorithms for clustering weighted networks with node attributes
Algorithms leveraging different approaches have been proposed to tackle community detection in networks with edge weights and node attributes. common principled approach is to determine the community assigmment that maximizes the likelihood function of model for the data. However, optimizing the likelihood function computationally intractable even for binary networks. Thus,
Also known the planted partition model.
3

---

approximation schemes such as variational inference and -ikulo-ik methods are often adopted. For instance, [24] introduced variational algorithm for clustering homooooeessuus weighted SBM with arbitrary distributions. Another approach for clustering node-attributed SBM whose edge weights and attribute distributions belong to exponential families is [2] These two approaches assume that the network is dense (all edges are present and have non-zero edge weight). However, most real networks are very sparse (most node pairs do not have an edge) and this work focuses this scenario. Another very recent work tackling sparse networks is the IR_sLs algorithm from [8] although its theoretical guarantees assume binary networks with Gaussian attributes.
The iterative clustering algorithm presented in this work maximizes the pseudo-likelihood likelihood likelihood by assuming that the probability distribution of network edges and node attributes belong to exponen- tial families. This yields a direct connection with Bregman divergences and establishes an elegant expression for the likelihood function. This connection has also been leveraged in 23 however, their model is restricted to dense weighted networks (all edges are present). This work (more specifi- cally, Lemma 2). demonstrates that this connection can also be applied to sparse weighted networks (using zero-inflated distributions to model the weights). This extension enhances the applicability of pseudo-likelihood algorithms using Bregman divergence to a broader class of scenarios, namely weighted sparse networks with node attributes.
3 Model and exact recovery in node-attributed SBM
3.1 Model definition
Consider a population of n objects, called nodes, partitioned into 2 2 disjoint sets, called blocks communities. A node-labelling vector 2 (21...., Z,) that 2; indicates the block of node i. The labels (blocks) of nodes are random variables assumed to be independent and identically distributed such that P(z; k) Ty for some vector (0, 1)K verifying that >n & = 1. The nodes interact in unordered pairs giving rise to undirected edges, and X' is the measurable space of all possible pairwise interactions. Additionally, each node has an attribute that is an element of a measurable space y. Let X E x x denote the symmetric matrix such that Xıj represents the interaction between node pair (ij). and by Y "Yi,".., ,Y,) ) ) the node attribute vector.
E [K] represents this partitioning so
Assume that interactions and attributes are independent conditionally the community labels of the nodes. Let (x) denote the probability that two nodes in blocks and have an interaction x E X, and h4 (y) denote the probability that node in block 1 [K] has attribute y E Y Thus,
12
((,Y
II ISicisn
fa.., (X
II hr, (Y)).
(3.1)
In the following, the interaction spaces X,Y' might depend as well the respective interaction probabilities f, The number of nodes n will increase to infinity while K and æ are constant. For an estimator 2 E [K]" of z, we define the classification error
loss(z, 2) = min Ham oo 2),
rESk
where Sx is the set of permutations of [K] and Ham(.;) is the hamming distance between two vectors. An estimator - = 2(X,Y) achieves exact recovery if IP (loss(z, (2, 2) 2 1) o(1).
3.2 Exact recovery threshold in node-attributed SBM
The difficulty of classifying empirical data in of K possible classes is traditionally measured by the Chernoff information [12]. More precisely, in the context of network clustering, let CH(a, b) = CH(a, b, π, f h) denote the hardness of distinguishing nodes that belong to block from block b. This quantity is defined by CH(a.b) = sup Ca,(a,b), 1E(0.1)
(3.2)
where
K
Te D2 (foellfac) + 1 D, (hallha)
CH,(a,b) b) -11 (1-t)
Σ
(3.3)

---

is the Chernoff coefficient of order t across blocks and b, and ll)) - - log ((z))""(()))
is the Rényi divergence of order t between two probability densities f.g [35]. The key quantity
assessing the possibility impossibility of exact recovery in SBM is then the minimal Chernoff information across all pairs of clusters. We denote it by I= [[T, f, h), and it is defined by
1 =
min CH(a,
(3.4)
a.be[K] agb
The following Theorem provides the information- theoretic threshold for exact recovery in node- attributed SBM.
Theorem 1. Consider model (3.1 with Ta > for all a E [K]. Denote by a", b' the two hardest
blocks to estimate, that is CH(a" (6))
- = Suppose that E (0, lim a "HHH(a" b*) exists
n log
and is strictly concave. Then the following holds:
(i) exact recovery is
impossible if lim n <1;
n--000 log n
(ii) exact recovery is cetimaatioon-hooettiiin possible if lim n-000 log n
The proof for Theorem T is provided in the supplemental material. The main ingredient of the proof is the asymptotic study log-likelihood ratios. More precisely, let L(z) P(X, [2). The application of Chernoff bounds provides an upper bound on - log P (log L(z) 2 log L(z)), where denotes the correct block structure and x' [K]" is another node-labelling vector (see Lemma I in the supplement). We can use this upper bond to prove that the maximum likelihood estimator (MLE) achieves exact recovery I > n 1 log n. Reciprocally, if / < n- log n, we show that whp there exist some "bad" nodes for which & arg ma P (X. 1=-1 = =a). a). In other words, even in setting where an oracle would reveal = (i.e., the correct block assignment of all nodes except node i), the MLE would fail recovering 2,. Establishing this fact requires to lower bound - log P (log L(z) 2 log L(z')) where 2' E [K] is such that Ham 2, 2') = 1 (i.e., z' correctly labels all nodes except one). This lower bound obtained using large deviation results for general random variables [10 30 To apply these results, the strict concavity of the limit n(log n is needed. In most practical settings, this assumption is verified, except in some edge cases (see Examples and 2
Let us now provide some examples of applications of Theorem [
Example 1 (Binary SBM with no attributes). Suppose that fab Ber(aas log n) where aub are constants. A Taylor-expansion of the Rényi divergence between Bernoulli distributions leads to
= (1+ log min sup
Σ [tasa + +1 (1-1) oh
a&b (E(0.1
which indeed coincides with the expression of the Chernoff-Hellinger divergence defined in (3). We also note that the limit n(logn)-11 -1 is strictly concave long as the Oaa not all equal Example (Binary SBM with Gaussian attributes). Suppose that fab Ber(a log and ha Nor(Ha log n,
o² La), where aabb and pa are independent of n. Then,
T= (1 (1+) log
1-t Σ [toree + +1 (1- -t)acc O0 +
||m6 Ma
min sup
ozz (E(0.1)
20
In particular, the technical conditions of Theorem 7 Jure verified if we rule out the uninformative case where all the aub's 's and the pa 's are equal to each other. Thus, exact recovery is possible if
1lub ++lllub -aal2
Σ ne [tase (1 t)aac afr + min sup
1.
a&b (E(0.1)
202
Further assuming that Club al b) ;1(a # b) (homogeneous interactions) and .k) (uniform block probabilities), the expression of simplifies to
K
logn n n
(Vā v
I = =1+ o(1))
S
IIndeed, since the matrix a = (arat) is symmetric, this implies that there exists a + b such that 3c e [k] Ola * abe.. The function f() = E. ne [tase + (1 - t) al. 1-t) is continuous and strictly concave, hence su f(t) is strictly concave.
5

---

where A = min |pe 1Ma-M6ll2 This last scenario recovers the recently established threshold for exact adb
recovery in the Contextual SBM (8).
Example 3 (Semi-supervised clustering in SBM). Consider binary interactions given by
[Ber(an - log n) [Ber(Bn-1 logn)
ifa=
sab
otherwise,
where a, B are independent of Consider semi-supervised model in which the vector of altributes is noisy oracle of the true community labels z. More precisely, for a node such that 2i = k, let
if y = 0, if y
hx(y) = P(Y; =)
7
if E [K])(E),
K-1
with no + +m = 17. A bit of algebra shows that exact recovery is possible if
(Va-v8)
2 log
(1- - 1 - 1/2
v /nuuh > K.
log
When To = (perfect oracle), the condition simplifies to (vā - vbj² 2log(1-n) > K. Note that
log
the oracle term is non-negligible only if log (1 77 Z log n, previously established [37]. This
last condition very strong since it implies 1 Z 1/n, and hence the oracle must provide the
correct label for almost all nodes.
4 Bregman hard clustering of sparse weighted node-attributed networks
In this section, we will propose an algorithm for clustering sparse, weighted networks with node attributes. When present, the weights are sampled from exponential family, and the node attributes also belong to an exponential family. In Section[4.]] we provide some reminder of exponential families. We derive the likelihood of the model in Section 4.2 and present the algorithm in Section 4.3
4.1 Exponential family
exponential family Eg parametric class of probability distributions whose densities can e e00 where the density is taken with respect to an appropriate measure, 0 θ is function of the parameters of the distribution that must belong to an open convex space O and vé is a convex function.
be canonically written as po.yi (x)
We consider the model defined in (3.1). such that fas are zero-inflated distributions and are given by (4.1)
fos( (1 (1-Pa) (=))))))(()) (z),
where Pas [0. 1] is the interaction probability between blocks and b, 60(x)) is the Dirac delta at zero, and Fas is probability density with no mass at zero. Note that this model can represent sparse weighted networks, edges between nodes in blocks and b are absent with probability Pab-
Finally, suppose that the distributions {fab and { belong to exponential families. More precisely.
fab(x) = 10aa..>>-00.. and ha(y) = < w/> o(ne),
(4.2)
for some parameters a 7a, and functions v. Φ. The following lemma provides the expression the Chernoff divergence of this model.
Lemma 1. Let fab and ha be defined as in 4.1 constant and < We have
4.2
Suppose that Pab anad where aab is
= (1 o()) min sup adth 1E(0.1)
Σ cE[K]
tPac (1-
- t))bcc 1-t e -do000ce0000))) 1 + IJ(naalln)) j
where (0 (bc) tx (0
(1 (Obc)) (10 + (1 t))bcc.
In combination with Theorem Lemma provides the expression for the exact recovery threshold
for node-attribute networks with interaction and attribute distributions given by (4.1-4..2)

---

4.2 Log-likelihood
Given a convex function v, the Bregman divergence dæ: m x F + E is defined by
(z, (xx) (0)) < y. V >
The log-likelihood of the density P of exponential family distribution is linked to the Bregman divergence by the following relationship (see for example [6] Equation 13I)
log log = -dw- (2,, (1) + (x),
(4.3)
where μs = EEp o (X) is the mean of the distribution, and v denotes the Legendre transform of 4/, defined by 30 (t) = supol< 0, > (0) The following Lemma provides an expression for the log-likelihood of fab when fab is distribution belonging
zero-inflated exponential family.
Lemma 2. Les fab be probability density as defined in (4.1) 442 For y E (0, 1), let dKL (x, v) be the Killback-Leibler divergences between Ber(r) and Ber yy), and let H (x) = x log x + (1
x) log(1 - z), with the usual convention 0 log 0 = 1. Then,
-log fab( dKL. (x)(paa)) + sdg- Mab) s1b(()) (z) H(s).
where s = 1(x #0)
Proof. To express log fas(2), we first note that
log far()) (1 - s) log(1 Pab) + Pls Pas + (og((f(())),
where e 1(x + 0). The result follows by adding and subtracting (b)) in the previous expression and expressing log (z) with a Bregman divergence as in (4.3)
Suppose that X,Y Y follow the model 3.1
with probability distributions given by -4.1244.2 Let A
be a binary matrix such that Aij 1 Xx; 1j + 0). We have
(X, Σ
dKL (Aij, + Andde (Xsj, (zzzy) ) + do (Yi,
t
where the additional term e is a function of X, Y but does not depend on z. Denoting 2 E (0, 1]nxK
the one-hot membership matrix such that Z₁A = 1(2; = k), observe that P2,2, = (Zp7²) 39 where a symmetric matrix with the interaction probabilities between different blocks, 2,;, (Z where ys is a symmetric matrix with the expected value of the interaction between different blocks if
(edge weights), and V2, (ZTv); where is a vector with the expected value of the attribute for different blocks. Thus, up to some additional constants, the negative log-likelihood log P(X, Y Z)) equal to
Σlp dkL (Ar., (Zpz"), + de (ZuZ"), + dg- (Z. tc,
1 2
(4.4)
where d/ (d),(B, (B,C= - 1(B, + Oydg- (B,, Cj) for two vectors B, C R.
4.3 Clustering by iterative likelihood maximisation
Following the log-likelihood expression derived in (4.4), we propose iterative clustering algorithm that places each node in the block maximising IP (X,Y 2-1. 2; = a) for 1 I a S K, the likelihood that node i is in community given the community labels of the other nodes. z-1. Let Z (fa) denote the membership matrix obtained from Z by placing node i in block a, and let Lia ((())) denote the contribution of node to the negative log-likelihood when node placed in block a. Equation 4.4) shows that
(Z) 2
dKL (Ar, (ZpZ"), ),) + do. (Xr, (ZuZ²),) + do (Y, (2"v))) 2
(4.5)
7

---

where the μ and y/ in the equation above must be estimated from X, Y, and the community
membership matrix Z. Let -= P(A, Z), f = م(X,, Z). and & ,YY, 2) denote the estimators for p. and v, respectively. Their values can be computed as follows:
(A,Z) (z² 2" AZ (z' 2z²
Z) AZ) xZ,
(4.6)
Z) (2² z²Y
Note that the matrix inverse ZZ can be easily computed since 2 a K-by-K diagonal matrix. This approach is described in Algorithm
Algorithm 1: Bregman hard clustering for node-attributed SBM.
convex Input: Interactions X E X=xx, attributes Y E >)", convex functions ui", .6" clustering Zo
Let Z = Zo
repeat
Compute P. jt, i according to (4.6
Let nnew 0. K
for i ,,..., do
Let (iaa) be the membership matrix obtained from Z by placing node i in community
Find k arg max Lia (Z(a)), where Lia (Z(aa) is defined in 4.5
[K[
Let 7, = (k: = k*) for all 1,...,K K
Let 7- 7uew
until convergence;
Return: Node-membership matrix Z
A fundamental aspect of many likelihood maximization iterative algorithms such as Algorithm ! the initial membership assignment, Zn- This initial assignment often has profound influence on the final membership assignment, and thus, it is important to have an adequate initialization. In the numerical section, we proceed follows. We construct the matrix W E RRx22 such that the first K columns of W are the first K eigenvectors of the graph normalised Laplacian, while the are the first K eigenvectors of the Gram matrix YY"..
last K columns
Numerical experiments
5.1 Performance of Algorithm
We first compare in Figure T the performance of Algorithm in terms of exact recovery (fraction of times the algorithm correctly recovers the community of all nodes) with the theoretical threshold for exact recovery proved in the paper (red curve in the plots) in two settings: Figure Ta shows binary weight with Gaussian attributes, and Figure Tb shows zero-inflated Gaussian weights with Gaussian attributes. A solid black (resp., white) square means that over trials, the algorithms failed 50 times (resp., succeeded 50 times) at exactly recovering the block structure.
5.2 Comparison with other algorithms
In this section, we compare Algorithm I with other algorithms presented in the literature. We used the Adjusted Rand Index (ARI) [21] between the predicted clusters and the ground truth ones to evaluate the performance of each algorithm.
In Figure 2 we compare Algorithm with the variational-EN. algorithm of 24 and the algorithm of [3] (which is also based on Bregman divergences, but tailored for dense networks). Because both of these algorithms are designed for dense networks, we observe that Algorithm has overall better performance on sparse networks.
We also compare Algorithm D with the IR_s/s algorithm from g. This is one of the most recent algorithms for node-attrin ande-attributed SBM and it comes with theoretical guarantees (for binary networks

---

1.75
1.0
1.75
1.0
1.50
0.8
1.50
0.8
1.25
1.25
1.00
0.6
1.00
0.6
0.75
0.4
0.75
0.4
0.50
0.50
0.25
0.2
0.25
0.00
0.00
0.0
0.0 0.5
2.0 2.5 mu
3.5
3
6
alpha
(b) zero-inflated Gaussian weights with Gaussian attributes.
(a) Binary weights with Gaussian attributes
Figure Phase transition of exact recovery. Each pixel represents the empirical probability that Algorithm succeeds exactly recovering the clusters (over 50 runs), and the red curve shows the theoretical threshold.
(a) n 500, K 2, fin Ber(an log n), fout Ber(n log n). The attributes 2d- spherical Gaussian with radius (+-r /lg n, 0) and identity covariance matrix.
(b) 600, K 3, Jin (1 p)ón + p Nor(p, 1), fout (1 p)óg p Nor(0, 1) with 5n log n. The attributes are 2d-spherical Gaussian whose means are the vertices of a regular polygon on the circle of radius rllog
1.00
1.00
0.75
0.75
ARI
ARI
0.50
Algorithm 1
0.50
Algorithm
bregman [23]
bregman [23]
0.25
vem [24]
0.25
vem [24]
initialisation
0.00
initialisation
0.00
0.03
0.05
0.07
0.09
0.11
1
3
9
11
p
muin
Figure 2: Comparison of Algorithm with algorithms of 23 and 24 Error bars show the standard
deviations over 25 realisations. Attributes are 2d-spherical Gaussian attributes with radius (+11,)
(a) 100, K 2, fin = (1 Pin J6g + Poi(5), four = (1 0.03)8g + 0.03 Poi(1). (b) 100, K 2, fin (1 0.07) 5ō + 0.07 Poi(Pin), fout (1 0.04)6o 0.04 Poi(1).
with Gaussian attributes). We also compare with the EM algorithm of 341 aMSSMM, which is designed for binary networks with Gaussian attributes. Finally, we compare with baseline methods for clustering using the network the attributes alone. EM-GMM refers fitting Gaussian Mixture Model via EM on attribute data Y, and sc refers to spectral clustering on network data X.
Figure shows the results for binary networks with Gaussian attributes. Algorithm D successfully learns from both the signal coming from the network and the attributes, even in scenarios where one of them is non- non-informative. Moreover, Algorithm| I has better performance than the other node-attribuedd clustering algorithms, and those algorithms also show a large variance We also note that IR sLss and anSBM both tailor-made for binary edges and Gaussian attributes. Even in such a setting, Algorithm Srnnthmmoour outperforms these two algorithms. We show in the supplement material that when the network is weighted and the attributes non-Gaussian IR_sLs and antSBM perform poorly.
5.3 Evaluation using real datasets
The following three benchmark datasets were used to evaluate and compare the proposed algorithm: CiteSeer (n 3279, m 9104, K 6, 3703), Cora (n 2708, m 10556,
As the large variance makes the figures less readable, provide all results in the supplemental material.

---

1.0
10
0.8
ARI
CM-GMM
[M-GMM
0.4
SC
SC
Algo1
Algo1
0.2
attSBM
attSaM
IR,
0.0
15
(a) Varying edge distribution.
(b) Varying attribute distributions.
binary networks with Gaussian attributes. We take 600, K 2. Jin Ber(an -1 log n),, fout = Ber(5n log n), and 2-dimensional Gaussian attributes with unit variance and mean (+r, 0). Results averaged over 60 runs.
Figure 3: Performance
1433), and Cornell (n 183, m 298, K = 5, 1703) (all available in Pytorch Geometric). For each network, the original node attribute vector was reduced to have dimension d = 10 by selecting the best features according to the chi-square test. Algorithm assumed multivariate Gaussian distribution with d = 10 for node attributes and Bernoulli edges (these networks have no edge weights). The initialization for Algorithm| [ and attSBM used spectral clustering both node similarity matrix (using node attributes) and network edges.
Dataset
CiteSeer
Cora
Cornell
Algorithm
0.20
0.12
0.49
auSSB
0.17
0.09
0.46
EM-GMM
0.13
0.06
0.37
sc
0.00
0.00
0.02
Table 1: Average ARI results (over independent runs) for the three benchmark datasets.
Table ! shows that Algorithm outperformed the other three algorithms. Spectral clustering (sc) has near zero performance, indicating that the network structure in these data sets has little information concerning the clusters of the nodes. Moreover, both Algorithm [ and attSBM (that leverage network and node attributes) outperform EM-GMM that use only node attributes. These preliminary results indicate that Algorithm is promising even real data sets with little pre-processing.
6 Conclusion
This work made the following contributions to community detection node-attributed networks: i) extended the known thresholds for exact recovery in binary SBM non-binary (weighted) networks with node attributes, providing a clean expression for a new information-theoreiie quantity, known in the binary setting as the Chernoff-Hellinger divergence; ii) proposed an iterative algorithm based on the likelihood function that can infer community memberships from problem instance. The algorithm leverages the framework of Bregman divergences and is simple and computationally efficient. Numerical experiments indicate the superiority of this algorithm when compared to recent state-of-the-ale approaches.
Acknowledgements
The first author would like to thank Lasse Leskelä for helpful discussions and comments.
This work has been partially funded by the Brazilian-Swiss Joint Research Program (grant the Brazilian National Council for Scientific and Technological Development (CNPq), and the Carlos Chagas Filho Research Foundation of the State of Rio de Janeiro (FAPERJ).
10

---

References
[1] Emmanuel Abbe. Community detection and stochastic block models: recent developments. The Journal of Machine Learning Research, 18(1):64466653 6531,, 2017.
[2] Emmanuel Abbe, Jianqing Fan, and Kaizheng Wang- An Ep theory of pea and spectral clustering. The Annals of Statistics, 504)22355-282,8 2022.
[3] Emmanuel Abbe and Colin Sandon. Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery. In 2015 IEEE 56th Annual Symposium Foundations of Computer Science, pages 670-688, Alamitos, CA, USA, 2015. IEEE Computer Society.
[4] Konstantin Avrachenkov and Maximilien Dreveton. Statistical Analysis of Networks. Now Publishers. 2022.
[5] Konstantin Avrachenkov, Maximilien Dreveton, and Lasse Leskelä. Community recovery in non- non-binary and temporal stochastic block models. arXiv preprint arXiv:2008.04749 04790,, 2022.
[6] Arindam Banerjec, Srujana Merugu, Inderjit S Dhillon, Joydeep Ghosh, and John Lafferty. Clustering with Bregman divergences. Journal of machine learning research, 6(10), 2005.
[7] Norbert Binkiewicz, Joshua T Vogelstein, and Karl Rohe. Covariate-asssisedd spectral clustering. Biometrika, 104(2)361-377,, 2017.
[8] Guillaume Braun, Hemant Tyagi, and Christophe Biernacki. An iterative clustering algorithm for the contextual stochastic black model with optimality guarantees. In International Conference on Machine Learning, pages 2257-2291. PMLR, 2022.
[9] Andressa Cerqueira and Elizaveta Levina. A pseudo-iikelhhodd approach community detection in weighted networks. arXiv preprint arXiv:2303. 35,099 2023.
[10] Narasinga Rao Chaganty and Jayaram Sethuraman. Strong large deviation and local limit theorems. The Annals of Probability, pages 1671-1690, 1993.
[11] Xiaohui Chen and Yun Yang. Cutoff for exact recovery of Gaussian mixture models. IEEE Transactions on Information Theory, 67(6):4223 4238, 2021.
[12] Herman Chernoff. A measure of asymptotic efficiency for tests of hypothesis based on the sum of observations. The Annals of Mathematical Statistics, pages 493-507, 1952.
[13] Michael Collins, Sanjoy Dasgupta, and Robert E. Schapire. A generalization of principal components analysis to the exponential family, Advances neural information processing systems, 14, 2001.
[14] David Combe, Christine Largeron, Mathias Géry, and Elöd Egyed-Zsigmmond, I-Louvain: An attributed graph clustering method. In Advances in Intelligent Data Analysis XIV: 14th International Symposium, IDA 2015, Saint Etienne. France, October 22-24, 2015. Proceedings 14, pages 181-192. Springer, 2015.
[15] Yash Deshpande, Subhabrata Sen, Andrea Montanari, and Elchanan Mossel. Contextual stochastic block models, Advances in Neural Information Processing Systems, 31, 2018
[16] Issam Falih, Nistor Grozavu, Rushed Kanawati, and Younès Bennani. Community detection in attributed network. In Companion proceedings of the the web conference 2018, pages 1299-1306, 2018.
[17] Coes M Fortuin, Pieter W Kasteleyn, and Jean Ginibre. Correlation inequalities Communications Mathematical Physics, 22:89-103, 1971.
partially ordered
[18] Santo Fortunato and Darko Hrie. Community detection in networks: A user guide. Physics reports, 659:1-44, 2016.
[19] Geoffrey Grimmett. Percolation. Springer, 1999.
[20] Theodore E. Harris. A lower bound for the critical probability in a certain percolation process. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 56, pages 13-20. Cambridge University Press, 1960.
[21] Lawrence Hubert and Phipps Arabie. Comparing partitions. Journal of classification, 2:193-218, 1985.
[22] Varun Jog and Po- Po-Ling Loh. Recovering communities in weighted stochastic block models. In Proceedings of the 53rd Annual Allerton Conference on Communication, Control, and Computing, Los Alamitos, CA. USA. October 2015. IEEE Computer Society.

---

[23] Bo Long, Zhongfei Mark Zhang, and Philip S Yu. A probabilistic framework for relational clustering. In ACM International Conference Knowledge Discovery and Data Mining (SIGKDD), pages 470-479. 2007.
[24] Mahendra Mariadassou. Stéphane Robin, and Corinne Vacher. Uncovering latent structure in valued graphs: variational approach. The Annals of Applied Statistics, 4(2):715 742, 2010.
[25] Angelo Mele, Lingxin Hao, Joshua Cape, and Carey E Priebe. Spectral inference for large stochastic blockmodels with nodal covariates. arXiv preprint arXiv:1908. 06438, 2019.
[26] Mohamed Ndaoud. Sharp optimal recovery in the component Gaussian mixture model. The Annals of Statisticx, 50(4):2096-2126 2022.
[27] Mark EJ Newman and Aaron Clauset. Structure and inference in annotated networks. Nature communica- tions, 7(1):11663 2016.
[28] Frank Nielsen. Cherooff information of exponential families. arXiv preprint arXiv:1102.2684 2011.
[29] Suhhadeep Paul and Yuguo Chen. Consistent community detection in multi-relational data through restricted multi-layer stochastic blockmodel. Electronic Journal of Statistics, 1012):3877-8877 2016.
[30] Detlef Plachky and Joseph Steinebach. A theorem about probabilitics of large deviations with an application to queuing theory. Periodica Mathematica Hungarica, 6(4):343-345, 1975.
[31] Hussein Saad and Aria Nosratinia. Community detection with side information: Exact recovery under the stochastic block model. IEEE Journal of Selected Topics Signal Processing, 12(5):944-958, 2018.
[32] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi Rad. Collective classification in network data. Al magazine, 29(3):33993, 2008
[33] Laura M Smith, Linhong Zhu, Kristina Lerman, and Allon G Percus. Partitioning networks with node attributes by compressing information flow. ACM Transactions on Knowledge Discovery from Data (TKDD), 1122) 2016.
[34] Natalic Stanley, Thomas Bonacci, Roland Kwitt, Mare Niethammer, and Peter Mucha. Stochastic black models with multiple continuous attributes. Applied Network Science, 4(1):1-22, 2019.
[35] Tim Van Erven and Peter Harremos. Rényi divergence and Kullback-Leiblee divergence. IEEE Transactions on Information Theory, 60(7):3797-3820, 2014.
[36] Min Xu, Varun Jog, and Po-Ling Loh. Optimal rates for community estimation in the weighted stochastic block model. The Annals of Statistics, 48(1):183 204, 2020.
[37] Bowei and Purnamrita Sarkar. Covariate regularized community detection in sparse graphs. Journal of the American Statistical Association, 1166534)::34-745, 2021.
[38] Se- Young Yun and Alexandre Prouticre. Optimal cluster recovery in the labeled stochastic block model. Advances in Neural Information Processing Systems, 29, 2016.
[39] Anderson Zhang and Harrison Zhou. Minimax rates community detection stochastic block models, The Annals of Statistics, 44(5):2252 - 2280, 2016.
12

---

A Establishing the exact recovery threshold
The proof of Theorem is structured follows. We start by establishing some concentration results on the block sizes in Section A.1 In Section A.2 we delve into the asymptotic analysis of log-likelihood ratios, establishing fundamental results. Building upon these findings, we prove the converse statement, demonstrating the impossibility of exact recovery below the threshold, in Section A.3 Conversely, in Section A.4 we establish the positive statement, demonstrating the possibility of exact recovery above the threshold. To complement the proof, Section A.5 presents set of technical combinatorial lemmas.
Notations the following, we denote by E [K] the true block-labelling vector, and by 2' E [K]" another block-labelling vector, and the conditional probabilities are denoted by IP, (+) P(: 2).
A.1 Preliminaries on the block sizes
For any [K]", we for c E [K] define #=(="), the empirical size of block c, as
*t(=²) |i [n]: 2 = c}
n
For any 0 < < 1, we define
Ze {2 [K]*: (1 -1-66 E)m Re(2) I (1 E)+ VC [K]]
(A.1)
Recalling that the true block-labelling vector is sampled from π @n, we have by concentration of multinomial distributions (see for example [5] Lemma Al])
P(Zg) 2 2K exp (-5" min To eE(K]
In the following, we chose f log Vn
and hence P (1).
A.2
Asymptotic study of log-likelihood ratios
This section studies the asymptotic behaviour of IP, (L(=) L(z)), where L(z') (X, Y) the likelihood of the block- block-labelling vector z' given the observed data Y.
A.2.1 Upper-bound
The following lemma provides an upper bound on P. (L(2) 2 L(z)).
Lemma 3. Let 2 E Z be two block labelling vectors such that Ham(z, 2²) = m 2 1, and let L(z) = IP 22) be the likelihood of labelling We have
P. (L(2') 2 I(=)) S e -1++o(1)1
nTmin mml
Moreover, let d sup 1E(0.1) aybbE K] cE[K]
min (1 1) (o(JaallSh)) Then we also have
P. (L(x)) 2 L(2)) mmmanmmd
Proof. Using Chernoff's bound, we have for all 2 0.
P. log Px,(X,Y)
P,)( P.XX.TT
P.(XYY) >0) < -t Ez
lox
(A.2)
where the probability measure P, is defined on X' x by (3.1) in the main text. The linearity of the Rényi divergence with respect to product distributions implies
D, (P:) ED, (Iass)llees)
Σ
De(hz,llia))
isj
Isisn
Σ
M(as((od) De(Facllfbd)
Σ ISabEK
Nat (hall()))), (A.3)
13

---

where
Nas Hi E [n]: (2),2)) (a, (a.b)}]
(ad) Hi j: (2), = (a. b) and (2g. = (c, d)}
Moreover, Lemma 6 eensures that
M(ab)(ed)
Nab (Nod (ab))(ed) Ned (Nab l(ab))((a)))-
Therefore,
Σ Isabeed
Moo))od) (e(Jaclffoa)
2
Σ Miasi(os) De(Faclffoc) + Σ> ond
Maa)((dd) De(Facllfad)
2 > Nab Σ Noc Da
(A.4)
Using Noc = -0)- Edeoo Ned and that Ee Edje Ned = m, we obtain that
Σ Nab Σ #t(=)) (1 1 Edjf Nod
Σ
Maab)(ed) De(JacllSaa)
(e(JalllSbe)
(+tc(2))
Ksa,,,e
m
Σ azb
Nab Σ Di
mine Tt(2))
Hence,
Σ Nab(1 (1 (
(1 (P:
Σ #t(()) # De(faelle))))) + De (his)
minn #c(2))
apth
n 1 (1-
m
Σ (4,
n mine (z)2))
axbb
Using the concentration of 2, we have *t(2)= (1 o(1))TTe for all c, and hence
sup (1 - (Pa 2 (1 o(1)) (1 m (E(0.1)
mnl.
where we used Eupb Nab and / s CH(a, b, +()). The first upper bound on P. (L(x)) 2 T(=))
follows by taking 0 and the supremum over E (0,1) in A.2).
Finally, let d sup min (1 t) fo(fallffoe). Combining A.3 and A.4 leads (E(0.1)
a
cE(K]
sup (1- (IP.))((P)( 2 d Σ Nab Σ Nec = dm(n - m), (E(0.1)
Noe
axf
and this ends the proof.
A.2.2 Lower bound
We focus lower-bounding P. (I(=) > L(z')) when Ham(z,z') 1. In particular, the condition Ham 2²) = 1 implies that there exists unique node E [m] such that 2, # z Let a, E [K] such that 2, a and 2/ b. By definition of the likelihood, have L(z) L(z') Aud (X, Y, where
ha (Yu)- Σ log Joz. (Xuv) log faz.
(x,,,
(A.5)
ha
Before studying the large deviation rates of likelihood ratios such as P (A,b > 0) and P. (Anb > 0, Aob > 0), we first recall some large deviation result for arbitrary sequences of random variables 30 [0].
14

---

Proposition 1 (Strong large deviations for arbitrary sequences of random variables - Theorem 3.3 of (TO). Let n, be sequence of random variables whose moment generating function @n (t) [(eTT]] non-vanishing and analytic the region Q {z E C: |z| a} for some be a sequence of real numbers, and let (nn(t kn log on (t). Let (ma) be a bounded sequence of real numbers such that there exists a sequence (Tn) verifying (Tx) = My, and 0 < Tn < au < a. Suppose that:
0. Let kn
1. there exists b > O such that [v)(2)) S for all E Ω
2. there exists a > 0 such that (T)) > c;
3. there exists óu such that sups</t/<Ara
de Oe +it) (T(T..)
o(kn 12) ) for any given 6, X such
that 0 < 60 < X.
Then,
1+ o(1)
P (Tn am) =
Tn a (TT)
Proposition[] T is extension of Cramer's large deviation theorem for sums of iid r.v. to sequences of arbitrary random variables (see [10, Remark 3.6)). We will apply it to the study of (Aub > 0).
Lemma 4. Let z 2g (where Ze is defined in (A.I)) with Zu a and let Aus be given in (A.5). Suppose that there exists 8n = w(1) such that 8: t e
o(1). Let u [M] such that
(0, - lim nó,, CCH b) exists and strictly convex. Then, for any sequence en such that n
6n E (t) (0, 1)3 we have
P₂ (Aub > 8mcn)
(t.)
te t
where (*xx) sup (la 3()) the Legendre transform of B, and le such that (1(6)) = e. In 1>0 particular 0 E (1), E (0, 1)}, and therefore for any sequence En = 0(0 we have
P. (Aus knen)
1
nCH(a.))
Proof of Lemma 4 the stated results.
We will apply Proposition with = (= E | < 1] and in = 6--1 to obtain
Let us first compute (t) = EEg [c and (t) = 8, log (t))) for E (0, 1). We first notice that for all [n].
Juan (Xuw) log Taxu
(See
Jozu fax
Eg
IE
(Xwv)
by definition of the Rényi divergence. Similar computations show that
low he nu
(Y.s] e D.(hollww,))
Eg
Therefore,
(n(()
clus Th -CHH.(a,6..)
where
K
CH,(a,b,2) (1-1)
Σ #e Dr (SbcllSac) + D, (hallhaa) c=11
(A.6)
with म. nn (2= We note that since E Zg we have CH,(a, b. 2) (1 + (L)
Thus, (t) = -(1 (L,))nCH,(aab) Moreover, the assumption CH(a, b) θ (n-18,) implies
15

---

that CH,(a, b) = θ (n) for all E (0, 1) since the Rényi divergences of orders t E (0, 1) are equívalent 35 Theorem 16]. Hence, (n) = (1 [1+ (())))) Since 3 is well-defined and strictly convex on (0.1). 1), this ensures that Assumptions and 2 of Proposition are verified. Moreover, we notice that e0(1) the m.g.f of some r.v. X, and let sp(() Ee the characteristic function of X. Then, (x(("+ir) [p(t" +at)
6n
((t)) Since ++(*"++t)) ((t") is the characteristic function of some r.v., its module is strictly less than on an interval not containing 0, and hence Assumption 3 of Proposition ! verified.
+n((")
Finally, Lemma 8 ensures that (0) < and (1) and hence (8'(1), e (0, 1)).
A.2.3 Asymptotic independence
Finally, the following lemma shows that the events Abb > and Aob 0 are asymptotically independent.
Lemma 5. Let Zg. u, 2 (a), and b [a]. Then,
Ps (AnD 0, Ab > 0) - 1 +
P2 Wh P. (Anh ub 0)
Proof. Let E(X = log Laa
(Xuv). We have
Jno
log foem (Xww) ) log
ho (Vw) + log foa (Nuv), Juo
A ub
log
aa
fazu
ha
v (a
fuzm (xw) log
hb (Y,) log foa Sea
Ab
log
log
(Xuv).
na
Saa
hea
v
Therefore,
Aub Un E(Xuv) and
Anb U, - {(Xun)
where U, and U. are iid. Therefore,
Ps (Aub 0, Aeb > 0) P. (Aub P. (Deb > 0) Covv 1(,1(A.b 0).
Conditioning on Un and U.. observe that
//Covz Cov, (G, (E) u(du)
Cov=(1(A) > 0), 1( > 0) =
where 6.(5) = 1(t > f and = Law(E). Because du and du' are monotonous, the Partinn-Kastllemm Ginibre (FKG) inequality 20 (see also 19 Section 2.2]) implies that Cov (En(E), &w (E)) 2 0. Therefore,
P. (A 0, A 66 0)
2
P. (A.b > P)P Ab 0)
Let us now derive an upper bound for this ratio. First, Lemma with en and 6, log n implies
P (Anb b > 0) = 1+ o()
-nCH(a,b)
22 log n13"(1*)
and the same relation holds for P P(Abb > 0). Moreover, conditionally on Xuv we have
P. (Anb 0, A 0) fe (x:)) Saa (x)dx)
2EE
where (xx P. (U {x))). Since CH.(a,b) = o(1), then fao and foo mutually contiguoug" for all e (see [35 Theorem 25]). In particular, this implies that {(x) < xo for all x E X' such that
'Let (p.) and (g.) be two sequences of distributions. Then is contiguous with respect to if for all sequence of event An such that gm (An) = o(1) also have pm (An) = o(1).
16

---

fa)( > O. Thus, we can apply Lemma 4 with cn = {(x) and on log n, verifying 6n - 0 to obtain
1 (1) -nCH(a.))
<(x)
8a 2 ng
and this ends the proof.
A.3 Impossibility of exact recovery
For a, E [K] two block indexes, we recall the quantity CH( b) defined (3.2) of the main text denotes the hardness distinguish node in block from node in block b. We suppose that
1 = mim CH(a, b) θ log with lim " < 1. We prove the failure of the MAP estimator agb
110000 log
for exact recovery in three steps:
(i) We start by showing that we can restrict the study to the node labelling vector for which the relative size of the communities are close to their expectations, i.e. (a) = (1+ ol)) o(1)) for
all [K];
(ii) Let (2) be the number of nodes in block a for which changing their community label to block b results in an increase of likelihood. We show that aMass > when a, are the two
hardest blocks to distinguish.
(iii) We show that Mat(z) > O almost surely using the second-moment method.
ii) Conditioning on well-behaving community sizes. established in Section A.1 that (PZ))) 1 o(1) for
Recall the definition of 2: in A. 1. We
log log
Hence,
Vu
P (MAP fails) )
Σ P. (2 MAP # P(2)
Σ
Ps (2 MAP, # #)) ((2)
=EZg
P (Zg)
inf Pz (=MAP #
sE2g
2 (1 o(1))
inf P. (aMAP # =
ZEZt
The rest of the proof devoted show that P3 MAP # 2) = =1 o(1) for all E Zç.
(ii) Expected number of bad nodes. Given a block structure z E Ze. an arbitrary node E [n] such that 2, a and block a. We define by the block structure obtained from by swapping the block of node u to b, ie..
Ve [n]: E (1 dvu) + dvab.
Suppose that X, y are generating from true block structure 2, and let
Aubl X, Y, = log P(= - log P(=|
(A.7)
the change in the MAP estimation of obtained by swapping the label of node u from its true block a to a wrong block By the definition E, we have using Bayes' law
PP (z., = X,Y,
A (X,Y,=) log
(
X, X_YY
TTP (X,
スー Zu = b) 2ー Zn =
log
T. (X, Y
17

---

Moreover,
n
log IP (X 22-2 Zu = b)
Σ
log fevew (Xow) +
Σ ==
log h2 (Xv)
log foz, (Xwe) + log (Y() + C
where C' does not depend b. Hence
uu X, 2)
log
b
log
Jizu
hb (Yu)- (Xuv) + log
aa
Jaz.
ha
The number nodes in block a for which updating the label to would cause the change of likelihood to be strictly positive is given by
Mar(z)
Σ (X) 0). (E=
In the following, select a, the indexes of the two hardest blocks to distinguish. Hence, CH(a, b, n, f.h. and we have using Lemma that
(ab
nane - (L4o()))))CCHHHa......
Since 2 2ę we have that CH( b, #, f.h) = (1+o(1))I. Moreover, by assumption I < (1-c) log for some > O and for any n large enough. Hence M.Mx(() > 1.
log
(iii) Conclusion. We will conclude that Ma > 0 almost surely using the second-moment method. Denote by = (Amb > 0) and 8 IP (Aus > Aub > 0) for two arbitrary distinct nodes u, 2-
2 (a). We have Mab - -(x) and
Var, Mas =
Σ Cov (1(Aue > 0), 1( > 0))
(,vEc-1(()
= -1> (a)) (a a²) (a) (1= (a)
- -1) (B a²)
S E.Mat + (Eg Mat)) 3 a²
a²
Hence, the second-moment method implies that
Var, Mab
1
B
P, (M = 0) <
+ a²
1.
(E, Mab)
E.Mab
We end the proof using Lemma
A.4 Possibility of exact recovery
To show that the MAP estimator achieves exact recovery up to the desired threshold, we need to show that there is possibility of reducing the likelihood by swapping m vertices from each community. In all the following, we recall that z denotes the true community labelling, and for any z' E [K] we denote by L(z')= P(X, Y 2²) the likelihood of labelling z'. For any 1, let denote the set of node-labelling at a distance m by
T Tm = (2' E 2: loss(2, 2') = m)
(A.8)
The probability that there exists labelling z' E I' with higher likelihood than 2 is
Pm P. (Ex' E T L(z') 2 L(z)).
18

---

Let be the block labelling estimated by the MAP. Lemma Thus, we have, using union bounds.
ensures that [Tml = if m 2 n K-1 2
K-
2K
Ps (loss (z, 2) 2
<
mm max P. (L(=)) L(=)) 2e
Moreover, 39 Proposition 5.2] show that
enk
mal S min
K
m
while Lemma provides upper bounds max Pa (L(z)) 2 L())). Combining these upper
s'El'm m
bounds ensure that for some sequence 7) = o(1), we have
2K
P- (loss(z, 2, 2 1) S
(sm) n
(A.9)
where 8m
enk min
e (1-nn)
mr minu
nt
(n-mjd
with d = sup
min (1
te(0.1)
a oE K]
Da(Seellbbe-
Let 0 such that > (1 + E) log We will now show that the sum on the right-hand side of
Equation (.. goes zero, by considering the cases (i) m Zmin n and (ii)
Tmin
S S 2n.
2
(i) First of all, suppose that m < Euiun. n. Then,
I n=)1-n)++ c (1-n)(1+e)) m
eK
log
llg m
Fmin
eK (1+r)
m lag log
I
n²/2
mminn
Let [m)
log
1 log Tiin
We will show that ((m) > log m for m 3. Indeed, for x 2 3, the
function I +
log is decreasing. Therefore, for 3 S m S Mmin n we have
[(m) log m 2m
log m
1 log 2
log log(mmin//
1 1+ log Tiin
>
m
Tuin
n
Tuin
72
n2
Iujin m=1
for n large enough. Hence sm S eKn e
log and Σ
Sm o(1)
(ii) Next, suppose that mi S m S n
x Then, the assumption De(Jacll =
implies that d > logn for some positive constant s. Hence,
2eK e * logn
Sm S
Tiin
K L
and thus Σ Euin
Sm o(1.
Hence, (A.9) shows that Pz (2))(2222 2 1) = o(1), and thus the MAP estimator exactly recovers the true community structure z.
A.5
Additional lemmas
Lemma 6. Let 2, x e [K]" and define for all b, c, d e [K]:
Aut = ( E [n]: (z, z{) = (a, b)]b
Maad(edd = (1 [1si<je n: (z x1) = (a, b) and (2,) = (c,d)}
We have
Mab)(oo) Anb (And ((a))=(ed)) Acd (Aub ((ad)=(od))
19

---

Proof. Denote by C. = 2- (a) and C. = =a)- and let Cab = Ca n Cj Then, Aub = Caabl and (aa))(dd) f J S n: Cab and E Cea) This proves the lemma.
Lemma 7. For any z E [ we have loss(2, x)) - n R)
Proof. Without loss of generality, suppose that loss(z, 2) Ham(zz =²) (that is, the optimal per- mutation in the definition of the loss simply the identity). For any E [K]. let us denote by
C (a), C² = (b). The confusion matrix of the two node labellings the K-by-K matrix having entries Nat CCa n Col. In particular, have n Ea.b Nos and
12ss(2,2')
Nab
72
N aa.
S Lemma B.2] show that Nab Naa + Nos Nba. and therefore
loss(2,2)) x (Nao + Nos Noa)
(A.10)
We notice that
ΣΣ Naa (K -K-11 Σ Naa (K 1)(n loss(2,, 2()) bşz
=KK
and similarly,
ΣΣ Nos Σ Σ Nob Naa bbaa
(K 1-)( loss z¹))
Finally, E. Eosa No. loss (2, 2²). Thus, going back to (A.10) leads to
loss(2, 20))) S 2(K 1)n - (2K 1)loss(22 2/);
and this ends the proof.
Lemma 8. Let S.g be wwo probability distributions and denote c(1) (1 1) De(l(l)) the Chernoff coefficient of order between I and g. We have e' c(()) = dkl.(gll)) and e' (1(1) = dki.()llg).
Proof. From c(t) -logg J f'gl-t, we notice that c' c'(t) 11""g-- log L I l'ggtt
and the result follows.
20

---

B Proof of Lemma 1
Proof of Lemma I. Using Taylor expansion, we have
= log (1-Pac) (1 - -Pbo)* + PucPbo / (Fao)
(1 (1
tp (1 -)---19900 -p'g'-1 / (Foo) (Foo) o00),
and we finish the proof using (fbo)) e-dollanlion)) and (1 -1-13 Dr(ha 11 = Jo (o (1)))
(see for example (8
C Additional numerical results
We present in Table and the numerical results that drawn in Figure (4a) and (4b), respectively, We observe that the variance of Algorithm very low, while all other algorithms (excepted EM-GMM) exhibit a very large variance.
Table 2: Average ARI of the different algorithms over 60 trials with standard deviation in brackets obtained for Figure (4a).
PARAMETER
5
7
9
11
13
15
ALGORITHM
0.40 (0.15)
0.62 (0.04)
0.93 (0.02)
(0)
(0)
(0)
EM-GMM
0.45 (0.04)
0.46 (0.03)
0.46 (0.04)
0.46 (0.04)
0.46 (0.04)
0.45 (0.07)
0 (0)
0.07 (0.05)
0.83 (0.15)
0.85 (0.33)
0.93 (0.24)
0.82 (0.37)
TR_SS LS
(0)
0.20 (0.13)
0.93 (0.14)
1 (0)
0.98 (0.12)
(0)
auSBM
0 (0)
0.07 (0.05)
0.82 (0.15)
0.86 (0.33)
0.42 (0.48)
0.59 (0.49)
Table Average ARI of the different algorithms over 60 trials with standard deviation in brackets obtained for Figure (4b).
PARAMETER r
0
1
2
3
ALGORITHM
0.47 (0.29)
0.82 (0.03)
0.97 (0.02)
(0)
(0)
1 (0)
EM-GMM
0 (0)
0.46 (0.04)
(0.02)
1 (0)
(0)
(0)
SC
0.36 (0.28)
0.38 (0.27)
0.35 (0.26)
0.40 (0.26)
0.37 (0.28)
0.35 (0.26)
LS
0.42 (0.29)
0.65 (0.31)
0.91 (0.21)
0.97 (0.15)
0.97 (0.14)
0.98 (0.12)
anSBM
0.36 (0.28)
0.38 (0.27)
0.38 (0.30)
0.59 (0.43)
0.57 (0.46)
0.50 (0.43)
We also provide in Figure comparison of Algorithm with IR_ IR_sIs and auSBM on weighted networks with attributes exponentially distributed. We observe that contrary to Algorithm IR_sIs and auSBM do not perform well in that setting (which expected as they are designed for binary network and Gaussian attributes).
0.8
0.5
0.6
ARI
EM-GMM
0.4
EM-GMM
SC
Algol
0.2
Algol
attSaM
IRS
-0.2
weights aavg
attributes_ave avg
(a) Varying X=1 with Xa 1/2.
(b) Varying A; with A.. 1/2.
Figure 4: Performance on weighted networks (n 600, K = 2) with edge- distributions fin (1 -p)o Exp(Aw), fout (1 p)oo + Fxp(1) with p 5m -1 log n, and exponentially distributed attributes hy ~ Exp(1) and ha = Exp(Aa). Results are averaged over 20 runs.
21

---

C.1
Robustness to the choice of du- and dø-
We show in Figure 5 that using divergence (distribution) for edge weights (Figure Sa and node attributes (Figure 5b different from the distribution used to generate the data does not impact the performance of Algorithm 1. We note that similar observation was done in previous papers using
Bregman divergence for clustering 6 23
1.0
1.0
0.8
0.8
0.6
ARI
0.6
euclidean
ARI
0.4
euclidean
manhattan
manhattan
0.4
0.2
Itakura-Saite
Itakura-Saito
0.0
0.2
poisson
poisson
5
7
11
5
7
11
muin
nul
(a) Various dgs,,
Poisson is correct model.
(b) Various dx. Poisson the correct model.
Figure 5: Performance of Algorithm when dæ. dæ- do not correspond to the model that generated the data. The different curves show the Adjusted Rand Index (ARI) [2]] averaged over 20 realisations with the standard deviations error bars.
(a) n = 400, K = 4, fi = (1 p))u(r) + pPoi((sn) and fout = (1 (x)) + qPoi(5), with p 0.04 and q 0.01. Attributes are 2d- id-Gaussians with unit variances and mean equally spaced the circle of radius r = 2.
(b) 400, K 2, fi (1 (x)) pNor(2, 1) and fout (1 g))n(x) (No((0, 1), with 0.04 and g = 0.01. Attributes are Poisson with means Vn (for nodes in cluster 1) and 3 (for
nodes in cluster 2).
22


Reviews:
[{"review_id": "fdEY9o0Nif", "reviewer": "Reviewer_hHhv", "summary": "This paper studies community detection in node-attributed stochastic block models. Although these models have been studied before, this work has two main contributions: (i) the edge weights in the model are now not necessarily binary, but can also be weighted. The node attributes don’t have to be Gaussian, and can come from a more general exponential family. (ii) An iterative clustering algorithm which maximizes the likelihood by placing nodes in correct cluster based on attributes and edge weights.\nExperiments on synthetic datasets are also presented\n", "questions": "None", "limitations": "none", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "•\tThe weakening of the assumptions in this work are more general than what previous work has considered. This is a significant strength of this work. The assumptions in this model (weighted edges, non Gaussian node attributes) are more realistic than what previous work has considered, and I consider this a nice contribution.\n\n•\tTo the best of my knowledge the theoretical work is sound and contains some non-trivial insights. Some of the technical techniques presented might have impact on future work.\n\n•\tExperimental results on synthetic data suggest that the proposed algorithm 1 performs well compared to previous work.\n\n", "weaknesses": "•\tGiven that a motivation for this paper is to provide an algorithm for a more realistic setting, I would have expected to see experiments on real world datasets. In general, stochastic block models enjoy a very symmetric structure, which in some sense makes it nice to cluster. It would be interesting to see how the performance of this algorithm generalises to real-world graphs. \n\n•\tExperimental results on synthetic data is only performed when $k=2$. Higher values of $k$ should be considered \n\n\n## Minor:\n\nLine 73: conditioned of --> conditioned on\n\nLine 129: is find --> is to find\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer,\n\nThank you for the time spent reviewing our paper. In order to address the weaknesses pointed out in your review, we have performed novel experiments using synthetic data sets with a larger number of clusters ($k=3$ and $k=4$). Results using more clusters are qualitatively similar to the $k=2$ case but do strengthen the results in the paper (see plots in the global rebuttal file). \n\nWe have not considered real datasets because this work focuses on characterizing (theoretically) and measuring (empirically) the influence of different model parameters (e.g., edge probability, edge weights, and node attributes) on the performance of recovering the clusters. Measuring this kind of influence is quite challenging when real datasets are used. In contrast, Fig. 2 in the global rebuttal file shows the relationship between the theoretical threshold for exact recovery (theorem proved in this paper) and the performance of Alg. 1 (proposed in the paper). "}, {"review_id": "3an1WMikJb", "reviewer": "Reviewer_cu9t", "summary": "This paper studies community recovery in sparse, weighted networks, which is an important setting that is more general than the commonly-studied undirected, unweighted networks. The authors' first main contribution is to establish the information-theoretic conditions for exact community recovery in this setting, which is a form of the Chernoff information (and cleanly reduces to well-known info-theoretic thresholds in unweighted settings). Next, assuming that edge and node attributes belong to exponential families, an expression for the likelihood in terms of Bregman divergences is given, which then leads to a natural clustering procedure. Extensive numerical experiments are provided comparing the proposed procedure to other approaches. ", "questions": "- You use the term \"homogeneous\" a lot: can you define precisely what you mean by this? \n- Section 2: You can also consider citing work on Censored Block Models, in which edges take on 3 values (present, absent, unknown)\n- Theorem 1: How crucial is the assumption on the convexity of CH_t (a^*, b^*) in t?\n- A clarification question: if the attribute distributions were not from an exponential family, would the likelihood be intractable to compute? \n- For clarity, I would suggest defining ARI. \n- In the simulations, is the ARI measured between the estimated and ground-truth communities? If so, please clarify in the main text.", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Deriving the information-theoretic threshold for exact recovery via the Chernoff information is perhaps not surprising, but it is a solid contribution as it encompasses a wide range of important examples. The clustering procedure derived, based on a connection between exponential families and Bregman divergences, is clean and intuitive. The simulations on synthetic data show that the clustering procedure has favorable performance in terms of the ARI, compared to other methods, which is a good validation of the theory. ", "weaknesses": "The paper could be improved if the authors filled in some gaps regarding a few central topics. \n- Please discuss in more detail how similar / different your approach is to [19], since both leverage the connection between exponential families and Bregman divergences to come up with clustering procedures. \n- The information-theoretic results are not too surprising. Does the proof require new techniques to handle the more general setting under consideration? If so, they should be discussed in the main text, as it would be of interest to theoreticians in this field. \n- Please provide additional discussion around the accuracy and sample complexity of the clustering algorithm. Is it efficient? Is it guaranteed to output the MLE or similar? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer, \n\nthank you for the time spent reviewing our paper. Please find below answers and comments to the weaknesses and questions you have raised. We hope this will help clarify and strengthen our contribution.\n\nWeaknesses:\n\n* Indeed, Alg. 1 is similar to [19] and the main (and only) difference is that their model assumes a dense weighted network (an edge is present between any pair of nodes and has non-zero weight). As most real networks are sparse (most node pairs do not have an edge), we propose a model for sparse weighted networks. Therefore, their model assumes edge weights $w_{ij}$ are drawn from an exponential family for every node pair $(i,j)$; our model assumes edges can be present or absent (Bernoulli) and a present edge $(i,j)$ has weight $w_{ij}$ drawn from an exponential family. Note that Lemma 2 established a relationship between the log-likelihood of such zero-inflated distribution and Bregman divergences. In any case, we have performed experiments that indicate that using a sparse model (Alg. 1) yields much better accuracy than the dense model assumed in [19, 20] when the network is sparse, as is the case for most real networks (see plots in the global rebuttal file). Moreover, since [19, 20] assume a dense network (all possible edges are present, $O(n^2)$) their algorithms do not scale to large networks. In contrast, the complexity of Alg. 1 depends on the number of edges, which is often $O(n\\log n)$. We plan to revise the exposition of Section 4 and include these results and observations on complexity. \n\n* The novelty in this proof is the usage of Plachky-Steinebach's theorem (a generalisation of Cramer's large deviation theorem) to derive the asymptotic behaviour of the probability that a given node $u$ is predicted to be in a wrong community by the MLE (let us call this event $Au$). Another novelty is the usage of FKG inequality to show that events $Au$ and $Av$ are positively correlated. Previous works in binary or edge-labelled SBMs typically computed this probability using ad-hoc calculations that only work for Bernoulli interactions (or interaction on a discrete, finite space). We plan to explicitly mention the Plachky-Steinebach theorem in the main text since this is essential for our theorem and may also be of interest to some readers. \n\n* Unfortunately, Alg. 1 comes without any theoretical guarantees. It does not necessarily computes the MLE for the instance at hand. However, Fig. 2 in the global rebuttal file shows that Alg. 1 achieves exact recovery in a region very close to the information-theoretic limit. Indeed, two-stage algorithms have been shown to achieve optimal accuracy in binary SBMs (see additional refs. [1]-[2]) and K-means achieve optimal accuracy in a Gaussian mixture model (additional refs. [3]-[4]). Thus, it is possible that the proposed algorithm can be analysed rigorously, but this challenging task is outside of the scope of this conference paper. \n\nQuestions:\n\n* Homogeneous refers to the setting where two distributions $f$ and $g$ determine the interactions (edge weights) within and between communities, respectively. This provides for a very simple and symmetric setting. We defined it in Section 2.1, but will emphasise its meaning also in the text. \n\n* Indeed, the Censored Block Model is a nice additional example, we will add it as an example and mention recent results such as [5]. \n\n* We noticed a typo in Theorem 1: the assumption should be that $CH_t(a,b)$ is strictly concave (which in turn implies the strict convexity of the function $\\beta$ defined in line 71 p.4 of the Appendix). This strict convexity of $\\beta$ is required to apply the Plachky-Steinebach theorem. However, this is not a constraining assumption for our setting, since the quantity $CH_t(a,b)$ is concave and will be strictly concave except in degenerate cases where all the probability distributions are equal and the divergence is zero. For example, if $f$ and $g$ are Gaussian with mean $\\mu_1$, $\\mu_2$ and variance 1, then $(1-t) D_t( f \\| g ) = \\frac12 t(1-t) (\\mu_1-\\mu_2)^2$ (where $D_t$ is the Renyi divergence of order $t$). This quantity is indeed strictly concave in $t$, except in the degenerate case where $\\mu_1 = \\mu_2$. This same argument can be made for any distribution in the exponential family. This technical comment was not mentioned in the paper due to lack of space, but we do plan to add a comment in the revised version. \n\n* Indeed, the exponential family provides some advantages when considering the MLE. For example, the Pitman-Koopman-Darmois Theorem states (under some smoothness assumptions on the probability density) that sufficient statistics with bounded dimensionality (i.e., not growing with the sample size) exist if and only if the distribution belongs to an exponential family. However, computing the MLE in weighted SBMs is computationally challenging even when restricting to exponential families, and this is the goal of Alg. 1 (not necessarily met). \n\n* Indeed, the performance of all algorithms is evaluated using the ground truth, since we have synthetic network models. We will clarify this and add a definition of the metric used (ARI).\n\n[1] Chao Gao, Zongming Ma, Anderson Y. Zhang, Harrison H. Zhou. Community detection in degree-corrected block models. The Annals of Statistics, 46(5) 2153-2185  2018.\n\n[2] Arash A. Amini, Aiyou Chen, Peter J. Bickel, Elizaveta Levina. \"Pseudo-likelihood methods for community detection in large sparse networks.\" The Annals of Statistics, 41(4) 2097-2122 2013.\n\n[3] Yu Lu, Harrison H. Zhou (2016). Statistical and computational guarantees of Lloyd's algorithm and its variants. arXiv preprint arXiv:1612.02099.\n\n[4] Chao Gao, Anderson Y. Zhang. Iterative algorithm for discrete structure recovery. The Annals of Statistics, 50(2) 1066-1094 2022.\n\n[5] Dhara, Gaudio, Mossel, Sandon. Spectral recovery of binary censored block models. ACM-SIAM Symposium on Discrete Algorithms (SODA), 2022."}, {"review_id": "9dqGFpPmqE", "reviewer": "Reviewer_coB1", "summary": "This paper studies clustering of node-attributed Stochastic Block Model (SBM). The authors provide information-theoretic threshold for exact recovery under generic distributions for both edge weights and node attributes. In addition, the authors propose a clustering algorithm based on iterative likelihood maximization when edge weights and node attributes are drawn from exponential family distributions. The authors carry out experiment on synthetic data and show that the proposed algorithm outperforms existing state-of-the-art methods.", "questions": "- In practice, how should one use Algorithm 1 when $\\psi^*$ and $\\phi^*$ are unknown?\n\n- Does Example 2 imply that an oracle to the true community is almost useless unless the oracle gives almost full access to all labels?", "limitations": "I could not find where the authors discuss the limitations or potential negative societal impact of their work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The theoretical setting (i.e. clustering of node attributed SBM) considered in this work is fairly general. The threshold for exact recovery is presented in a general setting without assuming any particular family of distributions for either edge weights or node attributes. The examples and implications of Theorem 1 provided on page 5 are nice. \n\n- The threshold which involves Equation (3.3) captures an intuitive additive signal from edge connections and node attributes.\n\n- The overall writing and presentation is very clear and generally easy to follow (although there are many typos here and there). In particular, the presentation of background and related works seem reasonably thorough.\n\n- The empirical results, though limited to synthetic data, are promising.\n\n- Overall, I think this paper studies a well-known problem in a more general setting than those have been considered in prior work. The new results and algorithm can be a nice addition.\n\n", "weaknesses": "- Algorithm 1 requires knowing the functions $\\psi^*$ and $\\phi^*$. This requirement often does not hold in practice. The authors should discuss the practical implications for such requirement and what if these functions are unknown.\n\n- Though not necessary for a theory paper, it would be nice to have at least some elementary experiments on real data.\n\n- There are many typos throughout the paper. Here are some:\n  - Line 95: standard deviation $\\sigma^2$ -> standard deviation $\\sigma$\n  - Line 124: while his work -> while this work\n  - Line 129: is find the community -> is finding the community\n  - Equation (4.2): subscripts for $\\theta$ do not match, similarly, subscripts for $\\eta$ do not match\n  - Lemma 2: $p_{k\\ell}$ in the Equation should be $p_{ab}$?\n  - Line 284: in Nor(...) I think the placements for mean and variance should be reversed", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer, \n\nthank you for the time spent reviewing our paper. Please find below answers and comments to the weaknesses and questions you have raised. We hope this will help clarify and strengthen our contribution.\n\nWeaknesses:\n\n* Indeed, the distributions used to compute $\\psi^*$ and $\\phi^*$ are parameters of Alg. 1 and must be determined a priori, through an educated guess, for example. Note that given the distribution for edge weights and node attributed,  $\\psi^*$ and $\\phi^*$ are uniquely determined. Nonetheless, we have performed experiments that indicate that the performance of Alg. 1 does not strongly depend on in the right choice of $\\psi^*$ (see plots in the global rebuttal file). We will add this assumption and results to the revised paper. Interestingly, a similar observation (that the right choice of distribution leads to marginal performance gains) was also made in [6] (see Tables 3 and 4 of [6]). \n\n* We have not considered real datasets because this work focuses on characterizing (theoretically) and measuring (empirically) the influence of different model parameters (e.g., edge probability, edge weights, and node attributes) on the performance of recovering the clusters. Measuring this kind of influence is quite challenging when real datasets are used. In contrast, Fig. 2 in the global rebuttal file shows the relationship between the theoretical threshold for exact recovery (theorem proved in this paper) and the performance of Alg. 1 (proposed in the paper). \n\n* Indeed, the submitted paper had some typos and we appreciate your indication. A throughout reading of the paper will correct them for the revised version. \n\nQuestions: \n\n* This is a tough question and outside the scope of this paper (since we assume them to be known or guessed informatively). However, here is an idea. Since the initial clustering does not require knowledge of $\\phi*$ and $\\psi*$, one could treat the Bregman divergence as unknown within a set of distributions, and then learn the distribution (divergence) in the iterative steps. We will mention this as potential future work, and cite the papers [1,2] that are recent advancements in this direction.  \n\n* Indeed, the exact recovery threshold is not modified unless the oracle gives almost all the labels. A high-level explanation is the following. \nConsider the planted partition model (two communities of equal size $n/2$, intra- and inter-community edge probabilities $p$ and $q$ with $p = a n^{-1} \\log n$ and $q = b n^{-1} \\log n)$. Exact recovery is impossible if (at least) one node has more neighbours in the opposite community than in its own community. The probability that a given node has more neighbours in the opposite community is $P_e = e^{- (1+o(1)) \\frac12 ( \\sqrt{a} - \\sqrt{b} )^2 \\log n }$ (see Section 4.1 (Lemma 4) in the last arxiv version of the review by E. Abbé, where he names this the 'genie-aided hypothesis'). \nIn the unsupervised setting, since there are n nodes to label, exact recovery is impossible if $n P_e$ does not go to zero. This provides the condition $(\\sqrt{a} - \\sqrt{b} )^2 > 2$. \nIn the semi-supervised setting, there are $\\eta \\\\, n$ nodes to cluster (where $\\eta$ is the fraction of labels revealed by the oracle). If $\\eta$ is constant, then the condition for exact recovery is unchanged. \nWhile this negative result is not new (we refer to [25]), we highlighted it here as an example since it is a special case that we find to be counter-intuitive. \n\n\nAdditional references:\n\n[1] Shah, Shah, Wornell (2021). A computationally efficient method for learning exponential family distributions. Advances in neural information processing systems, 34, 15841-15854.\n\n[2] Siahkamari, Xia, Saligrama, Castañón, Kulis (2020). Learning to approximate a Bregman divergence. Advances in Neural Information Processing Systems, 33, 3603-3612."}, {"review_id": "Kn8agGozwu", "reviewer": "Reviewer_1Ec2", "summary": "This paper extends the analysis of exact recovery of the Stochastic Block model to node attributed graphs (CSBM). This opens up a new dimension as the desired clustering must not only be optimal in the sense of the SBM but also respect the node attributes (which are assumed to be distributed based on the block of the SBM). First, a binary setting is presented, where edges are either present or not. For this setting, the authors present a tight bound on the information theoretical (im-)possibility of recovering the blocks of the SBM using the Chernoff information of the model. Second, a setting is analysed where the graph structure is sampled from an SBM and node attributes and edge weights are sampled from a distribution from the exponential family. For this setting, the authors present the Chernoff information of the model given its parameters allowing for a concrete characterization of the phase transition between possibility and impossibility of recovery. An iterative likelihood maximization algorithm is then proposed and evaluated on synthetic data.\n", "questions": "- Can you find any guarantees for your algorithm such as recovery with high probability in a certain regime? \n- In the experiments, why don't you compare your approach to the other papers [19,20] that you mentioned in your related work?\n- In the experiments, how close is the performance of your algorithm to the theoretical bound you presented?\n- Why did you not compare the algorithms on real-world data?\n", "limitations": "Limitations of the setting or the approach are not discussed -- this should be rectified.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- This paper provides a nice perspective on the relevance of information gained from the network structure and that gained from the node attributes.\n- The claims of the paper seem sound. \n- The sections themselves have clear statements.\n", "weaknesses": "- The experiments are not convincing. \n\t- All experiments are carried out on synthetic graphs generated in a way that benefits this algorithm. \n\t- The presented algorithm is compared with 2 baseline algorithms that only optimize for one of the two dimensions and thus fail at the other. Instead, one could have compared with other approaches to node-attributed community detection, which should pose more of a challenge. [19,20] could have been used as a comparison.\n- The related work section is quite sparse and is used to distinguish the contribution rather than present related work. E.g. section 2.2 \"Algorithms for clustering node-attributed networks\" contains 2 citations. This should be augmented. \n- In the presentation of the results it should be made much clearer that the developments presented here, heavily depend on [3]; with the current writing the reader gets a wrong impression of the novelty of the here presented ideas.\n- The structure and the presentation of this paper are sometimes confusing. \t\n\t- The reader is often left guessing where we are headed next. E.g. section 4, which is framed as the main contribution (extending [19] by allowing for sparse networks) simply starts by introducing zero-inflated distributions from the exponential family. Or 4.2 gives the derivation for the negative log-likelihood without previously mentioning that this will be used in the iterative likelihood maximization algorithm. \n\t- The numbering in the appendix overwrites the numbering in the paper (e.g. Theorem 1 in the paper is not Theorem 1 in the appendix) which makes referencing the paper from the appendix or the appendix from the paper very hard.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer, \n\nthank you for the time spent reviewing our paper. Please find below answers and comments to the weaknesses and questions you have raised. We hope this will help clarify and strengthen our contribution.\n\nWeaknesses:\n\n* This is not the case. Please note that Figs. 2 and 3 of the paper compare the performance of Alg. 1 (our proposal) to 4 other algorithms. Two of them (SC and EM) only optimize for one of the dimensions (network and attributes, respectively), while the other two (attSBM and IRsls) optimize over both the network and attributes. Note that Figure 2 deals with binary networks with Gaussian weights, which is exactly the model for which both attSBM and IRsls were designed. Hence this setting is not advantageous for our Algorithm. Yet, even in this case, Alg. 1 outperforms them. \n\nFigure 3 shows that attSBM and IRsls perform terribly when the attributes are non-Gaussian and the network is non-binary, while Alg. 1 has a relatively good performance. Thus, Alg. 1 performs well in both scenarios. Moreover, we have performed experiments that show that Algorithm 1 is not too dependent on the choice of $\\psi$, as questioned by reviewer coB1 (see plots in the global rebuttal file). This robustness to the choice of $\\psi^*$ and $\\phi^*$ confirms the superiority of Alg. 1 with respect to attSBM and IRsls. \n\nIndeed, Algorithm 1 is similar to [19] and the main (and only) difference is that their model assumes a dense weighted network (an edge is present between all node pairs with non-zero weight). As most real networks are sparse (most node pairs do not have an edge), we propose a model for sparse weighted networks (see the answer to reviewer cu9t). In any case, we have performed experiments that indicate that using a sparse model (Alg. 1) yields much better accuracy than the dense model assumed in [19, 20] when the network is sparse, as is the case for most real networks (see plots in the global rebuttal file). Moreover, since [19, 20] assume a dense network (all possible edges are present, $O(n^2)$) their algorithms do not scale to large networks. In contrast, the complexity of Alg. 1 depends on the number of edges, which is often $O(n\\log n)$. We plan to revise the exposition of Section 4 and include these results and observations on complexity. \n\n* Indeed, page limitation forced us to severely restrict the discussion of the related work. The revised version will improve this discussion. Note that Section 2.2 cites the two relevant algorithms to cluster (dense) weighted networks: [9] and [20]. We mentioned [19], as it inspired Algorithm 1, but we should have described [8] and [28] as well. \n\n* The proof techniques indeed rely on [3], but also on on [33] and [5]. Yet, some arguments here are new (refer to our answer to reviewer cu9t). However, the paper clearly states that the Chernoff-Hellinger (CH) divergence was first introduced in [3] (see the introduction, section 2.1 and Remark 1). Nonetheless, as defined in [3], the expression of the CH divergence does not extend easily to non-binary interactions (contrary say, to the Renyi divergence which appears when the interaction are homogeneous SBM). \nIt appears that the only work generalising the CH to a non-binary setting is [32]. Yet, in [32] the divergence is expressed as a minimisation of KL divergences, which again does not easily extend to more general interactions (say, real-valued probability distribution for edge weights). More, in [32] the link with the CH divergence requires a technical lemma (See Claim 4 of [32]), whose proof requires sparse interactions. \nThus, in our paper expression (3.3) of the CH is novel, and not directly evident from prior works. \n\n* Indeed, the submitted paper had some typos and we appreciate your indication. A throughout reading of the paper will correct them for the revised version. We also plan to better organize the exposition of Section 4. \n\nQuestions:\n\n* Unfortunately, Alg. 1 comes without any theoretical guarantees. It does not necessarily computes the MLE for the instance at hand. However, Fig. 2 in the global rebuttal file shows that Alg. 1 achieves exact recovery in a region very close to the information-theoretic limit. Indeed, two-stage algorithms have been shown to achieve optimal accuracy in binary SBMs and K-means achieve optimal accuracy in a Gaussian mixture model (see e.g., additional references [1]-[4] in comments to reviewer cu9t). \n\n* Note that the algorithms used for comparison, attSBM and IRsls in Figures 2 and 3 of the paper, are recent proposals for clustering networks with attributes (App. Net. Sci 2019 and ICML 2022, respectively). Note that algorithms proposed in [19, 20] are much older and are designed for dense networks (all possible network edges are present). In any case, we have performed experiments that indicate that using a sparse model (Alg. 1) yields much better accuracy than the dense model assumed in [19, 20] when the network is sparse, as is the case for most real networks (see plots in the global rebuttal file). Moreover, since [19, 20] assume a dense network (all possible edges are present, $O(n^2)$) their algorithms do not scale to large networks. In contrast, the complexity of Alg. 1 depends on the number of edges, which is often $O(n\\log n)$. We plan to revise the exposition of Section 4 and include these results and observations on complexity. \n\n* This is a very good question. We have performed experiments with Alg. 1 comparing its exact recovery performance (fraction of times the algorithm correctly recovers the community of all nodes) with the theoretical threshold for exact recovery proved in the paper (Theorem 1). Results are shown in Fig. 2 of the global rebuttal file. Interestingly, Alg. 1 achieves exact recovery in a region very close to the information-theoretic limit. This indicates that Alg. 1 is very promising! \n\n* We have not considered real datasets. Please see comments for reviewer coB1 and hHhv. "}]

Author rebuttal:
First and foremost, we would like to thank all four reviewers for their time spend reviewing our paper and their valuable comments. 
Some of the questions raised by the reviewers can be addressed with further experiments, as the following:

* how does Algorithm 1 perform when the network has more clusters?
* how sensitive is the performance of Algorithm 1 to the choice of the divergences $d_{\psi^*}$ and $d_{\phi^*}$?
* how does the performance of Algorithm 1 compare to the theoretical threshold for exact recovery derived in Section 3? 
* how does Algorithm 1 compare to algorithms published in [19] and [20]?


The attached PDF file has figures with the results of these questions. More precisely:


* Figures 1(a) and 3(c) have 4 clusters, and Figure 2(b) has 3 clusters. (Note that all these new experiments were run with same size clusters, and respective intra-cluster and inter-cluster edge densities $f_{in}$ and $f_{out}$)

* Figure 1 shows that using a divergence (distribution) for edge weights (Fig. 1(a)) and node attributes (Fig. 1(b)) different from the distribution used to generate the data does not impact the results. 

* Figure 2 compares the performance of Alg. 1 in terms of exact recovery (fraction of times the algorithm correctly recovers the community of all nodes) with the theoretical threshold for exact recovery proved in the paper (red curve in the plots) in two settings: 
(2a) binary weight with Gaussian attributes, and (2b) zero-inflated Gaussian weights with Gaussian attributes. Solid black and white squares represent fraction zero (no trial was recovered exactly) and one (all trials were exactly recovered) over 50 trials.

This is a very important numerical validation of Algorithm 1, and we plan to include it in the paper (to replace Figure 1 of the article, which does not explicitly show the theoretical curve). Due to limited time in the rebuttal phase, this new Figure 2 has a relatively large granularity and each pixel is averaged over 50 runs, but we can increase these numbers for the final version. 

* Figures 3(a) and (b) compare Algorithm 1 to the V-EM algorithm of [20] and to the Bregman algorithm of [19]. Note that algorithm [19] is a special case of Algorithm 1 for when the network is dense (all possible edges are present). Results indicate that when the network is sparse, [19] has poor performance (and not surprising since it assumes a dense network). The V-EM of [20] is also designed for dense networks, and while its performance on sparse networks is not poor, Algorithm 1 is superior (and not surprising, since it was designed for sparse networks). Last, since the models in [19, 20] assume a dense network (all possible edges are present, $O(n^2)$) their algorithms do not scale to large networks. In contrast, the complexity of Alg. 1 depends on the number of edges, which is often $O(n\log n)$. (The three algorithms had the same initialisation, and the performance of the initialization is given as a reference of a baseline to beat). 

* Finally, Figure 3(c) is similar to Figure 2(b) of the paper (binary network with Gaussian attributes) but with a larger number of clusters. We see that Algorithm 1 performs better than the algorithm of [8], which was a recently proposed algorithm to tackle sparse networks with binary edges and Gaussian attributes.

References:

[6] Arindam Banerjee, Srujana Merugu, Inderjit S Dhillon, Joydeep Ghosh, and John Lafferty. Clustering with Bregman divergences. Journal of machine learning research, 6(10), 2005. 

[8] Guillaume Braun, Hemant Tyagi, and Christophe Biernacki. An iterative clustering algorithm for the contextual stochastic block model with optimality guarantees. In International Conference on Machine Learning, pages 2257–2291. PMLR, 2022.

[19] Bo Long, Zhongfei Mark Zhang, and Philip S Yu. A probabilistic framework for relational clustering. In ACM International Conference on Knowledge Discovery and Data Mining (SIGKDD), pages 470–479, 2007.

[20] Mahendra Mariadassou, Stéphane Robin, and Corinne Vacher. Uncovering latent structure in valued graphs: A variational approach. The Annals of Applied Statistics, 4(2):715 – 742, 2010.

Meta-review: All reviewers agree to accept this paper. The paper is theoretically sound and sufficiently novel to grant acceptance at this conference. Experiments on synthetic data complement the theoretical results.

For a camera-ready version, please take into the account the comments from all reviewers regarding typos and clarifications. In particular, please include:
- a discussion of the novel techniques used in the proofs
- synthetic experiments for $k=3$ and $k=4$ clusters
- real-world experiments on CiteSeer, Cora, Cornell
- a discussion and experimental comparison with [19] and [20]
Decision: Accept (poster)