Reimagining Spectral Graph Theory

ACO Alumni Lecture
Wednesday, September 27, 2023 - 4:00pm for 1 hour (actually 50 minutes)
Skiles 005
Stephen Young – Pacific Northwest National Laboratory
Christine Heitsch

Abstract: While spectral methods provide far-ranging insights on graph structure, there remain significant challenges in their application to real data. Most notably, spectral methods do not incorporate information that maybe available beyond adjacency.  A common approach to incorporating such additional information is encode this information in an ad-hoc manner into weights associated with the edges. Not only does this have limited expressivity, but is also restricted by graph structure: if two vertices are not adjacent, then edge weights cannot capture any closeness implied by metadata.

We address this issue by introducing the inner product Hodge Laplacian for an arbitrary simplicial complex.  Within this framework we prove generalizations of foundational results in spectral graph theory, such as the Cheeger inequality and the expander mixing lemma, and show our framework recovers the usual combinatorial and normalized Laplacians as special cases. Our framework allows for the principled synthesis of combinatorial approaches in network science with more metadata driven approaches by using latent space encodings of the metadata to define an inner product both the vertices and the edges.

(Coffee will be available at 3:30 before this talk, following the speaker's Professional Development Seminar at 2:30pm.)