11institutetext: Department of Applied Mathematics, Computer Science and
Statistics, Ghent University, Belgium 22institutetext: Data Mining and
Modeling for Biomedicine, Center for Inflammation Research, VIB-UGent, Belgium

#  GroupEnc: encoder with group loss for global structure preservation

David Novak 1122 0000-0003-4574-9093 Sofie Van Gassen 1122 0000-0002-7119-5330
Yvan Saeys 1122 0000-0002-0415-1506

###### Abstract

Recent advances in dimensionality reduction have achieved more accurate lower-
dimensional embeddings of high-dimensional data. In addition to visualisation
purposes, these embeddings can be used for downstream processing, including
batch effect normalisation, clustering, community detection or trajectory
inference. We use the notion of structure preservation at both local and
global levels to create a deep learning model, based on a variational
autoencoder (VAE) and the stochastic quartet loss from the SQuadMDS algorithm.
Our encoder model, called GroupEnc, uses a ‘group loss’ function to create
embeddings with less global structure distortion than VAEs do, while keeping
the model parametric and the architecture flexible. We validate our approach
using publicly available biological single-cell transcriptomic datasets,
employing $R_{\mathrm{NX}}$ curves for evaluation.

###### Keywords:

Dimensionality reduction Autoencoders Bioinformatics.

##  1 Introduction

Autoencoders (AEs) are neural networks which encode high-dimensional (HD)
input data as a low-dimensional (LD) latent representation and decode this
into a reconstruction of the input. In training, reconstruction error is
minimised via back-propagation.

In the field of bioinformatics, we have seen impressive applications of
autoencoders and variational autoencoders (VAEs; probabilistic models based on
AEs) in dimensionality reduction (DR) for the purposes of visualisation [14,
4] and downstream data processing, including batch effect correction and cell
population clustering [2, 3, 7]. This pertains to large and high-dimensional
single-cell datasets, which quantify biological features per cell in a tissue
sample of interest. Examples of these methods include single-cell RNA
sequencing (scRNA-seq), flow cytometry, mass cytometry (CyTOF) and CITE-seq.

We introduce and evaluate GroupEnc: a stand-alone encoder module that
optimises the group loss: a differentiable loss function that imposes a scale-
agnostic structure-preserving constraint on the learned LD embedding. This is
a modification of the stochastic quartet loss in SQuadMDS [8], applied in a
deep learning context here. This results in a parametric model that can run on
GPU. We achieve similar local structure preservation and better global
structure preservation than a VAE model, as tested on 5 single-cell
transcriptomic datasets. Compared to previously published alternative triplet-
based loss functions proposed for VAEs [14, 1], the group loss does not
require computation of a k-nearest-neighbour graph of the input data.

##  2 Method

We describe the methodology used to create LD embeddings of HD data and to
evaluate them.

###  2.1 Model training

In an autoencoder architecture, HD input $\mathbf{X_{n\times
d}}\in\mathcal{X}$ is encoded as LD representation $\mathbf{Z_{n\times
w}}\in\mathcal{Z}$ (where
$\mathcal{X}=\mathbb{R}^{d},\mathcal{Z}=\mathbb{R}^{w},w<d$) and reconstructed
as an approximation $\mathbf{\hat{X}_{n\times d}}$.

The encoder $E_{\Phi}:\mathcal{X}\rightarrow\mathcal{Z}$ transforms
$\mathbf{X}$ to $\mathbf{L}$, and the decoder
$D_{\theta}:\mathcal{Z}\rightarrow\mathcal{X}$ transforms $\mathbf{L}$ to
$\mathbf{\hat{X}}$. Parameters of the AE (encoder weights $\Phi$ and decoder
weights $\Theta$) are learned so as to reduce a reconstruction loss. In our
baseline VAE model, we use the mean square error (MSE) as reconstruction loss.

In a VAE, the latent representation $\mathbf{L}$ is sampled from a
distribution $\mathcal{D}$ in latent space. The encoder and decoder networks
are probabilistic, and an extra term quantifying the Kullback-Leibler (KL)
divergence between $\mathcal{D}$ and a latent prior (isotropic Gaussian
distribution) is used as an additional loss term during training.

In contrast, our current GroupEnc model only consists of a variational encoder
and sampler (without a decoder), trained to minimise a group loss along with
the KL divergence from prior. The group loss adapts the notion of the quartet
loss function, computed using quartet-normalised distances between original
and embedded points, from SQuadMDS [8]. The normalised distances are used to
calculate a differentiable cost function per each randomly drawn quartet of
points. We denote Euclidean distances between any HD input points or LD
embedded points indexed $i$ and $j$ as $\delta_{ij}$ and $d_{ij}$,
respectively. To compute a group-normalised distance between two points in the
same group (for a quartet, quintet, sextet, etc.), we use all pairwise
distances within that group. For HD and LD points, respectively, we get group-
normalised distance formulas

$\delta^{\mathrm{norm}}_{ij}=\frac{\delta_{ij}}{\sum^{\gamma-1}_{a=1}\sum^{\gamma}_{b=a+1}\delta_{ab}}$
(1)
$d^{\mathrm{norm}}_{ij}=\frac{d_{ij}}{\sum^{\gamma-1}_{a=1}\sum^{\gamma}_{b=a+1}d_{ab}}$
(2)

where $\gamma$ is the number of points in each group.

The difference in group-normalised distances in HD and LD, which ought to be
minimised, is used to calculate the cost function

$g=\sum\limits^{\gamma-1}_{a=1}\sum\limits^{\gamma}_{b=a+1}(\delta^{\mathrm{norm}}_{ab}-d^{\mathrm{norm}}_{ab})^{2}$
(3)

of a group (a group cost). This is visualised in Figure 1.

The GroupEnc model is trained on shuffled batches of input data using the Adam
optimiser. Partitioning of points into groups is done dynamically at the batch
level, and the size of the groups ($\gamma$) is specified as a hyperparameter.
The group loss value per each point i in the training batch is assigned as the
cost value of the group for which i is the first point, and the group loss
term per batch is averaged across the batch.

Therefore, GroupEnc imposes a constraint on the latent distribution
$\mathcal{D}$ instead of reconstruction loss to compute weight updates.

Figure 1: A schematic illustration of GroupEnc training and inference is
shown. In training, a batch of high-dimensional points is used as input to the
encoder. Parameters of the model are adjusted in each pass via back-
propagation to minimise the group loss, which quantifies divergence in
relative distances within randomly assigned groups of points in a batch of
input points versus its embedding. The trained encoder then outputs a low-
dimensional embeddding of the input.

###  2.2 Dimensionality reduction quality assessment

To assess structure preservation (SP) in an embedding, we use the
$R_{\mathrm{NX}}$ curve, a previously proposed quality assessment metric [9].
This curve quantifies the overlap between ordering of neighbours to a
reference point in HD versus in LD for all neighbourhood sizes, from $1$ to
$(N-1)$ (with sample size $N$), averaged across all reference points.

To compute this, we denote neighbourhood ranks of a point $j$ (neighbour) with
respect to a point $i$ (reference point) as $\rho_{ij}$ and $r_{ij}$ in HD and
in LD, respectively. Non-self neighbourhoods of HD and LD points,
respectively, are then denoted as $\nu_{i}^{K}=\\{j:1\leq\rho_{ij}\leq K\\}$
and $n_{i}^{K}=\\{j:1\leq r_{ij}\leq K\\}$ for neighbourhood size $K$. For
dataset size $N$, the $Q_{\mathrm{NX}}$ value for a specific value of $K$ is
calculated as

$Q_{\mathrm{NX}}(K)=\frac{1}{KN}\sum\limits_{i=1}^{N}|\nu_{i}^{K}\cap
n_{i}^{K}|$ (4)

To obtain the full $Q_{\mathrm{NX}}$ curve, we calculate this score for $K$
from 1 to $(N-1)$.

It turns out that a random embedding results in
$Q_{\mathrm{NX}}(K)\approx\frac{K}{N-1}$. $R_{\mathrm{NX}}$, as opposed to
$Q_{\mathrm{NX}}$, corrects for chance, and is computed as

$R_{\mathrm{NX}}(K)=\frac{(N-1)Q_{\mathrm{NX}}(K)-K}{N-1-K}$ (5)

We quantify SP as the area-under-curve (AUC) for an $R_{\mathrm{NX}}$ curve of
an embedding of interest. Specifically, Local SP is the AUC of the curve where
neighbourhood size ($K$) is re-scaled logarithmically ($lnK$ is used), to up-
weight local neighbourhoods while not setting a hard cut-off for local versus
global. Moreover, Global SP is the AUC with a linear scale for $K$, therefore
without the emphasis on local neighbourhoods of the reference points. In both
cases, a higher SP score is better.

##  3 Results

We compare a VAE (trained to minimise reconstruction error and KL-divergence
from prior) and a GroupEnc model (encoder-only, trained to minimise group
loss)111The encoder module, in both cases, consisted of layers sized
$(32,64,128,32)$ and the VAE decoder module of layers consisted of layers
sized $(32,128,64,32)$. The Adam optimiser with a learning rate of $0.001$ was
used for $500$ epochs of training with batch size of $512$..

We tested structure preservation (SP) in embeddings of dimensionality 2, 5 and
10, with different values of hyperparameter $\gamma$ (group size), looking at
Local and Global SP separately.

We use 5 single-cell RNA-sequencing (scRNA-seq) datasets [10, 5, 13, 18, 19],
comprising high-dimensional feature vectors describing the identity of single
biological cells in a tissue sample of interest. These features are levels of
transcription of labelled genes. The datasets are listed in Table 3.

Local SP and Global SP scores are summarised in Figure 2 and shown in Tables 2
and 3 in full. Time required to train each model can be found in Table 4, with
a single node of a GPU cluster (16-core Intel Xeon Gold 6242 processor with
NVIDIA Volta V100 GPU) with 16 GB of usable RAM made available each time. 5
runs (with different random seeds) were run to collect the scores.

Figure 2: Boxplots of Local and Global SP scores across 5 runs for embeddings
of each dataset, obtained from VAE and GroupEnc model for different group size
($\gamma$) values (written as ‘Group($\gamma$)’). Subplots are sorted by
target dimensionalities (columns).

Dataset name |  Biological source |  Feature set |  Number of samples
---|---|---|---
Ziegler | human nasopharynx | 32,871 genes | 32,588 cells
Shekhar | mouse retina | 24,904 genes | 44,994 cells
Ximerakis | mouse brain | 14,699 genes | 37,069 cells
Farrell | zebrafish embryos | 17,239 genes | 38,731 cells
Liu | mouse brain | 17,482 genes | 26,187 cells

Table 1: Datasets used for DR benchmark and their brief descriptions.

