# Class Instance Balanced Learning for Long-Tailed Classification

Marc-Antoine Lavoie and Steven L. Waslander
Institute for Aerospace Studies
University of Toronto
Toronto, Canada
{ marc-antoine.lavoie, steven.waslander<EMAIL_ADDRESS>
###### Abstract

The long-tailed image classification task remains important in the development
of deep neural networks as it explicitly deals with large imbalances in the
class frequencies of the training data. While uncommon in engineered datasets,
this imbalance is almost always present in real-world data. Previous
approaches have shown that combining cross-entropy and contrastive learning
can improve performance on the long-tailed task, but they do not explore the
tradeoff between head and tail classes. We propose a novel class instance
balanced loss (CIBL), which reweights the relative contributions of a cross-
entropy and a contrastive loss as a function of the frequency of class
instances in the training batch. This balancing favours the contrastive loss
for more common classes, leading to a learned classifier with a more balanced
performance across all class frequencies. Furthermore, increasing the relative
weight on the contrastive head shifts performance from common (head) to rare
(tail) classes, allowing the user to skew the performance towards these
classes if desired. We also show that changing the linear classifier head with
a cosine classifier yields a network that can be trained to similar
performance in substantially fewer epochs. We obtain competitive results on
both CIFAR-100-LT and ImageNet-LT.

##  I Introduction

The rapid development of convolutional neural network (CNN) architectures has
allowed great progress in many computer vision tasks, such as classification,
object detection and segmentation. However, moving from the hand-engineered
benchmark datasets used in most image classification tasks to unfiltered
datasets collected from real-world experiments presents a problem. Real
datasets tend to be significantly more imbalanced, with some classes being
much more common than others. Consider for instance nuImages [1], an
autonomous driving dataset obtained from real-world driving scenes, in which
there are 36314 truck instances but only 42 ambulances. Standard training
approaches will generate classifiers biased toward the most common classes
when applied to this imbalanced dataset.

In long-tailed classification, we observe two main problems on the rarest
classes: underfitting and overfitting. When underfit, the classifier does not
learn to classify rare class examples during training and performs poorly on
both the training and testing datasets. On the other hand, when overfit, the
network performance is good on training examples but does not generalize to
the unseen test data.

Common strategies to improve performance on the rare classes involve
correcting for the data imbalance in the training signal, either by adjusting
the sampling by undersampling frequent classes [2] or oversampling rare
classes [3, 4], or by balancing the gradient of the loss by weighting the
individual losses according to class frequencies [5, 6]. These methods
generally trade performance on the most frequent classes to improve results on
the rarer ones [7].

A refinement of the oversampling approaches involves the generation of new
samples, particularly from the rare classes, to correct the initial imbalance.
These new samples can be generated in the image space using more robust
augmentations [8] or generative models [9], or in feature space by
transforming existing features with the addition of noise [10]. Similarly,
some developments on the loss gradient balancing approach are the margin [11]
and logit adjustment methods [12]. Instead of simply increasing the magnitude
of the gradient for rare classes, the training task is made harder and more
robust for these classes.

Recently, there has been an interest in using contrastive losses [13, 14]
instead of the standard cross-entropy formulation. These losses have been
shown to be effective in long-tailed classification, learning more balanced
feature representations [15]. Some approaches [16, 17, 18] now combine
contrastive and cross-entropy terms and obtain state-of-the-art performance.

Following the strong results shown by PaCo [17], we propose a similar
structure combining cross-entropy and supervised contrastive losses. In
contrast to that approach, we explicitly decouple the two losses and thus
consider a simple weighted sum of both. The weights bias the loss function
towards the contrastive loss for classes with many examples in the batch and
momentum queue. We show that this reweighting, and not simply the sum of the
two losses, improves performance and gives the user a single parameter to tune
the network’s performance towards the rarest classes. Next, we show that
replacing the final linear classifier with a cosine classifier yields a
network with competitive performance that requires significantly fewer epochs
to train. Our main contributions are:

  * •

We show that when combining cross-entropy and contrastive losses, increasing
the relative importance of the contrastive loss on the head classes
effectively balances the performance across all classes, and this can be done
by tuning a single value.

  * •

Next, we show that simply modifying the linear classifier to a cosine
classifier gives us a similar performance with much fewer training epochs.

  * •

The proposed approach achieves competitive results on two popular long-tailed
benchmarks.

##  II Related Works

###  II-A Long-Tailed Classification

####  II-A1 Resampling and Reweighting

Classical approaches in long-tailed classification rely on directly
compensating for the skew in training data. This can be solved by
undersampling common classes [2] or oversampling rare classes [3, 4], but the
first can lead to overfitting while the second can lead to poor representation
learning. Similar issues are observed with the direct loss reweighting
approaches [19, 5, 6].

####  II-A2 Decoupled Learning

To reduce these effects, LDAM [11] proposes a two-stage training process,
decoupling feature and classifier learning and ensuring that good features are
learned before the balanced classifier is trained in a second step, using a
more balanced sampling or weighting. In addition to simply training using a
more balanced distribution, some methods [20, 21] consider post hoc
adjustments that attempt to find an optimal reweighting of the logits to
improve the final performance. DLSA [22] trains a Gaussian mixture flow model
as a second step to detect and send the tail instances to a separate
classifying branch.

####  II-A3 Margins and Logit Adjustment

Instead of scaling the loss according to class frequencies, some approaches
instead attempt to make the classification task harder for instances of rare
classes. This can be done by subtracting an offset from the true logit during
training [11, 23], forcing the classifier to separate classes by an additional
margin, which scales inversely with the number of instances in a class.
Alternatively, logit adjustment methods [12, 24] opt instead to rescale all
logits during training such that the most frequent ones are larger, again
making the task more difficult for tail instances. ALA [25] uses the instance
difficulty in addition to class frequency to scale the added margins.

####  II-A4 Additional Augmentations and Sample Generation

Some approaches use stronger augmentations or attempt to generate entirely new
images to deal with the long tail. M2M [26] transforms frequent class images
by pushing them towards rare classes in image space, generating new rare
images. CMO [27] generates new tail samples by mixing tail and head images
using Cutmix [8]. GAMO [28] and AFHN [9] generate new images using a GAN.
MetaSAug [10] perturbs the feature representation of rare class examples
according to a learned covariance. A recent approach, OPeN [29], adds pure
noise images to the original instances from rare classes.

####  II-A5 Ensemble Methods

Long-tailed learning can also be improved using an ensemble of models instead
of a single one. In RIDE [30], multiple models are trained with a diversity
maximization loss, ensuring the models generate different outputs, and are
deployed sequentially. LFME [31] and NCL [32] train multiple experts and use
knowledge distillation to improve performance on a single model. ResLT [33]
uses a shared backbone but adds additional parameters to the heads trained on
tail classes.

###  II-B Contrastive Learning

####  II-B1 Pure Contrastive

Contrastive learning is an alternative to cross-entropy training originally
developed for self-supervised training without labels [34, 13, 14]. These
methods learn features by clustering different augmented views of the same
image while pushing away all other images. Some works have shown that self-
supervised contrastive pre-training can improve performance [35, 36] on the
long-tailed task. Supervised Contrastive Learning (SCL) [37] is an extension
of self-supervised contrastive learning when labels are available. It has been
used successfully for classification on the full ImageNet dataset. However,
this approach still suffers from issues with the long-tailed task and produces
skewed results. To remedy this, KCL [15] proposes to use a fixed number of
positive samples, reducing the imbalance in training. TSC [38] adds fixed
targets in the contrastive loss to act as class centers, ensuring a uniform
class distribution in the feature space.

####  II-B2 Mixed Cross-Entropy and Contrastive Losses

Other approaches consider a mix of supervised contrastive and cross-entropy
losses. Hybrid-SC [16] applies the loss in two independent branches and
gradually decays the contrastive component of the loss in favour of the cross-
entropy, allowing the network to first learn good features and then optimize
the classifier for classification performance. PaCo [17] adds the cross-
entropy directly to the contrastive loss as additional terms, while BCL [18]
first rescales the contribution of each class in the denominator of the
contrastive loss and then adds learnable class centers derived from the cross-
entropy classifier vectors.

Figure 1: Class Instance Balanced Loss. Items marked with an ∗ or in green are
from the momentum branch.

##  III Method

###  III-A Logit Adjustment

Balanced Softmax [12] is a variation of the standard cross-entropy (CE) loss
that adjusts the logits during training to account for the imbalance in the
training set. The loss for instance $i$ is

$\displaystyle\mathcal{L}_{i}^{\mathrm{CE}}$
$\displaystyle=-\log\frac{n_{c_{i}}\exp\left(\mbf{x}_{i}^{{\mathsf{T}}}{\boldsymbol{\theta}}_{c_{i}}\right)}{\sum\limits_{c\in
C}n_{c}\exp\left(\mbf{x}_{i}^{{\mathsf{T}}}{\boldsymbol{\theta}}_{c}\right)}$
$\displaystyle=-\log\frac{\eta_{i,c_{i}}}{\sum\limits_{c\in C}\eta_{i,c}},$
(1)

where $\mbf{x}_{i}$ is the feature vector, $C$ the set of all classes, $c_{i}$
the true class of instance $\mbf{x}_{i}$, $\theta_{c}$ the linear classifier
associated with class $c$, $n_{c}$ the number of instances of class $c$ in the
training set and $\eta_{i,c}$ the logit associated with class $c$. This
formulation greatly improves performance on a balanced test set. Unless
otherwise noted, cross-entropy losses in the following are corrected with
Balanced Softmax.

###  III-B Supervised Contrastive Learning

Supervised Contrastive Learning (SCL) [37] is a modification of standard
contrastive loss that considers all samples of the same class in a batch to
the positives. The supervised contrastive loss for instance $i$ has the form

$\displaystyle\mathcal{L}_{i}^{\mathrm{SCL}}$
$\displaystyle=-\frac{1}{\left|P_{i}^{-}\right|}\sum_{j\in
P_{i}^{-}}\log\frac{\exp\left(\mbf{z}_{i}\cdot\mbf{z}_{j}/\tau\right)}{\sum\limits_{k\in
A^{-}}\exp\left(\mbf{z}_{i}\cdot\mbf{z}_{k}/\tau\right)},$ (2)

where $\mbf{z}_{i}$ is the contrastive embedding vector for the $i^{th}$
instance, $P_{i}^{-}$ is the set of indices of the instances with the same
class as instance $i$ excluding instance $i$, $\left|P_{i}^{-}\right|$ is its
cardinality, $A^{-}$ the set of all indices in the batch and queue excluding
$i$, and $\tau$ is a temperature scaling parameter. Because contrastive losses
tend to learn more reliably with additional negative examples, we keep a
memory queue of past image features generated from a second copy of the
encoder following the MoCo framework [34]. Both $P_{i}^{-}$ and $A^{-}$
contain examples from the current batch and the momentum queue.

The contrastive embedding vectors $\mbf{z}_{\ell}$ are given as

$\displaystyle\mbf{z}_{\ell}$
$\displaystyle=\frac{h\left(\mbf{x}_{\ell}\right)}{\left\|h\left(\mbf{x}_{\ell}\right)\right\|_{2}},$

where $h$ is a MLP projection layer as per SimCLR [13].

###  III-C Combined Losses

As discussed in Section II-B, methods like Hybrid-SC [16] and PaCo [17]
combine both a cross-entropy and a supervised contrastive loss.

####  III-C1 Summed Loss

We first consider a scalar-weighted sum of both losses given by eqs. (1) and
(2), similar to Hybrid-SC [16] but with fixed weights

$\displaystyle\mathcal{L}^{\mathrm{sum}}_{i}$
$\displaystyle=\lambda^{\mathrm{CE}}\mathcal{L}^{\mathrm{CE}}_{i}+\lambda^{\mathrm{SCL}}\mathcal{L}^{\mathrm{SCL}}_{i}.$
(3)

In practice, this simple summed formulation has a limited effect on
performance, with final results similar to using only the cross-entropy term.
We discuss this further in Section IV-E.

####  III-C2 PaCo Loss

Another approach, presented in PaCo [17], is to treat the cross-entropy logits
as additional positive and negative samples in the contrastive loss. The loss
in PaCo has the form

$\displaystyle\mathcal{L}^{\mathrm{PaCo}}_{i}$
$\displaystyle=-\gamma_{i}\Bigg{(}\alpha\sum_{j\in
P_{i}^{-}}\log\frac{\exp\left(\mbf{z}_{i}\cdot\mbf{z}_{j}/\tau\right)}{\sum\limits_{k\in
A^{-}}\exp\left(\mbf{z}_{i}\cdot\mbf{z}_{k}/\tau\right)+\sum\limits_{c\in
C}\eta_{i,c}}$
$\displaystyle\quad+\beta\log\frac{\eta_{i,c_{i}}}{\sum\limits_{k\in
A^{-}}\exp\left(\mbf{z}_{i}\cdot\mbf{z}_{k}/\tau\right)+\sum\limits_{c\in
C}\eta_{i,c}}\Bigg{)},$ (4) $\displaystyle\gamma_{i}$
$\displaystyle=\frac{1}{\alpha\left|P_{i}^{-}\right|+\beta},$

where $\alpha$ and $\beta$ control the relative importance of the contrastive
and cross-entropy positives. The cross-entropy and contrastive terms have the
same definitions as in eq. (1) and eq. (2) respectively. The numerator term is
a weighted sum between a cross-entropy and a contrastive term from the other
positive instances. This is then normalized by the sum of all positive and
negative terms in both losses. Because each sample has only a single positive
logit in the cross-entropy but can have many positives in the contrastive
loss, the summed loss skews towards the contrastive term as the number of
positive examples in the batch and momentum queue $\left|P_{i}^{-}\right|$
increases.

####  III-C3 CIBL Loss

Inspired by the PaCO loss above, we consider a new class instance balanced
loss (CIBL) that explicitly considers the sum of a cross-entropy and a
contrastive term, with relative importance proportional to the number of
instances in the batch and queue

$\displaystyle\mathcal{L}_{i}^{\mathrm{CIBL}}$
$\displaystyle=-\frac{1}{\lambda^{\mathrm{CE}}+\lambda^{\mathrm{SCL}}\left|P_{i}^{-}\right|}\Bigg{(}\lambda^{\mathrm{CE}}\log\frac{\eta_{i,c_{i}}}{\sum\limits_{c\in
C}\eta_{i,c}}$ $\displaystyle\quad+\lambda^{\mathrm{SCL}}\sum_{j\in
P_{i}^{-}}\log\frac{\exp\left(\mbf{z}_{i}\cdot\mbf{z}_{j}/\tau\right)}{\sum\limits_{k\in
A^{-}}\exp\left(\mbf{z}_{i}\cdot\mbf{z}_{k}/\tau\right)}\Bigg{)}.$ (5)

Figure 1 presents a schematic of the CIBL formulation.

In contrast to the PaCo formulation in eq. (4), the cross-entropy and
contrastive terms are uncoupled in CIBL and only dependent on the number of
other positive samples in the batch and queue $\left|P_{i}^{-}\right|$.
Because of this, it remains a weighted sum of two independent losses. This
also means that we can change the formulation of either loss with fewer
repercussions on the other. CIBL is compared to PaCo and other methods in
Section IV-C. A comparison between the baseline given in eq. (1), the simple
summed loss given by eq. (3) and the proposed CIBL loss given by eq. (5) is
given in Section IV-E.

###  III-D Logit Adjustment for Cosine Classifiers

Recent state-of-the-art methods [18, 22] use a normalized classifier for the
cross-entropy and obtain improved performance. Here, we also implement the
cross-entropy loss with a cosine distance to see if this improvement is also
observed, giving us the normalized CIBL (NCIBL). This gives a normalized
cross-entropy (NCE) loss of the form

$\displaystyle\mathcal{L}_{i}^{\mathrm{NCE}}$
$\displaystyle=-\log\frac{n_{c_{i}}\exp\left(\mathrm{sim}\left(\mbf{x}_{i},{\boldsymbol{\theta}}_{c_{i}}\right)/\gamma\right)}{\sum_{c\in
C}n_{c}\exp\left(\mathrm{sim}\left(\mbf{x}_{i},{\boldsymbol{\theta}}_{c}\right)/\gamma\right)},$
(6)
$\displaystyle\mathrm{sim}\left(\mbf{x}_{i},{\boldsymbol{\theta}}_{c_{i}}\right)$
$\displaystyle=\frac{\mbf{x}_{i}^{{\mathsf{T}}}{\boldsymbol{\theta}}_{c_{i}}}{\left\|\mbf{x}_{i}\right\|_{2}\left\|{\boldsymbol{\theta}}_{c_{i}}\right\|_{2}},$

where $n_{c}$, $\mbf{x}_{i}$, $\theta_{c}$ are defined as in eq (1) and where
$\gamma$ is a temperature parameter that scales the sharpness of the softmax
and controls how sensitive the loss is towards the largest terms. Note that
because the magnitude of the temperature directly affects the magnitude of the
logits, the relative effects of the added logit adjustment depend on
temperature. This is obvious if the logit adjustment term $n_{c}$ is moved
inside the exponential, acting as a margin on both the positive and negative
logits.

$\displaystyle\mathcal{L}_{i}^{\mathrm{NCE}}$
$\displaystyle=-\log\frac{\exp\left(\mathrm{sim}\left(\mbf{x}_{i},{\boldsymbol{\theta}}_{c_{i}}\right)/\gamma+\log
n_{c_{i}}\right)}{\sum_{c\in
C}\exp\left(\mathrm{sim}\left(\mbf{x}_{i},{\boldsymbol{\theta}}_{c}\right)/\gamma+\log
n_{c}\right)},$ (7)

In practice, the performance of NCIBL is sensitive to the temperature value
$\gamma$ used, but a reasonable range of values gives results that are better
than the baseline of pure cross-entropy. Section IV-F presents a discussion of
this.

In CIBL, pulling the number of class instances $n_{c}$ into the exponential
function as in eq. (7) adds a margin $\log\left(n_{c}\right)$ that has a
constant magnitude for all instances of a given class, regardless of the
original logit $\mbf{x}_{i}^{{\mathsf{T}}}{\boldsymbol{\theta}}_{c}$. In NCIBL
however, the effect of the added margin depends on the temperature
hyperparameter $\gamma$. Moreover, it cannot be interpreted as a fixed margin
on the angle between $\mbf{x}_{i}$ and ${\boldsymbol{\theta}}_{c}$. In the
related task of face recognition, ArcFace [23] showed that a constant angular
margin, with the margin adjustment done inside the similarity $\mathrm{sim}$
function, was beneficial over having the margin added on the output of the
similarity as done here, but further analysis of this result in the context of
long-tailed image classification is outside the scope of this work.

##  IV Experiments

We compare the performance of CIBL and NCIBL against other current state-of-
the-art methods on two standard long-tailed datasets: CIFAR-100-LT [11] and
ImageNet-LT [39]. We follow the standard evaluation protocol by testing on a
class-balanced test set. The total classification accuracy is usually
considered the primary metric of performance, but we also report the mean
class-wise accuracy for three subsets of classes when testing on ImageNet: The
$Many$ category includes classes with $n>100$ images, $Medium$ those with
$100\geq n>20$ and $Few$ those with $n\leq 20$. While we rank the different
methods according to the average accuracy, we are also interested in
identifying if the proposed approach improves performance on the tail classes
specifically.

###  IV-A Datasets

####  IV-A1 Long-Tailed CIFAR-100

CIFAR-100-LT is a subsampled version of the original CIFAR-100 dataset [40],
which is composed of 50,000 training and 10,000 validation images of size
$32\times 32$, equally divided into 100 classes. The long-tailed version of
the training dataset is subsampled with an exponential factor, and we present
results for imbalance factors of 100, 50 and 10.

####  IV-A2 Long-Tailed ImageNet

ImageNet-LT is a subsampling of the original ImageNet 2012 [41] following a
Pareto distribution, with 1000 classes having from 1280 to 5 instances in the
training set. The test set is balanced, with 50 images per class. The original
images have varying dimensions, but all of them are cropped for testing and
training to a size of $224\times 224$, with the crop being centred for the
test images.

###  IV-B Implementation Details

To allow a fair comparison with PaCo [17], which is the closest method to our
proposed CIBL, we generally follow the same training setups and schedules.
This means that the supervised head uses logit adjustment following Balanced
Softmax [12] as described in Section III-A above and that the supervised
contrastive loss is based on the MoCov2 [14] approach. All the training is
done end-to-end on a single Nvidia 3090 GPU using SGD with a momentum of 0.9.

####  IV-B1 CIFAR-100-LT

We use ResNet-32 as the backbone. Note that this is the smaller version of
ResNet as per the test setting in LDAM [11]. Following PaCo, we augment the
main branch with Cutout [42] and AutoAugment [43] and the second momentum
branch with SimAugment [13]. The class instance balance parameters are set to
$\lambda^{\mathrm{CE}}=1.0$ and $\lambda^{\mathrm{SCL}}=0.03$ respectively. We
train for 400 epochs, with a learning rate of $0.1$, decaying to 0.01 at 320
and 0.001 at 360 epochs, and with a linear warmup for the first 10 epochs. We
use a batch size of 128, a MoCo queue length of 1024 and a contrastive
temperature of $\tau=0.05$. For NCIBL, we use a cross-entropy temperature of
$\gamma=0.05$.

####  IV-B2 ImageNet-LT

We use ResNet-50 as the backbone. We augment the main branch with RandAugment
[44] and the momentum branch with SimAugment. The class instance balance
parameters are set to $\lambda^{\mathrm{CE}}=1.0$ and
$\lambda^{\mathrm{SCL}}=0.05$ respectively. We present results for a training
time of 400 epochs for CIBL, following PaCo. However, this schedule overfits
when using NCIBL, and so we present results for 200 epochs instead for NCIBL.
See Section IV-D for further discussion. For CIBL, we use a learning rate of
0.02, and for NCIBL, a learning rate of 0.04. Both decay to 0 using a cosine
schedule and a linear warmup period of 10 epochs. We use a batch size of 128,
a MoCo queue of 8192 and a contrastive temperature of $\tau=0.2$, again
following the implementation in PaCo. NCIBL uses a temperature parameter of
$\gamma=0.05$.

###  IV-C Results

####  IV-C1 CIFAR-100-LT

Table I presents the results on CIFAR-100 for our proposed CIBL method with
and without the normalized classifier. Here, both proposed approaches
outperform the baselines Balanced Softmax and PaCo and all the other methods
for all the considered imbalance ratios. NCIBL performs similarly for an
imbalance ratio of 100 but underperforms for smaller imbalances ratios.

####  IV-C2 ImageNet-LT

Table II presents the results on ImageNet-LT for CIBL and NCIBL. Here, our
approaches perform similarly to PaCo, and both proposed methods outperform all
other methods. As on CIFAR-100, NCIBL has slightly lower accuracy than CIBL on
Imagenet-LT, but the differences of $-0.1\%$ are likely not significant.
However, NCIBL has $-1.5\%$ lower accuracy on the tail classes compared to
CIBL and so presents a significantly less balanced performance. This is due to
overfitting on the tail data, which is discussed in additional detail in
Section IV-D below.

Methods | 100 | 50 | 10
---|---|---|---
Focal [19] | 38.4 | 44.3 | 55.8
LDAM-DRW [11] | 42.0 | 46.6 | 58.7
TSC [38] | 43.8 | 47.4 | 59.0
Hybrid-SC [16] | 46.7 | 51.9 | 63.1
MisLAS [45] | 47.0 | 52.3 | 63.2
MetaSaug-LDAM [10] | 48.0 | 52.3 | 61.3
ResLT [33] | 48.2 | 52.7 | 62.0
RIDE (4 experts) [30] | 49.1 | - | -
Balanced Softmax [12] | 50.8 | - | 63.0
PaCo [17] | 52.0 | - | -
CIBL | 52.6 | 56.8 | 65.8
NCIBL | 52.4 | 56.4 | 65.3
TABLE I: Accuracy on CIFAR-100-LT. We present results for imbalance ratios of 100, 50 and 10. Bold values are the best, underlined second best. Methods | Many | Medium | Few | All
---|---|---|---|---
$\tau$-norm [20] | 56.6 | 44.2 | 27.4 | 46.7
KCL [15] | 61.8 | 49.4 | 30.9 | 51.5
TSC [38] | 63.5 | 49.7 | 30.4 | 52.4
MisLAS [45] | - | - | - | 52.7
DisAlign [21] | 61.3 | 52.2 | 31.4 | 52.9
Balanced Softmax† [12] | - | - | - | 55.0
vMF [46] | 65.1 | 52.8 | 34.2 | 55.0
RIDE (4 experts) [30] | - | - | - | 55.4
BCL [18] | - | - | - | 56.0
DLSA [22] | 64.6 | 54.9 | 41.8 | 56.9
PaCo [17] | - | - | - | 57.0
CIBL | 65.4 | 55.2 | 39.4 | 57.0
NCIBL | 65.8 | 55.2 | 37.9 | 56.9
TABLE II: Accuracy on ImageNet-LT. $\dagger$ denotes results provided by [17].
Bold values are the best, underlined second best.

###  IV-D A Discussion on Training Length

In image classification, increasing the number of training epochs generally
leads to improved performance. However, there are diminishing returns on
extended training and the eventual risk of overfitting to the training data.
However, the number of training epochs required to reach overfitting will
depend on the method used.

Table III compares the performances on ImageNet-LT of CIBL and NCIBL as the
number of training epochs is increased. The implementation is the same as in
Section IV-B2, except NCIBL at 100 epochs is trained with a learning rate of
0.02. For both CIFAR-100 and ImageNet, increasing the learning rate when close
to the best operating point for maximum accuracy tends to decrease overfitting
with respect to the test set. Thus, we increase the learning rate for the
longer training schedules of 200 and 400 epochs for NCIBL.

Here, we see that NCIBL has higher accuracy for shorter training times,
providing an improvement of $+3.3\%$ at 100 epochs. At 200 epochs, the gain is
still $+1.4\%$, and only $-0.1\%$ behind CIBL at 400 epochs. However, note
that the performance on rare classes has dropped compared to NCIBL at 100
epochs, indicating the method overfitting these classes. For the 400 epoch
run, NCIBL performs worse than CIBL by $-0.6\%$ and worse than the NCIBL run
at 200 epochs by $-0.5\%$, and there is a loss in performance on both the
medium and tail classes, again indicating overfit. Further increases in epochs
are likely to continue to reduce performance. In the end, the normalized
formulation allows a significantly faster training, with similar performance
to CIBL with only half the number of epochs, but not necessarily a better one.

Finally, we see that as the number of training epochs increases, improvements
in accuracy on the training data are less transferable to the test set. Figure
2 presents the difference between training and testing accuracies at the last
training epoch for all classes, ordered by test set frequency, and linear fits
to the data. For both CIBL and NCIBL, the increase in training epochs leads to
a higher y-intercept and a steeper slope on the linear fits. Overfitting tends
to worsen as the number of epochs increases, and this result is accentuated on
tail classes.

Loss | Epochs | Many | Medium | Few | All | Train
---|---|---|---|---|---|---
CIBL | 100 | 58.5 | 51.3 | 31.7 | 51.4 | 57.9
CIBL | 200 | 62.8 | 54.7 | 37.7 | 55.5 | 69.1
CIBL | 400 | 65.4 | 55.2 | 39.4 | 57.0 | 78.8
NCIBL | 100 | 61.8 | 53.5 | 38.9 | 54.7 | 69.4
NCIBL | 200 | 65.8 | 55.2 | 37.9 | 56.9 | 77.2
NCIBL | 400 | 67.2 | 53.4 | 36.4 | 56.4 | 83.4
TABLE III: Effect of the number of training epochs on ImageNet-LT. Highlighted
cells indicate worse performance for increased training epochs. Figure 2:
Class accuracy overfitting on ImageNet-LT for different training lengths. The
classes are ordered in decreasing order of frequency in the training dataset.
The bold lines are linear fits of the data.

###  IV-E Ablations on the Choice of Loss Formulation

We compare the baseline cross-entropy loss with and without logit adjustment
given by eq. (1), the summed loss given by eq. (3) and our CIBL loss given by
eq. (5) to identify the effects of the contrastive scaling term
$\lambda^{\mathrm{SCL}}$ and of our specific formulation. Results are
presented in Table IV and are obtained using the same test setting as the
experiments on CIFAR-100-LT discussed in Section IV-B1.

Loss | $\lambda^{\mathrm{SCL}}$ | Many | Medium | Few | All | Train
---|---|---|---|---|---|---
CE‡ | - | 75.3 | 46.9 | 9.8 | 45.8 | 78.4
CE | - | 67.6 | 52.1 | 30.5 | 51.0 | 72.1
Sum | 0.01 | 69.7 | 53.2 | 29.0 | 51.6 | 72.9
Sum | 0.1 | 69.3 | 53.5 | 30.0 | 52.0 | 73.5
Sum | 0.5 | 68.3 | 53.3 | 31.3 | 51.9 | 72.4
Sum | 1.0 | 68.2 | 53.7 | 31.5 | 52.1 | 70.9
Sum | 2.0 | 66.9 | 53.1 | 29.8 | 51.0 | 68.7
CIBL | 0.01 | 67.2 | 53.5 | 33.2 | 52.4 | 70.5
CIBL | 0.03 | 65.1 | 53.2 | 36.4 | 52.6 | 65.2
CIBL | 0.05 | 61.5 | 53.9 | 36.8 | 51.4 | 51.1
CIBL | 0.10 | 57.7 | 54.3 | 38.4 | 50.7 | 50.4
TABLE IV: Comparison between different combined losses on CIFAR-100-LT. We use
larger steps in $\lambda^{\mathrm{SCL}}$ for the summed loss to observe
significant changes with respect to the cross-entropy method. The CE‡ method
is implemented without logit adjustment. Bold values are the best, underlined
second best.

We see that including the contrastive loss can improve performance for both
formulations as long as $\lambda^{\mathrm{SCL}}$ is not too large, after which
the average performance degrades. For CIBL, increasing
$\lambda^{\mathrm{SCL}}$ also transfers performance from frequent classes
towards rare classes and reduces the overfit on the training set. These
effects are also seen with the summed loss, but the magnitudes are much
smaller. This is likely because in CIBL, the relative importance of the
contrastive term is scaled by the class frequency in a batch
$\left|P_{i}^{-}\right|$. This means that changes in $\lambda^{\mathrm{SCL}}$
mainly affect the loss on frequent classes, in contrast to the loss for rare
classes, which is always dominated by cross-entropy. This difference in
training objective allows the network to learn a more balanced representation,
unlike simply using a sum of the losses with the same weights for all
instances. Finally, the performance on the tail classes increases with the
magnitude of $\lambda^{\mathrm{SCL}}$, regardless of the change in average
accuracy. This means that the end user can sacrifice some average performance
for rare class performance if desired by increasing $\lambda^{\mathrm{SCL}}$.

###  IV-F Ablations on the Temperature Scaling $\gamma$ for NCIBL

Table V presents the performance of the NCIBL loss on CIFAR-100 for different
values of $\gamma$. It has been shown [47] that decreasing the temperature
tends to improve the fit on the dataset at the cost of a loss of
generalizability. Thus, we expect the average performance to increase as the
temperature decreases, but the performance on rare classes may also decrease
as overfitting worsens. Here, the network trains poorly for large values of
$\gamma$ (1, 0.2), with training and testing accuracies significantly under
the unnormalized cross-entropy baseline. As the value of $\gamma$ gets
smaller, the testing accuracy increases to a maximum at $\gamma=0.05$. At
$\gamma=0.025$, the performance is still better than the baseline, but the
test accuracy is worse than at $\gamma=0.05$, particularly for the rare
classes where it drops by $-3.5\%$. On the other hand, the training accuracy
continues to increase, indicating overfitting. The optimal temperature for
average accuracy is also where the performance on the rarest classes is
maximized. Note also that the optimal temperature $\gamma$ of 0.05 is the same
as the contrastive temperature $\tau$ used in the contrastive loss for CIFAR
as described in Section IV-B. While the performance of NCIBL is dependent on
$\gamma$, this parameter takes on values similar to other temperature scaling
parameters used in normalized losses.

Loss | $\gamma$ | Many | Medium | Few | All | Train
---|---|---|---|---|---|---
CE | - | 67.6 | 52.1 | 30.5 | 51.0 | 72.1
NCIBL | 1 | 27.5 | 30.9 | 17.5 | 25.7 | 23.2
NCIBL | 0.2 | 63.9 | 48.1 | 18.7 | 44.8 | 59.0
NCIBL | 0.1 | 63.4 | 53.0 | 32.5 | 50.6 | 65.4
NCIBL | 0.05 | 64.7 | 55.6 | 34.3 | 52.4 | 68.6
NCIBL | 0.025 | 66.4 | 54.7 | 30.8 | 51.9 | 70.6
TABLE V: Effects temperature magnitude $\gamma$ for NCIBL on CIFAR-100-LT.
Bold values are the best, underlined second best.

##  V Conclusion

In this paper, we propose Class Instance Balanced Loss (CIBL), a method of
combining cross-entropy and contrastive losses to improve long-tailed image
classification. Our analysis shows that by forcing the loss on frequent class
samples to favour the contrastive loss over the cross-entropy loss, we obtain
a more accurate and more balanced final classifier compared to using a fixed
weighting for all classes while also enabling a principled approach to the
tradeoff between head and tail performance, which can be tuned using a single
parameter. We also show that replacing the linear classifier with a cosine
classifier allows us to train a network with similar average performance in
significantly fewer epochs. Our method obtains competitive results compared to
state-of-the-art methods on CIFAR-100-LT and ImageNet-LT.

## References

  * [1] H. Caesar, V. Bankiti, A. H. Lang, S. Vora, V. E. Liong, Q. Xu, A. Krishnan, Y. Pan, G. Baldan, and O. Beijbom, “Nuscenes: A multimodal dataset for autonomous driving,” in _Proc. IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2020.
  * [2] H. He and E. A. Garcia, “Learning from imbalanced data,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 21, no. 9, pp. 1263–1284, 2009.
  * [3] C. Huang, Y. Li, C. C. Loy, and X. Tang, “Learning deep representation for imbalanced classification,” in _Proc. IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2016.
  * [4] D. Mahajan, R. Girshick, V. Ramanathan, K. He, M. Paluri, Y. Li, A. Bharambe, and L. Van Der Maaten, “Exploring the limits of weakly supervised pretraining,” in _Proc. European Conference on Computer Vision (ECCV)_ , 2018\.
  * [5] S. H. Khan, M. Hayat, M. Bennamoun, F. A. Sohel, and R. Togneri, “Cost-sensitive learning of deep feature representations from imbalanced data,” _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 29, no. 8, pp. 3573–3587, 2017.
  * [6] Y. Cui, M. Jia, T.-Y. Lin, Y. Song, and S. Belongie, “Class-balanced loss based on effective number of samples,” in _Proc. IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019.
  * [7] M. Buda, A. Maki, and M. A. Mazurowski, “A systematic study of the class imbalance problem in convolutional neural networks,” _Neural Networks_ , vol. 106, pp. 249–259, 2018.
  * [8] S. Yun, D. Han, S. J. Oh, S. Chun, J. Choe, and Y. Yoo, “Cutmix: Regularization strategy to train strong classifiers with localizable features,” in _Proc. IEEE/CVF International Conference on Computer Vision (ICCV)_ , 2019.
  * [9] K. Li, Y. Zhang, K. Li, and Y. Fu, “Adversarial feature hallucination networks for few-shot learning,” in _Proc. IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2020.
  * [10] S. Li, K. Gong, C. H. Liu, Y. Wang, F. Qiao, and X. Cheng, “Metasaug: Meta semantic augmentation for long-tailed visual recognition,” in _Proc. IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2021.
  * [11] K. Cao, C. Wei, A. Gaidon, N. Arechiga, and T. Ma, “Learning imbalanced datasets with label-distribution-aware margin loss,” _arXiv preprint arXiv:1906.07413_ , 2019.
  * [12] J. Ren, C. Yu, X. Ma, H. Zhao, S. Yi _et al._ , “Balanced meta-softmax for long-tailed visual recognition,” _Advances in Neural Information Processing Systems_ , vol. 33, pp. 4175–4186, 2020.
  * [13] T. Chen, S. Kornblith, M. Norouzi, and G. Hinton, “A simple framework for contrastive learning of visual representations,” in _International conference on machine learning_ , 2020.
  * [14] X. Chen, H. Fan, R. Girshick, and K. He, “Improved baselines with momentum contrastive learning,” _arXiv preprint arXiv:2003.04297_ , 2020.
  * [15] B. Kang, Y. Li, S. Xie, Z. Yuan, and J. Feng, “Exploring balanced feature spaces for representation learning,” in _International Conference on Learning Representations_ , 2021.
  * [16] P. Wang, K. Han, X.-S. Wei, L. Zhang, and L. Wang, “Contrastive learning based hybrid networks for long-tailed image classification,” in _Proc. IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2021.
  * [17] J. Cui, Z. Zhong, S. Liu, B. Yu, and J. Jia, “Parametric contrastive learning,” in _Proc. IEEE/CVF International Conference on Computer Vision (ICCV)_ , 2021.
  * [18] J. Zhu, Z. Wang, J. Chen, Y.-P. P. Chen, and Y.-G. Jiang, “Balanced contrastive learning for long-tailed visual recognition,” in _Proc. IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2022.
  * [19] T.-Y. Lin, P. Goyal, R. Girshick, K. He, and P. Dollár, “Focal loss for dense object detection,” in _Proc. IEEE International Conference on Computer Vision (ICCV)_ , 2017.
  * [20] B. Kang, S. Xie, M. Rohrbach, Z. Yan, A. Gordo, J. Feng, and Y. Kalantidis, “Decoupling representation and classifier for long-tailed recognition,” _arXiv preprint arXiv:1910.09217_ , 2019.
  * [21] S. Zhang, Z. Li, S. Yan, X. He, and J. Sun, “Distribution alignment: A unified framework for long-tail visual recognition,” in _Proc. IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2021.
  * [22] Y. Xu, Y.-L. Li, J. Li, and C. Lu, “Constructing balance from imbalance for long-tailed image recognition,” in _Proc. IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2022.
  * [23] J. Deng, J. Guo, N. Xue, and S. Zafeiriou, “Arcface: Additive angular margin loss for deep face recognition,” in _Proc. IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019.
  * [24] A. K. Menon, S. Jayaplana, A. S. Rawat, H. Jain, A. Veit, and S. Kumar, “Long-tail learning via logit adjustment,” _arXiv preprint arXiv:2007.07314_ , 2020.
  * [25] Y. Zhao, W. Chen, X. Tan, K. Huang, and J. Zhu, “Adaptive logit adjustment loss for long-tailed visual recognition,” in _Proc. AAAI Conference on Artificial Intelligence_ , 2022.
  * [26] J. Kim, J. Jeong, and J. Shin, “M2m: Imbalanced classification via major-to-minor translation,” in _Proc. IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2020.
  * [27] S. Park, Y. Hong, B. Heo, S. Yun, and J. Y. Choi, “The majority can help the minority: Context-rich minority oversampling for long-tailed classification,” in _Proc. IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2022.
  * [28] S. S. Mullick, S. Datta, and S. Das, “Generative adversarial minority oversampling,” in _Proc. IEEE/CVF International Conference on Computer Vision (ICCV)_ , 2019.
  * [29] S. Zada, I. Benou, and M. Irani, “Pure noise to the rescue of insufficient data: Improving imbalanced classification by training on random noise images,” in _Proc. International Conference on Machine Learning (ICML)_ , 2022.
  * [30] X. Wang, L. Lian, Z. Miao, Z. Liu, and S. X. Yu, “Long-tailed recognition by routing diverse distribution-aware experts,” _arXiv preprint arXiv:2010.01809_ , 2020.
  * [31] L. Xiang, G. Ding, and J. Han, “Learning from multiple experts: Self-paced knowledge distillation for long-tailed classification,” in _Proc. European Conference on Computer Vision (ECCV)_ , 2020.
  * [32] J. Li, Z. Tan, J. Wan, Z. Lei, and G. Guo, “Nested collaborative learning for long-tailed visual recognition,” in _Proc. IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2022.
  * [33] J. Cui, S. Liu, Z. Tian, Z. Zhong, and J. Jia, “Reslt: Residual learning for long-tailed recognition,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2022.
  * [34] K. He, H. Fan, Y. Wu, S. Xie, and R. Girshick, “Momentum contrast for unsupervised visual representation learning,” in _Proc. IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2020.
  * [35] Y. Yang and Z. Xu, “Rethinking the value of labels for improving class-imbalanced learning,” _Advances in Neural Information Processing Systems_ , vol. 33, 2020.
  * [36] T. Li, L. Wang, and G. Wu, “Self supervision to distillation for long-tailed visual recognition,” in _Proc. of the IEEE/CVF International Conference on Computer Vision_ , 2021.
  * [37] P. Khosla, P. Teterwak, C. Wang, A. Sarna, Y. Tian, P. Isola, A. Maschinot, C. Liu, and D. Krishnan, “Supervised contrastive learning,” _Advances in Neural Information Processing Systems_ , vol. 33, pp. 18 661–18 673, 2020\.
  * [38] T. Li, P. Cao, Y. Yuan, L. Fan, Y. Yang, R. S. Feris, P. Indyk, and D. Katabi, “Targeted supervised contrastive learning for long-tailed recognition,” in _Proc. IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2022.
  * [39] Z. Liu, Z. Miao, X. Zhan, J. Wang, B. Gong, and S. X. Yu, “Large-scale long-tailed recognition in an open world,” in _Proc. IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019.
  * [40] A. Krizhevsky, G. Hinton _et al._ , “Learning multiple layers of features from tiny images,” 2009.
  * [41] O. Russakovsky, J. Deng, H. Su, J. Krause, S. Satheesh, S. Ma, Z. Huang, A. Karpathy, A. Khosla, M. Bernstein, A. C. Berg, and L. Fei-Fei, “ImageNet Large Scale Visual Recognition Challenge,” _International Journal of Computer Vision (IJCV)_ , vol. 115, no. 3, pp. 211–252, 2015.
  * [42] T. DeVries and G. W. Taylor, “Improved regularization of convolutional neural networks with cutout,” _arXiv preprint arXiv:1708.04552_ , 2017.
  * [43] E. D. Cubuk, B. Zoph, D. Mane, V. Vasudevan, and Q. V. Le, “Autoaugment: Learning augmentation policies from data,” _arXiv preprint arXiv:1805.09501_ , 2018.
  * [44] E. D. Cubuk, B. Zoph, J. Shlens, and Q. V. Le, “Randaugment: Practical automated data augmentation with a reduced search space,” in _Proc. IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) workshops_ , 2020.
  * [45] Z. Zhong, J. Cui, S. Liu, and J. Jia, “Improving calibration for long-tailed recognition,” in _Proc. IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2021.
  * [46] H. Wang, S. Fu, X. He, H. Fang, Z. Liu, and H. Hu, “Towards calibrated hyper-sphere representation via distribution overlap coefficient for long-tailed learning,” in _Proc. IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2022.
  * [47] S. Kornblith, T. Chen, H. Lee, and M. Norouzi, “Why do better loss functions lead to less transferable features?” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 28 648–28 662, 2021.


