# KGLM: Integrating Knowledge Graph Structure
in Language Models for Link Prediction

Jason Youn1,2,3 Ilias Tagkopoulos 1,2,3
1 Department of Computer Science, University of California, Davis, CA 95616,
USA.
2 Genome Center, University of California, Davis, CA 95616, USA.
3 USDA/NSF AI Institute for Next Generation Food Systems (AIFS),
University of California, Davis, CA 95616, USA.
{jyoun<EMAIL_ADDRESS>
###### Abstract

The ability of knowledge graphs to represent complex relationships at scale
has led to their adoption for various needs including knowledge
representation, question-answering, and recommendation systems. Knowledge
graphs are often incomplete in the information they represent, necessitating
the need for knowledge graph completion tasks. Pre-trained and fine-tuned
language models have shown promise in these tasks although these models ignore
the intrinsic information encoded in the knowledge graph, namely the entity
and relation types. In this work, we propose the Knowledge Graph Language
Model (KGLM) architecture, where we introduce a new entity/relation embedding
layer that learns to differentiate distinctive entity and relation types,
therefore allowing the model to learn the structure of the knowledge graph. In
this work, we show that further pre-training the language models with this
additional embedding layer using the triples extracted from the knowledge
graph, followed by the standard fine-tuning phase sets a new state-of-the-art
performance for the link prediction task on the benchmark datasets.

##  1 Introduction

Knowledge graph (KG) is defined as a directed, multi-relational graph where
entities (nodes) are connected with one or more relations (edges) (Wang et
al., 2017). It is represented with a set of triples, where a triple consists
of (_head entity_ , _relation_ , _tail entity_) or ($h$, $r$, $t$) for short,
for example (_Bill Gates_ , _founderOf_ , _Microsoft_) as shown in Figure 1.
Due to their effectiveness in identifying patterns among data and gaining
insights into the mechanisms of action, associations, and testable hypotheses
(Li and Chen, 2014; Silvescu et al., 2012), both manually curated KGs like
DBpedia (Auer et al., 2007), WordNet (Miller, 1998), KIDS (Youn et al., 2022),
and CARD (Alcock et al., 2020), and automatically curated ones like FreeBase
(Bollacker et al., 2008), Knowledge Vault (Dong et al., 2014), and NELL
(Carlson et al., 2010) exist. However, these KGs often suffer from
incompleteness. For example, 71% of the people in FreeBase have no known place
of birth (West et al., 2014). To address this issue, knowledge graph
completion (KGC) methods aim at connecting the missing links in the KG.

Figure 1: Sample knowledge graph with 6 triples. The graph contains three
unique entity types (circle for person, triangle for company, and square for
location) and 5 unique relation types or 10 if considering both the forward
and inverse relations. The task of the knowledge graph completion is to
complete the missing links in the graph, e.g., (_Bill Gates_ , _bornIn?_ ,
_Washington_) using the existing knowledge graph. Figure 2: Proposed pre-
training approach of the KGLM. First, both the forward and inverse triples are
extracted from the knowledge graph to serve as the pre-training corpus. We
then continue pre-training the language model, RoBERTa in our case, using the
masked language model training objective, with an additional entity/relation-
type embedding layer. The entity/relation-type embedding scheme shown here
corresponds to the KGLMGER, the most fine-grained version where both the
entity and relation types are considered unique. Note that the inverse
relation denoted by -1 is different from its forward counterpart. For
demonstration purposes, we assume all entities and relations to have a single
token.

Graph feature models like path ranking algorithm (PRA) (Lao and Cohen, 2010;
Lao et al., 2011) attempt to solve the KGC tasks by extracting the features
from the observed edges over the KG to predict the existence of a new edge
(Nickel et al., 2015). For example, the existence of the path _Jennifer Gates_
$\xrightarrow{{\raisebox{-2.0pt}[0.0pt][0.0pt]{
$\scriptstyle{\text{\emph{daughterOf}}}$ }}}$ _Melinda French_
$\xleftarrow{{\raisebox{-2.0pt}[0.0pt][0.0pt]{
$\scriptstyle{\text{\emph{divorcedWith}}}$ }}}$ _Bill Gates_ in Figure 1 can
be used as a clue to infer the triple (_Jennifer Gates_ , _daughterOf_ , _Bill
Gates_). Other popular types of models are latent feature models such as
TransE (Bordes et al., 2013), TransH (Wang et al., 2014), and RotatE (Sun et
al., 2019) where entities and relations are converted into a latent space
using embeddings. TransE, a representative latent feature model, models the
relationship between the entities by interpreting them as a translational
operation. That is, the model optimizes the embeddings by enforcing the vector
operation of head entity embedding _h_ plus the relation embedding _r_ to be
close to the tail entity embedding _t_ for a given fact in the KG, or simply
$\emph{{h}}+\emph{{r}}\approx\emph{{t}}$.

Recently, pre-trained language models like BERT (Devlin et al., 2018) and
RoBERTa (Liu et al., 2019) have shown state-of-the-art performance in all of
the natural language processing (NLP) tasks. As a natural extension, models
like KG-BERT (Yao et al., 2019) and BERTRL (Zha et al., 2021) that utilize
these pre-trained language models by treating a triple in the KG as a textual
sequence, e.g., (_Bill Gates_ , _founderOf_ , _Microsoft_) as ‘ _Bill Gates
founder of Microsoft_ ’, have also shown state-of-the-art results on the
downstream KGC tasks. Although such _textual encoding_ (Wang et al., 2021)
models are generalizable to unseen entities or relations (Zha et al., 2021),
they still fail to learn the intrinsic structure of the KG as the models are
only trained on the textual sequence. To solve this issue, a hybrid approach
like StAR (Wang et al., 2021) has recently been proposed to take advantage of
both latent feature models and textual encoding models by enforcing a
translation-based graph embedding approach to train the textual encoders. Yet,
current textual encoding models still suffer from entity ambiguation problems
(Cucerzan, 2007) where an entity _Apple_ , for example, can refer to either
the company Apple Inc. or the fruit. Moreover, there are no ways to
distinguish forward relation (_Jennifer Gates_ , _daughterOf_ , _Melinda
French_) from inverse relation (_Melinda French_ , _daughterOf -1_, _Jennifer
Gates_).

In this paper, we propose the Knowledge Graph Language Model (KGLM) (Figure
2), a simple yet effective language model pre-training approach that learns
from both the textual and structural information of the knowledge graph. We
continue pre-training the language model that has already been pre-trained on
other large natural language corpora using the corpus generated by converting
the triples in the knowledge graphs as textual sequences, while enforcing the
model to better understand the underlying graph structure and by adding an
additional entity/relation-type embedding layer. Testing our model on the
WN18RR dataset for the link prediction task shows that our model improved the
mean rank by 21.2% compared to the previous state-of-the-art method (51 vs.
40.18, respectively). All code and instructions on how to reproduce the
results are available online.111https://github.com/ibpa/KGLM

##  2 Background

Link Prediction. The link prediction (LP) task, one of the commonly researched
knowledge graph completion tasks, attempts to predict the missing head entity
($h$) or tail entity ($t$) of a triple ($h$, $r$, $t$) given a KG $G=(E,R)$,
where $\\{h,t\\}\in E$ is the set of all entities and $r\in R$ is the set of
all relations. Specifically, given a single test positive triple ($h$, $r$,
$t$), its corresponding link prediction test dataset can be constructed by
corrupting either the head or the tail entity in the filtered setting (Bordes
et al., 2013) as

$\begin{gathered}\mathcal{D}_{LP}^{(h,r,t)}=\\\
\\{(\emph{h},\emph{r},\emph{t'})\;|\;t^{\prime}\in(E-\\{h,t\\})\wedge(h,r,t^{\prime})\notin\mathcal{D}\\}\\\
\cup\\{(\emph{h'},\emph{r},\emph{t})\;|\;h^{\prime}\in(E-\\{h,t\\})\wedge(h^{\prime},r,t)\notin\mathcal{D}\\}\\\
\cup\\{(h,r,t)\\},\end{gathered}$ (1)

where
$\mathcal{D}=\mathcal{D}_{train}\cup\mathcal{D}_{val}\cup\mathcal{D}_{test}$
is the complete dataset. Evaluation of the link prediction task is measured
with mean rank (MR), mean reciprocal rank (MRR), and hits@N (Rossi et al.,
2021). MR is defined as

$MR=\frac{\sum\limits_{(h,r,t)\in\mathcal{D}_{test}}rank((h,r,t)\;|\;\mathcal{D}_{LP}^{(h,r,t)})}{|\mathcal{D}_{test}|},$
(2)

where $rank(\cdot|\cdot)$ is the rank of the positive triple among its
corrupted versions and $|\mathcal{D}_{test}|$ is the number of positive test
triples. MRR is the same as MR except that the reciprocal rank
$1/rank(\cdot|\cdot)$ is used. Hits@N is defined as

$\begin{gathered}hits@N=\\\
\frac{\sum\limits_{(h,r,t)\in\mathcal{D}_{test}}\begin{cases}1,&\\!\\!\\!\\!$if
$rank((h,r,t)\;|\;\mathcal{D}_{LP}^{(h,r,t)})<N\\\
0,&\\!\\!\\!\\!otherwise\end{cases}}{|\mathcal{D}_{test}|},\end{gathered}$ (3)

where $N\in\\{1,3,10\\}$ is commonly reported. Higher MRR and hits@N values
are better, whereas, for MR, lower values denote higher performance.

##  3 Proposed Approach

In this work, we propose to continue pre-training, instead of pre-training
from scratch, the language model RoBERTaLARGE (Liu et al., 2019) that has
already been trained on English-language corpora of varying sizes and domains,
using both the forward and inverse knowledge graph textual sequences (Figure
2). Following the convention used in the KG-BERT and StAR (see Appendix A), we
use a textual representation of a given triple, e.g., (_Bill Gates_ ,
_founderOf_ , _Microsoft_) as ‘ _Bill Gates founder of Microsoft_ ’, to
generate the pre-training corpus. However, instead of extracting only the
forward triple as done in the previous work, we extract both the forward and
inverse versions of the triple, e.g., (_Jennifer Gates_ , _daughterOf_ , _Bill
Gates_) and (_Bill Gates_ , _daughterOf -1_, _Jennifer Gates_), where the -1
notation denotes the inverse direction of the corresponding relation.

Table 1: Statistics of the benchmark knowledge graphs used for link prediction. Dataset | # ent | # rel | # train | # val | # test
---|---|---|---|---|---
WN18RR | 40,943 | 11 | 86,835 | 3,034 | 3,134
FB15k-237 | 14,951 | 237 | 272,115 | 17,535 | 20,466
UMLS | 135 | 46 | 5,216 | 652 | 661

To enforce the model to learn the knowledge graph structure, we introduce a
new embedding layer _entity/relation-type embedding_ (ER-type embedding) in
addition to the pre-existing token and position embeddings of RoBERTa as shown
in Figure 2. This additional layer aims to embed the tokens in the input
sequence with its corresponding entity/relation-type, where the set of
entities $E$ in the knowledge graph can have $t_{E}$ different entity types
depending on the schema of the knowledge graph, (e.g., $t_{E}=3$ for person,
company, and location in Figure 1). Note that many knowledge graphs do not
specify the entity types, in which case $t_{E}=1$. For the set of relations
$R$, there exist $t_{R}=2n_{R}$, where $n_{R}$ is the number of unique
relations in the knowledge graph and the multiplier of 2 comes from forward
and inverse directions (e.g., $t_{R}=10$ for the sample knowledge graph in
Figure 1).

Table 2: Link prediction results on the benchmark datasets WN18RR, FB15k-237, and UMLS. Bold numbers denote the best performance for a given metric and class of models. Underlined numbers denote the best performance for a given metric regardless of the model type. Note that we do not report KGLMGER performance since the tested datasets do not specify entity types in their schema. | WN18RR | FB15k-237 | UMLS
---|---|---|---
Method | Hits @1 | Hits @3 | Hits @10 | MR | MRR | Hits @1 | Hits @3 | Hits @10 | MR | MRR | Hits@10 | MR
_Model type: Not based on language models_ |  |  |  |  |  |  |
TransE | .043 | .441 | .532 | 2300 | .243 | .198 | .376 | .441 | 323 | .279 | .989 | 1.84
TransH | .053 | .463 | .540 | 2126 | .279 | .306 | .450 | .613 | 219 | .320 | - | -
DistMult | .412 | .470 | .504 | 7000 | .444 | .199 | .301 | .446 | 512 | .281 | .846 | 5.52
ComplEx | .409 | .469 | .530 | 7882 | .449 | .194 | .297 | .450 | 546 | .278 | .967 | 2.59
ConvE | .390 | .430 | .480 | 5277 | .46 | .239 | .350 | .491 | 246 | .316 | .990 | 1.51
RotatE | .428 | .492 | .571 | 3340 | .476 | .241 | .375 | .533 | 177 | .338 | - | -
GAAT | .424 | .525 | .604 | 1270 | .467 | .512 | .572 | .650 | 187 | .547 | - | -
LineaRE | .453 | .509 | .578 | 1644 | .495 | .264 | .391 | .545 | 155 | .357 | - | -
QuatDE | .438 | .509 | .586 | 1977 | .489 | .268 | .400 | .563 | 90 | .365 | - | -
_Model type: Based on language models_ |  |  |  |  |  |  |
KG-BERT | .041 | .302 | .524 | 97 | .216 | - | - | .420 | 153 | - | .990 | 1.47
StAR | .243 | .491 | .709 | 51 | .401 | .205 | .322 | .482 | 117 | .296 | .991 | 1.49
KGLMBase | .305 | .518 | .730 | 47.97 | .445 | - | - | - | - | - | - | -
KGLMGR | .330 | .538 | .741 | 40.18 | .467 | .200 | .314 | .468 | 125.9 | .289 | .995 | 1.19

In this work, we propose three different variations of ER-type embeddings.
KGLMBase is the simplified version where all entities are assigned a single
entity type and relations are assigned either forward or inverse relation type
regardless of their unique relation types, resulting in a total of 3 ER-type
embeddings. The KGLMGR is a version with granular relation types with
$t_{R}+1$ ER-type embeddings. The KGLMGER is the most granular version where
we utilize all $t_{E}+t_{R}$ ER-type embeddings. In other words, all entity
types as well as all relation types including both directions are considered.

To be specific, we convert a triple ($h$, $r$, $t$) to a sequence of tokens
$w^{(h,r,t)}=\langle\texttt{[s]}w_{a}^{h}w_{b}^{r}w_{c}^{t}\texttt{[/s]}:a\in\\{1..|h|\\}{\And}b\in\\{1..|r|\\}{\And}c\in\\{1..|t|\\}\rangle\in\mathbb{R}^{(|h|+|r|+|t|+2)}$,
where [s] and [/s] are special tokens denoting beginning and end of the
sequence, respectively. The input to the RoBERTa model is then constructed by
adding the ER-type embedding $\mathbf{t}^{(h,r,t)}$ and the
$\mathbf{p}^{(h,r,t)}$ position embeddings to the $\mathbf{w}^{(h,r,t)}$ token
embeddings, as

$\mathbf{X}^{(h,r,t)}=\mathbf{w}^{(h,r,t)}+\mathbf{p}^{(h,r,t)}+\mathbf{t}^{(h,r,t)}.$
(4)

Unlike the segment embeddings in the KG-BERT and StAR that were used to mark
the input tokens with either the entity ($\mathbf{s}_{e}$) or relation
($\mathbf{s}_{r}$), the ER-type embedding now replaces its functionality.
Finally, we pre-train the model using the masked language model (MLM) training
objective (Liu et al., 2019).

For fine-tuning, we extend the idea of how the KG-BERT scores a triple (see
Equation 6 in Appendix A) to take advantage of the ER-type embeddings learned
in our pre-training stage. For a given target triple, we calculate the
weighted average score of both directions as

$\begin{gathered}score_{KGLM}(h,r,t)=\alpha\text{SeqCls}(\mathbf{X}^{(h,r,t)})+\\\
(1-\alpha)\text{SeqCls}(\mathbf{X}^{(t,r^{-1},h)}),\end{gathered}$ (5)

where SeqCls($\cdot$) is a RoBERTa model transformer with a sequence
classification head on top of the pooled output (last layer hidden-state of
the [CLS] token followed by dense layer and $\tanh$ activation function),
${(t,r^{-1},h)}$ denotes the inverse version of $(h,r,t)$, and
$0\leq\alpha\leq 1$ denotes the weight used for balancing the scores from
forward and inverse scores. For example, $\alpha=1.0$ considers only the
forward direction score.

##  4 Experiments and Results

###  4.1 Datasets

We tested our proposed method on three benchmark datasets WN18RR, FB15k-237,
and UMLS as shown in Table 1. WN18RR (Dettmers et al., 2018) is derived from
WordNet (Miller, 1998), a large English lexical database of semantic
relationships between words, FB15k-237 (Toutanova and Chen, 2015) is extracted
from Freebase (Bollacker et al., 2008), a large community-drive KG of general
facts about the world, and UMLS contains biomedical relationships. WN18RR and
FB15k-237 are subsets of WN18 (Bordes et al., 2013) and FB15k (Bordes et al.,
2013), respectively, where the _inverse relation test leakage_ problem, i.e.
the problem of inverted test triples appearing in the training set, has been
corrected.

Table 3: Breakdown of the original hypothesis and their results on WN18RR. For claim 1, we continued to pre-train RoBERTaLARGE using the knowledge graph without the ER-type embeddings. Note that we did not also use the ER-type embeddings layer in the fine-tuning stage. For claim 2, we learned the ER-type embeddings in the fine-tuning stage only without any further pre-training. | ER-type embeddings |
---|---|---
Model | Continue pre-training | Pre-train | Fine-tune | Hits @1 | Hits @3 | Hits @10 | MR | MRR
Claim 1 | o | x | x | 0.331 | 0.529 | 0.728 | 53.5 | 0.462
Claim 2 | x | - | o | 0.322 | 0.489 | 0.672 | 66.4 | 0.439
KGLMGR | o | o | o | 0.330 | 0.538 | 0.741 | 40.18 | 0.467

###  4.2 Settings

We used RoBERTaLARGE (Liu et al., 2019), a BERTLARGE-based architecture with
24 layers, 1024 hidden size, 16 self-attention heads, and 355M parameters, for
the pre-trained language model as it has been shown in a previous study to
perform better than BERT (hits@1 0.243 vs. 0.222 and MR 51 vs. 99, link
prediction on WN18RR) (Wang et al., 2021). For pre-training, we used learning
rate = 5e-05, batch size = 32, epoch = 20 (WN18RR), 10 (FB15k-237), and 1,000
(UMLS), and AdamW optimizer (Loshchilov and Hutter, 2017). For fine-tuning
training data, we sampled 10 negative triples for a positive triple by
corrupting both the head and tail entity 5 times each. We used the validation
set to find the optimal learning rates = $\\{1e-06,5e-07\\}$, batch size =
$\\{16,32\\}$, epochs = $\\{1,2,3,4,5\\}$ for WN18RR and FB15k-237 and 25, 50,
75, 100 for UMLS, and $\alpha$ from 0.0 to 1.0 with an increment of 0.1. For
all experiments, we set $\alpha=0.5$ based on the WN18RR validation set
performance. Both pre-training and fine-tuning were performed on 3 $\times$
Nvidia Quadro RTX 6000 GPUs in a distributed manner using the 16-bit mixed
precision and DeepSpeed (Rasley et al., 2020; Rajbhandari et al., 2020)
library in the stage-2 setting. We used the Transformers library (Wolf et al.,
2019).

###  4.3 Link Prediction Results

The hypothesis behind the KGLM was that learning the ER-type embedding layers
in the pre-training stage using the corpus generated by the knowledge graph,
followed by fine-tuning has the best performance. To test our hypothesis, we
broke down the hypothesis into two separate claims. For the first claim, we
only continued pre-training RoBERTaLARGE followed by fine-tuning without the
ER-type embeddings. This test removes the contribution from the ER-type
embeddings and solely tests the performance gained by further pre-training the
model with the knowledge graph as input. Table 3 shows that claim 1 falls
behind the KGLMGR in all metrics except for hits @1 (0.331 vs. 0.330,
respectively). For the second claim, we did not continue pre-training and
instead used the RoBERTaLARGE pre-trained weights as-is. We then learned the
ER-type embeddings in the fine-tuning stage. This test shows if the ER-type
embeddings can be learned only during the fine-tuning stage. Table 3 shows
that KGLMGR outperforms all of the metrics obtained using the second claim.
This result shows that the combination of these two claims works in a non-
linear fashion to maximize performance.

The results of performing link prediction on the benchmark datasets are shown
in Table 2. Compared to StAR, which had the best performance on MR and hits@10
on WN18RR, KGLMGR outperformed all the metrics with 21.2% improved MR (40.18
vs. 51, respectively) and 4.5% increased hits@10 (0.709 vs. 0.741,
respectively). Although still inferior compared to the graph embedding
approaches, KGLMGR has 35.8% improved hits@1 compared to the best language
model-based approach StAR (0.243 vs. 0.330, respectively). Across all model
types, KGLMGR has the best performance on all metrics for WN18RR except for
hits@1. Although we did not observe any improvement compared to StAR for the
FB15k-237 dataset, we had the best performance on all metrics for UMLS with
21.2% improved MR than ComplEx (1.19 vs. 1.51, respectively). KGLMGR
outperformed KGLMBase in all metrics.

##  5 Conclusion

In this work, we presented KGLM, which introduces a new entity/relation
(ER)-type embedding layer for learning the structure of the knowledge graph.
Compared to the previous language model-based methods that only fine-tune for
a given task, we found that learning the ER-type embeddings in the pre-
training stage followed by fine-tuning resulted in better performance. In
future work, we plan to further test the version of KGLM that takes into
account entity types, KGLMGER, on domain-specific knowledge graphs like KIDS
(Youn et al., 2022) with entity types in their schema.

## Limitations

Although KGLM outperforms state-of-the-art models when the training set
includes full sentences (e.g., UMLS and WN18RR), the model performed similarly
to the state-of-the-art in cases where the training dataset had only
ontological relationships, such as the /music/artist/origin relation present
in the FB15k-237 dataset. One major limitation of the proposed method is the
long training and inference time, which we plan to alleviate by adopting
Siamese-style textual encoders (Wang et al., 2021; Li et al., 2022) in future
work.

## Ethics Statement

The authors declare no competing interests.

## Acknowledgements

We would like to thank the members of the Tagkopoulos lab for their
suggestions. This work was supported by the USDA-NIFA AI Institute for Next
Generation Food Systems (AIFS), USDA-NIFA award number 2020-67021-32855 and
the NIEHS grant P42ES004699 to I.T. J.Y. conceived the project and performed
all experiments. Both J.Y. and I.T. wrote the manuscript. I.T. supervised all
aspects of the project.

## References

  * Alcock et al. (2020) Brian P Alcock, Amogelang R Raphenya, Tammy TY Lau, Kara K Tsang, Mégane Bouchard, Arman Edalatmand, William Huynh, Anna-Lisa V Nguyen, Annie A Cheng, Sihan Liu, et al. 2020.  Card 2020: antibiotic resistome surveillance with the comprehensive antibiotic resistance database.  _Nucleic acids research_ , 48(D1):D517–D525.
  * Auer et al. (2007) Sören Auer, Christian Bizer, Georgi Kobilarov, Jens Lehmann, Richard Cyganiak, and Zachary Ives. 2007.  Dbpedia: A nucleus for a web of open data.  In _The semantic web_ , pages 722–735. Springer.
  * Bollacker et al. (2008) Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. 2008\.  Freebase: a collaboratively created graph database for structuring human knowledge.  In _Proceedings of the 2008 ACM SIGMOD international conference on Management of data_ , pages 1247–1250.
  * Bordes et al. (2013) Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. 2013.  Translating embeddings for modeling multi-relational data.  _Advances in neural information processing systems_ , 26.
  * Carlson et al. (2010) Andrew Carlson, Justin Betteridge, Bryan Kisiel, Burr Settles, Estevam R Hruschka, and Tom M Mitchell. 2010.  Toward an architecture for never-ending language learning.  In _Twenty-Fourth AAAI conference on artificial intelligence_.
  * Cucerzan (2007) Silviu Cucerzan. 2007.  Large-scale named entity disambiguation based on wikipedia data.  In _Proceedings of the 2007 joint conference on empirical methods in natural language processing and computational natural language learning (EMNLP-CoNLL)_ , pages 708–716.
  * Dettmers et al. (2018) Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. 2018.  Convolutional 2d knowledge graph embeddings.  In _Thirty-second AAAI conference on artificial intelligence_.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_.
  * Dong et al. (2014) Xin Dong, Evgeniy Gabrilovich, Geremy Heitz, Wilko Horn, Ni Lao, Kevin Murphy, Thomas Strohmann, Shaohua Sun, and Wei Zhang. 2014.  Knowledge vault: A web-scale approach to probabilistic knowledge fusion.  In _Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining_ , pages 601–610.
  * Lao and Cohen (2010) Ni Lao and William W Cohen. 2010.  Relational retrieval using a combination of path-constrained random walks.  _Machine learning_ , 81(1):53–67.
  * Lao et al. (2011) Ni Lao, Tom Mitchell, and William Cohen. 2011.  Random walk inference and learning in a large scale knowledge base.  In _Proceedings of the 2011 conference on empirical methods in natural language processing_ , pages 529–539.
  * Li et al. (2022) Da Li, Ming Yi, and Yukai He. 2022.  Lp-bert: Multi-task pre-training knowledge graph bert for link prediction.  _arXiv preprint arXiv:2201.04843_.
  * Li and Chen (2014) Yixue Li and Luonan Chen. 2014.  Big biological data: challenges and opportunities.  _Genomics, proteomics & bioinformatics_, 12(5):187.
  * 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.  _arXiv preprint arXiv:1907.11692_.
  * Loshchilov and Hutter (2017) Ilya Loshchilov and Frank Hutter. 2017.  Decoupled weight decay regularization.  _arXiv preprint arXiv:1711.05101_.
  * Miller (1998) George A Miller. 1998.  _WordNet: An electronic lexical database_.  MIT press.
  * Nickel et al. (2015) Maximilian Nickel, Kevin Murphy, Volker Tresp, and Evgeniy Gabrilovich. 2015.  A review of relational machine learning for knowledge graphs.  _Proceedings of the IEEE_ , 104(1):11–33.
  * Rajbhandari et al. (2020) Samyam Rajbhandari, Jeff Rasley, Olatunji Ruwase, and Yuxiong He. 2020.  Zero: Memory optimizations toward training trillion parameter models.  In _SC20: International Conference for High Performance Computing, Networking, Storage and Analysis_ , pages 1–16. IEEE.
  * Rasley et al. (2020) Jeff Rasley, Samyam Rajbhandari, Olatunji Ruwase, and Yuxiong He. 2020.  Deepspeed: System optimizations enable training deep learning models with over 100 billion parameters.  In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pages 3505–3506.
  * Rossi et al. (2021) Andrea Rossi, Denilson Barbosa, Donatella Firmani, Antonio Matinata, and Paolo Merialdo. 2021.  Knowledge graph embedding for link prediction: A comparative analysis.  _ACM Transactions on Knowledge Discovery from Data (TKDD)_ , 15(2):1–49.
  * Silvescu et al. (2012) Adrian Silvescu, Doina Caragea, and Anna Atramentov. 2012.  Graph databases.  _Artificial Intelligence Research Laboratory Department of Computer Science, Iowa State University_.
  * Sun et al. (2019) Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang. 2019.  Rotate: Knowledge graph embedding by relational rotation in complex space.  _arXiv preprint arXiv:1902.10197_.
  * Toutanova and Chen (2015) Kristina Toutanova and Danqi Chen. 2015.  Observed versus latent features for knowledge base and text inference.  In _Proceedings of the 3rd workshop on continuous vector space models and their compositionality_ , pages 57–66.
  * Vu et al. (2019) Thanh Vu, Tu Dinh Nguyen, Dat Quoc Nguyen, Dinh Phung, et al. 2019.  A capsule network-based embedding model for knowledge graph completion and search personalization.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 2180–2189.
  * Wang et al. (2021) Bo Wang, Tao Shen, Guodong Long, Tianyi Zhou, Ying Wang, and Yi Chang. 2021.  Structure-augmented text representation learning for efficient knowledge graph completion.  In _Proceedings of the Web Conference 2021_ , pages 1737–1748.
  * Wang et al. (2017) Quan Wang, Zhendong Mao, Bin Wang, and Li Guo. 2017.  Knowledge graph embedding: A survey of approaches and applications.  _IEEE Transactions on Knowledge and Data Engineering_ , 29(12):2724–2743.
  * Wang et al. (2014) Zhen Wang, Jianwen Zhang, Jianlin Feng, and Zheng Chen. 2014.  Knowledge graph embedding by translating on hyperplanes.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 28.
  * West et al. (2014) Robert West, Evgeniy Gabrilovich, Kevin Murphy, Shaohua Sun, Rahul Gupta, and Dekang Lin. 2014.  Knowledge base completion via search-based question answering.  In _Proceedings of the 23rd international conference on World wide web_ , pages 515–526.
  * Wolf et al. (2019) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et al. 2019.  Huggingface’s transformers: State-of-the-art natural language processing.  _arXiv preprint arXiv:1910.03771_.
  * Yao et al. (2019) Liang Yao, Chengsheng Mao, and Yuan Luo. 2019.  Kg-bert: Bert for knowledge graph completion.  _arXiv preprint arXiv:1909.03193_.
  * Youn et al. (2022) Jason Youn, Navneet Rai, and Ilias Tagkopoulos. 2022.  Knowledge integration and decision support for accelerated discovery of antibiotic resistance genes.  _Nature Communications_ , 13(1):1–11.
  * Zha et al. (2021) Hanwen Zha, Zhiyu Chen, and Xifeng Yan. 2021.  Inductive relation prediction by bert.  _arXiv preprint arXiv:2103.07102_.

##  Appendix A Previous Work

###  A.1 KG-BERT

KG-BERT (Yao et al., 2019) is a fine-tuning method that utilizes the base
version of the pre-trained language model BERT (BERTBASE) (Devlin et al.,
2018) as an encoder for entities and relations of the knowledge graph.
Specifically, KG-BERT first converts a triple ($h$, $r$, $t$) to a sequence of
tokens
$w^{(h,r,t)}=\langle\texttt{[CLS]}w_{a}^{h}\texttt{[SEP]}w_{b}^{r}\texttt{[SEP]}w_{c}^{t}\texttt{[SEP]}:a\in\\{1..|h|\\}{\And}b\in\\{1..|r|\\}{\And}c\in\\{1..|t|\\}\rangle$,
where $w_{n}$ denotes the nth token of either entity or relation, [CLS] and
[SEP] are the special tokens, while $|h|$, $|r|$, and $|t|$ denote the number
of tokens in the head entity, relation, and tail entity, respectively. This
textual token sequence is then converted to a sequence of token embeddings
$\mathbf{w}^{(h,r,t)}\in\mathbb{R}^{d\times(|h|+|r|+|t|+4)}$, where $d$ is the
dimension of the embeddings and 4 is from the special tokens. Then the segment
embeddings
$\mathbf{s}^{(h,r,t)}=\langle(\mathbf{s}_{e})_{\times(|h|+2)}(\mathbf{s}_{r})_{\times(|r|+1)}(\mathbf{s}_{e})_{\times(|t|+1)}\rangle$,
where $\mathbf{s}_{e}$ and $\mathbf{s}_{r}$ are used to differentiate entities
from relations, respectively, as well as the position embeddings
$\mathbf{p}^{(h,r,t)}=\langle\mathbf{p}_{i}:i\in\\{1..(|h|{+}|r|{+}|t|{+}4)\\}\rangle$
are added to the token embeddings $\mathbf{w}^{(h,r,t)}$ to form a final input
representation $\mathbf{X}^{(h,r,t)}\in\mathbb{R}^{d\times(|h|+|r|+|t|+4)}$
that is fed to BERT as input. Then, the score of how likely a given triple
($h$, $r$, $t$) is to be true is computed by

$score_{\text{KG-BERT}}(h,r,t)=\text{SeqCls}(\mathbf{X}^{(h,r,t)}).$ (6)

KG-BERT significantly improved the MR of the link prediction task compared to
the previous state-of-the-art approach CapsE (Vu et al., 2019) (97 compared to
719, an 86.5% decrease), but suffered from poor hits@1 of 0.041 due to the
entity ambiguation problem and lack of structural learning (Wang et al., 2021;
Cucerzan, 2007).

###  A.2 StAR

StAR (Wang et al., 2021) is a hybrid model that learns both the contextual and
structural information of the knowledge graph by augmenting the structured
knowledge in the encoder. It divides a triple into two parts, (_h_ , _r_) and
(_t_), and applies a Siamese-style transformer with a sequence classification
head to generate
$\boldsymbol{u}=\text{Pool}(\mathbf{X}^{(h,r)})\in\mathbb{R}^{d\times(|h|+|r|+3)}$
and
$\boldsymbol{v}=\text{Pool}(\mathbf{X}^{(t)})\in\mathbb{R}^{d\times(|t|+2)}$,
respectively, where Pool($\cdot$) is the output of the RoBERTa’s pooling
layer. The first scoring module focuses on classifying the triple by applying
a

$score_{\text{StAR}}^{c}(h,r,t)=\text{Cls}([\boldsymbol{u};\boldsymbol{u}\times\boldsymbol{v};\boldsymbol{u}-\boldsymbol{u};\boldsymbol{v}]),$
(7)

where Cls($\cdot$) is a neural binary classifier with a dense layer followed
by a softmax activation function. The second scoring module then adopts the
idea of how translation-based graph embedding methods like TransE learns the
graph structure by minimizing the distance between $\boldsymbol{u}$ and
$\boldsymbol{v}$ as

$score_{\text{StAR}}^{d}(h,r,t)=-||\boldsymbol{u}-\boldsymbol{v}||,$ (8)

where $||\cdot||$ is the _L2_ -normalization. During the training, StAR uses a
weighted average of the binary cross entropy loss computed using
$score_{\text{StAR}}^{c}(h,r,t)$ and the margin-based hinge loss computed
using $score_{\text{StAR}}^{d}(h,r,t)$, whereas only the
$score_{\text{StAR}}^{c}(h,r,t)$ is used for inference. This approach shows a
new state-of-the performance over the metrics MR (51) and hits@10 (0.709), as
well as significantly improving the hits@1 compared to the KG-BERT (0.041 to
0.243, a 492.7% increase).


26 end foreach

27 if  _all the $accept(\mathcal{S},C_{i})$ are equal and non-empty_ then

28 return $isLeafPower(G-(C_{1}\cup Y_{1}),k)$

29

30

31

32 end foreach

33

34 end foreach

35 return “Not a $k$-leaf power”

36

37 end

Algorithm 2 Deciding if a graph is a $k$-leaf power.

###### Theorem 5.1

Let $k$ be a fixed positive integer. Then Algorithm 2 correctly decides
whether a graph $G$ is a $k$-leaf power, and runs in time
$O(n^{(d^{k}+1)3|S(k,3k)|+6})$, where $d=3|S(k,3k)|\cdot 2^{|S(k,3k)|}$.

  * Proof.

We argue correctness and complexity separately.

_Correctness._ Assume that $G$ admits a $k$-leaf root of arity at most $d$.
Then it will be found on line 2, by Lemma 2.2. Otherwise, if $G$ is a $k$-leaf
power, all its $k$-leaf roots have arity at least $d+1$. By Lemma 3.6, $G$
admits a homogeneous similar structure
$\mathcal{S}=(\mathcal{C},\mathcal{Y},z,\mathcal{L})$ with
$|\mathcal{C}|=3|S(k,3k)|$, with each $|C_{i}|\leq d^{k}$ and $G[C_{i}\cup
Y_{i}\cup\\{z\\}]$ having maximum degree $d^{k}$ or less.

We show that the algorithm finds such a structure, if one exists. By brute-
force, the main for loop will find a $\mathcal{C}$ that belongs to a desired
homogeneous similar structure
$\mathcal{S}=(\mathcal{C},\mathcal{Y},z,\mathcal{L})$. The $z$ vertex
described on line 2 exists, by Property 2 of similar structures. By Property
3, only the connected component $X_{z}$ of $G^{\prime}$ that contains $z$ can
have neighbors in more than one $C_{i}$, and all the others have neighbors in
exactly one $C_{i}$. Thus lines 2-2 correctly build the $Y_{i}$ subsets.
Moreover, by the properties described in Lemma 3.6, each $G[C_{i}\cup
Y_{i}\cup\\{z\\}]$ must have maximum degree at most $d^{k}$, and thus we will
not enter the _if_ on line 2. After that, since we brute-force every possible
set of layering functions, we will eventually find the correct $\mathcal{L}$
for $\mathcal{S}$. We then explicitly check whether $\mathcal{S}$ is a similar
structure and compute all the $accept$ sets to verify homogeneity. Assuming
that such a $\mathcal{S}$ exists, it follows that it will be found, and that
we will eventually reach line 2.

We can also argue the converse, i.e. that when line 2 is reached,
$\mathcal{S}$ is homogeneous and satisfies all the requirements of Lemma 3.6.
When this line is reached, $\mathcal{S}$ is a similar structure (this is
checked explicitly), and is homogeneous since we compute every $accept$ set.
We have $|\mathcal{C}|=3|S(k,3k)|$ and each $|C_{i}|\leq d^{k}$, since this is
what we enumerate. Moreover, it is checked that each $G[C_{i}\cup
Y_{i}\cup\\{z\\}]$ has degree bounded by $d^{k}$. Therefore, when line 2 is
reached, $\mathcal{S}$ meets all the requirements of Lemma 3.6. We can thus
apply Theorem 3.1 and state that $G$ is a $k$-leaf power if and only if
$G-(C_{1}\cup Y_{1})$ is a $k$-leaf power. Thus the recursive call on line 2
is correct.

If the algorithm never reaches line 2, then by the above, $G$ does not admit
an homogeneous structure with all the desired properties. By contraposition of
Lemma 3.6, $G$ cannot be a $k$-leaf power. This proves the correctness of the
algorithm.

_Complexity._ We can handle the case where $G$ has maximum degree at most
$d^{k}$ in time $O(n(d^{k}k)^{cd^{k}})$ for some constant $c$, by Lemma 2.2.
The enumeration of the possible $\mathcal{C}$’s requires choosing
$l=3|S(k,3k)|$ subsets of $V(G)$ of size at most $d^{k}$. We can
asymptotically bound the number of $\mathcal{C}$’s to enumerate by

$\left(\sum_{i=1}^{d^{k}}{n\choose
i}\right)^{3|S(k,3k)|}\leq\left(\sum_{i=1}^{d^{k}}n^{i}\right)^{3|S(k,3k)|}\leq\left(n^{d^{k}+1}\right)^{3|S(k,3k)|}$

(for large enough $n$). For each such $\mathcal{C}$, the construction and
verifications for $G^{\prime},X,z$ and the $Y_{i}$’s can be done in time
$O(n)$, until we must enumerate every set of layering functions. Such a
$\mathcal{L}$ must assign each vertex in $\mathcal{C}$ an integer between $0$
and $k$. The total number of vertices in $\mathcal{C}$ is at most
$3|S(k,3k)|\cdot d^{k}$, and so the number of layering functions is at most
$(k+1)^{3|S(k,3k)|\cdot d^{k}}$.

Then we must check whether $\mathcal{S}$ is truly a similar structure. At this
point, we must only check that $\mathcal{L}$ satisfies all the requirements of
similar structures, which can be done in time $O(n^{3})$, since if suffices to
compare pairs of vertices of $\mathcal{C}$ and their neighborhoods.

Using Lemma 4.1, one can see that we can compute one
$accept(\mathcal{S},C_{i})$ in time $O(|S(k,3k)|\cdot n^{2}d^{8k}f(k)^{3})$.
To see this, recall that we can enumerate every valued restriction of $k$-leaf
roots for $C_{i}\cup\\{z\\}\cup Y_{i}$ in time $nd^{8k}f(k)^{3}$. We need to
compute the signature of each of those valued trees. Such a signature can be
computed by traversing each node of the valued tree in post-order. Each node
requires filling a vector with at most $|S(k,3k)|$ entries, and so computing
the signature takes time $O(|S(k,3k)|\cdot n)$. Since there are $3|S(k,3k)|$
$C_{i}$’s to consider, computing every $accept$ set takes time
$O(|S(k,3k)|^{2}\cdot n^{2}d^{8k}f(k)^{3})$.

Finally, we note that at each recursion, $G$ becomes smaller since $C_{1}$ is
non-empty, so this whole procedure is repeated at most $n$ times.

Let us mention that the complexity of the case of maximum degree at most
$d^{k}$ is dominated by the main loop, so we may omit it. To sum up we have an
asymptotic complexity of

$n\cdot\left(n^{d^{k}+1}\right)^{3|S(k,3k)|}\cdot(k+1)^{3|S(k,3k)|\cdot
d^{k}}\cdot n^{3}\cdot|S(k,3k)|^{2}\cdot n^{2}d^{8k}f(k)^{3}$

where $d,f(k)$, and $|S(k,3k)|$ depend only on $k$. Assuming that $k\in O(1)$,
this amounts to

$O(n^{(d^{k}+1)3|S(k,3k)|+6})$

##  6 Conclusion

Although this work answers a longstanding open question, there is still much
to do on the topic of leaf powers and $k$-leaf powers.

  * •

Is recognizing $k$-leaf powers fixed-parameter tractable in $k$? That is, can
it be done in time $O(f(k)n^{c})$ for some function $f$ and some constant $c$?

Using the techniques of this work would require finding an homogeneous similar
structure in FPT time, thereby avoiding brute-force enumeration. Although this
appears difficult, it is possible that such structures have graph-theoretical
properties that can be exploited for fast identification. For instance, we
have not used the fact that $G$ is strongly chordal, which may help finding
similar structures.

  * •

Can $k$-leaf powers be recognized in time $O(n^{f(k)})$, where $f(k)$ is more
reasonable than in this work? In particular, can a power tower function be
avoided? It may be possible to find a better type of signature that is more
succinct, but still allows proving Theorem 3.1.

  * •

Can the techniques used here be used to recognize leaf powers? In particular,
can leaf powers be recognized easily if there is an upper bound on the arity
of its leaf root? Or conversely, is there a structure in leaf powers that
admit high arity leaf roots?

## Acknowledgements

The author thanks the anonymous reviewers of the SODA 2022 conference for
their extremely useful suggestions.

## References

  * [1] Jean RS Blair and Barry Peyton.  An introduction to chordal graphs and clique trees.  In Graph theory and sparse matrix computation, pages 1–29. Springer, 1993.
  * [2] Andreas Brandstädt, Van Bang Le, and Dieter Rautenbach.  A forbidden induced subgraph characterization of distance-hereditary 5-leaf powers.  Discrete mathematics, 309(12):3843–3852, 2009.
  * [3] Andreas Brandstädt et al.  Structure and linear time recognition of 3-leaf powers.  Information Processing Letters, 98(4):133–138, 2006.
  * [4] Andreas Brandstädt and Christian Hundt.  Ptolemaic graphs and interval graphs are leaf powers.  In Latin American Symposium on Theoretical Informatics, pages 479–491. Springer, 2008.
  * [5] Andreas Brandstädt, Christian Hundt, Federico Mancini, and Peter Wagner.  Rooted directed path graphs are leaf powers.  Discrete Mathematics, 310(4):897–910, 2010.
  * [6] Andreas Brandstädt, Van Bang Le, and R Sritharan.  Structure and linear-time recognition of 4-leaf powers.  ACM Transactions on Algorithms (TALG), 5(1):1–22, 2008.
  * [7] Andreas Brandstädt and Peter Wagner.  On $(k,l)$-leaf powers.  In International Symposium on Mathematical Foundations of Computer Science, pages 525–535. Springer, 2007.
  * [8] Andreas Brandstädt and Peter Wagner.  On $k$-versus $(k+1)$-leaf powers.  In International Conference on Combinatorial Optimization and Applications, pages 171–179. Springer, 2008.
  * [9] Tiziana Calamoneri and Blerina Sinaimeri.  Pairwise compatibility graphs: A survey.  SIAM Review, 58(3):445–460, 2016.
  * [10] Maw-Shang Chang and Ming-Tat Ko.  The 3-steiner root problem.  In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 109–120. Springer, 2007.
  * [11] Maw-Shang Chang, Ming-Tat Ko, and Hsueh-I Lu.  Linear-time algorithms for tree root problems.  In Scandinavian Workshop on Algorithm Theory, pages 411–422. Springer, 2006.
  * [12] Zhi-Zhong Chen, Tao Jiang, and Guohui Lin.  Computing phylogenetic roots with bounded degrees and errors.  SIAM Journal on Computing, 32(4):864–879, 2003.
  * [13] Michael Dom, Jiong Guo, Falk Hüffner, and Rolf Niedermeier.  Error compensation in leaf root problems.  In International Symposium on Algorithms and Computation, pages 389–401. Springer, 2004.
  * [14] Michael Dom, Jiong Guo, Falk Hüffner, and Rolf Niedermeier.  Extending the tractability border for closest leaf powers.  In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 397–408. Springer, 2005.
  * [15] Guillaume Ducoffe.  The 4-steiner root problem.  In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 14–26. Springer, 2019.
  * [16] David Eppstein and Elham Havvaei.  Parameterized leaf power recognition via embedding into graph products.  Algorithmica, 82:2337–2359, 2020.
  * [17] Joseph Felsenstein.  Inferring phylogenies, volume 2.  Sinauer associates Sunderland, MA, 2004.
  * [18] Frank Gurski and Egon Wanke.  The NLC-width and clique-width for powers of graphs of bounded tree-width.  Discrete Applied Mathematics, 157(4):583–595, 2009.
  * [19] Lars Jaffke, O-joung Kwon, Torstein JF Strømme, and Jan Arne Telle.  Mim-width III. Graph powers and generalized distance domination problems.  Theoretical Computer Science, 796:216–236, 2019.
  * [20] William Kennedy, Guohui Lin, and Guiying Yan.  Strictly chordal graphs are leaf powers.  Journal of Discrete Algorithms, 4(4):511–525, 2006.
  * [21] Manuel Lafond.  On strongly chordal graphs that are not leaf powers.  In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 386–398. Springer, 2017.
  * [22] Ragnar Nevries and Christian Rosenke.  Towards a characterization of leaf powers by clique arrangements.  Graphs and Combinatorics, 32(5):2053–2077, 2016.
  * [23] Naomi Nishimura, Prabhakar Ragde, and Dimitrios M Thilikos.  On graph powers for leaf-labeled trees.  Journal of Algorithms, 42(1):69–108, 2002.
  * [24] Hervé Philippe, Henner Brinkmann, Dennis V Lavrov, D Timothy J Littlewood, Michael Manuel, Gert Wörheide, and Denis Baurain.  Resolving difficult phylogenetic questions: why more sequences are not enough.  PLoS biology, 9(3):e1000602, 2011.
  * [25] Dieter Rautenbach.  Some remarks about leaf roots.  Discrete mathematics, 306(13):1456–1461, 2006.