JavaScriptを有効にしてください

【論文メモ】Graphormer: Do Transformers Really Perform Bad for Graph Representation?

 ·  ☕ 3 min read

はじめに


  • Transformerをベースとしたグラフ学習手法 (NeurIPS 2021)

  • 構成要素は三つ

    • Centrality Encoding
    • Spatial Encoding
    • Edge Encoding (in the Attention)
  • 特筆すべき点として, この手法はGINGCN, それからGraphSAGEといったGNN手法を一般化したものとなっているらしい


Do Transformers Really Perform Bad for Graph Representation?

論文メモ

  • 構成要素1. Centrality Encoding
    • モチベーション
      • Node Centrality, つまりノードがどれほど別のノードとつながっているかはノードが如何に重要かを示しており, とても有益となり得るので, Encodeしたい
      • 例えばTwitterにおいて, 有名人はフォローが少なくてフォロワーが多い→ノードの次数は直感的にも重要
    • どうするの?
      • ノードの埋め込み表現 $h^{(0)}_i$について
        $$h ^{(0)}_i = x_i + z ^−_{deg^-_{(v_i)}} + z^+_{deg^+_{(v_i)}}$$
      • ただし, 入次数と出次数をそれぞれ, $deg^-, deg^+$とする
      • 最初だけ( $h^{(0)}_i$)なので計算コストもそれほどかからない
      • $z^-, z^+ \in \mathbb{R}^d$は学習可能パラメタとなっていて, Centralityの埋め込みを行う
      • ただし無向グラフなら, $deg^-, deg^+$を一つのパラメタ $deg$としても良い

  • 構成要素2. Spatial Encoding
    • モチベーション
      • Transformerの強さは受容野の広さだが, 一方でPositional Encodingが必要
      • どうにかGlobal-Attentionのまま位置情報を保存する形の写像がほしい
      • GNNは隣接ノードしか見ない(AGGREGATE)なので, GNNよりも広い受容野を獲得できる
    • どうするの?
      • ノード間の関係を $\phi(v_i,v_j)$と記述し, QueryとKeyの内積=Attentionを以下のように変更
        $$A_{ij} = \frac{(h_iW_Q)(h_jW_K)^\top}{\sqrt{d}} + b_\phi(v_i,v_j)$$
      • Attention自体を修正している点に注意
      • 本論文では $\phi(v_i,v_j)$を最短経路距離(SPD)とする
      • $b_\phi(v_i,v_j)$は学習可能パラメタ (スカラ)
      • これにより, Attentionを $\phi(\cdot)$で調整できる
      • 例えば $\phi(\cdot)$に対して $b_\phi$が単調減少ならば, より周囲にAttentionを掛ける=隣接周囲を注視するようになる

  • 構成要素3. Edge Encoding

    • モチベーション
      • エッジの情報はもちろん重要. たとえば分子の解析などではエッジに結合情報が存在する
      • なので, エッジ $e \in \mathcal{E}$の特徴量 $x_e$も埋め込みたい
    • どうするの?
      • 最短経路をエッジ情報として埋め込む
      • →最短経路パス $SP_{i,j} = (e_1,e_2,…,e_n)$について, Attentionに $c_{ij}$を追加
        $$A_{ij} = \frac{(h_iW_Q)(h_jW_K)^\top}{\sqrt{d}} + b_\phi(v_i,v_j) + c_{ij}$$
      • ただし, $x_{e_n}$を最短パス内のエッジ $e_n$における特徴量として
        $$c_{ij} = \frac{1}{N}\sum_{n=1}^N x_{e_n} (w^E_n ) ^\top$$
  • その他

    • CLSトークン的な感じでVNodeトークンを追加
      • こいつはノードでもあって, 全てのノードとつながっている超頂点を成す
    • 1-WL testで識別できないグラフでも, SPDを使えば識別可


Supplementary Material: https://openreview.net/attachment?id=OeWooOxFwDa&name=supplementary_material

共有

YuWd (Yuiga Wada)
著者
YuWd (Yuiga Wada)
機械学習・競プロ・iOS・Web