# SelfDeco: Self-Supervised Monocular Depth Completion in Challenging Indoor
Environments

Jaehoon Choi1,2, Dongki Jung1, Yonghan Lee1, Deokhwa Kim1, Dinesh Manocha2,
and Donghwan Lee1
1NAVER LABS 2University of Maryland

###### Abstract

We present a novel algorithm for self-supervised monocular depth completion.
Our approach is based on training a neural network that requires only sparse
depth measurements and corresponding monocular video sequences without dense
depth labels. Our self-supervised algorithm is designed for challenging indoor
environments with textureless regions, glossy and transparent surfaces, moving
people, longer and diverse depth ranges and scenes captured by complex ego-
motions. Our novel architecture leverages both deep stacks of sparse
convolution blocks to extract sparse depth features and pixel-adaptive
convolutions to fuse image and depth features. We compare with existing
approaches in NYUv2, KITTI and NAVERLABS indoor datasets, and observe 5 - 34 %
improvements in root-means-square error (RMSE) reduction.

##  I Introduction

Depth completion has been widely studied in the field of robot navigation,
computer vision, and autonomous driving. Its goal is to convert a sparse depth
map from active depth sensors such as LiDAR or RGB-D cameras to a dense depth
map. In practice, robots with accurate sensing and dense depth maps have a
lower chance of collision [29] and are better able to compute safe navigation
routes through challenging environments [30, 31]. Currently, most recent
methods for depth completion rely on supervised learning [22, 25, 24],
requiring large amounts of high-quality and dense depth maps as ground truth.
Unfortunately, generating dense depth maps is expensive and challenging due to
the sparse and noisy depth values from other active sensors. Even existing
expensive 3D LiDAR sensors only have a limited number of scan lines and
provide sparse depth measurements.

Self-supervised methods with monocular videos that are able to train depth
completion neural networks without the need for dense depth maps. These
methods [2, 1, 3, 4] are based on an unsupervised learning framework that use
depth and camera ego-motion from monocular videos and use photometric loss as
supervision. This loss measures the difference between a reference image and a
synthesized image obtained by the depth-guided reprojection of other views
into the reference view. However, the previous self-supervised training
process for depth completion [17, 16] may not work well on public indoor
datasets such as NYUv2 [39]. This is due to large areas of textureless regions
and scenes captured by complex ego-motions of a handheld camera [5, 8]. Large
indoor environments are more challenging not only because of the above issues
but also because of large regions of glossy and transparent surface, non-
Lambertian surfaces, longer and diverse ranges, and moving people. To overcome
these issues, our proposed training process requires effective ways to compute
complex camera ego-motions attached to a robot, mask out regions where
photometric loss is unreliable, and output depth maps robust to diverse depth
range. In this paper, we address the problem of developing self-supervised
depth completion methods that work robustly on general indoor environments.

Main Results: We improve the training framework by leveraging learning-based
local features to obtain accurate relative poses, making robust matching with
auto-masking and minimum reprojection loss [4], and predicting inverse depth
using a sigmoid function. However, we observe that merely masking out all
regions still leads to depth artifacts including blurred boundaries and
irregular patterns copied from sparse depth input. Therefore, we also propose
a novel architecture with two unique components: sparsity-aware convolutions
that extract features properly from sparse input and pixel-adaptive
convolutions which propagate this information to the whole depth prediction
with the guidance of image features. We highlight the effectiveness of our
method by evaluating our approach on challenging datasets such as the Metro
Station or the Department Store (Fig. 1). We also demonstrate the
applicability of our method on datasets for which prior self-supervised depth
estimation and completion fail to provide reliable depth maps. Our novel
contributions can be summarized as follows:

Figure 1: Depth completion results in challenging scenes: Metro Station (top)
and the Department Store (bottom) from NAVERLABS indoor dataset. Our method
takes an RGB image and a sparse depth map (projection of LiDAR pointcloud) as
input, and predicts a dense depth map. (low  high; grey means empty depth
values.)

  * •

We develop a robust and stable training framework for self-supervised depth
completion in challenging indoor environments.

  * •

We propose a novel architecture that can extract sparse depth features guided
by high-level image features.

  * •

Our method outperforms prior self- and fully- supervised methods on
challenging indoor datasets like NAVERLABS. We also achieve the state-of-the-
art performance among self-supervised methods on public benchmark datasets,
including KITTI and the NYUv2 dataset based on various evaluation metrics.

##  II Related Work

Recently, depth completion methods using a deep neural network have shown
promising results. Uhrig et al. [9] propose a sparsity-invariance convolution
layer to handle sparse depth or features by using mask normalizations.
Eldesokey et al. [11, 15] propose the normalized convolution to produce both a
confidence map and dense depth output. In [25], they further extend their work
into uncertainty estimation with depth completion methods. Teixeira et al.
[23] use this confidence propagation from [11] to compute dense depth from
LiDAR. Cheng et al. [14, 22] utilize the neural network to learn the affinity
among neighboring pixels in order to perform the propagation process. In
addition to using RGB images, some methods take advantage of information from
other modalities, e.g., surface normals [13, 19, 20] or segmentation [12].
Yang et al. [16] predict the posterior over depth maps with a conditional
prior network. Some works [27, 28] only focus on an indoor depth completion
task. However, all aforementioned works on indoor scenarios are limited to a
small-scale indoor environment and handle non-LiDAR indoor data (e.g., on the
NYU-Depth-v2 [39] and Matterport3D [13] datasets). In this paper, we introduce
challenging indoor scenarios such as the department store or metro station
containing LiDAR sensor data.

The lack of dense depth maps is a significant limitation of supervised depth
completion. As an alternative, several current works study self-supervised
depth completion methods. Ma et al. [17] present self-supervised methods based
on a photometric loss with pose estimation using the PnP method. Yang et al.
[16] present a conditional prior network (CPN) that predicts a probability of
depths at each pixel. Zhang et al. [18] propose an end-to-end framework to
jointly estimate pose and depth without the PnP method. Yoon et al. [26]
combine monocular depth estimation and Gaussian process-based depth regression
for depth completion.

##  III Proposed Method

###  III-A Training Framework

In Fig. 2, our proposed depth completion model takes a target view image
$I_{t}$ and a sparse depth $S_{t}$ as input, and outputs a dense inverse-depth
$\hat{d}_{t}$. We invert $\hat{d}_{t}$ to compute a dense depth map
$\hat{D}_{t}$. In our method, the source view images contains its two adjacent
temporal frames, i.e., $I_{s}\in\\{I_{t-1},I_{t+1}\\}$, although including a
larger temporal context is possible. Also, we estimate the relative pose
$T_{t\rightarrow s}$ between the target image $I_{t}$ and the set of source
images $I_{s}$ by using a Perspective-n-Point (PnP) [46] with Random Sample
Consensus (RANSAC) [47].

Figure 2: Overview of our proposed framework. The black block with a dash-
dotted line shows the depth completion network (details in Fig. 4).

####  III-A1 Relative Pose Estimation

Although most prior works [4, 18] adopt learning-based pose estimation, we
observe that learning-based pose estimation reveals degradation in performance
when applied to challenging environments such as indoor scenes [5, 7, 8].
Additionally, according to recent findings [6], learning-based pose estimation
methods suffer from scale ambiguity problems and make it difficult to provide
absolute-scale depth supervision. Unlike self-supervised depth estimation,
pose estimation via the PnP method is aligned with the depth completion task
because our model needs to predict absolute scale depth.

Our method first detects learning-based features and computes their
corresponding descriptors via learning-based algorithms. We select R2D2 [36],
which shows better performance than traditional hand-crafted features on the
visual localization benchmarks. Given the predicted feature in source and
target images, we can compute high-quality correspondences by using a FLANN-
based search algorithm [48] and then output the relative camera pose by
solving PnP with corresponding sparse depths. Compared to hand-crafted
features used by [17], dense correspondences obtained by R2D2 enable us to
fully utilize sparse depth measurements with corresponding feature points for
PnP pose estimation.

####  III-A2 Photometric Loss

Given the camera intrinsic matrix $K$ and the relative pose $T_{t\rightarrow
s}$, we compute the warped pixel coordinates and synthesize target image
$I^{\prime}_{t}$ from source images $I_{s}$ via a bilinear sampling function.
Following the self-supervised depth estimation [2, 1], we use the combination
of the L1 and SSIM [33] as the photometric loss $L_{ph}$:

$\begin{split}L_{ph}(I_{t},I^{\prime}_{t})&=\alpha\frac{1-\text{SSIM}(I_{t},I^{\prime}_{t})}{2}+(1-\alpha)\parallel
I_{t}-I^{\prime}_{t}\parallel,\\\
I^{\prime}_{t}(x)&=I_{s}\langle\pi(KT_{t\rightarrow
s}\hat{D}_{t}(x)K^{-1}x_{h})\rangle\>.\end{split}$ (1)

where $x_{h}=[x^{T},1]^{T}$ are the homogeneous coordinates from the target
image, $\pi$ gives pixel coordinates, and $\langle\cdot\rangle$ denotes the
bilinear sampling function. We adopt the minimum reprojection loss and auto-
masking from [4]. Our methods often face the occlusion issue, meaning that
some pixels from frame $I_{t}$ do not appear in either $I_{t-1}$ or $I_{t+1}$
frame due to moving people. To mitigate this occlusion issue, our per-pixel
minimum photometric loss is defined as follows,

$\begin{split}L_{photo}=\min_{I_{s}}L_{ph}(I_{t},I^{\prime}_{t}).\end{split}$
(2)

Additionally, auto-masking encourages our method to mask out static pixels for
which the appearance does not change between the current frame and temporally
adjacent frames. This auto-masking results in removing pixels belonging to
low-texture scenes (e.g. ceiling or fluorescent light) that have undesirable
effects on the minimum photometric loss. Furthermore, these masks often remove
non-Lambertian surfaces (e.g. mirrors or digital bilborad screens), which are
common in the department store or the metro station.

####  III-A3 Sparse Depth Loss

Our proposed model can learn to encode absolute scale from sparse depth loss
by aligning the depth prediction $\hat{D}_{t}$ with sparse depth $S_{t}$. We
use the L1-norm to penalize the difference between $\hat{D}_{t}$ and $S_{t}$
over $\Omega$, where sparse depth is available,

