グラフニューラルネットワーク（GNN）は、グラフ構造を持つデータを深層学習で扱うための枠組みです。本記事では、GNNの核心である「ニューラルメッセージパッシング」の仕組みを解説します。本記事はWilliam L. Hamiltonの "Graph Representation Learning"（GRL本）第5章5.1節をもとにしています。

GNNが必要な理由｜置換不変性・等変性とグラフの難しさ

既存の深層学習手法がグラフに使えない理由

画像に対する深層学習では畳み込みニューラルネットワーク（CNN）が使われます。CNNはグリッド状の入力（ピクセル配列）に対して定義されており、画像処理に非常に効果的です。テキストには再帰型ニューラルネットワーク（RNN）が使われ、系列データに対して定義されています。

しかしグラフは、グリッドでも系列でもありません。ノード数・エッジ数が異なる多様な形状を持ち、「何番目のノードか」という順序も本質的には意味を持ちません。グラフに対してCNNやRNNをそのまま適用することはできません。

では、MLP（多層パーセプトロン）はどうでしょうか。グラフ構造を表現した隣接行列 $\mathbf{A}$ を、次式のようにMLPに入力することを考えます。

$$\mathbf{z}_{\mathcal{G}} = \text{MLP}(\mathbf{A}[1] \oplus \mathbf{A}[2] \oplus \cdots \oplus \mathbf{A}[|\mathcal{V}|])$$

ここで $\mathbf{A}[i] \in \mathbb{R}^{|\mathcal{V}|}$ は隣接行列の $i$ 行目、$\oplus$ はベクトルの連結を表します。つまり、グラフ構造を一列に並べ直し、長さ $n^2$ のベクトルにしてからMLPへと入力していることになります。

この方法の問題点は、ノードの順序付け（インデックスの割り当て）に依存してしまうことです。グラフのノードには本来決まった順序はなく、ノードを別の順序で並べても（置換しても）同じグラフを表しています。しかしMLPに入力するとノードの並べ方によって出力が変わってしまいます。

グラフ上のニューラルネットワークが満たすべき性質を数学的に表現すると次の2式となります。置換行列 $\mathbf{P}$（各行各列にひとつだけ1の要素を持ち、それ以外はすべて0の行列、つまりノードの並べ替えを表す行列）を使って表現します。

$$f(\mathbf{P}\mathbf{A}\mathbf{P}^\top) = f(\mathbf{A}) \quad (\text{置換不変性})$$ $$f(\mathbf{P}\mathbf{A}\mathbf{P}^\top) = \mathbf{P}f(\mathbf{A}) \quad (\text{置換等変性})$$

置換不変性は、隣接行列 $\mathbf{A}$ をある関数 $f$ に入力した結果と、Aのノードの順番を並べ替えた行列 $\mathbf{P}\mathbf{A}\mathbf{P}$ を $f$ に入力した結果が同じになる、つまり、ノードの順序が変わっても出力が変わらないという性質です。グラフ全体に対してスカラーや1つのベクトルを出力するモデル（グラフ分類など）が満たすべき性質です。置換等変性は、ノードの順序が変わったとき出力も同じ順序で並び替わるという性質です。各ノードに対して埋め込みベクトルを出力するモデル（ノード分類など）が満たすべき性質です。

このように、MLP、CNN、RNNのような従来のアーキテクチャをグラフの深層学習には不向きで、グラフ専用の新たなアーキテクチャが必要なのです。そのアーキテクチャとは、次節で説明するニューラルメッセージパッシングです。

ニューラルメッセージパッシングの仕組み｜AGGREGATEとUPDATEで近傍情報を伝播する

メッセージパッシングの枠組み

ニューラルメッセージパッシング（Neural Message Passing）[Gilmer et al., 2017]とは、ノードに埋め込みベクトルを持たせ、ノード間でベクトルをメッセージとしてやりとりし、埋め込みベクトルを更新する方法です。

