PaperlayerView exact revision on arXiv

Source-linked AI summary

Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges

Roberto Imbuzeiro Oliveira

arXiv:0911.0600v2math.COmath.PR

TL;DR

The paper asks whether graph properties of random graphs with independent edges concentrate around typical values, and addresses this with a new concentration inequality for random matrices. It establishes concentration for adjacency matrices and Laplacians and applies the result to bond percolation and inhomogeneous random graphs.

  • Problem

    The paper asks whether a graph parameter of a random combinatorial object is likely to be close to a typical value.

    Source: §1 · p. 1

  • Method

    The paper introduces a concentration inequality for random Hermitian matrices and applies it to adjacency matrices and Laplacians of random graphs with independent, not necessarily identically distributed, edges.

    Source: §1 · p. 2

  • Results

    For bond percolation with minimum expected degree ω(ln n), the random subgraph’s matrices are close to pA and L, while inhomogeneous random graph adjacency matrices approximate an integral operator defined by the kernel.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The matrix results give approximate transfer of estimates derived from a graph Laplacian to its percolated subgraph and relate inhomogeneous random graphs to kernel operators.

    Source: §1 · p. 3

    For inhomogeneous random graphs, the error bounds depend on κ because the Lipschitz approximation quality can vary with the kernel.

    Source: §6.2 · p. 24

Abstract

from arXiv · show

Consider any random graph model where potential edges appear independently, with possibly different probabilities, and assume that the minimum expected degree is omega(ln n). We prove that the adjacency matrix and the Laplacian of that random graph are concentrated around the corresponding matrices of the weighted graph whose edge weights are the probabilities in the random model. While this may seem surprising, we will see that this matrix concentration phenomenon is a generalization of known results about the Er\"{o}s-R\'{e}nyi model. In particular, we will argue that matrix concentration is implicit the theory of quasi-random graph properties. We present two main applications of the main result. In bond percolation over a graph G, we show that the Laplacian of the random subgraph is typically very close to the Laplacian of G. As a corollary, we improve upon a bound for the spectral gap due to Chung and Horn that was derived via much more complicated methods. In inhomogeneous random graphs, there are points X_1,...,X_n uniformly distributed on the interval [0,1] and each pair is connected with probability p kappa(X_i,X_j). We show that if \ln n/n<< p<< 1 and kappa is bounded, then the adjacency matrix of the random graph is close to an integral operator defined in terms of kappa. Our main proof tool is a new concentration inequality for matrix martingales that generalizes Freedman's inequality for the standard scalar setting.

1 Introduction

The paper studies whether graph matrices of random graphs with independent, potentially non-identically distributed edges concentrate around typical values. It introduces a matrix concentration inequality and applies it to bond percolation and inhomogeneous random graphs.

1 Introduction

  • The adjacency matrix and Laplacian are the paper’s concentration targets, extending the typical-value question to random graphs with independent edges.The edge probabilities need not be identical.Source: §1 · pp. 1–2
  • The paper connects matrix concentration to quasi-randomness: adjacency concentration reformulates dense-graph quasi-random properties, while Laplacian concentration relates to quasi-randomness for given degree sequences [24, 43, 25].Source: §1 · p. 2
  • For bond percolation, when the minimum expected degree is ω(ln n), the random subgraph’s adjacency matrix and Laplacian are close to pA and L, improving Chung and Horn’s spectral-gap bound.Estimates derived from L for the original graph then continue to hold at least approximately for the random subgraph.Source: §1 · p. 3
  • For inhomogeneous random graphs, at p = ω(ln n/n), the adjacency matrix corresponds to a discretization of an integral operator defined by the kernel, and the graph is close to the kernel in a metric stronger than cut distance.The results also relate the adjacency matrix’s eigenvalue distributions and eigenvectors to those of the operator.Source: §1 · p. 3