$\begin{split}L_{depth}=\sum_{x\in\Omega}|\hat{D}_{t}(x)-S_{t}(x)|\>.\end{split}$
(3)

####  III-A4 Total Loss Function

Following [2, 17, 4], we also incorporate an edge-aware smoothness loss
function $L_{smooth}$ over the predicted depth map to regularize the depth in
texture-less low-image gradient regions.

$L_{smooth}={\mid\partial_{x}d^{*}\mid}e^{-{\mid\partial_{x}I_{t}\mid}}+{\mid\partial_{y}d^{*}\mid}e^{-{\mid\partial_{y}I_{t}\mid}},$
(4)

where $\partial_{x},\partial_{y}$ denotes the gradients along the either the x
or y direction. $d^{*}=\hat{d}_{t}/{\overline{\hat{d}_{t}}}$ is the normalized
inverse depth [3]. Our overall loss function is a weighted sum over the
aforementioned losses,

$L_{tot}=L_{photo}+\lambda_{d}L_{depth}+\lambda_{s}L_{smooth}$ (5)

where $\lambda_{d}$ and $\lambda_{s}$ denote weighting terms selected through
a grid search.

Figure 3: Examples of auto-masks computed after one epoch. Auto masks (black
pixels) usually contain low-texture scenes or non-Lambertain surfaces where
photometric loss is unreliable.

###  III-B Network Architecture

In our training framework, the objective function defines a trade-off between
a sparse depth loss, which enables our network to predict absolute scale depth
on sparse regions, and a photometric loss, which encourages the network to
predict dense depth where sparse information does not exist. In challenging
indoor environments, self-supervised methods with photometric loss have shown
that finding the optimal depth value is very difficult because the loss only
comes from the appearance difference between target and synthesized images;
measuring these differences is difficult due to the large non-texture regions,
repeating structures, and occlusions.

The sparse depth loss might easily overwhelm the whole self-supervised
training, and the depth predictions often result in overfitting on sparse
depth input. Both feature extraction from the sparse depth and feature fusion
schemes of multi-modal data are critical to avoid such negative effects. Our
network adopts a late fusion scheme that uses each encoder for different
sources because image and sparse depth features are heterogeneous. Throughout
several experiments in Sec. IV-A1, a late fusion scheme is shown to be
particularly suitable for self-supervised depth completion. We focus on
designing an effective architecture that leverages sparse depth features to
fill the empty regions rather than getting stuck producing sparse depth
prediction.

Figure 4:  Our model consists of three main components: (1) an RGB encoder
that extracts RGB features, reducing the spatial resolution of the input
images to consider the global context; (2) a depth encoder that extracts
sparse depth features from sparse input via sparse convolutional blocks; (3) a
decoder that takes both RGB and depth features, and transforms them into dense
depth maps. Data flow contains convolution operations.

####  III-B1 Sparse Convolution

In order to extract features from sparse depth, recent depth completion
methods fall into two groups. One group [9, 11] designs shallow networks with
sparse convolution layers due to the poor performance of standard convolution
layers on sparse input. In contrast, the other group [14, 17, 22] demonstrates
that employing standard convolution layers yields better performance with
their training schemes; these methods also perform well on different levels of
sparsity. Comparing both approaches, we conclude that deep stacks of standard
convolution layers are key to handling sparse depth input. Therefore, we
choose to combine these two approaches by stacking sparse convolution layers
[9] deeper. Sparse convolution blocks take a sparse depth feature and a binary
observation mask as inputs, which both have the same spatial size. Since an
observation mask indicates the reliability of each location of the feature
maps, the convolution operations only attend on reliable input features which
are involved with sparse depth input. As a result, the depth encoder is able
to propagate depth information from reliable sparse depth input to its
surrounding depth features. In contrast to sparsity invariant convolutions
[9], we do not apply mask normalization, which causes a degradation problem
due to the small values extracted from the depth encoder when stacking deep
layers.

####  III-B2 Pixel-Adaptive Convolution (PAC)

Recent works utilize operations like concatenation or element-wise addition to
fuse the information from both the RGB and the depth encoder. However, this
simple method is not the optimal way to fuse the information from two
modalities because extracted depth features are not guided by RGB images in a
late-fusion manner. To achieve this, we require spatially-variant convolution
weights that different convolution kernels depending on image features are
applied to different spatial positions of the depth features. Thus, we adopt
pixel-adaptive convolutions (PACs) introduced by Su et al. [35]. Assume that
the PACs take a sparse depth feature map v and an image feature f as input,
and produce the output sparse depth feature $\textbf{v}^{\prime}$. We denote
the convolution weight as W and the bias term as b. PACs augment the spatially
invariant convolution weight W with a local-adaptive kernel function K.
Following the notation in [35], the PAC convolution is defined as

$\begin{split}\textbf{v}^{\prime}_{i}=\sum_{j\in\Omega(i)}K(\textbf{f}_{i},\textbf{f}_{j})\textbf{W}[\textbf{p}_{i}-\textbf{p}_{j}]\textbf{v}_{j}+\textbf{b}\end{split}$
(6)

where f are image features from the RGB encoder and act as guidance for the
PACs in the depth encoder. High-level image features are preferable because
they contain image context information. The kernel function K has a standard
Gaussian form:
$K(\textbf{f}_{i},\textbf{f}_{j})=exp(-\frac{1}{2}(\textbf{f}_{i}-\textbf{f}_{j})^{T}(\textbf{f}_{i}-\textbf{f}_{j}))$.
This kernel computes the correlation between image features and guides the
standard convolutional weights to generate depth features depending on the
content learned from the RGB encoder. This spatially-variant kernel is helpful
because, for instance, depth features on a person should not be applied to
generate depth maps on the wall. Thus, PACs enable our proposed architecture
to generate intermediate depth features consistent with image content.

####  III-B3 Decoder

The decoder is similar to Ma et al [17] with one major difference. Unlike
their method, our proposed network predicts inverse depth instead of depth.
Thus, we replace the ReLU nonlinearity function with sigmoid activation. We
observe that applying a sigmoid function is critical for training stability
and is more robust to diverse depth ranges on challenging indoor scenes.
Without inverse depth prediction, we fail to train the network proposed by
[17] on our challenging indoor datasets.

##  IV Implementation and Performance

###  IV-A Datasets

To demonstrate that our proposed method performs robustly in the challenging
environment, we experiment with NAVERLABS indoor dataset. Additionally, we
evaluate our method on two benchmarks: the NYUv2 dataset and KITTI. For indoor
scenes, we report five evaluation metrics: root mean squared error (RMSE),
mean absolute relative error (ABS Rel), and $\delta_{i}$ ,which means the
percentage of predicted pixels for which the relative error is less than a
threshold $i$. The RMSE is represented in $mm$ scale. For the KITTI benchmark,
we use four official metrics for evaluation.

####  IV-A1 NAVERLABS indoor dataset

NAVERLABS dataset [37] comprises data collected from three different places:
Department Store B1 (Dept. B1), Department Store 1F (Dept. 1F), and Metro
Station (MS). All data were collected using a mapping robot equipped with two
16-channel LiDAR sensors and six RGB cameras with 2592$\times$2048 resolution.
LiDAR SLAM is used to estimate sensor poses for our dataset, and this pose
information enables us to generate depth maps. We captured 17K images for
Dept. 1F, 32K images for Dept. B1, and 61K images for MS. The MS dataset was
captured at a highly crowded metro station.

We accumulate consecutive LiDAR sweeps and project the point clouds onto each
of six cameras in order to generate depth maps. These depth maps can be used
as sparse input and ground truth for evaluation. In order to create sparse
input, we accumulate 0.3 seconds of LiDAR scans, which correspond to one LiDAR
scan since the LiDAR is sampled at 10 Hz (see the second column in Fig. 5). In
the Dept. 1F and Dept. B1 datasets, we collect 1 second of LiDAR scans to
generate ground truth depth for training supervised depth completion
algorithms (see the third column in Fig. 5). However, the depth maps generated
from the MS dataset are too noisy to serve as ground truth due to noise caused
by moving objects (see SS-(c) in Fig. 5). For evaluation, we select the high-
quality depth maps generated from projecting a LiDAR 3D model onto the camera
frames in the Dept. 1F and Dept. B1 datasets (see 1F-(d) and B1-(d) in Fig.
5). In contrast, we use the SfM method [42] to reconstruct a sparse 3D model
of the MS dataset and MVS system [43] to produce dense depth maps instead of
noisy depth maps from LiDAR point clouds. Given the pose from LiDAR SLAM, we
can obtain a 3D model aligned with the LiDAR data. SS-(d) in Fig. 5 generated
by the SfM is the example of depth maps for evaluation.

Figure 5: Samples from the NAVERLABS indoor dataset. We include more samples
and demonstrate many challenging features from our datasets in supplementary
video.

####  IV-A2 NYU-Depth-v2 dataset

The NYUv2 dataset [39] comprises RGB images and depth maps collected from
Microsoft Kinect in 464 indoor scenes. The raw training dataset contains 268K
images. We downsampled 10 times to remove redundant frames, resulting in 47k
frames sampled for the training set. Our method is tested on the 654 official
labeled test set for evaluation.

####  IV-A3 KITTI depth completion dataset

The KITTI depth completion dataset [9] provides RGB images, sparse lidar
points, and dense ground truth depth. Following the official split, it
contains 86k frames for the training set, 1k frames for the validation set,
and 1k frames for the evaluation.

###  IV-B Implementation Details

We adopt ResNet34 [34] as the RGB encoder, and it was pretrained on ImageNet
[41]. The proposed deep networks were implemented with PyTorch [40] and
trained on 4 Tesla V100 GPUs. We trained our network from scratch for 30
epochs, with a batch size of 16 using Adam [44], where $\beta_{1}=0.9$,
$\beta_{2}=0.999$; we used an input resolution of 1024$\times$760 for
NAVERLABS, 640$\times$480 for NYUv2, and 1024$\times$320 for KITTI. We used an
initial learning rate of $10^{-4}$ for the first 10 epochs and halved it every
10 epochs. In loss functions, we set the $\alpha$ to 0.85, $\lambda_{d}$ to
0.001 and $\lambda_{s}$ to 0.1.

###  IV-C Experiments on NAVERLABS indoor datasets

