# Text Anchor Based Metric Learning for Small-footprint Keyword Spotting

###### Abstract

Keyword Spotting (KWS) remains challenging to achieve the trade-off between
small footprint and high accuracy. Recently proposed metric learning
approaches improved the generalizability of models for the KWS task, and
1D-CNN based KWS models have achieved the state-of-the-arts (SOTA) in terms of
model size. However, for metric learning, due to data limitations, the speech
anchor is highly susceptible to the acoustic environment and speakers. Also,
we note that the 1D-CNN models have limited capability to capture long-term
temporal acoustic features. To address the above problems, we propose to
utilize text anchors to improve the stability of anchors. Furthermore, a new
type of model (LG-Net) is exquisitely designed to promote long-short term
acoustic feature modeling based on 1D-CNN and self-attention. Experiments are
conducted on Google Speech Commands Dataset version 1 (GSCDv1) and 2 (GSCDv2).
The results demonstrate that the proposed text anchor based metric learning
method shows consistent improvements over speech anchor on representative CNN-
based models. Moreover, our LG-Net model achieves SOTA accuracy of 97.67% and
96.79% on two datasets, respectively. It is encouraged to see that our lighter
LG-Net with only 74k parameters obtains 96.82% KWS accuracy on the GSCDv1 and
95.77% KWS accuracy on the GSCDv2.

Index Terms: keyword spotting, long-term information, metric learning, small-
footprint, text anchor

##  1 Introduction

With speech technology development, speech assistants can help people solve
affairs more efficiently, such as querying weather and controlling air
conditioning. People increasingly enjoy the convenience of the hands-free
experience. Keyword Spotting (KWS) is the beginning of the human-computer
speech interaction, aims at distinguishing between each of the target keywords
of interest and non-target sounds such as general speech (non-target words)
and noises [1].

Recently, researchers have improved the generalization performance of models
in terms of data enhancement [2], loss function [3, 4], automatic gain control
[5], negative sample mining [6], and metric learning [1, 7]. In particular,
the metric learning based on triplet loss [1, 7] has demonstrated excellent
performance. The KWS models are trained using triplet consists of an $anchor$
sample, a $positive$ sample from the same class with the $anchor$, and a
$negative$ sample from a different class. The objective of the network
training is to minimize the distance between the embeddings of the $anchor$
and the $positive$ sample while maximizing the distance between the embeddings
of the $anchor$ and the $negative$ sample. It can be seen that the performance
is much dependent on the choice of the anchor. However, due to data
limitations, the speech anchor is highly susceptible to the acoustic
environment and speakers, making the anchor embedding more variant during
training. In addition, deviated speech anchors may make the KWS models
suffering from a local optimality issue, which leads to the degradation of the
performance.

Figure 1: Feature maps produced by the TC-ResNet14-1.5 and proposed model LG-
Net using a benchmark image, saliency for each feature is represented by
brightness. (a) and (b) shows that the feature maps outputs by 1D-CNN are
sparse, representing that 1D-CNN focuses on short-term temporal information.
(c) shows the self-attention layer modeling the long-term information while
preserving the short-term temporal information captured by the 1D-CNN.

On the other hand, Deep neural networks (DNNs) have recently proven to yield
efﬁcient small-footprint solutions for KWS [8, 9, 10, 11, 12, 13, 14, 15, 16].
In particular, more advanced architectures, such as Convolutional Neural
Networks (CNNs), have been applied to solve KWS problems under limited memory
footprint as well as computational resource scenarios, showing excellent
accuracy. Most CNN-based KWS models receive features, such as Mel-Frequency
Cepstral Coefﬁcient (MFCC), as a 2D input. However, such 2D CNN-based KWS
models struggle with capturing the dependency between low and high frequencies
with the relatively shallow network. To address this problem, [13, 15] utilize
temporal convolution to capture low and high-frequency features in a shallow
network, which achieves the best KWS performance. Despite their success, due
to local region perception and weight sharing characteristics of CNNs, the
long-term temporal information may not be considered. Figure 1a shows the
feature maps produced by a representative 1D-CNN-based KWS model, TC-
ResNet14-1.5 [13]. It is noted that the saliency regions are distributed
sparsely, which implies that 1D-CNN focuses on the short-term temporal
information. In fact, it is crucial to capture the long-term temporal
information for KWS, considering that the characteristics of keywords are
usually different on the time scale.

In this study, we aim at boosting the performance of the small-footprint KWS
model. To improve the stability of the anchor, we replace the speech anchor
with the text anchor and propose a text anchor based metric learning method
for KWS. Speciﬁcally, target keywords and non-target words are encoded in the
text anchors by pretraining models (like BERT [17]). Moreover, the local-
global network (LG-Net) is designed to model local and global information.
Speciﬁcally, the self-attention layer [18] is stacked to the 1D temporal
convolution layer to capture the long-term and short-term temporal
information. Experimental results demonstrate that the proposed text anchor
based metric learning method shows consistent improvements over speech anchor
on representative CNN-based models. Besides, our LG-Net model achieves SOTA
accuracy of 97.67% and 96.79% on Google Speech Commands Dataset version 1
(GSCDv1) and version 2 (GSCDv2), respectively.

##  2 Proposed Method

###  2.1 Data Process

The raw audio is decomposed into a sequence of frames where the window length
is 25 ms and the stride is 10 ms for feature extraction. We use 40 Mel-
Frequency Cepstral Coefficient (MFCC) features for each frame and stack them
over the time-axis, denote as $M\in\mathbb{R}^{T\times F}$ where $F$
represents the dimension of the MFCC feature, and $T$ denotes the number of
frames. The text anchor is extracted by BERT-base [17] denoted as
$V\in\mathbb{R}^{D}$, where $D$ represents the dimension of the text anchor
(i.e. $D=768$).

###  2.2 Text anchor based metric learning method

As mentioned in Section 1, the susceptibility of the speech anchor leads to
the poor performance of the model. Therefore, we propose a text anchor based
metric learning method for KWS, illustrated in Figure 2b. The input triplet is
denoted as ($M^{\mathrm{+}}$, $M^{\mathrm{-}}$, $V$), where $M^{\mathrm{+}}$
and $M^{\mathrm{-}}$ are input MFCCs from different classes, and $V$ as the
input text vector corresponding to $M^{\mathrm{+}}$. The speech embeddings
$E_{\mathrm{S}}^{M^{\mathrm{+}}}\in\mathbb{R}^{D^{\prime}}$ and
$E_{\mathrm{S}}^{M^{\mathrm{-}}}\in\mathbb{R}^{D^{\prime}}$ are extracted from
$M^{\mathrm{+}}$ and $M^{\mathrm{-}}$ by the speech embedding extraction
module $f_{\mathrm{S}}$, respectively, where $D^{\prime}$ represents the
dimension of the speech embedding (i.e. $D^{\prime}=128$). In parallel, $V$ is
mapped as a text embedding $E_{\mathrm{T}}\in\mathbb{R}^{D^{\prime}}$. The
triplet loss is employed to decreases the distance between the
$E_{\mathrm{T}}$ and $E_{\mathrm{S}}^{M^{\mathrm{+}}}$ and increases the
distance between $E_{\mathrm{T}}$ and $E_{\mathrm{S}}^{M^{\mathrm{-}}}$. For a
single sample, the triplet loss is thus

$L_{tri}=\max\left(d\left(E_{\mathrm{S}}^{M^{\mathrm{+}}},E_{\mathrm{T}}\right)-d\left(E_{\mathrm{S}}^{M^{\mathrm{-}}},E_{\mathrm{T}}\right)+\alpha,0\right)$
(1)

where $d(x,y)=\|x-y\|_{p}$ is the pairwise-distance between x and y (i.e.
$p=2$); $\alpha$ is a constant margin (i.e. $\alpha$ = 1).

Note that the phone embeddings extracted by the text encoder in [7] is
fundamentally different from the text anchor proposed in this paper. In [7], a
pronunciation dictionary is used to map words to their sequence of phonemes.
Therefore, the phone embeddings do not contain the information about other
words, although it is not influenced by factors such as acoustic environment
and speaker. The text anchor in this paper is extracted from the BERT [17]
which is trained on the large-scale text corpus, it contains information about
other words.

Figure 2: (a) Speech anchor based metric learning and (b) proposed text anchor
based metric learning. $M^{\mathrm{+}}$ and $M^{\mathrm{-}}$ are input MFCCs
from different classes, $M$ is input MFCC from the same class of
$M^{\mathrm{+}}$, and $V$ as the input text vector encoded by BERT [17]
corresponding $M^{\mathrm{+}}$. $E_{\mathrm{S}}$ represents the speech
embedding output from the speech embedding extraction module $f_{\mathrm{S}}$.
$E_{\mathrm{T}}$ represents the text embedding.

###  2.3 Local-global Neural Network

As mentioned in Section 1, for KWS, long-term temporal information is crucial
because the characteristics of keywords are usually different on the time
scale. In this work, we utilize the self-attention [18] layer to capture long-
term temporal information. The temporal convolution with residual structure
[13] is adopt in this paper, which is one of the most widely used 1D-CNN
architectures for KWS. To reduce the number of parameters, $3\times 1$ kernels
are utilized instead of $9\times 1$ kernels. As Figure 3 shows, and the self-
attention layer is stacked to the 1D-CNN layers, denoted as LG-Block.
Following the design of the previous study [13], the identity shortcuts can be
directly used when the input and output have matching dimensions (Figure 3a);
otherwise, we use an extra $1\times 1$ convolution with a stride to match the
dimensions (Figure 3b). Local-global neural network (LG-Net) can be easily
constructed by stacking LG-Blocks. We select LG-Net6 (Figure 3c), which has 6
LG-Blocks as our base model. To establish a small-footprint model, we compress
the LG-Net6 by taking out three LG-Blocks and reducing the number of channels,
named LG-Net3.

Considering the variation in feature maps due to speaking style, speed of
speech, we use an averaging pooling strategy on the time dimension. The output
of the average pooling layer is given to a fully connected layer to generate
speech embedding $E_{\mathrm{S}}\in\mathbb{R}^{D^{\prime}}$.

$E_{\mathrm{S}}=f_{\mathrm{S}}\left(M;\theta_{\mathrm{S}}\right)$ (2)

