グラフニューラルネットワーク (GNN) 入門

グラフデータ

本記事はGeminiの出力をプロンプト工学で整理した業務ドラフト（未検証）です。

グラフニューラルネットワーク (GNN) 入門

グラフニューラルネットワーク (GNN) は、グラフ構造データの表現学習を可能にする深層学習モデルです。本稿ではその基本概念、中核アルゴリズム、評価方法を解説します。

背景

課題と先行研究

従来のニューラルネットワークは、画像やテキストのようなユークリッド空間上のデータに対して高い性能を発揮しますが、ノード間の関係性を持つグラフデータには直接適用が困難でした。これは、グラフデータが非ユークリッド空間に存在し、ノードの順序に不変性がないためです。ノードIDに基づくOne-hotエンコーディングでは、ノード間の構造的類似性や連結性を捉えることができません。

この課題に対し、初期にはグラフカーネルを用いた手法や、グラフのスペクトル分解に基づくSpectral GNNが提案されました。しかし、これらの手法は計算コストが高い、inductive learning（未知のグラフへの汎化）が難しい、非ユークリッド空間への一般化が不十分といった課題を抱えていました。GNNは、ノード間の情報伝播メカニズムを導入することで、これらの課題の解決を試みています。特に、Message Passing Neural Network (MPNN) は、GNNの多くのバリアントを統一的に捉えるフレームワークを提供しました。

提案手法

メッセージ伝播によるノード表現学習

GNNの核となるのは「メッセージ伝播（Message Passing）」メカニズムです。各ノードは自身の特徴量と、近隣ノードから集約されたメッセージに基づいて、自身の新しい特徴表現（埋め込みベクトル）を繰り返し更新します。これにより、ノードの局所的な構造情報が複数ホップにわたって集約され、より包括的な表現が学習されます。

GNN層の一般的な形式は、以下の2つのステップで構成されます。

  1. メッセージ生成と集約（Aggregate）: 各ノードは、自身の近隣ノードからの特徴量（またはメッセージ）を集約します。この集約関数は、SUM, MEAN, MAXなどの対称的な関数であることが一般的です。
  2. 更新（Update）: 集約された情報と自身の以前の特徴量を組み合わせて、新しい特徴表現を更新します。これは通常、多層パーセプトロン (MLP) などの非線形変換によって行われます。

このプロセスは、複数の層（レイヤー）にわたって反復的に実行されます。層が深くなるほど、ノードはより遠い近隣ノードからの情報を取り込むことができます。

GCN層の擬似コード

以下に、Graph Convolutional Network (GCN) の単一層の擬似コードを示します。GCNは、正規化された隣接行列を用いて近隣ノードの特徴を集約し、線形変換と非線形活性化関数を適用します。

pseudo
function GCNLayer(node_features_in, adjacency_matrix_norm, weight_matrix, activation_function):
    # Input:
    #   node_features_in: N x D_in matrix (N: nodes, D_in: input feature dimension)
    #   adjacency_matrix_norm: N x N matrix (graph connectivity, self-loops added and symmetrically normalized: D^(-1/2) A D^(-1/2))
    #   weight_matrix: D_in x D_out matrix (learnable weight parameters)
    #   activation_function: Non-linear activation function (e.g., ReLU)
    #
    # Output:
    #   node_features_out: N x D_out matrix (new node features for the next layer)
    #
    # Preconditions:
    #   - adjacency_matrix_norm is pre-computed to include self-loops and symmetric normalization.
    #   - node_features_in and weight_matrix have compatible dimensions.

    # Step 1: Feature transformation for all nodes
    # Z = X @ W (where @ denotes matrix multiplication)
    transformed_features = node_features_in @ weight_matrix  # N x D_out

    # Step 2: Message passing (aggregation using normalized adjacency matrix)
    # H_out = A_norm @ Z
    aggregated_features = adjacency_matrix_norm @ transformed_features # N x D_out

    # Step 3: Apply non-linear activation
    node_features_out = activation_function(aggregated_features)

    return node_features_out

計算量とメモリ使用量

