Harnessing Multiple Correlated Networks for Exact Community Recovery

Authors: miklós z rácz
jifan  zhang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-07 22:39:14

Abstract: We study the problem of learning latent community structure from multiple correlated networks, focusing on edge-correlated stochastic block models with two balanced communities. Recent work of Gaudio, Rácz, and Sridhar (COLT 2022) determined the precise information-theoretic threshold for exact community recovery using two correlated graphs; in particular, this showcased the subtle interplay between community recovery and graph matching. Here we study the natural setting of more than two graphs. The main challenge lies in understanding how to aggregate information across several graphs when none of the pairwise latent vertex correspondences can be exactly recovered. Our main result derives the precise information-theoretic threshold for exact community recovery using any constant number of correlated graphs, answering a question of Gaudio, Rácz, and Sridhar (COLT 2022). In particular, for every $K \geq 3$ we uncover and characterize a region of the parameter space where exact community recovery is possible using $K$ correlated graphs, even though (1) this is information-theoretically impossible using any $K-1$ of them and (2) none of the latent matchings can be exactly recovered.

Main paper: 
 introduction: 
 Finding communities in networks-that is, groups of nodes that are similar-is one of the fundamental problems in machine learning. This task is crucially important for understanding the underlying structure and function of networks across diverse applications, including sociology and biology [23] . The increasing availability of network data sets offers the intriguing possibility of improving community recovery algorithms by synthesizing information across correlated networks. However, in many settings the graphs are not aligned-which may happen for a variety of reasons, including anonymization, missing or erroneous data, or simply the alignment being unknown-which presents a challenge. Thus graph matching-the task of recovering the latent vertex alignment between graphs-plays a central role in efforts to integrate data across networks. Our work follows an exciting recent line of work at the intersection of community recovery and graph matching.Recently, Rácz and Sridhar [41] initiated the study of community recovery in correlated stochastic block models (SBMs), focusing on the simplest setting of two correlated graphs with two balanced communities. They determined the information-theoretic limits for exact graph matching, which has applications for community recovery. In particular, they uncovered a region of the parameter space where exact community recovery is possible using two correlated graphs even though it is information-theoretically impossible to do so using just a single graph. Subsequently, Gaudio, Rácz, and Sridhar [22] determined the information-theoretic limits for exact community recovery from two correlated SBMs. This required going beyond exact graph matching and understanding the subtle interplay between community recovery and graph matching.Gaudio, Rácz, and Sridhar [22] posed the question of understanding what happens in the case of more than two graphs, which arises naturally in all the motivating examples. For instance, people participate in numerous overlapping yet complementary social networks, and only by combining these can we fully understand and make inferences about society. Similarly, synthesizing information across protein-protein interaction networks from several related species can aid in inferring protein functions [44] . The main challenge lies in understanding how to optimally pass information across three or more graphs.Our main contribution fully answers this open question by Gaudio, Rácz, and Sridhar [22] . Specifically, we precisely characterize the information-theoretic threshold for exact community recovery given K correlated SBMs, for any constant K. This result highlights an intricate phase diagram and quantifies the value of each additional correlated graph for the task of community recovery. In particular, for every K ≥ 3 we uncover and characterize a region of the parameter space where exact community recovery is possible using K correlated graphs, even though (1) this is impossible using any K -1 of them and (2) none of the latent matchings can be exactly recovered. See Section 3 and Theorems 1 and 2 for details.Along the way, we also precisely characterize the information-theoretic threshold for exact graph matching given K correlated SBMs, for any constant K. In particular, we uncover and characterize a region of the parameter space where the latent matching between two correlated SBMs cannot be exactly recovered given just the two graphs, but it can be exactly recovered given K > 3 correlated SBMs. See Section 3 and Theorems 3 and 4 for details.To prove our results, we study the so-called k-core matching between all pairs of graphs. Recent works have shown the k-core matching to be a flexible and successful tool in a variety of settings for two correlated graphs [13, 22, 43] . Our main technical contribution is to extend this analysis to more than two graphs. The main difficulty lies in understanding the size of intersections of "bad sets" for k-core matchings for different pairs of graphs. We refer to Section 4 for details. 
models and questions: 
 The stochastic block model (SBM). The SBM is the most common probabilistic generative model for networks with latent community structure. First introduced by Holland, Laskey, and Leinhardt [25] , it has garnered considerable attention and research. In particular, it can be employed as a natural testbed for evaluating and assessing clustering algorithms on average-case networks [1] . The SBM notably displays sharp information-theoretic phase transitions for various inference tasks, offering a detailed understanding of when community information can be extracted from network data. The phase transition thresholds were conjectured by Decelle et al. [15] and were proved rigorously in several papers [33, 34, 35, 36, 2, 3] . We refer to the survey [1] for a detailed overview of the SBM.In this paper, we focus on the simplest setting, a SBM with two symmetric communities. Let n be a positive integer and let p, q ∈ [0, 1] be parameters representing probabilities. We construct a graph G ∼ SBM(n, p, q) as follows. The graph G has n vertices, labeled by [n] := {1, 2, 3, . . . , n}. Each vertex i is assigned a community label σ * (i) from the set {+1, -1}; these are drawn i.i.d. uniformly at random across i ∈ [n]. Let σ * := {σ * (i)} n i=1 denote the community label vector. The vertices are thus categorized into two communities: V + := {i ∈ [n] : σ * (i) = +1} and V -:= {i ∈ [n] : σ * (i) = -1}. Given the community labels σ * , the edges of G are drawn independently between pairs of distinct vertices. If σ * (i) = σ * (j), then the edge (i, j) is in G with probability p; otherwise, it is in G with probability q.Community recovery. In the community recovery task, an algorithm takes as input the graph G (without knowing σ * ) and outputs an estimated community labeling σ. Define the overlap between the estimated labeling and the ground truth as follows:ov(σ * , σ) := 1 n n i=1 σ * (i) σ(i) .The overlap measures how well the true community labels and the estimated labels of the algorithm match. Note that ov(σ * , σ) ∈ [0, 1], where the larger the value is, the better performance the algorithm has. In particular, the algorithm succeeds in exactly recovering the partition into two communities (i.e., σ * = σ or σ * = -σ) if and only if ov(σ * , σ) = 1. Our focus in this paper is achieving this goal, known as exact community recovery. It is well-known that exact community recovery is most challenging and interesting in the logarithmic average degree regime [1] . Accordingly, we focus on this regime: in most of the paper we assume that p = a log n n and q = b log n n for some constants a, b > 0. In this regime there is a sharp informationtheoretic threshold for exact community recovery [2, 35, 3] (2.1) In other words, if D + (a, b) > 1, then exact recovery is possible (and, in fact, efficiently). That is, there is a (polynomial-time) algorithm which outputs an estimator σ with the guarantee that lim n→∞ P(ov(σ * , σ) = 1) = 1. On the other hand, if D + (a, b) < 1 then exact recovery is impossible: for any estimator σ, we have that lim n→∞ P(ov(σ * , σ) = 1) = 0.Correlated SBMs. The objective of our work is to understand how the sharp threshold for exact community recovery varies when the input data involves multiple correlated graphs. To do so, we first define a natural model of multiple correlated SBMs [29, 39, 28] (and see further discussion in Section 6 about alternative models).We construct (G 1 , . . . , G K ) ∼ CSBM(n, p, q, s) as follows, where the additional parameter s ∈ [0, 1] reflects the degree of correlation between the graphs (and the number of graphs K is dropped from the notation for ease of readability). First, generate a parent graph G 0 ∼ SBM(n, p, q) with community labels σ * . Subsequently, given G 0 , construct G ′ 1 , G ′ 2 , . . . , G ′ K by independent subsampling. Specifically, each edge of G 0 is included in G ′ i with probability s, independently of everything else, and non-edges of G 0 remain non-edges in G ′ i . The graphs G ′ i inherit both the vertex labels and the community labels from the parent graph G 0 . Finally, let π * 12 , . . . , π * 1K be i.i.d. uniformly random permutations of [n] and let π * := (π * 12 , . . . , π * 1K ). Define G 1 := G ′ 1 and, for all i ∈ {2, . . . , K}, defineG i := π * 1i (G ′ i ).In other words, for every i > 1 and j ∈[n], vertex j in G ′ i is relabeled to π * 1i (j) in G i .This last relabeling step mirrors the real-world observation that vertex labels are often unaligned across graphs. This construction is shown in Figure 1 .An important property of the model is that marginally each graph G i is an SBM. Since the subsampling probability is s, we have that G i ∼ SBM(n, ps, qs). Thus, it follows from (2.1) that, in the logarithmic average degree regime where p = a log n n and q = b log n n , the communities can be exactly recovered from G 1 alone precisely when sD + (a, b) = D + (sa, sb) > 1.The key question in our work is how to improve the threshold by incorporating more information as K, the number of correlated SBMs, increases. This question was initiated by Rácz and Sridhar [41] and then solved by Gaudio, Rácz, and Sridhar [22] when K = 2.An essential observation is that, to go beyond the threshold, one needs to combine information from the K graphs G 1 , . . . , G K through graph matching. Then one can exactly recover the community labels using the combined information, even in regimes where it is information-theoretically impossible to exactly recover σ * given up to K -1 graphs.To be more specific, if π * were known, then one can reconstruct G ′ j from G j and then combine the graphs G ′ 1 , . . . , G ′ K to obtain the union graph H * , defined as follows: the edge (i, j) is included inT c (a, b) := a + b 2 . (2.2)With this notation, the (pairwise) exact graph matching threshold is given by s 2 T c (a, b) = 1. This directly implies (by a union bound) that ifs 2 T c (a, b) > 1, then π * can be exactly recovered given (G 1 , G 2 , . . . , G K ) ∼ CSBM(n, a log n n , b log n n , s), for any constant K. By the discussion above, this also gives a sufficient condition for exact community recovery given(G 1 , G 2 , . . . , G K ) ∼ CSBM(n, a log n n , b log n n , s): s 2 T c (a, b) > 1 and 1 -(1 -s) K D + (a, b) > 1.(2.3) We will generalize the exact graph matching result of Rácz and Sridhar [41] and show (see Theorem 3 below) that π * can be exactly recovered givenEQUATIONwhich (for K > 2) is weaker than the condition s 2 T c (a, b) > 1 implied by [41] . (Moreover, in Theorem 4 we show that the condition in (2.4) is tight for exact recovery of π * .) Thus, by the discussion above, this gives a sufficient condition for exact community recovery given(G 1 , G 2 , . . . , G K ) ∼ CSBM(n, a log n n , b log n n , s): s 1 -(1 -s) K-1 T c (a, b) > 1 and 1 -(1 -s) K D + (a, b) > 1.(2.5) The interplay between community recovery and graph matching. The condition (2.5) is, however, not tight. To attain the sharp threshold for exact community recovery given K graphs, we need to answer the following question: does there exist a parameter regime where exact community recovery is possible for K graphs, even though (1) exact graph matching is impossible, and (2) exact community recovery is impossible using only K -1 graphs? For K = 2 graphs, Gaudio, Rácz, and Sridhar [22] proved that the sharp threshold for exact community recovery given K correlated SBMs is given byEQUATIONThe condition 1 -(1 -s) 2 D + (a, b) > 1 is necessary due to the work [41] . The first condition in (2.6) demonstrates the interplay between community recovery and graph matching. To be more specific, the first term s 2 T c (a, b) is the threshold for exact graph matching given (G 1 , G 2 ), while the second term s(1 -s)D + (a, b) comes from community recovery.Our main contribution generalizes this result, determining the exact community recovery thresholdfor K ≥ 3 graphs. If 1 -(1 -s) K D + (a, b) > 1,then the sharp threshold is given bys 1 -(1 -s) K-1 T c (a, b) + s(1 -s) K-1 D + (a, b) > 1.(2.7) The condition (2.7) also clearly exhibits the interplay between community recovery and graph matching. The first term comes from graph matching, while the second term comes from community recovery, as in the case of K = 2. We refer to Section 3 and Theorems 1 and 2 for details.Despite the apparent similarity in results, when K ≥ 3 the situation differs significantly from that of two graphs. The primary challenge lies in the existence of multiple methods for matching K ≥ 3 graphs. When K = 2, there is only a single matching that needs to be recovered from G 1 and G 2 . In contrast, with three or more graphs, the graphs can be matched pairwise, or to some anchor graph, or potentially in many other ways. Integrating information across different matchings requires substantial additional effort. We present the formal results in the next section. 
