# Chunk-based Nearest Neighbor Machine Translation

Pedro Henrique Martins♆♏ Zita Marinho♄☽ André F. T. Martins♆♇♏
♆Instituto de Telecomunicações ♏Unbabel ♄Institute of Systems and Robotics
☽DeepMind ♇LUMLIS (Lisbon ELLIS Unit), Instituto Superior Técnico
Lisbon, Portugal
<EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Semi-parametric models, which augment generation with retrieval, have led to
impressive results in language modeling and machine translation, due to their
ability to retrieve fine-grained information from a datastore of examples. One
of the most prominent approaches, $k$NN-MT, exhibits strong domain adaptation
capabilities by retrieving tokens from domain-specific datastores (Khandelwal
et al., 2021). However, $k$NN-MT requires an expensive retrieval operation for
every single generated token, leading to a very low decoding speed (around 8
times slower than a parametric model). In this paper, we introduce a chunk-
based $k$NN-MT model which retrieves chunks of tokens from the datastore,
instead of a single token. We propose several strategies for incorporating the
retrieved chunks into the generation process, and for selecting the steps at
which the model needs to search for neighbors in the datastore. Experiments on
machine translation in two settings, static and “on-the-fly” domain
adaptation, show that the chunk-based $k$NN-MT model leads to significant
speed-ups (up to 4 times) with only a small drop in translation quality.111The
code is available at https://github.com/deep-spin/chunk-based_knn-mt.

##  1 Introduction

Machine translation has seen remarkable advances due to increasingly powerful
neural models (Sutskever et al., 2014; Bahdanau et al., 2015; Vaswani et al.,
2017). Most deployed systems are fully-parametric (the training data is fully
compressed into the parameters of a neural model), but they often struggle
when translating rare words or out-of-domain sentences (Koehn and Knowles,
2017), commonly requiring several stages of fine-tuning to adapt to data drift
or to new domains. Recently, semi-parametric methods have shown great promise,
by combining the strengths of parametric models with external databases of
parallel sentences, such as translation memories (Gu et al., 2018; Zhang et
al., 2018; Bapna and Firat, 2019a; Meng et al., 2021; Zheng et al., 2021a;
Jiang et al., 2021; Martins et al., 2022).

One of the most prominent semi-parametric models for machine translation is
the $k$-Nearest Neighbor Machine Translation model ($k$NN-MT) (Khandelwal et
al., 2021), which has led to impressive results, particularly in domain
adaptation settings, without requiring fine-tuning. The $k$NN-MT model
constructs domain-specific datastores of parallel sentences and, at inference
time, it retrieves similar examples from these datastores, which are used to
improve the generation process, through the interpolation of probability
distributions. However, $k$NN-MT only retrieves single tokens—this is
inefficient, since the model needs to consult the datastore at every
generation step, an expensive operation. Consequently, its decoding speed is
around 8 times slower than that of a fully-parametric model.

Recent work has introduced several techniques to speed up $k$NN-MT. Meng et
al. (2021) proposed Fast $k$NN-MT, which constructs a different datastore for
each example, by first searching for the nearest neighbors of the source
tokens. Wang et al. (2021) introduced Faster $k$NN-MT, similar to Fast $k$NN-
MT but with reduced memory requirements. Martins et al. (2022) proposed
pruning the datastore, reducing the keys’ representation size, and using a
cache of retrieval distributions. However, despite leading to some decoding
speedups, these methods are limited as they still retrieve a single token at
each time step.

In this paper, we propose a simple and efficient chunk-based $k$NN-MT model.
Inspired by RETRO (Borgeaud et al., 2021), the chunk-based $k$NN-MT model
retrieves chunks of tokens, instead of single tokens. But, similarly to $k$NN-
MT and unlike RETRO, it does not require any training or fine-tuning of the
parametric component: it simply uses a combination of caching and
interpolation of probability distributions to incorporate the retrieved
tokens. By doing this, the model leads to a similar translation quality while
having to search for neighbors in the datastore less often. This leads to
decoding speeds up to 4 times faster than the ones achieved using the vanilla
$k$NN-MT model and only twice as slow as a fully-parametric model, but with
considerably higher translation quality.

In sum, our main contributions are:

  * •

We introduce a chunk-based $k$NN-MT model, which retrieves chunks of tokens
from a datastore of examples.

  * •

We propose and compare several approaches to deal with the retrieved chunks’
tokens and to select the steps in which the model performs retrieval from the
datastore.

  * •

We compare the translation quality and decoding efficiency on domain
adaptation, which shows the benefits of chunk-based $k$NN-MT.

  * •

We propose using chunk-based $k$NN-MT for on-the-fly adaptation.

##  2 Background

In machine translation, a model is given a sentence or document in a source
language, $\bm{x}=[x_{1},\dots,x_{L}]$, and the goal is to output a
translation in a target language, $\bm{y}=[y_{1},\dots,y_{N}]$. This is
commonly done using a parametric sequence-to-sequence model (Sutskever et al.,
2014; Bahdanau et al., 2015; Vaswani et al., 2017), in which the encoder
receives the source sentence as input and outputs a set of hidden states.
Then, at each step $t$, the decoder attends to these hidden states and outputs
a probability distribution over the vocabulary,
$p_{\mathrm{NMT}}(y_{t}|\bm{y}_{<t},\bm{x})$. Finally, these probability
distributions are used in a search procedure to generate the translation,
typically using beam search (Reddy, 1977).

###  2.1 $k$-Nearest Neighbor Machine Translation

Khandelwal et al. (2021) introduced a semi-parametric model called $k$-nearest
neighbor machine translation ($k$NN-MT). $k$NN-MT is composed of a parametric
component that outputs a probability distribution over the vocabulary as
above, $p_{\mathrm{NMT}}(y_{t}|\bm{y}_{<t},\bm{x})$, enhanced with an
approximate nearest neighbor retrieval mechanism, which allows direct access
to a datastore of examples.

The $k$NN-MT’s datastore $\mathcal{D}$ consists of a key-value memory, where
each key is the decoder’s output representation,
$\bm{f}(\bm{x},\bm{y}_{<t})\in\mathbb{R}^{d}$, and the value is the
corresponding target token $y_{t}\in\mathcal{V}$:

$\mathcal{D}=\left\\{\left(\bm{f}(\bm{x},\bm{y}_{<t}\right),y_{t})\;\forall\;t\mid(\bm{x},\bm{y})\in\mathcal{S}\right\\},$
(1)

where $\mathcal{S}$ denotes a set of parallel sentences. Then, at inference
time, the model searches the datastore to (approximately) retrieve the set of
$k$ nearest neighbors $\mathcal{N}$. The retrieval distribution,
$p_{k\mathrm{NN}}(y_{t}|\bm{y}_{<t},\bm{x})$, is computed, using the
neighbors’ distance to the current decoder’s output representation,
$d(\bm{f}(\bm{x},\bm{y}_{<t}),\cdot)$:

$\displaystyle p_{k\mathrm{NN}}(y_{t}|\bm{y}_{<t},\bm{x})=$ (2)
$\displaystyle\dfrac{\sum_{(\bm{k}_{j},v_{j})\in\mathcal{N}}\mathbbm{1}_{y_{t}=v_{j}}\exp\left(-d\left(\bm{k}_{j},\bm{f}(\bm{x},\bm{y}_{<t})\right)/T\right)}{\sum_{(\bm{k}_{j},v_{j})\in\mathcal{N}}\;\exp\left(-d\left(\bm{k}_{j},\bm{f}(\bm{x},\bm{y}_{<t})\right)/T\right)},$

where $T$ is the softmax temperature, $k_{j}$ denotes the key of the $j^{th}$
neighbor and $v_{j}$ its value. Finally, the two distributions,
$p_{\mathrm{NMT}}(y_{t}|\bm{y}_{<t},\bm{x})$ and
$p_{k\mathrm{NN}}(y_{t}|\bm{y}_{<t},\bm{x})$, are combined, by performing
interpolation, to obtain the final distribution, which is used to generate the
translation through beam search:

$\displaystyle p(y_{t}|\bm{y}_{<t},\bm{x})=$
$\displaystyle\,\,(1-\lambda)\;p_{\mathrm{NMT}}(y_{t}|\bm{y}_{<t},\bm{x})$ (3)
$\displaystyle+\lambda\;p_{k\mathrm{NN}}(y_{t}|\bm{y}_{<t},\bm{x}),$

where $\lambda\in[0,1]$ is a hyperparameter that controls the weight given to
the two distributions.

##  3 Chunk-based $k$NN-MT

Figure 1: Chunk-based $k$NN-MT scheme. Top left: model procedure when
retrieving neighbors from the datastore. Top right: procedure when not
performing retrieval. Bottom: retrieval schedule scheme.

We now describe our chunk-based $k$NN-MT model, illustrated in Figure 1. We
first describe the datastore creation (§3.1) and how we can retrieve chunks of
tokens from it (§3.2), describing how they are used by the model (§3.2.2).
Finally, we describe how to select the steps in which the model performs
retrieval (§3.3).

###  3.1 Building the datastore

For the model to retrieve a chunk of tokens of size $c$ instead of a single
token, we first need to build a datastore $\mathcal{D}$ which also consists of
a key-value memory, where each entry key is the decoder’s output
representation $\bm{f}(\bm{x},\bm{y}_{<t})$, but the value is now a chunk of
target tokens $y_{t:(t+c-1)}$: 222When the chunk size $c$ is larger than the
number of the remaining tokens in the sentence, $N-(t-1)$, we add padding
tokens to complete the chunk.

$\displaystyle\mathcal{D}=$
$\displaystyle\\{\left(\bm{f}(\bm{x},\bm{y}_{<t}\right),y_{t:(t+c-1)})\;\forall\;t\mid(\bm{x},\bm{y})\in\mathcal{S}\\}.$
(4)

Note that the chunks are sliding windows, i.e., they overlap.

###  3.2 Retrieving chunks of tokens

At inference time, when performing retrieval, the model searches the datastore
and retrieves the set of $k$ nearest neighbors $\mathcal{N}$, for each beam
hypothesis and example in the current batch. We now describe several
strategies to manipulate the retrieved chunks of tokens during generation.

####  3.2.1 Maintaining the chunk order

Since in the original sentences used to build the datastore each chunk is
composed of an ordered sequence of tokens, the simplest way for the model to
use the retrieved tokens is to consider them in the same order. For this, we
simply need to compute a retrieval distribution for each token in the chunk,
always using the same retrieval distances but aligning the chunk tokens with
the corresponding time step, i.e. at the retrieval step we consider the first
token of each neighbor chunk, at the following step we consider the second
token, and so on. We can compute this retrieval distribution as it is done for
the $k$NN-MT, in Eq. 2, just modifying the token indices according to the
step. However, by doing this, we are ignoring the remaining tokens in the
chunk, which can also contain relevant information for the current prediction.
Also, the tokens that are generated in the previous steps $t,\dots,t+j-1$
might not be well “aligned” with the next tokens in the $j$th position of the
chunk for all neighbors.

####  3.2.2 Neighbors’ Cache

To avoid the limitation stated above, we propose using a neighbors’ cache
instead. We keep the tokens of the retrieved chunks in this cache, so that the
model has a higher flexibility about which tokens to select for the current
step: it has access to all the tokens present in the retrieved chunks. The
neighbors’ cache, $\mathcal{M}$, consists of a key-value memory, where a key
is the decoder’s output representation, $\bm{f}(\bm{x},\bm{y}_{<t})$, and a
value is the corresponding target token $y_{t}$, as in the datastore:

$\displaystyle\mathcal{M}=$
$\displaystyle\\{\left(\bm{f}(\bm{x},\bm{y}_{<t+i}\right),y_{t+i})\;\forall\;0\leq
i<c\;\forall\;y_{t}\mid$ $\displaystyle y_{t:(t+c-1)}\in\mathcal{N}\\}.$ (5)

Note, however, that this cache requires having the decoder state for every
token in the chunk, not just for the first one. Therefore, we need to have
this information available in the datastore:333To avoid having the same
decoder states in several entries, we just store pointers to an array of
decoder states.

$\displaystyle\mathcal{D}=\;$
$\displaystyle\\{\left(\bm{f}(\bm{x},\bm{y}_{<t}\right),y_{t:(t+c-1)},$
$\displaystyle[\bm{f}(\bm{x},\bm{y}_{<t}),\dots,\bm{f}(\bm{x},\bm{y}_{<t+c-1})])$
$\displaystyle\forall\;t\mid(\bm{x},\bm{y})\in\mathcal{S}\\}.$ (6)

Then, as shown in the diagram of Figure 1, at the retrieval steps, the model
first searches for the nearest neighbors in the datastore, then builds the
neighbors’ cache with the tokens of the retrieved chunks, then finally uses
the first token of each chunk to compute the current retrieval distribution.
In contrast, at the non-retrieval steps, the model searches for the nearest
neighbors in the neighbors’ cache instead of retrieving from the datastore.
Then, to compute the retrieval distribution it also uses the softmax, as in
Eq. 2, but with a different softmax temperature, $T^{\prime}$. To incorporate
the retrieved tokens, it performs interpolation as before, Eq. 3, replacing
the hyperparameter $\lambda$ by $\lambda^{\prime}$.444We use a different
temperature and interpolation coefficient at the non-retrieval steps because
the number of entries in the neighbors’ cache is much smaller than in the
datastore, hence the neighbors might be less similar.

##### Considering batch-beam-level neighbors.

By building this neighbors’ cache, the model can use all the tokens in the
retrieved chunks that correspond to each beam hypothesis of the sentence being
translated. However, it still ignores the chunks of tokens corresponding to
the other beam hypotheses, which are often quite similar, and the other
sentences being translated in the same batch, which can contain relevant
contextual information if they belong to the same document.

To also leverage these, we propose increasing the number of tokens that the
model has access to, by combining the chunks retrieved for the different beam
hypotheses and the different examples of the same batch. To do so, we simply
need to build a single neighbors’ cache for the current batch, to which we
feed all the retrieved chunks’ tokens.

##### Considering sentence-level neighbors.

