We formulate spectral clustering for directed graphs as an
optimization problem, the objective being a weighted cut in the
directed graph. This objective extends several popular criteria like
the normalized cut and the averaged cut to asymmetric affinity data.
We show that this problem can be relaxed to a Rayleigh quotient
problem for a symmetric matrix obtained from the original affinities
and therefore a large body of the results and algorithms developed for
spectral clustering of symmetric data immediately extends to
asymmetric cuts. We also compare and contrast this approach with an
approach based on the Markov random walk view of spectral
clustering. We show that the two approaches coincide in the case of
symmetric spectral clustering (i.e for undirected graphs) but that
they bifurcate for the richer case of asymmetric affinities.