Efficient Graph Matching for Correlated Stochastic Block Models

Authors: shuwen  chai
miklós z rácz
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-07 21:01:37

Abstract: We study learning problems on correlated stochastic block models with two balanced communities. Our main result gives the first efficient algorithm for graph matching in this setting. In the most interesting regime where the average degree is logarithmic in the number of vertices, this algorithm correctly matches all but a vanishing fraction of vertices with high probability, whenever the edge correlation parameter $s$ satisfies $s^2 > \alpha \approx 0.338$, where $\alpha$ is Otter's tree-counting constant. Moreover, we extend this to an efficient algorithm for exact graph matching whenever this is information-theoretically possible, positively resolving an open problem of Rácz and Sridhar (NeurIPS 2021). Our algorithm generalizes the recent breakthrough work of Mao, Wu, Xu, and Yu (STOC 2023), which is based on centered subgraph counts of a large family of trees termed chandeliers. A major technical challenge that we overcome is dealing with the additional estimation errors that are necessarily present due to the fact that, in relevant parameter regimes, the latent community partition cannot be exactly recovered from a single graph. As an application of our results, we give an efficient algorithm for exact community recovery using multiple correlated graphs in parameter regimes where it is information-theoretically impossible to do so using just a single graph.

Main paper: 
 introduction: 
 The proliferation of network data has highlighted the ubiquity and importance of graph matching in machine learning, with applications in a variety of domains, including social networks [52, 57] , computational biology [61] , and computer vision [13, 37] . While the graph matching task-recovering the latent node alignment between two networks-is known to be NP-hard to solve or even approximate in general [39, 53] , in practice it is often possible to solve it well, such as in the works cited above. This has motivated an exciting recent line of work studying average-case graph matching [14, 15, 65, 16, 23, 28, 24, 50, 5, 21, 22, 40, 41, 42, 17, 20, 18] , focusing on correlated Erdős-Rényi random graphs [57] . These papers culminated in recent breakthrough works which developed efficient graph matching algorithms in the constant noise regime [41, 42] .However, real-world networks are not modeled well by Erdős-Rényi random graphs, which in turn has motivated a growing line of recent work studying graph matching beyond Erdős-Rényi [8, 33, 11, 55, 59, 70, 58, 25, 63, 60, 19, 67, 66, 10] . In particular, an important problem in this vein is to study graph matching in correlated stochastic block models (correlated SBMs) [36, 55, 35] (see Section 2 for definitions), since community structure is prevalent in many networks and the community recovery problem is a fundamental inference task that is often a starting point for deeper analyses. Recent work of Rácz and Sridhar [58] determined the fundamental information-theoretic limits for exact graph matching in correlated SBMs; however, the underlying algorithm used to achieve this limit is inefficient (that is, not polynomial time). Rácz and Sridhar [58] posed the open problem of finding an efficient algorithm for (exact) graph matching whenever this is information-theoretically feasible.Our main contribution positively resolves this open problem of Rácz and Sridhar [58] , giving the first efficient algorithm for graph matching for correlated SBMs with two balanced communities, under a condition on the correlation strength that is conjectured to be necessary. Specifically, we give an efficient algorithm that, in the most interesting regime where the average degree is logarithmic in the number of vertices, achieves almost exact recovery of the latent matching, whenever the edge correlation parameter s satisfies s 2 > α ≈ 0.338, where α is Otter's tree-counting constant. Moreover, we extend this to an efficient algorithm for exact graph matching whenever this is information-theoretically possible. See Section 3 and Theorem 1 for details.In addition, our results on graph matching directly imply novel efficient algorithms and results for community recovery. Specifically, combining-in a black-box fashion-our (exact) graph matching algorithm with existing community recovery algorithms, we give an efficient algorithm for exact community recovery using multiple correlated graphs in parameter regimes where it is informationtheoretically impossible to do so using just a single graph. See Section 3 and Theorem 2 for details.Our algorithm generalizes the recent breakthrough work of Mao, Wu, Xu, and Yu [42] , which is based on centered subgraph counts of a large family of trees termed chandeliers, to the setting of correlated SBMs. A major technical challenge that we overcome is dealing with the additional estimation errors that are necessarily present due to the fact that, in relevant parameter regimes, the latent community partition cannot be exactly recovered from a single graph, and thus the edge-indicator variables in the centered subgraph counts cannot be precisely centered. Our technical contributions highlight the interplay between graph matching and community recovery in ways that are complementary to the recent work of Gaudio, Rácz, and Sridhar [25] . 
