DiffWire：Lovász 界を用いたインダクティブなグラフリワーリング

グラフニューラルネットワーク（GNN）は、さまざまな分野においてノードおよびグラフ分類、リンク予測、ノードおよびグラフクラスタリングなどのグラフ関連タスクに対して競争力ある性能を示している。多数のGNNはメッセージパッシングフレームワークを採用しており、そのようなモデルはMPNN（Message Passing Neural Networks）と呼ばれる。しかし、これらのMPNNは過度なスムージング（over-smoothing）、過度な圧縮（over-squashing）、および情報の到達不足（under-reaching）といった問題に直面していることが報告されている。グラフのリワイヤリング（rewiring）とグラフプーリングが、こうした制約を克服するための手法として提案されてきた。しかしながら、現在の最先端のグラフリワイヤリング手法の多くは、グラフのグローバルなトポロジーを保持できず、微分可能でもなく、インダクティブでもなく、ハイパーパラメータのチューニングを必要とするという課題を抱えている。本稿では、ロヴァーシュ（Lovász）バウンドを活用することで、原理的かつ完全に微分可能であり、パラメータフリーなグラフリワイヤリングフレームワーク「DiffWire」を提案する。本手法は、MPNNに新たな2つの補完的な層を導入することで、グラフリワイヤリングに関する統一的な理論を提供する。第一に、CT-Layer（Commute Time Layer）は、移動時間（commute time）を学習し、それをエッジの重み付けに用いる関連性関数として利用する。第二に、GAP-Layer（Spectral Gap Optimization Layer）は、ネットワークの性質およびタスクの特性に応じてスペクトルギャップを最適化する。我々は、グラフ分類のベンチマークデータセットを用いて、各層の有効性を実証的に検証した。さらに、同層を同型性（homophilic）および異型性（heterophilic）ノード分類タスクに適用するための初期的検討も行った。DiffWireは、移動時間の学習性と曲率に関する関連概念を統合することで、より表現力豊かなMPNNの構築に道を開くものである。