Neural Concept Formation in Knowledge Graphs
Year: 2021

Abstract:
In this work, we investigate how to learn novel concepts in Knowledge Graphs (KGs) in a principled way, and how to effectively exploit them to produce more accurate neural link prediction models. Specifically, we show how concept membership relationships learned via unsupervised clustering of entities can be reified and used to augment a KG. In a thorough set of experiments we confirm that neural link predictors trained on these augmented KGs, or in a joint Expectation-Maximization iterative scheme, can generalize better and produce more accurate predictions for infrequent relationships. For instance, our method yields relative improvements of up to 8.6% MRR on WN18RR for rare predicates, and up to 82% in small-data regimes, where the model has access to just a small subset of the training triples. Furthermore, our proposed models are able to learn meaningful concepts.

text: a principled way, and how to effectively exploit them to produce more accurate neural link prediction models. Specifically, we show how concept membership relationships learned via unsupervised clustering of entities can be reified and used to augment a KG. In a thorough set of experiments we confirm that neural link predictors trained on these augmented KGs, or in a joint Expectation-Maximization iterative scheme, can generalize better and produce more accurate predictions for infrequent relationships. For instance, our method yields relative improvements of up to 8.6% MRR on WN18RR for rare predicates, and up to 82% in small-data regimes, where the model has access to just a small subset of the training triples. Furthermore, our proposed models are able to learn meaningful concepts.

heading: 1. Introduction
text: One of the most remarkable aspects of human intelligence is arguably the capacity to abstract and summarize knowledge into concepts. It is believed to play a central role in allowing humans to learn quickly from few examples [Lake et al., 2015] and to robustly generalize to unseen data [Pothos and Chater, 2002, Lakoff and Johnson, 1980, Rosch et al., 1976]. It is no wonder that many machine learning and knowledge representation methods have tried to “reverse-engineer” how humans learn concepts [Tenenbaum, 2018, Hassabis et al., 2017] in order to automate reasoning as well as knowledge base construction [Kok and Domingos, 2007, Kemp et al., 2006, Xu et al., 2006]. Among the most prominent knowledge representation formalisms, there are Knowledge Graphs (KGs) – graph-structured knowledge bases where knowledge about the world is encoded in the form of relationships between entities. KGs encode facts about entities and the relationships between them (edges) as subject-predicate-object triples, each denoting a relationship of type predicate between the subject and object of the triple. A fundamental task in the construction of KGs is link prediction, which consists of identifying missing edges between entities in the KG.
Neural link predictors are a class of link prediction models achieving state-of-the-art results on several link prediction benchmarks while being able to scale to very large KGs. Neural link predictors learn embedding representations for each entity and relation in the KG via back-propagation [Nickel et al., 2016]. However, neural link predictors are known not to be accurate in the presence of sparse KGs, i.e., when entities appear only in few
triples [Pujara et al., 2017], also referred to as the cold-start problem, and may not be able to learn patterns involving groups of entities [Evans and Grefenstette, 2018].
In this work, we propose to learn concepts in neural link predictors as a principled way to elicit discrete latent information that can alleviate the generalization issues of existing models. Moreover, learning new concepts and turning them into entities can help to automate the construction of KGs. Specifically, we make the following contributions. First, we formalize concept learning as an unsupervised clustering step over entities in a KG. We do this first by reifying concept membership relationships into KG facts and by incorporating them in the KG, in a process called KG augmentation, akin to Gad-Elrab et al. [2020]. Then, we demonstrate that training out-of-the-box neural link predictors on these augmented KGs improves their accuracy. Secondly, we introduce a single, principled probabilistic framework for jointly learning concept memberships and neural link prediction models at once, by maximizing the likelihood of the KG triples via an Expectation-Maximization scheme. Lastly, we execute a rigorous empirical evaluation on several real-world KG benchmarks, showing that both of our approaches, named ConFormA and ConFormAE, are capable of learning semantically meaningful concepts. We observe that explicitly augmenting the KG with the newly-learned concepts can improve generalization over rare predicates by up to 8.6% in terms of Mean Reciprocal Rank (MRR) on WN18RR and 2.1% on FB15k-237. Furthermore, we perform a sparsification analysis where neural link predictors are trained on only a small subset of the training set, showing that ConFormA and ConFormAE can achieve up to 82% relative improvement on WN18RR and 21% on FB15k-237 when trained on only 5% of the data. This highlights the potential of our approach for addressing the cold-start problem in sparse KGs.