models and problems: 
 In this section we describe the setting of the paper by introducing the stochastic block model (SBM), correlated SBMs, and the community recovery and graph matching tasks.The stochastic block model (SBM) is the canonical probabilistic generative model for a network with latent community structure. The SBM was first introduced by Holland, Laskey, and Leinhardt [30] and has been widely studied over the past decades [1] . In general, a SBM may consist of a number of communities, with distinct vertices connected randomly with a probability that depends on their community memberships.In this work, we focus on the simplest setting of the balanced two-community SBM. Given n ∈ Z + and p, q ∈ [0, 1], we construct G ∼ SBM(n, p, q) as follows. The graph G has n vertices, with vertex labels given by V = [n] := {1, 2, . . . , n}. Let σ * = {σ * (i)} n i=1 be the vector of community labels, where each entry σ * (i) ∈ {-1, +1} is drawn independently and uniformly at random. Then, given the community labels σ * , for any pair of vertices i ̸ = j ∈ [n], edge (i, j) is in G with probability p1 {σ * (i)=σ * (j)} + q1 {σ * (i)̸ =σ * (j)} . That is, two different vertices are connected with probability p if they are from the same community and connected with probability q otherwise. Correlated SBMs are multiple SBMs where the corresponding edge variables are correlated [36, 55, 35] . Specifically, we construct two correlated SBMs (G 1 , G 2 ) ∼ CSBM(n, p, q, s) using a natural subsampling procedure as follows. Let G ∼ SBM(n, p, q) be a parent graph with community labels σ * . Next, given G, we construct G 1 by random sampling of the edges: each edge of G is included in G 1 with probability s, independently of everything else, and non-edges of G remain non-edges of G 1 . We then do the edge sampling independently again to obtain G ′ 2 in the same way. The child graphs G 1 and G ′ 2 inherit both the vertex labels (given by [n] ) and the community labels σ * from the parent graph G. Finally, let π * be a uniformly random permutation of [n] := {1, 2, . . . , n} and generate G 2 by relabeling the vertices of G ′ 2 according to π * (e.g., vertex i in G ′ 2 is relabeled as π * (i) in G 2 ). This last step reflects the fact that in practice often the correspondence between the two vertex sets is unknown. We denote the adjacency matrices of G 1 and G 2 as A and B, respectively, and note that the community labels of the two graphs are σ A * := σ * and σ B [58] with permission.)equal to ρ + := s 1-p 1-ps , whereas if σ * (i) ̸ = σ * (j), then this correlation coefficient is ρ -:= s 1-q 1-qs . Our focus will be on the sparse setting where p, q = o(1) (as n → ∞), in which case both ρ + and ρ -are asymptotically (1o(1))s, and hence we can regard s as the edge correlation parameter.Community recovery. The goal of community recovery is to recover the latent community labels σ * given some (graph) data, such as a SBM G or correlated SBMs (G 1 , G 2 ). There are various notions of community recovery, depending on how close an estimate is to the ground truth σ * . In this work, we focus on exact community recovery, defined as follows: an estimator σ achieves exact community recovery if lim n→∞ P(| 1 n n i=1 σ(i)σ * (i)| = 1) = 1. The absolute value is present in the previous expression since we can only hope to recover the community labels up to a global sign flip; in other words, our goal is to recover the partition of the graph into two communities. A slightly weaker notion, which also appears throughout our work, is almost exact community recovery, which holds if 1)) = 1; in other words, this notion tolerates a vanishing fraction of errors. Further weaker notions include partial recovery and weak recovery; since these are not the focus here, we refer to [1] for details.lim n→∞ P(| 1 n n i=1 σ(i)σ * (i)| = 1 -o(Different parameter regimes give rise to different challenges and different notions of recovery become most relevant. In the constant average degree regime, that is, when p = a n and q = b n for some constants a and b, it is impossible to recovery the communities exactly. Prior works [47, 49, 44] have characterized the information-theoretic threshold and developed efficient algorithms for partial recovery in this regime. On the other hand, if the vertices have polynomially growing degrees, that is, when p = n -a+o (1) and q = n -b+o (1) for some constants a, b ∈ [0, 1), then community recovery is easy as long as lim inf n→∞ |p n /q n -1| > 0 (see [48] ).In this work, we focus on the "bottleneck regime" of logarithmic average degree, which is the bare minimum for the graph to be connected, and which is when exact community recovery is most interesting. In most of the paper we assume that p = a log n n and q = b log n n for some positive constants a, b. For an SBM with two balanced communities and these parameters, there is a sharp information-theoretic threshold for exact community recovery, which is given by D + (a, b) = 1, where [48, 2, 4, 1] ). This quantity is known as the Chernoff-Hellinger divergence in the general k-community SBM setting with linear size communities [4] and simplifies to the above form in our setting. In other words, when D + (a, b) > 1, there exists an estimator σ that is computable in polynomial-time and which achieves exact community recovery with high probability. On the other hand, when D + (a, b) < 1, exact community recovery is impossible, in the sense that for all estimators σ we have that lim n→∞ P(| 1 n n i=1 σ(i)σ * (i)| = 1) = 0. Moreover, when it is possible to achieve exact community recovery on a single graph, several polynomial-time algorithms have been studied by previous works (e.g., [48, 2] ).D + (a, b) := ( √ a - √ b) 2 /2 (seeCommunity recovery and graph matching. What are the information-theoretic limits for exact community recovery given two correlated SBMs (G 1 , G 2 ) ∼ CSBM(n, a log n n , b log n n , s)? This question was initiated and partially solved by Rácz and Sridhar [58] , and subsequently fully solved by Gaudio, Rácz, and Sridhar [26] . Without yet going into the details, these works highlight the importance of graph matching, that is, the task of recovering the latent matching π * given the two correlated graphs (G 1 , G 2 ). In brief, when π * can be perfectly recovered from (G 1 , G 2 ), then one can take the union graph G 1 ∨ π * G 2 of G 1 and G 2 , which is also an SBM, but with a larger edge density, which makes community recovery easier. This shows that exact community recovery is possible from (G 1 , G 2 ) even in parameter regimes where this is impossible from just a single graph G 1 (see [58] ).Graph matching. Motivated by the above discussion, we now discuss average-case graph matching and notions of recovery. In general, suppose that (G 1 , G 2 ) are two correlated random graphs with n vertices each and that π * is the underlying latent vertex matching. The goal of graph matching is to output an estimator π = π(G 1 , G 2 ) that is close to π * . There are various notions of recovery depending on how close π is to π * ; the two most relevant notions are the following. We say that an estimator π achieves exact graph matching if lim n→∞ P( π = π * ) = 1. We say that an estimator achieves almost exact graph matching if with high probability there exists a subset I ⊆ [n] with |I| = (1o( 1))n such that π| I = π * | I , where π| I denotes the restriction of π to I. In words, almost exact graph matching allows the estimator to make a vanishing fraction of errors.The graph matching problem has been widely studied, with applications to computer vision [13, 37] , computational biology [61] , and social networks [57] . In particular, de-anonymizing social networks is possible with graph matching algorithms, which implies that anonymity is not equivalent to privacy [52] . That said, studying the limits of graph matching algorithms-including potential information-computation gaps, as we shall discuss-can help guide data regulators on when to take more actions with regards to data protection, in addition to anonymity.As discussed in the introductory paragraphs, there has been a large body of recent work on averagecase graph matching, both studying correlated Erdős-Rényi random graphs [57, 14, 15, 65, 16, 23, 28, 24, 50, 5, 21, 22, 40, 41, 42, 17, 20, 18] and more general models of correlated random graphs [8, 33, 11, 55, 59, 70, 58, 25, 63, 60, 19, 67, 66, 10] . In particular, Rácz and Sridhar [58] determined the fundamental information-theoretic limits for exact graph matching in correlated SBMs: in the logarithmic average degree regime discussed above, this threshold is s 2 a+b 2 = 1. However, this result is information-theoretic, and the authors posed the open problem of finding an efficient algorithm for exact graph matching, whenever this is information-theoretically possible.Our main contribution positively resolves this open problem, giving the first efficient algorithm for graph matching for correlated SBMs with two balanced communities. Our algorithm generalizes the recent breakthrough work of Mao, Wu, Xu, and Yu [42] that developed an efficient graph matching algorithm for correlated Erdős-Rényi graphs. As an application, our results imply novel efficient algorithms and results for community recovery. We now turn to describing our results. 
main results: graph matching: 
 Our main theorem for graph matching on correlated SBMs is that there exists a polynomial-time algorithm that can achieve exact matching if s 2 > α, where α is Otter's tree counting constant 1 [56] . (b) (Exact matching) If, in addition, s 2 (a + b)/2 > 1, then there exists a polynomial-time algorithm that ouputs a mapping π such that lim n→∞ P( π = π * ) = 1.Several remarks are now in order about the tightness of the main result, an overview of the chandelier counting algorithm when a = b, and the main challenge of our analysis.Tightness. This result is tight whenever s 2 > α, because s 2 (a+b)/2 = 1 is the information-theoretic threshold of exact graph matching given two correlated SBMs (G 1 , G 2 ) [58] . When s 2 < α, it is conjectured that an information-computation gap exists for the correlated Erdős-Rényi graphs [42] . Specifically, by assuming that a = b, it is information-theoretically possible to match correlated Erdős-Rényi graphs exactly if s 2 a > 1 [14, 15, 65] . However, it is believed hard to find a polynomialtime algorithm to do this. In our model with SBMs, which is an extension from Erdős-Rényi graphs, it is also likely hard to find a polynomial-time algorithm when s 2 < α. ). The red diagonal line depicts a = b, which is an Erdős-Rényi graph. Black regions: exact graph matching is possible and can be done efficiently for each community separately by applying the graph matching algorithm for correlated Erdős-Rényi graphs; Green regions: exact graph matching is possible and can be done efficiently; Light green regions: exact graph matching is impossible, but almost exact graph matching is possible and can be done efficiently; Cyan regions: exact graph matching is possible and can be done efficiently by first recovering the community labels almost exactly; Yellow regions: exact graph matching is impossible but almost exact graph matching can be done efficiently by first recovering the community labels almost exactly.Signed chandelier counts. Our theorem extends from the main theorem in Mao et al. [42] , which proposed a polynomial-time algorithm that matches the correlated Erdős-Rényi graphs exactly. The algorithm has two main steps: First, construct signature vectors s i and t j for vertices i ∈ [n] in G 1 and j ∈ [n] in G 2 by the signed subgraph counts of a specially designed graph class-termed Chandeliers-and calculate the weighted inner product of pairs of signature vectors ⟨s i , t j ⟩ and match vertices if the inner product value is large enough; Second, use a seeded graph matching algorithm to boost the almost exact graph matching algorithm to exact graph matching. It is natural to adapt this algorithm from correlated Erdős-Rényi graphs to correlated SBMs but the details present non-trivial challenges, as we explain below.Main challenge. The main challenge on correlated SBMs is that signed subgraph counts is no longer a free lunch. Signed subgraph counts is counting the subgraphs on a centralized adjacency matrix, which is first proposed by Bubeck et al. [9] and later commonly used to control the variance of counting statistics. The success of the chandelier counting method relies on the sufficient separation of the two inner product distributions of true and false vertex correspondence. We want to find a way that keeps doing the adjacency matrices centralization possible. Recall that we explore the graph matching motivated by community recovery. Interestingly, the solution to this centralization problem is now the other way around-using a rough community label estimate to help the graph matching. Our main technical contributions are first showing that when there are no error occurs in the community label estimate, the signed chandelier counting can be generalized to correlated SBMs and then show that when the exact community recovery is not possible, the errors introduced in the community label estimation, which is polynomial in n, are actually tolerable for the whole algorithm.The analysis falls in two cases. If sD + (a, b) > 1, then we can achieve exact community recovery on each of the graphs by applying the community recovery algorithm from [48] . In addition, if s 2 a 2 > 1, 2 then it suffices to look at each community individually. This is easy and follows in a black-box fashion from [42] (See Section 7). However, on the other side, s 2 a 2 < 1, one still needs to use information the community information. Therefore, we need to go through the whole algorithm analysis again in this case. Note that the analysis would work for both regimes with no constraint on s 2 a 2 < 1. We plot the black-box regime in black and the non-black-box regime in green in Figure 2 . The second case is even trickier. If sD + (a, b) < 1, by the same algorithm, we can only obtain almost exact correct community labels σ A and σ B on graph G 1 and G 2 , respectively. We perform adjacency matrix centralization based on σ A and σ B and show that the error introduced in this step is negligible 2 For a SBM(n, a log n n , b log n n ), each community, conditioned on its size N ≈ n/2, is an Erdős-Rényi graph G(N, a log n n ) ≈ G(N, a log N 2N ).(G 1 , G 2 ) if s 2 ( a+b 2 ) + s(1 -s)D + (a, b) < 1 and possible if s 2 ( a+b 2 ) + s(1 -s)D + (a, b) > 1 [25]. It is unknown whether there exists an efficient algorithm for exact community recovery in this regime.in the sense that the inner-product scores remains sufficiently distinguishable between true pairs (j = π * (i)) and fake pairs (j ̸ = π * (i)). 
application: community recovery: 
 Once matching up the vertices on two correlated graphs, we can combine the information of them onto a union graph and then immediately have an application on community recovery. Our result for community detection is that there exists a polynomial-time algorithm for exact community recovery on correlated SBMs when the squared edge correlation parameter satisfies s 2 > α.Theorem 2. Fix constants a ̸ = b > 0 and s ∈ [0, 1]. Let (G 1 , G 2 ) ∼ CSBM(n, a log n n , b log n n , s). For any ε > 0, if s 2 ≥ α + ε and (1 -(1 -s) 2 )D + (a, b) > 1,then, there exists an estimator σ = σ(G 1 , G 2 ) that can be computed in polynomial-time such thatlim n→∞ P(| 1 n n i=1 σ(i)σ * (i)| = 1) = 1.Theorem 2 is a direct application of our Theorem 1. The proof mainly follows the Theorem 3.3 in [58] , which gives exact community recovery on the union graph of G 1 and G 2 regarding to the permutation π, G 1 ∨ π G 2 . The key difference is that we substitute the maximum a posterior estimator used in the first step with the π(G 1 , G 2 ) output by the algorithm used to prove Theorem 1. Figure 3 is a summary of the phase diagram for community recovery determined by this work along with previous works [58, 25] , focusing on the exact community recovery and efficiency. Remark 1. Consider a more general correlated SBMs with K correlated graphs(G 1 , G 2 , . . . , G K ) ∼ CSBM(n, a log n n , b log n n , s, K).Theorem 1 also implies an efficient algorithm for exact community recovery above the exact graph matching threshold for K correlated SBMs when [58] ).D + (a, b) > 1 1-(1-s) K (Theorem 3.6 in 
algorithm and the overview of the proofs: 
 In this section, we define a few key concepts, give a brief overview of the algorithm, and briefly discuss the proof of Theorem 1 and challenges. See Appendix C for a full version.Chandelier. An (L, M, K, R, D)-chandelier is a rooted tree with L branches, each of which consists of a path with M edges (M -wire), followed by a rooted tree with K edges (K-bulb); the K-bulbs are non-isomorphic to each other, each of them has at most R automorphisms, and the maximum degree is at most D. For each chandelier H, let K(H) denote the set of bulbs of H.For a rooted tree T , let aut(H) denote the number of rooted automorphisms of T throughout this paper. We abbreviate rooted automorphism as automorphism when it is clear that we are applying it to a chandelier. The number of automorphisms of H is determined by the automorphisms of its bulbs.Let T denote the family of non-isomorphic (L, M, K, R, D)-chandelier. The family size of chandelier is |T | = |J | L , where J ≡ J (K, R, D) denotes the collection of unlabeled rooted trees with K edges, at most R automorphisms, and maximum degree D. Otter [56] showed that the number of unlabeled rooted trees with K edges (and no constraint on the automorphisms and vertex degrees) is|J (K, ∞, ∞)| = (α + o(1)) -K, where α ≈ 0.338. We show that under proper choices of R and D, we have|J (K, R, D)| = (α + o(1)) -K in Section C.Algorithm overview. Given (G 1 , G 2 ) ∼ CSBM(n, p, q, s). Our algorithm contains mainly three steps. Firstly, we apply the Algorithm 3 (discussed in Section D.3) by Mossel, Neeman, and Sly [48] to obtain almost exact community label estimates for each single graph. Secondly, we calculate the signed chandelier counting [42] based similarity score to give an almost exact graph matching (Algorithm 1 and Algorithm 4). Lastly, we boost the almost exact matching to exact matching by extending the seeded graph matching algorithm [42] on Erdős-Rényi graphs to SBMs (Algorithm 2).Subgraph counts. For an arbitrary weighted adjacency matrix M of some adjacency matrix A, vertex i ∈ [n], and a rooted graph H, we define the weighted subgraph counts on M asW i,H (M ) := S(i) ∼ =H M S , where M S := e∈E(S) M e ,where S(i) enumerates through all subgraphs on the complete graph K n , rooted at i and are isomorphic to H. When M is the adjacency matrix itself, W i,H (M ) is the usual subgraph count, representing the number of subgraphs rooted at i in M that are isomorphic to H. When M is the centralized adjacency matrix A := A -E[A], we call W i,H (M ) a signed subgraph count following [9] . However, we do not have access to E[A] in many cases. Specifically for SBM, we can estimate E[A] through estimating the community labels. We define the approximately centralized adjacency matrix regarding to community label estimate σ, denoted as A σ , entry-wise asA σ i,j = A i,j -p1 σ[i]= σ[j] -q1 σ[i]̸ = σ[j]. Given a family H of non-isomorphic rooted graphs, we define the subgraph count signature of vertex i as W H i (M ) := (W i,H (M )) H∈H . Similarity score. Given a pair of correlated SBMs (G 1 , G 2 ), we define the similarity score between vertex i on graph G 1 and vertex j on graph G 2 as a weighted inner product between two signatures:Φ ij := ⟨W T i (A), W T j (B)⟩ := H∈T aut(H)W i,H (A)W j,H (B).When we do not have access to A and B, we use the approximately centralized adjacency matrices A σ and B σ . We define the similarity score in a slightly different notation:Φ σ ij := ⟨W T i (A σ A ), W T j (B σ B )⟩ = H∈T aut(H)W i,H (A σ A )W j,H (B σ B ).Almost exact graph matching. The first part in the analysis is to show that by calculating this similarity score, with an appropriate thresholding strategy, we can match up (1o(1))n vertices correctly (Theorem 3). The high-level idea is to show that the similarity score distributions are well-separated between true pairs and fake pairs. We expect the similarity score having the following properties, under event • For true pairs j = π(i) :H := { n 2 -n 3 4 ≤ |V + |, |V -| ≤ n 2 + nEQUATION• For fake pairs j ̸ = π(i) :EQUATION)Precisely forming bounds for these moments constitutes the main bulk of the paper. We provide results from Proposition 1 to Proposition 6. Followed by these moment bounds, we have Theorem 3.Theorem 3. Fix a ̸ = b > 0 and s ∈ [0, 1]. Let p = a log n n , q = b log n nand (G 1 , G 2 ) ∼ CSBM(n, p, q, s). For any ε > 0, suppose s 2 ≥ α + ε. There exists positive constants C 1 , C 2 , C 3 , C 4 , C 5 > 0 such that the following holds. Pick K, M, L, N, D asL = C 1 ε , K = C 2 log n, M = C 3 K log(ns(p ∧ q)) , R = exp(C 4 K), D = C 5 log n (log log n) 2 .(3) Pick an arbitrary c ∈ (0, 1) and set µ = |T |n N ρ N σ 2N eff , where σ 2 eff := (σ 2 + +σ 2 - 2). Then, Algorithm 1 outputs a set I with size (1o(1))n and a mapping π such that π| I = π * | I with high probability.Proof challenge. In regime sD + (a, b) > 1, the probability of existing one vertex being classified incorrectly is vanishing for Algorithm 3. Therefore, with high probability, A σ A = A. If sD + (a, b) < 1, then the recovered σ contains errors (polynomial in n), which will cause some edges being centralized incorrectly and thereby affect the moments calculation.This phenomenon poses a challenge to the algorithm analysis. We highlight some key points in the context of second moment calculation. For simplicity, we ignore event H here. From definition,Var[Φ σ ij ] = H,I∈Taut(H)aut(I)S1(i),S2(j) ∼ =H T1(i),T2(j) ∼ =I E σ * E[A σ A S1 B σ B S2 A σ A T1 B σ B T2 | σ * ] -E σ * E[A σ A S1 B σ B S2 | σ * ] E σ * E[A σ A T1 B σ B T2 | σ * ] .Let us define the union graphU := S 1 ∪ S 2 ∪ T 1 ∪ T 1 3 . If sD + (a, b) > 1, we view A σ and B σ as A and B, respectively. E[A S1 B S2 A T1 A T2 | σ * ] ̸ = 0 only if there exists no edge e ∈ E(U ) such that it occurs only once among (S 1 , S 2 , T 1 , T 2 ). This is because different edges are independent and centralized conditioned on σ * .However, in regime sD+ (a, b) < 1, E[A σ A S1 B σ B S2 A σ A T1 B σ BT2 | σ * ] ̸ = 0 even when edges are not occurring multiple times as we have the expectation of A σ A e can be non-zero when conditioning on σ * and an estimate σ A that disagrees with σ * on the edge type (i.e., for e = (u, v), σ * (u)σ * (v) ̸ = σ A (u) σ A (v)). This not only causes this cross-moments calculation being more complicated, but significantly increasing the possibility of the combinations between S 1 , S 2 , T 1 , and T 2 .The most important high-level idea to properly bound the moments is: the cross-moment conditioning on a specific σ = ( σ A , σ B ) would be non-trivial if and only if all edges occurring only once are centralized incorrectly. Assuming there are z edges occurring once, we show that the probability that σ satisfying this property is no greater than n -z(sD + (a,b)-ε log(a/b)/2) D for any ε > 0, by using the definition of T and Lemma 8 later in Section K and Section L. It turns out that we requiren -z(sD + (a,b)-ε log(a/b)/2) D to be o( 1 log C n )for some positive constant C so that (1) and ( 2) are satisfied. Efficient algorithm. Calculating Φ σ ij exactly (Algorithm 1) takes quasi-polynomial time as searching for all S ∼ = H has time complexity n Θ(N ) . Algorithm 4 in Section F computes an approximated score in polynomial time. Specifically, we follow the color coding-based similarity score approximation from [42] . The basic idea is coloring the stochastic block model using N + 1 colors uniformly at random. Then, we only do signed counts on vertex sets that are colorful with N + 1 distinct colors. We show that this is an unbiased estimator of Φ σ ij and only potentially increase the variance by an additional constant factor in Section F. The result is stated as in Theorem 4. Exact graph matching. The final step of the algorithm is boosting the almost exact matching to a exact matching. The key idea is exploring the number of common neighbors. Define h(x) = x log xx + 1. Denote N π (i, j) as the number of common neighbors of i and j under correspondence π. The idea is that if i and j form a true correspondence, then, with high probability N π (i, j) ≥ γ p 2 +q 2 2 s 2 (n + 2n 4 ), under the nice event H. Therefore, we match up i and j if they have more common neighbors than this threshold. We give the following guarantee. and (G 1 , G 2 ) ∼ CSBM(n, p, q, s). Suppose s 2 ( a+b 2 ) ≥ 1 + ε and s 2 ≥ α + ε, for some ε > 0. Let γ be the unique solution in (1, ∞) to h(γ) = 3 log n (n-2)pqs 2 . Then, the seeded matching Algorithm 2 with input π and an index setI ⊂ [n], |I| = (1 -o(1))n ≥ (1 -ε/16)n such that π| I = π * outputs an exact matching π = π * in O(n 3 (p + q) 2 ) time with probability 1 -o(1).Putting these pieces together implies Theorem 1. From Theorem 4, we know that for (G 1 , G 2 ) ∼ CSBM(n, a log n n , b log n n , s), a ̸ = b, if s 2 ≥ α+ε for some ε > 0 then there we can match (1-o(1))n vertices correctly and efficiently with high probability. Take the returned π from Algorithm 4 as input of Algorithm 2, then Theorem 5 guarantees that the final output π = π * with high probability. 
related work: 
 Graph Matching. Correlated Erdős-Rényi graphs were first studied in [57] for social network deanonymization. The information-theoretic threshold for partial matching was determined by [24, 28] and the information-theoretic threshold for exact graph matching was determined by [14, 15, 65] .Mao et al. [41] proposed the first efficient algorithm that achieves exact graph matching for correlated Erdős-Rényi graphs with average degree (1 + ε) log n ≤ nq ≤ n 1 Θ(log log n) and constant noise. This algorithm only requires a constant edge correlation (sufficiently close to 1) rather than converging to 1, which represents a perfect correlation. Mao et al. [42] followed up with an improved efficient algorithm that achieves exact graph matching for any correlation ρ satisfying ρ 2 > α when nq(q + ρ(1q)) ≥ (1 + ε) log n. It is conjectured that for random graphs of logarithmic average degree, ρ 2 = α is the computational threshold [42] . Muratori and Semerjian [51] added a small constant constraint on the maximum vertex degree of a chandelier to improve the runtime, at the expense of having a slightly larger constant α as the minimum squared correlation requirement.In the denser regime where p = n -a+o (1) , a ∈ (0, 1], Ding and Du [17] established a sharp information-theoretic threshold for matching a positive fraction of vertices. Ding and Li [20] also developed an efficient algorithm for exact graph matching whenever the edge correlation is nonvanishing, which goes beyond the Otter's tree counting constant.Several recent works also go beyond correlated Erdős-Rényi graphs. Wang et al. [64] studied the exact graph matching with additional attribute information on vanishing edge correlation.Closely related to our work, Yang et al. [67] adopted the binary tree counting algorithm [41] to give an efficient graph matching algorithm for correlated SBMs. However, [67] makes several significant assumptions (which we do not). For one, the algorithm in [67] assumes that the community labels are known. This is a strong assumption which may be unrealistic in practice; moreover, this precludes using graph matching as a tool for improved community recovery. In contrast, we do not assume that community labels are known; in fact, a significant part of our technical work is devoted to dealing with the errors arising from estimating the community labels. Moreover, our graph matching algorithm can be directly applied to improve community recovery, as discussed in Theorem 2 and Section 3. In addition, [67] makes strong assumptions on the parameters, assuming that (1) the average degree is at least (log n) 1.1 , (2) the SBM has at least 3 communities, and (3) the correlation parameter satisfies s > 1ε 0 for some unspecified (small) ε 0 . In contrast, our results hold in the most interesting regime of logarithmic average degree and the most natural setting of two balanced communities; moreover, our assumption on s is also weaker.Community recovery with side information Beyond correlated SBMs, there are some other models utilizing side information, from multiple networks [29, 62, 34, 31, 68, 71] , additional covariates [7] , or both [45, 38] . Multi-layer SBM is first mentioned in [30] , which is generated as following: first, generate the community labels for all vertices and fix them for all layers; second, form edges on each layer based on the community labels. Typically, different layers in a multi-layer SBM are conditionally independent given the shared community labels. In addition, several works [45, 38] also encode community membership correlated covariates onto each node. Aside from the multi-layer SBM, Braun and Sugiyama [7] recently studied community detection on a novel variation of SBM whose edges are attached with vectorial covariates. 
discussion and future work: 
 Our main contribution in this paper is to give the first efficient algorithm for exact graph matching for correlated SBMs with two balanced communities, as well as a rigorous proof of its correctness (Theorem 1). We also discuss novel applications to community recovery (Theorem 2). At the same time, our work raises many interesting questions for future research, which we discuss here.Optimal runtime. While our graph matching algorithm is efficient, it would be desirable to understand the optimal running time that can be achieved. Mao, Rudelson, and Tikhomirov [41] gave an efficient algorithm for matching correlated Erdős-Rényi graphs with runtime n 2+o (1) ; the main drawback is that this algorithm requires the correlation parameter to satisfy s > 1ε 0 for some unspecified (small) ε 0 > 0. Nonetheless, it would be interesting to generalize this algorithm to correlated SBMs and the techniques developed in our work may be useful to do so. In very recent (and concurrent) work, Muratori and Semerjian [51] gave faster algorithms for matching correlated Erdős-Rényi graphs by introducing a constraint on the maximum degree of a chandelier, at the expense of strengthening the condition s 2 > α to s 2 > α for some α > α. Exploring the connections between our work and theirs, and generalizing their ideas to correlated SBMs, are of interest.Information-computation gap. An important assumption throughout this work is that the correlation parameter satisfies s 2 > α. We believe that this is inherently necessary and that there is no efficient algorithm (in the logarithmic average degree regime) when s 2 < α. At the same time, exact graph matching is information-theoretically possible whenever s 2 (a + b)/2 > 1, so there is a conjectured information-computation gap. This mirrors the conjecture in [42] for Erdős-Rényi graphs; see also [18] for the low-degree hardness results on the correlation detection and [10] for the very recent low-degree hardness results on testing a pair of correlated stochastic block models against a pair of independent Erdős-Rényi graphs.Efficient exact community recovery when exact graph matching is not possible. Gaudio, Rácz, and Sridhar [25] determined the information-theoretic threshold for exact community recovery on correlated SBMs, in particular showing that there is a regime when this is possible even though (1) this is impossible with a single graph and also (2) exact graph matching is impossible. It remains unknown whether this can be done efficiently in this regime. We believe that this is possible, and our work is an important starting point for this question, yet additional ideas are needed to understand the subtle interplay between graph matching and community recovery in this regime.Sparser and denser regimes. Our work focuses on the most interesting regime where the average degree is logarithmic in n; it is worth understanding other regimes too. In particular, the chandelier counting algorithm by Mao et al. [42] gives almost exact graph matching whenever the average degree diverges. In our Theorem 1 we require that the average degree diverges logarithmically for the corresponding result, so that the error rate for community recovery estimate is polynomially small in n. It would be interesting to overcome this technical barrier and extend the analysis to this sparser regime. Denser regimes are easier to understand. A close inspection of our analysis shows that it also works when the average degree diverges as a (small) polynomial in n; in even denser regimes, the community partition can be recovered exactly and efficiently whenever lim inf n→∞ |p n /q n -1| > 0 (see [48] ) and then the graph matching algorithm in [42] can be applied in a black-box fashion.General block models. We focused here on the simplest case of SBMs with two balanced communities. It is of great interest to develop efficient graph matching algorithms in the general block model with k communities, whenever this is possible. Recently, Yang and Chung [66] determined the information-theoretic threshold for exact graph matching in the k-community symmetric SBM, extending the results of Rácz and Sridhar [58] . We conjecture that substituting the community recovery algorithm used in our work with the degree-profiling algorithm by Abbe and Sandon [4] gives an efficient algorithm for graph matching in this more general setting, assuming again that s 2 > α.The rest of this paper is organized as follows. In Section B, we give some notations used throughout. In Section C, we define the similarity score of a pair of vertices and give the formal proof of Theorem 1 based on Theorem 3 (Almost exact graph matching), Theorem 4 (Efficient algorithm for almost exact graph matching), and Theorem 5 (Exact graph matching by seeded graph matching). In Section D, we talk about some preliminaries: tail bounds, nice events, a tree node assigning sub-problem, an automorphism inequality for trees, and the calculation for cross-moments. These results will be repeatedly used in the following sections. In Section E, Section F, and Section G, we present the proofs for Theorem 3, Theorem 4, and Theorem 5, respectively. Section F and Section G are self-contained, while Section E contains several propositions whose proofs are deferred and which make up the remainder of the paper.In Section E, we introduce six additional Propositions to show that under two different casesnamely, sD + (a, b) ≥ 1 and sD + (a.b) < 1-the mean and variance of the similarity score are properly controlled. Specifically, if sD + (a, b) ≥ 1, then Proposition 1 gives the mean calculation of the similarity score, while Proposition 2 and Proposition 3 are about the variance calculation of the similarity score for true pairs and fake pairs of vertices. If sD + (a, b) < 1, then Proposition 4 gives the mean calculation of the similarity score, while Proposition 5 and Proposition 6 are about the variance calculation of the similarity score for true pairs and fake pairs of vertices. The proofs of Proposition 1, Proposition 2, Proposition 3, Proposition 4, Proposition 5, and Proposition 6 are presented in Section H, Section I, Section J, Section K, Section L, and Section M, respectively.For any graph G = (V, E), we denote E(G) as the edge set and V (G) as the vertex set. We let e(G) := |E(G)| denote the number of edges of graph G and v(G) := |V (G)| denote the number of vertices in graph G. We define the excess of graph G as e(G)v(G), the difference between the number of edges and the number of vertices of G.Consider an arbitrary graph where vertices are equipped with two possible community labels {+1, -1}, we denote V + as the set of vertices with community label +1, V -as the set of vertices with community label -1, N (v) as the set vertices that are neighbors of v.Let π be a permutation on [n], (G 1 , G 2 ) ∼ CSBM(n, p, q, s). Let A (resp. B) be the adjacency matrix of G 1 (resp. G 2 ). Let A := A-E[A] (resp. B) be the centralized adjacency matrix. We further define the approximately centralized adjacency matrix with respect to community label estimate σ as A σ A := A -E A , where E A is an n × n matrix whose (i, j)-th entry is p if σ(i) = σ(j) and q otherwise. 4We denote G 1 ∨ π G 2 as the union graph with respect to π, such that (i, j)∈ E(G 1 ∨ π G 2 ) if and only if (i, j) ∈ E(G 1 ) or (π(i), π(j)) ∈ E(G 2 ). We denote G 1 ∧ π G 2 as the intersection graph with respect to π, such that (i, j) ∈ E(G 1 ∧ π G 2 ) if and only if (i, j) ∈ E(G 1 ) and (π(i), π(j)) ∈ E(G 2 ).We denote the variance of in-community edges σ 2 + := sp(1-sp) and the variance of cross-community edges as σ 2 -:= sq(1sq). Denote the correlation for in-community edges and cross-community edges as ρ + and ρ -, respectively. In addition, we define ρ := ρ++ρ- 2 . Consider the average degree being logarithmic in the number of vertices, then for some constants a, b > 0, p = a log n n , q= b log n n , ρ = (1 + Θ( log n n ))ρ + = (1 + Θ( log n n ))ρ -= (1 + Θ( log n n ))s. 5Throughout the paper, we use standard asymptotic notation O(•), Ω(•), Θ(•), o(•), ω(•). Any limitation is for n → ∞ without special explanations. For real numbers x, y, we define x ∨ y := max{x, y} and x ∧ y := min{x, y}. In this paper, log is natural logarithmic function (with base e). Further notation is introduced in the following section which details the algorithms.A line of works convert the graph matching problem from quadratic assumption to linear assignment by creating a signature vector s i for each vertex i ∈ [n], followed by calculating the similarity scoreEQUATIONj ⟩ of all possible pairs of signatures on two graphs. Recently, Mao et al. [42] proposed a special tree family T , chandelier, that shows a result of efficient graph matching under constant correlation.Definition 1 ((L, M, K, R)-chandelier [42] ). An (L, M, K, R)-chandelier is a rooted tree with L branches, each of which consists of a path with M edges (M -wire), followed by a rooted tree with K edges (K-bulb); the K-bulbs are non-isomorphic to each other and each of them has at most R automorphisms.In this paper, we give an alternative definition of chandelier with five tuple. The first four parameters remain the same as (L, M, K, R)-chandelier. The last parameter D stands for the maximum degree of vertices on this chandelier. We explain the necessity of controlling D in the proof challenge.Definition 2 ((L, M, K, R, D)-chandelier). An (L, M, K, R, D)-chandelier is a rooted tree with L branches, each of which consists of a path with M edges (M -wire), followed by a rooted tree with K edges (K-bulb); the K-bulbs are non-isomorphic to each other, each of them has at most R automorphisms, and the degree of each vertex is at most D.For each chandelier H, let K(H) denote the set of bulbs of H. For a rooted tree T , let aut(H) denote the number of rooted automorphisms of T throughout this paper. We abbreviate rooted automorphism as automorphism when it is clear that we are applying it to a chandelier. The number of automorphisms of H is determined by the automorphisms of its bulbs. Because all bulbs are non-isomorphic to each other,EQUATIONLet T denote the family of non-isomorphic (L, M, K, R, D)-chandelier. The family size of chandelier is |T | = |J | L , where J ≡ J (K, R, D) denotes the collection of unlabeled rooted trees with K edges, at most R automorphisms, and maximum degree D.Otter [56] showed that the number of unlabeled rooted trees with K edges (and no constraint on the automorphisms and vertex degrees) is |J (K, ∞, ∞)| = (α + o(1)) -K , where α ≈ 0.338. We show that under proper choices of R and D, we have |J (K, R, D)| = (α + o(1)) -K through the following two Lemmas. Lemma 1. Let K be the number of vertices on a unlabeled rooted tree,EQUATIONProof. Otter [56] characterized that |J (K,∞,D)| |J (K,∞,∞)| ≍ α -n D α -n, where α D is the radius of convergence for the generating function of the number of unlabeled rooted trees whose maximum vertex degree less than or equal to D. Goh and Schumutz [27] (Theorem 7) showed the following property:as D → ∞, for some constant C > 0, α D = α + Cα D + o(α D ). Immediately we can see that |J (K,∞,D)| |J (K,∞,∞)| = (1 + O(α D )) -K = 1 -o(1) if Kα D → 0. Let C ′ > 1 log(1/α) , choosing D ≥ C ′ log K satisfies Kα D → 0.Lemma 2. Let K be the number of vertices on a unlabeled rooted tree, C be a constant and choose R = exp(CK). For sufficiently large C and K → ∞, Proof. Olsson and Wagner [54] (Theorem 2) showed a central limit theorem result for the number of automorphism on unlabeled rooted trees:EQUATION1 √ K (log aut(H K ) -µK) → N (0, σ 2 ) as K → ∞, where H K is a uniform random unlabeled rooted tree with K edges and µ ≈ 0.137, σ 2 ≈ 0.197. This implies that for some constant C > µ and R = exp(CK), aut(H K ) < R with high probability.Putting together Lemma 1 and Lemma 2, and choosing R and D as specified, we have that|J (K, R, D)| = (1 -o(1))|J (K, ∞, ∞)| = (α + o(1)) -K . Let β denote a universal constant such that |J | ≤ β K . We take β = α -1 .Given (G 1 , G 2 ) ∼ CSBM(n, p, q, s). Our algorithm contains mainly three steps. Firstly, we apply the algorithm by Mossel, Neeman, and Sly [48] to obtain almost exact community label estimates for each single graph. Secondly, we calculate the signed chandelier counting [42] based similarity score to give an almost exact graph matching. Lastly, we boost the almost exact matching to exact matching by extending the seeded graph matching algorithm [42] on Erdős-Rényi graphs to stochastic block models.Almost exact community recovery. Obtaining community label estimates for both graph G 1 and G 2 is the first step of our algorithm. This is necessary for centralizing the adjacency matrices for the signed subgraph counts afterwards. We expect the following properties from the community recovery algorithm:(a) gives almost exact recovery (down to the information-theoretic threshold, which is s 2 (a + b) = 1 in the correlated SBMs with two balanced communities [58] ); (b) gives an error rate for each vertex of inverse-polynomial; (c) gives error rates on different vertices that are approximately independent.The community recovery algorithm in [48] (described as Algorithm 3) has been shown with property (a) by [48] and property (b) by [25] with an error rate of n -sD+ (a,b) . In this paper, we show that property (c) is satisfied (See Lemma 8).Subgraph counts. For an arbitrary weighted adjacency matrix M of some adjacency matrix A, vertex i ∈ [n], and a rooted graph H, we define the weighted subgraph counts on M asEQUATIONwhere S(i) enumerates through all subgraphs on the complete graph K n , rooted at i and are isomorphic to H.When M is the adjacency matrix itself, W i,H (M ) is the usual subgraph count, representing the number of subgraphs rooted at i in M that are isomorphic to H. When M is the centralized adjacency matrix A := A -E[A], we call W i,H (M ) a signed subgraph count following [9] . However, we do not have access to E[A] in many cases. Specifically for SBM, we can estimate E[A] through estimating the community labels. We define the approximately centralized adjacency matrix regarding to community label estimate σ, denoted as A σ , entry-wise asA σ i,j = A i,j -p1 σ[i]= σ[j] -q1 σ[i]̸ = σ[j] .Using A σ in (7) yields the weighted subgraph counts for approximately centralized adjacency matrix.We also refer to this as a signed subgraph count, though errors may exist.Given a family H of non-isomorphic rooted graphs, we define the subgraph count signature of vertex i asEQUATIONSimilarity score. Given a pair of correlated SBMs (G 1 , G 2 ), we define the similarity score between vertex i on graph G 1 and vertex j on graph G 2 as a weighted inner product between two signatures:EQUATIONwhere T is the family of chandelier.When we do not have access to the centralized adjacency matrices A and B, we use community label estimates σ A and σ B for G 1 and G 2 correspondingly. We define the similarity score with a slightly different notation:EQUATION)Almost exact graph matching. The first part in the analysis is to show that by calculating this similarity score, with an appropriate thresholding strategy, we can match up (1o( 1))n vertices correctly (Theorem 3). The high-level idea is to show that the similarity score distributions are well-separated between true pairs and fake pairs. We expect the similarity score having the following properties, under event H:• For true pairs j = π(i) :E[Φ σ iπ * (i) 1 H ] > 0, Var[Φ σ ij 1 H ] = o E[Φ σ iπ * (i) 1 H ] 2 ,• For fake pairs j ̸ = π(i) :E[Φ σ ij 1 H ] = o E[Φ σ iπ * (i) 1 H ] , Var[Φ σ ij 1 H ] = o E[Φ σ iπ * (i) 1 H ] 2 n 2 .Precisely forming bounds for these moments constitutes the main bulk of the paper. Aside from proving the desired properties of the first and second order moments, we follow the color codingbased similarity score estimation idea from [42] to analyze an efficient algorithm. The basic idea is to color the vertices of SBMs using N + 1 colors uniformly at random. Then, we only do signed counts on vertex sets that are colorful with N + 1 colors. We show that this is an unbiased estimator and only potentially increase the variance by an additional constant factor in Section F. The result is stated formally as in Theorem 4. 1: Run community recovery Algorithm 3 [48] on A and B separately and get label vector σ A , σ B . 2: For each pair of vertex i in A σ A and vertex j in B σ B , compute their similarity score as in [42] :Input: Adjacency matrices A and B for (G 1 , G 2 ) ∼ CSBM(n, a log n n , b log n n ,EQUATION) 3: Let τ = cµ, output I := {i|i ∈ [n], ∃j ∈ [n], s.t. Φ T ij ≥ τ, and ∀k ∈ [n] \ {j}, Φ T ik < τ }.Proof challenge. In regime sD + (a, b) > 1, the probability of existing one vertex being classified incorrectly is vanishing. Therefore, with high probability,A σ A = A. If sD + (a, b) < 1, thenthe recovered σ contains errors (polynomial in n), which will cause some edges being centralized incorrectly and thereby affect the moments calculation. For example, let i, j ∈ [n] be two vertices on G 1 who has the same community label σ * (i) = σ * (j). If only one of i, j is labeled incorrectly by Algorithm 3, then the expectation of A σ A i,j conditioned on σ * and σ is pq. This phenomenon poses a challenge to the algorithm analysis. We highlight some key points in the context of second moment calculation. For simplicity, we ignore event H here.Var[Φ σ ij ] = H,I∈Taut(H)aut(I)S1(i),S2(j) ∼ =H T1(i),T2(j) ∼ =I E σ * E[A σ A S1 B σ B S2 A σ A T1 B σ B T2 | σ * ] -E σ * E[A σ A S1 B σ B S2 | σ * ] E σ * E[A σ A T1 B σ B T2 | σ * ] .Let us define the union graphU := S 1 ∪ S 2 ∪ T 1 ∪ T 1 6 . If sD + (a, b) > 1, we view A σ and B σ as A and B, respectively. E[A S1 B S2 A T1 A T2 | σ * ] ̸ = 0 only if there exists no edge e ∈ E(U ) such that it occurs only once among (S 1 , S 2 , T 1 , T 2 ). This is because different edges are independent and centralized conditioned on σ * . Without loss of generality, we assume there exists an edge e ∈ E(A)occur only on S 1 , thus E[A e | σ * ] = 0 and also E[A S1 B S2 A T1 A T2 | σ * ] = 0. However, in regime sD + (a, b) < 1, E[A σ A S1 B σ B S2 A σ A T1 B σ BT2 | σ * ] ̸ = 0 even when edges are not occurring multiple times as we have the expectation of A σ A e can be non-zero when conditioning on σ * and an estimate σ A that disagrees with σ * on the edge type (i.e., for e = (u, v),σ * (u)σ * (v) ̸ = σ A (u) σ A (v)).This not only causes this cross-moments calculation being more complicated, but significantly increasing the possibility of the combinations between S 1 , S 2 , T 1 , and T 2 . The maximum vertex in the union graph grows from 2N to 4N , squaring up the trivial bound on the number of subgraphs on the complete graph K n that is isomorphic to U .The most important high-level idea to properly bound the moments is: the cross-moment conditioning on a specific σ = ( σ A , σ B ) would be non-trivial if and only if all edges occurring only once are centralized incorrectly. This is because, conditioning on σ satisfying the above property, the expectation of A e takes either pq or qp for all e ∈ E(U ) that occurs only once. Assuming there are z edges occurring once, we show that the probability that σ satisfying this property is no greater than n -z(sD + (a,b)-ε log(a/b)/2) D for any ε > 0. Intuitively, this is saying that to incorrectly centralize z edges at the same time, we expect the Algorithm 3 to label at least ⌈ z D ⌉ vertices incorrectly. It turns out that we require n -z(sD + (a,b)-ε log(a/b)/2) D to be o( 1 log C n ) for some positive constant C so that (1) and ( 2) are satisfied.EQUATION) Pick an arbitrary c ∈ (0, 1) and set µ = |T |n N ρ N σ 2Neff , where σ 2 eff := (σ 2 + +σ 2 - 2). Then, Algorithm 1 outputs a set I with size (1o( 1))n and a mapping π such that π| I = π * | I with high probability.Algorithm 1 takes quasi-polynomial time. Algorithm 4 in Section F computes an approximated score in polynomial time and satisfies the following Theorem. Φ σ ij in place of Φ σ ij . Moreover, by Algorithm 4, { Φ σ ij } i,j∈[n] can be computed in O(n C ) for some constant C ≡ C(ε) depending only on ε, where ε is from (3).Exact graph matching. The final step of the algorithm is boosting the almost exact matching to a exact matching. The key idea is exploring the number of common neighbors for two unmatched vertices with regard to the current matching.Define h(x) = x log xx + 1. Denote N π (i, j) as the number of common neighbors of i and j under correspondence π. In another word, N π (i, j) is the number of vertex v ∈ I such that v is a neighbor of i in A and π(v) is a neighbor of j in B. The high-level idea is that if i and j form a true correspondence, then, with high probability N π (i, j) ≥ γ p 2 +q 2 2 s 2 (n + 2n 4 ), under the nice event H. Therefore, we match up i and j if they have more common neighbors than this threshold. In addition, we can show that all the remaining vertices will be matched up with high probability. Formally, we summarize the algorithm as Algorithm 2 and the guarantee as Theorem 5.Theorem 5. Fix a ̸ = b > 0 and s ∈ [0, 1]. Let p = a log n n , q = b log n n and (G 1 , G 2 ) ∼ CSBM(n, p, q, s). Suppose s 2 ( a + b 2 ) ≥ 1 + ε and s 2 ≥ α + ε, for some ε > 0. Let γ be the unique solution in (1, ∞) to h(γ) = 3 log n (n-2)pqs 2 .Then, the seeded matching Algorithm 2 with input π and an index setI ⊂ [n], |I| = (1 -o(1))n ≥ (1 -ε/16)n such that π| I = π * outputs an exact matching π = π * in O(n 3 (p + q) 2 ) time with probability 1 -o(1).Algorithm 2 Seeded Graph Matching [42] Input:EQUATIONAdd i to J and let π(i) = j. 4: end while Output: π.The proof of Theorem 1 follows from Theorem 4 and Theorem 5.Proof of Theorem 1. From Theorem 4, we know that for (G 1 , G 2 ) ∼ CSBM(n, a log n n , b log n n , s), a ̸ = b, if s 2 ≥ α + ε for some ε > 0 then there we can match (1o(1))n vertices correctly and efficiently with high probability.Take the returned π from Algorithm 4 as input of Algorithm 2, then Theorem 5 guarantees that the final output π = π * with probability 1o(1). This completes the proof of Theorem 1.Lemma 3 (Chernoff Bound, Theorem 2.1 of [32] ). Let X ∼ Binom(n, p) be a binomial random variable. Then, for all t ≥ 0,P(X ≥ EX + t) ≤ exp - t 2 2(EX + t/3) , P(X ≤ EX -t) ≤ exp - t 2 2EX .Lemma 4 (Multiplicative Chernoff Bound, Theorem 4.4 and Theorem 4.5 of [46] ). Let X ∼ Binom(n, p) be a binomial random variable, denote µ = np as the mean. Let h(x) = x log x-x+1.Then, for all γ ∈ (1, ∞), P(X ≥ γµ) ≤ exp(-µh(γ)). For γ ∈ (0, 1), P(X ≤ γµ) ≤ exp(-µh(γ)).Lemma 5. [48, 25] Suppose that a < b. (1) .Let Y ∼ Binom(m + , a log n n ) and Z ∼ Binom(m -, b log n n ) be independent. If m + = (1 + o(1)) n 2 , m -= (1 + o(1)) n 2 , then, P(Y < Z) = n -D+(a,b)+oFor any ε > 0,P(Y -Z ≤ ε log n) ≤ n -(D+(a,b)-ε log(a/b) 2)+o (1) .This result has been proved in Lemma 8 in [3] and Lemma 3.3 in [25] .When (G 1 , G 2 ) ∼ CSBM(n, a log n n , b log n n , s), there are some events that happen with high probability and our following analysis intuitively relies on the happening of these nice events.• (Balanced Communities) We denote H := { n 2 -n 3 4 ≤ |V + |, |V -| ≤ n 2 + n 3 4 }. We observe that |V + | ∼ Binom(n, 1 2 ) and |V -| = n -|V + |. By Chernoff bound, P(H c ) = P(|V + | ≥ n 2 + n 3 4 ) -P(|V + | ≤ n 2 -n 3 4 ) ≤ 1 e (1-o(1)) √ n .• (Reasonable Large Neighborhood) Let γ = max(a, b), we also denote thatF = {∀v ∈ [n], |N (v)| ≤ 100 max(1, γ) log 3 n}. Lemma 6.As n → ∞, we haveP(F) ≥ 1 -n -O(log 2 n) . Proof. Let X ∼ Binom(n, γ log n n ). Fix i ∈ [n], conditioned on any σ * , |N (i)| is stochastically dominated by X. Therefore, P(|N (i)| ≥ γ log 3 n | σ * ) ≤ P(X ≥ γ log 3 n) ≤ exp - (γ log 3 n) 2 2γ log n + 2/3γ log 3 n ≤ exp(-γ log 3 n) = n -γ log 2 n ,where the second line uses Bernstein's inequality and the third line holds for any n such that log 2 n > 6. From an union bound, we haveP(F) = E[P(F|σ * )] ≥ 1 -n -O(log 2 n) .We make a slight change on the choice of the partition number of the community detection algorithm proposed by Mossel, Neeman, and Sly [48] . This algorithm gives almost exact recovery with n 1-sD+(a,b)+ε| log(a/b)| vertices labeled incorrectly. After community recovery, we need to match the two communities in G 1 and G 2 by applying the community matching Algorithm 3.Consider G ∼ SBM(n, a log n n , b log n n ). Define γ = max{a, b}. For any vertex v ∈ [n], we define the signed neighbor counts of v in G as maj G (v) = σ * (v) u∈N (v) σ * (u).For any ε > 0, define a set of vertices:I ε (G) := {v ∈ [n] : maj G (v) ≤ ε log n or |N (v)| ≥ γ log 3 n}.Previous results (Lemma 5.1 [25] , Proposition 4.3 [48] ) have shown that Algorithm 3's correctness on log 2 n) -1 ) -1)ε/2 > 1.Initialize two empty sets, W + and W -. 2: Using the spectral method of [3] to find a community partition of [n], denoted as (U + , U -). Using the spectral method of [3] to find a community partition(U i,+ , U i,-) of G{[n] \ U i }. If |U i,+ ∆U + | ≥ n/2, then swap U i,+ and U i,-. 6:For v ∈ U i , insert v into W + or W -according to its neighborhood majority (resp., minority) inU i,+ ∪ U i,-if a > b (resp. a < b). 7: end for 8: For i ∈ W + , set σ(i) = 1, and for i ∈ W -, set σ(i) = -1. Return σ. Lemma 7. Algorithm 3 on input (n, a, b, s) classifies all vertices in [n] \ I ε (G) correctly with high probability.The proof directly follows from the proof of Proposition 5.1 in [25] , with two remarks. First, although the maximum size of neighbors |N (i)| we consider here is enlarged from 100 max{1, γ} log n to γ log 3 n, we adjust the condition of m accordingly such that the tail bound holds. Secondly, we need to justify that with high probability, all partitions done by the spectral method are still almost exactly correct under the new choice of m, which is no longer a constant independent of n. Theorem 3.2 of [3] showed that the vanilla spectral method achieved optimal error rate, in the sense that E[ (a,b) . This implies that with probability 1n -(1+o(1))D+(a,b) , the spectral method labels all but o(n) vertices correctly. Furthermore, for all i ∈ [n], U i,+ matches with V + \ U i and U i,-matches with V -\ U i on all but o(n) vertices after step (5) with high probability.1 n n i=1 1 {σ * (i)̸ = σ(i)} ] ≤ n -(1+o(1))D+In this work, we further determine the probability of a set of vertices being in the set I ε (G), which is a generalization of the result on the P(v ∈ I ε ) for an arbitrary v ∈ [n] (Lemma 5.3 of [25] ). If |S| = O(log n), then for any ε > 0, δ > 0,P({∀i ∈ V (S), i ∈ I ε } ∩ H) = O(n -|S|(sD+(a,b)-ε(1+δ)| log(a/b)|) + n -εδ(1-o(1)) log n ). If |S| = o(log n), then for any ε > 0, δ > 0, P({∀i ∈ V (S), i ∈ I ε } ∩ H) = O(n -|S|(sD+(a,b)-ε(1+δ)| log(a/b)|) ).Proof. The main idea is considering the intersection of the interested event {∀i ∈ S, i∈ I ε } ∩ H with G = {∀i ∈ S, |N S (i)| ≤ εδ log n},where N S (v) denotes the set of neighbors of v restricted on the vertex set S.EQUATIONFirstly, we give the upper bound of P(G c | σ * )1 H . Assume that |S| ≥ εδ log n without loss of generality. By using an union bound,EQUATIONwhere the second equation holds from the assumption of |S| = O(log n).Secondly, we study this event E = {∀i ∈ S, i ∈ I ε } ∩ H ∩ F.P(E) = E[P({∀v ∈ S, maj G (v) ≤ ε log n} | σ * )1 H ] = E[P({∀v ∈ S, maj G[[n]\S] (v) + maj G[S] (v) ≤ ε log n} | σ * )1 H ] ≤ E[P({∀v ∈ S, maj G[[n]\S] (v) ≤ ε(1 + δ) log n} | σ * )1 H ]. For any v ∈ S, maj G[[n]\S] (v) is the difference of two independent binomial random variables Y v and Z v , where Y v ∼ Binom(|V σ * (v) G[[n]\S] |, sa log n n ), Z v ∼ Binom(|V -σ * (v) G[[n]\S] |, sb log n n ). With H happening, we have |V σ * (v) G[[n]\S] | = (1 -o(1)) n 2 , |V -σ * (v) G[[n]\S] | = (1 -o(1)) n 2 .Since Y v and Z v do not take into account v ∈ S, they are independent for all v ∈ S. Therefore,EQUATIONwhere the second line holds by Lemma 5 and the last line holds for sufficiently large n. We conclude with by Lemma 6, Inequality (14) , and Inequality (15) into Inequality (13).Remark 2. For arbitrary ε > 0, we can find ε ′ > 0 and δ > 0 such that ε ′ (1 + δ) = ε. For the sake of convenience, we also denote D + (a, b, s, ε) as sD + (a, b) -ε| log(a/b)| and this is equivalent as the (ε, δ)-parameterization in Lemma 8. We mainly use the sD + (a, b, s, ε) notation in the analysis throughout this paper.Before getting to the first moment calculation of the similarity score, we introduce a sub-problem, named in-community edge counting for node assignment on trees.Assume that we have a random graph G with n vertices, which are labeled by a community label vector σ. We are also given a rooted tree T (i) with N vertices other than the root, where i specifies the root node of T on G. Planting T (i) onto G has at least n N possible positions. If G is a stochastic block model, different planted positions of T would contain different numbers of in-community edges. We are interested in the distribution of the number of in-community edges when planting T (i) onto G uniformly at random. Lemma 9. Let K n be the complete graph of a stochastic block model G on n vertices. Let σ * = {σ * (i)} n i=1 , σ * (i) ∈ {-1, +1} drawn independently and uniformly at random as the vector of community labels. Let v ∈ [n] be an arbitrary node of K n . Let T be an arbitrary rooted tree with N vertices other than the root. Consider a uniformly random injective function τ :V (T ) → V (K n ) such that root r(T ) is mapped to v in V (K n ).Define X as the random variable representing the number of in-community edges in the tree T under random τ . Then,Bin(N, 1 2 -2n -1 4 ) ≼ X | H ≼ Bin(N, 1 2 + 2n -1 4 ).Proof. There are N edges on the tree T . For any(u, v) ∈ V (K n ) × V (K n ), we denote X (u,v)as the indicator random variable of event E ={u and v are from the same community}. Since1 2 -2n -1 4 ≤ P(E | H) ≤ 1 2 + 2n -1 4 , X (u,v) | H stochastically dominates Bernoulli( 1 2 -2n -1 4) and is stochastically dominated by Bernoulli( 1 2 + 2n -1 4 ). Thus, the summation over all edges on tree T , 4 ) and is stochastically dominated by Binom(n, 1 2 + 2n -1 4 ). 4 ), Lemma 9 implies that with some non-negative integerEQUATIONEQUATIONN 1 ≤ N , P({X = N 1 } ∩ H) = (1 + o(1)) N N1 ( 1 2 ) N . Because P({X = N 1 } ∩ H) = (1 -o(1))P(X = N 1 | H), itsuffices to show both the upper and lower bound on P(X = N 1 | H).= N 1 | H) = P(X ≥ N 1 | H) -P(X ≥ N 1 + 1 | H) ≤ t≥N1 N t ( 1 2 + 2n -1 4 ) t ( 1 2 -2n -1 4 ) N -t - t≥N1+1 N t ( 1 2 -2n -1 4 ) t ( 1 2 + 2n -1 4 ) N -t ≤ (1 + o(1)) N N 1 ( 1 2 ) N + t≥(N -N1)∨(N1+1) N t ( 1 2 ) N f (n, N, t), where f (n, N, t) = (1 + 4n -1 4 ) t (1 -4n -1 4 ) N -t -(1 -4n -1 4 ) t (1 + 4n -1 4) N -t . The first inequality holds because of the stochastic dominance in Lemma 9. The second inequality holds becauseN N -t f (n, N, N -t) = N t f (n, N, t) and thus cancels out every term in the summation indexedfrom t = N 1 + 1 to t = N -(N 1 + 1). For t ≥ (N -N 1 ) ∨ (N 1 + 1), we know that N t < N N1 . Also, f (n, N, t) ≤ (1 + 4n -1 4 ) N -(1 -4n -1 4 ) N < O(n -1 4 N ) = o( 1 N) from our assumption on N . Therefore, summing over t ≥ (N -N 1 ) ∧ (N 1 + 1), we haveP(X = N 1 | H) ≤ (1 + o(1)) N N 1 ( 1 2 ) N .From the other direction of stochastic dominance, we haveP(X = N 1 | H) = P(X ≥ N 1 | H) -P(X ≥ N 1 + 1 | H) ≥ (1 -o(1)) N N1 ( 1 2 ) N . Lemma 10. Let K n be the complete graph of a stochastic block model G on n vertices. Let σ * = {σ * (i)} n i=1 , σ * (i) ∈ {-1, +1}drawn independently and uniformly at random as the vector of community labels. Let v ∈ [n] be an arbitrary node of G. Let {T } t i=1 be a sequence of arbitrary rooted tree with N vertices other than the root. Consider a uniformly random injective functionτ : V (T ) → V (K n ) such that root r(T 1 ) of the first tree is mapped to v in V (K n ). Also, the root of i-th tree is mapped to τ (r(T i )) = τ (u) for a fixed vertex on previous trees u ∈ ∪ i-1 t=1 V (T t) or a fixed vertex on K n . Define X as the random variable representing the number of in-community edges in all the trees under random τ . Then,Bin(N, 1 2 -2n -1 4 ) ≼ X | H ≼ Bin(N, 1 2 + 2n -1 4 ).Proof. Define X i as the random variable for number of in-community edges on Tree T i with random embedding τ . The following holds immediately from Lemma 9,Bin(N Ti , 1 2 -2n -1 4 ) ≼ X i | H ≼ Bin(N Ti , 1 2 + 2n -1 4 ). Since X | H = i X i | H, Bin(N, 1 2 -2n -1 4 ) ≼ X | H ≼ Bin(N, 1 2 + 2n -1 4 ).To present the following Lemma 11, we need to introduce a few more definitions: decorated union graph and decorated edges, which will be explained in more details in the context of chandelier in Section I.Decorated Union Graph. Let S 1 , S 2 , T 1 , T 2 be four rooted graphs. The union graph is defined asU := S 1 ∪ S 2 ∪ T 1 ∪ T 2 .We define the decorated union graph as a two-tuple U := (U, D U ), which is U associating with a decoration set. For each edge,D U (e) =The subset of {S 1 , S τ : V (T ) → V (K n ) such that root r(T ) is mapped to v in V (K n ). Define X (i)as the random variable representing the number of i-decorated in-community edges in UP . Assume that |V ( UP )| = O(log n) and UP has excess k. If k = -1, then,P(X (1) = M 1 , X (2) = M 2 , X (3) = M 3 , X (4) = M 4 | H) = (1 ± o(1))P(X (1) = M 1 | H)P(X (2) = M 2 | H)P(X (3) = M 3 | H)P(X (4) = M 4 | H) = (1 + o(1)) d 1 M 1 d 2 M 2 d 3 M 3 d 4 M 4 1 2 d1+d2+d3+d4 .Proof. From the assumption k = -1 we have UP is a tree. We can decompose U P to a sequence of trees as follows: Traverse U P in BFS order and include each maximal connected component with all edges i-decorated as a subtree.In addition, we break this sequence of tree into four sequences based on the decoration number:EQUATIONEQUATIONEQUATIONj } f j=1 . In the random mapping, the root of each tree should be mapped to either v or a non-root vertex on the other tree. Let X (i) j be the random variable for the number of in-community edges for the j-th tree of i-decoration. X (i) j | H satisfies the following stochastic dominance: 4 ).EQUATIONThus, their summation satisfies the following stochastic dominance:EQUATIONAs each of the series of trees occupy O(log n) vertices, every X (i) conditioned on other X (i ′ ) , i ′ ̸ = i still satisfies the stochastic dominance: 4 ).EQUATIONSpecifically, following Remark 3, P(X (4) = M 4 | H) = (1 + o(1)) d4 M4 1 2 d 4 , P(X (3) = M 3 |X (4) = M 4 , H) = (1 + o(1)) d3 M3 1 2 d 3 , P(X (2) = M 2 |X (3) = M 3 , X (4) = M 4 , H) = (1 + o(1)) d2 M2 1 2 d 2 ,and P(X (1) = M 1 |X (2) = M 2 , X (3) = M 3 , X (4) = M 4 , H) = (1 + o(1)) d1 M1 1 2 d 1 .Collectively, these form the asymptotic independence of X (i) :P(X (1) = M 1 , X (2) = M 2 , X (3) = M 3 , X (4) = M 4 | H) = (1 + o(1)) d 1 M 1 d 2 M 2 d 3 M 3 d 4 M 4 1 2 d1+d2+d3+d4 .Lemma 11 discusses the case of k = -1. We do not expect the same property holds for k ≥ 0 but we have an auxiliary result as in the following Corollary 1. Corollary 1. (If k ≥ 0, then UP contains cycles.) By definition, UP can be decomposed into a tree T P with v P vertices other than the root and additional k + 1 distinct edges E k+1 = {(u j , v j )} k+1 i=j fixed. By edges' decorations, E k+1 = E (1) ∪E (2) ∪E (3) ∪E (4) . Let X (i) still be the random variable representing the number of i-decorated in-community edges on UN . If k ≥ 0, let X (i,a) be the counts of i-decorated in-community edges on T N and X (i,b) be the counts of i-decorated in-community edges on {e i } k+1 i=1 . From construction, we know X (i) = X (i,a) + X (i,b) . Correspondingly, there are A i i-decorated edges on tree, B i = |E (i) |, and d i = A i + B i , which are all fixed from UP .Then, P(X (1,a) = a 1 , X (2,a) = a 2 , X (3,a) = a 3 , X (4,a) = a 4 , X (2,b) = b 2 , X (1,b) = b 1 , X (3,b) = b 3 , X (4,b) = b 4 | H) ≤ (1 + o(1)) A1 a1 A2 a2 A3 a3 A4 a4 1 2 A 1 +A 2 +A 3 +A 4 .The proof follows straightforwardly from the proof of Lemma 11. 2 )EQUATION3 )s r(Ts r(T2 ) s r(T3 ) s r(Ts r(T3 )Figure 5 : Decomposition of a decorated tree into three sequences of trees. Edges that are 2, 3, 4-decorated are painted as red, green, and blue color correspondingly. Roots of each subtree is marked by larger node and annotated as r(T(i) j ), where i is the decoration counts and j is the order in its sequence.In this subsection, we study how adding edges can change the number of rooted automorphisms of a rooted tree. With a slight abuse of notation, we denote by aut(T ) the number of rooted automorphisms (i.e., automorphisms which fix the root) of a rooted tree T . We start by quantifying the effect of adding an additional edge. Lemma 12. Let T = (V, E, r) be a rooted tree with root r. Let T ′ := (V ∪ {u}, E ∪ {(u, v)}, r) be the rooted tree obtained from T by adding a vertex u and the edge (u, v), where v ∈ V . The following bounds hold:EQUATIONwhere |V | is the number of vertices in T .Proof. Since T is a rooted tree, there is a natural notion of a parent vertex for every vertex other than the root. Namely, the parent of a vertex v ̸ = r is the neighbor of v which is closest to the root r. We also define the subtree rooted at v to be the subtree of T induced by all vertices whose shortest path to r goes through v, rooted at v.We partition V into equivalence classes according to the following rule: v 1 and v 2 are in the same equivalence class if and only if they share the same parent and the subtrees rooted at v 1 and v 2 are isomorphic. We denote the resulting partition as {V i } i∈I and refer to the equivalence classes as orbits. Note that the root r is always in a single-element orbit and thus the size of each orbit is at most |V | -1.Observe that a permutation of the vertices is a rooted automorphism precisely when it maps each vertex to a vertex in its orbit. Thus we have thatEQUATIONNow consider T ′ , which adds a new vertex u to T with an edge connecting u to a vertex in T . By (17) , in order to understand aut(T ′ ), we need to understand how the orbits and their sizes change due to the addition of the new vertex and edge. The new vertex u will either join an existing orbit or form its own one. The parent of u may change orbits, so might the parent of its parent, etc. In other words, the vertices on the path from u to the root r might change their orbit, but vertices not on this path will not. In the following, we argue iteratively based on the depth of u in T ′ (i.e., its distance from the root). When considering the upper bound, we will ignore the possible size decrease of orbits. When considering the lower bound, we will ignore the possible size increase of orbits.Assume first that the new vertex u is attached to the root r. If there are no leaves except for u connecting to r, then u forms a new orbit V |I|+1 whose size is 1, which does not change the number of rooted automorphisms. Otherwise, without loss of generality, assume that orbit V 1 is the set that contains all leaves connected to r. Then u will join this orbit, so the set of orbits of T ′ is given by V 1 ∪ {u} and {V i } |I| i=2 . Thus, we have that aut(T ′ ) = aut(T )(|V 1 | + 1), so in particularaut(T ) ≤ aut(T ′ ) = aut(T )(|V 1 | + 1) ≤ aut(T ) × |V |.Now suppose that u has depth 2 in T ′ , and let v (1) denote the parent of u in T ′ . Without loss of generality, assume that v (1) ∈ V 1 . There are again two cases depending on whether or not there are leaves attached to v (1) in T . Suppose first that there are not any leaves attached to v (1) in T .Then u has its own orbit (of size 1) in T ′ . The orbit of v (1) changes from V 1 in T to either a new orbit or some existing orbit V j1 in T ′ (for some 2 ≤ j 1 ≤ |I|). In the former case we have that aut(T ′ ) = aut(T )/|V 1 |, while in the latter case we have thataut(T ′ ) = aut(T ) × |V j1 | + 1 |V 1 | .The desired inequalities thus follow since each orbit has size at most |V | -1. Now suppose that there are leaves attached to v (1) in T and let V 2 denote the equivalence class of these vertices. Then, u joins the orbit V 2 in T ′ . The orbit of v (1) again changes from V 1 in T to either a new orbit or some existing orbit V j1 in T ′ (for some 3 ≤ j 1 ≤ |I|). In the former case we have that aut(T ′ ) = aut(T ) × (|V 2 | + 1)/|V 1 |, while in the latter case we have thataut(T ′ ) = aut(T ) × (|V 2 | + 1)(|V j1 | + 1) |V 1 | .The lower bound follows since|V 1 | ≤ |V | -1.For the upper bound in the latter case, note that by the definition of orbits, in T ′ there are |V j1 | + 1 nodes at depth 1 who each have |V 2 | + 1 children that are leaves. This implies that T ′ has at least(|V 2 | + 1)(|V j1 | + 1) non-root vertices, so (|V 2 | + 1)(|V j1 | + 1) ≤ (|V | + 1) -1 = |V |.The general case when u has depth ℓ in T ′ is analogous. Let v (ℓ-1) denote the parent of u in T ′ , let v (ℓ-2) denote the parent of v (ℓ-1) , etc. Without loss of generality, let V i denote the orbit of v (i) in T , for i ∈ [ℓ -1]. Suppose that v (ℓ-1) has children that are leaves in T (the other case, when it does not, is similar and simpler), and let V ℓ denote the equivalence class of these vertices. Then, using similar observations as above, we obtain the following upper and lower bounds on aut(T ′ ):aut(T ) × 1 ℓ-1 i=1 |V i | ≤ aut(T ′ ) ≤ aut(T ) × (|V ℓ | + 1) × ℓ-1 i=1 (|V ji | + 1) .Here, for every i ∈[ℓ -1], either j i ∈ [ℓ + 1, |I|] (which corresponds to v (i) changing from V i in T to some existing orbit V ji in T ′ ) or |V ji | = 0 (which corresponds to v (i) changing from V i in T to a new orbit in T ′ ).To conclude the lower bound, observe (using the definition of orbits) that T contains a subtree consisting of the root andℓ-1 i=1 |V i | additional vertices, so ℓ-1 i=1 |V i | ≤ |V | -1.For the upper bound, observe similarly that T ′ contains a subtree consisting of the root and(|V ℓ | + 1) × ℓ-1 i=1 (|V ji | + 1) additional vertices, so (|V ℓ | + 1) × ℓ-1 i=1 (|V ji | + 1) ≤ |V |.Lemma 12 is tight. Let T be a star rooted at its center (i.e., a tree where all vertices except the root are connected to the root). Then all permutations of the vertices that fix the root are rooted automorphisms, so aut(T ) = (|V (T )| -1)!. Now let T ′ be a tree obtained from T by adding an additional child to the root (see Figure 6 , tree in the middle). Then aut(T ′ ) = (|V (T )|)! = aut(T ) × |V (T )|. This shows that the upper bound in Lemma 12 is tight. Now let T ′′ be a tree obtained from T by adding a child to one of the leaves of T (see Figure 6 , tree on the right). The rooted automorphisms of T ′′ are precisely the permutations of the vertices that permute the neighbors of the root which are leaves, so aut(T ′′ ) = (|V (T )| -2)! = aut(T )/(|V (T )| -1). This shows that the lower bound in Lemma 12 is tight.From Lemma 12, we can derive the following corollary by an iterative argument. Corollary 2. Let T 1 = (V 1 , E 1 , r) and T 2 = (V 2 , E 2 , r) be two trees rooted at the same vertex r.Define the unionT 1 ∪ T 2 := (V 1 ∪ V 2 , E 1 ∪ E 2 , r) by taking the union of the two vertex sets (both of which contain r) and the union of the two edge sets, with multiple edges ignored (i.e., if an edge appears in both E 1 and E 2 , then it appears in E 1 ∪ E 2 exactly once). Suppose that T 1 ∪ T 2 is also a tree. Let d := |E 1 △E 2 | denote the size of the symmetric difference of the edge sets. ThenEQUATION)Proof. By the assumptions on T 1 and T 2 , the unionT 1 ∪ T 2 has (|V 1 | + |V 2 | + d)/2 -1 edges.There are two natural ways that we can think of T 1 ∪ T 2 . First, we can start from T 1 and add Combining these two inequalities, we obtain that(|V 2 | -|V 1 | + d)/2 new vertices-those that are in V 2 but not in V 1 -aut(T 1 )aut(T 2 ) ≤ aut(T 1 ∪ T 2 ) × (|V1|+|V2|+d)/2-2 k=min{|V1|,|V2|}-1 k. Since d ≤ 2(max{|V 1 , V 2 |} -1), it follows that (|V 1 | + |V 2 | + d)/2 -2 ≤ 2 max{|V 1 |, |V 2 |}, so all factors in the product above are at most2 max{|V 1 |, |V 2 |}. Note also that d ≥ max{|V 1 , V 2 |} - min{|V 1 , V 2 |}, so the number of factors in the product above is (max{|V 1 , V 2 |} -min{|V 1 , V 2 |} + d)/2 ≤ d.Putting these observations together we see that (18) holds.Remark 4. The leftmost example in Figure 6 provides an example showing that the right hand side of (18) would no longer be an upper bound without the factor (2 max{|V 1 |, |V 2 |}) d .In this section, we summarize the upper bound on cross-moments. In Lemma 13, we work on the regime sD + (a, b) > 1 where we can recover the community label exactly first. In Lemma 14, we work on the regime sD + (a, b) < 1 where we we have a inverse polynomial fraction of vertices being labeled incorrectly.          1 (ℓ, m) = (2, 0), (0, 2) (1 + Θ( log n n ))ρ (ℓ, m) = (1, 1) 1 √ s(p∧q) (ℓ, m) = (2, 1), (1, 2) 1 s(p∧q) (ℓ, m) = (2, 2).Proof. Conditioning on a specific true community label vector that satisfies the balanced community event H, we can apply Lemma 5 from [43] for each case of c(e) = + and c(e) = -. Then, the upper bound are different in terms of p, q and ρ + , ρ -. When (ℓ, m) = (1, 1),β ℓ,m ≤ max{|ρ + |, |ρ -|} ≤ (1 + Θ( log n n ))ρ. When (ℓ, m) = (2, 1) or (1, 2), if c(e) = +, then we have β ℓ,m ≤ 1 √ sp , else we have β ℓ,m ≤ 1 √ sq . Therefore, β ℓ,m ≤ 1 √ s(p∧q). The same argument holds for the case when (ℓ, m) = (2, 2). Lemma 14. Let (G 1 , G 2 ) ∼ CSBM(n, p, q, s), p = a log n n , q = b log n n . Denote A σ A , B σ Bη ℓ,m (e) := σ -(ℓ+m) c(e) E[A σ A ,ℓ e B σ B ,m e | σ * , σ] ≤                Θ( √ ∆) (ℓ, m) = (0, 1), (1, 0) 1 + Θ( log n n ) (ℓ, m) = (2, 0), (0, 2) ρ(1 + Θ( log n n )) (ℓ, m) = (1, 1) 1 √ s(p∧q) (1 + Θ( log n n )) (ℓ, m) = (2, 1), (1, 2) 1 s(p∧q) (1 + Θ( log n n )) (ℓ, m) = (2, 2).Proof. Denote the two vertices on e as u and v. We denote p ′ := sp and q ′ := sq.(a) ℓ + m = 1. Without loss of generality, we consider ℓ = 1 and m = 0.σ A ,1 e | σ * , σ] = 0, σ * (u)σ * (v) = σ A (u) σ A (v), ±∆, σ * (u)σ * (v) ̸ = σ A (u) σ A (v). When E[A σ A ,1 e | σ * , σ] is non-zero, σ -1 c(e) E[A σ A ,1 e | σ * , σ] = Θ( √ ∆). (b) ℓ + m = 2.We first consider the case of ℓ = 2 or m = 2.We explicitly calculate the expectation on the following two cases.If σ * (u)σ * (v) = σ(u) σ(v), then E[A σ A ,2 e | σ * , σ] = p ′ (1 -p ′ ) = σ 2 c(e) . If σ * (u)σ * (v) ̸ = σ(u) σ(v), then E[A σ A ,2 e | σ * , σ] = p ′ -2p ′ q ′ + q ′2 = σ 2c(e) + ∆ 2 . In summary, we haveE[A σ A ,2 e | σ * , σ] = E[B σ B ,2 e | σ * , σ] ≤ σ 2 c(e) + ∆ 2 = σ 2 c(e) (1 + Θ( log n n )).We next consider the case ofℓ = m = 1. If σ * (u)σ * (v) = σ(u) σ(v), then E[A σ A ,1 e B σ B ,1 e | σ * , σ] = ρ c(e) σ 2 c(e) . If σ * (u)σ * (v) ̸ = σ(u) σ(v), then E[A σ A ,1 e B σ B ,1 e | σ * , σ] = ρ c(e) σ 2c(e) + ∆ 2 . In summary, we haveE[A σ A ,1 e B σ B ,1 e | σ * , σ] ≤ ρ c(e) σ 2 c(e) + ∆ 2 = ρσ 2 c(e) (1 + Θ( log n n )) (c) ℓ + m = 3.With loss of generality, we assume that this edge connects two vertices from different communities. Conditioned on correct centralization, we can computeE[A σ A ,2 e B σ B ,1 e | σ * , σ] = E[A 2 e B e | σ * ] = qs 2 (1 -q)(1 -2qs) = σ 3 - ρ -(1 -2q ′ ) q ′ (1 -q ′ ) ≤ σ 3 - 1 √ q ′ ,which is the same as in Lemma 13. If the centralization is incorrect for both graphs, the expectation changes to the following:E[A σ A ,2 e B σ B ,1 e | σ * , σ] = q ′ s -p ′ q ′ -2p ′ q ′ s + 3p ′2 q ′ -p ′3 .From observation, we see that the dominant part in both cases are the same, which is q ′ s = Θ( log n n ). Then, we can show that the difference between two quantities are minor:EQUATIONThe above (20) also holds for the case when e is classified correctly in A or B only.By also considering the other case, that is, this edge is connects two vertices from the same community but wrongly centralized according to σ, we conclude withE[A σ A ,2 e B σ B ,1 e | σ * , σ] ≤ σ 3 c(e) 1 s(p ∧ q) (1 + Θ(s(p ∧ q))) = σ 3 c(e) 1 s(p ∧ q) (1 + Θ( log n n )) (d) ℓ + m = 4.With loss of generality, we assume that this edge connects two vertices from different communities. For the correct centralization, the moment stays the same as in Lemma 13,E[A 2 e B 2 e | σ * ] = q ′ s -4q ′2 s + 4q ′3 s + 2q ′3 -3q ′4 = q ′2 (1 -q ′ ) 2 + q ′ (1 -q ′ )ρ -(1 -2q ′ ) 2 ≤ σ 4 - 1 q ′ .If the centralization is incorrect for both graphs, we haveE[A σ A ,2 e B σ B ,2 e | σ * , σ] = q ′ s -4p ′ q ′ s + 4p ′2 q ′ s + 2p ′2 q ′ -4p ′3 q ′ + p ′4 ,and we can show that the error has the following orderEQUATIONWhen the centralization is incorrect for only one graph, (21) still holds.By also considering the other case, that is, this edge is connects two vertices from the same community but wrongly centralized according to σ, we conclude with . Depending on the different parameter regimes, the analysis is different. We first present the first and second moment bounds for both regimes and then prove Theorem 3.E[A σ A ,2 e B σ B ,2 e | σ * , σ] ≤ Θ(σ 4 c(e) ) + σ 4 c(e) 1 s(p ∧ q) ≤ σ 4 c(e) 1 s(p ∧ q) (1 + Θ( log n n )).Proposition 1 (Mean calculation, sD + (a, b) ≥ 1). Given (G 1 , G 2 ) ∼ CSBM(n, a log n n , b log n n , s), the similarity score satisfies,E[Φ ij 1 H ] = (1 + o(1))µ, if π * (i) = j, 0, if π * (i) ̸ = j.Proposition 2 (Variance calculation-True pairs, sD + (a, b) > 1). Suppose that j = π * (i), that sD + (a, b) > 1, and thatEQUATIONEQUATIONThen, for any i ∈ [n], we haveVar[Φ ij 1 H ] E[Φ iπ * (i) 1 H ] 2 = O L 2 ρ 2 ns(p ∧ q) + L 2 ρ 2(K+M ) |J | .Proposition 3 (Variance calculation-Fake pairs, sD + (a, b) > 1). Suppose that j ̸ = π * (i), that sD + (a, b) > 1, and thatEQUATIONEQUATION)Then, for any i ∈ [n], we haveVar[Φ ij 1 H ] E[Φ iπ * (i) 1 H ] 2 = O( 1 |T |ρ 2N ).Before getting into the details of proof, let us first give more intuition on the approximately centralized adjacency matrix.In this regime, for each element in the adjacency matrix, there are four cases: (1) Correct centralization for in-community edges; (2) Incorrect centralization for in-community edges; (3) Correct centralization for cross-community edges; (4) Incorrect centralization for cross-community edges. Figure 7 gives an example of how the graphon for balanced 2-community SBM changes under community label misclassifications. E[Φ σ iπ * (i) 1 H ] = (1 + o(1))µ.For all i ∈ [n] with j ̸ = π * (i), we haveEQUATIONThen, for any i ∈ [n], we haveEQUATIONThen, for any i ∈ [n], we haveVar[Φ σ ij 1 H ] E[Φ σ iπ * (i) 1 H ] = O( 1 |T |ρ 2N ).Proof of Proposition 3. Firstly, with the following conditions, (22) (23) (24) (25) are implied:EQUATION)for some absolute constants c 1 , c 2 , . . . , c 7 > 0.Furthermore, with growing ns(p∧q), we have for j = π * (i),Var[Φij 1 H ] E[Φ iπ * (i) 1 H ] 2 = o(1) when sD + (a, b) > 1 and Var[Φij 1 H ] E[Φ iπ * (i) 1 H ] 2 = o(1) when sD + (a, b) < 1. For any ε > 0 there exists ε ′ > 0 such that s 2 ≥ α + ε ⇔ ρ 2 ≥ α + ε ′ . We have for j ̸ = π * (i), Var[Φij 1 H ] E[Φ iπ * (i) 1 H ] 2 = o( 1 n 2 ) when sD + (a, b) > 1 and Var[Φij 1 H ] E[Φ iπ * (i) 1 H ] 2 = o( 1 n 2 ) when sD + (a, b) < 1.Next, we claim that almost exact recovery is achievable by counting chandeliers. Let τ = cµ, for arbitrary c ∈ (0, 1), where µ = E[Φ iπ * (i) 1 H ]. By Chebyshev's inequality, the probability that the similarity score of a fake pair (j ̸ = π * (i)) of vertices exceeding τ , is upper bounded asP(Φ ij 1 H ≥ τ ) ≤ P (|Φ ij 1 H -E[Φ ij 1 H ]| ≥ cE[Φ ij 1 H ]) ≤ Var[Φ ij 1 H ] c 2 E[Φ ii 1 H ] 2 = O 1 |T |ρ 2N = o( 1 n 2 ).Next, by the definition of H, we haveP(Φ ij ≥ τ ) ≤ P(Φ ij 1 H ≤ c) + P(H c ) = o( 1 n 2 ).Applying union bound over all i ̸ = j ∈ [n], we have P{∃i ̸ = j, Φ ij ≥ τ } = o(1). Thus, for all possible pairs of vertices (i, j) ∈ [n] × [n], Φ ij < τ with high probability.We next study the probability that the similarity score of a true pair of vertices falling below the threshold τ . We even consider a larger set containing F := {i ∈ [n] : Φ iπ * (i) < τ },P(|Φ iπ * (i) 1 H -µ| > (1 -c)µ) ≤ Var[Φ iπ * (i) 1 H ] (1 -c) 2 E[Φ iπ * (i) 1 H ] 2 = O L 2 ρ 2 ns(p ∧ q) + L 2 ρ 2(K+M ) |J | =: γ = o(1).Therefore,E[|F |] ≤ nγ. Denote I ∈ [n]the vertex set this algorithm matches. For every vertex not in the set F , it is guaranteed to be matched up correctly, soE[|I|] ≥ n -E[|F |] = n(1 -γ).By Markov's inequality,P(|F | >= √ γn) ≤ γn √ γn = √ γ = o(1).Therefore, Algorithm 1 matches |I| ≥ (1 -√ γ)n vertices correctly with high probability.In Regime II, with Proposition 4, Proposition 5, and Proposition 6, the same argument follows. These two regimes together complete the proof.In this section, we re-state and modify the efficient graph matching algorithm for correlated Erdős-Rényi graphs discussed in Section 5 of [42] , and then analyze it for correlated SBMs.Let (G 1 , G 2 ) be a pair of correlated SBMs with adjacency matrices A and B. Let H be a rooted connected graph with N + 1 vertices. We now want to approximately count the signed subgraphs rooted at i ∈ [n] on the centralized adjacency matrices. In general, we do not have access to the centralized adjacency matrices A and B, we would use community label estimates σ A and σ B from Algorithm 3 to approximately centralize the adjacency matrices as A σ A and B σ B .First, we generate a random coloring µ : [n] → [N + 1], which is assigning every node on A to one of N + 1-the same as the number of vertices on a chandelier-colors independently and uniformly at random. For any vertex set V ⊂ [n], we define χ µ (V ) = 1 {∀x,y∈V,x̸ =y:µ(x)̸ =µ(y)} . We call the vertex set V being colorful if χ µ (V ) = 1. We denote r := P(χ µ (V ) = 1) = (N +1)! (N +1) N +1 . We define the approximate signed rooted subgraph count asEQUATIONObserve thatE[X i,H (A σ A , µ)] = rW i,H (A σ A ), where W i,H (A σ A )is the ground truth of signed counts as defined in Section C. In another word, X i,H (A σ A , µ)/r is an unbiased estimator ofW i,H (A σ A ).Let t := ⌈1/r⌉, we repeat the random coloring for t times and then average over the estimates before taking the inner product of two signed counts vectors. Formally, we generate 2t independent colorings independently and uniformly at random, denoted as {µ a } t a=1 and {ν b } t b=1 . For vertex i in G 1 and vertex j in G 2 , we define the approximate similarity score as followsΦ σ ij := 1 r 2 H∈T aut(H) 1 t t a=1 X i,H (A σ A , µ a ) 1 t t b=1 X j,H (B σ B , ν b ) .We haveE[ Φ σ ij |A σ A , B σ B ] = Φ σ ij and also E[ Φ σ ij 1 H |A σ A , B σ B , σ * ] = Φ σ ij 1H also holds as 1 H is a deterministic function on σ * . We summarize the algorithm as Algorithm 4. There are two additional steps than Algorithm 2 in [42] : First, in the construction of the chandelier class in this work, we need to filter out instances with maximum degree greater than a threshold D, which takes O(K) time for each tree; Second, we need to obtain the community label estimates before estimating the signed subgraph counts.Input: Adjacency matrices A and B on n vertices for correlated stochastic block models (G 1 , G 2 ).Step 1 -Construct the chandelier class 1: (Rooted tree generation [6] ) List all non-isomorphic rooted trees with K edges. 2: (Automorphism constraint [12] ) Compute aut(H) for each rooted tree using the automorphism algorithm for trees. 3: (Maximum degree constraint) Compute maximum degree of vertices. When we can obtain the correct centralized adjacency matrices A and B, we replace A σ A (resp.B σ B ) with A (resp. B), and everything defined above is still valid. In that case, we denote the approximate similarity score as Φ rather than Φ σ .The analysis is similar to that in Section 5.1 of [42] , while we split the analysis into two regimes.Under Regime I (sD + (a, b) > 1), we can recover the community labels on G 1 and G 2 exactly correct with high probability. We define Γ ij as an upper bound of Var[Φ ij ] as follows:Var[Φ ij 1 H ] ≤ H,I∈Taut(H)aut(I)EQUATION)If 1 {S1△T1⊂S2∪T2,S2△T2⊂S1∪T1} = 0, then there exists some edge occurring only once among S 1 , S 2 , T 1 , and T 2 , and so|E[A S1 B S2 A T1 B T2 1 H ]| = 0.Therefore, we only look at the cases where every edge occurs at least two times among these four chandeliers. If1 {S1̸ =S2 or T1̸ =T2 or V (S1)∩V (T1)̸ ={i}} = 0, then S 1 = S 2 , T 1 = T 2 ,and S 1 has no common vertex with T 1 except for the root. In this case, S 1 and T 1 , and S 2 and T 2 have no common edges, so the covariance between A S1 B T1 and A S2 B T2 is always zero.For Regime II (sD + (a, b) < 1), where we cannot recover the correct centralized adjacency matrices with high probability. Alternatively, we define Γ ′ ij as:EQUATIONFrom the definition of variance,Var[Φ σ ij 1 H ] ≤ Γ ′ ij . Lemma 15. Fix constants a ̸ = b > 0, s ∈ [0, 1]. Let (G 1 , G 2 ) ∼ CSBM(n, a log n n , b log n n , s). The variance of estimation error has the following upper bound:Var[( Φ ij -Φ ij )1 H ] ≤ 3Γ ij , Var[( Φ σ ij -Φ σ ij )1 H ] ≤ 3Γ ′ ij ,where Γ ij is defined in (28) and Γ ′ ij is defined in (29) .Proof. Regime I: Assume that sD + (a, b) > 1. DefineY ij (µ, ν) := H∈T aut(H)X i,H (A, µ)X j,H (B, ν),where µ, ν are two (N + 1)-coloring of the vertices in [n] . Then, we can represent the approximate similarity score asEQUATION)For anyµ c , ν d , 1 ≤ c, d ≤ t, Y ij (µ c , ν d )/r 2 is an unbiased estimator of Φ ij given A, B as E[Y ij (µ c , ν d )1 H |A, B, σ * ] = r 2 H∈T aut(H)W i,H (A)W j,H (B)1 H = r 2 Φ ij 1 H .Note that X i,H (A, µ) and X j,H (B, ν) are independent conditioned on A, B. Moreover, note that {Y ij (µ c , ν d )} 1≤c,d≤t are identically distributed. Hence, we haveE[ Φ ij 1 H ] = E[E µ,ν [ 1 r 2 t 2 t c=1 t d=1 Y ij (µ c , ν d )1 H |A, B, σ * ]] = E[Φ ij 1 H ].Next, we bound the variance of Φ ij . In particular, we can getVar[( Φ ij -Φ ij )1 H ] = Var(E[( Φ ij -Φ ij )1 H |A, B, σ * ]) + E[Var(( Φ ij -Φ ij )1 H |A, B, σ * )] = E[Var( Φ ij |A, B, σ * )1 H ],because Φ ij and 1 H are fixed conditional on A, B, σ * . Furthermore, conditioned on A and B, for any 1 ≤ c, d, e, f ≤ t, Y ij (µ c , ν d ) are independent with Y ij (µ e , ν f ) if and only if c ̸ = e and d ̸ = f .Var[( Φ ij -Φ ij )1 H ] ≤ 1 r 4 t 4 t c=1 t d=1 t e=1 t f =1 E[Cov(Y ij (µ c , ν d ), Y ij (µ e , ν f ))|A, B, σ * )1 H ].Applying Lemma 16, we haveVar[( Φ ij -Φ ij )1 H ] ≤ 1 r 4 t 4 t c=1 t d=1 t e=1 t f =1 (r 2+1 {c̸ =e} +1 {d̸ =f } -r 4 )Γ ij = 1 r 2 t 2 t 2 r 2 + 2t 3 r 3 -(t 2 + 2t 3 )r 4 Γ ij ≤ 3Γ ij ,where the last inequality holds because t = ⌈1/r⌉, tr ≥ 1.Regime II: Assume that sD + (a, b) < 1. With community label estimates σ A and σ B , we defineEQUATIONwhere µ, ν are two (N + 1)-coloring of the vertices in [n]. The proof for Regime I still holds in this case by replacingA, B, Y ij , Φ ij , Φ ij and Γ ij with A σ A , B σ B , Y σ ij , Φ σ ij , Φ σ ij and Γ ′ ij correspondingly.Lemma 16 (Extension of Lemma 12 in [42] to correlated SBMs).EQUATION)EQUATION)Proof. We first prove (33) and then explain why it implies (32) .For two independent (N + 1)-colorings µ and ν of the vertices inEQUATION)From the definition of Y σ ij (µ, ν) in (31) again,E[Y ij (µ c , ν d )Y ij (µ e , ν f )|A σ A , B σ B , σ * ] = E[ H∈T aut(H)X i,H (A σ A , µ c )X j,H (B σ , ν d ) × I∈T aut(H)X i,I (A σ A , µ e )X j,I (B σ B , ν f )|A σ A , B σ B , σ * ].From ( 27) and the independence of colorings,E[Y ij (µ c , ν d )Y ij (µ e , ν f )|A σ A , B σ B , σ * ] = E H,I∈Taut(H)aut(I)S1(i),S2(j) ∼ =H T1(i),T2(j) ∼ =I χ µc (V (S 1 ))A σ A S1 × χ ν d (V (S 2 ))B σ B S2 × χ µe (V (T 1 ))A σ A T1 × χ ν f (V (T 2 ))B σ B T2 |A σ A , B σ B , σ * = H,I∈Taut(H)aut(I)EQUATIONFrom ( 34), (35) , and (10) ,E[Cov(Y ij (µ c , ν d ), Y ij (µ e , ν f )|A σ A , B σ B , σ * )1 H ] = H,I∈Taut(H)aut(I)S1(i),S2(j) ∼ =H T1(i),T2(j) ∼ =I E[A σ A S1 B σ B S2 A σ A T1 B σ B T2 1 H ] × E[χ µc (V (S 1 ))χ µe (V (T 1 ))]E[χ ν d (V (S 2 ))χ ν f (V (T 2 ))] -r 4 .Observe thatE[χ µc (V (S 1 ))χ µe (V (T 1 ))] ≤ r 1+1 {c̸ =e} and E[χ ν d (V (S 2 ))χ ν f (V (T 2 ))] ≤ r 1+1 {d̸ =f } , E[Cov(Y ij (µ c , ν d ), Y ij (µ e , ν f )|A σ A , B σ B , σ * )1 H ] ≤ H,I∈Taut(H)aut(I)S1(i),S2(j) ∼ =H T1(i),T2(j) ∼ =I E[A σ A S1 B σ B S2 A σ A T1 B σ B T2 1 H ](r 2+1 {d̸ =f } +1 {c̸ =e} -r 4 ) = Γ ′ ij (r 2+1 {d̸ =f } +1 {c̸ =e} -r 4 ),and this completes the proof for Regime II.S1 B S2 A T1 B T2 1 H ] ̸ = 0 only if {S 1 △ T 1 ⊂ S 2 ∪ T 2 , S 2 △ T 2 ⊂ S 1 ∪ T 1 } happens. In addition, if S 1 = S 2 , T 1 = T 2 , and V (S 1 ) ∩ V (T 1 ) = {i}, then E[χ µc (V (S 1 ))χ µe (V (T 1 ))] = E[χ ν d (V (S 2 ))χ ν f (V (T 2))] = r 2 , because S 1 (resp. S 2 ) shares no common edges with T 1 (resp. T 2 ) Therefore,E[Cov(Y ij (µ c , ν d ), Y ij (µ e , ν f )|A, B, σ * )1 H ] ≤ H,I∈Taut(H)aut(I)S1(i),S2(j) ∼ =H T1(i),T2(j) ∼ =I E[A S1 B S2 A T1 B T2 1 H ](r 2+1 {d̸ =f } +1 {c̸ =e} -r 4 ) = H,I∈Taut(H)aut(I)S1(i),S2(j) ∼ =H T1(i),T2(j) ∼ =I E[A S1 B S2 A T1 B T2 1 H ](r 2+1 {d̸ =f } +1 {c̸ =e} -r 4 ) × 1 {S1̸ =S2 or T1̸ =T2 or V (S1)∩V (T1)̸ ={i}} 1 {S1△T1⊂S2∪T2,S2△T2⊂S1∪T1} = Γ ij (r 2+1 {d̸ =f } +1 {c̸ =e} -r 4 ),where the first line follows from the proof in Regime II and the last line applies the definition of Γ ij (28) . Now, we are ready to prove Theorem 4.For the first part of this proof, our goal is to show that the estimated score preserves the asymptotic upper bound onVar[Φij 1 H ] E[Φ iπ * (i) 1 H ] 2for Regime I andVar[Φ σ ij 1 H ] E[Φ σ iπ * (i) 1 H ] 2 for Regime II. For Regime I (sD + (a, b) > 1), we have Var[ Φ ij 1 H ] E[ Φ iπ * (i) 1 H ] 2 = Var[ Φ ij 1 H ] E[Φ iπ * (i) 1 H ] 2 = 1 E[Φ iπ * (i) 1 H ] 2 Var[Φ ij 1 H ] + Var[( Φ ij -Φ ij )1 H ] + 2 Cov(( Φ ij -Φ ij )1 H , Φ ij 1 H ) ,where the first equality is from the fact that Φ ij 1 H is an unbiased estimator of Φ ij 1 H conditioned on A, B, and σ * . Further,Var[ Φ ij 1 H ] E[ Φ iπ * (i) 1 H ] 2 ≤ 1 E[Φ iπ * (i) 1 H ] 2 Γ ij + 3Γ ij + 2E[( Φ ij -Φ ij )Φ ij 1 H ] ≤ 4 Γ ij E[Φ iπ * (i) 1 H ] 2 ,where the first inequality holds from (28) , Lemma 15, and E[( Φ ij -Φ ij )1 H ] = 0, and the second inequality holds because E[(( Φ ij -Φ ij )Φ ij 1 H )] = E[E[( Φ ij -Φ ij )|A, B, σ * ]Φ ij 1 H ] = 0.The proof of Proposition 2 and Proposition 3 are based on analyzing Γ ij and thus the upper bounds onVar[Φij 1 H ] E[Φ iπ * (i) 1 H ] 2 all hold for Γij E[Φ iπ * (i) 1 H ] 2 . Therefore, we conclude that for all i ∈ [n], if (22) holds, then Var[ Φ iπ * (i) 1 H ] E[ Φ iπ * (i) 1 H ] 2 = O L 2 ρ 2 ns(p ∧ q) + L 2 ρ 2(K+M ) |J | ;and that for all i, j ∈ [n], j ̸ = π * (i), if (23) holds, thenVar[ Φ ij 1 H ] E[ Φ iπ * (i) 1 H ] 2 = O 1 |T |ρ 2N .For Regime II (sD + (a, b) < 1), from (29) and Lemma 15 ,Var[ Φ σ ij 1 H ] E[ Φ σ ij 1 H ] 2 ≤ 1 E[Φ σ iπ * (i) 1 H ] 2 Γ ′ ij + 3Γ ′ ij + 2E[( Φ σ ij -Φ σ ij )Φ σ ij 1 H ]) ≤ 4 Γ ′ ij E[Φ σ iπ * (i) 1 H ] 2 ,The proof of Proposition 5 and Proposition 6 are based on analyzing Γ ′ ij and thus the upper bounds onVar[Φ σ ij 1 H ] E[Φ σ iπ * (i) 1 H ] 2 all hold for Γ ′ ij E[Φ σ iπ * (i) 1 H ] 2 . Therefore, we conclude that for all i ∈ [n], if (24) holds, then Var[ Φ σ iπ * (i) 1 H ] E[ Φ σ iπ * (i) 1 H ] 2 = O L 2 ρ 2 ns(p ∧ q) + L 2 ρ 2(K+M ) |J | ;and that for all i, j ∈ [n], j ̸ = π * (i), if (25) holds, thenVar[ Φ σ ij 1 H ] E[ Φ σ iπ * (i) 1 H ] 2 = O 1 |T |ρ 2N .For the second part of this proof, we are going to show the time complexity of Algorithm 4.First, we know that step 1-1 costs time O(β K ) by the algorithm in [6] , step 1-2 takes time O(K) by the algorithm in [12] , and step 1-3 takes time O(K) by enumerating through all edges. In summary, he total time complexity to generate J is O(K 2 α K ). Afterwards, it takes O(|T |) time to complete step 1-4, the generation of chandelier class.The signed counts estimation step takes O(|T |N 3 N n 2 ) times as shown in the proof of Proposition 5 in [42] . Then, the total time complexity isO K 2 β K + |T |(1 + N (3e) N n 2 ) = O |J | L N (3e) N n 2 = O β KL (3e) N n 2 = O (3eβ) N n 2 .Under condition (3) and for large enough log(ns(p ∧ q)) ≥ log(2), we haveN = (K + M )L = C ′ log n ε (1 + C ′′ log(ns(p ∧ q)) ) ≤ C ′ (1 + C ′′ log 2 ) ε log n,for some constants C ′ and C ′′ . Hence, there exists some constant C depending only on ε such that the total time complexity of Algorithm 4 is O(n C ).For a pair of correlated SBMs (G 1 , G 2 ) ∼ CSBM(n, p, q, s), where p = a log n n and q = b log n n , Algorithm 4 efficiently matches (1o(1))n vertices correctly with high probability. Our next step is to finish the matching on those remaining vertices.To do this, we use the seeded graph matching algorithm7 (Algorithm 2): Starting with an initial partial matching on at least (1ε/16)n vertices which is correct on whatever it matches, we form new matches between vertex i in G 1 and vertex j in G 2 if the common neighbors of those two vertices under the current partial matching sufficiently large. We then update the partial matching and repeat this rule until we get a complete matching, which will be shown happens with high probability. Define h(x) = x log xx + 1. The sufficiently large common neighbors threshold is set as γ p 2 +q 2 2 s 2 (n + 2n 4 ), where γ ∈ (1, ∞) such that h(γ) = 3 log n (n-2)pqs 2 . Denote N π (i, j) as the number of common neighbors of i and j under correspondence π. In another word, N π (i, j) is the number of vertex v ∈ I such that v is a neighbor of i in A and π(v) is a neighbor of j in B. If π = π * , we also write it as N(i, j).The following lemma for SBM is an analogy to Lemma 13 in [42] , which studied the property of Erdős-Rényi graph. (η) = (1+ ε 8 ) log n (p+q)( n 2 -n 3/4 -ε 16 n) . In particular, η ≥ 1 - 1 + ε 8 (1 + ε)(1 -ε 7 ).Proof. If I = ∅, e G (I, I c ) ≥ η|I||I c | p+q 2 holds trivially. Let I be an non-empty set with 1 ≤ |I| ≤ ε 16 n. We denote k as |I|. The number of edges between I and I c is the summation of k(nk) independent Bernoulli trails. For arbitrary vertex i ∈ I and vertex j ∈ I c , if they have the same community label, then the Bernoulli trail between them has mean p. Otherwise,t he Bernoulli trail has mean q. We assume that there are N 1 trails with mean p and N 2 trails with mean q, where N 1 + N 2 = k(nk). We can write out the distribution as e G (I,I c ) ∼ Binom(N 1 , p) + Binom(N 2 , q).Under the balanced community event H, n 2 -n 3/4 ≤ |V + |, |V -| ≤ n 2 + n 3/4. Assume that there are k + vertices in I with label +1 and the remaining k -vertices with label -1.EQUATIONEQUATION)We are interested in the probability of e G (I, I c ) being less than n|I||I c |p ∧ q:P(e G (I,I c ) ≤ ηk(n-k)p∧q) ≤ P(e G (I, I c ) ≤ η(N 1 p+N 2 q)) ≤ exp(-(N 1 p+N 2 q)h(η)),where the first inequality holds because N 1 + N 2 = k(nk) and p ∧ q ≤ p, q and the second inequality holds because of the multiplicative Chernoff bound (Lemma 4).LetEQUATIONwhere the first inequality holds because of ( 36) and (37) , the second inequality holds because a+b 2 ≥ 1 + ε and the third inequality holds for sufficiently large n. Since h(η) ∈ (0, 1), there is an unique solution of η ∈ (0, 1) due to the monotocity (decreasing) of the function h(•).Applying the fact that (N 1 p + N 2 q)h(η) > (1 + ε 8 ) log n (38) and using an union bound over all subsets I ⊂ [n] with size 1 ≤ |I| ≤ ε 16 , we haveP(∃I ⊂ [n] s.t. 1 ≤ |I| ≤ ε 16 , e G (I, I c ) ≤ η|I|(n -|I|)p ∧ q) ≤ ε 16 k=1 n k P(e G (I, I c ) ≤ ηk(n -k)p ∧ q) ≤ ε 16 k=1 n k-k(1+ ε 8 ) = O(n -ε 8 ). Because h(x) ≥ (x-1) 2 2 for x ∈ (0, 1), we have η ≥ 1 -2h(η) > 1 - 1+ ε 8 (1+ε)(1-ε 7 ). Now, we are ready to prove Theorem 5.Proof of Theorem 5. Firstly, we study the size of common neighbors. For an arbitrary vertexu ∈ [n] in G 1 and v ∈ [n]in G 2 such that v is not the true correspondence of u, we study the number of common neighbors N(u, v) in the intersection graph corresponding to the true permutation.Case a: These two vertices come from different communities.If v ̸ = π * (u), σ(u)σ(v) = -1, then we have N(u, v) ∼ Binom(n -2, pqs 2 ). By the multiplicative Chernoff bound (Lemma 4) for Binomial distributions, for γ ∈ (1, ∞), we haveP(N(u, v) ≥ γ p 2 + q 2 2 s 2 (n + 2n 3 4 )) < P(N(u, v) ≥ γ(n -2)pqs 2 ) ≤ e -(n-2)pqs 2 h(γ) = n -3 , where h(γ) = 3 log n (n-2)pqs 2 > 1, γ ∈ (1, ∞).The first inequality holds because p 2 +q 2 2 (n + 2n3 4 ) > (n -2)pq.u, v such that v ̸ = π * (u), σ(u)σ(v) = -1, we have P{∃v ̸ = π * (u), σ(u)σ(v) = -1, s.t. N(u, v) ≥ γ p 2 + q 2 2 s 2 n(1 + 2n -1 4 )} = O( 1 n ).Case b: These two vertices come from the same community.If v ̸ = π * (u), σ(u)σ(v) = 1, then we have N(u, v) ∼ Binom(|V σ(v) | -2, p 2 s 2 ) + Binom(|V -σ(v) |, q 2 s 2 ) because there are |V σ(v) | -2vertices left from the same community as u, v and |V -σ(v) | vertices from the different community.Denoten 1 as |V σ(v) | -2 and n 2 as |V -σ(v) |, n 1 + n 2 = n -2. P{N(u, v) ≥ γ p 2 + q 2 2 s 2 (n + 2n 3 4 )} < P{N(u, v) ≥ γ(n 1 p 2 + n 2 q 2 )s 2 } ≤ exp(-(n 1 p 2 + n 2 q 2 )s 2 h(γ)) < n -3 .The first inequality holds because p 2 +q 2 2 (n + 2n 4 ) > n 1 p 2 + n 2 q 2 . The last inequality holds becauseEQUATION> 3 log n n1p 2 +n2q 2 for sufficiently large n.Then, with an union bound over all u, v such that v ̸ = π * (u), σ(u)σ(v) = 1, we haveP{∃v ̸ = π * (u), σ(u)σ(v) = 1, s.t. N(u, v) ≥ γ p 2 + q 2 2 s 2 n(1 + 2n -1 4 )} = O( 1 n ).Combining the above two cases, we haveEQUATIONSecondly, we show that the algorithm is working properly. From (39), we assume that for all v ̸ = π * (u), N(u, v) < γ p 2 +q 2 2 s 2 (n + 2n 4 ). We want to show π = π * | J in every step of Algorithm 2 by induction. This is true for the initialization of π as a base case, from our assumption for Theorem 5. Suppose that this is true for t-th round of the algorithm, then at the (t + 1)-th round, we have that for all v ̸ = π * (u), 4 ).EQUATIONTherefore, as the (t + 1)-th round, the algorithm will still not add an fake correspondence. Either the algorithm terminates, or a new vertex i is added to J such that π(i) = i, which preserves the property π = π * | J .Next, we show that Algorithm 2 always ends with J = [n] by contradiction. Assume that the algorithm terminates with |J| < n, then J c ̸ = ∅. Then, by definition, for al i 4 ). Therefore, 4 ).EQUATIONEQUATIONOn the other side,EQUATIONTo reach a contradiction between ( 40) and ( 41), the remaining is to prove thatEQUATION.We observe that h(γ) = 3 log n (n-2)pqs 2 = Θ(1), whileEQUATION= Θ( n log n ). Therefore (42) holds for sufficiently large n. Finally, we analyze the time complexity of Algorithm 2. For each u ∈ [n] to be added into the seeded set I, we update the number of common neighbors N π (i, j) for all i, j ∈ I. This step takes O(deg G1 (u) deg G2 (u)), where deg G (u) denotes the degree of u in graph G. With probability1 -o( 1 n 2 ), deg G1 (u) = O(n(p + q)). By summing up for all possible u to be added, the time complexity of Algorithm 2 is O(n 3 (p + q) 2 ).In this section, we calculate the expectation of similarity score for correlated SBM. Recall that we have defined σ 2 + := sp(1sp), σ 2 -:= sq(1sq) and that σ 2 eff := (σ 2 + +σ 2 - 2) throughout this paper.Proof of Proposition 1. By definition of the similarity score,E[Φ ij 1 H ] = H∈T aut(H) S(i) ∼ =H S(j) ∼ =H E A S(i) B S(j) 1 H .The expectation is zero if S(i) = S(j), which implies considering π * (i) = j suffices:E[Φ ij 1 H ] = (1 + o(1)) H∈T aut(H) S(i) ∼ =H E A S(i) B S(π * (i)) | H .Define X 1 as the random variable for the number of in-community edges of S(i), which takes possible value from 0 to N . Define |{S(i) : S(i) ∼ = H}| as the total number of S rooted at i and isomorphic to H, we haveE[Φ iπ * (i) 1 H ] = (1 + o(1)) H∈T aut(H)|{S(i) : S(i) ∼ = H}|E E A S(i) B S(π * (i)) | X 1 , H ≤ (1 + o(1)) H∈T n N N N1=0 P(X 1 = N 1 | H)ρ N σ 2N1 + σ 2N -2N1 - .The second inequality holds by |{S(i) :S(i) ∼ = H}| = ( n N )N! aut(H) = (1 + o(1)) n Naut(H) since n N N ! is the number of possible vertex embedding of the chandelier onto the random graph and alsoE A S(i) B S(π * (i)) |{X 1 = N 1 } ∩ H = ρ N1 + ρ N -N1 - σ 2N1 + σ 2(N -N1) - = (1 + o(1))ρ N σ 2N1 + σ 2(N -N1) - .Then, according to Lemma 9 and the binomial theorem, we have P(X 1 = N 1 | H) = (1 + o(1)) N N1 2 -N . Therefore, E[Φ iπ * (i) 1 H ] = (1 + o(1))|T |n N ρ N N N1=0 N N 1 1 2 N σ 2N1 + σ 2N -2N1 - = (1 + o(1))|T |n N ρ N ( σ 2 + + σ 2 - 2 ) N = (1 + o(1))|T |n N ρ N σ 2N eff .The analysis of the first moment involves two chandeliers, while the second moment analysis requires four chandeliers. Before delving into the analysis, we introduce the notation for the decorated union graph and establish a rule for union graph partition. We adopt some notations and definitions from [42] and further introduce concepts that are particularly useful for correlated stochastic block models.• (Decorated Graph) For any graph G, define Ġ as a decorated graph Ġ := (G, D G ), where D G is a decoration mapping from the edge set to a decoration set. Define the edge set of decorated graph E( Ġ) := E(G) and the vertex set of decorated graph V ( Ġ) := V (G). • (Decorated Union Graph) For any pair of chandeliers H, I ∈ T , let S 1 (i), S 2 (j) ∼ = H and T 1 (i), T 2 (j) ∼ = I. The union graph is defined as U = S 1 ∪ S 2 ∪ T 1 ∪ T 2 . Now, let us define the proper decoration for U :EQUATIONWe call an edge e ∈ E(U ) t-decorated if |D U (e)| = t, t ∈ {0, 1, 2, 3, 4}.• (Decorated Set Operation) Assume that U = (U, D U ) and U ′ = (U ′ , D U ′ ) are two decorated graphs. We define the union, intersection, and difference operations, from which the complement and symmetric difference naturally follow.-Union. U ∪ U ′ := (U ∪ U ′ , D U ′′ : D U ′′ (e) = D U (e) ∪ D U ′ (e)). -Intersection. U ∩ U ′ := (U ∩ U ′ , D U ′′ : D U ′′ (e) = D U (e) ∩ D U ′ (e)). -Difference. U \ U ′ := (U \ U ′ , D U ′′ : D U ′′ (e) = D U (e) \ D U ′ (e)).• (Union Graph Partition) Assume that i is the root of union graph. Consider the graph U with edge (i, a) removed for all neighbors a of i. Let Ċ(i, a) be the connected component therein that contains a. Let Ġ(i, a) be the graph union of Ċ(i, a) and the edge (i, a). Then, we divide the set of root neighbors N (i) into the following sets depending on whether Ġ(i, a) is a tree:N T = {a : (i, a) ∈ E(U ), Ġ(i, a) is a tree}, N N = {a : (i, a) ∈ E( U )} \ N T .Furthermore, we breakdown N T into two sets depending on whether there are at least M edges 3-decorated:N M = {a ∈ N T , |{e ∈ E( Ġ(i, a)) : |D U (e)| ≥ 3}| ≥ M }, N L = N T \ N M , .Next, we define the decomposition of decorated union graph U :EQUATIONIf any of these become an empty set, we define it as the graph consisting of the single vertex i. To provide an intuitive understanding: UN contains those chandelier branches that form cycles in the union graph, while UL and UM are the collection of those chandelier branches that do not tangle with other branches from bottom and remain a part of tree rooted at i (or j) in the union graph. As a characteristic of trees, the decorations on edges within UM and UN are monotonically decreasing, meaning that the decoration set of an edge at depth d ≥ 1 is always a subset of the decoration set of the preceding edge at depth d -1 that connects to it. For each node v ∈ UM that is connected to the root, the connected component Ġ(i, a) should have at list M vertices that are at least 3-decorated. UL is the union of all connected components remained that are trees. The definition of UL implies that the branches cannot be fully 3-decorated, otherwise this branch would fall in UM .For every union graph, we can decompose the decorated union graph based on its decoration sets. Specifically, we want to keep track of how many times each vertex appears on the chandeliers that are rooted at i and the chandeliers that are rooted at j. We present the definition as follows. Definition 3 (Decorated union graph decomposition by decorations).EQUATION) Definition 4 (Edge counts on 3 and 4-decorated edges). Based on the definition of union graph partition and K ℓm , we further defineEQUATIONEQUATIONEQUATIONwhere 2e L (resp. 2e M , 2e N ) is the counts of 3-decorated edges and two times the 4-decorated edges on U L (resp. U M , U N ).We use U L (v L , e L , ℓ) to denote the collection of all possible UL with v L vertices except for i and j, e L counts of special edges as defined, and ℓ edges in K 11 ∩ UL . U M (v M , e M ) denotes the family of all possible UM with v M vertices except for i and j and e L counts of special edges as defined.U N (v N , e N , k) denotes the family of all possible UN with v N vertices except for i and j, e N counts of special edges as defined, and excess k.We further define the weights for of decorated graphs UL , UM , and UN .Definition 5. Let Ġ be an arbitrary UL , UM , or UN , we define the weight of Ġ with regard to a chandelier S as w S ( Ġ) :=EQUATION)We set w S ( Ġ) = 1 if Ġ contains no bulbs in K(S). We define the weight of Ġ as the multiplication of its weights over S 1 , S 2 , T 1 , T 2 :EQUATIONWe have the following observation with regard to the concepts introduced above:• (Counting edges) 2(v L + v M + v N + k + 1 + 1 {i̸ =j} ) + 2(e L + e M + e N ) = 4N . This holds because 2(v L + v M + v N + k + 1 + 1 {i̸ =j}) counts all the edges on union graph twice and 2(e L + e M + e N ) makes up for an additional count for 3-decorated edges and two counts for 4-decorated edges.• (Automorphism as decorated graph weights) From the definition of aut(•) and chandelier, (aut(S 1 )aut(S 2 )aut(T 1 )aut(T 2 ))EQUATION• (Trivial upper bound on the decorated graph weights) Since aut(B) is upper bounded by R for arbitrary bulb B, this inequality follows from the definition of decorated union graph weightsEQUATIONThe same holds for UM and UN .Specific to the moment calculation for correlated stochastic block models, we present the following two definitions.Definition 6 (g U (σ + , σ -)). Fix chandeliers (S 1 , S 2 , T 1 , T 2 ) on the complete graph, conditioned on the ground-truth labels of correlated SBMs, we define a function as follows:g U (σ + , σ -) := σ h(S1)+h(S2)+h(T1)+h(T2) + σ h(S1)+h(S2)+h(T1)+h(T2) -, where h(•) is the counts of edges connecting two points from the same community, h(•) is the counts of edges connecting two points from different communities on the complete graph K n .Definition 7 (Extension of σ 2 eff ). We define γ 2 :=σ 4 + +σ 4 - 2/σ 4 eff and γ 1 :=σ 3 + +σ 3 - 2 /σ 3 eff . Thus, σ 4 + +σ 4 - 2 k = (1 + o(1)) σ 2 + +σ 2 - 2 2kγ k 2 andσ 3 + +σ 3 - 2 k = (1 + o(1)) σ 2 + +σ 2 - 2 3k 2 γ k 1 .Remark 5. We observe that γ 2 < 2 and γ 1 ≤ γ 2 . The first holds simply becauseσ 4 + + σ 4 -≥ 2σ 2 + σ 2 -.By Cauchy-Schwarz inequality, for an arbitrary random variable X,E[X 3 ]E[X 2 ] 2 ≤ E[X 4 ]E[X 2 ] 3/2 . Let X takes σ 2 + and σ 2 -uniformly at random, then E[X 3 ] E[X 2 ] 3/2 ≤ E[X 4 ] E[X 2 ] 2 and thus γ 1 ≤ γ 2 is implied.In regime sD + (a, b) > 1, we can recover the correct community label with high probability [2, 48, 1] . Therefore we can effectively work on the correct centralized adjacency matrices. Recall thatH = { n 2 -n 3 4 ≤ |V + |, |V -| ≤ n 2 + n 3 4}, as defined in Section D.Proof of Proposition 2. From the definition of variance,Var[Φ ij 1 H ] = H,I∈T aut(H)aut(I) S1,S2 ∼ =H,T1,T2 ∼ =I Cov(A S1 B S2 1 H , A T1 B T2 1 H ).If S 1 = S 2 , T 1 = T 2 , and V (S 1 ) ∩ V (T 1 ) = {i}, the covariance becomes zero. Also, we know from Proposition 1 thatE[A S1 B S2 ]E[A T1 B T2 ] is either 0 or (1 + o(1))(ρσ eff ) 2N . Thus, Var[Φ ij 1 H ] ≤ H,I∈T aut(H)aut(I) S1,S2 ∼ =H,T1,T2 ∼ =I E[A S1 B S2 A T1 B T2 1 H ]. E[A S1 B S2 A T1 B T2] is non-zero if and only if each edge e ∈ U is at least 2-decorated. Let W ij denote the collection of decorated union graph U D , where S 1 (i), S 2 (j) ∼ = H, T 1 (i), T 2 (j) ∼ = I for some H, I ∈ T , such that each edge is at least 2-decorated and satisfiesEQUATIONConditioned on the ground-truth labeling σ * ,EQUATION, v) = + if σ * (u) = σ * (v) and c(u, v) = -if σ * (u) ̸ = σ * (v).Conditioned on σ * , H is determined,EQUATIONConditioned on σ * , g U (σ + , σ -) is fixed, so as g -1 U (σ + , σ -).g U (σ + , σ -) -1 E[A S1 B S2 A T1 B T2 | σ * ] = 2≤ℓ+m≤4 (u,v)∈K ℓm σ -(ℓ+m) c(u,v) E[A ℓ uv B m uv | σ * ].We define β ℓm (e) as σ-(ℓ+m) c(u,v) E[A ℓ uv B m uv | σ * ], for e = (u, v) ∈ K ℓ,m . Thus, g U (σ + , σ -) -1 E[A S1 B S2 A T1 B T2 | σ * ] = g U (σ + , σ -) -1 2≤ℓ+m≤4 (u,v)∈K ℓm β ℓm (e).Then, we apply Lemma 13 to bound each β ℓm (e). Since the upper bound of β ℓm (e) only depends on ℓ and m, we have the following:g U (σ + , σ -) -1 E[A S1 B S2 A T1 B T2 | σ * ] ≤| max{ρ + , ρ -}| e(K11) (sp ∧ sq) -e(K22)(sp ∧ sq)(e(K21)+e(K12))EQUATIONwhere the last equality holds because 2 54) and (55) , and the fact that H happens with high probability, we haveEQUATION) It remains to compute E [g U (σ + , σ -) | H].Here, U is fixed and we assume that there are d 2 2decorated edges, d 3 3-decorated edges, and d 4 4-decorated edges without loss of generality. Let X (2) , X (3) , and X (4) be the number of in-community edges for 2, 3, and 4-decorated edges on the complete graph respectively. In U is a tree, we can apply Lemma 10 to determine the distribution of X (2) , X (3) , and X (4) .Generally, U contains cycles. U can be decomposed into a tree with an additional set of edges connecting vertices on the tree. We assume that there are A i i-decorated edges on the tree and B i i-decorated edges in the additional edge set of size e( U )v( U ) + 1, for i ∈ {2, 3, 4}. We apply the Corollary 1 and have that P(X (2,a) = a 2 , X (3,a) = a 3 , X (4,a) = a 4 , X (2,b) = b 2 , X (3,b) = b 3 , X (4,b) = b 4 | H) ≤ (1 + o(1)) A2 a2 A3 a3 A4 a4 1 2 A 2 +A 3 +A 4, where X (i,a) is the number of idecorated in-community edges on the tree-part of U and X (i,b) is the number of i-decorated incommunity edges among the additional edge set.A i and B i are fixed but summed up to d i for each U . a i (b i ) takes possible values from 0 to A i (B i ), for i ∈ [4] . The number of i-decorated in-community edges is a i + b i , and the number of i-decorated cross-community edges isEQUATIONwhere the last inequality holds because we can upper bound by multiplying a binomial coefficient EQUATIONThe last inequality holds because γ 1 < γ 2 and d 3 + d 4 = e(K 12 ) + e(K 21 ) + e(K 22 ) ≤ 2(e L + e M + e N ).Denote W ij (v, k) as the subset of W ij that contains all the elements that have exactly v vertices except for i and j and excess k. By applying the definition of union graph partitions, decorated graph weights, and (53) ,EQUATIONFor the UL , UM , UN partition, we defineEQUATIONEQUATIONEQUATIONThen, we can write out the upper bound asVar[Φ ij 1 H ] ≲ k v (sp ∧ sq) -2N +v+k+1 v L ,v M ,v N ≥0 e L ,e M ,e N ,ℓ≥0 σ 4N eff γ 2(e L +e M +e L ) 2 2 k+1× ρ ℓ P L (v L , e L , ℓ)P M (v M , e M )P N (v N , e N , k).Applying Proposition 1, Lemma 18, Lemma 19, and Lemma 20, we can upper bound the variance by:Var[Φ ij 1 H ] ≲ k v (sp ∧ sq) -2N +v+k+1 vi≥0 ei,ℓ≥0 ρ ℓ (11βn) v M R 4e M M 1 {v M ≤e M 4K+4M M } × σ 4N eff γ 2(e L +e M +e L ) 2 × 2n v L (1 + 2L 2 ) e L f t,t 1 {K+M |e L +v L } 1 {v L +e L ≤2N } × n v N (11β) v N (22R 4 (v N + 1) 2 ) k+1 1 {v N ≤2(K+M )(k+1)} Note that v M ≤ e M 4K+4M M , we have v M ≥0 (11β) v M ≤ 2(11β) e M 4K+4M M. Also, we know thatv N ≤ 2N, v N ≤ 2(K + M )(k + 1). Then, v N ≥0 (11β) v M ≤ 2(11β) 2(K+M )(k+1) . Thus, Var[Φ ij 1 H ] ≲ k,v (sp ∧ sq) -2N +v+k+1 e L +e M +e N =2N -(v+k+1) 2 3 n v R 4 M (11β) 4K+4M M e M × (22R 4 (2N + 1)(11β) 2(K+M ) ) k+1 (1 + 2L 2 ) e L σ 4N eff γ 2(e L +e M +e L ) 2 × v L ≥0,l≥0 ρ ℓ f t,t 1 {K+M |e L +v L } 1 {v L +e L ≤2N } .Regarding to the Lemma 4 in [42] , if 12L 2 ρ 2(K+M ) (|J |-2L) ≤ 1 2 , then Var[Φ ij 1 H ] ≲ k,v (sp ∧ sq) -2N +v+k+1 v L +v M +v N +e L +e M +e N =2N 2 3 n v R 4 M (11β) 4K+4M M e M (22R 4 (2N + 1)(11β) 2(K+M ) ) k+1 (1 + 2L 2 ) e L σ 4N eff γ 2(e L +e M +e N ) 2 8ρ 2N ρ -2e L 1 e L ̸ =0 + 12L 2 ρ 2(K+M )|J | 1 e L =0 |T | 2 .Var[Φ ij 1 H ] E[Φ iπ * (i) 1 H ] 2 ≤ (1 + o(1))2 6 σ 4N -4N eff k≥-1 22R 4 (2N + 1)(11β) 2(K+M ) n k+1 e M ≥0 γ 2 2 R 4 M (11β) 4K+4M M ns(p ∧ q) e M e L ≥0 γ 2 2 1 + 2L 2 ns(p ∧ q) e L ρ -2e L 1 {e L >0} + 12L 2 ρ 2(K+M ) |J | 1 {e L =0} 2N e M ≥0 γ 2 2 ( n sp ∧ sq ) 2N -(v+k+1+e L +e M ) 1 {e L +e M ≤2N -(v+k+1)}In view of γ 2 < 2, the last three conditions in (22) guarantee that k≥-122R 4 (2N + 1)(11β) 2(K+M ) n k+1 ≤ 2, e M ≥0 γ 2 2 R 4 M (11β) 4K+4M M ns(p ∧ q) e M ≤ 2, e L ≥0 γ 2 2 1 + 2L 2 ns(p ∧ q) e L ≤ 2.and the non-tree part UN := U \ ( UL (i) ∪ UM (i) ∪ UL (j) ∪ UM (j)).For convenience, we denote UL := UL (i) ∪ UL (j), UM := UM (i) ∪ UM (j).We again assign weights to each of these decorated union graph partitions.w( UL ) := w S1 ( UL (i))w T1 ( UL (i))w S2 ( UL (j))w T2 ( UL (j)),w( UM ) := w S1 ( UM (i))w T1 ( UM (i))w S2 ( UM (j))w T2 ( UM (j)),EQUATIONProof of Proposition 3. In the case of j ̸ = π * (i), the excess k of the union graph starts from -2. This is because the minimum number of edges of a decorated union graph for j ̸ = π * (i) with v vertices except for i and j is v, when S 1 , T 1 and S 2 , T 2 form two disjoint trees rooted at i and j respectively. Therefore,k ≥ v -v( U ) = -2.The proof of Proposition 2 in Section I holds for j ̸ = π * (i) until ( 59), which holds with placing k + 1 with k + 2. This is because the decorated union graph can be viewed as two disjoint trees with v + 2 vertices plus k + 2 edges connecting vertices on these two trees. We have,Var[Φ ij 1 H ] ≤ (1 + o(1)) k≥-2 2N -k-2 v=0 (sp ∧ sq) -2N +v+k+2 U ∈Wij (v,k)ρ e(K11) aut(H)aut(I)× σ 4N eff γ e(K12)+e(K21)+e(K22) 2 2 k+2 .We define P ij (v, k) := U ∈Wij (v,k) ρ e(K11) aut(H)aut(I)γ e(K12)+e(K21)+e(K22) 2.Var[Φ ij 1 H ] ≤ (1 + o(1)) k≥-2 2N -k-2 v=0 (sp ∧ sq) -2N +v+k+2 σ 4N eff 2 k+2 P ij (v, k)Case a: k = -2. We first consider the special case when k = -2. When k = -2, there are two disjoint trees in the decorated union graph. Then, it must be the case ofS 1 = T 1 , S 2 = T 2 , v = 2N, and H = I. Therefore, e(K 12 ) = e(K 21 ) = e(K 22 ) = 0. We have,P ij (2N, -2) ≤ H∈T aut(H) 2 |S 1 (i) : S 1 ∼ = H||S 2 (j) : S 2 ∼ = H| = |T |n 2N .Under this parameterization, -2N + v + k + 2 is also zero, we haveVar[Φ ij 1 H ] ≤ (1+o(1)) |T |n 2N σ 4N eff + k>-2 2N -k-2 v=0 (sp ∧ sq) -2N +v+k+2 σ 4N eff 2 k+2 P ij (v, k) .It turns out that the summation over k > -2 would have the same order as the first special case.Case b: k > -2. We enumerate through three parts of the union graph. Recall that e(K 12 ) + e(K 21 ) + e(K 22 ) ≤ 2(e L + e M + e N ) = 4N -2(v + k + 2), thereforeEQUATIONwhere P M (v M , e M ) is defined as before, while we let P L (v L ) and P N (v N , k) have no constraints on the number of 3 and 4-decorated edges for UL and UN .We can plug those upper bounds from Lemma 21, Lemma 22, and Lemma 23 into (69): 3(k+2) . Applying e M ≤ 2N -(v +k +2), v N ≤ 4(K +M )(k +2) and v M ≤ 2(K +M ) e M M we can get the following upper bound:P ij (v, k) ≤ e M R 2 e M M n v |T |4 L L 2L∧(4K+2) (6β) 4(K+M )-2 1 {e M ≤2N -(v+k+2)} × v L +v M +v N =v v M (11β) v M β(11β) v N (22R 4 (v N + 2) 2 ) k+2 σ 4N eff γ 4N -2(v+k+2) 2 × 1 {v M ≤2(K+M ) 2e M M } 1 {v N ≤4(K+M )(k+2)} . Note that v M , v N ≤ v ≤ 2N -k -2 ≤ 2N + 1 as k ≥ -1. Therefore v M (v N + 2) 2(k+2) ≤ (2N +1)Var[Φ ij 1 H ] E[Φ iπ * (i) 1 H ] 2 ≤ (1 + o(1)) 1 |T |ρ 2N + (1 + o(1)) 1 |T |ρ 2N 4 L L 2L∧(4K+2) (6β) 4K+4M × k≥-1 (11β) 4(K+M ) 22R 4 (2N + 1) 3 n k+2 × 2N -k-2 v=0 γ 2 2 R 2 M (11β) 4(K+M ) M ns(p ∧ q) 2N -(v+k+2).From the first condition in (23) , because γ 2 < 2, we have2N -k-2 v=0 γ 2 2 R 2 M (11β) 4(K+M ) M ns(p ∧ q) 2N -(v+k+2) ≤ 2.From the second condition in (23) , we have (11β) From the second condition in (23) , we know that4 L L 2L∧(4K+2) (6β) 4K+4M 2 2 (11β) 4(K+M ) 22R 4 (2N + 1) 3 n ≤ 1 2 .In summary,Var[Φ ij 1 H ] E[Φ iπ * (i) 1 H ] 2 = O( 1 |T |ρ 2N ).The following Lemma 21, Lemma 22, and Lemma 23, have been shown by Mao et al. [42] . We briefly re-state those results for completeness. Lemma 21 (Upper bound of P L (v L ) (Fake pairs: j ̸ = π * (i), sD + (a, b) > 1)).P L (v L ) ≤ n v L |T |4 L L 2L∧(4K+2) (6β) 4(K+M )-2 .Proof. Firstly, we introduce unlabeled union graph sets U(v L , e L ) and the set of labeled isomorphic members as H( UL ), for UL ∈ U(v L , e L , l). From definition (60) ,P L (v L ) = UL ∈U L (v L ) w( UL ) = UL ∈ U L (v L ) w( UL )|H( UL )|.As we have repeatedly seen, |H( UL )| ≤ n v L aut( UL ) . From the Lemma 10 and Claim 5-(v) in [42] we have the following takeaways: (1) | U L (v L )| ≤ |T |4 L L 2L∧(4K+2) (6β) 4(K+M )-2 ; (2) w( UL ) ≤ aut( UL (i))aut( UL (j)) = aut( UL ). Putting pieces together, we complete the proof.In this section, we prove Proposition 4, which extends the Proposition 1 to the case when we can only perform almost exact community recovery with a single graph. We denote σ := ( σ A , σ B ), which is the combination of the community label estimates for both graphs.Proof of Proposition 4. By definition of the similarity score and H,E[Φ σ ij 1 H ] = H∈T aut(H) S(i) ∼ =H T (j) ∼ =H E[A σ A S B σ B T 1 H ] = (1 + o(1))H∈T aut(H)S(i) ∼ =H T (j) ∼ =H E E[A σ A S B σ B T | σ * , σ]1 H .Define C as the edge collection of the intersection graph of S and T : C := E(S) ∩ E(T ).E[Φ σ ij 1 H ] ∼ H∈T aut(H) S(i) ∼ =H T (j) ∼ =H E   E[ e∈C A σ A e B σ B e e ′ ∈E(S)\C A σ A e ′ e ′′ ∈E(T )\C B σ B e ′ | σ * , σ]1 H   ∼ H∈T aut(H) S(i) ∼ =H T (j) ∼ =H E e∈C E[A σ A e B σ B e | σ * , σ] e ′ ∈E(S)\C E[A σ A e ′ | σ * , σ] × e ′′ ∈E(T )\C E[B σ B e ′ | σ * , σ]1 H .We perform case studies for E[Φ σ ij 1 H ] based on the structure of S, T as a union graph and then later sum each case up.(a) S = T , that is, all edges appear in pairs (this case is only possible for i = j). There are (1 + o(1))n N /aut(H) labeled union graphs of S 1 and T 1 satisfying this condition. In this case, every edge is 2-decorated and it no longer matters whether σ gives a correct output or not, as we can show the following upper bound.E[Φ σ ij 1 H ] (A) = (1 + o(1)) H∈T aut(H) n N aut(H) E e∈C E[A σ A e B σ B e | σ * , σ]1 H ≤ (1 + o(1))|T |n N N+ P(ζ = N + ) N ′ P(η c+ = N c+ , η c-= N c-|ζ = N + ) × (ρ + σ 2 + ) Nc+ (ρ -σ 2 -) Nc-(ρ + σ 2 + + ∆ 2 ) N+-Nc+ (ρ -σ 2 -+ ∆ 2 ) N -N+-Nc- ≤ (1 + o(1))|T |n N N N+=0 N N -1 1 2 N (ρσ 2 + + ∆ 2 ) N+ (ρσ 2 -+ ∆ 2 ) N -N+ = (1 + o(1))|T |n N (ρσ 2 eff + ∆ 2 ) N, where ζ is the number of in-community edges out of the N edges in S, η c+ is the number of incommunity edges that are centralized incorrectly, η c-is the number of cross-community edges that are centralized incorrectly, and ∆ := |p -q|. (i) The first equality holds by definition and counting cases. (ii) The second inequality holds because there are N c+ (N c-) in(cross)-community edges centralized correctly, each of which contributes the same asE[A e B e | σ * ] = (1 + o(1))ρ + σ 2 + (ρ -σ 2 -) (Lemma 13). For the remaining edges, N + -N c+ (N -N + -N c-) of them has E[A σ A e B σ B e | σ * , σ] = (1 + o(1))(ρ + σ 2 + ) + E[A σ A e | σ * , σ]E[B σ B e | σ * , σ] ≤ (1 + o(1))(ρ + σ 2 + + ∆ 2 ). (iii)The third inequality holds because ∆ 2 > 0, Lemma 9 gives the distribution of ζ, and ρ = (1 + Θ( log n n ))ρ + , ρ = (1 + Θ( log n n ))ρ -. (iv) The last equality holds from the binomial theorem. Observe that ∆ 2 = (1 + Θ( log n n ))(ρσ 2 eff ). Assume that N = O(log n), E[Φ σ ij 1 H ] (A) = (1 + o(1))|T |n N (ρσ eff ) N .EQUATIONwhere E denotes the event{ σ : e∈E(S) E[A σ A e ] e∈E(T ) E[B σ Be ] = Θ(∆ e(S)+e(T ) )} ∩ H, that is, every edge is centralized correctly and H happens. This inequality is true because conditioned on H and σ being correct, E[Aσ A e | σ * , σ]1 H = o(n -D+(a,b,s,ε)), the upper bound of the probability that one vertex on this edge being labeled incorrectly.We further denote E ′ as { σ A : e∈E(S) E[A σ A e ] = Θ(∆ e(S) )}∩H. It is obvious that P(E) ≤ P(E ′ ). Then, we need to upper bound the probability of σ A giving incorrect centralization for all edges in S ∪ T .We observe that there are only two situations, that is, no vertices in S that has a neighbor with the same label correctness as itself. See Figure 8 for an illustration. We denote those two possible outcomes constraint on S ∪ T as σ 1 and σ 2 . P(E ′ ) = P({ σ A = σ 1 } ∩ H) + P({ σ A = σ 2 } ∩ H).By the label correctness, we separate V (S) into two disjoint sets: V (S) σ c for the correctly labeled vertices and V (S) σ ic for the incorrectly labeled vertices. The deterministic relationship between σ 1 and σ 2 is: V (S) σ1 ic = V (S) σ2 c . without loss of generality, we assume|V (S) σ1 c | > |V (S) σ1 ic |. Observe that event { σ A = σ 1 } (resp. { σ A = σ 2 }) is equivalent as saying the set of vertices on odd (resp. even) levels are labeled incorrectly (falling in the bad vertex set I ε as defined in Section D). Denote p a,b,s,ε,δ,V := n -V ×D+(a,b,s,ε) + n -εδ(1-o(1)) log n . We can apply Lemma 8,A = σ 1 } ∩ H) ≤ (1 -p a,b,s,ε,δ,|V (S) σ 1 c | )(p a,b,s,ε,δ,|V (S) σ 1 ic | ), P({ σ A = σ 2 } ∩ H) ≤ (1 -p a,b,s,ε,δ,|V (S) σ 1 ic | )(p a,b,s,ε,δ,|V (S) σ 1 c | ), P(E ′ ) ≤ 2(1 -p a,b,s,ε,δ,|V (S) σ 1 c | )(p a,b,s,ε,δ,|V (S) σ 1 ic | ).Consider each chandelier has L branches and each has a M -wire (Assume that M = Θ( log n log logn ) as in condition (3)). Even if we don't know the structure of bulbs, we have |V (S) σ1 ic | = Ω( log n log log n ), because at least half of the vertices on wires should be labeled incorrectly. In this section, we analyze the second moment of similarity score. We expect the variance of Φ ij to be infinitely small in comparison with the squared expectation of true pair's similarity score.Proof of Proposition 5. Recall that S 1 , T 1 are rooted on i and S 2 , T 2 are rooted on j.EQUATIONH,I∈T aut(H)aut(I)S1,S2 ∼ =H,T1,T2 ∼ =I E[A σ A S1 B σ B S2 1 H ]E[A σ A T1 B σ B T2 1 H ] V2 (a) Analyzing V 2 .We first give the upper bound of the latter part. When analyzing with correct centralization, we ignore this part as it is non-negative in the correct centralization case. However, in this case, it is possible to be negative because there can be odd number of edges occurring once and also being incorrectly centralized.After factorizing V 2 ,V 2 =   H∈T aut(H) S1,S2 ∼ =H E[A σ A S1 B σ B S2 1 H ]     I∈T aut(I) T1,T2 ∼ =I E[A σ A T1 B σ B T2 1 H ]   ,we can see that V 2 ≥ 0, and thus we haveVar[Φ σ ij 1 H ] ≤ V 1 for j = π * (i).(b) Analyzing V 11 . The main challenge here is that we do not have the condition that every edge occurs at least twice in the union graph as in the analysis of Regime I. However, we can put union graphs into two categories based on whether every edge is at least 2-decorated or not. We keep the notation of W ij as the collection of decorated union graphs U that are at least 2-decorated and we decompose (72) as followsV 1 = H,I∈T aut(H)aut(I) S1,S2 ∼ =H,T1,T2 ∼ =I E[A σ A S1 B σ B S2 A σ A T1 B σ B T2 1 H ] = U ∈Wij (aut(S 1 )aut(S 2 )aut(T 1 )aut(T 2 )) 1 2 E[A σ A S1 B σ B S2 A σ A T1 B σ B T2 1 H ] V11 + + U / ∈Wij (aut(S 1 )aut(S 2 )aut(T 1 )aut(T 2 )) 1 2 E[A σ A S1 B σ B S2 A σ A T1 B σ B T2 1 H ] V12 . We first show that V 11 /µ 2 = O L 2 ρ 2 ns(p∧q) + L 2 ρ 2(K+M ) |J | .The incorrect centralization affects the upper bound of moments as the following:EQUATIONThe first two equalities follow from definitions. The third inequality holds because of the upper bounds of β e(K ℓm ) ℓ,m from Lemma 14 holds for all σ.Then, the structures of the union graph, alone with the assigned weights are bounded the same as in Section I. This implies thatV11 E[Φ iπ * (i) 1 H ] 2 ≤ O L 2 ρ 2 ns(p∧q) + L 2ρ 2(K+M ) |J | under the same condition as (22) .(c) Analyzing V 12 . To concludeVar[Φ σ ij 1 H ] E[Φ iπ * (i) 1 H ] 2 ≤ V11+V12+V2 E[Φ iπ * (i) 1 H ] 2 = O L 2 ρ 2 ns(p∧q) + L 2 ρ 2(K+M ) |J | , it remains to show V 12 = o L 2 ρ 2 ns(p∧q) + L 2 ρ 2(K+M ) |J | .Lemma 24 gives a even stronger result, because as assumed in Proposition 5, L = o(log n)), givingL 2 ρ 2 ns(p∧q) + L 2 ρ 2(K+M ) |J | ≫ n -ε ′ for all ε ′ > 0.Lemma 24. Under the same conditions as Proposition 5, for some ε ′ > 0,V 12 E[Φ iπ * (i) 1 H ] 2 = o(n -ε ′ ).Proof. For the expectation inside V 1 part, it can be separated as eight sets K ℓm :E[A σ A S1 B σ B S2 A σ A T1 B σ B T2 1 H ] = E   g U g -1 U E[ ℓ∈[2],m∈[2],ℓ+m≥1 e∈K ℓm A σ A ,ℓ e B σ B ,m e | σ * , σ]1 H   ,where g U is the abbreviation for g U (σ + , σ -).Conditioned on σ and σ, approximately centered edges are still independent with each other, | σ * , σ] and thus by enumerating through the products, we haveEQUATIONg -1 U ℓ∈[2],m∈[2],ℓ+m≥1 e∈K ℓm E[A σ A ,ℓ e B σ B ,m e | σ * , σ] ≤ (1 + Θ( log n n )) 4N ρ e(K11) (sp ∧ sq) -1 2 (e(K12)+e(K21))-e(K22) P(E)∆ z/2 , ≤ (1 + o(1))ρ e(K11) (sp ∧ sq) v+k+1-2N P(E)( |a -b| a ∧ b ) z/2 ,where E := {Every 1-decorated edges are centralized incorrectly} ∩ H and z is the number of 1decorated edges, namely, z := e(K 01 ) + e(K 10 ). The second inequality holds because -1 2 (e(K 12 ) + e(K 21 ))e(K 22 ) = (v + k + 1) -2Nz/2.According to Lemma 8 and the assumption that the maximum degree of chandelier is no greater than D, we have for any ε > 0, P(E) ≤ n -D+(a,b,s,ε) z D . Putting things together,E[A σ A S1 B σ B S2 A σ A T1 B σ B T2 1 H ] ≤ (1+o(1))n -D+(a,b,s,ε) z D (sp∧sq) v+k+1-2N ρ e(K11) E[g U (σ + , σ -) | H]. It remains to calculate E[g U (σ + , σ -) | H].Similar as in the calculation in Section I, where we only consider U being at least 2-decorated.Here, we need to generalize it into the case when U has 1-decorated edges. U can be decomposed into a tree with an additional set of edges connecting vertices on the tree. We assume that there are A i i-decorated edges on the tree and B i i-decorated edges in the additional edge set of size e( U )v( U ) + 1, for i ∈ [4] . We apply the Corollary 1 and have that P(X (1,a) = a 1 , X (2,a) = a 2 , X (3,a) = a 3 , X (4,a) = a 4 , X (1,b) = b 1 , X (2,b) = b 2 , X (3,b) = b 3 , X (4,b) = b 4 | H) ≤ (1+o(1)) A1 a1 A2 a2 A3 a3 A4 a4 1 2 A 1 +A 2 +A 3 +A 4, where X (i,a) is the number of i-decorated in-community edges on the tree-part of U and X (i,b) is the number of i-decorated in-community edges among the additional edge set.A i and B i are fixed but summed up to d i for each U . a i (b i ) takes possible values from 0 to A i (B i ), for i ∈ [4] . The number of i-decorated in-community edges is a i + b i , and the number of i-decorated cross-community edges is di -a i -b i = (A i -a i ) + (B i -b i ). E [g U (σ + , σ -) | H] ≤ (1 + o(1)) A1 a1 A2 a2 A3 a3 A4 a4 B1 b1 B2 b2 B3 b3 B4 b4 σ (a1+b1) + σ 2(a2+b2) + σ 2(d2-a2-b2) - σ 3(a3+b3) + σ 3(d3-a3-b3) - × σ 4(a4+b4) + σ 4(d4-a4-b4) - A 1 a 1 A 2 a 2 A 3 a 3 A 4 a 4 1 2 A1+A2+A3+A4 = (1 + o(1)) σ + + σ - 2 A1 σ 2 + + σ 2 - 2 A2 σ 3 + + σ 3 - 2 A3 σ 4 + + σ 4 - 2 A4 × B1 b1=0 σ b1 + σ (B1-b1) - B2 b2=0 σ 2b2 + σ 2(B2-b2) - B3 b3=0 σ 3b3 + σ 3(B3-b3) - B4 b4=0 σ 4b4 + σ 4(B4-b4) - ≤ (1 + o(1)) σ + + σ - 2 d1 σ 2 + + σ 2 - 2 d2 σ 3 + + σ 3 - 2 d3 σ 4 + + σ 4 - 2 d4 2 k+1 ,where the last inequality holds because the upper bound holds with multiplying a binomial coefficientB1 b1 B2 b2 B3 b3 B4 b4 and that i B i = k + 1. By the definition of γ 2 and γ 1 , E [g U (σ + , σ -) | H] ≤ (1 + o(1)) σ + + σ - 2 d1 σ 2d2+3d3+4d4 eff γ d3 1 γ d4 2 2 k+1 .Define γ 0 := ( σ++σ-)/σ eff and we can see that γ 0 < 1. So, we can upper bound ( σ++σ-) d1 as σ d1 eff . Because γ 1 < γ 2 and d 3 + d 4 = e(K 12 ) + e(K 21 ) + e(K 22 ),E [g U (σ + , σ -) | H] ≤ (1 + o(1))σ 4N eff γ e(K12)+e(K21)+e(K22) 2 2 k+1 .In summary,EQUATIONAfter plugging the upper bound on cross-moments to the ratio, it remains to bound the number of different union graph structures and their corresponding weights. In parallel to W ij , we define S ij as the collection of decorated union graphs that have at least one 1-decorated edge. S ij (v, k) denotes those with v + 1 + 1 j̸ =π * i vertices and excess k.V12 E[Φ iπ * (i) 1 H ] 2 ≤ 4N v+k+1=0 U ∈Sij (v,k) aut(H)aut(I)ρ e(K11) (sp ∧ sq) v+k+1-2N γ e(K12)+e(K21)+e(K22) 2 2 k+1 (1 + o(1))n 2N ρ 2N |T | 2 n zD+(a,b,s,ε)/DWe define the ( UL , UM , UN ) partition of decorated union graph as (44) in Section I. We define U L (v L , z, ℓ) as the collection of UL that has v L vertices, ℓ edges belonging to set e(K 11 ), and no more than z 1-decorated edges. We define U M (v M ) as the collection of UM that has v M vertices. We define U N (v N , k) as the collection of UN that has v N vertices and excess k. We also keep the notation of U as the corresponding unlabeled decorated union graph sets. In addition,EQUATIONEQUATIONEQUATIONFrom the above partition,V 12 E[Φ iπ * (i) 1 H ] 2 ≤ 4N v=N 4N -v k+1=0 (sp ∧ sq) v+k+1-2N 2 k+1 z v L ,v M ,v N ℓ ρ ℓ P L (v L , z, ℓ)P M (v M )P L (v N , k) (1 + o(1))n 2N ρ 2N |T | 2 n zD+(a,b,s,ε)/D γ 2(v+k+2)-4N 2 .We show upper bounds for P L (v L , z, ℓ) in Lemma 25, which is2N ℓ=0 ρ ℓ P L (v L , z, ℓ) ≤ (4N ) 2z+1 n v L L(4LM ) 6L |T | 2 ρ 2N ρ -z 2 .The upper bounds for P M and P N trivially follows from Lemma 19 and Lemma 20, with a replacement of 11 to 15 as the possible decorations of each vertex increase by 4 for 1-decoration and a different maximum value of e M , parameterized by v, k, z.P M (v M ) ≤ R 2e M M n v M (15β) (K+M ) 2e M M 1 {e M ≤2N -(v+k+2)+z/2} P N (v N , k) ≤ n v N (15β) v N (15R 4 (v N + 1) 2 ) k+1 1 {v N ≤2(K+M )(2k+2)} .Putting all the pieces together, we haveV 12 E[Φ iπ * (i) 1 H ] 2 ≤ k≥-1 30R 4 (2N + 1) 2 (15β) 4(K+M ) n k+1 × 4N -k-1 v=N R 2 M (15β) 2 K+M M ns(p ∧ q) γ 2 2 2N -v-k-1 × 4N z=1∨(2(v+k+1)-4N )   (4N ) 2 R 1 M (15β) K+M M √ ρn D + (a,b,s,ε) D   z × 2N L(4LM ) 6L .Next, we introduce three types of bulbs. The first type is called effective non-isomorphic bulbs, which is a selection of bulbs that are not isomorphic to each other and always pair with a bulb that are not of the same type. The selection is not unique and we take the largest possible set of bulbs satisfying those rules as the set of effective non-isomorphic bulbs. Fixed the effective bulb set, for bulbs that are isomorphic to those effective non-isomorphic bulbs, we name them as shadow effective bulbs. For the remaining bulbs, we name them as non-effective bulbs. We have the following Claim 2:EQUATION)From definition, there is at most one non-effective bulb and at most one effective non-isomorphic bulb in each pair of bulbs, while two shadow bulbs can pair up.We call those effective non-isomorphic bulbs as effective because when enumerating through the chandelier structures, we let them having the priority of taking any possible structure from J and serving the base of that pair. Shadow effective bulbs are named so because they mirror the structure of effective non-isomorphic bulbs and thus will not increase the union graph richness too much. For non-effective bulbs, we let them take any possible structures with the constrain that there are at most z 1-decorated edges in UL .We denote the number of effective non-isomorphic bulbs as a. For all pairs, we upper bound the number of different non-isomorphic tangled bulbs as following combinatorial factor|J | a b a 2N z/2 (4N ) z 2 ,where |J | a comes from the structure of a effective non-isomorphic bulbs, b a is the upper bound of choosing a effective non-isomorphic bulbs from b bulbs, 2N z/2 is the upper bound on the selection of which edges on effective non-isomorphic bulbs and shadow effective bulbs are overlapped as there are at most 2K (< 2N ) 2-decorated edges on bulbs if all bulbs are perfectly overlapping with one another, and (4N ) z 2 bounds the placement of those remaining 1-decorated edges from the non-effective bulbs as each of them has at most 4N possible vertices to attach to on the union graph.Since wires cannot tangle with bulbs (otherwise, it is not a tree), we bound the possible structures separately. There can be at most 4 wires tangling with each other, from top to bottom. We apply a very loose bound even without using this fact, which is (b -1)!M b-1 . This is because there are at most b wires and we determine the structure of wires on the union graph one by one. When the t-th wire comes in, it can determine which of the t -1 wires to tangle with and the length of overlap, from 0 to M . EQUATION)In the second inequality, we loose the upper bound of t 1 from a to 2L and change the order of summation. In the third inequality, we bound the summation over a and b. Lastly, Proof. Denote all bulbs contained in UL as B 1 , B 2 , . . . , B w . (1) Some of them can be fully overlapped to form a 2-decorated bulbs in the union graph. (2) Some of them can be partly overlapped. (3) And the remaining of them are fully 1-decorated. There cannot be three or more bulbs overlapping with each other thanks to the definition of UL (65) .Each bulb B i contributes to the w( UL ) by aut(B i ) independently from definition (66) and (50) . For any vertex on the bulbs, it will not be at the same orbit as any vertex on the wire, so studying the automorphism of the overlapped bulbs gives a lower bound on the automorphism of the whole decorated graph. Since each bulb occurs in at most one overlapped bulb, to prove the claim, it suffices to examine the relationship between weights and automorphism for each of the three cases aforementioned.For i, j ∈ [w], if bulbs B i is partly overlapping with B j . From Corollary 2, aut(B i )aut(B j ) ≤ aut(B i ∪ B j )(2K) |E(Bi)△E(Bj )| . If B i is fully overlapping with B j , then aut(B i )aut(B j ) = aut(B i ∪ B j ). If B i is fully 1-decorated, then aut(B i ) ≤ aut(B i ).Denote I 1 and I 2 as the collections of index pairs that the corresponding bulbs fall in case (1) or (2) . Denote I 3 as the collection of indices corresponding to the bulbs falling in case (3) . Therefore, w( UL ) ≤ (82)The union graph has at least 2 × (i,j)∈I |E(B i )△E(B j )| 1-decorated edges and we know that UL has at most z 1-decorated edges. Therefore, (i,j)∈I |E(B i )△E(B j )| ≤ z. Substituting this into (82) completes the proof.Claim 2. Let a be the number of effective non-isomorphic bulbs and t 1 be the number of pairs of tangled bulbs that are decorated by a subset of either {S 1 , S 2 } or {T 1 , T 2 }. We haveEQUATION)Proof. For an arbitrary bulb, it occurs at most one time in S 1 , S 2 , T 1 , T 2 each and they are paired up into two sets, a ≥ t1 2 . Assume that there are t ′ non-isomorphic bulbs among the t 1 pairs, they can all be assigned as effective non-isomorphic bulbs. Then, without loss of generality, S 1 , S 2 have at most L -t ′ 2 bulbs unspecified. By assumption, they cannot pair up with each other, so every one bulb from S 1 , S 2 remaining will pair up with another bulb from T 1 , T 2 . Therefore, the remaining bulbs have at most L -t ′ 2 effective non-isomorphic bulbs. Together, we have a ≤ t ′ + (L -t ′ 2 ) ≤ L + t1 2 , as t ′ ≤ t 1 .M.1 Proof of the Proposition Proof of Proposition 6. Recall that S 1 and T 1 are rooted on i, S 2 and T 2 are rooted on j. The minimum value of k is -2 when the union graph consists of two disconnected trees, S 1 ∪ T 1 and S 2 ∪ T 2 . We use the same notation for different parts of the variance as in Section L.Var[Φ σ ij 1 H ] = H,I∈Taut(H)aut(I) S1(i),S2(i) ∼ =H,T1(j),T2(j) ∼ =Iσ A S1 B σ B S2 1 H , A σ A T1 B σ B T2 1 H ) = U ∈Wij(aut(S 1 )aut(S 2 )aut(T 1 )aut(T 2 ))1 2 E[A σ A S1 B σ B S2 A σ A T1 B σ B T2 1 H ] V11 + U / ∈Wij(aut(S 1 )aut(S 2 )aut(T 1 )aut(T 2 ))1 2 E[A σ A S1 B σ B S2 A σ A T1 B σ B T2 1 H ] V12 - H,I∈Taut(H)aut(I)EQUATION)Since V 2 ≥ 0, it suffices to bound the first two summations. The same argument in Section L to bound the V 11 for true pairs works for this case with an additional fluctuation coming from using Lemma 14 to bound the cross moments rather than Lemma 13. We haveV 11 /µ 2 ≤ (1 + Θ( log n n )) 4N Var[Φ σ ij 1 H ] µ 2 | sD+(a,b)>1 = O( 1 |T |ρ 2N )under conditions (23) . The additional fluctuation comes from the cross moment bounds.Lemma 26 shows that V 12 /µ 2 = o( 1|T |ρ 2N ). In summary, we have T2 1 H ] as derived in (74), with replacing k + 1 to k + 2 everywhere as from definition v is the number of vertices except for i and j. When j ̸ = π * (i), the minimum value of j starts from -2 when the union graph consists of two disjoint trees. Var[Φ σ ij 1 H ] E[Φ iπ * (i)1 H ] 2 = O( 1 |T |ρ 2N ).After plugging the upper bound on cross-moments to the ratio, it remains to bound the number of different union graph structures and their corresponding weights. For a specific decorated graph U , we denote t 1 (resp. t 2 ) as the number of different edges vetween S 1 and T 2 (resp. S 2 and T 2 ). There are z = 2(t 1 + t 2 ) 1-decorated edges and the remaining edges are in set K 02 or K 20 . We write out F ij under the summation over t 1 and t 2 . (ignoring the constraint that T 1 ∼ = T 2 ∼ = I for some chandelier I having less automorphism number than H). Altogether, (b) Case k > -2. In general, we define UL , UM , and UN partition the same as (64) and (65) . We also define the weights of each part the same as (66), (67) , and (68) . We define P L (v L , z) = U ∈U L (v L ,z) w( U ). The definition of P M (v M ) and P N (v N , k) follow. All union graph class should not have more than z 1-decorated edges, but specifically we only need this constraint for UL .V 12 E[Φ iπ * (i) 1 H ] 2|S ij (v ≥ 2N, H, I)| ≤ n 2N aut(H) 2Note that e(K 12 ) + e(K 21 ) + e(K 22 ) ≤ 4N -2(v + k + 1) + z,V 12 | k>-2 ≤ σ 4N eff 4N v=N 4N -v k+2=1 4N z=1 γ 4N -2(v+k+2) 2 2 k+2 (sp ∧ sq) v-2N +k+2 × v L ,v M ,v N P L (v L , z)P M (v M )P L (v N , k)γ 2 n D+(a,b,s,ε)/D z .We show the upper bound for UL part in Lemma 27. The upper bound for P M and P N trivially follows from Lemma 22 and Lemma 23 as they do not use any assumption on edges are all at least 2-decorated, except for the number 11, the possible ways of decoration. So, we change 11 to 15 and then every thing follows. When z ̸ = 0, e M as defined before in an arbitrary UM has maximum value 2N -(v + k + 2)z/2 (same holds for e N , e L but we do not need to use them in our bound). In overlapping with B t , then aut(B t )aut(T r ) ≤ aut(B t ∪ T r )(2K) |E(B4)△E(Tr)| from Corollary 2. Note that in this case, full overlap is not possible because this invader branch spends at least one edge connecting from j to i. The third case can be considered as a generalized version of the first case.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [NA] Justification: This paper does not include experiments.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: This research conforms with the NeurIPS Code of Ethics in every respect.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] Justification: We discuss both the potential positive and negative societal impacts of this work, especially graph matching, in Section 2.• Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.38th Conference on Neural Information Processing Systems (NeurIPS 2024).This constant captures the base of the exponential growth of unlabeled rooted trees: the total number of unlabeled rooted trees with N vertices is (α + o(1)) -N .Note that S1 and T1 are rooted at i, while S2 and T2 are rooted at j. For e = (u, v) ∈ E(S1), we say it occurs in T1 if e ∈ E(T1) and it occurs in S2 (resp. T2) if (σ * (u), σ * (v)) ∈ E(S2) (resp. T2).See Section K for illustrations and more discussions on approximately centralized adjacency matrices.For arbitrarily small constant ε > 0, there exists n large enough, such that ρ 2 ≥ α + ε if and only if s 2 ≥ α + ε.Note that S1 and T1 are rooted at i, while S2 and T2 are rooted at j. For e = (u, v) ∈ E(S1), we say it occurs in T1 if e ∈ E(T1) and it occurs in S2 (resp. T2) if (σ * (u), σ * (v)) ∈ E(S2) (resp. T2).Relevant seeded graph matching algorithms also occur in[69,5,41].By a product over all overlapping bulbs, we have w( UL ) ≤ aut( UL )(2K) z because the total number of edges in the difference sets of overlapping bulbs are upper bounded by z, the number of 1-decorated edges, and the automorphism number of UL is greater than the product of automorphism number of all bulbs. 
 
 Appendix:  


