要約
グラフニューラルネットワーク（GNNs）は、グラフ構造データにおいて大きな成功を収めています。この成功を受け、GNNの表現力に関する研究への関心が高まっています。一方では、GNNがグラフ上の置換不変関数を近似する能力が研究され、他方では、グラフ同型性テストとしてのGNNの能力が注目されています。本研究では、これらの二つの視点を結びつけ、その等価性を証明します。さらに、σ-代数（sigma-algebra）の言葉を使用して、これら二つの視点を統合したGNNの表現力のフレームワークを開発し、異なる種類のGNNと他のグラフ同型性テストの表現力を比較します。特に、2次不変グラフネットワークが同じ次数を持つ非同型正則グラフを区別できないことを証明しました。その後、Ring-GNNという新しいアーキテクチャを開発し、これらのグラフを区別することに成功し、実世界データセットでの良好な性能を達成しています。