heading: 2. Background
text: Let a KG G be represented as a set of N triples, i.e., G = {〈s, r, o〉i}Ni=1 ⊆ E × R × E where E = {ei}Nei=1 is the set of subject (s) and object (o) entities, and R = {ri} Nr i=1 the set of relation types (r). Neural link predictors can be framed as learning a k-dimensional
Algorithm 1 ConFormA(G, Nc, n) 1: Input: KG G, no. of clusters Nc, no. of epochs n 2: Output: Parameters Θ, cluster memberships S = {Sc | c ∈ C} 3: P← propositionalization(G) . E.g., random paths 4: S ← Clustering(P, Nc) . E.g., spectral clustering 5: G′ ← G ∪ {〈ei, ISA, cj〉 | ei ∈ Sc, c ∈ C} . Create an augmented KG 6: Θ← init() 7: for n epochs do . Train the parameters Θ of a neural link predictor on G′ 8: Θ← train(G′,Θ)
return Θ,S
representation, i.e., an embedding vector e ∈ Ck, for all entities in E appearing in G. Given a triple 〈s, r, o〉 ∈ E ×R×E , a neural link predictor defines a scoring function φr : Ck×Ck 7→ R that, given the embedding representations es ∈ Ck and eo ∈ Ck of the subject s and the object o of the triple, returns the score φr(es, eo) ∈ R that s and o are related by the relation type r. The scoring function φr implicitly defines a probability distribution p over triples. Let xsro be a binary random variable denoting the existence of the triple 〈s, r, o〉, then we have that the probability of observing the triple is proportional to its score, i.e., p(xsro) ∝ φr(es, eo) [Nickel et al., 2016]. Examples of neural link predictors are TransE [Bordes et al., 2013], DistMult [Yang et al., 2015b], and ComplEx [Trouillon et al., 2016]. In this work, we adopt the latter two as baselines, as they achieve state-of-the-art performance on a number of benchmarks when trained with care [Ruffinelli et al., 2020].
Let E ∈ CNe×k and W ∈ CNr×k be the relation and entity embeddings. Then, learning a neural link predictor from data consists of finding the best set of parameters Θ = {E,W} that solve the optimization problem arg minΘ L(G; Θ) + λΩ(Θ), where L(G; Θ) denotes a modelspecific loss, typically proportional to the negative log-likelihood of the triples [Trouillon et al., 2016], and Ω( · ) is a regularization term, such as the L2 or the nuclear weighted 3-norm [N3, Lacroix et al., 2018], whose weight is determined by a coefficient λ ≥ 0. In the following section, we discuss how this learning loop for neural link predictors can be extended to learn concepts in a KG, while treating the link predictor model as a black-box.
3. ConFormA: Learning Concepts by Augmenting Knowledge Graphs
Given a KG G, we define concept learning as identifying sets of entities S1, . . . , SNc ⊆ E that are semantically related and can be abstracted into concepts c1, . . . , cNc ∈ C. We aim at finding a partitioning of entities S = {Si}Nci=1, such that each entity is assigned to a single concept at a time, i.e., ∀Si, Sj ∈ S → Si ∩ Sj = ∅, and ⋃ S∈S S = E . To this end, a natural solution is to perform a hard clustering of the entities in the KG G. Then, we can reify the cluster membership relations, i.e., introducing the concepts c1, . . . , cNc as new entities, and materializing the concept membership relations as new triples. We refer to this process as KG augmentation. Algorithm 1 summarizes our framework, which can be instantiated for different clustering and neural link prediction models. We name it Concept Formation via Augmentation (ConFormA). Next, we discuss how to perform these two steps, and the reasons why neural link predictors can benefit from being trained on augmented KGs.
Clustering entities. Ideally, the clustering step in ConFormA could be performed by any relational clustering algorithm. However, classical probabilistic approaches such as statistical predicate invention [Kok and Domingos, 2007] and stochastic block models [Kemp et al., 2006, Xu et al., 2006] would hardly scale to modern KGs with hundreds of thousands of entities. This poses a challenge also to kernel-based approaches [Blondel et al., 2008, de Vries, 2013, Morris et al., 2017]. To overcome this issue, we opt for a more computationally efficient alternative: we first propositionalize entities into d-dimensional embedding vectors [Kramer et al., 2001] and then employ a propositional clustering algorithm – e.g., spectral clustering [Ng et al., 2001] or K-means – over this now tabular representation P ∈ RNe×d.
We find that executing multi-hop random paths in G, as proposed by Das et al. [2020], provides scalable and accurate entity representations. We also explored clustering directly over the embeddings learned by a neural link prediction model but with scarce or no link prediction improvements (see Appendix E, Table 15). This could be due to the latent concept information which we explicitly introduce via augmentation being already captured by the neural link predictor embeddings, while graph-based features add complementary information, as observed in Nickel et al. [2016].
Knowledge Graph Augmentation. Given the set S, we reify the cluster membership relations by materializing new triples to augment G. Specifically, for each entity e participating in a cluster c ∈ C we create a new triple of the form 〈e, ISA, c〉, where c is a new entity denoting the j-th concept, and ISA is a freshly introduced relation denoting concept memberships.1
Let G′ denote the augmented KG, i.e., G′ ← G ∪ {〈e, ISA, c〉 | e ∈ Sc, c ∈ C}, where Sc is the set of entities assigned to concept c. Learning a neural link predictor simply requires calling its usual training routine (lines 6-8 of Algorithm 1) over the augmented KG G′. Specifically, its set of parameters Θ′ = {E,W,C}, which now includes the concept embeddings C ∈ CNc×k for the newly introduced concept entities C = {c1, . . . , cNc}, can be updated by minimizing the neural link predictor’s loss function, along its other parameters.
ConFormA is likely to improve the generalization of a neural link predictor for the following reasons. Firstly, this kind of augmentation acts as injecting background knowledge that does not need to be learned from scratch, akin to when inverse relation triples [Lacroix et al., 2018, Kazemi and Poole, 2018] or hierarchical relation information [Zhang et al., 2018] are explicitly added to KGs. Secondly, they help to make very sparse KGs more dense, tackling the sparsity issues in neural link predictors [Pujara et al., 2017].
4. ConFormAE: Jointly learning Concepts and Embeddings
ConFormA is a flexible framework: it can be customized with any propositionalization and clustering routines, and wrapped around any neural link prediction model. A natural question then arises: is it possible to automatically devise a propositionalization scheme that enhances clustering and embedding quality, that is, to jointly learn both the concepts and the embeddings? Ideally, we could cast this as a joint optimization problem to maximize the marginal log-likelihood of the triples in G, where marginalization is performed over some latent variable Z denoting the cluster assignments, i.e., having values c ∈ C. As directly maximizing this marginal likelihood is intractable, we adopt an iterative Expectation-Maximization
1. A similar augmentation strategy has been independently proposed in Gad-Elrab et al. [2020] to learn rule-based explanations for a subset of the KG entities. See Section 5 for a discussion.
Algorithm 2 ConFormAE(Θ,S, Nc, n, t) 1: Input: no. of clusters Nc, initial parameters Θ, no. of epochs n, and no. of iterations t. 2: Output: Updated parameters Θ, cluster memberships S = {Sc | c ∈ C} 3: for t iterations do 4: for c ∈ C do . Initialise the cluster memberships 5: Sc ← ∅ 6: for e ∈ E do 7: ĉ← arg maxc∈C φISA(ee, ec) 8: Sĉ ← Sĉ ∪ {e} 9: G′ ← G ∪ {〈e, ISA, c〉 | e ∈ Sc, c ∈ C} . E-step: Make hard assignments 10: for n epochs do . M-step: Refine the neural link prediction model 11: Θ← train(G′,Θ)
return Θ,S
(EM)-like scheme [Dempster et al., 1977]. Algorithm 2 summarizes the whole process, which we name ConFormAE – Concept Formation with Augmentation via EM. We next discuss in detail how to design the expectation (E) and maximization (M) steps efficiently.
E-step. Let p(Z | e) denote the distribution over concept-memberships induced by the neural link predictor for the entity e. Recall from Section 2 that the probability of assigning entity e to concept c is proportional to the score assigned to the reified triple (Section 3) encoding its concept membership, i.e., p(Z = c | e) ∝ φISA(ee, ec), where ee, ec denote the embeddings of e and c, respectively. Exactly computing all the cluster memberships p(Z = c | e) for each entity e and concept c ∈ C is a hard problem, since we would need to compute an intractable partition function. We therefore resort to compute hard cluster assignments, a practical approximation commonly adopted in many hard-EM variants [Samdani et al., 2012, Kok and Domingos, 2007]. That is, we are interested in solving ĉ = arg maxc∈C p(Z = c | ei) for each entity ei. Note that this can be done exactly and efficiently as ĉ = arg maxc∈C φISA(ee, ec) and therefore it reduces to predicting the most probable link between the entity e and a concept in C.
M-step. The aim of this step is to find the best set of parameters Θ′ for a neural link predictor by maximizing its log-likelihood, i.e., Ece∼p(·|e) [ log p(X) + ∑ e∈E log p(Z = ce | e) ] where log p(X) here compactly denotes the likelihood of the data in G, and ce ∈ C denotes the concept associated with the entity e ∈ E . This quantity can be efficiently approximated via our reification and augmentation scheme. In fact, at the end of the E-step, we had retrieved the clustering S (as in ConFormA, cf. Section 3). Therefore, to find Θ′ we can simply train the neural link prediction model for a certain number of epochs n over the augmented KG G′.
We refer to Appendix A for an in-depth analysis of the time and space complexity of ConFormA and ConFormAE.

