グラフニューラルネットワークの基礎理論と実践

1. グラフの基本理論

従来のアルゴリズム（機械学習、畳み込みニューラルネットワークなど）が主に処理するのはユークリッド空間データ（Euclidean space）です（一般的には画像などのデータを指します）。

ユークリッドデータ：データは整然と並んでいます。あるノードに対して、隣接ノードを見つけるのは簡単で、そのままです。最も一般的なのは画像(image)やビデオ(video)、音声(voice)です。 非ユークリッドデータ：整然と並んでおらず、比較的ランダムです。具体的には：データ中の特定の点に対して、隣接ノードを定義するのが難しい、または異なるノードの隣接ノードの数が異なることがあります。

しかし、非ユークリッド空間データ（家族の系図、人物関係ネットワークなど）は、伝統的なニューラルネットワークではほとんど処理できません（言い換えれば：世界の万物は互いに関連していますが、従来の深層学習や機械学習は単一で単純なデータ問題を処理しています）。そこでグラフニューラルネットワーク（\(Graph \quad Neural \quad Network\)）が提案されました。

グラフを定義します：\(G=(V,E,R,T)\)ここで：

1. ノード：\(v_i \in V\)
2. 異なるノード間の接続：\((v_i, r, v_j)\)
3. ノード間の関連性：\(r \in R\)
4. ノードタイプ：\(T(v_i)\)

簡単に理解すると、「グラフ」はいくつかのノードがいくつかのノード間で互いに関連していること（接続は有向、無向、重み付け、自己ループなどに分けられます）です。

コード例

from torch_geometric.data import Data
import torch
# ノード特徴量（例：身長、体重）
node_features = torch.tensor([[185, 75], [160, 65], [192, 80]], dtype=torch.float)
# エッジインデックス（ノード間の接続）
edges = torch.tensor([
    [0, 0, 1, 1, 2, 2],  # 始点ノード
    [1, 2, 0, 2, 0, 1]   # 終点ノード
])
# ノードラベル
node_labels = torch.tensor([[0, 0], [1, 0], [2, 1]])

# グラフデータオブジェクトの作成
graph_data = Data(x=node_features, edge_index=edges, y=node_labels)

# グラフの基本情報
print(f'ノード数: {graph_data.num_nodes}')
print(f'エッジ数: {int(graph_data.num_edges/2)}')
print(f'ノード特徴量の次元: {graph_data.num_edges / graph_data.num_nodes:.2f}')
print(f'孤立ノードを含む: {graph_data.contains_isolated_nodes()}')
print(f'自己ループを含む: {graph_data.contains_self_loops()}')
print(f'無向グラフか: {graph_data.is_undirected()}')

数学的に理解しやすくするために、グラフ（定義は広範囲：人物関係ネットワーク、画像ピクセル間の接続など）を隣接行列（Adjacency Matrices）に変換します。

より簡単な定義：\(G=(V,E)\)ここで：\(V\)はグラフのノードを表し、\(E\)は異なるノード間のエッジ（ノード間の重み、有向/無向）を表します。

networkxによるグラフ操作

import networkx as nx
import numpy as np

# グラフの定義（無向グラフ）
graph = nx.Graph()

# ノードの追加
graph.add_node("user1")
graph.add_node("user2")
graph.add_node("user3")

# エッジの追加（重み付き）
graph.add_edge("user1", "user2", weight=10)
graph.add_edge("user2", "user3", weight=5)
graph.add_edge("user1", "user3", weight=8)

# グラフ情報の表示
print(f"ノード数: {graph.number_of_nodes()}")
print(f"エッジ数: {graph.number_of_edges()}")
print("隣接行列:")
print(nx.to_numpy_array(graph))

基本理論：

1、隣接行列 \(A\)

[A_{i,j}=\begin{cases} 1 \qquad i,j間にエッジがある場合\ 0 \end{cases} ]

2、次数行列 \(D\)

[D_{i,j}=\begin{cases} deg(v_i)\qquad i=jの場合\ 0 \end{cases} ]

つまり、ノード\(i\)に接続されているエッジの数を計算します。

隣接行列への変換

import networkx as nx

# グラフの作成
G = nx.Graph()
G.add_edges_from([(0, 1), (1, 2), (2, 0)])

# 隣接行列への変換
adj_matrix = nx.to_numpy_array(G)
print("隣接行列:")
print(adj_matrix)

1.2 グラフ埋め込み方法

1.2.1 DeepWalkアルゴリズム

