# 知識グラフエンベディングのためのリレーションパスルールに よるトランスダクティブデータ拡張

廣瀬雄士 ${ }^{1}$ 新保仁 ${ }^{2}$ 渡辺太郎 ${ }^{1}$
1 奈良先端科学技術大学院大学 先端科学技術研究科, 2 千葉工業大学人工知能・ソフト
ウェア技術研究センター
hirose.yushi.hx4@is.naist.jp, shimbo@stair. center, taro@is.naist.jp

## 1 はじめに

実世界の情報をデータ化する手法として知識グ ラフが知られている．知識グラフはエンティティを 頂点とし，リレーションを辺のラベルとする有向 グラフである．辺を表すへッドエンティティ，リ レーション, テールエンティティの三つ組 $\left(e_{h}, r, e_{t}\right)$ は，トリプレットと呼ばれ，知識グラフはトリプ レットの集合ともみなせる. 知識グラフの例とし て, YAGO [1], Freebase [2], WordNet [3]があり, Q \& $\mathrm{A}[4]$ ，エンティティリンキング [5] などの自然言語処理タスクで用いられている。

通常，知識グラフは実世界の全てのトリプレッ トが記述されているわけではない. 久損したトリ プレットを予測するタスクを，知識グラフ補完 と呼び，主要な手法として，エンベディングモデ ル [6], [7], [8] とリレーションパスルールモデル [9] が研究されてきた. エンベディングモデルは既知の 知識グラフからエンティティ, リレーションの特徵 ベクトルを学習し, それらの間の演算により得られ るスコアによって欠損したトリプレットの真理値を 予測する．リレーションパスルールモデルは，知識 グラフ上のエンティティ間のリレーション系列 (リ レーションパス)を一階述語論理的なルールと考え て，欠損トリプレットの真理值を予測するモデルで ある。

両者には長所と短所がある. エンベディングモデ ルは，知識グラフ全体から特徴を学習できるが，知識グラフの経路情報のモデル化が明示的に行われて いない.リレーションパスルールモデルは，ルール を用いているので偽陽性が少ないが，エンティティ 間にリレーション系列が存在しなければそのトリプ レットを予測することはできない.

本研究では両者の長所を活かすように，リレー
ションパスルールによって予測されたトリプレット を訓練データに追加し，その拡張データを用いてエ ンベディングモデルの学習を行う。データの拡張は トランスダクティブ学習 [10] の設定で行う．これに よりクエリの予測に有益なデータを拡張することで 精度の向上が期待できる.

データセットとしてWN18RR，FB15k-237を用い，通常のデータを用いてエンベディングモデルを学習 させた場合と比較すると，拡張データを用いた場合 の方が予測精度が良い結果が得られた。通常の知識 グラフ補完のためにトランスダクティブ学習の設定 を用い，予測精度への効果を調べたのは，私の知る 限り本研究が初めてである。

## 2 背景

知識グラフ補完は, テストクエリ $\left(e_{h}, r, ?\right),\left(?, r, e_{t}\right)$ が与えられた時，?に入る真のエンティティが，エ ンティティ集合 $E$ の中で何番目に真である可能性が 高いかを予測するタスクとしてょく定式化される.本研究も同様なタスクを考える。

## 2.1 エンベディングモデル

エンベディングモデルはエンティティとリレー ションの特徴べクトルを用いた演算によってトリ プレットのスコアが定義されるモデルであり，その 值が大きいトリプレットほど，真である可能性が 高いと考える. 各特徴べクトルは, 通常確率的勾配降下法によって学習される. 初期モデルとして RESCAL [6] が知られており, 近年精度が高いモデ ルとして TuckER [8] が知られている. 各モデルのス コア関数 $f_{\mathrm{RESCAL}}$ および $f_{\text {TuckER }}$ は以下のように表さ れる。

$
\begin{gathered}
f_{\mathrm{RESCAL}}\left(e_{h}, r, e_{t}\right)=\mathbf{e}_{h}^{\top} \mathbf{R} \mathbf{e}_{t} \\
f_{\text {TuckER }}\left(e_{h}, r, e_{t}\right)=\mathbf{W} \times{ }_{1} \mathbf{e}_{h} \times{ }_{2} \mathbf{r} \times{ }_{3} \mathbf{e}_{t}
\end{gathered}
$

