# Bipartite Graph Matching Algorithms for Clean-Clean
Entity Resolution: An Empirical Evaluation

George Papadakis1, Vasilis Efthymiou2, Emmanouil Thanos3, Oktie Hassanzadeh4
1National and Kapodistrian University of Athens, Greece<EMAIL_ADDRESS>
2Foundation for Research and Technology - Hellas, Greece<EMAIL_ADDRESS>
3KU Leuven, Belgium<EMAIL_ADDRESS>
4IBM Research, USA<EMAIL_ADDRESS>
###### Abstract.

Entity Resolution (ER) is the task of finding records that refer to the same
real-world entities. A common scenario is when entities across two clean
sources need to be resolved, which we refer to as Clean-Clean ER. In this
paper, we perform an extensive empirical evaluation of 8 bipartite graph
matching algorithms that take in as input a bipartite similarity graph and
provide as output a set of matched entities. We consider a wide range of
matching algorithms, including algorithms that have not previously been
applied to ER, or have been evaluated only in other ER settings. We assess the
relative performance of the algorithms with respect to accuracy and time
efficiency over 10 established, real datasets, from which we extract $>$700
different similarity graphs. Our results provide insights into the relative
performance of these algorithms and guidelines for choosing the best one,
depending on the data at hand.

##  1\. Introduction

Entity Resolution is a challenging, yet well-studied problem in data
integration (Christen, 2012; Köpcke et al., 2010). A common scenario is Clean-
Clean ER (CCER) (Christophides et al., 2021), where the two data sources to be
integrated are both clean (i.e., duplicate-free), or are cleaned using single-
source entity resolution frameworks. Example applications include Master Data
Management (Otto and Reichert, 2010), where a new clean source needs to be
integrated into the clean reference data, and Knowledge Graph matching and
completion (Gutierrez and Sequeda, 2020; Saeedi et al., 2018a), where an
existing clean knowledge base needs to be augmented with an external source.

We focus on methods that take advantage of a large body of work on blocking
and matching algorithms, which efficiently compare the entities across two
sources and provide as output pairs of entities along with a confidence or
similarity score (Dong and Srivastava, 2015; Christophides et al., 2021). The
output can then be used to decide which pairs should be matched. The simplest
approach is specifying as duplicates all the pairs with a score higher than a
given threshold. Choosing a single threshold fails to address the issue that
in most cases the similarity scores vary significantly depending on the
characteristics of the entities. More importantly, for CCER, this approach
does not guarantee that each source entity can be matched with at most one
other entity. If we view the output as a bipartite similarity graph, where the
nodes are entity profiles and the edge weights are the matching scores between
the candidate duplicates, what we need is finding a matching (or independent
edge set (Lovasz and Plummer, [n.d.])) so that each entity from one source is
matched to at most one entity in the other source.

In this paper, we present the results of our thorough evaluation of efficient
bipartite graph matching algorithms for CCER. To the best of our knowledge,
our study is the first to primarily focus on bipartite graph matching
algorithms, examining the relative performance of the algorithms in a variety
of data sets and methods of creating the input similarity graph. Our goal is
to answer the following questions: Which bipartite graph matching algorithm is
the most accurate one, which is the most robust one, and which offers the best
balance between effectiveness and time efficiency? How well do the main
algorithms scale? Which characteristics of the input graphs determine the
absolute and the relative performance of the algorithms? By answering these
questions we intend to facilitate the selection of the best algorithm for the
data at hand.

In summary, we make the following contributions:

$\bullet$ In Section 3, we present an overview of eight efficient bipartite
graph1 matching algorithms along with an analysis of their behavior and
complexity. Some of the algorithms are adaptations of efficient graph
clustering algorithms that have not been applied

$\bullet$ In Section 4, we organize the input of bipartite graph partitioning
algorithms into a taxonomy that is based on the learning-free source of
similarity scores/edge weights.

$\bullet$ We perform an extensive experimental analysis that involves 739
different similarity graphs from 10 established real-world CCER datasets,
whose sizes range from several thousands to hundreds of million edges, as
explained in Section 5.

$\bullet$ In Section 6, we assess the relative performance of the matching
algorithms with respect to effectiveness and time efficiency.

$\bullet$ We have publicly released the implementation of all algorithms as
well as our experimental results.111See https://github.com/scify/JedAIToolkit
for more details.

##  2\. Preliminaries

We assume that an _entity profile_ or simply entity is the description of a
real-world object, provided as a set of attribute-value pairs in some _entity
collection_ $V$. The problem of Entity Resolution (ER) is to identify such
entity profiles (called _matches_ or _duplicates_) that correspond to the same
real-world object, and place them in a common _cluster_ $c$. In other words,
the output of ER, ideally, is a set of clusters $C$, each containing all the
matching profiles that correspond to a single real-world entity.

In this paper, we focus on the case of _Clean-Clean ER_ (CCER), in which we
want to match profiles coming from two clean (i.e., duplicate-free) entity
collections $V_{1}$ and $V_{2}$. This means that the resulting clusters should
contain at most two profiles, one from each collection. _Singular clusters_ ,
corresponding to profiles for which no match has been found, are also
acceptable.

To generate this clustering, a typical CCER pipeline (Christophides et al.,
2021) involves the steps of (i) _(meta-)blocking_ , i.e., indexing steps that
generate _candidate matching pairs_ , this way reducing the otherwise
quadratic search space of matches, (ii) _matching_ , assigning a similarity
score to each candidate pair, and (iii) _bipartite graph matching_ , which
receives the scored candidate pairs and decides which pairs will be placed
together in a cluster. In this work, we evaluate how different methods for the
last step perform, when the previous ones are fixed.

Problem Definition. The task of Bipartite Graph Matching receives as input a
bipartite _similarity graph_ $G=(V_{1},V_{2},E)$, where $V_{1}$ and $V_{2}$
are two clean entity collections, and $E\subseteq V_{1}\times V_{2}$ is the
set of edges with weights in [0,1], corresponding to the similarity scores
between entity profiles of the two collections. Its output comprises a set of
partitions/clusters $C$, with each one containing one node $v_{i}\in V_{1}\cup
V_{2}$ or two nodes $v_{i}\in V_{1}$ and $v_{j}\in V_{2}$ that represent the
same real-world object.

Figure 1(a) shows an example of a bipartite similarity graph, in which node
partitions (entity collections) are labeled as $A$ (in orange) and $B$ (in
blue). The edges connect only nodes from $A$ to $B$ and are associated with a
weight that reflects the similarity (matching likelihood) of the adjacent
nodes. Figures 1(b)–1(d) show three different outputs of CCER, in which nodes
within the same oval (cluster) correspond to matching entities.

Figure 1. Example of processing a similarity graph: (a) the similarity graph
constructed for a pair of clean entity collections ($V_{1}$ in orange and
$V_{2}$ in blue), (b) the resulting clusters after applying CNC, (c) the
resulting partitions/clusters assuming that the approximation algorithms RCA
or BAH retrieved the optimal solution for the maximum weight bipartite
matching or the assignment problem, and (d) the resulting clusters after
applying UMC, BMC or EXC.

Related work. There is a rich body of literature on ER (Christophides et al.,
2021; Christen, 2012). Following the seminal Fellegi-Sunter model for record
linkage (Fellegi and Sunter, 1969), a major focus of prior work has been on
classifying pairs of input records as match, non-match, or potential match.
While even some of the early work on record linkage incorporated a 1-1
matching constraint (Winkler, 2006), the primary focus of prior work,
especially the most recent one, has been on the effectiveness of the
classification task, mainly by leveraging Machine (Konda et al., 2016) and
Deep Learning (Brunner and Stockinger, 2020; Li et al., 2021; Mudgal et al.,
2018).

Inspired by the recent progress and success of prior work on improving the
efficiency of ER with blocking and filtering (Papadakis et al., 2020b), we
target ER frameworks where the output of the matching is used to construct a
similarity graph that needs to be partitioned for the final step of entity
resolution. Hassanzadeh et al. (Hassanzadeh et al., 2009) also target such a
framework, and perform an evaluation of various graph clustering algorithms
for entity resolution. However, they target a scenario where input data sets
are not clean or more than two clean sources are merged into a dirty source
that contains duplicates in itself; as a result, each cluster could contain
more than two records. We refer to this variation of ER as Dirty ER
(Christophides et al., 2021). Some of the bipartite matching algorithms we use
in this paper are adaptations of the graph clustering algorithms used in
(Hassanzadeh et al., 2009) for Dirty ER.

More recent clustering methods for Dirty ER were proposed in
(DBLP:journals/jdiq/DraisbachCN20). After estimating the connected components,
Global Edge Consistency Gain iteratively switches the label of edges so as to
maximize the overall consistency, i.e,. the number of triangles with the same
label in all edges. Maximum Clique Clustering ignores edge weights and
iteratively removes the maximum clique along with its vertices until all nodes
have been assigned to an equivalence cluster. This approach is generalized by
Extended Maximum Clique Clustering, which removes maximal cliques from the
similarity graph and enlarges them by adding edges that are incident to a
minimum portion of their nodes.

Gemmel et al. (Gemmell et al., 2011) present two algorithms for CCER as well
as more algorithms for different ER settings (e.g., one-to-many and many-to-
many). Both algorithms are covered by the clustering algorithms that are
included in our study: the MutualFirstChoice is equivalent to our Exact
clustering, while the Greedy algorithm is equivalent to
UniqueMappingClustering. Finally, the MaxWeight method (Gemmell et al., 2011)
utilises the exact solution of the maximum weight bipartite matching, for
which an efficient heuristic approach is considered in our Best Assignment
Heuristic Clustering.

FAMER (Saeedi et al., 2018a) is a framework that supports multiple matching
and clustering algorithms for multi-source ER. Although it studies some common
clustering algorithms with those explored in this paper (e.g., Connected
Components), our focus on bipartite graphs, which do not support multi-source
settings, makes the direct comparison inapplicable. Note, though, that
adapting FAMER’s top-performing algorithm, i.e., CLIP clustering, to work in a
CCER setting yields an algorithm equivalent to Unique Mapping Clustering.

Wang et al. (Wang et al., 2019) follow a reinforcement learning approach,
based on a Q-learning (Watkins and Dayan, 1992) algorithm, for which a state
is represented by the pair ($|L|,|R|$), where $L\subseteq V_{1},R\subseteq
V_{2}$ are the nodes matched from the two partitions, and the reward is
computed as the sum of the weights of the selected matches. We leave this
algorithm outside the scope of this study, as we consider only learning-free
methods, but we plan to further explore it in our future works.

Kriege et al. (Kriege et al., 2019) present a linear approximation to the
weighted graph matching problem, but for that, they require that the edge
weights are assigned by a tree metric, i.e. a similarity measure that
satisfies a looser version of the triangle inequality. In this work, we
investigate algorithms that are agnostic to such similarity measure
properties, assuming only that the weights are in [0,1], as is the case of
most existing algorithms.

##  3\. Algorithms

We consider algorithms that satisfy the following selection criteria:

  1. (1)

They are crafted for bipartite similarity graphs, which apply exclusively to
CCER. Algorithms for the types of graphs that correspond to Dirty and Multi-
source ER have been examined in (Hassanzadeh et al., 2009) and (Saeedi et al.,
2018a), respectively.

  2. (2)

Their functionality is learning-free in the sense that they do not learn a
pruning model over a set of labelled instances. We only use the ground-truth
of real matches to optimize their internal parameter configuration.

  3. (3)

Their time complexity is not worse than the brute-force approach of ER,
$O(n^{2})$, where $n=|V_{1}\cup V_{2}|$ is the number of nodes in the
bipartite similarity graph $G=(V_{1},V_{2},E)$.

  4. (4)

Their space complexity is $O(n+m)$, where $m=|E|$ is the number of edges in
the given similarity graph.

Table 1. Configuration parameters per algorithm. Algor. |  Similarity Threshold $t$ | Other
---|---|---
$CNC$ | ✓ | $\times$
$RSR$ | ✓ | $\times$
$RCA$ | ✓ | $\times$
$BAH$ | ✓ | maximum search steps (10,000)
maximum run-time per search step (2 min.)
$BMC$ | ✓ | node partition used as basis
$EXC$ | ✓ | $\times$
$KRC$ | ✓ | $\times$
$UMC$ | ✓ | $\times$

Due to the third criterion, we exclude the classic Hungarian algorithm, also
known as the Kuhn-Munkres algorithm (Kuhn and Yaw, 1955), whose time
complexity is cubic, $O(n^{3})$. For the same reason, we exclude the work of
Schwartz et al. (Schwartz et al., 2005) on 1-1 bipartite graph matching with
minimum cumulative weights, which reduces the problem to a minimum cost flow
problem and uses the matching algorithm of Fredman & Tarjan (Fredman and
Tarjan, 1987) to provide an approximate solution in O($n^{2}logn$). Note that
most of the considered algorithms depend on the number of edges $m$ in the
similarity graph, which is equal to $n^{2}$ in the worst case. In practice,
though, its value is determined by the similarity threshold $t$, which is used
by each algorithm to prune all edges with a lower weight. For reasonable
thresholds, $O(n)\leq m\ll O(n^{2})$.

Below, we describe the selected algorithms. Table 1 summarizes their
configuration parameters. Their implementation (in Java) is publicly available
through the JedAI toolkit (Papadakis et al., 2020a).

Connected Components (CNC). This is the simplest algorithm: it discards all
edges with a weight lower than the similarity threshold and then computes the
transitive closure of the pruned similarity graph. In the output, it solely
retains the partitions/clusters that contain two entities – one from each
entity collection. Using a simple depth-first approach, its time complexity is
$O(m)$ (Dasgupta et al., 2008).

Ricochet Sequential Rippling Clustering (RSR). This algorithm is an adaptation
of the homonymous method for Dirty ER in (Hassanzadeh et al., 2009) such that
it exclusively considers clusters with just one entity from each entity
collection. After pruning the edges weighted lower than $t$, RSR sorts all
nodes from both $V_{1}$ and $V_{2}$ in descending order of the average weight
of their adjacent edges. Whenever a new seed is chosen from the sorted list,
the first adjacent vertex that is currently unassigned or is closer to the new
seed than it is to the seed of its current partition is re-assigned to the new
cluster. If a partition is reduced to a singleton after a re-assignment, it is
placed in its nearest single-node cluster. The algorithm stops when all nodes
have been considered. Its time complexity is $O(n\;m)$ (Wijaya and Bressan,
2009).

Row Column Assignment Clustering (RCA). This approach is based on the Row-
Column Scan approximation method in (Kurtzberg, 1962) that solves the
assignment problem. It requires two passes of the similarity graph, with each
pass generating a candidate solution. In the first pass, each entity from
$V_{1}$ creates a new partition, to which the most similar, currently
unassigned entity from $V_{2}$ is assigned. Note that, in principle, any pair
of entities can be assigned to the same partition at this step even if their
similarity is lower than $t$, since the assignment problem assumes that each
vertex from $V_{1}$ is connected to all vertices from $V_{2}$ (any “job” can
be performed by all “men”). The clusters of pairs with similarity less than
$t$ are then discarded. In the second pass, the same procedure is applied to
the entities/nodes of $V_{2}$. The value of each solution is the sum of the
edge weights between the nodes assigned to the same (2-node) partition. The
solution with the highest value is returned as output. Its time complexity is
$O(|V_{1}|\;|V_{2}|)$ (Papadakis et al., 2021).

Best Assignment Heuristic (BAH). This algorithm applies a simple swap-based
random-search algorithm to heuristically solve the maximum weight bipartite
matching problem and uses the resulting solution to create the output
partitions. Initially, each entity from the smaller entity collection is
connected to an entity from the larger one. In each iteration of the search
process, two entities from the larger entity collection are randomly selected
in order to swap their current connections. If the sum of the edge weights of
the new pairs is higher than the previous pairs, the swap is accepted. The
algorithm stops when a maximum number of search steps is reached or when a
maximum run-time has been exceeded. In our case, the run-time limit has been
set to 2 minutes.

Best Match Clustering (BMC). This algorithm is inspired from the Best Match
strategy of (Melnik et al., 2002), which solves the stable marriage problem
(Gale and Shapley, 1962), as simplified in BigMat (Assi et al., 2019). For
each entity of the one entity collection, this algorithm creates a new
partition, in which the most similar, not-yet-clustered entity from the other
entity collection is also placed – provided that the corresponding edge weight
is higher than $t$. Note that the greedy heuristic for BMC introduced in
(Melnik et al., 2002) is the same, in principle, to Unique Mapping Clustering
(see below). Note also that an additional configuration parameter is the
entity collection that is used as the basis for creating partitions, which can
be set to $V_{1}$ or $V_{2}$. In our experiments, we examine both options and
retain the best one. Its time complexity is $O(m)$ (Papadakis et al., 2021).

Exact Clustering (EXC). This algorithm is inspired from the Exact strategy of
(Melnik et al., 2002). EXC places two entities in the same partition only if
they are mutually the best matches, i.e., the most similar candidates of each
other, and their edge weight exceeds $t$. This approach is basically a
stricter, symmetric version of BMC and could also be conceived as a strict
version of the reciprocity filter that was employed in (Efthymiou et al.,
2019). Its time complexity is $O(n\;m)$.