1.1 A new concentration inequality

  • The new concentration result is a matrix analogue of Freedman’s martingale inequality [34], and the main graph concentration theorem follows from a random-matrix inequality.The bound has worse exponent constants and an extra dimension factor d compared with scalar Freedman.Source: §1.1 · pp. 3–4

2 Preliminaries

The preliminaries fix matrix and operator notation, establish the graph and weighted-graph objects used later, and set entrywise conventions for matrix-valued probability.

2.1 Matrix notation

  • For Hermitian matrices, the spectral theorem supplies ordered eigenvalues and orthonormal eigenvectors, and the operator norm equals the largest absolute eigenvalue.Source: §2.1 · p. 6

2.2 Integral operators on L2([0, 1]) and spectral theory

  • Symmetric square-integrable kernels define compact self-adjoint operators on L2([0, 1]), whose nonzero spectral values have finite multiplicity.The section also states the compact-operator spectral decomposition and introduces the L2 space used for these operators.Source: §2.2 · p. 7

2.3 Concepts from Graph Theory

  • A graph’s adjacency matrix records edge indicators, while its Laplacian and spectral gap provide matrix-based graph quantities.Source: §2.3 · pp. 7–8
  • Weighted graphs use edge weights as adjacency-matrix entries and define degrees and Laplacians from those weights.Source: §2.3 · p. 8

2.4 Probability with matrices

  • Matrix expectations and conditional expectations are defined entrywise, with trace-expectation exchange and conditioning identities available for integrable matrices.Source: §2.4 · pp. 8–9

3 Concentration of graph matrices

Theorem 3.1 shows that random graph adjacency and Laplacian matrices concentrate around their typical weighted-graph counterparts under minimum-degree conditions. It also gives stability of eigenspace projections when the relevant eigenvalue ranges are separated.

3 Concentration of graph matrices

  • When ∆ > C ln n, Theorem 3.1 bounds adjacency-matrix deviations; when d ≥ C ln n, it also bounds Laplacian deviations over the stated failure-probability range.The constants may depend on c, but not on n or p.Source: §3 · pp. 9–10
  • For eigenvalue ranges separated from the rest of the typical matrix spectrum, the corresponding random-matrix eigenspace projections are typically close.The paper notes that such separation conditions hold in non-trivial inhomogeneous random graph cases.Source: §3 · pp. 10–11

3.1 Proof of the concentration result

  • The proof applies a matrix concentration inequality to sums of independent, centered edge matrices whose eigenvalues are bounded.Its variance term uses the largest eigenvalue of a sum of matrices, rather than the sum of their largest eigenvalues.Source: §3.1 · pp. 11, 15
  • The resulting bound has a −t^2/∆ exponent for small enough t, whereas the compared Hoeffding bound would be much weaker.For the adjacency-matrix sum, applying that Hoeffding bound requires r_i = 1/2.Source: §3.1 · p. 15

4 The Erd¨os-R´enyi graph and quasi-randomness

The section applies matrix concentration to Erdős–Rényi graphs and connects adjacency-matrix concentration with quasi-randomness. It also notes that Laplacian concentration is not expected below the logarithmic-degree scale.

4.1 Concentration for the Erd¨os-R´enyi graph

  • For Erdős–Rényi graphs, the section presents concentration bounds and says their range correctly predicts when adjacency-matrix concentration can be expected.The bounds are described as suboptimal relative to stronger results in, whose arguments do not seem to generalize to other bond-percolation cases.Source: §4 · p. 16, §4.1 · p. 16
  • Laplacian concentration is not expected when pn ≪ ln n, since the graph can have multiple connected components with probability bounded away from zero when pn ≤ ln n.The multiplicity of zero in the Laplacian spectrum equals the number of connected components.Source: §4.1 · p. 16

4.2 Quasi-randomness as concentration of the adjacency matrix

  • A sequence of graphs is quasi-random if and only if its adjacency matrices are sufficiently close to the typical adjacency matrix.The section frames this as a characterization of quasi-randomness through adjacency-matrix concentration.Source: §4.2 · p. 18

5 Application to bond percolation