Dim |  Model |  Dataset
---|---|---
Liu | Farrell | Shekhar | Ximerakis | Ziegler
$10d$ | VAE | $0.506{\scriptstyle\pm 0.005}$ | $0.556{\scriptstyle\pm 0.011}$ | $0.407{\scriptstyle\pm 0.006}$ | $0.487{\scriptstyle\pm 0.009}$ | $0.551{\scriptstyle\pm 0.006}$
GroupEnc ($\gamma=4$) | $0.453{\scriptstyle\pm 0.006}$ | $0.518{\scriptstyle\pm 0.003}$ | $0.392{\scriptstyle\pm 0.002}$ | $0.440{\scriptstyle\pm 0.002}$ | $0.488{\scriptstyle\pm 0.007}$
GroupEnc ($\gamma=5$) | $0.456{\scriptstyle\pm 0.006}$ | $0.513{\scriptstyle\pm 0.011}$ | $0.392{\scriptstyle\pm 0.002}$ | $0.439{\scriptstyle\pm 0.005}$ | $0.490{\scriptstyle\pm 0.007}$
GroupEnc ($\gamma=6$) | $0.452{\scriptstyle\pm 0.005}$ | $0.518{\scriptstyle\pm 0.004}$ | $0.391{\scriptstyle\pm 0.003}$ | $0.439{\scriptstyle\pm 0.002}$ | $0.489{\scriptstyle\pm 0.010}$
$5d$ | VAE | $0.384{\scriptstyle\pm 0.007}$ | $0.465{\scriptstyle\pm 0.006}$ | $0.354{\scriptstyle\pm 0.004}$ | $0.431{\scriptstyle\pm 0.005}$ | $0.448{\scriptstyle\pm 0.007}$
GroupEnc ($\gamma=4$) | $0.318{\scriptstyle\pm 0.002}$ | $0.442{\scriptstyle\pm 0.007}$ | $0.334{\scriptstyle\pm 0.002}$ | $0.414{\scriptstyle\pm 0.004}$ | $0.443{\scriptstyle\pm 0.003}$
GroupEnc ($\gamma=5$) | $0.321{\scriptstyle\pm 0.005}$ | $0.447{\scriptstyle\pm 0.005}$ | $0.335{\scriptstyle\pm 0.003}$ | $0.411{\scriptstyle\pm 0.002}$ | $0.444{\scriptstyle\pm 0.004}$
GroupEnc ($\gamma=6$) | $0.316{\scriptstyle\pm 0.003}$ | $0.444{\scriptstyle\pm 0.004}$ | $0.334{\scriptstyle\pm 0.002}$ | $0.412{\scriptstyle\pm 0.005}$ | $0.443{\scriptstyle\pm 0.002}$
$2d$ | VAE | $0.262{\scriptstyle\pm 0.015}$ | $0.281{\scriptstyle\pm 0.009}$ | $0.256{\scriptstyle\pm 0.005}$ | $0.304{\scriptstyle\pm 0.009}$ | $0.285{\scriptstyle\pm 0.010}$
GroupEnc ($\gamma=4$) | $0.187{\scriptstyle\pm 0.005}$ | $0.260{\scriptstyle\pm 0.005}$ | $0.223{\scriptstyle\pm 0.003}$ | $0.304{\scriptstyle\pm 0.005}$ | $0.278{\scriptstyle\pm 0.001}$
GroupEnc ($\gamma=5$) | $0.185{\scriptstyle\pm 0.005}$ | $0.262{\scriptstyle\pm 0.005}$ | $0.224{\scriptstyle\pm 0.002}$ | $0.305{\scriptstyle\pm 0.003}$ | $0.278{\scriptstyle\pm 0.001}$
GroupEnc ($\gamma=6$) | $0.183{\scriptstyle\pm 0.006}$ | $0.260{\scriptstyle\pm 0.003}$ | $0.224{\scriptstyle\pm 0.001}$ | $0.304{\scriptstyle\pm 0.010}$ | $0.277{\scriptstyle\pm 0.001}$

Table 2: Local SP for 5 datasets, 3 embedding dimensionalities (‘Dim’) and 4
models (VAE and GroupEnc with group size $\gamma$ of 4, 5 and 6). Mean and
standard deviation are shown.

Dim |  Model |  Dataset
---|---|---
Liu | Farrell | Shekhar | Ximerakis | Ziegler
$10d$ | VAE | $0.510{\scriptstyle\pm 0.016}$ | $0.690{\scriptstyle\pm 0.019}$ | $0.670{\scriptstyle\pm 0.012}$ | $0.632{\scriptstyle\pm 0.015}$ | $0.709{\scriptstyle\pm 0.014}$
GroupEnc ($\gamma=4$) | $0.681{\scriptstyle\pm 0.002}$ | $0.847{\scriptstyle\pm 0.005}$ | $0.793{\scriptstyle\pm 0.005}$ | $0.820{\scriptstyle\pm 0.005}$ | $0.840{\scriptstyle\pm 0.007}$
GroupEnc ($\gamma=5$) | $0.685{\scriptstyle\pm 0.009}$ | $0.844{\scriptstyle\pm 0.005}$ | $0.796{\scriptstyle\pm 0.004}$ | $0.826{\scriptstyle\pm 0.006}$ | $0.841{\scriptstyle\pm 0.006}$
GroupEnc ($\gamma=6$) | $0.686{\scriptstyle\pm 0.005}$ | $0.845{\scriptstyle\pm 0.004}$ | $0.793{\scriptstyle\pm 0.005}$ | $0.828{\scriptstyle\pm 0.004}$ | $0.837{\scriptstyle\pm 0.014}$
$5d$ | VAE | $0.401{\scriptstyle\pm 0.032}$ | $0.633{\scriptstyle\pm 0.012}$ | $0.580{\scriptstyle\pm 0.016}$ | $0.602{\scriptstyle\pm 0.024}$ | $0.657{\scriptstyle\pm 0.020}$
GroupEnc ($\gamma=4$) | $0.577{\scriptstyle\pm 0.005}$ | $0.788{\scriptstyle\pm 0.005}$ | $0.708{\scriptstyle\pm 0.003}$ | $0.739{\scriptstyle\pm 0.005}$ | $0.793{\scriptstyle\pm 0.002}$
GroupEnc ($\gamma=5$) | $0.576{\scriptstyle\pm 0.008}$ | $0.787{\scriptstyle\pm 0.003}$ | $0.710{\scriptstyle\pm 0.003}$ | $0.735{\scriptstyle\pm 0.004}$ | $0.795{\scriptstyle\pm 0.005}$
GroupEnc ($\gamma=6$) | $0.575{\scriptstyle\pm 0.007}$ | $0.788{\scriptstyle\pm 0.004}$ | $0.710{\scriptstyle\pm 0.003}$ | $0.738{\scriptstyle\pm 0.007}$ | $0.793{\scriptstyle\pm 0.005}$
$2d$ | VAE | $0.355{\scriptstyle\pm 0.045}$ | $0.512{\scriptstyle\pm 0.036}$ | $0.465{\scriptstyle\pm 0.029}$ | $0.504{\scriptstyle\pm 0.028}$ | $0.552{\scriptstyle\pm 0.035}$
GroupEnc ($\gamma=4$) | $0.474{\scriptstyle\pm 0.009}$ | $0.703{\scriptstyle\pm 0.007}$ | $0.599{\scriptstyle\pm 0.003}$ | $0.637{\scriptstyle\pm 0.013}$ | $0.687{\scriptstyle\pm 0.002}$
GroupEnc ($\gamma=5$) | $0.469{\scriptstyle\pm 0.012}$ | $0.701{\scriptstyle\pm 0.007}$ | $0.599{\scriptstyle\pm 0.005}$ | $0.614{\scriptstyle\pm 0.016}$ | $0.689{\scriptstyle\pm 0.001}$
GroupEnc ($\gamma=6$) | $0.466{\scriptstyle\pm 0.013}$ | $0.704{\scriptstyle\pm 0.003}$ | $0.598{\scriptstyle\pm 0.003}$ | $0.622{\scriptstyle\pm 0.028}$ | $0.686{\scriptstyle\pm 0.004}$

Table 3: Global SP for 5 datasets, 3 embedding dimensionalities (‘Dim’) and 4 models (VAE and GroupEnc with group size $\gamma$ of 4, 5 and 6). Mean and standard deviation are shown. Dim |  Model |  Dataset
---|---|---
Campbell | Farrell | Shekhar | Ximerakis | Ziegler
$10d$ | VAE | $89.7{\scriptstyle\pm 9.4}$ | $126.2{\scriptstyle\pm 15.9}$ | $138.2{\scriptstyle\pm 15.8}$ | $116.4{\scriptstyle\pm 11.2}$ | $103.9{\scriptstyle\pm 11.3}$
GroupEnc ($\gamma=4$) | $151.6{\scriptstyle\pm 18.2}$ | $221.8{\scriptstyle\pm 19.1}$ | $263.0{\scriptstyle\pm 35.2}$ | $211.6{\scriptstyle\pm 20.3}$ | $187.9{\scriptstyle\pm 24.0}$
GroupEnc ($\gamma=5$) | $150.2{\scriptstyle\pm 15.5}$ | $228.7{\scriptstyle\pm 27.0}$ | $252.1{\scriptstyle\pm 25.6}$ | $222.9{\scriptstyle\pm 23.2}$ | $172.9{\scriptstyle\pm 5.3}$
GroupEnc ($\gamma=6$) | $156.7{\scriptstyle\pm 20.0}$ | $221.9{\scriptstyle\pm 23.8}$ | $252.6{\scriptstyle\pm 28.6}$ | $213.1{\scriptstyle\pm 21.4}$ | $189.5{\scriptstyle\pm 22.1}$
$5d$ | VAE | $78.9{\scriptstyle\pm 3.5}$ | $121.9{\scriptstyle\pm 10.8}$ | $137.8{\scriptstyle\pm 15.4}$ | $120.1{\scriptstyle\pm 12.9}$ | $100.2{\scriptstyle\pm 6.7}$
GroupEnc ($\gamma=4$) | $155.9{\scriptstyle\pm 20.0}$ | $227.2{\scriptstyle\pm 29.2}$ | $258.6{\scriptstyle\pm 34.7}$ | $207.2{\scriptstyle\pm 24.0}$ | $179.9{\scriptstyle\pm 17.4}$
GroupEnc ($\gamma=5$) | $148.5{\scriptstyle\pm 17.1}$ | $226.7{\scriptstyle\pm 28.9}$ | $249.9{\scriptstyle\pm 30.2}$ | $207.8{\scriptstyle\pm 24.4}$ | $177.3{\scriptstyle\pm 18.3}$
GroupEnc ($\gamma=6$) | $150.0{\scriptstyle\pm 21.0}$ | $227.2{\scriptstyle\pm 28.2}$ | $251.3{\scriptstyle\pm 26.4}$ | $218.1{\scriptstyle\pm 27.8}$ | $178.1{\scriptstyle\pm 18.1}$
$2d$ | VAE | $85.4{\scriptstyle\pm 1.6}$ | $123.3{\scriptstyle\pm 10.7}$ | $149.5{\scriptstyle\pm 12.9}$ | $117.1{\scriptstyle\pm 12.2}$ | $100.1{\scriptstyle\pm 11.1}$
GroupEnc ($\gamma=4$) | $151.2{\scriptstyle\pm 2.2}$ | $226.8{\scriptstyle\pm 27.3}$ | $282.0{\scriptstyle\pm 27.1}$ | $209.0{\scriptstyle\pm 21.3}$ | $181.6{\scriptstyle\pm 18.0}$
GroupEnc ($\gamma=5$) | $159.7{\scriptstyle\pm 16.0}$ | $217.3{\scriptstyle\pm 24.0}$ | $255.6{\scriptstyle\pm 23.5}$ | $209.0{\scriptstyle\pm 22.7}$ | $179.1{\scriptstyle\pm 17.3}$
GroupEnc ($\gamma=6$) | $154.4{\scriptstyle\pm 13.7}$ | $218.0{\scriptstyle\pm 24.9}$ | $280.1{\scriptstyle\pm 31.2}$ | $218.0{\scriptstyle\pm 30.0}$ | $180.7{\scriptstyle\pm 16.4}$
Table 4: Model training time in seconds across 5 datasets, 3 embedding
dimensionalities (‘Dim’) and 4 models (VAE and GroupEnc with group size
$\gamma$ of 4, 5 and 6). Mean and standard deviation are shown.

For the Farrell dataset, we also plot the 2-dimensional embeddings from both
models and label individual embedded points using annotation provided by the
authors (Figure 3). The labels are ordered and correspond to developmental
stages of cells in zebrafish embryogenesis. This is to show the developmental
gradient is more apparent in the GroupEnc embedding.

Figure 3: 2-dimensional embeddings of the Farrell dataset obtained using VAE
and GroupEnc ($\gamma=4$) with colour labels according to labelled
developmental stages of embedded cells.

The results show that, intuitively, both local and global structures in terms
of neighbour ranks are preserved worse with decreased dimensionality of the
embedding, and this holds across all tested datasets and models (VAE and
GroupEnc with group sizes of 4, 5 and 6).

Furthermore, the VAE model generally outperforms the GroupEnc models when it
comes to Local SP. However, we see consistently better Global SP for GroupEnc,
concordant with the scale-agnostic nature of the group loss that GroupEnc
optimises. Differences between GroupEnc models with different group sizes are
not significant.

##  4 Discussion

Faithful reconstructions of global relationships in lower-dimensional
embeddings are of interest for purposes of visualisation, as well as the
potential for downstream processing of data. We set out to design a deep
learning model that uses a loss function for scale-agnostic preservation of
randomly sampled structures [8]. We have done this to demonstrate the
improvement in global structure preservation (versus VAE) via this loss
function and that it can be used in a deep learning context, which has the
advantage of providing a parametric model to be trained on a subset of data
and used to transform new samples.

The use of geometric priors (similarity matrices, topological priors) with
VAEs for dimensionality reduction [16, 7] is another promising avenue of
research in analyses of high-dimensional datasets. With data that is high-
dimensional and noisy by its nature (of which biological single-cell data is
an instance), feature engineering by the means of constructing such lower-
dimensional embeddings can help extract more salient information about the
differential expression of genes in cells, continuous developmental gradients
or batch effects between cohorts of samples.