heading: 5. Related Work
text: Concepts are a fundamental building block of modern Knowledge Graphs. For example, the Resource Description Framework [RDF, Klyne and Carroll, 2004] data model allows to state
that a resource is an instance of a concept (or class) via the rdf:type predicate, while its extension RDF Schema [Brickley and Guha, 2014] allows for specifying subclasses between concepts, and using concepts for specifying domain and range of predicates.
Concept Learning for Relational Data. Relational clustering, sometimes known as statistical predicate invention [Kok and Domingos, 2007], has been addressed in different communities and under different relational formalisms. For instance, the Infinite Relational Model [IRM, Kemp et al., 2006], is a Bayesian non-parametric interaction method for detecting community of users in networks, later extended to multiple relation types [Xu et al., 2006]. The Multiple Relational Clusterings [MRC, Richardson and Domingos, 2006] model extends the IRM to learning multiple cross-cutting clusterings, i.e. allowing each object to belong to more than one cluster, under the general framework of Markov logic networks (MLNs). The above approaches (and their variants) would hardly scale to the KGs we employ in our experiments. To see why, consider that to train either the IRM or the MRC on a small knowledge graph such as UMLS [McCray, 2003] (135 entities, see Section 6) took 10 hours, while both our algorithms require less than 3 minutes.
Concept learning for KGE models. In a preliminary study, Nickel and Tresp [2011] explore how to reconstruct a taxonomy over entities by performing hierarchical clustering of entity embeddings. Differently from our work, they do not learn embedding representations for the learned concepts nor use concept learning to improve link prediction on the original KG. Zhang et al. [2018], on the other hand, proposed learning and explicitly modeling taxonomies over relations. To do so, they cluster relation embeddings in a three-layer hierarchy. Our augmentation approach, while focusing on entity concepts, can be generalized to relations as well, after reifying them. Closer to our work, Gad-Elrab et al. [2020] propose an iterative clustering scheme which involves i) clustering latent embeddings, ii) reifying learned cluster memberships and then, iii) updating latent embeddings. Differently from our work, however, they do not aim at improving neural link prediction accuracy, but eliciting rules to explain subsets of entities. Without this difference in mind, their scheme can be thought of as a particular instance of ConFormA where K-Means is used for directly clustering the latent embeddings. We confirmed empirically that this instance of ConFormA does not yield statistically significant improvements over baselines (see Appendix E, Table 15). More interestingly, Gad-Elrab et al. [2020] propose different ways to reify concept memberships – adopting them in ConFormA is a promising research direction.
Concept Learning for Deep Graph Classification. Ying et al. [2018] introduce a differentiable graph pooling module in graph neural networks (GNNs) to for perform hierarchical clustering of nodes in graphs. While improving the accuracy over small-scale graph classification benchmarks, their work cannot be readily adapted to link prediction on KGs and would not scale to large benchmark KGs, such as those used in our experiments.
Data Augmentation for Link Prediction. Various KG augmentation schemes have been proposed in the neural link prediction literature. E.g., Lacroix et al. [2018] show that introducing reciprocal relations as explicit triples greatly enhances the performance of KGE models on many benchmarks. Minervini et al. [2017], instead, temporarily augment a KG during training by generating sets of adversarial examples that maximize an inconsistency loss encoding certain background knowledge.

