論文の概要: Limited Query Graph Connectivity Test
- arxiv url: http://arxiv.org/abs/2302.13036v1
- Date: Sat, 25 Feb 2023 09:27:02 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-28 19:15:30.503978
- Title: Limited Query Graph Connectivity Test
- Title（参考訳）: 限定クエリグラフ接続性テスト
- Authors: Mingyu Guo, Jialiang Li, Aneta Neumann, Frank Neumann, Hung Nguyen
- Abstract要約: エッジが2つの可能な状態(オン/オフ)を持つグラフを考える。
我々は,経路(エッジのみの構成)と切断(オフエッジのみの構成)を識別し,s-t接続性をテストすることを目指している。
- 参考スコア（独自算出の注目度）: 16.14044774445305
- 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.
If we remove the query limit B (i.e., by setting B to the total number of
edges), then our problem becomes a special case of (monotone) Stochastic
Boolean Function Evaluation (SBFE). There are two existing exact algorithms
that are prohibitively expensive. They have best known upper bounds of O(3^m)
and O(2^{2^k}) respectively, where m is the number of edges and k is the number
of paths/cuts. These algorithms do not scale well in practice.
We propose a significantly more scalable exact algorithm. Our exact algorithm
works by iteratively improving the performance lower bound until the lower
bound becomes achievable. Even when our exact algorithm does not scale, it can
be used as an anytime algorithm for calculating lower bound.
We experiment on a wide range of practical graphs. We observe that even for
large graphs (i.e., tens of thousands of edges), it mostly takes only a few
queries to reach conclusion, which is the practical motivation behind the query
limit B. B is also an algorithm parameter that controls scalability. For small
B, our exact algorithm scales well. For large B, our exact algorithm can be
converted to a heuristic (i.e., always pretend that there are only 5 queries
left). Our heuristic outperforms all existing heuristics ported from SBFE and
related literature.
- Abstract（参考訳）: 本稿では,限定クエリグラフ接続テストと呼ばれる組合せ最適化モデルを提案する。
エッジが2つの可能な状態(オン/オフ)を持つグラフを考える。
エッジの状態は最初に隠れている。
エッジをクエリしてその状態を明らかにすることができます。
ソース s と宛先 t が与えられた場合、経路(エッジのみからなる)と切断(オフエッジのみからなる)を識別することにより、s-t 接続性をテストする。
グラフ接続が確立されたかどうかに関わらず、Bクエリに制限されています。
期待されるクエリ数を最小化するクエリポリシーを設計することを目指している。
クエリ制限b(つまり、bをエッジの総数に設定することで)を削除すると、この問題は(単調)確率的ブール関数評価(sbfe)の特別な場合となる。
非常に高価なアルゴリズムが2つ存在する。
それらはそれぞれ O(3^m) と O(2^{2^k}) の上限としてよく知られており、m は辺の数、k は経路/切断の数である。
これらのアルゴリズムは実際にはうまくスケールしない。
我々はよりスケーラブルな完全アルゴリズムを提案する。
我々の正確なアルゴリズムは、下限が達成可能になるまで、性能下限を反復的に改善する。
正確なアルゴリズムがスケールしない場合でも、低境界を計算するための任意の時間アルゴリズムとして使用できる。
我々は多種多様な実用グラフを実験する。
大規模なグラフ(例えば数万のエッジ)であっても、結論に達するのにクエリはごくわずかであり、これはクエリ制限Bの背後にある実践的なモチベーションである。
小さなBの場合、我々の正確なアルゴリズムはうまくスケールする。
大きなBの場合、我々の正確なアルゴリズムはヒューリスティックに変換できる(つまり、常に5つのクエリしか残っていないふりをする)。
我々のヒューリスティックは、SBFEと関連する文献から移植された既存のヒューリスティックよりも優れています。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。