In general, preserving global structures, as opposed to constraining the
optimisation process to local structure preservation (as in t-SNE [15] or UMAP
[11]) can prove beneficial for analysing hierarchical relationships,
developmental gradients and pathways.

Our future work in dimensionality reduction of biological data will focus on
effective reconstruction of trajectories, tackling noise and an extended range
of evaluation metrics, both unsupervised and supervised.

##  5 Code availability

We make a TensorFlow implementation of GroupEnc, including Bash scripts for
generating benchmarking jobs (on Slurm) with custom datasets, available at
github.com/saeyslab/GroupEnc.

###  5.1 Data availability

We downloaded the Shekhar and Liu datasets via the scRNAseq R package [12]
using the functions ShekharRetinaData and LiuBrainData and converted them to
AnnData objects using the scDIOR [6] packages for R/Python interoperability.
Other datasets come from the Single Cell
Portal111https://singlecell.broadinstitute.org/single_cell and are accessible
using the following accession numbers.

  * •

Farrell: SCP162

  * •

Ximerakis: SCP263

  * •

Ziegler: SCP1289

  * •

Liu: SCP2161

###  5.2 Data pre-processing

We used the scanpy package version 1.9.1 [17] for data pre-processing. We
applied the following Python code for scaling, normalisation and principal
component analysis (PCA) prior to running the DR algorithms:

    import scanpy as sc
    hd = sc.pp.normalize_per_cell(X, copy=True) # assume X is count matrix
                                                # (numpy.ndarray)
    hd = sc.pp.log1p(hd, copy=True)
    hd = sc.pp.scale(hd, max_value=10, copy=True)
    data = sc.tl.pca(hd, svd_solver=‘arpack’, n_comps=50, copy=True)

The Farrell dataset was an exception, where already scaled data was used, and
only the PCA step remained.

## References

  * [1] E. Amid and M. K. Warmuth.  TriMap: Large-scale Dimensionality Reduction Using Triplets, Mar. 2022.  arXiv:1910.00204 [cs, stat].
  * [2] M. Amodio, D. van Dijk, K. Srinivasan, W. S. Chen, H. Mohsen, K. R. Moon, A. Campbell, Y. Zhao, X. Wang, M. Venkataswamy, A. Desai, V. Ravi, P. Kumar, R. Montgomery, G. Wolf, and S. Krishnaswamy.  Exploring single-cell data with deep multitasking neural networks.  Nature Methods, 16(11):1139–1145, Nov. 2019.
  * [3] L. Chen, W. Wang, Y. Zhai, and M. Deng.  Deep soft K-means clustering with self-training for single-cell RNA sequence data.  NAR Genomics and Bioinformatics, 2(2):lqaa039, June 2020.
  * [4] J. Ding, A. Condon, and S. P. Shah.  Interpretable dimensionality reduction of single cell transcriptome data with deep generative models.  Nature Communications, 9(1):2002, May 2018.
  * [5] J. A. Farrell, Y. Wang, S. J. Riesenfeld, K. Shekhar, A. Regev, and A. F. Schier.  Single-cell reconstruction of developmental trajectories during zebrafish embryogenesis.  Science, 360(6392):eaar3131, June 2018.
  * [6] H. Feng, L. Lin, and J. Chen.  scDIOR: single cell RNA-seq data IO software.  BMC Bioinformatics, 23(1):16, Dec. 2022.
  * [7] A. Kopf, V. Fortuin, V. R. Somnath, and M. Claassen.  Mixture-of-Experts Variational Autoencoder for clustering and generating from similarity-based representations on single cell data.  PLOS Computational Biology, 17(6):e1009086, June 2021.
  * [8] P. Lambert, C. de Bodt, M. Verleysen, and J. A. Lee.  Stochastic quartet approach for fast multidimensional scaling.  pages 417–422, 2021.
  * [9] J. A. Lee, D. H. Peluffo-Ordóñez, and M. Verleysen.  Multi-scale similarities in stochastic neighbour embedding: Reducing dimensionality while preserving both local and global structure.  Neurocomputing, 169:246–261, Dec. 2015.
  * [10] Y. Liu, E. L. Savier, V. J. DePiero, C. Chen, D. C. Schwalbe, R.-J. Abraham-Fan, H. Chen, J. N. Campbell, and J. Cang.  Mapping visual functions onto molecular cell types in the mouse superior colliculus.  Neuron, 111(12):1876–1886.e5, 2023.
  * [11] L. McInnes, J. Healy, and J. Melville.  UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction, Sept. 2020.  arXiv:1802.03426 [cs, stat].
  * [12] D. Risso and M. Cole.  scRNAseq: Collection of Public Single-Cell RNA-Seq Datasets, 2021.  R package version 2.8.0.
  * [13] K. Shekhar, S. W. Lapan, I. E. Whitney, N. M. Tran, E. Z. Macosko, M. Kowalczyk, X. Adiconis, J. Z. Levin, J. Nemesh, M. Goldman, S. A. McCarroll, C. L. Cepko, A. Regev, and J. R. Sanes.  Comprehensive Classification of Retinal Bipolar Neurons by Single-Cell Transcriptomics.  Cell, 166(5):1308–1323.e30, Aug. 2016.
  * [14] B. Szubert, J. E. Cole, C. Monaco, and I. Drozdov.  Structure-preserving visualisation of high dimensional single-cell datasets.  Scientific Reports, 9(1):8914, June 2019.
  * [15] L. van der Maaten and G. Hinton.  Visualizing Data using t-SNE.  Journal of Machine Learning Research, 9(86):2579–2605, 2008.
  * [16] R. Vandaele, B. Kang, J. Lijffijt, T. De Bie, and Y. Saeys.  Topologically Regularized Data Embeddings, Mar. 2022.  arXiv:2110.09193 [cs, stat].
  * [17] F. A. Wolf, P. Angerer, and F. J. Theis.  SCANPY: large-scale single-cell gene expression data analysis.  Genome Biology, 19(1):15, Dec. 2018.
  * [18] M. Ximerakis, S. L. Lipnick, B. T. Innes, S. K. Simmons, X. Adiconis, D. Dionne, B. A. Mayweather, L. Nguyen, Z. Niziolek, C. Ozek, V. L. Butty, R. Isserlin, S. M. Buchanan, S. S. Levine, A. Regev, G. D. Bader, J. Z. Levin, and L. L. Rubin.  Single-cell transcriptomic profiling of the aging mouse brain.  Nature Neuroscience, 22(10):1696–1708, Oct. 2019.
  * [19] C. G. Ziegler, V. N. Miao, A. H. Owings, A. W. Navia, Y. Tang, J. D. Bromley, P. Lotfy, M. Sloan, H. Laird, H. B. Williams, M. George, R. S. Drake, T. Christian, A. Parker, C. B. Sindel, M. W. Burger, Y. Pride, M. Hasan, G. E. Abraham, M. Senitko, T. O. Robinson, A. K. Shalek, S. C. Glover, B. H. Horwitz, and J. Ordovas-Montanes.  Impaired local intrinsic immunity to SARS-CoV-2 infection in severe COVID-19.  Cell, 184(18):4713–4733.e22, 2021.


# Hyperbolic L-space knots and their formal semigroups

Masakazu Teragaito  Department of Mathematics and Mathematics Education,
Hiroshima University, 1-1-1 Kagamiyama, Higashi-hiroshima, Japan 739-8524.
<EMAIL_ADDRESS>
###### Abstract.

For an L-space knot, the formal semigroup is defined from its Alexander
polynomial. It is not necessarily a semigroup. That is, it may not be closed
under addition. There exists an infinite family of hyperbolic L-space knots
whose formal semigroups are semigroups generated by three elements. In this
paper, we give the first infinite family of hyperbolic L-space knots whose
formal semigroups are semigroups generated by five elements.

###### 2020 Mathematics Subject Classification:

Primary 57K10

The author has been supported by JSPS KAKENHI Grant Number 20K03587.

##  1\. Introduction

A knot in the $3$–sphere is called an L–space knot if it admits a Dehn surgery
yielding an L–space. An L–space $Y$ is a rational homology $3$-sphere with the
simplest Heegaard Floer homology, that is,
$\mathrm{rank}\,\widehat{HF}(Y)=|H_{1}(Y;\mathbb{Z})|$. Typical examples are
the knots admitting lens space surgeries, such as torus knots. There are
several known constraints for L–space knots [25, 26]. Such a knot $K$ is
fibered, and its Alexander polynomial $\Delta_{K}(t)$ has the form of

(1.1) $\Delta_{K}(t)=1-t^{a_{1}}+t^{a_{2}}-\dots+t^{a_{2k}},$

where $0<a_{1}<a_{2}<\dots<a_{2k}$ for some $k$, and $a_{2k}$ equals to twice
of the knot genus. Also, it is known that $a_{1}=1$ by [11]. In general, it
seems that there remained little to be clarified about the distribution of
$a_{i}$. See [32, 33] for lens space surgery case.

Wang [35] introduced the formal semigroup $\mathcal{S}$ for an L–space knot
$K$. It is a set of nonnegative integers defined from the formal power series
expansion

$\frac{\Delta_{K}(t)}{1-t}=\Sigma_{s\in\mathcal{S}}t^{s}\in\mathbb{Z}[[t]].$

The form of (1.1) implies that $0\in\mathcal{S}$. Hence, if a formal semigroup
is a semigroup, then it is a monoid. Nevertheless, we use the term “formal
semigroup” in deference to previous research.

Essentially, [6, 7] discuss the same notion precedently. In [29], it is called
the support of the Turaev torsion. We remark that $\Delta_{K}(t)/(t-1)$ is
usually called the Reidemeister–Milnor torsion or Turaev torsion in
literatures.

For example, a torus knot of type $(2,7)$ has the Alexander polynomial
$1-t+t^{2}-t^{3}+t^{4}-t^{5}+t^{6}$. Hence
$\mathcal{S}=\\{0,2,4\\}\cup\mathbb{Z}_{\geq 6}$. Another typical example is
the $(-2,3,7)$–pretzel knot. Its Alexander polynomial is
$1-t+t^{3}-t^{4}+t^{5}-t^{6}+t^{7}-t^{9}+t^{10}$, so
$\mathcal{S}=\\{0,3,5,7,8\\}\cup\mathbb{Z}_{\geq 10}$. (In this paper, we use
the notation $\mathbb{Z}_{\geq m}$ for the set of integers bigger than or
equal to $m$.)

In general, a formal semigroup is a subset of $\mathbb{Z}_{\geq 0}$, and we
use the addition as the binary operation. As seen from the above example, a
formal semigroup is not necessarily closed under the addition. It is an easy
and known fact that a torus knot of type $(p,q)\ (p,q>0)$ has the formal
semigroup $\langle p,q\rangle\ (=\\{ap+bq\mid a,b\geq 0\\})$, which is a
semigroup (see [7, Example 1.10]). Also, the formal semigroup of an iterated
torus L–space knot is a semigroup [35]. However, this is not the case for the
$(-2,3,7)$–pretzel knot, because $3\in\mathcal{S}$ but $6\not\in\mathcal{S}$.
More generally, it is straightforward to verify that any hyperbolic Montesinos
L–space knot has the formal semigroup which is not a semigroup. Because such a
knot is known to be the $(-2,3,2n+1)$–pretzel knot with $n\geq 3$ by [4], and
its Alexander polynomial given by [12] immediately implies that
$3\in\mathcal{S}$ but $6\not\in\mathcal{S}$. Also, we checked that most of
hyperbolic Berge knots have formal semigroups which are not semigroups. Hence
it is not too much to say that the formal semigroup of a hyperbolic L–space
knot is less likely to become an actual semigroup.

In [35, Question 2.8], Wang asked if there exists an L–space knot which is not
an iterated torus knot and whose formal semigroup is a semigroup. As explained
in [2], the author found two hyperbolic L–space knots K8_201 and K9_449 whose
formal semigroups are actual semigroups. Indeed, they are the only knots among
$630$ hyperbolic L–space knots listed by Dunfield. (This list is found in [1].
There were two unclassified knots in Dunfield’s data, but they are confirmed
to be L–space knots by [3]. The formal semigroups of these two are not
semigroups.) On the other hand, Baker and Kegel [2] show that K9_449 is the
only knot among Dunfield’s list that is not the closure of a positive braid,
and try to generalize it to an infinite family of hyperbolic L–space knots
$\\{K_{n}\\}$, where $K_{1}$ is K9_449. The author also found that their knots
give the first infinite family of hyperbolic L–space knots whose formal
semigroups are semigroups. More precisely, the formal semigroup of $K_{n}$ is
$\langle 4,4n+2,4n+5\rangle$. See [2] for more details.

