トポロジカルニューラルネットワークの論理的表現力
arXiv cs.LG / 2026/4/22
📰 ニュースIdeas & Deep AnalysisModels & Research
要点
- グラフニューラルネットワーク（GNN）はグラフ学習の標準だが、表現力が限られており、しばしばウェイスタイラー・レーマン（WL）階層や一階論理の枠組みで特徴づけられる。
- トポロジカルニューラルネットワーク（TNN）は、メッセージパッシングに高次の関係構造を取り入れることで、従来のGNNより高い表現力を持つが、その論理的表現力は未解決だった。
- 本論文は、一般的なTNNの仕組みに基づく同型判定（isomorphism tests）を解析し、組合せ的複体に対する高次のWLベーステストとして k-CCWL を提案・調査する。
- さらに、ペアごとのカウント量化子を導入した拡張カウント論理 TC_k を導入し、k-CCWL ≡ TC_{k+2} ≡ Topological (k+2)-pebble game という厳密な同値性を証明する。
- これらの形式的な結果により、TNNの表現力に関する理論が確立され、TNNが表現できる二値グラフ分類器が明確になる。