To also consider the chunks of tokens retrieved in previous steps of the
generation of the current sentences, we propose to keep these in the
neighbors’ cache, instead of resetting the cache at each retrieval step.

We empirically compare these different proposed approaches in §4.1.3.

###  3.3 Retrieval Steps Schedule

As the need to perform retrieval slows down decoding considerably, having an
efficient retrieval schedule is key to achieve decoding speedups. The simplest
scheduling option corresponds to performing retrieval every $i$ steps.
However, we noticed empirically that it is beneficial to perform retrieval
steps more frequently at the beginning of the sentence, as we will see in
Table 3 of §4.1.4. To leverage this, we introduce the following schedule.

Having $k\in\\{1,2,\ldots\\}$ as the retrieval step’s index and $t_{k}$ as the
corresponding time step, (i.e. $t_{k}$ is the position of the token generated
after the $k\textsuperscript{th}$ retrieval step), we propose using a
geometric progression to compute the interval (in tokens) between the
$k\textsuperscript{th}$ and $(k+1)\textsuperscript{th}$ retrieval steps,
$i_{k}=t_{k+1}-t_{k}$:

$i_{k}=\lfloor\min\left(i_{\max},\>i_{\min}\times
2^{\,r\,t_{k}}\right)\rfloor,$ (7)

where $i_{\max}$ and $i_{\min}$ are hyperparameters that define the maximum
and minimum interval between retrieval steps, the rate at which the interval
increases is defined as $r={\frac{1}{2}i_{\max}}/{|\bm{x}|}$ where $|\bm{x}|$
is the source sentence size, and $\lfloor\cdot\rfloor$ denotes the floor
function.555We always consider that the first retrieval step occurs at the
first step of the generation ($t_{0}$=1). By using this progression, the
frequency with which the model performs retrieval decays along the generation,
until the interval between retrieval steps reaches $i_{\max}$. For example,
with $i_{\min}=2$, $i_{\max}=16$, and $|\bm{x}|=20$ the model performs
retrieval at steps: $\\{1,3,7,20,36,52,\dots\\}$. Note that the chunk size,
$c$, is independent of the interval between retrieval steps.

| BLEU | COMET
---|---|---
| Medical | Law | IT | Koran | Average | Medical | Law | IT | Koran | Average
Base MT | 40.01 | 45.64 | 37.91 | 16.35 | 34.98 | .4702 | .5770 | .3942 | -.0097 | .3579
Fine-tuned | 50.47 | 56.56 | 43.82 | 21.54 | 43.10 | .5871 | .6906 | .5856 | .0484 | .4779
$k$NN-MT | 54.47 | 61.23 | 45.96 | 21.02 | 45.67 | .5760 | .6781 | .5163 | .0480 | .4546
Efficient $k$NN-MT | 51.90 | 57.82 | 44.44 | 20.11 | 43.57 | .5513 | .6260 | .4909 | -.0052 | .4158
Chunk-based $k$NN-MT (ours) | 53.16 | 59.65 | 44.18 | 19.33 | 44.08 | .5551 | .6257 | .4854 | .0039 | .4175
Table 1: BLEU and COMET scores on the multi-domains test set, for a batch size
of 8.

Figure 2: Plots of the decoding speed (tokens per second) for the different
models on the medical, law, IT, and Koran domains, for different batch sizes
(1,8,16). The generation speed (y-axis) is in log scale.

##  4 Experiments

To understand if the chunk-based $k$NN-MT is able to maintain the translation
quality while speeding-up decoding, we performed experiments on domain
adaptation (§4.1) and on-the-fly adaptation (§4.2).

###  4.1 Domain Adaptation

##### Dataset and metrics.

For domain adaptation, we perform experiments on the Medical, Law, IT, and
Koran domain data of the multi-domains dataset introduced by Koehn and Knowles
(2017) using the splits redefined by Aharoni and Goldberg (2020). To build the
datastores, we use the training sets that have 6,903,141, 19,061,382,
3,602,862, and 524,374 tokens, respectively. The validation and test sets have
2,000 examples for each domain. For evaluation, we use BLEU (Papineni et al.,
2002; Post, 2018) and COMET (Rei et al., 2020).

##### Models.

As a baseline, we consider the fully parametric base MT model: the winning
system from the WMT’19 German-English news translation task (Ng et al., 2019)
(with 269M parameters), available in Fairseq Ott et al. (2019). We also
compare our chunk-based $k$NN-MT model with other models that have access to
the domain-specific training data: the base model above fine-tuned on the
domain-specific datasets, the vanilla $k$NN-MT model (Khandelwal et al.,
2021), and the Efficient $k$NN-MT model from Martins et al. (2022).

##### Settings.

For all models that perform retrieval, we retrieve $k=8$ neighbors and select
the hyperparameter $\lambda$ for each method and each domain by performing
grid search on $\lambda\in\\{0.5,0.6,0.7,0.8\\}$. For the chunk-based $k$NN-
MT, we also perform grid search on $\lambda^{\prime}\in\\{0.4,0.5,0.6\\}$ and
$T^{\prime}\in\\{1,2,3\\}$. The selected values for the hyperparameters for
each model for each domain, validated on the validation set, are stated in
Table 10 of App. D. We use the softmax temperatures proposed by Khandelwal et
al. (2021) and for the efficient $k$NN-MT, we use the efficiency methods’
parameters proposed by Martins et al. (2022). Where not stated otherwise, we
use the chunk-based $k$NN-MT with chunks of size $c=16$, with a sentence-level
neighbors’ cache, and use the geometric progression heuristic, in Eq. 7, to
select the retrieval steps, with $i_{\min}=2$ and $i_{\max}=16$, since this is
the setting that leads to the best trade-off between translation quality and
decoding speed on the validation set. We also follow Martins et al. (2022) and
use PCA to reduce the datastore keys’ dimension to 256 and the neighbors’
cache keys’ size to 64. To perform search in the datastore and in the
neighbors’ cache, we use FAISS (Johnson et al., 2019).

For the fine-tuned model, we perform fine-tuning for a maximum of 20 epochs on
each domain. We perform grid search on the validation set, using different
learning rates, $\eta\in\\{5\times 10^{-6},1\times 10^{-5},5\times
10^{-5},1\times 10^{-4}\\}$ and two different learning rate schedules
(reducing learning rate on plateau and by the inverse square root) with and
without warmup during 1 epoch. The selected hyperparameters are stated in
Table 11 of App. D.

##### Computational infrastructure.

All experiments were performed on a server with 3 RTX 2080 Ti (11 GB), 12 AMD
Ryzen 2920X CPUs (24 cores), and 128 Gb of RAM. For the decoding speed
measurements, we ran each model on a single GPU while no other process was
running on the server, to have a controlled environment. The nearest neighbor
search in the datastore is performed on the CPUs, since not all datastores fit
into GPU memory.

####  4.1.1 Results

The translation scores are reported in Table 1. We can see that the decrease
of translation quality when comparing the chunk-based $k$NN-MT model with the
vanilla $k$NN-MT model is not substantial in terms of BLEU (-1.5 points on
average) and COMET (-.04 points on average). It can also be seen that the
chunk-based $k$NN-MT model leads to considerably better translation scores
than the base MT model (+9.1 BLEU and +.06 COMET points on average) and to
slightly better results than the efficient $k$NN-MT model in terms of BLEU.
When comparing fine-tuning the base model with the use of semi-parametric
models, the results are not conclusive: in terms of BLEU, the semi-parametric
models lead to better translations, but according to COMET this is not the
case. We present translation examples for the different domains in App. F.

####  4.1.2 Decoding speed

As can be seen in Figure 2, the chunk-based $k$NN-MT model leads to a decoding
speed up to two times higher than the decoding speed of the efficient $k$NN-MT
model of Martins et al. (2022) and up to four times higher than that of the
vanilla $k$NN-MT model of Khandelwal et al. (2021). The chunk-based $k$NN-MT
model is also able to reduce the decoding speed gap to the base MT model to a
factor of two, compared to a factor of four from previous work. Moreover,
according to the results on Table 1 this speed-up comes without substantially
harming the model’s translation quality.

####  4.1.3 What is the best way to incorporate the retrieved tokens?

To understand which chunk incorporation strategy works best, we perform a
comparison using chunks of size $c=6$ and performed retrieval every 6 steps
($i=6$).

| Medical | Law | IT | Koran | Average
---|---|---|---|---|---
Maintain order | 45.17 | 51.48 | 40.11 | 17.87 | 38.66
Neighbors’ Cache |  |  |  |  |
Single chunk | 48.01 | 53.81 | 42.09 | 18.49 | 40.60
Beam-batch-level | 51.77 | 58.80 | 42.91 | 19.46 | 43.24
Sentence-level | 51.86 | 58.68 | 43.44 | 19.79 | 43.44
Table 2: BLEU scores on the multi-domains test set, for a batch size of 8,
with $c=6$ and $i=6$.

The results reported in Table 2 show that using a neighbors’ cache leads to
substantially better BLEU scores. We can also see that having a beam-batch-
level cache improves the BLEU score and that keeping the tokens from the
previous retrieved chunks in the neighbors’ cache further improves the
translation quality.

####  4.1.4 When to perform retrieval?

| Medical | Law | IT | Koran | Average
---|---|---|---|---|---
$i=6$ | 51.86 | 58.68 | 43.44 | 19.79 | 43.44
$i=8$ | 51.36 | 58.28 | 43.04 | 19.25 | 42.98
GP ($i_{\max}=8$) | 53.38 | 59.87 | 44.41 | 19.74 | 44.35
GP ($i_{\max}=16$) | 53.16 | 59.65 | 44.18 | 19.33 | 44.08
GP ($i_{\max}=32$) | 52.81 | 58.96 | 43.51 | 19.22 | 43.63
Table 3: BLEU scores on the multi-domains test set, for a batch size of 8. When using the geometric progression heuristic (GP) the average interval with $i_{\max}=16$ is 5.97 and with $i_{\max}=32$ is 6.85. | Medical | Law | IT | Koran | Average
---|---|---|---|---|---
$i=6$ | 374 | 328 | 398 | 441 | 385
$i=8$ | 421 | 374 | 429 | 470 | 424
GP ($i_{\max}=8$) | 354 | 307 | 358 | 405 | 356
GP ($i_{\max}=16$) | 397 | 368 | 393 | 445 | 401
GP ($i_{\max}=32$) | 436 | 423 | 418 | 481 | 440
Table 4: Decoding speed (tokens per second) on the multi-domains test set, for
a batch size of 8, with $c=i_{\max}$.

To understand how we should select the retrieval steps, we compare performing
retrieval every $i=6$ or $i=8$ steps against using the proposed geometric
progression (GP), Eq. 7, with $i_{\min}=2$ and $i_{\max}=8$, $i_{\max}=16$, or
$i_{\max}=32$, to compute the interval between retrieval steps. For this
comparison, we used the model with a sentence-level neighbors’ cache and
considered $c=i$ or $c=i_{\max}$ if using the geometric progression. We report
the BLEU scores in Table 3 and the corresponding decoding speeds in Table 4.
This comparison shows that performing retrieval steps more frequently at the
beginning of the translation, by using the the proposed geometric progression
heuristic (GP), leads to better BLEU scores while having a higher decoding
speed.

###  4.2 On-the-fly Adaptation

To understand how the chunk-based $k$NN-MT model behaves in a realistic
scenario where the data arrives in streams, we performed experiments where the
model is continuously adapted on the fly.

Figure 3: On-the-fly adaptation scheme. After the model translates an example,
a human translator (e.g., a post-editor) corrects the generated translation
which is added to the fine-tuning data or the domain-specific datastore. We
use the references to simulate human translations.

Figure 4: Analysis of the on-the-fly adaptation experiments on the medical
domain. Top left: BLEU scores measured every 4,000 examples. Top right: Time
(in minutes) spent by each model on training / creating and updating the
datastore and the corresponding BLEU score. Bottom left: Inference time (in
minutes) spent by each model to translate the whole set of examples and its
BLEU score. Bottom right: Total time ($\text{training}+\text{inference}$)
spent by each model to translate the set of examples and its BLEU score. For
the time plots, the lower right corner is better.

##### Task description.

In this task, we attempt to simulate a real scenario, described in Figure 3,
in which we have a model that translates sentences and a human translator
(e.g., a post-editor) who corrects the generated translations. Our goal is to
understand whether it is better to use the corrected translations to
repeatedly fine-tune the base model or to add the corrected translations to
the datastore without touching the base model. To do so, we consider that,
before starting translation, we have access to 10% of the dataset (we use the
training sets of the medical and law domains) and the goal is to translate the
remaining 90% examples. To simulate the existence of human translators who
correct the generated translations, we consider that, after the model
translates a block of sentences, it has access to the corresponding reference
sentences.

##### Models.

As baselines, we use the base MT model and the base model fine-tuned on the
initially available 10% of data (fine-tune (once)). We also compare fine-
tuning the base model on the initially available data and then finetuning
after every 32,000 and every 64,000 examples, with all the available data at
the time. In all cases, we fine-tuned the model for a maximum of 5 epochs with
a learning rate of $5\times 10^{-5}$ using the inverse square root scheduler.
Concerning the semi-parametric models, we compare the $k$NN-MT model and the
chunk-based $k$NN-MT model, building the initial datastore with the initially
available data and adding new examples to the datastore after every 250 or
1,000 sentences. We used the same configurations for the chunk-based $k$NN-MT
model, as in §4.1: chunks of size $c=16$, sentence-level neighbors’ cache, and
the geometric progression heuristic to select when to perform retrieval, with
$i_{\min}=2$ and $i_{\max}=16$. We also use the same hyperparameters, stated
on Table 10 of App. D.

####  4.2.1 Results

