Efficient Graph Neural Architecture Search
Authors: Huan Zhao
Lanning Wei
quanming yao
Zhiqiang He
Venue:  (2021)
Keywords: graph neural network
neural architecture search
automated machine learning

Abstract: Recently, graph neural networks (GNN) have been demonstrated effective in various graph-based tasks.  
To obtain state-of-the-art (SOTA) data-specific GNN architectures, researchers turn to the neural architecture search (NAS) methods. 
However, it remains to be a challenging problem to conduct efficient architecture search for GNN.
In this work, we present a novel framework for Efficient GrAph Neural architecture search (EGAN).
By designing a novel and expressive search space, an efficient one-shot NAS method based on stochastic relaxation and natural gradient is proposed.
Further, to enable architecture search in large graphs, a transfer learning paradigm is designed.
Extensive experiments, including node-level and graph-level tasks, are conducted. The results show that the proposed EGAN can obtain SOTA data-specific architectures, and reduce the search cost by two orders of magnitude compared to existing NAS baselines.

Under review as a conference paper at ICLR 2021
EFFICIENT GRAPH NEURAL ARCHITECTURE SEARCH
Anonymous authors Paper under double-blind review
ABSTRACT
Recently, graph neural networks (GNN) have been demonstrated effective in vari- ous graph-based tasks. To obtain state-of-the-art (SOTA) data-specific GNN archi- tectures, researchers turn the neural architecture search (NAS) methods. How- ever, it remains to be challenging problem to conduct efficient architecture search for GNN. In this work, we present a novel framework for Efficient GrAph Neural architecture search (EGAN). By designing novel and expressive search space, an efficient one-shot NAS method based on stochastic relaxation and natural gra- dient is proposed. Further, to enable architecture search in large graphs, transfer learning paradigm is designed. Extensive experiments, including node-level and graph-level tasks, are conducted. The results show that the proposed EGAN can obtain SOTA data-specific architectures, and reduce the search cost by two orders of magnitude compared to existing NAS baselines.
INTRODUCTION
Recent years have witnessed the success of graph neural networks (GNN) (Gori et al., 2005; Battaglia et al., 2018) in various graph-based tasks, c.g., recommendation (Ying et al., 2018a), chem- istry (Gilmer et al., 2017), circuit design (Zhang et al., 2019), subgraph counting (Liu et al., 2020), and SAT generation (You et al., 2019). To adapt to different graph-based tasks, various GNN mod- els, e.g., GCN (Kipf & Welling, 2016). GAT (Veličković et al., 2018), GIN (Xu et al., 2019), have been designed in the past five years. Most existing GNN models follow a neighborhood ag- gregation (or message passing) schema (Gilmer al., 2017), as shown in the left part of Figure 1, which is that the representation of a node in graph is learned by iteratively aggregating the features of its neighbors. Despite the broad applications of GNN models, researchers have take efforts to design proper GNN architectures given different tasks by imposing different relational inductive biases (Battaglia et al., 2018). As pointed out by Battaglia et al. (2018), the GNN architectures can support one form of combinatorial generalization given different tasks, i.e. graphs. Then a natural and interesting question can be asked: Can we automatically design state-of-the-ar (SOTA) GNN architectures for graph-based tasks? A straightforward solution is to adopt the neural architecture search (NAS) approaches, which have shown promising results in automatically designing archi- tectures for convolutional neural networks (CNN) (Zoph & Le, 2017; Pham et al., 2018; Liu et al., 2019a; Tan & Le, 2019; You et al., 2020a).
However, it is nontrivial to adopt NAS to GNN. The first challenge is to detine the search space. One can design a dummy search space to include as many as possible the related parameters, e.g., aggregation functions, number of layers, activation functions, etc., on top of the message passing framework (Eq. (1)), however, it leads to quite a large discrete space, for example, 315,000 possi- ble GNN architectures are generated by including just 12 types of model parameters in You et al. (2020b)), which is challenging for any search algorithm. The second challenge is to design an effective and efficient search algorithm. In the literature, reinforcement learning (RL) based and evolutionary based algorithms have been explored for GNN architecture search (Gao et al., 2020; Zhou al., 2019; Lai al., 2020; Nunes & Pappa, 2020). However, they are inherently compu- tationally expensive due to the stand-alone training manner. In the NAS literature, by adopting the weight sharing strategy, one-shot NAS methods are orders of magnitude more efficient than RL based ones (Pham et al., 2018; Liu et al., 2019a; Xie et al., 2019; Guo et al., 2019). However, the one-shot methods cannot be directly applied to the aforementioned dummy search space, since remains unknown how to search for some model parameters like number of layers and activation functions by the weight sharing strategy. Therefore, it is a challenging problem to conduct effective and efficient architecture search for GNN.

---