# Quantum walks on blow-up graphs

Bikash Bhattacharjya  1 Hermie Monterde  2 Hiranmoy Pal 3

###### Abstract

A blow-up of $n$ copies of a graph $G$ is the graph $\overset{n}{\uplus}~{}G$
obtained by replacing every vertex of $G$ by an independent set of size $n$,
where the copies of two vertices in $G$ are adjacent in the blow-up if and
only if the two vertices are adjacent in $G$. Our goal is to investigate
quantum state transfer on a blow-up graph $\overset{n}{\uplus}~{}G$ relative
to the adjacency matrix. We characterize strong cospectrality, periodicity,
perfect state transfer (PST) and pretty good state transfer (PGST) in blow-up
graphs. It turns out, if $\overset{n}{\uplus}~{}G$ admits PST or PGST, then
one must have $n=2.$ In particular, if $G$ has an invertible adjacency matrix,
then each vertex in $\overset{2}{\uplus}~{}G$ pairs up with a unique vertex to
exhibit strong cospectrality. We then apply our results to determine infinite
families of graphs whose blow-ups admit PST and PGST.

Keywords: perfect state transfer, pretty good state transfer, graph spectra,
blow-up, twin vertices, adjacency matrix.

MSC: 05C50, 05C76, 15A16, 15A18, 81P45.