results: 
 Our main contributions are to determine the precise information-theoretic thresholds for exact community recovery and for exact graph matching given K correlated SBMs.We first describe the precise information-theoretic threshold for exact community recovery, starting with the positive direction. Theorem 1 (Exact community recovery from K correlated SBMs). Fix constants a, b > 0 and s ∈ [0, 1], and let (G 1 , G 2 , . . . , G K ) ∼ CSBM(n, a log n n , b log n n , s). Suppose that the following two conditions both hold:1-(1 -s) K D + (a, b) > 1 (3.1) and s 1 -(1 -s) K-1 T c (a, b) + s(1 -s) K-1 D + (a, b) > 1. (3.2)Then exact community recovery is possible. That is, there is an estimatorσ = σ(G 1 , G 2 , . . . , G K ) such that lim n→∞ P (ov ( σ, σ * ) = 1) = 1.Combined with Theorem 2 below (which shows that Theorem 1 is tight), this result precisely answers an open problem of Gaudio, Rácz, and Sridhar [22] . The condition (3.1) is required for exact community recovery for K graphs by [41] . We now focus on the condition (3.2). In the prior work [22] , it is proved that the threshold for exact community recovery for two graphs is given by (2.6). The primary contribution of Theorem 1 is to go beyond this threshold as the number of graphs K increases. In particular, this showcases that there exists a regime where (1) it is impossible to exactly recover σ * from (G 1 , G 2 , . . . , G K-1 ) alone and (2) any exact graph matching is impossible, yet one can perform exact recovery of σ * given (G 1 , G 2 , . . . , G K ). This requires developing novel algorithms that integrate information from (G 1 , G 2 , . . . , G K ) delicately and incorporate multiple graph matchings carefully.Here we first provide a detailed discussion of the algorithms for three graphs (G 1 , G 2 , G 3 ) ∼ CSBM(n, a log n n , b log n n , s), which is the simplest case with intriguing new phenomena and challenges as mentioned. This avoids complicated notations (which arise for general K) for easier understanding. The new techniques used for combining multiple matchings and integrating information with three graphs are subsequently generalized to K > 3 correlated SBMs. The high level idea of the algorithm for exact community recovery when K = 3 consists of five steps (in the following discussion we assume a > b; when a < b, change majority to minority everywhere):1. Obtain an almost exact community labeling of G 1 .2. Obtain three pairwise partial almost exact graph matchings µ 12 , µ 13 , and µ 23 between graph pairs (G 1 , G 2 ), (G 1 , G 3 ), and (G 2 , G 3 ), respectively.3. For vertices in G 1 that are part of at least two matchings, refine the almost exact community labeling in Step 1 via majority vote in the (union) graph consisting of edges that appear at least once in (G 1 , G 2 , G 3 ).For vertices in G 1 that are part of only µ 12 (resp. µ 13 ), label them via majority vote of their neighbors' labels in the graph consisting of edges that appear only in G 1 and not in G 2 (resp. only in G 1 and not in G 3 ).For vertices in G 1 that are not part of any of the three matchings or only part of µ 23 , label them via majority vote of their neighbors' labels in G 1 .Each step in the algorithm involves abundant technical details. See Section 4 for a detailed overview of the algorithms and proofs. Note that the threshold (3.2) captures the interplay between community recovery and graph matching, which we now discuss in more detail.The first term in (3.2), which is s 1 -(1 -s) 2 T c (a, b) for K = 3, comes from graph matching.In [22] it is shown that for one matching, say µ 12 , the best possible almost exact graph matching makes n 1-s 2 Tc(a,b)+o (1) errors. Here, we show that it is possible to obtain almost exact matchings µ 12 and µ 13 (namely, these will be k-core matchings; see Section 4 for details) such that the size of the intersection of the two error sets is n 1-s(1-(1-s) 2 )Tc(a,b)+o (1) , which is a smaller power of n. This quantifies how synthesizing information across graph matchings can reduce errors and this exponent is precisely what shows up in the first term in (3.2). This observation is important and relevant for Steps 4 and 5 in the algorithm.On the other hand, the second term in (3.2), which is s(1 -s) 2 D + (a, b) for K = 3, comes from community recovery. In fact, this term arises from the majority votes in Step 5, where we use only edges in G 1 . Note that the nodes that are unmatched by µ 12 and µ 13 are, roughly speaking, the isolated nodes in the intersection graphs of G 1 and G 2 , and G 1 and G 3 , respectively. Thus, while we use all edges in G 1 in this step, the relevant edges are not present in G 2 nor in G 3 , giving the "effective" factor of s(1 -s) 2 . By (2.1), the exact community recovery threshold forSBM(n, s(1 -s) 2 a log n n , s(1 -s) 2 b log n n ) is s(1 -s) 2 D + (a, b) = 1,giving the second term in (3.2). The following impossibility result shows the tightness of Theorem 1. Theorem 2 (Impossibility of exact community recovery). Fix constants a, b > 0 and s ∈ [0, 1], and let(G 1 , G 2 , . . . , G K ) ∼ CSBM(n, a log n n , b log n n , s). Suppose that either 1 -(1 -s) K D + (a, b) < 1 (3.3) or s 1 -(1 -s) K-1 T c (a, b) + s(1 -s) K-1 D + (a, b) < 1.(3.4) Then exact community recovery is impossible. That is, for any estimator σ = σ(G 1 , G 2 , . . . , G K ), we have that lim n→∞ P (ov ( σ, σ * ) = 1) = 0.Impossibility of exact community recovery given K graphs under the condition (3.3) is proved in [41] . Hence, Theorem 2 focuses on proving impossibility for exact community recovery given K graphs under the condition (3.4) . In particular, condition (3.4) reveals a parameter regime where exact community recovery from (G 1 , G 2 , . . . , G K ) is impossible, yet, if π * were known, then exact community recovery would be possible based on the (correctly matched) union graph.Theorems 1 and 2 combined give the tight threshold for exact community recovery for general K correlated SBMs, see (2.7). Fig. 2 exhibits phase diagrams illustrating the results for three graphs.The techniques that we develop in order to prove Theorems 1 and 2 also allow us to solve the question of exact graph matching, that is, exactly recovering π * = (π * 12 , . . . , π * 1K ) from (G 1 , G 2 , . . . , G K ). In the context of correlated SBMs and community recovery, exact graph matching can be thought of as an intermediate step towards exact community recovery. However, more generally, graph matching is a fundamental inference problem in its own right; see Section 5 for discussion of related work. We start with the positive direction in the following theorem. Theorem 3 (Exact graph matching from K correlated SBMs). Fix constants a, b > 0 and s ∈ [0, 1], and let(G 1 , G 2 , . . . , G K ) ∼ CSBM(n, a log n n , b log n n , s). Suppose that s 1 -(1 -s) K-1 T c (a, b) > 1.(3.5)Then exact graph matching is possible. That is, there exists an estimatorπ = π(G 1 , G 2 , . . . , G K ) = ( π 12 , . . . , π 1K ) such that lim n→∞ P ( π(G 1 , G 2 , . . . , G K ) = π * ) = 1.Since the condition in (3.5) is weaker than s 2 T c (a, b) > 1 (which is the threshold for exact graph matching for K = 2, as shown in [41] ), Theorem 3 implies that there exists a parameter regime where π 12 cannot be exactly recovered from (G 1 , G 2 ), but π can be exactly recovered from (G 1 , G 2 , . . . , G K ). In other words, it is necessary to combine information across all graphs in order to recover π (and even just to recover π 12 ).The estimator π in Theorem 3 is based on pairwise k-core matchings (see Sec. 4 for further details). Roughly speaking, for each pairwise k-core matching the number of unmatched vertices is n 1-s 2 Tc(a,b)+o (1) ; however, we shall show that the number of vertices which cannot be matched through some combination of pairwise k-core matchings is n 1-s(1-(1-s) K-1 )Tc(a,b)+o (1) , which is of smaller order. So, when s 1 -(1 -s) K-1 T c (a, b) > 1, then exact graph matching is possible.The following impossibility result shows the tightness of Theorem 3. ), yet exact community recovery is possible from (G 1 , G 2 ); Pink region: exact community recovery is impossible from (G 1 , G 2 ) (even though it would be possible if π * 12 were known), yet exact community recovery is possible from(G 1 , G 2 , G 3 ); Violet region: exact community recovery is impossible from (G 1 , G 2 , G 3 ) (even though it would be possible from (G 1 , G 2 ) if π * 12were known); Light Green region: exact community recovery is impossible from (G 1 , G 2 ), but exact graph matching of graph pairs is possible, and subsequently exact community recovery is possible from(G 1 , G 2 , G 3 ); Grey region: exact community recovery is impossible from (G 1 , G 2 ), exact graph matching is also impossible from (G 1 , G 2 ), but exact graph matching is possible from (G 1 , G 2 , G 3 ), and subsequently exact community recovery is possible from (G 1 , G 2 , G 3 ); Yellow region: exact community recovery is impossible from (G 1 , G 2 ), exact graph matching is impossible from (G 1 , G 2 , G 3 ), yet exact community recovery is possible from (G 1 , G 2 , G 3 ); Orange region: exact community recovery is impossible from (G 1 , G 2 , G 3 ) (even though it would be possible from (G 1 , G 2 , G 3 ) if π * were known); Red region: exact community recovery is impossible from (G 1 , G 2 , G 3 ) (even if π * is known).The principal finding of this paper is the characterization of the Pink, Violet, Orange, Yellow, Grey, and Light Green regions.Theorem 4 (Impossibility of exact graph matching from K correlated SBMs). Fix constants a, b > 0 and s ∈ [0, 1], and let(G 1 , G 2 , . . . , G K ) ∼ CSBM(n, a log n n , b log n n , s). Suppose that s 1 -(1 -s) K-1 T c (a, b) < 1. (3.6)Then exact graph matching is impossible. That is, for any estimatorπ = π(G 1 , G 2 , . . . , G K ) = ( π 12 , . . . π 1K ) we have that lim n→∞ P ( π(G 1 , G 2 , . . . , G K ) = π * ) = 0.Theorems 3 and 4 combined give the tight threshold for exact graph matching for general K correlated SBMs, see (2.4) . We note that, in independent and concurrent work [5] , Ameen and Hajek derived the threshold for exact graph matching from K correlated Erdős-Rényi random graphs; in other words, they proved Theorems 3 and 4 in the special case of a = b.Comparing Theorems 3 and 4 with Theorems 1 and 2, note that there exists a parameter regime where exact community recovery is possible even though exact graph matching is impossible. 
