Graphormer: Do Transformers Really Perform Bad for Graph Representation?
https://gyazo.com/78a900d78ecdefbbad1d5b4c1609f9be
構成要素は三つ
Centrality Encoding
Spatial Encoding
構成要素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
モチベーション
どうにか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)
本論文では$ \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
その他
こいつはノードでもあって, 全てのノードとつながっている超頂点を成す https://gyazo.com/11ec95bb57389bdb5fc91269b5ff470f
結果
確かに表現力は上がってそう
https://gyazo.com/b1a6ede4b69767d62a10ceb6bdfa138e
Ablation
https://gyazo.com/9b13fa7232b12956a05c0c8f3167d9f4