Figure I: An illustrative example GNN model and the propsed BGAN (Best view in color). (a) An example graph with five nodes. The gray rectangle represents the input features of each node; (b) A typical 3-layer GNN model following the message passing neighborhood aggregation schema, which computes the embeddings of node "2"; (c) The DAG represents the search space for 3-layer GNN, and Ox,, 0x, Or represent, respectively, weight vectors for node aggregators, layer aggrega- tors, and skip-connections in the corresponding edges. The rectangles denote the representations, out of which three green ones represent the hidden embeddings, gray (h.) and yellow (h.) ones rep- resent the input and output embeddings, respectively, and blue one (h") represent the set of output embeddings of three node aggregators for the layer aggregator. (d) At the I-th epoch, an architecture Under review as a conference paper at ICLR 2021
0 02
022
(0.4)
0
(a)
(1.2)
DENTITY
EGAN
GAT-SYM
NAX
01 05
(1,4)
DENTITY.
(2,4)
0
GON
GNN
0
0
of
(4.5)
Search process at epoch
(b)
EGAN
(c)
Search Space
AGG
AGG
Layer
aggregator
ABC
AGS
600
AGS
4e Node ragrepatoo
is sampled from p(Z, p(Z,), p(Zz pZZ.), (.))).(Z)) (Z)), whose rows Z,, are one-hot random variable vector indicat- ing masks multipled edges (i,j) the DAG. Columns of these matrices represent the operations from O,,, O., O,
In this work, propose novel framework, called EGAN (Efficient GrAph Neural architecture search), to automatically design SOTA GNN architectures. Motivated by two well-established works (Xu et al., 2019; Garg et al., 2020) that the expressive capabilities of GNN models highly rely on the properties of the aggregation functions, novel search space consisting of node and layer aggregators designed, which can emulate many popular GNN models. Then by representing the search space as a directed acyclic graph (DAG) (Figure I(c)), we design one-shot framework by using the stochastic relaxation and natural gradient method, which can optimize the architecture selection and model parameters in a differentiable manner. To enable architecture search in large graphs, we further design a transfer learning paradigm, which firstly constructs a proxy graph out of the large graph by keeping the properties, and then searches for GNN architectures in the proxy graph, finally transfers the searched architecture to the large graph. To demonstrate the effectiveness and efficiency of the proposed framework, we apply EGAN various tasks, from node-level to graph-level ones. The experimental results on ten different datasets show that EGAN can obtain SOTA data-specific architectures for different tasks, and the same time, reduce the search cost by two orders of magnitude. Moreover, the transfer learning paradigm, to the best of our knowledge, is the first framework to enable architecture search large graphs
Let & = (V,E) be simple graph with node features X E Nxd where V and & represent the node and edge sets, respectively. N represents the number of nodes and d is the dimension of node features. We use ((v) to represent the first-order neighbors of node v in G, i.e., (v)) {u V((v. u) 8). In the literature, also create new set ((r) is the neighbor set including itself, i.e., N(v) = [v) U {u VI(u,u) u) E E}.
Notations,
2 RELATED WORKS
GNN was first proposed (Gori et al., 2005) and in the past five years different GNN models (Kipf & Welling, 2016; Hamilton al., 2017; Veličković et al., 2018; Gao et al., 2018; Battaglia al.,
2

---

Under review as a conference paper at ICLR 2021
2018: Xu et al., 2019; 2018: Liu et al., 2019b; Abu-El-Haija al., 2019; Wu et al., 2019; Zeng et al., 2020; Zhao & Akoglu, 2020; Rong et al., 2020) have been designed, and they rely on a neighborhood aggregation (or message passing) schema (Gilmer et al., 2017), which lears the representation of a given node by iteratively aggregating the hidden features ("message") of its neighbors. Besides, in Xu et al. (2018); Chen et al. (2020), the design of residual networks (He et al., 2016a;b) are incorporated into existing message passing GNN models. Battaglia et al. (2018) pointed out that the GNN architectures can provide one form of combinatorial generalization for graph-based tasks, and Xu et al. (2019); Garg et al. (2020) further show that the expressive capability of existing GNN models is upper bounded by the well-known Ceisfeiler-Lehmall (WL) test. It will be an interesting question to explore GNN architectures with better combinatorial generalization, thus neural architecture search (NAS) can a worthwhile approach for this consideration.
NAS (Baker et al., 2017; Zoph & Le, 2017; Elsken et al., 2018) aims to automatically find SOTA architectures beyond human-designed ones, which have shown promising results in architecture design for CNN and Recurrent Neural Network (RNN) (Liu et al., 2019a; Zoph et al., 2018; Tan & Le, 2019). Existing NAS approaches can be roughly categorized into two groups according to search methods (Bender et al., 2018): i.e. the stand-alone and one-shot ones. The former ones tend to obtain the SOTA architecture from training thousands of architectures from scratch, including reinforcement learning (RL) based (Baker et al., 2017: Zoph & Le, 2017) and evolutionary-basse ones (Real et al., 2019). while the latter ones tend to train a supernet containing thousands of archi- tectures based on the weight sharing strategy, and then extract submodel as the SOTA architecture at the end of the search phase (Pham et al., 2018: Bender et al., 2018; Liu et al., 2019a; Xie et al., 2019). The difference of training paradigms leads that one-shot NAS methods tend to be orders of magnitude more efficient than the RL based ones.
Recently, there are several works on architecture search for GNN, e-g., RL based ones (Gao et al., 2020: Zhou et al.. 2019; Lai et al., 2020), and vvolutionary-based ones (Nunes & Pappa. 2020; Jiang & BBalaprakash, 2020), thus all existing works are computationally expensive. Franceschi et al. (2019) proposes to jointly learn the edge probabilities and the parameters of GCN given graph, thus orthogonal to our work. Besides, Peng et al. (2020) proposes a one-shot NAS method for GCN architectures in the human action recognition task. In Li et al. (2020), sequential greedy search method based on DARTS (Liu et al., 2019a) is proposed to search for GCN architectures, however, the tasks are more focused vision related tasks, with only one dataset in conventional node classification task. In this work, to the best of our knowledge, for conventional node-level and graph-level classification tasks, architecture search, which is thus, in nature, more efficient than existing NAS methods for GNN. In Appendix A.3, we give more detailed discussions about the comparisons between EGAN and more recent GNN models.
the first to design a one-shot NAS method for GNN
3
THE PROPOSED FRAMEWORK
3.1 THE DESIGN OF SEARCH SPACE
As introduced in Section 2, most existing GNN architectures rely on a message passing frame- work (Gilmer et al., 2017), which constitutes the backbone of the designed search space in this work. To be specific, a K-layer GNN can be written as follows: the 1-th layer (I = -,....,. K) updates h, for each node by aggregating its neighborhood as
h a (w((). ((,h Vu E N())))),
where h. E Iddc represents the hidden features of node v learned by the (-th layer, and di is the corresponding dimension. w(O) is a trainable weight matrix shared by all nodes in the graph, and a is non-linear activation function, e.g., a sigmoid or ReL.U. $, is the key component, i.e., a pre-defined aggregation function, which varies across different GNN models.
Thus a dummy search space is to include as many as possible related parameters in Eq. (I), How- ever, it leads to a very large search space, making the search process very expensive. In this work, motivated by two well establiisi works (Xu et al., 2019; Garg et al., 2020), which show that the expressive capabilities of GNN models highly rely the properties of aggregation functions, propose to search for different aggregation functions by simplifying the dummy search space. For other parameters, we do simple tuning in the re-training stage, which is also standard practice in
3

---

Under review as a conference paper at ICLR 2021
existing NAS methods (Liu et al., 2019a; Xie et al., 2019). Then the first component of the proposed search space is the node aggregators, which consists of existing GNN models. To improve the ex- add the other component, layer aggregators, to combine the outputs of node aggregator in all layers, which have been demonstrated effective in JK-Network (Xu et al., 2018). Then we introduce the proposed search space, as shown in Figure ((c), in the following:
pressive capability,
Node aggregators: We choose 12 node aggregators based on popular GNN models, and they are presented in Table 7 in Appendix A. The node aggregator set is denoted by On-
Layer aggregators: We choose 3 layer aggregators as shown in Table 7 in Appendix A.I. Be- sides, we have two more operations, IDENTITY and ZERO, related to skip-connections. Instead of requiring connectonsss between all intermediate layers and the final layer in JK- -K-eework, in this work, we generalize this option by proposing to search for the existence of skip-connections between each intermediate layer and the last layer. To connect, we choose IDENT I TY, and ZERO otherwise. The layer aggregator set is denoted by Oj and the skip operation set by O..
To further guarantee that K-hop neighborhood can always be accessed, we add one more constraint that the output of the node aggregator in the last layer should always be used as the input of the layer aggregator, thus for a K-layer GNN architecture, we need to search K IDENTITY or ZERO for the skip-connection options.
3.2 DITFERENTIBLEE ARCHITECTURE SEARCH
Following existing NAS works (Liu et al., 2019a; Xie et al., 2019), we represent the search space by a directed acyclic graph (DAG), shown in Figure I(c), where nodes represent embeddings, and edges represent operations between the two end nodes. Then the intermediate nodes are
Σ (C (z,(),),
(2)
where Ö.,, is the selected operation at edge (i. In our work, each edge corresponds to an opera- tion in the search space, and represent it with distribution Pex(), which generates the one-hot random variable Zi, multiplied by the operation edge Oz, in the DAG. Then the intermediate nodes in each child graph are represented by
fラ = 3==E. ic (z,(Z:) = = Oz,))..
Note that in our framework, shown in Figure I(c), for each node aggregator, the input is from the previous one, and for the layer aggregators, the input are from outputs of all node aggregators.
Following the setting in Zoph & Le (2017) and Gao et al. (2020), the objective of the framework is
Ez-pp. (2) [R(Z]] Ez-pa (2) [Fw(Z)],
(4)
where R(Z) represents the reward, which defined by training loss Lw (Z) our framework. W represents the model parameters. In the GNN literature, node-level or graph-level classification tasks are commonly used, thus the cross-entropy loss is chosen, leading to a differentiable function of Lw(Z). To make use of the differentiable nature of Lw we design a differentiable search method to optimize Eq. (4). To be specific, we use the Gumbel-Softnn (Maddison et al., 2017: Xie et al., 2019; Noy et al., 2020) to relax the discrete architecture distribution to be continuous and differentiable with the reparameterization trick:
Ei = fas,, (G = exp((log a + G+t)/A)/ Σn exp((loga), + G(,)/A),
(5)
where Zr, is the softened one-hot random variable for operation selection at edge (i,j), and G is the k-th Gumbel random variable, U is a uniform random variable. ai is the architecture parameter. À is the temperature of the softmax, which is steadily annealed to be close to zero (Xie et al., 2019; Noy et al., 2020). Then we can use gradient descent methods to optimize the operation parameters and model parameters together in end-to-end manner. The gradients are given in Appendix A.2.
-
To improve the search efficiency, further design adaptive stochastic natural gradient method to update the architecture parameters in an end-to-end manner following Akimoto et al. (2019). To be specific, the update of at the m-th iteration is given as:
m+1
t pH pH-1. V....
(6)
4

---

Under review as a conference paper at ICLR 2021
where p is the step size. H is the Fisher matrix, which can be computed as H Ep.. m (a (Z)² with Pa (Z) = V log (Z)..
After the searching process terminates, derive the final architecture by retaining the edge with the largest weight, which is the same as existing DARTS (Liu et al., 2019a) and SNAS (Xie ct al., 2019). To make the final results more robust, the search process is executed 5 times with different random seeds, thus 5 architectures are obtained at the end of the search phase. Then the architectures are re-trained from scratch with some hyperparameters tuning on the validation set, and the one with the best validation accuracy is returned as the final architecture.
3.3 TRANSFER LEARNING PARADIGM
As introduced in Hamilton et al. (2017); Jia al. (2020), when training GNN in large graphs, in each batch, the time and memory cost increases exponentially w.r.t. K, i.e., the number of GNN layers, with the worst cases of O(VV)). Obviously, it is extremely expensive in large graphs for any GNN model. The situation becomes more severe when conducting architecture search in large graphs since we are training supernet emulating various GNN models. Therefore, tends to be infeasible to directly search for architectures in large graphs. Motivated by transferring searched blocks and cells in CNN architectures from small to large data sets in the NAS literature (Zoph et al., 2018; Tan & Le, 2019), we propose to address the above problem by transfer learning (Pan & Yang. 2009).
The core idea of the transferable architecture search is to find small proxy graph Spoxy (the source), then search in the proxy graph, finally tune the searched architecture {o.,. Oks, 0u) ) in the large graph 9 (the target). However, in order to make the architecture transfer feasible, we need to make the proxy graph sharing the same property distribution with the original graph (Pan & Yang. 2009). Since the properties vary across different graphs, it is not suitable to transfer across different datasets, like that from CIFAR-10 to ImageNet for image classification (Zoph et al., 2018). Thus, we pro- pose to sample a smaller graph from the original one, and then apply the transfer paradigm. Many praebbrrinnn sampling schema have been proposed in established work (Leskovec & Faloutsos, 2006), e.g., random sampling by node or edge, or sampling by PageRank. In this work, adopt the Random PageRank Node (RPN) sampling method in Leskovec & Faloutsos (2006), which is empirically demonstrated to be able to preserve the properties by sampling not less than 15% nodes from the original graph. In Section 4.2.2, the experimental results shows that this transfer paradigm empirically works well.
Table 1: Comparisons between existing NAS methods for GNN and the proposed EGAN
Search space
Search Algorithm
Able to run in large graphs
Node agg
Layer agg
NrS (Gao et al., 2020)
X
RL
Auto-GNN (Zhou al., 2019)
RL
Policy-GNi GNN (Lai el al.. 2020)
RL
Nunes & Pappa (2020)
X
Evolutionary
X
Jiang & Balaprakash (2020)
Evolutionary
EGAN
Differentiable
3.4 COMPARISONS WITH EXISTING NAS METHODS FOR GNN
In this section, as shown in Table 1, we emphasize the advantages of EGAN in the following:
In terms of the search space, EGAN can emulate more GNN models than existing methods. More- over, by only focusing on the "aggregation function",, the total size of the search space is smaller than those of the previous methods, which also contributes to the efficiency improvements of EGAN
In terms of the search algorithm, the one-shot nature of EGAN makes it much more efficient than stand-alone methods, e.g. GraphNAS.
The transfer paradigm of EGAN makes it feasible to conduct architecture search in large graphs.
Therefore, the advantages of EGAN over existing NAS methods are evident, especially the effi ciency.
4 EXPERIMENTS
In this section, we conduct extensive experiments to demonstrate the effectiveness and efficiency of the proposed EGAN, including node-level and graph-level tasks.
5

---

Under review as a conference paper at ICLR 2021
4.1 SETUP
Datasets. For node-level tasks, we have three settings: transductive, inductive, and transfer. The task node classification on 8 datasets, which are given in Appendix A.4.1. For graph-level tasks, the task is whole graph classification on 2 datasets, which are given in Appendix A.5.
Baselines In general, we have two types of baselines: human-designed GNN models, and NAS methods. Details of baselines are given in Appendix A.4.2. Note that for NAS baselines in Table 1, we only use GraphNAS (Gao et al.. 2020) and its variant using weight sharing (GraphNAS- -S). The search spaces of Auto-GNN (Zhou et al., 2019) and Nunes & Pappa (2020) are the same as GraphNAS, while their codes are not available. Jiang & Balaprakash (2020) is an concurrent work when we are preparing for this submission, and we will compare with it when the codes available. For Policy-GNN (Lai et al., 2020), they work on searching for different numbers of layers per node in selected GNN base model. i.c., GCN or GAT, thus can be an orthogonal work EGAN
Table 2: Performance comparisons in transductive and inductive tasks, whose evaluation metrics mean classification accuracy and Micro-F1, respectively. For the first five GNN models in the table, we present the better performance of each and its JK variants, and the detailed performance of GNN models and their JK variants are in Table 10 in Appendix A.4.5. Note that the performance of LGCN on CS and Computer is "_" due to the OOM (Out Of Memory) problem when running the released code in our GPUs. The results of Geom-GCN are copied from the original paper (Pei al.,
2020), since the data split ratio is the same to our experiments.
Transductive
Inductive
Methods
Cora
CiteSeer
PubMed
CS
Computer
PPI
GCN
0.877(0.012) (.771(0.014) 0.878(0.004) 0.949(0.003) 0.912(0.007) (.934((0.001)
GraphSAGE
0.884 (082)0 0.765(0.005) 0.882(0.007) 0.952(0.002) 0.918(0.004)
0.972(0.001)
Human-
GAT
0.873(0.009) 0.753(0.013)
0.867(0.006) (.934(0.004) 0.918(0.005)
0.978(0.001)
designed
GIN
0.870(0.010) 0.765(0.013) 0.883(0.005) 0.950(0.003) 0.913(0.008) 0.964(0.003)
GNN
GeniePath
0.878 0.759(0.014) 0.882(0.004)
0.926(0.004) 0.883(0.007)
0.964(0.001)
LGGN
(.869().008) 0.754(0.022) 0.875(0.001)
0.772(0.002)
Geom-GCN
0.852"
0.780
0.901
Random
0.86)(0.003) 0.782(0.002) 0.889(0.001) 0.939(0.001) 0.902(0.003) 0. (0.001)
Bayesian
0.808)).003) 0.765(0.002) 0.884(0.001) 0.940)).001) 0.908(0.001) 0.990(0.001)
NAS methods
GraphNAS
0.884 (07) 0.776(0.00) 0.890(0.002) 0.928(0.002) 0.900(0.003) 0.970(0.013)
GraphNAS- WS
0.881(0.010) 0.761(0.016) 0.884(0.010) 0.931(0.002) 0.906(0.002) 0.958(0.042)
|EGAN
0.900(0.001) 0.786(0.011) 0.900(0.001) 0.960(0.003) 0.920(0.003) 0.991
4.2
PERFORMANCE COMPARISON
4.2.1
PERFORMANCE COMPARISONS IN TRANSDUCTIVE AND INDUCTIVE TASKS
From Table 2, we see that EGAN consis- tently obtain better or close performance com- pared all baselines, which demonstrates the effectiveness of the proposed framework. In other words, with EGAN, we can obtain SOTA data-specific GNN architectures. When compar- ing EGAN with GraphNAS methods, the per- formance gain is evident. We attribute this to the expressive search space and the differen- tiable search algorithm. We further visualize the searched architectures in Figure 2, and we see that the searched architectures vary per dataset. More figures can be checked in Figure 6 and in Appendix A.6.3,
UNIEL
ENITEY
MAX
LiT
Cors
bi Cisdieer
Figure 2: The searched architectures on Cora and CiteSeer.
4.2.2 PERFORMANCE COMPARISONS IN TRANSFER TASKS
For the transfer learning experiments, we use two large graphs, i.e., Reddit and Arixv. As introduced in Section 3.3, we firstly sample two smaller graphs (15% nodes), and run EGAN in these two smaller graphs to obtain the optimal architectures, then transfer the searched architectures to the original graphs, finally report the test results in them. In terms of baselines, only report the

---

Under review as a conference paper at ICLR 2021
results of those, which are able reported to, run in the two large graphs, i.e., Reddit and Arxiv. More details are given in Appendix A.4.4.
The results are shown in Table 3. from which orders of magnitude, from GPU days' to less than a minute, which demonstrates the superiority of efficiency of the proposed transfer learning paradigm compared to direct architecture search in large graphs. Moreover, the performance the transferred architectures is better or close to those of the baselines, which demonstrates the effectiveness of the transfer learning paradigm.
that the improvement of search cost in two
Table 3:
Performance comparisons of the transfer task on Reddit and Arxiv, for which we use Micro- Fl and accuracy as evaluation metrics, respectively. Note that the OOM (Out Of Memory) problem occurs when running GraphNAS on these two datasets, thus we do not report its performance.
Reddit
Arxiv
Search cost (GPU hours)
Search cost (GPU
Method
Micro-F1
Method
Accuracy
hours)
Human-designed
GraphSAGE
0.938(0.001)
GCN
0.717(0.003)
GNN
GraphSAGE-JR 0.942(0.001)
GraphSAGE 0.715(0.003)
Random
0.930(0.002)
72
Random
0.691(0.005)
72
NAS methods
Bayesian
0.942(0.001)
72
Bayesian 0.703(0.004)
72
EGAN
0.954(0.000)
0.021
|EGNN
0.715(0.001)
0.003
Table 4:
Performance comparisons on graph classification tasks. We show the mean test accuracy (with standard de- viation) on these datasets. For the first five GNN models in
4.2.3 GRAPH-LEVEL. TASKS
The results of the graph-level task shown in Table 4, and we can see that the performance trending similar to node-level tasks. The searched architectures are shown in Figure 7 in Appendix A.6.3, which also shows that they are data specific. Note that the global pool- ing method, tion, in the whole graph learning can also be incorporated into the search space of EGAN, thus it can also be learned. We leave this for future work.
the table, we present the better performance of each and its JK variants, and the detailed performance of GNN models and their JK variants are in Table 12 in Appendix A.5.3
Methods
D&D
PROTEINS
GCN
0.733(0.043)
0.730(0.026)
GraphSAGE
0.734(0.029)
0.734(0.041)
Human-
GAT
0.716(0.056) 0.745(0.030)
the readout func-
designed
GIN
0.733(0.033) 0.737(0.048)
GNN
GeniePath
0.705(0.051) (.694(0.035)
DiffPool
0.779(0.045) (.738(0.040)
SAGPOOL
0.762(0.009)
0.724(0.041)
ASAP
0.748(0.024)
(0.03))
Random
0.742(0.043) (.733(0.0311)
Taking into consideration the re- sults of all tasks, the effective- ness of the proposed EGAN can be demonstrated.
Bayesian
0.746(0.031) 0.676(0.041)
NAS
GraphNAS
0.719(0.045)
0.725(0.031)
methods
GraphNAS WS
0.758(0.044)
0.752(0.025)
EGAN
0.779(0.034)) 0..7990.0344)..66100..0 0.761(0.039)
4.3 SEARCH EFFICIENCY
In this section, we conduct some experiments to show the superiority of efficiency of EGAN over NAS baselines. And for simplicity, we only use the four commonly used datasets in the node-level task, i.e., Cora, CiteSeer, PubMed, and PPI.
Firstly, we record the running time of each method during the search phase, which represents the search cost of the NAS methods. The results are given in Table 5, from which we can see that the search cost of EGAN is two orders of magnitude smaller than those of NAS baselines.
Secondly, we show the trending of the test accuracy w.r.t the running time of different methods during the search phase. In each epoch, we obtain the best model currently, and report the test accuracy after retraining it from scratch. The result of Cora is shown in Figure 3, from which we
Note that we stop the search process after days.

---

Under review as a conference paper at ICLR 2021
observe that EGAN can obtain architectures with better performance quickly than NAS baselines. More figures are shown Figure Appendix A.6.2.
Taking these results into considcration, the efficiency advantage of EGAN is significant, which is mainly attributed to the one-shot training paradigm as introduced in Section
Transductive task
Inductive task
Cora
CiteSeer
PubMed
PPI
EGAN
Random
1,500
2,694
3,174
13,934
Random
Bayesian
1,631
2,895
4.384
14,543
Bayeslan
GraphNNAS
GraphNAS
3,240
3,665
5,917
15,940
EGAN
14
35
54
298
Elapse time(s) log base 10
Table 5: The running time (s) of each method during the search phase.
Figure 3: Test accuracy W.r.t.
elapsed time on Cora.
4.4 ABLATION STUDY
In this section, we present two ablation studies EGAN.
Firstly, we show the importance of the layer aggregators in the designed search space by running EGAN in the search space without the layer aggregators, and the results shown in Table 6, from which we can see that the performance consistently drops on all datasets except Computer when removing the layer aggregators. This observation aligns with the results in JK-Network (Xu al., 2018) that the performance of GNN models can be improved by adding an extra layer.
Secondly, show the influence of K, i.e., the number of layers of GNN, in the search space, for which we conduct experiments with EGAN by varying layer K E 2,, 3, 4, 5, 6} and show the test accuracy in Figure The results suggest that along with the increment of layers, the test accuracy may decrease. Considering the computational resources, 3-layer architecture is a good choice for the backbone of EGAN in our experiments.
EGAN
layer aggregators(w)
layer aggregators(ww/)
Cara
Cora
0.900(0.001)
0.871(0.001)
0.95
CireSeer
CiteSeer
(0.09()
(.751(0.000)
Test accuracy
0.90
PuaMed
PubMed
0.900(0.001)
0.884(0.001)
PP
CS
0.947(0.001)
0.937(0.001)
0.85
DD
PROTEINS
Computer
0.915(0.003)
0,918(0.001)
PPI
0.990(0.000)
0.974(0.000)
0.75
DD
(0.79(0.034)
(0.610
0.70
Protein
(0.39))
0.758(0.034)
Table 6: Performance comparisons of EGAN using different search spaces.
Figure 4: Test accuracy w.r.t.
different Ks.
CONCLUSION AND FUTURE WORK
In this paper, we propose EGAN, an effective and efficient framework for graph neural architecture search. By designing novel and expressive search space, we propose one-shot NAS framework by stochastic relaxation and natural gradient. Further, to enable architecture search in large graphs, we design transfer learning paradigm. We conduct extensive experiments, including node-level and graph-level tasks, which demonstrates the effectiveness and efficiency of EGAN compared to various baselines.
Based on this work, show that NAS approaches can obtain data-specific GNN architectures. which supports one form of combinatorial generalization for GNN models. For future work, we will explore more aspects regarding the combinatorial generalization of GNN models beyond the aggregation functions, like the construction the graph, or the number layers as done in Policy- GNN (Lai al., 2020), introduced in Battaglia al. (2018).
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Sami Abu-EI-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In ICML, pp- 21-29, 2019.
Youhei Akimoto, Shinichi Shirakawa, Nozomu Yoshinari, Kento Uchida, Shota Saito, and Kouhei Nishida. Adaptive stochastic natural gradient method for one-shot neural architecture search. In ICML, pp. 171-180, 2019.
Bowen Baker, Otkrist Gupta, Nikhil Naik, and Ramesh Raskar. Designing neural network architec- tures using reinforcement learning. ICLR, 2017.
Peter Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanzhez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint 1806.0:800601222
2018.
Gabriel Bender, Pieter-Jan Kindermans, Barret Zoph, Vijay Vasudevan, and Quoe V. Le. Under- standing and simplifying one-shot architecture search. In ICML, pp. 549-558, 2018.
James S Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. Algorithms for parameer optimization. In NeurlPS, pp. 2546,2554, 2011.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In ICML, pp. 3730-3740, 2020.
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. 2020.
Paul D Dobson and Andrew Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of molecular biology (JMB), 731(4))77 2003.
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey. JMLR, 2018.
Matthias Fey and Jan Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLRW, 2019.
Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He. Learning discrete structures for graph neural networks. In ICML, pp. 1972-1982, 2019.
Hongyang Gao, Zhengyang Wang. and Shuiwang Ji. Large-scale learnable graph convolutional networks. In KDD, pp. 1416-1424, 2018.
Yang Gao, Hong Yang. Peng Zhang, Chuan Zhou, and Yue Hu. Graph neural architecture search. In IJCAL, pp. 1403-1409, 2020.
Vikas K Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. pp. 5204-5215, 2020.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George Dahl. Neural message passing for quantum chemistry. In ICML., pp. 1263-1272 2017.
Marco Gori, Gabriele Monfardini, and Franco Scarselli, new model for learning in graph domains. In IJCNN, volume 2, pp. 729-734, 2005.
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. arXiv preprint 100.001904.00420, 2019.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NewrlPS, pp. 1024-1034, 2017.

---

Under review as a conference paper at ICLR 2021
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. CVPR, pp. 770-778, 2016a.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In ECCV, pp. 630 630-645, 2016b.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs, 2020.
Zhihao Jia, Sina Lin, Rex Ying, Jiaxuan You, Jure Leskovec, and Alex Aiken. Rodundancy-free computation for graph neural networks. In KDD, pp. 997-1005, 2020.
Shengli Jiang and Prasanna Balaprakash. Graph neural network architecture search for molecular property prediction, 2020.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. ICLR, 2016.
Kwei-Herng Lai, Daochen Zha, Kaixiong Zhou, and Xia Hu. Policy-gnn: Aggregation optimization for graph neural networks. In KDD, pp. 461-471, 2020.
Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. In /CML, pp. 3734-3743, 2019.
Jure Leskovec and Christos Faloutsos. Sampling from large graphs. In KDD, pp. 631-636, 2006.
Guohao Li, Guocheng Qian, Itzel C Delgadillo, Matthias Muller, Ali Thabet, and Bernard Ghanem. SGAS: Sequential greedy architecture search. In CVPR, pp. 1620-1630, 2020.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. ICLR, 2019a.
Xin Liu, Haojie Pan, Mutian He, Yangqiu Song, Xin Jiang, and Lifeng Shang. Neural subgraph isomorphism counting. In KDD, pp. 1959-1969, 2020.
Ziqi Liu, Chaochao Chen, Longfei Li, Jun Zhou, Xiaolong Li. Song, and Yuan Qi. Geniepath: Graph neural networks with adaptive receptive paths. In AAAI, volume 33, pp. 4424-4431, 2019b.
Chris J Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: A continuous relaxation of discrete random variables. ICLR, 2017.
Asaf Noy, Niv Nayman, Tal Ridnik, Nadav Zamir, Sivan Doveh, Itamar Friedman, Raja Giryes, and Lihi Zelnik. Asap: Architecture search, anneal and prune. AISTAT, pp. 493-503, 2020.
Matheus Nunes and Gisele L Pappa. Neural architecture search in graph neural networks. arXiv preprint arXiv:2008..000 2020.
Sinno Jialin Pan and Qiang Yang. A survey on transfer learning. IEEE Transactions on Knowledge and Data Engineering (TKDE), 1315)):344--159 2009.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuar Chang, Yu Lei, and Bo Yang. Geom-gen Geometric graph convolutional networks. ICLR, 2020.
Wei Peng, Xiaopeng Hong, Haoyu Chen, and Guoying Zhao. Learning graph convolutional network for skeleton-based human action recognition by neural searching. In AAAI, 2020.
Hieu Pham, Melody Guan, Barret Quoc Le, and Jeff Dean. Efficient neural architecture search via parameter sharing. In ICML, pp. 4092-4101, 2018
Ekagra Ranjan, Soumya Sanyal, and Partha P Talukdar. Asap: Adaptive structure aware pooling for learning hierarchical graph representations. In AAAI, pp. 1470-5477, 2020.
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoe V Le. Regularized evolution for image classifier architecture search. In AAAI, volume 33, pp. 4780-4789, 2019.
10

