Spectral Embeddings of Degree-$α$ Laplacians in Random Dot Product Graphs

Spectral Embeddings of Degree-α Laplacians in Random Dot Product Graphs Ning Hao ∗ University of Arizona

John Park University of Hong Kong

arXiv:2608.10845v1 [stat.ML] 11 Aug 2026

Abstract Spectral clustering methods for network data are commonly based on a few matrix representations, such as the adjacency matrix and the symmetric Laplacian. We study a continuum of degree-normalized spectral embeddings that includes these commonly used choices as special cases. Under a random dot product graph model, we establish a row-wise central limit theorem for this family of embeddings. The result provides an explicit description of how degree normalization affects both population geometry and the local uncertainty of embedded nodes. We use the limiting distributions to compare different normalizations in two-community stochastic block models through a projected-Gaussian Bayes-error diagnostic. These comparisons show that no single normalization is uniformly preferred. Instead, the favored normalization depends on network density, community imbalance, and blockprobability structure. Typically, stronger normalization is favored in lower-density or more imbalanced settings. These results provide a unified distributional understanding of when and why alternative normalizations may improve spectral clustering.

Keywords: Central limit theorem, Degree-corrected stochastic block model, Imbalance, Network data, Spectral clustering. Mathematics Subject Classification (2020): 62H30

1

Introduction

Community detection is a fundamental statistical problem in network analysis. Given a single observed graph, the goal is to partition the nodes into groups with distinct connectivity patterns. A widely used approach to this task is spectral clustering (von Luxburg, 2007; Ng et al., 2001), which first embeds each node as a point in a low-dimensional space using the eigenvectors of a graph matrix, then partitions the resulting points with a clustering algorithm such as k-means. The performance of spectral clustering therefore depends on the graph matrix used to construct the embedding. Two standard choices are the adjacency matrix A and the symmetric Laplacian matrix D−1/2 AD−1/2 ,

where D is the diagonal matrix of observed node degrees. A large body of

literature has studied alternative normalizations and regularizations of the adjacency matrix ∗

Corresponding author: nhao@arizona.edu

1

(Jing et al., 2022; Amini et al., 2013; Qing and Wang, 2024; Qin and Rohe, 2013; Sarkar and Bickel, 2015; Priebe et al., 2019; Modell and Rubin-Delanchy, 2021), demonstrating that the choice of graph matrix can substantially affect the performance of spectral clustering. In this paper, we focus on one basic component of that choice: the amount of degree normalization applied before embedding. A natural one-parameter family generalizing the adjacency and symmetric Laplacian matrices is D−α AD−α ,

α ∈ [0, 1].

The choices α = 0 and α = 1/2 recover the adjacency and symmetric Laplacian matrices, respectively, while larger values of α apply stronger degree normalization. To the best of our knowledge, within the statistical literature on community detection, this continuous degreepower family was first studied by Ali and Couillet (2018), who considered a centered modularity formulation. Related uncentered formulations, including regularized variants, were subsequently studied by Fan et al. (2026) and Park (2025). In this paper, we study the uncentered family and investigate how the amount of normalization simultaneously changes the geometry and uncertainty of the spectral embedding. Our central question is whether different values of α can be systematically preferred for community detection and, if so, which features of the underlying network determine that preference. To preview the main geometric phenomenon, consider a degree-corrected stochastic block model (DCSBM) (Karrer and Newman, 2011). In this model, nodes are partitioned into communities, and each node is assigned an individual degree-correction parameter. Figure 1 shows the embeddings of a simple two-community DCSBM in which the nodes are randomly assigned one of three degree-correction parameters; Section 4 contains full modeling details. For the adjacency spectral embedding, corresponding to α = 0 and shown in Figure 1a, nodes from the same community, indicated by color, lie along a common ray from the origin, while the degreecorrection parameter, indicated by shade, determines their position along that ray. Figures 1b and 1c illustrate the first-order effect of increasing the amount of normalization. As α increases, the radial dependence on the degree-correction parameter is progressively reduced; at α = 1, it disappears entirely, and the population centers depend only on community membership. This radial variation makes it problematic to apply a clustering algorithm directly to the spectral embedding, because nodes in the same community may be separated by their degree parameters. This motivates the common preprocessing step of normalizing each embedding row to unit norm before clustering (Lei and Rinaldo, 2015; Qin and Rohe, 2013). Projecting the rows onto the unit sphere removes the within-community radial variation, so that the population centers from each community collapse to a common direction. After the usual orthogonal alignment, these community directions are independent of both the degree-correction parameter and α. Thus, after spherical row normalization, the different degree-α embeddings are equivalent at the first order, i.e., they have the same population community directions. They are not, however, equivalent at the second order. The Gaussian probability ellipses in Figure 1 show that the magnitude, shape, and orientation of the local fluctuations change with α. In this example, the ellipses become increasingly elongated in the direction of the line joining the corresponding community centers. Different values of α can thus produce different

2

amounts of overlap around the same population community directions. Population geometry and consistency results alone therefore cannot explain why one value of α may outperform another, and a more careful analysis of the second-order deviations is required. 150 20 100 25 10 50

0

0

0

−50 −10 −25 −100 −20 −150 −20

0

20

−40

(a) α = 0

0

40

−100

(b) α = 0.5

−50

0

50

100

(c) α = 1

Figure 1: Comparison of the degree-α spectral embeddings for a two-community DCSBM. Points are colored by community, with shading indicating the degree-correction parameter. The overlaid contours represent the 95% probability ellipses obtained from Corollary 1. Note that the axis scales differ between plots.

We analyze this phenomenon under the random dot product graph (RDPG) model, which includes the DCSBM with positive-semidefinite block-probability matrices as a special case. Our main theoretical result is a conditional row-wise central limit theorem for the uncentered degree-α spectral embedding. The result covers both dense and sparse regimes, requiring the expected-degree scale to grow faster than (log n)2 , and gives the limiting mean and covariance explicitly in terms of the latent-position distribution. We then use the limiting distributions implied by the central limit theorem to study how degree normalization affects row-normalized spectral clustering. For each value of α, we project the Gaussian approximations onto the unit sphere and compute the Bayes error for distinguishing the resulting community distributions. The minimizer of this error defines a normalization preferred under this Bayes-error criterion. Because the criterion relies on an asymptotic approximation and an idealized Bayes rule, it need not minimize the actual error for an observed network. We therefore compare its prediction with empirical misclassification rates in simulated networks. Across the two-community block models studied, stronger normalization tends to be favored when expected degrees are smaller or community proportions are more imbalanced. Row-wise central limit theorems for adjacency and symmetric Laplacian spectral embeddings are well established; see, respectively, Athreya et al. (2016) and Tang and Priebe (2018), as well as the overview of Agterberg and Cape (2026). More recently, Fan et al. (2026) establish asymptotic normality for a broad class of generalized and regularized Laplacian matrices that includes the degree-α family. Our result complements this general theory by working directly under the RDPG model, yielding explicit characterizations of the population centers and limiting covariances that can be specialized and interpreted under block models. Two complementary works are particularly relevant to our comparison of degree normalizations. Ali and Couillet (2018) study a centered modularity-based version of the degree-power 3

family under a dense heterogeneous DCSBM and select the amount of normalization according to a spectral detectability criterion. Cape et al. (2019a) use Chernoff information to compare adjacency and symmetric Laplacian embeddings under stochastic block models. Our analysis addresses a different question: how does degree normalization change the node-level overlap that remains after spherical row normalization? In this sense, we extend the distributional perspective of Cape et al. (2019a) across the continuous uncentered family, while targeting a performance criterion distinct from that of Ali and Couillet (2018). The present paper focuses on explaining the statistical consequences of degree normalization under a specified model. Selecting α from a single observed network is a related but distinct methodological problem. Park and Hao (2026) study degree-α spectral clustering from this perspective and propose a subsampling-based procedure for tuning α. Our contributions are threefold. First, we derive explicit conditional row-wise limiting distributions for degree-α spectral embeddings under the RDPG, covering both dense and sparse regimes. Second, under the DCSBM, we show that spherical row normalization makes the population community directions identical across α, while the projected uncertainty remains α-dependent. Our formulas characterize how normalization changes its magnitude, shape, and orientation. Third, we compare degree normalizations using a Bayes-error criterion, benchmark this comparison using Chernoff information, and investigate whether the predicted ordering is reflected in finite-sample spectral clustering. The remainder of the paper is organized as follows. In Section 2, we formally define the degree-α Laplacian and corresponding spectral embedding. In Section 3, we define random dot product graphs and state the central limit theorem for the embedding in terms of the relevant latent position distribution. Section 4 specializes the theorem to the DCSBM and formally analyzes the behavior observed in Figure 1. In Section 5, we study the implications of degree normalization for spectral clustering, and we conclude in Section 6.

2

Degree-α Laplacian Spectral Embeddings

Given an undirected, unweighted graph with no isolated vertices, let A ∈ {0, 1}n×n represent the adjacency matrix, where aij = 1 indicates an edge between nodes i and j. The degree matrix D is an n × n diagonal matrix whose diagonal entries are the node degrees, Dii =

P

j aij .

We

first define the symmetric Laplacian to be L̂sym = D−1/2 AD−1/2 . This definition differs from the definition of the symmetric Laplacian sometimes seen in the literature, Lsym = In − D−1/2 AD−1/2 . These matrices share eigenvectors, with the leading eigenvectors of the former corresponding to the trailing eigenvectors of the latter (von Luxburg, 2007). Following common practice in spectral clustering, we work with the normalized matrix itself. We analogously define the observed degree-α Laplacian to be L̂α = D−α AD−α ,

4

α ∈ [0, 1].

The degree-α Laplacian generalizes other common graph matrices, reducing to the adjacency matrix when α = 0 and the symmetric Laplacian when α = 1/2. We now define a spectral embedding for the degree-α Laplacian. Definition 1 (Degree-α Laplacian Spectral Embedding). Let A be an n × n adjacency matrix ⊤ be the rank-R truncated eigendecomposition of L̂ . That is, if λ̂ and let Ûα,R Λ̂α,R Ûα,R α α,1 ≥

λ̂α,2 ≥ · · · ≥ λ̂α,R are the R largest positive eigenvalues of L̂α , and ûα,1 , ûα,2 , . . . , ûα,R are the corresponding orthonormal eigenvectors, then Ûα,R is the n × R matrix whose columns are ûα,1 , . . . , ûα,R and Λ̂α,R = diag(λ̂α,1 , . . . , λ̂α,R ). A spectral embedding of L̂α is given by X̂α,R := 1/2

Ûα,R Λ̂α,R . The dimension of the embedding is often clear from context. In those cases, we suppress the dependence of these matrices on R.

3

Random Dot Product Graphs

In this section, we introduce the random dot product graph model and make its connection with the spectral embedding defined in the previous section explicit. In the random dot product graph model, each node is assigned a latent position in Rr , and the edge probability between two nodes is given by the dot product between the latent positions (Young and Scheinerman, 2007; Hoff et al., 2002; Handcock et al., 2007). Definition 2 (Random Graph). Let P = (pij ) be a symmetric n × n matrix with entries in [0, 1]. We define an undirected random graph with adjacency matrix A = (aij ) as follows. For i < j, the entries are independent and satisfy aij ∼ Bern(pij ). The remaining entries are aij =

 0,

i = j,

a , ji

i > j.

Definition 3 (Random Dot Product Graph Model). Let F be a distribution on Rr satisfying x⊤ y ∈ [0, 1] for all x, y ∈ Supp(F ). iid

Let ξ1 , . . . , ξn ∼ F , and let Ξ ∈ Rn×r be the matrix whose ith row is ξi⊤ . A random graph follows a random dot product graph model if, conditional on ξ1 , . . . , ξn , pij = ⟨ξi , ξj ⟩. Equivalently, P = ΞΞ⊤ . Remark 1. Using the convention that self-loops are excluded, we set the diagonal entries of A to zero. Therefore, in the RDPG model, E[A | ξ1 , . . . , ξn ] = P − diag(P ), 5

where diag(P ) denotes the diagonal matrix with the same diagonal as P . We denote this version of P by P ◦ = P − diag(P ). In the asymptotic regime of our theoretical results, the diagonal portion of P is negligible for the quantities of interest. Thus, in the main discussion, we sometimes suppress this distinction for clarity. In the appendix, where the distinction is needed for the proofs, we work explicitly with P ◦ . The random dot product graph model contains several familiar graph models as special cases. We briefly describe three examples to illustrate the role of the latent positions. Example 1 (Erdős–Rényi graph). In an Erdős–Rényi graph, for a given p ∈ [0, 1], every pair of distinct nodes is connected with probability p, so pij = p. This model can be written as an √ RDPG by taking r = 1 and assigning every node the same latent position ξi = p. Example 2 (Stochastic block model). In a stochastic block model (SBM), each node belongs to one of K communities (Holland et al., 1983). The community labels z1 , . . . , zn are independent copies of a random variable Z satisfying P(Z = k) = πk for k = 1, . . . , K. Given a symmetric matrix B ∈ [0, 1]K×K of community connection probabilities, the edge probabilities are pij = Bzi zj . If B is positive semidefinite with rank r, choose ν1 , . . . , νK ∈ Rr such that Bkℓ = ⟨νk , νℓ ⟩. Assigning node i the latent position ξi = νzi , we may write pij = Bzi zj = ⟨νzi , νzj ⟩ = ⟨ξi , ξj ⟩. Thus, the SBM can be represented as an RDPG, with community k associated with the latent position νk . Example 3 (Degree-corrected stochastic block model). The degree-corrected stochastic block model (DCSBM) generalizes the stochastic block model by assigning each node a degree-correction parameter (Karrer and Newman, 2011). Let Z be a random community label satisfying P(Z = k) = πk for k = 1, . . . , K, and let Θ be a random variable taking values in (0, 1], independent of Z. Let (z1 , θ1 ), . . . , (zn , θn ) be independent copies of (Z, Θ). Let B ∈ [0, 1]K×K be a symmetric matrix of community connection probabilities. The edge probabilities are then given by pij = θi θj Bzi zj . If B is positive semidefinite with rank r, choose ν1 , . . . , νK ∈ Rr such that Bkℓ = ⟨νk , νℓ ⟩. Assigning node i the latent position ξi = θi νzi , we may write pij = θi θj Bzi zj = ⟨θi νzi , θj νzj ⟩ = ⟨ξi , ξj ⟩. Thus, the DCSBM can be represented as an RDPG, with community k associated with the latent direction νk . The SBM is recovered as the special case Θ ≡ 1. To formulate our asymptotic results, we define a sequence of random graphs {An }n∈N , generated by the following process. 6

iid

1/2

Model 1. For each n ∈ N, draw ξ1 , . . . , ξn ∼ F . Let ρn ∈ (0, 1] and define Xi = ρn ξi . Conditional on these latent positions, generate An with independent upper-triangular entries satisfying aij ∼ Bern (ρn ⟨ξi , ξj ⟩) ,

i < j.

In Model 1, we distinguish the unscaled latent positions ξi ∼ F from the latent positions 1/2

used to generate the graph, Xi = ρn ξi . The quantity ρn drives the sparsity of the graph. We consider two asymptotic regimes for the sparsity factor. In the dense regime, ρn ≡ 1, and in the sparse regime, ρn → 0. These two cases are sufficient for our purposes, since if ρn → ρ∗ ∈ (0, 1], the limiting constant ρ∗ can be absorbed into the latent distribution, or for block models, into B. 1/2

Letting X denote the matrix whose ith row is Xi⊤ = (ρn ξi )⊤ , we have established that P = XX ⊤ . In this case, the adjacency spectral embedding X̂0 serves as a natural estimate of X, up to an orthogonal transformation. This relationship extends to the degree-α Laplacian. We first define the population degree-α Laplacian to be Lα = T −α P T −α , where T is a diagonal −α X, j̸=i pij , the expected degree of each node. We also write Xα = T obtaining the population decomposition Lα = Xα Xα⊤ = Uα Λα Uα⊤ . Thus, since L̂α is the natural

matrix with Tii =

P

sample analogue of Lα , the degree-α Laplacian spectral embedding X̂α serves as a natural estimate of Xα , again up to an orthogonal transformation. We formalize this intuition with the following theorem, which establishes a row-wise central limit theorem for the degree-α Laplacian spectral embedding. We now introduce the technical conditions required for our results to hold, which we assume throughout the theoretical results. Let ξ ∼ F denote a generic unscaled latent position, and define µ = E[ξ]. Condition 1. The following assumptions hold. (a) The latent position distribution F has bounded support in Rr , where r is fixed. Additionally, x⊤ y ∈ [0, 1]

for all x, y ∈ Supp(F ).

(b) The sparsity factor satisfies either ρn ≡ 1 or ρn → 0. In either case, δn := nρn satisfies δn −→ ∞. (log n)2 (c) There exists a constant c > 0 such that ⟨x, µ⟩ ≥ c

for all x ∈ Supp(F ).

(d) The support of F spans Rr . Remark 2. Condition 1a bounds the size of the latent positions and ensures that all dot products define valid edge probabilities. Condition 1b requires the expected-degree scale δn = nρn to grow faster than (log n)2 . Conditions of this form are standard in the spectral embedding literature. For comparison, Tang and Priebe (2018) require the corresponding expected-degree scale to grow 7

faster than (log n)4 for the adjacency and symmetric Laplacian cases. Condition 1c ensures that the expected-degree factors are uniformly bounded away from zero, which is needed to keep quantities such as ⟨x, µ⟩−1 uniformly bounded. Condition 1d ensures that the latent positions occupy all r dimensions. If the support of F spans a lower-dimensional subspace, we may simply take that subspace to be the latent dimension. Thus, we take R = r for the matrices in Definition 1. For α ∈ [0, 1], define "

#

ξξ ⊤ Υα = E . ⟨ξ, µ⟩2α Under Conditions 1c and 1d, Υα is positive definite. Conditions 1a and 1b ensure that the observed degrees are uniformly concentrated around their expectations (see Appendix A.2.1), while Condition 1c ensures the expected degrees are uniformly bounded away from zero. Thus, the observed degrees are uniformly positive with probability tending to one, and L̂α is well defined with probability tending to one. Theorem 1. Fix α ∈ [0, 1], and assume Condition 1 holds. Let {An }n≥1 be a sequence of RDPGs constructed according to Model 1, and let ξ ′ be an independent copy of ξ. Then there exists a sequence of orthogonal matrices Qn such that, for each fixed index i, conditional on ξi , nα+1/2 ραn

h

X̂α Qn

 i∗

− (Xα )i∗

where

i⊤

d

−→ N (0, Σα (ξi )) ,

−1 Υ−1 α Γρ,α (x)Υα , 2α ⟨x, µ⟩

Σα (x) = with

"    ⊤ # ′ ′  ξ αΥ x ξ αΥ x α α  ′ ′  E ′ ⟨x, ξ ⟩ (1 − ⟨x, ξ ⟩) − − ,    ξ ⟨ξ ′ , µ⟩2α ⟨x, µ⟩ ⟨ξ ′ , µ⟩2α ⟨x, µ⟩ Γρ,α (x) = "   ⊤ #  ′ ′  ξ αΥ x ξ αΥ x  α α ′ E ′ ⟨x, ξ ⟩  − − ,  ξ ′ 2α ′ 2α

⟨ξ , µ⟩

Interpretation

⟨x, µ⟩

⟨ξ , µ⟩

⟨x, µ⟩

ρn ≡ 1, ρn → 0.

Theorem 1 gives a row-wise Gaussian approximation for the degree-α spectral

embedding. In general, the statements of conditional convergence should be understood as convergence in probability of the corresponding distributional laws. After orthogonal alignment, the transpose of the ith row is approximately distributed as 

X̂α Qn

⊤ i∗



≈N

(Xα )⊤ i∗ ,

1 n2α+1 ρ2α n



Σα (ξi ) .

Thus, the choice of α affects the embedding in two ways. First, it changes the population embedding to Xα = T −α X, reweighting latent positions according to their expected degrees. Second, it changes the covariance Σα (x), which describes the shape and orientation of the uncertainty around each point. Consequently, different values of α can produce different signalto-noise tradeoffs, and need not be simple rescalings of the same embedding. This provides a basis for comparing choices of α in specific models, which we pursue in the following section.

8

Proof Sketch

The proof of Theorem 1 follows the approach of Tang and Priebe (2018), with

additional technical considerations when α > 1/2. We first write 



X̂α Qn − Xα = L̂α − Lα T −α X(X ⊤ T −2α X)−1 + Rsp,α Vα⊤ ,

(1)

where Rsp,α represents a spectral remainder term that is shown to be negligible after multiplication by nα+1/2 ραn . We then expand L̂α − Lα using a Taylor expansion, and show that many of the resulting terms are also negligible after multiplication by nα+1/2 ραn . Collecting the remaining terms ultimately allows us to write the leading terms in the expansion of the ith row as    −1 X t−α  (aij − pij )t−2α Xj∗  X ⊤ T −2α X + αt−α−1 (ti − di )Xi∗ + remainder, i

i

j

(2)

j̸=i

where ti and di denote the ith diagonal entry of T and D, respectively. Conditional on the latent positions, the two leading terms can be combined into a sum of independent random vectors, and a central limit theorem may be applied to produce the final result. The primary difficulty when considering general α ∈ [0, 1] is the presence of factors involving −1/2 Λα . The nonzero eigenvalues of Lα are of order δn1−2α , and hence

Λ−1/2 = O(δnα−1/2 ). α For α ≤ 1/2, this factor remains bounded, whereas for α > 1/2 it diverges. Consequently, several remainder terms that can be controlled by direct norm inequalities for α ≤ 1/2 require more structure-sensitive arguments when α > 1/2.

4

Spectral Embeddings Under Block Models

Under the DCSBM, defined in Example 3, the latent position distribution has a particularly simple structure. Let Θ be a random variable taking values in (0, 1], with support bounded away from zero, representing a generic degree-correction parameter. Let Z ∈ {1, . . . , K} be a community label independent of Θ satisfying P(Z = k) = πk . A generic latent position may then be written ξ = ΘνZ , where ν1 , . . . , νK ∈ Rr satisfy Bkℓ = ⟨νk , νℓ ⟩. Thus, nodes in the same community have latent positions lying along a common ray, with their distance from the origin scaled by the degree-correction parameter. In the remainder of the section, we formalize the two features previewed in Figure 1 from Section 1. We first summarize the model parameters used to generate the figure. A DCSBM is iid

used with n = 2000, π1 = π2 = 0.5, and degree-correction parameters θi ∼ Unif{1, 2/3, 1/3}, independently of the community labels. The block probability matrix is given by "

B=

0.5 0.3 0.3 0.5

#

.

The rows are scaled by nα+1/2 , and the asymptotic distributions are computed using Corollary 1 under the dense regime, ρn ≡ 1. The plotted points are the embedded rows, and the ellipses

9

show the corresponding 95% probability ellipses.

4.1

Population Geometry Under the DCSBM

To specialize Theorem 1 to the DCSBM, we first introduce some notation for the relevant quantities. Write θ̄ = E[Θ],

µ = θ̄

K X

πm νm ,

m=1

and for k ∈ {1, . . . , K}, define γk = ⟨νk , µ⟩ = θ̄

K X

πm Bkm .

m=1

Then ⟨ξ, µ⟩ = ΘγZ , and the matrix Υα in Theorem 1 becomes h

Υ̃α = E Θ2−2α

K iX π ν ν⊤

ℓ ℓ ℓ . γℓ2α

ℓ=1

With this notation, Theorem 1 specializes to the DCSBM as follows. Corollary 1. Assume the setting of Theorem 1, suppose that the random dot product graph follows the DCSBM described above, and let (Θ′ , Z ′ ) be an independent copy of (Θ, Z). For ϑ ∈ Supp(Θ) and k ∈ {1, . . . , K}, define ϑ1−α νk mα (ϑ, k) = γkα

and

∆α,k =

p

Θ′ B

−1 kZ ′ Υ̃α

αΥ̃α νk (Θ′ )1−2α νZ ′ − 2α γk γZ ′

!

.

Then, for each fixed index i, conditional on zi = k and θi = ϑ, there exists a sequence of orthogonal matrices Qn such that nα+1/2 ραn where Σα (ϑ, k) =

h

X̂α Qn

 i∗

− (Xα )i∗

i⊤

d

−→ N (0, Σα (ϑ, k)) ,

 h i
 ′ ⊤  EΘ′ ,Z ′ 1 − ϑΘ BkZ ′ ∆α,k ∆α,k ,  1−2α ϑ h i γk2α    EΘ′ ,Z ′ ∆α,k ∆⊤ , α,k

ρn ≡ 1, ρn → 0.

Moreover, p

nα ρα−1/2 (Xα )⊤ n i∗ −→ mα (ϑ, k). Proof. The stated covariance formula and central limit theorem follow by substituting the relevant DCSBM model parameters into Theorem 1. It remains to derive the limiting rescaled population center. Fix a node i with zi = k and θi = ϑ, and define (−i)

γk,n =

1X θj Bkzj . n j̸=i

10

Then α α−1/2 −α nα ρα−1/2 (Xα )⊤ ti Xi n i∗ = n ρn

−α



= nα ραn 

X

ϑνk

pij 

j̸=i

 (−i) −α



= nα ραn nρn ϑ γk,n ϑ1−α νk =  (−i) α . γk,n

ϑνk (3)

By the law of large numbers, (−i)

p

γk,n −→ γk = θ̄

K X

πℓ Bkℓ .

ℓ=1

Plugging this into Equation (3) gives the desired result, mα (ϑ, k) =

ϑ1−α νk . γkα

The expression for mα (ϑ, k) makes explicit how degree normalization changes the population geometry. At the population level, for α < 1, the center of a node with degree-correction parameter ϑ is proportional to ϑ1−α . Thus, within each community, the population centers lie along the ray spanned by νk , with ϑ determining the position along the ray. As α increases, this effect is reduced, and at α = 1 it disappears entirely. Consequently, all nodes in community k share the same limiting population center. This collapse to a common limiting population center is already implicit from the factorization Xα = T −α X and can be established without a row-wise central limit theorem. However, Corollary 1 additionally provides the corresponding second-order description in the form of the limiting covariance Σα (ϑ, k). To explain the elongating effect observed in Figure 1, it is useful to view the population centers in two ways. For a fixed community, varying ϑ traces the ray described above. For a fixed ϑ, the K community centers form a cross-section of these rays. In Figure 1, this is the vertical line joining the two centers with the same shade. The following corollary shows that, more generally, these fixed ϑ centers lie in an explicit affine hyperplane. Corollary 2. Assume the setting of Corollary 1 and suppose that B has rank K. For each α ∈ [0, 1], let hα be the unique vector satisfying α h⊤ α νk = γk ,

k = 1, . . . , K.

Then, for every ϑ ∈ Supp(Θ), the population centers mα (ϑ, 1), . . . , mα (ϑ, K) lie in the affine hyperplane n

o

1−α Hα,ϑ = x ∈ RK : h⊤ . αx = ϑ ⊤ , so that B = V V ⊤ . Since rank(B) = K, we have Proof. Let V ∈ RK×r have rows ν1⊤ , . . . , νK

rank(V ) = K. On the other hand, Condition 1d implies that ν1 , . . . , νK span Rr , and hence 11

rank(V ) = r. Thus, r = K and ν1 , . . . , νK form a basis of RK . Consequently, hα exists and is unique. Plugging in the definitions of hα and mα (ϑ, k) immediately gives 1−α h⊤ α mα (ϑ, k) = ϑ

h⊤ α νk = ϑ1−α , γkα

which proves that mα (ϑ, k) ∈ Hα,ϑ for every k = 1, . . . , K. Corollary 2 is useful for two reasons. First, when α = 1, we have h1 = µ. Thus, all the limiting population centers lie in the hyperplane n

o

H1,ϑ = x ∈ RK : µ⊤ x = 1 , and H1,ϑ is independent of ϑ. Second, these hyperplanes provide a natural reference for describing the orientation of the limiting covariance. We therefore decompose the covariance into components normal and tangential to Hα,ϑ . The resulting ratio quantifies the observed elongation of probability ellipses in Figure 1. Let uα =

hα , ∥hα ∥

Πα = IK − uα u⊤ α,

so that uα is normal to Hα,ϑ and Πα projects onto its tangent space. We may then define the normal variance and average tangential variance relative to this hyperplane by 2 σN,α,k (ϑ) = u⊤ α Σα (ϑ, k)uα

2 σT,α,k (ϑ) =

and

1 tr(Πα Σα (ϑ, k)Πα ) . K −1

2 Then, whenever σT,α,k (ϑ) > 0, we write

Fα,k (ϑ) :=

2 σN,α,k (ϑ) 2 σT,α,k (ϑ)

.

When ρn → 0, the only dependence of Σα (ϑ, k) on ϑ is through the scalar factor ϑ1−2α . Consequently, the ratio Fα,k (ϑ) does not depend on ϑ, and we may write it as Fα,k . Smaller values of Fα,k indicate that the limiting covariance is more strongly concentrated in directions tangent to Hα,ϑ .

4.2

A Symmetric Two-Community Example

We illustrate this ratio using a symmetric two-community DCSBM in the sparse regime, ρn → 0. An equivalent analysis could be carried out in the dense regime, though the computations are somewhat more involved. Consider the model 1 π1 = π2 = , 2

"

B=

12

p q

#

q p

,

p > q > 0.

