PaperlayerView exact revision on arXiv

Source-linked AI summary

Limit theorems for eigenvectors of the normalized Laplacian for random graphs

Minh Tang, Carey E. Priebe

arXiv:1607.08601v1stat.ML

TL;DR

The paper studies how adjacency versus normalized-Laplacian spectral embeddings affect graph inference. It derives eigenvector limits and compares the embeddings through Chernoff information; the analysis provides an optimal-error comparison for block recovery and identifies a single-graph scope boundary.

  • Problem

    The effect of choosing an embedding matrix on subsequent inference is rarely addressed, and existing within-block variance comparisons are tied to K-means.

    Source: §1 · p. 2

  • Method

    The paper establishes eigenvector distributional limits and uses Chernoff information between multivariate-normal approximations to compare embedding methods.

    Source: §1 · pp. 2–3, §3 · pp. 7–9

  • Results

    For clustering based only on a spectral embedding, Chernoff information characterizes the large-sample optimal error rate, enabling theoretical comparison of adjacency and normalized-Laplacian embeddings.

    Source: §5 · pp. 22–23

  • Takeaways & Limitations

    The comparison refines and extends prior work by providing an error-rate measure not tied to a specific clustering procedure.

    Source: §1 · p. 2, §5 · p. 23

    The Chernoff-information measure addresses the effect of embedding on inference for a single graph; an analogous measure for two-sample graph inference remains an open direction.

    Source: §5 · p. 24

Abstract

from arXiv · show

We prove a central limit theorem for the components of the eigenvectors corresponding to the $d$ largest eigenvalues of the normalized Laplacian matrix of a finite dimensional random dot product graph. As a corollary, we show that for stochastic blockmodel graphs, the rows of the spectral embedding of the normalized Laplacian converge to multivariate normals and furthermore the mean and the covariance matrix of each row are functions of the associated vertex's block membership. Together with prior results for the eigenvectors of the adjacency matrix, we then compare, via the Chernoff information between multivariate normal distributions, how the choice of embedding method impacts subsequent inference. We demonstrate that neither embedding method dominates with respect to the inference task of recovering the latent block assignments.

1 Introduction

The paper addresses the rarely studied effect of embedding-matrix choice on downstream graph inference. It develops distributional limits and compares embeddings using statistical information, finding that neither method dominates for block-assignment recovery.

1 Introduction

  • The effect of choosing an embedding matrix on subsequent inference is rarely addressed, despite spectral embeddings being used before clustering and other graph-inference tasks.Examples include normalized cuts followed by K-means and kernel-based graph comparisons.Source: §1 · p. 2
  • Prior work found that Laplacian embedding can reduce within-block variance while preserving between-block variance in a large two-block parameter regime, but its metric is tied to K-means.The reduction was occasionally by a factor of four; the metric does not establish which embedding is better for other clustering procedures.Source: §1 · p. 2
  • The paper seeks a clustering-independent metric for minimum block-recovery error, using eigenvector distributional limits and statistical information to compare the embeddings.Smaller statistical information implies less information for discriminating between stochastic-blockmodel blocks.Source: §1 · p. 2
  • The comparison uses Chernoff information between limiting multivariate normals, which characterizes the Bayes decision rule’s error rate in hypothesis testing.The paper builds on adjacency-eigenvector limits and develops analogous results for the normalized Laplacian.Source: §1 · pp. 2–3
  • The paper concludes that neither adjacency nor normalized-Laplacian embedding dominates for recovering block assignments.Its analysis characterizes the large-sample optimal error rate for procedures that cluster the spectral embedding.Source: §1 · p. 3

2 Background and Setting

The paper sets up random dot product graphs and their adjacency and normalized-Laplacian embeddings, then recalls adjacency-embedding limits as a basis for its Laplacian results.

