Fugu-MT 論文翻訳(概要): Testing Dependency of Weighted Random Graphs

論文の概要: Testing Dependency of Weighted Random Graphs

arxiv url: http://arxiv.org/abs/2409.14870v2
Date: Tue, 24 Sep 2024 16:07:57 GMT
ステータス: 処理完了
システム内更新日: 2024-11-06 20:39:08.814186
Title: Testing Dependency of Weighted Random Graphs
Title（参考訳）: 重み付きランダムグラフのテスト依存性
Authors: Mor Oren, Vered Paslev, Wasim Huleihel,
Abstract要約: 本研究では,2つのランダムグラフ間のエッジ依存性を検出するタスクについて検討する。一般のエッジウェイト分布に対して、最適テストが情報理論上可能か不可能となるしきい値を確立する。
参考スコア（独自算出の注目度）: 4.0554893636822
License: http://creativecommons.org/licenses/by/4.0/
Abstract: In this paper, we study the task of detecting the edge dependency between two weighted random graphs. We formulate this task as a simple hypothesis testing problem, where under the null hypothesis, the two observed graphs are statistically independent, whereas under the alternative, the edges of one graph are dependent on the edges of a uniformly and randomly vertex-permuted version of the other graph. For general edge-weight distributions, we establish thresholds at which optimal testing becomes information-theoretically possible or impossible, as a function of the total number of nodes in the observed graphs and the generative distributions of the weights. Finally, we identify a statistical-computational gap, and present evidence suggesting that this gap is inherent using the framework of low-degree polynomials.
Abstract（参考訳）: 本稿では,2つの重み付きランダムグラフ間のエッジ依存性を検出するタスクについて検討する。この課題を単純な仮説テスト問題として定式化し、ヌル仮説の下では、観測された2つのグラフは統計的に独立であり、一方のグラフのエッジは、他方のグラフの一様かつランダムに頂点に置換されたバージョンのエッジに依存する。一般のエッジウェイト分布に対して、観測されたグラフのノード数と重みの生成分布の関数として、最適テストが情報理論的に可能であるか不可能になるしきい値を確立する。最後に、統計的-計算的ギャップを特定し、このギャップが低次多項式の枠組みを用いて固有のものであることを示す証拠を示す。

関連論文リスト

Graph Out-of-Distribution Generalization with Controllable Data Augmentation [51.17476258673232]
グラフニューラルネットワーク(GNN)は,グラフ特性の分類において異常な性能を示した。トレーニングとテストデータの選択バイアスが原因で、分散偏差が広まっています。仮想サンプルの分布偏差を測定するためのOODキャリブレーションを提案する。
論文参考訳（メタデータ） (2023-08-16T13:10:27Z)
Graph Fourier MMD for Signals on Graphs [67.68356461123219]
本稿では,グラフ上の分布と信号の間の新しい距離を提案する。 GFMMDは、グラフ上で滑らかであり、期待差を最大化する最適な目撃関数によって定義される。グラフベンチマークのデータセットと単一セルRNAシークエンシングデータ解析について紹介する。
論文参考訳（メタデータ） (2023-06-05T00:01:17Z)
Joint graph learning from Gaussian observations in the presence of hidden nodes [26.133725549667734]
本稿では,隠れ変数の存在を考慮した共同グラフ学習法を提案する。従来の考察から得られた構造を利用して凸最適化問題を提案する。提案したアルゴリズムを異なるベースラインで比較し、合成グラフと実世界のグラフ上での性能を評価する。
論文参考訳（メタデータ） (2022-12-04T13:03:41Z)
Unveiling the Sampling Density in Non-Uniform Geometric Graphs [69.93864101024639]
グラフを幾何学グラフとみなす: ノードは基礎となる計量空間からランダムにサンプリングされ、その距離が指定された近傍半径以下であれば任意のノードが接続される。ソーシャルネットワークでは、コミュニティは密集したサンプル領域としてモデル化でき、ハブはより大きな近傍半径を持つノードとしてモデル化できる。我々は,未知のサンプリング密度を自己監督的に推定する手法を開発した。
論文参考訳（メタデータ） (2022-10-15T08:01:08Z)
Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
グラフに基づく相対的制約のない最小二乗重要度フィッティング(GRULSIF) 我々はこの考え方を、グラフベースの相対的非制約最小二乗重要度フィッティング(GRULSIF)と呼ばれる具体的な非パラメトリック手法で開発する。我々は、ノード当たりの観測回数、グラフのサイズ、およびグラフ構造がタスク間の類似性をどの程度正確にエンコードしているかといった変数が果たす役割を強調する、協調的なアプローチの収束率を導出する。
論文参考訳（メタデータ） (2022-05-28T15:37:03Z)
Residual2Vec: Debiasing graph embedding with random graphs [1.9280643035418397]
本稿では,グラフの様々な構造バイアスをランダムグラフを用いてデバイアスするグラフ埋め込み法であるRess2vecを提案する。この偏りがリンク予測やクラスタリング性能を改善するだけでなく、グラフ埋め込みにおける健全な構造特性を明示的にモデル化できることを実証する。
論文参考訳（メタデータ） (2021-10-14T18:24:11Z)
Hypothesis Testing for Equality of Latent Positions in Random Graphs [0.2741266294612775]
2つの頂点 $i$ と $j$th が、おそらくスケーリングまで、同じ潜在位置を持つという仮説テストの問題を考える。グラフの隣接性または正規化ラプラシアンスペクトル埋め込みのいずれかのi$th行とj$th行の間の経験的マハラノビス距離に基づくいくつかのテスト統計について提案する。これらのテスト統計を用いて、標準ブロックモデルとその次数補正変種を選択する際のモデル選択問題に対処する。
論文参考訳（メタデータ） (2021-05-23T01:27:23Z)
A Thorough View of Exact Inference in Graphs from the Degree-4 Sum-of-Squares Hierarchy [37.34153902687548]
各エッジの1つの破損した観測からノードの未知の接地型バイナリラベリングを正確に回収する問題に取り組む。この問題に対して、和の平方階層と呼ばれるリラクゼーションの階層を適用します。我々は、緩和問題の双対の解がジョンソングラフとクネーサーグラフのエッジウェイトを見つけることに関連していることを示した。
論文参考訳（メタデータ） (2021-02-16T08:36:19Z)
Testing correlation of unlabeled random graphs [18.08210501570919]
ラベルなしノードを持つ2つのランダムグラフ間のエッジ相関を検出する問題について検討する。これは仮説テスト問題として定式化され、ヌル仮説の下では、2つのグラフは独立に生成される。代替として、2つのグラフは、ある潜在ノード対応の下ではエッジ関連であるが、ヌルと同じ辺分布を持つ。
論文参考訳（メタデータ） (2020-08-23T19:19:45Z)
Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文参考訳（メタデータ） (2020-06-24T11:37:33Z)
Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。本稿では,非自明なERGに対する近似フレームワークを提案する。我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文参考訳（メタデータ） (2020-02-14T11:42:16Z)

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