論文の概要: 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アーキテクチャのバリエーションを紹介する。
実験結果は理論的な結果の妥当性を確認した。
関連論文リスト
- Future Directions in Foundations of Graph Machine Learning [49.049992612331685]
グラフ上の機械学習、特にグラフニューラルネットワーク(GNN)を用いた場合、関心が急増している。
その実用的成功にもかかわらず、GNNの特性に関する理論的理解は非常に不完全である。
論文 参考訳(メタデータ) (2024-02-03T22:55:31Z) - DGNN: Decoupled Graph Neural Networks with Structural Consistency
between Attribute and Graph Embedding Representations [62.04558318166396]
グラフニューラルネットワーク(GNN)は、複雑な構造を持つグラフ上での表現学習の堅牢性を示す。
ノードのより包括的な埋め込み表現を得るために、Decoupled Graph Neural Networks (DGNN)と呼ばれる新しいGNNフレームワークが導入された。
複数のグラフベンチマークデータセットを用いて、ノード分類タスクにおけるDGNNの優位性を検証した。
論文 参考訳(メタデータ) (2024-01-28T06:43:13Z) - 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) - Equivariant Subgraph Aggregation Networks [23.26140936226352]
本稿では,この問題に対処するためのEquivariant Subgraph Aggregation Networks (ESAN) という新しいフレームワークを提案する。
2つのグラフはMPNNでは区別できないかもしれないが、しばしば区別可能な部分グラフを含む。
グラフ同型に対する1次元Weisfeiler-Leman(1-WL)テストの新しい変種を開発し、ESANの表現性に対する下界を証明した。
サブグラフ選択ポリシーや同変ニューラルアーキテクチャといった設計選択がアーキテクチャの表現力にどのように影響するかを記述する理論的結果を提供する。
論文 参考訳(メタデータ) (2021-10-06T16:45:07Z) - Improving Graph Neural Network Expressivity via Subgraph Isomorphism
Counting [63.04999833264299]
グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。
Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。
グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
論文 参考訳(メタデータ) (2020-06-16T15:30:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。