GNNを1から — つながりを学ぶネットワーク

SNSも分子も道路網も「点と線」でできています。隣の情報を集めて自分を書き換えるメッセージパッシングを前提知識ゼロから組み立て、層を深くすると全ノードが同じ顔になるオーバースムージング、そして推薦と創薬での実際の使われ方までを一本の道でつなぎます。

Semi-Supervised Classification with Graph Convolutional Networks

名簿を見ても分からないこと

新しいクラスに転校生が来たとします。名簿には名前・年齢・出身地が並んでいますが、その子がどんな人かは、そこからはほとんど分かりません。ところが数週間経って「誰と誰が一緒に帰っているか」が見えてくると、急に像を結び始めます。その人の情報の多くは、その人自身の欄ではなく、周りとのつながりの側にある。

機械学習の教科書に出てくるデータは、たいてい表の形をしています。1行が1サンプルで、行と行は独立している。しかし世の中には、行の「間」こそが本体だというデータが山ほどあります。SNSのフォロー関係、論文の引用、道路網、タンパク質の相互作用、そして分子（原子と化学結合）。これらは点と線、すなわちグラフです。グラフの用語や最短経路のような古典的な扱いはグラフアルゴリズムを1からにまとめてあります。ここで扱うのは、その上で学習する話です。

グラフをそのままニューラルネットに食わせようとすると、すぐ3つの壁にぶつかります。

1. 隣の数がバラバラ。隣が1人のノードと1万人のノードが同じグラフに同居する。入力の長さが固定できない
2. 隣に順番がない。「友達リストの1番目」に意味はない。並べ替えても答えが変わってはいけない（置換不変性）
3. グラフごとに大きさが違う。分子は原子10個のものも100個のものもある

画像でCNNがうまくいくのは、上下左右に必ず隣がいて、位置関係が固定されているからです。グラフにはその足場がありません。GNN（Graph Neural Network）は、この3つを正面から満たす形で組み直されたニューラルネットです。

直感: 隣の話を聞いて、自分を書き換える

GNNの動きは、拍子抜けするほど単純な手順の繰り返しです。

1. すべてのノードが、自分の今の状態を隣人全員に送る
2. すべてのノードが、届いた手紙を1つにまとめる（足す、あるいは平均する）
3. まとめたものと自分の元の状態から、新しい自分の状態を作る

これで1ラウンド。面白いのは2ラウンド目です。2ラウンド目に届く手紙は、隣人が1ラウンド目に更新した状態です。つまりその中には、すでに「隣の隣」の情報が溶け込んでいます。k回繰り返せば、kホップ先までの情報が自分に届く。層の数が「どこまで遠くを見るか」の設定になっている、というのがGNNで最初に押さえるべき性質です。

もう1つ大事なのは、全ノードが同じ規則を使う点です。ノードごとに別の重みを持つのではなく、1組の重み行列を全員で共有します。CNNのフィルタが画像のどこに当てても同じであるように。だからこそ、学習に使ったのと違う大きさ・違う形のグラフにも、同じモデルをそのまま当てられます。

仕組み: メッセージパッシング

いまの3手順をそのまま式にしたものがメッセージパッシングです。GNNの論文はほぼすべて、この枠の中のどこかを差し替えたものだと思って読めます。

記号を1つずつ潰します。$h_v^{(k)}$ は「$k$層目におけるノード$v$の状態ベクトル」で、0層目は入力の特徴量（ユーザーなら登録日や地域、原子なら元素の種類）です。$N(v)$ は$v$の隣人の集合。$\psi$ はメッセージ関数で、送り手と受け手の状態から「送る中身」を作ります。$\bigoplus$ は集約で、届いた手紙の束を1つにまとめる操作。$\phi$ は更新関数で、自分の元の状態とまとめた手紙から新しい状態を作ります。

つまりこの式は、「隣から手紙をもらって、束ねて、自分を書き換える」としか言っていません。

ここで $\bigoplus$ に使えるのは、和・平均・最大のように順番に依存しない操作だけです。「隣人のベクトルを順に連結して全結合層に通す」はやってはいけません。友達リストを並べ替えただけで出力が変わってしまい、先ほどの置換不変性が壊れるからです。この一点が、GNNの設計自由度をかなり強く縛っています。

いちばん有名な具体形が GCN（Graph Convolutional Network）です。全ノードをまとめて行列で書くと1行で済みます。

$H^{(k)}$ は全ノードの状態を縦に並べた行列（ノード数×次元数）。$\tilde{A} = A + I$ は隣接行列に単位行列を足したもの、つまり自分自身への辺（自己ループ）を追加したつながり表です。$\tilde{D}$ はその次数（各ノードの隣の数）を対角に並べた行列、$W^{(k)}$ は学習する重み、$\sigma$ はReLUなどの非線形です。

言い換えると、「自分を含めた隣人の特徴を、次数で割り勘にしながら混ぜ、全員共通の重み行列を掛けて、非線形を通す」。それだけです。

隣人を等しく信用してよいか

いまの平均は「隣人全員を等しく信用する」という、かなり強い仮定を置いています。実際には、10人の友人のうち自分の趣味を説明するのは2人だけ、ということのほうが普通でしょう。そこで次に問題になるのが、隣ごとの「聞く割合」をどう決めるかです。割合である以上、合計は1でなければならない——softmaxの出番です。