グラフ表現学習

グラフ表現学習は、低次元の埋め込みでグラフの構造を効果的に要約するタスクです。深層学習の台頭に伴い、研究者はグラフ表現学習にニューラルネットワークを使用するさまざまなアーキテクチャを考案しました。このようなアーキテクチャをグラフニューラルネットワークと呼びます。

このGoogleコラボノートブックでグラフニューラルネットワークを試す→

なぜグラフニューラルネットワークが必要なのか？

GNNの詳細を見る前に、まずその背後にあるモチベーションを理解しましょう。グラフ表現学習にCNNやRNNなどの現在の深層学習アーキテクチャを使用できないかどうかを尋ねる人もいるかもしれません。ただし、CNNはグリッドのような構造を専門としているのに対し、RNNはシーケンシャルデータを専門としていることがわかります。対照的に、グラフはより構造化されておらず、そのような設定で学習できる特別な方法によって効果的になるでしょう。

グラフは各所にあります！
さまざまなデータストアには固有のグラフィカル構造があり、このデータを活用すると大きな影響を与える可能性があります。GNNが影響を与える可能性のあるドメインは、以下の通りです。

• ソーシャルネットワーク
• 経済ネットワーク
• 生物医学ネットワーク
• インターネット
• ニューロンネットワーク

これらのネットワークは、より良いレコメンデーションシステム、さまざまなコンポーネントの経済的影響の理解、創薬、脳内のニューロンの機能の理解、およびその他の多くのアプリケーションに活用できます。

問題の説明

ノード分類

他の既知のノードに基づいて未知のノードを分類します。たとえば、ソーシャルメディアアカウントをボットまたは人間として分類します。

グラフの分類

これには、グラフ全体を事前定義されたカテゴリに分類することが含まれます。たとえば、分子がその原子構造に基づいて水溶性であるかどうかを予測します。

リンク予測

グラフ内の特定のノードが他のノードにリンクされているかどうかを判断します。たとえば、ソーシャルネットワークで、ある人が別の人を知っているかどうかを予測したり、友達を提案したりするために使用できます。

グラフ回帰

グラフ回帰タスクは、ロジスティック回帰およびロジスティック分類に類似しています。分類ではなく、利用可能なグラフ構造に対して特定の変数を回帰することに焦点を当てた、異なる損失関数とパフォーマンスメトリックがあります。

ノード埋め込みの生成

グラフ構造から表現を学習するタスクには、グラフのノードの低次元埋め込みを作成することが含まれます。目標は、類似しているノードが低次元のユークリッド空間でより近くなるようにすることです。このタスクは、次の画像に示されています。

ノード埋め込みの2つの基本的なアプローチについて説明します。（1）古典的な「浅い」方法、および（2）ニューラルネットワークベースの方法。

浅い埋め込み方法

浅い埋め込み方法の典型的な特徴は、エンコーダーのサイズがグラフ内のノードの数に比例して大きくなることです。ノード埋め込みの取得は、基本的にテーブルルックアップです。したがって、名前は「浅い」です

次の画像に示すように、最も単純な浅いエンコード方式を検討します。

浅いノードの埋め込みを学習するタスクには、通常、次の3つのステップが含まれます。

1. ノードを埋め込みにマップするエンコーダーを定義します。

  ENC(v) = Z.v; 

ここで、$ZϵR^{d\times |\nu |},|\nu |$、$v$はグラフ内のノードの数、vはグラフ内の任意のノードのワンホットエンコードされたベクトルです。

2. つのノード間の類似性を測定する関数、つまり、$similarity(u,v)$を定義します.

3. 類似度類似度$similarity(u,v)\approx z_v^T.z_u$となるようにエンコーダーのパラメーターを最適化します

Node2Vec、DeepWalk、LINE など、他にもこのような浅いエンコーディングベースのアプローチがあります。ただし、このようなアプローチにはいくつかの固有の問題があります。

• エンコーダーのサイズは$\mathrm{O}(|V|)$であり、これは多くのノードを持つ大きなグラフのスケーラビリティに影響を与えます。