For bond percolation on an arbitrary graph, the section applies the general concentration theorem when the minimum expected degree is sufficiently large. It also derives eigenvector consequences and compares a spectral-gap bound with that of Chung and Horn.

5 Application to bond percolation

  • When pd_G ≥ C ln n, the section applies its concentration theorem to the percolated graph and identifies the relevant degree parameters as pd_G and pΔ_G.Here d_G and Δ_G are the minimum and maximum degrees of the original graph.Source: §5 · p. 20
  • For an isolated Laplacian eigenvalue, the percolated graph has a corresponding eigenvalue of multiplicity one, and its normalized eigenvector is close to the original eigenvector up to sign.The eigenvalue interval must contain no other eigenvalues of the original Laplacian; the passage also notes analogous conclusions for eigenspace projectors when multiplicity is higher.Source: §5 · p. 20
  • The section’s spectral-gap bound improves on Chung and Horn’s bound for all n and pd_G, and is nontrivial where their bound is vacuous for ln n ≪ pd_G ≪ ln^(3/2−ε) n.The passage describes this as the most dramatic improvement in that range.Source: §5 · p. 21

6 Application to inhomogeneous random graphs

The section studies an inhomogeneous random graph built from sampled points and a symmetric attachment kernel. Its main aim is to relate the normalized adjacency matrix to an integral operator defined by that kernel.

6 Application to inhomogeneous random graphs

  • Each pair of sampled points is assigned an edge probability through a density parameter and a symmetric kernel, defining the inhomogeneous random graph.The model’s dependence on the sampled point vector is implicit in its notation.Source: §6 · p. 21
  • The model’s random graph is formed using the kernel-based edge weights and the independent-edge construction introduced earlier.The passage defines the model as a random graph with the stated weight function.Source: §6 · p. 21
  • The section aims to show that the graph’s adjacency matrix, after normalization by pn, is related to the integral operator on L2([0, 1]) defined by κ, up to small error terms with high probability.The stated goal concerns the adjacency matrix; related Laplacian results are discussed in Section 8.Source: §6 · p. 21

6.1 Some history of the model

The section situates inhomogeneous random graphs among work on component structure, graph limits, and convergence of sparse graph sequences. It distinguishes the paper’s focus on kernel convergence in a stronger metric.

6.1 Some history of the model

  • Bollobás, Janson, and Riordan studied the model at p = Θ(1/n) on broader background spaces, focusing on connected components.Their motivation was analogous to the Erdős–Rényi phase transition at p = 1/n.Source: §6.1 · p. 22
  • For dense graphs, graph-limit theory relates convergent graph sequences and graphons through normalized subgraph counts, and random graphs generated from a graphon converge to it.The passage describes graphons as non-negative symmetric functions with κ ≤ 1.Source: §6.1 · p. 22
  • Earlier work examined bond percolation on convergent graph sequences and sparse-graph convergence, while this paper says its random graphs converge to the corresponding kernel in a stronger metric.The sparse-graph relationship between subgraph-count convergence and cut-metric convergence is described as not fully elucidated.Source: §6.1 · p. 22

6.2 The precise result

Theorem 6.1 controls the spectrum of the sampled graph operator by approximating the kernel with a bounded Lipschitz function. Its bounds depend on the approximation quality and Lipschitz constant, so they need not be uniform across kernels.

6.2 The precise result

  • Theorem 6.1 applies when κ has an ε-close, bounded L-Lipschitz approximation and pn ≥ C ln n, with p ≤ 1/K.The error parameter θ depends on ε, L, K, n, and p.Source: §6.2 · pp. 22–23
  • For S⊂R, m_{A_{n,κ,p}/p_n}(S) sums the multiplicities of eigenvalues of A_{n,κ,p}/p_n lying in S; m_{Tκ}(S) is defined similarly.Source: §6.2 · pp. 23–24
  • The theorem implies that A_n,p,κ/pn is determined by κ up to small high-probability errors and coordinate permutation, and its nonzero eigenvalues are strongly consistent estimators of those of Tκ.The consistency statement applies as n tends to infinity with p=p(n).Source: §6.2 · p. 24
  • The error bounds depend on κ because the Lipschitz constant needed for a given L2 approximation error can vary with the kernel.The authors contrast this dependence with approximation in the cut norm.Source: §6.2 · p. 24

