はじめに — なぜGNNの「表現力」を議論する必要があるのか
グラフニューラルネットワーク（GNN）は、ノード分類やリンク予測、グラフ分類など多くのタスクで成功を収めてきました。GCN（Graph Convolutional Network）やGraphSAGEといったモデルが次々と提案され、実用的な性能を示しています。
しかし、ここでひとつ根本的な疑問が生じます。「GNNはどこまで異なるグラフ構造を見分けられるのか？」 という問いです。
たとえば、次の2つのグラフを考えてみてください。
- グラフA: 6つのノードが六角形状に並んだ環（6-cycle）
- グラフB: 3つのノードの三角形が2つ、辺を共有せずに並んだグラフ（2つの3-cycle）
これら2つのグラフはノード数が同じ6で、すべてのノードの次数が2です。もしGNNが「各ノードの近傍の集約」しか行わないなら、すべてのノードが同じ表現を持ってしまい、この2つのグラフを区別できない可能性があります。
この「GNNの識別限界」を理論的に明らかにしたのが、Xu et al. (2019) による GIN（Graph Isomorphism Network） の論文です。彼らはグラフ理論における古典的なアルゴリズム——Weisfeiler-Leman（WL）テスト——とGNNの表現力の関係を厳密に証明し、WLテストと同等の識別能力を持つGNNアーキテクチャとしてGINを提案しました。
この記事では、以下の内容を扱います。
- WLテストとは何か、そしてグラフ同型判定における役割
- GNNの表現力がWLテストで上限づけられる理由
- GINがその上限に到達するための設計原理
- PyTorchによるGINのスクラッチ実装と実験
グラフ分類やグラフ表現学習に関心のある方、GNNの理論的基盤を理解したい方にとって、GINは避けて通れない重要なトピックです。
前提知識
この記事を読むにあたって、以下の知識があるとスムーズです。
- グラフの基本概念: ノード、エッジ、隣接行列、次数
- GNNの基礎: メッセージパッシングの枠組み（GCNやGraphSAGEレベル）
- 多層パーセプトロン（MLP）: 全結合層の基本
- PyTorchの基礎: Tensor操作、
nn.Moduleの定義
グラフ同型問題とは
GINの理論を理解するために、まず グラフ同型問題（Graph Isomorphism Problem） を整理しましょう。
グラフ同型の定義
2つのグラフ $G_1 = (V_1, E_1)$ と $G_2 = (V_2, E_2)$ が 同型（isomorphic） であるとは、全単射 $f: V_1 \to V_2$ が存在して、任意のノード $u, v \in V_1$ に対して
$$ (u, v) \in E_1 \iff (f(u), f(v)) \in E_2 $$
が成り立つことを意味します。直感的には、ノードのラベルを付け替えるだけで一方のグラフを他方に変換できるということです。グラフ同型判定は「2つのグラフが本質的に同じ構造を持つかどうか」を判定する問題です。
この問題は計算量理論において興味深い位置にあります。NPに属することはわかっていますが、P問題なのかNP完全なのかは未解決です。つまり、一般のグラフに対して効率的に同型判定を行うアルゴリズムは見つかっていません。
なぜGNNにとって重要か
GNNの目的のひとつは、グラフに対して有用な 表現ベクトル（graph embedding） を生成することです。理想的には、構造が異なるグラフには異なる表現を割り当て、同型なグラフには同じ表現を割り当てたいと考えます。
つまり、GNNが異なるグラフ構造をどこまで区別できるかは、GNNの「表現力」の指標として直接的に重要なのです。そしてこの識別能力の上限を与えるのが、次に説明するWLテストです。
Weisfeiler-Leman（WL）テスト
Weisfeiler-Leman テスト（1-WL テスト、またはカラーリファインメントとも呼ばれる）は、グラフ同型判定のための古典的なヒューリスティックアルゴリズムです。多項式時間で動作し、多くの実用的なグラフペアに対して同型・非同型を正しく判定できます。
WLテストのアルゴリズム
WLテストは以下のように動作します。
ステップ1: 初期ラベリング
すべてのノードに初期ラベル（色）$c^{(0)}(v)$ を割り当てます。ノード特徴量がある場合はそれを使い、ない場合はすべて同じラベル（例えば1）を割り当てます。
ステップ2: ラベル更新（反復）
各反復 $t$ において、すべてのノード $v$ のラベルを次のルールで更新します。
$$ c^{(t+1)}(v) = \text{HASH}\left(c^{(t)}(v),\, \{\!\!\{ c^{(t)}(u) : u \in \mathcal{N}(v) \}\!\!\}\right) $$
ここで $\{\!\!\{ \cdot \}\!\!\}$ は 多重集合（multiset） を表し、$\text{HASH}$ は入力が同じなら同じ値を、異なるなら異なる値を返す完全ハッシュ関数です。
重要なのは多重集合を使う点です。近傍のラベルを集合（重複を無視）ではなく多重集合（重複を保持）として扱います。たとえば、近傍に「赤が2つ、青が1つ」あるノードと「赤が1つ、青が2つ」あるノードは区別されます。
ステップ3: 収束判定
ラベルの分布（各色のノード数）が変化しなくなったら収束とみなします。最終的に、2つのグラフのラベル分布（色のヒストグラム）が異なれば「非同型」と判定します。一致すれば「判定不能（同型かもしれないし、そうでないかもしれない）」となります。
WLテストの具体例
3ノードの三角形グラフ（パス $A – B – C$ に加えて $A – C$ のエッジがある）と、3ノードのパスグラフ（$A – B – C$のみ）を考えます。
初期状態（ラベルなし、全ノード同じ色1）: – 三角形: $c^{(0)} = \{1, 1, 1\}$、各ノードの次数は2 – パス: $c^{(0)} = \{1, 1, 1\}$、端点の次数は1、中央の次数は2
1回目の更新: – 三角形: すべてのノードの近傍多重集合は $\{\!\!\{1, 1\}\!\!\}$ → 全ノードが同じ新ラベルを得る – パス: 端点の近傍多重集合は $\{\!\!\{1\}\!\!\}$、中央の近傍多重集合は $\{\!\!\{1, 1\}\!\!\}$ → 2種類のラベルが生じる
1回目の更新で、三角形は「色が1種類」、パスは「色が2種類」となり、ラベル分布が異なるため 非同型 と判定できます。
WLテストの限界
WLテストは万能ではありません。区別できないグラフペアの代表例として、正則グラフがあります。たとえば、先ほど述べた6-cycleと2つの3-cycleの例では、すべてのノードの次数が2であるため、WLテストでは何回反復しても同じラベル分布を生成してしまい、区別できません。
しかし実用上は、ほとんどのグラフペアをWLテストで正しく判定できることが知られており、非常に強力なベースラインです。
ここまでWLテストの仕組みを理解したところで、次にこのWLテストとGNNの表現力がどう結びつくかを見ていきましょう。
GNNの表現力とWLテストの関係
メッセージパッシングGNNの一般形
まず、GCNやGraphSAGEなどの一般的なGNNを統一的な枠組みで記述します。メッセージパッシング型GNNの $k$ 層目の更新は以下のように書けます。
$$ h_v^{(k)} = \text{COMBINE}^{(k)}\left(h_v^{(k-1)},\, \text{AGGREGATE}^{(k)}\left(\{\!\!\{ h_u^{(k-1)} : u \in \mathcal{N}(v) \}\!\!\}\right)\right) $$
ここで $h_v^{(k)}$ はノード $v$ の $k$ 層目の特徴ベクトル、$\text{AGGREGATE}$ は近傍の特徴量を集約する関数、$\text{COMBINE}$ は自身の特徴量と集約結果を統合する関数です。
WLテストとの構造的類似性
WLテストの更新式と比較してみましょう。
$$ c^{(t+1)}(v) = \text{HASH}\left(c^{(t)}(v),\, \{\!\!\{ c^{(t)}(u) : u \in \mathcal{N}(v) \}\!\!\}\right) $$
構造が驚くほど似ていることがわかります。WLテストのHASH関数がGNNのCOMBINE + AGGREGATEに対応しているのです。
定理: GNNの表現力の上限
Xu et al. (2019) は以下の定理を証明しました。
定理（GNNの上限）: メッセージパッシング型GNNが2つのグラフを区別できるならば、WLテストもそれらを区別できる。
対偶を取ると、WLテストが区別できない2つのグラフは、いかなるメッセージパッシング型GNNでも区別できないということです。
直感的な理由を説明します。WLテストのHASH関数は 単射（injective） です。つまり、異なる入力には必ず異なる出力を返します。一方、GNNのAGGREGATE関数（例えばmean、max、sum）は一般には単射ではありません。
たとえば、mean集約の場合:
$$ \text{MEAN}(\{\!\!\{1, 1, 1\}\!\!\}) = 1 = \text{MEAN}(\{\!\!\{1\}\!\!\}) $$
異なる多重集合に対して同じ出力を返してしまいます。max集約でも同様の問題が生じます。
$$ \text{MAX}(\{\!\!\{1, 2, 3\}\!\!\}) = 3 = \text{MAX}(\{\!\!\{3, 3, 3\}\!\!\}) $$
このように、一般的なGNNの集約関数はWLテストのHASH関数ほど情報を保持できないため、GNNの識別能力はWLテスト以下となるのです。
具体的な問題例
mean集約とmax集約がそれぞれ失敗するケースを図示的に説明します。
mean集約の失敗例: ノード $v$ の近傍が $\{\!\!\{1, 1, 1\}\!\!\}$ の場合と $\{\!\!\{1\}\!\!\}$ の場合、平均はどちらも1です。つまりmean集約では近傍の「個数」の情報が失われます。
max集約の失敗例: ノード $v$ の近傍が $\{\!\!\{1, 2, 3\}\!\!\}$ の場合と $\{\!\!\{3, 3, 3\}\!\!\}$ の場合、最大値はどちらも3です。つまりmax集約では近傍の「分布」の情報が失われます。
sum集約: 一方、sum（合計）集約はどうでしょうか。$\text{SUM}(\{\!\!\{1, 1, 1\}\!\!\}) = 3 \neq 1 = \text{SUM}(\{\!\!\{1\}\!\!\})$ であり、$\text{SUM}(\{\!\!\{1, 2, 3\}\!\!\}) = 6 \neq 9 = \text{SUM}(\{\!\!\{3, 3, 3\}\!\!\})$ です。sum集約は近傍の個数と分布の両方の情報をある程度保持します。
この観察が、GINの設計の核心につながります。次のセクションで、WLテストと同等の表現力を達成するためのGINの設計原理を詳しく見ていきましょう。
GINの理論 — WLテストと同等の表現力を達成する
多重集合関数の単射性
GNNがWLテストと同等の表現力を持つための必要十分条件は、以下の2つです。
- AGGREGATE関数が多重集合に対して単射であること: 異なる近傍の多重集合を異なるベクトルに写す
- COMBINE関数が単射であること: 自身の特徴量と集約結果の組み合わせが異なれば、異なる出力を返す
つまり、GNNの各層の更新関数全体が単射であれば、WLテストのHASH関数と同じ識別能力を持つことになります。
多重集合に対する単射関数の構成
では、多重集合に対する単射関数をどう構成すればよいでしょうか。Xu et al. は以下の定理を示しました。
定理: 可算な集合 $\mathcal{X}$ 上の多重集合 $X \in \mathcal{X}^*$ に対して、関数 $f: \mathcal{X}^* \to \mathbb{R}^n$ が単射であるための十分条件は、以下の形で表現できることです。
$$ f(X) = \phi\left(\sum_{x \in X} g(x)\right) $$
ここで $\phi$ と $g$ は適切な非線形関数です。
直感的に言えば、各要素を非線形変換 $g$ で写してから合計（sum）し、その結果をさらに非線形変換 $\phi$ で写すことで、多重集合に対する単射関数を実現できるということです。
なぜsumなのかを理解するために、多重集合の情報を考えましょう。多重集合は「どの要素が何個あるか」という情報を持っています。$g$ が単射であれば、各要素が異なるベクトルに写されます。それらのsumを取ると、要素の種類と個数の情報が合計値に反映されます。一方、meanやmaxではこの情報が潰れてしまうのです。
そして $\phi$ と $g$ としてMLPを用いれば、万能近似定理により十分な表現力を得られます。
GINの更新式
以上の理論に基づき、GINの更新式は次のように定義されます。
$$ h_v^{(k)} = \text{MLP}^{(k)}\left((1 + \epsilon^{(k)}) \cdot h_v^{(k-1)} + \sum_{u \in \mathcal{N}(v)} h_u^{(k-1)}\right) $$
ここで: – $\epsilon^{(k)}$ は学習可能なパラメータ（またはハイパーパラメータ）で、自身の特徴量と近傍の特徴量の相対的な重みを調整します – $\text{MLP}^{(k)}$ は各層ごとの多層パーセプトロンです – 集約はsumを使います
この式を分解して理解しましょう。
まず、$(1 + \epsilon^{(k)}) \cdot h_v^{(k-1)}$ の部分は、ノード $v$ 自身の特徴量です。$\epsilon$ を導入することで、「自身のノード」と「近傍のノード」を異なる重みで扱えるようになります。$\epsilon = 0$ なら自身と近傍を等しく扱い、$\epsilon > 0$ なら自身をより重視します。
次に、$\sum_{u \in \mathcal{N}(v)} h_u^{(k-1)}$ は近傍の特徴量のsumです。meanやmaxではなくsumを使うことが表現力の鍵です。
最後に、全体をMLPに通します。MLPが $\phi \circ g$ の役割を果たし、多重集合に対する単射性を実現します。ここで重要なのは、MLPが単なる線形変換ではなく非線形活性化を含む多層ネットワークであることです。線形関数だけでは単射性が保証されません。
なぜ $\epsilon$ が必要か
$\epsilon$ なしの更新式、つまり単純に自身と近傍のsumを取る場合を考えます。
$$ h_v^{(k)} = \text{MLP}^{(k)}\left(h_v^{(k-1)} + \sum_{u \in \mathcal{N}(v)} h_u^{(k-1)}\right) $$
この場合、自身のノードの特徴量 $h_v$ は近傍の合計の中に「1回分」として埋もれてしまいます。自身の特徴量と近傍の合計を区別するためには、$(1 + \epsilon)$ という係数で自身を「拡大」する必要があります。
たとえば、ノード $v$ の特徴量が $h_v = 2$ で近傍の合計が $\sum h_u = 3$ の場合と、$h_v = 3$ で $\sum h_u = 2$ の場合を考えます。$\epsilon = 0$ ではどちらも $2 + 3 = 5$ となり区別できません。$\epsilon \neq 0$ なら $(1+\epsilon) \cdot 2 + 3 \neq (1+\epsilon) \cdot 3 + 2$ となり（$\epsilon \neq 0$ のとき）、区別が可能になります。
グラフレベルのREADOUT
ノードレベルの表現からグラフレベルの表現を得るために、GINでは 全層のノード表現を活用 します。
$$ h_G = \text{CONCAT}\left(\text{READOUT}\left(\{\!\!\{ h_v^{(k)} : v \in G \}\!\!\}\right) \mid k = 0, 1, \ldots, K\right) $$
ここで $\text{READOUT}$ は集合関数（典型的にはsumまたはmean）です。
全層の表現を連結する理由は、各層が異なるスケールの構造情報を捉えているためです。第1層は直接の近傍、第2層は2ホップ先の情報を含み、第 $K$ 層は $K$ ホップ先の情報を含みます。これらをすべて活用することで、グラフの多スケールな構造を表現できます。
ここまでGINの理論的な基盤を理解したところで、次にPyTorchでGINを実装してみましょう。
GINのPyTorch実装
GIN層の実装
まず、GINの1層分を実装します。
import torch
import torch.nn as nn
import torch.nn.functional as F
import numpy as np
import matplotlib.pyplot as plt
class GINLayer(nn.Module):
"""GIN (Graph Isomorphism Network) の1層"""
def __init__(self, in_dim, out_dim, epsilon_learnable=True):
super().__init__()
# MLP: 2層の全結合ネットワーク（非線形活性化あり）
self.mlp = nn.Sequential(
nn.Linear(in_dim, out_dim),
nn.BatchNorm1d(out_dim),
nn.ReLU(),
nn.Linear(out_dim, out_dim),
nn.BatchNorm1d(out_dim),
nn.ReLU()
)
# epsilonの設定
if epsilon_learnable:
self.epsilon = nn.Parameter(torch.zeros(1))
else:
self.register_buffer('epsilon', torch.zeros(1))
def forward(self, x, adj):
"""
x: ノード特徴量 (num_nodes, in_dim)
adj: 隣接行列 (num_nodes, num_nodes)
"""
# 近傍の特徴量をsumで集約
neighbor_sum = torch.matmul(adj, x)
# (1 + epsilon) * 自身 + 近傍のsum
out = (1 + self.epsilon) * x + neighbor_sum
# MLPを適用
out = self.mlp(out)
return out
このコードでは、GINの更新式 $h_v^{(k)} = \text{MLP}^{(k)}((1 + \epsilon^{(k)}) \cdot h_v^{(k-1)} + \sum_{u \in \mathcal{N}(v)} h_u^{(k-1)})$ を忠実に実装しています。torch.matmul(adj, x) は隣接行列と特徴量の積で、各ノードの近傍特徴量のsumを計算します。MLPには2層の全結合にBatchNormとReLUを挟んでおり、これが多重集合に対する単射関数の近似として機能します。
GINモデル全体の実装
class GIN(nn.Module):
"""GINモデル（グラフ分類用）"""
def __init__(self, in_dim, hidden_dim, out_dim, num_layers=3, dropout=0.5):
super().__init__()
self.num_layers = num_layers
self.dropout = dropout
# GIN層のリスト
self.gin_layers = nn.ModuleList()
self.gin_layers.append(GINLayer(in_dim, hidden_dim))
for _ in range(num_layers - 1):
self.gin_layers.append(GINLayer(hidden_dim, hidden_dim))
# 各層の出力をグラフ表現に変換する線形層
self.linear_predictions = nn.ModuleList()
self.linear_predictions.append(nn.Linear(in_dim, out_dim))
for _ in range(num_layers):
self.linear_predictions.append(nn.Linear(hidden_dim, out_dim))
def forward(self, x, adj, graph_indicator):
"""
x: ノード特徴量 (total_nodes, in_dim)
adj: 隣接行列 (total_nodes, total_nodes)
graph_indicator: 各ノードが属するグラフのインデックス (total_nodes,)
"""
hidden_states = [x]
# GIN層を順に適用
h = x
for layer in self.gin_layers:
h = layer(h, adj)
h = F.dropout(h, p=self.dropout, training=self.training)
hidden_states.append(h)
# 各層のグラフレベル表現を計算（sumプーリング）
graph_representations = []
num_graphs = graph_indicator.max().item() + 1
for k, h_k in enumerate(hidden_states):
# 各グラフごとにノード表現をsumで集約
graph_rep = torch.zeros(num_graphs, h_k.size(1), device=h_k.device)
graph_rep.scatter_add_(0, graph_indicator.unsqueeze(1).expand_as(h_k), h_k)
# 線形変換
graph_rep = self.linear_predictions[k](graph_rep)
graph_representations.append(graph_rep)
# 全層の表現を合計（論文ではCONCATも可）
final_rep = sum(graph_representations)
return final_rep
このモデルでは、GINの全体アーキテクチャを実装しています。注目すべきは hidden_states リストです。入力層を含む各層の出力をすべて保存し、最終的にグラフレベルの表現として活用します。graph_indicator は各ノードがどのグラフに属するかを示すインデックスで、バッチ処理時に複数のグラフを1つの大きなグラフとして扱うための仕組みです。scatter_add_ によって、同じグラフに属するノードの表現がsumで集約されます。
WLテストのPython実装（比較用）
GINの挙動をWLテストと比較するために、WLテストもPythonで実装します。
from collections import Counter
def wl_test(adj_list_1, adj_list_2, num_iterations=3):
"""
WLテストによるグラフ同型判定
adj_list: 隣接リスト（辞書形式 {node: [neighbors]}）
戻り値: (判定結果, 各反復のラベル履歴)
"""
# 初期ラベル: すべてのノードに同じラベル1を割り当て
labels_1 = {v: '1' for v in adj_list_1}
labels_2 = {v: '1' for v in adj_list_2}
history = []
for t in range(num_iterations):
# グラフ1のラベル更新
new_labels_1 = {}
for v in adj_list_1:
# 近傍のラベルを多重集合として収集（ソートして文字列化）
neighbor_labels = sorted([labels_1[u] for u in adj_list_1[v]])
# 自身のラベルと近傍ラベルを組み合わせてハッシュ
new_labels_1[v] = f"({labels_1[v]},{','.join(neighbor_labels)})"
# グラフ2のラベル更新
new_labels_2 = {}
for v in adj_list_2:
neighbor_labels = sorted([labels_2[u] for u in adj_list_2[v]])
new_labels_2[v] = f"({labels_2[v]},{','.join(neighbor_labels)})"
labels_1 = new_labels_1
labels_2 = new_labels_2
# ラベル分布の比較
hist_1 = Counter(labels_1.values())
hist_2 = Counter(labels_2.values())
history.append({
'iteration': t + 1,
'graph1_hist': dict(hist_1),
'graph2_hist': dict(hist_2),
'distinguishable': hist_1 != hist_2
})
if hist_1 != hist_2:
return True, history # 非同型と判定
return False, history # 判定不能
# テスト: 三角形グラフ vs パスグラフ
triangle = {0: [1, 2], 1: [0, 2], 2: [0, 1]}
path = {0: [1], 1: [0, 2], 2: [1]}
is_different, history = wl_test(triangle, path, num_iterations=3)
print("=== WLテスト: 三角形 vs パスグラフ ===")
for record in history:
print(f"反復 {record['iteration']}:")
print(f" グラフ1のラベル分布: {record['graph1_hist']}")
print(f" グラフ2のラベル分布: {record['graph2_hist']}")
print(f" 区別可能: {record['distinguishable']}")
print(f"\n最終判定: {'非同型' if is_different else '判定不能'}")
実行結果を確認すると、1回目の反復で三角形グラフとパスグラフのラベル分布が異なることがわかります。三角形ではすべてのノードが同じラベル (1,1,1) を持ちますが、パスでは端点が (1,1) 、中央のノードが (1,1,1) と異なるラベルになります。このようにWLテストは構造の違いをラベル分布の違いとして検出します。
次に、GINとGCN（mean集約）の識別能力を実験的に比較してみましょう。
集約関数の比較実験
sum・mean・maxの識別能力の比較
異なる集約関数がどの程度多重集合を区別できるかを、実験的に検証します。
import torch
import numpy as np
import matplotlib.pyplot as plt
def generate_multisets(num_samples=1000, max_size=5, max_value=3):
"""ランダムな多重集合を生成"""
multisets = []
for _ in range(num_samples):
size = np.random.randint(1, max_size + 1)
ms = np.random.randint(0, max_value + 1, size=size)
multisets.append(tuple(sorted(ms)))
return multisets
def count_collisions(multisets, aggregation='sum'):
"""集約関数による衝突（異なる多重集合が同じ値に写される）の数を計算"""
# ユニークな多重集合を抽出
unique_multisets = list(set(multisets))
agg_values = {}
for ms in unique_multisets:
arr = np.array(ms, dtype=np.float32)
if aggregation == 'sum':
val = tuple(np.round(np.array([arr.sum()]), 4))
elif aggregation == 'mean':
val = tuple(np.round(np.array([arr.mean()]), 4))
elif aggregation == 'max':
val = tuple(np.round(np.array([arr.max()]), 4))
else:
raise ValueError(f"Unknown aggregation: {aggregation}")
if val not in agg_values:
agg_values[val] = []
agg_values[val].append(ms)
# 衝突: 2つ以上の多重集合が同じ値に写されるケース
collisions = sum(len(v) - 1 for v in agg_values.values() if len(v) > 1)
total_unique = len(unique_multisets)
distinct_outputs = len(agg_values)
return collisions, total_unique, distinct_outputs
# 実験
np.random.seed(42)
multisets = generate_multisets(num_samples=5000, max_size=6, max_value=4)
results = {}
for agg in ['sum', 'mean', 'max']:
collisions, total, distinct = count_collisions(multisets, agg)
results[agg] = {
'collisions': collisions,
'total_unique': total,
'distinct_outputs': distinct,
'collision_rate': collisions / total * 100
}
print(f"{agg:>4s}: ユニーク多重集合 {total}, 区別可能な出力 {distinct}, "
f"衝突 {collisions} ({collisions/total*100:.1f}%)")
# 可視化
fig, ax = plt.subplots(1, 1, figsize=(8, 5))
aggs = ['sum', 'mean', 'max']
collision_rates = [results[a]['collision_rate'] for a in aggs]
colors = ['#2ecc71', '#e74c3c', '#e74c3c']
bars = ax.bar(aggs, collision_rates, color=colors, edgecolor='black', linewidth=0.8)
ax.set_ylabel('Collision Rate (%)', fontsize=12)
ax.set_title('Aggregation Function Collision Rates on Multisets', fontsize=14)
ax.set_ylim(0, max(collision_rates) * 1.3)
for bar, rate in zip(bars, collision_rates):
ax.text(bar.get_x() + bar.get_width() / 2, bar.get_height() + 0.5,
f'{rate:.1f}%', ha='center', fontsize=11, fontweight='bold')
plt.tight_layout()
plt.savefig('aggregation_collision_comparison.png', dpi=150, bbox_inches='tight')
plt.show()
この実験では、ランダムに生成した5000個の多重集合に対して、sum・mean・maxの各集約関数がどの程度の衝突（collision）を起こすかを測定しています。衝突率が低いほど、その集約関数が多重集合をよく区別できることを意味します。結果として、sum集約は衝突率が最も低く、mean集約やmax集約は多くの衝突を起こすことが確認できます。これはGINがsum集約を採用する理論的根拠の実験的裏付けです。
GIN vs GCN（mean）のグラフ識別実験
次に、GINとGCN（mean集約）のグラフ識別能力を比較します。
import torch
import torch.nn as nn
import torch.nn.functional as F
import numpy as np
import matplotlib.pyplot as plt
class SimpleGINLayer(nn.Module):
"""簡易版GIN層"""
def __init__(self, in_dim, out_dim):
super().__init__()
self.mlp = nn.Sequential(
nn.Linear(in_dim, out_dim),
nn.ReLU(),
nn.Linear(out_dim, out_dim)
)
self.epsilon = nn.Parameter(torch.zeros(1))
def forward(self, x, adj):
neighbor_sum = torch.matmul(adj, x)
out = (1 + self.epsilon) * x + neighbor_sum
return self.mlp(out)
class SimpleMeanGNNLayer(nn.Module):
"""Mean集約のGNN層（GCN相当）"""
def __init__(self, in_dim, out_dim):
super().__init__()
self.linear = nn.Linear(in_dim, out_dim)
def forward(self, x, adj):
# 次数で正規化（mean集約）
degree = adj.sum(dim=1, keepdim=True).clamp(min=1)
neighbor_mean = torch.matmul(adj, x) / degree
out = x + neighbor_mean
return F.relu(self.linear(out))
def create_graph_pair_1():
"""
区別すべきグラフペア1: 星グラフ vs 完全二部グラフ
星グラフ: 中心1ノード + 葉4ノード
完全二部グラフ: K_{2,3}
"""
# 星グラフ (5ノード: 0が中心)
adj1 = torch.zeros(5, 5)
for i in range(1, 5):
adj1[0, i] = 1
adj1[i, 0] = 1
# パスグラフ (5ノード: 0-1-2-3-4)
adj2 = torch.zeros(5, 5)
for i in range(4):
adj2[i, i+1] = 1
adj2[i+1, i] = 1
x = torch.ones(5, 1) # 特徴量なし（すべて1）
return x, adj1, adj2, "Star vs Path"
def create_graph_pair_2():
"""
区別すべきグラフペア2: 三角形+孤立ノード vs 4ノードパス
"""
# 三角形(0,1,2) + 孤立ノード(3)
adj1 = torch.zeros(4, 4)
adj1[0, 1] = adj1[1, 0] = 1
adj1[1, 2] = adj1[2, 1] = 1
adj1[0, 2] = adj1[2, 0] = 1
# 4ノードパス: 0-1-2-3
adj2 = torch.zeros(4, 4)
adj2[0, 1] = adj2[1, 0] = 1
adj2[1, 2] = adj2[2, 1] = 1
adj2[2, 3] = adj2[3, 2] = 1
x = torch.ones(4, 1)
return x, adj1, adj2, "Triangle+Isolated vs 4-Path"
def get_graph_embedding(model_layers, x, adj):
"""グラフ全体の埋め込みを計算（全層のsumを連結）"""
h = x
embeddings = [h.sum(dim=0)]
for layer in model_layers:
h = layer(h, adj)
embeddings.append(h.sum(dim=0))
return torch.cat(embeddings)
# 実験: 複数の初期化で識別能力を比較
torch.manual_seed(42)
num_trials = 50
hidden_dim = 16
num_layers = 3
gin_distances = {'pair1': [], 'pair2': []}
mean_distances = {'pair1': [], 'pair2': []}
for trial in range(num_trials):
# GIN
gin_layers = nn.ModuleList([SimpleGINLayer(1 if i == 0 else hidden_dim, hidden_dim)
for i in range(num_layers)])
# Mean GNN
mean_layers = nn.ModuleList([SimpleMeanGNNLayer(1 if i == 0 else hidden_dim, hidden_dim)
for i in range(num_layers)])
for pair_name, create_fn in [('pair1', create_graph_pair_1), ('pair2', create_graph_pair_2)]:
x, adj1, adj2, _ = create_fn()
with torch.no_grad():
# GINの埋め込み距離
emb1_gin = get_graph_embedding(gin_layers, x, adj1)
emb2_gin = get_graph_embedding(gin_layers, x, adj2)
dist_gin = torch.norm(emb1_gin - emb2_gin).item()
gin_distances[pair_name].append(dist_gin)
# Mean GNNの埋め込み距離
emb1_mean = get_graph_embedding(mean_layers, x, adj1)
emb2_mean = get_graph_embedding(mean_layers, x, adj2)
dist_mean = torch.norm(emb1_mean - emb2_mean).item()
mean_distances[pair_name].append(dist_mean)
# 結果の可視化
fig, axes = plt.subplots(1, 2, figsize=(14, 5))
for idx, pair_name in enumerate(['pair1', 'pair2']):
ax = axes[idx]
title = "Star vs Path" if pair_name == 'pair1' else "Triangle+Isolated vs 4-Path"
data = [gin_distances[pair_name], mean_distances[pair_name]]
bp = ax.boxplot(data, labels=['GIN (sum)', 'Mean GNN'], patch_artist=True,
boxprops=dict(linewidth=1.5),
medianprops=dict(color='black', linewidth=2))
bp['boxes'][0].set_facecolor('#2ecc71')
bp['boxes'][1].set_facecolor('#3498db')
ax.set_ylabel('Embedding Distance', fontsize=12)
ax.set_title(f'Graph Pair: {title}', fontsize=13)
ax.axhline(y=0, color='red', linestyle='--', alpha=0.7, label='No distinction')
ax.legend(fontsize=10)
plt.suptitle('GIN vs Mean GNN: Graph Distinguishing Ability', fontsize=15, y=1.02)
plt.tight_layout()
plt.savefig('gin_vs_mean_gnn_comparison.png', dpi=150, bbox_inches='tight')
plt.show()
# 統計量の表示
for pair_name in ['pair1', 'pair2']:
print(f"\n=== {pair_name} ===")
gin_arr = np.array(gin_distances[pair_name])
mean_arr = np.array(mean_distances[pair_name])
print(f"GIN - 平均距離: {gin_arr.mean():.4f}, 距離>0の割合: {(gin_arr > 1e-6).mean()*100:.1f}%")
print(f"Mean - 平均距離: {mean_arr.mean():.4f}, 距離>0の割合: {(mean_arr > 1e-6).mean()*100:.1f}%")
この実験では、2組のグラフペアに対してGIN（sum集約）とMean GNN（mean集約）の埋め込み距離を50回の異なる初期化で測定しています。GINは一貫してグラフペアに対して非ゼロの距離を生成する傾向がある一方、Mean GNNは特に構造が似たグラフペアに対して距離がゼロに近くなりやすいことが確認できます。これは理論の予測と一致する結果です。
グラフ分類タスクでのGIN実験
実際のグラフ分類タスクでGINの性能を確認しましょう。ここでは合成データセットを用いて実験します。
import torch
import torch.nn as nn
import torch.nn.functional as F
import numpy as np
import matplotlib.pyplot as plt
from collections import defaultdict
# 合成グラフデータセットの生成
def generate_graph_classification_dataset(num_graphs=500, seed=42):
"""
3クラスのグラフ分類データセットを生成
クラス0: サイクルグラフ（環状構造）
クラス1: 星グラフ（中心ノード構造）
クラス2: ランダムグラフ（Erdos-Renyi）
"""
np.random.seed(seed)
graphs = []
for _ in range(num_graphs // 3):
# クラス0: サイクルグラフ
n = np.random.randint(5, 12)
adj = np.zeros((n, n))
for i in range(n):
adj[i, (i+1) % n] = 1
adj[(i+1) % n, i] = 1
feat = np.ones((n, 1))
graphs.append((adj, feat, 0))
# クラス1: 星グラフ
n = np.random.randint(5, 12)
adj = np.zeros((n, n))
for i in range(1, n):
adj[0, i] = 1
adj[i, 0] = 1
feat = np.ones((n, 1))
graphs.append((adj, feat, 1))
# クラス2: ランダムグラフ
n = np.random.randint(5, 12)
adj = np.zeros((n, n))
p = 0.3
for i in range(n):
for j in range(i+1, n):
if np.random.random() < p:
adj[i, j] = 1
adj[j, i] = 1
feat = np.ones((n, 1))
graphs.append((adj, feat, 2))
np.random.shuffle(graphs)
return graphs
# バッチ処理用のユーティリティ
def collate_graphs(graph_list):
"""複数のグラフを1つのバッチにまとめる"""
adjs = []
feats = []
labels = []
graph_indicators = []
offset = 0
for i, (adj, feat, label) in enumerate(graph_list):
n = adj.shape[0]
adjs.append((adj, offset))
feats.append(feat)
labels.append(label)
graph_indicators.extend([i] * n)
offset += n
# ブロック対角の隣接行列を構築
total_nodes = offset
batch_adj = np.zeros((total_nodes, total_nodes))
for adj, off in adjs:
n = adj.shape[0]
batch_adj[off:off+n, off:off+n] = adj
batch_feat = np.concatenate(feats, axis=0)
return (torch.FloatTensor(batch_adj),
torch.FloatTensor(batch_feat),
torch.LongTensor(labels),
torch.LongTensor(graph_indicators))
# GINモデル（グラフ分類用）
class GINClassifier(nn.Module):
def __init__(self, in_dim, hidden_dim, num_classes, num_layers=3):
super().__init__()
self.num_layers = num_layers
self.gin_layers = nn.ModuleList()
self.batch_norms = nn.ModuleList()
self.gin_layers.append(self._make_gin_layer(in_dim, hidden_dim))
self.batch_norms.append(nn.BatchNorm1d(hidden_dim))
for _ in range(num_layers - 1):
self.gin_layers.append(self._make_gin_layer(hidden_dim, hidden_dim))
self.batch_norms.append(nn.BatchNorm1d(hidden_dim))
# 各層からの予測ヘッド
self.linears = nn.ModuleList()
self.linears.append(nn.Linear(in_dim, num_classes))
for _ in range(num_layers):
self.linears.append(nn.Linear(hidden_dim, num_classes))
def _make_gin_layer(self, in_dim, out_dim):
return nn.Sequential(
nn.Linear(in_dim, out_dim),
nn.ReLU(),
nn.Linear(out_dim, out_dim)
)
def forward(self, adj, x, graph_indicator):
num_graphs = graph_indicator.max().item() + 1
hidden = x
score_over_layers = 0
# 入力層からのスコア
pooled = torch.zeros(num_graphs, hidden.size(1), device=x.device)
pooled.scatter_add_(0, graph_indicator.unsqueeze(1).expand_as(hidden), hidden)
score_over_layers += self.linears[0](pooled)
for k in range(self.num_layers):
# GIN更新
neighbor_sum = torch.matmul(adj, hidden)
hidden = neighbor_sum + hidden # epsilon=0で簡略化
hidden = self.gin_layers[k](hidden)
hidden = self.batch_norms[k](hidden)
hidden = F.relu(hidden)
# グラフレベルプーリング（sum）
pooled = torch.zeros(num_graphs, hidden.size(1), device=x.device)
pooled.scatter_add_(0, graph_indicator.unsqueeze(1).expand_as(hidden), hidden)
score_over_layers += self.linears[k + 1](pooled)
return score_over_layers
# Mean GNNモデル（比較用）
class MeanGNNClassifier(nn.Module):
def __init__(self, in_dim, hidden_dim, num_classes, num_layers=3):
super().__init__()
self.layers = nn.ModuleList()
self.layers.append(nn.Linear(in_dim, hidden_dim))
for _ in range(num_layers - 1):
self.layers.append(nn.Linear(hidden_dim, hidden_dim))
self.classifier = nn.Linear(hidden_dim, num_classes)
def forward(self, adj, x, graph_indicator):
num_graphs = graph_indicator.max().item() + 1
h = x
for layer in self.layers:
# mean集約
degree = adj.sum(dim=1, keepdim=True).clamp(min=1)
neighbor_mean = torch.matmul(adj, h) / degree
h = F.relu(layer(h + neighbor_mean))
# グラフレベルプーリング（mean）
pooled = torch.zeros(num_graphs, h.size(1), device=x.device)
counts = torch.zeros(num_graphs, 1, device=x.device)
pooled.scatter_add_(0, graph_indicator.unsqueeze(1).expand_as(h), h)
counts.scatter_add_(0, graph_indicator.unsqueeze(1), torch.ones(h.size(0), 1, device=x.device))
pooled = pooled / counts.clamp(min=1)
return self.classifier(pooled)
# 訓練と評価
def train_and_evaluate(model, train_graphs, test_graphs, epochs=100, lr=0.01):
optimizer = torch.optim.Adam(model.parameters(), lr=lr)
train_losses = []
test_accs = []
for epoch in range(epochs):
model.train()
# ミニバッチ（全データ）
adj, x, labels, indicator = collate_graphs(train_graphs)
logits = model(adj, x, indicator)
loss = F.cross_entropy(logits, labels)
optimizer.zero_grad()
loss.backward()
optimizer.step()
train_losses.append(loss.item())
# 評価
if (epoch + 1) % 5 == 0:
model.eval()
with torch.no_grad():
adj_t, x_t, labels_t, indicator_t = collate_graphs(test_graphs)
logits_t = model(adj_t, x_t, indicator_t)
preds = logits_t.argmax(dim=1)
acc = (preds == labels_t).float().mean().item()
test_accs.append((epoch + 1, acc))
return train_losses, test_accs
# 実験実行
torch.manual_seed(42)
dataset = generate_graph_classification_dataset(num_graphs=300, seed=42)
split = int(len(dataset) * 0.8)
train_graphs = dataset[:split]
test_graphs = dataset[split:]
# GIN
gin_model = GINClassifier(in_dim=1, hidden_dim=32, num_classes=3, num_layers=3)
gin_losses, gin_accs = train_and_evaluate(gin_model, train_graphs, test_graphs, epochs=150)
# Mean GNN
mean_model = MeanGNNClassifier(in_dim=1, hidden_dim=32, num_classes=3, num_layers=3)
mean_losses, mean_accs = train_and_evaluate(mean_model, train_graphs, test_graphs, epochs=150)
# 可視化
fig, axes = plt.subplots(1, 2, figsize=(14, 5))
# 訓練損失
axes[0].plot(gin_losses, label='GIN', color='#2ecc71', alpha=0.8)
axes[0].plot(mean_losses, label='Mean GNN', color='#3498db', alpha=0.8)
axes[0].set_xlabel('Epoch', fontsize=12)
axes[0].set_ylabel('Training Loss', fontsize=12)
axes[0].set_title('Training Loss Comparison', fontsize=14)
axes[0].legend(fontsize=11)
axes[0].grid(True, alpha=0.3)
# テスト精度
gin_epochs, gin_acc_vals = zip(*gin_accs)
mean_epochs, mean_acc_vals = zip(*mean_accs)
axes[1].plot(gin_epochs, gin_acc_vals, 'o-', label='GIN', color='#2ecc71', markersize=4)
axes[1].plot(mean_epochs, mean_acc_vals, 's-', label='Mean GNN', color='#3498db', markersize=4)
axes[1].set_xlabel('Epoch', fontsize=12)
axes[1].set_ylabel('Test Accuracy', fontsize=12)
axes[1].set_title('Test Accuracy Comparison', fontsize=14)
axes[1].legend(fontsize=11)
axes[1].set_ylim(0, 1.05)
axes[1].grid(True, alpha=0.3)
plt.suptitle('GIN vs Mean GNN on Graph Classification', fontsize=15, y=1.02)
plt.tight_layout()
plt.savefig('gin_graph_classification_result.png', dpi=150, bbox_inches='tight')
plt.show()
# 最終精度の表示
print(f"\n=== 最終テスト精度 ===")
print(f"GIN: {gin_acc_vals[-1]*100:.1f}%")
print(f"Mean GNN: {mean_acc_vals[-1]*100:.1f}%")
この実験では、3種類のグラフ構造（サイクル・星・ランダム）を分類するタスクでGINとMean GNNを比較しています。特にノード特徴量をすべて1に設定しているため、モデルは純粋にグラフの構造的な違いを学習する必要があります。GINはsum集約と全層の表現を活用することで、構造的な差異をより効果的に捉え、高い分類精度を達成する傾向があります。Mean GNNは次数情報が正規化されて失われるため、特にサイクルグラフと星グラフの区別に苦戦しやすくなります。
GINの理論的位置づけの深掘り
GNNの表現力の階層
ここまでの議論を整理すると、集約関数によるGNNの表現力の階層は次のようになります。
$$ \text{max/mean 集約GNN} \subset \text{sum 集約GNN (GIN)} \leq \text{1-WL テスト} $$
GINは1-WLテストと 同等 の表現力を持つことが証明されています。つまり、メッセージパッシング型GNNの枠組みにおいて、GINは理論的な表現力の 上限 に達しています。
1-WLテストを超えるには
1-WLテストにも限界があります。先述の正則グラフの例のように、WLテストでは区別できないグラフペアが存在します。この限界を超えるためのアプローチとしては、以下のようなものが研究されています。
高階WLテスト（k-WL テスト）: 個々のノードではなく、$k$ 個のノードの組（タプル）に対してラベリングを行います。$k$ が大きいほど表現力は上がりますが、計算量が $O(n^k)$ と爆発的に増加します。
構造的特徴量の追加: ランダムノード特徴量、ノードのポジショナルエンコーディング、サブグラフ構造のカウントなどの追加情報をノード特徴量に組み込むことで、WLテストの限界を間接的に突破できます。
サブグラフGNN: 各ノードを中心とするサブグラフを抽出し、サブグラフレベルでメッセージパッシングを行うアプローチです。
これらはいずれも計算コストとのトレードオフがありますが、GINの理論が「メッセージパッシングの限界」を明確にしたからこそ、それを超える方向性が見えてきたと言えます。
GINの実践的な意義
理論的にはGINがsum集約で最大の表現力を持つと示されましたが、実践ではタスクによってmean集約やmax集約が良い性能を示すこともあります。その理由は以下の通りです。
- mean集約: グラフのサイズに対して不変な表現を生成するため、異なるサイズのグラフを比較するタスクで有利になることがあります
- max集約: ノードの多重集合の中から最も顕著な特徴を抽出するため、ある種のグラフ分類では効果的です
- sum集約（GIN）: 多重集合の完全な情報を保持するが、グラフサイズに依存する表現になるため、正規化が重要です
つまり、GINは「最も情報を保持する」集約ですが、実用上は情報を適切に圧縮する方が汎化性能に寄与する場合もあるのです。これは「表現力」と「汎化性能」が必ずしも一致しないことを示しています。
次のセクションでは、epsilonパラメータの効果をより詳しく実験で確認します。
epsilonパラメータの効果
$\epsilon$ が学習可能な場合と固定（$\epsilon = 0$）の場合の差を実験的に比較します。
import torch
import torch.nn as nn
import torch.nn.functional as F
import numpy as np
import matplotlib.pyplot as plt
class GINWithEpsilon(nn.Module):
"""epsilon学習可能なGIN"""
def __init__(self, in_dim, hidden_dim, num_classes, num_layers=3):
super().__init__()
self.num_layers = num_layers
self.epsilons = nn.ParameterList(
[nn.Parameter(torch.zeros(1)) for _ in range(num_layers)]
)
self.mlps = nn.ModuleList()
self.mlps.append(nn.Sequential(
nn.Linear(in_dim, hidden_dim), nn.ReLU(), nn.Linear(hidden_dim, hidden_dim)
))
for _ in range(num_layers - 1):
self.mlps.append(nn.Sequential(
nn.Linear(hidden_dim, hidden_dim), nn.ReLU(), nn.Linear(hidden_dim, hidden_dim)
))
self.classifier = nn.Linear(hidden_dim, num_classes)
def forward(self, adj, x, graph_indicator):
num_graphs = graph_indicator.max().item() + 1
h = x
for k in range(self.num_layers):
neighbor_sum = torch.matmul(adj, h)
h = (1 + self.epsilons[k]) * h + neighbor_sum
h = self.mlps[k](h)
h = F.relu(h)
# sumプーリング
pooled = torch.zeros(num_graphs, h.size(1), device=x.device)
pooled.scatter_add_(0, graph_indicator.unsqueeze(1).expand_as(h), h)
return self.classifier(pooled)
def get_epsilons(self):
return [eps.item() for eps in self.epsilons]
class GINWithoutEpsilon(nn.Module):
"""epsilon固定（=0）のGIN"""
def __init__(self, in_dim, hidden_dim, num_classes, num_layers=3):
super().__init__()
self.num_layers = num_layers
self.mlps = nn.ModuleList()
self.mlps.append(nn.Sequential(
nn.Linear(in_dim, hidden_dim), nn.ReLU(), nn.Linear(hidden_dim, hidden_dim)
))
for _ in range(num_layers - 1):
self.mlps.append(nn.Sequential(
nn.Linear(hidden_dim, hidden_dim), nn.ReLU(), nn.Linear(hidden_dim, hidden_dim)
))
self.classifier = nn.Linear(hidden_dim, num_classes)
def forward(self, adj, x, graph_indicator):
num_graphs = graph_indicator.max().item() + 1
h = x
for k in range(self.num_layers):
neighbor_sum = torch.matmul(adj, h)
h = h + neighbor_sum # epsilon=0固定
h = self.mlps[k](h)
h = F.relu(h)
pooled = torch.zeros(num_graphs, h.size(1), device=x.device)
pooled.scatter_add_(0, graph_indicator.unsqueeze(1).expand_as(h), h)
return self.classifier(pooled)
# collate_graphs関数は前のセクションと同じ
def collate_graphs(graph_list):
adjs, feats, labels, indicators = [], [], [], []
offset = 0
for i, (adj, feat, label) in enumerate(graph_list):
n = adj.shape[0]
adjs.append((adj, offset))
feats.append(feat)
labels.append(label)
indicators.extend([i] * n)
offset += n
total = offset
batch_adj = np.zeros((total, total))
for adj, off in adjs:
n = adj.shape[0]
batch_adj[off:off+n, off:off+n] = adj
return (torch.FloatTensor(batch_adj), torch.FloatTensor(np.concatenate(feats)),
torch.LongTensor(labels), torch.LongTensor(indicators))
# 前のセクションと同じデータセット生成関数
def generate_graph_dataset(num_graphs=300, seed=42):
np.random.seed(seed)
graphs = []
for _ in range(num_graphs // 3):
# サイクル
n = np.random.randint(5, 12)
adj = np.zeros((n, n))
for i in range(n):
adj[i, (i+1)%n] = 1; adj[(i+1)%n, i] = 1
graphs.append((adj, np.ones((n,1)), 0))
# 星
n = np.random.randint(5, 12)
adj = np.zeros((n, n))
for i in range(1, n):
adj[0,i] = 1; adj[i,0] = 1
graphs.append((adj, np.ones((n,1)), 1))
# ランダム
n = np.random.randint(5, 12)
adj = np.zeros((n, n))
for i in range(n):
for j in range(i+1, n):
if np.random.random() < 0.3:
adj[i,j] = 1; adj[j,i] = 1
graphs.append((adj, np.ones((n,1)), 2))
np.random.shuffle(graphs)
return graphs
# 実験実行
torch.manual_seed(0)
dataset = generate_graph_dataset(300, seed=42)
split = int(len(dataset) * 0.8)
train_data, test_data = dataset[:split], dataset[split:]
# モデル1: epsilon学習可能
model_with_eps = GINWithEpsilon(1, 32, 3, num_layers=4)
opt1 = torch.optim.Adam(model_with_eps.parameters(), lr=0.01)
# モデル2: epsilon固定
model_without_eps = GINWithoutEpsilon(1, 32, 3, num_layers=4)
opt2 = torch.optim.Adam(model_without_eps.parameters(), lr=0.01)
results_with = {'loss': [], 'acc': [], 'eps_history': []}
results_without = {'loss': [], 'acc': []}
for epoch in range(200):
for model, opt, results in [(model_with_eps, opt1, results_with),
(model_without_eps, opt2, results_without)]:
model.train()
adj, x, labels, ind = collate_graphs(train_data)
logits = model(adj, x, ind)
loss = F.cross_entropy(logits, labels)
opt.zero_grad()
loss.backward()
opt.step()
results['loss'].append(loss.item())
if (epoch + 1) % 5 == 0:
for model, results in [(model_with_eps, results_with), (model_without_eps, results_without)]:
model.eval()
with torch.no_grad():
adj_t, x_t, labels_t, ind_t = collate_graphs(test_data)
logits_t = model(adj_t, x_t, ind_t)
acc = (logits_t.argmax(1) == labels_t).float().mean().item()
results['acc'].append((epoch+1, acc))
results_with['eps_history'].append(
(epoch+1, model_with_eps.get_epsilons())
)
# 可視化
fig, axes = plt.subplots(1, 3, figsize=(18, 5))
# 損失
axes[0].plot(results_with['loss'], label='GIN (learnable eps)', alpha=0.7, color='#2ecc71')
axes[0].plot(results_without['loss'], label='GIN (eps=0)', alpha=0.7, color='#e74c3c')
axes[0].set_xlabel('Epoch', fontsize=12)
axes[0].set_ylabel('Training Loss', fontsize=12)
axes[0].set_title('Training Loss', fontsize=14)
axes[0].legend(fontsize=10)
axes[0].grid(True, alpha=0.3)
# テスト精度
eps_e, eps_a = zip(*results_with['acc'])
no_eps_e, no_eps_a = zip(*results_without['acc'])
axes[1].plot(eps_e, eps_a, 'o-', label='GIN (learnable eps)', color='#2ecc71', markersize=3)
axes[1].plot(no_eps_e, no_eps_a, 's-', label='GIN (eps=0)', color='#e74c3c', markersize=3)
axes[1].set_xlabel('Epoch', fontsize=12)
axes[1].set_ylabel('Test Accuracy', fontsize=12)
axes[1].set_title('Test Accuracy', fontsize=14)
axes[1].legend(fontsize=10)
axes[1].set_ylim(0, 1.05)
axes[1].grid(True, alpha=0.3)
# epsilonの推移
eps_epochs = [e for e, _ in results_with['eps_history']]
for layer_idx in range(4):
eps_vals = [eps[layer_idx] for _, eps in results_with['eps_history']]
axes[2].plot(eps_epochs, eps_vals, label=f'Layer {layer_idx+1}', linewidth=2)
axes[2].axhline(y=0, color='gray', linestyle='--', alpha=0.5)
axes[2].set_xlabel('Epoch', fontsize=12)
axes[2].set_ylabel('Epsilon Value', fontsize=12)
axes[2].set_title('Learned Epsilon Values per Layer', fontsize=14)
axes[2].legend(fontsize=10)
axes[2].grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig('gin_epsilon_analysis.png', dpi=150, bbox_inches='tight')
plt.show()
# 最終epsilon値の表示
print("\n=== 学習されたepsilon値 ===")
for k, eps in enumerate(model_with_eps.get_epsilons()):
print(f"Layer {k+1}: epsilon = {eps:.4f}")
print(f"\nテスト精度 (learnable eps): {eps_a[-1]*100:.1f}%")
print(f"テスト精度 (eps=0): {no_eps_a[-1]*100:.1f}%")
この実験では、$\epsilon$ を学習可能にした場合と0に固定した場合のGINを比較しています。右のグラフで各層の $\epsilon$ がどのような値に収束するかを可視化しています。$\epsilon$ が正の値に学習される層は、自身のノードの特徴量を近傍よりも重視していることを示しています。実用上は $\epsilon$ を学習可能にすることで若干の性能向上が得られることが多いですが、その差はタスクやデータセットによって異なります。
まとめ
本記事では、GIN（Graph Isomorphism Network）の理論をWeisfeiler-Leman（WL）テストとの対応関係から詳しく解説しました。
重要なポイント
WLテストとGNNの対応: WLテストのラベル更新ルールとGNNのメッセージパッシングは構造的に類似しており、GNNの表現力の上限はWLテストによって規定されます。
集約関数と表現力: sum集約は多重集合に対してmeanやmaxよりも多くの情報を保持します。具体的には、meanは要素数の情報を失い、maxは分布の情報を失いますが、sumは両方を保持します。
GINの設計原理: GINは「(1+epsilon) * 自身 + 近傍のsum」をMLPに通すことで、WLテストと同等の識別能力を実現します。$\epsilon$ パラメータは自身のノードと近傍ノードの寄与を調整し、MLPの非線形性が単射関数の近似を担保します。
グラフレベル表現: 全層のノード表現を連結してグラフ表現を構成することで、異なるスケールの構造情報を統合的に活用できます。
次のステップ
GINの理論は「メッセージパッシングGNNの表現力の限界」を明確にしました。この限界を理解した上で、さらに発展的なトピックに進むことができます。
