  Search space is a key consideration for neural architecture search. Recently,
Xie et al. (2019) found that randomly generated networks from the same
distribution perform similarly, which suggests 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 nodes can
be drawn. By utilizing properties of the graphon space and the associated
cut-distance metric, we develop theoretically motivated techniques that search
for and scale up small-capacity stage-wise graphs found on small datasets to
large-capacity graphs that can handle ImageNet. The scaled stage-wise graphs
outperform DenseNet and randomly wired Watts-Strogatz networks, indicating the
benefits of graphon theory in NAS applications.
