グラフニューラルネットワークとメッセージパッシング

なぜ画像や系列の道具がそのまま使えないのか

CNN は格子状の画素、RNN は一直線の系列 という、規則正しい構造を前提にしています。畳み込みが「左上から右下へ」と窓を動かせるのは、画素に固定の並びがあるからです。ところがソーシャルネットワーク、分子、知識グラフのようなデータは 不規則なグラフ で、ノードごとに近傍の数が違い、しかもノードに 自然な順序がありません。

ここに本質的な制約が出ます。ノード v の表現は、その近傍 {u1, u2, ...} から計算したいのですが、近傍をどの順で並べても結果が変わってはいけません。つまり集約演算は 置換不変（permutation invariant） である必要があります。和・平均・max はこの性質を満たしますが、近傍を連結して全結合層に通すような順序依存の処理は使えません。グラフニューラルネットワーク（GNN）はこの制約の上に設計されます。

メッセージパッシング：近傍集約による表現更新

ほぼ全ての GNN は メッセージパッシング という共通の枠で書けます。各ノードは隣接ノードから「メッセージ」を受け取り、それを集約して自分の状態（埋め込み）を更新する。これを 1 層分の更新として、層を重ねて繰り返します。

ノード v の第 k 層の表現 h_v^(k) を、第 k-1 層から更新する:

  m_v^(k) = AGGREGATE( { h_u^(k-1) : u ∈ N(v) } )   ← 近傍からメッセージを集約
  h_v^(k) = UPDATE( h_v^(k-1), m_v^(k) )             ← 自分の前層表現と統合

  N(v) は v の近傍集合、h_v^(0) は入力ノード特徴

AGGREGATE は近傍集合に対する置換不変関数（和・平均・max など）、UPDATE は重み付き変換＋非線形（典型的には W を掛けて ReLU）です。重要なのは 層数 K がそのまま受容野（reception）になる 点で、K 層重ねると各ノードは K ホップ先のノードまでの情報を取り込めます。CNN で層を深くすると受容野が広がるのと同じ構図ですが、広がり方がグラフの接続に従います。

GCN：次数による対称正規化

GCN（Graph Convolutional Network）は集約を 隣接行列に基づく固定重みの線形和 として定めます。素朴に近傍の和を取るだけだと、次数の高いノードほど集約値が大きくなり、スケールが層ごとに暴れます。GCN はこれを次数で 対称正規化 して抑えます。

GCN の1層（行列形）:
  H^(k) = σ( D̃^(-1/2) Ã D̃^(-1/2) H^(k-1) W^(k) )

  Ã = A + I        自己ループを足した隣接行列（自分自身も近傍に含める）
  D̃               Ã の次数対角行列
  σ               非線形（ReLU など）

D̃^(-1/2) Ã D̃^(-1/2) という対称正規化は、エッジ (u,v) の重みを 1 / sqrt(deg(u)·deg(v)) にすることに相当します。これにより次数差によるスケールの偏りが平準化され、固有値が安定した範囲に収まって学習が安定します。注意したいのは、GCN では 近傍ごとの重みが次数だけで決まる固定値 で、学習されるのは変換 W のみという点です。どの近傍が重要かをデータから決めることはできません。

GAT：注意で近傍ごとの重みを学習する

GAT（Graph Attention Network）は、その「近傍の重みが固定」という GCN の制約を、アテンション機構 を持ち込んで解きます。ノード v が近傍 u から受け取るメッセージの重み α_vu を、両者の表現から動的に計算します。

GAT の注意係数（v から見た近傍 u の重み）:
  e_vu = LeakyReLU( aᵀ [ W h_v ‖ W h_u ] )        ‖ は連結
  α_vu = softmax_u( e_vu )                          v の近傍内で正規化
  h_v^(k) = σ( Σ_{u ∈ N(v)} α_vu · W h_u )

GCN が次数という 構造だけ で重みを決めるのに対し、GAT は 特徴の内容 に応じて「どの近傍を強く見るか」を学習します。実装ではマルチヘッドにして複数の注意を並列に走らせ安定化させるのが普通です。利点は内容依存の選択ができること、代償は近傍ごとに係数を計算する分のコストと、注意が必ずしも解釈可能な重要度になるとは限らない点です。

GraphSAGE：サンプリング集約で大規模・帰納的に

