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グラフ, 相関ランダムな幾何グラフの精度と部分的回復について, 新たな結果を得るための一般的な枠組みを考案する。

関連論文リスト

Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphs [7.001453437549302]
ErdHos-R'enyiグラフモデルでは、ある数を持つ一対の誘導された部分グラフが相関する。相関ノード数に対する部分回復に最適であることを示す。可能性の証明として,交差グラフのエッジを2種類の成分に分割する相関関数グラフを提案する。
論文参考訳（メタデータ） (2024-06-08T10:17:42Z)
GrannGAN: Graph annotation generative adversarial networks [72.66289932625742]
本稿では,高次元分布をモデル化し,グラフスケルトンと整合した複雑な関係特徴構造を持つデータの新しい例を生成することの問題点を考察する。提案するモデルは,タスクを2つのフェーズに分割することで,各データポイントのグラフ構造に制約されたデータ特徴を生成する問題に対処する。第一に、与えられたグラフのノードに関連する機能の分布をモデル化し、第二に、ノードのフィーチャに条件付きでエッジ機能を補完する。
論文参考訳（メタデータ） (2022-12-01T11:49:07Z)
Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
グラフに基づく相対的制約のない最小二乗重要度フィッティング(GRULSIF) 我々はこの考え方を、グラフベースの相対的非制約最小二乗重要度フィッティング(GRULSIF)と呼ばれる具体的な非パラメトリック手法で開発する。我々は、ノード当たりの観測回数、グラフのサイズ、およびグラフ構造がタスク間の類似性をどの程度正確にエンコードしているかといった変数が果たす役割を強調する、協調的なアプローチの収束率を導出する。
論文参考訳（メタデータ） (2022-05-28T15:37:03Z)
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)

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