BNS-GCN：パーティショニング並列性とランダム境界ノードサンプリングを用いたグラフ畳み込みネットワークの効率的なフルグラフ学習

グラフ畳み込みネットワーク（Graph Convolutional Networks, GCN）は、グラフベースの学習タスクにおいて最先端の手法として登場している。しかし、GCNのスケールアップした学習は依然として困難であり、より複雑なGCNアーキテクチャの探求や、現実世界の大規模グラフへの応用を阻害している。この課題に対処するため、グラフのパーティショニングと分散学習を検討するのは自然なアプローチであるが、従来の設計の制約により、この方向性はこれまでほとんど検討されてこなかった。本研究では、分散GCN学習が効果的でない理由を分析し、その根本的な原因として、各パーティショニングされた部分グラフにおける境界ノード（boundary nodes）の過剰な数が、メモリ使用量と通信コストを急激に増大させることを特定した。さらに、ランダムな境界ノードサンプリング（Boundary-Node-Sampling）を採用するシンプルかつ効果的な手法、BNS-GCNを提案する。実験およびアブレーション研究により、BNS-GCNの有効性が一貫して検証された。具体的には、スループットを最大16.2倍まで向上させ、メモリ使用量を最大58％削減しつつ、全体グラフの精度を維持することが可能となった。さらに、理論的および実証的分析から、既存のサンプリングベースの手法と比較して、BNS-GCNはより優れた収束性を示すことが明らかになった。本研究では、BNS-GCNが大規模GCN学習を可能にする新たなパラダイムを切り開いたと確信している。実装コードは、https://github.com/RICE-EIC/BNS-GCN にて公開されている。