技術要約：非線形ラプラシアンによる符号付き有向グラフ学習の向上

問題提起

現実世界のシステムは、符号付き（正負、例：信頼/不信、好き/嫌い）かつ有向（非対称、例：AからBへの影響の流れ）な相互作用を伴うことが多い。グラフニューラルネットワーク（GNN）は標準的なグラフに対しては成功を収めているが、符号付き有向グラフへの一般化は依然として困難である。既存のアプローチは、方向性と符号を個別に扱うか、あるいは特定の線形定義を通じて処理するために、主に線形ラプラシアン演算子や複雑な磁気ラプラシアンに依存している。しかし、符号付き有向ネットワークのために特別に設計された非線形ラプラシアン演算子に焦点を当てた研究は不足している。核心となる課題は、ノード分類やリンク予測といったダウンストリームタスクに対して、計算効率と表現力を維持しながら、これらのグラフの組合せ構造を効果的に捉える演算子を定義することである。

手法：NLSD および NLSD-GNN

本論文では、新しい**符号付き有向グラフ用非線形ラプラシアン（NLSD）**と、対応するスペクトルGNNフレームワークである NLSD-GNN を導入している。

1. 非線形符号付き有向ラプラシアン (NLSD)

著者らは、有向グラフの非線形ラプラシアン（Yoshida, 2016）の定義を、エッジの符号を取り入れるように拡張した。演算子 $L_G(x)$ は、ノードポテンシャルベクトル $x \in \mathbb{R}^V$ の関数として定義される。

1. グラフ変換（エッジドロップアウトと自己ループ）:
   与えられたポテンシャルベクトル $x$ に対して、元の符号付き有向グラフ $G$ は、符号付き無向グラフ $G_x$ へと変換される：

   • 各有向エッジ $(u, v)$（符号 $s \in \{+, -\}$ を持つ）について：
     • $x_u \geq x_v$ の場合：同じ符号 $s$ と重み $w(e)$ を持つ無向エッジ $\{u, v\}$ が $G_x$ に含まれる。
     • $x_u < x_v$ の場合：そのエッジは「ドロップ」され、同じ符号 $s$ と重み $w(e)/2$ を持つ自己ループ $\{u, u\}$ および $\{v, v\}$ が導入される。
   • このメカニクトにより、ポテンシャルの差がエッジの方向と一致する場合（または自己ループによって中和される場合）にのみ、メッセージパッシングが行われることが保証される。

2. ラプラシアンの構築:
   得られた符号付き無向グラフ $G_x$ に対して、標準的な線形ラプラシアン $L_{G_x}$ が計算される。最終的な演算子の出力は $L_G(x) = L_{G_x} x$ である。

3. 二次形式の性質:
   二次形式 $Q_G(x) = x^\top L_G(x)$ は、符号付きおよび有向グラフのカット特性を一般化する。この形式を最小化することは、正のエッジに対しては始点が終点の左側（$x_u \geq x_v$）、負のエッジに対しては始点が終点の右側（$x_u \leq x_v$）となるように頂点を埋め込むことを促し、構造的バランスと方向性を効果的に捉える。

4. 理論的保証:
   提案された演算子が半正定値であること、および正規化ラプラシアンの固有値が従来のグラフラプラシアンと同様に範囲 $[0, 2]$ 内に存在することを証明している。

2. NLSD-GNN アーキテクチャ

この演算子をGNNで利用するために、著者らはノード特徴 $H$ から必要なポテンシャルベクトル $x$ を生成するための2つのバリアントを提案している。

• NLSD-GNN-MLP: 多層パーセプトロン（MLP）と tanh 活性化関数を使用し、ノード特徴の次元を各ノードに対してスカラー値（1次元ベクトル）へと段階的に削減する。
• NLSD-GNN-Fast: ランダム投影を使用してノード特徴をスカラー値にマッピングし、計算効率の高い代替案を提供する。

ワークフロー:

