論文の概要: Random Subgraph Detection Using Queries
- arxiv url: http://arxiv.org/abs/2110.00744v2
- Date: Tue, 5 Oct 2021 08:07:27 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-06 10:47:28.848878
- Title: Random Subgraph Detection Using Queries
- Title（参考訳）: クエリを用いたランダムサブグラフ検出
- Authors: Wasim Huleihel and Arya Mazumdar and Soumyabrata Pal
- Abstract要約: 植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。
任意の(おそらくランダム化される)アルゴリズムは、$mathsfQ = Omega(fracn2k2chi4(p||q)log2n)$アダプティブクエリを生成する必要がある。
次に、$mathsfQ = O(fracn4)を用いて植木部分グラフを検出できる準多項式時間アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 56.96625809888241
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The planted densest subgraph detection problem refers to the task of testing
whether in a given (random) graph there is a subgraph that is unusually dense.
Specifically, we observe an undirected and unweighted graph on $n$ nodes. Under
the null hypothesis, the graph is a realization of an Erd\H{o}s-R\'{e}nyi graph
with edge probability (or, density) $q$. Under the alternative, there is a
subgraph on $k$ vertices with edge probability $p>q$. The statistical as well
as the computational barriers of this problem are well-understood for a wide
range of the edge parameters $p$ and $q$. In this paper, we consider a natural
variant of the above problem, where one can only observe a small part of the
graph using adaptive edge queries.
For this model, we determine the number of queries necessary and sufficient
for detecting the presence of the planted subgraph. Specifically, we show that
any (possibly randomized) algorithm must make $\mathsf{Q} =
\Omega(\frac{n^2}{k^2\chi^4(p||q)}\log^2n)$ adaptive queries (on expectation)
to the adjacency matrix of the graph to detect the planted subgraph with
probability more than $1/2$, where $\chi^2(p||q)$ is the Chi-Square distance.
On the other hand, we devise a quasi-polynomial-time algorithm that finds the
planted subgraph with high probability by making $\mathsf{Q} =
O(\frac{n^2}{k^2\chi^4(p||q)}\log^2n)$ adaptive queries. We then propose a
polynomial-time algorithm which is able to detect the planted subgraph using
$\mathsf{Q} = O(\frac{n^4}{k^4\chi^2(p||q)}\log n)$ queries. We conjecture that
in the leftover regime, where $\frac{n^2}{k^2}\ll\mathsf{Q}\ll
\frac{n^4}{k^4}$, no polynomial-time algorithms exist; we give an evidence for
this hypothesis using the planted clique conjecture. Our results resolve three
questions posed in \cite{racz2020finding}, where the special case of adaptive
detection and recovery of a planted clique was considered.
- Abstract（参考訳）: 植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。
具体的には、$n$ノード上の非方向および非重み付きグラフを観察します。
ヌル仮説の下で、グラフは erd\h{o}s-r\'{e}nyi グラフのエッジ確率(または密度) $q$ による実現である。
代替案として、k$頂点にエッジ確率$p>q$のサブグラフがある。
この問題の統計的および計算的障壁は、広範囲のエッジパラメーター $p$ と $q$ についてよく理解されている。
本稿では,適応的なエッジクエリを用いて,グラフのごく一部しか観測できない,上記の問題の自然な変形について考察する。
そこで,本モデルでは,植込みされたサブグラフの存在を検出するのに必要なクエリ数が決定される。
具体的には、任意の(確率的にランダム化された)アルゴリズムは、$\mathsf{Q} = \Omega(\frac{n^2}{k^2\chi^4(p||q)}\log^2n)$のグラフの隣接行列への適応的クエリを1/2$以上の確率で検出し、$\chi^2(p||q)$がChi-Square距離であることを示す。
一方,準多項時間アルゴリズムを考案し,$\mathsf{q} = o(\frac{n^2}{k^2\chi^4(p||q)}\log^2n)$適応クエリを用いて,高い確率で植込み部分グラフを求める。
次に,$\mathsf{q} = o(\frac{n^4}{k^4\chi^2(p||q)}\log n)$クエリを用いて植込み部分グラフを検出する多項式時間アルゴリズムを提案する。
我々は、$\frac{n^2}{k^2}\ll\mathsf{Q}\ll \frac{n^4}{k^4}$の場合、多項式時間アルゴリズムは存在しないと推測する。
本研究は, 植樹されたクランクを適応的に検出し, 回収する特別のケースを考慮し, 以下の3つの疑問を解決した。
関連論文リスト
- Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。
我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。
平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
論文 参考訳（メタデータ） (2023-04-17T10:38:08Z) - On the Unlikelihood of D-Separation [69.62839677485087]
解析的な証拠として、大きなグラフ上では、d-分離は存在が保証されたとしても珍しい現象である。
PCアルゴリズムでは、その最悪ケース保証がスパースグラフで失敗することが知られているが、平均ケースでも同じことが言える。
UniformSGSでは、既存のエッジに対してランニング時間が指数的であることが知られているが、平均的な場合、それは既存のほとんどのエッジにおいても期待されるランニング時間であることを示す。
論文 参考訳（メタデータ） (2023-03-10T00:11:18Z) - Planted Bipartite Graph Detection [13.95780443241133]
ランダムグラフに隠れた二部グラフを検出するタスクについて検討する。
ヌル仮説の下では、このグラフは、エッジ密度$q$の$n$上のアードホスラーイランダムグラフの実現である。
k_mathsfR times k_mathsfL$ bipartite subgraph with edge density $p>q$。
論文 参考訳（メタデータ） (2023-02-07T18:18:17Z) - Improved High-Probability Regret for Adversarial Bandits with
Time-Varying Feedback Graphs [62.52390282012508]
我々は、T$ラウンド以上の時間変化フィードバックグラフを持つ、敵対的な$K$武器付きバンディットに対する高い確率的後悔境界について検討する。
提案アルゴリズムは,高い確率で最適に後悔する$widetildemathcalO((sum_t=1Talpha_t)1/2+max_tin[T]alpha_t]$を達成するアルゴリズムを開発した。
また,弱可観測グラフに対する最適高確率残差を求めるアルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-10-04T04:36:15Z) - Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using
Graph-based Machine Learning [1.52292571922932]
本稿では,グラフニューラルネットワークに基づくアルゴリズムであるPYGONについて述べる。
我々はPYGONが$Thetaleft(sqrtnright)$を復元できることを示し、$n$は背景グラフのサイズである。
また、同じアルゴリズムで、$Thetaleft(sqrtnright)$の複数の植字されたサブグラフを、有向および無向の両方で復元できることを示す。
論文 参考訳（メタデータ） (2022-01-05T21:11:23Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - Inferring Hidden Structures in Random Graphs [13.031167737538881]
本研究では,ランダムなグラフ上に植えられた群集群集の検出と復元の2つの推論問題について検討する。
我々は、パラメータ $(n,k,q)$ や $Gamma_k$ の特定の性質の観点から、構造を検出・復元するための下限を導出し、これらの下限を達成するための計算学的に最適なアルゴリズムを示す。
論文 参考訳（メタデータ） (2021-10-05T09:39:51Z) - Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov
Random Fields [51.07460861448716]
本稿では,データから学ぶための凸解析フレームワークを提案する。
三角凸分解はその上部に対応する変換によって保証されることを示す。
論文 参考訳（メタデータ） (2021-09-17T17:46:12Z) - The Generalized Mean Densest Subgraph Problem [30.33731479053404]
1つのパラメータ$p$でパラメータ化された、高密度なサブグラフ対象の新しいファミリーを導入する。
我々の目的は、標準の高密度部分グラフ問題と特別な場合の最大$k$-coreの両方をキャプチャする。
我々の研究の大きな貢献は、理論と実践の両方において、密接な部分グラフに対する様々な種類の剥離アルゴリズムの性能を分析することである。
論文 参考訳（メタデータ） (2021-06-02T02:58:35Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。