##  1 Introduction

A quantum spin network is modelled by an undirected graph $G$, where the
vertices and edges of $G$ represent the qubits and their interactions in the
network. A continuous-time quantum walk on $G$ is described by the unitary
matrix

$U(t)=\exp{\left(itA\right)}$

where $t\in{\mathbbm{R}}$, $i=\sqrt{-1}$, and $A$ is the adjacency matrix of
$G$. Here, $|U(t)_{u,v}|^{2}$ represents the probability that the quantum
state assigned at vertex $u$ is found in vertex $v$ at time $t$. We say
perfect state transfer (PST) between $u$ and $v$ in $G$ at time $\tau>0$ if
$|U\left(\tau\right)_{u,v}|=1$. In this case, the quantum state initially at
vertex $u$ is transmitted to vertex $v$ at time $\tau$ with probability one.
If $|U\left(\tau\right)_{u,u}|=1$, then $u$ is said to be periodic in $G$ at
time $\tau$. A graph is periodic if it is periodic at all vertices at the same
time.

PST is critical for short distance communication in a physical quantum
computing scheme [JOHNSTON2017375]. The study of PST was initiated by Bose
[bose] and Christandl et al. [chr1]. In [chr2], we find that $P_{2}$ and
$P_{3}$ are the only paths that admit PST. Following this negative result,
several classes of graphs admitting PST have been studied, like cubelike
graphs [ber, che], distance-regular graphs [cou2], integral circulant graphs
[mil4, saxe], Hadamard diagonalizable graphs [JOHNSTON2017375,
mclaren2023weak], and quotient graphs [bac, ge]. In [chr2], Christandl et al.
used Cartesian products to construct graphs with PST over long distances. PST
was also studied under joins [ange1, kirkland2023quantum], non-complete
extended p-sums [pal1, pal2] and other graph products [ack1, ge, cou].

