論文の概要: Towards Arbitrarily Expressive GNNs in $O(n^2)$ Space by Rethinking Folklore Weisfeiler-Lehman

• arxiv url: http://arxiv.org/abs/2306.03266v1
• Date: Mon, 5 Jun 2023 21:35:32 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-07 18:10:43.579409
• Title: Towards Arbitrarily Expressive GNNs in $O(n^2)$ Space by Rethinking Folklore Weisfeiler-Lehman
• Title（参考訳）: Folklore Weisfeiler-Lehmanを再考したO(n^2)$空間における任意表現型GNN
• Authors: Jiarui Feng, Lecheng Kong, Hao Liu, Dacheng Tao, Fuhai Li, Muhan Zhang, Yixin Chen
• Abstract要約: 近年、グラフニューラルネットワーク(GNN)の最も人気のあるフレームワークとして、メッセージパッシングニューラルネットワーク(MPNN)が登場している。 しかし、その表現力は1次元のWeisfeiler-Lehman (1-WL) テストによって制限される。 我々は、$(k, t)$-FWLの拡張を提案し、$k$-FWLの設計空間を大幅に拡張する。 N$2-GNNは、ほぼすべてのタスクにおいて、ZINC-SubsetとZINC-Fullで記録破りの結果を達成している。
• 参考スコア（独自算出の注目度）: 82.95544706005822
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Message passing neural networks (MPNNs) have emerged as the most popular framework of graph neural networks (GNNs) in recent years. However, their expressive power is limited by the 1-dimensional Weisfeiler-Lehman (1-WL) test. Some works are inspired by $k$-WL/FWL (Folklore WL) and design the corresponding neural versions. Despite the high expressive power, there are serious limitations in this line of research. In particular, (1) $k$-WL/FWL requires at least $O(n^k)$ space complexity, which is impractical for large graphs even when $k=3$; (2) The design space of $k$-WL/FWL is rigid, with the only adjustable hyper-parameter being $k$. To tackle the first limitation, we propose an extension, $(k, t)$-FWL. We theoretically prove that even if we fix the space complexity to $O(n^2)$ in $(k, t)$-FWL, we can construct an expressiveness hierarchy up to solving the graph isomorphism problem. To tackle the second problem, we propose $k$-FWL+, which considers any equivariant set as neighbors instead of all nodes, thereby greatly expanding the design space of $k$-FWL. Combining these two modifications results in a flexible and powerful framework $(k, t)$-FWL+. We demonstrate $(k, t)$-FWL+ can implement most existing models with matching expressiveness. We then introduce an instance of $(k,t)$-FWL+ called Neighborhood$^2$-FWL (N$^2$-FWL), which is practically and theoretically sound. We prove that N$^2$-FWL is no less powerful than 3-WL, can encode many substructures while only requiring $O(n^2)$ space. Finally, we design its neural version named N$^2$-GNN and evaluate its performance on various tasks. N$^2$-GNN achieves superior performance on almost all tasks, with record-breaking results on ZINC-Subset (0.059) and ZINC-Full (0.013), outperforming previous state-of-the-art results by 10.6% and 40.9%, respectively.
• Abstract（参考訳）: 近年、グラフニューラルネットワーク(GNN)の最も人気のあるフレームワークとして、メッセージパッシングニューラルネットワーク(MPNN)が登場している。 しかし、その表現力は1次元のWeisfeiler-Lehman (1-WL) テストによって制限される。 いくつかの作品は$k$-WL/FWL(Folklore WL)にインスパイアされ、対応するニューラルバージョンを設計する。 表現力が高いにもかかわらず、この研究には深刻な制限がある。 特に、(1)$k$-WL/FWL は少なくとも$O(n^k)$空間複雑性を必要とし、これは$k=3$; (2)$k$-WL/FWL の設計空間は厳密であり、唯一の調整可能なハイパーパラメータは$k$である。 最初の制限に対処するために、$(k, t)$-FWLの拡張を提案する。 理論的には、空間複雑性を$O(n^2)$ in $(k, t)$-FWL に固定しても、グラフ同型問題を解くために表現性階層を構築することができる。 2つ目の問題に取り組むために、全てのノードの代わりに任意の同変集合を隣人として考える$k$-FWL+を提案し、その結果、設計空間を$k$-FWLに拡大する。 これら2つの修正を組み合わせると、柔軟性と強力なフレームワーク $(k, t)$-fwl+ が得られる。 例えば、$(k, t)$-FWL+は、表現性にマッチする既存のモデルの多くを実装できることを示す。 次に、(k,t)$-FWL+ である Neighborhood$^2$-FWL (N$^2$-FWL) の例を導入する。 N$^2$-FWL が 3WL に劣らず強力であることを証明し、O(n^2)$空間のみを必要としながら多くの部分構造を符号化できる。 最後に、N$^2$-GNNというニューラルバージョンを設計し、各種タスクの性能を評価する。 N$^2$-GNNは、ZINC-Subset (0.059) と ZINC-Full (0.013) でそれぞれ10.6%と40.9%と、ほぼ全てのタスクにおいて優れたパフォーマンスを実現している。