---

Under review as a conference paper at ICLR 2021
Yu Rong. Wenbing Huang, Tingyang Xu, and Junzhou Huang. convolutional networks on node classification. In ICLR, 2020.
Dropedge: Towards deep graph
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):93-93, 2008.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv: /./.:886,, 2018.
Mingxing Tan and Quoe Le. Efficientnet: Rethinking model scaling for convolutional neural net- works. In ICML, pp. 6105-6114, 2019.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. ICLR, 2018
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, 2019.
Sirui Xie, Hehui Zheng, Chunxiao Liu, and Liang Lin. SNAS: stochastic neural architecture search. In ICLR, 2019.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In ICML, pp. 5449-5458, 2018
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2019.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In KDD, pp. 974-983, 2018a.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hi- erarchical graph representation learning with differentiable pooling. In NeurlPS, pp. 4800-4810, 2018b.
Jiaxuan You, Haoze Wu, Clark Barrett, Raghuram Ramanujan, and Jure Leskovec. G2SAT: Learning to generate sat formulas. In NeurIPS, pp. 10553-10564, 2019.
Jiaxuan You, Jure Leskovec, Kaiming He, and Saining Xie. Graph structure of neural networks. In ICML, pp. 327-337, 2020a.
Jiaxuan You, Zhitao Ying, and Jure Leskovec. Design space for graph neural networks. volume 33, 2020b.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- Saint: Graph sampling based inductive learning method. ICLR, 2020.
Guo Zhang, Hao He, and Dina Katabi. Circuit-GNN: Graph neural networks for distributed circuit design. In ICML, pp. 7373, 2019.
Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. ICLR, 2020.
Kaixiong Zhou, Qingquan Song, Xiao Huang, and Xia Hu. Auto-GNN; Neural architecture search of graph neural networks, 2019.
Barret Zoph and Quoe Le. Neural architecture search with reinforcement learning. ICI.R, 2017.
Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoc V Le. Learning transferable architectures for scalable image recognition. In CVPR, pp. 8697-8710, 2018.
11

