# 知識グラフ補完のためのモデル予測に基づくサブサンプリング

Xincan Feng ${ }^{1}$ 上垣外英剛 ${ }^{1}$ 林克彦 $^{2}$ 渡辺太郎 ${ }^{1}$
1 奈良先端科学技術大学院大学 2 北海道大学
\{feng.xincan.fy2, kamigaito.h, taro\}@is.naist.jp katsuhiko-h@ist.hokudai.ac.jp

## 概要

知識グラフの埋め込み (KGE) において，サブサン プリングは知識グラフ (KG) データセットの疎性に より生じる過学習を減少させる効果がある. しか し，現在のサブサンプリングは，エンティティとそ の関係からなるクエリの頻度を考慮するだけである ため，頻度の少ないクエリに含まれるエンティティ や関係の頻度が高い場合，そのようなクエリの出現確率を低く見積もる可能性がある。この問題を解決 するために，KGE モデルの予測を利用することで クエリの出現確率を推定する，モデルに基づくサブ サンプリング (MBS) および混合サブサンプリング (MIX) を提案する．FB15k-237 および WN18RRでの 評価を行った結果，提案法であるサブサンプリング は代表的な KGE モデルである ComplEx, RotatE, お よび HAKE において知識グラフの補完性能が改善 されることを示した。

## 1 はじめに

知識グラフ $(\mathrm{KG})$ とは，エンティティとその関係 を枝として含むグラフである．知識グラフは，対話 [1], 質問応答 [2], 自然言語生成 [3] などの様々な自然言語処理タスクにおいて重要なリソースとして利用されている. しかし，KG 内のエンティティの関係を人手で全て網羅するには多くのコストがかか る. 知識グラフ補完 (KGC) は，知識グラフ中の関係 を基に，含まれていない関係を自動的に補完するこ とでこの問題を解決することができる. $e_{i}$ と $e_{k}$ を エンティティ,$r_{j}$ をそれらの関係とすると，KGCは $\left(e_{i}, r_{j}, ?\right)$ や $\left(?, r_{j}, e_{k}\right)$ などのクエリに対して?を埋 めて回答することにより枝の存在を予測する.

現在，KGC では知識グラフの埋め込み (KGE) を 用いる手法が主流である. KGE はエンティティと その関係を連続べクトルとして表現する. このべク トルの数は $\mathrm{KG}$ 内の枝の数に比例して増加するた め，KGE では学習時の計算量を減らすためにネガ

図 1 FB15k-237 と WN18RR の学習データにおいて，一度だけしか出現しないクエリに含まれるエンティティと 関係が持つ出現頻度 ${ }^{1)}$ 。

ティブサンプリング (NS)を用いることが一般的で ある. NS では，KGE モデルが KG 内の枝からサン プリングして作成された偽の枝と真の枝とを識別す ることで KG を学習する. NS は計算量を削減でき る一方で，サンプリングされた枝は元の KG の偏り を反映してしまうという問題がある。

その解決策として，KGEのNS に対し，サブサン プリング法 [4] が導入された [5]. サブサンプリング は, 頻度の高い枝の頻度を減らし, 頻度の低い枝の 頻度を増やすことで，KGの偏りを緩和する。

しかし，KGEにおける現在のサブサンプリング は，クエリの頻度のみを考慮する．そのため，出現頻度の低いクエリに含まれるエンティティや関係 の出現頻度が高い場合に，そのようなクエリの出現確率を過小評価する可能性がある. 図 1 は, 学習 データに 1 回だけ出現したクエリに含まれるエン ティティと関係の出現頻度を示している.この結果 から，現在のカウントに基づくサブサンプリング (CBS) では，出現頻度の低いクエリに含まれるエン ティティや関係の出現頻度が十分であるにもかかわ らず有効に利用されていない。

この問題に対処するため，我々はモデルに基づく サブサンプリング (MBS) と混合分布に基づくサブ サンプリング (MIX)を提案し，KGE モデルの予測結果に基づいてクエリの出現確率を推定することでこ のような頻度の低いクエリに対処する。

本稿では，一般的に使用されている KGE モデル ComplEx [6], RotatE [5], HAKE [7] に我々の MBS と MIXを適用し, FB15k-237 [8] と WN18RR [9] データ セットを用いた評価を害施した。評価の結果，MBS と MIX はそれぞれの設定において，KGC の評価尺度であるMRR，Hits@1，Hits@3，Hits@10において がベースラインである CBS よりも高いスコアを達成可能であることが分かった.