6.3 Convergence in the operator and cut metrics

This section distinguishes cut-metric convergence from operator-metric convergence for graph kernels. The cut metric supports dense-graph convergence results, while the paper uses the stronger operator norm to control eigenvalues in the sparse setting.

6.3.1 The cut norm and the cut metric

  • The cut metric treats kernels as equivalent under measure-preserving rearrangements, so it does not distinguish kernels of isomorphic graphs.The cut norm induces graph distance, but that distance may remain positive even for isomorphic graphs.Source: §6.3.1 · p. 25
  • For dense graphs, cut-metric convergence implies convergence of normalized subgraph counts and gives a criterion for testable graph properties, but substantially less is understood when p=o(1).The cited discussion also notes conjectures concerning the sparse case.Source: §6.3.2 · p. 25

6.3.2 The operator norm and the operator metric

  • The paper states that cut norm alone does not generally control adjacency eigenvalues, with difficulties extending bounded-kernel results to sparse graphs.The text relates eigenvalue estimation to counting cycles in the corresponding graph or graphon.Source: §6.3.2 · pp. 25–26
  • The authors use the stronger L2→L2 operator norm, defining an operator metric on square-integrable kernels; their methods achieve this stronger convergence notion.For n≫1 and p≫ln n/n under Assumption 6.1, the graph kernel converges to κ in the operator metric.Source: §6.3.2 · p. 26
  • A drawback of the operator metric is that it lacks a corresponding weak or strong regularity lemma for approximating bounded kernels by a bounded number of simple-function values.The passage connects this drawback to the dependence of Theorem 6.1’s bound on the kernel.Source: §6.3.2 · p. 26

6.4 Proof of Theorem 6.1

The proof transfers the sampled adjacency matrix to an operator on L2, controls its distance from the kernel operator, and then applies perturbation results to obtain spectral conclusions. Its approximation step uses a Lipschitz kernel close to κ in L2.

6.4.1 The relationship between TGn,p,κ and AGn,p,κ

  • The operators H_nΠ_αE_n are orthogonal projections, identifying the nonzero eigenvalues and eigenspaces of T_Gn,p,κ with those of A_n,p,κ after scaling by pn.This relationship lets the proof transfer spectral comparisons between the finite matrix and the graph-kernel operator.Source: §6.4.1 · pp. 26–27

6.4.2 The concentration argument

  • Conditioning on the sampled points makes the edge indicators independent, allowing Theorem 3.1 to control the random adjacency matrix when the conditional degree parameter Δ is at least C ln n.The comparison uses the matrix with entries pκ(X_i,X_j).Source: §6.4.2 · pp. 27–28

6.4.3 Nearing the end of the argument

  • The proof bounds the graph-kernel operator’s distance from Tκ, then invokes perturbation lemmas to transfer eigenvalue and eigenspace conclusions.The operator comparison is carried through the maps E_n and H_n, whose norms are bounded by 1.Source: §6.4.2 · p. 28, §6.4.3 · pp. 28–29

6.4.4 Approximating Tκ

  • The approximation lemma assumes a bounded, symmetric L-Lipschitz kernel κ_ε that is ε-close to κ in L2.The proof bounds contributions using the sampled points and a concentration estimate for their empirical distribution, citing Massart’s version of the DKW inequality.Source: §6.4.4 · pp. 29, 31

7 Freedman’s inequality for matrix martingales

This section develops a matrix-martingale concentration inequality by adapting scalar Freedman-style arguments to matrices. The proof relies on positive-semidefinite order, conditional-expectation monotonicity, and matrix exponentials.

