Structure Aware Negative Sampling in Knowledge Graphs (2020)

Abstract: Learning low-dimensional representations for entities and relations in knowledge graphs using contrastive estimation represents a scalable and effective method for inferring connectivity patterns. A crucial aspect of contrastive learning approaches is the choice of corruption distribution 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 uninformative negatives or sophisticated adversarial distributions with challenging optimization schemes, they do not explicitly incorporate known graph structure resulting in suboptimal negatives. In this paper, we propose Structure Aware Negative Sampling (SANS), an inexpensive negative sampling strategy that utilizes the rich graph structure by selecting negative samples from a node’s k -hop neighborhood. Empirically, we demonstrate that SANS finds semantically meaningful negatives and is competitive with SOTA approaches while requires no additional parameters nor difficult adversarial optimization.

## introduction knowledge graphs (kgs) are repositories of information organized as factual triples (h, r, t), where head and tail entities are connected via a particular relation (r). indeed, kgs have seen wide application in a variety of domains such as question answering @xcite @xcite and machine reading @xcite to name a few and have a rich history within the natural language processing (nlp) community @xcite @xcite . while * equal contribution, names ordered alphabetically. in recent years, there has been a surge of methods employing graph embedding techniques that encode kgs into a lower-dimensional vector space facilitating easier data manipulation @xcite while being an attractive framework for handling data sparsity and incompleteness @xcite . to learn such embeddings, contrastive learning has emerged as the de facto gold standard. indeed, contrastive learning approaches enjoy significant computational benefits over methods that require computing an exact softmax over a large candidate set, such as over all possible tail entities given a head and relation. another important consideration is modeling needs, as certain assumptions are best expressed as some score or energy in margin-based or un-normalized probability models @xcite . for example, modeling entity relations as translations or rotations in a vector space naturally leads to a distance-based score to be minimized for observed entity-relation-entity triplets @xcite . leveraging contrastive estimation to train kg embedding models involves optimizing the model by pushing up the energy with respect to observed positive triplets while simultaneously pushing down energy on negative triplets. consequently, the choice of negative sampling distribution plays a crucial role in shaping the energy landscape as simple random sampling-e.g. noise contrastive estimation (nce) (gutmann and hyvärinen, 2010)produces negatives that are easily classified and provide little information alongside in the form of a gradient signal. this is easily remedied if the corruption process selects a hard negative example through more complex negative sampling distribution, such as adversarial samplers @xcite @xcite . however, adversarial negative sampling methods are computationally expensive, while more tractable approaches-e.g. cache-based methods (zhang et al., 2019)-are not tailored to the kg setting as they fail to incorporate known graph structure as part of the sampling process. this raises the important question of whether we can obtain a computationally inexpensive negative sampling strategy while benefiting from the rich graph structure of kgs. present work. in this work, we introduce structure aware negative sampling (sans), an algorithm that utilizes the graph structure of a kg to find hard negative examples. specifically, sans constructs negative samples using a subset of entities restricted to either the head or tail entity's k-hop neighborhood. we hypothesize that entities that are within each other's neighborhood but share no direct relation have higher chances of being related to one another and thus are good candidates for negative sampling. we also experiment with a dynamic sampling scheme based on random walks to approximate a node's local neighborhood. empirically, we find that negative sampling using sans consistently leads to improvements upon uniform sampling and sophisticated generative adversarial network (goodfellow et al., 2014) (gan) based approaches at a fraction of the computational cost, and is competitive with other sota approaches with no added parameters. to address the issue of easy negatives, @xcite propose self-adversarial negative sampling, which weighs each sampled negative according to its probability under the embedding model. alternatively, the authors in @xcite and @xcite try creating high-quality negative samples by exploiting gans, which, while effective, are expensive to train and require black-box gradient estimation techniques. another elegant approach that uses fewer parameters and is easier to train compared to gan-based methods is nscaching @xcite , which involves using a cache of high-quality negative triplets-i.e. those with high scores. ## structure aware negative sampling given an observed positive triplet (h, r, t), a negative sample can be constructed by corrupting either the head or tail entity to form a new triplet-i.e. (h , r, t )-where either h , @xmath0, where e is the set of all entities in the kg. additionally, we assume that the graph embedding models are trained using a loss function of the following form: in this paper, we seek to explicitly use the rich graph structure surrounding a particular node when generating negative triplets. we motivate our approach based on the observation that prior work in learning word embeddings @xcite , where negative sampling has historically developed, lacked the richness of graph structure that is immediately accessible in the kg setting. consequently, we hypothesize that enriching the negative sampling process with structural information can yield harder negative examples, crucial to learning effective embeddings. fig. 1 highlights our approach, which requires the construction of the k-hop neighborhood (k) for each node at its first step, for @xmath1, where k is an integer, representing the neighborhood radius, a is the kg's adjacency matrix, and s + is the element-wise sign function set to 1 if a path exists and 0 otherwise. to construct negatives triplets, we may now simply sample from the nonzero cell of k, which represents a subset of all entities for each node in the kg-i.e. k ⊂ 1 e×e . intuitively, sans exploits the locality of an entity's neighborhood, where negative samples are defined as entities that are not directly linked under a relation r but can be accessed through a path of at most length k. we argue that such local negatives are harder to distinguish and lead to higher scores as evaluated by the embedding model. one important technical detail in constructing k is the existence of multiple relation types, which requires an additional dimension to represent the graph connectivity as adjacency and k-hop tensors. ## experiments we investigate the application of sans-based negatives to train kg embedding models based on the transe, distmult, and rotate models for the task of kg completion * . we evaluate our proposed approach on standard benchmarks, consisting of fb15k-237 @xcite , wn18 and wn18rr @xcite . from our experiments we seek to answer the following questions: in our experiments, we rely on three representative baselines, namely uniform negative sampling @xcite , kbgan @xcite , and nscaching @xcite . we also compare with the current sota approach in self-adversarial negative sampling (sun et al., 2019), and we test whether local graph structure can also be leveraged in this setting. ## conclusion and future directions in this work, we introduced sans, a novel negative sampling strategy, which directly leverages information about k-hop neighborhoods to select negative examples. our work sheds light on the need and importance of incorporating graph structure when designing negative samplers for kgs, and for which sans can be seen as a cheap yet powerful baseline that requires no additional parameters or difficult optimization. empirically, we find that sans-based negatives have comparable performance with sota approaches and even outperform previous sophisticated gan-based approaches. ian goodfellow, jean pouget-abadie, mehdi mirza, bing xu, david warde-farley, sherjil ozair, aaron courville, and yoshua bengio. 2014. generative adversarial nets. in advances in neural information processing systems, pages 2672-2680. michael gutmann and aapo hyvärinen. 2010. noisecontrastive estimation: a new estimation principle for unnormalized statistical models. in proceedings of the thirteenth international conference on artificial intelligence and statistics, pages 297-304. yanchao hao, yuanzhe zhang, kang liu, shizhu he, zhanyi liu, hua wu, and jun zhao. 2017. an endto-end model for question answering over knowledge base with cross-attention combining global knowledge. in proceedings of the 55th annual meeting of the association for computational linguistics (volume 1: long papers), pages 221-231. tomas mikolov, ilya sutskever, kai chen, greg s corrado, and jeff dean. 2013. distributed representations of words and phrases and their compositionality. in advances in neural information processing systems, pages 3111-3119. george a miller. 1995. wordnet: a lexical database for english. communications of the acm, 38(11):39-41. dan i moldovan and vasile rus. 2001. logic form transformation of wordnet and its applicability to question answering. in proceedings of the 39th annual meeting on association for computational linguistics, pages 402-409. association for computational linguistics. bryan perozzi, rami al-rfou, and steven skiena. 2014. deepwalk: online learning of social representations. in proceedings of the 20th acm sigkdd international conference on knowledge discovery and data mining, pages 701-710. matthew e peters, mark neumann, robert logan, roy schwartz, vidur joshi, sameer singh, and noah a smith. 2019. knowledge enhanced contextual word representations. in proceedings of the 2019 conference on empirical methods in natural language processing and the 9th international joint conference on natural language processing (emnlp-ijcnlp), pages 43-54. noah a smith and jason eisner. 2005. contrastive estimation: training log-linear models on unlabeled data. in proceedings of the 43rd annual meeting on association for computational linguistics, pages 354-362. association for computational linguistics. zhiqing sun, zhi-hong deng, jian-yun nie, and jian tang. 2019. rotate: knowledge graph embedding by relational rotation in complex space. in international conference on learning representations. peifeng wang, shuangyin li, and rong pan. 2018. incorporating gan for negative sampling in knowledge representation learning. in thirty-second aaai conference on artificial intelligence. dirk weissenborn, pasquale minervini, isabelle augenstein, johannes welbl, tim rocktäschel, matko bosnjak, jeff mitchell, thomas demeester, tim dettmers, pontus stenetorp, et al. 2018. jack the reader-a machine reading framework. in proceedings of acl 2018, system demonstrations, pages 25-30. bishan yang and tom mitchell. 2017. leveraging knowledge bases in lstms for improving machine reading. in proceedings of the 55th annual meeting of the association for computational linguistics (volume 1: long papers), pages 1436-1446. xuchen yao and benjamin van durme. 2014. information extraction over structured data: question answering with freebase. in proceedings of the 52nd annual meeting of the association for computational linguistics (volume 1: long papers), pages 956-966. mo yu and mark dredze. 2014. improving lexical embeddings with semantic knowledge. in proceedings of the 52nd annual meeting of the association for computational linguistics (volume 2: short papers), pages 545-550. yongqi zhang, quanming yao, yingxia shao, and lei chen. 2019. nscaching: simple and efficient negative sampling for knowledge graph embedding. in 2019 ieee 35th international conference on data engineering (icde), pages 614-625. ieee.