Figure 6:  SD represents a sparse depth. We design 4 architectures: (a) 1e-1d:
an encoder and a decoder; (b) 2e-1d: an RGB encoder, a depth encoder, and a
decoder; (c) 2es-1d: an RGB encoder, a depth encoder with sparse convolutions,
and a decoder; (d) 2es-1dp: the same architecture as Fig. 4.  TABLE I:  Depth
completion results on NAVERLABS indoor dataset.

(a) Dept. 1F Dataset
---
Method | T | RMSE $\downarrow$ | ABS Rel $\downarrow$ |  $\delta_{1.25}$ $\uparrow$ |  $\delta_{1.25^{2}}$ $\uparrow$ |  $\delta_{1.25^{3}}$ $\uparrow$
UNET [17] | S | 5043.5 | 0.571 | 0.273 | 0.463 | 0.553
nUNET [15] | S | 4993.8 | 0.171 | 0.898 | 0.933 | 0.951
CSPN [14] | S | 2857.1 | 0.266 | 0.808 | 0.886 | 0.924
MD2 [4] | SS | 3862.4 | 0.493 | 0.488 | 0.716 | 0.818
1e-1d | SS | 2899.6 | 0.256 | 0.784 | 0.869 | 0.911
2e-1d | SS | 2801.4 | 0.265 | 0.783 | 0.868 | 0.909
2es-1d | SS | 2700.3 | 0.242 | 0.790 | 0.875 | 0.915
Ours | SS | 2692.9 | 0.234 | 0.815 | 0.887 | 0.926
|  |  |  |  |  |
(b) Dept. B1 Dataset
Method | T | RMSE $\downarrow$ | ABS Rel $\downarrow$ |  $\delta_{1.25}$ $\uparrow$ |  $\delta_{1.25^{2}}$ $\uparrow$ |  $\delta_{1.25^{3}}$ $\uparrow$
UNET [17] | S | 3048.5 | 0.346 | 0.599 | 0.711 | 0.764
nUNET [15] | S | 2963.1 | 0.324 | 0.635 | 0.732 | 0.779
CSPN [14] | S | 2162.2 | 0.199 | 0.774 | 0.890 | 0.938
MD2 [4] | SS | 3592.7 | 0.338 | 0.47 | 0.729 | 0.862
1e-1d | SS | 2210.5 | 0.186 | 0.823 | 0.914 | 0.947
2e-1d | SS | 2157.5 | 0.170 | 0.832 | 0.916 | 0.949
2es-1d | SS | 2116.8 | 0.183 | 0.829 | 0.916 | 0.949
Ours | SS | 2024.1 | 0.178 | 0.841 | 0.922 | 0.953
|  |  |  |  |  |
(c) Metro Station Dataset
Method | T | RMSE $\downarrow$ | ABS Rel $\downarrow$ |  $\delta_{1.25}$ $\uparrow$ |  $\delta_{1.25^{2}}$ $\uparrow$ |  $\delta_{1.25^{3}}$ $\uparrow$
UNET [17] | S | 4029.7 | 0.749 | 0.201 | 0.219 | 0.23
nUNET [15] | S | 2705.1 | 0.472 | 0.444 | 0.528 | 0.582
MD2 [4] | SS | 1321.2 | 0.166 | 0.8 | 0.916 | 0.939
Ours | SS | 1248.4 | 0.138 | 0.866 | 0.923 | 0.942

“S” represents supervised training methods and “SS” denotes self-supervised
training methods. Different from other depth completion methods, MD2 is based
on self-supervised depth estimation with monocular video sequences. Compared
to prior self- and fully- supervised methods, our proposed method demonstrates
improvement in RMSE metric by 5.8% in Dept. 1F, by 6.4% in Dept. B1 and by
5.5% in Metro Station.

Figure 7: Examples of depth artifacts generated by 1e-1d model. The top
(NYUv2) and bottom (Dept. 1F) figures in third column shows irregular sparse
patterns copied from sparse inputs and blurred depth boundaries Figure 8:
Qualitative comparison with “UNET” [17], “nUNET” [15], and “CSPN” [14] on the
NAVERLABS indoor dataset. As mentioned in Sec. IV-A1, the groundtruth of the
Metro Station dataset is the results of MVS. (low  high; grey means empty
depth values.)

We compare our proposed method with 4 baseline approaches with public codes:
1) UNET is a U-shaped ResNet [17]; 2) nUNET is an early-fusion encoder-decoder
network combined with multiple normalization convolutions [15]; 3) CSPN learns
the affinity to perform sparse depth propagation [14]; 4) Monodepth2 (MD2) is
based on ResNet34 [4]. The same relative pose generated from our method is
applied to training MD2 for a fair comparison. MD2 benefits from the use of
ground truth median scaling at inference, while other depth completion methods
utilize unmodified network prediction. Except for 4), the aforementioned
methods are based on supervised training with ground truth depth. As mentioned
in Section IV-A, it is difficult to create ground truth depth for the Metro
Station dataset (MS). In the case of the MS dataset, we only use the sparse
depth maps as weak supervisions for supervised depth completion. Quantitative
results are shown in Table I, and the associated qualitative comparisons are
shown in Fig. 8. We train the model from Ma et al. [17] with its network
architecture and the relative poses from our method, which are more accurate.
Note that Ma et al. failed to produce meaningful results. We observe that the
network just copies the sparse inputs, meaning that the sparse depth loss only
serves as supervision for training while the photometric loss is unreliable.

In contrast, our method successfully performs depth completion in the
NAVLERLABS dataset. This indicates that our training framework is more robust
to variant supervision compared to other self-supervised depth completion
methods. The performance of our method is superior to existing supervised
completion methods. From columns 4 through 6 of Fig. 8, we can observe that
supervised depth completion methods rely heavily on the density of ground
truth depth. We notice that these algorithms fail to fill the holes where
LiDAR information does not exist (e.g., the upper part of the image) due to
the sensor configuration. In contrast, thanks to the effectiveness of
photometric loss, the proposed method succeed in filling empty regions such as
the ceiling, which LiDAR sensors are not able to measure, with accurate depth
values. In addition, our method even predicts the correct depth map on shiny
or transparent surface which cannot be scanned accurately by sensors (see
First row in Fig. 8). The experimental results of CSPN bolster this
observation because our method achieves performance comparable to the
supervised setting in Table I-(a), (b), while its training with weak
supervision collapsed on the MS dataset. If we collect the high-quality dense
depth maps (see the last column in Fig. 8), the supervised depth completion
methods can be superior to our method. However, collecting dense depth maps
requires a high cost and can be impractical in certain environments such as
the MS dataset.

TABLE II:  depth completion results on the NYUv2 dataset

Method | T | RMSE $\downarrow$ | ABS Rel $\downarrow$ |  $\delta_{1.25}$ $\uparrow$ |  $\delta_{1.25^{2}}$ $\uparrow$ |  $\delta_{1.25^{3}}$ $\uparrow$
---|---|---|---|---|---|---
(a) 500 Samples
Ma et al. [10] | S | 0.204 | 0.043 | 97.8 | 99.6 | 99.9
CSPN [14] | S | 0.117 | 0.016 | 99.2 | 99.9 | 100
Ma et al. [17] | SS | 0.271 | 0.068 | - | - | -
Ours | SS | 0.178 | 0.033 | 98.1 | 99.7 | 100
(b) 200 Samples
Ma et al. [10] | S | 0.230 | 0.044 | 97.1 | 99.4 | 99.8
Yang et al. [16] | SS | 0.569 | 0.171 | - | - | -
Yoon et al. [26] | SS | 0.309 | - | - | - | -
Ours | SS | 0.240 | 0.048 | 96.6 | 99.4 | 99.9

TABLE III:  depth completion results on the KITTI validation set

Method | T | RMSE [mm] | MAE [mm] | iRMSE [1/km] | iMAE [1/km]
---|---|---|---|---|---
Uhrig et al. [9] | S | 1601.33 | 481.27 | 4.94 | 1.78
Ma et al. [17] | S | 814.73 | 249.95 | 2.80 | 1.21
Yoon et al. [26] | SS | 1593.37 | 547.00 | 27.98 | 2.36
Ma et al. [17] | SS | 1343.33 | 358.66 | 4.28 | 1.64
Yang et al. [16] | SS | 1310.03 | 347.17 | - | -
Ours | SS | 1212.89 | 346.12 | 3.54 | 1.29

“S” represents supervised training methods and “SS” denotes self-supervised
training methods. Compared to prior self-supervised method, our method reduces
the RMSE by 34.3% in NYUv2 and by 7.4% in KITTI.

To investigate the impact of our network architecture, we conduct ablation
studies for different network configurations on the NAVERLABS dataset. Figure
6 illustrates the network variants, and their quantitative results are shown
in Table I. Comparing the results of 1e-1d with those of 2e-1d, we observe
that fusing the RGB and depth feature at the earliest stage worsens the
results. With the early fusion, we often observe depth with blurrier depth
discontinuities, as seen in Fig. 7. With PAC, depth maps can eliminate either
irregular lattice patterns from LiDAR or sparse points from sampled depth
maps. We conclude that the late fusion is more effective for self-supervised
learning because image and depth features are heterogeneous data, and early
fusion is more likely to produce noisy initial depth values.

###  IV-D Experiments on Public Benchmark Datasets

To verify the performance of our method on public datasets, we train and
evaluate our method on the NYUv2 dataset. Following previous works, we
uniformly sample 200 and 500 sparse depth points separately for sparse input.
Except for supervised depth completion methods, our proposed method achieves
the best performance among self-supervised depth completion methods in Table
III.

In order to prove the generalization capability of our method, we train and
evaluate our method on an outdoor dataset, the KITTI depth completion dataset.
The comparison results are shown in Table III. We observe that our method
outperforms other self-supervised depth completion methods on every metric.
Although Yang [16] pretrains their network using a virtual dataset such as the
Virtual KITTI dataset [45], which is similar to the benchmark dataset, our
method performs better than their method. We include qualitative results in
the supplementary video.

##  V Conclusions, Limitations, and Future Work

