MLエンジニアへの道 #32

このブログ記事では、ディープラーニングにおけるGCNについて紹介します。

前回の記事では、グラフの潜在表現を生成する関数 $F$ が置換等変性を持つ必要があることを説明しました。これは、置換不変なローカル関数 $g$ を行ごとに適用する形で実現されます。 $g$ に使える置換不変な関数は複数ありますが、その中でも最も単純なものの1つは、ノードとその隣接ノードの各特徴量の加重和を取る方法、またの名を畳み込みです。

グラフ畳み込み

グラフ畳み込みは、画像処理における畳み込み演算とは異なり、固定サイズのカーネルをスライドさせることはありません。しかし、本質的には、データとその隣接ノードの加重和を取るという点で同じです。隣接行列 $A$ を使用することで、隣接ノードの加重和を $AXW$ で便利に計算できます。ここで、 $A$ のサイズは $(n, n)$ 、ノード行列 $X$ のサイズは $(n, d_{in})$ 、重み行列 $W$ のサイズは $(d_{in}, d_{out})$ です。ここで、 $n$ はノード数、 $d_{in}$ はノード特徴量の次元数、 $d_{out}$ はカーネル数または出力特徴量の次元数を表します。結果の加重和はサイズ $(n, d_{out})$ となります。

しかし、 $AXW$ はノード自身を加重和の計算に含まないため、正しい畳み込みにはなりません。この問題を解決するために、隣接行列に単位行列を加算して新しい行列 $\tilde{A}$ を作成し、 $\tilde{A}XW$ を計算することで、正しいグラフ畳み込みを実現します。ここで、 $W$ をサイズ $(n, n)$ に設定し、ノードペアに依存した値を持たせて $W\tilde{A}X$ を計算することもできます。しかし、この操作は置換等変性を持ちません。これは、 $W$ の置換が $\tilde{A}$ の置換と対応している必要があるためです。そのため、入力および出力特徴量に対応する値を持つ $W$ を用いて $\tilde{A}XW$ を計算します。

グラフ畳み込みネットワーク (GCN)

モデルがバックプロパゲーションを通じて複雑で非線形な関係を学習できるようにするため、非線形活性化関数 $\sigma$ を導入して $\sigma(\tilde{A}XW)$ を計算します。しかし、加重和から得られる潜在表現は次第に大きくなり、モデルが適切な重みを学習するのが難しくなる可能性があります。この加重和を正規化するために、各ノードの次数を対角成分に持つ次数行列 $D$ の逆行列を加重和に乗算します。これにより、以下のような グラフ畳み込みネットワーク (GCN) を得ることができます。 (*次数は、非重み付きグラフではエッジの数、重み付きグラフではエッジ重みの合計を指します。)

H^{0} = X \\ H^{(l+1)} = \sigma(D^{-1}\tilde{A}H^{(l)}W^{(l)})

各層 $l$ において、GCN は上記の計算を実行してサイズ $(n, d_{out})$ のグラフ埋め込み $H^{(l+1)}$ を生成します。ただし、実際には、GCN は $\sigma(D^{-\frac{1}{2}}\tilde{A}D^{-\frac{1}{2}}H^{(l-1)}W^{(l)})$ を計算することが多いです。これは、ノード自身の次数で正規化する代わりにノードペアの次数の平方根 $\sqrt{d_id_j}$ で値を正規化するとより良い性能を示すことが分かっているためです。 $g$ と $F$ の文脈では、GCN は以下のように表現できます。

g(x_i, X_{N_i}) = \sum_{j \in \{i, N_i\}} \frac{1}{\sqrt{d_i d_j}}Wx_j \\ F(X, A) = \begin{bmatrix} - g(x_1, X_{N_1}) -\\ - g(x_2, X_{N_2}) -\\ \vdots \\ - g(x_v, X_{N_v}) -\\ \end{bmatrix} = \sigma(D^{-\frac{1}{2}}\tilde{A}D^{-\frac{1}{2}}XW)

ノードに依存しない重みを使用した、ノードとその隣接ノードの正規化された加重和を取るという単純な畳み込み操作により、 GCNは類似したノードが接続されやすいホモフィラスグラフに対して良い性能を発揮する傾向があります。

コードの実装

以下は、TensorFlow を用いた GCN 層の実装を示しています。

class GraphConvolutionLayer(layers.Layer):
    def __init__(self, d_in, d_out):
        super(GraphConvolutionLayer, self).__init__()
        self.d_in = d_in
        self.d_out = d_out
        self.W = self.add_weight(shape=(d_in, d_out),
                                       initializer='glorot_uniform',
                                       trainable=True)
 
    def call(self, x, A):
        D = tf.reduce_sum(A, axis=-1)
        D = tf.linalg.diag(D)
        D_inv_sqrt = tf.linalg.inv(tf.sqrt(D))
        A = tf.matmul(tf.matmul(D_inv_sqrt, A), D_inv_sqrt)
        x = tf.matmul(A, x)
        x = tf.matmul(x, self.W)
        x = tf.nn.relu(x)
        return x

この実装では、次数行列が提供されないことを前提としています。得られた潜在表現は、様々なグラフタスクを実行するために、後続の分類器や回帰器に渡すことができます。練習としてPyTorch を使ってグラフ畳み込み層を実装してみることをお勧めします。

結論

この記事では、置換不変な集約演算子として畳み込みを使用し、置換等変なグラフ畳み込み層を構成する方法、層を積み重ねてグラフ畳み込みネットワークを構築する方法、および下流タスクのための潜在表現を生成する方法を解説しました。数学的操作とコード実装を示しながら、ノードに依存しない重みを用いることで GCN がシンプルかつホモフィラスグラフに対して効果的である理由にも触れました。次回の記事では、ホモフィラスでないグラフにも適用可能な、より複雑なモデルを紹介します。

リソース

Barbero, F. 2023. Graph Convolutional Networks - Oxford Geometric Deep Learning. YouTube.
Velickovic, P. 2021. Theoretical Foundations of Graph Neural Networks. YouTube.