異質性グラフをGNNにさらに適応させる：グラフリワイヤリングアプローチ

グラフニューラルネットワーク（GNN）は、グラフデータをモデル化するための代表的な機械学習手法として広く用いられている。多くのGNNは同質性（homophily）を示すグラフ上で優れた性能を発揮するが、異質性（heterophily）を示すグラフでは満足のいく結果を得られない。近年、メッセージパッシング機構の調整やメッセージパッシングの受容領域（receptive field）の拡大によって異質性グラフ向けのGNN設計に注目が集まっている。本研究では、従来のモデル設計の視点から異質性の問題を緩和するアプローチとは異なり、グラフ構造の再接続（rewiring）を通じて異質性を低減し、従来のGNNがより良い性能を発揮できるようにする、異質性グラフを扱うための直交的なアプローチを提案する。包括的な実証的研究および分析を通じて、再接続手法の潜在的有効性を検証した。その潜在能力を最大限に引き出すために、同質的エッジの追加と異質的エッジの削除を通じてグラフを再構築する手法「Deep Heterophily Graph Rewiring（DHGR）」を提案する。再接続の詳細な手法は、ノードの近傍におけるラベル／特徴分布の類似度を比較することによって決定される。さらに、DHGRのスケーラブルな実装を設計し、高い効率性を確保した。DHGRは、任意のGNN（同質性向けおよび異質性向けの両方）に簡単に統合可能なプラグインモジュールとして利用可能であり、ノード分類タスクにおける性能向上を実現するグラフ前処理ステップとして活用できる。本研究は、異質性グラフに対するグラフ再接続の研究において、世界で初めての試みであると認識している。11個の公開グラフデータセットを用いた広範な実験により、本研究で提案する手法の優位性を実証した。