Király’s Clustering (KRC). This algorithm is an adaptation of the linear time
3/2 approximation to the maximum stable marriage problem, called “New
Algorithm” in (Király, 2013). Intuitively, the entities of $V_{1}$ (“men”
(Király, 2013)) propose to the entities from $V_{2}$ with an edge weight
higher than $t$ (“women” (Király, 2013)) to form a partition (“get engaged”
(Király, 2013)). The entities of $V_{2}$ accept a proposal under certain
conditions (e.g., if it’s the first proposal they receive), and the partitions
and preferences are updated accordingly. Entities from $V_{1}$ get a second
chance to make proposals and the algorithm terminates when all entities of
$V_{1}$ are in a partition, or no more proposal chances are left. We omit some
of the details (e.g., the rare case of “uncertain man”), due to space
restrictions, and refer the reader to (Papadakis et al., 2021; Király, 2013)
for more information (e.g., the acceptance criteria for proposals). Its time
complexity is $O(n+m\;logm)$ (Király, 2013).

Unique Mapping Clustering (UMC). This algorithm prunes all edges with a weight
lower than $t$, sorts the remaining ones in decreasing weight/similarity and
iteratively forms a partition for the top-weighted pair as long as none of its
entities has already been matched to some other. This comes from the unique
mapping constraint of CCER, i.e., the restriction that each entity from the
one entity collection matches with at most one entity from the other. Note
that the CLIP Clustering algorithm, introduced for the multi-source ER problem
in (Saeedi et al., 2018b), is equivalent to UMC in the CCER case that we
study. Its time complexity is $O(m\;logm)$ (Papadakis et al., 2021).

Example. Figure 1 demonstrates an example of applying the above algorithms to
the similarity graph in Figure 1(a). For all algorithms, we assume a weight
threshold of $0.5$.

CNC completely discards the 4-node connected component $(A1,\\\ B1,A5,B3)$ and
considers exclusively the valid partitions $(A2,B2)$ and $(A3,B4)$, as
demonstrated in Figure 1(b).

Algorithms that aim to maximize the total sum of edge weights between the
matched entities, such as RCA and BAH, will cluster $A1$ with $B1$ and $A5$
with $B3$, as shown in Figure 1(c), if they manage to find the optimal
solution for the given graph. The reason is that this combination of edge
weights yields a sum of $0.6+0.6=1.2$, which is higher than $0.9$, i.e., the
sum resulting from clustering $A5$ with $B1$ and leaving $A1$ and $B3$ as
singletons.

UMC starts from the top-weighted edges, matching $A5$ with $B1$, $A2$ with
$B2$ and $A3$ with $B4$; $A1$ and $B3$ are left as singletons, as shown in
Figure 1(d), because their candidates have already been matched to other
entities. The same output is produced by EXC, as the entities in each
partition consider each other as their most similar candidate. For this
reason, BMC also yields the same results assuming that $V_{2}$ (blue) is used
as the basis entity collection.

The partitions generated by RSR and KRL depend on the sequence of adjacent
vertices and proposals, respectively. Given, though, that higher similarities
are generally more preferred than increasing total sum by both of these
algorithms, the outcome in Figure 1(d) is the most possible one for these
algorithms, too.

##  4\. Similarity Graphs

Two types of methods can be used for the generation of the similarity graphs
that constitute the input to the above algorithms (Christen, 2012):

(i) learning-free methods, which produce similarity scores in an unsupervised
manner based on the content of the input entities, and

(ii) learning-based methods, which produce probabilistic similarities based on
a training set.

In this work, we exclude the latter, focusing exclusively on learning-free
methods. Thus, we make the most of the selected datasets, without sacrificing
valuable parts for the construction of the training (and perhaps the
validation) set. We also avoid depending on the fine-tuning of numerous
configuration parameters, especially in the case of Deep Learning-based
methods (Wang et al., 2020). Besides, our goal is not to optimize the
performance of the CCER process, but to investigate how the main graph
matching algorithms perform under a large variety of real settings. For this
reason, we produce a large number of similarity graphs per dataset, rather
than generating synthetic data.

In this context, we do not apply any blocking method when producing these
inputs. Instead, we consider all pairs of entities from different datasets
with a similarity higher than 0. This allows for experimenting with a large
variety of similarity graph sizes, which range from several thousand to
hundreds of million edges. Besides, the role of blocking, i.e., the pruning of
the entity pairs with very low similarity scores, is performed by the
similarity threshold $t$ that is employed by all algorithms.

The resulting similarity graphs differ in the number of edges and the
corresponding weights, which were produced using different similarity
functions. Each similarity function consists of two parts: (i) the
representation model, and (ii) the similarity measure.

The representation model transforms a textual value into a model that is
suitable for applying the selected similarity measure. Depending on the scope
of these representations, we distinguish them into (i) schema-agnostic and
(ii) schema-based. The former consider all attribute values in an entity
description, while the latter consider only the value of a specific attribute.
Depending on their form, we also distinguish the representations into (i)
syntactic and (ii) semantic. The former operate on the original text of the
entities, while the latter operate on vector transformations (embeddings) of
the original text that aim to capture its actual connotation, leveraging
external information that has been extracted from large and generic corpora
through unsupervised learning.

The schema-based syntactic representations process each value as a sequence of
characters or words and apply to mostly short textual values. For example, the
attribute value “Joe Biden” can be represented as the set of tokens {‘Joe’,
‘Biden’}, or the set of character 3-grams {‘Joe’, ‘oe_’, ‘e_B’, ‘_Bi’, ‘Bid’,
‘ide’, ‘den’}.

The schema-agnostic syntactic representations process the set of all
individual attribute values. We use two types of models that have been widely
applied to document classification tasks (Papadakis et al., 2016):

(i) an n-gram vector (Manning et al., 2008), whose dimensions correspond to
character or token n-grams and are weighted according to their frequency (TF
or TF-IDF score). This approach does not consider the order of n-gram
appearances in each value.

(ii) an n-gram graph (Giannakopoulos et al., 2008), which transforms each
value into a graph, where the nodes correspond to character or token n-grams,
the edges connect those co-occurring in a window of size $n$ and the edge
weights denote the n-gram’s co-occurrence frequency. Thus, the order of
n-grams in a value is preserved.

Following the previous example, the character 3-gram vector of “Joe Biden”
would be a sparse vector with as many dimensions as all the 3-grams appearing
in the entity collection and with zeros in all other places except the ones
corresponding to the seven character 3-grams of “Joe Biden” listed above. For
the places corresponding to those seven 3-grams, the value would be the TF or
TF-IDF of each 3-gram. Similarly, a token 2-gram vector of “Joe Biden” would
be all zeros, for each token 2-gram appearing in all the values, except for
the place corresponding to the 2-gram ‘Joe Biden’, where its value would be 1.
A character 3-gram graph would be a graph with seven nodes, one for each
3-gram listed above, connecting the node ‘Joe’ to the nodes ‘oe_’ and ‘e_B’,
each with an edge of weight 1, ‘oe_’ to ‘e_B’ and ‘_Bi’, etc. See (Papadakis
et al., 2021) for more details.

Both approaches build an aggregate representation per entity: the n-gram
vectors treat each entity as a “document” and adjust their weights
accordingly, while the individual n-gram graphs of each value are merged into
a larger “entity graph” through the update operator discussed in
(Giannakopoulos et al., 2008). For both approaches, we consider
$n\in\\{2,3,4\\}$ for character and $n\in\\{1,2,3\\}$ for token n-grams.

The semantic representations treat every text as a sequence of items (words or
character n-grams) of arbitrary length and convert it into a dense numeric
vector based on learned external patterns. The closer the connotation of two
texts is, the closer are their vectors. These representations come in two main
forms, which apply uniformly to schema-agnostic and schema-based settings:

(i) The pre-trained embeddings of word- or character-level. Due to the highly
specialized content of ER tasks (e.g., arbitrary alphanumerics in product
names), the former, which include word2vec (Mikolov et al., 2013) and GloVe
(Pennington et al., 2014), suffer from a high portion of out-of-vocabulary
tokens – these are words that cannot be transformed into a vector because they
are not included in the training corpora (Mudgal et al., 2018). This drawback
is addressed by the character-level embeddings: fastText vectorizes a token by
summing the embeddings of all its character n-grams (Bojanowski et al., 2017).
For this reason, we exclusively consider the 300-dimensional fastText in the
following.

(ii) Transformer-based language models (Devlin et al., 2019) go beyond the
shallow, context-agnostic pre-trained embeddings by vectorizing an item based
on its context. In this way, they assign different vectors to homonyms, which
share the same form, but different meaning (e.g., “bank” as a financial
institution or as the border of a river). They also assign similar vectors to
synonyms, which have different form, but almost the same meaning (e.g.,
“enormous” and “vast”). Several BERT-based language models have been applied
to ER in (Brunner and Stockinger, 2020; Li et al., 2021). They do suffer from
out-of-vocabulary tokens, but to the best of our knowledge, there is no
established character-level language model that could address this issue, as
fastText does for pre-trained embeddings. Among them, we exclusively consider
the 768-dimensional ALBERT, due to its higher efficiency (Lan et al., 2020).

Every similarity measure receives as input two representation models and
produces a score that is proportional to the likelihood that the respective
entities correspond to the same real world object: the higher the score, the
more similar are the input models and their textual values and the higher is
the matching likelihood.

For each type of representation models, we considered a large variety of
established similarity measures. The following are combined with the
character-level schema-based representation models: Damerau-Levenshtein,
Levenshtein and q-grams distance, Jaro Similarity, Needleman Wunch, Longest
Common Subsequence and Longest Common Subsequence. To the token-level, schema-
based models we apply: Cosine, Dice and (Generalized) Jaccard similarity as
well as Monge-Elkan, Overlap Coefficient, Block and Euclidean distance. The
schema-agnostic n-gram vectors are coupled with Arcs and Jaccard similarity as
well as with Cosine and Generalized Jaccard similarity with TF or TF-IDF
weights. For the n-gram graphs, we consider Containment, (Normalized) Value
and Overall similarity. Finally, the semantic similarity models are combined
with Cosine, Euclidean and World Mover’s similarity. We formally define these
measures in the Appendix of (Papadakis et al., 2021).

##  5\. Experimental Setup

Table 2. Technical characteristics of the real datasets for Clean-Clean ER in increasing number of computational cost.  | $\mathbf{D_{1}}$ | $\mathbf{D_{2}}$ | $\mathbf{D_{3}}$ | $\mathbf{D_{4}}$ | $\mathbf{D_{5}}$ | $\mathbf{D_{6}}$ | $\mathbf{D_{7}}$ | $\mathbf{D_{8}}$ | $\mathbf{D_{9}}$ | $\mathbf{D_{10}}$
---|---|---|---|---|---|---|---|---|---|---
Dataset1 | Rest.1 | Abt | Amazon | DBLP | IMDb | IMDb | TMDb | Walmart | DBLP | IMDb
Dataset2 | Rest.2 | Buy | Google Pr. | ACM | TMDb | TVDB | TVDB | Amazon | Scholar | DBpedia
$|V_{1}|$ | 339 | 1,076 | 1,354 | 2,616 | 5,118 | 5,118 | 6,056 | 2,554 | 2,516 | 27,615
$|V_{2}|$ | 2,256 | 1,076 | 3,039 | 2,294 | 6,056 | 7,810 | 7,810 | 22,074 | 61,353 | 23,182
NVP1 | 1,130 | 2,568 | 5,302 | 10,464 | 21,294 | 21,294 | 23,761 | 14,143 | 10,064 | 1.6$\cdot 10^{5}$
NVP2 | 7,519 | 2,308 | 9,110 | 9,162 | 23,761 | 20,902 | 20,902 | 1.14$\cdot 10^{5}$ | 1.98$\cdot 10^{5}$ | 8.2$\cdot 10^{5}$
$|A_{1}|$ | 7 | 3 | 4 | 4 | 13 | 13 | 30 | 6 | 4 | 4
$|A_{2}|$ | 7 | 3 | 4 | 4 | 30 | 9 | 9 | 6 | 4 | 7
$|\bar{p}_{1}|$ | 3.33 | 2.39 | 3.92 | 4.00 | 4.16 | 4.16 | 3.92 | 5.54 | 4.00 | 5.63
$|\bar{p}_{2}|$ | 3.33 | 2.14 | 3.00 | 3.99 | 3.92 | 2.68 | 2.68 | 5.18 | 3.24 | 35.20
$|D(V_{1}$$\cap$$V_{2})|$ | 89 | 1,076 | 1,104 | 2,224 | 1,968 | 1,072 | 1,095 | 853 | 2,308 | 22,863
$||V_{1}\times V_{2}||$ | 7.65$\cdot 10^{5}$ | 1.16$\cdot 10^{6}$ | 4.11$\cdot 10^{6}$ | 6.00$\cdot 10^{6}$ | 3.10$\cdot 10^{7}$ | 4.00$\cdot 10^{7}$ | 4.73$\cdot 10^{7}$ | 5.64$\cdot 10^{7}$ | 1.54$\cdot 10^{8}$ | 6.40$\cdot 10^{8}$

