前回の記事では、GNNの核心であるニューラルメッセージパッシングの枠組みと、最も基本的なAGGREGATEの実装（近傍埋め込みの総和）を解説しました。本記事では、この基本的な総和集約をどのように改善・拡張できるかを、3種類のアプローチで解説します。本記事はWilliam L. Hamiltonの "Graph Representation Learning"（GRL本）第5章5.2節をもとにしています。

近傍正規化集約｜次数の違いによる不安定性を解消する（GCN）

総和集約の問題点｜次数依存性

前回解説した基本GNNでは、近傍集約に次の総和を使います。

$$\mathbf{m}_{\mathcal{N}(u)} = \sum_{v \in \mathcal{N}(u)} \mathbf{h}_v \tag{1}$$

この総和集約にはノードの次数（接続するエッジの数）に対して敏感という問題があります。あるノード $u$ が別のノード $u'$ より100倍多くの近傍ノードを持つ場合、総和の大きさも100倍程度になります。

$$\left\|\sum_{v \in \mathcal{N}(u)} \mathbf{h}_v\right\| \gg \left\|\sum_{v' \in \mathcal{N}(u')} \mathbf{h}_{v'}\right\|$$

この大きさの違いはメッセージの大きさのスケールをノードごとに大幅に変化させ、数値的な不安定性や最適化の困難を引き起こします。

平均集約と対称正規化

最もシンプルな解決策は、総和の代わりに平均を使うことです。

$$\mathbf{m}_{\mathcal{N}(u)} = \frac{\sum_{v \in \mathcal{N}(u)} \mathbf{h}_v}{|\mathcal{N}(u)|} \tag{2}$$

平均集約はノードの次数で割ることで、次数によるスケールの差を除去します。

さらに Kipf and Welling [2016a] は、次の対称正規化（symmetric normalization）を提案しています。

$$\mathbf{m}_{\mathcal{N}(u)} = \sum_{v \in \mathcal{N}(u)} \frac{\mathbf{h}_v}{\sqrt{|\mathcal{N}(u)||\mathcal{N}(v)|}} \tag{3}$$

ここで $|\mathcal{N}(u)|$ はノード $u$ の次数、$|\mathcal{N}(v)|$ はノード $v$ の次数です。集約する側（$u$）と集約される側（$v$）の両方の次数で正規化する点が、単純な平均との違いです。

対称正規化を使うモチベーションは次の通りです。引用グラフを例にすると、何千もの論文から引用されている高次数のノード（著名な論文）の情報は、コミュニティ帰属の推定に有用でないことがあります。そのようなノードからの情報は、$|\mathcal{N}(v)|$ が大きいほど小さく重み付けされます。

グラフ畳み込みネットワーク（GCN）の定義

対称正規化と自己ループを組み合わせたモデルが、グラフ畳み込みネットワーク（Graph Convolutional Network, GCN）[Kipf and Welling, 2016a] です。GCNのメッセージパッシングは次のように定義されます。

$$\mathbf{h}_u^{(k)} = \sigma\!\left(\mathbf{W}^{(k)} \sum_{v \in \mathcal{N}(u) \cup \{u\}} \frac{\mathbf{h}_v}{\sqrt{|\mathcal{N}(u)||\mathcal{N}(v)|}}\right) \tag{4}$$

自己ループを含めることで、自身の埋め込みも近傍と同じ変換 $\mathbf{W}^{(k)}$ で処理されます。GCNは最も広く使われるGNNの基本アーキテクチャの1つです。

正規化のトレードオフ

正規化を行うことで学習の安定性は向上しますが、構造情報が失われるというデメリットもあります。式(2)を使う基本GNNは、理論的に式(1)よりも表現力が低いことが証明されています。次数が異なるノードを区別できなくなるためです。

正規化が有効なのは、ノードの特徴量情報が構造情報より重要な場合、または次数の分布が広くて最適化が不安定になる場合です。用途に応じて選択する必要があります。

セット集約関数｜MLP・Janossy poolingで表現力を高める

近傍集約はセット関数として定式化できる

近傍集約は、近傍ノードの埋め込みの集合 $\{\mathbf{h}_v,\, \forall v \in \mathcal{N}(u)\}$ を1つのベクトル $\mathbf{m}_{\mathcal{N}(u)}$ に写す関数です。近傍ノードには自然な順序がないため、この関数は置換不変でなければなりません。

これまで見てきた総和・平均・対称正規化はすべて置換不変ですが、理論的に表現力の上限があります。より表現力の高い置換不変なセット関数を設計するアプローチが、セット集約（Set Aggregators）です。

セットプーリング｜MLPで汎用的なセット関数を近似する

Zaheer et al. [2017] は、以下の形のAGGREGATEが置換不変なセット関数であり、かつ高い表現力を獲得し得ることを示しました。

$$\mathbf{m}_{\mathcal{N}(u)} = \text{MLP}_\theta\!\left(\sum_{v \in \mathcal{N}(u)} \text{MLP}_\phi(\mathbf{h}_v)\right) \tag{5}$$

ここで $\text{MLP}_\theta$ と $\text{MLP}_\phi$ はそれぞれ学習可能なパラメータ $\theta$, $\phi$ を持つ多層パーセプトロンです。

処理の流れは次の通りです。

1. 各近傍ノードの埋め込み $\mathbf{h}_v$ を $\text{MLP}_\phi$ で変換する
2. 変換後のベクトルを総和で集約する（置換不変）
3. 集約結果を $\text{MLP}_\theta$ でさらに変換してメッセージを得る

総和の代わりに要素ごとの最大値（element-wise max）や最小値を使うこともできます [Qi et al., 2017]。また正規化を組み合わせることも可能で、GraphSAGE-pool [Hamilton et al., 2017b] はこのアプローチの一例です。

セットプーリングは性能を若干向上させる効果がありますが、MLPの深さによっては過学習のリスクが高まります。実用上は、隠れ層が1つだけのMLPを使うことが推奨されます。

Janossyプーリング｜置換に敏感な関数で置換不変性を達成する

セットプーリングとは異なるアプローチとして、Murphy et al. [2018] が提案した Janossy pooling があります。

セットプーリングは「置換不変な縮約関数 + MLP」で表現力を高めます。一方 Janossy pooling では、敢えて順序によって返値が異なる関数（置換感応関数）を用い、近傍ノードをいろんな順序にして置換感応関数に入力した結果を平均することで置換不変な出力を得ます。

$$\mathbf{m}_{\mathcal{N}(u)} = \text{MLP}_\theta\!\left(\frac{1}{|\Pi|} \sum_{\pi \in \Pi} \rho_\phi\!\left(\mathbf{h}_{v_1}, \mathbf{h}_{v_2}, \ldots, \mathbf{h}_{v_{|\mathcal{N}(u)|}}\right)_\pi\right) \tag{6}$$

ここで $\Pi$ は置換の集合、$\pi_i$ は置換関数（近傍ノードを特定の順序に並べる関数）、$\rho_\phi$ は系列データを処理できる置換感応関数です。$\rho_\phi$ には系列に対して強力なアーキテクチャであるLSTM [Hochreiter and Schmidhuber, 1997] がよく使われます。

全ての置換について総和をとると計算量が膨大になるため、実用上は次の2つのアプローチが使われます。

1. ランダムに一部の置換をサンプリングして総和をとる
2. 正準順序（canonical ordering）を採用する（例：次数の降順に近傍ノードを並べる）

Janossy pooling はセットプーリングより優れた性能を示すことが報告されています [Murphy et al., 2018]。

近傍アテンション｜重要な近傍ノードに着目する（GAT・多頭アテンション）

アテンションとは何か？なぜ使うのか？

正規化集約やセット集約では、近傍ノードからの情報をどう集約するかを工夫しますが、各近傍ノードの「重要度」は考慮しません。しかし実際のグラフでは、すべての近傍ノードが同等に重要とは限りません。アテンションとは、ニューラルネットワークに入力のどの部分に注目するか（attention）を学ばせる手法です。

例えば引用グラフで論文のトピックを推定する場合、同じ研究分野の論文からの情報は有用ですが、様々な分野にまたがる高被引用論文からの情報は無関係なノイズになり得ます。アテンションを使う理由は、重要な近傍ノードには高い重みを割り当て、重要でないノードには低い重みを割り当てることで、より高い表現力の獲得が期待できるからです。

近傍アテンションのアイデアは Bahdanau et al. [2015] のアテンションメカニズムをGNNに適用したものです。

グラフアテンションネットワーク（GAT）

GNNに初めてアテンションを適用したモデルが、Veličković et al. [2018] のグラフアテンションネットワーク（Graph Attention Network, GAT）です。

まずアテンション重みを使った集約を定義します。

$$\mathbf{m}_{\mathcal{N}(u)} = \sum_{v \in \mathcal{N}(u)} \alpha_{u,v}\, \mathbf{h}_v \tag{7}$$

ここで $\alpha_{u,v}$ はノード $u$ が近傍ノード $v$ に割り当てるアテンション重みです。GATでのアテンション重みは次のように定義されます。

$$\alpha_{u,v} = \frac{\exp\!\left(\mathbf{a}^\top [\mathbf{W}\mathbf{h}_u \oplus \mathbf{W}\mathbf{h}_v]\right)}{\sum_{v' \in \mathcal{N}(u)} \exp\!\left(\mathbf{a}^\top [\mathbf{W}\mathbf{h}_u \oplus \mathbf{W}\mathbf{h}_{v'}]\right)} \tag{8}$$

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

