論文の概要: Fine-grained Expressivity of Graph Neural Networks

• arxiv url: http://arxiv.org/abs/2306.03698v2
• Date: Thu, 2 Nov 2023 13:37:35 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-03 17:34:40.066747
• Title: Fine-grained Expressivity of Graph Neural Networks
• Title（参考訳）: グラフニューラルネットワークの細粒度表現性
• Authors: Jan B\"oker, Ron Levie, Ningyuan Huang, Soledad Villar, Christopher Morris
• Abstract要約: 我々は1ドルWLとMPNNの連続的な拡張をグラファイトに検討する。 連続的な1ドルWLの変動は,MPNNのグラフ上での表現力の正確なトポロジ的特徴を与えることを示す。 また,グラフ距離の保存能力に基づいて,異なるMPNNアーキテクチャの評価を行った。
• 参考スコア（独自算出の注目度）: 15.766353435658043
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Numerous recent works have analyzed the expressive power of message-passing graph neural networks (MPNNs), primarily utilizing combinatorial techniques such as the $1$-dimensional Weisfeiler-Leman test ($1$-WL) for the graph isomorphism problem. However, the graph isomorphism objective is inherently binary, not giving insights into the degree of similarity between two given graphs. This work resolves this issue by considering continuous extensions of both $1$-WL and MPNNs to graphons. Concretely, we show that the continuous variant of $1$-WL delivers an accurate topological characterization of the expressive power of MPNNs on graphons, revealing which graphs these networks can distinguish and the level of difficulty in separating them. We identify the finest topology where MPNNs separate points and prove a universal approximation theorem. Consequently, we provide a theoretical framework for graph and graphon similarity combining various topological variants of classical characterizations of the $1$-WL. In particular, we characterize the expressive power of MPNNs in terms of the tree distance, which is a graph distance based on the concept of fractional isomorphisms, and substructure counts via tree homomorphisms, showing that these concepts have the same expressive power as the $1$-WL and MPNNs on graphons. Empirically, we validate our theoretical findings by showing that randomly initialized MPNNs, without training, exhibit competitive performance compared to their trained counterparts. Moreover, we evaluate different MPNN architectures based on their ability to preserve graph distances, highlighting the significance of our continuous $1$-WL test in understanding MPNNs' expressivity.
• Abstract（参考訳）: グラフ同型問題に対する1ドルのWeisfeiler-Lemanテスト(1$-WL)のような組合せ手法を主に利用して、メッセージパッシンググラフニューラルネットワーク(MPNN)の表現力を分析した。 しかし、グラフ同型目的は本質的にバイナリであり、2つの与えられたグラフ間の類似度について洞察を与えない。 この研究は、1ドルのWLとMPNNをグラファイトに連続的に拡張することでこの問題を解決する。 具体的には,MPNNのグラフ上での表現力の正確なトポロジ的特徴を提示し,これらのネットワークが区別できるグラフと分離の難しさのレベルを明らかにした。 我々はMPNNが点を分離し、普遍近似定理を証明する最も優れた位相を同定する。 その結果,1ドルWLの古典的特徴づけの様々な位相的不変量を組み合わせたグラフとグラフの類似性の理論的枠組みを提供する。 特に、分数同型の概念に基づくグラフ距離である木間距離(英語版)と木準同型(英語版)による部分構造数(英語版)という観点からMPNNの表現力を特徴づけ、これらの概念がグラフオン上の1ドルWLやMPNNと同じ表現力を持つことを示す。 実験により, ランダムに初期化したMPNNは, 訓練を受けずに, 訓練したMPNNと比較して, 競争性能を示すことを示した。 さらに,MPNNの表現性を理解する上での連続的な1ドルWLテストの重要性を強調し,グラフ距離を保存する能力に基づいて異なるMPNNアーキテクチャを評価する。

関連論文リスト