For a finite set of positive integers $\\{p_{1},p_{2},\dots,p_{k}\\}$,

$\langle
p_{1},p_{2},\dots,p_{k}\rangle=\\{a_{1}p_{1}+a_{2}p_{2}+\dots+a_{k}p_{k}\mid
a_{i}\in\mathbb{Z}_{\geq 0}\\}$

is a semigroup under the addition. Since we include 0 as a coefficient, the
identity element $0$ is excluded from generators. For such a semigroup, the
rank is defined to be the minimal cardinality of a generating set.

Thus, the formal semigroup of the hyperbolic L–space knot $K_{n}$ in [2] is a
semigroup of rank three. On the other hand, the cabling formula of [35]
implies that the semigroup of an iterated torus L–space knot can have
arbitrarily high rank. Then it is natural to ask the following.

######  Question 1.1.

Does there exist a hyperbolic L–space knot whose formal semigroup is a
semigroup with arbitrarily high rank?

The purpose of the present paper is to construct a new family of hyperbolic
L–space knots whose formal semigroups are semigroups of rank $5$.

######  Theorem 1.2.

There exists an infinite family of hyperbolic L–space knots whose formal
semigroups are semigroups of rank $5$.

The formal semigroup of an L–space knot is related to its knot Floer complex
(see [16]). However, the meaning of closedness under addition in the formal
semigroup seems to be missing.

##  2\. The family of hyperbolic L–space knots

For any integer $n\geq 1$, let $\beta_{n}$ be the $6$–braid defined as

$\beta_{n}=(\sigma_{3}\sigma_{2}\sigma_{4}\sigma_{1}\sigma_{3}\sigma_{5}\sigma_{2}\sigma_{4}\sigma_{3})^{2n+1}\sigma_{3}\sigma_{2}\sigma_{1}\sigma_{1}\sigma_{2}\sigma_{3}\sigma_{2}\sigma_{1}\sigma_{2}\sigma_{2},$

where $\sigma_{i}$ is the standard generator in the $6$–strand braid group.
See Fig. 1. Let $K_{n}$ be the knot obtained as the closure of $\beta_{n}$.

Figure 1. The braid $\beta_{n}$. The knot $K_{n}$ is the closure of
$\beta_{n}$.

Since $\beta_{n}$ is positive, $K_{n}$ is fibered ([31]), and its genus
$g(K_{n})$ is $9n+7$ as seen from an Euler characteristic calculation

$(\text{number of strand})-(\text{number of
crossing})=6-(9(2n+1)+10)=1-2g(K_{n}).$

We remark that $\beta_{0}$ can be defined, but $K_{0}$ is the $(2,11)$–cable
of the trefoil. Hence this is excluded from our interest.

Theorem 1.2 is the direct consequence of the next theorem.

######  Theorem 2.1.

For $n\geq 1$, let $K_{n}$ be the knot defined as above. Then we have:

  * (1)

$K_{n}$ is a hyperbolic L–space knot; and

  * (2)

its formal semigroup is a semigroup $\langle
6,6n+4,6n+8,12n+11,12n+15\rangle$.

The proof of Theorem 2.1 is divided in the remaining sections. In Section 3,
we prove that $(18n+22)$–surgery on $K_{n}$ yields an L–space by using the
Montesinos trick. In Section 4, we calculate the Alexander polynomial and the
formal semigroup. Finally, we prove that $K_{n}$ is hyperbolic in Section 5.

##  3\. Montesinos trick and L–space surgery

In this section, we prove that each $K_{n}$ admits a Dehn surgery yielding an
L–space by using the Montesinos trick. The Montesinos trick is the standard
tool introduced by [21]. For a strongly invertible link $L$ in $S^{3}$, the
resulting manifold by Dehn surgery on $L$ is described as the double branched
cover of some link $\ell$. The surgery corresponds to a tangle replacement.
For details, see [24, 36].

For $K_{n}$, Fig. 2 shows a surgery diagram of $K\cup C_{1}\cup C_{2}$, where
performing $-1/n$–surgery on $C_{1}$ and $1/2n$–surgery on $C_{2}$ changes $K$
to $K_{n}$. This diagram can be changed into a strongly invertible position as
illustrated in Fig. 3. We remark that $r$–surgery on $K$ corresponds to
$(18n+r)$–surgery on $K_{n}$.

Figure 2. A surgery diagram $K\cup C_{1}\cup C_{2}$. Performing $-1/n$–surgery
on $C_{1}$ and $1/2n$–surgery on $C_{2}$ changes $K$ to our $K_{n}$. Figure 3.
A strongly invertible position of the link $K\cup C_{1}\cup C_{2}$ with an
axis.

######  Theorem 3.1.

For $n\geq 1$, $(18n+22)$–surgery on $K_{n}$ yields an L–space.

###### Proof.

For the link in Fig. 3, take a quotient by the involution around the axis.
Note that the surgery coefficient on $K$ is $22$. In the diagram of Fig. 3,
the blackboard framing (or writhe) of $K$ is $19$. Hence, $22$–surgery on $K$
corresponds to the tangle replacement by the $3$–tangle.

Rational tangle replacements corresponding to the surgeries on $K,C_{1},C_{2}$
yield a link $\ell$, whose double branched cover is the result of
$(18n+22)$–surgery on $K_{n}$. Figures 4, 5, 6 and 7 show the deformation of
$\ell$.

Figure 4. A deformation of $\ell$, where a rectangle box means horizontal
half-twists. The integer indicates the number of half-twists, which is right-
handed if it is positive, or left-handed otherwise.  Figure 5. Continued from
Figure 4. Figure 6. Continued from Figure 5. Figure 7. Continued from Figure
6.

In the next lemma, we prove that the double branched cover of the link $\ell$
is an L–space, so the proof is complete. ∎

######  Lemma 3.2.

The double branched cover of the link $\ell$ is an L–space.

###### Proof.

First, $\det\ell=18n+22$. This is easily calculated from the Goeritz matrix
for the checkerboard coloring of the diagram of $\ell$ in Fig. 7. Let $c$ be
the crossing as indicated in Fig. 7. Then we have $\ell_{0}$ and
$\ell_{\infty}$ by smoothing $c$ as shown in Fig. 8, and it is also a direct
calculation to see $\det\ell_{0}=4n+5$ and $\det\ell_{\infty}=14n+17$ from
Figs. 9 and 10. Hence $\det\ell=\det\ell_{0}+\det\ell_{\infty}$ holds.

By [27, Proposition 2.1], the triple of thee double branched covers of $\ell$,
$\ell_{0}$ and $\ell_{\infty}$ forms a triad. Thus [26, Proposition 2.1]
claims that if the double branched covers of $\ell_{0}$ and $\ell_{\infty}$
are L–spaces, then so is the double branched cover of $\ell$.

Figure 8. Two resolutions. Figure 9. The resolution $\ell_{0}$ is a Montesinos
knot. Figure 10. The resolution $\ell_{\infty}$ and its further resolutions
$\ell_{\infty 0}$ and $\ell_{\infty\infty}$ at the crossing $d$.

We can see that $\ell_{0}$ is the Montesinos knot
$M(-\frac{n+1}{2n+1},\frac{1}{2},\frac{2}{4n-1})$ as shown in Fig. 9. When
$n=1$, $\ell_{0}$ is the knot 8_20, which is non-alternating, but quasi-
alternating. Then the double branched cover is an L–space by [27]. If $n>1$,
then $\ell_{0}$ is not quasi-alternating by [14]. Nevertheless, we can show
the following.

######  Claim 3.3.

The double branched cover of $\ell_{0}$ is an L–space.

###### Proof of Claim 3.3.

The double branched cover of $\ell_{0}$ is the Seifert fibered space
$M(0;-\frac{n+1}{2n+1},\frac{1}{2},\frac{2}{4n-1})=M(-1;\frac{n}{2n+1},\frac{1}{2},\frac{2}{4n-1})$.
(We use the convention of [20], which is the same as [2].)

Theorem 1.1 of [20] combined with [19] claims that such a Seifert fibered
space $M(-1;r_{1},r_{2},r_{3})\ (1\geq r_{1}\geq r_{2}\geq r_{3}>0)$ is an
L–space if and only if there are no relatively prime integers $m>a>0$ such
that $mr_{1}<a<m(1-r_{2})$ and $mr_{3}<1$.

First, assume $n=1$. Then $r_{1}=2/3$, $r_{2}=1/2$ and $r_{3}=1/3$, so
$1-r_{2}=1/2$. Since $r_{1}>1-r_{2}$, we have no solution $m$ satisfying
$mr_{1}<m(1-r_{2})$.

Suppose $n\geq 2$. Then $r_{1}=1/2$, $r_{2}=n/(2n+1)$ and $r_{3}=2/(4n-1)$, so
$1-r_{2}=(n+1)/(2n+1)$.

We assume that there are coprime integers $m$ and $a$ such that
$m/2<a<m(n+1)/(2n+1)$ and $2m/(4n-1)<1$. Then the first gives

$0<2a-m<\frac{m}{2n+1},$

and the second gives $m<2n-1/2$. Combining these yields

$0<2a-m<\frac{4n-1}{4n+2}<1.$

Since $a$ and $m$ are integers, this is a contradiction. ∎

For the other resolution $\ell_{\infty}$, we further perform two smoothings at
the crossing $d$ as shown in Fig. 10. Then we have a link $\ell_{\infty 0}$
and a knot $\ell_{\infty\infty}$ as shown there. In particular, a direct
calculation on Fig. 10 (or, Figs. 11 and 12) shows that $\det\ell_{\infty
0}=4n+14$ and $\det\ell_{\infty\infty}=10n+3$. Hence
$\det\ell_{\infty}=\det\ell_{\infty 0}+\det\ell_{\infty\infty}$ holds.

Figure 11. The resolution $\ell_{\infty 0}$ is a Montesinos link.

######  Claim 3.4.

The double branched covers of $\ell_{\infty 0}$ and $\ell_{\infty\infty}$ are
L–spaces.

###### Proof of Claim 3.4.

The link $\ell_{\infty 0}$ is the Montesinos link
$M(\frac{1}{2n+1},-\frac{1}{2},\frac{2n+3}{4n+8})$ as shown in Fig. 11.
Although this is not quasi-alternating by [14], we can show that the double
branched cover is an L–space as before. The double branched cover is the
Seifert fibered space
$M(0;\frac{1}{2n+1},-\frac{1}{2},\frac{2n+3}{4n+8})=M(-1;\frac{1}{2n+1},\frac{1}{2},\frac{2n+3}{4n+8})$.
As in the proof of Claim 3.3, set $r_{1}=1/2$, $r_{2}=(2n+3)/(4n+8)$ and
$r_{3}=1/(2n+1)$.

Suppose that there are coprime integers $m$ and $a$ such that
$mr_{1}<a<m(1-r_{2})$ and $mr_{3}<1$. Then

$0<2a-m<\frac{m}{2n+4}<\frac{2n+1}{2n+4}<1,$

a contradiction.

The link $\ell_{\infty\infty}$ is the Montesinos knot
$M(-\frac{1}{2},\frac{n}{2n+1},\frac{5}{10n+7})$ as shown in Fig. 12, which is
not quasi-alternating by [14] again. The double branched cover is the Seifert
fibered space
$M(0;-\frac{1}{2},\frac{n}{2n+1},\frac{5}{10n+7})=M(-1;\frac{1}{2},\frac{n}{2n+1},\frac{5}{10n+7})$.

Figure 12. The resolution $\ell_{\infty\infty}$ is a Montesinos knot.

Set $r_{1}=1/2$, $r_{2}=n/(2n+1)$ and $r_{3}=5/(10n+7)$. Suppose that there
are coprime integers $m$ and $a$ as above. Then

$0<2a-m<\frac{m}{2n+1}<\frac{10n+7}{10n+5}.$

Hence $2a-m=1$.

Then $a<m(1-r_{2})$ implies $2n+1<m$. Combining with $mr_{3}<1$ gives

$10n+5<5m<10n+7,$

which is impossible. ∎

By [26, Proposition 2.1] and [27, Proposition 2.1], the double branched cover
of $\ell_{\infty}$ is an L–space, so is that of $\ell$. ∎

