Title: SEARCHING FOR STAGE-WISE NEURAL GRAPHS IN THE LIMIT Anonymous authors Paper under double-blind review

Abstract: 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 Watts-Strogatz networks, indicating the benefits of graphon theory in NAS applications.

1. INTRODUCTION:

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 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 → ∞. 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.

2. RELATED WORK:

We review the NAS literature with a focus on the distinction between cell and stage structures. In the pioneering work of [36] , a recurrent neural network served as the controller that outputs all network parameters for all layers without such distinction. Later works attempted to reduce the cost of search by constraining the search to cell structures only. [35] searched for a single cell structure and perform downsampling using pooling operations. [37] , [33] , and [24] searched for two types of cells: a reduction cell that includes downsampling, and a normal cell that does not. [17] grew the cell structure from the simplest 1-operation cell to the maximum of 5 operations. DARTS [19] relaxed discrete choices and enabled gradient-based optimization. [5] imposed a probabilistic formulation on DARTS.

While various manual designs of stage structures have been proposed (e.g., Huang et al. 12, Larsson et al. 16 ), NAS for stage-wise graph has received relatively little attention. [32] found that random graphs generated by properly parameterized Watts-Strogatz models outperform manual designs for stage-wise structures. [30] redefined the stage-wise graphs so that a node can take multiple inputs but output only a single channel, resulting in large stage-wise graphs with up to 2560 nodes. [27] evolved the connections between multiple residual blocks for applications in video processing. As a differennt type of global structure, [18] optimized organization of downsampling and upsampling. In summary, we believe that NAS for stage structures is an emerging research direction with many unexplored opportunities.

Another approach for accelerate search is to share weights among different architectures. [28] built a lattice where a chain-structured network is a path from the beginning to the end. In ENAS [22] , a controller is trained using gradient policy to select a subgraph, which is subsequently trained using cross-entropy. The process repeats, sharing network weights across training sessions and subgraphs.

In the one-shot approach [4, 2, 6] , the hypergraph is only trained once. After that, subgraphs are sampled from the hypergraph and evaluated. Finally, the best performing subgraph is retrained. Our focus in this paper is to validate that the mathematical theory of graphon can be effectively operationalized and leave weight sharing as future work.

3. BACKGROUND ON GRAPHON:

Definition 1. A graphon is a symmetric, measurable function

W : [0, 1] 2 → [0, 1].

The definition of graphon is straightforward, but its relation with graphs requires some standard concepts from real analysis, which we introduce below. In machine learning, graphon has found applications in hierarchical clustering [8] and graph classification [10] .

3.1. PRELIMINARIES:

A metric space is a space with a distance function. More specifically, a metric space is a set M with a metric function d : M × M → R that defines the distance between any two points in M and satisfies the following properties: (1) Identity: d(x, x) = 0. (2) Symmetry: d(x, y) = d(x, y). (3) Triangular inequality: d(x, y) ≤ d(x, z) + d(z, y). As an example, the set of real numbers R with the absolute difference metric d abs (x, y) = |x -y| is a metric space.

A Cauchy sequence is defined as a sequence (x 1 , x 2 , . . .) whose elements become infinitely close to each other as we move along the sequence. Formally, for any positive ∈ R + , there exists a positive integer N ∈ Z + such that d(x j , x i ) < , ∀i, j > N, i, j ∈ Z + .

A complete metric space is a metric space (M, d) in which every Cauchy sequence converges to a point in M. It turns out that some familiar spaces, such as rational numbers Q under the metric d abs , are not complete. As an example, the sequence defined by

x 0 = 1, x n+1 = x n /2 + 1/x n converges to an irrational number √ 2.

The space of real numbers R with d abs , however, is a complete metric space. Given any metric space, we can form its completion, in general, by adding limit points. In the case of graphs, the limits allow explicit descriptions.

3.2. GRAPHON, THE CUT DISTANCE, AND DIGRAPHON:

We consider a weighted undirected graph G = (V, E) where every v i ∈ V is associated with a node weight α i and every edge e ij ∈ E is associated with edge weight β ij . When necessary, we also write α i = α i (G) to highlight the graph the node belongs to. The weighted graph is a generalization of the simple graph, where all nodes have weight 1 and all edge have weight 1. Edges that do not exist are considered to have weight 0. [3] show the following. Theorem 1. Every Cauchy sequence of weighted graphs in the metric δ converges to a graphon. Theorem 2. An weighted graphon is the limit of some Cauchy sequence in the metric δ .

The definition of the cut distance δ relies on its discrete versions d and δ . To avoid unnecessary technical details, here we introduce the intuition of d and leave δ and δ to Appendix C. For a partition S, T of V, the cut size is defined as cut(S, T, G) = vi∈S,vj ∈T α i α j β ij . When two graphs G and G = (V , E ) have the same set of nodes (i.e. V = V ), the partition S, T applies to both graphs. We can then define

EQUATION

The seemingly counter-intuitive d is a sensible metric for random graphs. Consider two random graphs with n nodes from the same Erdős-Rényi model with edge density 1/2. As they are identically distributed, their distance should be small. However, their edit distance, or the number of edges where the two graphs differ, is likely quite large. In contrast, d is only O(1/n) with high probability, which is consistent with our intuition.

For directed graphs with the potential of self-loops, [7] define a digraphon as a 5-tuple (W 00 , W 01 , W 10 , W 11 , w). For nodes u i and u j , W 00 (i, j) describes the probability that no edge exists between them; W 01 (i, j) the probability that an edge goes from u i to u j ; W 10 (i, j) the probability that an edge goes from u j to u i , and W 11 (i, j) the probability that two edges go both ways. w i is the probability for a self-loop at u i . For all i, j, W 00 (i, j)+W 01 (i, j)+W 10 (i, j)+W 11 (i, j) = 1.

4. APPROACH:

Since the graphon is a limit object, we must approaximate it with finite means. Here we use a step function approximation. We utilize a matrix B ∈ [0, 1] n×n as the adjacency matrix of a weighted graph whose edgeweights β ij represent the mean of a 1 n × 1 n square from the graphon. Its nodeweights are uniformly 1 n . This approximation converges to the graphon when n tends to infinity (Lemma 3.2, Borgs et al. 3) . In order to represent directed acyclic graphs in neural networks, we require the adjacency matrices to be upper-triangular and has a zero vector on the diagonal. This is equivalent to imposing a total ordering ≺ on the nodes and requiring i ≺ j for a directed edge to go from v i to v j .

In the following, we propose theoretically motivated techniques for sampling stage-wise graphs of different sizes from the graphon representation and NAS for graphon.

4.1. SAMPLING FROM AND SCALING A GRAPHON:

Given a finite graph G est with edge weights β ij ∈ [0, 1] and uniform nodeweights, we can sample a simple graph G sample (i.e. with all edgeweights equal to 0 or 1) with n nodes by drawing every edge independently as a 0-1 variable from the Bernoulli distribution parameterized by β ij . [3] show G sample converges to G est in probability as the number of nodes n increases.

EQUATION

This procedure requires G est and G sample to have the same number of nodes. 

EQUATION

To handle the case when the upsampling factor is not an integer, we propose a method called fractional blow-up. Suppose we want to create a stage-wise graph with kn + m nodes. We first perform k-fold blow-up to create a new graph with kn nodes and equal nodeweight 1/kn. After that, we shift the nodeweights such that the first m nodes have nodeweights 2/(kn + m) and the rest kn -m nodes have nodeweights 1/(kn + m). We subsequently split the first m node into 2 nodes, yielding a graph of equal nodeweights. As detailed in Appendix D, the cut distance between G est and G est can be bounded by

EQUATION

where β ∆ denotes the maximum difference between any two edge weights. Since

β ij ∈ [0, 1], β ∆ ≤ 1.

From G est , we can then sample a simple graph with kn + m nodes.

It is worth noting that the proposed upscaling methods differ from conventional upsampling techniques like linear or bilinear interpolation. In Appendix D.3, we show that, under moderate conditions, the k-fold blow-up graph is strictly closer to the original graph than a graph created by interpolation.

