# CNN-based Dual-Chain Models for
Knowledge Graph Learning

Bo Peng
The Ohio State University
<EMAIL_ADDRESS>
&Renqiang Min
NEC Laboratories America, Inc
<EMAIL_ADDRESS>
&Xia Ning
The Ohio State University
<EMAIL_ADDRESS>
###### Abstract

Knowledge graph learning plays a critical role in integrating domain-specific
knowledge bases when deploying machine learning and data mining models in
practice. Existing methods on knowledge graph learning primarily focus on
modeling the relations among entities as translations among the relations and
entities, and many of these methods are not able to handle zero-shot problems,
when new entities emerge. In this paper, we present a new convolutional neural
network (CNN)-based dual-chain model. Different from translation based
methods, in our model, interactions among relations and entities are directly
captured via CNN over their embeddings. Moreover, a secondary chain of
learning is conducted simultaneously to incorporate additional information and
to enable better performance. We also present an extension of this model,
which incorporates descriptions of entities and learns a second set of entity
embeddings from the descriptions. As a result, the extended model is able to
effectively handle zero-shot problems. We conducted comprehensive experiments,
comparing our methods with 15 methods on 8 benchmark datasets. Extensive
experimental results demonstrate that our proposed methods achieve or
outperform the state-of-the-art results on knowledge graph learning, and
outperform other methods on zero-shot problems. In addition, our methods
applied to real-world biomedical data are able to produce results that conform
to expert domain knowledge.

##  1 Introduction

Real-world knowledge can be represented in directed, multi-relational, and
structured graphs, the so-called knowledge graphs. In a knowledge graph, graph
nodes represent entities of interest and edges encode relations among
entities. Therefore, one piece of knowledge can be succinctly represented by
two nodes and one edge between them in the knowledge graph, where the source
node is referred to _head_ and the destination node is referred to _tail_.
Thus, the whole collection of such (head, relation, tail) triplets captures
entirely the knowledge graph structure and content. Real-world knowledge
graphs include WordNet [15], a large lexical database for English, Google
Knowledge Graph 111https://developers.google.com/knowledge-graph/, a
comprehensive system about facts among people, etc., and DBpedia [10], a
structured knowledge base for information extracted from Wikipedia, etc.

Typically, knowledge graphs suffer from incompleteness, that is, many
relations (i.e., edges) among entities (i.e., nodes) in the graphs cannot be
established due to the limited or unknown information. It is substantially
significant to enable complete knowledge graphs. For example, a complete
knowledge graph on the relations between diseases and genes, and the relations
between genes and drugs, could dramatically help improve medicine and health
care. However, knowledge graph completion, and in general, knowledge graph
learning, is a very challenging task, requiring strong modeling power to
capture the underlying logic that governs the formation of the head-relation-
tail triplets, and thus, the knowledge.

Substantial research efforts have been dedicated to knowledge graph learning,
in particular, from the deep learning community, due to the extraordinary
capability of deep learning in modeling complicated relations among data.
Quite a few deep learning methods [2, 22, 11, 7, 8, 25, 21, 4] (Section 2)
have been developed and have dramatically improved knowledge graph learning.
Still, there exist increasing needs to further improve knowledge graph
learning performance, particularly for high-impact applications such as
medicine and health care. In addition, being able to leverage additional
information from other sources, for example, descriptions on entities, to
improve knowledge graph learning, is very promising but less explored.

In this paper, we present our efforts toward improving knowledge graph
learning as follows:

  * •

We present new deep learning methods, termed as Convolutional Neural Network
(CNN)-based Dual-Chain methods, denoted as $\mathop{\mathtt{CDC}}\limits$, for
knowledge graph learning. Very different from existing methods (Section 2),
$\mathop{\mathtt{CDC}}\limits$ models the interactions among relations and
entities via a CNN over their respective embeddings as features for the
corresponding triplet. Then, logistic regression is used to predict whether
the triplets are valid from the learned features.

  * •

In addition to the above primary learning process, we introduced a secondary
chain of simultaneous learning process in $\mathop{\mathtt{CDC}}\limits$,
which learns from sparsified entity and relation embeddings in a same
architecture as in the primary chain. This dual-chain structure in
$\mathop{\mathtt{CDC}}\limits$ helps reduce overfitting, accelerate
convergence and improve learning performance in general.

  * •

We also developed an extension of $\mathop{\mathtt{CDC}}\limits$, denoted as
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$, to incorporate and utilize
textual information (i.e., entity descriptions) in knowledge graph learning.
In $\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$, entities and relations will
both have a second embedding learned from the descriptions via structure
attention and CNNs. The embeddings learned from graph structures (i.e., the
head-relation-tail triplets) and from the descriptions are used together along
the dual chains to enable more accurate prediction on triplets. Thus,
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$ is able to improve learning
performance and handle zero-shot problems [24].

  * •

We conducted comprehensive experiments on 8 public, benchmark datasets, and
compared our methods with another 15methods on knowledge graph learning. The
experimental results demonstrate that our methods are able to achieve or
outperform the state of the art.

  * •

We also investigated our methods on two important biological knowledge graphs:
drug-gene interaction graph and drug-drug interaction graph. Our experimental
results demonstrate that our methods outperform the state-of-the-art knowledge
graph learning methods, and make discoveries supported by expert domain
knowledge.

Table 1 presents the key definitions and notations used in this paper. The
rest of this paper is organized as follows. Section 2 presents the related
work. Section 3 presents the details of $\mathop{\mathtt{CDC}}\limits$ method.
Section 4 presents the details of $\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$
method. Section 5 compares $\mathop{\mathtt{CDC}}\limits$ with existing
methods. Section 6 presents the experimental protocols, datasets and
evaluation metrics. Section 7 presents the experimental results. In Section 8,
we conclude our work and discuss future work.

Table 1: Definitions and Notations notation | meaning
---|---
$\mathop{\mathtt{e}}\limits$/$\mathop{\mathrm{E}}\limits$ | entity/entity set
$\mathop{\mathtt{r}}\limits$/$\mathop{\mathrm{R}}\limits$ | relation/relation set
$\mathop{\mathtt{h}}\limits$/$\mathop{\mathtt{t}}\limits$ | head/tail entity
($\mathop{\mathtt{h}}\limits$, $\mathop{\mathtt{r}}\limits$, $\mathop{\mathtt{t}}\limits$) | a head-relation-tail triplet
$\mathop{\mathrm{S}}\limits$/$\mathop{\mathrm{S}}\limits$’ | set of positive/negative $(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})$ triplets
$\mathop{\mathbf{v}}\limits$/$\mbox{$\mathop{\mathbf{v}}\limits$}^{s}$ | embedding/sparsified embedding of size $k$

##  2 Related Work

In this section, we review the literature on knowledge graph learning,
particularly using deep neural networks, based on how the relations among
entities are formulated and learned, and which information is used to learn
the relations.

###  2.1 Translation based Knowledge Graph Learning

The most popular way to formulate the relations among entities in knowledge
graph learning is through translation, pioneered by the work of Bordes _et
al._ [2] on the TransE method. In TransE, a true relation
$\mathop{\mathtt{r}}\limits$ between head $\mathop{\mathtt{h}}\limits$ and
tail $\mathop{\mathtt{t}}\limits$ is represented as a linear translation among
their respective embeddings
$\mbox{$\mathop{\mathbf{v}}\limits$}_{{\mbox{$\mathop{\mathtt{r}}\limits$}}}$,
$\mbox{$\mathop{\mathbf{v}}\limits$}_{{\mbox{$\mathop{\mathtt{h}}\limits$}}}$
and
$\mbox{$\mathop{\mathbf{v}}\limits$}_{{\mbox{$\mathop{\mathtt{t}}\limits$}}}$,
that is,
$\mbox{$\mathop{\mathbf{v}}\limits$}_{{\mbox{$\mathop{\mathtt{h}}\limits$}}}+\mbox{$\mathop{\mathbf{v}}\limits$}_{{\mbox{$\mathop{\mathtt{r}}\limits$}}}=\mbox{$\mathop{\mathbf{v}}\limits$}_{{\mbox{$\mathop{\mathtt{t}}\limits$}}}$.
Thus, a false relation $\mbox{$\mathop{\mathtt{r}}\limits$}^{\prime}$ between
head $\mbox{$\mathop{\mathtt{h}}\limits$}^{\prime}$ and tail
$\mbox{$\mathop{\mathtt{t}}\limits$}^{\prime}$ will induce a large distance
between
$\mbox{$\mathop{\mathbf{v}}\limits$}_{{\mbox{$\mathop{\mathtt{h}}\limits$}}}+\mbox{$\mathop{\mathbf{v}}\limits$}_{{\mbox{$\mathop{\mathtt{r}}\limits$}}}$
and
$\mbox{$\mathop{\mathbf{v}}\limits$}_{{\mbox{$\mathop{\mathtt{t}}\limits$}}}$.
All the entity and relation embeddings are learned via optimizing a pairwise
ranking objective among all the triplets, that is, distances from positive
triplets are smaller than the distances from their corresponding negative
triplets. Wang _et al._ [22] developed TransH, which also uses the linear
translation as in TransE to model relations. Different from TransE, in TransH,
one hyperplane is learned for each relation. Head and tail entities are
projected onto the hyperplane of a relation as relation-specific embeddings.
The linear translation is done on the hyperplane to predict if the relation
holds for the projected heads and tails. TransR [11] is another translation
based method. In TransR, entities and relations are represented in two
different spaces. For each relation, a mapping function is learned to map the
head and tail entities from the entity space to the relation space, where the
relations between the head and tail entities are represented via the
translation as in TransE. Cluster-based TransR (CTransR) [11] is an extension
of TransR. In CTransR, the triplets of a same relation are clustered into
groups. In each group, a relation embedding is learned, as well as a cluster-
specific mapping function that maps entities into the relation space. Thus, in
CTransR, a relation will have multiple embeddings and multiple mapping
functions so as to capture the different subtypes among a same relation. The
translation among entities is same as that in TransR in the relation space.

