📄 Knowledge Graph Embedding via Dynamic Mapping Matrix

Summary

Knowledge graphs such as WordNet and Freebase are far from complete, so models that predict missing triplets (h, r, t) are needed. Translation-based embedding methods like TransE, TransH and TransR/CTransR treat a relation as a shift from the head entity to the tail entity. TransR/CTransR, the previous best, gives each relation a single mapping matrix that all of its entities share. This ignores how varied the entities linked by one relation can be, and it adds many parameters and costly matrix-vector products. The authors propose TransD, which gives every entity and relation two vectors. One encodes its meaning, and the other is a projection vector. The mapping matrix for each entity-relation pair is then built dynamically from the two projection vectors plus an identity matrix. TransD therefore accounts for diversity in both entities and relations while staying close to TransE and TransH in cost. On triplet classification and link prediction, it beats TransE, TransH and TransR/CTransR. This makes fine-grained projection practical for large-scale graphs.

Key points

• Mapping matrices in TransD are built as M_rh = r_p h_pᵀ + I^{m×n} (and the same way for tails), so each entity-relation pair gets its own projection without any matrix-vector multiplication.
• TransD needs O(2N_e m + 2N_r n) parameters and O(2nN_t) operations per epoch, compared with O(2mnN_t) operations for TransR/CTransR.
• On FB15k link prediction broken down by relation type, TransD improves on prior state-of-the-art results by 9.0% for N-to-1 relations (predicting the head) and 14.7% for 1-to-N relations (predicting the tail).
• An analysis of projection vectors on WN18 (40,943 entities) and FB15k (1,345 relations) shows that objects of the same category end up with similar projection vectors, measured by cosine similarity.
• The datasets include WN18, FB15k and FB13, and the baselines include RESCAL, SE, SME, LFM, SLM and NTN. As future work, the authors propose extracting new facts from plain text.