PACM Colloquium: Network clustering with higher order structures

Spectral clustering is a well-known way to partition a graph or network into clusters or communities with provable guarantees on the quality of the clusters. This guarantee is known as the Cheeger inequality and it holds for undirected graphs. We'll discuss a new generalization of the Cheeger inequality to higher-order structures in networks including network motifs. This is easy to implement and seamlessly generalizes spectral clustering to directed, signed, and many other types of complex networks. In particular, our generalization allow us to re-use the large history of existing ideas in spectral clustering including local methods, overlapping methods, and relationships with kernel k-means. We will illustrate the types of clusters or communities found by our new method in biological, neuroscience, ecological, transportation, and social networks.
This is joint work with Austin Benson and Jure Leskovec at Stanford.

Bio:
David Gleich is an assistant professor in the Computer Science Department at Purdue University whose research is on novel models and fast large-scale algorithms for data-driven scientific computing including scientific data analysis and social network analysis. He held theJohn von Neumann post-doctoral fellowship at Sandia National Laboratories in Livermore CA before joining Purdue in Fall 2011. Gleich received an NSF CAREER Award in 2011 for work on matrix methods for large-scale network analysis. His research is funded by the NSF, DOE, DARPA, and NASA. In 2016, Gleich also received a Sloan Research Fellowship.