Figure 4 contains the results of the on-the-fly adaptation experiments on the
medical domain. On the top left plot, we see that both the $k$NN-MT and the
chunk-based $k$NN-MT lead to higher BLEU scores than the fine-tuned models.
Also, on the top right, we see that the time needed to add examples to the
datastore is much shorter than the time needed to fine-tune the model. This
comes at the cost of a higher inference time (bottom left). However, we can
see that the chunk-based $k$NN-MT model is able to substantially reduce the
inference time gap to the fully-parametric models. Also, the bottom right plot
shows that the chunk-based $k$NN-MT has a shorter total time than $k$NN-MT and
the models fine-tuned every 32,000 and 64,000 steps. Concerning the fine-tuned
models, there is a BLEU increase when the model is fine-tuned more often.
However, this leads to a substantially higher training time. On the other
hand, increasing the datastore updates frequency leads to small BLEU
improvements and small increases in training time. The results on the law
domain show similar results (App. E).

##  5 Related Work

##### Semi-parametric models.

Semi-parametric models, which augment a parametric model with a retrieval
component, have been shown to be effective on several text generation tasks.
For language modeling, Khandelwal et al. (2019) proposed the $k$-nearest
neighbor language ($k$NN-LM), in which a language model is augmented with
token-based retrieval and uses probability interpolation to incorporate these
tokens. Yogatama et al. (2021) proposed to integrate the retrieved tokens with
a gating mechanism. Borgeaud et al. (2021) proposed to retrieve chunks of
tokens and incorporate them with cross-attention, using datastores with
trillions of tokens. To increase the $k$NN-LM’s decoding speed, He et al.
(2021) proposed a range of techniques, such as datastore pruning, dimension
reduction, and adaptive retrieval. Alon et al. (2022) proposed adding pointers
to the next token on the original corpus to the datastore entries, so that the
model can consider the pointed entries instead of performing retrieval.
Similarly to our approach, this saves retrieval steps by leveraging the
original corpus sequences, but in our case, we do not limit the candidate
tokens to be the following ones and consider the succeeding tokens even if the
model has not generated the same prefix token(s).

For machine translation, Gu et al. (2018) introduced a semi-parametric model
which uses an out-of-the-box search engine to retrieve similar sentence pairs,
and incorporate them with shallow and deep fusion. Zhang et al. (2018)
proposed to retrieve $n$-grams and use them to up-weight token probabilities.
Bapna and Firat (2019a) proposed to retrieve sentences similar to the source’s
$n$-grams, and incorporate them with attention. More recently, Khandelwal et
al. (2021) proposed the $k$NN-MT model which Zheng et al. (2021a) extended
with a network that determines the number of retrieved tokens to consider and
Zheng et al. (2021b) proposed building the datastore using monolingual
sentences. As $k$NN-MT can be up to two orders of magnitude slower than a
fully-parametric model, methods that improve its efficiency have been
proposed. Meng et al. (2021) and Wang et al. (2021) proposed the Fast and
Faster $k$NN-MT, in which the model has a higher decoding speed, by creating a
different datastore, based on the source sentence, for each example. Martins
et al. (2022) propose efficient $k$NN-MT, which we use as baseline (§4.1), by
adapting the methods introduced by He et al. (2021) to machine translation and
introducing a retrieval distributions cache to speed-up decoding. In this
paper, we show that the chunk-based $k$NN-MT model can further speed-up
decoding, by retrieving chunks of tokens instead of a single token.

Semi-parametric models have also been applied to other tasks as question
answering (Lewis et al., 2020; Izacard and Grave, 2021a, b) and dialogue
generation (Weston et al., 2014; Fan et al., 2021).

##### Domain adaptation for machine translation.

Domain adaptation consists of adapting generic models to domain-specific data.
The most common method for domain adaptation in machine translation is fine-
tuning the model on each domain, but this can be expensive and often leads to
catastrophic forgetting (Saunders, 2021). To simplify this, some work has
proposed fine-tuning only part of the model (Wuebker et al., 2018; Bapna and
Firat, 2019b; Lin et al., 2021; Liang et al., 2021). Farajian et al. (2017)
performed on-the-fly adaptation, by fine-tuning the model on a set of
retrieved examples for each source sentence. However, this still requires
fine-tuning model parameters.

Several works have introduced domain adaptation methods without the need to
fine-tune the model. Eidelman et al. (2012), Hasler et al. (2014), and Su et
al. (2015) proposed using topic models while Bertoldi et al. (2014) proposed
leveraging post-editing information. More recently, Khandelwal et al. (2021)
proposed using semi-parametric models which retrieve from domain-specific
datastores. The aim of our chunk-based $k$NN-MT method is to speed up $k$NN-
MT’s decoding, while maintaining its high translation quality.

##  6 Conclusions

In this paper, we propose a chunk-based $k$NN-MT model, which retrieves chunks
of tokens from a datastore, instead of a single token. To do so, we proposed
several alternatives to explore the retrieved chunks’ tokens: keeping the
original order or building a neighbors’ cache. We also analyzed two approaches
to select the retrieval steps: every $i$ steps or using a geometric
progression heuristic to define the interval between retrieval steps. Through
experiments on domain adaptation, we showed that chunk-based $k$NN-MT leads to
a considerable speed-up without substantially compromising the translation
quality. Experiments on on-the-fly adaptation showed that chunk-based $k$NN-MT
leads to high quality translations while being more efficient than previously
proposed methods.

## Limitations

The scope of this paper is limited to the usage of small to medium size
datastores, due to the memory requirements needed for big size datastores, for
which the proposed model could be even more beneficial. Additionally, we use
the decoding speed (tokens per second), training time (in minutes), and
inference time (in minutes) to compare the efficiency of the different models.
However, these metrics depend on the computational infrastructure used, and,
consequently, the speed-up gains can vary when using different hardware.

## Acknowledgments

This work was supported by the European Research Council (ERC StG DeepSPIN
758969), by EU’s Horizon Europe Research and Innovation Actions (UTTER,
contract 101070631), by the P2020 project MAIA (contract 045909), by the
Fundação para a Ciência e Tecnologia through project PTDC/CCI-INF/4703/2021
(PRELUNA), contract UIDB/50008/2020, and by contract PD/BD/150633/2020 in the
scope of the Doctoral Program FCT - PD/00140/2013 NETSyS. We thank Chris Dyer,
Lei Yu, the SARDINE team members, and the reviewers for helpful discussion and
feedback.

## References

  * Aharoni and Goldberg (2020) Roee Aharoni and Yoav Goldberg. 2020.  Unsupervised domain clusters in pretrained language models.  In _Proc. ACL_.
  * Alon et al. (2022) Uri Alon, Frank F Xu, Junxian He, Sudipta Sengupta, Dan Roth, and Graham Neubig. 2022.  Neuro-Symbolic Language Modeling with Automaton-augmented Retrieval.  In _Proc. ICML_.
  * Bahdanau et al. (2015) Dzmitry Bahdanau, Kyung Hyun Cho, and Yoshua Bengio. 2015.  Neural machine translation by jointly learning to align and translate.  In _Proc. ICLR_.
  * Bapna and Firat (2019a) Ankur Bapna and Orhan Firat. 2019a.  Non-Parametric Adaptation for Neural Machine Translation.  In _Proc. NAACL_.
  * Bapna and Firat (2019b) Ankur Bapna and Orhan Firat. 2019b.  Simple, Scalable Adaptation for Neural Machine Translation.  In _Proc. EMNLP-IJCNLP_.
  * Bertoldi et al. (2014) Nicola Bertoldi, Patrick Simianer, Mauro Cettolo, Katharina Wäschle, Marcello Federico, and Stefan Riezler. 2014.  Online adaptation to post-edits for phrase-based statistical machine translation.  _Machine Translation_.
  * Borgeaud et al. (2021) Sebastian Borgeaud, Arthur Mensch, Jordan Hoffmann, Trevor Cai, Eliza Rutherford, Katie Millican, George van den Driessche, Jean-Baptiste Lespiau, Bogdan Damoc, Aidan Clark, et al. 2021.  Improving language models by retrieving from trillions of tokens.  _arXiv preprint_.
  * Eidelman et al. (2012) Vladimir Eidelman, Jordan Boyd-Graber, and Philip Resnik. 2012.  Topic models for dynamic translation model adaptation.  In _Proc. ACL_.
  * Fan et al. (2021) Angela Fan, Claire Gardent, Chloé Braud, and Antoine Bordes. 2021.  Augmenting Transformers with KNN-Based Composite Memory for Dialog.  _Transactions of the Association for Computational Linguistics_.
  * Farajian et al. (2017) M Amin Farajian, Marco Turchi, Matteo Negri, and Marcello Federico. 2017.  Multi-domain neural machine translation through unsupervised adaptation.  In _Proc. Second Conference on Machine Translation_.
  * Gu et al. (2018) Jiatao Gu, Yong Wang, Kyunghyun Cho, and Victor OK Li. 2018.  Search engine guided neural machine translation.  In _Proc. AAAI_.
  * Hasler et al. (2014) Eva Hasler, Phil Blunsom, Philipp Koehn, and Barry Haddow. 2014.  Dynamic topic adaptation for phrase-based mt.  In _Proc. EACL_.
  * He et al. (2021) Junxian He, Graham Neubig, and Taylor Berg-Kirkpatrick. 2021.  Efficient Nearest Neighbor Language Models.  In _Proc. EMNLP_.
  * Izacard and Grave (2021a) Gautier Izacard and Edouard Grave. 2021a.  Leveraging Passage Retrieval with Generative Models for Open Domain Question Answering.  In _Proc. EACL_.
  * Izacard and Grave (2021b) Gautier Izacard and Edouard Grave. 2021b.  Distilling Knowledge from Reader to Retriever for Question Answering.  In _Proc. ICLR_.
  * Jiang et al. (2021) Qingnan Jiang, Mingxuan Wang, Jun Cao, Shanbo Cheng, Shujian Huang, and Lei Li. 2021\.  Learning Kernel-Smoothed Machine Translation with Retrieved Examples.  In _Proc. EMNLP_.
  * Johnson et al. (2019) Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2019.  Billion-scale similarity search with gpus.  _IEEE Transactions on Big Data_.
  * Khandelwal et al. (2021) Urvashi Khandelwal, Angela Fan, Dan Jurafsky, Luke Zettlemoyer, and Mike Lewis. 2021\.  Nearest neighbor machine translation.  In _Proc. ICLR_.
  * Khandelwal et al. (2019) Urvashi Khandelwal, Omer Levy, Dan Jurafsky, Luke Zettlemoyer, and Mike Lewis. 2019\.  Generalization through Memorization: Nearest Neighbor Language Models.  In _Proc. ICLR_.
  * Koehn and Knowles (2017) Philipp Koehn and Rebecca Knowles. 2017.  Six Challenges for Neural Machine Translation.  In _Proceedings of the First Workshop on Neural Machine Translation_.
  * Lewis et al. (2020) Patrick Lewis, Ethan Perez, Aleksandara Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, et al. 2020.  Retrieval-augmented generation for knowledge-intensive nlp tasks.  In _Proc. NeurIPS_.
  * Liang et al. (2021) Jianze Liang, Chengqi Zhao, Mingxuan Wang, Xipeng Qiu, and Lei Li. 2021.  Finding Sparse Structures for Domain Specific Neural Machine Translation.  In _Proc. AAAI_.
  * Lin et al. (2021) Zehui Lin, Liwei Wu, Mingxuan Wang, and Lei Li. 2021.  Learning Language Specific Sub-network for Multilingual Machine Translation.  In _Proc. ACL_.
  * Martins et al. (2022) Pedro Henrique Martins, Zita Marinho, and André F. T. Martins. 2022.  Efficient Machine Translation Domain Adaptation.  In _Proc. ACL 2022 Workshop on Semiparametric Methods in NLP: Decoupling Logic from Knowledge_.
  * Meng et al. (2021) Yuxian Meng, Xiaoya Li, Xiayu Zheng, Fei Wu, Xiaofei Sun, Tianwei Zhang, and Jiwei Li. 2021.  Fast Nearest Neighbor Machine Translation.
  * Ng et al. (2019) Nathan Ng, Kyra Yee, Alexei Baevski, Myle Ott, Michael Auli, and Sergey Edunov. 2019\.  Facebook FAIR’s WMT19 News Translation Task Submission.  In _Proc. of the Fourth Conference on Machine Translation_.
  * Ott et al. (2019) Myle Ott, Sergey Edunov, Alexei Baevski, Angela Fan, Sam Gross, Nathan Ng, David Grangier, and Michael Auli. 2019.  fairseq: A Fast, Extensible Toolkit for Sequence Modeling.  In _Proc. NAACL (Demonstrations)_.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002.  Bleu: a method for automatic evaluation of machine translation.  In _Proc. ACL_.
  * Post (2018) Matt Post. 2018.  A Call for Clarity in Reporting BLEU Scores.  In _Proc. Third Conference on Machine Translation_.
  * Reddy (1977) Raj Reddy. 1977.  Speech understanding systems: summary of results of the five-year research effort at Carnegie-Mellon University.
  * Rei et al. (2020) Ricardo Rei, Craig Stewart, Ana C Farinha, and Alon Lavie. 2020.  COMET: A Neural Framework for MT Evaluation.  In _Proc. EMNLP_.
  * Saunders (2021) Danielle Saunders. 2021.  Domain Adaptation and Multi-Domain Adaptation for Neural Machine Translation: A Survey.
  * Su et al. (2015) Jinsong Su, Deyi Xiong, Yang Liu, Xianpei Han, Hongyu Lin, Junfeng Yao, and Min Zhang. 2015.  A context-aware topic model for statistical machine translation.  In _Proc. ACL_.
  * Sutskever et al. (2014) Ilya Sutskever, Oriol Vinyals, and Quoc V Le. 2014.  Sequence to sequence learning with neural networks.  In _Proc. NeurIPS_.
  * Tang et al. (2020) Yuqing Tang, Chau Tran, Xian Li, Peng-Jen Chen, Naman Goyal, Vishrav Chaudhary, Jiatao Gu, and Angela Fan. 2020.  Multilingual Translation with Extensible Multilingual Pretraining and Finetuning.
  * Tiedemann (2012) Jörg Tiedemann. 2012.  Parallel Data, Tools and Interfaces in OPUS.  In _Proc. LREC_.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In _Proc. NeurIPS_.
  * Wang et al. (2021) Shuhe Wang, Jiwei Li, Yuxian Meng, Rongbin Ouyang, Guoyin Wang, Xiaoya Li, Tianwei Zhang, and Shi Zong. 2021.  Faster Nearest Neighbor Machine Translation.  _arXiv preprint arXiv:2112.08152_.
  * Weston et al. (2014) Jason Weston, Sumit Chopra, and Antoine Bordes. 2014.  Memory networks.
  * Wuebker et al. (2018) Joern Wuebker, Patrick Simianer, and John DeNero. 2018.  Compact Personalized Models for Neural Machine Translation.  In _Proc. EMNLP_.
  * Yogatama et al. (2021) Dani Yogatama, Cyprien de Masson d’Autume, and Lingpeng Kong. 2021.  Adaptive Semiparametric Language Models.  _Transactions of the Association for Computational Linguistics_ , 9:362–373.
  * Zhang et al. (2018) Jingyi Zhang, Masao Utiyama, Eiichiro Sumita, Graham Neubig, and Satoshi Nakamura. 2018.  Guiding Neural Machine Translation with Retrieved Translation Pieces.  In _Proc. NAACL_.
  * Zheng et al. (2021a) Xin Zheng, Zhirui Zhang, Junliang Guo, Shujian Huang, Boxing Chen, Weihua Luo, and Jiajun Chen. 2021a.  Adaptive Nearest Neighbor Machine Translation.
  * Zheng et al. (2021b) Xin Zheng, Zhirui Zhang, Shujian Huang, Boxing Chen, Jun Xie, Weihua Luo, and Jiajun Chen. 2021b.  Non-Parametric Unsupervised Domain Adaptation for Neural Machine Translation.  In _Proc. EMNLP Findings_.