heading: 6. Experiments
text: In this Section, we aim to answer the following research questions: Q1) are the concepts learned by ConFormA and ConFormAE semantically-meaningful?, Q2) can unsupervised concept learning boost neural link prediction performance?, Q3) can concept reification help alleviate the cold-start problem in sparse in KGs?, and Q4) how does augmentation impact generalization over rare relation types?. We proceed by outlining our experimental setting.
Datasets. We perform experiments on three datasets: WN18RR [Dettmers et al., 2018] and FB15k-237 [Toutanova and Chen, 2015] – two large benchmark KGs and UMLS [McCray, 2003] – a small biomedical KG. Summary statistics of the entity and relation distributions for each dataset are shown in Table 1. The two large KGs come with unique challenges – in FB15k-237, the number of predicates is relatively high (Table 1), and it may be difficult to jointly model all of them. In WN18RR, on the other hand, most entities are sparsely represented in the training set. As in [Pujara et al., 2017], we consider the sparsity of each graph by computing the entity density (ED) and relation density (RD), i.e., the average number of triples per entity or relation: RD = |T |/|R|, ED = 2|T |/|E| where |T | is the number of train triples. We note that the entity density in WN18RR is extremely low, with each entity occurring on average in only four triples (Table 1).
Baselines. To investigate the ability of ConFormA and ConFormAE to work with different out-of-the-box neural link predictors, we employ two different baselines: ComplEx [Trouillon et al., 2016] and DistMult [Yang et al., 2015a]. For all experiments we used the nuclear N3 norm [Lacroix et al., 2018] as a regularizer, the standard multi-class loss proposed by Lacroix et al. [2018], and the AdaGrad optimizer [Duchi et al., 2011]. Hyperparameter values can be found in Appendix G. We trained each model till convergence for 100 epochs and computed the filtered Mean Reciprocal Rank (MRR) and HITS@K [Bordes et al., 2013] every 3 epochs on the validation and test sets. The highest validation performance was extracted and the corresponding test performance was reported.
ConFormA.We use the propositionalization scheme leveraging random paths proposed by Das et al. [2020]. To construct the vector embeddings, we represent each entity e ∈ E using p where each entry pi is given by the number of times we have traveled along relation ri across the n paths. We distinguish as to whether we have traveled along a relation in the forward or inverse direction, hence the resulting embeddings are p ∈ R2Nr . We clustered the resulting representations using the Spectral Clustering algorithm [Ng et al., 2001] using the default parameters, and the number of clusters in {50, 100, 500, 1000} for WN18RR and
FB15k-237, and {30, 50, 100} for UMLS. The hyperparameters for training the neural link predictors were selected with the baseline model on a held-out validation set.
ConFormAE. To train ConFormAE we experimented with initializing cluster memberships in two ways: randomly and using memberships learned via clustering of simple propositionalized embeddings, such as those used for ConFormA. We found that in most cases a random initialization performed competitively and reduced compute time hence this is the strategy we have opted to use throughout this work. To obtain the ConFormAE results quoted in Table 3 the initial number of clusters was in {50, 100, 500, 1000}. Our experiments showed that setting n = 1 i.e., training the neural predictor for one epoch after every E-step was sufficient for fast convergence (see Appendix G). Again, we use the same hyperparameters used for the baselines. 2
Experimental Results. In order to answer Q1 we first perform a qualitative analysis: we inspect the entities which form the concepts learned by ConFormA and ConFormAE on UMLS, FB15k-237 and WN18RR. Excerpts of prototypical clusters learned by ConFormA and ConFormAE are shown in Table 2, while full clustering of UMLS and further examples can be found in Appendix C. Across all datasets entities appear to be meaningfully clustered into e.g., diseases, music schools and geographical locations. Next, we strengthen our analysis with a quantitative evaluation: we compare against ground truth concept information related to the semantic types in UMLS [Bodenreider and McCray, 2003] and the notable_types in FB15k-237. We report our findings in Appendix D by evaluating cluster matches using normalized mutual information scores, generalized to deal with overlapping clusters for FB15k-237. In summary, for UMLS, we find that ConFormA with random paths and ConFormAE outperform clustering neural link predictor embeddings and recover the group information rather faithfully, with ConFormAE achieving the best scores overall (Table 10). For FB15k-237, we find that across all 3 approaches the NMI is relatively low, indicating that all the methods struggle to recover the concepts as specified by types. Nevertheless, even in this scenario ConFormAE delivers the best scores (Tables 11 and 12).
Hence, we can answer Q1 affirmatively and note one advantage of ConFormAE over ConFormA– ConFormAE can yield meaningful concepts from random cluster initialization, without requiring any a priori knowledge on the structure of the KG.
To answer Q2 Table 3 reports the MRR and Hits@K for ConFormA and ConFormAE, for different values of embedding size k, after a grid search on regularizers, batch-size and
2. Code is available at: https://github.com/AgaDob/conformae
learning rates for the baselines. We report additional results in Appendix E where we quantitatively inspect which triples benefit most from concept learning and report results with TuckER [Balazevic et al., 2019] – an additional neural link predictor. In general, we see a consistent boost over both DistMult and ComplEx baselines. The boost is especially striking on WN18RR. For example, a smaller (k = 500) model learned by ConFormA or ConFormAE is equally good or better than a much larger one (k = 2000) learned by ComplEx in terms of in terms of H@10. If we perform additional augmentations, such as adding reciprocal relationships [Lacroix et al., 2018] we find that the improvements from the two methods are additive, as reported in Appendix B. For FB15k-237 we also see an improvement in Table 3, though of a smaller magnitude. This can be explained by the fact that WN18RR is a much sparser KG and as such it can benefit more from our concept learning scheme. Therefore, we hypothesize that the concept reification and explicit augmentation might be especially beneficial for performing link prediction in a small data regime and thus alleviate the cold-start problem [Bobadilla et al., 2012]. To verify this (Q3), we performed a series of sparsification experiments, decreasing the percentage of training triples available to the propositionalisation algorithm and to the link predictor. Fig. 2 and Table 4 show the relative improvement upon the baseline in terms of MRR for the percentage of retained triples in {5, 7, 10, 20, . . . , 90}. Across all configurations we see a clear boost, more evident for few training triples. For WN18RR, ConFormA and ConFormAE improve over 80%
w.r.t. their baselines when only 5% of training data is available. For FB15k-237, we also see a consistent boost, though there is some stochasticity for less than 20% training triples - this is likely due to its large number of predicates which increase the minimum number of training triples required to learn a good model.
To answer Q4, we inspect how generalization affects different triples after binning them w.r.t. the frequency (rare, medium, common) of their relations. The bins used to categorize relations into their frequency-based sub-populations (Table 26) were constructed by considering the total number of training examples. Fig. 3 reports the relative improvement of ConFormA and ConFormAE over the baselines on predicate sub-populations in terms of MRR w.r.t. the baseline for the aforementioned bins. Across all datasets, the largest improvement is observed on the rare predicates sub-population, with relative improvements of up to 8% on WN18RR, 15% on UMLS and 2% on FB15k-237 confirming that discovering concepts and augmenting KGs with them helps neural link predictors on triples whose predicates are underrepresented.
We note that while generally ConFormA and ConFormAE perform similarly, occasionally randomly-initialized ConFormAE performs worse, as can be seen for FB15k-237 in Fig. 3. As is the case for other Hard-EM algorithms, the quality of the clustering learned
by ConFormAE depends to a certain extent on the cluster initialization. We find that the cluster memberships learned by ConFormA through clustering of propositionalized representations can provide a good initialization for ConFormAE and accelerate convergence. Strictly speaking, ConFormA can be seen as a special case of ConFormAE with a non-random initialization, where only a series of M-steps is performed.
Lastly, we consider the run-times. Averaging across all embedding sizes, datasets, and six random trials we find that ConFormA and ConFormAE only add a minimal overhead over the respective baselines: they are only 1.09 and 1.14 times slower. For example, training DistMult on WN18RR using k = 2000 for 100 epochs took 176min for the baseline, 211min for ConFormA and 227min for ConFormAE with random initialization.

heading: 7. Conclusions
text: In this work we have introduced the task of unsupervised concept formation in KGs and proposed two algorithms to achieve it – ConFormA and ConFormAE – based on entity clustering and KG augmentation. Our experiments show that our approaches can learn semantically-meaningful concepts and improve the accuracy on downstream link prediction tasks. We find that leveraging latent concept information helps neural link predictors to generalize to rare predicates and is especially beneficial in sparse KGs, where entities participate in few training triples. Moreover, learning new concepts as entities can help to automate the construction of KGs and the learned concept representations can be used for a variety of downstream tasks. While the assumption that every entity participates in exactly one concept can be unrealistic, it points to exciting future work on learning concept hierarchies. Lastly, our work also paves the way for principled probabilistic approaches to elicit discrete latent variables in neural link prediction models.

heading: Acknowledgments
text: This research was supported by the European Union’s Horizon 2020 research and innovation programme under grant agreement no. 875160.

heading: Appendix A. Computational Complexity
text: The time and space complexity of ConFormA depends on the propositionalization, clustering, and neural link prediction model being used. In our experiments, the random path propositionalization has time complexity O(kL), where L is the max length of a path and k is the number of paths, while its space complexity is Θ(kNr).
Clustering. For a vanilla spectral clustering implementation the complexity would be dominated by the O(N3e ) cost of computing the Singular Value Decomposition of the propositionalization embedding matrix P. Alternatively, the K-means algorithm would require O(tkNeNc) time, where t is the number of iterations and k is the embedding size.
Neural Link Prediction. For the cost of training and evaluating neural link prediction models, we refer the reader to their respective papers [Bordes et al., 2013, Trouillon et al., 2016, Yang et al., 2015a, Dettmers et al., 2018, Lacroix et al., 2018]. We refer to [Ruffinelli et al., 2020] for a comparison of different choices of the loss function on several downstream link prediction tasks. We point out that, in our case, the number of entities in G becomes Ne +Nc, as the new set of entities in the augmented KG G′ would include Nc concept entities.
Expectation-Maximization. In ConFormAE, the complexity of the M-step is that of training the neural link predictor. In the E-step we need to evaluate the score and loop through all of the entities and all the concepts, which results in O (NeNc) steps. Note that, in practice, this step can be efficiently parallelized on GPU. In Section 6 we report average run-times, showing that the computational cost is only marginally higher than that of an out-of-the-box link predictor: in our experiments, ConFormA and ConFormAE are respectively only 1.09 and 1.14 times slower than the neural link predictor alone.
Appendix B. Reciprocal Relations with ConFormA/E
Reciprocal relations [Lacroix et al., 2018] is a popular method of augmenting KGs by introducing an inverse of every relation into the graph. In Table 5 we compare link prediction performance between training neural link predictors on standard KGs, KGs augmented with inverse relations, training with concept augmentations (ConFormA and ConFormAE) and lastly, the effect of combining inverse relations with ConFormA and ConFormAE. Across all datasets and models we find that best performance is achieved either by combining inverse relations with ConFormA and ConFormAE, or by our method alone.