We remark that computer experiments suggest that the knot $K_{n}$ does not
admit a nontrivial exceptional surgery. This situation brings us a difficulty
to find candidates of slopes for L–space surgeries. Also, since $K_{n}$ has
genus $9n+7$, if $r$–surgery on $K_{n}$ yields an L–space, then $r\geq
2(9n+7)-1=18n+13$ by [28]. In fact, it is known that any $r\ (\geq 18n+13)$
yields an L–space. We selected the slope $18n+22$ for our proof, but there
might be a better slope for a proof.

##  4\. Alexander polynomials and formal semigroups

In this section, we calculate the Alexander polynomial $\Delta_{K_{n}}(t)$ of
$K_{n}$, and its formal semigroup. For the former, we mimic the argument in
[2, 5].

######  Theorem 4.1.

The Alexander polynomial of $K_{n}$ is given as

$\Delta_{K_{n}}(t)=t^{6n+4}+\sum_{i=0}^{n}(A_{1}+A_{2}+A_{3}+A_{4}+A_{5}),$

where

$\displaystyle A_{1}$ $\displaystyle=t^{6(n-i)}-t^{6(n-i)+1},$ $\displaystyle
A_{2}$ $\displaystyle=t^{6(n+i)+6}-t^{6(n+i)+5},$ $\displaystyle A_{3}$
$\displaystyle=t^{6(n+i)+8}-t^{6(n+i)+7},$ $\displaystyle A_{4}$
$\displaystyle=t^{6(n+i)+10}-t^{6(n+i)+9},$ $\displaystyle A_{5}$
$\displaystyle=t^{6(2n+i)+14}-t^{6(2n+i)+13}.$

###### Proof.

Let $L=K\cup C_{1}\cup C_{2}$ be the oriented link as shown in Fig. 13. We
remark that this is modified from the link in Fig. 2 to reduce the number of
crossing by changing the surgery coefficients. (This process is not critical,
because we only need to calculate the multivariable Alexander polynomial.)

Figure 13. A modified surgery diagram of $L=K\cup C_{1}\cup C_{2}$. This is
simpler than the previous link in Figure 2.

It has the multivariable Alexander polynomial

$\begin{split}\Delta_{L}(x,y,z)&=(x^{3}-1)(x^{5}y^{4}z^{2}+x^{3}y^{5}z^{2}-x^{3}y^{4}z^{2}+x^{2}y^{4}z^{2}+x^{4}y^{2}z+x^{3}y^{3}z\\\
&\quad-x^{3}y^{2}z-x^{2}y^{3}z+x^{2}y^{2}z+xy^{3}z+x^{3}y-x^{2}y+x^{2}+y).\end{split}$

(We used [15] for the calculation.)

Performing $-1/(n+1)$–surgery on $C_{1}$ and $1/(2n+2)$–surgery on $C_{2}$
changes the link $K\cup C_{1}\cup C_{2}$ to $K_{n}\cup C_{1}^{n}\cup
C_{2}^{n}$. Clearly, these links have homeomorphic exteriors. Hence the
induced isomorphism of the homeomorphism on their homology groups relates the
Alexander polynomials of two links. (See [9, 23].) Let $\mu_{K}$,
$\mu_{C_{1}}$ and $\mu_{C_{2}}$ be the homology classes of meridians of $K$,
$C_{1}$ and $C_{2}$, respectively. We assume that each (oriented) meridian has
linking number one with the corresponding knot. Moreover, let $\lambda_{K}$,
$\lambda_{C_{1}}$ and $\lambda_{C_{2}}$ be the homology classes of their
oriented longitudes.

Similarly, we have homology classes of meridians, $\mu_{K_{n}}$,
$\mu_{C_{1}^{n}}$ and $\mu_{C_{2}^{n}}$ of $K_{n}$, $C_{1}^{n}$ and
$C_{2}^{n}$. Then we have

$\mu_{K_{n}}=\mu_{K},\quad\mu_{C_{1}^{n}}=\mu_{C_{1}}-(n+1)\lambda_{C_{1}},\quad\mu_{C_{2}^{n}}=\mu_{C_{2}}+(2n+2)\lambda_{C_{2}}.$

Since $\lambda_{C_{1}}=6\mu_{K}$ and $\lambda_{C_{2}}=3\mu_{K}$,

$\mu_{C_{1}^{n}}=\mu_{C_{1}}-6(n+1)\mu_{K},\quad\mu_{C_{2}^{n}}=\mu_{C_{2}}+6(n+1)\mu_{K}.$

Thus

$\mu_{K_{n}}=\mu_{K},\quad\mu_{C_{1}}=\mu_{C_{1}^{n}}+6(n+1)\mu_{K},\quad\mu_{C_{2}}=\mu_{C_{2}^{n}}-6(n+1)\mu_{K}.$

Hence we have the relation between the Alexander polynomials as

(4.1) $\Delta_{K_{n}\cup C_{1}^{n}\cup
C_{2}^{n}}(x,y,z)=\Delta_{L}(x,yx^{6(n+1)},zx^{-6(n+1)}).$

On the other hand, since
$\mathrm{lk}(K_{n},C_{2}^{n})=\mathrm{lk}(K,C_{2})=3$, the Torres condition
[34] gives

$\displaystyle\Delta_{K_{n}\cup C_{1}^{n}\cup C_{2}^{n}}(x,y,1)$
$\displaystyle=(x^{3}y^{0}-1)\Delta_{K_{n}\cup C_{1}^{n}}(x,y)$
$\displaystyle=(x^{3}-1)\Delta_{K_{n}\cup C_{1}^{n}}(x,y).$

Similarly, since $\mathrm{lk}(K_{n},C_{1}^{n})=\mathrm{lk}(K,C_{1})=6$,

$\Delta_{K_{n}\cup C_{1}^{n}}(x,1)=\frac{x^{6}-1}{x-1}\Delta_{K_{n}}(x).$

Thus,

$\Delta_{K_{n}}(x)=\frac{x-1}{x^{6}-1}\Delta_{K_{n}\cup
C_{1}^{n}}(x,1)=\frac{x-1}{(x^{6}-1)(x^{3}-1)}\Delta_{K_{n}\cup C_{1}^{n}\cup
C_{2}^{n}}(x,1,1).$

Then (4.1) gives

$\displaystyle\Delta_{K_{n}}(t)$
$\displaystyle=\frac{t-1}{(t^{6}-1)(t^{3}-1)}\Delta_{L}(t,t^{6(n+1)},t^{-6(n+1)})$
$\displaystyle=\frac{t^{2}(t-1)}{t^{6}-1}(t^{18n+19}+t^{12n+15}+t^{12n+11}+t^{6n+8}+t^{6n+4}+1)$
$\displaystyle\stackrel{{\scriptstyle.}}{{=}}\frac{t^{18n+19}+t^{12n+15}+t^{12n+11}+t^{6n+8}+t^{6n+4}+1}{t^{5}+t^{4}+t^{3}+t^{2}+t+1}.$

(Recall that $\stackrel{{\scriptstyle.}}{{=}}$ means equivalence up to units.)

Next, we calculate

(4.2)
$(t^{5}+t^{4}+t^{3}+t^{2}+t+1)\bigl{(}t^{6n+4}+\sum_{i=0}^{n}(A_{1}+A_{2}+A_{3}+A_{4}+A_{5})\bigr{)}.$

First,

$(t^{5}+t^{4}+t^{3}+t^{2}+t+1)t^{6n+4}=t^{6n+9}+t^{6n+8}+t^{6n+7}+t^{6n+6}+t^{6n+5}+t^{6n+4}.$

Next,

$\displaystyle(t^{5}+t^{4}+t^{3}+t^{2}+t+1)\sum_{i=0}^{n}A_{1}$
$\displaystyle=(t^{5}+t^{4}+t^{3}+t^{2}+t+1)\sum_{i=0}^{n}(t^{6(n-i)}-t^{6(n-i)+1})$
$\displaystyle=(t^{5}+t^{4}+t^{3}+t^{2}+t+1)\sum_{i=0}^{n}t^{6(n-i)}(1-t)$
$\displaystyle=(1-t^{6})\sum_{i=0}^{n}t^{6(n-i)}$
$\displaystyle=\sum_{i=0}^{n}t^{6(n-i)}-\sum_{i=0}^{n}t^{6(n-i)+6}$
$\displaystyle=1-t^{6n+6}.$

Similarly,

$\displaystyle(t^{5}+t^{4}+t^{3}+t^{2}+t+1)\sum_{i=0}^{n}A_{2}$
$\displaystyle=(t^{5}+t^{4}+t^{3}+t^{2}+t+1)\sum_{i=0}^{n}(t^{6(n+i)+6}-t^{6(n+i)+5})$
$\displaystyle=(t^{6}-1)\sum_{i=0}^{n}t^{6(n+i)+5}$
$\displaystyle=\sum_{i=0}^{n}t^{6(n+i)+11}-\sum_{i=0}^{n}t^{6(n+i)+5}$
$\displaystyle=t^{12n+11}-t^{6n+5},$
$\displaystyle(t^{5}+t^{4}+t^{3}+t^{2}+t+1)\sum_{i=0}^{n}A_{3}$
$\displaystyle=(t^{5}+t^{4}+t^{3}+t^{2}+t+1)\sum_{i=0}^{n}(t^{6(n+i)+8}-t^{6(n+i)+7})$
$\displaystyle=(t^{6}-1)\sum_{i=0}^{n}t^{6(n+i)+7}$
$\displaystyle=\sum_{i=0}^{n}t^{6(n+i)+13}-\sum_{i=0}^{n}t^{6(n+i)+7}$
$\displaystyle=t^{12n+13}-t^{6n+7},$
$\displaystyle(t^{5}+t^{4}+t^{3}+t^{2}+t+1)\sum_{i=0}^{n}A_{4}$
$\displaystyle=(t^{5}+t^{4}+t^{3}+t^{2}+t+1)\sum_{i=0}^{n}(t^{6(n+i)+10}-t^{6(n+i)+9})$
$\displaystyle=(t^{6}-1)\sum_{i=0}^{n}t^{6(n+i)+9}$
$\displaystyle=\sum_{i=0}^{n}t^{6(n+i)+15}-\sum_{i=0}^{n}t^{6(n+i)+9}$
$\displaystyle=t^{12n+15}-t^{6n+9},$
$\displaystyle(t^{5}+t^{4}+t^{3}+t^{2}+t+1)\sum_{i=0}^{n}A_{5}$
$\displaystyle=(t^{5}+t^{4}+t^{3}+t^{2}+t+1)\sum_{i=0}^{n}(t^{6(2n+i)+14}-t^{6(2n+i)+13})$
$\displaystyle=(t^{6}-1)\sum_{i=0}^{n}t^{6(2n+i)+13}$
$\displaystyle=\sum_{i=0}^{n}t^{6(2n+i)+19}-\sum_{i=0}^{n}t^{6(2n+i)+13}$
$\displaystyle=t^{18n+19}-t^{12n+13}.$

These show that (4.2) is equal to
$t^{18n+19}+t^{12n+15}+t^{12n+11}+t^{6n+8}+t^{6n+4}+1$. Hence

$\Delta_{K_{n}}(t)=t^{6n+4}+\sum_{i=0}^{n}(A_{1}+A_{2}+A_{3}+A_{4}+A_{5}).$

∎

######  Lemma 4.2.

For $n\geq 1$, let $\mathcal{T}=\langle 6,6n+4,6n+8,12n+11,12n+15\rangle$. The
the semigroup $\mathcal{T}$ has rank $5$.

###### Proof.

Let $G$ be a generating set of $\mathcal{T}$. It suffices to show that
$\\{6,6n+4,6n+8,12n+11,12n+15\\}\subset G$.

Since $6$ is the minimal nonzero element of $\mathcal{T}$, we need $6\in G$.
Except the multiples of $6$, $6n+4$ is the minimal element of $\mathcal{T}$
and $6n+8$ is the next, so $6n+4,6n+8\in G$.

Assume $12n+11=6a+(6n+4)b+(6n+8)c$ for $a,b,c\geq 0$. Then $1\equiv
0\pmod{2}$, so $12n+11\not\in\langle 6,6n+4,6n+8\rangle$. Hence $12n+11\in G$.

Finally, assume $12n+15=6a+(6n+4)b+(6n+8)c+(12n+11)d$ for $a,b,c,d\geq 0$.
Then $1\equiv d\pmod{2}$, so $d\neq 0$. In fact, $d=1$. We have
$4=6a+(6n+4)b+(6n+8)c$. Since $n\geq 1$, this is impossible. Hence $12n+15\in
G$. ∎