ここで $\mathbf{e}_{h}, \mathbf{e}_{t}, \mathbf{r}, \mathbf{R}, \mathbf{W}$ はそれぞれ学習されるパラメー タを示し，順にへッド，テールエンティティ，リ レーションのエンベディングベクトル，リレーショ ン行列, 全トリプレット共通のコアテンソルを表 す. $\times_{n}$ はテンソルの n-mode 積を表す.

## 2.2 リレーションパスルール

リレーションの系列をリレーションパスと呼 ぶ. すなわち $r_{1}, \ldots, r_{n}$ が $n$ 個のリレーションで あるとき, path $h_{i}:=\left(r_{1}, \ldots, r_{n}\right)$ は長さ $n$ のリレー ションパスである. また, $\left(e_{1}, r_{1}, e_{2}\right),\left(e_{2}, r_{2}, e_{3}\right), \ldots$, $\left(e_{n}, r_{n}, e_{n+1}\right)$ が知識グラフ中のトリプレットである とき, $e_{1}$ と $e_{n+1}$ の間に $p a t h_{i}$ が存在する, といい, $\operatorname{path}_{i}\left(e_{1}, e_{n+1}\right)$ と書く.

リレーションパスを用いた予測の例としてクエ リ (Bob, nationality, ?) を考える. (Bob, bornIn, NYC), (NYC, isCityOf, USA) が知識グラフ上で既知なら， Bob,USA の間に (bornIn, isCityOf) というリレーショ ンパスが存在することを用いて，USA がクエリの 真のエンティティに含まれると予測することがで きる.

リレーションパス path $_{i}=\left(r_{1}, r_{2}, \ldots, r_{n}\right)$ を用いて リレーション $r$ を予測するとき，述語論理を用いて 次のようなルールとしてみることもできる.

$
\begin{aligned}
\exists e_{1}, e_{2}, \ldots e_{n+1} & :\left(e_{1}, r_{1}, e_{2}\right) \wedge\left(e_{2}, r_{2}, e_{3}\right) \wedge \ldots \\
& \wedge\left(e_{n}, r_{n}, e_{n+1}\right) \rightarrow\left(e_{1}, r, e_{n+1}\right)
\end{aligned}
$

ルールの尤もらしさは, 先行研究 [11] の Partial Completeness Assumption（PCA）という仮定に基づ くと，式のような確信度スコアで示される. 式はリ レーション $r$ の予測に用いる path $h_{i}$ の確信度スコア を表し,$e_{t}^{\prime}$ は知識グラフ上のいずれかのエンティ ティを表す.

$\operatorname{Conf}_{\mathrm{PCA}}\left(\right.$ path $\left._{i}\right)=\frac{\left|\left.\{\left(e_{h}, e_{t}\right) \mid \operatorname{path}_{i}\left(e_{h}, e_{t}\right) \wedge\left(e_{h}, r, e_{t}\right)\right.\}\right|}{\left|\left.\{\left(e_{h}, e_{t}\right) \mid \operatorname{path}_{i}\left(e_{h}, e_{t}\right) \wedge\left(e_{h}, r, e_{t}^{\prime}\right)\right.\}\right|}$

## 2.3 データ拡張による知識グラフ補完

リレーションパスルールを用いてデータ拡張を行 い，エンベディングモデルの学習に用いるモデルに は UniKER [12] が存在する. この手法により, エン ベディングモデルの精度は大きく向上するが，デー 夕拡張のために様々な手法が必要である. 例えば，拡張するトリプレットをうまく見つけるために， “forward chaining" やパスの補完などがある. またこ の手法ではエンベディングスコアもデータ拡張のた
めの情報として用いている. そしてエンベディング の学習 よるエンベディングの学習，というように繰り返し エンベディングモデルを学習する必要がある.

## 3 トランスダクティブ学習設定によ るデータ拡張

トランスダクティブ学習設定では，テストクエ リ $\left(e_{h}, r\right.$, ? )が学習時に既知であると考える. このた め、テスト時にあらゆるクエリを想定しないといけ ない通常の知識グラフ補完タスクよりは容易な問題設定になっている. しかし, 現実的には予測したい クエリがあらかじめ分かっていて，その予測精度を 向上することの方が求められることも考えられる.

本手法ではテストデータのクエリ $\left(e_{h}, r, ?\right)$ が与え られたとき，テールとして該当しそうなエンティ

トリプレット $\left(e_{h}, r, e_{t}^{\prime}\right)$ を訓練データに追加する. そうすることでクエリの答えであるテールエンティ ティか，それと似た特徴を持つテールエンティティ を訓練データに追加することが期待できる。その 後，拡張データを用いてエンベディングモデルを訓練し，テストの評価に用いる. 拡張データで学習さ れたエンベディングモデルを拡張データモデルと呼 ぶこととする.

