SGAS: Sequential Greedy Architecture Search

Guohao Li; Guocheng Qian; Itzel C. Delgadillo; Matthias Müller; Ali Thabet; Bernard Ghanem

Source-linked AI summary

SGAS: Sequential Greedy Architecture Search

Guohao Li, Guocheng Qian, Itzel C. Delgadillo, Matthias Müller, Ali Thabet, Bernard Ghanem

arXiv:1912.00195v2Nov 30, 2019cs.LGcs.CVstat.ML

TL;DR

Neural architecture search can select architectures whose search-phase rankings do not predict final evaluation, while manual design and earlier automated methods remain costly. SGAS divides the search into greedy sub-problems, selecting and pruning operations for CNN and GCN architectures. It achieves state-of-the-art performance across CIFAR-10, ImageNet, ModelNet, and PPI datasets.

Problem
Search-phase rankings may not predict final evaluation performance because search and evaluation differ in datasets, hyper-parameters, and network architectures.
Method
SGAS solves NAS's bi-level optimization greedily using criteria based on edge importance, selection certainty, and selection stability, pruning other incoming edges after two are selected.
Results
SGAS achieves state-of-the-art performance on CIFAR-10, ImageNet, ModelNet, and PPI datasets.
Takeaways & Limitations
SGAS provides an efficient architecture-search approach that reflects architecture rankings more faithfully across CNN and GCN tasks.

Abstract

from arXiv · show

Architecture design has become a crucial component of successful deep learning. Recent progress in automatic neural architecture search (NAS) shows a lot of promise. However, discovered architectures often fail to generalize in the final evaluation. Architectures with a higher validation accuracy during the search phase may perform worse in the evaluation. Aiming to alleviate this common issue, we introduce sequential greedy architecture search (SGAS), an efficient method for neural architecture search. By dividing the search procedure into sub-problems, SGAS chooses and prunes candidate operations in a greedy fashion. We apply SGAS to search architectures for Convolutional Neural Networks (CNN) and Graph Convolutional Networks (GCN). Extensive experiments show that SGAS is able to find state-of-the-art architectures for tasks such as image classification, point cloud classification and node classification in protein-protein interaction graphs with minimal computational cost. Please visit https://www.deepgcns.org/auto/sgas for more information about SGAS.

1. Introduction

Architecture search reduces manual design effort but remains difficult because its search space is huge and search-phase validation rankings can diverge from final evaluation performance. SGAS addresses this discrepancy with an efficient greedy search approach and targets high correlation across tasks.

Meta-learning and architecture search aim to reduce manual intervention, but the architecture-search space makes manual exploration prohibitive.
Search-phase validation accuracy can diverge substantially from final test accuracy because the phases use limited architectures and differ in datasets, hyper-parameters, and network scale.
SGAS is a greedy architecture-search algorithm designed to address search–evaluation discrepancy while searching efficiently.
The method targets high search–evaluation correlation, lower search cost than DARTS, and architecture discovery for both CNNs and GCNs across varied tasks.

2. Related Work

Neural architecture design progressed from successful hand-crafted networks toward automated methods. Reinforcement-learning search achieved promising results but was computationally expensive, while DARTS made search differentiable and more efficient.

Hand-crafted architectures including LeNet, AlexNet, VGG, GoogLeNet, ResNet, and DenseNet established influential design patterns for deep networks.
DARTS introduced a continuous relaxation that made architecture search differentiable and enabled good convolutional architectures at lower computational cost.

3. Methodology

SGAS reformulates differentiable architecture search as a sequence of greedy decisions, progressively pruning operations and reducing the discrepancy between search and evaluation. It selects edges using criteria based on importance, certainty, and optionally stability, then produces a stand-alone architecture without weight sharing.

Preliminary - DARTS: Cell-based NAS represents architectures as DAGs whose directed edges transfer node information through candidate operations.Each intermediate node aggregates information from its predecessors, while the output node concatenates a fixed number of predecessor representations.
Preliminary - DARTS: DARTS derives a discrete architecture by selecting the highest-weight operation for every relaxed mixture operation.Architectural parameters are optimized with supernet weights in a bi-level optimization procedure.
Search-Evaluation Correlation: Existing NAS separates lightweight proxy-model search from final training, but search rankings often correlate poorly with evaluation rankings.The discrepancy can arise from differences in datasets, hyper-parameters, and network architectures between the two phases.
Search-Evaluation Correlation: SGAS raises search-evaluation Kendall τ from DARTS values of 0.16 and −0.29 to 0.56 and 0.42 under its two criteria.The reported coefficients correspond to the first-order and second-order DARTS versions, followed by SGAS Criterion 1 and Criterion 2, respectively, as described in the cited passages.
Sequential Greedy Architecture Search: SGAS solves the bi-level problem sequentially, selecting one edge at each decision epoch and replacing its mixture operation with a greedy operation choice.The remaining architecture parameters and weights form a smaller sub-problem that is optimized iteratively.
Sequential Greedy Architecture Search: After an edge is decided, SGAS removes its architectural parameter and prunes unchosen operations and weights, gradually reducing optimization cost.The final search output is a stand-alone architecture without weight sharing.
Sequential Greedy Architecture Search: SGAS evaluates candidate edges using edge importance and selection certainty, with a second criterion that additionally incorporates selection stability.The method preserves two incoming edges for each intermediate node and prunes the others once those edges are determined.