All experiments were carried out on a server running Ubuntu 18.04.5 LTS with a
32-core Intel Xeon CPU E5-4603 v2 (2.20GHz), 128 GB of RAM and 1.7 TB HDD. All
time experiments were executed on a single core. For the implementation of the
schema-based syntactic similarity functions, we used the Simmetrics Java
package222https://github.com/Simmetrics/simmetrics. For the schema-agnostic
syntactic similarity functions, we used the implementation provided by the
JedAI toolkit (the implementation of n-gram graphs and the corresponding graph
similarities is based on the JIinsect
toolkit333https://github.com/ggianna/JInsect). For the semantic representation
models, we employed the Python sister
package444https://pypi.org/project/sister, which supports both fastText and
ALBERT. For the computation of the semantic similarities, we used the Python
scipy package.555https://www.scipy.org

Datasets. In our experiments, we use 10 real-world, established datasets for
ER, whose technical characteristics appear in Table 2, where $|V_{x}|$ stands
for the number of input entities, $|NVP_{x}|$ for the total number of name-
value pairs, $|A_{x}|$ for the number of attributes and $|\bar{p}_{x}|$ for
the average number of name-value pairs per entity profile in Datasetx.
$|D(V_{1}\cap V_{2})|$ denotes the number of duplicates in the ground-truth
and $||V_{1}\times V_{2}||$ the number of pairwise comparisons executed by the
brute-force approach. $D_{1}$, which was introduced in OAEI
2010666http://oaei.ontologymatching.org/2010/im, contains data about
restaurants. $D_{2}$ matches products from the online retailers Abt.com and
Buy.com (Köpcke et al., 2010). $D_{3}$ interlinks products from Amazon and the
Google Base data API (Google Pr.) (Köpcke et al., 2010). $D_{4}$ contains data
about publications from DBLP and ACM (Köpcke et al., 2010). $D_{5}-D_{7}$
contain data about television shows from TheTVDB.com (TVDB) and movies from
IMDb and themoviedb.org (TMDb) (Obraczka et al., 2021). $D_{8}$ contains data
about products from Walmart and Amazon (Mudgal et al., 2018). $D_{9}$ contains
data about scientific publications from DBLP and Google Scholar (Köpcke et
al., 2010). $D_{10}$ matches movies from IMDb and DBpedia (Papadakis et al.,
2020a) (note that $D_{10}$ contains a different snapshot of IMDb movies than
$D_{5}$ and $D_{6}$). All datasets are publicly available through the JedAI
data repository.777https://github.com/scify/JedAIToolkit/tree/master/data

Note that for the schema-based settings (both the syntactic and semantic
ones), we used only the attributes that combine high coverage with high
distinctiveness. That is, they appear in the majority of entities, while
conveying a rich diversity of values, thus yielding high effectiveness. These
attributes are “name” and “phone” for $D_{1}$, “name” for $D_{2}$, “title” for
$D_{3}$, “title” and “authors” for $D_{4}$, “modelno” and “title” for $D_{5}$,
“title” and “authors” for $D_{6}$, “name” and “title” for $D_{7}$, “title” and
“name” for $D_{8}$, “title” and “abstract” for $D_{9}$, and “title” for
$D_{10}$.

Evaluation Measures. In order to assess the relative performance of the above
graph matching algorithms, we evaluate both their effectiveness and their time
efficiency (and scalability). We measure their effectiveness, with respect to
a ground truth of known matches, in terms of three measures:

$\bullet$ _Precision_ denotes the portion of output partitions that involve
two matching entities.

$\bullet$ _Recall_ denotes that portion of partitions with two matching
entities that are included in the output.

$\bullet$ _F-Measure_ ($F1$) is the harmonic mean of Precision and Recall.

All are defined in $[0,1]$. Higher values show higher effectiveness.

For time efficiency, we measure the average run-time of an algorithm for each
setting, i.e., the time that intervenes between receiving the weighted
similarity graph as input and returning the partitions as output, over 10
repeated executions.

Generation Process. To generate a large variety of input similarity graphs, we
apply every similarity function described in Section 4 to all datasets in
Table 2. We actually apply all combinations of representation models and
similarity measures, thus yielding 60 schema-agnostic syntactic similarity
graphs per dataset, 16 schema-based similarity graphs per attribute in each
dataset, and 12 semantic similarity graphs per dataset. Note that we did not
apply any fine-tuning to ALBERT, as our goal is not optimize ER performance,
but rather to produce diverse inputs.

To estimate the algorithms’ performance, we first apply min-max normalization
to the edge weights of all similarity graphs, regardless of the similarity
function that produced them, to ensure that they are restricted to $[0,1]$.
Next, we apply every algorithm to every input similarity graph by varying its
similarity threshold from 0.05 to 1.0 with a step of 0.05 (preliminary
experiments showed that there is no significant difference in the experimental
results when using a smaller step size like 0.01. Thus, we set it to 0.05 to
reduce the effort for the experiments, due to the large number of algorithms,
inputs and datasets they involve). The largest threshold that achieves the
highest F-Measure is selected as the optimal one, determining the performance
of the algorithm for the particular input.

Table 3. The number of similarity graphs $|G|$ as well as their size, in terms of the average number of edges $|\bar{E}|$, per dataset. In parenthesis, the ratio of $|\bar{E}|$ to $||V_{1}\times V_{2}||$ (cf. Table 2). |  Syntactic Similarities |  Semantic Similarities
---|---|---
| Schema-based | Schema-ag. | Schema-based | Schema-ag.
| $\mathbf{|G|}$ |  $\mathbf{|\bar{E}|}$$\cdot$106 | $\mathbf{|G|}$ |  $\mathbf{|\bar{E}|}$$\cdot$106 | $\mathbf{|G|}$ |  $\mathbf{|\bar{E}|}$$\cdot$106 | $\mathbf{|G|}$ |  $\mathbf{|\bar{E}|}$$\cdot$106
$D_{1}$ | 20 | 0.16 (21.2%) | 46 | 0.72 (93.5%) | 8 | 0.26 (34.3%) | 2 | 0.76 (100%)
$D_{2}$ | 12 | 1.05 (90.5%) | 47 | 0.64 (55.1%) | 2 | 1.16 (100%) | 2 | 1.16 (100%)
$D_{3}$ | 14 | 2.89 (70.5%) | 53 | 2.65 (64.5%) | 2 | 4.11 (100%) | 2 | 4.11 (100%)
$D_{4}$ | 27 | 4.49 (74.8%) | 24 | 3.84 (64.0%) | 12 | 5.99 (99.8%) | 4 | 6.00 (100%)
$D_{5}$ | 24 | 5.81 (18.7%) | 48 | 11.92 (38.5%) | 12 | 8.22 (26.7%) | 2 | 30.64 (98.8%)
$D_{6}$ | 25 | 8.39 (21.0%) | 45 | 10.99 (27.5%) | 12 | 12.31 (30.8%) | 2 | 39.81 (99.6%)
$D_{7}$ | 26 | 2.80 (05.9%) | 42 | 12.21 (25.8%) | 12 | 36.44 (07.8%) | 5 | 46.99 (99.3%)
$D_{8}$ | 26 | 28.10 (49.8%) | 47 | 37.31 (66.2%) | 2 | 37.70 (67.0%) | - | -
$D_{9}$ | 20 | 119.18 (77.2%) | 46 | 77.56 (50.2%) | 6 | 154.26 (100%) | 2 | 154.36 (100%)
$D_{10}$ | 13 | 250.73 (39.2%) | 43 | 317.17 (49.5%) | 2 | 378.51 (59.0%) | - | -
$\Sigma$ | 207 | - | 441 | - | 70 | - | 21 | -

Special care was taken to clean the experimental results from noise. We
removed all similarity graphs where all matching entities had a zero edge
weight. We also removed all noisy graphs, where all algorithms achieve an
F-Measure lower than 0.25. Finally, we cleaned our data from duplicate inputs,
i.e., similarity graphs that emanate from the same dataset but different
similarity functions and have the same number of edges, while at least two
different algorithms achieve their best performance with the same similarity
threshold, exhibiting almost identical effectiveness, i.e., the difference in
F-Measure and precision or recall is less than 0.2%.

The characteristics of the retained similarity graphs appear in Table 3.
Overall, there are 739 different similarity graphs, most of which rely on
syntactic similarity functions and the schema-agnostic settings, in
particular. The reason is that the semantic similarities assign relatively
high similarity scores to most pairs of entities, thus resulting in poor
performance for all considered algorithms – especially in the schema-agnostic
settings. Every dataset is represented by at least 58 similarity graphs, in
total, while the average number of edges ranges from 160K to 379M. This large
set of real-world similarity graphs allows for a rigorous testing of the graph
matching algorithms under diverse conditions.

##  6\. Experimental Analysis

Effectiveness Measures. The most important performance aspect of clustering
algorithms is their ability to effectively distinguish the matching from the
non-matching pairs. In this section, we examine this aspect, addressing the
following questions:

  1. QE(1):

What is the trade-off between precision and recall that is achieved by each
algorithm?

  2. QE(2):

Which algorithm is the most/least effective?

  3. QE(3):

How does the type of input affect the effectiveness of the evaluated
algorithms?

  4. QE(4):

Which other factors affect their effectiveness?

To answer QE(1) and QE(2), we consider the macro-average performance ($\mu$)
of all algorithms across all input similarity graphs, which is reported in
Table 4. We observe that all algorithms emphasize on precision at the cost of
lower recall. The most balanced algorithm is UMC, as it yields the smallest
difference between the two measures (just 0.017). In contrast, CNC constitutes
the most imbalanced algorithm, as its precision is almost double its recall.
The former achieves the second best F-Measure, being very close to the top
performer KRC, while the latter achieves the second worst F-Measure,
surpassing only BAH. Note that BAH is the least robust with respect to all
measures, as indicated by their standard deviation ($\sigma$), due to its
stochastic functionality, while CNC, UMC and KRC are the most robust with
respect to precision, recall and F-Measure, respectively. Among the other
algorithms, EXC and BMC are closer to KRC and UMC, with the former achieving
the third highest F1, while RSR and RCA lie closer to CNC, with RSR exhibiting
the third lowest F1.

Table 4. Macro-average performance across all similarity graphs. | Precision | Recall | F-Measure
---|---|---|---
| $\mu$ | $\sigma$ | $\mu$ | $\sigma$ | $\mu$ | $\sigma$
$CNC$ | 0.801 | 0.185 | 0.403 | 0.257 | 0.490 | 0.237
$RSR$ | 0.615 | 0.228 | 0.455 | 0.239 | 0.499 | 0.216
$RCA$ | 0.590 | 0.224 | 0.502 | 0.238 | 0.518 | 0.211
$BAH$ | 0.548 | 0.236 | 0.383 | 0.282 | 0.408 | 0.246
$BMC$ | 0.631 | 0.212 | 0.582 | 0.221 | 0.586 | 0.196
$EXC$ | 0.735 | 0.197 | 0.544 | 0.242 | 0.591 | 0.199
$KRC$ | 0.696 | 0.200 | 0.597 | 0.223 | 0.619 | 0.187
$UMC$ | 0.645 | 0.212 | 0.628 | 0.212 | 0.618 | 0.193

To assess the statistical significance of these patterns, we perform an
analysis (Herbold, 2020) based on their F-Measure over the 739 paired samples.
In more detail, we first perform the non-parametric Friedman test (Demsar,
2006) and reject the null hypothesis (with $\alpha$ = 0.05) that the
differences between the evaluated methods are statistically insignificant.
Then, we perform a post-hoc Nemenyi test (Nemenyi, 1963) to identify the
critical distance (CD = 0.37) between the methods. The Nemenyi diagram based
on F-Measure, which appears in Figure 2, shows that there are no significant
differences among the methods with the worst ranks with respect to F-Measure
(CNC, RCA, BAH, and RSR). All other differences are significant, with KRC,
UMC, EXC, and BMC, ranking first (in that order).

We have also performed the same analysis for Precision and for Recall
(Papadakis et al., 2021) (the same CD of 0.37 applies). The Precision-based
ranking (reporting Mean Rank, MR) of the methods is: CNC (MR=1.28), EXC
(MR=2.5), KRC (MR=3.7), UMC (MR=4.81), BMC (MR=5.3), RSR (MR=5.66), BAH
(MR=6.12), and RCA (MR=6.64), so there is no significant difference between
BMC and RSR, while all other differences are significant. The Recall-based
ranking of the methods is: UMC (MR=1.77), KRC (MR=2.44), BMC (MR=3.15), EXC
(MR=4.34), RCA (MR=5.46), RSR (MR=5.92), BAH (MR=5.93), and CNC (MR=7), so
there is no significant difference between RSR and BAH, while all other
differences are significant.

An interesting observation drawn from these patterns is that EXC consistently
achieves higher precision and lower recall than BMC. This should be expected,
given that EXC requires an additional reciprocity check before declaring that
two entities match. We notice, however, that the gain in precision is greater
than the loss in recall and, thus, EXC yields a higher F-Measure than BMC, on
average. Note also that in the vast majority of cases, BMC works best when
choosing the smallest entity collection as the basis for creating clusters.

To answer QE(3), Figure 3 presents the distribution of precision, recall and
F-Measure of all algorithms across the four types of similarity graphs’
origin. For the schema-based syntactic weights, we observe in Figure 3(a) that
the average precision of all algorithms increases significantly in comparison
to the one in Table 4 \- from 4.0% (CNC) to 16.8% (BMC). For CNC and RSR, this
is accompanied by an increase in average recall (by 7.7% and 5.1%,
respectively), while for all other algorithms, the average recall drops
between 4.8% (EXC) and 7.5% (KRC). This means that the schema-based syntactic
similarities reinforce the imbalance between precision and recall in Table 4
in favor of the former for all algorithms except CNC and RSR. The average
F-Measure drops only for KRC (by 0.2%), which is now outperformed by UMC.
Similarly, BMC exceeds EXC in terms of average F1 (0.603 vs 0.599), because
the increase in its mean precision is much higher than the decrease in its
mean recall. Finally, it is worth noting that this type of input increases
significantly the robustness of all algorithms, as the standard deviation of
F1 drops by more than 12% for all algorithms, but the stochastic BAH.

Figure 2. Nemenyi diagram based on F-Measure.

Figure 3. Precision (left), recall (center) and F-Measure (right) of all
algorithms over similarity graphs with (a) schema-based syntactic, (b) schema-
agnostic syntactic, (c) schema-based semantic, and (d) schema-agnostic
semantic edge weights.

The opposite patterns are observed for schema-agnostic syntactic weights in
Figure 3(b): the imbalance between precision and recall is reduced, as on
average, the former drops from 1.9% (EXC) to 5.3% (BAH), while the latter
raises from 2.4% (RSR) to 7.6% (RCA). The imbalance is actually reversed for
BMC and UMC, whose average recall (0.613 and 0.664, resp.) exceeds their
average precision (0.606 and 0.622, resp.). The only exception is CNC, which
increases both its average and average precision. Overall, there are minor,
positive changes in the average F-Measure of most algorithms, with KRC and EXC
retaining a minor edge over UMC and BMC, respectively.

Regarding the semantic similarity weights, we observe in Figure 3(c) similar
patterns with the schema-based syntactic ones: average precision increases for
all algorithms except CNC and RSR, while average recall drops in all cases. In
this case, though, the latter change is stronger than the former, leading to
lower average F-Measures than those in Table 4. In the case of schema-agnostic
semantic weights, all measures in Figure 3(d) drop to a significant extend
(¿15% in most cases) when compared to Table 4. It is also remarkable that the
standard deviation of all measures increases to a significant extent for both
schema-based and schema-agnostic weights in relation to their syntactic
counterparts, despite the fewer similarity graphs. As a result, the robustness
of all algorithms over semantic weights is limited. Nevertheless, KRC and EXC
maintain a clear lead over UMC and MBC, respectively.

Table 5. The number of times each algorithm achieves the highest and second highest F1 for a particular similarity graph, $\\#Top1$ and $\\#Top2$, resp., as well as the average difference $\Delta~{}(\%)$ with the second highest F1 across all types of edge weights for balanced (BLC), one-sided (OSD) and scarce (SCR) entity collections. OVL stands for the overall sums or averages across all similarity graphs per category. Note that there are ties for both $\\#Top1$ and $\\#Top2$: 16 and 40, resp., over schema-based syntactic weights, 17 and 11, resp., over schema-agnostic syntactic weights, 9 and 2, resp., over schema-based semantic weights.  |  Syntactic Similarities |  Semantic Similarities
---|---|---
| Schema-based | Schema-agnostic | Schema-based | Schema-agnostic
| BLC | OSD | SCR | OVL | BLC | OSD | SCR | OVL | BLC | OSD | SCR | OVL | BLC | OSD | SCR | OVL
$CNC$ | $\\#Top1$ | - | - | 18 | 18 | - | - | 48 | 48 | - | - | 1 | 1 | - | - | - | -
$\Delta~{}(\%)$ | - | - | 0.41 | 0.41 | - | - | 7.59 | 7.59 | - | - | 0.33 | 0.33 | - | - | - | -
| $\\#Top2$ | - | - | 8 | 8 | - | - | 8 | 8 | - | - | 4 | 4 | - | - | - | -
$RSR$ | $\\#Top1$ | - | - | 4 | 4 | - | - | 1 | 1 | - | - | 1 | 1 | - | - | - | -
$\Delta~{}(\%)$ | - | - | 1.90 | 1.90 | - | - | 0.51 | 0.51 | - | - | 0.33 | 0.33 | - | - | - | -
| $\\#Top2$ | - | - | 7 | 7 | - | - | 5 | 5 | - | - | 1 | 1 | - | - | 1 | 1
$RCA$ | $\\#Top1$ | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | -
$\Delta~{}(\%)$ | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | -
| $\\#Top2$ | - | - | - | - | - | - | 1 | 1 | - | - | - | - | - | - | - | -
$BAH$ | $\\#Top1$ | 8 | - | 1 | 9 | 40 | - | 2 | 42 | 2 | - | 1 | 3 | 2 | - | 1 | 3
$\Delta~{}(\%)$ | 3.69 | - | 1.90 | 3.49 | 5.55 | - | 0.46 | 5.31 | 12.72 | - | 0.67 | 8.70 | 13.96 | - | 0.52 | 9.48
| $\\#Top2$ | 8 | - | 3 | 11 | 7 | 5 | 6 | 18 | - | - | 2 | 2 | - | - | - | -
$BMC$ | $\\#Top1$ | - | - | 6 | 6 | - | - | 7 | 7 | - | - | 2 | 2 | - | - | - | -
$\Delta~{}(\%)$ | - | - | 0.57 | 0.57 | - | - | 1.41 | 1.41 | - | - | 0.21 | 0.21 | - | - | - | -
| $\\#Top2$ | 2 | 2 | 27 | 31 | 12 | 5 | 18 | 35 | - | - | 2 | 2 | - | - | - | -
$EXC$ | $\\#Top1$ | - | 4 | 35 | 39 | - | 11 | 79 | 90 | - | 3 | 14 | 17 | - | - | 5 | 5
$\Delta~{}(\%)$ | - | 0.53 | 0.87 | 0.84 | - | 0.18 | 1.18 | 1.67 | - | 1.62 | 2.54 | 2.38 | - | - | 4.18 | 4.18
| $\\#Top2$ | - | 10 | 31 | 41 | - | 19 | 72 | 91 | - | 3 | 19 | 22 | - | 2 | 2 | 4
$KRC$ | $\\#Top1$ | 22 | 15 | 43 | 80 | 16 | 47 | 79 | 142 | 11 | 5 | 30 | 46 | 3 | 4 | 4 | 11
$\Delta~{}(\%)$ | 1.36 | 1.60 | 0.35 | 0.87 | 4.15 | 2.54 | 4.05 | 3.56 | 2.92 | 1.47 | 4.92 | 4.07 | 4.06 | 10.32 | 5.01 | 6.68
| $\\#Top2$ | 12 | 17 | 57 | 86 | 39 | 40 | 87 | 166 | 3 | 3 | 11 | 17 | 1 | - | 5 | 6
$UMC$ | $\\#Top1$ | 22 | 15 | 30 | 67 | 58 | 41 | 29 | 128 | 3 | - | 6 | 9 | 1 | - | 1 | 2
$\Delta~{}(\%)$ | 4.99 | 1.75 | 1.19 | 2.56 | 4.51 | 3.21 | 2.51 | 3.64 | 2.11 | - | 0.34 | 0.93 | 0.22 | - | 1.00 | 0.61
| $\\#Top2$ | 30 | 5 | 28 | 63 | 56 | 30 | 42 | 128 | 13 | 2 | 9 | 24 | 5 | 2 | 3 | 10

To answer QE(4), we distinguish the similarity graphs into three categories
according to the portion of duplicates in their ground truth with respect to
the size of $|V_{1}|$ and $|V_{2}|$:

(i) Balanced (BLC) are the entity collections where the vast majority of
entities in $V_{i}$ are matched with an entity in $V_{j}$ (i=1 $\wedge$ j=2 or
i=2 $\wedge$ j=1). This category includes all similarity graphs generated from
$D_{2}$, $D_{4}$ and $D_{10}$.

(ii) One-sided (OSD) are the entity collections, where only the vast majority
of entities in $V_{1}$ are matched with an entity from $V_{2}$, or vice versa.
OSD includes all graphs stemming from $D_{3}$ and $D_{9}$.

(iii) Scarce (SCR) are the entity collections, where a small portion of
entities in $V_{i}$ are matched with an entity in $V_{j}$ (i=1 $\wedge$ j=2 or
i=2 $\wedge$ j=1). This category includes all graphs generated from $D_{1}$,
$D_{5}$-$D_{8}$.

We apply this categorization to the four main types of similarity graphs
defined in Section 4 and for each subcategory, we consider three new
effectiveness measures:

(i) $\\#Top1$ denotes the number of times an algorithm achieves the maximum
F-Measure for a particular category of similarity graphs,

(ii) $\Delta~{}(\%)$ stands for the average difference (expressed as a
percentage) between the highest and the second highest F1 across all
similarity graphs of the same category, and

(iii) $\\#Top2$ denotes the number of times an algorithm scores the second
highest F1 for a particular category of similarity graphs.

Note that in case of ties, we increment $\\#Top1$ and $\\#Top2$ for all
involved algorithms. Note also that these three effectiveness measures also
allow for answering QE(2) in more detail.

The results for these measures are reported in Table 5. For schema-based
syntactic weights, there is a strong competition between KRC and UMC for the
highest effectiveness. Both algorithms achieve the maximum F1 for the same
number of similarity graphs in the case of balanced and one-sided entity
collections. For the former inputs, though, UMC exhibits consistently high
performance, as it ranks second in almost all cases that it is not the top
performer, unlike KRC, which comes second in 1/3 of these cases. Additionally,
UMC achieves significantly higher $\Delta$ than KRC. For one-sided entity
collections, KRC takes a minor lead over UMC: even though its $\Delta$ is
slightly lower, it comes second three times more often than UMC. For scarce
entity collections, KRC takes a clear lead over UMC, outperforming it with
respect to both $\\#Top1$ and $\\#Top2$ to a large extent. UMC excels only
with respect to $\Delta$.

Among the remaining algorithms, CNC, RSR, BMC and EXC seem suitable only for
scarce entity collections. RSR actually achieves the highest $\Delta$, while
EXC achieves the second highest $\\#Top1$ and $\\#Top2$, outperforming UMC.
Regarding BAH, we observe that for balanced entity collections, it outperforms
all algorithms for 15% of the similarity graphs, achieving the highest
$\Delta$ and comes second for an equal number of inputs. This is in contrast
to the poor average performance reported in Table 4, but is explained by its
stochastic nature, which gives rise to an unstable performance, as indicated
by the significantly higher $\sigma$ than all other algorithms for all
effectiveness measures.

In the case of schema-agnostic syntactic edge weights, UMC verifies its
superiority over KRC for balanced entity collections with respect to all
measures. KRC is actually outperformed by BAH, which achieves the top F1 2.5
times more often, while exhibiting the highest $\Delta$ among all algorithms.
For one-sided entity collections, KRC excels with respect to $\\#Top1$ and
$\\#Top2$, but UMC achieves significantly higher $\Delta$, while EXC
constitutes the third best algorithm overall, as for the schema-based
syntactic edge weights. In the case of scarce entity collections, the two
competing algorithms are KRC and EXC, as they share the highest $\\#Top1$.
Yet, the former achieves three times higher $\Delta$ and slightly higher
$\\#Top2$. Suprisingly, CNC ranks second in terms of $\\#Top1$, while
achieving the highest $\Delta$ by far, among all algorithms. As a result, UMC
is left at the fourth place, followed by BMC.

For the semantic edge weights, we observe the following patterns: for the
balanced entity collections, only KRC, BAH and UMC exhibit the highest
performance for both schema-based and schema-agnostic weights. They excel in
$\\#Top1$, $\Delta$ and $\\#Top2$, respectively. For one-sided entity
collections, KRC is the dominant algorithm, especially in the case of schema-
agnostic weights. For the schema-based ones, EXC consistently achieves very
high performance, too. For scarce entity collections, there is a strong
competition between KRC and EXC; the former consistently outperforms the
latter with respect to $\Delta$, while EXC excels in $\\#Top1$ for schema-
agnostic weights and in $\\#Top2$ for schema-based ones.

We examined other patterns with respect to additional characteristics of the
entity collections, such as the distribution of positive and negative weights
(i.e., between matching and non-matching entities, respectively) and the
domain (e-commerce for $D_{2}$, $D_{3}$ and $D_{8}$, bibliographic data for
$D_{4}$ and $D_{9}$ as well as movies for $D_{5}$-$D_{8}$ and $D_{10}$). Yet,
no clear patterns emerged in these cases.

Figure 4. Scalability analysis of all algorithms over all similarity graphs
with (i) schema-based syntactic, (ii) schema-agnostic syntactic, (iii) schema-
based semantic and (iv) schema-agnostic semantic edge weights. The horizontal
axis corresponds to the number of edges in the similarity graphs and the
vertical one to the run-time in milliseconds (maximum value=16.7 min).

Time Efficiency. The (relative) run-time of the evaluated algorithms is a
crucial aspect for the task of Entity Resolution, due to the very large
similarity graphs, which comprise thousands of entities/nodes and (hundreds
of) millions of edges/entity pairs, as reported in Table 3. Below, we study
this aspect along with the scalability of the considered algorithms over the
739 different similarity graphs. More specifically, we examine the following
questions:

  1. QT(1):

Which algorithm is the fastest one?

  2. QT(2):

Which factors affect the run-time of the algorithms?

  3. QT(3):

How scalable are the algorithms to large input sizes?

  4. QT(4):

Which algorithms offer the best trade-off between F-Measure and run-time?

The average run-times over 10 executions of the evaluated algorithms per
dataset and type of edge weights are reported in Table 6.

Regarding QT(1), we observe that all algorithms are quite fast, as they are
all able to process even the largest similarity graphs (i.e., those of $D_{9}$
and $D_{10}$) within minutes or even seconds. CNC is the fastest one almost in
all cases, due to the simplicity of its approach. It is followed in close
distance by BMC and RSR, with the former consistently outperforming the
latter. EXC is also very efficient, but as expected, it is usually slower than
BMC, due to the additional reciprocity check it involves. On the other extreme
lies BAH, which constitutes by far the slowest method, yielding in many cases
2 or even 3 orders of magnitude longer run-times. The reason is the large
number (10,000) of search steps we allow per dataset. For the largest
datasets, its maximum run-time actually equals the run-time limit of 2
minutes, except for $D_{9}$, where the very large number of entities in
$V_{2}$ delays the activation of the time-out. The rest of the algorithms lie
between these two extremes: KRC is the slowest one, on average, while UMC and
RCA exhibit significantly lower run-times. Among the most effective
algorithms, EXC is significantly faster than UMC, which is significantly
faster than KRC.

Table 6. Mean run-time per algorithm, dataset and type of input. Milliseconds are reported, except for BAH, $D_{10}$ and cases followed by s, which are measured in seconds. | CNC | RSR | RCA |  BAH (sec) | BMC | EXC | KRC | UMC
---|---|---|---|---|---|---|---|---
$\mathbf{D_{1}}$ |  3$\pm$1 |  8$\pm$5 |  8$\pm$4 |  1.9$\pm$.0 |  4$\pm$5 |  4$\pm$3 |  14$\pm$9 |  4$\pm$3
$\mathbf{D_{2}}$ |  8$\pm$1 |  15$\pm$4 |  20$\pm$2 |  1.1$\pm$.0 |  13$\pm$5 |  59$\pm$73 |  66$\pm$19 |  39$\pm$50
$\mathbf{D_{3}}$ |  21$\pm$13 |  36$\pm$16 |  57$\pm$15 |  2.2$\pm$.1 |  24$\pm$16 |  34$\pm$37 |  200$\pm$91 |  61$\pm$64
$\mathbf{D_{4}}$ |  32$\pm$18 |  57$\pm$23 |  136$\pm$20 |  2.0$\pm$.0 |  43$\pm$25 |  69$\pm$164 |  384$\pm$381 |  254$\pm$601
$\mathbf{D_{5}}$ |  44$\pm$41 |  56$\pm$38 |  662$\pm$66 |  3.6$\pm$.8 |  49$\pm$49 |  43$\pm$35 |  286$\pm$254 |  53$\pm$45
$\mathbf{D_{6}}$ |  52$\pm$60 |  86$\pm$79 |  706$\pm$97 |  3.0$\pm$.2 |  63$\pm$75 |  58$\pm$64 |  422$\pm$508 |  79$\pm$93
$\mathbf{D_{7}}$ |  41$\pm$95 |  43$\pm$17 |  980$\pm$251 |  3.1$\pm$.3 |  28$\pm$16 |  27$\pm$13 |  204$\pm$138 |  50$\pm$81
$\mathbf{D_{8}}$ |  196$\pm$168 |  209$\pm$167 |  557$\pm$136 |  123.5$\pm$.6 |  282$\pm$402 |  182$\pm$153 |  1.2s$\pm$1.0s |  213$\pm$194
$\mathbf{D_{9}}$ |  946$\pm$421 |  994$\pm$408 |  1.8s$\pm$.3s |  147.5$\pm$2.7 |  1.1s$\pm$1.4s |  18s$\pm$36s |  17s$\pm$29s |  1.1s$\pm$.5s
$\mathbf{D_{10}}$ |  1.6$\pm$1.1 |  2.8$\pm$1.4 |  21.9$\pm$1.2 |  127$\pm$2 |  1.9$\pm$1.2 |  1.6$\pm$1.1 |  164$\pm$243 |  7.9$\pm$18.4
(a) Schema-based, syntactic inputs
$\mathbf{D_{1}}$ |  11$\pm$8 |  19$\pm$27 |  10$\pm$2 |  1.9$\pm$.1 |  9$\pm$5 |  22$\pm$34 |  52$\pm$0.2 |  25$\pm$47
$\mathbf{D_{2}}$ |  6$\pm$3 |  18$\pm$8 |  18$\pm$4 |  1.1$\pm$.0 |  10$\pm$10 |  14$\pm$16 |  51$\pm$40 |  74$\pm$166
$\mathbf{D_{3}}$ |  21$\pm$13 |  39$\pm$21 |  57$\pm$13 |  2.3$\pm$.4 |  34$\pm$48 |  81$\pm$177 |  582$\pm$686 |  599$\pm$1.2s
$\mathbf{D_{4}}$ |  31$\pm$19 |  56$\pm$22 |  130$\pm$17 |  2.2$\pm$.3 |  40$\pm$26 |  44$\pm$74 |  334$\pm$705 |  125$\pm$356
$\mathbf{D_{5}}$ |  93$\pm$58 |  206$\pm$393 |  616$\pm$55 |  2.9$\pm$.4 |  172$\pm$201 |  203$\pm$404 |  858$\pm$821 |  672$\pm$2.0s
$\mathbf{D_{6}}$ |  86$\pm$83 |  124$\pm$84 |  676$\pm$70 |  3.3$\pm$.4 |  99$\pm$92 |  151$\pm$216 |  635$\pm$578 |  116$\pm$107
$\mathbf{D_{7}}$ |  102$\pm$109 |  129$\pm$127 |  912$\pm$91 |  3.5$\pm$.4 |  104$\pm$96 |  112$\pm$168 |  637$\pm$713 |  232$\pm$716
$\mathbf{D_{8}}$ |  280$\pm$121 |  319$\pm$132 |  581$\pm$91 |  122.8$\pm$.4 |  245$\pm$103 |  443$\pm$1,264 |  1.8s$\pm$747 |  360$\pm$155
$\mathbf{D_{9}}$ |  611$\pm$492 |  728$\pm$515 |  1.5s$\pm$340 |  144.8$\pm$2 |  627$\pm$499 |  1.7s$\pm$6.5s |  5.3s$\pm$9.7s |  2.1s$\pm$8.8s
$\mathbf{D_{10}}$ |  2.5$\pm$2.1s |  8.4$\pm$14.3 |  24.6$\pm$2.8 |  128.4$\pm$2.1 |  4.1$\pm$6.0 |  21.1$\pm$86.4 |  205$\pm$354 |  157$\pm$600
(b) Schema-agnostic, syntactic inputs
$\mathbf{D_{1}}$ |  11$\pm$18 |  32$\pm$43 |  9$\pm$5 |  1.9$\pm$.0 |  9$\pm$7 |  16$\pm$19 |  33$\pm$26 |  20$\pm$29
$\mathbf{D_{2}}$ |  7$\pm$0 |  91$\pm$51 |  23$\pm$3 |  1.0$\pm$.0 |  15$\pm$2 |  30$\pm$26 |  118$\pm$42 |  79$\pm$48
$\mathbf{D_{3}}$ |  28$\pm$4 |  136$\pm$124 |  88$\pm$16 |  2.2$\pm$.0 |  282$\pm$11 |  602$\pm$612 |  2.4s$\pm$.2 |  5.6s$\pm$.0s
$\mathbf{D_{4}}$ |  210$\pm$388 |  392$\pm$514 |  152$\pm$14 |  2.1$\pm$.1 |  217$\pm$366 |  295$\pm$569 |  1.5s$\pm$1.4s |  1.6$\pm$3.6s
$\mathbf{D_{5}}$ |  384$\pm$869 |  883$\pm$1.7s |  629$\pm$49 |  2.8$\pm$.2 |  373$\pm$947 |  445$\pm$1s |  1.4s$\pm$2.8s |  2.3s$\pm$6.3
$\mathbf{D_{6}}$ |  550$\pm$1.3s |  1.4s$\pm$2.8s |  730$\pm$70 |  3.0$\pm$.2 |  250$\pm$482 |  754$\pm$2s |  2.1s$\pm$4.4s |  4s$\pm$12s
$\mathbf{D_{7}}$ |  181$\pm$372 |  264$\pm$415 |  917$\pm$77 |  3.0$\pm$.1 |  124$\pm$247 |  168$\pm$301 |  547$\pm$741 |  882$\pm$2.2s
$\mathbf{D_{8}}$ |  216$\pm$0 |  381$\pm$78 |  654$\pm$31 |  123.6$\pm$.3 |  245$\pm$2 |  4.8s$\pm$6.4s |  1.8s$\pm$.0s |  364$\pm$10
$\mathbf{D_{9}}$ |  1s$\pm$317 |  1.8s$\pm$1.1s |  2.2s$\pm$.3s |  147.8$\pm$2.7 |  1.1s$\pm$.1s |  1.2s$\pm$.2s |  8.2s$\pm$.6s |  1.7s$\pm$.5s
$\mathbf{D_{10}}$ |  2.3$\pm$.1 |  5.2$\pm$2.4 |  24.9$\pm$1.3 |  128.8$\pm$1.2 |  39.4$\pm$51.6 |  4.8$\pm$2.4 |  365$\pm$463 |  137$\pm$191
(c) Schema-based, semantic inputs
$\mathbf{D_{1}}$ |  8$\pm$3 |  31$\pm$28 |  14$\pm$6 |  1.9$\pm$.1 |  9$\pm$3 |  9$\pm$2 |  72$\pm$50 |  11$\pm$5
$\mathbf{D_{2}}$ |  9$\pm$0 |  58$\pm$22 |  23$\pm$1 |  1.1$\pm$.0 |  70$\pm$30 |  80$\pm$30 |  215$\pm$89 |  521$\pm$561
$\mathbf{D_{3}}$ |  30$\pm$2 |  43$\pm$9 |  92$\pm$3 |  2.1$\pm$.0 |  39$\pm$0 |  320$\pm$255 |  2.5s$\pm$.0s |  4.5s$\pm$1.5s
$\mathbf{D_{4}}$ |  40$\pm$1 |  65$\pm$13 |  147$\pm$16 |  2.0$\pm$.0 |  65$\pm$14 |  54$\pm$7 |  2.2s$\pm$1.4s |  250$\pm$194
$\mathbf{D_{5}}$ |  199$\pm$5 |  280$\pm$16 |  700$\pm$22 |  2.8$\pm$.0 |  230$\pm$19 |  517$\pm$401 |  1.8s$\pm$.8s |  441$\pm$180
$\mathbf{D_{6}}$ |  486$\pm$336 |  372$\pm$12 |  816$\pm$54 |  3.2$\pm$.2 |  660$\pm$412 |  1.1s$\pm$1.1s |  3.6s$\pm$2.5s |  3.9s$\pm$4.9s
$\mathbf{D_{7}}$ |  2.1s$\pm$4.1s |  1.1s$\pm$1.3s |  1.2s$\pm$.1s |  3.3$\pm$.2 |  2.8s$\pm$5.6 |  3.0s$\pm$5.6s |  7.0s$\pm$10.9s |  15s$\pm$33s
$\mathbf{D_{8}}$ | - | - | - | - | - | - | - | -
$\mathbf{D_{9}}$ |  1.1s$\pm$.1 |  1.3s$\pm$.1s |  2.0s$\pm$.3s |  148.6$\pm$3.3 |  1.4s$\pm$.1 |  24s$\pm$11s |  46s$\pm$18s |  4.8s$\pm$1.8s
$\mathbf{D_{10}}$ | - | - | - | - | - | - | - | -
(d) Schema-agnostic, semantic inputs

Regarding QT(2), there are two main factors that affect the reported run-
times: (i) the time complexity of the algorithms, and (ii) the similarity
threshold used for pruning the search space. Regarding the first factor, we
observe that the run-times in Table 6 verify the time complexities described
in Section 3. With $O(m)$, CNC and BMC are the fastest ones, followed by RSR
and EXC with $O(n\;m)$, RCA with $O(|V_{1}|\;|V_{2}|)$, UMC with $O(m\;\log
m)$ and KRC with $O(n+m\;\log m)$. BAH’s run-time is determined by the number
of search steps and the run-time limit.

Equally important is the effect of the similarity thresholds: the higher their
optimal value (i.e., the one maximizing F1) is, the fewer edges are retained
in the similarity graph and the faster is its processing. The optimal
similarity threshold depends on the type of edge weights and the size of the
similarity graph, as we explain in the threshold analysis in (Papadakis et
al., 2021). This means that the relative time efficiency of algorithms with
the same theoretical complexity should be attributed to their different
similarity threshold. For example, the average optimal thresholds for CNC and
BMC over all schema-based syntactic weights are 0.755 and 0.669, respectively,
while over schema-agnostic syntactic weights they are 0.409 and 0.327,
respectively. These large differences account for the significantly lower run-
time of CNC in almost all datasets for both cases. The larger the difference
in the similarity threshold, the larger is the difference in the run-times.

Note that the similarity threshold typically accounts for the relative run-
times that conflict with the relative time complexities, too: in case an
algorithm runs faster than another one with lower time complexity, this is
typically caused by the higher similarity threshold it employs. For example,
KRC exhibits a lower average run-time than EXC over $D_{9}$ for schema-based
syntactic weights, because their mean optimal similarity thresholds amount to
0.550 and 0.490, respectively. Similarly, UMC runs much faster than EXC over
$D_{8}$ with schema-agnostic syntactic weights, because their mean optimal
similarity thresholds amount to 0.427 and 0.387, respectively.

Finally, the similarity threshold accounts for the relative run-times between
the same algorithm over different types of edge weights. For example, EXC is
13 times slower over the schema-agnostic syntactic weights of $D_{10}$ than
their schema-based counterparts, even though the former involve just 25% more
edges than the latter, as reported in Table 3. This significant difference
should be attributed to the large deviation in the mean optimal thresholds:
0.153 for the former weights and 0.535 for the latter ones. The same applies
to UMC, whose average run-time increases by 20 times when comparing the
schema-based with the schema-agnostic weights, because its average optimal
threshold drops from 0.481 to 0.110.

To answer QT(3), Figure 4 presents the scalability analysis of every algorithm
over all similarity graphs for each type of edge weights. In each diagram,
every point corresponds to the run-time of a different similarity graph. We
observe that for all algorithms, the run-time increases linearly with the size
of the similarity graphs: as the number of edges increases by four orders of
magnitude, from $10^{4}$ to $10^{8}$, the run-times increase to a similar
extent in most cases. For all algorithms, though, there are outlier points
that deviate from the “central” curve. The larger the number of outliers is,
the less robust is the time efficiency of the corresponding algorithm, due to
its sensitivity to the size of the graph and the similarity threshold. In this
respect, the least robust algorithms are RSR over schema-based syntactic
weights along with UMC and EXC over schema-agnostic syntactic weights. These
patterns seem to apply to the semantic weights, too, despite the limited
number of the similarity graphs, especially in the case of schema-agnostic
settings.

Note that there are two exceptions to these patterns, namely RCA and BAH. The
diagrams of the former algorithm seem to involve a much lower number of
points, as its time complexity depends exclusively on the number of entities
in the input entity collections, i.e., $O(|V_{1}|\;|V_{2}|)$. As a result,
different similarity graphs from the same dataset yield similar run-times that
coincide in the diagrams of Figure 4. Regarding BAH, it exhibits a step-
resembling scalability graph, because its processing terminates after a pre-
defined timeout or a fixed number of iterations (whichever comes first),
independently of the size of the similarity graph.

Figure 5. F1-runtime diagram for all algorithms, but BAH over $D_{1}$.

Finally, to answer QT(4), Figure 5 depicts the trade-off between macro-
averaged F1 and run-time (RT) per algorithm and type of edge weights in
$D_{1}$. Note that every type corresponds to a different shape: circle stands
for the schema-agnostic syntactic weights, triangle for the schema-based
syntactic ones, rhombus for the schema-agnostic semantic ones and rectangle
for the schema-based semantic ones. We observe that the schema-based syntactic
similarity graphs dominate the other types of input, as they exhibit very high
F1 in combination with the lowest run-times. The former should be attributed
to the relatively clean values of names and phones for the duplicate entities
and the latter to the lack of attribute values for most non-matching entities.
As a result, the average size of these graphs is significantly lower than the
other types of graphs, especially the schema-agnostic ones, as shown in Table
3. Among the schema-based syntactic inputs, the differences in F1 are lower
than 4%, with UMC achieving the best trade-off between the two measures
(average F1=0.781 for average run-time=4 msec). This combination practically
dominates all others. Only CNC is significantly faster (RT=3 msec), but its F1
(0.756) is also significantly lower. For the patterns pertaining to rest of
the datasets, please refer to the extended version of the paper (Papadakis et
al., 2021).

Comparison with the best matching methods. We now compare the performance
achieved by bipartite graph matching algorithms with the recent state-of-the-
art matching methods: ZeroER (Wu et al., 2020), which leverages unsupervised
learning, and DITTO (Li et al., 2020), which is based on deep learning. We
consider the four common datasets, namely $D_{2}$-$D_{5}$ ($D_{1}$ is a larger
and noisier version of FZ in (Wu et al., 2020; Li et al., 2020), and thus not
directly comparable). Table 7 reports the relative performance in terms of
maximum F-Measure for ZeroER and DITTO, as it was reported reported in (Wu et
al., 2020) and (Li et al., 2020), respectively.

Bipartite matching is represented by UMC in combination with cosine similarity
over schema-agnostic vector models with TF-IDF weights; the best
representation model and the corresponding similarity threshold depend on the
dataset. These settings do not necessarily correspond to the highest F-Measure
across all algorithms and similarity graphs we have considered, but
demonstrate the capabilities of bipartite matching when varying just two
configuration parameters. The results appear in Table 7.

Compared to ZeroER, we observe that UMC consistently achieves higher
performance: its F1 is higher by 3%, 9%, 25% and 83% over $D_{4}$, $D_{5}$,
$D_{3}$ and $D_{2}$, respectively. Compared to DITTO, UMC achieves identical
performance over $D_{4}$ and 2% lower F1 over $D_{5}$. The difference is much
larger over $D_{3}$, where UMC underperforms by 21%, due to the contextual
evidence captured by the training set and the RoBERTa language model (Liu et
al., 2019) that lies at the core of DITTO. Note, though, that the difference
is reduced to 12%, when considering the best schema-based configuration of UMC
(the Overlap Coefficient of the tokens of the “Title” attribute with a
similarity threshold of 0.3). For $D_{2}$, UMC outperforms DITTO by 7%.

Overall, we can conclude that bipartite graph matching underperforms the best
(deep learning-based) performance in the literature in just one out of four
benchmark datasets.

Table 7. Comparison to state-of-the-art matching methods. | ZeroER | DITTO | UMC (schema-agnostic TF-IDF weights, cosine sim.)
---|---|---|---
$D_{2}$ | 0.52 | 0.89 |  0.95 (character bi-grams, $t=0.35$)
$D_{3}$ | 0.48 | 0.76 |  0.60 (token bi-grams, $t=0.05$)
$D_{4}$ | 0.96 | 0.99 |  0.99 (token uni-grams, $t=0.40$)
$D_{5}$ | 0.86 | 0.96 |  0.94 (character four-grams, $t=0.35$)

##  7\. Conclusions

We draw the following important patterns from our experiments:

(i) The best performing algorithm for a particular similarity graph mainly
depends on the type of edge weights and the portion of duplicates with respect
to the total number of nodes/entities.

(ii) CNC constitutes the fastest algorithm, due to its simplicity and the high
similarity thresholds it employs, achieving the highest precision at the cost
of low recall. It frequently outperforms all other algorithms with respect to
F1 in the case of scarce entity collections with syntactic weights, especially
the schema-agnostic ones.

(iii) RSR is a fast algorithm that rarely achieves high effectiveness, in the
case of scarce entity collections.

(iv) RCA is an efficient method that never excels in effectiveness.

(v) BAH constitutes a slow, stochastic approach that is capable of the best
and the worst. It frequently achieves, by far, the highest F1 over balanced
entity collections (and rarely over scarce ones), but in most cases, it yields
the lowest scores with respect to all effectiveness measures.

(vi) BMC is the second fastest algorithm that tries to balance precision and
recall, being particularly effective in the case of scarce entity collections,
especially in combination with syntactic weights.

(vii) EXC improves BMC by boosting precision at the cost of lower recall and
higher run-time. It consistently achieves (close to) the maximum F1 over
scarce and one-sided entity collections, losing only to KRC and (rarely) to
UMC. Given, though, that it outperforms both algorithms to a significant
extent with respect to run-time, it constitutes the best choice for
applications requiring both high effectiveness and efficiency/scalability.

(viii) KRC achieves very high or the highest effectiveness in most cases,
especially over one-sided and scarce entity collections. This comes, though,
at the cost of higher (yet stable) run-times than its top-performing
counterparts.

(ix) UMC is the best choice for balanced entity collections, especially when
coupled with syntactic weights, exhibiting a much more robust performance than
BAH. It achieves very high (and frequently the highest) effectiveness in the
rest of the cases, too. Its run-time, though, is rather unstable, depending
largely on the optimal similarity threshold.

###### Acknowledgements.

This project has received funding from the Hellenic Foundation for Research
and Innovation (HFRI) and the General Secretariat for Research and Technology
(GSRT), under grant agreement No 969.

## References

  * (1)
  * Assi et al. (2019) Ali Assi, Hamid Mcheick, and Wajdi Dhifli. 2019.  BIGMAT: A Distributed Affinity-Preserving Random Walk Strategy for Instance Matching on Knowledge Graphs. In _IEEE Big Data_. 1028–1033.
  * Bojanowski et al. (2017) Piotr Bojanowski, Edouard Grave, Armand Joulin, and Tomás Mikolov. 2017.  Enriching Word Vectors with Subword Information.  _Trans. Assoc. Comput. Linguistics_ 5 (2017), 135–146.
  * Brunner and Stockinger (2020) Ursin Brunner and Kurt Stockinger. 2020.  Entity Matching with Transformer Architectures - A Step Forward in Data Integration. In _EDBT_. 463–473.
  * Christen (2012) Peter Christen. 2012\.  _Data Matching - Concepts and Techniques for Record Linkage, Entity Resolution, and Duplicate Detection_.  Springer.
  * Christophides et al. (2021) Vassilis Christophides, Vasilis Efthymiou, Themis Palpanas, George Papadakis, and Kostas Stefanidis. 2021.  An Overview of End-to-End Entity Resolution for Big Data.  _ACM Comput. Surv._ 53, 6 (2021), 127:1–127:42.
  * Dasgupta et al. (2008) Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh V. Vazirani. 2008.  _Algorithms_.  McGraw-Hill.
  * Demsar (2006) Janez Demsar. 2006\.  Statistical Comparisons of Classifiers over Multiple Data Sets.  _J. Mach. Learn. Res._ 7 (2006), 1–30.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In _NAACL-HLT_. 4171–4186.
  * Dong and Srivastava (2015) Xin Luna Dong and Divesh Srivastava. 2015.  _Big Data Integration_.  Morgan & Claypool Publishers.
  * Efthymiou et al. (2019) Vasilis Efthymiou, George Papadakis, Kostas Stefanidis, and Vassilis Christophides. 2019.  MinoanER: Schema-Agnostic, Non-Iterative, Massively Parallel Resolution of Web Entities. In _EDBT_. OpenProceedings.org, 373–384.
  * Fellegi and Sunter (1969) I. P. Fellegi and A. B. Sunter. 1969.  A Theory for Record Linkage.  _J. Amer. Statist. Assoc._ 64, 328 (1969), 1183–1210.
  * Fredman and Tarjan (1987) Michael L. Fredman and Robert Endre Tarjan. 1987.  Fibonacci heaps and their uses in improved network optimization algorithms.  _J. ACM_ 34, 3 (1987), 596–615.
  * Gale and Shapley (1962) D. Gale and L. S. Shapley. 1962.  College Admissions and the Stability of Marriage.  _Am. Math. Mon._ 69, 1 (1962), 9–15.
  * Gemmell et al. (2011) Jim Gemmell, Benjamin I. P. Rubinstein, and Ashok K. Chandra. 2011\.  Improving Entity Resolution with Global Constraints.  _CoRR_ abs/1108.6016 (2011).
  * Giannakopoulos et al. (2008) George Giannakopoulos, Vangelis Karkaletsis, George A. Vouros, and Panagiotis Stamatopoulos. 2008\.  Summarization system evaluation revisited: N-gram graphs.  _ACM Trans. Speech Lang. Process._ 5, 3 (2008), 5:1–5:39.
  * Giannakopoulos and Palpanas (2010) George Giannakopoulos and Themis Palpanas. 2010.  Content and type as orthogonal modeling features: a study on user interest awareness in entity subscription services.  _International Journal of Advances on Networks and Services_ 3, 2 (2010).
  * Gotoh (1982) Osamu Gotoh. 1982\.  An improved algorithm for matching biological sequences.  _Journal of molecular biology_ 162, 3 (1982), 705–708.
  * Gutierrez and Sequeda (2020) Claudio Gutierrez and Juan F. Sequeda. 2020.  _Knowledge Graphs: A Tutorial on the History of Knowledge Graph’s Main Ideas_.  Association for Computing Machinery, 3509–3510.  https://doi.org/10.1145/3340531.3412176
  * Hassanzadeh et al. (2009) Oktie Hassanzadeh, Fei Chiang, Renée J. Miller, and Hyun Chul Lee. 2009.  Framework for Evaluating Clustering Algorithms in Duplicate Detection.  _Proc. VLDB Endow._ 2, 1 (2009), 1282–1293.
  * Herbold (2020) Steffen Herbold. 2020\.  Autorank: A Python package for automated ranking of classifiers.  _Journal of Open Source Software_ 5, 48 (2020), 2173\.
  * Király (2013) Zoltán Király. 2013\.  Linear Time Local Approximation Algorithm for Maximum Stable Marriage.  _Algorithms_ 6, 3 (2013), 471–484.
  * Konda et al. (2016) Pradap Konda, Sanjib Das, Paul Suganthan G. C., AnHai Doan, Adel Ardalan, Jeffrey R. Ballard, Han Li, Fatemah Panahi, Haojun Zhang, Jeffrey F. Naughton, Shishir Prasad, Ganesh Krishnan, Rohit Deep, and Vijay Raghavendra. 2016\.  Magellan: Toward Building Entity Matching Management Systems.  _Proc. VLDB Endow._ 9, 12 (2016), 1197–1208.
  * Köpcke et al. (2010) Hanna Köpcke, Andreas Thor, and Erhard Rahm. 2010\.  Evaluation of entity resolution approaches on real-world match problems.  _Proc. VLDB Endow._ 3, 1 (2010), 484–493.
  * Kriege et al. (2019) Nils M. Kriege, Pierre-Louis Giscard, Franka Bause, and Richard C. Wilson. 2019.  Computing Optimal Assignments in Linear Time for Approximate Graph Matching. In _ICDM_. 349–358.
  * Kuhn and Yaw (1955) H. W. Kuhn and Bryn Yaw. 1955.  The Hungarian method for the assignment problem.  _Naval Res. Logist. Quart_ (1955), 83–97.
  * Kurtzberg (1962) Jerome M Kurtzberg. 1962\.  On approximation methods for the assignment problem.  _Journal of the ACM (JACM)_ 9, 4 (1962), 419–439.
  * Lan et al. (2020) Zhenzhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Soricut. 2020\.  ALBERT: A Lite BERT for Self-supervised Learning of Language Representations. In _ICLR_.
  * Li et al. (2020) Yuliang Li, Jinfeng Li, Yoshihiko Suhara, AnHai Doan, and Wang-Chiew Tan. 2020.  Deep Entity Matching with Pre-Trained Language Models.  _Proc. VLDB Endow._ 14, 1 (2020), 50–60.
  * Li et al. (2021) Yuliang Li, Jinfeng Li, Yoshihiko Suhara, Jin Wang, Wataru Hirota, and Wang-Chiew Tan. 2021\.  Deep Entity Matching: Challenges and Opportunities.  _ACM J. Data Inf. Qual._ 13, 1 (2021), 1:1–1:17.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  RoBERTa: A Robustly Optimized BERT Pretraining Approach.  _CoRR_ abs/1907.11692 (2019).
  * Lovasz and Plummer ([n.d.]) L. Lovasz and M. D. Plummer. [n.d.].  _Matching theory_.
  * Malliaros et al. (2018) Fragkiskos D. Malliaros, Polykarpos Meladianos, and Michalis Vazirgiannis. 2018.  Graph-based Text Representations: Boosting Text Mining, NLP and Information Retrieval with Graphs. In _WWW Tutorials_.
  * Manning et al. (2008) Christopher D. Manning, Prabhakar Raghavan, and Hinrich Schütze. 2008.  _Introduction to information retrieval_.  Cambridge University Press.
  * Melnik et al. (2002) Sergey Melnik, Hector Garcia-Molina, and Erhard Rahm. 2002\.  Similarity Flooding: A Versatile Graph Matching Algorithm and Its Application to Schema Matching. In _ICDE_. 117–128.
  * Mikolov et al. (2013) Tomás Mikolov, Ilya Sutskever, Kai Chen, Gregory S. Corrado, and Jeffrey Dean. 2013.  Distributed Representations of Words and Phrases and their Compositionality. In _NIPS_. 3111–3119.
  * Mudgal et al. (2018) Sidharth Mudgal, Han Li, Theodoros Rekatsinas, AnHai Doan, Youngchoon Park, Ganesh Krishnan, Rohit Deep, Esteban Arcaute, and Vijay Raghavendra. 2018.  Deep Learning for Entity Matching: A Design Space Exploration. In _SIGMOD_. 19–34.
  * Nemenyi (1963) P. Nemenyi. 1963\.  _Distribution-free Multiple Comparisons_.  Princeton University.
  * Obraczka et al. (2021) Daniel Obraczka, Jonathan Schuchart, and Erhard Rahm. 2021\.  EAGER: Embedding-Assisted Entity Resolution for Knowledge Graphs.  _CoRR_ abs/2101.06126 (2021).
  * Otto and Reichert (2010) Boris Otto and Andreas Reichert. 2010.  Organizing Master Data Management: Findings from an Expert Survey. In _Proceedings of the 2010 ACM Symposium on Applied Computing (SAC)_. 106–110.  https://doi.org/10.1145/1774088.1774111
  * Papadakis et al. (2021) George Papadakis, Vasilis Efthymiou, Emanouil Thanos, and Oktie Hassanzadeh. 2021.  Bipartite Graph Matching Algorithms for Entity Resolution: An Empirical Evaluation.  arXiv:2112.14030 https://arxiv.org/abs/2112.14030
  * Papadakis et al. (2016) George Papadakis, George Giannakopoulos, and Georgios Paliouras. 2016\.  Graph vs. bag representation models for the topic classification of web documents.  _World Wide Web_ 19, 5 (2016), 887–920.
  * Papadakis et al. (2020a) George Papadakis, Georgios M. Mandilaras, Luca Gagliardelli, Giovanni Simonini, Emmanouil Thanos, George Giannakopoulos, Sonia Bergamaschi, Themis Palpanas, and Manolis Koubarakis. 2020a.  Three-dimensional Entity Resolution with JedAI.  _Inf. Syst._ 93 (2020), 101565.
  * Papadakis et al. (2020b) George Papadakis, Dimitrios Skoutas, Emmanouil Thanos, and Themis Palpanas. 2020b.  Blocking and Filtering Techniques for Entity Resolution: A Survey.  _ACM Comput. Surv._ 53, 2 (2020), 31:1–31:42.  https://doi.org/10.1145/3377455
  * Pennington et al. (2014) Jeffrey Pennington, Richard Socher, and Christopher D. Manning. 2014.  Glove: Global Vectors for Word Representation. In _EMNLP_. 1532–1543.
  * Rousseau and Vazirgiannis (2013) François Rousseau and Michalis Vazirgiannis. 2013.  Graph-of-word and TW-IDF: new approach to ad hoc IR. In _CIKM_. 59–68.
  * Saeedi et al. (2018a) Alieh Saeedi, Markus Nentwig, Eric Peukert, and Erhard Rahm. 2018a.  Scalable Matching and Clustering of Entities with FAMER.  _Complex Syst. Informatics Model. Q._ 16 (2018), 61–83.
  * Saeedi et al. (2018b) Alieh Saeedi, Eric Peukert, and Erhard Rahm. 2018b.  Using Link Features for Entity Clustering in Knowledge Graphs. In _ESWC_ _(Lecture Notes in Computer Science)_ , Vol. 10843. Springer, 576–592.
  * Schwartz et al. (2005) Justus Schwartz, Angelika Steger, and Andreas Weißl. 2005\.  Fast Algorithms for Weighted Bipartite Matching. In _WEA_ _(Lecture Notes in Computer Science)_ , Vol. 3503. 476–487.
  * Wang et al. (2019) Yansheng Wang, Yongxin Tong, Cheng Long, Pan Xu, Ke Xu, and Weifeng Lv. 2019\.  Adaptive Dynamic Bipartite Graph Matching: A Reinforcement Learning Approach. In _ICDE_. 1478–1489.
  * Wang et al. (2020) Zhengyang Wang, Bunyamin Sisman, Hao Wei, Xin Luna Dong, and Shuiwang Ji. 2020.  CorDEL: A Contrastive Deep Learning Approach for Entity Linkage. In _ICDM_.
  * Watkins and Dayan (1992) Christopher J. C. H. Watkins and Peter Dayan. 1992.  Technical Note Q-Learning.  _Mach. Learn._ 8 (1992), 279–292.
  * Wijaya and Bressan (2009) Derry Tanti Wijaya and Stéphane Bressan. 2009.  Ricochet: A family of unconstrained algorithms for graph clustering. In _International Conference on Database Systems for Advanced Applications_. Springer, 153–167.
  * Winkler (2006) W. E. Winkler. 2006\.  _Overview of Record Linkage and Current Research Directions_.  Technical Report. Bureau of the Census.
  * Wu et al. (2020) Renzhi Wu, Sanya Chaba, Saurabh Sawlani, Xu Chu, and Saravanan Thirumuruganathan. 2020\.  ZeroER: Entity Resolution using Zero Labeled Examples. In _SIGMOD_. 1149–1164.

## Appendix

##  Appendix A Algorithms

Ricochet Sequential Rippling Clustering (RSR). This algorithm, outlined in
Algorithm 1, is an adaptation of the homonymous method for Dirty ER in
(Hassanzadeh et al., 2009) such that it exclusively considers partitions with
just one entity from each input dataset. Initially, RSR sorts all nodes from
both input datasets in descending order of the average weight of their
adjacent edges (Line 7). Whenever a new seed is chosen from the sorted list,
we consider all its adjacent edges with a weight higher than $t$ (Lines 8-11).
The first adjacent vertex that is currently unassigned or is closer to the new
seed than it is to the seed of its current partition is re-assigned to the new
partition (Lines 14-16). If a partition is reduced to a singleton after a re-
assignment, either because the chosen vertex (Line 17) or the seed (Line 24)
was previously in it, it is placed in its nearest single-node partition (Lines
30-39).

The algorithm stops when all nodes have been considered. In the worst case the
algorithm has to iterate through $n$ vertices and each time reassign $n$
vertices to their most similar adjacent vertex, therefore its time complexity
is $O(n\;m)$ (Wijaya and Bressan, 2009).

Input: Similarity Graph $G=(V_{1},V_{2},E)$, similarity threshold $t$

Output: A set of Partitions $C=\\{c_{1},c_{2},\ldots,c_{n}\\}$

1 $C\leftarrow\emptyset$

2 $Center\leftarrow\emptyset$

3 foreach  _$v\in(V_{1}\cup V_{2})$_ do // Initialization

4 $simWithCenter(v)\leftarrow 0$

5 $Partition(v)\leftarrow\emptyset$

6 $centerOf(v)\leftarrow v$

$Q\leftarrow G.nodesInDecWeight(v,w(v))$

// $w(v)=\sum_{e\in adj(v)}{e.sim}/|adj(v)|$

7 while  _$Q\neq\emptyset$_ do

$v_{i}\leftarrow Q.pop()$

// the vertex with highest weight

8 $ToReassign\leftarrow\emptyset$

9 foreach  _ $e=(v_{i},v_{j},sim)\in E:sim>t$_ do // for $v_{i}$’s adjacent
edges

10 if  _$v_{j}\in Center$_ then

11 continue

12

13 if  _$e.sim >simWithCenter(v_{j})$_ then

$Partition(centerOf(v_{j})).remove(v_{j})$

// remove $v_{j}$ from its previous partition

14 $Partition(v_{i})\leftarrow Partition(v_{i})\cup v_{j}$

$ToReassign\leftarrow ToReassign\cup centerOf(v_{j})$

// it is now a singleton

15 $simWithCenter(v_{j})\leftarrow e.sim$

16 $centerOf(v_{j})\leftarrow v_{i}$

17 break

18

19

20 if  _$|Partition(v_{i})| >0$_ then

if  _$centerOf(v_{i})\neq v_{i}$_ then

// if $v_{i}$ was previously in another partition

21

22 $Partition(centerOf(v_{i})).remove(v_{i})$

23 $ToReassign\leftarrow ToReassign\cup centerOf(v_{i})$

24

25 $Center\leftarrow Center\cup v_{i}$

$Partition(v_{i})\leftarrow Partition(v_{i})\cup v_{i}$

// put $v_{i}$ in its partition

26 $centerOf(v_{i})\leftarrow v_{i}$

27 $simWithCenter(v_{i})\leftarrow 1$

28

29 foreach  _$v_{k}\in ToReassign$_ do

30 $maxSim\leftarrow 0$

31 $cMax\leftarrow v_{k}$

32 foreach  _$e=(v_{k},v_{\ell},sim)\in E:sim >t$_ do // find singleton with
the highest similarity with $v_{k}$ to reassign it

33 if  _$e.sim >maxSim$ and $|Partition(v_{\ell})|<2$_ then

34 $cMax\leftarrow v_{\ell}$

35 $maxSim\leftarrow e.sim$

36

37

38 if  _$maxSim >0$_ then

39 $Partition(v_{k})\leftarrow\emptyset$

40 $Partition(cMax)\leftarrow Partition(cMax)\cup v_{k}$

41

42

43

44foreach  _$v_{i}\in(V_{1}\cup V_{2})$_ do

45 if  _$|Partition(v_{i})| >0$_ then

46 $C\leftarrow C\cup Partition(v_{i})$

47

return $C$

Algorithm 1 Ricochet SR Clustering (RSR)

Connected Components (CNC). This is the simplest algorithm for bipartite graph
matching and is outlined in Algorithm 2. First, it discards all edges with a
weight lower than the given similarity threshold (Lines 1-3). Then, it
computes the transitive closure of the pruned similarity graph (Line 4). In
the output, it solely retains the partitions that contain two entities – one
from each input dataset (Lines 6-8). Using a simple depth-first approach, its
time complexity is $O(n+m)\sim O(m)$, given that $m\gg n$ (Dasgupta et al.,
2008).

Input: Similarity Graph $G=(V_{1},V_{2},E)$, similarity threshold $t$

Output: A set of clusters $C=\\{c_{1},c_{2},\ldots,c_{n}\\}$

1

2foreach  _$e=(v_{i},v_{j},sim)\in E$_ do

3 if  _$sim <t$_ then

4 $E\leftarrow E-(e)$

5

6

7

8$C_{1}\leftarrow transitiveClosure(G)$

9

10$C\leftarrow\emptyset$

11 foreach  _$c_{i}\in C_{1}$_ do

12 if  _$|c_{i}|==2\wedge c_{i}\cap V1\neq\emptyset\wedge c_{i}\cap
V2\neq\emptyset$_ then

13 $C\leftarrow C\cup\\{c_{i}\\}$

14

15

return $C$

Algorithm 2 Connected Components (CNC)

Row Column Assignment Clustering (RCA). This approach, outlined in Algorithm
3, is based on the Row-Column Scan approximation method in (Kurtzberg, 1962)
that solves the assignment problem. It requires two passes of the similarity
graph, with each pass generating a candidate solution. In the first pass, each
entity from the source dataset creates a new partition, to which the most
similar, currently unassigned entity from the target dataset is assigned
(Lines 7-17). Note that, in principle, any pair of entities can be assigned to
the same partition at this step even if their similarity is lower than $t$,
since the assignment problem assumes that each vertex from $V1$ is connected
to all vertices from $V2$ (any ”job” can be performed by all ”men”). In the
second pass, the same procedure is applied to the entities/nodes of the target
dataset (Lines 18-28). The value of each solution is the sum of the edge
weights between the nodes assigned to the same (2-node) partition (Lines
17,28). The solution with the highest value is returned as output, after
discarding the pairs with similarity less than $t$ (Lines 29-36).

At each pass the algorithm iterates over all nodes/entities of one of the
entity collection searching for the node/entity with maximum similarity from
the other entity collection. Therefore, its time complexity is
$O(|V1|\;|V2|)$.

Input: Similarity Graph $G=(V_{1},V_{2},E)$, similarity threshold $t$

Output: A set of partitions $C=\\{c_{1},c_{2},\ldots,c_{n}\\}$

1 $C_{1}\leftarrow\emptyset$

2 $C_{2}\leftarrow\emptyset$

$M_{1}\leftarrow\emptyset$

// matched nodes from $V_{1}$

$M_{2}\leftarrow\emptyset$

// matched nodes from $V_{2}$

$D_{1}\leftarrow 0$

// assignment value of $C_{1}$

$D_{2}\leftarrow 0$

// assignment value of $C_{2}$

3 foreach  _$v_{i}\in V_{1}$_ do

$c_{i}\leftarrow\\{v_{i}\\}$

// create a new partition containing $v_{i}$

$Q_{i}\leftarrow V_{2}(sim(v_{i}))$

// a priority queue of $V_{2}$’s nodes in decreasing sim with $v_{i}$

4 while  _$Q_{i}\neq\emptyset$_ do

5 $v_{2}\leftarrow Q_{i}.pop()$

6 if  _$v_{2}\notin M_{2}$_ then // if $v_{2}$ is not yet matched

$c_{i}\leftarrow c_{i}\cup\\{v_{2}\\}$

// add $v_{2}$ to partition $c_{i}$

7 $M_{2}\leftarrow M_{2}\cup\\{v_{2}\\}$

8 $D_{1}\leftarrow D_{1}+\\{sim(v_{1},v_{2})\\}$

9 break

10

11 $C_{1}\leftarrow C_{1}\cup\\{c_{i}\\}$

12

13foreach  _$v_{j}\in V_{2}$_ do

$c_{j}\leftarrow\\{v_{j}\\}$

// create a new partition containing $v_{j}$

$Q_{j}\leftarrow V_{1}(sim(v_{j}))$

// a priority queue of $V_{1}$’s nodes in decreasing sim with $v_{j}$

14 while  _$Q_{j}\neq\emptyset$_ do

15 $v_{1}\leftarrow Q_{j}.pop()$

16 if  _$v_{1}\notin M_{1}$_ then // if $v_{1}$ is not yet matched

$c_{j}\leftarrow c_{j}\cup\\{v_{1}\\}$

// add $v_{1}$ to partition $c_{j}$

17 $M_{1}\leftarrow M_{1}\cup\\{v_{1}\\}$

18 $D_{2}\leftarrow D_{2}+\\{sim(v_{1},v_{2})\\}$

19 break

20

21 $C_{2}\leftarrow C_{2}\cup\\{c_{j}\\}$

22

23if  _$D_{1} >D_{2}$_ then // get maximal assignment

24 $C=C_{1}$

25

26else

27 $C=C_{2}$

28

29foreach  _$c=\\{v_{i},v_{j}\\}\in C$_ do

30 if  _$sim(v_{i},v_{j}) <t$_ then // check similarities

$C=C\setminus c$ // remove partition pairs with similarity less than $t$

31

32

return $C$

Algorithm 3 Row Column Clustering (RCA)

Best Assignment Heuristic (BAH). This algorithm applies a simple swap-based
random-search algorithm to heuristically solve the Maximum Weight Bipartite
Matching problem and uses the resulting solution to create the output
partitions. Its functionality is outlined in Algorithm 4. Initially, each
entity from the smaller input dataset is connected to an entity from the
larger input dataset (Line 9). In each iteration of the search process (Line
10), two entities from the larger dataset are randomly selected (Lines 12-13)
in order to swap their current connections. If the sum of the edge weights of
the new pairs is higher than the previous pairs (Line 15-19), the swap is
accepted (Lines 20-24). The algorithm stops when a maximum number of search
steps is reached or when a maximum run-time has been exceeded. In our case,
the run-time has been set to 2 minutes.

Input: Similarity Graph $G=(V_{1},V_{2},E):|V_{1}|>|V_{2}|$, similarity
threshold $t$, max number of moves $maxNumMoves$

Output: A set of partitions $C=\\{c_{1},c_{2},\ldots,c_{n}\\}$

1 $C\leftarrow\emptyset$

2 $numMoves\leftarrow 0$

3 foreach  _$(v^{1}_{i},v^{2}_{j})\in(V_{1}\times V_{2})$ _ do

$d(v^{1}_{i},v^{2}_{j})\leftarrow 0$

// initialize pair contributions

4

5foreach  _$e=(v^{1}_{i},v^{2}_{j},sim)\in E$ , with $e.sim$ ¿ $t$_ do

$d(v^{1}_{i},v^{2}_{j})\leftarrow sim$

// initialize pair contributions

6

7foreach  _$v^{1}_{i}\in V_{1},v^{2}_{i}\in V_{2}:i\leq|V_{2}|$_ do

$c_{i}\leftarrow\\{v^{1}_{i},v^{2}_{i}\\}$

// initialize partitions

8 $p(v^{1}_{i})=v^{2}_{i}$

9

10

11while  _$numMoves <maxNumMoves$_ do

12 $numMoves\leftarrow numMoves+1$

13 $i=nextRand(|V_{1}|)$

14 $j=nextRand(|V_{1}|):j\neq i$

15 $D\leftarrow 0$

16 if  _$p(v^{1}_{i})\neq null$_ then // check swaps

17 $D\leftarrow d(v^{1}_{j},p(v^{1}_{i}))-d(v^{1}_{i},p(v^{1}_{i}))$

18 if  _$p(v^{1}_{j})\neq null$_ then // check swaps

19 $D\leftarrow D+d(v^{1}_{i},p(v^{1}_{j}))-d(v^{1}_{j},p(v^{1}_{j}))$

20 if  _$D\geq 0$_ then // if swaps increase assignment value

$temp\leftarrow p(v^{1}_{j})$

// perform swaps

21 $p(v^{1}_{j})\leftarrow p(v^{1}_{i})$

22 $p(v^{1}_{i})\leftarrow temp$

23 $c_{i}\leftarrow\\{v^{1}_{i},p(v^{1}_{i})\\}$

24 $c_{j}\leftarrow\\{v^{1}_{j},p(v^{1}_{j})\\}$

25

26

27

return $C$

Algorithm 4 Best Assignment Heuristic (BAH)

Best Match Clustering (BMC). This algorithm is inspired from the Best Match
strategy of (Melnik et al., 2002), which solves the Stable Marriage problem
(Gale and Shapley, 1962), as simplified in BigMat (Assi et al., 2019). Its
functionality is outlined in Algorithm 5. For each entity of the one dataset,
this algorithm creates a new partition (Lines 4-5), in which the most similar,
not-yet-clustered entity from the other dataset is also placed - provided that
the corresponding edge weight is higher than $t$ (Lines 6-12). Note that the
greedy heuristic for BMC introduced in (Melnik et al., 2002) is the same, in
principle, to Unique Mapping Clustering (see below). Note also that BMC is the
only algorithm with an additional configuration parameter, apart from the
similarity threshold: the input dataset that is used as the basis for creating
partitions can be set to the source or the target dataset. In our experiments,
we examine both options and retain the best one.

The algorithm iterates over the nodes of one of the datasets searching for its
adjacent vertex with maximum similarity, therefore its time complexity is
$O(m)$.

Input: Similarity Graph $G=(V_{1},V_{2},E)$, similarity threshold $t$

Output: A set of clusters $C=\\{c_{1},c_{2},\ldots,c_{n}\\}$

1 $C\leftarrow\emptyset$

$M_{2}\leftarrow\emptyset$

// matched nodes from $V_{2}$

2

3foreach  _$v_{i}\in V_{1}$_ do

$c_{i}\leftarrow\\{v_{i}\\}$

// create a new cluster containing $v_{i}$

$Q_{i}\leftarrow v_{i}.edgesDecOrder(t)$

// edges in desc. sim > $t$

4 while  _$Q_{i}\neq\emptyset$_ do

5 $e\leftarrow Q_{i}.pop()$

6 if  _$e.v_{2}\notin M_{2}$_ then // if $v_{2}$ is not yet matched

$c_{i}\leftarrow c_{i}\cup\\{e.v_{2}\\}$

// add $v_{2}$ to cluster $c_{i}$

7 $M_{2}\leftarrow M_{2}\cup\\{e.v_{2}\\}$

8 break

9

10 $C\leftarrow C\cup\\{c_{i}\\}$

11

return $C$

Algorithm 5 Best Match Clustering (BMC)

Exact Clustering (EXC). This algorithm is inspired from the Exact strategy of
(Melnik et al., 2002). Its functionality is outlined in Algorithm 6.
Initially, it creates an empty priority queue for every vertex (Lines 2-5).
Then, it populates the queue of every vertex $v_{i}$ with all its adjacent
edges that exceed the given similarity threshold $t$, sorting them in
decreasing weight (Lines 6-8). Subsequently, EXC places two entities in the
same partition (Lines 9-16) only if they are mutually the best matches, i.e.,
the most similar candidates of each other (Line 14). This approach is
basically a stricter, symmetric version of BMC and could also be conceived as
a strict version of the reciprocity filter that was employed in (Efthymiou et
al., 2019).

Its time complexity is $O(n\;m)$, since the algorithm iterates over each
vertex of one dataset searching for its adjacent vertex with maximum
similarity and then performs the same search for the latter vertex.

Unique Mapping Clustering (UMC). This algorithm is outlined in Algorithm 8.
Initially, it iteraters over all edges and those with a weight higher than $t$
are placed in a priority queue that sorts them in decreasing weight/similarity
(Lines 5-7). Subsequently, it iteratively forms a partition (Line 11) for the
top-weighted pair (Line 9), as long as none of its entities has already been
matched to some other (Line 10). This approach relies on the unique mapping
constraint of CCER, i.e., the restriction that each entity from the one input
dataset matches at most one entity from the other. Note that the CLIP
Clustering algorithm, introduced for the multi-source ER problem in (Saeedi et
al., 2018b), is equivalent to UMC when there are only two input datasets
(i.e., in the CCER case that we study).

Its time complexity is $O(m\;logm)$, due to the cost that is required for
sorting all edges.

Király’s Clustering (KRC). This algorithm is an adaptation of the linear time
3/2 approximation to the Maximum Stable Marriage problem, called “New
Algorithm” in (Király, 2013). Intuitively, the entities of the source dataset
(“men” (Király, 2013)) propose to the entities (Line 16) from the target
dataset with an edge weight higher than $t$ (“women” (Király, 2013)) to form a
partition (“get engaged” (Király, 2013)). Its functionality is outlined in
Algorithm 7. The entities of the target dataset accept a proposal under
certain conditions (e.g., if it’s the first proposal they receive - Line 17),
and the partitions and preferences are updated accordingly (Lines 18, 22, 24).
Entities from the source dataset get a second chance to make proposals (Lines
5, 27-30) and the algorithm terminates when all entities of the first dataset
are in a partition (Line 13), or no more proposal chances are left (Line 27).
We omit some of the details (e.g., the rare case of “uncertain man”), due to
space restrictions, and refer the reader to (Király, 2013) for more
information (e.g., the acceptance criteria for proposals). Its time complexity
is $O(n+m\;logm)$ (Király, 2013).

Input: Similarity Graph $G=(V_{1},V_{2},E)$, similarity threshold $t$

Output: A set of clusters $C=\\{c_{1},c_{2},\ldots,c_{n}\\}$

1 $C\leftarrow\emptyset$

2

3foreach  _$v_{i}\in|V_{1}|$_ do

$Q1_{i}\leftarrow\emptyset$

// initialize a PQ in desc. sim

4

5foreach  _$v_{j}\in|V_{2}|$_ do

$Q2_{j}\leftarrow\emptyset$

// initialize a PQ in desc. sim

6

7

8foreach  _$e=(v_{i},v_{j},sim)\in E$ , with $e.sim$ ¿ $t$_ do

9 $Q1_{i}.push(e)$

10 $Q2_{j}.push(e)$

11

12

13foreach  _$v_{i}\in V_{1}$_ do

$c_{i}\leftarrow\\{v_{i}\\}$

// create a new cluster containing $v_{i}$

$e\leftarrow Q1_{i}.pop()$

// the best edge for $v_{i}$

$v_{j}\leftarrow e.v_{j}$

// the best match for $v_{i}$ is $v_{j}$

$e_{2}\leftarrow Q2_{j}.pop()$

// the best edge for $v_{j}$

14

15 if  _$e_{2}.v_{i}=v_{i}$_ then // if the best match for $v_{j}$ is $v_{i}$

$c_{i}\leftarrow c_{i}\cup\\{v_{j}\\}$

// add $v_{j}$ to cluster $c_{i}$

16 $C\leftarrow C\cup\\{c_{i}\\}$

17

18

return $C$

Algorithm 6 Exact Clustering (EXC)

Input: Similarity Graph $G=(V_{1},V_{2},E)$, similarity threshold $t$

Output: A set of clusters $C=\\{c_{1},c_{2},\ldots,c_{n}\\}$

1

2$C\leftarrow\emptyset$

$freeM\leftarrow\emptyset$

// an initially empty linked list

3

4foreach  _$v_{i}\in V_{1}$_ do // $V_{1}$ corresponds to men in (Király,
2013)

