Does normalized cuts need labeled training examples?

The classical graph-partitioning method does not require them, although a system may learn its features or affinities using labeled data.

Is it only for images?

No. It operates on suitable similarity graphs; images are an important application.

Does it always return two groups?

The basic formula describes a bipartition. Recursive or multiway approaches can produce additional groups.

AI Glossary / Computer vision and multimodal AI / Advanced

Normalized cuts

Definition

Normalized cuts is a graph-partitioning approach that groups strongly connected items while penalizing connections broken between groups relative to each group's total connection weight. In computer vision, it can divide an image into regions by treating pixels or larger image elements as graph nodes.

What it means

Imagine an image represented as a network. Two nodes receive a strong connection when the chosen features suggest that they belong together. Features might include color, position or texture. A proposed segmentation separates this network into groups.

Simply minimizing the total weight of broken connections can favor peeling off small, weakly connected pieces. The normalized-cut criterion instead considers the broken weight as a fraction of the connections associated with each side. This changes what counts as an inexpensive separation.

The result still depends on how similarity was defined. A graph that strongly connects visually similar background and foreground regions may produce a grouping that is mathematically reasonable but unsuitable for the intended task. Graph partitioning does not automatically understand object identity.

How it works

For two nonempty groups A and B in an undirected graph with nonnegative weights, let cut(A,B) be the sum of weights connecting one group to the other. Let vol(A) be the sum of all node degrees in A, with degrees computed using the whole graph. Define vol(B) similarly.

The criterion is Ncut(A,B) = cut(A,B)/vol(A) + cut(A,B)/vol(B), assuming positive volumes. Lower values are preferred.

Exactly optimizing the discrete partition is difficult in general. A widely used approach relaxes the discrete assignments, solves an eigenvector problem involving the graph Laplacian and then converts the continuous representation into groups. Recursive splitting or multiway spectral methods can produce more than two regions.

The relaxation and conversion are important: using an eigenvector does not certify that the final discrete partition is the exact global optimum. Graph construction, connectivity and the desired number or stopping rule for groups also affect the outcome.

Three practical examples

An image-segmentation experiment groups neighboring regions using color and spatial relationships, then reviews the resulting boundaries.
A video-analysis study constructs connections using appearance and motion similarity to suggest coherent groups.
A data-analysis team uses a similarity graph when clusters have shapes poorly represented by a single center, while checking whether those graph relationships reflect its real task.

Think of it this way

Think of dividing a transport network into service districts. A good division would break relatively few important routes compared with the total route connections serving each district.

The analogy explains relative connection cost. It does not mean normalized cuts must create equal-sized districts, respect administrative boundaries or find the most useful division for travelers. Those requirements would need their own representation or evaluation.

Worked example

Comparing two cuts in a four-node graph

Consider four nodes A, B, C and D with only three undirected edges: A - B has weight 5, B - C has weight 1, and C - D has weight 5. The node degrees are therefore 5, 6, 6 and 5.

First split {A,B} from {C,D}. The broken edge has weight 1. Each group's volume is 11, so the normalized-cut score is 1/11 + 1/11 = 2/11, approximately 0.182.

Now isolate A from {B,C,D}. The broken weight is 5. The volumes are 5 and 17, giving 5/5 + 5/17, approximately 1.294. The first partition has the lower score among these two candidates.

Notice that an internal edge contributes to the degree sum at both of its endpoints. For {A,B}, the weight-5 internal edge contributes 10 to the volume, while the edge from B to C contributes another 1. Counting only distinct edges incident to the group would give the wrong denominator.

This small example makes the criterion inspectable. The weights are illustrative; real segments need not have equal sizes.

Illustrative case study

Illustrative case study - fictional

A fictional catalog team experiments with separating products from simple backgrounds. It constructs a graph whose connections reflect nearby regions with similar colors. Normalized cuts gives useful-looking divisions on some images, but a pale product on a pale background often remains grouped with its surroundings.

The team inspects those examples and realizes that its similarity definition lacks useful boundary information. It revises the experiment and compares the new regions against manually reviewed examples.

The lesson is that a better optimization procedure cannot compensate for every missing distinction in the graph. The case describes a possible investigation, not a validated commercial segmentation system.

Common misconceptions and mistakes

Normalized cut is not the same objective as ordinary minimum cut; the denominators change the preference between partitions.
The normalization does not require equal numbers of nodes in each group. It uses connection volume.
A low objective value does not prove that a segment corresponds to a meaningful object.
Spectral relaxation is not a general guarantee of the exact best discrete partition.
Edge weights should represent the intended affinities. Feeding arbitrary distances directly into an affinity interpretation can reverse the desired meaning.

Business use

Businesses can use normalized cuts as a conceptual and practical basis for grouping images or other relationship-based data. It is particularly useful for making the role of similarity explicit.

A responsible evaluation compares resulting groups with the intended operation: selecting product regions, proposing annotation boundaries or organizing related items. Record graph features, weight construction and partition settings. Where results will be corrected by people, measure the correction effort as well as the numerical objective; a mathematically tidy division may still be inconvenient to use.

Check your understanding

In the example, why is the volume of {A,B} equal to 11 rather than 6?

Answer: Volume sums node degrees. The internal weight-5 edge contributes once at A and once at B, and the cross-group edge contributes 1.

Related terms

Spectral clustering
Image segmentation
Superpixels
graph Laplacian
affinity matrix
minimum cut
superpixel

Learn next

Draw the four-node example and change the middle edge's weight. Recalculate the candidate scores. Then inspect a small image graph to distinguish choices made by the similarity design from choices made by the partitioning algorithm.

Sources

Sources: Shi and Malik, Normalized Cuts and Image Segmentation (2000): https://people.eecs.berkeley.edu/~malik/papers/SM-ncut.pdf ; scikit-learn SpectralClustering documentation: https://scikit-learn.org/stable/modules/generated/sklearn.cluster.SpectralClustering.html . The original criterion and relaxation discussion, plus relevant implementation description, were reviewed.

Previous: Normalized cross-correlation (NCC) Next: Normalized Discounted Cumulative Gain