論文の概要: Is uniform expressivity too restrictive? Towards efficient expressivity of graph neural networks
- arxiv url: http://arxiv.org/abs/2410.01910v1
- Date: Wed, 2 Oct 2024 18:09:12 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-04 10:04:30.284346
- Title: Is uniform expressivity too restrictive? Towards efficient expressivity of graph neural networks
- Title（参考訳）: 均一表現性は制限的すぎるか?グラフニューラルネットワークの効率的な表現性を目指して
- Authors: Sammy Khalife, Josué Tonelli-Cueto,
- Abstract要約: グラフニューラルネットワーク(GNN)は、入力グラフのサイズによってパラメータなしでクエリを表現できる。
入力グラフの最大次数に対してパラメータの数が対数的であるように,多くのGNNがGC2クエリを効率的に表現できることを示す。
- 参考スコア（独自算出の注目度）: 0.6445605125467574
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Uniform expressivity guarantees that a Graph Neural Network (GNN) can express a query without the parameters depending on the size of the input graphs. This property is desirable in applications in order to have number of trainable parameters that is independent of the size of the input graphs. Uniform expressivity of the two variable guarded fragment (GC2) of first order logic is a well-celebrated result for Rectified Linear Unit (ReLU) GNNs [Barcelo & al., 2020]. In this article, we prove that uniform expressivity of GC2 queries is not possible for GNNs with a wide class of Pfaffian activation functions (including the sigmoid and tanh), answering a question formulated by [Grohe, 2021]. We also show that despite these limitations, many of those GNNs can still efficiently express GC2 queries in a way that the number of parameters remains logarithmic on the maximal degree of the input graphs. Furthermore, we demonstrate that a log-log dependency on the degree is achievable for a certain choice of activation function. This shows that uniform expressivity can be successfully relaxed by covering large graphs appearing in practical applications. Our experiments illustrates that our theoretical estimates hold in practice.
- Abstract（参考訳）: 均一表現性は、グラフニューラルネットワーク(GNN)が入力グラフのサイズに依存するパラメータなしでクエリを表現できることを保証する。
この性質は、入力グラフのサイズに依存しない多くのトレーニング可能なパラメータを持つアプリケーションで望ましい。
第1次論理の2つの可変ガードフラグメント(GC2)の均一表現性は、Rectified Linear Unit (ReLU) GNNs [Barcelo & al., 2020] の良好な評価結果である。
本稿では,[Grohe, 2021] で定式化された質問に答える,幅広い種類の Pfaff 活性化関数 (sigmoid と tanh を含む) を持つ GNN に対して,GC2 クエリの均一表現性は不可能であることを示す。
また、これらの制限にもかかわらず、これらのGNNの多くは、入力グラフの最大次数でパラメータの数が対数的であるように、GC2クエリを効率的に表現できることも示している。
さらに、あるアクティベーション関数の選択に対して、その度合いに対するログ依存が達成可能であることを示す。
このことは、一様表現性は、実用に現れる大きなグラフを被覆することで、うまく緩和できることを示している。
我々の実験は、我々の理論的な推定が実際に成り立つことを示している。
関連論文リスト
- The logic of rational graph neural networks [0.7614628596146602]
我々は,GC2 の深度 3$ のクエリは,合理的なアクティベーション関数を持つ GNN では表現できないことを証明した。
これは、すべての非ポリノミカル活性化関数がGNNの最大表現性を参照しているわけではないことを示している。
また、一階述語論理(RGC2)の有理サブフラグメントを示し、すべてのグラフに対して有理GNNがRGC2クエリを均一に表現できることを証明する。
論文 参考訳（メタデータ） (2023-10-19T20:32:25Z) - Some Might Say All You Need Is Sum [2.226803104060345]
グラフニューラルネットワーク(GNN)の表現性は、採用する集約関数に依存する。
我々は,Mean や Max GNN によって正確に計算できる基本関数が任意の Sum GNN によって近似できないことを証明した。
論文 参考訳（メタデータ） (2023-02-22T19:01:52Z) - Training Graph Neural Networks on Growing Stochastic Graphs [114.75710379125412]
グラフニューラルネットワーク(GNN)は、ネットワーク化されたデータの意味のあるパターンを活用するために、グラフ畳み込みに依存している。
我々は,成長するグラフ列の極限オブジェクトであるグラフオンを利用して,非常に大きなグラフ上のGNNを学習することを提案する。
論文 参考訳（メタデータ） (2022-10-27T16:00:45Z) - Representation Power of Graph Neural Networks: Improved Expressivity via
Algebraic Analysis [124.97061497512804]
標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。
また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
論文 参考訳（メタデータ） (2022-05-19T18:40:25Z) - The Exact Class of Graph Functions Generated by Graph Neural Networks [43.25172578943894]
グラフ関数と出力が同一のグラフニューラルネットワーク(GNN)?
本稿では,この疑問に完全に答え,GNNで表現可能なグラフ問題のクラスを特徴付ける。
この条件は2次的に多くの制約をチェックすることで効率よく検証できることを示す。
論文 参考訳（メタデータ） (2022-02-17T18:54:27Z) - On the approximation capability of GNNs in node
classification/regression tasks [4.141514895639094]
グラフニューラルネットワーク(GNN)は、グラフ処理のための幅広い種類の接続モデルである。
GNNはノード分類/回帰タスクの確率の普遍近似であることを示す。
論文 参考訳（メタデータ） (2021-06-16T17:46:51Z) - GNNAutoScale: Scalable and Expressive Graph Neural Networks via
Historical Embeddings [51.82434518719011]
GNNAutoScale(GAS)は、任意のメッセージパスGNNを大規模グラフにスケールするためのフレームワークである。
ガスは、前回のトレーニングの繰り返しから過去の埋め込みを利用して計算グラフのサブツリー全体を掘り起こします。
ガスは大規模グラフ上で最先端のパフォーマンスに達する。
論文 参考訳（メタデータ） (2021-06-10T09:26:56Z) - Bi-GCN: Binary Graph Convolutional Network [57.733849700089955]
ネットワークパラメータと入力ノードの特徴を二項化するバイナリグラフ畳み込みネットワーク(Bi-GCN)を提案する。
我々のBi-GCNは、ネットワークパラメータと入力データの両方で平均30倍のメモリ消費を削減でき、推論速度を平均47倍に加速できる。
論文 参考訳（メタデータ） (2020-10-15T07:26:23Z) - Distance Encoding: Design Provably More Powerful Neural Networks for
Graph Representation Learning [63.97983530843762]
グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。
GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。
より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。
本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
論文 参考訳（メタデータ） (2020-08-31T23:15:40Z) - Expressive Power of Invariant and Equivariant Graph Neural Networks [10.419350129060598]
Folklore Graph Neural Networks (FGNN) は、与えられたテンソル次数に対してこれまで提案されてきた最も表現力のあるアーキテクチャである。
FGNNはこの問題の解決方法を学ぶことができ、既存のアルゴリズムよりも平均的なパフォーマンスが向上する。
論文 参考訳（メタデータ） (2020-06-28T16:35:45Z) - Can Graph Neural Networks Count Substructures? [53.256112515435355]
グラフニューラルネットワーク(GNN)の能力について,属性付きグラフサブ構造をカウントする能力を用いて検討する。
我々は2種類のサブストラクチャカウントを区別する: インダクションサブグラフカウントとサブグラフカウント、および人気のあるGNNアーキテクチャに対する肯定的および否定的な回答である。
論文 参考訳（メタデータ） (2020-02-10T18:53:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。