This talk has three parts. In the first part we discuss two flow-based
rounding methods that can be used to extract cuts from graph
embeddings. While running in nearly linear time, these consider an
exponential number of possibilities and are strictly more powerful
than the hyperplane-based methods which are in common use.

In the second part we discuss the tradeoff between cut quality and
balance in some large real-world power-law graphs, providing empirical
confirmation of the "Octopus" structure theorem of Chung and Lu which
says that certain power-law graphs consist of a core and tentacles. We
point out that this structure causes practical difficulties for
Spectral partitioning and clustering methods, which end up chopping
off tiny pieces of the graph.

In the third part we discuss how a well-known SDP-based vector
relaxation of graph partitioning can be thought of as a version of the
Spectral relaxation in which the balance constraint has been
strengthened. We use this SDP relaxation and flow-based rounding to
find some balanced cuts in a 2 million node social graph.