SMORE: Knowledge Graph Completion and Multi-hop Reasoning in Massive Knowledge Graphs

• URL: http://arxiv.org/abs/2110.14890v1
• Date: Thu, 28 Oct 2021 05:02:33 GMT
• Title: SMORE: Knowledge Graph Completion and Multi-hop Reasoning in Massive Knowledge Graphs
• Authors: Hongyu Ren, Hanjun Dai, Bo Dai, Xinyun Chen, Denny Zhou, Jure Leskovec, Dale Schuurmans
• Abstract summary: We present scalable Multi-hOp REasoning (SMORE), the first general framework for both single-hop and multi-hop reasoning in Knowledge Graphs (KGs) Using a single machine SMORE can perform multi-hop reasoning in Freebase KG (86M entities, 338M edges), which is 1,500x larger than previously considered KGs. SMORE increases throughput (i.e., training speed) over prior multi-hop KG frameworks by 2.2x with minimal GPU memory requirements.
• Score: 147.73127662757335
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Knowledge graphs (KGs) capture knowledge in the form of head--relation--tail triples and are a crucial component in many AI systems. There are two important reasoning tasks on KGs: (1) single-hop knowledge graph completion, which involves predicting individual links in the KG; and (2), multi-hop reasoning, where the goal is to predict which KG entities satisfy a given logical query. Embedding-based methods solve both tasks by first computing an embedding for each entity and relation, then using them to form predictions. However, existing scalable KG embedding frameworks only support single-hop knowledge graph completion and cannot be applied to the more challenging multi-hop reasoning task. Here we present Scalable Multi-hOp REasoning (SMORE), the first general framework for both single-hop and multi-hop reasoning in KGs. Using a single machine SMORE can perform multi-hop reasoning in Freebase KG (86M entities, 338M edges), which is 1,500x larger than previously considered KGs. The key to SMORE's runtime performance is a novel bidirectional rejection sampling that achieves a square root reduction of the complexity of online training data generation. Furthermore, SMORE exploits asynchronous scheduling, overlapping CPU-based data sampling, GPU-based embedding computation, and frequent CPU--GPU IO. SMORE increases throughput (i.e., training speed) over prior multi-hop KG frameworks by 2.2x with minimal GPU memory requirements (2GB for training 400-dim embeddings on 86M-node Freebase) and achieves near linear speed-up with the number of GPUs. Moreover, on the simpler single-hop knowledge graph completion task SMORE achieves comparable or even better runtime performance to state-of-the-art frameworks on both single GPU and multi-GPU settings.

Related papers

• A Prompt-Based Knowledge Graph Foundation Model for Universal In-Context Reasoning [17.676185326247946]
  We propose a prompt-based KG foundation model via in-context learning, namely KG-ICL, to achieve a universal reasoning ability. To encode prompt graphs with the generalization ability to unseen entities and relations in queries, we first propose a unified tokenizer. Then, we propose two message passing neural networks to perform prompt encoding and KG reasoning, respectively.
  arXiv  Detail & Related papers  (2024-10-16T06:47:18Z)
• Efficient Parallel Multi-Hop Reasoning: A Scalable Approach for Knowledge Graph Analysis [0.0]
  Multi-hop reasoning (MHR) is a critical function in various applications. This paper focuses on optimizing MHR for time efficiency on large-scale graphs. We introduce a novel parallel algorithm that harnesses domain-specific learned embeddings.
  arXiv  Detail & Related papers  (2024-06-11T21:12:34Z)
• Less is More: Hop-Wise Graph Attention for Scalable and Generalizable Learning on Circuits [12.468913984721018]
  HOGA is a novel attention-based model for learning circuit representations in a scalable and generalizable manner. As a result, HOGA is adaptive to various structures across different circuits and can be efficiently trained in a distributed manner.
  arXiv  Detail & Related papers  (2024-03-02T21:33:23Z)
• 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)
• UniKGQA: Unified Retrieval and Reasoning for Solving Multi-hop Question Answering Over Knowledge Graph [89.98762327725112]
  Multi-hop Question Answering over Knowledge Graph(KGQA) aims to find the answer entities that are multiple hops away from the topic entities mentioned in a natural language question. We propose UniKGQA, a novel approach for multi-hop KGQA task, by unifying retrieval and reasoning in both model architecture and parameter learning.
  arXiv  Detail & Related papers  (2022-12-02T04:08:09Z)
• SQUIRE: A Sequence-to-sequence Framework for Multi-hop Knowledge Graph Reasoning [21.53970565708247]
  Given a triple query, multi-hop reasoning task aims to give an evidential path that indicates the inference process. We present SQUIRE, the first Sequence-to-sequence based multi-hop reasoning framework.
  arXiv  Detail & Related papers  (2022-01-17T04:22:54Z)
• Scaling Graph Neural Networks with Approximate PageRank [64.92311737049054]
  We present the PPRGo model which utilizes an efficient approximation of information diffusion in GNNs. In addition to being faster, PPRGo is inherently scalable, and can be trivially parallelized for large datasets like those found in industry settings. We show that training PPRGo and predicting labels for all nodes in this graph takes under 2 minutes on a single machine, far outpacing other baselines on the same graph.
  arXiv  Detail & Related papers  (2020-07-03T09:30:07Z)
• KACC: A Multi-task Benchmark for Knowledge Abstraction, Concretization and Completion [99.47414073164656]
  A comprehensive knowledge graph (KG) contains an instance-level entity graph and an ontology-level concept graph. The two-view KG provides a testbed for models to "simulate" human's abilities on knowledge abstraction, concretization, and completion. We propose a unified KG benchmark by improving existing benchmarks in terms of dataset scale, task coverage, and difficulty.
  arXiv  Detail & Related papers  (2020-04-28T16:21:57Z)
• Heterogeneous CPU+GPU Stochastic Gradient Descent Algorithms [1.3249453757295084]
  We study training algorithms for deep learning on heterogeneous CPU+GPU architectures. Our two-fold objective -- maximize convergence rate and resource utilization simultaneously -- makes the problem challenging. We show that the implementation of these algorithms achieves both faster convergence and higher resource utilization than on several real datasets.
  arXiv  Detail & Related papers  (2020-04-19T05:21:20Z)
• MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical Models [96.1052289276254]
  This work introduces a new MAP-solver, based on the popular Dual Block-Coordinate Ascent principle. Surprisingly, by making a small change to the low-performing solver, we derive the new solver MPLP++ that significantly outperforms all existing solvers by a large margin.
  arXiv  Detail & Related papers  (2020-04-16T16:20:53Z)

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.