---

Under review as a conference paper at ICLR 2021
A APPENDIX
A.1 DETAILS OF NODE AGGREGATORS
As introduced in Section 3.1, we have 12 types of node aggregators, which are based on well- known existing GNN models: GCN Kipf & Welling (2016), GraphSAGE Hamilton al. (2017), GAT Veličković et al. (2018), GIN Xu et al. (2019), and GeniePath Liu et al. (2019b). Here we give key explanations these node aggregators in Table 8. For more details, we refer readers the original papers.
Table 7: The operations we use as node and layer aggregators for the search space of EGAN, Details of node aggregators are given Table
Operations
SAGE SUM, SAGE-MMAN, SAGE-MAX, SAGE-I-ST GCN, GAT,GAT-SYM, GAT-COS, GAEAR, GAT-GEN-LINEAR, GTN, GeniePath
On
CONCAT, MAX, LSTM IDENTITY, ZERO
Table 8: More explanations to the node aggregators in Table
GNN models
Symhol in the puper
Key explanations
GCN (Kipf & Welling, 2016)
GCN
(x)
Σ
(degree(1)) degrre(())) 1/2 -1/) bf-
we ((w)
SALE-MEAS SAGR-KAX,
GrahSAGGE (Hamilton et al., 2017)
Apply mean, max, sum, or LSTM operatioo to (hu/u e (())).
SAGB- SUM,
SAGE LSTM
GAT
Compute attention score: 2 Leaky ReI.Ula W.h. W.h.
GAT-SYN
GAT (Veličkovic et al., 2018)
GAT-C38
8. W.h. W.h.).
GAT-LINEA
E. lunh W.,h, + W..b.)
GAT GEN LINEAR
C = Westanb (W..h, + W.h.).
GIN (Xu et al., 2019)
GTN
(x)))) MI. (1 (1-)) b/-1
b
LGCN (Gao et al., 2018)
CNN
Use CND as the aggregator.
GeniePath
CanieFash
Composition
LSTM bused apgregators Depending on the base above GNN
JK-Network (uu et al., 2018)
A.2 GRADIENTS OF L
Here give the gradients of Lad (Z) w.r.t the hidden embeddings, model parameters, and the architecture parameters, which is in the following:
Oc Σ
ac Z 80 (I,)) dx,
dx; m>j drm
0c OL zh (0.,(m))
aw 1.j Oz,
owh,
OC Oc O (z;)) - k)) Li, VZ. Xa
da da,
For full derivation, we refer readers to the appendix of Xie et al. (2019).
A.3 DISCUSSION ABOUT RECENT GNN METHODS
Very recently there were new GNN models proposed in the literature, e.g., MixHop (Abu-El- Haija et al., 2019), Geom-GCN (Pei et al., 2020), GraphSaint (Zeng et al., 2020), DropEdge (Rong al., 2020), PariNorm (Zhao & Akoglu, 2020), PNA (Corso al., 2020). We did not include all
12

