Introduction to the McPherson number, $\Upsilon(G)$ of a simple connected
graph

(Johan Kok, Susanth C)111Affiliation of author(s):
Johan Kok (Tshwane Metropolitan Police Department), City of Tshwane, Republic
of South Africa
e-mail<EMAIL_ADDRESS>

Susanth C (Department of Mathematics, Vidya Academy of Science and
Technology), Thalakkottukara, Thrissur-680501, Republic of India
e-mail<EMAIL_ADDRESS>
###### Abstract

The concept of the _McPherson number_ of a simple connected graph $G$ on $n$
vertices denoted by $\Upsilon(G),$ is introduced. The recursive concept,
called the _McPherson recursion_ , is a series of _vertex explosions_ such
that on the first iteration a vertex $v\in V(G)$ explodes to arc (directed
edges) to all vertices $u\in V(G)$ for which the edge $vu\notin E(G),$ to
obtain the mixed graph $G^{\prime}_{1}.$ Now $G^{\prime}_{1}$ is considered on
the second iteration and a vertex $w\in V(G^{\prime}_{1})=V(G)$ may explode to
arc to all vertices $z\in V(G^{\prime}_{1})$ if edge $wz\notin E(G)$ and arc
$(w,z)$ or $(z,w)\notin E(G^{\prime}_{1}).$ The _McPherson number_ of a simple
connected graph $G$ is the minimum number of iterative vertex explosions say
$\ell$, to obtain the mixed graph $G^{\prime}_{\ell}$ such that the underlying
graph of $G^{\prime}_{\ell}$ denoted $G^{*}_{\ell}$ has $G^{*}_{\ell}\simeq
K_{n}.$ We determine the _McPherson number_ for paths, cycles and $n$-partite
graphs. We also determine the _McPherson number_ of the finite Jaco Graph
$J_{n}(1),n\in\mathbb{N}.$ It is hoped that this paper will encourage further
exploratory research.

Keywords: McPherson number, McPherson recursion, McPherson discrepancy,
McPherson stability, Jaco graph.

AMS Classification Numbers: 05C07, 05C20, 05C38, 05C75, 05C85

##  1 Introduction

The concept of the _McPherson number_ of a simple connected graph $G$ on $n$
vertices denoted by $\Upsilon(G),$ is introduced. The recursive concept,
called the _McPherson recursion_ , is a series of _vertex explosions_ such
that on the first iteration a vertex $v\in V(G)$ explodes to arc (directed
edges) to all vertices $u\in V(G)$ for which the edge $vu\notin E(G),$ to
obtain the mixed graph $G^{\prime}_{1}.$ Now $G^{\prime}_{1}$ is considered on
the second iteration and a vertex $w\in V(G^{\prime}_{1})=V(G)$ may explode to
arc to all vertices $z\in V(G^{\prime}_{1})$ if edge $wz\notin E(G)$ and arc
$(w,z)$ or $(z,w)\notin E(G^{\prime}_{1}).$ The _McPherson number_ of a simple
connected graph $G$ is the minimum number of iterative vertex explosions say
$\ell$, to obtain the mixed graph $G^{\prime}_{\ell}$ such that the underlying
graph $G^{*}_{\ell}\simeq K_{n}.$ Note that $G=G^{*}_{0}.$

It is easy to see that the total number of arcs created is
$\epsilon(K_{n})-\epsilon(G).$ It is equally easy to see that
$\Upsilon(K_{n})=0$ and $\Upsilon(K_{n}-uv)_{uv\in E(K_{n})}=1.$ It is not
that easy to see that the sequence of vertex explosions does not generally
obey the commutative law. This will be illustrated by way of an example.

Example 1. Let $G$ be the simple connected graph with
$V(G)=\\{v_{1},v_{2},v_{3},v_{4},v_{5},v_{6}\\}$ and
$E(G)=\\{v_{1}v_{2},v_{1}v_{3},v_{1}v_{4},v_{1}v_{5},v_{2}v_{5},v_{2}v_{6},v_{3}v_{4},v_{3}v_{5}\\}.$

On the first iteration let vertex $v_{6}$ explode to create the arcs
$(v_{6},v_{1}),(v_{6},v_{3}),(v_{6},v_{4}),(v_{6},v_{5}).$ On the second
iteration let $v_{2}\in V(G^{\prime}_{1})$ explode to create arcs
$(v_{2},v_{3}),(v_{2},v_{4}).$ Finally let $v_{4}\in V(G^{\prime}_{2})$
explode to create arc $(v_{4},v_{5}).$ After validating all permutated
sequences of vertex explosions we conclude that, since three explosions are
the minimum needed to ensure that the underlying graph $G^{*}_{3}\simeq
K_{6}$, it follows that $\Upsilon(G)=3.$

However, if vertex $v_{1}\in V(G)$ explodes first, the arc $(v_{1},v_{6})$ is
created. If secondly, the vertex $v_{3}\in V(G^{\prime}_{1})$ explodes the
arcs $(v_{3},v_{2})$ and $(v_{3},v_{6})$ are created. Followed by the next
iteration let $v_{2}\in V(G^{\prime}_{2})$ explode to create arc
$(v_{2},v_{4})$ followed by the explosion of vertex $v_{5}\in
V(G^{\prime}_{3})$ to create arcs $(v_{5},v_{4}),(v_{5},v_{6}).$ The final
vertex explosion is that of vertex $v_{4}$ to create the arc $(v_{4},v_{6})$.
Now only is the underlying graph $G^{*}_{5}\simeq K_{6}.$ Since, minimality is
defined we see that the sequence of explosions does not generally obey the
commutative law.222Whilst listening to an amasing djembe drumming group from
Ghana on Friday, 10 October 2014, celebrating the $15^{th}$ anniversary of
Klitsgras Drumming Circle, the concept of McPherson numbers struck Kokkie’s
mind. Thank you to them. It reminds us there are mathematics in music and vice
versa.

##  2 McPherson numbers of Jaco Graphs, Paths, Cycles and n-Partite Graphs

Before we consider specialised graphs we will endeavour to find the optimal
algorithm to calculate the McPherson number, $\Upsilon(G)$ of a simple
connected graph $G$. The _McPherson recursion_ described in Lemma 2.2 below is
sufficient.

######  Lemma 2.1.

The McPherson number of a simple connected graph $G$ on n vertices is
$\Upsilon(G)\leq\epsilon(K_{n})-\epsilon(G).$

###### Proof.

Consider any complete graph $K_{n},n\in\mathbb{N}.$ Without loss of generality
let $n$ be even and let
$G=K_{n}-(v_{1}v_{2},v_{3}v_{4},v_{5}v_{6},...,v_{n-1}v_{n}).$ Clearly
$\epsilon(K_{n})-\epsilon(G)=\frac{n}{2}.$ For any vertex $v_{i}$ eligible to
explode only one arc, either $(v_{i},v_{i+1})$ or $(v_{i},v_{i-1})$ is added.
Hence exactly $\frac{n}{2}$ vertex explosions are required to have
$G^{*}_{\frac{n}{2}}\simeq K_{n}.$ Therefore,
$\Upsilon(G)=\frac{n}{2}=\epsilon(K_{n})-\epsilon(G).$ For all other simple
connected graphs on $n$ vertices, $\Upsilon(G)\leq\epsilon(K_{n})-\epsilon(G)$
since vertex explosions are defined to be _greedy_ and on each iteration
always arcs to the maximum number of non-adjacent vertices in $G^{*}_{i}$ on
the $(i+1)^{th}$-iteration. ∎

######  Lemma 2.2.

The McPherson number of a simple connected graph $G$ on $n$ vertices is
obtained through the McPherson recursion. Let any vertex with degree equal to
$\delta(G)$ explode on the first iteration. This is followed by letting any
vertex in the underlying graph $G^{*}_{1}$ of $G^{\prime}_{1}$ with degree
equal to $\delta(G^{*}_{1})$ explode on the second iteration to obtain
$G^{\prime}_{2}$ and, so on. If after exactly $\ell$ vertex explosions the
underlying graph $G^{*}_{\ell}\simeq K_{n}$ then, $\Upsilon(G)=\ell.$

###### Proof.

Consider any simple connected graph $G$ on $n$ vertices. Apply the _McPherson
recursion_ and assume after exactly $\ell$ vertex explosions the underlying
graph $G^{*}_{\ell}\simeq K_{n}.$ Label the vertices which exploded
consecutively $v_{1},v_{2},v_{3},...,v_{\ell}.$ The total number of edges
added in $G^{*}_{\ell}$ (total number of arcs added during the $\ell$ vertex
explosions) is given by:

$\epsilon(K_{n})-\epsilon(G)=d_{G^{*}_{0}}^{+}(v_{1})+d_{G^{*}_{1}}^{+}(v_{2})+d_{G^{*}_{2}}^{+}(v_{3})+...+d_{G^{*}_{\ell}}^{+}(v_{\ell-1}).$

Now assume that for any vertex $v_{i}$ a vertex
$v_{j},d_{G^{*}_{i-1}}(v_{j})>d_{G^{*}_{i-1}}(v_{i})$ exploded instead. Then
it follows that:

