High-Dimensional Procrustes Matching via Tree Counts

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

High-Dimensional Procrustes Matching via Tree Counts

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

machine learning, deep learning, neural networks

High-Dimensional Procrustes Matching via Tree Counts Xiaochun (Nora) Niu

Tselil Schramm

Jiaming Xu∗

Abstract

arXiv:2607.08538v1 [stat.ML] 9 Jul 2026

Suppose we observe two sets of n Gaussian vectors in Rd , with the promise that, after applying a permutation of [n] and a rotation of Rd , the two sets are ρ-correlated. The Procrustes matching problem asks us to recover the unknown permutation of [n] that aligns the two sets. The problem is well-studied in the low-dimensional regime d = O(log n), but the high-dimensional regime d ≫ log n has remained largely uncharted: prior matching guarantees require nearly perfect correlation ρ = 1 − o(1), even for information-theoretic recovery. Our main result is a polynomial-time algorithm for exact recovery at constant correlation. The algorithm works by computing and comparing weighted counts of a specially chosen family of “wide” √ trees. So long as d ≥ polylog(n), the algorithm succeeds with high probability for any ρ2 > α, where α ≈ 0.338 is Otter’s tree-counting constant. We complement this algorithmic result with an improved information-theoretic guarantee, p showing that exact recovery is possible when ρ2 ≳ max{log n/d, log n/n}. √ We also carry out a low-degree advantage calculation, which suggests that the condition ρ2 > α is necessary for any tree-counting algorithm.

∗

X. Niu and J. Xu are with The Fuqua School of Business, Duke University, Durham NC, USA, {xiaochun.niu,jx77}@duke.edu. T. Schramm is with the Department of Statistics, Stanford University, Stanford, CA, USA, [email protected].

Contents 1 Introduction 1.1 Key Challenges and New Ideas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Notation and Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 4 6

2 Main Results 2.1 Matching Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Wide Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Statistical Properties of Our Similarity Scores . . . . . . . . . . . . . . . . . . . . . . 2.4 Performance Guarantees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Information-Theoretic Thresholds and Computational Gaps . . . . . . . . . . . . . .

6 6 7 8 11 12

3 Statistical Guarantees

4 Joint Moments Calculation 15 4.1 Joint Moments of Gaussian Random Variables . . . . . . . . . . . . . . . . . . . . . . 15 4.2 Weingarten Calculus for Orthogonal Groups. . . . . . . . . . . . . . . . . . . . . . . . 17 4.3 Joint Moments Calculation via Alternating Circuit Decompositions . . . . . . . . . . 19 5 Mean Calculation 21 5.1 True Pairs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 5.2 False Pairs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 6 Variance Calculation 25 6.1 Decomposition of Decorated Union Graphs . . . . . . . . . . . . . . . . . . . . . . . 27 6.2 Proof of Proposition 3.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 6.3 Bounding the Grafted Part . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 6.3.1 Counting the Grafted Part . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 6.4 Bounding the Fully Overlapping Part . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 7 Polynomial-Time Approximation via Color Coding

8 From Almost Exact to Exact Recovery

9 Quadratic Assignment Estimator 48 9.1 Signal Lower Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 9.2 Noise Upper Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 10 Limits of Tree Polynomials via Low-Degree Analysis 54 10.1 Graph Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 10.2 Proof of Theorem 10.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

Introduction

Aligning high-dimensional datasets is a fundamental problem in modern statistics and machine learning. It arises in tasks such as aligning word embeddings across languages [LCR+ 18], matching entities across networks [FLM+ 20], integrating biological datasets across experiments [SBH+ 19], and registering point clouds or shapes in computer vision [ZSN+ 17]. In these settings, two datasets may encode the same underlying objects, but their correspondence is obscured by measurement noise, relabeling, and latent geometric transformations. A central question is therefore whether the unknown correspondence can be recovered efficiently, how to design algorithms achieving such recovery, and how the recovery guarantees depend on the ambient dimension and signal strength. We study an idealized version of this question called the Procrustes matching problem: we observe two datasets {Xi }ni=1 , {Yi }ni=1 ⊂ Rd of correlated Gaussian random vectors whose correspondence is obscured by an unknown permutation and an unknown orthogonal transformation. Specifically, for each data point i ∈ [n], i.i.d.

Xi ∼ N (0, Id ), Yi = ρQXπ(i) +

p 1 − ρ 2 Zi ,

(1.1)

where π is an unknown permutation drawn uniformly at random from the set of all permutations on [n], Q ∼ Od is an unknown orthogonal transformation drawn from the Haar measure on d × d i.i.d.

orthogonal matrices, ρ ∈ [0, 1] is the correlation parameter, and Zi ∼ N (0, Id ) is independent noise. Given only the matrices X = (X1⊤ ; · · · ; Xn⊤ ) and Y = (Y1⊤ ; · · · ; Yn⊤ ), our goal is to recover the hidden permutation π and align the two datasets. When the permutation π is known, the Procrustes matching problem simplifies to the classical orthogonal Procrustes problem, which admits a closed-form solution via singular value decomposition [Sch66]. On the other hand, when the orthogonal transformation Q is known, recovering the hidden permutation becomes a linear assignment problem on correlated Gaussian observations, which can be solved in polynomial time, for example, in cubic time using the celebrated Hungarian algorithm [Kuh55]. Recovery thresholds for this linear assignment problem have been characterized in a recent line of work [DCKG19, DCK19, KNW22, WWXY22]. In the Procrustes matching problem (1.1), both the permutation π and the orthogonal transformation Q are unknown. By a simple observation, Procrustes matching is equivalent to the geometric graph alignment problem when one assumes a linear kernel : there, only Gram matrices A = XX ⊤ and B = Y Y ⊤ are observed and treated as weighted adjacency matrices. Indeed, let A1/2 ≜ U Λ1/2 based on the eigenvalue decomposition A = U ΛU ⊤ and similarly for B 1/2 . Then d (A1/2 , B 1/2 Q′ ) = (X, Y ) for an independent Q′ ∼ Od . Hence, statistical and algorithmic guarantees for one formulation translate directly to the other. The Procrustes matching problem has been extensively studied (under a few different names) in the literature [RCB97, MDK+ 16, DL17, GJB19, WWXY22, GL24, EGMM24, Li26]. In the low-dimensional regime d = o(log n), [WWXY22] established sharp information-theoretic thresholds for exact matching (ρ2 = 1 − o(n−4/d )) and almost exact matching (ρ2 = 1 − o(n−2/d )). Subsequently, [GL24] proved that a spectral method, namely the classical Umeyama algorithm [Ume88], achieves these thresholds up to polynomial factors in d, in polynomial time. However, a substantial gap remains in our understanding of the high-dimensional regime d ≫ log n. The state-of-the-art results in [EGMM24], summarized in Table 1, show that almost exact recovery can be achieved informationtheoretically when the correlation ρ tends to one. Computationally, almost exact recovery was known to be achievable in polynomial time only when the correlation ρ = 1 − n−c for some constant c > 0. 3

Whether matching can be achieved efficiently, or even information-theoretically, under constant correlation in the high-dimensional regime has remained a widely open problem. In this work, we address this open problem, showing that exact matching is achievable in polynomial time under constant correlation when d ≥ polylog(n). Theorem 1.1. Suppose that d ≥ polylog(n). There exists a polynomial-time estimator π b that correctly matches all the datapoints with high probability whenever √ (1.2) ρ2 > α, where α ≈ 0.338 is Otter’s tree-counting constant [Ott48]. We complement these algorithmic results with improved information-theoretic guarantees that allow vanishing √ correlations, matching the impossibility result of [WWXY22] up to constant factors when d ≪ n log n. Table 1 summarizes the known statistical and computational guarantees in the high-dimensional regime.

[EGMM24] This work

Information-theoretic

Computational

ρ2 ≥ 1 − o(1) r log n log n 2 ρ ≳ max , d n

ρ2 ≥ 1 − n−c √ ρ2 > α

Table 1: Comparison of sufficient conditions for matching when d ≥ poly(log n). Our results are for exact matching, whereas the results in [EGMM24] are for the weaker notion of almost exact matching and further require d ≪ n.

Otter’s constant appears in (1.2) because our algorithm is based on counting trees. One may compare to the problem of matching correlated Erdős-Rényi graphs [MWXY25], where tree-counting √ based estimators achieve efficient recovery once the graph correlation exceeds α. The Wishart matrices XX ⊤ and Y Y ⊤ in our setting behave like correlated Gaussian matrices with correlation √ ρ2 when d is large.1 From this perspective, we may view ρ2 > α as the Wishart analogue of the condition for correlated Erdős-Rényi graph matching. Despite this connection, our setting is fundamentally different from correlated Erdős-Rényi graph matching, as we discuss below.

1.1

Key Challenges and New Ideas

The key defining feature of the Procrustes matching problem (1.1) is the presence of an unknown rotation matrix Q in addition to the unknown matching π. Most existing algorithmic approaches circumvent the unknown rotation Q by matching through Gram matrices A = XX ⊤ and B = Y Y ⊤ . These include, for instance, spectral methods such as Umeyama [Ume88] or GRAMPA [FMWX23], which align the eigenvectors of A and B [WWXY22, GL24], as well as convex relaxations of the quadratic assignment problem minΠ ∥ΠAΠ⊤ −B∥2F [GJB19, EGMM24]. However, existing algorithms either work only in the low-dimensional regime d = O(log n) or require nearly perfect correlation ρ = 1 − n−c for some constant c > 0. Motivated by the recent advances in graph matching [BCL+ 19, MWXY25, CR24, CDGL26], a promising approach is to construct similarity scores by counting a certain family of subgraphs in The total variation distance between the distribution of the off-diagonals of the Wishart matrix XX ⊤ and their iid Gaussian counterpart converges to zero if and only if d ≫ n3 [JL15, BG18]; our results cover significantly smaller d as well, but we still find the analogy useful. 1

weighted graphs defined by A and B. The success of this approach crucially relies on the counts of different subgraphs being only weakly correlated, so that they can be aggregated into robust signatures capable of withstanding small constant correlation. However, when A = XX ⊤ and B = Y Y ⊤ are low-rank, there is excessive correlation among different subgraph counts. To see this, k consider the k-walk count rooted at vertex i, that is, e⊤ i A 1, for different lengths k. When d ≪ n, all d p nonzero eigenvalues of A, denoted by λℓ ’s, concentrate around n and moreover λkℓ ≈ nk when k k−1 e⊤ A1.2 In other words, the k-walk counts essentially collapse k ≪ n/d. Therefore, e⊤ i A 1≈n i to degree counts up to scaling, and are therefore highly correlated across different k. This motivates us to depart from this conventional Gram-matrix paradigm and match directly using the data matrices X and Y . A major difficulty immediately arises: unlike in correlated random graph matching, correctly matched edges do not themselves induce positive correlation. Indeed, if a single edge (π(u), a) in X is matched to the edge (u, b) in Y , even though the endpoint u has been correctly matched, we still have EXπ(u)a Yub = ρEQab = 0 because of the random rotation. The key observation, however, is that correlation reappears when pairs of edges sharing a node in [d] are matched together. Namely, matching a pair of edges (π(u), a), (π(v), a) in X with another pair of edges (u, b), (v, b) in Y yields EXπ(u)a Xπ(v)a Yub Yvb = ρ2 EQ2ab = ρ2 /d. This allows us to extract the desired correlation from corresponding subgraph counts in X and Y , despite the presence of the unknown rotation Q. We therefore construct signature vectors by counting carefully chosen families of rooted subgraphs in the weighted bipartite graphs defined by X and Y , designed so that edge pairs can be matched across the two graphs. We then define similarity scores through suitably weighted inner products of these signatures and recover the matching based on these scores. The main analytical difficulty, however, is that the precise correlation structure among these subgraph counts depends on higher-order moments of the rotation matrix Q. To control these correlations, we use Weingarten calculus [Mat13, CM17] to evaluate and bound the correlations. This requires a delicate analysis of circuit decompositions in unions of subgraph copies. In addition, to simplify the correlation structure and suppress undesired correlations among distinct subgraph counts, we crucially constrain the degree of every node in [d] to be exactly two.3 Finally, our signature is comprised of counts of a specific family of “wide” trees, consisting of many non-isomorphic small branches sprouting from a high-degree common root. This “wide” structure plays a crucial role in controlling the undesired correlations among different tree counts. Moreover, despite having size Θ(log n), these trees can be counted sufficiently accurately in polynomial time using the color-coding method [AYZ95, ADH+ 08]. A number of recent works in high-dimensional statistics have used a combination of color-coding and tree-counting to push algorithmic limits, for example in stochastic block models [HS17, CR24, CDGL26] and matching correlated Erdős-Rényi random graphs [MRT23]. Each setting calls for a tailored tree structure. We draw inspiration from these works. In our setting, the bipartite graphs X, Y are highly imbalanced in the regime d = polylog(n) ≪ n, which necessitates the use of “wide” trees with very large root degrees, whereas the chandelier trees in [MWXY25], for instance, are “thin” and “long”. p More precisely, by standard matrix concentration inequality, λℓ = n(1 + δℓ ) with δℓ = Op ( d/n), so that P d k k λkℓ = nk (1 + O(kδi )). Therefore, by letting cℓ = ⟨ei , uℓ ⟩ ⟨uℓ , 1⟩, we have e⊤ i A 1 = n ℓ=1 (1 + O(kδi ))cℓ = k Pd n c + O (kd/n) , where the last equality follows because c ’s are approximately i.i.d. N (0, 1/n). p ℓ ℓ=1 ℓ 2

The degree-2 constraint can be understood from the perspective of decorrelating walk counts. Indeed, the excessive correlations among walk counts based on the Gram matrix A = XX ⊤ arise largely from walks that repeatedly revisit the same d-node, thereby creating high-degree nodes. By imposing the degree-2 constraint on d-nodes, we eliminate precisely these highly correlated contributions.

1.2

Notation and Organization

We write [n] = {1, . . . , n} and let Sn denote the set of permutations of [n]. For graphs G and H, we write G ∼ = H if G and H are isomorphic. For a bipartite graph G on [n] × [d], we write Vn (G) and Vd (G) for the vertices of G in [n] and [d], respectively. In all multigraphs, parallel edges incident to the same pair of vertices are treated as distinct. Unless otherwise specified, the union of two multigraphs retains all parallel edges. The rest of the paper is organized as follows. Section 2 presents our tree-counting matching algorithm, its performance guarantees, and the information-theoretic recovery guarantees. Section 3 establishes the statistical guarantees of similarity scores derived from the tree counts. Section 4 derives the joint moment formula via Weingarten calculus. Sections 5 and 6 then prove the mean separation and variance bounds stated in Section 3. Section 7 shows how to approximately compute the similarity scores in polynomial time via color coding. Section 8 boosts the almost exact recovery to exact recovery using a seeded matching algorithm. Section 9 establishes the information-theoretic recovery guarantees by analyzing the quadratic assignment estimator. Finally, Section 10 applies the low-degree polynomial framework to justify our focus on the particular tree design.

Main Results

In this section, we introduce our matching algorithm and present its main performance guarantees.

2.1

Matching Algorithm

Our algorithmic approach is as follows: we assign a vector-valued polynomial signature to each datapoint, compute similarity scores between signatures of datapoints in X and Y , and then match datapoints whose similarity scores are sufficiently large. We first define the polynomial features used in the signatures. We represent monomials in the entries of X using bipartite multigraphs. Let G = (V (G), E(G)) be a bipartite multigraph with vertex set V (G) ⊂ [n] ∪ [d] and edge multiset E(G) ⊂ [n] × [d]. We define the monomial Y XG ≜ Xua . (u,a)∈E(G)

Let G be an unlabeled bipartite graph with one special node that we designate as the “root.” For i ∈ [n], we consider all bipartite graphs rooted at i and isomorphic to G, and define the polynomial X labelG (X, i) = X G1 . (2.1) G1 ∼ =G root(G1 )=i

For example, when G is a single edge rooted at a node in [n], then labelG (X, i) is the ith row sum. Any family G of rooted bipartite graphs assigns a signature vector to each datapoint: signature(Xi ) = (labelG (X, i) : G ∈ G), and similarly for Yj . We assign a similarity score to each pair of datapoints using the inner product of their signatures: X scoreGij = ⟨signature(Xi ), signature(Yj )⟩G = aut(G) · labelG (X, i) · labelG (Y, j), (2.2) G∈G

where aut(G) denotes the number of root-fixing automorphisms of G. The matching rule is then straightforward: we match a datapoint from X with a datapoint from Y whenever their similarity score is sufficiently large. The procedure is summarized as Algorithm 1. Algorithm 1: Procrustes matching via counting trees Input: Data matrices X and Y , a family of rooted bipartite graphs G, and a threshold τ . Output: π b : I → [n]. 1 for each G ∈ G and each i ∈ [n] do 2 Compute labelG (X, i) and labelG (Y, i) as given by (2.1). 3 for each pair (i, j) ∈ [n] × [n] do

Compute the similarity score between Xi and Yj as given by (2.2).

5 for each i ∈ [n] do

If there exists a unique j ∈ [n] such that scoreij ≥ τ , let π b(i) = j and include i in set I.

The performance of this algorithm depends critically on the choice of the graph family G. We next describe our choice of G.

2.2

Wide Trees

Our family G will consist of rooted, bipartite trees in which every node in [d] has degree 2. Furthermore, we will require that the trees be “wide,” in the sense that the degree of the root is quite large relative to the size of the tree. We impose these constraints because of computational and analytical considerations, as we now explain. The construction of the graph family is guided by a few competing requirements: first, the signatures should be (approximately) computable in polynomial time. This is the requirement that leads us to consider trees; indeed, if G is a tree, the color-coding technique [AYZ95, ADH+ 08] can be used to compute labelG (X, i) more efficiently. The other two requirements are statistical: the family must be sufficiently rich to create a large mean separation between true (j = π(i)) and false (j ̸= π(i)) pairs, and the variance of the similarity scores should be well controlled. To ensure that these conditions hold, it will be useful to consider wide trees whose nodes in [d] have bounded degree. Each tree in our family will have a root with many incident subtrees or “branches” of equal size, chosen from the following branch family J . We recall a classical result in combinatorics: the number of unlabeled trees with k edges is (α + o(1))−k as k → ∞, where α ≈ 0.338 is Otter’s constant [Ott48]. Moreover, [OW22] shows that most such trees have at most exponentially many automorphisms: there exists an absolute constant C such that the number of trees with k edges and at most exp(Ck) automorphisms is still (α + o(1))−k . Fix such a constant C. Definition 2.1 (Branch family J ). Each J ∈ J is a rooted bipartite simple tree with nodes in [n] (the n-nodes) and [d] (the d-nodes). We begin with a rooted tree on n-nodes with M edges whose root has degree one and whose automorphism group has size at most exp(CM ), where C is the constant fixed above. We then subdivide each edge (u, v) of the tree into two edges, (u, a) and (v, a), by inserting a d-node a between u and v. By construction, each J contains 2M edges, and |J | = (α + o(1))−M . The trees in J will serve as the branches of our final tree family. 7

Definition 2.2 (Tree family T ). Each tree T ∈ T is constructed by taking D pairwise non-isomorphic branches from J and merging their roots into a single common root. Throughout the paper, we write scoreij for scoreTij , the similarity score in (2.2) under T . Recall that D is the root degree and 2M is the number of edges per branch. Let K = DM . Then each T has 2K edges, K + 1 n-nodes (including the root), and K d-nodes, each of degree 2. Figure 1 illustrates an example of such a tree. root i n-node d-node

...

D non-isomorphic branches from J

Figure 1: Schematic illustration of a tree in T . Each dashed triangle represents the descendant subtree of a branch.

We will later choose the parameters K and D carefully to meet our statistical requirements, taking K = Θ(log n) and D = Θ(K/ log K). The resulting trees are wide, with large root degree and small branch size (M = Θ(log K)). These choices will be explained in Section 2.3.

2.3

Statistical Properties of Our Similarity Scores

Here we elaborate further on the statistical properties of our similarity scores. To keep notation manageable, assume from here on out (without loss of generality) that π = id is the identity permutation. We also at times neglect to account for the fact that the n-node and d-node labels within each labeled T are distinct, leaving that accounting for the formal proofs. Mean separation. We first study the mean of scoreij for true and false pairs. By definition, X X X E [scoreij ] = aut(T ) · E [labelT (X, i) · labelT (Y, j)] = aut(T ) E X T1 Y T2 . T ∈T

T ∈T

T1 ,T2 ∼ =T root(T1 )=i root(T2 )=j