## 2 KGE に適したサブサンプリング

## 2.1 KGE の定式化

本稿ではエンティティ $h$ と $t$ とその関係 $r$ を表す 枝(トリプレット)を $(h, r, t)$ と表記する．KGCでは クエリ $(h, r, ?)$ や $(?, r, t)$ が与えられ, モデルは? に対応するエンティティを予測する。 入力されたクエリ を $x$ ，予測すべきエンティティを $y$ とすると，モデル パラメータ $\theta$ に基づくスコア関数 $s_{\theta}(x, y)$ は $x$ から $y$ が予測される確率 $p_{\theta}(y \mid x)$ を計算する。一般的には， $|D|$ 個の枝を用いて,$p_{\theta}(y \mid x)$ を予測することで， $\theta$ を学習させる. ここで $D=\left.\{\left(x_{1}, y_{1}\right), \cdots,\left(x_{|D|}, y_{|D|}\right)\right.\}$ は $p_{d}(x, y)$ に従う観測データとする.

## 2.2 NS におけるサブサンプリング

計算効率の高さから NS は KGE モデルの学習によ く使われる。近年，Kamigaito ら [10] は KGE の NS において使用されている様々なサブサンプリングを 説明可能な一般的な定式化を行った. この定式化に おいてサブサンプリングは二つの項 $A$ と $B$ を用い て次のように表記される:

$
\begin{aligned}
& -\frac{1}{|D|} \sum_{(x, y) \in D}\left[A \log \left(\sigma\left(s_{\theta}(x, y)+\gamma\right)\right)\right. \\
+ & \left.\frac{1}{v} \sum_{y_{i} \sim p_{n}\left(y_{i} \mid x\right)}^{v} B \log \left(\sigma\left(-s_{\theta}\left(x, y_{i}\right)-\gamma\right)\right)\right] .
\end{aligned}
$

ここで $\sigma$ はシグモイド関数を， $p_{n}\left(y_{i} \mid x\right)$ は負例をサ ンプリングするためのノイズ分布を， $v$ は一つの正例 $(x, y)$ に対してサンプリングする負例の数を， $\gamma$ はマージン項をそれぞれ表す。

表 1 に，KGE において現在提案されているサブサ ンプリング手法を列挙する。これらは Sun ら [5] に よって提案された word2vec [4] のサブサンプリング を用いる手法 (Base), 頻度に基づく手法 (Freq) [10], そして，ユニーク性を考慮した手法 (Uniq) [10] であ る.ここで\#は頻度, $\#(x, y)$ は $(x, y)$ の頻度, $\alpha$ は頻度を平滑化するための温度を各々表している。表 1 現在の KGE で使用されているサブサンプリング法

と対応する項 $A$ と $B$ の一覧.

各 $(x, y)$ の頻度は $\mathrm{KG}$ 上で高々 1 であるため，先行研究では次のようなバックオフ [11]を行い, $(x, y)$ の頻度をクエリの頻度から近似的に導いている:

$
\#(x, y) \approx \#(x, y)_{c b s}=\frac{\#\left(h_{i}, r_{j}\right)+\#\left(r_{j}, t_{k}\right)}{2}
$

ここで， $\left(h_{i}, r_{j}, t_{k}\right)$ は $(x, y)$ に対応する枝であり, $\left(h_{i}, r_{j}\right),\left(r_{j}, t_{k}\right)$ はそのクエリである. 式 (2) は頻度情報に重度に依存しているため，我々は以降，この手法を頻度に基づくサブサンプリング (CBS) と呼ぶ.

## 3 提案手法

CBS は式 (2) に示すように，エンティティと関係 の組の頻度の平均で $\#(x, y)$ を近似する. そのため,少なくとも 1 つの組の頻度が低いと, CBS は\# $(x, y)$ をうまく推定できない。このスパースネス問題に対処するために，以下のように，モデルに基づくサブ サンプリング(MBS) と, 混合分布に基づくサブサン プリング (MIX)を提案する.

## 3.1 モデルに基づくサブサンプリング

