Triple2Vec のバックアップ(No.8)

提案論文

定義等

  • 知識グラフ：\( G=(V_G,E_G,T_G) \)
    • \( V_G \)：エンティティ（頂点）の集合
    • \( E_G \)：述語の集合
    • \( T_G \)：トリプルの集合
  • \( G=(V_G,E_G) \)：無向グラフ (undirected graph)または有向グラフ (directed graph)
  • \( \mathcal{G}_L=(V_L,E_L) \)：線グラフ (line graph)
    • \( G \)のエッジを\( \mathcal{G}_L \)のノードにする
    • \( G \)のエッジが共通のノードを持つとき、\( \mathcal{G}_L \)の2頂点は隣接する
    • \( G \)が有向のとき\( \mathcal{G}_L \)も有向。

既存Line Graph の問題点

知識グラフからの線グラフ構築の問題点

  1. 意味が抜け落ちる
    • 主語と述語を共有するトリプルについて、述語が違っても全く同じようなノードができることがある。
  2. 孤立ノードができる
    • エンティティが主語と述語両方にならないと、（つまり、主語のみ、述語のみの状態だと）孤立グラフになる。

Triple2Vecの手法

  1. Triple Line Graph の作成
  2. エッジの重みを計算する
  3. 重み付き Triple Line Graph のランダムウォーク
  4. Skip-gram を利用したエンベッディングを行う

Triple Line Graph

  • Triple Line Graph の動機
    • KB上で距離2で接続されているノード同士ならば、そのエッジの方向性・意味に関わらず、変換後のグラフでも接続されるべきだ。
    • トリプル間の関係を、述語に基づいて何かの形で保持することが望ましい。
  • Triple Line Graphの定義
    • \( \mathcal{G}_L=(V_L,R_L,w) \)
    1. ノードは\( G \)のトリプルに対応
    2. \( \mathcal{G}_L \)の2つのノード\( s_1,p_1,o_1 \)と\( s_2,p_2,o_2 \)は、\( \{s_1,o_1\}\cap\{s_2,o_2\}\neq\emptyset \)のとき接続
      • つまり、主語同士・目的語同士もしくは主語・目的語間に同じものがあれば接続。
    3. 関数\( w \)は値域\( [0,1] \)で、全てのエッジに重みづけをする。
  • Triple Line Graphの特徴
    • メリット
      • 知識グラフ上で連結していれば、 Triple Line Graph 上でも連結している。
    • デメリット
      • エッジ数が多くランダムウォークの計算に影響を与える

Triple Line Graph の重みづけ

  • TF-ITF計算
    • トリプル頻度(TF)
      • \( TF(p_i,p_j)=\log(1+C_{i,j}) \)
        ただし\( C_{i,j} \)は、述語\( p_i,p_j \)が同じ主語・目的語で接続される回数
    • 逆トリプル頻度 (ITF)
      • \( ITF(p_j,E)=\log\frac{|E|}{|{p_i:C_{i,j}>0}|} \)
    • (symmetric) matrix
      • \( C_M(i,j) = TF(p_i,p_j)\times ITF(p_j,E) \)
    • 述語関連行列
      • \( M_R(p_i,p_j)=Cosine(W_i,W_j) \)
        ただし\( W_i \)は\( C_M \)の\( p_i \)の行
    • トリプル間に関連する述語が多いほど重みが高い
    • メリット
      • トリプル間の関連性と意味の近さの両方をとらえることができる。

ベクトル化の方法

  • \( p((e_{v_{i},e_{v_{i+1}}}) \in \mathcal{W})=\sigma(e^T_{v_i},e_{v_{}i+1}) \)
    • \( \sigma \)はソフトマックス関数
  • ネガティブサンプリング
    • \( p((e_{v_{i},e_{v_{i+1}}}) \notin \mathcal{W})=\sigma(-e^T_{v_i},e_{v_{i+1}}) \)
  • \( \mathcal{O}(\theta)=\log(e^T_{v_i},e_{v_{i+1}})+\sum_{j=1}^k \mathbb{E}_{v_j}[\log\sigma(-e^T_{v_i},e_{v_{i+1}})] \)
    • \( \theta \)全パラメータ
    • \( k \)ネガティブサンプリングの数
    • 並列非同期確率的勾配降下法を利用

実験

比較手法

metapath2vec, node2vec, DeepWalkの利用
エンティティをベクトルにする手法。
トリプル中の2つのエンティティベクトルの平均を利用。
ConvE, RotatE
pykg2vecの実装を利用
トリプル中の2つのエンティティベクトルと述語ベクトルの結合

利用したKB

  • DBLP
  • Foursquare
  • Yago

適用された問題

トリプル分類
推薦機能