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.

  • 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 Jan 12 '19 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 Jan 12 '19 at 1:13
  • 3
    $\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 Jan 12 '19 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 Jan 12 '19 at 16:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.