Search space is a key consideration for neural architecture search. Recently, Xie et al. (2019a) found that randomly generated networks from the same distribution perform similarly, which suggest we should search for random graph distributions instead of graphs. We propose graphon as a new search space. A graphon is the limit of Cauchy sequence of graphs and a scale-free probabilistic distribution, from which graphs of different number of vertices can be drawn. This property enables us to perform NAS using fast, low-capacity models and scale the found models up when necessary. We develop an algorithm for NAS in the space of graphons and empirically demonstrate that it can find stage-wise graphs that outperform DenseNet and other baselines on ImageNet. Neural architecture search (NAS) aims to automate the discovery of neural architectures with high performance and low cost. Of primary concern to NAS is the design of the search space [23] , which needs to balance multiple considerations. For instance, too small a space would exclude many good solutions, whereas a space that is too large would be prohibitively expensive to search through. An ideal space should have a one-to-one mapping to solutions and sufficiently smooth in order to accelerate the search. A common technique [37, 17, 35, 19, 24, 34] to keep the search space manageable is to search for a small cell structure, typically containing about 10 operations with 1-2 input sources each. When needed, identical cells are stacked to form a large network. This technique allows cells found on, for instance, CIFAR-10 to work on ImageNet. Though this practice is effective, it cannot be used to optimize the overall network structure. In both manual and automatic network design, the overall network structure is commonly divided into several stages, where one stage operates on one spatial resolution and contains several nearidentical layers or multi-layer structures (i.e., cells). For example, ResNet-34 [11] contains 4 stages with 6, 8, 12 , and 6 convolutional layers, respectively. DenseNet-121 [12] contains 4 stages with 6, 12, 24, and 16 two-layer cells. AmoebaNet-A [24] has 3 stages, within each 6 cells are arranged sequentially. Among cells in the same stage, most connections are sequential with skip connections occasionally used. As an exception, DenseNet introduces connections between every pairs of cells within the same stage. Here we emphasize the difference between a stage and a cell. A cell typically contains about 10 operations, each taking input from 1-2 other operations. In comparison, a stage can contain 60 or more operations organized in repeated patterns and the connections can be arbitrary. A network usually contains only 3-4 stages but many more cells. In this paper, we focus on the network organization at the level of stage rather than cell. [32] recently showed that the stage structure can be sampled from probabilistic distributions of graphs, including Erdős-Rényi (ER) (1960), Watts-Strogatz (WS) (1998), and Barabási-Albert (BA) (1999), yielding high-performing networks with low in-group variance. This finding suggests the random graph distribution, rather than the exact graph, is the main causal factor behind network performance. Thus, searching for the graph is likely not as efficient as searching for the random (c) m0 = m = 100, n = 1000 Figure 1 : Three adjacency matrices of graphs generated by the Barabási-Albert model with m = m 0 = 0.1n. A black dot at location (i, j) denotes an edge from node i to node j. The sequence of matrices converges to its limit, the graphon, as n → ∞. Figure 2: Graphons for common random graph models. Different shades denote different probabilities (e.g., p and 1 − p). The Erdős-Rényi model has two parameters: number of nodes n and probability p. The Watts-Strogatz (WS) model has three parameters: number of nodes n, replacement probability p, and initial neighborhood width k. Technically, the WS model has a constant number of edges, violating exchangeability for random graphs; graphs sampled from (b) converges in probability to the same number of edges as n increases. graph distribution. The parameter space of random graph distributions may appear to be a good search space. We propose a different search space, the space of graphons [20] , and argue for its superiority as an NAS search space. Formally introduced in Section 3, a graphon is a measurable function defined on [0, 1] 2 → [0, 1] and a probabilistic distribution from which graphs can be drawn. Graphons are limit objects of Cauchy sequences of finite graphs under the cut distance metric. Figure 1 visualizes three adjacency matrices randomly generated by the Barabási-Albert (BA) model with increasing numbers of nodes. It is easy to see that, as the number of nodes increases, the sequence of random graphs converges to its limit, a graphon. The BA model starts with an initial seed graph with m 0 nodes and arbitrary interconnections. Here we choose a complete graph as the seed. It sequentially adds new nodes until there are n nodes in the graph. For every new node v new , m edges are added, with the probability of adding an edge between v new and the node v i being proportional to the degree of v i . In Figure 1 , we let m = m 0 = 0.1n. The fact that different parameterization results in the same adjacency matrix suggests that directly searching in the parameter space will revisit the same configuration and is less efficient than searching in the graphon space. Additionally, graphon provides a unified and more expressive space than common random graph models. Figure 2 illustrates the graphons for the WS and the ER models. We can observe that these random models only capture a small proportion of all possible graphons. The graphon space allows new possibilities such as interpolation or striped combination of different random graph models. Finally, graphon is scale-free, so we should be able to sample an arbitrary-sized stage-wise architecture with identical layers (or cells) from a graphon. This allows us to perform expensive NAS on small datasets (e.g., CIFAR-10) using low-capacity models and obtain large stage-wise graphs to build large models. By relating graphon theory to NAS, we provide theoretically motivated techniques that scale up stage-wise graphs, which are shown to be effective in practice. Our experiments aim to fairly compare the stage-wise graphs found by our method against DenseNet and the WS random graph model by keeping other network structures and other hyperparameters constant. The results indicate that the graphs found outperform the baselines consistently across a range of model capacities. The contribution of this paper revolves around building a solid connection between theory and practice. More specifically, • We propose graphon, a generalization of random graphs, as a search space for stage-wise neural architecture that consists of connections among mostly identical units. • We develop an operationalization of the theory on graphon in the representation, scaling and search of neural stage-wise graphs that perform well in fair comparisons. We attribute the performance differences to the stage-wise graphs, since we have strictly applied the same setting, including the global network structure, the cell structure, and hyperparameter settings. The first conclusion we draw is the effectiveness of the theoretically motivated scaling technique for graphon. We scaled up the 11-node graph found by the search to graphs with up to 64 nodes in the experiments. We also scaled the WS(4, 0.25) network, initially defined for 32 nodes in [32] , to 64 nodes in the DenseNet-264 group. The experiments show that after scaling, the relative rankings of these methods are maintained, suggesting that the proposed scaling technique incurs no performance loss. Second, we observe the standard deviations for most methods are low, even though they edge a bit higher for ImageNet V2 where model selection has been carried out. This is consistent with the findings of [32] and reaffirms that searching for random graphs is a valid approach for NAS. Finally, we emphasize that these results are created for the purpose of fair comparisons and not for showcasing the best possible performance. Our goal is to show that the graphon space and the associated cut distance metric provide a feasible approach for NAS and the empirical evidences support our argument. The design of search space is of paramount importance for neural architecture search. Recent work [32] suggests that searching for random graph distributions is an effective strategy for the organization of layers within one stage. Inspired by mathematical theories on graph limits, we propose a new search space based on graphons, which are the limits of Cauchy sequences of graphs based on the cut distance metric. The contribution of this paper is the operationalization of the graphon theory as practical NAS solutions. First, we intuitively explain why graphon is a superior search space than the parameter space of random graph models such as the Erdős-Rényi model. Furthermore, we propose a technique for scaling up random graphs found by NAS to arbitrary size and present a theoretical analysis under the cut distance metric associated with graphon. Finally, we describe an operational algorithm that finds stage-wise graphs that outperform manually designed DenseNet as well as randomly wired architectures in [32] . Although we find neural architectures with good performance, we remind the reader that absolute performance is not the goal of this paper. Future work involves expanding the work to different operators in the same stage graph. This can be achieved, for example, in the same manner that digraphon accommodates different types of connections. We contend that the results achieved in this paper should not be considered an upper bound, but only the beginning, of what can be achieved. We believe this work opens the door toward advanced NAS algorithms in the space of graphon and the cut distance metric. A The DenseNet network contains a stem network before the first stage, which contains a 3 × 3 convolution, batch normalization, ReLU and max-pooling. This is followed by three stages for CIFAR-10 and four stages for ImageNet. Between every two stages, there is a transition block containing a 1×1 convolution for channel reduction and a 2 × 2 average pool with stride 2 for downsampling. The network ends with a 7 × 7 global average pooling and a linear layer before a softmax. Figure 4 shows the cell structure for DenseNet, which contains two convolutions with different kernel size: 1 × 1 and 3 × 3. Each of the two convolutions are immediately preceded by a batch normalization and ReLU. Every cell in the same stage outputs c channels. The input to the n th cell is the concatenation of outputs from the cell 1 to cell n − 1, for a total of c(n − 1) channels. As every cell increments the number of input channels by c, it is called the growth rate. Theorem 5 shows the k-fold blow-up method is a better approximation of the original graph in terms of the cut distance δ than the 1D linear interpolation. But the exact k-fold blow-up is only applicable when k is an integer. If a graph of size n + m(0 < m < n) is desired, we need to resort to the fractional blow-up method, which has been analyzed in Theorems 3 and 4. We show that when m is 1 or n − 1, this partial blowup operation does not cause δ to change more than O(β ∆ /n). However, when m is n/2, δ between the original graph and the new graph could be up to β ∆ /6. This suggests that the fractional upsampling results in a graph that is similar to the original when only a small number of nodes (relative to n) is added.
Graphon is a good search space for neural architecture search and empirically produces good networks.
{"src": "scitldr-AIC_train", "paper_id": "SkxWnkStvS"}