クラスター-GCN: 深層かつ大規模グラフ畳み込みネットワークの効率的な学習アルゴリズム

グラフ畳み込みネットワーク（GCN）は、多くのグラフベースの応用に成功裏に適用されてきましたが、大規模なGCNの学習は依然として課題となっています。現在のSGDベースのアルゴリズムは、GCN層数の増加とともに指数関数的に増大する高い計算コストや、全グラフと各ノードの埋め込みをメモリに保持するために必要な大きな空間要件という問題を抱えています。本論文では、グラフクラスタリング構造を利用することでSGDベースの学習に適した新しいGCNアルゴリズムであるCluster-GCNを提案します。Cluster-GCNの動作は以下の通りです：各ステップで、グラフクラスタリングアルゴリズムによって特定された密な部分グラフに関連するノードブロックをサンプリングし、近傍探索をこの部分グラフ内に制限します。この単純だが効果的な戦略により、以前のアルゴリズムと同等のテスト精度を達成しながら、大幅に改善されたメモリー効率と計算効率が得られます。当社のアルゴリズムのスケーラビリティを検証するために、200万ノードと6100万エッジを持つAmazon2Mデータセットを作成しました。これは、これまで最大で公開されていたデータセット（Reddit）よりも5倍以上大きいものです。このデータ上で3層のGCNを学習する場合、Cluster-GCNは従来の最先端技術であるVR-GCNよりも高速（1523秒対1961秒）であり、さらに少ないメモリーを使用します（2.2GB対11.2GB）。さらに、4層のGCNを学習する場合でも、当社のアルゴリズムは約36分で完了しますが、既存のすべてのGCN学習アルゴリズムはメモリー不足のために学習できませんでした。また、Cluster-GCNにより時間とメモリー負荷が大きく増えずに深さのあるGCNを学習することが可能となりました。これにより予測精度が向上し、5層のCluster-GCNを使用してPPIデータセットでの最先端テストF1スコア99.36％を達成しました。これに対して従来最高結果であった[16]では98.71％でした。当社のコードは https://github.com/google-research/google-research/tree/master/cluster_gcn で公開されています。