Existing work also tackles the mapping functions to embed entities and
relations within the translation based learning framework. In TransD [7], a
dynamic mapping matrix is calculated from the embeddings of entities and
relations to map entities from entity space to relation space. In the relation
space, a translation as in TransE is used to model the relations among
entities. TranSparse [8] uses relation-specific sparse mapping matrices to map
entities into the relation space, similarly as in TransR and TransD. The
sparsity of the mapping matrices varies according to the complexity of the
relations. Thus, complexities among the relations can be captured via mapping
matrix sparsity, and meanwhile, overfitting risks are decreased. DistMult [25]
represents relations using diagonal matrices (e.g., $W_{r}$) and use a
bilinear scoring function to measure the distance from
$\mathop{\mathtt{h}}\limits$ through $\mathop{\mathtt{r}}\limits$ to
$\mathop{\mathtt{t}}\limits$ (e.g.,
$\mbox{$\mathop{\mathtt{h}}\limits$}W_{r}\mbox{$\mathop{\mathtt{t}}\limits$}^{\intercal}$).
In ComplEx [21], the distance from $\mathop{\mathtt{h}}\limits$ through
$\mathop{\mathtt{r}}\limits$ to $\mathop{\mathtt{t}}\limits$ is also measured
by dot product. However, instead of using a single representation for the
entities and relations, ComplEx learns multiple representations for each
entity and relation in different domains. The distances from
$\mathop{\mathtt{h}}\limits$ through $\mathop{\mathtt{r}}\limits$ to
$\mathop{\mathtt{t}}\limits$ in the different domains are then combined
(multiplied) as the final distance. HolE [16] can be considered as a special
case of ComplEx, which models relations between entities using compositional
vector representations based on circular correlations. In ConvE [4], a 2D CNN
architecture is used to convert
$\mbox{$\mathop{\mathbf{v}}\limits$}_{{\mbox{$\mathop{\mathtt{h}}\limits$}}}$
and
$\mbox{$\mathop{\mathbf{v}}\limits$}_{{\mbox{$\mathop{\mathtt{r}}\limits$}}}$
to an estimated
$\tilde{\mbox{$\mathop{\mathbf{v}}\limits$}}_{{\mbox{$\mathop{\mathtt{t}}\limits$}}}$.
The similarity between
$\tilde{\mbox{$\mathop{\mathbf{v}}\limits$}_{{\mbox{$\mathop{\mathtt{t}}\limits$}}}}$
and the true tail embedding
$\mbox{$\mathop{\mathbf{v}}\limits$}_{{\mbox{$\mathop{\mathtt{t}}\limits$}}}$,
via dot product, is used to calculate the probability score of
$(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})$.
Different from these methods mainly based on simple linear translations or
correlations between (transformed) embeddings, our proposed methods learn a
powerful nonlinear scoring metric of the
$(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})$
triplets, and directly model complex interactions between relation and entity
embeddings via a CNN.

pthead
$\mbox{$\mathop{\mathbf{v}}\limits$}_{{\mbox{$\mathop{\mathtt{h}}\limits$}}}$relation
$\mbox{$\mathop{\mathbf{v}}\limits$}_{{\mbox{$\mathop{\mathtt{r}}\limits$}}}$tail
$\mbox{$\mathop{\mathbf{v}}\limits$}_{{\mbox{$\mathop{\mathtt{t}}\limits$}}}$$m_{(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})}\in\mathbb{R}^{k}$primary
chain$n_{k}$ featuremaps in $\mathbb{R}^{k/3}$ptCNN($n_{k}$
kernels)$\mbox{$\mathop{\mathbf{f}}\limits$}\in\mathbb{R}^{n_{k}\times
k/3}$flattenedfeature
mapptflatten$\mathop{\mathbf{g}}\limits$tripletrepresentationptfully-
connectedlayers$\mathop{\mathrm{s}}\limits$ptlogisticregressionsparsified
$\mbox{$\mathop{\mathbf{v}}\limits$}_{{\mbox{$\mathop{\mathtt{h}}\limits$}}}^{s}$sparsified
$\mbox{$\mathop{\mathbf{v}}\limits$}_{{\mbox{$\mathop{\mathtt{r}}\limits$}}}^{s}$sparsified
$\mbox{$\mathop{\mathbf{v}}\limits$}_{{\mbox{$\mathop{\mathtt{t}}\limits$}}}^{s}$$m_{(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})}^{s}\in\mathbb{R}^{k}$secondary
chain$n_{k}$ featuremaps in
$\mathbb{R}^{k/3}$ptpt$\mbox{$\mathop{\mathbf{f}^{s}}\limits$}\in\mathbb{R}^{n_{k}\times
k/3}$flattenedfeature
mappt$\mathop{\mathbf{g}^{s}}\limits$tripletrepresentation$\mathop{\mathrm{s}^{s}}\limits$ptdrop
outdrop outdrop out

Figure 1: $\mathop{\mathtt{CDC}}\limits$ Model Architecture

###  2.2 Knowledge Graph Learning with Additional Information

Existing work also incorporates additional information (e.g., textual
information of entities, paths in knowledge graphs) to improve performance on
knowledge graph learning. DKRL [24] incorporates entity descriptions in words,
and applies a 2-layer CNN to map word descriptions to entity embeddings, in
addition to learning another set of entity and relation embeddings from the
$(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})$
triplets (i.e., knowledge graph structure). DKRL leverages the translation
idea from TransE, and enforces small distances between
$\mbox{$\mathop{\mathbf{v}}\limits$}_{{\mbox{$\mathop{\mathtt{h}}\limits$}}}+\mbox{$\mathop{\mathbf{v}}\limits$}_{{\mbox{$\mathop{\mathtt{r}}\limits$}}}$
and
$\mbox{$\mathop{\mathbf{v}}\limits$}_{{\mbox{$\mathop{\mathtt{t}}\limits$}}}$
for all positive triplets, using the embeddings learned from both word
descriptions and knowledge graph structures. With the entity descriptions,
DKRL is able to calculate embeddings for entities that are not in its training
data, and thus handle the zero-shot problem [24]. CBOW [24] is a variation of
DKRL, in which the descriptions are represented using the bag-of-word
representation by their top-20 words weighted by TF-IDF. R-GCN [19]
incorporates the path information of knowledge graphs. R-GCN learns the
embedding for each entity in the knowledge graph via graph convolution [17],
and uses a similar idea as in DistMult to measure the relation between head
and tail entities (i.e., dot product between head embedding, diagonal matrix
of relation and tail embedding). SSP [23] learns a topic model of the textual
descriptions of entities. Unlike these previous approaches, our methods model
entity descriptions with CNNs over word embeddings enhanced with a structural
attention mechanism and perform knowledge graph completion in our proposed CNN
based triplet scoring framework.

##  3 CNN-based Dual-Chain Model ($\mathop{\mathtt{CDC}}\limits$)

We develop a novel CNN-based Dual-Chain model, denoted as
$\mathop{\mathtt{CDC}}\limits$, for entity and relation prediction in
knowledge graph. $\mathop{\mathtt{CDC}}\limits$ has two chains of learning
processes: a primary chain and a secondary chain. In the primary chain of
learning processes, each entity
$\mbox{$\mathop{\mathtt{e}}\limits$}\in\mbox{$\mathop{\mathrm{E}}\limits$}$
and each relation
$\mbox{$\mathop{\mathtt{r}}\limits$}\in\mbox{$\mathop{\mathrm{R}}\limits$}$
will be embedded into a low-dimensional vector
$\mbox{$\mathop{\mathbf{v}}\limits$}_{\mbox{$\mathop{\mathtt{e}}\limits$}}\in\mathbb{R}^{k}$
and
$\mbox{$\mathop{\mathbf{v}}\limits$}_{{\mbox{$\mathop{\mathtt{r}}\limits$}}}\in\mathbb{R}^{k}$,
respectively, in a same latent space, where $k$ is the embedding dimension. A
CNN will be applied on the entity and relation embeddings so as to capture
their interactions, which will be used to predict
($\mathop{\mathtt{h}}\limits$, $\mathop{\mathtt{r}}\limits$,
$\mathop{\mathtt{t}}\limits$) triplets. We will learn such embeddings via
supervised learning in $\mathop{\mathtt{CDC}}\limits$ such that true
(positive)
$(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})$
triplets will be scored high and false (negative) triplets will be scored low.
A secondary chain of learning processes is designed to relax the primary
learning process so as to avoid overfitting, and meanwhile to strengthen the
major signals that will be learned from the primary chain in order to enforce
robust and consistent predictions. Figure 1 presents the architecture of
$\mathop{\mathtt{CDC}}\limits$.

###  3.1 $\mathop{\mathtt{CDC}}\limits$ Model Architecture

####  3.1.1 Dual Embedding Representations

In $\mathop{\mathtt{CDC}}\limits$, given a triplet
$(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})$,
we stack their embedding vectors
$\mbox{$\mathop{\mathbf{v}}\limits$}_{{\mbox{$\mathop{\mathtt{h}}\limits$}}}$,
$\mbox{$\mathop{\mathbf{v}}\limits$}_{{\mbox{$\mathop{\mathtt{r}}\limits$}}}$
and
$\mbox{$\mathop{\mathbf{v}}\limits$}_{{\mbox{$\mathop{\mathtt{t}}\limits$}}}$
into a matrix
$\mbox{$\mathop{\mathtt{m}}\limits$}_{{(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})}}\in\mathbb{R}^{3\times
k}$, that is,
$\mbox{$\mathop{\mathtt{m}}\limits$}_{{(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})}}=[\mbox{$\mathop{\mathbf{v}}\limits$}_{{\mbox{$\mathop{\mathtt{h}}\limits$}}};\mbox{$\mathop{\mathbf{v}}\limits$}_{{\mbox{$\mathop{\mathtt{r}}\limits$}}};\mbox{$\mathop{\mathbf{v}}\limits$}_{{\mbox{$\mathop{\mathtt{t}}\limits$}}}]$.
Meanwhile, we also use a sparsified version of
$\mbox{$\mathop{\mathtt{m}}\limits$}_{{(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})}}$,
denoted as
$\mbox{$\mathop{\mathtt{m}}\limits$}_{{(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})}}^{s}$,
by randomly dropping out 20% of values in
$\mbox{$\mathop{\mathtt{m}}\limits$}_{{(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})}}$.
Both of
$\mbox{$\mathop{\mathtt{m}}\limits$}_{{(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})}}$
and
$\mbox{$\mathop{\mathtt{m}}\limits$}_{{(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})}}^{s}$
will go through exactly same network architectures with same parameters, and
will be learned with shared parameters in almost identical ways (except drop-
out operations as indicated in Figure 1). Therefore, we only discuss the
learning for
$\mbox{$\mathop{\mathtt{m}}\limits$}_{{(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})}}$
in the following section. The process with
$\mbox{$\mathop{\mathtt{m}}\limits$}_{{(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})}}$/$\mbox{$\mathop{\mathtt{m}}\limits$}_{{(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})}}^{s}$
as input is referred to as the primary/secondary chain, respectively.

The use of the sparsified embeddings in addition to the original embeddings is
inspired by ComplEx [21], which learns multiple embeddings for each entity to
capture different aspects of the entity information. In our experiments, we
observed that learning multiple embeddings to represent each entity (i.e,
replacing
$\mbox{$\mathop{\mathtt{m}}\limits$}_{{(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})}}^{s}$
by another embedding that is also learned from the
$(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})$
triplet) will induce overfitting. Instead, we use the sparsified version
$\mbox{$\mathop{\mathtt{m}}\limits$}_{{\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$}}}^{s}$
as a second representation for
$(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})$.
Thus, the secondary chain is expected to still capture the major signals
learned in
$\mbox{$\mathop{\mathtt{m}}\limits$}_{{\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$}}}$
and strengthen such signals as
$\mbox{$\mathop{\mathtt{m}}\limits$}_{{\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$}}}^{s}$
goes through almost same learning process as
$\mbox{$\mathop{\mathtt{m}}\limits$}_{{\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$}}}$
with same model parameters. Meanwhile, the learning for the model parameters
will be regularized by the drop-out operations along the chains, thus the risk
of overfitting is reduced. The other drop-outs as in Figure 1 will be
discussed in Section 3.1.2.

