要約
グラフニューラルネットワーク（GNN）は、グラフ構造データの学習において最近、標準的なアプローチとして定着しつつある。これまでの研究により、GNNの潜在能力と限界の両方が明らかにされてきた。しかし、標準的なGNNは表現力に限界があることが示された。すなわち、非同型なグラフを区別する能力において、これらのモデルは1次元ワイズフェーラー・レーマン（1-WL）アルゴリズムと同等、あるいはそれ以下であることが示されている。本論文では、ノードから発するパスを統合することでノード表現を更新する新しいモデル「パスニューラルネットワーク（PathNN）」を提案する。本モデルの3つの異なる変種を導出しており、それぞれ単一の最短パス、すべての最短パス、および長さがK以下のすべての単純パスを統合する方式である。我々は、そのうち2つの変種が1-WLアルゴリズムよりも厳密に表現力が強いことを理論的に証明し、実験的にもその結果を検証した。実験の結果、PathNNは1-WLでは区別できない非同型グラフのペアを区別可能であり、特に最も表現力の高いPathNNの変種は、3-WLでも区別できないグラフ間をも区別可能であることが確認された。さらに、グラフ分類およびグラフ回帰のデータセットにおける実験において、多数のケースでベースライン手法を上回る性能を示した。