SGAS: Sequential Greedy Architecture Search

Introduction

Deep learning has revolutionized computer vision by learning features directly from data. As a result deep neural networks have achieved state-of-the-art results on many difficult tasks such as image classification , object detection , object tracking , semantic segmentation , depth estimation and activity understanding , to name just a few examples. While there was a big emphasis on feature engineering before deep learning, the focus has now shifted to architecture engineering. In particular many novel architectures have been proposed, such as LeCun , AlexNet , VGG , GoogLeNet , ResNet , DenseNet , ResNeXt and SENet . Results on each of the above mentioned tasks keep improving every year by innovations in architecture design. In essence, the community has shifted from feature engineering to architecture engineering.

In recent years, many efforts have been made to reduce the manual intervention required to obtain better models for a particular task. As a matter of fact, a new area of research, commonly referred to as meta-learning, has emerged in order to tackle such problems. The idea of meta-learning is to leverage prior experience in order to quickly find good algorithm configurations, network architectures and any required parameters for a new learning task. Examples of recent meta-learning approaches include automatic hyper-parameter search , data-augmentation , finding novel optimizers and architecture search . In particular, architecture search has sparked a lot of interest in the community. In this task, the search space is huge and manual search is prohibitive.

Early work by Zoph et al. , based on Reinforcement Learning, has shown very promising results. However, its high computational cost has prevented widespread adoption. Recently, differentiable architecture search (DARTS) has been proposed as an alternative which makes architecture search differentiable and much more efficient. This has opened up a path towards computationally feasible architecture search. However, despite their success, current approaches still have a lot of limitations. During the search phase, network architectures are usually constructed from basic building blocks and evaluated on a validation set. Due to computational cost, the size of considered architectures is limited. In the evaluation phase, the best building blocks are used to construct larger architectures and they are evaluated on the test set. As a result there is a large discrepancy between the validation accuracy during search and the test accuracy during evaluation. In this work, we propose a novel greedy architecture search algorithm, SGAS, which addresses this discrepancy and searches very efficiently.

Contributions. Our contributions can be summarized as the following: (1) We propose SGAS, a greedy approach for neural architecture search with high correlation between the validation accuracy during the search phase and the final evaluation accuracy. (2) Our method discovers top-performing architectures with much less search cost than previous state-of-the-art methods such as DARTS. (3) Our proposed method is able to search architectures for both CNNs and GCNs across various datasets and tasks.

Related Work

In the past, considerable success was achieved with hand-crafted architectures. One of the earliest successful architectures was LeNet , a very simple convolutional neural network for optical character recognition. Other prominent networks include AlexNet , VGG and GoogLeNet which revolutionized computer vision by outperforming all previous approaches in the ImageNet challenge by a large margin. ResNet and DenseNet were further milestones in architecture design. They showed the importance of residual and dense connections for designing very deep networks, an insight that influences modern architecture design to this day. Until recently, architecture innovations were a result of human insight and experimentation. The first successful attempts for architecture search were using reinforcement learning and evolutionary algorithms . These works were extended with NASNet where a new cell-based search space and regularization technique were proposed. Another extension, ENAS , represents the entire search space as a single directed acyclic graph. A controller discovers architectures by searching for subgraphs that maximize the expected reward on the validation set. This setup allows for parameter sharing between child models making search very efficient. Further, PNAS introduced a sequential model-based optimization (SMBO) strategy in order to search for structures of increasing complexity. PNAS needs to evaluate $5$ times less models and reduces the computational cost by a factor of $8$ compared to NASNet. Yet, PNAS still requires thousands of GPU hours. One shot approaches further reduce the search time by training a single over-parameterized network with inherited/shared weights. In order to search in a continuous domain , DARTS proposes a continuous relaxation of the architecture representation, making architecture search differentiable and hence much more efficient. As a result, DARTS is able to find good convolutional architectures at a fraction of the computational cost making NAS broadly accessible. Owed to the large success of DARTS, several extensions have been proposed recently. SNAS optimizes parameters of a joint distribution for the search space in a cell. The authors propose a search gradient which optimizes the same objective as RL-based NAS, but leads to more efficient structural decisions. P-DARTS attempts to overcome the depth gap issue between search and evaluation. This is accomplished by increasing the depth of searched architectures gradually during the training procedure. PC-DARTS leverages the redundancy in network space and only samples a subset of channels in super-net during search to reduce computation.