Since PST in simple unweighted graphs is rare [god2], the notion of pretty
good state transfer (PGST) was introduced [god1, vin]. A graph $G$ exhibits
PGST between $u$ and $v$ if there is a sequence $\tau_{k}\in{\mathbbm{R}}$
such that $\lim_{k\rightarrow\infty}|U\left(\tau_{k}\right)_{u,v}|=1$, i.e.,
$|U(t)_{u,v}|^{2}$ can be made arbitrarily close to one through appropriate
choices of $t$. If
$\lim_{k\rightarrow\infty}|U\left(\tau_{k}\right)_{u,u}|=1$, then $G$ is said
to be almost periodic at $u$ with respect to the sequence $\tau_{k}$, and $G$
is said to be almost periodic if there is a sequence
$\tau_{k}\in{\mathbbm{R}}$ such that

$\lim\limits_{k\to\infty}U\left(\tau_{k}\right)=\gamma I,~{}\text{for some
}\gamma\in{\mathbbm{C}},$

where $I$ is the identity matrix of appropriate order. Infinite families of
paths [cou3, god4, bom], double stars [fan] and circulant graphs are known to
exhibit PGST [pal6, pal7, pal4].

Our goal in this paper is to systematically study quantum state transfer on
blow-up graphs. Here, we consider the more familiar type of blow-up where
every vertex of a graph is replaced by an independent set. This variant of the
blow-up operation is a special case of the lexicographic product. The
lexicographic product $G[H]$ of $G$ and $H$ is the graph $G[H]$ obtained by
replacing every vertex of $G$ by a copy of $H$, and adding all possible edges
between the vertices in the copies of $H$ corresponding to adjacent vertices
in $G$. In [ge], Ge at al. provided sufficient conditions for PST to occur in
lexicographic products. Their results about PST in $G[H]$ require that $H$
exhibits PST. But in our case, $H$ is an empty graph which cannot exhibit PST,
and so their results are not applicable. This is our main motivation for
studying quantum state transfer on blow-up graphs. Another motivation is to
explore a graph operation that induces strong cospectrality between many pairs
of vertices. Strong cospectrality is an important property because it is a
requirement PGST. It turns out that if $0$ is not in the eigenvalue support of
vertex $u$ in $G$, then the two copies of $u$ are strongly cospectral in
$\overset{2}{\uplus}~{}G$ (see Theorem 2(2)). Hence, each vertex in
$\overset{2}{\uplus}~{}G$ pair up to exhibit strong cospectrality whenever $G$
has an invertible adjacency matrix (see Corollary 1). Thus, blow-ups have the
advantage of producing pairs of vertices that are promising for high
probability state transfer. Lastly, the two copies of a vertex in $G$ are
twins in $\overset{2}{\uplus}~{}G$. This allows us to utilize some of the
recent results on quantum state transfer between twins [kirk2, mon1, fr,
pal8]. In particular, we give characterizations of strong cospectrality, PST,
PGST and periodicity in blow-up graphs (see Theorems 2-5). We then
characterize PST and PGST in blow-ups of special classes of graphs (see
Sections 7-10). We note that while PST in $\overset{2}{\uplus}~{}G$ only
occurs between vertices at distance two, one may use the Cartesian product
operation to obtain relatively sparse graphs that admit PST at large distances
(Section 11).

##  2 Blow-up

Throughout, we let $G$ be a simple (loopless) connected undirected graph with
vertex set $V$. The blow-up of $G$, denoted by $\overset{n}{\uplus}~{}G$, is
the graph with vertex set ${\mathbbm{Z}}_{n}\times V$, and two vertices
$(l,u)$ and $(m,v)$ are adjacent in $\overset{n}{\uplus}~{}G$ if and only if
the vertices $u$ and $v$ are adjacent in $G$. It is immediate that if $G$ is
an $r$-regular graph then $\overset{n}{\uplus}~{}G$ is $nr$-regular. If
$P_{3}$ is the path on three vertices then $\overset{2}{\uplus}~{}P_{3}$ is
the graph shown in Figure 1.