In this paper, we investigated the self-supervised depth completion framework
for a challenging indoor environment. We provide two main research
contributions. First, we introduced a training framework that leads to stable
self-supervised training. Second, we proposed a novel architecture to combine
image features and sparse depth features effectively. In indoor environments,
our method outperforms other self-supervised methods and is competitive with
supervised methods. Furthermore, it generalizes better to all public benchmark
datasets. As part of future work, we would like to apply this method to
complement depth sensors for mobile robots in indoor environments and and
evaluate its benefits for robot navigation. A limitation of the current method
is the high computational cost for embedded platforms. For robotic tasks, we
would like to explore network compression algorithms to reduce computational
complexity and latency.

## ACKNOWLEDGMENT

This work was supported by the Institute of Information & Communications
Technology Planning & Evaluation(IITP) grant funded by the Korea
government(MSIT) (No. 2019-0-01309, Development of AI Technology for Guidance
of a Mobile Robot to its Goal with Uncertain Maps in Indoor/Outdoor
Environments). This work was supported in part by ARO Grants W911NF1910069,
W911NF2110026 and W911NF1910315 and NSF grant 2031901.

## References

  * [1] Zhou, Tinghui, Matthew Brown, Noah Snavely, and David G. Lowe. “Unsupervised learning of depth and ego-motion from video.” In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1851-1858. 2017.
  * [2] Godard, Clément, Oisin Mac Aodha, and Gabriel J. Brostow. “Unsupervised monocular depth estimation with left-right consistency.” In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 270-279. 2017.
  * [3] Wang, Chaoyang, José Miguel Buenaposada, Rui Zhu, and Simon Lucey. “Learning depth from monocular videos using direct methods.” In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 2022-2030. 2018.
  * [4] Godard, Clément, Oisin Mac Aodha, Michael Firman, and Gabriel J. Brostow. “Digging into self-supervised monocular depth estimation.” In Proceedings of the IEEE international conference on computer vision, pp. 3828-3838. 2019.
  * [5] Zhou, Junsheng, Yuwang Wang, Kaihuai Qin, and Wenjun Zeng. “Moving indoor: Unsupervised video depth learning in challenging environments.” In Proceedings of the IEEE International Conference on Computer Vision, pp. 8618-8627. 2019.
  * [6] Sattler, Torsten, Qunjie Zhou, Marc Pollefeys, and Laura Leal-Taixe. “Understanding the limitations of cnn-based absolute camera pose regression.” In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 3302-3312. 2019.
  * [7] Zhao, Wang, Shaohui Liu, Yezhi Shu, and Yong-Jin Liu. “Towards Better Generalization: Joint Depth-Pose Learning without PoseNet.” In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 9151-9161. 2020.
  * [8] Bian, Jia-Wang, Huangying Zhan, Naiyan Wang, Tat-Jun Chin, Chunhua Shen, and Ian Reid. “Unsupervised Depth Learning in Challenging Indoor Video: Weak Rectification to Rescue.” arXiv preprint arXiv:2006.02708 (2020).
  * [9] Uhrig, Jonas, Nick Schneider, Lukas Schneider, Uwe Franke, Thomas Brox, and Andreas Geiger. “Sparsity invariant cnns.” In 2017 international conference on 3D Vision (3DV), pp. 11-20. IEEE, 2017.
  * [10] Mal, Fangchang, and Sertac Karaman. “Sparse-to-dense: Depth prediction from sparse depth samples and a single image.” In 2018 IEEE International Conference on Robotics and Automation (ICRA), pp. 1-8. IEEE, 2018.
  * [11] Eldesokey, Abdelrahman, Michael Felsberg, and Fahad Shahbaz Khan. “Propagating confidences through cnns for sparse data regression.” arXiv preprint arXiv:1805.11913 (2018).
  * [12] Jaritz, Maximilian, Raoul De Charette, Emilie Wirbel, Xavier Perrotton, and Fawzi Nashashibi. “Sparse and dense data with cnns: Depth completion and semantic segmentation.” In 2018 International Conference on 3D Vision (3DV), pp. 52-60. IEEE, 2018.
  * [13] Zhang, Yinda, and Thomas Funkhouser. “Deep depth completion of a single rgb-d image.” In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 175-185. 2018.
  * [14] Cheng, Xinjing, Peng Wang, and Ruigang Yang. “Depth estimation via affinity learned with convolutional spatial propagation network.”In Proceedings of the European Conference on Computer Vision (ECCV), pp. 103-119. 2018.
  * [15] Eldesokey, Abdelrahman, Michael Felsberg, and Fahad Shahbaz Khan. “Confidence propagation through cnns for guided sparse depth regression.” IEEE transactions on pattern analysis and machine intelligence (2019).
  * [16] Yang, Yanchao, Alex Wong, and Stefano Soatto. “Dense depth posterior (ddp) from single image and sparse range.” In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 3353-3362. 2019.
  * [17] Ma, Fangchang, Guilherme Venturelli Cavalheiro, and Sertac Karaman. “Self-supervised sparse-to-dense: Self-supervised depth completion from lidar and monocular camera.” In 2019 International Conference on Robotics and Automation (ICRA), pp. 3288-3295. IEEE, 2019.
  * [18] Zhang, Yilun, Ty Nguyen, Ian D. Miller, Shreyas S. Shivakumar, Steven Chen, Camillo J. Taylor, and Vijay Kumar. “Dfinenet: Ego-motion estimation and depth refinement from sparse, noisy depth input with rgb guidance.” arXiv preprint arXiv:1903.06397 (2019).
  * [19] Qiu, Jiaxiong, Zhaopeng Cui, Yinda Zhang, Xingdi Zhang, Shuaicheng Liu, Bing Zeng, and Marc Pollefeys. “Deeplidar: Deep surface normal guided depth prediction for outdoor scene from sparse lidar data and single color image.” In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 3313-3322. 2019.
  * [20] Xu, Yan, Xinge Zhu, Jianping Shi, Guofeng Zhang, Hujun Bao, and Hongsheng Li. “Depth completion from sparse lidar data with depth-normal constraints.” In Proceedings of the IEEE International Conference on Computer Vision, pp. 2811-2820. 2019.
  * [21] Zhong, Yiqi, Cho-Ying Wu, Suya You, and Ulrich Neumann. “Deep rgb-d canonical correlation analysis for sparse depth completion.” In Advances in Neural Information Processing Systems, pp. 5331-5341. 2019.
  * [22] Cheng, Xinjing, Peng Wang, Chenye Guan, and Ruigang Yang. “CSPN++: Learning Context and Resource Aware Convolutional Spatial Propagation Networks for Depth Completion.” In AAAI, pp. 10615-10622. 2020.
  * [23] Teixeira, Lucas, Martin R. Oswald, Marc Pollefeys, and Margarita Chli. “Aerial Single-View Depth Completion With Image-Guided Uncertainty Estimation.” IEEE Robotics and Automation Letters 5, no. 2 (2020): 1055-1062.
  * [24] Tang, Jie, Fei-Peng Tian, Wei Feng, Jian Li, and Ping Tan. “Learning guided convolutional network for depth completion.” arXiv preprint arXiv:1908.01238 (2019).
  * [25] Eldesokey, Abdelrahman, Michael Felsberg, Karl Holmquist, and Michael Persson. “Uncertainty-Aware CNNs for Depth Completion: Uncertainty from Beginning to End.” In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 12014-12023. 2020
  * [26] Yoon, Sungho, and Ayoung Kim. “Balanced Depth Completion between Dense Depth Inference and Sparse Range Measurements via KISS-GP.” arXiv preprint arXiv:2008.05158 (2020).
  * [27] Huang, Yu-Kai, Tsung-Han Wu, Yueh-Cheng Liu, and Winston H. Hsu. “Indoor Depth Completion with Boundary Consistency and Self-Attention.” In Proceedings of the IEEE International Conference on Computer Vision Workshops, pp. 0-0. 2019.
  * [28] Senushkin, Dmitry, Ilia Belikov, and Anton Konushin. “Decoder Modulation for Indoor Depth Completion.” arXiv preprint arXiv:2005.08607 (2020).
  * [29] Park, Jae Sung, and Dinesh Manocha. “Efficient probabilistic collision detection for non-Gaussian noise distributions.” IEEE Robotics and Automation Letters 5, no. 2 (2020): 1024-1031.
  * [30] Sathyamoorthy, Adarsh Jagan, Utsav Patel, Tianrui Guan, and Dinesh Manocha. “Frozone: Freezing-Free, Pedestrian-Friendly Navigation in Human Crowds.” IEEE Robotics and Automation Letters (2020).
  * [31] Sathyamoorthy, Adarsh Jagan, Jing Liang, Utsav Patel, Tianrui Guan, Rohan Chandra, and Dinesh Manocha. “Densecavoid: Real-time navigation in dense crowds using anticipatory behaviors.” arXiv preprint arXiv:2002.03038 (2020).
  * [32] Hirschmuller, Heiko. “Stereo processing by semiglobal matching and mutual information.” IEEE Transactions on pattern analysis and machine intelligence 30, no. 2 (2007): 328-341.
  * [33] Wang, Zhou, Alan C. Bovik, Hamid R. Sheikh, and Eero P. Simoncelli. “Image quality assessment: from error visibility to structural similarity.” IEEE transactions on image processing 13, no. 4 (2004): 600-612.
  * [34] He, Kaiming, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. “Deep residual learning for image recognition.” In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778. 2016.
  * [35] Su, Hang, Varun Jampani, Deqing Sun, Orazio Gallo, Erik Learned-Miller, and Jan Kautz. “Pixel-adaptive convolutional neural networks.” In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 11166-11175. 2019.
  * [36] Revaud, Jerome, Cesar De Souza, Martin Humenberger, and Philippe Weinzaepfel. “R2d2: Reliable and repeatable detector and descriptor.” In Advances in Neural Information Processing Systems, pp. 12405-12415. 2019.
  * [37] Min Young Chang, Suyong Yeon, Soohyun Ryu and Donghwan Lee. “SpoxelNet: Spherical Voxel-based Deep Place Recognition for 3D Point Clouds of Crowded Indoor Spaces” In Intelligent Robots and Systems (IROS), 2020 IEEE/RSJ International Conference on. IEEE, 2020, pp. 8564–8570.
  * [38] Geiger, Andreas, Philip Lenz, and Raquel Urtasun. “Are we ready for autonomous driving? the kitti vision benchmark suite.” In 2012 IEEE Conference on Computer Vision and Pattern Recognition, pp. 3354-3361. IEEE, 2012.
  * [39] Silberman, Nathan, Derek Hoiem, Pushmeet Kohli, and Rob Fergus. “Indoor segmentation and support inference from rgbd images.” In European conference on computer vision, pp. 746-760. Springer, Berlin, Heidelberg, 2012.
  * [40] Paszke, Adam, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. “Automatic differentiation in pytorch.” (2017).
  * [41] Russakovsky, Olga, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang et al. “Imagenet large scale visual recognition challenge.” International journal of computer vision 115, no. 3 (2015): 211-252.
  * [42] Schonberger, Johannes L., and Jan-Michael Frahm. “Structure-from-motion revisited.” In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 4104-4113. 2016.
  * [43] Schönberger, Johannes L., Enliang Zheng, Jan-Michael Frahm, and Marc Pollefeys. “Pixelwise view selection for unstructured multi-view stereo.” In European Conference on Computer Vision, pp. 501-518. Springer, Cham, 2016.
  * [44] Kingma, Diederik P., and Jimmy Ba. “Adam: A method for stochastic optimization.” arXiv preprint arXiv:1412.6980 (2014).
  * [45] Gaidon, Adrien, Qiao Wang, Yohann Cabon, and Eleonora Vig. “Virtual worlds as proxy for multi-object tracking analysis.” In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4340-4349. 2016.
  * [46] Lepetit, Vincent, Francesc Moreno-Noguer, and Pascal Fua. “Epnp: An accurate o (n) solution to the pnp problem.” International journal of computer vision 81, no. 2 (2009): 155.
  * [47] Fischler, Martin A., and Robert C. Bolles. “Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography.” Communications of the ACM 24, no. 6 (1981): 381-395.
  * [48] Muja, Marius, and David G. Lowe. ”Fast approximate nearest neighbors with automatic algorithm configuration.” VISAPP (1) 2, no. 331-340 (2009): 2.


