AI Glossary / AI and machine learning / Advanced

Correlation clustering

Definition

Correlation clustering groups items using pairwise judgments of similarity and difference, seeking a partition that agrees with those judgments as much as possible. In the classic formulation, positive links favor grouping items together and negative links favor separating them.

What it means

A system may have evidence about pairs without a convenient coordinate representation for each item. For example, a matching process may judge two records likely to describe the same entity. Those pairwise judgments can disagree with one another.

Correlation clustering turns the collection of local judgments into a globally consistent partition. It balances positive links cut between groups against negative links left within groups.

The name does not mean ordinary clustering of a Pearson correlation matrix, although correlation-derived information can be used in some applications. Here it names a specific optimization problem. In its classic form, the number of groups need not be fixed beforehand.

How it works

Items become vertices in a graph, with edges representing similar or different judgments. The objective can minimize disagreements or maximize agreements, with weighted variants reflecting different strengths of evidence.

The difficulty is that pairwise preferences may be impossible to satisfy simultaneously. An algorithm must choose a partition that makes a suitable compromise.

Practical methods use exact or approximate optimization depending on scale and formulation. The output quality depends on the pairwise evidence, edge weights and objective, so an elegant partition cannot repair systematically wrong matching judgments.

Three practical examples

• A record-linkage project combines pairwise same-entity predictions into groups of records.
• A document team organizes items using a mixture of similarity and explicit difference evidence.
• A graph-analysis study seeks groups consistent with positive and negative relationships under a clearly defined interpretation.

Think of it this way

Think of organizing photographs when sticky notes say “same event” or “different event” for selected pairs. Some notes may conflict, so the organizer must resolve the whole arrangement.

The analogy has limits. The algorithm does not know which note is trustworthy unless the model supplies that information. Its objective measures agreement with encoded evidence, not necessarily agreement with reality.

Worked example

A triangle of conflicting evidence

Consider three fictional records, A, B and C. The pair A-B has a positive link, B-C has a positive link and A-C has a negative link. With equal weights, no ordinary partition satisfies all three.

Putting all three together satisfies the two positive links but violates the negative one: one disagreement. Putting A and B together and C separately satisfies A-B and A-C but cuts B-C: also one disagreement. Separating all three violates both positive links: two disagreements.

Thus the first two candidate arrangements tie under this simplified objective. Additional evidence or unequal weights could change the preferred solution.

The example shows why a pairwise classifier's outputs cannot always be treated as independent final decisions. Once records are placed into disjoint groups, membership has transitive consequences, and the full pattern of evidence matters.

Illustrative case study

A fictional supplier-data team uses pairwise matching scores to consolidate records. Several abbreviations create a chain of positive matches linking two genuinely different businesses.

The team frames the problem with both positive and negative evidence and reviews the resulting disagreements. A verified company identifier supplies stronger separation evidence than a weak name resemblance.

Reviewers inspect uncertain groups before merging operational records. The clustering is a decision aid, while the source records and match evidence remain available. The case illustrates why global grouping and local similarity scoring should be evaluated separately.

Common misconceptions and mistakes

• Assuming correlation clustering simply computes statistical correlations: the classic problem uses signed pairwise relationships.
• Treating every positive link as an unquestionable must-link: the optimization may need to violate some evidence.
• Ignoring inconsistent triangles: pairwise predictions may not form a valid partition directly.
• Calling the chosen partition factual truth: it is the best or approximate solution under the supplied evidence and objective.

Business use

The approach is relevant when a business has meaningful pairwise judgments but needs complete groups, especially in record organization and entity-resolution research.

Ask how similarities became positive or negative evidence and how weights were calibrated. Examine the cost of incorrect merges separately from missed merges. Preserve uncertain groups for review and avoid making irreversible record changes solely because an optimization returned a clean partition. The quality of the original comparisons remains central.

People also ask

Must the number of clusters be specified?

The classic formulation does not require a fixed number, though variants may add constraints.

Can links have different weights?

Yes. Weighted formulations express different disagreement costs.

Can every pairwise judgment be satisfied?

Not always. Conflicting relationships can make some disagreement unavoidable.

Check your understanding

A-B and B-C are positive links, while A-C is negative. Can all three be satisfied in a disjoint clustering?

Answer: No. If A shares a cluster with B and B with C, A also shares it with C. At least one judgment must be violated or reconsidered.

Related terms

• Graph partitioning
• Constrained clustering
• signed graph
• entity resolution
• pairwise similarity

Learn next

Read entity resolution. Draw a small signed graph of candidate matches and identify conflicting triangles before converting pairwise decisions into record groups.

More in AI and machine learning

• Convergence - Convergence is the point in training when a model stops improving meaningfully, when further rounds of adjustment change so little that continuing adds...
• Convex clustering - Convex clustering is a clustering method that poses the grouping task as a single smooth optimization problem with one best answer, avoiding the...
• Cooperative coevolution - Cooperative coevolution is an evolutionary optimization approach in which different populations evolve parts of a solution and are evaluated through their...
• Correspondence analysis - Correspondence analysis is an exploratory method for studying relationships in a table of nonnegative counts, especially a contingency table.
• Cost-sensitive machine learning - Cost-sensitive machine learning accounts for the fact that different prediction errors or actions can have different consequences.
• Count sketch - Count sketch is a compact probabilistic data structure for estimating item frequencies in a data stream.

Sources

Bansal, Blum and Chawla, Correlation Clustering: https://www.cs.cmu.edu/~shuchi/papers/clusteringfull.pdf. Publication: https://doi.org/10.1023/B:MACH.0000033116.57574.95. The abstract and introduction were checked for signed-edge objectives, unconstrained cluster count, weighted evidence and conflicting triangles. Examples and disagreement counts are original.

Previous: Correlation Next: Correlation coefficient