##  Appendix A Varying the Chunk Size along the Generation

When using the geometric progression to compute the interval between retrieval
steps (§3.3), the model performs retrieval more frequently at the beginning of
the generation of the translation. Because of this, we compare having a fixed
chunk size equal to the maximum interval between retrieval steps
($c=i_{\max}$) with having the chunk size vary along the generation
($c_{k}=i_{k}$). For this comparison, we compute the retrieval steps using the
geometric progression with $i_{\min}=2$ and $i_{\max}=16$, and use a sentence-
level cache.

| Medical | Law | IT | Koran | Average
---|---|---|---|---|---
$c=i_{\max}$ | 53.16 | 59.65 | 44.18 | 19.33 | 44.08
$c_{k}=i_{k}$ | 52.70 | 59.40 | 43.96 | 19.10 | 43.79
Table 5: BLEU scores on the multi-domains test set, for a batch size of 8.

The results, in Table 5, indicate that keeping the chunk size fixed leads to
slightly better translation quality.

##  Appendix B Using Different Values for $k$.

In order to understand how the number of retrieved chunks ($k$) affects the
translation quality and the decoding speed, we compare using different values
of $k$. For this comparison, we compute the retrieval steps using the
geometric progression with $i_{\min}=2$ and $i_{\max}=16$, and use a sentence-
level cache.

| Medical | Law | IT | Koran | Average
---|---|---|---|---|---
$k=2$ | 50.55 | 56.30 | 41.42 | 18.32 | 41.65
$k=4$ | 51.46 | 58.28 | 43.55 | 19.07 | 43.09
$k=8$ | 53.16 | 59.65 | 44.18 | 19.33 | 44.08
$k=16$ | 53.75 | 60.64 | 45.37 | 19.99 | 44.94
Table 6: BLEU scores on the multi-domains test set, for a batch size of 8. | Medical | Law | IT | Koran | Average
---|---|---|---|---|---
$k=2$ | 452 | 392 | 452 | 494 | 448
$k=4$ | 433 | 386 | 428 | 486 | 433
$k=8$ | 397 | 368 | 393 | 445 | 401
$k=16$ | 343 | 323 | 329 | 380 | 344
Table 7: Decoding speed (tokens per second) on the multi-domains test set, for
a batch size of 8.

We report the BLEU score and decoding speed for different values of $k$ in
Tables 6 and 7, respectively. These results show that there is a trade-off
between the translation quality and the decoding speed, when varying the
number of retrieved neighbors ($k$).

##  Appendix C Experiments on ES-FR and ET-IT.

To understand if the proposed model, chunk-based $k$NN-MT, performs well on
language pairs and datasets other than the ones used in the main experiments
(§4.1.1), we perform experiments on Spanish-French (es-fr) and Estonian-
Italian (et-it) on two datasets: EMEA and JRC-acquis (Tiedemann, 2012). For
this experiment, we used the multilingual model mBART50 (Tang et al., 2020),
compute the retrieval steps using the geometric progression with $i_{\min}=2$
and $i_{\max}=16$, and use a sentence-level cache.

| EMEA | JRC
---|---|---
| es-fr | et-it | es-fr | et-it
Base MT | 5.02 | 16.44 | 19.27 | 17.94
$k$NN-MT | 36.65 | 38.79 | 45.87 | 39.88
Chunk-based $k$NN-MT | 25.69 | 32.80 | 29.17 | 28.16
Table 8: BLEU scores on the EMEA and JRC test sets, for a batch size of 8. | EMEA | JRC
---|---|---
| es-fr | et-it | es-fr | et-it
Base MT | 189 | 214 | 189 | 205
$k$NN-MT | 37 | 37 | 26 | 27
Chunk-based $k$NN-MT | 98 | 96 | 95 | 101
Table 9: Decoding speed (tokens per second) on the EMEA and JRC test sets, for
a batch size of 8.

We report the BLEU scores and the decoding speeds (in tokens per second) on
Tables 8 and 9, respectively. As can be seen, the chunk-based $k$NN-MT model
is able to improve the translation quality considerably, when comparing with
the base MT model, while leading to a decoding speed around 3 times faster
than the vanilla $k$NN-MT model.

##  Appendix D Hyperparameters

On Table 10 we report the values for the hyperparameters of the semi-
parametric models: the interpolation coefficients
$\lambda\in\\{0.5,0.6,0.7,0.8\\}$ and $\lambda^{\prime}\in\\{0.4,0.5,0.6\\}$,
and the retrieval softmax temperatures $T$ and $T^{\prime}\in\\{1,2,3\\}$. For
decoding we use beam search with a beam size of $5$.

On Table 11 we report the values of the hyperparameters used to fine-tune the
base model on each domain: learning rate, learning rate scheduler, and whether
warmup steps were used.

| Medical | Law | IT | Koran
---|---|---|---|---
| $\lambda$ | $T$ | $\lambda^{\prime}$ |  $T^{\prime}$ | $\lambda$ | $T$ | $\lambda^{\prime}$ |  $T^{\prime}$ | $\lambda$ | $T$ | $\lambda^{\prime}$ |  $T^{\prime}$ | $\lambda$ | $T$ | $\lambda^{\prime}$ | $T^{\prime}$
$k$NN-MT | 0.7 | 10 | — | — | 0.8 | 10 | — | — | 0.7 | 10 | — | — | 0.6 | 100 | — | —
Efficient $k$NN-MT | 0.7 | 10 | — | — | 0.8 | 10 | — | — | 0.7 | 10 | — | — | 0.7 | 100 | — | —
Chunk-based $k$NN-MT | 0.7 | 10 | 0.5 | 1 | 0.8 | 10 | 0.5 | 1 | 0.7 | 10 | 0.4 | 2 | 0.8 | 100 | 0.4 | 3
Ablations |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
c=6 , i=6 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
Maintain order | 0.8 | 10 | 0.4 | — | 0.7 | 10 | 0.4 | — | 0.5 | 10 | 0.4 | — | 0.7 | 100 | 0.4 | —
Single chunk | 0.8 | 10 | 0.4 | 2 | 0.7 | 10 | 0.4 | 2 | 0.7 | 10 | 0.4 | 2 | 0.7 | 100 | 0.4 | 3
All chunks | 0.7 | 10 | 0.5 | 1 | 0.8 | 10 | 0.5 | 1 | 0.7 | 10 | 0.4 | 2 | 0.6 | 100 | 0.4 | 1
Keep previous | 0.7 | 10 | 0.5 | 1 | 0.8 | 10 | 0.5 | 1 | 0.7 | 10 | 0.4 | 1 | 0.7 | 100 | 0.4 | 3
Keep previous |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
$i=6$ | 0.7 | 10 | 0.5 | 1 | 0.8 | 10 | 0.5 | 1 | 0.7 | 10 | 0.4 | 1 | 0.7 | 100 | 0.4 | 3
$i=8$ | 0.7 | 10 | 0.4 | 1 | 0.8 | 10 | 0.5 | 1 | 0.7 | 10 | 0.4 | 1 | 0.7 | 100 | 0.4 | 3
$\exp(i_{\max}=16)$ | 0.7 | 10 | 0.5 | 1 | 0.8 | 10 | 0.5 | 1 | 0.7 | 10 | 0.4 | 2 | 0.8 | 100 | 0.4 | 3
$\exp(i_{\max}=32)$ | 0.8 | 10 | 0.5 | 1 | 0.6 | 10 | 0.5 | 1 | 0.6 | 10 | 0.4 | 1 | 0.5 | 100 | 0.4 | 1
Table 10: Values of the hyperparameters: number of neighbors to be retrieved $k$, interpolation coefficient $\lambda$, and retrieval softmax temperature $T$. Medical | Law
---|---
$\eta$ | schedule | warmup | $\eta$ | schedule | warmup
$1\times 10^{-5}$ | on plateau | no | $5\times 10^{-5}$ | inverse sqrt | yes
IT | Koran
$\eta$ | schedule | warmup | $\eta$ | schedule | warmup
$5\times 10^{-5}$ | inverse sqrt | yes | $5\times 10^{-5}$ | inverse sqrt | no
Table 11: Values of the hyperparameters for the fine-tuned model.

##  Appendix E On-the-fly Adaptation on Law Domain

We report the results of the on-the-fly adaptation experiment, on the law
domain, on Figure 5. In a similar way as in the medical domain, the top left
plot shows that the $k$NN-MT and the chunk-based $k$NN-MT models lead to
higher BLEU scores than the fine-tuned models. We can also see, on the top
right plot, that the time the models take to add examples to the datastore
along the generation is much shorter than the time needed to fine-tune the
model. This comes at the cost of a higher inference time (as shown on the
bottom left plot). However, we can see that the chunk-based $k$NN-MT model is
able to substantially reduce the inference time gap between fully-parametric
and semi-parametric models, having a shorter total time than the $k$NN-MT and
the models fine-tuned every 32,000 and 64,000 steps (bottom right plot).
Concerning the fine-tuned models, fine-tuning more often leads to a slightly
better BLEU score. However, this also leads to a substantially higher training
time.

Figure 5: Analysis of the on-the-fly adaptation experiments on the law domain.
Top left: BLEU scores measured every 4,000 examples. Top right: Time (in
minutes) spent by each model on training / creating and updating the datastore
and the corresponding BLEU score. Bottom left: Inference time (in minutes)
spent by each model to translate the whole set of examples and its BLEU score.
Bottom right: Total time ($\text{training}+\text{inference}$) spent by each
model to translate the set of examples and its BLEU score. The lower right
corner is better.

##  Appendix F Translation Examples

We report some translation examples on the medical domain in Figures 6 and 7,
on the law domain in Figure 8, and on the IT domain in Figure 9. To simplify
the examples, we use a batch size of 1 and a beam size of 1.

Figure 6: Example of translation from the medical domain. The tokens generated
at the retrieval steps are highlighted in the same color as the retrieved
chunks of tokens. These chunks of tokens are added to the neighbors’ cache,
after being retrieved. The retrieved tokens which are present in the
translation are bolded. Figure 7: Example of translation from the medical
domain. The tokens generated at the retrieval steps are highlighted in the
same color as the retrieved chunks of tokens. These chunks of tokens are added
to the neighbors’ cache, after being retrieved. The retrieved tokens which are
present in the translation are bolded. Figure 8: Example of translation from
the law domain. The tokens generated at the retrieval steps are highlighted in
the same color as the retrieved chunks of tokens. These chunks of tokens are
added to the neighbors’ cache, after being retrieved. The retrieved tokens
which are present in the translation are bolded. Figure 9: Example of
translation from the IT domain. The tokens generated at the retrieval steps
are highlighted in the same color as the retrieved chunks of tokens. These
chunks of tokens are added to the neighbors’ cache, after being retrieved. The
retrieved tokens which are present in the translation are bolded.


# Quadratic Embedding Constants of graphs: Bounds and distance spectra

Projesh Nath Choudhury  Discipline of Mathematics, Indian Institute of
Technology Gandhinagar, Palaj, Gandhinagar 382355, India
<EMAIL_ADDRESS>and  Raju Nandi  Discipline of Mathematics, Indian
Institute of Technology Gandhinagar, Palaj, Gandhinagar 382355, India
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

The quadratic embedding constant (QEC) of a finite, simple, connected graph
$G$ is the maximum of the quadratic form of the distance matrix of $G$ on the
subset of the unit sphere orthogonal to the all-ones vector. The study of
these QECs was motivated by the classical work of Schoenberg on quadratic
embedding of metric spaces [Ann. of Math., 1935] and [Trans. Amer. Math. Soc.,
1938]. In this article, we provide sharp upper and lower bounds for the QEC of
trees. We next explore the relation between distance spectra and quadratic
embedding constants of graphs – and show two further results: $(i)$ We show
that the quadratic embedding constant of a graph is zero if and only if its
second largest distance eigenvalue is zero. $(ii)$ We identify a new subclass
of nonsingular graphs whose QEC is the second largest distance eigenvalue.
Finally, we show that the QEC of the cluster of an arbitrary graph $G$ with
either a complete or star graph can be computed in terms of the QEC of $G$. As
an application of this result, we provide new families of examples of graphs
of QE class.

###### Key words and phrases:

Distance matrix, distance spectra of graphs, euclidean distance geometry,
quadratic embedding constant, tree, double star, cluster of graphs

###### 2020 Mathematics Subject Classification:

05C12 (primary); 05C50, 05C76 (secondary)

##  1\. Introduction and main results

