Do Not Train It: A Linear Neural Architecture Search of Graph Neural Networks
Authors: Peng XU
Lin Zhang
Xuanzhou Liu
Jiaqi Sun
Yue Zhao
Haiqin Yang
Bei Yu
Venue: Submitted to ICLR 2023 (2023)
Keywords: Neural Architecture Search
Graph neural network
Automated Machine Learning

Abstract: Neural architecture search (NAS) for Graph neural networks (GNNs), called NAS-GNNs,  has achieved significant performance  over manually designed GNN architectures. However, these methods inherit issues from the conventional NAS methods, such as high computational cost and optimization difficulty. More importantly, previous NAS methods have ignored the uniqueness of GNNs, where the non-linearity has limited effect. Based on this, we are the first to theoretically prove that a GNN fixed with random weights can obtain optimal outputs under mild conditions. With the randomly-initialized weights, we can then seek the optimal architecture parameters via the sparse coding objective and derive a novel NAS-GNNs method, namely neural architecture coding (NAC).  Consequently, our NAC holds a no-update scheme on GNNs and can efficiently compute in linear time. Empirical evaluations on multiple GNN benchmark datasets demonstrate that our approach leads to state-of-the-art performance, which is up to $200\times$ faster and $18.8\%$ more accurate than the strong baselines.

Under review as a conference paper at ICLR 2023
Do NOT TRAIN IT: A LINEAR NEURAL ARCHITECTURE SEARCH OF GRAPH NEURAL NETWORKS
Anonymous authors Paper under double-bling review
ABSTRACT
Neural architecture search (NAS) for Graph neural networks (GNNs), called NAS- GNNs, has achieved significant performance over manually designed GNN ar- chitectures. However, these methods inherit issues from the conventional NAS methods, such as high computational cost and optimization difficulty. More im- portantly, previous NAS methods have ignored the uniqueness of GNNs, where the non-linearity has limited effect. Based on this, we are the first to theoretically prove that a GNN fixed with random weights can obtain optimal outputs under mild conditions. With the randomly-initializz optimal architecture parameters via the sparse coding objective and derive novel NAS-GNN method, namely neural architecture coding (NAC). Consequently, our NAC holds no-update scheme on GNNs and can efficiently compute in linear time. Empirical evaluations multiple GNN benchmark datasets demonstrate that our approach leads to state-of- of-tth-art performance, which is up to 200x faster and 18.8% more accurate than the strong baselines.
weights, we can then seek the
INTRODUCTION
Remarkable progress of graph neural networks (GNNs) has boosted research in various domains, such as traffic prediction, recommender systems, etc., as summarized (Wu et al. 202T). The central paradigm of GNNs is to generate node embeddings through the message- pastggggpasingggggg mecha- nism (Hamilton) 2020), including passing, transforming, and aggregating node features across the input graph. Despite its effectiveness, designing GNNs requires laborious efforts to choose and tune neural architectures for different tasks and datasets (You et al.) 2020), which limits the usability of GNNs. To automate the process, researchers have made efforts to leverage neural architecture search (NAS) (Liu et al. 2019a; Zhang et al. 2021b) for GNNs, including GraphNAS (Gao et al. 2020). Auto-GNN (Zhou et 2019), PDNAS (Zhao et al. 2020) and SANE (Zhao et al.) 202 lb) In this work, we refer the problem of NAS for GNNs as WAS-GNNs.
While NAS-GNN: have shown promising results, they inherit issues from general NAS methods and fail to account for the unique properties of GNN operators. It is important to understand the difficulty in general NAS training (e.g., architecture searching and weight evaluation). Based on the searching strategy, NAS methods can be categorized into three types: reinforcement learning- based methods (Zoph & Le 2017). evolutionary algorithms- based methods (Jozefowicz et al. 2015). and differennial -basedd methods (Liu et al. 2019a Wu et al. (0019)) Both reinforcement learning-baat evolutionary algorithm-basse methods suffer from high computational costs due to the need to re-train interential-bbssee paradigm sampled architectures from scratch. On the contrary. the Bright-sharing sub-an subaarchitecture directly reuses the neural weights to reduce the search effort and produces the optimal
and
without excessive processes, such sampling, leading to significant computational cost reduction and becoming the new frontier of NAS.
However, the weight sharing paradigm requires the neural weights to reach optimality so as to obtain the optimal sub-architecture based on its bi-level optimization (BLO) strategy (Liu et al., 2019a), which alternately optimizes the network weights (outputs of operators) and architecture parameters (importance of operators). First, it is hard to achieve the optimal neural weights in general due to the curse of dimensionality in deep learning. leading to unstable searching results, also called the optimization gap (Xie et al.] (022). Second, this paradigm often shows a sloppy gradient estimation (Bi et al. 2020a b) Guoo et al. 2020b) due the alternating optimization, softmax-based

---

Under review as a conference paper at ICLR 2023
estimation, and unfairesss in architecture updating. This type of work suffers from slow convergence during training and is sensitive to initialization due to the wide use of early termination. If not worse, it is unclear why inheriting weights for specific architecture is still efficient- weight updating and sharing lack interpretability.
Is updating the GNN weights necessary? Or, does up- dating weights contribute to optimal GNN architecture searching? Existing NAS-GNN methods rely on updat- ing the weights, and in fact, all these issues raised are due to the need update weights the optimum. Unlike other deep learning structures, graph neural networks be- have almost linearly, so they can simplified as linear networks while maintaining superior performance (Wu et al. 2019b) Inspired by this, we find that the untrained GNN model is nearly optimal in theory. Note that the first paper on modern GNNs, i.c., GCN (Kipt & Welling 2017a), already spotted this striking phenomenon in the experiment, but gained little attention. To the best of our knowledge, our work is the first to unveil this and provide theoretical proof. The issues mentioned before may not be as much of a concern given no weight update is needed, making NAS-GNN much simpler.
90
.NAC
SANE
Accuracy (%6
75
RS GraphNAS WS
70
BayesianGraphNÄS
10
10 Running Time (Min) in log base 10
10
Figure 1: Accuracy vs. running time on Cora. NAC (ours) outperforms the leading methods significantly in both accuracy and speed (in minutes).
In this paper, we formulate the NAS-GNN problem sparse coding problem by leveraging the untrained GNNs, called neural architecture coding (NAC). We prove that untrained GNNs have built-in orthogonality, making the output dependent on the linear output layer. With no-update scheme, we only need to optimize the architecture parameters, resulting in single-level optimization strategy as opposed to the bi-level optimization in the weight-sharing paradigm, which reduces the computational cost significantly and improves the optimization stability. Much like the sparse coding problem (Zhang et al. 2015), our goal is also to learn a set of sparse coefficients for selecting operators when treating these weights collectively understandable. Through extensive experiments on multiple challenging benchmarks, we demonstrate that our approach is competitive with the state-of- of-tt-----e-arr baselines, while decreasing the computational cost significantly, as shown in Fig. !
dictionary, making sharing weights straightforward and
In summary, our main contributions are:
We present (to our best knowledge) the first linear complexity NAS algorithm for GNNs, namely NAC, which is solved by sparse coding.
Problem Formulation:
Theoretical Analysis: Our NAC holds a no-update scheme, which is theoretically justified by the built-in model linearity in GNNs and orthogonality in the model weights.
Effectiveness and Efficiency: We compare NAC with state-of-the-art baselines and show superior performance in both accuracy and speed. Especially, NAC brings up to 18.8% improvement in terms of accuracy and is x faster than basclines.
2 RELATED WORK AND PRELIMINARIES
Graph Neural Networks (GNNs) are powerful representation learning techniques (Xu al. 2019) with many key applications (Hamilton et al., 2017). Early GNNs are motivated from the spectral perspective, such Spectral GNN (Bruna et al. 2014) that applies the Laplacian operators directly. ChebNet (Defferrard et al., 2016) approximates these operators using summation instead to avoid high computational cost. GCN (Kipf Welling 2017b) further simplifies ChebNet by using its first order, and reaches the balance between efficiency and effectiveness, revealing the message-passing mechanism of modern GNNs. Concretely, recent GNNs aggregate node features from neighbors and stack multiple layers capture long-range dependencies. For instance, GraphSAGE (Hamilton) ctt al. (001)) concatenates nodes features with mean/max/LSSMM pooled neighbouring information. GAT (Velickovic et al. 2018) aggregates neighbor information using learnable attention weights. GIN (Xu et al.] 2019) converts the aggregation as a learnable function based on the Weisfeiler-Lehman test instead of prefixed ones other GNNs, aiming to maximize the power of GNNs.
GNNs consist of two major components, where the aggregation step aggregates node features of target nodes' neighbors and the combination step passes previous aggregated features networks to
2

---