A direct computation (Appendix B.2.1) gives Fα =

κ (1 − α(2 − α)rα ) , 1 − κ2 α(2 − α)rα

where p−q κ= p+q


2

E Θ2−2α . rα = θ̄ E[Θ3−4α ] 

and

If Θ is constant, i.e., if there is no degree heterogeneity and the model reduces to an SBM, rα = 1 and the expression simplifies to Fα =

κ(1 − α)2 . 1 − (κ)2 α(2 − α)

This quantity is strictly decreasing in α and is exactly 0 when α = 1. Qualitatively, in this setting, the covariance matrices become progressively flatter and are singular at α = 1, with all variation lying parallel to the hyperplane containing the limiting population centers. When Θ is not constant, an application of Cauchy–Schwarz gives 0 ≤ rα ≤ 1. Holding rα fixed, the expression for Fα is decreasing in α. Although rα does affect how Fα changes with α, this nevertheless identifies one mechanism contributing to the general flattening seen in the example of Figure 1. While Fα,k summarizes the shape of the within-community covariance, it does not fully capture the overall separation between communities. In the next section, we thus compare the resulting community distributions directly.

5

Comparing Degree Normalizations for Community Detection

To study how different degree normalizations affect community detection, we consider a rownormalized spectral clustering algorithm (Jin, 2015; Qin and Rohe, 2013). Under the DCSBM, the row-normalization step is included to remove the effect of the degree-correction parameter at the population level. For each choice of α, the degree-α spectral embedding is computed, its rows are normalized, and k-means is applied to the resulting points. The algorithm is summarized in Algorithm 1. In this section, we continue under the assumption that B has rank K. Algorithm 1 Row-Normalized Degree-α Spectral Clustering Require: Degree-α Laplacian L̂α ; number of communities K Ensure: Estimated community labels ẑ1 , . . . , ẑn 1: Compute the degree-α spectral embedding X̂α,K ∈ Rn×K from L̂α . 2: Normalize the rows of X̂α,K and let X̃α,K denote the normalized embedding. 3: Apply k-means to the rows of X̃α,K . 4: Return the resulting cluster labels ẑ1 , . . . , ẑn . It is natural to ask how the choice of α affects spectral clustering performance. In the

13

following section, we study this question by comparing the projected Gaussian distributions predicted by asymptotic theory.

5.1

Comparing the Projected Distributions

We now restrict our attention to two-community SBMs and describe a diagnostic for comparing different values of α in spectral clustering. Following the idealization used by Cape et al. (2019a), we adopt two approximations. First, we treat the asymptotic Gaussian approximation from Corollary 1 as the exact finite-sample distribution of an embedded row. Second, we condition on a fixed community assignment, with deterministic community sizes chosen to match the specified community proportions. Together, these assumptions define the surrogate distributions compared below. Consequently, the value of α preferred by the diagnostic need not coincide with the value that minimizes the actual finite-sample error of spectral clustering. Finally, because this section concerns inference from a single observed graph rather than a sequence of graphs, we set ρn ≡ 1 and interpret sparsity through the magnitudes of the entries of B. We now compare values of α by applying the row-normalization step from Algorithm 1 to these Gaussian approximations and evaluating the Bayes error of the resulting projected distributions. Concretely, for each α ∈ [0, 1] and k ∈ {1, 2}, let mα,k and Σα,k denote the limiting population center and covariance matrix of a node in community k, respectively. Let (n)

Qk,α denote the distribution obtained by projecting a draw from 1 N mα,k , Σα,k n 



onto the unit circle using ψ(x) = x/ ∥x∥. Strictly speaking, the distribution here is a scaled (n)

version of the one derived in Corollary 1. Because this distribution is projected to get Qk,α , this scaling is irrelevant. However, this scale makes clear how the distribution changes as n increases. To quantify the overlap between the distributions, we consider the Bayes error Eα(n) =

inf

ϕ:S1 →{1,2}

2 X

(n)

πk Qk,α

n

u ∈ S1 : ϕ(u) ̸= k

o

,

k=1 (n)

where πk denotes the probability of a node belonging to community k. Smaller values of Eα indicate better distinguishability between the communities. We are therefore interested in αn∗ ∈ arg min Eα(n) .

(4)

α∈[0,1]

We refer to αn∗ as the “preferred” degree normalization for the specified model and value of n, where the comparison is understood to be with respect to the Bayes-error criterion rather than (n)

actual finite-sample clustering error. Although Eα → 0 for every fixed α, the relative ordering across α may stabilize as n increases. We next describe how we compute αn∗ in practice.

14

5.2

Numerical Evaluation

In the next two sections, we consider a family of models corresponding to a range of parameter settings. For each setting, we use the explicit expressions for the means and covariance matrices from Corollary 1 to numerically evaluate Equation (4). We approximate αn∗ by the grid point that (n)

minimizes Eα . For the remaining computations, we set n = 200 and suppress the dependence on n, writing the resulting minimizer as α∗ . Further computational details, including the stability of α∗ with respect to n, can be found in Appendix B.1. This diagnostic is closely related to the Chernoff-information comparison used by Cape et al. (2019a) for adjacency and symmetric Laplacian embeddings. Chernoff information is a natural criterion because it characterizes the asymptotic exponential decay rate of the Bayes error and has an explicit form for multivariate Gaussian distributions. We target the Bayes error directly because we apply the row-normalization step used in Algorithm 1 before evaluating community separation. The resulting projected Gaussian distributions are no longer Gaussian, so the corresponding Chernoff information does not retain the same convenient closed form. Further comparisons with the Chernoff-information benchmark are provided in Appendix B. For selected parameter settings, we also simulate networks and compare the predicted α∗ with the finite-sample misclassification rates of Algorithm 1. Although the error of the kmeans decision rule need not approach the Bayes error, these comparisons are intended to assess whether the broad ordering across values of α predicted by the projected Gaussian distributions is reflected in the performance of the actual clustering procedure typically used in practice.

5.3

Imbalanced Communities

We begin by considering an SBM on n nodes with "

B=

p q

#

q p

,

p > q.

Let π denote the proportion of nodes in community 1, so that π1 = π and π2 = 1 − π. Figure 2 illustrates how α∗ varies with p, q, and π. Each heat map shows a clear dark region in which adjacency spectral clustering, corresponding to α = 0, is preferred. This region generally occurs when p and q are both relatively large, with α∗ increasing as these values decrease. We now evaluate whether this behavior is reflected in finite-sample performance of Algorithm 1. To further isolate the effect of community imbalance, we fix p and q and vary only the community proportions. We use "

B=

0.30 0.21

#

0.21 0.30

with n = 350, π = 0.5 + 0.04c, and c ∈ {0, . . . , 10}. The results of this experiment are shown in Figure 2d, which plots the overall misclassification rate as a function of π. Lighter shades correspond to stronger degree normalization. This finite-sample experiment shows that when the communities are nearly balanced, the choice of α has little effect. However, as the imbalance increases, smaller values of α perform progressively worse. Overall, both the analysis of α∗ and numerical evidence support the idea that stronger normalization can mitigate the deterioration

15

α* 1.00 0.75

0.75

0.75

0.50

q

0.50

q

q

0.75 0.50

0.50 0.25

0.25

0.25

0.25

0.00 0.25

0.50

0.75

0.25

0.50

p

0.75

0.25

0.50

p

p

(b) π = 0.7

Misclassification Rate

(a) π = 0.5

0.75

(c) π = 0.9

0.4 0.3 0.2 0.1 0.0 0.5

0.6

α

0

0.7

0.8

π

0.25

0.5

0.75

0.9

1

(d) Numerical Results

Figure 2: The top row shows α∗ as a function of p, q, and π, while the bottom panel reports the average misclassification rates over 500 runs of spectral clustering for varying α. Error bars indicate ±2 standard errors across the 500 replications. Both results suggest that stronger normalization is favored as the communities become more imbalanced.

of spectral clustering performance caused by community imbalance.

5.4

Unequal Within-Community Probabilities

In this section, we consider an SBM on n nodes with 1 π1 = π2 = , 2

"

B=

p q q r

#

,

pr − q 2 > 0.

Here, r denotes a block-probability parameter rather than the latent position dimension introduced earlier. Since the embedding dimension is fixed at two throughout this section, the distinction should be clear from context. The condition pr − q 2 > 0 ensures that B is positive definite. When p ̸= r, the two communities have different expected-degree scales, so degree normalization may affect the two blocks differently. The left panel of Figure 3 shows that the preferred amount of normalization depends strongly on B. Larger values of α are favored throughout much of the low-q region, whereas little or no normalization is preferred when both q and r are relatively large. Thus, even with balanced communities, no single value of α is uniformly preferable.

16

0.40

Misclassification Rate

r

0.75

0.50

0.25

0.35

0.30 (0.1, 0.1)

0.1

0.2

0.3

0.4

0.5

q 0.25

α* 0.00

0.25

0.50

0.75

0.0

1.00

0.1

(a) Fixed p = 0.25

0.2

0.3

0.4

0.5

α

0.6

0.7

0.8

0.9

1.0

(b) Numerical Results

Figure 3: The left panel shows α∗ as a function of q and r with p fixed at 0.25. The right panel reports the average misclassification rates over 500 runs of spectral clustering for varying α with p = 0.25, q = 0.1, and r = 0.1, corresponding to the labeled point in the left panel. Error bars indicate ±2 standard errors across the 500 replications. Both results suggest that an intermediate value of α is appropriate for these parameters, though the values do not agree exactly.

We next examine finite-sample performance in the setting "

B=

0.25 0.10

#

0.10 0.10

with n = 200 and α ∈ {0, 0.1, . . . , 1}. For each value of α, we apply Algorithm 1 and average the overall misclassification rate over 500 replications. As shown in Figure 3b, the average misclassification rate is minimized near α = 0.4, with α = 0.5 giving comparable performance. This minimizer does not coincide with the predicted α∗ ≈ 0.8, though some discrepancy is expected due to the assumptions used in computing α∗ . Nevertheless, both suggest that an intermediate amount of normalization is preferred, and possible sources of this discrepancy are discussed in Section 6.

6

Discussion

We have studied a continuum of degree-normalized spectral embeddings that contains the adjacency and symmetric Laplacian embeddings as special cases. Under the random dot product graph model, we derived a row-wise central limit theorem describing how the choice of α changes both the population geometry and the local uncertainty of the embedded nodes. Specializing these expressions to the DCSBM, we showed that increasing α progressively removes the effect of degree heterogeneity from the population embedding. In particular, when α = 1, the population centers depend only on community membership and, when B is full rank, lie in a common affine hyperplane. The same expressions describe the accompanying change in the shape and

17

orientation of the limiting covariance, which can flatten toward that hyperplane as α increases. These results also provide a basis for comparing degree normalizations in community detection. For the single-graph comparisons in Section 5, we take ρn ≡ 1 and interpret sparsity through the magnitudes of the entries of B. In the balanced two-community SBM, shown in Figure 2a, stronger normalization is preferred when the entries of B are relatively small, whereas little or no normalization is preferred when they are large. Community imbalance (Section 5.3) and unequal within-community probabilities (Section 5.4) alter the preferred normalization, so that it depends on community proportions and block-probability structure as well as on overall density. The finite-sample experiments indicate that the broad normalization regime suggested by α∗ is also reflected in the performance of row-normalized spectral clustering. We now discuss several limitations and possible extensions of this work. Our analysis focused on the RDPG, which requires B to be positive semidefinite, so many disassortative and other indefinite structures lie outside the present model. The generalized RDPG (Rubin-Delanchy et al., 2022) would be the natural setting for such an extension. The numerical comparison in Section 5.4 also illustrates how α∗ should be interpreted. The quantity is computed under two idealizations. The first is that the row-wise Gaussian approximation of Theorem 1 is exact at the sample size considered. The second is that clustering is carried out by the Bayes rule for the projected distributions rather than by k-means. Neither holds in finite samples, and α∗ should therefore not be expected to coincide with the empirical minimizer. One possible source of the finite-sample discrepancy is the contribution of higherorder terms arising from the use of observed rather than expected degrees. Such higher-order terms may become more visible as α increases, particularly when the first-order covariance is nearly singular. A related practical extension is degree regularization. Replacing D by Dτ = D + τ I for some τ > 0 (typically the average observed degree) is a standard approach in spectral clustering (Amini et al., 2013; Qin and Rohe, 2013), as it limits the influence of nodes with very small observed degrees. We have deliberately worked throughout with the unregularized family D−α AD−α in order to isolate the effect of degree normalization without introducing a second tuning parameter. Extending this family to Dτ−α ADτ−α and studying the joint roles of α and τ is a natural direction for future work. However, the population target associated with Dτ involves T + τ I, which does not cancel the degree-correction parameter exactly, so the collapse of the population centers at α = 1 described in Corollary 2 is recovered only when τ /δn → 0. Regularization would therefore trade part of the population geometry that motivates large α against the finite-sample stability described above. Characterizing this tradeoff, together with the corresponding projected Gaussian diagnostic, warrants further investigation. Taken together, our results suggest that the amount of degree normalization affects both first-order geometry and second-order uncertainty of the corresponding embeddings. It should therefore be viewed as a model-dependent design choice rather than as a universal default.

18

References Joshua Agterberg and Joshua Cape. An overview of asymptotic normality in stochastic blockmodels: Cluster analysis and inference. Statistical Science, 41(2):354–385, 2026. Hafiz Tiomoko Ali and Romain Couillet. Improved spectral community detection in large heterogeneous networks. Journal of Machine Learning Research, 18:1–49, 2018. Arash A Amini, Aiyou Chen, Peter Bickel, and Liza Levina. Pseudo-likelihood methods for community detection in large sparse networks. The Annals of Statistics, pages 2097–2122, 2013. A Athreya, CE Priebe, M Tang, V Lyzinski, DJ Marchette, and DL Sussman. A limit theorem for scaled eigenvectors of random dot product graphs. Sankhyā: The Indian Journal of Statistics, Series A (2008-), 78(1):1–18, 2016. Stéphane Boucheron, Gábor Lugosi, and Pascal Massart.

Concentration Inequalities: A

