Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities
Authors: Miklos Z. Racz
Anirudh Sridhar
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Stochastic block model
community recovery
graph matching
correlated random graphs
information-theoretic limits

Abstract: We consider the task of learning latent community structure from multiple correlated networks. First, we study the problem of learning the latent vertex correspondence between two edge-correlated stochastic block models, focusing on the regime where the average degree is logarithmic in the number of vertices. We derive the precise information-theoretic threshold for exact recovery: above the threshold there exists an estimator that outputs the true correspondence with probability close to 1, while below it no estimator can recover the true correspondence with probability bounded away from 0. As an application of our results, we show how one can exactly recover the latent communities using \emph{multiple} correlated graphs in parameter regimes where it is information-theoretically impossible to do so using just a single graph.

Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities
Miklós Z. Rácz Department of ORFE Princeton University Princeton, NJ 08544 praczpprinceton edu
Anirudh Sridhar
Department Electrical and Computer Engineering
Princeton University
Princeton, NJ 08544
an anirudhs@princeton. edu
Abstract
We consider the task of learning latent community structure from multiple corre- lated networks. First, we study the problem of learning the latent vertex correspon- dence between two aigeecccrellted stochastic block models, focusing on the regime where the average degree is logarithmic in the number of vertices. We derive the precise information -hhooretcc threshold for exact recovery: above the threshold there exists an estimator that outputs the true correspondence with probability close to 1, while below it estimator can recover the true correspondence with probability bounded away from O. As an application of our results, we show how exactly recover the latent communities using multiple correlated graphs in parameter regimes where it is information- -hatttoointtorrtillllyyy impossible to do so using just single graph.
Introduction
Learning community structure in networks a ubiquitous inference task in several domains, including biology [33 4T). sociology [26], and machine learning [57 37 60). Recent decades have therefore
seen an explosion of work on the topic, leading to determining the fundamental
citoommation-thhorree [2 46), well
limits for learning communities in probabilistic generative models [ 3, 45 44
as algorithms that work well in practice
[55] B 22 Typically, such algorithms only leverage the
structure of the network (i.e., the configuration of node-node links). Increasingly, one often has
access to side information that can greatly improve the performance of inference algorithms.
There a vast literature on designing algorithms that incorporate various types of side information to aid in recovering communities networks. The works [2]]
g 63 56 39 leverage node-level information that is correlated with community memberships; here the sharp limits for community detection were conjectured by Deshpande
38
47
32
al.
2I and recently proven by Lu and
Sen (38] Another line of work [30] 5 51 52, 36 4 7 43
39 recovers communities from multi-
layer network, where the different layers are conditionally independent given the same community structure. Recently Ma and Nandy 39 synthesized these two strands of literature.
In contrast prior work, we explore scenarios where the side information comes in the form of multiple correlated networks, which is natural in several domains including social networks (49 53 35 computational biology [59], and machine learning [4]. In the context of social networks, for instance, many datasets are anonymized to protect the identity of users. Nevertheless, one may be able infer additional information about users from additional networks by noting that the interaction patterns of the same set of users are likely to be similar across networks 53 35]
In computational biology, an important goal is to study the functional properties of protein groups
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