Under review as a conference paper at ICLR 2023
generate node embeddings. Mathematically, we can update node v's embedding at the I-th layer by
h² - -b (W -o ((h) Vu E N()))))
(1)
where (() denotes the neighbours of e. W denotes the trainable weight shared by all nodes at the (-layer. is an activation function (with ReLU as default). A main difference of different GNNs lies in the design of the the aggregation functions, o(-). As GNNs have large design space (You et al.
2020 this makes it challenging for the architecture search.
Neural Architecture Search (Xie & Yuille 2017) generally includes three major parts, i.e., search spaces, search strategies, and evaluation methods. Recent advances adopt weight-sharing (Xie et al.) 2022) to avoid (re-) rra))training from scratch as in previous methods, where any architecture can share the weights directly for evaluation without re-training. In particular, making the weights and architectural parameters differentiable (Liu et al.) 2019at Luo et al. 2018) further improves the training e efficiency. Although efficient, weight-sharing NAS has genetic issues that are caused by its bi-level optimization, including over-fitting and inaccurate gradient estimation (Xie et al. 2022). D. making these methods collapse unexpectedly. A variety of methods are proposed to address this from different perspectives, while mainly adding regularization towards weights, such as using k-shot (Su et al.] [021] ). paths dropout (Bender et al. 2018). sampling paths (Guo et al. 2020a). sparsity (Zhang et al. 2001a)) However, these cures are still within the bi-level optimization framework, which can at best alleviate the problem but not directly tackle it. In this work, we propose NAC, linear (i.e., single-level) optimization paradigm, to address the issues weight-sharing NAS.
Concretely, consider WS-NAS defined by {AA, W). where A and W denote the search space and weights of neural networks, respectively. WS-NAS addresses two subproblems of these two space al- ternatively using a bi-level optimization framework (Liu et al., 2019a). including weight optimization and architecture optimization as shown in the following.
a² argmax Muat (w" a)); s.t. w w (a) = argmin Lumin (a, w),
(2)
40
where L denotes a loss function in the training set. M denotes an evaluation metric, such as accuracy, in the validation set. Optimizing separately, WS-NAS avoids the potential biased caused by imbalance dimensionality between w and a, i.e., the neural weights and the architecture parameters. DARTS (Liu et al.) 2a) further converts the discrete search space into a differentiable one with exp(a!!.))
the help of the softmax function that is writing as Eveo exp (..)))) where O represents the search
space consisting of all operators. Thus, we can get the importance of each operator in the format of probability. However, it is difficult reach the optimal state for the objectives defined in Eq. (2) simultaneously. because achieving optimality in deep neural networks is still an open question, and the gradient w.r.t. a intractable (Xie et al. 2022). In practice, researchers often apply early stopping to tackle it, which leads to unexpected model collapse (Zela et al. 2020) and initialization sensitivity (Xie et al. 2022). Another line of work (Chen et al. 2021) (Shu et al. 202T) uses neural tangent kernels (NTK) to search the network structure, called training-free NAS and focuses on CNN architectures. These hold strong assumptions when analyzing due to the need for infinite width of networks, and thus far from reality. In contrast, we do not have such assumption by taking advantage of the built-in linearity in GNNs to get untrained GNNs to work.
NAS for Graph Neural Networks: Many NAS methods have been proposed and adapted for GNNs. such as GraphNAS (Gao et al.) 2020). Auto-GNN (Zhou et al.) 2019), and SANE (Zhao et al. 2021b), and thus enable learning adaptive GNN architecture with less human effort. Methods like Auto-GNN and GraphNAS adopt reinforcement learning (RL) for searching, and thus suffer from the expensive computational cost. Thanks to the weight-sharing policy, SANE (Zhao et al., 2021b) avoids heavy retraining processes in RL methods, which leads to superior performance in general. However, this type of work also faces issues from the weight-sharing differential framework, such as bias optimization and instability due to bi-level optimization. In this work, our proposed method NAC focuses on the NAS for GNNs, and we use GraphNAS and SANE as our main baselines.
Sparse Coding ZZhag et al. 2015) is well-studied topic, and its goal is to learn an informative representation as linear combination from a collection of basis or atom, which is called a dictionary collectively. The standard SC formulation is written as follows:
min L(V,D, D,)) IIV - 2 s.t. Vi, S Toi Vj. D. s112 = 1, D.F
(3)
3

---

Under review as a conference paper at ICLR 2023
where I is the sparse coefficient vector, D is the dictionary, To is value control the sparsity. The first constraint to encourage a sparse representation on and the second constraint to normalize the atoms in the dictionary. NAS aims to find small portion of operators from large set of operators, making it a sparse coding problem in nature. We, therefore, reformulate the NAS-GNN problem as a sparse coding problem.
3 NETWORK ARCHITECTURE CODING (NAC) FOR NAS-GNN
To find the best- pest--erforming architecture, we introduce a novel NAS-GNN paradigm, Neural Archi- tecture Coding (NAC), based on sparse Coding, which requires no update on the neural weights during training. Technical motivation for NAC stems from the observation that an untrained GNN performs well, and training it might not provide extra benefit. In the remainder of this section, we provide theoretical analysis of why no-update GNNs are preferred (Section. 3.1 and propose new NAS-GNN paradigm based on our theorems by leveraging untrained GNNs (Section. 3.2).
3.1 ANALYSIS OF NO-UPDATE SCHEME IN GNNS
In the performance analysis of GNNs, the nonlinear activation function & defined in Eq. ① is often skipped. Following (Wu et al. 2019b), we simplify GNN F = A ... (2 Wr A X I Wi, where A is the adjacency matrix, Wi is the neural weight at the 1-th layer from total number of layers, L. We then obtain the final output as Out = FW, by passing a linear layer W. At the f-th iteration, we denote the GNN weight the /-th layer as Wi()) and the theoretical output layer weight as Wa (t). By initializing the network for all layers, i.e. [W.... Wo), we aim to train the network to get the optimal weights, denoted as [W i-z: Wo). where we assume the optimal weight can obtained +oo-th iteration: W Wi(+oo). We use gradient descent as the default optimizer in GNNs.
We now provide our first main theorem to investigate why an untrained GNN model can attain the same performance as the optimal one.
Theorem 3.1. Assume (0) is randomly initialized for all e L), if Wi(0) is full rank,
there must exist a weight matrix for the output layer, i.c., W., that makes the final output the same as the one from well-trained network:
A A x
W.
= X woo...
(4)
Proof. Because II Wi(0 is full-rank matrix, I1 (i is invertible. We can define W, by
II ([)) II w w. w.
(5)
Hence, by multiplying I Wi( and A x on both sides in Eq. we can attain Eq. 44
This theorem implies that the output layer alone ensure the optimality of the network even when all previous layers have no updates. Next, we show that training in the standard setting of GNNs is guaranteed to reach the desired weight of the output layer, i.e. W.. under mild conditions. We begin by providing the theorem from (Gunasekar al. 2018).
Theorem 3.2 (From (Gunasekar al. 2018) Assume have the following main conditions: 1) the loss function is either the exponential loss or the log-loss; 2) gradient descent is employed to seek the optimal solution; and 3) data is linearly separable. When defining linear neural network as Y XW, W W W. = X IT Wi X,3, we always have the same optimal weight regardless of the number of layers when using gradient descent,
3 argmin || s.t. X3 1,
8
where the ground-truth label vectors with elements as 1 or -1; denotes vector of all ones; O denotes the element- product.
This theorem suggests that the optimal weights obtained by the gradient descent are the same regardless of how many layers in the network, which is equivalent to finding max-margin
4

---

Under review as a conference paper at ICLR 2023
separating hyperplane. Following this, we prove that W. can be obtained based the above conditions:
Theorem 3.3. Assume a GNN model has either the exponential loss or the log-loss, the desired weight Wo is secured when updating with gradient descent and initializing II Wi(0) as an orthogonal matrix. Mathematically, we have Wo(+o0) W. W..
Proof. We first frame the simplified GNNs as A A I Wi = (A Wi). According to Theorem. 3.2 we define the corresponding /3 as B II W,. When using the gradient descent to optimize W and Wo we have the optimized /3 as f II'=1 W, W." The obtained 3 can be viewed as the max-margin hyperplane to separate data A X according to Theorem, 3.2 Omitting the output layer, we let the untrained GNN model as A X I Wi(0) = A XO and assume O - Wi(0) is an orthogonal square matrix. Denoting complete GNN model as A' X'O.. the optimized output weight, i.e. W becomes the max-margin separating hyperplane of XO because it is also trained by gradient descent. Here, we fix the (i( during training to maintain its orthogonality. We know that the max-margin hyperplane of any data remains the same if and only it takes orthogonal transformations, resulting in the following equivalence: OW, = = =
I Wi [=
W. Finally, we get W." O- - W. W = A Wi(o)) W. W.. n
In summary, our proposed theorems prove that GNN with randomly initialized weights can make the final output as good as a well-trained network, where one needs to update the overall network with gradient descent and initialize networks with orthogonal weights. Apart from the optimality, another immediate benefit of this no-update scheme is that the computational cost will be significantly reduced. This is of particular importance when the budget is limited, as the main computational cost of NAS comes from this update.
In this work, we treat the entire NAS supernet general GNN model where each layer a mixture of multiple operators. The above theorems show that one can approximate the optimal output by using the network without training, where we only need update the final linear layer of the supernet. This finding motivates us to learn architectures by taking advantage of randomly initialized networks.
We want to emphasize that real-world scenarios can break the optimal conditions, such as the high complexity of data and the early stopping of the training. Even though, our strategy still provides near-optimal performance, not the best, in experiments.
3.2 ARCHITECTURE SEARCHING VIA SPARSE CODING
Building the above theorems, present novel NAS-GNN paradigm in which untrained GNN model can also yield optimal outputs under mild conditions in the following. This optimality allows us waive the effort design complicated models for updating weights and makes us focus on architecture updates. At a high level, the ultimate goal of NAS is to assign the coefficients of unimportant operators as zeros and the important ones as non-zeros. Towards this, searching the optimal architecture is equivalent to finding the optimal sparse combination of GNN operators, i.c., a. Notably, one of the most successful algorithms for this purpose is sparse coding (Olshausen & Field 1997), which has strong performance guarantees.
What matters most when we reformulate the NAS problem as a sparse coding problem over dictionary defined on GNN operators? According to the research in sparse coding (Aharon et al.) 2006 Tropp] 2004 Candes et al. 2006),, its performance depends on the quality the dictionary. In particular, the most desirable property is mutual coherence or orthogonality. High incoherence in the dictionary tends to avoid ambiguity in the solution and improve optimization stability, resulting in optimal or at least sub-optimal solutions. We prove dictionary that is defined deep neural networks has built-in orthogonality, as shown in the theorem below.
Theorem 3.4. Let the neural weights of each operator in a deep neural network an atom and stack them column-wisely, we can guarantee the existence of an orthogonal dictionary.
Please see Appendix A.2 for more details. This theorem implies that the obtained weights are qualified to be dictionary due to the built-in high dimensionality in deep neural networks. Taking
5