Decision: The problem of graph alignment -- ie. of matching the vertices of two random graphs with correlated edges -- has received significant attention in the literature. The present paper considers the case of correlated stochastic block models (cSBM) with two communities. The main result is to show how a certain estimator from previous work, which is based on on counting "signed chandeliers" in the graph, achieves good performance, and (most importantly) does so in polynomial time. The paper adds to recent information theoretic results for this model, and also to algorithmic results for the simpler Erd\H{o}s-Rényi case. At least in some cases, it reaches the natural information theoretic threshold below which alignment becomes (in some sense) impossible. 

Reviewers' scores were 5, 6, 6 and 7. They all seem to agree that this is a technically challenging paper, which solves an interesting problem. Differences in scores seem to reflect differing views of the relevance of the paper. My own opinion is that this paper contains important ideas required to deal with the challenge brought about by the fact that edge probabilities take two values. Moreover, the problem considered is of broad interest, albeit the contributions here are mostly theoretical. Overall, I believe the paper should appear in NeurIPS.

Reviews: review: paper_summary: paper_summary: The paper under revision addresses the problem of graph matching and community recovery in correlated stochastic block models (SBM) with two balanced communities. In particular, it studies the regime where the vertices of the parent graph have a logarithmic average degree, considering the within-community edge probability to be $a\frac{\log n}{n}$ and between-community edge probability to be $b\frac{\log n}{n}$. The edge correlation parameter is equal to $s$.