4.2. SEARCHING FOR AN ADJACENCY MATRIX:

We now introduce the search algorithm. When optimizing discrete objects with gradient descent, the Gumbel softmax [14, 31] has been widely used. Given a multinomial distribution with probabilities π 0 , . . . , π K , we independently draw a K-dimensional vector β from a Gumbel distribution: ∀k, γ k ∼ Gumbel(0, 1). The Gumbel softmax is defined as

EQUATION

The Gumbel softmax can be understood as pitting the choices from 1 to K against each other, while the random perturbation from β enables exploration.

Our search algorithm optimizes the input connections to each node in the stage-wise graph. Empirically, we find it important to let different cells in the same stage learn to collaborate during the a node on the 0-1 lattice a state on the lattice visited by SGD the estimated graphon

Figure 3 : The intuition on the search for the optimal graphon. When searching in the space of adjacency matrices, we only can only move on the 0-1 lattice. The optimal graphon, denoted by the filled black dot, is estimated by taking the average of the states visited by SGD.

search. Therefore, we devise an algorithm that pits different input combinations against each other. Specifically, the node v i may take input from nodes v 1 , . . . , v i-1 , from which we sample K subsets. For example, for the seventh node v 7 , we could sample {v 1 , v 3 , v 5 } or {v 5 , v 6 } and so on. We assign a structural parameter π k to every input subset. Finding the adjacency matrix amounts to finding the best input subset for every node. We also assign separate model parameters to the same node in different input subsets. This allows all nodes in the same subset to learn to collaborate, which would be difficult if the parameters were shared across input subsets. The outputs of nodes in the same subset are aggregated using concatenation with zero padding for aligning the dimensions. During the search, the input to node v i is computed as the convex combination of the outputs from all K subsets, K k=1 a k out(k). For the pseudo-code of the search algorithm, the reader is referred to Appendix B.

We use cross-entropy loss and standard stochastic gradient descent (SGD) with momentum to optimize the model parameters together with subset weights π. After the search completes, We pick the input subset with the highest π k in the final adjacency matrix.

However, the goal of the search is to find a probabilistic distribution of random graphs, not a single graph. As indicated by [21] and [13] , the last phase of SGD may be considered as a Markov chain that draws samples from a stationary distribution. Figure 3 illustrates this intuition. Thus, we compute the graphon as the average of adjacency matrix found by the last phase of the search.

5. EXPERIMENTS:



5.1. SETUP:

DenseNet [12] is a classical example where the stage-wise structure plays a major role in improving the network performance. Therefore, in the experiment, we focus on improving and comparing with DenseNet. In order to create fair comparisons, we focus the search on the stage-wise structure and strictly follow DenseNet for the global network layout and the cell structure (See details in Appendix A.1).

Following [32] , we start the search from the graphon that corresponds to the WS distribution with k/n = 0.4 and p = 0.75, which we denote as WS-G(0.4, 0.75). We limit the search to input subsets that differ by 1 edge from the starting point. We perform the search on CIFAR-10 for 300 epochs with 8 cells in every stage. The search completes within 24 hours on 1 GPU.

We create four groups of comparison for the four DenseNet variants: DenseNet-121, DenseNet-169, DenseNet-201, and DenseNet-264 in an increasing order of model capacity. We use the proposed scaling method (Section 4.1) to scale up the graphs in the four stages to roughly match the corresponding DenseNet variant. The largest stage-wise graph, containing 64 nodes, is used in the DenseNet-264 group. We also adjust the growth rate c so that the numbers of parameters of all models are as close to DenseNet as possible to enable fair comparisons. However, as the number of parameters depends on the stage-wise connections, which are randomly drawn from the same distribution, we do not have precise control over the number of parameters. We strictly follow the standard hyperparameters and data augmentation techniques used by DenseNet. The networks are trained for 90 epoch on ImageNet; results from 6 independent training sessions are averaged. For a detailed list of hyperparameters and data augmentation, see Appendix A.2.

