# Metric Learning Compensating for Projection Bias of Generalized Zero-shot
Learning

Chong Zhang2, Mingyu Jin1, Qinkai Yu3, Haochen Xue2, Xiaobo Jin 2
Corresponding Author

# Metric Learning for Projections Bias of Generalized Zero-shot Learning

Chong Zhang2, Mingyu Jin1, Qinkai Yu3, Haochen Xue2, Xiaobo Jin 2
Corresponding Author

###### Abstract

Generalized zero-shot learning models (GZSL) aim to recognize samples from
seen or unseen classes using only samples from seen classes as training data.
During inference, GZSL methods are often biased towards seen classes due to
the visibility of seen class samples during training. Most current GZSL
methods try to learn an accurate projection function (from visual space to
semantic space) to avoid bias and ensure the effectiveness of GZSL methods.
However, during inference, the computation of distance will be important when
we classify the projection of any sample into its nearest class since we may
learn a biased projection function in the model. In our work, we attempt to
learn a parameterized Mahalanobis distance within the framework of VAEGAN
(Variational Autoencoder & Generative Adversarial Networks), where the weight
matrix depends on the network’s output. In particular, we improved the network
structure of VAEGAN to leverage the discriminative models of two branches to
separately predict the seen samples and the unseen samples generated by this
seen one. We proposed a new loss function with two branches to help us learn
the optimized Mahalanobis distance representation. Comprehensive evaluation
benchmarks on four datasets demonstrate the superiority of our method over the
state-of-the-art counterparts. Our codes are available at
https://anonymous.4open.science/r/111hxr.

##  1 Introduction

With the help of computer vision, deep learning (DL) models have achieved
recent advances in image processing and have gained widespread popularity due
to their ability to provide end-to-end solutions from feature extraction to
classification. Despite their success, traditional deep learning models
require a large amount of data labelled for each category. However, collecting
large-scale markers is a challenging problem. Zero-shot learning (ZSL)
(Palatucci et al. 2009; Larochelle, Erhan, and Bengio 2008) technology
provides a good solution to this challenge. ZSL aims to train a model that can
classify objects and realize knowledge transfer from seen classes (source
classes) to unseen classes (target domain) through semantic information, which
is leveraged to bridge the gap between seen and unseen classes. In practice,
data samples from seen classes are more common than unseen classes, and it is
important to classify samples from both classes at the same time rather than
only samples from unseen classes. This task set is called generalized zero-
shot learning (GZSL).

Figure 1: Demonstration of how the Mahalanobis distance compensates for the
biased nature of GZSL in projective space, both from class-wise and instance-
wise perspective: when image instances and class descriptions are biased in
the projection space, an image from the Lion class (indicated by the circle)
will be misclassified into the Cat class (green pentagram) according to the
Euclidean distance (Part b); however, the image will be correctly classified
into the Lion class according to the Mahalanobis distance (Part c).

Most GZSL methods learn embedding/projection functions to associate seen low-
level visual feature classes with their corresponding semantic vectors. The
learned function is used to compute the distance between the prototype
representation of the class and the projected representation of the sample and
classify them to the nearest class. Since each entry of an attribute vector
represents a description of that class, class descriptions with similar
features are expected to contain similar attribute vectors in the semantic
space. However, in visual space, classes with similar properties can be quite
different. Therefore, finding a precise and suitable embedding space is a
challenging task. Otherwise, it may lead to the ambiguity problem of visual
semantics.

Semantic embeddings learn a projection function from the visual space to the
semantic space using different constraints or loss functions, with the aim of
forcing semantic embeddings belonging to the same class to map to their
ground-truth label embeddings (Rahman, Khan, and Porikli 2018; Chen et al.
2018), and then classify the given test samples by nearest neighbour search.
Visual embedding learns an inverse projection function that maps semantic
representations back into visual space and categorizes them in visual space.
The goal is to make the semantic representation close to its corresponding
visual feature (Shigeto et al. 2015). Potential space embedding projects
visual features and semantic representations into a common space $L$, i.e.,
the potential space, in order to explore some common semantic properties
across modalities (Zhang et al. 2020; Zhao et al. 2017; Yang et al. 2018). The
goal is to project visual and semantic features near each category into the
potential space. Zhang et al. proposed that an ideal potential space should
satisfy two conditions: (i) intra-class compactness and (ii) inter-class
separability (Zhang et al. 2020).

However, there is a problem of projection domain bias for the embedding
methods in the GZSL task. On the one hand, vision and semantics are located in
two different entity spaces; on the other hand, the samples of the seen and
unseen classes do not intersect, and their distributions may be different.
Therefore, for the unseen class, failure to make certain adjustments to the
embedding space can lead to the problem of projection domain bias (Fu et al.
2015; Zhao et al. 2017; Jia et al. 2019). Since GZSL methods need to recognize
both seen and unseen categories during inference and only see visual features
of seen categories during training, they are usually biased towards seen
categories. To overcome this problem, induction-based methods incorporate
additional constraints or information about the seen classes. In contrast,
transductive-based methods utilize prevalent information to mitigate the
problem of projection domain shifts (Cheraghian et al. 2020; Rahman, Khan, and
Barnes 2019; Guan, Zhao, and Lu 2019; Huo et al. 2018).

We note that once we find some projection/embedding space to which both the
images and the class semantics will be mapped, then in the inference phase,
any unknown image will be classified into the nearest class according to the
Euclidean distance in the projection space. However, we argue that the
distance measure should be more important at this point since we may be
learning a less accurate projection space. In our work, we try to learn a
parameterized Mahalanobis distance metric in the generative framework of
VAEGAN (Xian et al. 2018b), where with the Mahalanobis distance, we propose a
new loss function to help us learn an optimized Mahalanobis distance
representation. This distance can effectively influence the decision of the
classifier in the inference phase, as shown in Fig. 1, the sample point in
Part (b) is classified into the wrong class under the Euclidean distance, but
by the Mahalanobis distance, it becomes closest to its true category as shown
in Part (c).

Our key contributions can be summarized as follows:

  * •

We introduce the learning of the Mahalanobis distance metric into GZSL, which
can effectively alleviate the classification performance degradation caused by
projection bias. At the same time, we propose a new loss function with
Mahalanobis distance to help us learn an optimized Mahalanobis distance
measure.

  * •

We propose a new network architecture based on the VAEGAN framework with two
discriminative modules that learn to project samples from seen classes and
samples from (pseudo) unseen classes, respectively. This architecture can
alleviate the situation in the training phase where only samples of the seen
classes are encountered.

  * •

Extensive experimental results show that our method outperforms the state-of-
the-art methods on four benchmark datasets.

##  2 Related Work

Generalized zero-shot learning (GZSL) (Socher et al. 2013; Chen et al. 2018)
means that the trained classifier can identify the existing data categories in
the training set and distinguish data from unseen categories. The goal is to
(Morgado and Vasconcelos 2017) use the semantics or other relevant information
of seen (source) and unseen (target) classes to establish a connection between
them (Changpinyo et al. 2016), which can be mainly divided into two
categories: embedding-based methods and generative methods.

###  2.1 Embedding-based methods

The embedding-based approach (Pourpanah et al. 2022) learns an embedding space
by measuring the similarity between prototype and predicted data sample
representations that associate low-level visual features of seen categories
with semantic vectors and identify new categories. There are various types of
embedding-based methods (Pourpanah et al. 2022), including graph-based, meta-
learning, attention-based, autoencoder-based methods, and others.

Graph learning (Keshari, Singh, and Vatsa 2020; Zhao et al. 2017) leverages
machine learning techniques to extract relevant features and map properties of
graphs into feature vectors with the same dimensions in the embedding space.
Graph learning techniques (Zhao et al. 2017; Bhagat, Choudhary, and Singh
2021) have been proven to be effective paradigms in GZSL, but the
incorporation of graph-based information increases the complexity of the
model.

Meta-learning (Vanschoren 2019) extracts transferable knowledge from auxiliary
tasks to improve performance and avoid overfitting. Multiple studies (Verma,
Brahma, and Rai 2020) show that GZSL problems can be effectively solved using
meta-learning strategies. By dividing the training classes into a support set
and a query set (corresponding to seen and unseen classes, respectively),
meta-learning methods can transfer knowledge from seen to unseen classes and
alleviate the bias of the GZSL task by randomly selecting different classes
(Liu et al. 2021; Vanschoren 2019).

The attention mechanism (Xie et al. 2019; Huynh and Elhamifar 2020) uses
trainable parameters in a deep learning model to assign weights to important
parts of the input by identifying key information and fine-grained classes
with only a few regions in the image. It can effectively identify key
information and important area. Information related to performing tasks. To
further reduce bias and improve localization, this study (Yang et al. 2020)
adopted a global average pooling scheme as the aggregation mechanism. It uses
localized attributes to project local features into semantic space. This
approach ensures that the patterns obtained for unseen classes are similar to
those of seen classes, thus improving model accuracy.

Autoencoders (AEs) are neural network-based unsupervised learning methods for
representation learning. The main benefit of autoencoders (AEs) is that they
can be trained without the need for labelled data, which makes them suitable
for unsupervised learning. AEs have been widely used to solve generalized
zero-shot learning (GZSL) problems. One way to achieve this is to import the
decoder as an additional constraint to learn various mappings (Liu et al.
2018).

###  2.2 Generative Models

Generative model-based GZSL methods mitigate the bias of model predictions on
seen categories by utilizing semantic representations to classify generated
unseen samples (i.e., images or visual features). The earliest generative
ZSL/GZSL is CVAE-ZSL (Mishra et al. 2018), which employs a Conditional
Variational Autoencoder (CVAE) (Pagnoni, Liu, and Li 2018) as the generator,
compared to the traditional Variational Autoencoder (VAE) (Hou et al. 2017).
CVAE introduces conditional features that enable the generator to generate
more diverse and realistic samples to approximate the true distribution of
unseen categories. Zero-Sample Learning Semantic Embeddings (SE-ZSL) (Frome et
al. 2013) is another zero-shot learning model whose generative model
associates semantically representable category embeddings with the generated
samples to ensure that the generated samples capture the semantic features of
the categories. Since SE-ZSL may perform poorly in a few categories due to
category imbalance, Generative Zero-Sample Learning with Balanced Semantic
Embeddings (LBSE-ZSL) (Xie et al. 2022) introduces balanced semantic
embeddings to specifically address the category imbalance problem, thus
improving the learning performance of the minority class model. In addition to
the semantic information of known categories, Generative Zero Sample Learning
using Visible and Invisible Semantic Relationships (LsrGAN) (Vyas,
Venkateswara, and Panchanathan 2020) leverages the semantic relationships
between seen and unseen classes to enable the generative model to better
generate feature representations of unseen categories.

##  3 Method

In this section, we first clarify the problem we aim to solve. We then
introduce a modified VAEGAN framework. Next, we explain in detail how to
integrate the Mahalanobis distance into VAEGAN and propose a new loss to help
us learn the optimal Mahalanobis distance metric. Finally, we show how to use
Mahalanobis distance for classification in the inference stage.

###  3.1 Problem Formulation

The main goal of GZSL is to build a classifier based only on samples
$\mathcal{X}^{s}$ of seen classes $\mathcal{C}^{s}$ that can simultaneously
distinguish samples $\mathcal{X}^{u}$ from seen classes $\mathcal{C}^{s}$ and
unseen classes $\mathcal{C}^{u}$, where unseen classes only appear in the test
set, e.g. $\mathcal{C}^{s}\cap\mathcal{C}^{u}=\phi$. In addition to class
labels, current existing methods fully use class-level semantic labels
$\mathcal{S}$ (such as attributes or word2vec) to bridge the gap between seen
and unseen classes. To this end, we define the training set as
$\mathcal{D}^{tr}=\\{I_{i},\bm{s}_{i},y_{i})|I_{i}\in\mathcal{X}^{s},\bm{s}_{i}\in\mathcal{S},y_{i}\in\mathcal{C}^{s}\\}$,
where $I_{i}$ and $\bm{s}_{i}$ represent the image of the $i$-th sample and
its semantic vector, respectively. Similarly, we can represent the test set by
$\mathcal{D}^{te}=\\{(I_{i},\bm{s}_{i},y_{i})|I_{i}\in\mathcal{X}^{s}\cup\mathcal{X}^{u},\bm{s}_{i}\in\mathcal{S},y_{i}\in\mathcal{C}^{s}\cup\mathcal{C}^{u}\\}$,
where $I_{i},\bm{y}_{i}$ either belong to the seen classes or belong to the
unseen classes.

Figure 2: Framework of VAEGAN with Mahalanobis distance contains two branches,
where the upper branch generates unseen images on the seen class through a
generative network in order to simulate the classification of images from the
unseen class in the inference phase, and the lower branch learns the
projective representations of the images in the seen class directly, and the
newly proposed Mahalanobis distance-based loss function makes samples of the
same class from the same branch as close as possible while keeping samples of
the same class from different branches as far away as possible.

