論文の概要: On the Interplay between Graph Structure and Learning Algorithms in Graph Neural Networks

• arxiv url: http://arxiv.org/abs/2508.14338v1
• Date: Wed, 20 Aug 2025 01:26:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-21 16:52:41.300838
• Title: On the Interplay between Graph Structure and Learning Algorithms in Graph Neural Networks
• Title（参考訳）: グラフニューラルネットワークにおけるグラフ構造と学習アルゴリズムの相互作用について
• Authors: Junwei Su, Chuan Wu,
• Abstract要約: グラフニューラルネットワーク(GNN)における学習アルゴリズムとグラフ構造との相互作用について検討する。 本研究は,GNNにおけるグラフ構造と学習の相互作用を理解する上で,いくつかの重要な貢献をしている。
• 参考スコア（独自算出の注目度）: 6.598758004828656
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper studies the interplay between learning algorithms and graph structure for graph neural networks (GNNs). Existing theoretical studies on the learning dynamics of GNNs primarily focus on the convergence rates of learning algorithms under the interpolation regime (noise-free) and offer only a crude connection between these dynamics and the actual graph structure (e.g., maximum degree). This paper aims to bridge this gap by investigating the excessive risk (generalization performance) of learning algorithms in GNNs within the generalization regime (with noise). Specifically, we extend the conventional settings from the learning theory literature to the context of GNNs and examine how graph structure influences the performance of learning algorithms such as stochastic gradient descent (SGD) and Ridge regression. Our study makes several key contributions toward understanding the interplay between graph structure and learning in GNNs. First, we derive the excess risk profiles of SGD and Ridge regression in GNNs and connect these profiles to the graph structure through spectral graph theory. With this established framework, we further explore how different graph structures (regular vs. power-law) impact the performance of these algorithms through comparative analysis. Additionally, we extend our analysis to multi-layer linear GNNs, revealing an increasing non-isotropic effect on the excess risk profile, thereby offering new insights into the over-smoothing issue in GNNs from the perspective of learning algorithms. Our empirical results align with our theoretical predictions, \emph{collectively showcasing a coupling relation among graph structure, GNNs and learning algorithms, and providing insights on GNN algorithm design and selection in practice.}
• Abstract（参考訳）: 本稿では,グラフニューラルネットワーク(GNN)の学習アルゴリズムとグラフ構造との相互作用について検討する。 GNNの学習力学に関する既存の理論的研究は、主に補間体制下での学習アルゴリズムの収束率(ノイズフリー)に焦点を当て、これらの力学と実際のグラフ構造(例えば最大度)の間の粗い接続のみを提供する。 本稿では,一般化体制内のGNNにおける学習アルゴリズムの過度なリスク(一般化性能)を調査し,このギャップを埋めることを目的とする。 具体的には、従来の設定を学習理論の文献からGNNの文脈に拡張し、グラフ構造が確率勾配勾配(SGD)やリッジ回帰といった学習アルゴリズムの性能にどのように影響するかを検討する。 本研究は,GNNにおけるグラフ構造と学習の相互作用を理解する上で,いくつかの重要な貢献をしている。 まず、GNNにおけるSGDとリッジ回帰の過剰なリスクプロファイルを導出し、これらのプロファイルをスペクトルグラフ理論によりグラフ構造に接続する。 この確立されたフレームワークにより、比較分析により、異なるグラフ構造(正規対パワーロー)がこれらのアルゴリズムの性能にどのように影響するかをさらに調べる。 さらに、我々は分析を多層線形GNNに拡張し、過剰リスクプロファイルに対する非等方的効果が増大していることを明らかにし、学習アルゴリズムの観点からGNNの過度な問題に対する新たな洞察を提供する。 実験の結果は,グラフ構造,GNN,学習アルゴリズム間の結合関係を示す「emph{collectively showsing a coupling relation of graph structure, GNNs and learning algorithm, and provide insights on GNN algorithm design and selection in practice。 ※

関連論文リスト

• Research on the application of graph data structure and graph neural network in node classification/clustering tasks [13.51508928671878]
  グラフ構造化データは、ソーシャルネットワーク、生物学的ネットワーク、ナレッジグラフを含むドメインにまたがる。 非ユークリッド的な性質のため、そのようなデータは従来の機械学習手法に重大な課題をもたらす。 本研究では,グラフデータ構造,古典的グラフアルゴリズム,グラフニューラルネットワーク(GNN)について検討する。
  論文  参考訳（メタデータ） (2025-07-20T12:57:23Z)
• On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspective [28.497567290882355]
  グラフニューラルネットワーク(GNN)は、リレーショナルデータに対する学習と推論の標準的なアプローチとなっている。 本稿では,回路複雑性のレンズによるGNNの計算限界について検討する。 具体的には、共通GNNアーキテクチャの回路複雑性を分析し、定数層、線形またはサブ線形埋め込みサイズ、精度の制約の下で、GNNはグラフ接続やグラフ同型といった重要な問題を解くことができないことを証明している。
  論文  参考訳（メタデータ） (2025-01-11T05:54:10Z)
• Permutation-Invariant Graph Partitioning:How Graph Neural Networks Capture Structural Interactions? [2.7398542529968477]
  グラフニューラルネットワーク(GNN)は、グラフ関連学習タスクの基盤となるための道を開いた。 しかし、グラフ内の構造的相互作用を捕捉するGNNの能力は、まだ解明されていない。 構造的相互作用の学習において,GNNの表現力を効率的に向上する新しいアーキテクチャであるグラフ分割ニューラルネットワーク(GPNN)を提案する。
  論文  参考訳（メタデータ） (2023-12-14T06:08:35Z)
• Ensemble Learning for Graph Neural Networks [28.3650473174488]
  グラフニューラルネットワーク(GNN)は、グラフ構造化データから学習するための様々な分野で成功している。 本稿では,GNNの性能とロバスト性向上のためのアンサンブル学習手法の適用について検討する。
  論文  参考訳（メタデータ） (2023-10-22T03:55:13Z)
• Self-supervision meets kernel graph neural models: From architecture to augmentations [36.388069423383286]
  カーネルグラフニューラルネットワーク(KGNN)の設計と学習の改善 我々はLGA(Latent graph augmentation)と呼ばれる新しい構造保存グラフデータ拡張法を開発した。 提案モデルは,最先端のグラフ表現学習フレームワークに匹敵する,あるいは時として優れる性能を実現する。
  論文  参考訳（メタデータ） (2023-10-17T14:04:22Z)
• How Graph Neural Networks Learn: Lessons from Training Dynamics [80.41778059014393]
  グラフニューラルネットワーク(GNN)の関数空間におけるトレーニングダイナミクスについて検討する。 GNNの勾配勾配勾配最適化は暗黙的にグラフ構造を利用して学習関数を更新する。 この発見は、学習したGNN関数が一般化した時期と理由に関する新たな解釈可能な洞察を提供する。
  論文  参考訳（メタデータ） (2023-10-08T10:19:56Z)
• DEGREE: Decomposition Based Explanation For Graph Neural Networks [55.38873296761104]
  我々は,GNN予測に対する忠実な説明を提供するためにDGREEを提案する。 GNNの情報生成と集約機構を分解することにより、DECREEは入力グラフの特定のコンポーネントのコントリビューションを最終的な予測に追跡することができる。 また,従来の手法で見過ごされるグラフノード間の複雑な相互作用を明らかにするために,サブグラフレベルの解釈アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2023-05-22T10:29:52Z)