A pair of vertices $u$ and $v$ in a graph $G$ are called twins if
$N\left(u\right)\setminus\left\\{v\right\\}=N\left(v\right)\setminus\left\\{u\right\\}$.
A twin set is a set of vertices in a graph whose elements are pairwise twins.
If $u$ is a vertex of $G$, then $T_{u}=\left\\{(j,u)\mathrel{\mathop{\mathchar
58\relax}}j\in{\mathbbm{Z}}_{n}\right\\}$ is a set of twins in
$\overset{n}{\uplus}~{}G.$ If $n\geq 2$, then each vertex in in
$\overset{n}{\uplus}~{}G$ is contained in a twin set of size at least $n$.

######  Proposition 1.

Let $u$ and $v$ be two vertices in $G$. The set $T_{u}\cup T_{v}$ is a twin
set in $\overset{n}{\uplus}~{}G$ if and only if $u$ and $v$ are non-adjacent
twins in $G.$

We also state Kronecker’s approximation theorem which is useful in classifying
graphs with PGST.

######  Theorem 1.

[apo] If $\alpha_{1},\ldots,\alpha_{l}$ are arbitrary real numbers and if
$1,\theta_{1},\ldots,\theta_{l}$ are real, algebraic numbers linearly
independent over ${\mathbbm{Q}}$ then for $\epsilon>0$ there exist
$q\in{\mathbbm{Z}}$ and $p_{1},\ldots,p_{l}\in{\mathbbm{Z}}$ such that

$\left|q\theta_{j}-p_{j}-\alpha_{j}\right|<\epsilon.$

$(0,a)$$(0,b)$$(0,c)$$(1,a)$$(1,b)$$(1,c)$ Figure 1: The graph
$\overset{2}{\uplus}~{}P_{3}$, a blow-up of two copies of $P_{3}$

##  3 Transition matrix

Let $G$ be a graph on $m$ vertices with adjacency matrix $A.$ We refer to the
eigenvalues of $A$ as the the eigenvalues of $G.$ Suppose $J_{n}$ is the
square matrix of order $n\times n$ with all entries equal to $1$. Considering
the lexicographic ordering on ${\mathbbm{Z}}_{n}\times V(G),$ the adjacency
matrix of $\overset{n}{\uplus}~{}G$ is evaluated as $A_{n}=J_{n}\otimes A,$
which is the tensor product of the matrices $J_{n}$ and $A$. Let 1 be the
vector of length $n$ with all entries equal to $1$, and let $\lambda$ be an
eigenvalue of $A$ associated to the eigenvector ${\bf x}.$ Then

$\left(J_{n}\otimes A\right)\left(\textbf{1}\otimes{\bf
x}\right)=J_{n}\textbf{1}\otimes A{\bf x}=n\lambda\left(\textbf{1}\otimes{\bf
x}\right).$

Let $\sigma(G)=\\{\lambda_{1},\lambda_{2},\ldots,\lambda_{d}\\}$ denote the
distinct eigenvalues of $A$, and $E_{j}$ be the idempotent associated with
$\lambda_{j}$. The eigenvalue support of a vertex $u$ in $G$ is the set

$\sigma_{u}(G)=\left\\{\lambda\in\sigma(G)\mathrel{\mathop{\mathchar
58\relax}}E_{\lambda}{\bf e}_{u}\neq\mathbf{0}\right\\}.$

In case $0\in\sigma\left(G\right),$ we assume $\lambda_{d}=0$. Then the
idempotents of $A_{n}$ corresponding to the eigenvalues
$n\lambda_{1},n\lambda_{2},\ldots,n\lambda_{d-1}$ and $0$ are respectively
given by

$\displaystyle\frac{1}{n}J_{n}\otimes E_{1},\ \ \frac{1}{n}J_{n}\otimes
E_{2},\ \ \ldots,\ \ \frac{1}{n}J_{n}\otimes E_{d-1},\ \
I_{mn}-\frac{1}{n}J_{n}\otimes\left(I_{m}-E_{d}\right).$ (1)

Consequently, the spectral decomposition of the transition matrix of
$\overset{n}{\uplus}~{}G$ becomes

$\displaystyle U_{n}(t)$ $\displaystyle=$
$\displaystyle\exp{\left(-itA_{n}\right)}=\sum\limits_{j=1}^{d-1}\exp{\left(-in\lambda_{j}t\right)}\cdot\frac{1}{n}J_{n}\otimes
E_{j}+\left[I_{mn}-\frac{1}{n}J_{n}\otimes\left(I_{m}-E_{d}\right)\right].$
(2)

For $(0,u),(1,u)\in{\mathbbm{Z}}_{n}\times V(G),$ one can then check that

$\displaystyle{\bf e}^{T}_{(0,u)}U_{n}(t){\bf e}_{(1,u)}$ $\displaystyle=$
$\displaystyle\frac{1}{n}\sum\limits_{j=1}^{d}\left[\exp{\left(-in\lambda_{j}t\right)}-1\right](E_{j})_{u,u}.$
(3)

If $0$ not an eigenvalue of $G,$ then we get the same set of idempotents for
$A_{n}$ in (1), except for the $d$th matrix which is now given by
$I_{mn}-\frac{1}{n}J_{n}\otimes I_{m}$. Thus, the spectral decomposition of
the transition matrix of $\overset{n}{\uplus}~{}G$ can be evaluated as follows

$U_{n}(t)=\exp{\left(-itA_{n}\right)}=\sum\limits_{j=1}^{d}\exp{\left(-in\lambda_{j}t\right)}\cdot\frac{1}{n}J_{n}\otimes
E_{j}+\left[I_{mn}-\frac{1}{n}J_{n}\otimes I_{m}\right].$

Thus, we get an expression for ${\bf e}^{T}_{(0,u)}U_{n}(t){\bf e}_{(1,u)}$
similar to (3). Next, we state an observation about the spectra and eigenvalue
supports in blow-ups (see also [oliveira2014spectra]).

######  Proposition 2.

Let $n\geq 2$. Then
$\sigma\left(\overset{n}{\uplus}~{}G\right)=n\cdot\sigma\left(G\right)\cup\left\\{0\right\\}$
and
$\sigma_{(j,v)}\left(\overset{n}{\uplus}~{}G\right)=n\cdot\sigma_{v}(G)\cup\left\\{0\right\\}$
for any vertex $u$ of $G$ and for all $j\in{\mathbbm{Z}}_{n}$.

In [cou, Lemma 3.3], the authors provided the form of transition matrices of
graphs whose adjacency matrices look like $B\otimes M+C\otimes N$, where
$(B,C)$ and $(M,N)$ are pairs of commuting matrices. This include blow-up
graphs, since we may write $J_{n}\otimes A=A(K_{n})\otimes A+I_{n}\otimes A$.
However, their paper had no other results specific to blow-up graphs.

We also mention that Monterde investigated sedentariness, a type of low
probability quantum transport, on several variants of the blow-up operation
[sed]. Apart from the work of Ge et al. [ge] and Monterde, we are unaware of
other results about quantum state transfer on blow-up graphs.

##  4 Strong cospectrality

Two vertices $u$ and $v$ in a graph $G$ are said to be strongly cospectral if
for every $\lambda\in\sigma_{u}(G)$,

$E_{\lambda}\textbf{e}_{u}=\pm E_{\lambda}\textbf{e}_{v}.$

Strong cospectrality is a necessary condition for PGST to occur between two
vertices [god1, Lemma 13.1]. This motivates us to characterize strong
cospectrality in blow-up graphs.

######  Theorem 2.

Let $G$ be a graph with vertex $u$. The following hold.

  1. 1.

If $n\geq 3$, then $\overset{n}{\uplus}~{}G$ does not exhibit strong
cospectrality.

  2. 2.

Let $n=2$. Then $(0,u)$ and $(1,u)$ are strongly cospectral in
$\overset{2}{\uplus}~{}G$ if and only if $0\notin\sigma_{u}(G)$. Moreover,
$(0,u)$ can only be strongly cospectral with $(1,u)$ in
$\overset{2}{\uplus}~{}G$.

###### Proof.

We prove 1. If $n\geq 3$, then $|T_{u}|\geq 3$ in $\overset{n}{\uplus}~{}G$
for every vertex $u$ of $G$. Invoking [mon1, Corollary 3.10] yields the
desired conclusion. To prove 2, note that the $d-1$ idempotents of $A_{2}$ in
(1) satisfy $\left(\frac{1}{2}J_{2}\otimes
E_{j}\right)(\textbf{e}_{0}\otimes\textbf{e}_{u})=\frac{1}{2}\textbf{1}\otimes
E_{j}\textbf{e}_{u}=\left(\frac{1}{n}J_{2}\otimes
E_{j}\right)(\textbf{e}_{1}\otimes\textbf{e}_{u}).$ Let $E$ denoted the $d$th
idempotent of $A_{2}$ in (1). Note that
$E(\textbf{e}_{0}\otimes\textbf{e}_{u})=\left(\textbf{e}_{0}-\frac{1}{2}\textbf{1}\right)\otimes\textbf{e}_{u}+\left(\frac{1}{2}\textbf{1}\otimes
E_{d}\textbf{e}_{u}\right)$, and so we have
$E(\textbf{e}_{0}\otimes\textbf{e}_{u})\neq
E(\textbf{e}_{1}\otimes\textbf{e}_{u})$. However, one checks that
$E(\textbf{e}_{0}\otimes\textbf{e}_{u})=-E(\textbf{e}_{1}\otimes\textbf{e}_{u})$
if and only if $n=2$ and $0\notin\sigma_{u}(G)$. This proves the first
statement in 2, while the second statement follows directly from [mon1,
Theorem 3.9(2)]. ∎

The following result is immediate from Theorem 2(2).

######  Corollary 1.

If $0\notin\sigma(G)$, then for any vertex $u$ of $G$, $(0,u)$ and $(1,u)$ are
strongly cospectral in $\overset{2}{\uplus}~{}G$, and they cannot be strongly
cospectral to any other vertex of $\overset{2}{\uplus}~{}G$.

######  Example 1.

Let $T$ be a tree with a (unique) perfect matching. Then $T$ has an invertible
adjacency matrix, and so each vertex of $\overset{2}{\uplus}~{}G$ pairs up
with a unique vertex to exhibit strong cospectrality by Corollary 1.

Note that Example 1 applies to $P_{2m}$. For $P_{2m+1}$, we have the following
observation.

######  Example 2.

Let $G=P_{2m+1}$ with edges $(u,u+1)$ for each $u\in\\{1,\ldots,2m\\}$. Note
that 0 is a simple eigenvalue of $G$ with eigenvector
$\textbf{e}_{1}-\textbf{e}_{3}+\textbf{e}_{5}-\ldots+(-1)^{\frac{2m-1}{2}}\textbf{e}_{2m+1}$.
Therefore, $0\notin\sigma_{u}(G)$ if and only if $u$ is even. By Theorem 2(2),
$(0,u)$ and $(1,u)$ are strongly cospectral in $\overset{2}{\uplus}~{}G$ if
and only if $u$ is even.

##  5 Pretty good state transfer

Since strong cospectrality is a necessary condition for PGST, we restrict to
the case $n=2$ and $0\not\in\sigma_{u}(G)$. The following result characterizes
PGST in blow-up graphs.

######  Theorem 3.

Let $u$ be a vertex in $G$ with $0\notin\sigma_{u}(G).$ The following are
equivalent.

  1. 1.

The graph $\overset{2}{\uplus}~{}G$ exhibits PGST between $(0,u)$ and $(1,u)$
with phase factor $\gamma=-1.$

  2. 2.

There exists a sequence $\tau_{k}$ so that
$\lim\limits_{k\to\infty}\exp{\left(-2i\lambda\tau_{k}\right)}=-1\text{ for
each }\lambda\in\sigma_{u}(G)$.

  3. 3.

$G$ is almost periodic at $u$ with the phase factor $\gamma=-1.$

  4. 4.

If $m_{j}$ are integers such that
$\displaystyle\sum_{\lambda_{j}\in\sigma_{u}(G)}m_{j}\lambda_{j}=0$, then
$\displaystyle\sum_{\lambda_{j}\in\sigma_{u}(G)}m_{j}$ is even.

###### Proof.

We first prove that 1 implies 2. Suppose $\overset{2}{\uplus}~{}G$ exhibits
PGST between the twin vertices $(0,u)$ and $(1,u)$. We have from (3)