We introduce two other baseline models besides DenseNet. In the first model, the stage-wise graphs are generated by randomly deleting edges from the fully connected graph of DenseNet. In the second model, we use random graphs generated from WS-G(0.4, 0.75), which are similar to the best random architecture in [32] and shown to be competitive with Amoeba [24] , PNAS [17] and DARTS [19] on an equal-parameter basis.

5.2. RESULTS:

For evaluation, we report the average performance on the ILSVRC-2012 validation set [26] and the new ImageNet V2 test set [25] . For ILSVRC-2012 validation, we report the performance directly after epoch 90. For ImageNet V2, we select the best performing model on the ILSVRC-2012 validation set from the 90 epochs and test it on ImageNet V2. In order to mitigate the effects of random variance, we sample 6 graphs from every graphon and report the average accuracy and standard deviation, as well as the number of parameters in Table 1 .

Across all groups of comparison and model parameter setting, the graphon found by our algorithm consistently achieves the highest accuracy despite having the least parameters. On ImageNet validation, the top-1 performance gap between our method and DensetNet is 0.4% except for 0.1% for DenseNet-121. On ImageNet V2, the performance gap is up to 0.8%. The WS-G baseline in most comparisons is stronger than DenseNet but weaker than the propose technique.

5.3. DISCUSSION:

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.

6. CONCLUSIONS:

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 IMPLEMENTATION DETAILS

A.1 THE GLOBAL STRUCTURE AND THE CELL STRUCTURE OF DENSENET:

1x1 Conv 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.

A.2 HYPERPARAMETERS Some detailed hyperparameters in our experiments are as follows.

During the architecture search stage, we train for 300 epochs. The learning rate schedule follows DenseNet, i.e. The initial learning rate is set to 0.1, and is divided by 10 at epochs 150 and 225. Momentum is set at 0.9. Our batch size is 64 and growth rate in the DenseNet framework is set to 32. For the Gumble softmax, initial temperature is set at 1.0 and the minimum temperature is set at 0.1 with an anneal rate of 0.03.

For ImageNet training, we train for 90 epochs. We use label smoothing, which assigns probability 0.1 to all labels other than the ground truth. We use a batch size of 256 = 64 per GPU × 4 GPUs or 260 = 52 per GPU × 5 GPUs, depending on the GPU memory size. For the 4 stages, growth rates are set at 26,26,26,32 to match the number of parameters for Densenet-121. Learning rate is set at 0.1, divided by 10 at epochs 30, 60, and 80. We use Nesterov momentum of 0.9 and weight decay of 0.00005.

A.3 DATA AUGMENTATION:

We also adopt the following data augmentation for ImageNet training, which are executed sequentially: Inception-style random cropping and aspect ratio distortion, resizing the image to 224 × 224, color jitter with factors for brightness, contrast and saturation all set to 0.4, horizontal flip with probability 0.5, and AlexNet-style random changes to the brightness of the RGB channels [15] .

B THE SEARCH ALGORITHM:

Algorithm 1 shows the detailed procedures. Specifically, for every node v on the graph, we sample K subsets of nodes that could provide input to v, while avoiding cycles (lines 5-7). For example, for the seventh node v 7 , we could sample {v 1 , v 3 , v 5 } or {v 4 , v 6 } and so on. We assign one weight parameter π k to every input subset (line 8). The model parameters for node u is denoted by θ u . Every sampled input edge subset U(v, k) employ the same neural network operations in u, but with different parameters θ u,k (lines 9-11). In particular, the input to node v is the convex combination Algorithm 1 Search for Graphon

1: procedure INITIALIZE(V, k) 2:

Input: totally ordered nodes V, number of subsets k 3:

Output: I s (v), θ u,i , α v , U i 4:

for each node v ∈ V do 5:

I(v) ← {u | u ≺ v, u ∈ V}

all nodes preceding v to avoid cycles 6:

I p (v) ← P(I(v))

the powerset of I(v) 7:

I s (v) ← a random K-element subset of I p (v) 8:

α v ← a random vector in R K weights for the subsets 9:

for each input subset U(v, k) ∈ I s (v) do 10:

for each node u ∈ U(v, k) do 11: INITWEIGHT(θ u,k ) create a set of weights θ u,k for u 12: procedure STAGEFORWARD(V, x, τ , I s (v), θ u,i , π v , U i ) 13:

Input: nodes V, input to the stage x, temperature τ , initialized I s (v), θ u,i , π v , U i 14:

Output: a feature map extracted by the current stage 15: in(v in ) ← x v in is a dummy sending outputs to all nodes.

16:

for each node v ∈ V do 17:

for each input subset U(v, k) ∈ I s (v) do 18:

for each node u ∈ U(v, k) do

19: out(u, k) ← f u (in(u), θ u,k )

apply the operation of u to its input 

in(v) ← K k=1 a k out(k) return in(v out )

v out is a dummy whose input is the stage's output.

of the outputs from all K subsets.

EQUATION

This allows all nodes in the same subset to learn to collaborate, which would be difficult if the parameters were shared across input subsets. During the forward computation, outputs from nodes in the same input subset are aggregated by either summation or concatenation (line 20). Finally, different input subsets are forced to compete by the Gumbel softmax (lines 21-23). We pick the input edge subset with the highest π as the winning adjacency matrix.

C THE CUT DISTANCE δ:

For a partition S, T of V, the cut size is defined as

EQUATION

When two graphs G and G = (V , E ) have the same set of nodes (i.e. V = V ), the partition S, T applies to both graphs. We can then define

EQUATION

When the graphs have the same number of nodes, but the correspondence between nodes is unknown, the distance is defined as the minimum over all isomorphism G ∼ = G.

EQUATION

In general, the two graphs do not have the same number of nodes. Thus, in the most general metric δ , we allow the correspondence between nodes to be fractional. We define the "overlay" matrix L ∈ R |V|×|V | . The entry L ip denotes the fractional mapping from u i ∈ V to u p ∈ V , subject to

EQUATION

Based on L, we can create two new graphs, G[L] and G [L ], which have the same set of nodes V × V and a well defined distance d (G[L], G [L ]). In both graphs, the weight of node (u i , u p ) is L ip . The edge weights are different, however; the weight of edge ((u i , u p ), (u

j , u q )) in G[L] is β ij , whereas in G [L ]

it is β pq . The cut distance δ takes the minimum over all possible overlay matrices.

EQUATION

The fractional overlay is applicable even when the two graphs have the same node count and can lead to a lower distance than integer overlay.

D FRACTIONAL UPSAMPLING:

In fractional upsampling, we start with a graph G with n nodes and generate a new graph with n + m nodes (0 < m < n). To achieve this, we perform two operations sequentially. First, we shift the node weights such that the m nodes have weight 2/(n + m) and the rest n -m nodes have weights 1/(n + m). Next, in what we call a partial blow-up, we split each of the m nodes into two nodes.

After the upsampling operation, all nodes have equal weights 1/(n + m). The requirement for equal weight is needed as the nodeweights are the probabilities of every node being sampled.

Here, the k-way split of node v i is defined as replacing v i with k new nodes v i1 , . . . , v ik , each having node weight α i /k. For any other node v j , the edge (v ik , v j ) has the same weight as (v i , v j ) and the same applies to (v j , v ik ).

In the following, we analyze the cut distance between the new graph and the original graph and show its upper bound is (n-m)m n(n+m) β ∆ , where β ∆ denotes the maximum difference between any two edgeweights.

D.1 WEIGHT SHIFTING:

Theorem 3. Let G = (V, E) and G = (V, E) be two weighted graphs that have the same set of n nodes with different nodeweights and the same set of edges with the same edgeweights. If every node in G has nodeweight 1/n, whereas G has m nodes (0 < m < n) with nodeweight 2/(n + m) and n -m nodes having weight 1/(n + m), then

EQUATION

)

where β ∆ denotes the maximum difference between any two edge weights.

Proof. We create an overlay matrix L with the diagonal terms L ii = min(α i (G), α i G ). For the first m diagonal terms, L ii = 1/n, and for the rest the diagonal terms are 1/(n + m). Then

EQUATION