2 Background and Setting

  • A random dot product graph samples latent positions independently, with edge probabilities determined by their inner products; stochastic blockmodels with positive-semidefinite block probability matrices are a special case.The paper assumes non-degenerate latent positions, meaning E[XX⊤] has full rank.Source: §2 · pp. 3–4
  • Adjacency and Laplacian spectral embeddings use the top d eigenvectors, scaled by the square roots of their corresponding eigenvalues.The adjacency embedding estimates a sparsity-scaled latent position, whereas the Laplacian embedding estimates a degree-normalized quantity that does not depend on the sparsity factor.Source: §2 · pp. 4–5
  • The embeddings estimate distinct but one-to-one-related latent-position parametrizations, motivating comparison through f-divergences that are invariant under invertible transformations.The Laplacian limit results assume either ρn=1 or ρn→0 with nρn=ω(log^4 n).Source: §2 · p. 5

2.1 Limit results for the adjacency spectral embedding

  • For adjacency spectral embedding, the paper recalls prior eigenvector limits and assumes the latent dimension d is fixed and known.The cited prior theorem is generalized beyond a distinct-eigenvalues assumption for E[XX⊤].Source: §2.1 · pp. 5–6
  • Conditioned on a vertex’s block, its scaled adjacency-embedding error converges to a multivariate normal; unconditionally, the limit is a mixture of multivariate normals.The stated results cover ρn≡1 and a sparse regime with ρn→0 and nρn=ω(log^4 n).Source: §2.1 · p. 7

3 Limit results for Laplacian spectral embedding

The section establishes limit results for the normalized-Laplacian spectral embedding, including asymptotic normality of its rows. It gives block-specific limits and sketches how the proof reduces the eigenvector error to sums of independent edge fluctuations.

3 Limit results for Laplacian spectral embedding

  • For the normalized-Laplacian embedding, aligned row errors have asymptotic normal limits in dense and sufficiently sparse regimes.The sparse condition is ρ_n → 0 with nρ_n = ω(log^4 n).Source: §3 · pp. 8–9
  • For stochastic blockmodels, conditioning on a vertex’s block gives a multivariate-normal limit with block-specific covariance.The block corollary treats both ρ_n ≡ 1 and the stated sparse regime.Source: §3 · p. 9
  • Block-size randomness is not incorporated when replacing observed counts n_k with expected counts nπ_k; an additional random term would be needed.The authors surmise that the displayed limits could be adapted to account for this randomness, but do not do so.Source: §3 · p. 10

3.1 Proofs sketch for Theorem 3.1 and Theorem 3.2

  • The proof sketch rewrites the embedding error using edge fluctuations, then applies concentration and the multivariate central limit theorem.The expansion also uses a Taylor approximation of D^-1/2 around T^-1/2.Source: §3.1 · pp. 11–13

4 Subsequent Inference

The section compares adjacency and Laplacian spectral embeddings for recovering stochastic block assignments, moving from within-block variance to Chernoff information as a measure of optimal inference performance. The comparison finds that neither embedding is uniformly preferable across the settings considered.

4 Subsequent Inference

  • Gaussian mixture model clustering improves on K-means for the Laplacian embedding, while within-block variance alone cannot compare embeddings independently of the clustering procedure.The variance measures capture only covariance trace; the paper argues pairwise Chernoff information between block-conditional normals is a more appropriate surrogate for optimal error.Source: §4 · pp. 14–15, §4.1 · pp. 15, 17

4.1 Comparison of ASE and LSE via within-class covariances

  • Within-block variances summarize average distances to block centroids, but their large-sample results do not require distinct eigenvalues, unlike the cited earlier proofs.The paper extends the comparison to K-block stochastic blockmodels with positive semidefinite block-probability matrices.Source: §4.1 · pp. 15–16

4.2 Chernoff Information

  • Chernoff information between block-conditional multivariate normals is used to compare the large-sample optimal block-recovery error for ASE and LSE.The section relates larger Chernoff information to lower large-sample optimal error and uses ρA/ρL to compare the embeddings.Source: §4.2 · pp. 18–19, §4.3 · pp. 19–20

