グラフ畳み込みネットワークの作り方は？これは最小限のNumpy実装です

グラフは非常に複雑な構造を持ち、大量の情報を含んでいるため、グラフ上での機械学習は困難な作業です。この記事では、グラフ上で直接動作し、その構造情報を活用する強力なニューラルネットワークであるグラフ畳み込みネットワーク (GCN) を使用して、グラフ上でディープラーニングを実行する方法について説明します。

この記事では GCN を紹介し、コード例を使用して、情報が GCN の隠しレイヤーを通じてどのように伝播するかを説明します。読者は、GCN が前のレイヤーから情報をどのように集約し、このメカニズムがグラフ内のノードの有用な特徴表現をどのように生成するかを確認します。

グラフ畳み込みネットワークとは何ですか?

GCN は、グラフデータ用の非常に強力なニューラルネットワークアーキテクチャのクラスです。実際、これは非常に強力であるため、ランダムに初期化された 2 層 GCN でも、グラフネットワーク内のノードの有用な特徴表現を生成できます。下の図は、この 2 層 GCN によって生成された各ノードの 2 次元表現を示しています。トレーニングを行わなくても、これらの 2D 表現はグラフ内のノードの相対的な近接性を維持できることに注意してください。

より正式には、グラフ畳み込みネットワーク (GCN) は、グラフデータに対して動作するニューラルネットワークです。グラフ G = (V, E) が与えられた場合、GCN の入力は次のようになります。

N × F⁰ 次元の入力特徴行列 X。ここで、N はグラフネットワーク内のノード数、F⁰ はノードあたりの入力特徴の数です。
グラフ構造は、グラフ G の隣接行列 A など、N × N 次元の行列で表されます。 [1]

したがって、GCN の隠れ層は Hⁱ = f(Hⁱ⁻¹, A)) と表すことができます。ここでH⁰ = Xであり、fは伝播則である[1]。各隠れ層 Hⁱ は次元 N × Fⁱ の特徴行列に対応し、行列の各行はノードの特徴表現です。各レイヤーでは、GCN は伝播ルール f を使用してこの情報を集約し、次のレイヤーの特徴を形成します。このようにして、各レイヤーごとに機能がますます抽象化されます。この枠組みの下では、GCNのさまざまな変種は伝播規則fの選択のみが異なる[1]。

伝播ルールの簡単な例

以下、この記事では最も単純な伝播ルールの例を示します[1]。

 f(Hⁱ, A) = σ(AHⁱWⁱ)

ここで、Wⁱ は i 番目の層の重み行列であり、σ は非線形活性化関数 (ReLU 関数など) です。重み行列の次元はFⁱ×Fⁱ⁺¹です。つまり、重み行列の2番目の次元のサイズによって、次の層の特徴の数が決まります。畳み込みニューラルネットワークに精通している場合は、これらの重みがグラフ内のノード間で共有されるため、この操作は畳み込みカーネルフィルタリング操作に似ていることがわかります。

簡素化する

次に、最も単純なレベルでの伝播ルールを学習します。作る：

i = 1、（制約fは入力特徴行列に作用する関数です）
σは恒等関数である
重みを選択（制約：AH⁰W⁰ =AXW⁰ = AX）

つまり、f(X, A) = AXです。この伝播ルールは単純すぎる可能性があるため、不足している部分はこの記事の後半で補足します。さらに、AX は多層パーセプトロンの入力層に相当します。

1. 簡単なグラフの例

簡単な例として次の図を使用します。

単純な有向グラフ。

