論文の概要: A Practical, Progressively-Expressive GNN

• arxiv url: http://arxiv.org/abs/2210.09521v1
• Date: Tue, 18 Oct 2022 01:27:21 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-19 15:25:06.604550
• Title: A Practical, Progressively-Expressive GNN
• Title（参考訳）: プログレッシブ圧縮型GNN
• Authors: Lingxiao Zhao, Louis H\"artel, Neil Shah, Leman Akoglu
• Abstract要約: 近年,メッセージパッシングニューラルネットワーク(MPNN)がグラフニューラルネットワーク(GNN)の主流となっている。 MPNNは、グラフ同型テストのフレームワークにおいてグラフを区別する1次元のWeisfeiler-Leman (1-WL)テストと同じくらい強力である。 我々は,k-tuples ノードから =c 連結成分上で定義された=k ノードの集合へ移動することで,k-WL から k-WL への複雑性を大幅に低減した (k, c)(=)-SETWL 階層を提案する。
• 参考スコア（独自算出の注目度）: 27.267362661067285
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Message passing neural networks (MPNNs) have become a dominant flavor of graph neural networks (GNNs) in recent years. Yet, MPNNs come with notable limitations; namely, they are at most as powerful as the 1-dimensional Weisfeiler-Leman (1-WL) test in distinguishing graphs in a graph isomorphism testing frame-work. To this end, researchers have drawn inspiration from the k-WL hierarchy to develop more expressive GNNs. However, current k-WL-equivalent GNNs are not practical for even small values of k, as k-WL becomes combinatorially more complex as k grows. At the same time, several works have found great empirical success in graph learning tasks without highly expressive models, implying that chasing expressiveness with a coarse-grained ruler of expressivity like k-WL is often unneeded in practical tasks. To truly understand the expressiveness-complexity tradeoff, one desires a more fine-grained ruler, which can more gradually increase expressiveness. Our work puts forth such a proposal: Namely, we first propose the (k, c)(<=)-SETWL hierarchy with greatly reduced complexity from k-WL, achieved by moving from k-tuples of nodes to sets with <=k nodes defined over <=c connected components in the induced original graph. We show favorable theoretical results for this model in relation to k-WL, and concretize it via (k, c)(<=)-SETGNN, which is as expressive as (k, c)(<=)-SETWL. Our model is practical and progressively-expressive, increasing in power with k and c. We demonstrate effectiveness on several benchmark datasets, achieving several state-of-the-art results with runtime and memory usage applicable to practical graphs. We open source our implementation at https://github.com/LingxiaoShawn/KCSetGNN.
• Abstract（参考訳）: 近年,メッセージパッシングニューラルネットワーク(MPNN)がグラフニューラルネットワーク(GNN)の主流となっている。 しかし、MPNNには顕著な制限があり、すなわち、グラフ同型テストのフレームワークにおいてグラフを区別する1次元のWeisfeiler-Leman (1-WL)テストと同じくらい強力である。 この目的のために、研究者はより表現力のあるGNNを開発するためにk-WL階層からインスピレーションを得ている。 しかし、現在の k-WL 等価 GNN は k の小さい値に対しても実用的ではない。 同時に、グラフ学習タスクにおいて高度に表現力のあるモデルを持たずに大きな実験的な成功をおさめ、k-WLのような表現力の粗い支配者による表現力の追跡は、実際的なタスクでは不要な場合が多いことを示唆している。 表現性と複雑さのトレードオフを真に理解するために、よりきめ細かい定規を欲しがる。 k, c)(<=)-setwl階層をk-wl階層から大きく縮小し、ノードのk-タプルから<=kノードが誘導された元のグラフの<=c接続されたコンポーネント上で定義される集合へと移行させることにより、最初に提案する。 我々は、k-WLに関して、このモデルに有利な理論的結果を示し、(k, c)(<=)-SETGNNを用いて、(k, c)(<=)-SETWLと同じくらい表現的である。 我々のモデルは実践的かつ漸進的に表現され、k と c でパワーが増大する。 我々は,いくつかのベンチマークデータセットで有効性を実証し,実用グラフに適用可能な実行時およびメモリ使用量を用いて,最先端の結果を複数達成した。 実装はhttps://github.com/LingxiaoShawn/KCSetGNNで公開しています。

関連論文リスト

• How Graph Neural Networks Learn: Lessons from Training Dynamics [80.41778059014393]
  グラフニューラルネットワーク(GNN)の関数空間におけるトレーニングダイナミクスについて検討する。 GNNの勾配勾配勾配最適化は暗黙的にグラフ構造を利用して学習関数を更新する。 この発見は、学習したGNN関数が一般化した時期と理由に関する新たな解釈可能な洞察を提供する。
  論文  参考訳（メタデータ） (2023-10-08T10:19:56Z)
• Equivariant Polynomials for Graph Neural Networks [38.15983687193912]
  グラフネットワーク(GNN)は本質的に表現力に制限がある。 本稿では、GNNがある程度の同変を計算する能力に基づく代替パワー階層を提案する。 これらの強化されたGNNは、複数のグラフ学習ベンチマークの実験において最先端の結果を示す。
  論文  参考訳（メタデータ） (2023-02-22T18:53:38Z)
• 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)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。 また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
  論文  参考訳（メタデータ） (2022-05-19T18:40:25Z)
• 1-WL Expressiveness Is (Almost) All You Need [3.4012007729454807]
  メッセージパッシングニューラルネットワーク (MPNN) は、一階のWeisfeiler-Leman (1-WL) グラフ同型テストと同型である。 本研究では,MPNNや他の標準グラフデータセットのWLモデルにおいて,限定表現性が実際に制限要因であるかどうかを解析する。
  論文  参考訳（メタデータ） (2022-02-21T12:05:06Z)
• Weisfeiler and Lehman Go Cellular: CW Networks [3.0017241250121383]
  グラフニューラルネットワーク(GNN)は、表現力に制限があり、長距離相互作用に苦慮し、高次構造をモデル化する原則的な方法が欠けている。 SC の最近の理論的結果は、SC とグラフを柔軟にサブスムする位相対象である正則なセルコンプレックスに拡張する。 この一般化は、グラフリフトの変換の強力なセットを提供し、それぞれがユニークなメッセージパッシング手順につながることを示す。
  論文  参考訳（メタデータ） (2021-06-23T17:59:16Z)
• Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Results [58.277290855841976]
  グラフニューラルネットワーク(GNN)の計算コストと表現力のトレードオフについて検討する。 新しいモデルでは、$k$のサブグラフをカウントでき、低次GNNの既知の制限を克服できることを示す。 いくつかの場合において、提案アルゴリズムは既存の高階$k$-GNNに比べて計算量を大幅に削減することができる。
  論文  参考訳（メタデータ） (2020-12-06T03:42:54Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。 GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。 より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。 本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
  論文  参考訳（メタデータ） (2020-08-31T23:15:40Z)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。 Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。 グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
  論文  参考訳（メタデータ） (2020-06-16T15:30:31Z)
• Can Graph Neural Networks Count Substructures? [53.256112515435355]
  グラフニューラルネットワーク(GNN)の能力について,属性付きグラフサブ構造をカウントする能力を用いて検討する。 我々は2種類のサブストラクチャカウントを区別する: インダクションサブグラフカウントとサブグラフカウント、および人気のあるGNNアーキテクチャに対する肯定的および否定的な回答である。
  論文  参考訳（メタデータ） (2020-02-10T18:53:30Z)

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

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