論文の概要: Two-Sample Testing for Random Graphs without Vertex Correspondence
- arxiv url: http://arxiv.org/abs/2610.07503v1
- Date: Mon, 05 Oct 2026 23:09:29 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-08 02:58:29.702941
- Title: Two-Sample Testing for Random Graphs without Vertex Correspondence
- Title（参考訳）: 頂点対応のないランダムグラフの2サンプルテスト
- Abstract要約: グループごとのmasymp t-3$グラフは、グラフごとの信号-雑音比が$t1$であるときに必要であることを示す。
また、1グループにつき1つか2つのグラフに対して、電力のコストで、正確に有効なテストも行います。
- 参考スコア（独自算出の注目度）: 13.142220109832197
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Two populations of graphs often have to be compared without any correspondence between their vertices, for instance when networks come from different communities, or when a graph generative model is evaluated against held-out graphs. We study how many graphs such an unaligned two-sample test needs, and which graph statistics can detect which differences. For an Erdős--Rényi null and a planted two-block difference that leaves every expected degree unchanged, we show that $m\asymp t^{-3}$ graphs per group are necessary and sufficient when the per-graph signal-to-noise ratio is $t<1$. Signed triangle counts attain this rate, and the lower bound holds for every graph size. With aligned vertices $m\asymp t^{-1}$ graphs suffice, so misalignment costs a factor of order $t^{-2}$. When the triangle signal cancels, the rate becomes $t^{-4}$ and $4$-cycles are needed. Statistics built from trees have exactly the same expectation under both hypotheses, and tests based on finitely many of them have asymptotically no power. In the graphon limit, this class includes degree distributions and message-passing graph neural network features. For a non-constant null, a generic difference is visible at first order, and a simple motif test attains the aligned order of sample size, suggesting that misalignment is costly mainly for differences that are invisible at low orders. We also give an exactly valid test for one or two graphs per group, at a cost in power. In our simulations, the fitted exponents are close to the predicted ones, and degree-based and random-GNN evaluation metrics stay at their level in a setting where signed triangles need about $65$ graphs.
- Abstract（参考訳）: 例えば、異なるコミュニティから来るネットワークや、グラフ生成モデルがホールドアウトグラフに対して評価される場合などである。
本研究では,不整合な2サンプルテストに必要なグラフ数と,差分を検出するグラフ統計量について検討する。
エルデシュ=レーニ・ヌルと、全ての期待される次数を変えない2ブロック差を植え込んだ場合、グラフ毎の$m\asymp t^{-3}$グラフは、グラフ毎の信号-雑音比が$t<1$であるときに必要で十分であることを示す。
符号付き三角形はこの値に達し、下限はグラフのサイズごとに保持される。
整列頂点 $m\asymp t^{-1}$ グラフが十分であれば、不整合は階数 $t^{-2}$ の因子を必要とする。
三角形信号がキャンセルされると、そのレートが$t^{-4}$となり、サイクルが4ドル必要になる。
木から作られた統計学は、両方の仮説の下で全く同じ期待を持ち、有限個の木に基づくテストは漸近的に力を持たない。
グラフオン制限では、このクラスは次数分布とメッセージパッシンググラフニューラルネットワーク機能を含んでいる。
非コンスタントヌルに対しては、一階で一般的な差分が見え、単純なモチーフテストはサンプルサイズの整列順序に達する。
また、1グループにつき1つか2つのグラフに対して、電力のコストで、正確に有効なテストも行います。
我々のシミュレーションでは、適合した指数は予測値に近づき、等級ベースおよびランダムGNN評価指標は、符号付き三角形が約65ドルのグラフを必要とする設定でそれらのレベルに留まる。
関連論文リスト
- Automated search for highly contextual Kochen-Specker proofs [0.0]
コチェン=スペーカー証明(Kochen-Specker proofs)は、多ビットのパウリ可観測体の構成で、積が増減する文脈にグループ化される。
まず反可換グラフを列挙し、次に各グラフに$G$を関連づけ、そのハイパーグラフ全体をサポートする$HS(G)$を持てる1つのハイパーグラムに関連付ける。
論文 参考訳（メタデータ） (2026-09-17T08:18:29Z) - Learning from one graph: transductive learning guarantees via the geometry of small random worlds [8.781923502647055]
我々は,低次元メートル法埋め込みによる大規模グラフの幾何正則性を活用する新しい集中度測定ツールを開発した。
まず、任意の決定論的 $k$-vertex グラフと、ErdHos-R'enyi グラフ $mathbfG=mathbfG(k,p)$ in the regime $p in the MathcalO((log (k)/k)1/2) で鍵幾何学的性質を共有するランダムグラフについて述べる。
論文 参考訳（メタデータ） (2025-09-08T17:13:28Z) - Structural perspective on constraint-based learning of Markov networks [11.388331913007248]
すべての$n$-vertexグラフは、最大$nkappa$テストによって、条件付きサイズのセットを最大$kappa$で学習できることを証明します。
正の面において、有界木幅のすべてのグラフは、条件付きサイズの集合を少なくとも2kappa$で持つ多くのテストによって学習できることを証明している。
論文 参考訳（メタデータ） (2024-03-13T14:14:47Z) - 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) - Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect
Alignment [51.74913666829224]
強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。
本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。
実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
論文 参考訳（メタデータ） (2022-08-18T09:19:01Z) - 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) - Random Subgraph Detection Using Queries [29.192695995340653]
植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。
本稿では,適応的なエッジクエリを用いてグラフの比較的小さな部分のみを観測できる,上記の問題の自然な変形について考察する。
このモデルでは,植込み部分グラフの存在を検出するのに必要なクエリ数と十分なクエリ数(準多項式最適アルゴリズムを伴う)を決定する。
論文 参考訳（メタデータ） (2021-10-02T07:41:17Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。