heading: Appendix C. Qualitative Concepts Analysis
text: In this section we provide further examples of concepts learned by ConFormA and ConFormAE. Tables 6 and 7 show fragments of prototypical concepts learned by ConFormA for WN18RR and by ConFormAE for FB15K-237, respectively, while Table 8 and Table 9 show the full clustering of ConFormAE and ConFormA for UMLS, respectively.
Table 9: Concepts learned by ConFormA for UMLS using ComplEx with k=200 by clustering random paths representations using Spectral Clustering, with the number of clusters set to 20.
Concept 1 clinical_drug, food, indicator_reagent_or_diagnostic_aid, chemical, organophosphorus_compound, chemical_viewed_functionally, biomedical_or_dental_material, lipid, chemical_viewed_structurally, amino_acid_peptide_or_protein, organic_chemical, carbohydrate, nucleic_acid_nucleoside_or_nucleotide, element_ion_or_isotope, steroid, eicosanoid, inorganic_chemical
Concept 2 conceptual_entity, spatial_concept, activity, idea_or_concept.
Concept 3 cell_component, body_location_or_region, body_substance, anatomical_structure, body_space_or_junction, gene_or_genome, fully_formed_anatomical_structure, tissue, cell, embryonic_structure, body_part_organ_or_organ_component.
Concept 4 regulation_or_law, classification, intellectual_product.
Concept 5 molecular_sequence, language, body_system, carbohydrate_sequence, nucleotide_sequence, amino_acid_sequence, functional_concept.
Concept 6 plant, alga, bacterium, fungus, rickettsia_or_chlamydia, virus.
Concept 7 quantitative_concept, laboratory_or_test_result.
Concept 8 qualitative_concept, finding, sign_or_symptom.
Concept 9 research_device, drug_delivery_device, manufactured_object, medical_device.
Concept 10 molecular_biology_research_technique, diagnostic_procedure, research_activity, laboratory_procedure.
Concept 11 invertebrate, archaeon, organism, bird, fish, amphibian, animal, reptile, human, mammal, vertebrate.
Concept 12 occupation_or_discipline, biomedical_occupation_or_discipline.
Concept 13 organism_attribute, natural_phenomenon_or_process, temporal_concept, mental_process, genetic_function, molecular_function, biologic_function, cell_function, organ_or_tissue_function, physiologic_function, organism_function.
Concept 14 population_group, professional_or_occupational_group, machine_activity, group_attribute, group, age_group, family_group, patient_or_disabled_group.
Concept 15 clinical_attribute, anatomical_abnormality, acquired_abnormality, congenital_abnormality, health_care_activity, injury_or_poisoning, pathologic_function, experimental_model_of_disease, mental_or_behavioral_dysfunction, disease_or_syndrome, neoplastic_process, cell_or_molecular_dysfunction, therapeutic_or_preventive_procedure.
Concept 16 event, entity, physical_object, substance.
Concept 17 human_caused_phenomenon_or_process, phenomenon_or_process, environmental_effect_of_humanst.
Concept 18 professional_society, organization, health_care_related_organization, self_help_or_relief_organization.
Concept 19 governmental_or_regulatory_activity, educational_activity, geographic_area, behavior, daily_or_recreational_activity, social_behavior, occupational_activity, individual_behavior.
Concept 20 hazardous_or_poisonous_substance, antibiotic, neuroreactive_substance_or_biogenic_amine, pharmacologic_substance, vitamin, hormone, immunologic_factor, enzyme, receptor, biologically_active_substance.

heading: Appendix D. Quantitative Cluster Analysis