######  Theorem 4.3.

The formal semigroup $\mathcal{S}$ of $K_{n}$ is a semigroup of rank $5$:

$\mathcal{S}=\langle 6,6n+4,6n+8,12n+11,12n+15\rangle.$

###### Proof.

By Theorem 4.1,

$\Delta_{K_{n}}(t)=t^{6n+4}+\sum_{i=0}^{n}(A_{1}+A_{2}+A_{3}+A_{4}+A_{5}).$

Hence, as a formal power series,

$\displaystyle\frac{\Delta_{K_{n}}(t)}{1-t}$
$\displaystyle=\frac{t^{6n+4}}{1-t}+\sum_{i=0}^{n}\Bigl{(}\frac{A_{1}}{1-t}+\frac{A_{2}}{1-t}+\frac{A_{3}}{1-t}+\frac{A_{4}}{1-t}+\frac{A_{5}}{1-t}\Bigr{)}$
$\displaystyle=t^{6n+4}\sum_{j=0}^{\infty}t^{j}+\sum_{i=0}^{n}(t^{6(n-i)}-t^{6(n+i)+5}-t^{6(n+i)+7}-t^{6(n+i)+9}-t^{6(2n+i)+13})$
$\displaystyle=\sum_{j=0}^{\infty}t^{6n+4+j}+\sum_{i=0}^{n}t^{6(n-i)}-t^{6n+5}\sum_{i=0}^{n}(t^{6i}+t^{6i+2}+t^{6i+4})-\sum_{i=0}^{n}t^{12n+13+6i}.$

Then

$\mathcal{S}=\mathbb{Z}_{\geq 6n+4}\cup B-C-D,$

where $B=\\{0,6,12,\dots,6n\\}$,
$C=\\{6n+5,6n+7,6n+9,\dots,12n+5,12n+7,12n+9\\}$ and
$D=\\{12n+13,12n+19,\dots,18n+13\\}$.

Let $\mathcal{T}=\langle 6,6n+4,6n+8,12n+11,12n+15\rangle$. We need to show
that $\mathcal{S}=\mathcal{T}$.

First, if $m\geq 18n+14$, then $m\in\mathcal{S}$. Thus $\mathbb{Z}_{\geq
18n+14}\subset\mathcal{S}$. To show that $\mathbb{Z}_{\geq
18n+14}\subset\mathcal{T}$, it suffices to verify that
$18n+14,18n+15,\dots,18n+19\in\mathcal{T}$, since $6\in\mathcal{T}$. This
follows from

$18n+14\equiv 6n+8,18n+15\equiv 12n+15,18n+16\equiv 6n+4,$ $18n+17\equiv
12n+11,18n+18\equiv 6\pmod{6},$ $18n+19=(6n+8)+(12n+11).$

Next, the set $\mathbb{Z}_{<18n+14}$ of nonnegative integers less than
$18n+14$ is decomposed into the congruence classes of modulo 6,
$Z_{0},Z_{1},Z_{2},\dots,Z_{5}$, where $Z_{i}=\\{m\mid 0\leq m<18n+14,m\equiv
i\pmod{6}\\}$. Then $B\subset Z_{0}$, $D\subset Z_{1}$, and $C\subset
Z_{1}\cup Z_{3}\cup Z_{5}$.

We examine each congruence class.

  * •

$Z_{0}\subset\mathcal{S}$ and $Z_{0}\subset\mathcal{T}$. Thus
$Z_{0}\cap\mathcal{S}=Z_{0}\cap\mathcal{T}=Z_{0}$.

  * •

$Z_{1}\cap\mathcal{S}=\varnothing$.

  * •

$Z_{2}\cap\mathcal{S}=\\{6n+8,6n+14,\dots,18n+8\\}\subset\mathcal{T}$.

  * •

$Z_{3}\cap\mathcal{S}=\\{12n+15,12n+21,\dots,18n+9\\}\subset\mathcal{T}$.

  * •

$Z_{4}\cap\mathcal{S}=\\{6n+4,6n+10,\dots,18n+10\\}\subset\mathcal{T}$.

  * •

$Z_{5}\cap\mathcal{S}=\\{12n+11,12n+17,\dots,18n+11\\}\subset\mathcal{T}$.

Hence $\mathcal{S}\cap\mathbb{Z}_{<18n+14}\subset\mathcal{T}$.

Conversely, let $m\in Z_{1}$. If $m\in\mathcal{T}$, then we need to use
$12n+11$ or $12n+15$ to yield $m$. Since $m\leq 18n+13$, either

  * (1)

$m=(12n+11)+r$ and $r\leq 6n+2$, $r\equiv 2\pmod{6}$, or

  * (2)

$m=(12n+15)+r$ and $r\leq 6n-2$, $r\equiv 4\pmod{6}$.

However, there is no $r\in\mathcal{T}$ satisfying these. Hence
$Z_{1}\cap\mathcal{T}=\varnothing$.

Let $m\in Z_{2}\cap\mathcal{T}$. If $m<6n+8$, then $m\leq 6n+2$. So, there is
no such element in $\mathcal{T}$. Hence
$Z_{2}\cap\mathcal{S}=Z_{2}\cap\mathcal{T}$.

Similarly, let $m\in Z_{4}\cap\mathcal{T}$. If $m<6n+4$, then $m\leq 6n-2$.
But there is no such element in $\mathcal{T}$. Hence
$Z_{4}\cap\mathcal{S}=Z_{4}\cap\mathcal{T}$.

Let $m\in Z_{3}\cap\mathcal{T}$. Again, we need to use $12n+11$ or $12n+15$ to
yield $m$. Then, we have either

  * (3)

$m=(12n+11)+r$ and $r\leq 6n-2$ and $r\equiv 4\pmod{6}$, or

  * (4)

$m=(12n+15)+r$ and $r\leq 6n-6$ and $r\equiv 0\pmod{6}$.

For (3), there is no $r\in\mathcal{T}$. For (4),
$r\in\\{0,6,12,\dots,6n-6\\}$, so $m\in Z_{3}\cap\mathcal{S}$. Hence
$Z_{3}\cap\mathcal{S}=Z_{3}\cap\mathcal{T}$.

Finally, let $m\in Z_{5}\cap\mathcal{T}$. Again, we have either

  * (5)

$m=(12n+11)+r$ and $r\leq 6n$ and $r\equiv 0\pmod{6}$, or

  * (6)

$m=(12n+15)+r$ and $r\leq 6n-4$ and $r\equiv 2\pmod{6}$.

For (6), there is no $r\in\mathcal{T}$. For (5), $r\in\\{0,6,12,\dots,6n\\}$,
so $m\in Z_{5}\cap\mathcal{S}$. Hence
$Z_{5}\cap\mathcal{S}=Z_{5}\cap\mathcal{T}$. ∎

##  5\. Hyperbolicity

In this section, we prove that our knot $K_{n}$ is a hyperbolic knot for any
$n\geq 1$ by using the fact that $K_{n}$ has tunnel number one.

######  Lemma 5.1.

For $n\geq 1$, $K_{n}$ has tunnel number one, hence $K_{n}$ is prime.

###### Proof.

Figure 14 shows an unknotting tunnel $\gamma$ for $K_{n}$. The series of
isotopy as illustrated in Fig. 14 indicates that the outside of a regular
neighborhood of $K_{n}\cup\gamma$ is a genus two handlebody. ∎

Figure 14. The unknotting tunnel $\gamma$ and the series of isotopy of
$N(K_{n}\cup\gamma)$.

######  Theorem 5.2.

For $n\geq 1$, $K_{n}$ is a hyperbolic knot.

###### Proof.

By Theorem 4.3, the formal semigroup of $K_{n}$ is a semigroup of rank $5$.
Since the formal semigroup of a torus knot is a semigroup of rank two (see
[7]), $K_{n}$ is not a torus knot.

Assume that $K_{n}$ is a satellite knot for a contradiction. By Lemma 5.1,
$K_{n}$ has tunnel number one. Then Morimoto and Sakuma’s classification [22]
tells us that $K_{n}$ has a torus knot $T(p,q)$ as its companion. Since
$K_{n}$ has bridge number at most $6$, the companion has bridge number at most
three [30]. More precisely, either the companion is $3$–bridge and the
wrapping number of the pattern is two, or the companion is $2$–bridge and the
wrapping number is two or three.

By Theorem 3.1, $K_{n}$ is an L–space knot. Then [10] implies that the pattern
knot is also an L–space knot. Furthermore, [5, Theorem 1.17] claims that the
pattern is braided in the pattern solid torus. In particular, the wrapping
number coincides with the winding number there.

We divide the argument into two cases.

Case 1. Suppose that $K_{n}$ has a companion $T(3,q)\ (|q|>3)$ and a braided
pattern knot $P$. Then the wrapping number and winding number of $P$ are equal
to two. This means that $K_{n}$ is a $2$–cable of $T(3,q)$. However, the
cabling formula of [35] shows that its formal semigroup has rank three. Hence
this case is impossible.

Case 2. Suppose that $K_{n}$ has a companion $T=T(2,q)\ (|q|\geq 3)$ and a
braided pattern knot $P$. We may assume that $q>0$ by taking the mirror image
of $K_{n}$, if necessary. If the wrapping number is two, then $K_{n}$ is a
$2$–cable, which is a contradiction again. Hence the wrapping number and the
winding winding number are equal to three. For the Alexander polynomials, we
have

$\Delta_{K_{n}}(t)=\Delta_{T}(t^{3})\Delta_{P}(t)$

(see [8]). Here, $\Delta_{T}(t^{3})=1-t^{3}+t^{6}-\dots+t^{3(q-1)}$. Also,
this implies $g(K_{n})=3g(T)+g(P)$ (see [13, Lemma 2.6]).

By [17, Theorem 3.1], the only closed $3$–braids which are L–space knots are
torus knots and twisted torus knots $T(3,t;2,s)$ with $ts>0$. Here,
$T(3,t;2,s)$ is obtained from $T(3,t)$ by adding $s$ full twists on two
adjacent strings. Again, a $3$–cable is excluded.

We need to recall the construction of [22] of tunnel number one satellite
knots. Let $k_{1}\cup k_{2}$ be a $2$–bridge link in $S^{3}$. We remark that
each component $k_{i}$ is unknotted. The exterior of $k_{2}$ is a solid torus
$J$ containing $k_{1}$ in its interior. Here, the longitude of $J$ is the
meridian of $k_{2}$. For the companion $T$, consider the homeomorphism $f$
from $J$ to the regular neighborhood $N(T)$ of $T$, which sends the longitude
of $J$ to the $(1,2q)$–curve on $\partial N(T)$. This $(1,2q)$–curve
corresponds to a regular fiber of the Seifert fibration in the exterior of
$T$. Then the image $f(k_{1})$ gives our $K_{n}$.

Since the pattern knot $P$ is defined so as to preserve the preferred
longitudes of $J$ and $N(T)$, $P$ is obtained from $k_{1}$ in $J$ by adding
$2q$–full twists. Conversely, if we add $(-2q)$-full twists on $P$, then the
result is unknotted.

By the classification of twisted torus knots which are unknotted in [18],
$T(3,2;2,-1)$, $T(3,2;2,-2)$, $T(3,1;2,-1)$ and their mirror images
$T(3,-2;2;1)$, $T(3,-2;2,2)$, $T(3,-1;2,1)$ give all $3$–strand twisted torus
knots, which are unknotted. Thus Table 1 is the list of possible pattern knot
$P$ with genus. (Each knot has a positive braid presentation, so its genus is
calculated as in Section 2.) Since $P$ is an L–space knot and not a $3$–cable,
(1), (2) and (3) are excluded by [17]. (In fact, (1) gives a $3$–cable.)

| Knot | Genus
---|---|---
(1) | $T(3,6q+2;2,-1)$ | $6q$
(2) | $T(3,6q+2;2,-2)$ | $6q-1$
(3) | $T(3,6q+1;2,-1)$ | $6q-1$
(4) | $T(3,6q-2;2,1)$ | $6q-2$
(5) | $T(3,6q-2;2,2)$ | $6q-1$
(6) | $T(3,6q-1;2,1)$ | $6q-1$
Table 1. List of the pattern knot $P$ and its genus.

