Structure Aware Negative Sampling in Knowledge Graphs

Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, pages 6093–6101, November 16–20, 2020. c⃝2020 Association for Computational Linguistics 6093 Structure Aware Negative Sampling in Knowledge Graphs Kian Ahrabian∗,1,3, Aarash Feizi∗,1,3, Yasmin Salehi∗,2, William L. Hamilton1,3,4 and Avishek Joey Bose1,3 1 School of Computer Science, McGill University, Canada 2 Department of Electrical and Computer Engineering, McGill University, Canada 3 Montreal Institute of Learning Algorithms (Mila), Canada 4 Canada CIFAR AI Chair {kian.ahrabian, aarash.feizi, yasmin.salehi } {@mail.mcgill.ca } Abstract Learning low-dimensional representations for entities and relations in knowledge graphs us- ing contrastive estimation represents a scalable and effective method for inferring connectivity patterns. A crucial aspect of contrastive learn- ing approaches is the choice of corruption dis- tribution that generates hard negative samples, which force the embedding model to learn discriminative representations and find critical characteristics of observed data. While earlier methods either employ too simple corruption distributions, i.e. uniform, yielding easy unin- formative negatives or sophisticated adversar- ial distributions with challenging optimization schemes, they do not explicitly incorporate known graph structure resulting in suboptimal negatives. In this paper, we propose Struc- ture Aware Negative Sampling (SANS), an in- expensive negative sampling strategy that uti- lizes the rich graph structure by selecting neg- ative samples from a node’s k-hop neighbor- hood. Empirically, we demonstrate that SANS finds semantically meaningful negatives and is competitive with SOTA approaches while re- quires no additional parameters nor difficult adversarial optimization. 1 Introduction Knowledge Graphs (KGs) are repositories of infor- mation organized as factual triples (h, r, t), where head and tail entities are connected via a particular relation (r). Indeed, KGs have seen wide appli- cation in a variety of domains such as question answering (Yao and Van Durme, 2014; Hao et al., 2017; Moldovan and Rus, 2001) and machine read- ing (Weissenborn et al., 2018; Yang and Mitchell, 2017) to name a few and have a rich history within the natural language processing (NLP) community (Berant et al., 2013; Yu and Dredze, 2014; Col- lobert and Weston, 2008; Peters et al., 2019). While ∗Equal contribution, names ordered alphabetically. often large, real-world KGs such as FreeBase (Bol- lacker et al., 2008) and WordNet (Miller, 1995) are known to be incomplete. Consequently, KG completion via link prediction constitutes a funda- mental research topic ameliorating the practice of important NLP tasks (Sun et al., 2019; Angeli and Manning, 2013). In recent years, there has been a surge of meth- ods employing graph embedding techniques that encode KGs into a lower-dimensional vector space facilitating easier data manipulation (Zhang et al., 2019) while being an attractive framework for han- dling data sparsity and incompleteness (Wang et al., 2018). To learn such embeddings, contrastive learn- ing has emerged as the de facto gold standard. In- deed, contrastive learning approaches enjoy sig- nificant computational benefits over methods that require computing an exact softmax over a large candidate set, such as over all possible tail enti- ties given a head and relation. Another important consideration is modeling needs, as …

Content truncated to 500 words