自然言語処理のアルゴリズム（word2vec）をグラフニューラルネットワークに導入しました。word2vecはコーパス内の文のシーケンスを使用して単語間の共起関係を記述し、単語のベクトル表現を学習します。DeepWalkアルゴリズムはword2vecと同様に、グラフ内のノード間の共起関係を使用してノードのベクトル表現を学習します。DeepWalkでは、ランダムウォーク（RandomWalk：グラフからランダムにノードを選択）を使用してグラフ内でノードをサンプリングし、コーパス内のテキストをシミュレートし、word2vecの方法を使用してノードの共起関係を学習します。DeepWalkは、まずランダムウォークを使用してノードシーケンスをサンプリングし、次にskip-gramモデルを使用して表現ベクトルを学習します。

2. 基本的なグラフニューラルネットワーク

2.1 グラフ畳み込みニューラルネットワーク

論文で定義されているグラフニューラルネットワークを踏襲します：

[f(X,A)= \sigma(D^{- 1/2}(A+I)D^{- 1/2}XW) ]

ここで： [A:隣接行列(nn), I:単位行列(nn), D:次数行列(nn), \ X:入力データ(nd), W:重みパラメータ(d*w), \sigma():活性化関数 ]

この関数の定義は、一般的なニューラルネットワークと非常に似ています：ネットワーク構造（パラメータ\(W\)）を設計し、出力データを最適化アルゴリズムでパラメータを最適化します。

• \(A+I\) の理解

ソーシャルネットワークなどのグラフでは、ノード間が互いに関連しており、ノード自身が特性を持つ（両方を考慮する必要があります）ため、モデル構築過程では、ノード自身およびノード間の情報を十分に考慮する必要があります（または：情報を伝達する）。上記（グラフの定義）で述べたように、グラフを隣接行列\(A\)に変換し、数学的に表現し、得られた隣接行列と\(XW\)を乗算することで、ノード間の関連性を考慮しています。しかし、なぜ関数を(VanillaGNN)のように設計しないのでしょうか：

[f(X,A)= \sigma(AXW) \tag{1} ]

• ノード自身の情報の自己伝達を考慮していない問題
• \(A\)は通常標準化されていないため、\(A\)との乗算により特徴ベクトルのスケールが完全に変化する
• より直感的な説明：ノードAが1000個の隣接ノードを持っているのに対し、ノードBは1個しか持っていない場合、計算された値の間に大きな差が生じる

したがって、隣接行列（\(A\)）に単位行列（\(I\)）を加えることは、グラフに自己ループを追加することに相当します。

• \(D^{- 1/2}(A+I)D^{- 1/2}\) の理解

\(D^{- 1/2}(A+I)D^{- 1/2}\) は隣接行列の標準化と呼ばれます。

なぜ標準化を実行するのでしょうか？なぜ直接\(f(X,A)= \sigma(DAXW) \tag{2} \)を使用しないのでしょうか？

グラフの定義を思い出してください：グラフはノードとエッジの2つの部分で構成されています（ノード分類タスクを例に取ります）；ノード \(i\) に対して、ノード \(i\) と接続されている他のノードおよびそれらの間のエッジの情報を組み合わせて \(i\) を判断する必要があります。つまり、まず隣接ノード情報を集約（Aggregate information）し、その後の操作を行う必要があります。データを集約するのであれば、問題が生じます：グラフ内の一部のノードは他のノードと多くの接続を持っているのに対し、一部のノードは1つのノードとしか接続していない可能性があります。

もし直接式\((2)\)を使用すると、ノード間の情報を考慮しているものの、後続のパラメータ最適化で困難が生じます。最も直接的な例は：接続ノード数に差があるのであれば、そのノード数で割ってしまえばいい！

2.1.1 グラフ畳み込みネットワークの理解

上記の式\(f(X,A)= \sigma(D^{- 1/2}(A+I)D^{- 1/2}XW)\)を\(f(X,A)=\sigma(\widehat{A}XW)\)に簡略化します。
下図を借用してグラフ畳み込みアルゴリズムを理解します（ここで\(H\)は上記の式の\(X\)に対応します）

簡略化されたグラフ畳み込み関数（ \(f(X,A)=\sigma(\widehat{A}XW)\) ）を思い出してください。グラフ畳み込みネットワークは、畳み込みニューラルネットワークを設計上借鉴しており、行列\(\widehat{A}\)には多くの0が存在します。つまり、特定のノードに対して「畳み込みカーネル」を設計し、それと接続されているノードに対して「畳み込み演算」を実行し、その後「プーリング」操作を行うことができます。

2.1.2 GCNコード

GCNの実装

import torch
import torch.nn.functional as F
from torch_geometric.nn import GCNConv

class GraphConvolutionalNetwork(torch.nn.Module):
    def __init__(self, input_features, hidden_units, output_classes):
        super(GraphConvolutionalNetwork, self).__init__()
        self.conv1 = GCNConv(input_features, hidden_units)
        self.conv2 = GCNConv(hidden_units, output_classes)

    def forward(self, node_features, edge_index):
        # 第1層の畳み込み
        hidden = self.conv1(node_features, edge_index)
        hidden = F.relu(hidden)
        
        # 第2層の畳み込み
        output = self.conv2(hidden, edge_index)
        
        return output

