A Brief (Not-so-mathematical) Introduction To Spectral Graph Theory


"Just as astronomers use stellar spectra to determine the make-up of distant stars... [we aim] to deduce the properties and structure of [networks] from its spectrum."

-Chapter 1, Spectral Graph Theory by F.R.K. Chung


Suppose you asked, "What the largest group of people on Facebook who are all mutually friends with each other?". (Mathematically, this is known as the "largest clique problem"). This sounds like a trivial problem; after all, you could try all the possibilities. However, given that Facebook has hundreds of millions of users, there are more combinations for just 100 users than there are protons in the universe! Hence, "trying all the possibilities" is not exactly feasible.

So how would one approach finding the answer, or even find an estimate, to the question? This is where spectral graph theory comes into play. The main premise of spectral graph theory is to encode a graph or network into a matrix, then compute the eigenvalues (together known as the "spectra") of the matrix. These eigenvalues can be computed efficiently and accurately. Finally, using the eigenvalues, we can deduce important information about the graph or network.

We illustrate this idea was a much smaller network below:

In the case above, a simple fact is spectral graph theory says that the largest clique size is not more than the largest eigenvalue (so it can be no more than 8), and from a simple inspection we can find a clique of size 4. Hence, we know the maximum clique is between 4 and 8, inclusive. However, even in this case, spectral graph theory can go further. Using more sophisticated techniques, we can also determine good candidates for the largest clique.

And this is just the tip of the iceberg! Spectral graph theory can be used to estimate (or sometimes determine exactly) all sorts of properties of networks: With no doubt, as we enter the "overinformation age" where we have more information than we know what to do with, spectral graph theory will, more and more, become a very important tool for sifting and analyzing the large amount of data and information the world generates!

And if none of those things convinced you that spectral graph theory is useful, hopefully this will:

"Spectral graph theory is a useful subject. The founders of Google computed the Perron-Frobenius eigenvector of the [internet] and became billionaires."

-Preface from Spectra of Graphs by A.E. Brouwer and W.H. Haemers