####  3.1.2 Convolution and Feature Mapping

We first use $n_{c}$ kernels of size 3$\times$3 to conduct convolution over
$\mbox{$\mathop{\mathtt{m}}\limits$}_{{(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})}}$
(and same for
$\mbox{$\mathop{\mathtt{m}}\limits$}_{{(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})}}^{s}$).
The convolution will go through the rows of
$\mbox{$\mathop{\mathtt{m}}\limits$}_{{(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})}}$
as indicated in Figure 2 Therefore, it will capture the interactions between
$\mathop{\mathtt{h}}\limits$, $\mathop{\mathtt{r}}\limits$ and
$\mathop{\mathtt{t}}\limits$ since the kernels have same height as
$\mbox{$\mathop{\mathtt{m}}\limits$}_{{(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})}}$
and thus cover and integrate information from $\mathop{\mathtt{h}}\limits$,
$\mathop{\mathtt{r}}\limits$ and $\mathop{\mathtt{t}}\limits$ at the same
time. It is expected that the interaction patterns among positive triplets are
different from those among negative triplets, and thus lead to different label
predictions. Out of the convolution, we will produce $n_{k}$ feature maps of
size $k/3$$\times$1\. We apply ReLU activation function, defined as
$\text{ReLU}(x)=\max(0,x)$, on each of feature maps to generate non-negative
feature maps. The ReLU activation is used here to only keep the non-negative
interactions among the triplets that will contribute to their labels, and
meanwhile introduces non-linearality in the feature mapping.

pt$\mbox{$\mathop{\mathbf{v}}\limits$}_{{\mbox{$\mathop{\mathtt{h}}\limits$}}}$$\mbox{$\mathop{\mathbf{v}}\limits$}_{{\mbox{$\mathop{\mathtt{r}}\limits$}}}$$\mbox{$\mathop{\mathbf{v}}\limits$}_{{\mbox{$\mathop{\mathtt{t}}\limits$}}}$$3\times
3$ kernel Figure 2: $\mathop{\mathtt{CDC}}\limits$ Convolution over Triplet
Matrix

After the convolution operation, we flatten the feature maps (i.e., the output
of the convolution operation) into a feature vector
$\mathop{\mathbf{f}}\limits$ of size $1\times(n_{k}k/3)$ with 20% of the
values randomly dropped out. We use a fully-connected layer (i.e., a
projection matrix) with ReLU activation function and map
$\mathop{\mathbf{f}}\limits$ into another low-dimension feature
$\mathop{\mathbf{g}}\limits$ as in Equation 1,

$\mbox{$\mathop{\mathbf{g}}\limits$}=f(\mbox{$\mathop{\mathbf{f}}\limits$}\mbox{$\mathop{\mathrm{W}_{f}}\limits$}+\mbox{$\mathop{\mathbf{b}_{f}}\limits$}),$
(1)

where $\mathop{\mathrm{W}_{f}}\limits$ and $\mathop{\mathbf{b}_{f}}\limits$
are the projection matrix and the bias, $f()$ is the ReLU function. After the
mapping, $\mathop{\mathbf{g}}\limits$ will have 20% of its values randomly
dropped out. The embedding
$\mbox{$\mathop{\mathtt{m}}\limits$}_{{(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})}}^{s}$
will go through exactly the same operations with same parameters, except that
drop-out is only applied on the flattened feature maps. The resulted feature
from the fully-connected layer is denoted as $\mathop{\mathbf{g}^{s}}\limits$.
Please note that the two drop-outs in the primary chain are to prevent
overfitting along the primary chain. In the secondary chain, since the input
triplets are already sparsified, we only applied drop-out on the flattened
feature maps, not on the triplet representations. Our experiments showed that
without any drop-outs on the secondary chain, the performance is suboptimal
compared to one drop-out on the secondary chain.

####  3.1.3 Logistic Regression

We consider the feature $\mathop{\mathbf{g}}\limits$ out of the fully-
connected layer as the feature representation of the triplet. In
$\mathop{\mathtt{CDC}}\limits$, a positive triplet should be assigned a high
score and a negative triplet should have a low score. We use logistic
regression to calculate the scores for the triplets based on
$\mathop{\mathbf{g}}\limits$. The scoring function on
$\mathop{\mathbf{g}}\limits$ is as in Equation 2,

$\mbox{$\mathop{\mathrm{s}}\limits$}(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})=\sigma(\mbox{$\mathop{\mathbf{g}}\limits$}\mbox{$\mathop{\mathrm{W}_{l}}\limits$}+\mbox{$\mathop{\mathbf{b}_{l}}\limits$})=\sigma(f(\mbox{$\mathop{\mathbf{f}}\limits$}\mbox{$\mathop{\mathrm{W}_{f}}\limits$}+\mbox{$\mathop{\mathbf{b}_{f}}\limits$})\mbox{$\mathop{\mathrm{W}_{l}}\limits$}+\mbox{$\mathop{\mathbf{b}_{l}}\limits$}),$
(2)

where $\sigma$ is the sigmoid function, $\mathop{\mathrm{W}_{l}}\limits$ and
$\mathop{\mathbf{b}_{l}}\limits$ are the linear mapping weights and bias.
Similarly, for
$\mbox{$\mathop{\mathtt{m}}\limits$}_{{(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})}}^{s}$,
the score out of logistic regression is denoted as
$\mathop{\mathrm{s}^{s}}\limits$. Both $\mathop{\mathrm{s}}\limits$ and
$\mathop{\mathrm{s}^{s}}\limits$ will be optimized as described in Section 3.2
in order to learn the model.

pt$w_{1}$$w_{2}$$w_{3}$$w_{4}$$w_{5}$word embeddings
($D_{{\mbox{$\mathop{\mathtt{e}}\limits$}}}$)$L_{{\mbox{$\mathop{\mathtt{e}}\limits$}}}$$v_{1}$$v_{3}$embedding
matrixstructureattention
($A_{\mbox{$\mathop{\mathtt{e}}\limits$}}$)featuremapptconv&maxpoolingtextual
$\mathop{\mathbf{v}^{d}}\limits$entity embeddingfrom
descriptionsptconv&meanpooling

Figure 3: Entity Embeddings from Descriptions in
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$

pthead
$\mbox{$\mathop{\mathbf{v}}\limits$}_{{\mbox{$\mathop{\mathtt{h}}\limits$}}}$relation
$\mbox{$\mathop{\mathbf{v}}\limits$}_{{\mbox{$\mathop{\mathtt{r}}\limits$}}}$tail
$\mbox{$\mathop{\mathbf{v}}\limits$}_{{\mbox{$\mathop{\mathtt{t}}\limits$}}}$$m_{(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})}\in\mathbb{R}^{k}$structureinformation$n_{k}$
featuremaps in $\mathbb{R}^{k/3}$ptCNN$n_{k}$
kernels$\mbox{$\mathop{\mathbf{f}^{u}}\limits$}\in\mathbb{R}^{n_{k}k/3}$flattenedfeature
mapptflatten$\mathop{\mathbf{g}^{u}}\limits$tripletrepresentationptfully-
connectedlayers$\mathop{\mathrm{s_{str}}}\limits$ptlogisticregressiontextual
$\mbox{$\mathop{\mathbf{v}}\limits$}_{{\mbox{$\mathop{\mathtt{h}}\limits$}}}^{d}$textual
$\mbox{$\mathop{\mathbf{v}}\limits$}_{{\mbox{$\mathop{\mathtt{r}}\limits$}}}^{d}$textual
$\mbox{$\mathop{\mathbf{v}}\limits$}_{{\mbox{$\mathop{\mathtt{t}}\limits$}}}^{d}$$m_{(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})}^{t}\in\mathbb{R}^{k}$entitydescriptions$n_{k}$
featuremaps in
$\mathbb{R}^{k/3}$ptpt$\mbox{$\mathop{\mathbf{f}^{d}}\limits$}\in\mathbb{R}^{n_{k}k/3}$flattenedfeature
mappt$\mathop{\mathbf{g}^{d}}\limits$tripletrepresentation$\mathop{\mathrm{s_{txt}}}\limits$drop
out$\mathop{\mathrm{s}}\limits$

Figure 4: $\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$ Model Architecture

###  3.2 The $\mathop{\mathtt{CDC}}\limits$ Optimization Problem

We use entropy loss as the objective in order to learn the
$\mathop{\mathtt{CDC}}\limits$ model. As mentioned in Section 3.1.3 and shown
in Figure 1, $\mathop{\mathtt{CDC}}\limits$ will produce two scores
$\mathop{\mathrm{s}}\limits$ and $\mathop{\mathrm{s}^{s}}\limits$ for each
triplet. During training, we optimize these two scores jointly. Thus, the
objective function for $\mathop{\mathtt{CDC}}\limits$ is as in Equation 3,

$\displaystyle\min_{\bm{\Theta}}\sum_{\begin{subarray}{c}{(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})\in\mbox{$\mathop{\mathrm{S}}\limits$}}\end{subarray}}\log(\mbox{$\mathop{\mathrm{s}}\limits$}(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$}))+\sum_{\begin{subarray}{c}{(\mbox{$\mathop{\mathtt{h}}\limits$}^{\prime},\mbox{$\mathop{\mathtt{r}}\limits$}^{\prime},\mbox{$\mathop{\mathtt{t}}\limits$}^{\prime})\in\mbox{$\mathop{\mathrm{S}}\limits$}^{\prime}}\end{subarray}}\log(1-\mbox{$\mathop{\mathrm{s}}\limits$}(\mbox{$\mathop{\mathtt{h}}\limits$}^{\prime},\mbox{$\mathop{\mathtt{r}}\limits$}^{\prime},\mbox{$\mathop{\mathtt{t}}\limits$}^{\prime}))+$
(3)
$\displaystyle\sum_{\begin{subarray}{c}{(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})\in\mbox{$\mathop{\mathrm{S}}\limits$}}\end{subarray}}\log(\mbox{$\mathop{\mathrm{s}^{s}}\limits$}(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$}))+\sum_{\begin{subarray}{c}{(\mbox{$\mathop{\mathtt{h}}\limits$}^{\prime},\mbox{$\mathop{\mathtt{r}}\limits$}^{\prime},\mbox{$\mathop{\mathtt{t}}\limits$}^{\prime})\in\mbox{$\mathop{\mathrm{S}}\limits$}^{\prime}}\end{subarray}}\log(1-\mbox{$\mathop{\mathrm{s}^{s}}\limits$}(\mbox{$\mathop{\mathtt{h}}\limits$}^{\prime},\mbox{$\mathop{\mathtt{r}}\limits$}^{\prime},\mbox{$\mathop{\mathtt{t}}\limits$}^{\prime})),$