上記のGCNLayerの擬似コードに基づき、計算量とパラメトリックなメモリ使用量を分析します。

計算量

  • transformed_features = node_features_in @ weight_matrix: $O(N \cdot D_{in} \cdot D_{out})$
  • aggregated_features = adjacency_matrix_norm @ transformed_features:
    • 隣接行列が密な場合: $O(N^2 \cdot D_{out})$
    • 隣接行列が疎な場合 (推奨): $O(M \cdot D_{out})$ （$M$はエッジ数）
    • 多くのグラフは疎であるため、$O(M \cdot D_{out})$ が支配的です。

したがって、1層のGCNレイヤーの総計算量は、$O(N \cdot D_{in} \cdot D_{out} + M \cdot D_{out})$ となります。

パラメトリックなメモリ使用量

  • weight_matrix: $O(D_{in} \cdot D_{out})$ （学習可能なパラメータ）
  • 中間特徴量 (transformed_features, aggregated_features): $O(N \cdot D_{out})$
  • 入力 (node_features_in, adjacency_matrix_norm) はモデルのパラメータではないため含みません。

したがって、1層のGCNレイヤーのパラメトリックなメモリ使用量は、$O(D_{in} \cdot D_{out})$ となります。これは、GNNがノード数に比例するパラメータを持たないため、大規模グラフに対してもメモリ効率が良いことを示します。

モデル/データフロー

一般的なGNNを用いたグラフデータ処理のフローチャートを以下に示します。

flowchart TD
    A["入力グラフ"] --> B{"ノード特徴初期化"};
    B --> C{"隣接行列構築と正規化"};
    C --> D{"メッセージ伝播層(L層)"};
    D --> E["各ノードの特徴集約"];
    E --> F["ノード特徴更新"];
    F --> D;
    D -- L回繰り返し --> G["最終ノード埋め込み"];
    G --> H["ダウンストリームタスクヘッド"];
    H --> I["出力(ノード分類/リンク予測など)"];

実験設定

データセット

  • Cora: 科学論文の引用ネットワーク。ノードは論文、エッジは引用関係。ノード特徴はBoW表現、ノード分類タスク (7クラス)。
  • CiteSeer: Coraと同様の引用ネットワーク。ノード分類タスク (6クラス)。
  • PubMed: Coraと同様の引用ネットワーク。ノード分類タスク (3クラス)。
  • OGB (Open Graph Benchmark): 大規模なベンチマークデータセット。例えば ogbn-arxiv は大規模な引用ネットワークで、ノード分類タスクに使用されます。

タスク

  • ノード分類: 各ノードにカテゴリラベルを割り当てる。
  • リンク予測: グラフ内の未観測のエッジ（リンク）を予測する。

モデル

  • GCN (Graph Convolutional Network): 上述のメッセージ伝播メカニズムに基づく代表的なモデル。
  • GraphSAGE: 近隣ノードの情報をサンプリングして集約することで、Inductive Learning (訓練時に見なかったノードへの汎化) に対応。
  • GAT (Graph Attention Network): 近隣ノードからのメッセージを集約する際に、Attentionメカニズムを用いて重要度を学習。

ハイパーパラメータと正則化

  • 学習率: 0.01
  • エポック数: 200〜500
  • 隠れ層の次元数: 16, 32, 64
  • ドロップアウト率: 0.5 (過学習防止)
  • 正則化: L2正則化 (weight_decay: 5e-4)

再現性と環境

  • 乱数種: random_seed = 42 (PyTorch, NumPy, Pythonの乱数状態を固定)
  • 環境: Python 3.9, PyTorch 1.10.0, PyTorch Geometric 2.0.0, NumPy 1.21.0

評価指標

  • ノード分類:
    • Accuracy: 正しく分類されたノードの割合。
    • F1-score (Micro/Macro): 特にクラス不均衡がある場合に有用。
  • リンク予測:
    • AUROC (Area Under the Receiver Operating Characteristic curve): 予測されたリンクスコアの閾値を変化させた際の真陽性率と偽陽性率の関係を示す。
    • AP (Average Precision): 予測されたリンクの順位リストの品質を評価。

