論文の概要: Efficient Dynamic Algorithms for Graph Neural Networks with Non-Linear Propagation

• arxiv url: http://arxiv.org/abs/2609.32929v1
• Date: Sat, 26 Sep 2026 20:42:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-06 11:53:45.441499
• Title: Efficient Dynamic Algorithms for Graph Neural Networks with Non-Linear Propagation
• Title（参考訳）: 非線形伝播を用いたグラフニューラルネットワークの効率的な動的アルゴリズム
• Abstract要約: グラフニューラルネットワーク(GNN)は、グラフ上の表現学習に広く使われている。 ほとんどのメソッドは静的トポロジを前提としており、エッジが時間とともに変化するネットワークの進化に非効率である。 エッジ挿入および削除下での非線形GNN伝搬に対するノード表現の効率よく維持する方法を示す。
• 参考スコア（独自算出の注目度）: 29.80247243097058
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph Neural Networks (GNNs) are widely used for representation learning on graphs, but most methods assume static topologies, making them inefficient on evolving networks where edges change over time. Existing dynamic approaches either model graph evolution through temporal GNN architectures without focusing on efficient dynamic maintenance, or are restricted to linear propagation models based on Personalized PageRank. In this work, we study how to efficiently maintain node representations for non-linear GNN propagation under edge insertions and deletions. The propagation has no learned parameters, and only a classifier applied afterward is trained. For a broad class of standard activation functions, we develop a residual-based dynamic algorithm that selectively propagates local errors via push operations, maintaining an approximation to the evolving fixed point without full recomputation. We prove that our method achieves amortized $O(1/ε)$ update time per graph change under a degree-normalized error guarantee. Our approach uses a potential-based analysis in a degree-scaled norm and, in contrast to prior work on the linear case, requires no randomness assumptions on either the update sequence or the input vector. For the linear special case, we additionally provide an exact dynamic algorithm via low-rank matrix inverse updates. Experiments on benchmark datasets show that incorporating non-linearity improves accuracy while preserving efficient update performance, yielding a scalable and theoretically grounded method for maintaining this propagation on dynamic graphs.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)はグラフ上での表現学習に広く使用されているが、ほとんどの手法では静的トポロジを前提としており、エッジが時間とともに変化するネットワークの進化に非効率である。 既存の動的アプローチは、効率的な動的保守に焦点をあてることなく、時間的GNNアーキテクチャによるグラフの進化をモデル化するか、あるいはパーソナライズされたPageRankに基づく線形伝搬モデルに制限される。 本研究では, エッジ挿入および削除下での非線形GNN伝搬に対するノード表現の効率よく維持する方法について検討する。 伝搬には学習パラメータがなく、その後適用された分類器のみが訓練される。 標準活性化関数の幅広いクラスに対して、我々はプッシュ操作により局所誤差を選択的に伝播させ、完全再計算なしで進化する固定点への近似を維持する残差に基づく動的アルゴリズムを開発した。 本手法は,次数正規化誤差保証の下で,グラフ変更毎の更新時間(O(1/ε)$)を補正できることを実証する。 提案手法は,次数スケールのノルムにおけるポテンシャルに基づく解析を用いており,線形の場合と対照的に,更新シーケンスや入力ベクトルのいずれにもランダムな仮定は不要である。 線形特殊ケースに対しては、低ランク行列逆更新による正確な動的アルゴリズムも提供する。 ベンチマークデータセットの実験では、非直線性の導入により、効率的な更新性能を維持しながら精度が向上し、動的グラフ上でこの伝搬を維持するためのスケーラブルで理論的に基礎付けられた方法が得られた。

関連論文リスト

• Semi-Supervised Learning on Graphs using Graph Neural Networks [7.3886152750469]
  グラフニューラルネットワーク(GNN)は、半教師付きノード回帰において極めてうまく機能する。 本稿では,複数の共通メッセージパッシングアーキテクチャを含むアグリゲート・アンド・リードアウトモデルについて検討する。 我々は、誤差近似、収束、最適化を分離する急激な非漸近的リスク境界を証明した。
  論文  参考訳（メタデータ） (2026-02-19T06:25:13Z)
• Efficient and Effective Implicit Dynamic Graph Neural Network [42.49148111696576]
  Indicit Dynamic Graph Neural Network (IDGNN) は動的グラフのための新しい暗黙的ニューラルネットワークである。 IDGNNの鍵となる特徴は、それが実証的に良好である、すなわち、固定点表現を持つことが理論的に保証されていることである。
  論文  参考訳（メタデータ） (2024-06-25T19:07:21Z)
• Topology-Aware Dynamic Reweighting for Distribution Shifts on Graph [24.44321658238713]
  グラフニューラルネットワーク(GNN)は、ノード分類タスクに広く使用されているが、トレーニングやテストノードが異なるディストリビューションから来ると、一般化に失敗することが多い。 トレーニング中にWasserstein空間の勾配流を通じて標本重量を動的に調整するTopology-Aware Dynamic Reweighting (TAR) フレームワークを導入する。 フレームワークの優位性は、4つのグラフOODデータセットと3つのクラス不均衡ノード分類データセットの標準テストによって実証される。
  論文  参考訳（メタデータ） (2024-06-03T07:32:05Z)
• Dynamic Graph Unlearning: A General and Efficient Post-Processing Method via Gradient Transformation [24.20087360102464]
  動的グラフアンラーニングを初めて研究し、DGNNアンラーニングを実装するための効率的で効率的で汎用的で後処理手法を提案する。 提案手法は,将来的な未学習要求を処理できる可能性があり,性能が大幅に向上する。
  論文  参考訳（メタデータ） (2024-05-23T10:26:18Z)
• Efficient Heterogeneous Graph Learning via Random Projection [58.4138636866903]
  不均一グラフニューラルネットワーク(HGNN)は、異種グラフを深層学習するための強力なツールである。 最近のプリ計算ベースのHGNNは、一時間メッセージパッシングを使用して不均一グラフを正規形テンソルに変換する。 我々はRandom Projection Heterogeneous Graph Neural Network (RpHGNN) というハイブリッド計算前HGNNを提案する。
  論文  参考訳（メタデータ） (2023-10-23T01:25:44Z)
• How Graph Neural Networks Learn: Lessons from Training Dynamics [80.41778059014393]
  グラフニューラルネットワーク(GNN)の関数空間におけるトレーニングダイナミクスについて検討する。 GNNの勾配勾配勾配最適化は暗黙的にグラフ構造を利用して学習関数を更新する。 この発見は、学習したGNN関数が一般化した時期と理由に関する新たな解釈可能な洞察を提供する。
  論文  参考訳（メタデータ） (2023-10-08T10:19:56Z)
• Instant Graph Neural Networks for Dynamic Graphs [18.916632816065935]
  Instant Graph Neural Network (InstantGNN) を提案する。 提案手法は,時間を要する反復計算を回避し,表現の即時更新と即時予測を可能にする。 本モデルでは,既存手法よりも高精度かつ高次精度で最先端の精度を実現する。
  論文  参考訳（メタデータ） (2022-06-03T03:27:42Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  最適グラフ構造を学習するための二段階最適化手法を提案する。 また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
  論文  参考訳（メタデータ） (2022-05-06T03:37:00Z)

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

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