where
$\bm{\Theta}=\\{\mbox{$\mathop{\mathtt{m}}\limits$}_{{(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})}},\mbox{$\mathop{\mathbf{b}_{f}}\limits$},\mbox{$\mathop{\mathrm{W}_{f}}\limits$},\mbox{$\mathop{\mathbf{b}_{l}}\limits$},\mbox{$\mathop{\mathrm{W}_{l}}\limits$},\mathcal{K}\\}$
is the set of parameters in $\mathop{\mathtt{CDC}}\limits$ and $\mathcal{K}$
is the set of kernels used for convolution, $\mathop{\mathrm{S}}\limits$ is
the set of positive triplets and $\mathop{\mathrm{S}}\limits$’ is manually
corrupted negative set as will be described in Section 3.3, and
$\mathop{\mathrm{s}}\limits$ and $\mathop{\mathrm{s}^{s}}\limits$ are defined
as in Equation 2. That is, $\mathop{\mathtt{CDC}}\limits$ makes predictions
from two input embeddings, and optimizes both of the two predicted scores to
be close to the ground truth. The score $\mathop{\mathrm{s}}\limits$ is used
to predict the relations among triplets during testing.

The reason why only $\mathop{\mathrm{s}}\limits$, instead of both
$\mathop{\mathrm{s}}\limits$ and $\mathop{\mathrm{s}^{s}}\limits$, is used for
prediction is that, when testing, the drop-out rate will be 0. As a result,
the secondary chain will also start from the same entity and relation
embeddings as in the primary chain. Since the architectures of the two chains
are identical, $\mathop{\mathrm{s}}\limits$ and
$\mathop{\mathrm{s}^{s}}\limits$ calculated from the two chains will be
identical. For simplicity, we use $\mathop{\mathrm{s}}\limits$ for prediction
in $\mathop{\mathtt{CDC}}\limits$. However, during model learning, both
$\mathop{\mathrm{s}}\limits$ and $\mathop{\mathrm{s}^{s}}\limits$ are used in
the objective function so $\mathop{\mathrm{s}^{s}}\limits$ can enhance
$\mathop{\mathrm{s}}\limits$ for better optimization. We also observed from
our experiments that the performance without $\mathop{\mathrm{s}^{s}}\limits$
in the objective function is worse than that with both the scores. The reason
why we use entropy loss instead of pairwise ranking loss is that we observed
tie problems from pairwise ranking loss in our experiments, that is, multiple
triplets may have exactly same scores and thus be ranked equally, which causes
overestimate using ranking based metric (e.g., hits at 10 as will be discussed
in Section 6.2).

###  3.3 $\mathop{\mathtt{CDC}}\limits$ Learning Algorithm and Negative
Triplet Generation

We initialize the embeddings and the model parameters using uniform
distributions over
$[-\sqrt{\frac{6}{n_{\text{in}}+n_{\text{out}}}},\sqrt{\frac{6}{n_{\text{in}}+n_{\text{out}}}}]$
[5], where $n_{\text{in}}$ is the in dimension, $n_{\text{out}}$ is the out
dimension of the embeddings or parameters (e.g., for a matrix
$X\in\mathbb{R}^{m\times n}$, $m$ is the in dimension, $n$ is the out
dimension). At each epoch, multiple batches are created and used as training
data, and mini-batch stochastic gradient descent method is used to update all
the parameters. The training batches are generated as follows. We first
randomly choose $n_{b}$ positive triplets from positive training set
$\mathop{\mathrm{S}}\limits$. For every positive triplet
$(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})$,
we generate a corresponding negative triplet by randomly replacing either
$\mathop{\mathtt{h}}\limits$ or $\mathop{\mathtt{t}}\limits$ (but not both at
same time) by $\mbox{$\mathop{\mathtt{h}}\limits$}^{\prime}$ or
$\mbox{$\mathop{\mathtt{t}}\limits$}^{\prime}$, where
$(\mbox{$\mathop{\mathtt{h}}\limits$}^{\prime},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})\notin\mbox{$\mathop{\mathrm{S}}\limits$}$
and
$(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$}^{\prime})\notin\mbox{$\mathop{\mathrm{S}}\limits$}$.
The negative triplets are sampled for each batch of positive triplets. We use
the distribution described in Wang _et al._ [22] to decide to replace head or
tail. Therefore, there will be $n_{b}$ pairs of positive and negative triplets
in a batch. We use the batches of $n_{b}$ pairs of triplets for
$\mathop{\mathtt{CDC}}\limits$ model learning.

##  4 $\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$ with Entity Descriptions

When entity descriptions are available, they may provide additional, useful
information that can help relation prediction over entities. Thus, we extend
$\mathop{\mathtt{CDC}}\limits$ to incorporate available entity descriptions,
and denote the new model as $\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$. Given
the entity descriptions in the form of word vectors,
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$ learns a mapping function from
entity descriptions to entity embeddings. Figure 4 presents the scheme of such
mapping. Structure attention mechanism [12] and two-layers CNN [24] are
applied to learn the entity embeddings from descriptions, denoted as
$\mathop{\mathbf{v}^{d}}\limits$.

###  4.1 Attention and Convolution over Word Embeddings

We use the structure attention mechanism [12] to map the word embeddings of
the descriptions of an entity, denoted as
$D_{{\mbox{$\mathop{\mathtt{e}}\limits$}}}$, to a more expressive embedding
matrix denoted as $L_{{\mbox{$\mathop{\mathtt{e}}\limits$}}}$. The attention
weights are calculated from $D_{{\mbox{$\mathop{\mathtt{e}}\limits$}}}$ as
follows,

$A_{{\mbox{$\mathop{\mathtt{e}}\limits$}}}=\text{softmax}(V\tanh(UD_{{\mbox{$\mathop{\mathtt{e}}\limits$}}}^{\intercal})),$
(4)

where $U$ and $V$ are two weighting matrices shared across all the entities.
$A_{{\mbox{$\mathop{\mathtt{e}}\limits$}}}$ is the attention weight matrix,
which maps $D_{{\mbox{$\mathop{\mathtt{e}}\limits$}}}$ to
$L_{{\mbox{$\mathop{\mathtt{e}}\limits$}}}$ as follows,

$L_{{\mbox{$\mathop{\mathtt{e}}\limits$}}}=A_{{\mbox{$\mathop{\mathtt{e}}\limits$}}}D_{{\mbox{$\mathop{\mathtt{e}}\limits$}}}.$
(5)

Intuitively, each row of $L_{{\mbox{$\mathop{\mathtt{e}}\limits$}}}$
represents one semantic aspect of the entity $\mathop{\mathtt{e}}\limits$’s
description.

We use a two-layer CNN to map the $L_{{\mbox{$\mathop{\mathtt{e}}\limits$}}}$
to an entity embedding $\mathop{\mathbf{v}^{d}}\limits$. In the first layer, a
convolution kernel is applied on $L_{{\mbox{$\mathop{\mathtt{e}}\limits$}}}$,
followed by a max pooling. The output from this layer goes through a second
layer of convolution, followed by a mean pooling. The output will be reshaped
into
$\mbox{$\mathop{\mathbf{v}}\limits$}_{{\mbox{$\mathop{\mathtt{e}}\limits$}}}^{t}$
for the entity $\mathop{\mathtt{e}}\limits$.

###  4.2 Learning with Entity Descriptions

Given the descriptions, we are able to produce two heterogeneous embeddings
for each entity. One is from the structure information (i.e., relations among
entities) and the other is from the textual information (i.e., entity
descriptions in words). We use the architecture shown in Figure 4 to calculate
two scores $\mathop{\mathrm{s_{str}}}\limits$ and
$\mathop{\mathrm{s_{txt}}}\limits$ from these two embeddings, respectively,
and use the mean of these two scores as the output from the architecture. This
method is denoted as $\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$. That is,
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$ replaces the sparsified version of
the entity embeddings in $\mathop{\mathtt{CDC}}\limits$ (Figure 1) in the
inputs by the entity description embeddings (Figure 4), and the two scores at
the output in $\mathop{\mathtt{CDC}}\limits$ by the mean of two scores. Also,
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$ applies drop-outs over the triplet
representations, with all the other architectures in
$\mathop{\mathtt{CDC}}\limits$ remained same. The reason why the mean of
$\mathop{\mathrm{s_{str}}}\limits$ and $\mathop{\mathrm{s_{txt}}}\limits$ is
used as the output is that we consider the embeddings from the entity
descriptions and knowledge graph structure information both important in
contributing to the final prediction, as they may encode different,
complementary information about the entities.

In $\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$, we denote the triplet
representations (similar as $\mathop{\mathbf{g}}\limits$ and
$\mathop{\mathbf{g}^{s}}\limits$ in $\mathop{\mathtt{CDC}}\limits$) learned
from structure information and textual information as
$\mathop{\mathbf{g}^{u}}\limits$ and $\mathop{\mathbf{g}^{d}}\limits$,
respectively. We enforce the similarity between
$\mathop{\mathbf{g}^{u}}\limits$ and $\mathop{\mathbf{g}^{d}}\limits$ by
introducing an $\ell_{1}$-norm penalty in
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$ model training so that the
structure information and the textual information can be better fused in the
model. We use $\ell_{1}$ norm here due to its empirical superior performance
over other norms (e.g., $\ell_{2}$ norm) in similar applications [24].
Therefore, the objective function for
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$ is as follows,

