論文の概要: Some Might Say All You Need Is Sum

• arxiv url: http://arxiv.org/abs/2302.11603v2
• Date: Fri, 19 May 2023 10:34:37 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-22 18:55:34.773344
• Title: Some Might Say All You Need Is Sum
• Title（参考訳）: 知っておくべきことすべては「サム」だ
• Authors: Eran Rosenbluth, Jan Toenshoff, Martin Grohe
• Abstract要約: グラフニューラルネットワーク(GNN)の表現性は、採用する集約関数に依存する。 我々は,Mean や Max GNN によって正確に計算できる基本関数が任意の Sum GNN によって近似できないことを証明した。
• 参考スコア（独自算出の注目度）: 2.226803104060345
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: The expressivity of Graph Neural Networks (GNNs) is dependent on the aggregation functions they employ. Theoretical works have pointed towards Sum aggregation GNNs subsuming every other GNNs, while certain practical works have observed a clear advantage to using Mean and Max. An examination of the theoretical guarantee identifies two caveats. First, it is size-restricted, that is, the power of every specific GNN is limited to graphs of a specific size. Successfully processing larger graphs may require an other GNN, and so on. Second, it concerns the power to distinguish non-isomorphic graphs, not the power to approximate general functions on graphs, and the former does not necessarily imply the latter. It is desired that a GNN's usability will not be limited to graphs of any specific size. Therefore, we explore the realm of unrestricted-size expressivity. We prove that basic functions, which can be computed exactly by Mean or Max GNNs, are inapproximable by any Sum GNN. We prove that under certain restrictions, every Mean or Max GNN can be approximated by a Sum GNN, but even there, a combination of (Sum, [Mean/Max]) is more expressive than Sum alone. Lastly, we prove further expressivity limitations for GNNs with a broad class of aggregations.
• Abstract（参考訳）: グラフニューラルネットワーク(gnns)の表現性は、それらが採用する集約関数に依存する。 理論的な研究は、他のすべてのGNNを仮定する Sumアグリゲーション GNN に向けられているが、ある実践的な研究は、Mean と Max を使うことに対する明確な優位性を観察している。 理論的保証の検証は2つの注意事項を識別する。 第一に、それはサイズ制限され、すなわち、特定のGNNのパワーは特定のサイズのグラフに制限される。 より大きなグラフを処理するには、他のGNNなどが必要になる。 第二に、グラフ上の一般函数を近似する力ではなく、非同型グラフを区別する力に関係しており、前者は必ずしも後者を含まない。 GNNのユーザビリティは、特定のサイズのグラフに制限されないことが望ましい。 したがって,非制限サイズ表現の領域を探索する。 我々は,Mean や Max GNN によって正確に計算できる基本関数が任意の Sum GNN によって近似できないことを証明した。 一定の制限の下では、すべての平均または最大 GNN は Sum GNN によって近似できるが、そこでさえも (Sum, [Mean/Max]) の組み合わせは Sum 単独よりも表現力が高い。 最後に,広範に集約されたGNNに対して,さらなる表現性制限を証明した。

関連論文リスト

• Is uniform expressivity too restrictive? Towards efficient expressivity of graph neural networks [0.6445605125467574]
  グラフニューラルネットワーク(GNN)は、入力グラフのサイズによってパラメータなしでクエリを表現できる。 入力グラフの最大次数に対してパラメータの数が対数的であるように,多くのGNNがGC2クエリを効率的に表現できることを示す。
  論文  参考訳（メタデータ） (2024-10-02T18:09:12Z)
• A Manifold Perspective on the Statistical Generalization of Graph Neural Networks [84.01980526069075]
  我々は、スペクトル領域の多様体からサンプリングされたグラフ上のGNNの統計的一般化理論を確立するために多様体の視点を取る。 我々はGNNの一般化境界が対数スケールのグラフのサイズとともに線形に減少し、フィルタ関数のスペクトル連続定数とともに線形的に増加することを証明した。
  論文  参考訳（メタデータ） (2024-06-07T19:25:02Z)
• Spatio-Spectral Graph Neural Networks [50.277959544420455]
  比スペクトルグラフネットワーク(S$2$GNN)を提案する。 S$2$GNNは空間的およびスペクトル的にパラメータ化されたグラフフィルタを組み合わせる。 S$2$GNNsは、MPGNNsよりも厳密な近似理論誤差境界を生じる。
  論文  参考訳（メタデータ） (2024-05-29T14:28:08Z)
• The logic of rational graph neural networks [0.7614628596146602]
  我々は,GC2 の深度 3$ のクエリは,合理的なアクティベーション関数を持つ GNN では表現できないことを証明した。 これは、すべての非ポリノミカル活性化関数がGNNの最大表現性を参照しているわけではないことを示している。 また、一階述語論理(RGC2)の有理サブフラグメントを示し、すべてのグラフに対して有理GNNがRGC2クエリを均一に表現できることを証明する。
  論文  参考訳（メタデータ） (2023-10-19T20:32:25Z)
• Distance-Restricted Folklore Weisfeiler-Leman GNNs with Provable Cycle Counting Power [27.929167547127207]
  グラフニューラルネットワーク(GNN)の特定のグラフサブ構造、特にサイクルをカウントする能力は重要である。 本稿では,GNNの新しいクラスとして$d$-Distance-Restricted FWL(2) GNNを提案する。 我々のモデルは今までで最も効率的なGNNモデルであり、最大6サイクルまで数えることができる。
  論文  参考訳（メタデータ） (2023-09-10T06:13:29Z)
• On the Correspondence Between Monotonic Max-Sum GNNs and Datalog [19.288835943223816]
  グラフニューラルネットワーク(GNN)に基づくデータ変換の研究 最大および総和集約関数を持つGNNのサブクラスをカバーするモノトニックマックスサムGNNの表現性について検討する。
  論文  参考訳（メタデータ） (2023-05-29T11:13:38Z)
• On the approximation capability of GNNs in node classification/regression tasks [4.141514895639094]
  グラフニューラルネットワーク(GNN)は、グラフ処理のための幅広い種類の接続モデルである。 GNNはノード分類/回帰タスクの確率の普遍近似であることを示す。
  論文  参考訳（メタデータ） (2021-06-16T17:46:51Z)
• A Unified Lottery Ticket Hypothesis for Graph Neural Networks [82.31087406264437]
  本稿では,グラフ隣接行列とモデルの重み付けを同時に行う統一GNNスペーシフィケーション(UGS)フレームワークを提案する。 グラフ宝くじ(GLT)をコアサブデータセットとスパースサブネットワークのペアとして定義することにより、人気のある宝くじチケット仮説を初めてGNNsにさらに一般化します。
  論文  参考訳（メタデータ） (2021-02-12T21:52:43Z)
• 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)
• Eigen-GNN: A Graph Structure Preserving Plug-in for GNNs [95.63153473559865]
  グラフニューラルネットワーク(GNN)は、グラフ上の新たな機械学習モデルである。 既存のGNNモデルの多くは浅く、本質的に機能中心である。 我々は,既存の浅いGNNがグラフ構造をよく保存できないことを経験的かつ解析的に示す。 本稿では,グラフ構造保存におけるGNNの能力を高めるプラグインモジュールであるEigen-GNNを提案する。
  論文  参考訳（メタデータ） (2020-06-08T02:47:38Z)

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

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