頻度の低いエンティティと関係のペアに起因する 問題を回避するため，MBS では，学習済みモデル $\theta$ によって推定される確率を用いて，以下のように各 トリプレットとクエリの頻度を計算する。

$
\begin{aligned}
\#(x, y) & \approx \#(x, y)_{m b s}=|D| p_{\theta^{\prime}}(x, y), \\
\# x & \approx \# x_{m b s}=|D| \sum_{y_{i} \in D} p_{\theta^{\prime}}\left(x, y_{i}\right), \\
p_{\theta^{\prime}}(x, y) & =\frac{e^{\operatorname{score}_{\theta^{\prime}}(x, y)}}{\sum_{\left(x^{\prime}, y^{\prime}\right) \in D} e^{\text {score }_{\theta^{\prime}}\left(x^{\prime}, y^{\prime}\right)}} .
\end{aligned}
$

以下，MBS に使用するモデルをサブモデルと呼ぶ.式 (2) のカウントによって決定される頻度とは異 なり, 式 (5) の score $_{\theta^{\prime}}(x, y)$ は実際の頻度に関わら ず推論によって推定される. したがって，MBS は CBS で生じるスパースネスの問題に対処することが 期待できる. ただし，MBS の能力は選択するサブ モデルに依存するため，その限界については $\$ 4$ で の実験により評価する.
表 2 FB15k-237 での結果. 太字は各サブサンプリング (Base, Freq, Uniq) で最も良い結果であることを，†は各モ デルでの最良の結果を示す。

## 3.2 混合分布に基づくサブサンプリング

言語モデルに関する研究 [12] で言及されている ように，頻度に基づく出現確率とモデル予測に基づ く出現確率には異なる長所と短所が存在する．MIX では，CBS と MBS の短所を緩和して長所を高める

MBS による混合分布に置き換える。

$\lambda \frac{\#(x, y)_{m b s}^{-\alpha}|D|}{\sum_{\left(x^{\prime}, y^{\prime}\right) \in D} \#\left(x^{\prime}, y^{\prime}\right)_{m b s}^{-\alpha}}+(1-\lambda) \frac{\#(x, y)_{c b s}^{-\alpha}|D|}{\sum_{\left(x^{\prime}, y^{\prime}\right) \in D} \#\left(x^{\prime}, y^{\prime}\right)_{c b s}^{-\alpha}}$.

そして表 1 中の $\frac{\# x^{-\alpha}|D|}{\sum_{x^{\prime} \in D}^{\# x^{\prime-\alpha}}}$ を下記で置き換える:

$
\lambda \frac{\# x_{m b s}^{-\alpha}|D|}{\sum_{x^{\prime} \in D} \# x_{m b s}^{\prime-\alpha}}+(1-\lambda) \frac{\# x_{c b s}^{-\alpha}|D|}{\sum_{x^{\prime} \in D} \# x_{c b s}^{\prime-\alpha}} .
$

表 3 WN18RRでの結果．表記は表 2 と同様.

$\lambda$ は混合比率を決定するハイパーパラメータであ る.なお MIX はマルチタスク学習の一種である2).

## 4 実験

データセット: FB15k-237 と WN18RRを使用した31).比較手法: ComplEx, RotatE, HAKE に対し，表 1 の Base, Freq, Uniq を適用し，さらに CBS (\$2.2) と提案手法である MBS (\$3.1) 及び MIX (\$3.2)を適用した.評価尺度: MRR, Hits@1, Hits@3, Hits@10を使用.

実装およびハイパーパラメータ: ComplEx, RotatE に ついては先行研究 [5] の実装とハイパーパラメー 夕を継承し，HAKE についても先行研究 [7] の実装 とハイパーパラメータを継承した. 温度パラメー タ $\alpha$ について，CBSでは，Base の場合は Sun ら [5] を，Freq と Uniq は Kamigaito ら [10] の設定を引き継 いだ. MBS と MIXについては，各手法の検証デー

2）付録 $\mathrm{A}$ を参照

3）各データセットの統計については付録 B を参照.

図 $2 \mathrm{CBS}$ と MBS の各設定において，CBS の頻度で下位 100 件のクエリの出現確率を CBS の頻度で降順に左から右に 整列した際の MBS での出現確率.

タでの MRR の値を基に $\{2.0,1,0.5,0.1,0.05,0.01\}$ か ら $\alpha$ を， $\{0.1,0.3,0.5,0.7,0.9\}$ から混合比 $\lambda$ を選択 した. さらに，MBS と MIX のサブモデルを，開発 データの MRR を元に ComplEx, RotatE から選択し た.サブモデルの学習ではサブサンプリング法の Base を適用した場合とサブサンプリングを用いない 場合の二種類を用意した ${ }^{4}$ ).

## 4.1 実験結果および分析

実験結果 表 2,3 の結果はそれぞれ FB15k-237 と WN18RR における KG の補完性能を示している.こ の結果から，MIXやMBS を用いたモデルは，全て のモデルにおいて最も高い性能を達成していること が分かる.この結果は §1 で説明したように, MBS と MIX によって KG の補完性能が向上するという 考えと一致する. しかし, 各評価尺度に対して個別に手法を比較した場合には， CBS が MIX や MBS の補完性能を上回る場合も存在している。これは， MIX や MBS において推定される頻度が選択したサ ブモデルに依存して変化するためである.

以上より，MIX と MBS は頻度を推定するための サブモデルを適切に選択することで，KG 補完の性能を向上させる可能性があることが分かった.

分析 残された課題，すなわち，MBS のためにど のモデルを選択することが好ましいのかについて を分析する. 表 4 に各 MBS で選択されたサブモデ ルを示す.この表から ComplEx が他のモデルより 頻繁に選ばれていることが分かる. その理由を知 るために，CBS における頻度が下位 100 件のクエ リの MBS における頻度を図 2 に示した. この結果 では，FB15k-237 において RotatEでは ComplEx には ない頻度のスパイクがいくつか見られる．WN18RR表 4 開発データで選択されたサブモデルの一覧.

ではサブサンプリングを用いない ComplEx におけ る MBS の頻度の最大値が他の手法に比べて大きく なっている.

この結果は FB15k-237 と WN18RR においてモデ ルがそれぞれ平滑化の過剰と不足の問題に遭遇し， MBS がこの問題に対処したことを示している. 通常，データが少ないとスパース性が問題になるた め, この推測は FB15k-237 の学習データが WM18RR より大きいという事実に沿う。このように，MBSで は対象とするデータセットに適したサブモデルを選択することが重要であると考えられる。

## 5 おわりに

本論文では，モデルを用いてエンティティと関係 の組の頻度を推定することで，CBS における低頻度 な組が起こす問題に対処することが可能な新しい サブサンプリング法である，MBS と MIX を提案し た. FB15k-237 と WN18RRに対する評価結果から， MBS と MIXによって KG 補完の性能が向上するこ とが示された. さらに，分析の結果，データセット に適したサブモデルを選択することが KG 補完の性能向上に重要であることを明らかにした.

4）その他の詳細は付録 $\mathrm{C}$ に記載.

## 謝辞

本研究は JSPS 科研費 JP21K17801，JP21H03491 の 助成を受けたものです.

## 参考文献

[1] Seungwhan Moon, Pararth Shah, Anuj Kumar, and Rajen Subba. OpenDialKG: Explainable conversational reasoning with attention-based walks over knowledge graphs. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 845-854, Florence, Italy, July 2019. Association for Computational Linguistics.

[2] Denis Lukovnikov, Asja Fischer, Jens Lehmann, and Sören Auer. Neural network-based question answering over knowledge graphs on word and character level. In Proceedings of the 26th International Conference on World Wide Web, WWW '17, p. 1211-1220, Republic and Canton of Geneva, CHE, 2017. International World Wide Web Conferences Steering Committee.

[3] Jian Guan, Yansen Wang, and Minlie Huang. Story ending generation with incremental encoding and commonsense knowledge. Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 33, No. 01, pp. 6473-6480, Jul. 2019.

[4] Tomás Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado, and Jeffrey Dean. Distributed representations of words and phrases and their compositionality. CoRR, Vol. abs/1310.4546, 2013.

[5] Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang. Rotate: Knowledge graph embedding by relational rotation in complex space. In Proceedings of the 7th International Conference on Learning Representations, ICLR 2019, 2019.

[6] Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. Complex embeddings for simple link prediction. CoRR, Vol. abs/1606.06357, , 2016.