## 3.1 リレーションパスルールのマイニング

リレーションパスルールは先行研究 [13] の手法 に倣って双方向ランダムウォークによって取得す る.トリプレット $\left(e_{h}, r, e_{t}\right)$ について考える.この マイニング手法では $, e_{h}, e_{t}$ それぞれを始点とした グラフ上のランダムウォークが行われ，ウォークし たお互いの終点が同じエンティティだった場合に， リレーション $\mathrm{r}$ の予測に用いられるパスが取得さ れる。

各リレーションに対して, マイニングされた パスのうち，確信度スコアがトップ $\mathrm{N}$ 個のパス path $_{i=1 \ldots N}^{r}$ を用いてデータ拡張を行う. テストデー タの各クエリ $\left(e_{h}, r\right.$, ? に対して, 全テールエンティ ティ $e_{t}^{\prime} \in E$ を用いて,$e_{h}$ と $e_{t}^{\prime}$ の間に各 path $_{i=1 \ldots N}^{r}$ が存在するかを調べる. 存在するパスの中で, 式 4 の確信度スコアが最も大きいものを $\left(e_{h}, r, e_{t}^{\prime}\right)$ のパ ススコアとし, 各クエリのパススコアが大きいトリ プレットを訓練データに追加する. このとき top $S$ と confThold という閾値を導入する. 各クエリに 対して，最初の訓練データを含めて多くとも top $S$
表 1 知識グラフの各データセット統計情報

$E, R$ はエンティティ，リレーションの集合を表す.

個までのトリプレットを訓練データに追加する。ま た scoreThold より小さいパススコアを持つトリプ レットは訓練データに追加しないようにする。

## 4 実験

## 4.1 実験設定

データセットには WN18RR [14] と FB15k-237 [15] を用いた。データセットの統計情報は表 1 に示す。

データ拡張には各リレーションで確信度スコア トップ 1000 までのパスを用いる.またハイパーパ ラメータを検証用データで調整するために，テスト データだけでなく検証用データもデータ拡張のた めのクエリとして用いた. エンベディングモデルに は RESCAL,TuckERを用い，そのハイパーパラメー タ等の值は付録に示す。ハイパーパラメータの探索範囲は，ベースモデルと拡張データモデルで等し く，検証用データの MRR が最大になるようグリッ ドサーチする.

また各データ $\left(e_{h}, r, e_{t}\right)$ に対して逆リレーション $r^{-1}$ を用いた $\left(e_{t}, r^{-1}, e_{h}\right)$ を追加する. そして学習と 評価は各トリプレットのテールエンティティを予測 する手法を用いる [16].

## 4.1.1 損失関数

損失関数には KvsAll [17] という負例の取り方と，二値交差エントロピー損失を用いる。このときミニ バッチ内の一つの訓練事例は $\left(e_{h}, r\right)$ となり，このぺ アに対する損失関数は以下のように表される.

$
\begin{aligned}
L= & -\frac{1}{|E|} \sum_{e^{\prime} \in E}^{|E|}\left(\mathbf{y}_{e^{\prime}} \log \sigma\left(f\left(e_{h}, r, e^{\prime}\right)\right)+\right. \\
& \left.\left(1-\mathbf{y}_{e^{\prime}}\right) \log \left(1-\sigma\left(f\left(e_{h}, r, e^{\prime}\right)\right)\right)\right)
\end{aligned}
$

ここで $\mathbf{y}_{e^{\prime}}$ は，トリプレット $\left(e_{h}, r, e^{\prime}\right)$ が訓練デー タに含まれるなら 1 ，それ以外は 0 となるラベルを 表し， $f$ は学習に用いるスコア関数， $\sigma$ は活性化関数であるシグモイド関数を表す。

## 4.2 実験結果

ベースモデルと拡張データモデルによるテスト クエリの予測結果を表 2 に示す. MRR は予測され表 2 拡張データモデルの実験結果

た真のエンティティのランクの逆数の平均を表し， Hits@ $K$ は真のエンティティのランクが $K$ 位内であ るテストクエリの割合を表す。

## 5 分析・考察

## 5.1 予測精度に関する考察

表 2 の実駼結果から，拡張データがエンベディン グモデルの精度を向上させることがわかる. また， FB15k-237 で拡張データモデルがベースモデルに対 してあまり精度の改善が見られなかった原因の一つ に，適切なハイパーパラメータを設定できなかった 可能性が考えられる。拡張データによって訓練デー タの数が変化するので，最適なエンベディングの次元やドロップアウトの值が変化したと思われる.

## 5.2 予測結果の違いに関する分析

一つのテストデータに対して，そのクエリによっ て生成される拡張データを，そのテストデータの拡張データと呼ぶことにする。

拡張データに真またはそれに類似したテールエン ティティを含んだ結果，予測が改善されたのか分析 する. ベースモデル・拡張データモデルによって予測される各検証用データのランクを調べ，それぞれ のモデルで 10 位以内かそれ未満で予測されたデー 夕数と，その内拡張データを持つもの，拡張データ に含まれるものを示したのが，表 3,4 である。 エン ベディングモデルには RESCALを用いた.

まず WN18RR について表 3 のデータをみる。拡張データに含まれる検証用データは全て，拡張デー タモデルで 10 位以内に予測できている。そのうち 93 個はベースモデルでは 10 位以内に予測できな かったもので，拡張データモデルの予測精度が向上 に寄与している。

FB15k-237 も WN18RR と同じような傾向が見られ るが，拡張データモデルによって新たに 10 位内に 予測できるようになったトリプレットの数が，予測 できなくなった数と同じくらい存在する.

両方のデータセットで拡張データを持つ検証用
表 3 各モデルによる検証用データの予測ランク比較（WN18RR）

表 4 各モデルによる検証用データの予測ランク比較（FB15k-237）

表中の “have 拡張データ” は拡張データを持つ検証用データ，“in 拡張データ” は拡張データに含まれる検証用データを 示す.

データのうち，そのデータ自身が拡張データに含ま れなくても精度が上昇したものが存在する. この原因が，拡張データにクエリの真のテールエンティ ティに類似したエンティティを含んだためかどうか 次の節で確かめる。

## 5.3 エンベディングコサイン類似度比較

以下のように検証用データと拡張データのテー ルエンティティのエンベディングコサイン類似度 を分析した．検証用データ $\left(e_{h}, r, e_{t}\right)$ の拡張データ のテールエンティティの集合を $D\left(e_{h}, r\right)$ とする. $D\left(e_{h}, r\right)$ の各テールエンティティ $e_{t}^{\prime}$ 対して,$E$ 中 の全エンティティとのエンベディングのコサイン類似度を求める. 各 $e_{t}^{\prime}$ について $e_{t}^{\prime}$ と $e_{t}$ のコサイン類似度が $E$ 中で何番目か求める. 各 $e_{t}^{\prime}$ と $e_{t}$ のコサイ ン類似度ランクの中で最も小さいものを，D $\left(e_{h}, r\right)$ と $e_{t}$ との最小コサイン類似度ランクとする.

検証用データで拡張データに含まれない，かつ拡張データ持ち検証用データのうち，以下 3 タイプの データを比較のために取り出す.

・タイプ 1：10 位以内の予測精度が向上したデー タ（予測ランクがベースモデルで 10 位未満か つ拡張データモデルで 10 位以内のデータ)

