Fugu-MT 論文翻訳(概要): Equivariant Polynomials for Graph Neural Networks

論文の概要: Equivariant Polynomials for Graph Neural Networks

arxiv url: http://arxiv.org/abs/2302.11556v1
Date: Wed, 22 Feb 2023 18:53:38 GMT
ステータス: 処理完了
システム内更新日: 2023-02-23 14:08:43.620583
Title: Equivariant Polynomials for Graph Neural Networks
Title（参考訳）: グラフニューラルネットワークのための等変多項式
Authors: Omri Puny, Derek Lim, Bobak T. Kiani, Haggai Maron, Yaron Lipman
Abstract要約: グラフネットワーク(GNN)は本質的に表現力に制限がある。本稿では、GNNがある程度の同変を計算する能力に基づく代替パワー階層を提案する。これらの強化されたGNNは、複数のグラフ学習ベンチマークの実験において最先端の結果を示す。
参考スコア（独自算出の注目度）: 38.15983687193912
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Graph Neural Networks (GNN) are inherently limited in their expressive power. Recent seminal works (Xu et al., 2019; Morris et al., 2019b) introduced the Weisfeiler-Lehman (WL) hierarchy as a measure of expressive power. Although this hierarchy has propelled significant advances in GNN analysis and architecture developments, it suffers from several significant limitations. These include a complex definition that lacks direct guidance for model improvement and a WL hierarchy that is too coarse to study current GNNs. This paper introduces an alternative expressive power hierarchy based on the ability of GNNs to calculate equivariant polynomials of a certain degree. As a first step, we provide a full characterization of all equivariant graph polynomials by introducing a concrete basis, significantly generalizing previous results. Each basis element corresponds to a specific multi-graph, and its computation over some graph data input corresponds to a tensor contraction problem. Second, we propose algorithmic tools for evaluating the expressiveness of GNNs using tensor contraction sequences, and calculate the expressive power of popular GNNs. Finally, we enhance the expressivity of common GNN architectures by adding polynomial features or additional operations / aggregations inspired by our theory. These enhanced GNNs demonstrate state-of-the-art results in experiments across multiple graph learning benchmarks.
Abstract（参考訳）: グラフニューラルネットワーク(GNN)は本質的に表現力に制限がある。最近のセミナー作品(Xu et al., 2019; Morris et al., 2019b)は、表現力の尺度としてWeisfeiler-Lehman階層を導入した。この階層構造は、GNN分析とアーキテクチャ開発に大きな進歩をもたらしたが、いくつかの重大な制限に悩まされている。これには、モデル改善のための直接的なガイダンスが欠けている複雑な定義と、現在のGNNを研究するには大きすぎるWL階層が含まれる。本稿では、GNNが等変多項式をある程度計算する能力に基づいて、別の表現力階層を提案する。最初のステップとして、具体的基礎を導入し、前の結果を著しく一般化することで、すべての同変グラフ多項式の完全な特徴づけを提供する。各基底要素は特定の多重グラフに対応し、そのグラフデータ入力上の計算はテンソル収縮問題に対応する。第2に、テンソルの縮約配列を用いてGNNの表現性を評価するアルゴリズムツールを提案し、人気のあるGNNの表現力を算出する。最後に,この理論に触発された多項式特徴や演算・集約を追加することで,共通gnnアーキテクチャの表現性を高める。これらの強化されたGNNは、複数のグラフ学習ベンチマークの実験において最先端の結果を示す。

関連論文リスト