関連論文リスト

• Approximation Rates for Shallow ReLU$^k$ Neural Networks on Sobolev Spaces via the Radon Transform [4.096453902709292]
  我々は,ReLU$k$アクティベーション関数がソボレフ空間からの関数をいかに効率的に近似できるかという問題を考察する。 例えば、$qleq p$, $pgeq 2$, $s leq k + (d+1)/2$ などである。
  論文  参考訳（メタデータ） (2024-08-20T16:43:45Z)
• Spatio-Spectral Graph Neural Networks [50.277959544420455]
  比スペクトルグラフネットワーク(S$2$GNN)を提案する。 S$2$GNNは空間的およびスペクトル的にパラメータ化されたグラフフィルタを組み合わせる。 S$2$GNNsは、MPGNNsよりも厳密な近似理論誤差境界を生じる。
  論文  参考訳（メタデータ） (2024-05-29T14:28:08Z)
• Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learning [17.646846505225735]
  グラフ同型テストの新しい階層構造と対応するGNNフレームワークである$r$-$ell$MPNNを導入し、最大長さ$r + 2$までサイクルをカウントできる。 特に、$r$-$ell$WL がサクタスグラフの準同型を数えることができることを示す。 提案した$r$-$ell$MPNNの複数の合成データセットに対する表現力とカウント力を実証的に検証し,様々な実世界のデータセットに対する最先端の予測性能を示す。
  論文  参考訳（メタデータ） (2024-03-20T16:58:28Z)
• Learning General Policies for Classical Planning Domains: Getting Beyond C$_2$ [15.574717738100727]
  計画領域全体にわたる一般的なポリシーを学ぶためのGNNベースのアプローチは、$C$の表現力によって制限される。 関係GNNのパラメータ化版を導入し、$t$が無限大であるとき、R-GNN[$t$]は埋め込みのための2次空間のみを用いて3ドルGNNを近似する。 t=1 や $t=2 のような $t$ の低い値の場合、R-GNN[$t$] はより少ないメッセージを交換することでより弱い近似を達成する。
  論文  参考訳（メタデータ） (2024-03-18T12:42:53Z)
• Capacity Bounds for Hyperbolic Neural Network Representations of Latent Tree Structures [8.28720658988688]
  本稿では,ReLUアクティベーション機能を持つHNN(Deep Hyperbolic Neural Network)の表現能力について検討する。 HNN が任意の有限重み付き木を少なくとも 2$ に等しい次元の双曲空間に埋め込むことができるという最初の証明を確立する。 グラフ表現を実装するHNNのネットワーク複雑性は,表現の忠実さ/歪みとは無関係であることがわかった。
  論文  参考訳（メタデータ） (2023-08-18T02:24:32Z)
• When Expressivity Meets Trainability: Fewer than $n$ Neurons Can Work [59.29606307518154]
  幅が$m geq 2n/d$($d$は入力次元)である限り、その表現性は強く、すなわち、訓練損失がゼロの少なくとも1つの大域最小化器が存在することを示す。 また、実現可能な領域がよい局所領域であるような制約付き最適化の定式化も検討し、すべてのKKT点がほぼ大域最小値であることを示す。
  論文  参考訳（メタデータ） (2022-10-21T14:41:26Z)
• Neural Networks Efficiently Learn Low-Dimensional Representations with SGD [22.703825902761405]
  SGDで訓練されたReLU NNは、主方向を回復することで、$y=f(langleboldsymbolu,boldsymbolxrangle) + epsilon$という形の単一インデックスターゲットを学習できることを示す。 また、SGDによる近似低ランク構造を用いて、NNに対して圧縮保証を提供する。
  論文  参考訳（メタデータ） (2022-09-29T15:29:10Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  量子順序付き二項決定図($OBDD$)モデルについて検討する。 入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。 read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
  論文  参考訳（メタデータ） (2022-04-22T12:37:56Z)
• Improving Robustness and Generality of NLP Models Using Disentangled Representations [62.08794500431367]
  スーパービジョンニューラルネットワークはまず入力$x$を単一の表現$z$にマップし、次に出力ラベル$y$にマッピングする。 本研究では,非交叉表現学習の観点から,NLPモデルの堅牢性と汎用性を改善する手法を提案する。 提案した基準でトレーニングしたモデルは、広範囲の教師付き学習タスクにおいて、より堅牢性とドメイン適応性を向上することを示す。
  論文  参考訳（メタデータ） (2020-09-21T02:48:46Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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