###  3.2 VAEGAN

VAEGAN (Xian et al. 2019) combines the power of VAE models and WGAN models
(Xian et al. 2018b) to learn the data distribution of unlabeled samples by
sharing the decoder in VAE and the generator in WGAN. We adopt this model to
simulate scenarios where samples in the inference stage may come from unseen
categories. During the training phase, the generated samples can be seen as
coming from some fake unseen class, although these unseen classes are somewhat
similar to the seen class.

#### Feature Extraction

Under the framework of VAEGAN, image and text pairs $(I_{i},\bm{s}_{i})$ are
pre-trained through Resnet-101 (He et al. 2016) and BERT model (Liu et al.
2019) to obtain their initial representation such as

$\bar{\bm{x}}_{i}=\textrm{RESNET}(I_{i})\in
R^{d},\quad\bar{\bm{s}}_{i}=\textrm{BERT}(\bm{s}_{i})\in R^{k}.$ (1)

We borrowed the Affine Transformation Fusion (ATF) from (Tao et al. 2022) to
replace the common vector concatenation operation to better fuse the two
multimodal information while keeping the dimensions unchanged. We adopt two
MLPs $\alpha(\cdot)$ and $\theta(\cdot)$ to predict the scale parameter and
offset parameter of the affine transformation, respectively, as follows

$\bm{x}_{i}=\alpha(\bar{\bm{s}}_{i})\bar{\bm{x}}_{i}+\theta(\bar{\bm{s}}_{i})\in
R^{d},$ (2)

where $\alpha(\cdot)$ will output a scalar, and $\theta(\cdot)$ will output a
$d$-dimensional vector, resulting in a fused representation of image
$\bar{\bm{x}}_{i}$ and semantics $\bar{\bm{s}}_{i}$. In the following
description, unless otherwise specified, we will omit the subscript $i$.

#### VAEGAN

A variational autoencoder (VAE) (Kingma and Welling 2013) is a deep generative
model capable of learning complex density model variables from latent data.
Given a nonlinear generative model $p_{\phi}(\bm{x}|\bm{z})$, where $\bm{x}$
is the input of the network, the latent variable $\bm{z}$ comes from the prior
distribution $p_{0}(\bm{z})$. The goal of a VAE is to approximate the
posterior probability distribution of the latent variable $\bm{z}$ by
maximizing the following variational lower bound through an inference network
$q_{\tau}(\bm{z}|\bm{x})$

$\mathcal{L}_{\phi,\tau}=\mathbb{E}_{q_{\tau}(\bm{z}|\bm{x})}[\log
p_{\phi}(\bm{x}|\bm{z})]-\textrm{KL}(q_{\tau}(\bm{z}|\bm{x})||p_{0}(\bm{z})).$
(3)

With the above consideration, we minimize the following the VAE loss (Xian et
al. 2019) with the input $\bm{x}$

$\mathcal{L}_{\textrm{VAE}}=\textrm{KL}(q_{\tau}(\bm{z}|\bm{x})||p_{0}(\bm{z}))-\mathbb{E}_{q_{\tau}(\bm{z}|\bm{x})}[\log
p_{\phi}(\bm{x}|\bm{z})],$ (4)

where $q_{\tau}(\bm{z}|\bm{x})$ is an encoder $E(x)$, which encodes an input
$\bm{x}$ to a latent variable $\bm{z}$, $p_{\phi}(\bm{x}|\bm{z})$ is a
decoder, which reconstructs the input $\bm{x}$ from the latent $\bm{z}$ and
the prior distribution $p_{0}(\bm{z})$ is assumed to be a standard normal
distribution $\mathcal{N}(0,1)$.

It is worth noting that in VAEGAN, VAE’s decoder $p_{\phi}(\bm{x}|\bm{z})$ and
GAN’s generator $G(\bm{z})$ share a network structure, so we use the
discriminator $D_{A}(\bm{x})$ to distinguish real and fake samples, where the
discriminator $D_{A}(\bm{x})$ will be optimized by minimizing the loss
function

$\displaystyle\mathcal{L}_{\textrm{WGAN}}$ $\displaystyle=$
$\displaystyle\mathbb{E}[D_{A}(\bm{x})]-\mathbb{E}[D_{A}(\tilde{\bm{x}})]$ (5)
$\displaystyle-$
$\displaystyle\lambda\mathbb{E}[\left(\|\nabla_{\tilde{\bm{x}}}D_{A}(\hat{\bm{x}})\|_{2}-1\right)^{2}],$

where $\tilde{\bm{x}}=G(\bm{z})\sim p_{\phi}(\bm{x}|\bm{z})$,
$\hat{\bm{x}}=\alpha\bm{x}+(1-\alpha)\tilde{\bm{x}}$ and $\alpha\sim U(0,1)$.

Different from the literature (Xian et al. 2019), we effectively fuse the
semantic information in the input and condition in VAEGAN through the learning
of affine transformation (see Eqn. (2)). In addition, to ensure that the
generated samples do not deviate too far from the real samples, we introduce
the following MSE loss

$\mathcal{L}_{\textrm{MSE}}=\mathbb{E}(\bm{x}-\tilde{\bm{x}})^{2}.$ (6)

###  3.3 Metric Learning with Stochastic Gradient Descent

The root cause of projection bias is that in the projection space, the samples
of the seen class and the samples of the unseen class are too close to each
other (see Fig. 1). When the samples are classified according to the distance
from the class description vector, the samples from the unseen class are
likely to be classified into seen classes. To this end, we extend the
traditional Euclidean distance metric to a general Mahalanobis distance metric
so that under this distance metric, samples from unseen classes will be far
away from the class vectors of seen classes, thereby improving the
classification performance of GZSL.

Given two vectors $X$, $Y$ from projected space, we calculate the Mahalanobis
distance between $X$ and $Y$ by the following formula

$d_{M}^{2}(X,Y)=(X-Y)^{T}M(X-Y),$ (7)

where $M$ is a positive definite matrix, which can clearly represent the
correlation between the various components of the vector.

For the output $\tilde{\bm{x}}$ of VAEGAN and the image $I$, we simulate the
projection output of unseen class samples and seen class samples respectively
by two discriminators

$\displaystyle X$ $\displaystyle=$ $\displaystyle D_{A}(\tilde{\bm{x}})\in
R^{k},$ (8) $\displaystyle Y$ $\displaystyle=$ $\displaystyle D_{B}(I)\in
R^{k}.$ (9)

We stitch $N$ samples by row to get a $2N\times k$ matrix $\tilde{X}$ through
the output $X$ and $Y$ of the two branches. In order to learn the optimal
matrix $M$ under the framework of gradient descent, we represent $M$ in the
following form

$M=[\textrm{cov}(\tilde{X})]^{+}+\epsilon I,$ (10)

where $R^{+}$ It represents the generalized inverse matrix of the matrix $R$.
Note that $M$ is actually a function of network structure parameters, and it
should be a symmetrical positive definite distance, thus ensuring that the
distance (7) is an effective distance.

Given a batch of samples, we propose a new loss function below so that the
Mahalanobis distances of the projection outputs of the different branches are
as far as possible, and the Mahalanobis distances of the projection outputs
from the same branch are as close as possible

$\mathcal{L}_{M}=-\log\sum_{i\neq
j}\left(d^{2}_{M}(X_{i},Y_{j})-d^{2}_{M}(X_{i},X_{j})\right),$ (11)

where $X_{i}$ and $Y_{j}$ are calculated by Eqn. (8) and (9), respectively.

Ultimately, our algorithm minimizes the following loss function via stochastic
gradient descent (as shown in Alg. 1)

$\mathcal{L}=\mathcal{L}_{\textrm{WGAN}}+\lambda_{1}\mathcal{L}_{\textrm{VAE}}+\lambda_{2}\mathcal{L}_{\textrm{MSE}}+\lambda_{3}\mathcal{L}_{\textrm{M}},$
(12)

where $\lambda_{1}$,$\lambda_{2}$ and $\lambda_{3}$ are hyperparameters.

It is worth noting that since the matrix $M$ depends on the outputs of the two
branches, $M$ is constantly updated during model iteration. We use $M^{*}$
obtained in the last iteration as the optimal metric for the inference phase.

Algorithm 1 VAEGAN with Mahalanobis Metric

1: Input: A batch of images and class-attributes pairs $\langle
I_{i},\bm{s}_{i},y_{i}\rangle$

2: for $i=1,2,\cdots$ do

3: $\bar{\bm{x}}_{i}=\textrm{RESNET}(I_{i})$

4: $\bar{\bm{s}}_{i}=\textrm{BERT}(\bm{s}_{i})$

5:
$\bm{x}_{i}=\alpha(\bar{\bm{s}}_{i})\bar{\bm{x}}_{i}+\theta(\bar{\bm{s}}_{i})$

6: Encode: $\bm{z}_{i}=E(\bm{x}_{i})$

7: Decode: $\tilde{\bm{x}}_{i}=G(\bm{z}_{i})$

8: Branch A: $X_{i}=D_{A}(\tilde{\bm{x}}_{i})$

9: Branch B: $Y_{i}=D_{B}(I_{i})$

10: end for

11:
$\tilde{X}=\textrm{cat}((X_{1},X_{2},\cdots,Y_{1},Y_{2},\cdots),\textrm{dim}=0)$

12: $M=[\textrm{cov}(\tilde{X})]^{+}+\epsilon I$

13: Compute the loss function $\mathcal{L}$ with Eqn. (12)

return $\mathcal{L}$

When $M=I$, then the distance metric $d^{2}_{M}(X,Y)$ becomes an Euclidean
distance. Since M is a positive definite distance, it has the following
Cholesky decomposition form $M=LL^{T}$, and thus we have

$d^{2}_{M}(X,Y)=\|L^{T}(X-Y)\|_{2}^{2}.$ (13)

Unlike the projection bias problem in which the projection to vector $X$ is
learned, our network optimizes the projection matrix of the difference $X-Y$
of any two vectors $X$ and $Y$.

###  3.4 Inference with Mahalanobis Metric

In the inference stage (as shown in Alg. 2), for any image $I$, it and all
class description text $s\in\mathcal{X}^{s}\cup\mathcal{X}^{u}$ are input into
the upper branch of the network as multiple pairs, and the semantic
representation $X$ of the class prototype is obtained through the
discriminator $A$; at the same time, the image is directly passed through the
lower branch of the network to obtain an embedded representation $Y$ of the
image. Finally, according to the Mahalanobis distance between the image and
the class prototype, the image will be classified into the nearest class.

Algorithm 2 Inference with Mahalanobis Metric

1: Input: Any given image $I$

2: $\textrm{dist}=[]$

3: Branch B: $Y=D_{B}(I)$

4: for $s\in\mathcal{X}^{s}\cup\mathcal{X}^{u}$ do

5: $\bar{\bm{x}}=\textrm{RESNET}(I)$

6: $\bar{\bm{s}}=\textrm{BERT}(\bm{s})$

7: $\bm{x}=\alpha(\bar{\bm{s}})\bar{\bm{x}}+\theta(\bar{\bm{s}})$

8: Encode: $\bm{z}=E(\bm{x})$

9: Decode: $\tilde{\bm{x}}=G(\bm{z})$

10: Branch A: $X=D_{A}(\tilde{\bm{x}})$

11: $d=d^{2}_{M^{*}}(X,Y)$

12: dist.append($d$)

13: end for

14: $c=\operatorname*{arg\,max}(\textrm{dist})$

return $c$

##  4 Experiments

We first describe four popular public datasets and experimental implementation
details. We then describe and compare the experimental implementation details
with certain classical approaches. Finally, we conduct an ablation study to
test the effectiveness of three important components of the work.

###  4.1 Datasets and Evaluation Details

We adopted four public datasets including Caltech-UCSD Birds-200-2011 (CUB)
(Wah et al. 2011), Animals with Attribute 1 (AWA1) (Lampert, Nickisch, and
Harmeling 2009), Animals with Attribute 2 (AWA2) (Xian et al. 2018a), SUN
Database (SUN) (Xiao et al. 2010), and four other datasets. The CUB dataset
contains 11,788 images of 200 species of birds, with about 60 images from each
category. The AWA1 and AWA2 datasets each collect 50 different animal
categories with about 40 to 60 images, and the AWA1 and AWA2 datasets have
30,475 and 37,322 images, respectively. The SUN dataset has images from 717
different scene categories, with about 200 to 500 images per category,
totalling about 14,340. In dividing the dataset, we followed the conventional
division method of GZSL datasets.

In the evaluation method, we used the harmonic mean $H$ to evaluate the
recognition results on both visible and invisible class data simultaneously,
which is often used to evaluate the classification performance of the GZSL
task and is calculated as follows