$\lim\limits_{k\to 0}{\bf e}^{T}_{(0,u)}U_{n}(t_{k}){\bf
e}_{(1,u)}=\lim\limits_{k\to
0}\sum\limits_{j=1}^{d}(1/2)\left[\exp{\left(-2i\lambda_{j}t_{k}\right)}-1\right](E_{j})_{u,u}=\gamma.$
(4)

Note that if $(0,u)$ and $(1,u)$ are strongly cospectral in
$\overset{2}{\uplus}~{}G$, then $\lambda=0$ is the only eigenvalue in
$\sigma_{(0,u)}(\overset{2}{\uplus}~{}G)$ for which
$E_{\lambda}(\mathbf{e}_{0}\otimes\mathbf{e}_{u})=-E_{\lambda}(\mathbf{e}_{1}\otimes\mathbf{e}_{u})$.
Thus, $\gamma=-e^{it0}=-1$, and the conclusion in 2 follows from (4). Now, if
2 holds, then there exists a sequence $\tau_{k}$ so that
$\lim\limits_{k\to\infty}\exp{\left(-2i\lambda_{j}\tau_{k}\right)}=-1$ for all
$\lambda_{j}\in\sigma_{u}(G)$. Then (3) yields $\lim\limits_{k\to\infty}{\bf
e}^{T}_{(0,u)}U_{n}(\tau_{k}){\bf e}_{(1,u)}=-1$, and so 1 holds. Thus, 1 and
2 are equivalent. The equivalence of 2 and 3 follows from the spectral
decomposition of $U_{2}(t)$, while the equivalence of 1 and 4 follows from
[kirk2, Theorem 13]. ∎

Denote the largest power of two that divides an integer $a$ by $\nu_{2}(a)$.
The following is a characterization PST in blow-up graphs, the proof of which
is identical to that of Theorem 3, except that the equivalence of 1 and 4 is a
consequence of [kirk2, Theorem 10].

######  Theorem 4.

Let $u$ be a vertex in $G$ with $0\notin\sigma_{u}(G).$ The following are
equivalent.

  1. 1.

The graph $\overset{2}{\uplus}~{}G$ exhibits PST between $(0,u)$ and $(1,u)$
with the phase factor $\gamma=-1$.

  2. 2.

There exists $\tau\in{\mathbbm{R}}$ so that
$\exp{\left(-2i\lambda\tau\right)}=-1\text{ for each
}\lambda\in\sigma_{u}(G)$.

  3. 3.

$G$ is periodic at $u$ with the phase factor $\gamma=-1.$

  4. 4.

Each $\lambda_{j}\in\sigma_{u}(G)$ can be written as
$\lambda_{j}=b_{j}\sqrt{\Delta}$, where $b_{j}$ is an integer, $\Delta=1$ or
$\Delta>1$ is a square-free integer, and the $\nu_{2}(b_{j})$’s are all equal.

We note that while PGST is a relaxation of PST, these two are equivalent for
periodic vertices [pal7]. Hence, we say that proper pretty good state transfer
occurs between two vertices if they exhibit pretty good state transfer but not
periodicity.

##  6 Periodicity

Before we move on to the next section, we include results on periodicity of
vertices in blow-up graphs. Similar to strong cospectrality, periodicity is a
requirement for two vertices to admit PST. The following is straightforward
from [god2, Theorem 6.1].

######  Theorem 5.

Let $n\in{\mathbbm{N}}.$ Then $\overset{n}{\uplus}~{}G$ is periodic at all
vertices in $S_{u}=\left\\{(j,u)\mathrel{\mathop{\mathchar
58\relax}}j\in{\mathbbm{Z}}_{n}\right\\}$ if and only if the elements in
$\sigma_{u}(G)$ are either all integers or all integer multiples of
$\sqrt{\Delta}$, where $\Delta>1$ is a square-free integer. Moreover,
periodicity of vertices in $S_{u}$ in $\overset{n}{\uplus}~{}G$ implies
periodicity of $u$ in $G$, and the time at which vertices in $S_{u}$ are
periodic in $\overset{n}{\uplus}~{}G$ is equal to $\frac{\tau}{n}$, where
$\tau$ is the time at which $u$ is periodic in $G$. Furthermore, if a vertex
in $S_{u}$ is periodic in $\overset{n}{\uplus}~{}G$ for some $n,$ then it is
periodic in $\overset{n}{\uplus}~{}G$ for all $n\in{\mathbbm{N}}.$

From Theorem 5, periodicity of vertices in $S_{u}$ in
$\overset{n}{\uplus}~{}G$ implies periodicity of $u$ in $G$. However, the
converse of this does not hold whenever $u$ is periodic in $G$ and
$\frac{1}{2}(a+b\sqrt{\Delta})\in\sigma_{u}(G)$ for some integer $a\neq 0$ and
square-free integer $\Delta>1$. Theorem 5 also implies that the blow-up
operation yields shorter times for periodicity than the original graph. We
illustrate these two observations in the following example.

######  Example 3.

Let $H$ is a $k$-regular graph on $m$ vertices. Let $G$ be a graph resulting
from $H$ by adding a vertex $u$ adjacent to all vertices of $H$. Then
$\sigma_{u}(G)=\\{\lambda_{\pm}\\}$, where
$\lambda_{\pm}=\frac{1}{2}(k\pm\sqrt{k^{2}+4m})$. Thus, $u$ is periodic in $G$
at $\tau=\frac{2\pi}{\sqrt{k^{2}+4m}}$. Since $0\notin\sigma_{u}(G)$, Theorem
5(2) implies that $\overset{n}{\uplus}~{}G$ is periodic at all vertices in
$S_{u}=\left\\{(j,u)\mathrel{\mathop{\mathchar
58\relax}}j\in{\mathbbm{Z}}_{n}\right\\}$ if and only if either $k^{2}+4m$ is
a perfect square , or $k=0$ (in which case $G=K_{1,m}$ and
$\lambda_{\pm}=\pm\sqrt{m}$). In both cases, the vertices in $S_{u}$ are
periodic at $\tau=\frac{2\pi}{n\sqrt{k^{2}+4m}}$. Moreover, if
$\overset{n}{\uplus}~{}G$ is periodic at all vertices in
$S_{u}=\left\\{(j,u)\mathrel{\mathop{\mathchar
58\relax}}j\in{\mathbbm{Z}}_{n}\right\\}$ for some $n>1$, then it holds for
all $n\in{\mathbbm{N}}$.

In Example 3, vertex $u$ in $G$ is always periodic. However, if $k>0$ and
$k^{2}+4m$ is not a perfect square, then each vertex in $S_{u}$ is not
periodic for all $n$. Thus, blow-ups need not preserve periodicity. The next
result follows from [god3, Corollary 3.3].

######  Proposition 3.

If $G$ is periodic at $\tau,$ then $\overset{n}{\uplus}~{}G$ is periodic at
$\frac{\tau}{n}$ for all $n\in{\mathbbm{N}}$.

##  7 Complete graphs and cycles

We now start our investigation of PST and PGST on blow-ups of various classes
of graphs.

Let $K_{m}$ be a complete graph on $m$ vertices with eigenvalues $-1$ and
$m-1,$. If $m$ is even then the eigenvalues $K_{m}$ are all odd. If
$\tau=\frac{\pi}{2}$ in Theorem 4, then $\overset{2}{\uplus}~{}K_{m}$ exhibits
PST between every pair of twin vertices. If $m$ is odd, then
$\exp{\left(-2i(-1)\tau\right)}=-1$ implies
$\exp{\left(-2i(m-1)\tau\right)}=\left[\exp{\left(-2i(-1)\tau\right)}\right]^{1-m}=1$,
and so $\overset{2}{\uplus}~{}K_{m}$ does not exhibit PST by Theorem 4. Thus,
we have:

######  Theorem 6.

$\overset{2}{\uplus}~{}K_{m}$ exhibits PST at $\frac{\pi}{2}$ if and only if
$m$ is even.

Next, let $C_{n}$ be a cycle of length $n$ where $n\geq 3$. The eigenvalues of
$C_{n}$ are

$\lambda_{l}=2\cos{\left(\frac{2l\pi}{n}\right)},~{}l=0,1,\ldots,n-1.$

We now prove the following negative result for cycles.

######  Theorem 7.

$\overset{2}{\uplus}~{}C_{n}$ does not exhibit PGST for all $n\geq 3$.

###### Proof.

If $n$ is divisible by $4,$ then support of each vertex in $C_{n}$ contains
$\lambda=0.$ Thus, $\overset{2}{\uplus}~{}C_{n}$ does not admit strong
cospectrality by Theorem 2. Now, let $n=mp$, where $p$ is an odd prime, and
$\omega_{p}$ is the primitive $p$-th root of unity. Then

$1+\omega_{p}+\omega_{p}^{2}+\ldots+\omega_{p}^{p-1}=0.$

It follows that

$1+2\sum_{r=1}^{(p-1)/2}\cos{\left(\frac{2r\pi}{p}\right)}=0.$

Multiplying both sides by $2\cos{\left(2\pi/n\right)}$ yields

$\lambda_{1}+\sum_{r=1}^{(p-1)/2}\lambda_{mr+1}+\sum_{r=1}^{(p-1)/2}\lambda_{mr-1}=0.$

Suppose the sum of the eigenvalues of $C_{n}$ in the above expression be $L.$
By Theorem 3, if there is PGST in $\overset{2}{\uplus}~{}C_{n}$ then
$1=\lim\limits_{k\to\infty}\exp{\left(-2iL\tau_{k}\right)}=(-1)^{p}=-1,$ a
contradiction. ∎

Note that $C_{4}$ admits PST but $\overset{2}{\uplus}~{}C_{4}$ does not. Thus,
a blow-up of a graph with PST need not have PST.

##  8 Paths

Next, we characterize PGST in blow-ups of paths. The eigenvalues of $P_{n}$
are

$\theta_{j}=2\cos\left(\frac{j\pi}{n+1}\right),\quad 1\leq j\leq n.$

Moreover, for every vertex $u$ of $P_{n}$, [Bommel2019, Lemma 3.3.6] yields

$\sigma_{u}(P_{n})=\\{\theta_{j}\mathrel{\mathop{\mathchar 58\relax}}n+1\nmid
uj\\}$ (5)

The following result characterizes PGST on blow-ups of $P_{n}$ whenever
$n=p-1$ or $n=2p-1$ for some prime $p$, or $n=2^{t}-1$ for some integer $t\geq
2$.

######  Theorem 8.

Suppose $n=p-1$ or $n=2p-1$ for some prime $p$, or $n=2^{m}-1$. Then PGST
occurs between vertices $(0,u)$ and $(1,u)$ in $\overset{2}{\uplus}~{}P_{n}$
if and only if

  1. 1.

$n=p-1$ for some prime $p$ and $u$ is any vertex in $P_{n}$, or

  2. 2.

$n=2p-1$ for some prime $p$ or $n=2^{t}-1$ for some integer $t$, and $u$ is
even.

###### Proof.

Suppose that either (i) $n=p-1$ for some prime $p$, (ii) $n=2p-1$ for some
prime $p$, (iii) $n=2^{t}-1$ for some integer $t$. From [god4], (i), (ii) or
(iii) hold if and only if the positive eigenvalues of $P_{n}$ are linearly
independent over $\mathbb{Q}$. Thus, if (i) holds, then applying Theorem 1
with $\alpha_{j}=\frac{1}{2}(\theta_{j}+1)$, we obtain integers $q_{k}$ and
$p_{j}$ such that $|q_{k}\theta_{j}-p_{j}-\alpha_{j}|<\frac{1}{2\pi k}.$
Equivalently,
$|(2q_{k}-1)\frac{\pi}{2}(2\theta_{j})-(2p_{j}+1)\pi|<\frac{1}{k}$. Setting
$\tau_{k}=(2q_{k}-1)\frac{\pi}{2}$, we obtain

$\lim\limits_{k\to\infty}\exp{\left(-2i\theta_{j}\tau_{k}\right)}=\exp{((2p_{j}+1)\pi)}=-1$
(6)

for each eigenvalue $\theta_{j}\in\sigma_{u}(P_{n})$. Since $P_{n}$ in this
case has an invertible adjacency matrix, $(0,u)$ and $(1,u)$ are strongly
cospectral for each vertex $u$ of $P_{n}$ by Example 1. Combining this with
(6) yields PGST between $(0,u)$ and $(1,u)$ for each vertex $u$ of $P_{n}$ by
virtue of Theorem 3. This proves 1. The same argument works for cases (ii) and
(iii), except that we need $u$ to be an even vertex of $P_{n}$ by Example 2 to
ensure that $(0,u)$ and $(1,u)$ are strongly cospectral. Hence, 2 holds. ∎

Next, we rule out PGST in blow-ups of $P_{n}$ whenever
$n\notin\\{p-1,2p-1,2^{t}-1\\}$.

