# The minimal spectral radius with given independence number

Jinwon Choi and Jooyeon Park Department of Mathematics and Research Institute
of Natural Sciences, Sookmyung Women’s University, Seoul, 04310, Korea.
<EMAIL_ADDRESS>of Mathematics, Sookmyung Women’s
University, Seoul, 04310, Korea<EMAIL_ADDRESS>
###### Abstract

In this paper, we determine the graphs which have the minimal spectral radius
among all the connected graphs of order $n$ and the independence number
$\lceil\frac{n}{2}\rceil-1.$

Keywords: Spectral radius, Independence number, Bicyclic graph
AMS subject classification : 05C50

##  1 Introduction

Let $G$ be a simple, connected, and undirected graph of order $n$ with vertex
set $V(G)$ and edge set $E(G)$. For a graph $G$, a vertex subset $S$ is
_independent_ if the induced subgraph $G[S]$ has no edges. The maximum size of
an independent set in $G$ is called the _independence number_ of $G$ and
denoted by $\alpha(G)$. For the vertex set $\\{v_{1},v_{2},\ldots,v_{n}\\}$ of
$G$, the _adjacency matrix_ $A(G)=(a_{ij})$ of $G$ is defined as the $n\times
n$ matrix whose $ij$-entry is $1$ if $v_{i}$ and $v_{j}$ are adjacent or $0$
otherwise. Since $A(G)$ a real symmetric matrix, all its eigenvalues are real.
The largest eigenvalue of $A(G)$ is called the _spectral radius_ of $G$ and
denoted by $\rho(G)$. By Perron-Frobenius Theorem, $\rho(G)$ is simple and
positive.

Many studies about the relation between the spectral radius and the
independence number have been done. In particular, a bound of spectral radius
and the classification of the corresponding extremal graphs are important
problems. In [3], Das and Mohanty gave an upper bound for the spectral radius
of a bi-block graphs with given independence numbers, where a block of a graph
is a maximal connected subgraph having no cut-vertex and a _bi-block graph_ is
a connected graph each of whose blocks is a complete bipartite graph. Lou and
Guo [9] extended the result of [3] and proved that among all bipartite graphs
with given independence number $\alpha$, the maximum spectral radius is
uniquely attained by the complete bipartite graph $K_{\alpha,n-\alpha}$.

On the other hand, determining the graphs with the minimum spectral radius
among connected graphs with given independence number is considered to be a
tough problem. ([13, §4.4]). It has been studied for some cases. A graph with
minimum spectral radius among a given class of graphs is called a _minimizer
graph_. Let $\mathbb{G}_{n,\alpha}$ be the set of simple connected graphs of
order $n$ with independence number $\alpha$. In [14], Xu, Hong, Shu, and Zhai
determined the minimizer graphs with the independence number
$\alpha=1,2,\lceil\frac{n}{2}\rceil,\lceil\frac{n}{2}\rceil+1,n-3,n-2,n-1$. Du
and Shi in [4] determined the minimizer graph for $\alpha=3,4$ and $n=k\alpha$
for some integer $k$ and Jin and Zhang in [8] extended results for all
$\alpha$ and $n=k\alpha$. In [9], Lou and Guo proved that the minimizer graph
in $\mathbb{G}_{n,\alpha}$ must be a tree if
$\alpha\geq\lceil\frac{n}{2}\rceil$. They also determined the extremal graphs
when $\alpha=n-4$. Later, Hu, Huang and Lou [7] gave a construction of the
minimizer graphs for $\alpha\geq\lceil\frac{n}{2}\rceil$.

In this paper, we determine the minimizer graphs when
$\alpha=\lceil\frac{n}{2}\rceil-1$. To state our main theorem, we fix
notations. Let $C_{n}$ be the cycle of length $n$ and let $P_{n}$ be the path
of length $n$. Let $B(m,p,q)$ be the graph obtained by attaching $C_{m}$ and
$C_{q}$ at each end vertex of the path $P_{p}$. (See Figure 2) The main
theorem of this paper is the following.

######  Theorem 1.1.

Let $G$ be the minimizer graph in
$\displaystyle\mathbb{G}_{n,\lceil\frac{n}{2}\rceil-1}$ where $n\geq 7$ and
let $k=\lceil\frac{n}{3}\rceil$. Then

$G\cong\begin{cases}C_{n},&\text{if $n$ is odd}\\\ B(k+1,k-1,k+1),&\text{if
$n\equiv 0\ (mod~{}6)$}\\\ B(k,k,k),&\text{if $n\equiv 2\ (mod~{}6)$}\\\
B(k-1,k+1,k-1),&\text{if $n\equiv 4\ (mod~{}6)$}\end{cases}$

######  Remark 1.2.

For completeness, we state results for $n\leq 6$, which can be checked easily.
The complete graph $K_{3}$ and $K_{4}$ are the only graph in
$\mathbb{G}_{3,1}$ and $\mathbb{G}_{4,1}$, respectively. The minimizer graph
in $\mathbb{G}_{5,2}$ is $C_{5}$ and in $\mathbb{G}_{6,2}$ is $B(3,1,3)$.

This paper is organized as follows. In Section 2, we review necessary results.
In Section 3, we study the spectral radius of bicyclic graphs. In Section 4,
we prove Theorem 1.1. For undefined terms or notations of graph theory, see
West [15]. For basic properties of spectral graph theory, see Brouwer and
Haemers [1] or Godsil and Royle [5].

##  2 Preliminaries

In this section, we introduce relevant tools and results.

######  Lemma 2.1 (Perron-Frobenius theorem).

Let $G$ be a connected graph and $A$ be the adjacency matrix of $G$. Then we
have the following.

  1. 1.

The spectral radius $\rho(G)$ of $G$ is a positive simple eigenvalue of $A$

  2. 2.

There is a unique positive unit eigenvector of $A$ corresponding to $\rho(G)$.
This vector is called the _Perron vector_ of $G$.

  3. 3.

If there exists a nonzero vector $y$ with $y\geq 0$ and a number $\sigma$ such
that $Ay\leq\sigma y$ and $Ay\neq\sigma y$, then $y>0$ and $\rho(G)<\sigma$.

######  Lemma 2.2 ([2, Interlacing Theorem]).

Let $G$ be a graph with $n$ vertices and eigenvalues
$\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{n}$ and let $H$ be an
induced subgraph of $G$ with $m$ vertices and eigenvalues
$\mu_{1}\geq\mu_{2}\geq\cdots\geq\mu_{m}$. Then for $1\leq i\leq m,$

$\lambda_{i}\geq\mu_{i}\geq\lambda_{n-m+i}.$

In other words, the eigenvalues of $H$ interlace the eigenvalues of $G$.

######  Lemma 2.3 ([2, Theorem 1.3.10]).

Let $G$ be a connected graph. Then deleting an edge of $G$ strictly decreases
its spectral radius.

By Lemma 2.3, the characterization of the graph having maximal spectral radius
in $\mathbb{G}_{n,\alpha}$ is immediate. The _join_ of graphs $G$ and $H$,
written as $G\vee H$, is the graph union of $G$ and $H$ together with all the
edges joining each vertex of $G$ to each vertex of $H$.

######  Theorem 2.4 ([9]).

Let $G\in\mathbb{G}_{n,\alpha}$. Then $\rho(G)\leq\rho(K_{n-\alpha}\vee\alpha
K_{1})$ with equality if and only if $G\cong K_{n-\alpha}\vee\alpha K_{1}$.

We introduce operations on graphs which decreases the spectral radius. An
_internal path_ of a graph is a sequence of vertices
$u_{1},u_{2},\cdots,u_{k}$ such that all $u_{i}$ are distinct (except possibly
$u_{1}=u_{k}$), the degree $d(u_{i})$ satisfy

$d(u_{1})\geq 3,\ d(u_{2})=\cdots=d(u_{k-1})=2,\ d(u_{k})\geq 3,$

and $u_{i}$ is adjacent to $u_{i+1}$ for $i=1,2,\cdots,k-1.$ Note that two
adjacent vertices with degree at least 3 form an internal path.

######  Lemma 2.5 ([6, Proposition 2.4]).

Let $G$ be a graph not isomorphic to the graph $\tilde{D}_{n}$ depicted in
Figure 1. Then the spectral radius strictly decreases after inserting a vertex
of degree 2 to an internal path of $G$ (i.e. after deleting an edge $uv$ in an
internal path and adding a new vertex $w$ and two new edges $uw$ and $wv$).

$\cdots$ Figure 1: $\tilde{D}_{n}$

Thus, by Lemmas 2.2 and 2.5, removing a vertex outside of an internal path and
reinserting it into an internal path strictly decreases the spectral radius
while the number of vertices remains unchanged. We will repeatedly use this
operation.

For the Perron vector $x$ of a graph $G$, we denote by $x_{u}$ the component
of $x$ corresponding to a vertex $u\in V(G)$. A _cut edge_ is a single edge
whose removal disconnects the graph.

######  Lemma 2.6 ([16]).

Let $G$ be a connected graph with the Perron vector $x$. Let $u,v$ be two
vertices of $G$. Suppose that $v_{1},v_{2},\ldots,$ $v_{s}(1\leq s\leq d_{v})$
are some vertices of $N_{G}(v)\setminus N_{G}(u)$. Let $G^{*}$ be the graph
obtained from $G$ by deleting the edges $(v,v_{i})$ and adding the edges
$(u,v_{i})(1\leq i\leq s)$. If $x_{u}\geq x_{v}$, then $\rho(G)<\rho(G^{*})$.

######  Lemma 2.7 ([7]).

Let $G$ be a connected graph with the Perron vector $x$. Suppose that $vw_{1}$
is a cut edge of $G$, $N_{G}(v)=\\{w_{1},w_{2},\ldots,w_{t}\\}(t\geq 3)$ and
$x_{w_{1}}=\min_{w\in N_{G}(v)}{x_{w}}$. Let $G^{\prime}$ be a graph obtained
from $G$ by replacing $v$ with two new vertices $v^{\prime},v^{\prime\prime}$
and adding new edges $v^{\prime}w_{1},v^{\prime}w_{2},\ldots,v^{\prime}w_{s}$
and
$v^{\prime\prime}w_{s+1},v^{\prime\prime}w_{s+2},\ldots,v^{\prime\prime}w_{t}$
for some $2\leq s\leq t-1$. Then $\rho(G^{\prime})\leq\rho(G)$, with equality
if and only if $t=3$ and $x_{w_{1}}=x_{w_{2}}=x_{w_{3}}$.

##  3 Spectral radius of bicyclic graphs

A connected graph $G$ is called a _unicyclic graph_ if $|E(G)|=|V(G)|$ and a
_bicyclic graph_ if $|E(G)|=|V(G)|+1$. For even $n$, we will see that the
minimizer graphs in $\displaystyle\mathbb{G}_{n,\lceil\frac{n}{2}\rceil-1}$
are bicyclic graphs. In this section, we present results on the spectral
radius of bicyclic graphs, which will be used in the proof of our main
theorem.

######  Definition 3.1.

Let $m$, $p$, $q$ be positive integers.

  1. 1.

Let $P(m,p,q)$ be the graph obtained by identifying each end vertex of the
path graphs $P_{m}$, $P_{p}$ and $P_{q}$. We assume at most one of $m,p,q$ is
one.

  2. 2.

Let $C(m,q)$ be the graph obtained by identifying a vertex of the cycle graphs
$C_{m}$ and $C_{q}$. We assume $m,q\geq 3$.

  3. 3.

Let $B(m,p,q)$ be the graph obtained by attaching $C_{m}$ and $C_{q}$ at each
end vertex of the path $P_{p}$. We assume $m,q\geq 3$ and $p\geq 1$.

These graphs are depicted in Figure 2. Each of $m,p,q$ is the number of edges
for an independent path or cycle. The number of vertices of $P(m,p,q)$ and
$B(m,p,q)$ is $m+p+q-1$ and that of $C(m,q)$ is $m+q-1$. We name each vertex
of $P(m,p,q)$ and $B(m,p,q)$ as shown in Figure 2.

$u_{0}$$v_{0}$$u_{1}$$u_{2}~{}~{}~{}~{}$$v_{2}~{}~{}~{}~{}$$v_{1}$$w_{1}$$w_{p-1}$$u_{m-1}$$~{}~{}~{}~{}u_{m-2}$$~{}~{}~{}~{}v_{q-2}$$v_{q-1}$$\cdots$$\cdots$$\cdots$$P(m,p,q)$

$m$$q$⋮⋮$C(m,q)$

$u_{0}$$v_{0}$$u_{1}$$u_{2}$$u_{m-2}$$u_{m-1}$$w_{1}$$w_{p-1}$$v_{1}$$v_{2}$$v_{q-2}$$v_{q-1}$⋮⋮$\cdots$$B(m,p,q)$

Figure 2: The bicyclic graphs $P(m,p,q)$, $C(m,q)$ and $B(m,p,q)$

Note that a graph $G$ with $|E(G)|\geq|V(G)|+1$ contains a subgraph isomorphic
to either $P(m,p,q)$, $C(m,q)$ or $B(m,p,q)$ for some integer $m,p,q$. We
review results of [10] and [11] on the bicyclic graphs in Definition 3.1.

######  Lemma 3.2 ([11]).

For any integers $m\geq 3$ and $p\geq 1$, $\rho(P(m,p,m))=\rho(B(m,p,m))$.

In [11], Simić and Kocić proved Lemma 3.2 by observing that the Perron vectors
and the spectral radii of the two graphs should satisfy the same equations. We
remark that Lemma 3.2 can also be seen by using equitable partition. Namely,
the vertex sets

$\\{u_{0},v_{0}\\},\\{u_{1},v_{1},u_{m-1},v_{m-1}\\},\ldots,\\{u_{\lfloor\frac{m}{2}\rfloor},v_{\lfloor\frac{m}{2}\rfloor},u_{\lceil\frac{m}{2}\rceil},v_{\lceil\frac{m}{2}\rceil}\\},\\{w_{1},w_{p-1}\\},\ldots\\{w_{\lfloor\frac{p}{2}\rfloor},w_{\lceil\frac{p}{2}\rceil}\\}$

