論文の概要: Probabilistic Graph Rewiring via Virtual Nodes

• arxiv url: http://arxiv.org/abs/2405.17311v1
• Date: Mon, 27 May 2024 16:11:49 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-28 14:33:59.928211
• Title: Probabilistic Graph Rewiring via Virtual Nodes
• Title（参考訳）: 仮想ノードによる確率的グラフのリライト
• Authors: Chendi Qian, Andrei Manolache, Christopher Morris, Mathias Niepert,
• Abstract要約: メッセージパッシンググラフニューラルネットワーク(MPNN)は、グラフベースの機械学習の強力なパラダイムとして登場した。 MPNNは、受信フィールドの制限や構造的ボトルネックが、グラフ内の情報フローを妨げている、アンダーリーチ(low-reaching)やオーバースキャッシング(over-squashing)といった課題に直面している。 そこで本研究では,MPNNに書き換えることの容易な確率的グラフを統合する新しいアプローチである,IPR-MPNN(Emphimplicitly rewired Message-passing Neural Network)を提案する。
• 参考スコア（独自算出の注目度）: 21.273828055299408
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Message-passing graph neural networks (MPNNs) have emerged as a powerful paradigm for graph-based machine learning. Despite their effectiveness, MPNNs face challenges such as under-reaching and over-squashing, where limited receptive fields and structural bottlenecks hinder information flow in the graph. While graph transformers hold promise in addressing these issues, their scalability is limited due to quadratic complexity regarding the number of nodes, rendering them impractical for larger graphs. Here, we propose \emph{implicitly rewired message-passing neural networks} (IPR-MPNNs), a novel approach that integrates \emph{implicit} probabilistic graph rewiring into MPNNs. By introducing a small number of virtual nodes, i.e., adding additional nodes to a given graph and connecting them to existing nodes, in a differentiable, end-to-end manner, IPR-MPNNs enable long-distance message propagation, circumventing quadratic complexity. Theoretically, we demonstrate that IPR-MPNNs surpass the expressiveness of traditional MPNNs. Empirically, we validate our approach by showcasing its ability to mitigate under-reaching and over-squashing effects, achieving state-of-the-art performance across multiple graph datasets. Notably, IPR-MPNNs outperform graph transformers while maintaining significantly faster computational efficiency.
• Abstract（参考訳）: メッセージパッシンググラフニューラルネットワーク(MPNN)は、グラフベースの機械学習の強力なパラダイムとして登場した。 その効果にもかかわらず、MPNNは、制限された受容フィールドと構造的ボトルネックが、グラフ内の情報フローを妨げるという、過剰な取得や過剰な監視といった課題に直面している。 グラフトランスフォーマーはこれらの問題に対処することを約束するが、そのスケーラビリティはノード数に関する二次的な複雑さのために制限されており、より大きなグラフでは現実的ではない。 本稿では,<emph{implicit} Probabilistic graph rewiringをMPNNに組み込む新しいアプローチである,<emph{implicitly rewired message-passing Neural Network} (IPR-MPNNs)を提案する。 少数の仮想ノード、すなわち与えられたグラフに追加ノードを追加し、それを既存のノードに接続することで、IPR-MPNNは長距離メッセージの伝搬を可能にし、二次的な複雑さを回避する。 理論的には、IPR-MPNNが従来のMPNNの表現性を上回ることを示す。 経験的に、我々は、アンダーリーチングとオーバースキャッシングの効果を緩和し、複数のグラフデータセットにまたがって最先端のパフォーマンスを達成する能力を示すことによって、我々のアプローチを検証する。 特に、IPR-MPNNは、計算効率を著しく向上させながら、グラフ変換器より優れている。

関連論文リスト

• Spatio-Spectral Graph Neural Networks [50.277959544420455]
  比スペクトルグラフネットワーク(S$2$GNN)を提案する。 S$2$GNNは空間的およびスペクトル的にパラメータ化されたグラフフィルタを組み合わせる。 S$2$GNNsは、MPGNNsよりも厳密な近似理論誤差境界を生じる。
  論文  参考訳（メタデータ） (2024-05-29T14:28:08Z)
• Graph Coordinates and Conventional Neural Networks -- An Alternative for Graph Neural Networks [0.10923877073891444]
  メッセージパッシングGNNの新たな代替手段として,Topology Coordinate Neural Network (TCNN) と Directional Virtual Coordinate Neural Network (DVCNN) を提案する。 TCNNとDVCNNは、メッセージパッシングGNNの競合や優れたパフォーマンスを達成する。 私たちの研究は、グラフベースの機械学習のためのテクニックのツールボックスを拡張します。
  論文  参考訳（メタデータ） (2023-12-03T10:14:10Z)