# Automorphism group of the holomorph of a cyclic group

Kazuki Sato  National Institute of Technology, Ichinoseki College, Japan
<EMAIL_ADDRESS>
###### Abstract.

We show that the holomorph of a cyclic group of order $n$ is isomorphic to its
own automorphism group when $n$ is twice of a power of an odd prime.

###### 2010 Mathematics Subject Classification:

20D45

##  1\. Introduction

Let $C_{n}$ be a cyclic group of order $n$. In this paper we prove the
following.

######  Theorem 1.1 (Theorem 3.8).

Let $p$ be an odd prime and $e>0$ a positive integer. Assume $n=2p^{e}$. Let
$G=\operatorname{Hol}(C_{n})$ be the holomorph of $C_{n}$. Then there exists
an isomorphism $G\cong\operatorname{Aut}(G)$.

It is known that the automorphism group of the dihedral group $D_{2n}$ of
order $2n$ is isomorphic to the holomorph $\operatorname{Hol}(C_{n})$ of
$C_{n}$ [walls]. It is also known that the holomorph
$\operatorname{Hol}(C_{n})$ of $C_{n}$ is a complete group when $n$ is odd
[miller]. In particular, $\operatorname{Hol}(C_{n})$ is isomorphic to
$\operatorname{Aut}(\operatorname{Hol}(C_{n}))$ when $n$ is odd. But when $n$
is even, the center $Z(\operatorname{Hol}(C_{n}))$ is nontrivial (see Lemma
2.2), so $\operatorname{Hol}(C_{n})$ is not complete. Despite that fact,
Theorem 1.1 asserts that two groups $\operatorname{Hol}(C_{n})$ and
$\operatorname{Aut}(\operatorname{Hol}(C_{n}))$ are isomorphic as abstract
groups when $n=2p^{e}$. We note that the case $e=1$, that is, $n=2p$ in
Theorem 1.1 is known to be true [svb, Theorem 2.10].

In section $2$, we recall preliminary results from elementary group theory and
number theory. We show our main theorem in section $3$.

##  2\. Preliminaries

###  2.1. Semi-direct product

We will review briefly the notion of a semi-direct product. Given two groups
$A$ and $B$, and a homomorphism $\theta:B\to\operatorname{Aut}(A)$, the semi-
direct product gives a group structure to the set $G=A\times B$ by

$(a_{1},b_{1})\cdot(a_{2},b_{2})=(a_{1}\theta(b_{1})(a_{2}),b_{1}b_{2}).$

We will denote the semi-direct product of $A$ by $B$ with
$\theta:B\to\operatorname{Aut}(A)$ by $A\rtimes_{\theta}B$, where $\theta$ may
be omitted if it is clear from the context. We identify an element $a\in A$
with $(a,1)$ and $b\in B$ with $(1,b)$. With these identifications we can see
that all the elements of $A\rtimes_{\theta}B$ can be written uniquely in the
form $ab$ with $a\in A$ and $b\in B$. Multiplication of elements from $A$ and
$B$ is determined by the relation $bab^{-1}=\theta(b)(a)$. From these
identifications we can write $A\rtimes_{\theta}B=AB$ with $A\triangleleft
A\rtimes_{\theta}B$ and $A\cap B=1$. In particular
$(A\rtimes_{\theta}B)/A\cong B$. If $B=\operatorname{Aut}(A)$ and $\theta$ is
the identity map, then we call $A\rtimes\operatorname{Aut}(A)$ the holomorph
of $A$ and write it as $\operatorname{Hol}(A)$.

We use the following theorem in section 3.

######  Theorem 2.1 ([Isaacs, Theorem 3.35]).

Let $G$ and $G_{0}$ be groups, and let $N\triangleleft G$ and
$N_{0}\triangleleft G_{0}$, where $G/N$ and $G_{0}/N_{0}$ are cyclic of finite
order $m$. Suppose that $y:N\to N_{0}$ is an isomorphism, and let $gN$ and
$g_{0}N_{0}$ be generating cosets of $G/N$ and $G_{0}/N_{0}$ respectively.
Assume that

$y(g^{m})=(g_{0})^{m}\ \ \ \textrm{and}\ \ \ y(gxg^{-1})=g_{0}y(x)g_{0}^{-1}$

for all elements $x\in N$. Then there is a unique isomorphism $\alpha:G\to
G_{0}$ that extends the given isomorphism $y:N\to N_{0}$ and that satisfies
$\alpha(g)=g_{0}$.

###  2.2. Dihedral Groups

Let $n$ be a positive integer. In this paper we let $C_{n}$ denote the cyclic
group of order $n$ and $D_{2n}$ the dihedral group of order $2n$. As mentioned
in the Introduction, it is known that the automorphism group
$\operatorname{Aut}(D_{2n})$ of $D_{2n}$ is isomorphic to the holomorph
$\operatorname{Hol}(C_{n})$ of $C_{n}$.

######  Lemma 2.2.

Let $n$ be an even integer. Let $G=\operatorname{Hol}(C_{n})$ be the holomorph
of $C_{n}$. Then the center $Z(G)$ of $G$ is equal to $\\{1,z\\}$, where $z\in
C_{n}$ is the unique involution.

###### Proof.

Since $y(z)\in C_{n}$ is also an involution for any
$y\in\operatorname{Aut}(C_{n})$, we have $yzy^{-1}=y(z)=z$. Hence
$\\{1,z\\}\subset Z(G)$. We have to show the reverse inclusion.

Let $xy\in Z(G)$, where $x\in C_{n},y\in\operatorname{Aut}(C_{n})$. Then we
have $(xy)x^{\prime}=x^{\prime}(xy)$ for any $x^{\prime}\in C_{n}$. Note that
$yx^{\prime}=y(x^{\prime})y$, so
$xy(x^{\prime})y=x(yx^{\prime})=(xy)x^{\prime}=x^{\prime}(xy)=xx^{\prime}y$
for any $x^{\prime}\in C_{n}$. This implies that $y(x^{\prime})=x^{\prime}$
for any $x^{\prime}\in C_{n}$, hence $y=1\in\operatorname{Aut}(C_{n})$. Let
$\iota\in\operatorname{Aut}(C_{n})$ be the automorphism given by
$\iota(x)=x^{-1}$. Since $x\in Z(G)$, we have $x=\iota
x\iota^{-1}=\iota(x)=x^{-1}$. Therefore $x^{2}=1$, that is, $x=1$ or $x=z$ is
the involution. This shows that $Z(G)\subset\\{1,z\\}$. ∎

If $G$ is an arbitrary group, then $G/Z(G)$ is naturally isomorphic to the
group of inner automorphisms $\operatorname{Inn}(G)$. If $Z(G)=1$, therefore,
$G\cong\operatorname{Inn}(G)$, and so we can identify $G$ with
$\operatorname{Inn}(G)$ via the natural isomorphism, and this embeds $G$ as a
subgrouop of the automorphism group $\operatorname{Aut}(G)$. We say that $G$
is complete if $Z(G)=1$ and $\operatorname{Aut}(G)=\operatorname{Inn}(G)$. It
is known that $\operatorname{Aut}(D_{2n})\cong\operatorname{Hol}(C_{n})$ is
complete when $n$ is odd. But when $n$ is even, $\operatorname{Aut}(D_{2n})$
can never be complete.

###  2.3. Elementary number theory

######  Lemma 2.3.

Let $k$ be an integer and $p$ a prime. Assume that $k\equiv 1\mod p$. Then
$k^{p^{e-1}}\equiv 1\mod p^{e}$ for any $e\geq 1$.

###### Proof.

By induction on $e$. Assume that $k^{p^{e-1}}\equiv 1\mod p^{e}$ for some
$e\geq 1$. Then $k^{p^{e-1}}=1+rp^{e}$ for some integer $r$. Hence we have

$k^{p^{e}}=(1+rp^{e})^{p}=1+\sum_{i=1}^{p-1}\binom{p}{i}r^{i}p^{ei}+r^{p}p^{ep}.$

For each $1\leq i\leq p-1$, since $\binom{p}{i}$ is divisible by $p$, we see
that $\binom{p}{i}p^{ei}\equiv 0\mod p^{e+1}$. Clearly $p^{ep}\equiv 0\mod
p^{e+1}$. This shows that $k^{p^{e}}\equiv 1\mod p^{e+1}$. ∎

######  Lemma 2.4.

Let $p$ be an odd prime and $e>0$. Let $k$ be an integer coprime to
$n=2p^{e}$. Assume that the order of $k\in({\mathbb{Z}}/n{\mathbb{Z}})^{*}$ is
$\phi(n)=p^{e-1}(p-1)$, where $\phi$ is Euler’s totient funciton. Then

  1. (i)

$k-1$ is not divisible by $p$,

  2. (ii)

the greatest common divisor of $n$ and $k-1$ is $(n,k-1)=2$,

  3. (iii)

$1+k+k^{2}+\dots+k^{\phi(n)-1}\equiv 0\mod n$.

###### Proof.

(i) Assume $k\equiv 1\mod p$. Then $k^{p^{e-1}}\equiv 1\mod p^{e}$ from Lemma
2.3. Since $k$ is odd, we also have $k^{p^{e-1}}\equiv 1\mod 2$. Hence
$k^{p^{e-1}}\equiv 1\mod n$, so the order of
$k\in({\mathbb{Z}}/n{\mathbb{Z}})^{*}$ divides $p^{e-1}<p^{e-1}(p-1)=\phi(n)$,
contradiction.

(ii) Since $n$ and $k-1$ are even, $2|(n,k-1)$. On the other hand, $(n,k-1)$
is not divisible by $p$ by (i). This shows (ii).

(iii) See [svb, Theorem 2.5]. ∎

##  3\. Main theorem

In this section, we fix the notation as follows. Let $e>0$ be an integer and
$p$ an odd prime. Put $n:=2p^{e}$. Then the automorphism group
$\operatorname{Aut}(C_{n})$ is a cyclic group of order $\phi(n)=p^{e-1}(p-1)$.
We fix generators $x\in C_{n}$ and $y\in\operatorname{Aut}(C_{n})$. Assume
that $y(x)=x^{k}$, where $k$ is an integer coprime to $n$ with $1<k<n$. In
this situation, there exists an isomorphism
$\operatorname{Aut}(C_{n})\cong({\mathbb{Z}}/n{\mathbb{Z}})^{*}$ that maps $y$
to $k$. We note that the order of $k\in({\mathbb{Z}}/n{\mathbb{Z}})^{*}$ is
$\phi(n)$. Let
$G:=\operatorname{Hol}(C_{n})=C_{n}\rtimes\operatorname{Aut}(C_{n})$ be the
holomorph of $C_{n}$. Then $G$ is generated by $x$ and $y$, and the elements
of $G$ can be written in the form $x^{a}y^{b}$. We see that
$x^{a}y^{b}=x^{c}y^{d}$ if and only if $a\equiv c\mod n$ and $b\equiv
d\mod\phi(n)$. We have the following relations in $G$;

$x^{n}=1,\ y^{\phi(n)}=1,\ yxy^{-1}=y(x)=x^{k}.$

######  Lemma 3.1.

$y^{b}x^{a}y^{-b}=x^{ak^{b}}$ holds for any integer $a$ and nonnegative
integer $b$.

###### Proof.

By induction on $b$. The case $b=0$ is trivial. Assume that $b>0$ and that
$y^{b-1}x^{a}y^{-(b-1)}=x^{ak^{b-1}}$ for any $a$. Then we have
$y^{b}x^{a}y^{-b}=y^{b-1}yx^{a}y^{-1}y^{-(b-1)}=y^{b-1}x^{ak}y^{-(b-1)}=x^{akk^{b-1}}=x^{ak^{b}}$.
Here, for the second equality, we used the relation in $G$ and for the third
equality, we used the inductive hypothesis. ∎

######  Lemma 3.2.

$(x^{a}y^{b})^{m}=x^{a(1+k^{b}+\dots+k^{b(m-1)})}y^{bm}$ holds for any integer
$a$, nonnegative integer $b$ and positive integer $m$.

###### Proof.

By induction on $m$. The case $m=1$ is trivial. Assume that $m>1$. Then

$\displaystyle(x^{a}y^{b})^{m}$ $\displaystyle=(x^{a}y^{b})^{m-1}x^{a}y^{b}$
$\displaystyle=x^{a(1+k^{b}+\dots+k^{b(m-2)})}y^{b(m-1)}x^{a}y^{b}$
$\displaystyle=x^{a(1+k^{b}+\dots+k^{b(m-2)})}y^{b(m-1)}x^{a}y^{-b(m-1)}y^{bm}$
$\displaystyle=x^{a(1+k^{b}+\dots+k^{b(m-2)})}x^{ak^{b(m-1)}}y^{bm}$
$\displaystyle=x^{a(1+k^{b}+\dots+k^{b(m-1)})}y^{bm}.$

Here, for the second equality, we used the inductive hypothesis and for the
fourth equality, we used Lemma 3.1. ∎

######  Lemma 3.3.

Let $\alpha\in\operatorname{Aut}(G)$. Then $\alpha(x)=x^{a}$ for some integer
$a$ coprime to $n$. Hence there exists an integer $j$ such that
$\alpha(x)=y^{j}(x)$.

###### Proof.

The last statement is clear from the first one. Let
$\alpha\in\operatorname{Aut}(G)$. Assume
$\alpha(x)=x^{a}y^{b},\alpha(y)=x^{c}y^{d}$ for some integers $a,b,c,d$, with
$0\leq b<\phi(n)$. First, we will show that $b=0$. We must have
$\alpha(y)\alpha(x)\alpha(y^{-1})=\alpha(x^{k})$. It follows that

$(x^{c}y^{d})(x^{a}y^{b})(x^{c}y^{d})^{-1}=(x^{a}y^{b})^{k},$

which considered modulo $\langle x\rangle$ implies that $y^{b}=y^{bk}$, and
thus consequently that $y^{bk-b}=1$. So $bk\equiv b\mod\phi(n)$. Assume
$0<b<\phi(n)$. We note that $k^{b}-1\neq 0$, since $1<k<n$. By Lemma 3.2, we
see that

$(x^{a}y^{b})^{k-1}=x^{a(1+k^{b}+\dots+k^{b(k-2)})}y^{b(k-1)}=x^{a(k^{b(k-1)}-1)/(k^{b}-1)}.$

Since the order of $x^{a}y^{b}=\alpha(x)$ is $n$, the order of
$(x^{a}y^{b})^{k-1}$ is $n/(n,k-1)=n/2$ from Lemma 2.4, (ii). On the other
hand, the order of $x^{a(k^{b(k-1)}-1)/(k^{b}-1)}$ is
$n/\left(n,a\dfrac{k^{b(k-1)}-1}{k^{b}-1}\right)$. Hence

(1) $\left(n,a\dfrac{k^{b(k-1)}-1}{k^{b}-1}\right)=2.$

Recall that $b(k-1)\equiv 0\mod\phi(n)$. Hence

(2) $k^{b(k-1)}\equiv 1\mod n.$

(1) and (2) imply that $k^{b}-1\equiv 0\mod p^{e}$. Since $k$ is odd, we also
have $k^{b}-1\equiv 0\mod 2$. Therefore we can conclude that $k^{b}-1\equiv
0\mod n$. This contradicts the assumptions that
$k\in({\mathbb{Z}}/n{\mathbb{Z}})^{*}$ has order $\phi(n)$ and that
$0<b<\phi(n)$. Hence $b=0$ and $\alpha(x)=x^{a}$. Since $\alpha(x)=x^{a}$ has
order $n$, $a$ is coprime to $n$ and this completes the proof. ∎

######  Lemma 3.4.

Let $\alpha\in\operatorname{Aut}(G)$. Then $\alpha(y)=x^{c}y$ for some integer
$c$.

###### Proof.

Let $\alpha\in\operatorname{Aut}(G)$. By Lemma 3.3, we can assume that
$\alpha(x)=x^{a},\alpha(y)=x^{c}y^{d}$ for some integers $a,c,d$ with $a$
coprime to $n$ and $0\leq d<\phi(n)$. As above we must have

$(x^{c}y^{d})(x^{a})(x^{c}y^{d})^{-1}=(x^{a})^{k}.$

This implies $x^{ak^{d}}=x^{ak}$, so $ak^{d}\equiv ak\mod n$. Since $ak$ is
coprime to $n$, we have $k^{d-1}\equiv 1\mod n$. Hence $d-1\equiv
0\mod\phi(n)$. Therefore $y^{d}=y$, and we have $\alpha(y)=x^{c}y^{d}=x^{c}y$.
∎

We define a map $\psi:\operatorname{Aut}(G)\to G$ as follows. Let
$\alpha\in\operatorname{Aut}(G)$. By Lemmas 3.3 and 3.4, there exist integers
$j$ and $c$ such that $\alpha(x)=y^{j}(x),\alpha(y)=x^{c}y$. We note that
$y^{j}$ and $x^{c}$ are uniquely determined from $\alpha$. We define

$\psi(\alpha)=x^{c}y^{j}.$

######  Proposition 3.5.

The map $\psi:\operatorname{Aut}(G)\to G$ is a group homomorphism.

###### Proof.

Let $\alpha,\beta\in\operatorname{Aut}(G)$. Assume $\psi(\alpha)=x^{c}y^{j}$,
$\psi(\beta)=x^{d}y^{m}$. Then we have
$(\alpha\beta)(x)=\alpha(\beta(x))=\alpha(y^{m}(x))=y^{j}(y^{m}(x))=y^{j+m}(x)$
and
$(\alpha\beta)(y)=\alpha(\beta(y))=\alpha(x^{d}y)=\alpha(x)^{d}\alpha(y)=y^{j}(x^{d})x^{c}y$.
Hence $\psi(\alpha\beta)=y^{j}(x^{d})x^{c}y^{j+m}$. On the other hand, we have
$\psi(\alpha)\psi(\beta)=x^{c}y^{j}x^{d}y^{m}=x^{c}y^{j}(x^{d})y^{j+m}=y^{j}(x^{d})x^{c}y^{j+m}$.
Therefore $\psi(\alpha)\psi(\beta)=\psi(\alpha\beta)$. ∎

######  Proposition 3.6.

The map $\psi:\operatorname{Aut}(G)\to G$ is injective.

###### Proof.

Let $\alpha\in\operatorname{Aut}(G)$. Assume $\psi(\alpha)=x^{c}y^{j}=1$. Then
$x^{c}=1$ and $y^{j}=1$, so we have $\alpha(x)=y^{j}(x)=x$ and
$\alpha(y)=x^{c}y=y$. Since $G$ is generated by $x$ and $y$, we see that
$\alpha$ is the identity map on $G$. ∎