overview of algorithms and proofs: 
 In this section we elaborate on the technical details of the community recovery algorithm, for which high-level ideas were presented in Section 3. We focus our discussion on the setting of K = 3 graphs, which already captures the main technical challenges; we highlight these and explain how we overcome them. We subsequently explain the generalization from 3 graphs to K graphs. The overview of the impossibility proof is discussed as well.k-core matching. We now define a k-core matching [13, 22, 43] , which is used for almost exact graph matching in Step 2. Given a pair of graphs (G, H) with vertex set [n], for any permutation π, we have the corresponding intersection graph G ∧ π H, where (i, j) is an edge in the intersection graph if and only if (i, j) is an edge in G and (π(i), π(j)) is an edge in H. The k-core estimator explores all possible permutations π of [n] to seek a permutation π that maximizes the size of the k-core of the intersection graph G ∧ π H; recall that the k-core of a graph is the maximal induced subgraph for which all vertices have degree at least k. The output of the k-core estimator is then a partial matching µ, which is the restriction of π to the vertex set of the k-core in G ∧ π H.One significant advantage of using k-core matchings is a certain optimality property in terms of performance. Specifically, if(G 1 , G 2 ) ∼ CSBM(n, a log n n , b log n n , s), then the k-core estimator between G 1 and G 2 fails to match at most n 1-s 2 Tc(a,b)+o (1) vertices, which is the same order as the number of singletons of G 1 ∧ π * 12 G 2 and any graph matching algorithm would fail to match these singletons [11, 41, 22] . Another significant benefit of utilizing k-core matchings is the correctness of the k-core estimator for correlated SBMs, as discussed in [22] . The k-core estimator might not be able to match all vertices under the parameter regime that we are interested in; however, every vertex that it does match is matched correctly with high probability.Community recovery subroutines. The high-level summary of the algorithm is as follows. Since exact community recovery might be impossible in G 1 alone, we first obtain an initial estimate which gives almost exact community recovery in G 1 , as described in Step 1. In Step 2, we use pairwise partial k-core matchings with k = 13 to obtain µ := { µ 12 , µ 13 , µ 23 } (see Fig. 3b ), which we will use to combine information across (G 1 , G 2 , G 3 ) to recover communities. Note that each partial matching µ ij only matches a subset of the vertices, denoted as M ij ; we denote the set of vertices not matched by µ ij by F ij := [n] \ M ij . Subsequently, we split the vertices into two categories: "good" vertices and "bad" vertices, where "good" vertices are part of at least two matchings and "bad" vertices are part of at most one matching (see Fig. 3a ). We conduct several majority votes among "good" and "bad" vertices to do the clean-up after the graph matching phase, where each subroutine is meticulously executed to disentangle the intricate dependencies among (G 1 , G 2 , G 3 ) and µ.Exact community recovery for the "good" vertices. The major distinction between being "good" and being "bad" is that "good" vertices can combine information from all three graphs via their union graph (which is denser), whereas "bad" vertices cannot. Suppose that vertex i is part of µ 12 and µ 13 (i.e., i ∈ M 12 ∩ M 13 ). We can then identify the union graphG 1 ∨ µ12 G 2 ∨ µ13 G 3 , which consists of edges (i, j) such that (i, j) is an edge in G 1 or ( µ 12 (i), µ 12 (j)) is an edge in G 2 or ( µ 13 (i), µ 13 (j)) is an edge in G 3 , and i is part of this union graph. Similarly, if i ∈ M 12 ∩ M 23 , then i is part of the union graph G 1 ∨ µ12 G 2 ∨ µ23• µ12 G 3 thatalso integrates information from all three graphs. On the union graph, we can refine the almost exact community labeling by reclassifying "good" vertices based on a majority vote among the labels of their neighbors that are also "good", and this reclassification will be correct as long as the condition (3.1) holds.There are many underlying technical challenges and roadblocks in the theoretical analysis. The key difficulty arises from the structure of the union graph. It is statistically guaranteed that inG 1 ∨ π * 12 G 2 ∨ π * 13 G 3, all vertices have a community label which is the same as the majority community among their neighbors [35] . However, whether this is also the case for G 1 ∨ µ12 G 2 ∨ µ13 G 3 is unclear, since the latter graph is only defined on the "good" vertices M 12 ∩ M 13 . One would like to demonstrate that the removal of "bad" vertices does not significantly affect the majority community among neighbors of "good" vertices. Prior work [22] addressed a similar problem for two graphs by employing a technique known as Łuczak expansion [27] to F 12 to ensure that the vertices inside the expanded set F 12 are only weakly connected to the vertices outside of the expanded set [n] \ F 12 . Unfortunately, this method is no longer applicable for correlated SBMs with three or more graphs. Even though the size of the expanded set F 12 is orderwise equal to the size of F 12 , the size of the intersection of the expanded sets F 12 ∩ F 13 might not be orderwise equal to the size of F 12 ∩ F 13 , which directly leads to the failure of the algorithm working down to the information-theoretic threshold. To overcome this challenge, we consider the graph G{[n] \ v} to decouple the dependence of v being connected to a vertex w and w being part of the k-core. Applying the Łuczak expansion on such a graph for any given v, and through a union bound, we prove that unmatched vertices are contained in the set of vertices whose degree is smaller than a constant, with high probability. This allows us to quantify the size of F 12 ∩ F 13 and meanwhile directly ensure that "good" vertices within the k-core are only weakly connected with "bad" vertices.Another hurdle needed to overcome, as stated in [22] , concerns the almost exact community recovery in Step 1 which is subsequently used for majority votes. Therefore, it is of great importance to guarantee that the incorrectly-classified vertices are not well-connected and do not have a great impact on majority votes. Consequently, we utilize an algorithm originally developed by Mossel, Neeman, and Sly [35] which allows us to manage the geometry of the misclassified vertices and demonstrate that the vertices classified incorrectly are indeed only weakly connected.Exact community recovery for the "bad" vertices. The remaining step is to label the "bad" vertices. The "bad" vertices can be further classified into three categories (see Fig. 3a ): vertices in F 12 ∩ F 13 , which are only matched by µ 23 or are not matched by any of the three matchings; vertices in F 13 ∩ F 23 \ F 12 , which are only matched by µ 12 ; and vertices in F 12 ∩ F 23 \ F 13 , which are only matched by µ 13 .Consider the vertices in F 12 ∩ F 13 (the other cases are similar). First of all, as discussed above, we show that (1) with high probability. Consider the graph G 1 \ π12 G 2 \ π13 G 3 , which consists of the edges (i, j) in G 1 such that ( π 12 (i), π 12 (j)) and ( π 13 (i), π 13 (j)) are not edges in G 2 and G 3 , respectively. Due to the approximate independence of F 12 ∩ F 13 and G 1 \ π12 G 2 \ π13 G 3 , for a vertex i ∈ F 12 ∩ F 13 we can calculate the probability of the failure of the majority vote in the graph G 1 \ π12 G 2 \ π13 G 3 in a relatively straightforward manner, giving n -s(1-s) 2 D+(a,b)+o (1) . The factor s(1 -s) 2 arises from the fact that the edges in this graph are subsampled in G 1 and are not subsampled in G 2 and G 3 . Now since a vertex in F 12 ∩ F 13 can have at most 12 edges outside of F 12 in G 1 ∧ µ12 G 2 , and also at most 12 edges outside of|F 12 ∩F 13 | = n 1-s(1-(1-s) 2 )Tc(a,b)+oF 13 in G 1 ∧ µ13 G 3 , the majority vote for i ∈ F 12 ∩ F 13 essentially does not change whether it is performed in G 1 or in G 1 \ π12 G 2 \ π13 G 3 .Putting all this together, the probability that the majority vote fails is at most: P(exists a vertex i ∈ F 12 ∩ F 13 such that the majority vote fails) (1) . Thus, if (3.2) with K = 3 holds, then majority vote will correctly classify all vertices in F 12 ∩ F 13 .= |F 12 ∩F 13 |×P(majority vote fails for a vertex) = n 1-s(1-(1-s) 2 )Tc(a,b)-s(1-s) 2 D+(a,b)+oGeneralization to K graphs. For K graphs, we have K 2 pairwise matchings to consider (see Fig. 3b ). We again categorize the vertices as "good" and "bad". The "good" vertices can integrate information across all K graphs through the pairwise partial k-core matchings { µ ij : i, j ∈ [K], i ̸ = j}, while "bad" vertices cannot. To illustrate this concept more vividly, for any vertex v, consider a new "metagraph" MG v on K nodes, defined as follows: there is an edge between i and j in MG v if and only if v can be matched through µ ij (see Fig. 4 ). If the metagraph MG v is connected, then there exists a path that can connect all of its K nodes. Equivalently, there exists a set of matchings that allows us to combine information across all K graphs. Subsequently, we quantify the number of "bad" vertices to be n 1-s(1-(1-s) K-1 )Tc(a,b)+o (1) . The remaining analysis for K graphs can be derived by generalizing the analysis for three graphs.Impossibility proof. As discussed in Section 3, we focus on the proof of (3.4) for impossibility. We compute the maximum a posterior (MAP) estimator for the communities in G 1 . We show that, even with significant additional information provided, including all the correct community labels in G 2 , the true matchings π * ij for i, j ∈ {2, 3, . . . , K}, and most of the true matching π * 12 except for singletons in the graphG 1 ∧ π * 12 (G 2 ∨ . . . ∨ G K ), the MAP estimator fails to exactly recovery communities with probability bounded away from 0 if (3.4) holds. The proof is adapted from the MAP analysis in [22] . The difference is that here we are considering K graphs G 1 , G 2 , . . . , G K with different additional information provided for the MAP estimator. Given that the MAP estimator is ineffective under this regime, all other estimators also fail.Exact graph matching threshold. The proof of the exact graph matching threshold is implicitly present in the proof of the exact community recovery threshold. Essentially, since we show that the number of "bad" vertices is n 1-s(1-(1-s) K-1 )Tc(a,b)+o (1) , the condition (3.5) implies that there are no "bad" vertices with high probability. Since all vertices are "good", and "good" vertices can integrate information across all K graphs, the latent matchings can be recovered exactly. For the impossibility result we analyze the MAP estimator and show that, even with significant additional information, including the true matchings {π * ij : i, j ∈ {2, 3, . . . , K}}, it fails if (3.6) holds. 