4.3 Comparison of ASE and LSE via Chernoff information

  • ASE and LSE trade places across blockmodel settings: GMM◦ASE error is 0.079 versus 0.083 for GMM◦LSE at p = 0.75, q = 0.6, while at p = 0.2, q = 0.3 the errors are 0.161 and 0.151, respectively.The reported differences are statistically significant at α = 0.001; a second pair of settings likewise favors different embeddings.Source: §4.3 · p. 22

5 Summary and Conclusions

The paper establishes normalized-Laplacian spectral-embedding limits and uses Chernoff information to characterize the large-sample minimum clustering error. It also identifies scope boundaries and extensions, including regularized Laplacians and two-sample graph inference.

5 Summary and Conclusions

  • For stochastic blockmodels, each row of the normalized-Laplacian spectral embedding converges conditionally on block assignments to a multivariate normal.Chernoff information between the embedding’s normal approximations characterizes the minimum error achievable by clustering procedures operating only on the embedding.Source: §5 · pp. 22–23
  • Figure 4 displays contours of ρA/ρL across p ∈ [0.2, 0.8] and r = q − p ∈ [−0.2, −0.01] for a 3-block stochastic blockmodel.The model is given by Eq. (4.17).Source: Figure 4 · p. 23
  • The paper compares adjacency and normalized-Laplacian embeddings through Chernoff information for single-graph inference.The measure concerns the effect of spectral embedding on subsequent inference for one graph.Source: §5 · pp. 23–24
  • Deriving analogous eigenvector limits for the τ-regularized normalized Laplacian is identified as future work.The paper notes that regularization is useful for spectral clustering in sparse graphs and that such limits could inform the choice of τ.Source: §5 · p. 23
  • The stated limit results assume fixed, known rank d; results for embedding into d′ > d are an open problem.The paper also notes that related limits could help study latent-position and graphon approximation properties.Source: §5 · pp. 23–24
  • The Chernoff-information analysis addresses single-graph inference, while a corresponding measure for two-sample graph inference remains of interest.The cited examples include network comparison and two-sample hypothesis testing.Source: §5 · p. 24

A Proof of Theorem 2.1 and Theorem 2.2

The proof sketches adapt earlier adjacency-embedding arguments to the paper’s sampling and sparsity setup, and generalize an adjacency result beyond distinct eigenvalues.

A Proof of Theorem 2.1 and Theorem 2.2

  • The proof distinguishes this paper’s independently sampled latent positions and explicit sparsity factor ρn from ’s fixed, unknown latent positions with implicit sparsity.The paper notes that does not require a relationship between latent-position matrices at different graph sizes.Source: A Proof of Theorem 2.1 and Theorem 2.2 · p. 28
  • Theorem 2.2 generalizes the corresponding result in by removing the assumption that E[XX⊤] has distinct eigenvalues.The passage identifies distinct eigenvalues as necessary for the proof in.Source: A Proof of Theorem 2.1 and Theorem 2.2 · p. 29
  • The proof conditions on Xi and applies the multivariate central limit theorem to a sum of independent, identically distributed mean-zero terms.The proof also uses concentration arguments for terms involving A − P.Source: A Proof of Theorem 2.1 and Theorem 2.2 · pp. 28–30

B Proof of Theorem 3.1 and Theorem 3.2

The appendix proof derives Theorem 3.1’s limit statements and proves Theorem 3.2 using those results.

B Proof of Theorem 3.1 and Theorem 3.2

B.1 Proof of Theorem 3.2

The proof of Theorem 3.2 controls the rowwise approximation error, then applies a conditional central limit theorem and Slutsky’s theorem.