$H=\frac{2\times U\times S}{U+S},$ (14)

where $U$ and $S$ denote the classification accuracy on unseen classes and
seen class data, respectively.

###  4.2 Implementation Details

For basic visual features and visual extraction, we refer to VAEGAN (Xian et
al. 2019) and improve the original VAEGAN in the feature generation part. We
use pre-trained Resnet101(He et al. 2016) and Bert Tokenizer(Devlin et al.
2018) to extract the visual and semantic features of images and generate
$1000$-dimensional visual feature vectors and $768$-dimensional semantic
feature vectors, respectively. These two vectors are fused together and
converted into a $1*3*256*256$ tensor for use in the encoding stage of VAEGAN.
Subsequently, we obtain a latent semantic representation of size $500$. The
samples generated by the latent semantic representation pass through the
discriminator A to obtain a vector with a length of $900$. Similarly, the
original image also gets a $900$-dimensional vector through the discriminator
B to facilitate our calculation of the Mahalanobis distance. The ADAM (Kingma
and Ba 2014) optimizer is used in our algorithm, where the learning rate is
set to $10^{-3}$. Finally, the initial values of the hyperparameters
$\lambda_{1}$, $\lambda_{2}$ and $\lambda_{3}$ are $1.0$, $1.0$ and $1.0$,
respectively.

###  4.3 Comparison with State-of-the-Art Methods

In this section, we select recent results of the state of the art in GZSL
tasks, including ALE (Akata et al. 2015), f-CLSWGAN (Xian et al. 2018b), LiGAN
(Li et al. 2019), CE-GZSL (Han et al. 2021), DCRGAN-TMM (Ye et al. 2021), HSVA
(Chen et al. 2021), DEM (Zhang, Xiang, and Gong 2017), CADA-VAE (Schonfeld et
al. 2019), DAZLE (Huynh and Elhamifar 2020), BSeGN (Xie et al. 2022),
f-VAEGAN-D2 (Xian et al. 2019) and CMC-GAN (Yang et al. 2023), see Tab. 1 for
details.

Tab. 1 lists the result comparison between our method and other classical
methods. Specifically, in our method, the H-score can reach 67.2% on the CUB
dataset, 71.6% on AWA1, 70.9% on AWA2, and 45.9% on SUN. Compared with the
original VAEGAN model (Xie et al. 2022): Our method improves the H-score of
the model from 58.0% to 67.2% on the CUB dataset, from 67.4% to 70.9% on the
AWA2, and finally, the SUN data set is increased from 42.9% to 45.9%. The
above results show that our proposed method outperforms the state-of-the-art
methods in all evaluated datasets and achieves significant improvements,
especially in the $H$-score. We attribute the above results to two aspects: 1)
Under the generative framework of VAEGAN, we simulate the output from seen
samples and the output of unseen samples through two branches and make the
samples of the two branches as far as possible through the loss function, at
the same time, the samples of the same branch are as close as possible so that
the seen class and the (pseudo) unseen class can be separated as much as
possible; 2) Mahalanobis distance can help us correct wrong decisions when
projection bias occurs, thereby improving Classification performance on seen
and unseen classes.

Table 1: Comparison of our method with other state-of-the-art methods on four datasets Model | CUB | AWA1 | AWA2 | SUN
---|---|---|---|---
| U | S | H | U | S | H | U | S | H | U | S | H
ALE | 23.7 | 62.8 | 34.4 | 16.8 | 76.1 | 27.5 | 14.0 | 81.8 | 23.9 | 21.8 | 33.1 | 26.3
f-CLSWGAN | 31.73 | 64.34 | 42.50 | 61.41 | 59.63 | 60.51 | 29.85 | 76.60 | 42.96 | 42.6 | 36.6 | 39.4
LiGAN | 46.5 | 57.9 | 51.6 | 52.6 | 76.3 | 62.3 | 54.3 | 68.5 | 60.6 | 42.9 | 37.8 | 40.2
CE-GZSL | 54.17 | 67.24 | 61.39 | 65.3 | 73.4 | 69.1 | 63.1 | 78.6 | 70.0 | 48.8 | 38.6 | 43.1
DCRGAN-TMM | 40.61 | 54.12 | 46.39 | 32.21 | 65.03 | 43.08 | 51.59 | 63.85 | 57.07 | 40.49 | 34.61 | 37.32
HSVA | 52.2 | 59.7 | 55.7 | 61.1 | 75.2 | 67.4 | 57.4 | 81.1 | 67.3 | 48.6 | 39.0 | 43.3
DEM | 19.6 | 57.9 | 29.2 | 32.8 | 84.7 | 47.3 | 30.5 | 86.4 | 45.1 | 19.6 | 57.9 | 29.2
f-VAEGAN-D2 | 48.4 | 60.1 | 53.6 | 62.9 | 63.3 | 63.5 | 57.6 | 70.6 | 63.5 | 45.1 | 38.0 | 41.3
CADA-VAE | 51.6 | 53.5 | 52.4 | 57.3 | 72.8 | 64.1 | 55.8 | 75 | 63.9 | 47.2 | 35.7 | 40.6
DAZLE | 56.7 | 59.6 | 58.1 | - | - | - | 60.3 | 75.7 | 67.1 | 52.3 | 24.3 | 33.2
CMC-GAN | 52.6 | 65.1 | 58.2 | 63.2 | 70.6 | 66.7 | - | - | - | 48.2 | 40.8 | 44.2
BSeGN | 55.3 | 60.8 | 58.0 | - | - | - | 59.3 | 78.0 | 67.4 | 48.9 | 38.3 | 42.9
Our model | 57.1 | 81.6 | 67.2 | 62.9 | 83.1 | 71.6 | 62.2 | 82.3 | 70.9 | 39.6 | 52.7 | 45.9

It is worth noting that the weight matrix in the Mahalanobis distance does not
introduce additional parameters, it only depends on the structural parameters
of the network, which limits the complexity of the model to some extent and
reduces the risk of model overfitting.

###  4.4 Ablation Study

#### Mahalanobis distance metric/Euclidean distance metric

Table 2: Performance of Our method with Euclidean Distance/Mahalanobis Distance Model | CUB | AWA1 | AWA2 | SUN
---|---|---|---|---
| U | S | H | U | S | H | U | S | H | U | S | H
$+$ Euclidean Distance | 16.9 | 41.6 | 24.0 | 18.1 | 46.3 | 26.1 | 19.4 | 43.2 | 26.8 | 9.7 | 18.4 | 12.4
$+$ Mahalanobis Distance | 57.1 | 81.6 | 67.2 | 62.9 | 83.1 | 71.6 | 62.2 | 82.3 | 70.9 | 39.6 | 52.7 | 45.9

The Mahalanobis distance plays a key role in our algorithm. To verify its
effectiveness, we compare it with ordinary Euclidean distance. Since the
Euclidean distance does not contain any parameters, we remove the $L_{M}$ loss
during training. The comparison results of using Euclidean distance and
Mahalanobis distance on the four data sets are shown in Tab. 2.

From the experimental results, the Euclidean distance measure is very poorly
represented under our model framework, which also shows the important role of
the Mahalanobis distance. But in fact, the VAEGAN baseline architecture as
shown in Tab. 3 also uses Euclidean distance, where the performance
degradation on the 4 datasets is not very obvious. The Mahalanobis distance
takes into account the interaction between the sample attribute features in
the projection space, and it is continuously accumulated and updated in the
iterative process, which alleviates the projection offset problem in the GZSL
problem.

#### Multi-branch Discriminators/Single-branch Discriminator

In our work, we improve the structure of VAEGAN, in particular, we introduce
another branch to better learn features that are discriminative between seen
and unseen classes (see Tab. 3).

Table 3: Ablation study on our method with augmented discriminator Model | CUB | AWA1 | AWA2 | SUN
---|---|---|---|---
| U | S | H | U | S | H | U | S | H | U | S | H
VAEGAN with Discriminator A | 46.4 | 62.1 | 53.1 | 66.3 | 61.2 | 63.6 | 54.1 | 69.8 | 61.0 | 38.0 | 45.7 | 41.5
$+$ Augmented Discriminator B | 57.1 | 81.6 | 67.2 | 62.9 | 83.1 | 71.6 | 62.2 | 82.3 | 70.9 | 39.6 | 52.7 | 45.9
Table 4: Performance comparison of our method under different information fusion Model | CUB | AWA1 | AWA2 | SUN
---|---|---|---|---
| U | S | H | U | S | H | U | S | H | U | S | H
$+$ Concatenation operation | 56.0 | 81.6 | 66.4 | 61.0 | 82.3 | 70.1 | 61.1 | 80.4 | 69.4 | 33.7 | 52.2 | 41.0
$+$ Affine transformation fusion (ATF) | 57.1 | 81.6 | 67.2 | 62.9 | 83.1 | 71.6 | 62.2 | 82.3 | 70.9 | 39.6 | 52.7 | 45.9

According to the conducted experiments, our model slightly outperforms the
baseline of VAEGAN in all categories except unseen categories in the AWA1
dataset. This suggests that branch B of our model alleviates the projection
bias/shift problem of samples to some extent and helps alleviate the problem
related to semantic imbalance.

#### Affine Transformation Fusion/Concatenation Operation

The fusion of multiple modalities such as images and texts is usually fused by
the concatenation operation. However, multiple modalities of the same sample
are interrelated, and affine transformation fusion makes the change of text
representation directly affect the mapping function to the image, realizing a
closer information fusion between the two. In order to verify the
effectiveness of the Affine Transformation Fusion (ATF) module under our model
framework, we list the results of their comparison in Tab. 4. According to the
experimental results, the affine transformation function shows a slight
improvement over models that only capture image features and semantic features
for all categories except the SUN dataset. As a result, the information fusion
effect of this module is basically equivalent to the general concatenation
operation.

##  5 Conclusion

The biased projection is an important challenging problem in GZSL. In our
work, we introduce the Mahalanobis distance into the VAEGAN framework. To this
end, we use two branches to learn the samples of the seen class and the
samples of the (pseudo) unseen class, respectively, and propose a new loss
function such that The projected space is learned to be more discriminative
for samples from unseen and seen classes. In particular, the weight matrix of
the Mahalanobis distance does not introduce additional parameters, which
limits the expressive ability of the model and avoids the possibility of
further overfitting. Finally, our extensive experimental evaluation shows that
our proposed method outperforms the state-of-the-art methods on four benchmark
datasets. Our contribution has significant implications for advancing zero-
shot learning and provides a promising avenue for future research in this
area.

