Localized RETE for Incremental Graph Queries

• URL: http://arxiv.org/abs/2405.01145v2
• Date: Fri, 5 Jul 2024 13:26:09 GMT
• Title: Localized RETE for Incremental Graph Queries
• Authors: Matthias Barkowsky, Holger Giese,
• Abstract summary: We propose an extension semantics that enables local yet fully incremental execution graph queries. The proposed technique can significantly improve performance regarding memory consumption and execution time in favorable cases, but may incur a noticeable linear overhead unfavorable cases.
• Score: 1.3858051019755282
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Context: The growing size of graph-based modeling artifacts in model-driven engineering calls for techniques that enable efficient execution of graph queries. Incremental approaches based on the RETE algorithm provide an adequate solution in many scenarios, but are generally designed to search for query results over the entire graph. However, in certain situations, a user may only be interested in query results for a subgraph, for instance when a developer is working on a large model of which only a part is loaded into their workspace. In this case, the global execution semantics can result in significant computational overhead. Contribution: To mitigate the outlined shortcoming, in this paper we propose an extension of the RETE approach that enables local, yet fully incremental execution of graph queries, while still guaranteeing completeness of results with respect to the relevant subgraph. Results: We empirically evaluate the presented approach via experiments inspired by a scenario from software development and an independent social network benchmark. The experimental results indicate that the proposed technique can significantly improve performance regarding memory consumption and execution time in favorable cases, but may incur a noticeable linear overhead in unfavorable cases.

Related papers

• Instance-Aware Graph Prompt Learning [71.26108600288308]
  We introduce Instance-Aware Graph Prompt Learning (IA-GPL) in this paper. The process involves generating intermediate prompts for each instance using a lightweight architecture. Experiments conducted on multiple datasets and settings showcase the superior performance of IA-GPL compared to state-of-the-art baselines.
  arXiv  Detail & Related papers  (2024-11-26T18:38:38Z)
• Likelihood as a Performance Gauge for Retrieval-Augmented Generation [78.28197013467157]
  We show that likelihoods serve as an effective gauge for language model performance. We propose two methods that use question likelihood as a gauge for selecting and constructing prompts that lead to better performance.
  arXiv  Detail & Related papers  (2024-11-12T13:14:09Z)
• Reasoning Graph Enhanced Exemplars Retrieval for In-Context Learning [13.381974811214764]
  Reasoning Graph-enhanced Exemplar Retrieval(RGER) RGER uses graph kernel to select exemplars with semantic and structural similarity. The efficacy of RGER on math and logit reasoning tasks showcases its superiority over state-of-the-art retrieval-based approaches.
  arXiv  Detail & Related papers  (2024-09-17T12:58:29Z)
• Less is More: One-shot Subgraph Reasoning on Large-scale Knowledge Graphs [49.547988001231424]
  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.
  arXiv  Detail & Related papers  (2024-03-15T12:00:12Z)
• Efficient Causal Graph Discovery Using Large Language Models [42.724534747353665]
  The proposed framework uses a breadth-first search (BFS) approach which allows it to use only a linear number of queries. In addition to being more time and data-efficient, the proposed framework achieves state-of-the-art results on real-world causal graphs of varying sizes.
  arXiv  Detail & Related papers  (2024-02-02T08:25:32Z)
• ProvG-Searcher: A Graph Representation Learning Approach for Efficient Provenance Graph Search [13.627536649679577]
  We present ProvG-Searcher, a novel approach for detecting known APT behaviors within system security logs. We formulate the task of searching provenance graphs as a subgraph matching problem and employ a graph representation learning method. Experimental results on standard datasets demonstrate that ProvG-Searcher achieves superior performance, with an accuracy exceeding 99% in detecting query behaviors.
  arXiv  Detail & Related papers  (2023-09-07T11:29:01Z)
• 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)
• Interactive Visual Pattern Search on Graph Data via Graph Representation Learning [20.795511688640296]
  We propose a visual analytics system GraphQ to support human-in-the-loop, example-based, subgraph pattern search. To support fast, interactive queries, we use graph neural networks (GNNs) to encode a graph as fixed-length latent vector representation. We also propose a novel GNN for node-alignment called NeuroAlign to facilitate easy validation and interpretation of the query results.
  arXiv  Detail & Related papers  (2022-02-18T22:30:28Z)
• Enel: Context-Aware Dynamic Scaling of Distributed Dataflow Jobs using Graph Propagation [52.9168275057997]
  This paper presents Enel, a novel dynamic scaling approach that uses message propagation on an attributed graph to model dataflow jobs. We show that Enel is able to identify effective rescaling actions, reacting for instance to node failures, and can be reused across different execution contexts.
  arXiv  Detail & Related papers  (2021-08-27T10:21:08Z)
• Probabilistic Case-based Reasoning for Open-World Knowledge Graph Completion [59.549664231655726]
  A case-based reasoning (CBR) system solves a new problem by retrieving cases' that are similar to the given problem. In this paper, we demonstrate that such a system is achievable for reasoning in knowledge-bases (KBs) Our approach predicts attributes for an entity by gathering reasoning paths from similar entities in the KB.
  arXiv  Detail & Related papers  (2020-10-07T17:48:12Z)
• IOHanalyzer: Detailed Performance Analyses for Iterative Optimization Heuristics [3.967483941966979]
  IOHanalyzer is a new user-friendly tool for the analysis, comparison, and visualization of performance data of IOHs. IOHanalyzer provides detailed statistics about fixed-target running times and about fixed-budget performance of the benchmarked algorithms. IOHanalyzer can directly process performance data from the main benchmarking platforms.
  arXiv  Detail & Related papers  (2020-07-08T08:20:19Z)

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.