Nonasymptotic Theory of Independence. Oxford University Press, 2013. Joshua Cape, Minh Tang, and Carey E Priebe. On spectral embedding performance and elucidating network structure in stochastic blockmodel graphs. Network Science, 7(3):269–291, 2019a. Joshua Cape, Minh Tang, and Carey E Priebe. The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics. The Annals of Statistics, 47(5): 2405–2439, 2019b. Jianqing Fan, Yingying Fan, Jinchi Lv, Fan Yang, and Diwen Yu. Asymptotic theory of eigenvectors for latent embeddings with generalized Laplacian matrices. IEEE Transactions on Information Theory, 72(8):5970–6022, 2026. doi: 10.1109/TIT.2026.3699098. Mark S Handcock, Adrian E Raftery, and Jeremy M Tantrum. Model-based clustering for social networks. Journal of the Royal Statistical Society Series A: Statistics in Society, 170(2): 301–354, 2007. Peter D Hoff, Adrian E Raftery, and Mark S Handcock. Latent space approaches to social network analysis. Journal of the American Statistical Association, 97(460):1090–1098, 2002. doi: 10.1198/016214502388618906. Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social Networks, 5(2):109–137, 1983. Jiashun Jin. Fast community detection by SCORE. The Annals of Statistics, 43(1):57–89, 2015. Bing-Yi Jing, Ting Li, Ningchen Ying, and Xianshi Yu. Community detection in sparse networks using the symmetrized Laplacian inverse matrix (SLIM). Statistica Sinica, 32(1):1–22, 2022. Brian Karrer and Mark EJ Newman. Stochastic blockmodels and community structure in networks. Physical Review E—Statistical, Nonlinear, and Soft Matter Physics, 83(1):016107, 2011. 19

Jing Lei and Alessandro Rinaldo. Consistency of spectral clustering in stochastic block models. The Annals of Statistics, 43(1):215–237, 2015. Alexander Modell and Patrick Rubin-Delanchy. Spectral clustering under degree heterogeneity: a case for the random walk Laplacian, 2021. URL https://arxiv.org/abs/2105.00987. Andrew Ng, Michael Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. Advances in Neural Information Processing Systems, 14, 2001. John Park and Ning Hao. Degree-corrected spectral clustering for heterogeneous and imbalanced networks. manuscript, 2026. John Jeongsoo Park. Spectral Analysis of the Degree-Corrected Laplacian. PhD thesis, The University of Arizona, Tucson, Arizona, 2025. URL https://repository.arizona.edu/ handle/10150/679216. Carey E Priebe, Youngser Park, Joshua T Vogelstein, John M Conroy, Vince Lyzinski, Minh Tang, Avanti Athreya, Joshua Cape, and Eric Bridgeford. On a two-truths phenomenon in spectral graph clustering. Proceedings of the National Academy of Sciences, 116(13):5995– 6000, 2019. Tai Qin and Karl Rohe. Regularized spectral clustering under the degree-corrected stochastic blockmodel. In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013. Huan Qing and Jingli Wang. Applications of dual regularized Laplacian matrix for community detection. Advances in Data Analysis and Classification, 18(4):1001–1043, December 2024. ISSN 1862-5347, 1862-5355. doi: 10.1007/s11634-023-00565-3. Patrick Rubin-Delanchy, Joshua Cape, Minh Tang, and Carey E Priebe. A statistical interpretation of spectral embedding: the generalised random dot product graph. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84(4):1446–1473, 2022. Purnamrita Sarkar and Peter J Bickel. Role of normalization in spectral clustering for stochastic blockmodels. The Annals of Statistics, pages 962–990, 2015. Minh Tang and Carey E Priebe. Limit theorems for eigenvectors of the normalized Laplacian for random graphs. The Annals of Statistics, 46(5):2360–2415, 2018. Joel A Tropp. User-friendly tail bounds for sums of random matrices. Foundations of Computational Mathematics, 12(4):389–434, 2012. Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018. Ulrike von Luxburg. A tutorial on spectral clustering. Statistics and computing, 17(4):395–416, 2007.

20

Stephen J Young and Edward R Scheinerman. Random dot product graph models for social networks. In International workshop on algorithms and models for the web-graph, pages 138– 149. Springer, 2007. Yi Yu, Tengyao Wang, and Richard J Samworth. A useful variant of the Davis–Kahan theorem for statisticians. Biometrika, 102(2):315–323, 2015.

A

Proof of Theorem 1

The proof of Theorem 1 is technical and notation-heavy, but, as outlined in Section 3, the overall structure is relatively simple. This section of the appendix is organized as follows. In Section A.1, we first list commonly used notation throughout the proof. Section A.2 then proves several technical lemmas that will be used frequently throughout the proof of the theorem. Section A.3 derives Equation (1) and shows that the spectral remainder is negligible after scaling by nα+1/2 ραn . Finally, Section A.4 proves Theorem 1.

A.1

Notation and Preliminaries for Proof

We first introduce some notation used throughout the appendix. For a matrix M , let Mi∗ denote its ith row. We write ∥M ∥ for the spectral norm of a matrix, ∥M ∥F for the Frobenius norm, ∥M ∥∞ := maxi

j |Mij | for the induced matrix infinity norm, and ∥M ∥2→∞ := maxi ∥Mi∗ ∥2

P

for the two-to-infinity norm of a matrix (Cape et al., 2019b). Throughout the proof, we fix α. Additionally, we now make explicit the matrix Qn that appears in the statement of Theorem 1. Let ⊤ Uα⊤ Ûα = W1,n Sn W2,n ⊤ . We choose V so that U = be a singular value decomposition, and define Wn := W2,n W1,n α α −1/2

T −α XVα Λα

1/2

. It follows that Xα = Uα Λα Vα⊤ . We then define Qn := Wn Vα⊤ . Because α

is fixed, we suppress the dependence of these matrices on α in the notation. The table below contains additional notation and descriptions.

A.2

Helper Lemmas

A.2.1

Commonly Used Bounds

Lemma 1. Under Condition 1, the following bounds hold with high probability.

21

Quantity

Definition

Description

Pdiag , P ◦ EA

Pdiag = diag(P ), P ◦ = P − Pdiag EA = A − P ◦

Diagonal correction and loop-free population matrix Centered adjacency noise

d, D

d = A1,

D = diag(d)

Observed degrees

t, T

t = P ◦ 1,

T = diag(t)

Expected degrees

δn

δn = nρn

Expected-degree scale

Eα

Eα = L̂α − Lα

Perturbation of the degree-α Laplacian

Gn,α

Gn,α = X ⊤ T −2α X

Gram matrix associated with Lα

Uα , Vα , Λα

Lα = Uα Λα Uα⊤ ,

Population eigendecompositions

Π⊥ (Uα )

Gn,α = Vα Λα Vα⊤ ⊤ , Uα⊤ Ûα = W1,n Sn W2,n ⊤ Wn = W2,n W1,n Qn = Wn Vα⊤ Π⊥ (Uα ) = In − Uα Uα⊤

BD , RD

BD = αT −α−1 (T − D),

Wn Qn

Procrustes alignment of the sample and population eigenspaces. Alignment of X̂α and Xα . Projection onto the orthogonal complement of the population eigenspace. First-order and remainder terms in the expansion of D−α .

RD = D−α − T −α − BD

Table 1: Notation used repeatedly in the proof.

Population bounds T −α = O(δn−α )

(5a)

∥P ∥ = O(δn ),

(5b)

2α−1 G−1 ), n,α = O(δn

(5c)

Λ−1/2 = O(δn−1/2+α ), α

(5d)

∥Uα ∥2→∞ = O(n−1/2 ).

(5e)

∥D − T ∥ = OP (δn1/2 log n)

(5f)

D−α = OP (δn−α ),

(5g)

cδn ≤ min ti ≤ max ti ≤ Cδn , i

i

∥Pdiag ∥ = O(ρn ), λmin (Gn,α ) ≍ λmax (Gn,α ) ≍ δn1−2α , min Λα ≍ max Λα ≍ δn1−2α ,

Degree and adjacency concentration |di − ti | = OP (δn1/2 ) for each i,

p

cδn ≤ min di ≤ max di ≤ Cδn , i

i

p −α−1/2

D−α − T −α = OP (δn

log n),

(5h)

log n),

(5i)

|(EA )ij | = OP (δn ).

(5j)

