DAPath: distance-aware knowledge graph reasoning based on deep reinforcement learning. (English) Zbl 1521.68217
Summary: Knowledge graph reasoning aims to find reasoning paths for relations over incomplete knowledge graphs (KG). Prior works may not take into account that the rewards for each position (vertex in the graph) may be different. We propose the distance-aware reward in the reinforcement learning framework to assign different rewards for different positions. We observe that KG embeddings are learned from independent triples and therefore cannot fully cover the information described in the local neighborhood. To this effect, we integrate a graph self-attention (GSA) mechanism to capture more comprehensive entity information from the neighboring entities and relations. To let the model remember the path, we incorporate the GSA mechanism with GRU to consider the memory of relations in the path. Our approach can train the agent in one-pass, thus eliminating the pre-training or fine-tuning process, which significantly reduces the problem complexity. Experimental results demonstrate the effectiveness of our method. We found that our model can mine more balanced paths for each relation.
References:
| [1] | Balazevic, I., Allen, C., & Hospedales, T. M. (2019). Tucker: Tensor factorization for knowledge graph completion. In Proceedings of EMNLP-IJCNLP. |
| [2] | Bansal, T.; Juan, D.-C.; Ravi, S.; McCallum, A., A2N: Attending to neighbors for knowledge graph inference, (Proceedings of ACL (2019), Association for Computational Linguistics), 4387-4392 |
| [3] | Bordes, A., Usunier, N., García-Durán, A., Weston, J., & Yakhnenko, O. (2013). Translating embeddings for modeling multi-relational data. In C.J.C. Burges, and L. Bottou, and Z. Ghahramani, and K.Q. Weinberger (Eds.). Proceedings of NIPS, pp. (2787-2795). |
| [4] | Carlson, A.; Betteridge, J.; Kisiel, B.; Settles, B.; Hruschka, Estevam R.; Mitchell, T. M., Toward an architecture for never-ending language learning, (Fox, M.; Poole, D., Proceedings of AAAI (2010), AAAI Press) |
| [5] | Chen, W.; Xiong, W.; Yan, X.; Wang, W. Y., Variational knowledge graph reasoning, (Walker, M. A.; Ji, H.; Stent, A., Proceedings of NAACL-HLT (2018), Association for Computational Linguistics), 1823-1832 |
| [6] | Chung, J., Gülçehre, Ç., Cho, K., & Bengio, Y. (0000). Empirical evaluation of gated recurrent neural networks on sequence modeling, CoRR abs/1412.3555. |
| [7] | Das, R., Dhuliawala, S., Zaheer, M., Vilnis, L., Durugkar, I., & Krishnamurthy, A. et al. (2018). Go for a walk and arrive at the answer: Reasoning over paths in knowledge bases using reinforcement learning. In Proceedings of ICLR. |
| [8] | Das, R.; Neelakantan, A.; Belanger, D.; McCallum, A., Chains of reasoning over entities, relations, and text using recurrent neural networks, (Lapata, M.; Blunsom, P.; Koller, A., Proceedings of EACL (2017), Association for Computational Linguistics), 132-141 |
| [9] | Dettmers, T.; Minervini, P.; Stenetorp, P.; Riedel, S., Convolutional 2d knowledge graph embeddings, (McIlraith, S. A.; Weinberger, K. Q., Proceedings of AAAI (2018), AAAI Press), 1811-1818 |
| [10] | Elfwing, S.; Uchibe, E.; Doya, K., Sigmoid-weighted linear units for neural network function approximation in reinforcement learning, Neural Networks, 107, 3-11 (2018) |
| [11] | Graves, A.; Schmidhuber, J., Framewise phoneme classification with bidirectional lstm and other neural network architectures, Neural Networks, 18, 5-6, 602-610 (2005) |
| [12] | Gullapalli, V., A stochastic reinforcement learning algorithm for learning real-valued functions, Neural Networks, 3, 6, 671-692 (1990) |
| [13] | Guo, L., Sun, Z., & Hu, W. (2019). Learning to exploit long-term relational dependencies in knowledge graphs. In K. Chaudhuri, and R. Salakhutdinov (Eds.), Proceedings of ICML, Vol. 97 of Proceedings of Machine Learning Research, PMLR (pp. 2505-2514). |
| [14] | Haruno, M.; Kawato, M., Heterarchical reinforcement-learning model for integration of multiple cortico-striatal loops: fmri examination in stimulus-action-reward association learning, Neural Networks, 19, 8, 1242-1254 (2006) · Zbl 1100.92013 |
| [15] | He, S.; Liu, K.; Ji, G.; Zhao, J., Learning to represent knowledge graphs with gaussian embedding, (Bailey, J.; Moffat, A.; Aggarwal, C. C.; de Rijke, M.; Kumar, R.; Murdock, V.; Sellis, T. K.; Yu, J. X., Proceedings of CIKM (2015), ACM: ACM Melbourne, VIC, Australia), 623-632 |
| [16] | Iwashita, A. S.; Papa, J. P.; Falcão, A. X.; de Alencar Lotufo, R.; de Araujo Oliveira, V. M.; de Albuquerque, V. H.C., Speeding up optimum-path forest training by path-cost propagation, (Proceedings ICPR (2012), IEEE Computer Society), 1233-1236 |
| [17] | Jagvaral, B.; Lee, W.-K.; Roh, J.-S.; Kim, M.-S.; Park, Y.-T., Path-based reasoning approach for knowledge graph completion using cnn-bilstm with attention mechanism, Expert Systems with Applications, 142, Article 112960 pp. (2020) |
| [18] | Ji, G., He, S., Xu, L., Liu, K., & Zhao, J. (2015). Knowledge graph embedding via dynamic mapping matrix. In Proceedings of ACL (pp. 687-696). |
| [19] | Ji, G.; Liu, K.; He, S.; Zhao, J., Knowledge graph completion with adaptive sparse transfer matrix, (Schuurmans, D.; Wellman, M. P., Proceedings of AAAI (2016), AAAI Press: AAAI Press Phoenix, Arizona, USA), 985-991 |
| [20] | Jiang, X.; Wang, Q.; Wang, B., Adaptive convolution for multi-relational learning, (Burstein, J.; Doran, C.; Solorio, T., Proceedings of NAACL-HLT (2019), Association for Computational Linguistics), 978-987 |
| [21] | Johnson, A.; Redish, A. D., Hippocampal replay contributes to within session learning in a temporal difference reinforcement learning model, Neural Networks, 18, 9, 1163-1171 (2005) · Zbl 1085.92006 |
| [22] | Karevan, Z.; Suykens, J. A., Transductive lstm for time-series prediction: An application to weather forecasting, Neural Networks, 125, 1-9 (2020) |
| [23] | Kazemi, S. M., & Poole, D. (2018). Simple embedding for link prediction in knowledge graphs. In S. Bengio, and H.M. Wallach, and H. Larochelle, and K. Grauman, and N. Cesa-Bianchi, and R. Garnett (Eds.), Proceedings of NIPS (pp. 4289-4300). |
| [24] | Kipf, T. N., & Welling, M. (0000). Semi-supervised classification with graph convolutional networks, arXiv preprint arXiv:1609.02907. |
| [25] | Lao, N.; Cohen, W. W., Relational retrieval using a combination of path-constrained random walks, Machine Learning, 81, 1, 53-67 (2010) · Zbl 1470.68130 |
| [26] | Lao, N.; Mitchell, T. M.; Cohen, W. W., Random walk inference and learning in a large scale knowledge base, (Proceedings of EMNLP (2011), ACL), 529-539 |
| [27] | Laurent, P. A., The emergence of saliency and novelty responses from reinforcement learning principles, Neural Networks, 21, 10, 1493-1499 (2008) · Zbl 1254.92026 |
| [28] | Lin, Y., Liu, Z., Sun, M., Liu, Y., & Zhu, X. (2015). Learning entity and relation embeddings for knowledge graph completion. In B. Bonet, and S. Koenig (Eds.), Proceedings of AAAI (pp. 2181-2187). |
| [29] | Lin, X. V.; Socher, R.; Xiong, C., Multi-hop knowledge graph reasoning with reward shaping, (Proceedings of EMNLP (2018), Association for Computational Linguistics), 3243-3253 |
| [30] | Liu, H., Wu, Y., & Yang, Y. (2017). Analogical inference for multi-relational embeddings. In D. Precup, and Y.W. Teh (Eds.), Proceedings of ICML, Vol. 70 of Proceedings of Machine Learning Research, PMLR (pp. 2168-2178). |
| [31] | Luo, B.; Wu, H.-N.; Huang, T.; Liu, D., Reinforcement learning solution for hjb equation arising in constrained optimal control problem, Neural Networks, 71, 150-158 (2015) · Zbl 1397.49044 |
| [32] | Lv, X.; Gu, Y.; Han, X.; Hou, L.; Li, J.; Liu, Z., Adapting meta knowledge graph information for multi-hop reasoning over few-shot relations, (Proceedings of EMNLP-IJCNLP (2019), Association for Computational Linguistics), 3374-3379 |
| [33] | Nathani, D.; Chauhan, J.; Sharma, C.; Kaul, M., Learning attention-based embeddings for relation prediction in knowledge graphs, (Korhonen, A.; Traum, D. R.; Màrquez, L., Proceedings of ACL (2019), Association for Computational Linguistics), 4710-4723 |
| [34] | Neelakantan, A.; Roth, B.; McCallum, A., Compositional vector space models for knowledge base completion, (Proceedings of ACL (2015), The Association for Computer Linguistics: The Association for Computer Linguistics Beijing, China), 156-166 |
| [35] | Nguyen, D. Q.; Nguyen, T. D.; Nguyen, D. Q.; Phung, D. Q., A novel embedding model for knowledge base completion based on convolutional neural network, (Walker, M. A.; Ji, H.; Stent, A., Proceedings of NAACL-HLT (2018), Association for Computational Linguistics), 327-333 |
| [36] | Nguyen, D. Q.; Vu, T.; Nguyen, T. D.; Nguyen, D. Q.; Phung, D. Q., A capsule network-based embedding model for knowledge graph completion and search personalization, (Burstein, J.; Doran, C.; Solorio, T., Proceedings of NAACL-HLT (2019), Association for Computational Linguistics), 2180-2189 |
| [37] | Nickel, M.; Rosasco, L.; Poggio, T. A., Holographic embeddings of knowledge graphs, (Schuurmans, D.; Wellman, M. P., Proceedings of AAAI (2016), AAAI Press), 1955-1961 |
| [38] | Rossi, A., Firmani, D., Matinata, A., Merialdo, P., & Barbosa, D. (0000). Knowledge graph embedding for link prediction: A comparative analysis, arXiv preprint arXiv:2002.00819. |
| [39] | Schlichtkrull, M. S., Kipf, T. N., Bloem, P., van den Berg, R., Titov, I., & Welling, M. (2018). Modeling relational data with graph convolutional networks. In Proceedings of ESWC 2018, (pp. 593-607). |
| [40] | Schweighofer, N.; Doya, K., Meta-learning in reinforcement learning, Neural Networks, 16, 1, 5-9 (2003) |
| [41] | Shen, Y., Chen, J., Huang, P., Guo, Y., & Gao, J. (2018). M-walk: Learning to walk over graphs using monte carlo tree search. In Proceedings of NIPS (pp. 6787-6798). |
| [42] | Sutton, R. S.; Barto, A. G., Reinforcement Learning: An Introduction (2018), MIT press · Zbl 1407.68009 |
| [43] | Sutton, R. S.; McAllester, D. A.; Singh, S. P.; Mansour, Y., Policy gradient methods for reinforcement learning with function approximation, (Solla, S. A.; Leen, T. K.; Müller, K., Proceedings of NIPS (1999), The MIT Press), 1057-1063 |
| [44] | Toutanova, K.; Chen, D.; Pantel, P.; Poon, H.; Choudhury, P.; Gamon, M., Representing text for joint embedding of text and knowledge bases, (Màrquez, L.; Callison-Burch, C.; Su, J.; Pighin, D.; Marton, Y., Proceedings of EMNLP (2015), The Association for Computational Linguistics), 1499-1509 |
| [45] | Trouillon, T.; Welbl, J.; Riedel, S.; Gaussier, É.; Bouchard, G., Complex embeddings for simple link prediction, (Balcan, M.; Weinberger, K. Q., Proceedings of ICML, Vol. 48 of JMLR Workshop and Conference Proceedings (2016), JMLR.org), 2071-2080 |
| [46] | Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., & Bengio, Y. (0000). Graph attention networks. In International conference on learning representations. |
| [47] | Wang, W. Y.; Cohen, W. W., Learning first-order logic embeddings via matrix factorization, (Kambhampati, S., Proceedings of IJCAI (2016), IJCAI/AAAI Press), 2132-2138 |
| [48] | Wang, R.; Li, B.; Hu, S.; Du, W.; Zhang, M., Knowledge graph embedding via graph attenuated attention networks, IEEE Access, 8, 5212-5224 (2020) |
| [49] | Wang, H.; Li, S.; Pan, R.; Mao, M., Incorporating graph attention mechanism into knowledge graph reasoning based on deep reinforcement learning, (Proceedings of EMNLP-IJCNLP (2019), Association for Computational Linguistics), 2623-2631 |
| [50] | Wang, Q.; Mao, Z.; Wang, B.; Guo, L., Knowledge graph embedding: A survey of approaches and applications, IEEE Transactions on Knowledge and Data Engineering, 29, 12, 2724-2743 (2017) |
| [51] | Wang, D., Tiwari, P., Garg, S., Zhu, H., & Bruza, P. (0000). Structural block driven enhanced convolutional neural representation for relation extraction. Applied Soft Computing 86. |
| [52] | Wang, Z., Zhang, J., Feng, J., & Chen, Z. (2014) Knowledge graph embedding by translating on hyperplanes. In C.E. Brodley, and P. Stone (Eds.), Proceedings of AAAI (pp. 1112-1119). |
| [53] | Williams, R. J., Simple statistical gradient-following algorithms for connectionist reinforcement learning, Machine Learning, 8, 229-256 (1992) · Zbl 0772.68076 |
| [54] | Xiao, H., Huang, M., Hao, Y., & Zhu, X. (0000). Transa: An adaptive approach for knowledge graph embedding, CoRR abs/1509.05490. arXiv:1509.05490. URL http://arxiv.org/abs/1509.05490. |
| [55] | Xiao, H.; Huang, M.; Zhu, X., Transg : A generative model for knowledge graph embedding, (Proceedings of ACL (2016), The Association for Computer Linguistics: The Association for Computer Linguistics Berlin, Germany) |
| [56] | Xiong, W.; Hoang, T.; Wang, W. Y., Deeppath: A reinforcement learning method for knowledge graph reasoning, (Proceedings of EMNLP (2017), Association for Computational Linguistics), 564-573 |
| [57] | Yang, F., Yang, Z., & Cohen, W. W. (2017). Differentiable learning of logical rules for knowledge base reasoning. In Proceedings of NIPS (pp. 2319-2328). |
| [58] | Yang, B., Yih, W., He, X., Gao, J., & Deng, L. (2015). Embedding entities and relations for learning and inference in knowledge bases. In Y. Bengio, and Y. LeCun (Eds.), Proceedings of ICLR 2015. |
| [59] | Zhang, Y.; Yao, Q.; Dai, W.; Chen, L., Autosf: Searching scoring functions for knowledge graph embedding, (36th IEEE International Conference on Data Engineering, ICDE 2020, Dallas (2020), IEEE: IEEE TX, USA), 433-444 |
| [60] | Zheng, S.; Wang, F.; Bao, H.; Hao, Y.; Zhou, P.; Xu, B., Joint extraction of entities and relations based on a novel tagging scheme, (Proceedings of ACL (2017), Association for Computational Linguistics), 1227-1236 |
| [61] | Zhu, Y.; Liu, H.; Wu, Z.; Song, Y.; Zhang, T., Representation learning with ordered relation paths for knowledge graph completion, (Proceedings of EMNLP-IJCNLP (2019), Association for Computational Linguistics), 2662-2671 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
