論文の概要: Skeleton-Guided Learning for Shortest Path Search

• arxiv url: http://arxiv.org/abs/2508.02270v1
• Date: Mon, 04 Aug 2025 10:21:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-05 18:25:22.290687
• Title: Skeleton-Guided Learning for Shortest Path Search
• Title（参考訳）: 最短経路探索のための骨格誘導学習
• Authors: Tiantian Liu, Xiao Li, Huan Li, Hua Lu, Christian S. Jensen, Jianliang Xu,
• Abstract要約: 最短経路探索はグラフベースのアプリケーションにおける中核的な操作である。 汎用グラフ上での最短経路探索のための多目的学習に基づくフレームワークを提案する。
• 参考スコア（独自算出の注目度）: 31.51778160288742
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Shortest path search is a core operation in graph-based applications, yet existing methods face important limitations. Classical algorithms such as Dijkstra's and A* become inefficient as graphs grow more complex, while index-based techniques often require substantial preprocessing and storage. Recent learning-based approaches typically focus on spatial graphs and rely on context-specific features like geographic coordinates, limiting their general applicability. We propose a versatile learning-based framework for shortest path search on generic graphs, without requiring domain-specific features. At the core of our approach is the construction of a skeleton graph that captures multi-level distance and hop information in a compact form. A Skeleton Graph Neural Network (SGNN) operates on this structure to learn node embeddings and predict distances and hop lengths between node pairs. These predictions support LSearch, a guided search algorithm that uses model-driven pruning to reduce the search space while preserving accuracy. To handle larger graphs, we introduce a hierarchical training strategy that partitions the graph into subgraphs with individually trained SGNNs. This structure enables HLSearch, an extension of our method for efficient path search across graph partitions. Experiments on five diverse real-world graphs demonstrate that our framework achieves strong performance across graph types, offering a flexible and effective solution for learning-based shortest path search.
• Abstract（参考訳）: 最短経路探索はグラフベースのアプリケーションでは中核的な操作であるが、既存の手法には重要な制限がある。 Dijkstra や A* のような古典的なアルゴリズムはグラフが複雑化するにつれて非効率になるが、インデックスベースの手法ではプリプロセッシングやストレージを必要とすることが多い。 最近の学習ベースのアプローチは、一般に空間グラフに焦点をあて、地理的座標のようなコンテキスト固有の特徴に依存し、一般的な適用性を制限する。 本稿では,汎用グラフ上で最短経路探索を行うための汎用学習ベースのフレームワークを提案する。 我々のアプローチの核となるのは、マルチレベル距離とホップ情報をコンパクトな形でキャプチャするスケルトングラフの構築である。 Skeleton Graph Neural Network (SGNN)は、ノードの埋め込みを学習し、ノード間の距離とホップの長さを予測する。 これらの予測は、モデル駆動プルーニングを使用して精度を維持しながら検索スペースを削減するガイド付き検索アルゴリズムであるLSearchをサポートする。 より大規模なグラフを扱うために、個別に訓練されたSGNNを用いてグラフをサブグラフに分割する階層的なトレーニング戦略を導入する。 この構造により,グラフ分割を横断する効率的な経路探索法HLSearchが拡張される。 5つの多種多様な実世界のグラフの実験により、我々のフレームワークはグラフタイプ間で強力なパフォーマンスを達成し、学習に基づく最短経路探索のための柔軟で効果的なソリューションを提供することを示した。

関連論文リスト

• Finding Increasingly Large Extremal Graphs with AlphaZero and Tabu Search [31.68823192070739]
  この研究は、1975年のエルドホスの予想から着想を得た中心極端グラフ理論の問題を研究する。 それは、与えられた大きさ(ノード数)のグラフを見つけることを目的としており、3サイクルや4サイクルを必要とせずに、エッジの数を最大化する。
  論文  参考訳（メタデータ） (2023-11-06T22:29:55Z)
• GraphGLOW: Universal and Generalizable Structure Learning for Graph Neural Networks [72.01829954658889]
  本稿では,この新たな問題設定の数学的定義を紹介する。 一つのグラフ共有構造学習者と複数のグラフ固有GNNを協調する一般的なフレームワークを考案する。 十分に訓練された構造学習者は、微調整なしで、目に見えない対象グラフの適応的な構造を直接生成することができる。
  論文  参考訳（メタデータ） (2023-06-20T03:33:22Z)
