論文の概要: Message-Passing GNNs Fail to Approximate Sparse Triangular Factorizations

• arxiv url: http://arxiv.org/abs/2502.01397v2
• Date: Wed, 28 May 2025 07:53:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-29 15:04:27.177193
• Title: Message-Passing GNNs Fail to Approximate Sparse Triangular Factorizations
• Title（参考訳）: メッセージパッシングGNNは、スパース三角因子の近似に失敗する
• Authors: Vladislav Trifonov, Ekaterina Muravleva, Ivan Oseledets,
• Abstract要約: 疎行列プレコンディショナを学習するためのツールとして,グラフニューラルネットワーク(GNN)が提案されている。 本稿では、メッセージパッシングGNNは、疎三角形の分解を近似できないことを論じる。
• 参考スコア（独自算出の注目度）: 3.868222899558346
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph Neural Networks (GNNs) have been proposed as a tool for learning sparse matrix preconditioners, which are key components in accelerating linear solvers. This position paper argues that message-passing GNNs are fundamentally incapable of approximating sparse triangular factorizations. We demonstrate that message-passing GNNs fundamentally fail to approximate sparse triangular factorizations for classes of matrices for which high-quality preconditioners exist but require non-local dependencies. To illustrate this, we construct a set of baselines using both synthetic matrices and real-world examples from the SuiteSparse collection. Across a range of GNN architectures, including Graph Attention Networks and Graph Transformers, we observe severe performance degradation compared to exact or K-optimal factorizations, with cosine similarity dropping below $0.6$ in key cases. Our theoretical and empirical results suggest that architectural innovations beyond message-passing are necessary for applying GNNs to scientific computing tasks such as matrix factorization. Experiments demonstrate that overcoming non-locality alone is insufficient. Tailored architectures are necessary to capture the required dependencies since even a completely non-local Graph Transformer fails to match the proposed baselines.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)は、線形解法を高速化する上で重要な要素であるスパース行列プレコンディショナーを学習するためのツールとして提案されている。 このポジションペーパーは、メッセージパッシングGNNは、疎三角形の分解を近似することができない、と論じている。 メッセージパッシングGNNは、高品質のプリコンディショナーが存在するが非局所的な依存関係を必要とする行列のクラスに対して、疎三角形の分解を基本的に近似できないことを実証する。 これを説明するために, SuiteSparseコレクションから合成行列と実世界の実例を用いて,ベースラインの集合を構築した。 グラフ注意ネットワーク(Graph Attention Networks)やグラフ変換器(Graph Transformer)など,GNNアーキテクチャの幅広い範囲において,コサイン類似性が0.6ドル未満のキーケースにおいて,正確なあるいはK-最適因数分解と比較して,大幅なパフォーマンス劣化が観測されている。 我々の理論的および実証的な結果は、GNNを行列分解などの科学計算タスクに適用するには、メッセージパス以外のアーキテクチャ革新が必要であることを示唆している。 非局所性のみを克服する実験は不十分である。 完全に非ローカルなグラフトランスフォーマーでさえ、提案されたベースラインにマッチしないため、階層化されたアーキテクチャは、必要な依存関係をキャプチャするために必要である。

関連論文リスト

• Learning incomplete factorization preconditioners for GMRES [1.1519724914285523]
  行列分解を直接近似するためにグラフニューラルネットワークを訓練する。 グラフニューラルネットワークアーキテクチャを適用することで、出力自体がスパースであることを保証することができます。 GMRESの繰り返し回数を減らし、合成データに対するスペクトル特性を改善する効果を示す。
  論文  参考訳（メタデータ） (2024-09-12T17:55:44Z)
• Weight Conditioning for Smooth Optimization of Neural Networks [28.243353447978837]
  本稿では,ニューラルネットワークの重み行列に対する新しい正規化手法を提案する。 このアプローチは、ウェイト行列の最小値と最大の特異値の間のギャップを狭くすることを目的としており、より良い条件付き行列をもたらす。 以上の結果から,本手法は競争力だけでなく,文献の既往の重み正規化手法よりも優れていたことが示唆された。
  論文  参考訳（メタデータ） (2024-09-05T11:10:34Z)
• Learning from Linear Algebra: A Graph Neural Network Approach to Preconditioner Design for Conjugate Gradient Solvers [40.6591136324878]
  我々は,従来のプリコンディショナーよりもシステムの条件数を大幅に削減するプリコンディショナーを得るために,GNNを訓練する。 本手法は、パラメトリック偏微分方程式の重要なクラスにおいて、古典的およびニューラルネットワークに基づく手法よりも優れている。
  論文  参考訳（メタデータ） (2024-05-24T13:44:30Z)
