Graph Differentiable Architecture Search with Structure Learning
Authors: Yijian Qin
Xin Wang
Zeyang Zhang
Wenwu Zhu
Venue: NeurIPS 2021 Poster (2021)
Keywords: neural architecture search
graph neural architecture

Abstract: Discovering ideal Graph Neural Networks (GNNs) architectures for different tasks is labor intensive and time consuming. To save human efforts, Neural Architecture Search (NAS) recently has been used to automatically discover adequate GNN architectures for certain tasks in order to achieve competitive or even better performance compared with manually designed architectures. However, existing works utilizing NAS to search GNN structures fail to answer the question: how NAS is able to select the desired GNN architectures? In this paper, we investigate this question to solve the problem, for the first time. We conduct a measurement study with experiments to discover that gradient based NAS methods tend to select proper architectures based on the usefulness of different types of information with respect to the target task. Our explorations further show that gradient based NAS also suffers from noises hidden in the graph, resulting in searching suboptimal GNN architectures. Based on our findings, we propose a Graph differentiable Architecture Search model with Structure Optimization (GASSO), which allows differentiable search of the architecture with gradient descent and is able to discover graph neural architectures with better performance through employing graph structure learning as a denoising process in the search procedure. The proposed GASSO model is capable of simultaneously searching the optimal architecture and adaptively adjusting graph structure by jointly optimizing graph architecture search and graph structure denoising. Extensive experiments on real-world graph datasets demonstrate that our proposed GASSO model is able to achieve state-of-the-art performance compared with existing baselines.

Graph Differentiable Architecture Search with Structure Learning
Yijian Qin, Xin Wang, Zeyang Zhang, Wenwu Zhu"
Tsinghua University
qiny 1reyj110mails..mmm tsinguua edu cn, rin_sangotsinghua.ede cn 2y zy-2hang200mails tsinghua. edu. en, wwzhu@tsinghua. edu,
Abstract
Discovering ideal Graph Neural Networks (GNNs) architectures for different tasks is labor intensive and time consuming. To save human efforts, Neural Architecture Search (NAS) recently has been used to automatically discover adequate GNN architectures for certain tasks in order achieve competitive mance compared with manually designed architectures. However, existing works utilizing NAS search GNN structures fail to answer the question How NAS is able to select the desired GNN architectures. In this paper, we investigate this question solve the problem, for the first time. We conduct theoretical analysis and measurement study with experiments to discover that gradient based NAS methods tend to select proper architectures based on the usefulness of different types of information with respect to the target task. Our explorations further show that gradient based NAS also suffers from noises hidden in the graph, resulting in searching suboptimal GNN architectures. Based on our findings, we propose Graph differentiable Architecture Search model with Structure Optimization (GASSO), which allows differentiable search of the architecture with gradient descent and is able to discover graph neural architectures with better performance through employing graph structure learning denoising process in the search procedure. Extensive experiments on real-world graph datasets demonstrate that proposed GASSO model is able to achieve the state-of-the of-the-arttttttt performance compared with existing baselines.
better perfor-
1 Introduction
In real-world applications including social networks, e-commerce, traffics, and biochemistry, variety of relational data can be represented graphs. This motivates the advent of graph neural networks (GNNs) based models such as GCN D. GAT 2 and GIN (3) which are designed learn and extract knowledge from the relational graph-structured data. To utilize information in graph structure and node features, GNNs follow recursive message passing scheme where nodes aggregate information from their neighbors in each layer, making great success in various graph related tasks. Given that discovering ideal GNN architectures for different tasks is labor intensive and time consuming, graph architecture search 4 5
employs the ideas of neural architecture search (NAS) 6 to facilitate the automatic design of optimal GNN architectures so that a large number human efforts can be saved. These automatically generated GNNs achieve competitive or even better performance compared with manually designed GNNs on graph related tasks.
Nevertheless, existing works graph architecture search mainly focus on designing search space and search strategy, ignoring the fundamental mechanism in adopting NAS for automatic GNN
Conresponding Authors. Our code will be released at
35th Conference on Neural Information Processing Systems (NcurIPS 2021), virtual.

---

hidden feature smoothness loss
original graph
denolsed graph
node classification
joint optimization neural architecture and graph structure
0
0
super network
training loss
final architecture
Figure I: Overview framework of the proposed GASSO model, where the original graph and super network architecture are jointly optimized, hidden feature smoothness loss and training loss are proposed to optimize the neural architecture and graph structure. Then the learned architecture is adopted on the denoised graph, giving predictions of target nodes.
structure search and failing to answer the following questions. (i) How does graph architecture search select its desired architectures? and (ii) How optimal the architectures selected by graph neural architecture search? Answers to these questions can help us to understand the NAS and GNN mechanism in gathering messages, leading to design better GNN structures for certain tasks. However, the failure of existing works in answering the questions significantly limits their capabilities of designing powerful GNN architectures.
In this paper, we answer the above question through exploring how graph neural architecture search able to select the desired GNN architectures. Given that neural architecture search approaches in literature can be mainly categorized into several groups, i.c., gradient based (DARTS [8), reinforce- ment learning based, evolution algorithm based, and Bayesian optimization based methods, we only focus on gradient based architecture search approach this work and leave investigations into the other groups future works. We theoretically analyze DARTS behavior and find that DARTS prefers operations who can help to correct the predictions on hard data. Further analysis on graph data shows that different operations fit graphs with different amount of information in the node features and graph structures. Measurement study via designing synthetic experiments corroborates our theory. We find that DARTS on GNN able evaluate the usefulness information hidden node features and graph structure with respect to the target task, then automatically select appropriate operations based on the evaluated usefulness for GNN architecture. On the other hand, we also discover that the performance of gradient based graph architecture search (e.g., DARTS) can also be deteriorated by noises inside the graphs, leading to suboptimal architectures.
To solve the problem, we propose Graph differentiable Architecture Search model with Structure Optimization (GASSO), which allows differentiable search of the architecture with gradient descent and is capable of searching the optimal architecture as well as adjusting graph structure adaptively through joint optimization scheme. The graph structure adjustment in our proposed GASSO model serves as an adaptive noise reduction to enhance the architecture search performance. The framework of GASSO shown in Figure I We employ differentiable graph structure to allow us to optimize graph structure by gradient based methods during the training process, and we use hidden feature smoothness to evaluate the edge importance and constrain edge weights. Overall, we jointly optimize the parameters of neural architecture and graph structure in an iterative updating manner. We evaluate our model on several widely used graph benchmark datasets including CiteSeer, Cora and PubMed. The experimental results show that our proposed GASSO model can outperform state-of -oe---fftheeeeeee the-art methods and demonstrate better denoising ability than existing graph architecture search model using DARTS and other GNNs models. To summarize, this paper makes the following contributions: (1) We theoretically explore how graph neural architecture search is able to select the desired GNN architectures, the best of knowledge, for the first time, showing that i) gradient based graph

