13
$\begingroup$

Is there a version of Weyl's law or a local Weyl's law for eigenvectors of the graph Laplacian?

For some context, a colleague in statistics has encountered eigenvectors of the Laplacian for certain graphs. In her applications, the low frequencies correspond to large-scale spatial patterns, whereas the higher eigenfunctions tend to be localized (i.e. they are very small except at a few vertices) and oscillate rapidly.

The eigenvector correspond to the Fiedler eigenvalue An eigenvector correspond to a large eigenvalue

For an example, here are two eigenfunctions of the graph corresponding to block groups in Columbus, Ohio. The first corresponds to the principle eigenvalue whereas the latter is associated to a high frequency. For her work, the graphs are always planar, but may not be regular and are fixed (i.e. not expanding).

She asked me if I knew of a reference that rigorously formalizes this phenomena. I wasn't able to find one, or even sure what it would be referred to in spectral graph theory. Does anyone have any recommendations?

The Continuous Case

In the continuous case on a compact manifold, this phenomena corresponds to some well-known results about the Laplace-Beltrami operator.

The fact that the low-frequency eigenfunctions correspond to more "global" patterns can be formalized in terms of Bernstein (or Li-Yau) gradient estimates, which show that the functions do not oscillate too rapidly. Furthermore, it is possible to bound the number of nodal domains, which shows that the eigenfunctions do not switch signs too many times.

At higher frequencies, the fact that the eigenfunctions tend to be localized and oscillate rapidly can be proven using the local Weyl's law and some estimates bounding the size of the nodal sets. For precise statements of these results, Professor Canzani has some lecture notes that include these results (see Chapter 8).

The issue that seems to prevent the direct application of these results to the discrete case is that the graph is fixed so there are only finitely many eigenvectors of the graph Laplacian. As such, it's not clear how to apply asymptotic results or how to prove gradient type estimates on a space that is not smooth.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ If you want version of Weyl's law with pointwise bounds (I call it a "quantitative Weyl law"), my gut instinct is to try a heat kernel approach: Bound the heat trace (sum of probabilities of return) as a function of time and then try to use a discrete Laplace transform to try to get pointwise bounds on the eigenvalue counting function. But that doesn't really answer questions about how the eigenfunctions reflect the graph's structure, that says more how eigenvalue growth rates reflect some notion of volume. $\endgroup$
    – Neal
    Commented Jan 12, 2019 at 1:08
  • 1
    $\begingroup$ The graph Laplacian for a planar graph could be viewed as a discretization of the Laplacian on an appropriate domain -- in the examples above, as an approximation of the Laplacian of the domain circumscribed by the boundary of Columbus. So another approach might be to study eigenvalues of the Laplacian on that domain (perhaps with other discretizations, such as fine triangular meshes). But that ignores structure relevant to your colleague such as population density. I think there's interesting mathematics to be found exploring the difference between this discretization and an "arbitrary" one. $\endgroup$
    – Neal
    Commented Jan 12, 2019 at 1:13
  • 4
    $\begingroup$ One other thought before I dive into this... if you are not familiar, there is a result of Cheeger connecting the principal eigenvalue to a measure of how separated the manifold is into two distinct volumes. I understand the same argument easily gives a similar result for a graph. en.wikipedia.org/wiki/Cheeger_constant_(graph_theory) $\endgroup$
    – Neal
    Commented Jan 12, 2019 at 1:18
  • $\begingroup$ Thanks for the suggestions. I imagine that considering the discrete Laplacian as an approximation of the continuous one probably works well for the lower frequency eigenfunctions. However, for the higher eigenfunctions it's much less clear how to make it work. $\endgroup$
    – Gabe K
    Commented Jan 12, 2019 at 16:49

2 Answers 2

Reset to default
4
+50
$\begingroup$

There will certainly exist a Weyl law for random planar graphs. However, the nature of the law will depend very sensitively on exactly which model of random graphs one takes.

One can start to see this by considering the first two moments of the eigenvalues of the graph Laplacian. The first moment is the average degree of a vertex, while the second moment is the average of $d(d+1)$, for $d$ the degree. This means that from the Weyl law we can determine the mean and variance of the degree distribution. For a model of random large planar graphs the mean and variance of the degree will typically converge to some constants as the size of the graph goes to $\infty$, but the constants depend on the model.

More generally the $k$th moment of the eigenvalue distribution of the graph Laplacian is the trace of the $k$th power of the graph Laplacian which can be expressed as a sum over loops of length $\leq k$ in the graph. For each vertex $v$ of a random graph, the sum over loops of length $\leq k$ starting and ending at $v$ is an integer-valued random variable. In a reasonable model of large random planar graphs we would expect this random variable to converge to a limiting distribution as the size of the graph goes to $\infty$, and we would expect variables associated to points a distance significantly more than $k$ from each other to be approximately independent, so a law of large numbers implies that the $k$th moment of the eigenvalue distribution converges almost surely to the expectation of the limiting distribution. But this variable depends finely on the local structure of the graph, and so its distribution depends on the random model. I don't think there is any kind of universal distribution that applies to an arbitrary planar graph.

In her applications, the low frequencies correspond to large-scale spatial patterns, whereas the higher eigenfunctions tend to be localized (i.e. they are very small except at a few vertices) and oscillate rapidly.

The fact that low frequencies correspond to large-scale spatial patterns should be possible to verify rigorously. If a function $f$ is an eigenvector of the Laplacian $L$ with eigenvalue $\lambda$ small then $|| L f||_2 = || \lambda f ||_2 = \lambda ||f||_2$ is small. But $||L f||_2^2 $ is just the sum over edges connecting vertices $v_1,v_2$ of $(f(v_1)-f(v_2))^2$. So $f(v_1)-f(v_2)$ must be small for most edges, meaning the function $f$ does not change rapidly.