## References

  * Akata et al. (2015) Akata, Z.; Perronnin, F.; Harchaoui, Z.; and Schmid, C. 2015.  Label-embedding for image classification.  _IEEE transactions on pattern analysis and machine intelligence_ , 38(7): 1425–1438.
  * Bhagat, Choudhary, and Singh (2021) Bhagat, P.; Choudhary, P.; and Singh, K. M. 2021.  A novel approach based on fully connected weighted bipartite graph for zero-shot learning problems.  _Journal of Ambient Intelligence and Humanized Computing_ , 12: 8647–8662.
  * Changpinyo et al. (2016) Changpinyo, S.; Chao, W.-L.; Gong, B.; and Sha, F. 2016.  Synthesized classifiers for zero-shot learning.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 5327–5336.
  * Chen et al. (2018) Chen, L.; Zhang, H.; Xiao, J.; Liu, W.; and Chang, S.-F. 2018.  Zero-shot visual recognition using semantics-preserving adversarial embedding networks.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 1043–1052.
  * Chen et al. (2021) Chen, S.; Xie, G.; Liu, Y.; Peng, Q.; Sun, B.; Li, H.; You, X.; and Shao, L. 2021\.  Hsva: Hierarchical semantic-visual adaptation for zero-shot learning.  _Advances in Neural Information Processing Systems_ , 34: 16622–16634.
  * Cheraghian et al. (2020) Cheraghian, A.; Rahman, S.; Campbell, D.; and Petersson, L. 2020.  Transductive zero-shot learning for 3d point cloud classification.  In _Proceedings of the IEEE/CVF winter conference on applications of computer vision_ , 923–933.
  * Devlin et al. (2018) Devlin, J.; Chang, M.-W.; Lee, K.; and Toutanova, K. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_.
  * Frome et al. (2013) Frome, A.; Corrado, G. S.; Shlens, J.; Bengio, S.; Dean, J.; Ranzato, M.; and Mikolov, T. 2013.  Devise: A deep visual-semantic embedding model.  _Advances in neural information processing systems_ , 26.
  * Fu et al. (2015) Fu, Y.; Hospedales, T. M.; Xiang, T.; and Gong, S. 2015.  Transductive multi-view zero-shot learning.  _IEEE transactions on pattern analysis and machine intelligence_ , 37(11): 2332–2345.
  * Guan, Zhao, and Lu (2019) Guan, J.; Zhao, A.; and Lu, Z. 2019.  Extreme reverse projection learning for zero-shot recognition.  In _Computer Vision–ACCV 2018: 14th Asian Conference on Computer Vision, Perth, Australia, December 2–6, 2018, Revised Selected Papers, Part I 14_ , 125–141. Springer.
  * Han et al. (2021) Han, Z.; Fu, Z.; Chen, S.; and Yang, J. 2021.  Contrastive embedding for generalized zero-shot learning.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , 2371–2381.
  * He et al. (2016) He, K.; Zhang, X.; Ren, S.; and Sun, J. 2016.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 770–778.
  * Hou et al. (2017) Hou, X.; Shen, L.; Sun, K.; and Qiu, G. 2017.  Deep feature consistent variational autoencoder.  In _2017 IEEE winter conference on applications of computer vision (WACV)_ , 1133–1141. IEEE.
  * Huo et al. (2018) Huo, Y.; Ding, M.; Zhao, A.; Hu, J.; Wen, J.-R.; and Lu, Z. 2018.  Zero-shot learning with superclasses.  In _Neural Information Processing: 25th International Conference, ICONIP 2018, Siem Reap, Cambodia, December 13–16, 2018, Proceedings, Part III 25_ , 460–472. Springer.
  * Huynh and Elhamifar (2020) Huynh, D.; and Elhamifar, E. 2020.  Fine-grained generalized zero-shot learning via dense attribute-based attention.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , 4483–4493.
  * Jia et al. (2019) Jia, Z.; Zhang, Z.; Wang, L.; Shan, C.; and Tan, T. 2019.  Deep unbiased embedding transfer for zero-shot learning.  _IEEE Transactions on Image Processing_ , 29: 1958–1971.
  * Keshari, Singh, and Vatsa (2020) Keshari, R.; Singh, R.; and Vatsa, M. 2020.  Generalized zero-shot learning via over-complete distribution.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , 13300–13308.
  * Kingma and Ba (2014) Kingma, D. P.; and Ba, J. 2014.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_.
  * Kingma and Welling (2013) Kingma, D. P.; and Welling, M. 2013.  Auto-encoding variational bayes.  _arXiv preprint arXiv:1312.6114_.
  * Lampert, Nickisch, and Harmeling (2009) Lampert, C. H.; Nickisch, H.; and Harmeling, S. 2009.  Learning to detect unseen object classes by between-class attribute transfer.  In _2009 IEEE conference on computer vision and pattern recognition_ , 951–958. IEEE.
  * Larochelle, Erhan, and Bengio (2008) Larochelle, H.; Erhan, D.; and Bengio, Y. 2008.  Zero-data learning of new tasks.  In _AAAI_ , 2, 3.
  * Li et al. (2019) Li, J.; Jing, M.; Lu, K.; Ding, Z.; Zhu, L.; and Huang, Z. 2019.  Leveraging the invariant side of generative zero-shot learning.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 7402–7411.
  * Liu et al. (2018) Liu, Y.; Gao, Q.; Li, J.; Han, J.; and Shao, L. 2018.  Zero shot learning via low-rank embedded semantic autoencoder.  In _IJCAI_ , 9, 10.
  * Liu et al. (2019) Liu, Y.; Ott, M.; Goyal, N.; Du, J.; Joshi, M.; Chen, D.; Levy, O.; Lewis, M.; Zettlemoyer, L.; and Stoyanov, V. 2019.  Roberta: A robustly optimized bert pretraining approach.  _arXiv preprint arXiv:1907.11692_.
  * Liu et al. (2021) Liu, Z.; Li, Y.; Yao, L.; Wang, X.; and Long, G. 2021.  Task aligned generative meta-learning for zero-shot learning.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , 10, 8723–8731.
  * Mishra et al. (2018) Mishra, A.; Krishna Reddy, S.; Mittal, A.; and Murthy, H. A. 2018.  A generative model for zero shot learning using conditional variational autoencoders.  In _Proceedings of the IEEE conference on computer vision and pattern recognition workshops_ , 2188–2196.
  * Morgado and Vasconcelos (2017) Morgado, P.; and Vasconcelos, N. 2017.  Semantically consistent regularization for zero-shot recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 6060–6069.
  * Pagnoni, Liu, and Li (2018) Pagnoni, A.; Liu, K.; and Li, S. 2018.  Conditional variational autoencoder for neural machine translation.  _arXiv preprint arXiv:1812.04405_.
  * Palatucci et al. (2009) Palatucci, M.; Pomerleau, D.; Hinton, G. E.; and Mitchell, T. M. 2009.  Zero-shot learning with semantic output codes.  _Advances in neural information processing systems_ , 22.
  * Pourpanah et al. (2022) Pourpanah, F.; Abdar, M.; Luo, Y.; Zhou, X.; Wang, R.; Lim, C. P.; Wang, X.-Z.; and Wu, Q. J. 2022.  A review of generalized zero-shot learning methods.  _IEEE transactions on pattern analysis and machine intelligence_.
  * Rahman, Khan, and Barnes (2019) Rahman, S.; Khan, S.; and Barnes, N. 2019.  Transductive learning for zero-shot object detection.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 6082–6091.
  * Rahman, Khan, and Porikli (2018) Rahman, S.; Khan, S.; and Porikli, F. 2018.  A unified approach for conventional zero-shot, generalized zero-shot, and few-shot learning.  _IEEE Transactions on Image Processing_ , 27(11): 5652–5667.
  * Schonfeld et al. (2019) Schonfeld, E.; Ebrahimi, S.; Sinha, S.; Darrell, T.; and Akata, Z. 2019.  Generalized zero-and few-shot learning via aligned variational autoencoders.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , 8247–8255.
  * Shigeto et al. (2015) Shigeto, Y.; Suzuki, I.; Hara, K.; Shimbo, M.; and Matsumoto, Y. 2015.  Ridge regression, hubness, and zero-shot learning.  In _Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2015, Porto, Portugal, September 7-11, 2015, Proceedings, Part I 15_ , 135–151. Springer.
  * Socher et al. (2013) Socher, R.; Ganjoo, M.; Manning, C. D.; and Ng, A. 2013.  Zero-shot learning through cross-modal transfer.  _Advances in neural information processing systems_ , 26.
  * Tao et al. (2022) Tao, M.; Tang, H.; Wu, F.; Jing, X.-Y.; Bao, B.-K.; and Xu, C. 2022.  Df-gan: A simple and effective baseline for text-to-image synthesis.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 16515–16525.
  * Vanschoren (2019) Vanschoren, J. 2019.  Meta-learning.  _Automated machine learning: methods, systems, challenges_ , 35–61.
  * Verma, Brahma, and Rai (2020) Verma, V. K.; Brahma, D.; and Rai, P. 2020.  Meta-learning for generalized zero-shot learning.  In _Proceedings of the AAAI conference on artificial intelligence_ , 04, 6062–6069.
  * Vyas, Venkateswara, and Panchanathan (2020) Vyas, M. R.; Venkateswara, H.; and Panchanathan, S. 2020.  Leveraging seen and unseen semantic relationships for generative zero-shot learning.  In _Computer Vision–ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part XXX 16_ , 70–86. Springer.
  * Wah et al. (2011) Wah, C.; Branson, S.; Welinder, P.; Perona, P.; and Belongie, S. 2011.  CUB_200_2011.  Technical Report CNS-TR-2011-001, California Institute of Technology.
  * Xian et al. (2018a) Xian, Y.; Lampert, C. H.; Schiele, B.; and Akata, Z. 2018a.  Zero-shot learning—a comprehensive evaluation of the good, the bad and the ugly.  _IEEE transactions on pattern analysis and machine intelligence_ , 41(9): 2251–2265.
  * Xian et al. (2018b) Xian, Y.; Lorenz, T.; Schiele, B.; and Akata, Z. 2018b.  Feature generating networks for zero-shot learning.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 5542–5551.
  * Xian et al. (2019) Xian, Y.; Sharma, S.; Schiele, B.; and Akata, Z. 2019.  f-vaegan-d2: A feature generating framework for any-shot learning.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , 10275–10284.
  * Xiao et al. (2010) Xiao, J.; Hays, J.; Ehinger, K. A.; Oliva, A.; and Torralba, A. 2010.  Sun database: Large-scale scene recognition from abbey to zoo.  In _2010 IEEE computer society conference on computer vision and pattern recognition_ , 3485–3492. IEEE.
  * Xie et al. (2019) Xie, G.-S.; Liu, L.; Jin, X.; Zhu, F.; Zhang, Z.; Qin, J.; Yao, Y.; and Shao, L. 2019.  Attentive region embedding network for zero-shot learning.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , 9384–9393.
  * Xie et al. (2022) Xie, G.-S.; Zhang, X.-Y.; Xiang, T.-Z.; Zhao, F.; Zhang, Z.; Shao, L.; and Li, X. 2022.  Leveraging Balanced Semantic Embedding for Generative Zero-Shot Learning.  _IEEE Transactions on Neural Networks and Learning Systems_.
  * Yang et al. (2023) Yang, F.-E.; Lee, Y.-H.; Lin, C.-C.; and Wang, Y.-C. F. 2023.  Semantics-guided intra-category knowledge transfer for generalized zero-shot learning.  _International Journal of Computer Vision_ , 131(6): 1331–1345.
  * Yang et al. (2018) Yang, G.; Liu, J.; Xu, J.; and Li, X. 2018.  Dissimilarity representation learning for generalized zero-shot recognition.  In _Proceedings of the 26th ACM international conference on Multimedia_ , 2032–2039.
  * Yang et al. (2020) Yang, S.; Wang, K.; Herranz, L.; and van de Weijer, J. 2020.  Simple and effective localized attribute representations for zero-shot learning.  _arXiv preprint arXiv:2006.05938_.
  * Ye et al. (2021) Ye, Z.; Hu, F.; Lyu, F.; Li, L.; and Huang, K. 2021.  Disentangling semantic-to-visual confusion for zero-shot learning.  _IEEE Transactions on Multimedia_ , 24: 2828–2840.
  * Zhang et al. (2020) Zhang, L.; Wang, P.; Liu, L.; Shen, C.; Wei, W.; Zhang, Y.; and Van Den Hengel, A. 2020.  Towards effective deep embedding for zero-shot learning.  _IEEE Transactions on Circuits and Systems for Video Technology_ , 30(9): 2843–2852.
  * Zhang, Xiang, and Gong (2017) Zhang, L.; Xiang, T.; and Gong, S. 2017.  Learning a deep embedding model for zero-shot learning.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2021–2030.
  * Zhao et al. (2017) Zhao, B.; Sun, X.; Yao, Y.; and Wang, Y. 2017.  Zero-shot learning via shared-reconstruction-graph pursuit.  _arXiv preprint arXiv:1711.07302_.


# It is better to be semi-regular when you have a low degree

T. Kolokolnikov  Department of Mathematics and Statistics, Dalhousie
University Halifax, Nova Scotia, B3H3J5, Canada<EMAIL_ADDRESS>
###### Abstract

We study the algebraic connectivity for several classes of random semi-regular
graphs. For large random semi-regular bipartite graphs, we explicitly compute
both their algebraic connectivity and as well as the full spectrum
distribution. For an integer $d\in\left[3,7\right]$, we find families of
random semi-regular graphs that have higher algebraic connectivity than a
random $d$-regular graphs with the same number of vertices and edges. On the
other hand, we show that regular graphs beat semi-regular graphs when $d\geq
8.$ More generally, we study random semi-regular graphs whose average degree
is $d$, not necessary an integer. This provides a natural generalization of a
$d$-regular graph in the case of a non-integer $d.$ We characterise their
algebraic connectivity in terms of a root of a certain 6th-degree polynomial.
Finally, we construct a small-world-type network of average degree 2.5 with a
relatively high algebraic connectivity. We also propose some related open
problems and conjectures.

##  1 Introduction

Algebraic connectivity (AC; also called the spectral gap) of a graph is a
fundamental property that measures how fast information diffuses throughout
the graph fiedler1973algebraic ; de2007old . It corresponds to the second
smallest eigenvalue of the graph Laplacian matrix (the smallest eigenvalue is
always zero). In many applications, it is desirable to maximize the algebraic
connectivity (i.e. speed of diffusion) subject to certain constraints; this
and related problems have a long history ghosh2006growing ; wang2008algebraic
; sydney2013optimizing ; olfati2005ultrafast ; ghosh2006growing ;
kolokolnikov2015maximizing ; ogiwara2015maximizing ; shahbaz2021algebraic .
For example in communications, the “cost” of a network increases with the
number of links. It is therefore desirable to have as few edges as possible,
while at the same time maximizing the algebraic connectivity. This leads to a
natural question: _For a fixed average degree_ $d,$_what is the graph that
maximizes algebraic connectivity as the number of vertices_
$n\rightarrow\infty?$