・タイプ 2：10 位以内の予測精度が悪化したデー タ（予測ランクがベースモデルで 10 位以内か つ拡張データモデルで 10 位未満のデータ)

・タイプ 3：10 位以内に変わらず予測できてい ないデータ（予測ランクがベースモデル，拡張 データモデル共に 10 位未満のデータ)

各タイプに含まれる検証用データそれぞれについ て，その拡張データのテールエンティティとの最小 コサイン類似度ランクを求める. その後各タイプご表 53 タイプの検証用データの最小コサイン類似度

とに，検証用データの最小コサイン類似度ランクの MRR を求める. このようにして求められた 3 タイ プの MRRを，各タイプに含まれる検証用データ数 と共に表 5 に示す.

両データセット共にタイプ 1 が最も最小コサイン 類似度 MRR が高く，類似したエンティティの拡張 データの学習が，拡張データモデルの精度向上に寄与したと考えられる。

## 6 おわりに

トランスダクティブ設定の下で，リレーションパ スによるデータ拡張を行い，エンベディングモデル の学習と予測を行った. 予測結果は拡張データなし の場合を上回り，分析の結果，多くの場合トランス ダクティブ学習の設定がより良いデータの拡張に つながることがわかった. また本手法は他のエンベ ディングモデルへの応用も期待できる。

トランスダクティブではなく，通常の設定でのリ レーションパスルールによるデータ拡張は今後の課題とする。

## 参考文献

