論文の概要: Learning-Based Algorithms for Graph Searching Problems

• arxiv url: http://arxiv.org/abs/2402.17736v1
• Date: Tue, 27 Feb 2024 18:12:58 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-28 15:06:48.581532
• Title: Learning-Based Algorithms for Graph Searching Problems
• Title（参考訳）: グラフ探索問題に対する学習アルゴリズム
• Authors: Adela Frances DePavia, Erasmo Tani, Ali Vakilian
• Abstract要約: 本稿では,Banerjeeらによって最近導入された予測付きグラフ探索の問題点について考察する。 この問題では、ある$r$から始まるエージェントは、隠れたゴールノード$g$を見つけるために、(潜在的に未知の)グラフ$G$をトラバースしなければならない。 我々は未知のグラフ上でこの探索タスクのアルゴリズムを設計する。
• 参考スコア（独自算出の注目度）: 7.781643140249867
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of graph searching with prediction recently introduced by Banerjee et al. (2022). In this problem, an agent, starting at some vertex $r$ has to traverse a (potentially unknown) graph $G$ to find a hidden goal node $g$ while minimizing the total distance travelled. We study a setting in which at any node $v$, the agent receives a noisy estimate of the distance from $v$ to $g$. We design algorithms for this search task on unknown graphs. We establish the first formal guarantees on unknown weighted graphs and provide lower bounds showing that the algorithms we propose have optimal or nearly-optimal dependence on the prediction error. Further, we perform numerical experiments demonstrating that in addition to being robust to adversarial error, our algorithms perform well in typical instances in which the error is stochastic. Finally, we provide alternative simpler performance bounds on the algorithms of Banerjee et al. (2022) for the case of searching on a known graph, and establish new lower bounds for this setting.
• Abstract（参考訳）: banerjee et al. (2022) が最近導入した予測によるグラフ探索の問題を考える。 この問題では、ある頂点 $r$ から始まるエージェントは(潜在的に未知の)グラフ $g$ をトラバースして隠れたゴールノード $g$ を探しながら、移動距離を最小化する必要がある。 我々は、任意のノード $v$ において、エージェントが$v$ から $g$ までのノイズの多い距離の見積もりを受ける設定について検討する。 我々は未知のグラフ上でこの探索タスクのアルゴリズムを設計する。 未知重み付きグラフに対する最初の形式的保証を確立し,提案するアルゴリズムが予測誤差に最適あるいはほぼ最適に依存することを示す下限を与える。 さらに, 逆誤差に対して頑健であるだけでなく, 誤差が確率的な典型例においても, アルゴリズムが良好に動作することを示す数値実験を行った。 最後に、既知のグラフを探索する場合に、 Banerjee et al. (2022) のアルゴリズムの代替的なより単純な性能境界を提供し、この設定に対して新しい下界を確立する。

関連論文リスト

• A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph [51.880164098926166]
  グラフベースのアルゴリズムは、近隣探索(NN-Search)問題において最先端の性能を示す。 グラフベースのNN-Searchアルゴリズムには実践と理論のギャップがある。 低次元および高密度ベクトルに対する ANN-Graph 上の欲求探索による NN-Search の解法を理論的に保証する。
  論文  参考訳（メタデータ） (2023-03-10T21:18:34Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• Causal Bandits without Graph Learning [28.021500949026766]
  我々は,原子間干渉を用いた報酬ノードの親ノード探索のための効率的なアルゴリズムを開発した。 報奨ノードが複数の親を持つ場合にアルゴリズムを拡張します。
  論文  参考訳（メタデータ） (2023-01-26T20:27:14Z)
• Linear-Time Algorithms for Front-Door Adjustment in Causal Graphs [3.707290781951909]
  観測データから因果効果を推定することは経験科学の基本的な課題である。 本論文は, 観測媒介者を用いて, 保存されていない共同設立者の存在下においても, 因果関係を識別できる古典的な手法である, 正面調整に焦点を当てたものである。
  論文  参考訳（メタデータ） (2022-11-29T18:44:03Z)
• Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
  グラフ上の連続時間量子ウォークに着目したGroverの探索アルゴリズムについて検討する。 関連する量子ウォークに便利なグラフトポロジーを見つける代わりに、グラフトポロジーを修正し、ラプラシアンを基礎とするグラフを変化させる。
  論文  参考訳（メタデータ） (2022-07-04T19:33:06Z)
• Verification and search algorithms for causal DAGs [11.038866111306728]
  クレーム因果グラフの正しさを確認するために、最小サイズの原子介入のセットを特徴づける。 我々は,ノード依存の介入コストと境界サイズ介入の設定に対して,その結果を一般化する。 この結果は、一般の未重み付きグラフ上での検証サイズに対する非自明な近似を保証する最初のアルゴリズムである。
  論文  参考訳（メタデータ） (2022-06-30T15:52:30Z)
• Random Subgraph Detection Using Queries [29.192695995340653]
  植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。 本稿では,適応的なエッジクエリを用いてグラフの比較的小さな部分のみを観測できる,上記の問題の自然な変形について考察する。 このモデルでは,植込み部分グラフの存在を検出するのに必要なクエリ数と十分なクエリ数(準多項式最適アルゴリズムを伴う)を決定する。
  論文  参考訳（メタデータ） (2021-10-02T07:41:17Z)
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations [80.95090605985042]
  学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。 エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。 textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
  論文  参考訳（メタデータ） (2020-12-10T15:40:07Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  実世界の多くのアプリケーションにおいて古典的なグラフ解析問題であるグラフリンク予測タスクについて検討する。 このフォーマリズムでは、リンク予測問題をグラフ分類タスクに変換する。 本稿では,線グラフをグラフ理論に用いて,根本的に異なる新しい経路を求めることを提案する。 特に、線グラフの各ノードは、元のグラフのユニークなエッジに対応するため、元のグラフのリンク予測問題は、グラフ分類タスクではなく、対応する線グラフのノード分類問題として等価に解決できる。
  論文  参考訳（メタデータ） (2020-10-20T05:54:31Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)

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

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