Methodology

By reducing the search problem to searching for the best cell structure, cell-based NAS methods are able to learn scalable and transferable architectures. The networks are composed of layers with identical cell structure but different weights. A cell is usually represented as a directed acyclic graph (DAG) with $N$ nodes including two input nodes, several intermediate nodes and a single output node. Each node is a latent representation denoted as $x^{(i)}$, where $i$ is its topological order in the DAG. Each directed edge $(i,j)$ in the DAG is associated with an operation $o^{(i,j)}$ that transfers the information from node $x^{(i)}$ to node $x^{(j)}$. In Differentiable Architecture Search (DARTS) and its variants , the optimal architecture is derived from a discrete search space by relaxing the selection of operations to a continuous optimization problem. During the search phase, the operation of each edge is parameterized by architectural parameters $\alpha^{(i,j)}$ as a softmax mixture over all the possible operations within the operation space $\mathcal{O}$, i.e. $\bar{o}^{(i,j)}(x^{(i)})=\sum_{o\in\mathcal{O}}\frac{\exp(\alpha_{o}^{(i,j)})}{\sum_{o^{\prime}\in\mathcal{O}}\exp(\alpha_{o^{\prime}}^{(i,j)})}o(x^{(i)})$. The input nodes are represented by the outputs from the previous two cells. Each intermediate node aggregates information flows from all of its predecessors, $x^{(j)}=\sum_{i<j}\bar{o}^{(i,j)}(x^{(i)})$. The output node is defined as a concatenation of a fixed number of its predecessors. The learning procedure of architectural parameters involves a bi-level optimization problem:

2 Search-Evaluation Correlation

A popular pipeline of existing NAS algorithms includes two stages: a search phase and an evaluation phase. In order to reduce computational overhead, previous works first search over a pre-defined search space with a lightweight proxy model on a small proxy dataset. After the best architecture cell/encoding is obtained, the final architecture is built and trained from scratch on the target dataset. This requires that the true performance during evaluation can be inferred during the search phase. However, this assumption usually does not hold due to the discrepancy in dataset, hyper-parameters and network architectures between the search and evaluation phases. The best ranking derived from the search phase does not imply the actual ranking in the final evaluation. In practice, the correlation between the performances of derived architectures during the search and evaluation phases is usually low. In this paper, we refer to this issue as degenerate search-evaluation correlation. Recent work by Sciuto et al. also analyzes this issue and suggests that the Kendall $\tau$ metric could be used to evaluate the search phase. They show that the widely used weight sharing technique actually decreases the correlation. The Kendall $\tau$ metric is a common measurement of the correlation between two rankings. The Kendall $\tau$ coefficient can be computed as $\tau=\frac{N_{c}-N_{d}}{\frac{1}{2}n(n-1)}$, where $N_{c}$ and $N_{d}$ are the number of concordant pairs and the number of discordant pairs respectively. It is a number in the range from $-1$ to $1$ where $-1$ corresponds to a perfect negative correlation and $1$ to a perfect positive correlation. If the Kendall $\tau$ coefficient is , the rankings are completely independent. An ideal NAS method should have a high search-evaluation Kendall $\tau$ coefficient. We take DARTS as an example and show its Kendall $\tau$ in Figure 1. It is calculated between the rankings during search phase and evaluation phase. The rankings are determined according to the validation accuracy and the final evaluation accuracy after 10 different runs on the CIFAR-10 dataset. The Kendall $\tau$ coefficients for DARTS are only $0.16$ and $-0.29$ for the $1$st-order and $2$nd-order versions respectively. Therefore, it is impossible to make reliable predictions regarding the final test accuracy based on the search phase.

3 Sequential Greedy Architecture Search

Edge Importance. Similar to DARTS , a zero operation is included in the search space to indicate a lack of connection. Edges that are important should have a low weight in the zero operation. Thus, the edge importance is defined as the summation of weights over non-zero operations:

Selection Certainty. Entropy is a common measurement of uncertainty of a distribution. The normalized softmax weights of non-zero operations can be regarded as a distribution, $p_{o}^{(i,j)}=\frac{\exp(\alpha_{o}^{(i,j)})}{S_{EI}^{(i,j)}\sum_{o^{\prime}\in\mathcal{O}}\exp(\alpha_{o^{\prime}}^{(i,j)})},o\in\mathcal{O},o\neq zero$. We define the selection certainty as the complement of the normalized entropy of the operation distribution:

Selection Stability. In order to incorporate the history information, we measure the movement of the operation distribution. Kullback–Leibler divergence and histogram intersection are two popular methods to detect changes in distribution. For simplicity, we choose the latter one. The average selection stability at step $T$ with a history window size $K$ is computed as follows:

In our experiments, we consider the following two criteria:

Criterion 1. An edge $(i^{\dagger},j^{\dagger})$ with a high edge importance $S_{EI}^{(i,j)}$ and a high selection certainty $S_{SC}^{(i,j)}$ will be selected. We normalize $S_{EI}^{(i,j)}$ and $S_{SC}^{(i,j)}$, compute the final score and pick the edge with the highest score:

Criterion 2. In addition to Criterion 1, we also consider that the selected edge $(i^{\dagger},j^{\dagger})$ should have a high selection stability. The final score is defined as follows:

where $normalize(\cdot)$ denotes a standard Min-Max scaling normalization. For a fair comparison with existing works , two incoming edges are preserved for every intermediate node in the DAG. Once a node has two determined incoming edges, its other incoming edges will be pruned. We refer to our method as Sequential Greedy Architecture Search (SGAS). Figure 1 shows that SGAS with Criterion $1$ and $2$ improves the Kendall $\tau$ correlation coefficients to $0.56$ and $0.42$ respectively. As expected from the much higher search-evaluation correlation SGAS outperform DARTS in terms of average accuracy significantly.

Experiments

We use our SGAS to automatically find architectures for both CNNs and GCNs. The CNN architectures discovered by SGAS outperform the state-of-the-art (SOTA) in image classification on CIFAR-10 and ImageNet . Similarly, the discovered GCN architectures outperform the state-of-the-art methods for point cloud classification on ModelNet and node classification in biological graphs using the PPI dataset.

As is common practice, we first search for normal cells and reduction cells with a small network for image classification on CIFAR-$10$. CIFAR-$10$ is a small popular dataset containing $50K$ training images and $10K$ testing images. Then, a larger network is constructed by making necessary changes in channel size and stacking the searched cells multiple times. The larger network is retrained on CIFAR-$10$ to compare its performance with other state-of-the-art methods. Finally, we show the transferability of our SGAS by stacking even more cells and evaluating on ImageNet. We show that SGAS consistently achieves the top performance.

Search Space. We keep our search space the same as DARTS, which has $8$ candidate operations: skip-connect, max-pool-3$\times$3, avg-pool-3$\times$3, sep-conv-3$\times$3, sep-conv-5$\times$5, dil-conv-3$\times$3, dil-conv-5$\times$5, zero. During the search phase, we stack $6$ normal cells and $2$ reduction cells to form a network. Two reduction cells are inserted at a network depth of $1/3$ and $2/3$ respectively. The stride of each convolution in normal cells is $1$, so the spatial size of an input feature map does not change. In reduction cells, convolutions with stride $2$ are used to reduce the spatial resolution of feature maps. There are $7$ nodes with $4$ intermediate nodes and $14$ edges in each cell during search. The first and second input nodes of the cell are set equal to the outputs of the two previous cells respectively. The output node of a cell is the depth-wise concatenation of all the intermediate nodes.

Training Settings. We keep the training setting the same as in DARTS . A small network consisting of $6$ normal cells and $2$ reduction cells with an initial channel size $16$ is trained on CIFAR-$10$. We perform architecture search for $50$ epochs with a batch size of $64$. SGD is used to optimize the model weights $\mathcal{W}$ with an initial learning rate $0.025$, momentum $0.9$ and weight decay $3\times 10^{-4}$. For architecture parameters $\mathcal{A}$, the Adam optimizer with an initial learning rate $3\times 10^{-4}$, momentum $(0.5,0.999)$ and weight decay $10^{-3}$ is used. Instead of training the entire super-net throughout the search phase, SGAS makes decisions sequentially in a greedy fashion. After warming up for $9$ epochs, SGAS begins to select one operation for one selected edge every $5$ epochs using Criterion 1 or Criterion 2 as the selection criterion. For Criterion 2, we set the history window size $K$ to 4. The batch size is increased by $8$ after each greedy decision, which further boosts the searching efficiency of SGAS. We provide a thorough discussion and ablation study on the choices of hyper-parameters in the supplement material. The search takes only $0.25$ day ($6$ hours) on a single NVIDIA GTX 1080Ti.

1.2 Architecture Evaluation on CIFAR-10

We run $10$ independent searches to get $10$ architectures with Criterion 1 or Criterion 2, as shown in Figure 1. To highlight the stability of the search method, we evaluate the discovered architectures on CIFAR-$10$ and report the mean and standard deviation of the test accuracy across those $10$ models and the performance of the best model in Table 1. It is important to mention that other related works in Table 1 only report the mean and standard deviation for their best architecture with different runs on evaluation.

Training Settings. We train a large network of $20$ cells with a initial channel size $36$. The SGD optimizer is used during $600$ epochs with a batch size of $96$. The other hyper-parameters remain the same as the search phase. Cutout with length $16$, auxiliary towers with weight $0.4$ and path dropout with probability $0.3$ are used as in DARTS .

Evaluation Results and Analysis. We compare our results with other methods in Table 1 and report the average and best performance for both Criterion 1 and Criterion 2. We outperform our baseline DARTS by a significant margin with test errors of $2.39\%$ and $2.44\%$ respectively while only using $0.25$ day ($6$ hours) on a single NVIDIA GTX 1080Ti.

1.3 Architecture Evaluation on ImageNet

The architecture evaluation on ImageNet uses the cell architectures that we obtained after searching on CIFAR-10.

Training Settings. We choose the $3$ best performing cell architectures on CIFAR-10 for each Criterion and train them on ImageNet. For this evaluation, we build a large network with $14$ cells and $48$ initial channels and train for $250$ epochs with a batch size of $1024$. The SGD optimizer with an initial learning rate of $0.5$, a momentum of $0.9$ and a weight decay of $3\times 10^{-5}$ is used. We run these experiments on $8$ Nvidia Tesla V100 GPUs for three days.

Evaluation Results and Analysis. In Table 2 we compare our models with SOTA hand-crafted architectures (manual) and models obtained through other search methods. We apply the mobile setting for ImageNet, which has an image size of $224\times 224$ and restricts the number of multi-add operations to $600M$. Our best performing models SGAS (Cri.1 best) and SGAS (Cri.2 best) outperform all the other methods with top-1 errors $24.2\%$ and $24.1\%$ respectively while using only a search cost of $0.25$ GPU day on one NVIDIA GTX 1080Ti. SGAS (Cri.2) outperforms SGAS (Cri.1) showing the effectiveness of integrating selection stability into the selection criterion. The best performing cells of SGAS (Cri.2 best) are illustrated in Figure 3.

2 Searching GCN architectures with SGAS

Recently, GCNs have achieved impressive performance on point cloud segmentation , biological graph node classification and video recognition by training DeepGCNs . However, this hand-crafted architecture design requires adequate effort by an human expert. The main component of DeepGCNs is the GCN backbone. We explore an automatic way to design the GCN backbone using SGAS. Our backbone network is formed by stacking the graph convolutional cell discovered by SGAS. Our GCN cell consists of 6 nodes. We use fixed $1\times 1$ convolutions in the first two nodes, and set the input to them equal to the output from the previous two layers. Our experiments on GCNs have two stages. First, we apply SGAS to search for the graph convolutional cell using a small dataset and obtain $10$ architectures from $10$ runs. Then, $10$ larger networks are constructed by stacking each discovered cell multiple times. The larger networks are trained on the same dataset or a larger one to evaluate their performance. We report the best and average performance of these $10$ architectures. We show the effectiveness of SGAS in GCN architecture search by comparisons with SOTA hand-crafted methods and Random Search.

ModelNet is a dataset for 3D object classification with two variants, ModelNet10 and ModelNet40 containing objects from $10$ and $40$ classes respectively. We conduct GCN architecture search on ModelNet10 and then evaluate the final performance on ModelNet40.

Search Space. Our graph convolutional cell has $10$ candidate operations: conv-1$\times$1, MRConv , EdgeConv , GAT , SemiGCN , GIN , SAGE , RelSAGE, skip-connect, and zero operation. Please refer to our supplement material for more details of these GCN operators. We use k nearest neighbor in the first operation of each cell to construct edges (we use $k=9$ by default unless it is specified). These edges are then shared in the following operations inside the cell. Dilated graph convolutions with the same linearly increasing dilation rate schedule as proposed in DeepGCNs are applied to the cells.

Training Settings. We sample $1024$ points from the 3D models in ModelNet10. We use $2$ cells with $32$ initial channels and search the architectures for $50$ epochs with batch size $28$. SGD is used to optimize the model weights with initial learning rate $0.005$, momentum $0.9$ and weight decay $3\times 10^{-4}$. The Adam optimizer with the same parameters as in the search for CNNs is used to optimize architecture parameters. After warming up for $9$ epochs, SGAS begins to select one operation for a selected edge every $7$ epochs. We experimented with both selection criteria, Criterion 1 and Criterion 2. We use a history window of $4$ for Cri.2. The batch size increases by $4$ after each decision. The search takes around $0.19$ GPU day on one NVIDIA GTX 1080Ti.

2.2 Architecture Evaluation on ModelNet40

After searching for $10$ architectures on ModelNet10, we form a large backbone network for each and train them on ModelNet40. The performance of 3D point cloud classification is evaluated with the overall accuracy (OA). We also apply Random Search to the same search space to obtain $10$ architectures as our random search baseline.

Training Settings. We stack the searched cell $9$ times with channel size $128$. We also form small networks by stacking the cell $3$ times with the same channel size. We use $k=20$ for all the large networks and $k=9$ for the small ones. Adam is used to optimize the weights with initial learning rate $0.001$ and weight decay $1\times 10^{-4}$. We sample $1024$ points as input. Our architectures are all trained for $400$ epochs with batch size of $32$. We report the mean and standard deviation of the accuracy on the test dataset of the $10$ discovered architectures; we also report the accuracy of the best performing model of the big and the small networks.

Evaluation Results and Analysis. We compare the performance of our discovered architectures with SOTA hand-crafted methods and architectures obtained by Random Search for 3D point clouds classification on ModelNet40. Table 3 shows that SGAS (Cri.2 best), the best architecture discovered by our SGAS with Criterion 2, outperforms all the other models. The smaller network SGAS (Cri.2 small best) discovered by SGAS with Criterion 2 also outperforms all the hand-crafted architectures. Owing to a well-designed search space, Random Search is a strong baseline. The performance of SGAS surpasses the hand-crafted architectures and Random Search, demonstrating the effectiveness of SGAS for GCN architecture search. The best architecture for this task can be found in Figure 4 (a).

2.3 Architecture Search on PPI

PPI is a popular biological graph dataset in the data mining domain. We search for GCN architectures on the PPI dataset for the task of node classification.

Training Settings. We use $1$ cell with $32$ channels. We train and search the architectures for $50$ epochs with a batch size of $6$ on PPI. We do not increase the batch size after making decisions since PPI is small and only contains $20$ batches. The other parameters are the same as when searching on ModelNet10. The search takes around $0.003$ day ($4$ minutes) on a Nvidia Tesla V100 GPU (16GB).

2.4 Architecture Evaluation on PPI

We evaluate architectures on the PPI test set. We report the mean, standard derivation and the best accuracy and compare them with the SOTA methods and Random Search. We also conduct an ablation study on number of cells and channel size which we include in the supplement material.

Training Settings. We stack the discovered cell $5$ times with channel size 512. Adam is used to optimize the model weights with initial learning rate $0.002$. We use a cosine annealing to schedule the learning rate. Our architectures are trained for $2000$ epochs with batch size of $1$ as suggested in DeepGCNs . We find the best model on the validation dataset and obtain the micro-F1 score on the test dataset.

Evaluation Results and Analysis. We compare the average and best performance of SGAS to other state-of-the-arts methods and Random Search on node classification on the PPI dataset. Table 4 shows the best architecture discovered by our SGAS outperforms the state-of-the-art DenseMRGCN-14 by $\sim$0.03% with $\sim$30.24 M less parameters. The average performance of SGAS also surpasses the Random Search baseline consistently. In addition, SGAS (Cri.2 avg.) outperforms SGAS (Cri.1 avg.) in terms of both mean and standard deviation. This indicates that Criterion 2 provides more stable results. We visualize the architecture with the best performance in Figure 4 (b).

Conclusion

In this work, we propose the Sequential Greedy Architectural Search (SGAS) algorithm to design architectures automatically for CNNs and GCNs. The bi-level optimization problem in NAS is solved in a greedy fashion using heuristic criteria which take the edge importance, the selection certainty and the selection stability into consideration. Such an approach alleviates the effect of the degenerate search-evaluation correlation problem and reflects the true ranking of architectures. As a result, architectures discovered by SGAS achieve state-of-the-art performance on CIFAR-10, ImageNet, ModelNet and PPI datasets.

Acknowledgments. This work was supported by the King Abdullah University of Science and Technology (KAUST) Office of Sponsored Research (OSR) through VCC funding. The authors thank the KAUST IBEX team for helping to optimize the training workloads on ImageNet.

References

Appendix A Discussion

The idea of incorporating greedy algorithms into NAS has been explored in several works. PNAS proposes a sequential model-based optimization (SMBO) approach to accelerate the search for CNN architectures. They start from a simple search space and a learn a predictor function. Then they greedily grow the search space by predicting scores of candidates cells using the learned predictor function. GNAS learns a global tree-like architecture for multi-attribute learning by iteratively updating layer-wise local architectures in a greedy manner. P-DARTS can also be regarded as a greedy approach, in which they bridge the depth gap between search and evaluation by gradually increasing the depth of the search networks while shrinking the number of candidate operations.

A.2 Selection Criteria and Hyper-parameters

Edge Importance and Selection Certainty. Edge importance and selection certainty are combined into a single criterion, since the algorithm will be agnostic to the selection distribution of an edge, if we only consider edge importance. In this case, an edge may be selected with a sub-optimal operation at early epochs. On the other hand, we need to select $8$ out of $14$ edges in a DAG with $4$ intermediate nodes for a fair comparison with DARTS. Only considering selection certainty may fail to select the optimal $8$ edges, since an edge with a high selection certainty may have a high weight on Zero operation (low edge importance).

Choices of Hyper-parameters. Three extra parameters are introduced in SGAS: (1) length of warm-up phase (2) interval of greedy decisions (3) history window size for Cri.2. We provide a discussion on the default choices of them:

(1) Since the softmax weights of operations are initialized under a uniform distribution, choosing an operation for an edge after a short period of warming up leads to stable results. We simply set the length of the warm-up phase to 9 epochs so that the first greedy decision will be made at the $10$th epoch. (2) For CNN experiments, the interval between greedy decisions is chosen to be $5$. Since designing a normal cell with $4$ intermediate nodes needs to select $8$ out of $14$ edges ($8$ decisions to be made). For a fair comparison to our baseline DARTS, we want the search phase to last up to $50$ epochs, which is the length of search epochs in DARTS. For GCN architectures, in order to learn a compact network, we search a normal cell with $3$ intermediate nodes. Thus, we have $6$ decisions to make ($6$ out of $9$ edges). Similarly, to keep the length of the search phase less than 50 epochs, we set the interval between greedy decisions to be $7$. (3) The history window size for Cri.2 is always set as $4$, which is simply chosen to be slightly smaller than the interval between greedy decisions.

Ablation Study on Hyper-parameters. In order to better understand the effects of the choices of hyper-parameters, we conduct ablation studies on interval of greedy decisions $T$ and history window size $K$ for Cri.2 on CIFAR-$10$ in Table 5. The default values of $T$ and $K$ are $5$ and $4$ respectively. We find that larger $T$ and $K$ stabilize the search and produce standard deviations in the test error. The test error only has a standard deviation as $0.08$ when $T=7$. When $T=3$, the average test error increases significantly from $2.67\%$ to $2.86\%$. We also find $K$ is less sensitive than $T$.

Appendix B Experimental Details

GCN operators. Similar as the search for CNN, SGAS selects one operation from a candidate operation search space for each edge in the DAG. We choose the following $10$ operations as our candidate operations: conv-1$\times$1, MRConv , EdgeConv , GAT , SemiGCN , GIN , SAGE , RelSAGE, skip-connect, and zero operation. conv-1$\times$1 is a basic convolution operation without aggregating information from neighbors, which is similar to PointNet . MRConv , EdgeConv , GAT , SemiGCN , GIN and SAGE are widely used GCN operators in the graph learning domain and the 3D computer vision domain. RelSAGE is a modified GraphSAGE (SAGE) which combines the ideas from MRConv and GraphSAGE . Instead of aggregating the node features with its neighbor features directly, we aggregate the node features with the difference between the node features and its neighbor features:

$\mathbf{h}_{v}^{(k)}=\sigma\left(\mathbf{W}^{(k)}\cdot f_{k}\left(\mathbf{h}_{v}^{(k-1)},\left\{\mathbf{h}_{u}^{(k-1)}-\mathbf{h}_{v}^{(k-1)},\forall u\in\mathcal{N}(v)\right\}\right)\right)$

where $\mathbf{h}_{v}^{(k)}$ is the feature of the center node $v$ in $k$-th layer. $\mathcal{N}(v)$ denotes the neighbors of node $v$. $f_{k}$ is a max aggregation function and $\sigma$ is a ReLU activation function as GraphSAGE . The GCNs operators are implemented using Pytorch Geometric . We also add skip-connect (similar as residual graph connections ) and zero operation in our search space.

Ablation Study on GCN Cells. We conduct an ablation study on the parameter size of the best cell searched on PPI by SGAS (Cri.1 best). Table 6 shows the trade-off between the parameter size and the final performance. To derive a compact model, we can use a smaller number of cells or less channels in the architecture searched by SGAS.

B.2 More Details

Cell Visualizations. We visualize the best cells discovered by SGAS with different criteria (Criterion 1 and Criterion 2) mentioned in the experiment section. Figure 5 shows the best cells for CNNs on CIFAR-$10$ and ImageNet. Figure 6 shows the best cells for GCNs on ModelNet-$40$ and PPI.

Detailed results. Here we provide the detailed results mentioned in the experimental section of the paper. In the CNN experiments, we compare SGAS with DARTS on CIFAR-$10$ and ImageNet. We execute the search phase $10$ times for both SGAS (Cri.1 and Cri.2) and DARTS (1st and 2nd order) to obtain $10$ different architectures per method. For each resulting architecture, we run the evaluation phase and assign a ranking based on the evaluation accuracy. To measure the discrepancy between the search and evaluation, we calculate the Kendall $\tau$ correlation between the ranking of the search phase and the evaluation phase. We show these results in Table 7 and Table 8 for SGAS, and Table 9 and Table 10 for DARTS. For ImageNet, we evaluate the top three architectures found on CIFAR-$10$. We show the results in Table 11 and Table 12 for both Criterion 1 and Criterion 2.

In the GCN experiments, we compare SGAS (Cri.1 and Cri.2) with a random search baseline on ModelNet and PPI. Similar as in experiments for CNNs, we conduct the search phase $10$ times for each method. For experiments on ModelNet, we search cells on ModelNet10 and then evaluate the searched cells on ModelNet40. The results are shown for Criterion 1, Criterion 2 and random search in Table 13, Table 14 and Table 15 respectively. The results on PPI are presented in Table 16 and Table 17 for each Criterion and in Table 18 for random search.