######  Theorem 9.

Let $n=2^{t}r-1$, where $t\geq 0$ is an integer and $r>0$ is odd. Then PGST
does not occur between vertices $(0,u)$ and $(1,u)$ in
$\overset{2}{\uplus}~{}P_{n}$ whenever

  1. 1.

$t\geq 0$ and $r$ is an odd composite number, or

  2. 2.

$t>0$, $r$ is an odd prime number and $u$ is not a multiple of $2^{t-1}$.

###### Proof.

To prove 1, let us first suppose that $t=0$ so that $n=r-1$, where $r$ is an
odd composite number. From [bom, Equation 26], we obtain

$\sum_{i=0}^{r/p-1}(-1)^{i}\theta_{c+ip}=0$

where $c\in\\{1,2\\}$ and $p$ is a prime factor of $r$ such that
$p\mid\frac{r}{\operatorname{gcd}(a,r)}$. Since $c+ip$ is not a multiple of
$p$ for each $i\in\\{0,1,\ldots,\frac{r}{p}-1\\}$, (5) implies that each
$\theta_{c+ip}$ above is contained in $\sigma_{u}(P_{n})$ for any vertex $u$
of $P_{n}$. If there is PGST in $\overset{2}{\uplus}~{}P_{n}$, then Theorem 3
yields $\lim\limits_{k\to\infty}\exp{\left(\pm
2i\theta_{c+ip}\tau_{k}\right)}=-1$. Now, let $L$ be the expression on the
left of the above equation. Since $r$ is composite and $p$ is prime,
$\frac{r}{p}$ is odd, and so
$1=\lim\limits_{k\to\infty}\exp{\left(-2iL\tau_{k}\right)}=(-1)^{\frac{r}{p}}=-1,$
a contradiction. In case $t>0$, then we have two subcases. First, if $r$ has
no prime factor $p$ such that
$p\mid\frac{2^{t}r}{\operatorname{gcd}(a,2^{t}r)}$, then $r\mid a$ and [bom,
Equation 24] gives us

$\sum_{i=0}^{r/p-1}(-1)^{i}\theta_{c+i2^{t}p}=0.$

However, if $r$ has a prime factor $p$ such that
$p\mid\frac{2^{t}r}{\operatorname{gcd}(a,2^{t}r)}$, then [bom, Equation 25]
yields

$\sum_{i=0}^{r/p-1}(-1)^{i}\theta_{c+i2^{t}}=0.$

In both subcases, an argument similar to the case $t=0$ yields the desired
result. Finally, the proof of the second case follows from the first case with
$t>0$ and $r$ has no prime factor $p$ such that
$p\mid\frac{2^{t}r}{\operatorname{gcd}(a,2^{t}r)}$. ∎

Combining Theorems 8 and 9, the only case left to check for PGST in blow-ups
of $P_{n}$ is when $n=2^{t}r-1$, where $t\geq 2$, $r$ is an odd prime and $u$
is a multiple of $2^{t-1}$. For $P_{11}$ with an even vertex $u$, one checks
that $\theta_{5},\theta_{9},\theta_{11}\in\sigma_{u}(G)$ and
$\lambda_{5}-\theta_{9}+\theta_{11}=0$. If PGST occurs between $(0,u)$ and
$(1,u)$ in $\overset{2}{\uplus}~{}P_{11}$, then Theorem 3 yields
$\lim\limits_{k\to\infty}\exp{\left(\pm 2i\theta_{j}\tau_{k}\right)}=-1$ for
each $\theta_{j}\in\sigma_{u}(G)$. Consequently,
$1=\lim\limits_{k\to\infty}\exp{\left(-2i(\lambda_{5}-\theta_{9}+\theta_{11})\tau_{k}\right)}=(-1)^{3}=-1$,
a contradiction. Thus, $(0,u)$ is not involved in PGST in
$\overset{2}{\uplus}~{}P_{11}$ for each even vertex $u$ of $P_{11}$. This
leads us to the following conjecture.

######  Conjecture 1.

Let $n=2^{t}r-1$, where $t\geq 2$ and $r$ is an odd prime number. If $u$ is a
multiple of $2^{t-1}$, then PGST does not occur between $(0,u)$ and $(1,u)$ in
$\overset{2}{\uplus}~{}P_{n}$.

######  Remark 1.

In [bom, Theorem 4(2)], PGST occurs between $u$ and $12-u$ in $P_{11}$
whenever $u$ is even. As PGST does not occur between $(0,u)$ and $(1,u)$ in
$\overset{2}{\uplus}~{}P_{n}$, blow-up graphs need not preserve PGST.

We end this section with a result on periodicity and PST on blow-ups of
$P_{n}.$ Theorem 5 implies that periodicity of a vertex $(j,u)$ in
$\overset{m}{\uplus}~{}P_{n}$ implies periodicity of $u$ in $P_{n}$. From the
proof of [Bommel2019, Theorem 3.3.8], one can infer that the only periodic
vertices in $P_{n}$ are the vertices of $P_{2}$ and $P_{3}$ and the middle
vertex $u$ of $P_{5}$ with $\sigma_{u}(P_{5})=\\{0,\pm\sqrt{3}\\}$. Applying
Theorems 2(2) and 4 yields the following result.

######  Theorem 10.

Consider the set $S_{u}=\left\\{(j,u)\mathrel{\mathop{\mathchar
58\relax}}j\in{\mathbbm{Z}}_{m}\right\\}$. The following hold.

  1. 1.

Each vertex in $S_{u}$ is periodic in $\overset{m}{\uplus}~{}P_{n}$ for all
$m$ if and only if either (i) $u$ is any vertex of $P_{2}$, (ii) $u$ is any
vertex of $P_{3}$, or (iii) $u$ is the middle vertex of $P_{5}$. Moreover, a
vertex in $S_{u}$ has period either $\tau=\frac{2\pi}{m}$,
$\tau=\frac{2\pi}{\sqrt{2}m}$, or $\tau=\frac{2\pi}{\sqrt{3}m}$, respectively.

  2. 2.

$\overset{2}{\uplus}~{}P_{n}$ admits PST between $(0,u)$ and $(1,u)$ if and
only if (i) $u$ is any vertex of $P_{2}$, or (ii) $u$ is the middle vertex of
$P_{3}$. Moreover, the minimum PST time in $\overset{2}{\uplus}~{}P_{2}$ is
$\tau=\frac{\pi}{2}$. Otherwise, it is $\tau=\frac{\pi}{2\sqrt{2}}$.

##  9 Double and subdivided stars

A double star graph $S_{k,\ell}$ is a tree resulting from attaching $k$ and
$\ell$ pendent vertices to the vertices of $K_{2}$. The following result
characterizes PGST in blow-ups of double stars.

######  Theorem 11.

Let $u$ and $v$ be the degree $k$ and $\ell$ vertices of $S_{k,\ell}$. The
following hold in $\overset{2}{\uplus}~{}S_{k,\ell}$.

  1. 1.

If $k\geq 2$, then $(0,w)$ is not involved in PGST for every $w\in
N_{S_{k,\ell}}(u)\backslash\\{v\\}$.

  2. 2.

Let $k=1$. Then PGST occurs between the pairs $\\{(0,u),(1,u)\\}$,
$\\{(0,v),(1,v)\\}$ and $\\{(0,w),(1,w)\\}$, where $w\in
N_{S_{k,\ell}}(u)\backslash\\{v\\}$. Further, if $x\in
N_{S_{k,\ell}}(v)\backslash\\{u\\}$, then PGST occurs between $(0,x)$ and
$(1,x)$ if and only if $\ell=1$.

  3. 3.

Let $k=\ell$. There is PGST between $(0,u)$ and $(1,u)$ if and only if $4k+1$
is not a perfect square.

  4. 4.

If $k\neq\ell$ and all non-zero eigenvalues of $S_{k,\ell}$ are linearly
independent over $\mathbb{Q}$, then PGST occurs between $(0,u)$ and $(1,u)$.

###### Proof.

We first show 1. Since $k\geq 2$, two vertices $w,x\in N_{S_{k,\ell}}(u)$ are
twins, and so $T_{w}\cup T_{x}$ is a twin set in
$\overset{2}{\uplus}~{}S_{k,\ell}$ with size at least four by Proposition 1.
By [mon1, Corollary 3.10], $(0,w)$ cannot exhibit strong cospectrality in
$\overset{2}{\uplus}~{}S_{k,\ell}$ for each $w\in
N_{S_{k,\ell}}(u)\backslash\\{v\\}$. Thus, 1 holds.

To prove 2, let $k=1$ and $w$ be the lone vertex in
$N_{S_{1,\ell}}(u)\backslash\\{v\\}$. Note that
$\sigma_{u}(G)=\sigma_{v}(G)=\sigma_{w}(G)=\\{\sqrt{(k+2\pm
m)/2},-\sqrt{(k+2\pm m)/2}\\}$, where $m=\sqrt{k^{2}+4}$. As
$\\{\sqrt{(k+2+m)/2},\sqrt{(k+2-m)/2}\\}$ is a linearly independent set over
$\mathbb{Q}$, the same argument in the proof of Theorem 8(1) proves the first
statement of 2, while 1 and the fact that the positive eigenvalues of $P_{4}$
yields the second statement of $2$.

To prove 3, suppose $k=\ell$. Then
$\sigma_{u}(G)=\\{\frac{1}{2}(1\pm\sqrt{4k+1}),-\frac{1}{2}(1\pm\sqrt{4k+1})\\}$.
If $4k+1$ is a perfect square, then $1+\sqrt{4k+1}$ and $-1+\sqrt{4k+1}$ are
even integers whose largest powers of two dividing them are not equal.
Invoking Theorem 4(5), PST does not occur between $(0,u)$ and $(1,u)$ in
$\overset{2}{\uplus}~{}S_{k,\ell}$. Now, if $4k+1$ is not a perfect square,
then $\\{\pm 1+\sqrt{4k+1}\\}$ is a linearly independent set over
$\mathbb{Q}$, from which it again follows that PGST occurs between $(0,u)$ and
$(1,u)$ in $\overset{2}{\uplus}~{}S_{k,\ell}$. The same conclusion can be
drawn with the assumption in 4. Hence, 3 and 4 hold. ∎

$0$$\pm(1-m)$$1-m$$\pm 1$$1$$\pm 1$$1$$m-1$ Figure 2: An eigenvector of
$SK_{1,m}$ corresponding to $\pm 1.$

Next, we examine subdivided stars. First, observe that an eigenvector of a
graph $G$ can be viewed a function ${\bf x}\mathrel{\mathop{\mathchar
58\relax}}V(G)\to{\mathbbm{R}},$ where ${\bf x}(u)$ is the $u$-th component of
the vector ${\bf x}.$ Hence $A{\bf x}=\lambda{\bf x}$ if and only if

$\sum\limits_{v\sim u}{\bf x}(v)=\lambda{\bf x}(u),\text{ for all }u\in V(G).$

A subdivided star $SK_{1,m}$ is obtained by subdividing all edges of the star
$K_{1,m}.$ The eigenvalues of $SK_{1,m}$ are known [brou] and we state them
below.

######  Proposition 4.

The eigenvalues of $SK_{1,m}$ for $m>1$ are
$\sqrt{m+1},~{}(1)^{m-1},~{}0,~{}(-1)^{m-1},~{}-\sqrt{m+1}.$

###### Proof.

The eigenvectors of $SK_{1,m}$ corresponding to $\pm\sqrt{m+1}$ are obtained
by assigning the values $1,~{}\pm\sqrt{m+1}$ and $m$ to all vertices of degree
equal to $1,~{}2$ and $m$, respectively. Similarly, an eigenvector
corresponding to $0$ is obtained by assigning the values $1,0$ and $-1$ to all
vertices of degree equal to $1,~{}2$ and $m$, respectively. Let $P$ be the
permutation matrix corresponding to an automorphism of $SK_{1,m}.$ If $A$ is
the adjacency matrix of $SK_{1,m}$ then $AP=PA.$ Thus, if ${\bf x}$ is an
eigenvector $SK_{1,m}$ with $A{\bf x}=\lambda{\bf x},$ then $P{\bf x}$ is also
an eigenvector corresponding to $\lambda$ as $AP{\bf x}=PA{\bf x}=\lambda
P{\bf x}.$ Thus, we get $m-1$ linearly independent eigenvectors corresponding
to $\pm 1$ as shown in Figure 2. This yields the spectra of $SK_{1,m}$. ∎

Thus, $SK_{1,m}$ is integral if and only if $\sqrt{m+1}$ is an integer. This
yields the following:

######  Corollary 2.

The graph $SK_{1,m}$ is periodic if and only if $\sqrt{m+1}$ is an integer.

