# Learning Moving-Object Tracking with FMCW LiDAR

Yi Gu1, Hongzhi Cheng1, Kafeng Wang2, Dejing Dou3, Chengzhong Xu1∗ and Hui
Kong1∗ The Doppler LiDAR data were provided by Guangshao
Technology.∗Corresponding author.1Yi Gu, Hongzhi Cheng, Hui Kong and
Chengzhong Xu are with Faculty of Science and Technology, University of Macau,
Taipa, Macau, China. {yc17463; hongzhicheng; huikong<EMAIL_ADDRESS>Wang is with Shenzhen Institute of Advanced Technology, Chinese Academy of
Sciences and University of Chinese Academy of Sciences.
<EMAIL_ADDRESS>Dou is with Baidu Research.

###### Abstract

In this paper, we propose a learning-based moving-object tracking method
utilizing our newly developed LiDAR sensor, Frequency Modulated Continuous
Wave (FMCW) LiDAR. Compared with most existing commercial LiDAR sensors, our
FMCW LiDAR can provide additional Doppler velocity information to each 3D
point of the point clouds. Benefiting from this, we can generate instance
labels as ground truth in a semi-automatic manner. Given the labels, we
propose a contrastive learning framework, which pulls together the features
from the same instance in embedding space and pushes apart the features from
different instances, to improve the tracking quality. Extensive experiments
are conducted on our recorded driving data, and the results show that our
method outperforms the baseline methods by a large margin.

##  I INTRODUCTION

Multi-Object Tracking (MOT) is a significant module in modern autonomous
driving pipelines. As one of the key tasks of MOT, moving-object tracking can
strongly affect the local planning strategy of the ego-vehicle. With this
consideration, we only focus on tracking moving objects in this work. In the
literature, most state-of-the-art (SOTA) MOT algorithms are based on deep
learning techniques, and require detection or segmentation results. For
example, the recent MOT methods [1, 2] require to detect objects first, and
then associate detections across frames. The training processes of these
methods need the bounding box labels for the moving targets in each LiDAR
frame. The 4D Panoptic LiDAR Segmentation (4D-PLS) [3] is based on a tracking-
by-segmentation paradigm and has shown remarkable performance in the LiDAR-
based MOT task. However, the labeling of the segmentation task is more
expensive, even with many advanced tools [4].

Basically, these methods require a large amount of manual annotations to train
a deep neural network in a supervised way, and may not generalize well in
scenes beyond the training set. Typically, there are two strategies to
overcome this problem. One strategy is to investigate how to utilize data
efficiently or how to train a model with less supervision, such as self-
supervised learning [5, 6], weakly supervised learning [7], few-shot learning
[8], etc.

The other potential strategy to solve this problem is from sensor innovation
or fusion perspective, since it can usually provide extra information acting
as a kind of self-supervision during model training. Our work belongs to this
route, where we utilize our newly developed FMCW LiDAR to track moving objects
in a deep learning paradigm. Our target is to accomplish this task with as
little manual-labeling effort as possible.

The major difference of FMCW LiDAR from most existing LiDAR sensors lies in
its supplement of speed information in addition to the 3D coordinates of the
point cloud. Its basic principle is based on the Doppler effect that can
provide the measurement of relative velocity between each sensed 3D world
point to the FMCW LiDAR sensor along the radial direction. Figure 1 shows a
certain frame of FMCW LiDAR point cloud with and without velocity information,
respectively.

(a) Point clouds with velocity

(b) Original 3D point clouds.

Figure 1: Visual comparison of the FMCW LiDAR measurements and the range-only
measurements. We use the HSI color model to visualize the velocity. Hue values
in (a) are arranged by the Doppler velocity. A lower hue indicates faster
speed towards the sensor.

In contrast to the above-mentioned methods, the advantages of using the FMCW
LiDAR are reflected in two aspects. The first one is to reduce the cost of
data labeling, and the other is to provide the motion cue for data
association.

In our work, we are devoted to fully utilizing these two advantages of the
FMCW LiDAR. The first stage of our method is data labeling, a semi-automatic
annotation process. Specifically, we initially separate static points from
dynamic ones with velocity information. Within each LiDAR frame, a clustering
algorithm [9] is applied to the moving points to get each individual moving
cluster. Then data association is carried out on the moving clusters with
estimated ego-motion and position (velocity) compensation.

As shown in Figure 2(a), with the estimated ego-motion information (by a LiDAR
SLAM algorithm for our case), the segmented moving clusters across multiple
frames can be aligned to a reference frame (set as the current frame). As
shown in Figure 2(b), based on position compensation with velocity information
on each cluster, we can further align each cluster so that the clusters
corresponding to the same object are aggregated, where the initial data
association can be achieved based on the distance between the centers of the
aggregated clusters. It is observed that data association can be established
for most cases in this way. But the density parameter of clustering and the
distance threshold need to be tuned scene-by-scene. We annotate our dataset by
manually tuning these hyper-parameters. After that, each point is assigned an
instance ID without semantic class label. Note that the cost of this semi-
automatic annotation process is far less than the per-point annotations and
bounding box annotations.

(a)

(b)

Figure 2: The illustration of the position compensation. (a) is the result of
clustering in each frame and aligned in the current frame. (b) is the result
of the position compensation according to the velocity of each cluster.

With the above ground-truth labels, we can train an end-to-end model to track
the moving objects. Generally, it is not robust to track objects with only
instance-level supervision. We propose a contrastive learning framework to
make the features belonging to the same instance close and the features from
different instances apart. With these high-quality features, we can track the
instances across time simply by calculating the association probabilities of
their points.

In summary, our main contributions are of two folds:

  * •

We present the first deep learning based method on moving-object tracking with
the FMCW LiDAR. We propose a contrastive learning framework to make full use
of the instance-only supervision.

  * •

Our semi-automatic annotation method with FMCW LiDAR can significantly reduce
the labeling costs, which can motivate more related works based on newly
developed sensors.

##  II RELATED WORK

Figure 3: An overview of our moving-object tracking pipeline (window size
$\tau=4$ for illustration).

###  II-A FMCW LiDAR

FMCW LiDAR is a newly developed type of ranging sensors and was first
researched in wind measurements [10]. Compared with other popular LiDAR
schemes, the scheme of FMCW LiDAR makes it able to measure the relative
velocity (Doppler velocity) of each scanned point with respect to the sensor
along the radial direction by the Doppler effect [11]. Since this kind of
LiDAR sensors is seldom available, there are few related works specifically on
perception. Recently, DICP [11] presented a novel method for point cloud
registration by using Aeva’s Aeries I FMCW LiDAR. Guo et al. [12] proposed a
clustering and velocity estimation method based on Doppler velocity with CARLA
[13] simulation. Jie Shan et al. [14, 15] proposed detection and tracking
methods based on hand-crafted features with Kalman filter to estimate the
state of moving objects by using Blackmore FMCW LiDAR. Their methods are not
based on deep learning, simple and efficient, but in low accuracy.

###  II-B 3D Multi-Object Tracking

The dominant methods in this field exploit the tracking-by-detection paradigm,
which detects objects first, then associates detections across time. The
association step is usually formulated as a bipartite matching problem, where
the key to matching relies on the appearance and motion models. Most of the
LiDAR-based tracking methods hinge on the motion for association due to the
lack of the texture cue. For example, CenterPoint [1] achieved this by
estimating the velocity of each object. Other methods [16, 2] exploited
appearance information from camera to enhance the association quality.
SimTrack [17] avoided heuristic matching step by joint detection and tracking
in an end-to-end manner. It detects objects in bird-eye-view and predicts the
offset of each object directly. Its association step can be finished with a
simple lookup operation. However, all these methods require bounding box
annotations for detection.

MOTS [18] proposed the multi-object tracking and segmentation task for the
first time and MOTP [19] extended it to panoptic segmentation and 3D domain.
4D-PLS [3] explored tracking-by-segmentation paradigm, which can associate
objects at point level. The core of 4D-PLS is the density-based clustering,
which benefits from their semantic features. Our method can be sorted into
this category. But in our dataset, there are only instance annotations without
semantic labeling, which is more challenging than previous works.

###  II-C Contrastive Learning

Contrastive learning based methods have dominated self-pretraining in vision
in recent years [5, 20]. The main idea of contrastive learning is the
following: pull together an anchor and a ”positive” sample in embedding space,
and push apart the anchor from many ”negative” samples [21]. In the self-
supervised learning domain, there are no labels available. The positive
samples are usually drawn from data augmentations, and the negative pairs are
formed by the anchor and remaining samples in the mini-batch. When labels are
available, a similar idea can also be applied in the supervised learning
scheme with different loss functions, such as Triplet Loss [22, 23], N-pairs
Loss [24] and Supervised Contrastive Loss [21]. Recently, Marcuzzi et al. [25]
proposed to use contrastive learning to make instance association, which is
similar to our work. The difference is that we only utilize the instance
information, while their method also requires semantic information.

##  III Method

The goal of our approach is to track the moving objects across different
times. To achieve this, we first annotate our data by Heuristic Tracking (See
Sec. III-A), which is a semi-automatic process and can provide us high-quality
labeled data as ground truth. Thereafter, we train a deep neural network to
achieve better performance (See Sec. III-B). Due to lack of the supervision
from semantic class labels, we utilize the contrastive learning method to
improve the effectiveness of the association (See Sec. III-C). Figure 3 is the
overview of our pipeline.

###  III-A Heuristic Tracking

We first filter out the abnormal points such as geometry outliers and those
with unrealistic velocity values. Then we separate dynamic and static points
apart according to the ego velocity $V_{car}$. As this value is not recorded
in our dataset, we estimate it by the mean velocity of the ground points in
front view, noted as $V_{g}$, which is theoretically equal to $-V_{car}$. The
ground points are extracted via the RANSAC [26] algorithm. We treat the points
whose velocities are within $V_{g}\pm V_{m}$ as static points, where $V_{m}$
is a constant value and is set to 0.2 $m/s$ in our experiments. Then the
remaining points are dynamic points. Henceforth, we only focus on these moving
points.

Since there are no bounding boxes nor instance segmentation masks, we need to
define the concept of the object first. We apply DBSCAN [9] to cluster the
moving points so that each cluster can be treated as an object. Though most of
our cases can be successfully clustered, there are still some objects that
failed to be separated out, which need to be further tuned by adjusting the
density parameter of DBSCAN.

To track across the frames, we compensate the position of each cluster with
the mean velocity of its own points. More specifically, for a window of $\tau$
frames at times $\\{max(0,t+1-\tau),...,t\\}$, we first align them to the
current frame $t$ according to the ego-motion estimation results provided by a
SLAM approach [27]. As we operate in consecutive frames and the window time
duration in our experiments is less than 1 $s$, we can treat the motion of
each object as uniform motion during this period. In this way, we can
compensate the position of each cluster by computing the relative displacement
and translating the corresponding points to simplify the association, as shown
in Figure 2. Ideally, the points from the same object instance can be
aggregated together so that we can do association by nearest neighbor query,
accompanied by a distance threshold, $d_{N}$. That is to say, if two clusters
at different times are nearest neighbors after shifting and the distance
between them is within the threshold $d_{N}$, we consider them as the same
instance. To make this operation more robust, we represent the position of
each cluster by its centroid in the bird-eye-view to eliminate the height
error.

###  III-B 4D-PLS Review

We annotate our data based on Heuristic Tracking (See IV-B2 for details). With
the obtained ground-truth labels, we are able to train a neural network to
further improve the tracking quality. We build up our model based on the
4D-PLS [3] architecture. We will review the 4D-PLS first in this subsection
and introduce our modifications in the next one.

The input of the 4D-PLS is a 4D volume, which contains consecutive frames of
point clouds in a time window, aligned to the current frame. The main
component of the model is the density-based clustering by the following
equation,

$\hat{p}_{ij}=\frac{1}{(2\pi)^{\frac{D}{2}}|\Sigma_{i}|^{\frac{1}{2}}}exp(-\frac{1}{2}(e_{i}-e_{j})^{T}\Sigma_{i}^{-1}(e_{i}-e_{j})),$
(1)

where $\hat{p}_{ij}$ is the probability of the two points $p_{i}$ and $p_{j}$
belonging to the same instance. $e_{i}\in\mathbb{R}^{D}$ is the embedding of
the $p_{i}$. Note that in this formulation, $p_{i}$ should be the instance
center approximation. So $\Sigma_{i}$ is the variance matrix of $p_{i}$.

Therefore, the outputs of the 4D-PLS [3] are semantic class, objectness,
variance and point embedding. Here the objectness is a scalar used to assess
how close each point is to its instance center.

###  III-C Contrastive Moving-Object Tracking

There are two drawbacks if we directly use the original 4D-PLS [3]. The first
one lies in the window size limitation. Longer temporal windows can aggregate
more information, while the Gaussian assumption is only valid for shorter
temporal windows in 4D-PLS. Besides, since we discard the static points and
only focus on the moving points, a small window size is not efficient. Thanks
to the superiority of velocity information, this problem can be solved simply
by the position compensation described before. After that, the Gaussian
assumption can be valid for longer temporal windows. We validate this
conclusion in our ablation studies.

Another problem is that our dataset has no bounding box labels nor semantic
labels needed in 4D-PLS, and only the above obtained instance IDs can be used
for supervised learning. It is hard to associate the points at different times
without a strong semantic cue. We tried to apply 4D-PLS with only instance
level supervision, where the objectness loss and instance loss are defined as:

$L_{obj}=\sum\limits_{i=1}^{N}({\hat{o}_{i}}-{o}_{i})^{2},\quad\hat{o}_{i},o_{i}\in[0,1]$
(2) $\displaystyle
L_{ins}=\sum\limits_{j=1}^{K}\sum\limits_{i=1}^{N}({\hat{p}_{ij}}-p_{ij})^{2},\quad
p_{ij}=\begin{cases}1,&\mbox{if $p_{i}\in{I_{j}}$};\\\
0,&\mbox{otherwise}.\end{cases}$ (3)

In the above losses, notations are defined as follows: N is the number of
points; $K$ is the number of instances in the current time window; $I_{j}$
represents the point set of the $j$-th instance; ${\hat{o}_{i}}$ is the
approximation to the instance objectness ${o}_{i}$ after position
compensation. Note that since the clusters from the same instance have been
aggregated, we obtain the ground-truth objectness according to the instance
center, while in 4D-PLS, it is calculated for each cluster.

This method does not work well in our experiments (See Table II and Figure 4
for better comparison). Due to the lack of ground-truth class labels, we
cannot rely on semantic information to obtain the class related features,
which are considerably helpful for the association step.

Besides the motion cue, the appearance of the instance is also an important
cue that can be explored further [17, 2]. It means that the clusters from the
same instance should be similar, while from different instances should be
distinct. Inspired by this hint, we propose to train a class-agnostic model in
a contrastive learning paradigm [5, 21]. More specifically, we make use of the
supervised contrastive learning [21] loss to further utilize the instance ID
information. We represent each instance at each timestamp, i.e., each cluster,
by its global feature $z_{i}$. Following Pointnet [28], we obtain this global
feature $z_{i}$ by applying a symmetric function on all embeddings of its
points:

$z_{i}=f(x_{i1},...,x_{in})\approx g(e_{i1},...,e_{in}),$ (4)

where $x_{ij}$ is the $j$-th point of the cluster $i$ and $e_{ij}$ is its
corresponding feature embedding. We define that the positive samples are
clusters from the same instance and the negative samples are those from
different instances.

After that, we can use the following expression to compute the loss:

$L_{SC}=\sum\limits_{i\in N}\frac{-1}{|P(i)|}\sum\limits_{p\in
P(i)}log\frac{exp(z_{i}\cdot z_{p}/\tau)}{\sum\limits_{a\in
A(i)}exp(z_{i}\cdot z_{a}/\tau)},$ (5)

where $N$ is the number of clusters. $A(i)$ is the index set of all the
clusters within the window except $i$. $P(i)$ is the index set of the clusters
from the same instance as $i$.

As for inference, we follow the 4D-PLS to associate points in two stages. For
the first stage, we select the point $p_{i}$ which has the highest objectness
score as the instance center proxy. Then, we do the density-based clustering
for all candidate points. If $p_{ij}>p_{threshold}$, we assign it to the
instance of $p_{i}$ and remove it from candidate points. These steps are
repeated until all points are clustered. For the second stage, we perform
cross-volume association greedily based on the overlap score. When the overlap
is below a threshold, we assign a new ID.

##  IV Experiments

###  IV-A Dataset

We utilize the latest Guangshao 2.0 FMCW LiDAR to collect our data. The
horizontal field-of-view of our LiDAR is $37.5^{\circ}$, and the vertical
field-of-view is $16.7^{\circ}$. The maximum perceived range is $300$ $m$. The
precision of the velocity measurement is $5$ $cm/s$. The sampling rate is $10$
$Hz$. The data were collected in seven different scenes, 5 from highway and 2
from urban scenes. Each scene contains 300-500 frames after sampling and all
data contain 3200 frames in total. We use 2400 scannings as the training set
and the left as the test set.

(a) Ground Truth

(b) Ours

(c) 4D-PLS [3] \+ PC

(d) Vanilla 4D-PLS [3]

Figure 4: Qualitative comparison of our method with baseline methods. We show
the tracking results for 4 frames (top row) and 10 frames (bottom row). PC
means Position Compensation. The areas with significant differences are
enlarged for better comparison.

###  IV-B Implementation Details

####  IV-B1 Ego-motion Estimation

We first filter out the outlier points as mentioned in section III-A. In
addition, we also remove the ground points estimated by RANSAC [26], since the
points with special pattern scanned on the ground may lead to bad registration
results. We use the modified LOAM [27] to get the ego-pose information.
Specifically, we only use the static points to do the registration. We
initialize the translation between the two frames by ego-velocity
compensation. Other more robust registration methods, such as DICP [11], can
be explored in future work. Figure 5(a) shows the local map built by our FMCW
LiDAR data.

(a)

(b)

Figure 5: (a) is the local map by SLAM [27] with only static non-ground points
reserved. (b) is the corresponding image in front view. Note that the dynamic
cars are filtered out in static map.

####  IV-B2 Semi-Automatic Annotation

We use DBSCAN [9] to cluster the moving points. The default density parameter
is set as $1.2$, and the minimum number of points in each cluster is $20$. If
there are less than 20 points in a cluster, we filter out these points. We
double-check the results by both nearest neighbor query and cluster again
after position compensation. After that, we manually check the correctness.
For those failing and wrongly labeled data, we re-label them by hand.

####  IV-B3 Network Detail and Loss functions

Since the position of each cluster has been compensated, our method is not
sensitive to the window size $\tau$. We validate this by choosing different
window sizes (4, 6, 8, and 10) in our experiments.

We use KPConv [29] as our backbone and the complete loss function is set as:

$L=L_{SC}+\lambda_{ins}L_{ins}+\lambda_{var}L_{var}+L_{obj}+L_{reg},$ (6)

where $L_{reg}$ is the regression loss from KPConv [29], and $L_{var}$ is the
variance smoothness loss similar to 4D-PLS [3]. We set the $\lambda_{ins}$ and
$\lambda_{var}$ as $0.01$ in our experiments. And as the KPConv has provided
the per-point embeddings, we can extract instance features by directly using a
max-pooling operation, which is better than the other symmetric functions.

We find that $p_{threshold}=0.4$ can get the best performance. The overlap
threshold is set as $0.8$, which has a trivial effect on the final results.
Note that these hyper-parameters are not changed after configuration, while
the hyper-parameters in Heuristic Tracking need to be tuned scene-by-scene.

TABLE I: Comparison of our method with baseline methods. PC means Position Compensation. Method | AS | MOTSA | MOTSP | SMOTSA
---|---|---|---|---
Heuristic Tracking | 54.18 | 82.55 | 84.15 | 77.24
Vanilla 4D-PLS [3] | 59.55 | 80.68 | 84.87 | 76.03
4D-PLS [3] \+ PC | 84.07 | 88.42 | 87.02 | 85.97
Ours | 87.89 | 89.44 | 89.07 | 89.04

###  IV-C Evaluation Metrics

Since we have no class labels, we choose the following metrics [18, 3] which
are only related to instance IDs, to make a fair comparison with the baseline
methods: multi-object tracking and segmentation accuracy (MOTSA), multi-object
tracking and segmentation precision (MOTSP), soft multi-object tracking and
segmentation accuracy (SMOTSA) and association score (AS). In all of these
metrics, larger values indicate better performance.

We follow the MOTS [18] to define the set of True Positives (TP), False
Positives (FP), False Negatives (FN) and ID switch (IDS) to compute the MOTSA,
MOTSP and SMOTSA. For AS, we follow the 4D-PLS [3] to define the TP, FP, and
FN, which can be seen as a soft version of that in MOTS. In consideration that
Association Score can evaluate the association in space and time in a more
unified manner, we treat AS as the main evaluation indicator.

###  IV-D Results

We compare our method with two baselines: heuristic tracking and 4D-PLS [3].
We reimplement the 4D-PLS on our dataset, without semantic output. Since
4D-PLS is sensitive to the window size, we also add position compensation to
4D-PLS to compare with our method. As for heuristic tracking, we follow our
semi-automatic annotation process without human interactions. We test several
sets of hyper-parameters and choose the results with the best performance.
Table I shows the results of our method and baseline methods. Obviously, our
method achieves the best results and generalizes well in most cases. Figure 4
is the qualitative comparison of our method with baselines. Our method is more
consistent in association step. It is worth mentioning that these results are
not cherry-picked.

###  IV-E Ablation studies

The velocity of points within the same instance should be close, which is also
a strong cue for the association. Thus, we conduct experiments on whether to
input the velocity channel. The results in Table II show that there is a
slight improvement with velocity as input.

Since our method has compensated for the position of each cluster, our model
is not sensitive to the window size. But the window size cannot be too large,
since the memory is limited and the uniform motion assumption cannot hold for
large window sizes. We conduct ablation study on the window size, with
$\tau=4,6,8,10$. Table III shows that there is no obvious difference in the
performance.

TABLE II: Ablation study on input format Method | AS | MOTSA | MOTSP | SMOTSA
---|---|---|---|---
xyz | 87.03 | 89.48 | 88.94 | 88.95
xyz+v | 87.89 | 89.44 | 89.07 | 89.04
TABLE III: Ablation study on window size Method | AS | MOTSA | MOTSP | SMOTSA
---|---|---|---|---
4 scans | 87.89 | 89.44 | 89.07 | 89.04
6 scans | 86.25 | 89.14 | 89.02 | 88.94
8 scans | 86.47 | 89.16 | 88.94 | 88.62
10 scans | 86.54 | 89.31 | 89.19 | 89.02

##  V CONCLUSIONS

In this paper, we present a method of moving-object tracking based on the
latest FMCW LiDAR sensor. To the best of our knowledge, it is the first work
ever conducted on moving-object tracking with the FMCW LiDAR in a learning
scheme. We propose a contrastive learning framework to make full use of the
instance-only supervision, which can significantly improve the tracking
quality. Our whole pipeline requires far less annotation effort than most
existing works, e.g., MOT and MOTS, which require bounding box labels or per-
point semantic labels. The results show that our method can surpass the
baseline methods by a large margin. We hope our work can motivate more
revolutionary works based on the FMCW LiDAR.

## References

  * [1] T. Yin, X. Zhou, and P. Krahenbuhl, “Center-based 3d object detection and tracking,” in _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , 2021, pp. 11 784–11 793.
  * [2] Y. Zeng, C. Ma, M. Zhu, Z. Fan, and X. Yang, “Cross-modal 3d object detection and tracking for auto-driving,” in _2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2021, pp. 3850–3857.
  * [3] M. Aygun, A. Osep, M. Weber, M. Maximov, C. Stachniss, J. Behley, and L. Leal-Taixé, “4d panoptic lidar segmentation,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2021, pp. 5527–5537.
  * [4] D. Bloembergen and C. Eijgenstein, “Automatic labelling of urban point clouds using data fusion,” _arXiv preprint arXiv:2108.13757_ , 2021.
  * [5] K. He, H. Fan, Y. Wu, S. Xie, and R. Girshick, “Momentum contrast for unsupervised visual representation learning,” in _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , 2020, pp. 9729–9738.
  * [6] K. He, X. Chen, S. Xie, Y. Li, P. Dollár, and R. Girshick, “Masked autoencoders are scalable vision learners,” _arXiv preprint arXiv:2111.06377_ , 2021.
  * [7] Z.-H. Zhou, “A brief introduction to weakly supervised learning,” _National science review_ , vol. 5, no. 1, pp. 44–53, 2018.
  * [8] J. Snell, K. Swersky, and R. Zemel, “Prototypical networks for few-shot learning,” _Advances in neural information processing systems_ , vol. 30, 2017.
  * [9] M. Ester, H.-P. Kriegel, J. Sander, X. Xu, _et al._ , “A density-based algorithm for discovering clusters in large spatial databases with noise.” in _kdd_ , vol. 96, no. 34, 1996, pp. 226–231.
  * [10] M. L. Chanin, A. Garnier, A. Hauchecorne, and J. Porteneuve, “A doppler lidar for measuring winds in the middle atmosphere,” _Geophysical Research Letters_ , vol. 16, no. 11, pp. 1273–1276, 1989.
  * [11] B. Hexsel, H. Vhavle, and Y. Chen, “Dicp: Doppler iterative closest point algorithm,” _arXiv preprint arXiv:2201.11944_ , 2022.
  * [12] M. Guo, K. Zhong, and X. Wang, “Doppler velocity-based algorithm for clustering and velocity estimation of moving objects,” _arXiv preprint arXiv:2112.12984_ , 2021.
  * [13] A. Dosovitskiy, G. Ros, F. Codevilla, A. Lopez, and V. Koltun, “Carla: An open urban driving simulator,” in _Conference on robot learning_. PMLR, 2017, pp. 1–16.
  * [14] Y. Ma, J. Anderson, S. Crouch, and J. Shan, “Moving object detection and tracking with doppler lidar,” _Remote Sensing_ , vol. 11, no. 10, p. 1154, 2019.
  * [15] X. Peng and J. Shan, “Detection and tracking of pedestrians using doppler lidar,” _Remote Sensing_ , vol. 13, no. 15, p. 2952, 2021.
  * [16] H.-k. Chiu, J. Li, R. Ambruş, and J. Bohg, “Probabilistic 3d multi-modal, multi-object tracking for autonomous driving,” in _2021 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2021, pp. 14 227–14 233.
  * [17] C. Luo, X. Yang, and A. Yuille, “Exploring simple 3d multi-object tracking for autonomous driving,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021, pp. 10 488–10 497.
  * [18] P. Voigtlaender, M. Krause, A. Osep, J. Luiten, B. B. G. Sekar, A. Geiger, and B. Leibe, “Mots: Multi-object tracking and segmentation,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2019, pp. 7942–7951.
  * [19] J. V. Hurtado, R. Mohan, W. Burgard, and A. Valada, “Mopt: Multi-object panoptic tracking,” _arXiv preprint arXiv:2004.08189_ , 2020.
  * [20] T. Chen, S. Kornblith, M. Norouzi, and G. Hinton, “A simple framework for contrastive learning of visual representations,” in _International conference on machine learning_. PMLR, 2020, pp. 1597–1607.
  * [21] P. Khosla, P. Teterwak, C. Wang, A. Sarna, Y. Tian, P. Isola, A. Maschinot, C. Liu, and D. Krishnan, “Supervised contrastive learning,” _Advances in Neural Information Processing Systems_ , vol. 33, pp. 18 661–18 673, 2020\.
  * [22] K. Q. Weinberger and L. K. Saul, “Distance metric learning for large margin nearest neighbor classification.” _Journal of machine learning research_ , vol. 10, no. 2, 2009.
  * [23] F. Schroff, D. Kalenichenko, and J. Philbin, “Facenet: A unified embedding for face recognition and clustering,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2015, pp. 815–823.
  * [24] K. Sohn, “Improved deep metric learning with multi-class n-pair loss objective,” _Advances in neural information processing systems_ , vol. 29, 2016.
  * [25] R. Marcuzzi, L. Nunes, L. Wiesmann, I. Vizzo, J. Behley, and C. Stachniss, “Contrastive instance association for 4d panoptic segmentation using sequences of 3d lidar scans,” _IEEE Robotics and Automation Letters_ , 2022\.
  * [26] M. A. Fischler and R. C. Bolles, “Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography,” _Communications of the ACM_ , vol. 24, no. 6, pp. 381–395, 1981.
  * [27] J. Zhang and S. Singh, “Loam: Lidar odometry and mapping in real-time.” in _Robotics: Science and Systems_ , vol. 2, no. 9. Berkeley, CA, 2014, pp. 1–9.
  * [28] C. R. Qi, H. Su, K. Mo, and L. J. Guibas, “Pointnet: Deep learning on point sets for 3d classification and segmentation,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2017, pp. 652–660.
  * [29] H. Thomas, C. R. Qi, J.-E. Deschaud, B. Marcotegui, F. Goulette, and L. J. Guibas, “Kpconv: Flexible and deformable convolution for point clouds,” in _Proceedings of the IEEE/CVF international conference on computer vision_ , 2019, pp. 6411–6420.


# CORE: A Knowledge Graph Entity Type Prediction Method via Complex Space
Regression and Embedding

Xiou Ge
University of Southern California
Los Angeles, USA
<EMAIL_ADDRESS>
&Yun-Cheng Wang
University of Southern California
Los Angeles, USA
<EMAIL_ADDRESS>
&Bin Wang
National University of Singapore
Singapore
<EMAIL_ADDRESS>
&C.-C. Jay Kuo
University of Southern California
Los Angeles, USA
<EMAIL_ADDRESS>

###### Abstract

Entity type prediction is an important problem in knowledge graph (KG)
research. A new KG entity type prediction method, named CORE (COmplex space
Regression and Embedding), is proposed in this work. The proposed CORE method
leverages the expressive power of two complex space embedding models; namely,
RotatE and ComplEx models. It embeds entities and types in two different
complex spaces using either RotatE or ComplEx. Then, we derive a complex
regression model to link these two spaces. Finally, a mechanism to optimize
embedding and regression parameters jointly is introduced. Experiments show
that CORE outperforms benchmarking methods on representative KG entity type
inference datasets. Strengths and weaknesses of various entity type prediction
methods are analyzed.

##  1 Introduction

Research on knowledge graph (KG) construction, completion, inference, and
applications has grown rapidly in recent years since it offers a powerful tool
for modeling human knowledge in graph forms. Nodes in KGs denote entities and
links represent relations between entities. The basic building blocks of KG
are entity-relation triples in form of (_subject, predicate, object_)
introduced by the Resource Description Framework (RDF). Learning
representations for entities and relations in low dimensional vector spaces is
one of the most active research topics in the field.

Entity type offers a valuable piece of information to KG learning tasks.
Better results in KG-related tasks have been achieved with the help of entity
type. For example, TKRL [1] uses a hierarchical type encoder for KG completion
by incorporating entity type information. AutoETER [2] adopts a similar
approach but encodes the type information with projection matrices. Based on
DistMult [3] and ComplEx [4] embedding, [5] propose an improved factorization
model without explicit type supervision. JOIE [6] attempts to embed entities
and types in two separate spaces by learning instance-view embedding and
ontology-view embedding. Similar to JOIE, TaRP [7] leverages the hierarchical
type ontology structure for relation prediction. Instead of learning embedding
for all types, TaRP develops a heuristic weighting mechanism to rank the prior
probability of a relation given its head and tail type information. A similar
idea was examined in TransT [8]. Besides, entity type is also important for
Information Extraction tasks including entity linking [9] and relation
extraction [10, 11].

Figure 1: A KG with the entity type information.

Figure 2: Illustration of the statistical approach.

On the other hand, entity type prediction is challenging for several reasons.
First, collecting additional type labels for entities is expensive. Second,
type information is often incomplete especially for large-scale datasets. Fig.
2 shows a snapshot of a KG, where missing entity types need to be inferred.
Third, KGs are ever-evolving and type information is often corrupted by noisy
facts. Thus, there is a need to design algorithms to predict missing type
labels. Quite a few approaches have been proposed to predict missing entity
types in KG. They can be classified into three different categories: namely
statistical-based, classifier-based, and embedding-based methods. A brief
review is given in Sec. 2.

The contributions of our work are summarized as follows:

  * •

We present a new method for entity type prediction named CORE (COmplex space
Regression and Embedding). CORE leverages the expressive power of complex
space embedding models including RotatE [12] and ComplEx [4] to represent
entities and types. To capture the relatedness of entities and types, a
complex regression model is built between entity space and type space.

  * •

We conduct experiments on three major KG datasets and make performance
comparison between CORE and state-of-the-art entity type prediction methods.
CORE outperforms extant methods in most evaluation metrics.

  * •

We study and compare statistical-based, classifier-based, and embedding-based
methods for entity type prediction. Strengths and weaknesses of different
approaches are discussed. We also introduce a better statistical method
baseline named SDType-Cond.

##  2 Related Work

Work on entity type prediction can be categorized into three types as
elaborated below.

###  2.1 Statistical Approach.

Before machine learning is introduced to KG entity type prediction, the type
inference is often performed using RDF rules and graph pattern matching [13].
Although these handcrafted rules can make type prediction with high precision,
they tend to miss a lot of possible cases since it is almost impossible to
manually create all patterns. Hence, this approach is not scalable for large
scale datasets. As such, researchers apply basic statistics to solve the KG
entity type prediction problem. An early method, called SDType [14], predicts
missing entity types by estimating the empirical probability distribution of
$P(type|relation)$ and aggregating all such conditional probabilities
generated by neighboring relations of the target entity. Although this
approach is robust to noise, it cannot predict unseen types and relation
combinations. Another shortcoming of the statistical approach is that its
performance deteriorates as the number of entity types becomes larger (say,
with thousands of entity types). Furthermore, it does not exploit the type
information of neighboring entities. In this paper, we will show that the type
prediction performance can be further improved by conditioning on the type
information of neighboring entities. Fig. 2 illustrates the statistical
approach for entity type prediction. Suppose we want to predict the type of
the target node, then given the information of each neighbor relation and
neighbor node’s type, we can estimate the type distribution of for the target
node.

###  2.2 Classification Approach.

Node classification is a common task in graph learning. One solution is to
train a classifier with node features as the input and corresponding labels as
the output. This idea can be applied to entity type prediction as well.
Researchers [15, 16, 17] conducted experiments with entity textual
descriptions in form of word embeddings as features and neural networks such
as MLP, LSTM, and CNN as classifiers. An end-to-end architecture that learns
entity embedding and type prediction jointly was proposed in [18]. The
correlation between entity attributes and KG link structures were taken into
account in the learning of distributed entity representations. In this work,
with pretrained KG embeddings as features, we test a couple of classifiers
such as SVM and XGBoost [19]. Again, we find this approach does not perform
well for large datasets. In fact, a comparative study on statistical and
classifier approaches was conducted in [20]. By analyzing results from
selected entity type classes, they concluded that KG embeddings fail to
capture the semantics of entities and statistical approaches are often
superior in type prediction. While we concur with their experimental findings
that the combination of entity embedding features and classifiers tend to
yield poor results, we do not agree that KG embedding models cannot be useful
for entity type prediction as elaborated below.

###  2.3 Embedding Approach.

Before introducing the embedding approach for entity type prediction, it is
worthwhile to review KG Embedding models briefly. According to [21], a KG
embedding model can be categorized based on its representation space and
scoring function. Among several representation spaces, real and complex vector
spaces are the two most common ones. TransE models triples in form of
_subject, relation, object_ or $(s,r,o)$ in $d$-dimensional real vector space
with the translational principle
$\mathbf{e_{s}}+\mathbf{w_{r}}\approx\mathbf{e_{o}}$. Yet, TransE is not
suitable for modeling asymmetric and many-to-one relations. To overcome this
weakness, researchers venture into the complex vector space for and design
models with greater expressive power. ComplEx and RotatE are two prominent
examples. ComplEx is motivated by low rank matrix factorization in the complex
space to model both symmetric and asymmetric relations effectively. Inspired
by Euler’s identity, RotatE models relations as rotations in the complex
vector space to remedy ComplEx’s inability to model composition patterns in
KG. Both TransE and RotatE adopt distance-based scoring function while ComplEx
has a semantic matching score.

Besides KG embedding, embedding-based entity type prediction approaches learn
a distributed representation of entity types. For example, a distance-based
scoring function can be used to measure the relevance of a particular type to
the target entity. The ETE model [22] embeds entity and entity types in the
same space. ConnectE [23] embeds entities and types in two different spaces
and learns a mapping from the entity space to the type space. It leverages
neighbor label information to boost the performance further. Based on a
similar idea, JOIE [23] adds an intra-view component to model the hierarchical
structure of the type ontology. ETE, ConnectE, and JOIE all adopt TransE
embedding to represent KG entities. JOIE targets at better results for link
prediction whereas ETE and ConnectE focus on improving entity type prediction.
TransE is known to suffer from a few problems, e.g., not able to model
asymmetric relations. Poor relation representation leads to poor entity
representation. Since the quality of entity representation affects entity type
prediction performance, we exploit the expressive power of complex-space KG
embedding to achieve better results.

##  3 Proposed CORE Methods

To leverage the expressive power of the complex-space KG embedding, we propose
to learn a set of embeddings for both the entity space and the type space as
shown in Fig. 4. Specifically, we experiment with ComplEx and RotatE embedding
models. On top of entity embedding and type embedding, we learn a regression
between these two spaces. Finally, we make type predictions using a distance-
based scoring scoring function based on the embeddings and regression
parameters. The high-level concept of the proposed CORE model is given in Fig.
4.

###  3.1 Complex Space KG Embedding.

Let $(s,r,o)$ be a KG triple and
$\mathbf{e_{s}},\mathbf{w_{r}},\mathbf{e_{o}}\in\mathbb{C}^{k}$ denote the
complex space representation of triple’s subject, relation, and object. For
ComplEx, the score function is

$\displaystyle
f_{r}(s,o)=-\operatorname{Re}(\langle\mathbf{w_{r}},\mathbf{e_{s}},\mathbf{\overline{e}_{o}}\rangle),$

where $\langle\cdot,\cdot,\cdot\rangle$ denotes an element-wise multi-linear
dot product, and $\overline{\ \cdot\ }$ denotes the conjugate for complex
vectors. For RotatE embedding, the score function is

$\displaystyle
f_{r}(s,o)=\|\mathbf{e_{s}}\circ\mathbf{w_{r}}-\mathbf{e_{o}}\|_{1},$

where $\circ$ denotes the element-wise product.

We follow RotatE’s negative sampling loss and self-adversarial training
strategy to train the embedding. The loss function for KG embedding models can
be written as

$\displaystyle
L_{\textnormal{KGE}}=-\log\sigma(\gamma_{1}-f_{r}(s,o))-\sum_{i=1}^{n}p(s^{\prime}_{i},r,o^{\prime}_{i})\log\sigma(f_{r}(s^{\prime}_{i},o^{\prime}_{i})-\gamma_{1}),$

where $\sigma$ is the sigmoid function, $\gamma_{1}$ is a fixed margin
hyperparameter for training KG embedding, $(s^{\prime}_{i},r,o^{\prime}_{i})$
is the $i$th negative triple and $p(s^{\prime}_{i},r,o^{\prime}_{i})$ is the
probability of drawing negative triple $(s^{\prime}_{i},r,o^{\prime}_{i})$.
Given a positive triple, $(s_{i},r,o_{i})$, the negative sampling distribution
is

$\displaystyle
p(s^{\prime}_{j},r,o^{\prime}_{j}|\\{(s_{i},r,o_{i})\\})=\frac{\exp\alpha_{1}f_{r}(s^{\prime}_{j},o^{\prime}_{j})}{\sum_{i}\exp\alpha_{1}f_{r}(s^{\prime}_{i},o^{\prime}_{i})},$

where $\alpha_{1}$ is the temperature of sampling.

###  3.2 Complex Space Type Embedding.

Similar to definitions in KG Embedding space, we use $(s_{t},r,o_{t})$ to
denote a type triple and
$\mathbf{t_{s}},\mathbf{v_{r}},\mathbf{t_{o}}\in\mathbb{C}^{l}$ to denote
representations of the subject type, the relation, and the object type in the
type embedding space. For ComplEx embedding, the score function is

$\displaystyle
f_{r}(s_{t},o_{t})=-\operatorname{Re}(\langle\mathbf{v_{r}},\mathbf{t_{s}},\mathbf{\overline{t}_{o}}\rangle).$

For RotatE embedding, the score function is

$\displaystyle
f_{r}(s_{t},o_{t})=\|\mathbf{t_{s}}\circ\mathbf{v_{r}}-\mathbf{t_{o}}\|_{1}.$

To train type embedding, we use the self-adversarial negative sampling loss in
form of

$\displaystyle
L_{\textnormal{TPE}}=-\log\sigma(\gamma_{2}-f_{r}(s_{t},o_{t}))-\sum_{i=1}^{n}p(s_{t_{i}}^{\prime},r,o_{t_{i}}^{\prime})\log\sigma(f_{r}(s_{t_{i}}^{\prime},o_{t_{i}}^{\prime})-\gamma_{2}),$

where $\gamma_{2}$ is a fixed margin hyperparameter for training type
embedding and $(s_{t_{i}}^{\prime},r,o_{t_{i}}^{\prime})$ is the $i$th
negative triple, and $p(s_{t_{i}}^{\prime},r,o_{t_{i}}^{\prime})$ is the
probability of drawing the negative triple
$(s_{t_{i}}^{\prime},r,o_{t_{i}}^{\prime})$. Given a positive triple,
$(s_{t_{i}},r,o_{t_{i}})$, the negative sampling distribution is

$\displaystyle
p(s_{t_{j}}^{\prime},r,o_{t_{j}}^{\prime}|\\{(s_{t_{i}},r,o_{t_{i}})\\})=\frac{\exp\alpha_{2}f_{r}(s_{t_{j}}^{\prime},o_{t_{j}}^{\prime})}{\sum_{i}\exp\alpha_{2}f_{r}(s_{t_{i}}^{\prime},o_{t_{i}}^{\prime})},$

where $\alpha_{2}$ is the temperature of sampling.

Figure 3: Illustration of RotatE entity space and RotatE type space and the
regression linking two spaces.

Figure 4: Illustration of the CORE Model, where the blue and red dots denote
entities and types in their complex embedding spaces, respectively.

###  3.3 Solving Complex Space Regression.

To propagate information from the entity space to the type space, we learn a
regression between two complex spaces. A feasible and logical way of solving
the complex regression is to cast the problem into a multivariate regression
problem in real vector space. Formally, let $\mathbf{e}\in\mathbb{C}^{k}$,
$\mathbf{t}\in\mathbb{C}^{l}$ denote the representation of the entity and its
type. We divide the real and the imaginary parts of every complex entity
vector into two real vectors; namely,
$\operatorname{Re(\mathbf{e})}\in\mathbb{R}^{k}$ and
$\operatorname{Im(\mathbf{e})}\in\mathbb{R}^{k}$. We do the same to divide the
complex type vector into two real vectors:
$\operatorname{Re(\mathbf{t})}\in\mathbb{R}^{l}$ and
$\operatorname{Im(\mathbf{t})}\in\mathbb{R}^{l}$.

As shown in Fig. 4, the regression process consists of four different real
block matrices:
$\\{\mathbf{A}_{\operatorname{Re}\rightarrow\operatorname{Re}}$,
$\mathbf{A}_{\operatorname{Im}\rightarrow\operatorname{Re}}$,
$\mathbf{A}_{\operatorname{Re}\rightarrow\operatorname{Im}}$ and
$\mathbf{A}_{\operatorname{Im}\rightarrow\operatorname{Im}}\\}\in\mathbb{R}^{k\times
l}$. The real part of the output vector depends on both the real and imaginary
part of the input vector. Similarly, the imaginary part of the output vector
also depends on both the real and imaginary part of the input vector. The
regression problem can be rewritten as

$\displaystyle\begin{pmatrix}\operatorname{Re(\mathbf{t})}\\\ \
\operatorname{Im(\mathbf{t})}\end{pmatrix}=\begin{pmatrix}\mathbf{A}_{\operatorname{Re}\rightarrow\operatorname{Re}}&\mathbf{A}_{\operatorname{Im}\rightarrow\operatorname{Re}}\\\
\
\mathbf{A}_{\operatorname{Re}\rightarrow\operatorname{Im}}&\mathbf{A}_{\operatorname{Im}\rightarrow\operatorname{Im}}\end{pmatrix}\begin{pmatrix}\operatorname{Re(\mathbf{e})}\\\
\ \operatorname{Im(\mathbf{e})}\end{pmatrix}+\mathbf{\epsilon},$

where $\mathbf{\epsilon}$ denotes the error vector. To minimize
$\mathbf{\epsilon}$, we use the following score function

$\displaystyle f(e,t)$
$\displaystyle=\|\mathbf{A}_{\operatorname{Re}\rightarrow\operatorname{Re}}\cdot\operatorname{Re(\mathbf{e})}+\mathbf{A}_{\operatorname{Im}\rightarrow\operatorname{Re}}\cdot\operatorname{Im(\mathbf{e})}-\operatorname{Re(\mathbf{t})}\|_{2}$
$\displaystyle+\|\mathbf{A}_{\operatorname{Re}\rightarrow\operatorname{Im}}\cdot\operatorname{Re(\mathbf{e})}+\mathbf{A}_{\operatorname{Im}\rightarrow\operatorname{Im}}\cdot\operatorname{Im(\mathbf{e})}-\operatorname{Im(\mathbf{t})}\|_{2}.$

We find that the self-adversarial negative sampling strategies are useful in
optimizing regression coefficients. The loss function in learning these
coefficients is set to

$\displaystyle
L_{\textnormal{RR}}=-\log\sigma(\gamma_{3}-f(e,t))-\sum_{i=1}^{n}p(e,t^{\prime}_{i})\log\sigma(f(e,t^{\prime}_{i})-\gamma_{3}),$

where $\gamma_{3}$ is a fixed margin hyperparameter in the regression,
$(e,t^{\prime}_{i})$ is the $i$th negative pair, and $p(e,t^{\prime}_{i})$ is
the probability of drawing negative pair $(e,t^{\prime}_{i})$. Given positive
triple $(e,t_{i})$, the negative sampling distribution is equal to

$\displaystyle
p(e,t^{\prime}_{j}|\\{(e,t_{i})\\})=\frac{\exp\alpha_{3}f(e,t^{\prime}_{j})}{\sum_{i}\exp\alpha_{3}f(e,t^{\prime}_{i})},$

where $\alpha_{3}$ is the temperature of sampling.

###  3.4 Type Prediction.

We use the distance-based scoring function $f(e,t)$ in the regression to
predict entity types. The type prediction function can be written as

$\displaystyle\hat{t}=\operatorname*{arg\,min}_{t\in\mathcal{T}}f(e,t),$

where $\mathcal{T}$ denotes the set of all types.

###  3.5 Optimization.

We first initialize the embedding and regression parameters by sampling from
the standard uniform distribution. Three parts of our model are optimized
sequentially. First, we optimize the KG embeddings using KG triples and
negative triples. Next, we move on to train regression and type space
embeddings parameters. we freeze the KG embedding to ensure the regression is
learning important information in this stage. Last, we further optimize the
type space embeddings using type triples. To avoid overfitting of the
regression model in the early training stage, we alternate the optimization
for each part of the model every 1000 iterations.

###  3.6 Complexity.

The memory and space complexity for CORE are both $O(n_{e}\times
d_{e}+n_{r}\times d_{r}+n_{t}\times d_{t}+d_{e}\times d_{t})$, where $n$
denotes the number of objects, $d$ denotes the dimension, and the subscripts
$e$ denotes entity, $r$ denotes relation, $t$ denotes type, respectively.

Dataset | #Ent | #Rel | #Type | #KG Triples | #Entity Type Pairs
---|---|---|---|---|---
#Train | #Valid | #Test | #Train | #Valid | #Test
FB15k-ET | 14,951 | 1,345 | 3,851 | 483,142 | 50,000 | 59,071 | 136,618 | 15,749 | 15,780
YAGO43k-ET | 42,335 | 37 | 45,182 | 331,687 | 29,599 | 29,593 | 375,853 | 42,739 | 42,750
DB111K-174 | 111,762 | 305 | 242 | 527,654 | 65,000 | 65,851 | 57,969 | 1,000 | 39,371
Table 1: Statistics of three KG datasets used in our experiments.

##  4 Experiments

###  4.1 Datasets

We evaluate the proposed CORE model by conducting experiments on several well-
known KG datasets with the entity type information. They include FB15k-ET,
YAGO43k-ET [22], and DB111k-174 [6], which are subsets of Freebase [24], YAGO
[25], and DBpedia [26] KGs, respectively. [23] further clean FB15k-ET and
YAGO43k-ET datasets by removing triples in the training sets from the
validation and test sets. They also create a script to generate type triples
$(s_{t},r,o_{t})$ by enumerating all possible combination of relations and the
types of their subject and object. We use the same script to generate type
triples for training type embedding. The statistics of these datasets are
shown in Table 1.

###  4.2 Hyperparameter Setting

We list out the hyperparameter settings for each of the benchmarking datasets
we run experiments on in Table 2. In this table, $k$ and $l$ denote the
dimension of entity embedding and type embedding, respectively. $Ebz$, $Tbz$,
and $Nsz$ denote the entity batch size, type batch size, and negative sample
size, respectively. $\alpha_{1}$, $\gamma_{1}$, and $\eta_{1}$ denote the
sampling temperature, margin parameter, and learning rate respectively. In
addition, we also show the MRR and Hits@k results for RotatE and ComplEx with
different type dimensions for FB15k-ET in Fig. 6 and Fig. 6, respectively.

Dataset | Model | $k$ | $l$ | $Ebz$ | $Tbz$ | $Nsz$ | $\alpha_{1}$ | $\gamma_{1}$ | $\eta_{1}$
---|---|---|---|---|---|---|---|---|---
FB15k-ET | CORE-RotatE | 1000 | 700 | 1024 | 4096 | 256 | 1 | 24 | 0.0001
CORE-ComplEx | 500 | 550 | 1024 | 4096 | 400 | 1 | 24 | 0.0002
YAGO43k-ET | CORE-RotatE | 500 | 350 | 1024 | 4096 | 400 | 1 | 24 | 0.0002
CORE-ComplEx | 500 | 350 | 1024 | 4096 | 400 | 1 | 24 | 0.0002
DB111K-174 | CORE-RotatE | 1000 | 250 | 1024 | 4096 | 256 | 1 | 24 | 0.0005
CORE-ComplEx | 1000 | 250 | 1024 | 4096 | 400 | 1 | 24 | 0.0002
Table 2: Hyperparameter setting.

Figure 5: Comparison of the MRR performance for FB15k-ET as a function of the
type dimension with RotatE embedding.

Figure 6: Comparison of the MRR performance for FB15k-ET as a function of the
type dimension with ComplEx embedding.

Datasets |  | FB15k-ET |  |  | YAGO43k-ET |
---|---|---|---|---|---|---
Metrics | MRR | H@1 | H@3 | H@10 | MRR | H@1 | H@3 | H@10
RESCAL [27] | 0.19 | 9.71 | 19.58 | 37.58 | 0.08 | 4.24 | 8.31 | 15.31
RES.-ET [22] | 0.24 | 12.17 | 27.92 | 50.72 | 0.09 | 4.32 | 9.62 | 19.40
HOLE [28] | 0.22 | 13.29 | 23.35 | 38.16 | 0.16 | 9.02 | 17.28 | 29.25
HOLE-ET [22] | 0.42 | 29.40 | 48.04 | 66.73 | 0.18 | 10.28 | 20.13 | 34.90
TransE [29] | 0.45 | 31.51 | 51.45 | 73.93 | 0.21 | 12.63 | 23.24 | 38.93
TransE-ET [22] | 0.46 | 33.56 | 52.96 | 71.16 | 0.18 | 9.19 | 19.41 | 35.58
ETE [22] | 0.50 | 38.51 | 55.33 | 71.93 | 0.23 | 13.73 | 26.28 | 42.18
ConnectE-E2T [23] | 0.57 | 45.53 | 62.31 | 78.12 | 0.24 | 13.54 | 26.20 | 44.51
ConnectE-E2T-TRT [23] | 0.59 | 49.55 | 64.32 | 79.92 | 0.28 | 16.01 | 30.85 | 47.92
ConnectE-E2T-TRT (Actual) | 0.58 | 47.45 | 64.33 | 77.55 | 0.14 | 8.04 | 17.59 | 24.62
SDType-Cond | 0.42 | 27.56 | 50.09 | 71.23 | - | - | - | -
CORE-RotatE | 0.60 | 49.32 | 65.25 | 81.09 | 0.32 | 22.96 | 36.55 | 51.00
CORE-ComplEx | 0.60 | 48.91 | 66.30 | 81.60 | 0.35 | 24.17 | 39.18 | 54.95
Table 3: Performance comparison of various entity type prediction methods in terms of filtered ranking for FB15k-ET and YAGO43k-ET, where the best and the second best performance numbers are shown in bold face and with an underscore, respectively. Datasets |  | DB111K-174 |
---|---|---|---
Metrics | MRR | H@1 | H@3
JOIE-HATransE-CT | 0.857 | 75.55 | 95.91
SDType | 0.861 | 78.53 | 92.67
ConnectE-E2T | 0.88 | 81.63 | 94.19
ConnectE-E2T-TRT | 0.90 | 82.96 | 96.07
SDType-Cond | 0.879 | 80.99 | 94.05
CORE-RotatE | 0.889 | 82.02 | 95.36
CORE-ComplEx | 0.900 | 84.25 | 95.42
TransE+XGBoost | 0.878 | 81.38 | 94.07
TransE+SVM | 0.917 | 86.77 | 96.33
Table 4: Performance comparison of entity type prediction for DB111K-174, where the best and the second best performance numbers are shown in bold face and with an underscore, respectively. Entity | Model | Top 3 Type Predictions
---|---|---
Albert Einstein | ConnectE | Islands of Sicily, Swiss singers, Heads of state of Canada
CORE |  Nobel laureates in Physics, Fellows of the Royal Society,
20th-century mathematicians
Warsaw | ConnectE | Defunct political parties in Poland, Political parties in Poland,
Universities in Poland
CORE |  Administrative district, Port cities, Cities in Europe
George Michael | ConnectE | United Soccer League players, People from Stourbridge,
Fortuna Düsseldorf managers
CORE |  British singers, English musicians, Rock singers
Table 5: An illustrative example of type prediction for the YAGO43k-ET
dataset.

###  4.3 Benchmarking Methods

To the best of our knowledge, we are the first work to compare embedding-based
methods with statistical-based and classifier-based methods since we would
like to understand the strengths and weaknesses of different models.

####  4.3.1 Statistical-based Method.

We compare the performance of the proposed CORE model with that of a
statistical-based method named SDType-Cond in FB15k-ET dataset. SDType-Cond is
a variant of SDType. The neighbor type is readily available in many entities,
yet SDType ignores this important piece of information. SDType-Cond is capable
of estimating the type distribution more precisely by leveraging the known
neighbor type information. Instead of estimating the type distribution given a
paricular relation $p(s_{t}|r=\tilde{r})$ or $p(o_{t}|r=\tilde{r})$, we
estimate $p(s_{t}|r=\tilde{r},o_{t}=\tilde{t})$ or
$p(o_{t}|r=\tilde{r},s_{t}=\tilde{t})$, $\tilde{r}\in\mathcal{R}$,
$\tilde{t}\in\mathcal{T}$, where $\mathcal{R}$ and $\mathcal{T}$ denote the
set of all relations and the set of all entity types, respectively. The two
probabilities represent the two cases where the target entity serves as a
subject and an object, respectively. By aggregating the probabilities
generated by all possible $(\tilde{r},\tilde{t})$ combinations in the
neighborhood of the target entity, we can rank the type candidates using the
following function:

$\displaystyle\hat{t}=\operatorname*{arg\,max}_{\hat{t}\in\mathcal{T}}\frac{1}{|\mathcal{N}|}\left\\{\sum_{(\tilde{r},\tilde{t})\in\mathcal{N}}p(s_{t}=\hat{t}|r=\tilde{r},o_{t}=\tilde{t})+\sum_{(\tilde{r},\tilde{t})\in\mathcal{N}}p(o_{t}=\hat{t}|r=\tilde{r},s_{t}=\tilde{t})\right\\},$

where $\mathcal{N}$ denotes the set of all $(\tilde{r},\tilde{t})$
combinations in the target entity’s neighborhood.

####  4.3.2 Classifier-based Method.

We also explore the node classification approach to solve the type prediction
problem as a benchmarking method. Specifically, we experiment with the
combination of pretrained TransE embedding as entity features and use SVM and
XGBoost as classifiers. To get the pretrained TransE embedding for FB15k, we
set the batch size to 1000, negative sample size to 256, hidden dimension to
1000, $\alpha_{1}=1$, the margin parameter $\gamma_{1}=24$, and the learning
rate $\eta_{1}=0.0001$, and train for 150000 epochs. For the SVM classifier,
we set the regularization parameter $C=1$ and adopt the Radial Basis Function
(RBF) kernel. The kernel coefficient for RBF is
$\gamma_{svm}=(\\#\text{features}\times\text{feature variance})^{-1}$. For the
XGBoost classifier, we set the learning rate to $0.1$, the number of
estimators to $500$, the maximum depth of each estimator to $5$, the minimum
child weight to 1, and use the softmax objective function for training.

###  4.4 Experimental Results

To evaluate the performance of the CORE method and several benchmarking
methods, we use the Mean Reciprocal Rank (MRR) and Hits@k as the performance
metrics. Since models are trained to favor observed types as top choices, we
filter the observed types from all possible type candidates when computing the
ranking based on a scoring function.

First, we show the MRR and Hits@k results for RotatE and ComplEx with
different type dimensions for FB15k-ET in Fig. 6 and Fig. 6, respectively. The
optimal type dimensions for the RotatE and the ComplEx embeddings are 700 and
550. We adopt this setting in the following experiments.

Table 3 shows the results for FB15k-ET and YAGO34k-ET. We see from the table
that our proposed CORE models offer the state-of-the-art performance in both
datasets. CORE-ComplEx achieves the best performance in all categories except
Hits@1 for FB15K-ET. It outperforms the previous best method,
ConnectE-E2T-TRT, by a significant margin for YAGO34K-ET dataset.

We also experiment with classifier-based methods and observe that classifier-
based methods do not scale well for large datasets such as FB15k-ET and
YAGO43k-ET. The training time for classifier grows significantly with the size
of the label set and the feature dimension. In addition, the performance of
the classifier-based method is much lower than the statistical-based and
embedding-based methods.

On the other hand, for datasets with a small number of distinct types,
classifier-based methods do have some advantage. Table 4 compares the
performance of several type prediction methods for DB111K-174. The SVM
classifier with pretrained TransE embedding features outperforms all other
methods. The idea to incorporate hierarchical structural information of types
by JOIE does not seem effective for type prediction since even the simple
statistical-based method such as SDType can outperform the JOIE baseline for
MRR and Hits@1 metrics. By conditioning on neighbor type label information,
SDType-Cond can further boost the performance. The performance gap among
different benchmarking methods is smaller on DB111K-174.

To gain insights into entity type prediction, we provide an illustrative
example of type prediction in the YAGO43k-ET dataset. In Table 5, we compare
the top three type predictions by ConnectE and CORE for some well-known people
and place. Although there are some lapses in CORE’s predictions, the model can
make right decisions for most queries and majority of the top three candidates
are in fact valid type labels for the corresponding target entity. These
results demonstrate the impressive prediction power of our proposed CORE
model, given the enormous amount of unique type labels.

##  5 Conclusion and Future Work

A complex regression and embedding method, called CORE, has been proposed to
solve entity type prediction problem in this work by exploiting the expressive
power of RotatE and ComplEx models. It embeds entities and types in two
different complex spaces and used a complex regression model to measure the
relatedness of entities and types. Finally, it optimizes embedding and
regression parameters jointly to reach the optimal performance under this
framework. Experimental results demonstrate that CORE offers great performance
on representative KG entity type inference datasets and outperforms the state-
of-the-art model by a significant margin for YAGO34K-ET dataset.

There are several research directions worth exploration in the future. First,
the use of textual descriptions and transformer models to extract features for
entity type prediction can be investigated. Second, we can examine the
multilabel classification framework for entity type prediction since it shares
a similar problem formulation. Although both try to predict multiple target
labels, there are however differences. For multilabel classification, objects
in the train set and the test set are disjoint. That is, we train the
classifier using the train set and test it on a different set. For entity type
prediction, the two sets are not disjoint. In training, a model is trained
with a set of entity feature vectors and their corresponding labels. In
inference, it is often to infer missing type labels for the same set of
entities. Third, a binary classifier can also be used for entity type
prediction. Yet, there exist far more negative samples than positive ones, and
it requires good selection of negative examples to handle the data imbalance
problem.

## References

  * [1] Ruobing Xie, Zhiyuan Liu, Maosong Sun, et al.  Representation learning of knowledge graphs with hierarchical types.  In IJCAI, 2016.
  * [2] Guanglin Niu, Bo Li, Yongfei Zhang, Shiliang Pu, and Jingyang Li.  Autoeter: Automated entity type representation for knowledge graph embedding.  In EMNLP Findings, 2020.
  * [3] Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng.  Embedding entities and relations for learning and inference in knowledge bases.  In ICLR, 2014.
  * [4] Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard.  Complex embeddings for simple link prediction.  In ICML, 2016.
  * [5] Prachi Jain, Pankaj Kumar, Soumen Chakrabarti, et al.  Type-sensitive knowledge base inference without explicit type supervision.  In ACL, 2018.
  * [6] Junheng Hao, Muhao Chen, Wenchao Yu, Yizhou Sun, and Wei Wang.  Universal representation learning of knowledge bases by jointly embedding instances and ontological concepts.  In KDD, 2019.
  * [7] Zijun Cui, Pavan Kapanipathi, Kartik Talamadupula, Tian Gao, and Qiang Ji.  Type-augmented relation prediction in knowledge graphs.  In AAAI, 2021.
  * [8] Shiheng Ma, Jianhui Ding, Weijia Jia, Kun Wang, and Minyi Guo.  Transt: Type-based multiple embedding representations for knowledge graph completion.  In ECML PKDD, 2017.
  * [9] Nitish Gupta, Sameer Singh, and Dan Roth.  Entity linking via joint encoding of types, descriptions, and context.  In EMNLP, 2017.
  * [10] GuoDong Zhou, Jian Su, Jie Zhang, and Min Zhang.  Exploring various knowledge in relation extraction.  In ACL, 2005.
  * [11] Aron Culotta and Jeffrey Sorensen.  Dependency tree kernels for relation extraction.  In ACL, 2004.
  * [12] Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang.  Rotate: Knowledge graph embedding by relational rotation in complex space.  In ICLR, 2019.
  * [13] Aldo Gangemi, Andrea Giovanni Nuzzolese, Valentina Presutti, Francesco Draicchio, Alberto Musetti, and Paolo Ciancarini.  Automatic typing of dbpedia entities.  In ISWC, 2012.
  * [14] Heiko Paulheim and Christian Bizer.  Type inference on noisy rdf data.  In ISWC, 2013.
  * [15] Yadollah Yaghoobzadeh and Hinrich Schütze.  Corpus-level fine-grained entity typing using contextual information.  In EMNLP, 2015.
  * [16] Ji Xin, Yankai Lin, Zhiyuan Liu, and Maosong Sun.  Improving neural fine-grained entity typing with knowledge attention.  In AAAI, 2018.
  * [17] Radina Sofronova, Russa Biswas, Mehwish Alam, and Harald Sack.  Entity typing based on rdf2vec using supervised and unsupervised methods.  In ESWC, 2020.
  * [18] Hailong Jin, Lei Hou, Juanzi Li, and Tiansi Dong.  Attributed and predictive entity embedding for fine-grained entity typing in knowledge bases.  In COLING, 2018.
  * [19] Tianqi Chen and Carlos Guestrin.  Xgboost: A scalable tree boosting system.  In KDD, 2016.
  * [20] Nitisha Jain, Jan-Christoph Kalo, Wolf-Tilo Balke, and Ralf Krestel.  Do embeddings actually capture knowledge graph semantics?  In ESWC, 2021.
  * [21] Shaoxiong Ji, Shirui Pan, Erik Cambria, Pekka Marttinen, and S Yu Philip.  A survey on knowledge graphs: Representation, acquisition, and applications.  IEEE Trans. Neural Netw. Learn. Syst., 2021.
  * [22] Changsung Moon, others, Paul Jones, and Nagiza F Samatova.  Learning entity type embeddings for knowledge graph completion.  In CIKM, 2017.
  * [23] Yu Zhao, Anxiang Zhang, Ruobing Xie, Kang Liu, and Xiaojie Wang.  Connecting embeddings for knowledge graph entity typing.  In ACL, 2020.
  * [24] Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor.  Freebase: A collaboratively created graph database for structuring human knowledge.  In ACM SIGMOD/PODS, 2008.
  * [25] Fabian M Suchanek, Gjergji Kasneci, and Gerhard Weikum.  Yago: A core of semantic knowledge.  In WWW, 2007.
  * [26] Sören Auer, Christian Bizer, Georgi Kobilarov, Jens Lehmann, Richard Cyganiak, and Zachary Ives.  DBpedia: A nucleus for a web of open data.  In The Semantic Web. Springer, 2007.
  * [27] Nickel, Maximilian others, Volker Tresp, and Hans-Peter Kriegel.  A three-way model for collective learning on multi-relational data.  In ICML, 2011.
  * [28] Nickel, Maximilian others, Lorenzo Rosasco, and Tomaso Poggio.  Holographic embeddings of knowledge graphs.  In AAAI, 2016.
  * [29] Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko.  Translating embeddings for modeling multi-relational data.  In NeurIPS, 2013.