論文の概要: On Local Limits of Sparse Random Graphs: Color Convergence and the Refined Configuration Model
- arxiv url: http://arxiv.org/abs/2510.21392v1
- Date: Fri, 24 Oct 2025 12:29:51 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-28 09:00:15.464113
- Title: On Local Limits of Sparse Random Graphs: Color Convergence and the Refined Configuration Model
- Title（参考訳）: スパースランダムグラフの局所極限について:色収束と精製構成モデル
- Authors: Alexander Pluska, Sagar Malhotra,
- Abstract要約: 局所収束はスパースランダムグラフモデル解析の基本的なツールとして登場した。
Wesfeiler-Lemanアルゴリズムに基づく局所収束、色収束という新しい概念を導入する。
- 参考スコア（独自算出の注目度）: 47.46315349835094
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Local convergence has emerged as a fundamental tool for analyzing sparse random graph models. We introduce a new notion of local convergence, color convergence, based on the Weisfeiler-Leman algorithm. Color convergence fully characterizes the class of random graphs that are well-behaved in the limit for message-passing graph neural networks. Building on this, we propose the Refined Configuration Model (RCM), a random graph model that generalizes the configuration model. The RCM is universal with respect to local convergence among locally tree-like random graph models, including Erd\H{o}s-R\'enyi, stochastic block and configuration models. Finally, this framework enables a complete characterization of the random trees that arise as local limits of such graphs.
- Abstract（参考訳）: 局所収束はスパースランダムグラフモデル解析の基本的なツールとして登場した。
Wesfeiler-Lemanアルゴリズムに基づく局所収束、色収束という新しい概念を導入する。
色収束は、メッセージパッシンググラフニューラルネットワークの限界においてよく理解されているランダムグラフのクラスを、完全に特徴付けている。
これに基づいて、構成モデルを一般化するランダムグラフモデルであるRefined Configuration Model (RCM)を提案する。
RCMは、局所木のようなランダムグラフモデル(Erd\H{o}s-R\'enyi, 確率ブロックおよび構成モデルを含む)の局所収束に関して普遍的である。
最後に、このフレームワークはそのようなグラフの局所極限として生じるランダムツリーの完全な特徴づけを可能にする。
関連論文リスト
- A Spectral Interpretation of Redundancy in a Graph Reservoir [51.40366905583043]
この研究はMRGNN(Multi resolution Reservoir Graph Neural Network)における貯留層の定義を再考する。
コンピュータグラフィックスにおける表面設計の分野で最初に導入されたフェアリングアルゴリズムに基づく変種を提案する。
この論文の中核的な貢献は、ランダムウォークの観点からのアルゴリズムの理論解析にある。
論文 参考訳（メタデータ） (2025-07-17T10:02:57Z) - Almost Surely Asymptotically Constant Graph Neural Networks [7.339728196535312]
出力は定数関数に収束し、これらの分類器が一様に表現できる上限となることを示す。
この強い収束現象は、芸術モデルを含む非常に幅広い種類のGNNに適用される。
我々はこれらの知見を実証的に検証し、収束現象がランダムグラフだけでなく、実世界のグラフにも現れることを観察した。
論文 参考訳（メタデータ） (2024-03-06T17:40:26Z) - GNN-LoFI: a Novel Graph Neural Network through Localized Feature-based
Histogram Intersection [51.608147732998994]
グラフニューラルネットワークは、グラフベースの機械学習の選択フレームワークになりつつある。
本稿では,古典的メッセージパッシングに代えて,ノード特徴の局所分布を解析するグラフニューラルネットワークアーキテクチャを提案する。
論文 参考訳（メタデータ） (2024-01-17T13:04:23Z) - GrannGAN: Graph annotation generative adversarial networks [72.66289932625742]
本稿では,高次元分布をモデル化し,グラフスケルトンと整合した複雑な関係特徴構造を持つデータの新しい例を生成することの問題点を考察する。
提案するモデルは,タスクを2つのフェーズに分割することで,各データポイントのグラフ構造に制約されたデータ特徴を生成する問題に対処する。
第一に、与えられたグラフのノードに関連する機能の分布をモデル化し、第二に、ノードのフィーチャに条件付きでエッジ機能を補完する。
論文 参考訳（メタデータ） (2022-12-01T11:49:07Z) - Community Recovery in the Geometric Block Model [38.77098549680883]
幾何学ブロックモデルにおけるコミュニティを検出するための単純な三角形計数データセットは、ほぼ最適であることを示す。
また,本アルゴリズムは理論的にも実用的にも極めて良好であることを示す。
論文 参考訳（メタデータ） (2022-06-22T18:10:49Z) - Spatial-spectral Hyperspectral Image Classification via Multiple Random
Anchor Graphs Ensemble Learning [88.60285937702304]
本稿では,複数のランダムアンカーグラフアンサンブル学習(RAGE)を用いた空間スペクトルHSI分類手法を提案する。
まず、各選択されたバンドのより記述的な特徴を抽出し、局所的な構造と領域の微妙な変化を保存するローカルバイナリパターンを採用する。
次に,アンカーグラフの構成に適応隣接代入を導入し,計算複雑性を低減した。
論文 参考訳（メタデータ） (2021-03-25T09:31:41Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。