Recall that $g(K_{n})=9n+7$ and $g(T)=(q-1)/2$. If $g(P)=6q-1$, then
$9n+7=3(q-1)/2+6q-1$, so $18n+14=3(q-1)+12q-2$. Then $18n+14\equiv-2\pmod{3}$,
a contradiction. Thus (4) remains. For this case, $9n+7=3(q-1)/2+6q-2$ gives
$6n+7=5q$. Then $n\equiv 3\pmod{5}$. Set $n=5m+3\ (m\geq 0)$. Then $q=6m+5$.

We have $\Delta_{K_{n}}(-1)=\Delta_{T}(-1)\Delta_{P}(-1)$, and
$\Delta_{K_{n}}(-1)=10n+11=50m+41$ from Theorem 4.1. However,
$\Delta_{T}(-1)=q=6m+5$. Then $6m+5$ does not divide $50m+41$, a
contradiction.

Thus we have shown that our $K_{n}$ is hyperbolic. ∎

###### Proof of Theorem 2.1.

By Theorems 3.1 and 5.2, $K_{n}$ is a hyperbolic L–space knot. Its formal
semigroup is described in Theorem 4.3. ∎

## Acknowledgments

The author would like to thank Ken Baker, Marc Kegel and Kimihiko Motegi for
valuable communication, and Yukinori Kitadai for his help of computer
calculation. The author also thanks the referee for valuable suggestions and
comments.

## References

  * [1] C. Anderson, K. Baker, X. Gao, M. Kegel, K. Le, K. Miller, S. Onaran, G. Sangston, S. Tripp, A. Wood and A. Wright, L–space knots with tunnel number $>1$ by experiment, preprint. arXiv:1090.00790.
  * [2] K. Baker and M. Kegel, Census L–space knots are braid positive, except for one that is not, preprint. arXiv:2203.12013.
  * [3] K. Baker, M. Kegel and D. McCoy, The search for alternating and quasi-alternating surgeries on asymmetric knots, preprint.
  * [4] K. Baker and A. Moore, Montesinos knots, Hopf plumbings, and L–space surgeries, J. Math. Soc. Japan. 70 (2018) 95–110.
  * [5] K. Baker and K. Motegi, Seifert vs. slice genera of knots in twist families and a characterization of braid axes, Proc. Lond. Math. Soc. (3) 119 (2019) 1493–1530.
  * [6] M. Borodzik and C. Livingston, Heegaard Floer homology and rational cuspidal curves, Forum Math. Sigma. 2 (2014), Paper No. e28, 23 pp.
  * [7] M. Borodzik and C. Livingston, Semigroups, $d$–invariants and deformations of cuspidal singular points of plane curves, J. Lond. Math. Soc. (2) 93 (2016) 439-463.
  * [8] G. Burde, H. Zieschang and M. Heusener, Knots, Third, fully revised and extended edition, (De Gruyter Studies in Mathematics, 5. De Gruyter, Berlin, 2014.)
  * [9] R. H. Fox, Free differential calculus II, Ann. of Math. (2) 59 (1954) 196–210.
  * [10] J. Hanselman, J. Rasmussen and L. Watson, Bordered Floer homology for manifolds with torus boundary via immersed curves, preprint. arXiv:1604.03466.
  * [11] M. Hedden and L. Watson, On the geography and botany of knot Floer homology, Selecta Math. (N.S.) 24 (2018) 997–1037.
  * [12] E. Hironaka, The Lehmer polynomial and pretzel links, Canad. Math. Bull. 44 (2001) 440–451.
  * [13] J. Hom, T. Lidman and F. Vafaee, Berge–Gabai knots and L–space satellite operations, Algebr. Geom. Topol. 14 (2014) 3745–3763.
  * [14] A. Issa, The classification of quasi-alternating Montesinos links, Proc. Amer. Math. Soc. 146 (2018) 4047–4057.
  * [15] K. Kodama, The software “KNOT”, a tool for knot theory, available at http://www.math.kobe-u.ac.jp/HOME/kodama/knot.html
  * [16] D. Krcatovich, A restriction on the Alexander polynomials of L–space knots, Pacific J. Math. 297 (2018) 117–129.
  * [17] C. R. S. Lee and F. Vafaee, On $3$–braids and L–space knots, Geom. Dedicata. 213 (2021) 513–521.
  * [18] S. Lee, Twisted torus knots that are unknotted, Int. Math. Res. Not. (2014) 4958–4996.
  * [19] P. Lisca and G. Matić, Transverse contact structures on Seifert $3$–manifolds, Algebr. Geom. Topol. 4 (2004) 1125–1144.
  * [20] P. Lisca and A. Stipsicz, Ozsváth-Szabó invariants and tight contact $3$–manifolds. III, J. Symplectic Geom. 5 (2007) 357–384.
  * [21] J. M. Montesinos, Surgery on links and double branched covers of $S^{3}$, in Knots, groups, and $3$–manifolds (Papers dedicated to the memory of R. H. Fox), pp. 227–259. (Ann. of Math. Studies, No. 84, Princeton Univ. Press, Princeton, N.J., 1975. )
  * [22] K. Morimoto and M. Sakuma, On unknotting tunnels for knots, Math. Ann. 289 (1991) 143–167.
  * [23] H. Morton, The Alexander polynomial of a torus knot with twists, J. Knot Theory Ramifications. 15 (2006) 1037–1047.
  * [24] K. Motegi and K. Tohki, Hyperbolic L–space knots and exceptional Dehn surgeries, J. Knot Theory Ramifications. 23 (2014) 1450079, 13 pp.
  * [25] Y. Ni, Knot Floer homology detects fibred knots, Invent. Math. 170 (2007) 577–608.
  * [26] P. Ozsváth and Z. Szabó, On knot Floer homology and lens space surgeries, Topology. 44 (2005) 1281–1300.
  * [27] P. Ozsváth and Z. Szabó, On the Heegaard Floer homology of branched double-covers, Adv. Math. 194 (2005) 1–33.
  * [28] P. Ozsváth and Z. Szabó, Knot Floer homology and rational surgeries, Algebr. Geom. Topol. 11 (2011) 1–68.
  * [29] J. Rasmussen and S. Rasmussen, Floer simple manifolds and L–space intervals, Adv. Math. 322 (2017) 738–805.
  * [30] H. Schubert, Über eine numerische Knoteninvariante, Math. Z. 61 (1954) 245–288.
  * [31] J. Stallings, Constructions of fibred knots and links, in Algebraic and geometric topology, Proc. Sympos. Pure Math., Stanford Univ., Stanford, Calif., 1976, Part 2, pp. 55–60, (Proc. Sympos. Pure Math., XXXII, Amer. Math. Soc., Providence, R.I., 1978.)
  * [32] M. Tange, On the Alexander polynomial of lens space knots, Topology Appl. 275 (2020) 107124, 37 pp.
  * [33] M. Tange, The third term in lens surgery polynomials, Hiroshima Math. J. 51 (2021) 101–109.
  * [34] G. Torres, On the Alexander polynomial, Ann. of Math. (2) 57 (1953) 57–89.
  * [35] S. Wang, Semigroups of L–space knots and nonalgebraic iterated torus knots, Math. Res. Lett. 25 (2018) 335–346.
  * [36] L. Watson, A surgical perspective on quasi-alternating links, in Low-dimensional and symplectic topology, 39–51, (Proc. Sympos. Pure Math., 82, Amer. Math. Soc., Providence, RI, 2011. )


