A Graph-based Blocking Approach for Entity Matching
Using Contrastively Learned Embeddings

Presenter: John Bosco Mugeni
Supervisor: Toshiyuki Amagasa
University of Tsukuba
Published in (ACM SIGAPP) Applied Computing Review, 2022
Computer Science(University of Tsukuba)

UoT

1 / 28

Contents

1Introduction2

Problem definition

3

Related works

4

Proposed approach5

Experimental work

6

Results(University of Tsukuba)

UoT

2 / 28

Introduction: entity matching
Entity Matching: is the task of discovering matching entries among
disperate data sources.
The goal is to then link these entries with a high-match quality
However, the process meets quadratic complexity problem w.r.t
dataset size

Figure: An example of matching tuples(University of Tsukuba)

UoT

3 / 28

Introduction: entity matching
Entity Matching: is the task of discovering matching entries among
disperate data sources.
The goal is to then link these entries with a high-match quality
However, the process meets quadratic complexity problem w.r.t
dataset size

Figure: An example of matching tuples(University of Tsukuba)

UoT

3 / 28

Introduction: entity matching
Entity Matching: is the task of discovering matching entries among
disperate data sources.
The goal is to then link these entries with a high-match quality
However, the process meets quadratic complexity problem w.r.t
dataset size

Figure: An example of matching tuples(University of Tsukuba)

UoT

3 / 28

Introduction: blocking“Blocking” is introduced for efficient execution of entity matching
The naive pairwise comparison (right figure) requires exorbitantcomputation due to a massive search space in contrast to apartitioned search space due to “blocking” (left figure)

Figure: Types of blocking frameworks(University of Tsukuba)

UoT

4 / 28

Introduction: blocking“Blocking” is introduced for efficient execution of entity matching
The naive pairwise comparison (right figure) requires exorbitantcomputation due to a massive search space in contrast to apartitioned search space due to “blocking” (left figure)

Figure: Types of blocking frameworks(University of Tsukuba)

UoT

4 / 28

Introduction: blocking techqniues“Blocking” techniques can be categorized into 3 types;

Figure: Types of blocking frameworks

Rule-based methods require handcrafted features, domain knowledge& are labour intensive
Learning-based methods have high accuracy but require labelled data(labels are not always available)
Cluster-based methods circumvent the need of labels & handcraftedfeatures(University of Tsukuba)

UoT

5 / 28

Introduction: blocking techqniues“Blocking” techniques can be categorized into 3 types;

Figure: Types of blocking frameworks

Rule-based methods require handcrafted features, domain knowledge& are labour intensive
Learning-based methods have high accuracy but require labelled data(labels are not always available)
Cluster-based methods circumvent the need of labels & handcraftedfeatures(University of Tsukuba)

UoT

5 / 28

Introduction: blocking techqniues“Blocking” techniques can be categorized into 3 types;

Figure: Types of blocking frameworks

Rule-based methods require handcrafted features, domain knowledge& are labour intensive
Learning-based methods have high accuracy but require labelled data(labels are not always available)
Cluster-based methods circumvent the need of labels & handcraftedfeatures(University of Tsukuba)

UoT

5 / 28

Introduction: blocking techqniues“Blocking” techniques can be categorized into 3 types;

Figure: Types of blocking frameworks

Rule-based methods require handcrafted features, domain knowledge& are labour intensive
Learning-based methods have high accuracy but require labelled data(labels are not always available)
Cluster-based methods circumvent the need of labels & handcraftedfeatures(University of Tsukuba)

UoT

5 / 28

Introduction: motivation for cluster blocking

Existing solutions capture database interactions via traditional wordembeddings.
That means they assign the same vector to a word irrespective ofcontext.
E.g., The bank is located near the river bank.
In contrast, context embeddings assign vectors dynamically thereby
incorporating rich semantics.

(University of Tsukuba)

UoT

6 / 28

Introduction: motivation for cluster blocking

Existing solutions capture database interactions via traditional wordembeddings.
That means they assign the same vector to a word irrespective ofcontext.
E.g., The bank is located near the river bank.
In contrast, context embeddings assign vectors dynamically thereby
incorporating rich semantics.

(University of Tsukuba)

UoT

6 / 28Introduction: motivation for cluster blocking

Existing solutions capture database interactions via traditional wordembeddings.
That means they assign the same vector to a word irrespective ofcontext.
E.g., The bank is located near the river bank.
In contrast, context embeddings assign vectors dynamically thereby
incorporating rich semantics.

(University of Tsukuba)

UoT

6 / 28

Introduction: motivation for cluster blocking

Existing solutions capture database interactions via traditional wordembeddings.
That means they assign the same vector to a word irrespective ofcontext.
E.g., The bank is located near the river bank.
In contrast, context embeddings assign vectors dynamically thereby
incorporating rich semantics.

(University of Tsukuba)

UoT

6 / 28

Introduction: leveraging contrastive learning for clusterblocking.
Existing contextual embeddings suffer from anisotropy.

Figure: leveraging contrastive learning.

(University of Tsukuba)

UoT

7 / 28

Problem definition

Traditional clustering techniques suffer long execution times when
dealing with large databases
As a consequence, improving the efficiency of cluster-based blocking
while maintaining accuracy is a major challenge
To this end, our work exploits pre-trained language models for featureextraction, a k-nearest neighbour graph and graph clustering
algorithms
We wish to execute “blocking” in an effiecient way while maintaining
accuracy(University of Tsukuba)

UoT

8 / 28

Problem definition

Traditional clustering techniques suffer long execution times when
dealing with large databases
As a consequence, improving the efficiency of cluster-based blocking
while maintaining accuracy is a major challenge
To this end, our work exploits pre-trained language models for feature
extraction, a k-nearest neighbour graph and graph clustering
algorithms
We wish to execute “blocking” in an effiecient way while maintaining
accuracy(University of Tsukuba)

UoT

8 / 28

Problem definition

Traditional clustering techniques suffer long execution times when
dealing with large databases
As a consequence, improving the efficiency of cluster-based blocking
while maintaining accuracy is a major challenge
To this end, our work exploits pre-trained language models for feature
extraction, a k-nearest neighbour graph and graph clustering
algorithms
We wish to execute “blocking” in an effiecient way while maintaining
accuracy(University of Tsukuba)

UoT

8 / 28

Problem definition

Traditional clustering techniques suffer long execution times when
dealing with large databases
As a consequence, improving the efficiency of cluster-based blocking
while maintaining accuracy is a major challenge
To this end, our work exploits pre-trained language models for feature
extraction, a k-nearest neighbour graph and graph clustering
algorithms
We wish to execute “blocking” in an effiecient way while maintaining
accuracy(University of Tsukuba)

UoT

8 / 28

Thesis objective and contributions

We propose a graph-based blocking technique predicated on thek-nearest neighbour (k-NN) graph algorithm for EM.
We leverage readily available context-aware sentence embeddings
from four pre-trained language models for our blocking scheme
We show that our k-NN graph blocking transcends the existing deeplearning-based cluster blocking solution in terms of time and accuracy.

(University of Tsukuba)

UoT

9 / 28

Thesis objective and contributions

We propose a graph-based blocking technique predicated on thek-nearest neighbour (k-NN) graph algorithm for EM.
We leverage readily available context-aware sentence embeddings
from four pre-trained language models for our blocking scheme
We show that our k-NN graph blocking transcends the existing deeplearning-based cluster blocking solution in terms of time and accuracy.

(University of Tsukuba)

UoT

9 / 28

Thesis objective and contributions

We propose a graph-based blocking technique predicated on thek-nearest neighbour (k-NN) graph algorithm for EM.
We leverage readily available context-aware sentence embeddings
from four pre-trained language models for our blocking scheme
We show that our k-NN graph blocking transcends the existing deeplearning-based cluster blocking solution in terms of time and accuracy.

(University of Tsukuba)

UoT

9 / 28

Related works

Earlier attempts adopted rule-based solutions, e.g., standard blocking,sorted neighbourhood blocking, Q-gram blocking, suffix blocking, &canopy blocking
Normally, a special function (BKV) is used to map tuples to theirblocks
However, limitations arise when dealing with long, dirty, noisy text or
missing values
Some methods, e.g., sorted neighbourhood blocking are sensitive toparameters (the sliding window)(University of Tsukuba)

UoT

10 / 28

Related works

Earlier attempts adopted rule-based solutions, e.g., standard blocking,sorted neighbourhood blocking, Q-gram blocking, suffix blocking, &canopy blocking
Normally, a special function (BKV) is used to map tuples to theirblocks
However, limitations arise when dealing with long, dirty, noisy text or
missing values
Some methods, e.g., sorted neighbourhood blocking are sensitive toparameters (the sliding window)(University of Tsukuba)

UoT

10 / 28

Related works

Earlier attempts adopted rule-based solutions, e.g., standard blocking,sorted neighbourhood blocking, Q-gram blocking, suffix blocking, &canopy blocking
Normally, a special function (BKV) is used to map tuples to theirblocks
However, limitations arise when dealing with long, dirty, noisy text or
missing values
Some methods, e.g., sorted neighbourhood blocking are sensitive toparameters (the sliding window)(University of Tsukuba)

UoT

10 / 28

Related works

Earlier attempts adopted rule-based solutions, e.g., standard blocking,sorted neighbourhood blocking, Q-gram blocking, suffix blocking, &canopy blocking
Normally, a special function (BKV) is used to map tuples to theirblocks
However, limitations arise when dealing with long, dirty, noisy text or
missing values
Some methods, e.g., sorted neighbourhood blocking are sensitive toparameters (the sliding window)(University of Tsukuba)

UoT

10 / 28

Related works

Later the paper of Azzalini1 develops a system for “blocking” basedon the RNN architecture.
However, clustering large data sets proves to be resource-intensive
Morever, vectors have to be down-sampled via the t-SNE algorithm, intheir work, which scales poorly on big data sets
The RNN architecture relies on simple word embeddings that neglect
context

1F Azzalini, et al. 2020. Blocking Techniques for Entity Linkage: A Semantics-BasedApproach.
(University of Tsukuba)

UoT

11 / 28

Related works

Later the paper of Azzalini1 develops a system for “blocking” basedon the RNN architecture.
However, clustering large data sets proves to be resource-intensive
Morever, vectors have to be down-sampled via the t-SNE algorithm, intheir work, which scales poorly on big data sets
The RNN architecture relies on simple word embeddings that neglectcontext1
F Azzalini, et al. 2020. Blocking Techniques for Entity Linkage: A Semantics-BasedApproach.
(University of Tsukuba)

UoT

11 / 28

Related works

Later the paper of Azzalini1 develops a system for “blocking” basedon the RNN architecture.
However, clustering large data sets proves to be resource-intensive
Morever, vectors have to be down-sampled via the t-SNE algorithm, intheir work, which scales poorly on big data sets
The RNN architecture relies on simple word embeddings that neglect
context

1F Azzalini, et al. 2020. Blocking Techniques for Entity Linkage: A Semantics-BasedApproach.
(University of Tsukuba)

UoT

11 / 28

Related works

Later the paper of Azzalini1 develops a system for “blocking” basedon the RNN architecture.
However, clustering large data sets proves to be resource-intensive
Morever, vectors have to be down-sampled via the t-SNE algorithm, intheir work, which scales poorly on big data sets
The RNN architecture relies on simple word embeddings that neglectcontext1
F Azzalini, et al. 2020. Blocking Techniques for Entity Linkage: A Semantics-BasedApproach.
(University of Tsukuba)

UoT

11 / 28

Proposed approach: system overview
An overview of the system is as follows;

Figure: Our blocking system(University of Tsukuba)

UoT

12 / 28

Proposed approach: pipeline step 1
First, attributes of data sets to be integrated are concatenated into a string

Figure: Textual representation from table A or B
(University of Tsukuba)

UoT

13 / 28

Proposed approach:pipeline step 2
Next, each tuple is then input to a pre-trained transformer language model
producing context embeddings

Figure: Feature extraction (generating embeddings)(University of Tsukuba)

UoT

14 / 28

Proposed approach:pipeline step 3
Projection of embeddings to lower dimension is possible via UMAP orCVAE

Figure: elaborating the vector processing in case of dimensionality reduction(University of Tsukuba)

UoT

15 / 28

Proposed approach: pipeline step 4
Next, we apply knn graph algorithm on embedding vectors to construct agraph followed by unsupervised community detection algorithms