• $\mathbf{a}$：学習可能なアテンションベクトル
• $\mathbf{W}$：学習可能なパラメータ行列
• $\oplus$：ベクトルの連結操作
• 分母のソフトマックスにより、近傍ノード全体でアテンション重みの和が1になる

ノード $u$ の埋め込み $\mathbf{h}_u$ とノード $v$ の埋め込み $\mathbf{h}_v$ を連結した後、アテンションベクトル $\mathbf{a}$ との内積でスカラーを計算し、ソフトマックスで正規化します。これにより、ノード $u$ からの視点で見たときの各近傍ノード $v$ の重要度が計算されます。

アテンション機構が無い集約、たとえば式(5)では、ある近傍ノードをMLPに入力した結果はすべて同じです。一方、式(8)では同じ近傍ノード $v$ を入力しても、中心ノード $u$ によって出力も変わるため、「$u$ の近傍での相対比較の方法」を学べます。式(5.17)でも高い表現力を学ぶことは可能ですが、モデルサイズとデータ数が同じなら、アテンション機構が備わったGNNの方が表現力が高まりやすい、ということです。

GATのアテンション式(8)の他にも、アテンションの亜種があります。

双線形アテンション：

$$\alpha_{u,v} = \frac{\exp\!\left(\mathbf{h}_u^\top \mathbf{W} \mathbf{h}_v\right)}{\sum_{v' \in \mathcal{N}(u)} \exp\!\left(\mathbf{h}_u^\top \mathbf{W} \mathbf{h}_{v'}\right)} \tag{9}$$