$Q1_{i}\leftarrow\emptyset$

// $v_{i}$’s edges in desc. sim > $t$

5 $lastChance[i]\leftarrow false$

$freeM.addLast(v_{i})$

// keeps insertion order

6

7foreach  _$v_{j}\in V_{2}$_ do // $V_{2}$ corresponds to women in (Király,
2013)

$Q2_{j}\leftarrow\emptyset$

// $v_{j}$’s edges in desc. sim > $t$

8 $fianc\acute{e}[j]\leftarrow null$

9

10foreach  _$e=(v_{i},v_{j},sim)\in E$ , with $e.sim$ ¿ $t$_ do

11 $Q1_{i}.push(e)$

12 $Q2_{j}.push(e)$

13

14while  _$freeM\neq\emptyset$_ do

$v_{i}\leftarrow freeM.removeFirst()$

// in insertion order

15 if  _$Q1_{i}\neq\emptyset$_ then

$v_{j}\leftarrow Q1_{i}.pop()$

// $v_{i}$’s preference is $v_{j}$

16 if  _$fianc\acute{e}[j]=null$_ then // $v_{j}$ is free

$C\leftarrow C\cup\\{\\{v_{i},v_{j}\\}\\}$

// match $v_{i}$ to $v_{j}$

17

18 else

