Normalized cut

A normalized cut is a graph partitioning criterion that measures the cost of cutting a graph into disjoint subsets relative to the total connection from each subset to all vertices in the graph. Formally, the normalized cut of a partition (A, B) is:

Ncut(A, B) = cut(A, B) / assoc(A, V) + cut(A, B) / assoc(B, V)

where cut(A, B) is the sum of weights of edges between A and B, and assoc(A, V) is the sum of weights of all edges from A to any vertex in the graph. Minimizing the normalized cut produces partitions that are not only separated from each other (low cut) but also internally coherent (high association), avoiding the trivial solution of isolating a single vertex.

The normalized cut problem is NP-hard, but Shi and Malik (1997) showed that a continuous relaxation leads to a generalized eigenvalue problem involving the graph Laplacian. This relaxation is the foundation of spectral clustering: the eigenvectors of the normalized Laplacian provide an embedding in which the normalized cut problem becomes separable by simple clustering methods.

The normalized cut criterion has been particularly influential in computer vision, where it provides a principled framework for image segmentation. The pixels of an image are represented as vertices in a graph, with edge weights encoding pixel similarity, and normalized cut partitioning separates objects from background while maintaining internal coherence within each region.