B.1 Proof of Theorem 3.2

  • Under nρn = ω(log^4(n)), the scaled rowwise residual has second moment tending to zero.The argument bounds the expected squared Frobenius norm using exchangeability of the residual rows.Source: §B.1 · p. 30
  • The proof uses exchangeability of the latent positions and embedding rows to relate a fixed row’s residual to the full residual matrix.Source: §B.1 · p. 30
  • The normalized latent-position matrix eX⊤eX converges almost surely to eΔ.The proof invokes the strong law of large numbers in establishing this convergence.Source: §B.1 · p. 31
  • Conditional on Xi = x, the proof applies the multivariate central limit theorem to the rowwise sum and uses Slutsky’s theorem for its limit.The passage states the resulting convergence in distribution for ζi.Source: §B.1 · p. 33

B.2 Proof of Eq. (3.1)

The proof establishes Eq. (3.1) using concentration bounds for the adjacency and normalized Laplacian matrices, together with subspace perturbation and technical lemmas. Its setup assumes a sufficiently large sparsity factor.

  • The proof begins with concentration inequalities for the spectral norms of A − P and L(A) − L(P) in edge-independent inhomogeneous random graphs.Source: §B.2 · p. 34
  • The derivation assumes ρ_n = ω(log^k(n)) for some integer k ≥ 4, under which the nonzero eigenvalues of L(P) are order Θ(1).Source: §B.2 · p. 34
  • Davis–Kahan bounds the principal angles between the subspaces spanned by the leading eigenvectors of L(A) and L(P).Source: §B.2 · p. 34
  • Lemmas B.3 and B.4 support the proof by enabling rearrangement of orthogonal transformations and diagonal scalings and simplifying expressions involving A, D, and L(A).Source: §B.2 · p. 35

B.3 Proof of Lemma B.3 and Lemma B.4

The proof of Lemmas B.3 and B.4 controls degree and matrix perturbation terms using concentration inequalities, then uses those bounds to establish Lemma B.3.

  • Degree fluctuations are controlled by bounding |t_i − d_i| at order O_P(√(nρ_n)) and |√t_i − √d_i| at order O_P(1).Source: §B.3 · p. 38
  • Hoeffding’s inequality and a union bound control entries of the d × d matrix formed from the normalized adjacency perturbation and the population eigenvectors.Source: §B.3 · p. 39
  • The proof uses conditional mean-zero sums and Hoeffding’s inequality to bound a degree-perturbation term involving T−3/2(T − D)X.Source: §B.3 · p. 40
  • These intermediate bounds establish Lemma B.4, from which Lemma B.3 follows directly.Source: §B.3 · p. 41

B.4 Proof of Eq. (3.4) and Eq. (3.5)

The proof derives Eqs. (3.4) and (3.5) by concentrating the terms in their expansions around their expectations and evaluating the limiting expectations.

  • The proof strategy is to show that each term in the expansion concentrates around its expectation, then evaluate those expectations as n tends to infinity.Source: §B.4 · p. 42
  • For one intermediate quantity, the conditional expectation is bounded by C(nρ_n)^−1 for a positive constant C.Source: §B.4 · p. 47
  • The paper states that Eqs. (3.4) and (3.5) then follow directly from Eqs. (B.42), (B.46), and (B.50).Source: §B.4 · p. 49

C Within-block variances

This section expresses within-block variance quantities using block-model parameters and relates the results to earlier two-block theorems. It extends both stated theorems to general K-block stochastic blockmodels when the block probability matrix is positive semidefinite.

  • The expression for the within-block variance quantity can be written using only the entries of B and π, without explicitly finding the vectors ν_1, …, ν_d.Source: C Within-block variances · p. 49
  • Theorem 4.1 extends Theorem 3.1 of to general K-block stochastic blockmodels when the block probability matrix is positive semidefinite.Source: C Within-block variances · p. 50
  • Theorem 4.2 extends Theorem 3.2 of to general K-block stochastic blockmodels when the block probability matrix is positive semidefinite.Source: C Within-block variances · p. 52

Related papers

Loading 1607.08601v1…