メッセージパッシングは次式で定義されます。各反復 $k$ において、ノード $u$ の隠れ埋め込み $\mathbf{h}_u^{(k)}$ は、その近傍 $\mathcal{N}(u)$ から集約した情報をもとに更新されます。

$$\begin{align} \mathbf{h}_u^{(k+1)} &= \text{UPDATE}^{(k)}\!\left(\mathbf{h}_u^{(k)},\, \text{AGGREGATE}^{(k)}\!\left(\left\{\mathbf{h}_v^{(k)},\, \forall v \in \mathcal{N}(u)\right\}\right)\right) \notag \\ &= \text{UPDATE}^{(k)}\!\left(\mathbf{h}_u^{(k)},\, \mathbf{m}_{\mathcal{N}(u)}^{(k)}\right) \tag{1} \end{align}$$

各記号の意味は次の通りです。

• $\mathbf{h}_u^{(k)} \in \mathbb{R}^{d^{(k)}}$：反復 $k$ でのノード $u$ の隠れ埋め込みベクトル
• $\mathcal{N}(u)$：ノード $u$ のグラフ近傍（近傍ノードの集合）
• $\mathbf{m}_{\mathcal{N}(u)}^{(k)}$：近傍 $\mathcal{N}(u)$ から集約されたメッセージベクトル
• AGGREGATE：近傍ノードの埋め込みを集合として受け取り、メッセージを生成する関数
• UPDATE：メッセージと自身の埋め込みを組み合わせて、次の埋め込みを生成する関数

AGGREGATE と UPDATE はどちらも微分可能な関数（ニューラルネットワーク）であれば何でも使えます。

初期埋め込みはノードの特徴量で初期化します。

$\mathbf{h}_u^{(0)} = \mathbf{x}_u, \quad \forall u \in \mathcal{V}$

流れ場を予測するGNNであれば、 $\mathbf{x}_u$ は各格子点での速度、圧力、温度といった物理量です。

$K$ 回のメッセージパッシングを経た最終的な出力をノード埋め込みとして使います。

$\mathbf{z}_u = \mathbf{h}_u^{(K)}, \quad \forall u \in \mathcal{V}$

AGGREGATEやUPDATEには近傍ノードの順序に依存しない関数を選ぶので、GNNは設計上、置換等変性を満たします。

ノードの特徴量がない場合

GNNの枠組みでは、すべてのノードに特徴量ベクトル $\mathbf{x}_u$ が必要です。多くのグラフでは自然にノード特徴量が存在します（生物学的ネットワークの遺伝子発現量、ソーシャルネットワークのプロフィール情報など）。

特徴量がない場合は、次の方法で代替できます。

• ノード統計量（次数、クラスタリング係数など）を特徴量として使う
• 各ノードをone-hotベクトルで識別する（ただし、この方法はモデルを帰納的でなくし、未知ノードへの汎化ができなくなる）

k反復後に何を学ぶか

メッセージパッシングを $k$ 回繰り返すと、各ノードの埋め込みはそのノードの $k$ ホップ近傍の情報を含みます。

• $k = 1$：1ホップ近傍（直接隣接するノード）の情報
• $k = 2$：2ホップ近傍の情報
• 一般に $k$ 回反復後：$k$ ホップ近傍の情報

ノード埋め込みに含まれる情報は2種類に分類できます。

1つ目は構造情報です。$k$ 回の反復後、ノード $u$ の埋め込み $\mathbf{h}_u^{(k)}$ は、$u$ の $k$ ホップ近傍にあるノードの次数などの構造的な情報を含みます。分子グラフでは、この構造情報を使って原子の種類やベンゼン環のような構造モチーフを推定できます。

2つ目は特徴量情報です。$k$ 回の反復後、各ノードは $k$ ホップ近傍にあるすべてのノードの特徴量情報も集約します。これはCNNにおけるプーリング操作に類似しています。CNNが空間的に定義されたパッチから特徴を集約するのに対し、GNNはグラフの近傍から集約します。

基本GNNモデルの数式と自己ループ｜隣接行列を使った実装イメージ

基本GNNモデルの数式

