Entity Resolution (ER) is the task of finding records that refer to the same real-world entity, which are called matches. ER is a fundamental pre-processing step when dealing with dirty and/or heterogeneous datasets; however, it can be very time-consuming when employing complex machine learning models to detect matches, as state-of-the-art ER methods do. Thus, when time is a critical component and having a partial ER result is better than having no result at all, progressive ER methods are employed to try to maximize the number of detected matches as a function of time. In this paper, we study how to perform progressive ER by exploiting graph embeddings. The basic idea is to represent candidate matches in a graph: each node is a record and each edge is a possible comparison to check-we build that on top of a well-known, established graph-based ER framework. We experimentally show that our method performs better than existing state-of-the-art progressive ER methods on real-world benchmark datasets.
Entity Resolution (ER) is the task of identifying records (a.k.a. profiles) that refer to the same
real-world entity in datasets [
The naïve solution of comparing each and every pair of records to determine whether they belong to the same entity (i.e., they match) has a quadratic complexity; hence, it is impractical with large datasets. To mitigate this problem, blocking is typically employed to partition the considered data into blocks and to perform the all-pairs comparison only within each block. Blocking is usually achieved by extracting from each record one or more blocking keys that are used to index that record into specific blocks. For instance, given a dataset with client contacts, a simple blocking strategy could be to index together records that share some attribute values, such as the client name or the phone number.
Yet, a client may use a nickname (e.g., William/Bill) and have multiple phone numbers (e.g., home/work). Thus, to define efective blocking key extraction strategies that discard many e1 CMaotdeeglo:rAyp:pSlmeaiPrthpohnoenXe e4 tdyepsec:r.S: asmmsaurtnpgho2n0e e2 gmrooduepl::sSmaamrstpuhnognSe20 e5 sHmuaawrtpeihPon2e0 e3 tnyapme:e:smiPahrotnpeho1n0e producer: Apple
e6 fSoaldmasbulengphFoonlde
(a)
superfluous comparisons while correctly indexing together matching records is a hard task.
This task becomes even harder when considering heterogeneous datasets, since aligning the
attributes can be prohibitive when dealing with Web data or data lakes. In such a scenario, the
state-of-the-art solution is to employ meta-blocking [
The basic idea of meta-blocking is to extract schema-agnostic blocking keys (i.e., by considering the record as a unique, concatenated snippet of text, discarding its schema) and then to restructure the yielded blocks to improve the eficiency. The former step allows to deal with schema heterogeneity and to achieve a high level of recall. For instance, by employing Token Blocking, each token appearing in a record (regardless of the attribute in which it appears) is used as a blocking key. Thus, on one hand, there is no need to perform schema alignment beforehand if the data is messy (e.g., in an e-commerce dataset, sony appears in the Brand attribute in a record and in the Title attribute in another one); on the other hand, the number of generated blocking keys (hence comparisons) can be very high, slowing the process and yielding low precision. To increase precision, in the meta-blocking step, the blocks are restructured by representing them in the following way: each record is represented as a node in a graph, called blocking graph; an edge is present between two nodes if the two corresponding records appear together in at least one block (i.e., they share at least one blocking key); each edge is weighted according to the number and the characteristics (e.g., the size) of the blocks that the two adjacent nodes share; finally, a graph-pruning algorithm is applied and the remaining edges represent the final candidate pairs of matching records.
Figure 1a reports an example of a record collection gathered from diferent data sources. The schema of each record may be diferent from the others—a common trait of data collected from the Web. Token Blocking is applied to the record collection: each token in the record is a blocking key, which means that the record is indexed in a block with all the records in which that token appears. Without performing schema alignment, the only viable way is to consider each blocking key (i.e., token) regardless of the attribute in which it appears.
The result is the blocking collection of Figure 1b. On one hand, in these blocks, all records are indexed together in at least one block—in other words, all matching pairs will be checked. On the other hand, many comparisons are superfluous, since this strategy does not filter many pairs; further, many pairs appear multiple times across the blocks (for records that share multiple tokens). At the end of the day, the high capability of such a schema-agnostic blocking strategy to find all matching pairs is traded for a higher number of comparisons to perform, which is a burden for the ER process.
A solution is to employ meta-blocking. All the records of Figure 1b are represented as nodes in a graph and the edges of the graph are weighted accordingly to the co-occurrences in the blocks of their adjacent nodes (Figure 1c). This blocking graph is processed with graph pruning algorithms to retain only promising edges (i.e., comparisons). Figure 1d reports as an example the output of a pruning algorithm that takes as a threshold for each node the average of the weights of its edges, then applies that local threshold to each node neighborhood.
Such an approach has two main advantages: the first is that all redundant comparisons are inherently removed (we can have only one edge between two nodes); the second is that shifting to a graph representation (from blocks) allows to implement progressive strategies (as explained below) and exploit the findings of the research community about graph embedding, which is explored in this work.
Progressive Entity Resolution with Meta-blocking. Meta-blocking was designed to support
batch ER [
In particular, the best performing method is Progressive Profile Scheduling , denoted as PPS. The basic idea of PPS is to store all top-1 comparisons per node in the blocking graph in a heap data structure. Then, PPS attractively emits the comparisons until the heap is empty. While populating the main heap of comparisons mentioned above, PPS also maintains an auxiliary heap where it inserts all the nodes of the graph, weighted accordingly to an aggregate measure of their adjacent edges. For instance, a node has a weight equal to the average of the weights of its adjacent edges in the blocking graph. This auxiliary heap is employed to attractively retrieve at a time the node that is most likely to have a match. Then, while the primary heap emits comparisons, a parallel process can generate new comparisons from the current node extracted from the auxiliary heap and fill the primary one. In this way, the memory footprint of the algorithm is (), where is the number of records.
Our Contribution. Our intuition is to represent each node of the blocking graph as an
embedding by exploiting recent advances in the field [
In Section 2, we provide the notation, the definition of the problem, and the basic concepts behind graph embedding, which are employed to present our method in Section 3. The experimental demonstration of the eficacy of our method is reported in Section 4, which shows how our method outperforms the state-of-the-art graph-based PPS method. Further related work and conclusions (which also introduce future directions for this research) are presented in Sections 5 and 6, respectively.
In a dirty dataset , two records that refer to the same real-world entity are defined as matching
records; we denote this with ≡ . As other state-of-the-art ER frameworks [
In the first phase, blocking is applied and a set ℬ of possibly overlapping clusters of records (called blocks) is generated. All the pairs of records appearing within a block are candidate matches, denoted with ⟨, ⟩.
In the second phase, a binary matching function is applied to all candidate pairs entailed
by ℬ: the matching function : × → { true, false} takes as input two records and
returns true in case they match, false otherwise. The matching function can be a trained
machine/deep learning model [
In graph-based meta-blocking (meta-blocking for simplicity), a collection of blocks ℬ is
represented by a weighted graph ℬ{ℬ, ℬ, ℬ} called blocking graph. is the set of nodes
representing all records ∈ . An edge between two records exists if they appear together in at
least one block; thus, = { : ∃, ∈ | |ℬ | > 0} is the set of edges, with ℬ = ℬ ∩ ℬ ,
where ℬ and ℬ are the sets of blocks containing and respectively. ℬ is the set of edge
weights. Meta-blocking tries to capture the matching likelihood of two records in the weight of
the edge that connects them. For instance, Block Co-occurrence Frequency (CBS) [
Then, in order to keep only the most promising edges, we can apply suitable edge-pruning strategies. In this way, after this pruning step, each connected pair of nodes forms a new block of the restructured blocking collection.
Meta-blocking can operate by keeping all the candidate comparisons that are weighted above a certain threshold or in a top-k fashion. We call the first case Weighted Pruning, while Cardinality Pruning the latter. The weight threshold, or the for the top-k approach, can be defined at local level (i.e., for each record/node in the graph) or at global level (i.e., for all the edges in the graph). Hence, the combination of those strategies yields the following pruning strategies: (i) Weighted Edge Pruning, where edges with a weight lower than the given threshold are pruned; (ii) Cardinality Edge Pruning, where edges are sorted in descending order with respect to their weights, and then only the first are kept; (iii) Weighted Node Pruning, which considers in turn each node and its adjacent edges, and edges with a weight lower than the given threshold are pruned; (iv) Cardinality Node Pruning, which similarly to the previous one is node-centric, but where a cardinality threshold is used instead of a weight threshold.
Finally, the state-of-the-art progressive ER method based on the blocking graph [
A limitation of the existing blocking-graph-based methods is that for each comparison likelihood is estimated by analyzing only the two adjacent nodes that its corresponding edge connects. Thus, for instance, if a set of nodes is part of a clique, this information is not captured just by looking at two nodes at a time. Generally, graph patterns that involve more than two nodes are not captured. Our intuition is that such an information could be exploited. Yet, we do not want to count triangles, cliques of unknown size, etc. The main reasons are the following: firstly, it would be computationally expensive; secondly, we do not know which structure could be useful; ifnally, it would be dificult to take into account all information—e.g., should we count the cliques? Should we assign weights to them? Should we also give importance to quasi-cliques?
An efective solution is to exploit node embeddings [
The basic idea is to measure somehow the similarity between two nodes in the network and
compare it to the similarity in a vector space (the embedding space). In particular, we focus
on unsupervised approaches based on random walks. These methods use a walk approach to
generate (sample) network neighborhoods for nodes. For every node, they generate its network
neighborhood by choosing in some way (e.g., randomly following the edges) the next node of
the walk, until a certain number of steps (the walk sampling) is reached. This iterative process
associates nodes that appear in a path together since they are considered more similar. Then,
to compute the representative vector embeddings, the nodes and their co-occurrences in the
random paths are given as an input to a shallow two-layers neural network, which extracts the
vector embedding for each node as in the skip-gram model [
Once that the vector embeddings have been generated for all the nodes, we employ LSH to build bands of decreasingly similar pairs of nodes. Each band can be dynamically computed; thus, for instance, we start by considering pairs with a cosine similarity greater than 0.9 (i.e., between 1 and 0.9). Then, in the second iteration, we consider pairs with a similarity greater than 0.8 and remove from that set the pairs already considered in the first iteration, and so forth—for lower similarly thresholds.
When considering each level, we actually compute the similarity of each candidate pair and insert it in a heap. Then, we start the emission of the pairs in non-increasing weight order.
Hardware and Software. All experiments were performed on a machine equipped with four
Intel Xeon E5-2697 2.40 GHz (72 cores), 216 GB of RAM, running Ubuntu 18.04. We employed
the SparkER library [
Measures. We employ recall and precision, defined as follows: = #{matching pairs indexed in blocks} #{existing matching pairs} = #{matching pairs indexed in blocks} #{pairs indexed in blocks} and their harmonic mean (i.e., F-score) in order to refer to the overall performance of a blocking strategy—with the assumption that enough time is given to complete the entire ER process. Instead, to assess the progressiveness, we plot the recall as a function of the comparisons yielded by a progressive method.
Datasets. Table 1 lists the 6 real-world datasets employed in our experiments: || stands
for the number of records in a data source, |ℳ| for the number of matching pairs, || for the
number of candidate pairs yielded by schema-agnostic Token Blocking [
Algorithms and baseline. We rely on HARP [
As a baseline, we employed PPS [
Results. Figure 2 reports the progressive recall of the considered methods: our proposal based on HARP and the baseline (i.e., PPS). The ideal method, i.e., the method that ideally emits only matching pairs, is depicted with a red, dashed line.
On ScholarDblp (Figure 2b), HARP has a steeper recall curve than PPS after the recall reaches 0.8 (they perform basically the same before that). On TmdbTvdb (Figure 2f), HARP has 1https://github.com/GTmac/HARP 0 1.0 llca0.5 e R 0.0 0 llca0.5 e R 0.0 0
DblpAcm
HARP(deepwalk)
HARP(n2v) scholarDblp
PPS
a steeper recall curve than PPS only when employing DeepWalk [
As for the runtime, HARP is between 3 and 10 times slower that PPS. Yet, this is typically
not a limiting problem: the entity matching functions employed in real-world scenarios, based
on machine/deep learning models [
A plethora of approaches and algorithms have been proposed for the problem of Entity
Resolution (ER) [
Scaling ER. Schema-agnostic blocking [
By employing the well-known blocking graph framework for representing candidate pairs in an Entity Resolution (ER) task, we devised a method that allows to prioritize those candidates. We show how to exploit graph embeddings to capture hidden patterns in the graph, which can be a good hint for detecting matches. The method we propose can be employed when resources and/or time are limited to yield an approximate ER, since it has been shown to always achieve the same or even a better performance than PPS on real-world datasets.
Finally, we are currently working on a framework to unify the blocking and matching phases by exploiting graph embeddings. This work is the first step to explore that research direction.