on both graphs form equitable partitions having the same quotient matrix.
Hence, they have the same spectral radius.

######  Lemma 3.3 ([11]).

  1. 1.

If $m+p+q$ is fixed, $\rho(P(m,p,q))$ decreases as $\max(m,p,q)-\min(m,p,q)$
decreases.

  2. 2.

If $m+q$ is fixed, $\rho(C(m,q))$ decreases as $\max(m,q)-\min(m,q)$
decreases.

However, for the graphs $B(m,p,q)$, differences between parameters are not
sufficient to compare their spectral radii, unless we fix the middle
parameter.

######  Lemma 3.4 ([10]).

If $p$ and $m+q$ are fixed, $\rho(B(m,p,q))$ decreases as
$\max(m,q)-\min(m,q)$ decreases..

Let $\mathbb{B}_{n}$ be the set of all bicyclic graphs with order $n$. By
Lemma 2.2 and 2.5, the minimizer graph in $\mathbb{B}_{n}$ has no vertices of
degree one, because otherwise we can remove the vertex of degree one and
reinsert it to an internal path to get a graph with less spectral radius.
Also, by Lemmas 3.3 and 3.4, it is expected that the minimizer graph is either
$P(m,p,q)$ or $B(m,p,q)$ where the difference $\max(m,p,q)-\min(m,p,q)$ is as
small as possible. In [11], Simić proved that this is the case.

######  Lemma 3.5 ([10]).

Assume $n\geq 7$ and let $k=\lceil\frac{n}{3}\rceil$. The minimizer graphs in
$\mathbb{B}_{n}$ are $P(k,n+1-2k,k)$ and $B(k,n+1-2k,k)$.

Now, we present a few comparison results between the spectral radius of
bicyclic graphs. Let

$x=(x_{u_{0}},\ldots,x_{u_{m-1}},x_{w_{1}},\ldots,x_{w_{p-1}},x_{v_{0}},\ldots,x_{v_{q-1}})^{T}$

be the Perron vector of the graph $B(m,p,q)$ and let $\rho=\rho(B(m,p,q))$.
Then we have

$\rho x_{v}=\sum_{u\sim v}x_{u}.$ (1)

We will use the following elementary lemma to determine $x$ and $\rho$.

######  Lemma 3.6 ([10, Lemma 1]).

Define

$f_{i}(t,k,a,b)=\frac{b\sinh{it}+a\sinh{(k-i)t}}{\sinh{kt}}.$

The difference equation

$\rho x_{i+1}=x_{i}+x_{i+2}\,(i=0,\ldots k-2)\quad\text{with}\quad
x_{0}=a,x_{k}=b$ (2)

has the solution $x_{i}=f_{i}(t_{\rho},k,a,b)$, where
$t_{\rho}=\ln(\frac{\rho+\sqrt{\rho^{2}-4}}{2})$ or equivalently
$\rho=2\cosh{t_{\rho}}$.

Assume $x_{u_{0}}=a$ and $x_{v_{0}}=b$. By Lemma 3.6, we have

$\displaystyle x_{u_{i}}$ $\displaystyle=f_{i}(t_{\rho},m,a,a)\text{ for
}i=1,\ldots,m-1,$ $\displaystyle x_{w_{i}}$
$\displaystyle=f_{i}(t_{\rho},p,a,b)\text{ for }i=1,\ldots,p-1,$
$\displaystyle x_{v_{i}}$ $\displaystyle=f_{i}(t_{\rho},q,b,b)\text{ for
}i=1,\ldots,q-1.$

The numbers $a$ and $b$ are determined by equations (1) at vertices $u_{0}$
and $v_{0}$, that is,

$\displaystyle 2a\cosh{t_{\rho}}$
$\displaystyle=2f_{1}(t_{\rho},m,a,a)+f_{1}(t_{\rho},p,a,b),$ $\displaystyle
2b\cosh{t_{\rho}}$
$\displaystyle=2f_{1}(t_{\rho},q,b,b)+f_{p-1}(t_{\rho},p,a,b).$

Rearranging terms using the definition of $f_{i}$, we get

$\displaystyle
a\cosh{t_{\rho}}-f_{1}(t_{\rho},m,a,a)-\frac{1}{2}f_{1}(t_{\rho},p,a,a)$
$\displaystyle=-\frac{a-b}{2}\frac{\sinh{t_{\rho}}}{\sinh{pt_{\rho}}},$ (3)
$\displaystyle
a\cosh{t_{\rho}}-f_{1}(t_{\rho},q,a,a)-\frac{1}{2}f_{1}(t_{\rho},p,a,a)$
$\displaystyle=\frac{a(a-b)}{2b}\frac{\sinh{t_{\rho}}}{\sinh{pt_{\rho}}}.$ (4)

######  Remark 3.7.

Dividing both sides of (3), (4) by $a$ and subtracting (3) from (4), we have

$f_{1}(t_{\rho},m,1,1)-f_{1}(t_{\rho},q,1,1)=(a-b)\left(\frac{1}{2a}+\frac{1}{2b}\right)\frac{\sinh{t_{\rho}}}{\sinh{pt_{\rho}}}.$

It is easy to check that $f_{1}(t_{\rho},x,1,1)$ is strictly decreasing in
$x$.([10, Lemma 3]) Thus, if $m>q$ then $a<b$ and if $m=q$ then $a=b$.

The following is a slight modification of [10, Equation (11)].

######  Lemma 3.8.

Let $m,p$ be distinct positive integers greater than or equal to $3$. Then,

$\rho(B(m,p,m))<\rho(B(m,m,p)).$

###### Proof.

For the Perron vector

$x=(x_{u_{0}},\ldots,x_{u_{m-1}},x_{w_{1}},\ldots,x_{w_{m-1}},x_{v_{0}},\ldots,x_{v_{p-1}})^{T}$

of $B(m,m,p)$, let $x_{u_{0}}=a$ and $x_{v_{0}}=b$. Let
$\sigma=\rho(B(m,m,p))$ and
$t_{\sigma}=\ln(\frac{\sigma+\sqrt{\sigma^{2}-4}}{2})$. By the above
discussion, $a$ and $b$ must satisfy

$\displaystyle 2a\cosh{t_{\sigma}}$
$\displaystyle=2f_{1}(t_{\sigma},m,a,a)+f_{1}(t_{\sigma},m,a,b),$
$\displaystyle 2b\cosh{t_{\sigma}}$
$\displaystyle=2f_{1}(t_{\sigma},p,b,b)+f_{p-1}(t_{\sigma},m,a,b).$

By rearranging terms as before, we have

$\displaystyle
a\cosh{t_{\sigma}}-f_{1}(t_{\sigma},m,a,a)-\frac{1}{2}f_{1}(t_{\sigma},m,a,a)$
$\displaystyle=-\frac{a-b}{2}\frac{\sinh{t_{\sigma}}}{\sinh{mt_{\sigma}}},$
(5) $\displaystyle
a\cosh{t_{\sigma}}-f_{1}(t_{\sigma},p,a,a)-\frac{1}{2}f_{1}(t_{\sigma},m,a,a)$
$\displaystyle=\frac{a(a-b)}{2b}\frac{\sinh{t_{\sigma}}}{\sinh{mt_{\sigma}}}.$
(6)

Consider a vector

$x^{\prime}=(x_{u_{0}}^{\prime},\ldots,x_{u_{m-1}}^{\prime},x_{w_{1}}^{\prime},\ldots,x_{w_{p-1}}^{\prime},x_{v_{0}}^{\prime},\ldots,x_{v_{m-1}}^{\prime})^{T}$

constructed as

$x_{u_{i}}^{\prime}=x_{v_{i}}^{\prime}=f_{i}(t_{\sigma},m,a,a)~{}\text{and}~{}x_{w_{j}}^{\prime}=f_{j}(t_{\sigma},p,a,a)$

for $i=0,1,\ldots,m-1$ and $j=0,1,\ldots,p-1$, which corresponds to the graph
$B(m,p,m)$. By construction, $\rho x_{v}^{\prime}=\sum_{u\sim
v}x_{u}^{\prime}$ for degree two vertices $v$ of $B(m,p,m)$. We claim that
$\rho x_{v}^{\prime}>\sum_{u\sim v}x_{u}^{\prime}$ for $v=u_{0}$ or $v=v_{0}$,
which implies $\rho(B(m,p,m))<\sigma$ by Theorem 2.1.

By adding (5) and (6), we have

$\displaystyle\sigma x_{v_{0}}^{\prime}-\sum_{u\sim v_{0}}x_{u}^{\prime}$
$\displaystyle=2a\cosh{t_{\sigma}}-2f_{1}(t_{\sigma},m,a,a)-f_{p}(t_{\sigma},p,a,a)$
$\displaystyle=a\left(\frac{a-b}{2b}-\frac{a-b}{2a}\right)\frac{\sinh{t_{\sigma}}}{\sinh{mt_{\sigma}}}$
$\displaystyle=a(a-b)\left(\frac{1}{2b}-\frac{1}{2a}\right)\frac{\sinh{t_{\sigma}}}{\sinh{mt_{\sigma}}}$
$\displaystyle=\frac{(a-b)^{2}}{2b}\frac{\sinh{t_{\sigma}}}{\sinh{mt_{\sigma}}}.$

Since $\sigma>2$ by Lemma 4.1, $t_{\sigma}>0$ and hence $\sigma
x_{v_{0}}^{\prime}>\sum_{u\sim v_{0}}x_{u}^{\prime}$. By the same argument, we
also have $\sigma x_{u_{0}}^{\prime}>\sum_{u\sim u_{0}}x_{u}^{\prime}$, which
completes the proof. ∎

######  Lemma 3.9.

Let $m,p,q$ be positive integers with $m\geq q\geq 3$. Then,

$\rho(B(m,p,q))<\rho(C(m+p,q)).$

###### Proof.

Let $x$ be the Perron vector of $B(m,p,q)$. By Remark 3.7, since $m\geq q$, we
have $x_{v_{0}}\leq x_{u_{0}}$. Then Lemma 2.6 applies, where we take
$u=v_{0}$, $v=u_{0}$ and $u_{1}\in N(v)\setminus N(u)$. ∎

######  Lemma 3.10.

Let $m,p$ be positive integers with $\min(m,p)\geq q\geq 3$. Then,

$\rho(B(m,p,q))\geq\rho(B(m,p-1,q+2)),$

with equality if and only if $m=p=q$.

$z$$v$$w_{1}$$w_{2}$$w_{3}$$\cdots$(a) $G=B(m,p,q)$

$v^{\prime}$$w_{1}$$w_{2}$$w_{3}$$v^{\prime\prime}$$\cdots$(b)
$G^{\prime}=B(m,p-1,q+2)$

Figure 3: $\rho(G^{\prime})\leq\rho(G)$

###### Proof.

We apply Lemma 2.7. Let $G$ be the graph $B(m,p,q)$ as in Figure 3 (a). Then
$vw_{1}$ is a cut edge of $G$. For the Perron vector $x=(x_{u}\,|\,u\in
V(G))$, we have

$\displaystyle x_{w_{1}}$ $\displaystyle=f_{1}(t,p,x_{z},x_{v}),$
$\displaystyle x_{w_{2}}$
$\displaystyle=f_{1}(t,q,x_{v},x_{v})=f_{p-1}(t,q,x_{v},x_{v})=x_{w_{3}}$

where $\rho(G)=2\cosh t$. Since $m\geq q$, we have $x_{z}\leq x_{v}$ by Remark
3.7. Thus,

$f_{1}(t,q,x_{v},x_{v})\geq f_{1}(t,p,x_{v},x_{v})\geq
f_{1}(t,p,x_{z},x_{v}),$

where the first inequality holds because $p\geq q$. Therefore
$x_{w_{1}}=\min_{w\in N_{G}(v)}{x_{w}}$ and hence
$\rho(B(m,p,q))\geq\rho(B(m,p-1,q+2))$ by Lemma 2.7.

The equality holds if and only if $x_{w_{1}}=x_{w_{2}}=x_{w_{3}}$. In the
above inequality, this holds if and only if $x_{z}=x_{v}$ and $p=q$, or
equivalently $m=p=q$. ∎

##  4 Minimizer graphs with independence number $\lceil\frac{n}{2}\rceil-1$

In this section, we determine the graphs with minimal spectral radius in
$\displaystyle\mathbb{G}_{n,\lceil\frac{n}{2}\rceil-1}.$ Since
$\alpha(T)\geq\lceil\frac{n}{2}\rceil$ for any tree $T$ of order $n$, we will
only consider non-tree graphs. In [12], Smith showed that the only graphs with
spectral radius less than two are the finite simply-laced Dynkin diagrams and
the only graphs with spectral radius equal to two are the extended simply-
laced Dynkin diagrams. The only non-tree graphs among them is the cycle
$C_{n}$. Hence we have the following.

######  Lemma 4.1 ([12]).

Let $G$ be a non-tree graph of order $n$. Then $\rho(G)\geq 2$ and $\rho(G)=2$
if and only if $G$ is the cycle $C_{n}$.

Since $\alpha(C_{n})=\lceil\frac{n}{2}\rceil-1$ for odd $n$, the following is
immediate.

######  Theorem 4.2.

When $n$ is odd, the minimizer graph in
$\displaystyle\mathbb{G}_{n,\lceil\frac{n}{2}\rceil-1}$ is the cycle $C_{n}$.

From now on, we assume that $n$ is even. By Lemma 2.3, the minimizer graphs
should have as small number of edges as possible. For a unicyclic graph $G$ of
order $n$, the independence number
$\alpha(G)\geq\lfloor\frac{n}{2}\rfloor$.([15, Exercise 3.1.41]) Hence when
$n$ is even, $\alpha(G)\geq\frac{n}{2}>\lceil\frac{n}{2}\rceil-1$ for any
unicyclic graph of order $n$.

Now we consider the bicyclic graphs. It is elementary to check the
independence number of graphs of $P(m,p,q)$, $C(m,q)$ and $B(m,p,q)$.

######  Lemma 4.3.

Let $n$ be the order of the graph.

  1. 1.