• Matrix Completion via Nonsmooth Regularization of Fully Connected Neural Networks [7.349727826230864]
  ディープニューラルネットワークのような非線形推定器を使うことで、性能の向上が達成できることが示されている。 本稿では,標準中間表現の観点から,FCNNモデルの正規化によるオーバーフィット制御を行う。 本シミュレーションは,既存の線形および非線形アルゴリズムと比較して,提案アルゴリズムの優位性を示す。
  論文  参考訳（メタデータ） (2024-03-15T12:00:37Z)
• Interpretable A-posteriori Error Indication for Graph Neural Network Surrogate Models [0.0]
  本稿では,グラフニューラルネットワーク(GNN)の解釈可能性向上手法を提案する。 最終結果は、予測タスクに本質的に関連付けられたサブグラフに対応する物理空間内の領域を分離する解釈可能なGNNモデルである。 解釈可能なGNNは、推論中に予測される予測エラーの大部分に対応するグラフノードを特定するためにも使用できる。
  論文  参考訳（メタデータ） (2023-11-13T18:37:07Z)
• Probabilistically Rewired Message-Passing Neural Networks [41.554499944141654]
  メッセージパッシンググラフニューラルネットワーク(MPNN)は、グラフ構造化入力を処理する強力なツールとして登場した。 MPNNは、潜在的なノイズや欠落した情報を無視して、固定された入力グラフ構造で動作する。 確率的に再構成されたMPNN(PR-MPNN)を考案し、より有益なものを省略しながら、関連するエッジを追加することを学習する。
  論文  参考訳（メタデータ） (2023-10-03T15:43:59Z)
• Contextualizing MLP-Mixers Spatiotemporally for Urban Data Forecast at Scale [54.15522908057831]
  本稿では,STTD予測を大規模に行うためのコンピュータ・ミクサーの適応版を提案する。 我々の結果は、この単純な効率の良いソリューションが、いくつかのトラフィックベンチマークでテストした場合、SOTAベースラインに匹敵する可能性があることを驚くほど示している。 本研究は, 実世界のSTTD予測において, 簡便な有効モデルの探索に寄与する。
  論文  参考訳（メタデータ） (2023-07-04T05:19:19Z)
• Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Results [58.277290855841976]
  グラフニューラルネットワーク(GNN)の計算コストと表現力のトレードオフについて検討する。 新しいモデルでは、$k$のサブグラフをカウントでき、低次GNNの既知の制限を克服できることを示す。 いくつかの場合において、提案アルゴリズムは既存の高階$k$-GNNに比べて計算量を大幅に削減することができる。
  論文  参考訳（メタデータ） (2020-12-06T03:42:54Z)
• Improving predictions of Bayesian neural nets via local linearization [79.21517734364093]
  ガウス・ニュートン近似は基礎となるベイズニューラルネットワーク(BNN)の局所線形化として理解されるべきである。 この線形化モデルを後部推論に使用するので、元のモデルではなく、この修正モデルを使用することも予測すべきである。 この修正された予測を"GLM predictive"と呼び、Laplace近似の共通不適合問題を効果的に解決することを示す。
  論文  参考訳（メタデータ） (2020-08-19T12:35:55Z)
• Learning Reasoning Strategies in End-to-End Differentiable Proving [50.9791149533921]
  条件付き定理プローバーは勾配に基づく最適化により最適規則選択戦略を学習する。 条件付き定理プローサは拡張性があり、CLUTRRデータセット上で最先端の結果が得られることを示す。
  論文  参考訳（メタデータ） (2020-07-13T16:22:14Z)
• Fast Learning of Graph Neural Networks with Guaranteed Generalizability: One-hidden-layer Case [93.37576644429578]
  グラフニューラルネットワーク(GNN)は、グラフ構造化データから実際に学習する上で、近年大きな進歩を遂げている。 回帰問題と二項分類問題の両方に隠れ層を持つGNNの理論的に基底的な一般化可能性解析を行う。
  論文  参考訳（メタデータ） (2020-06-25T00:45:52Z)
• Binarized Graph Neural Network [65.20589262811677]
  我々は二項化グラフニューラルネットワークを開発し、二項化ネットワークパラメータを用いてノードのバイナリ表現を学習する。 提案手法は既存のGNNベースの埋め込み手法にシームレスに統合できる。 実験により、提案された二項化グラフニューラルネットワーク、すなわちBGNは、時間と空間の両方の観点から、桁違いに効率的であることが示されている。
  論文  参考訳（メタデータ） (2020-04-19T09:43:14Z)
• Node Masking: Making Graph Neural Networks Generalize and Scale Better [71.51292866945471]
  グラフニューラルネットワーク(GNN)は近年,多くの関心を集めている。 本稿では,芸術空間のGNNの状態によって実行される操作をよりよく可視化するために,いくつかの理論ツールを利用する。 私たちはNode Maskingというシンプルなコンセプトを導入しました。
  論文  参考訳（メタデータ） (2020-01-17T06:26:40Z)

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

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