######  Proposition 3.7.

The map $\psi:\operatorname{Aut}(G)\to G$ is surjective.

###### Proof.

Let $z\in G$. Then $z=x^{c}y^{j}$ for some $0\leq c<n$ and $0\leq j<\phi(n)$.
We note that $yC_{n}=(x^{c}y)C_{n}$ is a generating coset of $G/C_{n}$. We
have $(x^{c}y)^{\phi(n)}=x^{c(1+k+\dots+k^{\phi(n)-1})}y^{\phi(n)}=1$ by
Lemmas 3.2 and 2.4, (iii). Furthermore,
$y^{j}(yxy^{-1})=y^{j}(y(x))=y^{j+1}(x)=x^{c}y(y^{j}(x))x^{-c}=(x^{c}y)y^{j}(x)(x^{c}y)^{-1}$.
Taking $i$-th power of both sides, we have
$y^{j}(yx^{i}y^{-1})=(x^{c}y)y^{j}(x^{i})(x^{c}y)^{-1}$ for all integers $i$.
By Theorem 2.1, there exists a unique isomorphism $\alpha:G\to G$ that extends
the isomorphism $y^{j}:\langle x\rangle\to\langle x\rangle$ so that
$\alpha(y)=x^{c}y$. Then $\psi(\alpha)=x^{c}y^{j}=z$ by definiton of $\psi$. ∎

######  Theorem 3.8.

The map $\psi:\operatorname{Aut}(G)\to G$ is an isomorphism.

###### Proof.

This follows from Propositions 3.5, 3.6 and 3.7. ∎

## References


# NLDS-QL: From natural language data science questions to queries on graphs:
analysing patients conditions & treatments

Genoveva Vargas-Solar  1234-5678-9012 French Council of Scientific Research
(CNRS), LIRISLyon38000France<EMAIL_ADDRESS>,  Karim Dao
University Paris DauphineTunisTunisia<EMAIL_ADDRESS>and  Mirian
Halfeld-Ferrari  Université d’Orléans, INSA-CVL LIFOOrléansFrance mirian@univ-
orleans.fr

###### Abstract.

This paper introduces NLDS-QL 111This work was partially funded by the French
CNRS MADICS action DOING and the UEMOA (Union économique et monétaire ouest-
africaine) funding K. Dao’s master., a translator of data science questions
expressed in natural language (NL) into data science queries on graph
databases. Our translator is based on a simplified NL described by a grammar
that specifies sentences combining keywords to refer to operations on graphs
with the vocabulary of the graph schema. The demonstration proposed in this
paper shows NLDS-QL in action within a scenario to explore and analyse a graph
base with patient diagnoses generated with the open-source Synthea.

##  1\. Introduction

The volume of connected data, often modelled as graphs, has grown
exponentially. The availability of these graphs data collections has been
democratised through social networks and knowledge graphs used to explore
content (e.g. scientific papers, clinical cases). Although this accessibility
is promising, it introduces a barrier for non-experts, who have to familiarise
with the nature of the data, the way they have been represented in the
database and the specific query languages or user interfaces to access them.

Besides, the emergence of data science has brought a new type of ’complex’
queries embodying a data analysis scenario. A data science query generally
refers to a workflow of tasks including exploration, data cleaning and
preparation, sampling and analysis. These workflows include visualisation and
evaluation tasks that involve the calculation of scores and metrics.
Implementing these workflows is a challenge even for engineers and data
scientists. In most cases, users should have advanced skills in querying and
analysing the data according to their needs and the type of search questions
to be answered. Requiring formal and technical expertise from non-computer
scientists is not obvious or reasonable.

In our work, the goal is to identify important research questions, formulated
by non-technical experts over data collections. Allowing their expression in
natural language (NL) would optimize data accessibility. However, this
facility implies complex NL analysis, particularly when such questions are
intended to be transformed into sophisticated workflows. Thus, to achieve our
goal, we address the problem under a reverse-engineering strategy: we build a
simplified natural language (NL) grammar and map NL data science questions to
graph data science queries as those proposed by Neo4J DS templates. The users
can then express their questions using this simplified NL with sentences that
correspond to the DS Neo4J templates, seeing and assessing the results and
proposing new questions over an enriched vocabulary that can extend the NL
query language treated by our tool.

### Contribution

We propose NLDS-QL, a semi-automatic and evolutive interface for processing
experts’ NL questions on a given vocabulary. It derives data science query
templates that program the answers to these questions, and offers a
conversational evaluation of results and adapted vocabulary. NLDS-QL is based
on a simplified English NL that associates a vocabulary based on graph schema
keywords to refer to operations on graphs (e.g., attributes describing the
nodes, links, and associated labels). Depending on the type of queries to
explore graphs or to analyse them, their expression in NL can yield to a more
or less complex document.

### Demonstration

NLDS-QL will be presented in the context of medical diagnostics using the
patient graph of the Synthea 222
https://xilinx.github.io/graphanalytics/recom-tg3/synthea-overview.html  data
collection and using Neo4J for running translated queries. Assuming that they
have a collection of data corresponding to medical follow-ups, doctors (users)
express the questions whose answers would be helpful for the elaboration of a
diagnosis and their decision making. Questions described in written or spoken
English can denote navigational, aggregation and data science queries
requiring centrality and clustering algorithms to be expressed and answered.
Given the ambiguity of the NL, the translation of questions can lead to
several Cypher (data science) queries. So the demonstration of NLDS-QL is
proposed under a conversational pipeline where users acquainted with Cypher
can choose the query that best corresponds to their expectations before
executing them. Non-expert users can decide to let the system run different
Cypher queries, analyse their results and then choose one or adjust their
question.

The remainder of the paper is organised as follows. Section 2 synthesises the
main families of works addressing NL to query languages translation and
processing. Section 3 describes the general architecture of NLDS-QL. Section 4
describes the demonstration scenario for NLDS-QL and the tasks proposed to
users during the demo. Section 5 concludes the paper and discusses lessons
learned from the demonstration.

##  2\. Related work

Existing work has addressed data mining using NL, but not yet the expression
of data science questions. There are different approaches to developing a NL
interface for database queries, in general for relational systems. Georgia
Kutrika (Koutrika, 2021) describes the process of handling NL queries with a
workflow that consists of three steps. Given a relational database and
assuming knowledge of the schema vocabulary: 1\. Analysis of the NL query
expression; 2\. Disambiguation and interpretation, which produces a set of
ranked interpretations; 3\. Finally, the translation into SQL and its
execution. Three generations of NL Query to SQL Transformation systems can be
identified (Gkini et al., 2021), namely: (i) Keyword based i.e. information
retrieval techniques to evaluate queries. For example, systems like Discover
(query interpretations as subgraphs), DiscoverIR (Song et al., 2015; Lakhanpal
et al., 2015), Spark (ranking and fast execution) (Thomas, 2020). (ii) NL
processing based like NaLIR (parser) (Li and Jagadish, 2014), ATHENA (Saha et
al., 2016) (ontologies and mappings). (iii) Machine translation using neural
networks (Baevski et al., 2020), like NL to SQL conversion as a language
translation problem. The challenge is training a neural network on a large
number of NL/SQL query pairs. Approaches like SQLNet (Xu et al., 2017),
Hydranet adopt this strategy.

On the other hand, we identify two families of works concerning NL Graph
Querying. 1\. Approaches that address NL translation on SPARQL for knowledge
graph queries, such as (Baevski et al., 2020), concerning machine learning
techniques (Tree-LSTM and neural networks), and methods based on grammar and
logical predicates (Liang et al., 2021; Liu et al., 2018). 2\. Approaches that
translate questions into structured queries using NL processing methods such
as: named entity recognition, binary relationship (pattern) extraction, key
entity identification, and relationship mapping to graph components (Oro and
Ruffolo, 2015).

The literature agrees that little work has addressed the issue of answer
validation, i.e. how can a user confirm that the results match the query’s
intent? With the emergence of data science, two questions arise: How to
express data exploration, cleaning and preparation, sampling and analysis,
visualisation and metrics calculation? How to model and process research
questions formulated by non-technical experts? How to allow their NL
expression and translation into data science queries?

Our work proposes an interactive reverse-engineering method that highlights
essential aspects to be considered when dealing with NL medical queries. It is
the basis for a user-friendly interface adapted for the medical personnel.

##  3\. NLDS-QL

Figure 1. NLDS-QL general architecture

The general process implemented by NLDS-QL is shown in Figure 1. The first two
phases of our translation approach are devoted to analysing the NL query,
which is expressed as a text (see the NL processing and NL parsing phases in
Figure 1). The text can be written or defined as a voice message and
transcribed into text. Therefore, the NL processing phases implement the
classical text processing of syntactic analysis to produce an expression tree
that represents the query (this is done by a parser as shown in Figure 1). The
tree is then processed to produce one or more corresponding Cypher queries in
the query generation phase (see the query generation phase in Figure 1).
Finally, the queries are evaluated on Neo4J (see the query evaluation phase in
Figure 1).

### Overview of NLDS-QL expressions.

The expression of NLDS-QL questions is based on the way data science
operations are applied on graphs in Neo4J. Neo4J defines a general template
including several commands for expressing the execution of a DS query.

DS operations are generally applied on graph views created in memory from
persistent graphs. The views require main memory space to be allocated for
creating them and main memory resources for using algorithms with specific
execution conditions expressed in parameters. Thus, Neo4J provides commands
for performing these estimations and then calling DS operations with given
parameters’ values. Finally, DS operations can yield new graphs that can be
named and persist or not. The creation of new graphs and whether to persist
them is expressed as function call commands.

Consequently, the definition of data science questions in NL include
expressions for specifying the commands specified in the Neo4J template. The
most simple expression for defining a graph view and estimating the memory
required assuming that it is stored in Neo4J and that the graph schema with
the nodes and relations is available, is defined with the following English
expression:

\- Create and estimate memory for the graph view $<$subgraph-name$>$ [named as
$<$ view name $>$] with the node $<$ node name $>$ and the relationship $<$
relationship name $>$ [oriented]