• Discovering the Representation Bottleneck of Graph Neural Networks from Multi-order Interactions [51.597480162777074]
  グラフニューラルネットワーク(GNN)は、ノード機能を伝搬し、インタラクションを構築するためにメッセージパッシングパラダイムに依存している。 最近の研究は、異なるグラフ学習タスクはノード間の異なる範囲の相互作用を必要とすることを指摘している。 科学領域における2つの共通グラフ構築法、すなわち、emphK-nearest neighbor(KNN)グラフとemphfully-connected(FC)グラフについて検討する。
  論文  参考訳（メタデータ） (2022-05-15T11:38:14Z)
• Towards Unsupervised Deep Graph Structure Learning [67.58720734177325]
  本稿では,学習したグラフトポロジを外部ガイダンスなしでデータ自身で最適化する,教師なしグラフ構造学習パラダイムを提案する。 具体的には、元のデータから"アンカーグラフ"として学習目標を生成し、対照的な損失を用いてアンカーグラフと学習グラフとの一致を最大化する。
  論文  参考訳（メタデータ） (2022-01-17T11:57:29Z)
• Bridging the Gap between Spatial and Spectral Domains: A Unified Framework for Graph Neural Networks [61.17075071853949]
  グラフニューラルネットワーク(GNN)は、古典的なディープラーニングが容易に管理できないグラフ構造データを扱うように設計されている。 本研究の目的は,スペクトルグラフと近似理論に基づいてGNNを統合する統一フレームワークを確立することである。
  論文  参考訳（メタデータ） (2021-07-21T17:34:33Z)
• Fast Learning of Graph Neural Networks with Guaranteed Generalizability: One-hidden-layer Case [93.37576644429578]
  グラフニューラルネットワーク(GNN)は、グラフ構造化データから実際に学習する上で、近年大きな進歩を遂げている。 回帰問題と二項分類問題の両方に隠れ層を持つGNNの理論的に基底的な一般化可能性解析を行う。
  論文  参考訳（メタデータ） (2020-06-25T00:45:52Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。