Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities
Year: 2021

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 multiple correlated graphs in parameter regimes where it is information-theoretically impossible to do so using just a single graph.

heading: 1 Introduction
text: Learning community structure in networks is a ubiquitous inference task in several domains, including biology [13, 41], 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 information-theoretic limits for learning communities in probabilistic generative models [1, 2, 3, 45, 44, 42, 46], as well as algorithms that work well in practice [55, 33, 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 is a vast literature on designing algorithms that incorporate various types of side information to aid in recovering communities in networks. The works [21, 38, 47, 32, 8, 63, 11, 56, 39] leverage node-level information that is correlated with community memberships; here the sharp limits for community detection were conjectured by Deshpande et al. [21] and recently proven by Lu and Sen [38]. Another line of work [30, 5, 51, 52, 36, 4, 7, 43, 39] recovers communities from a multilayer 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 to 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 [15, 14]. In the context of social networks, for instance, many datasets are anonymized to protect the identity of users. Nevertheless, one may be able to 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 [49, 53, 35]. In computational biology, an important goal is to study the functional properties of protein groups
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
through a protein-protein interaction (PPI) network. Using the insight that functionally similar protein groups will have similar interaction structures, one can compare PPIs across species to 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 a 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-theoretic 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 [31, 1]. The reason for studying this probabilistic model is twofold. For one, it serves as a 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.

heading: 2 Models and Questions
text: 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 a theoretical testbed for evaluating clustering algorithms on average-case networks (see, e.g., [24, 12, 9]). A striking fact about the SBM is that it exhibits sharp information-theoretic 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 rigorously by several authors [44, 42, 46, 2, 45, 3, 10, 1]. 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, q ∈ [0, 1], we construct G ∼ SBM(n, p, q) as follows. The graph G has n vertices, labeled by the elements of [n] := {1, . . . , n}. Each vertex i ∈ [n] has a community label σi ∈ {+1,−1}; these are drawn i.i.d. uniformly at random across all i ∈ [n]. Let σ := {σi}ni=1 be the vector of community labels, with the two communities given by the sets V+ := {i ∈ [n] : σi = +1} and V− := {i ∈ [n] : σi = −1}. Then, given the community labels σ, the edges of G are drawn independently across vertex pairs as follows. For distinct i, j ∈ [n], if σiσj = 1, then the edge (i, j) 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
ov(σ̂,σ) := 1
n ∣∣∣∣∣ n∑
i=1
σ̂iσi ∣∣∣∣∣ . In the formula for the overlap, we take an absolute value since the labelings σ and −σ specify the same community partition (and it is only possible to recover σ up to its sign). Moreover, notice that ov(σ̂,σ) is always between 0 and 1, 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.e., σ̂ = σ or σ̂ = −σ) if and only if ov(σ̂,σ) = 1. In the logarithmic degree regime—that is, when p = α log(n)/n and q = β log(n)/n for some fixed constants α, β ≥ 0—it is well-known that there is a sharp information-theoretic threshold for exactly recovering communities in the SBM [2, 45, 3, 1]. Specifically, if∣∣∣√α−√β∣∣∣ > √2, (2.1) then exact recovery is possible: there is a polynomial-time algorithm which outputs an estimator σ̂ satisfying limn→∞ P(ov(σ̂,σ) = 1) = 1. On the other hand, if∣∣∣√α−√β∣∣∣ < √2, (2.2) then exact recovery is impossible: for any estimator σ̃, we have that limn→∞ P(ov(σ̃,σ) = 1) = 0.
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.1) and (2.2). To construct a pair of correlated SBMs, we define an additional parameter s ∈ [0, 1] which controls the level of correlation between the two graphs. Formally, we construct (G1, G2) ∼ CSBM(n, p, q, s) as follows. First, generate a parent graph G ∼ SBM(n, p, q), and let σ denote the community labels. Next, given G, we construct G1 and G′2 by independent subsampling: each edge of G is included in G1 with probability s, independently of everything else, and non-edges of G remain non-edges in G1; we obtain G′2 independently in the same fashion. Note that G1 and G ′ 2 inherit the vertex labels from the parent graph G, and the community labels are given by σ in both graphs. Finally, we let π∗ be a uniformly random permutation of [n], independently of everything else, and generate G2 by relabeling the vertices of G′2 according to π∗ (e.g., vertex i 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 1.
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 a 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 to study correlated graphs from the Erdős-Rényi model (see, e.g., [53], as well as further references in Section 4), the Chung-Lu model [62], and the preferential attachment model [35].
An important property of the construction is that marginally G1 and G2 are both SBMs. Specifically, since the subsampling probability is s, we have that G1 ∼ SBM(n, ps, qs). In the logarithmic degree regime, where p = α log(n)/n and q = β log(n)/n, (2.1) implies that the communities can be exactly recovered from G1 alone if ∣∣∣√α−√β∣∣∣ > √2
s . (2.3)
A central question of our work is how one 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, α lognn , β logn n , s ) , deter-
mine conditions on α, β, and s so that there exists an estimator σ̂ = σ̂(G1, G2) satisfying
lim n→∞
P(ov(σ̂,σ) = 1) = 1.
A key observation is that if the latent correspondence π∗ is known, then one can readily improve the achievability region in (2.3). Indeed, if π∗ is known, then one can reconstruct G′2 from G2. We can then construct a new graph H∗ by “overlaying" G1 and G′2 (i.e., taking their union). Formally, (i, j) is an edge in H∗ if and only if (i, j) is an edge in G1 or G′2. An equivalent interpretation is that (i, j) is an edge in the parent graph G and it is included in either G1 or G′2 in the subsampling process. The probability that the edge is not included in either G1 or G′2 is (1− s)2, so it follows that H∗ ∼ SBM ( n, α(1− (1− s)2) log(n)/n, β(1− (1− s)2) log(n)/n ) . By (2.1) it thus follows that exact community recovery is possible if∣∣∣√α−√β∣∣∣ > √ 2 1− (1− s)2 . (2.4)
Since 1 − (1 − s)2 > s for s ∈ (0, 1), (2.4) is a strict improvement over (2.3). Remarkably, this implies that if π∗ is known and if√
2 s > ∣∣∣√α−√β∣∣∣ > √ 2 1− (1− s)2 ,
then it is information-theoretically impossible to exactly recover σ from G1 (or G2) alone, but one can recover σ exactly by combining information from G1 and G2. To make this rigorous, we study when it is possible to exactly recover π∗ from G1 and G2. This task is known as graph matching.
Objective 2 (Exact graph matching). Given (G1, G2) ∼ CSBM ( n, α lognn , β logn n , s ) , determine
conditions on α, β, and s so that there exists an estimator π̂ = π̂(G1, G2) satisfying lim n→∞ P(π̂ = π∗) = 1.
While we have motivated graph matching as an intermediate step in recovering communities, it is an important problem in its own right, with applications to data privacy in social networks [49, 53], protein-protein interaction networks [59], and machine learning [15, 14], among others. In particular, it is well known that graph matching algorithms can be used to de-anonymize social networks [49], 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 2 has not been studied previously, there is strong evidence of a phase transition for exact recovery of π∗ in the logarithmic degree regime. In the special case of correlated Erdős-Rényi graphs—that is, when α = β—Cullina and Kiyavash [16, 17] showed that the maximum likelihood estimate exactly recovers π∗ with probability tending to 1 if s2α > 1. When α ̸= β, and assuming that the community labels are known in both graphs, Onaran, Garg, and Erkip [50] showed that exact recovery of π∗ is possible if s(1− √ 1− s2) (α+ β) /2 > 3. Cullina et al. [19], also assuming that community labels are known in both graphs, stated (without proof) that exact recovery is possible if s2(α+ β)/2 > 2. Since these works assume knowledge of community labels, it is unclear 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 Erdős-Rényi graphs, if s2α < 1, then there is no estimator which exactly recovers π∗ with probability bounded away from zero [16, 17, 61]. For correlated SBMs, Cullina et al. [19] showed that one cannot exactly recover π∗ when s2(α+β)/2 < 1.
In particular, for correlated Erdős-Rényi graphs the information-theoretic threshold s2α = 1 is the connectivity threshold for the intersection graph of G1 and G′2. (Given two graphs H1 and H2, the edge (i, j) is in the intersection graph of H1 and H2 if and only if it is an edge in both H1 and H2.) For correlated SBMs the connectivity threshold for the intersection graph is
s2 ( α+ β
2
) = 1. (2.5)
This suggests that (2.5) may be the information-theoretic threshold for exact recovery of π∗ for correlated SBMs. Our main result, Theorem 3.1, shows that this is indeed the case.