• State of the Art and Potentialities of Graph-level Learning [54.68482109186052]
  グラフレベルの学習は、比較、回帰、分類など、多くのタスクに適用されている。 グラフの集合を学習する伝統的なアプローチは、サブストラクチャのような手作りの特徴に依存している。 ディープラーニングは、機能を自動的に抽出し、グラフを低次元表現に符号化することで、グラフレベルの学習をグラフの規模に適応させるのに役立っている。
  論文  参考訳（メタデータ） (2023-01-14T09:15:49Z)
• Learning Graph Search Heuristics [48.83557172525969]
  本稿では,新しいニューラルネットワークと学習アルゴリズムであるPHIL(Path Heuristic with Imitation Learning)について述べる。 我々の関数は、ノード距離の推測に有用なグラフ埋め込みを学習し、グラフサイズに依存しない一定時間で実行し、テスト時にA*のようなアルゴリズムに容易に組み込むことができる。 実験の結果、PHILはベンチマークデータセットの最先端の手法と比較して平均58.5%の探索ノード数を削減している。
  論文  参考訳（メタデータ） (2022-12-07T22:28:00Z)
• Subgraph Matching via Query-Conditioned Subgraph Matching Neural Networks and Bi-Level Tree Search [33.9052190473029]
  サブグラフマッチングは、グラフデータベース検索、バイオメディカル分析、ソーシャルグループ検索などにおける中核的な操作である。 本稿では,クエリと対象グラフのマッチング情報を動的に計算する,新しいエンコーダ・デコーダニューラルネットワークアーキテクチャを提案する。 5つの大きな実世界のターゲットグラフの実験により、N-BLSはサブグラフマッチング性能を大幅に改善できることが示された。
  論文  参考訳（メタデータ） (2022-07-21T04:47:21Z)
• Automatic Relation-aware Graph Network Proliferation [182.30735195376792]
  GNNを効率的に検索するためのARGNP(Automatic Relation-Aware Graph Network Proliferation)を提案する。 これらの操作は階層的なノード/リレーショナル情報を抽出し、グラフ上のメッセージパッシングのための異方的ガイダンスを提供する。 4つのグラフ学習タスクのための6つのデータセットの実験により、我々の手法によって生成されたGNNは、現在最先端の手作りおよび検索に基づくGNNよりも優れていることが示された。
  論文  参考訳（メタデータ） (2022-05-31T10:38:04Z)
• Towards Unsupervised Deep Graph Structure Learning [67.58720734177325]
  本稿では,学習したグラフトポロジを外部ガイダンスなしでデータ自身で最適化する,教師なしグラフ構造学習パラダイムを提案する。 具体的には、元のデータから"アンカーグラフ"として学習目標を生成し、対照的な損失を用いてアンカーグラフと学習グラフとの一致を最大化する。
  論文  参考訳（メタデータ） (2022-01-17T11:57:29Z)
• Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Tracking [58.30147362745852]
  フレーム間のデータアソシエーションは、Multiple Object Tracking(MOT)タスクの中核にある。 既存の手法は、主にトラックレットとフレーム内検出の間のコンテキスト情報を無視する。 そこで本研究では,学習可能なグラフマッチング手法を提案する。
  論文  参考訳（メタデータ） (2021-03-30T08:58:45Z)
• Co-embedding of Nodes and Edges with Graph Neural Networks [13.020745622327894]
  グラフ埋め込みは、高次元および非ユークリッド特徴空間でデータ構造を変換しエンコードする方法である。 CensNetは一般的なグラフ埋め込みフレームワークで、ノードとエッジの両方を潜在機能空間に埋め込む。 提案手法は,4つのグラフ学習課題における最先端のパフォーマンスを達成または一致させる。
  論文  参考訳（メタデータ） (2020-10-25T22:39:31Z)
• GLSearch: Maximum Common Subgraph Detection via Learning to Search [33.9052190473029]
  検索モデルに対するグラフニューラルネットワーク(GNN)に基づく学習手法であるGLSearchを提案する。 このモデルでは2つの入力グラフから1対のノードを選択して一度に拡張する。 我々のGLSearchは、グラフ上の制約で他の多くの問題を解決するために拡張できる可能性がある。
  論文  参考訳（メタデータ） (2020-02-08T10:03:40Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。