$\alpha(P(m,p,q))=\begin{cases}\lceil\frac{n}{2}\rceil-1,&\mbox{if exactly two
of }m,p,q~{}\text{are odd},\\\
\lceil\frac{n}{2}\rceil,&\mbox{otherwise}.\end{cases}$

  2. 2.

$\alpha(C(m,q))=\begin{cases}\lceil\frac{n}{2}\rceil-1,&\mbox{if both of
}m,q~{}\text{are odd},\\\
\lceil\frac{n}{2}\rceil,&\mbox{otherwise}.\end{cases}$

  3. 3.

$\alpha(B(m,p,q))=\begin{cases}\lceil\frac{n}{2}\rceil-1,&\mbox{if at least
two of }m,p,q~{}\text{are odd},\\\
\lceil\frac{n}{2}\rceil,&\mbox{otherwise.}\end{cases}$

When $k=\lceil\frac{n}{3}\rceil$ is odd, that is, when $n\equiv 2\pmod{6}$,
the graph $B(k,k,k)$ and $P(k,k,k)$ are minimizer graphs in $\mathbb{B}_{n}$
by Lemma 3.5. By Lemma 4.3, $\alpha(B(k,k,k))=\lceil\frac{n}{2}\rceil-1$ and
$\alpha(P(k,k,k))=\lceil\frac{n}{2}\rceil$. Hence we have the following.

######  Theorem 4.4.

If $n\equiv 2\pmod{6}$ and $n\geq 7$, the minimizer graph in
$\displaystyle\mathbb{G}_{n,\lceil\frac{n}{2}\rceil-1}$ is isomorphic to
$B(k,k,k)$, where $k=\lceil\frac{n}{3}\rceil$.

###### Proof.

A graph $G$ in $\mathbb{G}_{n,\lceil\frac{n}{2}\rceil-1}$ has at least $n+1$
edges. Since removing an edge strictly decreases the spectral radius,
$\rho(G)\geq\rho(H)$ for some bicyclic graph $H$. Hence
$\rho(G)\geq\rho(H)\geq\rho(B(k,k,k))$ with equality if and only if
$G=B(k,k,k)$. ∎

Now, it remains to consider the cases $n\equiv 0$ or $4\pmod{6}$. Our strategy
is as follows. Since a graph $G$ in $\mathbb{G}_{n,\lceil\frac{n}{2}\rceil-1}$
has more than $n$ edges, $G$ has a minimal bicyclic subgraph, which is
isomorphic to one of $P(m,p,q)$, $C(m,q)$ or $B(m,p,q)$. We first show that if
$G$ contains either $C(m,q)$ or $P(m,p,q)$, then $\rho(G)$ is greater that
that of the minimizer graph in Theorem 1.1. If $G$ does not contain any of
$C(m,q)$ or $P(m,p,q)$, all cycles in $G$ are disjoint and $G$ contains some
$B(m,p,q)$ as an induced subgraph. We prove that in this case the minimum
spectral radius is attained by the minimizer graph in Theorem 1.1. Our main
tool is Lemma 2.2 and Lemma 2.5. Namely, we take a minimal bicyclic subgraph
and remove all vertices outside of it and reinsert them to internal paths of
the bicyclic subgraph. This process will decrease the spectral radius and we
end up with the minimizer graph.

######  Remark 4.5.

Let $k=\lceil\frac{n}{3}\rceil$. When $n\equiv 0$ or $4\pmod{6}$, $k$ is even
and $n=3k$ or $3k-2$, respectively. Hence if the bicyclic graphs $P(m,p,q)$
and $B(m,p,q)$ have order $n$, we have $m+p+q=3k+1$, or $3k-1$, respectively.

######  Proposition 4.6.

Let $n$ be an integer with $n\geq 7$ and $k=\lceil\frac{n}{3}\rceil$ even.
Suppose that a connected graph $G$ of order $n$ contains $C(m,q)$ as a
subgraph for some $m,q\geq 3$.

  1. 1.

if $n\equiv 0\pmod{6}$, $\rho(G)>\rho(B(k+1,k-1,k+1))$.

  2. 2.

if $n\equiv 4\pmod{6}$, $\rho(G)>\rho(B(k-1,k+1,k-1))$.

###### Proof.

By Lemmas 2.2, 2.3 and 2.5, one can remove all vertices and edges outside of
$C(m,q)$ and reinsert vertices to one of the cycles, for example to the cycle
of length $q$, in $C(m,q)$ to get a graph with less spectral radius. Hence we
have $\rho(C(m,n-m+1))\leq\rho(G)$. Then,

$\displaystyle\rho(G)\geq\rho(C(m,n-m+1))$
$\displaystyle\geq\rho\left(C\left(\frac{n}{2}+1,\frac{n}{2}\right)\right)$
(by Lemma 3.3)
$\displaystyle>\rho\left(B\left(\frac{n}{2},1,\frac{n}{2}\right)\right)$ (by
Lemma 3.9)
$\displaystyle=\rho\left(P\left(\frac{n}{2},1,\frac{n}{2}\right)\right)$ (by
Lemma 3.2)

Since $n\geq 7$, we have $n/2-1>2$. Thus when $n\equiv 0\pmod{6}$, that is,
when $n=3k$,

$\rho\left(P\left(\frac{n}{2},1,\frac{n}{2}\right)\right)>\rho(P(k+1,k-1,k+1))=\rho(B(k+1,k-1,k+1)),$

by Lemma 3.2 and Lemma 3.3. The case for $n\equiv 4\pmod{6}$ is similar. ∎

######  Proposition 4.7.

Let $n$ be an integer with $n\geq 7$ and $k=\lceil\frac{n}{3}\rceil$ even.
Suppose that a connected graph $G$ of order $n$ contains
$P^{*}=P(m^{*},p^{*},q^{*})$ as a subgraph for some integers $m^{*},q^{*}\geq
2$ and $p^{*}\geq 1$.

  1. 1.

If $n\equiv 0\pmod{6}$ and $G\ncong P(k,k+1,k)$, then
$\rho(G)\geq\rho(B(k+1,k-1,k+1))$ with equality if and only if $G\cong
P(k+1,k-1,k+1)$.

  2. 2.

If $n\equiv 4\pmod{6}$ and $G\ncong P(k,k-1,k)$, then
$\rho(G)\geq\rho(B(k-1,k+1,k-1))$ with equality if and only if $G\cong
P(k-1,k+1,k-1)$.

###### Proof.

Case 1. $n\equiv 0\pmod{6}$

Note that we may assume that $P^{*}\ncong P(k,k+1,k)$. Indeed, if $G$ contains
$P(k,k+1,k)$ as a proper subgraph, that is, $G$ is $P(k,k+1,k)$ with at least
one extra edges between vertices, then one can see that $G$ contains
$P(m,p,q)$ with $m+p+q<3k+1$, which can be chosen to be $P^{*}$.

Suppose that $m^{*}+p^{*}+q^{*}=3k+1$. Since $P^{*}\ncong P(k,k+1,k)$, we have
$\max(m^{*},p^{*},q^{*})-\min(m^{*},p^{*},q^{*})\geq 2$. Therefore, by Lemma
3.3 and Lemma 3.2,

$\rho(G)\geq\rho(P^{*})\geq\rho(P(k+1,k-1,k+1))=\rho(B(k+1,k-1,k+1)).$

In this case, the equality holds if and only if $G\cong P(k+1,k-1,k+1)$.

Now suppose that $m^{*}+p^{*}+q^{*}<3k+1$. If
$(m^{*},p^{*},q^{*})\neq(k,k,k)$, by removing all the vertices and edges
outside of $P^{*}$ and reinserting vertices to the longest internal path in
$P^{*}$, one can find $(m^{\prime},p^{\prime},q^{\prime})$ such that
$m^{\prime}+p^{\prime}+q^{\prime}=3k+1$,
$\max(m^{\prime},p^{\prime},q^{\prime})-\min(m^{\prime},p^{\prime},q^{\prime})\geq
2$ and $\rho(P(m^{\prime},p^{\prime},q^{\prime}))<\rho(P^{*})<\rho(G)$. Hence
by the same argument as above, we have $\rho(G)>\rho(B(k+1,k-1,k+1))$.

Finally, if $(m^{*},p^{*},q^{*})=(k,k,k)$, then by Lemma 3.2 and Lemma 3.10,
we have

$\rho(G)>\rho(P(k,k,k))=\rho(B(k,k,k))=\rho(B(k,k-1,k+2)).$

Since $\rho(B(k,k-1,k+2))>\rho(B(k+1,k-1,k+1))$, we are done.

Case 2. $n\equiv 4\pmod{6}$

The proof is parallel to Case 1. We may assume that $P^{*}\ncong P(k,k-1,k)$.
Then, by removing all the vertices and edges outside of $P^{*}$ and
reinserting vertices to the longest internal path in $P^{*}$, one can find
$(m^{\prime},p^{\prime},q^{\prime})$ such that
$m^{\prime}+p^{\prime}+q^{\prime}=3k-1$,
$\max(m^{\prime},p^{\prime},q^{\prime})-\min(m^{\prime},p^{\prime},q^{\prime})\geq
2$ and $\rho(P(m^{\prime},p^{\prime},q^{\prime}))\leq\rho(P^{*})\leq\rho(G)$.
Thus

$\rho(G)\geq\rho(P(m^{\prime},p^{\prime},q^{\prime}))\geq\rho(P(k-1,k+1,k-1))=\rho(B(k-1,k+1,k-1)).$

The equality holds if and only if $G\cong P(k+1,k-1,k+1)$. Therefore, the
proof is complete. ∎

By Lemma 4.3, $P(k,k+1,k)$ and $P(k+1,k-1,k+1)$ in the case $n\equiv
0\pmod{6}$ and $P(k,k-1,k)$ and $P(k+1,k-1,k+1)$ in the case $n\equiv
4\pmod{6}$ are not in $\mathbb{G}_{n,\lceil\frac{n}{2}\rceil-1}$. Hence by
Proposition 4.6 and Proposition 4.7, we now assume that the graph $G$ does not
contain $C(m,q)$ or $P(m,p,q)$ as a subgraph. This condition is equivalent to
the condition that all cycles in $G$ are mutually disjoint.

######  Proposition 4.8.

Let $n$ be an integer with $n\geq 7$ and $k=\lceil\frac{n}{3}\rceil$ even. Let
$G\in\displaystyle\mathbb{G}_{n,\lceil\frac{n}{2}\rceil-1}$. Suppose that the
cycles in $G$ are mutually disjoint.

  1. 1.

When $n\equiv 0\pmod{6}$,

$\rho(B(k+1,k-1,k+1))\leq\rho(G)$

with equality if and only if $G\cong B(k+1,k-1,k+1)$.

  2. 2.

When $n\equiv 4\pmod{6}$,

$\rho(B(k-1,k+1,k-1))\leq\rho(G)$

with equality if and only if $G\cong B(k-1,k+1,k-1)$.

###### Proof.

Since $G\in\displaystyle\mathbb{G}_{n,\lceil\frac{n}{2}\rceil-1}$ has at least
$n+1$ edges, $G$ contains at least two disjoint cycles. So, $G$ contains
$B^{*}=B(m^{*},p^{*},q^{*})$ for some integers $m^{*},q^{*}\geq 3$ and
$p^{*}\geq 1$. We choose $B^{*}$ having the minimum $p^{*}$ so that $B^{*}$ is
an induced subgraph of $G$.

Case 1. $n\equiv 0\pmod{6}$

Subcase 1a. $m^{*}+p^{*}+q^{*}=3k+1$.

Since $B^{*}$ is an induced subgraph of $G$, we have
$G=B^{*}=B(m^{*},p^{*},q^{*})$ and moreover $m^{*},p^{*},q^{*}$ are all odd by
Lemma 4.3.

First, assume that $p^{*}=k+1$. Then $(m^{*},q^{*})\neq(k,k)$ because $k$ is
even. Thus,

$\displaystyle\rho(G)=\rho(B(m^{*},k+1,q^{*}))$
$\displaystyle\geq\rho(B(k+1,k+1,k-1))$ (by Lemma 3.4)
$\displaystyle>\rho(B(k+1,k-1,k+1))$ (by Lemma 3.8)

Now assume $p^{*}\neq k+1$. Then we have $|\frac{m^{*}+q^{*}}{2}-p^{*}|\geq
2$. So,

$\displaystyle\rho(G)=\rho(B(m^{*},p^{*},q^{*}))$
$\displaystyle\geq\rho(B(\frac{m^{*}+q^{*}}{2},p^{*},\frac{m^{*}+q^{*}}{2}))$
(by Lemma 3.4)
$\displaystyle=\rho(P(\frac{m^{*}+q^{*}}{2},p^{*},\frac{m^{*}+q^{*}}{2}))$ (by
Lemma 3.2) $\displaystyle\geq\rho(P(k+1,k-1,k+1))$ (by Lemma 3.3)
$\displaystyle\geq\rho(B(k+1,k-1,k+1)).$ (by Lemma 3.2)

Subcase 1b. $m^{*}+p^{*}+q^{*}<3k+1$.

First assume that $p^{*}\neq k$ or $k+1$. Then it is not hard to see that by
removing all vertices outside of $B^{*}$ and reinserting them to internal
paths in $B^{*}$, one can find $(m^{\prime},p^{\prime},q^{\prime})$ such that
$m^{\prime}+p^{\prime}+q^{\prime}=3k+1$, $p^{\prime}$ is odd, $p^{\prime}\neq
k+1$ and $\rho(B(m^{\prime},p^{\prime},q^{\prime}))<\rho(B^{*})<\rho(G)$. Then
we have $|\frac{m^{\prime}+q^{\prime}}{2}-p^{\prime}|\geq 2$ and by the
similar argument as above,

$\rho(G)>\rho(B(m^{\prime},p^{\prime},q^{\prime}))\geq\rho(B(k+1,k-1,k+1)).$

