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)$.
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."
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