• エンコーダーのパラメーターを最適化するための基準となる類似性メトリックを定義することは困難です。 隣接ノードに基づいて類似性メトリックを計算する場合、メトリックの範囲は、埋め込みを単に最も近い隣接ノードを集約することに制限し、カバレッジを増やすと、計算の複雑さが増します。

• このような浅い埋め込み方法は、トレーニング中にグラフに存在するノードに対してのみ機能します。したがって、グラフが更新されるテスト中に使用できなくなります

• これらのメソッドには、特定のタスクに役立つ可能性のあるノード機能が組み込まれています。

グラフニューラルネットワーク

上述のように、浅い埋め込み方法には、実際のシナリオで実行する能力に影響を与える特定の制限があります。これらの問題を修正するために、GNNを調べます。ニューラルネットワークベースのノード埋め込みアプローチには、大きく2つのタイプがあります。

1. メッセージパッシングベースのGCN

2. WLテストに基づくWeisfeiler-Lehman GNN [1]

このレポートでは、現在のWLGNNベースのアプローチはスケーラブルではないため、メッセージパッシングベースのGCNについてのみ説明します。それらの複雑さは、グラフサイズに関して空間と時間で多項式的に増加し、一般に、大規模なデータセットではWLGNNの使用が困難になります。

メッセージパッシングベースのグラフ畳み込みネットワーク

メッセージパッシングベースのGCNは、近隣集約と呼ばれる概念に依存しています。基本的に、各ノードの埋め込みは、ニューラルネットワークを通過するすべての隣接ノードの平均になります。正しくフォローしている場合は、それでも単にネイバーを集約しているだけだと思うかもしれません。ただし、これは反復手順であるため、グラフ全体をカバーするために、数回の反復後の集計が複合されることが想像できます。このプロセスは、以下の画像で視覚化できます。

正式には、このプロセスは次の手順として要約できます。

1. 近隣集計関数を定義します
最も単純なケースは、各ノードがすべての隣接ノードを等しく考慮する場合です。つまり、すべての隣接ノードが等しく重み付けされ、生成されたノードの埋め込みに等しい影響を与えます。このようなアーキテクチャは、等方性とも呼ばれます。例：GCN[2]およびGraphSage[3]。次の式は、等方性アーキテクチャのノード更新操作を示しています。 $h_i^{l+1}=\sigma (W_1^l{h}_i^l+{\Sigma }_{jϵN_i}{W}_2^l{h}_j^l),h^l,h^{l+1}ϵ{\mathbb{R}}^{n\times d},W_{1,2}^lϵ{\mathbb{R}}^{d\times d}$
$\sigma$はReLUのような活性化関数です。より高度なアーキテクチャは異方性です。つまり、各ネイバーは、生成されたノードの埋め込みにさまざまな影響を及ぼします。例えば：MoNet[4]、GAT[5]、GatedGCN[6]。次の式は、異方性アーキテクチャのノード更新操作を示しています。 $h_i^{l+1}=\sigma (W_1^l{h}_i^l+{\Sigma }_{jϵN_i}{\eta }_{ij}{W}_2^l{h}_j^l),h^l,h^{l+1}ϵ{\mathbb{R}}^{n\times d},W_{1,2}^lϵ{\mathbb{R}}^{d\times d}$ ここで、ηij​=fl(hil​,hjl​)およびflは、トレーニング中に重みが学習されるパラメーター化された関数です。 ここでの\eta_{ij} = f^l(h^l_i, h^l_j)$が注意メカニズムとして寄与することに注意してください。

2. 損失関数を定義します
損失関数は、予測が行われるタスクに基づいて定義されます。たとえば、ノード分類タスクの場合、損失関数はラベルを予測する際のBCE損失になります。したがって、学習されたノードの埋め込みは特徴を抽出するのに効果的で、ノードのクラスを決定するのに役立ちます