$v_{i}^{\prime}\leftarrow fianc\acute{e}[j]$

// $v_{j}$ was engaged to $v_{i}^{\prime}$

19 if  _acceptsProposal( $v_{j}$, $v_{i}$)_ then // refer to (Király, 2013)

$C\leftarrow C\setminus\\{\\{v_{i}^{\prime},v_{j}\\}\\}$

// $v_{i}^{\prime}$ and $v_{j}$ break up

$freeM.addLast(v_{i}^{\prime})$

// $v_{i}^{\prime}$ is free again

$C\leftarrow C\cup\\{\\{v_{i},v_{j}\\}\\}$

// match $v_{i}$ to $v_{j}$

$fianc\acute{e}[j]\leftarrow v_{i}$

// $v_{j}$ gets engaged to $v_{i}$

20

21

22

23 else

24 if  _$lastChance(v_{i})=false$_ then

$lastChance[i]\leftarrow true$

// $2^{nd}$ chance for $v_{i}$

25 $Q1_{i}\leftarrow recoverInitialQueue(v_{i})$

26 $freeM.addLast(v_{i})$

27

28

29

return $C$

Algorithm 7 Király’s Clustering

Input: Similarity Graph $G=(V_{1},V_{2},E)$, similarity threshold $t$

Output: A set of clusters $C=\\{c_{1},c_{2},\ldots,c_{n}\\}$

