Less is More: One-shot Subgraph Reasoning on Large-scale Knowledge Graphs

• URL: http://arxiv.org/abs/2403.10231v1
• Date: Fri, 15 Mar 2024 12:00:12 GMT
• Title: Less is More: One-shot Subgraph Reasoning on Large-scale Knowledge Graphs
• Authors: Zhanke Zhou, Yongqi Zhang, Jiangchao Yao, Quanming Yao, Bo Han,
• Abstract summary: We propose the one-shot-subgraph link prediction to achieve efficient and adaptive prediction. Design principle is that, instead of directly acting on the whole KG, the prediction procedure is decoupled into two steps. We achieve promoted efficiency and leading performances on five large-scale benchmarks.
• Score: 49.547988001231424
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: To deduce new facts on a knowledge graph (KG), a link predictor learns from the graph structure and collects local evidence to find the answer to a given query. However, existing methods suffer from a severe scalability problem due to the utilization of the whole KG for prediction, which hinders their promise on large scale KGs and cannot be directly addressed by vanilla sampling methods. In this work, we propose the one-shot-subgraph link prediction to achieve efficient and adaptive prediction. The design principle is that, instead of directly acting on the whole KG, the prediction procedure is decoupled into two steps, i.e., (i) extracting only one subgraph according to the query and (ii) predicting on this single, query dependent subgraph. We reveal that the non-parametric and computation-efficient heuristics Personalized PageRank (PPR) can effectively identify the potential answers and supporting evidence. With efficient subgraph-based prediction, we further introduce the automated searching of the optimal configurations in both data and model spaces. Empirically, we achieve promoted efficiency and leading performances on five large-scale benchmarks. The code is publicly available at: https://github.com/tmlr-group/one-shot-subgraph.

Related papers

• Deep Generative Models for Subgraph Prediction [10.56335881963895]
  This paper introduces subgraph queries as a new task for deep graph learning. Subgraph queries jointly predict the components of a target subgraph based on evidence that is represented by an observed subgraph. We utilize a probabilistic deep Graph Generative Model to answer subgraph queries.
  arXiv  Detail & Related papers  (2024-08-07T19:24:02Z)
• Learning Large Graph Property Prediction via Graph Segment Training [61.344814074335304]
  We propose a general framework that allows learning large graph property prediction with a constant memory footprint. We refine the GST paradigm by introducing a historical embedding table to efficiently obtain embeddings for segments not sampled for backpropagation. Our experiments show that GST-EFD is both memory-efficient and fast, while offering a slight boost on test accuracy over a typical full graph training regime.
  arXiv  Detail & Related papers  (2023-05-21T02:53:25Z)
• Sampling Enclosing Subgraphs for Link Prediction [2.1270496914042996]
  Link prediction is a fundamental problem for graph-structured data computation. This paper presents a scalable solution, that we call ScaLed, which utilizes sparse enclosing subgraphs to make predictions. By leveraging the smaller sampled subgraph, ScaLed can scale to larger graphs with much less overhead while maintaining high accuracy.
  arXiv  Detail & Related papers  (2022-06-23T22:48:44Z)
• A Graph-Enhanced Click Model for Web Search [67.27218481132185]
  We propose a novel graph-enhanced click model (GraphCM) for web search. We exploit both intra-session and inter-session information for the sparsity and cold-start problems.
  arXiv  Detail & Related papers  (2022-06-17T08:32:43Z)
• Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
  Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We develop this idea in a concrete non-parametric method that we call Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We derive convergence rates for our collaborative approach that highlights the role played by variables such as the number of available observations per node, the size of the graph, and how accurately the graph structure encodes the similarity between tasks.
  arXiv  Detail & Related papers  (2022-05-28T15:37:03Z)
• Neural Graph Matching for Pre-training Graph Neural Networks [72.32801428070749]
  Graph neural networks (GNNs) have been shown powerful capacity at modeling structural data. We present a novel Graph Matching based GNN Pre-Training framework, called GMPT. The proposed method can be applied to fully self-supervised pre-training and coarse-grained supervised pre-training.
  arXiv  Detail & Related papers  (2022-03-03T09:53:53Z)
• Ensembling Graph Predictions for AMR Parsing [28.625065956013778]
  In many machine learning tasks, models are trained to predict structure data such as graphs. In this work, we formalize this problem as mining the largest graph that is the most supported by a collection of graph predictions. We show that the proposed approach can combine the strength of state-of-the-art AMRs to create new predictions that are more accurate than any individual models in five standard benchmark datasets.
  arXiv  Detail & Related papers  (2021-10-18T09:35:39Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)
• G2MF-WA: Geometric Multi-Model Fitting with Weakly Annotated Data [15.499276649167975]
  In weak annotating, most of the manual annotations are supposed to be correct yet inevitably mixed with incorrect ones. We propose a novel method to make full use of the WA data to boost the multi-model fitting performance.
  arXiv  Detail & Related papers  (2020-01-20T04:22:01Z)

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.