• Weisfeiler-Leman at the margin: When more expressivity matters [10.192184857243666]
  アーキテクチャの表現性は、グラフ同型を通して見るときの一般化性能に関する限られた洞察を与えることを示す。 本稿では,表現力のある1ドルWLベースのカーネルとMPNNアーキテクチャと,証明可能な一般化特性を導入したMPNNアーキテクチャを提案する。
  論文  参考訳（メタデータ） (2024-02-12T11:03:52Z)
• Uplifting the Expressive Power of Graph Neural Networks through Graph Partitioning [3.236774847052122]
  グラフ分割のレンズによるグラフニューラルネットワークの表現力について検討する。 我々は新しいGNNアーキテクチャ、すなわちグラフ分割ニューラルネットワーク(GPNN)を導入する。
  論文  参考訳（メタデータ） (2023-12-14T06:08:35Z)
• Generalization Limits of Graph Neural Networks in Identity Effects Learning [12.302336258860116]
  グラフニューラルネットワーク(GNN)は、さまざまなグラフドメインでデータ駆動学習を行う強力なツールとして登場した。 我々は、いわゆるアイデンティティ効果の学習において、GNNの新たな一般化特性と基本的限界を確立する。 我々の研究は、単純な認知タスクを行う際に、GNNの能力を理解する必要性によって動機付けられている。
  論文  参考訳（メタデータ） (2023-06-30T20:56:38Z)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。 また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
  論文  参考訳（メタデータ） (2022-05-19T18:40:25Z)
• Discovering the Representation Bottleneck of Graph Neural Networks from Multi-order Interactions [51.597480162777074]
  グラフニューラルネットワーク(GNN)は、ノード機能を伝搬し、インタラクションを構築するためにメッセージパッシングパラダイムに依存している。 最近の研究は、異なるグラフ学習タスクはノード間の異なる範囲の相互作用を必要とすることを指摘している。 科学領域における2つの共通グラフ構築法、すなわち、emphK-nearest neighbor(KNN)グラフとemphfully-connected(FC)グラフについて検討する。
  論文  参考訳（メタデータ） (2022-05-15T11:38:14Z)
• On Graph Neural Networks versus Graph-Augmented MLPs [51.23890789522705]
  Graph-Augmented Multi-Layer Perceptrons (GA-MLPs)は、まずグラフ上の特定のマルチホップ演算子でノード機能を拡張する。 我々は,GA-MLPとGNNの表現力の分離を証明し,指数関数的に成長することを示す。
  論文  参考訳（メタデータ） (2020-10-28T17:59:59Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。 GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。 より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。 本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
  論文  参考訳（メタデータ） (2020-08-31T23:15:40Z)
• Walk Message Passing Neural Networks and Second-Order Graph Neural Networks [4.355567556995855]
  我々は,新しいタイプのMPNNである$ell$-walk MPNNを紹介した。 2ドル(約2万円)のMPNNが表現力で2-WLと一致していることを示す。 特に、W[$ell$]を表現力で一致させるために、各層で$ell-1$行列乗法を許す。
  論文  参考訳（メタデータ） (2020-06-16T20:24:01Z)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。 Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。 グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
  論文  参考訳（メタデータ） (2020-06-16T15:30:31Z)
• How hard is to distinguish graphs with graph neural networks? [32.09819774228997]
  本研究では,メッセージパッシングモデル(MPNN)におけるグラフアイソモーフィズムの分類変種に対する硬度結果の導出を行う。 MPNNは、今日のグラフニューラルネットワークの大部分を包含しており、ノードにユニークな特徴が与えられた場合、普遍的である。 12のグラフ分類タスクと420のネットワークを含む実証的研究は、実際の性能と理論的予測の間に強い整合性を示す。
  論文  参考訳（メタデータ） (2020-05-13T22:28:46Z)
• Can Graph Neural Networks Count Substructures? [53.256112515435355]
  グラフニューラルネットワーク(GNN)の能力について,属性付きグラフサブ構造をカウントする能力を用いて検討する。 我々は2種類のサブストラクチャカウントを区別する: インダクションサブグラフカウントとサブグラフカウント、および人気のあるGNNアーキテクチャに対する肯定的および否定的な回答である。
  論文  参考訳（メタデータ） (2020-02-10T18:53:30Z)

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

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