where $\theta_{\mathrm{S}}$ denote the parameters of the $f_{\mathrm{S}}$.

Finally, the predicted score, $\hat{y}\in\mathbb{R}^{C}$ where $C$ denote the
number of class, is obtained from $E_{\mathrm{S}}$

$\hat{y}=\sigma\left(f_{\mathrm{FC}}\left(E_{\mathrm{S}};\theta_{\mathrm{FC}}\right)\right)$
(3)

where $\sigma$ is the sigmoid function; $\theta_{\mathrm{FC}}$ denotes the
parameters of the fully connected layer $f_{\mathrm{FC}}$. KWS as a multi-
classification problem, the cross entropy (CE) loss is adopted to optimize the
model, for the given ground truth $y\in\mathbb{R}^{C}$ (where
$y^{(i)}=\\{0,1\\}$ denotes whether label $i$ appears or not), the loss $L$ is
calculated using binary cross-entropy:

$L_{CE}=\sum_{i=1}^{C}y^{(i)}\log\left(\hat{y}^{(i)}\right)+\left(1-y^{(i)}\right)\log\left(1-\hat{y}^{(i)}\right)$
(4)

Figure 3: The local-global block (LG-Block) when (a) stride = 1 and (b) stride
= 2 and two implementations of local-global neural network (LG-Net) when (c)
LG-Net6 and (d) LG-Net3. TConv means the temporal convolution layer, “s” and
“c” indicates stride and channel of TConv, respectively. PE means the position
encoding [18]. BN and FC denote batch normalization and fully connected layer.
The part inside the dotted line is regarded as the speech embedding extraction
module.

In this work, the networks are optimized by the loss $L$, which is calculated
by weighted sum of $L_{\mathrm{tri}}$ and $L_{\mathrm{CE}}$

$L=\beta L_{\mathrm{tri}}+(1-\beta)L_{\mathrm{CE}}$ (5)

where $\beta$ is the balanced weight between $L_{\mathrm{tri}}$ and
$L_{\mathrm{CE}}$.

Except for the cases of target keywords and non-target words, a “silence”
class is considered to indicate the case when no speech is detected [19].
However, in this work, the text vector of “silence” does not match the
definition in KWS, so the model cannot be trained directly using the text
vector of “silence”. To address the problem, we first train the network
without the “silence” sample and then finetune the two FC layers on the full
dataset with only CE loss.

##  3 Experiments

###  3.1 Datasets

