異種親和（ヘテロフィリック）グラフに対するコストセンシティブ近傍集約：いつエッジごとのルーティングが役立つのか？

要旨: 近年の研究では、ヘテロフィリー（異種結合）の状態には2つのレジームがあることが区別されている。1つは敵対的（adversarial）であり、異クラス間のエッジがクラスの信号を希釈して分類を損なう。もう1つは情報的（informative）であり、ヘテロフィリーな構造それ自体が有用な信号を運んでいる。本研究では次の問いを扱う: いつ、1エッジごとのメッセージルーティングが有効なのか。そして、いつ、一様なスペクトルチャネルだけで十分なのか。この問いを具体化するために、学習した射影における距離のペアワイズ計算を行い、その距離を用いて、コンコーダント（concordant）チャネルとディスコーダント（discordant）チャネルへ独立な変換によって各メッセージをソフトにルーティングするGNN層である、Cost-Sensitive Neighborhood Aggregation（CSNA、コスト感度型近傍集約）を提案する。文脈付き確率ブロックモデル（contextual stochastic block model）の下で、平均集約は信号を減衰させてしまうのに対し、コスト感度付きの重み付けはクラス識別的な信号を保持することを示す。さらに、条件として w_+/w_- > q/p を要する。6つのベンチマークにおいて一様なチューニングで評価したところ、CSNAは敵対的ヘテロフィリー（adversarial-heterophily）データセット（Texas, Wisconsin, Cornell, Actor）では最先端手法と競合するが、情報的ヘテロフィリー（informative-heterophily）データセット（Chameleon, Squirrel）では上回れない。これはまさに、1エッジごとのルーティングに活用できる有用な分解が存在しないレジームに対応している。このパターン自体が本研究の発見である。すなわち、コスト関数がエッジ種別を分離できる能力は、ヘテロフィリーのレジームを診断する指標として機能し、微視的なルーティングが一様なチャネルよりも価値を持つ場合と持たない場合を明らかにする。コードは https://github.com/eyal-weiss/CSNA-public で公開されている。