RATs-NAS: Redirection of Adjacent Trails on GCN for Neural Architecture Search

There have been many studies on NAS in the past. Some methods are based on reinforcement learning [4, 11, 12], and others are developed from the evolutionary algorithm [13, 14, 15, 16]. The predictor-based NAS methods focuse on training a predictor to predict the performance of a CNN architecture and quickly filter out impossible candidates [17, 18, 7, 8, 19, 9, 10]. It can reduce the verification time required to evaluate the performance of an architecture candiate. The cell-based search space shares a fixed meta-architecture and the same hyperparameters. Therefore, the search space is reduced to a small cell which contains several operations such as convolution, pooling, etc. The predictors can be GCN-based or MLP-based. The GCN-based predictor performs more accurately, but needs more training time than the MLP-based one. This paper proposes a predictor called RATs-GCN which combines both advantages of GCN and MLP to better find the desired architecture.

There are many types of these predictors [17, 18, 7, 8, 19] for NAS. In recent work, the Neural Predictor [7] is the most common method and encodes a cell as an adjacency matrix and an operations matrix. The adjacency matrix indicates the adjacent trails of operations and the operations matrix indicates the features of operations. The GCN-based predictor shows significant performance in NASBench-101 [5]. Since the number of cells in its meta-architecture is equal, the hyperparameters of GCN are fixed. It uses multiple graph convolution [20] to extract high-level features and directionality from the above two matrices and then uses a fully connected layer to get the prediction. After that, the promising architecture is found with the prediction from the search space. Moreover, BRP-NAS [8] proposes a binary predictor that simultaneously takes two different architectures as input and predicts which is better rather than directly predicting their accuracies. This method dramatically improves the prediction performance compared to Neural Predictor [7]. WeakNAS [9] proposes a more robust sampling method and then adopts MLP to form the predictor. Surprisingly, even though a weak MLP-based preditor is used, it still surpasses Neural Predictor and BRP-NAS. The Arch-Graph [10] proposes a transferable predictor and can find promising architectures on NASBench-101 and NASBench-201 [6] on a limited budget.

As mentioned above, the predictors can be GCN-based or MLP-based. As shown in Fig. 1, GCN uses adjacent trails of operations (adjacency matrix) and operation features (operation matrix) in a cell as input. MLP uses only operations features as input, which means that GCN has more prior knowledge than MLP, and MLP can be regarded as a full network connection architecture of adjacent trails. However, as shown in Tab. 1, we found that GCN is only sometimes better than MLP in all experimental settings since its inherent adjacent trails hinder the information flow caused by matrix multiplication. The adjacency matrix used in GCN may receieve the negative effects caused by the directions stored in the inherent adjacent trails. To address this problem, the trails stored in the adjacency matrix should be adaptively changed. Thus, this paper proposes a RATs (Redirected Adjacent Trails) module and attachs it to the backbone of GCN to adaptively tune the trail directions and their weights stored in the adjacency matrix. This module allows GCN to change each trail with a new learning weight. In extreme cases, RATs-GCN can be GCN or MLP.

As described above, the trails stored in the adjacency matrix of GCN are fixed. If the trails are wrongly set, negative effects will be sent to the predictor and result in accuracy deficiency. Fig. 1 shows the concept of our RATs predictor. The trails in the original GCN-based predcitor are fixed (the left part of Fig. 1) during training and inference. However, in the right part of Fig. 1, the trails in our RATs-GCN will be adaptively adjusted according to the embedded code generated by the operation matrix. Fig. 2 shows the detailed designs of the RATs module and RATs-GCN. Unlike the original GCN-based predictor, a new RATs module is proposed and attached to our RATs-GCN predictor. This module first converts the operation matrix to three new feature vectors: query $Q$, key $K$, and vaule $V$ by self-attention [21]. Then, an embedded code can be obtained by concatenating $Q$, $K$, $V$ with the original adjacency matrix. With this embedded code as input, the trail offsets and operation strengths are generated by a linera projection and sigmoid function. Finally, a new adjacency matrix is generated by adding the offset to the adjacency matrix and then doing a Hadamard product with the strength. The RATs can redetermine the trails and their strengths.

