Approximate Knowledge Graph Query Answering: From Ranking to Binary Classification

• URL: http://arxiv.org/abs/2102.11389v1
• Date: Mon, 22 Feb 2021 22:28:08 GMT
• Title: Approximate Knowledge Graph Query Answering: From Ranking to Binary Classification
• Authors: Ruud van Bakel, Teodor Aleksiev, Daniel Daza, Dimitrios Alivanistos, Michael Cochez
• Abstract summary: Structured querying on incomplete graphs will result in incomplete sets of answers. Several algorithms for approximate structured query answering have been proposed. We argue that performing a ranking-based evaluation is not sufficient to assess methods for complex query answering.
• Score: 0.20999222360659608
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Large, heterogeneous datasets are characterized by missing or even erroneous information. This is more evident when they are the product of community effort or automatic fact extraction methods from external sources, such as text. A special case of the aforementioned phenomenon can be seen in knowledge graphs, where this mostly appears in the form of missing or incorrect edges and nodes. Structured querying on such incomplete graphs will result in incomplete sets of answers, even if the correct entities exist in the graph, since one or more edges needed to match the pattern are missing. To overcome this problem, several algorithms for approximate structured query answering have been proposed. Inspired by modern Information Retrieval metrics, these algorithms produce a ranking of all entities in the graph, and their performance is further evaluated based on how high in this ranking the correct answers appear. In this work we take a critical look at this way of evaluation. We argue that performing a ranking-based evaluation is not sufficient to assess methods for complex query answering. To solve this, we introduce Message Passing Query Boxes (MPQB), which takes binary classification metrics back into use and shows the effect this has on the recently proposed query embedding method MPQE.

Related papers

• Konstruktor: A Strong Baseline for Simple Knowledge Graph Question Answering [60.6042489577575]
  We introduce Konstruktor - an efficient and robust approach that breaks down the problem into three steps. Our approach integrates language models and knowledge graphs, exploiting the power of the former and the interpretability of the latter. We show that for relation detection, the most challenging step of the workflow, a combination of relation classification/generation and ranking outperforms other methods.
  arXiv  Detail & Related papers  (2024-09-24T09:19:11Z)
• 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)
• Open-Set Knowledge-Based Visual Question Answering with Inference Paths [79.55742631375063]
  The purpose of Knowledge-Based Visual Question Answering (KB-VQA) is to provide a correct answer to the question with the aid of external knowledge bases. We propose a new retriever-ranker paradigm of KB-VQA, Graph pATH rankER (GATHER for brevity) Specifically, it contains graph constructing, pruning, and path-level ranking, which not only retrieves accurate answers but also provides inference paths that explain the reasoning process.
  arXiv  Detail & Related papers  (2023-10-12T09:12:50Z)
• Approximate Answering of Graph Queries [40.375299599925924]
  In this chapter, we will give an overview of several methods which have been proposed to answer queries in such a setting. We will first provide an overview of the different query types which can be supported by these methods and datasets typically used for evaluation. Then, we give an overview of the different approaches and describe them in terms of expressiveness, supported graph types, and inference capabilities.
  arXiv  Detail & Related papers  (2023-08-12T14:47:21Z)
• A Method of Query Graph Reranking for Knowledge Base Question Answering [2.367061689316429]
  This paper presents a novel reranking method to better choose the optimal query graph, a sub-graph of knowledge graph, to retrieve the answer for an input question in Knowledge Base Question Answering (KBQA) Existing methods suffer from a severe problem that there is a significant gap between top-1 performance and the oracle score of top-n results.
  arXiv  Detail & Related papers  (2022-04-27T09:57:54Z)
• Semantic Structure based Query Graph Prediction for Question Answering over Knowledge Graph [5.5332967798665305]
  This paper focuses on query graph generation from natural language questions. Existing approaches for query graph generation ignore the semantic structure of a question. We develop a novel Structure-BERT to predict the semantic structure of a question.
  arXiv  Detail & Related papers  (2022-04-15T20:35:00Z)
• Knowledge Base Question Answering by Case-based Reasoning over Subgraphs [81.22050011503933]
  We show that our model answers queries requiring complex reasoning patterns more effectively than existing KG completion algorithms. The proposed model outperforms or performs competitively with state-of-the-art models on several KBQA benchmarks.
  arXiv  Detail & Related papers  (2022-02-22T01:34:35Z)
• Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
  Subgraph matching algorithms enumerate all is embeddings of a query graph in a data graph G. matching order plays a critical role in time efficiency of these backtracking based subgraph matching algorithms. In this paper, for the first time we apply the Reinforcement Learning (RL) and Graph Neural Networks (GNNs) techniques to generate the high-quality matching order for subgraph matching algorithms.
  arXiv  Detail & Related papers  (2022-01-25T00:10:03Z)
• Outlining and Filling: Hierarchical Query Graph Generation for Answering Complex Questions over Knowledge Graph [16.26384829957165]
  We propose a new two-stage approach to build query graphs. In the first stage, the top-$k$ related instances are collected by simple strategies. In the second stage, a graph generation model performs hierarchical generation.
  arXiv  Detail & Related papers  (2021-11-01T07:08:46Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  We introduce a novel learning problem for dense subgraph discovery. We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability. We then design a more scalable algorithm with a theoretical guarantee.
  arXiv  Detail & Related papers  (2020-06-24T11:37:33Z)
• Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
  We study the problem of clustering a set of items from binary user feedback. We devise an algorithm with a minimal cluster recovery error rate. For adaptive selection, we develop an algorithm inspired by the derivation of the information-theoretical error lower bounds.
  arXiv  Detail & Related papers  (2019-10-14T09:18:26Z)

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.