論文の概要: Learning Sparse Graphons and the Generalized Kesten-Stigum Threshold
- arxiv url: http://arxiv.org/abs/2006.07695v1
- Date: Sat, 13 Jun 2020 18:38:05 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-21 21:38:49.075038
- Title: Learning Sparse Graphons and the Generalized Kesten-Stigum Threshold
- Title（参考訳）: 学習用スパースグラフと一般化ケステン・スティグラム閾値
- Authors: Emmanuel Abbe, Shuangping Li and Allan Sly
- Abstract要約: 本論文は,一定の期待次数条件下でグラノンを学習するための効率的なアルゴリズムを提供する。
このアルゴリズムは、グラフンの上位$k$固有値が一般化ケステン・スティグム条件を満たす場合、$L$計量におけるグラフンのランク-$k$射影を推定することに成功した。
- 参考スコア（独自算出の注目度）: 21.044900734651627
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The problem of learning graphons has attracted considerable attention across
several scientific communities, with significant progress over the recent years
in sparser regimes. Yet, the current techniques still require diverging degrees
in order to succeed with efficient algorithms in the challenging cases where
the local structure of the graph is homogeneous. This paper provides an
efficient algorithm to learn graphons in the constant expected degree regime.
The algorithm is shown to succeed in estimating the rank-$k$ projection of a
graphon in the $L_2$ metric if the top $k$ eigenvalues of the graphon satisfy a
generalized Kesten-Stigum condition.
- Abstract（参考訳）: グラフ学習の問題は、いくつかの科学コミュニティでかなりの注目を集めており、近年のスパルサー政権では大きな進歩を遂げている。
しかし、現在の手法では、グラフの局所構造が均質な場合において、効率的なアルゴリズムを成功させるためには、変分度を必要とする。
本稿では,一定の期待度でグラフを学習するための効率的なアルゴリズムを提案する。
このアルゴリズムは、グラフンの上位$k$固有値が一般化ケステン・スティグム条件を満たす場合、$L_2$計量におけるグラフンのランク-$k$投影を推定することに成功した。
関連論文リスト
- Scalable Implicit Graphon Learning [25.015678499211404]
本稿では、暗黙的ニューラルネットワーク(INR)とグラフニューラルネットワーク(GNN)を組み合わせて、観測されたグラフからグラフを推定するスケーラブルな手法を提案する。
合成グラフと実世界のグラフでSIGLを評価し,既存の手法より優れ,大規模グラフに効果的にスケール可能であることを示した。
論文 参考訳（メタデータ） (2024-10-22T22:44:24Z) - Expander Hierarchies for Normalized Cuts on Graphs [3.3385430106181184]
本稿では,拡張器の分解とその階層を計算するためのアルゴリズムについて紹介する。
様々な大きなグラフに対する実験により、この拡張器に基づくアルゴリズムは正規化カットに対する最先端の解法よりも優れていることが示された。
論文 参考訳（メタデータ） (2024-06-20T08:50:57Z) - What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding [67.59552859593985]
自己アテンションと位置エンコーディングを組み込んだグラフトランスフォーマーは、さまざまなグラフ学習タスクのための強力なアーキテクチャとして登場した。
本稿では,半教師付き分類のための浅いグラフ変換器の理論的検討について紹介する。
論文 参考訳（メタデータ） (2024-06-04T05:30:16Z) - Encoder Embedding for General Graph and Node Classification [4.178980693837599]
エンコーダの埋め込み行列が大数の法則と中心極限定理を満たすことを証明している。
ある条件下では、クラスごとの正規性を達成し、識別分析による最適な分類を可能にする。
論文 参考訳（メタデータ） (2024-05-24T11:51:08Z) - Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
本稿では,属性付きグラフデータに対する新しいDeep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE)を提案する。
提案手法は,最先端のベースラインアルゴリズムを,一般的なデータセット間でのダウンストリームタスクの差を大きく越える。
論文 参考訳（メタデータ） (2024-01-12T17:57:07Z) - Learning Regularized Graphon Mean-Field Games with Unknown Graphons [155.38727464526923]
グラフィック平均フィールドゲーム(GMFG)のための強化学習アルゴリズムを設計する。
我々は、正規化されたGMFGのナッシュ平衡(NE)を、グラフンが未知のときに学習することを目指している。
これらのアルゴリズムは、サンプルエージェントからグラモンを学習するために設計された最初のものである。
論文 参考訳（メタデータ） (2023-10-26T16:19:24Z) - Optimal Propagation for Graph Neural Networks [51.08426265813481]
最適グラフ構造を学習するための二段階最適化手法を提案する。
また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
論文 参考訳（メタデータ） (2022-05-06T03:37:00Z) - Learning Graphon Autoencoders for Generative Graph Modeling [91.32624399902755]
Graphonは任意のサイズでグラフを生成する非パラメトリックモデルであり、グラフから簡単に誘導できる。
解析可能でスケーラブルなグラフ生成モデルを構築するために,textitgraphon autoencoder という新しいフレームワークを提案する。
線形グルーポン分解モデルはデコーダとして機能し、潜在表現を活用して誘導されたグルーポンを再構成する。
論文 参考訳（メタデータ） (2021-05-29T08:11:40Z) - Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
グラフ表現学習は、ノード分類、予測、コミュニティ検出など、多くのグラフベースのアプリケーションで顕著な成功を収めている。
しかし,グラフ圧縮やエッジ分割などのグラフアプリケーションでは,グラフ表現学習タスクに還元することは極めて困難である。
本稿では,このようなアプリケーションの背後にあるグラフ順序付け問題に対して,新しい学習手法を用いて対処することを提案する。
論文 参考訳（メタデータ） (2020-01-18T09:14:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。