1 $C\leftarrow\emptyset$

$M_{1}\leftarrow\emptyset$

// matched nodes from $V_{1}$

$M_{2}\leftarrow\emptyset$

// matched nodes from $V_{2}$

2 $Q\leftarrow\emptyset$

3 foreach  _$e=(v_{i},v_{j},sim)\in E$_ do

4 if  _e.sim ¿ t_ then

$Q.put(e)$

// a PQ of edges in desc. sim > $t$

5

6

7while  _$Q\neq\emptyset$_ do

$e\leftarrow Q.pop()$

// the entity pair with highest sim

8 if  _$e.v_{i}\notin M_{1}$ and $e.v_{j}\notin M_{2}$_ then // $v_{i}$,
$v_{j}$ not matched

9 $C\leftarrow C\cup\\{\\{e.v_{i},e.v_{j}\\}\\}$

10 $M_{1}\leftarrow M_{1}\cup\\{e.v_{i}\\}$

11 $M_{2}\leftarrow M_{2}\cup\\{e.v_{j}\\}$

12

13

return $C$

Algorithm 8 Unique Mapping Clustering

##  Appendix B Similarity Functions

In this section, we provide more details about the similarity measures
mentioned in Figure 6.

  1. (1)

For the schema-based syntactic representations, which involve short textual
values, we considered 16 established similarity measures: Cosine Similarity,
Block Distance, Levenshtein Distance, Damerau-Levenshtein Distance, Euclidean
Distance, Jaccard Similarity, Generalized Jaccard Similarity, Dice Similarity,
Overlap Coefficient, Jaro Similarity, Longest Common Subsequence, Longest
Common Substring, Monge-Elkan Similarity, Needleman-Wunch, q-grams Distance,
and Simon White Similarity.

  2. (2)

