Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: 
The 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.

main_review: Positive points:
1.	The paper is well-organized with easy-to-follow presentation.
2.	The idea of refining the architectures is novel. Analyzing the theoretical property and noise effect to NAS algorithms is of great value.

Comments:
1.	Theorem 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.
2.	The 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.
3.	I’m curious whether adding the structure refining term would benefit other baselines. It would be great to add these experiments if possible.
4.	Bayesian 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.
5.	I’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.
6.	It’s better to add a 2D plot to better described the joint effect of two variables in Figure 2.

limitations_and_societal_impact: The author didn’t describe the limitations and potential negative societal impact.
review_title: null

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: 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.
main_review: #### Pros:
1. This paper provides the theoretical analysis about how NAS method selects the operations in GNNs which is novel and interesting to understanding NAS.
2. 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.
It is conceptual novel in understanding NAS in GNN architecture search.

#### Cons:
1. 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?

2. This paper learns to optimize the graph topology to obtain better performance. In exactly this, DropEdge [29] should be a natural baseline in experiments.

#### Other comments:
1. 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.
2. In line 130, I think it should be “the operation with the maximum \alpha of each edge is chosen”, not "the node".

limitations_and_societal_impact: yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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. 

main_review: Strength
S1. This paper conducts theoretical analysis and measurement study with experiments to analyze how does the gradient based NAS method select its desired architectures.
S2. 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.
S3. The writing of this paper is good.

Weakness
W1. 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.
W2. 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.
W3. 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.
W4. 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.  
W5. The details of the search space and the details of the searched GNN architectures are missing in the main paper.

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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. 

The 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.


Given 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:

[1] Graph Structure Learning for Robust Graph Neural Networks

[2] Neural Relational Inference for Interacting Systems

[3] Learning discrete structures for graph neural networks

......

Finally, 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.
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_title: null

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)