Linear algebra is a common theme in graph analysis, and spectral approaches to graph partitioning, clustering, and ranking are among the most popular methods now available. We use spectral ideas to explore graphs in novel ways, whether looking at local clusters and communities in graph or looking at how the global PageRank vector changes with systematic variations in how a graph is constructed. Often, these forays into spectral graph theory start from a completely different problem; recent examples include analyzing models of opinion formation and understanding the difficulty of a standard problem from computer vision (rotation averaging).



Analyzing graphs based on global and local Density of States

Edge-weighted personalized PageRank

Using model reduction for fast PageRank with varying edge weights.

Local spectral clustering

Using eigenvalue iterations to grow graph clusters from seeds.

Rotation averaging

How hard is it to combine pictures to understand scene geometry?

Opinions as game theory

In the game of expressing our opinions, we all want to both follow our beliefs and agree with our friends. Analyzing Nash equilibria yields interesting insights. Eigenvalues are involved!