JavaScriptを有効にしてください

【論文メモ】TokenGT: Pure Transformers are Powerful Graph Learners

 ·  ☕ 2 min read


  • グラフをそのままTransformerにブチこむ手法

  • GNNより帰納バイアスが少ないが, GNNよりも良い精度を達成

  • 入力について

    • まず, ノードとエッジをそれぞれ独立なものとして捉え, それぞれを同等にトークン Xとする
    • そのトークンに, ノードなのかエッジなのかを判別するType Identifiersをconcatして入力
  • トークン Xについて

    • トークンには直交行列 Pを用いる
      • なんで直交?→後述
    • ノード vVについては, X[Xu,Pv,Pv]
    • エッジ (u,v)Eについては, X[X(u,v),Pu,Pv]
      • こうすれば, Attentionの内積計算でe=1, 0 (繋がり)を表現でき, グラフ構造を扱える
      • 例えば
        • ノード kVがエッジ e:=(u,v)Eにつながってるなら
        • [Pu,Pv][Pk,Pk]=1になるし, そうでないなら0になる
        • ( k=uor k=vPは直交行列)
  • 直交行列 Pについて→どうやって Pを得るの?

    • 方法は2つ提案されている
    • 1つ目: ORF (Orthogonal Random Features)
      • 正規分布からランダムにサンプリングした行列 GQR分解
      • ほとんどランダムに近いので, トークン情報しかモデルは扱えない
      • にも拘らず, 結構いい精度出たらしい
    • 2つ目: ラプラシアン行列の固有ベクトルを用いる (固有値分解)
      • ラプラシアン行列の固有ベクトルはグラフにおけるPositional Encodingとある種同等なので, モデルにとっては有益
      • ORFより良い精度が出たらしい
  • このあたりのデータセットの知見ないから結果みても何ともいえんな…


共有

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