heading: D.1 UMLS
text: To quantify the cluster quality, we compare our learned clusters against ground-truth clusters available for UMLS and FB15k-237. Specifically. for UMLS we utilize the semantic group information [Bodenreider and McCray, 2003], which is composed of groups such as Physiology, Living Beings, Concepts & Ideas, and Chemicals & Drugs. Altogether, semantic groups amount to 14 disjoint clusters, constructed on the basis of semantic validity, parsimony, completeness and utility. Table 10 summarizes our results: ConFormA and ConFormAE, both with random paths initialization, score higher NMI than clustering directly over neural link predictor embeddings. By manually inspecting the clusters, we can furthermore say that all approaches recover the group information rather faithfully.
D.2 FB15K-237
To assess the quality of concepts learned for FB15K-237 we utilize the notable_type information available in Freebase. Extracting this information for all entities in FB15K-237 gives rise to 3.8k overlapping clusters, with cluster sizes ranging from 14.5k entities to single-entity clusters. Comparing against the entire set of the overlapping ground-truth clusters would not be very informative in our case, as in this work we have restricted ourselves to smaller numbers of disjoint clusters. Instead, we propose the following two approaches:
1. Comparison against Top 100 Clusters We select the 100 largest clusters from the ground truth clustering – jointly, these cover all of the entities in FB15K-237, some more than once. The resulting clusters range from concepts such as abstract, animate and person, through to award nominee, film and educational institution. In order to compare the learned clusterings against the ground truth, we compute the Normalized Mutual Information (NMI) for overlapping clusters [Lancichinetti et al., 2009], comparing the quality of clusters obtained through clustering vanilla ComplEx and DistMult embeddings against random-paths-initialized ConFormA and randompaths-initialized ConFormAE. The results are reported in Table 11.
2. Boolean Cluster Matching While comparing only against the largest clusters can assess how well the clusters capture global properties of the entities, it does not allow us to assess the quality of more fine-grained clusters. To address this, we propose the following comparison: firstly, we describe each cluster using a Boolean vector such that each entry of the vector corresponds to the presence or absence of a given entity in a cluster. Next, we use the Jaccard Index to find for each learned cluster the closest corresponding cluster in the set of ground truth clusters. Lastly, we compute NMI between the entire clustering learned by random-paths-initialized ConFormA or random-paths-initialized ConFormAE, and the selected set of ground-truth clusters. The resulting NMIs can be found in Table 12.
We find that across all 3 approaches the NMI is relatively low, indicating that all the methods struggle to recover the ground truth information as defined by the notable type information in FB. It is worth noting, however, that ConFormA with relatively low-dimensional random paths representations, p ∈ R2Nr where Nr = 237 for FB15K-237,
consistently outperforms clustering even significantly larger neural link predictor embeddings. Furthermore, across both, Table 11 and Table 12, ConFormAE initialized with random paths representations improves upon nearly all other scores.
Qualitatively inspecting the cluster matches with the highest Jaccard scores (Table 13) we find, as expected, that the model learns a concept which is very similar to the ground truth. In the case of the lowest Jaccard scores (Table 14) we find that despite the scores being low, concepts learned by ConFormA and ConFormAE are not in themselves poor quality or random. Rather, the issue lies in that the closest corresponding notable_types cluster encodes a very different meaning, resulting in poor overlap between the entities.

heading: Appendix E. Link Prediction Results
text: In this section we provide additional link prediction performance results of our method. In Table 15 we report experiments investigating the impact of performing link prediction with ConFormA using concepts learned via directly clustering ComplEx embeddings. We find that in most cases the augmentation either degrades the performance or there is no significant improvement. Tables 17 to 22 show top 10 test triples for which our method achieves greatest improvement over the baseline neural link predictor. In Table 16 we visualize link prediction results shown earlier in tabular form (Table 3) and in Table 23 we provide link prediction performance for UMLS. In Table 24 we include link prediction results with Tucker, an additional neural link prediction model. Lastly, in Table 25 we provide an extension of results for link prediction on sparsified KGs, showing results for both, ComplEx and DistMult, for a range of embedding sizes.

heading: E.1 Link Prediction with TuckER
text: To further demonstrate that our method can improve upon a wide range of neural link predictors and embedding sizes, we report link prediction results with TuckER [Balazevic et al., 2019] – a recent neural link predictor which has achieved competitive performance for small embedding sizes.
To compute the TuckER baselines for ranks k in {50, 100, 500}, following the training set-up described in [Balazevic et al., 2019], we used the Adam optimizer [Kingma and Ba, 2015] and performed a gridsearch over the learning rates in {0.1, 0.05, 0.01, 0.005, 0.001, 0.0005, 0.0001}. We set the predicate embedding size equal to the entity embedding size for both datasets. A batch-size of 128 and learning rate decay of 1.0 were held constant for all experiments.
Table 13: Examples of concepts learned by ConFormA and ConFormAE for FB15K-237 alongside their ground-truth examples, with some of the highest Jaccard Index scores in the entire clustering – 1.0 for ConFormAE and 0.952 for ConFormA, using ComplEx with k=500 and 100 clusters.

heading: Ground Truth
text: <film.film_ festival_event> 2010 Sundance Film Festival, 1982 Cannes Film Festival, 62nd Berlin International Film Festival, 39th Berlin International Film Festival, 2011 Sundance Film Festival, 2011 Toronto International Film Festival, 2009 Sundance Film Festival, 2008 Sundance Film Festival, 2012 Sundance Film Festival, 34th Berlin International Film Festival, 2009 Toronto International Film Festival, 59th Berlin International Film Festival, 2008 Toronto International Film Festival, 32nd Berlin International Film Festival, 58th Berlin International Film Festival, 2000 Cannes Film Festival, 60th Berlin International Film Festival, 2012 Toronto International Film Festival, 61st Berlin International Film Festival, 2010 Toronto International Film Festival ConFormA Concept_72 2009 Sundance Film Festival, 2000 Cannes Film Festival, 2009 Toronto International Film Festival, 2008 Toronto International Film Festival, 59th Berlin International Film Festival, 1982 Cannes Film Festival, 32nd Berlin International Film Festival, 34th Berlin International Film Festival, 39th Berlin International Film Festival, 60th Berlin International Film Festival, 2010 Toronto International Film Festival, 58th Berlin International Film Festival, 2010 Sundance Film Festival, 2011 Sundance Film Festival, 61st Berlin International Film Festival, 2011 Toronto International Film Festival, 2012 Sundance Film Festival, 62nd Berlin International Film Festival, 2012 Toronto International Film Festival Ground Truth <sports.sports _league_draft> 2005 Major League Baseball draft, 2005 NFL Draft, 2007 NBA Draft, 2004 NFL Draft, 2006 Major League Baseball draft, 2002 Major League Baseball draft, 2003 NFL Draft, 2006 NFL Draft, 2005 NBA Draft, 2003 NBA Draft, 2007 NFL Draft, 1997 Major League Baseball draft, 2004 NBA Draft, 1995 Major League Baseball draft, 2008 NBA Draft, 2004 Major League Baseball draft, 2003 Major League Baseball draft, 2007 Major League Baseball draft, 2006 NBA Draft, 2008 NFL Draft
ConFormAE Concept_36 2005 Major League Baseball draft, 2005 NFL Draft, 2007 NBA Draft, 2004 NFL Draft, 2006 Major League Baseball draft, 2002 Major League Baseball draft, 2003 NFL Draft, 2006 NFL Draft, 2005 NBA Draft, 2003 NBA Draft, 2007 NFL Draft, 1997 Major League Baseball draft, 2004 NBA Draft, 1995 Major League Baseball draft, 2008 NBA Draft, 2004 Major League Baseball draft, 2003 Major League Baseball draft, 2007 Major League Baseball draft, 2006 NBA Draft, 2008 NFL Draft
Link prediction results with TuckER are shown in Table 24, where we find that ConFormA and ConFormAE consistently outperform the baseline TuckER model for nearly all of the configurations.

