Searching for Stage-wise Neural Graphs In the Limit

Xin Zhou, Dejing Dou, Boyang LiarXiv 2019 · arXiv

Abstract

Neural Architecture Search (NAS) traditionally focuses on micro-structures (cells) while neglecting the macro-scale connectivity of the network. This paper introduces graphons—the mathematical limits of graph sequences—as a continuous and scale-free search space for macro-structures. By searching for a graphon rather than a discrete graph, we can discover high-performing "stage-wise" network styles on small datasets and mathematically scale them to massive architectures. Our "NAS Graphon" models consistently outperform manually designed structures like DenseNet and random graph models on ImageNet and ImageNet V2.

Introduction

Most Neural Architecture Search (NAS) research focuses on finding a small, complex "cell" and then stacking it repeatedly to build a network. While effective, this ignores the "macro" structure of the network—how these cells are connected across different stages and resolutions.

Searching for the macro-structure is difficult because of the computational explosion at scale (e.g., stages with 60+ nodes) and the lack of linear transferability between small and large models. Existing work suggested that random graph distributions (like Watts-Strogatz) perform well, hinting that we should search for distributions of graphs. This paper takes that idea to its mathematical limit using graphons.

Methods: Searching in the Limit

What is a Graphon?

Mathematically, a graphon is a symmetric function that represents the limit of a sequence of graphs as the number of nodes goes to infinity. Practically, it acts as a "probability map" for connections that is independent of the number of nodes. For any two nodes $i$ and $j$ in a graph of size $n$, the probability of an edge existing between them is determined by sampling the graphon at coordinates $(i/n, j/n)$.

Figure 6: Graphons for Erdős-Rényi (left) and Watts-Strogatz (right) models, representing connection probability maps.

As shown in Figure 6, standard random graph models have distinct graphon representations. By searching for the optimal underlying function $W$ rather than a specific graph $G$, the search space becomes continuous and more expressive than standard random graph models.

Scaling via Blow-ups

Because graphons are scale-free, they provide a natural mechanism for scaling architectures. The authors utilize "k-fold blow-up" and "fractional blow-up" techniques to expand a small searched graph (e.g., 11 nodes) into a large-scale architecture (e.g., 64 nodes or more) while maintaining structural properties measured by "cut-distance."

Figure 5: An adjacency matrix for a graph with n=1000 nodes sampled from a graphon, illustrating the convergence to a continuous limit.

As the number of nodes $n$ increases, the discrete adjacency matrix (as seen in Figure 5) increasingly resembles the underlying continuous graphon. This allows a network "style" discovered on a small dataset like CIFAR-10 to be reliably expanded for large-scale tasks like ImageNet.

The Search Algorithm

The authors use a differentiable approach, assigning weights to different input combinations and using the Gumbel-softmax trick to optimize connections via gradient descent. To find the final "graphon," they average the adjacency matrices visited during the final phase of training, treating the SGD process as a Markov chain sampling from the optimal distribution.

Key Results

The authors compared their "NAS Graphon" models against DenseNet and randomly wired Watts-Strogatz (WS) graphs across four parameter scales:

  • Performance: In every category (equivalent to DenseNet-121, 169, 201, and 264), the NAS Graphon achieved the highest Top-1 accuracy on ImageNet.
  • Efficiency: At the smallest scale, NAS Graphon achieved 75.47% Top-1 accuracy with 7.94M parameters, outperforming the standard DenseNet-121 (75.39% with 7.98M parameters).
  • Consistency: The performance gap was even more noticeable on ImageNet V2, where the NAS Graphon models showed superior generalization (up to 0.8% improvement over DenseNet).

Discussion and Future Work

The results show that these "graphon-sampled" networks often outperform manually designed structures like DenseNet, suggesting that optimal layer connectivity is more complex than simple sequential or all-to-all patterns. Because a graphon is a limit object, a network's "style" can be preserved regardless of depth.

However, limitations remain. This paper focuses purely on the wiring (the graph) using standard DenseNet-style operations. A complete NAS would search for both wiring and operations simultaneously. Additionally, incorporating weight-sharing (like in ENAS or DARTS) could speed up the search process, and exploring "digraphons" could allow for more complex directed acyclic graph (DAG) structures.

Summary updated

Abstract

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.
BibTeX
@misc{zhou2019searching,
  author = {Xin Zhou and Dejing Dou and Boyang Li},
  title = {{Searching for Stage-wise Neural Graphs In the Limit}},
  year = {2019},
  eprint = {1912.12860},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1912.12860},
}
Figure