Although the proposed RATs-GCN has already provided more flexible plasticity than GCN and MLP, we all know that a predictor-based NAS’s performance depends not only on predictor design but also on the sampling method. WeakNAS gets SOTA performance using a weaker predictor with a firmer sampling method. So, a promising strategy is bound to bring about considerable improvement for NAS. The proposed P3S is based on our observations on cell-based NAS: (1) The architectures constructed in a cell-based approach share the same meta-architecture and candidate operations for cell search; (2) Each layer in the meta-architecture has the same hyperparameters, such as filters, strides, etc. This means that those candidate operations for cells have the same input and output shapes. In short, there are many architectures that are very similar because they all share the same meta-architecture and limited candidate operations, and the hyperparameters are the same. All of them result in our P3S method. The P3S method rapidly divides search space into tighter FLOPs intervals by following rough steps: (1) Sort the search space $S$ by FLOPs and initialize $i_{1}=0$ and $i_{2}=len(S)-1$ as the focus interval; (2) Select the top 1% architectures of the sub search space $[S_{i},S_{j}]$ sorted by predictor at $t$ time $P_{t}$; (3) If the indexes of selected architectures are at least 75% in the first or second half of the search space sorted by FLOPs, move $i,j$ to that half interval; if not, move $i,j$ to the last interval; (4) Sorting and get the top $k$ of $[S_{i},S_{j}]$ by $P_{t}$ and add these $S_{topk}$ to the sample pool $B$; (5) Training $P_{t+1}$ based on $B$, then back to (2). At the beginning of $t=0$, we randomly select $k$ samples from the search space as initial training samples to train $P_{0}$. After that, the above steps will continue until we find the optimal global cell or exceed the budget. This process aims to rapidly divide and focus on the tighter FLOPs range because we believe the architectures with similar FLOPs will perform similarly. P3S has corrective measures such as Step (2) to avoid falling into the wrong range.

We extensively test MLP, GCN, BI-GCN, and RATs-GCN under similar model settings with 30 runs for a fair comparison. GCN, BI-GCN, and RATs-GCN have three GCN layers with 32 filters and one FC layer with one filter to obtain output prediction accuracy, and MLP has three FC layers with 32 filters and one FC layer with one filter. They all applied the random sampling method to get training architectures from the search space. We evaluated them on NASBench-101 with training budgets of 300, 600, and 900. We also evaluate them on the three sub-datasets (CIFAR-10, CIFAR-100, ImageNet-16) of NASBench-201 with training budgets 30, 60, and 90. As shown in Tab. 1, we found that RATs-GCN surpasses others in mAcc for about 1%$\sim$5% and in Psp for about 10%$\sim$50% under different budgets. The mAcc denotes the average accuracy of the top 100 architectures predicted by the predictor. The Psp denotes the Spearman Correlation of predicted ranking and ground truth ranking.

We design two experiments with 30 runs to verify the performance of RATs-NAS and compare it with other SOTA methods. The first experiment aims to evaluate how fast an NAS method finds the optimal one in the search space. As shown in Tab. 2, we can see that the RATs-NAS use fewer architectures than other methods. It even finds the global optimal cell using an average of 146.7 architecture costs, nearly twice as fast as WeakNAS. Another experiment examines how good architecture can be found at the cost of 150 architectures. As shown in Tab. 3, the RATs-NAS find the architecture with an accuracy of 73.50% on NASBench-201 (CIFAR-10), it better than other SOTA methods. Considering the optimal accuracy are 94.37%, 73.51%, 47.31% in three sub-dataset of NASBench-201, it can find the architectures of 94.36%, 73.50%, 47.07% with such little cost. It shows a significant performance and beats others by a considerable margin.

In order to obtain more evidence to support the RATs module, in addition to other experiments focusing on performance, we also visualize the trail of operations in a single cell. We randomly select an architecture (cell) from NASBench-101, then draw its adjacent trails to represent GCN, draw full trails to represent MLP, and draw new adjacent trails by the last RATs module in RATs-GCN. As shown in Fig. 4, we can see that the proposed RATs-NAS differs from GCN and MLP. Part (c) of Fig. 4 shows that RATs-GCN gets approximate MLP trails with weights between 0 and 1 starting from GCN trails.