論文の概要: Answering Complex Logical Queries on Knowledge Graphs via Query Computation Tree Optimization

• arxiv url: http://arxiv.org/abs/2212.09567v2
• Date: Wed, 21 Dec 2022 06:57:32 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-22 14:20:50.300170
• Title: Answering Complex Logical Queries on Knowledge Graphs via Query Computation Tree Optimization
• Title（参考訳）: 問合せ木最適化による知識グラフ上の複雑な論理的クエリの解法
• Authors: Yushi Bai, Xin Lv, Juanzi Li, Lei Hou
• Abstract要約: そこで我々は,QTO (Query Computation Tree Optimization) を提案する。 QTOは、木のようなグラフ計算、すなわちクエリ計算ツリーの前方への伝播によって最適な解を求める。 3つのデータセットの実験から、QTOは複雑なクエリ応答における最先端のパフォーマンスを得ており、以前の最高の結果を平均22%上回っている。
• 参考スコア（独自算出の注目度）: 24.53940704113805
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Answering complex logical queries on incomplete knowledge graphs is a challenging task, and has been widely studied. Embedding-based methods require training on complex queries, and cannot generalize well to out-of-distribution query structures. Recent work frames this task as an end-to-end optimization problem, and it only requires a pretrained link predictor. However, due to the exponentially large combinatorial search space, the optimal solution can only be approximated, limiting the final accuracy. In this work, we propose QTO (Query Computation Tree Optimization) that can efficiently find the exact optimal solution. QTO finds the optimal solution by a forward-backward propagation on the tree-like computation graph, i.e., query computation tree. In particular, QTO utilizes the independence encoded in the query computation tree to reduce the search space, where only local computations are involved during the optimization procedure. Experiments on 3 datasets show that QTO obtains state-of-the-art performance on complex query answering, outperforming previous best results by an average of 22%. Moreover, QTO can interpret the intermediate solutions for each of the one-hop atoms in the query with over 90% accuracy.
• Abstract（参考訳）: 不完全な知識グラフ上で複雑な論理クエリに応答することは難しい課題であり、広く研究されている。 埋め込みベースのメソッドは複雑なクエリのトレーニングを必要とし、分散のクエリ構造にうまく一般化できない。 最近の作業では、このタスクをエンドツーエンドの最適化問題として捉えており、事前訓練されたリンク予測器のみを必要とする。 しかし、指数関数的に大きい組合せ探索空間のため、最適解は近似され、最終的な精度が制限される。 本研究では,最適解を効率的に見つけるためのqto(query computation tree optimization)を提案する。 QTOは、木のような計算グラフ、すなわちクエリ計算ツリーの前方への伝播によって最適な解を求める。 特に、QTOは、クエリ計算ツリーにエンコードされた独立性を利用して、最適化処理中にローカルな計算のみに関わる検索スペースを削減する。 3つのデータセットの実験から、QTOは複雑なクエリ応答における最先端のパフォーマンスを得ており、以前の最高の結果を平均22%上回っている。 さらにqtoは、クエリ内の各1ホップ原子の中間解を90%以上の精度で解釈することができる。

関連論文リスト

• Quality-Diversity Algorithms Can Provably Be Helpful for Optimization [24.694984679399315]
  QD(Quality-Diversity)アルゴリズムは、ハイパフォーマンスだが多様なソリューションのセットを見つけることを目的としている。 本稿では,厳密な実行時間解析によってQDアルゴリズムの最適化能力に光を当てようとしている。
  論文  参考訳（メタデータ） (2024-01-19T07:40:24Z)
• JoinGym: An Efficient Query Optimization Environment for Reinforcement Learning [58.71541261221863]
  結合順序選択(JOS)は、クエリの実行コストを最小化するために結合操作を順序付けする問題である。 木質強化学習(RL)のためのクエリ最適化環境JoinGymを提案する。 JoinGymは内部で、事前計算されたデータセットから中間結果の濃度を調べることで、クエリプランのコストをシミュレートする。
  論文  参考訳（メタデータ） (2023-07-21T17:00:06Z)
• Adapting Neural Link Predictors for Data-Efficient Complex Query Answering [45.961111441411084]
  本稿では,複雑な問合せタスクに対して,ニューラルネットワーク予測スコアを再校正するために最適化されたパラメータ効率のスコア強調モデルを提案する。 CQD$mathcalA$は現在の最先端手法よりもはるかに正確な結果が得られる。
  論文  参考訳（メタデータ） (2023-01-29T00:17:16Z)
• Logical Message Passing Networks with One-hop Inference on Atomic Formulas [57.47174363091452]
  本稿では,ニューラルネットワーク演算子から知識グラフの埋め込みを分解する,複雑な問合せ応答のためのフレームワークを提案する。 クエリグラフの上に、局所的な原子式上のワンホップ推論とグローバル論理的推論を結びつける論理メッセージパッシングニューラルネットワーク(LMPNN)を提案する。 我々のアプローチは、最先端のニューラルCQAモデルをもたらす。
  論文  参考訳（メタデータ） (2023-01-21T02:34:06Z)
• Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
  多くの現実世界では、T関数の評価の予算を考えると、高価なブラックボックス関数 f の性質を推測したい。 本稿では,アルゴリズムの出力に対して相互情報を最大化するクエリを逐次選択する手法InfoBAXを提案する。 これらの問題に対してInfoBAXは、元のアルゴリズムで要求されるより500倍少ないクエリをfに使用する。
  論文  参考訳（メタデータ） (2021-04-19T17:22:11Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)
• Complex Query Answering with Neural Link Predictors [13.872400132315988]
  不完全な知識グラフ上で複雑なクエリを効率的に応答するフレームワークを提案する。 我々は、各クエリをエンドツーエンドの微分可能な目的に翻訳し、各原子の真理値が事前学習されたニューラルネットワーク予測器によって計算される。 実験では,提案手法は最先端手法よりも精度の高い結果が得られる。
  論文  参考訳（メタデータ） (2020-11-06T16:20:49Z)
• Generalized and Scalable Optimal Sparse Decision Trees [56.35541305670828]
  様々な目的に対して最適な決定木を生成する手法を提案する。 また,連続変数が存在する場合に最適な結果が得られるスケーラブルなアルゴリズムも導入する。
  論文  参考訳（メタデータ） (2020-06-15T19:00:11Z)
• Gumbel-softmax-based Optimization: A Simple General Framework for Optimization Problems on Graphs [5.486093983007419]
  本稿では,ディープラーニングフレームワークによって強化された高度な自動微分技術に基づく,シンプルで高速で汎用的なアルゴリズムフレームワークを提案する。 高品質なソリューションは、従来のアプローチに比べてはるかに少ない時間で得られる。
  論文  参考訳（メタデータ） (2020-04-14T14:11:00Z)

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

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