heading: 3 Results
text: We now describe our results, which address Objectives 1 and 2. In Section 3.1, we precisely characterize the fundamental information-theoretic limits for exact graph matching, thereby fully achieving Objective 2. In Section 3.2, we provide partial answers to Objective 1; in particular, these provide the information-theoretic threshold for exact community recovery in the regime where s2(α+β)/2 > 1. Finally, in Section 3.3, we extend the ideas of Section 3.2 to establish achievability and impossibility results for exact community recovery with K correlated SBMs.

heading: 3.1 Exact Graph Matching
text: 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-theoretic threshold.
Theorem 3.1. Fix constants α, β > 0 and s ∈ [0, 1]. Let (G1, G2) ∼ CSBM ( n, α lognn , β logn n , s ) .
Let π̂(G1, G2) be a 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
s2 ( α+ β
2
) > 1, (3.1)
then lim n→∞ P (π̂(G1, G2) = π∗) = 1.
We remark that the estimator π̂ used in Theorem 3.1 is a natural and well-motivated estimator for the latent mapping π∗. It was first considered by Pedarsani and Grossglauser [53] in the context of the correlated Erdős-Rényi model, where it is the maximum a posteriori (MAP) estimate [16, 17, 50]. As a result, it achieves the information-theoretic threshold for exact recovery of π∗ in the correlated Erdős-Rényi model [17, 61]. This estimator has also been studied in 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 not map a vertex with label +1 to a vertex of label −1) succeeds in recovering π∗ exactly, provided that the (suboptimal) condition s(1− √ 1− s2) (α+ β) /2 > 3 holds. Theorem 3.1 improves on this result using a more refined analysis, obtaining the optimal condition (3.1), and not assuming any knowledge of community labels.
The next result establishes a converse to Theorem 3.1. This was previously proven in [19]. Theorem 3.2. Fix constants α, β > 0 and s ∈ [0, 1]. Let (G1, G2) ∼ CSBM ( n, α lognn , β logn n , s ) and suppose that
s2 ( α+ β
2
) < 1. (3.2)
Then for any estimator π̃(G1, G2), we have that lim n→∞ P(π̃(G1, G2) = π∗) = 0.
Together, Theorems 3.1 and 3.2 establish the fundamental information-theoretic limits for exact recovery of π∗. This is the natural generalization of the corresponding results for correlated ErdősRényi graphs: when α = β, the same estimator π̂ succeeds if s2α > 1, else if s2α < 1, then no estimator can exactly recover π∗ 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.

