Fugu-MT 論文翻訳(概要): Testing network correlation efficiently via counting trees

論文の概要: Testing network correlation efficiently via counting trees

arxiv url: http://arxiv.org/abs/2110.11816v1
Date: Fri, 22 Oct 2021 14:47:20 GMT
ステータス: 処理完了
システム内更新日: 2021-10-25 15:28:09.388058
Title: Testing network correlation efficiently via counting trees
Title（参考訳）: 計数木によるネットワーク相関の効率的な検証
Authors: Cheng Mao, Yihong Wu, Jiaming Xu, Sophie H. Yu
Abstract要約: 本稿では,2つのネットワークがエッジ関連であるかどうかを潜時対応によって検証する新しい手法を提案する。テスト統計は、非同型木族に対する符号付き木の共起を数えることに基づいている。
参考スコア（独自算出の注目度）: 19.165942326142538
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We propose a new procedure for testing whether two networks are edge-correlated through some latent vertex correspondence. The test statistic is based on counting the co-occurrences of signed trees for a family of non-isomorphic trees. When the two networks are Erd\H{o}s-R\'enyi random graphs $\mathcal{G}(n,q)$ that are either independent or correlated with correlation coefficient $\rho$, our test runs in $n^{2+o(1)}$ time and succeeds with high probability as $n\to\infty$, provided that $n\min\{q,1-q\} \ge n^{-o(1)}$ and $\rho^2>\alpha \approx 0.338$, where $\alpha$ is Otter's constant so that the number of unlabeled trees with $K$ edges grows as $(1/\alpha)^K$. This significantly improves the prior work in terms of statistical accuracy, running time, and graph sparsity.
Abstract（参考訳）: 本稿では,2つのネットワークがエッジ関連であるかどうかを,潜在頂点対応によって検証する新しい手法を提案する。テスト統計は、非同型木族に対する符号付き木の共起を数えることに基づいている。 Erd\H{o}s-R\'enyiランダムグラフ $\mathcal{G}(n,q)$ と相関係数 $\rho$ が独立あるいは相関関係を持つ場合、我々のテストは $n^{2+o(1)} の時間で実行され、高い確率で $n\to\infty$ として成功し、$n\min\{q,1-q\} \ge n^{-o(1)}$ と $\rho^2>\alpha \approx 0.338$ が成立すると、$\alpha$ は、$K$エッジを持つ未ラベル木の数が$(1/\alpha)^K$ として増加する。これにより、統計的精度、実行時間、グラフの間隔の観点から、以前の作業を大幅に改善する。

関連論文リスト

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)
On the Unlikelihood of D-Separation [69.62839677485087]
解析的な証拠として、大きなグラフ上では、d-分離は存在が保証されたとしても珍しい現象である。 PCアルゴリズムでは、その最悪ケース保証がスパースグラフで失敗することが知られているが、平均ケースでも同じことが言える。 UniformSGSでは、既存のエッジに対してランニング時間が指数的であることが知られているが、平均的な場合、それは既存のほとんどのエッジにおいても期待されるランニング時間であることを示す。
論文参考訳（メタデータ） (2023-03-10T00:11:18Z)
Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
論文参考訳（メタデータ） (2023-02-13T22:51:07Z)
Phase Transitions in the Detection of Correlated Databases [12.010807505655238]
本稿では,2つのガウスデータベースの相関関係を$mathsfXinmathbbRntimes d$と$mathsfYntimes d$で検出する問題について検討する。この問題は、ソーシャルメディア、計算生物学などの分析に関係している。
論文参考訳（メタデータ） (2023-02-07T10:39:44Z)
Statistical limits of correlation detection in trees [0.7826806223782055]
本稿では,2本の観測木$(t,t')$が独立に標本化されているか,あるいは相関関係のある関節分布から採取されているかを調べる。グラフアライメントにより,片側テストの存在条件について検討する。このようなテストは$s leq sqrtalpha$に対して存在せず、そのようなテストは$s > sqrtalpha$, for $lambda$十分に大きいときに存在します。
論文参考訳（メタデータ） (2022-09-27T22:26:53Z)
Random graph matching at Otter's threshold via counting chandeliers [16.512416293014493]
そこで本研究では,各木に根付いた重み付き木を数えることで構築した類似度スコアに基づく,グラフマッチングの効率的なアルゴリズムを提案する。これは、明示的な一定の相関で成功し、スパースグラフと密度グラフの両方に適用する最初のグラフマッチングアルゴリズムである。
論文参考訳（メタデータ） (2022-09-25T20:00:28Z)
Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文参考訳（メタデータ） (2021-10-21T18:43:00Z)
Coresets for Decision Trees of Signals [19.537354146654845]
仮にそのような行列に対して$(k,varepsilon)$-coresetを出力する最初のアルゴリズムを提供する。これは、決定木と -- 機械学習から -- 計算幾何学における分割木の間のリンクをフォージすることで実現している。
論文参考訳（メタデータ） (2021-10-07T05:49:55Z)
Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu [14.298220510927695]
古典的ChowLiuアルゴリズム(IEEE Trans.Inform.Theory, 1968)に対する有限サンプル保証を提供する。特定の木の$T$に対して、$widetildeO (|Sigma|2nvarepsilon-1)$の分布からのサンプルを$P$ over $Sigman$とすると、最も近いKL分岐を効率的に学習できる。
論文参考訳（メタデータ） (2020-11-09T02:08:56Z)
A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
論文参考訳（メタデータ） (2020-06-02T16:38:36Z)

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