Semi-supervised clustering for de-duplication

Shrinu Kushagra, Shai Ben-David, Ihab F. Ilyas

Abstract

De-duplication, the task of identifying multiple records referring to the same real-world entity, is a fundamental challenge in data cleaning. This paper demonstrates that even with high-quality similarity metrics and access to a human expert (oracle), finding the optimal clustering is NP-Hard. To address this, the authors propose a semi-supervised framework, Restricted Correlation Clustering (RCC), which utilizes informative metrics and clever sampling to minimize oracle queries while providing strong theoretical guarantees.

Introduction

Record de-duplication is often more complex than standard clustering tasks due to three primary factors:

  1. Unknown Cluster Count ($k$): The number of unique entities is typically unknown a priori.
  2. Lack of Geometric Structure: Records (e.g., names, addresses) often lack a natural vector space or convex properties.
  3. Extreme Class Imbalance: In large databases, the vast majority of record pairs are non-duplicates, making standard supervised learning prone to high accuracy with zero utility.

The authors frame this as a Correlation Clustering problem, aiming to minimize disagreements between a similarity graph and the final clustering. They specifically explore whether a "promise"—the assumption that the input graph is already near-optimal—makes the problem tractable.

Theoretical Hardness

The paper introduces Promise Correlation Clustering (PCC) to test if a high-quality initial graph simplifies the search for the optimal clustering. Through reductions from the X3C problem and the Exponential Time Hypothesis, the authors prove that the problem remains NP-Hard even under this promise.

Figure 2: The general structure of the graph construction used in the NP-hardness reduction, illustrating the arrangement of blocks $B_1, \dots, B_t$.

Furthermore, they establish that any polynomial-time algorithm requires at least $\Omega(n)$ queries to a human oracle to find the optimal clustering, proving that human intervention is not a "magic bullet" for computational hardness.

Figure 3: A detailed view of the block gadgets $B_1$ and $B_2$ used within the hardness proof construction.

Restricted Correlation Clustering (RCC)

To bypass the NP-Hardness of the general problem, the authors propose Restricted Correlation Clustering (RCC). This framework restricts the search space to a finite class of clusterings $\mathcal{F}$, such as all possible prunings of a hierarchical clustering tree.

The Core Algorithm

The RCC approach employs a semi-supervised strategy:

  • Sampling Negative Pairs ($P_0$): Uniform sampling effectively identifies "different-cluster" pairs due to the natural class imbalance.
  • Sampling Positive Pairs ($P_1$): To find "same-cluster" pairs efficiently, the authors use an informative metric. This metric prioritizes pairs that are likely to be duplicates, acting as a filter to focus oracle queries where they are most needed.
  • Empirical Risk Minimization (ERM): The sampled pairs are used to estimate the loss for every clustering in $\mathcal{F}$, selecting the one that minimizes the total disagreement.

Key Insights and Results

  • Informative Metrics as Filters: Rather than using a similarity metric to decide the final clustering, it is used to prioritize human queries, solving the "needle in a haystack" problem.
  • VC-Dimension for Clustering: The authors adapt VC-Dimension to measure the complexity of clustering classes. They show that for classes like hierarchical trees, the search is statistically efficient.
  • Success Guarantees: The ERM-based algorithm is proven to find a clustering with a loss close to the best possible in $\mathcal{F}$, with sample complexity scaling with the VC-Dimension and desired accuracy ($\epsilon$).

Conclusion and Future Work

While the RCC framework provides a robust theoretical path forward, it remains dependent on the quality of the restricted class $\mathcal{F}$. If the ground truth is not well-represented within $\mathcal{F}$ (e.g., a poorly constructed hierarchy), the algorithm can only find the best of the "bad" options. Future work may involve methods for constructing better initial classes $\mathcal{F}$ or refining the requirements for informative metrics in highly noisy environments.

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 F. Ilyas},
  title = {{Semi-supervised clustering for de-duplication}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
}
Figure