結果

Coraデータセットを用いたノード分類タスクにおいて、GCNは78.5%〜81.0%の分類精度を達成しました。これは、ベースラインであるMLP (約60%) やLabel Propagation (約70%) と比較して有意に高い性能です。GraphSAGEは、特にogbn-arxivのような大規模かつinductiveな設定において、GCNを上回る分類精度を示しました。リンク予測タスクでは、GATが近隣ノードの重要度を学習することで、AUROCスコアにおいて既存手法を数パーセントポイント上回る結果を示しました。

考察

GNNは、ノードの初期特徴量だけでなく、グラフ構造から近隣ノードの情報を効果的に集約することで、表現学習を強化できることが示されました。特に、メッセージ伝播によって生成される低い次元のノード埋め込みは、元の高次元でスパースな特徴量よりも、ノードのセマンティックな意味と構造的な役割をより豊富に捉えていると解釈できます。これは、GNNがグラフの局所的な構造パターンを符号化する能力に起因すると考えられます。

限界

過平滑化 (Over-smoothing)

GNN層を深くする（例えば5層以上）と、ノードの特徴表現が均一化し、最終的にすべてのノードがほぼ同じ埋め込みを持つ「過平滑化」と呼ばれる現象が発生する仮説があります。これにより、ノード間の識別能力が低下し、モデル性能が劣化します。これは、メッセージ伝播が繰り返し行われることで、遠いノードの情報が過剰に伝播し、各ノードが受け取る情報が平均化されるためです。

スケーラビリティ

大規模なグラフでは、全グラフをメモリに保持することや、隣接行列と特徴行列の乗算の計算コストが課題となります。特に、ノード数$N$が数百万を超える場合、従来のバッチ処理が困難になります。

異種グラフ (Heterogeneous Graphs)

ノードやエッジの種類が複数存在する異種グラフへの適用は、追加のモデリングが必要です。単一のメッセージ伝播関数では、異なる関係性の情報を適切に集約できない可能性があります。

失敗例と感度分析

  • ハイパーパラメータ: 学習率が高すぎると学習が不安定になり、損失が発散する傾向があります。小さすぎると収束が遅れます。隠れ層の次元数が小さすぎると表現能力が不足し、大きすぎると過学習や計算コストの増大を招きます。
  • 正則化: ドロップアウト率が低すぎると過学習しやすく、高すぎるとアンダーフィッティングにつながります。
  • 初期値: 重み行列の初期値は性能に影響を与えますが、Glorot (Xavier) 初期化やHe初期化を用いることで、安定した学習が可能です。特にGCNでは、正規化された隣接行列が活性化関数に与える影響が大きいため、初期値の選択が大切です。
  • スケジューラ: 固定学習率よりも、Cosine Annealingなどの学習率スケジューラを導入することで、より良い最小値に収束する可能性があります。

今後

GNNの研究は活発であり、以下のような方向性が期待されます。

  • スケーラビリティの改善: 大規模グラフに対応するためのサンプリング手法 (e.g., Cluster-GCN, GraphSAINT) のさらなる効率化、並列・分散処理技術の導入。
  • 異種グラフ学習: 異なるノード・エッジタイプをより効果的に扱うための汎用的なGNNアーキテクチャの研究。
  • 理論的基盤の深化: GNNの表現能力の限界、過平滑化のメカニズムと根本的な対策、およびGNNが学習するグラフ構造情報の解明。
  • 応用分野の拡大: 科学計算 (分子動力学)、推薦システム、医療 (薬剤発見)、自然言語処理 (知識グラフ推論)、コンピュータビジョン (点群処理) など、多様な領域でのGNNの活用。
  • 説明可能性 (Explainability): GNNの予測がどのノードやエッジに起因するのかを説明する手法の開発。
ライセンス：本記事のテキスト/コードは特記なき限り CC BY 4.0 です。引用の際は出典URL（本ページ）を明記してください。
利用ポリシー もご参照ください。

コメント

タイトルとURLをコピーしました