論文の概要: Learning to Efficiently Propagate for Reasoning on Knowledge Graphs
- arxiv url: http://arxiv.org/abs/2206.04798v1
- Date: Tue, 7 Jun 2022 01:01:36 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-19 22:47:27.314436
- Title: Learning to Efficiently Propagate for Reasoning on Knowledge Graphs
- Title（参考訳）: 知識グラフの推論を効率的に広めるための学習
- Authors: Zhaocheng Zhu, Xinyu Yuan, Louis-Pascal Xhonneux, Ming Zhang, Maxime
Gazeau, Jian Tang
- Abstract要約: 本稿では,知識グラフに基づくパスベースの推論のための効率的なモデルであるA*Netを提案する。
我々のA*Netは、最も短い経路問題に対する古典的なA*アルゴリズムにインスパイアされ、各ステップで重要なノードとエッジを優先順位付けします。
A*Netは、既存の最先端パスベースの手法と競合する性能を達成する。
- 参考スコア（独自算出の注目度）: 18.296287311665907
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Path-based methods are more appealing solutions than embedding methods for
knowledge graph reasoning, due to their interpretability and generalization
ability to unseen graphs. However, path-based methods usually suffer from the
problem of scalability, as the time complexity grows exponentially w.r.t. the
length of paths. While recent methods compute reasoning paths with the
Bellman-Ford algorithm in polynomial time, the time and memory cost remains
very high, as they need to propagate through all the nodes and edges in the
graph. In this paper, we propose A*Net, an efficient model for path-based
reasoning on knowledge graphs. Inspired by the classical A* algorithm for
shortest path problems, our A*Net prioritizes important nodes and edges at each
propagation step, to reduce the time and memory footprint. Unlike the classical
A* algorithm that uses a heuristic function, we propose to learn the priority
function for each node to capture the complex semantics in knowledge graphs.
The priority function and the propagation steps are jointly optimized through
backpropagation. Experiments on both transductive and inductive knowledge graph
reasoning benchmarks show that A*Net achieves competitive performance with
existing state-of-the-art path-based methods, and meanwhile reduces the number
of messages, the time and the memory cost up to 7.2$\times$, 3.4$\times$ and
4.9$\times$ respectively.
- Abstract（参考訳）: パスベースの手法は、グラフの解釈可能性や一般化能力のため、知識グラフ推論のための埋め込み方法よりも魅力的である。
しかしながら、パスベースのメソッドは通常、時間複雑性が指数関数的に増加するため、スケーラビリティの問題に苦しむ。
最近の手法では、多項式時間でベルマン・フォードアルゴリズムによる推論経路を計算するが、時間とメモリコストは非常に高く、グラフのすべてのノードとエッジを伝播する必要がある。
本稿では,知識グラフに基づく経路ベース推論の効率的なモデルであるA*Netを提案する。
従来のA*アルゴリズムにヒントを得て、A*Netは各伝搬ステップにおいて重要なノードとエッジを優先し、時間とメモリフットプリントを削減する。
ヒューリスティック関数を用いた古典的A*アルゴリズムとは異なり、各ノードの優先度関数を学習して知識グラフの複雑な意味を捉えることを提案する。
優先順位関数と伝搬ステップはバックプロパゲーションにより共同で最適化される。
帰納的および帰納的知識グラフ推論ベンチマークの実験は、A*Netが既存のパスベースの手法と競合する性能を達成し、一方でメッセージの数、時間、メモリコストをそれぞれ7.2$\times$, 3.4$\times$, 4.9$\times$に削減していることを示している。
関連論文リスト
- Probabilistic Routing for Graph-Based Approximate Nearest Neighbor Search [3.934351369702082]
高次元空間における近似近接探索(ANNS)は、機械学習分野における重要な課題である。
本稿では,グラフ内のノードの近傍を探索する際の確率的保証を提供する手法を提案する。
次に,グラフ内のどの近傍が正確な距離計算を行うべきかを効率的に同定する新しい手法PEOを紹介する。
論文 参考訳（メタデータ） (2024-02-17T18:08:37Z) - Distance-Based Propagation for Efficient Knowledge Graph Reasoning [43.138409280069204]
知識グラフ補完(KGC)は、知識グラフ(KG)の未確認エッジを予測することを目的とする。
経路情報を集約することでこの問題に対処する新しい手法が提案されている。
新たな手法であるTAGNetは、効率的に情報を伝達することができる。
論文 参考訳（メタデータ） (2023-11-02T06:37:46Z) - Learning Graph Search Heuristics [48.83557172525969]
本稿では,新しいニューラルネットワークと学習アルゴリズムであるPHIL(Path Heuristic with Imitation Learning)について述べる。
我々の関数は、ノード距離の推測に有用なグラフ埋め込みを学習し、グラフサイズに依存しない一定時間で実行し、テスト時にA*のようなアルゴリズムに容易に組み込むことができる。
実験の結果、PHILはベンチマークデータセットの最先端の手法と比較して平均58.5%の探索ノード数を削減している。
論文 参考訳（メタデータ） (2022-12-07T22:28:00Z) - GraphWalks: Efficient Shape Agnostic Geodesic Shortest Path Estimation [93.60478281489243]
3次元曲面上の測地線経路を近似する学習可能なネットワークを提案する。
提案手法は,最短経路の効率的な近似と測地距離推定を提供する。
論文 参考訳（メタデータ） (2022-05-30T16:22:53Z) - DOTIN: Dropping Task-Irrelevant Nodes for GNNs [119.17997089267124]
最近のグラフ学習アプローチでは、学習のためのグラフのサイズを減らすためのプール戦略が導入されている。
我々はDOTIN(underlineDrunderlineopping underlineTask-underlineIrrelevant underlineNodes)と呼ばれる新しいアプローチを設計し、グラフのサイズを減らす。
本手法は,グラフ分類やグラフ編集距離を含むグラフレベルのタスクにおいて,GATを約50%高速化する。
論文 参考訳（メタデータ） (2022-04-28T12:00:39Z) - Road Extraction from Overhead Images with Graph Neural Networks [18.649284163019516]
本稿では,最終道路グラフを1パスで直接推測する手法を提案する。
鍵となるアイデアは、関心点の特定を担当する完全な畳み込みネットワークと、これらのポイント間のリンクを予測するグラフニューラルネットワークを組み合わせることである。
我々は,一般的なRoadTracerデータセット上の既存の作業に対して評価を行い,競合する結果を得た。
論文 参考訳（メタデータ） (2021-12-09T21:10:27Z) - 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) - Cream of the Crop: Distilling Prioritized Paths For One-Shot Neural
Architecture Search [60.965024145243596]
ワンショット重み共有手法は、高効率と競争性能のため、最近、ニューラルアーキテクチャ探索において大きな注目を集めている。
この問題を軽減するため, 単純で効果的な蒸留法を提案する。
本稿では、訓練中に優れた性能を示すアーキテクチャ候補を指す優先順位付けパスの概念を紹介する。
優先順位付けされた経路は、その性能や複雑さに応じて、ハエで変化するため、最終的な経路は作物のクリームである。
論文 参考訳（メタデータ） (2020-10-29T17:55:05Z) - Scalable Graph Neural Networks via Bidirectional Propagation [89.70835710988395]
グラフニューラルネットワーク(GNN)は、非ユークリッドデータを学習するための新興分野である。
本稿では、特徴ベクトルとトレーニング/テストノードの両方から局所的な双方向伝搬プロセスを利用するスケーラブルなGNNであるGBPを提案する。
実証実験により、GBPは、トレーニング/テスト時間を大幅に減らして最先端のパフォーマンスを達成することが示された。
論文 参考訳（メタデータ） (2020-10-29T08:55:33Z) - Co-embedding of Nodes and Edges with Graph Neural Networks [13.020745622327894]
グラフ埋め込みは、高次元および非ユークリッド特徴空間でデータ構造を変換しエンコードする方法である。
CensNetは一般的なグラフ埋め込みフレームワークで、ノードとエッジの両方を潜在機能空間に埋め込む。
提案手法は,4つのグラフ学習課題における最先端のパフォーマンスを達成または一致させる。
論文 参考訳（メタデータ） (2020-10-25T22:39:31Z) - Shortest path distance approximation using deep learning techniques [0.43461794560295636]
埋め込みを施したフィードフォワードニューラルネットワークは、比較的低い歪み誤差で距離を近似できることを示す。
提案手法は,Facebook,BlogCatalog,Youtube,Flickrのソーシャルネットワーク上で評価される。
論文 参考訳（メタデータ） (2020-02-12T21:59:25Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。