Throughout this paper, all graphs are assumed to be finite, simple, connected,
and unweighted. Given a graph $G=(V,E)$, we define $C(V):$ the space of all
$\mathbb{R}$-valued functions on $V$, $e:$ the constant function in $C(V)$
taking value $1$, and $J:$ matrix with all entries one. The canonical inner
product on $C(V)\cong\mathbb{R}^{|V|}$ will be denoted by $\langle.,.\rangle$.
Also, given a graph $G$ with vertex set $V$, $D_{G}$ denotes its distance
matrix, with the $(v,w)$ entry given by the length of a shortest path
connecting $v\neq w\in V$, and $(D_{G})_{vv}=0\ \forall v\in V$. The
eigenvalues of $D_{G}$ are arranged as
$\lambda_{1}(G)>\lambda_{2}(G)\geq\lambda_{3}(G)\geq\cdots\geq\lambda_{|V|}(G).$

The aim of this work is to study a graph-theoretic constant arising from
Euclidean distance geometry. A well-studied problem in distance geometry asks
whether given a graph $G=(V,E)$ there exists a function $\psi$ from $V$ into a
Euclidean space $\mathcal{H}$ such that $d(i,j)=\
\parallel\psi(i)-\psi(j)\parallel^{2}$ for all $i,j\in V$, where
$\parallel.\parallel$ denotes the norm of $\mathcal{H}$. Such a map
$\psi:V\rightarrow\mathcal{H}$ is called a quadratic embedding  of $G$ and if
$G$ admits a quadratic embedding, we say that $G$ is of QE class. Graphs of QE
class have rich applications in quantum probability and non-commutative
harmonic analysis [4, 5, 6, 8, 9, 15, 16]. In [19], Schoenberg showed a
striking characterization of the $QE$ class:

######  Theorem 1.1.

Let $G=(V,E)$ be a graph with at least two vertices. Then $G$ is of QE class
if and only if $D_{G}$ is conditionally negative definite, that is $\langle
f,D_{G}f\rangle\leq 0$ for all $f\in C(V)$ with $\langle e,f\rangle=0$.

Motivated by Schoenberg’s result, the authors in [17] introduced the notion of
quadratic embedding constant of $G$ denoted and defined as

$\operatorname{QEC}(G):=\max\\{\langle f,D_{G}f\rangle;\ f\in C(V),\ \langle
f,f\rangle=1,\ \langle e,f\rangle=0\\}.$

In particular, Schoenberg’s result says a graph $G$ is of QE class if and only
if $\operatorname{QEC}(G)\leq 0$. $\operatorname{QEC}(G)$ has since been
studied by several authors [3, 11, 12, 13, 17]. For instance, the quadratic
embedding constants of $K_{n}$, $C_{n}$ and complete multipartite graphs are
given in [14, 17]. E.g., $\operatorname{QEC}(K_{m,m})=m-2$; in particular
$K_{m,m}$ is not of QE class for $m\geq 3$.

We now consider trees. For a path graph $P_{n}$ on $n$ vertices, the authors
in [13] derived a lower and upper bound for $\operatorname{QEC}(P_{n})$.
Młotkowski [12] recently extended this work by providing the exact value:
$\operatorname{QEC}(P_{n})=\frac{-1}{1+\cos(\pi/n)}$. In [17], authors studied
quadratic embedding of graphs and proved that any tree $T$ is of QE class.
Also, from [12, 17],
$\operatorname{QEC}(P_{n})<\operatorname{QEC}(K_{1,n-1})=-2/n$, for $n\geq 4$.
Now our first main result shows that the quadratic embedding constants of any
tree on $n\geq 4$ vertices lies between $\operatorname{QEC}(P_{n})$ and
$\operatorname{QEC}(K_{1,n-1})$.

######  Theorem 1.2.

Let $T_{n}$ be a tree on $n\geq 4$ vertices. Then
$\operatorname{QEC}(P_{n})\leq\operatorname{QEC}(T_{n})\leq\operatorname{QEC}(K_{1,n-1})$.
Moreover, the left side equality holds if and only if $T_{n}=P_{n}$ while the
right hand equality holds if and only if $T_{n}=K_{1,{n-1}}$.

######  Remark 1.3.

In [13], the authors showed that for any tree $T_{n}$ on $n\geq 3$ vertices

$\operatorname{QEC}(T_{n})\leq-\frac{2}{2n-3},$ (1.1)

and this inequality is strict for $n=4,5$ (see [17, Section 5]). A natural
problem, which is mentioned in [3], is to find tight upper and lower bound for
$\operatorname{QEC}(T_{n})$, where $T_{n}$ runs over all trees with $n$
vertices. By [17, Theorem 2.8],
$\operatorname{QEC}(K_{1,n-1})=-\frac{2}{n}<-\frac{2}{2n-3}$. Hence our first
main result answers this question.

An interesting topic in spectral graph theory is exploring the relation
between distance spectra and the quadratic embedding constants of graphs. The
distance matrix of a connected graph is an irreducible, nonnegative, symmetric
matrix. By the Perron–Frobenius Theorem, its largest eigenvalue is simple. By
the min–max principle for eigenvalues of symmetric matrices [10, Theorem
4.2.6],

$\lambda_{2}(G)\leq\operatorname{QEC}(G)<\lambda_{1}(G).$ (1.2)

This leads us to a natural question that has been pursued in the literature:
Characterize the family of graphs that satisfy $\lambda_{2}(G)=QEC(G)$. It is
well known that this equality holds for distance regular graphs and
transmission regular graphs [3]. In [17], the author showed that
$\lambda_{2}(G)=QEC(G)$ holds for path graphs with an even number of vertices.
In this article, we show that this holds for unicyclic graphs with an even
cycle, cacti with at least one even cycle, linear hexagonal chains and wheel
graphs with odd vertices. In fact, we prove a stronger result:

######  Theorem 1.4.

Let $G$ be a graph on $n\geq 2$ vertices. Then $\lambda_{2}(G)=0$ if and only
if $\operatorname{QEC}(G)=0$.

######  Remark 1.5.

By the above theorem, any graph $G$ with the property that either the second
largest distance eigenvalue is zero or $\operatorname{QEC}(G)=0$, satisfies
$\lambda_{2}(G)=\operatorname{QEC}(G)=0$. Unicyclic graphs with an even cycle,
cacti with at least one even cycle, linear hexagonal chains, and a plethora of
other graphs in [1] have the second largest eigenvalue zero. Hence, for all
those graph classes, $\operatorname{QEC}(G)$ is the second largest eigenvalue
of $D_{G}$.

In 1977, Graham–Pollak [7] proved that $D_{T}$ for any tree $T$ is nonsingular
and $\det(D_{T})$ depends only on the number of vertices of $T$. Thus, a path
graph with even number of vertices provides an example of a graph with a
nonsingular distance matrix and the quadratic embedding constant as a distance
eigenvalue. Our next main result gives a new subclass of trees with the
quadratic embedding constant as the second largest distance eigenvalue.

######  Theorem 1.6.

Let $S_{n,n}$ be a double star graph (see Definition 3.3). Then

$\operatorname{QEC}(S_{n,n})=\lambda_{2}(S_{n,n})=\frac{-(n+2)+\sqrt{(n+2)^{2}-8}}{2}.$

Moreover, in the definition of $\operatorname{QEC}(S_{n,n})$, the maximum is
attained at a vector $f\in\mathbb{R}^{2n}$ of the form $\frac{g}{\parallel
g\parallel}$, where