式 (1) はAGGREGATEとUPDATEを具体的に定めないと実装できません。ここでは最もシンプルな実装として、Merkwirth and Lengauer [2005] および Scarselli et al. [2009] が提案した基本GNNモデルを紹介します。

$$\mathbf{h}_u^{(k)} = \sigma\!\left(\mathbf{W}_{\text{self}}^{(k)} \mathbf{h}_u^{(k-1)} + \mathbf{W}_{\text{neigh}}^{(k)} \sum_{v \in \mathcal{N}(u)} \mathbf{h}_v^{(k-1)} + \mathbf{b}^{(k)}\right) \tag{2}$$

各記号は次の通りです。

• $\mathbf{W}_{\text{self}}^{(k)},\, \mathbf{W}_{\text{neigh}}^{(k)} \in \mathbb{R}^{d^{(k)} \times d^{(k-1)}}$：学習可能なパラメータ行列
• $\sigma$：要素ごとの非線形活性化関数（tanh または ReLU）
• $\mathbf{b}^{(k)} \in \mathbb{R}^{d^{(k)}}$：バイアス項

このモデルでは、AGGREGATEとUPDATEはそれぞれ次のように定義されます。

$$\mathbf{m}_{\mathcal{N}(u)} = \sum_{v \in \mathcal{N}(u)} \mathbf{h}_v \tag{3}$$ $$\text{UPDATE}(\mathbf{h}_u,\, \mathbf{m}_{\mathcal{N}(u)}) = \sigma\!\left(\mathbf{W}_{\text{self}} \mathbf{h}_u + \mathbf{W}_{\text{neigh}} \mathbf{m}_{\mathcal{N}(u)}\right) \tag{4}$$

AGGREGATEには近傍ノードの埋め込みの総和を使います。近傍ノードの埋め込みを足し合わせてメッセージを作り、UPDATEでは自身の埋め込みと合わせて線形変換してから非線形活性化関数を適用します。

グラフ全体での行列表現

式 (2) はノードに注目した式ですが、同じ操作をグラフ全体をまとめて行列演算で表現することもできます。$k$ 層目のノード表現を行列 $\mathbf{H}^{(k)} \in \mathbb{R}^{|\mathcal{V}| \times d^{(k)}}$（各行がノードの埋め込み）とすると、

$$\mathbf{H}^{(t)} = \sigma\!\left(\mathbf{A}\mathbf{H}^{(k-1)}\mathbf{W}_{\text{neigh}}^{(k)} + \mathbf{H}^{(k-1)}\mathbf{W}_{\text{self}}^{(k)}\right) \tag{5}$$

ここで $\mathbf{A}$ はグラフの隣接行列です。行列 $\mathbf{A}\mathbf{H}^{(k-1)}$ の $u$ 行目は、ノード $u$ の近傍ノードの埋め込みを足し合わせたベクトルになります。これは式 (3) の総和集約に対応しています。

この行列表現は全GNNモデルに使えるわけではありませんが、疎な行列積として効率よく実装できるため、実用上よく使われます。

自己ループを使ったメッセージパッシングの簡略化

基本GNNモデルの簡略化として、入力グラフに自己ループ（ノードからそれ自身へのエッジ）を付け加え、UPDATEを省略する方法があります。

$$\mathbf{h}_u^{(k)} = \text{AGGREGATE}\!\left(\left\{\mathbf{h}_v^{(k-1)},\, \forall v \in \mathcal{N}(u) \cup \{u\}\right\}\right) \tag{6}$$

集約の対象に自身のノード $u$ が含まれるため、UPDATEで明示的に自身の埋め込みを組み合わせる必要がなくなります。基本GNNで $\mathbf{W}_{\text{self}} = \mathbf{W}_{\text{neigh}} = \mathbf{W}$ と共有した場合、行列表現は次の通りです。

$$\mathbf{H}^{(t)} = \sigma\!\left((\mathbf{A} + \mathbf{I})\mathbf{H}^{(t-1)}\mathbf{W}^{(t)}\right) \tag{7}$$