The data science operation task includes estimating the cost in memory of
applying a graph data science algorithm on the graph, using the algorithm on
the graph view. According to specific keywords, NLDS-QL can determine the type
of algorithm that can be applied. Keywords like most important, most popular,
most influential refer to centrality algorithms such as PageRank and Louvain
and classify, communities, group can refer to clustering algorithms like Label
Propagation, as illustrated by the following three questions:

\- $Q_{1}:$ Estimate the required memory for applying $<$ DS algorithm name$>$
on the graph view $<$ view name $>$

\- $Q_{2}:$ Find the most important/most popular $<$ node name $>$ with $<$
relation name $>$ [in the graph  $<$ graph name $>$] with $<$ number of
iterations $>$ maximum of iterations and with a damping factor $<$ floating
number $>$

\- $Q_{3}:$ Classify/Find groups/communities of $<$ node name $>$ within the
view $<$ view name $>$ with relation $<$ relation name $>$ with $<$ number of
iterations $>$ maximum of iterations

##  4\. Demonstration overview

We set up an experiment to validate our approach. Therefore we use the patient
part of the Synthea Generic study. The Synthea’s Generic Graph
333https://xilinx.github.io/graphanalytics/recom-tg3/synthea-overview.html
models various diseases conditions that contribute to the medical history of
synthetic patients 800K vertices and nearly 2000K edges.

Querying graphs is based on navigational queries, which retrieve information
already ”contained” in a graph. In the Synthea graph, it is possible to ask
simple queries like : How many patients are there in the Synthea study? Which
allergies are identified in the Synthea study patients? But it is also
possible to go further and ask analytical type questions that involve
classification tasks such as What are the most frequently prescribed drugs for
patients in the Synthea study? Answering this type of query involves
performing a sequence of tasks ordered in a pipeline, which we call a data
science query.

### Demonstration scenario

The demonstration is based on the Synthea patients graph shown in Figure 2. It
describes the immunisations, allergies, conditions, studies, procedures and
care plans of patients. Each entity and its relations are characterised by
properties that describe them. The patient graph has approximately 100
thousand nodes and 37 thousand relations stored on Neo4J. The demonstration
runs on a local machine to avoid connection problems, and the questions use
the graph vocabulary extracted from its schema.

Figure 2. Synthea patients’ graph

The demonstration of NLDS-QL on the Synthea patients graph is based on a
conversational pipeline where expert and non-expert users can ask questions to
start exploring the graph (see Figure 3). The demonstration environment
initially shows the Synthea patients graph, and users can ask for details
about the description of the graph, like the number of nodes and relations.
Then, the user can ask a question. The system generates one or several
queries, and then the user can either choose one or several queries to be
adjusted or executed and then modified (see right side of Figure 3). For every
choice, the user can evaluate the system’s performance with stars that show
the degree of satisfaction.

Figure 3. Demonstration conversation pipeline

For exploring the Synthea graph, the demonstration scenario proposes a set of
queries that include navigational queries of the type selection, projection,
aggregation.

Selection. Find the Medications for which the DESCRIPTION is Lisinopril 10 MG
Oral Tablet and the REASON of the DESCRIPTION is Hypertension.

        MATCH (n:Allergies) return n.DESCRIPTION

Projection. Which is the birthplace of the PATIENTS in the study?

        MATCH (n:Patients) return n.BIRTHPLACE

Selection and Projection. Find the Encounters DESCRIPTION node where the
DESCRIPTION of the drugs is Amlodipine 5 MG Oral Tablet.

        MATCH (n:Encounters)-[*]->(m:Medications
        {DESCRIPTION:’Amlodipine 5 MG Oral Tablet})
        return n.DESCRIPTION, m.DESCRIPTION

Aggregation. How many patients are caucasian?

        MATCH (n:Patients {RACE:’white})
        return count(n)

For data science queries, the demonstration shows NLDS-QL questions that refer
to centrality type operations. Note that the translation is quite complex as
it involves:

  * •

Specifying a graph view from the patient graph, as Neo4J works with graph
views stored in RAM when data science algorithms are applied.

  * •

Then it is possible to generate two queries that call the page rank algorithm
to process the keyword ”most important” with the possibility to make the view
persistent and consider the constraints related to the parameters of the
Pagerank algorithm.

Centrality.
Find the most popular Encounters for Medications in the graph.

        MATCH (n:Encounters)-[r:ENCOUNTER_FOR_MEDICATION]-()
        with n,count(*) as degree return id(n), degree
        ORDER BY (degree) DESC

Find the most important Drugs prescribed for the PATIENT with a maximum of 25
iterations and a damping factor of 0.60.

    CALL gds.graph.create(’my_graph’,’Medications,
    {PATIENT_HAS_MEDICATION: {orientation: ’NATURAL’}})

    CALL gds.pageRank.write.estimate( ’my_graph’,
            {writeProperty: ’pageRank’,
             maxIterations: 25,
             dampingFactor:0.60})
    YIELD nodeCount, relationshipCount, bytesMin,
          bytesMax, requiredMemory

    CALL gds.pageRank.stream( ’my_graph’ )
    YIELD       nodeId, score
    RETURN      gds.util.asNode(nodeId).name AS name, score
    ORDER BY    score DESC LIMIT 10

In this example, NSDL-QL generates the template that includes first the graph
”my_graph”. Then it computes the estimation of required memory, number of
nodes and relations, minimum and maximum bytes that will yield the resulting
graph when executing PageRank with the specified parameters. Then the call to
the algorithm with the result format with the top 10 nodes associating each
node with its score.
Community detection. The translation also involves several operations as
described in the definition of data science queries.

Get the subgroup of Patients who have PATIENT_HAS_CAREPLAN in the graph with
max iterations 20

    CALL gds.labelPropagation.write.estimate(’my_graph,
            {writeProperty: ’community})
    YIELD   nodeCount, relationshipCount, bytesMin,
            bytesMax, requiredMemory

    CALL gds.labelPropagation.stream(’my_graph’,
              {maxIterations: 20})
    YIELD     nodeId, communityId
    RETURN    communityId, count(nodeId) AS size
    ORDER BY  size DESC LIMIT 5

##  5\. Conclusion and Results

The demonstration of the evaluator NLDS-QL shows how to map NL data science
questions (using an adapted vocabulary) to Neo4J data science query templates.
The demonstration is based on a use case on querying and analysing a graph in
the medical domain. Users with medical and non-medical backgrounds can define
a sequence of natural language queries executed step by step to explore the
graph, as in data science questions. Thereby users can acquire an
understanding of medical prescriptions proposed to patients by classifying
their treatment, their physiological characteristics to better understand how
diseases are diagnosed and treated according to patients conditions. In this
way, we show the essential aspects of a data science query template expressed
in NL.

The approach is flexible and can be enhanced for processing documents with
richer NL vocabulary and more complex templates. The intervention of a human
in handling natural language queries calls for the design of an interactive
strategy based on conversation. We have started to design a more evolved
conversational interface considering human in the loop and user profiling
techniques.

## References

  * (1)
  * Baevski et al. (2020) Alexei Baevski, Henry Zhou, Abdelrahman Mohamed, and Michael Auli. 2020.  wav2vec 2.0: A framework for self-supervised learning of speech representations.  _arXiv preprint arXiv:2006.11477_ (2020).
  * Gkini et al. (2021) Orest Gkini, Theofilos Belmpas, Georgia Koutrika, and Yannis Ioannidis. 2021.  An In-Depth Benchmarking of Text-to-SQL Systems. In _Proceedings of the 2021 International Conference on Management of Data_. 632–644.
  * Koutrika (2021) Georgia Koutrika. 2021\.  The Rise of Intelligent Data Assistants: Democratizing Data Access - Keynote.  _4th International Workshop on Big Data Visual Exploration and Analytics - EDBT/ICDT Workshops_ (2021).
  * Lakhanpal et al. (2015) Shilpa Lakhanpal, Ajay Gupta, and Rajeev Agrawal. 2015\.  Discover trending domains using fusion of supervised machine learning with natural language processing. In _2015 18th International Conference on Information Fusion (Fusion)_. IEEE, 893–900.
  * Li and Jagadish (2014) Fei Li and Hosagrahar V Jagadish. 2014.  NaLIR: an interactive natural language interface for querying relational databases. In _Proceedings of the 2014 ACM SIGMOD international conference on Management of data_. 709–712.
  * Liang et al. (2021) Shiqi Liang, Kurt Stockinger, Tarcisio Mendes de Farias, Maria Anisimova, and Manuel Gil. 2021\.  Querying knowledge graphs in natural language.  _Journal of big Data_ 8, 1 (2021), 1–23.
  * Liu et al. (2018) Zhongxin Liu, Xin Xia, Ahmed E Hassan, David Lo, Zhenchang Xing, and Xinyu Wang. 2018\.  Neural-machine-translation-based commit message generation: how far are we?. In _Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering_. 373–384.
  * Oro and Ruffolo (2015) Ermelinda Oro and Massimo Ruffolo. 2015.  A Natural Language Interface for Querying RDF and Graph Databases.  _Consiglio Nazionale delle Ricerche Istituto di Calcoloe Reti and Alte Prestazioni_ (2015).
  * Saha et al. (2016) Diptikalyan Saha, Avrilia Floratou, Karthik Sankaranarayanan, Umar Farooq Minhas, Ashish R Mittal, and Fatma Özcan. 2016.  ATHENA: an ontology-driven system for natural language querying over relational data stores.  _Proceedings of the VLDB Endowment_ 9, 12 (2016), 1209–1220.
  * Song et al. (2015) Dezhao Song, Frank Schilder, Charese Smiley, Chris Brew, Tom Zielund, Hiroko Bretz, Robert Martin, Chris Dale, John Duprey, Tim Miller, et al. 2015\.  TR Discover: A natural language interface for querying and analyzing interlinked datasets. In _International Semantic Web Conference_. Springer, 21–37.
  * Thomas (2020) Alex Thomas. 2020\.  _Natural Language Processing with Spark NLP: Learning to Understand Text at Scale_.  ” O’Reilly Media, Inc.”.
  * Xu et al. (2017) Xiaojun Xu, Chang Liu, and Dawn Song. 2017.  Sqlnet: Generating structured queries from natural language without reinforcement learning.  _arXiv preprint arXiv:1711.04436_ (2017).