MLPアテンション：

$$\alpha_{u,v} = \frac{\exp\!\left(\text{MLP}(\mathbf{h}_u, \mathbf{h}_v)\right)}{\sum_{v' \in \mathcal{N}(u)} \exp\!\left(\text{MLP}(\mathbf{h}_u, \mathbf{h}_{v'})\right)} \tag{10}$$

ここでMLPはスカラーを出力します。

多頭アテンション（Multi-head Attention）

トランスフォーマーアーキテクチャ [Vaswani et al., 2017] と同様に、GNNでも多頭アテンション（multi-head attention）を使うことができます。$K$ 個の独立したアテンション重み $\alpha_{u,v,k}$（$k = 1, \ldots, K$）を計算し、それぞれのアテンションヘッドで集約したメッセージを連結します。

$$\mathbf{m}_{\mathcal{N}(u)} = [\mathbf{a}_1 \oplus \mathbf{a}_2 \oplus \cdots \oplus \mathbf{a}_K] \tag{11}$$ $$\mathbf{a}_k = \mathbf{W}_k \sum_{v \in \mathcal{N}(u)} \alpha_{u,v,k}\, \mathbf{h}_v \tag{12}$$

各アテンションヘッドが異なる「注目の観点」を学習できるため、表現力が高まります。

GNNとトランスフォーマーの関係

基本的なトランスフォーマー層は、完全グラフ（すべてのノード間にエッジがある）を入力とするGNN層に多頭アテンションを適用した場合と等価です。トランスフォーマーを出発点として、隣接行列によるマスクをアテンション層に適用することでGNNを実装することもできます。

ただし、トランスフォーマーではすべてのノード対についてアテンションを計算するため、時間計算量が $O(|\mathcal{V}|^2)$ になります。通常のGNNはエッジに沿ってのみ集約するため $O(|\mathcal{V}||\mathcal{E}|)$ であり、疎なグラフでは標準的なGNNの方が効率的です。

アテンションを使うべき状況

アテンションは「一部の近傍ノードが他より重要であると事前知識がある場合」に特に有効です。例えば次のような状況です。

• 引用グラフで論文のトピックを分類するとき、分野横断的な高被引用論文の情報は有用でない
• 分子グラフで原子の役割を推定するとき、特定の結合の強さが予測に重要な場合
• CFDの格子グラフで物理量を予測するとき、上流側の格子点の情報が下流側より重要な流れがある場合

まとめ

GNNのAGGREGATE関数は、総和集約をベースとして、3種類の拡張があります。

アプローチ	モチベーション	代表モデル
近傍正規化	次数差による数値不安定性の解消	GCN [Kipf & Welling, 2016a]
セット集約	表現力の向上（普遍的近似）	GraphSAGE-pool, Janossy pooling
近傍アテンション	重要な近傍ノードへの選択的集約	GAT [Veličković et al., 2018]

正規化は学習の安定性を高めますが構造情報を失います。セット集約は表現力を高めますが過学習のリスクがあります。アテンションは有益な近傍を選択的に使えますが計算コストが増えます。用途と計算コストに応じて適切な集約関数を選ぶことが重要です。

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

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

入門・学部レベル

• Deep Learning（Ian Goodfellow、Yoshua Bengio、Aaron Courville、MIT Press）：ニューラルネットワークの基礎、アテンションメカニズムを含む発展的なトピックまでを体系的に解説しています。GNNを学ぶ前の深層学習の基礎固めに適しています。

発展・大学院レベル

• Graph Representation Learning（William L. Hamilton、Morgan & Claypool Publishers）：本記事のベースとなった教科書です。近傍集約・アテンション・GCN・GATの理論的背景まで体系的に解説しており、著者のウェブサイトから無料で入手できます。