GCN は学習時にグラフ全体の隣接行列を使うため、ノードが数億あるグラフや、学習後に現れた新規ノード への対応が苦手です（全体を見て初めて埋め込みが決まる＝トランスダクティブ寄り）。GraphSAGE はここを 近傍サンプリングと集約関数の学習 で解き、帰納的（inductive） な推論を可能にします。

GraphSAGE の1層:
  N_s(v) = sample(N(v), 個数固定)                   近傍を一定数だけサンプリング
  m_v    = AGGREGATE( { h_u^(k-1) : u ∈ N_s(v) } )  mean / pool / LSTM など
  h_v^(k) = σ( W · [ h_v^(k-1) ‖ m_v ] )            自己表現と集約を連結して変換

ポイントは二つです。第一に、近傍を 固定個数にサンプリング することで、次数のばらつきに依らず計算量を一定化し、ミニバッチ学習を大規模グラフでも回せます。第二に、学習するのは「近傍特徴をどう集約するか」という 関数 なので、未知ノードでもその特徴と近傍さえ与えれば埋め込みを計算できます。これが帰納的設定での強みです。

三者は対立する別物ではなく、同じメッセージパッシングの枠で AGGREGATE の取り方が違うだけ と捉えると関係が一望できます。GCN は固定係数の和、GAT は学習した注意による加重和、GraphSAGE はサンプルした近傍への集約関数、という具合です。

過平滑化：深くすると表現が一様化する

CNN や Transformer は層を深くするほど表現力が増すのが普通ですが、GNN では逆に 層を深くしすぎると性能が落ちる 現象が知られています。これが 過平滑化（over-smoothing） です。

原因はメッセージパッシングそのものにあります。近傍集約は本質的に 近傍との平均化（ラプラシアン平滑化） であり、これを何度も繰り返すと、連結成分内の全ノードの表現が互いに区別できないほど似通った値へ収束していきます。直観的には、K を増やすと各ノードの受容野がグラフ全体に広がり、最終的にどのノードも「ほぼ同じ大域情報」だけを見ることになる、というイメージです。

過平滑化のイメージ:
  浅い層  : 各ノードは局所構造を反映した区別可能な表現
  深い層  : 集約の反復で表現が平均化し、ノード間の差が消える
  → 下流タスク（ノード分類など）で識別不能になり精度が低下

そのため標準的な GNN は 2 〜 3 層程度の浅い構成が実用的に多用されます。深い GNN を機能させるには、残差接続、各層表現の連結（jumping knowledge）、DropEdge のような正則化など、平滑化を緩和する仕掛け が必要になります。「深さ＝受容野」である以上、深さと過平滑化はトレードオフだと押さえておくべきです。

WL 検定：標準的な GNN の表現力の上限

GNN にはもう一つ、原理的な識別力の限界 があります。メッセージパッシング型 GNN が二つのノード（やグラフ）を区別できる能力は、グラフ同型性判定の古典アルゴリズムである WL（Weisfeiler-Leman）検定、正確には 1次元 WL 検定の表現力を 超えられない ことが理論的に示されています。

1-WL は次のように色（ラベル）を反復更新します。これはメッセージパッシングと構造が同じです。

1-WL の色更新（反復）:
  c_v ← HASH( c_v , multiset{ c_u : u ∈ N(v) } )
  色の分布が変化しなくなるまで繰り返す
  二つのグラフで最終的な色の分布が異なれば「非同型」と判定

各ノードが自分の色と近傍の色の 多重集合（multiset） から新しい色を作る——これはまさに近傍集約です。したがって、1-WL が区別できないグラフは、標準的な GNN も区別できません。たとえば特定の正則グラフ（全ノードの次数が同じで局所構造も一致するもの）は 1-WL では同じ色になり、GNN も同一表現を割り当ててしまいます。

メッセージパッシングは「不規則なグラフ上で置換不変に近傍を集める」という一点に集約され、GCN・GAT・GraphSAGE はその集約の取り方の選択肢として整理できます。一方で過平滑化と WL の上限は、GNN が万能ではなく、深さと表現力の両面で原理的な制約を抱えていることを示します。ノードを連続空間のベクトルとして扱う発想は 埋め込みの幾何 と、近傍ごとに重みを動的に決める仕組みは アテンション機構 と地続きで、これらと並べて見ると GNN の設計判断の根拠が線でつながります。