グラフ構造を扱えるNNとして近年**グラフニューラルネット(GNN)**が熱い視線を集めています。GNNにはGCNやGATなどのヴァリアントがありますが、GCNやGATは一種類のノード、エッジのみの(= homogeneousな)グラフ構造を対象としています。
しかしグラフ構造で表せるものが全てhomogeneousなわけではありません。
例えば購買関係をグラフで表したい場合、少なくとも商品ノードと消費者ノードが必要ですよね。文書をグラフ構造で表すときも、単語ノード、文ノード、固有名詞ノードと区別した方がいい場合もあるかもしれません。論文の引用関係を表すときは論文ノードと著者ノードは区別されるべきです。
ビジネス的な応用といった面では、UberがDriver, Riderノードから成るグラフ構造のデータにRGCN1 を用いてFraud Detectionを行った2そうです。
このように、異なる種類のノード、エッジを含む(= heterogeneousな)グラフ構造は私たちの観察対象に遍在している構造です。
そんなheterogeneousなグラフ構造をGNN的に扱うための手法の一つが今回紹介するWang etal(2019)で提案されたHAN(Heterogeneous graph Attention Network)です。
本記事ではWang etal.(2019) 'Heterogeneous Graph Attention Network'をできるだけわかりやすく解説することを目指します。
この論文中で用いられている(そしてこの記事でも用いられている)Notationについてはこちらを参照ください。
本記事で使用されている画像は全てWang etal.(2019)からの転載です。
#準備
冒頭でも述べた通り今回扱うのはHeterogeneousなグラフ構造です。
図を元にそのheterogeneityを確認してみましょう。
例えば下記の図だと(b)のグラフにはActor, Movie, Directorの三種類のノードが存在していますね。
異なるノード同士の繋がりに着目してみると、ノード同士の関係性にも何種類かありそうです。
例えばMovieノード-Actorノード-Movieノードのつながりは'同じ俳優が二つの映画に登場している'ことを示す関係として、また映画ノード-監督ノード-映画ノードは'同じ監督による作品'ということを示す関係として解釈できます。
これらの「関係」を**メタパス(Meta-path)**と呼びます。
HANは異なるメタパスごとにノードの特徴量を集約(aggregate)することでグラフのHeterogeneityを反映した学習を可能にしたモデルです。
そのような学習はnode-levelとsemantic-levelという2ステップに分けられて行われます。
大まかな流れは下記の通りです。
ノードの特徴量をGNNの枠組みでメタパス近傍(後述)から計算(node-level)
↓
メタパスごとの重みを、そのメタパスに属するノードの特徴量を元に計算(semantic-level)
↓
メタパスの重みとノードの特徴量を掛け合わせるとグラフのHeterogeneityを反映したノードの特徴量が計算できる
Node-levelとSemantic-levelに分けて詳しく見ていきましょう。
#ノードの特徴量をGNNの枠組みでメタパス近傍から計算(Node-level)
(グラフ$ G = (V, E)$を想定しています。)
まずメタパス近傍(Meta-path based neighbors)とはなんぞや？というお気持ちかもしれません。
ノードiとノードjがメタパス近傍にあるとは、ノードiとノードjがメタパスを通じてつながっているということです。
先程の画像に戻って見ていきましょう。
この図の(d)にあるように、ノードm1はm2, m3, m4, m1とメタパス近傍にあります(m1自身も含まれている点に注意)
また、ノードa1はa1,a2,a3とメタパス近傍にありますね(a1-m1-a3, a1-m2-a2)。
さて、次はメタパス近傍を利用してどのようにノード特徴量を得ていくかを数式を元に追っていきましょう。
h_i' = M_{\phi_i} \cdot h_i
ここで$h_i$はノードiの特徴量、$h_i'$はノードiの射影された特徴量、$M_{\phi_i}$はタイプ固有変換行列(Type-specific transformation matrix)です。
なぜ変換行列をかけるかというと、異なる種類のノードの特徴量を同じ特徴量空間で扱うためですね。
次はノード間の重み$e^\phi_{ij}$を計算します。
つまり$ h_i' $にとっての$ h_j' $の重要性のようなものを計算するのですが、
異なるメタパスごとに両ノード間の重みは分けて計算したいので3メタパス$ \phi $で条件づけられた$ h_i' $と$ h_j' $の間の重みを計算します。
この重みの計算はself-atteitonを用いて次のように計算されます。
e^\phi_{ij} = att_{node}\left(h_i',h_j';\phi\right)
ここで$e^\phi_{ij}$は非対称な関係(e.g., $e^\phi_{ij} \neq e^\phi_{ji}$)であることに注意してください。
次に$e^\phi_{ij}$をsoftmaxで正規化します。
\alpha^\phi_{ij} = softmax(e^\phi_{ij}) = \frac{exp\left(\sigma\left(a^T_{\phi}\cdot [h_i' \mathbin\Vert h_j']\right)\right)}{\sum_{k \in N^\phi_{i}} exp\left(\sigma\left(a^T_{\phi}\cdot [h_i' \mathbin\Vert h_k']\right)\right)}
$a_{\phi}$はメタパスφのAttentionベクトル、σは活性化関数、$\mathbin\Vert$は連結(concatenate)オペレータ、$N^\phi_i$はノードiのメタパス近傍ノードの添字を表す集合です。
分母に$h_k' , s.t. , k \in N^\phi_{i}$ が出てきて、メタパス近傍ノードを考慮した正規化が行われている点がポイントですね。
そしてメタパス近傍のノードから以下のように埋め込み表現$z^\phi_i$を得ます。
z^\phi_i = \sigma(\sum_{j \in N^\phi_{I}} \alpha^\phi_{ij} \cdot h_j')
この学習は近傍から畳み込むというGNNの基本的な学習枠組みをメタパスで条件づけて行っているだけと見るとわかりやすいかと思います。
一応論文中ではMultihead attentionで計算しているので、ちゃんと書き直すと次の通りです。
z^\phi_i = \mathbin\Vert^K_{k=1} \sigma(\sum_{j \in N^\phi_{I}} \alpha^\phi_{ij} \cdot h_j')
そうするとメタパス $ {\phi_1, \phi_2, ..., \phi_P} $ごとにP個の埋め込み表現 $ Z_{\phi_1},..., Z_{\phi_P}$が得られます。
ここまではnode-levelの話でしたが、続くsemantic-levelではこの$ Z_{\phi_1},..., Z_{\phi_P}$を使ってメタパスの重みを計算します。
#メタパスの重みを計算(Semantic-level)
メタパス $ \phi_P $ の重み $ w_{\phi_P} $ は次のように計算されます。
w_{\phi_P} = \frac{1}{|V|}\sum_{i \in V}q^T \cdot tanh(W \cdot z^{\phi_P}_i + b)
ここで$W$は重み行列、$b$はバイアスベクトル、$q$はsemantic-levelのattentionベクトルです。
node-levelの埋め込みを計算するときもattentionベクトルを用いましたがここではsemantic-levelの埋め込み表現を得るために別のattentionベクトルを用意してきます。
node-levelの時と同じようにsoftmaxで正規化します。
\beta_{\phi_P} = \frac{exp(w_{\phi_P})}{\sum_{p=1}^P exp(w_{\phi_p})}
メタパスレベルで正規化しているのがポイントですね。
さて、ここまででメタパスごとにその重み($\beta_{\phi_P}$)とそのメタパスに属するノードの埋め込み表現($Z_{\phi_p}$)を得ることができました。
そのため、最終的な埋め込み表現は次のように計算されます。
Z = \sum_{p=1}^P \beta_{\phi_P} \cdot Z_{\phi_p}
それぞれのメタパスごとにメタパスの重みとノードの特徴量を掛け合わせ、それらを全て足した特徴量がそのノードの特徴量、という計算ですね。
今までのプロセスを図で表すと次のようになります。
最終的なノードの埋め込み表現が得られたらそれを損失関数とともにノード分類などの特定のタスクに利用することができます。
ここまでがHANの学習構造です。実験セクションについては後々追記すると思います(多分、メイビー)
#終わりに
以上から、HANの特徴は
(i)メタパスbasedであること、
(ii)階層的なAttention構造(node level-semantic level)を用いていること
にあると見ることができそうです。
今回はHeterogeneousなグラフを扱う手法の一つとして有名なHANを紹介しましたが、HAN以外にも冒頭の例で挙げたRGCNなどのヴァリアントがあります。
Heterogeneousなグラフの埋め込み手法について包括的に知りたい方はこちらのサーベイがおすすめです。