Fugu-MT 論文翻訳(概要): Detection threshold for correlated Erd\H{o}s-R\'enyi graphs via densest subgraphs

論文の概要: Detection threshold for correlated Erd\H{o}s-R\'enyi graphs via densest subgraphs

arxiv url: http://arxiv.org/abs/2203.14573v1
Date: Mon, 28 Mar 2022 08:32:43 GMT
ステータス: 処理完了
システム内更新日: 2022-03-29 17:26:52.114039
Title: Detection threshold for correlated Erd\H{o}s-R\'enyi graphs via densest subgraphs
Title（参考訳）: 高密度部分グラフによる相関 Erd\H{o}s-R\enyi グラフの検出しきい値
Authors: Jian Ding, Hang Du
Abstract要約: ラベルなしノード上の2つのErdHos-R'enyiランダムグラフ間のエッジ相関を検出する問題を解く。我々の研究における重要な新規性は、検出問題とエルドホス=ルネニグラフの最も密度の高い部分グラフの間の興味深い関係である。
参考スコア（独自算出の注目度）: 9.12788494573002
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: The problem of detecting edge correlation between two Erd\H{o}s-R\'enyi random graphs on $n$ unlabeled nodes can be formulated as a hypothesis testing problem: under the null hypothesis, the two graphs are sampled independently; under the alternative, the two graphs are independently sub-sampled from a parent graph which is Erd\H{o}s-R\'enyi $\mathbf{G}(n, p)$ (so that their marginal distributions are the same as the null). We establish a sharp information-theoretic threshold when $p = n^{-\alpha+o(1)}$ for $\alpha\in (0, 1]$ which sharpens a constant factor in a recent work by Wu, Xu and Yu. A key novelty in our work is an interesting connection between the detection problem and the densest subgraph of an Erd\H{o}s-R\'enyi graph.
Abstract（参考訳）: n$ の非ラベルノード上の 2 つの erd\h{o}s-r\'enyi ランダムグラフ間の辺相関を検出する問題は、仮説検定問題として定式化することができる: ヌル仮説の下では、2つのグラフは独立にサンプリングされる; 代替として、2つのグラフは erd\h{o}s-r\'enyi $\mathbf{g}(n, p)$ の親グラフから独立にサブサンプリングされる。 p = n^{-\alpha+o(1)}$ for $\alpha\in (0, 1]$ が、Wu, Xu, Yu の最近の研究で定数因子をシャープ化するとき、鋭い情報理論しきい値を確立する。我々の研究における重要な新規性は、検出問題と Erd\H{o}s-R\'enyi グラフの最も密度の高い部分グラフの間の興味深い関係である。

関連論文リスト

Collaborative non-parametric two-sample testing [55.98760097296213]
目標は、null仮説の$p_v = q_v$が拒否されるノードを特定することである。グラフ構造を効率的に活用する非パラメトリックコラボレーティブ2サンプルテスト(CTST)フレームワークを提案する。提案手法は,f-divergence Estimation, Kernel Methods, Multitask Learningなどの要素を統合する。
論文参考訳（メタデータ） (2024-02-08T14:43:56Z)
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)
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)
Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment [51.74913666829224]
強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
論文参考訳（メタデータ） (2022-08-18T09:19:01Z)
Matching recovery threshold for correlated random graphs [9.12788494573002]
共通 ErdHos-R'enyi グラフ $mathbfG(n, p)$ から独立にサブサンプリングされた2つの相関グラフに対して、これらの2つのグラフのアンフィグアウトラベルの観測からそれらのエンフィラテントマッチングを回復したい。この結果は,近年のWu,Xu,Yuによる研究において一定の要因を導出する。
論文参考訳（メタデータ） (2022-05-29T13:04:20Z)
Deep Graph-level Anomaly Detection by Glocal Knowledge Distillation [61.39364567221311]
グラフレベルの異常検出(GAD)は、その構造やノードの特徴に異常なグラフを検出する問題を記述している。 GADの課題の1つは、局所的および大域的非正則グラフの検出を可能にするグラフ表現を考案することである。本稿では,グラフとノード表現の連成ランダム蒸留により,グローバルおよびローカルな正規パターン情報を豊富に学習するGADのための新しい深部異常検出手法を提案する。
論文参考訳（メタデータ） (2021-12-19T05:04:53Z)
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)
Adversarial Linear Contextual Bandits with Graph-Structured Side Observations [80.95090605985042]
学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。 textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
論文参考訳（メタデータ） (2020-12-10T15:40:07Z)
Testing correlation of unlabeled random graphs [18.08210501570919]
ラベルなしノードを持つ2つのランダムグラフ間のエッジ相関を検出する問題について検討する。これは仮説テスト問題として定式化され、ヌル仮説の下では、2つのグラフは独立に生成される。代替として、2つのグラフは、ある潜在ノード対応の下ではエッジ関連であるが、ヌルと同じ辺分布を持つ。
論文参考訳（メタデータ） (2020-08-23T19:19:45Z)

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