---

architecture search prefers operations who can help to correct the predictions on hard data, and ii) different operations fit graphs with different amount of information in the node features and graph structures. (2) We design measurement study with experiments to show that i) gradient based graph architecture search able to select operations based on the usefulness of the information in graphs, and ii) noises in graph features and structures can deteriorate the architecture search performance. (3)We propose Graph differentiable Architecture Search model with Structure Optimization (GASSO), which searches the optimal architecture well as adjusts graph structure adaptively through a joint optimization scheme. Experimental results on several graph benchmark datasets demonstrate the superiority of our GASSO model against state-of-the the-art methods.
2
Related Work
2.1 Graph Neural Network
follows a neigh- borhood aggregation scheme. At each iteration, representations of nodes are generated through aggregating their neighbors' representations. For instance, graph convolutional neural network (GCN) [ takes the average of all neighbor nodes' features as aggregation. Different from GCN, Graph Attention Network (GAT) (2 treats neighbors unequally. It calculates the attention on each neighbor. Therefore, the aggregation can emphasize representations of more important neighbor nodes with larger attentions. The vectorized representation of a given node in the graph after k iterations can capture both structural (topological) and semantic (attributed) information within the region of the target node's 's k-hop neighborhood. As such, GNN characterizes the whole graph by aggregating node representations [4], making themselves achieve the state-of-the-ar results for tasks including node and graph classifications. Like other types of deep neural networks, GNNs are vulnerable to noise and adversarial attacks. Graph attackers usually adopt data perturbation by changing the node features or graph structure [13 How to denoise and defend graph adversarial attacks is also a popular question 17-19]. Graph structure learning is presented in recent GNN methods (2) Since graph structure plays an important role in GNN scheme, certain noise in the original graph is extremely harmful to GNNs. Graph structure learning aims to generate a clean graph during the training procedure. To achieve this, prior constraints such as low rank and smoothness are utilized. Learning a new graph structure improves the model's 's ability of denoising, as well as its robustness to adversarial attacks of GNNs.
As an effective framework for graph representation learning, GNN 13 13
2.2 (Graph) Neural Architecture Search
Recent years have witnessed a significant surge in research on automated machine learning, including hyper-paramett optimization (23 26 and Neural Architecture Search (NAS) methods [6 27
aim at designing an neural architecture automatically for certain tasks, Since the architecture search space is discrete, reinforce learning G 7 and evolution algorithm [1 32 are often used in NAS methods. Besides, transferring the discrete architecture search space into differentiable space is another strategy for solving the NAS problems. DARTS (8] and SNAS [33] construct a super network where each operation is mixed by all candidate operations, making it possible to update the architecture as well as the weights simultaneously through the classical gradient descent method. NAS has also been applied to graph tasks, achieving competitive performance with the state-of-the-art performances. Existing works [4, 5 34 36 mainly focus on defining a proper search space and search strategy for GNNs. However, the mechanism of NAS methods to select architectures and the relationship between NAS methods and GNN denoising ability have not been noticed.
Exploring Architecture Search for Graph
3.1 Preliminaries: Differentiable Architecture Search
We use DARTS g
representative NAS method with both conciseness and effectiveness as the directed acyclic
exploration object in this paper. In DARTS, neural architecture is represented graph (DAG) where the input data is the source node, the output the sink node, and the edges represent operations (c.g. GCN layer, or linear layer) adopted on the data. Following micro
3

---

search space setting, DARTS only searches which operation should be selected and how the nodes in the DAG should be connected. The calculation inside each operation is predefined.
There are two phases in DART'S procedure, the searching phase and the evaluation phase. In searching phase, super network (shown in Figure I is constructed, where edges exist between each two nodes, i.c., eij exists, YO S < j S N - 1. Each edge is a mixed operation that can be calculated by
exp(n?g]
o(x;), where x; is the output of node i, O is candidate operation (i5(x:) = EoEO Edeo (
set, a is learnable architecture parameters. After calculating the mixed weighted sum, each node aggregates all input edges by x, Eiez Cic (x:). As such, all possible operations all possible positions are contained in the super network. DARTS uses gradient based methods to optimize both architecture parameters a and operation parameters by a bi-level optimization scheme. Since the parameters are all trained in the super network, W of different architectures shared with each other, the mathematical formulation is as follows:
min Lea AA) s.t. W = argminw (A) A)-
(1)
Here, I(AA) is architecture distribution learned in the searching phase. In this formulation, W and A are independently learned, improving the search efficiency.
At the end of the training procedure, the operation with the maximum a of each node is chosen, and the selected operations compose the optimal architecture. Then comes to evaluation phase, new network based on the designed architecture is constructed. This network will be trained from scratch and finally get tested after retraining.
3.2 Theoretical Analysis of Architecture Parameters
We next explore the DARTS behavior on graph task, aiming to answer (i) how does graph neural architecture search select its desired architectures? and (ii) how optimal are the architectures selected by graph neural architecture search? We firstly provide theoretically analysis on (i).
Mixed operation is the key part in DARTS, where the architecture parameters controls the operation selection. However, there no theoretical analysis on how these architecture parameters change according to the performance of different operations. To explore how these architecture parameters change during training procedure, we firstly analyze simple scene of a binary classification problem, and there is only one layer with two candidate operations needs searching in the super network.
exp(o1) The mixed operation is F((x)) (xx) + 02.2(xx). Here, 01 explon +ezploz) and 02
(xp [oa] fi and f2 are candidate operations. We use gradient methods to minimize binary cross entropy loss combined with sigmoid function: H(F) ExIu< Ino F(xx)) + yk) 1n(1 af ((xx))))] Then we can conduct following theorem with proof Appendix A.1.
explaz)
Theorem
The changes of operation weights on after one step of gradient descent w.r.t architecture parameters depend on the score E [y [x<]]] where wi = a (F((x))) - yk- Specifically, if
Ex [n(wxfa(xx)] then 01 increases and 02 decreases, and vice versa.
Theorem I tells us that DARTS judges different candidate operations by score, which can be seen as a weighted sum of logits. As for the weights, we have We E (-1, whether is positive or negative depends on the data label. If yı O, the weight is positive number o ([F(x)) )). which means those data with bad prediction given by the super network have larger weights. If only considering those scores with positive weights, the candidate operation giving better prediction has smaller logits. Summing them up will get smaller score and increase architecture weight On, We can reach a similar conclusion if we analyze data with label yı 1. In nutshell, know DARTS prefers those operations which can help to correct the predictions over hard data.
3.3 Synthetic Graph Experiment Setting
We further construct a synthetic graph which is composed of 600 nodes with 10 types, 60 nodes per type. The node features of certain type follow a Gaussian distribution N(us; 01) (to be simple, we write one-dimension Gaussian distribution here, all dimensions are the same and independent, the same below), where (4; is sampled from another Gaussian distribution (0, 02). σi and 02 are predefined parameters. Here use 3 da to represent the difficulty of classifying nodes by

---

their features. If 3 is large, entra-group node features are close while inter-group node features are far away ("group" denotes node label here), thus easy to classify nodes by their features, vice versa. This difficulty also reflexes the ratio of noises and type-relevant information inside the features.
As for the edges, also two parameters p1 and p2- p1 is the probability of generating edge between two intra-group nodes while P2 is that of two inter-group nodes. We define = pa can reflex the difficulty of classifying nodes by message passing scheme. If 8 is large, intra- nodes appear more often in the neighborhood, making it easier classify nodes by aggregating neighborhood information, and vice versa. This difficulty also reflexes the ratio of noises and lype-relevant information inside the graph structure.
Ri which
We generate synthetic graphs with different 3 and 6, then split the nodes in supervised setting for node classification task. To theoretically explore how different operations behave under different settings, we analyze a simple scene here. We only consider one target node, which is connected with only classes of nodes, one is the same as its own class. The node feature channel is 1. The candidate operations only contain linear and GCN M1 they can represent two types of operations, pessage-passing operations and those without message passing.
Theorem
Under our synthetic graph setting, let be the number of edges connected the target node, the relative distance between the centers of two classes is D). which follows D) ~ N (0,, B²). Then, the probability of that linear operation gives more accurate prediction than GCN on the target
node is P +b
/2n D
(8+1) (1 ()(n+)
The proof of Theorem 2 is in Appendix A.2. Theorem 2 shows that the information gained by different operations are influenced by 3, 6 and n. When 3 increases, the expectation of [D] increases, thus the probability to choose linear increases. When 8 increases, the probability to choose GCN increases. the number of edges can influence the probability as well, but weaker than and ò.
04
0.2
6.0
0.3
9.3
5.0
beta
02
4.0
9.
6.1
2.0
gcn
get
arma edge mr GNN
linear skip
0.6
gen
gat
gin
arma edge
linear skip
(a) heat
heat2
Figure 2: The frequency of GNNs appeared in optimal architecture in different graph setting
3.4 Operation Selection
To discover how and influence DARTS in practice, we generate synthetic graphs by controlling one variable when we change the other one. We set [3 0.4 while changing ö, and set = 4.0 while changing 3. For each setting of ,9 and we generate 100 different graphs and adopt DARTS on We choose GCN (1). GAT 2 GIN 3. MRCony (37), EdgeConv (38), linear, skip connect and zero operation as the candidate operations in DARTS. We set the number of operations to be Since GNNs usually are very shallow, mainly explore DARTS behavior operation selection but not the connections. We count the times of each operation that appears in the optimal architecture and show the frequency in Figure
According to the results above, we found that for different graphs, DARTS suggests using different operations. To be more specific, for graphs with more structure information (large 8) less feature information (small 3), DARTS tends to select typical message passing operations, such as GIN. When there is less structure information (small 8) and more feature information (large 13, DARTS is more likely to select operations like linear and skip connect to prevent message passing. The results agree with Theorem 2
5

---

Table The GNN performances under different settings of the searching phase and evaluation phase. "S" indicates the setting of searching phase. "E" indicates the setting of evaluation phase. All the results are average of 100 runs the variances of each result are listed Appendix C.I. Left: under different B. Right: under different 6.
E
0.2
0.3
0.4
0.5
0.6
6.0
5.0
3.0
2.0
S
0.2
56.4
70.9
82.0
87.9
91.6
6.0
93.4
88.4
80.6
68.9
55.1
0.3
55.5
73.1
85.1
91.7
94.4
5.0
94.2
90.1
83.6
79.2
62.9
0.4
52.3
73.1
86.5
93.0
96.3
4.0
94.2
91.3
86.3
79.2
70.5
=
0.5
48.5
72.7
88.6
96.1
98.6
3.0
92.9
91.0
88.7
85.8
82.1
3
0.6
43.0
69.4
88.1
96.3
99.0
6
2.0
86.8
86.3
85.8
85.4
84.8
Here we can give some explanations for (i) by combining two theorems and the experiment results. A GNN can be regarded as an information extractor, which collects useful messages inside the graph to give accurate node classification. The operations in the search space have different ability to extract information from node feature and graph structure, e.g., GCN has the ability to extract information from graph structure but reduce the influence of the node's 's own feature, while linear only uses the feature information and ignores graph structure. DARTS aims to find the optimal information extractor to help correct the prediction of the super network. To achieve this, it should judge how the node feature and graph structure useful for the task. If the graph structure is useful, DARTS will take advantage of it and select operations that can extract information from the topology. If the node features are useful, DARTS will decide to prevent message passing to make full use of the features.
In addition, we can find that the heat map of the two experiment results are very similar, revealing that DARTS judges the relative amount of the two types of information but not the absolute amount. This also agrees with Theorem [ e.g., as long as node features are more useful than graph structure, the structure thought have certain noise that is harmful to the task, so message passing is preferred to be prevented.
On denoising issue. We have concluded that DARTS has the ability to judge which part inside the graph is useful and select proper operations. This behavior motivates us to test the denoising ability of DARTS. When random noise perturbs clean graph, DARTS can rejudge the usefulness of these two parts and give new architecture suggestions according to the current condition. Thus DARTS may have denoising ability. We make experiments on real graph datasets in Section [5] The results show its denoising ability is unstable. Therefore, we move on to explore how accurate DARTS selects operations.
3.5 Accuracy of Operation Selection
To further explore the answer to (ii), save the architectures searched on graphs with each 3 and ā in Figure 2 and transfer them on graphs with different settings to do the evaluation. We also control one variable while changing the other one. The results are shown in Table [
Following normal sense, the architecture searched on a graph should perform well on the same graph, ie., the elements on the main diagonal in the tables should be the maximum elements of theirs columns. However, we find that when evaluating on a certain setting, architecture searched from another setting can perform well, even better than the architecture searched the same setting. E.g., the best architecture evaluated on the graph with d = 5 is searched from the graph with 5 = 4. This phenomenon can answer (ii). DARTS may not be able to accurately select the optimal architecture with the original graph.
We can also give explanation here. Although DARTS can judge the usefulness of different information, they cannot get an accurate answer, c.g., when å = 6, graph structure contains useful classification information. However, DARTS may have overconfidence in it and make radical decisions, aggregating too much message from the neighborhood which includes noises and cause fvtt-fitting. Less graph structure information (8 4, 5) lets DARTS become more conservative about aggregation. Architectures searched at these settings perform better when evaluating at 5 = 6 setting. Similarly, DARTS may misjudge the information's usefulness in other settings.
Based on the above exploration, we have found that DARTS cannot design the optimal architecture due to certain noise in the original graph. Message passing scheme used in GNNs smooths node

---

features, which can also be seen as a denoising process. Therefore, denoising graph structure is what we should consider more. Combining architecture search and structure learning becomes a natural way. In the next section, we will introduce our method which jointly optimizes neural architecture and graph structure.
4 Joint optimization of graph architecture and structure
4.1 Differentiable Graph Structure
In most real graph datasets, the graph structure is discrete, i.c., the edges given in the graph unweighted. Although these edges contain crucial information, certain noise is brought into the data well. Take citation dataset for example, a paper cites other papers for many different reasons. Some citations are helpful for paper classification, such as citing related works and baselines. Others may have less use, such citing mathematical method. However, the graph treats all these different types of citation equally. The classification model may be confused by those unhelpful edges. This phenomenon can be also found in other types of graphs. In addition, the discrete space of graph structure makes it difficult to optimize the structure. Thus, it is necessary to differentiate the edges in the graph.
We apply differentiable graph structure here. We use a parameter to represent the weight of each edge. To restrict the weight is in (0, 1) during message passing, use sigmoid function to the parameter. Thus, the parameter matrix used in message passing can be represented as G, = normalize( sigmoid(G)) (G)), where G is the parameter. The normalize function includes adding self-loops, i.e we can only change the weight of normal edges, the weight of self-loops is fixed. In the message passing procedure, edge weights used multipliers before aggregation.
We benefit from the differentiable graph structure in two ways. One is we can distinguish the helpfulness of edges, and aggregate more useful information during message passing. The other one we can use gradient based methods to optimize the structure. We should note this differentiable graph structure fits most of GNNs by just replacing the adjacent matrix with the parameter matrix Gp-
4.2 Learning by Hidden Feature Smoothness Constraint
that more links between intra-group nodes and fewer links between inter-group nodes improve the node classification accuracy. However, we cannot get all node labels in the training phase. We use hidden feature to approximate the node labels, which is the matrix indicating the probability of which type the nodes belong to. It is proper to use H to represent the node label. To minimize the connections between anter-group nodes, we can use the hidden feature smoothness a regularizer. In condition that the model has learnt some knowledge, the model will give good predictions about node labels. Thus, the edge weights whose connected nodes have similar hidden features larger than those have different hidden features. By updating the structure, similar node features are aggregated more in later GNN procedure, improving the denoising ability of the algorithm. However, if we only adopt this loss to optimize the structure. All edge weight will be reduced to at convergence. Thus we combine the smoothness loss with distance loss, which can be formulated as:
An important assumption in graph is the first-order proximity. It is proved in 21 22
C. l h. + [G,,
Σ
(G., - Go.s))²
(2)
where G.y is the weight parameter of the edge between node and j. Go.sj is the elements in the initialization G. we initial all edge weights as 0.5, À is a hyper-parameter to control the contribution of the hidden feature smoothness. Hence, the weight of edges between inter-group nodes is reduced. certain degree. In addition, this loss restricts G not
This loss guarantees the first-order proximity to change too much from the original graph. To save calculation resources, we only learn the weight of edges existing in the original graph in this procedure. The weight of other edges is always kept as O. Therefore, the memory and time complexity of our methods is O(E)). Besides, since G also takes part in the calculation of L., we detach from the computational graph while calculating the gradient of L, to G in order prevent complex back Back-propagation.
7

---

4.3 Training Procedure
We formulate the joint optimization problem as follows:
minCeai .A,
A
s.l. G argminnG.. ,,GG),
W argminny argminyyB.erraaa BaerrayyCraii
In this problem, there are three parameters W, G needing optimized. is hard optimize all of them at the same time. Thus we apply gradient descent methods to these parameters in turns. In the training procedure, we set the first several epochs as warming up, when only W updated. Since at the very beginning of training, W is unstable and may lead to incorrect hidden features. Using those hidden features to update the other two parameters aggravates the model's 's unstableness.
Different from DARTS for image tasks where a small proxy model is usually used in the searching phase due the memory limitation, and a larger network is retrained in the evaluation phase. Here, the number of layers in the super network is the same as a complete GNN. We can directly use the super network to do the evaluation. Interestingly, we find that the super network performs well in node classification tasks, even better than retraining the designed architecture at most times. This phenomenon may be due the regularization caused by weight sharing, which is one type of ensemble model [39]. Other ensemble models such dropout 40 and multiple heads [41] have proved their success in deep neural networks. All these models can regarded as an ensemble of different submodels, which learn different parts of knowledge from the data and provide different perspectives of it. These submodels restrict each other during the training phase, which is facto a type of regularization, helping reduce over-fitting and improve performance.
5 Experiments
5.1
Performance Evaluation
Dataset
Cora
Citeseer
Pubmed
GCN
87.40
79.20
88.40
GAT
87.26 = 0.08
77.82
86.83 = 0.11
1.000
0.75
ARMA
86.06 + 0.05
76.50 0.00
88.70 = 0.24
0.000
DropEdget
87.60 = 0.05
78.57
87.34 = 0.24
6.255
DARTS
86.18 0.36
74.96
88.38 = 0.18
6.900
GDAS
85.48 = 0.30
74.20
89.50 = 0.14
0.75
ASAP
85.21 + 0.13
75.14 0.09
88.65 = 0.10
0.50
XNAS
86.80 + 0.14
76.33 + 0.09
88.61 + 0.25
0.75
GraphNAS
86.83 + 0.56
79.05 + 0.28
89.99 = 0.43
epoch
GASSO
87.63 + 0.29
79.61
0.32
90.52
0.24
1,000
GASSO-VI
87.19 + 0.24
78.71 1 0.16
90.30 + 0.46
6.955
GASSO-V2
87.17 0.26
78.62 + 0.22
90.13 = 0.33
0.000
GASSO-VE V3
87.35 + 0.19
78.80 + 0.33
90.26 = 0.44
GASSO-VA V4
87.31 + 0.21
79.04 + 0.34
89.12 = 0.18
0000
GASSO-VS
86.26 1 0.50
77.08 1 0.55
89.34 + 0.20
GASSO-V6!
86.78 1 0.24
79.40 1 0.35
89.78 1 0.20
GASSO-V7!
87.35 + 0.46
78.38 + 0.31
89.52 + 0.20
64t0
epoch
GASSO-V8
87.14 1 0.37
78.38 1 0.24
90.40 +::01 0.39
GASSO-V9
87.37 1. 0.24
78.22 1 0.42
90.24 + 0.30
Figure 3: Weight ratio of noisy edges to orignical edges. Top: Cora. Bottom: Citeseer.
Table 2: Node Classification Performance
To be fairly compared, we expand the channels of these model to make the number of model parameters comparable with GASSO. We GraphNAS because their code leaks test set of data.
Since structure learning is directly performed on the original graph, we focus on transductive node classification task. We evaluate our model on three widely used citation benchmark datasets, Cora, Citeseer, and Pubmed, where nodes denote papers and edges denote citation relationship. We apply

---

the full- sullesuper training fashion used in 442 44
settings are listed in Appendix
B.2. We use GCN M. GAT 2 ARMA [5], DropEdge [42) DARTS 8 GDAS 46) ASAP 47
XNAS 48 and GraphNAS S as our baselines, and the paramm-r of them are following
the original implementation. For our GASSO model, we set the number of layers as in Cora and CiteSeer, 4 in PubMed. The candidate operations contain GCN M. GAT' 22, GIN B MRConv [7 and linear. In the super network, we adopt dropout (p=0.8) before each layer and a ReLU function after each layer. We summarize node classification accuracy in Table 2 All results in the table are averaged over 10 runs with random parameter initialization, and the standard deviations are also provided in the table.
We can find that our model GASSO outperforms all baselines on all three benchmark datasets. The results show that our proposed model has the power to effectively utilize information in the original graph, giving better node label predictions.
Dataset
Physics
CoraFull
oghn-arxiv
GCN
95.94
68.08
70.39
GAT
95.86
65.78
68.53
DARTS
95.74
68.51
69.52
We conduct further experiments on three larger graph benchmarks: Physics, CoraFull and ogbn- arxiv. For Physics and CoraFull, we randomly split train/valid/test set as 50:25:25, For ogbn-arxiv, we follow the default setting. We narrow down the op- eration search space to GCN, GAT and linear because of the memory limit. The results shown in Table 3 indicating that our model still performs well in larger graphs.
GASSO
96.38
68.89
70.52
Table 3: Node Classification Performance
5.2 Ablation Study
In our scheme, the most two important parts are neural architecture search and graph structure learning. To further evaluate the contribution of these two components and their cooperation, we conduct an ablation study on them. We design several variant models, which can be divided into three parts. 1) We change the graph structure learning model in the first part of variants. For GASSO-VI, we remove the structure learning part, i.c., the model becomes pure DARTS with our initial G. For GASSO- V2, we replace hidden feature smoothness with original feature smoothness, which is used in 20 For GASSO-V3; we replace hidden feature smoothness with one-hot predicted label smoothness, which similar with (2T]. For GASSO-V4: we directly calculate edge weight based on similarities between nodes. 2) In the second part, we change the neural architecture search method. For GASSO- V5, we do not update the neural architecture, but the super network is still kept, i.e., all candidate operations have equal weights from the beginning to the end. For GASSO- V6, we fix GCN as the architecture. For GASSO-V7, we fix GAT as the architecture. 3) In the third part, we change the optimization scheme. The aim of setting this part of variants is to prove the cooperation of graph structure learning and neural architecture search. For GASSO-V8. we split the training of neural architecture and graph structure. In the first half of epochs, we only train the graph structure. In the second half, we only train the neural architecture. To be fair, the number of training epochs is doubled, and the warming up procedure is still kept. For GASSO-V9; the same as GASSO-V8, but the order of training neural architecture and graph structure is exchanged.
We examine all these variant on the same datasets, the results are also presented in Table Overall, our model outperforms all of the variants in all three datasets, showing training of both graph architecture and neural architecture contributes to our model.
For part 1), find that GASSO-VI also achieves comparable performance with GCN and GAT, showing the great power of ensemble in the super network. But the margin below GASSO proves that graph structure learning is necessary. Interestingly, the performance of GASSO-V2 not even good as GASSO-VI. It is possible that using original feature smoothness to constrain edges causes more severe over-fitting The performance of GASSO-V3 indicates that one-hot predicted label smoothness is of some usefulness. But neither the original feature nor the one-hot predicted label better than hidden feature for graph structure learning- GASSO-V4 is radical method, which makes the edge weights different at the early stage of training. For part 2), we observe that the performance has an obvious drop in GASSO-V5, demonstrating that the neural architecture training is of significant importance. GASSO-V6 V6 and CASSO-V7 behave differently in three datasets compared with GCN and GAT, showing these datasets have different properties. For part 3), we dicover that GASSO-VE V8 can be regarded as GASSO-V4 V4 followed by neural architecture search, and GASSO-V9