---

Under review as a conference paper at ICLR 2023
inspiration from this, propose NAS paradigm called neural architecture coding as follows:
min a
Lor (y, [z)) 11 11 + e||a[|,
h = ø w' ((h² Yu E N()) d(x) d'á Σ (z))
where
(x)
o' = (z)
where p is the sparsity hyperparameter. f(-) a linear function the final output layer, c.g,, MLP, h represents all nodes' embeddings, and Lcg defines the Cross-Entron loss function. Here, we set the number of GNN operators K and the number of hidden layers L. oth denotes the k-th operator at the (-th layer and its output is vector; am denotes the scalar coefficient for operator Ith-layer and thus ai R& o' is the weight vector from all operators at the 1-th layer. h denotes the embedding of the node at the 1-th layer, where its neighborhood aggregation process is performed as the weighted summation of the outputs from all operators as of (x). y is the node label.
Algorithm The NAC algorithm
Require: The search space .A;
Ensure: The architecture
Randomly initializing W for 1,...,
2: while 1..... do
3: Performing the feature aggregation each layer as d(xx) d'à. E
tth (x);
Toulla
4: Computing h² á [W ((h5-), Vu E N())))]
5: Optimizing a based on the objective function in Eq. w.r.t. a under the fixed dictionary o
6: Updating W. based on the objective function in Eq. w.r.t W. under fixed o;
7: end while Obtain final architecture {a*) from trained a argmax operation each layer:
is important to note that, rather than computing the optimal neural weight for ll like previous randomly initialized weights instead and focus optimizing the combination coefficient o, i.e. architecture parameters. The desired optimal embedding z is then used for downstream applications, such as node classification. In practice, often let h for computational convenience, which makes the loss of the second term to be zero.
NAS methods explicitly,
The sparsity regularization ||x||| allows rank the importance of the operator directly, alleviating inaccurate gradient estimation such as softmax (Garg et al. 202T). We want to emphasize that this regularization does not break the requirement of using gradient descent. Since the architecture, i... a. is fixed when updating the output layer weights, we can use gradient descent for updating as required, so the theorems in Section. hold.
3.3 IMPLEMENTATION DETAILS AND COMPLEXITY ANALYSIS
The overall algorithm is presented at Algorithm 1 Computing NAC consists of two major parts: the forward pass and the backward pass. Given the search space, the computation of the forward is then fixed and regarded as a constant. Therefore, the computational complexity mainly focuses on the backward pass in the NAC algorithm. In summary, the algorithmic complexity of NAC is O * |al), where |x|] is the size a. Please refer to Appendix A.3 for more details about the implementation.
EXPERIMENTS
We conduct experiments address the following issues: (1) How does NAC perform comparison
to the leading baselines? (2) How does the no-update scheme affect other methods? ? (3) Is NAC
robust? Sec. Sec. answer the above questions accordingly.
4.1 EXPERIMENT SETUP
Datasets. We performed experiments on transductive learning for node classification Zhao et al.
2021b). For this setting,
four benchmark datasets: CiteSeer (Giles et al.) (199),, Cora (Kipf & Welling 2016), PubMed (Sen et al. 2008), and Computers (McAuley et al. 2015). Also, we follow the data partition setting (training/validdtioonrtssgggg in (Zhao al. 2021b). For details

---

Under review as a conference paper at ICLR 2023
about transductive learning task and introduction of each dataset, please refer to Appendix A.] for more details.
Methods. Following (Zao et al.
202 compare our NAC with the following strong baselines:
1) Random Search (RS) (Bergstra & Bengio 2012) and 2) Bayesian Optimization (BO) (Jones et al.
1998). 3) GraphNAS (Gao al. 2020): a popular reinforcement bearning-based (RL) method, 4) GraphNAS- S-WS (Zhao et al. 2021b): a variant of GraphNAS with weight sharing, and 5) SANE (Zhao
al. bb2 Among all baselines, the first two are hyperparameter optimization (HPO) methods (Yu & Zhu 2020). GraphNAS and GraphNAS-WS are two popular methods following the weight sharing paradigm while SANE is the most recent work on automated GNNs using the weight-sharing differential paradigm, which is the closest one to our work. We also evaluate NAC-updating, i.c., NAC with weight updates, to compare with the proposed one with no-update scheme.
Search space. We select list of node aggregators (i.e., operators) in GNNs to form the search space. More specifically, they include the following seven aggregators: multi-layer pereeptrons (MLP), GCN (Kipf & Welling (017b)) GAT (Velickovic et al. 2018), GIN (Xu et al.] 2019). Geniepath (Liu et 2001bb,. Graphsage (Hamilton et al. 2017). and ChebNet (Defferrard et al. 2016). Note that MLP is special aggregator with fixed Trequency when viewing GNNs from a spectrum perspective (Balcilar et al., 2020). Besides, Graphsage and GAT contain different aggregation functions, i... maximum and LSTM. We apply all these variations as operators in the experiments. Note that we do not include the layer aggregators like skip-connection in our search space. The underlying rationale is that recent research (Zela et al. 2020 Chen & Hsieh] 2020 Liang iet al., 2019) finds that NAS models converge to skip-connection much faster than other operators due to its parameter-free nature. This introduces biased searching and yields poor generalization. Our experiments ensure that the search space is the same for all baselines.
We do not include layer-wise aggregators like JKNets (Xu et al./ (2018) in the main experiment. As we show in Sec. 3.I] our theory is built upon the classical GNN framework, which equals matrix multiplication. JKNets cannot be represented in this framework. which contradicts our assumptions.
Evaluation Metrics. The proposed approaches aim to boost the ability to learn efficacious archi- tecture for downstream tasks. The classification accuracy and the runtime (i.e., wall-clock time) are two widely used metrics in NAS research to measure the model performance and efficiency, respectively (Zhang et al. 2021a). The reported results are the average of the best results in 4 runs from different random seeds.
We set the runtime of NAC. SANE, and GraphNAS as the time they take to obtain the final ar- chitectures with 100 epochs] The runtime of RS and Bayesian is fixed to the time of 100 times trial-and-crror processes.
Table 1: Experimental results on the compared methods: our NAC attains superior performance in both
accuracy (%) and efficiency (in minutes).
CiteSeer
Cora
PubMed
Computers
Accuracy
Time
Accuracy
Time
Accuracy
Time
Accuracy
Time
RS
70. 12.
14.4
71.2614.08
30.6
86.75 86.7510.92
187.8
77.8411.5
8.75
70.95
68.5926.66
31.2
87 87.422n.0s
189.6
77 77.4622.02
17.65
GraphNAS
68.6941..0
253.8
71.26x+4.0
245.4
86.07+0.51
1363.8
73.97+1.79
86.37
GraphNAS WS
65.35
80.4
72.1422.50
161.4
85.71
965.4
72.99
42.47
SANE
71.84
4.2
84.58
10.2
87.55+0.75
107.4
90.70+0.00
0.72
NAC
14.62
1.2
87.41.o.s
1.2
88.04
9.0
91.64
0.23
NAC-updating
74.17+1.18
4.2
86.62+1.14
3.6
88. 10..80
25.8
90.89+1.10
0.70
4.2 COMPARISON RESULTS
Results in Table I and Fig. show that NAC attains superior performance than all baselines regarding both accuracy and efficiency. More specifically, we observe the following.
In terms of model performance, our NAC beats all baselines and attains up to 2.83%inprovemmnt over the best bascline, i.c.. SANE, while attaining up to 18.8% improvement over the Bayesian method, the best HPO method. Thanks to our non-updating scheme, it prompts the outputs near the optimal to make the selection of the best best-performing architecture reliable, as opposed to biased
'The running time for the Computers dataset is measured on single GPU, which is different from all other three datasets.
7

---

Under review as a conference paper at ICLR 2023
optimization in others. We notice that in case, NAC is slightly worse than NAC-updating, about 0.06%. This case reminds us that the optimal condition can get compromised due to the high complexity of the data. Still, NAC holds for near-best performance, demonstrating its robustness. Empirical results corroborate our theories in Section. 3.1 that non-updating scheme is preferred. The underlying assumption of RL.-based and BO-based methods is obtain accurate estimation of the distribution of the search space. However, these methods rely on random sampling to perform the estimation, thus have no guarantee of the search quality due the high complexity the search space. For instance, RL-based methods are sometimes even worse than RS- ESS-aased methods, pure randomly sampled, implying the unreliability of such estimation under a limited budget. WS-based methods couple the architecture search and the weight training, so they struggle to train the network to be optimal and obtain a biased network due oscillations between the two components.
In terms of model efficiency, our NAC achieves superior performance, around 10x faster than SANE and up to x time faster than GraphNAS. Our non-updating scheme requires nearly no weight update, thus giving NAC incomparable advantage in reducing the computation cost. All previous NAS methods need to update neural weights, for example, RL-based costs the most due retraining the network from scratch at each time step, and WS- costs the least by reusing neural weights.
4.3 NO-UPDATE SCHEME AT WORK
To further validate our no-update scheme, we evaluate its effect on other weight-sharing methods. Since SANE attains the best performance among all baselines, we test the no-update scheme on SANE as SANE". i.e., SANE with fixed neural weights. Results in Table show that SANE" outperforms the one with updates. This result implies that we can improve the performance of NAS-GNN methods by simply fixing the weights with random initialization. This yields much lower computational cost in the training.
Table 2: Performance comparison between SANE, NAC+ and NAC.
Suboi Ravoaan
CiteSeer Acc(S)
Cora Acc(%)
PubMed Acc(FE)
Computers Acc(S)
SANE
1..84
84.58
07 na
00.70
NAC
21.76
27.27
87,59 22
91.07 20.71
Scried
Figure 2: Visualization of the sorted eigenvalues of weights of NAC with dif- ferent initialization.
NAC
7..62
87.41
18.04
20.64
4.4 ABLATION STUDIES
Initialization: Recall that in Sec. 3.1 a prerequisite is the orthogonality on the neural weights matrix. This makes the initialization critical to the final performance. To investigate the effect of initialization, we try three types of initialization methods, including normal, uniform, and orthogonal. Table 4 shows that NAC with orthogonal initialization outperforms other cases of initialization. The results again confirm our theory.
To get a better understanding of the reason, we visualize the eigenvalues of Il Wi on different initialization cases in Figure 2 The results show that the eigenvalues of NACs with normal and uniform initialization decay accordingly. This makes the input feature tends to project to the subspace spanned by the top-ranked eigenvectors, which results feature distortion and leads to performance degeneration. In contrast, when NAC with orthogonal initialization, the eigenvalues are distributed uniformly, which ensures the spanned space does not bias toward any particular eigenvectors.
In summary, NAC with orthogonal initialization attains the best performance and confirms our theory. In addition, results from orthoothogonal initializations are still better than other baselines, demonstrating the robustness of NAC.
The linear output layer: Recall that for a given linear output layer, there exists the optimal weight, ie. W., to secure the optimal output according to Theorem, 3.1 Nevertheless, obtaining optimal weights in deep learning algorithm is an open question due its high dimensionality. Often, in practice, we train the network with early stopping. especially in NAS methods. Therefore, obtaining the optimal weights for the output layer is not possible. Is training the output layer necessary? This
8

---

Under review as a conference paper at ICLR 2023
Table 3: Comparison between SANE and SANE" (w/o. weight updates).
50.0
SA3E K30
CiteSeer Acc(5))
Cora A
Pubmed Acc(%)
Computers Acc(%)
75.0
SANE SANE"
1.
84.58 20.53 85.46
87.55 o7
00.70_0.88 9..86-0.60
1..95=1.82
88.12
20,0
Table 4: Comparison NAC with different initializations.
CiteSeer Acc(R))
Cora Acc(S))
PubMed Acc(S))
Computers Acc(Sh)
66.0
10
41
70
100
120
300
300
230
250
Kaiming Normal
41.1242.45
86.85
07.52
91.05=0080
Figure 3: Convergence for SANE and NAC in terms of accuracy. NAC converges much faster than SNAE in only around 20 epochs.
Kaiming Uniform
72.06ga.224
86,99_1.03
87.68 97
88.52
Orthngonal
74.62
87.41
88.04+1.06
91.64.0.14
experiment attempts to answer this by comparing NAC with and without training the output layer. Note that we fix all other layers with random weights. By default, NAC is the one without training any layers in the whole paper, including the output layer. On the contrary, NAC is the one with training the output layer. Here, set the number of epochs as 100. In Table. - we can find that the performance NAC+ is in the middle between SANE and NAC. On the one hand, training the linear layer may not be worthwhile because it is impossible get the desired optimal weights. On the other hand, results with and without training the output layer are always better than SANE, suggesting the superiority of the no-update scheme in general. To further demonstrate this, implement multiple experiments by training the last layer with different epochs, as shown in Appendix. A.4.3
Sparsity effect: We also conduct experiments test how sparsity affect the search quality of NAC. The hyperparameter is to control the sparsity of the architecture parameter a. We test the effect by varying its value in a considerably large range, i.e., [0.001, 10). The results show that the performance varies little w.r.t. p. This indicates that NAC is insensitive to the sparsity hyperparameter.
Random seeds: By default, researchers report the average or the best result from different random seeds, this often lead to poor reproducibility. We now present the effect of random seeds on this topic. In particular, we implement the experiment on multiple random seeds and observe a stable performance of NAC.
The experimental results show that NAC is robust to both sparse hyperparameter selection and random seeds. Please refer to Appendix A.4 for more details.
4.5 ANALYSIS OF CONVERGENCE
notable benefit of the NAC framework is its guaranteed convergence from the sparse coding perspective. To verify this, Fig. offers convergence comparison between NAC and SANE from the Pubmed dataset by showing the accuracy on the retrained network acquired at each training epoch. NAC shows substantially faster convergence than SANE, which take around 20 and 80 epochs, respectively. Due to the BLO strategy, SANE suffers strong oscillation when optimizing two variables, i.e., the architecture and neural weights, which consumes more epochs to converge.
5 CONCLUSION
We present the first linear complexity NAS algorithm for GNNs, namely NAC. Our NAC is solved by sparse coding and holds no-update scheme for model weights in GNNs because GNNs embed the built-in model linearity and orthogonality for the model weights. Extensive experiments demonstrate that our NAC can achieve higher accuracy (up to 18.8%) and much faster convergence (up to 200x) than SOTA KAS-GNNs baselines.
Several promising directions can be considered. We can further explore more deep neural networks that satisfy the mild condition of our NAC to extent its usability. We can investigate more on the efficiency of different subgradient methods for solving the sparse coding objective. We also intend to investigate how to jointly learn the search space and architectural representation to further enhance the expressive ability of scarched architectures.

---

Under review as a conference paper at ICLR 2023
REPRODUCIBILITY STATEMENT
The supplemental material includes the code for our experiments. An detailed description of the datasets used in the experiments is provided in Appendix A.1
REFERENCES
M. Aharon, M. Elad, and A. Bruckstein. K-svd: An algorithm for designing overcomplete dictionaries for sparse representation. IEEE Transactions on Signal Processing.
1-4322, 2006.
Muhammet Balcilar, Guillaume Renton, Pierre Héroux, Benoit Gaüzère, Sébastien Adam, and Paul Honeine. Analyzing the expressive power of graph neural networks in spectral perspective. In ICLR, 2020.
Gabriel Bender, Pieter-Jan Kindermans, Barret Zoph, Vijay Vasudevan, and Quoe Le. Understanding and simplifying one-shot architecture search. In ICML, 2018.
James Bergstra and Yoshua Bengio. Random search for hyper-parament optimization. Mach. Learn. Res., 13:281 1-225, feb 2012. ISSN 1532-4435.
Kaifeng Bi, Changping Hu, Lingxi Xie, Xin Chen, Longhui Wei, and Qi Tian. Stabilizing darts with amended gradient estimation on architectural parameters. CoRR, abs/1910.11831, 2020a.
Kaifeng Bi, Lingxi Xie, Xin Chen, Longhui Wei, and Qi Tian. differentiable. CoRR, abs/2007 1as/2007700331, 2020b.
Gold-nas: Gradual, one-level,
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. In ICLR, 2014.
E.J. Candes, J. Romberg, and T. Tao. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Transactions Information Theory, 52(2): 489-509, 2006.
Wuyang Chen, Xinyu Gong, and Zhangyang Wang. Neural architecture search on imagenet in four gpu hours: A theoretically inspired perspective. arXiv preprint arXiv:2102. 2021.
Xiangning Chen and Cho-Jui Hsieh. Stabilizing differentiable architecture search via perturbation- based regularization. In ICML., 2020.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst, Convolutional neural networks on graphs with fast localized spectral filtering. In NeurIPS, 2016.
Matthias Fey and Jan Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop, 2019.
Hans Fischer. A history of the central limit theorem: from classical to modern probability theory. Springer, 2011.
Wenjiang Fu. Penalized regressions: the bridge versus the lasso. Journal of computational and graphical statistics, 7(3):397-416, 1998.
Yang Gao, Hong Yang, Peng Zhang, Chuan Zhou, and Yue Hu. Graph neural architecture search. In IJCAI, 2020.
Shivam Garg, Samuele Tosatto, Yangehen Pan, Martha White, and A Rupam Mahmood. An alternate policy gradient estimator for softmax policies. arXiv preprint arXiv:21 2021.
C. Lee Giles, Kurt D. Bollacker, and Steve Lawrence. Citeseer: An automatic citation indexing system. Proceedings of the Third ACM Conference on Digital Libraries, pp. 89-98, 1998.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent on linear convolutional networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman. N. Cesa- Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
10

---

Under review as a conference paper at ICLR 2023
Ronghao Guo, Chen Lin, Chuming Li, Keyu Tian, Ming Sun, Lu Sheng, and Junjie Yan. Powering one-shot topological NAS with stabilized thare-paramene proxy. In ECCV, 2020a.
Zichao Guo, Xiangyu Zhang, Haoyuan Mu, Wen Heng, Zechun Liu, Yichen Wei, and Jian Sun. Single path one-shot neural architecture search with uniform sampling. ECCV, 2020b.
William L. Hamilton. Graph representation learning. Synthesis Lectures on Artificial Intelligence and Machine Learning, 14(3):1-15,, 2020.
William L. Hamilton, Zhitao Ying. and Jure Leskovee. Inductive representation learning on large graphs. In NeurlPS, 2017.
Donald R. Jones, Matthias Schonlau, and William J. Welch. Efficient global optimization of expensive black-box functions. Journal of Global Optimization, 13(4). 1998.
Rafal Jozefowicz, Wojciech Zaremba, and Ilya Sutskever. An empirical exploration of recurrent network architectures. In ICMI., 2015.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: 1609.02907, 2016.
Thomas N. Kipf and Max Welling. Semi-super classification with graph convolutional networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017a.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017b.
Hanwen Liang, Shifeng Zhang, Jiacheng Sun, Xingqiu He, Weiran Huang, Kechen Zhuang, and Zhenguo Li. DARTS+: improved differentiable architecture search with early stopping. CoRR, abs/1909.06035, 2019.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: differentiable architecture search. In ICLR, 2019a.
Ziqi Liu, Chaochao Chen, Longfei Li, Jun Zhou, Xiaolong Li, Le Song, and Yuan Qi. Geniepath: Graph neural networks with adaptive receptive paths. In AAAI, 2019b.
Renqian Luo, Fei Tian, Tao Qin, Enhong Chen, and Tie- Yan Liu. Neural architecture optimization. In NeurlPS, 2018.
Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton Van Den Hengel. amage-based recommendations on styles and substitutes. In Proceedings of the 38th international ACM SIGIR conference on research and development in information retrieval, pp. 43-52, 2015.
Bruno A. Olshausen and David J. Field. Sparse coding with an overcomplete basis set: A strategy employed by vI? Vision Research, 37(23):331 1997. ISSN 0042-6989.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
J Ranstam and JA Cook. Lasso regression, Journal of British Surgery, 105(10):1348-1333 2018.
Mark Schmidt, Glenn Fung, and Romer Rosales. Optimization methods for 11-regularization. University of British Columbia, Technical Report TR-2009-19 19, 2009.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. A/ Magazine, 29(3):93, Sep. 2008. doi: 10. 1009/imma.. v29.3.2157.
Shirish Krishnaj Shevade and S Sathiya Keerthi. simple and efficient algorithm for gene selection using sparse logistic regression. Bioinformatics, 19(17):244-2253, 2003.
11

---

Under review as a conference paper at ICLR 2023
Yao Shu, Shaofeng Cai, Zhongxiang Dai, Beng Chin Ooi, and Bryan Kian Hsiang Low. Nasi: Label- and lata-agnostic neural architecture search at initialization. arXiv preprint arXiv:2109.00817, 2021.
Xiu Su, Shan You, Mingkai Zheng, Fei Wang. Chen Qian, Changshui Zhang, and Chang Xu, K-shot NAS: learnable weight-sharing for NAS with k-shot supernets. In ICML, 2021.
D. ter Haar. Mathematical foundations of statistical mechanics. a. khinchin. Science, 110(2865): 570-570, 1949.
J.A. Tropp. Greed is good: algorithmic results for sparse approximation. IEEE Transactions on Information Theory, 50(10):2231-2244 2004.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
Bichen Wu, Xiaoliang Dai, Peizhao Zhang, Yanghan Wang, Fei Sun, Yiming Wu, Yuandong Tian, Peter Vajda, Yangqing Jia, and Kurt Keutzer. Fbnet: Hardware-aware efficient convnet design via differentiable neural architecture search. In CVPR, 2019a.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In International conference on machine learning, pp. 6861-6871. PMLR, 2019b.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 32(1):4-24, Jan 2021. ISSN 2162-2388.
Lingxi Xie and Alan L. Yuille. Genetic CNN. In ICCV, 2017.
Lingxi Xie, Xin Chen, Kaifeng Bi, Longhui Wei, Yuhui Xu, Lanfei Wang, Zhengsu Chen, An Xiao, Jianlong Chang, Xiaopeng Zhang, and Qi Tian. Weight-sharing neural architecture search: A battle to shrink the optimization gap. ACM Comput. Surv. 14(9):183:1-1833 2022.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanic Jegelka. Representation learning on graphs with jumping knowledge networks. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 5453-5460 5462. PMLR, 10-15 Jul 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. networks? ICML, 2019.
How powerful are graph neural
Jiaxuan You, Zhitao Ying, and Jure Leskovec. Design space for graph neural networks. Advances in Neural Information Processing Systems, 33, 2020.
Tong Yu and Hong Zhu. Hyper-parameter optimization: review of algorithms and applications. CoRR, abs/2003. 056699, 2020.
Arber Zela, Thomas Elsken, Tonmoy Saikia, Yassine Marrakchi, Thomas Brox, and Frank Hutter. Understanding and robustifying differentiable architecture search. In ICLR, 2020.
Xinbang Zhang, Zehao Huang, Naiyan Wang, Shiming Xiang, and Chunhong Pan. You only search once: Single shot neural architecture search via direct sparse optimization. IEEE Trans. Pattern Anal. Mach. Intell. 43(9))
2021a.
Zheng Zhang, Yong Xu, Jian Yang. Xuelong Li, and David Zhang. A survey of sparse representation: algorithms and applications. IEEE access, 3:490-530, 2015.
Ziwei Zhang, Xin Wang, and Wenwu Zhu. Automated machine learning on graphs: A survey. In IJCAI, 2021b.
Huan Zhao, Lanning Wei, quamming yao, and Zhiqiang He. Efficient graph neural architecture search, 2021a.
12

---

Under review as a conference paper at ICLR 2023
Huan Zhao, Quanming Yao, and Weiwei Tu. Search to aggregate neighborhood for graph neural network. ICDE, 2021b.
Yiren Zhao, Duo Wang, Xitong Gao, Robert Mullins, Pietro Lio, and Mateja Jamnik. Probabilistic dual network architecture search on graphs. arXiv preprini arXiv:2003. 09676, 2020.
Kaixiong Zhou, Qingquan Song, Xiao Huang, and Xia Hu. Auto-gnn: Neural architecture search of graph neural networks. CoRR, 0tts/1999.053 84, 2019.
Barret Zoph and Quoc V. Le. Neural architecture search with reinforcement learning. In ICLR, 2017.
13

