Weisfeiler-Leman階層からの脱却：メッセージ伝達を超えるグラフ学習

我々は、グラフ学習のための新規ニューラルネットワークアーキテクチャであるCRaWlを提案する。グラフニューラルネットワーク（GNN）と同様に、CRaWlのレイヤーはグラフ上のノード特徴量を更新するが、その結果としてGNNレイヤーと自由に組み合わせたり、交互に配置したりすることが可能である。しかし、CRaWlはメッセージパッシング型GNNと根本的に異なる仕組みを採用している。CRaWlのレイヤーは、グラフ上でランダムウォークに沿って出現する部分グラフに対して、1次元畳み込み（1D Convolution）を用いて情報の抽出と集約を行う。この仕組みにより、長距離の相互作用を検出可能となり、非局所的な特徴量を計算することが可能となる。本手法の理論的基盤として、我々は、CRaWlの表現力がWeisfeiler-Leman（WL）アルゴリズムおよびそれに対応するGNNの表現力と比較不能であるという定理を証明した。すなわち、CRaWlで表現可能な関数が存在する一方で、GNNでは表現不可能であり、逆もまた然りである。この結果は、WL階層の高次のレベルにまで拡張可能であり、高次元GNN（higher-order GNNs）に対しても同様に成り立つ。実験的にも、多数のグラフ分類および回帰タスクにおけるベンチマークデータセットにおいて、CRaWlが最先端のGNNアーキテクチャと同等の性能を達成することを示した。