x ER : An Explainable Model for Entity Resolution using an Efficient Solution for the Clique Partitioning Problem (2021)

Abstract: In this paper, we propose a global, self- explainable solution to solve a prominent NLP problem: Entity Resolution (ER). We formu- late ER as a graph partitioning problem. Every mention of a real-world entity is represented by a node in the graph, and the pairwise sim- ilarity 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 Partition- ing Problem (CPP), which is an Integer Pro- gram (IP) to formulate ER as a graph partition- ing 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 combi- nation 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 exper- iments and results of applying this method to ER data sets.

## introduction entity resolution (er) is a prominent nlp problem, also referred to as co-reference resolution, de-duplication and record linkage, depending on the the problem set up. irrespective of the name, the objective is to combine and cluster multiple mentions of a real-world entity from various data sources into their respective real-world entities and remove duplicates. various techniques such as clustering @xcite , @xcite , rule-based methods @xcite , mathematical programming, and combinatorial optimization @xcite have previously been applied to er. in this paper, we formulate and solve er as a graph partitioning problem. representing er as a graph partitioning problem the transformation from the real-world er problem domain to the mathematical integer programming (ip) formulation setup is essential to understand the model's explainable nature and the solution procedure. a node in the graph represents a mention in the er domain. an edge between any two nodes has a weight associated with it, representing the similarity score between the two mentions in consideration. this similarity score indicates the probability that these mentions are associated with the same entity. the goal is to ensure that based on the weights, the nodes are optimally allotted to their respective clusters. from a combinatorial perspective, this problem is known as the clique partitioning problem (cpp). a clique is a complete subgraph in which all its nodes are pairwise connected. the weight of a clique is defined as the sum of all its edges' weights. the objective of this mathematical formulation is to find disjoint cliques in the graph such that the total weight of all the cliques is maximized, which, in the er domain, translates to associating each mention to a single real-world entity with the highest probability association. the constraints in this mathematical formulation enforce that a particular node is mapped to just one clique and ensure that the mentions' transitivity conditions are obeyed. @xcite was one of the earlier papers that formulated er as a graphical problem and @xcite proposed a correlation clustering method for the graphical problem. er was also approached as a graph partitioning problem in @xcite , @xcite , @xcite and the cpp approach outperformed other solution methods for er @xcite , @xcite . @xcite formulated er as cpp, where an incremental graph partitioning approach was applied and solved using a heuristic. lokhande et al. (2020) formulated er as a set packing problem by considering the sets of all possible combinations of mentions and then choosing the best combination, based on the weights of the sets. er has also been approached as a clustering problem. @xcite conducted an extensive survey on the clustering methods that had been applied to the entity resolution problem. von luxburg (2007) solved er as a spectral graph clustering problem, which is based on the graph's laplacian matrix. star clustering @xcite formalizes clustering as graph covering and assigns each node to the highest probabilistic cluster. k-means is also a common technique to solve er as a clustering problem. however, the mathematical formulation based methods come with a guarantee of optimality. furthermore, it is easy to obtain an upper bound to these problems by relaxing the integer constraints. these upper bounds provide a guarantee on any feasible solution. in typical clustering algorithms, the number of clusters to produce in the output needs to be provided upfront, while it is decided by the model intrinsically in the cpp framework. the long convergence times and the iterations pose a disadvantage for them to be used as a solution technique for entity resolution @xcite . moreover, from an explainability perspective, in the formulation-based methods proposed in this paper, the explanation is substantiated with mathematical guarantees, while the clustering-based approaches lack this mathematical precision and the heuristic nature further confounds explainability. ribeiro et al. (2016 since cpp is np-hard @xcite , a novel two-phase solution is proposed, in this paper, to solve cpp optimally. this solution method can be easily accelerated and scaled to handle large-sized datasets. as a part of this two-phased approach, new and creative formulations for the generalized set packing problem are also proposed. the formulations and the approach to obtain the optimal solution provide a mathemati-cal guarantee on the output, and the results are easily interpretable and explainable. the constraints and objective function mathematically support the explanation behind the predicted output. the rest of the paper is organized as follows. in section 2, entity resolution is formulated as cpp. in section 3, explainability and interpretability of this method is discussed. section 4 then introduces the two-phase solution approach proposed for solving the np-hard cpp. sections 5 and 6 go over the computational experiments and the results. ## mathematical formulation of cpp as discussed in section 1, the entity resolution problem is transformed to a graph where each mention is represented by nodes and the weight on an edge between the nodes is the similarity score between the mentions. to obtain the pairwise similarity scores, we use an open-source entity resolution library called dedupe @xcite , which applies blocking and a logistic regression based model to obtain the similarity scores between mentions. see section 5 for more details about this. in this section, the graph partitioning setup is formally represented by a mathematical formulation. let i, j (@xmath0. x ij is a binary variable that denotes whether i, j are associated or co-referent (belong to the same clique). the "traditional" math formulation of cpp is: constraints (2), (3), and (4) are the transitivity constraints enforced among the nodes. these three constraints ensure that if mention a is the same as b and b is the same as c, then it must also be that a is the same as c. the graph is assumed to be directed to avoid duplication of cliques and memory exhaustion. an optimal solution to this problem results in the best possible solution to the er for the given similarity scores. however, due to cubic number of constraints, this particular formulation for cpp, does not scale with the number of nodes. hence, heuristics are prevalent to find an approximate solution to cpp; see section 4 for details. ## model explainability and interpretability before we discuss our solution approaches, the explainable nature of this method is highlighted. the definitions of explainability have been studied in various works @xcite , @xcite . as defined in @xcite and @xcite , understanding the level of explainability of models can be interpreted as outcome explanation problems, where the emphasis lies in understanding the rationale behind the prediction of a specific output or all outputs in general. in this paper, the definitions and categorizations of explanations are based on the definitions in @xcite . two major categorizations of explanations are emphasized. the first is based on the explanation process's target set, and divided into two types: local and global. suppose the explanation is for a particular individual output. in that case, the explanation type is referred to as local. on the other hand, if the explanation is for the whole model in itself, then it is a global explanation. the second categorization is based on the origin of the explanation process. if the explanation is from the prediction process itself, then it belongs to the self explaining or the directly interpretable category @xcite . otherwise, if post prediction processing is required to explain the output, it can be categorized as post-hoc explanation. as seen in @xcite , mathematical formulation based methods have a notion of optimality infused in the problems. the design of nlp problems like er as mathematical formulations ensures that various constraints are met simultaneously, and hence making the output and the prediction process trustworthy and reliable. since the constraints and the objective function are enforced into the mathematical formulation, the explanation behind any output comes directly from the model itself, making it a self-explainable model model. moreover, the explanation behind any output is only dependent on the formulation and not on the output itself. this makes the model globally explainable. therefore, by applying an efficient approach based on mathematical formulations, the solution method discussed in this paper presents an easily interpretable and explainable model for er. ## solution approach for cpp as discussed in section 2, cpp is np-hard. in this paper, an efficient and scalable solution approach is proposed to solve the cpp. the solution procedure is divided into two phases: phase 1 involves finding the maximal cliques in the graph. a maximal clique is a clique that is not a sub-clique of a larger clique @xcite . for phase 2, we propose a novel generalized set packing formulation that not only ensures that each node belongs to a single clique, but it is able to break larger cliques into smaller sub-cliques if necessary. the formulation enables to find the optimal combinations of the cliques, that maximize the weight of the system. the algorithm (phase 1 + phase 2), is referred to as xer (explainable er). ## computational experiments in this section, the xer algorithm's performance is evaluated through experiments on different er datasets. in this paper, two primary data sources considered: benchmarking datasets @xcite and ecb+ @xcite . datasets from both these sources are used to test the algorithm and analyze the algorithm's performance in terms of the f1 scores, solution times and their potential for scalability. different blocking and scoring techniques have been applied to both these datasets, and are discussed in detail. blocking is a pre-processing technique applied to the datasets. the purpose is to eliminate the need to store similarity scores between those pairs of mentions that are extremely unlikely to being associated to the same entity. this increases the sparsity in the graph, making it easier to process the graph and perform computations. blocking and similarity score computation techniques are different for different data sources and are discussed below. @xcite provides benchmark datasets, three of which are used in this paper. ## results the experiments are performed on an intel i5 processor with 8gb ram. the datasets from both sources are preprocessed and converted into graphs given as an input to the xer algorithm. these graphs have mentions as nodes and the pairwise similarity scores as the edges' weight. as shown in the xer algorithm (1), this graph is first passed through phase 1, which is the bron-kerbosch algorithm with pivoting @xcite . this step's output is a set of maximal cliques that are not disjoint and passed on to phase 2 for the set packing step. qsp formulation is modelled using gurobi (gurobi optimization, 2021) and solved optimally. the solution for the z variable from the optimally solved model is used to compute f1 scores. the xer algorithm is applied to all the datasets listed above and is evaluated in terms of f1 scores and computation times, and compared to the other competing algorithms. xer is also compared with the traditional set packing algorithm and the difference in the input sizes between spp and qsp is highlighted through experiments. also, to demonstrate the quality of the xer algorithm, the weights on the edges are replaced with ground truth (gt) values (+1 and -1) instead of similarity scores and tested. this helps in analyzing and confirming the model's consistency and accuracy, irrespective of the method used to compute similarity scores. ## conclusion a graph partitioning based approach is proposed to solve the entity resolution problem and is formulated as a clique partitioning problem. a node in the graph represents each mention, and the objective was to assign nodes to cliques optimally, and each clique represents a real-world entity. this mathematical formulation based model is inherently explainable. since cpp is np-hard, a twophased algorithm called xer is proposed and tested on multiple datasets. phase 1 of xer finds all the graph's maximal cliques, which is much more practical than finding all the cliques in the graph. phase 2 is a generalized set packing formulation and has a much smaller input size than the traditional set packing problem. these contributions help develop a practical and easily parallelizable implementation for xer. xer shows promising performance in terms of accuracy. a gpu accelerated approach for xer is in progress and will provide a scalable and practical model. also, xer can be extended to other applications such as topic modelling, community detection, temporal analysis. we believe this paper will lead the way to more mathematical formulationbased approaches and nlp problems can be solved using such highly explainable models, thus reducing the dependency on black-box models.