【DL輪読会】AUTOGT: AUTOMATED GRAPH TRANSFORMER ARCHITECTURE SEARCH

DEEP LEARNING JP AUTOGT: AUTOMATED GRAPH TRANSFORMER ARCHITECTURE SEARCH [DL Papers] Kensuke Wakasugi, Panasonic Holdings Corporation. http://deeplearning.jp/ 1

• http://deeplearning.jp/

書誌情報 ◼ タイトル： AUTOGT: AUTOMATED GRAPH TRANSFORMER ARCHITECTURE SEARCH ◼ 著者： Zizhao Zhang1, Xin Wang1,2∗, Chaoyu Guan1, Ziwei Zhang1, Haoyang Li1, Wenwu Zhu1∗ • 1Department of Computer Science and Technology, Tsinghua University • 2THU-Bosch JCML Center, Tsinghua University ◼ URL: https://openreview.net/forum?id=GcM7qfl5zY ◼ 選書理由 GNN関連に興味があり、 ICLR2023のNotable-top-5%からGNN論文を選出。 ※特に記載しない限り、本資料の図表は上記論文からの引用です。 2

• https://openreview.net/forum?id=GcM7qfl5zY

3 イントロ ■背景・課題 • • Transformerの登場以後、Graph Neural Network（GNN）への応用も進む。 しかし、グラフ特有の情報の埋め込みは、依然として試行錯誤が必要。 ■Contributions • • • • Graph Transformerのアーキテクチャを自動的に探索するフレームワークを初めて提案 近年のSOTAを含む、統一的な探索空間を設計 グラフエンコーディングに着目した、探索戦略により、探索コストを低減 提案手法により、SOTAを超える性能を複数のベンチマークで達成

4 AutoGT Automated Graph Transformer Architecture Search (AUTOGT) • Graph Transformer関連技術を統一的に扱うことが できる空間を設計 • Graph特有の差分： -Node特徴へのadd -Attention Mapへのadd • 上記差分のあるなしを探索空間に含むことで、 既存手法を統一的に取り扱えるように。 • 各種パーツの他、layer数、各種次元も探索対象。

5 Transformer Architecture Transformerの内、nodeのembeddingとattention mapにgraph由来の情報を加算 • Transformer部分は一般的な構造 • Input Embedding：H(l)と、 Multi-Head Attention：“softmaxのカッコ内”に、 Graphからの情報を加算

6 Graph Encoding Strategy Graph Encodingを二か所で表現。処理変更で既存手法を切り替え ・・・Input Embeddingへの加算 ・・・ Multi-Head Attention への加算 ・・・ Hの更新式全体

Graph Transformer Search Space 最大サイズのNNパラメータから、対象パラメータを抽出して学習を実行 • • 最大サイズのNNパラメータを用意 NASに応じて、対象部分のパラメターのみ学習させる →レイヤー数変更時は、重複部分を継承。 • • 上段は、数に関わる探索（レイヤー数、次元数） 下段は、使用・不使用の探索 7

8 Node Attribution Augmentations グラフGから、node毎の特徴量を算出し、加算 ■nodeへの加算 ①Centrality Encoding • • 有効グラフの場合における、inとoutのエッジ数（次数）に基づく特徴量． 次数毎の埋め込みベクトル（学習対象、nodeと同じ次元数） ■参考 Ying, C., Cai, T., Luo, S., Zheng, S., Ke, G., He, D., ... & Liu, T. Y. (2021). Do transformers really perform badly for graph representation?. Advances in Neural Information Processing Systems, 34, 28877-28888.

9 Node Attribution Augmentations グラフGから、node毎の特徴量を算出し、加算 ■nodeへの加算 ②Laplacian Eigenvector ■参考 Belkin, M., & Niyogi, P. (2003). Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation, 15(6), 1373-1396. i. グラフGのnodeをある空間に埋め込んだ時の座標をyとするとき、 以下を最小化するとよい WはGから得られる node間の関係性 ii. • 式変形すると、グラフラプラシアンLが出てくる。 グラフラプラシアンから、良い埋め込み表現を算出 iii. 良い埋め込み表現は以下を最小化する iv. k次元表現を得たい場合、 固有値が小さい順に、k個の固有ベクトルを使う

Node Attribution Augmentations グラフGから、node毎の特徴量を算出し、加算 ■nodeへの加算 ③SVD-based Positional Encoding • • 隣接行列の特異値分解で得られる行列をnode特徴として利用 正負の任意性があるので、学習時はランダムにフリップ。 10

