要約
1次元のWeisfeiler-Lemanアルゴリズムと対応するニューラルアーキテクチャは、最近、（教師あり）グラフ学習における強力なツールとして注目を集めています。しかし、これらのアルゴリズムが純粋に局所的な性質を持つため、与えられたデータ中の重要なパターンを見逃す可能性があり、二項関係のみを扱うことができます。この問題に対処するために、$k$次元のWeisfeiler-Lemanアルゴリズムは頂点集合上で定義された$k$-タプルを考え、これらの頂点タプル間の隣接性の適切な概念を定義します。したがって、このアルゴリズムは頂点間の高次の相互作用を考慮に入れることができます。しかし、スケーラビリティに欠け、機械学習の設定で使用される場合過学習の問題に直面する可能性があります。したがって、表現力があり、スケーラブルであり、過学習しにくいWLベースのグラフ学習手法を設計することは重要な未解決問題となっています。本研究では、元の近傍の部分集合を考えることでよりスケーラブルになり、過学習しにくい局所的な変種と対応するニューラルアーキテクチャを提案します。私たちのアルゴリズム（の一つ）は非同型グラフを区別する能力において元のアルゴリズムよりも厳密に高い表現力を有しています。実験結果は、局所的なアルゴリズム（カーネル版およびニューラル版）が大幅に計算時間を削減し、過学習を防ぐことを確認しています。カーネル版は幅広いベンチマークデータセットでのグラフ分類において新しい最先端性能を達成しており、ニューラル版は大規模な分子回帰タスクにおいて有望な性能を示しています。