Organizers
Gary Miller, Carnegie Mellon University
Bob Collins, Penn State University

Spectral Graph Theory or Algebraic Graph Theory, as it is also known, is the study of the relationship between the eigenvalues and eigenvectors of graphs and their combinatorial properties. Random walks on graphs, expander graphs, clustering, and several other combinatorial aspects of graphs are intimately connected to their spectral properties.

These connections have recently found algorithmic applications of great impact. As an example, one of Google’s first patents used the Perron-Frobenius eigenvector to rank pages from the Internet. Also, many recent exciting approaches to the analysis of high-dimensional data have exploited the smallest eigenvectors of normalized Laplacian matrices. The data sets in many of these applications are large and ever increasing. Moreover, the applications often require “real-time” accurate responses to the given queries. This creates the need for very fast algorithms, that also provide strict theoretical guarantees on their output.

This PROBE brings together researchers from a wide range of disciplines, including machine learning, algorithms, computer science theory, Internet search, human computation, numerical analysis, and materials science. The goal of our research in this PROBE is two-fold. One, design better and fast algorithms for finding eigenvectors/eigenvalues of graphs and solving linear systems derived from graphs. Two, find better way to use eigenvectors/eigenvalues of graphs to analysis and cluster real world data.