11 AutoGT 再掲 Automated Graph Transformer Architecture Search (AUTOGT) • Graph Transformer関連技術を統一的に扱うことが できる空間を設計 • Graph特有の差分： -Node特徴へのadd -Attention Mapへのadd • 上記差分のあるなしを探索空間に含むことで、 既存手法を統一的に取り扱えるように。 • 各種パーツの他、layer数、各種次元も探索対象。

Attention Map Augmentations Space グラフGから、Attention Mapを算出し、加算 ■ Attention Mapへの加算 ①Spatial Encoding、②Edge Encoding • • Spatial：shortest path lengthに応じた重み Edge：経路上のedge特徴の平均 ■参考 Ying, C., Cai, T., Luo, S., Zheng, S., Ke, G., He, D., ... & Liu, T. Y. (2021). Do transformers really perform badly for graph representation?. Advances in Neural Information Processing Systems, 34, 28877-28888. 12

Attention Map Augmentations Space グラフGから、Attention Mapを算出し、加算 ■ Attention Mapへの加算 ③Proximity-Enhanced Attention • m個のedgeを経由して、viとvjが接続しているかどうか、 あるいは、その場合の数 13

Attention Map Augmentations Space グラフGから、Attention Mapを算出し、加算 ■ Attention Mapへの加算 ③Attention Mask • m個以下のedgeを経由して、viとvjが接続している場合０、それ以外-∞ 14

既存手法との対応関係 既存手法を包括した枠組みになっている 15

Encoding-Aware Supernet Training 共通の学習パラメータWを用意し、アーキテクチャに応じて部分的に利用 ■NASの問題として記述すると以下のようになる • アーキテクチャa毎に定義されるWの代わりに、 共通のW（パラメータ数最大のaに対応）を定義し、 aの選択に応じて、Wの一部を学習パラメータとして採用。 16

Encoding-Aware Supernet Training Attention map augmentationの有無で8通りにGNNをスプリットして学習 • 学習初期は、全パラメータで学習（supernet） Attention map augmentation部分（左図紫）の有無 で学習パラメータも8通り用意 これにより、探索空間が広くてもうまく学習できるとのこと • Evolutionary Search • • • • mutation:性能上位のアーキテクチャのchoicesを変更 cross over:同じレイヤー数のアーキテクチャ間で、 choicesを入れ替え 学習データ数に応じて、パラメータサイズは2通りのいずれかを選択。 17

18 Experiments 2値分類のベンチマークで検証 ■データセット • • 主として、2値分類のベンチマークで検証。 データ数は303～41,127個。 ■学習パラメータ • • • • • ①AutoGT（L = 8, d = 128) ②AutoGTbase(L = 4, d = 32) バッチサイズ：128 Optimizer：Adam lr：3e-4 iteration(supernet+subnet)： ①50 + 150 = 200 ②6 + 44 = 50 ※evoは別。

19 Experiments いずれの従来法よりも良い精度。Evolutionary Searchも必要 • GT(ours)は、Searchパートなし※おそらく8通りのGNNのmix →探索も必要。

20 その他解析 統一的な探索空間を設定するだけでなく、Attention Mapに着目したことが重要 ■Time Cost • OGBG-MolHIVのデータにおいてGraphormerと比較して“たった“7倍 • • • GraphormerもAutoGTも、2minutes /1epoch on single GPU Graphormer：300 epoch AutoGT：50 + 150×8 + 900(evoにおける2000回評価分)=2150 epoch Table3から抜粋 ■Ablation Studies • PROTEINSデータで比較 ①One-Shot：8subnetを使用しない場合 ②Positional-Aware：node特徴の有無でsubnetを構成 • ①→②の改善幅より、②→AutoGTの方が5倍近い改善なので、 Attention Map Encodingについてsubnetを構成したほうが効果的

Conclusion • 従来手法を包含する統一的なアーキテクチャ探索空間を提案 • Attention Map Encodingの有無で探索を分けることで、効率的に探索 • 従来法を上回る性能も達成 21

22 所感 • Graph由来のnode特徴量や、Attention Mapへの埋め込み方について統一的に取り 扱っていて、比較検討がしやすい • 一方、グラフの情報の使い方・埋め込み方が網羅されているわけではないように思われ、 アーキテクチャの探索には余地がある印象