If i = p and j = q, then β ij (G) = β pq (G). Thus, i,j,p,q

EQUATION

D.2 PARTIAL BLOW-UP Theorem 4. Let G = (V, E) be a weighted graph without self-loops and G be the graph resulted from the k-way split of a node v i ∈ V, δ (G, G ) = 0.

Proof. We construct the overlay matrix L as follows. L jj = 1/n, ∀j = i. L ip = 1/kn, for p = 1, . . . , k. All other entires in L are zeros.

Thus, the graphs G[L] and G [L ] have the same set of nodes with non-zero weights, which include (u j , u j ) for j = i, and (u i , u ip ) for p = 1, . . . , k. The nodes (u j , u j ) have weight 1 and the nodes (u i , u ip ) have weight 1/k. The rest of the nodes have weight 0 and do not enter the computation of δ .

In both G[L] and G [L ], for all j, j = i, the edge weight between (u j , u j ) and (u j , u j ) is the same weight in the original graph β jj (G). Additionally, in both G[L] and G [L ], the edge weight between (u j , u j ), j = i and

(u i , u ip ), p = 1, . . . , k is β ij (G). In G[L],

there are no self loops, so β ii (G) = 0. Similarly, in G [L ], there are no edges between u ip and u iq , so β ip,iq (G ) = 0. Therefore, the graphs G

[L] and G [L ] are identical and d (G[L], G [L ]) = 0. Since the metric δ is non-negative, δ (G[L], G [L ]) = min L∈L d (G[L], G [L ]) = 0.

Corollary 1. Let G = (V, E) be a weighted graph and G be the graph resulted from the k-way split of any subset of nodes V s ⊆ V, then δ (G, G ) = 0.

Proof. G can be realized by splitting the nodes in V s ⊆ V sequentially. Every split keeps the distance with the previous graph at zero. 

D.3 COMPARING K-FOLD BLOW-UP WITH INTERPOLATION:

Another possible approach for upsampling of a weighted graph is interpolating its adjacency matrix. We analyze the distance between the interpolated graph w.r.t. the blow-up graph and show interpolation results in higher distance under moderate assumptions.

In this analysis, we adopt the following notations and definitions. Let G denote a weighted graph with n nodes. The adjacency matrix of G is upper-triangular and has an all-zero diagonal. This is the same as the graphon parameterization that we adopt in this paper. Further, let G[k] be the k-fold blow-up of G and let G itpl [k] be a graph obtained by interpolating the adjacency matrix of G to kn nodes. In all three graphs, let the sum of nodeweights be 1 and evenly distributed among all nodes.

We focus on the analysis of the one-dimensional linear interpolation, where

β ij (G itpl [k])) = (i/k -i/k )β i/k j/k (G) + ( i/k -i/k)β i/k j/k (G).

For example, if we interpolate a 3 × 3 matrix to the size 3k × 3k, we would first repeat every row k times and interpolate horizontally.

More specifically, the row 

EQUATION

Now we construct the partition S , T such that the first km nodes belong to S and the rest kn -km nodes belong to T . Since the adjacency matrix of G is upper triangular and non-zero, without loss of generality we pick m such that m i=1 β im (G) = n i=m+1 β im (G). Since all entries below the diagonal are zero, that inequality is satisfied as long as the column sum at the index m is non-zero. Hence, we let S = {v 1 . . . v km } and T = {v km+1 , . . . , v kn }. Let the cut distance under this partition S , T be δ 

G[k], G itpl [k] , then δ G[k], G itpl [k] = 1 k 2 n 2 vi∈S ,vj ∈T (β ij (G[k]) -β ij (G itpl [k])) = 1 k 2 n 2 k

D.4 DISCUSSION:

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.

:



Figures and Tables:

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.

Figure 4: The DenseNet cell structure used in all experiments.

Let G = (V, E) and G[k] be a weighted graph and its k-way blow-up, respectively, then δ (G, G[k]) = 0.

[a, b, c] will become [a, (k-1)a+b k , . . . , a+(k-1)b k , b, (k-1)b+c k , . . . , b+(k-1)c k , c, (k-1)c k ], . . . , c k ].We note the row sum is k+1 2 a + kb + kc.