related work: 
 Our work generalizes-and solves an open question raised by-the work of Gaudio, Rácz, and Sridhar [22] . Just as [22] , our work lies at the interface of the literatures on community recovery and graph matching1 -two fundamental learning problems-which we briefly summarize here.Community recovery in SBMs. A huge research literature exists on learning latent community structures in networks, and this topic is especially well understood for the SBM [25, 15, 34, 35, 33, 36, 2, 3, 7, 1] . Specifically, we highlight the work of [2, 35] , which identify the precise threshold for exact community recovery for SBMs with two balanced communities. Our algorithm builds upon their analysis, taking particular care about dealing with the dependencies arising from the multiple inexact partial matchings between K correlated graphs.Graph matching: correlated Erdős-Rényi random graphs. The past decade has seen a plethora of research on average-case graph matching, focusing on correlated Erdős-Rényi random graphs [40] .The information-theoretic thresholds for recovering the latent vertex correspondence π * have been established for exact recovery [11, 46, 12] , almost exact recovery [13] , and weak recovery [20, 21, 24, 46, 16] . In parallel, a line of work has focused on algorithmic advances [37, 6, 18, 19, 30, 31, 32] , culminating in recent breakthroughs that developed efficient graph matching algorithms in the constant noise setting [31, 32] . We particularly highlight the work of Cullina, Kiyavash, Mittal, and Poor [13] , who introduced k-core matchings and showed their utility for partial matching of correlated Erdős-Rényi random graphs. Subsequent work has shown the power of k-core matchings as a flexible and successful tool for graph matching [22, 43, 4] . Our work both significantly builds upon these works, as well as further develops this machinery, which may be of independent interest. We also note the independent and concurrent work of Ameen and Hajek which determined the exact graph matching threshold for K correlated Erdős-Rényi random graphs [5] .Graph matching: beyond correlated Erdős-Rényi random graphs. Motivated by real-world networks, a growing line of recent work studies graph matching beyond Erdős-Rényi graphs [8, 26, 9, 39, 42, 49, 41, 22, 45, 43, 17, 48, 47] , including for correlated SBMs [29, 39, 28, 41, 22, 48, 47] .The works that are most relevant to ours are [41, 22] , which have been discussed extensively above.6 Discussion and Future WorkOur main contribution highlights the power of integrative data analysis for community recovery, yet many open questions still remain.Efficient algorithms. Theorem 1 characterizes when exact community recovery is informationtheoretically possible from K correlated SBMs. Is this possible efficiently (i.e., in time polynomial in n)? The bottleneck in the algorithm that we use to prove Theorem 1, which makes it inefficient, is the k-core matching step; the other steps are efficient. Recent breakthrough results have developed efficient graph matching algorithms for correlated Erdős-Rényi random graphs [31, 32] , which promisingly suggest that an efficient algorithm for exact community recovery may indeed exist in this regime. We refer to [22] for further discussion on this point.General block models. We focused here on the simplest case of SBMs with two balanced communities. It would be interesting to extend these results to general block models with multiple communities. This is understood well in the single graph setting [1] and recent work has also characterized the threshold for exact graph matching for two correlated SBMs with k symmetric communities [47] .Alternative constructions of correlated graphs. An exciting research direction is to study different constructions of correlated graph models. For general K, there are many ways that K graphs can be correlated. In particular, the following is a natural alternative construction of multiple correlated SBMs. First, generate G 0 ∼ SBM(n, p, q). Then, independently generateH i ∼ SBM(n, p ′ , q ′ ) for i ∈ [K]. Construct G ′ i := G 0 ∨ H i ,and finally generate G i through an independent random permutation of the vertex indices in G ′ i . This construction is equivalent to the one we studied in this paper for K = 2 and it is different when K ≥ 3, and investigating it is interesting and valuable.The rest of the paper is structured as follows. First, we elaborate on the recovery algorithm for three graphs in Section C. Section D includes some useful preliminary propositions, including some nice properties of almost exact community recovery on G 1 . Section E discusses the k-core estimator. After these preparations, we are ready to prove the main theorems in the paper.Section F proves Theorem 1 for three graphs, where we first validate the accuracy of the community labels for "good" vertices and then classify the remaining "bad" vertices. Section G presents the proof of the impossibility result (Theorem 2) for three graphs. Section H discusses the recovery algorithm for K graphs and provides a general proof for K graphs, with additional arguments on how to identify "good" and "bad" vertices. Section I discusses the proof of the impossibility result (Theorem 2) for K graphs. Section J contains the proof of the threshold for exact graph matching given K graphs, that is, the proofs of Theorems 3 and 4.We introduce here some notation that will be used in the rest of the paper. In most of the paper we focus on the setting of K = 3 graphs:(G 1 , G 2 , G 3 ) ∼ CSBM(n, a log n n , b log n n , s), and this is the setting that we consider here as well.Let V := [n] = {1, 2, 3, ..., n} denote the vertex set of the parent graph G 0 , and letV + := {i ∈ [n] : σ * (i) = +1} and V -:= {i ∈ [n] : σ * (i) = -1} denote the sets of vertices in the two communities. Let [n] 2 := {(i, j) : i, j ∈ [n], i ̸ = j}denote the set of all unordered vertex pairs. Given a community labeling σ ∈ {+1, -1} n , we define the set of intra-community vertex pairs as E + (σ) := {(i, j) ∈ [n] 2 : σ(i) = σ(j)} and the set of inter-community vertex pairs asE + (σ) := {(i, j) ∈ [n] 2 : σ(i) = -σ(j)}. Note that E + (σ) and E -(σ) form a partition of [n]2 . Let A, B, and C denote the adjacency matrices of G 1 , G 2 , and G 3 , respectively. Let B ′ and C ′ denote the adjacency matrices of G ′ 2 and G ′ 3 , respectively. Note that, by construction, we have for all (i, j) ∈ [n] 2 that B ′ i,j = B π * 12 (i),π * 12 (j) and C ′ i,j = C π * 13 (i),π * 13 (j) . Observe that we have the following probabilities for every (i, j) ∈ [n] 2 . If a, b, c ∈ {0, 1} 3 and a + b + c > 0, thenP A ij , B ′ ij , C ′ ij = (a, b, c) = s a+b+c (1 -s) 3-a-b-c p if σ * (i) = σ * (j), s a+b+c (1 -s) 3-a-b-c q if σ * (i) ̸ = σ * (j).Furthermore, we have thatP A ij , B ′ ij , C ′ ij = (0, 0, 0) = 1 -p + (1 -s) 3 p if σ * (i) = σ * (j), 1 -q + (1 -s) 3 q if σ * (i) ̸ = σ * (j).Our recovery algorithm is based on discovering a matching between subsets of two graphs. Definition C.1. Let G i and G j be two graphs in vertex set [n] with adjacency matrix A, B, respectively. The pair(M ij , µ ij ) is a matching between G i and G j if • M ij ∈ [n],•µ ij : M ij → [n],• µ ij is injective.Given a matching (M ij , µ ij ), here are some related notations. Define G i ∨ µij G j to be the union graph, whose vertex set is M , whose vertex index is the same as the vertex index of G i and whose edge set is {{ℓ, m} : ℓ, m ∈ M ij , A ℓm + B µij (ℓ),µij (m) ≥ 1}. In other words, the edges are those that appear in either G i or G j . Conversely, G i ∧ µij G j represents intersection graph, whose vertex set is M ij , whose vertex index is the same as the vertex index of G i and whose edge set is {{ℓ, m} : ℓ, m ∈ M ij , A ℓm = B µij (ℓ),µij (m) = 1}. In other words, the edges are those that appear For three graphs, we can define the additional notations in the same manner as in Definition C.1 and the core concepts remain consistent.G i ∨ µij G j ∨ µ jk •µij G k represents the union graph of G i , G j , G k , whose vertex set is M = M ij ∩ M jk , whose vertex index is the same as the vertex index of G i and whose edge set is {{ℓ, m} : ℓ, m ∈ M, A ℓm + B µij (ℓ),µij (m) + C µ jk •µij (ℓ),µ jk •µij (m) ≥ 1}.In other words, the edge set are the edges that appears in at least one graph out ofG i , G j , G k . Similarly, G i ∧ µij G j ∧ µ jk G k represents the intersection graph, the edge set is {{ℓ, m} : ℓ, m ∈ M ; A ℓm = B µij (ℓ),µij (m) = C µ jk •µij (ℓ),µ jk •µij (m) = 1}. Define G i ∨ µij G j \ µ jk G kbe the graph whose edge set is those edges that appear in either G i or G j and not appear in G k . Similarly, we can defineEQUATIONG i \ µij (G i ∧ µ jk G k ) as well.Note that all the definitions above are defined on vertex set M and use vertex index in G i .Introduce d min (G) := min i∈[n] d(i), where d(i) is the degree of vertex i.Definition C.3. A matching (M ij , µ ij ) is a k-core matching of (G i , G j ) if d min (G i ∧ µij G j ) ≥ k.A matching (M ij , µ ij ) is called a maximal k-core matching if it involves the greatest number of vertices, among all k-core matchings.Algorithm 1 k-core matchingInput: Pair of graphs G i , G j on n vertices, k ∈ [n]. Output: A matching ( M ij , µ ij ) of G i and G j .1: Enumerating all possible matchings, find the maximal k-core matching( M ij , µ ij ) of G i and G j .Let (M ij , µ ij ) be the matching found by Algorithm 1 with k = 13. M ij coincides with the maximal k-core of G i ∧ π * ij G j , denote it as M * ij while µ ij coincides with the true permutation π * ij , with high probability (Lemma E.5).The k-core matching is symmetric, i.e. µ ij (M ij ) = M ji . Note that by Definition C.1, M ij uses the vertex index of G i while M ji uses the vertex index of G j , they are equivalent and exchangeable through the 1-1 mapping. Now define F ij := [n] \ M ij be the set of vertices which are excluded from the matching. Note that F ij use the vertice index same as G i . We define F * ij := [n] \ M * ij be the set of vertices which are outside the maximal k-core of G i ∧ π * ij G j . As briefly discussed in Section 4, we start with leveraging the "good" vertices in order to find the correct communities. The "good" vertices are those which are part of at least two matchings out of three partial matchings µ 12 , µ 13 , µ 23 . The details are shown in Algorithm 2.Input: Three graphs G 1 , G 2 , G 3 on n vertices and three 13-core matchings (M 12 , µ 12 , M 13 , µ 13 , M 23 , µ 23 ), parameters a, b, s, ϵ. Output: A labeling of (M 13 ∩ M 32 ) ∪ (M 12 ∩ M 13 ) ∪ (M 23 ∩ M 12 ) given by σ. 3: For i ∈ M 13 ∩ M 32 , set σ(i) ∈ {-1, 1} according to the neighborhood majority (resp., minority) of σ 1 (i) with respect to the graph(G 1 ∨ µ32•µ13 G 2 ∨ µ13 G 3 ){M 13 ∩ M 32 } if a > b (resp., a < b). 4: For i ∈ M 12 ∩ M 23 , set σ(i) ∈ {-1, 1}according to the neighborhood majority (resp., minority) of σ 1 (i) with respect to the graph(G 1 ∨ µ12 G 2 ∨ µ23•µ12 G 3 ){M 12 ∩ M 23 } if a > b (resp., a < b). 5: For i ∈ M 13 ∩ M 12 , set σ(i) ∈ {-1, 1}according to the neighborhood majority (resp., minority) of σ 1 (i) with respect to the graph(G 1 ∨ µ12 G 2 ∨ µ13 G 3 ){M 13 ∩ M 12 } if a > b (resp., a < b). 6: Return σ : (M 13 ∩ M 32 ) ∪ (M 12 ∩ M 13 ) ∪ (M 23 ∩ M 12 ) → {-1, 1}.The remaining step is to label the "bad" vertices which cannot utilize the combined information from three graphs. Hence, we classify the "bad" vertices according to the majority of neighborhood restricted to the corresponding "good" vertices. The detailed descriptions are shown Algorithm 3.Input: Three graphs (G 1 , G 2 , G 3 ) on n vertices and three 13-core matching (M 12 , µ 12 ), (M 13 , µ 13 ), and (M 23 , µ 23 ), parameters a, b, s, a label on the "good" vertices σ. Output: A labeling of [n] given by σ. The complete exact recovery algorithm is exhibited in Algorithm 4. First, the 13-core matchings are preformed. Next, the "good" vertices are labeled according to the union graph. Finally, the "bad" vertices are labeled according to neighborhood labels inG 1 or G 1 \ µ12 G 2 or G 1 \ µ13 G 3 .Input: Three graphs (G 1 , G 2 , G 3 ) on n vertices, k = 13, and ϵ > 0. Output: A labeling of [n] given by σ.1: Apply Algorithm 1 on input (G i , G j , k), obtaining a matching ( M ij , µ ij ), i ̸ = j ∈ {1, 2, 3}. Denote M := ( M 13 ∩ M 32 ) ∪ ( M 12 ∩ M 13 ) ∪ ( M 23 ∩ M 12 ). 2: Apply Algorithm 2 on input (G 1 , G 2 , G 3 , M 12 , M 23 , M 13 , µ 13 , µ 12 , µ 23 ), obtaining a labeling σ : M → {-1, 1}. 3: Apply Algorithm 3 on input (G 1 , G 2 , G 3 , M 12 , M 23 , M 13 , µ 13 , µ 12 , µ 23 , σ), obtaining a labeling σ : [n] → {-1, 1}. 4: Return σ : [n] → {-1, 1}.Here we provide some useful preliminary propositions. In this section, we elaborate on an alternative method for constructing three correlated SBMs, which emphasizes the independent regions of G 1 , G 2 and G 3 . we detail the construction for three graphs to maintain reasonable and manageable notation throughout our discussion. The extension of these ideas to the general case of K graphs follows a similar structure where the key steps and arguments can be directly applied. This construction is analogous to the construction from [22, Section 3.2], generalizing the case from two graphs to three graphs.Firstly, we construct a random partition {E ijk , i, j, k, ∈ {0, 1}} of [n] 2 . Independently, for each pair {i, j} ∈ [n] 2 , we let {i, j} ∈ {E ijk } with a probability of (1 -s) 3-i-j-k s i+j+k . Subsequently, for each pair {i, j} ∈ [n] 2 , an edge is constructed between i and j with probability p if the two vertices are in the same community, and with probability q if they are in different communities. Graph G 1 is constructed using the edges from ∪ j,k∈{0,1},i=1 E ijk , while the graph G ′ 2 is constructed using edges from ∪ i,k∈{0,1},j=1 E ijk . Graph G 2 is then generated from G ′ 2 and π * 12 by relabeling the vertices of G ′ 2 according to π * 12 . Similarly, the graph G ′ 3 is constructed using edges from ∪ i,j∈{0,1},k=1 E ijk and G 3 is obtained from G ′ 3 and π * 13 by relabeling the vertices of G ′ 3 according to π * 13 . This construction offers an alternative method for generating multiple correlated SBMs and emphasizes regions of independence between the multiple graphs. The following lemma D.2 describes the idea formally. Lemma D.2. The random partition construction of correlated SBMs in Section D.2 is equivalent to the original construction shown in Figure 1 . Moreover, conditioned on π * := (π * 12 , π * 13 , π * 23 ), σ * , and E := {E ijk , i, j, k ∈ {0, 1}}, the graphs that are comprised of edges in disjoint E ijk are mutually independent.Proof. Firstly we show that the distribution of (A i,j , B π * 12 (i),π * 12 (j) , C π * 13 (i),π * 13 (j) ) is the same under two constructions. Then by the indepence of vertex pairs, the equivalence follows. In the first construction, If a + b + c > 0:P((A ij , B π * 12 (i)π * 12 (j) , C π * 13 (i)π * 13 (j) ) = (a, b, c)|π * , σ * ) = s a+b+c (1 -s) 3-a-b-c p if σ * (i) = σ * (j), s a+b+c (1 -s) 3-a-b-c q if σ * (i) ̸ = σ * (j).If a + b + c = 0:P((A ij , B π * 12 (i)π * 12 (j) , C π * 13 (i)π * 13 (j) ) = (0, 0, 0)|π * , σ * ) = 1 -p + (1 -s) 3 p if σ * (i) = σ * (j), 1 -q + (1 -s) 3 q if σ * (i) ̸ = σ * (j).Under the second construction, if σ * (i) = σ * (j):P((A ij , B π * 12 (i)π * 12 (j) , C π * 13 (i)π * 13 (j) ) = (a, b, c)|π * , σ * ) = P({i, j} ∈ E abc ) × p = s a+b+c (1 -s) 3-a-b-c p if a + b + c > 0, 1 -p + (1 -s) 3 p if a + b + c = 0. If σ * (i) ̸ = σ * (j), the joint distribution is the same only with p replaced by q. We can see that the joint distribution under two constructions is the same. To prove the second part of the lemma, note that conditioned on π * , σ * , and the random partition {E ijk , i, j, k ∈ {0, 1}}, the edges in E ijk form independently. Hence the graphs that are comprised of edges in disjoint E ijk are mutually independent.Definition D.3. Define the constant: , b, c ) ∈ {(0, 0, 1), (1, 0, 0), (0, 1, 0)}, (1 -s) 3 (a, b, c) = (0, 0, 0).s abc :=      s 3 (a, b, c) = (1, 1, 1), s 2 (1 -s) (a, b, c) ∈ {(0, 1, 1), (1, 0, 1), (1, 1, 0)}, s(1 -s) 2 (aThe event F holds if and only ifn/2 -n 3/4 ≤ |V + |, |V -| ≤ n/2 + n 3/4 ,and the following conditions hold for all a, b, c ∈ {0, 1}, i ∈ [n]:s abc (|V σ * (i) | -n 3/4 ) ≤ |{j : j ∈ E abc ∩ E + (σ * (i))}| ≤ s abc (|V σ * (i) | + n 3/4 ), s abc (|V -σ * (i) | -n 3/4 ) ≤ |{j : j ∈ E abc ∩ E -(σ * (i))}| ≤ s abc (|V -σ * (i) | + n 3/4 ).Lemma D.4. Define s m := min a,b,c∈{0,1} s abc . We have P(F c ) ≤ 100n exp(-s 2 m √ n 2 ). Proof. Denote G holds if and only if n/2 -n 3/4 ≤ |V + |, |V -| ≤ n/2 + n 3/4. The event G is proved in Lemma 3.8 in [22] .P(G c ) ≤ 4e - √ n .Then, look at the remaining condition of event F.Fix i ∈ [n], condition on σ * 1 , π * 12 , π * 13 . Note that k + abc (i) := |{j : j ∈ E abc ∩ E + (σ * 1 (i))}| ∼ Bin(|V σ * (i) | -1, s abc ). By Hoeffding inequality we haveP(|k + abc (i) -s abc (|V σ * (i) | -1)| ≥ s abc n 3/4 2 |π * 12 , π * 13 , σ * 1 )1(G) ≤ 2 exp(- s 2 abc n 3/2 2|V σ * (i) | )1(G) ≤ 2 exp(-(1 -o(1))s 2 abc √ n).Then by a union bound,P(∃i ∈ [n] : |k + abc (i) -s abc |V σ * (i) || ≥ s abc n 3/4 ) ≤ n i=1 P(|k + abc (i) -s abc (|V σ * (i) | -1)| ≥ s abc n 3/42 )≤ n i=1 E[P(|k + abc (i) -s abc (|V σ * (i) | -1)| ≥ s abc n 3/4 2 |π * 12 , π * 13 , σ * 1 )1(G)] + P(G c ) ≤ 2n exp(-(1 -o(1))s 2 abc √ n) + 4 exp(- √ n) ≤ 6n exp(-(1 -o(1))s 2 m √ n).Similarly, we can define k - abc (i) and through an identical proof we haveP(∃i ∈ [n] : |k - abc (i) -s abc |V -σ * (i) || ≥ s abc n 3/4 ) ≤ 6n exp(-(1 -o(1))s 2 m √ n).The conclusion then follows by a union bound. P(∀i ∈ [n], |N (i) ∩ I ϵ (G)| ≤ 2⌈D + (a, b) -1 ⌉|σ * ) = 1 -o(1).Proof. Proved by [22, Lemma 5.4 ].In this section, we prove two important properties of k-core estimator. Lemma E.4 describes that all vertices have weak connections with those vertices who are not part of the k-core, in the logarithmic regime that we are interested in. Lemma E.1 argues that all the vertices with degree larger than a given constant will be part of the k-core.Lemma E.1. Fix a, b > 0. Consider the graph G ∼ SBM(n, a log n n , b log n n ).For any integer m satisfying m > 2 a+b , all vertices whose degree is greater than m + k are part of the k-core with high probability.Proof. For a given m > 2 a+b , we would like to prove that any vertex v with degree greater than k + m will not be part of the k-core with probability o(n -1 ). The lemma then follows by a union bound.Isolating vertex v for independence. If the vertex v is not part of the k-core of G, it must has more than m neighbors who are / ∈ C k ( G). Note that the event w / ∈ C k ( G) is independent of the event w ∈ N G (v), while the latter event is stochastically dominated by a binomial distribution with probability ν log n/n, ν = max(a, b). Hence, by the tower rule,P(v is not part of k -core in G) ≤ P(|{w ∈ N G (v) : w / ∈ C k ( G)}| > m) ≤ E[1 Bin(|{w:w / ∈C k ( G)}|,ν log n/n)>m ]. (E.2)The size of {w : w / ∈ C k ( G)} can not be directly quantified. Hence, we would like to find a set U based on G such that {w ∈[n] \ v : w / ∈ C k ( G)} ⊂ U, where we can bound the size of U . Now we denote µ = |U |ν log n/n, then we have thatE[1 Bin(|{w:w / ∈C k ( G)}|,ν log n/n)>m ] ≤ E[1 Bin(|U |,ν log n/n)>m ] ≤ E[min t>0 exp(µ(e t -1) -tm)]. (E.3)To construct U , the idea is motivated by Łuczak expansion in [27] . We consider a modified version of expanding the set in our setting.Quantify the set U .Define U to be the set of vertices with degree at most T in the graph G. The choice of T would be specified later. Denote H := {n/2 -n 3/4 ≤ |V + |, |V -| ≤ n/2 + n 3/4 }. By Lemma D.4, P(H c ) = o(1/n). E(|U |) ≤ E(|U |1 H ) + P(H c )n = E(|U |1 H ) + o(1) ≤ n T i=0 i j=0 (1 + o(1) n 2 ) j (1 + o(1) n 2 ) i -j p j (1 -p) (1-o(1)) n 2 -j q i-j (1 -q) (1-o(1)) n 2 -i+j ≤ 2n(1 - a log n n ) (1-o(1)) n 2 (1 - b log n n ) (1-o(1)) n 2 T i=0 i j=0 (1 + o(1))n 2 i ( ν log n n ) i ≤ 2n 1-a+b 2 +o(1) T i=0 (i + 1) (1 + o(1))ν log n 2 i ≤ 2(T + 1) 2 ( ν log n 2 ) T n 1-a+b 2 +o(1) = n 1-a+b 2 +o(1).Consider the situation when 1 -a+b 2 > 0. Now we claim: for any constantW , E[|U | W ] ≤ n W -W a+b 2 +o(1). Suppose for W -1, it is true, then for W :E[|U | W ] = i1,...,i W P(i 1 ∈ U, . . . , i W ∈ U ) = i1̸ =i2...̸ =i W P(i 1 ∈ U, . . . , i W ∈ U ) + i1̸ =i2...̸ =i W -1 P(i 1 ∈ U, . . . , i W -1 ∈ U ) + . . . + i1∈[n] P(i 1 ∈ U ) ≤ i1̸ =i2...̸ =i W P(i 1 ∈ U, . . . , i W ∈ U ) + E(|U | W -1 ) ≤ i1̸ =i2...̸ =i W P(i 1 ∈ U, . . . , i W ∈ U ) + E[|U | W -1 ].The remaining thing is to show that i1̸ =i2...̸ =i W P(i 1 ∈ U, . . . , i W ∈ U ) ≤ n W -W a+b 2 +o(1) . We havei1̸ =i2...̸ =i W P(i 1 ∈ U, . . . , i W ∈ U ) ≤ i1̸ =i2...̸ =i W P(∩ W j=1 {i j has at most T neighbours in [n] \ i 1 , ..., i W , v}) = i1̸ =i2...̸ =i W P({i 1 has at most T neighbours in [n] \ i 1 , ..., i W , v}) W ≤E[|U |] W ≤ n W -W a+b 2 +o(1).The first inequality is because that if i 1 ∈ U in G, then i 1 has at most T neighbours in [n] \ v, then it implies that {i 1 has at most T neighbours in [n] \ i 1 , ..., i W , v}.The second inequality is due to the independence of the events. By induction, the claim follows. By choosing appropriate m ′ -th moment method of |U |, we can select a ϵ such thatP(|U | ≥ n 1-ϵ ) ≤ n -m ′ (a+b)/2+m ′ ϵ+o(1) = o(n -m a+b 2 ). Denote D 0 as |U | ≤ n 1-ϵ , then P(D c 0 ) = o(n -m a+b 2). The possibility of the existence of a well-connected small subgraph. Now we would like to bound the probability of the existence of a well-connected small subgraph. Define the event D := {there exists S ∈ [n] such that |S| < n 1-ϵ and G{S} has at least N |S| edges }.We would like to bound P(D) = o(n -m(a+b)/2 ). Let S be a κ-vertex subset of [n]. Let X S be the indicator variable that is 1 if the subgraph induced by S has at least N |S| edges. Denote ν = max(a, b), then we haveE[ S∈[n],|S|=κ X S ] ≤ S∈[n],|S|=κ κ 2 N κ ( ν log n n ) N κ ≤ S∈[n],|S|=κ ( κeν log n N n ) N κ ≤ n κ ( κeν log n N n ) N κ ≤ (( e 1+1/N ν log n N ) N ( κ n ) N -1 ) κ .The second and the third inequality is because (1) .n k ≤ ( en k ) k . Under the assumption |S| < n 1-ϵ , ( e 1+1/N ν log n N ) N ( κ n ) N -1 < n -ϵ(N -1)+oHence for n sufficiently large we have:E[ S∈[n],|S|<n 1-ϵ X S ] ≤ n 1-ϵ κ=1(n -ϵ(N -1)+o( 1) ) κ ≤ n -ϵ(N -1)+o (1) .Then by Markov's inequality, P(D) ≤ n -ϵ(N -1)+o (1) . If we want to boundP(D) = o(n -m(a+b)/2 ), set N > (a+b)m 2ϵ + 1. Hence, P(D) ≤ E[ S∈[n],|S|<n 1-ϵ X S ] ≤ n -ϵ(N -1)+o(1) < n -m(a+b)/2 .Identify the expansion set of U .Now we do the following expansion on U , the expansion process is adapted from Łuczak expansion first introduced in [27] .1. Define U 0 := U .2. Given U t , define U 1 t+1 to be the set of those vertices outside U t which have at leastN ′ neighbors in U t . If U 1t+1 is non-empty, set U t+1 = U t ∪ {u}, where u is the first vertex in U 1 t+1 . Otherwise, stop the expansion with the set U t .Suppose the expansion ends at the step h, hence we have an increasing sequence {U s } h s=0 . Denote U := U h to be the set after expansion. (1) . Denote e l as the number of edges in G{U ℓ }. Each step in the expanding process, at least N ′ edges are added into the graph, henceD c ∩ D 0 , we can choose N 1 , N ′ > 0, such that |U | ≤ N 1 |U |. Suppose that |U | > N 1 |U |, then there exists ℓ > 0 s.t. |U ℓ | = N 1 |U |. On event D 0 , there exists ϵ > 0, |U | ≤ n 1-ϵ , hence |U ℓ | = N 1 |U | ≤ n 1-ϵ+oe ℓ ≥ N ′ ℓ ≥ N ′ (|U ℓ | -|U |) = (N ′ -N ′ N1 )|U ℓ |. We can choose N ′ , N 1 such that (N ′ -N ′ N1 ) ≥ N . However on the event D c , the set |U ℓ | < n 1-ϵ cannot have at least N |U ℓ | edges, which is a contradiction. Therefore, on the event D c ∩ D 0 , |U | ≤ N 1 |U |. Subsequently, E[|U | m ] ≤ N m 1 E[|U | m 1 D c ∩D0 ] + n m P(D) + n m P(D 0 ) ≤ N m 1 E[|U | m ] + o(n m-m(a+b)/2 ) ≤ n m-m a+b 2 +o(1).Bound the probability of v being in the k-core.Note that G{[n] \ U } has minimum degree at least T -N ′ . If a vertex i ∈ [n] \ U , then i /∈ U , it follows that i has degree at least T in G. However i can have at most N ′ neighbor in U by construction of expansion process, so i must have at leastT -N ′ neighbors in [n] \ U . We can set T = k + N ′ , then If i ∈ [n] \ U , i is part of k-core in G.Since the deg(v) ≥ m + k, it must has at least m neighbors who are not part of k-core in G.Follow the equation (E.2), (E.3), denote µ = |U |ν log n/n, then we haveE[1 Bin(|U |,ν log n/n)>m ] ≤ E[min t>0 exp(µ(e t -1) -tm)] ≤ E[eµ m ] + o(n -1 ) = eν m log n m n m E[|U | m ] + o(n -1 ) ≤ n -(a+b)m/2+o(1) + o(n -1 ) = o(n -1 ).The second inequality follows by setting t = log(1/µ). This is valid since (1) . We can select 0 < c < a+b 2 , W > 0 such thatP(|U | > n 1-c ) ≤ E[|U | W ] n (1-c)W ≤ n -((a+b)/2-c)W +oP(|U | > n 1-c ) = o(n -1 ). On the event |U | ≤ n 1-c , µ = o(1), 1/µ > 1. The third inequality follows by E[|U | m ] ≤ n m-m a+b 2 +o(1)and the last equality is due to m > 2 a+b .If1 -(a + b)/2 ≤ 0, we can directly set m = 1. Similarly, we can prove E[|U |] ≤ n 1-a+b 2 +o(1) , then through a similar calculation, P( v is not part of k-core in G}|) = o(n -1 ).Hence, by a union bound, we can say that all vertices with degree larger than m + k will be part of k-core with high probability.Lemma E.4. Fix a, b, ε > 0. Let G ∼ SBM(n, a log n n , b log n n ).Then, w.h.p., all vertices have at most ε log n neighbors who are not part of the k-core.Proof. For v ∈ [n], consider the graph G := G{[n]\v}. Following the same arguments in Lemma E.1, we can obtain U . We haveP(|{w ∈ N G (v) : w is not part of k-core in G}| > ϵ log n) ≤P(|{w ∈ N G (v) : w / ∈ C k ( G)}| > ϵ log n) ≤P(|{w ∈ N G (v) : w / ∈ C k ( G)}| > m) ≤ o(n -1 ).Based on the proof of Lemma E.1, we can show the lemma follows immediately when n is sufficiently large. Hence, all vertices have at most ϵ log n neighbors who are not part of the kcore with probability 1 -o(1).Lemma E.5. Fix constants a, b > 0, s ∈ [0, 1]. Let (G 1 , G 2 ) ∼ CSBM(n, a log n n , b log n n , s). Let M * be the set of vertices of the 13-core in the graphG 1 ∧ π * G 2 . π * is the permutation of vertices from G 1 to G 2 . Let (M 1 , µ 1 ) be the output of the k-core match of (G 1 , G 2 ), k = 13. Then P((M 1 , µ 1 ) = (M * , π * )) = 1 -o(1). Remark: We can replace (M k , µ k ) by (M * k , π * k {M * }) in any analysis.Proof. Proved by [22, Lemma 4.8] . (1) .Lemma E.6. Let G ∼ SBM(n, a log n n , b log n n ) for fixed a, b > 0. Fix k ≥ 1. With probability 1 -o(1), we have that |F | ≤ n 1-Tc(a,b)+oProof. Proved by [22, Lemma 4.13] . Lemma E.7. Suppose G 1 , G 2 , G 3 are independently subsampled with probability s from a parent graph G ∼ SBM(n, a log n/n, b log n/n) for a, b > 0. Let F * ij be the set of vertices outside the k-core of G i ∧ πij G j (taking vertice index in i) with k = 13. Prove that with probability 1 -o(1), |F * ij ∩ F * jk | ≤ n 1-(2s 2 -s 3 )Tc(a,b)+δ , for any δ > 0. Proof. |F * 12 ∩ F * 23 | = |F * 21 ∩ F * 23 | = |F * 12 ∩ F * 13 |, by symmetricity of G 1 , G 2 , G 3 . Define U ij toE[|U 12 ∩ U 13 |] = n v=1 E[1 v∈U12∩U13 ] = nE[1 v∈U12 1 v∈U13 ]. Let D 1 denote the degree of vertex v in the graph G 1 . Let X a ∼ Bin((1 + o(1))n/2, sa log n/n),and X b ∼ Bin((1 + o(1))n/2, sb log n/n). On the event F, D 1 d = X a + X b , where F is defined in Definition D.3, X a , X b are independent. Note that by Lemma D.4, P(F c ) = o( 1 n 2 ). We haveE[1 v∈U12 1 v∈U13 ] = E[E[1 v∈U12 1 v∈U13 |D 1 ]] = E   m+k i=0 D 1 i s i (1 -s) D1-i 2   = m+k i=0 m+k j=0 C(i, j)E[D i+j 1 (1 -s) 2D1 ]. (E.8)Here C(i, j) is a constant related to i, j. Now look atE[D L 1 (1 -s) 2D1 ].In our regime, L ≤ 2(m + k) are constant. Hence:E[D L 1 (1 -s) 2D1 1 F ] = E[(X a + X b ) L (1 -s) 2Xa (1 -s) 2X b 1 F ] = K t=0 C t E[X t a (1 -s) 2Xa 1 F ]E[X L-t b (1 -s) 2Xa 1 F ]. (E.9)Here C t is constant related to t, the second equality is due to the independence ofX a , X b . Now look at E[X t a (1 -s) 2Xa 1 F ]. E[X t a (1 -s) 2Xa 1 F ] ≤ E[X t a (1 -s) 2Xa ] = (1+o(1))n/2 ℓ=0 ℓ t (1 -s) 2ℓ ( sa log n n ) ℓ (1 - sa log n n ) (1+o(1))n/2-ℓ = (log n) 3 ℓ=0 ℓ t ( (1 -s) 2 sa log n n ) ℓ (1 - sa log n n ) (1+o(1))n/2-ℓ + (1+o(1))n/2 ℓ=(log n) 3 +1 ℓ t ( (1 -s) 2 sa log n n ) ℓ (1 - sa log n n ) (1+o(1))n/2-ℓ .We can bound the first part:(log n) 3 ℓ=0 ℓ t ( (1 -s) 2 sa log n n ) ℓ (1 - sa log n n ) (1+o(1))n/2-ℓ ≤(log n) 3t (log n) 3 ℓ=0 ( (1 -s) 2 sa log n n ) ℓ (1 - sa log n n ) (1+o(1))n/2-ℓ ≤(log n) 3t (1+o(1))n/2-ℓ ℓ=0 ( (1 -s) 2 sa log n n ) ℓ (1 - sa log n n ) (1+o(1))n/2-ℓ =(log n) 3t (1 -(1 -(1 -s) 2 ) sa log n n ) (1+o(1))n/2 ≤ n -(1-(1-s) 2 )sa/2+o(1)Then we can bound the second part, note that (1) ).(1+o(1))n/2 ℓ=(log n) 3 +1 ℓ t ( (1 -s) 2 sa log n n ) ℓ (1 - sa log n n ) (1+o(1))n/2-ℓ = (1+o(1))n/2 ℓ=(log n) 3 +1 ℓ t (1 -s) 2ℓ P(X a = ℓ) ≤ (log n) 3t (1 -s) 2(log n) 3 P(X a > (log n) 3 ) ≤ n 2(log n) 2 log(1-s)+o(1) = o(n -(1-(1-s) 2 )sa/2+oLemma F.5. Suppose that a, b, ϵ 0 satisfy the following conditions:(1 (1 -s) ( σ 1 (j) -σ * (j))| ≤ |N H (i) ∩ I ϵ (G 1 )| ≤ |N G * (i) ∩ I ϵ (G 1 )| ≤ |N G2∨ π * 23 G3\ π * 12 G1 (i) ∩ π * 12 (I ϵ (G 1 ))| + |N G1 (i) ∩ I ϵ (G 1 )| ≤ 2⌈D + (a, b) -1 ⌉ + 2⌈(sD + (a, b)) -1 ⌉ ≤ ϵ log n/2.The first inequality uses Lemma D.5 that the set of errors are contained in I ϵ (G 1 ). The last inequality is due to Lemma D.8, F.4. Notice that maj Using an identical proof, we can argue that the algorithm correctly label all vertices in M 13 ∩ M 32 and M 12 ∩ M 13 .H (i) ≥ ϵ log n for i ∈ [n] \ (F * 12 ∪ F * 23 ). Hence, σ * (i) j∈N H (i) σ 1 (j) ≥ maj H (i) -|σ * (i) j∈N H (i) ( σ 1 (j) -σ * (j))| ≥ ϵ log n/2 >[n] \ {(M 13 ∩ M 32 ) ∪ (M 12 ∩ M 13 ) ∪ (M 23 ∩ M 12 )} Define M = (M 13 ∩ M 32 ) ∪ (M 12 ∩ M 13 ) ∪ (M 23 ∩ M 12 ). Denote F b = (F 12 ∩ F 13 ) ∪ (F 12 ∩ F 23 \ F 13 ) ∪ (F 13 ∩ F 23 \ F 12 ), note that F b = [n] \ M.Lemma F.6. Suppose that a, b, ϵ > 0 satisfy the following conditions:(1 -(1 -s) 3 )D + (a, b) > 1 + 2ϵ| log a/b|, 0 < ϵ ≤ sD + (a, b) 4| log a/b| , s(1 -(1 -s) 2 )T c (a, b) + s(1 -s) 2 D + (a, b) > 1.With high probability, the algorithm correctly labels all vertices that are in F b .Proof. For i ∈ F b , defineH i := (G 1 \ π * 13 G 3 \ π * 12 G 2 ){(M 12 ∩ M 13 ) ∪ {i}}. Let E i be the event that i has a majority of at most ϵ ′ log n in the graph H i . Let σ be the labeling after the step. For bervity, define a "nice" event based on the previous results. Define the event H, which holds if and only if:• F ij = F * ij ; • H i = H i ; • σ(i) = σ * (i) for all i ∈ M 12 ∩ M 13 ;• The event F holds;• |F b | ≤ n 1-(2s 2 -s 3 )Tc(a,b)+δ .By Lemmas E.5, E.7, D.4, F.5, the event H holds with probability 1 -o(1). Furthermore, define E * i := maj Hi (i) ≤ ϵ ′ log n, we have:P(∪ i∈[n] ({i ∈ F b } ∩ E i )) ≤ P((∪ i∈[n] ({i ∈ F * b } ∩ E * i )) ∩ H) + P(H c ) ≤ n i=1 P({i ∈ F * b } ∩ E * i ∩ {F * b ≤ n 1-(2s 2 -3s 3 )Tc(a,b)+δ } ∩ F) + o(1).(F.7)Denote I be the sigma algebra induced by the random variables (j) . By Corollary G.3, the MAP estimator fails. Use the first and second method to analyze i∈R * ∩V + 1D = max(B, C), * 12 , σ * 1 , R * , {E abc : a, b, c ∈ {0, 1}}. Note that R * , R * ∩ V + 1 , R * ∩ V - 1 are I measurable. Now I'd like to show that i∈R * ∩V + 1 W i > 0, i∈R * ∩V - 1 W i > 0 with high probability, then it follows that ∃i ∈ S * ∩ V + 1 , j ∈ S * ∩ V - 1 such that maj(i) < 0 < majW i , i∈R * ∩V - 1 W i : Lemma G.7. Fix δ > 0 and denote θ := 1 -(2s 2 -s 3 )T c (a, b) -s(1 -s) 2 D + (a, b). We have E[ i∈R * ∩V + 1 W i |I]1(F ∩ G δ ) ≥ (1 -n -(2s 2 -s 3 )Tc(a,b)+2δ )n θ-δ-o(1) 1(F ∩ G δ ) and E[ i∈R * ∩V - 1 W i |I]1(F ∩ G δ ) ≥ (1 -n -(2s 2 -s 3 )Tc(a,b)+2δ )n θ-δ-o(1) 1(F ∩ G δ ). Lemma G.8. Fix δ > 0 and denote θ := 1 -(2s 2 -s 3 )T c (a, b) -s(1 -s) 2 D + (a, b) Var( i∈R * ∩V + 1 W i |I)1(F ∩ G δ ) ≤ n 2θ-3δ 1(F ∩ G δ )andVar(i∈R * ∩V - 1 W i |I)1(F ∩ G δ ) ≤ n 2θ-3δ 1(F ∩ G δ ).The proofs of these two lemmas are deferred to Section G.7. Using the lemmas above we can now prove Theorem 5.Proof of Theorem 2 when K = 3. Firstly, show that i∈R * ∩V + 1 W i > 0 with high probability. Use the second moment method, we obtain P(i∈R * ∩V + 1 W i > 0|I) ≥ E[ i∈R * ∩V + 1 W i |I] 2 E[( i∈R * ∩V + 1 W i ) 2 |I] = E[ i∈R * ∩V + 1 W i |I] 2 E[ i∈R * ∩V + 1 W i |I] 2 + Var( i∈R * ∩V + 1 W i |I) ≥ 1 - Var( i∈R * ∩V + 1 W i |I) E[ i∈R * ∩V + 1 W i |I] 2 .Hence for unconditional probability, let δ small enough, δ < min((2s 2 -s 3 )T c (a, b)/8, θ/4), then P(i∈R * ∩V + 1 W i > 0) ≥ P({ i∈R * ∩V + 1 W i > 0} ∩ F ∩ G δ ) = E[P( i∈R * ∩V + 1 W i > 0|I)1(F ∩ G δ )] ≥ E 1 - Var( i∈R * ∩V + 1 W i |I) E[ i∈R * ∩V + 1 W i |I] 2 1(F ∩ G δ ) ≥ (1 -o(1))n 2θ-3δ-2(θ-δ)+o(1) P(F ∩ G δ ) = 1 -o(1).The inequality on the last line is by Lemma G.7, G.8. The equality in the last line is by Lemma G.5, D.4. The proof for P( i∈R * ∩V - 1) is identical. Hence, in light of Corollary G.3, the MAP estimator fails with probability 1 -o(1).1 W i > 0) = 1 -o(P π,ρ := π(i) i ∈ [n] \ S * , π(ρ(i)) i ∈ S * .Lemma G.11. Let ρ be a permutation of S * . Then P π,ρ ∈ A * .Proof. The proof is identical to [22, Lemma 8.11] ]. We only need to change B to B ′ = max(B, C) in the argument.A useful corollary of Lemma G.11 is that the elements of A * can be described by permutation of S. Corollary G.12. We have the following representation A * = {P π *µ -(π) abc := (π(i),π(j))∈E -(σ * 2 ) 1((A i,j , B π(i),π(j) , C π * 23 (π(i)),π * 23 (π(j)) ) = (a, b, c)), a, b, c ∈ {0, 1}, ν + (π) := (π(i),π(j))∈E + (σ * 2 ) A i,j , ν -(π) := (π(i),π(j))∈E -(σ * 2 ) A i,j .With these definitions, we can derive an exact expression for the posterior distribution of π × q 111 q 000 q 011 q 100 µ -(π)111 q 100 q 000 ν -(π)q 000 q 110 q 100 q 010 µ -(π)110 q 000 q 101 q 001 q 100µ -(π)101 . Proof. Note that σ X (i)σ X (j) = 1 if (π(i), π(j)) ∈ E (σ * 2 ), σ X (i)σ X (j) = -1 if (π(i), π(j)) ∈ E -(σ * 2 ). We have ν + (π) -ν -(π) = (i,j)∈( [n] 2 ) σ X (i)σ X (j)A i,j = (i,j)∈{[n]\S * } σ X (i)σ X (j)A i,j + i,j∈S * σ X (i)σ X (j)A i,j + i∈S * ,j∈{[n]\S * } σ X (i)σ X (j)A i,j .We should note that if(i, j) ∈ {[n] \ S * }, then σ X (i)σ X (j)A i,j = σ * 2 (π 12 (i))σ * 2 (π 12 (j))A i,j = σ * 2 (π * 12 (i))σ * 2 (π * 12 (j))A i,j . Denote D 3 := (i,j)∈{[n]\S * } σ X (i)σ X (j)A i,j .ClearlyD 3 depends only on A, σ * 2 , S * , π * 12 {[n] \ S * }. If i, j ∈ S * , A i,j = 0 by Definition G.2. i∈S * ,j∈{[n]\S * } σ X (i)σ X (j)A i,j = i∈S * ,j∈{[n]\S * } σ X (i)σ * 1 (j)A i,j = i∈S * σ X (i) j∈{[n]\S * } σ * 1 (j)A i,j = i∈S * σ X (i)maj(i).The last equality is becauseif i ∈ S * ,maj(i) = j∈[n] A i,j σ * 1 (j) = j∈{[n]\S * } A i,j σ * 1 (j), since A i,j = 0 if i, j ∈ S * . Then the statement follows, ν + (π) -ν -(π) = D 3 + i∈S * σ X (i)maj(i).Lemma G.17. If B(X) is nonempty, thenP((V + 1 , V + 2 ) = (X + , X -)|A, B, C, σ * 2 , π * 23 , S * , π * 12 {[n] \ S * }) = D 4p 100 q 100 p 000 q 000 i∈S * σ X (i)maj (i) ,where D 4 is a constant depending on A, B, C, σ * 2 , π * 23 , S * , π * 12 {[n] \ S * }, but not on X.Proof. We have thatP((V + 1 , V + 2 ) = (X + , X -)|A, B, C, σ * 2 , π * 23 , S * , π * 12 {[n] \ S * }) = π∈B(X) P(π * 12 = π|A, B, C, σ * 2 , π * 23 , S * , π * 12 {[n] \ S * }) = π∈B(X) D 2 p 100 q 000 p 000 q 100 ν + (π)-ν -(π)=D 2 p 100 q 000 p 000 q 100 D3 π∈B(X)p 100 q 000 p 000 q 100 i∈S * σ X (i)maj(i)=D 2 p 100 q 000 p 000 q 100 D3 |B(X)| p 100 q 000 p 000 q 100 i∈S * σ X (i)maj(i)=D 4 p 100 q 000 p 000 q 100 i∈S * σ X (i)maj (i) ,whereD 4 = D 2 p100q000 p000q100 D3 |S * ∩ V + 1 ||S * ∩ V - 1 |. The statement follows.Note thatE[ i∈R * ∩V + 1 W i |I] 2 1(F ∩ G ) = ( i∈R * ∩V + 1 P(i ∈ S * , j∈[n]\ R * A i,j σ * 1 (j) < 0|I)) 2 1(F ∩ G δ ) ≥ (1 -n -(2s 2 -s 3 )Tc(a,b)+2δ ) 2 ( i∈R * ∩V + 1 X i ) 2 1(F ∩ G δ ).Var(i∈R * ∩V + 1 W i |I)1(F ∩ G δ ) =   E[( i∈R * ∩V + 1 W i ) 2 |I] -E[ i∈R * ∩V + 1 W i |I] 2   1(F ∩ G δ ) ≤   i∈R * ∩V + 1 X i + ( i∈R * ∩V + 1 X i ) 2 1 -(1 -n -(2s 2 -s 3 )Tc(a,b)+2δ ) 2   1(F ∩ G δ ) ≤   i∈R * ∩V + 1 X i + 2( i∈R * ∩V + 1 X i ) 2 n -(2s 2 -s 3 )Tc(a,b)+2δ   1(F ∩ G δ ) ≤ |R * ∩ V + 1 |n -s(1-s) 2 D+(a,b)+o(1) + 2 |R * ∩ V + 1 |n -s(1-s) 2 D+(a,b)+o(1) 2 n -(2s 2 -s 3 )Tc(a,b)+2δ 1(F ∩ G δ ) ≤(n θ+δ+o(1) + 2n 2θ+2δ-(2s 2 -s 3 )Tc(a,b)+2δ+o(1) )1(F ∩ G δ ).The second inequality uses the fact that 1 -(1 -n -x ) 2 ≤ 2n -x .W i |I)1(F ∩ G δ ) ≤ n 2θ-3δ 1(F ∩ G δ ).The proof for Var( i∈R * ∩V -1 W i |I)1(F ∩ G δ ) is the same.We start with the definition of categorizing vertices as "good" and "bad" vertices. To begin with, we define a metagraph for each vertex. Then we categorize each vertex as "good" and "bad" according to the connectivity of the metagraph for the vertex.Definition H.1. Given (G 1 , . . . ., G K ) ∼ CSBM(n, a log n n , b log n n , s), and K 2 partial k-core match- ings µ := { µ ij : i ̸ = j ∈ [K]}.For any vertex v, define the following graph matching metagraph for the vertex v, denoted it as MG v . E(MG v ) denotes the edge set in the graph MG v . There are K nodes in MG v , where node i represents the graph G i , and an edge exists between (i, j), that is, (i, j) ∈ E(MG v ) if and only if vertex v can be matched in the partial matching µ ij between G i and G j .Note that MG v is an undirected graph. This is because of an inherent symmetry in the definition of a k-core matching, which looks at the k-core of the intersection graph of the two matched graphs. Thus for k-core matchings, a vertex is matched by µ ij if and only if it is matched by µ ji . This property does not necessarily hold for other graph matching algorithms. Definition H.2. Given (G 1 , . . . , G K ) ∼ CSBM(n, a log n n , b log n n , s), and K 2 partial k-core matchings µ := { µ ij : i ̸ = j ∈ [K]}, we define a vertex v to be "good" if and only if MG v is connected. Conversely, a vertex v is "bad" if and only if MG v is disconnected.Input: K graphs (G 1 , G 2 . . . , G K ) on n vertices, k = 13, and ϵ > 0. Output: A labeling of [n] given by σ.1: Apply [35, Algorithm 1] to the graph G 1 and parameters (sa, sb, ϵ), obtaining a label σ 1 . 2: Apply Algorithm 1 on input (G i , G j , k), obtaining a matching ( M ij , µ ij ), i ̸ = j ∈ {1, 2, .., K}. 3: For "good" vertices v, look at the set Ψ := { µ ij , i, j ∈ [K] : (i, j) ∈ E(MG v )}, by Lemma H.3, we can define the π := ( π 12 , π 13 , . . . , π 1K ) to obtain the union graph of K graphs based on the matchings from Ψ, denote it as(G 1 ∨ G 2 . . . ∨ G K ) Ψ . Denote M := ∩M ij , where (i, j) satisfying µ ij ∈ MG v . Set σ(v) ∈ {-1, 1}according to the neighborhood majority (resp., minority) of σ 1 (v) with respect to the graph(G 1 ∨ G 2 . . . ∨ G K ) Ψ {M } if a > b (resp., a < b). 4: For "bad" vertices v, denote ϕ := {j ∈ [K] : (1, j) ∈ E(MG v )}. Denote M := ∩ i∈[K] M 1i , set σ(v) ∈ {-1, 1}according to the neighborhood majority (resp., minority) of σ(v) with respect to the graphG 1 \ j / ∈ϕ G j (M ∪ {v}) if a > b (resp., a < b). 5: Return σ : [n] → {-1, 1}. Lemma H.4. Suppose that G 1 , G 2 , . . . , G K are independently subsampled with probability s from a parent graph G ∼ SBM(n, a log n/n, b log n/n) for a, b > 0. Let F * ij be the set of vertices outside the k-core of G i ∧ πij G j with k = 13. For 1 ≤ L ≤ K -1 and every δ > 0, with probability 1 -o(1) we have that | ∩ 1≤i≤L,L+1≤j≤K F * ij | ≤ n 1-s(1-(1-s) K-1 )Tc(a,b)+δ .Proof. Define U ij to be the set of vertices with degree at most m + k in G i ∧ πij G j ,* ij ⊂ U ij and | ∩ 1≤i≤L,L+1≤j≤K F * ij | ≤ | ∩ 1≤i≤L,L+1≤j≤K U ij |.Now we look at the expectation: With high probability, the algorithm correctly labels all "bad" vertices.E [| ∩ 1≤i≤L,L+1≤j≤K U ij ] = nEProof. For vertex i that are "bad", denote ψ := {j ∈ [K] : i cannot be matched through µ 1j , j ̸ = 1}. Denote F b as the vertex set of all the "bad" vertices that have the same ψ with vertex i. DenoteM * := ∩ i∈[K] M * 1i . define H i := (G 1 \ π * 12 G 2 \ π * 13 G 3 . . . \ π * 1K G K ){M ∪ {i}}. Let E i be the event that i has a majority of at most ϵ ′ log n in the graph H i . Let σ be the labeling after the step. For brevity, define a "nice" event based on the previous results. Define the event H, which holds if and only if:• F ij = F * ij ;• σ(i) = σ * (i) for all i ∈ M * ;• The event F holds;• |F b | ≤ n 1-s(1-(1-s) K-1 )Tc(a,b)+δ .By Lemma E. ≤ n -s(1-s) K-1 D+(a,b)+ϵ ′ log(a/b)/2+o (1) .Follow (H.12) and take a union bound, we have that ] ≤n 1-s(1-(1-s) K-1 )Tc(a,b)-s(1-s) K-1 D+(a,b)+ϵ ′ log(a/b)/2+δ .• If the authors answer NA or No, they should explain why their work has no societal impact or the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA]Justification: The paper does not involve any data or models that have a high risk for misuse.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes]Justification: Relevant prior work on models (all theoretical) is cited and discussed in detail throughout the paper, following the norms of the research literature. No code or data is used.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.38th Conference on Neural Information Processing Systems (NeurIPS 2024).We note that graph matching has both positive and negative societal impacts. In particular, it is well known that graph matching algorithms can be used to de-anonymize social networks, showing that anonymity is different, in general, from privacy[38]. At the same time, studying fundamental limits can aid in determining precise conditions when anonymity can indeed guarantee privacy, and when additional safeguards are necessary. 
 
 Appendix:  