heading: 3.2 Exact Community Recovery
text: 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 the matching, and finally to run an exact community recovery algorithm on this new graph.
Theorem 3.3. Fix constants α, β > 0 and s ∈ [0, 1]. Let (G1, G2) ∼ CSBM ( n, α lognn , β logn n , s ) . Suppose that s2 (α+ β) /2 > 1 and∣∣∣√α−√β∣∣∣ > √ 2 1− (1− s)2 . (3.3)
Then there is an estimator σ̂ = σ̂(G1, G2) such that
lim n→∞
P (ov (σ̂,σ) = 1) = 1.
The proof readily follows from Theorem 3.1 and existing results on exact community recovery in the SBM [2, 45, 3, 1].
Proof. Given a permutation π mapping [n] to [n], we let G1 ∨π G2 be the union graph with respect to π, so that (i, j) is an edge in G1 ∨π G2 if and only if (i, j) is an edge in G1 or (π(i), π(j)) is an edge in G2. In the special case where π = π∗, H∗ := G1 ∨π∗ G2 is the subgraph of the parent graph G consisting of edges that are in either G1 or G′2. It is readily seen that
H∗ ∼ SBM ( n, α(1− (1− s)2) log n
n , β(1− (1− s)2) log n n
) . (3.4)
The algorithm we study first computes π̂(G1, G2) according to Theorem 3.1. We then pick any community recovery algorithm that is known to succeed until the information-theoretic limit, and run it on Ĥ := G1 ∨π̂ G2; we denote the result of this algorithm by σ̂(Ĥ). We can then write
P(ov(σ̂(Ĥ),σ) ̸= 1) ≤ P({ov(σ̂(Ĥ),σ) ̸= 1} ∩ {Ĥ = H∗}) + P(Ĥ ̸= H∗) ≤ P(ov(σ̂(H∗),σ) ̸= 1) + P(π̂ ̸= π⋆),
where, to obtain the inequality in the second line, we have used that σ̂(Ĥ) = σ̂(H∗) on the event {Ĥ = H∗}, and that Ĥ ̸= H∗ implies π̂ ̸= π∗. Since exact community recovery on H∗ is possible when (3.3) holds [2, 45, 3, 1], we know that P(ov(σ̂(H∗),σ) ̸= 1) → 0 as n → ∞. In light of Theorem 3.1 we also have that P(π̂ ̸= π∗) → 0 when s2(α+ β)/2 > 1, concluding the proof.
By the discussion in Section 2, Theorem 3.3 establishes the existence of a region of the parameter space where (i) there exists an algorithm that can exactly recover the communities using both G1 and G2, but (ii) it is information-theoretically impossible to do so using G1 (or G2) alone. Figures 2, 3, and 4 illustrate phase diagrams of the parameter space, where this region is highlighted in cyan.
To complement the achievability result of Theorem 3.3, our next result provides a condition under which exact community recovery is information-theoretically impossible.
Theorem 3.4. Fix constants α, β > 0 and s ∈ [0, 1]. Let (G1, G2) ∼ CSBM ( n, α lognn , β logn n , s
) and suppose that ∣∣∣√α−√β∣∣∣ < √ 2
1− (1− s)2 . (3.5)
Then for any estimator σ̃ = σ̃(G1, G2), we have that lim n→∞ P(ov(σ̃,σ) = 1) = 0.
The idea behind the proof is a simulation argument. Recall H∗ := G1 ∨π∗ G2 from the proof of Theorem 3.3, and note that H∗ ∼ SBM ( n, α(1− (1− s)2) log(n)/n, β(1− (1− s)2) log(n)/n ) . From H∗ it is possible to simulate (G1, G2), and so if exact community recovery is possible given (G1, G2), then it is also possible given H∗. However, it is known [2, 45, 3, 1] that exact community recovery is not possible from H∗ if (3.5) holds. See Section D in the Supplementary Material for the full proof.
We remark that Theorem 3.4 provides a partial converse to the achievability result in Theorem 3.3: it is tight when s2(α + β)/2 > 1, but the precise information-theoretic threshold is unknown when s2(α+ β)/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 ϵ = ϵ(α, β, s) > 0 such that if (3.3) holds and
s2 ( α+ β
2
) ≥ 1− ϵ, (3.6)
then there is an estimator σ̂ = σ̂(G1, G2) such that lim n→∞ P(ov(σ̂,σ) = 1) = 1.
In words, we believe that the communities can be exactly recovered even in regimes where exact graph matching is information-theoretically impossible. We outline a possible way to prove this conjecture. The algorithm we shall use is the same one used in the proof of Theorem 3.3: we compute π̂, the permutation which maximizes the number of agreeing edges across G1 and G2, and then run an optimal community recovery algorithm on the union graph Ĥ = G1 ∨π̂ G2. Define the correctly-matched region C := {i ∈ [n] : π̂(i) = π∗(i)}. When s2(α + β)/2 < 1, we have that C ̸= [n] with high probability. However, we expect that |C| = (1− o(1))n; that is, π̂ coincides with π∗ on all but a negligible fraction of vertices (which is known as almost exact recovery). This is the case in correlated Erdős-Rényi graphs [18, 61], so we expect it to hold for correlated SBMs as well. Let ĤC be the subgraph of Ĥ restricted to the vertices in C. Since all vertices in C have been correctly matched, we expect that (possibly in an approximate sense)
ĤC ∼ SBM ( |C|, α(1− (1− s)2) log n
n , β(1− (1− s)2) log n n
) . (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 α > β, then the true community label of a given vertex is the same as the true label of most neighbors with high probability (when α < β, the reverse is true) [2], hence the community labels of vertices not in C can be correctly identified using a majority vote.
Making the arguments above formal is a challenging task. For one, though we may expect (3.7) to hold if C is a fixed set, it is in fact a random set depending on G1, G2, and π∗, so formally proving (3.7) requires a careful analysis. Moreover, we would like to use (3.7) to argue that running a community recovery algorithm on Ĥ (rather than ĤC) perfectly recovers the communities in C. Rigorously justifying these points requires significant effort, so we leave it to future work.

heading: 3.3 Multiple correlated stochastic block models
text: We next describe our results on how one can recover communities using K correlated stochastic block models, again using graph matching as a subroutine. Considering more than two networks is more and more important in 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, 34].
Formally, we construct (G1, . . . , GK) ∼ CSBM(n, p, q, s,K) as follows. First, generate a parent graph G ∼ SBM(n, p, q), and let σ denote the community labels. Next, given G, we construct G1 as well as G′2, . . . , G ′ K by independently subsampling G with probability s. Finally, we let π 2 ∗, . . . , π K ∗ be i.i.d. uniformly random permutations of [n], independent of everything else, and for 2 ≤ k ≤ K, we generate Gk by relabeling the vertices of G′k according to π k ∗ .
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 π2∗, . . . , π K ∗ .
Theorem 3.6. Let (G1, . . . , GK) ∼ CSBM ( n, α lognn , β logn n , s,K ) . Suppose that s2 (α+ β) /2 > 1 and
|√α− √ β| >
√ 2
1− (1− s)K . (3.8)
Then there is an estimator σ̂ = σ̂(G1, . . . , GK) such that lim n→∞ P(ov(σ̂,σ) = 1) = 1.
Analogously to Theorem 3.3, Theorem 3.6 establishes the existence of a region of the parameter space where (i) there exists an algorithm that can exactly recover the communities using all of G1, G2, . . . , GK , but (ii) it is information-theoretically impossible to do so using only a strict subset of G1, G2, . . . , GK .
Our next result establishes an impossibility result which is analogous to Theorem 3.4. Theorem 3.7. Let (G1, . . . , GK) ∼ CSBM ( n, α lognn , β logn n , s,K ) and suppose that
|√α− √ β| <
√ 2
1− (1− s)K . (3.9)
Then for any estimator σ̃ = σ̃(G1, G2), we have that lim n→∞ P(ov(σ̃,σ) = 1) = 0.
We highlight a few interesting aspects of Theorems 3.6 and 3.7. As in the two-graph case, Theorem 3.7 provides a partial converse to the achievability result in Theorem 3.6: it is tight in the regime s2(α+ β)/2 > 1, but the correct threshold remains unknown when s2(α+ β)/2 < 1. Additionally, as K increases, the achievability and impossibility conditions in (3.8) and (3.9) converge to the conditions |√α−√β| > √ 2 and |√α−√β| < √ 2, which are the information-theoretic conditions for achievability and impossibility of community recovery in the parent graph G. In words, the more correlated graphs we observe, the less information is lost when generating the observed graphs from the parent graph via the sampling process.