$\displaystyle\begin{aligned}
&\min_{\bm{\Theta}}&&\sum_{\begin{subarray}{c}{(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})\in\mbox{$\mathop{\mathrm{S}}\limits$}}\end{subarray}}\log(\mbox{$\mathop{\mathrm{s}}\limits$}(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$}))+\sum_{\begin{subarray}{c}{(\mbox{$\mathop{\mathtt{h}}\limits$}^{\prime},\mbox{$\mathop{\mathtt{r}}\limits$}^{\prime},\mbox{$\mathop{\mathtt{t}}\limits$}^{\prime})\in\mbox{$\mathop{\mathrm{S}}\limits$}^{\prime}}\end{subarray}}\log(1-\mbox{$\mathop{\mathrm{s}}\limits$}(\mbox{$\mathop{\mathtt{h}}\limits$}^{\prime},\mbox{$\mathop{\mathtt{r}}\limits$}^{\prime},\mbox{$\mathop{\mathtt{t}}\limits$}^{\prime}))\\\
&&&+\sum_{{\mbox{$\mathop{\mathrm{S}}\limits$}\cup\mbox{$\mathop{\mathrm{S}}\limits$}^{\prime}}}\lVert\mbox{$\mathop{\mathbf{g}^{d}}\limits$}-\mbox{$\mathop{\mathbf{g}^{u}}\limits$}\rVert_{\ell_{1}},\\\
&\text{s.t.,}&&\mbox{$\mathop{\mathrm{s}}\limits$}(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})=0.5\times(\mbox{$\mathop{\mathrm{s_{txt}}}\limits$}(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})+\mbox{$\mathop{\mathrm{s_{str}}}\limits$}(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})),\\\
&&&\mbox{$\mathop{\mathrm{s}}\limits$}(\mbox{$\mathop{\mathtt{h}}\limits$}^{\prime},\mbox{$\mathop{\mathtt{r}}\limits$}^{\prime},\mbox{$\mathop{\mathtt{t}}\limits$}^{\prime})=0.5\times(\mbox{$\mathop{\mathrm{s_{txt}}}\limits$}(\mbox{$\mathop{\mathtt{h}}\limits$}^{\prime},\mbox{$\mathop{\mathtt{r}}\limits$}^{\prime},\mbox{$\mathop{\mathtt{t}}\limits$}^{\prime})+\mbox{$\mathop{\mathrm{s_{str}}}\limits$}(\mbox{$\mathop{\mathtt{h}}\limits$}^{\prime},\mbox{$\mathop{\mathtt{r}}\limits$}^{\prime},\mbox{$\mathop{\mathtt{t}}\limits$}^{\prime})),\\\
\end{aligned}$ (6)

where
$\bm{\Theta}=\\{U,V,D_{{\mbox{$\mathop{\mathtt{e}}\limits$}}},\Theta_{\text{CNN}},\mbox{$\mathop{\mathtt{m}}\limits$}_{{(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$},\mbox{$\mathop{\mathtt{t}}\limits$})}},\mbox{$\mathop{\mathbf{b}_{f}}\limits$},\mbox{$\mathop{\mathrm{W}_{f}}\limits$},\mbox{$\mathop{\mathbf{b}_{l}}\limits$},\mbox{$\mathop{\mathrm{W}_{l}}\limits$},\mathcal{K}\\}$,
where $\Theta_{\text{CNN}}$ is the set of parameters of the two-layer CNN
including the kernels and bias, and $\mathcal{K}$ is the set of kernels as in
$\mathop{\mathtt{CDC}}\limits$. The learning algorithm for
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$ is same to that for
$\mathop{\mathtt{CDC}}\limits$ as in Section 3.3.

##  5 Comparison between $\mathop{\mathtt{CDC}}\limits$ and Existing Methods

The model that is most similar to $\mathop{\mathtt{CDC}}\limits$ is ConvE [4],
which employs 2D CNNs to learn embeddings for entities and relations. However,
there are several key differences between $\mathop{\mathtt{CDC}}\limits$ and
ConvE. The ConvE model architecture is shown in Figure 6 (extracted from the
ConvE paper [4]).

Figure 5: ConvE Model Architecture

pt$e1$$rel$$3\times 3$ kernel Figure 6: ConvE Convolution over Head and
Relation Embeddings

In ConvE, the embedding of head (e.g., $e1$ in Figure 6) and relation (e.g.,
$rel$ in Figure 6) are stacked and reshaped into a matrix (e.g., of size
10$\times$20, the matrix under “Image” in Figure 6), denoted as $e1$ and $rel$
respectively. Then, a CNN along with a fully-connected layer is employed to
project the head and relation representations together into an embedding
(e.g., the embedding under “Projection to embedding dimension” in Figure 6).
The probabilities of the projected embedding belonging to different tail
entities are calculated via the dot product between the projected embedding
and the corresponding entity embeddings and logits (e.g., the probabilities
under “Predictions” in Figure 6). The key idea of ConvE is similar to TransE
[2], that is, to “translate” head and relation to tail, except that ConvE uses
a CNN rather than a simple linear operation as in TransE to model the
translation. In ConvE, multiple kernels are used in the CNN to capture the
interactions between head and relation. However, the kernels are typically
very small (e.g., 3$\times$3 for 10$\times$20 reshaped matrices). Therefore,
the kernels can only capture the interactions at the boundaries of the head
and relation embeddings as demonstrated in Figure 6. However, in
$\mathop{\mathtt{CDC}}\limits$, the CNN can directly capture the interactions
from the entirety of the head, relation and tail embeddings as demonstrated in
Figure 2.

##  6 Experimental Protocols

###  6.1 Datasets and Comparison Methods

We use the following 8 public datasets in our experiments: Yago3-10 [14], WN18
[2], FB15k [2], FB14k [24], FB15k-237 [4], FB20k [24], DGI [3] and DDI [20].

  * •

_YAGO3-10 dataset_ contains relations among people and their attributes (e.g.,
(“Alex”, “is a”, “football player”)), and each relation has more than 10
triplets.

  * •

_WN18_ is a subset of WordNet [15]. Most triplets in WN18 represent the
semantic relation between words.

  * •

_FB15k dataset_ is a subset of Freebase [1]. Most triplets record facts about
actors, awards, sports, sport teams and movies, and their relations.

  * •

_FB14k dataset_ is a subset of FB15k, with entities that do not have
descriptions removed.

  * •

_FB15k-237 dataset_ is another subset of FB15k, where inverse relations are
removed.

  * •

_FB20k dataset_ is an extension of FB14k. It contains 19,923 entities, among
which 5,019 entities never appear in the training set.

  * •

_DGI dataset_ is a subset of drug-gene interaction dataset described in Cotto
_et al._ [3] with interaction types of frequency higher than 50. Common drug-
gene interaction types include activation and inhibition, etc.

  * •

_DDI dataset_ is a subset of drug-drug interaction dataset TWOSIDES [20] with
interaction types of frequency between 500 and 1,100. Relations in DDI
represent side effects that are induced by drug-drug interactions. Common
drug-drug interaction (i.e., side effect) types include food intolerance,
breast cyst and bunion, etc.

The first 6 datasets are widely used benchmark datasets in knowledge graph
learning. The last 2 datasets are biological datasets for important biological
problems. It’s noteworthy that FB15k and WN18 are reported to have test
leakage issues [4]. Although FB15k and WN18 are widely used, they may not be
good benchmarks for the evaluation purpose. Table 2 presents the statistics of
the datasets.

Table 2: Dataset Statistics

dataset | #entity | #relation | #train | #valid | #test
---|---|---|---|---|---
YAGO3-10 | 123,182 | 37 | 1,079,040 | 5,000 | 5,000
WN18 | 40,943 | 18 | 141,442 | 5,000 | 5,000
FB15k | 14,951 | 1,345 | 483,142 | 50,000 | 59,071
FB14k | 14,904 | 1,341 | 472,860 | 48,991 | 57,809
FB15k-237 | 14,541 | 237 | 272,115 | 17,535 | 20,466
FB20k | 19,923 | 1,341 | 472,860 | 48,991 | 30,490
DGI | 7,217 | 14 | 15,781 | 1,130 | 1,131
DDI | 538 | 25 | 20,951 | 2,618 | 2,617

  * •

The columns corresponding to #entity, #relation, #train, #valid and #test have
the number of entities, the number of relations, the number of training,
validation and testing triplets, respectively.

We compare $\mathop{\mathtt{CDC}}\limits$ with the following 15 methods in
total, where the results of these methods on the datasets are available from
literature: TransE [2], TransH [22], TransR [11], CTransR [11], KG2E [6],
TransD [7], TranSparse [8], HolE [16], DistMult [25], ComplEx [21], R-GCN
[19]. We did not compare with ConvE due to the data unfairness and
reproducibility issues as discussed later in Appendix A.1. We include the
corresponding results in Table 10 in appendix. We compare
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$ with DKRL [24] and SSR [23], which
are able to use entity descriptions and have results reported on FB14k.

###  6.2 Evaluation Metrics

We use two popular evaluation metrics: mean rank
($\mathop{\mathtt{{MR}}}\limits$) [2] and hits at 10
($\mathop{\mathtt{H@10}}\limits$) [2], to evaluate the performance of the
methods, calculated as follows. For each positive triplet in the testing set,
we generate a set of negative triplets by corrupting its head by each of the
other entities in $\mathop{\mathrm{E}}\limits$, but remove the negative
triplets if they are in training or validation set. We predict the scores for
each positive triplet and its corresponding negative triplets, and rank all
the triplets using their predicted scores in descending order.
$\mathop{\mathtt{{MR}}}\limits$ is calculated as the average ranking position
of all the positive testing triplets among their corresponding negative
triplets. Low $\mathop{\mathtt{{MR}}}\limits$ indicates that true positive
triplets are ranked high, and thus good performance.
$\mathop{\mathtt{H@10}}\limits$ is calculated as the fraction of the positive
testing triplets over all positive testing triplets that are ranked into top
10 among their corresponding negative testing triplets. High
$\mathop{\mathtt{H@10}}\limits$ indicates that many true positive triplets are
ranked among top 10 of their negative triplets, and thus good performance.

##  7 Experimental Results

###  7.1 Entity Prediction

For all the testing triplets ($\mathop{\mathtt{h}}\limits$,
$\mathop{\mathtt{r}}\limits$, $\mathop{\mathtt{t}}\limits$), we conducted two
sets of experiments: 1) prediction of $\mathop{\mathtt{t}}\limits$ given
$\mathop{\mathtt{h}}\limits$ and $\mathop{\mathtt{r}}\limits$, and 2)
prediction of $\mathop{\mathtt{h}}\limits$ given $\mathop{\mathtt{t}}\limits$
and $\mathop{\mathtt{r}}\limits$. We evaluated the performance of each
experiment using $\mathop{\mathtt{{MR}}}\limits$ and
$\mathop{\mathtt{H@10}}\limits$, and present the respective average results
over the two sets of the experiments in Table 3, 4 and 5.

Table 3: Entity Prediction on WN18 and FB15k

method | WN18 |  | FB15k
---|---|---|---
$\mathop{\mathtt{{MR}}}\limits$ |  $\mathop{\mathtt{H@10}}\limits$ |  |  $\mathop{\mathtt{{MR}}}\limits$ | $\mathop{\mathtt{H@10}}\limits$
TransE [2] | 251 | 89.2 |  | 125 | 47.1
TransH [22] | 303 | 86.7 |  | 87 | 64.4
TransR [11] | 225 | 92.0 |  | 77 | 68.7
CTransR [11] | 218 | 92.3 |  | 75 | 70.2
KG2E [6] | 331 | 92.8 |  |  59 | 70.4
TransD [7] | 212 | 92.2 |  | 91 | 77.3
TranSparse [8] |  211 | 93.2 |  | 82 | 79.5
DistMult [25] | - | 93.6 |  | - | 82.4
ComplEx [21] | - | 94.7 |  | - | 84.0
HolE [16] | - |  94.9 |  | - | 73.9
$\mathop{\mathtt{CDC}}\limits$ | 380 |  94.9 |  | 73 | 83.3

  * •

