Complex Query Answering with Neural Link Predictors

• URL: http://arxiv.org/abs/2011.03459v4
• Date: Thu, 18 Mar 2021 09:42:49 GMT
• Title: Complex Query Answering with Neural Link Predictors
• Authors: Erik Arakelyan, Daniel Daza, Pasquale Minervini, Michael Cochez
• Abstract summary: We propose a framework for efficiently answering complex queries on incomplete Knowledge Graphs. We translate each query into an end-to-end differentiable objective, where the truth value of each atom is computed by a pre-trained neural predictor. In our experiments, the proposed approach produces more accurate results than state-of-the-art methods.
• Score: 13.872400132315988
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Neural link predictors are immensely useful for identifying missing edges in large scale Knowledge Graphs. However, it is still not clear how to use these models for answering more complex queries that arise in a number of domains, such as queries using logical conjunctions ($\land$), disjunctions ($\lor$) and existential quantifiers ($\exists$), while accounting for missing edges. In this work, we propose a framework for efficiently answering complex queries on incomplete Knowledge Graphs. We translate each query into an end-to-end differentiable objective, where the truth value of each atom is computed by a pre-trained neural link predictor. We then analyse two solutions to the optimisation problem, including gradient-based and combinatorial search. In our experiments, the proposed approach produces more accurate results than state-of-the-art methods -- black-box neural models trained on millions of generated queries -- without the need of training on a large and diverse set of complex queries. Using orders of magnitude less training data, we obtain relative improvements ranging from 8% up to 40% in Hits@3 across different knowledge graphs containing factual information. Finally, we demonstrate that it is possible to explain the outcome of our model in terms of the intermediate solutions identified for each of the complex query atoms. All our source code and datasets are available online, at https://github.com/uclnlp/cqd.

Related papers

• One Model, Any Conjunctive Query: Graph Neural Networks for Answering Complex Queries over Knowledge Graphs [7.34044245579928]
  We propose AnyCQ, a graph neural network model that can classify answers to any conjunctive query on any knowledge graph. We show that AnyCQ can generalize to large queries of arbitrary structure, reliably classifying and retrieving answers to samples where existing approaches fail.
  arXiv  Detail & Related papers  (2024-09-21T00:30:44Z)
• Meta Operator for Complex Query Answering on Knowledge Graphs [58.340159346749964]
  We argue that different logical operator types, rather than the different complex query types, are the key to improving generalizability. We propose a meta-learning algorithm to learn the meta-operators with limited data and adapt them to different instances of operators under various complex queries. Empirical results show that learning meta-operators is more effective than learning original CQA or meta-CQA models.
  arXiv  Detail & Related papers  (2024-03-15T08:54:25Z)
• Rethinking Complex Queries on Knowledge Graphs with Neural Link Predictors [58.340159346749964]
  We propose a new neural-symbolic method to support end-to-end learning using complex queries with provable reasoning capability. We develop a new dataset containing ten new types of queries with features that have never been considered. Our method outperforms previous methods significantly in the new dataset and also surpasses previous methods in the existing dataset at the same time.
  arXiv  Detail & Related papers  (2023-04-14T11:35:35Z)
• Neural Graph Reasoning: Complex Logical Query Answering Meets Graph Databases [63.96793270418793]
  Complex logical query answering (CLQA) is a recently emerged task of graph machine learning. We introduce the concept of Neural Graph Database (NGDBs) NGDB consists of a Neural Graph Storage and a Neural Graph Engine.
  arXiv  Detail & Related papers  (2023-03-26T04:03:37Z)
• Adapting Neural Link Predictors for Data-Efficient Complex Query Answering [45.961111441411084]
  We propose a parameter-efficient score emphadaptation model optimised to re-calibrate neural link prediction scores for the complex query answering task. CQD$mathcalA$ produces significantly more accurate results than current state-of-the-art methods.
  arXiv  Detail & Related papers  (2023-01-29T00:17:16Z)
• Logical Message Passing Networks with One-hop Inference on Atomic Formulas [57.47174363091452]
  We propose a framework for complex query answering that decomposes the Knowledge Graph embeddings from neural set operators. On top of the query graph, we propose the Logical Message Passing Neural Network (LMPNN) that connects the local one-hop inferences on atomic formulas to the global logical reasoning. Our approach yields the new state-of-the-art neural CQA model.
  arXiv  Detail & Related papers  (2023-01-21T02:34:06Z)
• Answering Complex Logical Queries on Knowledge Graphs via Query Computation Tree Optimization [24.53940704113805]
  We propose QTO (Query Computation Tree Optimization) to efficiently find the exact optimal solution. QTO finds the optimal solution by a forward-backward propagation on the tree-like graph computation, i.e., query computation tree. Experiments show that QTO obtains state-of-the-art performance on complex query answering, outperforming previous best results by an average of 22%.
  arXiv  Detail & Related papers  (2022-12-19T15:59:00Z)
• Neural Methods for Logical Reasoning Over Knowledge Graphs [14.941769519278745]
  We focus on answering multi-hop logical queries on Knowledge Graphs (KGs) Most previous works have been unable to create models that accept full First-Order Logical (FOL) queries. We introduce a set of models that use Neural Networks to create one-point vector embeddings to answer the queries.
  arXiv  Detail & Related papers  (2022-09-28T23:10:09Z)
• Neural-Symbolic Models for Logical Queries on Knowledge Graphs [17.290758383645567]
  We propose Graph Neural Network Query Executor (GNN-QE), a neural-symbolic model that enjoys the advantages of both worlds. GNN-QE decomposes a complex FOL query into relation projections and logical operations over fuzzy sets. Experiments on 3 datasets show that GNN-QE significantly improves over previous state-of-the-art models in answering FOL queries.
  arXiv  Detail & Related papers  (2022-05-16T18:39:04Z)
• Neural Subgraph Matching [57.05893848555512]
  NeuroMatch is an accurate, efficient, and robust neural approach to subgraph matching. NeuroMatch is 100x faster than existing geometric approaches and 18% more accurate than existing subgraph matching methods.
  arXiv  Detail & Related papers  (2020-07-06T22:06:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.