1. 特徴投影: ノード特徴 $H$ がスカラーベクトル $x$ に投影される。
2. グラフ変換: 入力された符号付き有向グラフが、$x$ に基づいて符号付き無向グラフ $G_x$ に変換される。
3. スペクトル畳み込み: 標準的なスペクトルGNNレイヤー（ChebNetスタイルなど）が、変換されたグラフの線形ラプラシアンを用いて $G_x$ 上に適用される。
4. 予測: 出力が線形層とsoftmaxに渡され、ノード分類が行われるか、あるいは結合されてリンク予測が行われる。

主な貢献

1. 新規演算子の定義: 有向グラフのラプラシアン（Yoshida, 2016）と符号付きグラフのラプラシアン（Hou et al., 2003）の概念を統合した、符号付き有向グラフ専用の非線形ラプラシアンの初となる定義。
2. 理論的表現力: 提案された演算子がCheeger型の不等式を満たし、スペクトルグラフ理論に適したスペクトル特性（半正定値性、有界な固有値）を持つことの証明。
3. 効率的なフレームワーク (NLSD-GNN): 毎ステップの複雑な固有値分解を必要とせず、代わりに疎密行列積を利用することで、非線形演算を活用するスペクトルGNNアーキテクチャ。
4. 包括的な評価: ノード分類（有向および符号付き有向）およびリンク予測（符号、方向、およびマルチクラス）における広範な実験により、最先端または競争力のある性能を実証。

実験結果

ノード分類

• データセット: 有向グラフ（Cornell, Texas, Wisconsin, Cora-ML, CiteSeer）およびヘテロフィリック有向グラフ（Chameleon, Squirrel, Arxiv-Year, Roman-Empire）でテスト。
• 性能:
  • ホモフィリックな有向データセットにおいて、NLSD-GNNのバリアントは一貫してトップ3に入り、いくつかのデータセットでMagNetなどのスペクトルベースラインや、SAGEやGATなどの非スペクトル手法を上回った（例：Texas、Wisconsinで最高の結果を出し、Cornellで2位を獲得）。
  • ヘテロフィリックな有向グラフにおいて、NLSD-GNNはMagNetや他のスペクトル手法を凌駕したが、HoloNetやDir-GNNのような（符号データを想定していない）特化したヘテロフィリックモデルには及ばなかった。

符号付き有向グラフにおけるリンク予測

• データセット: Bitcoin-Alpha, Bitcoin-OTC, Slashdot, Epinions.
• タスク: 符号予測 (SP)、方向予測 (DP)、およびマルチクラスタスク (3C, 4C, 5C)。
• 性能:
  • NLSD-GNN-Fastは、ほぼすべてのデータセットとタスクにおいて、すべてのベースライン手法（SGCN, SDGNN, SiGAT, SNEA, SSSNET, SigMaNet, MSGNNを含む）を上回った。
  • このモデルは、符号と方向を同時に扱う必要があるタスク（4Cおよび5C）において特に強みを示し、統一された非線形演算子の有効性を検証した。
  • アブレーション研究により、符号付き特徴と方向情報の両方を組み込むことが最良の結果をもたらすことが確認された。

重要性と主張

本論文は、NLSD-GNNフレームワークがスペクトルグラフ理論と符号付き有向グラフ学習の間の溝を埋めることに成功したと主張している。ノードポテンシャルに基づいてグラフ構造を動的に適応させる非線形ラプラシアンを導入することで、本手法は以下を実現している：

• 符号付きおよび方向データの統合: 線形演算子が過剰なパラメータなしに同時に捉えるのが困難な、エッジの符号と方向の相互作用を効果的にモデル化する。
• 優れた性能の達成: 符号付き有向グラフのリンク予測において新しい最先端ベンチマークを設定し、ノード分類において主要なGNNと強力に競合する。
• 効率性の維持: ポテンシャル生成のためのランダム投影や単純なMLPの使用、および疎行列演算の組み合わせにより、他のスペクトルアプローチと比較して計算効率（$O(MFd)$ の複雑性）を維持している。

著者らは、本研究が、ソーシャルネットワーク、金融信頼ネットワーク、意見ダイナミクスのように、相互作用が符号付きかつ有向である複雑なシステムの分析において、堅牢で理論に基づいた、実用的なツールを提供すると結論付けている。