Regarding graph matching, they proved in Theorem 1 the existence of a polynomial-time algorithm that can achieve both almost exact and exact matching. Almost exact matching is achieved when the square of the edge correlation is greater than Otter’s tree counting constant ($s^2 > \alpha$). To obtain exact matching, an additional condition is necessary, namely $s^2(a+b)/2 > 1$. This result extends known results on almost exact and exact matching for correlated Erd\H{o}s--Rényi graphs obtained in Mao et al. (2023). It corroborates the previous work by Racz & Sridhar (2021), which determined that exact matching in correlated SBM is only achieved when $s^2(a+b)/2 > 1$.

In the context of community detection, Theorem 2 of the manuscript states that exact community recovery in correlated SBM is achieved by a polynomial-time algorithm when \( s^2 > \alpha \), and it satisfies the information-theoretic threshold for community recovery in correlated SBM established by Racz & Sridhar (2021). The authors provide a brief description of the polynomial-time algorithm in Section 5 and a more detailed explanation in Appendix C. In this way, one of the main contributions of this work is to propose an efficient algorithm for graph matching for correlated SBM.

In terms of the algorithm itself, it is structured by first applying a community detection algorithm proposed by Mossel et al. (2015) to each of the graphs to ensure exact recovery of the communities. Then, an adaptation of the algorithm proposed by Mao et al. (2023) for correlated Erdős–Rényi graphs, based on rooted trees known as chandeliers, is applied.

The manuscript combines established ideas from previous works, specifically integrating the concepts from Racz & Sridhar (2021) and Mao et al. (2023) to develop a polynomial-time algorithm for graph matching in correlated SBM. The manuscript is well-structured and provides detailed explanations of the algorithms, results and their connections to related works.

References:

Mao, Cheng, Wu, Yihong, Xu, Jiaming, & Yu, Sophie H. 2023. Random graph matching
at Otter’s threshold via counting chandeliers. Pages 1345–1356 of: Proceedings of the
55th Annual ACM Symposium on Theory of Computing.

Mossel, Elchanan, Neeman, Joe, & Sly, Allan. 2015. Consistency thresholds for the planted
bisection model. Pages 69–75 of: Proceedings of the forty-seventh annual ACM
symposium on Theory of computing.

Racz, Miklos, & Sridhar, Anirudh. 2021. Correlated stochastic block models: Exact graph
matching with applications to recovering communities. Advances in Neural Information
Processing Systems, 34, 22259–22273.
strength_weakness: strength_weakness: X
questions: questions: X
limitations: limitations: X
paper_summary: paper_summary: The author(s) consider graph matching and community recovery on correlated stochastic block models. In the stochastic block model (SBM) the algorithm's input is a graph G generated by first partitioning vertices into two equal size clusters and then adding every intra-cluster edge with probability p and every inter-cluster edge with probability q, independently. In the correlated version onG_ f irst samples a graph G from the SBM, and then takes two independent edge samplings of G, referred to as G_1 and G_2 -- these are the input of the algorithm (with randomly permuted vertices).  Thus, the correlated SBM setting generalizes the more basic correlated Erdos-Renyi setting, in which there is only one community (or, one can think of p=q). In the latter setting the objective is graph matching. In the more general setting of correlated SBMs the objective function is community recovery, but graph matching is a natural sub-objective along the way, as it is quite reasonable to match G_1 to G_2 first, and then use the improved edge density for community detection.