$t=d_{G^{*}_{0}}^{+}(v_{1})+d_{G^{*}_{1}}^{+}(v_{2})+d_{G^{*}_{2}}^{+}(v_{3})+...+d_{G^{*}_{i-1}}^{+}(v_{j})+...+d_{G^{*}_{\ell}}^{+}(v_{\ell-1})<d_{G^{*}_{0}}^{+}(v_{1})+d_{G^{*}_{1}}^{+}(v_{2})+d_{G^{*}_{2}}^{+}(v_{3})+...+d_{G^{*}_{i-1}}^{+}(v_{i})+...+d_{G^{*}_{\ell}}^{+}(v_{\ell-1})=\epsilon(K_{n})-\epsilon(G).$

It means at least one more vertex explosion is needed to finally add the
additional $(\epsilon(K_{n})-\epsilon(G))-t$ arcs required to obtain
$G^{*}_{\ell+}\simeq K_{n}.$ The latter is a contradiction in respect of
minimality as defined. Hence the _McPherson recursion_ is well-defined and
$\Upsilon(G)=\ell.$ ∎

###  2.1 The McPherson number of Jaco Graphs $J_{n}(1),n\in\mathbb{N}.$

The infinite directed Jaco graph (_order 1_) was introduced in $[3],$ and
defined by $V(J_{\infty}(1))=\\{v_{i}|i\in\mathbb{N}\\}$,
$E(J_{\infty}(1))\subseteq\\{(v_{i},v_{j})|i,j\in\mathbb{N},i<j\\}$ and
$(v_{i},v_{j})\in E(J_{\infty}(1))$ if and only if $2i-d^{-}(v_{i})\geq j.$
The graph has four fundamental properties which are;
$V(J_{\infty}(1))=\\{v_{i}|i\in\mathbb{N}\\}$ and, if $v_{j}$ is the head of
an edge (arc) then the tail is always a vertex $v_{i},i<j$ and, if $v_{k},$
for smallest $k\in\mathbb{N}$ is a tail vertex then all vertices
$v_{\ell},k<\ell<j$ are tails of arcs to $v_{j}$ and finally, the degree of
vertex $k$ is $d(v_{k})=k.$ The family of finite directed graphs are those
limited to $n\in\mathbb{N}$ vertices by lobbing off all vertices (and edges
arcing to vertices) $v_{t},t>n.$ Hence, trivially we have $d(v_{i})\leq i$ for
$i\in\mathbb{N}.$

Note that the _McPherson recursion_ can naturally be extended to directed
graphs. For the Jaco graph $J_{n}(1),n\in\mathbb{N},n\geq 3$ it easily follows
that if the lowest indiced vertex $v_{i}$ for which the edge $v_{i}v_{n}$
exists is found, then $\Upsilon(J_{n}(1))=i-1$. The next theorem presents a
stepwise closed formula for $\Upsilon(J_{n}(1)),n\in\mathbb{N},n\geq 3.$

######  Theorem 2.3.

Consider the Jaco graph $J_{n}(1),n\in\mathbb{N},n\geq 3.$ If $v_{i}$ is the
prime Jaconian vertex we have:

$\Upsilon(J_{n}(1))\begin{cases}=i,&\text{if the edge $v_{i}v_{n}\notin
E(J_{n}(1)$,}\\\ \\\ =i-1,&\text{otherwise.}\end{cases}$

###### Proof.

(a) If the edge $v_{i}v_{n}$ exists the largest complete subgraph of
$J_{n}(1)$ is given by $\mathbb{H}_{n}(1)+v_{i}\simeq K_{(n-i)+1},[3].$ From
the definition of a Jaco Graph it follows that vertices
$v_{1},v_{2},v_{3},...,v_{i-1}$ are non-adjacent to at least vertex $v_{n}.$
So exactly $i-1$ vertex explosions are required to obtain
$J^{*}_{n,(i-1)}\simeq K_{n}.$ Hence, $\Upsilon(J_{n}(1))=i-1.$

(b) If the edge $v_{i}v_{n}\notin E(J_{n}(1))$ then the Hope graph [3], is the
largest complete subgraph of $J_{n}(1).$ From the definition of a Jaco graph
it follows that vertices $v_{1},v_{2},v_{3},...,v_{i}$ are non-adjacent to at
least vertex $v_{n}.$ So exactly $i$ vertex explosions are required to obtain
$J^{*}_{n,i}\simeq K_{n}.$ Hence, $\Upsilon(J_{n}(1))=i.$ ∎

Table 1 shows the $\Upsilon$-values for $J_{n}(1),3\leq n\leq 15.$ The table
can easily be verified and extended by using the Fisher Algorithm [3]. Note
that the Fisher Algorithm determines $d^{+}(v_{i})$ on the assumption that the
Jaco Graph is always sufficiently large, so at least $J_{n}(1),n\geq
i+d^{+}(v_{i}).$ For a smaller graph the degree of vertex $v_{i}$ is given by
$d(v_{i})_{J_{n}(1)}=d^{-}(v_{i})+(n-i).$ In [3] Bettina’s theorem describes
an arguably, closed formula to determine $d^{+}(v_{i})$. Since
$d^{-}(v_{i})=n-d^{+}(v_{i})$ it is then easy to determine
$d(v_{i})_{J_{n}(1)}$ in a smaller graph $J_{n}(1),n<i+d^{+}(v_{i}).$

Table 1

$i\in{\mathbb{N}}$ $d^{-}(v_{i})$ $d^{+}(v_{i})$ Prime Jaconian vertex,$v_{j}$
$\Upsilon(J_{i}(1))$ 3 1 2 $v_{2}$ 1 4 1 3 $v_{2}$ 2 5 2 3 $v_{3}$ 2 6 2 4
$v_{3}$ 3 7 3 4 $v_{4}$ 3 8 3 5 $v_{5}$ 4 9 3 6 $v_{5}$ 5 10 4 6 $v_{6}$ 5 11
4 7 $v_{7}$ 6 12 4 8 $v_{7}$ 7 13 5 8 $v_{8}$ 7 14 5 9 $v_{8}$ 8 15 6 9
$v_{9}$ 8

Conjecture: For a Jaco Graph $J_{n}(1),n\in\mathbb{N},n\geq 3$ we have that
$d^{+}(v_{n})$ is unique (_non-repetitive_) if and only if
$\Upsilon(J_{n}(1))$ is unique (_non-repetitive_).

###  2.2 McPherson number of Paths, $P_{n},n\in\mathbb{N}$

######  Proposition 2.4.

The McPherson number of a path $P_{n},n\geq 3$ is given by
$\Upsilon(P_{n})=n-2.$

###### Proof.

Consider any path $P_{n},n\in\mathbb{N}$ and label the vertices from left to
right, $v_{1},v_{2},v_{3},...,v_{n}.$ Clearly
$d(v_{1})=d(v_{n})=\delta(P_{n}).$ So, without loss of generality let vertex
$v_{1}$ explode on the first iteration. The arcs
$(v_{1},v_{3}),(v_{1},v_{4}),(v_{1},v_{5}),...,(v_{1},v_{n})$ are added. In
the graph $P^{\prime}_{n,1}$ we have that
$d(v_{2})=d(v_{n})=2=\delta(P^{*}_{n,1}).$ Without loss of generality let
vertex $v_{2}$ explode in the second iteration. Now arcs
$(v_{2},v_{4}),(v_{2},v_{5}),...,(v_{2},v_{n})$ are added. Recursively, all
vertices $v_{3},v_{4},v_{5},...,v_{n-2}$ must explode to have
$P^{*}_{n,(n-2)}\simeq K_{n}.$

Clearly the number of explosions are a minimum to ensure
$P^{*}_{n,(n-2)}\simeq K_{n}$ so we have,
$\Upsilon(P_{n})=n-2.$ ∎

###  2.3 McPherson number of Cycles, $C_{n},n\in\mathbb{N}$

We begin this subsection with an interesting lemma.

######  Lemma 2.5.

Consider two simple connected graphs $G$ and $H$ with $G\neq H.$ If after
minimum recursive explosions, say $t$ explosions in respect of vertices $v\in
V(G)$, we have that $G^{*}_{t}\simeq H,$ then $\Upsilon(G)=\Upsilon(H)+t.$

###### Proof.

Vertex explosions as defined, only add _arcs_. So the mere fact that after the
minimum $t$ explosions of $t$ vertices of $G$ we have that $G^{*}_{t}\simeq H$
implies that $\nu(G)=\nu(H).$ The definition of the McPherson number is well-
defined [see Lemma 2.2], so for all graphs $G$ and $H$ each on $n$ vertices,
if $G\simeq H$ then $\Upsilon(G)=\Upsilon(H).$

From the _McPherson recursion_ it follows that
$\Upsilon(G)=\Upsilon(G^{*}_{t})+t=\Upsilon(H)+t.$ ∎

######  Proposition 2.6.

The McPherson number of a cycle $C_{n},n\geq 4$ is given by
$\Upsilon(C_{n})=n-2.$

###### Proof.

Consider any path $P_{n}$ and the cycle $C_{n}$. Label the vertices of the
path from left to right, $v_{1},v_{2},v_{3},...,v_{n}$ and the vertices of the
cycle clockwise, $v_{1},v_{2},v_{3},...,v_{n}.$ Without loss of generality let
vertex $v_{1}$ of both the path and the cycle explode on the first interation.
It follows that $P^{\prime}_{n,1}$ has amongst others, the arc $(v_{1},v_{n})$
whilst $C^{\prime}_{n,1}$ has amongst others, the edge $v_{1}v_{n}.$ So it
follows that $P^{*}_{n,1}\simeq C^{*}_{n,1}.$

Hence, the result
$\Upsilon(P_{n})=\Upsilon(P^{*}_{n,1})+1=\Upsilon(C^{*}_{n,1})+1=\Upsilon(C_{n})$
holds true. Therefore $\Upsilon(C_{n})=n-2.$ ∎

###  2.4 McPherson number of n-Partite graphs,
$K_{(n_{1},n_{2},...,n_{\ell})},n_{i,\forall i}\in\mathbb{N}$

We recall that the sequence of vertex explosions do not generally obey the
commutative law. However, $n$-partite graphs are a class of graphs which does
obey the commutative law. It follows because the vertices of
$K_{(n_{1},n_{2},...,n_{\ell})},n_{i,\forall i}\in\mathbb{N}$ can be partioned
in $\ell$ subsets of _pairwise non-adjacent_ vertices. Although we mainly
consider simple connected graphs, we will as a special case consider the
following lemma for the _edgeless_ graph on $n$ vertices which we call the
$n$-Null graph, denoted $\aleph_{n}$. It is important to note that
$\aleph_{n}=\cup_{n-times}K_{1}.$ The importance lies in the fact that if we
determine the _McPherson number_ of $\cup_{\forall i}G_{i}$ the explosion of a
vertex $v_{j}\in V(G_{k})$ will arc to all vertices $v_{s}\in V(G_{k})$, non-
adjacent to $v_{j}$ as well as, arc to all vertices $v_{t}\in V(G_{m})$ for
all $m\neq k$.

######  Lemma 2.7.

For any $n$-Null graph, $n\in\mathbb{N}$ we have that:

(a) The vertex explosion sequence obeys the commutative law,
(b) The McPherson number is given by $\Upsilon(\aleph_{n})=n-1.$

###### Proof.

(a) Consider any $n$-Null graph, $n\in\mathbb{N}.$ Clearly the $n$ vertices
can randomly be labelled $v_{1},v_{2},v_{3},...,v_{n}$ in $n!$ ways. Label
these $n!$ _vertex labelled_ $n$-Null graphs,
$\aleph_{(n,1)},\aleph_{(n,2)},\aleph_{(n,3)},...,\aleph_{(n,n!)}.$ Clearly,
$\aleph_{(n,1)}\simeq\aleph_{(n,2)}\simeq\aleph_{(n,3)}\simeq...\simeq\aleph_{(n,n!)}.$
The different random labelling represents the random (commutative law) vertex
explosions and from Lemma 2.2 it follows that
$\Upsilon(\aleph_{(n,1)})=\Upsilon(\aleph_{(n,2)})=\Upsilon(\aleph_{(n,3)})=...=\Upsilon(\aleph_{(n,n!)}).$

(b) Consider anyone of the $n!$ _vertex labelled_ $n$-Null graphs say,
$\aleph_{(n,i)}.$ Let vertex $v_{1}$ explode on the first iteration to add
arcs $(v_{1},v_{2}),(v_{1},v_{3}),...,(v_{1},v_{n}).$ Then let vertex $v_{2}$
explode on the second iteration to add arcs
$(v_{2},v_{3}),(v_{2},v_{4}),...,(v_{2},v_{n}).$ Clearly on the _$i^{th}$_
-iteration the arcs $(v_{i},v_{i+1}),(v_{i},v_{i+2}),...,(v_{i},v_{n})$ are
added. It implies that on the _$(n-1)^{th}$_ -iteration the last arc
$(v_{n-1},v_{n})$ is added, to obtain $\aleph^{*}_{(n,i),(n-1)}\simeq K_{n}.$
Since the number of vertex explosions are a minimum we conclude that
$\Upsilon(\aleph_{(n,i)})=n-1.$ Following from part (a) we have that
$\Upsilon(\aleph_{n})=n-1$ in general. ∎

######  Proposition 2.8.

For the n-Partite graphs, $K_{(n_{1},n_{2},...,n_{\ell})},n_{i,\forall
i}\in\mathbb{N}$ we have that
$\Upsilon(K_{(n_{1},n_{2},...,n_{\ell})})=\sum\limits^{\ell}_{i=1}n_{i}-\ell.$

###### Proof.

In the graph $G\uplus H$ we restrict the explosion of vertex, $v_{i}\in V(G)$
to arc to non-adjacent vertices $v_{j}\in V(G)$ and the arcing of the
explosion of vertex $u_{i}\in V(H)$ to non-adjacent vertices $u_{j}\in V(H).$
Clearly $\Upsilon(G\uplus H)=\Upsilon(G)+\Upsilon(H)=\Upsilon(H)+\Upsilon(G).$

Now label the $n_{1}$ vertices, $v_{1,1},v_{1,2},v_{1,3},...,v_{1,n_{1}},$ and
label the $n_{2}$ vertices, $v_{2,1},v_{2,2},v_{2,3},...,v_{2,n_{2}}$ and so
on, and finally label the $n_{\ell}$ vertices,
$v_{\ell,1},v_{\ell,2},v_{\ell,3},...,v_{\ell,\ell}.$ In the $n$-partite graph
we have that the edge $v_{i,j}v_{k,m}$ exists for $1\leq i,j\leq\ell,1\leq
j\leq n_{i},1\leq m\leq n_{k}$ and $i\neq j.$ It implies that
$\Upsilon(K_{(n_{1},n_{2},...,n_{\ell})})=\Upsilon(\aleph_{n_{1}}\uplus\aleph_{n_{2}}\uplus\aleph_{n_{3}}\uplus...\uplus\aleph_{n_{\ell}}).$

Now we have that
$\Upsilon(\aleph_{n_{1}}\uplus\aleph_{n_{2}}\uplus\aleph_{n_{3}}\uplus...\uplus\aleph_{n_{\ell}})=\Upsilon(\aleph_{n_{1}})+\Upsilon(\aleph_{n_{2}})+\Upsilon(\aleph_{n_{3}})+...+\Upsilon(\aleph_{n_{\ell}})=(n_{1}-1)+(n_{2}-1)+(n_{3}-1)+...+(n_{\ell}-1)=\sum\limits^{\ell}_{i=1}n_{i}-\ell.$
∎

We note from the proof above that the _McPherson recursion_ could be relax in
the sense that it applies to each $\aleph_{i}$ but not to
$K_{(n_{1},n_{2},...,n_{\ell})},n_{i,\forall i}\in\mathbb{N}$ as a singular
graph. The commutativity of the $\uplus$ operation allows for the relaxation.
It makes the following generalisation possible.

######  Corollary 2.9.

Consider the simple connected graphs $G_{1},G_{2},G_{3},...,G_{n}$ and define
the $n_{G}$-partite graph to be the graph $G_{n_{G}}$ obtained by adding all
the edges $vu$, if and only if $v\in V(G_{i})$ and $u\in G_{j},i\neq j$ to
$\cup_{\forall i}G_{i}.$ We have that
$\Upsilon(G_{n_{G}})=\sum\limits_{\forall i}\Upsilon(G_{i}).$

###### Proof.

Similar to the proof of Proposition 2.8. ∎

[Open problem: In the graph $G\uplus H$ we restrict the explosion of vertex
$v_{i}\in V(G)$ to arc to non-adjacent vertices $v_{j}\in V(G)$ and the arcing
of the explosion of vertex $u_{i}\in V(H)$ to non-adjacent vertices $u_{j}\in
V(H).$ Clearly $\Upsilon(G\uplus
H)=\Upsilon(G)+\Upsilon(H)=\Upsilon(H)+\Upsilon(G).$ This law is called the
$\uplus$-commutative law of _McPherson numbers_. It is easy to see that the
$\uplus$-associative law of _McPherson numbers_ namely,

$\Upsilon(G\uplus H\uplus M)=\Upsilon(G\uplus
H)+\Upsilon(M)=\Upsilon(G)+\Upsilon(H\uplus M)=\Upsilon(G\uplus
M)+\Upsilon(H)$ is valid as well.
Alternatively stated, $\Upsilon(G\uplus H\uplus
M)=(\Upsilon(G)+\Upsilon(H))+\Upsilon(M)=\Upsilon(G)+(\Upsilon(H)+\Upsilon(M))=(\Upsilon(G)+\Upsilon(M))+\Upsilon(H).$
If both graphs $G$ and $H$ are graphs on $n$ vertices we note that
$\Upsilon(G\uplus
K_{n})=\Upsilon(G)+\Upsilon(K_{n})=\Upsilon(G)+0=\Upsilon(G)=0+\Upsilon(G)=\Upsilon(K_{n})+\Upsilon(G)=\Upsilon(K_{n}\uplus
G).$ If possible, describe the algebraic structure.]
[Open problem: If possible, prove that for a Jaco Graph
$J_{n}(1),n\in\mathbb{N},n\geq 3$ we have that $d^{+}(v_{n})$ is unique (_non-
repetitive_) if and only if $\Upsilon(J_{n}(1))$ is unique (_non-
repetitive_).]
[Open problem: Define the _McPherson graph_ to be the directed subgraph of
$G^{\prime}_{\Upsilon(G)}$ which was obtained through _vertex explosions_.
Characterise the _McPherson graph_ in general if possible, or for some
specialised graphs.]
[Open problem: Prove the conjecture that if graph $G$ on $n$ vertices has
$d(v_{i})=d(v_{j}),i\neq j$ for all vertices of $G$, it is always possible to
add a vertex $v_{n+1}$ with edges such that $G+v_{n+1}$ has the same graph
theoretical structural properties.]
[Open problem: Example 1 showed that the graph $G$ has $\Upsilon(G)=3.$ The
maximum number of vertex explosions to obtain $G^{*}_{5}\simeq K_{6}$ was
given by $\Upsilon^{*}(G)=5.$ The _McPherson discrepancy_ is defined to be
$\Upsilon_{d}(G)=\Upsilon^{*}(G)-\Upsilon(G).$ If $\Upsilon_{d}(G)=0$ the
graph $G$ is said to be _McPherson stable_. It easily follows that
$K_{n},C_{4}$ are _McPherson stable_ whilst $P_{n},n\geq 4$ is not. The
maximum number of vertex explosions can be determine by applying the _inverse
McPherson recursion_. The maximum McPherson number of a simple connected graph
$G$ on $n$ vertices is obtained through the inverse McPherson recursion. Let
any vertex with maximum degree $d(v)\leq n-2$ explode on the first iteration.
This is followed by letting any vertex in the underlying graph $G^{*}_{1}$ of
$G^{\prime}_{1}$ with maximum degree $d(u)\leq n-2$ explode on the second
iteration to obtain $G^{\prime}_{2}$ and, so on. If after exactly $\ell^{*}$
vertex explosions the underlying graph $G^{*}_{\ell^{*}}\simeq K_{n}$ then
$\Upsilon^{*}(G)=\ell^{*}.$ Characterise _McPherson stable_ graphs.]
[Open problem: Platonic graphs are the graphs whose vertices and edges are the
vertices and edges of platonic solids such as _the tetrahedron, the
octahedron, the cube, the icosahedron, the dodecahedron_ and alike, See [2].
Determine the McPherson number for platonic graphs.]

_Open access: 333To be submitted to the _Pioneer Journal of Mathematics and
Mathematical Sciences.
Dedicated to our friend, _Vic McPherson_.__ This paper is distributed under
the terms of the Creative Commons Attribution License which permits any use,
distribution and reproduction in any medium, provided the original author(s)
and the source are credited.

References (Limited)

$[1]$ Bondy, J.A., Murty, U.S.R., _Graph Theory with Applications,_ Macmillan
Press, London, (1976).
$[2]$ Fréchet, M., Ky, F., _Initiation to Combinatorial Topology,_ Prindle,
Weber and Schmidt, Boston, (1967).
$[3]$ Kok, J., Fisher, P., Wilkens, B., Mabula, M., Mukungunugwa, V.,
_Characteristics of Finite Jaco Graphs, $J_{n}(1),n\in\mathbb{N}$_, arXiv:
1404.0484v1 [math.CO], 2 April 2014.


∎

11institutetext:  ∗Ran Cheng is the corresponding author.

S. Hu, R. Cheng, C. He, and Z. Lu 22institutetext: Guangdong Provincial Key
Laboratory of Brain-inspired Intelligent Computation, Department of Computer
Science and Engineering, Southern University of Science and Technology,
Shenzhen 518055, China.
22email<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>33institutetext: J. Wang and M.
Zhang 44institutetext: Shanghai Aircraft Design and Research Institute,
Shanghai 200135, China.
44email<EMAIL_ADDRESS><EMAIL_ADDRESS>
# Accelerating Multi-Objective Neural Architecture Search by Random-Weight
Evaluation

Shengran Hu  Ran Cheng∗ Cheng He  Zhichao Lu  Jing Wang  Miao Zhang

(Received: date / Accepted: date)

###### Abstract

For the goal of automated design of high-performance deep convolutional neural
networks (CNNs), Neural Architecture Search (NAS) methodology is becoming
increasingly important for both academia and industries. Due to the costly
stochastic gradient descent (SGD) training of CNNs for performance evaluation,
most existing NAS methods are computationally expensive for real-world
deployments. To address this issue, we first introduce a new performance
estimation metric, named Random-Weight Evaluation (RWE) to quantify the
quality of CNNs in a cost-efficient manner. Instead of fully training the
entire CNN, the RWE only trains its last layer and leaves the remainders with
randomly initialized weights, which results in a single network evaluation in
seconds. Second, a complexity metric is adopted for multi-objective NAS to
balance the model size and performance. Overall, our proposed method obtains a
set of efficient models with state-of-the-art performance in two real-world
search spaces. Then the results obtained on the CIFAR-10 dataset are
transferred to the ImageNet dataset to validate the practicality of the
proposed algorithm. Moreover, ablation studies on NAS-Bench-301 datasets
reveal the effectiveness of the proposed RWE in estimating the performance
compared with existing methods.

###### Keywords:

Neural Architecture Search Efficient Performance Estimation Multi-Objective
Optimization Evolutionary Algorithms

##  1 Introduction

In recent years, deep convolutional neural networks (CNNs) have been widely
studied and achieved astonishing performance in different computer vision
tasks. One crucial component among these studies is the design of dedicated
architectures of neural networks, which significantly affects the performance
and generalization ability of CNNs among various tasks krizhevsky2012imagenet
; he2016deep ; muxconv . Along with the architectural milestones, from the
original AlexNet krizhevsky2012imagenet  to the ResNet he2016deep , the
performance of CNNs across extensive datasets and tasks keeps boosting.
However, it still takes researchers enormous works to achieve these
architectural advancements via trial-and-error tuning manually. Therefore,
Neural Architecture Search (NAS) has emerged as an alternative way to design
CNN in an automated manner. Although NAS alleviates the laborious experiments
by researchers, existing NAS algorithms still suffer from numerous
computational overheads, leading to challenges in the real-world deployment
Zoph2018 ; Real2019 .

The expensive evaluations of the performance of architectures contribute to
dominant computational consumption in the NAS algorithm. Usually, a brute-
force training of a network can cost days to weeks on a single GPU, varying
from simple to complex datasets and tasks. Therefore, several approaches have
been proposed to approximate the true performance with fewer computational
costs and, as a result, fewer fidelities. These works can be roughly divided
into three categories.

The first category includes methods that reduce training budgets via
decreasing the network sizes (e.g., the number of layers and channels), which
are widely adopted in early NAS works Zoph2018 ; Real2019 ; he2021efficient .
Nevertheless, their effectiveness has not been systematically researched until
recently zela2018 ; Zhou_2020_CVPR , demonstrating that their effectiveness
can be limited under inappropriate parameter settings. Moreover, these methods
are computationally expensive due to the thorough training for every single
network. Finally, these methods require that the CNN architectures in search
spaces should be modular, i.e., the networks are constructed by repeatedly
stacking modular blocks. For instance, several state-of-the-art search spaces
in Liu2018a ; lu2020nsganetv2  do not follow the constraints above, and the
extension of these methods to new search spaces is not trivial.

The second category is often known as the supernet-based method, which intends
to avoid training every architecture from scratch tan2020relativenas ;
lu2020nsganetv2 ; lu2021neural . This technique typically decouples NAS into
two main stages to share weights during searching. In the first stage, it
constructs a supernet that contains all possible architectures in the search
space, such that each architecture becomes a subnet of the supernet. In the
second stage, the search process begins, and each architecture inherits the
weights from the supernet, and thus the evaluation of each architecture
becomes a simple inference on the valid set. Despite the fact that this
technique can speed up the searching process, the construction of the supernet
could be more time-consuming than a complete search cai2020once . Besides, the
search spaces require substantial modifications to accommodate the
construction of the supernet Liu2019 .

The third category consists of several studies known as the zero-cost proxies
abdelfattah2021zerocost ; mellor2020neural , which estimate the performance
with a few mini-batches of forward/backward propagation. To be more specific,
this category analyzes information such as gradients, activations, or
magnitudes of parameters to achieve estimations for reducing the computational
cost drastically. Notably, most of these techniques attempt to validate their
effectiveness on several NAS-Bench datasets siems2020bench ;
dong2020nasbench201  which are public architecture datasets constructed by
exhaustively evaluating search spaces. Nevertheless, they may perform well
only on certain NAS-Bench datasets abdelfattah2021zerocost , or they are not
validated on real-world search spaces mellor2020neural .

On top of the performance estimation methods, a branch of works named
predictor-based NAS lu2020nsganetv2 ; lu2021neural  has been proposed to
further improve the sampling efficiency. In these works, a regression model,
i.e., a performance predictor, would be trained to fit the mapping from the
architectures to the corresponding performance. After the establishment of the
predictor, the estimated performance in the searching stage is achieved by the
evaluations of the predictor instead of the expensive estimation methods,
which improves the sampling efficiency of NAS. The predictor can be built upon
different performance estimation methods, e.g., based on the training with
reduced budgets 8744404 ; wen2020neural  and the evaluations of the supernet
lu2020nsganetv2 ; lu2021neural . Also, several works explore different
encoding methods for the architectures Sun2021 ; ning2020generic ; yan2020does
and different machine learning models as the predictor ning2020generic ;
8744404 ; wen2020neural .

In this work, we propose a Random-Weight Evaluation (RWE) approach. Comparing
to the existing methods, it is less expensive, more flexible, and the
effectiveness is validated more solid. In detail, by training the last
classification layer only and keeping others with randomly initialized
weights, RWE saves orders of magnitudes computational resources comparing with
conventional methods. At the same time, RWE is conceptually flexible with any
search space, and it does not need any modifications to the search space.
Moreover, the effectiveness of RWE is validated by the searching on two modern
real-world search spaces and some ablation studies on the NAS-Bench-301
dataset. We briefly summarize our main contributions below:

  * •

We propose a novel performance estimation metric, namely RWE, for efficiently
quantifying the quality of CNNs. RWE is highly efficient in computational
costs compared with conventional methods, which reduces the wall-clock
evaluation time from hours to seconds. Extensive experiments on both real-
world search spaces and benchmark search space NAS-Bench further validate the
effectiveness of RWE.

  * •

Paired with a multi-objective evolutionary algorithm, our RWE based NAS
algorithm can achieve a set of efficient networks in one run, where both the
performance and efficiency of models are considered. For instance, the
proposed algorithm achieves state-of-the-art performance on the CIFAR-10
dataset, resulting in the networks from the largest, with 2.98% Top-1 error
and 1.5M parameters, to the smallest, with 4.05% Top-1 error and 0.9M
parameters. The experiments of transferability on ImageNet further demonstrate
the competitiveness of our method. With such competitive performance, the
whole searching procedure only costs less than two hours on a single GPU card,
making the algorithm highly practical in handling real-world applications.

The rest of this paper is organized as follows. In Section 2, some related
work on multi-objective NAS algorithms and the expressive power of randomly
initialized convolution filters is introduced. Then we present our proposed
approach in Section 3, including the detailed random-Weight evaluation, search
strategy, and search space and encoding. Comparative studies are shown in
Section 4, and the conclusions are drawn in Section 5.

##  2 Related Works

In this section, we briefly discuss two topics related to the technicalities
of our approach, i.e., multi-objective NAS and randomly initialized
convolution filters.

###  2.1 Multi-Objective NAS

Single-objective optimization algorithms have dominated the early researches
in NAS Zoph2018 ; Liu2019 ; Real2019 , which mainly propose architectures to
maximize their performance on certain datasets and tasks. Though NAS
algorithms have shown their practicality in solving benchmark tasks, they
cannot meet the demands from deployment scenarios varying from GPU servers to
edge devices Howard2017 . Thus, NAS algorithms are expected to balance between
multiple conflicting objectives, such as inference latency, memory footprint,
and power consumption. Though recent attempts often convert multiple competing
objectives into a single objective in a weighted sum manner Tan2019 ; Cai2019
, they may miss the global optima of the problem. As a result, multiple runs
of the algorithm could be required in real-world applications, due to the
difficulty of deciding the best coefficient for weighted sum. Also, the search
strategies these works adopted are primarily based on gradient-based methods
or reinforcement learning, and they cannot approximate the Pareto front in a
single run.

There are also several works that adopt multi-objective evolutionary
algorithms as search strategies for NAS Lu2019 ; lu2020nsganetv2 ;
lu2021neural . The population-based strategies introduce the natural
parallelism, which increases the practicality in large-scale applications, and
the conflicting nature of multiple objectives is helpful to enhance the
diversity of the population. Most of them aim to tradeoff between the
performance and the complexity of networks Lu2019 ; lu2020nsganetv2 , while
some other works temp to exploit the performance among different datasets,
similar to the concepts in multi-task learning lu2021neural . Following
successful practices, we adopt a classic multi-objective evolutionary
algorithm, namely NSGA-II deb2002fast . We aim to achieve a set of efficient
architectures in one run, where the proposed performance metric and a
complexity metric FLOPs are two conflicting objectives to be optimized.

###  2.2 Expressive Power of Randomly Initialized Convolution Filters

The RWE is surprisingly powerful, inspired by the fact that the convolution
filters are in terms of extracting the features for input images, even with
randomly initialized weights Jarrett2009 . It is indicated in Jarrett2009 ;
wann2019  that, with proper architecture, the convolution filters with
randomly initialized weights can be as competitive as the ones with fully
trained weights on both visual and control tasks. Also, it is validated that
the structure itself can introduce prior knowledge to be capable of capturing
the features for visual tasks Adebayo2018 ; ulyanov2018deep . Similarly, the
local binary convolutional neural network achieves comparable performance to
CNNs with fully trained convolution filters by learning a linear combination
of randomly initialized convolution filters lbcnn .

Some early works in the literature conceptually explore the potential of
estimating the performance of networks from randomly initialized weights. In
detail, Sax _et al._ mathematically proved that the convolutional ﬁlter with
random weights still has its key functionality, which is frequency selectivity
and translation invariance. These characteristics are utilized to rank shallow
neural networks with different network configurations Saxe2011 . Rosenfeld and
Tsotsos successfully predict the performance ranking on several widely used
CNN architectures by only training a fraction of weights in convolutional
filters Rosenfeld2019 .

Although previous works show the potential of randomly initialized convolution
filters, those methods are not scalable to real-world applications. In this
work, we randomly initialized and freeze the weights in convolutional kernels
in CNN, only training for the last classification layer. Using the predictive
performance after doing so as a performance metric, we demonstrate the
scalability of our approach on complex datasets and modern CNN search spaces
that contains deep yet powerful CNNs.

##  3 Proposed Approach

The Multi-objective NAS problem for a target dataset $\mathcal{D}=$
$\\{\mathcal{D}_{trn},\mathcal{D}_{vld},\mathcal{D}_{tst}\\}$ can be
formulated as the following bilevel optimization problem lu2020 , —l—
αf_1(α;w^*(α)),f_2(α),…,f_m(α) w^*(α) ∈argmin_w L(w;α) α ∈Ω_α, w ∈Ω_w where
the upper lever variable $\boldsymbol{\alpha}$ defines an architecture in the
search space $\Omega_{\alpha}$, and the lower level variable
$\boldsymbol{w}(\boldsymbol{\alpha})$ represents the corresponding weights.
$\mathcal{L}(\boldsymbol{w};\boldsymbol{\alpha})$ is the loss function on the
$\mathcal{D}_{trn}$ for the architecture $\boldsymbol{\alpha}$ with weights
$\boldsymbol{w}$. The first objective $f_{1}$ represents the classification
error on $\mathcal{D}_{vld}$, which depends on both architectures and weights.
Other objectives $f_{2},...,f_{m}$ only depend on architectures, such as the
number of parameters, floating-point operations (FLOPs), latencies, etc.

In our approach, we simplify the complex bilevel optimization by using the
proposed performance metric RWE as a proxy of $f_{1}$. In addition, we adopt
the complexity metric FLOPs as the second objective $f_{2}$ to optimize. As a
result, the multi-objective formulation of this work becomes —l— αRWE(α),
FLOPs(α) α ∈Ω_α, where RWE and FLOPs represent the values of these metrics
with respect to architecture $\alpha$.

###  3.1 Random-Weight Evaluation

Input : An architecture $\boldsymbol{\alpha}$, a training and validation
dataset $\mathcal{D}_{trn}\text{, }\mathcal{D}_{vld}$

Output : The performance metric _RWE_ of $\boldsymbol{\alpha}$.

1

2 _net_ $\leftarrow$ Decode the architecture $\boldsymbol{\alpha}$ into CNN
backbone;

3Randomly initialize the _net_ and a linear classifier _clsfr_ ;

4Freeze the weights of _net_ throughout the whole algorithm;

5 _features_ $\leftarrow$ Infer $\mathcal{D}_{trn}$ on the _net_ ;

6Train the linear classifier _clsfr_ with the _features_ as input;

7foreach  _image, target $\in$ $\mathcal{D}_{vld}$_ do

8

9 Infer _image_ on _net_ with _clsfr_ ;

10  _prediction_ $\leftarrow$ the label approved by _clsfr_ ;

11 Compare the _prediction_ with _target_ and record the result;

12 end foreach

13

14 _RWE_ $\leftarrow$ Calculate the classification error rate;

15return _RWE;_

16

Algorithm 1 Random-Weight Evaluation

As mentioned in Section 2.2, randomly initialized convolution filters are
surprisingly powerful in extracting the features from images, due to the
frequency selectivity and translation invariance preserved with random weights
Saxe2011 . Inspired by this amazing characteristic, this work attempts to
judge the quality of the architectures based on the ability of architectures
with random weights to extract “good” features. And we quantify the quality of
the features by training a linear classifier that takes these features as
input and calculates the classification error for that classifier.

We detail the proposed performance metric Random-Weight Evaluation (RWE) as
following. The overall procedure is shown in the Algorithm 1. First, we decode
the encoding of a candidate architecture $\alpha$ into a CNN backbone _net_ ,
which refers to all layers before the last classification layer. Second, we
initialize the _net_ and a linear classifier _clsfr_ with random weights, the
latter of which acts as the last classification layer in a complete CNN and
its structure is identical for all candidate CNNs in the search space. Here, a
modified version of the _Kaiming initialization_ He  is adopted to initialize
the _net_ (default setting in PyTorch). The weights in the backbone part will
keep frozen throughout the algorithm. Third, we infer the training set
$D_{trn}$ on _net_ and utilize the output _feature_ to train _clsfr_. Finally,
after assembling _net_ and trained _clsfr_ into a complete CNN, this CNN gets
tested on the validation set $D_{vld}$, the output error rate of which becomes
the value of RWE.

###  3.2 Search Strategy

We adopt a classic multi-objective evolutionary algorithm NSGA-II deb2002fast
in our approach, where the searching process is detailed as below.

First, we randomly initialize the population, the individual of which get
evaluated with RWE and FLOPs as two objectives. Second, we apply the binary
tournament selection to select the parents for offspring. Third, the two-point
crossover and the polynomial mutation are applied to generate the offspring,
followed by the evaluations of offspring. Finally, we apply the environment
selection based on the nondominated sorting and the crowding distance
deb2002fast , and the process is repeated until reaching the max generation.

###  3.3 Search Space and Encoding

Figure 1: The micro Zoph2018  and macro Xie2017  search spaces adopted in our
approach. LEFT: Overall network architecture. MIDDLE and RIGHT: Design of
layers in micro and macro search space.

Our proposed RWE is conceptually flexible and can be applied to any search
space. To validate the effectiveness of our algorithm on the real-world
application, we experiment with two modern search spaces, the micro Zoph2018
and macro Xie2017  search spaces, in our approach. As shown in Fig. 1 LEFT,
these two search spaces are modular search spaces, in which two kinds of
layers, the normal and reduction layers, are repeatedly stacked, forming the
complete CNN. The former kind of layers keeps the resolution and the number of
channels for input images, while the latter halves the resolution and doubles
the number of channels. The main difference between the micro and macro spaces
is the design of each layer and the way to stack them into a complete CNN.

Micro Search Space: In the micro search space Zoph2018 , we search for both
the normal and reduction layers, named the normal and reduction cells. All the
normal cells share the same architecture in a CNN, in which the weights are
different though, and the case for the reduction cells is the same. Typically,
we scale networks using different repeating number ($\mathbf{N}$) in searching
and validation stages. The normal and reduction cells share the same template,
except for the stride size in operators. In each kind of cell, we search for
both of the connections between nodes and the operation applied on each
connection, as shown in Fig. 1 MIDDLE.

Macro Search Space: In the macro search space Xie2017 , we search for only the
normal layers, leaving the predefined reduction layers identical. Each normal
layer in the macro search space is searched independently, where the repeating
number in a phase ($\mathbf{N}$) is equal to one. In the normal layers, only
the connection patterns get searched, and the operation in each node is a
predefined sequential operator, including convolution operators, batch
normalization layers, and activation functions. Fig. 1 RIGHT shows an example
for candidate connection patterns.

##  4 Experimental Results

In this section, we first present the searching results of our proposed NAS
algorithm on the micro and macro search spaces for a modern classification
dataset CIFAR-10 krizhevsky2009learning . Then, the ablation studies on NAS-
Bench-301 siems2020bench  demonstrate the effectiveness of our evaluation
method and the rationality of some design choices. Finally, the experiment on
ImageNet imagenet_cvpr09 , which is one of the most challenging classification
benchmarks, shows the transferability of our architectures and illustrates the
practicality for real-world applications.

###  4.1 Searching on CIFAR-10

In our approach, we search on a modern classification dataset CIFAR-10
krizhevsky2009learning , which contains ten categories and 60K $32\times 32$
images. Conventionally, the dataset split into a training set with 50K images
and a test set with 10K images. Following common settings in NAS algorithms
Zoph2018 ; Real2019 ; Lu2019 , we further split the training set (80%-20%) in
the searching stage to create the training and validation sets.

Here we introduce the detailed implementation and parameter settings in our
NAS algorithm. In the searching stage, the population size is set to 20 and
the max generation is set to 30. For RWE, the architectures in the micro
search space have 10 initial channels and 5 layers, and the architectures in
the macro search space have 32 initial channels. Also, due to the randomness
introduced in RWE, we adopt assemble learning technique Hansen1990  in the
training of the linear classifier to stabilize the results. Specifically,
there are five classifiers to be trained, each of which is only exposed to 4/5
features. We only introduce the normalization techniques in the preprocessing
of the input images, without the data augmentation techniques introducing the
randomness. SGD optimizer with an initial learning rate of 0.25 and a momentum
of 0.9 is adopted, where the cosine annealing schedule loshchilov2016sgdr
decays the learning rate to zero gradually. The batch size is set to 512 and
the training iterations conduct for 30 epochs. The average CPU time for a
single evaluation is approximately 10 seconds with a single Nvidia 2080Ti.

Table 1: The results of the proposed algorithm and other state-of-the-art
methods on CIFAR-10. ⇕ denotes the results achieved by the same training
setting with ours and reported in Lu2019 . † denotes the work that adopts the
regularization technique cutout devries2017improved .

Architecture |  | Test Error
---
(%)
| Params
---
(M)
| FLOPs
---
(M)
| Search Cost
---
(GPU days)
Search Method
Wide ResNet Zagoruyko2016  | 4.17 | 36.5 | - | - | manual
DenseNet-BC Huang2017  | 3.47 | 25.6 | - | - | manual
BlockQNN† Zhong2020  | 3.54 | 39.8 | - | 96 | RL
SNAS† Xie2019  | 3.10 | 2.3 | - | 1.5 | gradient
NASNet-A†⇕ Zoph2018  | 2.91 | 3.2 | 532 | 2,000 | RL
DARTS†⇕ Liu2019  | 2.76 | 3.3 | 547 | 4 | gradient
NSGA-Net⇕ \+ macro space Lu2019  | 3.85 | 3.3 | 1290 | 8 | evolution
Macro-L† | $\boldsymbol{4.27}$ | $\boldsymbol{2.79}$ | $\boldsymbol{1074}$ | $\boldsymbol{0.14}$ | evolution
AE-CNN + E2EPP 8744404  | 5.30 | 4.3 | - | 7 | evolution
Hier. Evolution Liu2018a  | 3.75 | 15.7 | - | 300 | evolution
AmoebaNet-A†⇕ Real2019  | 2.77 | 3.3 | 533 | 3,150 | evolution
NSGA-Net†⇕ Lu2019  | 2.75 | 3.3 | 535 | 4 | evolution
Micro-S† | $\boldsymbol{4.05}$ | $\boldsymbol{0.9}$ | $\boldsymbol{203}$ | $\boldsymbol{0.05}$ | evolution
Micro-M† | $\boldsymbol{3.37}$ | $\boldsymbol{1.2}$ | $\boldsymbol{249}$ | $\boldsymbol{0.05}$ | evolution
Micro-L† | $\boldsymbol{2.98}$ | $\boldsymbol{1.5}$ | $\boldsymbol{340}$ | $\boldsymbol{0.05}$ | evolution

Figure 2: The visualization of Micro-L and Macro-L architecture.

For the validation stage, we scale the architectures to the deployment
settings, where the number of training epochs, layers, and channels increases.
The architectures from the final Pareto front are selected to be trained from
scratch, where the number of layers and initial channels is set to 20 and 34
for the micro search space, and the number of channels is set to 128 in all
layers in the macro search space. We use the same SGD optimizer as the one in
the training stage, except the initial learning rate is set to 0.025. The
selected architectures are trained for 600 epochs with a batch size of 96.
Also, the regularization techniques cutout devries2017improved  and scheduled
path dropout Zoph2018  is introduced, where the cutout length and the drop out
rate are set to 16 and 0.2. The settings are the same with state-of-the-art
algorithms for a fair comparison Lu2019 .

The results of validation and the comparison to other state-of-the-art
architecture are shown in Table. 1. The representative architectures from the
final Pareto front get compared to both hand-crafted and search-based
architectures. In the experiments with the micro search space, the
architecture with the lowest error rate (Micro-L) in our approach achieves a
2.98% Top-1 error rate with 340M FLOPs. With fewer FLOPs, it has competitive
performance with state-of-the-art architectures. Also, Micro-M, Micro-S shows
a different tradeoff between performance and complexity. Similar to the micro
search space, the chosen architecture in the macro search space (Macro-L) has
competitive performance and fewer FLOPs comparting to the state-of-the-art.
The visualization of the detailed structures of Micro-L in the micro space and
Macro-L in the macro space are shown in Fig. 2.

###  4.2 Effectiveness of Random-Weight Evaluation

Figure 3: The Spearman correlation coefficient for different performance
metrics in searching on NAS-Bench-301. Figure 4: The Spearman correlation
coefficient for different initialization method in searching on NAS-Bench-301.

To demonstrate the effectiveness of RWE, we conduct experiments on NAS-
Bench-301 dataset siems2020bench . The dataset is constructed by the surrogate
model trained by sampled architectures in search space, such that it covers
the whole search space to help researchers to analyze their NAS algorithms.
While other NAS-Bench datasets construct a toy search space for the
convenience of studies dong2020nasbench201 , NAS-Bench-301 covers a real-world
search space, which is the micro search space adopted in our work. Thus, the
ablation studies based on NAS-Bench-301 examine the behavior of our algorithm
during the searching stage.

We evaluate the effectiveness of estimation strategies by calculating the
Spearman correlation coefficient between the estimation and queried
performance from NAS-Bench-301. The target individuals are from the union of
the population of each generation and their offspring. The Spearman
correlation coefficient, which ranged from $[-1,1]$, is a nonparametric
measure of rank correlation. The higher coefficient is, the ranking of two
variables has a more similar rank to each other. The idea of experiment
settings is that, during the evolutionary algorithm, the only phase depending
on the estimation strategy is the mating and survival selection, which happen
in the union mentioned above. The higher the correlation coefficient is, the
more reliable the estimation strategy is. Thus, the algorithm has more chances
to choose good candidates from a set of architectures.

In the following experiments, we use the same search strategy as introduced in
Section 3.2 and conduct the experiments in NAS-Bench-301 with 20 generations.
The search space in NAS-Bench-301 is a subset of the Micro Space, where
identical connections to a single node are not allowed in NAS-Bench-301. As a
result, we add a fix operation in the search strategy, which randomly chooses
another connection to avoid duplication when an invalid architecture is
produced. Also, the results present the mean and the standard variation of
five independent trials with different random seeds.

We first compare our estimation strategy RWE with the zero-cost proxies
abdelfattah2021zerocost ; mellor2020neural  and the training-based evaluation
method Zoph2018 ; Zhou_2020_CVPR . For the zero-cost proxies, we choose the
representative performance metrics _synflow_ , _grasp_ , and _fisher_ from
abdelfattah2021zerocost , and _jacob_conv_ from mellor2020neural . For the
training-based method, we train the network for 10 epochs with the number
initial channels and layers of 16 and 8. As shown in Fig. 3, the proposed RWE
outperforms all zero-cost proxies after the initial stage of searching, ending
up with a similar accuracy with the training-based method. The experiment
shows the effectiveness of RWE is competitive to the one of training-based
method while having much fewer computational overheads. Paired with the
searching in the micro and macro spaces, it further shows that RWE performs
well in the real-world search spaces.

We then investigate the effects of different initialization methods applied in
our approach. The method we adopt in this paper is the default one in PyTorch,
and we examine other four representative initialization methods, which are
known as _Kaiming normal (uniform) initialization_ He  and _Xavier normal
(uniform) initialization_ glorot2010understanding . As shown in Fig. 4, the
initialization methods have minor impacts on the effectiveness of RWE, as we
observe no significant different behaviors. The experiment shows that our
approach is robust to different initialization methods.

###  4.3 Transferring to ImageNet

Table 2: The results of the proposed algorithm and other state-of-the-art methods on ImageNet. ⇑ denotes the methods that first get searched on CIFAR-10 and then get transferred to ImageNet. Architecture |  | Test Error (%)
---
Params (M) |  FLOPs (M)
top-1 | top-5
MobileNetV1 Howard2017  | 31.6 | - | 2.6 | 325
InceptionV1 Szegedy2015  | 30.2 | 10.1 | 6.6 | 1448
ShuffleNetV1 Zhang2018  | 28.5 | - | 3.4 | 292
VGG simonyan2014very  | 28.5 | 9.9 | 138 | -
MobileNetV2 Sandler2018  | 28.0 | 9.0 | 3.4 | 300
ShuffleNetV2 1.5$\times$ ma2018shufflenet  | 27.4 | - | - | 299
NASNet-C ⇑ Zoph2018  | 27.5 | 9.0 | 4.9 | 558
SNAS ⇑ Xie2019  | 27.3 | 9.2 | 4.3 | 533
EffPNet ⇑ 9349967  | 27.0 | 9.25 | 2.5 | -
DARTS ⇑ Liu2019  | 26.7 | 8.7 | 4.7 | 574
AmoebaNet-B ⇑ Real2019  | 26.0 | 8.5 | 5.3 | 555
PNAS ⇑ liu2018progressive  | 26.0 | 8.5 | 5.3 | 555
Micro-L ⇑ | $\boldsymbol{27.6}$ | $\boldsymbol{9.4}$ | $\boldsymbol{3.7}$ | $\boldsymbol{363}$

To validate the practicality of our output architectures, we experiment with
the transferability of the architecture Micro-L from CIFAR-10 to ImageNet
imagenet_cvpr09 . ImageNet dataset, which substantially shows its importance
in real-world applications, contains more than one million images. With
various resolutions, these images unevenly distribute in 1K categories. The
general idea of transferring is to scale the architectures with a greater
number of channels but a smaller number of layers, which is introduced by some
classic works in NAS Zoph2018 ; Xie2019 . More specifically, the architectures
starts with three stem convolutional layers with stride 2, which downsample
the resolution by eight times. Following, there are 14 layers and 48 initial
channels, where the reduction cells appear on the fifth and ninth layer. Some
common data augmentation techniques are also adopted, including the random
resize, the random crop, the random horizon flip, and the color jitter. We
train our model with the SGD optimizer with 250 epochs, batch size of 1024,
and resolution of $224\times 224$ on 4 Nvidia Tesla V100 GPU. The initial
learning rate is set to 0.5 and decays to $1\times 10^{-5}$ linearly. In
addition, the warmup strategy is applied on the first five epochs, increasing
the learning rate from 0 to 0.5 linearly. The label smooth technique with a
smooth rate of 0.1 is also adopted. Table. 2 shows the experimental results
and the comparisons to state-of-the-art methods. It shows that our approach
has superior performance comparing to the hand-crafted architectures and has
competitive performance with state-of-the-art NAS algorithms.

##  5 Conclusion

This paper proposed a flexible performance metric Random-Weight Evaluation
(RWE) to rapidly estimate the performance of CNNs. Inspired by the expressive
power of randomly initialized convolution filters, RWE only trains the last
classification layer and leaving the backbone with randomly initialized
weights. As a result, RWE achieves a reliable estimation of architectures in
seconds. We further integrated RWE with an evolutionary multi-objective
algorithm, adopting the complexity metric as the second objective. The
experimental results showed that our algorithm achieved a set of efficient
networks with state-of-the-art performance on both micro and macro search
spaces. The resulted architecture with 350M FLOPs achieved 2.98% Top-1 error
in CIFAR-10 and 27.6% Top-1 error in ImageNet after transferring. Also, the
careful ablation studies experiments on different performance metrics and
initialization methods indicated the effectiveness of the proposed algorithm.

###### Acknowledgements.

This work was supported by the National Natural Science Foundation of China
(No. 61903178, 61906081, and U20A20306), the Shenzhen Science and Technology
Program (No. RCBS20200714114817264), the Program for Guangdong Introducing
Innovative and Entrepreneurial Teams (No. 2017ZT07X386), the Shenzhen Peacock
Plan (No. KQTD2016112514355531), and the Program for University Key Laboratory
of Guangdong Province (No. 2017KSYS008).

## Conflict of interest

The authors declare that they have no conflict of interest.

## References

  * (1) Abdelfattah, M.S., Mehrotra, A., Dudziak, Ł., Lane, N.D.: Zero-cost proxies for lightweight nas.  In: International Conference on Learning Representations (2021)
  * (2) Adebayo, J., Gilmer, J., Goodfellow, I.J., Kim, B.: Local explanation methods for deep neural networks lack sensitivity to parameter values.  In: International Conference on Learning Representations (2018)
  * (3) Cai, H., Gan, C., Wang, T., Zhang, Z., Han, S.: Once for all: Train one network and specialize it for efficient deployment.  In: International Conference on Learning Representations (2020)
  * (4) Cai, H., Zhu, L., Han, S.: ProxylessNAS: Direct neural architecture search on target task and hardware.  In: International Conference on Learning Representations (2019)
  * (5) Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II.  IEEE Transactions on Evolutionary Computation 6(2), 182–197 (2002)
  * (6) Deng, J., Dong, W., Socher, R., Li, L., Li, K., Li, F.: Imagenet: A large-scale hierarchical image database.  In: IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pp. 248–255 (2009)
  * (7) DeVries, T., Taylor, G.W.: Improved regularization of convolutional neural networks with cutout.  arXiv preprint arXiv:1708.04552 (2017)
  * (8) Dong, X., Yang, Y.: Nas-bench-201: Extending the scope of reproducible neural architecture search.  In: International Conference on Learning Representations (2020)
  * (9) Gaier, A., Ha, D.: Weight agnostic neural networks.  In: Advances in Neural Information Processing Systems, vol. 32, pp. 5365–5379 (2019)
  * (10) Glorot, X., Bengio, Y.: Understanding the difficulty of training deep feedforward neural networks.  In: International Conference on Artificial Intelligence and Statistics, pp. 249–256 (2010)
  * (11) Hansen, L.K., Salamon, P.: Neural Network Ensembles.  IEEE Transactions on Pattern Analysis and Machine Intelligence 12(10), 993–1001 (1990)
  * (12) He, C., Tan, H., Huang, S., Cheng, R.: Efficient evolutionary neural architecture search by modular inheritable crossover.  Swarm and Evolutionary Computation 64, 100894 (2021)
  * (13) He, K., Zhang, X., Ren, S., Sun, J.: Delving deep into rectifiers: Surpassing human-level performance on imagenet classification.  In: International Conference on Computer Vision, pp. 1026–1034 (2015)
  * (14) He, K., Zhang, X., Ren, S., Sun, J.: Deep residual learning for image recognition.  In: IEEE Conference on Computer Vision and Pattern Recognition, pp. 770–778 (2016)
  * (15) Howard, A.G., Zhu, M., Chen, B., Kalenichenko, D., Wang, W., Weyand, T., Andreetto, M., Adam, H.: MobileNets: Efficient convolutional neural networks for mobile vision applications.  arXiv preprint arXiv:1704.04861 (2017)
  * (16) Huang, G., Liu, Z., Van Der Maaten, L., Weinberger, K.Q.: Densely connected convolutional networks.  In: IEEE Conference on Computer Vision and Pattern Recognition, pp. 4700–4708 (2017)
  * (17) Jarrett, K., Kavukcuoglu, K., Ranzato, M., LeCun, Y.: What is the best multi-stage architecture for object recognition?  In: International Conference on Computer Vision, pp. 2146–2153. IEEE (2009)
  * (18) Juefei-Xu, F., Naresh Boddeti, V., Savvides, M.: Local binary convolutional neural networks.  In: IEEE Conference on Computer Vision and Pattern Recognition, pp. 19–28 (2017)
  * (19) Krizhevsky, A., Hinton, G., et al.: Learning multiple layers of features from tiny images.  Tech. rep., Citeseer (2009)
  * (20) Krizhevsky, A., Sutskever, I., Hinton, G.E.: Imagenet classification with deep convolutional neural networks.  In: Advances in Neural Information Processing Systems, vol. 25, pp. 1097–1105 (2012)
  * (21) Liu, C., Zoph, B., Neumann, M., Shlens, J., Hua, W., Li, L.J., Fei-Fei, L., Yuille, A., Huang, J., Murphy, K.: Progressive neural architecture search.  In: European Conference on Computer Vision, pp. 19–34 (2018)
  * (22) Liu, H., Simonyan, K., Vinyals, O., Fernando, C., Kavukcuoglu, K.: Hierarchical representations for efficient architecture search.  In: International Conference on Learning Representations (2018)
  * (23) Liu, H., Simonyan, K., Yang, Y.: DARTS: Differentiable architecture search.  In: International Conference on Learning Representations (2019)
  * (24) Liu, Y., Tang, Y., Sun, Y.: Homogeneous architecture augmentation for neural predictor.  In: International Conference on Computer Vision (2021)
  * (25) Loshchilov, I., Hutter, F.: SGDR: Stochastic gradient descent with warm restarts.  arXiv preprint arXiv:1608.03983 (2016)
  * (26) Lu, Z., Deb, K., Boddeti, V.N.: MUXConv: Information multiplexing in convolutional neural networks.  In: IEEE Conference on Computer Vision and Pattern Recognition, pp. 12044–12053 (2020)
  * (27) Lu, Z., Deb, K., Goodman, E., Banzhaf, W., Boddeti, V.N.: NSGANetV2: Evolutionary multi-objective surrogate-assisted neural architecture search.  In: European Conference on Computer Vision, pp. 35–51 (2020)
  * (28) Lu, Z., Sreekumar, G., Goodman, E., Banzhaf, W., Deb, K., Boddeti, V.N.: Neural architecture transfer.  IEEE Transactions on Pattern Analysis and Machine Intelligence 43(09), 2971–2989 (2021)
  * (29) Lu, Z., Whalen, I., Boddeti, V., Dhebar, Y., Deb, K., Goodman, E., Banzhaf, W.: Nsga-net: neural architecture search using multi-objective genetic algorithm.  In: Genetic and Evolutionary Computation Conference, pp. 419–427 (2019)
  * (30) Lu, Z., Whalen, I., Dhebar, Y., Deb, K., Goodman, E., Banzhaf, W., Boddeti, V.N.: Multi-objective evolutionary design of deep convolutional neural networks for image classification.  IEEE Transactions on Evolutionary Computation 25(2), 277–291 (2020)
  * (31) Ma, N., Zhang, X., Zheng, H.T., Sun, J.: Shufflenet v2: Practical guidelines for efficient cnn architecture design.  In: European Conference on Computer Vision, pp. 116–131 (2018)
  * (32) Mellor, J., Turner, J., Storkey, A., Crowley, E.J.: Neural architecture search without training.  In: International Conference on Machine Learning, pp. 7588–7598. PMLR (2021)
  * (33) Ning, X., Zheng, Y., Zhao, T., Wang, Y., Yang, H.: A generic graph-based neural architecture encoding scheme for predictor-based nas.  In: European Conference on Computer Vision, pp. 189–204. Springer (2020)
  * (34) Real, E., Aggarwal, A., Huang, Y., Le, Q.V.: Regularized evolution for image classifier architecture search.  In: AAAI Conference on Artificial Intelligence, vol. 33, pp. 4780–4789 (2019)
  * (35) Rosenfeld, A., Tsotsos, J.K.: Intriguing properties of randomly weighted networks: Generalizing while learning next to nothing.  In: Conference on Computer and Robot Vision, pp. 9–16 (2019)
  * (36) Sandler, M., Howard, A., Zhu, M., Zhmoginov, A., Chen, L.C.: MobileNetV2: Inverted Residuals and Linear Bottlenecks.  In: IEEE Conference on Computer Vision and Pattern Recognition, pp. 4510–4520 (2018)
  * (37) Saxe, A.M., Koh, P.W., Chen, Z., Bhand, M., Suresh, B., Ng, A.Y.: On random weights and unsupervised feature learning.  In: International Conference on Machine Learning (2011)
  * (38) Siems, J., Zimmer, L., Zela, A., Lukasik, J., Keuper, M., Hutter, F.: Nas-bench-301 and the case for surrogate benchmarks for neural architecture search.  arXiv preprint arXiv:2008.09777 (2020)
  * (39) Simonyan, K., Zisserman, A.: Very deep convolutional networks for large-scale image recognition.  In: International Conference on Learning Representations (2015)
  * (40) Sun, Y., Wang, H., Xue, B., Jin, Y., Yen, G.G., Zhang, M.: Surrogate-assisted evolutionary deep learning using an end-to-end random forest-based performance predictor.  IEEE Transactions on Evolutionary Computation 24(2), 350–364 (2020)
  * (41) Szegedy, C., Liu, W., Jia, Y., Sermanet, P., Reed, S., Anguelov, D., Erhan, D., Vanhoucke, V., Rabinovich, A.: Going deeper with convolutions.  In: IEEE Conference on Computer Vision and Pattern Recognition, pp. 1–9 (2015)
  * (42) Tan, H., Cheng, R., Huang, S., He, C., Qiu, C., Yang, F., Luo, P.: Relativenas: Relative neural architecture search via slow-fast learning.  IEEE Transactions on Neural Networks and Learning Systems pp. 1–1 (2021)
  * (43) Tan, M., Chen, B., Pang, R., Vasudevan, V., Sandler, M., Howard, A., Le, Q.V.: MnasNet: Platform-aware neural architecture search for mobile.  In: IEEE Conference on Computer Vision and Pattern Recognition, pp. 2820–2828 (2019)
  * (44) Ulyanov, D., Vedaldi, A., Lempitsky, V.: Deep image prior.  In: IEEE Conference on Computer Vision and Pattern Recognition, pp. 9446–9454 (2018)
  * (45) Wang, B., Xue, B., Zhang, M.: Surrogate-assisted particle swarm optimization for evolving variable-length transferable blocks for image classification.  IEEE Transactions on Neural Networks and Learning Systems pp. 1–14 (2021).  DOI 10.1109/TNNLS.2021.3054400
  * (46) Wen, W., Liu, H., Chen, Y., Li, H., Bender, G., Kindermans, P.J.: Neural predictor for neural architecture search.  In: European Conference on Computer Vision, pp. 660–676. Springer (2020)
  * (47) Xie, L., Yuille, A.: Genetic CNN.  In: International Conference on Computer Vision (2017)
  * (48) Xie, S., Zheng, H., Liu, C., Lin, L.: SNAS: Stochastic neural architecture search.  In: International Conference on Learning Representations (2019)
  * (49) Yan, S., Zheng, Y., Ao, W., Zeng, X., Zhang, M.: Does unsupervised architecture representation learning help neural architecture search?  Advances in Neural Information Processing Systems 33 (2020)
  * (50) Zagoruyko, S., Komodakis, N.: Wide Residual Networks.  In: British Machine Vision Conference (2016)
  * (51) Zela, A., Klein, A., Falkner, S., Hutter, F.: Towards automated deep learning: Efficient joint neural architecture and hyperparameter search.  arXiv preprint arXiv:1807.06906 (2018)
  * (52) Zhang, X., Zhou, X., Lin, M., Sun, J.: ShuffleNet: An Extremely Efficient Convolutional Neural Network for Mobile Devices.  In: IEEE Conference on Computer Vision and Pattern Recognition, pp. 6848–6856 (2018)
  * (53) Zhong, Z., Yang, Z., Deng, B., Yan, J., Wu, W., Shao, J., Liu, C.: BlockQNN: Efficient Block-wise Neural Network Architecture Generation.  IEEE Transactions on Pattern Analysis and Machine Intelligence 43(7), 2314–2328 (2021)
  * (54) Zhou, D., Zhou, X., Zhang, W., Loy, C.C., Yi, S., Zhang, X., Ouyang, W.: Econas: Finding proxies for economical neural architecture search.  In: IEEE Conference on Computer Vision and Pattern Recognition, pp. 11396–11404 (2020)
  * (55) Zoph, B., Vasudevan, V., Shlens, J., Le, Q.V.: Learning transferable architectures for scalable image recognition.  In: IEEE Conference on Computer Vision and Pattern Recognition, pp. 8697–8710 (2018)