Spectral Methods for Seed-Set Expansion on Graphs

Spectral methods for graph clustering and community identification use the eigenvectors of one of a number of matrices associated with the graph to guide the clustering or ranking process. The commute time between two nodes, defined as the expected length of a random walk from one node to another and back again, provides a statistical measure of distance on the graph that has a simple formula as a sum of terms involving the spectrum of the associated matrices. We make some observations about the partial sums of this formula and cast the graph seed-set expansion problem as a regularization problem using the approximate commute time, testing our methods on real-world graphs and communities.