$g=\begin{pmatrix}\ \ y\\\ -y\\\
\end{pmatrix},~{}y\in\mathbb{R}^{n}\hbox{~{}~{}~{}and~{}~{}~{}}y_{i}=\left\\{\begin{array}[]{cl}\frac{n+\sqrt{(n+2)^{2}-8}}{2},&\mbox{if
}i=1,\\\ -1,&\mbox{otherwise.}\end{array}\right.$ (1.3)

We, now turn our focus to investigating the quadratic embedding constant of
$G$ using graph operations. It can be challenging to determine the quadratic
embedding constant of a graph sometimes, but if we factorize the given $G$
into smaller graphs whose quadratic embedding constants are known,
$\operatorname{QEC}(G)$ can then be represented in terms of the quadratic
embedding constant of the smaller graphs. Thus, a natural question arises: Can
the quadratic embedding constant of $G=G_{1}\\#G_{2}$ be computed using
$\operatorname{QEC}(G_{1})$ and $\operatorname{QEC}(G_{2})$, where $\\#$
denotes some graph operation? The quadratic embedding constant of $G$ using
several graph operations, e.g., Cartesian product [17], star product [3, 13],
lexicographic product and joining [11] of graphs studied in the literature. In
this article, we study the cluster $G_{1}\\{G_{2}\\}$ of two simple, connected
graphs $G_{1}$ and $G_{2}$ (See Definition 4.1). Our final result provides
$\operatorname{QEC}(G\\{K_{n}\\})$ and
$\operatorname{QEC}(G\\{K_{1,{n-1}}\\})$, in terms of the quadratic embedding
constant of the base graph $G$.

######  Theorem 1.7.

Let $n\geq 2$ be an integer and $G$ be an arbitrary graph. Then

  * (i)

For a complete graph $K_{n}$ on $n\geq 2$ vertices

$\operatorname{QEC}(G\\{K_{n}\\})=\frac{(n\operatorname{QEC}(G)-n)+\sqrt{(n\operatorname{QEC}(G)-n)^{2}+4n\operatorname{QEC}(G)}}{2}.$

  * (ii)

For a star graph $K_{1,n-1}$ on $n\geq 2$ vertices

$\operatorname{QEC}(G\\{K_{1,n-1}\\})=\frac{(n\operatorname{QEC}(G)-2)+\sqrt{(n\operatorname{QEC}(G)-2)^{2}+8\operatorname{QEC}(G)}}{2}.$

As applications of this result: (a) We generate new families of examples of
graphs of QE class. (b) We obtain the quadratic embedding constant of a simple
corona graph.

Organization of the paper: The remaining sections are devoted to proving our
main results above. In section 2, we recall the quadratic embedding constants
of a complete bipartite graph and of the star product of graphs, and prove
Theorem 1.2. In section 3, we prove Theorems 1.4 and 1.6. We also provide a
formula for the quadratic embedding constant of a general double star tree
$S_{m,n}$ – see Theorem 3.6. In the final section, we prove Theorem 1.7,
followed by several applications.

##  2\. Sharp bound for the Quadratic Embedding Constant of Trees

We begin by proving Theorem 1.2: for any tree $T_{n}$ on $n$ vertices,
$\operatorname{QEC}(T_{n})$ lies between $\operatorname{QEC}(P_{n})$ and
$\operatorname{QEC}(K_{1,{n-1}})$. The proof requires a couple of preliminary
results; the first gives the quadratic embedding constant of complete
bipartite graphs.

######  Theorem 2.1.

[17, Theorem 2.8] Let $K_{m,n}$ be a complete bipartite graph on $(m+n)$
vertices. Then

$\operatorname{QEC}(K_{m,n})=\frac{2(mn-m-n)}{m+n}$ for all $m\geq 1$, $n\geq
1$.

In particular, for a star graph $K_{1,n-1}$ on $n$ vertices,
$\operatorname{QEC}(K_{1,n-1})=-\frac{2}{n}$.

The next result concerns the quadratic embedding constant of the star product
of two graphs. Recall that the star product of $G_{1}=(V_{1},E_{1})$ and
$G_{2}=(V_{2},E_{2})$ with respect to distinguished vertices $\sigma_{1}\in
V_{1}$ and $\sigma_{2}\in V_{2}$ is also called their coalescence, is denoted
by $G_{1}\star G_{2}$ and is obtained by joining $G_{1}$ and $G_{2}$ at the
vertices $\sigma_{1}$ and $\sigma_{2}$.

######  Proposition 2.2.

[13, Proposition 4.3] Let $G_{1}$ and $G_{2}$ be two graphs on $n_{1}+1$ and
$n_{2}+1$ vertices with $Q_{1}=\operatorname{QEC}(G_{1})$ and
$Q_{2}=\operatorname{QEC}(G_{2})$ respectively. Let
$M=M(n_{1},n_{2};-Q_{1},-Q_{2})$ be the conditional infimum of

$\Phi(\alpha,x^{1},x^{2})=\sum_{i=1}^{2}(-Q_{i})\\{\langle
x^{i},x^{i}\rangle+\langle e,x^{i}\rangle^{2}\\},\ \ \ \ \ \
\alpha\in\mathbb{R},\ \ x^{i}\in\mathbb{R}^{n_{i}},$

subject to

$\alpha^{2}+\sum_{i=1}^{2}\langle x^{i},x^{i}\rangle=1\ \ \ and\ \ \
\alpha+\sum_{i=1}^{2}\langle e,x^{i}\rangle=0.$

Then, $\operatorname{QEC}(G_{1}\star G_{2})\leq-M$.

The third preliminary result establishes a relationship between the quadratic
embedding constants of a graph and its subgraphs.

######  Theorem 2.3.

[17, Theorem 3.1] Let $G$ be a connected graph and $H$ be a connected subgraph
of $G$. If $H$ is isometrically embedded in $G$, then
$\operatorname{QEC}(H)\leq\operatorname{QEC}(G)$.

With these preliminaries at hand, our first main result follows.

###### Proof of Theorem 1.2.

First, we prove the left inequality –
$\operatorname{QEC}(P_{n})\leq\operatorname{QEC}(T_{n})$. Suppose $T_{n}$ is a
tree other than the path graph $P_{n}$. Then $T_{n}$ has a vertex that is
adjacent to at least three vertices, and the graph induced by them is a
subtree $K_{1,3}$ that is isometrically embedded in $T_{n}$. By Theorems 2.1
and 2.3,

$-\frac{1}{2}=\operatorname{QEC}(K_{1,3})\leq\operatorname{QEC}(T_{n}).$ (2.1)

Also, from [3, Section 4], we have

$\operatorname{QEC}(P_{2})<QEC(P_{3})<\cdots<\operatorname{QEC}(P_{n})<\operatorname{QEC}(P_{n+1})<\cdots\longrightarrow-\frac{1}{2}.$
(2.2)

From equation (2.1) and (2.2), we have
$\operatorname{QEC}(P_{n})<\operatorname{QEC}(T_{n})$.

Now, we prove the right inequality. Let $T_{n}$ be a tree with $n$ vertices
distinct from the star graph $K_{1,{n-1}}$. We claim that
$\operatorname{QEC}(T_{n})<\operatorname{QEC}(K_{1,n-1})$. We prove this by
induction on $n\geq 4$. In the base case, the only tree other than the star
$K_{1,3}$ on 4 vertices is $P_{4}$ and
$\operatorname{QEC}(P_{4})<-\frac{1}{2}=\operatorname{QEC}(K_{1,3})$. For the
induction step, let $T_{r+1}$ be a tree on $(r+1)$ vertices other than
$K_{1,r}$, with $r\geq 4$. Then $T_{r+1}$ has a pendant vertex $v$ such that
the tree $T_{r+1}-v=T_{r}$ is different from the star graph $K_{1,{r-1}}$.
Note that $T_{r+1}=K_{2}\star T_{r}$. By the induction hypothesis,

$\operatorname{QEC}(T_{r})<\operatorname{QEC}(K_{1,r-1})=-\frac{2}{r}.$ (2.3)

Note that $\operatorname{QEC}(K_{2})=-1$. By Proposition 2.2,

$\operatorname{QEC}(T_{r+1})=\operatorname{QEC}(K_{2}\star
T_{r})\leq-M(1,r-1;1,-\operatorname{QEC}(T_{r})).$ (2.4)

Since $-\operatorname{QEC}(T_{r})>\frac{2}{r}$, by [13, Theorem 3.5 and
Proposition 2.3],

$M(1,r-1;1,\frac{2}{r})<M(1,r-1;1,-\operatorname{QEC}(T_{r})).$ (2.5)

By [13, Theorem 3.5], $M(1,r-1;1,\frac{2}{r})$ is the minimal solution of

$\frac{1}{1\cdot
1+1-\lambda}+\frac{r-1}{\frac{2}{r}\cdot(r-1)+\frac{2}{r}-\lambda}=\frac{1}{\lambda},$

and a straightforward calculation shows that
$M(1,r-1;1,\frac{2}{r})=\lambda=\frac{2}{r+1}$. Using (2.4) and (2.5), we get

$\operatorname{QEC}(T_{r+1})<-M(1,r-1;1,\frac{2}{r})=-\frac{2}{r+1}=\operatorname{QEC}(K_{1,r})$.

This completes the induction step. ∎

##  3\. Quadratic Embedding Constants and distance spectra of graphs

We next prove Theorem 1.4. The proof employs the following preliminary result
that computes the quadratic embedding constant using Lagrange multipliers.

######  Proposition 3.1.

[17, Proposition 4.1] Let $G=(V,E)$ be a graph on $n\geq 3$ vertices.
Identifying $C(V)$ with $\mathbb{R}^{n}$, let $\mathcal{S}(D_{G})$ be the set
of all stationary points
$(f,\lambda,\mu)\in\mathbb{R}^{n}\times\mathbb{R}\times\mathbb{R}$ of

$\phi(f,\lambda,\mu)=\langle f,D_{G}f\rangle-\lambda(\langle
f,f\rangle-1)-\mu\langle e,f\rangle,$

or equivalently,
$(f,\lambda,\mu)\in\mathbb{R}^{n}\times\mathbb{R}\times\mathbb{R}$ satisfying
the system of the following three equations

$(D_{G}-\lambda I)f=\frac{\mu}{2}\ e$, $\langle f,f\rangle=1$ and $\langle
e,f\rangle=0.$

Then $\mathcal{S}(D_{G})$ is nonempty and

$\operatorname{QEC}(G)=\max\\{\lambda:(f,\lambda,\mu)\in\mathcal{S}(D_{G})\\}$.

###### Proof of Theorem 1.4.

Suppose that $\operatorname{QEC}(G)=0$. Then $\lambda_{2}(G)\leq 0$ by (1.2).
We claim that $\lambda_{2}(G)=0$. Indeed, suppose $\lambda_{2}(G)\neq 0$. Then
$D_{G}$ is a nonsingular matrix by (1.2). By Proposition 3.1, there exist
$f\in\mathbb{R}^{n}$ and $\mu\in\mathbb{R}$ such that

$(D_{G}-0\cdot I)f=\frac{\mu}{2}\ e$, $\langle f,f\rangle=1$ and $\langle
e,f\rangle=0$.

Since $D_{G}$ is nonsingular, $f=\frac{\mu}{2}D_{G}^{-1}e$ and
$\frac{\mu^{2}}{4}\langle D_{G}^{-1}e,D_{G}^{-1}e\rangle=1$. Thus

$\mu\neq 0~{}~{}~{}\mbox{and}~{}~{}~{}\langle e,D_{G}^{-1}e\rangle=0.$ (3.1)

By [2, Lemma 8.3] and using (3.1), we have $\det(D_{G}+J)=\det(D_{G})$. Let
$\beta_{1}\geq\cdots\geq\beta_{n}$ be the eigenvalues of $D_{G}+J$. Since
$D_{G}$ is symmetric, by [10, Corollary 4.3.12], $\lambda_{i}(G)\leq\beta_{i}$
for all $1\leq i\leq n$. Let $x>0$ be the Perron vector of $D_{G}$. By the
Perron–Frobenius Theorem, any eigenvector corresponding to $\lambda_{1}(G)$ is
a constant multiple of $x$. Let $y$ be an arbitrary eigenvector corresponding
to $\lambda_{1}(G)$. Then

$D_{G}y=\lambda_{1}(G)y~{}~{}~{}~{}~{}~{}\mbox{~{}~{}~{}~{}~{}and~{}~{}~{}~{}~{}}~{}~{}~{}~{}~{}\sum_{i=1}^{n}y_{i}\neq
0.$

Since $Jy\neq 0$, again by [10, Corollary 4.3.12], $\lambda_{1}(G)<\beta_{1}$.
Thus

$\det(D_{G})=\prod_{i=1}^{n}\lambda_{i}(G)\neq\prod_{i=1}^{n}\beta_{i}=\det(D_{G}+J),$

a contradiction. Hence $\lambda_{2}(G)$ must be zero.

To prove the converse, let $\lambda_{2}(G)=0$. Then $\operatorname{QEC}(G)\geq
0$. If $\operatorname{QEC}(G)=0$, then we are done. Suppose that
$\operatorname{QEC}(G)>0$. Since
$0=\lambda_{2}(G)<\operatorname{QEC}(G)<\lambda_{1}(G)$, the matrix
$D_{G}-\operatorname{QEC}(G)I$ is invertible. Again, by Proposition 3.1, there
exist $f\in\mathbb{R}^{n}$ and $\mu\in\mathbb{R}$ such that

$(D_{G}-\operatorname{QEC}(G)I)f=\frac{\mu}{2}\ e$, $\langle f,f\rangle=1$ and
$\langle e,f\rangle=0,$

and so
$\det(D_{G}-\operatorname{QEC}(G)I+J)=\det(D_{G}-\operatorname{QEC}(G)I)$. The
same argument can be adapted, as in the first half of the proof, to show that
$\lambda_{i}(G)\leq\beta_{i}$ for all $2\leq i\leq n$ and
$\lambda_{1}(G)<\beta_{1}$. Hence

$\det(D_{G}-\operatorname{QEC}(G)I)=\prod_{i=1}^{n}(\lambda_{i}(G)-\operatorname{QEC}(G))\neq\prod_{i=1}^{n}(\beta_{i}-\operatorname{QEC}(G))=\det(D_{G}-\operatorname{QEC}(G)I+J),$

a contradiction. Thus $\operatorname{QEC}(G)=0$. ∎

As a consequence, we characterize all singular graphs of QE class.

######  Corollary 3.2.

Let $G$ be a graph of QE class. Then $D_{G}$ is singular if and only if
$\operatorname{QEC}(G)=0$.

###### Proof.

Suppose that $G$ is a graph of QE class. By Schoenberg’s Theorem 1.1,
$\operatorname{QEC}(G)\leq 0$. Since
$\lambda_{2}(G)\leq\operatorname{QEC}(G)<\lambda_{1}(G)$, $\det(D_{G})=0$ if
and only if $\lambda_{2}(G)=0$. Hence the result follows by Theorem 1.4. ∎

Next, we will look at graphs with nonsingular distance matrices. In general,
the quadratic embedding constant is not a distance eigenvalue for every graph
with a nonsingular distance matrix, e.g., complete bipartite graphs $K_{m,n}$
($m\neq n$), path graphs with an odd number of vertices, star graphs, etc. In
Theorem 1.6, we identify a subclass of trees, the double star graphs for which
the QEC is an eigenvalue of the distance matrix. To prove Theorem 1.6, we
first recall the definition of the double star graph.

######  Definition 3.3.

A double star graph is a tree denoted by $S_{m,n}$, obtained by adding an edge
between the center vertices of the star graphs $K_{1,m-1}$ and $K_{1,n-1}$.

######  Example 3.4.

Example of a double star graph on $8$ vertices.

$1$$4$$2$$3$$6$$7$$5$$8$ Figure 1. $S_{3,5}$

###### Proof of Theorem 1.6.

Note that $S_{n,n}=K_{2}\\{K_{1,n-1}\\}$ (see Definition 4.1). By Theorem 1.7,

$\operatorname{QEC}(S_{n,n})=\frac{-(n+2)+\sqrt{(n+2)^{2}-8}}{2}.$

Next, we show that $\operatorname{QEC}(S_{n,n})$ is an eigenvalue of
$D_{S_{n,n}}$. Let $\\{1,2,\ldots n,n+1,\ldots,2n\\}$ be the vertex set of
$S_{n,n}$ such that one $K_{1,n-1}$ is induced by $\\{1,2,\ldots,n\\}$ with
the vertex 1 as its centre and the other $K_{1,n-1}$ is induced by vertices
$\\{n+1,n+2,\ldots,2n\\}$ with the centre vertex $n+1$. Then
$D_{S_{n,n}}=\begin{pmatrix}P&Q\\\ Q&P\\\ \end{pmatrix}$, where
$P=(p_{ij}),Q=(q_{ij})\in\mathbb{R}^{n\times n}$ are two symmetric matrices of
the form

$p_{ij}=\left\\{\begin{array}[]{cl}0,&\mbox{if }i=j,\\\ 1,&\mbox{if }i=1\mbox{
and }2\leq j\leq n,\\\ 2,&\mbox{otherwise.}\end{array}\right.$ and
$q_{ij}=\left\\{\begin{array}[]{cl}1,&\mbox{if }i=j=1,\\\ 2,&\mbox{if
}i=1\mbox{ and }2\leq j\leq n,\\\ 3,&\mbox{otherwise.}\end{array}\right.$

Note that

$q_{ij}-p_{ij}=\left\\{\begin{array}[]{cl}3,&\mbox{if }i=j\mbox{ and }2\leq
i\leq n,\\\ 1,&\mbox{otherwise.}\end{array}\right.$

Define the vectors $g$ and $y$ as in (1.3). Then

$(Q-P)y=\frac{-(n+2)+\sqrt{(n+2)^{2}-8}}{2}\Big{(}-\frac{n+\sqrt{(n+2)^{2}-8}}{2},1,1,\ldots,1\Big{)}^{T}$

and

$D_{S_{n,n}}g=\begin{pmatrix}(P-Q)y\\\ (Q-P)y\\\
\end{pmatrix}=\frac{-(n+2)+\sqrt{(n+2)^{2}-8}}{2}\begin{pmatrix}\ \ y\\\ -y\\\
\end{pmatrix}=\operatorname{QEC}(S_{n,n})\ g.$

Hence $\operatorname{QEC}(S_{n,n})$ is an eigenvalue of $D_{S_{n,n}}$. Since
$\lambda_{2}(S_{n,n})\leq\operatorname{QEC}(S_{n,n})<\lambda_{1}(S_{n,n})$, we
have

$\lambda_{2}(S_{n,n})=\operatorname{QEC}(S_{n,n})\mbox{~{}~{}~{}~{}and~{}~{}~{}~{}}\left\langle\frac{g}{\parallel
g\parallel},D_{S_{n,n}}\frac{g}{\parallel
g\parallel}\right\rangle=\operatorname{QEC}(S_{n,n}).\qed$

In the last part of this section, we provide the quadratic embedding constant
of a general double star graph $S_{m,n}$. Note that
$\operatorname{QEC}(S_{m,n})$ is the maximum of $\langle
f,D_{S_{m,n}}f\rangle$ over the uncountable set of all vectors $f$ in the unit
sphere orthogonal to $e$. Our next result avoid this rout and compute
$\operatorname{QEC}(S_{m,n})$ via the largest root of a polynomial of degree
3. The proof requires a basic result that gives us a lower bound for the
quadratic embedding constant of any connected graph.

######  Proposition 3.5.

[11] Let $G$ be a graph on $n$ vertices. Then, $\operatorname{QEC}(G)\geq-1$.
Moreover, equality holds if and only if $G$ is a complete graph $K_{n}$.

From the above result and Proposition 3.1, to calculate the quadratic
embedding constant of a graph that is not complete, it is sufficient to take
the maximum over $\lambda>-1$ such that $(f,\lambda,\mu)$ is a stationary
point of $\phi(f,\lambda,\mu)$.

######  Theorem 3.6.

Let $m,n\geq 1$ be integers. Then $\operatorname{QEC}(S_{m+1,n+1})=-2+2t$,
where $t$ is the largest root of the polynomial

$(m+n+2)t^{3}-(m+n+1-mn)t^{2}-2mnt+mn=0.$

###### Proof.

Let $\\{1,2,\ldots,m+1,m+2,\ldots,m+n+2\\}$ be the vertex set of $S_{m+1,n+1}$
such that $K_{1,m}$ is induced by $\\{1,2,\ldots,m,m+n+1\\}$ with the vertex
$m+n+1$ as its centre and $K_{1,n}$ is induced by vertices
$\\{m+1,m+2,\ldots,m+n,m+n+2\\}$ with the centre vertex $m+n+2$. Then, the
distance matrix of $S_{m+1,n+1}$ is an $(m+n+2)\times(m+n+2)$ matrix of the
form

$\begin{pmatrix}A&P&Q\\\ P^{T}&B&R\\\ Q^{T}&R^{T}&C\\\ \end{pmatrix}$,

where $A=2(J-I)\in\mathbb{R}^{m\times m}$, $B=2(J-I)\in\mathbb{R}^{n\times
n}$, $C=(J-I)\in\mathbb{R}^{2\times 2}$, $P=3J\in\mathbb{R}^{m\times n}$,

$Q=\begin{pmatrix}1&2\\\ 1&2\\\ \vdots&\vdots\\\ 1&2\\\
\end{pmatrix}\in\mathbb{R}^{m\times 2}$ and $R=\begin{pmatrix}2&1\\\ 2&1\\\
\vdots&\vdots\\\ 2&1\\\ \end{pmatrix}\in\mathbb{R}^{n\times 2}$.

Let $f=(x^{T},y^{T},z^{T})^{T}\in\mathbb{R}^{(m+n+2)}$, where
$x\in\mathbb{R}^{m}$, $y\in\mathbb{R}^{n}$ and $z\in\mathbb{R}^{2}$ such that
$\langle e,f\rangle=0$ and $\langle f,f\rangle=1$. Then a straightforward but
longwinded calculation shows that

$\displaystyle\langle f,D_{S_{m+1,n+1}}f\rangle$
$\displaystyle=x^{T}Ax+y^{T}By+z^{T}Cz+2x^{T}Py+2x^{T}Qz+2y^{T}Rz$
$\displaystyle=2\Big{\\{}\Big{(}\sum_{i=1}^{m}x_{i}\Big{)}^{2}-\sum_{i=1}^{m}x_{i}^{2}\Big{\\}}+2\Big{\\{}\Big{(}\sum_{j=1}^{n}y_{j}\Big{)}^{2}-\sum_{j=1}^{n}y_{j}^{2}\Big{\\}}+\Big{(}\sum_{k=1}^{2}z_{k}\Big{)}^{2}-\sum_{k=1}^{2}z_{k}^{2}$
$\displaystyle+6\Big{(}\sum_{i=1}^{m}x_{i}\Big{)}\Big{(}\sum_{j=1}^{n}y_{j}\Big{)}+2(z_{1}+2z_{2})\Big{(}\sum_{i=1}^{m}x_{i}\Big{)}+2(2z_{1}+z_{2})\Big{(}\sum_{j=1}^{n}y_{j}\Big{)}$
$\displaystyle=-2+2\Big{\\{}z_{2}^{2}-\Big{(}\sum_{i=1}^{m}x_{i}\Big{)}^{2}-2z_{1}\Big{(}\sum_{i=1}^{m}x_{i}\Big{)}\Big{\\}}.$

Let
$\Psi(x,y,z)=\Psi(x_{1},\ldots,x_{m},y_{1},\ldots,y_{n},z_{1},z_{2}):=z_{2}^{2}-\Big{(}\sum_{i=1}^{m}x_{i}\Big{)}^{2}-2z_{1}\Big{(}\sum_{i=1}^{m}x_{i}\Big{)}$.
Then there exists a symmetric matrix $M$ such that $\Psi(x,y,z)=\langle
f,Mf\rangle$. Thus

$\displaystyle\operatorname{QEC}(S_{m+1,n+1})$ $\displaystyle=\max\\{\langle
f,D_{S_{m+1,n+1}}f\rangle;\ f\in\mathbb{R}^{(m+n+2)\times(m+n+2)},\ \langle
f,f\rangle=1,\ \langle e,f\rangle=0\\}$ $\displaystyle=-2+2\ \max\\{\langle
f,Mf\rangle;\ f=(x,y,z)^{T},\ \langle f,f\rangle=1,\ \langle e,f\rangle=0\\}.$

We use the Lagrange multiplier method to solve the above maximization problem.
Set

$F(f,\lambda,\mu):=\langle f,Mf\rangle-\lambda(\langle
f,f\rangle-1)-\mu\langle e,f\rangle.$

Then all the stationary points of $F(f,\lambda,\mu)$ satisfy $(M-\lambda
I)f=\frac{\mu}{2}$, $\langle f,f\rangle=1$ and $\langle e,f\rangle=0$. Since
$K_{1,{m+1}}$ is isometrically embedded in $S_{{m+1},{n+1}}$, it suffices to
consider $\lambda\in\mathbb{R}$ with $\frac{m+1}{m+2}\leq\lambda<1$. By
solving $(M-\lambda I)f=\frac{\mu}{2}$, we get

$\displaystyle x_{i}$
$\displaystyle=\frac{\mu}{2}\cdot\frac{\lambda-1}{m-\lambda(m+\lambda)},\ \
1\leq i\leq m,$ $\displaystyle y_{j}$ $\displaystyle=-\frac{\mu}{2\lambda},\ \
1\leq j\leq n,$ $\displaystyle z_{1}$
$\displaystyle=\frac{\mu}{2}\cdot\frac{\lambda}{m-\lambda(m+\lambda)},$
$\displaystyle z_{2}$ $\displaystyle=\frac{\mu}{2-2\lambda}.$

Using $\langle f,f\rangle=1$ and $\langle e,f\rangle=0$, we have
$p(\lambda)=(m+n+2)\lambda^{3}-(m+n+1-mn)\lambda^{2}-2mn\lambda+mn=0$. So,

$\displaystyle\operatorname{QEC}(S_{m+1,n+1})$ $\displaystyle=-2+2\
\max\\{\langle f,Mf\rangle;\ f=(x,y,z)^{T},\ \langle f,f\rangle=1,\ \langle
e,f\rangle=0\\}$ $\displaystyle=-2+2\ \max\\{\lambda;\ (M-\lambda
I)f=\frac{\mu}{2},\ \langle f,f\rangle=1,\ \langle e,f\rangle=0\\}$
$\displaystyle=-2+2\ \max\\{\lambda;\ p(\lambda)=0\\}.$

Next, we claim that the roots of $p(\lambda)=0$ are real. Since $p(0)=mn>0$,
$p(1)=1>0$, and $p(\frac{m+n}{m+n+2})=-\Big{(}\frac{m-n}{m+n+2}\Big{)}^{2}\leq
0$, $p(\lambda)$ has at least one positive root. By Descartes’ rule of sign,
$p(\lambda)$ has two positive and one negative root. This completes the proof.
∎

##  4\. Quadratic Embedding Constant of Cluster of Graphs

In this final section, we prove theorem 1.7 – deriving the quadratic embedding
constants of the clusters of an arbitrary graph with $K_{n}$ and $K_{1,n-1}$.
First we recall the definition of cluster of two graphs in general.

######  Definition 4.1.

[20] Let $G_{1}$ and $G_{2}$ be two graphs and $V(G_{1})$ be the vertex set of
$G_{1}$. The cluster $G_{1}\\{G_{2}\\}$ is obtained by taking one copy of
$G_{1}$ and $|V(G_{1})|$ copies of a rooted graph $G_{2}$, and by identifying
the root (should be same for each copy of $G_{2}$) of the i-th copy of $G_{2}$
with the i-th vertex of $G_{1}$, $i=1,2,\ldots,|V(G_{1})|$.

######  Example 4.2.

Example of a cluster graph with $G_{2}=K_{3}$:

$G_{1}$

$G_{2}$

$1$$4$$2$$3$$8$$12$$7$$11$$6$$10$$9$$5$$G_{1}\\{G_{2}\\}$

Figure 2.

Cluster graphs have important applications in Chemistry – all composite
molecules consisting of some amalgamation over a central submolecule can be
understood as generalized cluster graphs. For instance, they can be used to
understand some issues in metal-metal interaction in some molecules, since a
cluster graph structure can be easily found. In [20], the Kirchhoff index
formulae for cluster graphs are presented in terms of the pieces.

To prove Theorem 1.7, we need a basic result. The following lemma provides two
examples of monotonically increasing functions that will be crucial in proving
Theorem 1.7. We only prove the monotonicity of the first function, and that of
the second function may be shown similarly.

######  Lemma 4.3.

Let $Y,Z:\mathbb{R}\rightarrow\mathbb{R}$ be two real-valued functions defined
by

(i) $Y(b):=\frac{(nb-n)+\sqrt{(nb-n)^{2}+4nb}}{2}$ and (ii)
$Z(b):=\frac{(nb-2)+\sqrt{(nb-2)^{2}+8b}}{2},$

where $n\geq 2$ is a natural number. Then $Y$ and $Z$ are monotonically
increasing functions.

###### Proof.

(i) First, note that the term inside the square root in $Y(b)$ is always
positive. For $b\geq 0$, it is obvious, while for $b<0$,

$(nb-n)^{2}+4nb=(nb)^{2}+n^{2}+2nb(2-n)>0$.

Let $F_{b}:=\sqrt{(b-1)^{2}+\frac{4b}{n}}$, where $b\in\mathbb{R}$. Then
$F_{b}>0$ and

$(b-1)^{2}+\frac{4b}{n}=\Big{(}b-1+\frac{2}{n}\Big{)}^{2}+(\frac{4}{n}-\frac{4}{n^{2}})>\Big{(}b-1+\frac{2}{n}\Big{)}^{2}=\Big{(}1-b-\frac{2}{n}\Big{)}^{2},$

which implies $F_{b}>(1-b-\frac{2}{n})$. Now, for $b\geq c$,

$\displaystyle Y(b)-Y(c)$
$\displaystyle=\frac{(nb-n)+\sqrt{(nb-n)^{2}+4nb}}{2}-\frac{(nc-n)+\sqrt{(nc-n)^{2}+4nc}}{2}$
$\displaystyle=\frac{n}{2}\Big{\\{}(b-c)+\frac{(b-1)^{2}+\frac{4b}{n}-(c-1)^{2}-\frac{4c}{n}}{\sqrt{(b-1)^{2}+\frac{4b}{n}}+\sqrt{(c-1)^{2}+\frac{4c}{n}}}\Big{\\}}$
$\displaystyle=\frac{n}{2}\Big{(}\frac{b-c}{F_{b}+F_{c}}\Big{)}(F_{b}+F_{c}+b+c-2+\frac{4}{n})\geq
0.$

This concludes our proof. ∎

With Lemma 4.3 and Proposition 3.5 in hand, we now prove Theorem 1.7.

###### Proof of Theorem 1.7.

(i) For the sake of notional convenience, set $H:=G\\{K_{n}\\}$. Let the
vertex set of $G$ be $V=\\{1,2,\ldots,m\\}$ and the vertex set of the $i$-th
copy of $K_{n}$ be $V_{i}=\\{i,i+m,i+2m\ldots,i+(n-1)m\\}$, $1\leq i\leq m$
(see the labeling of vertices in Figure 2). If $\tilde{V}$ is the vertex set
of $H$, then $\tilde{V}=\cup_{i=1}^{m}V_{i}$. Then, $D_{H}$ can be written as

$\begin{pmatrix}D_{G}&D_{G}+J&D_{G}+J&\ldots&D_{G}+J\\\
D_{G}+J&D_{G}+2(J-I)&D_{G}+2J-I&\ldots&D_{G}+2J-I\\\
D_{G}+J&D_{G}+2J-I&D_{G}+2(J-I)&\ldots&D_{G}+2J-I\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
D_{G}+J&D_{G}+2J-I&D_{G}+2J-I&\ldots&D_{G}+2(J-I)\\\ \end{pmatrix}.$

Let $S(D_{H})$ be the set of all
$(f,\lambda,\mu)\in(C(\tilde{V})\cong\mathbb{R}^{mn})\times\mathbb{R}\times\mathbb{R}$
satisfying

$\displaystyle(D_{H}-\lambda I)f$ $\displaystyle=\frac{\mu}{2}\ e,$ (4.1)
$\displaystyle\langle f,f\rangle$ $\displaystyle=1,$ (4.2)
$\displaystyle\langle e,f\rangle$ $\displaystyle=0.$ (4.3)

By Proposition 3.1, $\operatorname{QEC}(H)=\max\\{\lambda:(f,\lambda,\mu)\in
S(D_{H})\\}$. Suppose $f=({x^{1}}^{T},{x^{2}}^{T},\ldots,{x^{n}}^{T})^{T}$,
where $x^{i}\in\mathbb{R}^{m}$ for all $1\leq i\leq n$. Using (4.3), we have
$\sum_{i=1}^{n}\langle e,x^{i}\rangle=0$ which in turn gives

$J(\sum_{i=1}^{n}x^{i})=\sum_{i=1}^{n}\langle e,x^{i}\rangle e=0.$ (4.4)

From (4.1), we obtain a system of $n$ equations. Using (4.4) and subtracting
the $i$-th equation from the first equation for $2\leq i\leq n$, we get the
following system of $(n-1)$ equations:

$\displaystyle(\lambda+2)x^{2}+x^{3}+\cdots+x^{n}=\lambda x^{1},$
$\displaystyle x^{2}+(\lambda+2)x^{3}+\cdots+x^{n}=\lambda x^{1},$
$\displaystyle\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots$
$\displaystyle x^{2}+x^{3}+\cdots+(\lambda+2)x^{n}=\lambda x^{1}.$

By solving the above system of linear equations, we get

$x^{2}=x^{3}=\cdots=x^{n}=\frac{\lambda}{\lambda+n}x^{1}.$ (4.5)

From (4.4) and (4.5), $\frac{n\lambda+n}{\lambda+n}Jx^{1}=0$ which implies
$Jx^{1}=0$, because $\lambda>-1$ (by the discussion immediately following
Proposition 3.5). Using the aforementioned observations, we can rewrite
equations [4.1–4.3] as follows:

$\displaystyle\Big{\\{}\Big{(}1+(n-1)\frac{\lambda}{\lambda+n}\Big{)}D_{G}-\lambda
I\Big{\\}}x^{1}$ $\displaystyle=$ $\displaystyle\frac{\mu}{2}\ e$ (4.6)
$\displaystyle\langle x^{1},x^{1}\rangle$ $\displaystyle=$
$\displaystyle\frac{1}{1+(n-1)\Big{(}\frac{\lambda}{\lambda+n}\Big{)}^{2}}$
(4.7) $\displaystyle\langle e,x^{1}\rangle$ $\displaystyle=$ $\displaystyle
0.$ (4.8)

On the other hand, to calculate $\operatorname{QEC}(G)$, consider the set
$S(D_{G})$ of all the stationary points
$(x,a,\gamma)\in(C(V)\cong\mathbb{R}^{m})\times\mathbb{R}\times\mathbb{R}$
satisfying

$(D_{G}-aI)x=\frac{\eta}{2}\ e,\ \ \ \ \langle x,x\rangle=1,\ \ \ \ \langle
e,x\rangle=0.$ (4.9)

By looking at equations [4.6–4.9], the following relations

$\displaystyle\lambda=\frac{(na-n)+\sqrt{(na-n)^{2}+4na}}{2}$ $\displaystyle
x^{1}=\frac{1}{\sqrt{1+(n-1)\Big{(}\frac{\lambda}{\lambda+n}\Big{)}^{2}}}\
x=\frac{\lambda+n}{\sqrt{(\lambda+n)^{2}+(n-1)\lambda^{2}}}\ x,$
$\displaystyle\mu=\frac{1+(n-1)\Big{(}\frac{\lambda}{\lambda+n}\Big{)}}{\sqrt{1+(n-1)\Big{(}\frac{\lambda}{\lambda+n}\Big{)}^{2}}}\
\eta=\frac{n(\lambda+1)}{\sqrt{(\lambda+n)^{2}+(n-1)\lambda^{2}}}\ \eta,$

give us a one to one correspondence between $S(D_{G})$ and $S(D_{H})$. So,

$\displaystyle\operatorname{QEC}(H)$
$\displaystyle=\max\\{\lambda:(({x^{1}}^{T},{x^{2}}^{T},\ldots,{x^{n}}^{T})^{T},\lambda,\mu)\in
S(D_{H})\\}$
$\displaystyle=\max\Big{\\{}\frac{(na-n)+\sqrt{(na-n)^{2}+4na}}{2}:(x,a,\eta)\in
S(D_{G})\Big{\\}}.$

Now $a\leq\operatorname{QEC}(G)$, and in particular for
$\operatorname{QEC}(G)$, there exist $\tilde{x}\in\mathbb{R}^{m}$ and
$\tilde{\eta}\in\mathbb{R}$ such that
$(\tilde{x},\operatorname{QEC}(G),\tilde{\eta})\in S(D_{G})$. Thus

$\frac{(n\operatorname{QEC}(G)-n)+\sqrt{(n\operatorname{QEC}(G)-n)^{2}+4n\operatorname{QEC}(G)}}{2}\leq\operatorname{QEC}(H).$
(4.10)

Also, by Lemma 4.3, $a\leq Q$ implies

$\operatorname{QEC}(H)\leq\frac{(n\operatorname{QEC}(G)-n)+\sqrt{(n\operatorname{QEC}(G)-n)^{2}+4n\operatorname{QEC}(G)}}{2}.$
(4.11)

Hence, the conclusion follows from (4.10) and (4.11).

(ii) Set $L:=G\\{K_{1,n-1}\\}$. Label the vertices of $L$ as in the preceding
part of this proof. Then

$D_{L}=\begin{pmatrix}D_{G}&D_{G}+J&D_{G}+J&\ldots&D_{G}+J\\\
D_{G}+J&D_{G}+2(J-I)&D_{G}+2J&\ldots&D_{G}+2J\\\
D_{G}+J&D_{G}+2J&D_{G}+2(J-I)&\ldots&D_{G}+2J\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
D_{G}+J&D_{G}+2J&D_{G}+2J&\ldots&D_{G}+2(J-I)\\\ \end{pmatrix}.$

Let $S(D_{L})$ be the set of all stationary points
$(f,\lambda,\mu)\in\mathbb{R}^{mn}\times\mathbb{R}\times\mathbb{R}$ satisfying

$(D_{L}-\lambda I)f=\frac{\mu}{2}\ e,\ \ \ \ \langle f,f\rangle=1,\ \ \ \
\langle e,f\rangle=0,$ (4.12)

and let $S(D_{G})$ be the set of all stationary points
$(x,a,\eta)\in\mathbb{R}^{m}\times\mathbb{R}\times\mathbb{R}$ satisfying

$(D_{G}-aI)x=\frac{\eta}{2}\ e,\ \ \ \ \langle x,x\rangle=1,\ \ \ \ \langle
e,x\rangle=0.$ (4.13)

Here, note that $K_{1,n}$ is isometrically embedded in $L$. So,
$-\frac{2}{n+1}\leq\lambda$. Thus, it suffices to consider all stationary
points in $S(D_{L})$ with $-\frac{2}{n}<\lambda$. By a similar argument as in
the first part of the proof, we can show that (4.12) reduces to the following
equations:

$\displaystyle\Big{\\{}\Big{(}1+(n-1)\frac{\lambda}{\lambda+2}\Big{)}D_{G}-\lambda
I\Big{\\}}x^{1}$ $\displaystyle=$ $\displaystyle\frac{\mu}{2}\ e$
$\displaystyle\langle x^{1},x^{1}\rangle$ $\displaystyle=$
$\displaystyle\frac{1}{1+(n-1)\Big{(}\frac{\lambda}{\lambda+2}\Big{)}^{2}}$
$\displaystyle\langle e,x^{1}\rangle$ $\displaystyle=$ $\displaystyle 0,$

where $f=({x^{1}}^{T},{x^{2}}^{T},\ldots,{x^{n}}^{T})^{T}$,
$x^{i}\in\mathbb{R}^{m}$.

$\displaystyle\operatorname{QEC}(L)$
$\displaystyle=\max\\{\lambda:(({x^{1}}^{T},{x^{2}}^{T},\ldots,{x^{n}}^{T})^{T},\lambda,\mu)\in
S(D_{L})\\}$
$\displaystyle=\max\Big{\\{}\frac{(na-2)+\sqrt{(na-2)^{2}+8a}}{2}:(x,a,\eta)\in
S(D_{G})\Big{\\}}.$

The remainder of the proof is same as the last part of the above proof, except
for the use of the second part of Lemma 4.3. ∎

######  Remark 4.4.

Since $\operatorname{QEC}(K_{n})=-1$ and
$\operatorname{QEC}(K_{1,n-1})=-\frac{2}{n}$, using Theorem 1.7, one can
verify that
$\operatorname{QEC}(K_{1,n-1}\\{K_{m}\\})=\operatorname{QEC}(K_{m}\\{K_{1,n-1}\\})$
if and only if $m=n$.

We conclude by discussing a couple of applications of Theorem 1.7. Our first
application provides novel families of examples of graphs of QE class.

######  Corollary 4.5.

If $G$ is a graph of QE class, then the graphs $G\\{K_{n}\\}$ and
$G\\{K_{1,n-1}\\}$ are of QE class.

###### Proof.

If $G$ is a graph of QE class then $\operatorname{QEC}(G)\leq 0$. By Lemma
4.3,

$\displaystyle\frac{(n\operatorname{QEC}(G)-n)+\sqrt{(n\operatorname{QEC}(G)-n)^{2}+4n\operatorname{QEC}(G)}}{2}$
$\displaystyle\leq\frac{-n+\sqrt{n^{2}}}{2}$
$\displaystyle\Rightarrow\operatorname{QEC}(G\\{K_{n}\\})$ $\displaystyle\leq
0;$

and

$\displaystyle\frac{(n\operatorname{QEC}(G)-2)+\sqrt{(n\operatorname{QEC}(G)-2)^{2}+8\operatorname{QEC}(G)}}{2}$
$\displaystyle\leq\frac{-2+2}{2}$
$\displaystyle\Rightarrow\operatorname{QEC}(G\\{K_{1,n-1}\\})$
$\displaystyle\leq 0.$

Thus $G\\{K_{n}\\}$ and $G\\{K_{1,n-1}\\}$ are of QE class. ∎

The next application provides the quadratic embedding constant of a simple
corona graph.

######  Definition 4.6.

Let $G_{1}$ and $G_{2}$ be two graphs defined on disjoint sets of $m$ and $n$
vertices, respectively. The corona $G_{1}\circ G_{2}$ of $G_{1}$ and $G_{2}$
is defined as the graph obtained by taking one copy of $G_{1}$ and $m$ copies
of $G_{2}$, and then joining the $i$th vertex of $G_{1}$ to every vertex in
the $i$th copy of $G_{2}$. If $G_{2}=K_{1}$, then the corona $G\circ K_{1}$ is
called a simple corona graph.

######  Corollary 4.7.

Let $G\circ K_{1}$ be a simple corona graph. Then,

$\operatorname{QEC}(G\circ
K_{1})=\operatorname{QEC}(G)-1+\sqrt{1+(\operatorname{QEC}(G))^{2}}.$

Observe that for any tree $T$, $T\\{K_{1,n-1}\\}$ is again a tree. As a final
application of Theorem 1.7, we give a better lower and upper bound for this
class of trees than Theorem 1.2.

######  Corollary 4.8.

Let $T$ be a tree on $m$ vertices. Then

$\operatorname{QEC}(P_{mn})<\operatorname{QEC}(P_{m}\\{K_{1,n-1}\\})\leq\operatorname{QEC}(T\\{K_{1,n-1}\\})\leq\operatorname{QEC}(K_{1,m-1}\\{K_{1,n-1}\\})<\operatorname{QEC}(K_{1,mn-1}).$

###### Proof.

Note that the number of vertices in $T\\{K_{1,n-1}\\}$ is $mn$. By Theorems
1.2, 1.7 and Lemma 4.3,

$\operatorname{QEC}(P_{m}\\{K_{1,n-1}\\})\leq\operatorname{QEC}(T\\{K_{1,n-1}\\})\leq\operatorname{QEC}(K_{1,m-1}\\{K_{1,n-1}\\})$

Again, by Theorem 1.2,

$\operatorname{QEC}(P_{mn})<\operatorname{QEC}(P_{m}\\{K_{1,n-1}\\})\ \ \
\mbox{and}\ \ \
\operatorname{QEC}(K_{1,m-1}\\{K_{1,n-1}\\})<\operatorname{QEC}(K_{1,mn-1}).$
(4.14)

This concludes the proof. ∎

## Acknowledgments

We thank Apoorva Khare for a detailed reading of an earlier draft and for
providing valuable feedback. P.N. Choudhury was partially supported by INSPIRE
Faculty Fellowship research grant DST/INSPIRE/04/2021/002620 (DST, Govt. of
India), and IIT Gandhinagar Internal Project: IP/IITGN/MATH/PNC/2223/25. R.
Nandi was supported by IIT Gandhinagar Post-Doctoral Fellowship
IP/IITGN/MATH/PC/2223/20.

## References

  * [1] M. Aouchiche and P. Hansen, Distance spectra of graphs: a survey, Linear Algebra Appl. 458, 301-386 (2014).
  * [2] R.B. Bapat, Graphs and Matrices, Springer, Hindustan Book Agency, New Delhi, 2010.
  * [3] E.T. Baskoro, N. Obata, Determining finite connected graphs along the quadratic embedding constants of paths. Electron. J. Graph Theory Appl. 9, 539-560 (2021).
  * [4] M. Bozejko, Positive-definite kernels, length functions on groups and non- commutative von Neumann inequality. Studia Math. 95, 107-118 (1989).
  * [5] M. Bozejko, T. Januszkiewicz and R.J. Spatzier, Infinite Coxeter groups do not have Kazhdan’s property. J. Operator Theory 19, 63-67 (1988).
  * [6] R.L. Graham and P.M. Winkler, On isometric embedding of graphs. Trans. Am. Math. Soc. 288, 527-536 (1985).
  * [7] R.L. Graham and H.O. Pollak, On the addressing problem for loop switching. Bell Sys. Tech. J. 50, 2495-2519 (1971).
  * [8] U. Haagerup, An example of a nonnuclear C*-algebra which has the metric approximation property. Invent. Math. 50, 289-293 (1979).
  * [9] A. Hora and N. Obata, Quantum Probability and Spectral Analysis of Graphs, Springer, 2007.
  * [10] R.A. Horn and C.R. Johnson, Matrix analysis. Second edition. Cambridge University Press, Cambridge, 2013.
  * [11] Z. Lou, N. Obata and Q. Huang, Quadratic embedding constants of graph joins. Graphs Combin. 38 (2022), no. 5, Paper No. 161, 22 pp.
  * [12] W. Młotkowski, Quadratic embedding constants of path graphs. Linear Algebra Appl. 644, 95-107 (2022).
  * [13] W. Młotkowski and N. Obata, On quadratic embedding constants of star product graphs. Hokkaido Math. J. 49, 129-163 (2020).
  * [14] N. Obata, Complete multipartite graphs of non-QE class, 2022\. https://arxiv.org/abs/2206.05848.
  * [15] N. Obata, Markov product of positive definite kernels and applications to Q-matrices of graph products. Colloq. Math. 122, 177-184 (2011).
  * [16] N. Obata, Positive Q-matrices of graphs. Studia Math. 179, 81-97 (2007).
  * [17] N. Obata, A.Y. Zakiyyah, Distance matrices and quadratic embedding of graphs. Electron. J. Graph Theory Appl. 6, 37-60 (2018).
  * [18] I.J. Schoenberg, Metric spaces and positive definite functions. Trans. Amer. Math. Soc. 44, 522-536 (1938).
  * [19] I.J. Schoenberg, Remarks to Maurice Frechet’s article “Sur la definition axiomatique d’une classe d’espace distancis vectoriellement applicable sur l’espace de Hilbert”. Ann. of Math. 36, 724-732 (1935).
  * [20] H. Zhang, Y. Yang, and C. Li, Kirchhoff index of composite graphs. Discrete Appl. Math., 157, 2918-2927 (2009).