論文の概要: Statistical limits of correlation detection in trees
- arxiv url: http://arxiv.org/abs/2209.13723v1
- Date: Tue, 27 Sep 2022 22:26:53 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-29 18:16:36.222035
- Title: Statistical limits of correlation detection in trees
- Title（参考訳）: 樹木における相関検出の統計的限界
- Authors: Luca Ganassali, Laurent Massouli\'e, Guilhem Semerjian
- Abstract要約: 本稿では,2つの観測木$(t,t')$が独立に,あるいは相関関係のある関節分布から標本化されるかどうかを検証する。
グラフアライメントにより,片側テストの存在条件について検討する。
このようなテストは$s leq sqrtalpha$に対して存在せず、そのようなテストは$s > sqrtalpha$, for $lambda$十分に大きいときに存在します。
- 参考スコア（独自算出の注目度）: 1.4180331276028662
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper we address the problem of testing whether two observed trees
$(t,t')$ are sampled either independently or from a joint distribution under
which they are correlated.
This problem, which we refer to as correlation detection in trees, plays a
key role in the study of graph alignment for two correlated random graphs.
Motivated by graph alignment, we investigate the conditions of existence of
one-sided tests, i.e. tests which have vanishing type I error and non-vanishing
power in the limit of large tree depth.
For the correlated Galton-Watson model with Poisson offspring of mean
$\lambda>0$ and correlation parameter $s \in (0,1)$, we identify a phase
transition in the limit of large degrees at $s = \sqrt{\alpha}$, where $\alpha
\sim 0.3383$ is Otter's constant. Namely, we prove that no such test exists for
$s \leq \sqrt{\alpha}$, and that such a test exists whenever $s >
\sqrt{\alpha}$, for $\lambda$ large enough.
This result sheds new light on the graph alignment problem in the sparse
regime (with $O(1)$ average node degrees) and on the performance of the MPAlign
method studied in Ganassali et al. (2021), Piccioli et al. (2021), proving in
particular the conjecture of Piccioli et al. (2021) that MPAlign succeeds in
the partial recovery task for correlation parameter $s>\sqrt{\alpha}$ provided
the average node degree $\lambda$ is large enough.
- Abstract（参考訳）: 本稿では、2つの観測された木$(t,t')$が独立に、あるいは相関関係にある関節分布からサンプリングされるかどうかをテストする問題に対処する。
この問題は木における相関検出と呼ばれ、2つの相関ランダムグラフに対するグラフアライメントの研究において重要な役割を果たしている。
グラフアライメントによってモチベーションされた片側テスト,すなわち,木深の限界におけるI型誤差と非消滅力を有するテストの存在条件について検討する。
平均 $\lambda>0$ と相関パラメータ $s \in (0,1)$ のポアソン子と相関したガルトン・ワットソンモデルに対して、大きな次数制限の位相遷移を $s = \sqrt{\alpha}$ で同定する。
すなわち、そのようなテストが$s \leq \sqrt{\alpha}$ に対して存在せず、$s > \sqrt{\alpha}$, for $\lambda$ が十分大きいとき、そのようなテストが存在することが証明される。
この結果はスパース系におけるグラフアライメント問題(平均ノード次数$O(1))と、ガナサリら(2021年)、ピッコリら(2021年)で研究されたMPAlign法の性能に新たな光を当て、特に相関パラメータ$s>\sqrt{\alpha}$の平均ノード次数$\lambda$が十分大きいことを証明するPiccioli et al.(2021年)の予想を証明した。
関連論文リスト
- 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) - Kernelized Normalizing Constant Estimation: Bridging Bayesian Quadrature
and Bayesian Optimization [51.533164528799084]
小さい相対誤差内で正規化定数を推定するために、難易度は$lambda$の値に依存する。
関数評価がノイズである場合でも,このパターンは真であることがわかった。
論文 参考訳（メタデータ） (2024-01-11T07:45:09Z) - 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) - 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) - Causal Bandits for Linear Structural Equation Models [58.2875460517691]
本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。
グラフの構造は知られており、ノードは$N$である。
頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-26T16:21:31Z) - A Law of Robustness beyond Isoperimetry [84.33752026418045]
我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。
次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。
我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
論文 参考訳（メタデータ） (2022-02-23T16:10:23Z) - Testing network correlation efficiently via counting trees [19.165942326142538]
本稿では,2つのネットワークがエッジ関連であるかどうかを潜時対応によって検証する新しい手法を提案する。
テスト統計は、非同型木族に対する符号付き木の共起を数えることに基づいている。
論文 参考訳（メタデータ） (2021-10-22T14:47:20Z) - Inferring Hidden Structures in Random Graphs [13.031167737538881]
本研究では,ランダムなグラフ上に植えられた群集群集の検出と復元の2つの推論問題について検討する。
我々は、パラメータ $(n,k,q)$ や $Gamma_k$ の特定の性質の観点から、構造を検出・復元するための下限を導出し、これらの下限を達成するための計算学的に最適なアルゴリズムを示す。
論文 参考訳（メタデータ） (2021-10-05T09:39:51Z) - Correlation detection in trees for partial graph alignment [3.5880535198436156]
グラフのアライメントは,エッジの大部分を保存する2つのグラフのノード間のマッピングを探索する。
我々のアプローチは、2つのグラフの局所構造を比較し、その近傍が相関グラフに対して「十分近い」場合、2つのノードをマッチングすることである。
この問題は、一対の分岐木が積分布または相関分布から引き出されるかどうかの検定の観点から説明できる。
論文 参考訳（メタデータ） (2021-07-15T22:02:27Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。