[1] Fabian M Suchanek, Gjergji Kasneci, and Gerhard Weikum. Yago: a core of semantic knowledge. In Proceedings of the 16th international conference on World Wide Web, pp. 697-706, 2007.

[2] Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. Freebase: a collaboratively created
graph database for structuring human knowledge. In Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pp. 1247-1250, 2008.

[3] George A. Miller. Wordnet: A lexical database for english. Coтmun. ACM, Vol.38, No. 11, p.39-41, November 1995.

[4] Xiao Huang, Jingyuan Zhang, Dingcheng Li, and Ping Li. Knowledge graph embedding based question answering. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, WSDM '19, p. 105-113, New York, NY, USA, 2019. Association for Computing Machinery.

[5] Deep semantic match model for entity linking using knowledge graph and text. Procedia Computer Science, Vol. 129, pp. 110 - 114, 2018.

[6] Maximilian Nickel, Volker Tresp, and Hans-Peter Kriegel. A three-way model for collective learning on multirelational data. In Icml, Vol. 11, pp. 809-816, 2011.

[7] Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. Complex embeddings for simple link prediction. International Conference on Machine Learning (ICML), 2016.

[8] Ivana Balažević, Carl Allen, and Timothy M Hospedales. Tucker: Tensor factorization for knowledge graph completion. In Empirical Methods in Natural Language Processing, 2019.

[9] Christian Meilicke, Manuel Fink, Yanjie Wang, Daniel Ruffinelli, Rainer Gemulla, and Heiner Stuckenschmidt. Fine-grained evaluation of rule-and embedding-based systems for knowledge graph completion. In International Semantic Web Conference, pp. 3-20. Springer, 2018.

[10] A. Gammerman, V. Vovk, and V. Vapnik. Learning by transduction. In Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence, UAI'98, p. 148-155, San Francisco, CA, USA, 1998. Morgan Kaufmann Publishers Inc.

[11] Luis Galárraga, Christina Teflioudi, Katja Hose, and Fabian M Suchanek. Fast rule mining in ontological knowledge bases with amie+. The VLDB Journal, Vol. 24, No. 6, pp. 707-730, 2015.

[12] Ke wei Cheng, Ziqing Yang, Ming Zhang, and Y. Sun. Uniker: A unified framework for combining embedding and horn rules for knowledge graph inference. In ICML Workshop on Graph Representation Learning and Beyond, 2020.

[13] Matt Gardner and Tom Mitchell. Efficient and expressive knowledge base completion using subgraph feature extraction. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pp. 1488-1498, Lisbon, Portugal, September 2015. Association for Computational Linguistics.

[14] Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 2d knowledge graph embeddings, 2018.

[15] Kristina Toutanova and Danqi Chen. Observed versus latent features for knowledge base and text inference. In Proceedings of the 3rd Workshop on Continuous Vector Space Models and their Compositionality, pp. 57-66, Beijing, China, July 2015. Association for Computational Linguistics.
[16] Timothee Lacroix, Nicolas Usunier, and Guillaume Obozinski. Canonical tensor decomposition for knowledge base completion. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, Vol. 80 of Proceedings of Machine Learning Research, pp. 2863-2872, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR.

[17] Daniel Ruffinelli, Samuel Broscheit, and Rainer Gemulla. You CAN teach an old dog new tricks! on training knowledge graph embeddings. In International Conference on Learning Representations, 2020.

[18] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.

[19] Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 249-256, 2010.

## A 付録

## A. 1 マイニングされたパス数

本研究で用いたマイニングされたパスの各リレーションごとの平均数・標準偏差を表に示す.

表 6 マイニングされたパス数

## A. 2 エンベディングモデル実験設定とハイパーパラメータ

エンベディングモデル実験設定とハイパーパラメータの值を表 7 に示す。表中の \{\} 内の值は探索に用いた 值である.

表 7 エンベディングモデルのハイパーパラメータ

## A. 3 データ拡張の域値

データ拡張の域値 topS, scoreThold は, WN18RR で topS $=5$, scoreThold $=0.1, \mathrm{FB} 15 \mathrm{k}-237$ で top $S=$ 5, scoreThold $=0.6$ を用いた.
 廣瀬雄士 ${ }^{1}$ 新保仁 ${ }^{2}$ 渡辺太郎 ${ }^{1}$ 1 奈良先端科学技術大学院大学 先端科学技術研究科, 2 千葉工業大学人工知能・ソフト ウェア技術研究センター hirose.yushi.hx4@is.naist.jp, shimbo@stair. center, taro@is.naist.jp  