---

Under review as a conference paper at ICLR 2023
A APPENDIX
A.1 DATASET DETAILS
In the transductive learning task, node features and edges between nodes in the whole datasets were known beforehand. We learn from the already labeled training dataset and then predict the labels of the testing dataset. Three benchmark datasets were used in this setting: CiteSeerr (Giles et al. 1998). Cora (Kipf & Welling 2016) and PubMed (Sen et al., 2008). All of the three benchmark datasets are citation networks. In citation networks, each node represents a work, and each edge shows the relationship between two papers in terms of citations. The datasets contain bag-of-words features for each node, and the goal is to categorize papers into various subjects based on the citation. In addition the three benchmark datasets, we also employ another dataset Amazon Computers (McAuley et al.) 2015). Amazon Computers is subset of the Amazon co- co-purchase graph, where nodes represent commodities and edges connect them if they are frequently purchased together. Product reviews are encoded as bag-of- of-word feature vectors in node features, and class labels are assigned based on product category.
In the inductive task, several graphs are used as training data, while other completely unseen graphs are used as validation and test data. For the inductive setting, we use the [Pm[Hamltton et al. (2017) dataset as benchmark dataset. The task of PPI dataset is to classify the different protein functions. consists of 24 graphs, with each representing a different human tissue. Each node has properties such positional gene sets, motif gene sets, and immunological signatures, ant gene ontology sets as labels. Twenty graphs are chosen for training, two graphs for validation, and the remaining for testing. For the inductive task, we use Micro-Fl F1 the evaluation metric.
The used datasets are concluded in Table
Table 5: The Statistics of Datasets
Transductive PubMed
Inductive PPI
CiteSeer
Cora
Computers
#nodes
2708
3327
19717
13752
56944
# #edges
5278
4552
44324
245861
818716
# features
1433
3703
500
767
121
# classes
3
10
50
A.2 PROOF OF THROREM 3.4 FOR THE DICTIONARY ORTHOGONALITY NAC
Theorem A.1. Let the neural weights of each operator in deep neural network be atom and stack them column-wisely we can guarantee the existence of an orthogonal dictionary.
Proof. Given dictionary H E R K where is the number of nodes and K is the number of opearators in each layer, have its mutual coherence computed as follows,
h;
h
max h. E.
|1:112
|
(8)
where & E [o. 1), and (-) denotes inner product. Here, each atom, h,, is the weights from an operator. The minimum of to is 0 and is attained when there is an orthogonal dictionary, while the maximum is 1 and it attained when there are at least two collinear atoms (columns) in a dictionary.
Let E;
hy h and E, ||b,11, by Central Limit Theorem (Fischer 2011), we know that [lbill,
(E, E,) /vn converges to a normal distribution, i.e.,
(E, E,) lim VnZ,
where is a standard normal distribution. Consider E the mean value of all (E,, E,). With weak law of large numbers (a.k.a. Khinchin's 's law) (ter Haar 1949), for any positive number the probability that sample average É greater than e converges
written as
lim Pr 2 s) =0
(10)
n 400
14

---

Under review as a conference paper at ICLR 2023
This implies that the probability that the inner product of E, and Ej is greater than close to zero when n + co. In other words, the probability that E, and E are nearly orthogonal goes to 1 when their dimensionality is high. Therefore, the coherence of this dictionary reaches the minimum at high dimensionality that holds for deep neural networks naturally.
A.3 EXPERIMENTAL IMPLEMENTATION DETAILS
Environment. We implement experiments related to accuracy on Citeseer, Cora, and PubMed using PyTorch (Paszke et al., 2019) (version 1.10.2+cpu) on a CPU server that has a 48-core Intel Xeon Platinum 8260L CPU, and experiments Amazon Computers using PyTorch (version 1.10.2+gpul on a GPU server with four NVIDIA 3090 GPUs (24G). Speed-related experiments on Citeseer, Cora, and PubMed were measured using Py PyToch (version 1 1.4+cpu) on CPU server with ten-core Intel Xeon Platinum 8255C CPU, 40G RAM, and 500G DRAM. Speed-related experiments on Amazon Computers were measured using Py PyTorch (version 10 on GPU server with four NVIDIA 3090 GPUs (24G). Operators used in the experiments are from the built-in functions of PyG (version 2.0.2) (Fey & Lenssen 2019).
Searching configuration. In our experiments we adopt 3-layer GNN as the backbone. Unless specified, our experiments follow the same settings for searching architectures as SANE (Zhao et al. 2021b)
Architecture optimizer. We use Adam for training the architecture parameters a. We set the learning rate as 0.0003 and the weight decay as 0.001. Also, the 31 and [3 are fixed as 0.5 and 0.999, respectively. All runs a constant schedule for training, such as 100 epochs.
Wei Weight optèmizer. We use SGD to update models' parameters, i.e., w. The learning rate and SGD momentum are given as 0.025 and 0, respectively, where the learning rate has a cosine decay schedule for 100 epochs. We fix the weight decay value, i.e. set P1 0.0005.
Batch size. For transductive tasks, we adopt in-memory datasets, and the batch_size fixed as the size of the dataset themselves.
The configuration for retraining phase. At the retraining state, we adopt Adam as the optimizer and set the scheduler with cosine decay to adjust the learning rate. The total number of epochs is fixed 400 for all methods for fairness. Please refer to the setting of SANE (Zhao et al.] (021b) and EGAN Zhao et al. 2021a) for more details we follow this in experiment.
For CiteSeer dataset, we set the initial learning rate as 0.005937 and weight decay as 0.00002007. The configuration for models is follows: hidden_size 512, dropoul 0.5, and using Le as the activation function.
For Cora dataset, we set the initial learning rate as 0.0004150, and weight decay as 0.0001 125. In model, we set hidden_size 256, dropout = 0.6, and use Re as the activation function.
For PubMed dataset, we set the initial learning rate as 0.002408 and weight decay as 0.00008850. As for the model, we have hidden_size 64 and dropoul = 0.5, and use ReLU as the activation function.
For Amazon dataset, we set the initial learning rate as 0.002111 and weight decay as 0.000331. As for the model, we have hidden_stt size 64 and dropout 0.5, and use elu as the activation function.
For PPI dataset, we set the initial learning rate as 0.00102 and weight decay 0. As for the model, we have hidden_siie = 512 and dropout = 0.5, and use Relu as the activation function.
Solving L' regularization. The L' regularization, also known as Lasso Regression (Least Absolute Shrinkage and Selection Operator), adds an absolute value of the magmitude of the coefficient as penalty term to the loss function (Ranstam Cook 2018)). Using the I," regularization, the coefficient of the less important feature is usually decreased to zero, sparsifying the parameters. It should be noted that since ||a/|] is not differentiable at a = O, the standard gradient descent approach cannot be used.
Despite the fact that the loss function of the Lasso Regression cannot be differentiated, many approaches to problems of this kind, such (Schmidt et al.] 2009), have been proposed in the literature. These methods can be broadly divided into three groups: constrained optimization methods, unconstrained approximations, and sub-gradient methods.
15

---

Under review as a conference paper at ICLR 2023
Since subgradient methods natural generalization of gradient descent, this type of methods can be easily implemented in Pytorch's framework. Lasso Regression can be solved using a variety of subgradient techniques; details their implementation can be found in (Fu 1998) and (Shevade & Keerthi (003).
Computational Complexity Estimation of NAC. The computation of NAC has two major parts: the forward pass and the backward pass. Given the search space, the computation of the forward is then fixed and regarded as a constant. Therefore, the computational complexity mainly focuses on the backward pass in the NAC algorithms.
The main version of our work does not need update weights, but only to update architectural parameter a during the training process. Therefore, the algorithmic complexity is as O(T ||x[]) which is a linear function w.r.f a. The dimension of ar is often small, which makes the model easy to scale to large datasets and high search space. When updating weights of the linear layer, the complexity estimated as O(T [I]ox] + IIl)) The dimension of W, is constant number, that equals the number of classes. Therefore, the complexity is almost the same as the main version of NAC, where the complexity is O * ||x]| [[Wol)).
When updating weights, similar DARTS, the complexity is estimated O(T (||o< || ())- The dimension of w is often much larger than a therefore, the complexity is dominated by updating
w, where the complexity is O(T |/wl)). Since the dimension of is much smaller than w, the complexity of NAC is much less than this type of methods.
Approximate Architecture Gradient. Our proposed theorems imply an optimization problem with a as the upper-level variable and Wo as the lower-level variable:
a argmax. (W (a),,
a W (a) = argminC(aa, Wo).
(11)
W.
Following (Liu et al. 2019a), we can adopt First-order Approximation to avoid the the expensive inner optimization, which allows us to give the implementation in the algorithm
A.4
ABLATION STUDIES
A.4.1 THE EFFECT OF SPARSITY
Our model uses the hyperparameter to control the sparsity of the architecture parameter a, where a large sparsity is to enforce more elements to be zero. We investigate the effect of this hyperparameter by varying its value in considerably large range, such as [0.001, 10). We first present the accuracy of different sparse setting in Fig. We find that the results vary little in a considerably wide range, this indicates our models are insensitive to sparsity hyperparameter in general.
A.4.2 THE EFFECT OF RANDOM SEEDS
Random seeds often play importance role in traditional NAS methods as it affects the initialization significantly. People often report the average or the best results under different random seeds, this may lead to poor reproducibility. To the best our knowledge, this is for the first explicitly demonstrate the effect of random seeds in this subject. We run experiments on several random seeds and report the results of NAC on Pubmed dataset, shown in Fig. 5 In particular, we implement multiple combinations of random seeds and sparsity to observe the variation on performance. Note that we round the values to integer fit the table. In all these combinations, we have the average and variance as 87. .2% and 0.9%, respectively. The average performance is comparable to the best results from all competitive results, which indicates the stability of NAC.
A.4.3 THE EFFECT TRAINING ON THE FINAL LINEAR LAYER
Our proposed theorems prove that a GNN with randomly initialized weights can make the final output as good as well-trained network when initializing networks with orthogonal weights and updating the total network using gradient descent. In practice, we find it difficult to determine at what training epoch the optimal weight parameters can be obtained through training linear layer. We noticed that most of the time, the untrained weights in the initial state can often already exceed the accuracy that can be obtained from the weights after multiple epochs of training the final linear layer, shown in
16

---

Under review as a conference paper at ICLR 2023
tag NAC(Orthogonal)
tag NAC(Normal)
tag NAC(Uniform)
90
80
Acc
70
60
50
0
1
2
3 4
910
0
1
2
3
6
7
8 910
0
1
2
5 6 sparse
7
8
910
sparse
sparse
(a) CiteSeer
1 ag = NAC(Orthogonal)
tag NAC(Normal)
tag NAC(Uniform)
100
90
Acc
80
70
60
0
1
2
4
910
910
2
4
5 sparse
6
8 910
sparse
sparse
(b) Cora
tag = NAC(Orthogonal)
tag = NAC(Normal)
tag NAC(Uniform)
100
90
Acc
80
70
60
2 3 4
6 7 sparse
5
910
4 5 7
910 3 4 5 6 7
910
910
sparse
sparse
(c) PubMed
Figure 4: Sensitivity study of the sparsity. Results are with varying sparsity (x-axis) and different initialization NAC methods (i.e., normal, uniform and orthogonal). The variation is small, showing the robustness of our model w.r.t the sparsity.
Fig. 6 Therefore, further omit the training of the final linear layer. It important to note that this approximation is based on our proposed theorems in which most of the intermediate layers do not require training.
A.5 RUNTIME OF EACII METHOO ON A SINGLE GPU SERVER
Apart from the running time on the CPU, we also measure the running time for all methods GPU platform. where we use Py PyToc (version 1.10.2+gpu on a GPU server with four NVIDIA 3090 GPUs (24G), as shown in Table These results are consistent with the ones Table demonstrating our advantage in speed.
A.6 PERFORMANCE ON INDUCTIVE TASKS
To validate the effectiveness of our approach to the Inductive task, we performed set of experiments on the PPI dataset. The experimental results are concluded in Table / The experimental results show that proposed method effectively outperforms the best baseline method by about 4% in terms of Micro-Fi score. Besides, our method achieves an 8x speedup terms of running time than SANE. Also, the non-updating scheme of the NAC approach exceeds the NAC-updating method effectively.
17

---

Under review as a conference paper at ICLR 2023
88
seed
88
86
89
87
88
87
0.00 0.001
88
86
87
87
87
87
88
89
88
88
88
87
1.0
88
8.8
89
87
88
87
8.5
89
87
88
87
87
0.0
8.5
86
87
87
87
87
sparso
1
0
Figure 5: The effects of random seeds of NAC on the accuracy, where x-axis denotes the random
seeds and y-axis denotes the sparsity. NAC performs stably with random seeds.
89
88
Ane (%)
87
NAC
86
85
20
40
60
80
100
Traning Epochs of Linear Layer
Figure 6: The effects of training final linear layer of NAC on the accuracy, where x-axis denotes the training epochs of the final linear layer and y-axis denotes the averaged accuracy of acquired architecture a using the corresponding weights.
18

---

Under review as a conference paper at ICLR 2023
Table 6: Timing results of the compared methods and our NAC method in the same GPU server. NAC attains superior performance in efficiency (in seconds).
CiteSeer
Cora
PubMed
Computers
RS
196.00
328.00
461.00
900.00
BO
225.00
355.00
462.00
878.00
GraphNAS
6193 00
6207.00
6553.00
8969.00
GraphNAS-WE WS
947.00
1741.00
2325.00
4343.00
SANE
35.00
41.00
43.00
43,00
NAC
14.00
14.00
15.00
14.00
NAC-updating
42.00
31.00
36.00
42.00
Experiments on the PPI dataset further validate the effectiveness and superiority of our proposed method.
Table Experimental results compared methods: our NAC attains superior performance on dataset in both Micro-FI score (%) and efficiency (in hours).
PPI(Micro-FI(S8)
PPI(Time(h))
SANE
91.01 +6.83
2.50
NAC
95.16
0.31
NAC-updating
94.47+7.09
4.68
A.7 SEARCHED ARCHITECTURES FOR EACH DATASET OUR METHOD
We visualize the searched architectures (top-1) 1) by NAC on different datasets in Fig
For Citeseer dataset, the searched result is GATIGGNNIChebboow;
For Cora dataset, the searched result GINIGINIGCN:
For Pubmed dataset, the searched result is GCNIIGTT_ LiniiIATTLLnaalllliiieeaatat
For Amazon Computers dataset, the searched result is GeniepathlIGCNIIAAGEE;
For PPI dataset, the searched result is
Cheb
GCN
Geniopath
SAGE
Chob
GCN
GTN
GAT_linear
GCN
GAT
GAT
GIN
GCN
Genieputh
Club
(a) CiteSeer
(b) Cora
(c) PubMed
(d) Amazon Computers
(e) PPI
Figure The searched architectures of NAC on benchmark datasets.
19


Reviews:
[{"review_id": "ogXmmU0PPA", "reviewer": "Reviewer_9TQX", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work firstly proved that GNNs (without activation function) fixed with random weights can make final outputs as good as well-trained GNNs under mild conditions. Based on this foundation, the authors proposed a novel graph neural architecture search method neural architecture coding (NAC). Specifically, NAC holds a no-update scheme on the parameters of GNNs and concentrates on the training of architecture parameters. And the NAC is 200x faster than existed GNN-NAS methods and can find better GNN architecture.", "summary_of_the_review": "    I recommend acceptance. This work proposed a linear complexity GNN-NAS method NAC. And the proposed NAC faster than existed GNN-NAS methods and can find GNNs with better performance than existing GNN-NAS methods. What’s more, the work has a good theoretical foundation. Here are my major concerns:\n\n    1. The conditions of Theorem 3.1 and Theorem 3.3 are very strong. They only apply to some GNNs without activation functions.\n    2. There are errors in servel statement of this paper.  “Graph neural networks behave almost linearly, so they can be simplified as linear networks while maintaining superior performance (Wu et al.,2019b).” They only claim GCN can be simplified as linear networks.\n    3. Considering that the search space is different from the previous methods, it is suggested to add ablation experiments to verify the impact of the search space. \n    4. It is suggested to add training-free NAS methods to related works, such as [1][2].\n    5.  It is suggested to add SOTA GNN methods to related works.\n\n[1] Neural architecture search on imagenet in four gpu hours: A theoretically inspired perspective\n[2] NASI: Label-and Data-agnostic Neural Architecture Search at Initialization\n", "strength_and_weaknesses": "Strength:\n1. The proposed NAC is 200x faster than existing GNN-NAS methods. \n2. Besides, the NAC can find better GNN architectures than existing GNN-NAS methods.\n3. This work has a good theoretical contribution.\n\nWeaknesses:\n1. The assumption is strong and the theory holds for GNNs without activation functions.\n2. There is a lack of experiments on large-scale graph data.\n3. The contrast of SOTA GNN is missing in the experiment.\n4. The GNN architecture searched by the proposed method is not shown.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "oVF3k2drLKh", "reviewer": "Reviewer_GxHc", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper first proposed that on some graph datasets a model with untrained graph layers can perform equally well as trained graph layers, and then proposed a NAS method that exploits this trait to accelerate NAS training.", "summary_of_the_review": "The proposed method works well but under a strong assumption and only on limited datasets. I can only recommend acceptance if authors can clarify my doubts above.", "strength_and_weaknesses": "Strength:\n1. If the data assumption is correct, the proposed method does seem to achieve both better search results in much shorter time.\n2. Some novelty in proposing the sparse coding reformulation of NAS for GNNs.\n\nWeaknesses:\n1. In theorem 3.2, the authors states the assumption: \"data is linearly separable\". I doubt this assumption holds true for all the graph datasets. Is there any proof that this is actually true?\n2. Following the 1st point, GNN layers performing equally well without activation layers are usually observed on simpler GNN datasets using simple features such as Bag-of-words. I have some doubts that this will be the case when GNN datasets gets more complex and the interactions between nodes are more complex, e.g. in particle simulation or protein interaction datasets. In this case I am not sure if the proposed method can still work. Can authors perform experiment on more complex datasets?\n\nMissing citation:\nZhao Y, Wang D, Gao X, et al. Probabilistic dual network architecture search on graphs[J]. arXiv preprint arXiv:2003.09676, 2020.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "d2j10jb8ppU", "reviewer": "Reviewer_WVaT", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors first provide theoretical proof that the untrained GNN models are nearly optimal,\nsecond, propose a novel, based on sparse coding, NAS for GNNs: NAC - neural architecture coding.\nUnlike other NAS methods, NAC, based on the assumption that untrained GNN models are nearly optimal, does not update GNN weights, \nwhat leads to computational cost reduction and optimization stability improvement.", "summary_of_the_review": "In general very interesting paper proposes new insights hoe to design NAS for GNNs in linear time. In addition, the paper is well constructed. \nEven though there are a few weak points, which are summarized in the following questions:\n\n1) Can you please elaborate on your statement that \" GNN models behave almost linearly\"?  I expect to see the theoretical or empirical justification for it. \nThe statement \"Technical motivation for NAC stems from the observation that an untrained GNN performs well, and training it might not provide extra benefit\"\nfills like very strong and should be theoretically or empirically justified, preferable for both transductive and inductive datasets.\n\n2) The proof result is \"the output layer alone can ensure the optimality of the network even when all previous layers have no updates\" \nis strongly relied on skipping all nonlinear activation functions. \nFrom my understanding, skipping all non-linear activations can dramatically reduce neural network feature extraction expressive power. \nWe can simply shrink all layers into a single layer, as a result, do not need depth.\nAgain, can authors provide empirical or theoretical justification for that?\n\n\n3) From my understanding, the objection of NAS algorithms is to provide architectures that can achieve better accuracy than handcrafted architectures. I expect the authors also to add SOTA results of the evaluated datasets to justify the practical impact of the proposed method.\n\n4) The experiments were only done on transductive datasets. It is known that inductive datasets are harder.\nCan authors provide experimental results also for inductive datasets?\n\nPre-rebuttal score: I give 5 (BR), and looking forward to receiving the author's responses to my concerns.", "strength_and_weaknesses": "*Strength*\nThe paper is interesting, and the proposed idea of using sparse coding for NAS in GNNs seems novel.\nThe proposed method seems to outperform previous art in terms of accuracy, taking less time. \n\n*Weaknesses*\nThe paper presents the results only on transductive small datasets and does not provide a sota for comparison.\nAs a result, it is hard to understand the impact of the proposed method NAC.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "JmRlKgveygu", "reviewer": "Reviewer_P1Y6", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers the neural architecture search (NAS) problem specifically for graph neural networks (GNNs). By omitting the effect of non-linearity of GNNs (in terms of the NAS ranking of architectures), i.e., we can linearize the GNNs, and the NAS for GNN problem can be greatly simplified and formulated as a sparse encoding problem, which this paper called neural architecture coding (NAC). This paper first proves the linearized GNN can still achieve optimality under mild conditions (Theorem 3.1-3.3), and then proposes to search/optimize the architecture parameters via the sparse coding method. Experiments show that the proposed NAC method is much faster and accurate than some previous NAS for GNNs baselines.", "summary_of_the_review": "Overall for the current manuscript, I recommend weak rejection. I do like the idea of NAC and agree with its novelty. But I think some rewrites are needed to improve the clarity, especially about the description of the NAC algorithm and related analysis, which could be extended with more details. Moreover, the experiments may also need a bit more recent baselines from the Auto-GNN line of research and, more importantly, evaluation on at least a few larger graphs to support the efficiency claims.\n", "strength_and_weaknesses": "#### Strengths\n1. I like the idea of linearizing the GNNs for the NAS problem and formulating the search of architecture parameters as a sparse coding problem. To my best knowledge, this should be novel in the line of research of NAS for GNNs.\n2. The empirical results look promising compared to the previous methods in terms of performance and efficiency.\n\n#### Weaknesses\n1. One major concern of mine is regarding the clarity of the theory & algorithm parts. I think the major contribution of this work is the NAC algorithm which is described in section 3.2. However, I think the clarity (and length) of section 3.2 could be much improved. In terms of length, I think section 3.1 takes too much space, and I suggest moving the detailed proofs to the appendices. In terms of clarity, I suggest the authors define and describe the concepts/notations with more details. For example, how do we encode/what is the dimensionality of the GNN operator $\\alpha$; is $o^l$ a set function (aggregator) or a normal vector function (as the last line of Eq.(7))? The Eq. (7) is the central contribution and should be explained and analyzed with much greater details. Moreover, the notations and logic in sections 3.1 and 3.2 are somehow disconnected, and it is also hard to understand how is the theorems in section 3.1 useful to the NAC algorithm.\n2. The proposed NAC method outputs the optimal architecture by an argmax in each layer in Algorithm 1, so I think this method should be better understood as a differentiable NAS or Auto-GNN method. Does the author ensure the search space is exactly the same among all baselines, including random search (RS), Bayesian optimization (BO), and GraphNAS in Table 1? Also, is it possible to also consider Auto-GNN (and maybe some newer SOTA methods in that line of research) as a fair baseline?\n3. The evaluation is mostly done on very small graphs, and this is not sufficient to justify the (consistent) advantage of the proposed method on large-scale real-world graphs. Moreover, this paper also claims the efficiency advantages. Thus it would be necessary to evaluate on at least a few larger graphs.\n\n\n#### Minor Issues\n1. The format of the uploaded PDF is not directly generated from LaTeX, i.e., it seems that each page is an image thus, I cannot search/select text, or use the hyperlinks.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "96XT5mMEs5i", "reviewer": "Reviewer_oy8p", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposed one method NAC to automatically design GNNs. With randomly initialized model weights, NAC designs the GNNs by learning the sparse encodings on top of the search space. The empirical and theoretical results demonstrate its effectiveness.", "summary_of_the_review": "This paper proposed one method NAC to automatically design GNNs based on the no-update GNNs. The theoretically analysis and some experiments can be further improved.", "strength_and_weaknesses": "### Strength:\n\nThis paper shows the feasibility of no-update GNNs in graph representation learning, and then applied them into NAS-GNN, which can transfer the bi-level optimization problem to single-level. It is interesting and useful for NAS-GNN.\n\n### Weakness:\n\n1. The optimization gap still exists due to the shared output layer.\nIn Theorem 3.2, one untrained GNN (which is denoted as A^LXO and omits the output layer) can make the final output as good as the well-trained GNNs based on the optimized weights $\\hat{W}^*_o$. It seems that this weight still needs to be trained with the first term of the optimization objective in Eq.(7). Then, the optimization gap cannot be addressed since different architectures also share these untrained weights (W_l) in each layer and the output layer(W_o). When we obtained the optimized weight $\\hat{W}^*_o$ with Eq.(7), this weight is sub-optimal for each candidate architecture in the search space. Therefore, the optimization gap still exists.\n\n2. The constraints on the dictionary D in sparse encoding. The second term in Eq.(3) is ignored in Eq.(7).\n\n3. Some experiments are ignored.\na) This paper only considered the NAS baselines in GNNs. Compared with SANE(Zhao et al. 2021b), the baseline performance is pretty lower.\n\nb) Since this paper remove all the non-linear operations in GNNs. The untrained SGC baseline should be considered. It seems that it is one competitive baseline with Theorem 3.1-3.3.\n\nc) The evaluations on “complex” datasets. As mentioned in Page 8, “the optimal condition can get compromised due to the high complexity of the data.” It seems that the proposed method has difficulty when applied to a complex dataset. However, how to measure the “complexity” of the dataset? Besides, the proposed method aims to learn the sparse encoding for each node, which is equivalent to designing the node-wise GNNs. It would be better to evaluate the proposed procedures, e.g., large-scale datasets ogbn-arxiv.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject