Spectral clustering of directed and time-evolving graphs : theory and applications
Abstract
Description
Spectral clustering of vertices in graphs is well understood for undirected graphs and there
exists a wealth of literature on the subject. The method computes a graph Laplacian
matrix and groups vertices by projecting them into a lower dimensional space using the
eigenvectors of this Laplacian matrix, which contain information about connectivity in the
graph. However, standard spectral clustering fails on directed graphs, where relationships
between vertices are not necessarily reciprocal and clusters can be characterised in different
ways. It is also not obvious how to apply the spectral clustering framework to graphs
that evolve in time, as there are many questions to consider about how to represent these
graphs and how to define a cluster in this case.
This work proposes two extensions to the standard spectral clustering approach, exploiting a connection with dynamical systems theory to consider clusters on graphs as
coherent sets using transfer operators. In the case of directed graphs, we propose a Laplacian based on a forward–backward operator which captures dynamics of random walkers
on the graph. We illustrate that this is equivalent to the standard approach for undirected
graphs as a special case, and numerical results show that this Laplacian outperforms existing approaches for clustering directed graphs in certain parameter settings. A further
graph Laplacian is proposed for clustering time-evolving graphs, which draws on canonical
correlation analysis and can also be interpreted via dynamical systems. We analyse the
performance on benchmarks and show that this Laplacian yields substantial advantages
over existing methods. Additionally, a real-world example derived from fluid dynamics is
considered and we show that our clustering algorithm can accurately detect fluid patterns
evolving in time.