heading: Ground Truth
text: <default_domain.facts_from_the_community> Republican Party
Concept_84 Communist Party of the Soviet Union, Communist Party of India (Marxist), Kuomintang, Republican Party, Whig Party, Democratic-Republican Party, Federalist Party, Democratic Party, Canadian Alliance. <terrorism.terrorist _organization> al-Qaeda, Hamas, Hezbollah
Concept_11 Austria-Hungary, Kingdom of Great Britain, Byzantine Empire, Empire of Japan, Kingdom of Naples, Russian Soviet Federative Socialist Republic, Kingdom of Romania, Spanish Empire, Kingdom of Sardinia, Prussia, Kingdom of Portugal, House of Plantagenet, Kingdom of Italy, Hamas...

heading: Appendix F. Datasets
text: For each of the datasets used to evaluate our approach – UMLS, WN18RR and FB15K-237 – we provide the frequency bins shown in Table 26 used to divide relations into frequency sub-populations for computing the link prediction results in Fig. 3.

heading: Appendix G. Training Details

heading: G.1 Baselines
text: To obtain the best parameters for the baselines, we ran the same grid search for all of the datasets on both, ComplEx and DistMult, with the ranks set to {50, 100, 200} for UMLS and {500, 1000, 2000} for WN18RR and FB15K-237, using the standard train/validation/test splits. The grid consisted of three batch-sizes in {50, 100, 500}, three learning rates: {10−1, 10−2, 10−3} and six regularization strengths in {10−3, 5× 10−3, . . . , 10−1, 5× 10−1}.
G.2 ConFormA
Propositionalisation To generate the representations we explored the parameter range suggested by Perozzi et al. [2014], using a minimum path length of 2, maximum path length in {3, 5, 10, 20, 30} and two number of paths parameters: 32 and 64. We found that the maximum path length parameter was most influential in determining how well a representation captured the characteristics of a given KG. For both, WN18RR and FB15K-237, we found that setting maximum path length to 5 and number of paths to 64 gave competitive results.
Clustering Algorithm We experimented with clustering the propositionalised representations using a number of clustering algorithms: K-Means, Spectral Clustering, Affinity Propagation and DBSCAN. Across these, we have found no significant difference in performance in terms of both, cluster quality and downstream link prediction performance, hence we used Spectral Clustering for all experiments.
Number of clusters The number of clusters was treated as a hyperparameter and chosen from {50, 100, 500, 1000} for FB15K-237 and WN188R, and from {30, 50, 100} for UMLS. As shown in Fig. 4, lower numbers of clusters on average resulted in better link prediction performance.
G.3 ConFormAE
Number of epochs, n, per E-Step: To explore the effect of changing the number of epochs, n, per E-step, we trained a range models and embedding sizes, varying n in {1, 2, 3, 5}. We found that n = 1 provided a good compromise in terms of link prediction performance across different embedding sizes, datasets and neural link predictors - a visualization for WN18RR can be found in Figure Fig. 5.
Cluster initialization: Between the two initialization methods we experimented with – random initialization and Spectral Clustering of random paths propositionalisation – we found no significant difference in performance, hence we used random initialization by default due to its reduced complexity, unless the contrary is specified.
Number of clusters: We used the same ranges to select the number of clusters as for ConFormA. It is worth noting, however, that while for ConFormA the number of clusters is fixed, in ConFormAE that number of clusters can decrease during training if no entities
are assigned to some concepts. The number of clusters specified in Fig. 4 for ConFormAE corresponds to the initial number of clusters.

heading: G.4 Evaluation
text: During evaluation, we only consider the triples and entities appearing in the original dataset, to make sure the evaluation metrics for ConFormA and ConFormAE are computed using exactly the same protocol as for the baselines.
{500, 1000, 2000}. Each experiment was repeated with 5 different random seeds and averages plotted.

Review summaries:
The paper aims to improve the performance of neural link predictors on sparse KGs, by augmenting KGs with clusters of concepts. It proposes two versions of augmentations: (1) ConFormA which inserts the clustered concept, and (2) ConformAE which jointly learn the concepts and embeddings through an EM scheme. The authors show that the augmentation helps improve performance of two baselines. on different datasets.