∥EA ∥ = OP (δn1/2 max i

Taylor expansion terms

22

X j

p

|(BD )ii | = OP (δn−α−1/2 ) for each i,

∥BD ∥ = OP (δn−α−1/2 log n),

(5k)

∥RD ∥ = OP (δn−α−1 log n),

(5l)

p

|(RD )ii | = OP (δn−α−1 ) for each i, Error bounds

∥Eα ∥ = OP (δn1/2−2α log n), p

max i

X

|(Eα )ij | = OP (δn1−2α ),

(5m) (5n)

j

Proof. We first establish the population bounds, where probability is with respect to the latent positions. For the remaining bounds, we condition on the latent positions and work on the event that the population bounds hold. Since this event has probability tending to one and the conditional bounds are uniform over this event, the corresponding unconditional bounds hold. Population bounds For Equation (5a), write ti = ρn

X

ξi⊤ ξj

j̸=i





n ti 1 1X ξj  − ξi⊤ ξi . = ξi⊤  δn n j=1 n

By the law of large numbers and Condition 1a, the right-hand side converges to ξi⊤ µ uniformly in i. Thus, max i

ti p − ξi⊤ µ → 0. δn

(6)

By Conditions 1a and 1c, ξi⊤ µ is uniformly bounded above and away from zero. Equation (6) therefore implies the first inequality in Equation (5a) with high probability. The second statement follows immediately. For Equation (5b), pii = Xi⊤ Xi = ρn ξi⊤ ξi . By Condition 1a, this is bounded above by a constant times ρn , and the first statement follows. For the second statement, the Gershgorin circle theorem states that the eigenvalues of a symmetric matrix with nonnegative entries are bounded above by its row sums. The bound then follows from Equation (5a) and the first statement, since the row sums of P are given by ti + pii . 1/2

For Equation (5c), we use the facts that Xi = ρn ξi and ti ≍ δn to write Gn,α = X ⊤ T −2α X =

n X

t−2α Xi Xi⊤ i

i=1

= ρn δn−2α

n X

ξi ξi⊤ . (t /δ )2α i=1 i n

By Equation (6), δn2α−1 Gn,α =

n ξi ξi⊤ 1X + oP (1). n i=1 ⟨ξi , µ⟩2α

By Conditions 1a and 1c, the right-hand side converges to Υα , which is a fixed, r-dimensional

23

positive definite matrix. The first statement follows, and the second statement follows immediately from the first. For Equation (5d), note that we want to bound the eigenvalues of Lα = T −α XX ⊤ T −α . Since Gn,α = X ⊤ T −2α X, the nonzero eigenvalues of Lα and Gn,α are the same. The statements then follow immediately from Equation (5c). −1/2

For Equation (5e), write Gn,α = Vα Λα Vα⊤ and Uα = T −α XVα Λα

. It is straightforward to

verify Uα⊤ Uα = Ir and Lα Uα = Uα Λα . Thus, for each i, −1/2 ∥(Uα )i∗ ∥ ≤ t−α . i ∥Xi ∥ Λα

Using Equations (5a), (5d) and Condition 1, 



−1/2+α ∥(Uα )i∗ ∥ = O δn−α ρ1/2 = O(n−1/2 ). n δn

The statement follows by taking the maximum over i. Degree and adjacency concentration Throughout the remainder of the proof, we write C for a positive constant independent of n, whose values may change from line to line. Additionally, we write M for a sufficiently large positive constant, chosen as needed. For Equation (5f), note that di − ti is a sum of mean-zero random variables. Furthermore, the summands are bounded by 1 and the sum of the variances is bounded by ti . By Equation (5a),

j̸=i pij = ti ≤ Cδn . Thus, by Bernstein’s inequality (see,

P

for example, Boucheron et al. (2013)), for all u > 0, !

u2 P (|di − ti | > u) ≤ 2 exp − . 2(Cδn + u/3) 1/2

Choosing u = M δn , we have, for n sufficiently large, 

P

|di − ti | > M δn1/2



!

M 2 δn

≤ 2 exp −

1/2

2(Cδn + M δn /3) !

M2

≤ 2 exp −

1/2

2(C + M/(3δn )) 



≤ 2 exp −CM 2 . 1/2 √

The first statement follows. The second statement is similar, choosing u = M δn

log n and

taking a union bound. Equations (5g) and (5h) follow easily from Equations (5a) and (5f). For Equation (5i), note that we may write EA as a sum of independent, symmetric, mean⊤ zero matrices by defining Yij = (EA )ij (ei e⊤ j + ej ei ), where ek denotes the kth standard basis

vector in Rn . Then ⊤ ∥Yij ∥ ≤ |(EA )ij | ei e⊤ ≤ 1. j + ej ei

Additionally, X i<j

E(Yij2 ) =

X

⊤ pij (1 − pij )(ei e⊤ i + ej ej ),

i<j

24

so X

E(Yij2 ) ≤ max i

i<j

X

pij (1 − pij ) ≤ max i

j̸=i

X

pij = max ti ≤ Cδn . i

j̸=i

Thus, by the matrix Bernstein inequality (see, for example, Tropp (2012)), for all u > 0, !

u2 P (∥EA ∥ > u) ≤ 2n exp − . 2(Cδn + u/3) 1/2 √

Choosing u = M δn 

P

log n,

∥EA ∥ > M δn1/2

p

M 2 δn log n log n ≤ 2n exp − 1/2 √ 2(Cδn + M δn log n/3) 



!



≤ 2n exp −CM 2 log n . The statement follows by choosing M sufficiently large. For Equation (5j), we write X

|(EA )ij | =

j

X

|aij − pij | ≤

j̸=i

X

aij +

j̸=i

X

pij = di + ti .

j̸=i 1/2 √

By Equation (5a), we have ti = O(δn ) and by Equation (5f), we have di = ti + OP (δn √ 1/2 OP (δn ), since log n = o(δn ). The statement follows.

log n) =

Taylor expansion terms (ti − di ) and use Equations (5a) and (5f). For Equation (5k), we write (BD )ii = αt−α−1 i For Equation (5l), we use Taylor’s theorem to write 



d−α = t−α + αt−α−1 (ti − di ) + O t−α−2 (di − ti )2 , i i i i then apply Equations (5a) and (5f) to the last term. Error bounds For Equation (5m), we first write Eα = T −α EA T −α + BD P T −α + T −α P BD + BD EA T −α + T −α EA BD + RE , where RE = RD (P + EA )T −α + T −α (P + EA )RD + BD (P + EA )BD + BD (P + EA )RD + RD (P + EA )BD + RD (P + EA )RD − (T −α + BD + RD )Pdiag (T −α + BD + RD ). By Equations (5a) and (5i), T −α EA T −α ≤ T −α

2





∥EA ∥ = OP δn1/2−2α log n . p

Each of the remaining terms may be individually bounded. Because this decomposition 25

appears several times throughout the appendix in slightly different forms, we prove a slightly more general form in Lemma 2. Using the notation of the lemma, let H = P + EA = A + Pdiag . Since H is symmetric and maxi

j |hij | = OP (δn ), the operator-norm version of Lemma 2,

P

applied with V = In gives 

BD HT −α + T −α HBD = OP δn1/2−2α log n p



and 



∥RH,In ∥ = OP (δn−2α log n) = oP δn1/2−2α log n . p

This bounds the first six terms of RE . For the last term, use Equations (5a), (5k), (5l), and (5b) to get (T −α + BD + RD )Pdiag (T −α + BD + RD ) ≤ T −α + BD + RD

2

∥Pdiag ∥

= OP (δn−2α ρn ) = OP (δn1/2−2α log n), p

where we have used the fact that ρn ≤ 1 and

√

1/2

log n = o(δn ).

The proof of Equation (5n) is the same as that of Equation (5m), with the matrix infinity norm in place of the operator norm. In particular, for H = P + EA = A + Pdiag , ∥H∥∞ = max(di + pii ) = OP (δn ), i

so the infinity-norm version of Lemma 2 applies to the first six terms of RE with V = In . Remark 3. For the remainder of the appendix, whenever we establish concentration or remainder bounds, we condition on the latent positions and work on the event on which the population bounds in Lemma 1 hold. The conditional estimates below are uniform over this event, and since the probability of this event goes to 1, they imply the corresponding unconditional OP bounds. We suppress this conditioning from the notation. A.2.2

Taylor Remainder Bound

Lemma 2. Let (D−α HD−α − T −α HT −α )V = BD HT −α V + T −α HBD V + RH,V , where H is any symmetric random matrix satisfying maxi

j |hij | = OP (δn ), V

P

is any random

matrix satisfying ∥V ∥2→∞ = OP (vn ), and RH,V = RD HT −α V + T −α HRD V + BD HBD V + BD HRD V + RD HBD V + RD HRD V. The first two terms satisfy BD HT −α V

2→∞ +

T −α HBD V

26

2→∞ = OP





δn1/2−2α log n vn , p

and the remaining terms satisfy 



∥RH,V ∥2→∞ = OP δn−2α log n vn . The same bounds hold if every occurrence of the 2 → ∞ norm, including the assumption on V , is replaced by the operator norm or the matrix infinity norm. Proof. We begin with the two terms ∥BD HT −α V ∥2→∞ + ∥T −α HBD V ∥2→∞ . Write ML , MR ∈ {T −α , BD , RD }. For each row i, ∥(ML HMR V )i∗ ∥ ≤ |(ML )ii |

n X

|hij ||(MR )jj | ∥Vj∗ ∥

j=1



≤ ∥ML ∥ max i

n X



|hij | ∥MR ∥ ∥V ∥2→∞ .

j=1

By assumption, max i

n X

|hij | = OP (δn )

∥V ∥2→∞ = OP (vn ).

and

j=1

By Equations (5k) and (5a), if one of ML , MR is BD and the other is T −α , then 

p



p

∥ML HMR V ∥2→∞ = OP δn−α−1/2 log n · δn · δn−α · vn





= OP δn1/2−2α log nvn . This proves the statement on the first two terms. The remaining terms contain RD or at least two factors from {BD , RD }. In each case, ∥ML ∥ ∥MR ∥ = OP (δn−2α−1 log n). Thus, 

∥ML HMR V ∥2→∞ = OP δn−2α−1 log n · δn · vn 





= OP δn−2α log nvn . This proves the statement for the remaining terms. Since H is symmetric, ∥H∥ ≤ max i

X

|hij | = OP (δn ),

j

so the same argument, together with submultiplicativity, applies with every occurrence of the 2 → ∞ norm replaced by the appropriate norm.

27

A.3

Derivation of the Spectral Expansion and Proof of Negligibility

Lemma 3. The following identity holds: ⊤ 1/2 ⊤ −1/2 ⊤ Ûα Λ̂1/2 Vα + Rsp,α Vα⊤ , α Wn Vα − Uα Λα Vα = Eα Uα Λα

where 

1/2 ⊤ −1/2 Rsp,α = Uα Wn⊤ Λ̂1/2 + (Uα⊤ Ûα Wn − Ir )Wn⊤ Λ̂1/2 α Wn − Λα − Uα Eα Uα Λα α Wn







+ Π⊥ (Uα )Eα Ûα Λ̂−1/2 Wn − Uα Λ−1/2 . α α Proof. Using Π⊥ (Uα ) = In − Uα Uα⊤ , 







1/2 ⊤ 1/2 1/2 1/2 Ûα Λ̂1/2 + Π⊥ (Uα ) Ûα Λ̂1/2 . α Wn − Uα Λα = Uα Uα Ûα Λ̂α Wn − Uα Λα α Wn − U α Λ α −1/2

1/2

Note that Π⊥ (Uα )Uα = 0. Since L̂α Ûα = Ûα Λ̂α , we have Ûα Λ̂α Wn = L̂α Ûα Λ̂α

Wn .

Thus, 















1/2 1/2 1/2 ⊤ + Π⊥ (Uα )Ûα Λ̂1/2 Ûα Λ̂1/2 α Wn α Wn − Uα Λα = Uα Uα Ûα Λ̂α Wn − Uα Λα 1/2 + Π⊥ (Uα )L̂α Ûα Λ̂−1/2 Wn = Uα Uα⊤ Ûα Λ̂1/2 α Wn − U α Λ α α 1/2 + Π⊥ (Uα )(Lα + Eα )Ûα Λ̂−1/2 Wn = Uα Uα⊤ Ûα Λ̂1/2 α Wn − U α Λ α α 1/2 + Π⊥ (Uα )Eα Ûα Λ̂−1/2 Wn , = Uα Uα⊤ Ûα Λ̂1/2 α Wn − U α Λ α α

where in the last step we have used the fact that Π⊥ (Uα )Lα = Π⊥ (Uα )Uα Λα Uα⊤ = 0. For the first term, 





1/2 1/2 Uα Uα⊤ Ûα Λ̂1/2 = Uα Uα⊤ Ûα Λ̂1/2 α Wn − U α Λ α α Wn − Λ α





1/2 = Uα Uα⊤ Ûα Wn Wn⊤ Λ̂1/2 α Wn − Λ α







1/2 ⊤ ⊤ 1/2 = Uα Wn⊤ Λ̂1/2 α Wn − Λα + (Uα Ûα Wn − Ir )Wn Λ̂α Wn . (7) −1/2

For the second term, adding and subtracting Uα Λα

, we get

Π⊥ (Uα )Eα Ûα Λ̂−1/2 Wn α 

= Π⊥ (Uα )Eα Uα Λ−1/2 + Π⊥ (Uα )Eα Ûα Λ̂−1/2 Wn − Uα Λ−1/2 α α α 

 

= Eα Uα Λ−1/2 − Uα Uα⊤ Eα Uα Λ−1/2 + Π⊥ (Uα )Eα Ûα Λ̂−1/2 Wn − Uα Λ−1/2 . (8) α α α α Combining Equations (7) and (8) gives 

1/2 −1/2 Ûα Λ̂1/2 − Uα Uα⊤ Eα Uα Λ−1/2 + Π⊥ (Uα )Eα Ûα Λ̂−1/2 Wn − Uα Λ−1/2 α Wn − Uα Λα = Eα Uα Λα α α α





1/2 ⊤ ⊤ 1/2 + Uα Wn⊤ Λ̂1/2 α Wn − Λα + (Uα Ûα Wn − Ir )Wn Λ̂α Wn ,

28



and factoring the second term finally gives 1/2 −1/2 Ûα Λ̂1/2 α Wn − Uα Λα = Eα Uα Λα



1/2 ⊤ −1/2 + (Uα⊤ Ûα Wn − Ir )Wn⊤ Λ̂1/2 + Uα Wn⊤ Λ̂1/2 α Wn − Λα − Uα Eα Uα Λα α Wn







+ Π⊥ (Uα )Eα Ûα Λ̂−1/2 Wn − Uα Λ−1/2 . α α Multiplication on the right by Vα⊤ completes the proof. Lemma 4. Under Condition 1, 







−2α ∥Eα Uα ∥2→∞ = OP n−1/2 δn1/2−2α log n = OP ρ1/2 log n . n δn

p

p

Proof. We first write Eα Uα = T −α EA T −α Uα + BD P T −α Uα + T −α P BD Uα + BD EA T −α Uα + T −α EA BD Uα + RE Uα , where RE = RD (P + EA )T −α + T −α (P + EA )RD + BD (P + EA )BD + BD (P + EA )RD + RD (P + EA )BD + RD (P + EA )RD − (T −α + BD + RD )Pdiag (T −α + BD + RD ). For the first term, conditional on the latent positions, the ith row is a weighted sum of independent mean-zero vectors, −α e⊤ EA T −α Uα = t−α i T i

X

(EA )ij t−α j (Uα )j∗ .

j

The weights satisfy −α −1/2 −2α max t−α δn i tj (Uα )j∗ ≤ Cn i,j

and max t−2α i i

X

∥(Uα )j∗ ∥2 ≤ Cn−1 δn1−4α . pij t−2α j

j

Applying Bernstein’s inequality (see, e.g., Vershynin (2018, Theorem 2.8.4)) coordinatewise and taking a union bound over i and the fixed number of coordinates gives 

p



p

T −α EA T −α Uα 2→∞ = OP n−1/2 δn1/2−2α log n + n−1/2 δn−2α log n





= OP n−1/2 δn1/2−2α log n , where the second equality uses the assumption that δn = ω((log n)2 ). For the second term, since Lα Uα = Uα Λα and Lα = T −α P T −α , P T −α Uα = T α Uα Λα . Thus, we may write (P T −α Uα )i∗ ≤ Cδnα n−1/2 δn1−2α = Cn−1/2 δn1−α .

29

Using Equation (5k), 



BD P T −α Uα 2→∞ ≤ ∥BD ∥ max (P T −α Uα )i∗ = OP n−1/2 δn1/2−2α log n . p

i

Similarly, for the third term, (T −α P BD Uα )i∗ ≤ Cδn−α

X

pij ∥BD ∥ ∥(Uα )j∗ ∥

j





≤ Cδn−α · δn · δn−α−1/2 log n · n−1/2 = OP n−1/2 δn1/2−2α log n . p

p

For the fourth and fifth terms, using Equation (5j) gives 



BD EA T −α Uα 2→∞ + T −α EA BD Uα 2→∞ ≤ 2 ∥BD ∥ max

X

i

= OP



|(EA )ij | T −α ∥Uα ∥2→∞

j

n−1/2 δn1/2−2α

p



log n .

For the final term involving RE , let H = P + EA = A + Pdiag , and note that the first six terms are then RH,Uα from Lemma 2. By Equations (5g) and (5b), we have max i

X

|hij | = max(di + pii ) = OP (δn ).

j

i

Lemma 2 and Equation (5e) then give 







∥RH,Uα ∥2→∞ = OP n−1/2 δn−2α log n = oP n−1/2 δn1/2−2α log n . p

Finally, since T −α + BD + RD = D−α , Equations (5g), (5b), and (5e) give D−α Pdiag D−α Uα 2→∞ ≤ D−α

2

∥Pdiag ∥ ∥Uα ∥2→∞







p

= OP n−1/2 ρn δn−2α



= oP n−1/2 δn1/2−2α log n . Combining the preceding bounds proves the result. Lemma 5. Under Condition 1, 



Uα⊤ Eα Uα = OP δn−2α log n . Proof. We first write Uα⊤ Eα Uα = Uα⊤ T −α EA T −α Uα + Uα⊤ BD P T −α Uα + Uα⊤ T −α P BD Uα + Uα⊤ BD EA T −α Uα + Uα⊤ T −α EA BD Uα + Uα⊤ RE Uα ,

30

where RE = RD (P + EA )T −α + T −α (P + EA )RD + BD (P + EA )BD + BD (P + EA )RD + RD (P + EA )BD + RD (P + EA )RD − (T −α + BD + RD )Pdiag (T −α + BD + RD ). For the first term, for k, ℓ ∈ {1, . . . , r}, 

Uα⊤ T −α EA T −α Uα

 kℓ

=

X

−α (EA )ab t−α a tb ((Uα )ak (Uα )bℓ + (Uα )bk (Uα )aℓ ) .

a<b

Conditional on the latent positions, this is a weighted sum of independent mean-zero random variables. By Equations (5a) and (5e), the weights satisfy −α −1 −2α t−α . a tb ((Uα )ak (Uα )bℓ + (Uα )bk (Uα )aℓ ) ≤ Cn δn

Consequently, Var



Uα⊤ T −α EA T −α Uα

  kℓ

≤

X

t−2α pab t−2α |((Uα )ak (Uα )bℓ + (Uα )bk (Uα )aℓ )|2 a b

a<b

≤ Cδn−4α n−2

X

pab

a<b

≤ Cn−1 δn1−4α . By Chebyshev’s inequality, for every M > 0, 

P

Uα⊤ T −α EA T −α Uα





kℓ

−2α > M ρ1/2 ≤ n δn

Cn−1 δn1−4α C −4α = M 2 . 2 M ρn δn

Hence, 

Uα⊤ T −α EA T −α Uα

 kℓ

−2α = OP (ρ1/2 ). n δn

(9)

Because r is fixed, Uα⊤ T −α EA T −α Uα ≤ r · max k,ℓ



Uα⊤ T −α EA T −α Uα

 kℓ

.

Combining this with Equation (9) and noting that ρn ≤ 1, we have 



Uα⊤ T −α EA T −α Uα = OP δn−2α .

31

(10)

For the second term, we write Uα⊤ BD P T −α Uα = Uα⊤ BD T α Uα Λα , and (Uα⊤ BD T α Uα )kℓ = α

X

(Uα )ak (Uα )aℓ

a

= −α

X

ta − da ta

(Uα )ak (Uα )aℓ t−1 a

a

= −α

X

X

(EA )ab

b̸=a





−1 (EA )ab t−1 a (Uα )ak (Uα )aℓ + tb (Uα )bk (Uα )bℓ .

a<b

Conditional on the latent positions, this is again a weighted sum of independent mean-zero random variables. By Equations (5a) and (5e), the weights satisfy −1 −1 −1 t−1 a (Uα )ak (Uα )aℓ + tb (Uα )bk (Uα )bℓ ≤ Cn δn

and X

pab



−1 t−1 a (Uα )ak (Uα )aℓ + tb (Uα )bk (Uα )bℓ

2

≤ Cδn−2 n−2

a<b

X

pab

a<b

≤ Cn−1 δn−1 . An analogous argument to that used to obtain Equation (10) gives 



Uα⊤ BD T α Uα = OP δn−1 . After multiplication by Λα , Equation (5d) gives 



Uα⊤ BD P T −α Uα = OP δn−2α . The third term, Uα⊤ T −α P BD Uα , is the transpose of the second and thus shares the same bound. The fourth and fifth terms are bounded by Uα⊤ BD EA T −α Uα + Uα⊤ T −α EA BD Uα ≤ 2 ∥BD ∥ ∥EA ∥ T −α = OP (δn−2α log n). For the final term involving RE , let H = P + EA = A + Pdiag , and note that the first six terms are then RH,In from Lemma 2. Then ∥RH,In ∥ = OP (δn−2α log n). Moreover, D−α Pdiag D−α = OP (δn−2α ρn ) and ∥RE ∥ = OP (δn−2α log n). Thus, Uα⊤ Eα Uα = OP (δn−2α log n).

32

Lemma 6. Under Condition 1, for any fixed q ∈ R, 



Uα⊤ Ûα Λ̂qα − Λqα Uα⊤ Ûα = OP δnq(1−2α)−1 log n . Consequently, the following three bounds hold: 

Wn⊤ Λ̂qα Wn − Λqα = OP δnq(1−2α)−1 log n 





−α−1/2 Uα⊤ Ûα Wn − Ir Wn⊤ Λ̂1/2 log n α Wn = OP δn

Ûα Λ̂−1/2 Wn − Uα Λ−1/2 α α





p α−1

F

= OP (δn

log n).

(11) (12) (13)

Proof. Let {ϕ1 , ϕ2 , . . . , ϕr } be the principal angles between the two subspaces spanned by the columns of Uα and Ûα . Then the singular values of Π⊥ (Uα )Ûα = (In − Uα Uα⊤ )Ûα are given by {sin(ϕ1 ), . . . , sin(ϕr )}. Thus, by Davis–Kahan (see, for example, Yu et al. (2015)), 

(In − Uα Uα⊤ )Ûα = OP

∥Eα ∥ min |Λα |



= OP (δn−1/2 log n). p

We now write (Lα + Eα )Ûα = Ûα Λ̂α Uα⊤ Ûα Λ̂α − Λα Uα⊤ Ûα = Uα⊤ Eα Ûα 

Uα⊤ Ûα Λ̂α − Λα Uα⊤ Ûα = Uα⊤ Eα Uα Uα⊤ Ûα + Π⊥ (Uα )Ûα



Uα⊤ Ûα Λ̂α − Λα Uα⊤ Ûα = Uα⊤ Eα Uα Uα⊤ Ûα + Uα⊤ Eα Π⊥ (Uα )Ûα . Thus, by Lemma 5 and Equations (5m) and (14), Uα⊤ Ûα Λ̂α − Λα Uα⊤ Ûα ≤ Uα⊤ Eα Uα

Uα⊤ Ûα + ∥Eα ∥ Π⊥ (Uα )Ûα

= OP (δn−2α log n). We now show this for a general fixed q. We may explicitly calculate 



Uα⊤ Ûα Λ̂qα − Λqα Uα⊤ Ûα = Hq ◦ Uα⊤ Ûα Λ̂α − Λα Uα⊤ Ûα , where ◦ denotes the entrywise product and

(Hq )ij =

 q q  λ̂ − λi,α    j,α ,

λ̂j,α ̸= λi,α ,

   qλq−1 ,

λ̂j,α = λi,α .

λ̂j,α − λi,α i,α

Now Weyl’s inequality gives max λk (Λ̂α ) − λk (Λα ) ≤ ∥Eα ∥ .

1≤k≤r

33

(14)

By Equations (5m) and (5d), it follows that, with high probability, λmin (Λ̂α ) ≍ λmax (Λ̂α ) ≍ δn1−2α . Thus, for each fixed q, there exists a constant Cq > 0 such that max |(Hq )ij | ≤ Cq δn(q−1)(1−2α) . i,j

Since r is fixed, this implies 



Uα⊤ Ûα Λ̂qα − Λqα Uα⊤ Ûα = OP δnq(1−2α)−1 log n ,

(15)

which proves the first bound. We now show that Uα⊤ Ûα Wn − Ir = OP (δn−1 log n). This follows by definition, because Wn is the matrix that solves the orthogonal Procrustes problem between Ûα and Uα . It is easy to see that Uα⊤ Ûα Wn − Ir = maxi |cos(ϕi ) − 1|. Since 1 − cos(x) ≤ sin2 (x), by Equation (14), we have Uα⊤ Ûα Wn − Ir = OP (δn−1 log n).

(16)

We now show Equation (11). Since Wn is orthogonal, we may multiply the bound in Equation (15) by Wn on the right to get 



Uα⊤ Ûα Wn Wn⊤ Λ̂qα Wn − Λqα Uα⊤ Ûα Wn = OP δnq(1−2α)−1 log n .

(17)

We then have h





i

h

Wn⊤ Λ̂qα Wn − Λqα = Uα⊤ Ûα Wn Wn⊤ Λ̂qα Wn − Λqα Uα⊤ Ûα Wn + Ir − Uα⊤ Ûα Wn h

i

Wn⊤ Λ̂qα Wn



i

+ Λqα Uα⊤ Ûα Wn − Ir . q(1−2α)−1

The second and third terms are OP (δn

log n) by Equations (16) and (5d). Combining

this with Equation (17) proves Equation (11). Taking q = 1/2, the bound on the second term is exactly Equation (12). Finally, for Equation (13), using Wn Wn⊤ = Ir , we write 



Ûα Λ̂−1/2 Wn − Uα Λ−1/2 = Ûα Wn Wn⊤ Λ̂−1/2 Wn − Uα Λ−1/2 α α α α 



= (Ûα Wn − Uα )Λ−1/2 + Ûα Wn Wn⊤ Λ̂−1/2 Wn − Λ−1/2 . α α α Thus, Ûα Λ̂−1/2 Wn − Uα Λ−1/2 α α

F

≤ Ûα Wn − Uα

F

Λ−1/2 + Ûα Wn α

Wn⊤ Λ̂−1/2 Wn − Λ−1/2 α α

F

.

√ By Equations (14) and (5d), the first term is OP (δnα−1 log n). By Equation (11), the second √ term is OP (δnα−1 log n). Thus, Wn − Uα Λ−1/2 Ûα Λ̂−1/2 α α 34

= OP (δnα−1 log n), p

F

which completes the proof. Lemma 7. Under Condition 1, 



∥Rsp,α ∥F = OP δn−α−1/2 log n . Proof. We recall that 

1/2 ⊤ −1/2 Rsp,α = Uα Wn⊤ Λ̂1/2 + (Uα⊤ Ûα Wn − Ir )Wn⊤ Λ̂1/2 α Wn − Λα − Uα Eα Uα Λα α Wn







+ Π⊥ (Uα )Eα Ûα Λ̂−1/2 Wn − Uα Λ−1/2 . α α −α−1/2

The first term is OP (δn

log n) by Lemma 6 (with q = 1/2), Lemma 5 and Equation (5d), −α−1/2

and Equation (12) of Lemma 6. The second term is OP (δn

log n) by Equation (5m) and

Equation (13) of Lemma 6. Combining these two bounds completes the proof. Proposition 1. Under Condition 1, for each fixed row index i, n1/2 δnα (Rsp,α )i∗ = oP (1). Consequently, for every ε > 0,  p



P n1/2 δnα (Rsp,α )i∗ > ε | ξi → 0. Proof. By Lemma 7, 



δn2α ∥Rsp,α ∥2F = OP δn−1 (log n)2 = oP (1), where the last equality uses Condition 1b. Because the latent positions are iid and the graph model is invariant under a relabeling of the vertices, and because Wn is the usual alignment between Ûα and Uα , the rows of Rsp,α are exchangeable. Thus, for any ε > 0, 



n n o 1X 1 n1/2 δnα ∥(Rsp,α )j∗ ∥ > ε  . P n1/2 δnα ∥(Rsp,α )i∗ ∥ > ε = E  n j=1





For every realization of Rsp,α , n n n o 1X 1X nδn2α ∥(Rsp,α )j∗ ∥2 1 n1/2 δnα ∥(Rsp,α )j∗ ∥ > ε ≤ 1 ∧ n j=1 n j=1 ε2

=1∧

δn2α ∥Rsp,α ∥2F . ε2

The right-hand side converges to zero in probability and is bounded by 1. Therefore its expectation converges to zero. Thus, 



P n1/2 δnα ∥(Rsp,α )i∗ ∥ > ε → 0,

35

which proves the proposition. The conditional statement follows from the fact that h 

E P n1/2 δnα ∥(Rsp,α )i∗ ∥ > ε | ξi

i

→ 0.

An application of Markov’s inequality completes the proof.

A.4

Proof of Theorem 1

We begin this section with a proof that three of the terms arising from the expansion of X̂α Wn Vα⊤ − Xα are negligible. For these three lemmas, we note that since Uα Λ−1/2 Vα⊤ = T −α XG−1 α n,α and Vα is orthogonal, for any n × n matrix M and any row i, 

M Uα Λ−1/2 α

 i∗

=



M T −α XG−1 n,α

 i∗

.

Intuitively, we may drop the Vα term in the proof for clarity, with the understanding that this orthogonal matrix does not affect the row norms. Lemma 8. For each fixed row i, 

nα+1/2 ραn −1/2

Proof. Since Uα Λα

T −α P ◦ BD Uα Λ−1/2 α

 i∗

= oP (1).

Vα⊤ = T −α XG−1 n,α , we have

−2α−1 BD Uα Λ−1/2 Vα⊤ = αT −α−1 (T − D)T −α XG−1 (T − D)XG−1 α n,α = αT n,α .

We thus write 

T −α P ◦ BD Uα Λ−1/2 Vα⊤ α

 i∗

= αt−α i

X



j̸=i

Define bj := t−2α−1 Xj⊤ G−1 n,α . We begin by bounding the quantity E j 2

E

X

pij (tj − dj )bj



Xj⊤ G−1 pij (tj − dj ) t−2α−1 n,α . j

j̸=i pij (tj − dj )bj

P

2

.

  XX = E pij piℓ (tj − dj )(tℓ − dℓ )bj b⊤  ℓ

j̸=i

j̸=i ℓ̸=i

  XX = E pij piℓ Cov (tj − dj , tℓ − dℓ ) bj b⊤  ℓ

(18)

j̸=i ℓ̸=i

If j = ℓ, then the covariance term is simply Var(tj − dj ). Since tj is fixed, this simplifies to X

Var (ajk ) =

k̸=j

X

pjk (1 − pjk ) ≤

k̸=j

X k̸=j

By Equation (5a), this is O(δn ).

36

pjk = tj .

If j ̸= ℓ, then all terms are independent except for the shared edge (j, ℓ). Thus, the covariance term becomes Cov (tj − dj , tℓ − dℓ ) = Cov (pjℓ − ajℓ , pℓj − aℓj ) = Var(ajℓ ) ≤ pjℓ . Since pjℓ = Xj⊤ Xℓ = ρn ξj⊤ ξℓ and we assume the latent positions are uniformly bounded, we have Cov (tj − dj , tℓ − dℓ ) = O(ρn ). Plugging these bounds into Equation (18) gives 2

E

X

pij (tj − dj )bj

≤

X

p2ij Var(tj − dj ) ∥bj ∥2 +

j̸=i

j̸=i

≤ Cδn

pij piℓ Cov (tj − dj , tℓ − dℓ ) bj b⊤ ℓ

j̸=i ℓ̸=i,j

X

p2ij ∥bj ∥2 + C ′ ρn

j̸=i

≤ Cδn

X X

X

XX

pij piℓ ∥bj ∥ ∥bℓ ∥

j̸=i ℓ̸=i

 2 X p2 ∥bj ∥2 + C ′ ρn  pij ∥bj ∥ .

(19)

ij

j̸=i

j̸=i

We now bound maxj̸=i ∥bj ∥. By Equations (5a), (5c), and the fact that the latent positions are uniformly bounded, we have 2α−1 −2 max ∥bj ∥ ≤ Cδn−2α−1 · ρ1/2 = Cρ1/2 n · δn n δn .

(20)

j̸=i

Combining these bounds with Equations (5b) and (19) gives 2

E

X

pij (tj − dj )bj

≤ Cδn

j̸=i

X

 2 X p2ij ∥bj ∥ + C ′ ρn  pij ∥bj ∥ 2

j̸=i

j̸=i



−2 ≤ Cδn · nρ2n · ρn δn−4 + C ′ ρn · nρn · ρ1/2 n δn

2

≤ Cρ2n δn−2 Thus, X

pij (tj − dj )bj = OP (ρn δn−1 ).

j̸=i

Recalling that 

T −α P ◦ BD Uα Λ−1/2 Vα⊤ α

 i∗

= αt−α i

X





pij (tj − dj ) t−2α−1 Xj⊤ G−1 n,α , j

j̸=i

we have 

T −α P ◦ BD Uα Λ−1/2 Vα⊤ α

 i∗

= OP (δn−α · ρn δn−1 ) = OP (ρn δn−α−1 ).

37

Finally, we have nα+1/2 ραn



T −α P ◦ BD Uα Λ−1/2 α

 i∗

= OP (n−1/2 ) = oP (1),

which completes the proof. Lemma 9. For each fixed row i, nα+1/2 ραn −1/2

Proof. Since Uα Λα 



BD (A − P ◦ )T −α Uα Λ−1/2 α

 i∗

−1/2

−α U Λ Vα⊤ = T −α XG−1 α α n,α , we have T

BD EA T −α Uα Λ−1/2 Vα⊤ α

 i∗

= αt−α−1 (ti − di ) i

= oP (1).

Vα⊤ = T −2α XG−1 n,α . We thus write (EA )ij t−2α Xj⊤ G−1 n,α , j

X j̸=i

where (EA )ij satisfies E[(EA )2ij ] = pij (1 − pij ) ≤ pij . Additionally, by Equations (5a), (5c), and the fact that the latent positions are uniformly bounded, we have −2α 1/2 2α−1 −1 Xj⊤ G−1 ρn δn = Cρ1/2 t−2α n,α ≤ Cδn n δn . j

Thus, 2

E

X

(EA )ij t−2α Xj⊤ G−1 n,α j

≤

X

pij t−2α Xj⊤ G−1 n,α j

2

j̸=i

j̸=i

≤ Cρn δn−2

X

pij

j̸=i

= Cρn δn−2 ti ≤ Cρn δn−1 . Combining this with Equations (5a) and (5f) gives h

BD EA T −α Uα Λ−1/2 α

i



i∗



−α−1 = OP ρ1/2 . n δn

Finally, nα+1/2 ραn



BD EA T −α Uα Λ−1/2 α





i∗

−α−1 = OP nα+1/2 ραn · ρ1/2 n δn



= OP δnα+1/2 δn−α−1



= OP (δn−1/2 ) = oP (1), which completes the proof. Lemma 10. For each fixed row i, nα+1/2 ραn



T −α (A − P ◦ )BD Uα Λ−1/2 α

38

 i∗

= oP (1).



−1/2

Proof. Since Uα Λα

Vα⊤ = T −α XG−1 n,α , we have

−2α−1 BD Uα Λ−1/2 Vα⊤ = αT −α−1 (T − D)T −α XG−1 (T − D)XG−1 α n,α = αT n,α .

We thus write 

T −α (A − P ◦ )BD Uα Λ−1/2 Vα⊤ α

 i∗

= αt−α i

X

= αt−α i

X

(aij − pij )t−2α−1 (tj − dj )Xj⊤ G−1 n,α j

j̸=i

(EA )ij (tj − dj )bj ,

j̸=i

where (EA )ij = aij − pij and bj = t−2α−1 Xj⊤ G−1 n,α . j For fixed i and j ̸= i, define (−i)

Dj

X

=

(ajk − pjk ),

k̸=i,j

so that (−i)

tj − dj = −(EA )ij − Dj

.

X

X

Thus, X

(EA )ij (tj − dj )bj = −

j̸=i

(EA )2ij bj −

j̸=i

(−i)

(EA )ij Dj

bj .

j̸=i

We bound the two terms separately. For the first term, E[(EA )2ij ] = pij (1 − pij ) ≤ pij .

(21)

1/2

Recalling Equation (20), which states maxj̸=i ∥bj ∥ ≤ Cρn δn−2 , we have

E

X

(EA )2ij bj ≤

X

≤

X

E[(EA )2ij ] ∥bj ∥

j̸=i

j̸=i

pij ∥bj ∥

j̸=i



≤ max ∥bj ∥ j̸=i

X

pij

j̸=i

−2 1/2 −1 ≤ Cρ1/2 n δn · δn = Cρn δn .

Thus, 



−1 (EA )2ij bj = OP ρ1/2 . n δn

X

(22)

j̸=i

For the second term, we have 2

E

(−i) (EA )ij Dj bj

X j̸=i

=

X

h

(−i)

bj b⊤ ℓ E (EA )ij (EA )iℓ Dj

(−i)

Dℓ

i

.

j,ℓ̸=i (−i)

If j ̸= ℓ, then ((EA )ij , (EA )iℓ ) is independent of (Dj 39

(−i)

, Dℓ

). Since (EA )ij and (EA )iℓ are

independent and mean-zero, we have 2

E

X

(−i) (EA )ij Dj bj

=

X

h

(−i) 2

∥bj ∥2 E (EA )2ij (Dj

)

i

.

(23)

j̸=i

j̸=i

By Equation (21), E[(EA )2ij ] ≤ Cρn . Additionally, (−i) 2

X

) ]=