Thus, the problem reduces to understanding the joint moments E[X T1 Y T2 ]. Intuitively, these joint moments are largest when the n-nodes of T1 and T2 are labeled identically. Here we will only briefly explain, deferring a full analysis to Section 4. Recall that the trees T ∈ T were constructed by first choosing a tree on the n-nodes, then subdividing each edge by inserting a d-node. Hence each d-node in T induces a natural “pair” of edges. Consider the special case where G is one such “pair” of edges, so E(G) = {(u, a), (v, a)}, and let G1 be a labeling of G in X and G2 a labeling of G in Y . A straightforward calculation shows that ( G1 G2 ρ2 /d, if Vn (G1 ) = Vn (G2 ), E X Y = (2.3) 0, otherwise. 8

Thus, the moment is zero unless G1 and G2 induce the same edge after their d-nodes are contracted. When i and j form a true pair, we can lower bound E[scoreii ] by considering terms E[X T1 Y T2 ] for which every n-node in T1 has the same label as the corresponding n-node in T2 . In this configuration, every edge pair in T1 is matched with its corresponding edge pair in T2 , as illustrated in Figure 2. Therefore, up to lower-order terms we have E[X T1 Y T2 ] = (E[X G1 Y G2 ])|E(T )|/2 = (ρ2 /d)K , recalling that the tree has 2K edges. We now count the number of these dominant configurations. There are |T | choices for the unlabeled tree, nK choices for the non-root n-nodes, and d2K choices for the d-nodes in the two labeled trees. All other configurations contribute lower-order terms. Therefore, E[scoreii ] = (1 + o(1))|T |nK d2K (ρ2 /d)K = (1 + o(1))|T |nK dK ρ2K . For false pairs where i ̸= j, E[scoreij ] = 0. This is because the joint moment E[X T1 Y T2 ] is only nonzero if the degree of u in T1 is equal to the degree of u in T2 ; since the root is the unique node of degree D in T , E[X T1 Y T2 ] = 0 unless i = root(T1 ) = root(T2 ) = j. root i = j T1 T2

...

d-node from T1 d-node from T2 matched n-node

Figure 2: Dominant contribution to the true-pair mean. Every n-node in T1 has the same label as its counterpart in T2 ; these matched n-nodes are drawn in purple. Moreover, every edge pair in T1 is matched with the corresponding edge pair in T2 . The d-nodes from T1 and T2 are drawn separately to indicate that they need not have the same labels, while still contributing positively after averaging over Q.

Variance bounds. Given the separation in the mean of the similarity scores for true and false pairs, we prove concentration by bounding the variance. To successfully argue that most of the n true pairs can be distinguished from the n(n − 1) false pairs, we require ( o(1/n), j ̸= i, Var(scoreij ) = (2.4) 2 (E[scoreii ]) o(1), j = i. In the following explanation, we focus on a false pair with j ̸= i. Since E[scoreij ] = 0, we have X X Var(scoreij ) = E[score2ij ] = aut(T )aut(S) E X T1 Y T2 X S1 Y S2 . (2.5) T1 ,T2 ∼ =T,S1 ,S2 ∼ =S root(T1 )=root(S1 )=i root(T2 )=root(S2 )=j

T,S∈T

Thus, the variance is governed by joint moments of four trees T1 , T2 , S1 , S2 . The moments are governed by the degree to which these labeled trees’ structure matches; there are two types of configurations whose contribution dominates variance, as illustrated in Figure 3. 9

root j

root i

T1 a

...

(a) Consider the four branches on the left as an example. The first d-node in the branch of T1 coincides with that in the branch of S1 at a, and similarly the first d-node in the branch of T2 coincides with that in the branch of S2 at b. Once these parallel edge pairs are formed, edge pairs in the descendant subtree of this branch in T1 are matched with those in the isomorphic branch of T2 , and similarly for S1 and S2 .

root i

root j

...

(b) Here T1 = S1 and T2 = S2 as labeled trees, and therefore T ∼ = S. Figure 3: Dominant configurations for the false-pair variance.

The first type of configuration dominates when X and Y are imbalanced, namely d ≪ n, as illustrated in Figure 3a. Focus first on the four branches on the left. The first d-node in the branch of T1 coincides with that in the branch of S1 at a; similarly, the first d-node in the branch of T2 coincides with that in the branch of S2 at b. This creates two parallel edge pairs, one red and one 2 ] = E[Y 2 ] = 1. Moreover, the red edge pair ((u, a), (v, a)) is blue, which contribute factors E[Xia jb matched with the blue edge pair ((u, b), (v, b)). Each red edge pair in the descendant subtree of this branch in T1 can then be matched with a blue edge pair in the descendant subtree of the isomorphic branch in T2 , and the same holds for S1 and S2 . Suppose that all branches are partitioned into groups of four branches arranged in this way. Then, except for the 2D parallel edges incident to the roots, the remaining 2K − D matched edge pairs together contribute a factor (ρ2 /d)2K−D , up to lower-order terms, by (2.3). The unlabeled trees T and S can be chosen independently, giving |T |2 choices. There are n2K choices for the n-node labels. For the d-nodes, the root-adjacent d-nodes are shared by two X-trees or by two Y -trees, giving d4K−2D choices in total. Hence, after dividing this configuration’s contribution to the variance by the squared mean, we obtain |T |2 n2K d4K−2D (ρ2 /d)2K−D 1 = 2 D. 2 (E[scoreii ]) (ρ d)

(2.6)

When d is only polylog(n), to achieve (2.4), the bound (2.6) forces D ≥ C log n/ log log n, 10

(2.7)

for a sufficiently large constant C > 0. That is, the trees must be wide. The second dominant configuration occurs when T1 = S1 and T2 = S2 as labeled trees, as illustrated in Figure 3b. In this case, the interaction of X and Y is irrelevant; instead, pairs of 2 ] = 1 and pairs of parallel edges inside parallel edges inside X contribute factors of the form E[Xua Y contribute similarly. Since T and S must be isomorphic in this configuration, there are only |T | such terms. There are n2K choices of the n-node labels and d2K choices of the d-node labels. Hence, the contribution of this term is of order |T |n2K d2K . Dividing by the mean square gives 1 |T |n2K d2K = . (E[scoreii ])2 |T |ρ4K

(2.8)

So we wish for |T | as large as possible to upper bound this quantity by o(1/n) as required in (2.4). In particular, we have D |J | e · (α + o(1))−M = (α + o(1))−K exp(−D log D + D). |T | = ≈ D D Now, for each ϵ > 0, so long as D ≤ cK/ log K for c > 0 sufficiently small, |T | ≥ (α + ϵ/2)−K . Thus, by choosing ρ4 ≥ α + ϵ,

K = C1 log n,

and D = c1 K/ log K,

(2.9)

for constants C1 > 0 sufficiently large and c1 > 0 sufficiently small, we satisfy both the wide tree constraint (2.7) and the requirement from (2.4) that (2.8) is o(1/n). This explains the parameter choices of K and D and the correlation condition ρ4 > α. We state these statistical guarantees formally in Section 3.

2.4

Performance Guarantees

We now state the main guarantee for our matching algorithm. Theorem 2.1. Suppose that ρ4 ≥ α + ϵ, where ϵ is an arbitrarily small constant. There exist constants C1 , C2 , c1 > 0, depending only on ϵ, such that the following holds. Let T be the tree family defined in Definition 2.2 with parameters specified in (2.9). Let π b and I denote the output of Algorithm 1 applied to T with threshold τ = c|T |nK dK ρ2K for some constant c ∈ (1/4, 3/4). If d ≥ (log n)C2 , then with probability 1 − o(1), π b = π | I and |I| ≥ n − n/ log2 n. Polynomial-time approximation. With our choice of T and K = Θ(log n), a direct computation of labelT (X, i) in (2.1) and scoreij in (2.2), which requires enumerating all labeled trees T1 ∼ = T with K+1 K 2K +1 vertices, would take n d time, which is super-polynomial in (n, d) when K = Θ(log n). To address this computational issue, in Section 7 we present a polynomial-time algorithm (Algorithm 2) that computes an approximation score [ ij to scoreij using the color-coding technique, as in [MWXY25]. The same performance guarantees for Algorithm 1 continue to hold when {scoreij } is replaced by {score [ ij }, stated as follows. Consequently, we complete the computational result. Proposition 2.1. Theorem 2.1 continues to hold with score [ ij in place of scoreij . Moreover, {score [ ij }i,j∈[n] can be computed in O(nC d) time, with a constant C > 0 depending only on ϵ. 11

Exact recovery. Moreover, we can boost almost exact recovery to exact recovery in polynomial time. The key observation is that, given a seed set J, if i ∈ / J and j = π(i) form a true pair, then the vectors (⟨xi , xr ⟩)r∈J and (⟨yj , yπ(r) ⟩)r∈J are correlated, whereas for a false pair, these vectors are independent. Starting from the almost exact matching π b on I as seeds, we threshold the correlations between these vectors for unmatched points, and iteratively extend the matching to all vertices. Algorithm 3 in Section 8 formalizes this procedure. The following theorem establishes its success. Theorem 2.2. Suppose that there exists a large constant C > 0 such that log n 1 2 . ρ ≥ C max , √ d log n

(2.10)

Then, with probability 1 − o(1), the following holds: for every partial matching π b = π|I , where I ⊂ [n] satisfies |I| ≥ n − n/ log2 n, the seeded matching algorithm Algorithm 3, initialized with π b, outputs π e = π in O(n3 d) time. Observe that the boosting condition (2.10) is implied by the almost-exact recovery condition ρ2 > α, and that the seeded matching algorithm succeeds under any seed set I with |I| ≥ n − n/ log2 n. Therefore, combining Theorem 2.1 and Theorem 2.2 yields Theorem 1.1, showing that exact recovery √ is achieved in polynomial time whenever ρ2 > α. √

2.5

Information-Theoretic Thresholds and Computational Gaps

We complement our algorithmic results with an improved information-theoretic guarantee in the high-dimensional regime. We analyze the following quadratic assignment problem (QAP) estimator: D E b ∈ arg max B, P AP ⊤ , Π (2.11) P ∈Sn

where A = XX ⊤ , B = Y Y ⊤ , and the maximization is taken over all possible permutation matrices P . Note that QAP is NP-hard to solve or even approximate in the worst case [MMS10]. Theorem 2.3. There exists a constant C > 0 such that if d ≥ C log n and ) ( r log n log n 2 , , ρ ≥ C max d n

(2.12)

b = Π with probability 1 − o(1). then the QAP estimator in (2.11) satisfies Π When d ≫ log n, [WWXY22] shows that even if the orthogonal transformation Q is known, ρ2 ≥ (2 − o(1)) log n/d is necessary for almost exact recovery of π. Therefore, the √ sufficient condition (2.12) √ matches this necessary condition up to constant factors when d ≪ n log n. If instead d ≳ n log n, then the sufficient condition (2.12) reduces to ρ4 ≳ log n/n, which coincides with the recovery thresholds for the correlated Gaussian model [Gan22, WXY22]. It remains open whether this condition is also necessary for exact recovery in Procrustes matching. Note that, unlike the correlated Gaussian model, the observed data matrix B is not given by ΠAΠ⊤ plus an additive Gaussian noise matrix; thus, the QAP (2.11) does not coincide with the maximum likelihood estimator (MLE). As shown in [WWXY22, (3)], the exact MLE for Procrustes matching maximizes a likelihood function that involves an integral over the Haar measure on the orthogonal group, rendering the exact MLE difficult to analyze directly. The previous work [WWXY22] applies Laplace’s method to this integral to derive an approximate MLE arg maxP ∈Sn maxQ∈Od ⟨Y, P XQ⟩ and shows that it achieves the sharp information-theoretic thresholds in the low-dimensional regime when d ≪ log n. However, in the high-dimensional regime, [EGMM24] only shows that this approximate MLE succeeds in almost exact recovery when ρ = 1 − o(1) and d ≪ n. 12

Computational gaps. In the high-dimensional regime d ≥ polylog(n), our tree-counting algorithm √ succeeds under constant correlation ρ2 > α, whereas exact recovery is information-theoretically possible even when ρ2 decays polynomially in n and d. We see a substantial computational-statistical gap, and whether it can be narrowed or closed remains open. The prior work [Li26] shows, under the low-degree hardness framework [HS17, KWB19, Wei25], that a closely related hypothesis testing problem exhibits a computational gap. Specifically, all degree-O(log n) polynomial tests fail to reliably distinguish between the null hypothesis ρ = 0 and alternative ρ = ρ∗ , when ρ2∗ ≪ 1/ log n. One may be tempted to ask whether counting a richer family of graphs would yield computational √ guarantee below ρ2 > α. Indeed, going beyond trees, for example, to graphs with bounded treewidth, or using a different algorithmic design may help. For both the correlated Gaussian model and the dense correlated Erdős-Rényi graph model, previous work [DL25a, DL25b] has shown that one can achieve correct matching even when the correlation ρ is an arbitrarily small but fixed constant. Within the tree-counting framework, however, our choice of trees appears close to optimal. In Section 10, we show that among all trees with 2K edges, the main contribution to the distingushing power between the null hypothesis ρ = 0 and alternative ρ = ρ∗ , comes from trees with degree-2 d-nodes, as long as d ≥ poly(K). This supports the choice made by our algorithm, which counts precisely this family of trees.

Statistical Guarantees

In this section, we present the statistical guarantees for the similarity scores suggested by the preceding intuition, and then deduce Theorem 2.1 from them. We begin with the mean separation. Proposition 3.1. The similarity scores defined in (2.2) with T being the tree family from Definition 2.2 satisfy E[scoreii ] ≥ (1 − o(1)) |T |nK dK ρ2K ,

E[scoreij ] = 0, ∀j ̸= i.

(3.1)

The intuition behind Proposition 3.1 has already been discussed in Section 2.3 and illustrated in Figure 2; the formal proof is given in Section 5. The next proposition bounds the variance. Proposition 3.2. Define β = α + ϵ/2. Suppose that ρ4 ≥ α + ϵ and p β M |J | ≥ 7D2 , ( β/ρ2 )M < 1/2, (poly(K)/ min{d, n})1/8 < 1/2. Then there exists an absolute constant C > 0 such that " √ M # Var(scoreii ) β poly(K) 1/8 ≤C + , ρ2 min{d, n} (E[scoreii ])2 " # Var(scoreij ) poly(K) D/2 β K ≤ CD + , ρ4 min{d, n} (E[scoreii ])2

(3.2) ∀j ̸= i.

(3.3)

The intuition behind the false-pair variance bound (3.3) has already been discussed in Section 2.3. In particular, the two dominant terms arise from the two configurations depicted in Figure 3. The intuition behind the true-pair variance bound (3.2) is similar, except that these structures can occur only at a branch pair; as a result, the exponents in the two terms are each reduced by a Θ(D) factor. The formal proof of Proposition 3.2 involves intricate combinatorial arguments on trees, and is deferred to Section 6. Together, Propositions 3.1 and 3.2 guarantee the success of the algorithm. 13

Proof of Theorem 2.1. We first show that, under the parameter specified in (2.9) with appropriate choice of constants C1 , C2 , c1 > 0, Proposition 3.2 implies the following bounds: " √ M # C Var(scoreii ) β poly(K) 1/8 ≤ + , (3.4) 2 ≤C 2 ρ min{d, n} log5 n (E[scoreii ]) " # Var(scoreij ) β K poly(K) D/2 C + ≤ 3 , ∀j ̸= i. (3.5) 2 ≤ CD 4 ρ min{d, n} n (E[scoreii ]) First, note that |J | = (α + o(1))−M ≥ [(α + ϵ/2)/(1 + ϵ/4)]−M and recall that M = K/D = (1/c1 ) log K. Thus, if c1 is sufficiently small so that log(1 + ϵ/4)/c1 > 2, then β M |J | ≥ (1 + ϵ/4)M = K log(1+ϵ/4)/c1 ≥ 7D2 . √ Second, if c1 ≤ log((α + ϵ)/(α + ϵ/2))/12 = log(ρ2 / β)/6, then with M = K/D = (1/c1 ) log K and K = C1 log n, we have √ M √ √ 1 β − log(ρ2 / β)/c1 − log(ρ2 / β)/c1 = K = (C log n) ≤ . 1 2 ρ 2 log5 n Next, choose C1 ≥ 4/ log((α + ϵ)/(α + ϵ/2)) = 4/ log(ρ4 /β). Then C1 log n K c1 K β 1 β = ≤ 3. D 4 4 ρ log K ρ 2n Moreover, note that d ≥ (log n)C2 and K = C1 log n. By choosing C2 to be a sufficiently large constant, we have poly(K)/ min{d, n} ≤ (log n)−C2 /2 and 1 poly(K) 1/8 . ≤ (log n)−C2 /16 ≤ min{d, n} 2 log5 n Finally, substituting K = C1 log n and D = c1 K/ log K and choosing C2 to be a sufficiently large constant, we get poly(K) D/2 1 D ≤ D(log n)−C2 D/4 ≤ (log n)−C2 C1 c1 log n/(4 log(C1 log n))+1 ≤ 3 . min{d, n} 2n We now prove Theorem 2.1. Recall that the constant c ∈ (1/4, 3/4). Let ν = E[scoreii ]. For any j ̸= i, by Chebyshev’s inequality and (3.5), we obtain P {scoreij ≥ τ } = P {scoreij − E[scoreij ] ≥ (c − o(1))ν} ≤

Var(scoreij ) = o(1/n2 ). (c − o(1))2 ν 2

Applying a union bound over all pairs with j ̸= i, we obtain P {∃j ̸= i ∈ [n] : scoreij ≥ τ } = o(1). Thus, with probability at least 1 − o(1), we have scoreij < τ for all j = ̸ i and all i ∈ [n]. By our construction of π b and I, it follows that I = {i : scoreii > τ } and π b | I = π with probability at least 1 − o(1). For the true pairs, Chebyshev’s inequality yields P {scoreii ≤ τ } ≤ P {|scoreii − ν| ≥ (1 − c)ν} ≤

Var(scoreii ) ≜ γ, (1 − c)2 ν 2

where γ ≤ 1/ log4 n by (3.4). Hence E [n − |I|] ≤ γn. Applying Markov’s inequality, we have P {n − |I| ≥

√

γn} ≤

E [n − |I|] √ 1 ≤ γ= . √ γn log2 n

Consequently, we conclude that |I| ≥ n − n/ log2 n with probability at least 1 − o(1). 14

Joint Moments Calculation

We first establish a general result for the joint moments of X and Y , which will be useful for bounding the mean and variance. Given any bipartite multigraphs G and H with the same number of edges, we compute the expectation E XG · Y H . (4.1) We show that this expectation can be bounded in terms of combinatorial properties of the n-union graph of G and H, which we will denote by G ∪n H and define as follows: 1. Edges and d-nodes from G are colored red. Edges and d-nodes from H are colored blue. 2. n-nodes from G and H are merged according to their labels; d-nodes from G are kept distinct from d-nodes from H. Specifically, we show that the joint moments can be bounded as a function of the alternating circuit decompositions of G ∪n H (to be defined later). To arrive at this decomposition, we first take expectation over the Gaussian random variables X and Z using Isserlis’ (or Wick’s) theorem, and then take expectation over the random orthogonal matrix Q via Weingarten calculus.

4.1

Joint Moments of Gaussian Random Variables

Since the entries of X and Z are symmetrically distributed around zero, their odd-degree moments vanish. Thus, we only need to consider even-degree moments. The following lemma, known as Isserlis’ (or Wick’s) theorem [Iss18, Wic50], provides a formula for computing the moments of joint Gaussian distributions. Fix an even integer N . We define M(N ) as the set of all perfect matchings (pair partitions) m of the index set [N ], where each matching m ∈ M(N ) can be written as m = {{m(1), m(2)}, · · · , {m(N − 1), m(N )}}, with {m(1), · · · , m(N )} being a permutation of [N ]. Lemma 4.1 (Isserlis’/Wick’s Theorem). Let (ξ1 , · · · , ξN ) be a multivariate Gaussian random vector with zero mean and N be even. Then we have "N # Y X Y E ξi = E[ξi ξj ], i=1

m∈M(N ) {i,j}∈m

where the summation runs over M(N ), the set of perfect matchings (pair partitions) m of the index set [N ], and each product is over the pairs defined by the matching m. Isserlis’ theorem converts higher-order moments of Gaussian random variables into sums of products of pairwise covariances. This allows us to compute the joint moments of X and Y f conditional on Q. Specifically, we define M(G, H) as the set of perfect matchings on the edge set f of the n-union graph G ∪n H. For each m ∈ M(G, H), let mbi = m ∩ (E(G) × E(H)) be the set 4 of bichromatic pairs. The remaining pairs in m \ mbi are called monochromatic pairs, since they f consist of two edges both in E(G) or both in E(H). We further define a subset M(G, H) ⊂ M(G, H) consisting of those perfect matchings such that all bichromatic pairs of edges share an n-node in G ∪n H, and all monochromatic pairs share both endpoints. That is, for any m ∈ M(G, H): 4

For clarity, we always write pairs {(u, a), (v, b)} ∈ m with one edge from E(G) and the other from E(H) in an ordered manner, where the first component is from E(G) corresponding to X, and the second component is from E(H) corresponding to Y . Such pairs are denoted by {(u, a), (v, b)} ∈ E(G) × E(H).

1. For each pair {(u, a), (v, b)} ∈ mbi , it must hold that u = v. 2. For each pair {(u, a), (v, b)} ∈ m \ mbi , it must hold that u = v and a = b. Note that if both G and H are simple graphs without parallel edges, then no monochromatic pairs exist, and M(G, H) ̸= ∅ only if every n-node in G ∪n H is incident to the same number of edges from G as from H. The lemma below computes the joint moments in X and Y , conditioned on Q, by applying Isserlis’ theorem. Since every matching Q m ∈ M(G, H) consists of pairs of edges sharing an n-node, we abuse notation and write Qm = {(u,a),(u,b)}∈m Qab , conflating the set of pairs of edges m with the corresponding set of pairs of their d-endpoints. Lemma 4.2. For any bipartite multigraphs G and H, we have X EX,Z X G · Y H Q = ρ|mbi | Qmbi . m∈M(G,H)

Lemma 4.2 implies that any G and H with M(G, H) = ∅ yield a joint moment of 0. Proof of Lemma 4.2. Since X, Y | Q follow a joint Gaussian distribution with zero mean, we apply Isserlis’ Theorem by first computing the pairwise correlation of entries. First, since all entries of X are independent, we have E[Xua Xvb ] = 1{(u,a)=(v,b)} .

(4.2)

E [Yua Yvb | Q] = 1{(u,a)=(v,b)} .

(4.3)

Similarly, we have

Next, we compute the conditional correlation between Xua and Yvb and obtain     X p E [Xua Yvb | Q] = E Xua ρ Qcb Xvc + 1 − ρ2 Zvb  Q c∈[d]





= ρE Xua ·

Qcb Xvc Q

c∈[d]

(4.4)

= ρQab 1{u=v} ,

where the second equality uses independence of X and Z and the last equality follows from (4.2). f Recall that M(G, H) is the set of perfect matchings among all edges in G and H. Lemma 4.1 and the pairwise covariances in (4.2), (4.3), and (4.4) imply that X Y Y Y E XG · Y H Q = E [Xe Xf ] E [Ye Yf | Q] E [Xe Yf | Q] f {e,f }∈m\mbi m∈M(G,H) e,f ∈E(G)

f {e,f }∈m\mbi m∈M(G,H) e,f ∈E(G)

{e,f }∈m\mbi e,f ∈E(H)

1{e=f }

{e,f }∈m\mbi e,f ∈E(H)

1{e=f }

{e,f }∈mbi

ρQab 1{u=v} .

{(u,a),(v,b)}∈mbi

The conclusion now follows because the indicators enforce the conditions defining M(G, H). It now remains to take the expectation over Q. 16

4.2

Weingarten Calculus for Orthogonal Groups.

Weingarten calculus is a method for computing moments of matrices sampled from the Haar measure over the Orthogonal or Unitary group. We use Weingarten calculus to take the expectation over Q, as in a number of recent works in high-dimensional/computational statistics [CLO22, KMW24] (our specific use is somewhat different). We now summarize several key results from Weingarten calculus for computing moments of entries of Q [CM17]. Since the Haar measure over orthogonal matrices is symmetric about zero, all odd-degree moments vanish, and it suffices to consider only even-degree moments. Suppose we are given a bipartite multigraph J = ([d], [d], E), whose left-hand vertex set is identified with a “red” copy of [d] and whose right-hand vertex set is identified with a “blue” copy of [d]. Recall that QJ denotes the product of matrix entries corresponding to the edges of J. It will turn out that the moment EQ∼O(d) [QJ ] can be expressed in terms of features of the circuit decompositions of J. To describe this relation, we introduce the following notion. Definition 4.1 (Circuit Decomposition). Let J be a multigraph, and in what follows treat multi-edges as distinct parallel edges. A closed walk is a sequence of edges (e1 , e2 , · · · , ek ) for which there exists a sequence of vertices (v1 , v2 , · · · , vk+1 ) such that ei is an edge between vi and vi+1 for each i ∈ [k], and v1 = vk+1 . A circuit is a closed walk in which all edges are distinct. Two closed walks that traverse the same set of edges in a different order are considered distinct as circuits, unless one can be obtained from the other by a cyclic shift or by reversing the order of traversal. In other words, the walks (e1 , e2 , · · · , ek ), (ei , ei+1 , · · · , ek , e1 , · · · , ei−1 ), and (ei , ei−1 , · · · , e1 , ek , · · · , ei+1 ) for any i ∈ [k] are considered the same circuit. A circuit decomposition of J is a set of circuits that partitions E(J). Two circuit decompositions are considered distinct if they contain different circuits. We denote by C(J) the set of all circuit decompositions of J. A graph J admits a circuit decomposition if and only if all of its vertices have even degrees. Figure 4 shows an example of a graph J and its circuit decompositions. e1 1

e3 e4

Figure 4: Here E(J) = {e1 , e2 , e3 , e4 } and QJ = Q211 Q212 . The graph J admits three circuit decompositions: one consisting of two circuits of length 2, {(e1 , e2 ), (e3 , e4 )}, and two consisting of a single circuit of length 4, {(e1 , e2 , e3 , e4 )} and {(e1 , e2 , e4 , e3 )}.

Weingarten calculus. Consider any circuit decomposition c in which every circuit has even length. For each integer ℓ ≥ 1, let µℓ (c) denote the number of circuits of length 2ℓ in c, and write µ(c) = (µℓ (c))ℓ≥1 for the circuit type of c. We take a vertex-disjoint union of these circuits in c, and assign each vertex a distinct label so that vertices belonging to different circuits have different labels. Let G be a bipartite multigraph obtained in this way. We define the Weingarten function associated with the circuit type µ(c) by Wg(µ(c), d) ≜ EQ∼O(d) QG . (4.5) 17

By the bi-invariance of the Haar measure, the value in (4.5) is invariant under permutations of vertex labels and therefore depends only on the circuit type µ(c), rather than on the specific labeling of G. Now consider an arbitrary bipartite graph J = ([d], [d], E). In general, J may admit multiple circuit decompositions, each consisting of circuits of even length, see, e.g., Figure 4. For any decomposition c ∈ C(J), its circuit type µ(c) determines a Weingarten function value Wg(µ(c), d) defined in (4.5). The following Weingarten calculus expresses the moment of QJ as a sum over all such circuit decompositions. Lemma 4.3 ([CM17, Lemma 4.1]). For a bipartite graph J = ([d], [d], E), we have X EQ∼O(d) QJ = Wg(µ(c), d), c∈C(J)

where µ(c) denotes the circuit type of the decomposition c, and Wg(µ(c), d) is the corresponding Weingarten function. In the special case where every vertex of J has degree exactly 2, the graph J itself is a disjoint union of cycles and thus admits a unique circuit decomposition c. In this case, Lemma 4.3 reduces to the definition in (4.5). Asymptotic values of the Weingarten function. Explicit formulas for Wg(µ(c), d) can be derived directly from (4.5). For our P purposes, however, it suffices to use asymptotic bounds. The total number of edges of the graph is ℓ≥1 2ℓµℓ (c), since each of the µℓ (c) circuits contains 2ℓ edges. We µ (c) Q 1 2i denote this quantity by 2k. Define γµ(c) = ℓ≥1 Catalan(ℓ−1) ℓ , where Catalan(i) = i+1 i for P

i ≥ 0 denotes the Catalan number. Since Catalan(i) ≤ 4i for all i, we have 1 ≤ γµ(c) ≤ 4k− ℓ≥1 µℓ (c) . The Weingarten function Wg(µ(c), d) can be bounded as follows. P Lemma 4.4 ([CM17, Theorem 4.11, Lemma 4.12]). Given any circuit type µ(c), let k ≜ ℓ≥1 ℓµℓ (c). So long as d > 12k 7/2 , we have P P poly(k) γµ(c) (−1)k− ℓ≥1 µℓ (c) d−2k+ ℓ≥1 µℓ (c) . Wg(µ(c), d) = 1 ± d P

ℓ≥1 µℓ (c) in Lemma 4.4 implies that circuit decompositions c containing The leading factor d−2k+ P a larger number of circuits ℓ≥1 µℓ (c) tend to yield Weingarten function values of larger magnitude. In addition, Lemma 4.4 implies that the Weingarten function admits an approximate factorization over edge-disjoint graphs. Specifically, for two edge-disjoint graphs J1 and J2 with union J = J1 ∪ J2 , and their circuit decompositions c1 and c2 with union c = c1 ∪ c2 , it holds that

Wg(µ(c), d) = (1 + o(1))Wg(µ(c1 ), d)Wg(µ(c2 ), d).

(4.6)

This follows from the fact that, in the approximation, the quantities µℓ (c) appear only in the exponents, and the circuit counts are additive for edge-disjoint parts; that is, µℓ (c) = µℓ (c1 ) + µℓ (c2 ) for all ℓ ≥ 1. Joint moments via Weingarten calculus. We now apply the Weingarten calculus to compute joint moments. Recall from Lemma 4.2 that each matching m ∈ M(G, H) corresponds to a Q m bi monomial Q = {(u,a),(u,b)}∈mbi Qab . We represent this monomial using a bipartite multigraph Jmbi = ([d], [d], E(Jmbi )), whose edge multiset is defined by E(Jmbi ) = {(a, b) ∈ [d] × [d] : {(u, a), (u, b)} ∈ mbi }. 18

(4.7)

Since each pair {(u, a), (u, b)} ∈ mbi corresponds to a bichromatic 2-path in G ∪n H, we can think of Jmbi as the bipartite graph obtained by contracting each such 2-path into a single edge with one red and one blue d-endpoint. With this representation, the joint moments in (4.1) can be expressed using circuit decompositions of Jmbi as follows. Proposition 4.1. For any bipartite multigraphs G and H, we have X X E XG · Y H = ρ|mbi | · Wg(µ(c), d). m∈M(G,H)

c∈C(Jmbi )

Proof. Following from (4.1) and Lemma 4.2, we have X EX,Y X G · Y H =

ρ|mbi | · E [Qmbi ] .

m∈M(G,H)

For each m ∈ M(G, H), the Weingarten calculus in Lemma 4.3 implies that X E [Qmbi ] = Wg(µ(c), d), c∈C(Jmbi )

where Jmbi is the bipartite multigraph defined in (4.7). Combining Proposition 4.1 with Lemma 4.4, we can further obtain bounds for the joint moments. To simplify the presentation, we state the final result in the next section using alternating circuit decompositions of the n-union of G and H.

4.3

Joint Moments Calculation via Alternating Circuit Decompositions

For each m ∈ M(G, H), each circuit decomposition c of Jmbi induces a circuit decomposition of the n-union G ∪n H as follows: 1. Each circuit of length 2ℓ maps to a circuit of length 4ℓ in G ∪n H, by un-contracting each edge of Jmbi to the original bichromatic 2-path from which it arose. These circuits are “alternating” in that whenever they reach an n-node, the edge color alternates from red to blue or vice-versa. 2. Each pair {(u, a), (u, a)} ∈ m \ mbi gives a circuit of length 2 in G ∪n H. We define the set of circuit decompositions that can be induced in G ∪n H by such Jmbi alternating circuit decompositions, denoted by C(G ∪n H), where “alternating” refers to the fact that the edge color in circuits of length ≥ 4 alternates between blue and red every time an n-node is reached. Definition 4.2 (Alternating Circuit Decompositions). An alternating circuit decomposition of the n-union G ∪n H is a circuit decomposition where each circuit satisfies: 1. Within each circuit of length 4 or greater, any two edges incident to each n-node have distinct colors; 2. Circuits of length 2 are multi-edges in G ∪n H, where both edges have the same color. Recall that we treat each parallel copy of a multi-edge as distinct. Thus, two alternating circuit decompositions whose circuits differ only by the choice or order of edges from a multi-edge are considered distinct in the set C(G ∪n H). For C(G ∪n H) to be nonempty, graphs G and H must satisfy the following conditions: 19

1. All d-nodes from both G and H have even degrees; 2. After removing all 2-circuits, the remaining degree sequences of n-nodes from G and H are the same. With a slight abuse of notation, for any c ∈ C(G ∪n H), we let µℓ (c) denote the number of alternating circuits of length 4ℓ in G ∪n H for ℓ ≥ 1, and µ(c) = {µℓ (c)}ℓ≥1 for the circuit type. Each alternating circuit of length 4ℓ arises from a circuit of length 2ℓ in Jmbi . Thus, µ(c) also corresponds to the circuit type of the original circuit decomposition of Jmbi . Accordingly, we denote by Wg(µ(c), d) the Weingarten function associated with this circuit type. We consider G and H both with 2k edges. Let 2κ(c) be the number of circuits of length 2. Since every circuit of length ≥ 4 alternates between edges of G and H, each such c contains exactly κ(c) 2-edge circuits from G and κ(c) 2-edge circuits from H. The following theorem summarizes the joint moments computation via alternating circuit decompositions. Theorem 4.1 (Joint Moments Calculation). For any bipartite multigraphs G and H both with 2k number of edges, X E XG · Y H = ρ2(k−κ(c)) Wg(µ(c), d), c∈C(G∪n H)

and as long as d > 12k 7/2 , poly(k) = 1± d

X c∈C(G∪n H)

P 2 k−κ(c) 1 k−κ(c)− ℓ≥1 µℓ (c) ρ γµ(c) − . d d

The proof follows immediately from combining PropositionP 4.1 and Lemma 4.4, noting that the total number of edges in alternating circuits of length ≥ 4 is 4 ℓ≥1 ℓµℓ (c) = 4k − 4κ(c). Moreover, we have the following bound on the total number of alternating circuits: X X X µℓ (c) = µ1 (c) + µℓ (c) ≤ µ1 (c) + ℓµℓ (c)/2 = µ1 (c) + (k − κ(c) − µ1 (c))/2. ℓ≥1

ℓ≥2

Consequently, we obtain k − κ(c) − 4

P k−κ(c)− ℓ≥1 µℓ (c)

ℓ≥1 µℓ (c) ≥ (k − κ(c) − µ1 (c))/2.

Recall also that γµ(c) ≤

. Thus, each summand in Theorem 4.1 is bounded by

2(k−κ(c))

ℓ≥2

|Wg(µ(c), d)| ≤

poly(k) 1+ d

2 k−κ(c) (k−κ(c)−µ1 (c))/2 ρ 4 . d d

(4.8)

Therefore, the key parameter determining each decomposition’s contribution is k − κ(c) − µ1 (c). In what follows, we will show that decompositions c satisfying µ1 (c) = k − κ(c) yield the leading contribution to the mean or variance, while those with µ1 (c) < k − κ(c) contribute negligibly. Since Theorem 4.1 will be used repeatedly throughout the paper to approximate the Weingarten function for graphs with 2K or 4K edges, where 2K is the number of edges in graphs from T (see Definition 2.2), we henceforth assume that d > 12(2K)7/2 . For brevity, we omit this standing assumption from subsequent theorem and proposition statements in Sections 5 and 6.

Mean Calculation

This section establishes Proposition 3.1. We prove a slightly more general result. Let H be any set of rooted simple bipartite graphs on [n] × [d] with 2K edges, such that the root node is an n-node with strictly larger degree than every non-root node, and every d-node has degree 2. The tree family T from Definition 2.2 is one such set. We compute the mean of scoreH ij , defined in (2.2), separately for true pairs (j = i) and false pairs (j ̸= i). Then Proposition 3.1 follows directly by taking H = T .

5.1

True Pairs

For any i ∈ [n], we have X E scoreH aut(T ) ii = X

E X T1 Y T2

T1 ,T2 ∼ =T root(T1 )=root(T2 )=i

T ∈H

aut(T )

ρ2K Wg(µ(c), d),

(5.1)

T1 ,T2 ∼ =T c∈C(T1 ∪n T2 ) root(T1 )=root(T2 )=i

T ∈H

where the last equality follows from the Weingarten calculus in Theorem 4.1, noting that each of T1 and T2 has 2K edges. Moreover, since T1 and T2 are simple graphs, their n-union is also simple (recall the d-nodes in T1 and T2 have distinct colors, so no multi-edge can be formed), and thus contains no 2-circuits. Hence, every c ∈ C(T1 ∪n T2 ) satisfies κ(c) = 0. Recall the intuition following Lemma 4.4 and (4.8): among all decompositions c, those with the largest µ1 (c), equivalently containing the most 4-circuits, make the dominant contribution to the mean, while the contributions of the remaining decompositions are negligible. We now use this observation to derive the order of E[scoreH ii ]. We also define X X X νH ≜ aut(T ) ρ2K |Wg(µ(c), d)| (5.2) T ∈H

T1 ,T2 ∼ =T c∈C(T1 ∪n T2 ) root(T1 )=root(T2 )

by replacing Wg(·) in (5.1) with its absolute value, which will be used in the variance bound. √ Proposition 5.1. Fix any i ∈ [n]. If K = o( n), we have poly(K) poly(K) H H E scoreii = 1 ± ν = 1± |H|nK dK ρ2K . d min{n, d} Proof. We suppress the root index i to simplify notation. By (5.1), we have X X X E scoreH = aut(T ) ρ2K Wg(µ(c), d). ii T ∈H

T1 ,T2 ∼ =T c∈C(T1 ∪n T2 )

Fix T ∈ H. Note that T has 2K edges and recall from Theorem 4.1 that 2K

2 K P poly(K) ρ 1 K− ℓ≥1 µℓ (c) . Wg(µ(c), d) = 1 ± γµ(c) − d d d

We now analyze the contribution according to the value of µ1 (c).

Leading term: µ1 (c) = K. We first show that the dominant contribution arises from decompositions c satisfying µ1 (c) = K, as illustrated in Figure 2. Whenever µ1 (c) = K, we have γµ(c) = 1 P P K− ℓ≥1 µℓ (c) and ℓ≥1 µℓ (c) = K and therefore γµ(c) (−1/d) = 1. Thus, for such c, we have 2K

ρ It follows that X X aut(T ) T ∈H

Wg(µ(c), d) =

poly(K) 1± d

2 K ρ . d

(5.3)

ρ2K Wg(µ(c), d)

T1 ,T2 ∼ =T c∈C(T1 ∪n T2 ) µ1 (c)=K

2 K X X ρ poly(K) |{(T2 , c) : T2 ∼ = 1± aut(T ) = T1 , c ∈ C(T1 ∪n T2 ), µ1 (c) = K}| . d d ∼ T ∈H

T1 =T

For a fixed labeled tree T1 , the condition µ1 (c) = K forces complete overlap of all K edge pairs, each sharing a common d-node. Hence T2 must coincide with T1 on all n-nodes, and there is a unique decomposition c with µ1 (c) = K. Thus, the only freedom in choosing (T2 , c) lies in labeling the K d-nodes of T2 , giving d ∼ |{(T2 , c) : T2 = T1 , c ∈ C(T1 ∪n T2 ), µ1 (c) = K}| = K!. K It remains to count the number of labeled trees T1 ∼ = T . We first label the K n-nodes using labels n−1 from [n] \ {i}, excluding the root label i, with K K!/aut(T ) distinct choices. For each such d labeling, we label the K d-nodes, with additional K K! choices. Thus, we have n−1 K! d K ∼ T }| = |{T1 = K!. (5.4) aut(T ) K Combining the above, we conclude that X X X aut(T )

ρ2K Wg(µ(c), d)

T1 ,T2 ∼ =T c∈C(T1 ∪n T2 ) µ1 (c)=K

T ∈H

2 K X n−1 ρ d K K! d aut(T ) K! K! = d aut(T ) K K T ∈H 2 K 2 poly(K) ρ n−1 d = 1± |H| K! K! . d d K K

poly(K) 1± d

(5.5)

Since the right-hand side of (5.3) is positive, it follows that Wg(µ(c), d) > 0, and hence Wg(µ(c), d) = |Wg(µ(c), d)| for all c such that µ1 (c) = K. Therefore, (5.5) continues to hold when Wg(·) is replaced by its absolute value. Remaining terms: µ1 (C) P≤ K − 2. We next bound the contribution of all terms with µ1 (C) ≤ K − 2. In this case, K − r≥1 µr (C) > 0, so each such term gets an additional factor of at least 1/d, making it negligible compared to the leading term. By (4.8), we have 2 K (K−µ1 (c))/2 poly(K) ρ 4 2K ρ |Wg(µ(c), d)| ≤ 1 + . d d d 22

Thus, for any µ1 ≤ K − 2, we have X

aut(T )

T ∈H

|Wg(µ(c), d)| ≤

T1 ,T2 ∼ =T c∈C(T1 ∪n T2 ) µ1 (c)=µ1

aut(T )

poly(K) 1+ d

2 K (K−µ1 )/2 ρ 4 d d

(5.6)

|{(T2 , c) : T2 ∼ = T1 , c ∈ C(T1 ∪n T2 ), µ1 (c) = µ1 }| .

T1 ∼ =T

T ∈H

Fix any T1 . Lemma 5.1 bounds the number of feasible pairs (T2 , c), where the d-nodes in T2 are d unlabeled. Since there are K K! ways to label the K d-nodes in T2 , applying Lemma 5.1 yields d |{(T2 , c) : T2 ∼ K!. (5.7) = T1 , c ∈ C(T1 ∪n T2 ), µ1 (c) = µ1 }| ≤ (4K)K−µ1 K d Recalling that |{T1 ∼ = T }| = n−1 K K! K K!/aut(T ) given in (5.4), we have X aut(T ) |{(T2 , c) : T2 ∼ = T1 , c ∈ C(T1 ∪n T2 ), µ1 (c) = µ1 }| T1 ∼ =T

n−1 K K! d

K−µ1

K! · (4K) aut(T ) K 2 n−1 d = K! K! (4K)K−µ1 . K K ≤ aut(T ) ·

d K! K (5.8)

Thus, combining (5.6) and (5.8), and summing over all µ1 ≤ K − 2, we obtain X X X aut(T ) ρ2K |Wg(µ(c), d)| T ∈H

T1 ,T2 ∼ =T c∈C(T1 ∪n T2 ) µ1 (c)≤K−2

2 K 2 K−2 X 4(4K)2 (K−µ1 )/2 ρ n−1 d poly(K) K! K! ≤ |H| 1 + d d K K d µ1 =0 2 K 2 8(4K)2 ρ n−1 d ≤ |H| K! K! , (5.9) d d K K where the last line follows from summing the geometric series with ratio 4(4K)2 /d ≤ 1/3. Finally, combining the results from (5.5) and (5.9), since

X X E scoreH − aut(T ) ii

ρ2K Wg(µ(c), d)

T1 ,T2 ∼ =T c∈C(T1 ∪n T2 ) µ1 (c)=K

T ∈H

≤

X T ∈H

aut(T )

ρ2K |Wg(µ(c), d)| ,

T1 ,T2 ∼ =T c∈C(T1 ∪n T2 ) µ1 (c)≤K−2

we obtain E

scoreH ii

2 K 2 poly(K) ρ n−1 d = 1± |H| K! K! . d d K K 23

√ K! = (1 + O(K 2 /n))nK = (1 + o(1))nK if K = o( n). Similarly, Furthermore, note that n−1 K √ d K K K! = (1 + o(1)) d if K = o( d). Therefore, we conclude that poly(K) H |H|nK dK ρ2K E scoreii = 1 ± min{n, d} Recall that Wg(µ(c), d) = |Wg(µ(c), d)| for all leading terms where c with µ1 (c) = K. Thus, after replacing Wg(·) by its absolute value, we have ν H = (1 + o(1))E scoreH ii . We now bound the number of feasible pairs (T2 , c) in (5.7). To this end, we drop the isomorphism constraint T2 ∼ = T1 , obtaining a result that will also be used later in Section 6. In this setting, we are given a graph G consisting of red edges in [n] × [d], paired so that each pair shares a common d-node. We aim to bound the number of (H, c), where H is a union of blue edges with unlabeled d-nodes, and c ∈ C(G ∪n H) satisfies µ1 (c) = µ1 . Intuitively, a larger value of µ1 (i.e., more 4-circuits) implies that more blue edges form pairs of parallel edges with the red edge pairs. This imposes stronger structural constraints on H and c, thereby reducing the number of feasible pairs. Lemma 5.1. Fix a (possibly disconnected) graph G consisting of 2k red edges in [n] × [d], where the edges are paired so that each pair shares a common d-node. Consider all unions H of k blue edge pairs (with unlabeled d-nodes), where each pair consists of two edges in [n] × [d] sharing a common d-node. For each such H, form the n-union G ∪n H and consider alternating circuit decompositions c ∈ C(G ∪n H) with no 2-circuits, satisfying κ(c) = 0 and µ1 (c) = µ1 . Then for the fixed G, |{(H, c) : c ∈ C(G ∪n H), µ1 (c) = µ1 }| ≤ (4k)k−µ1 . Proof. We obtain the upper bound by counting valid circuit decompositions c rather than counting H directly. Indeed, once c ∈ C(G ∪n H) is fixed, the blue edge union H (with unlabeled d-nodes) is uniquely determined by c. Thus it suffices to bound the number of such decompositions c. Let µℓ denote the number of P alternating circuits of length 4ℓ Pin c, for ℓ ≥ 1. The total number of red and blue edges satisfies 4 ℓ≥1 ℓµℓ = 4k. In particular, ℓ≥2 ℓµℓ = k − µ1 . Note that each circuit of length 4ℓ uses ℓ pairs of red edges and ℓ pairs of blue edges. For each ℓ ≥ 1, we choose µℓ (ordered) sequences of ℓ pairs out of the k red pairs; this gives a total of Q k! µℓ ! choices (we can ℓ≥1 globally order all of the pairs, split the global ordering into sequences of the desired lengths: µ1 sequences of length 1, µ2 sequences of length 2, etc; and finally divide by the number of orderings of the µℓ ℓ-sequences for each ℓ). For ℓ = 1, each sequence contains just one pair of red edges: we simply concatenate a blue path of length 2 (with an unlabeled blue d-node in the middle) to each pair. For each ℓ ≥ 2, for each sequence of ℓ pairs, we choose a first and second edge in each pair (a total of 2k−µ1 choices), and according to this order form an alternating cycle by concatenating each consecutive ordered red pair with a blue 2-path. The number of {µℓ }ℓ≥1 is no more than the number of integer partitions of k − µ1 , which is at most 2k−µ1 . For each such partition, the number of compatible c is upper bounded by k! Q

ℓ≥1 µℓ !

· 2k−µ1 ≤

k! · 2k−µ1 ≤ k k−µ1 · 2k−µ1 . µ1 !

Thus, multiplying by the 2k−µ1 upper bound on the number of partitions, we have our result.

5.2

False Pairs

For i ̸= j, we have X E scoreH aut(T ) ij =

E X T1 Y T2 .

T1 ,T2 ∼ =T root(T1 )=i root(T2 )=j

T ∈H

For a pair T1 and T2 , their roots are distinct. Since the root of a tree in H has strictly larger degree than any non-root node, the root i of T1 is incident to more edges from T1 than from T2 (where it can appear only as a non-root node) in T1 ∪n T2 . On the other hand, by the remarks following Lemma 4.1, E[X T1 Y T2 ] can be nonzero only if every n-node in T1 ∪n T2 is incident to the same number of edges from T1 as from T2 . This condition therefore fails at the root i, implying that E[X T1 Y T2 ] = 0. Since this holds for every pair T1 and T2 , we conclude that E[scoreij ] = 0.

Variance Calculation

In this section, we derive upper bounds on the variance of the scores and prove Proposition 3.2. Recall from (2.5) that X X Cov X T1 Y T2 , X S1 Y S2 . (6.1) aut(T )aut(S) Var(scoreij ) = T,S∈T

T1 ,T2 ∼ =T,S1 ,S2 ∼ =S root(T1 )=root(S1 )=i root(T2 )=root(S2 )=j

For labeled trees T1 , T2 , S1 , S2 , the Weingarten calculus in Theorem 4.1 implies that the covariance term depends on the alternating circuit decomposition of the n-union graph (T1 ∪ S1 ) ∪n (T2 ∪ S2 ). For ease of notation, we write U ≜ (T1 ∪ S1 ) ∪n (T2 ∪ S2 ) for the decorated union graph obtained from these four trees. The graph U is a multigraph in which edges between the same pair of nodes that originate from different trees are retained as parallel edges. Each edge in U carries a decoration in {T1 , S1 , T2 , S2 } indicating its origin. When forming alternating circuits, we color edges originating from T1 or S1 (from X) red, and edges originating from T2 or S2 (from Y ) blue. We denote by Uij the set of all pairs (U, c), where U is a decorated union graph formed by some trees T1 ∼ = T2 ∈ T and S1 ∼ = S2 ∈ T with roots i and j, respectively, and c ∈ C(U ) is a circuit decomposition of U . By construction, there is a natural one-to-one correspondence between (T1 , S1 , T2 , S2 ) and U . To rewrite the variance in terms of U , we define the weight w(·) as follows. For a subgraph H ⊂ U and a tree L ∈ {T1 , S1 , T2 , S2 }, let B(L) ⊂ J denote the set of L’s branches, and define Y p wL (H) ≜ aut(J), w(H) ≜ wT1 (H)wS1 (H)wT2 (H)wS2 (H). (6.2) J∈B(L),J⊂H

We now verify that w(U ) = aut(T )aut(S). Since T ≃ T1 ≃ T2 and S ≃ S1 ≃ S2 , we have p aut(T )aut(S) = aut(T1 )aut(S1 )aut(T2 )aut(S2 ).

(6.3)

Moreover, since T1 is a tree with non-isomorphic branches, we have Y aut(T1 ) = aut(J), J∈B(T1 )

and the same p identity holds for S1 , T2 , and S2 . Therefore, the right-hand side of (6.3) equals the product of aut(J) over all branches J appearing in the four trees, which is precisely w(U ). 25

The next lemma applies the approximate factorization property of the Weingarten function from (4.6) and rewrites the variance bound in terms of decorated union graphs. For U = (T1 ∪S1 )∪n (T2 ∪S2 ), let C † (U ) = C(U ) \ C(T1 ∪ T2 ) × C(S1 ∪ S2 ) denote the set of alternating circuit decompositions, excluding those in which every circuit lies within either T1 ∪n T2 or S1 ∪n S2 . This exclusion corresponds to subtracting the mean square from the second moment. Lemma 6.1. For any i ̸= j ∈ [n], with ν = ν T from (5.2), we have X

Var(scoreii ) ≤

(U,c)∈Uii

Var(scoreij ) ≤

w(U )ρ2(2K−κ(c)) Wg(µ(c), d) +

: c∈C † (U )

poly(K) 2 ν , d

(6.4) (6.5)

w(U )ρ2(2K−κ(c)) Wg(µ(c), d).

(U,c)∈Uij

Proof. We consider true pairs (i = j) and false pairs (i ̸= j) separately. True pairs. Following from (6.1), for fixed labeled trees T1 , T2 , S1 , S2 , we compute the covariance Cov X T1 Y T2 , X S1 Y S2 = E X T1 Y T2 X S1 Y S2 − E X T1 Y T2 E X S1 Y S2 . (6.6) Let U = (T1 ∪ S1 ) ∪n (T2 ∪ S2 ). Applying the Weingarten calculus from Theorem 4.1, and noting that each of the four trees contains 2K edges, the second moment is given by X E X T1 Y T2 X S1 Y S2 = ρ2(2K−κ(c)) Wg(µ(c), d). (6.7) c∈C(U )

In addition, since T1 ∪n T2 and S1 ∪n S2 are simple graphs that do not contain 2-circuits, we have X E X T1 Y T2 E X S1 Y S2 = ρ4K Wg(µ(c1 ), d)Wg(µ(c2 ), d). (6.8) c1 ∈C(T1 ∪n T2 ) c2 ∈C(S1 ∪n S2 )

Combining (6.6), (6.7), and (6.8), and using the definition of C † (U ), we obtain X Cov X T1 Y T2 , X S1 Y S2 − ρ2(2K−κ(c)) Wg(µ(c), d) c∈C † (U )

ρ4K [Wg(µ(c1 ∪ c2 ), d) − Wg(µ(c1 ), d)Wg(µ(c2 ), d)]

c1 ∈C(T1 ∪n T2 ) c2 ∈C(S1 ∪n S2 )

≤

poly(K) d

ρ4K |Wg(µ(c1 ), d)| |Wg(µ(c2 ), d)| ,

(6.9)

c1 ∈C(T1 ∪n T2 ) c2 ∈C(S1 ∪n S2 )

where the last inequality follows from the approximate factorization of the Weingarten function in (4.6). Summing (6.9) over T, S ∈ T , and then over T1 , T2 ∼ = T , S1 , S2 ∼ = S (equivalently, over all possible decorated union graphs U ), and using w(U ) = aut(T )aut(S), we conclude that Var(scoreii ) ≤

w(U )ρ2(2K−κ(c)) Wg(µ(c), d) +

(U,c)∈Uii : c∈C † (U )

poly(K) 2 ν . d

False pairs. For i = ̸ j, it suffices to bound the variance by the second moment. Summing (6.7) over all decorated union graphs U yields X Var(scoreij ) ≤ w(U )ρ2(2K−κ(c)) Wg(µ(c), d). (6.10) (U,c)∈Uij

Introducing such decorated union graphs will also simplify the subsequent counting by allowing us to first count the union graph and then retrieve the individual trees via edge decorations.

6.1

Decomposition of Decorated Union Graphs

The approximate factorization of the Weingarten function in (4.6) allows us to apply a divide-andconquer strategy: we decompose each (U, c) into edge-disjoint components and study them separately. Specifically, we consider U = Uo ∪ Ug and c = co ∪ cg , where first component, (Uo , co ), is the fully overlapping part, and the second, (Ug , cg ), is the grafted part. The fully overlapping part consists of those branches that fully overlap between exactly two of the four trees and whose circuit decomposition contains only 2- or 4-circuits. As illustrated in Figure 5, two rooted branches are said to be fully overlapping in (U, c) if they share the same root node and one of the following holds: (i) Monochromatic case. There are two parallel edges of the same color between each pair of adjacent n-node and d-node. These edges form only 2-circuits. The two rooted branches are decorated by either (T1 , S1 ) or (T2 , S2 ). (ii) Bichromatic case. There are two parallel pairs of edges between each pair of adjacent n-nodes. Within each edge pair, the two edges have the same color and share a common d-node, whereas the two edge pairs have different colors and distinct d-nodes. In this case, these edges form only 4-circuits. We further distinguish the cross-isomorphism pairs (T1 , S2 ) or (T2 , S1 ), and the within-isomorphism pairs (T1 , T2 ) or (S1 , S2 ).

T1 root i

S1 j

S2 i=j

(a) Monochromatic (T1 , S1 ) (b) Monochromatic (T2 , S2 )

i=j

(d) Bichromatic within-isomorphism (T1 , T2 )

Figure 5: Different cases of fully overlapping branches.

We define Uo as the union of all branches in U that fully overlap between exactly two of the four trees, and co as the set of circuits in Uo (all of length 2 or 4). The grafted part is then defined by 27

Ug = U \ Uo and cg = c \ co , consisting of the remaining branches of the four trees that do not fully overlap with one another. We provide some intuition for this decomposition. The fully overlapping part Uo consists of branches taken directly from J , which allows for a more precise and explicit counting. The grafted part Ug , by contrast, requires a more delicate analysis: unlike in Uo , the branches here intertwine without fully overlapping, leading to more intricate union structures. However, an important observation that facilitates counting is that each branch in the grafted part either shares nodes with other branches or participates in longer circuits, which helps constrain the number of admissible grafted structures. We now introduce parameters describing each part, as illustrated in Figure 6. Let Uo (r, m, s) denote the set of fully overlapping parts (Uo , co ) containing a total of r fully overlapping branch pairs, among which m are monochromatic pairs and s are bichromatic cross-isomorphism pairs. Let Ug (ℓ) denote the set of grafted parts (Ug , cg ) containing ℓ branches in total from the four trees T1 , T2 , S1 , S2 . Given (U, c) ∈ U, its two parts (Uo , co ) and (Ug , cg ) belong to some pair of Uo (r, m, s) and Ug (ℓ), respectively, where r, ℓ satisfy (6.11)

2r + ℓ = 4D,

since the four trees contain 4D branches in total, while Uo and Ug contain 2r and ℓ branches, respectively. T1

S2 (Ug , cg ): ℓ grafted branches

... u

v a root i = j

...

m monochromatic pairs

(Uo , co ): r fully overlapping branch pairs

...

s bichromatic cross-isomorphism

(r − m − s) bichromatic within-isomorphism

Figure 6: Schematic illustration of decomposition of a decorated union (U, c).

With this notation, we decompose the variance into contributions from the fully overlapping part and the grafted part. Specifically, with the weight w(·) defined in (6.2), we define Overlap(r, m, s) =

1 2 |T | (ndρ2 )rM

w(Uo )ρ2(rM −κ(co )) |Wg(µ(co ), d)| ,

(Uo ,co )∈Uo (r,m,s)

(6.12)

Graft(ℓ) =

(ndρ2 )ℓM/2

(6.13)

w(Ug )ρ2(ℓM/2−κ(cg )) |Wg(µ(cg ), d)| ,

(Ug ,cg )∈Ug (ℓ)

with the conventions Overlap(0, 0, 0) = Graft(0) = 1. The next lemma formalizes this decomposition. Lemma 6.2. For Overlap(r, m, s) and Graft(ℓ) defined in (6.12) and (6.13), we have Var(scoreii ) ≤ (1 + o(1)) |T |2 (ndρ2 )2K Var(scoreij ) ≤ (1 + o(1)) |T |2 (ndρ2 )2K

Overlap(r, m, s)Graft(ℓ) +

r≥m,s≥0, ℓ≥0 2r+ℓ=4D m+s+ℓ≥1

Overlap(r, m, 0)Graft(ℓ),

poly(K) , d

∀j ̸= i.

r=m≥0, ℓ≥0 2m+ℓ=4D

Proof. We consider true pairs (i = j) and false pairs (i ̸= j) separately. True pairs. For i = j, we recall the bound on Var(scoreii ) from (6.4). Every (U, c) ∈ Uii admits a decomposition into (Uo , co ) ∈ Uo (r, m, s) and (Ug , cg ) ∈ Ug (ℓ). The condition c ∈ C † (U ) requires that at least one circuit contain edges with decorations from both {T1 , T2 } and {S1 , S2 }, rather than lying within either T1 ∪n T2 or S1 ∪n S2 . This is only possible if the parameters satisfy (6.14)

m + s + ℓ ≥ 1.

Otherwise, when m = s = ℓ = 0, every branch of U belongs to a bichromatic within-isomorphism fully overlapping pair, and therefore every circuit of U lies entirely within either T1 ∪n T2 or S1 ∪n S2 . Since Uo and Ug are edge-disjoint and each branch of the four trees belongs to exactly one of them, the weight factorizes as w(U ) = w(Uo )w(Ug ). Using κ(c) = κ(co ) + κ(cg ) and 2K = rM + ℓM/2 from (6.11), we split the factor (ρ2 )2K−κ(c) = (ρ2 )rM −κ(co ) · (ρ2 )ℓM/2−κ(cg ) . Furthermore, the approximate factorization property in (4.6) yields |Wg(µ(c), d)| ≤ (1 + o(1)) |Wg(µ(co ), d)| |Wg(µ(cg ), d)| . Combining them and summing over (r, s, ℓ) satisfying (6.11) and (6.14), we may bound (6.4) as   X X  Var(scoreii ) ≤ (1 + o(1)) w(Uo )ρ2(rM −κ(co )) |Wg(µ(co ), d)| r≥m,s≥0, ℓ≥0 2r+ℓ=4D m+s+ℓ≥1

(Uo ,co )∈Uo (r,m,s)

 ×

 X

(Ug ,cg )∈Ug (ℓ)

poly(K) 2 w(Ug )ρ2(ℓM/2−κ(cg )) |Wg(µ(cg ), d)| + ν . d

Finally, dividing both sides by |T |2 (ndρ2 )2K = |T |2 (ndρ2 )rM · (ndρ2 )ℓM/2 , recalling Overlap(r, m, s) and Graft(ℓ) defined in (6.12) and (6.13), and using ν = (1 + o(1))|T |(ndρ2 )K from Proposition 5.1, we obtain the claimed bound. 29

False pairs. For i = ̸ j, bichromatic overlapping branches cannot occur by definition, since branches of different colors are rooted at distinct vertices. Thus, we must have r = m and s = 0; by (6.11), (6.15)

2m + ℓ = 4D.

The remainder of the argument is the same as the true-pair case. We decompose each (U, c) ∈ Uij into (Uo , co ) ∈ Uo (r, m, s) and (Ug , cg ) ∈ Ug (ℓ), apply the factorizations, and finally normalize by |T |2 (ndρ2 )2K . By (6.5), with the additional constraint in (6.15), we obtain Var(scoreij ) ≤ (1 + o(1)) |T |2 (ndρ2 )2K

(6.16)

Overlap(r, m, 0)Graft(ℓ).

r=m≥0, ℓ≥0 2m+ℓ=4D

By Lemma 6.2, it suffices to bound Overlap(r, m, s) and Graft(ℓ) separately. The results are given in Propositions 6.1 and 6.2. Proposition 6.1 (Fully overlapping part). Suppose that β M |J | ≥ 7D2 . For any 0 ≤ m ≤ r and 0 ≤ s ≤ r, Overlap(r, m, s) defined in (6.12) satisfies: √ mM β Overlap(r, m, s) ≤ C β sM/2 . ρ2 √ By Proposition 6.1, if ρ2 > β, the bound on Overlap(r, m, s) decays geometrically in both the number of monochromatic pairs m and the number of bichromatic cross-isomorphism pairs s. Proposition 6.2 (Grafted part). For any ℓ ≥ 0, Graft(ℓ) defined in (6.13) satisfies Graft(ℓ) ≤ C

poly(K) min{d, n}

ℓ/8 .

By Proposition 6.2, the upper bound on Graft(ℓ) decays geometrically as the number of grafted branches ℓ increases. In what follows, we first combine Propositions 6.1 and 6.2 to complete the proof of Proposition 3.2. We then analyze the more intricate grafted part in Section 6.3, and the fully overlapping part in Section 6.4.

6.2

Proof of Proposition 3.2

We now combine Propositions 6.1 and 6.2 to prove Proposition 3.2. True pairs. We first prove (3.2) for true pairs i = j. Proof of (3.2). Substituting Propositions 6.1 and 6.2 into Lemma 6.2, when ρ2 > Var(scoreii ) ≤ (1 + o(1)) |T |2 (ndρ2 )2K

≤C

Overlap(r, m, s)Graft(ℓ) +

r≥m,s≥0, ℓ≥0 2r+ℓ=4D m+s+ℓ≥1 √ mM

m,s,ℓ≥0 m+s+ℓ≥1

ρ2

sM/2

poly(K) min{d, n}

ℓ/8 +

√

β, we obtain

poly(K) d

" √ M # β poly(K) 1/8 ≤C + , ρ2 min{d, n}

(6.17)

P where the last inequality follows from m,s,ℓ≥0,m+s+ℓ≥1 xm y s z ℓ = 1/[(1 − x)(1 − y)(1 − z)] − 1 ≤ √ 14(x + y + z)/3 when x = ( β/ρ2 )M , y = β M/2 , and z = (poly(K)/ min{d, n})1/8 satisfy x, y, z ∈ [0, 1/2]; and y ≤ x. False pairs. We now prove (3.3) for false pairs i ̸= j. Proof of (3.3). Substituting Propositions 6.1 and 6.2 into Lemma 6.2, when ρ2 > Var(scoreij ) ≤ (1 + o(1)) |T |2 (ndρ2 )2K

≤C

ρ2 (

≤ C(2D + 1) max

β, we have

Overlap(r, m, 0)Graft(ℓ)

r=m≥0, ℓ≥0 2m+ℓ=4D √ mM

m,ℓ≥0 2m+ℓ=4D

√

β ρ4

poly(K) min{d, n}

ℓ/8

K ) poly(K) D/2 , , min{d, n}

(6.18)

P where the last inequality follows by applying m,ℓ≥0,2m+ℓ=4D x2m y ℓ ≤ (2D + 1) max{x, y}4D for √ x, y > 0 with x = ( β/ρ2 )M/2 and y = (poly(K)/ min{d, n})1/8 , where K = M D.

6.3

Bounding the Grafted Part

In this section, we prove Proposition 6.2. A key step is to bound |Ug (ℓ)| by counting the admissible grafted parts Ug and, for each such part, the corresponding alternating circuit decompositions. Throughout the counting argument, we will keep track of the following two types of nodes. Definition 6.1 (Overdecorated node). We say an n-node, u, is overdecorated if u’s incident edges carry at least 3 different decorations from the set {S1 , S2 , T1 , T2 }, and there is at least one tree in {S1 , S2 , T1 , T2 } for which u is not the root. We use o to denote the number of overdecorated nodes. Definition 6.2 (Crossroad node). We say a d-node, a, is a crossroad node with respect to a circuit decomposition c if a has degree 4 and participates in at least one circuit of size ≥ 4 in c. We use x to denote the number of crossroad nodes. Collectively, we refer to overdecorated and crossroad nodes as graft witness nodes. Consider, for example, the grafted part in Figure 6. The node a is a crossroad node. Moreover, the edge pairs corresponding to (u, w), (w, v), (v, t), and (t, u) form an alternating circuit of length 8. Thus, each of the four grafted branches contains an edge lying in an alternating circuit of length greater than 4. More generally, the size and structural complexity of the grafted part can be controlled by the numbers of overdecorated nodes, crossroad nodes, and edges lying in alternating circuits of length greater than 4. The following lemma gives one concrete formulation of this observation; we will use more later. Lemma 6.3. For any (Ug , c) with ℓ grafted branches, κ 2-circuits, µ1 4-circuits, o overdecorated nodes and x crossroad nodes, ℓ ≤ 4 (ℓM/2 − κ/2 − µ1 + o + x) . 31

Proof. Fix a pair (Ug , c). The total number of edges (counted with multiplicity) in Ug is 2ℓM , of which 2ℓM − 2κ − 4µ1 belong to circuits of length > 4. Hence, there are at most 2ℓM − 2κ − 4µ1 branches that include an edge participating in a circuit of length > 4. We now show that every other grafted branch must correspond to a graft witness node. Consider a branch J from, say, T1 , in which all edges participate in circuits of length ≤ 4. Let Ve (J) be the node set including all n-nodes and d-nodes in J and all d-nodes that lie in 4-circuits involving edges in J. We claim that if Ve (J) \ {root(J)} has no graft witness nodes, then J is actually not a grafted branch. Indeed, consider any pair of edges (u, a), (v, a) from J (with u, v ∈ [n] and a ∈ [d]). 1. If a has degree 2 in Ug , the fact that all circuits are of length at most 4 implies that (u, a), (v, a) are in a 4-circuit with blue edges (u, a′ ), (v, a′ ). If a′ has degree 4, since its incident edges (u, a′ ), (v, a′ ) appear in a 4-circuit, it must be a crossroad node by definition. Therefore, a′ must have degree 2 and the edges (u, a′ ), (v, a′ ) are decorated by some Ruv ∈ {S2 , T2 }. 2. Otherwise, if a has degree 4 in Ug , the lack of crossroad nodes implies that (u, a), (v, a) is covered by two 2-circuits with edges (u, a), (v, a) of decoration Ruv = S1 . In both cases, we may map each pair of edges (u, a), (v, a) in J to an edge (u, v) in a tree J map on n-nodes which is decorated with two decorations, T1 and Ruv . Now, if there exist some (u, v) and (u′ , v ′ ) such that Ruv ̸= Ru′ v′ , take a path in J map from u to u′ (such a path must exist because J was connected). Since the first endpoint is decorated with T1 , Ruv and the second endpoint is decorated with T1 , Ru′ v′ , at least one non-root n-node in this path has to be incident to edges of three types of labels within J. But then this n-node would be overdecorated, a contradiction. Hence Ruv = R for all edges (u, v), so J completely overlaps with a branch B decorated by R. Moreover, branches J and B must share the same root; otherwise, the root of B would appear as a non-root node in J whose incident edges carry at least 3 distinct decorations, and hence would be overdecorated. Thus, if Ve (J) \ {root(J)} has no graft witness nodes, then J and B form a fully-overlapping branch pair. Therefore, we charge every grafted branch J containing no edge in a circuit of length > 4 to a graft witness node in Ve (J) \ {root(J)}. Each overdecorated node can be charged at most four times, since it belongs to at most one such branch in each of the four trees. Moreover, each crossroad node belongs to V (J) for at most two branches J, and hence to Ve (J) for at most four branches J. Thus, each graft witness node is charged at most four times, giving at most 4(o + x) such branches. Combining this with the previous bound completes the proof. The following lemma is another example by which the graft witness nodes allow us to control the structure of the grafted part. Here Vn (T1 ) (resp. Vn (S1 )) denotes the set of n-nodes incident to T1 -decorated edges (resp. S1 -decorated edges) in Ug . Lemma 6.4. For any (Ug , c) with o overdecorated nodes, x crossroad nodes, and κ1 red 2-circuits, |Vn (T1 ) ∩ Vn (S1 ) \ {i}| ≤ o + x + κ1 /2.

(6.19)

Proof. We prove the result by constructing a one-to-one map from the set of nodes u ∈ Vn (T1 )∩Vn (S1 ) with u = ̸ i to the union of the set of overdecorated nodes, the set of crossroad nodes, and the set of pairs of red 2-circuits that share a d-vertex in S1 . Fix such a node u. If u is overdecorated, we map u to itself. Suppose next that u is not overdecorated. Then by virtue of being in S1 ∩ T1 it is incident only to red edges, and must participate exclusively in red 2-circuits. By assumption u is not the root node, so let a ∈ [d] be the parent of u in S1 , and let v ∈ [n] be the parent of a in S1 . If a is a crossroad node, we map u to a. No other n-node has parent a in S1 . If a is not a crossroad node, then both (u, a) and (v, a) must 32

be in red 2-circuits. We map u to the pair of red 2-circuits formed by these two edges. No other n-node has the same pair of parent edges. On the other hand, a straightforward counting argument shows that when there are many overdecorated and crossroad nodes, there are fewer ways to label the vertices. This will allow us to account for the combinatorial complexity of the many possible grafted configurations. Lemma 6.5. For any (Ug , c) with ℓ grafted branches, κ 2-circuits, o overdecorated nodes, and x crossroad nodes, the following bounds hold: |Vn (Ug ) \ {i, j}| ≤ ℓM/2 − o/2,

(6.20)

|Vd (Ug )| ≤ ℓM − (κ + x)/2.

(6.21)

Proof. Both statements are a consequence of simple accounting. To prove (6.20), let m(u) be the number of trees in {S1 , T1 , S2 , T2 } that contain node u as a non-root. Since each branch contains M n-nodes, and because a valid circuit decomposition requires m(u) ≥ 2 for each node u appearing as a non-root, X 2|Vn (Ug ) \ {i, j}| + |{u ̸∈ {i, j} : m(u) ≥ 3}| + m(i) + m(j) ≤ m(u) = ℓM. u

By definition of overdecorated nodes, o ≤ |{u : m(u) ≥ 3}| + m(i) + m(j). Hence 2|Vn (Ug ) \ {i, j}| + o ≤ ℓM And rearranging gives (6.20). To prove (6.21), let D4 be the set of d-nodes in Ug of degree 4. Since every d node has degree 2 before taking the union and degree 2 or 4 in Ug , X 2ℓM = deg(a) = 2|Vd (Ug )| + 2|D4 | =⇒ |D4 | = ℓM − |Vd (Ug )|. a∈Vd (Ug )

Now, each crossroad node has degree 4 and is part of D4 . There are also at least (κ − x)/2 degree-4 non-crossroad nodes, because there are at least κ − x 2-circuits which are not incident on any crossroad node (each crossroad node can be incident on at most one 2-circuit) but must be incident to a d-node of degree 4, and any non-crossroad node of degree 4 is incident on two 2-circuits. Therefore |D4 | ≥ x + (κ − x)/2 ≥ (κ + x)/2. Combining this with the previous display gives (6.21). 6.3.1

Counting the Grafted Part

We now give an upper bound on the number of pairs (Ug , c) with a given number of 2- and 4-circuits and a given number of graft witness nodes. We will first construct the union of S1 , T1 and the red 2-circuits, then appeal to Lemma 5.1 as we did for the mean calculation to add in the structure of S2 , T2 and the alternating circuits, and finally add in the blue 2-circuits (whose admissible locations will be constrained by the graft witness nodes, as we shall soon see). Lemma 6.6. Let Ug (ℓ, κ, µ1 , o, x) denote the set of all pairs (Ug , c) with ℓ grafted branches, κ 2-circuits, µ1 4-circuits, o overdecorated nodes and x crossroad nodes. Then there exists a universal constant C such that for all n sufficiently large, for any ℓ, κ, µ1 , o, x ∈ N, ℓM CK 12 o/2 CK 12 x/2 C κ/2 4 1/2 |Ug (ℓ, κ, µ1 , o, x)| ≤ CK Cn d (CK)ℓM −κ−2µ1 . n d d 33

Proof. The proof will be via an encoding argument. As in our bounds for the expectation in Proposition 5.1, we will start by encoding the structure of the red part, and then simultaneously encode the alternating circuit decomposition and blue part. The red part. We first encode the configuration of the red part, T1 ∪ S1 . Let v1 + 1 denote the number of n-nodes (including the root) in S1 ∪ T1 . Since T1 and S1 are trees sharing a common root i, the graph T1 ∪ S1 is connected and must admit a rooted spanning tree. We choose an arbitrary minimum spanning tree of its v1 + 1 n-nodes, for which there are at most Cα−(v1 +1) choices; each edge in this spanning tree is subdivided into two edges by adding a d-node in the middle. Next, we record the location of the remaining red edges. We first place the m remaining red edges, treating each 2-circuit as a single edge, and then specify which red edges to double to form the red 2-circuits. There are fewer than 10K nodes in the union of all 4 trees, and the number of possible simple edges between them is at most (10K)2 . Hence there are at most (10K)2m ways to add the m red edges. It remains to specify which edges are doubled to create the red 2-circuits. Since there are at most 2ℓM red edges in total, this can be done in at most 22ℓM ways. Finally, given any graph constructed above, we specify the pairing of all red edges in circuits of length > 2 so that each pair shares a common d-node. At each d-node of degree 2, the pairing is uniquely determined. The only nontrivial choices arise at d-nodes of degree 4 that are not exclusively incident to red 2-circuits. By definition, these are the crossroad nodes, and there are at most x of them. At each crossroad node, the four incident edges are partitioned into two unordered pairs. The number of such pairings is 42 /2 = 3. Hence, the total number of possible pairings is at most 3x . Hence, the total number of possible S1 ∪ T1 structures is no more than Cα−(v1 +1) · (10K)2m · 22ℓM · 3x . We now claim that m ≤ 2(o + x). To see this, let e1 and κ1 denote, respectively, the number of red edges in S1 ∪ T1 counted with multiplicity, and the number of red 2-circuits. The spanning tree constructed in the first step contains exactly 2v1 red edges, so in the second step we must first place m = e1 − 2v1 − κ1 remaining red edges, treating each 2-circuit as a single edge. Note that the number of n-nodes common to S1 and T1 is exactly |Vn (S1 ) ∩ Vn (T1 ) \ {i}| = e1 /2 − v1 . Indeed, the e1 red edges form the two trees S1 and T1 rooted at i; since half of the non-root nodes are n-nodes and half are d-nodes, we have |Vn (S1 ) \ {i}| + |Vn (T1 ) \ {i}| = e1 /2. Moreover, the union of S1 and T1 satisfies |Vn (S1 ) ∪ Vn (T1 ) \ {i}| = v1 by definition. Thus, by the inclusion–exclusion principle, we immediately have |Vn (S1 ) ∩ Vn (T1 ) \ {i}| = e1 /2 − v1 . By (6.19), this quantity satisfies e1 /2 − v1 ≤ o + x + κ1 /2. Consequently, m = e1 − 2v1 − κ1 ≤ 2(o + x). Moreover, by (6.20), v1 ≤ ℓM/2. Hence, the number of possible encodings of union structures S1 ∪ T1 is bounded by X α−(v1 +1) · (10K)2m · 22ℓM · 3x ≤ Cα−ℓM/2 (10K)4(o+x) 22ℓM 3x , v1 ≤ℓM/2 m≤2(o+x)

for C a sufficiently large constant. Blue edges and alternating circuit decompositions. As was done in the bound on the expectation, we now simultaneously encode the alternating circuit decompositions and the structure of blue edges participating in circuits of length ≥ 4. First we order the paired red edges to form alternating circuits of length ≥ 4. In all of the circuits of length ≥ 4 there are 2ℓM − 2κ ≤ 8K red and blue edges in total, of which 4µ1 lie in 4-circuits. 34

By Lemma 5.1, the number of ways to form these alternating circuits is at most (4K)2(ℓM/2−κ/2−µ1 ) . These ordered pairs also determine the blue edges in these alternating circuits. Now, we specify the location of the blue 2-circuits. Since each 2-circuit corresponds to a pair of identical edges, one from S2 and one from T2 , we may consider the graph induced by the blue 2-circuits in T2 , and note that it is a forest. We first encode the structure of this forest. The work [PS79] establishes the asymptotic number of unlabeled forests on p nodes as Fp ∼ Cp−5/2 α−p . Hence P −2ℓM . the number of unlabeled forests on at most ℓM edges is upper bounded by 2ℓM p=2 Fp ≤ Cα Next, we must specify how the blue 2-circuit forest is attached to the rest of the graph. We will encode the attachment point nodes in the 2-circuit forest, the attachment point nodes in the rest, and the correspondence between them. To see how many such encodings there are, note that if u is a non-root n-node which appears in both the blue 2-circuit forest and in the rest, it must appear in both T2 and S2 (by virtue of participating in a blue 2-circuit) and in at least one of T1 and S1 through an alternating circuit, so u must be an overdecorated node. If a is a d-node which appears in both the blue 2-circuit forest and the rest, it must be incident on both a 2-circuit and on a circuit of length ≥ 4, so a is a crossroad node. All these nodes are graft witness nodes. Therefore, after including the possible two roots, their total number is at most o + x + 2. Because there are at most 5K nodes in the 2-circuit forest and at most 5K nodes in the rest, there are at P 5K 2 most o+x+2 j! ≤ (5K)2(o+x+2) ways to encode the attachment. j=0 j Edge decorations and node labeling. It remains to encode the edge decorations and the node labels. We encode for each red edge whether it is decorated by T1 or S1 , and for each blue edge whether it is decorated by T2 or S2 . Since there are 2ℓM edges in total, the number of encodings is at most 22ℓM . Finally, we encode the labels of the n-nodes and d-nodes. The root nodes i and j are uniquely determined since each is incident to D red and blue edges, respectively. Thus, it suffices to encode the labels of the remaining nodes. By (6.20) and (6.21), there are at most (ℓM/2 − o/2) n-nodes and (ℓM − κ/2 − x/2) d-nodes. Thus, the number of possible labelings is at most nℓM/2−o/2 dℓM −κ/2−x/2 . Multiplying the bounds together yields that the number of such encodings, and thus grafted parts, satisfies ℓM CK 12 o/2 CK 12 x/2 1 κ/2 4 1/2 |Ug (ℓ, κ, µ1 , o, x)| ≤ CK Cn d (CK)ℓM −κ−2µ1 , n d d for C a sufficiently large universal constant (depending on α). We are now ready to prove Proposition 6.2 using Lemma 6.6. Proof of Proposition 6.2. Consider any grafted part with ℓ branches, that is, U ∈ Ug (ℓ). Since each branch J ⊂ J satisfies aut(J) ≤ exp(CM ), it follows from the definition that w(U ) ≤ exp(CℓM ). Thus, the definition of Graft(ℓ) in (6.13) yields Graft(ℓ) ≤

exp(CℓM ) ℓM/2 n dℓM/2 ρℓM

X (U,c)∈Ug (ℓ)

ρ2(ℓM/2−κ(c)) |Wg(µ(c), d)| .

(6.22)

Here U contains 2ℓM edges in total. We now consider the grafted parts with fixed parameters κ, µ1 , o, and x. For any (U, c) ∈ Ug (ℓ, κ, µ1 , o, x), by (4.8), we have 2(ℓM/2−κ(c))

2 ℓM/2−κ/2 ℓM/2−κ/2−µ1 4 ρ |Wg(µ(c), d)| ≤ (1 + o(1)) . d d

Note that the parameters must satisfy 2κ + 4µ1 ≤ 2ℓM since the total number of edges is 2ℓM . We define a ≜ ℓ/4 − (ℓM/2 − κ/2 − µ1 ) as the lower bound on o + x given in Lemma 6.3. Then, summing over all possible choices of these parameters yields X ρ2(ℓM/2−κ(c)) |Wg(µ(c), d)| (U,c)∈Ug (ℓ)

≤

X κ,µ1 ≥0 κ+2µ1 ≤ℓM

2 ℓM/2−κ/2 ℓM/2−κ/2−µ1 4 ρ d d

(6.23)

|Ug (ℓ, κ, µ1 , o, x)| .

o,x≥0 o+x≥max{a,0}

Fix κ and µ1 and recall that Lemma 6.6 provides a bound on |Ug (ℓ, κ, µ1 , o, x)|. Substituting the bound, we obtain X |Ug (ℓ, κ, µ1 , o, x)| o,x≥0 o+x≥max{a,0} 4

≤ CK C

ℓM ℓM/2 ℓM −κ/2

(CK)

ℓM −κ−2µ1

o,x≥0 o+x≥max{a,0} 4 ℓM/2 ℓM −κ/2

≤ CK n

poly(K) min{d, n}

ℓ/8

poly(K) min{d, n}

CK 12 n

o/2

CK 12 d

x/2

−(ℓM/4−κ/4−µ1 /2) .

(6.24)

Here the last line follows from C M = poly(K) and

X o,x≥0 o+x≥max{a,0}

CK 12 n

o/2

CK 12 d

x/2

≤

max{a,0}≤t≤6K

≤2

CK 13 min{d, n}

t/2

max{a,0}/2 ,

where the first inequality holds since t = o + x ≤ 6K, the total number of nodes, and there are at most 6K + 1 ways to split t into o and x, and the last inequality follows by bounding the sum with a geometric series (since CK 13 /min{d, n} ≤ 1/2) and cancelling the factor (CK)ℓM −κ−2µ1 . Substituting (6.24) into (6.23), we have X ρ2(ℓM/2−κ(c)) |Wg(µ(c), d)| (U,c)∈Ug (ℓ) 4 ℓM/2 ℓM/2 ℓM

≤ CK n

4 ℓM/2 ℓM/2 ℓM

≤ CK n

poly(K) min{d, n}

ℓ/8

poly(K) min{d, n}

ℓ/8

X κ,µ1 ≥0 κ+2µ1 ≤ℓM

−κ

ℓM/4−κ/4−µ1 /2 4 d (6.25)

where the last line follows from ρ−κ ≤ ρ−ℓM = poly(K)ℓ and X κ,µ1 ≥0 κ+2µ1 ≤ℓM

ℓM/4−κ/4−µ1 /2 X 4 8K a ≤ ≤2 d d a≥0

since there are at most ℓM ≤ 2K number of ways to split each a = κ + 2µ1 into κ and µ1 . Finally, combining (6.22) and (6.25), since eM = poly(K), if ℓ > 1, we conclude that Graft(ℓ) ≤ C

6.4

poly(K) min{d, n}

ℓ/8 .

Bounding the Fully Overlapping Part

This section proves Proposition 6.1 for the fully overlapping part. Since the overlapping branches are taken directly from J and preserve a tree structure, we can perform a more explicit counting by analyzing how many non-isomorphic branches can appear, how they may be decorated, and how the nodes are labeled. Proof of Proposition 6.1. Consider any (U, c) ∈ Uo (r, m, s). Recall that U contains r fully overlapping branch pairs, among which m are monochromatic pairs and s are bichromatic cross-isomorphism pairs. Then U contains 4rM edges in total (counting multi-edges with multiplicity), and c contains 2mM 2-circuits and (r − m)M 4-circuits. Thus, by (4.8), such c satisfies ρ2(rM −κ(c)) |Wg(µ(c), d)| ≤ (1 + o(1))

2 (r−m)M ρ . d

Substituting this bound into (6.12), we have Overlap(r, m, s) ≤ It therefore suffices to bound the labelings of their nodes.

1 + o(1) 2 rM |T | n d(2r−m)M ρ2mM

w(U ).

(6.26)

(U,c)∈Uo (r,m,s)

(U,c)∈Uo (r,m,s) w(U ). We first count the unlabeled graphs and then

Counting unlabeled graphs. Suppose that the r fully overlapping branch pairs involve r′ non-isomorphic pairs. Since each non-isomorphic branch can appear in at most two overlapping pairs (there are four trees in total), we have r/2 ≤ r′ ≤ r. Moreover, since each of the m + s monochromatic and bichromatic cross-isomorphism pairs has one decoration from {T1 , T2 } and the other from {S1 , S2 }, the unlabeled trees T and S must share at least (m + s)/2 isomorphic branches. Consequently, r′ ≤ 2D − (m + s)/2. Let R(r) = min{r, 2D − (m + s)/2}. We obtain r/2 ≤ r′ ≤ R(r).

(6.27)

Among the r′ non-isomorphic branch pairs: r − r′ pairs appear twice among the four trees, and

2r′ − r appear once. Thus, the number of choices for these unlabeled branch templates is at most

′ |J | r . r′ r − r′

We now decorate the branches. Since each branch appearing twice must receive complementary decorations across its two copies, it suffices to decorate the r′ non-isomorphic branches. Among these, 2r′ − r appear only once. Of these, at least (r′ − D) ∨ 0 must be decorated by (T1 , T2 ), and at least (r′ − D) ∨ 0 by (S1 , S2 ), because each of T and S contains at most D branches. The remaining 4 branches each admit at most 2 = 6 possible decoration choices. Thus, for each of the trees above, the number of decorations is at most 2r′ − r ′ ′ 6(2D−r )∧r . (r′ − D) ∨ 0, (r′ − D) ∨ 0, (2D − r) ∧ (2r′ − r) The decorations also determine the parallel edges in the branches. Monochromatic branches decorated by (T1 , S1 ) or (T2 , S2 ) contain two parallel edges between each pair of adjacent n-node and d-node, whereas bichromatic branches contain two parallel pairs of edges between each pair of adjacent n-nodes (see Figure 5 for an illustration). Note that the circuit decomposition is also uniquely determined by the unlabeled, decorated tree since by definition it consists of 2-circuits in monochromatic branches and 4-circuits in bichromatic branches. We define f (r′ , r) as the product of the two displayed expressions above ′ |J | r 2r′ − r ′ ′ ′ f (r , r) = 6(2D−r )∧r . (6.28) ′ ′ ′ ′ ′ r r−r (r − D) ∨ 0, (r − D) ∨ 0, (2D − r) ∧ (2r − r) Let Ueo (r, m, s) denote the set of unlabeled decorated graph-decomposition pairs. Then summing over all possible trees constructed above, it follows that X |Ueo (r, m, s)| ≤ f (r′ , r). (6.29) r/2≤r′ ≤R(r)

Lemma 6.7 will provide an upper bound on r/2≤r′ ≤R(r) f (r′ , r). Following from Lemma 6.7 and 2D − R(r) ≥ (m + s)/2 from (6.27), we have (m+s)/2 2 |J | 6D2 e ≤ 2|T |2 β (m+s)M/2 , (6.30) |Uo (r, m, s)| ≤ 2 D |J | − 2D | M ≥ 7D 2 /|J | ≥ 6D 2 /(|J | − 2D). where the last inequality uses |T | = |J D together with β P

Labeling the nodes. Fix an unlabeled graph. We now count the number of ways to label its nand d-nodes. Each of the r pairs of overlapping branches contains M distinct n-nodes. Moreover, among these r pairs, each of the m monochromatic pairs contains M d-nodes, while each of the r − m bichromatic pairs contains 2M d-nodes. Hence, there are rM n-nodes and (2r − m)M d-nodes in total. Hence, the number of possible node labelings is at most nrM d(2r−m)M choices. We now account for overcounting. Different node labelings may yield the same labeled graph if a permutation of the nodes preserves the graph structure. Recall that aut(J) denotes the number of node permutations that produce the same labeled graph for a branch J. Since U is a tree composed of branches, any permutation that preserves each branch necessarily preserves the entire tree. Hence, the number of node labelings that give Q rise to the same labeled graph U is at least the product of aut(J) over the branches, that is, J⊂J ,J⊂U aut(J). Recall from the definition of w(U ) in (6.2) p that it assigns a weight of aut(J) to each branch of the four trees in U . Since each branch of U appears in exactly two of the four trees, we have Y Y Y p w(U ) = aut(J) = aut(J). L∈{T1 ,S1 ,T2 ,S2 } J∈R(L),J⊂U

J⊂J ,J⊂U

In particular, the overcounting is at least w(U ). After dividing by this symmetry factor, the number of distinct labeled graphs is therefore at most nrM d(2r−m)M . w(U )

(6.31)

Combining (6.30) and (6.31), we have X

w(U ) ≤ Ueo (r, m, s)

(U,c)∈Uo (r,m,s)

w(U ) ×

nrM d(2r−m)M w(U )

(U,c)∈Ueo (r,m,s)

(6.32)

≤ 2nrM d(2r−m)M |T |2 β (m+s)M/2 . We further combine (6.26) and (6.32) and obtain Overlap(r, m, s) ≤ 2(1 + o(1))β (m+s)M/2 ρ−2mM .

Finally, we present the following auxiliary lemma to bound

′ r/2≤r′ ≤R(r) f (r , r) in (6.29).

Lemma 6.7. For any D, r, r′ ∈ N such that 0 ≤ r ≤ 2D, recall the definition of f (r′ , r) from (6.28). Fix R ≤ 2D. Then 2D−R 2 X 6D2 |J | ′ f (r , r) ≤ 2 . |J | − 2D D ′ r/2≤r ≤R

Proof. For any a, b ∈ N such that b/2 ≤ a ≤ b − 1 and b ≤ 2D, [MWXY25, Claim 3] shows that 6D2 1 f (a, b) ≤ ≤ , f (a + 1, b) |J | − 2D 2 and f (2D, 2D) ≤ X

f (a, a) ≤ 1, f (a, a + 1)

f (a, a) 6D2 ≤ , f (a + 1, a + 1) |J | − 2D

|J |2 . Then for fixed r, we have D

f (r′ , r) ≤ 2f (R, r) ≤ 2f (R, 2D)

r/2≤r′ ≤R

≤2

6D2 |J | − 2D

2D−R

f (2D, 2D) ≤ 2

6D2 |J | − 2D

2D−R 2 |J | , D

where the first inequality follows by summing over r′ and using f (a, b) ≤ f (a + 1, b)/2, the second inequality uses f (a, a) ≤ f (a, a+1), the third inequality follows from f (a, b) ≤ f (a+1, b)·6D2 /(|J |− |2 2D) and the last inequality uses f (2D, 2D) ≤ |J . D

Polynomial-Time Approximation via Color Coding

In this section, we provide a polynomial-time algorithm for approximating the similarity scores using the idea of color coding. The discussion follows closely that of [MWXY24, Section 4] and [MWXY25, Section 5]. Fix a rooted bipartite tree T ∈ T . We first approximate labelT (X, i) defined in (2.1). We view X as a weighted bipartite graph on vertex set [n] ⊔ [d], where the edge between u ∈ [n] and a ∈ [d] 39

has weight Xua . We generate a random coloring ϕ = (ϕn , ϕd ) as follows: ϕn : [n] → [K + 1] assigns to each n-node in X an independent uniformly random color from [K + 1], and ϕd : [d] → [K] assigns to each d-node an independent uniformly random color in [K]. For any V = Vn ⊔ Vd with Vn ⊂ [n] and Vd ⊂ [d], let χϕ (V ) denote the indicator that V is colorful under ϕ, meaning that ϕn (u) ̸= ϕn (v) for all distinct u, v ∈ Vn and ϕd (a) ̸= ϕd (b) for all distinct a, b ∈ Vd . If |Vn | = K + 1 and |Vd | = K, then P {χϕ (V ) = 1} =

(K + 1)! K! · ≜ p. (K + 1)K+1 K K

We define X

] T (X, i; ϕ) ≜ label

χϕ (V (T1 ))X T1 .

T1 ∼ =T root(T1 )=i

It follows that

i h ] T (X, i; ϕ) X = p · labelT (X, i). E label

] T (X, i; ϕ)/p is an unbiased estimator of labelT (X, i). Similarly, we also view Y as a Hence label weighted bipartite graph, generate a random coloring ψ on Y , and define X ] T (Y, j; ψ) ≜ label χψ (V (T2 ))Y T2 . T2 ∼ =T root(T2 )=j

Since T is a tree, color coding together with the recursive structure of T allows us to use ] T (X, i; ϕ) efficiently. This dynamic programming to count weighted colorful copies and compute label procedure is described in [MWXY24, Algorithm 2] for unrooted trees; with minor modifications, the same algorithm applies to rooted trees, as outlined in [MWXY25, Section 5]. The algorithm takes a weighted host graph on [n] as input. For the rooted bipartite trees considered here, we apply it to the bipartite weighted host graphs induced by X and Y . To reduce the variance, we generate independent colorings ϕ1 , · · · , ϕt with t ≜ ⌈1/p⌉, and define [ T (X, i) ≜ 1 label tp

t X

] T (X, i; ϕs ). label

(7.1)

s=1

[ T (Y, j). We then define the Similarly, using independent colorings ψ1 , · · · , ψt for Y , we define label approximate similarity score X [ T (X, i) · label [ T (Y, j). score [ ij ≜ aut(T ) · label (7.2) T ∈T

Then E score [ ij X, Y = scoreij . The procedure is summarized as Algorithm 2.

Algorithm 2: Approximation of similarity scores via color coding Input: Data matrices X and Y and integers M , D 1 Construct J as specified in Definition 2.1: first use the algorithms of [BH80, CB81] to construct rooted trees on [n] with M edges, root degree 1, and at most exp(CM ) automorphisms; then subdivide each edge by inserting a d-node. 2 Construct T using J according to Definition 2.2. 3 Generate i.i.d. random colorings {ϕs }ts=1 and {ψs }ts=1 . 4 for each T ∈ T do 5 for each s = 1, · · · , t do ] T (X, i; ϕs )}i∈[n] , {label ] T (Y, j; ψs )}j∈[n] via [MWXY24, Algorithm 2]. 6 Compute {label 7

[ T (X, i)}i∈[n] and {label [ T (Y, j)}j∈[n] via (7.1). Compute {label Output: {score [ ij }i,j∈[n] according to (7.2).

Finally, we prove Proposition 2.1 by showing that Algorithm 2 runs in polynomial time and that Theorem 2.1 continues to hold with score [ ij in place of scoreij . Proof. We analyze the time complexity and control the variance in turn. Time complexity. We first show that Algorithm 2 outputs {score [ ij }i,j∈[n] in polynomial time. The algorithm in [BH80] generates all non-isomorphic rooted trees with M edges in time O(α−M ). Moreover, for each such rooted tree, the algorithm in [CB81] computes the number of automorphisms −M in time O(M ). Hence, the total time complexity to generate J is O(M α ). Given J , the time | required to construct T is O |J = O(|T |). D ] T (X, i; ϕs )}i∈[n] and As discussed above, we apply [MWXY24, Algorithm 2] to compute {label ] T (Y, j; ψs )}j∈[n] for all T ∈ T and s ∈ [t]. Since t = ⌈1/p⌉ = e2K , [MWXY24, Lemma 2] implies {label [ T (X, i)}i∈[n] and {label [ T (Y, j)}j∈[n] is O(|T |K(3e)2K nd). that the time complexity to compute {label Here the factor nd comes from the bipartite structure: every edge connects an n-node to a d-node, so each recursion step sums over pairs in [n] × [d]. In summary, since |T | ≤ |J |D ≤ α−K , the total time complexity is O M α−M + |T | + |T |K(3e)2K nd = O K[(3e)2 /α]K nd = O(nC d), where constant C = C1 log((3e)2 /α) + 2 > 0 by the choice of K given in Theorem 2.1. Variance bound. Next, to show that Theorem 2.1 continues to hold with score [ ij in place of scoreij , it suffices to establish an analogue of Propositions 3.1 and 3.2 for score [ ij ; that is, E[score [ ii ] ≥ (1 − o(1))ν,

E[score [ ij ] = 0,

Var(score [ ii ) = o(ν 2 ),

Var(score [ ij ) = o(ν 2 /n2 ), (7.3)

where ν ≜ |T |nK dK ρ2K . For two independent colorings ϕ and ψ, we define X ] T (X, i; ϕ) · label ] T (Y, j; ψ). Sij (ϕ, ψ) ≜ aut(T ) · label T ∈T

Then from (7.2), we have t

score [ ij =

1 XX Sij (ϕa , ψb ). 2 t p2 a=1 b=1

For any a, b ∈ [t], Sij (ϕa , ψb )/p2 is an unbiased estimator of scoreij , since X E [Sij (ϕa , ψb ) | X, Y ] = p2 aut(T ) · labelT (X, i) · labelT (Y, j) = p2 scoreij .

(7.4)

T ∈T

Thus, we have E score [ ij X, Y = scoreij and E score [ ij = E[scoreij ] for any i, j. Hence, the mean result in (7.3) follows directly from (3.1). It remains to bound the variance. Since E score [ ij X, Y = scoreij , we have Cov(score [ ij − scoreij , scoreij ) = 0; hence Var(score [ ij ) = Var(score [ ij − scoreij ) + Var(scoreij ). Thus, it suffices to bound Var(score [ ij − scoreij ). In particular, we have Var(score [ ij − scoreij ) = Var E score [ ij − scoreij X, Y + E Var score [ ij − scoreij X, Y = E Var score [ ij X, Y t

1 XXXX E [Cov (Sij (ϕa , ψb ), Sij (ϕc , ψd ) | X, Y )] . 4 t p4

(7.5)

a=1 b=1 c=1 d=1

Here Sij (ϕa , ψb ) and Sij (ϕc , ψd ) are independent if and only if a = ̸ c and b = ̸ d. Fix i, j and a, b, c, d. We compute the covariance as follows, Cov (Sij (ϕa , ψb ), Sij (ϕc , ψd ) | X, Y ) = E [Sij (ϕa , ψb )Sij (ϕc , ψd ) | X, Y ] − E [Sij (ϕa , ψb ) | X, Y ] E [Sij (ϕc , ψd ) | X, Y ] = E [Sij (ϕa , ψb )Sij (ϕc , ψd ) | X, Y ] − p4 score2ij , where the last equality follows from (7.4). We now compute the first term X E [Sij (ϕa , ψb )Sij (ϕc , ψd ) | X, Y ] = aut(T )aut(S) T,S∈T

E[χϕa (V (T1 ))χϕc (V (S1 ))]E[χψb (V (T2 ))χψd (V (S2 ))]X T1 Y T2 X S1 Y S2 ,

T1 ,T2 ∼ =T,S1 ,S2 ∼ =S root(T1 )=root(S1 )=i root(T2 )=root(S2 )=j

where χϕa (V (T1 ))χϕc (V (S1 )) and χψb (V (T2 ))χψd (V (S2 )) are independent since they are defined on vertices from different graphs X and Y , respectively. If V (T1 )∩V (S1 ) = {i} and V (T2 )∩V (S2 ) = {j}, since T1 (resp. T2 ) only shares one common node with S1 (resp. S2 ), we have E[χϕa (V (T1 ))χϕc (V (S1 ))] = E[χψb (V (T2 ))χψd (V (S2 ))] = p2 , In general, it is straightforward to verify that E[χϕa (V (T1 ))χϕc (V (S1 ))] ≤ p1+1{a̸=c} ,

E[χψb (V (T2 ))χψd (V (S2 ))] ≤ p1+1{b̸=d} .

Combining the equations above, we have Cov (Sij (ϕa , ψb ), Sij (ϕc , ψd ) | X, Y ) ≤ (p2+1{a̸=c} +1{b̸=d} − p4 )

aut(T )aut(S)

T,S∈T

X T1 Y T2 X S1 Y S2 1{V (T1 )∩V (S1 )̸={i} or V (T2 )∩V (S2 )̸={j}} .

T1 ,T2 ∼ =T,S1 ,S2 ∼ =S root(T1 )=root(S1 )=i root(T2 )=root(S2 )=j

For i = j, an important observation is that if either V (T1 ) ∩ V (S1 ) ̸= {i} or V (T2 ) ∩ V (S2 ) ̸= {i}, that is, T1 and S1 or T2 and S2 share a non-root node, then their decorated union graph cannot consist solely of bichromatically overlapping branches; hence, m + ℓ ≥ 1. Therefore, by the same argument as in Lemmas 6.1 and 6.2, we have X X E X T1 Y T2 X S1 Y S2 1{V (T1 )∩V (S1 )̸={i} or V (T2 )∩V (S2 )̸={i}} aut(T )aut(S) T1 ,T2 ∼ =T,S1 ,S2 ∼ =S root(T1 )=root(S1 )=i root(T2 )=root(S2 )=i

T,S∈T

≤ (1 + o(1)) ν 2

Overlap(r, m, s)Graft(ℓ) = o(ν 2 ),

r≥m,s≥0, ℓ≥0 2r+ℓ=4D, m+ℓ≥1

where the last equality follows from (6.17) and (3.2). Hence, we have E [Cov (Sii (ϕa , ψb ), Sii (ϕc , ψd ) | X, Y )] ≤ (p2+1{a̸=c} +1{b̸=d} − p4 )o(ν 2 ).

(7.6)

For i ̸= j, it suffices to bound the second moment. Combining (6.10), (6.16), and (6.18) gives X X aut(T )aut(S) E X T1 Y T2 X S1 Y S2 ≤ o(ν 2 /n2 ). T1 ,T2 ∼ =T,S1 ,S2 ∼ =S root(T1 )=root(S1 )=i root(T2 )=root(S2 )=j

T,S∈T

It follows that E [Cov (Sij (ϕa , ψb ), Sij (ϕc , ψd ) | X, Y )] ≤ (p2+1{a̸=c} +1{b̸=d} − p4 )o(ν 2 /n2 ).

(7.7)

Note that when t > 1/p, t

1 1 X X X X 2+1{a̸=c} +1{b̸=d} 2 p − p4 ≤ 2 2 + ≤ 3. 4 4 t p t p tp a=1 b=1 c=1 d=1

Hence, combining (7.5), (7.6), and (7.7), we conclude that t

1 X X X X 2+1{a̸=c} +1{b̸=d} Var(score [ ij − scoreij ) ≤ 4 4 p − p4 o ν 2 1{i=j} + ν 2 1{i̸=j} /n2 t p a=1 b=1 c=1 d=1 2 = o ν 1{i=j} + ν 2 1{i̸=j} /n2 . This verifies (7.3). Therefore, by following the proof of Theorem 2.1 with score [ ij in place of scoreij , we conclude that Theorem 2.1 continues to hold with score [ ij .

From Almost Exact to Exact Recovery

With high probability, Algorithm 1 finds a permutation π b : I → [n] such that π b = π |I and 2 |I| ≥ n − n/ log n. In this section, we provide a seeded matching algorithm to match the remaining data points, thereby achieving exact recovery. Given a seed set J, the basic intuition is as follows: if (i, j) is a true pair, then the vectors (⟨xi , xr ⟩)r∈J and (⟨yj , yπ(r) ⟩)r∈J are correlated, whereas if (i, j) is a false pair, then these vectors are independent. Hence, we determine whether i and j form a true pair by thresholding the following similarity score: X ΨJij ≜ 1{x⊤ xr y⊤ yπ(r) ≥0} . i j r∈J

Algorithm 3 iteratively adds data points as new seeds once we are confident, based on the current seed set, that they form true pairs. Algorithm 3: Achieving exact recovery via seeded matching Input: Data matrices X and Y , a mapping π b : I → [n], and a threshold γ > 0. 1 Let J = I and π e=π b. 2 while there exist i ∈ / J and j ∈ /π e(J) such that ΨJij ≥ γn do 3 Add i to J and let π e(i) = j. Output: π e : [n] → [n]. Since the initial seed set I depends on the data matrices X and Y , we show that Algorithm 3 succeeds for every possible set I satisfying |I| ≥ n − n/ log2 n. The following proposition gives sufficient conditions under which our seeded algorithm achieves exact recovery. p Proposition 8.1. Suppose that ρ2 ≥ C max{log n/d, 1/ log n} for a sufficiently large constant C. Then there exists γ > 0 such that, with probability 1 − n−Ω(1) , the following holds: for every partial mapping π b = π |I , where I ⊂ [n] satisfies |I| ≥ n − n/ log2 n, Algorithm 3, when run with inputs π b and γ, outputs π e = π in O(n3 d) time. Proof. Without loss of generality, assume that π = id and Q = Id . We choose 0 < p < q and δ > 0: 2 2 ρ 1 1 3ρ q−p 1 1 , q = + arcsin , δ= , (8.1) p = + arcsin 2 π 4 2 π 4 2(p + 2q) where (1 − 2δ)q > (1 + δ)p. We set the threshold γ = (1 + δ)p. We first show that with high probability, no false pair exceeds the threshold γn: n o [n]\{i,j} P ∃ i ̸= j : Ψij ≥ γn ≤ o(1). Fix i = ̸ j ∈ [n]. For independent standard Gaussian vectors x, z ∼ N (0, Id ) and y = ρx + we define the conditional probability n o ⊤ pij ≜ P x⊤ x · y y ≥ 0 x , y i j . i j

p 1 − ρ2 z, (8.2)

⊤ Conditioned on xi , yj , the events {x⊤ i xr yj yr ≥ 0} for r ∈ [n] \ {i, j} are independent. Therefore, [n]\{i,j}

Ψij ∼ Bin(n − 2, pij ) conditioned on xi , yj . On the event {pij ≤ p}, this conditional binomial random variable is stochastically dominated by Bin(n − 2, p). Thus, the Chernoff bound yields n o [n]\{i,j} P Ψij ≥ (1 + δ)np xi , yj · 1{pij ≤p} ≤ exp(−cδ 2 np) · 1{pij ≤p} , for all sufficiently large n and c > 0 is an absolute constant. Thus, taking expectations over xi , yj on both sides, we have nn o o [n]\{i,j} P Ψij ≥ (1 + δ)np ∩ {pij ≤ p} ≤ exp(−cδ 2 np). Let E = {pij ≤ p, ∀i = ̸ j}. Lemma 8.1 will establish that P {E} ≥ 1 − n−Ω(1) under the assumption 2 that ρ ≥ C log n/d for a sufficiently large constant C. Therefore, a union bound over all n2 false pairs (i, j) with i ̸= j yields that n o o X n [n]\{i,j} [n]\{i,j} P ∃ i ̸= j : Ψij ≥ (1 + δ)np ≤ P {E c } + P Ψij ≥ (1 + δ)np, E i̸=j

≤ n−Ω(1) + n2 exp(−cδ 2 np) = n−Ω(1) , where the last equality holds when δ 2 ≥ C log n/n for a sufficiently large C > 0 (equivalently, p [n]\{i,j} ρ2 ≥ C log n/n since δ = Θ(ρ2 )). Henceforth, we assume that Ψij < (1 + δ)np for all i ̸= j. We prove by induction that π e = id |J throughout the algorithm. At initialization, J = I and π e=π b = id |I by assumption. Suppose that π e = id |J after t iterations. At iteration t + 1, suppose the algorithm selects i, j ∈ / J. If i ̸= j, by monotonicity (J ⊂ [n] \ {i, j}), we have [n]\{i,j}

ΨJij ≤ Ψij

< (1 + δ)np.

Therefore, if i is added to J, we must have j = i and π e(i) = i is correct. Next, we show that the algorithm matches all datapoints so that π e = id. Suppose, for contrac diction, that the algorithm terminates with J ⊊ [n] with |J | ≤ n/ log2 n. Then for every i ∈ J c , ΨJii < (1 + δ)np (otherwise the while-loop would not have stopped). Summing over all i ∈ J c , X e(J, J c ) ≜ ΨJii < (1 + δ)np|J c |. (8.3) i∈J c

Here e(J, J c ) =

counts the number of edges between J and J ⊤ r∈J 1{x⊤ i xr yi yr ≥0} ⊤ random geometric graph G on [n], where (i, r) ∈ E(G) if and only if x⊤ i xr yi yr ≥ 0. P

i∈J c

c in the

On the contrary, each edge exists with a constant marginal probability, so Lemma 8.2 shows the edge expansion property of G: with probability 1 − o(1), for all J with |J c | ≤ n/ log2 n, e(J, J c ) ≥ (1 − δ)q|J||J c | ≥ (1 − 2δ)nq|J c |,

(8.4)

where the last inequality holds for all sufficiently large n. Note that δ was chosen so that (1 − 2δ)q > (1 + δ)p. Thus, we arrive at a contradiction between (8.3) and (8.4). Therefore J = [n] and π e = id. Running time. Initially, there are at most O(n2 ) unmatched candidate pairs, and each score ⊤ sums over at most n seeds. Since computing each pair of inner products x⊤ i xr and yj yr takes O(d) time, computing all initial scores {ΦIij } costs at most O(n3 d). During the algorithm, whenever a new seed r is added to J, we update the score for each unmatched pair (i, j) by checking whether ⊤ this new seed contributes one additional term, namely whether x⊤ e(r) ≥ 0. Since there are at i x r yj y π 2 most O(n ) unmatched pairs and each check takes O(d) time, each iteration costs O(n2 d). There are at most O(n) iterations, so the total update cost is O(n3 d). Together with the initialization cost, the total running time is O(n3 d). The following lemma establishes the separation between pij for i ̸= j and pii . Lemma 8.1. Let pij be the conditioned probability defined in (8.2) for all i, j ∈ [n], and let p and q be as defined in (8.1). We consider the event Esep = {pij ≤ p for all i ̸= j, pii ≥ q for all i ∈ [n]} . If ρ2 ≥ C log(n)/d for a sufficiently large constant C, then P {Esep } = 1 − n−Ω(1) . Proof. For i, j ∈ [n], we define ξi ≜

x⊤ i x , ∥xi ∥

ζj ≜

yj⊤ y , ∥yj ∥ 45

θij ≜

ρx⊤ i yj . ∥xi ∥∥yj ∥

Conditioned on xi and yj , the pair (ξi , ζj ) is Gaussian with mean zero, where Var(ξi | xi , yj ) = 1, and Cov(ξi , ζj | xi , yj ) =

Var(ζj | xi , yj ) = 1,

⊤ x⊤ ρx⊤ i E[xy ] yj i yj = = θij . ∥xi ∥ ∥yj ∥ ∥xi ∥ ∥yj ∥

Hence, by Sheppard’s formula [She99] for a standard bivariate normal with correlation θij , pij = P {ξi ζj > 0 | xi , yj } =

1 arcsin(θij ) + . 2 π

Since arcsin is strictly increasing on [−1, 1], it suffices to show that with probability 1 − o(1), θij ≤

ρ2 , 4

θii ≥

3ρ2 , 4

for all i ̸= j ∈ [n].

Fix constants δ = 1/20 and τ = |ρ|/10. By Gaussian norm concentration, we have n n √ o √ o √ √ P ∥xi ∥ − d ≥ δ d ≤ 2 exp(−cd), P ∥yj ∥ − d ≥ δ d ≤ 2 exp(−cd). Pd ⊤ If i = ̸ j, we have E[x⊤ i yj ] = 0 since xi and yj are independent. Moreover, xi yj = k=1 xik yjk is a sum of independent sub-exponential random variables. Thus, Bernstein’s inequality gives n o P x⊤ y > τ d ≤ 2 exp(−cρ2 d). i j On the event ∥xi ∥ −

√

√ d ≤ δ d,

∥yj ∥ −

√

√ d ≤ δ d,

x⊤ i yj ≤ τ d,

we have θij ≤

ρ2 ρτ d ≤ . (1 − δ)2 d 4

p ⊤ ⊤ If i = j, we have E[x⊤ 1 − ρ2 E[x⊤ i yi ] = ρE[xi xi ] + i zi ] = ρd. Since xi yi is a sum of independent sub-exponential random variables, Bernstein’s inequality yields that n o P x⊤ y − ρd > τ d ≤ 2 exp(−cρ2 d). i i On the event ∥xi ∥ −

√

√ d ≤ δ d,

∥yi ∥ −

√

√ d ≤ δ d,

x⊤ i yi − ρd ≤ τ d,

we have θii ≥

(ρ2 − |ρ|τ )d 3ρ2 ≥ . (1 + δ)2 d 4 2

In summary, for each false pair (i, j), failure occurs with probability at most Ce−cρ d , and the same holds for each true pair (i, i). A union bound over all n(n − 1) false pairs and all n true pairs yields 2 P ∃ i ̸= j : θij > ρ2 /4 or ∃ i : θii < 3ρ2 /4 ≤ Cn2 e−cρ d . 2

Hence, if ρ2 ≥ C log(n)/d for C large enough, the error probability is at most Cn2 e−cρ d = n−Ω(1) . 46

The following lemma shows the edge expansion property of a random geometric graph G. Lemma 8.2. Let G be the random geometric graph on [n], where each node i ∈ [n]pis independently associated with a pair (xi , yi ), with xi , zi ∼ N (0, Id ) independently and yi = ρxi + 1 − ρ2 zi . There ⊤ c is an edge between nodes i and r if and only if p x⊤ i xr yi yr ≥ 0. Let e(J, J ) denote the number of c 2 edges between J and J in G. Suppose that ρ ≥ C/ log n for a sufficiently large constant C. Then, with probability at least 1 − o(1), for all J ⊂ [n] with |J c | ≤ n/ log2 n, e(J, J c ) ≥ (1 − δ)q|J||J c |, where q and δ are defined in (8.1). Proof. The statement trivially holds when J c = ∅. Fix a nonempty set J ⊂ [n] with |J c | = k and 1 ≤ k ≤ n/ log2 n. We have XX X e(J, J c ) = 1{x⊤ xr y⊤ yr ≥0} = Mr , i i r∈J i∈J c

where Mr ≜

r∈J

. Conditional on {xi , yi }i∈J c , by definition, we have ⊤ i∈J c 1{x⊤ i xr yi yr ≥0}

E [e(J, J c ) | {xi , yi }i∈J c ] =

E [Mr | {xi , yi }i∈J c ] =

pii = (n − k)

r∈J i∈J c

r∈J

Let EJ c = {pii

pii .

i∈J c

≥ q, ∀i ∈ J c }. Then it holds that

E [e(J, J c ) | {xi , yi }i∈J c ] · 1EJ c = (n − k)

pii · 1EJ c ≥ (n − k)kq · 1EJ c .

i∈J c

Moreover, conditional on {xi , yi }i∈J c , the random variables {Mr } for r ∈ J are independent. Each Mr satisfies 0 ≤ Mr ≤ k. Thus, Hoeffding’s inequality gives that 2(δ(n − k)kq)2 P {e(J, J c ) ≤ (1 − δ)(n − k)kq | {xi , yi }i∈J c } · 1EJ c ≤ exp − · 1EJ c (n − k)k 2 = exp −2δ 2 (n − k)q 2 · 1EJ c . Therefore, taking expectations over {xi , yi }i∈J c on both sides, we have P {e(J, J c ) ≤ (1 − δ)(n − k)kq, EJ c } ≤ exp −2δ 2 (n − k)q 2 . Let E = {pii ≥ q, ∀i ∈ [n]}. Then for every fixed J, we have E ⊂ EJ c ; hence P {e(J, J c ) ≤ (1 − δ)(n − k)kq, E} ≤ exp −2δ 2 (n − k)q 2 . By Lemma 8.1, P {E} ≥ P {Esep } ≥ 1 − n−Ω(1) . Since there are at most nk such J with |J| = k, taking a union bound over all J with |J c | ≤ n/ log2 n, we have P ∃ J with |J c | ≤ n/ log2 n : e(J, J c ) ≤ (1 − δ)q|J||J c | n/ log2 n c

≤ P {E } +

nk exp −2δ 2 (n − k)q 2

k=1 −Ω(1)

≤n

n 2 2 −Ω(1) , 2 exp −δ nq + n/ log n = n log n

wherepthe last equality holds when δ 2 ≥ C/ log n for a sufficiently large C > 0 (or equivalently, ρ2 ≥ C/ log n since δ = Θ(ρ2 )). 47

Quadratic Assignment Estimator

In this section, we prove the information-theoretic condition in Theorem 2.3, by analyzing the quadratic assignment problem (QAP) estimator (2.11). Recall that A = XX ⊤ and B = Y Y ⊤ . Proof of Theorem 2.3. Without loss of generality, we assume the true permutation is identity, that is, Π = I. Specifically, we prove the result under the condition d ≥ C log n,

1 − ρ2 cnd < , 2 ρ (n + d) log n

(1 − ρ2 )2 cn < , 4 ρ log n

(9.1)

for some absolute constants C, c > 0. The conditions in (9.1) imply those in (2.12). For a permutation matrix P ∈ Sn , we define DP ≜ A − P AP ⊤ , ∆P ≜ ⟨DP , B⟩ . We now show that, under condition (9.1), we have ∆P > 0 for every P = ̸ I with high probability. Hence, the QAP estimator exactly recovers the true permutation. By definition, p B = Y Y ⊤ = ρ2 XX ⊤ + ρ 1 − ρ2 (XZ ⊤ + ZX ⊤ ) + (1 − ρ2 )ZZ ⊤ . We decompose ∆P according to these three terms in B. First, since P AP ⊤ F = ∥A∥F , we have ∥DP ∥2F = 2 ∥A∥2F − 2 P AP ⊤ , A . Thus, for the following signal term, D E D E DP , XX ⊤ = ∥A∥2F − P AP ⊤ , A = ∥DP ∥2F /2. Next, by the symmetry of DP , the following linear-noise term can be written as D E DP , XZ ⊤ + ZX ⊤ = 2 Tr(DP XZ ⊤ ) = 2 ⟨DP X, Z⟩ . Finally, since Tr(DP ) = Tr(A) − Tr(P AP ⊤ ) = 0, the following quadratic-noise term satisfies D E D E DP , ZZ ⊤ = DP , ZZ ⊤ − dIn . Combining them together, we have D E p ∆P ≥ ρ2 ∥DP ∥2F /2 − 2ρ 1 − ρ2 |⟨DP X, Z⟩| − (1 − ρ2 ) DP , ZZ ⊤ − dIn .

(9.2)

Lemmas 9.3 to 9.5 provide a lower bound on the signal term and upper bounds on the noise terms, respectively. In particular, we work on the event n o E ≜ ∥X∥2 ≤ C(n + d) , (9.3) which occurs with probability at least 1 − e−c(n+d) by standard Gaussian matrix theory [Ver12]. For P ∈ Sn , we define m(P ) = |{i : P (i) ̸= i}| as the number of indices at which P differs from the true permutation. For P with m(P ) = m, whenever the events AP ∩ LP ∩ QP in Lemmas 9.3 to 9.5 occur, by (9.2), we have ∆P ≥ ρ2 ∥DP ∥2F /2 − ρ2 ∥DP ∥2F /16 − C(1 − ρ2 )(n + d)m log n − ρ2 ∥DP ∥2F /16 − C ≥ ρ2 ∥DP ∥2F /4 + cρ2 dmn − C(1 − ρ2 )(n + d)m log n − C 48

(1 − ρ2 )2 dm log n ρ2

≥ ρ2 ∥DP ∥2F /4 + c′ ρ2 dmn > 0, where the last inequality follows from condition (9.1). Therefore, P {E ∩ {∆P ≤ 0}} ≤ P {E ∩ AcP } + P {E ∩ LcP } + P {E ∩ QcP } ′

′

≤ e−c nd + e−c mnd/(n+d) + 4n−2m . Finally, taking a union bound over all P ∈ Sn , and noting that there are at most nm such permutations with m mismatches for each m ∈ {2, . . . , n} yields that c

P {∃P ̸= I : ∆P ≤ 0} ≤ P {E } +

n X

′ ′ nm e−c nd + e−c mnd/(n+d) + 4n−2m

m=2

≤ e−c(n+d) + e−cnd − e−cnd/(n+d) +

4 = o(1), n(n − 1)

where the last inequality holds since d ≥ C log n and nd/(n + d) ≥ min{n, d} ≥ C log n with a sufficiently large C > 0.

9.1

Signal Lower Bound

We begin with several preliminaries regarding the signal term. For a permutation P ∈ Sn , we define M (P ) = {i : P (i) ̸= i} as its mismatch set; then m(P ) = |M (P )|. Given a permutation P ∈ Sn and a subset S ⊂ [n], let P (S) = {P (i) : i ∈ S}. The following lemma shows that one can extract a linear-size subset S ⊂ M (P ) such that S and P (S) are disjoint. Lemma 9.1. Let P be a permutation on [n] with m(P ) ≥ 2. Then there exists S ⊂ M (P ) such that S ∩ P (S) = ∅

and

|S| ≥ m(P )/3.

Moreover, P (S) ⊂ M (P ) and |S ∪ P (S)| = 2|S|. Proof. Note that P maps M (P ) into itself, so P |M (P ) is a permutation of M (P ) with no fixed points. Hence, P |M (P ) decomposes into cycles of at least 2. On each cycle of length ℓ, choose every other vertex; this gives ⌊ℓ/2⌋ ≥ ℓ/3 vertices, no two of which are adjacent along the cycle. Taking the union of these selected vertices over all cycles gives a set S satisfying |S| ≥ m/3, P (S) ⊂ M (P ), S ∩ P (S) = ∅, and |S ∪ P (S)| = 2|S|, as required. The next lemma states the concentration bounds for weighted chi-square random variables. P 2 Lemma 9.2. Let a1 , . . . , am be nonnegative constants. For i.i.d. ξi ∼ N (0, 1), let ζ = m i=1 ai (ξi −1). Then for any t > 0, v   um uX P ζ ≤ −2t a2i t ≤ e−t . (9.4) i=1 i.i.d.

Moreover, let K ⪰ 0 be a deterministic r × r matrix and let g1 , . . . , gs ∼ N (0, Ir ). Then ! s X s Tr(K) Tr(K) ⊤ P gi Kgi ≤ ≤ exp −cs . 2 ∥K∥ i=1

(9.5)

Proof. The concentration bound (9.4) is the Laurent–Massart inequality [LM00]. Next, we diagonalize i.i.d.

K = U diag(λ1 , . . . , λr )U ⊤ and define hij = (U ⊤ gi )j ∼ N (0, 1). Then s X

gi⊤ Kgi =

i=1

s X r X

λj h2ij ,

i=1 j=1

which is a sum of independent weighted χ21 random variables, with weight vector λ (each weight λj repeated s times). Its mean equals s Tr(K). Applying (9.4) to the deviation level s Tr(K)/2 yields a tail bound with exponent of order s Tr(K)2 /∥K∥2F . Since K ⪰ 0 yields ∥K∥2F ≤ ∥K∥ Tr(K), we may lower bound the exponent by s Tr(K)/ ∥K∥, which gives (9.5). We are now ready to lower bound the signal. Lemma 9.3. Recall E from (9.3). There are absolute constants c, c′ > 0 such that if we define the event for every P ∈ Sn , n o AP ≜ ∥DP ∥2F > cm(P )nd , ′

′

then it holds that P {E ∩ AcP } ≤ e−c nd + e−c m(P )nd/(n+d) . Proof. We separately analyze the small- and large-mismatch regimes, corresponding to m(P ) ≤ n/2 and m(P ) > n/2. Fix P with m(P ) = m. Small-mismatch regime: m ≤ n/2. Let F = [n]\M (P ); thus |F | = n−m ≥ n/2. By Lemma 9.1, we extract S ⊂ M (P ) with s ≜ |S| ≥ m/3 and S ∩ P (S) = ∅. For i ∈ S and j ∈ F , we have P (j) = j; hence (DP )ij = Aij − AP (i),j = Xi − XP (i) , Xj . We define matrices GS ∈ Rs×d with rows (Xi − XP (i) )⊤ for i ∈ S and HF ∈ R|F |×d with rows Xj⊤ for j ∈ F . Restricting the off-diagonal sum to S × F , we obtain XX ∥DP ∥2F ≥ 2 (DP )2ij = 2∥GS HF⊤ ∥2F . (9.6) i∈S j∈F

By Lemma 9.1, the 2s row-indices in S ∪ P (S) are distinct elements of M (P ). Hence each row of GS is the difference of two independent N (0, Id ) vectors from disjoint rows of X; the rows of GS are i.i.d. N (0, 2Id ). Moreover, F is disjoint from M (P ); thus GS and HF are independent. Writing √ e S , where G e S has i.i.d. N (0, 1) entries and rows g1 , . . . , gs iid GS = 2G ∼ N (0, Id ), we have e S HF⊤ ∥2F = 2 ∥GS HF⊤ ∥2F = 2∥G

s X

gi⊤ HF⊤ HF gi .

(9.7)

i=1

Let K = HF⊤ HF . Combining (9.6) and (9.7), we have ∥DP ∥2F ≥ 4

s X

gi⊤ Kgi .

(9.8)

i=1

Conditional on HF , applying Lemma 9.2 to the gi ’s, which are independent of K = HF⊤ HF , implies, ! s X s Tr(K) Tr(K) ⊤ P gi Kgi ≤ HF ≤ exp −c1 s . (9.9) 2 ∥K∥ i=1

Recall E from (9.3) and let E1 ≜ {∥HF ∥2 ≤ C(n + d)}. Since ∥HF ∥2 ≤ ∥X∥2 , we have E ⊂ E1 . P P 2 ∼ χ2 Moreover, since ∥HF ∥2F = j∈F r∈[d] Xjr |F |d and |F | ≥ n/2, the bound (9.4) yields for small constants c, c2 > 0 and E2 ≜ {∥HF ∥2F ≥ 3cnd/2}, P {E2 } ≥ 1 − e−c2 nd . Whenever E1 ∩ E2 occurs, the matrix K = HF⊤ HF satisfies ∥K∥ = ∥HF ∥2 ≤ C(n + d) and Tr(K) = ∥HF ∥2F ≥ 3cnd/2; hence Tr(K) 3cnd ≥ . ∥K∥ 2C(n + d)

(9.10)

Combining (9.9) and (9.10) and using s ≥ m/3, we obtain ! s X Tr(K) c3 mnd s Tr(K) ⊤ 1E1 ∩E2 ≤ exp − 1E1 ∩E2 . P HF 1E1 ∩E2 ≤ exp −c1 s gi Kgi ≤ 2 ∥K∥ n+d i=1

Taking the expectation over HF , we have ( s ) ! X s Tr(K) c3 mnd ⊤ . P ∩ E1 ∩ E2 ≤ exp − gi Kgi ≤ 2 n+d i=1

Finally, together with (9.8) and s ≥ m/3, the event AcP ∩ E2 with AcP = {∥DP ∥2F < cmnd} implies s X

gi⊤ Kgi ≤

i=1

∥DP ∥2F cmnd s Tr(K) < ≤ . 4 4 2

Therefore, since E ⊂ E1 , we have P {E ∩ AcP } ≤ P {E2c } + P {E2 ∩ E1 ∩ AcP } ( s ) ! X s Tr(K) c ⊤ ≤ P {E2 } + P gi Kgi ≤ ∩ E1 ∩ E2 2 −c2 nd

≤e

i=1 −c3 mnd/(n+d)

(9.11)

Large-mismatch regime: m > n/2. By Lemma 9.1, we again extract S ⊂ M (P ) with s ≜ |S| ≥ m/3 ≥ n/6 and S ∩ P (S) = ∅. For i, j ∈ S, (DP )ij = ⟨Xi , Xj ⟩ − XP (i) , XP (j) . Define XS ∈ Rs×d with rows Xi⊤ for i ∈ S and XP (S) ∈ Rs×d with rows XP⊤(i) for i ∈ S, both with i.i.d. N (0, 1) entries. Since S ∩ P (S) = ∅, XS and XP (S) are independent. Note that the S × S block of DP satisfies (DP )S,S = XS XS⊤ − XP (S) XP⊤(S) . U Let a ≜ ⌈s/2⌉ and b ≜ ⌊s/2⌋. We partition the row-set of XS into XS = 1 with U1 ∈ Ra×d and U2 b×d U2 ∈ R , and likewise for V . Then taking the off-diagonal sum gives ∥DP ∥2F ≥ ∥XS XS⊤ − XP (S) XP⊤(S) ∥2F ≥ 2∥U1 U2⊤ − V1 V2⊤ ∥2F .

(9.12)

2d for j ∈ [b], where u ⊤ ⊤ Let W ≜ [U1 , −V1 ] ∈ Ra×2d , K = W ⊤ W , and wj ≜ (u⊤ 2,j and 2,j , v2,j ) ∈ R v2,j are the rows of U2 and V2 , respectively. Here wj ’s are i.i.d. N (0, I2d ). Then we may rewrite

∥U1 U2⊤ − V1 V2⊤ ∥2F =

b X

wj⊤ Kwj .

(9.13)

j=1

Applying Lemma 9.2 conditionally on W , we have   b X b Tr(K) Tr(K) P wj⊤ Kwj ≤ W  ≤ exp −c4 b . 2 ∥K∥

(9.14)

j=1

Recall E from (9.3) and let E3 ≜ {∥W ∥2 ≤ 2C(n + d)}. Since ∥W ∥2 ≤ ∥U1 ∥2 + ∥V1 ∥2 ≤ 2 ∥X∥2 , we have E ⊂ E3 . Moreover, let E4 ≜ {∥W ∥2F ≥ 9cnd}. Since ∥W ∥2F ∼ χ22ad and a ≥ s/2 ≥ m/6 ≥ n/12, the bound (9.4) gives P {E4 } ≥ 1 − e−c5 nd . Whenever E3 ∩ E4 occurs, the matrix K = W ⊤ W satisfies ∥K∥ = ∥W ∥2 ≤ 2C(n + d) and Tr(K) = ∥W ∥2F ≥ 9cnd; hence 9cnd Tr(K) ≥ . ∥K∥ 2C(n + d)

(9.15)

Combining (9.14) and (9.15) and using b ≥ s/3 ≥ m/9, we obtain   b X b Tr(K) c6 mnd Tr(K) ⊤   P wj Kwj ≤ 1E3 ∩E4 ≤ exp − 1E3 ∩E4 . W 1E3 ∩E4 ≤ exp −c4 b 2 ∥K∥ n+d j=1

Taking the expectation over W , we have    b X  c6 mnd b Tr(K) ⊤   P ∩ E3 ∩ E4 ≤ exp − . wj Kwj ≤   2 n+d j=1

Finally, with (9.12), (9.13), and b ≥ m/9, the event AcP ∩ E4 where AcP = {∥DP ∥2F < cmnd} gives b X

wj⊤ Kwj ≤

j=1

∥DP ∥2F cmnd b Tr(K) < ≤ . 2 2 2

Therefore, since E ⊂ E3 , we have P {E ∩ AcP } ≤ P {E4c } + P {E4 ∩ E3 ∩ AcP }    b X  b Tr(K) ≤ P {E4c } + P  wj⊤ Kwj ≤ ∩ E3 ∩ E4    2 j=1

≤ e−c5 nd + e−c6 mnd/(n+d) . Combining (9.11) and (9.16) concludes the proof of the lemma.

(9.16)

9.2

Noise Upper Bound

The lemmas in this section provide upper bounds on the two noise terms, respectively. Lemma 9.4. There exists a constant C > 0 such that, if for every P ∈ Sn we define the event n p o LP ≜ 2ρ 1 − ρ2 |⟨DP X, Z⟩| ≤ ρ2 ∥DP ∥2F /16 + C(1 − ρ2 )(n + d)m(P ) log n , then recalling E from (9.3), it holds that P {E ∩ LcP } ≤ 2n−2m(P ) . Proof. Fix P ∈ Sn with m(P ) = m. Conditional on X, since Z has i.i.d. N (0, 1) entries, it holds that ⟨DP X, Z⟩ ∼ N (0, ∥DP X∥2F ). Hence by Chernoff bound, for any t > 0, P {| ⟨DP X, Z⟩ | ≥ t | X} ≤ 2 exp −t2 / 2∥DP X∥2F . √ Let RP ≜ | ⟨DP X, Z⟩ | ≤ 2 m log n∥DP X∥F . With t2 = 4m log n · ∥DP X∥2F , it follows that P {RcP | X} ≤ 2n−2m . When E = {∥X∥2 ≤ C(n + d)} and RP both occur, we have √ ∥DP X∥F ≤ ∥DP ∥F ∥X∥ ≤ C∥DP ∥F n + d, and p p p 2ρ 1 − ρ2 | ⟨DP X, Z⟩ | ≤ Cρ 1 − ρ2 (n + d)m log n∥DP ∥F ≤ ρ2 ∥DP ∥2F /16 + 4C 2 (1 − ρ2 )(n + d)m log n, where p the last p line applies the Cauchy–Schwarz inequality 2ab ≤ a2 /16 + 16b2 with a = ρ∥DP ∥F and b = C 1 − ρ2 (n + d)m log n/2. Thus, E ∩ RP ⊂ E ∩ LP ; hence E ∩ LcP ⊂ E ∩ RcP . Therefore, P {E ∩ LcP } ≤ P {E ∩ RcP } = E[1E P {RcP | X}] ≤ 2n−2m .

Lemma 9.5. There exists a constant C > 0 such that, if for every P ∈ Sn we define the event D E (1 − ρ2 )2 QP ≜ (1 − ρ2 ) DP , ZZ ⊤ − dIn ≤ ρ2 ∥DP ∥2F /16 + C dm(P ) log n ρ2 2 + C(1 − ρ )(n + d)m(P ) log n , then recalling E from (9.3), it holds that P {E ∩ QcP } ≤ 2n−2m(P ) . Proof. Fix P ∈ Sn with m(P ) = m. Let z1 , . . . , zd denote the columns of Z, where zℓ ∼ N (0, In ). Note that D

DP , ZZ

⊤

d X

zℓ⊤ DP zℓ = vec(Z)⊤ (Id ⊗ DP )vec(Z),

ℓ=1

with mean E DP , ZZ ⊤ = ⟨DP , dIn ⟩. Thus, by Hanson–Wright inequality, for any u > 0, nD E o √ P DP , ZZ ⊤ − dIn ≥ C ∥Id ⊗ DP ∥F u + ∥Id ⊗ DP ∥ u X ≤ 2e−u , 53

(9.17)

√ where ∥Id ⊗ DP ∥F = d∥DP ∥F and ∥Id ⊗ DP ∥ = ∥DP ∥. We define the event nD o E p BP ≜ DP , ZZ ⊤ − dIn ≤ C ∥DP ∥F dm log n + ∥DP ∥ m log n . Taking u = 2m log n in (9.17) yields that P {BPc | X} ≤ 2n−2m . Moreover, when E occurs, since ∥P AP ⊤ ∥ = ∥A∥, we have ∥DP ∥ ≤ ∥A∥ + ∥P AP ⊤ ∥ = 2∥A∥ = 2∥X∥2 ≤ 2C(n + d). Therefore, when E ∩ BP both occur, we obtain D E p (1 − ρ2 ) DP , ZZ ⊤ − dIn ≤ C(1 − ρ2 )∥DP ∥F dm log n + C(1 − ρ2 ) ∥DP ∥ m log n (1 − ρ2 )2 dm log n + 2C(1 − ρ2 )(n + d)m log n, ρ2 √ where the last inequality uses 2ab ≤ a2 /16 + 16b2 with a = ρ∥DP ∥F and b = C(1 − ρ2 ) dm log n/ρ. In other words, we have E ∩ BP ⊂ E ∩ QP . Therefore, ≤ ρ2 ∥DP ∥2F /16 + 16C 2

P {E ∩ QcP } ≤ P {E ∩ BPc } = E[1E P {BPc | X}] ≤ 2n−2m .

Limits of Tree Polynomials via Low-Degree Analysis

Recall that our matching algorithm counts only trees whose d-nodes all have degree 2. In this section, we show that enlarging the tree family to allow d-nodes of arbitrary even degree yields only a negligible improvement in distinguishing power for a closely related hypothesis testing problem: • Under the null hypothesis H0 : X, Y ∈ Rn×d are independent with i.i.d. N (0, 1) entries; p • Under the alternative hypothesis H1 : the pair (X, Y ) follows Y = ρΠXQ + 1 − ρ2 Z, where X, Z ∈ Rn×d are independent with i.i.d. N (0, 1) entries, Π is a uniform permutation matrix on [n], and Q ∈ Od is Haar-distributed. We employ the widely adopted low-degree framework to study the limits of polynomial tests [HS17, KWB19, Wei25]. Consider the space F of functions f : Rn×d × Rn×d → R endowed with inner product ⟨f, g⟩ ≜ E0 [f (X, Y )g(X, Y )]. It is well-known that the Hermite polynomials form an orthogonal basis of F. Let F≤D denote the space of all multivariate polynomials of X, Y with a total degree at most D. A standard way to measure the distinguishing power of polynomials in the space F≤D is the low-degree advantage defined as E1 [f ] − E0 [f ] p . f ∈F≤D Var0 (f )

Adv≤D ≜ max

(10.1)

The ratio above measures the mean separation of a test f under the two hypotheses relative to its standard deviation under the null hypothesis, and therefore has a natural interpretation as a signal-to-noise ratio. Hence, following the literature, we say that degree-D polynomials fail to strongly (resp. weakly) distinguish the two hypotheses if Adv≤D = O(1) (resp. = o(1)). It is shown in [Li26] that Adv≤D = o(1) as n → ∞ when ρ → 0 and D ≪ 1/ρ. In particular, this implies that all O(log(n))-degree polynomials fail to weakly distinguish the two hypotheses when ρ ≪ 1/ log(n). In this section, we take a step further by showing that all multilinear polynomials built from trees have bounded low-degree advantage and hence fail to strongly distinguish the two √ √ hypotheses when ρ2 < α. This suggests that breaking the α threshold requires counting graphs beyond trees, for testing and likely for matching as well. 54

10.1

Graph Polynomials

For bipartite simple graphs G and H on [n] × [d], define the multilinear polynomial ϕG,H (X, Y ) = X G · Y H . Since the entries of X and Y are independent under H0 , and G and H are simple graphs, the polynomials {ϕG,H (X, Y )} are orthonormal: ⟨ϕG,H , ϕG′ ,H ′ ⟩ = E0 [ϕG,H (X, Y )ϕG′ ,H ′ (X, Y )] = 1{G=G′ ,H=H ′ } . We are interested in the subspace spanned by those orthogonal polynomials whose graph indices belong to a prescribed family G of unlabeled graphs: FG ≜ span({ϕT1 ,S1 : T1 ∼ = T, S1 ∼ = S, T, S ∈ G}). Analogously to (10.1), we measure the distinguishing power of G by its advantage E1 [h] − E0 [h] p . h∈FG Var0 (h)

AdvG ≜ max

Without loss of generality, we assume E0 [h] = 0. Moreover, for any h ∈ FG , q p E1 [h] = E0 [Lh] = E0 [LG h] ≤ E0 [L2G ] E0 [h2 ], where LG ≜

⟨L, ϕT1 ,S1 ⟩ ϕT1 ,S1

T,S∈G T1 ∼ =T,S1 ∼ =S

denotes the projection of the likelihood ratio L = P1 (X, Y )/P0 (X, Y ) onto FG . The above inequality follows from Cauchy–Schwarz and is achieved when h = LG . Therefore,  q X AdvG = E0 [L2G ] = 

1/2 X

⟨L, ϕT1 ,S1 ⟩2 

(10.2)

T,S∈G T1 ∼ =T,S1 ∼ =S

The projection coefficient ⟨L, ϕT1 ,S1 ⟩ can be evaluated via the Weingarten calculus: 1 X ⟨L, ϕT1 ,S1 ⟩ = EΠ EX,Y X T1 Y S1 Π = n! π

ρ2K Wg(µ(c), d).

(10.3)

c∈C(π(T1 )∪n S1 )

Observe that ⟨L, ϕT1 ,S1 ⟩ depends only on the isomorphism classes of T1 and S1 . Moreover, ⟨L, ϕT1 ,S1 ⟩ is non-zero only when C(π(T1 ) ∪n S1 ) ̸= ∅ for some permutation π. Recalling from Definition 4.2, this requires that 1. Every d-node in both T1 and S1 must have even degree; 2. The n-nodes in T1 and S1 have matching degree sequences under the relabeling. Therefore, it suffices to restrict G to graphs with even d-node degrees. Let T be the family of unlabeled simple bipartite trees on [n] × [d] with 2K edges and even d-node degrees, and let T ∗ be the subfamily in which every d-node has degree 2. The following theorem bounds the advantage of T in terms of the contribution from T ∗ . 55

Theorem 10.1. If d ≥ poly(K), then poly(K) X X 2 ⟨L, ϕT1 ,T2 ⟩2 . AdvT ≤ 1 + d ∗ ∼ T ∈T

T1 =T T2 ∼ =T

Furthermore, K poly(K) ρ4 ⟨L, ϕT1 ,T2 ⟩ ≤ 1 + , d α + o(1) ∼

X X

T ∈T ∗ T1 =T T2 ∼ =T

which is O(1) when ρ2 <

√

α.

Theorem 10.1 shows that the main contribution to AdvT comes from pairs of trees that are both √ isomorphic to some common T ∈ T ∗ . In particular, when ρ2 < α, AdvT = O(1); hence no tree polynomial in FT strongly separates H0 from H1 . Furthermore, as shown in (10.7) later, for any T1 , T2 ∼ = T with T ∈ T ∗ , ⟨L, ϕT1 ,T2 ⟩ ∝ aut(T ). Therefore, up to negligible terms, AdvT is achieved by the tree polynomial X X X X X fT ∗ (X, Y ) ≜ ⟨L, ϕT1 ,T2 ⟩ϕT1 ,T2 (X, Y ) ∝ aut(T ) X T1 Y T2 , T ∈T ∗ T1 ∼ =T T2 ∼ =T

T ∈T ∗

T1 ∼ =T

T2 ∼ =T

This coincides with the similarity score defined in (2.2) for matching, except that the matching statistic counts rooted trees. The proof of Theorem 10.1 also explains why trees in T ∗ give the leading contribution. In the calculation of the advantage, the number of ways to choose the n-node labels cancels the probability that π(T1 ) and S1 are properly matched under the random permutation appearing in the projection coefficient (10.3). By contrast, the d-node labels of T1 and S1 need not match each other, and thus they contribute powers of d to the advantage. Therefore, among trees with 2K edges, whose total number of nodes is fixed at 2K + 1, the dominant contribution comes from those with the largest possible number of d-nodes, namely D = K. These are exactly the trees in T ∗ .

10.2

Proof of Theorem 10.1

Proof of Theorem 10.1. Recall from (10.2) that X X Adv2T =

⟨L, ϕT1 ,S1 ⟩2 .

T,S∈T T1 ∼ =T,S1 ∼ =S

∼ T for some T ∈ T ∗ ); non-isomorphic We split the sum into three parts: isomorphic pairs (T1 , S1 = pairs (T1 ∼ = T, S1 ∼ = S for some distinct T, S ∈ T ∗ ); and all remaining pairs (T1 ∼ = T, S1 ∼ = S for ∗ ∗ some (T, S) ∈ / T × T ). Leading term: T1 , S1 ∼ = T for some T ∈ T ∗ . Recall from (10.3) that ⟨L, ϕT1 ,S1 ⟩ =

1 X n! π

ρ2K Wg(µ(c), d).

(10.4)

c∈C(π(T1 )∪n S1 )

By Theorem 4.1, under the assumption that d ≥ poly(K), every circuit decomposition c with µ1 (c) = K satisfies ρ2K Wg(µ(c), d) ≜ wd,K = (1 + poly(K)/d)(ρ2 /d)K . Moreover, given T1 , S1 , 56

there are aut(T )×(n−K −1)! distinct permutations π such that each edge pair of π(T1 ) fully overlaps with an edge pair of S1 , so that π(T1 ) ∪n S1 admits a unique decomposition c with µ1 (c) = K. Hence, we obtain X X ρ2K Wg(µ(c), d) = wd,K |{(π, c) : c ∈ C(π(T1 ) ∪n S1 ), µ1 (c) = K}| π c∈C(π(T1 )∪n S1 ) µ1 (c)=K

2 K poly(K) ρ = 1+ aut(T ) × (n − K − 1)!. d d

(10.5)

For circuit decompositions c with µ1 (c) = µ1 ≤ K − 2, by (4.8) and the assumption that d ≥ poly(K), ρ2K |Wg(µ(c), d)| ≤ C(ρ2 /d)K (4/d)(K−µ1 )/2 . Recall from Lemma 5.1 that, given S1 , |{(H, c) : c ∈ C(H ∪n S1 ), µ1 (c) = µ1 }| ≤ (4K)K−µ1 , where H is a union of K edge pairs (with unlabeled d-nodes). Moreover, for each such H, there are at most aut(T ) × (n − K − 1)! distinct permutations π such that each edge pair of π(T1 ) fully overlaps with an edge pair of H. It follows that X X X ρ2K |Wg(µ(c), d)| µ1 ≤K−2 π c∈C(π(T1 )∪n S1 ) µ1 (c)=µ1

≤C

X µ1 ≤K−2

(K−µ1 )/2 2 K ρ 4(4K)2 × aut(T ) × (n − K − 1)! d d

2 K ρ 4(4K)2 ≤C aut(T ) × (n − K − 1)! × . d d Therefore, substituting (10.5) and (10.6) into (10.4) yields K poly(K) (n − K − 1)! ρ2 ⟨L, ϕT1 ,S1 ⟩ = 1 + aut(T ), d n! d

(10.6)

(10.7)

( n )(K+1)! d Finally, given an unlabeled tree T ∈ T ∗ , there are K+1 K K! labeled trees T1 that are aut(T ) isomorphic to T ; the same for labeled trees S1 . Therefore, X X ⟨L, ϕT1 ,S1 ⟩2 T ∈T ∗ T1 ,S1 ∼ =T

#2 " n K #2 (K + 1)! poly(K) (n − K − 1)! ρ2 d 1+ aut(T ) × K+1 K! = d n! d aut(T ) K T ∈T ∗ poly(K) = 1+ ρ4K |T ∗ |. (10.8) d X

Non-isomorphic pairs: T1 ∼ ̸ S ∈ T ∗ . In this case, for any permutation = T, S1 ∼ = S for some T = π, any circuit decomposition c of π(T1 ) ∪n S1 must have µ1 (c) ≤ K − 2. Therefore, it follows from (10.6) that X 1 X |⟨L, ϕT1 ,S1 ⟩| ≤ ρ2K |Wg(µ(c), d)| n! π c∈C(π(T1 )∪n S1 ) µ1 (c)≤K−2

(n − K − 1)! ≤C n!

2 K ρ 4(4K)2 aut(T ) × . d d

Moreover, given T1 ∼ = T , we have X X

|⟨L, ϕT1 ,S1 ⟩| ≤

S∈T ∗ S1 ∼ =S

1 X X X n! π ∗ ∼ S∈T

X X

ρ2K |Wg(µ(c), d)|

S1 =S c∈C(π(T1 )∪n S1 ) µ1 (c)≤K−2

ρ2K |Wg(µ(c), d)|

S∈T ∗ S1 ∼ =S c∈C(T1 ∪n S1 ) µ1 (c)≤K−2

2 K ρ ≤C d

X µ1 ≤K−2

(K−µ1 )/2 X X 4 d ∗ ∼ S∈T

(10.9)

S1 =S c∈C(T1 ∪n S1 ) µ1 (c)=µ1

where the equality holds as the inner double sum does not depend on π, and the last inequality follows from ρ2K |Wg(µ(c), d)| ≤ C(ρ2 /d)K (4/d)(K−µ1 )/2 . It follows from Lemma 5.1 that d ∗ K−µ1 ∼ |{(S1 , c) : S1 = S for some S ∈ T , c ∈ C(T1 ∪n S1 ), µ1 (c) = µ1 }| ≤ (4K) × K!, K d where the factor K K! comes from labeling the K d-nodes in S1 . The above also follows from the more general Lemma 10.1 proved below. Combining the last three displayed equations and summing over µ1 ≤ K − 2 yields that given T1 ∼ = T, (n − K − 1)! ⟨L, ϕT1 ,S1 ⟩ ≤ C n! ∼

X X

S∈T ∗ S1 =S

2 2K 2 ρ 4(4K)2 d aut(T ) × × K!. d d K

( n )(K+1)! d ∗ Finally, note that there are K+1 K K! distinct labeled T1 that are isomorphic to T ∈ T . aut(T ) Therefore, X X ⟨L, ϕT1 ,S1 ⟩2 T,S∈T ∗ T1 ∼ =T =S T ̸=S S1 ∼

2 2K 2 2 ρ (n − K − 1)! n 4(4K)2 d ≤ C|T | (K + 1)! × K! d n! K +1 d K 2 4(4K)2 4K ∗ ≤ Cρ |T | . d ∗

(10.10)

Remaining pairs: (T1 ∼ / T ∗ × T ∗ ). Let TD ⊂ T denote the = T, S1 ∼ = S for some (S, T ) ∈ subfamily of trees with 2K edges and D d-nodes with even degrees. Then TK = T ∗ . Recall that ⟨L, ϕT1 ,S1 ⟩ is non-zero only when T1 and S1 have the same number of n-nodes and the d-nodes have even degrees. Therefore, X

⟨L, ϕT1 ,S1 ⟩2 =

=T (T,S)∈T / ∗ ×T ∗ T1 ∼

K−1 X

D=1 T,S∈TD T1 ∼ =T S1 ∼ =S

S1 ∼ =S

⟨L, ϕT1 ,S1 ⟩2 .

(10.11)

Note that TD has N ≜ 2K + 1 − D n-nodes. Given any T1 ∼ = T, S1 ∼ = S with T, S ∈ TD , we first pair the edges incident to each d-node of S1 . The proof of Lemma 10.1 (cf. (10.14)) shows that the number of such pairings is at most (2K)2(K−D) . After fixing this pairing, analogous to the derivation of (10.7), we have |⟨L, ϕT1 ,S1 ⟩| ≤

1 X n! π

ρ2K |Wg(µ(c), d)|

c∈C(π(T1 )∪n S1 )

2 K (K−µ1 )/2 4 ρ (4K)K−µ1 (2K)2(K−D) × aut(T )(n − N )! d d µ1 ≤K K (n − N )! ρ2 ≤C (2K)2(K−D) aut(T ) n! d C X ≤ n!

Moreover, given T1 ∼ = T , analogous to (10.9), we have 2 K X (K−µ1 )/2 X X ρ 4 |⟨L, ϕT1 ,S1 ⟩| ≤ C d d ∼ ∼

X X

µ1 ≤K

S∈TD S1 =S

S∈TD S1 =S c∈C(T1 ∪n S1 ) µ1 (c)=µ1

By Lemma 10.1, we have |{(S1 , c) : S1 ∼ = S for some S ∈ TD , c ∈ C(T1 ∪n S1 ), µ1 (c) = µ1 }| K−µ1 4(K−D) d ≤ (4K) (2K) D!. D

(10.12)

Combining the last three displayed equations and summing over µ1 ≤ K yields that given T1 ∼ = T, (n − N )! ⟨L, ϕT1 ,S1 ⟩ ≤ C n! ∼

X X

S∈TD S1 =S

2 2K ρ 6(K−D) d D!. aut(T ) × (2K) D d

(Nn )N ! d Recall that there are aut(T ) D D! distinct labeled trees T1 that are isomorphic to T ∈ TD . Therefore, X

2 2 2K ρ (n − N )! n d 6(K−D) ⟨L, ϕT1 ,S1 ⟩ ≤ C|TD | N ! × (2K) D! d n! N D ∼

T,S∈TD T1 =T S1 ∼ =S

≤ Cρ

|TD |

8K 3 d2

2(K−D) .

It remains to bound |TD | as follows: −D

|TD | ≤ (α + o(1))

ND ≤ |T ∗ |(2K)4(K−D) . 2(K − D)

For the first inequality, each T ∈ TD can be constructed in two steps: first build a tree with D + 1 n-nodes, D d-nodes, and 2D edges in which every d-node has degree 2, then add the remaining 2(K − D) edges. The number of trees built by the first step is (α + o(1))−D , and the second step ND admits at most 2(K−D) choices, since each added edge connects an n-node and a d-node and there are at most N D such pairs. The second inequality follows from (α + o(1))−D ≤ (α + o(1))−K = |T ∗ | 59

and N D ≤ [(N + D)/2]2 = (K + 1/2)2 . Combining the last two displayed equations, plugging the result back into (10.11), and summing over D ≤ K − 1 yields X

⟨L, ϕT1 ,S1 ⟩ ≤ Cρ

=T (T,S)∈T / ∗ ×T ∗ T1 ∼ S1 ∼ =S

∗

|T |

K−1 X D=1

8K 5 d

2(K−D) ≤

CK 5 4K ∗ ρ |T |. d2

(10.13)

We conclude the proof of Theorem 10.1 by combining (10.8), (10.10), and (10.13), and recalling that |T ∗ | = (α + o(1))−K . The following lemma bounds the number of admissible pairs (S1 , c), as claimed in (10.12). It can be viewed as an extension of Lemma 5.1 from D = K to general D. Lemma 10.1. Given T1 ∼ = T for some T ∈ TD and D, µ1 ≤ K, it holds that K−µ1 4(K−D) d ∼ |{(S1 , c) : S1 = S for some S ∈ TD , c ∈ C(T1 ∪n S1 ), µ1 (c) = µ1 }| ≤ (4K) (2K) D!. D Proof. Since the d-nodes of T1 may have arbitrary even degrees, while the edges of T1 enter c as pairs sharing a common d-node, we begin by pairing the edges incident to each d-node of T1 . Let {ai }i∈[D] denote the degree sequence of the d-nodes of T1 , and define A ≜ {i ∈ [D] : ai ≥ 4}. Since the total number of edges is 2K, we have X 4|A| + 2(D − |A|) ≤ ai + 2(D − |A|) = 2K. i∈A

Thus |A| ≤ K − D and i∈A ai ≤ 2(K − D + |A|) ≤ 4(K − D). For a d-node of degree ai , the number of pairings of its incident edges is (ai − 1)!!; in particular, this pairing is unique when ai = 2. Hence, the total number of pairings of the edges of T1 is at most P Y Y a /2 (ai − 1)!! ≤ ai i ≤ (2K) i∈A ai /2 ≤ (2K)2(K−D) . (10.14) P

i∈A

For each such pairing of the edges of T1 , Lemma 5.1 gives at most (4K)K−µ1 ways to construct an alternating circuit decomposition c with µ1 4-circuits and the corresponding union of K blue edge pairs. At this stage, the blue part has K degree-2 d-nodes. To determine an unlabeled tree S ∈ TD , we merge these K degree-2 d-nodes into D nodes. Specifically, we choose D out of the K nodes, in at most K then merged with these D nodes, in D ways. The remaining K − D d-nodes are K−D K K−D at most D ways. In total, this can be done in at most D D ≤ (KD)K−D ≤ K 2(K−D) ways. Finally, to obtain S1 isomorphic to S, since n-nodes have already been labeled given the K blue d edge pairs, we only need to label the D d-nodes in D D! ways.

Acknowledgment J. Xu would like to thank Yihong Wu and Cheng Mao for inspiring discussions on efficient algorithms for matching random geometric graphs. T. Schramm would like to thank Jerry Li for suggesting the reference [CM17] for Weingarten calculus. J. Xu is supported in part by an NSF CAREER award CCF-2144593. T. Schramm is supported in part by NSF CAREER award CCF-2143246. This research began as a result of conversations at the IDEAL Institute Workshop on Learning in Networks in 2024. Part of this research was performed while X. Niu and J. Xu were visiting Simons Laufer Mathematical Sciences Institute in Berkeley, California, during the Spring 2025 semester. 60

References [ADH+ 08] Noga Alon, Phuong Dao, Iman Hajirasouliha, Fereydoun Hormozdiari, and S Cenk Sahinalp. Biomolecular network motif counting and discovery by color coding. Bioinformatics, 24(13):i241–i249, 2008. [AYZ95] Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. Journal of the ACM (JACM), 42(4):844–856, 1995. [BCL+ 19] Boaz Barak, Chi-Ning Chou, Zhixian Lei, Tselil Schramm, and Yueqi Sheng. (Nearly) efficient algorithms for the graph matching problem on correlated random graphs. In Advances in Neural Information Processing Systems, volume 32, 2019. [BG18] Sébastien Bubeck and Shirshendu Ganguly. Entropic CLT and phase transition in highdimensional wishart matrices. International Mathematics Research Notices, 2018(2):588– 606, 2018. [BH80] Terry Beyer and Sandra Mitchell Hedetniemi. Constant time generation of rooted trees. SIAM Journal on Computing, 9(4):706–712, 1980. [CB81] Charles J Colbourn and Kellogg S Booth. Linear time automorphism algorithms for trees, interval graphs, and planar graphs. SIAM Journal on Computing, 10(1):203–225, 1981. [CDGL26] Guanyi Chen, Jian Ding, Shuyang Gong, and Zhangsong Li. Detecting correlation efficiently in very supercritical stochastic block models: Breaking the otter’s threshold barrier. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2743–2759. SIAM, 2026. [CLO22] Sitan Chen, Jerry Li, and Ryan O’Donnell. Toward instance-optimal state certification with incoherent measurements. In Conference on Learning Theory, pages 2541–2596. PMLR, 2022. [CM17] Benoıt Collins and Sho Matsumoto. Weingarten calculus via orthogonality relations: new applications. ALEA, 14:631–656, 2017. [CR24] Shuwen Chai and Miklós Z Rácz. Efficient graph matching for correlated stochastic block models. Advances in Neural Information Processing Systems, 37:116388–116461, 2024. [DCK19] Osman E Dai, Daniel Cullina, and Negar Kiyavash. Database alignment with Gaussian features. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 3225–3233. PMLR, 2019. [DCKG19] Osman Emre Dai, Daniel Cullina, Negar Kiyavash, and Matthias Grossglauser. Analysis of a canonical labeling algorithm for the alignment of correlated Erdős–Rényi graphs. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 3(2):36:1– 36:25, June 2019. [DL17] Nadav Dym and Yaron Lipman. Exact recovery with symmetries for procrustes matching. SIAM Journal on Optimization, 27(3):1513–1530, 2017.

[DL25a] Jian Ding and Zhangsong Li. A polynomial time iterative algorithm for matching gaussian matrices with non-vanishing correlation. Foundations of Computational Mathematics, 25(4):1287–1344, 2025. [DL25b] Jian Ding and Zhangsong Li. A polynomial-time iterative algorithm for random graph matching with nonvanishing correlation. Mathematics of Operations Research, 2025. [EGMM24] Mathieu Even, Luca Ganassali, Jakob Maier, and Laurent Massoulié. Aligning embeddings and geometric random graphs: Informational results and computational approaches for the procrustes-wasserstein problem. Advances in Neural Information Processing Systems, 37:70730–70764, 2024. [FLM+ 20] Matthias Fey, Jan E Lenssen, Christopher Morris, Jonathan Masci, and Nils M Kriege. Deep graph matching consensus. In International Conference on Learning Representations, 2020. [FMWX23] Zhou Fan, Cheng Mao, Yihong Wu, and Jiaming Xu. Spectral graph matching and regularized quadratic relaxations I: Algorithm and Gaussian analysis. Foundations of Computational Mathematics, 23(5):1511–1565, 2023. [Gan22] Luca Ganassali. Sharp threshold for alignment of graph databases with gaussian weights. In Proceedings of the 2nd Mathematical and Scientific Machine Learning Conference, volume 145, pages 314–335. PMLR, 2022. [GJB19] Edouard Grave, Armand Joulin, and Quentin Berthet. Unsupervised alignment of embeddings with wasserstein procrustes. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1880–1890. PMLR, 2019. [GL24] Shuyang Gong and Zhangsong Li. The umeyama algorithm for matching correlated gaussian geometric models in the low-dimensional regime. arXiv preprint arXiv:2402.15095, 2024. [HS17] Samuel B Hopkins and David Steurer. Efficient bayesian estimation from few samples: community detection and related problems. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 379–390. IEEE, 2017. [Iss18] Leon Isserlis. On a formula for the product-moment coefficient of any order of a normal frequency distribution in any number of variables. Biometrika, 12(1/2):134–139, 1918. [JL15] Tiefeng Jiang and Danning Li. Approximation of rectangular beta-laguerre ensembles and large deviations. Journal of Theoretical Probability, 28(3):804–847, 2015. [KMW24] Dmitriy Kunisky, Cristopher Moore, and Alexander S Wein. Tensor cumulants for statistical inference on invariant distributions. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 1007–1026. IEEE, 2024. [KNW22] Dmitriy Kunisky and Jonathan Niles-Weed. Strong recovery of geometric planted matchings. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 834–876. SIAM, 2022. [Kuh55] Harold W Kuhn. The Hungarian method for the assignment problem. Naval research logistics quarterly, 2(1-2):83–97, 1955. 62

[KWB19] Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira. Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio. In ISAAC Congress (International Society for Analysis, its Applications and Computation), pages 1–50. Springer, 2019. [LCR+ 18] Guillaume Lample, Alexis Conneau, Marc’Aurelio Ranzato, Ludovic Denoyer, and Hervé Jégou. Word translation without parallel data. In International conference on learning representations, 2018. [Li26] Zhangsong Li. A computational transition for detecting multivariate shuffled linear regression by low-degree polynomials. IEEE Transactions on Information Theory, 72(4):2444–2456, 2026. [LM00] Beatrice Laurent and Pascal Massart. Adaptive estimation of a quadratic functional by model selection. Annals of statistics, pages 1302–1338, 2000. [Mat13] Sho Matsumoto. Weingarten calculus for matrix ensembles associated with compact symmetric spaces. Random Matrices: Theory and Applications, 2(02):1350001, 2013. [MDK+ 16] Haggai Maron, Nadav Dym, Itay Kezurer, Shahar Kovalsky, and Yaron Lipman. Point registration via efficient convex relaxation. ACM Transactions on Graphics (TOG), 35(4):1–12, 2016. [MMS10] Konstantin Makarychev, Rajsekar Manokaran, and Maxim Sviridenko. Maximum quadratic assignment problem: Reduction from maximum label cover and LP-based approximation algorithm. Automata, Languages and Programming, pages 594–604, 2010. [MRT23] Cheng Mao, Mark Rudelson, and Konstantin Tikhomirov. Exact matching of random graphs with constant correlation. Probability Theory and Related Fields, 186(1–2):327– 389, 2023. [MWXY24] Cheng Mao, Yihong Wu, Jiaming Xu, and Sophie H Yu. Testing network correlation efficiently via counting trees. The Annals of Statistics, 52(6):2483–2505, 2024. [MWXY25] Cheng Mao, Yihong Wu, Jiaming Xu, and Sophie H. Yu. Random graph matching at Otter’s threshold via counting chandeliers. Operations Research, 74(1):430–445, 2025. [Ott48] Richard Otter. The number of trees. Annals of Mathematics, 49(3):583–599, 1948. [OW22] Christoffer Olsson and Stephan Wagner. Automorphisms of random trees. In 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022), pages 16–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2022. [PS79] Edgar M Palmer and Allen J Schwenk. On the number of trees in a random forest. Journal of Combinatorial Theory, Series B, 27(2):109–121, 1979. [RCB97] Anand Rangarajan, Haili Chui, and Fred L Bookstein. The softassign procrustes matching algorithm. In Biennial International Conference on Information Processing in Medical Imaging, pages 29–42. Springer, 1997.

[SBH+ 19] Tim Stuart, Andrew Butler, Paul Hoffman, Christoph Hafemeister, Efthymia Papalexi, William M Mauck, Yuhan Hao, Marlon Stoeckius, Peter Smibert, and Rahul Satija. Comprehensive integration of single-cell data. cell, 177(7):1888–1902, 2019. [Sch66] Peter H Schönemann. A generalized solution of the orthogonal procrustes problem. Psychometrika, 31(1):1–10, 1966. [She99] William Fleetwood Sheppard. Iii. on the application of the theory of error to cases of normal distribution and normal correlation. Philosophical Transactions of the Royal Society of London, Series A: Containing Papers of a Mathematical or Physical Character, (192):101–167, 1899. [Ume88] Shinji Umeyama. An eigendecomposition approach to weighted graph matching problems. IEEE Transactions on Pattern Analysis and Machine Intelligence, 10(5):695–703, 1988. [Ver12] Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. pages 210–268, 2012. [Wei25] Alexander S Wein. Computational complexity of statistics: New insights from low-degree polynomials. arXiv preprint arXiv:2506.10748, 2025. [Wic50] Gian-Carlo Wick. The evaluation of the collision matrix. Physical review, 80(2):268, 1950. [WWXY22] Haoyu Wang, Yihong Wu, Jiaming Xu, and Israel Yolou. Random graph matching in geometric models: the case of complete graphs. In Conference on Learning Theory, pages 3441–3488. PMLR, 2022. [WXY22] Yihong Wu, Jiaming Xu, and Sophie H. Yu. Settling the sharp reconstruction thresholds of random graph matching. IEEE Transactions on Information Theory, 68(8):5391–5417, 2022. [ZSN+ 17] Andy Zeng, Shuran Song, Matthias Nießner, Matthew Fisher, Jianxiong Xiao, and Thomas Funkhouser. 3dmatch: Learning local geometric descriptors from rgb-d reconstructions. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1802–1811, 2017.

Record · ID 353061 · SHA-256 6f9b1d63f2ac39ef
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.