through a pootein-protein interaction (PPI) network. Using the insight that functionally similar protein groups will have similar interaction structures, one can compare PPIs across species infer protein functions (59. In all of these examples, an important task, commonly known as graph matching, is to synthesize the information from multiple correlated networks in sensible manner.
To the best of our knowledge, we are the first to consider the use of multiple correlated networks for recovering communities. Specifically, we quantify, in an information- theooretcc sense, how much information we can gain from correlated networks in order to infer community structure. To this end, we focus on correlated graphs G1 and G2 drawn marginally according to the stochastic block model (SBM), which is widely recognized as the canonical probabilistic generative model for networks with community structure [.. The reason for studying this probabilistic model is twofold. For one, it serves as prototypical model for networks with community structure found in practice, hence the algorithms we develop will serve as a starting point for applications. Moreover, the SBM has well-defined ground-truth communities, so we can concretely study the correctness of algorithms in terms of whether the communities they output align with the ground truth.
2 Models and Questions
The stochastic block model (SBM). The SBM is perhaps the simplest and most well-known probabilistic generative model for networks with community structure. It was initially proposed by Holland, Laskey, and Leinhardt [31] and subsequently used as theoretical testbed for evaluating clustering algorithms on average-case networks (see, e.g.. [24 12 9). striking fact about the SBM is that it exhibits sharp information thhooretic phase transitions for various inference tasks, leading to a precise understanding of when community information can be extracted from network data. Such phase transitions were first conjectured by Decelle et al. (20] and were subsequently proven 2
rigorously by several authors 44 42 46
45 [. In summary, the SBM is a well-motivated and mathematically rich setting for studying inference tasks.
In this work we focus on the simplest setting, a SBM with two symmetric communities. For a positive integer n and p. E [0.1]. we construct G ~ SBM(n, q) as follows. The graph G' has n vertices, labeled by the elements of [n] == (1.....n) n). Each vertex E [n] has a community label a; {+1,- - 1}; these are drawn i. uniformly at random across all E [m]. Let o == {or]²= be the vector of community labels, with the two communities given by the sets V4 := fi E in] 0; +1}
and V_ := {i E [m] o, -13. Then, given the community labels the edges of G are drawn independently across vertex pairs as follows. For distinct i.j E [m),, o,o, = 1, then the edge ji is in G with probability p; else (i,j) is in G with probability q-
Community recovery. Generally speaking, a community recovery algorithm takes as input G (without knowledge of the community labels σ)) and outputs a community labeling Ø. The overlap between the estimated labeling and the ground truth is given by
n
ov σ) = n i=1
Σ o
In the formula for the overlap, we take an absolute value since the labelings a and -a specify the same community partition (and it is only possible to recover up to its sign). Moreover, notice that ov(ō, o is always between 0 and I, where a larger value corresponds to a better match between the estimated communities and the ground truth. Indeed, the algorithm succeeds in exactly recovering the communities (i.c., Ô = o or x -o) if and only if ov(ō σ) = 1.
In the logarithmic degree regime- oegime-thatin is, when p a log(n)/n /n and q B log(n)/n /n for some fixed constants a, 3 2 0-it is well-known that there is a sharp Information-theoree threshold for exactly recovering communities in the SBM 2 45 3 []. Specifically, if
Va
vB V2,
(2.1)
then exact recovery is possible: there is a polynomial-time algorithm which outputs an estimator ō satisfying lim P(ov(o, or = 1) = 1. On the other hand, if
Vo
vB < V2,
(2.2)
then exact recovery is impossible: for any estimator o, we have that lim P(ov(or, = 1) 0.

---

subssample
subsample
1,9,
G p,
(3)
(122)
1
G1
G2 (G22
(8)
10 (5)
12
(13)
(1)
Figure 1: Schematic showing the construction of correlated SBMs (see text for details).
Correlated SBMs. The goal of our work is to understand how side information in the form of multiple correlated SBMs affects the threshold given by (2.T) and (2.2) To construct pair of correlated SBMs, we define an additional parameter E [0, which controls the level of correlation between the two graphs. Formally, we construct (G1, G2) CSBM(n, p. q, 8) as follows. First, generate a parent graph G ~ SBM(n, p, 4). and let denote the community labels. Next, given G, we construct G1 and G22 by independent subsampling: each edge of is included in G₁ with probability s, independently of everything else, and non-edges of G' remain non-edges in G1; obtain G²2 independently in the same fashion. Note that G1 and G22 inherit the vertex labels from the parent graph G, and the community labels are given by in both graphs. Finally, we let n, be a uniformly random permutation of [n]. independently of everything else, and generate G2 by relabeling the vertices of 2 according to π. (e.g., vertex in G¹2 is relabeled to æ, (i) in G2). This last step in the construction of G2 reflects the observation that in applications, node labels are often obscured. This construction is visualized in Figure []
This model of correlated SBMs was first studied by Onaran, Erkip, and Garg (50 This process of generating correlated graphs (i.e., by first generating parent graph, independently subsampling it, and randomly permuting the labels) is a natural and common approach for inducing correlation in the formation of edges, and has been employed study correlated graphs from the Erdös-Rényi model (see, e.g., [53], as well as further references Section the Chung-Lu model 622, and the preferential attachment model (35).
An important property of the construction that marginally G₃ and G2 are both SBMss Specifically, since the subsampling probability is s, we have that G₁ SBM(n, ps, gs). In the logarithmic degree regime, where p = log(n) /n and q = 3 log(n)/n, n, 2. implies that the communities can be exactly recovered from G1 alone if
Va
3
(2.3)
A central question of our work is how can utilize the side information in G2 to go beyond the single-graph threshold (2.3) This is formalized as follows.
Objective 1 (Exact community recovery). Given (G1, G2) ~ CSBM n, a alog Blogn
.) deter-
mine conditions on a, B, and so that there exists an estimator = ā (G G2) satisfying
lim P(ov(( 11 20000
key observation that if the latent correspondence n, is known, then one can readily improve the achievability region in (2.3). Indeed, if n, is known, then one can reconstruct G¹2, from G2. We can then construct a new graph H. by "overlaying" G, and G² (i.e., taking their union). Formally, (i,j) is an edge in H. if and only if (i,j) is edge in G₁ or G An equivalent interpretation is that (i,j) an edge the parent graph G and is included in either G or G2 in the subsampling
process. The probability that the edge is not included in either G1 G² is (1 s)², so it follows
that H, ~ SBM (n, ax1 (1 2)2) log(n)/m /n 3( (1 - =) log ( (n)/n)))n)) m) By 2.1 it thus follows
that exact community recovery is possible
2
Va VB
(2.4)
(1
8)2
3

---

Since - (1 -1-55 = for E (0, implies that n, is known and if
2.4 is strict improvement over 2.3 Remarkably, this
2
2
V vB
1- S)2
then it recover exactly by combining information from G1 and G2. To make this rigorous, study when it is possible to exactly recover т. from 1 and G2. This task known as graph matching.
impossible to exactly recover a from G1 (or G2) alone, but one
Objective (Exact graph matching). Given (G1, G2) CSBM n, log Blogn s). determine conditions on a, 8, and so that there exists an estimator रे = (G1, G2) satisfying
lim P( T.) 1. 22000
While we have motivated graph matching as an intermediate step in recovering communities, is an important problem in its own right, with applications to data privacy in social networks [49] [3)
protein-protein interaction networks [59], and machine learning [15 14]. among others. In particular, is well known that graph matching algorithms
be used de-anonymize social networks (9)
showing that anonymity is not the same as privacy. Studying the fundamental limits of when graph matching is possible can serve to highlight the precise conditions when anonymity can indeed guarantee privacy, and when additional safeguards are necessary.
Although Objective has not been studied previously, there is strong evidence of a phase transition for exact recovery of r, in the logarithmic degree regime. In the special case of correlated Frdös-Rényí graphs- that is, when estimate exactly recovers T, with probability tending to 1 if s²a > 1. When o + 3, and assuming that the community labels are known in both graphs, Onaran, Garg, and Erkip (50 showed that exact
B Cullina and Kiyavash [16, 17 showed that the maximum likelihood
recovery of T. is possible if s(1 vi s2) (a 3) /2 3. Cullina et al.
19 also assuming that
community labels are known both graphs, stated (without proof) that exact recovery is possible sa + /2 > Since these works assume knowledge of community labels, it unelear if these conditions allow to recover т. based on knowledge of only G1 and G2. Nevertheless, they suggest that exact graph matching may be possible in the logarithmic degree regime.
Turning to impossibility results, in correlated Prdös-Rény: graphs, s²a < 1, then there is no estimator which exactly recovers T. with probability bounded away from zero [16] [7 61). For correlated SBMs, Cullina et al. 19 showed that one cannot exactly recover т. when saaa='(aaaaa 3)/2 < 1.
In particular, for correlated Frdós-Rényí graphs the information-theoree connectivity threshold for the intersection graph of G1 and G²z- (Given two graphs H1 and H2, the edge (i.j) is in the intersection graph of H, and H2 if and only if it is an edge in both H1 and Hz.) For correlated SBMs the connectivity threshold for the intersection graph is
threshold 2a 1 is the
82
+
1.
(2.5)
2
This suggests that 2.5) may be the information theoorttc threshold for exact recovery of T. for correlated SBMs. Our main result, Theorem 3.1 shows that this is indeed the case.
3 Results
We now describe our results, which address Objectives and In Section 3.1
we precisely characterize the fundamental information- limits for exact graph matching, thereby fully achieving Objective 2 In Section 3.2 we provide partial answers to Objective [ in particular, threshold for exact community recovery in the regime where s² (a 3)/2 > 1. Finally, in Section 3.3 we extend the ideas of Section establish achievability and impossibility results for exact community recovery with K correlated SBMs.
these provide the information-theoredt
3.1 Exact Graph Matching
We start with our main result, which determines the achievability region for exact graph matching in correlated SBMs, providing an estimator that correctly recovers the latent vertex correspondence above the information-thow theoretic threshold.

---

Theorem 3.1. Fix constants a, 3 and E [0.1]. Let (2), CSBM (n, o log log
Let 7t (GG G2) be vertex mapping that maximizes the number of agreeing edges between G1 and G2 (that is, the number of matched pairs of vertices for which an edge exists between them in both graphs). If
a 82
1,
(3.1)
2
then
lim P ( G2) R.) =1
We remark that the estimator used Theorem a natural and well-motivated estimator for the latent mapping n.. It was first considered by Pedarsani and Grossglauser (53) in the context of the correlated Pedōs-Rényí model, where is the maximum a posteriori (MAP) estimate [16 17 50]. As result, it achieves the cetommation-thhoree Bedōs--Rényi model [7 61]. This estimator has also been studied the context of correlated SBMs by Onaran, Erkip, and Garg [50] they show that if the commmunity labels of all vertices in G1 and G2 are known, then the permutation which maximizes the number of agreeing edges and is consistent with the community labels (i.e., does map vertex with label +1 to vertex of label -1 1) succeeds in recovering тı exactly, provided that the (suboptimal) condition s(1 vI - s2) (a 3) /2 3 holds. Theorem 3.1 improves on this result using a more refined analysis, obtaining the optimal condition (3.1), D and not assuming any knowledge of community labels.
threshold for exact recovery of r, in the correlated
The next result establishes a converse to Theorem 3.1 This was previously proven
19
Theorem 3.2. Fix constants a, 3 > and E [0, 1]. Les (G1, G2) ~ CSBM and suppose that
log log
52 a < 1.
(3.2)
2
Then for any estimator H(G,, G2), we have that lim (T G2) =..) =.
Together, Theorems 3.1 and 3 establish the fundamental information eeformation-thcoreticc limits for exact recovery of R., This is the natural generalization of the corresponding results for correlated Erdös- the same estimator स succeeds if s² 1, else if saa < 1, then
Rényi graphs: when estimator can exactly recover n, with probability bounded away from zero [17 61
An overview of the proofs of Theorems 3.1 and 3.2 is given in Section 5 with full details provided in
the Supplementary Material.
3.2 Exact Community Recovery
We now turn to exact community recovery with two correlated SBMs, formalizing the arguments of Section 2 The strategy is to first perform exact graph matching, then to combine the two graphs by taking their union with respect to matching, and finally to run an exact community recovery algorithm on this new graph.
Theorem 3.3. Fix constants a, B and E [0, 1]. Let (G1, G2) CSBM (n,, logo
3 log
13
Suppose that s2 (a 32/22 and
2
Va V
(3.3)
1 1 s)2
Then there is estimator ā @G1, G2) such that
lim IP (ov (ō, σ) =) =
000
The proof readily follows from Theorem and existing results on exact community recovery the
SBM 2 45 3 M.
5

---

46
35
35
35
30
0. 20
20
20
15
15
15
10
15
20
25
30
5
10
15
20
25
30
35
40
%
5
10
15
20
25
30
35
40
(a) Fixed = 0.25.
(b) Fixed & 0.5.
(c) Fixed = 0.75.
Figure 2: Phase diagrams for exact community recovery for fixed s, with a E [0, 40) and 3 [0 40] on the axes, Green region: exact community recovery is possible from G1 alone; Cyan region: exact community recovery impossible from G₁ alone, but it is possible from (G,, G2): Yellow region: exact community recovery is impossible from G₁ alone, unknown if it is possible from (G1, G2); Red region: exact community recovery impossible from (G1, G2).
0.8
0,8
0.8
0.4
0.4
02
0.0
0.0
0.0
(a) Fixed
(b) Fixed 3 10.
(c) Fixed 20.
Figure 3: Phase diagrams for exact community recovery for fixed B, with a E [0, 40] and E [0.1]
on the axes. (Colors in Fig.
Proof. Given permutation π mapping [n] to [n]. we let G1 Vx G2 be the union graph with respect
to n, so that (i is an edge in G1 Vr G2 and only (i,j) an edge G₁ or (i)),, (i)) an edge in G2. In the special case where G consisting of edges that are in either G₁ or Gz. It is readily seen that
T,., H. = G1 Vx. G2 is the subgraph of the parent graph
H. SBM n, a,,a11 (1- log B1 (1-1() (1-s)?) log
(3.4)
n
n
The algorithm study first computes (G1, G2) according Theorem 3.1 We then pick any community recovery algorithm that is known to succeed until the information-theore theoretic limit, and run it on H G1 V G2; we denote the result of this algorithm by ō (H). We can then write
P(ov(@ (f)) 1) P((ov(ō σ) = + # H.)
H. < P(ov( 1) + T.).
where, to obtain the inequality the second line, we have used that ā @ ã (H.) on the event A = H and that + H. implies # n.. Since exact community recovery on H. is possible In light of
when 3.3 holds
45 3 I. know that ((ov(@(H.))) a) * 1)
Theorem we also have that IP(R + π.) + when s² 2( + 3)/2 > 1, concluding the proof. nI
By the discussion in Section 2 Theorem 3.3 establishes the existence of region of the parameter space where (i) there exists an algorithm that can exactly recover the communities using both G, and G2, but (ii) it is -iteaattionthoootticllllll impossible to do using G1 (or G2) alone. Figures 2 and illustrate phase diagrams the parameter space, where this region is highlighted cyan.
To complement the achievability result of Theorem 3.3 our next result provides condition under which exact community recovery is information -irmaatioonthoortticllllll impossible.

---

1.0
1.0
0.6
0.6
0.6
0.0
5
10
20
25
30
10
15
20
25 30
35
%
10
15
20
25
35 40
(a) Fixed a/3 = 2.
(b) Fixed a/3 = 4.
(c) Fixed a/B = 6.
Figure Phase diagrams for exact community recovery for fixed a with [0, 40] and E [0. on the axes. (Colors as in Fig.
Theorem 3.4. Fix constants a, 3 and {0,0 11. Let (G1, G2) ~M CSBM (n, a log 3 log and suppose that
Va- VB (1-(1-57
2
(3.5)
Then for any estimator = (G1, G2), we have that lim P(ov(o σ) = 0. n-
The idea behind the proof is simulation argument. Recall H. G1 V G2 from the proof of Theorem 3.3 and note that H. SBM (n, a (1 s)²) log(n) /n, B(1 (1 s) log(n)/n). From H. It IS possible to simulate (G1, G2), and so if exact community recovery is possible given known 45 T that exact community recovery is not possible from H. if 3.5 holds. See Section D in the Supplementary Material for the full proof.
(G1, G2). then it also possible given H.. However,
We remark that Theorem 3.4 provides a partial converse to the achievability result in Theorem 3.3 tight when s² + 3)/2 1, but the precise information-theoretic threshold is unknown when (2 + 8)/2 < 1, which is the regime where exact graph matching fails. This leads to an interesting follow-up question: is exact graph matching necessary for the exact recovery of communities? We conjecture that it is not, which is formalized as follows.
Conjecture 3.5. There exists e c(a, B,s) > O such that if
3.3
holds and
s2 a +
2 21-6,
(3.6)
2
then there is an estimator Ô T (G1, G2) such that lim P(ov(ā,, = 2=000
In words, we believe that the communities can be exactly recovered even in regimes where exact graph matching is conjecture. The algorithm we shall use is the same one used in the proof of Theorem 3.3 we compute R, the permutation which maximizes the number of agreeing edges across G1 and G2, and
-teooreeiirlll impossible. We outline a possible way to prove this
then run an optimal community recovery algorithm on the union graph H = G1 Va G2. Define the correctly-man matchhd region C := {i [n]] 7(i) I. (i)). When s² + 8)/2 < 1, have that * [n] with high probability. However, we expect that [C = (1 o(1) m: that is, स coincides with n. on all but negligible fraction of vertices (which is known almost exact recovery). This is the case in correlated Erdós-Rény Rényi graphs [18] 61], so we expect to hold for correlated SBMs as well.
Let He be the subgraph of i restricted to the vertices in C. Since all vertices in C have been correctly matched, we expect that (possibly in an approximate sense)
Åe ~ SBM (C)).((1 - (1 =))) log n
n 3(1 - ()) log
(3.7)
In particular, if (3.3) holds, the communities of vertices in C can be exactly recovered. For vertices not in C, note that most of the neighbors will be elements of C, which will have correct community labels. If a: >> B, then the true community label of given vertex is the same the true label of most neighbors with high probability (when a < 3, the reverse true) [2), hence the community labels of vertices not in C can be correctly identified using majority vote.
7

---

Making the arguments above formal is challenging task. For one, though we may expect 3.7 hold if C is fixed set, it is in fact a random set depending on G₁. G2. and Ras so formally proving (3.7) requires a careful analysis. Moreover, we would like to use (3.7) to argue that running community recovery algorithm H (rather than Hc) perfectly recovers the communities in C. Rigorously justifying these points requires significant effort, so we leave to future work.
3.3 Multiple correlated stochastic block models
We next describe our results on how one can recover communities using K correlated stochastic block models, again using graph matching subroutine. Considering more than two networks is more and more important many applications, for instance in computational biology, where the increasing number of species for which protein-protein interaction networks are available can be leveraged for more powerful comparative studies (59
Formally, we construct (G1,..., Gk) ~ CSBM(n, P,, 8, K) as follows. First, generate a parent graph G ~ SBM(nn, p. q), and let denote the community labels. Next, given G, we construct G1 as well as G....., G"x by independently subsampling G with probability Finally, we let T T be i.i.d. uniformly random permutations of [ri), independent of everything else, and for 2 S k < K, generate G5 by relabeling the vertices of G¹2 according to ...
As in the case of two correlated graphs, the achievability and impossibility results depend on the structure of the union graph with respect to the true permutations n²
Theorem 3.6. Let (Gi,..,,Grr) Gk)
CSBM
11,
log n
Blogn 8, K))
Suppose that
1
8² (a + B) and
IV
B
(3.8)
(1 - s)
Then there is an estimator ē = =G(G,.... Gk) such that lim PPoov((, =
Analogously to Theorem 3.3 Theorem 3.6 establishes the existence of region of the parameter
space where (i) there exists an algorithm that can exactly recover the communities using all of G1,G2, G2, Gk, but (ii) it is information-theorriiaalll impossible to do so using only strict subset of G1, G2, G2,...,GKk
Our next result establishes an impossibility result which is analogous to Theorem 3.4
Theorem 3.7. Let (G1....,Grt CSBM
n, logn
B log
8, K) and suppose that
IV - V V sk=
(3.9)
Then for any estimator ō = (G1, G2), we have that lim Piov(o, σ) = 0.
We highlight a few interesting aspects of Theorems 3.6 and 3.7 As in the two-graph case, Theorem 3.7
provides partial converse the achievability result Theorem 3.6 it is tight in the regime (a 8)/2 > 1, but the correct threshold remains unknown when la + B) /2/22 < 1. Additionally, as K increases, the achievability and impossibility conditions (.8) and 3.9 converge to the conditions I - /BI /2 and I - /3 /2. which are the information-theorehe conditions for achievability and impossibility of community recovery in the parent graph G. In words, the more correlated graphs we observe, the less information lost when generating the observed graphs from the parent graph via the sampling process.
4 Related work
Our work naturally draws upon techniques in the graph matching literature well as the community recovery literature. Here, we elaborate on relevant work these fields that were not covered during the exposition of our model and main results.
8

---

Graph Matching, Most of the theoretical literature on graph matching has focused on correlated Erdós-Rény: random graphs, which was introduced by Pedarsani and Grossglauser [53]. Significant progress has been made in recent years in characterizing the fundamental information-theoreti limits for recovering the latent vertex correspondence ... Cullina and Kiyavash [T6] 17 first derived the precise pooomatioonthhoreee
conditions for exact recovery of IT, for sparse graphs (in sublinear- degree regime), and recently Wu, Xu, and Yu [6]] refined this to include linear degree regimes. Our results, in particular Theorems 3.1 and 3.2] are the natural generalizations of these previous works to correlated SBMs, determining the precise information-theoree threshold for exact recovery in this setting (and improving upon [50 19]).
Weaker notions of recovery (e.g.. almost exact recovery, partial recovery) have also been addressed for correlated Erdös- Rényi graphs (see [8] 27 29 28 [1] for more details). Recent work by Shirani, Erkip, and Garg [58] provides necessary and sufficient conditions for almost exact recovery in correlated SBMs. Our work is also a part of the growing literature studying correlated random graphs beyond the vrdōs-Rény) model (50
62
A major open question is whether there exist efficient algorithms for inferring т. in correlated Erdös- Rényi graphs. In particular, the estimators which are known to succeed up to the information-theorett threshold are usually given by the solution to a combinatorial optimization problem, for which a brute force search takes (n!) time. Significant improvements were recently made by 48 who provided n Ollog n) time algorithms for exactly recovering π.. For values of s close to recent work
provides polynomial-timg time algorithms for exact recovery 23 25 40)
Community Recovery in Multi-layer SBMs. We briefly review the literature multi-layer SBMs, as it is the form of side information studied in the literature that is closest to our work. Multi-layer SBMs were first introduced by Holland, Laskey, and Leinhardt, in their original work that introduced stochastic block models (31]. In this model, first a community labeling is chosen at random. Given the block structure, collection of SBMs on the same vertex with the same latent community labels are then generated, one for each layer, possibly with different (but known) edge formation probabilities. Variants of this model have been explored by several authors [30 5 51 52 36 7 but typically the layers are conditionally independent given the community labels. The works (43 39 additionally consider node-level information that is correlated with the latent community membership. While our work also considers multiple networks as side information, we emphasize that there are significant differences. For one, the networks we consider are not conditionally independent given the latent communities, but are also correlated through the formation of edges. Moreover, in the multi-layer setting the node labels are known, which completely removes the need for graph matching.
5 Overview of graph matching proofs
Let F. {(1-c)n/2 < VV. < (1 e)n/2} denote the event that the two communities are approx- imately balanced. Since the community labels are i.i.d. uniform, we have for any fixed 6 >> that P(F.) = 1 - 11)(1) as n oo; we may thus condition on F.. Let Sk be the set of permutations which mismatches k vertices in V+ and l2 vertices in V_. We show that if (..) holds, then there exists = e(a, 3) sufficiently small so that
Achievability of exact graph matching: Proof sketch of Theorem 3.1
PP ( E Sk (F.) S ((kg
(5.1)
To bound the probability that के A n., we then take a union bound over all the events ( E Sk such that k + k2 2 1. that is, there is at least one mismatched vertex, concluding the proof.
The key technical result which enables the proof is (5.)) this derived by deriving tight bounds for the generating function corresponding to the number of agreeing edges in G₁ and G2 with respect to a given permutation. In prior work on the graph matching problem in correlated Erdös-Rényí graphs, as well as for correlated Gaussian matrices, the aforementioned generating functions could be exactly computed [16] [7 61]. An important difference between work on these models and ours is that the stochastic block model is heterogeneous: the probability of edge formation is not i.i.d. over all vertex pairs, but varies depending on the latent community labels of the vertex pairs. As a result, the generating functions of interest cannot be explicitly computed. To handle this heterogeneity, we develop new techniques for bounding these generating functions. Specifically, we derive recursive bounds for the generating functions of interest function of the number of vertices; see Section C
9

---

in the Supplementary Material for details. We suspect that this method can be extended to analyze other classes of correlated networks with heterogeneous structure.
Impossibility of exact graph matching: Proof sketch of Theorem 3.2 Let H be the inter- section graph between G1 and G22- that is, (i.j) is edge in H if and only if (i, () is an edge in G1 and G2. Equivalently, (i,j) must be an edge in the parent graph G and must be included in both G1 and Gz.. Since the probability of the latter event is s², we see that H ~ SBM (n, as² log(n)/n, 3s log(n)/n). If sa B)/2 < 1, then H is not connected with probability tending to as n 7 oc. In particular, H has many singletons in this regime, which vertices that have non-overlapping neighborhoods in G1 and G2- Due to the lack of shared information, it is difficult to match such vertices across the two graphs, even for optimal estimators that have access to the ground-truth community labeling σ. In particular, one can show that the maximum a posteriori (MAP) estimator of t,, given G₁, G2, and a cannot output n, with probability bounded away from zero, so neither can any other estimator.
Discussion and future work
In this work, we studied the problem of exact community recovery given multiple correlated SBMs as side information. Specifically, our goal was to understand how this side information changes the fundamental information thheoretic threshold for achievability and impossibility of exact community recovery. Strikingly, using multiple correlated SBMs allows one to exactly recover communities in regimes where it is information ceeemattonnthcorrticalyy theoretically impossible to do so using a single graph.
Precisely, we determine the sharp iiformatioontheorect condition for exact graph matching in a pair of correlated SBMs. We then apply this to determine conditions for achievability and impossibility of exact community recovery. In the regime where exact graph matching is achievable, we identify the precise information-theoret
conditions for achievability and impossibility of exact community recovery. We also discuss extensions with K 2 2 correlated SBMs.
Our work leaves open several important avenues for future work, which we outline below.
Closing the information-theoreti gaps in exact community recovery. Together, The- orems 3.3 and 3.4 show that in the regime sa + 3)/2 > 1, have identified the information-fhheorric threshold between impossibility and achievability for exact commu- nity recovery. However, we do not have achievability results for the regime (3 < 1, since exact graph matching is not possible in this case. This leads to the following natural question which is formalized in Conjecture 3.5 is exact graph matching needed for exact community recovery? We believe the answer is no; we expect that showing this rigorously will lead to new algorithms for jointly synthesizing networks and identifying communities.
Efficient algorithms. Our achievability algorithms rely graph matching as a subroutine, which is computationally expensive. Do there exist efficient algorithms for graph matching in the correlated SBM model? If not, is it possible to recover communities exactly using polynomial time relaxation of the graph matching subroutine?
General correlated stochastic block models. For simplicity of exposition, we focused on the simplest setting of the stochastic block model where there are two balanced communities. A natural future direction is to extend our results to account for more general SBMs with multiple communities (which are understood well in the single graph setting [l].
Beyond exact community recovery. Besides exact recovery, natural notions of community recovery include almost exact recovery, where the goal is recover all but negligible fraction of community labels, and partial recovery, where the goal is to do better than random labeling. Using correlated networks as side information to accomplish these tasks is a natural and exciting direction. A key challenge is that in the regimes where phase transitions occur for almost exact and partial recovery (see (I) exact graph matching is information--heoreiinn box. Solving this problem will lead to new methods for community detection based on data from multiple networks.
impossible by Theorem 3.2 hence this cannot be used as a black
10

---

Acknowledgments and Disclosure of Funding
We thank Jasmine Nirody for help with figures. We gratefully acknowledge funding support from
NSF under Grant DMS 1811724 (to M.Z.R. and A.S.) and RAPID Grant IIS-2026982 (to A.S.).
References
[1] E. Abbe. Community detection and stochastic block models: recent developments. Journal of Machine Learning Research, 18(1):6446-655 6531, 2017.
[2] E. Abbe, A. S. Bandeira, and G. Hall. Exact recovery in the stochastic block model. IEEE Trunsactions on Information Theory, 62(1):471-487, 2016.
[3] E. Abbe and C. Sandon. Community detection in general stochastic block models: Funda- mental limits and efficient algorithms for recovery. 2015 JEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), pages 670 770-688, 2015.
[4] H. T. Ali, S. Liu, Y. Yilmaz, R. Couillet, I. Rajapakse, and A. Hero. Latent heterogeneous multilayer community detection. In 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 8142-8146, 2019.
[5] J. Arroyo, A. Athreya, Cape, G. Chen, C. E. Priebe, and J. T. Vogelstein. Inference for multiple heterogeneous networks with common invariant subspace. Preprint available 10026 2020.
[6] B. Barak, C.-N. Chou, Z. Lei, T. Schramm, and Y. Sheng. (Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs. In Advances in Neural Information Processing Systems (NeurIPS), pages 9190-99 109009198,111 2019.
[7] S. Bhattacharyya and S. Chatterjee. Consistent Recovery of Communities from Sparse Multi- relational Networks: A Scalable Algorithm with Optimal Recovery Conditions. In Complex Networks XI, pages 92-103, 2020.
[8] N. Binkiewicz, J. T. Vogelstein, and K. Rohe. Covariate-assisted spectral clustering. Biometrika, 104(2)3361-37) -3776 2017. 2017.
[9] R. B. Boppana. Eigenvalues and graph bisection: An average-case analysis. In 28th Annual Symposium on Foundations of Computer Science (FOCS), pages 280-285, 1987.
[10] C. Bordenave, M. Lelarge, and L. Massoulié, Non-backtracking spectrum of random graphs: Community detection and non-regular ramanujan graphs. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), pages 1347-1357, 2015.
[11] C. Bothorel, J. D. Cruz, M. Magnani, and B. Micenková. Clustering attributed graphs: models, measures and methods. Network Science, 3(3):408-444, 2015.
[12] T. Bui, S. Chaudhuri, T. Leighton, and M. Sipser. Graph Bisection Algorithms With Good Average Case Behavior. In 25th Annual Symposium on Foundations of Computer Science (FOCS), pages 181-192, 1984.
[13] Chen and Yuan. Detecting functional modules in the yeast protein interaction network. Bioinformatics, 22(18))2283-2290 2006.
[14] D. Conte, P. Foggia, C. Sansone, and M. Vento. Thirty years of graph matching in pattern recognition. International JountiaallJJJuraal of Pattern Recognition and Artificial Intelligence, 18(03):265- 298, 2004.
[15] Cour, Srinivasan, and Shi. Balanced graph matching. In Advances in Neural Information Processing Systems (NeurIPS), pages 313-320, 2007.
[16] D. Cullina and N. Kiyavash. Improved Achievability and Converse Bounds for Erdös-Rényi Graph Matching. SIGMETRICS Perform. Eval. Rev,, (4(1))63-72,201
11

---

[17] D. Cullina and N. Kiyavash. Exact alignment recovery for correlated Erdös- Erdös-Rényi Rényi graphs. Preprint available at at/ttps://arxiv wwwpaawwwww..gg////..aaa...
2018.
[18] D. Cullina, N. Kiyavash, P. Mittal, and H. V. Poor. Partial Recovery of Erdös-Rényi Graph Alignment via k-Core Alignment. SIGMETRICS Perform. Eval. Rev, 48(1);99-100, 2020.
[19] D. Cullina, K. Singhal, N. Kiyavash, and P. Mittal. On the simultaneous preservation of privacy and community structure in anonymized networks. Preprint available at attttps://arxiii org/ abs/ bbss/100.rm 0 08028 2016.
[20] A. Decelle, F. Krzakala, C. Moore, and L. Zdehorová. Asymptotic analysis of the stochas- tic block model for modular networks and its algorithmic applications. Physical Review E, 84(6):066106, 2011.
[21] Y. Deshpande, S. Sen, A. Montanari, and E. Mossel. Contextual Stochastic Block Models. In Advances in Neural Information Processing Systems (NeurIPS), pages 8581-859) 2018.
[22] I. S. Dhillon, Y. Guan, and B. J. Kulis. Kernel k-means, spectral clustering and normalized cuts. In ACM SIGKDD Int. Conf. on Knowledge Discovery and Duta Mining (KDD), 2004.
[23] Ding, Z. Ma, Y. Wu, and J. Xu. Efficient random graph matching via degree profiles. Probability Theory and Related Fields, 179(1):29-115, 2021.
[24] M. Dyer and A. Frieze. The solution of some random NP-hard problems in polynomial expected time. Journal of Algorithms, 10(4):451-489) 1989.
[25] Z. Fan, C. Mao, Y. Wu, and J. Xu, Spectral graph matching and regularized quadratic relaxations: Algorithm and theory. Proc. of the 37th Int. Conf. on Machine Learning (ICML), volume 119 of Proc. of Machine Learning Research, pages 2985-2995, PMLR, 2020.
[26] S. Fortunato. Community detection in graphs. Physics Reports, 486(3):75 2010.
[27] L. Ganassali and L. Massoulié. From tree matching to sparse graph alignment. In Proceedings of the Thirty Third Conference on Learning Theory (COLT), volume 125 of Proceedings of Machine Learning Research, pages 1633-1665. PMLR, 09-12 Jul 2020.
[28] L. Ganassali, L. Massoulié, and M. Lelarge. Impossibility of Partial Recovery in the Graph Alignment Problem. Preprint available at
org/ abs abs/2122. 02685, 2021.
[29] G. Hall and I.. Massoulié. Partial Recovery in the Graph Alignment Problem. Preprint available /httts:://arttt http//arvvvoooraaaa//// abs 20abs//200..00 00533 2020.
[30] Q. Han, K. Xu, and E. Airoldi. Consistent estimation of dynamic and multi-layer block models. In International Conference on Machine Learning (ICML), pages 1511-1520. PMLR, 2015.
[31] P. W. Holland, K. B. Laskey, and S. Leinhardt. Stochastic blockmodels: First steps. Social Networks, 5(2):109- 137, 1983.
[32] V. Kanade, E. Mossel, and T. Schramm. Global and Local Information in Clustering Labeled Block Models. IEEE Transactions on Information Theory, 62(10))5906-5917, 2016.
[33] G. Karypis and V. Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing, 20(1):359-392 1998.
[34] E. Kazemi and M. Grossglauser. MPGM: Scalable and Accurate Multiple Network Alignment. IEEF/ACM Trans. on Computational Biology and Bioinformatics, 1766):240-20522, 2019.
[35] N. Korula and S. Lattanzi, An efficient reconciliation algorithm for social networks. Proceedings of the VLDB Endowment, 755)3777-388 2014.
[36] J. Lei, K. Chen, and B. Lynch. Consistent community detection in multi-layer network data. Biometrika, 107(1):61-73 12 2019.
[37] G. Linden, B. Smith, and York. Amazon.com recommendations: item-to-item collaborative filtering. IEEE Internet Computing, 7(1):76-80, 2003.
12

---

[38] C. Lu and S. Sen. Contextual stochastic block model: Sharp thresholds and contiguity. Preprint 09841 2020.
available at
[39] Z. Ma and S. Nandy, Community Detection with Contextual Multilayer Networks. Preprint available at
2021.
[40] C. Mao, M. Rudelson, and K. Tikhomirov. Random Graph Matching with Improved Noise Robustness. Preprint available at ltttps://axxiiiii org/ hbs///b///// ataaabb//1110 2201. 11783 2021.
[41] E. M. Marcotte, M. Pellegrini, H.-L. Ng. D. W. Rice, T. O. Yeates, and D. Eisenberg. De- tecting protein function and protein-protein interactions from genome sequences. Science, 285(5428):551-73,, 1999.
[42] L. Massoulié. Community detection thresholds and the weak Ramanujan property. In Proc. of the 46th Annual ACM Symposium Theory of Computing (STOC), pages 694-6094 2014.
[43] V. Mayya and G. Reeves. Mutual information in community detection with covariate information and correlated networks. In 2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 602-607, 2019.
[44] H. Mossel, J. Neeman, and A. Sly. Reconstruction and estimation in the planted partition model. Probability Theory and Related Fields, 162, 07 2014.
[45] E. Mossel, J. Neeman, and A. Sly. Consistency thresholds for the planted bisection model. Electronic Journal of Probability, 21 (noone): 24, 2016.
[46] E. Mossel. J. Neeman, and A. Sly. proof of the block model threshold conjecture. Combina- torica, 38(3):665-22) 708, 2018.
[47] E. Mossel and J. Xu. Local Algorithms for Block Models with Side Information. In Proc. of the ACM Conf. on Innovations in Theoretical Computer Science (ITCS), pages 71 71-80, 2016.
[48] E. Mossel and Xu. Seeded graph matching via large neighborhood statisties. In Proc. of the 30th Ann. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1005-1014, 2019.
[49] A. Narayanan and V. Shmatikov. De-anonymizing social networks. In Proceedings of the 30th IFFE Symposium on Security and Privacy, pages 173-187. IEEE Computer Society, 2009.
[50] E. Onaran, S. Garg, and E. Erkip. Optimal de-anonymization in random graphs with community structure. In 2016 50th Asilomar Conference on Signals, Systems and Computers, pages 713-713 IEEE, 2016.
[51] S. Paul and Y. Chen. Null Models and Community Detection in Multi-Layer Networks. Preprint available at httts:://arxi: org/ abs/a/ass...//////////////////ea 1608. 00623, 2020.
[52] S. Paul and Y. Chen. Spectral and matrix factorization methods for consistent community detection in multi-layer networks. The Annals of Statistics, 48(1):230 - 250, 2020.
[53] P. Pedarsani and M. Grossglauser. On the privacy of anonymized networks. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pages 1235-1243, 2011.
[54] M. Z. Rácz and A. Sridhar. Correlated randomly growing graphs. Preprint available at https: bttps:///rrxiv org/ abs 13537 2020.
[55] Y. Ruan, D. Fuhry, and Parthasarathy. Efficient community detection in large networks using content and links. In Proceedings of the 22nd International Conference on World Wide Web, WWW '13, page 1089-1098. New York, NY, USA, 2013.
[56] H. Saad and Nosratinia. Recovering a single community with side information. IEEE Transactions on Information Theory, (6(12))7939-799) 2020.
[57] S. Sahebi and W. Cohen. Community recommendations: solution to the cold start problem. In Workshop on Recommender Systems and the Social Web (RSWEB), held in conjunction with ACM RecSys' 11, October 2011.
13

---

[58] F. Shirani, S. Garg, and E. Erkip. A concentration of measure approach to correlated graph matching. IEEE Journal on Selected Areas in Information Theory, 2(1):338-233 2021.
[59] R. Singh, J. Xu, and B. Berger. Global alignment multiple protein interaction networks with application to functional orthology detection. Proceedings of the National Academy of Sciences, 105(35):12763- 127799 2008.
[60] R. Wu, Xu, R. Srikant, L.. Massoulie, M. Lelarge, and B. Hajek. Clustering and inference from pairwise comparisons. In Proc. of the 2015 ACM SIGMETRICS Int. Conf. on Measurement and Modeling of Computer Systems, SIGMETRICS '15, page 449-450, 2015.
[61] Y. Wu, J. Xu, and S. H. Yu. Settling the Sharp Reconstruction Thresholds of Random Graph Matching. Preprint available at
2021.
[62] I.. Yu, Xu, and X. Lin. The Power of D-hops in Matching Power-Law Graphs. Preprint available at filhtps:: /tatpps//arxiv.... wwwp//iiiorreeeeee httpg/bs//10..../ 12975 2021.
[63] Y. Zhang, E. Levina. and J. Zhu. Community detection in networks with node features. Electronic Journal of Statistics, 1052):313--318,, 2016.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See page 4.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] The main text provides a full proof of Theorem a33 and proof sketches of the other theorems. Full proofs are in the Supplementary Material.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]] Relevant prior work
on models (all theoretical) is cited and discussed in detail throughout the paper.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you's 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "xDjFeRyKil-", "reviewer": "Reviewer_DFob", "summary": "This paper revisits the community detection problem from a theoretical perspective. The community detection problem on the SBM is now well-understood, this paper looks at a case where 2 correlated SBMs are given instead of only one. The nodes of the 2 SBMs represent the same population but the mapping between the nodes of the 2 SBMs is not known. This is a natural extension of the mathematical problem of community detection on a single SBM motivated for example by de-anonymizing social networks.\nThe authors obtain partial results for exact recovery. A natural algorithm is to first align the 2 SBMs and then used the union of the 2 SBMs which is still a SBM to find the communities. The authors fully characterize when exact alignment is possible and then provide sufficient conditions for exact recovery. They also prove a partial converse result and provide conditions under which community recovery is information theoretically impossible.", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is very clear, well written and easy to read. I think that this line of work is a very natural extension for the SBM and will lead to subsequent works. As the authors claim, their work is a first step and I suspect that it will trigger interest in the crowd working on the theory of ML.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "OK", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "wiMFJoDNCkX", "reviewer": "Reviewer_maHr", "summary": "This paper provides necessary and sufficient conditions for exact recovery problems in a two-community correlated stochastic block model (SBMs). In this model, correlated SBMs are generated on the same set of vertices in a natural way and then the vertices of  one of the SBMs is randomly permuted. The paper gives necessary and sufficient conditions for 1) recovering the (unknown) permutation to recover the correspondence between the two SBMs and 2) recovering the underlying community memberships.  The extension to multiple correlated SBMs in also considered. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is clearly written. It provides a nice descriptions of the problem and the results are easy to follow. Overall, I enjoyed reading it. \n\nThe key part of the proof requires a careful analysis of the conditions for finding the graph matching. While it seems the main approach builds upon previous work, there are a number of technical details which are well explained in the supplementary material. I think this analysis should also be viewed as a useful contribution of the paper. \n\nThe significance and novelty are on par with related work in the literature. Also, similar to other work in the literature, the model is not very realistic so these results are more an exercise in mathematical analysis rather than shedding new insight into community detection problems in practice. Along these lines, one may question whether exact community recovery is a realistic objective, as opposed to approximate recovery. The authors do mention approximate recovery in the future work section.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The assumptions for the theoretical results are clearly stated.  Given the theoretical nature of this work I do not see the need for any more discussion on societal impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "ut8HpkyykX", "reviewer": "Reviewer_aMdS", "summary": "This paper studies the task of learning latent community structure from two correlated Stochastic Block Models (SBM). They provide a information theoretic threshold above which there exists a estimator that learns the community structure with probability 1, and below which no estimator can recover the true correspondence with some probability away from 0.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This is a well written paper that not only is a precursor for using multiple correlated graphs to learn underlying latent communities, it demonstrates the advantages of using multiple graphs instead of a single graph (Theorem 3.6). The authors have shown robust and novel understanding of the subject as well as described conjectures on where future research work in this area could potentially head. I find that this adds to the significance of their results. Clear accept.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "-4sZRYWpmKS", "reviewer": "Reviewer_dpAb", "summary": "This paper studies the exact graph matching problem in correlated stochastic block model. With the exact graph matching function, classical community detection algorithm can achieve exact community recovery.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main contribution of the this paper is the analysis on phase transaction on the possibility on exact graph matching in correlated stochastic block model. Existing literature only solves the problem with correct community labels. The result is interesting and substantial in network analysis. \nThe paper is well organized and reader-friendly.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The author has clearly indicated the limitation of this paper. The contribution to the community recovery problem is actually limited. The paper has not solved the community detection problem. Given the true matching function of the nodes, community recovery can be obtained by existing algorithms. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a fine theoretical contribution showing how an initial step of graph matching of correlated graphs yields improved results to subsequently perform community detection, assuming graphs sampled from a correlated stochastic block model. The reviews are quite positive. Indeed joint consideration of multiple graphs to perform tasks such as community detection is a very natural strategy, and does not seem to have received much attention in the past. This makes the paper's contribution all the more valuable, hence the recommendation to accept. 
Decision: Accept (Spotlight)