# Learning Heterogeneous Knowledge Base Embeddings for Explainable Recommendation
## 4 Collaborative Filtering on Knowledge Graphs
### Optimization Algorithm  
For model optimization, we learn the representations of entities and relations by maximizing the likelihood of all observed relation triplets. Let \(S\) be the set of observed triplets \((e_{h},e_{t},r)\) in the training data, then we can compute the likelihood of \(S\) defined as  
\[\mathcal{L}(S)=\log\prod_{(e_{h},e_{t},r)\in S}\hskip-14.226378 ptP(e_{t}|trans( e_{h},r)) \tag{3}\]  
where \(P(e_{t}|trans(e_{h},r))\) is the posterior probability of \(e_{t}\) computed with Equation (2). The computation cost of \(\mathcal{L}(S)\), however, is prohibitive in practice because of the softmax function. For efficient training, we adopt a negative sampling strategy to approximate \(P(e_{t}|trans(e_{h},r))\)[PERSON] et al. (2016). Specifically, for each observed relation triplet \((e_{h},e_{t},r)\), we randomly sample a set of \"negative\" entities with the same type of \(e_{t}\). Then the log likelihood of \((e_{h},e_{t},r)\) is approximated as  
\[\log P(e_{t}|trans(e_{h},r))\approx\log\sigma(\mathbf{e_{t}}\cdot trans(e_{h},r))+ k\cdot\mathbb{E}_{e_{t}^{\prime}\sim P_{t}}[\log\sigma(-\mathbf{e_{t}^{\prime}} \cdot trans(e_{h},r))] \tag{4}\]  
where \(k\) is the number of negative samples, \(P_{t}\) is a predefined noisy distribution over entities with the type of \(e_{t}\), and \(\sigma(x)\) is a sigmoid function as \(\sigma(x)=\frac{1}{1+e^{-x}}\). Therefore, \(\mathcal{L}(S)\) can be reformulated as the sum of the log-likelihood of \((e_{h},e_{t},r)\in S\) as  
\[\mathcal{L}(S)=\hskip-14.226378 pt\sum_{(e_{h},e_{t},r)\in S}\hskip-14.226378 pt \log\sigma(\mathbf{e_{t}}\cdot trans(e_{h},r))+k\cdot\mathbb{E}_{e_{t}^{\prime}\sim P _{t}}[\log\sigma(-\mathbf{e_{t}^{\prime}}\cdot trans(e_{h},r))] \tag{5}\]  
We also tested the \(\ell_{2}\)-norm loss function used in TransE model and it does not provide any improvement compared to our inner product-based model with log-likelihood loss, and it is also difficulty for \(\ell_{2}\)-norm loss to generate expansions, as a result, we adopt our loss function for embedding, recommendation, and explanation in this work. To better illustrate the relationship between our model and a traditional CF method based on matrix factorization, we conduct the following analysis. Inspired by [PERSON] et al. (2016), we derive the local objective for the maximization of Equation (5) on a specific relation triplet \((e_{h},e_{t},r)\):  
\[\ell(e_{h},e_{t},r)=\#(e_{h},e_{t},r)\cdot\log\sigma(\mathbf{e_{t}}\cdot trans(e_ {h},r))+k\cdot\#(e_{h},r)\cdot P_{t}(e_{t})\cdot\log\sigma(-\mathbf{e_{t}}\cdot trans (e_{h},r)) \tag{6}\]where \(\#(e_{h},e_{t},r)\) and \(\#(e_{h},r)\) are the frequency of \((e_{h},e_{t},r)\) and \((e_{h},r)\) in the training data. If we further compute the partial derivative of \(\ell(e_{h},e_{t},r)\) with respect to \(x=\mathbf{e_{t}}\cdot trans(e_{h},r)\), we have  
\[\frac{\partial\ell(e_{h},e_{t},r)}{\partial x}=\#(e_{h},e_{t},r) \cdot\sigma(-x)-k\cdot\#(e_{h},r)\cdot P_{t}(e_{t})\cdot\sigma(x) \tag{7}\]  
When the training process has converged, the partial derivative of \(\ell(e_{h},e_{t},r)\) should be 0, and then we have  
\[x=\mathbf{e_{t}}\cdot trans(e_{h},r)=\log(\frac{\#(e_{h},e_{t},r)}{ \#(e_{h},r)}\cdot\frac{1}{P_{t}(e_{t})})-\log k \tag{8}\]  
As we can see, the left-hand side is the product of the latent vectors for \(e_{t}\) and \(trans(e_{h},r)\); and the right-hand side of Equation (8) is a shifted version of the pointwise mutual information between \(e_{t}\) and \((e_{h},r)\). Therefore, maximizing the log likelihood of observed triplet set \(S\) with negative sampling is actually factorizing the matrix of mutual information between the head-tail entity pairs \((e_{h},e_{t})\) of relation \(r\). From this perspective, our model is a variation of factorization methods that can jointly factorize multiple relation matrix on a product knowledge graph. As shown in Equation (8), the final objective of the proposed model is controlled by the noisy distribution \(P_{t}\).