A strong recent result of Mao et al (STOC'23) established a tight threshold for reconstruction in the correlated Erdos-Renyi setting, and provided a polynomial time algorithm in the regime where  matching is possible. The present paper basically ports the techiques of Mao et al from the correlated Erdos-Renyi to the correlated SBM setting. Specifically, they develop technical tools for using Chandelier counts, which underly the result of Mao et al, in the SBM setting.
strength_weakness: strength_weakness: There is a number of lower level technical challenges that stem from the need of extending an Erdos-Renyi result to the SBM setting, but the most conceptual one appears to be the fact that when using partial matching results to perform community recovery on the union of the two graphs, one needs to handle errors that come from the non-exact matching. This, while definitely an interesting technical challenge, does not seem sufficiently compelling as a conceptual one.
questions: questions: None.
limitations: limitations: None.
paper_summary: paper_summary: The paper extends graph matching from correlated Erdos Reyni graphs to correlated SBM graphs. 
To do so, they apply the recent breakthrough work of Mao, Wu, Xu, and Yu (STOC 2023) for ER graphs, which are based on counting a special kind of graph called chandeliers. A prerequisite for this method is to be able to center the graph. The primary challenge is that SBM graphs a graph cannot be easily centered (as the intra and inter-community edges have different means). To this end, they first apply a weak-community recovery approach to get a rough estimate of the communities in the different graphs. Then, they use this information to get a match. 

As an application, they show efficient community recovery given multiple correlated SBM graphs in a regime where recovery is information-theoretically impossible given only one graph (This also shows that the approach is interesting, as they use a rough community recovery on individual graphs to obtain a matching, which in turn leads to a complete community recovery using the graphs collectively). This is the first efficient algorithm for this problem.
strength_weakness: strength_weakness: 1. The definition of correlated SBM seems a special case of the usual definition of correlated graphs in the ER model. Specifically, the authors assume that the non-edges of the first graph also remain non-edges in the second graph. 

2. The paper does not contain any simulation results. Implementing this algorithm and applying it to SBM graphs should not be hard.
questions: questions: It would be great if the authors could comment on the aforementioned weaknesses.
limitations: limitations: The authors have adequately addressed the limitations.
paper_summary: paper_summary: The text presents progress in solving learning conditions within correlated stochastic block models with two balanced communities. The main result is the creation of the first efficient algorithm for graph matching. This algorithm works well when the average degree is logarithmic in the number of vertices and can accurately match nearly all vertices with high probability if the edge correlation parameter $ s $ satisfies $ s^2 \geq \alpha + \epsilon$, with $\alpha $ being Otter's tree-counting constant. The algorithm is extended to achieve exact graph matching, solving an open problem posed by Rácz and Sridhar; 2021. This new algorithm generalizes recent work by Mao, Wu, Xu, and Yu (STOC 2023), which relies on centered subgraph counts of structures called chandeliers. A key challenge addressed is managing estimation errors since the latent community partition cannot be perfectly recovered from a single graph in certain parameter regimes. The findings also lead to an efficient algorithm for exact community recovery using multiple correlated graphs, even in cases where it is impossible with just a single graph.
strength_weakness: strength_weakness: The paper is highly theoretical and, as such, most limitations are associated with this. For instance, it does not incorporate simulations as a sanity check of the proofs which could be useful to illustrate not only the usefulness of the theorems for graph matching but also the assumptions.
A minor weakness in this regard is that although the introduction indicates the assumptions for which the framework is developed, e.g., the level of sparsity and logarithmic average degree, it could be useful to discuss the implications on highly dense graphs when the parameters are the complement of the SBM parameters p,q.
questions: questions: How differentiated the SBM model has to be from an ER model to effectively achieve exact and almost exact matching if $s^2>\alpha$?
limitations: limitations: The discussion section indicates some of the limitations of the work including the lack of runtime analysis, and that the condition $s^2>\alpha$ is believed to be necessary but that is not proven in this paper.
paper_summary: paper_summary: In this paper, the authors tackle two related problems: graph matching and community recovery of correlated balanced SBM under the logarithmic average degree regime. The authors extend proofs from the ER model for similar tasks and overcome the difficulties in the proofs raised by working with the SBM model.
The main two theorems are: (1) for correlation levels above a certain threshold, almost exact and exact graph matching are possible, and (2), again, for correlation levels above a certain threshold, community recovery is possible.
strength_weakness: strength_weakness: The weakness I see is not of the paper itself but more of the paper-conference combination. The strengths of the paper, as stated above, are the two theoretical results. But the 9-page paper ONLY includes the statements of these results and some ideas about the proofs. I found it very very nice, well motivated, etc. But I cannot review a ~70-page paper in all detail like it deserves. Not for a conference. I can see this as a beatuiful journal paper, where a reviewer can spend some months to study the paper like it deserves.
questions: questions: There are some verbs missing in several sentences, and other grammatical or spelling errors (for instance in Erdos). I suggest a profound check on the writing.
I think the other comment (about the suitability of this paper for a conference) is not something the authors could change in the rebuttal phase.
limitations: limitations: The authors claim to address the limitations in Section 7. However, this section is more of a "future work" section (as it is named). It's true that every possible line of future work is a limitation of the present paper, but it's not presented in this way, and no other limitations are discussed.

Comments: comment: Thank you for the answer.
I really hope to see this paper published somewhere :)
Thank you for the response.
I thank the authors for their response, and shall keep my score unchanged. Best wishes.