Figure 1: Types of graphs considered in this work. (a) Random semi-regular
bipartite graph with $(d_{1},d_{2})=(2,3)$. (b) Random semi-regular graph with
$(p,d_{1},d_{2})=(0.4,2,3).$ Both graphs have the same average degree of
$d=2.4$. (c) Small-world network consisting of a ring and with edges added at
random between the odd-numbered vertices. It has an average degree of $d=2.5.$

Numerous papers address various aspects of this question, see e.g.
olfati2005ultrafast ; kolokolnikov2015maximizing ; ogiwara2015maximizing ;
shahbaz2021algebraic . This is one of those situations where the best answer
is elusive mosk2008maximum , but a decent answer can be found relatively
quickly ghosh2006growing ; wang2008algebraic . Graphs with high algebraic
connectivity are related to expander graphs, and are important in many
applications hoory2006expander ; lubotzky2012expander . In this paper, we
study the algebraic connectivity of _sparse_ random graphs in the case when
the number of edges $m$ scales linearly with the number of vertices $n,$ i.e.
$m=O(n)$. In other words, we fix the average degree $d=2m/n=O(1)$ while
letting $n\rightarrow\infty.$

It is well known that a random Erdos-Renyi graph (where $m$ edges are taken at
random) needs $O(n\log n)$ edges to be fully connected erdos ;
alon2004probabilistic , and as such, they are poor candidates for maximizing
algebraic connectivity in this sparse regime (since AC of a disconnected graph
is zero). A good candidate are $d-$regular graphs for which every vertex has
degree $d$. It is well known that random regular $d-$graphs have an algebraic
connectivity that asymptotes to $\mu\sim d-2\sqrt{d-1}$ as
$n\rightarrow\infty$ with fixed $d$ mckay1981expected ; alon1986eigenvalues ;
broder1987second ; friedman1991second ; nilli2004tight . For integer $d\geq
3,$ this is quantity is bounded away from zero, which assures these graphs
have good expander properties wormald1999models ; murty2003ramanujan . A
natural question is whether one can do better than regular graph, but without
“too much work” (in, say, $O(n)$ time). In this paper we give an affirmative
answer when $d\leq 7$: we introduce a class of semi-regular random graphs
(whose vertices have degree either $d_{1}$ or $d_{2}\neq d_{1}$) which are as
easy to construct as random $d$-regular graphs, but which have better AC.

Another question is whether “expander-type” graphs (which we define to be
graphs with AC bounded away from 0 as $n\rightarrow\infty$) are possible when
the average degree $d$ is less than 3, with $n\rightarrow\infty.$ For $2<d<3,$
the answer is yes, and it is provided by semi-regular graphs of degrees $2$
and $3,$ whose average degree is $2+p$ (with $0<p<1)$. We show that AC of such
graphs asymptotes to $\mu\sim p^{2}/4$ in the limit of small $p$ and large
$n$, with $n\rightarrow\infty$ independent of $p$. (The answer is no when
$d\leq 2$ since any graph needs at least $n-1$ edges to be connected).

Our first result is on random semi-regular _bipartite_ graphs, where each
vertex has degree either $d_{1}$ or $d_{2}$, and we compute their asymptotic
AC in the limit $n\rightarrow\infty.$ In particular, we will exhibit a family
of semi-random bipartite graphs having the same average degree as random
$d$-regular graphs, but which have higher algebraic connectivity when $d\leq
7.$

Before stating our result, let us define what we mean by such graphs. Consider
a bipartite graph with one part having $n_{1}$ vertices of degree $d_{1},$ and
the second part having $n_{2}$ vertices of degree $d_{2},$ such that every
edge is between these two parts, and no edges are within each part. Then
$n_{1}d_{1}=n_{2}d_{2}.$ Such graph has $n=n_{1}+n_{2}$ vertices so that

$n_{1}=\frac{d_{2}}{d_{1}+d_{2}}n,\ \ \ n_{2}=\frac{d_{1}}{d_{1}+d_{2}}n$
(1.1)

and therefore the average degree is

$d=\frac{2d_{1}d_{2}}{d_{1}+d_{2}}.$ (1.2)

We call such a graph a $(d_{1},d_{2})$ semi-regular bipartite graph. We now
introduce the following random model.

Random semi-regular bipartite (RSRB) graph model: Take two bags. In the first
bag, put $d_{1}$ copies of $n_{1}$ vertices labelled $1\ldots n_{1}.$ In the
second bag, put $d_{2}$ copies of $n_{2}$ vertices labelled $n_{1}+1\ldots
n_{1}+n_{2}.$ Start with an empty graph of $n_{1}+n_{2}$ vertices. Then
randomly pick two vertices without replacement – one from each bag – and add
an edge between them to the graph. Repeat until the bags are empty. Refer to
Figure 1(a) and Matlab code in Appendix A.

We remark that this model (and the theory below) generally allows for multiple
edges. If desired, they can be eliminated through a random rewiring
postprocessing step111Given a multiple edge $(a,b)$ or a self loop ($a=b$),
choose another edge $\left(c,d\right)$ at random. Then replace edges
$\left(a,b\right)$ and $\left(c,d\right)$ by edges $\left(a,c\right)$ and
$\left(b,d\right).$ Repeat until all multiple edges/loops are eliminated. This
operation preserves degree distribution and edge count.. These cases are
sufficiently rare that the postprocessing step does not effect the asymptotic
results in the large $n$ limit. We now state our main results for RSRB graphs.

######  Main Result 1.1.

Consider a $\left(d_{1},d_{2}\right)$ RSRB graph. In the limit
$n\rightarrow\infty,$ its spectrum density asymptotes to