[7] Zhanqiu Zhang, Jianyu Cai, Yongdong Zhang, and Jie Wang. Learning hierarchy-aware knowledge graph embeddings for link prediction, 2019.

[8] 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.

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

[10] Hidetaka Kamigaito and Katsuhiko Hayashi. Comprehensive analysis of negative sampling in knowledge graph representation learning. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, Vol. 162 of Proceedings of Machine Learning Research, pp. 10661-
10675. PMLR, 17-23 Jul 2022.

[11] Slava Katz. Estimation of probabilities from sparse data for the language model component of a speech recognizer. IEEE transactions on acoustics, speech, and signal processing, Vol. 35, No. 3, pp. 400-401, 1987.

[12] Graham Neubig and Chris Dyer. Generalizing and hybridizing count-based and neural language models. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pp. 1163-1172, Austin, Texas, November 2016. Association for Computational Linguistics.

## A マルチタスク学習

式(1)において $A$ に CBS を適用したものを $A_{c b s} ， B$ に CBS を適用したものを $B_{c b s}$ とし， $A$ に MBSを適用 したものを $A_{m b s} ， B$ に MBS を適用したものを $B_{m b s}$ とする。ここで式 (1)に CBS を適用した際の損失関数 $\ell_{c b s}$ は

$
\ell_{c b s}=-\frac{1}{|D|} \sum_{(x, y) \in D}\left[A_{c b s} \log \left(\sigma\left(s_{\theta}(x, y)+\gamma\right)\right)+\frac{1}{v} \sum_{y_{i} \sim p_{n}\left(y_{i} \mid x\right)}^{v} B_{c b s} \log \left(\sigma\left(-s_{\theta}\left(x, y_{i}\right)-\gamma\right)\right)\right]
$

式 (1) に MBS を適用した際の損失関数 $\ell_{m b s}$ は

$
\ell_{m b s}=-\frac{1}{|D|} \sum_{(x, y) \in D}\left[A_{m b s} \log \left(\sigma\left(s_{\theta}(x, y)+\gamma\right)\right)+\frac{1}{v} \sum_{y_{i} \sim p_{n}\left(y_{i} \mid x\right)}^{v} B_{m b s} \log \left(\sigma\left(-s_{\theta}\left(x, y_{i}\right)-\gamma\right)\right)\right]
$

と定義される。また MIXを適用した際の損失関数 $\ell_{\text {mix }}$ は，式 (6) と式 (7) より，

$
\begin{aligned}
\ell_{\text {mix }}=-\frac{1}{|D|} \sum_{(x, y) \in D}[ & \left(\lambda A_{m b s}+(1-\lambda) A_{c b s}\right) \log \left(\sigma\left(s_{\theta}(x, y)+\gamma\right)\right) \\
& \left.+\frac{1}{v} \sum_{y_{i} \sim p_{n}\left(y_{i} \mid x\right)}^{v}\left(\lambda B_{m b s}+(1-\lambda) B_{c b s}\right) \log \left(\sigma\left(-s_{\theta}\left(x, y_{i}\right)-\gamma\right)\right)\right],
\end{aligned}
$

と定義される。ここで式(10) は次のように変形が可能である.

$
\ell_{\text {mix }}=\lambda \ell_{m b s}+(1-\lambda) \ell_{c b s}
$

式 (11) より $\ell_{m i x}$ は $\ell_{c b s}$ と $\ell_{m b s}$ の両損失を混合した損失であることから，MIX は CBS と MBS を使用した場合に対するマルチタスク学習であることが示された.

## B データセットの統計量

表 5 に各データセットの統計を示す.

表 5 各データセットの統計量. Ent はエンティティを，Rel は関係を示す.

## C 学習設定

表 6 に開発データの MRR で選択された各サブサンプリングの設定を示す。なお，MIXにおける $\alpha$ は MBS における最良のものを引き継いでいる.

表 6 開発データで選択されたサブモデルとその設定の一覧.
 Xincan Feng ${ }^{1}$ 上垣外英剛 ${ }^{1}$ 林克彦 $^{2}$ 渡辺太郎 ${ }^{1}$ 1 奈良先端科学技術大学院大学 2 北海道大学 \{feng.xincan.fy2, kamigaito.h, taro\}@is.naist.jp katsuhiko-h@ist.hokudai.ac.jp  