# モデルの初期化
model = GraphConvolutionalNetwork(input_features=16, hidden_units=32, output_classes=4)

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

GATネットワークの特徴：

• 1、ノード間で並列化操作を実行できます
• 2、異なる次数を持つグラフノードに適用できます（隣接ノードに任意の重みを指定できます）
• 3、帰納学習問題に直接適用できます（モデルが完全に見えないグラフに一般化する必要があるタスクを含む）

ここでGCNとの違い：GCNは直接隣接ノードの平均を計算します（重みは一定です）

2.2.1 GATネットワークの定義

論文で定義：一連のノード特徴量\(h=\{\vec{h_1},...,\vec{h_N} \}\)ここで\(\vec{h_i} \in R^F\)、\(N\)はノードの数、\(F\)は各ノードの特徴量の数。GATアルゴリズムのステップ：

• ステップ1：各ノードに共有線形写像を追加

[(W\vec{h_i}||W\vec{h_j}) ]

ここで\(W\in R^{{F^ \prime}*F}\)、特徴量の次元を増やすために計算を行い、\(||\)は特徴量を結合（axis=1）します。

• ステップ2：線形写像されたノードにアテンションメカニズム（self-attention）を追加

[e_{ij}=a(W\vec{h_i}|| W\vec{h_j}) ]

ここで\(e_{ij}\)はアテンション係数を表し、ノード \(i\) の隣接ノード \(j\) がそのノードに対して持つ重要性を計算するために使用されます。\(a\)は前駆ニューラルネットワークです。これにより、モデルは各ノードが他のノードに参加し、すべての構造情報を省略し、\(LeakyReLU\)を活性化関数として使用します。

• ステップ3：活性化関数とsoftmaxの追加

[\begin{aligned} \alpha_{ij}&= softmax(e_{ij})= \frac{exp(e_{ij})}{\sum_{k\in N_i}exp(e_{ik})}\ &=\frac{exp(LeakyReLU(\vec{a^T}[W\vec{h_i ||W\vec{h_j}}]))}{\sum_{k\in N_i}exp(LeakyReLU(\vec{a^T}[W\vec{h_i ||W\vec{h_k}}]))} \end{aligned} ]

ここで\(T\)は転置、\(||\)は連結操作を表します。

• ステップ4：マルチヘッドアテンション処理

[単頭アテンション: \vec{h}i^{\prime}=\sigma\left(\sum{j\in N_i}\alpha_{ij}\mathbf{W}\vec{h}_j\right) ]

ここで\(\sigma\)は非線形活性化関数です。マルチヘッドアテンションの場合：

[\ concat: \vec{h}i^{\prime}= ||{k=1}^{K} \sigma\left(\sum_{j\in N_i}\alpha_{ij}^{k}\mathbf{W^k}\vec{h}j\right) \ avg: \vec{h}i^{\prime}= \sigma\left(\frac{1}{K} \sum{k=1}^K \sum{j\in N_i}\alpha_{ij}^{k}\mathbf{W^k}\vec{h}_j\right) ]

GATの実装例

import torch
import torch.nn as nn
import torch.nn.functional as F
from torch_geometric.nn import GATConv

class GraphAttentionNetwork(nn.Module):
    def __init__(self, input_dim, hidden_dim, output_dim, heads=8):
        super(GraphAttentionNetwork, self).__init__()
        self.attention1 = GATConv(input_dim, hidden_dim, heads=heads, dropout=0.6)
        self.attention2 = GATConv(hidden_dim * heads, output_dim, heads=1, concat=False, dropout=0.6)

    def forward(self, data):
        x, edge_index = data.x, data.edge_index
        
        # 第1層のアテンション
        x = F.dropout(x, p=0.6, training=self.training)
        x = F.elu(self.attention1(x, edge_index))
        x = F.dropout(x, p=0.6, training=self.training)
        
        # 第2層のアテンション
        x = self.attention2(x, edge_index)
        
        return F.log_softmax(x, dim=1)

# モデルの初期化
gat_model = GraphAttentionNetwork(input_dim=16, hidden_dim=8, output_dim=4)

3. その他のグラフニューラルネットワーク構造

3.1 STGNN（Spatio-Temporal Graph Convolutional Networks）

著者は交通ネットワーク予測の処理過程で出現：交通流の非線形性と複雑性は、伝統的な畳み込みユニットと再帰ユニットではなく、グラフニューラルネットワークを通じて処理しました。そして**时空グラフ畳み込みネットワーク（STGNN）**を提案しました。

著者は交通予測を以下のように説明しています：

