Clustering is one of the most fundamental tasks in data analysis: given a set of objects, we want to group similar ones together. Traditionally, clustering algorithms like k-means or hierarchical clustering require a numeric notion of distance between points and often ask you to specify the number of clusters in advance.

Correlation clustering takes a different approach. Rather than starting with distances, it starts with pairwise relationships between objects. For every pair of points, we are given a label that says whether they are "similar" (should belong to the same cluster) or "dissimilar" (should be separated). The goal is to find a clustering that agrees with these labels as much as possible.

More formally, imagine we have a graph where each edge is labeled "+" (similar) or "−" (dissimilar). A perfect clustering would put all "+" pairs in the same cluster and all "−" pairs in different clusters. But real data is noisy—conflicting labels are common—so we seek a partition that minimizes the number of disagreements (or equivalently, maximizes the number of agreements).

This makes correlation clustering a very flexible model. It does not require you to pick the number of clusters ahead of time: the "right" number emerges naturally from the data. It can also handle arbitrary similarity information—no need for a metric or Euclidean space.

The Pivot Algorithm: A Simple and Elegant Approach

One of the most famous algorithms for correlation clustering is the Pivot algorithm. Its idea is surprisingly simple:

  1. Pick a random vertex as the "pivot."
  2. Form a cluster consisting of the pivot and all vertices labeled "+" with it.
  3. Remove these vertices from the graph.
  4. Repeat until no vertices remain.

Despite its simplicity, the Pivot algorithm has a beautiful theoretical guarantee: it is a 3-approximation for minimizing disagreements on complete graphs. In other words, the number of disagreements it produces is at most three times the optimal value—an impressive result for such an intuitive procedure.

My Research

My research explores approximation algorithms for correlation clustering, particularly when the number of clusters is fixed (the so-called k-correlation clustering problem). This variant is significantly harder, but also very relevant to practical applications where we know in advance that the data should naturally form a certain number of groups.

I work on developing new algorithms that achieve better guarantees for these problems and analyzing their performance both theoretically and experimentally. A major theme of my work is understanding how we can make algorithms robust in the presence of noisy data and efficient in streaming or online settings where data arrives over time.

How to Start Researching Correlation Clustering

If you are interested in working on correlation clustering, here are a few steps to get started:

1. Read the classic papers

The original formulation:

Bansal, Blum, and Chawla (2004): "Correlation Clustering" – This is the seminal paper that introduced the problem and the Pivot algorithm.

Follow-up work on approximations:

Charikar, Guruswami, and Wirth (2005): "Clustering with Qualitative Information" – Improves approximation ratios and analyzes several variants.

Recent progress:

Giotis and Guruswami (2006): "Correlation Clustering with a Fixed Number of Clusters" – Introduces approximation schemes for the k-clustering variant.

2. Try implementing the Pivot algorithm

It is short and elegant—perfect for building intuition and running experiments on small datasets.

3. Explore open questions

  • How do these algorithms behave on real-world graphs (e.g., social networks)?
  • Can we design faster or more scalable approximation schemes?
  • What happens if the similarity labels are partially missing, noisy, or adversarially corrupted?
  • How do we adapt correlation clustering to streaming, online, or distributed models?

4. Experiment

Generate synthetic data with known cluster structure and compare how different algorithms perform. Many papers provide benchmark datasets you can use.

Why It's Exciting

Correlation clustering is a beautiful example of how theoretical computer science and machine learning meet. It is simple to state, rich in mathematical structure, and directly applicable to real problems like entity resolution, community detection, and deduplication. And because it is NP-hard, there is always room for new insights—whether that means proving tighter approximation guarantees, designing faster algorithms, or exploring entirely new models.