Abstract
In this paper, we propose a global, self-explainable solution to solve a prominent NLP problem: Entity Resolution (ER). We formulate ER as a graph partitioning problem. Every mention of a real-world entity is represented by a node in the graph, and the pairwise similarity scores between the mentions are used to associate these nodes to exactly one clique, which represents a real-world entity in the ER domain. In this paper, we use Clique Partitioning Problem (CPP), which is an Integer Program (IP) to formulate ER as a graph partitioning problem and then highlight the explainable nature of this method. Since CPP is NP-Hard, we introduce an efficient solution procedure, the xER algorithm, to solve CPP as a combination of finding maximal cliques in the graph and then performing generalized set packing using a novel formulation. We discuss the advantages of using xER over the traditional methods and provide the computational experiments and results of applying this method to ER data sets.
The Challenge of Entity Resolution
In Natural Language Processing (NLP), Entity Resolution (ER) is the critical task of determining when different text mentions refer to the same real-world entity. For instance, "Harry Potter," "The Boy Who Lived," and "Mr. Potter" must all be linked to a single entity record.
Most modern approaches rely on heuristic clustering or black-box machine learning models. While effective, these methods often lack a guarantee of optimality and offer little transparency regarding why specific links were formed. Mathematically, the most rigorous way to model this is as a Clique Partitioning Problem (CPP): grouping mentions into cliques (where every mention in a group is similar to every other) to maximize total similarity. However, CPP is NP-hard, and traditional solvers struggle to scale as the number of possible cliques grows exponentially with the dataset size.
The xER Methodology
The authors introduce the xER algorithm, a two-phase approach designed to make the rigorous mathematical formulation of ER computationally practical:
- Phase 1: Finding Maximal Cliques: Rather than evaluating every possible combination of mentions, the algorithm identifies "maximal cliques"—the largest possible groups where every node is connected. This is achieved using the Bron-Kerbosch (BK) algorithm.
- Phase 2: Quadratic Set Packing (QSP): This phase represents the paper's core innovation. Traditional set packing requires the "power set" (every possible sub-group) as input, which is computationally prohibitive. The authors developed a Quadratic Set Packing formulation that takes only the maximal cliques and optimally "carves them out" into smaller, disjoint sub-cliques.
By utilizing an Integer Programming (IP) solver like Gurobi, the model ensures the final clusters are the mathematically optimal groupings based on input similarity scores.
Key Insights: Explainability and Efficiency
- Self-Explaining by Design: Unlike post-hoc explanations where a secondary model attempts to interpret a primary one, xER is directly interpretable. The explanation for any link is the mathematical proof: given the similarity scores and transitivity constraints (if A=B and B=C, then A=C), this specific grouping maximizes the global objective.
- Efficiency through Sparsity: By focusing on maximal cliques rather than all possible cliques, the authors drastically reduce complexity. In one test case, the number of all cliques was 17,114, while the number of maximal cliques was only 829—a 20x reduction in the search space.
- The "Noisy Weight" Sensitivity: The model's accuracy is inherently tied to its similarity scores. If the scoring model assigns high similarity to unrelated mentions, the optimizer will still find the "best" solution for those scores, potentially leading to incorrect links.
Experimental Results
The researchers evaluated xER using benchmarking datasets (patent_example, csv_example, and settlements) and the ECB+ Corpus.
- Accuracy: xER achieved F1 scores comparable to or exceeding state-of-the-art methods. On the
settlementsdataset, it reached an F1 of 95.7%. When tested with perfect "Ground Truth" weights, it achieved a 100% F1 score, validating the optimization logic. - Speedup: The efficiency gains were significant. As shown in the performance data, on a graph where a traditional Set Packing Problem (SPP) solver took 99.88 seconds, the xER approach completed the task in just 4.78 seconds.
Limitations and Future Directions
While xER is significantly faster than traditional IP formulations, it still relies on off-the-shelf solvers like Gurobi, which may face challenges with massive datasets containing millions of mentions. Future work is focused on developing GPU-accelerated versions of Phase 1 and a Linearized Set Packing (LSP) version of Phase 2 to further enhance scalability for real-world, large-scale applications.
Summary updated