The best performance under each metric is bold.
$\mathop{\mathtt{H@10}}\limits$ values are in percent.

Table 3 presents the comparison between $\mathop{\mathtt{CDC}}\limits$ and
another 10 state-of-the-art methods on WN18 and FB15k datasets. The results of
the other 10 methods are cited from their respective publications. On WN18,
$\mathop{\mathtt{CDC}}\limits$ achieves the best
$\mathop{\mathtt{H@10}}\limits$ (94.9%), tied with HolE. In terms of
$\mathop{\mathtt{{MR}}}\limits$ $\mathop{\mathtt{CDC}}\limits$ is not as good
as many of the others. This indicates that $\mathop{\mathtt{CDC}}\limits$ is
able to rank the majority positive testing triplets very high among top 10,
but a small portion of the positive testing triplets lower than other methods.
However, given the large number of entities in WN18 (i.e., 4̃1k as in Table
2), we consider the performance of $\mathop{\mathtt{CDC}}\limits$ in terms of
$\mathop{\mathtt{{MR}}}\limits$ is still reasonable (i.e.,
1-380/40,943=99.07%ile). On FB15k, $\mathop{\mathtt{CDC}}\limits$ is the 2nd
best method in terms of $\mathop{\mathtt{{MR}}}\limits$ (73), slightly worse
than that of KG2E ($\mathop{\mathtt{{MR}}}\limits$ = 59). In terms of
$\mathop{\mathtt{H@10}}\limits$, $\mathop{\mathtt{CDC}}\limits$ is the 2nd
best method ($\mathop{\mathtt{H@10}}\limits$ = 83.3%), only very slightly
worse than ComplEx ($\mathop{\mathtt{H@10}}\limits$ = 84.0%). We believe
$\mathop{\mathtt{H@10}}\limits$ is more meaningful in real applications when
only a top few predictions will be further investigated, and when it is very
costly to validate every one in the top, for example, 211 predictions
(TranSparse’s $\mathop{\mathtt{{MR}}}\limits$ = 211). Thus,
$\mathop{\mathtt{CDC}}\limits$ achieves the state-of-the-art performance in
terms of $\mathop{\mathtt{H@10}}\limits$ on WN18 and FB15k, and comparable
performance on $\mathop{\mathtt{{MR}}}\limits$, compared with the other
methods. Note that we also conducted experiments in which only the primary
chain in $\mathop{\mathtt{CDC}}\limits$ is used and the secondary chain is
removed. However, the performance of this simplified
$\mathop{\mathtt{CDC}}\limits$ is worse than $\mathop{\mathtt{CDC}}\limits$.
For example, on FB15k, this method achieves $\mathop{\mathtt{H@10}}\limits$ =
79.0%, compared to that of $\mathop{\mathtt{CDC}}\limits$ (83.3%). Thus, we
did not present such results in the tables. Please also note that, although we
present the experimental results on FB15k and WN18 as they are widely used
benchmarks, these two datasets may not properly evaluate the methods due to
their serious test leakage issue as reported in [4]. In order to further
evaluate our method, we conduct experiments on more difficult datasets, in
which the interactions among triplets are more complicated.

Table 4: Entity Prediction on YAGO3-10 and FB15k-237

method | YAGO3-10 |  | FB15k-237
---|---|---|---
$\mathop{\mathtt{{MR}}}\limits$ |  $\mathop{\mathtt{H@10}}\limits$ |  |  $\mathop{\mathtt{{MR}}}\limits$ | $\mathop{\mathtt{H@10}}\limits$
DistMult [25] | 5,926 | 54.0 |  |  254 | 41.9
ComplEx [21] | 6,351 | 55.0 |  | 339 | 42.8
R-GCN [19] | - | - |  | - | 41.7
$\mathop{\mathtt{CDC}}\limits$ |  2,061 |  62.9 |  | 267 | 46.2

  * •

The best performance under each metric is bold.
$\mathop{\mathtt{H@10}}\limits$ values are in percent.

Table 4 presents the comparison between $\mathop{\mathtt{CDC}}\limits$ and 3
state-of-the-art methods on YAGO3-10 and FB15k-237 datasets. The results of
the 3 methods are citepd from [4]. Other methods do not have results reported
on these two datasets. On YAGO3-10, $\mathop{\mathtt{CDC}}\limits$ achieves
the best $\mathop{\mathtt{H@10}}\limits$ (62.9%) and
$\mathop{\mathtt{{MR}}}\limits$ among all the methods. On FB15k-237,
$\mathop{\mathtt{CDC}}\limits$ also achieves the best
$\mathop{\mathtt{H@10}}\limits$ and $\mathop{\mathtt{{MR}}}\limits$. Thus,
based on both Table 3 and Table 4, $\mathop{\mathtt{CDC}}\limits$ performs
better than the other comparison methods on average. The state-of-the-art
performance and significant improvement on these difficult datasets properly
demonstrate the strong ability of $\mathop{\mathtt{CDC}}\limits$ in modeling
interactions among triplets.

Table 5: Entity Prediction on DDI and DGI

method | DGI |  | DDI
---|---|---|---
$\mathop{\mathtt{{MR}}}\limits$ |  $\mathop{\mathtt{H@10}}\limits$ |  |  $\mathop{\mathtt{{MR}}}\limits$ | $\mathop{\mathtt{H@10}}\limits$
DistMult [25] | 157 | 86.6 |  | 66 | 22.0
ComplEx [21] | 174 |  87.3 |  | 64 | 31.6
$\mathop{\mathtt{CDC}}\limits$ |  88 | 86.8 |  |  35 | 35.7

  * •

The best performance under each metric is bold.
$\mathop{\mathtt{H@10}}\limits$ values are in percent.

Table 5 presents the comparison between $\mathop{\mathtt{CDC}}\limits$,
DistMult and ComplEx. On DGI, $\mathop{\mathtt{CDC}}\limits$ achieves the best
$\mathop{\mathtt{{MR}}}\limits$ (88) compared to DistMult and ComplEx, and the
2nd best $\mathop{\mathtt{H@10}}\limits$ (86.8%), which is slightly worse than
ComplEx’s. On DDI, $\mathop{\mathtt{CDC}}\limits$ achieves the best
$\mathop{\mathtt{{MR}}}\limits$ and $\mathop{\mathtt{H@10}}\limits$ compared
to DistMult and ComplEx, and the improvement over ComplEx, the 2nd best
method, is very significant (i.e., 45% in $\mathop{\mathtt{{MR}}}\limits$ and
13% in $\mathop{\mathtt{H@10}}\limits$).

###  7.2 Entity Prediction with Descriptions

####  7.2.1 Entity Prediction from Structure and Textual Information

We use FB14k to evaluate the performance of
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$. FB14k is a benchmark dataset to
evaluate knowledge graph learning with descriptions [24]. The statistics of
FB14k is presented in Table 2.

In $\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$, we use Glove [18] pre-trained
100-dimension word vectors to initialize the embeddings for each word in the
entity descriptions. For each entity, we use the first 200 words in its
description with necessary padding, since 99.2% entities have descriptions of
fewer than 200 words. We compared $\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$
with DKRL [24] and SSP [23] as they reported the state-of-the-art performance
on FB14k. For DKRL, when both the entity embeddings from structure information
and from entity descriptions are used in prediction, DKRL is denoted as DKRL
(ALL). When only the entity descriptions are used, the method is denoted as
DKRL (CNN). For SSP, when the knowledge graph learning model and the topic
model are trained separately, SSP is denoted as SSP (Std.). When the tow
models are trained simultaneously, it is denoted as SSP (Joint).

We conduct three sets of experiments on
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$, following the experimental
setting of Xie _et al._ [24]. In the first experiment, we use the mean of the
$\mathop{\mathrm{s_{txt}}}\limits$ and $\mathop{\mathrm{s_{str}}}\limits$ as
the predicted score, as exactly in
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$. In the second experiment, we only
use $\mathop{\mathrm{s_{str}}}\limits$ in
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$, not
$\mathop{\mathrm{s_{txt}}}\limits$, as the predicted score. This method is
denoted as $\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$(str). In the third
experiment, we only use $\mathop{\mathrm{s_{txt}}}\limits$ in
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$, not
$\mathop{\mathrm{s_{str}}}\limits$, as the predicted score. This method is
denoted as $\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$(txt). Table 6 presents
the experimental results from all the comparison methods on FB14k.

Table 6: Entity Prediction with Descriptions on FB14k

method |  $\mathop{\mathtt{{MR}}}\limits$ | $\mathop{\mathtt{H@10}}\limits$
---|---|---
DKRL (CNN) [24] | 113 | 57.6
DKRL (ALL) [24] | 91 | 67.4
SSP (Std.) [23] |  77 | 78.6
SSP (Joint) [23] | 82 | 79.0
$\mathop{\mathtt{CDC}}\limits$ | 109 | 82.7
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$(str) | 101 | 75.7
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$(txt) | 107 | 84.1
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$ | 109 | 84.5

  * •

$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$(str) and
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$(txt) represent that in
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$, only
$\mathop{\mathrm{s_{str}}}\limits$ or $\mathop{\mathrm{s_{txt}}}\limits$ is
used for prediction, respectively. The best performance under each metric is
bold. $\mathop{\mathtt{H@10}}\limits$ values are in percent.

Table 6 demonstrates that $\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$ achieves
the best $\mathop{\mathtt{H@10}}\limits$ (84.5%) among all the methods.
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$(txt) achieves the second best
$\mathop{\mathtt{H@10}}\limits$ (84.1%) and
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$(str) achieves a poor
$\mathop{\mathtt{H@10}}\limits$ (75.7%), even worse than that from
$\mathop{\mathtt{CDC}}\limits$ (82.7%) when no textual information is used.
Both $\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$(txt) and
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$(str) train a
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$ model but use different scores for
prediction. The good performance of
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$(txt) indicates that textual
information is useful in entity prediction, while the worse performance of
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$(str) than
$\mathop{\mathtt{CDC}}\limits$ demonstrates the effectiveness of the dual-
chain architecture in $\mathop{\mathtt{CDC}}\limits$ (i.e., only structure
information is used in the model) in improving performance and reducing
overfitting. The fact that $\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$
outperforms both $\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$(txt) and
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$(str) indicates that the structure
and textual information might be complementary and combining them will benefit
entity prediction. The fact that $\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$
outperforms $\mathop{\mathtt{CDC}}\limits$ indicates the capability of
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$ in integrating structure
information and textual information for entity prediction.

####  7.2.2 Zero-Shot Learning