4. Experiments

SGAS is evaluated across CNN and GCN architecture-search tasks, using lightweight proxy searches followed by larger-network evaluation. It achieves strong results on CIFAR-10, ImageNet, ModelNet40, and PPI with low search cost and stable selection criteria.

CNN experiments: SGAS searches CNN architectures in the DARTS operation space, then transfers selected cells from small CIFAR-10 searches to larger evaluations.The CNN search uses 8 candidate operations, 6 normal cells, and 2 reduction cells; the search lasts 50 epochs and costs 0.25 GPU day.
CNN experiments: 2.39% and 2.44% test errors are reported for SGAS Criteria 1 and 2 on CIFAR-10, while using 0.25 day on one NVIDIA GTX 1080Ti.The reported comparison states that both SGAS variants outperform the DARTS baseline.
CNN experiments: 24.2% and 24.1% top-1 errors are achieved by SGAS Criterion 1 and Criterion 2 on ImageNet, outperforming the other compared methods in the mobile setting.The ImageNet models transfer the top three CIFAR-10 architectures and restrict multi-add operations to 600M.
GCN experiments: SGAS searches GCN cells on ModelNet10 and evaluates stacked larger networks on ModelNet40 using ten candidate graph-convolution operations.The ModelNet40 evaluation compares SGAS with hand-crafted architectures and Random Search within the stated search space.
GCN experiments: Criterion 2’s best ModelNet40 architecture outperforms all compared models, including hand-crafted architectures and Random Search.The smaller Criterion 2 network also outperforms the hand-crafted architectures.
GCN experiments: On PPI node classification, SGAS surpasses DenseMRGCN-14 by approximately 0.03% with approximately 30.24 M fewer parameters, while Criterion 2 provides more stable results.The average SGAS performance also consistently surpasses the Random Search baseline.

5. Conclusion

SGAS automatically designs CNN and GCN architectures by greedily solving NAS subproblems, addressing search–evaluation mismatch while achieving state-of-the-art results across several datasets.

SGAS greedily solves the bi-level NAS optimization problem using edge importance, selection certainty, and selection stability.
The method is intended to alleviate degenerate search–evaluation correlations and better reflect the true ranking of architectures.
SGAS achieves state-of-the-art performance on CIFAR-10, ImageNet, ModelNet, and PPI datasets.
The paper reports automatic architecture search for both CNNs and GCNs with substantially lower search cost than previous state-of-the-art methods such as DARTS.

A.1. Greedy Methods in NAS

Earlier NAS work incorporated greedy decisions to accelerate architecture discovery through sequential search-space growth or iterative architecture updates.

PNAS sequentially grows the CNN search space and uses a learned predictor to score candidate cells.
GNAS builds a global tree-like architecture for multi-attribute learning through iterative updates.

A.2. Selection Criteria and Hyper-parameters

SGAS combines edge importance and selection certainty, then uses warm-up, decision intervals, and history windows to control greedy decisions and stabilize search.

Selection Criteria: SGAS combines edge importance and selection certainty because either criterion alone can select suboptimal operations or fail to select enough edges.
Hyper-parameters: The method introduces warm-up length, greedy-decision interval, and Criterion 2 history-window size as additional hyper-parameters.
Hyper-parameters: For GCN architectures, the search uses 6 decisions among 9 edges and a 7-epoch interval to keep the search phase below 50 epochs.
Ablation Study: Larger decision intervals and history windows stabilize search and reduce variation in test error.
Ablation Study: Table 5 reports average and best performance for Criterion 2 across settings of greedy-decision interval T and history-window size K on CIFAR-10.

B.1. GCN Experiments

SGAS searches GCN cells from diverse graph operators and evaluates stacked architectures, with experiments examining both performance and compactness.

Search Space: The GCN search space contains 10 candidate operations, including convolution, message-passing, attention, skip-connect, and zero operations.
GCN Operators: SAGE aggregates center-node features with differences between center and neighboring features rather than directly aggregating neighbor features.
Ablation Study: Smaller numbers of cells or channels can produce more compact SGAS architectures, reflecting a trade-off between parameter size and final performance.
Ablation Study: Table 6 studies channel size and cell count for node classification on PPI using the best architecture found with Criterion 1.

B.2. More Details

This section provides visualizations and detailed experimental results for SGAS across CNN and GCN architecture-search settings. It organizes comparisons with DARTS and random search across image, point-cloud, and graph tasks.

Cell Visualizations: SGAS cell visualizations cover CNNs on CIFAR-10 and ImageNet, and GCNs on ModelNet-40 and PPI.The visualizations compare cells discovered using Criterion 1 and Criterion 2.
Detailed results: CNN experiments compare SGAS and DARTS using ten search runs per method and rank the resulting architectures by evaluation accuracy.SGAS uses Criterion 1 and Criterion 2, while DARTS uses first- and second-order variants.
Detailed results: ImageNet evaluation uses the three best architectures obtained on CIFAR-10 for each SGAS criterion.The results are reported separately for Criterion 1 and Criterion 2 in Tables 11 and 12.
Detailed results: GCN experiments compare SGAS with random search on ModelNet and PPI using ten search runs for each method.ModelNet cells are searched on ModelNet10 and evaluated on ModelNet40; results are organized by criterion and baseline tables.