利用图谱信息优化路径搜索，显著减少回溯次数
A Schema-aware Logic Reformulation for Graph Reachability
- 基于图谱结构自动排除无效路径并排序
- 实验显示回溯次数大幅减少，节省时间和空间
- 适合需要高效路径搜索的场景如导航、规划
图可达性任务旨在判断图中两点是否通过带有语义的边相连。该任务在运动规划、路由等场景中有广泛应用。传统深度优先和广度优先策略复杂度高，需依赖逻辑语言实现。当图包含定义每条边域与范围的模式（schema）时，引入模式感知的推理机制可有效剪枝无效路径，优先探索可能更早到达目标的路径。本文提出一种自动化的第一阶逻辑重构方法，利用实例的高层概念化信息，对图路径进行筛选与排序。实验表明，该方法显著降低了搜索过程中的回溯次数，在时间、空间消耗及回溯数上均优于传统算法。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。