Now we find the support of the vertex of degree $m$ in $SK_{1,m}$ as follows.

######  Lemma 1.

The eigenvalue support of a vertex $u$ of degree $m$ in $SK_{1,m}$ is given by

$\sigma_{u}\left(SK_{1,m}\right)=\left\\{\sqrt{m+1},~{}0,~{}-\sqrt{m+1}\right\\}.$

###### Proof.

The eigenvectors of $SK_{1,m}$ corresponding to $-\sqrt{m+1},\sqrt{m+1}$ and
$0$, as given in Proposition 4. Thus, $-\sqrt{m+1},\sqrt{m+1}$ and $0$ are
contained in the eigenvalue support of $u.$ We claim that $\pm
1\not\in\sigma_{u}\left(SK_{1,m}\right).$ It is enough to show that if ${\bf
x}_{\pm}$ is an eigenvector corresponding to $\pm 1$ then ${\bf e}_{u}^{T}{\bf
x}_{\pm}=0.$ Let $v$ be a neighbour of $u$ with ${\bf e}_{v}^{T}{\bf
x}_{\pm}\neq 0.$ If $w$ is the leaf adjacent to $v,$ then $\pm 1\cdot{\bf
e}_{w}^{T}{\bf x}_{\pm}={\bf e}_{v}^{T}{\bf x}_{\pm}$ and $\pm 1\cdot{\bf
e}_{v}^{T}{\bf x}_{\pm}={\bf e}_{w}^{T}{\bf x}_{\pm}+{\bf e}_{u}^{T}{\bf
x}_{\pm}.$ Thus ${\bf e}_{u}^{T}{\bf x}_{\pm}=0$, as desired. ∎

Lemma 1 and Proposition 2 combined with Theorem 5 yields the following result.

######  Corollary 3.

$SK_{1,m}$ is periodic at the vertex of degree $m$ for all $m>0.$ Moreover,
for all $n>0$, the graph $\overset{n}{\uplus}~{}SK_{1,m}$ with $m>1$ is
periodic at each vertex of degree $nm.$

We now include the following characterization on PGST in subdivided star.

######  Theorem 12.

The graph $\overset{2}{\uplus}~{}SK_{1,m}$ admits PGST if and only if
$\sqrt{m+1}$ is not an even integer. Moreover, if there is PGST on
$\overset{2}{\uplus}~{}SK_{1,m}$ then it occurs between every pair of twin
vertices of degree $4.$

###### Proof.

We begin with the observation on the proof of Proposition 4 that the support
of a vertex of degree $1$ and $m$ in $SK_{1,m}$ contains the eigenvalue $0.$
Using Theorem 3, we find that there is no PGST in
$\overset{2}{\uplus}~{}SK_{1,m}$ from either the vertices of degree $2$ or
$2m.$ However, the support of a vertex of degree $2$ in $SK_{1,m}$ contain the
eigenvalues $\pm\sqrt{m+1}$ and $\pm 1$ only. Now consider the following
cases.
Case I: Let $\sqrt{m+1}$ be even. If $\overset{2}{\uplus}~{}SK_{1,m}$ exhibits
PGST then $\lim\limits_{k\to\infty}\exp{\left(-2i(\pm 1)\tau_{k}\right)}=-1.$
However

$\lim\limits_{k\to\infty}\exp{\left(-2i\left(\pm\sqrt{m+1}\right)\tau_{k}\right)}=\left[\lim\limits_{k\to\infty}\exp{\left(-2i(\pm
1)\tau_{k}\right)}\right]^{\sqrt{m+1}}=1,$

a contradiction to Theorem 3. In this case, $\overset{2}{\uplus}~{}SK_{1,m}$
does not have PGST.
Case II: Suppose $\sqrt{m+1}$ is an odd integer. Considering
$\tau=\frac{\pi}{2}$, we obtain

$\exp{\left(-2i(\pm 1)\tau\right)}=-1,\text{ and
}\exp{\left(-2i\left(\pm\sqrt{m+1}\right)\tau\right)}=-1.$

By Theorem 4, $\overset{2}{\uplus}~{}SK_{1,m}$ admits PST between every pair
of twins of degree $4$.
Case III: If $m+1$ is not a perfect square then $1,\sqrt{m+1}$ are linearly
independent over ${\mathbbm{Q}}.$ Assuming
$\alpha=\frac{\sqrt{m+1}}{2}+\frac{1}{2}$ in Theorem 1, for every
$k\in{\mathbbm{N}}$, there exists integers $p_{k}$ and $q_{k}$ such that

$\left|q_{k}\sqrt{m+1}-p_{k}-\frac{\sqrt{m+1}}{2}-\frac{1}{2}\right|<\frac{1}{2\pi
k}.$

This further yields

$\left|\left(2q_{k}-1\right)\frac{\pi}{2}\cdot
2\sqrt{m+1}-\left(2p_{k}+1\right)\pi\right|<\frac{1}{k}.$

Considering $\tau_{k}=\left(2q_{k}-1\right)\frac{\pi}{2},$ we find that

$\lim\limits_{k\to\infty}\exp{\left(-2i(\pm 1)\tau_{k}\right)}=-1,\text{ and
}\lim\limits_{k\to\infty}\exp{\left(-2i\left(\pm\sqrt{m+1}\right)\tau_{k}\right)}=-1.$

By Theorem 3, we get that $\overset{2}{\uplus}~{}SK_{1,m}$ admits PGST between
every pair of twins of degree $4$.∎

##  10 Cones

A cone $G$ on a graph $H$ is a graph with vertex set $V(G)=\\{u\\}\cup V(H)$
and $G$ is obtained by adding a vertex $u\notin V(H)$ that is adjacent to all
vertices of $H$. We call $u$ the apex of $G$. It can be checked that if $H$ is
a $k$-regular graph on $m$ vertices and $G$ is a cone $K_{1}+H$, then
$\overset{2}{\uplus}~{}G$ is a (disconnected) double cone on
$\overset{2}{\uplus}~{}H$, where $\overset{2}{\uplus}~{}H$ is a $2k$-regular
graph on $2m$ vertices. That is, $\overset{2}{\uplus}~{}G$ is a graph obtained
by adding two vertices $u$ and $w$ that are adjacent to all vertices of
$\overset{2}{\uplus}~{}H$. We call $u$ and $w$ apexes of the double cone.
Periodicity, PST and PGST between apexes of disconnected double cones over
regular graphs were characterized by Kirkland et al. [kirk2]. The following is
immediate from Theorems 11(1) and 14(2a) in [kirk2].

######  Theorem 13.

Let $G$ be a cone on a $k$-regular graph on $m$ vertices with apex $u$.

  1. 1.

PST occurs between $\left(0,u\right)$ and $\left(1,u\right)$ in
$\overset{2}{\uplus}~{}G$ if and only if either (i) $k=0$ or (ii) $k>0$ and
$m=\frac{1}{4}s\left(2k+s\right)$ for some even integer $s$ such that
$\nu_{2}(2k)>\nu_{2}(s)$. Moreover, PST occurs at time
$\tau=\frac{\pi}{2\sqrt{m}}$ whenever $k=0$ and $\tau=\pi/g$ otherwise, where
$g=\operatorname{gcd}(2k,s)$.

  2. 2.

Proper PGST occurs between $\left(0,u\right)$ and $\left(1,u\right)$ in
$\overset{2}{\uplus}~{}G$ if and only if $k>0$ and $k^{2}+4m$ is not a perfect
square.

We illustrate the above theorem using the following example.

######  Example 4.

Let $G$ be a cone on $H$ with apex $u$, where $H$ is $k$-regular with $m$
vertices.

  1. 1.

If $H$ is the empty graph on $m$ vertices, then $k=0$ and $G=K_{1,m}$. By
Theorem 13(1), PST occurs between $\left(0,u\right)$ and $\left(1,u\right)$ in
$\overset{2}{\uplus}~{}G$ at $\frac{\pi}{2\sqrt{m}}$ for all $m\geq 1$.

  2. 2.

For all $m\geq 3$, let $H=C_{m}$, so that $k=2$.

    1. (a)

Let $m+1$ be a perfect square. Since $m=\frac{1}{4}s(2k+s)$, we obtain
$s=2(\pm\sqrt{m+1}-1)$. By Theorem 13(1), we get PST between
$\left(0,u\right)$ and $\left(1,u\right)$ in $\overset{2}{\uplus}~{}G$ if and
only if $m$ is odd.

    2. (b)

If $m+1$ is not a perfect square, then so is $k^{2}+4m=4(m+1)$. By Theorem
13(2), proper PGST occurs between $\left(0,u\right)$ and $\left(1,u\right)$ in
$\overset{2}{\uplus}~{}G$.

  3. 3.

Let $H=K_{r,r}$ be a complete bipartite graph. Then $k^{2}+4m=(r-1)^{2}+4(2r)$
is not a perfect square. By Theorem 13(2), proper PGST occurs between
$\left(0,u\right)$ and $\left(1,u\right)$ in $\overset{2}{\uplus}~{}G$ for all
$r\geq 2$.

##  11 Cartesian products

PST is rare, and this fact motivates us to search for new graphs with PST. It
is desirable for these graphs to be sparse, and for PST to occur between
vertices that are far apart. For the case of blow-up graphs, PST in
$\overset{2}{\uplus}~{}G$ can only occur between vertices at distance two.
Nonetheless, we may still utilize our results herein to illustrate the
construction of relatively sparse graphs using blow-up graphs, with the
property that PST occurs between vertices that are far apart. To do this, we
make use of the Cartesian product operation.

Recall that the Cartesian product of graphs $G$ and $H$, denoted $G\square H$,
is the graph with adjacency matrix $A(G)\otimes I+I\otimes A(H)$. Thus,

$U_{G\square H}(t)=U_{G}(t)\otimes U_{H}(t)$

Consequently, PST occurs between $(u,x)$ and $(v,y)$ in $G\square H$ whenever
PST occurs between $u$ and $v$ in $G$ and PST occurs between $x$ and $y$ in
$H$ at the same time. Combining this fact with [pal5, Theorem 4.2] yields the
following observations.

######  Example 5.

Suppose $\overset{2}{\uplus}~{}G$ has PST between $u$ and $v$ at time
$\tau=\frac{\pi}{g}$. Denote the hypercube of dimension $d$ by $Q_{d}$, which
is known to admit PST between vertices $x$ and $y$ that are at distance $d$.
If $g$ is an even integer, then $(\overset{2}{\uplus}~{}G)\square Q_{d}$ has
PST between $(u,x)$ and $(v,y)$ for all $d\geq 2$ at time $\frac{\pi}{2}$.
However, if $g\notin\mathbb{Q}$, then $(\overset{2}{\uplus}~{}G)\square Q_{d}$
has PGST between $(u,x)$ and $(v,y)$ for all $d\geq 2$.

######  Example 6.

From Example 4(1), we know $\overset{2}{\uplus}~{}K_{1,m}$ admits PST, say
between vertices $u$ and $v$, at time $\frac{\pi}{2\sqrt{m}}$ for all $m\geq
1$. Let $X=X(n)$ be the Cartesian product of $n$ copies of $P_{3}$, which is
known to admit PST between vertices $x$ and $y$ that are at distance $2^{n}$.
If $m=2n^{2}$, then $(\overset{2}{\uplus}~{}G)\square X$ has PST between
$(u,x)$ and $(v,y)$ at time $\frac{\pi}{\sqrt{2}}$. Otherwise,
$(\overset{2}{\uplus}~{}G)\square X$ has PGST between $(u,x)$ and $(v,y)$.

##  12 Future work

In this paper, we characterized strong cospectrality, periodicity, PST and
PGST in blow-up graphs, and applied our results to the blow-ups of complete
graphs, cycles, paths, double stars, subdivided stars and cones. Our results

One line of investigation would be to determine the quantum state transfer
properties of blow-ups of other classes of graphs such as Cayley and trees in
general.

We would also like to know whether Conjecture 1 is true. If it is not, then
for which integers $t\geq 2$ and odd primes $r$ does
$\overset{2}{\uplus}~{}P_{2^{t}r-1}$ exhibit PGST between $(0,u)$ and $(1,u)$,
whenever $u$ is a multiple of $2^{t-1}$?

Lastly, if $G$ is a cone on a non-regular graph, then when does
$\overset{2}{\uplus}~{}G$ admit periodicity and PGST?

## Acknowledgement

We thank C. van Bommel for providing the $P_{11}$ example. Hermie Monterde is
supported by the University of Manitoba Faculty of Science and Faculty of
Graduate Studies. Hiranmoy Pal is supported by Science and Engineering
Research Board (Project No. SRG/2021/000522).

## References