---

can be regarded GASSO-VI followed by graph structure learning, The margin of GASSO-VE over GASSO-V4 and margin of GASSO-VS V9 over GASSO-VI prove that adding neural architecture search behind graph structure learning can achieve better performances, while adding graph structure learning behind neural architecture search causes unstable influence. Nevertheless, neither GASSO- V8 nor GASSO-V9 outperforms GASSO, demonstrating that the cooperation training in our scheme play key role in optimizing the model.
accuracy
accuracy
accuracy
0.02
GCN
GCN
GCV
GAT
GAT
2A1
DARTS
6.11
DART5
DARTS
GASSO
GASSO
GASSO
690
631
perturbation rate (%)
perturbation rate (%)
perturbation rate (%)
(a) Cora
(b) CiteSeer
(c) PubMed
Figure 4: Accuracy with noisy edges
5.3
Denoising Analysis
Here we examine the denoising ability of our model. We select the experiment setting follow- ing [13] 16, 20), where only the largest connected component is considered, and the split train- We manually include random edges in the three datasets with different perturbation rates, from 0% to 100% with step of 20%. We compare our methods with baselines GCN, GAT and DARTS. The results shown in Figure 4 We observe that DARTS has an unstable denoising ability. It performs very well on PubMed, the accuracy almost keeps as it the original graph even when there is 100% perturbation rate of edges. However, it performs badly the other two cases, even worse than GCN. Our proposed methods consistently outperform the three baselines in all three datasets. Comparing our proposed GASSO with GCN and GAT, the performance gain gets larger when more noise is added to the graph in all cases. Moreover, GASSO leads margin of around 6% CiteSeer and 4% in Cora upon DARTS 100% perturbation rate setting. To better demonstrate the effectiveness of our denoising process, we show the weight ratio of noisy edges to original edges in Figure 3 We choose the case of 100% perturbation rate in Cora and CiteSeer. We use 20 epochs to warm up. Then the weight ratio begins to decrease. It tends to be stable at around 82.5% both cases, indicating we can exclude 17.5% of noise effect. All the above results show that GASSO has a great power to reduce noise disturbing NAS methods.
ing/validatiinn/essing set is 10%%
6 Conclusion
In this paper, we study how graph architecture search can select desired architectures by conducting measurement study and proposing a Graph Differentianle Architecture Search model with Structure Optimization (GASSO). We find that gradient based graph architecture search can select proper operations according to the usefulness of information inside the graph, and may suffer from noises in graph features and structures. Based on our findings, we proposed our GASSO model, which jointly optimizes graph architecture and structure. Extensive experiments on real graph benchmark datasets demonstrate that the joint optimization of neural architecture and graph structure not only benefits in graph learning but also enhances the denoising ability.
Acknowledgments and Disclosure of Funding
This work is supported by the National Key Research and Development Program of China No. A020AAA0006000 and National Natural Science Foundation of China (No. 620501 10, No. 62102222).
10

---

References
[1] Thomas N. Kipf' and Max Welling, Semi-supervised classification with graph convolutional networks. In Proceedings of the 5th International Conference on Learning Representations. 2017.
[2] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In Proceedings of the 6th International Conference on Learning Representations, 2018
[3] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In 7th International Conference on Learning Representations, 2019.
[4] Guohao Li, Guocheng Qian, Itzel C Delgadillo, Matthias Muller, Ali Thabet, and Bernard Ghanem. Sgas: Sequential greedy architecture search. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, 2020.
[5] Yang Gao, Hong Yang, Peng Zhang, Chuan Zhou, and Yue Hu. Graph neural architecture search. In Proceedings of the Twenty-Ninth International Joinl Conference Artificial Intelligence, 2020.
[6] Barret Zoph and Quoc V Le. Neural architecture search with reinforcement learning. In Proceedings of the 5th International Conference on Learning Representations, 2017.
[7] Hicu Pham, Melody Y Guan, Barret Zoph. Quoc V Le, and Jeff Dean. Efficient neural architecture search via parameter sharing. In Proceedings of the 35th International Conference on Machine Learning, 2018.
[8] Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. In Proceedings of the 7th International Conference on Learning Representations, 2019.
[9] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In Advances in neural information processing systems, 2017.
[10] H. Li, X. Wang. Z. Zhang, J. Ma, and W. Zhu. Intention-aware sequential recommendation with structured intent transition. IEEE Transactions on Knowledge and Data Engineering, 2021.
[11] Fangda Gu, Heng Chang, Wenwu Zhu, Somayeh Sojoudi, and Laurent El Ghaoui. Implicit graph neural networks. Advances in Neural Information Processing Systems, 2020.
[12] Ming Jin, Heng Chang, Wenwu Zhu, and Somayeh Sojoudi. Power up! robust graph con- volutional network via graph powering. In 35th AAAI Conference on Artificial Intelligence, 2021.
[13] Heng Chang, Yu Rong, Tingyang Xu, Wenbing Huang, Somayeh Sojoudi, Junzhou Huang, and Wenwu Zhu. Spectral graph attention network with fast eigen-approximation. arXiv preprint arXiv:2003.07450, 2020.
[14] Steven Kearnes, Kevin McCloskey, Mare Berndl, Vijay Pande, and Patrick Riley. Molecular graph convolutions: moving beyond fingerprints. Journal of Computer-Aided Molecular Design, 30(8).
[15] Daniel Ziggner, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks neural networks for graph data. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, 2019.
[16] Daniel Zügner and Stephan Günnemann. Adversarial attacks on graph neural networks via meta learning. In 7th International Conference on Learning Representations, 2019.
[17] Dingyuan Zhu, Ziwei Zhang, Peng Cui, and Wenwu Zhu. Robust graph convolutional networks against adversarial attacks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2019.

---

[18] Huijun Wu, Chen Wang, Yuriy Tyshetskiy. Andrew Docherty, Kai Lu, and Liming Zhu. Adver- sarial examples for graph data: Deep insights into attack and defense. In Proceedings of the Tightt-Figtth International Joint Conference on Artificial Intelligence, 2019.
[19] Negin Entezari, Saba A. Al-Sayouri, Amirali Darvishzadeh, and Evangelos E. Papalexakis. All you need is low (rank): Defending against adversarial attacks on graphs. In WSDM '20: The Thirteenth ACM International Conference on Web Search and Data Mining. 2020.
[20] Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang. Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. In KDD 20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2020.
[21] Liang Yang. Zesheng Kang, Xiaochun Cao. Di Jin, Bo Yang, and Yuanfang Guo. Topology opti- mization based graph convolutional network. Proceedings of the Twenty-Eighth International Joint Conference Artificial Intelligence, 2019.
[22] Dongsheng Luo, Wei Cheng, Wenchao Yu, Bo Zong. Jingchao Ni, Haifeng Chen, and Xiang Zhang. Learning to drop: Robust graph neural network via topological denoising. CoRR, 2020.
[23] Ke Tu, Jianxin Ma, Peng Cui, Jían Pei, and Wenwu Zhu, Autone: Hyperparameter optimization for massive network embedding. In KDD '19: The 25th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2019.
[24] Xin Wang, Shuyi Fan, Kun Kuang, and Wenwu Zhu. Explainable automated graph repre- sentation learning with hyperparameter importance. In Proceedings of the 38th International Conference on Machine Learning. 2021.
[25] Zhikun Wei, Xin Wang*, and Wenwu Zhu. Autoias: Automatic integrated architecture searcher for click-trough rate prediction. In CIKM '21: The 30th ACM International Conference on Information and Knowledge Management, 2021.
[26] Yue Liu, Xin Wang*, Xue Xu, Jianbo Yang, and Wenwu Zhu. Meta hyperparameter optimization with adversarial proxy subsets sampling. In CIKM '21: The 30th ACM International Conference on Information and Knowledge Management. 2021.
[27] Zhao Zhong, Junjie Yan, Wei Wu, Jing Shao, and Cheng- Liu. Practical block-wite wise neural network architecture generation. In Proceedings of the IEEE conference on computer vision and pattern recognition, 2018.
[28] Yuhang Jiang, Xin Wang, and Wenwu Zhu. Hardware-awand transformable architecture search with efficient search space. In IEEE International Conference on Multimedia and Expo, 2020.
[29] Lanning Wei, Huan Zhao, Quanming Yao, and Zhiqiang He. Pooling architecture search for graph classification. CoRR.
[30] Yijian Qin, Xin Wang, Peng Cui, and Wenwu Zhu. Gqnas: Graph q network for neural architecture search. In 21st IEEE International Conference on Data Mining, 2021.
[31] Lingxi Xie and Alan Yuille. Genetic enn. In Proceedings of the IEEE international conference on computer vision, 2017.
[32] Hanxiao Liu, Karen Simonyan, Oriol Vinyals, Chrisantha Fernando, and Koray Kavukeuoglu. Hierarchical representations for efficient architecture search. In Proceedings of the 6th Interna- tional Conference on Learning Representations, 2018
[33] Sirui Xie, Hehui Zheng, Chunxiao Liu, and Liang Lin. Snas: stochastic neural architecture search. In Proceedings of the 7th International Conference on Learning Representations, 2019.
[34] Kaixiong Zhou, Qingquan Song, Xiao Huang, and Xia Hu. Auto-gnn: Neural architecture search of graph neural networks. CoRR, 2019.
[35] Jiaxuan You, Zhitao Ying, and Jure Leskovee. Design space for graph neural networks, Advances in Neural Information Processing Systems, 33, 2020.
12

---

[36] Chaoyu Guan, Xin Wang. and Wenwu Zhu. Autoattend: Automated attention representation search. In Proceedings of the 38th International Conference on Machine Learning, 2021.
[37] Guohao Li, Matthias Müller, Ali K. Thabet, and Bernard Ghanem. Deepgens: Can gens go as deep cans? In 2019 IEEE/CVE International Conference on Computer Vision, 2019.
[38] Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E. Sarma, Michael M. Bronstein, and Justin M. Solomon. Dynamic graph CNN for learning on point clouds. ACM Trans. Graph., 2019.
[39] Zhijie Deng, Yimpeng Dong, Shifeng Zhang, and Jun Zhu. Understanding and exploring the network with stochastic architectures. Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, 2020.
[40] Geoffrey E. Hinton, Nitish Srivastava, Alex Krizhevsky, llya Sutskever, and Ruslan Salakhut- dinov. Improving neural networks by preventing co-adaptation feature detectors. CoRR, 2012.
[41] Stefan Lee, Senthil Purushwalkam, Michael Cogswell, David J. Crandall, and Dhruv Batra. Why M heads are better than one: Training a diverse ensemble of deep networks. CoRR, 2015.
[42] Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks node classification. In 8th International Conference on Learning Representations, 2020.
[43] Wen-bing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representation learning. In Advances Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems, 2018.
[44] Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. 6th International Conference on Learning Representations, 2018.
[45] William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems 30: Annual Conference Neural Information Processing Systems, 2017.
[46] Xuanyi Dong and Yi Yang. Searching for a robust neural architecture in four gpu hours. In Proceedings of the IEEF Conference on Computer Vision and Pattern Recognition, 2019.
[47] Asaf Noy, Niv Nayman, Tal Ridnik, Nadav Zamir, Sivan Doveh, Itamar Friedman, Raja Giryes, and Lihi Zelnik. Asap: Architecture search, anneal and prune. In International Conference on Artificial Intelligence and Statistics. PMLR, 2020.
[48] Niv Nayman, Asaf Noy, Tal Ridnik, Itamar Friedman, Rong Jin, and Lihi Zelnik. Xnas: Neural architecture search with expert advice. In Advances in Neural Information Processing Systems, 2019.
13


Reviews:
[{"review_id": "k5OckQQPFGg", "reviewer": "Reviewer_Sygr", "summary": "\nThe paper investigates the ability of gradient-based NAS method on selecting desired operators to construct GNN architectures. It shows that DARTs method can discriminate the benefits of different operators based on the graph structure but suffers from the noised in graph. Based on the findings, the authors propose to add an extra graph-structure learning term during the optimization process to denoise the graph structure and shows improved performance compared to existing baselines.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Positive points:\n1.\tThe paper is well-organized with easy-to-follow presentation.\n2.\tThe idea of refining the architectures is novel. Analyzing the theoretical property and noise effect to NAS algorithms is of great value.\n\nComments:\n1.\tTheorem 1 seems to be intuitive and straightforward, and I don’t think the second theorem answers the question “how optimal are the architectures selected by graph NAS”. It only shows the linear operator are preferable than GCN under certain conditions, which I think it’s kind of overclaim. Also, it is hard to say how close the synthetic setting is to the real graph settings and there’re no experiments on real graphs to demonstrate this.\n2.\tThe way of how W and A is updated based on the weighted edges is not clear. Please clarify. Also, it would be great to add more theoretical foundations rather than pure intuition of why the specific smoothness constraint is added.\n3.\tI’m curious whether adding the structure refining term would benefit other baselines. It would be great to add these experiments if possible.\n4.\tBayesian optimization-based methods are not described in the second graph of the introduction. Also, some NAS for GNN references are not included such as Kaixiong Zhou, Qingquan Song, Xiao Huang, and Xia Hu. Auto-gnn: Neural architecture search of graph neural networks. arXiv preprint arXiv:1909.03184, 2019.\n5.\tI’m worried about the memory/time complexity of the proposed method. It is also great to do a complexity and convergence analysis for the final algorithm.\n6.\tIt’s better to add a 2D plot to better described the joint effect of two variables in Figure 2.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The author didn’t describe the limitations and potential negative societal impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "XCe3ufZWoCr", "reviewer": "Reviewer_6Tss", "summary": "This paper proposed one graph neural architecture search method to learn graph structures in one differentiable way. It makes an investigation on how NAS select the operations in GNNs, and then evaluate the NAS method on a set of synthetic datasets with different structures. This paper proposed one feature smoothness constraints which can learn the graph architecture in one differentiable way.", "questions": "", "limitations": "", "rating": 9, "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": "#### Pros:\n1. This paper provides the theoretical analysis about how NAS method selects the operations in GNNs which is novel and interesting to understanding NAS.\n2. The experiments on these synthetic datasets are interesting and it can verify that NAS can select data-specific architectures when facing different structures and features.\nIt is conceptual novel in understanding NAS in GNN architecture search.\n\n#### Cons:\n1. There is too little introduction about the constraints in section 4 thus it would be a little confusing to me. How to initialize G? The distance loss in Eq (2) aims to minimize the connections between inter-group nodes. It seems that the node labels are encoded in G_0 and we can identify whether one edge (i, j) belongs to the inter or intra group?\n\n2. This paper learns to optimize the graph topology to obtain better performance. In exactly this, DropEdge [29] should be a natural baseline in experiments.\n\n#### Other comments:\n1. On those synthetic datasets, the relationship of operation selections and the different settings are shown. On the 3 real-world datasets, it would be better to show the \\delta and \\beta conditions, and how DARTS select operations on these 3 real-world datasets. I wonder whether the conclusion on real-world datasets is consistent with figure 2.\n2. In line 130, I think it should be “the operation with the maximum \\alpha of each edge is chosen”, not \"the node\".\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5h"}, "extra_text": {}}, {"review_id": "9STFB5qfZVt", "reviewer": "Reviewer_fXBu", "summary": "This paper combines the differentiable graph structure learning and neural architecture search together. By conducting the two iteratively, the framework can automate GNN design for tasks without given graph. It also provide an analysis that NAS could help balance GNN and MLP by the informativeness of graph against structure.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper firstly conducts an analysis about which GNN architecture (specifically, which operator) will be learned given a graph by DARTS. They mainly focus on analyzing the search result with respect to the informativeness of graph structure against node feature. The author construct many synthetic graph by stochastic block model, and see how the predicted operator by DARTS is related to the informativeness of structure. The finding is that if a graph is noisy and the structure cannot provide more information than feature, the DARTS will flavor MLP and skip connection against message passing operator. \n\nThe analysis of this part is reasonable but not so surprising. Also in real-world the underlying graph structure could be more complicated than the synthetic graph the paper uses. For example, probably only a portion of nodes has noisy edges. Also, it would be interesting to go deeper into the analysis. For example, whether the predicted operator per layer will be different, and how this result is associated with some graph properties. Also, many similar and more in-depth findings have been revealed in \"Design Space for Graph Neural Networks\". The authors could consider follow some of their experimental setup to strengthen the analysis part.\n\n\nGiven the finding, the author then tries to introduce structure learning to denoise the graph for better NAS. Though the idea is reasonable and there exists several structure learning works, this paper utilizes the most straightforward version: regard the graph as a weighted complete graph and adjust the pairwise weights as edge parameter. Such method cannot scale up to large-scale graph as the edge number goes quadratically to node size, and also it cannot be inductive to new nodes. I highly recommend the authors refer to some recent works on structure learning, including but not limiting to:\n\n[1] Graph Structure Learning for Robust Graph Neural Networks\n\n[2] Neural Relational Inference for Interacting Systems\n\n[3] Learning discrete structures for graph neural networks\n\n......\n\nFinally, the authors only conduct experiments on three small node classification datasets. It would be more convincing to add results on some large-scale graph datasets, such as the ones in OGB, as the scale of network data is very important to the quality of both structure learning and NAS.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The main limitation is that the structure learning could not scale to large-scale graph or new nodes in inductive setting.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "5UEIS79FAIL", "reviewer": "Reviewer_i3zt", "summary": "This paper analyzes how DARTS selects its desired architectures, and shows that the gradient based NAS suffers from noises hidden in the graph, resulting in searching suboptimal GNN architectures. Besides, this paper improves the gradient based NAS methods by employing graph structure learning as a denoising process in the search procedure, and thus proposes GASSO, a more effective NAS algorithm. The theoretical analysis given by this paper is important and interesting, but the technical improvement lacks experimental analysis and proof, and important comparison experiments are missing. \n", "questions": "", "limitations": "", "rating": 7, "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": "Strength\nS1. This paper conducts theoretical analysis and measurement study with experiments to analyze how does the gradient based NAS method select its desired architectures.\nS2. This paper analyzes and points out the shortcoming of the gradient based NAS methods, i.e., they suffer from noises hidden in the graph and thus result in searching suboptimal GNN architectures.\nS3. The writing of this paper is good.\n\nWeakness\nW1. Important experiments are missing. This paper uses many paragraphs to explain and analyze the defect of DARTS, a gradient based NAS method, but does not compare with the proposed gradient based NAS method with it in Table 2. In the experimental part (Table 2), authors only compare GASSO with one RL-based NAS method, i.e., GraphNAS, and three GNN methods. Suggest to add more gradient-based NAS methods, e.g., GDAS, ASAP and XNAS, and state-of-the-arts GNN methods in the comparison experiments.\nW2. Experimental datasets are not enough. Only three small datasets on GNN, i.e., Citeseer, Cora, PubMed, are used in the experiments. Suggest to add some large datasets, such as Physics and Corafull in the experiments.\nW3. The motivation of the Hidden Feature Smoothness Constraint, and the experimental proof of its significance and rationality are missing and not clear. How does Hidden Feature Smoothness Constraint solve the defect of the gradient-based NAS methods, i.e., suffering from noises hidden in the graph and thus result in searching suboptimal GNN architectures? Suggest to add experiments to explain and analyze its function.\nW4. What’s the definition of hidden feature mentioned in Section 4. Hidden Feature Smoothness Constraint is the key to solve the defect of the gradient-based NAS methods, suggest to give its definition.  \nW5. The details of the search space and the details of the searched GNN architectures are missing in the main paper.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studied the NAS problem for GNNs, provided analysis on the limitation of existing gradient based NAS for this task, and proposed to perform graph structure learning at the same time. The reviewers generally find the analysis is interesting and the paper to be well written. The authors have provided additional experiments and explanations during the rebuttal, and all the reviewers found the rebuttal to be helpful during the committee discussion. Based on this, we recommend the acceptance of the paper.
Decision: Accept (Poster)