numpy を使用して記述された上記の有向グラフの隣接行列は次のように表されます。

 A = np.matrix ([
    [0, 1, 0, 0],
    [0, 0, 1, 1],
    [0, 1, 0, 0],
    [1, 0, 1, 0]],
 dtype =浮動小数点数 
 ）

次に、特徴を抽出する必要があります。インデックスに基づいて各ノードに 2 つの整数特徴を生成します。これにより、この記事の後半で行列演算を手動で検証するプロセスが簡素化されます。

 [3]では、 X = np .matrix([
            [私、-私]
            i が範囲内(A.shape[0])にある場合
        ]、 dtype = float )
        バツ
出力[3]: 行列([
           [ 0., 0.],
           [ 1., -1.],
           [ 22。]、
           [3.、-3.]
        ])

2. 伝播ルールを適用する

これで、隣接行列 A と入力特徴のセット X を持つグラフが構築されました。伝播ルールを適用すると何が起こるか見てみましょう。

 [6]において: A * X
出力[6]: 行列([
            [ 1., -1.],
            [5., -5.],
            [ 1., -1.],
            [ 22。]]

各ノード (各行) の表現は、隣接するノードの特徴の合計になります。つまり、グラフ畳み込み層は、各ノードを隣接するノードの集約として表現します。この計算プロセスは自分で検証することができます。この場合、v から n へのエッジがある場合、ノード n はノード v の隣接ノードであることに注意してください。

質問

問題に気づいたかもしれません:

ノードの集約表現には、そのノード自身の特徴は含まれません。この表現は、隣接ノードからの特徴の集約であるため、自己ループを持つノードのみが集約に独自の特徴を含みます [1]。
次数が大きいノードは特徴表現でより大きな値を持ち、次数が小さいノードはより小さな値を持ちます。これにより、勾配が消失したり爆発したりする可能性がある[1, 2]。また、確率的勾配降下アルゴリズム（このようなネットワークのトレーニングに一般的に使用され、各入力特徴のスケール（または値の範囲）に敏感）にも影響を与える可能性があります。

次に、この記事ではこれらの問題について個別に説明します。

1. 自己ループを追加する

最初の問題を解決するには、各ノードに自己ループを直接追加することができます[1, 2]。具体的には、伝播規則を適用する前に、隣接行列 A を単位行列 I に追加することでこれを実現できます。

 [4]において： I = np .matrix(np.eye(A.shape[0]))
        私
出力[4]: 行列([
            [1., 0., 0., 0.],
            [0., 1., 0., 0.],
            [0., 0., 1., 0.],
            [0., 0., 0., 1.]
        ])
 [8]において: A A_hat = A + I
        A_hat * X
出力[8]: 行列([
            [ 1., -1.],
            [6., -6.],
            [3., -3.],
            [ 5., -5.]])

現在、すべてのノードはそれ自体の隣接ノードであるため、隣接ノードの特徴を合計するときに、各ノードには独自の特徴も含まれます。

2. 特徴表現を正規化する

隣接行列 A は、次数行列 D の逆行列を乗算することによって変換され、それによって特徴表現がノード次数によって正規化されます。したがって、簡略化された伝播ルールは次のようになります。

 f(X, A) = D⁻¹AX

何が起こったのか見てみましょう。まず、ノードの次数行列を計算します。

 [9]では： D = np .array(np.sum(A, axis = 0 ))[0]
 D = np.matrix (np.diag(D))
        だ
出力[9]: 行列([
            [1., 0., 0., 0.],
            [0., 2., 0., 0.],
            [0., 0., 2., 0.],
            [0., 0., 0., 1.]
        ])

伝播ルールを適用する前に、隣接行列を変換すると何が起こるかを確認しておくと役立ちます。

変身前

A = np.matrix ([
    [0, 1, 0, 0],
    [0, 0, 1, 1],
    [0, 1, 0, 0],
    [1, 0, 1, 0]],
 dtype =浮動小数点数 
 ）

変身後

[10]では: D**-1 * A
出力[10]: 行列([
             [0. , 1. , 0. , 0. ],
             [0. , 0. , 0.5, 0.5],
             [0. , 0.5, 0. , 0. ],
             [0.5, 0. , 0.5, 0. ]
 ])

隣接行列の各行の重み（値）が、その行に対応するノードの次数で割られていることがわかります。次に、変換された隣接行列に伝播規則を適用します。

 [11]では: D**-1 * A * X
出力[11]: 行列([
             [ 1. , -1. ],
             [ 2.5, -2.5],
             [ 0.5, -0.5],
             [ 22。 ]
         ])

隣接ノードの特徴平均に対応するノード表現が得られます。これは、（変換された）隣接行列の重みが、隣接ノードの特徴の加重合計の重みに対応するためです。この結果はあなた自身で確認できます。

統合

ここで、自己ループと正規化の手法を組み合わせます。さらに、議論を簡略化するために、先ほど省略した重みと活性化関数の操作を再度導入します。

1. 重みを加える

最初に行うことは、重量を加えることです。ここでの D_hat は、A_hat = A + I に対応する次数行列、つまり強制的な自己ループを持つ行列 A の次数行列であることに注意してください。

 [45]において: W = np .matrix([
             [1, -1],
             [-1, 1]
         ])
         D_hat**-1 * A_hat * X * W
出力[45]: 行列([
            [ 1., -1.],
            [4., -4.],
            [ 22。]、
            [ 5., -5.]
        ])

出力特徴表現の次元を減らしたい場合は、重み行列 W のサイズを減らすことができます。

 [46]において: W = np .matrix([
             [1]、
             [-1]
         ])
         D_hat**-1 * A_hat * X * W
出力[46]: 行列([[1.],
        [4.]、
        [2.]、
        [5.]]
 ）

2. 活性化関数を追加する

この論文では、特徴表現の次元を維持し、ReLU 活性化関数を適用することを選択します。

 [51]において: W = np .matrix([
             [1, -1],
             [-1, 1]
         ])
         relu(D_hat**-1 * A_hat * X * W)
出力[51]: 行列([[1., 0.],
        [4., 0.],
        [2., 0.],
        [5., 0.]])

これは、隣接行列、入力機能、重み、および活性化関数を備えた完全な隠し層です。

現実世界のシナリオへの応用

***、グラフ畳み込みネットワークを実際のグラフに適用します。この記事では、上記の機能表現を生成する方法を説明します。

1. ザカリー空手クラブ

Zachary Karate Club は、ノードが空手クラブのメンバーを表し、エッジがメンバー間の関係を表す、広く使用されているソーシャルネットワークです。ザカリーさんが空手クラブを調査していたとき、管理者とインストラクターの間で対立が起こり、クラブは二つに分裂しました。下の図は、ネットワークのグラフ表現を示しています。ノードは、クラブのどの部分に属するかに応じてラベル付けされており、「A」と「I」は、それぞれ管理者キャンプとインストラクターキャンプに属するノードを表しています。

ザカリー空手クラブネットワーク

2. GCNの構築

次に、グラフ畳み込みネットワークを構築します。実際にこのネットワークをトレーニングするのではなく、単にランダムに初期化して、この記事の冒頭で見た特徴表現を生成します。簡単に実装できる Zachary's Karate Club のグラフ表現を持つ networkx を使用します。次に、A_hat 行列と D_hat 行列を計算します。

 networkx から to_numpy_matrix をインポートします
zkc =空手クラブグラフ()
順序=ソート済み(リスト(zkc.nodes()))
 A = to_numpy_matrix (zkc、ノードリスト=順序)
 I = np .eye(zkc.number_of_nodes())
 A A_hat = A + I
 D_hat = np .array(np.sum(A_hat,軸= 0 ))[0]
 D_hat = np.matrix (np.diag(D_hat))

次に、重みをランダムに初期化します。

 W_1 = np.ランダム.正規分布(
位置= 0 、スケール= 1 、サイズ= (zkc.number_of_nodes(), 4))
 W_2 = npランダム正規分布(
位置= 0 、サイズ= (W_1.shape[1]、2))

次に、GCN レイヤーを積み重ねます。ここでは、特徴表現として単位行列のみを使用します。つまり、各ノードはワンホットエンコードされたカテゴリ変数として表されます。

 gcn_layer(A_hat, D_hat, X, W)を定義します。
    relu(D_hat**-1 * A_hat * X * W) を返します
H_1 = gcn_layer (A_hat、D_hat、I、W_1)
 H_2 = gcn_layer (A_hat、D_hat、H_1、W_2)
出力= H_2

さらに特徴表現を抽出します。

機能表現= {
    ノード: np.array(出力)[ノード]
    zkc.nodes() 内のノードの場合}

ご覧のとおり、この描写はザカリーの空手クラブの 2 つのコミュニティをうまく区別しています。この時点では、モデルのトレーニングはまだ始まっていません。

ザカリー空手クラブグラフネットワークのノードの特性

この例では、ReLU 関数の影響により、x 軸または y 軸上のランダムに初期化された重みが 0 になる可能性が高いため、上記の図を生成するには複数のランダム初期化が必要になることに注意してください。

結論

この記事では、グラフ畳み込みネットワークの概要を説明し、GCN 内の各ノード層の特徴表現が、隣接ノードの集約に基づいてどのように構築されるかを説明します。 NumPy を使用してこれらのネットワークを構築する方法とその強力さを学ぶことができます。ランダムに初期化された GCN でも、Zachary の空手クラブネットワーク内のコミュニティを分離できます。

参考文献