A Manifold Perspective on the Statistical Generalization of Graph Neural Networks [84.01980526069075]
我々は、スペクトル領域の多様体からサンプリングされたグラフ上のGNNの統計的一般化理論を確立するために多様体の視点を取る。我々はGNNの一般化境界が対数スケールのグラフのサイズとともに線形に減少し、フィルタ関数のスペクトル連続定数とともに線形的に増加することを証明した。
論文参考訳（メタデータ） (2024-06-07T19:25:02Z)
Uplifting the Expressive Power of Graph Neural Networks through Graph Partitioning [3.236774847052122]
グラフ分割のレンズによるグラフニューラルネットワークの表現力について検討する。我々は新しいGNNアーキテクチャ、すなわちグラフ分割ニューラルネットワーク(GPNN)を導入する。
論文参考訳（メタデータ） (2023-12-14T06:08:35Z)
A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Tests [30.558563815430418]
GNN(Subgraph Neural Network)は、表現型グラフニューラルネットワーク(GNN)を開発するための重要な方向として登場した。本稿では,WIP(Subgraph Weisfeiler-Lehman Tests)のレンズを用いた一般ノードベースサブグラフGNNの系統的研究を行う。ノードベースの部分グラフ GNN が 6 つのSWL 等価クラスのうちの 1 つに該当することを証明し、その中で $mathsfSSWL$ が最大表現力を達成する。
論文参考訳（メタデータ） (2023-02-14T14:42:54Z)
Towards Better Generalization with Flexible Representation of Multi-Module Graph Neural Networks [0.27195102129094995]
ランダムグラフ生成器を用いて,グラフサイズと構造特性がGNNの予測性能に与える影響について検討する。本稿では,GNNが未知のグラフに一般化できるかどうかを決定する上で,平均ノード次数が重要な特徴であることを示す。集約された入力に対して単一の正準非線形変換を一般化することにより、ネットワークが新しいグラフに柔軟に対応可能なマルチモジュールGNNフレームワークを提案する。
論文参考訳（メタデータ） (2022-09-14T12:13:59Z)
Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
論文参考訳（メタデータ） (2022-05-19T18:40:25Z)
Expressiveness and Approximation Properties of Graph Neural Networks [6.1323142294300625]
Wesfeiler-Leman (WL) テストの観点で GNN の分離パワーのバウンダリを得るためのエレガントな方法を提供する。我々はテンソル言語を用いて、MPNNの自然な拡張である高次メッセージパッシングニューラルネットワーク(またはk-MPNN)を定義する。提案手法は,GNNアーキテクチャ設計者がGNNの分離パワーを解析できるツールボックスを提供する。
論文参考訳（メタデータ） (2022-04-10T11:33:04Z)
The Surprising Power of Graph Neural Networks with Random Node Initialization [54.4101931234922]
グラフニューラルネットワーク(GNN)は、関係データ上での表現学習に有効なモデルである。標準 GNN はその表現力に制限があり、Weisfeiler-Leman グラフ同型(英語版)の能力以外の区別はできない。本研究では,ランダムノード(RNI)を用いたGNNの表現力の解析を行う。我々はこれらのモデルが普遍的であることを証明し、GNNが高次特性の計算に頼らない最初の結果である。
論文参考訳（メタデータ） (2020-10-02T19:53:05Z)
Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。 GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
論文参考訳（メタデータ） (2020-08-31T23:15:40Z)
Expressive Power of Invariant and Equivariant Graph Neural Networks [10.419350129060598]
Folklore Graph Neural Networks (FGNN) は、与えられたテンソル次数に対してこれまで提案されてきた最も表現力のあるアーキテクチャである。 FGNNはこの問題の解決方法を学ぶことができ、既存のアルゴリズムよりも平均的なパフォーマンスが向上する。
論文参考訳（メタデータ） (2020-06-28T16:35:45Z)
Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。 Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
論文参考訳（メタデータ） (2020-06-16T15:30:31Z)
Eigen-GNN: A Graph Structure Preserving Plug-in for GNNs [95.63153473559865]
グラフニューラルネットワーク(GNN)は、グラフ上の新たな機械学習モデルである。既存のGNNモデルの多くは浅く、本質的に機能中心である。我々は,既存の浅いGNNがグラフ構造をよく保存できないことを経験的かつ解析的に示す。本稿では,グラフ構造保存におけるGNNの能力を高めるプラグインモジュールであるEigen-GNNを提案する。
論文参考訳（メタデータ） (2020-06-08T02:47:38Z)

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

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