論文の概要: Message Passing on the Edge: Towards Scalable and Expressive GNNs
- arxiv url: http://arxiv.org/abs/2510.13615v1
- Date: Wed, 15 Oct 2025 14:45:17 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-16 20:13:28.715682
- Title: Message Passing on the Edge: Towards Scalable and Expressive GNNs
- Title（参考訳）: エッジでのメッセージパッシング - スケーラブルで表現豊かなGNNを目指して
- Authors: Pablo Barceló, Fabian Jogl, Alexander Kozachinskiy, Matthias Lanzinger, Stefan Neumann, Cristóbal Rojas,
- Abstract要約: 本稿では,エッジベースのカラーリファインメントテストであるEB-1WLと,対応するGNNアーキテクチャであるEB-GNNを提案する。
我々のアーキテクチャは千葉・西関の古典的三角形計数アルゴリズムに着想を得ており、メッセージパッシング中に三角形を明示的に用いている。
- 参考スコア（独自算出の注目度）: 53.11031839861869
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We propose EB-1WL, an edge-based color-refinement test, and a corresponding GNN architecture, EB-GNN. Our architecture is inspired by a classic triangle counting algorithm by Chiba and Nishizeki, and explicitly uses triangles during message passing. We achieve the following results: (1)~EB-1WL is significantly more expressive than 1-WL. Further, we provide a complete logical characterization of EB-1WL based on first-order logic, and matching distinguishability results based on homomorphism counting. (2)~In an important distinction from previous proposals for more expressive GNN architectures, EB-1WL and EB-GNN require near-linear time and memory on practical graph learning tasks. (3)~Empirically, we show that EB-GNN is a highly-efficient general-purpose architecture: It substantially outperforms simple MPNNs, and remains competitive with task-specialized GNNs while being significantly more computationally efficient.
- Abstract（参考訳）: 本稿では,エッジベースのカラーリファインメントテストであるEB-1WLと,対応するGNNアーキテクチャであるEB-GNNを提案する。
我々のアーキテクチャは千葉・西関の古典的三角形計数アルゴリズムに着想を得ており、メッセージパッシング中に三角形を明示的に用いている。
1)~EB-1WLは1-WLよりもはるかに表現力が高い。
さらに、一階述語論理に基づくEB-1WLの完全論理的特徴付けと、同型カウントに基づく識別可能性のマッチングについて述べる。
2) より表現力のあるGNNアーキテクチャの提案とは違い,EB-1WL と EB-GNN は実用的なグラフ学習タスクにおいてほぼ線形時間とメモリを必要とする。
EB-GNNは単純なMPNNを実質的に上回り、タスク特化GNNと競合するが、計算効率は著しく高い。
関連論文リスト
- Rethinking the Expressive Power of GNNs via Graph Biconnectivity [45.4674360883544]
本稿では,グラフ双連結性による表現度指標の新たなクラスを導入し,理論と実践の両面での重要性を強調した。
我々は、GD-WL(Generalized Distance Weisfeiler-Lehman)と呼ばれる原理的で効率的なアプローチを導入する。
実際に,GD-WLをTransformerのようなアーキテクチャで実装し,完全な並列化性を保ち,実現可能であることを示す。
論文 参考訳（メタデータ） (2023-01-23T15:58:59Z) - Empowering GNNs via Edge-Aware Weisfeiler-Leman Algorithm [79.68451803954751]
メッセージパッシンググラフニューラルネットワーク(GNN)は1次元Weisfeiler-Leman (1-WL)アルゴリズムによって上界表現性を持つことが知られている。
本稿では,メッセージパッシング方式のスケーラビリティを保った汎用かつ実証可能なGNNフレームワークを提案する。
論文 参考訳（メタデータ） (2022-06-04T21:37:59Z) - Representation Power of Graph Neural Networks: Improved Expressivity via
Algebraic Analysis [124.97061497512804]
標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。
また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
論文 参考訳（メタデータ） (2022-05-19T18:40:25Z) - From Stars to Subgraphs: Uplifting Any GNN with Local Structure
Awareness [23.279464786779787]
私たちはMPNNをより表現力のあるものにするための一般的なフレームワークを導入します。
私たちのフレームワークは1&2-WLよりも強力で、3WLよりも強力です。
本手法は,いくつかのよく知られたグラフMLタスクに対して,新たな最先端性能を大きなマージンで設定する。
論文 参考訳（メタデータ） (2021-10-07T19:08:08Z) - Identity-aware Graph Neural Networks [63.6952975763946]
グラフニューラルネットワーク(ID-GNN)を1-WLテストよりも表現力の高いメッセージクラスを開発しています。
ID-GNNは、メッセージパッシング中にノードのIDを誘導的に考慮することにより、既存のGNNアーキテクチャを拡張します。
既存のGNNをID-GNNに変換すると、挑戦ノード、エッジ、グラフプロパティ予測タスクの平均40%の精度が向上することを示す。
論文 参考訳（メタデータ） (2021-01-25T18:59:01Z) - Distance Encoding: Design Provably More Powerful Neural Networks for
Graph Representation Learning [63.97983530843762]
グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。
GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。
より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。
本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
論文 参考訳（メタデータ） (2020-08-31T23:15:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。