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

Proceedings of the 17th Conference of the European Chapter of the Association for Computational Linguistics, pages 1818–1832 May 2-6, 2023 ©2023 Association for Computational Linguistics Don’t Mess with Mister-in-Between: Improved Negative Search for Knowledge Graph Completion Fan Jiang and Tom Drummond and Trevor Cohn School of Computing and Information Systems The University of Melbourne, Victoria, Australia fan.jiang1@student.unimelb.edu.au {tom.drummond, t.cohn}@unimelb.edu.au Abstract The best methods for knowledge graph comple- tion use a ‘dual-encoding’ framework, a form of neural model with a bottleneck that facili- tates fast approximate search over a vast col- lection of candidates. These approaches are trained using contrastive learning to differenti- ate between known positive examples and sam- pled negative instances. The mechanism for sampling negatives to date has been very sim- ple, driven by pragmatic engineering consider- ations (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 lex- ical overlaps, from the dual-encoder model and according to knowledge graph structures. Ex- perimental results on four benchmarks show that our best single model improves consis- tently over previous methods and obtains new state-of-the-art performance, including the chal- lenging large-scale Wikidata5M dataset. Comb- ing different strategies through model ensem- bling results in a further performance boost. 1 Introduction A Knowledge Graph (KG) is a structured form of human knowledge consisting of entities, facts, rela- tionships 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 an- swering (Yasunaga et al., 2021) and reasoning (Ren and Leskovec, 2020). Knowledge Graph Comple- tion (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 meth- ods are two mainstream techniques for KGC prob- lems. The former typically map entities and rela- tions into fixed dense vectors and maximises the probability of valid triples using specially-designed scoring functions (Bordes et al., 2013; Sun et al., 2019); while the latter additionally uses avail- able textual descriptions associated with entities to gather more information (Wang et al., 2021b). Sur- prisingly, 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, Wang et al. (2022) 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 train- ing instances and randomly sampled negative in- stances (Karpukhin et al., 2020). 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 in- efficient in training dual encoders (Lu et …

Content truncated to 500 words