• Probabilistically Rewired Message-Passing Neural Networks [41.554499944141654]
  メッセージパッシンググラフニューラルネットワーク(MPNN)は、グラフ構造化入力を処理する強力なツールとして登場した。 MPNNは、潜在的なノイズや欠落した情報を無視して、固定された入力グラフ構造で動作する。 確率的に再構成されたMPNN(PR-MPNN)を考案し、より有益なものを省略しながら、関連するエッジを追加することを学習する。
  論文  参考訳（メタデータ） (2023-10-03T15:43:59Z)
• Transferability of Graph Neural Networks using Graphon and Sampling Theories [0.0]
  グラフニューラルネットワーク(GNN)は、さまざまなドメインでグラフベースの情報を処理するための強力なツールとなっている。 GNNの望ましい特性は転送可能性であり、トレーニングされたネットワークは、その正確性を再トレーニングすることなく、異なるグラフから情報を交換することができる。 我々は,2層グラファイトニューラルネットワーク(WNN)アーキテクチャを明示することにより,GNNへのグラファイトの適用に寄与する。
  論文  参考訳（メタデータ） (2023-07-25T02:11:41Z)
• Training Graph Neural Networks on Growing Stochastic Graphs [114.75710379125412]
  グラフニューラルネットワーク(GNN)は、ネットワーク化されたデータの意味のあるパターンを活用するために、グラフ畳み込みに依存している。 我々は,成長するグラフ列の極限オブジェクトであるグラフオンを利用して,非常に大きなグラフ上のGNNを学習することを提案する。
  論文  参考訳（メタデータ） (2022-10-27T16:00:45Z)
• Spiking Variational Graph Auto-Encoders for Efficient Graph Representation Learning [10.65760757021534]
  本稿では,効率的なグラフ表現学習のためのSNNに基づく深層生成手法,すなわちSpking Variational Graph Auto-Encoders (S-VGAE)を提案する。 我々は,複数のベンチマークグラフデータセット上でリンク予測実験を行い,この結果から,グラフ表現学習における他のANNやSNNに匹敵する性能で,より少ないエネルギーを消費することを示した。
  論文  参考訳（メタデータ） (2022-10-24T12:54:41Z)
• Dynamic Graph Message Passing Networks for Visual Recognition [112.49513303433606]
  長距離依存のモデリングは、コンピュータビジョンにおけるシーン理解タスクに不可欠である。 完全連結グラフはそのようなモデリングには有益であるが、計算オーバーヘッドは禁じられている。 本稿では,計算複雑性を大幅に低減する動的グラフメッセージパッシングネットワークを提案する。
  論文  参考訳（メタデータ） (2022-09-20T14:41:37Z)
• Increase and Conquer: Training Graph Neural Networks on Growing Graphs [116.03137405192356]
  本稿では,このグラフからBernoulliをサンプリングしたグラフ上でGNNをトレーニングすることで,WNN(Graphon Neural Network)を学習する問題を考察する。 これらの結果から着想を得た大規模グラフ上でGNNを学習するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-07T15:05:59Z)
• Uniting Heterogeneity, Inductiveness, and Efficiency for Graph Representation Learning [68.97378785686723]
  グラフニューラルネットワーク(GNN)は,グラフ上のノード表現学習の性能を大幅に向上させた。 GNNの過半数クラスは均質グラフのためにのみ設計されており、より有益な異種グラフに劣る適応性をもたらす。 本稿では,低次ノードと高次ノードの両方のエッジに付随するヘテロジニアスなノード特徴をパッケージ化する,新しい帰納的メタパスフリーメッセージパッシング方式を提案する。
  論文  参考訳（メタデータ） (2021-04-04T23:31:39Z)
• Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Results [58.277290855841976]
  グラフニューラルネットワーク(GNN)の計算コストと表現力のトレードオフについて検討する。 新しいモデルでは、$k$のサブグラフをカウントでき、低次GNNの既知の制限を克服できることを示す。 いくつかの場合において、提案アルゴリズムは既存の高階$k$-GNNに比べて計算量を大幅に削減することができる。
  論文  参考訳（メタデータ） (2020-12-06T03:42:54Z)

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

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