Don’t Mess with Mister-in-Between: Improved Negative Search for Knowledge Graph Completion (2023)

Abstract: The best methods for knowledge graph completion use a ‘dual-encoding’ framework, a form of neural model with a bottleneck that facilitates fast approximate search over a vast collection of candidates. These approaches are trained using contrastive learning to differentiate between known positive examples and sampled negative instances. The mechanism for sampling negatives to date has been very simple, driven by pragmatic engineering considerations (e.g., using mismatched instances from the same batch). We propose several novel means of finding more informative negatives, based on searching for candidates with high lexical overlaps, from the dual-encoder model and according to knowledge graph structures. Experimental results on four benchmarks show that our best single model improves consistently over previous methods and obtains new state-of-the-art performance, including the challenging large-scale Wikidata5M dataset. Combing different kinds of strategies through model ensembling results in a further performance boost.

## introduction a knowledge graph (kg) is a structured form of human knowledge consisting of entities, facts, relationships between any pair of entities, and semantic descriptions of entities. as important structures that store millions of data records that represent a part of human knowledge, kgs have been proven to bring substantial benefits to a wide range of applications, including commonsense question answering @xcite and reasoning @xcite . knowledge graph completion (kgc) supports the automatic construction or completion of a kg by finding the missing entity or link in incomplete triples. graph embedding and textual embedding methods are two mainstream techniques for kgc problems. the former typically map entities and relations into fixed dense vectors and maximises the probability of valid triples using specially-designed scoring functions @xcite ; while the latter additionally uses available textual descriptions associated with entities to gather more information @xcite . surprisingly, textual embedding methods lag behind graph embedding methods, perhaps due to their extra computational overheads in encoding textual inputs and, thus, inefficiency in incorporating a sufficient number of negatives (i.e., incorrect kg triples) to learn discriminative kg embeddings. recently, @xcite found that the key to making textual embedding methods outperform their graph embedding counterparts is to adopt a dual-encoder structure and train using contrastive learning to differentiate between positive training instances and randomly sampled negative instances @xcite . although their technique outperformed various graph embedding methods, achieving a new state-of-the-art, their means of negative sampling is not optimal: this in-batch negative method has been shown to be inefficient in training dual encoders @xcite . instead, as they are highly similar to positives in terms of topics and lexicons, the use of so-called 'hard' negatives have been shown to result in better models in information retrieval @xcite through providing a more informative training signal and faster convergence. however, their effectiveness has not yet been established for kgc. therefore, to fill this gap, in this work, we aim to systematically investigate the effects of various hard negative sampling strategies for dual-encoderbased kgc. specifically, we construct negative samples using three different ways. our approach first evaluates the utility of negatives that share high lexical similarity with the head entity or the correct tail entity in terms of entity names and text descriptions. based on the knowledge graph structures, we alternatively search negatives from the head or tail entity's local neighbourhood, hypothesising that the neighbourhoods of a certain entity that are not directly connected to it are highly related, but not so related to be false negatives (i.e., positives). lastly, we investigate sampling so-called 'hard negatives' from top-k predictions generated by a baseline dual-encoder kgc model, as negatives that receive high scores are believed to be important and difficult to distinguish. in addition, in order to reduce possible false negatives, we also experimented with two variant neural negative sampling strategies according to heuristics. in summary, our contributions are: 1 1. to the best of our knowledge, we are the first to systematically investigate the impacts of different types of negative sampling strategies for dual-encoder-based kgc. 2. we explore how best to combine the benefits of different negative sampling strategies to obtain further performance gains. ## model ensembling since we propose multiple hard negative sampling strategies in §3.2, we train several models, each with different types of hard negatives. it is natural to combine these models to achieve further performance improvements through model ensembling. inspired by @xcite , we explore two methods to ensemble results from multiple models. rank fusion reciprocal rank fusion (rrf) @xcite is a simple yet effective algorithm for merging ranking results from multiple retrievers, and is a prevailing technique in information retrieval. its utility in knowledge graph completion has not yet been evaluated. the technique works by merging the ranking positions from the various models. suppose we have a query (h, r) and each model @xmath0, the final ranking score is: rank p e is the ranking position of an entity e returned by a model p, ranging from [1, |e|]. w p is the weight of a model p, which is tuned based on the performance on the development set. embedding fusion an alternative aggregation method is to compute the weighted sum of ranking scores from different models, i.e., p @xmath1. this can be implemented cheaply using the models' embeddings, which has the benefit of allowing for efficient vector indexing and search. specifically, for each query (h, r), we obtain vectors from each models' encoder, which are then scaled by a model specific weight (tuned manually) and concatenated. each entity @xmath2, is also embedded by each model and the vectors concatenated. this allows the aggregation method to be implemented as a simple dot product: 6 ## analysis 6.1 why the effects vary by dataset next, we analyse why the benefits of different hard negative sampling strategies vary from dataset to dataset. we employ two measurements, namely difficulty and false negative rate, to draw the con-nections to the performance on specific datasets. difficulty is measured by the average model score between hard negatives and their corresponding head-relation pairs. more specifically, for a given kg triplet (h i , r i , t i ) and its associated hard negative pool n @xmath3, the difficulty is computed as follows: ## conclusion in this paper, we successfully improve a powerful dual-encoder-based kgc model by introducing various improved negative search methods and investigating their combinatorial effects. empirical results on four benchmarks with different scales confirm the superiority of our proposed methods, significantly beating a wide range of competitive methods and achieving state-of-the-art performance. for future work, we are interested in eliminating false negatives contained in sampled hard negatives. an exciting future direction is to use a model to filter out false negatives and potentially even identify pseudo positives, for more accurate models.