E[(Dj

pjk (1 − pjk ) ≤ tj ≤ Cδn .

k̸=i,j

Thus, (−i) 2

E[(EA )2ij (Dj

) ] ≤ Cρn δn .

Plugging this into Equation (23) and using Equation (20) gives 2

X

E

(−i) (EA )ij Dj bj

≤ Cnρn δn−4 · ρn δn = Cρn δn−2 .

j̸=i

Thus, X

(−i)

(EA )ij Dj





−1 bj = OP ρ1/2 . n δn

(24)

j̸=i

Combining Equations (22) and (24) gives 



−1 (EA )ij (tj − dj )bj = OP ρ1/2 . n δn

X j̸=i

Recalling that 

T −α (A − P ◦ )BD Uα Λ−1/2 Vα⊤ α



= αt−α i

i∗

X

(EA )ij (tj − dj )bj

j̸=i

and using Equation (5a), we have 

T −α (A − P ◦ )BD Uα Λ−1/2 α





i∗







−1 −α−1 = OP δn−α ρ1/2 = OP ρ1/2 . n δn n δn

Finally, nα+1/2 ραn



T −α (A − P ◦ )BD Uα Λ−1/2 α

 i∗



−α−1 = OP nα+1/2 ραn ρ1/2 n δn



= OP δnα+1/2 δn−α−1 





= OP δn−1/2 = oP (1), which completes the proof. We are now ready to prove Theorem 1. Proof. We begin by writing ⊤ 1/2 ⊤ X̂α Qn − Xα = Ûα Λ̂1/2 α Wn Vα − Uα Λα Vα .

40



Again, since Vα is orthogonal, the extra factor preserves row norms. Just as in the previous lemmas, for clarity, we omit this factor, with the understanding that we multiply by this matrix at the end to obtain the final result. By Lemma 3, 1/2 −1/2 Ûα Λ̂1/2 + Rsp,α , α Wn − Uα Λα = Eα Uα Λα

where 

1/2 ⊤ −1/2 + (Uα⊤ Ûα Wn − Ir )Wn⊤ Λ̂1/2 Rsp,α = Uα Wn⊤ Λ̂1/2 α Wn − Λα − Uα Eα Uα Λα α Wn







Wn − Uα Λ−1/2 . + Π⊥ (Uα )Eα Ûα Λ̂−1/2 α α By Proposition 1, for every ε > 0,  p



P nα+1/2 ραn (Rsp,α )i∗ > ε ξi −→ 0. Thus, nα+1/2 ραn

h

Ûα Λ̂1/2 α Wn





i∗

− Uα Λ1/2 α

 i i∗



= nα+1/2 ραn Eα Uα Λ−1/2 α

 i∗

+ rn,i ,

p

where P(∥rn,i ∥ > ε | ξi ) → 0 for every ε > 0. We expand Eα using a Taylor expansion to get Eα = D−α AD−α − T −α P T −α = D−α AD−α − T −α AT −α + T −α (A − P ◦ )T −α − T −α Pdiag T −α

= BD AT −α + T −α ABD + T −α (A − P ◦ )T −α − T −α Pdiag T −α + RTay,α , where RTay,α = BD ABD + RD AT −α + T −α ARD + RD ABD + BD ARD + RD ARD . Using A = P ◦ + (A − P ◦ ), we get Eα = T −α (A − P ◦ )T −α + BD P ◦ T −α + T −α P ◦ BD + BD (A − P ◦ )T −α + T −α (A − P ◦ )BD − T −α Pdiag T −α + RTay,α . −1/2

Finally, we multiply on the right by Uα Λα

to get

Eα Uα Λ−1/2 = T −α (A − P ◦ )T −α Uα Λ−1/2 + BD P ◦ T −α Uα Λ−1/2 + R̃α,n , α α α where R̃α,n = T −α P ◦ BD Uα Λ−1/2 + BD (A − P ◦ )T −α Uα Λ−1/2 + T −α (A − P ◦ )BD Uα Λ−1/2 α α α − T −α Pdiag T −α Uα Λ−1/2 + RTay,α Uα Λ−1/2 . α α

41

(25)

We now show that nα+1/2 ραn



R̃α,n



= oP (1) by considering each term separately. The first

i∗

three terms are handled by Lemmas 8, 9 and 10, respectively. Since A is symmetric and, by Equation (5g), max

X

i

|aij | = max di = OP (δn ), i

j

−1/2

Lemma 2 applies with H = A and V = Uα Λα

. By Equations (5e) and (5d), we have

α−1/2 ∥V ∥2→∞ = OP (n−1/2 δn ). Thus,



nα+1/2 ραn

RTay,α Uα Λ−1/2 α

 i∗

= OP (nα+1/2 ραn · δn−2α log n · n−1/2 δnα−1/2 ) = OP (δn−1/2 log n) = oP (1).

The diagonal term is easily bounded using Equations (5a), (5b), (5e) and (5d). The same −1/2

bounds, together with Equation (5k) show that the additional term BD Pdiag T −α Uα Λα

is also

negligible after scaling. Using the identity Vα⊤ = T −α XG−1 Uα Λ−1/2 α n,α , together with the preceding fixed-row remainder bounds, we obtain, for each fixed row i, 

Eα Uα Λ−1/2 Vα⊤ α

⊤ i∗

−1 = t−α i Gn,α

Xj (aij − pij )t−2α j

X j̸=i

(ti − di )Xi + oP + αt−α−1 i





n−α−1/2 ρ−α . n

Then 

nα+1/2 ραn Eα Uα Λ−1/2 Vα⊤ α 

=

ti δn

−α 

δn1−2α G−1 n,α

ti −α δn =

ti δn

i∗

 X a − p  t −2α j ij ij

√

j̸=i





⊤

−α 

−α−1

ξi

δn

X aij − pij j̸=i

δn1−2α G−1 n,α

√ δn

δn

ξj

+ oP (1)

"  X a − p tj −2α ij ij

√

j̸=i

δn

δn

ξj −

αδn2α−1 Gn,α ti δn

#

ξi

+ oP (1). p

p

Conditional on ξi , we have δtni → ⟨ξi , µ⟩ and δn2α−1 Gn,α → Υα . These convergences follow from Equation (6), the law of large numbers, and the argument used to prove Equation (5c). It only remains to justify replacing (tj /δn )−2α inside the sum. By Equation (6) and Conditions 1a and 1c, the error caused by this replacement is oP (1) uniformly in j. Conditional on the latent positions, the resulting difference is a centered sum whose conditional variance is bounded by C(ti /δn ) times the square of this error, and is therefore oP (1).

42

Slutsky’s theorem then gives nα+1/2 ραn

h

X̂α Qn

 i∗

− (Xα )i∗

i⊤

X aij − pij

1 Υ−1 = ⟨ξi , µ⟩α α j̸=i

√

ξj αΥα ξi − ⟨ξj , µ⟩2α ⟨ξi , µ⟩

δn

!

+ oP (1).

Now consider the sum X aij − pij

√

j̸=i

ξj αΥα ξi − 2α ⟨ξj , µ⟩ ⟨ξi , µ⟩

δn

!

1 X aij − pij =√ √ n j̸=i ρn

ξj αΥα ξi − 2α ⟨ξj , µ⟩ ⟨ξi , µ⟩

!

.

Conditional on ξi , the summands are independent, mean-zero random vectors. By Conditions 1a and 1c, the vector in parentheses is uniformly bounded. Thus, each summand has norm bounded √ by C/ nρn → 0, and the conditional Lindeberg condition holds. Additionally, pij = ρn ⟨ξi , ξj ⟩. Writing ξ ′ for an independent copy of a latent position from distribution F , the conditional covariance is Cov

aij − pij √ ρn

ξj αΥα ξi − 2α ⟨ξj , µ⟩ ⟨ξi , µ⟩

" ′

′

= E ⟨ξi , ξ ⟩ 1 − ρn ⟨ξi , ξ ⟩



!!

ξ′ αΥα ξi − ′ 2α ⟨ξ , µ⟩ ⟨ξi , µ⟩



ξ′ αΥα ξi − ′ 2α ⟨ξ , µ⟩ ⟨ξi , µ⟩

⊤ #

.

The conditional covariance of the sum thus converges to Γρ,α (ξi ). Consequently, an application of the Lindeberg–Feller central limit theorem gives X aij − pij

√ δn

j̸=i

αΥα ξi ξj − 2α ⟨ξj , µ⟩ ⟨ξi , µ⟩

!

d

→ N (0, Γρ,α (ξi )) .

Another application of Slutsky’s theorem gives nα+1/2 ραn

h

X̂α Qn

 i∗

− (Xα )i∗

i⊤

Υ−1 Γρ,α (ξi )Υ−1 α → N 0, α ⟨ξi , µ⟩2α d

!

,

which completes the proof.

B

Additional Calculations for Block Models

B.1

Numerical Computation

In this section, we describe how the quantity α∗ in Equation (4) is computed. We evaluate the diagnostic on a grid of 100 equally spaced values of α in [0, 1] and approximate the solution to (n)

Equation (4) by the grid point at which Eα is smallest. For each such α, the population centers (n)

mα,k and covariances Σα,k are given in closed form by Corollary 1. The projected law Qk,α also 

has a closed-form density on the circle, obtained by integrating the distribution N mα,k , n1 Σα,k



(n)

along each ray through the origin. We therefore compute Eα by locating the decision boundaries between the two projected densities weighted by their community proportions and integrating.

43

p = 0.20, q = 0.10

p = 0.30, q = 0.10

p = 0.30, q = 0.20

p = 0.40, q = 0.20

p = 0.50, q = 0.10

p = 0.50, q = 0.20

p = 0.50, q = 0.30

p = 0.60, q = 0.40

p = 0.70, q = 0.10

p = 0.70, q = 0.20

p = 0.70, q = 0.30

p = 0.70, q = 0.50

1.00 0.75 0.50 0.25 0.00

1.00

α*

0.75 0.50 0.25 0.00

1.00 0.75 0.50 0.25 0.00 50

200

400 50

200

400 50

200

400 50

200

400

n

Figure 4: Value of α∗ across n ∈ {50, 100, 200, 400} for selected block matrices with π1 = 0.7. Although the minimizer can vary at smaller n, it is stable between n = 200 and n = 400 for the parameter settings considered.

As α → 1, the covariance Σα,k can become numerically singular, so we add a small ridge εI2 with ε = 10−6 before inverting the covariance matrix. The selected α∗ is insensitive to ε across several orders of magnitude. As described in Section 5.2, we set n = 200 in these computations. To confirm that this is a sensible choice, we recompute α∗ over the sample sizes n ∈ {50, 100, 200, 400} for a coarse collection of twelve (p, q) configurations with p > q, fixing π1 = 0.7. Figure 4 plots α∗ against n for each (p, q) pair. In every configuration, the value is relatively stable between n = 200 and n = 400, justifying its choice.

B.2

Calculations for Two-Community Models

In this section, we derive two analytic results for the balanced symmetric two-community model. The first gives the explicit expression for Fα in Section 4, while the second derives the Chernoffinformation benchmark used below. Both calculations use the following common RDPG representation. The model is 1 π1 = π2 = , 2 and we write s=

p+q , 2

"

B=

h=

p q

q p

p−q , 2

44

#

,

p > q > 0,

κ=

h p−q = . s p+q

A convenient RDPG representation is " √ #

"√ #

ν1 = √

s

,

h

ν2 =

s √ , − h

so that ν1⊤ ν1 = ν2⊤ ν2 = p, B.2.1

ν1⊤ ν2 = q.

Derivation of the Variance Ratio

We work in the sparse regime ρn → 0. Our goal is to derive the closed-form expression for Fα given in Section 4. We show that, using the representation chosen in the preceding subsection, finding the normal and tangential components of the covariance matrix reduces to finding the diagonal entries of Σα (ϑ, 1). We then compute the corresponding entries. By symmetry between the two communities, it is sufficient to consider a node from community 1. Let θ̄ = E[Θ]. By symmetry, θ̄ µ = (ν1 + ν2 ) = θ̄ 2

"√ #

s

0

γ := γ1 = γ2 = ⟨νk , µ⟩ = θ̄s.

,

Define the two moments aα = E[Θ2−2α ],

bα = E[Θ3−4α ].

We then have "

#

aα s 0 Υ̃α = 2α . γ 0 h α Recall that h⊤ α νk = γk for k = 1, 2. Then

" #

" #

γα 1 hα = √ , s 0

uα =

2 σN,α (ϑ) = u⊤ α Σα (ϑ)uα

and

1 0

"

,

Πα =

0 0 0 1

#

.

Recalling that 2 σT,α (ϑ) = tr(Πα Σα (ϑ)Πα ) ,

finding Fα is equivalent to computing the ratio of the first and second diagonal entries of Σα (ϑ, 1). Here, the quantities are independent of k by symmetry of the model. We now compute these values. Let (Θ′ , Z ′ ) be an independent copy of (Θ, Z). Then in the sparse regime, Corollary 1 gives Σα (ϑ, 1) =

h i ϑ1−2α ⊤ ′ ,Z ′ ∆α,1 ∆ E . Θ α,1 γ 2α

2 2 Note that, when taking the ratio σN,α,k /σT,α,k , the scalar factor will cancel. We now only need

to compute the quantities h

i

h

i

EΘ′ ,Z ′ (∆α,1 )22 .

EΘ′ ,Z ′ (∆α,1 )21 , 45

Substituting the preceding expressions into the definition of ∆α,1 gives 

∆α,1 =

p

(Θ′ )1−2α α − aα θ̄

 1 √

(Θ′ )1−2α



1  √  s 

(Θ′ )1−2α α − aα θ̄

 1 √

(Θ′ )1−2α

Θ′ p 

aα

h

∆α,1 =

p

!

1  √  s 

Θ′ q 

−

h

−

aα

   ! , ακ  

Z ′ = 1,

(26)

Z ′ = 2.

(27)

θ̄

−

! 

   ! , ακ  

θ̄

We thus have h

EΘ′ ,Z ′ (∆α,1 )21

i



(Θ′ )1−2α α − aα θ̄



(Θ′ )1−2α α − aα θ̄

Θ′ = EΘ′  s = EΘ′ Θ′

!2 



p+q  2 

!2  

E (Θ′ )3−4α 2αE (Θ′ )2−2α α2 E[Θ′ ] = − + a2α aα θ̄ θ̄2 bα 2α α2 = 2 − + aα θ̄ θ̄ bα α(2 − α) = 2 − . aα θ̄ 







(28)

Additionally,  h

i

EΘ′ ,Z ′ (∆α,1 )22 = EΘ′ 

Θ′ 2h

 p

"

(Θ′ )1−2α aα

−

ακ θ̄

!2

+q −

(Θ′ )1−2α aα

1 (Θ′ )2−4α 2ακ (Θ′ )1−2α α2 κ − + 2 κ a2α aα θ̄ θ̄

′

= EΘ′ Θ

bα 2ακ α2 κ − + κa2α θ̄ θ̄ bα κα(2 − α) = 2 − . κaα θ̄

−

ακ θ̄

!2  

!#

=

(29)

Defining
2

a2 E[Θ2−2α ] rα = α = , θ̄bα θ̄E[Θ3−4α ] and combining Equations (28) and (29) gives Fα =

2 σN,α κ (1 − α(2 − α)rα ) = . 2 1 − κ2 α(2 − α)rα σT,α

46

B.2.2

Connection to Chernoff Information (n)

In Section 5, we compare degree-α embeddings using the projected Gaussian Bayes error Eα , which incorporates the row-normalization step commonly used in spectral clustering. This diagnostic is flexible, but it is computed numerically and relies on finite-n Gaussian approximations. In this appendix, we consider an alternative perspective based on the Chernoff information analysis of Cape et al. (2019a). In the balanced two-community SBM, this approach yields an analytic benchmark against which our numerical approximations may be compared. Throughout the calculations below, we take α ∈ [0, 1). At α = 1, the limiting covariance may be singular, so we define the corresponding quantities by continuous extension as α ↑ 1. We first recall some notation from Section 5. For each α ∈ [0, 1) and k ∈ {1, 2}, let mα,k and Σα,k denote the limiting population center and covariance matrix of a node in community k, respectively. We approximate the distribution of a scaled embedded row from community k by (n)

Gk,α = N (µk , Σα,k ) , where µk =

√

k = 1, 2,

nmα,k . For a single node, the idealized community-detection problem may then (n)

(n)

be viewed as distinguishing between G1,α and G2,α . Chernoff information provides a way to quantify the difficulty of distinguishing between these two distributions. Definition 4 (Chernoff Information). Let F1 and F2 be two absolutely continuous multivariate distributions on Rr and let f1 and f2 be their densities, respectively. Chernoff divergence is defined to be Z

Ct (F1 , F2 ) = − log

f11−t (x)f2t (x)dx Rr



.

Chernoff information is defined to be C(F1 , F2 ) = − log

!

Z



inf f11−t (x)f2t (x)dx t∈(0,1) Rr 

= sup

Z

− log

t∈(0,1)

f11−t (x)f2t (x)dx Rr

= sup Ct (F1 , F2 ). t∈(0,1)

This quantity may be explicitly computed for multivariate Gaussian distributions. Define Σ12 (t) = tΣ1 + (1 − t)Σ2 and let F1 = N (µ1 , Σ1 ) and F2 = N (µ2 , Σ2 ). Then   1 |Σ12 (t)| C(F1 , F2 ) = sup t(1 − t)(µ1 − µ2 )⊤ Σ−1 (t)(µ − µ ) + log 1 2 12 2 t∈(0,1) |Σ1 |t |Σ2 |1−t

!

.

(30)

Note that (µ1 − µ2 )⊤ Σ−1 12 (t)(µ1 − µ2 ) is the square of the Mahalanobis norm with respect to Σ12 (t). We thus rewrite Equation (30) as   1 |Σ12 (t)| sup t(1 − t) ∥µ1 − µ2 ∥2Σ−1 (t) + log C(F1 , F2 ) = 12 2 t∈(0,1) |Σ1 |t |Σ2 |1−t

47

!

.

We now apply this formula to the two Gaussian approximations associated with the degree-α embedding. Because their means depend on n, the resulting Chernoff information, denoted by ηα , also depends on n. We suppress this dependence in the notation, as this dependence will cancel in the ratio after taking a large-sample approximation. "

1 ηα = sup t(1 − t) ∥µ1 − µ2 ∥2Σ−1 (t) + log α,12 2 t∈(0,1)

|Σα,12 (t)| |Σα,1 |t |Σα,2 |1−t

!#

,

where Σα,12 (t) := tΣα,1 + (1 − t)Σα,2 . From Theorem 1, the means of the Gaussian distributions are given by the rows of nα+1/2 ραn Xα . If ti ≍ nρn , then ⊤ nα+1/2 ραn (Xα )i∗ = nα+1/2 ραn t−α i Xi ≍

√

nρn .

Thus, in the dense SBM considered below, the quantity µ1 − µ2 is of order

√

n. On the other

hand, the covariance matrices are independent of n. Therefore, for large n, the second term in the previous equation is dominated by the first. We then have a large-sample approximation of the Chernoff information as 1 ηα∗ ≈



sup 2 t∈(0,1)

t(1 − t) ∥µ1 − µ2 ∥2Σ−1 (t) α,12



.

(31)

Equation (31) implies that the leading approximation to the Chernoff information increases as n increases. Consider the degree-α and degree-α′ embeddings. To compare the relative efficiency between the two choices, we may define ∗ ηα,α ′ =

ηα∗ . ηα∗ ′

This quantity describes the relative approximate Chernoff information between α and α′ . A large value suggests that α may provide more separation of the two communities, and thus may ∗ be a more appropriate choice for spectral clustering. We now study the behavior of ηα,α ′ under

the explicit two-community SBM considered in this section. The asymptotic means and covariances from Theorem 1 simplify in this setting, allowing an ∗ explicit form for ηα,α ′ to be computed. Carrying out the calculation (see Section B.2.3) gives

∗ ηα,α ′ =

C2 α′2 + C1 α′ + C0 , C2 α 2 + C 1 α + C 0

where C2 = (p − q)2 (p2 − p + q 2 − q), C1 = −2(p − q)2 (p + q)(p + q − 1), C0 = (p + q)2 (p2 − p + q 2 − q).

48

(32)

1.00

q

0.75

0.50

0.25

0.00 0.00

0.25

0.50

0.75

1.00

p

0.00 0.25 0.50 0.75 1.00

Figure 5: Chernoff-optimal αCh for the balanced symmetric two-community SBM. The dark region denotes αCh = 0, corresponding to adjacency spectral clustering being preferred. Lighter colors represent higher αCh , with stronger normalization being preferred when block probabilities are smaller.

Note that when α = α′ , the ratio simplifies to 1, as expected. When α = 0 (corresponding to the adjacency matrix) and α′ = 1/2 (corresponding to the symmetric Laplacian), the ratio simplifies to equation (14) of Cape et al. (2019a). If we fix α′ = 0, we may determine when the ratio is largest, indicating the α at which the relative Chernoff information is maximized. For C1 a fixed p and q, the ratio is clearly maximized at − 2C . Thus, for each p and q, the optimal α 2

may be computed to be αCh =

  C1  0 if − 2C <0   2 

1 if − C1 > 1

2C2     − C1 otherwise 2C2

(33)

Figure 5 shows αCh over the region 0 < q < p < 1. At each point, the optimal α is computed using Equation (33). The most striking feature of the graph is the phase transition, corresponding to the case when C1 = 0. This occurs when either p = q, which corresponds to the degenerate model, or when p + q = 1, which is visible as the diagonal line in the figure. Above this boundary, adjacency spectral clustering provides higher Chernoff information for clustering, and below this boundary, some amount of degree normalization is preferred. In general, as the block probabilities decrease, increasing α provides higher Chernoff information.

49

B.2.3

Derivation of the Relative Chernoff Information

We now derive Equation (32) for the balanced symmetric two-community SBM. We recall that in this section, we work in the dense regime ρn ≡ 1 and take Θ ≡ 1. Hence θ̄ = 1, γ1 = γ2 = s, and " −2α

Υ̃α = s

s 0

#

0 h

.

Define vp = p(1 − p),

vq = q(1 − q),

and, for k ∈ {1, 2}, write (n)

mα,k :=

√

n mα,k =

√ −α n s νk ,

Σα,k := Σα (1, k).

Using Equations (26) and (27) in the specific SBM setting gives  1−α 

√  ∆α,1 = p  

√

s  , 1 − ακ  √ h

 1−α  √ √  s  ,  ∆α,1 = q  1 + ακ 

− √

Z ′ = 1,

(34)

Z ′ = 2.

(35)

h

Since P(Z ′ = 1) = P(Z ′ = 2) = 1/2, the dense-regime covariance formula in Corollary 1 gives Σα,1 =

h i 1 ⊤ ′ (1 − B1Z ′ ) ∆α,1 ∆ E . Z α,1 s2α

Expanding this expectation, we obtain "

Σα,1 =

Aα Bα

B α Cα

#

,

where, writing γ− (α) = s − αh,

γ+ (α) = s + αh, we have Aα = Bα =

(1 − α)2 (vp + vq ) , 2s2α+1

(1 − α) (vp γ− (α) − vq γ+ (α)) √ , 2 h s2α+3/2

and Cα =

2 (α) + v γ 2 (α) vp γ− q + . 2α+2 2h s

50

By symmetry, the covariance for a node in community 2 is "

Σα,2 =

Aα

−Bα

−Bα

Cα

#

.

∗ . To do so, we first compute the expression from Equation (31), We may now compute ηα,α ′

which we restate below: "

ηα∗ ≈

sup t∈(0,1)

#

t(1 − t) (n) (n) 2 , mα,1 − mα,2 −1 Σα,12 (t) 2

where Σα,12 (t) = tΣα,1 + (1 − t)Σα,2 . Equivalently, ηα∗ ≈



sup t∈(0,1)

   t(1 − t)  (n) (n) (n) (n) ⊤ mα,1 − mα,2 (tΣα,1 + (1 − t)Σα,2 )−1 mα,1 − mα,2 . 2 

We compute this quantity in two steps. First, we show that the supremum is achieved at t = 1/2. Second, we use this fact to derive an explicit expression for ηα∗ . We begin with the first claim. Define 

 (n) ⊤

(n)

f (t) = t(1 − t) mα,1 − mα,2



(n)

(n)



(tΣα,1 + (1 − t)Σα,2 )−1 mα,1 − mα,2 .

(36)

Since "

tΣα,1 + (1 − t)Σα,2 =

Aα

(2t − 1)Bα

(2t − 1)Bα

Cα

#

,

we have "

−1

(tΣα,1 + (1 − t)Σα,2 )

#

Cα −(2t − 1)Bα 1 = . Aα Cα − (2t − 1)2 Bα2 −(2t − 1)Bα Aα

(37)

Additionally, √

(n) (n) mα,1 − mα,2 = 2

" # −α

nh s

0

.

1

Plugging Equations (37) and (38) into Equation (36) gives f (t) =

4nh s−2α t(1 − t)Aα . Aα Cα − (2t − 1)2 Bα2

Elementary calculus gives f ′ (t) = −

4nhs−2α Aα (2t − 1)(Aα Cα − Bα2 ) . (Aα Cα − (2t − 1)2 Bα2 )2

Note that Aα Cα − Bα2 =

(1 − α)2 vp vq > 0, hs4α+1

51

α ∈ [0, 1),

(38)

and this quantity is exactly zero at α = 1. Additionally, the denominator is clearly positive, and the quantities 4nhs−2α and Aα are also positive. Thus, the sign of f ′ (t) is completely determined by the sign of −(2t − 1). The derivative is positive when t < 1/2 and negative when t > 1/2, and f (t) is uniquely maximized at t = 1/2. At t = 1/2, we have #

"

Aα 0 1 Σα,12 (1/2) = (Σα,1 + Σα,2 ) = . 2 0 Cα Thus, "

Σ−1 α,12 (1/2) =

#

A−1 α

0

0

Cα−1

.

Since √

(n) (n) mα,1 − mα,2 = 2

we have (n) 2

(n)

mα,1 − mα,2

Σ−1 α,12 (1/2)

We thus have ∗ ηα,α ′ =

=

" # −α

nh s

0 1

,

8nh2 s2 . vp γ− (α)2 + vq γ+ (α)2

vp γ− (α′ )2 + vq γ+ (α′ )2 . vp γ− (α)2 + vq γ+ (α)2

Plugging in the values for vp , vq , γ+ , and γ− gives ∗ ηα,α ′ =

C2 α′2 + C1 α′ + C0 , C2 α 2 + C 1 α + C 0

where C2 = (p − q)2 (p2 − p + q 2 − q), C1 = −2(p − q)2 (p + q)(p + q − 1), and C0 = (p + q)2 (p2 − p + q 2 − q). This establishes Equation (32).

52

Related documents

• Bernoulli flow for Erdős-Rényi graphs#1109557
• Spectral Universality for Matrices with Non-Linear Correlated Entries#1144960
• Limit theorems for spectra of random matrices with martingale structure#492600
• PHL: Persistent Hyperdigraph Learning for Protein-Protein Binding Affinity Prediction#1117834
• Learning Commute-Time-Preserving World Models for Planning#1156645