Semi-supervised clustering for de-duplication

Shrinu Kushagra, Shai Ben-David, Ihab Ilyas

TL;DR

Data de-duplication can be elegantly modeled as correlation clustering, but even when your similarity metric is "promised" to be highly accurate, the problem remains fundamentally NP-Hard. This paper proves that sub-linear human intervention cannot break this hardness barrier, but demonstrates that restricting the search space to a specific class of clusterings yields a semi-supervised approach with provable success guarantees.

What Problem Does This Paper Address?

Data de-duplication—identifying multiple database records that refer to the same real-world entity—is a massive headache in data cleaning. Think of merging patient records across different clinics or removing duplicate papers in Google Scholar.

Because the number of true entities (clusters) is unknown upfront, standard clustering tools struggle. Furthermore, standard machine learning classification fails because the data is incredibly skewed: if you pick two random records, they are almost certainly not duplicates, leading to a trivial "all different" classifier that has low error but zero utility.

To solve this, researchers often use correlation clustering, which balances minimizing false positives and false negatives (correlation loss). However, finding the absolute optimal correlation clustering is NP-Hard. This paper investigates whether two common real-world advantages can break this hardness:

  1. The Promise: Having a similarity metric that is already quite accurate (an "informative metric").
  2. The Oracle: Having access to human supervision (an oracle) that can definitively tell you if two records match.

Methods

The authors analyze the problem through two frameworks:

  1. Promise Correlation Clustering (PCC): They formalize a setting where the input graph's edges are "close" to the ground truth clustering. To test its complexity, they use a mathematical reduction from the Exact Cover by 3-Sets (X3C) problem, building a specialized graph gadget to prove hardness.
  2. Restricted Correlation Clustering (RCC): Since the general problem is intractable, they propose restricting the algorithm to choose the best clustering from a predefined, finite class $\mathcal{F}$ (such as the prunings of a hierarchical clustering tree).

For the restricted version, they design a semi-supervised active learning strategy using two distinct sampling procedures:

  • $\mathcal{P}_0$ (Negative Pairs): Uniformly samples pairs from the dataset. Because duplicate pairs are rare, random sampling naturally yields non-duplicate (negative) pairs efficiently.
  • $\mathcal{P}_{11}$ (Positive Pairs): Uses the informative metric to construct a neighborhood graph, sampling pairs that are close to each other to efficiently find actual duplicates (positive pairs) without searching for a needle in a haystack.

An Empirical Risk Minimization (ERM) algorithm then evaluates the clusterings in $\mathcal{F}$ against these samples to pick the one with the minimum estimated loss.

Datasets

None used. This paper is entirely theoretical and focuses on proving computational complexity bounds and algorithmic guarantees rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Good Intuition, Bad Complexity: Intuitively, if a similarity metric is already excellent, tweaking it into a perfect clustering should be easy. The authors prove this intuition wrong: even under a strong accuracy promise, the problem remains NP-Hard.
  • Humans Don't Scale (Mathematically): Introducing a human oracle to answer "are these two records the same?" only helps if you ask a linear number of queries ($\Omega(n)$). If you are limited to sub-linear queries ($o(n)$), the problem remains NP-Hard under the Exponential Time Hypothesis (ETH).
  • The Power of Restriction: The "aha moment" is that while you can't find the globally optimal clustering, you can find the best clustering within a restricted family (like a hierarchical tree) using a very small, practical number of human queries, provided that family has a bounded VC-dimension.

Key Results

  • Hardness of PCC: The authors prove that finding the optimal solution for Promise Correlation Clustering is NP-Hard for any maximum cluster size $M \ge 3$.
The graph gadget used to reduce X3C to the Promise Correlation Clustering problem.
  • Query Complexity Lower Bound: Under the Exponential Time Hypothesis, any polynomial-time algorithm must make at least $\Omega(|X|)$ queries to a same-cluster oracle to solve the promise version.
  • RCC Success Guarantees: The proposed ERM algorithm guarantees that the correlation loss of the chosen clustering $\hat{C}$ is bounded close to the optimal clustering within that class: $$L_{C^*}(\hat{C}) \le \min_{C \in \mathcal{F}} L_{C^*}(C) + 3\alpha + \epsilon$$ This is achievable with high probability using a sample size that scales with the VC-dimension of the class $\mathcal{F}$.

  • VC-Dimension Bounds: They prove that for a finite list of $s$ clusterings, the VC-dimension is bounded by $o(\log s)$, making it highly scalable. They also provide bounds for hierarchical clustering trees.

An example of a hierarchical clustering tree used to define a restricted class of clusterings.

Limitations and Future Work

The primary limitation is that the framework relies on a perfect, noiseless oracle (a human who never makes a mistake). In real-world crowdsourcing or expert review, human annotators frequently provide noisy or contradictory labels. Additionally, the algorithm assumes prior knowledge of the parameters ($\alpha, \beta$) of the informative metric to optimize the sampling bounds.

An obvious next step for future work is extending this framework to handle noisy oracles and evaluating the restricted active sampling algorithm on real-world dirty databases.

Summary updated

Abstract

Data de-duplication is the task of detecting multiple records that correspond to the same real-world entity in a database. In this work, we view de-duplication as a clustering problem where the goal is to put records corresponding to the same physical entity in the same cluster and putting records corresponding to different physical entities into different clusters. We introduce a framework which we call promise correlation clustering. Given a complete graph $G$ with the edges labelled $0$ and $1$, the goal is to find a clustering that minimizes the number of $0$ edges within a cluster plus the number of $1$ edges across different clusters (or correlation loss). The optimal clustering can also be viewed as a complete graph $G^*$ with edges corresponding to points in the same cluster being labelled $0$ and other edges being labelled $1$. Under the promise that the edge difference between $G$ and $G^*$ is "small", we prove that finding the optimal clustering (or $G^*$) is still NP-Hard. [Ashtiani et. al, 2016] introduced the framework of semi-supervised clustering, where the learning algorithm has access to an oracle, which answers whether two points belong to the same or different clusters. We further prove that even with access to a same-cluster oracle, the promise version is NP-Hard as long as the number queries to the oracle is not too large ($o(n)$ where $n$ is the number of vertices). Given these negative results, we consider a restricted version of correlation clustering. As before, the goal is to find a clustering that minimizes the correlation loss. However, we restrict ourselves to a given class $\mathcal F$ of clusterings. We offer a semi-supervised algorithmic approach to solve the restricted variant with success guarantees.
BibTeX
@inproceedings{kushagra2019semi,
  author = {Shrinu Kushagra and Shai Ben-David and Ihab Ilyas},
  title = {{Semi-supervised clustering for de-duplication}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
}
Figure