Figure: KNN-graph based blocking(University of Tsukuba)

UoT

16 / 28

Experimental work: data sets

Each data set has the format of Table A-Table B
Each pair has more than 6 million record comparisons

Figure: Experimental datasets for entity matching(University of Tsukuba)

UoT

17 / 28

Experimental work: data sets

Each data set has the format of Table A-Table B
Each pair has more than 6 million record comparisons

Figure: Experimental datasets for entity matching(University of Tsukuba)

UoT

17 / 28

Experimental work: computing environment & keyparameters

For the transformer based models, we choose the attention spans tobe 200 tokens
Batch size is chosen to be 32 & mean-pooling for summarising input
tokensA single workstation equipped with Intel(R) Core(TM) i7-4820K
quad-core CPU encompassing 48 GB RAM running Ubuntu 18.04
We use pre-trained models based on Hugging-face 2 & all programs
are executed in python version 3.7.6

2T. Wolf et al. 2020. HuggingFace’s Transformers: State-of-the-art Natural
Language Processing. arXiv:cs.CL/1910.03771(University of Tsukuba)

UoT18 / 28

Experimental work: computing environment & keyparameters

For the transformer based models, we choose the attention spans tobe 200 tokens
Batch size is chosen to be 32 & mean-pooling for summarising input
tokensA single workstation equipped with Intel(R) Core(TM) i7-4820K
quad-core CPU encompassing 48 GB RAM running Ubuntu 18.04
We use pre-trained models based on Hugging-face 2 & all programs
are executed in python version 3.7.6

2T. Wolf et al. 2020. HuggingFace’s Transformers: State-of-the-art Natural
Language Processing. arXiv:cs.CL/1910.03771(University of Tsukuba)

UoT

18 / 28Experimental work: computing environment & keyparameters

For the transformer based models, we choose the attention spans tobe 200 tokens
Batch size is chosen to be 32 & mean-pooling for summarising inputtokens
A single workstation equipped with Intel(R) Core(TM) i7-4820K
quad-core CPU encompassing 48 GB RAM running Ubuntu 18.04
We use pre-trained models based on Hugging-face 2 & all programs
are executed in python version 3.7.6

2T. Wolf et al. 2020. HuggingFace’s Transformers: State-of-the-art Natural
Language Processing. arXiv:cs.CL/1910.03771(University of Tsukuba)

UoT

18 / 28

Experimental work: computing environment & key
parameters

For the transformer based models, we choose the attention spans tobe 200 tokens
Batch size is chosen to be 32 & mean-pooling for summarising input
tokensA single workstation equipped with Intel(R) Core(TM) i7-4820K
quad-core CPU encompassing 48 GB RAM running Ubuntu 18.04
We use pre-trained models based on Hugging-face 2 & all programs
are executed in python version 3.7.6

2T. Wolf et al. 2020. HuggingFace’s Transformers: State-of-the-art Natural
Language Processing. arXiv:cs.CL/1910.03771(University of Tsukuba)

UoT

18 / 28

Results: blocking time

Figure: Performance on iTunes-Amazon(62,830 tuples)(University of Tsukuba)

UoT

19 / 28

Results:blocking time

Figure: Performance on DBLP-Scholar(66,879 tuples)(University of Tsukuba)

UoT

20 / 28

Results:blocking time

Figure: Performance on GoogleScholar-DBLP(66,879 tuples)(University of Tsukuba)

UoT

21 / 28

Results:blocking time

Figure: Performance on Walmart-Amazon(22,628 tuples)(University of Tsukuba)

UoT

22 / 28

Comparison of embeddings as a function of parameter k(University of Tsukuba)

UoT

23 / 28

Comparison of embeddings as a function of parameter k(University of Tsukuba)

UoT

24 / 28

Comparison of embeddings as a function of parameter k(University of Tsukuba)

UoT

25 / 28

Comparison of embeddings as a function of parameter k(University of Tsukuba)

UoT

26 / 28

Conclusion

As future work, we plan to improve representation learning using task
domain data as well combining our approach with a supervised system
for Entity Matching.

(University of Tsukuba)

UoT

27 / 28

The End(University of Tsukuba)

UoT

28 / 28