3. トレーニング
定義された損失関数に基づいて、勾配降下法を適用して、ネットワーク全体で共有されるパラメーターの重みを更新します。各更新ステップはローカルネイバーにのみ依存するため、この操作は非常にスケーラブルであり、バッチ操作が可能です。メッセージパッシングベースのGCNについて理解したので、次のセクションでは、このタイプの最もパフォーマンスの高いアーキテクチャの1つであるゲートグラフ畳み込みネットワークについて説明します。

ここで、$U^l,V^lϵ{\mathbb{R}}^{d\times d}$, ⊙は要素ごとの乗算を意味し、Niはノードiの近傍であり、$e_{ij}^l$は次のように定義されたエッジゲートです。

$e_{ij}^l=\sigma ({\hat{e}}_{ij}^l)÷({\Sigma }_{j^{\prime }ϵN_i}\sigma ({\hat{e}}_{i{j}^{\prime }}^l)+\epsilon )$

${\hat{e}}_{ij}^l={\hat{e}}_{ij}^{l-1}+ReLU(BN(A^l{h}_i^{l-1}+B^l{h}_j^{l-1}+C^l{\hat{e}}_{ij}^{l-1}))$
where σ is the signmoid function, ε is a small fixed constant for numerical stability, Al,Bl,ClϵRd×d

ここで、σは符号関数、εは数値安定性のための小さな固定定数、Al,Bl,ClϵRd×dです。

これで多くの方程式ができました。これらの方程式が示す顕著な特徴を見てみましょう。

特徴

• コンポーネント$h_i^{l+1}=h_i^l+ReLU(...)$（...）は、ニューラルネットワークの残りの接続を示します。これらの「スキップ接続」は、より深いネットワークのトレーニングを容易にします。

• $e_{ij}^l$は、各ネイバーに与えられる重みを決定するため、注意メカニズムとして機能します。

• $BN$ は、学習プロセスの安定化に役立つバッチ正規化を示します。

  GatedGCNの機能を確認したので、次のセクションで実際に実験します

Experiment

バイナリノード分類のためにDwivediらによって提案されたPATTERNデータセットでネットワークをトレーニングします。これは、確率的ブロックモデル（SBM）を使用して生成された人工データセットです。SBMは、ソーシャルネットワークのコミュニティを制御可能にモデル化することが知られています。トレイン/検証/テストの分割は、平均117ノードと4749エッジの10K/2K/2Kグラフです。

実験はPyTorchで実行されます。コラボノートブックはこのリンクから入手できます。AdamオプティマイザーをReduceLROnPlateauスケジューラーと一緒に使用します。初期学習率は10-3で、減少係数は0.5でした。実験時にColabによって割り当てられたGPUはNvidiaT4でした。モデルは約50エポックで収束し、各エポックには約280秒かかります。

検証精度とエポックのグラフに示されているように、モデルは検証精度84.37%で収束します。

最後に、テスト分割の分類精度は84.5%です。

フルコード→

結論

このレポートでは、グラフ表現学習の背後にある動機とGNNの必要性を理解しています。また、現在研究されているGNNベースのアプローチを幅広く検討し、方法を直感的に理解します。最後に、最高のパフォーマンスを発揮するGNNアーキテクチャの1つであるGatedGCNの内部動作を理解しました。

このレポートは、グラフィック表現学習に使用されている方法の概要として機能しますが、現在利用可能な文献の深さの観点から、表面をかじっただけです。Dwivedi氏等による論文Benchmarking Graph Neural Networksをご覧になることを読者にお勧めします。このホワイトペーパーでは、現在のGNNアーキテクチャの詳細と、すべての方法の標準化された比較について詳しく説明します。また、Githubでコー��を公開しています。この実験に使用されたコードは、それらのコードの簡略版です。演習として、読者は、重みとバイアスのレポートを使用して、すべてのアーキテクチャをトレーニングおよび比較できます。

この投稿のパート2をチェックしてください。ここでは、メッセージパッシングベースのGNNアーキテクチャを比較しています。

参考文献