  The sparsest cut problem consists of identifying a small set of edges that
breaks the graph into balanced sets of vertices. The normalized cut problem
balances the total degree, instead of the size, of the resulting sets.
Applications of graph cuts include community detection and computer vision.
However, cut problems were originally proposed for static graphs, an assumption
that does not hold in many modern applications where graphs are highly dynamic.
In this paper, we introduce the sparsest and normalized cut problems in
temporal graphs, which generalize their standard definitions by enforcing the
smoothness of cuts over time. We propose novel formulations and algorithms for
computing temporal cuts using spectral graph theory, multiplex graphs,
divide-and-conquer and low-rank matrix approximation. Furthermore, we extend
our formulation to dynamic graph signals, where cuts also capture node values,
as graph wavelets. Experiments show that our solutions are accurate and
scalable, enabling the discovery of dynamic communities and the analysis of
dynamic graph processes.
