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:
- Unknown Cluster Count ($k$): The number of unique entities is typically unknown a priori.
- Lack of Geometric Structure: Records (e.g., names, addresses) often lack a natural vector space or convex properties.
- 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.
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.
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