We propose a framework to utilize Knowledge Graph (KG) embedding models for conceptual clustering, i.e., the task of clustering a given set of entities in a KG based on the quality of the resulting descriptions for the clusters. Speci cally, prominent regions in the embedding space are detected using Multicut clustering algorithm, and then the queries describing/covering the entities within these regions are obtained by rule learning. Finally, we evaluate these queries using di erent metrics. In our preliminary experiments, we compare the suitability of well-known KG embedding models for conceptual clustering. The reported results provide insights for the capability of these embeddings to capture graph topology and their applicability for data mining tasks beyond link prediction.
In this preliminary study, our goal is to analyze the suitability of
embedding models for conceptual clustering. More speci cally, we aim at investigating
whether prominent regions in the embedding space constructed by existing
embeddings correspond to any conjunctive queries. Comparing embeddings w.r.t.
their capability of capturing such queries opens new perspectives for their
applicability for various data mining tasks such as conceptual clustering.
Framework Description. To start with, we introduce our proposed framework
for utilizing KG embeddings for conceptual clustering. Given a KG and a set of
target entities, we rst compute KG embedding (see, e.g., [
To detect prominent regions in the embedding space we propose to use the
multicut graph clustering approach [
X
f2T nfeg
yf
9
=
;
where ye and yf are labels of the edges e and f respectively obtained using the
labeling function y. Considering only chordless cycles is su cient [
By solving (2) using e cient local search methods [
The constructed regions, i.e., clusters, in the vector space are then mapped to
CQs by learning Horn rules. E.g., the rule r : belongsTo(X ; c) created (Y ; X );
type(Y ; productOwner ); belongsTo(Y ; boschGMBH ) states that the answers to
the CQ q(X) created (Y ; X );type(Y ;productOwner );belongsTo(Y ;boschGMBH )
belong to the cluster c. For learning such rules, we adapt [
Per cluster coverage (cov) for a rule r, cluster c, and KG G, written as
cov (r ; c; G), is de ned as the ratio of entities covered by r within the cluster
c over the cardinality of c [
Exclusive coverage (exc) estimates exclusiveness of the rule r to the corresponding cluster c compared to other clusters from a set of clusters S. Formally, exc(r ;c;S;G)=
P >:cov (r; c; G) c02Snc jSncj cov(r;c0;G) 80; if min fcov (r ;c;G) cov (r ;c0;G)g 0 <> c02Snc ; otherwise.
Weighted Relative Accuracy (wra) measures unusualness of patterns (see [
We implemented our framework in Python, using the KG embedding models
from Ampligraph [
As described above, the cosine similarity is used to compute the pairwise
distances between entities. We tried several cutting prior values for the
Multicut algorithm and report here the best results. The Multicut is compared to
commonly used clustering algorithms, namely, DBSCAN [
We performed experiments on widely-used relational datasets: Hepatitis,
Mutagensis, WebKB, and Terrorist Attacks (see [
We evaluated the predictive quality of the trained embeddings using standard Mean Reciprocal Rank (MRR) and Hit@k measures, and assessed the quality of the mined queries using the functions cov, exc, and wra introduced above. Results. Table 1 shows the predictive quality of the KG embedding models, where ComplEx consistently achieves better results than TransE on all datasets, except YAGO. Training embeddings for this KG is particularly challenging for both models, and ComplEx could not converge within the training epochs due to its complexity.
In Table 2, we report the estimated quality of the discovered queries. For each dataset, we present the average cov, exc, wra measures, and the number of Hepatitis 0.929 0.903 0.947 Mutagenesis 0.896 0.840 0.959 WebKB 0.210 0.158 0.223 Terrorist 0.320 0.140 0.429 YAGO-Art 0.105 0.085 0.111 0.974 0.946 0.919 0.970 0.988 0.983 0.953 0.919 0.988 0.998 0.293 0.415 0.329 0.441 0.584 0.623 0.930 0.876 0.984 0.998 0.133 0.000 0.000 0.000 0.000 discovered clusters (cls). Conceptual clustering over ComplEx results in better average exc and wra, which answers our rst research question (Q1). In addition, the higher predictive quality of ComplEx in Table 1, supports the hypothesis (Q2), suggesting correlation between the predictive quality and the quality of the discovered queries. This also holds for YAGO, where TransE performs better than ComplEx in both prediction and clustering.
Regarding (Q3), multicut achieved better results compared to DBSCAN in the majority of datasets. Moreover, DBSCAN failed in several cases regardless of the used parameters. Interestingly, even compared to other clustering algorithms that require the number of clusters, Multicut performed better on several datasets. This demonstrates the suitability of this algorithm for the KG domain.
Finally, Table 3 shows example rules mined from YAGO over TransE. E.g.,
r1 describes entities in c1 as \artifacts that have a director and an actor", while
r3 describes entities in c2 as: \artifacts created by an award winner".
Conclusion and Outlook. We have introduced a framework for utilizing KG
embeddings for the task of conceptual clustering, which exploits the Multicut
algorithm [
For future work, we plan to extend our framework to account for background
knowledge in the form of ontologies. Additionally, we will consider comparing
the suitability of other embedding models for the task of conceptual clustering,
especially those trained on complex patterns [