Most traditional knowledge graph methods can not handle new entities that are
not involved in the knowledge graph during training. Our
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$ provides a natural way to deal
with this zero-shot problem by learning entity representations through their
textual descriptions, and using the scores predicted from the textual
information (i.e., $\mathop{\mathrm{s_{str}}}\limits$ in
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$) for prediction (i.e.,
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$(txt) as in Table 6). We compare
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$ with another two methods CBOW [24]
and DKRL [24], which are able to deal with zero-shot learning. We test these
methods on dataset FB20k [24], in which each testing triplet has at least one
new entity. In our experiments, the testing set is split into 3 subsets with
different types of triplets: 1). triplets with new entities at head, denoted
as $\mathop{\mathtt{N\text{-}h}}\limits$; 2). triplets with new entities at
tail, denoted as $\mathop{\mathtt{N\text{-}t}}\limits$; and 3). triplets with
new entities at both heads and tails, denoted as
$\mathop{\mathtt{N\text{-}ht}}\limits$. Table 7 presents the FB20K data
statistics on $\mathop{\mathtt{N\text{-}h}}\limits$,
$\mathop{\mathtt{N\text{-}t}}\limits$ and
$\mathop{\mathtt{N\text{-}ht}}\limits$.

Table 7: Statistics of FB20k

dataset | #entity | #$\mathop{\mathtt{N\text{-}h}}\limits$ | #$\mathop{\mathtt{N\text{-}t}}\limits$ | #$\mathop{\mathtt{N\text{-}ht}}\limits$ | #total
---|---|---|---|---|---
FB20k | 19,923 | 18,753 | 11,586 | 151 | 30,490

We test $\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$, CBOW and DKRL on these
three subsets and present the results in Table 8. We use the
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$ model that is trained from FB14k
and performs best on FB14k to test FB20k, following the setting in [24]. Our
results demonstrate that $\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$(txt)
substantially outperforms CBOW and DKRL on
$\mathop{\mathtt{N\text{-}h}}\limits$ and
$\mathop{\mathtt{N\text{-}t}}\limits$. In particular,
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$(txt) outperforms DKRL (the second
best method) 30.7% and 40.2% on $\mathop{\mathtt{N\text{-}h}}\limits$ and
$\mathop{\mathtt{N\text{-}t}}\limits$, respectively. On
$\mathop{\mathtt{N\text{-}ht}}\limits$,
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$(txt) is slightly worse than DKRL
(CNN) but still 3.9% better than CBOW. However, given the very limited size of
$\mathop{\mathtt{N\text{-}ht}}\limits$, the slight difference between
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$(txt) and DKRL (CNN) (i.e., only 4
missed hits in $\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$(txt)) is not
significant. Overall, $\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$(txt) is
33.2% better than DKRL (CNN) in terms of the weighted-sum performance over
$\mathop{\mathtt{N\text{-}h}}\limits$, $\mathop{\mathtt{N\text{-}t}}\limits$
and $\mathop{\mathtt{N\text{-}ht}}\limits$ together (i.e., total in Table 8).
These results demonstrate the strong capability of
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$ in dealing with zero-shot problems
in knowledge graph learning.

Table 8: Zero-Shot Learning on FB20k ($\mathop{\mathtt{H@10}}\limits$)

method |  $\mathop{\mathtt{N\text{-}h}}\limits$ |  $\mathop{\mathtt{N\text{-}t}}\limits$ |  $\mathop{\mathtt{N\text{-}ht}}\limits$ | total
---|---|---|---|---
CBOW [23] | 27.1 | 21.7 | 67.2 | 24.6
DKRL (CNN) [23] | 31.2 | 26.1 |  72.5 | 29.5
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$(txt) |  40.8 |  36.6 | 69.8 | 39.3

  * •

The column of “total” has the weighted sum of $\mathop{\mathtt{H@10}}\limits$
over the three cases $\mathop{\mathtt{N\text{-}h}}\limits$,
$\mathop{\mathtt{N\text{-}t}}\limits$ and
$\mathop{\mathtt{N\text{-}ht}}\limits$. The best performance under each metric
is bold. $\mathop{\mathtt{H@10}}\limits$ values are in percent.

###  7.3 Representation Distribution

-100-60-202060100-100-60-202060100drugsgenes$C_{1}^{d}$$C_{2}^{d}$$C_{3}^{d}$$C_{4}^{d}$$C_{5}^{d}$$C_{1}^{g}$$C_{2}^{g}$$C_{3}^{g}$$C_{4}^{g}$$C_{5}^{g}$ Figure 7: Embeddings from $\mathop{\mathtt{CDC}}\limits$ on DGI -100-60-202060100-100-60-202060100drugsgenes Figure 8: Embeddings from ComplEx (Real Vectors) on DGI

We compare the embeddings learned from $\mathop{\mathtt{CDC}}\limits$ and
ComplEx on the DGI dataset, as ComplEx is very strong baseline according to
Table 5. We use t-SNE method [13] to project the embeddings into 2-dimension
space. Figure 7 presents the embeddings of drugs and genes learned from
$\mathop{\mathtt{CDC}}\limits$ in 2D space. Figure 8 presents the embeddings
of the real vectors of drug and genes learned from ComplEx. The projected
embeddings of imaginary vectors are very similar to that in Figure 8 so we
don’t present them here. Please note that in these two figures, a small
Euclidean distance between a drug and a gene does not necessarily mean that
the drug and gene tend to interact due to the ways the interactions are
calculated in $\mathop{\mathtt{CDC}}\limits$ (i.e., through CNN) and in
ComplEx (i.e., through bilinear scoring).

In Figure 7, the drugs and genes are well separated by
$\mathop{\mathtt{CDC}}\limits$, and there are some tight clusters among drugs
and genes, respectively. However, in Figure 8, the drugs and genes are all
mixed, and the clustering structure is less clear. We checked several clusters
in Figure 7. Most of the drugs in drug cluster 1 in Figure 7 (i.e.,
$C_{1}^{d}$) are anti-inflammatory drugs (e.g., betamethasone, dexamethasone,
fluorometholone, hydrocortamate and prednisolone), and belong to drug class
corticosteroid and glucocorticoid. Most of the drugs in drug cluster 2 (i.e.,
$C_{2}^{d}$) are used to treat anxiety, tension, depression and insomnia
(e.g., diazepam, meprobamate, methyprylon, temazepam and zaleplon). Most of
the drugs in drug cluster 5 (i.e., $C_{5}^{d}$) are used to treat allergy
symptoms and allergic rhinitis (e.g., azelastine, cetirizine, clemastine,
dimethindene and triprolidine). There are also some tight gene clusters. For
example, in gene cluster 1 (i.e., $C_{1}^{g}$) in Figure 7, almost all the
genes are from gene group NADH:ubiquinone oxidoreductase core subunits (NDUF,
MT-ND) (e.g., MT-ND5, MT-ND6, NDUFB9, NDUFV1 and NDUFS4). In gene cluster 5
(i.e., $C_{5}^{g}$), almost all the genes are from gene group Potassium
voltage-gated channels (e.g., KCNQ5, KCNH6, KCNA2). Since drugs from a same
drug class tend to be similar in terms of their chemical structures and/or
their interactions with protein pathways, and genes from a same gene family
tend to interact with similar drugs, the clustering structures among the drug
and gene embeddings from $\mathop{\mathtt{CDC}}\limits$ demonstrate that
$\mathop{\mathtt{CDC}}\limits$ is able to learn the entity relations that
conform to knowledge.

###  7.4 Case Study

Table 9: Examples of $\mathop{\mathtt{CDC}}\limits$ Prediction on DDI Dataset | drug 1 | drug 2 | side effects
---|---|---|---
head prediction | fluconazole | metformin | enuresis
guaifenesin | telithromycin | respiratory alkalosis
amlodipine | sumatriptan | breast disorder
voltaren | a-methapred | cystitis interstitial
furosemide | rofecoxib | ingrowing nail
tail prediction | bupropion | acetaminophen | keratoconjunctivitis sicca
cyclobenzaprine | ibuprofen | epicondylitis
amitriptyline | carbamazepine | trigger finger
clonazepam | gabapentin | enuresis
diazepam | primidone | bunion

Table 9 presents some examples from head prediction
($\mathop{\mathtt{N\text{-}h}}\limits$) and tail prediction
($\mathop{\mathtt{N\text{-}t}}\limits$) that $\mathop{\mathtt{CDC}}\limits$
was able to correctly rank among top 10 in the corresponding testing lists,
but ComplEx was not. The examples represented in Table 9 do not involve either
rare drugs or rare side effects. Actually, they correspond to average drug and
side effects in the dataset. Thus, Table 9 shows that
$\mathop{\mathtt{CDC}}\limits$ is able to better prioritize true relations
compared to ComplEx.

##  8 Conclusion and Future Work

In this paper, we developed a CNN-based dual-chain model
($\mathop{\mathtt{CDC}}\limits$) for knowledge graph learning. In
$\mathop{\mathtt{CDC}}\limits$, two learning chains are constructed, one
learning from the ($\mathop{\mathtt{h}}\limits$, $\mathop{\mathtt{r}}\limits$,
$\mathop{\mathtt{t}}\limits$) triplet embeddings via a CNN and the following
layers, the other learning from a sparsified version of the triplet embeddings
via exactly same architectures as in the first chain. Our experimental results
demonstrate that this CNN based method for triplet embedding learning,
together with the dual-chain structure, is able to achieve or outperform the
state-of-the-art results on graph learning. We also extended
$\mathop{\mathtt{CDC}}\limits$ to incorporate textual information (entity
descriptions) into $\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$. Embeddings
from descriptions are also learned via CNN and structure attention for the
entities, in addition to the embeddings learned from knowledge graph
structures. The two types of embeddings are both used to predict entities in
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$. Therefore,
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$ is able to work for new entities
that are not available during model training (i.e., zero-shot problem). Our
experimental results demonstrate that
$\mathop{\mathtt{CDC\\!\texttt{+}}}\limits$ outperforms other methods that are
also able to handle zero-shot problems. In the future research, we will also
incorporate the path and community information from the knowledge graph
structures, in addition to textual information on entities, to further improve
learning performance. We will also consider using the textual information of
the entities along a path or within a community. We will also try and apply
such methods in more impactful applications such as disease-gene association
graph, etc.