$\mathbf{I}$ は単位行列で、自己ループを表します。この「self-loop GNN」はパラメータ数が少なく過学習しにくいというメリットがあります。一方、自身の埋め込みと近傍からの情報を区別できないため、表現力が限られるというデメリットもあります。

GNNの入力と出力｜グラフと特徴量を入れてノード埋め込みを得る

GNNへの入力

GNNへの入力は次の2つです。

• グラフ構造 $\mathcal{G} = (\mathcal{V}, \mathcal{E})$：隣接行列 $\mathbf{A}$ として与える
• ノード特徴量行列 $\mathbf{X} \in \mathbb{R}^{|\mathcal{V}| \times d}$：各行がノード $u$ の特徴量ベクトル $\mathbf{x}_u$

入力	形状	意味
隣接行列 $\mathbf{A}$	$\|\mathcal{V}\| \times \|\mathcal{V}\|$	グラフのエッジ構造
特徴量行列 $\mathbf{X}$	$\|\mathcal{V}\| \times d$	各ノードの属性（$d$ 次元）

流体領域では、非構造格子の場合、$\mathbf{A}$ に格子点間の接続関係、$\mathbf{X}$ に座標・速度・圧力などの物理量を格納します。

GNNの出力

$K$ 回のメッセージパッシングを経ると、各ノードの埋め込みベクトル $\mathbf{z}_u = \mathbf{h}_u^{(K)}$ が得られます。これをまとめた行列 $\mathbf{Z} \in \mathbb{R}^{|\mathcal{V}| \times d^{(K)}}$ がGNNの出力です。

ノード埋め込み $\mathbf{z}_u$ は、ノード $u$ の $K$ ホップ近傍の構造情報と特徴量情報を集約したベクトルです。このベクトルを下流のタスクに応じた予測に使います。

タスク	GNN出力の使い方
ノード分類	$\mathbf{z}_u$ を分類器に入力して各ノードのラベルを予測
関係予測	$\mathbf{z}_u$ と $\mathbf{z}_v$ の類似度からエッジの有無を予測
グラフ分類・回帰	全ノード埋め込みをプーリングしてグラフ全体の表現を作り予測

流体領域では、格子グラフを入力したGNNから得られるノード埋め込みを使って、各格子点の流速・圧力を予測するタスク（グラフ上の回帰）や、ジオメトリが異なる複数のグラフを学習して空力特性を予測するタスク（グラフ回帰）に応用できます。

まとめ

ここまで、GNNの核心であるニューラルメッセージパッシングについて、流体に関するタスクを例に解説してきました。

• GNNはニューラルメッセージパッシングを使ってグラフ上のノード埋め込みを学習する
• 各反復で AGGREGATE（近傍の情報を集約）と UPDATE（自身の埋め込みを更新）を繰り返す
• $K$ 回の反復後、各ノードは $K$ ホップ近傍の構造情報と特徴量情報を含む埋め込みを持つ
• 基本GNNモデルは近傍ノードの埋め込みの総和を集約し、線形変換と非線形活性化で更新する
• 自己ループを付加すると AGGREGATE のみで実装でき、行列表現は $\mathbf{H}^{(t)} = \sigma((\mathbf{A}+\mathbf{I})\mathbf{H}^{(t-1)}\mathbf{W}^{(t)})$
• 入力: グラフ $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ とノード特徴量行列 $\mathbf{X} \in \mathbb{R}^{|\mathcal{V}| \times d}$
• 出力: ノード埋め込み行列 $\mathbf{Z} \in \mathbb{R}^{|\mathcal{V}| \times d^{(K)}}$

さらに深く学ぶための書籍

本記事のテーマをより深く学びたい方には、以下の書籍をおすすめします。

• Graph Representation Learning（William L. Hamilton、Morgan & Claypool Publishers）：本記事のベースとなった教科書です。メッセージパッシングの枠組みからGNNの最新手法まで体系的に解説しており、著者のウェブサイトから無料で入手できます。