# Knowledge Graph Completion Based on Entity Descriptions in Hyperbolic Space
## 3 Knowledge Representation Learning Based on Hyperbolic Space
### Algorithm  
In this paper, we give the process of knowledge representation learning for the DMuRP method, as shown in Algorithm 1. DMuRP uses the triple set and entity descriptions as input. First, we obtain hyperbolic embeddings of triples by the MuRP model (line 1). Second, sample a minibatch of size b from the training set (line 3). Third, several negative samples are generated for each correct triple (lines 6-8). Third, calculate the energy function based on Equation (6), and calculate the result of the score function based on Equation (11) (lines 9-10). Finally, calculating the loss, optimize the loss function by Riemannian stochastic gradient descent (line 12, line 14). After many iterations, hyperbolic embeddings of triples and hyperbolic embeddings of entity descriptions with corresponding semantic information are obtained.  
The time complexity of learning DMuRP is O(Num \(\times\) len(train)/batchSize). Num is the number of iterations, batchSize is the sampling size, and len(train) is the size of training set. The time complexity of this algorithm is related to the number of iterations, the sampling size, and the size of training set. When the number of iterations and training sets increases or the number of samples decreases, the time complexity will increase. The space complexity is O((len(Ent) + len(des) + len(Rel)) \(\times\) d). len(Ent) is the size of the entity set, len(des) is the size of the entity descriptions, len(Rel) is the size of the relation set, and d is the embedding dimensions. When the size of the entity set, the size of the entity descriptions, and the size of the relation set increase, the space complexity will increase.  
```
0: Training set \(S=\{(h,r,t)\}\), \(\mathbf{E_{d}}=\mathbf{h_{d}^{E}}\cup\mathbf{t_{d}^{E}}\), \(\alpha_{1}\), \(\alpha_{2}\), \(\alpha_{3}\), \(\alpha_{4}\)// triples set, entity description-based representations, balanced factors. Output: get hyperbolic embeddings: \(\mathbf{h}^{H},\mathbf{r}^{H},\mathbf{t}^{H},\mathbf{h}_{d}^{H},\mathbf{t_{d}^ {H}}\)// hyperbolic embeddings of triples and entity descriptions.
1: get \(\mathbf{h}_{ss}^{H},\mathbf{r}^{H},\mathbf{t_{s}^{H}},\mathbf{b_{h}},\mathbf{b_ {t}}\) by MuRP model // hyperbolic embeddings of triples, \(\mathbf{b_{h}}\) and \(\mathbf{b_{t}}\) are head entity bias and tail entity bias.
2:loop
3:\(S_{batch}\gets Sample(S,b)\)// sample a minibatch of size b.
4:\(T_{batch}\leftarrow\varnothing\)// initialize the set of pairs of triples.
5:for\((h,r,t)\in S_{batch}\)do
6:\(S^{{}^{\prime}}_{(h,r,t)}\leftarrow\) get the set of negative samples of S based on Equation (17).
7:\((h^{\prime},r,t^{\prime})\leftarrow Sample(S^{{}^{\prime}}_{(h,r,t)},1)\)// sample a negative triple.
8:\(T_{batch}\gets T_{batch}\cup\{((h,r,t),(h^{\prime},r,t^{\prime}))\}\)
9:\(E(h,r,t)\leftarrow\alpha_{1}E_{1}(\mathbf{h_{ss}^{H}},\mathbf{r}^{H},\mathbf{t_ {s}^{H}})+\alpha_{2}E_{2}(\mathbf{h_{d}^{E}},\mathbf{r}^{H},\mathbf{t_{s}^{H}} )+\alpha_{3}E_{3}(\mathbf{h_{ss}^{H}},\mathbf{r}^{H},\mathbf{t_{d}^{E}})+\alpha _{4}E_{4}(\mathbf{h_{d}^{E}},\mathbf{r}^{H},\mathbf{t_{d}^{E}})\)// energy function based on Equation (6).
10:\(p\leftarrow-E(h,r,t)+\mathbf{b_{h}}+\mathbf{b_{t}}\)// score function based on Equation (11).
11:\(y\leftarrow\) when \((h,r,t)\) is positive sample, \(y=1\), otherwise, \(y=0\).
12:\(\mathcal{L}(y,p)\leftarrow-\frac{1}{n}\sum_{i=1}^{n}(y_{i}log(p_{i})+(1-y_{i}) log(1-p_{i}))\)// loss function based on Equation Equation Equation (16). \(n\) is the number of training samples.
13:endfor
14: update embeddings w.r.t. \(\sum\limits_{((h,r,t),(h^{\prime},r,t^{\prime}))\in T_{batch}}RSGD(\mathcal{L }(y,p))\)// Riemannian stochastic gradient descent.
15:endloop
```  
**Algorithm 1** Learning DMuRP [4]