最大エントロピー重み付き独立集合プーリングを用いたグラフニューラルネットワーク

本稿では、入力グラフとプーリング後のグラフ間の相互情報量を最大化することを目的とした、グラフニューラルネットワークにおける新たなプーリング層を提案する。相互情報量の最大化は計算上困難であるため、本手法ではグラフのシャノン容量（Shannon capacity）を誘導的バイアス（inductive bias）として導入する。具体的には、プーリング層の入力グラフがノイズのある通信チャネルの表現として解釈できることを示す。このようなチャネルにおいて、グラフの独立集合（independent set）に属するシンボルを送信することで、情報の信頼性の高い誤りのない伝送が可能となる。さらに、相互情報量の最大化が、各頂点にエントロピーの内容を表す重みを付与したグラフにおける最大重み独立集合の探索に等価であることを示す。この通信理論的な視点から、グラフニューラルネットワークによって実装されるノイズのある通信チャネルを介した情報伝送速度の最大化という観点から、グラフプーリング問題を再定式化する。提案手法は「最大エントロピー重み付き独立集合プーリング（Maximum Entropy Weighted Independent Set Pooling, MEWISPool）」と呼ばれる。本手法は、グラフ分類タスクおよび最大独立集合問題という組合せ最適化問題において評価された。実験結果から、複数のベンチマークデータセットにおいて、MEWISPoolはグラフ分類タスクおよび最大独立集合問題の両方で、最先端（state-of-the-art）かつ競争力のある性能を達成することが示された。