### Summary

Researchers from many disciplines study spectra to understand the
structure and composition of mathematical objects and physical systems.
For large systems, *complete* spectral information costs too much,
whether it is gathered computationally or measured experimentally;
hence, most spectral analysis methods use *partial* information about
the eigenvalues or eigenvectors of some matrix or operator.
Broadly speaking, these methods use either

- A few (extreme) eigenvalues and associated eigenvectors
- Invariants that are simple functions of all the eigenvalues
- Densities of eigenvalues (a.k.a. density of states), possibly weighted by local importance.

All three approaches are used in spectral geometry an in applications to physics and engineering systems. But distributional information is much less used in the study of complex networks. Indeed, though Weyl’s law for eigenvalue distributions was introduced to spectral geometry six decades prior to Cheeger’s inequality, within spectral graph theory the latter is universally taught as part of spectral graph theory while the former is nearly unknown, though related concepts having to do with the heat kernel have started to be more widely used.

In this project, we explore the computation and interpretation of the density of states and local density of states for different network-related matrices.

### Papers

*Proceedings of the 2021 SIAM International Conference on Data Mining*, 2021, pp. 289–297.

@inproceedings{2021-sdm, author = {Huang, Leo and Graven, Andrew and Bindel, David}, title = {Density of States Graph Kernels}, booktitle = {Proceedings of the 2021 SIAM International Conference on Data Mining}, pages = {289--297}, year = {2021}, link = {https://doi.org/10.1137/1.9781611976700.33}, doi = {10.1137/1.9781611976700.33} }

#### Abstract:

A fundamental problem on graph-structured data is that of quantifying similarity between graphs. Graph kernels are an established technique for such tasks; in particular, those based on random walks and return probabilities have proven to be effective in wide-ranging applications, from bioinformatics to social networks to computer vision. However, random walk kernels generally suffer from slowness and tottering, an effect which causes walks to overemphasize local graph topology, undercutting the importance of global structure. To correct for these issues, we recast return probability graph kernels under the more general framework of density of states — a framework which uses the lens of spectral analysis to uncover graph motifs and properties hidden within the interior of the spectrum — and use our interpretation to construct scalable, composite density of states based graph kernels which balance local and global information, leading to higher classification accuracies on benchmark datasets.

*Proceedings of KDD*, 2019.

**Best research paper award**

@inproceedings{2019-kdd, author = {Dong, Kun and Benson, Austin R. and Bindel, David}, title = {Network density of states}, booktitle = {Proceedings of KDD}, month = aug, year = {2019}, arxiv = {1905.09758}, doi = {10.1145/3292500.3330891}, notable = {Best research paper award} }

#### Abstract:

Spectral analysis connects graph structure to the eigenvalues and eigenvectors of associated matrices. Much of spectral graph theory descends directly from spectral geometry, the study of differentiable manifolds through the spectra of associated differential operators. But the translation from spectral geometry to spectral graph theory has largely focused on results involving only a few extreme eigenvalues and their associated eigenvalues. Unlike in geometry, the study of graphs through the overall distribution of eigenvalues - the spectral density - is largely limited to simple random graph models. The interior of the spectrum of real-world graphs remains largely unexplored, difficult to compute and to interpret.

In this paper, we delve into the heart of spectral densities of real-world graphs. We borrow tools developed in condensed matter physics, and add novel adaptations to handle the spectral signatures of common graph motifs. The resulting methods are highly efficient, as we illustrate by computing spectral densities for graphs with over a billion edges on a single compute node. Beyond providing visually compelling fingerprints of graphs, we show how the estimation of spectral densities facilitates the computation of many common centrality measures, and use spectral densities to estimate meaningful information about graph structure that cannot be inferred from the extremal eigenpairs alone.

*SIAM Network Science 2015 (poster)*, 2015.

@inproceedings{2015-siam-ns, author = {Dong, Kun and Bindel, David}, title = {Modified Kernel Polynomial Method for Estimating Graph Spectra}, booktitle = {SIAM Network Science 2015 (poster)}, month = may, year = {2015} }

#### Abstract:

The kernel polynomial method (KPM) is a standard tool in condensed matter physics to estimate the density of states for a quantum system. We use the KPM to instead estimate the eigenvalue densities of the normalized adjacency matrices of “natural” graphs. Because natural graph spectra often include high-multiplicity eigenvalues corresponding to certain motifs in the graph, we introduce a pre-processing phase that counts just these special eigenvalues, leaving the rest of the eigenvalue distribution to be estimated by the standard KPM.

### Talks

#### Understanding Graphs through Spectral Densities

Cornell Applied Math Colloquium

spechist
•
colloquium local

#### Understanding Graphs through Spectral Densities

University of Buffalo Applied Math Seminar

spechist
•
seminar external invited

#### Understanding Graphs through Spectral Densities

WMU math colloquium

spechist
•
colloquium external invited

#### Understanding Graphs through Spectral Densities

ICIAM 2019

spechist
•
minisymposium external invited

#### Understanding Graphs through Spectral Densities

SIAG-LA lecture at ILAS 2019

spechist
•
meeting external invited plenary

#### Understanding Graphs through Spectral Densities

CS Colloquium, William and Mary

spechist
•
colloquium external invited

#### Understanding Graphs through Spectral Densities

Math Colloquium, Virginia Tech

spechist
•
colloquium external invited

#### Understanding Graphs through Spectral Densities

LANS Seminar, Argonne National Lab

spechist
•
seminar local

#### Understanding Graphs through Spectral Densities

SIAM Network Science, Portland

spechist
•
meeting external invited plenary

#### Understanding Graphs through Spectral Densities

Seminar at Huazhong University of Science and Tech

spechist
•
seminar external invited

#### Understanding Graphs through Spectral Densities

ZY-INS Colloquium, Shanghai Jiao Tong University

spechist
•
colloquium external invited

#### Density of States for Graph Analysis

SIAM Annual Meeting, Boston

spechist
•
meeting external poster

#### Understanding graphs through spectral densities

Cornell SCAN Seminar

spechist
•
seminar local

#### Spectral Densities and Social Networks

NYCAM

spechist
•
meeting local organizer

#### A Tale of Two Eigenvalue Problems

Cornell Brownbag Seminar

gyro mems spechist
•
seminar local