9 つの SOTA GNN よりも強力です。 Google Brainが新しいグラフニューラルネットワークGKATを提案

  [[413820]]

グラフは、ソーシャル ネットワークからバイオインフォマティクス、ロボット工学のナビゲーションや計画の問題に至るまで、さまざまな現実世界のデータセットに遍在しています。

その結果、グラフ構造化されたデータを処理するために特別に設計されたグラフ ニューラル ネットワーク (GNN) に大きな関心が寄せられるようになりました。

最新の GNN はグラフ データの理解に大きな成功を収めていますが、グラフ データを効果的に処理するにはまだいくつかの課題が残っています。

たとえば、考慮するグラフが大きい場合、計算の複雑さが問題になります。

対照的に、空間領域で動作するアルゴリズムは、高価なスペクトル計算を回避しますが、単一レイヤーではローカルな相互作用のみをモデル化するため、より長い範囲の依存関係をモデル化するには、遠方のノードからの信号伝播を実装するためにディープ GNN アーキテクチャに依存する必要があります。

これらの問題に対処するために、Google Brain、コロンビア大学、オックスフォード大学の研究チームは、新しいタイプのグラフニューラルネットワークであるGraph Kernel Attention Transformers（GKAT）を提案しました。

これは、グラフ カーネル、アテンション ベース ネットワーク、構造事前確率、および低ランク分解技術を通じてメモリ フットプリントの小さい暗黙的アテンション メソッドを適用する最新の Transformer アーキテクチャを組み合わせたものです。

研究チームは、GKAT は計算負荷を軽減しながら、SOTA GNN よりも表現力が高いことを実証しました。

計算の複雑さを軽減する新しいGNN

「グラフ内のより長距離のノード間の関係を明示的にモデル化する密な個々のレイヤーを持つ GNN を設計し、それによってより浅いアーキテクチャを実現しながら、より大きな (必ずしもスパースではない) グラフに拡張することは可能でしょうか?」

GKAT における分解可能なロングアテンション

GKAT は、各レイヤー内のグラフ アテンションを、ノード特徴ベクトルのカーネル マトリックスとグラフ カーネル マトリックスのアダマール積としてモデル化します。

これにより、GKAT は計算効率の高い暗黙的な注意メカニズムを活用し、単一レイヤー内でより長い範囲の依存関係をモデル化できるため、従来の GNN を超える表現力が向上します。

効率的なマッピングを可能にするグラフノード上の表現力豊かなカーネルを定義するために、研究者らは、2 つのノードの値がグラフノード内のランダムウォークを記録する 2 つの頻度ベクトルのドット積として与えられる、新しいランダムウォーク グラフノードカーネル (RWNGK) アプローチを採用しました。

完全な GKAT アーキテクチャは複数のブロックで構成され、各ブロックはアテンション レイヤーと標準 MLP レイヤーから構築されます。

特に、アテンション レイヤーは入力グラフ内のノードの数に対して 2 次ではなく線形にスケーリングされるため、通常のグラフ アテンション レイヤーと比較して計算の複雑さが軽減されます。

9つのSOTA GNNを上回る

エルデシュ・レーニランダムグラフ

著者らは、モチーフに接続されたランダム ER グラフ (正の例) またはモチーフと同じ平均次数を持つ他の小さな ER グラフ (負の例) で構成される 5 つのバイナリ分類データセットを使用しました。

各データセットに対して、S 個の正例と S 個の負例が構築されます (S = 2048)。

著者らは、GKAT、グラフ畳み込みネットワーク (GCN)、スペクトルグラフ畳み込みネットワーク (SGC)、およびグラフ注意ネットワーク (GAT) をテストしました。

各頂点の固有ベクトルの長さは l = 5 で、その近傍の次数 l が含まれます (l 未満の場合、0 で埋められます)。

各ファントムのデータセットは、75% のトレーニング セットと 25% の検証セットにランダムに分割されました。

同時に、学習率 η = 0.001 の Adam オプティマイザーが使用され、検証損失と検証精度が c = 80 連続エポックで改善されない場合は、トレーニングが早期に停止されます。

モデルについては、著者らは 2 層アーキテクチャを使用することを選択し、すべてのモデルが同等のサイズになるように調整を行いました。

GCN と SGC では、隠れ層に h = 32 個のノードがあります。

SGC では、各隠れ層は 2 つの多項式ローカル フィルターと組み合わされます。

GAT と GKAT では、2 つのアテンション ヘッドが使用され、隠れ層には h = 9 個のノードがあります。

GKAT では、長さ τ = 3 のランダムウォークが使用されます。

GKAT はすべてのモチーフにおいて他の方法よりも優れていることがわかります。

長い誘導ループの検出と深さと密度の注意テスト

アルゴリズムは、与えられた定数 T に対して、グラフに T より大きい長さの誘導サイクルが含まれているかどうかを判断する必要があります。