Decision: The paper studies the problem of exact community recovery in $K$ correlated 2-community stochastic block models (SBMs) where node labels are not maintained between networks. The authors extend previous work for the $K=2$ case, introducing new challenges and proof mechanisms to allow for $K \geq 3$ networks. The main results of the paper are Theorems 1 and 2, which provide necessary and sufficient conditions for exact community recovery, relating to the difficulty of the pairwise matching problem and the individual exact community recovery problem.

All reviewers agree that the paper is well-written, with clear explanations of the problem and the interplay between community recovery and graph matching. The paper successfully answers the open question, generalizing the results to multiple ($K \geq 3$) SBMs. The reviewers appreciate the paper's well-structured presentation. The questions raised by the reviewers are well addressed. 

Overall, this paper is technically sound, well-presented, and provides a solid foundation for future work in this area.

Reviews: review: paper_summary: paper_summary: Theoretical work showing conditions for exact community recovery in $K$ correlated $2$-community SBMs where node labels are not maintained between networks. The work extends previous work for $K=2$ which introduces new challenges and proof mechanisms to allow for $K \ge 3$ networks. Theorems 1 and 2 provide necessary and sufficient conditions for exact community recovery relating to the difficulty of the pairwise matching problem $T_c(a, b)$ and the individual exact community recovery problem $D_+(a,b)$.
strength_weakness: strength_weakness: While reading this paper, I was unsure whether this paper fitted the remit of NeurIPS and would be better suited in another journal rather than conference paper. I felt more comfortable about this upon noticing that [18], which supplied the problem for this work, was itself inspired by work of community recovery in correlated SBMs [37] published in NeurIPS. I recognise this is a personal bias of what I consider a NeurIPS paper.

There is some discussion of how this work relates to real-world networks, but it is unclear how much further research needs to be done before these ideas can be used for practical analysis of real graphs. A number of my questions below relate to applying these ideas to more realistic networks.
questions: questions: How does changing the correlated SBM to allow for different subsampling probabilities $s_i$ for each network affect the theory?

Is it possible to do just exact graph matching better than $s^2 T_c(a,b) > 1$ for $K \ge 3$ graphs? Perhaps this is addresses in some of the referenced papers, but my reading of Lines 128-129 is that exact graph matching is done pairwise for any graphs $G_k$ and $G_l$ which means that all graphs can be paired. Is there any improvement by doing things other than pairwise? I believe the answer reading on later is no, at least asymptotically, but it is uncertain later whether the benefit of extra graphs is solely for graph matching and community detection together, rather than individually. This may be addressed by resolving whether the "if if" typo in Line 128 should be just a single  "if" or, in fact, "if and only if".

While it is useful to consider the extreme case, often there is some evidence of persistent node labelling across networks. For example, Joe Bloggs on Facebook is more likely to correspond to the email joe_bloggs_01@mail.com compared to a completely random node. How could this scenario be incorporated into graph matching and community detection?

Do Steps 3-5 in the algorithm still work if $a < b$? Obviously, there is a symmetry in these two parameters, but as the algorithm is written, in this scenario neighbours are more likely to be the other community rather than the same. Please can you explain the changes necessary to make this approach work when $a < b$?

What subsampling parameter $s$ should we expect in real-world networks? Figure 2 shows two possible values but I have no idea what I would expect as normal. Given networks $G_1, \ldots, G_K$ one could find a maximum likelihood estimator for $s$, perhaps by computing the true $G$ using the graph matching algorithms described here and finding the subsample rate.

Any intuition why the value $k = 13$ in the $k$-core algorithm in Line 244?

How do these ideas relate to subsampling from any arbitrary base graph $G$ rather than just a 2-community SBM? For example, if $G$ was sampled from a generalised random dot product graph (A statistical interpretation of spectral embedding: the generalised random dot product graph, Rubin-Delanchy et al), then the subsampled graphs $G_i$ would also be a GRDPG. The problem of community recovery may not always make sense in that setting, but graph matching is still very important.

An alternative way of subsampling graphs is EdgeFlip used for edge-differential privacy in networks (Sharing social network data: differentially private estimation of exponential-family random graph models, Karwa et al). Edges and non-edges are flipped in $G$ with some probability $p$. How do these techniques work using this method of generating anomalised networks? The results here could show the dangers of producing multiple anomalous versions of the same network, a potentially important result for data privacy.
limitations: limitations: The authors highlight the positive and negative impact of their results, particular for de-anomalising multiple networks.
paper_summary: paper_summary: The paper studies the problem of exact community recovery from multiple ($K$) correlated graphs in 2-community balanced symmetric SBM. Prior work of [Gaudio, Ra\'cz, and Sridhar 2022] for $K=2$ case. The paper generalizes their result for any $K$ (constant) number of graphs. In particular, the main result of the paper determines a sharp information-theoretic threshold in terms of $a,b,s$ (correlated SBM parameters) and $K$ such that 
1. (Theorem 1) Above the threshold, the optimal MAP estimator (not efficient though) achieves exact recovery with high probability. To show this, the main challenge is to combine the information from more than two networks when none of the pairs can be matched exactly.
2. (Theorem 2) Below the threshold, any estimator fails to exactly recover the communities with high probability.

In particular, some interesting highlights from their results are that there is a region of parameter $(a,b,s)$ such that exact recovery is (i) impossible using $K-1$ graphs but possible using $K$ graphs AND (ii) matching the vertex labels of any of the graph pair is impossible.
strength_weakness: strength_weakness: I do not see any major weaknesses in the paper.
questions: questions: What do authors think about the challenges in handling weak recovery in a constant degree regime using correlated graphs? For weak recovery, it would be only good enough to create a partial overlap. 

The rest of the questions are to clarify my understanding of Figure 2.
1. Why pink region is not a finding of this paper (it only mentions violet)? Would it be correct to say that one of the findings is to characterize the boundary between pink and violet region, i.e. how the union of violet and pink splits into the two regions?
2. Is the only difference between the pink and yellow regions that in the former, exact recovery would have been possible if any pair of matchings were known, but in the latter one needs all pairwise matchings? Otherwise, the two regions have the same properties: e.g. no pairwise matching is possible, not possible to recover the community using any individual pairs, yet possible using three graphs. Also, does the region of parameters given by pink+yellow exactly correspond to the region mentioned in abstract lines 12-15 (and as the highlights in the summary of the review).
limitations: limitations: Yes, the authors list out both negative and positive societal impacts of their work and graph matching in general.
paper_summary: paper_summary: Given K correlated SBMs, the authors derive information-theoretic conditions for (i) the exact recovery of the community structure and (ii) the perfect recovery of the planted alignment $\pi^*$.
strength_weakness: strength_weakness: No major weaknesses, the paper opens and closes the problem it intends to solve. The discussion section lays directions for interesting future works. I hesitate between 7 and 8. But for a higher grade, I would have liked to see a bit more (such as graphs with 2 communities of different sizes, or more than 2 communities, which I believe is not that much harder). In any case, the paper is a clear accept.

Minor comments:

* Since the authors consider SBM with two balanced communities and edge probabilities p&q, the term planted partition model may be more adapted.

* In the planted partition model, the key information-theoretic quantity for exact recovery is the Rényi divergence of order 1/2 between two Bernoulli distributions. The CH divergence is only needed for SBM with general connection probabilities and/or block sizes. 

* Typo line 143: "for K \ge graphs", 3 is missing.

* It may be useful to define earlier "almost exact community labeling" and "partial almost exact graph matching" (which I believe are accounted first in lines 179 and 180, and not before, and define only lines 241).
questions: questions: * Can you elaborate on why k-core matching is a good choice? In particular, going over the proof, it appears that k = 13 is used (Lemmas F.4, F.6), is the choice of k important?

* Is there a low-degree hardness conjecture for the alignment of correlated SBMs?

* What happens when $K$ grows unbounded?

* Can one conjecture what happens with k \ge 3 communities of equal size? Going over ref [43], it seems natural to replace the quantity T_c by (a+(k-1)b) / k (which by the way, multiplied by \log n, is the average degree) and replace D_+ by (\sqrt(a) - \sqrt(b) )^2 / k.  

* With k=2 communities of different sizes, could one get a different story than simply replacing the D_+ with the CH divergence? (a naive thinking: the step of almost exact recovery provides 2 communities of sizes n_1 < n_2 for G_1 and of sizes n_1' < n_2' for G_2'; thus I can already map the community of size n_1 with the one of size n_1'. Does it help?).
limitations: limitations: The theoretical results and their assumptions are clearly stated. The work is purely theoretical and does not require more discussion on societal impact.
paper_summary: paper_summary: The paper studies the problem of exact community detection in correlated stochastic block models (with two symmetric communities). More precisely, a graph is sampled from an SBM with parameters p and q and each edge in the graph is then kept with probability q. This downsampling is performed K times independently at random to obtain K different graphs. Each graph is then randomly permuted. From these K correlated sample we want to recover the communities of the model.

The authors provide a necessary and sufficient condition on the parameters p,q,k, and s for exact recovery. 
In particular, they show there exists a regime of p,q,s where K-1 graphs are not enough to recover exactly the communities, but K samples are enough. In particular, there exists a regime in which K samples might not even be enough to solve graph matching perfectly (i.e., recover the random permutation). Therefore, it is necessary to aggregate imperfect matching information with techniques for community detection.

The case for K=2 has been solved by Gaudio, Rácz, and Sridhar. This paper extends their result for any fixed K>=2.
strength_weakness: strength_weakness: Perhaps the main weakness of the paper is that the analysis is not algorithmic, in the sense that there is not an efficient algorithm able to recover the communities. This is, however, more an invitation to future work rather than a flaw of the paper itself.

The other point I'd like to raise is that the proofs in this paper are fairly lengthy and involved. Is NeurIPS the best venue for these kind of papers? I believe the paper will be interesting to the NeurIPS community and that's why I recommend acceptance, but in a perfect world I'd like results of this kind to be also checked for correctness (disclaimer: I did not read the appendix).
questions: questions: Just a few questions that are essentially out of curiosity:
1. Can some of these techniques be used to analyse the sparse case? Of course we wouldn't aim for exact recovery, but rather partial recovery, and we would need to use different algorithms to obtain a good community labelling of the individual graphs.
1. I guess the limit of the recovery probability depends on K and that's the reason K needs to be constant? How bad is its dependency on K? Can K diverge at least slightly?
1. I know this is not the point of this paper, but I wonder if there is a practical application of the techniques developed in the paper. It'd be quite interesting to try and apply them to obtain an algorithm that work in practice, even without theoretical guarantees.
limitations: limitations: Yes.

Comments: comment: Thank you for your responses to my questions, several of which I accept are beyond the scope of this paper (e.q. Q7 and 8), but were of interest to me. I have increased my score of this paper as a result.
Thanks for providing clarifications! I would be happy to see this paper getting accepted.
Thank you for your answers! It answers my questions very well. My overall rating remains unchanged, I recommend acceptance of the paper.
Thanks for your response. I agree that the fact that the threshold depends exponentially on K makes handling the non-constant case not super important, but I appreciated the explanation.