For the n-gram vectors, we used six similarity measures: Cosine and
Generalized Jaccard Similarity with both TF and TF-IDF weights, Enhanced
Jaccard Similarity with TF weights and ARCS Similarity with TF-IDF weights.

  3. (3)

For the n-gram graphs, we used four graph similarity measures: Containment,
Value, Normalized Value and Overall Similarity (i.e., the average of the three
measures) (Giannakopoulos et al., 2008).

  4. (4)

For the semantic models, we consider Cosine Similarity, Euclidean Similarity
(=1/(1+Euclidean distance)) and World Mover’s Similarity (=1/(1+World Mover’s
Distance)).

Each category of similarity functions is described in more detail in the
following.

###  B.1. Schema-based syntactic functions

For this category, we use the following similarity and distance measures, as
defined and implemented in Simmetrics.

####  B.1.1. Character-level measures.

The following similarity measures are applied to two strings $s_{1}$ and
$s_{2}$ at character level.

Levenshtein Distance: Counts the (minimum) number of insert, delete and
substitute operations required to transform one string into the other.

Damerau-Levenshtein Distance: Demerau-Levenshtein Distance only differs to
Levenshtein Distance by including transpositions among the operations allowed.

Jaro Similarity: The Jaro Similarity of two strings $s_{1}$ and $s_{2}$ is
given by the formula:

$similarity(s_{1},s_{2})=\begin{cases}0&\text{, if }m=0\\\
\frac{1}{3}\left(\frac{m}{|s_{1}|}+\frac{m}{|s_{2}|}+\frac{m-t}{m}\right)&\text{,
else,}\end{cases}$

where $m$ is the number of common characters, and $t$ is the number of
transpositions.

Figure 6. Taxonomy of the similarity functions we used to generate the
similarity graphs. We use $n\in\\{2,3,4\\}$ for character and
$n\in\\{1,2,3\\}$ for token n-grams for both vector and graph models, as in
(Papadakis et al., 2016). The graph similarities are defined in
(Giannakopoulos et al., 2008).

Needleman-Wunch: This similarity measure is the result of applying an
algorithm that assigns three scores (seen as parameters) to two sequences of
characters $s_{1}$ and $s_{2}$, depending on whether aligned characters are a
match, a mismatch, or a gap. A match occurs when the two aligned characters
are the same, a mismatch when they are not the same, and a gap when for the
aligned we need an insert or delete operation. The match, mismatch, gap scores
used in this study, as in Simmetrics, are 0, -1, and -2, respectively.

q-grams Distance: It applies a Block Distance (see below) similarity metric
over all tri-grams in a string.

Longest Common Substring Similarity: As the name suggests, this measure counts
the size of the longest common substring ($lcs_{str}$) between two strings,
divided by the size of the longest string:
$similarity(s_{1},s_{2})=|lcs_{str}(s_{1},s_{2})|/max(|s_{1}|,|s_{2}|)$.

Longest Common Subsequence Similarity: The difference between this measure and
the previous is that a subsequence does not need to consist of consecutive
characters:
$similarity(s_{1},s_{2})=|lcs_{seq}(s_{1},s_{2})|/max(|s_{1}|,|s_{2}|)$.

####  B.1.2. Word-level measures

The following similarity measures are applied to two strings $a$ and $b$ that
are treated as sets or multisets (bags) of words.

Cosine Similarity: The similarity is defined as the cosine of the angle
between the multisets (bags) of words $a$ and $b$ expressed as sparse vectors.
$similarity(a,b)=a\cdot b/(||a||\;||b||)$.

Euclidean Distance: Compares the frequency of occurrence of each word $w$ in
two strings $a$ and $b$
$distance(a,b)=||a-b||=\sqrt{\sum_{w}{(freqA(w)-freqB(w))^{2}}}$

Block Distance: Also known as L1 Distance, City Block Distance and Manhattan
Distance between two multisets (bags) of words $a$ and $b$ is the sum of the
absolute differences of the frequency of each word in $a$ vs in $b$:
$distance(a,b)=||a-b||_{1}$.

Overlap Coefficient: The size of the intersection divided by the smaller of
the size of the two sets of words: $similarity(a,b)=|a\cap b|/min(|a|,|b|)$.

Dice Similarity: The Dice Similarity is defined as twice the shared
information (intersection) divided by sum of cardinalities of the two sets of
words: $similarity(a,b)=2|a\cap b|/(|a|+|b|)$.

Simon White Similarity: This similarity is the same as Dice Similarity, with
the only difference being that it considers $a$ and $b$ as multisets (bags) of
words.

Jaccard Similarity: Computes the size of the intersection divided by the size
of the union for two sets of words $similarity(a,b)=|a\cap b|/|a\cup b|$.

Generalized Jaccard Similarity: Same as the Jaccard Similarity, except that
the Generalized Jaccard Similarity considers multisets (bags) of words,
instead of sets.

Monge-Elkan Similarity: This similarity is the average similarity of the most
similar words between two sets of words $a$ and $b$:
$similarity(a,b)=\frac{1}{|a|}\sum_{w_{i}\in a}{max_{w_{j}\in
b}\left(sim(w_{i},w_{j})\right)}$, where $sim$ is the optimized Smith-Waterman
algorithm (Gotoh, 1982) that operates as the secondary character-level
similarity to compute the similarity of individual words.

###  B.2. Schema-agnostic syntactic functions

For this category, we use the following similarity functions, as defined and
implemented in JedAI.

####  B.2.1. Bag Models (Manning et al., 2008)

There are two types of n-grams, the character and the token ones. These give
rise to two types of bag models: the character n-grams model and the token
n-grams model. Collectively, they are called bag or vector space models,
because they model an entity $e_{i}$ as a vector with one dimension for every
distinct n-gram in an entity collection $E$:
$BM(e_{i})=(w_{i1},\dots,w_{im})$, where $m$ stands for the dimensionality of
$E$ (i.e., the number of distinct n-grams in it), while $w_{ij}$ is the weight
of the $j^{th}$ dimension that quantifies the importance of the corresponding
n-gram for $e_{i}$.

The most common weighting schemes are:

_(i)_ Term Frequency (TF) sets weights in proportion to the number of times
the corresponding n-grams appear in the values of entity $e_{i}$. More
formally, $TF(t_{j},e_{i})$=$f_{j}/N_{e_{i}}$, where $f_{j}$ stands for the
occurrence frequency of $t_{j}$ in $e_{i}$, while $N_{e_{i}}$ is the number of
n-grams in $e_{i}$, normalizing TF so as to mitigate the effect of different
lengths on the weights.

