Graph HyperNetworks for
Neural Architecture Search

We represent a given architecture as a directed acyclic graph $A=(V,E)$, where each node $v\in V$ has an associated computational operator $f_v$ parametrized by $w_v$, which produces an output activation tensor $x_v$. Edges $e_{u\mapsto v}=(u,v)\in E$ represent the flow of activation tensors from node $u$ to node $v$. $x_v$ is computed by applying its associated computational operator on each of its inputs and taking summation as follows

Our proposed Graph Hypernetwork is defined as a composition of a GNN and a hypernetwork. First, given an input architecture, we used the graphical representation discussed above to form a graph $A$. A parallel GNN $G_A$ is then constructed to be homomorphic to $A$ with the exact same topology. Node embeddings are initialized to one-hot vectors representing the node’s computational operator. After graph message-passing steps, a hypernet uses the node embeddings to generate each node’s associated parameters. Let $h_v^{\left(T\right)}$ be the embedding of node $v$ after $T$ steps of GNN propagation, and let $H(\cdot ;\phi )$ be a hypernetwork parametrized by $\phi$, the generated parameters ${\tilde{w}}_v$ are:

For simplicity, we implement $H$ with a multilayer perceptron (MLP). It is important to note that $H$ is shared across all nodes, which can be viewed as an output prediction branch in each node of the GNN. Thus the final set of generated weights of the entire architecture $\tilde{w}$ is found by applying $H$ on all the nodes and their respective embeddings which are computed by $G_A$:

The computation graph of some popular CNN architectures often spans over hundreds of nodes (He et al., 2016a; Huang et al., 2017), which makes the search problem scale poorly. Repeated architecture motifs are originally exploited in those architectures where the computation of each computation block at different resolutions is the same, e.g. ResNet (He et al., 2016b). Recently, the use of architectural motifs also became popular in the context of neural architecture search, e.g. (Zoph et al., 2018; Pham et al., 2018), where a small graph module with a fewer number of computation nodes is searched, and the final architecture is formed by repeatedly stacking the same module. Zoph et al. (2018) showed that this leads to stronger performance due to a reduced search space; the module can also be transferred to larger datasets by adopting a different repeating pattern.

Our proposed method scales naturally with the design of repeated modules by stacking the same graph hypernetwork along the depth dimension. Let $A$ be a graph composed of a chain of repeated modules $\{A_i{\}}_{i=1}^N$. A graph level embedding $h_{A_i}$ is computed by taking an average over all node embeddings after a full propagation of the current module, and passed onwards to the input node of the next module as a message before graph propagation continues to the next module.

Note that $G_{A_i}$ share parameters for all $A_i$. Please see Figure 2 for an overview.

Standard GNNs employ the synchronous propagation scheme (Li et al., 2016), where the node embeddings of all nodes are updated simultaneously at every step (see Equation 3). Recently, Liao et al. (2018) found that such propagation scheme is inefficient in passing long-range messages and suffers from the vanishing gradient problem as do regular RNNs. To mitigate these shortcomings they proposed asynchronous propagation using graph partitions. In our application domain, deep neural architectures are chain-like graphs with a long diameter; This can make synchronous message passing difficult. Inspired by the backpropagation algorithm, we propose another variant of asynchronous propagation scheme, which we called forward-backward propagation, that directly mimics the order of node execution in a backpropagation algorithm. Specifically, let $s$ be a topological sort of the nodes in the computation graph in a forward pass,

The total number of propagation steps $T$ for a full forward-backward pass will then become $2|V|-1$. Under the synchronous scheme, propagating information across a graph with diameter $|V|$ would require $O\left(|V{|}^2\right)$ messages. This is reduced to $O\left(|V|\right)$ under the forward-backward scheme.

Learning a graph hypernetwork is straightforward since $\tilde{w}$ are directly generated by a differentiable network. We compute gradients of the graph hypernetwork parameters $\varphi ,\phi$ using the chain rule:

The first term is the gradients of standard network parameters, the second term is decomposed as

where (Eq. 17) is the contribution from GNN module $G$ and (Eq. 18) is the contribution from the hypernet module $H$. Both $G$ and $H$ are jointly learned throughout training.

In the real-time setting, the computational budget available can vary for each test case and cannot be known ahead of time. This is formalized in anytime prediction, (Grubb and Bagnell, 2012) the setting in which for each test example $x$, there is non-deterministic computational budget $B$ drawn from the joint distribution $P(x,B)$. The goal is then to minimize the expected loss $L\left(f\right)=E{\left[L\left(f\right(x),B)\right]}_{P(x,B)}$, where $f(\cdot )$ is the model and $L(\cdot )$ is the loss for an $f(\cdot )$ that must produce a prediction within the budget $B$.

We conduct experiments on CIFAR-10. Our anytime search space consists of networks with 3 cells containing 24, 16, and 8 nodes. Each node is given the additional properties: 1) the spatial size it operates at and 2) if an early-exit classifier is attached to it. A node enforces its spatial size by pooling or upsampling any input feature maps inputs that are of different scale. Note that while a naive one-shot model would triple its size to include three different parameter sets at three different scales, the GHN is negligibly affected by such a change. The GHN uses the area under the predicted accuracy-FLOPS curve as its selection criteria. The search space, contains various convolution and pooling operators. Training methodology of the final architectures are chosen to match Huang et al. (2018) and can be found in the Appendix.

Figure 3 shows a comparison with the various methods presented by Huang et al. (2018). Our experiments show that the best searched architectures can outperform the current state-of-the-art human designed networks. We see the GHN is amenable to the changes proposed above, and can find efficient architectures with a random search when used with a strong search space.

In this section, we evaluate whether the parameters generated from GHN can be indicative of the final performance. Our metric is the correlation between the accuracy of a model with trained weights vs. GHN generated weights. We use a fixed set of 100 random architectures that have not been seen by the GHN during training, and we train them for 50 epochs to obtain our “ground-truth” accuracy, and finally compare with the accuracy obtained from GHN generated weights. We report the Pearson’s R score on all 100 random architectures and the top 50 performing architectures (i.e. above average architectures). Since we are interested in searching for the best architecture, obtaining a higher correlation on top performing architectures is more meaningful.

To evaluate the effectiveness of GHN, we further consider two baselines: 1) training a network with SGD from scratch for a varying number of steps, and 2) our own implementation of the one-shot model proposed by Pham et al. (2018), where nodes store a set of shared parameters for each possible operation. Unlike GHN, which is compatible with varying number of nodes, the one-shot model must be trained with $N=17$ nodes to match the evaluation. The GHN is trained with $N=7$, $T=5$ using forward-backward propagation. These GHN parameters are selected based on the results found in Section 5.4.

Table 4 shows performance correlation and search cost of SGD, the one-shot model, and our GHN. Note that GHN clearly outperforms the one-shot model, showing the effectiveness of dynamically predicting parameters based on graph topology. While it takes 1000 SGD steps to surpasses GHN in the “Random-100” setting, GHN is still the strongest in the “Top-50” setting, which is more important for architecture search. Moreover, compared to GHN, running 1000 SGD steps for every random architecture is over 1000 times more computationally expensive. In contrast, GHN only requires a pre-training stage of 6 hours, and afterwards, the trained GHN can be used to efficiently evaluate a massive number of random architectures of different sizes.