最近、Weisfeiler-Lehman (WL) グラフ同型テストが、グラフニューラルネットワーク (GNN) の表現力を測定するために使用されました。研究結果によると、人気のあるメッセージパッシング GNN は、1-WL テストで区別できないグラフを区別することができないことが示されています (Morris et al. 2018; Xu et al. 2019)。残念ながら、多くの単純なグラフの例は1-WL テストでは区別できません。より表現力豊かなグラフ学習モデルを探求するために、私たちは最近提案された k 階不変および k 階等変グラフニューラルネットワーク (Maron et al. 2019a,b) を基盤として、以下の2つの結果を提示します：第一に、このような k 階ネットワークは k-WL テストと同等の性能で非同型グラフを区別できることが示されました。k>2 の場合、k-WL テストは証明上1-WL テストよりも強力であるため、これらのモデルはメッセージパッシングモデルよりも厳密に強力です。ただし、これらのモデルの高い表現力には高階テンソルの処理に伴う計算コストが伴います。第二に、証明上より強力で単純かつスケーラブルなモデルを構築することを目指し、スケーリングされた恒等演算子のみを含む簡略化された2階ネットワークに単一の二次演算（行列乗算）を追加したモデルが3-WL 表現力を有することが証明されました。言い換えると、特徴次元に対して標準的なマルチレイヤーパーセプトロン (MLP) を適用し、行列乗算を行うというシンプルなモデルを提案しています。このモデルの有効性を検証するために、人気のあるグラフ分類および回帰タスクにおける最先端の結果を提示します。私たちの知る限りでは、これは初めて実用的に不変性/等変性を持ちつつ3-WL 表現力を保証するモデルであり、メッセージパッシングモデルよりも厳密に強力です。