ワイスフェイラーとレマンがニューラルへ：高次グラフニューラルネットワーク

近年、グラフニューラルネットワーク（GNNs）は、ノードやグラフのベクトル表現を教師ありのエンドツーエンド学習で獲得する強力なニューラルアーキテクチャとして注目を集めています。これまで、GNNsは経験的に評価されてきましたが、有望な結果を示しています。本研究では、GNNsを理論的な観点から調査し、1次元ワイスフェイラー・レマングラフ同型判定ヒューリスティック（1-WL）との関連性について考察します。我々は、非同型の（部分）グラフを区別する能力において、GNNsが1-WLと同等の表現力を有することを示しました。したがって、両アルゴリズムには同じ制約も存在します。この知見に基づいて、我々は多次元のグラフ構造を取り扱うことができる一般化されたGNNs、すなわち$k$次元GNNs（$k$-GNNs）を提案します。これらの高次の構造は、ソーシャルネットワークや分子グラフの特性化において重要な役割を果たします。実験評価では、理論的な知見が確認されるとともに、高次の情報がグラフ分類や回帰タスクにおいて有用であることも確認されました。