Now assume that $p^{*}=k$ or $k+1$. Suppose that
$(m^{*},p^{*},q^{*})\neq(k,k,k)$, Then by removing all vertices outside of
$B^{*}$ except one and reinserting them to internal paths in $B^{*}$, one can
find $(m^{\prime},p^{\prime},q^{\prime})$ such that
$m^{\prime}+p^{\prime}+q^{\prime}=3k+1$, $p^{\prime}=k+1$, $m^{\prime}\neq
q^{\prime}$ and
$\rho(B(m^{\prime},p^{\prime},q^{\prime}))<\rho(B^{*})\leq\rho(G)$. Without
loss of generality, we may assume $m^{\prime}<q^{\prime}$. Since
$m^{\prime}+q^{\prime}=2k$, we have $m^{\prime}\leq k-1<k+1\leq q^{\prime}$.
Thus,

$\displaystyle\rho(G)>\rho(B(m^{\prime},p^{\prime},q^{\prime}))$
$\displaystyle\geq\rho(B(k-1,k+1,k+1)))$ (by Lemma 3.4)
$\displaystyle>\rho(B(k+1,k-1,k+1))$ (by Lemma 3.8)

Finally, suppose that $(m^{*},p^{*},q^{*})=(k,k,k)$. In this case, the graph
$G$ is the graph $B(k,k,k)$ with an extra vertex adjacent to some vertices of
$B(k,k,k)$. By Lemma 4.3,
$\alpha(B(k,k,k))=\lceil\frac{n-1}{2}\rceil=\frac{n}{2}$. Since an independent
set in $B(k,k,k)$ remains independent in $G$, this implies
$\alpha(G)\geq\frac{n}{2}$, which is a contradiction.

Therefore, we conclude that $\rho(G)\geq\rho(B(k+1,k-1,k+1))$ and we can check
in the proof that the equality holds if and only if $G\cong B(k+1,k-1,k+1)$.

Case 2. $n\equiv 4\pmod{6}$

Subcase 2a. $m^{*}+p^{*}+q^{*}=n+1=3k-1$.

By choice of $B^{*}$, $G$ should not have extra edges other than edges in
$B^{*}$. So, we have $G=B^{*}=B(m^{*},p^{*},q^{*})$ and moreover
$m^{*},p^{*},q^{*}$ are all odd by Lemma 4.3.

First assume that $p^{*}=k-1$. Then $(m^{*},q^{*})\neq(k,k)$ because $k$ is
even. Thus,

$\displaystyle\rho(G)=\rho(B(m^{*},k-1,q^{*}))$
$\displaystyle\geq\rho(B(k+1,k-1,k-1))$ (by Lemma 3.4)
$\displaystyle>\rho(B(k-1,k+1,k+1))$ (by Lemma 3.8)

Now assume $p\neq k-1$. Then we have $|\frac{m^{*}+q^{*}}{2}-p^{*}|\geq 2$.
So,

$\displaystyle\rho(G)=\rho(B(m^{*},p^{*},q^{*}))$
$\displaystyle\geq\rho(B(\frac{m^{*}+q^{*}}{2},p^{*},\frac{m^{*}+q^{*}}{2}))$
(by Lemma 3.4)
$\displaystyle=\rho(P(\frac{m^{*}+q^{*}}{2},p^{*},\frac{m^{*}+q^{*}}{2}))$ (by
Lemma 3.2) $\displaystyle\geq\rho(P(k-1,k+1,k-1))$ (by Lemma 3.3)
$\displaystyle\geq\rho(B(k-1,k+1,k-1)).$ (by Lemma 3.2)

Subcase 2b. $m^{*}+p^{*}+q^{*}<3k-1$.

First assume that $p^{*}\neq k-2$ or $k-1$. Then it is not hard to see that by
removing all vertices outside of $B^{*}$ and reinserting them to internal
paths in $B^{*}$, one can find $(m^{\prime},p^{\prime},q^{\prime})$ such that
$m^{\prime}+p^{\prime}+q^{\prime}=3k-1$, $p^{\prime}$ is odd, $p^{\prime}\neq
k-1$ and $\rho(B(m^{\prime},p^{\prime},q^{\prime}))<\rho(B^{*})\leq\rho(G)$.
Then we have $|\frac{m^{\prime}+q^{\prime}}{2}-p^{\prime}|\geq 2$ and by the
similar argument as above,

$\rho(G)>\rho(B(m^{\prime},p^{\prime},q^{\prime}))\geq\rho(B(k-1,k+1,k-1)).$

Now assume that $p^{*}=k-2$ or $k-1$. Suppose that
$(m^{*},p^{*},q^{*})\neq(k,k-2,k)$, Then by removing all vertices outside of
$B^{*}$ except one and reinserting them to internal paths in $B^{*}$, one can
find $(m^{\prime},p^{\prime},q^{\prime})$ such that
$m^{\prime}+p^{\prime}+q^{\prime}=3k-1$, $p^{\prime}=k-1$, $m^{\prime}\neq
q^{\prime}$ and
$\rho(B(m^{\prime},p^{\prime},q^{\prime}))<\rho(B^{*})\leq\rho(G)$. Without
loss of generality, we may assume $m^{\prime}<q^{\prime}$. Since
$m^{\prime}+q^{\prime}=2k$, we have $m^{\prime}\leq k-1<k+1\leq q^{\prime}$.
Thus,

$\displaystyle\rho(G)>\rho(B(m^{\prime},p^{\prime},q^{\prime}))$
$\displaystyle\geq\rho(B(k-1,k-1,k+1)))$ (by Lemma 3.4)
$\displaystyle>\rho(B(k+1,k-1,k+1))$ (by Lemma 3.8)

Finally, suppose that $(m^{*},p^{*},q^{*})=(k,k-2,k)$. In this case, the graph
$G$ is the graph $B(k,k-2,k)$ with an extra vertex adjacent to some vertices
of $B(k,k-2,k)$. By Lemma 4.3,
$\alpha(B(k,k-2,k))=\lceil\frac{n-1}{2}\rceil=\frac{n}{2}$. Since an
independent set in $B(k,k-2,k)$ remains independent in $G$, this implies
$\alpha(G)\geq\frac{n}{2}$, which is a contradiction.

Therefore, we conclude that $\rho(G)\geq\rho(B(k-1,k+1,k-1))$ and we can check
in the proof that the equality holds if and only if $G\cong B(k-1,k+1,k-1)$. ∎

By Proposition 4.6, Proposition 4.7 and Proposition 4.8, the proof of Theorem
1.1 is complete.

## References

  * [1] A.E. Brouwer and W.H. Haemers, Spectra of Graphs, Springer, New York, 2011.
  * [2] D. Cvetkovic, P. Rowlinson, S. Simić, An introduction to the Theory of Graph Spectra, Cambridge University Press, Cambridge, 2010.
  * [3] J. Das, S. Mohanty, On the spectral radius of bi-block graphs with given independence number $\alpha$, Appl. Math. Comput. 402(2021) 125912.
  * [4] X. Du, L. Shi, Graphs with small independence number minimizing the spectral radius, Discrete Math. Algorithms Appl. 5 (2013) 1350017.
  * [5] C. Godsil and G. Royle, Algebraic Graph Theory, Graduate Texts in Mathematics, 207. Springer-Verlag, New York, (2001).
  * [6] A. J. Hoffman, J. H. Smith, On the spectral radii of topologically equivalent graphs, in: Recent advances in Graph Theory, (Proceedings of the Symposium held in Prague, June 1974.)(ed. M. Fiedler) Academic, Prague, 1975, pp.273-281.
  * [7] Y. Hu, Q. Huang and Z. Lou, Graphs with the minimum spectral radius for given independence number, arXiv:2206.09152.
  * [8] Y.L. Jin, X.D. Zhang, The sharp lower bound for the spectral radius of connected graphs with the independence number, Taiwan. J. Math. 19(2) (2015) 419-431.
  * [9] Z. Lou, J. Guo, The spectral radius of graphs with given independence number, Discrete Mathematics 345 (2022) 112778.
  * [10] S. K. Simić, On the largest eigenvalue of bicyclic graphs, Publ. Inst. Math. (Beograd) 46 (60), (1989), 1-6.
  * [11] S. K. Simić, V. Lj. Kocić, On the largest eigenvalue of some homeomorphic graphs, Publ. Inst. Math. (Beograd) 40 (54) (1986), 3-9.
  * [12] J.H. Smith, Some properties of the spectrum of a graph, in: R. Guy et al.(Eds.), Combinatorial Structures and their applications, Proc. Conf. Calgary, 1969, Gordon and Breach, New York, 1970, pp. 403-406.
  * [13] D. Stevanovic, Spectral Radius of Graphs, Academic Press, Amsterdam, 2015.
  * [14] M.M. Wu, Y. Hong, J.L. Shu, M.Q. Zhai, The minimum spectral radius of graphs with a given independence number, Linear Algebra and its Appl. 431 (2009) 937-945.
  * [15] D.B. West, Introduction to Graph Theory, Prentice Hall, Inc., Upper Saddle River, NJ, (2001).
  * [16] B. Wu, E. Xiao, Y. Hong, The spectral radius of trees on $k$ pendant vertices, Linear Algebra and its Appl. 395 (2005) 343-349.


# mPLUG: Effective and Efficient Vision-Language Learning by Cross-modal Skip-
connections

Chenliang Li , Haiyang Xu∗, Junfeng Tian, Wei Wang, Ming Yan , Bin Bi†, Jiabo
Ye, Hehong Chen,
Guohai Xu, Zheng Cao, Ji Zhang, Songfang Huang, Fei Huang, Jingren Zhou, Luo
Si
DAMO Academy, Alibaba Group
{lcl193798, shuofeng.xhy, tjf141457, hebian.ww, ym119608, b.bi, yejiabo.yjb,
hehong.chh,
guohai.xgh, zhengzhi.cz, zj122146, songfang.hsf, f.huang, jingren.zhou,
<EMAIL_ADDRESS>
Equal contribution† Corresponding authors

###### Abstract

Large-scale pretrained foundation models have been an emerging paradigm for
building artificial intelligence (AI) systems, which can be quickly adapted to
a wide range of downstream tasks. This paper presents mPLUG, a new vision-
language foundation model for both cross-modal understanding and generation.
Most existing pre-trained models suffer from the problems of low computational
efficiency and information asymmetry brought by the long visual sequence in
cross-modal alignment. To address these problems, mPLUG introduces an
effective and efficient vision-language architecture with novel cross-modal
skip-connections, which creates inter-layer shortcuts that skip a certain
number of layers for time-consuming full self-attention on the vision side.

mPLUG is pre-trained end-to-end on large-scale image-text pairs with both
discriminative and generative objectives. It achieves state-of-the-art results
on a wide range of vision-language downstream tasks, such as image captioning,
image-text retrieval, visual grounding and visual question answering. mPLUG
also demonstrates strong zero-shot transferability when directly transferred
to multiple video-language tasks.

##  1 Introduction

Large-scale pre-training of vision-language models have recently received
tremendous success on a wide range of cross-modal tasks [1, 2, 3, 4, 5, 6, 7].
Such vision-language models learn cross-modal representations from a quantity
of image-text pairs by aligning the visual and linguistic modalities. A great
challenge of learning vision-language models is to find a good alignment
between the two modalities to close the semantic gap in-between.

Figure 1: Illustration of two conventional cross-modal fusion networks and our
proposed cross-modal skip-connected network. We compare the running time and
performance of different fusion networks, where the total fusion layers, image
encoder and text encoder are all kept the same. The running time is the total
forward time of 100 samples in different fusion networks.

To discover a cross-modal alignment, prior studies [4, 8, 9] employ a pre-
trained object detector to extract salient regions from images, which are then
aligned with language counterparts. Such an architecture, however, is
generally limited by the power of the object detector, the pre-defined visual
semantics it can represent, and the quantity of annotations available.
Besides, it is also computationally expensive to extract region-based visual
features from high-resolution (e.g. 600$\times$1000) images. More recent work
[3, 7, 6, 10, 11], which scales and performs better on many vision-language
tasks, drops the requirement of pre-trained object detection and enables a
direct alignment between the image and text representations in an end-to-end
manner. These models extract finer-grained visual representation with a long
sequence of image patches or grids for good vision understanding [11].
However, there exist two significant problems in modeling long visual
sequences: 1) efficiency: full self-attention on long visual sequences
requires much more computation than that on textual sequences, and 2)
information asymmetry: the caption text in widely-used image-text pre-training
data is usually short and highly abstract while more detailed and diverse
information can be extracted from the image. This asymmetry presents
challenges for effective multi-modal fusion between the modalities.

One straightforward way of multi-modal fusion is the connected-attention
network as shown in Figure 1 (a). It adopts a single Transformer [12] network
for early fusion of vision and language by simply taking the concatenation of
visual and linguistic features as input [13]. This paradigm allows self-
attention to discover alignments between the modalities from the bottom level,
and requires full self-attention on the concatenation of cross-modal
sequences, which is rather time-consuming. Besides, this type of methods
process information from both modalities equally, which may suffer from the
information asymmetry especially when there is a big difference in information
density or sequence lengths between the modalities.

Another line of work keeps separate Transformer networks for both textual and
visual features, and uses techniques such as cross-attention to enable cross-
modal interaction [11], as shown in Figure 1 (b). This architecture design
conducts multi-modal fusion on both modalities independently, which can help
alleviate the information asymmetry problem. However, it still suffers from
computation inefficiency for full self-attention on long visual sequences, and
it is not that parameter-efficient with two separate Transformer networks.

In this work, we propose mPLUG, a unified Multi-modal Pre-training framework
for both vision-Language Understanding and Generation. mPLUG performs
effective and efficient vision-language learning with novel cross-modal skip-
connections to address the fundamental information asymmetry problem. Instead
of fusing visual and linguistic representations at the same levels, the cross-
modal skip-connections enables the fusion to occur at disparate levels in the
abstraction hierarchy across the modalities. It creates inter-layer shortcuts
that skip a certain number of layers for visual representations to reflect the
semantic richness of language compared to vision. As shown in Figure 1 (c), in
each block of our cross-modal skip-connected network, mPLUG first adopts an
asymmetric co-attention architecture at the first few layers for efficiency,
by removing the co-attention on vision side. It is then followed by one layer
of connected-attention, by concatenating the original visual representation
and the co-attention output on the language side as input. In addition to the
modeling efficacy due to the asymmetry, the cross-modal skip-connections ease
the model training by alleviating vanishing gradients with the inserted
shortcuts. Figure 1 shows that the new cross-modal skip-connected network
achieves superior performance with at least four times speeding-up than other
cross-modal fusion networks.