7.1.1 The positive semi-definite order

  • The proof works in the positive-semidefinite order, where A⪯ξI is equivalent to λ_max(A)≤ξ.The order supports the trace monotonicity argument used in the proof.Source: §7.1.1 · p. 32

7.1.2 Conditional expectations are monotone

  • Conditional expectation preserves the positive-semidefinite order: X⪯Y almost surely implies E[X|G]⪯E[Y|G] almost surely.The text justifies the matrix statement by testing quadratic forms v*Xv.Source: §7.1.2 · pp. 32–33

7.1.3 Matrix functions and matrix exponentials

  • The section introduces matrix functions and the Golden–Thompson inequality as tools for adapting standard concentration proofs to matrices.The passage identifies Golden–Thompson as fundamental to this adaptation.Source: §7.1.3 · p. 33

7.2 The proof

  • The proof derives an exponential inequality for martingales and uses it in proving Theorem 1.2.It also notes that the matrix-martingale result yields bounds for sums of independent mean-zero random matrices.Source: §7.2 · pp. 34–36

8 Final remarks

The final remarks test the martingale bound’s sharpness, describe further operator and lift applications, and identify unresolved questions about sparse-graph spectra and broader extensions.

Sharpness of Theorem 1.2

  • A diagonal-matrix example shows that the factor d in the martingale bound is necessary, and Corollary 7.1 matches its scale up to constants in the exponent.The example uses independent, unbiased ±1 diagonal entries; its largest eigenvalue is the maximum of d independent sums.Source: §8 · p. 37

Better bounds and extensions?

  • Whether the factor d can be removed, perhaps by recovering sharper results through a variant of Theorem 1.2, remains open.The remarks also ask whether other applications are possible where the Christofides-Märkstrom variance term is too large.Source: §8 · p. 37

Other applications of Theorem 1.2

  • A random-lift Laplacian is essentially indistinguishable from the Laplacian of the corresponding sequential random lifts, when the original graph’s minimum degree is ω(ln(k1k2n)).The comparison is between a random k1k2-lift and a k1-lift followed by a k2-lift.Source: §8 · p. 37

The Laplacian of inhomogeneous random graphs

  • Under a uniform lower bound K_- on kernel degrees, the inhomogeneous-graph Laplacian corresponds closely to Sξ, with consequences for its spectrum and eigenspaces.The lower bound requires the kernel’s integral over y to be at least K_- for every x; the authors omit the consequences’ details.Source: §8 · p. 38

Better bounds and extensions?

  • Prior work finds well-behaved large cores even in sparse graphs and; extending that result to more general bond percolation or inhomogeneous random graphs is posed as an open question.Source: §8 · p. 38

Cut convergence, eigenvalues and eigenvectors

  • The author leaves unresolved whether cut-norm convergence to a kernel suffices for eigenvalue and eigenvector convergence in sparse graphs, even under suitable assumptions.Source: §8 · p. 38

A Appendix: two perturbation results

The appendix states perturbation results for spectra and spectral projectors of compact Hermitian operators and outlines finite- and infinite-dimensional proof techniques.

Lemma A.1

Finite-rank case

  • For finite-rank operators, the proof restricts to the span of their ranges and applies the eigenvalue perturbation bound; the condition on S handles a possible zero eigenvalue in that restriction.Source: A Appendix: two perturbation results · p. 39

Infinite-rank case

  • For arbitrary compact operators, the proof approximates them by finite-rank operators within δ and passes to the limit as δ decreases.The approximants retain only finitely many spectral components outside (−δ, δ).Source: A Appendix: two perturbation results · pp. 39, 42

Lemma A.2

  • Lemma A.2 sets up a comparison of projectors onto an eigenvalue interval, assuming operator distance at most ε and spectral gaps around both interval endpoints.Its finite-dimensional proof uses contour integration of the resolvent, and the appendix says this completes that case.Source: A Appendix: two perturbation results · pp. 40–41

Related papers

Loading 0911.0600v2…