グラフニューラルネットワークの表現力向上のための部分グラフ同型性カウント手法

グラフニューラルネットワーク（GNN）は、さまざまな応用分野で顕著な成果を上げているが、近年の研究により、そのグラフ構造の捉え方における重要な限界が明らかになった。標準的なGNNの表現力は、ワイスフェイラー＝レーマン（WL）グラフ同型性判定テストによって上限が定められており、これに起因して、グラフの部分構造の検出や数え上げが不可能であるといった既知の制約を内包していることが示されている。一方で、ネットワーク科学やバイオインフォマティクスなどの分野には、部分構造が下流タスクと密接に関連しているという豊富な実証的証拠が存在する。このような背景を踏まえ、本研究では「グラフ部分構造ネットワーク」（Graph Substructure Networks; GSN）を提案する。これは部分構造の符号化に基づくトポロジカルに注意を払ったメッセージパッシングスキームであり、理論的にその表現力がWLテストを厳密に上回ることを示した。さらに、普遍性（universality）を満たすための十分条件も提示した。重要な点として、我々はWL階層に従うことを試みていない。これにより、標準GNNが持つ局所性や線形のネットワーク複雑性といった魅力的な性質を維持しつつ、グラフ同型性の難しい例ですら区別可能となる。本研究では、グラフ分類および回帰タスクにおいて広範な実験評価を実施し、分子グラフやソーシャルネットワークを含む多様な実世界設定で、最先端の性能を達成した。コードは公開されており、https://github.com/gbouritsas/graph-substructure-networks にて入手可能である。