論文の概要: Weisfeiler-Leman at the margin: When more expressivity matters

• arxiv url: http://arxiv.org/abs/2402.07568v1
• Date: Mon, 12 Feb 2024 11:03:52 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-13 14:44:10.718260
• Title: Weisfeiler-Leman at the margin: When more expressivity matters
• Title（参考訳）: Weisfeiler-Leman氏:もっと表現力が重要な時
• Authors: Billy J. Franks, Christopher Morris, Ameya Velingker, and Floris Geerts
• Abstract要約: アーキテクチャの表現性は、グラフ同型を通して見るときの一般化性能に関する限られた洞察を与えることを示す。 本稿では,表現力のある1ドルWLベースのカーネルとMPNNアーキテクチャと,証明可能な一般化特性を導入したMPNNアーキテクチャを提案する。
• 参考スコア（独自算出の注目度）: 10.192184857243666
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Weisfeiler-Leman algorithm ($1$-WL) is a well-studied heuristic for the graph isomorphism problem. Recently, the algorithm has played a prominent role in understanding the expressive power of message-passing graph neural networks (MPNNs) and being effective as a graph kernel. Despite its success, $1$-WL faces challenges in distinguishing non-isomorphic graphs, leading to the development of more expressive MPNN and kernel architectures. However, the relationship between enhanced expressivity and improved generalization performance remains unclear. Here, we show that an architecture's expressivity offers limited insights into its generalization performance when viewed through graph isomorphism. Moreover, we focus on augmenting $1$-WL and MPNNs with subgraph information and employ classical margin theory to investigate the conditions under which an architecture's increased expressivity aligns with improved generalization performance. In addition, we show that gradient flow pushes the MPNN's weights toward the maximum margin solution. Further, we introduce variations of expressive $1$-WL-based kernel and MPNN architectures with provable generalization properties. Our empirical study confirms the validity of our theoretical findings.
• Abstract（参考訳）: Weisfeiler-Lemanアルゴリズム(1$-WL)はグラフ同型問題に対するよく研究されたヒューリスティックである。 近年、このアルゴリズムは、メッセージパッシンググラフニューラルネットワーク(mpnn)の表現力の理解と、グラフカーネルとしての有効性において重要な役割を果たしている。 その成功にもかかわらず、1ドルWLは非同型グラフを区別する問題に直面し、より表現力のあるMPNNとカーネルアーキテクチャの開発に繋がる。 しかし,表現性向上と一般化性能向上の関係はいまだ不明である。 ここで、アーキテクチャの表現性は、グラフ同型を通して見るとき、その一般化性能に関する限られた洞察を与える。 さらに,サブグラフ情報による$$$-wlとmpnnの強化に着目し,古典的マージン理論を用いて,アーキテクチャの表現率の増大が一般化性能の向上と一致する条件を検討する。 さらに, 勾配流がMPNNの重み付けを最大限界解へ押し上げることを示す。 さらに,表現力のある1ドルWLベースのカーネルとMPNNアーキテクチャのバリエーションを紹介する。 実験結果は理論的な結果の妥当性を確認した。

関連論文リスト

• Towards Bridging Generalization and Expressivity of Graph Neural Networks [11.560730203511111]
  グラフニューラルネットワーク(GNN)における表現性と一般化の関係について検討する。 本稿では,GNNの一般化と,それらが捉えることのできるグラフ構造の分散を結合する新しいフレームワークを提案する。 我々は,クラス内濃度とクラス間分離のトレードオフを明らかにする。
  論文  参考訳（メタデータ） (2024-10-14T00:31:16Z)
• A Manifold Perspective on the Statistical Generalization of Graph Neural Networks [84.01980526069075]
  我々は、スペクトル領域の多様体からサンプリングされたグラフ上のGNNの統計的一般化理論を確立するために多様体の視点を取る。 我々はGNNの一般化境界が対数スケールのグラフのサイズとともに線形に減少し、フィルタ関数のスペクトル連続定数とともに線形的に増加することを証明した。
  論文  参考訳（メタデータ） (2024-06-07T19:25:02Z)
• Future Directions in the Theory of Graph Machine Learning [49.049992612331685]
  グラフ上の機械学習、特にグラフニューラルネットワーク(GNN)を使用すると、グラフデータが広く利用できるため、関心が高まっている。 実際の成功にもかかわらず、GNNの特性に関する理論的理解は非常に不完全である。
  論文  参考訳（メタデータ） (2024-02-03T22:55:31Z)
• Fine-grained Expressivity of Graph Neural Networks [15.766353435658043]
  我々は1ドルWLとMPNNの連続的な拡張をグラファイトに検討する。 連続的な1ドルWLの変動は,MPNNのグラフ上での表現力の正確なトポロジ的特徴を与えることを示す。 また,グラフ距離の保存能力に基づいて,異なるMPNNアーキテクチャの評価を行った。
  論文  参考訳（メタデータ） (2023-06-06T14:12:23Z)
• Improving Expressivity of GNNs with Subgraph-specific Factor Embedded Normalization [30.86182962089487]
  グラフニューラルネットワーク(GNN)は、グラフ構造化データを扱うための学習アーキテクチャの強力なカテゴリとして登場した。 我々は SUbgraph-sPEcific FactoR Embedded Normalization (SuperNorm) と呼ばれる専用プラグアンドプレイ正規化方式を提案する。
  論文  参考訳（メタデータ） (2023-05-31T14:37:31Z)
• On the Expressiveness and Generalization of Hypergraph Neural Networks [77.65788763444877]
  この拡張抽象化はハイパーグラフニューラルネットワーク(HyperGNN)の表現性、学習、および(構造的)一般化を分析するためのフレームワークを記述する。 具体的には、HyperGNNが有限データセットからどのように学習し、任意の入力サイズのグラフ推論問題に構造的に一般化するかに焦点を当てる。
  論文  参考訳（メタデータ） (2023-03-09T18:42:18Z)
• 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)
• Gradient Gating for Deep Multi-Rate Learning on Graphs [62.25886489571097]
  グラフニューラルネットワーク(GNN)の性能向上のための新しいフレームワークであるグラディエントゲーティング(G$2$)を提案する。 我々のフレームワークは,GNN層の出力を,基盤となるグラフのノード間でのメッセージパッシング情報のマルチレートフローのメカニズムでゲーティングすることに基づいている。
  論文  参考訳（メタデータ） (2022-10-02T13:19:48Z)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。 また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
  論文  参考訳（メタデータ） (2022-05-19T18:40:25Z)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。 Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。 グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
  論文  参考訳（メタデータ） (2020-06-16T15:30:31Z)

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

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