Knowledge graphs have attracted lots of attention in academic and industrial environments. Despite their usefulness, popular knowledge graphs suffer from incompleteness of information especially in their type assertions. This has encouraged research in the automatic discovery of entity types. In this context, multiple works were developed to utilise logical inference on ontologies and statistical machine learning methods to learn type assertion in knowledge graphs. However, these approaches suffer from limited performance on noisy data, limited scalability and the dependence on labelled training samples. In this work, we propose a new unsupervised approach that learns to categorise entities into a hierarchy of named groups. We show that our approach is able to effectively learn entity groups using a scalable procedure in noisy and sparse datasets. We experiment our approach on a set of popular knowledge graph benchmarking datasets, and we publish a collection of the outcome group hierarchies4.
Type information of knowledge graph (KG) entities is an important feature that
categorizes entities of similar semantics. It is used in different tasks related to
knowledge graphs including meta path extraction [
The currently available approaches for classifying knowledge graph entities
can be classified into two categories. First, schema-based approaches, where
the developed approaches utilise the known schema of the knowledge graph to
learn entity types. This includes automatically inferring type information using
standard RDF reasoning [
Secondly, the statistical learning approaches, which treat type prediction task
as a multi-label classification problem, where models learn entity types using a
set of graph based features. They use known type assertions as training examples
and learn a model that can infer other unknown type assertions. They are known
to provide more robust-to-noise type predictions [
In this work, we propose a new unsupervised approach that groups knowledge graph entities according to their connected neighbour in the graph. This can be formulated such that for every set of entity nodes E connected to another object node eo with a relation r, the set of nodes E belongs to the group gr,eo . For example, in a general knowledge graph about people and cities all the people entities connected to the entity "Dublin" with the relation "live-in" are associated with the group "live-in-Dublin" as shown in Fig. 1. We then learn the hierarchy of these groups using intersection and containment ratios between them to build a hierarchy of entity types. This allows us to produce new named groups for entities, and provides rich hierarchy of the newly created groups.
The rest of this work is organised as follows: (A) We present a detailed description of the pipeline of our approach in Section 2. (B) We experiment our method on multiple popular knowledge graph benchmarking datasets and we show samples of produced hierarchies in Section 3. (C) We discuss related works in Section 4. (D) We present our conclusions and future works in Section 5. Europe p1 • Rugby
LiveIn
LiveIn p5 • Play • p2
p3• p6 • • p4
LiveIn
Ireland Dublin
LiveInEurope LiveInIreland LiveInDublin PlayRugby In this section, we present our approach for learning hierarchical groups of entities in knowledge graphs. We divide the pipeline of our method into three segments: (1) entity grouping, (2) computing group similarities and (3) building group hierarchy. In the following subsection, we discuss the motivation for our approach and we discuss also each of its pipeline segments in detail while we use the knowledge graph sample in Fig. 1 as a running example. Knowledge graphs can model different types of assertions depending on their predicate types such as attribute assertions like the age or names of an entity, or related entities like birthplaces, friend, etc. Usually, the cardinality of relational predicates are many-to-many like having a friend, associated nationality or working for an organisation. In this case, our brains intuitively group entities associated with same predicates and destinations to a group like "friend of Jack", "people with British nationality " or "companies working in IT". In our approach, we use the same technique, where we transform every knowledge assertion i.e. SPO triple to a group assertion ("S" belongs to group "PO"). We also use a configurable minimum size requirement for groups to avoid including one-to-one predicates as group assertions. Given any knowledge graph, our approach starts with generating groups of entities by transforming the graph facts into group assertions as previously discussed. For example, the knowledge graph in Fig. 1 contains multiple facts about six persons. In this graph, all the persons are living in Europe such that 8 p 2 { p1, ..., p6}(p, ”LiveIn”, ”Europe”). This is transformed to creating a group called "LiveIn_Europe" (g) such that g = {p1, p2, p3, p4, p5, p6}. Similarly, other groups are created like "LiveIn_Ireland "7! {p2, p3, p4}, "LiveIn_Dublin" 7! {p3} and "Play_Rugby "7! {p5, p6}. This procedure is performed to generate groups from all the triples in the knowledge graph.
Algorithm 1 describes the process of generating these groups, where processing facts is parallelised to speed up processing large volumes of data. First, the set of all knowledge graph triples is divided into a configurable j number of splits. Each of these splits is then processed to generate a dictionary of groups and their contained entities according to their own set of triples. All the resulting dictionaries are then joined to generate one dictionary of all groups in the graph and their corresponding entities. In order to restrict the extracted groups to a minimum specific number of entities, groups with size less than a configurable minimum size are removed from the group dictionary. Finally, the outcome of this procedure is a dictionary of the remaining groups and their member entities.
We compute similarity measures between entity groups to learn their similarities
and hierarchical structure. We compute two types of similarities to achieve that:
Jaccard and hub promoted index (HPI) similarities [
Sgj1a,cgc2ard = (g1) \ (g1) [ (g2) (g2) ,
SgH1P,gI2 = | (g1) \ (g2)| min(|g1|, |g2|) , for any two groups g1 and g2, where (g) denotes the set of member entities of the group g and |g| denotes its size. The HPI similarity in this context computes the overlap between two groups, where its maximum value 1 implies that one of the groups is a subset of the other. The Jaccard similarity on the other hand computes the overall similarity between two groups of entities. For example, the HPI similarity between "LiveInEurope" and "LiveInIreland " is equal to |{p2, p3, p4}|/min(3, 6) = 1, which implies that the small group "LiveInIreland " is a subset of the larger group "LiveInEurope".
We also compute the similarities in a parallel procedure similar to the generation of groups. We first generate all possible combinations of groups, then we divide these combinations into splits. We then compute similarities for each of the splits. the outcome similarities of all the parallel procedures are then joined to generate a similarity matrix between all the groups. 2.4
The range of the hub promoted index (HPI) similarity between two groups is bounded between 0 and 1, where 0 represents that the groups are independent and 1 implies that one group is a subset of the other. In noisy knowledge graph, the HPI index between totally dependant groups is always less than 1 due to missing members in one of the two groups. In our approach we use a configurable parameter ✓ that represents the group containment HPI threshold. We initialise this parameter with a value of 0.9 by default to tolerate 10% of information loss. 3
In this section, we describe the datasets and outcomes of the experimentation of our approach. 3.1
In our experiments we use six knowledge graph benchmarking datasets:
– WN18 & WN18RR: subsets of the WordNet dataset [
– YAGO10: a subset of of YAGO3 dataset [
The above mentioned datasets are divided into three splits: training, validation and testing. In our experiments, we first join the three splits and we execute our method on the full dataset. 3.2
We executed our approaches on the aforementioned datasets, and we have generated the entity group hierarchies for each one of them. We use a minimum group size of 10 and a threshold of 0.9 for the HPI similarity for all the experimented datasets.
The outcome results show that these datasets contain different root groups, where each root include super group of different group semantics such locations, people and organisations.
Fig. 2 shows an example of an outcome hierarchy of location-based entities in the NELL239 dataset. It shows that our approach is able to generate a hierarchy of different levels with valid and meaningful semantics.
Fig 3 also shows another hierarchy for entities of people with a female gender
extracted from the FB13k dataset [
We have also published further outcomes and hierarchy views on a publicly available website 5. 5 https://samehkamaleldin.github.io/kg-hierarchies-gallery/ 3.3
4
The experiments are implemented in Python3.5, and all the experiments were executed on a Linux machine with an Intel(R) Core(TM) i70.4790K CPU @ 4.00GHz and 32 GB RAM. We also use the D3 JavaScript library to visualise our hierarchy in a radial tree form.
Despite the widespread uses of knowledge graph in multiple domains, they suffer
from missing information, especially type-based assertions of their entities.
Multiple works were developed to tackle this problem including classical link prediction
models [
Further works have also focused on developing methods that exclusively predict
entity types in knowledge graphs. These models have utilised different techniques
including schema-based inference of type information [
In this work, we have discussed the problem on knowledge graph entity classification, and we have shown that current state-of-the-art solutions are limited. We have also proposed a new approach for hierarchical grouping for knowledge graph entities which utilises an intuitive grouping of entities connected with the same predicate object combinations. We have shown that our approach can provide named hierarchical categorisation for the knowledge graph entities in a scalable parallel procedure. Our approach also operates on noisy data data by using flexible similarity measures. We have experimented our approach on standard knowledge graph benchmarking datasets and we have published the outcome hierarchies.
In future works we intend to add the new generated groups as triples to the graph along with their equivalence and dependence relationships and evaluate their effects on tasks like link prediction on knowledge graphs. We also intend to examine the possible use of the outcome hierarchies in mining association rules in knowledge graphs.
This work has been supported by Insight Centre for Data Analytics at National University of Ireland Galway, Ireland (supported by the Science Foundation Ireland grant 12/RC/2289).