---

Under review as a conference paper at ICLR 2021
these works into the search space of EGAN, since they can be regarded as orthogonal works of EGAN to the GNN literature, which means they are very likely to further increase the performance when integrating with EGAN.
As shown in Eq. (1), the embedding of a node e in the I-th layer of a K-layer GNN is computed as:
hy oWW" AGG _ Vu E (()))))
From this computation process, we can summarize four key components of GNN model: aggre- gation function (oGG) number of layers (O, neighbors (N())), and hyperparameters (a, dimen- sion size, etc.), which decide the properties of GNN model, e.g., the model capacity, expressive capability, and prediction performance.
To be specific, EGAN mainly focus the aggregation functions, which affect the expressive pability of GNN models. GraphSaint mainly focuses on neighbors selection in each layer, thus the "neighbor explosion" problem can be addressed. Geom-GCN also focuses on neighbors selection, which constructs a novel neighborhood set in the continuous space, thus the structural information can be utilized. DropEdge mainly focuses on the depth of GNN model, i.e., the number of layers, which can alleviate the over-smoothing problem with the increasing of the number of GNN layers. Besides the three works, there are more other works on the four key components, like MixHop (Abu- El-Haija et al.. 2019) integrating neighbors of different hops in a GNN layer, or PairNorm (Zhao & Akoglu, 2020) working on the depth of GNN models, and PNA (Corso et al., 2020) is a more recent GNN model, which proposes composition of multiple aggregation functions in each GNN layer. Therefore, all these works can integrated as a whole to improve each other. For example, the DropEdge Geom-GCI, methods can further help EGAN in constructing more powerful GNN models. With PNA, we can use our framework to help search for the combinations of multiple ag- gregation functions in a single GNN layer, or include the PNA aggregator to our search space to see whether it can help further enhance the final performance. This is what we mean "orthogonal" works of EGAN. Since mainly focus on the aggregation functions in this work, we only compare the GNN variants with different aggregations functions.
Moreover, one purpose of this work is not design the most powerful search space include all aspects, but to demonstrate that the proposed EGAN, including the search space and search method, provides an alternative option enhance GNN architecture search. We believe the application of NAS to GNN has unique values, and the proposed EGAN can benefit the GNN community.
A.4 EXPERIMENT SETUP OF NODE-LEVEL TASKS
A.4.1 DATASETS
Table Dataset statistics of the datasets in the experiments. Here we use "CS", "Computer", as the abbreviations for Coauthor CS and Amazon Computers, respectively.
Transductive
Inductive
Transfer
Cora
CiteSeer
PubMed
CS
Computer
PPI
Reddit
Arxiv
#nodes
2,708
3,327
19,717
18,333
13,752
56,944
232,965
169,343
#edges
5,278
4.552
44.324
81,894
245.861
818,716
57,307.946
1,166,243
#fcatures
1,433
3,703
500
6,805
767
121
602
128
#classes
7
6
3
15
10
50
50
40
Transductive Setting Only subset of nodes in one graph are used as training data, and other nodes are used as validation and test data. For this setting, we use three benchmark dataset: Cora, CiteSeer, PubMed. They are all citation networks, provided by (Sen al., 2008). Each node represents paper, and each edge represents the citation relation between two papers. The datasets contain bag- of-words features for each paper (node), and the task is to classify papers into different subjects based on the citation networks.
Besides the three benchmark datasets, puters, provided by (Shchur et al., 2018). Coauthor CS a co-authorship graph where nodes are authors which are connected by an edge if they co-author a paper. Given paper keywords for each
two more datasets: Coauthor CS and Amazon Com-
13

---

Under review as a conference paper at ICLR 2021
author's paper as node features, the task is map each author its most active field of study. Ama- zon Computers is segments of the Amazon co-purchase graph where nodes represent goods which are linked by an edge if these goods are frequently bought together. Node features encode product reviews as bag-of-word feature vectors, and class labels are given by product category.
For all datasets, We split the nodes in all graphs into 60%, 20%, 20% for training, validation, and test. For the transductive task, we use the classification accuracy as the evaluation metric.
Inductive Setting In this task, unseen graphs as validation/test data. For this setting, we use the PPI dataset, provided by (Hamilton al., 2017), on which the task is to classify protein functions. PPI consists of 24 graphs, with each corresponding to human tissue. Each node has positional gene sets, motif gene sets and immunological signatures as features and gene ontology sets labels. 20 graphs are used for training. 2 graphs are used for validation and the rest for testing, respectively. For the inductive task, we use Micro-F1 the evaluation metric.
number of graphs as training data, and other completely
Transfer Setting In this task, we use two datasets, Reddit and Arxiv, which are two orders of mag- nitude larger than Cora and CiterSeer in number of nodes, as shown Table 9. The Reddit dataset is provided by Hamilton et al. (2017), and the task is to predict the community to which different Reddit posts belong. Reddit an online discussion forum where users comment on different top- ics. Each node represents post, and each edge represents link between two posts, when they are commented by the same user. The dataset contains word vectors as node features. The graph constructed from Reddit posts made in the month of September 2014, and follow the same settings the original paper (Hamilton et al., 2017), which uses the first 20 days for training and the remaining days for test (with 30% used for validation).
The Arxiv dataset is constructed based on the citation network between all papers, and we use the specific version of oggon-arxi v. provided by recent open graph benchmark (OGB) project (Hu et al., 2020), where the task is to predict the 40 subject areas of Arxiv CS papers, c.g., cs.Al, cs.LG. Each node (paper) has 128-dimensional feature vector obtained by averaging the embedding of words in its title and abstract. And all papers are also associated with the year that the corresponding paper was published. The dataset split by time. To specific, papers published before 2017 are used as training data, while those in 2018 and 2019 are used, respectively, as validation and test set. For more details, we refer readers to Hu et al. (2020).
A.4.2 COMPARED METHODS
We compare EGAN with two groups of ofate-of-the-ar methods: numan-designed GNN architec- tures and NAS methods for GNN.
Human-designed GNNs. We use the following popular GNN architectures:
GCN (Kipf& & Welling, 2016) proposes a sum aggregator normalized by the degrees nodes.
GraphSAGE (Hamilton et al., 2017) proposes scalable graph neural network with different aggre- gators: Mean, Sum, Pool, LSTM.
GAT (Veličković et al., 2018) proposes the attention aggregators, and it has different vari- ants according to the attention functions: GAT, GAT-SYS, GAT-LINEAR, GAT-COS, GAT- The detail these attention functions are given in (Gao et al., 2020).
GENERALIZED-LINEAN
GIN (Xu et al., 2019) proposes to use Multi-layern Perceptron (MLP) aggregators.
LGCN (Gao et al., 2018) proposes to automatically select topK neighbors for each node, and use the 1-D regular convolutional operation as the aggregator.
GeniePath (Liu al., 2019b) proposes a composition of attention and LSTM-style aggregators, which can learn adaptive neighborhood for each node.
Geom-GCN (Pei et al., 2020) propose a geometric bi-level aggregation schema over structure- aware neighbors in continuous space and neighbors by adjacency matrix.
For models with variants, like different aggregators in GraphSAGE or different attention functions in GAT, we report the best performance across the variants. Besides, extend the idea of JK- Network (Xu et al., 2018) in all models except for LGCN, and obtain 5 more variants: GCN-JK, GraphSAGE-JK, GAT-JK, GIN-JK, GeniePath-JK, which add an extra layer. In the experiments,
14

---

