論文の概要: Limited Query Graph Connectivity Test

• arxiv url: http://arxiv.org/abs/2302.13036v2
• Date: Wed, 16 Aug 2023 11:53:48 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-17 17:33:00.308717
• Title: Limited Query Graph Connectivity Test
• Title（参考訳）: 限定クエリグラフ接続性テスト
• Authors: Mingyu Guo, Jialiang Li, Aneta Neumann, Frank Neumann, Hung Nguyen
• Abstract要約: エッジが2つの可能な状態(On/Off)を持つグラフを考える。 我々は,経路(オンエッジのみの構成)とカット(オフエッジのみ構成)を識別し,s-t接続性をテストすることを目指している。 我々のモデルは主に、ネットワーク内に攻撃経路が存在するかどうかを確かめる必要があるサイバーセキュリティユースケースによって動機付けられている。
• 参考スコア（独自算出の注目度）: 14.108454811023465
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a combinatorial optimisation model called Limited Query Graph Connectivity Test. We consider a graph whose edges have two possible states (On/Off). The edges' states are hidden initially. We could query an edge to reveal its state. Given a source s and a destination t, we aim to test s-t connectivity by identifying either a path (consisting of only On edges) or a cut (consisting of only Off edges). We are limited to B queries, after which we stop regardless of whether graph connectivity is established. We aim to design a query policy that minimizes the expected number of queries. Our model is mainly motivated by a cyber security use case where we need to establish whether an attack path exists in a network, between a source and a destination. Edge query is resolved by manual effort from the IT admin, which is the motivation behind query minimization. Our model is highly related to monotone Stochastic Boolean Function Evaluation (SBFE). There are two existing exact algorithms for SBFE that are prohibitively expensive. We propose a significantly more scalable exact algorithm. While previous exact algorithms only scale for trivial graphs (i.e., past works experimented on at most 20 edges), we empirically demonstrate that our algorithm is scalable for a wide range of much larger practical graphs (i.e., Windows domain network graphs with tens of thousands of edges). We propose three heuristics. Our best-performing heuristic is via reducing the search horizon of the exact algorithm. The other two are via reinforcement learning (RL) and Monte Carlo tree search (MCTS). We also derive an anytime algorithm for computing the performance lower bound. Experimentally, we show that all our heuristics are near optimal. The exact algorithm based heuristic outperforms all, surpassing RL, MCTS and 8 existing heuristics ported from SBFE and related literature.
• Abstract（参考訳）: 本稿では,限定クエリグラフ接続テストと呼ばれる組合せ最適化モデルを提案する。 エッジが2つの可能な状態(On/Off)を持つグラフを考える。 エッジの状態は最初に隠れている。 エッジをクエリしてその状態を明らかにすることができます。 ソースsと宛先tが与えられた場合、経路(オンエッジのみ)とカット(オフエッジのみ)を識別してs-t接続をテストする。 グラフ接続が確立されたかどうかに関わらず、Bクエリに制限されています。 期待されるクエリ数を最小化するクエリポリシーを設計することを目指している。 我々のモデルは、主にサイバーセキュリティのユースケースに動機付けられており、攻撃経路がネットワーク内、つまりソースと宛先の間に存在するかどうかを確立する必要がある。 エッジクエリは、クエリ最小化の背後にあるモチベーションであるIT管理者の手作業によって解決される。 本モデルはSBFE (monotone Stochastic Boolean Function Evaluation) と密接に関連している。 SBFEには、違法に高価である2つの正確なアルゴリズムがある。 我々はよりスケーラブルな完全アルゴリズムを提案する。 従来の正確なアルゴリズムは、自明なグラフ(つまり、少なくとも20のエッジで実験された過去の作業)に対してのみスケールするが、我々のアルゴリズムは、より広い範囲の実用的なグラフ(例えば、数万のエッジを持つWindowsドメインネットワークグラフ)に対してスケーラブルであることを実証的に実証する。 我々は3つのヒューリスティックを提案する。 我々の最も優れたヒューリスティックは、正確なアルゴリズムの探索地平線を減らすことである。 他の2つは強化学習(RL)とモンテカルロ木探索(MCTS)である。 また,性能下限を計算するためのanytimeアルゴリズムも導出する。 実験では、全てのヒューリスティックがほぼ最適であることを示す。 正確なアルゴリズムに基づくヒューリスティックは、SBFEと関連する文献から移植されたRL、MCTS、および8つの既存のヒューリスティックを上回っている。

関連論文リスト

• Learning-Based Algorithms for Graph Searching Problems [6.923787372512553]
  本稿では,Banerjeeらによって最近導入された予測付きグラフ探索の問題点について考察する。 この問題では、ある$r$から始まるエージェントは、隠れたゴールノード$g$を見つけるために、(潜在的に未知の)グラフ$G$をトラバースしなければならない。 我々は未知のグラフ上でこの探索タスクのアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2024-02-27T18:12:58Z)
• Learnable Graph Matching: A Practical Paradigm for Data Association [74.28753343714858]
  これらの問題に対処するための一般的な学習可能なグラフマッチング法を提案する。 提案手法は,複数のMOTデータセット上での最先端性能を実現する。 画像マッチングでは,一般的な屋内データセットであるScanNetで最先端の手法より優れている。
  論文  参考訳（メタデータ） (2023-03-27T17:39:00Z)
• 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)
• Arch-Graph: Acyclic Architecture Relation Predictor for Task-Transferable Neural Architecture Search [96.31315520244605]
  Arch-Graphはタスク固有の最適アーキテクチャを予測するトランスファー可能なNASメソッドである。 Arch-Graphの転送性と,多数のタスクにわたる高いサンプル効率を示す。 わずか50モデルの予算の下で、2つの検索スペースで平均して0.16%と0.29%のアーキテクチャを見つけることができる。
  論文  参考訳（メタデータ） (2022-04-12T16:46:06Z)
• Random Subgraph Detection Using Queries [29.192695995340653]
  植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。 本稿では,適応的なエッジクエリを用いてグラフの比較的小さな部分のみを観測できる,上記の問題の自然な変形について考察する。 このモデルでは,植込み部分グラフの存在を検出するのに必要なクエリ数と十分なクエリ数(準多項式最適アルゴリズムを伴う)を決定する。
  論文  参考訳（メタデータ） (2021-10-02T07:41:17Z)
• Classical algorithms and quantum limitations for maximum cut on high-girth graphs [6.262125516926276]
  すべての(量子または古典的な)一局所アルゴリズムが$D$正規グラフに対して$5$の最大カットが1/2 + C/sqrtD$ for $C=1/sqrt2 approx 0.7071$であることを示す。 1/2 + C/sqrtD - O (1/sqrtk)$ for $D$-regular graphs of $> 2k+1$,
  論文  参考訳（メタデータ） (2021-06-10T16:28:23Z)
• 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)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。 我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
  論文  参考訳（メタデータ） (2020-08-29T14:58:26Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis [7.99536002595393]
  本稿では,ネットワーク上あるいはそのモラル化されたグラフ上に制約を加える際に,最適なベイズネットワークの構造を学習する問題について検討する。 モラル化されたグラフに少なくとも$k$のエッジを持つ最適ネットワークを学習すると、おそらく$f(k)cdot |I|O(1)$-timeアルゴリズムが存在しない。
  論文  参考訳（メタデータ） (2020-04-30T12:31:13Z)

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

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