Fall 2023 Data Science Seminar Series
Stephen Young–Reimagining Spectral Graph Theory

Speaker: Stephen Young, Ph.D., Scientist at Pacific Northwest National Laboratory; Algorithms, Combinatorics, and Optimization Team Lead 

Faculty Host: Nate Veldt, CSCE

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 may be 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 this 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 on both the vertices and the edges. We demonstrate this synthesized approach on cyber data by using the latent space embedding generated by an autoencoder on the metadata to define the inner product.

Biography: As a graduate student at the Georgia Institute of Technology, Young studied the mathematical properties of complex networks such as the world wide web and social networks, as well as the combinatorial properties of partially ordered sets. After graduating with his PhD in Algorithms, Combinatorics, and Optimization in 2008, Young worked with Dr. Fan Chung at the University of California, San Diego to understand the emergence of paradoxical behaviors in selfish routing on networks with an underlying expansion property. After completing his post-doctoral studies, he joined the faculty of the Department of Mathematics at the University of Louisville, where he continued his research into properties of models for complex networks and combinatorics of partial orders. Since joining Pacific Northwest National Laboratory in 2015, Young has applied combinatorial and algorithmic techniques to a variety of application areas, including the mathematics of topological quantum computation, anomaly detection in cyber-systems, graphical models for the transmission layer of the grid, and the design of network topologies for next-generation supercomputers. Since 2020, he has been a team lead in PNNL’s Physical and Computational Sciences directorate and is currently serving as the lead for the Algorithms, Combinatorics, and Optimization team.

Link to PDF version

You can also click this link to join the seminar

For more information about TAMIDS Seminar Series, please contact Ms. Jennifer South at jsouth@tamu.edu