11institutetext: Manipal Institute of Technology
11email: {nemakallu.rakshit, ankita.ghosh1, yash.maurya1,
<EMAIL_ADDRESS>
22institutetext: SRM Institute of Science and Technology
22email<EMAIL_ADDRESS>
# IS-CAM: Integrated Score-CAM for axiomatic-based explanations

Rakshit Naidu 11 Ankita Ghosh 11 Yash Maurya 11 Shamanth R Nayak K 11 Soumya
Snigdha Kundu 22

###### Abstract

Convolutional Neural Networks have been known as black-box models as humans
cannot interpret their inner functionalities. With an attempt to make CNNs
more interpretable and trustworthy, we propose IS-CAM (Integrated Score-CAM),
where we introduce the integration operation within the Score-CAM pipeline to
achieve visually sharper attribution maps quantitatively. Our method is
evaluated on 2000 randomly selected images from the ILSVRC 2012 Validation
dataset, which proves the versatility of IS-CAM to account for different
models and methods.

###### Keywords:

Explainable AI Interpretable ML.

##  I Introduction

Convolutional Neural Networks (CNNs) are paramount when it comes to solving
state of the art vision problems. The deployment of these models in sensitive
situations such as the medical and security industry cannot be done without
understanding and interpreting the intuition of the models as that will
greatly increase the chances for model failure and deplete the confidence of
the model. To overcome these concerns and maintain the sensitivity of the
task, a new research direction was put forward in order to build explainable
models with CAMs [12]. Explainable models not only help in recognizing the
drawbacks but also help in generating insights and accumulation of valuable
information in tandem to the model’s inference. It also helps in debugging the
model and removing bias. Our work builds upon the CAM-based approaches [10]
[9] , which acquire attribution maps by a linear combination of the weights
and the activation maps. While there are two different approaches to using
CAMs we focused on the gradient-free approach as there are issues pertaining
to gradient CAMs such as saturation and false confidence [7]. One of the first
approaches towards a gradient-free method was Score-CAM [10], but due to its
coarse localization, it tends to lead to erratic localizations in certain
cases. Our contributions to overcome the existing issues are:

  * •

We propose a new axiomatic-based approach IS-CAM, which is combined within the
Score-CAM pipeline to produce sharper attribution maps.

  * •

We attain improved performance in comparison to previous CAM-based methods. We
quantitatively evaluate over faithfulness and localization tasks, which
indicate better localized decision-related features of IS-CAM.

##  II Related Work

IntegratedGrad:  [9] demonstrated their ability to debug a network by
extracting certain rules from the network, thereby enabling the users to
engage more with the models and understand the network’s predictions. They
introduced two axioms for attribution methods, namely: Sensitivity (if there
is a feature difference between the input and the baseline and have different
predictions, then the differing feature should be assigned a non-zero
attribution) and Implementation Invariance (if two networks give the same
output for all inputs, despite having different implementations, the
attributions should be equal in these two functionally equivalent networks).
The Integrated gradient along the ${i}^{th}$ dimension is denoted by:

$\left(x_{i}-x_{i}^{\prime}\right)\times\int^{1}_{\alpha=0}\dfrac{\partial
F(x^{\prime}+\alpha\times\left(x-x^{\prime}\right))}{\partial x_{i}}d\alpha$
(1)

where ${x}$ is the input and ${x^{\prime}}$ is the baseline. $\dfrac{\partial
F\left(x\right)}{\partial x_{i}}$ represents the gradient of ${F(x)}$ along
the ${i}^{th}$ dimension.

Class Activation Maps:  The inspiration driving CAM [12] is that each
activation map $A^{k}_{l}$, where $A$ denotes the activation map for the
$k$-th channel and $l$-th layer, contains distinctive spatial information
about the input $X$. For a given class $c$, the input to the softmax $S_{c}$
is $\sum\limits_{k}w_{c}^{k}A_{l}^{k}$ where $w_{c}^{k}$ is the weight
corresponding to class $c$ for $k$-th layer and $A_{l}^{k}$ represents the
global pooling layer. CAM $L^{c}_{CAM}$ can be defined as

$L^{c}_{CAM}=ReLU\left(\sum\limits_{k}w_{c}^{k}A_{l-1}^{k}\right)$ (2)

Grad-CAM:  As CAM is limited to GAP-based CNN models, Grad-CAM [7] was
developed to generalize for a wider range of CNN architectures. To obtain each
neuron for a decision of interest, Grad-CAM uses the gradient information
flowing into the last convolutional layer. Considering an activation map
$A^{k}$ for the $k$-th channel, Grad-CAM $L^{c}_{Grad-CAM}$ for target class
$c$ can be defined as

$L^{c}_{Grad-CAM}=ReLU\left(\sum\limits_{k}\alpha_{c}^{k}A^{k}\right)$ (3)

where $\alpha_{c}^{k}$ represents the neuron importance weights.
$\alpha_{c}^{k}=\frac{1}{Z}\sum\limits_{i}\sum\limits_{j}\frac{\partial
Y_{c}}{\partial A^{k}_{ij}}$ where $Y_{c}$ is the score computed for the
target class, $(i,j)$ represents the location of the pixel and $Z$ denotes the
total number of pixels.

Some other variations of Grad-CAM like Grad-CAM++ and Smooth Grad-CAM++ serve
as a comparison for our algorithm in the sections that follow.

Score-CAM:  In Score-Cam [10], the weights of the score obtained for a
specific target class $c$ are utilized. Score-CAM disposes of the reliance on
the gradient and provides a more generalized framework as it only requires
access to the class activation map and output scores. Considering an
activation map $A^{k}_{l}$ for $k$-th channel and $l$-th convolutional layer,
Score-CAM $L^{c}_{Score-CAM}$ can be defined as

$L^{c}_{Score-CAM}=ReLU\left(\sum\limits_{k}\alpha_{c}^{k}A^{k}_{l}\right)$
(4)

where $\alpha_{c}^{k}$ denotes the channel-wise Increase of Confidence
performed on $A^{k}_{l}$ in order to measure the importance of the activation
map.

##  III Proposed Approach

In this section, we explain our approach on how we combine IntegratedGrad [9]
within the Score-CAM pipeline. Figure 1 shows our pipeline.

We set a parameter $N$ as the number of intervals between the range [0, 1]. As
the integration operation is analogous to the summation operation, we
calculate scores of the maps at each step of the interval from $0$ to $1$.
Finally, we calculate the average of the scores generated as the mean
operation is sensitive to changes in the saliency maps generated at each step
of the process. Note that $M_{0}=0$.

Integrating over the input mask:

$L^{c}_{IS-CAM}=ReLU\left(\sum_{k}\alpha^{c}_{k}A^{k}_{l}\right)$ (5)

$where$

$\alpha^{c}_{k}=\dfrac{\sum^{N}_{i=1}\left(C(M_{i})\right)}{N}$ (6)
$M_{i+1}\leftarrow M_{i}+\left((X_{0}*A^{k}_{l})*\frac{i}{N}\right)$ (7)

Normalization:

As the spatial region needs to focused on the object in the image, we leverage
the features within a particular region by following the same normalization
function as stated in [10], [11]. The normalization used in the algorithm is
given as:

$s\left(A^{k}_{l}\right)=\dfrac{A^{k}_{l}-min(A^{k}_{l})}{max(A^{k}_{l})-min(A^{k}_{l})}$
(8)

Figure 1: Pipeline of the proposed IS-CAM approach. The saliency map is
produced by the linear combination of the average scores after ”integration”
and the upsampled activation maps. The average score is obtained from
performing summation over the normalized input mask at every interval.

##  IV Experiments

In this section, we conduct experiments to evaluate the effectiveness of the
proposed explanation method. Our setup is similar to that described in [1],
[6], [10]. First, a qualitative output comparison of the architectures by
visualization on the ILSVRC 2012 Validation set in section A. Second, we
assess the fairness of the interpretations of architectures for object
recognition in section B. Third, the Energy-based pointing game (proposed in
[1]) is used to evaluate the bounding boxes for the class-conditional object
localization in a given image in section C over 2000 uniformly random selected
images from the ILSVRC Validation Set 2012.

Our comparative analysis extends to five other known CAM methods, Grad-CAM
[7], Grad-CAM++ [1], Smooth Grad-CAM++ [5] Score-CAM [10], and Smoothed Score-
CAM [11]. The images are resized with a fixed size (224, 224, 3), condensed
into the [0,1] range and then, normalized using ImageNet [2] weights (mean
vector : [0.485, 0.456, 0.406] and standard deviation vector [0.229, 0.224,
0.225]). For simplicity, baseline image $X_{b}$ is set to 0(as shown in
Channel-wise Increase in Confidence [10]).

A. _Visual Comparison_

To perform this experiment, 2,000 images were randomly selected from the 2012
ILSVRC Validation Set. Fig 2 shows a few photos comparing our approach to
prevailing CAM approaches. Here, we used N = 15 and $\sigma$ = 2 for SS-CAM.
Even though we achieve comparable visual results to Score-CAM, we perform
better quantitatively in terms of the Faithfulness explanations as shown in
the next section.

Figure 2: Depicts the Imagenet Labels (Row-wise): Basenji, Capuchin and
Whippet. This figure is used for a Visual Comparison of our approach with the
other existing approaches. We use $N=10$ here.

B. _Faithfulness Evaluations_

Faithfulness evaluations are carried out as described in Grad-CAM++ [1] for
the purpose of Object Recognition. Three metrics called Average Drop, Average
Increase In Confidence, and Win $\%$ are implemented. These metrics are tested
for 2000 images randomly chosen from the ILSVRC 2012 Validation set, using the
pre-trained VGG-16 model. To perform this sub-experiment, we used N = 15 and
$\sigma$ = 2 (for SS-CAM).

Table I: Average AUC scores of the Insertion curve(the higher, the better) and Deletion curve(the lower, the better) over all the 2000 images. CAM techniques |  Insertion % |  Deletion %
---|---|---
Grad-CAM |  45.25 |  11.25
G-CAM ++ 111Grad-CAM++ |  44.94 |  11.41
SG-CAM++ 222Smooth Grad-CAM++ |  42.68 |  13.43
Score-CAM |  48.22 |  9.92
SS-CAM |  45.92 |  11.46
IS-CAM |  48.13 |  9.92

Insertion and Deletion Curves are used to calculate the Area Under Curve (AUC)
metric to understand how many pixels of the saliency map will either add or
reduce the scores of the resulting fractioned maps. We average the resulting
pixel values at each stage(deleting/inserting 224 pixels) over all the 2000
images and produce graphs in Figure 3. The Deletion operation demonstrates the
ability to remove the map information pixel-wise. A sharp decline and a lower
AUC of the generated scores imply a good explanation. The Insertion operation
evaluates the ability to reconstruct the saliency map from a given baseline. A
sharp rise and higher AUC of the generated scores imply a good explanation.

Figure 3: Insertion and Deletion curve charts for Table I.

  1. 1.

Average Drop %: The Average Drop refers to the maximum positive difference in
the predictions made by the prediction using the input image and the
prediction using the saliency map. It is given as:
$\sum_{i=1}^{N}\frac{max(0,Y_{i}^{c}-O_{i}^{c})}{Y_{i}^{c}}\times 100$. Here,
Yic refers to the prediction score on class c using the input image i and Oic
refers to the prediction score on class c using the saliency map produced over
the input image i.

  2. 2.

Increase in Confidence %: The Average Increase in Confidence is denoted as:
$\sum_{i=1}^{N}\frac{Fun(Y_{i}^{c}<O_{i}^{c})}{N}\times 100$ where Fun refers
to a boolean function which returns 1 if the condition inside the brackets is
true, else the function returns 0. The symbols are referred to as shown in the
above experiment for Average Drop.

  3. 3.

Win %: The Win percentage refers to the decrease in the model’s confidence for
an explanation map generated by IS-CAM to the confidence generated by another
algorithm. This metric is compared to the confidence generated by SS-CAM [11]
maps and Score-CAM [10] maps with IS-CAM maps. When our approach is compared
to SS-CAM, we get 59.25% and when compared to Score-CAM, we get 52.35% using
VGG-16(higher is better); which indicates that IS-CAM performs better with
respect to this metric.

The AUC scores, Average Drop and Increase in Confidence indicate that IS-CAM
performs better on an overall perspective. While Score-CAM performs well in
AUC scores it fails to do so in Average Drop and Inc% using VGG-16 . Likewise,
SS-CAM does well in Average Drop and Inc% but it fails to do so in AUC scores.
IS-CAM does well in both perspectives which shows its profound versatility.

Table II: Average Drop (the lower, the better) and Average Increase in Confidence (the higher, the better) across 2000 ILSVRC Validation images. CAM | VGG-16 | Resnet | SqueezeNet
---|---|---|---
Techniques | Avg Drop% | Avg Inc% | Avg Drop% | Avg Inc% | Avg Drop% | Avg Inc%
Score-CAM | 66.03 | 51.85 | 64.23 | 53.55 | 13.42 | 60.85
SS-CAM | 79.15 | 51.30 | 64.53 | 54.80 | 12.06 | 64.85
IS-CAM | 63.30 | 52.35 | 64.85 | 53.50 | 13.00 | 62.15

C. _Localization Evaluations_

This section accomplishes evaluations related to Bounding boxes. A metric
known as Energy-based pointing game, as introduced in [10], is employed for
our localization experiments. This helps in calculating how much energy of the
saliency map falls within the given Bounding box. This is achieved in two
steps. The first step of this is where the input image is binarized,
specifically with the interior of the Bounding box marked as 1 and the region
outside the Bounding box as 0. This is then multiplied element-wise with the
saliency map generated for the input image and summed over to calculate
proportion ratio which is given as - $Proportion=\frac{\sum L^{c}_{(i,j)\in
bbox}}{\sum L^{c}_{(i,j)\in bbox}+\sum L^{c}_{(i,j)\notin bbox}}$. We evaluate
this metric on 2000 randomly selected images from the ILSVRC 2012 Validation
set [2]. These images are then fed to 3 pre-trained models, namely, VGG-16
[8], ResNet-18(Residual Network with 18 layers) [3], and SqueezeNet1.0 [4].
Table III portrays the results of the localization evaluation for the 3
architectures. We see that IS-CAM performs better than most techniques in all
three models. It also achieves the highest value for the VGG-16 variant.

Table III: Localization Evaluation CAM techniques |  VGG-16 Proportion(%) |  ResNet18 Proportion(%) |  SqueezeNet1.0 Proportion(%)
---|---|---|---
Grad-CAM |  42.69 |  43.55 |  42.01
G-CAM++ |  42.87 |  43.53 |  41.83
SG-CAM++ |  42.97 |  43.56 |  41.77
Score-CAM |  43.07 |  43.46 |  42.48
SS-CAM |  42.46 |  43.30 |  41.98
IS-CAM |  43.17 |  43.52 |  42.40

##  V Conclusion & Future Work

Our proposed method involves integrating over the input mask and averaging the
scores obtained from the normalised masks. According to our experiments, the
increase or decrease of the value $N$, does not have a significant impact on
the visual attribution map produced. The effect of $N$ is quite evident
quantitatively as demonstrated in our experiments. In the future, we hope to
test our algorithms in the medical domain to prove its effectiveness in
sensitive real world scenarios.

## Acknowledgment

We thank Mr. Haofan Wang from Carnegie Mellon University for his valuable
inputs during the discussion. We would also like to thank the Research Society
MIT, Manipal(RSM) for supporting and moderating the project.

## References

  * [1] Chattopadhyay, A., Sarkar, A., Howlader, P., Balasubramanian, V.N.: Grad-cam++: Improved visual explanations for deep convolutional networks (2017)
  * [2] Deng, J., Dong, W., Socher, R., Li, L., Kai Li, Li Fei-Fei: Imagenet: A large-scale hierarchical image database pp. 248–255 (2009)
  * [3] He, K., Zhang, X., Ren, S., Sun, J.: Deep residual learning for image recognition. 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) pp. 770–778 (2016)
  * [4] Iandola, F.N., Moskewicz, M.W., Ashraf, K., Han, S., Dally, W., Keutzer, K.: Squeezenet: Alexnet-level accuracy with 50x fewer parameters and ¡1mb model size. ArXiv abs/1602.07360 (2017)
  * [5] Omeiza, D., Speakman, S., Cintas, C., Weldermariam, K.: Smooth grad-cam++: An enhanced inference level visualization technique for deep convolutional neural network models (2019)
  * [6] Petsiuk, V., Das, A., Saenko, K.: Rise: Randomized input sampling for explanation of black-box models (2018)
  * [7] Selvaraju, R.R., Cogswell, M., Das, A., Vedantam, R., Parikh, D., Batra, D.: Grad-cam: Visual explanations from deep networks via gradient-based localization (2016)
  * [8] Simonyan, K., Zisserman, A.: Very deep convolutional networks for large-scale image recognition. CoRR abs/1409.1556 (2015)
  * [9] Sundararajan, M., Taly, A., Yan, Q.: Axiomatic attribution for deep networks. In: ICML (2017)
  * [10] Wang, H., Wang, Z., Du, M., Yang, F., Zhang, Z., Ding, S., Mardziel, P., Hu, X.: Score-cam: Score-weighted visual explanations for convolutional neural networks. 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW) pp. 111–119 (2020)
  * [11] Wang, H., Naidu, R., Michael, J., Kundu, S.S.: Ss-cam: Smoothed score-cam for sharper visual feature localization (2020)
  * [12] Zhou, B., Khosla, A., Lapedriza, A., Oliva, A., Torralba, A.: Learning deep features for discriminative localization (2015)