Fugu-MT 論文翻訳(概要): Matching Correlated Inhomogeneous Random Graphs using the $k$-core Estimator

論文の概要: Matching Correlated Inhomogeneous Random Graphs using the $k$-core Estimator

arxiv url: http://arxiv.org/abs/2302.05407v1
Date: Fri, 10 Feb 2023 18:21:35 GMT
ステータス: 処理完了
システム内更新日: 2023-02-13 15:08:34.699981
Title: Matching Correlated Inhomogeneous Random Graphs using the $k$-core Estimator
Title（参考訳）: $k$-core推定器を用いた相関不均質ランダムグラフのマッチング
Authors: Mikl\'os Z. R\'acz and Anirudh Sridhar
Abstract要約: 我々は、両グラフの大きな共通部分グラフを誘導する対応を出力するいわゆるemph$k$-core推定器について検討する。相関ブロックモデル,Chung-Lu幾何グラフ,および相関ランダムグラフの精度と部分的回復に関する新たな結果を導出するために,我々の一般的な枠組みを専門化している。
参考スコア（独自算出の注目度）: 5.685589351789462
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We consider the task of estimating the latent vertex correspondence between two edge-correlated random graphs with generic, inhomogeneous structure. We study the so-called \emph{$k$-core estimator}, which outputs a vertex correspondence that induces a large, common subgraph of both graphs which has minimum degree at least $k$. We derive sufficient conditions under which the $k$-core estimator exactly or partially recovers the latent vertex correspondence. Finally, we specialize our general framework to derive new results on exact and partial recovery in correlated stochastic block models, correlated Chung-Lu graphs, and correlated random geometric graphs.
Abstract（参考訳）: 汎用的不均質構造を持つ2つの辺相関ランダムグラフ間の潜在頂点対応を推定するタスクについて検討する。いわゆる \emph{$k$-core estimator} は、少なくとも$k$の最低次数を持つ2つのグラフの大きな共通部分グラフを誘導する頂点対応を出力する。我々は、$k$-core推定器が潜在頂点対応を正確にあるいは部分的に回復する十分な条件を導出する。最後に, 相関確率ブロックモデル, 相関Chung-Luグラフ, 相関ランダムな幾何グラフの精度と部分的回復について, 新たな結果を得るための一般的な枠組みを考案する。

関連論文リスト

GrannGAN: Graph annotation generative adversarial networks [72.66289932625742]
本稿では,高次元分布をモデル化し,グラフスケルトンと整合した複雑な関係特徴構造を持つデータの新しい例を生成することの問題点を考察する。提案するモデルは,タスクを2つのフェーズに分割することで,各データポイントのグラフ構造に制約されたデータ特徴を生成する問題に対処する。第一に、与えられたグラフのノードに関連する機能の分布をモデル化し、第二に、ノードのフィーチャに条件付きでエッジ機能を補完する。
論文参考訳（メタデータ） (2022-12-01T11:49:07Z)
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)
Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
論文参考訳（メタデータ） (2021-12-29T18:46:52Z)
Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields [51.07460861448716]
本稿では,データから学ぶための凸解析フレームワークを提案する。三角凸分解はその上部に対応する変換によって保証されることを示す。
論文参考訳（メタデータ） (2021-09-17T17:46:12Z)
Correlation detection in trees for partial graph alignment [3.5880535198436156]
グラフのアライメントは,エッジの大部分を保存する2つのグラフのノード間のマッピングを探索する。我々のアプローチは、2つのグラフの局所構造を比較し、その近傍が相関グラフに対して「十分近い」場合、2つのノードをマッチングすることである。この問題は、一対の分岐木が積分布または相関分布から引き出されるかどうかの検定の観点から説明できる。
論文参考訳（メタデータ） (2021-07-15T22:02:27Z)
Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文参考訳（メタデータ） (2021-06-22T11:07:38Z)
A Thorough View of Exact Inference in Graphs from the Degree-4 Sum-of-Squares Hierarchy [37.34153902687548]
各エッジの1つの破損した観測からノードの未知の接地型バイナリラベリングを正確に回収する問題に取り組む。この問題に対して、和の平方階層と呼ばれるリラクゼーションの階層を適用します。我々は、緩和問題の双対の解がジョンソングラフとクネーサーグラフのエッジウェイトを見つけることに関連していることを示した。
論文参考訳（メタデータ） (2021-02-16T08:36:19Z)
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)
Factorizable Graph Convolutional Networks [90.59836684458905]
本稿では,グラフに符号化された相互に絡み合った関係を明示的に解消する新しいグラフ畳み込みネットワーク(GCN)を提案する。 FactorGCNは単純なグラフを入力として取り、それをいくつかの分解グラフに分解する。提案したFacterGCNは,合成および実世界のデータセットに対して質的かつ定量的に評価する。
論文参考訳（メタデータ） (2020-10-12T03:01:40Z)
Testing correlation of unlabeled random graphs [18.08210501570919]
ラベルなしノードを持つ2つのランダムグラフ間のエッジ相関を検出する問題について検討する。これは仮説テスト問題として定式化され、ヌル仮説の下では、2つのグラフは独立に生成される。代替として、2つのグラフは、ある潜在ノード対応の下ではエッジ関連であるが、ヌルと同じ辺分布を持つ。
論文参考訳（メタデータ） (2020-08-23T19:19:45Z)
Wasserstein-based Graph Alignment [56.84964475441094]
我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
論文参考訳（メタデータ） (2020-03-12T22:31:59Z)

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