Under review as a conference paper at ICLR 2021
only report the better performance of each GNN and its JK variant, which is denoted by the original name, as shown in Table 2, and 4, respectively.
For LGCN, use the code released by the authors For other basclines, we use the popular open source library Pytorch Geometric (PyG) (Fey & Lenssen, 2019) (Version: 1.6.0,, which implements various GNN models. For all baselines, hyperparameters on validation datasets, and get the test performance. We repeat this process for times, and report the final mean accuracy with standard deviation.
train it from scratch with the obtained best
NAS methods for GNN. We consider the following methods:
Random search (denoted as "Random") is a simple baseline NAS, which uniformly randomly samples architectures from the search space, and keeps track of the optimal architecture during the search process.
Bayesian optimization' (denoted as "Bayesian") (Bergstra al., 2011) popular sequential model-based global optimization method for hyper-parameter optimization, which uses tree- structured Parzen estimator as the metric for expected improvement.
GraphNAS' (Gao al., 2020). a NAS method for searching GNN architecture, which is based on reinforcement learning (Zoph & Le, 2017).
Random and Bayesian are searching on the designed search space EGAN, where a GNN ar- chitecture is sampled from the search space, and trained till convergence to obtain the validation performance, 5000 models are sampled in total and the architecture with the best validation per- formance is trained from scratch, and do some hyperparameters tuning on the validation dataset, and obtain the test performance. For GraphNAS, we set the epoch of training the RL-based con- troller 5000, and in each epoch, a GNN architecture is sampled, and trained for enough epochs (600 ~ 1000 depending on datasets), update the parameters of RL-based controller. In the end, we sample 10 architectures and collect the top 5 architectures that achieve the best validation accuracy. Then the best architecture is trained from scratch. Again, we do some hyperparameters tuning based on the validation dataset, and report the best test performance. Note that we repeat the re- re-training of the architecture for five times, and report the final mean accuracy with standard deviation.
Note that for human-designed GNN models and NAS methods, for fair comparison and good balance between efficiency and performance, choose set the number of GNN layers to be 3, which is an empirically good choice in the literature (Veličković et al., 2018; Liu et al., 2019b).
A.4.3 IMPLEMENTATION DETAILS OF EGAN
Our experiments are running with Pytorch (version 1.6.0) on GPU 2080Ti (memory: 12GB, cuda version: 10.2). We implement EGAN on top of the building codes provided by PyG (version 1.6.0) and SNAS 6. For all tasks, we run the search process for 5 times with different random seeds, and retrieve top-1 architecture each time. By collecting the best architecture out of the 5 top-1 architectures on validation datasets, we repeat 5 times the process in re-training the best one, fine- tuning hyperparameters on validation data, and reporting the test performance. Again, the final mean accuracy with standard deviations are reported.
In the training stage, we set the search epoch to 600 for all datasets except PPI (150), and the learning rate to 0.005, Le norm to 0.0005, dropout rate to 0.5. In the fine-tuning stage, each architecture is trained from scratch with 600 epochs.
A.4.4 BASELINES IN TRANSFER LEARNING
On Reddit, we follow the same settings of GraphSAGE in the original paper (Hamilton et al., 2017), except that we use a 3-layer GNN backbone to search, while GraphSAGE use 2-layer. Since the performance of Reddit is only reported in GraphS (Hamilton et al., 2017) and JK-Network (Xu
hhaps:/gghhbb.cm//oooaagggaaaa
"htps://gihub..oo/////// hwppyorcchhhtttcchooo...cccec
15

---

Under review as a conference paper at ICLR 2021
al., 2018), we them as human-designed architectures. Note that the authors of JK-Network did not release their implementation, thus we use the implementation by the PyG framework. To keep consistent, we also use the implementation for GraphSAGE by the PyG framework. For Arxiv, follow the same setting in OGB project (Hu et al., 2020), where only two buman-designed architec- tures, GCN and GraphSAGE, are tested, thus use these two human-designed architectures.
For NAS baselines, we use the same NAS approaches in transductive and inductive tasks: Random, Bayesian, GraphNAS, and GraphNAS-WS, and run them directly the original graphs, i.e., Reddit and Arxiv. However, since the code of GraphNAS and GraphNAS-WS crashed due to out of memory error, we only report the performance of Random and Bayesian. Besides, we report the search cost in terms of GPU hours to compare the efficiency of different methods.
A.4.5 PERFORMANCE COMPARISONS OF GNN MODELS AND JK VARIANTS
The detailed performance of GNN baselines and their JK variants in Section 4.2.1 are in Table 10.
Table 10: Performance comparisons between the five GNN models and their JK variants. For sim- plicity, we report the better one of each in Table 2.
Transductive
Inductive
Cora
CiteScer
PubMed
CS
Computer
PPT
GCN
0.876(0.010) 0.766(0.020) 0.871(0.003) 0.935(0.005) 0.912(0.007) 0.933(0.002)
GCN-JK
0.877(0.012) 0.771(0.014) 0.878(0.004) 0.949 (0.003) 0.910(0.000) (00(0000)))))0 0.934(0.001)
GraphS
0.874(0.00) (02))) 0.760(0.009) 0.878(0.004) 0.933(0.005) 0.915(0.003) 0.972(0.001)
GraphSAGE-JK
0,884(0.002 (0.00) 0.765((0.0)) (0.5)) 0.882(0.007) 0.952(0.002) 0.918(0.004) (..72(0.000))
GAT
0.872(0.016) 0.752(0.014) 0.857(0.007) 0.929(0.003) 0.917(0.006) 0.978(0.001)
GAT-JK
0.809(0.009) 0.753(0.013) 0.867(0.006) 0.934(0.004) 0.918(0.005) 0.978(0.001)
GIN
0,860 )000) 0.734(0.014) 0.880(0.005) 0.921(0.005) 0.867(0.041) 0.959(0.005)
GIN-JK
0,870(0.010) 0.765(0.013) 0.883(0.005) 0,950(0.003) 0.913 (00)00000))00
0.964(0.003)
GeniePath
0.867(0.012) 0.759(0.014) 0. 0.880(0.004) 0.926(0.004) 0,861
(.950()
GenicPath-JKK
0.878(0.012) 0.759(0.012) 0.882(0.004) 0.925(0.005)
0.883(0.007)
0.964(0.000)
A.5 EXPERIMENT SETUP OF GRAPH-LEVEL TASKS
A.5.1 DATASETS
Table 11: The statistics of datasets in graph-level tasks.
Dataset
Num. Graphs
Classes
Avg. Number of Nodes
Avg. Number of Edges
D&D
1,178
2
384.32
715.66
PROTEINS
1,113
2
39.06
72.82
In this section, we evaluate EGAN on graph classification task two datasets: D&D and PROTEINS datasets, provided in Dobson & Doig (2003). These two datasets are both the protein graphs. In D&D dataset, nodes represent the amino acids and two nodes are connected iff the distance less than Á. In PROTEINS dataset, nodes are secondary structure elements and edges represent nodes are in an amino acid or in close 3D space. More information are shown in Table 11.
A.5.2 BASELINES
Besides the GNN baselines in node-level tasks, we use three more methods, which use hierarchy pooling to learn whole graph representation given the embeddings of all nodes. DiffPool (Ying et al., 2018b), SAGPool (Lee et al., 2019) and ASAP (Ranjan et al., 2020) are latest methods based on hierarchical pooling schema, which learn node embeddings with node aggregators and coarsen graphs with pooling aggregators. The final graph embeddings based on the final coarsend graph. DifiPool learns a soft assignment matrix for each node with any GNN methods, combine with entropy regularization and link prediction objective, that the
generated by a readout operation
16

---

Under review as a conference paper at ICLR 2021
coarsened graph can preserve much information possible. SAGPool learns node weights with attention mechanism and keeps the top-k nodes in pooling layer. In ASAP, it learns a soft cluster assignment matrix for each node with self-attention mechanism, and calculates the fitness score for each cluster and select top-k clusters.
For other methods, including GNN models in node-level tasks and NAS methods used in Table 4, to obtain the representation of a whole graph, we use the global sum pooling method at the end of retraining the derived architecture, i.e., the whole graph representation is obtained by the summation of the embeddings all nodes. Eiey b(k)., K is the number of GNN layers.
In this section, tation details are presented in A.4.3. After finding the best architecture and tuning the hyperparam- eters, we report the mean accuracy and standard deviations 10 folds data.
10-fold cross-validation accuracy as the evaluation metric, and the implemen-
In the search stage, we set the search epoch to 150, and the learning rate to 0.01, L2 norm to 0.0005, dropout rate to 0.5. In the re-training stage, each architecture is trained from scratch with 100 epochs.
A.5.3 PERFORMANCE COMPARISONS OF GNN MODELS AND JK VARIANTS
The detailed performance of GNN baselines and their JK variants in Section 4.2.3 are Table 12.
Table 12:
Performance comparisons between the five GNN models and their JK variants. For sim- plicity, we report the better one of each in Table 4.
D&D
PROTEINS
GCN
0.727(0.039)
0.727(0.026)
GCN-JK
0.733(0.043)
0.730(0.026)
GraphSAGE
0.734(0.029)
0.734(0.031)
GraphSAGE-JK
0.728(0.047)
0.730(0.035)
GAT
0.713(0.052)
0.734(0.037)
GAT-JK
0.716(0.056)
0.745(0.030)
GIN
0.732(0.030)
0.736(0.028)
GIN-JK
0.733(0.033)
0.737(0.048)
GeniePath
0.704(0.039)
0.670(0.045)
GeniePath-IIe
0.705(0.051)
0.694(0.035)
A.6 MORE EXPERIMENTAL. RESULTS
Table 13: Performance comparisons of two search spaces on four benchmark datasets. We show the mean classification accuracy (with STD).
Methods
Cora
CiteSeer
PubMed
PPI
GraphNAS
0.884(0.007)
0.776(0.006)
0.890(0.0022 (00)))
0.970(0.013)
GraphNAS-WS
(0.81()
0.884(0.010) (0.66))
0.958(0.042)
GraphNAS (Our search space)
(.883(0.002) 0.890(0.005)
0.771(0.006)
0.888(0.001)
0.989(0.001)
GraphNAS-WV WS (Our search space)
0.770(0.007)
0.894(0.001)
0.988(0.001)
A. THE ADVANTAGE OF THE PROPOSED SEARCH SPACE
In Section 3.1, we discuss the advantages of search space between EGAN and GraphNAS/Autto GNN. this section, we conduct experiments to further show the advantages. To specific, we run GraphNAS over its own and EGAN's search space, given the same time budget (20 hours), and compare the final test accuracy the searched architectures in Table 13. From Table 13, we can that despite the simplicity of the search space, EGAN can obtain better or at least close accuracy compared to GraphNAS, which means better architectures can be obtained given the same time budget, thus demonstrating the efficacy of the designed search space.
17

---

Under review as a conference paper at ICLR 2021
A.6.2 TEST ACCURACY DURING THE SEARCH PHASE
In this section, compare the efficiency of EGAN and NAS baselines by showing the test accu- racy w.r. the running time, as shown in Figure 5, from which we can observe that the efficiency improvements are in orders of magnitude, which aligns with the experiments in previous one-shot NAS methods, like DARTS (Liu et al., 2019a).
3ccurscy
0.78
Test accuracty
Test accurroy
0.99
0.96
0.00
0.04
0.14
FGAN
Random
Random
Random
Bayosian GrophNAS
Bayesian
Boyesian
GraphNAS
GraphNAS
Elasse timels) in log base 10
Elapsa timels) log base 10
Elapse timels) log base 10
(a) CiteSeer.
(b) PubMed.
(c) PPI.
Figure 5: Test accuracy w.r.t. elapsed time CiteSeer, PubMed, and PPI.
A.6.3 MORE SEARCHED ARCHITECTURES
SAGE MEAN
EREAR DIENIIY
SAGS MEAN
Pig
MAX
11p
CONTAT
ft
LSSK
3) PubMed
b) Cs
Computer
DOCITY
LOGARR
CAT JENDAR
74p
CONCAT
Ptg
COS
hg
d) PPI
c) Reddit
Figure 6: The searched architectures more datasets in node-level tasks.
IDENUITY
DENTLY
GENHIPATI
GAT LINEALL IENNITT
/t
Ttp
-ty
GTN
CIN
GIN
h
DD
PROTEINS
Figure 7: The searched architectures datasets in graph-level tasks.
A.7 MORE HYPERPARAMETERS
For all GNN baselines in node-level tasks, the Adam optimizer, and set learning rate Ir 0.005, dropout = 0.5, and Lg norm to 0.0005. For other parameters, we do some tuning, and present the best ones in Table 14.
18

---

Under review as a conference paper at ICLR 2021
On Reddit, the parameters for GraphSAGE and GraphSAGE-JK are follows: Ir 0.005, dropout
p = 0.5, and L2 norm to 0.0002, = 3, d = 64, relu, epoch=30; For EGAN, = 0.006, dropout
p 0.3, and L2 norm to 0.0005.
On Arxiv, the parameters of EGAN are as follows: Ir = 0.025, dropout = 0.5, and L2 norm to 0.0005.
For all searched GNN architectures, the tuned hyperparameters are shown Table 13.
Table 14: More implementing details of GNN baselines. Here we give hidden dimension size, activation function, and the number of heads (GAT models). For JK-Network, further give the layer aggregators.
Cora&CiteSeer
PubMod
Computer
PPI
D&D
PROTEINS
GCN
64, clu
256,
ehu
64,
GribhSAGE
64, relu
128. relu
64, relu
128, relu
256, elu
64,
128. clu
GAT
64, relu, 8
128, relu. 8
16, rolu, 8
16, relu,
256, relu, 8
64, clu, 4
clu,
128, relu
128,
128, relu
relu
256,
32, clu
clu
LGCN
128.
128,
256, relu
GeniePath
256, tanh
256, tanh
128, tanh
128, tanh
256, tanh
32,
16, clu
JK Network
CONCAT
CONCAT
CONCAT
CONCAT
LSTM
CONCCT]
CONCAT
Table 15: The hyperparameters obtained by hyperopt in the fine-tuning process for the searched architectures in Figure 2, 6, and 7. For all GAT aggregators, we set the number of head to for simplicity, which empirically works well in experiments.
Cora
CiteSeer
PubMed]
CS
Computer
PPI
Reddit
Arxiv
D&D
PROTEINS
Hidden size
32
64
256
256
64
1024
256
128
16
64
Learning rate
3.120-3
3.937c-3
4,484-3
3.164e-3
2.111o-3
1.036-33
5,4400-5
3.019e-3
3.8670-2
2.334p-2
La
3.08c-5
2.007e-5
466-4
2.46844
3.31e-4
0
1.995-55
6.979e-5
2.16e-4
5.46-44
Activation function
clu
elu
clu
clu
clu
elu
relu
relu
elu
elu
Dropout rale
0.
0.7
0.6
0.6
0.5
0.5
0.4
0.4
0.3
0.3
A.8 COMPARISONS WITH SNAS AND DARTS
In this section, to further demonstrate the efficiency of EGAN compared to DARTS (Liu et al., 2019a) and SNAS (Xie al., 2019), we further record the trending of validation accuracy of the supernet by rumning them on the same search space during the search phase. These results are shown in Figure 8, from which we can see that EGAN can obtain larger validation accuracy more quickly than than SNAS and DARTS, which is attributed to the usage of natural gradient in Eq. (6).
BSAN
B5AN
230
308
300
500
880
130
350
300
180
(a) Cora.
(b) CiteSeer.
(c) PubMed.
(d) PPI.
Figure 8: Validation accuracy w.r.t. elapsed time on CiteSeer, PubMed, and PPI.
19


Reviews:
[{"review_id": "hvOAe9je5Yl", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents a differentiable NAS method named EGAN for automatically designing GNN architectures. The main contribution is searching GNN architectures efficiently with an one-shot framework based on stochastic relaxation and natural gradient method. Extensive experiments conducted on node-level and graph-level tasks show the efficiency and effectiveness of the proposed search method.\n\nPros:\n\n+ Paper is well-written and easy to follow;\n+ The proposed search space with node aggregators, layer aggregators is interesting;\n+ The design of the baseline methods including random and bayesian search is appreciated;\n+ Empirical results on different datasets and tasks are very strong.\n\nCons:\n\n- Limited novelty, the proposed search method is very similar to SNAS (Xie et al., 2018) except the search space;\n- A similar one-shot search method for GNN has been proposed in SGAS (Li et al., 2020) which weakens the claimed contribution of being the first one-shot NAS method for GNNs;\n- It is not clear why stochastic natural gradient method is needed;\n- The performance of GraphNAS with EGAN’s search space (Table 11) is close to the performance EGAN (Table 2). Therefore, the performance gain mainly comes from the well-designed search space;\n- There is a lack of comparison of the models' parameters across different search methods. Thus, it is not clear whether the experiments are conducted under a fair setting.\n\nOther Comments:\n\n* The obtained architecture in Figure 2 b) includes SAGE. But it is not clear which aggregator is using;\n* The contribution in terms of transfer learning is weak since the proxy graph is a subsample of the large graph. The identical nodes have been exposed during the search phase.\n\nReferences:\n* Xie, S., Zheng, H., Liu, C. and Lin, L., 2018, September. SNAS: stochastic neural architecture search. In International Conference on Learning Representations.\n* Li, G., Qian, G., Delgadillo, I.C., Muller, M., Thabet, A. and Ghanem, B., 2020. Sgas: Sequential greedy architecture search. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (pp. 1620-1630).\n\nPost rebuttal Comments:\nThank the authors for the detailed response. I keep my rating as 5.", "extra_scores": {}, "extra_text": {}}, {"review_id": "he_p37FzoZE", "reviewer": "AnonReviewer4", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: The paper proposes a framework for efficient architecture search for graphs. This is done by combining a differentiable DARTS-like architecture encoding with a transfer learning method, that searches on smaller graphs with similar properties, and then transfers to the target graphs. The experiments show that EGAN matches or exceeds both hand-designed and NAS-designed GNNs. Moreover, the method is very fast to run.\n\nRecommendation: Overall, I am voting to reject, as several crucial pieces of information are missing from the current draft, and some other parts are unclear. The most novel part of the paper seems to be the transfer of architectures learned on subgraphs to larger graphs, but there is little discussion on how that impacts downstream accuracy, or if the transfer learning is at all needed given that the method is already very efficient. Moreover, there is no information on how the choice of method used to select subgraphs affects the entire framework. The experimental results look promising, but there should be more care taken to assess statistical significance.\n\nMain pros:\n1. The general concept of adapting ideas from DARTS to work with Graph Neural Networks is fairly natural.\n2. The set of tasks that are considered is broad, and the comparison is performed across a range of baselines.\n3. Selecting subgraphs with similar properties to the full graph, searching for good architectures on those, and then transferring to the full task, is a very interesting idea.\n\nMain cons:\n1. The transfer learning method is only described very briefly, which leaves several open questions\n- How much are the graphs reduced? Section 3.3 mentions 15% of original size, but it's unclear if that concerns the framework presented in the paper, or is that a value advocated for in some related work. It is also unclear if that refers to number of nodes or number of edges; surrounding text seems to suggest the former, but then the GNN running time will be more affected by the latter.\n- What is the empirical impact of the reduced graph size on running time?\n- As the proposed method seems to be very fast, is it unfeasible to run the search on the full graphs? This would allow to estimate how much accuracy is lost due to searching on a proxy task instead of using the target task, and how that changes as one varies the graph sizes for the proxy task.\n- The paper mentions using Random PageRank Node to select the subgraphs; I wonder how that choice affects the results as opposed to doing something more trivial (e.g. dropping nodes and/or edges uniformly at random).\n2. The bolding of results (Tables 2, 4, 6) is a bit misleading, since many of the differences do not seem statistically significant (e.g. Computer, Proteins) or are even zero (D&D). It would be better to perform a statistical significance test, and make the statistical significance clear by bolding several joint top values.\n3. From Appendix 3.2, I understand that most baseline results were produced by the authors (as opposed to copying the numbers from related works). How were the hyperparameters for the different baselines tuned? In particular, I'm concerned about the last paragraph on page 14, which mentions that the number of layers for all models was fixed to 3. As the number of layers is one of the most important GNN hyperparameters, I'm not sure if simply fixing it to 3 for all baselines is entirely fair.\n\nOther comments:\n- The paper says that the output of the last GNN layer is always used by the layer aggregator, motivating it as injecting relational bias. My understanding is that this just ensures there are no \"dead ends\" in the resulting computational graph, which is a common idea in NAS works; I'm not sure how relational bias is related to this.\n- [1] defines two variants of the Gumbel Softmax trick: besides the basic one, there's also the straight-through variant, which uses hard (i.e. one hot) samples on the forward pass, and the soft approximations (as defined in Equation 5) on the backward pass. Which variant did the authors use?\n- The paper motivates the transfer learning approach by saying that a k-layer GNN needs to process k-hop neighbours, the number of which can be exponential in k. This seems to suggest the GNN running time grows exponentially with k, which is of course not true; in fact, every GNN propagation step requires the same amount of compute, proportional to the number of nodes and edges in the graph.\n- The first dot in Section 3.4 says that EGAN is better than existing GNN-NAS methods, as it has a larger (and thus more expressive) search space, but then goes on to say that EGAN is also better as it has a smaller (and thus cheaper to search) search space. This feels a bit contradictory; it would be fine to just state that the EGAN search space has a different focus (i.e. searching only over the \"core GNN propagation + aggregation\" part).\n- [2] report several simple (hand-designed) GNN variants that get 0.992 on PPI.\n- Table 3 reports that searching on the Arxiv dataset took 10 seconds. How is that even possible? As far as I understand, the architecture search involves training a supernet (containing 12 different aggregation types for each of the 3 GNN layers, among other things) for some number of epochs, repeating that process 5 times for different seeds, and then retraining the best architecture from scratch. Can you comment on how long each of these stages takes?\n- In the GNN literature, results on D&D and Proteins (Table 4) are reported in two different ways: some papers (e.g. [3]) report the validation set results as the final metric (despite it being available to the model selection procedure), while others (e.g. [4]) report the result on the test set (which was not seen by any part of the pipeline). I understand the authors follow the latter strategy - can you confirm?\n- Appendix 4.2 says \"we use the global sum pooling method at the end of retraining\" - what does that mean?\n- Reading the paper feels a bit bumpy, since there are some sentences that are hard to read, and therefore could be revised. Examples (I include only part of each sentence, just to make it identifiable):\n  - Page 2: \"In the literature, we (...)\"\n  - Page 4: \"Note that in our work (...)\"\n  - Page 6: \"Jiang & Balaprakash (2020) is (...)\"\n  - Page 7: \"First,, we (...)\", \"Second, we (...)\"\n  - Caption of Table 5\n  - Page 16: \"For other methods, (...)\"\n\nSmall remarks, typos, and grammar issues (did not influence my rating recommendation):\n- The EGAN abbreviation may be a bit misleading, since one could assume it refers to Generative Adversarial Networks\n- Abstract: \"SOAT\"\n- Page 1: \"one shot methods NAS methods\"\n- Page 1: \"in orders more efficient\" -> \"orders of magnitude more efficient\"\n- Pages 1 & 8: missing space after citation\n- Pages 2 & 3: \"for the best of our knowledge\" -> \"to the best of our knowledge\"\n- Page 3: \"computational\" -> \"computationally\"\n- Equation 1: l should be in parenthesis\n- Page 3: \"have been demonstrated effectiveness\" -> \"have been demonstrated effective\"\n- Page 4: \"kth\" -> \"k-th\"\n- Page 5: \"To robust the final results\" -> \"To make the final results more robust\"\n- Page 8: \"BY\"\n- Page 13: \"feature vector obtains\" -> \"feature vector obtained\"\n- Page 16: \"as evaluate metric\" -> \"as the evaluation metric\"\n- Throughout the paper: \"In this part\" -> \"In this section\"\n\nReferences:\n- [1] Categorical Reparameterization with Gumbel-Softmax\n- [2] GNN-FiLM: Graph Neural Networks with Feature-wise Linear Modulation\n- [3] How Powerful are Graph Neural Networks?\n- [4] A Fair Comparison of Graph Neural Networks for Graph Classification\n\n----------------------------------------------------------------------------------------------------\n\nComments after rebuttal:\n\nI would like to thank the authors for their detailed response. Many things were addressed, and I have increased my score to 5 to reflect that the paper is not far from acceptance threshold. I think the main thing missing is a discussion of the effect of the sampling of subgraphs: i.e. showing that PageRank is indeed better than choosing nodes at random, and analysing how the results change when the reduction percentage is varied (between a low value and the maximum value that fits in GPU memory).", "extra_scores": {}, "extra_text": {}}, {"review_id": "HlKyj_yzwiq", "reviewer": "AnonReviewer1", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents a NAS method for graph-structured learning, which focuses on constructing a search space tailored to Graph Neural Networks (based on different node aggregators, skip-connections and layer aggregators).\nIn contrast to related GNN-NAS approaches, the authors apply a one-shot training paradigm, where model parameters and network architectures are learned simultaneously in an end-to-end fashion.\nTo enable NAS in large graphs, authors further apply a transfer learning scheme, where the optimal architecture is first learned on a sampled subgraph and model parameters are fine-tuned later on in the original graph.\nThe empirical evaluation includes experiments for node classification and graph classification, on which the proposed approach constantly performs better than or on par with human-designed GNNs, while being more efficient than related NAS approaches.\n\nThe paper is easily comprehensible, although it contains some typos and grammatical flaws.\nThe proposed approach is inspired by the idea to allow different GNN operators for different layers (adhering to different expressive capabilities), which is quite interesting and a fairly ignored topic in current literature.\nIn some sense, this is related to PNA [1], and it would be great to discuss this relationship in the paper.\nThe experiments look promising, showing both the strength of the proposed approach in terms of performance as well as in efficiency compared to related NAS approaches.\n\nThe training architecture and the model parameters are learned simultaneously (based on a Gumbel softmax formulation) via gradient descent.\nAs far as I understand, this requires the model to compute the output of every possible search state in every optimization step, which does not seem to scale to larger search spaces.\nIs my understanding correct? And if so, how can the proposed method scale to larger search spaces?\nFurthermore, other hyperparameters are tuned later on, e.g., dropout ratio or hidden feature dimensionality, which might prevent finding the \"right\" architecture in the first place.\nFurthermore, this manual hyperparameter tuning might make the efficiency comparison to related NAS approaches somewhat unfair.\n\nAdditional comments:\n\n* Eq. (4) refers to optimizing the network architecture based on training loss performance, while in general, one wants to find hyperparameters/network architectures that perform good on the validation set. Please clarify.\n\n* Some baseline results are a bit weak and do not reflect the results reported in the official papers, e.g., for PPI and Reddit. For example, the GraphSAGE paper reports 95.4 micro F1 score on Reddit, while the paper reports 93.8.\n\n* The transfer learning experiments do not seem that convincing to me (given my previous comment regarding Reddit results and the performance on ogbn-arxiv compared to a human-designed GNN). I personally think that the transfer learning idea has potential, but may need more work in order to see clear benefits.\n\n* Is there some intuition why specific architectures win over others? Which architectures generally perform better than others? Can there be guidelines extracted for better GNN architecture design decisions?\n\n[1] Corso et al.: Principal Neighbourhood Aggregation for Graph Nets (NeurIPS 2020)\n\n=================== Post Rebuttal Comments ===================\n\nI would like to thank the authors for their insightful rebuttal and clarifications.\n\nMost of my concerns have been properly addressed, and I very much appreciate the discussion about PNA. However, since the authors train a \"SuperNet\", it is not particular clear to me why one even needs to decide for a specific aggregation scheme (in contrast to PNA), e.g., by simply using the softmax function instead of the gumbel softmax formulation.\n\nFurthermore, I'm still not that convinced about the transfer learning proposal. In my opinion, a more in-depth analysis is needed (both theoretical and practical) to justify the claims made in the paper. Since GNNs do not even need to be trained in full-batch mode (i.e. via GraphSAGE, Cluster-GCN, GraphSAINT, ...), I'm not sure which benefits the proposed approach brings to the table in comparison to any other scalable methods.\n\nTherefore, my rating will stay the same.", "extra_scores": {}, "extra_text": {}}, {"review_id": "DkLzaRbXwz2", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nThis work proposes an efficient graph neural architecture search to address the problem of automatically designing GNN architecture for any graph-based task. Comparing with the existing NAS approaches for GNNs, the authors improves the search efficiency from the following three components: (1) a slim search space only consisting of the node aggregator, layer aggregator and skip connection; (2) a one-shot search algorithm, which is proposed in the previous NAS work; and (3) a transfer learning strategy, which searches architectures for large graphs via sampling proxy graphs. However, the current performance improvement over the human-designed models is marginal, which diminishes their research contribution.\n\nThe paper organization is clear, but some expressions should be improved. The details are listed as below.\nTypos: In the Abstract, state-of-the-art should be abbreviated as SOTA, not SOAT.\nTypos: $L_\\theta(Z)$ after Equation (4) is not defined. Should it be $L_W (Z)$ as used in Equation (4)?\nClarity: The explanation before Equation (5) is a bit confused, which should be re-organized. There is grammar error (the absence of sentence subject) in the first sentence: “however, in this work, to make use of the differentiable nature of Lθ(Z), and design a differentiable search method to optimize Eq. (4).”\nClarity: The notations related to variable $Z_{i, j}$, i.e., $Z_{i, j}^T$ and $Z_{i, j}^k$,  are not defined well. What is the difference between the super-scripts: T and k?\n\nThe pros of this work are summarized in terms of three components used in EGAN, which improves the search efficiency. The experiment results show that their framework greatly reduce time, comparing with the GraphNAS, Bayesian search and random search.\n\nMajor questions:\n(1) In Introduction: we doubt that designing proper GNN architectures will take tedious efforts. As far as I know, the architecture parameters of the human-designed models do not require extensive tuning efforts on the testing benchmark datasets. Furthermore, most of the architecture parameters could be shared and used among the testing datasets to achieve the competitive performances.\n(2) It is unclear for the second challenge: the one-shot methods cannot be directly applied to the aforementioned dummy search space. There are some one-shot models with the parameter sharing strategy used for searching the hidden embedding size. \n(3) In Section 3.1, why is the dummy search space very large? The search space seems only to include the aggregators and hidden dimensions. It might be much smaller than the search space of CNNs.\n(4) Their search space assigns skip connections between the intermediate layers and the final layer, which is contradictory to the common case where the skip connections could be applied among the intermediate layers. As shown in [1], the skip connections may exist between any two layers. Could you provide reasons on the design of skip connection limitation? \n(5) In the node and graph classification of the experimental section, the performance improvement over the human-designed is marginal. This would not justify the motivation of applying NAS to search graph neural networks. The authors should provide more discussions on the contribution of this work in terms of research and industrial applications. \n(6) The marginal performance improvement might result from the search space. Currently, the authors’ search space is based on the traditional message passing approaches. They should consider more the recent developments in GNNs to further improve the performance. \n(7) The selection of baselines is unfair. The search space contains the skip connection components based on the JK-Network. However, authors excluded the important baseline in [2], which could achieve the comparable performance on dataset Citeseer and Reddit. For the graph classification task, authors also excluded a lot of pooling methods, such as the Graph-u-Net [3], which achieves the better performance than the proposed approach.\n\n[1] Rong, Yu, et al. \"Dropedge: Towards deep graph convolutional networks on node classification.\" International Conference on Learning Representations. 2019.\n[2] Xu, Keyulu, et al. \"Representation learning on graphs with jumping knowledge networks.\" arXiv preprint arXiv:1806.03536 (2018).\n[3] Gao, Hongyang, and Shuiwang Ji. \"Graph u-nets.\" arXiv preprint arXiv:1905.05178 (2019)\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a differentiable neural architecture search method for GNNs using Gumbel softmax-based gating for fast search. It also introduces a transfer technique to search architectures on smaller graphs with similar properties as the target graph dataset. The paper further introduces a search space based on GNNs message aggregators, skip connections, and layer aggregators. Results are presented on several undirected graph datasets without edge features on both node and graph classification.

The reviewers mention that the results are promising, but they unanimously agree that the paper does not meet the bar for acceptance in its current form. I tend to agree with the reviewers in that the effect of the individual contributions (search space vs. method vs. transfer) needs to be better disentangled and studied independently, and that it is unclear why selecting a single aggregation function out of many is important vs. choosing multiple ones at the same time such as in PNA [1] as pointed out by R1. This should be carefully studied going forward. Lastly, all reviewers agreed that the proposed transfer method requires more detailed experimental validation and motivation.

[1] Corso et al.: Principal Neighbourhood Aggregation for Graph Nets (NeurIPS 2020)
Decision: Reject