したがって、モチーフ自体は、ノードの近傍を探索するだけでは検出できないグローバル プロパティになります。

この実験では、深さと密度のトレードオフにも注意する必要があります。

高密度の注意力を持つ浅いニューラル ネットワークは、スパース レイヤーに依存する深いネットワークをモデル化できますが、レイヤーごとに追加の計算コストがかかります。

実験では、GCN、GAT、SGC の隠れ層のノード数と、GAT の各注意ヘッドの数を制御して、トレーニング可能なパラメータの総量が 2 層 GKAT と同程度になるようにする必要があります。

GKAT の場合、第 1 層に 8 つのヘッドが適用され、第 2 層に 1 つのヘッドが適用され、各ヘッドのサイズは d=4 です。

最後の層は、バイナリ分類の出力次元 o = 2 とランダム ウォークの長さ τ = 6 を持つ完全接続層です。

異なる長さの GKAT のランダムウォーク結果

2層GKATと、異なる隠れ層数（2～6）のGCN、GAT、SGCとの比較

ご覧のとおり、より浅い GKAT は、ほぼすべての GCN バリアント、および 4 層未満の GAT と SGC よりも優れています。

さらに、GKAT は 4 層の GAT および SGC と同等の傾向を持ちますが、トレーニングと推論の実行がより高速です。

バイオインフォマティクスタスクとソーシャルネットワークデータのテスト

著者らは、GKAT を DCGNN、DiffPool、ECC、GraphSAGE、RWNN などの他の SOTA GNN 手法と比較しています。

バイオインフォマティクス データセットの場合、分子フィンガープリント (MF) 法がベースラインとして使用されました。

ソーシャル ネットワーク データセットの場合、DeepMultisets (DM) メソッドがベースラインとして使用されます。

GKAT 構成に関しては、まず k 個のヘッド (調整するハイパーパラメータ) を持つ注意層が適用されます。

これに続いて、グラフ上のトポロジ情報を集約するためのヘッドを備えた別のアテンション レイヤーが続きます。

次に、MF メソッドまたは DM メソッドを適用して、集約された情報をさらに処理します。

各 GKAT レイヤーのランダム ウォークの長さ τ は、τ ≤ 4 を満たし、評価されるデータセットによって異なります。

ランダムウォークが長くなると原理的にはより多くの情報を取得できますが、無関係なノードの数が増えるという代償を伴います。

バイオインフォマティクスデータセット

ソーシャルネットワークデータセット

その中で、平均グラフ パス (各ノード ペア間の最長最短パスの平均) は、歩行距離を調整し、実験の平均ノード数に最も近いノード数を持つグラフを選択するのに役立ちます。

著者らは、9 つ​​の標準的かつ公開されているバイオインフォマティクスおよびソーシャル ネットワーク データセットでグラフ分類タスクに対して GKAT をテストしました。

各データセットについて、最もパフォーマンスの高い方法が太字で表示され、2 番目に優れた方法が下線で表示されます。

GKATはバイオインフォマティクスデータセットの4つのタスクのうち3つで最高の結果を達成しました。

GKATはソーシャルネットワークデータセットの5つのタスクのうち4つで上位2位にランクイン

注目すべきことに、GKAT は、1 つを除くすべてのバイオインフォマティクス データセットでベースラインを一貫して上回る唯一の GNN 手法です。

GKATの空間と時間の複雑さの向上

著者らは、分解可能注意力を備えた GKAT (GKAT+) の速度と記憶力の向上を GAT と比較し、通常の GKAT での精度の低下を比較しました。

対応する GKAT モデルと GKAT+ モデル間の精度の差は非常に小さいことがわかります。

しかし、GKAT+ は、GAT と比較して、各アテンション レイヤーで一貫した速度とメモリの向上を実現し、特に Citeseer と Pubmed の非常に大きなグラフではその向上は顕著です。

GKAT+は速度と空間の複雑さを改善します

最初の行: graphot によるグラフのメモリ圧縮 (低いほど良い)。

2 行目と 3 行目: 各注意層のトレーニング速度と推論速度は、GAT と比較してそれぞれ向上しています。

4 行目: 分解可能な注意メカニズムを適用しない場合の GKAT と比較した精度の低下。

2層構造を持つさまざまなネットワークをトレーニングする時間

さらに、通常の GKAT は、特定の精度レベルに到達するのに必要な時間に関しても、対応するモデル (GCN、GAT、SGC) よりも高速です。

要約する

著者は、新しい注意ベースのグラフニューラルネットワーク、グラフカーネル注意トランスフォーマー (GKAT) を提案しました。

1. グラフカーネル法とスケーラブルアテンションを活用
2. グラフデータの処理における表現力の向上
3. 時間計算量とメモリ使用量が少ない
4. 幅広いタスクにおいて他のSOTAモデルよりも優れたパフォーマンスを発揮します