heading: 4 Related work
text: Our work naturally draws upon techniques in the graph matching literature as well as the community recovery literature. Here, we elaborate on relevant work in these fields that were not covered during the exposition of our model and main results.
Graph Matching. Most of the theoretical literature on graph matching has focused on correlated Erdős-Rényi random graphs, which was introduced by Pedarsani and Grossglauser [53]. Significant progress has been made in recent years in characterizing the fundamental information-theoretic limits for recovering the latent vertex correspondence π∗. Cullina and Kiyavash [16, 17] first derived the precise information-theoretic conditions for exact recovery of π∗ for sparse graphs (in a sublineardegree regime), and recently Wu, Xu, and Yu [61] 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-theoretic 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 Erdős-Rényi graphs (see [18, 27, 29, 28, 61] 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 Erdős-Rényi model [50, 19, 35, 54, 58, 62].
A major open question is whether there exist efficient algorithms for inferring π∗ in correlated ErdősRényi graphs. In particular, the estimators which are known to succeed up to the information-theoretic threshold are usually given by the solution to a combinatorial optimization problem, for which a brute force search takes O(n!) time. Significant improvements were recently made by [48, 6], who provided nO(logn) time algorithms for exactly recovering π∗. For values of s close to 1, recent work provides polynomial-time algorithms for exact recovery [23, 25, 40].
Community Recovery in Multi-layer SBMs. We briefly review the literature on 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, a collection of SBMs on the same vertex set 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, 4, 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.

heading: 5 Overview of graph matching proofs
text: Achievability of exact graph matching: Proof sketch of Theorem 3.1. Let Fϵ := {(1− ϵ)n/2 ≤ |V+|, |V−| ≤ (1 + ϵ)n/2} denote the event that the two communities are approximately balanced. Since the community labels are i.i.d. uniform, we have for any fixed ϵ > 0 that P (Fϵ) = 1− o(1) as n → ∞; we may thus condition on Fϵ. Let Sk1,k2 be the set of permutations which mismatches k1 vertices in V+ and k2 vertices in V−. We show that if (3.1) holds, then there exists ϵ = ϵ(α, β, s) sufficiently small so that
P (π̂ ∈ Sk1,k2 | Fϵ) ≤ n−ϵ(k1+k2). (5.1) To bound the probability that π̂ ̸= π∗, we then take a union bound over all the events {π̂ ∈ Sk1,k2} such that k1 + k2 ≥ 1, that is, there is at least one mismatched vertex, concluding the proof. The key technical result which enables the proof is (5.1); this is derived by deriving tight bounds for the generating function corresponding to the number of agreeing edges in G1 and G2 with respect to a given permutation. In prior work on the graph matching problem in correlated Erdős-Rényi graphs, as well as for correlated Gaussian matrices, the aforementioned generating functions could be exactly computed [16, 17, 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 as a function of the number of vertices; see Section C
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 intersection graph between G1 and G′2, that is, (i, j) is an edge in H if and only if (i, j) is an edge in G1 and G′2. Equivalently, (i, j) must be an edge in the parent graph G and must be included in both G1 and G′2. Since the probability of the latter event is s
2, we see that H ∼ SBM ( n, αs2 log(n)/n, βs2 log(n)/n ) . If s2(α + β)/2 < 1, then H is not connected with probability tending to 1 as n → ∞. In particular, H has many singletons in this regime, which are vertices that have non-overlapping neighborhoods in G1 and G′2. 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 π∗ given G1, G2, and σ cannot output π∗ with probability bounded away from zero, so neither can any other estimator.

heading: 6 Discussion and future work
text: 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-theoretic 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-theoretically impossible to do so using a single graph.
Precisely, we determine the sharp information-theoretic 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-theoretic conditions for achievability and impossibility of exact community recovery. We also discuss extensions with K ≥ 2 correlated SBMs. Our work leaves open several important avenues for future work, which we outline below.
• Closing the information-theoretic gaps in exact community recovery. Together, Theorems 3.3 and 3.4 show that in the regime s2(α + β)/2 > 1, we have identified the information-theoretic threshold between impossibility and achievability for exact community recovery. However, we do not have achievability results for the regime s2(α+β)/2 < 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 on 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 a 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 [1]).
• Beyond exact community recovery. Besides exact recovery, natural notions of community recovery include almost exact recovery, where the goal is to recover all but a negligible fraction of community labels, and partial recovery, where the goal is to do better than a 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 [1]), exact graph matching is information-theoretically impossible by Theorem 3.2, hence this cannot be used as a black box. Solving this problem will lead to new methods for community detection based on data from multiple networks.
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.).

Review summaries:
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. The 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.

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.