論文の概要: Testing correlation of unlabeled random graphs
- arxiv url: http://arxiv.org/abs/2008.10097v2
- Date: Mon, 8 Feb 2021 01:57:36 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-26 03:22:12.336426
- Title: Testing correlation of unlabeled random graphs
- Title（参考訳）: ラベルなしランダムグラフの検定相関
- Authors: Yihong Wu, Jiaming Xu, Sophie H. Yu
- Abstract要約: ラベルなしノードを持つ2つのランダムグラフ間のエッジ相関を検出する問題について検討する。
これは仮説テスト問題として定式化され、ヌル仮説の下では、2つのグラフは独立に生成される。
代替として、2つのグラフは、ある潜在ノード対応の下ではエッジ関連であるが、ヌルと同じ辺分布を持つ。
- 参考スコア（独自算出の注目度）: 18.08210501570919
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of detecting the edge correlation between two random
graphs with $n$ unlabeled nodes. This is formalized as a hypothesis testing
problem, where under the null hypothesis, the two graphs are independently
generated; under the alternative, the two graphs are edge-correlated under some
latent node correspondence, but have the same marginal distributions as the
null. For both Gaussian-weighted complete graphs and dense Erd\H{o}s-R\'enyi
graphs (with edge probability $n^{-o(1)}$), we determine the sharp threshold at
which the optimal testing error probability exhibits a phase transition from
zero to one as $n\to \infty$. For sparse Erd\H{o}s-R\'enyi graphs with edge
probability $n^{-\Omega(1)}$, we determine the threshold within a constant
factor.
The proof of the impossibility results is an application of the conditional
second-moment method, where we bound the truncated second moment of the
likelihood ratio by carefully conditioning on the typical behavior of the
intersection graph (consisting of edges in both observed graphs) and taking
into account the cycle structure of the induced random permutation on the
edges. Notably, in the sparse regime, this is accomplished by leveraging the
pseudoforest structure of subcritical Erd\H{o}s-R\'enyi graphs and a careful
enumeration of subpseudoforests that can be assembled from short orbits of the
edge permutation.
- Abstract（参考訳）: ラベルなしノードを持つ2つのランダムグラフ間のエッジ相関を検出する問題について検討する。
これは仮説テスト問題として定式化され、ヌル仮説の下では、2つのグラフは独立に生成される。
ガウス重み付き完備グラフと密度の強いエルド・H{o}s-R\enyiグラフ(辺確率$n^{-o(1)}$)に対して、最適試験誤差確率が0から1への位相遷移を示すシャープしきい値を$n\to \infty$として決定する。
辺確率 $n^{-\Omega(1)}$ のスパース Erd\H{o}s-R\'enyi グラフに対して、定数係数内のしきい値を決定する。
この結果の証明は条件付き第2モーメント法の適用であり、交叉グラフの典型的な挙動(観測されたグラフの両辺の結合)を慎重に条件付けし、その辺における誘導されたランダムな置換のサイクル構造を考慮し、確率比の断続した第2モーメントを拘束する。
特にスパース状態において、これは亜臨界 Erd\H{o}s-R\'enyi グラフの擬フォレスト構造と、エッジ置換の短い軌道から組み立てることができる擬フォレストを注意深く列挙することによって達成される。
関連論文リスト
- Testing Dependency of Weighted Random Graphs [4.0554893636822]
本研究では,2つのランダムグラフ間のエッジ依存性を検出するタスクについて検討する。
一般のエッジウェイト分布に対して、最適テストが情報理論上可能か不可能となるしきい値を確立する。
論文 参考訳（メタデータ） (2024-09-23T10:07:41Z) - Graph Fourier MMD for Signals on Graphs [67.68356461123219]
本稿では,グラフ上の分布と信号の間の新しい距離を提案する。
GFMMDは、グラフ上で滑らかであり、期待差を最大化する最適な目撃関数によって定義される。
グラフベンチマークのデータセットと単一セルRNAシークエンシングデータ解析について紹介する。
論文 参考訳（メタデータ） (2023-06-05T00:01:17Z) - Online Centralized Non-parametric Change-point Detection via Graph-based
Likelihood-ratio Estimation [77.81487285123147]
グラフの各ノードを、ほぼリアルタイムで同期して観測されるデータストリームを生成するようにします。
変更ポイント$tau$では、変更はノードのサブセット$C$で発生し、関連するノードストリームの確率分布に影響を与える。
本稿では,ポストチェンジとノードストリームの事前変更分布の確率比の直接推定に基づいて,$tau$を検出して$C$をローカライズするカーネルベースの新しい手法を提案する。
論文 参考訳（メタデータ） (2023-01-08T10:15:24Z) - Causal Bandits for Linear Structural Equation Models [58.2875460517691]
本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。
グラフの構造は知られており、ノードは$N$である。
頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-26T16:21:31Z) - Bi-stochastically normalized graph Laplacian: convergence to manifold Laplacian and robustness to outlier noise [10.418647759223965]
双確率正規化 (bi-stochastic normalization) はグラフベースのデータ解析においてグラフラプラシアンの代替正規化を提供する。
両階層正規化グラフ Laplacian から (重み付き) Laplacian への収束を速度で証明する。
多様体データが外乱ノイズによって破損した場合、理論的にはラプラシア点の整合性を証明する。
論文 参考訳（メタデータ） (2022-06-22T21:08:24Z) - Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
グラフに基づく相対的制約のない最小二乗重要度フィッティング(GRULSIF)
我々はこの考え方を、グラフベースの相対的非制約最小二乗重要度フィッティング(GRULSIF)と呼ばれる具体的な非パラメトリック手法で開発する。
我々は、ノード当たりの観測回数、グラフのサイズ、およびグラフ構造がタスク間の類似性をどの程度正確にエンコードしているかといった変数が果たす役割を強調する、協調的なアプローチの収束率を導出する。
論文 参考訳（メタデータ） (2022-05-28T15:37:03Z) - Detection threshold for correlated Erd\H{o}s-R\'enyi graphs via densest
subgraphs [9.12788494573002]
ラベルなしノード上の2つのErdHos-R'enyiランダムグラフ間のエッジ相関を検出する問題を解く。
我々の研究における重要な新規性は、検出問題とエルドホス=ルネニグラフの最も密度の高い部分グラフの間の興味深い関係である。
論文 参考訳（メタデータ） (2022-03-28T08:32:43Z) - Correlation detection in trees for partial graph alignment [3.5880535198436156]
グラフのアライメントは,エッジの大部分を保存する2つのグラフのノード間のマッピングを探索する。
我々のアプローチは、2つのグラフの局所構造を比較し、その近傍が相関グラフに対して「十分近い」場合、2つのノードをマッチングすることである。
この問題は、一対の分岐木が積分布または相関分布から引き出されるかどうかの検定の観点から説明できる。
論文 参考訳（メタデータ） (2021-07-15T22:02:27Z) - Spectral clustering under degree heterogeneity: a case for the random
walk Laplacian [83.79286663107845]
本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。
次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
論文 参考訳（メタデータ） (2021-05-03T16:36:27Z) - Settling the Sharp Reconstruction Thresholds of Random Graph Matching [19.54246087326288]
2つのエッジ関連ランダムグラフ間の隠れた対応を復元する問題について検討する。
p=n-o(1)$のグラフに対して、鋭いしきい値が存在することが証明される。
sparse ErdHos-R'enyi graphs with $p=n-Theta(1)$ に対して、オール・オー・ナッシング現象はもはや成り立たないことを示す。
論文 参考訳（メタデータ） (2021-01-29T21:49:50Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。