Efficient and Scalable Neural Symbolic Search for Knowledge Graph Complex Query Answering

• URL: http://arxiv.org/abs/2505.08155v3
• Date: Tue, 20 May 2025 12:09:36 GMT
• Title: Efficient and Scalable Neural Symbolic Search for Knowledge Graph Complex Query Answering
• Authors: Weizhi Fei, Zihao Wang, hang Yin, Shukai Zhao, Wei Zhang, Yangqiu Song,
• Abstract summary: We propose an efficient and scalable symbolic search framework for complex queries.<n>Our framework reduces the computational load of symbolic methods by 90% while maintaining nearly the same performance.
• Score: 50.1887329564127
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Complex Query Answering (CQA) aims to retrieve answer sets for complex logical formulas from incomplete knowledge graphs, which is a crucial yet challenging task in knowledge graph reasoning. While neuro-symbolic search utilized neural link predictions achieve superior accuracy, they encounter significant complexity bottlenecks: (i) Data complexity typically scales quadratically with the number of entities in the knowledge graph, and (ii) Query complexity becomes NP-hard for cyclic queries. Consequently, these approaches struggle to effectively scale to larger knowledge graphs and more complex queries. To address these challenges, we propose an efficient and scalable symbolic search framework. First, we propose two constraint strategies to compute neural logical indices to reduce the domain of variables, thereby decreasing the data complexity of symbolic search. Additionally, we introduce an approximate algorithm based on local search to tackle the NP query complexity of cyclic queries. Experiments on various CQA benchmarks demonstrate that our framework reduces the computational load of symbolic methods by 90\% while maintaining nearly the same performance, thus alleviating both efficiency and scalability issues.

Related papers

• Discovering physical laws with parallel combinatorial tree search [57.05912962368898]
  Symbolic regression plays a crucial role in scientific research thanks to its capability of discovering concise and interpretable mathematical expressions from data.<n>Existing algorithms have faced a critical bottleneck of accuracy and efficiency over a decade.<n>We introduce a parallel tree search (PCTS) model to efficiently distill generic mathematical expressions from limited data.
  arXiv  Detail & Related papers  (2024-07-05T10:41:15Z)
• Data Complexity in Expressive Description Logics With Path Expressions [7.832189413179361]
  We investigate the data complexity of the satisfiability problem for the expressive description logic ZOIQ (a.k.a. ALCHb Self reg OIQ) over quasi-forests. This completes the data complexity landscape for decidable fragments of ZOIQ, and reproves known results on decidable fragments of OWL2 (SR family)
  arXiv  Detail & Related papers  (2024-06-11T09:37:51Z)
• Improving Complex Reasoning over Knowledge Graph with Logic-Aware Curriculum Tuning [89.89857766491475]
  We propose a curriculum-based logical-aware instruction tuning framework, named LACT.<n>Specifically, we augment the arbitrary first-order logical queries via binary tree decomposition.<n> Experiments across widely used datasets demonstrate that LACT has substantial improvements(brings an average +5.5% MRR score) over advanced methods, achieving the new state-of-the-art.
  arXiv  Detail & Related papers  (2024-05-02T18:12:08Z)
• 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)
• Query2Triple: Unified Query Encoding for Answering Diverse Complex Queries over Knowledge Graphs [29.863085746761556]
  We propose Query to Triple (Q2T), a novel approach that decouples the training for simple and complex queries. Our proposed Q2T is not only efficient to train, but also modular, thus easily adaptable to various neural link predictors.
  arXiv  Detail & Related papers  (2023-10-17T13:13:30Z)
• Complex Logical Reasoning over Knowledge Graphs using Large Language Models [13.594992599230277]
  Reasoning over knowledge graphs (KGs) is a challenging task that requires a deep understanding of the relationships between entities. Current approaches rely on learning geometries to embed entities in vector space for logical query operations. We propose a novel decoupled approach, Language-guided Abstract Reasoning over Knowledge graphs (LARK), that formulates complex KG reasoning as a combination of contextual KG search and logical query reasoning.
  arXiv  Detail & Related papers  (2023-05-02T02:21:49Z)
• 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)
• 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)
• A tetrachotomy of ontology-mediated queries with a covering axiom [1.749935196721634]
  Our concern is the problem of efficiently determining the data complexity of answering queries mediated by description and their optimal rewritings to standard database queries. We focus on Boolean conjunctive-mediated queries called disjunctive sirups (or d-sirups) Some d-sirups only have exponential-size resolution features, some only double-exponential-size positive existential existential-rewritings and single-exprecursive datalog rewritings.
  arXiv  Detail & Related papers  (2020-06-07T14:47:07Z)

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.