Our key contributions can be summarized as follows:

  * •

We propose a unified vision-language pretrained model mPLUG of cross-modal
understanding and generation for both effectiveness and efficiency in cross-
modal learning.

  * •

We introduce a new asymmetric vision-language architecture with novel cross-
modal skip-connections, to address two fundamental problems of information
asymmetry and computation inefficiency in multi-modal fusion.

  * •

mPLUG achieves state-of-the-art performance on a wide range of vision-language
tasks, including image captioning, image-text retrieval, visual grounding and
visual question answering. mPLUG also demonstrates strong zero-shot
transferability when directly transferred to a wide range of vision-language
and video-language tasks.

##  2 Related Work

###  2.1 Vision-Language Pre-training

Vision-Language pre-training (VLP) has recently received tremendous success
and achieved state-of-the-art results across a variety of vision-language
tasks [14, 15, 16]. In terms of how information from different modalities are
aggregated, typical approaches to VLP [1, 2, 3, 5, 6, 17, 18] can be roughly
divided into two categories: dual encoder and fusion encoder. Dual encoder
approach utilizes two single-modal encoders to encode images and text
separately, and then uses simple functions such as dot product to model the
instance-level cross-modal interaction between image and text. The advantage
of dual encoder models like CLIP [17] and ALIGN [18] is that images and text
can be pre-computed and cached, which is quite computation-efficient and more
appropriate for retrieval tasks. However, they tend to fail in handling more
complicated VL understanding tasks that require complex reasoning, such as
visual question answering [14]. In contrast, fusion encoder approach uses deep
fusion functions such as multi-layer self-attention and cross-attention
networks to model the fine-grained cross-modal interaction between image and
text sequences. Representative methods of this category include the single-
stream architecture such as UNITER [2] and OSCAR [4], and two-stream
architecture such as LXMERT [1], ALBEF [6] and ERNIE-ViL [5]. This kind of
methods can better capture the underlying association between image and text
for vision-language understanding tasks, while it needs to jointly encode all
possible image-text pairs, which leads to a relatively slow inference speed.

To improve the inference speed, some recent work such as Pixel-BERT [3],
E2E-VLP [19] and ViLT [10] removes the complicated object detector in feature
extraction, and conducts end-to-end VL learning with CNN-based grid features
and linearly projected patched embeddings, respectively. To combine the
benefits of both categories of architectures, VLMo [20] further unifies the
dual encoder and fusion encoder modules with shared mixture-of-modality-
experts Transformer. In this work, mPLUG introduces a new cross-modal fusion
mechanism with cross-modal skip-connections, to enables the fusion to occur at
disparate levels in the abstraction hierarchy across the modalities. It
achieves superior performances in effectiveness and efficiency across a wide
range of VL tasks.

###  2.2 Skip-connection

Skip-connection is a popular technique to bypass the gradient exploding or
vanishing problem for model optimization in deep neural networks, which is
widely-used in CV and NLP architectures such as ResNet [21] and Transformer
[12]. A variety of skip connection methods have been proposed in recent years
[22, 21, 12, 23, 24, 25]. ResNet [21] introduces summed shortcut connections
between different layers using simple identity mapping, while highway network
[22] designs a transform gating function to control the balance of the input
and the transformed input. DenseNet [23] designs new architectures with
concatenated skip-connections, allowing the subsequent layers to re-use all
the middle representations of previous layers. Layer Normalization and
recursive skip connection are further used in combination with plain skip
connection for further stablizing model optimization and better incorporating
the transformed input [12, 25]. In this work, mPLUG proposes a new cross-modal
skip connection method to address cross-modal fusion problem, and combines the
concatenated skip-connection and summed skip-connection for choosing whether
to attend to all the concatenated representations of different modalities or
just focus on the cross-modal interaction part at each layer.

(a)  (b)

Figure 2: The model architecture and objectives of mPLUG, which consists of
two unimodal encoders for images and text separately, a cross-modal skip-
connected network and a decoder for text generation. An image-text contrastive
loss is first applied to align the unimodal representations from the visual
encoder and text encoder. Then, we use a novel cross-modal skip-connected
network to fuse the visual and linguistic representations effectively and
efficiently. We adopt connected cross-modal fusion to every $S$ asymmetric co-
attention layers, where $S$ is a fixed stride value. Based on the connected
representation of the image and prefix sub-sequence, the decoder is trained
with a prefix language modeling (Prefix LM) loss by generating the remaining
caption.

##  3 mPLUG

In this section, we will first introduce our new model architecture with the
key module of the cross-modal skip-connected network, and then give the
details of the pre-training objectives and scalable training infrastructure.

###  3.1 Model Architecture

As shown in Figure 2, mPLUG consists of two unimodal encoders for image and
text independently, a cross-modal skip-connected network and a decoder for
text generation. To better model the inherent modality bias information, we
first use two unimodal encoders to encode image and text separately. Following
[11, 26], we use a visual transformer [27] directly on the image patches as
the visual encoder, which is more computation-friendly than using pre-trained
object detectors for visual feature extraction [8, 9]. The visual encoder
divides an input image into patches and encodes them as a sequence of
embeddings $\\{v_{cls},v_{1},v_{2},...,v_{M}\\}$ with an additional $[CLS]$
token. The input text is fed to the text encoder and represented as a sequence
of embeddings $\\{l_{cls},l_{1},l_{2},...,l_{N}\\}$, where $l_{cls}$ is the
embedding of the $[CLS]$ token and used to summarize the input text. Then, the
visual and linguistic representations are fed into a cross-modal skip-
connected network, which consists of multiple skip-connected fusion blocks. In
each skip-connected fusion block, we adopt connected cross-modal fusion to
each of $S$ asymmetric co-attention layers where $S$ is a fixed stride value.
The aim of this network is to take advantage of the effectiveness of the
connected cross-modal fusion and the efficiency of the asymmetric co-attention
for enhanced cross-modal fusion in a recursive manner. Finally, the output
cross-modal representations are fed into a transformer decoder for sequence to
sequence learning, which equips mPLUG with both understanding and generation
capabilities.

###  3.2 Cross-modal Skip-connected Network

The cross-modal skip-connected network consists of $N$ skip-connected fusion
blocks. In each skip-connected fusion block, we adopt connected-attention
layer to each of $S$ asymmetric co-attention layers where $S$ is a fixed
stride value. We first pass the text feature and image feature from unimodal
encoders through the $S$ asymmetric co-attention layers, and then connect the
output text feature and image feature to one connected-attention layer. We
repeat the skip-connected fusion block $N$ times for the final connected image
and text representation.

Specifically, the asymmetric co-attention is composed of the self-attention
(SA) layer, cross-attention (CA) layer and the feed-forward network (FFN). The
input text feature $l^{n-1}$ is first fed to the self-attention layer, and
then the visual feature $v^{n-1}$ is injected into the text feature
$l^{n}_{SA}$ by the cross-attention layer which gives $l^{n}_{CA}$. The output
of self-attention $l^{n}_{SA}$ and cross-attention $l^{n}_{SA}$ are added up
and fed to the FFN layer for the visual-aware text representation $l^{n}$:

$l^{n}_{SA}=LN(SA(l^{n-1})+l^{n-1})$ (1)
$l^{n}_{CA}=LN(CA(l^{n}_{SA},v^{n-1})+l^{n}_{SA})$ (2)
$l^{n}=LN(FFN(l^{n}_{CA})+l^{n}_{CA})$ (3)

where LN is short for layer normalization.

The connected-attention layer is composed of the self-attention (SA) layer and
the feed-forward network (FFN). We connect the image feature $v^{n-1}$ and
input text feature $l^{n-1}$, where $l^{n-1}$ is the output of $S$ asymmetric
co-attention layers. The connected image and text feature $[v^{n-1};l^{n-1}]$
are fed to the self-attention layer and FFN layer:

$[v^{n}_{SA};l^{n}_{SA}]=LN(SA([v^{n-1};l^{n-1}])+[v^{n-1};l^{n-1}])$ (4)
$[v^{n};l^{n}]=LN(FFN([v^{n}_{SA};l^{n}_{SA}])+[v^{n}_{SA};l^{n}_{SA}])$ (5)

Then $[v^{n};l^{n}]$ is fed into the next cross-modal skip-connected network
repeatedly to get the final connected image and text representation. Finally,
the connected output is fed into a Transformer decoder for sequence to
sequence learning.

###  3.3 Pre-training Tasks

We perform four pre-training tasks including three understanding tasks (Image-
Text Contrastive Learning, Image-Text Matching, Masked Language Modeling) and
one generation task (Prefix Language Modeling). These pre-training tasks are
optimized jointly.

Image-Text Contrastive (ITC): Following [6], we employ the task to align the
image features and the text features from the unimodal encoders. Specifically,
we calculate the softmax-normalized image-to-text and text-to-image
similarity, and take two dynamic memory queues (text, image) to increase the
number of negative examples as MoCo [28].

Image-Text Matching (ITM): This task aims to predict whether an image and a
sentence match with each other on the cross-modal representation. We also
select hard negative image-text pairs based on the contrastive text-image
similarity as [6].

Masked Language Modeling (MLM): The task setup is basically the same as in
BERT [29], where we randomly mask $15\%$ of tokens in text and the model is
asked to predict these masked words with the cross-modal representations.

Prefix Language Modeling (PrefixLM): This task aims to generate the caption
given an image and predict the text segment subsequent to the cross-modal
context as [30]. It optimizes a cross entropy loss by maximizing the
likelihood of text in an autoregressive manner.

##  4 Distributed Learning on a Large Scale

Training a big model like mPLUG on large-scale datasets faces many efficiency
challenges. We increase the throughput from the perspective of reducing memory
usage and computation time, thereby accelerating the training of the model.

The memory usage during model training is mainly composed of two aspects: the
static memory usage composed of parameters/optimizer states/gradients, etc.,
and the runtime memory usage caused by intermediate variables like activation
values. For static memory overhead, we use the ZeRO [31] technique to
partition parameters/optimizer states/gradients into the entire data-parallel
group, so that the static memory overhead of a single GPU can be approximately
reduced to $1/N$, where $N$ denotes the number of GPU cards. We use gradient
checkpointing [32] for the runtime memory cost, which greatly reduces the
runtime memory usage at the expense of increasing forward time by recomputing
part of the activation values during backward pass without keeping them in
memory.

To reduce the computation time, we use BF16 precision training. BF16 is a new
data type supported by NVIDIA’s new Ampere architecture GPU like A100.
Compared with the previously widely used mixed-precision training of FP16 and
FP32, BF16 has the same representation range as FP32, thereby reducing the
risk of numerical overflow and ensuring model convergence stability, and at
the same time has the same fast computing speed as FP16.

##  5 Experiments

###  5.1 Data & Setup

Models | Data | COCO Caption | NoCaps
---|---|---|---
Cross-entropy Optimization | CIDEr Optimization |
B@4 | M | C | S | B@4 | M | C | S | C | S
Encoder-Decoder | CC12M | - | - | 110.9 | - | - | - | - | - | 90.2 | 12.1
E2E-VLP [19] | 4M | 36.2 | - | 117.3 | - | - | - | - | - | - | -
VinVL [9] | 5.65M | 38.5 | 30.4 | 130.8 | 23.4 | 41.0 | 31.1 | 140.9 | 25.2 | 97.3 | 13.8
OSCAR [4] | 6.5M | - | - | - | - | 41.7 | 30.6 | 140.0 | 24.5 | 83.4 | 11.4
SimVLMlarge [7] | 1.8B | 40.3 | 33.4 | 142.6 | 24.7 | - | - | - | - | - | -
LEMONlarge [33] | 200M | 40.6 | 30.4 | 135.7 | 23.5 | 42.3 | 31.2 | 144.3 | 25.3 | 113.4 | 15.0
BLIP [34] | 129M | 40.4 | - | 136.7 | - | - | - | - | - | 113.2 | 14.8
OFA [35] | 18M | - | - | - | - | 43.5 | 31.9 | 149.6 | 26.1 | - | -
mPLUG | 14M | 43.1 | 31.4 | 141.0 | 24.2 | 46.5 | 32.0 | 155.1 | 26.0 | 114.8 | 14.8
Table 1: Evaluation Results on COCO Caption ”Karpathy” test split and NoCaps
validation set. B@4: BLEU@4, M: METEOR, C: CIDEr, S: SPICE.