The proposed models are trained and evaluated with Google Speech Commands
Dataset version 1
(GSCDv1111http://download.tensorflow.org/data/speech_commands_v0.01.tar.gz)
and version 2
(GSCDv2222http://download.tensorflow.org/data/speech_commands_v0.02.tar.gz)
[19]. Following the implementation of Google [19], we seek to discriminate
among 12 classes for GSCDv1: “yes”, “no”, “up”, “down”, “left”, “right”, “on”,
“off”, “stop”, “go”, unknown, or silence, and 16 classes for GSCDv2 which add
4 keywords of GSCDv1: ‘backward”, “forward”, “follow”, and “learn”. In order
to generate background noise, we randomly sample and crop background noises
provided in the dataset. For a fair comparison, in our test set, the “silence”
class test samples are taken from open source speech commands dataset test set
version
2333http://download.tensorflow.org/data/speech_commands_test_set_v0.02.tar.gz
[19], and test samples of other classes are written in the ofﬁcially released
testing.listv1v2. Table 1 shows the number of samples in training, validation,
and test sets. Note that to make it easy for other researchers to reproduce
the model and results in this paper, we do not use any data augmentation
methods.

Table 1: The number of samples in training, validation and test set of google speech commands dataset version 1 and version 2. Dataset |  Train |  Valid |  Test |  Total
---|---|---|---|---
GSCDv1 |  55287 |  7218 |  7242 |  69747
GSCDv2 |  89043 |  10401 |  11413 |  110857

###  3.2 Implementation Details

Our implementation was done with Pytorch [20] deep learning toolkit.

Training. All the models are trained with a mini-batch of 256 samples using
stochastic gradient descent with weight decay of 0.001 and momentum of 0.9.
For formula (5), the $L_{\mathrm{tri}}$ and $L_{\mathrm{CE}}$ weights to be
the same, i.e. $\beta=0.5$, $L=0.5L_{\mathrm{CE}}+0.5L_{\mathrm{tri}}$. The
initial learning rate is set to be 0.01 and decayed by a factor of 3 when the
validation accuracy does not increase for 3 epochs. The training is terminated
when validation accuracy does not increase for 10 epochs. For the fine-tuning
stage mentioned in Section 2.3, the training setup is the same as the text
anchor based metric learning method, except that $\beta$ is set as 0.

Evaluation. The primary metric in our experiments is classiﬁcation accuracy,
the proportion of correct decisions out of the total number of samples. We
also report the number of parameters and the false reject rate (FRR) at 0.5%
false alarm rate (FAR). We train each model 10 times and report its average
performance.

###  3.3 Baselines

To demonstrate the consistent performance improvement of our proposed text
anchor based metric learning method, we reproduce CnnTradFpool3 [9],
CnnOneFstride4 [9], TDNNSWSA [14], TC-ResNet8 [13], and TC-ResNet14-1.5 [13],
which are representative CNN-based KWS models.

We use three loss functions for training and comparison. First, the CE loss,
which is the most widely used loss function in the KWS task. Second, the
triplet loss based on speech anchor (ST) is used to evaluate the performance
gains from the triplet loss. As shown in Figure 2a, the input triplet is
denoted as ($M^{\mathrm{+}}$, $M^{\mathrm{-}}$, $M$), where $M$ is input MFCC
randomly sampled from the training set with the same class of
$M^{\mathrm{+}}$. Third, the triplet loss based on text anchor (TT). As
mentioned in Section 2.3, we employ CE loss accompanied by the ST and the TT,
denote as CE+ST and CE+TT, respectively. Also, to evaluate the performance
improvement brought by our proposed LG-Net model, we selected several CNN-
based KWS models trained with CE loss functions for direct comparison [10, 15,
16].

Table 2: Comparison of the proposed method and the baselines Model | Loss | Params | Acc.(v1) | Acc.(v2)
---|---|---|---|---
CnnTradFpool3 [9] (Sainath et al. 2015) | CE | 1.39M | 93.53% | 90.15%
CE+ST | 93.72% | 90.19%
CE+TT | 94.35% | 91.45%
0-4[0.8pt/2pt]  CnnOneFstride4 [9] (Sainath et al. 2015) | CE | 3.84M | 91.50% | 89.16%
CE+ST | 91.68% | 90.03%
CE+TT | 92.21% | 90.38%
0-4[0.8pt/2pt]  TDNNSWSA [14] (Bai et al. 2019) | CE | 20K | 94.19% | 93.11%
CE+ST | 95.32% | 93.77%
CE+TT | 95.47% | 94.15%
0-4[0.8pt/2pt]  TC-ResNet8 [13] (Choi et al. 2019) | CE | 72K | 95.71% | 95.22%
CE+ST | 96.12% | 95.56%
CE+TT | 96.58% | 95.59%
0-4[0.8pt/2pt]  TC-ResNet14-1.5 [13] (Choi et al. 2019) | CE | 313K | 96.78% | 95.96%
CE+ST | 96.81% | 96.20%
CE+TT | 96.89% |  96.27%
0-4[0.8pt/2pt]  Res15* [10] (Tang et al. 2018) | CE | 238K | 95.80% | -
0-4[0.8pt/2pt]  TENet12* [15] (Li et al. 2020) | CE | 100K | 96.84% | -
0-4[0.8pt/2pt]  NAS2* [16] (Mo et al. 2020) | CE | 886K |  97.22% | -
LG-Net3 (ours) | CE | 74K | 95.71% | 95.35%
CE+ST | 96.46% | 95.39%
CE+TT | 96.82% | 95.77%
0-4[0.8pt/2pt] LG-Net6 (ours) | CE | 313K | 97.03% | 96.45%
CE+ST | 97.13% | 96.57%
CE+TT | 97.67% | 96.79%
* represents the direct result of the corresponding paper.

###  3.4 Experimental Results and Analysis

Impact of text anchor based metric learning method. As Table 2 shows, for each
model, training with CE+TT loss shows consistent improvements over training
with CE+ST loss, since that BERT provides informative and robust text anchors,
which alleviates the effects of the acoustic environment and speakers.
Furthermore, We find that training with CE+ST loss yields a performance gain
compared to CE loss because triplet loss increases the distinguishability of
features. From Table 3, we can see that LG-Net6 achieves a lower FRR at 0.5%
FAR. Note that there is no increase in memory footprint and computational
resource at inference compared with the corresponding baseline. As Figure 4
shows, we randomly sample speech embeddings and use the t-SNE algorithm [23]
to visualize the embeddings. We can see that keywords with similar
pronunciation are difﬁcult to distinguish (e.g. “go” and “no”), but are easily
distinguished in the feature space after using our proposed text anchor based
metric learning method.

Table 3: Comparison of FRR (false reject rate) of TC-ResNet14-1.5 and LG-Net6, FRR (false alarm rate) is at 0.5% Model | Params | Loss | FRR
---|---|---|---
TC-ResNet14-1.5 | 313K | CE | 5.91%
CE+ST | 5.36%
CE+TT | 5.29%
LG-Net6 (ours) | 313K | CE | 4.69%
CE+ST | 4.31%
CE+TT |  3.56%

Figure 4: t-SNE visualization of speech embeddings extracted by LG-Net6.

Impact of other text vectors. We make a step forward to study how other text
vectors influence the performance of our proposed method. Comparison
experiments among the different layers of BERT and Glove [21] are performed.
Referring to Table 4, both models, TC-ResNet14-1.5 [13] and LG-Net6, achieve
the best performances by employing the output of the first layer from BERT as
the text anchor. The results indicate that the lower layer of BERT can mostly
capture word-level information, which is consistent with the statement in
[22].

Table 4: Comparison of other text embeddings on GSCDv2 Model | Text Embedding | Acc.
---|---|---
TC-ResNet14-1.5 [13] (Choi et al. 2019) |  glove.840B.300d [21] | 96.21%
BERT-Layer 1 [17] |  96.27%
BERT-Layer 2 [17] | 96.23%
BERT-Layer 12 [17] | 96.22%
LG-Net6 (ours) |  glove.840B.300d [21] | 96.47%
BERT-Layer 1 [17] |  96.79%
BERT-Layer 2 [17] | 96.52%
BERT-Layer 12 [17] | 96.50%

Impact of the local-global block. As shown in Table 2, compared to models
trained using CE loss, LG-Nets achieve a balance between model size and
accuracy. Compared to TC-ResNet14-1.5 [13], our LG-Net6 achieves better
accuracy of 97.03% and 96.45% on GSCDv1 and GSCDv2, respectively. Compared to
NAS2 [9], our proposed LG-Net6 achieves comparable results using only 35%
(313K/886K) of the number of parameters. The small-footprint model LG-Net3
obtains 95.71% KWS accuracy in GSCDv1 and 95.35% KWS accuracy in GSCDv2.
Visualization results (Figure 1b and Figure 1c) show that the self-attention
layer helps the network capture long-term temporal information while
preserving the short-term temporal information captured by the 1D-CNN.

##  4 Conclusion

In this paper, we propose text anchor based metric learning method and design
a neural network LG-Net for small-footprint keyword spotting (KWS). The
experimental results show that the proposed text anchor based metric learning
method shows consistent improvements over the speech anchor based method.
Moreover, our LG-Net model achieves SOTA accuracy on the Google Speech
Commands Dataset version 1 and version 2.

##  5 Acknowledgements

This paper was partially supported by Shenzhen Science & Technology
Fundamental Research Programs (No: JSGG20191129105421211 &
GXWD20201231165807007-20200814115301001)

## References

  * [1] J. Huh, M. Lee, H. Heo, S. Mun, and J. S. Chung, “Metric learning for keyword spotting,” _arXiv preprint arXiv:2005.08776_ , 2020.
  * [2] A. Raju, S. Panchapagesan, X. Liu, A. Mandal, and N. Strom, “Data augmentation for robust keyword spotting under playback interference,” _arXiv preprint arXiv:1808.00563_ , 2018.
  * [3] B. Liu, S. Nie, Y. Zhang, S. Liang, Z. Yang, and W. Liu, “Loss and double-edge-triggered detector for robust small-footprint keyword spotting,” in _ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2019, pp. 6361–6365.
  * [4] K. Zhang, Z. Wu, D. Yuan, J. Luan, J. Jia, H. Meng, and B. Song, “Re-weighted interval loss for handling data imbalance problem of end-to-end keyword spotting,” _Proc. Interspeech 2020_ , pp. 2567–2571, 2020.
  * [5] R. Prabhavalkar, R. Alvarez, C. Parada, P. Nakkiran, and T. N. Sainath, “Automatic gain control and multi-style training for robust small-footprint keyword spotting with deep neural networks,” in _2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2015, pp. 4704–4708.
  * [6] J. Hou, Y. Shi, M. Ostendorf, M.-Y. Hwang, and L. Xie, “Mining effective negative training samples for keyword spotting,” in _ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2020, pp. 7444–7448.
  * [7] N. Sacchi, A. Nanchen, M. Jaggi, and M. Cernak, “Open-vocabulary keyword spotting with audio and text embeddings,” in _INTERSPEECH 2019-IEEE International Conference on Acoustics, Speech, and Signal Processing_ , no. CONF, 2019.
  * [8] G. Chen, C. Parada, and G. Heigold, “Small-footprint keyword spotting using deep neural networks,” in _2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2014, pp. 4087–4091.
  * [9] T. N. Sainath and C. Parada, “Convolutional neural networks for small-footprint keyword spotting,” in _Sixteenth Annual Conference of the International Speech Communication Association_ , 2015.
  * [10] R. Tang and J. Lin, “Deep residual learning for small-footprint keyword spotting,” in _2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2018, pp. 5484–5488.
  * [11] C. Shan, J. Zhang, Y. Wang, and L. Xie, “Attention-based end-to-end models for small-footprint keyword spotting,” _arXiv preprint arXiv:1803.10916_ , 2018\.
  * [12] H. Zhang, J. Zhang, and Y. Wang, “Sequence-to-sequence models for small-footprint keyword spotting,” _arXiv preprint arXiv:1811.00348_ , 2018\.
  * [13] S. Choi, S. Seo, B. Shin, H. Byun, M. Kersner, B. Kim, D. Kim, and S. Ha, “Temporal convolution for real-time keyword spotting on mobile devices,” _arXiv preprint arXiv:1904.03814_ , 2019.
  * [14] Y. Bai, J. Yi, J. Tao, Z. Wen, Z. Tian, C. Zhao, and C. Fan, “A time delay neural network with shared weight self-attention for small-footprint keyword spotting,” _Proc. Interspeech 2019_ , pp. 2190–2194, 2019.
  * [15] X. Li, X. Wei, and X. Qin, “Small-footprint keyword spotting with multi-scale temporal convolution,” _arXiv preprint arXiv:2010.09960_ , 2020.
  * [16] T. Mo, Y. Yu, M. Salameh, D. Niu, and S. Jui, “Neural architecture search for keyword spotting,” _arXiv preprint arXiv:2009.00165_ , 2020.
  * [17] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, “Bert: Pre-training of deep bidirectional transformers for language understanding,” _arXiv preprint arXiv:1810.04805_ , 2018.
  * [18] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, “Attention is all you need,” in _Advances in neural information processing systems_ , 2017, pp. 5998–6008.
  * [19] P. Warden, “Speech commands: A dataset for limited-vocabulary speech recognition,” _arXiv preprint arXiv:1804.03209_ , 2018.
  * [20] A. Paszke, S. Gross, S. Chintala, G. Chanan, E. Yang, Z. DeVito, Z. Lin, A. Desmaison, L. Antiga, and A. Lerer, “Automatic differentiation in pytorch,” 2017.
  * [21] J. Pennington, R. Socher, and C. D. Manning, “Glove: Global vectors for word representation,” in _Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP)_ , 2014, pp. 1532–1543.
  * [22] G. Jawahar, B. Sagot, and D. Seddah, “What does bert learn about the structure of language?” in _ACL 2019-57th Annual Meeting of the Association for Computational Linguistics_ , 2019.


# Model-based Subsampling for Knowledge Graph Completion

Xincan Feng†, Hidetaka Kamigaito†, Katsuhiko Hayashi‡, Taro Watanabe†
†Nara Institute of Science and Technology ‡Hokkaido University
{feng.xincan.fy2, kamigaito.h<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

Subsampling is effective in Knowledge Graph Embedding (KGE) for reducing
overfitting caused by the sparsity in Knowledge Graph (KG) datasets. However,
current subsampling approaches consider only frequencies of queries that
consist of entities and their relations. Thus, the existing subsampling
potentially underestimates the appearance probabilities of infrequent queries
even if the frequencies of their entities or relations are high. To address
this problem, we propose Model-based Subsampling (MBS) and Mixed Subsampling
(MIX) to estimate their appearance probabilities through predictions of KGE
models. Evaluation results on datasets FB15k-237, WN18RR, and YAGO3-10 showed
that our proposed subsampling methods actually improved the KG completion
performances for popular KGE models, RotatE, TransE, HAKE, ComplEx, and
DistMult.

##  1 Introduction

A Knowledge Graph (KG) is a graph that contains entities and their relations
as links. KGs are important resources for various NLP tasks, such as dialogue
Moon et al. (2019), question-answering Lukovnikov et al. (2017), and natural
language generation Guan et al. (2019), etc. However, covering all relations
of entities in a KG by humans takes a lot of costs. Knowledge Graph Completion
(KGC) tries to solve this problem by automatically completing lacking
relations based on the observed ones. Letting $e_{i}$ and $e_{k}$ be entities,
and $r_{j}$ be their relation, KGC models predict the existence of a link
$(e_{i},r_{j},e_{k})$ by filling the $?$ in the possible links
$(e_{i},r_{j},?)$ and $(?,r_{j},e_{k})$, where $(e_{i},r_{j})$ and
$(r_{j},e_{k})$ are called queries, and the $?$ are the corresponding answers.

$25$$30$$35$$40$$45$$50$$55$YAGO3-10WN18RRFB15k-237Mean Reciprocal Rank
(MRR)w/ Subsamplingw/o Subsampling Figure 1: The averaged KGC performance
(MRR) of KGE models222See Appendix A for the details.with and without
subsampling on FB15k-237, WN18RR, and YAGO3-10.

Currently, Knowledge Graph Embedding (KGE) is a dominant approach for KGC. KGE
models represent entities and their relations as continuous vectors. Since the
number of these vectors proportionally increases to the number of links in a
KG, KGE commonly relies on Negative Sampling (NS) to reduce the computational
cost in training. In NS, a KGE model learns a KG by discriminating between
true links and false links created by sampling links in the KG. While NS can
reduce the computational cost, it has the problem that the sampled links also
reflect the bias of the original KG.

As a solution, Sun et al. (2019) introduce subsampling Mikolov et al. (2013)
into NS for KGE. In this usage, subsampling is a method of mitigating bias in
a KG by discounting the appearance frequencies of links with high-frequent
queries and reserving the appearance frequencies for links with low-frequent
queries. Figure 2 shows the effectiveness of using subsampling. From this
figure, we can understand that KGE models cannot perform well without
subsampling on commonly used datasets such as FB15k-237 Toutanova and Chen
(2015), WN18RR Dettmers et al. (2018), and YAGO3-10 Dettmers et al. (2018).
Furthermore, the improved MRR on FB15k-237, which has more sparse relations
than the other datasets, indicates that subsampling actually works on the
sparse dataset.

Figure 2: Frequencies of entities and relations included in each query that
appeared only once in training data of FB15k-237, WN18RR, and YAGO3-10444Due
to the space limitation, it is difficult to plot all the values in this graph.
Thus, we filter the entities and relations for every certain amount after they
are sorted by frequency in descending order. The filtering amounts for
FB15k-237, WN18RR, and YAGO3-10 are 2,000, 1,778, and 4,444, respectively. By
this filtering, the number of plotted entities and relations for FB15k-237,
WN18RR, and YAGO3-10 are reduced to 45, 44, and 45, respectively..

However, the current subsampling approaches in KGE Sun et al. (2019);
Kamigaito and Hayashi (2022a) only consider the frequencies of queries. Thus,
these approaches potentially underestimate the appearance probabilities of
infrequent queries when the frequencies of their entities or relations are
high. Figure 4 shows the frequencies of entities and relations included in
each query that appeared only once in training data. From the statistics, we
can find that the current count-based subsampling (CBS) does not effectively
use frequencies of entities and relations in infrequent queries, although
these have sufficient frequencies.

To deal with this problem, we propose Model-based Subsampling (MBS) that can
handle such infrequent queries by estimating their appearance probabilities
through predictions from KGE models in subsampling. Since the observed
frequency in training data does not restrict the estimated frequencies of MBS
different from CBS, we can expect the improvement of KGC performance using
MBS. In addition, we also propose Mixed Subsampling (MIX), which uses the
frequencies of both CBS and MBS to boost their advantage by reducing their
disadvantages.

In our evaluation on FB15k-237, WN18RR, and YAGO3-10 datasets, we adopted our
MBS and MIX to the popularly used KGE models RotatE Sun et al. (2019), TransE
Bordes et al. (2013), HAKE Zhang et al. (2019), ComplEx Trouillon et al.
(2016), and DistMult Yang et al. (2015). The evaluation results showed that
MBS and MIX improved MRR, H@1, H@3, and H@10 from Count-based Subsampling
(CBS) in each setting555Our code is available on
https://github.com/xincanfeng/ms_kge..

##  2 Subsampling in KGE

###  2.1 Problem Definitions and Notations

We denote a link of a KG in the triplet format $(h,r,t)$. $h$ is the head
entity, $t$ is the tail entity, and $r$ is the relation of the head and tail
entity. In a classic KG completion task, we input the query $(h,r,?)$ or
$(?,r,t)$, and output the predicted head or tail entity corresponding to $?$
as the answer. More formally, let us denote the input query as $x$ and its
answer as $y$, hereafter. A score function $s_{\mathbf{\theta}}(x,y)$ predicts
$p_{\mathbf{\theta}}(y|x)$, a probability for a given query $x$ linked to an
answer $y$ based on a model $\mathbf{\theta}$. In general, we train
$\mathbf{\theta}$ by predicting $p_{\mathbf{\theta}}(y|x)$ on $|D|$ number of
links, where $D=\\{(x_{1},y_{1}),\cdots,(x_{|D|},y_{|D|})\\}$ is a set of
observables that follow $p_{d}(x,y)$.

###  2.2 Negative Sampling in KGE

Since calculating all possible $y$ for given $x$ is computationally
inefficient, NS loss is commonly used for training KGE models. The NS loss in
KGE, $\ell_{kge}(\mathbf{\theta})$ is represented as follows:

$\displaystyle\ell_{kge}(\mathbf{\theta})$ $\displaystyle=$
$\displaystyle-\frac{1}{|D|}\sum_{(x,y)\in
D}\Bigl{[}\log(\sigma(s_{\mathbf{\theta}}(x,y)+\gamma))$
$\displaystyle+\frac{1}{\nu}\sum_{y_{i}\sim
p_{n}(y_{i}|x)}^{\nu}\log(\sigma(-s_{\mathbf{\theta}}(x,y_{i})-\gamma))\Bigr{]},$
(1)

where $\sigma$ is a sigmoid function, $p_{n}(y_{i}|x)$ is a noise distribution
describing negative samples, $\nu$ is a number of negative samples per
positive sample $(x,y)$, $\gamma$ is a margin term to adjust the value range
of the score function. $p_{n}(y_{i}|x)$ has a role of adjusting the frequency
of $y_{i}$ Kamigaito and Hayashi (2021).

###  2.3 Negative Sampling with Subsampling

Subsampling Mikolov et al. (2013) is a method to reduce the bias of training
data by discounting high-frequent instances. Kamigaito and Hayashi (2022a)
show a general formulation to cover currently proposed subsampling approaches
in the NS loss for KGE by altering two terms $A_{cbs}$ and $B_{cbs}$. In that
form, the NS loss in KGE with subsampling, $\ell_{cbs}(\mathbf{\theta})$ is
represented as follows:

$\displaystyle\ell_{cbs}(\mathbf{\theta})$ $\displaystyle=$
$\displaystyle-\frac{1}{|D|}\sum_{(x,y)\in
D}\Bigl{[}A_{cbs}\log(\sigma(s_{\mathbf{\theta}}(x,y)+\gamma))$
$\displaystyle+\frac{1}{\nu}\sum_{y_{i}\sim
p_{n}(y_{i}|x)}^{\nu}B_{cbs}\log(\sigma(-s_{\mathbf{\theta}}(x,y_{i})-\gamma))\Bigr{]},$
(2)

where $A_{cbs}$ adjusts the frequency of a true link $(x,y)$, and $B_{cbs}$
adjusts the query $x$ to adjust the frequency of a false link $(x,y_{i})$.

Method | $A_{cbs}$ | $B_{cbs}$
---|---|---
Base | $\frac{\frac{1}{\sqrt{\\#(x,y)}}|D|}{\sum_{(x^{\prime},y^{\prime})\in D}\frac{1}{\sqrt{\\#(x^{\prime},y^{\prime})}}}$ | $\frac{\frac{1}{\sqrt{\\#(x,y)}}|D|}{\sum_{(x^{\prime},y^{\prime})\in D}\frac{1}{\sqrt{\\#(x^{\prime},y^{\prime})}}}$
Freq | $\frac{\frac{1}{\sqrt{\\#(x,y)}}|D|}{\sum_{(x^{\prime},y^{\prime})\in D}\frac{1}{\sqrt{\\#(x^{\prime},y^{\prime})}}}$ | $\frac{\frac{1}{\sqrt{\\#x}}|D|}{\sum_{x^{\prime}\in D}{\frac{1}{\sqrt{\\#x^{\prime}}}}}$
Uniq | $\frac{\frac{1}{\sqrt{\\#x}}|D|}{\sum_{x^{\prime}\in D}{\frac{1}{\sqrt{\\#x^{\prime}}}}}$ | $\frac{\frac{1}{\sqrt{\\#x}}|D|}{\sum_{x^{\prime}\in D}{\frac{1}{\sqrt{\\#x^{\prime}}}}}$

Table 1: Currently proposed count-based subsampling methods in KGE and their
corresponding terms on $A_{cbs}$ and $B_{cbs}$.

Table 1 lists the currently proposed subsampling approaches which are the
original subsampling for word2vec (Mikolov et al., 2013) in KGE of Sun et al.
(2019) (Base), frequency-based subsampling of Kamigaito and Hayashi (2022a)
(Freq), and unique-based subsampling of Kamigaito and Hayashi (2022a) (Uniq)
Kamigaito and Hayashi (2022b). Here, $\\#$ denotes frequency, $\\#(x,y)$
represents the frequency of $(x,y)$.

Since frequency for each link $(x,y)$ is at most one in KG, the previous
approaches use the following back-off approximation (Katz, 1987):

$\displaystyle\\#(x,y)\approx\frac{\\#(h_{i},r_{j})\\!+\\#(r_{j},t_{k})}{2},$
(3)

where $(x,y)$ corresponds to the link $(h_{i},r_{j},t_{k})$, and
$(h_{i},r_{j})$ and $(r_{j},t_{k})$ are the queries. Due to their heavily
relying on counted frequency information of queries, we call the above
conventional subsampling method Count-based Subsamping (CBS), hereafter.

##  3 Proposed Methods

As shown in Equation (3), CBS approximates the frequency of a link $\\#(x,y)$
by combining the counted frequencies of entity-relation pairs. Thus, CBS
cannot estimate $\\#(x,y)$ well when at least one pair’s frequency is low in
the approximation. This kind of situation is caused by the sparseness problem
in the KG datasets. To deal with this sparseness problem, we propose Model-
based Subsampling method (MBS) and Mixed Subsampling method (MIX) as described
in the following subsections.

###  3.1 Model-based Subsampling (MBS)

To avoid the problem caused by low-frequent entity-relation pairs, our MBS
uses the estimated probabilities from a trained model
$\mathbf{\theta}^{\prime}$ to calculate frequencies for each triplet and
query. By using $\mathbf{\theta}^{\prime}$, the NS loss in KGE with MBS is
represented as follows:

$\displaystyle\ell_{mbs}(\mathbf{\theta};\mathbf{\theta}^{\prime})$
$\displaystyle=$ $\displaystyle-\frac{1}{|D|}\sum_{(x,y)\in
D}\Bigl{[}A_{mbs}(\mathbf{\theta}^{\prime})\log(\sigma(s_{\mathbf{\theta}}(x,y)+\gamma))$
$\displaystyle+\frac{1}{\nu}\\!\\!\\!\\!\\!\\!\sum_{y_{i}\sim
p_{n}(y_{i}|x)}^{\nu}\\!\\!\\!\\!\\!\\!B_{mbs}(\mathbf{\theta}^{\prime})\log(\sigma(-s_{\mathbf{\theta}}(x,y_{i})-\gamma))\Bigr{]},$
(4)

Here, corresponding to each method in Table 4,
$A_{mbs}(\mathbf{\theta}^{\prime})$ and $B_{mbs}(\mathbf{\theta}^{\prime})$
are further represented as follows:

$\displaystyle A_{mbs}(\mathbf{\theta}^{\prime})$
$\displaystyle=\left\\{\begin{array}[]{*2{>{\displaystyle}l}}\frac{\\#(x,y)_{mbs}^{-\alpha}|D|}{\sum_{(x^{\prime},y^{\prime})\in
D}\\#(x^{\prime},y^{\prime})_{mbs}^{-\alpha}}&\mathrm{(Base)}\\\
\frac{\\#(x,y)_{mbs}^{-\alpha}|D|}{\sum_{(x^{\prime},y^{\prime})\in
D}\\#(x^{\prime},y^{\prime})_{mbs}^{-\alpha}}&\mathrm{(Freq)}\\\
\frac{\\#x_{mbs}^{-\alpha}|D|}{\sum_{x^{\prime}_{mbs}\in
D}{{\\#x^{\prime}}_{mbs}^{-\alpha}}}&\mathrm{(Uniq)}\end{array}\right.$ (8)
$\displaystyle B_{mbs}(\mathbf{\theta}^{\prime})$
$\displaystyle=\left\\{\begin{array}[]{*2{>{\displaystyle}l}}\frac{\\#(x,y)_{mbs}^{-\alpha}|D|}{\sum_{(x^{\prime},y^{\prime})\in
D}\\#(x^{\prime},y^{\prime})_{mbs}^{-\alpha}}&\mathrm{(Base)}\\\
\frac{\\#x_{mbs}^{-\alpha}|D|}{\sum_{x^{\prime}_{mbs}\in
D}{\\#x^{\prime}}_{mbs}^{-\alpha}}&\mathrm{(Freq)}\\\
\frac{\\#x_{mbs}^{-\alpha}|D|}{\sum_{x^{\prime}_{mbs}\in
D}{\\#x^{\prime}}_{mbs}^{-\alpha}}&\mathrm{(Uniq)}\end{array}\right.$ (12)

where $\alpha$ is a temperature term to adjust the distribution on
$A_{mbs}(\mathbf{\theta}^{\prime})$ and $B_{mbs}(\mathbf{\theta}^{\prime})$.
The frequencies $\\#(x,y)_{mbs}$ and $\\#x_{mbs}$, estimated by using
$score_{\mathbf{\theta}^{\prime}}(x,y)$ are calculated as follows:

$\displaystyle\\#(x,y)_{mbs}$
$\displaystyle=|D|p_{\mathbf{\theta}^{\prime}}(x,y),$ (13)
$\displaystyle\\#x_{mbs}$ $\displaystyle=|D|\textstyle\sum_{y_{i}\in
D}p_{\mathbf{\theta}^{\prime}}(x,y_{i}),$ (14) $\displaystyle
p_{\mathbf{\theta}^{\prime}}(x,y)$
$\displaystyle=\frac{e^{score_{\mathbf{\theta}^{\prime}}(x,y)}}{\sum_{(x^{\prime},y^{\prime})\in
D}e^{score_{\mathbf{\theta}^{\prime}}(x^{\prime},y^{\prime})}}.$ (15)

Hereafter, we refer to a model pre-trained for MBS as a sub-model. Different
from the counted frequencies in Eq. (3),
$score_{\mathbf{\theta}^{\prime}}(x,y)$ in Eq. (15) estimates them by sub-
model inference regardless of their actual frequencies. Hence, we can expect
MBS to deal with the sparseness problem in CBS. However, the ability of MBS
depends on the sub-model, and we investigated the performance through our
evaluations (§4).

###  3.2 Mixed Subsampling (MIX)

As discussed in language modeling context (Neubig and Dyer, 2016), count-based
and model-based frequencies have different strengths and weaknesses. To boost
the advantages of CBS and MBS by mitigating their disadvantages, MIX uses a
mixture of the distribution as follows:

$\displaystyle\ell_{mix}(\mathbf{\theta};\mathbf{\theta}^{\prime})$
$\displaystyle=$ $\displaystyle-\frac{1}{|D|}\sum_{(x,y)\in
D}\Bigl{[}A_{mix}(\mathbf{\theta}^{\prime})\log(\sigma(s_{\mathbf{\theta}}(x,y)+\gamma))$
$\displaystyle+\frac{1}{\nu}\\!\\!\\!\\!\\!\\!\sum_{y_{i}\sim
p_{n}(y_{i}|x)}^{\nu}\\!\\!\\!\\!\\!\\!B_{mix}(\mathbf{\theta}^{\prime})\log(\sigma(-s_{\mathbf{\theta}}(x,y_{i})-\gamma))\Bigr{]},$
(16)

where $A_{mix}(\mathbf{\theta}^{\prime})$ is a mixture of $A_{cbs}$ in Eq. (2)
and $A_{mbs}(\mathbf{\theta}^{\prime})$ in Eq. (4), and
$B_{mix}(\mathbf{\theta}^{\prime})$ is also a mixture of $B_{cbs}$ in Eq. (2)
and $B_{mbs}(\mathbf{\theta}^{\prime})$ Eq. (4) as follows:

$\displaystyle A_{mix}(\mathbf{\theta}^{\prime})=\lambda
A_{mbs}(\mathbf{\theta}^{\prime})+(1-\lambda)A_{cbs}$ (17) $\displaystyle
B_{mix}(\mathbf{\theta}^{\prime})=\lambda
B_{mbs}(\mathbf{\theta}^{\prime})+(1-\lambda)B_{cbs}$ (18)

where $\lambda$ is a hyper-parameter to adjust the ratio of MBS and CBS. Note
that MIX can be interpreted as a kind of multi-task learning666See Appendix B
for the details..

##  4 Evaluation and Analysis

###  4.1 Settings

#### Datasets

We used the three commonly used datasets, FB15k-237, WN18RR, and YAGO3-10, for
the evaluation. Table 2 shows the statistics for each dataset. Unlike
FB15k-237 and WN18RR, the dataset of YAGO3-10 only includes entities that have
at least 10 relations and alleviates the sparseness problem of KGs. Thus, we
can investigate the effectiveness of MBS and MIX in the sparseness problem by
comparing performances on these datasets.

#### Methods

We compared five popular KGE models RotatE, TransE, HAKE, ComplEx, and
DistMult with utilizing subsampling methods Base, Freq, and Uniq based on the
loss of CBS (§2.3) and our MBS (§3.1) and MIX (§3.2). Additionally, we
conducted experiments with no subsampling (None) to investigate the efficacy
of the subsampling method. In YAGO3-10, due to our limited computational
resources and the existence of tuned hyper-parameters by Sun et al. (2019);
Zhang et al. (2019), we only used RotatE and HAKE for evaluation.

Dataset | #Train | #Valid | #Test | Ent | Rel
---|---|---|---|---|---
FB15K-237 | 272,115 | 17,535 | 20,466 | 14,541 | 237
WN18RR | 86,835 | 3,034 | 3,134 | 40,943 | 11
YAGO3-10 | 1,079,040 | 5,000 | 5,000 | 123,188 | 37

Table 2: Datasets statistics. #: Split in terms of number of triples; Ent:
Entities; Rel: Relations; Exa: Examples.

FB15k-237
---
Model | Subsampling | MRR | H@1 | H@3 | H@10 | Submodeling
Mean | SD | Mean | SD | Mean | SD | Mean | SD | Sub-model | $\alpha$ | $\lambda$
RotatE | None | 32.9 | 0.1 | 22.9 | 0.1 | 37.0 | 0.1 | 53.1 | 0.1 |  |  |  |
Base | CBS | 33.6 | 0.1 | 23.9 | 0.1 | 37.4 | 0.1 | 53.1 | 0.1 |  |  |  |
| MBS | 33.9 | 0.0 | 24.2 | 0.1 | 37.7 | 0.1 | 53.5 | 0.1 | ComplEx | None | 0.5 | –
| MIX | 33.9 | 0.0 | 24.2 | 0.0 | 37.7 | 0.1 | 53.5 | 0.1 | 0.9
Freq | CBS | 34.1 | 0.0 | 24.6 | 0.1 | 37.7 | 0.0 | 53.1 | 0.0 |  |  |  |
| MBS | 34.3 | 0.0 | 24.8 | 0.1 | 38.0 | 0.1 | 53.6 | 0.1 | ComplEx | None | 0.1 | –
| MIX |  †34.5 | 0.0 | 24.9 | 0.1 |  †38.1 | 0.1 |  †53.7 | 0.1 | 0.7
| Uniq | CBS | 33.9 | 0.0 | 24.4 | 0.1 | 37.6 | 0.1 | 53.0 | 0.2 |  |  |  |
|  | MBS | 34.3 | 0.0 | 24.7 | 0.1 | 38.0 | 0.2 |  †53.7 | 0.1 | ComplEx | None | 0.1 | –
|  | MIX |  †34.5 | 0.1 |  †25.0 | 0.1 | 38.0 | 0.1 | 53.6 | 0.1 | 0.5
TransE | None | 33.0 | 0.1 | 22.9 | 0.1 | 37.2 | 0.1 | 53.0 | 0.2 |  |  |  |
Base | CBS | 33.0 | 0.1 | 23.1 | 0.1 | 36.8 | 0.1 | 52.7 | 0.1 |  |  |  |
| MBS | 33.3 | 0.1 | 23.4 | 0.1 | 37.3 | 0.0 | 53.1 | 0.1 | ComplEx | None | 0.5 | –
| MIX | 33.4 | 0.1 | 23.4 | 0.1 | 37.3 | 0.0 | 53.2 | 0.1 | 0.9
Freq | CBS | 33.5 | 0.1 | 23.9 | 0.2 | 37.3 | 0.1 | 52.8 | 0.1 |  |  |  |
| MBS | 33.9 | 0.0 | 24.1 | 0.1 | 37.7 | 0.1 | 53.2 | 0.0 | RotatE | Base | 0.1 | –
| MIX |  †34.1 | 0.1 |  †24.3 | 0.1 |  †37.9 | 0.1 |  †53.4 | 0.0 | 0.7
| Uniq | CBS | 33.6 | 0.1 | 24.0 | 0.1 | 37.3 | 0.1 | 52.7 | 0.1 |  |  |  |
|  | MBS | 33.8 | 0.1 | 23.9 | 0.1 | 37.7 | 0.1 | 53.2 | 0.1 | RotatE | Base | 0.1 | –
|  | MIX | 34.0 | 0.1 |  †24.3 | 0.1 |  †37.9 | 0.1 |  †53.4 | 0.1 | 0.7
HAKE | None | 32.4 | 0.0 | 22.0 | 0.0 | 36.9 | 0.1 | 53.1 | 0.1 |  |  |  |
Base | CBS | 34.5 | 0.1 | 24.9 | 0.1 | 38.3 | 0.1 | 54.1 | 0.0 |  |  |  |
| MBS | 34.4 | 0.1 | 24.5 | 0.1 | 38.2 | 0.1 | 54.1 | 0.2 | ComplEx | None | 1.0 | –
| MIX | 34.6 | 0.1 | 24.8 | 0.1 | 38.3 | 0.1 | 54.2 | 0.1 | 0.5
Freq | CBS | 35.1 | 0.1 | 25.5 | 0.1 | 38.8 | 0.1 | 54.3 | 0.0 |  |  |  |
| MBS | 35.2 | 0.1 | 25.7 | 0.1 | 39.0 | 0.1 | 54.4 | 0.1 | ComplEx | Base | 0.5 | –
| MIX |  †35.4 | 0.0 |  †25.8 | 0.1 |  †39.2 | 0.1 | 54.5 | 0.1 | 0.5
| Uniq | CBS | 35.2 | 0.1 | 25.6 | 0.2 | 38.9 | 0.1 | 54.5 | 0.1 |  |  |  |
|  | MBS | 35.3 | 0.1 | 25.6 | 0.0 | 38.9 | 0.1 | 54.5 | 0.1 | RotatE | Base | 0.5 | –
|  | MIX | 35.3 | 0.0 |  †25.8 | 0.1 | 38.9 | 0.1 |  †54.6 | 0.1 | 0.3
ComplEx | None | 22.3 | 0.1 | 13.9 | 0.1 | 24.1 | 0.2 | 39.5 | 0.1 |  |  |  |
Base | CBS | 32.3 | 0.1 | 23.0 | 0.2 | 35.5 | 0.1 | 51.3 | 0.1 |  |  |  |
| MBS | 31.2 | 0.1 | 21.7 | 0.1 | 34.4 | 0.2 | 50.6 | 0.1 | ComplEx | None | 1.0 | –
| MIX | 32.4 | 0.1 | 22.8 | 0.1 | 35.8 | 0.1 |  †52.1 | 0.2 | 0.5
Freq | CBS | 32.7 | 0.1 | 23.6 | 0.1 | 36.0 | 0.1 | 51.2 | 0.1 |  |  |  |
| MBS | 32.0 | 0.0 | 23.0 | 0.0 | 35.1 | 0.1 | 50.1 | 0.1 | DistMult | Base | 0.5 | –
| MIX |  †32.9 | 0.1 |  †23.7 | 0.1 |  †36.2 | 0.1 | 51.3 | 0.2 | 0.1
| Uniq | CBS | 32.6 | 0.1 | 23.4 | 0.2 | 35.9 | 0.1 | 51.1 | 0.1 |  |  |  |
|  | MBS | 31.8 | 0.1 | 22.6 | 0.2 | 34.9 | 0.1 | 50.5 | 0.2 | ComplEx | Base | 0.5 | –
|  | MIX | 32.7 | 0.1 | 23.4 | 0.1 | 36.0 | 0.1 | 51.2 | 0.2 | 0.1
DistMult | None | 22.3 | 0.1 | 14.1 | 0.1 | 24.2 | 0.1 | 39.3 | 0.1 |  |  |  |
Base | CBS | 30.8 | 0.1 | 22.0 | 0.1 | 33.7 | 0.1 | 48.4 | 0.1 |  |  |  |
| MBS | 31.1 | 0.2 | 21.8 | 0.1 | 34.1 | 0.2 | 49.6 | 0.2 | ComplEx | None | 1.0 | –
| MIX |  †31.3 | 0.1 |  †22.3 | 0.1 |  †34.3 | 0.1 |  †49.7 | 0.1 | 0.7
Freq | CBS | 29.9 | 0.1 | 21.2 | 0.1 | 32.8 | 0.1 | 47.5 | 0.0 |  |  |  |
| MBS | 27.9 | 0.1 | 19.6 | 0.2 | 30.4 | 0.2 | 44.4 | 0.1 | DistMult | Base | 0.5 | –
| MIX | 29.7 | 0.1 | 20.9 | 0.1 | 32.6 | 0.1 | 47.5 | 0.1 | 0.1
| Uniq | CBS | 29.2 | 0.0 | 20.4 | 0.1 | 31.9 | 0.0 | 46.7 | 0.1 |  |  |  |
|  | MBS | 27.9 | 0.1 | 19.3 | 0.0 | 30.3 | 0.1 | 45.2 | 0.1 | ComplEx | Base | 0.5 | –
|  | MIX | 29.1 | 0.0 | 20.3 | 0.1 | 31.8 | 0.1 | 46.6 | 0.1 | 0.1

Table 3: Results on FB15k-237. The bold scores are the best results for each
subsampling type (e.g. Base, Freq, and Uniq.). $\dagger$ indicates the best
scores for each model. SD denotes the standard deviation of the three trial.
Sub-model, $\alpha$, and $\lambda$ denote the sub-model, temperature, and
mixing ratio chosen by development data.

WN18RR
---
Model | Subsampling | MRR | H@1 | H@3 | H@10 | Submodeling
Mean | SD | Mean | SD | Mean | SD | Mean | SD | Sub-model | $\alpha$ | $\lambda$
RotatE | None | 47.3 | 0.1 | 42.9 | 0.4 | 48.8 | 0.3 | 55.7 | 0.7 |  |  |  |
Base | CBS | 47.6 | 0.1 |  †43.3 | 0.2 | 49.3 | 0.3 | 56.1 | 0.5 |  |  |  |
| MBS |  †48.0 | 0.0 |  †43.3 | 0.2 | 49.6 | 0.2 |  †57.5 | 0.4 | ComplEx | None | 1.0 | –
| MIX | 47.8 | 0.1 | 43.2 | 0.2 | 49.5 | 0.2 | 57.2 | 0.3 | 0.5
Freq | CBS | 47.7 | 0.1 | 43.2 | 0.3 | 49.5 | 0.3 | 56.9 | 0.9 |  |  |  |
| MBS | 47.9 | 0.1 | 43.2 | 0.2 | 49.6 | 0.2 | 57.4 | 0.4 | ComplEx | None | 0.5 | –
| MIX | 47.9 | 0.1 | 42.9 | 0.1 | 49.8 | 0.1 |  †57.5 | 0.2 | 0.3
| Uniq | CBS | 47.7 | 0.1 | 43.1 | 0.1 | 49.6 | 0.2 | 56.9 | 0.4 |  |  |  |
|  | MBS |  †48.0 | 0.1 | 43.2 | 0.2 |  †49.9 | 0.2 |  †57.5 | 0.2 | ComplEx | None | 0.5 | –
|  | MIX | 47.8 | 0.1 | 43.0 | 0.1 | 49.7 | 0.3 | 57.2 | 0.5 | 0.5
TransE | None | 22.5 | 0.0 | 1.7 | 0.0 | 40.1 | 0.1 | 52.5 | 0.2 |  |  |  |
Base | CBS | 22.3 | 0.1 | 1.3 | 0.1 | 40.1 | 0.2 | 53.0 | 0.0 |  |  |  |
| MBS | 23.7 | 0.1 | 2.5 | 0.1 | 41.2 | 0.2 | 53.1 | 0.1 | ComplEx | Base | 2.0 | –
| MIX | 23.6 | 0.1 | 2.4 | 0.1 | 41.4 | 0.1 | 53.2 | 0.2 | 0.9
Freq | CBS | 23.0 | 0.0 | 1.9 | 0.1 | 40.9 | 0.1 | 53.7 | 0.0 |  |  |  |
| MBS |  †25.0 | 0.1 |  †4.2 | 0.1 | 42.4 | 0.2 | 54.1 | 0.0 | ComplEx | Base | 2.0 | –
| MIX |  †25.0 | 0.1 | 4.0 | 0.2 |  †42.6 | 0.1 |  †54.3 | 0.1 | 0.9
| Uniq | CBS | 23.2 | 0.1 | 2.2 | 0.1 | 40.9 | 0.2 | 53.6 | 0.2 |  |  |  |
|  | MBS | 23.9 | 0.1 | 3.3 | 0.1 | 40.8 | 0.1 | 54.2 | 0.1 | ComplEx | Base | 1.0 | –
|  | MIX | 23.9 | 0.1 | 3.3 | 0.0 | 41.1 | 0.2 | 54.2 | 0.2 | 0.9
HAKE | None | 49.0 | 0.1 | 44.6 | 0.2 | 50.7 | 0.1 | 57.5 | 0.2 |  |  |  |
Base | CBS | 49.6 | 0.0 | 45.1 | 0.2 | 51.5 | 0.2 | 58.2 | 0.1 |  |  |  |
| MBS | 49.2 | 0.1 | 44.7 | 0.1 | 51.0 | 0.3 | 58.0 | 0.1 | ComplEx | None | 0.5 | –
| MIX | 49.5 | 0.1 | 45.0 | 0.2 | 51.4 | 0.2 | 58.2 | 0.1 | 0.1
Freq | CBS | 49.7 | 0.0 | 45.1 | 0.1 | 51.5 | 0.2 | 58.4 | 0.2 |  |  |  |
| MBS |  †49.9 | 0.1 |  †45.4 | 0.1 | 51.7 | 0.2 |  †58.5 | 0.1 | ComplEx | None | 0.5 | –
| MIX |  †49.9 | 0.1 |  †45.4 | 0.1 | 51.7 | 0.2 | 58.4 | 0.3 | 0.9
| Uniq | CBS | 49.7 | 0.1 | 45.2 | 0.2 | 51.6 | 0.2 |  †58.5 | 0.3 |  |  |  |
|  | MBS |  †49.9 | 0.1 |  †45.4 | 0.1 |  †51.8 | 0.2 |  †58.5 | 0.1 | DistMult | None | 0.5 | –
|  | MIX |  †49.9 | 0.1 |  †45.4 | 0.2 |  †51.8 | 0.2 |  †58.5 | 0.1 | 0.7
ComplEx | None | 45.0 | 0.1 | 40.9 | 0.1 | 46.6 | 0.2 | 53.5 | 0.2 |  |  |  |
Base | CBS | 46.9 | 0.1 | 42.6 | 0.1 | 48.7 | 0.2 | 55.3 | 0.2 |  |  |  |
| MBS | 47.3 | 0.2 | 43.4 | 0.1 | 49.1 | 0.1 | 55.5 | 0.4 | ComplEx | None | 2.0 | –
| MIX | 47.3 | 0.2 | 43.4 | 0.1 | 49.1 | 0.1 | 55.5 | 0.4 | 0.7
Freq | CBS | 47.3 | 0.2 | 43.0 | 0.2 | 49.2 | 0.2 | 56.1 | 0.2 |  |  |  |
| MBS |  †48.5 | 0.1 |  †44.6 | 0.1 | 49.9 | 0.3 | 56.5 | 0.2 | ComplEx | None | 0.5 | –
| MIX | 48.4 | 0.2 | 44.4 | 0.1 |  †50.1 | 0.1 |  †56.7 | 0.4 | 0.9
| Uniq | CBS | 47.5 | 0.2 | 43.1 | 0.2 | 49.4 | 0.1 | 56.1 | 0.2 |  |  |  |
|  | MBS | 48.4 | 0.1 | 44.3 | 0.1 | 50.0 | 0.2 | 56.5 | 0.1 | ComplEx | None | 0.5 | –
|  | MIX | 48.4 | 0.1 | 44.2 | 0.2 | 50.0 | 0.2 | 56.6 | 0.2 | 0.9
DistMult | None | 42.5 | 0.1 | 38.3 | 0.1 | 43.6 | 0.0 | 51.2 | 0.1 |  |  |  |
Base | CBS | 43.9 | 0.1 | 39.3 | 0.1 | 45.4 | 0.1 | 53.3 | 0.2 |  |  |  |
| MBS | 44.0 | 0.1 | 40.0 | 0.1 | 44.9 | 0.2 | 52.4 | 0.4 | ComplEx | None | 2.0 | –
| MIX | 44.6 | 0.1 | 40.5 | 0.1 | 45.7 | 0.3 | 53.7 | 0.2 | 0.7
Freq | CBS | 44.5 | 0.1 | 39.9 | 0.2 | 46.0 | 0.2 | 54.3 | 0.2 |  |  |  |
| MBS |  †45.5 | 0.1 |  †41.2 | 0.2 | 46.6 | 0.2 | 54.6 | 0.1 | ComplEx | None | 0.5 | –
| MIX |  †45.5 | 0.1 |  †41.2 | 0.1 |  †46.7 | 0.3 |  †54.7 | 0.1 | 0.9
| Uniq | CBS | 44.8 | 0.1 | 40.1 | 0.2 | 46.3 | 0.3 | 54.5 | 0.2 |  |  |  |
|  | MBS | 45.3 | 0.1 | 41.1 | 0.2 | 46.4 | 0.1 | 54.3 | 0.1 | ComplEx | None | 0.5 | –
|  | MIX | 45.3 | 0.1 | 41.0 | 0.2 | 46.4 | 0.1 | 54.4 | 0.2 | 0.9

Table 4: Results on WN18RR. The notations are the same as the ones in Table 3.

YAGO3-10
---
Model | Subsampling | MRR | H@1 | H@3 | H@10 | Submodeling
Mean | SD | Mean | SD | Mean | SD | Mean | SD | Sub-model | $\alpha$ | $\lambda$
RotatE | None | 49.2 | 0.2 | 39.6 | 0.2 | 55.0 | 0.2 | 67.2 | 0.3 |  |  |  |
Base | CBS | 49.3 | 0.1 | 39.9 | 0.1 | 54.9 | 0.3 | 67.1 | 0.2 |  |  |  |
| MBS | 49.5 | 0.2 | 40.0 | 0.3 | 55.4 | 0.0 | 66.8 | 0.2 | RotatE | None | 0.5 | –
| MIX | 49.8 | 0.1 | 40.4 | 0.2 | 55.6 | 0.2 | 67.2 | 0.3 | 0.7
Freq | CBS | 49.6 | 0.1 | 40.2 | 0.1 | 55.2 | 0.1 | 67.3 | 0.1 |  |  |  |
| MBS | 50.1 | 0.2 |  †41.0 | 0.2 | 55.6 | 0.2 | 67.1 | 0.1 | HAKE | Base | 0.5 | –
| MIX |  †50.2 | 0.2 |  †41.0 | 0.4 |  †55.8 | 0.1 | 67.5 | 0.2 | 0.5
| Uniq | CBS | 49.8 | 0.2 | 40.3 | 0.2 | 55.4 | 0.1 |  †67.6 | 0.1 |  |  |  |
|  | MBS | 49.5 | 0.2 | 39.9 | 0.2 | 55.2 | 0.3 | 67.4 | 0.2 | RotatE | Base | 0.5 | –
|  | MIX | 49.7 | 0.2 | 40.3 | 0.2 | 55.4 | 0.2 | 67.5 | 0.2 | 0.5
HAKE | None | 53.6 | 0.1 | 45.0 | 0.3 | 58.9 | 0.3 | 69.0 | 0.0 |  |  |  |
Base | CBS | 54.3 | 0.1 | 45.9 | 0.2 | 59.6 | 0.2 | 69.3 | 0.1 |  |  |  |
| MBS | 53.6 | 0.3 | 44.9 | 0.4 | 58.9 | 0.2 | 68.8 | 0.1 | HAKE | None | 0.1 | –
| MIX | 54.0 | 0.1 | 45.4 | 0.1 | 59.3 | 0.3 | 69.2 | 0.1 | 0.5
Freq | CBS | 54.5 | 0.3 | 46.1 | 0.3 | 59.8 | 0.5 | 69.4 | 0.3 |  |  |  |
| MBS | 54.8 | 0.1 | 46.5 | 0.2 | 60.0 | 0.3 | 69.7 | 0.1 | RotatE | None | 0.5 | –
| MIX | 54.8 | 0.1 | 46.7 | 0.1 | 59.7 | 0.2 | 69.5 | 0.1 | 0.1
| Uniq | CBS |  †55.1 | 0.1 |  †46.8 | 0.2 |  †60.1 | 0.3 |  †70.0 | 0.2 |  |  |  |
|  | MBS | 54.8 | 0.1 | 46.5 | 0.2 | 60.0 | 0.3 | 69.7 | 0.1 | RotatE | None | 0.5 | –
|  | MIX | 54.9 | 0.1 | 46.6 | 0.1 | 60.0 | 0.2 | 69.9 | 0.2 | 0.3

Table 5: Results on YAGO3-10. The notations are the same as the ones in Table
3.

Figure 3: Appearance probabilities (%) of queries in CBS and MBS that have the
lowest 100 CBS frequencies for each setting, sorted left to right in
descending order by their CBS frequencies.

#### Metrics

We evaluated these methods using the most conventional metrics in KGC, i.e.,
Mean Reciprocal Rank (MRR), Hits@1 (H@1), Hits@3 (H@3), and Hits@10 (H@10). We
reported the average scores in three different runs by changing their
seeds777We fixed seed numbers for the three trials in the training model and
sub-model correspondingly. Note that the appearance probabilities drawn in
Figure 3 all use the same seed. for each metric. We also reported the standard
deviations of the scores by the three runs.

#### Implementations and Hyper-parameters

For RotatE, TransE, ComplEx, and DistMult, we followed the implementations and
hyper-parameters reported by Sun et al. (2019). For HAKE, we inherited the
setting of Zhang et al. (2019).

In our experiments, the performance of subsampling is influenced by the
selection of the following hyper-parameters: (1) temperature $\alpha$; (2)
$\lambda$, the ratio of MBS against CBS. For our proposed MBS subsampling, we
chose $\alpha$ from $\\{2.0,1.0,0.5,0.1,0.05,0.01\\}$ based on validation MRR.
For our proposed MIX subsampling, we inherited the best $\alpha$ in MBS. Then,
we chose the mix ratio $\lambda$ from $\\{0.1,0.3,0.5,0.7,0.9\\}$ based on
validation MRR.

In FB15k-237 and WN18RR, we chose the sub-model from RotatE, TransE, HAKE,
ComplEx, and DistMult with the setting of Base and None based on the
validation MRR. In YAGO3-10, we also chose the sub-model from RotatE and HAKE,
similar to FB15k-237 and WN18RR.

###  4.2 Results

#### Results

Table 3, 4, and 5 show the KGC performances on FB15k-237, WN18RR and YAGO3-10,
respectively. Note that the results of Wilcoxon signed-rank test for
performance differences between MBS/MIX and CBS show statistical significance
with p-values less than 0.01 in all cases when MBS/MIX outperforms CBS.

As we can see, the models trained with MIX or MBS achieved the best results in
all models on FB15k-237 and WN18RR. However, in YAGO3-10, HAKE with Freq in
CBS outperformed the results of MBS and MIX. Considering that the preprocess
of YAGO3-10 filtered out entities with less than 10 relations in the dataset,
we can conclude that MBS and MIX are effective on the sparse KGs like that of
FB15k-237 and WN18RR. These results are along with our expectation that MBS
and MIX can improve the completion performances in sparse KGs as introduced in
§1.

In individual comparison for each metric, CBS sometimes outperformed MIX or
MBS. This is because the estimated frequencies in MIX and MBS rely on selected
sub-models. From these results, we can understand that MIX and MBS have the
potential to improve the KG completion performances by carefully choosing
their sub-model.

#### Analysis

We analyze the remaining question, i.e., which sub-model to choose for MBS.
Table 3, 4, and 5 show the selected sub-models for each MBS (See §4.1 in
details), where ComplEx dominates over other models in FB15k-237 and WN18RR.
To know the reason, we depict MBS frequencies of queries that have the bottom
100 CBS frequencies in Figure 3. In FB15k-237, we can see several spikes of
frequencies in TransE, RotatE, and HAKE that do not exist in ComplEx. In
WN18RR, the peak frequencies of ComplEx with None are larger and broader than
that of other sub-models. These results indicate that models in FB15k-237 and
WN18RR, respectively, encountered problems of an over and lack of smoothing,
and MBS dealt with this problem. Because sparseness is a problem when data is
small, these are along with the fact that FB15k-237 has larger training data
than WN18RR. Thus, choosing a suitable sub-model for a target dataset is
important in MBS.

#### Discussion

We discuss how sub-model and hyper-parameter choices contribute to the
improvement of KGE performance apart from our method. The choice of the sub-
model and the $\alpha$ played significant roles in the observed improvements
because distributions from sub-model prediction depend on each sub-model and
each dataset. Since we adopted the value of $\alpha$ used in the past state-
of-the-art method of Sun et al. (2019) and Zhang et al. (2019), we believe
that the performance gains of MBS are not only caused by the values of
$\alpha$. Similarly, keeping $\lambda$ constant in the MIX strategy may lead
to certain improvements depending on used sub-models and datasets. However, as
shown in Appendix B, $\lambda$ has the role of adjusting the loss of multi-
task learning, and thus, it may be more sensitive compared with $\alpha$.

##  5 Related Work

Mikolov et al. (2013) originally propose the NS loss to train their word
embedding model, word2vec. Trouillon et al. (2016) introduce the NS loss to
KGE to reduce training time. Sun et al. (2019) extend the NS loss for KGE by
introducing a margin term, normalization of negative samples, and newly
proposed their noise distribution. Kamigaito and Hayashi (2021) claim the
importance of dealing with the sparseness problem of KGs through their
theoretical analysis of the NS loss in KGE. Furthermore, Kamigaito and Hayashi
(2022a) reveal that subsampling Mikolov et al. (2013) can alleviate the
sparseness problem in the NS for KGE.

Similar to these works, our work aims to investigate and extend the NS loss
used in KGE to improve KG performance.

##  6 Conclusion

In this paper, we propose new subsampling approaches, MBS and MIX, that can
deal with the problem of low-frequent entity-relation pairs in CBS by
estimating their frequencies using the sub-model prediction. Evaluation
results on FB15k-237 and WN18RR showed the improvement of KGC performances by
MBS and MIX. Furthermore, our analysis also revealed that selecting an
appropriate sub-model for the target dataset is important for improving KGC
performances.

## Limitations

Utilizing our model-based subsampling requires pre-training for choosing a
suitable sub-model, and thus may require more than twice the computational
budget. However, since we can use a small model as a sub-model, like the use
of ComplEx as a sub-model for HAKE, there is a possibility that the actual
computational cost becomes less than the doubled one.

For calculating CBS frequencies, we only use the one with the arithmetic mean
since we inherited the conventional subsampling methods as our baseline. Thus,
we can consider various replacements not covered by this paper for the
operation. However, even if we carefully choose the operation, CBS is
essentially difficult to induce the appropriate appearance probabilities of
low-frequent queries compared with our MBS, which can use vector-space
embedding.

Our experiments are carried out only on FB15k-237, WN18RR, and YAGO3-10
datasets. Thus, whether our method works for larger and noisier data is to be
verified.

Furthermore, although our method is generalizable to deep learning models, our
current work is conducted purely on KGE models, and whether it works for
general deep learning models as well is to be verified.

## Acknowledgements

This work was supported by NAIST Touch Stone, i.e., JST SPRING Grant Number
JPMJSP2140, and JSPS KAKENHI Grant Numbers JP21H05054 and JP23H03458.

## References

  * Bordes et al. (2013) Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. 2013.  Translating embeddings for modeling multi-relational data.  In _Advances in Neural Information Processing Systems_ , volume 26. Curran Associates, Inc.
  * Dettmers et al. (2018) Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. 2018.  Convolutional 2d knowledge graph embeddings.  In _AAAI_.
  * Guan et al. (2019) Jian Guan, Yansen Wang, and Minlie Huang. 2019.  Story ending generation with incremental encoding and commonsense knowledge.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 33(01):6473–6480.
  * Kamigaito and Hayashi (2021) Hidetaka Kamigaito and Katsuhiko Hayashi. 2021.  Unified interpretation of softmax cross-entropy and negative sampling: With case study for knowledge graph embedding.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 5517–5531, Online. Association for Computational Linguistics.
  * Kamigaito and Hayashi (2022a) Hidetaka Kamigaito and Katsuhiko Hayashi. 2022a.  Comprehensive analysis of negative sampling in knowledge graph representation learning.  In _Proceedings of the 39th International Conference on Machine Learning_ , volume 162 of _Proceedings of Machine Learning Research_ , pages 10661–10675. PMLR.
  * Kamigaito and Hayashi (2022b) Hidetaka Kamigaito and Katsuhiko Hayashi. 2022b.  Subsampling for knowledge graph embedding explained.
  * Katz (1987) Slava Katz. 1987.  Estimation of probabilities from sparse data for the language model component of a speech recognizer.  _IEEE transactions on acoustics, speech, and signal processing_ , 35(3):400–401.
  * Lukovnikov et al. (2017) Denis Lukovnikov, Asja Fischer, Jens Lehmann, and Sören Auer. 2017.  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, page 1211–1220, Republic and Canton of Geneva, CHE. International World Wide Web Conferences Steering Committee.
  * Mikolov et al. (2013) Tomás Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013\.  Distributed representations of words and phrases and their compositionality.  _CoRR_ , abs/1310.4546.
  * Moon et al. (2019) Seungwhan Moon, Pararth Shah, Anuj Kumar, and Rajen Subba. 2019.  OpenDialKG: Explainable conversational reasoning with attention-based walks over knowledge graphs.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 845–854, Florence, Italy. Association for Computational Linguistics.
  * Neubig and Dyer (2016) Graham Neubig and Chris Dyer. 2016.  Generalizing and hybridizing count-based and neural language models.  In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing_ , pages 1163–1172, Austin, Texas. Association for Computational Linguistics.
  * Sun et al. (2019) Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang. 2019.  Rotate: Knowledge graph embedding by relational rotation in complex space.  In _Proceedings of the 7th International Conference on Learning Representations, ICLR 2019_.
  * Toutanova and Chen (2015) Kristina Toutanova and Danqi Chen. 2015.  Observed versus latent features for knowledge base and text inference.  In _Proceedings of the 3rd Workshop on Continuous Vector Space Models and their Compositionality_ , pages 57–66, Beijing, China. Association for Computational Linguistics.
  * Trouillon et al. (2016) Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. 2016.  Complex embeddings for simple link prediction.  _CoRR_ , abs/1606.06357.
  * Yang et al. (2015) Bishan Yang, Wen tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. 2015.  Embedding entities and relations for learning and inference in knowledge bases.
  * Zhang et al. (2019) Zhanqiu Zhang, Jianyu Cai, Yongdong Zhang, and Jie Wang. 2019.  Learning hierarchy-aware knowledge graph embeddings for link prediction.

##  Appendix A Note on Figure 2

To illustrate the results on FB15k-237 and WN18RR datasets, we used TransE,
RotatE, ComplEx, DistMult, and HAKE as the KGE models. To plot that on the
YAGO3-10 dataset, we used RotatE and HAKE as the KGE models following the
setting in §4.1. Regarding the use of subsampling, the MRR scores of using
subsampling refer to the result of Base subsampling in Table 1 with CBS
frequencies, whereas that without subsampling corresponds to the setting
"None" §4.1.

##  Appendix B Interpretation of MIX Subsampling as Multi-task Learning

We can reformulate Eq. (16) as follows:

$\displaystyle\ell_{mix}(\mathbf{\theta};\mathbf{\theta}^{\prime})$ (19)
$\displaystyle=$ $\displaystyle-\frac{1}{|D|}\sum_{(x,y)\in
D}\Bigl{[}A_{mix}(\mathbf{\theta}^{\prime})\log(\sigma(s_{\mathbf{\theta}}(x,y)+\gamma))+\frac{1}{\nu}\\!\\!\\!\\!\\!\\!\sum_{y_{i}\sim
p_{n}(y_{i}|x)}^{\nu}\\!\\!\\!\\!\\!\\!B_{mix}(\mathbf{\theta}^{\prime})\log(\sigma(-s_{\mathbf{\theta}}(x,y_{i})-\gamma))\Bigr{]},$
(20) $\displaystyle=$ $\displaystyle-\frac{1}{|D|}\sum_{(x,y)\in
D}\Bigl{[}(\lambda
A_{mbs}(\mathbf{\theta}^{\prime})+(1-\lambda)A_{cbs})\log(\sigma(s_{\mathbf{\theta}}(x,y)+\gamma))$
$\displaystyle+\frac{1}{\nu}\\!\\!\\!\\!\\!\\!\sum_{y_{i}\sim
p_{n}(y_{i}|x)}^{\nu}\\!\\!\\!\\!\\!\\!(\lambda
B_{mbs}(\mathbf{\theta}^{\prime})+(1-\lambda)B_{cbs})\log(\sigma(-s_{\mathbf{\theta}}(x,y_{i})-\gamma))\Bigr{]},$
(21) $\displaystyle=$ $\displaystyle-\frac{\lambda}{|D|}\sum_{(x,y)\in
D}\Bigl{[}A_{mbs}(\mathbf{\theta}^{\prime})\log(\sigma(s_{\mathbf{\theta}}(x,y)+\gamma))+\frac{1}{\nu}\\!\\!\\!\\!\\!\\!\sum_{y_{i}\sim
p_{n}(y_{i}|x)}^{\nu}\\!\\!\\!\\!\\!\\!B_{mbs}(\mathbf{\theta}^{\prime})\log(\sigma(-s_{\mathbf{\theta}}(x,y_{i})-\gamma))\Bigr{]},$
$\displaystyle-\frac{1-\lambda}{|D|}\sum_{(x,y)\in
D}\Bigl{[}A_{cbs}\log(\sigma(s_{\mathbf{\theta}}(x,y)+\gamma))+\frac{1}{\nu}\\!\\!\\!\\!\\!\\!\sum_{y_{i}\sim
p_{n}(y_{i}|x)}^{\nu}\\!\\!\\!\\!\\!\\!B_{cbs}\log(\sigma(-s_{\mathbf{\theta}}(x,y_{i})-\gamma))\Bigr{]},$
(22) $\displaystyle=$
$\displaystyle\lambda\ell_{mbs}(\mathbf{\theta};\mathbf{\theta}^{\prime})+(1-\lambda)\ell_{cbs}(\mathbf{\theta})$
(23)

From Eq. (23), since $\ell_{mix}(\mathbf{\theta};\mathbf{\theta}^{\prime})$ is
the mixed loss of the two loss functions
$\ell_{mbs}(\mathbf{\theta};\mathbf{\theta}^{\prime})$ and
$\ell_{cbs}(\mathbf{\theta})$, we can understand that using MIX is multi-task
learning of using both CBS and MBS.