$\rho(x)=\left\\{\begin{array}[c]{c}\frac{1}{\pi}\frac{d_{1}d_{2}}{d_{1}+d_{2}}\frac{\sqrt{(x^{2}-r_{-}^{2})(r_{+}^{2}-x^{2})}}{\left(d_{1}d_{2}-x^{2}\right)\left|x\right|},\
\ \left|x\right|\in\left(r_{-},r_{+}\right)\\\
\frac{\left|d_{2}-d_{1}\right|}{d_{1}+d_{2}}\delta\left(x\right),\ \
\left|x\right|<r_{-}\\\ 0,\ \ \ \left|x\right|>r_{+}\end{array}\right.$ (1.3)

where $\delta$ is the Dirac-delta function and

$r_{\pm}=\left(d_{1}+d_{2}-2\pm\sqrt{\left(d_{1}+d_{2}-2\right)^{2}-\left(d_{2}-d_{1}\right)^{2}}\right)^{1/2}.$
(1.4)

In other words, the number of eigenvalues inside any interval
$\left(a,b\right)$ asymptotes to $\int_{a}^{b}\rho(x)dx$ as
$n\rightarrow\infty.$

Moreover, its algebraic connectivity asymptotes to

$\mu\sim\frac{d_{1}+d_{2}}{2}-\left(\left(\frac{d_{2}-d_{1}}{2}\right)^{2}+r_{+}^{2}\right)^{1/2},\
\ \ n\gg 1$ (1.5)

Figure 2:  (a) Full spectrum of random semi-regular bipartite graph with
$\left(d_{1},d_{2}\right)=\left(2,3\right)$. Numerics correspond to the
histograph of eigenvalues of a single such graph with 1000 vertices, computed
numerically using Matlab. Asymptotics corresponds to the formula (1.3). The
height of the lollypop corresponds to the weight delta function at the origin.
(b) Comparison of algebraic connectivity between $\left(3,3\right)$ regular
bipartite, $\left(2,6\right)$ semi-regiular bipartite graphs, and the
asymptotic theory. The two classes have the same number of vertices and edges,
and $\left(2,6\right)$ is 15% better than (3,3) (both for asymptotics and
numerics).

Figure 2(a) shows the shape of the distribution (1.3) for the case $d_{1}=2,\
\ d_{2}=3$ (having an average degree of $d=2.4$), and compares it to an
numerical histogram of eigenvalues of a 1000-vertex graph for this case. Very
good agreement is observed.

Note that in the case $d_{1}=d_{2},$ formula (1.3) reduces to the well-known
Mackay distribution of the spectrum of a regular graph mckay1981expected :

$\rho(x)=\left\\{\begin{array}[c]{c}\frac{1}{\pi}\frac{d}{2}\frac{\sqrt{4(d-1)-x^{2}}}{d^{2}-x^{2}},\
\ \left|x\right|<2\sqrt{d-1}\\\ 0,\ \
\left|x\right|>2\sqrt{d-1}.\end{array}\right.$ (1.6)

Moreover, formula (1.5) simplifies to the classical result $\mu\sim
d-2\sqrt{d-1}$ for the algebraic connectivity of a random regular graph of $d$
vertices 222This also shows that a random regular graph and random bipartite
regular graphs have the same algebraic connectivity, at least to leading order
in $n.$.

Consider a random cubic graph $\left(d_{1}=d_{2}=3\right)$ and contrast it
with an RSRB graph with $d_{1}=2,\ d_{2}=6.$ Both cases have the same average
degree of $d=3.$ Formula (1.5) gives the asymptotic values of $\mu\sim
0.17157$ for the former, and $\mu\sim 0.19577,$ for the latter. _Thus,_
$\left(2,6\right)$_RSRB graph is about 15% better than a random cubic graph
with respect to its expander properties, while having the same number of
vertices and edges._ Figure 2(b) shows a histogram for $\mu$ of 1000 randomly
constructed such graphs, comparing these two cases with $n=2000$. Very good
agreement between numerics and asymptotics is observed in both cases.

More generally, the following table shows all possible combinations of
$d_{1},d_{2}$ such that $d=\frac{2d_{1}d_{2}}{d_{1}+d_{2}}$ is an integer
between 3 and 8, and the corresponding value of $\mu$ (1.5).

All RSRB graphs with integer average degree $d=3,\ldots,8$
---
$d$ | 3 | 4 | 5 | 6 | 7 | 8
$d_{1}$ | 3 | 2 | 4 | 3 | 5 | 3 | 6 | 4 | 7 | 4 | 8 | 6 | 5
$d_{2}$ | 3 | 6 | 4 | 6 |  5 | 15 | 6 | 12 | 7 | 28 | 8 | 12 | 20
$\mu_{\text{asympt}}$ | 0.1715 | 0.1957 | 0.5358 | 0.5535 | 1 | 1.0890 | 1.5278 | 1.5587 | 2.1010 | 2.1435 | 2.7084 | 2.6887 | 2.6671
$\mu_{\text{numerics}}$ | 0.178 | 0.205 | 0.553 | 0.572 | 1.027 | 1.122 | 1.565 | 1.596 | 2.150 | 2.205 | 2.766 | 2.745 | 2.729
std | 0.006 | 0.006 | 0.011 | 0.010 | 0.015 | 0.017 | 0.018 | 0.018 | 0.021 | 0.020 | 0.026 | 0.022 | 0.022
diff % | 3.8% | 4.7% | 3.1% | 3.2% | 2.7% | 3.0% | 2.4% | 2.4% | 2.3% | 2.87% | 2.1% | 2.1% | 2.2%

The row $\mu_{\text{asympt}}$ is the asymptotic formula given by (1.5). Row
$\mu_{\text{numerics}}$ corresponds to Monte Carlo simulations of $\mu$. It
shows the average $\mu$ for 200 randomly chosen RSRB graphs with $n=1000$
edges. The row “diff %” is
$\frac{\mu_{\text{numerics}}-\mu_{\text{asympt}}}{\mu_{\text{asympt}}}\times
100$. Uniformly good agreement with between asymptotics and numerics is
observed.

Parameters with higher AC are in shown in bold. For $d\leq 7,$ RSRB with
$d_{1}\neq d_{2}$ have higher algebraic connectivity than the $d$-regular
graph. On the other hand, for $d\geq 8$, $d$-regular graphs win.

It is interesting to note that for any integer $d\geq 3,$ equation (1.2)
always has a solution with integers $2\leq d_{1}<d_{2}.$ When $d$ is prime,
this solution is unique and is given by $d_{1}=(d+1)/2,$
$d_{2}=d\left(d+1\right)/2.$ More generally, the number of such solutions is
precisely the number of pythegorean triples of leg $d$ (sequence A046079 in
OEIS).

RSRB graphs above have a constraint $n_{1}d_{1}=n_{2}d_{2}.$ In particular the
minimum attainable average degree of such graphs is $d=2.4$ corresponding to
$\left(d_{1},d_{2}\right)=\left(2,3\right).$ We can remove this constraint by
instead introducing the probability of having degree $d_{1}$ or $d_{2}$ as
follows.

Random semi-regular (RSR) model: Given $p,d_{1},d_{2},$ and $n,$ let
$n_{1}=\left\lfloor\left(1-p\right)n\right\rfloor$ and let $n_{2}=n-n_{1}.$ In
the same bag, put $d_{1}$ copies of $n_{1}$ vertices labelled $1\ldots n_{1}$
and $d_{2}$ copies of $n_{2}$ vertices labelled $n_{1}+1\ldots n.$ Create
edges by drawing two vertices from the bag at random (without replacement),
until only one or zero vertices are left in the bag. See Appendix A for Matlab
code.

An example of RSR graph is shown in Figure 1(b). Note that such a graph has an
average degree of $d=\left(1-p\right)d_{1}+pd_{2}$. We have the following.

######  Main Result 1.2.

Consider a $\left(p,\ d_{1},d_{2}\right)$ random semi-regular graph. Let

$F(R,x)=x\left(d_{{2}}-d_{{1}}\right)\left(1-Rx\right)p+\left(R{x}^{2}(d_{{2}}-1)-1\right)\left({R}^{2}{x}^{2}\left(d_{{1}}-1\right)+Rx\left(d_{{2}}-d_{1}\right)-R+1\right).$
(1.7)

Let $x$ be the smallest root of the system $F=0=\partial F/\partial R.$Then in
the limit $n\rightarrow\infty,$ the AC is given by $\mu=d_{2}-1/x.$

In general, eliminating $R$ from the system $F=0=\partial F/\partial R$ is a
straightforward computer algebra computation using a resultant, and yields in
a 6th degree polynomial for $x$. It is too ugly to write down here for general
$d_{1},d_{2}$ – see Appendix A for Maple code. In the case $d_{1}=2,d_{2}=3,$
RSR graph has average degree $2+p,$ and $\mu$ is the smallest root of

$0=\mu\left(\mu-4\right)\left(\mu^{2}-4\mu-1\right)+2\mu\left(3\mu^{3}-33\mu^{2}+89\mu-19\right)p+\left(-15\mu^{2}-30\mu+1\right)p^{2}+8p^{3}.$
(1.8)

Figure 3 compares $\mu$ given by (1.8) with numerical computations of $\mu$
for randomly chosen $\left(p,2,3\right)$ RSR graphs. Note that the numerical
result approaches the asymptotic value of $\mu$ as the number of edges $n$ is
increased.

Figure 3: Comparison between RSR, RSRB asymptotics, and RSR numerics, with
average degree $2<d\leq 3.$ Numerics represent AC of 1000 randomly chosen RSR
graphs with $p\in(0,1)$ and $(d_{1},d_{2})=(2,3)$. Here, $\mu$ is plotted
against $d=2+p$. Asymptotics for RSR correspond to roots of (1.8). Asymptotics
for RSRB are given by (1.5).

The following table gives the value of $\mu$ for several choices of
$p,d_{1},d_{2}$ for which the average degree $d=4,$ and comparison with
numerics:

$\text{RSR\ model with }d=4$
---
$d_{1}$ | 4 | 3 | 3 | 2 | 2 | 2
$d_{2}$ | 4 | 5 | 6 | 5 | 6 | 7
$p$ |  | 0.5 | 1/3 | 2/3 | 0.5 | 0.4
$\mu_{\text{asympt}}$ | 0.5359 | 0.44261 | 0.39162 | 0.3333 | 0.25352 | 0.20748
$\mu_{\text{numerics}}$ | 0.551 | 0.488 | 0.451 | 0.286 | 0.217 | 0.174
std | 0.010 | 0.020 | 0.022 | 0.062 | 0.051 | 0.045
diff % | 2.8% | 10% | 15% | -14% | -14% | -19%

Here, $\mu_{\text{asympt}}$ is as given by Main Result 1.2;
$\mu_{\text{numerics}}$ is the average of 200 simulations with $n=1000.$ As
apparent from this table, RSR model performs worse than RSRB of average degree
4 (including $4-$regular graphs). This appears to be true for any average
degree $d$. However one advantage of RSR graphs is that they produce graphs
with an average degree $2<d<3,$ with $\mu$ bounded away from zero as
$n\rightarrow\infty.$ The smallest average degree that RSRB model can have is
2.4 corresponding to $\left(d_{1},d_{2}\right)=\left(2,3\right).$ In fact,
(1.8) shows that $\mu\sim p^{2}/4$ when the average degree is $2+p$ with
$d_{1}=2,d_{2}=3,$ and $0<p\ll 1.$

##  2 Derivation of main results

Derivation of spectral density (1.3). Following wigner ; mckay1981expected  we
use the trace method. It is based on the fact that
$\operatorname{trace}(A^{s})=\sum_{j=1}^{s}\lambda_{j}^{s}.$Define
$\phi_{s}=\frac{1}{n}\operatorname{trace}(A^{s}).$ Then $\phi_{s}$ represents
the average number of closed walks of length $s$ on the graph whose adjacency
matrix is $A$. In the limit $n\rightarrow\infty,$ the eigenvalue distribution
therefore satisfies

$\int x^{s}\rho(x)dx=\phi_{s}.$ (2.9)

As in wigner ; mckay1981expected , the derivation consists of (a) computing
$\phi_{s};$ and (b) inverting the integral equation (2.9) to determine
$\rho(x).$

To compute $\phi_{s},$ we write

$\phi_{s}=\frac{d_{1}}{d_{1}+d_{2}}\phi_{A,s}+\frac{d_{2}}{d_{1}+d_{2}}\phi_{B,s},$

where $\phi_{A,s}$ is the number of closed walks of length $s$ starting from a
vertex of degree $d_{2},$ and $\phi_{B,s}$ is that number for vertices of
degree $d_{1}.$ A key insight mckay1981expected  that allows the asymptotic
determination of $\phi_{A,s}$ and $\phi_{B,s}$ is that locally, a large random
regular graph looks like a tree because the probability of encountering a
cycle of length $s$ is vanishinly small as $n\rightarrow\infty$ (for fixed
$s$). The same is true of semi-regular random graphs. For the RSRB graphs,
each successive level alternates between vertices of degree $d_{1}$ and
$d_{2}.$ We therefore decompose these trees as illustrated in the following
diagram, for the case $d_{1}=2$ and $d_{2}=3$:

$\displaystyle d_{1}=2,\ \ d_{2}=3$

Accordingly, $\phi_{A,s}$ and $\phi_{B,s}$ satisfy the recursion

$\displaystyle\phi_{A,s}$
$\displaystyle=d_{2}\sum_{j=0}^{s-2}\phi_{A,j}A_{s-2-j},\ \ \ \
\phi_{B,s}=d_{1}\sum_{j=0}^{s-2}\phi_{B,j}B_{s-2-j},$ $\displaystyle A_{s}$
$\displaystyle=\left(d_{1}-1\right)\sum_{j=0}^{s-2}A_{j}B_{s-2-j},\ \ \ \ \
B_{s}=\left(d_{2}-1\right)\sum_{j=0}^{s-2}B_{j}A_{s-2-j},$ (2.10)

with $A_{0}=B_{0}=\phi_{A,0}=\phi_{B,0}=1.$ Let $A(x)=\sum A_{s}x^{s}$ be the
generating function for $A_{s}$ and similarly for $B,\ \phi_{A},\ \phi_{B},\
\phi.$ From recursion relations (2.10), the corresponding generating functions
satisfy

$\displaystyle A$ $\displaystyle=1+\left(d_{1}-1\right)x^{2}AB,$
$\displaystyle B$ $\displaystyle=1+\left(d_{2}-1\right)x^{2}BA,$
$\displaystyle\phi_{A}$ $\displaystyle=1+d_{2}x^{2}\phi_{A}A,$ (2.11)
$\displaystyle\phi_{B}$ $\displaystyle=1+d_{1}x^{2}\phi_{B}B,$
$\displaystyle\phi$
$\displaystyle=\frac{d_{1}}{d_{1}+d_{2}}\phi_{A}+\frac{d_{2}}{d_{1}+d_{2}}\phi_{B}$

Solving (2.11), while keeping in mind that $\phi\left(0\right)=1,$we find that

$\phi(x)=\frac{d_{1}d_{2}}{d_{1}+d_{2}}\frac{\frac{d_{1}+d_{2}}{d_{1}d_{2}}-\sqrt{\left(d_{2}-d_{1}\right)^{2}x^{4}+\left(4-2d_{1}-2d_{2}\right)x^{2}+1}-1}{d_{1}d_{2}x^{2}-1}.$

In principle, $\phi_{s}$ can be computed from $\phi(x)$ by Taylor-expanding
near the origin; the first few terms are $\phi_{0}=1,\
\phi_{2}=2\frac{d_{1}d_{2}}{d_{1}+d_{2}},\
\phi_{4}=2\frac{d_{1}d_{2}}{d_{1}+d_{2}}\left(d_{1}+d_{2}-1\right)$. In
mckay1981expected  explicit computation of $\phi_{s}$ was combined with
Tchebychev polynomials to compute the McKay distribution for $d$-regular
random graphs. Here, we use a simpler and more powerful technique using
complex variables introduced in longoria2020pascal .

Write $\phi_{s}$ using Cauchy’s integral formula as

$\phi_{s}=\int z^{-s-1}\phi(z)\frac{dz}{2\pi i},$

where the integration is around a circle $\left|z\right|=\varepsilon$, with
$\varepsilon$ sufficiently small to avoid any branch cuts of $\phi.$ Using the
fact that $\phi(z)$ is even, we then have

$\displaystyle\phi_{s}$
$\displaystyle=\frac{1}{\pi}\int_{0}^{\pi}\varepsilon^{-s}\phi\left(\varepsilon
e^{i\theta}\right)e^{-si\theta}d\theta$
$\displaystyle=\frac{i}{\pi}\int_{-1/\varepsilon}^{1/\varepsilon}\frac{1}{x}\phi\left(\frac{1}{x}\right)x^{s}dx$

Taking $\varepsilon\rightarrow 0$ and recalling (2.9) we obtain

$\int\rho(x)x^{s}dx=\frac{i}{\pi}\int_{-\infty}^{\infty}\frac{1}{x}\phi\left(\frac{1}{x}\right)x^{s}dx.$

This yields the formula for $\rho,$ namely

$\rho(x)=-\frac{1}{\pi}\operatorname{Im}\left\\{\frac{1}{x}\phi\left(\frac{1}{x}\right)\right\\}.$
(2.12)

This formula was derived in longoria2020pascal  using an equivalent technique
(Stieltjes inversion). Next we compute

$\frac{1}{x}\phi\left(\frac{1}{x}\right)=\frac{1}{x}\frac{d_{1}d_{2}}{d_{1}+d_{2}}\frac{\frac{d_{1}+d_{2}}{d_{1}d_{2}}x^{2}-\sqrt{(x^{2}-r_{-}^{2})(x^{2}-r_{+}^{2})}-x^{2}}{d_{1}d_{2}-x^{2}},$
(2.13)

where $r_{\pm}$ are given by (1.4). It follows that
$\operatorname{Im}\left\\{\frac{1}{x}\phi\left(\frac{1}{x}\right)\right\\}=0$
for $\left|x\right|\notin\left(r_{-},r_{+}\right)$ and $x\neq 0.$ On the other
hand when $\left|x\right|\in\left(r_{-},r_{+}\right)$ we obtain

$\rho(x)=\frac{1}{\pi}\frac{1}{\left|x\right|}\frac{d_{1}d_{2}}{d_{1}+d_{2}}\frac{\sqrt{(r_{+}^{2}-x^{2})(x^{2}-r_{-}^{2})}}{d_{1}d_{2}-x^{2}},\
\ \left|x\right|\in\left(r_{-},r_{+}\right).$ (2.14)

This recovers the formula (1.3) except for the delta mass at the center which
is due to the singularity there. To compute the weight of the delta mass, one
can integrate the overall density and impose that $\int\rho=1.$ While the
exact integration of (2.14) is possible, it is easier and more instructive to
compute the number of zero eigenvalues directly as follows.

Suppose that $d_{2}>d_{1}.$ Label the components of the eigenvector
$x_{1}\ldots x_{n_{1}}$ and $y_{1}\ldots y_{n_{2}},$ corresponding to vertices
of degree $d_{1}$ and $d_{2},$ respectively. A zero eigenvalue satisfies
$\sum_{x_{j}\in nbr(y_{k})}x_{j}=0$, $k=1\ldots n_{2}$ and $\sum_{y_{j}\in
nbr(x_{k})}y_{j}=0$, $k=1\ldots n_{1}.$ Look for solutions of the form where
$y_{j}=0$, $j=1\ldots n_{2}.$ This corresponds to solving $n_{2}$ linear
equations $\sum_{x_{j}\in nbr(y_{k})}x_{j}=0$, for the $n_{1}$ unknows
$x_{1}\ldots x_{n_{1}}.$ This is an under-determined system, since
$n_{2}<n_{1}.$ Generically, it has $n_{1}-n_{2}$ independent solutions.
Therefore the weight of the delta function at zero should be
$\frac{n_{1}-n_{2}}{n}.$ Using (1.2) yields
$\frac{n_{1}-n_{2}}{n}=\frac{d_{2}-d_{1}}{d_{1}+d_{2}},$ which recovers the
weight of the delta function in (1.3). We also verified using computer algebra
that this indeed agrees with the full integration of (2.14), namely, that
$\int_{r_{-}}^{r_{+}}\rho(x)dx=\frac{d_{1}}{d_{1}+d_{2}}$, $d_{2}>d_{1},$ so
that indeed $\int_{-\infty}^{\infty}\rho=1$. This completes the derivation of
the spectral density (1.3).

Finally, another derivation of the delta weight, as pointed out by James
Mingo, is to use Proposition 3.8 in mingo2017free . It says that if
$\frac{1}{x}\phi\left(\frac{1}{x}\right)$ has a singularity at $x=a,$ then the
associated measure $\rho(x)$ has a delta mass at $x=a$ whose weight is given
by $\lim_{x\rightarrow
a}\left|\left(x-a\right)\frac{1}{x}\phi\left(\frac{1}{x}\right)\right|.$ Here,
$a=0$ and the mass weight is then given by $\lim_{x\rightarrow
0}\left|\phi\left(\frac{1}{x}\right)\right|=\frac{d_{1}d_{2}}{d_{1}+d_{2}}\frac{\sqrt{r_{-}^{2}r_{+}^{2}}}{d_{1}d_{2}}=\frac{\left|d_{2}-d_{1}\right|}{d_{1}+d_{2}}$
in agreement with direct computation. $\blacksquare$

Derivation of AC formula for RSRB (1.5) Next we derive the formula for
algebraic connectivity (1.5). For $d$-regular graphs, the Laplacian graph is
given by $dI-A$ where $I$ is the identity and $A$ is the adjacency matrix.
This allows to characterize the AC in terms of second-largest eigenvalue
$\lambda$ of $A$: $\mu=d-\lambda.$ Of course this is not true if the graph is
not regular. The trick is to regularize the graph by adding enough self-loops
to vertices until all vertices have the same degree. Each self-loops counts as
a single additional edge (i.e. adding a loop to vertex $j$ corresponds to
adding ”1” to the $j$-th diagonal entry of the associated adjacency matrix)
and crucially, adding self-loops does not change the Laplacian of the graph.

For a $\left(d_{1},d_{2}\right)$ semi-regular graph, assume that $d_{1}<d_{2}$
and add $d_{2}-d_{1}$ loops to all vertices of degree $d_{1}.$ This results in
a $d_{2}$-regular graph with loops. As before let $\phi_{s}$ be the number of
closed walks of size $s$. Let $\lambda$ be the _local expansion rate_ , that
is, the rate at which $\phi_{s}$ grows:
$\lambda=\lim\limits_{s\rightarrow\infty}\phi_{s+1}/\phi_{s}$. Then by analogy
to regular graphs, the AC is given by $\mu=d_{2}-\lambda.\,\ $To compute
$\lambda,$ we decompose closed loops similarly to (2.11). The decomposition
now has loops as illustrated below:

$\displaystyle d_{1}=2,\ d_{2}=3$

Correspondingly, the associated generating functions satisfy

$\displaystyle A$
$\displaystyle=1+(d_{2}-d_{1})xA+\left(d_{1}-1\right)x^{2}AB,\ \ \ $
$\displaystyle B$ $\displaystyle=1+\left(d_{2}-1\right)x^{2}BA,$
$\displaystyle\phi_{A}$ $\displaystyle=1+d_{2}x^{2}\phi_{A}A,$ (2.15)
$\displaystyle\phi_{B}$
$\displaystyle=1+x\left(d_{2}-d_{1}\right)\phi_{B}+d_{1}x^{2}\phi_{B}B,$
$\displaystyle\phi$
$\displaystyle=\frac{d_{1}}{d_{1}+d_{2}}\phi_{A}+\frac{d_{2}}{d_{1}+d_{2}}\phi_{B}$

To determine AC, it suffices to determine the growth rate of $\phi_{s}$. This
growth rate is in turn determined by the locations of singularities in the
associated generating functions wilf2005generatingfunctionology . In
particular, if $\sum\phi_{s}z^{s}=g(z)+h(z)(z-r)^{p}$, where $p$ is non-
integer and $g,h$ analytic, then $\phi_{s}$ grows with the rate $r^{-1}:\ $in
other wors, $\phi_{s+1}/\phi_{s}\rightarrow r^{-1}$ as $s\rightarrow\infty.$
The location of the singularity can be found without solving the full system,
and corresponds to the smallest root of the discriminant of the system. To
illustrate this, consider the Catalan numbers
$c_{n}=\frac{1}{n+1}\left(\begin{array}[c]{c}2n\\\ n\end{array}\right)$ whose
generating function satisfies $c=1+xc^{2}.$ Explicitly,
$c(x)=\frac{1-\sqrt{1-4x}}{2x},$ and has a singularity at $x=1/4,$
corresponding to the zero of the discriminant of the quadratic $xc^{2}-c+1=0.$
It follows that $c_{n+1}/c_{n}\rightarrow 4$ as $n\rightarrow\infty$ (indeed
more precise asymptotics $c_{n}\sim\frac{1}{\sqrt{\pi}}4^{n}n^{-3/2}$ can also
be derived from its generating function, although here, we only need the
growth rate).

Let us now get back to the system (2.15). Eliminating $B,$ we find that $A$
satisfies a quadratic,

$\left(d_{2}-1\right)\left(x\left(d_{2}-d_{1}\right)-1\right)x^{2}A^{2}+\left[x^{2}\left(d_{2}-d_{1}\right)-x\left(d_{2}-d_{1}\right)+1\right]A-1=0.$

Setting its discriminant to zero, we obtain a quartic polynomial for $x$,
namely

$\left({d}_{1}-{d}_{2}\right)^{2}{x}^{4}+2\left({d}_{1}+{d}_{2}-2\right)\left({d}_{2}-d_{1}\right){x}^{3}+\left((d_{1}-d_{2})^{2}-2\left({d}_{1}+{d}_{2}-2\right)\right){x}^{2}+2\left({d}_{1}-{d}_{2}\right)x-1=0.$
(2.16)

The expansion rate is then $\lambda=1/x,$ so that $\mu=d_{2}-1/x$.
Substituting $x=1/(\mu-d_{2})$ into (2.16), one obtains a 4th degree
polynomial for $\mu,$

$0=\mu^{4}-2\left(d_{1}+d_{2}\right)\mu^{3}+\left(\left(d_{1}+d_{2}\right)^{2}+2d_{1}d_{2}-2d_{1}-2d_{2}+4\right)\mu^{2}+2\left(d_{1}+d_{2}\right)\left(d_{1}+d_{2}-2-d_{1}d_{2}\right)\mu+\left(d_{1}d_{2}-d_{1}-d_{2}\right)^{2}$

Shift this polynomial to eliminate the $\mu^{3}$ term by substituting
$\mu=y+\frac{d_{1}+d_{2}}{2}.$ Magically, it simultaneously elimintes the
$\mu^{1}$ term resulting in a quadratic for $y^{2}$:

$0=y^{4}+\left(4-2\left(d_{1}+d_{2}\right)-\left(d_{2}-d_{1}\right)^{2}/2\right)y^{2}+\frac{\left(d_{2}-d_{1}\right)^{2}\left(d_{1}+d_{2}\right)}{2}+\frac{\left(d_{2}-d_{1}\right)^{4}}{16}$

Solving for $y$ using quadratic formula yields the solution (1.5).
$\blacksquare$

Derivation of Result 1.2. Again, we compute the average number of closed walks
of length $s$, $\phi_{s}.$ As before, each vertex looks like a tree locally.
Each child in this tree has probability $\left(1-p\right)$ chance of having
degree $d_{1},$ and probability $p$ of having degree $d_{2}.$ As in the
derivation of (1.5), assume that $d_{1}\leq d_{2}$, and add $d_{2}-d_{1}$
self-loops to each vertex of degree $d_{1}.$ The walks on these trees then
decompose according to the following diagram (here given in the case
$d_{1}=2,\ d_{2}=3$):

$\displaystyle d_{1}=2,\ \ d_{2}=3$

The corresponding generating function $\phi(x)=\sum\phi_{s}x^{s}$ solves the
equations

$\displaystyle A$
$\displaystyle=1+x\left(d_{2}-d_{1}\right)A+\left(d_{1}-1\right)x^{2}AR$
$\displaystyle B$ $\displaystyle=1+\left(d_{2}-1\right)BR$ $\displaystyle R$
$\displaystyle=\left(1-p\right)A+pB$ $\displaystyle\phi_{A}$
$\displaystyle=1+x\left(d_{2}-d_{1}\right)\phi_{A}+d_{1}x^{2}\phi_{A}R$ (2.17)
$\displaystyle\phi_{B}$ $\displaystyle=1+d_{2}x^{2}\phi_{B}R$
$\displaystyle\phi$ $\displaystyle=(1-p)\phi_{A}+p\phi_{B}.$

Eliminating $A$ and $B$ yields a cubic $F(R;x)=0$ given by (1.7). The AC is
then given by $\mu=d_{2}-1/x$, where $x$ is the singularity of $R(x)$ that is
closest to the origin. By implicit function theorem, this happens when
$F_{R}=0.$ In other words, $x$ satisfies $F=0=\partial F/\partial
R.\blacksquare$

##  3 Discussion and open problems

We computed asymptotics of AC for two models of semiregular random graphs:
either RSR or RSRB models. While RSR model is shown to have smaller AC than a
random $d$-regular graph with the same average degree, we found that RSRB
model has _higher_ AC than $d$-regular when $d\leq 7.$

Ramunajan expander graphs are defined hoory2006expander ; lubotzky2012expander
as being $d$-regular graphs whose algebraic connectivity is at least
$d-2\sqrt{d-1}$. As illustrated in Figure 2(b) (see also Figure 9 in
hoory2006expander  and related table there), a random $d-$regular graph has a
decent chance of being Ramunajan graph (around 66% when $d=3$ as
$n\rightarrow\infty$ according to simulations in hoory2006expander ). We can
extend the definition of Ramunajan exander graphs as being any graph of
_average_ degree $d$ whose AC is at least $d-2\sqrt{d-1}.$ When $d=3,$ an
RSRB$\ \left(2,6\right)$ graph is actually Ramunajan graph with very high
probability as $n\rightarrow\infty.$ This is illustrated in Figure 2(b) where
$n\approx 2000.$ Out of 1000 randomly chosen such graphs, only _one_ had AC
less than $d-2\sqrt{d-1}=0.1716.$

We relied on careful but formal power series computations. While the results
were validated using numerics, a rigorous analysis of the results in this
paper is an open problem. Related to this, it is an open question to estimate
the accuracy of asymptotics as a function of $n.$ In particular, the accuracy
appears to be significantly degraded for the RSR graphs when $d_{1}$ and
$d_{2}$ far from each other. Take for example the case
$\left(d_{1},d_{2}\right)=\left(2,6\right)$. Intriguingly, the distribution
for AC appears to have multiple peaks and does not necessary concentrate
around the mean, as illustrated in Figure 4 (note that this does not appear to
be the case for RSRB graphs as figure 2(b) illustrates). We pose this as an
open problem.

Challenge 1. _Describe the full distribution of AC, particularly for RSR
graphs. Explain why it can be multi-peaked when_ $d_{1}\neq d_{2}$.

Figure 4: Distribution of AC for RSR graphs with
$\left(d_{1},d_{2}\right)=\left(2,6\right)$ and with $p$ as indicated. Average
degree $d=2+4p$ is also indicated. We used $n=500$ nodes, and 1000
simulations. $\mu_{\mbox{numeric}}$ is the average of the distribution whereas
$\mu_{\mbox{asym}}$ is the asymptotics according to Main Result 1.2. Note the
multi-peaked shape of the distribution, and the fact that the distribution
does not concentrate around the mean when $d\leq 5.$

Another class of graphs having high algebraic connectivity are the complete
bipartite graphs $K_{b,n-b}$, which have AC $\mu=b$ (with $b<n/2$). The
average degree of such a graph asymptotes to $d=2b$ as $n\rightarrow\infty,$
so that $\mu\sim d/2.$ Contrast this to $d$-regular random graphs ($\mu\sim
d-2\sqrt{d-1}$). As was noted in kolokolnikov2015maximizing , $K_{d/2,n-d/2}$
have higher AC than the $d$-regular graphs (for asymptotically same number of
edges) provided that $d<15$ (since $d/2>d-2\sqrt{d-1}$ in that case) while the
converse is true when $d\geq 15.$ While complete bipartite graphs have a
relatively high AC when $d<15$, they are also fragile, in the sense that
removing any single edge causes AC to decrease by one. Random graphs are more
robust with respect to edge deletions as they seem to have some redundancy
built-in.

Consider the limit of large $d_{2}$ for the RSRB model. From (1.2) and (1.5),
one obtains that $d\sim 2d_{1}$ and $\mu\sim\frac{d}{2}-1$ as
$d_{2}\rightarrow\infty.$ This is one less than the AC of complete bipartite
graph $K_{d/2,n-d/2}$ (which also has average degree $d$ as
$n\rightarrow\infty)$. More generally, let $\mu_{d_{1},d_{2}}$ be as in (1.5)
and let $\mu_{d}=d-2\sqrt{d-1},$ where $d=2d_{1}d_{2}/(d_{1}+d_{2})$ is the
average degree. It can be shown that $\mu_{d_{1},d_{2}}<\mu_{d}$ for any
$d_{1},d_{2}$ when $d\geq 10.$ This discussion suggests the following
question.

Challenge 2. _Find a family of random graphs which has a higher algebraic
connectivity than_ $d$_-regular random graphs when average degree_ $d\geq 10.$
_Explore if more complex degree distribution (e.g. tri-regular) can be better
than semi-regular for say,_ $d=3.$

There are several notions of graph connectivity, with AC being just one.
Another notion is using the average of reliability polynomial brown2014average
; perez2018sixty  to compute the effect of edge deletions on graph
connectivity. While the full reliability polynomial requires exponential time
to compute, we performed the following simple experiment to quickly measure
graph robustness. Start with a random 6-regular graph on 500 vertices (i.e.
containing 1500 edges). Then delete edges at random one by one until the graph
becomes disconnected. Over 100 simulations, it took on average 460 edge
deletions until the graph became disconnected (and in every instance,
disconnectivity first occurred when a single vertex lost all of its edges). We
then repeated this experiment with
$\left(d_{1},d_{2}\right)=\left(4,12\right)$ RSRB graph with 500 vertices
(which also contains 1500 edges but has higher AC than 6-regular random
graph). It took on average 325 edge deletions until the disconnection was
achieved. These preliminary experiments indicate that $d$-regular graphs are
more reliable with respect to edge deletions than semi-regular bipartite
graphs, even though the latter might have a higher AC. We state this as a
conjecture.

Conjecture 1._For a given average degree_ $d$_, the most reliable graph is a_
$d$_-regular graph._

Generally speaking, cubic graphs of high girth are good candidates for high-AC
graphs kolokolnikov2015maximizing . Since RSRB can have higher AC, they are
also natural candidates for searching high-girth graphs. We pose this as a
challenge.

Challenge 3._For fixed average degree_ $d$_and fixed number of vertices_ $n,$
_find graphs (not necessarily_ $d$_-regular) with highest possible girth._

A $d$-regular graph with the smallest possible $n$ for a given girth $g$ is
called a cage. There is an extensive literature for looking for high-girth
graphs; see exoo2012dynamic ; biggs1998constructions  for an overview. There
are powerful methods to do computer searches for high-girth $d$-regular graphs
mckay1998fast ; exoo2011computational . As an example, consider
$\left(2,6\right)$ RSRB graphs, whose average degree is $d=3$. Do
$\left(2,6\right)$ semi-regular graphs give better cages than cubic graphs
with the same number of vertices? The answer is, it depends. Note that that
$\left(2,6\right)$ graphs can be obtained from $6$-regular graphs by inserting
a vertex in the middle of each edge; conversely, any $\left(2,6\right)$ graph
yields a $6$-regular graph by vertex contraction: just delete all 2-degree
vertices. According to o1979smallest ; exoo2012dynamic , a 6-regular 5-cage
graph has 40 vertices. By vertex insertion, this yields a girth 10
$\left(2,6\right)$ semi-regular graph with 80 vertices. On the other hand,
there are three cubic graphs having girth 10 and only 70 vertices
exoo2012dynamic . So cubic is better for girth 10.

Similarly, a 6-regular cage of girth 6 has 62 vertices exoo2012dynamic , which
induces a (2,6) graph of girth 12 and 124 vertices. On the other hand, a cubic
graph of girth 12 has at least 126 vertices benson1966minimal ;
exoo2012dynamic . So (2,6) semi-regular graph wins for girth 12.

The techniques in this paper are rather general, and can be used to derive
algebraic connectivity for many other random graph families. As an example,
consider the “small-world”-type graph illustrated in Figure 1(c). Start with a
cycle of $n$ vertices. Then connect all odd-numbered vertices to each other at
random. See Appendix A for Matlab code that generates such a graph. The
resulting graph has an average degree of 2.5. To compute its AC, as in the
derivation of (1.5), we add a self-loop to even-numbered vertices so that each
vertex has degree 3. We leave it as an excercise to the reader that the
average walk-counting sequence $\phi_{s}$ has the generating function which
satisfies

$\displaystyle A$ $\displaystyle=1+x^{2}(A\hat{A}+AB)$ $\displaystyle\hat{A}$
$\displaystyle=1+2x^{2}\hat{A}B$ $\displaystyle B$
$\displaystyle=1+xB+x^{2}AB$ $\displaystyle\phi_{o}$
$\displaystyle=1+x^{2}\phi_{o}\left(\hat{A}+2B\right)$ (3.18)
$\displaystyle\phi_{e}$ $\displaystyle=1+x\phi_{e}+2x^{2}\phi_{e}A$
$\displaystyle\phi$ $\displaystyle=\frac{1}{2}\phi_{o}+\frac{1}{2}\phi_{e}$

Looking at the radius of convergence of the generating functions as before, we
find that in the limit $n\rightarrow\infty$ its AC asymptotes to the smallest
root of the polynomial

$\mu^{9}-24\mu^{8}+249\mu^{7}-1454\mu^{6}+5184\mu^{5}-11400\mu^{4}+14848\mu^{3}-10368\mu^{2}+3108\mu-136=0,$

explicitly given by $\mu=0.0521926.$ This is validated using Monte Carlo
simulations: the average AC of 1000 random such graphs with $n=1000$ vertices
is 0.0557 (std=0.0029), the difference of about 7%. This is significantly
higher than a RSR graph with $(p,d_{1},d_{2})=\left(0.5,2,3\right)$, which
also has average degree of 2.5, but whose AC is $\mu\sim 0.044241.$

## Appendix A: Matlab and Maple code

RSRB model (Figure 1(a)):

d1=2; d2=3; n1=30; n2=20;
bag1=mod([0:n1*d1-1], n1)+1;
bag2=mod([0:n2*d2-1], n2)+1+n1;
bag2=bag2(randperm(numel(bag2)));
G=graph(bag1, bag2);
plot(G);

RSR model (Figure 1(b)):

p=0.4; d1=2; d2=3; n=50;
n1=(1-p)*n; n2=p*n;
v1=mod([0:n1*d1-1], n1)+1;
v2=mod([0:n2*d2-1], n2)+1+n1;
bag=[v1, v2];
bag=bag(randperm(numel(bag)));
G=graph(bag(1:end/2), bag(end/2+1:end));
plot(G);

Small-world-like model (Figure 1(c)):

n=52;
v1=[1:n];
v2=[2:n,1];
bag=[1:2:n];
bag=bag(randperm(numel(bag)));
v1=[v1,bag(1:end/2)];
v2=[v2,bag(end/2+1:end)];
G=graph(v1,v2);
t=(1:n)/n*2*pi;
plot(G, ’XData’, cos(t), ’YData’, sin(t));

Maple code to compute AC of RSR graphs:

## References

  * (1) M. Fiedler, Algebraic connectivity of graphs, Czechoslovak Mathematical Journal 23 (2) (1973) 298–305.
  * (2) N. M. M. de Abreu, Old and new results on algebraic connectivity of graphs, Linear algebra and its applications 423 (1) (2007) 53–73.
  * (3) A. Ghosh, S. Boyd, Growing well-connected graphs, 2006 45th IEEE Conference on Decision and Control (2006) 6605–6611.
  * (4) H. Wang, P. Van Mieghem, Algebraic connectivity optimization via link addition, Proceedings of the 3rd International Conference on Bio-Inspired Models of Network, Information and Computing Sytems (2008) 22.
  * (5) A. Sydney, C. Scoglio, D. Gruenbacher, Optimizing algebraic connectivity by edge rewiring, Applied Mathematics and computation 219 (10) (2013) 5465–5479.
  * (6) R. Olfati-Saber, Ultrafast consensus in small-world networks, American Control Conference, 2005. Proceedings of the 2005 (2005) 2371–2378.
  * (7) T. Kolokolnikov, Maximizing algebraic connectivity for certain families of graphs, Linear Algebra and its Applications 471 (2015) 122–140.
  * (8) K. Ogiwara, T. Fukami, N. Takahashi, Maximizing algebraic connectivity in the space of graphs with a fixed number of vertices and edges, IEEE Transactions on Control of Network Systems 4 (2) (2015) 359–368.
  * (9) K. Shahbaz, M. N. Belur, A. Ganesh, Algebraic connectivity: local and global maximizer graphs, arXiv preprint arXiv:2110.01918 (2021).
  * (10) D. Mosk-Aoyama, Maximum algebraic connectivity augmentation is NP-hard, Operations Research Letters 36 (6) (2008) 677–679.
  * (11) S. Hoory, N. Linial, A. Wigderson, Expander graphs and their applications, Bulletin of the American Mathematical Society 43 (4) (2006) 439–561.
  * (12) A. Lubotzky, Expander graphs in pure and applied mathematics, Bulletin of the American Mathematical Society 49 (1) (2012) 113–162.
  * (13) P. Erdos, A. Renyi, On Random Graphs. I, Publicationes Mathematicae 6 (1959) 290–297.
  * (14) N. Alon, J. H. Spencer, The probabilistic method, Wiley, 2004.
  * (15) B. D. McKay, The expected eigenvalue distribution of a large regular graph, Linear Algebra and its Applications 40 (1981) 203–216.
  * (16) N. Alon, Eigenvalues and expanders, Combinatorica 6 (2) (1986) 83–96.
  * (17) A. Broder, E. Shamir, On the second eigenvalue of random regular graphs, Foundations of Computer Science, 1987., 28th Annual Symposium on (1987) 286–294.
  * (18) J. Friedman, On the second eigenvalue and random walks in randomd-regular graphs, Combinatorica 11 (4) (1991) 331–362.
  * (19) A. Nilli, Tight estimates for eigenvalues of regular graphs, Electron. J. Combin 11 (9) (2004) 1–4.
  * (20) N. C. Wormald, Models of random regular graphs, London Mathematical Society Lecture Note Series (1999) 239–298.
  * (21) M. R. Murty, Ramanujan graphs, Journal-Ramanujan Mathematical Society 18 (1) (2003) 33–52.
  * (22) E. P. Wigner, Characteristic vectors of bordered matrices with infinite dimensions, Annals of Mathematics 62 (3) (1955) 548–564.
  * (23) I. S. A. Longoria, J. A. Mingo, Freely independent coin tosses, standard Young tableaux, and the Kesten–McKay law, arXiv preprint arXiv:2009.11950 (2020).
  * (24) J. A. Mingo, R. Speicher, Free probability and random matrices, Vol. 35, Springer, 2017.
  * (25) H. S. Wilf, generatingfunctionology, CRC press, 2005.
  * (26) J. I. Brown, D. Cox, R. Ehrenborg, The average reliability of a graph, Discrete Applied Mathematics 177 (2014) 19–33.
  * (27) H. Pérez-Rosés, Sixty years of network reliability, Mathematics in Computer Science 12 (3) (2018) 275–293.
  * (28) G. Exoo, R. Jajcay, Dynamic cage survey, The electronic journal of combinatorics (2012) DS16–July.
  * (29) N. Biggs, Constructions for cubic graphs with large girth, the electronic journal of combinatorics (1998) A1–A1.
  * (30) B. McKay, W. Myrvold, J. Nadon, Fast backtracking principles applied to find new cages, in: Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, 1998, pp. 188–191.
  * (31) G. Exoo, B. D. McKay, W. Myrvold, J. Nadon, Computational determination of (3, 11) and (4, 7) cages, Journal of Discrete Algorithms 9 (2) (2011) 166–169.
  * (32) M. O’Keefe, P.-K. Wong, A smallest graph of girth 5 and valency 6, Journal of Combinatorial Theory, Series B 26 (2) (1979) 145–149.
  * (33) C. T. Benson, Minimal regular graphs of girths eight and twelve, Canadian Journal of Mathematics 18 (1966) 1091–1094.