Following the previous work [6], we use the same pre-training dataset with 14M
images with texts, which includes two in-domain datasets (MS COCO [36] and
Visual Genome [37]), and three web out-domain datasets (Conceptual Captions
[38], Conceptual 12M [39], SBU Captions [40].

We pretrain the model for 30 epochs with the total batch size of 1024 on 16
NVIDIA A100 GPUs. We use a 6-layer Transformer for both the text encoder and
the cross-modal skip-connected network, and a 12-layer Transformer for the
decoder. The text encoder is initialized using the first 6 layers of the
BERTbase [29] model and the skip-connected network is initialized using the
last 6 layers of the BERTbase. We initialize the visual encoder by CLIP-ViT
[17] pretrained on 400M noisy image-text pairs. The visual transformer with
ViT-B/16 is used as our base architecture, the one with ViT-L/14 as the large
architecture. We use the AdamW [41] optimizer with a weight decay of 0.02. The
learning rate is warmed-up to 1e-5 (ViT-B/16) and 1e-4 (BERTbase) for
mPLUGViT-B , and 5e-6 (ViT-L/14) and 5e-5 (BERTbase) for mPLUGViT-L in the
first 1000 iterations, and decayed to 1e-6 following a cosine schedule. During
pre-training, we take random image crops of resolution 256 $\times$ 256
(ViT-B/16)/224 $\times$ 224 (ViT-L/14) as input, and also apply RandAugment
[42] to improve the generalization of vision encoders. For VQA and image
captioning tasks, we do an additional continue pre-training on 4M image-text
pairs. We increase the image resolution during finetuning. For image-text
contrastive learning, the queue size is set as 65,536 and the momentum
coefficient is set as 0.995.

###  5.2 Evaluation on Vision-Language Tasks

We compare our pre-trained model against other VLP models on the six
downstream V+L tasks. We introduce each task and our fine-tuning strategy
below. Details of the datasets and fine-tuning hyperparameters are in
Appendix.

Models | Data | Test-dev | Test-std
---|---|---|---
_Pretrained on COCO, VG, SBU and CC datasets_
VLBERT [43] | 4M | 71.16 | -
E2E-VLP [19] | 4M | 73.25 | 73.67
VL-T5 [44] | 4M | - | 71.30
UNITER[2] | 4M | 72.70 | 72.91
OSCAR[4] | 4M | 73.16 | 73.44
CLIP-ViL[26] | 4M | 76.48 | 76.94
METER[11] | 4M | 77.68 | 77.64
ALBEF[6] | 4M | 74.54 | 74.70
mPLUGViT-B | 4M | 77.94 | 77.96
_Models Pretrained on More Data_
ALBEF [6] | 14M | 75.84 | 76.04
BLIP [34] | 129M | 78.25 | 78.32
SimVLM [7] | 1.8B | 80.03 | 80.34
Florence [45] | 0.9B | 80.16 | 80.36
OFA [35] | 18M | 79.87 | 80.02
VLMo [20] | - | 79.94 | 79.98
mPLUGViT-B | 14M | 79.79 | 79.81
mPLUGViT-L | 14M | 81.27 | 81.26
Table 2: Evaluation Results on VQA test set.

####  5.2.1 Visual Question Answering

The VQA task [14] requires the model to answer natural language questions
given an image. Most methods [1, 20, 4, 7] deal with visual question answering
tasks as multi-label classification on predefined answer sets. This strategy
achieves strong performance, but it is not suitable for real-world open
scenarios. We treat VQA as an answer generation task and directly use
unconstrained open-vocab generation during inference, which is different from
constrained close-vocab generation models [6, 35]. Following [4, 35], we
concatenate the question with the object labels and OCR tokens extracted from
image. As shown in Table 2, mPLUG achieves 81.27 on Test-std split and
outperforms the SOTA models including SimVLM and Florence, which use 100$X$
and 60$X$ more pre-training image-text pairs, respectively. Based on the same
4M pre-training data, mPLUG outperforms CLIP-ViL and METER, which also use
CLIP [17] as the visual encoder. Besides, under the same settings, mPLUG
always significantly outperforms ALBEF and BLIP which only rely on co-
attention from images to text for cross-modal fusion. The gain can derive from
the network design of cross-modal skip-connections specifically for
information asymmetry of the two modalities. Neither ALBEF nor BLIP addresses
this problem well, with bias towards the language modality.

Models | # Pretrain | MSCOCO (5K test set) | Flickr30K (1K test set)
---|---|---|---
data | TR | IR | TR | IR
|  | R@1 | R@5 | R@10 | R@1 | R@5 | R@10 | R@1 | R@5 | R@10 | R@1 | R@5 | R@10
E2E-VLP [19] | 4M | - | - | - | - | - | - | 86.2 | 97.5 | 98.92 | 73.6 | 92.4 | 96.0
UNITER [2] | 4M | 65.7 | 88.6 | 93.8 | 52.9 | 79.9 | 88.0 | 87.3 | 98.0 | 99.2 | 75.6 | 94.1 | 96.8
OSCAR [4] | 4M | 70.0 | 91.1 | 95.5 | 54.0 | 80.8 | 88.5 | - | - | - | - | - | -
UNIMO [46] | 4M | - | - | - | - | - | - | 89.4 | 98.9 | 99.8 | 78.0 | 94.2 | 97.1
VLMo [20] | 4M | 78.2 | 94.4 | 97.4 | 60.6 | 84.4 | 91.0 | 95.3 | 99.9 | 100.0 | 84.5 | 97.3 | 98.6
ALIGN [18] | 1.8B | 77.0 | 93.5 | 96.9 | 59.9 | 83.3 | 89.8 | 95.3 | 99.8 | 100.0 | 84.9 | 97.4 | 98.6
ALBEF [6] | 14M | 77.6 | 94.3 | 97.2 | 60.7 | 84.3 | 90.5 | 95.9 | 99.8 | 100.0 | 85.6 | 97.5 | 98.9
Florence [45] | 0.9B | 81.8 | 95.2 | - | 63.2 | 85.7 | - | 97.2 | 99.9 | - | 87.9 | 98.1 | -
BLIP [34] | 14M | 80.6 | 95.2 | 97.6 | 63.1 | 85.3 | 91.1 | 96.6 | 99.8 | 100.0 | 87.2 | 97.5 | 98.8
BLIP [34] | 129M | 82.4 | 95.4 | 97.9 | 65.1 | 86.3 | 91.8 | 97.4 | 99.8 | 99.9 | 87.6 | 97.7 | 99.0
mPLUG | 14M | 82.8 | 96.1 | 98.3 | 65.8 | 87.3 | 92.6 | 97.6 | 100.0 | 100.0 | 88.4 | 97.9 | 99.1

Table 3: Image-text retrieval results on Flickr30K and COCO datasets.

####  5.2.2 Image Captioning

The image captioning task requires a model to generate an appropriate and
fluent caption for a given image. We evaluate image captioning on two datasets
COCO Caption [47] and NoCaps [48]. mPLUG finetuned with training data of COCO
Caption is tested on both of the datasets. We train mPLUG on the MS COCO
Caption and test on the same Karpathy split [4, 7] and NoCaps validation set.
Following [4, 35], we first fine-tune mPLUG with cross-entropy loss and then
with CIDEr optimization [49] for extra 5 epochs. As shown in Table 1, mPLUG
with only 14M pre-training images can outperform the SOTA models including
LEMON and SimVLM on both COCO Caption and Nocaps datasets, which uses more
than 10$X$ and 100$X$ pre-training data, respectively. For the COCO Caption,
mPLUG performs the best on CIDEr evaluation and surpasses the SOTA model by a
large margin of 5.5 on Karpathy test set. We use the best checkpoint on COCO
Caption and predict on the Nocaps validation set directly.

Model | RefCOCO | RefCOCO+ | RefCOCOg
---|---|---|---
val | testA | testB | val | testA | testB | val-u | test-u
VLBERT [43] | - | - | - | 72.59 | 78/57 | 62.30 | - | -
UNITER [2] | 81.41 | 87.04 | 74.17 | 75.90 | 81.45 | 66.70 | 74.86 | 75.77
VILLA [50] | 82.39 | 87.48 | 74.84 | 76.17 | 81.54 | 66.84 | 76.18 | 76.71
MDETR [51] | 86.75 | 89.58 | 81.41 | 79.52 | 84.09 | 70.62 | 81.64 | 80.89
UNICORN [52] | 88.29 | 90.42 | 83.06 | 80.30 | 85.05 | 71.88 | 83.44 | 83.93
OFA [35] | 90.05 | 92.93 | 85.26 | 84.49 | 90.10 | 77.77 | 84.54 | 85.20
mPLUG | 92.40 | 94.51 | 88.42 | 86.02 | 90.17 | 78.17 | 85.88 | 86.42
Table 4: Visual grounding results<EMAIL_ADDRESS>on ReferCOCO, ReferCOCO+, and
ReferCOCOg.

####  5.2.3 Image-Text Retrieval

We conduct experiments for both image-to-text retrieval (TR) and text-to-image
retrieval (IR) on COCO [36] and Flickr30K [53] datasets. Following [6, 34], we
jointly optimize the ITC loss and the ITM loss during fine-tuning. During
inference, we first select top-k candidates by computing the dot-product
similarity between the image and text encoder features, and then rerank the
selected candidates based on their ITM scores. We set $k=256$ for COCO and
$k=128$ for Flickr30K. As shown in Table 3, mPLUG outperforms all existing
methods on both datasets. Using 14M images, mPLUG achieves better performance
than BLIP with 129M and Florence with 0.9B pre-training data. Using the same
14M pre-training images, mPLUG substantially outperforms the previous best
model BLIP by +2.7% in TR recall@1 on COCO and +1.0 % in TR recall@1 on
Flickr30K.

####  5.2.4 Visual Grounding

Given a query in plain text and an image, visual grounding requires models to
localize the referred object in the image. Instead of regressing the bounding
boxes directly, we concatenate visual features and attended textual features
and feed them into the decoder to predict the coordinates. Table 4 shows that
mPLUG outperforms all the SOTA methods. We observe that in RefCOCO testB the
images often contain arbitrary objects and in RecCOCOg test-u the expressions
are longer than other datasets. Compared with the previous best model OFA,
mPLUG achieves 3.16% absolute improvement on RefCOCO testB and 1.22% absolute
improvement on RefCOCOg test-u. It demonstrates that mPLUG learns better
multi-modal interaction from cross-modal skip-connections and is better at
handling complex images and long queries.

####  5.2.5 Visual Reasoning

We consider two datasets for visual reasoning: NLVR2 [54] and SNLI-VE [55].
The NLVR2 [54] task requires the model to predict whether a sentence describes
a pair of images. Following [34], we use two cross-attention layers to process
the two input images, and their outputs are merged and fed to the FFN. An MLP
classifier is then applied on the output embedding of the language [CLS]
token. The SNLI-VE [55] task requires the model to evaluate how the given
image and text are semantically correlated, i.e., entailment, neutral, or
contradiction. Following [35], the image premise, text premise and text
hypothesis are fed to the encoder. While we remove the decoder, and only use
the encoder modules for three-way classification, which can save nearly half
of the total computation cost. We predict the class probabilities using the
multimodal encoder’s output representation of the language [CLS] token. As
shown in Table 5, mPLUG can obtain competitive performances to the SOTA models
111The SOTA models such as OFA and VLMo both add large-scale text-only and
image-only pre-training data for improving the reasoning ability. in both
visual reasoning tasks, and even outperform SimVLM [7] and BLIP [34], which
use far more pre-training data.

Model | NLVR2 | SNLI-VE
---|---|---
dev | test-P | dev | test
LXMERT[1] | 74.90 | 74.50 | - | -
VL-T5[44] | - | 73.6 | - | -
UNITER[2] | 79.12 | 79.98 | 79.39 | 79.38
CLIP-ViL[26] | - | - | 80.61 | 80.20
METER[11] | 82.33 | 83.05 | 80.86 | 81.19
UNIMO[46] | - | - | 81.11 | 80.63
ALBEF[6] | 82.55 | 83.14 | 80.80 | 80.91
BLIP[34] | 82.67 | 82.30 | - | -
SimVLMlarge[7] | 84.13 | 84.84 | 85.68 | 85.62
VLMo[20] | 85.64 | 86.86 | - | -
OFA[35] | - | - | 90.30 | 90.20
mPLUG | 84.58 | 84.95 | 89.45 | 89.29
Table 5: Evaluation Results on NLVR2 and SNLI-VE.

###  5.3 Effectiveness and Efficiency

To validate the effectiveness and efficiency of our proposed cross-modal skip-
connected network, we conduct in-depth analysis on different stride values and
various cross-modal fusion methods.

####  5.3.1 Analysis of Stride for Skip

Figure 3: Results w.r.t different stride values in cross-modal skip-connected
network on running time and performance of VQA test-dev and NLVR2 test-P,
where the running time is the total forward time of 100 samples.

The stride _S_ is the key factor to control the effectiveness and efficiency
tradeoff. Therefore, we further compare the running time and performance of
different stride value _S_ in cross-modal skip-connected network on VQA and
NLVR2 tasks. Specifically, we test four different stride values, which can be
divisible by the total number of cross-modal fusion layers. The model is
chosen as mPLUGViT-B and all the other experiment settings are kept the same.
As shown in Figure 3, we can see that the larger _S_ is, the more efficient
cross-modal fusion is, where the running time can be largely reduced from
skipping the vision co-attention layers by 5$X$ times from $\emph{S}=1$ to
$\emph{S}=6$. The performances of mPLUG on both datasets gradually increases
when $\emph{S}=3$, and slightly decreases later on. Compared with
$\emph{S}=3$, mPLUG can achieve comparable performance at $\emph{S}=6$, while
speeding up by nearly 30%. Therefore, we set $\emph{S}=6$ on mPLUGViT-L for
faster pre-training.

####  5.3.2 Analysis of Cross-modal Fusion

Figure 4: Results w.r.t different cross-modal fusions on running time and
performance on VQA test-dev and NLVR2 test-P, where the running time is the
total forward time of 100 samples.

We compare the effectiveness and efficiency of different cross-modal fusion
variants in terms of running time and performance on VQA and NLVR2 tasks.
Specifically, we pre-train mPLUG with different cross-modal fusion network
based on the same image encoder and text encoder. All the pre-training
settings and the number of fusion layers are kept the same as in the original
mPLUG pre-training. As shown in Figure 4, the fusion methods of co-attention
and connected-attention both requires much more running time due to long
visual sequence. Compared with the two fusion methods, our proposed skip-
connected network is 4$X$ faster and obtain better performance on both
datasets. We also compare it with the asymmetric co-attention used in BLIP [6,
34] which only relies on the co-attention layers from images to text. Despite
running slightly faster than the skip-connected network does, the asymmetric
co-attention performs worse in accuracy on both datasets. The performance
degradation is attributed to the information asymmetry and bias towards
language, as shown in Section 5.2.1.

Model | Throughput (Samples/S)
---|---
baseline | 124.0
\+ BFloat16 | 182.7
\+ Gradient Checkpoint | 238.2
\+ ZeRO | 422.5
Table 6: Training Throughput

####  5.3.3 Large-scale Training

Combining the techniques introduced in Section 4 has dramatically increased
the training throughput. With the utilization of memory saving and accelerated
training techniques, the throughput of mPLUG improves 3$X$ more from 124
samples per second to 422 samples per second, as shown in Table 6.

Model | In | Near | Out | Overall
---|---|---|---|---
SimVLMbase[7] | 83.2 | 84.1 | 82.5 | 83.5
SimVLMhuge[7] | 101.2 | 100.4 | 102.3 | 101.4
Oscar$\dagger$[4] | 85.4 | 84.0 | 80.3 | 83.4
VinVL$\dagger$[9] | 103.7 | 95.6 | 83.8 | 94.3
SimVLMhuge$\dagger$[7] | 113.7 | 110.9 | 115.2 | 112.2
mPLUG | 86.34 | 81.5 | 90.49 | 84.02
mPLUG$\dagger$ | 116.7 | 113.75 | 117.0 | 114.8
Table 7: Image captioning results on NoCaps validation split (zero-shot and finetuned), and {In, Near, Out} refer to in-domain, near-domain and out-of-domain respectively. $\dagger$ denotes the models finetuned on COCO Caption dataset. Model | TR | IR
---|---|---
R@1 | R@5 | R@1 | R@5
_Zero-Shot_
CLIP [17] | 88.0 | 98.7 | 68.7 | 90.6
ALIGN [18] | 88.6 | 98.7 | 75.7 | 93.8
FLIP [56] | 89.8 | 99.2 | 75.0 | 93.4
Florence [45] | 90.9 | 99.1 | 76.7 | 93.6
ALBEF$\dagger$ [6] | 94.1 | 99.5 | 82.8 | 96.3
BLIP$\dagger$ [34] | 94.8 | 99.7 | 84.9 | 96.7
mPLUG | 93.0 | 99.5 | 82.2 | 95.8
mPLUG$\dagger$ | 95.8 | 99.8 | 86.4 | 97.6
Table 8: Zero-shot image-text retrieval results on Flickr30K. $\dagger$ denotes the models finetuned on COCO.  Model | # Pretrain | MSRVTT-Retrieval
---|---|---
data | R@1 | R@5 | R@10
_Zero-Shot_
MIL-NCE [57] | How100M | 9.9 | 24.0 | 32.4
VideoCLIP [58] | How100M | 10.4 | 22.2 | 30.0
VATT [59] | How100M, AudSet | - | - | 29.7
ALPRO [60] | W2M, C3M | 24.1 | 44.7 | 55.4
VIOLET [61] | Y180M, W2M, C3M | 25.9 | 49.5 | 59.7
CLIP [17] | WIT400M | 26.0 | 49.4 | 60.7
Florence [45] | FLD900M | 37.6 | 63.8 | 72.6
BLIP $\dagger$ [34] | 129M | 43.3 | 65.6 | 74.7
mPLUG | 14M | 38.1 | 59.2 | 68.2
mPLUG $\dagger$ | 14M | 44.3 | 66.4 | 75.4
_Fine-Tuning_
VideoCLIP [58] | How100M | 30.9 | 55.4 | 66.8
ALPRO [60] | C3M, W2M | 33.9 | 60.7 | 73.2
VIOLET [61] | Y180M, C3M, W2M | 34.5 | 63.0 | 73.4
Table 9: Zero-shot video-language results on text-to-video retrieval on the 1k
test split of the MSRVTT dataset. $\dagger$ denotes the models finetuned on
COCO. Video datasets include HowTo100M [62], WebVid-2M(W2M) [63], YT-
Temporal-180M( Y180M) [64]. Image datasets include CC3M(C3M) [38], FLD900M
[45], WIT400M [17]. Audio datasets include AudioSet(AudSet) [65].

###  5.4 Zero-shot Transferability

In this section, we examine the generalization of mPLUG and compare the zero-
shot result on two Vision-Language and three Video-Language tasks.

####  5.4.1 Zero-shot Vision-Language Tasks

The pretraining of mPLUG adopts image-text contrastive and prefix language
modeling tasks on large-scale image-text pairs. Thus, mPLUG has zero-shot
generalization ability in image-text retrieval and image captioning. Image
Caption: First, we take the pretrained mPLUG model and directly decode on
NoCaps validation set without further finetuning. Following[7, 34], we feed a
prefix prompt _“A picture of”_ into the text encoder to improve the quality of
decoded captions. As shown in Table 7, the zero-shot performance of mPLUG is
competitive with fully supervised baselines such like Oscar and VinVL. With
further finetuning on MSCOCO dataset, mPLUG outperforms the SimVLMhuge, which
use more pre-training image-text pairs and has larger model parameters. Image-
text Retrieval: We perform zero-shot retrieval on Flickr30K. The result is
shown in Table 8, where zero-shot mPLUG outperforms models (CLIP, ALIGN,
Florence) pretrained with more image-text pairs. Following [34], we also
evaluate zero-shot retrieval by the model finetuned on MSCOCO dataset. Table 8
shows that mPLUG achieves better performance than the previous SOTA models.

####  5.4.2 Zero-shot Transfer to Video-Language Tasks

To evaluate the generalization ability of mPLUG to Video-Language Tasks, we
conduct zero-shot experiments on Video-text Retrieval, Video Caption and Video
Question Answering. Following [34], we uniformly sample $n$ frames for each
video ($n=8$ for Retrieval, $n=16$ for QA, $n=8$ for Caption), and concatenate
the frame features into a single sequence. Video-text Retrieval: We evaluate
the mPLUG models pretrained and further finetuned on the COCO-retrieval image-
text dataset without any video pre-training or supervision. Table 9 shows that
zero-shot mPLUG can outperform the SOTA models pretrained on far more
pretraining data (e.g., Florence, BLIP), and can even outperform models
finetuned on the supervised video dataset without using temporal information
(e.g., VideoCLIP, VIOLET); Video Question Answering: Following BLIP [34], We
treat Video QA as an answer generation task and perform evaluation based on
models finetuned on VQA. As shown in Table 10, the zero-shot mPLUG outperforms
BLIP pretrained with more image-text pairs; Video Caption: We use a prefix
prompt _“A video of”_ to improve the quality of decoded captions. Table 10
shows that zero-shot mPLUG also achieves better performance than BLIP.

Model | MSRVTT-QA | MSVD-QA | VATEX-Cap
---|---|---|---
Acc | Acc | CIDEr
_Zero-Shot_
VQA-T [66] | 2.9 | 7.5 | -
BLIP [34] | 19.2 | 35.2 | 37.4
mPLUG | 21.1 | 37.2 | 42.0
Table 10: Zero-shot video-language results on Question-Answer and Caption
tasks.

##  6 Conclusion

This paper presents mPLUG, an effective and efficient VLP framework for both
cross-modal understanding and generation. mPLUG introduces a new asymmetric
vision-language architecture with novel cross-modal skip-connections, to
address two fundamental problems of information asymmetry and computation
efficiency in cross-modal alignment. Pretrained on large-scale image-text
pairs, mPLUG achieves state-of-the-art performance on a wide range of vision-
language tasks. mPLUG also demonstrates strong zero-shot transfer ability when
directly applied to multiple video-language tasks. Our work explores the
cross-modal alignment with a newly-designed VLP architecture and we hope it
can help promote future research on image-text foundation models.

## References

  * Tan and Bansal [2019] Hao Tan and Mohit Bansal. 2019.  Lxmert: Learning cross-modality encoder representations from transformers.  _arXiv preprint arXiv:1908.07490_.
  * Chen et al. [2020] Yen-Chun Chen, Linjie Li, Licheng Yu, Ahmed El Kholy, Faisal Ahmed, Zhe Gan, Yu Cheng, and Jingjing Liu. 2020.  Uniter: Universal image-text representation learning.  In _European conference on computer vision_ , pages 104–120. Springer.
  * Huang et al. [2020] Zhicheng Huang, Zhaoyang Zeng, Bei Liu, Dongmei Fu, and Jianlong Fu. 2020.  Pixel-bert: Aligning image pixels with text by deep multi-modal transformers.  _arXiv preprint arXiv:2004.00849_.
  * Li et al. [2020a] Xiujun Li, Xi Yin, Chunyuan Li, Pengchuan Zhang, Xiaowei Hu, Lei Zhang, Lijuan Wang, Houdong Hu, Li Dong, Furu Wei, et al. 2020a.  Oscar: Object-semantics aligned pre-training for vision-language tasks.  In _European Conference on Computer Vision_ , pages 121–137. Springer.
  * Yu et al. [2021] Fei Yu, Jiji Tang, Weichong Yin, Yu Sun, Hao Tian, Hua Wu, and Haifeng Wang. 2021\.  Ernie-vil: Knowledge enhanced vision-language representations through scene graphs.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pages 3208–3216.
  * Li et al. [2021a] Junnan Li, Ramprasaath Selvaraju, Akhilesh Gotmare, Shafiq Joty, Caiming Xiong, and Steven Chu Hong Hoi. 2021a.  Align before fuse: Vision and language representation learning with momentum distillation.  _Advances in Neural Information Processing Systems_ , 34.
  * Wang et al. [2021a] Zirui Wang, Jiahui Yu, Adams Wei Yu, Zihang Dai, Yulia Tsvetkov, and Yuan Cao. 2021a.  Simvlm: Simple visual language model pretraining with weak supervision.  _CoRR_ , abs/2108.10904.
  * Anderson et al. [2018] Peter Anderson, Xiaodong He, Chris Buehler, Damien Teney, Mark Johnson, Stephen Gould, and Lei Zhang. 2018.  Bottom-up and top-down attention for image captioning and visual question answering.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 6077–6086.
  * Zhang et al. [2021] Pengchuan Zhang, Xiujun Li, Xiaowei Hu, Jianwei Yang, Lei Zhang, Lijuan Wang, Yejin Choi, and Jianfeng Gao. 2021.  Vinvl: Revisiting visual representations in vision-language models.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 5579–5588.
  * Kim et al. [2021] Wonjae Kim, Bokyung Son, and Ildoo Kim. 2021.  Vilt: Vision-and-language transformer without convolution or region supervision.  _arXiv preprint arXiv:2102.03334_.
  * Dou et al. [2021] Zi-Yi Dou, Yichong Xu, Zhe Gan, Jianfeng Wang, Shuohang Wang, Lijuan Wang, Chenguang Zhu, Zicheng Liu, Michael Zeng, et al. 2021.  An empirical study of training end-to-end vision-and-language transformers.  _arXiv preprint arXiv:2111.02387_.
  * Vaswani et al. [2017] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In _Advances in neural information processing systems_ , pages 5998–6008.
  * Li et al. [2019] Liunian Harold Li, Mark Yatskar, Da Yin, Cho-Jui Hsieh, and Kai-Wei Chang. 2019\.  Visualbert: A simple and performant baseline for vision and language.  _arXiv preprint arXiv:1908.03557_.
  * Antol et al. [2015] Stanislaw Antol, Aishwarya Agrawal, Jiasen Lu, Margaret Mitchell, Dhruv Batra, C Lawrence Zitnick, and Devi Parikh. 2015.  Vqa: Visual question answering.  In _Proceedings of the IEEE international conference on computer vision_ , pages 2425–2433.
  * Chen et al. [2015a] Xinlei Chen, Hao Fang, Tsung-Yi Lin, Ramakrishna Vedantam, Saurabh Gupta, Piotr Dollár, and C Lawrence Zitnick. 2015a.  Microsoft coco captions: Data collection and evaluation server.  _arXiv preprint arXiv:1504.00325_.
  * Yu et al. [2016] Licheng Yu, Patrick Poirson, Shan Yang, Alexander C Berg, and Tamara L Berg. 2016\.  Modeling context in referring expressions.  In _European Conference on Computer Vision_ , pages 69–85. Springer.
  * Radford et al. [2021] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. 2021.  Learning transferable visual models from natural language supervision.  _arXiv preprint arXiv:2103.00020_.
  * Jia et al. [2021] Chao Jia, Yinfei Yang, Ye Xia, Yi-Ting Chen, Zarana Parekh, Hieu Pham, Quoc V Le, Yunhsuan Sung, Zhen Li, and Tom Duerig. 2021.  Scaling up visual and vision-language representation learning with noisy text supervision.  _arXiv preprint arXiv:2102.05918_.
  * Xu et al. [2021a] Haiyang Xu, Ming Yan, Chenliang Li, Bin Bi, Songfang Huang, Wenming Xiao, and Fei Huang. 2021a.  E2e-vlp: End-to-end vision-language pre-training enhanced by visual learning.  _arXiv preprint arXiv:2106.01804_.
  * Wang et al. [2021b] Wenhui Wang, Hangbo Bao, Li Dong, and Furu Wei. 2021b.  Vlmo: Unified vision-language pre-training with mixture-of-modality-experts.  _arXiv preprint arXiv:2111.02358_.
  * He et al. [2016] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 770–778.
  * Srivastava et al. [2015] Rupesh Kumar Srivastava, Klaus Greff, and Jürgen Schmidhuber. 2015.  Highway networks.  _arXiv preprint arXiv:1505.00387_.
  * Huang et al. [2017] Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. 2017.  Densely connected convolutional networks.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 4700–4708.
  * Szegedy et al. [2017] Christian Szegedy, Sergey Ioffe, Vincent Vanhoucke, and Alexander A Alemi. 2017\.  Inception-v4, inception-resnet and the impact of residual connections on learning.  In _Thirty-first AAAI conference on artificial intelligence_.
  * Liu et al. [2021] Fenglin Liu, Xuancheng Ren, Zhiyuan Zhang, Xu Sun, and Yuexian Zou. 2021.  Rethinking skip connection with layer normalization in transformers and resnets.  _arXiv preprint arXiv:2105.07205_.
  * Shen et al. [2021] Sheng Shen, Liunian Harold Li, Hao Tan, Mohit Bansal, Anna Rohrbach, Kai-Wei Chang, Zhewei Yao, and Kurt Keutzer. 2021.  How much can clip benefit vision-and-language tasks?  _arXiv preprint arXiv:2107.06383_.
  * Dosovitskiy et al. [2020] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. 2020.  An image is worth 16x16 words: Transformers for image recognition at scale.  In _International Conference on Learning Representations_.
  * He et al. [2020] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. 2020.  Momentum contrast for unsupervised visual representation learning.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 9729–9738.
  * Devlin et al. [2018] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_.
  * Bi et al. [2020] Bin Bi, Chenliang Li, Chen Wu, Ming Yan, Wei Wang, Songfang Huang, Fei Huang, and Luo Si. 2020.  Palm: Pre-training an autoencoding&autoregressive language model for context-conditioned generation.  _arXiv preprint arXiv:2004.07159_.
  * Rajbhandari et al. [2020] Samyam Rajbhandari, Jeff Rasley, Olatunji Ruwase, and Yuxiong He. 2020.  Zero: Memory optimizations toward training trillion parameter models.  In _SC20: International Conference for High Performance Computing, Networking, Storage and Analysis_ , pages 1–16. IEEE.
  * Chen et al. [2016] Tianqi Chen, Bing Xu, Chiyuan Zhang, and Carlos Guestrin. 2016.  Training deep nets with sublinear memory cost.  _arXiv preprint arXiv:1604.06174_.
  * Hu et al. [2021] Xiaowei Hu, Zhe Gan, Jianfeng Wang, Zhengyuan Yang, Zicheng Liu, Yumao Lu, and Lijuan Wang. 2021.  Scaling up vision-language pre-training for image captioning.  _CoRR_ , abs/2111.12233.
  * Li et al. [2022] Junnan Li, Dongxu Li, Caiming Xiong, and Steven Hoi. 2022.  Blip: Bootstrapping language-image pre-training for unified vision-language understanding and generation.  _arXiv preprint arXiv:2201.12086_.
  * Wang et al. [2022] Peng Wang, An Yang, Rui Men, Junyang Lin, Shuai Bai, Zhikang Li, Jianxin Ma, Chang Zhou, Jingren Zhou, and Hongxia Yang. 2022.  Unifying architectures, tasks, and modalities through a simple sequence-to-sequence learning framework.  _arXiv preprint arXiv:2202.03052_.
  * Lin et al. [2014] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick. 2014.  Microsoft coco: Common objects in context.  In _European conference on computer vision_ , pages 740–755. Springer.
  * Krishna et al. [2017] Ranjay Krishna, Yuke Zhu, Oliver Groth, Justin Johnson, Kenji Hata, Joshua Kravitz, Stephanie Chen, Yannis Kalantidis, Li-Jia Li, David A Shamma, et al. 2017\.  Visual genome: Connecting language and vision using crowdsourced dense image annotations.  _International journal of computer vision_ , 123(1):32–73.
  * Sharma et al. [2018] Piyush Sharma, Nan Ding, Sebastian Goodman, and Radu Soricut. 2018.  Conceptual captions: A cleaned, hypernymed, image alt-text dataset for automatic image captioning.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 2556–2565.
  * Changpinyo et al. [2021] Soravit Changpinyo, Piyush Sharma, Nan Ding, and Radu Soricut. 2021.  Conceptual 12m: Pushing web-scale image-text pre-training to recognize long-tail visual concepts.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 3558–3568.
  * Ordonez et al. [2011] Vicente Ordonez, Girish Kulkarni, and Tamara L Berg. 2011.  Im2text: Describing images using 1 million captioned photographs.  In _Advances in neural information processing systems_ , pages 1143–1151.
  * Loshchilov and Hutter [2017] Ilya Loshchilov and Frank Hutter. 2017.  Decoupled weight decay regularization.  _arXiv preprint arXiv:1711.05101_.
  * Cubuk et al. [2020] Ekin D Cubuk, Barret Zoph, Jonathon Shlens, and Quoc V Le. 2020.  Randaugment: Practical automated data augmentation with a reduced search space.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops_ , pages 702–703.
  * Lu et al. [2019] Jiasen Lu, Dhruv Batra, Devi Parikh, and Stefan Lee. 2019.  Vilbert: Pretraining task-agnostic visiolinguistic representations for vision-and-language tasks.  In _Advances in Neural Information Processing Systems_ , pages 13–23.
  * Cho et al. [2021] Jaemin Cho, Jie Lei, Hao Tan, and Mohit Bansal. 2021.  Unifying vision-and-language tasks via text generation.  In _Proceedings of the 38th International Conference on Machine Learning_ , volume 139 of _Proceedings of Machine Learning Research_ , pages 1931–1942. PMLR.
  * Yuan et al. [2021] Lu Yuan, Dongdong Chen, Yi-Ling Chen, Noel Codella, Xiyang Dai, Jianfeng Gao, Houdong Hu, Xuedong Huang, Boxin Li, Chunyuan Li, et al. 2021.  Florence: A new foundation model for computer vision.  _arXiv preprint arXiv:2111.11432_.
  * Li et al. [2020b] Wei Li, Can Gao, Guocheng Niu, Xinyan Xiao, Hao Liu, Jiachen Liu, Hua Wu, and Haifeng Wang. 2020b.  Unimo: Towards unified-modal understanding and generation via cross-modal contrastive learning.  _arXiv preprint arXiv:2012.15409_.
  * Chen et al. [2015b] Xinlei Chen, Hao Fang, Tsung-Yi Lin, Ramakrishna Vedantam, Saurabh Gupta, Piotr Dollár, and C. Lawrence Zitnick. 2015b.  Microsoft COCO captions: Data collection and evaluation server.  _CoRR_ , abs/1504.00325.
  * Agrawal et al. [2018] Harsh Agrawal, Karan Desai, Yufei Wang, Xinlei Chen, Rishabh Jain, Mark Johnson, Dhruv Batra, Devi Parikh, Stefan Lee, and Peter Anderson. 2018.  nocaps: novel object captioning at scale.  _CoRR_ , abs/1812.08658.
  * Rennie et al. [2017] Steven J. Rennie, Etienne Marcheret, Youssef Mroueh, Jerret Ross, and Vaibhava Goel. 2017.  Self-critical sequence training for image captioning.  In _2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 1179–1195.
  * Gan et al. [2020] Zhe Gan, Yen-Chun Chen, Linjie Li, Chen Zhu, Yu Cheng, and Jingjing Liu. 2020\.  Large-scale adversarial training for vision-and-language representation learning.  In _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_.
  * Kamath et al. [2021] Aishwarya Kamath, Mannat Singh, Yann LeCun, Gabriel Synnaeve, Ishan Misra, and Nicolas Carion. 2021.  MDETR - modulated detection for end-to-end multi-modal understanding.  In _2021 IEEE/CVF International Conference on Computer Vision, ICCV 2021, Montreal, QC, Canada, October 10-17, 2021_ , pages 1760–1770. IEEE.
  * Yang et al. [2021a] Zhengyuan Yang, Zhe Gan, Jianfeng Wang, Xiaowei Hu, Faisal Ahmed, Zicheng Liu, Yumao Lu, and Lijuan Wang. 2021a.  Crossing the format boundary of text and boxes: Towards unified vision-language modeling.  _CoRR_ , abs/2111.12085.
  * Plummer et al. [2015] Bryan A Plummer, Liwei Wang, Chris M Cervantes, Juan C Caicedo, Julia Hockenmaier, and Svetlana Lazebnik. 2015.  Flickr30k entities: Collecting region-to-phrase correspondences for richer image-to-sentence models.  In _Proceedings of the IEEE international conference on computer vision_ , pages 2641–2649.
  * Suhr et al. [2018] Alane Suhr, Stephanie Zhou, Ally Zhang, Iris Zhang, Huajun Bai, and Yoav Artzi. 2018\.  A corpus for reasoning about natural language grounded in photographs.  _arXiv preprint arXiv:1811.00491_.
  * Xie et al. [2019] Ning Xie, Farley Lai, Derek Doran, and Asim Kadav. 2019.  Visual entailment: A novel task for fine-grained image understanding.  _CoRR_ , abs/1901.06706.
  * Yao et al. [2021] Lewei Yao, Runhui Huang, Lu Hou, Guansong Lu, Minzhe Niu, Hang Xu, Xiaodan Liang, Zhenguo Li, Xin Jiang, and Chunjing Xu. 2021.  Filip: Fine-grained interactive language-image pre-training.  _arXiv preprint arXiv:2111.07783_.
  * Miech et al. [2020] Antoine Miech, Jean-Baptiste Alayrac, Lucas Smaira, Ivan Laptev, Josef Sivic, and Andrew Zisserman. 2020.  End-to-end learning of visual representations from uncurated instructional videos.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 9879–9889.
  * Xu et al. [2021b] Hu Xu, Gargi Ghosh, Po-Yao Huang, Dmytro Okhonko, Armen Aghajanyan, Florian Metze, Luke Zettlemoyer, and Christoph Feichtenhofer. 2021b.  Videoclip: Contrastive pre-training for zero-shot video-text understanding.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 6787–6800.
  * Akbari et al. [2021] Hassan Akbari, Liangzhe Yuan, Rui Qian, Wei-Hong Chuang, Shih-Fu Chang, Yin Cui, and Boqing Gong. 2021.  Vatt: Transformers for multimodal self-supervised learning from raw video, audio and text.  _Advances in Neural Information Processing Systems_ , 34.
  * Li et al. [2021b] Dongxu Li, Junnan Li, Hongdong Li, Juan Carlos Niebles, and Steven CH Hoi. 2021b.  Align and prompt: Video-and-language pre-training with entity prompts.  _arXiv preprint arXiv:2112.09583_.
  * Fu et al. [2021] Tsu-Jui Fu, Linjie Li, Zhe Gan, Kevin Lin, William Yang Wang, Lijuan Wang, and Zicheng Liu. 2021.  Violet: End-to-end video-language transformers with masked visual-token modeling.  _arXiv preprint arXiv:2111.12681_.
  * Miech et al. [2019] Antoine Miech, Dimitri Zhukov, Jean-Baptiste Alayrac, Makarand Tapaswi, Ivan Laptev, and Josef Sivic. 2019.  Howto100m: Learning a text-video embedding by watching hundred million narrated video clips.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 2630–2640.
  * Bain et al. [2021] Max Bain, Arsha Nagrani, Gül Varol, and Andrew Zisserman. 2021.  Frozen in time: A joint video and image encoder for end-to-end retrieval.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 1728–1738.
  * Zellers et al. [2021] Rowan Zellers, Ximing Lu, Jack Hessel, Youngjae Yu, Jae Sung Park, Jize Cao, Ali Farhadi, and Yejin Choi. 2021.  Merlot: Multimodal neural script knowledge models.  _Advances in Neural Information Processing Systems_ , 34.
  * Gemmeke et al. [2017] Jort F Gemmeke, Daniel PW Ellis, Dylan Freedman, Aren Jansen, Wade Lawrence, R Channing Moore, Manoj Plakal, and Marvin Ritter. 2017.  Audio set: An ontology and human-labeled dataset for audio events.  In _2017 IEEE international conference on acoustics, speech and signal processing (ICASSP)_ , pages 776–780. IEEE.
  * Yang et al. [2021b] Antoine Yang, Antoine Miech, Josef Sivic, Ivan Laptev, and Cordelia Schmid. 2021b.  Just ask: Learning to answer questions from millions of narrated videos.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 1686–1697.
  * Goyal et al. [2017] Yash Goyal, Tejas Khot, Douglas Summers-Stay, Dhruv Batra, and Devi Parikh. 2017\.  Making the v in vqa matter: Elevating the role of image understanding in visual question answering.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 6904–6913.
  * Karpathy and Fei-Fei [2015] Andrej Karpathy and Li Fei-Fei. 2015.  Deep visual-semantic alignments for generating image descriptions.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 3128–3137.
  * Mao et al. [2016] Junhua Mao, Jonathan Huang, Alexander Toshev, Oana Camburu, Alan L Yuille, and Kevin Murphy. 2016.  Generation and comprehension of unambiguous object descriptions.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 11–20.

##  7 More Experiments Details

###  7.1 Downstream Task Details

We evaluate mPLUG on the six downstream vision-language tasks. The
hyperparameters that we use for finetuning on the downstream tasks are listed
in Table 11. Following [6], all tasks adopt RandAugment, AdamW optimizer with
a weight decay of 0.05 and a cosine learning rate schedule. We use an image
resolution of 336 $\times$ 336, except for VQA where we use 504 $\times$ 504
images. For VQA and image captioning tasks, we also do an additional continue
pre-training on 4M image-text pairs, which can bring about 0.2+ accuracy
improvement. Next we introduce the dataset settings in detail.

##### VQA.

We conduct experiment on the VQA2.0 dataset [67], which contains 83k/41k/81k
images for training/validation/test. Following [6], we use both training and
validation splits for training, and incorporate additional training data from
Visual Genome [37].

Task | LR (ViT-L/BERTbase) | batch size | epochs
---|---|---|---
VQA | 2e-5/5e-6 | 1024 | 8
Captioning$\dagger$ | 1e-5&8e-7 | 256 | 5
Retrieval | 1e-5/2e-6 | 256 | 5
Visual Grounding | 2e-5/2e-6 | 512 | 120
NLVR2 | 5e-5/5e-6 | 256 | 15
SNLI-VE | 2e-5 | 64 | 5
Table 11: Finetuning hyperparameters for downstream tasks. $\dagger$ denotes
two stages fine-tuning.

##### Image Captioning.

We finetune on COCO’s Karpathy train split, and evaluate on COCO’s Karpathy
test split and No-Caps validation split. Following [4, 35], we first fine-tune
mPLUG with cross-entropy loss for 5 epochs with a learning rate of 1e-5 and a
batch size of 256. Based on the fine-tuned model, we the fine-tune it with
CIDEr optimization [49] for extra 5 epochs with a smaller learning rate of
8e-7. During inference, we use beam search with a beam size of 10, and set the
maximum generation length as 20.

##### Image-Text Retrieval.

We adopt the widely-used Karpathy split [68] for both COCO and Flickr30K. COCO
contains 113/5k/5k images for train/validation/test, and Flickr30K contains
29k/1k/1k images for train/validation/test.

##### Visual Grounding.

We evaluate our method on three referring expression grounding datasets:
RefCOCO, RefCOCO+ [16] and RefCOCOg [69]. The RefCOCO and RefCOCO+ datasets
share 19K images and contain 142/141K queries. The RefCOCOg dataset contains
25K images and 95K queries. To fully use training data, we first train the
model with a mixed dataset with a learning rate of 2e-5. Then we continue
fine-tuning the model on each dataset with a learning rate of 2e-6.

##### NLVR2 & SNLI-VE.

We conduct experiment both on the official split [54, 55].

###  7.2 Pre-training Dataset Details

Table 12 shows the statistics of the 14M pre-training images with texts.

| COCO | VG | SBU | CC3M | CC12M
---|---|---|---|---|---
image | 113K | 100K | 860K | 3M | 10M
text | 567K | 769K | 860K | 3M | 10M
Table 12: Statistics of the pre-training datasets.