論文の概要: Planted Bipartite Graph Detection

• arxiv url: http://arxiv.org/abs/2302.03658v2
• Date: Wed, 6 Mar 2024 08:30:48 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-07 18:31:37.636173
• Title: Planted Bipartite Graph Detection
• Title（参考訳）: 植込み二部グラフ検出
• Authors: Asaf Rotenberg and Wasim Huleihel and Ofer Shayevitz
• Abstract要約: ランダムグラフに隠れた二部グラフを検出するタスクについて検討する。 ヌル仮説の下では、このグラフは、エッジ密度$q$の$n$上のアードホスラーイランダムグラフの実現である。 k_mathsfR times k_mathsfL$ bipartite subgraph with edge density $p>q$。
• 参考スコア（独自算出の注目度）: 13.95780443241133
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the task of detecting a hidden bipartite subgraph in a given random graph. This is formulated as a hypothesis testing problem, under the null hypothesis, the graph is a realization of an Erd\H{o}s-R\'{e}nyi random graph over $n$ vertices with edge density $q$. Under the alternative, there exists a planted $k_{\mathsf{R}} \times k_{\mathsf{L}}$ bipartite subgraph with edge density $p>q$. We characterize the statistical and computational barriers for this problem. Specifically, we derive information-theoretic lower bounds, and design and analyze optimal algorithms matching those bounds, in both the dense regime, where $p,q = \Theta\left(1\right)$, and the sparse regime where $p,q = \Theta\left(n^{-\alpha}\right), \alpha \in \left(0,2\right]$. We also consider the problem of testing in polynomial-time. As is customary in similar structured high-dimensional problems, our model undergoes an "easy-hard-impossible" phase transition and computational constraints penalize the statistical performance. To provide an evidence for this statistical computational gap, we prove computational lower bounds based on the low-degree conjecture, and show that the class of low-degree polynomials algorithms fail in the conjecturally hard region.
• Abstract（参考訳）: ランダムグラフに隠れた二部グラフを検出するタスクについて検討する。 これは仮説テスト問題として定式化され、ヌル仮説の下では、グラフは辺密度$q$の$n$頂点上のErd\H{o}s-R\'{e}nyiランダムグラフの実現である。 代替として、k_{\mathsf{r}} \times k_{\mathsf{l}}$ bipartite subgraph with edge density $p>q$がある。 この問題の統計的および計算的障壁を特徴づける。 具体的には、情報理論的な下界を導出し、それらの境界に一致する最適なアルゴリズムを設計し分析する。例えば、$p,q = \Theta\left(1\right)$ と、$p,q = \Theta\left(n^{-\alpha}\right), \alpha \in \left(0,2\right]$ のスパース状態である。 また,多項式時間におけるテストの問題についても検討する。 類似した構造化高次元問題における慣例と同様に、このモデルでは「容易に不可能」な位相遷移と計算制約が統計性能をペナルティ化する。 この統計計算ギャップの証拠を提供するために, 低次予想に基づく計算下限を証明し, 低次多項式アルゴリズムのクラスは, 仮定的に難しい領域では失敗することを示す。

関連論文リスト

• A computational transition for detecting correlated stochastic block models by low-degree polynomials [13.396246336911842]
  一対のランダムグラフにおける相関性の検出は、近年広く研究されている基本的な統計的および計算上の問題である。 一対の相関ブロックモデル $mathcalS(n,tfraclambdan;k,epsilon;s)$ を共通の親ブロックモデル $mathcalS(n,tfraclambdan;k,epsilon;s)$ からサブサンプリングする。 隣接部のエントリーのエンスロー度に基づくテストに焦点をあてる
  論文  参考訳（メタデータ） (2024-09-02T06:14:05Z)
• 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)
• Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
  期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。 低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
  論文  参考訳（メタデータ） (2023-02-13T22:51:07Z)
• Statistical limits of correlation detection in trees [0.7826806223782055]
  本稿では,2本の観測木$(t,t')$が独立に標本化されているか,あるいは相関関係のある関節分布から採取されているかを調べる。 グラフアライメントにより,片側テストの存在条件について検討する。 このようなテストは$s leq sqrtalpha$に対して存在せず、そのようなテストは$s > sqrtalpha$, for $lambda$十分に大きいときに存在します。
  論文  参考訳（メタデータ） (2022-09-27T22:26:53Z)
• Causal Bandits for Linear Structural Equation Models [58.2875460517691]
  本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。 グラフの構造は知られており、ノードは$N$である。 頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-26T16:21:31Z)
• Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity [121.83085611327654]
  積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。 エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。 提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
  論文  参考訳（メタデータ） (2022-05-30T14:28:02Z)
• 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)
• Random Subgraph Detection Using Queries [29.192695995340653]
  植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。 本稿では,適応的なエッジクエリを用いてグラフの比較的小さな部分のみを観測できる,上記の問題の自然な変形について考察する。 このモデルでは,植込み部分グラフの存在を検出するのに必要なクエリ数と十分なクエリ数(準多項式最適アルゴリズムを伴う)を決定する。
  論文  参考訳（メタデータ） (2021-10-02T07:41:17Z)
• Testing correlation of unlabeled random graphs [18.08210501570919]
  ラベルなしノードを持つ2つのランダムグラフ間のエッジ相関を検出する問題について検討する。 これは仮説テスト問題として定式化され、ヌル仮説の下では、2つのグラフは独立に生成される。 代替として、2つのグラフは、ある潜在ノード対応の下ではエッジ関連であるが、ヌルと同じ辺分布を持つ。
  論文  参考訳（メタデータ） (2020-08-23T19:19:45Z)
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
  非コンミニマックス問題、$min_mathbfx max_mathhidoty f(mathbfdoty)$を効率的に考える。
  論文  参考訳（メタデータ） (2019-06-02T03:03:45Z)

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

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