Normalized Cut

Normalized Cut is a way to split a network of data points into groups without making a careless cut through a dense, well-connected region. The basic idea is simple: if two sets of points are only weakly connected to each other, they probably belong in different clusters—but the split should also respect how strongly connected each group is internally.

What it measures

In graph-based clustering, each data point becomes a node, and edges carry similarity weights. A plain cut just adds up the weights of edges removed when the graph is split. The problem is that minimizing raw cut value favors tiny isolated groups. Normalized Cut fixes this by dividing the cut cost by the total connection strength, or volume, of each side. That makes the objective balance two goals:

keep connections within a cluster strong,
keep connections between clusters weak,
avoid trivial partitions like peeling off one small node.

Why it matters in practice

This idea is central to spectral clustering. Directly finding the best normalized cut is computationally hard, so the problem is relaxed into an eigenvector problem involving the graph Laplacian, especially the normalized Laplacian. Those eigenvectors embed the data into a new space where ordinary methods like k-means can separate the groups. This is why spectral clustering can detect curved or non-convex shapes that centroid-based methods miss.

Where you see it

Normalized cut became especially well known in image segmentation, where pixels or regions are connected by similarity in color, texture, or position. It is also useful in:

customer segmentation from similarity graphs built from behavior,
document clustering where documents link by shared terms or embeddings,
social or transaction networks where community structure matters.

In tools like scikit-learn, spectral clustering uses this same principle behind the scenes: build an affinity graph, compute a spectral embedding, then partition in that embedded space.

Normalized Cut is a graph partitioning objective that splits a similarity graph into clusters by minimizing the connection strength between groups while normalizing by each group’s total connectivity. This avoids trivial partitions that isolate small sets of points and instead favors balanced, well-separated clusters. It matters because it provides the core criterion behind spectral clustering, enabling reliable discovery of non-convex structure in unlabeled data.

Imagine splitting a social network into two friend groups. A bad split would cut through lots of close friendships. A better split would separate people with fewer connections between the groups, while also avoiding tiny, unfair groups. That balance is the idea behind Normalized Cut.

In AI, Normalized Cut is a way to divide data into meaningful groups by looking at how strongly items are connected, like photos, customers, or documents. It tries to separate groups cleanly without isolating just a few items. This matters because real-world data often forms messy, uneven shapes, and simple “draw a line through the middle” methods can miss those natural groupings.