論文の概要: Learning Graph Search Heuristics

• arxiv url: http://arxiv.org/abs/2212.03978v1
• Date: Wed, 7 Dec 2022 22:28:00 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-09 14:47:11.659393
• Title: Learning Graph Search Heuristics
• Title（参考訳）: グラフ検索の学習ヒューリスティックス
• Authors: Michal P\'andy, Weikang Qiu, Gabriele Corso, Petar Veli\v{c}kovi\'c, Rex Ying, Jure Leskovec, Pietro Li\`o
• Abstract要約: 本稿では,新しいニューラルネットワークと学習アルゴリズムであるPHIL(Path Heuristic with Imitation Learning)について述べる。 我々の関数は、ノード距離の推測に有用なグラフ埋め込みを学習し、グラフサイズに依存しない一定時間で実行し、テスト時にA*のようなアルゴリズムに容易に組み込むことができる。 実験の結果、PHILはベンチマークデータセットの最先端の手法と比較して平均58.5%の探索ノード数を削減している。
• 参考スコア（独自算出の注目度）: 48.83557172525969
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Searching for a path between two nodes in a graph is one of the most well-studied and fundamental problems in computer science. In numerous domains such as robotics, AI, or biology, practitioners develop search heuristics to accelerate their pathfinding algorithms. However, it is a laborious and complex process to hand-design heuristics based on the problem and the structure of a given use case. Here we present PHIL (Path Heuristic with Imitation Learning), a novel neural architecture and a training algorithm for discovering graph search and navigation heuristics from data by leveraging recent advances in imitation learning and graph representation learning. At training time, we aggregate datasets of search trajectories and ground-truth shortest path distances, which we use to train a specialized graph neural network-based heuristic function using backpropagation through steps of the pathfinding process. Our heuristic function learns graph embeddings useful for inferring node distances, runs in constant time independent of graph sizes, and can be easily incorporated in an algorithm such as A* at test time. Experiments show that PHIL reduces the number of explored nodes compared to state-of-the-art methods on benchmark datasets by 58.5\% on average, can be directly applied in diverse graphs ranging from biological networks to road networks, and allows for fast planning in time-critical robotics domains.
• Abstract（参考訳）: グラフ内の2つのノード間の経路を探すことは、コンピュータ科学において最もよく研究され基礎的な問題の一つである。 ロボット工学、AI、生物学などの多くの分野において、実践者はパスフィニングアルゴリズムを加速するために探索ヒューリスティックを開発する。 しかし、与えられたユースケースの問題と構造に基づいてヒューリスティックを手作業で設計するのは、面倒で複雑なプロセスである。 本稿では,新しいニューラルアーキテクチャであるphil(path heuristic with imitation learning)と,模倣学習とグラフ表現学習の最近の進歩を活用して,データからグラフ探索とナビゲーションヒューリスティックを検出するためのトレーニングアルゴリズムを提案する。 学習時には,探索軌跡と最短経路距離のデータセットを集約し,パスフィンディングプロセスのステップを通じてバックプロパゲーションを用いて,特殊なグラフニューラルネットワークに基づくヒューリスティック関数を訓練する。 我々のヒューリスティック関数は、ノード距離の推定に有用なグラフ埋め込みを学習し、グラフサイズに依存しない一定時間動作し、テスト時にa*のようなアルゴリズムに容易に組み込むことができる。 実験の結果、PHILはベンチマークデータセットの最先端の手法と比較して探索ノードの数を平均58.5倍に減らし、生物学的ネットワークから道路ネットワークまで多様なグラフに直接適用でき、時間クリティカルなロボット分野における高速な計画を可能にしている。

関連論文リスト

• State of the Art and Potentialities of Graph-level Learning [54.68482109186052]
  グラフレベルの学習は、比較、回帰、分類など、多くのタスクに適用されている。 グラフの集合を学習する伝統的なアプローチは、サブストラクチャのような手作りの特徴に依存している。 ディープラーニングは、機能を自動的に抽出し、グラフを低次元表現に符号化することで、グラフレベルの学習をグラフの規模に適応させるのに役立っている。
  論文  参考訳（メタデータ） (2023-01-14T09:15:49Z)
• 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)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  最適グラフ構造を学習するための二段階最適化手法を提案する。 また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
  論文  参考訳（メタデータ） (2022-05-06T03:37:00Z)
• Learning heuristics for A* [9.701208207491879]
  我々は,近年のニューラル推論の進歩と,グラフ上の経路探索問題に対する効率的な関数の学習を組み合わせる。 我々はマルチタスク学習を利用してDijkstraのアルゴリズムとA*探索アルゴリズムの一貫性のある関数を学習する。 その結果、学習した値上でA*を実行すると、Dijkstraと比較してターゲットノード探索が大幅に高速化されることがわかった。
  論文  参考訳（メタデータ） (2022-04-11T10:13:53Z)
• Multi-Robot Active Mapping via Neural Bipartite Graph Matching [49.72892929603187]
  本稿では,最小時間ステップにおけるシーンマップ構築の完全化を目的としたマルチロボットアクティブマッピングの問題点について検討する。 この問題の鍵は、より効率的なロボットの動きを可能にするゴール位置推定にある。 本稿では,ニューラルコマッピング(NeuralCoMapping)という新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-03-30T14:03:17Z)
• 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)
• Persistence Homology for Link Prediction: An Interactive View [15.068319518015421]
  リンク予測は、グラフ構造データにとって重要な学習タスクです。 2つのノード間の相互作用を特徴付ける新しいトポロジカルアプローチを提案する。 また、異なるベンチマークで最新技術を上回るグラフニューラルネットワーク手法を提案する。
  論文  参考訳（メタデータ） (2021-02-20T04:33:59Z)
• DiffMG: Differentiable Meta Graph Search for Heterogeneous Graph Neural Networks [45.075163625895286]
  我々はメタグラフを探索し、メタパスよりも複雑なセマンティック関係をキャプチャし、グラフニューラルネットワークが異なるタイプのエッジに沿ってメッセージを伝播する方法を決定する。 我々は、HINの候補メタグラフを表すために、有向非巡回グラフ(DAG)の形式で表現型検索空間を設計する。 本稿では,1回のGNNトレーニングに匹敵する検索コストを1対1に抑えるための,新しい効率的な探索アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-07T08:09:29Z)
• SIGN: Scalable Inception Graph Neural Networks [4.5158585619109495]
  本稿では,グラフサンプリングの必要性を助長する,効率的でスケーラブルなグラフ深層学習アーキテクチャを提案する。 私たちのアーキテクチャでは、異なるローカルグラフ演算子を使用して、そのタスクに最も適しています。 我々は,1億1000万のノードと15億のエッジを持つ,最大の公開グラフデータセットであるogbn-papers100Mについて,最先端の結果を得た。
  論文  参考訳（メタデータ） (2020-04-23T14:46:10Z)

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

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