[\widehat{v}{t+1},...,\widehat{v}{t+H}= \quad \underset{v_{t+1}, \ldots, v_{t+H}}{\arg \max } \log P\left(v_{t+1}, \ldots, v_{t+H} \mid v_{t-M+1}, \ldots, v_{t}\right), ]

つまり：\(M\)個の過去の時点データに基づいて、未来\(H\)時点のデータを予測します。ここで\(v_t \in R^n\)は、\(n\)本の道路における時間\(t\)での観測ベクトル（道路の交通量を記録）を表します。

3.2 Gated Graph Sequence Neural Network

名前から理解しやすいように、\(GGSNN\)（ゲート付きシーケンスグラフニューラルネットワーク）は、シーケンスを予測できるグラフニューラルネットワークとして、著者が言及した：1、ゲート付きシーケンスユニット（gated recurrent units）；2、「最適化」方法（modern optimization techniques）。

3.3 GraphSAGE

GraphSAGEは大規模グラフを処理するGNN構造で、ノード特徴量情報（例：テキスト属性）を効率的に利用して以前に見たことのないデータのノード埋め込みを生成します。前のニューラルネットワーク構造は、ノード埋め込みの生成が本質的に伝達的であり、方法論的にもすべて行列分解に基づいています。

• 1、前向き伝播アルゴリズム（forward propagation algorithm）

• 2、集約構造（Aggregator Architecture）

集約構造は、畳み込みニューラルネットワークのプーリング層と同様です。ノード\(h_v^0\)に対して、\(K=k\)でそれと接続されているノード情報を「集約」します。論文では以下を提供しています： 1、Mean aggregator：\(\mathbf{h}_v^k\leftarrow\sigma(\mathbf{W}\cdot\text{мЕА}\mathbf{N}(\{\mathbf{h}_v^{k-1}\}\cup\{\mathbf{h}_u^{k-1},\forall u\in\mathcal{N}(v)\}).\)； 2、LSTM aggregator：方法1より表現力が強い； 3、Pooling aggregator：同時に対称性とトレーニング可能性を考慮します。\(\text{AGGREGATE}_k^{\mathbf{pool}}=\max(\left\{\sigma\left(\mathbf{W}_{\mathrm{pool}}\mathbf{h}_{u_i}^{k}+\mathbf{b}\right),\forall u_i\in\mathcal{N}(v)\right\}),\)

4. GNNの実践

4.1 ノード分類

🎏使用データセット：Cora dataset
🎏🎏タスク分析
🎏🎏プログラミング理解：ノード分類タスクは、グラフニューラルネットワークにとって、大きな行列であり、アルゴリズムの設計は行列の分析にすぎません。

ノード分類の実践

import torch
import torch.nn.functional as F
from torch_geometric.datasets import CoraFull
from torch_geometric.nn import GCNConv

# データセットのロード
dataset = CoraFull(root='./data/Cora')
data = dataset[0]

# モデルの定義
class NodeClassifier(torch.nn.Module):
    def __init__(self, input_features, hidden_units, output_classes):
        super(NodeClassifier, self).__init__()
        self.conv1 = GCNConv(input_features, hidden_units)
        self.conv2 = GCNConv(hidden_units, output_classes)

    def forward(self, x, edge_index):
        # 第1層の畳み込み
        x = self.conv1(x, edge_index)
        x = F.relu(x)
        x = F.dropout(x, training=self.training)
        
        # 第2層の畳み込み
        x = self.conv2(x, edge_index)
        
        return F.log_softmax(x, dim=1)

# モデル、オプティマイザ、損失関数の初期化
model = NodeClassifier(dataset.num_features, 16, dataset.num_classes)
optimizer = torch.optim.Adam(model.parameters(), lr=0.01, weight_decay=5e-4)
criterion = torch.nn.CrossEntropyLoss()

# トレーニング関数
def train():
    model.train()
    optimizer.zero_grad()
    out = model(data.x, data.edge_index)
    loss = criterion(out[data.train_mask], data.y[data.train_mask])
    loss.backward()
    optimizer.step()
    return loss

# テスト関数
def test():
    model.eval()
    out = model(data.x, data.edge_index)
    pred = out.argmax(dim=1)
    
    train_acc = (pred[data.train_mask] == data.y[data.train_mask]).sum() / data.train_mask.sum()
    test_acc = (pred[data.test_mask] == data.y[data.test_mask]).sum() / data.test_mask.sum()
    return train_acc, test_acc

# トレーニングループ
for epoch in range(200):
    loss = train()
    train_acc, test_acc = test()
    if epoch % 20 == 0:
        print(f'Epoch: {epoch:03d}, Loss: {loss:.4f}, Train Acc: {train_acc:.4f}, Test Acc: {test_acc:.4f}')