はじめに

• NeurIPS22
  • Few-shotにおける knowledge graph completion task を行う
    • 上図のように, Background KG (knowledge graph)とsupport setが与えられた状態で, Query setのrelationを推論するタスク
  • Connection Subgraph Reasoner (CSR)を提案

Few-shot KG Completion

• KGは $\mathcal{G}=(\mathcal{E},\mathcal{R},\mathcal{T})$で表される

  • ここで, $\mathcal{E},\mathcal{R}$はそれぞれentityとrelationで, $\mathcal{T}$はtripletで $\mathcal{T}=(h,r,t)|h,t\in \mathcal{E},r\in \mathcal{R}$

• Few-shotknowledge graph completion taskとは

  • $r^{\prime }\notin \mathcal{R}$なような $r^{\prime }$について (=unseenなrelationについて)
  • support set $S_{r^{\prime }}={(h_k,r^{\prime },t_k)|h_k\in \mathcal{E}}_{k=1}^K$が与えられた状態で
  • $Q_{r^{\prime }}={(h_j,r^{\prime },?)|h_j\in \mathcal{E}}_{j=1}^J$の"?“に該当するentityを当てるタスク

Inductive Reasoning

• 以下のようなものをhypothesisと呼ぶ
  $$\mathrm{\exists }Z,(h_c,\text{can be done with},Z)\wedge (Z,\text{is located at},t_c)⟹(h_c,\bowtie ,t_c).$$

• 基本的には有効なhypothesisを探すことを目的とする

General Framework

• まずは一般化されたフレームワークを提案している
  • このフレームワークに則り,Learning-freeな方法(CSR-OPT)と学習可能な方法(CSR-GNN)の二つを提案している

1. Triplet Contextualization

• support setとクエリのTripletに対して, background KGからサブグラフを作成する
  • 具体的には, ノードからk-hopで到達しうるノードまでを使ってサブグラフを構成する
  • これにより知識グラフによって"contextualized"されたグラフを得ることができる

2. Hypothesis Proposal

• 一般にhypothesis proposal module と呼ばれる $M_p$を用いて, support setに対する全てのサブグラフに対してhypothesisを提案する
  • $M_p$はどのエッジを採用するかを示すsoft edge mask $m:[0,1{]}^E$を出力する
  • エッジを採用 = tripletを採用

$$\begin{array}{rl}{m_i}_{i=1}^K& =M_p(G(h_i,t_i)|(h_i,r^{\prime },t_i)\in S_{r^{\prime }})\\ b& =\frac{1}{K}\sum _{i=1}^K{M}_{enc}(G(h_i,t_i),m_i)\end{array}$$

• ただし, $M_p$は以下の式を満たす必要がある ( $s$はcosine類似度)
  $$\begin{array}{r}\arg max(\sum _{i=1}^K\sum _E{m}_i),s.t.\mathrm{\forall }i,j\in 1\dots K,\\ s(M_{enc}(G(h_i,t_i),m_i),M_{enc}(G(h_j,t_j),m_j))>1-ϵ\end{array}$$

3. Hypothesis Testing.

• 一般にevidence proposal module $M_e$と呼ばれる $M_e$を用いてhypothesisが正しいかどうかを検証する
  $$\begin{array}{rl}{m}_q& =M_e(b,G(h_q,t_q))\\ score& =s(b,M_{enc}(G(h_q,t_q),m_q))\end{array}$$

• ただし $M_e$は以下の式を満たす必要がある ( $s$はcosine類似度)
  $$s(M_{enc}(G(h_q,t_q),m_q),b)>1-ϵ$$

CSR-OPT (Learning-free)

• hypothesis proposal module $M_p$について, 以下の最適化問題を解く
  $$M_p(G(h_i,t_i)|(h_i,r^{\prime },t_i)\in S_{r^{\prime }})=\arg max\sum ({m_i}_{i=1}^K)-\lambda \ast H(m_q)$$
  $$\begin{array}{rl}s.t.\sum s(M_{enc}(G(h_i,t_i),m_i),M_{enc}(G(h_j,t_j),m_j))& >1-{ϵ}^{\prime },\\ \mathtt{\text{connectivity}}(m_i)& >1-{ϵ}^{\prime }\end{array}$$

  • ただし, $\mathtt{\text{connectivity}}$は $A$を隣接行列, $R_{i,j}=min((I+A+A^2)[i,j],1)$として, 以下の通り
    $$\mathtt{\text{connectivity}}(m_i)=\frac{1}{|E|}\sum _{e=(n,n^{\prime })\in E}{m}_{ie}\ast min(R_{n,h_i}+R_{n,t_i}+R_{n^{\prime },h_i}+R_{n^{\prime },h_i},1)$$
  • おそらく $k\mathtt{\text{-hop}},k\in [0,2]$なので $A^2$とか出てくる

Aが無向または有向グラフGの隣接行列とすると、行列An（すなわちAのn個の複製の積）は興味深い解釈を持つ: 要素(i, j)は頂点iから頂点jへの長さnの（有向または無向）歩道の数を与える。nが、あるi、jについてAnの要素(i, j)が正となるような最小の非負整数とすると、nは頂点iと頂点jとの間の距離である。
引用: Wikipedia ─ 隣接行列

• evidence proposal module $M_e$について, 以下の最適化問題を解く ( $H(\cdot )$は正則化項)
  $$T(b,G(h_q,t_q))=\arg maxs(b,M_{enc}(G(h_q,t_q),m_q))-\lambda \ast H(m_q)$$

  • $M_{enc}$はランダムなGNN (要検証)

CSR-GNN

• $f_{enc}(G_1,m_1):\mathcal{G}\times {\mathbb{R}}^{|\mathcal{E}|}\to {\mathbb{R}}^d$, $f_{dec}(G_2,b):\mathcal{G}\times {\mathbb{R}}^d\to {\mathbb{R}}^{|\mathcal{E}|}$として, それぞれを $M_p$, $M_e$とする
• $f_{dec}$にはPathConを使用
  • Relational Message Passing for Knowledge Graph Completion (KDD21)

• 学習方法

  • reconstruction loss とcontrastive lossを使用
    $$\begin{array}{rl}Los{s}_{recon}& ={\ell }_{\text{CE}}(m,f_{dec}(G,f_{enc}(G,m)))\\ Los{s}_{contrast}& =max(s(g_{pos},g)-s(g_{neg},g)+\gamma ,0)\end{array}$$

  • $g$に関して,

  • 同じrelationに対して異なるtripetをサンプリングしてきたものを $G,G^{\prime }$として正例と負例を作る

$$\begin{array}{rl}g& =M_{enc}(G,m)\\ g_{pos}& =M_{enc}(G,f_{dec}(G,f_{enc}(G,m)))\\ g_{neg}& =M_{enc}(G^{\prime },f_{dec}{G}^{\prime },f_{enc}(G,m))\end{array}$$

実際の推論例