If(1) the adjacency matrix of G contains a column with non-zero sum and (2)G itpl [k] and G[k] are optimally overlaid (i.e. δ G[k], G itpl [k] ≤ δ (G[k], G ) ∀G G itpl [k]), then δ G, G itpl [k] > δ (G, G[k]).Proof. From Theorem 2.3 of[3], we have the inequalityδ G[k], G itpl [k] 32 67 ≤ δ G[k], G itpl [k]](15)Note that G[k] and G[itpl(k)] have equal number of nodes. By definition, for a partition S, T of the node set V,δ G[k], G itpl [k] = max S,T cut(S, T, G[k])cut(S, V, G itpl [k])= max S,T vi∈S,vj ∈T

δ G[k], G itpl [k] ≥ δ G[k], G itpl [k] > 0. By Eq 15, δ G[k], G itpl [k] > 0, implying δ G, G itpl [k] > 0. Since δ (G, G[k]) = 0,we have proven the desired proposition.

Performance (accuracy and standard deviation) on ImageNet and ImageNet V2.

Table content: <table><tr><td>Model</td><td># Param</td><td colspan="2">ImageNet Val %</td><td colspan="2">ImageNet V2 Test %</td></tr><tr><td/><td/><td>Top-1</td><td>Top-5</td><td>Top-1</td><td>Top-5</td></tr><tr><td>DenseNet-121</td><td>7.98 M</td><td colspan="4">75.39 ± 0.07 92.51 ± 0.05 62.92 ± 0.06 84.36 ± 0.03</td></tr><tr><td>Random Deletion</td><td>8.02 M</td><td colspan="4">75.30 ± 0.09 92.48 ± 0.07 63.41 ± 0.31 84.74 ± 0.13</td></tr><tr><td>WS-G (4, 0.75)</td><td>8.04 M</td><td colspan="4">75.43 ± 0.11 92.54 ± 0.05 63.62 ± 0.18 84.56 ± 0.11</td></tr><tr><td>NAS Graphon</td><td>7.94 M</td><td colspan="4">75.47 ± 0.12 92.57 ± 0.04 63.74 ± 0.08 84.71 ± 0.24</td></tr><tr><td>DenseNet-169</td><td>14.15M</td><td colspan="2">76.74± 0.02 93.28 ± 0.06</td><td>65.29±0.29</td><td>85.90±0.21</td></tr><tr><td>WS-G (4, 0.75)</td><td>14.23M</td><td>76.94±0.06</td><td>93.37±0.07</td><td>65.18±0.23</td><td>85.79±0.13</td></tr><tr><td>NAS Graphon</td><td>14.14M</td><td>77.14±0.16</td><td>93.44±0.09</td><td>65.36±0.25</td><td>85.96±0.14</td></tr><tr><td>DenseNet-201</td><td>20.01M</td><td>77.42±0.06</td><td>93.60±0.04</td><td>65.84±0.17</td><td>86.04±0.09</td></tr><tr><td>WS-G (4, 0.75)</td><td>20.10M</td><td>77.56±0.11</td><td>93.67±0.07</td><td>65.99±0.09</td><td>86.29±0.15</td></tr><tr><td>NAS Graphon</td><td>19.94M</td><td>77.82±0.14</td><td>93.80±0.09</td><td>66.44±0.15</td><td>86.59±0.38</td></tr><tr><td>DenseNet-264</td><td>33.34M</td><td>77.99±0.02</td><td>93.76±0.07</td><td>66.11±0.11</td><td>86.35±0.32</td></tr><tr><td>WS-G (4, 0.75)</td><td>33.42M</td><td>78.13±0.13</td><td>93.93±0.09</td><td>66.82±0.28</td><td>86.54±0.24</td></tr><tr><td>NAS Graphon</td><td>33.26M</td><td>78.34±0.07</td><td>94.06±0.04</td><td>66.91±0.16</td><td>86.76±0.14</td></tr></table>

Peer review (iclr2020):
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?