## References

  * Bollacker et al. [2008] Bollacker K, Evans C, Paritosh P, Sturge T, Taylor J (2008) Freebase: a collaboratively created graph database for structuring human knowledge. In: Proceedings of the 2008 ACM SIGMOD international conference on Management of data, AcM, pp 1247–1250
  * Bordes et al. [2013] Bordes A, Usunier N, Garcia-Duran A, Weston J, Yakhnenko O (2013) Translating embeddings for modeling multi-relational data. In: Advances in neural information processing systems, pp 2787–2795
  * Cotto et al. [2017] Cotto KC, Wagner AH, Feng YY, Kiwala S, Coffman AC, Spies G, Wollam A, Spies NC, Griffith OL, Griffith M (2017) Dgidb 3.0: a redesign and expansion of the drug–gene interaction database. Nucleic acids research 46(D1):D1068–D1073
  * Dettmers et al. [2018] Dettmers T, Minervini P, Stenetorp P, Riedel S (2018) Convolutional 2d knowledge graph embeddings. In: Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pp 1811–1818
  * Glorot and Bengio [2010] Glorot X, Bengio Y (2010) Understanding the difficulty of training deep feedforward neural networks. In: Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp 249–256
  * He et al. [2015] He S, Liu K, Ji G, Zhao J (2015) Learning to represent knowledge graphs with gaussian embedding. In: Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, ACM, pp 623–632
  * Ji et al. [2015] Ji G, He S, Xu L, Liu K, Zhao J (2015) Knowledge graph embedding via dynamic mapping matrix. In: Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), vol 1, pp 687–696
  * Ji et al. [2016] Ji G, Liu K, He S, Zhao J (2016) Knowledge graph completion with adaptive sparse transfer matrix. In: Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, February 12-17, 2016, Phoenix, Arizona, USA., pp 985–991
  * Lacroix et al. [2018] Lacroix T, Usunier N, Obozinski G (2018) Canonical tensor decomposition for knowledge base completion. arXiv preprint arXiv:180607297
  * Lehmann et al. [2015] Lehmann J, Isele R, Jakob M, Jentzsch A, Kontokostas D, Mendes PN, Hellmann S, Morsey M, Van Kleef P, Auer S, et al. (2015) Dbpedia–a large-scale, multilingual knowledge base extracted from wikipedia. Semantic Web 6(2):167–195
  * Lin et al. [2015] Lin Y, Liu Z, Sun M, Liu Y, Zhu X (2015) Learning entity and relation embeddings for knowledge graph completion. In: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, January 25-30, 2015, Austin, Texas, USA., pp 2181–2187
  * Lin et al. [2017] Lin Z, Feng M, dos Santos CN, Yu M, Xiang B, Zhou B, Bengio Y (2017) A structured self-attentive sentence embedding. CoRR abs/1703.03130
  * Maaten and Hinton [2008] Maaten Lvd, Hinton G (2008) Visualizing data using t-sne. Journal of machine learning research 9(Nov):2579–2605
  * Mahdisoltani et al. [2015] Mahdisoltani F, Biega J, Suchanek FM (2015) YAGO3: A knowledge base from multilingual wikipedias. In: CIDR 2015, Seventh Biennial Conference on Innovative Data Systems Research, Asilomar, CA, USA, January 4-7, 2015, Online Proceedings
  * Miller et al. [1990] Miller GA, Beckwith R, Fellbaum C, Gross D, Miller KJ (1990) Introduction to wordnet: An on-line lexical database. International journal of lexicography 3(4):235–244
  * Nickel et al. [2016] Nickel M, Rosasco L, Poggio TA (2016) Holographic embeddings of knowledge graphs. In: Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, February 12-17, 2016, Phoenix, Arizona, USA., pp 1955–1961
  * Niepert et al. [2016] Niepert M, Ahmed M, Kutzkov K (2016) Learning convolutional neural networks for graphs. In: International conference on machine learning, pp 2014–2023
  * Pennington et al. [2014] Pennington J, Socher R, Manning C (2014) Glove: Global vectors for word representation. In: Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), pp 1532–1543
  * Schlichtkrull et al. [2018] Schlichtkrull M, Kipf TN, Bloem P, van den Berg R, Titov I, Welling M (2018) Modeling relational data with graph convolutional networks. In: European Semantic Web Conference, Springer, pp 593–607
  * Tatonetti et al. [2012] Tatonetti NP, Patrick PY, Daneshjou R, Altman RB (2012) Data-driven prediction of drug effects and interactions. Science translational medicine 4(125):125ra31–125ra31
  * Trouillon et al. [2016] Trouillon T, Welbl J, Riedel S, Gaussier É, Bouchard G (2016) Complex embeddings for simple link prediction. In: International Conference on Machine Learning, pp 2071–2080
  * Wang et al. [2014] Wang Z, Zhang J, Feng J, Chen Z (2014) Knowledge graph embedding by translating on hyperplanes. In: Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, July 27 -31, 2014, Québec City, Québec, Canada., pp 1112–1119
  * Xiao et al. [2017] Xiao H, Huang M, Meng L, Zhu X (2017) Ssp: Semantic space projection for knowledge graph embedding with text descriptions. In: AAAI, vol 17, pp 3104–3110
  * Xie et al. [2016] Xie R, Liu Z, Jia J, Luan H, Sun M (2016) Representation learning of knowledge graphs with entity descriptions. In: Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, February 12-17, 2016, Phoenix, Arizona, USA., pp 2659–2665
  * Yang et al. [2014] Yang B, Yih W, He X, Gao J, Deng L (2014) Embedding entities and relations for learning and inference in knowledge bases. CoRR abs/1412.6575

##  Appendix A Appendix

###  A.1 Data Augmentation and Reproducibility Issues with ConvE

The training and testing data used in the ConvE are constructed in a different
way compared to the data used in $\mathop{\mathtt{CDC}}\limits$ and also the
data used in other baseline methods such as TransE, Distmult and Complex. In
ConvE, before training the model, for each triplet with reversible relation
$(\mbox{$\mathop{\mathtt{h}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$}_{rv},\mbox{$\mathop{\mathtt{t}}\limits$})$,
it adds a reversed triplet
$(\mbox{$\mathop{\mathtt{t}}\limits$},\mbox{$\mathop{\mathtt{r}}\limits$}_{rv},\mbox{$\mathop{\mathtt{h}}\limits$})$
into the training, validation and testing sets, correspondingly. As a result,
ConvE has benefited from this data augmentation to achieve better performance
[9]. Moreover, the reversed triplets on the testing set give the model two
chances to predict a same triplet correctly. Thus, it further over-estimate
the performance. However, in our experiments and the experiments of the
baseline methods, such data augmentation before training is not implemented.
So it is not fair to compare the reported results of ConvE with the
experimental results of our model and baseline methods. This is an issue that
has been recognized by others
222https://github.com/TimDettmers/ConvE/issues/45. It is noteworthy that,
without data augmentation, $\mathop{\mathtt{CDC}}\limits$ can still achieve
similar or even better performance than ConvE on almost all the public
datasets used in our experiments. It demonstrates that the CNN architecture
used in our model is very competitive or even better compared to the CNN
architecture used in ConvE.

We also find that the source code of ConvE published on Github
333https://github.com/TimDettmers/ConvE will cause memory explosion issues and
thus we can not reproduce the reported results in ConvE. Our computers with
16GB RAM can not run their code through on FB15k-237, which is a small dataset
used in their paper, while it only takes about 3.5GB to run our model. Because
of this, we reimplement ConvE with Tensorflow and train it on FB15k. However,
tt produces much worse results compared with the results reported by ConvE.
Consequently upon these facts, we don’t use ConvE as baseline in our
experiments.

###  A.2 Experimental Setting

We implemented the algorithm in python with tensorflow (www.tensorflow.org).

On the WN18, FB15k, FB15k-237 and DDI datasets, the learning rate starts from
3e-3; on the YAGO3-10, FB14k and DGI datasets, the learning rate starts from
1e-3. We decreased the learning rate in each epoch with a rate 0.998 on all
the datasets. We find the following hyper-parameters work well on the
datasets: on dataset WN18, the dimension of entity and relationship embedding
$k$ as 200, the number of convolutional kernel $n_{c}$ as 64, the dimension of
the triplet representations, denoted as $d_{g}$, as 256, the drop-out rate $p$
as 0.2, batch size as 5,000, the number of training epoches as 3,000, and
label smoothing weight as 0.0. On dataset FB15k, the best performing
parameters are as follows: $k$=200, $n_{c}$=64, $d_{g}$=256, $p$=0.2, batch
size=5,000, number of epochs=3,000 and label smoothing weight=0.0; On dataset
FB15k-237, the best performing parameters are as follows: $k$=200, $n_{c}$=64,
$d_{g}$=256, $p$=0.2, batch size=2,000, number of epochs=2,000 and label
smoothing weight=0.1. On dataset DDI, the best performing parameters are as
follows: $k$=200, $n_{c}$=64, $d_{g}$=256, $p$=0.2, batch size=300, number of
epochs=1,000 and label smoothing weight=0.0. On dataset YAGO3-10, the best
performing parameters are as follows: $k$=200, $n_{c}$=64, $d_{g}$=256,
$p$=0.2, batch size=30,000, number of epochs=2,000 and label smoothing
weight=0.0. On dataset FB14k, the best performing parameters are as follows:
$k$=100, $n_{c}$=64, $d_{g}$=256, $p$=0.2, batch size=1,000, number of
epochs=600 and label smoothing weight=0.0. On dataset DDI, the best performing
parameters are as follows: $k$=200, $n_{c}$=64, $d_{g}$=256, $p$=0.2, batch
size=100, number of epochs=1,000 and label smoothing weight=0.0. In order to
avoid overfitting, we regularized the embedding of relations and entities to
have unit $\ell_{2}$ norm. We will publish the source code upon the acceptance
of this paper.

###  A.3 Comparison between $\mathop{\mathtt{CDC}}\limits$ and ConvE on
experimental results

Tabel 10 presents the comparison between $\mathop{\mathtt{CDC}}\limits$ and
ConvE. The results of ConvE are cited from its paper. On almost all the
datasets, without data augmentation, $\mathop{\mathtt{CDC}}\limits$ can still
achieve similar or even better performance than ConvE. It demonstrates that
the CNN architecture used in $\mathop{\mathtt{CDC}}\limits$ is very
competitive or even better compared to the CNN architecture used in ConvE.

Table 10: Comparison between $\mathop{\mathtt{CDC}}\limits$ and ConvE

method | WN18 |  | FB15k |  | YAGO3-10 |  | FB15k-237
---|---|---|---|---|---|---|---
$\mathop{\mathtt{{MR}}}\limits$ | $\mathop{\mathtt{H@10}}\limits$ |  |  $\mathop{\mathtt{{MR}}}\limits$ | $\mathop{\mathtt{H@10}}\limits$ |  |  $\mathop{\mathtt{{MR}}}\limits$ | $\mathop{\mathtt{H@10}}\limits$ |  |  $\mathop{\mathtt{{MR}}}\limits$ | $\mathop{\mathtt{H@10}}\limits$
ConvE | 374 | 95.6 |  | 51 | 83.1 |  | 1,676 | 62.0 |  | 244 | 50.1
$\mathop{\mathtt{CDC}}\limits$ | 380 | 94.9 |  | 73 | 83.3 |  | 2,061 | 62.9 |  | 267 | 46.2

  * •

$\mathop{\mathtt{H@10}}\limits$ values are in percent.