Graph Neural Network (GNN)

グラフニューラルネットワーク（GNN）は、グラフを直接扱うニューラルネットワークです。グラフはエッジで接続されたノードの集合で、ノードとエッジの両方が特徴量を持てます。分子（原子と結合）、ソーシャルネットワーク（ユーザーとフォロー関係）、道路網（交差点と道路区間）、3Dメッシュ、人間の骨格の関節はいずれもグラフです。グラフには固定されたグリッドや順序がなく、ノードごとに隣接ノードの数も異なるため、畳み込みニューラルネットワーク（CNN）のスライディングフィルターやリカレントニューラルネットワーク（RNN）の逐次処理をそのまま適用できません。GNNはメッセージパッシングでこの問題に対処します。各ノードが隣接ノードの特徴量を使って自身の特徴ベクトルを繰り返し更新し、ノード自身の属性とグラフ内の位置の両方を表すノード埋め込みを生成します。

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

GNNレイヤーは、3つのステップで各ノードを更新します。各近傍ノードはメッセージを送り、通常は特徴量に学習済みの変換を適用したものを送信します。ノードは、合計、平均、最大値など、順序を考慮しない関数で受信したメッセージを集約します。次に、その集約結果を自身の特徴量と組み合わせ、新しい表現を形成します。集約では順序を考慮しないため、ノードの番号の付け方にかかわらず、結果は変わりません。2017年、Justin Gilmerらは、多くのGNNをこのメッセージパッシングニューラルネットワークフレームワークの一例として説明しました。最後のレイヤーの後、タスク固有のヘッドがノードの埋め込みを読み取り、ノードへのラベル付け、欠損エッジの予測、またはグラフ全体の分類を行います。

各レイヤーでノードの視野は1ホップずつ広がるため、k層の後では、ノードの埋め込みはk本以内のエッジでつながるすべてのノード、すなわちグラフ上の受容野に依存します。以下のPyTorchのコードは、6ノードのパスグラフを作成し、Thomas KipfとMax WellingのGCNの正規化を用いたグラフ畳み込みレイヤーを3つ適用し、autogradを使って各レイヤーの後にノード0へ影響する入力ノードを列挙します。

import torch
from torch import nn

# A path graph 0-1-2-3-4-5 as an adjacency matrix with self-loops
A = torch.eye(6)
for i in range(5):
    A[i, i + 1] = A[i + 1, i] = 1
deg = A.sum(dim=1)
A_hat = A / torch.sqrt(deg[:, None] * deg[None, :])  # GCN normalization D^-1/2 (A + I) D^-1/2

torch.manual_seed(0)
x = torch.randn(6, 4, requires_grad=True)  # 4 input features per node
layers = [nn.Linear(4, 4) for _ in range(3)]

h = x
for k, layer in enumerate(layers, start=1):
    h = torch.tanh(A_hat @ layer(h))  # each node mixes in its neighbors' transformed features
    grad = torch.autograd.grad(h[0].sum(), x, retain_graph=True)[0]
    print(f"After layer {k}, node 0 depends on nodes {grad.abs().sum(dim=1).nonzero().flatten().tolist()}")

[0, 1]、[0, 1, 2]、[0, 1, 2, 3]が出力されます。ノード0の受容野は、レイヤーごとに正確に1ホップずつ広がります。

一般的なGNNアーキテクチャ#

• GCN: グラフ畳み込みネットワークは、H′ = σ(D̃^(−1/2) Ã D̃^(−1/2) H W)を計算します。ここでÃは自己ループを含む隣接行列、D̃はその次数行列です。各ノードとその近傍の次数で重み付けされた平均を求めた後、すべてのノードで共有される重み行列Wを適用します。
• GraphSAGE: ノードごとに一定数の近傍ノードをサンプリングし、集約関数を学習するため、非常に大規模なグラフにもスケールし、学習後に出現したノードの埋め込みも生成できます。
• GAT: グラフ注意ネットワークは、固定された次数ベースの重みではなく、学習可能な注意スコアを使って各近傍ノードに重みを付けます。
• GIN: グラフ同型ネットワークは近傍ノードを合計してMLPに適用します。Keyulu Xuらは、これによってグラフを識別する能力が、標準的なメッセージパッシングの上限であるWeisfeiler-Lehmanテストと同等になることを証明しました。
• グラフトランスフォーマー: すべてのノード間に自己注意を適用し、グラフ構造から導出した位置エンコーディングを追加します。標準的なトランスフォーマー自体も、トークンをノードとする完全結合グラフ上のGNNです。

レイヤーを多数積み重ねると、過剰平滑化が発生します。繰り返し平均を取ることでノードの埋め込みが互いに近づき、区別できなくなるため、多くのGNNではレイヤーを2～3層にとどめています。元のGCNも2層でした。PyTorch GeometricとDeep Graph Library (DGL)は、スパースなエッジリスト上でこれらのレイヤーを効率的に実装します。

実際のアプリケーション#

• 天気予報: Google DeepMindのGraphCastは、2023年にScience誌で発表されました。地球全体を覆うマルチスケールメッシュ上でメッセージパッシングを実行し、0.25°の解像度で10日間の予報を1分未満で生成します。1,380の検証対象のうち90%で、最も精度の高い運用決定論的システムを上回ります。
• 創薬: 2020年、MITの研究者は、分子グラフから抗菌活性を予測する有向メッセージパッシングネットワークを学習させ、ハリシンの特定に活用しました。この化合物は既知の抗生物質とは構造が大きく異なり、実験室の試験で多くの薬剤耐性菌を死滅させました。
• レコメンデーションシステム: PinterestのPinSageは、30億件のピンとボード、および180億本のエッジからなるグラフを使ってピンの埋め込みを学習し、75億件の例で訓練されました。
• スケルトンベースの行動認識: ST-GCNは、身体の関節をノードとして扱い、各フレーム内では骨で、隣接フレーム間では同じ関節同士を接続し、こうして得られる時空間グラフから行動を分類します。YOLO26の姿勢推定モデルは、すべてのフレームで人物ごとに17個のCOCOキーポイントを返します。これらの関節座標からスケルトングラフを構築します。

GNNと関連概念の比較#

• ナレッジグラフ: エンティティ・関係・エンティティの三つ組として事実を格納するデータ構造です。GNNは、たとえば欠けているリンクを予測するために、ナレッジグラフから学習できるモデルです。
• 幾何学的深層学習: データの対称性を基盤に構築されたネットワークを扱う、より広範な分野です。グリッド上のCNN、グラフ上のGNN、メッシュや多様体上のモデルが含まれます。
• CNN: 画像に適用されるCNNは、グリッドグラフ上のメッセージパッシングの特殊なケースです。各ピクセルの近傍数は同じで、相対位置も固定されています。そのためCNNは各近傍位置に個別の重みを学習できますが、不規則なグラフ上のGNNにはできません。