A Schema-aware Logic Reformulation for Graph Reachability

• URL: http://arxiv.org/abs/2410.02533v1
• Date: Thu, 3 Oct 2024 14:39:49 GMT
• Title: A Schema-aware Logic Reformulation for Graph Reachability
• Authors: Davide Di Pierro, Stefano Ferilli,
• Abstract summary: We propose a strategy to automatically exclude and sort certain graph paths by exploiting the higher-level conceptualization of instances. The aim is to obtain a new first-order logic reformulation of the graph reachability scenario, capable of improving the traditional algorithms in terms of time, space requirements, and number of backtracks.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Graph reachability is the task of understanding whether two distinct points in a graph are interconnected by arcs to which in general a semantic is attached. Reachability has plenty of applications, ranging from motion planning to routing. Improving reachability requires structural knowledge of relations so as to avoid the complexity of traditional depth-first and breadth-first strategies, implemented in logic languages. In some contexts, graphs are enriched with their schema definitions establishing domain and range for every arc. The introduction of a schema-aware formalization for guiding the search may result in a sensitive improvement by cutting out unuseful paths and prioritising those that, in principle, reach the target earlier. In this work, we propose a strategy to automatically exclude and sort certain graph paths by exploiting the higher-level conceptualization of instances. The aim is to obtain a new first-order logic reformulation of the graph reachability scenario, capable of improving the traditional algorithms in terms of time, space requirements, and number of backtracks. The experiments exhibit the expected advantages of the approach in reducing the number of backtracks during the search strategy, resulting in saving time and space as well.

Related papers

• Can Graph Learning Improve Planning in LLM-based Agents? [61.47027387839096]
  Task planning in language agents is emerging as an important research topic alongside the development of large language models (LLMs) In this paper, we explore graph learning-based methods for task planning, a direction that is to the prevalent focus on prompt design. Our interest in graph learning stems from a theoretical discovery: the biases of attention and auto-regressive loss impede LLMs' ability to effectively navigate decision-making on graphs.
  arXiv  Detail & Related papers  (2024-05-29T14:26:24Z)
• CoRe-GD: A Hierarchical Framework for Scalable Graph Visualization with GNNs [20.706469085872516]
  We introduce a scalable Graph Neural Network (GNN) based Graph Drawing framework with sub-quadratic that can learn to optimize stress. Inspired by classical stress optimization techniques and force-directed layout algorithms, we create a coarsening hierarchy for the input graph. To enhance information propagation within the network, we propose a novel positional rewiring technique.
  arXiv  Detail & Related papers  (2024-02-09T10:50:45Z)
• Multi-Scene Generalized Trajectory Global Graph Solver with Composite Nodes for Multiple Object Tracking [61.69892497726235]
  Composite Node Message Passing Network (CoNo-Link) is a framework for modeling ultra-long frames information for association. In addition to the previous method of treating objects as nodes, the network innovatively treats object trajectories as nodes for information interaction. Our model can learn better predictions on longer-time scales by adding composite nodes.
  arXiv  Detail & Related papers  (2023-12-14T14:00:30Z)
• Learning High-level Semantic-Relational Concepts for SLAM [10.528810470934781]
  We propose an algorithm for learning high-level semantic-relational concepts that can be inferred from the low-level factor graph. We validate our method in both simulated and real datasets demonstrating improved performance over two baseline approaches.
  arXiv  Detail & Related papers  (2023-09-30T14:54:31Z)
• Graph Value Iteration [35.87805182676444]
  deep Reinforcement Learning (RL) has been successful in various search domains, such as two-player games and scientific discovery. One major difficulty is that without a human-crafted function, reward signals remain zero unless the learning framework discovers any solution plan. We propose a domain-independent method that augments graph search with graph value iteration to solve hard planning instances.
  arXiv  Detail & Related papers  (2022-09-20T10:45:03Z)
• Subgraph Matching via Query-Conditioned Subgraph Matching Neural Networks and Bi-Level Tree Search [33.9052190473029]
  Subgraph Matching is a core operation in graph database search, biomedical analysis, social group finding, etc. In this paper, we propose a novel encoder-decoder neural network architecture to dynamically compute the matching information between the query and the target graphs. Experiments on five large real-world target graphs show that N-BLS can significantly improve the subgraph matching performance.
  arXiv  Detail & Related papers  (2022-07-21T04:47:21Z)
• Automatic Relation-aware Graph Network Proliferation [182.30735195376792]
  We propose Automatic Relation-aware Graph Network Proliferation (ARGNP) for efficiently searching GNNs. These operations can extract hierarchical node/relational information and provide anisotropic guidance for message passing on a graph. Experiments on six datasets for four graph learning tasks demonstrate that GNNs produced by our method are superior to the current state-of-the-art hand-crafted and search-based GNNs.
  arXiv  Detail & Related papers  (2022-05-31T10:38:04Z)
• Graph Pooling for Graph Neural Networks: Progress, Challenges, and Opportunities [128.55790219377315]
  Graph neural networks have emerged as a leading architecture for many graph-level tasks. graph pooling is indispensable for obtaining a holistic graph-level representation of the whole graph.
  arXiv  Detail & Related papers  (2022-04-15T04:02:06Z)
• 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)
• Temporal graph-based approach for behavioural entity classification [0.0]
  In this study, a two phased approach for exploiting the potential of graph structures in the cybersecurity domain is presented. The main idea is to convert a network classification problem into a graph-based behavioural one. We extract these graph structures that can represent the evolution of both normal and attack entities. Three clustering techniques are applied to the normal entities in order to aggregate similar behaviours, mitigate the imbalance problem and reduce noisy data.
  arXiv  Detail & Related papers  (2021-05-11T06:13:58Z)
• Long-Horizon Visual Planning with Goal-Conditioned Hierarchical Predictors [124.30562402952319]
  The ability to predict and plan into the future is fundamental for agents acting in the world. Current learning approaches for visual prediction and planning fail on long-horizon tasks. We propose a framework for visual prediction and planning that is able to overcome both of these limitations.
  arXiv  Detail & Related papers  (2020-06-23T17:58:56Z)

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.