The fact that high frequencies oscillate rapidly is also generic, applying to almost any graph, and can be established rigorously, by a reverse argument: For $f$ an eigenvector with large eigenvalue (compared to the average degree of vertices where $f$ is large) the differences $f(v_1)-f(v_2)$ must be large for many pairs of $v_1,v_2$ connected by an edge, which is only possible if $f$ oscillates rapidly.

The last fact, that higher eigenfunctions are localized, seems most interesting. I don't think this is true for generic graphs or even for typical planar graphs, e.g. I am pretty sure this is not true for the grid graph. This must reflect a special feature of your colleague's graphs.

One possible explanation is that her graphs contain clusters with a large number of edges within the cluster and a small number of edges connecting the cluster outside - I mean with a larger discrepancy between these two figures than you would get in a uniform planar graph. In such a graph I think you might see eigenfunctions localized on the clusters.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Thanks for the helpful answer. About your last point, you are correct that for a uniform rectangular lattice, the high-frequency eigenvectors will not localize (and this might be true for grid graphs as well). However, in curved geometry, the $L^\infty$ norm of $L^2$-normalized eigenfunctions can grow like $O(\lambda^{(n-1)/4})$. My intuition is that a non-uniform grid should behave somewhat like a curved manifold, so this localization phenomena is reflecting that fact. $\endgroup$
    – Gabe K
    Commented Jul 16 at 17:19
  • $\begingroup$ In general, the $L^\infty$ growth of the eigenfunctions is slower than that (the bound is only sharp in spherical geometry) and won't apply to every eigenfunction, but that's the intuition for why there can be sharp local peaks. $\endgroup$
    – Gabe K
    Commented Jul 16 at 17:22
  • 1
    $\begingroup$ @GabeK For a general curved manifold one expects the lower bound of the $L^\infty$ norm coming from the $L^2$ norm to be close to sharp. For locally symmetric spaces, one expects large $L^\infty$ norms to occur only for some global geometric reason. For the sphere, this is the global symmetry. For arithmetic hyperbolic manifolds there can be large values arising from special subgroups of the arithmetic group. In this case the points of the manifold where large values occur are special, it cannot be an arbitrary point. $\endgroup$
    – Will Sawin
    Commented Jul 16 at 17:32
  • 1
    $\begingroup$ @GabeK In neither case that I am familiar with is a typical high-frequency eigenfunction localized: In the sphere case these are very special eigenfunctions invariant under a large subgroup, and in the arithmetic hyperbolic case they are functorial transfers. So your colleague's observations still seem non-manifold-like to me. $\endgroup$
    – Will Sawin
    Commented Jul 16 at 17:34
  • 1
    $\begingroup$ @Pulcinella. Each infinite graph has its own spectral measure. One can consider this spectral measure to be a "Weyl law", or one can consider the fact that the measure depends on the graph to be the absence of a 'Weyl law". For an infinite graph of bounded average edge degree, the spectrum is typically not infinitely large, so it's not clear what the right analogue of a Weyl law would be. $\endgroup$
    – Will Sawin
    Commented Jul 22 at 20:45
1
$\begingroup$

For $N_\lambda$ denoting the number of eigenvalues less than $\lambda$, Weyl's law gives the asymptotics of $N_\lambda$ as $\lambda$ tends to infinity. The usual approach to establish this asymptotics in the continuum divides space into boxes. This fails for a graph, since cutting the graph is not a small perturbation.
An analogue of Weyl asymptotics for graph Laplacians that satisfy a strong isoperimetric inequality is given in Graphs and Discrete Dirichlet Spaces by Keller, Lenz, and Wojciechowski, page 439. See also Essential spectrum and Weyl asymptotics for discrete Laplacians by Bonnefont and Golenia.

The above refers to the eigenvalues. For the eigenvectors, the localisation phenomenon has been studied in Localization of Laplacian eigenvectors on random networks, but there is no "rigorous" theory.

Concerning the connection with random matrix theory: Randomly weighted $d$-regular graphs [fixed number of neighbors $d$ of each vertex, with weights defined on the edges that are uniformly and independently drawn from (-1,1)] have a mean spectral density $\rho(\mu)$ of the graph Laplacian given by the Kesten-McCay law: $$\rho(\mu)=\frac{d}{2\pi}(d^2-\mu^2)^{-1}\sqrt{4(d-1)-\mu^2},\;\;\text{for}\;\;|\mu|<2\sqrt{d-1}.$$ See for example Local Kesten-McKay law for random regular graphs. In this case the eigenvalues are delocalised. The Wigner semi-circle law of Gaussian random matrix ensembles is obtained in the limit $d\rightarrow\infty$.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Can you write down a concrete result/conjecture that you claim is the correct analogue of Weyl's formula? $\endgroup$
    – Pulcinella
    Commented Jul 15 at 13:26
  • 1
    $\begingroup$ As a follow up to @Pulcinella's question, is there a known distribution for the spectrum of a random planar graph? Random matrices often follow a semi-circle law, but I'm not sure what the correct analogue to that is here. $\endgroup$
    – Gabe K
    Commented Jul 15 at 14:38
  • $\begingroup$ @GabeK -- there is indeed a graph analogue of the semicircle law, I've added the formula. $\endgroup$
    – Carlo Beenakker
    Commented Jul 15 at 15:13
  • $\begingroup$ Thanks, but I believe this applies to regular graphs. The statistics for planar graphs might be very different. $\endgroup$
    – Gabe K
    Commented Jul 15 at 16:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .