Search space is a key consideration for neural architecture search. Recently, [32] 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 WattsStrogatz networks, indicating the benefits of graphon theory in NAS applications.
The authors propose a new search space based on graphons and explore some of its benefits such as certain theoretical properties. The architecture search shares similarities with DARTS. An important difference is that the network parameters are not shared.
The paper is well-written and the authors consider that the typical reader will not be familiar with graphons. I agree that their proposed model allows for more architectures but in practice it is not much stronger than WS-G. The argumentation with respect to parameters is unclear to me. On one hand, you manually influence the number of parameters, on the other you argue that you use less parameters. Obviously, you chose that your baselines have more parameters. How do results for WS-G look like if you reduce its parameters to match yours? In fact, you were searching for an architecture on CIFAR-10 but you did not report your results here. Instead you only report your transferred results to ImageNet. Is it possible that you also report results on CIFAR-10? Finally, you do not discuss that your graph contains only one kind of node. In many NAS methods the search space contains various types of operations. Do you think this is a problem? Is there a trivial way to extend your method to cover this as well?