_(ii)_ Term Frequency-Inverse Document Frequency (TF-IDF) discounts the TF
weight for the most common tokens in the entire entity collection $E$, as they
typically correspond to noise (i.e., stop words). Formally,
$TF$-$IDF(t_{j},e_{i})=TF(t_{j},e_{i})\cdot IDF(t_{j})$, where $IDF(t_{j})$ is
the inverse document frequency of the n-gram $t_{j}$, i.e.,
$IDF(t_{j})=\log{|E|/(|\\{e_{k}\in E:t_{j}\in e_{k}\\}|+1)}$. In this way,
high weights are given to n-grams with high frequency in $e_{i}$, but low
frequency in $E$.

To construct the bag model for a specific entity, we aggregate the vectors
corresponding to each one of its attribute values. The end result is a
weighted vector $(a_{i}(w_{1}),....,a(w_{m}))$, where $a_{i}(w_{j})$ is the
sum of weights, i.e., $a_{i}(w_{j})=\sum_{a_{k}\in A_{i}}w_{ij}$, where
$a_{k}$ stands for an individual attribute value in the set of values $A_{i}$
of entity $e_{i}$.

To compare two bag models, $BM(e_{i})$ and $BM(e_{j})$, one of the following
similarity measures is typically used:

_(i)_ ARCS Similarity (ARCS) sums the inverse Document Frequency of the common
n-grams in two bag models. That is, the rarer the common n-grams are, the
higher gets the overall similarity. Formally:
$ARCS(BM(e_{i}),BM(e_{j}))=\sum_{k\in BM(e_{i}){\cap}BM(e_{j})}{\log
2/\log(DF_{1}(k)\cdot DF_{2}(k))}$.

_(ii)_ Cosine Similarity (CS) measures the cosine of the angle of the weighted
vectors. Formally, it is equal to their dot product similarity, normalized by
the product of their magnitudes:
$CS(BM(e_{i}),BM(e_{j}))=\sum_{k=1}^{m}{w_{ik}w_{jk}}/||BM(e_{i})||/||BM(e_{j})||$.

_(iii)_ Jaccard Similarity (JS) treats the document vectors as sets, with
weights higher than (equal to) 0 indicating the presence (absence) of the
corresponding n-gram. On this basis, it defines as similarity the ratio
between the sizes of set intersection and union:
$JS(BM(e_{i}),BM(e_{j})){=}|BM(e_{i}){\cap}BM(e_{j})|/|BM(e_{i}){\cup}BM(e_{j})|$.

_(iv)_ Generalized Jaccard Similarity (GJS) extends JS so that it takes into
account the weights associated with every n-gram:
$GJS(BM(e_{i}),BM(e_{j})){=}\sum_{k=1}^{m}min(w_{ik},w_{jk})/\sum_{k=1}^{m}max(w_{ik},w_{jk})$.

Both CS and GJS apply seamlessly to both TF and TF-IDF weights.

####  B.2.2. Graph Models (Giannakopoulos et al., 2008; Rousseau and
Vazirgiannis, 2013).

Recent works suggest that graph models outperform the bag ones in various
tasks (Malliaros et al., 2018), from Information Retrieval (Rousseau and
Vazirgiannis, 2013) to Document Classification (Papadakis et al., 2016). There
are two graph models, one for each type of n-grams, i.e., token n-gram graphs
(Rousseau and Vazirgiannis, 2013) and character n-gram graphs (Giannakopoulos
et al., 2008). Both models represent each entity $e_{i}$ as an undirected
graph $G_{i}$ that contains one vertex for each n-gram in the attribute values
of $e_{i}$. An edge connects every pair of vertices/n-grams that co-occur
within a window of size $n$ in the values of $e_{i}$. Every edge is weighted
according to the co-occurrence frequency of the corresponding n-grams. Thus,
the graphs incorporate contextual information in the form of n-grams’
closeness.

To construct the model for an entity, we merge the graphs of its attribute
values using the update operator, which is described in (Giannakopoulos et
al., 2008; Giannakopoulos and Palpanas, 2010). To compare graph models, we can
use the following graph similarity measures (Giannakopoulos et al., 2008):

_(i)_ Containment Similarity (CoS) estimates the number of edges shared by two
graph models, $G_{i}$ and $G_{j}$, regardless of the corresponding weights
(i.e., it merely estimates the portion of common n-grams in the original
texts). Formally:
$CoS(G_{i},G_{j})=\sum_{e\in G_{i}}{\mu(e,G_{j})}/min(|G_{i}|,|G_{j}|)$, where
$|G|$ is the size of graph G, and $\mu(e,G)=1$ if $e\in G$, or 0 otherwise.

_(ii)_ Value Similarity (VS) extends CoS by considering the weights of common
edges. Formally, using $w_{e}^{k}$ for the weight of edge $e$ in $G_{k}$:
$VS(G_{i},G_{j})=\sum_{e\in(G_{i}\cap
G_{j})}{\frac{min(w_{e}^{i},w_{e}^{j})}{max(w_{e}^{i},w_{e}^{j})\cdot
max(|G_{i}|,|G_{j}|)}}$.

_(iii)_ Normalized Value Similarity (NS) extends VS by mitigating the impact
of imbalanced graphs, i.e., the cases where the comparison between a large
graph with a much smaller one yields similarities close to 0. Formally:
$NS(G_{i},G_{j}){=}\sum_{e\in(G_{i}\cap
G_{j})}{min(w_{e}^{i},w_{e}^{j})/max(w_{e}^{i},w_{e}^{j})}/min(|G_{i}|,|G_{j}|)$.

_(iv)_ Overall Similarity (OS) constitutes the average of the above graph
similarity measures, which are all defined $[0,1]$. Formally:
$OS(G_{i},G_{j}){=}(CoS(G_{i},G_{j})+VS(G_{i},G_{j})+NS(G_{i},G_{j}))/3$.

##  Appendix C Additional Experiments

###  C.1. Critical Difference Analysis

In addition to F-Measure, which is examined in Section 6 and Figure 2, we
performed a post-hoc Nemenyi test to identify the critical difference of the
eight algorithms with respect to Precision and Recall. The corresponding
Nemenyi diagrams appear in Figures 7 and 8, respectively. In both cases, the
critical distance is the same as that of F-Measure, namely 0.37. We observe
that for Precision, only the difference between RSR and BMC is insignificant,
while for Recall, the only insignificant difference pertains to BAH and RSR.
The best performing algorithm in terms of Precision is CNC, followed by EXC,
KRC and UMC, while the best recall is achieved by UMC, with KRC in the second
place. These results verify the patterns in Section 6 (Table 4 and Figure 3 in
particular), which highlight the excellent balance between Precision and
Recall that is achieved by UMC and KRC.

###  C.2. Threshold Analysis

Figure 7. Nemenyi diagram based on Precision. Figure 8. Nemenyi diagram based
on Recall.

As explained in Section 6, the similarity threshold constitutes the most
important configuration parameter for the effectiveness and time efficiency of
all bipartite graph matching algorithms. It is crucial, therefore, to
understand how easily this parameter can be fine-tuned a-priori, examining the
main factors that determine its optimal value. To this end, Table 8 presents
the descriptive statistics of similarity threshold per algorithm and type of
edge weights. These statistics include the average value along with the
corresponding standard deviation as well as the minimum and maximum values
together with the first, second and third quartile ($Q_{1}$, $Q_{2}$ and
$Q_{3}$, respectively). We also report the Pearson correlation of similarity
thresholds with the normalized size of similarity graphs, i.e., the number of
their edges divided by the Cartesian product.

Table 8. The distribution of similarity thresholds per algorithm and type of input. | mean$\pm$std | min. | $\mathbf{Q_{1}}$ | $\mathbf{Q_{2}}$ | $\mathbf{Q_{3}}$ | max. | $\mathbf{\rho(t,\frac{|E|}{||V_{1}\times V_{2}||})}$
---|---|---|---|---|---|---|---
CNC |  0.76$\pm$0.16 | 0.30 | 0.65 | 0.80 | 0.90 | 0.95 | -0.09
RSR |  0.76$\pm$0.16 | 0.20 | 0.65 | 0.80 | 0.90 | 0.95 | -0.14
RCA |  0.66$\pm$0.21 | 0.05 | 0.50 | 0.70 | 0.80 | 0.95 | -0.22
BAH |  0.66$\pm$0.25 | 0.05 | 0.50 | 0.70 | 0.85 | 0.95 | -0.31
BMC |  0.67$\pm$0.20 | 0.20 | 0.53 | 0.70 | 0.80 | 0.95 | -0.16
EXC |  0.63$\pm$0.23 | 0.05 | 0.45 | 0.65 | 0.80 | 0.95 | -0.19
KRC |  0.61$\pm$0.25 | 0.05 | 0.40 | 0.65 | 0.80 | 0.95 | -0.17
UMC |  0.63$\pm$0.23 | 0.05 | 0.45 | 0.65 | 0.80 | 0.95 | -0.16
(a) Schema-based syntactic inputs
CNC |  0.41$\pm$0.23 | 0.05 | 0.20 | 0.40 | 0.60 | 0.95 | 0.43
RSR |  0.41$\pm$0.24 | 0.05 | 0.20 | 0.40 | 0.60 | 0.95 | 0.39
RCA |  0.31$\pm$0.24 | 0.05 | 0.10 | 0.25 | 0.50 | 0.95 | 0.35
BAH |  0.30$\pm$0.24 | 0.05 | 0.05 | 0.25 | 0.45 | 0.95 | 0.35
BMC |  0.33$\pm$0.24 | 0.05 | 0.10 | 0.30 | 0.50 | 0.95 | 0.37
EXC |  0.29$\pm$0.23 | 0.05 | 0.10 | 0.25 | 0.45 | 0.90 | 0.38
KRC |  0.27$\pm$0.24 | 0.05 | 0.05 | 0.20 | 0.45 | 0.90 | 0.31
UMC |  0.30$\pm$0.25 | 0.05 | 0.05 | 0.20 | 0.50 | 0.95 | 0.33
(b) Schema-agnostic syntactic inputs
CNC |  0.69$\pm$0.36 | 0.00 | 0.48 | 0.95 | 0.95 | 0.95 | -0.13
RSR |  0.80$\pm$0.24 | 0.15 | 0.70 | 0.95 | 0.95 | 0.95 | -0.29
RCA |  0.77$\pm$0.27 | 0.10 | 0.55 | 0.95 | 0.95 | 0.95 | -0.32
BAH |  0.66$\pm$0.30 | 0.05 | 0.41 | 0.80 | 0.95 | 0.95 | -0.25
BMC |  0.78$\pm$0.27 | 0.10 | 0.56 | 0.95 | 0.95 | 0.95 | -0.26
EXC |  0.77$\pm$0.26 | 0.10 | 0.56 | 0.95 | 0.95 | 0.95 | -0.24
KRC |  0.75$\pm$0.29 | 0.05 | 0.51 | 0.95 | 0.95 | 0.95 | -0.25
UMC |  0.76$\pm$0.28 | 0.10 | 0.51 | 0.93 | 0.95 | 0.95 | -0.22
(c) Schema-based semantic inputs
CNC |  0.68$\pm$0.29 | 0.00 | 0.55 | 0.75 | 0.95 | 0.95 | -0.31
RSR |  0.74$\pm$0.24 | 0.10 | 0.55 | 0.85 | 0.95 | 0.95 | -0.27
RCA |  0.66$\pm$0.28 | 0.05 | 0.45 | 0.80 | 0.85 | 0.95 | -0.34
BAH |  0.60$\pm$0.33 | 0.05 | 0.30 | 0.75 | 0.85 | 0.95 | -0.37
BMC |  0.71$\pm$0.26 | 0.10 | 0.50 | 0.85 | 0.95 | 0.95 | -0.30
EXC |  0.67$\pm$0.27 | 0.05 | 0.45 | 0.80 | 0.90 | 0.95 | -0.28
KRC |  0.64$\pm$0.25 | 0.05 | 0.45 | 0.68 | 0.84 | 0.95 | -0.31
UMC |  0.67$\pm$0.27 | 0.05 | 0.46 | 0.80 | 0.85 | 0.95 | -0.33
(d) Schema-agnostic semantic inputs

We observe different patterns for each type of edge weights. More
specifically, the schema-agnostic syntactic inputs yield relatively high
thresholds: the average values of all algorithms fluctuate between 0.61 and
0.76, while the median ($Q_{2}$) is slightly higher, between 0.65 and 0.8.
Yet, the variance is also high, as indicated by the standard deviation, which
is consistently higher than 0.16. The reason is that the similarity thresholds
of all algorithms cover the entire space in $[0.05,0.95]$, as suggested by the
minimum and maximum values. For most algorithms, though, the first ($Q_{1}$)
and third ($Q_{3}$) quartiles significantly restrict the optimal values to the
range 0.4/0.5-0.8 or 0.65-0.90. The slightly negative correlation with the
normalized graph size suggests that in datasets where the portion of edges is
high, the optimal threshold should be slightly lower. The reason is that the
schema-based syntactic weights provide higher confidence in datasets with
relatively small graphs (e.g., $D_{1}$), while large graphs indicate non-zero
similarities with too many non-matching entities. These conditions occur in
datasets with lower confidence in the similarity values, such as the
bibliographic ones $D_{4}$ and $D_{9}$, which convey a limited vocabulary. In
the former cases, high thresholds suffice for achieving high performance, but
in the latter ones, slightly lower thresholds are required in order to
restricting the impact on recall.

Regarding the schema-agnostic syntactic weights, we observe that the standard
deviation is higher than the schema-based counterparts, even though the
average and median values are much lower, even by 50%. The reason is that the
similarity thresholds still cover the entire space in $[0.05,0.95]$, with the
interquartile range ($Q_{3}$ \- $Q_{1}$) increasing from 0.25 or 0.3 to 0.4
for practically all algorithms. This means that this type of weights yields a
larger diversity of graphs, which hinders the configuration of the similarity
thresholds. Note that the correlation with the normalized graph size is
significantly positive for all algorithms. The reason is that large graphs
emanate from similarity functions that associate many non-matching entities,
albeit with low weights. These settings call for higher thresholds in order to
prune the non-matching edges and increase precision. In other words, smaller
thresholds should be used in smaller graphs in order to maintain a high
recall.

Figure 9. Pearson correlation between the similarity thresholds of every
algorithm for schema-based syntactic, schema-agnostic syntactic inputs,
schema-based semantic and schema-agnostic semantic inputs, from left to right.

Among the semantic inputs, the schema-based ones share similar patterns with
their syntactic counterparts, as the average thresholds are high for all
algorithms. Compared to syntactic weights, though, the median and the third
quartile get higher, but the first one gets lower, thus increasing the
interquartile range and the standard deviation. This means that threshold
fine-tuning gets harder. Yet, the normalized graph size provide stronger
indications for the best thresholds, as suggested by the significantly higher
negative correlations. Similar patterns apply to the schema-agnostic semantic
inputs, albeit with slightly lower thresholds.

Note that the relative order of the algorithms with respect to the average
thresholds remains the same in both types of syntactic weights: CNC and RSR
exhibit the highest thresholds, with KRC lying at the other extreme. followed
in close distance by EXC and UMC. These patterns do not hold in the case of
semantic inputs, except for RSR, which consistently yields the highest average
threshold. In fact, CNC uses lower thresholds than KRC, EXC and UMC for
schema-based weights.

These patterns can be verified at a finer granularity through Table 9, which
provides the average threshold per dataset for each algorithm and type of edge
weights. Another pattern that emerges from this table is that every algorithm
exhibits highly similar thresholds for every row (i.e., dataset). This means
that knowing the optimal threshold for a particular algorithm over a specific
dataset provides strong indications for fine-tuning the rest of the algorithms
over the same dataset. The high correlation between the optimal thresholds of
the eight algorithms is verified by the diagrams in Figure 9, which present
the Pearson correlations for each pair across the four types of edge weights.
We observe that this correlation is highly positive, taking values well above
0.8 in the vast majority of cases, especially for the syntactic weights. The
only exceptions are BAH and CNC for semantic weights, which fluctuate from 0.2
to 0.8.

Overall, the similarity thresholds used by bipartite graph matching algorithms
depend on the type of edge weights and the normalized graph size. With the
exception of schema-agnostic syntactic weights, relatively high thresholds are
used on average. Their optimal value is more stable in the case of schema-
based syntactic weights, with the interquartile range limited to 0.3 over even
0.25 for most algorithms. Most importantly, the optimal threshold for a
particular similarity graph is relatively stable across different algorithms.
In other words, it depends more on the characteristics of the input, than the
functionality of the graph matching algorithm.

Table 9. The average similarity threshold and its standard deviation per algorithm, dataset and type of edge weights. | CNC | RSR | RCA | BAH | BMC | EXC | KRC | UMC
---|---|---|---|---|---|---|---|---
$\mathbf{D_{1}}$ |  .81$\pm$.15 |  .85$\pm$.12 |  .75$\pm$.14 |  .83$\pm$.13 |  .76$\pm$.14 |  .69$\pm$.21 |  .72$\pm$.17 |  .71$\pm$.17
$\mathbf{D_{2}}$ |  .63$\pm$.15 |  .60$\pm$.14 |  .42$\pm$.20 |  .16$\pm$.17 |  .48$\pm$.20 |  .34$\pm$.23 |  .39$\pm$.22 |  .38$\pm$.20