グラフニューラルネットワークの設計空間を拡張するためのfolklore Weisfeiler-Lehmanの再考

メッセージパッシングニューラルネットワーク（MPNNs）は、最近のグラフニューラルネットワーク（GNNs）の中で最も人気のあるフレームワークとして台頭しています。しかし、その表現力は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という拡張を提案します。理論的に証明したところによると、$(k,t)$-FWLにおいて空間複雑さを$O(n^k)$（任意の$k \geq 2$に対して）に固定しても、グラフ同型問題を解くまでの表現力階層を構築することができます。第二の問題に対処するために、我々は$k$-FWL+を提案します。これにより全てのノードではなく任意の等変集合を近傍として考慮することで、$k$-FWLの設計空間が大幅に拡大されます。これらの2つの改良を組み合わせることで、柔軟かつ強力なフレームワーク$(k,t)$-FWL+が得られます。我々は$(k,t)$-FWL+が既存のモデルの大半を同等の表現力で実装できることを示します。さらに、$(k,t)$-FWL+の一例としてNeighborhood$^2$-FWL (N$^2$-FWL)を導入します。N$^2$-FWLは実際的かつ理論的に健全であることが証明されています。N$^2$-FWLが3-WL以上に強力であり、多くの部分構造をエンコードしながらも僅かに$O(n^2)$の空間が必要であることを証明しました。最後に、N$^2$-GNNと呼ばれるニューラル版を設計し、様々なタスクでの性能評価を行いました。N$^2$-GNNはZINCサブセット（0.059）において記録的な結果を達成し、以前の最先端結果よりも10.6%優れています。また、N$^2$-GNNは全ての既存の高表現力GNN手法の中でもBRECデータセット（71.8%）において新しい最先端結果を達成しています。