Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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.

Recommendation: 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.

Main pros:
1. The general concept of adapting ideas from DARTS to work with Graph Neural Networks is fairly natural.
2. The set of tasks that are considered is broad, and the comparison is performed across a range of baselines.
3. 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.

Main cons:
1. The transfer learning method is only described very briefly, which leaves several open questions
- 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.
- What is the empirical impact of the reduced graph size on running time?
- 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.
- 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).
2. 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.
3. 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.

Other comments:
- 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.
- [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?
- 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.
- 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).
- [2] report several simple (hand-designed) GNN variants that get 0.992 on PPI.
- 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?
- 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?
- Appendix 4.2 says "we use the global sum pooling method at the end of retraining" - what does that mean?
- 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):
  - Page 2: "In the literature, we (...)"
  - Page 4: "Note that in our work (...)"
  - Page 6: "Jiang & Balaprakash (2020) is (...)"
  - Page 7: "First,, we (...)", "Second, we (...)"
  - Caption of Table 5
  - Page 16: "For other methods, (...)"

Small remarks, typos, and grammar issues (did not influence my rating recommendation):
- The EGAN abbreviation may be a bit misleading, since one could assume it refers to Generative Adversarial Networks
- Abstract: "SOAT"
- Page 1: "one shot methods NAS methods"
- Page 1: "in orders more efficient" -> "orders of magnitude more efficient"
- Pages 1 & 8: missing space after citation
- Pages 2 & 3: "for the best of our knowledge" -> "to the best of our knowledge"
- Page 3: "computational" -> "computationally"
- Equation 1: l should be in parenthesis
- Page 3: "have been demonstrated effectiveness" -> "have been demonstrated effective"
- Page 4: "kth" -> "k-th"
- Page 5: "To robust the final results" -> "To make the final results more robust"
- Page 8: "BY"
- Page 13: "feature vector obtains" -> "feature vector obtained"
- Page 16: "as evaluate metric" -> "as the evaluation metric"
- Throughout the paper: "In this part" -> "In this section"

References:
- [1] Categorical Reparameterization with Gumbel-Softmax
- [2] GNN-FiLM: Graph Neural Networks with Feature-wise Linear Modulation
- [3] How Powerful are Graph Neural Networks?
- [4] A Fair Comparison of Graph Neural Networks for Graph Classification

----------------------------------------------------------------------------------------------------

Comments after rebuttal:

I 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).
review_title: Official Blind Review #4

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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.

Pros:

+ Paper is well-written and easy to follow;
+ The proposed search space with node aggregators, layer aggregators is interesting;
+ The design of the baseline methods including random and bayesian search is appreciated;
+ Empirical results on different datasets and tasks are very strong.

Cons:

- Limited novelty, the proposed search method is very similar to SNAS (Xie et al., 2018) except the search space;
- 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;
- It is not clear why stochastic natural gradient method is needed;
- 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;
- 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.

Other Comments:

* The obtained architecture in Figure 2 b) includes SAGE. But it is not clear which aggregator is using;
* 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.

References:
* Xie, S., Zheng, H., Liu, C. and Lin, L., 2018, September. SNAS: stochastic neural architecture search. In International Conference on Learning Representations.
* 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).

Post rebuttal Comments:
Thank the authors for the detailed response. I keep my rating as 5.
review_title: Concerns about the novelty and the experimental design

final_score: rating: 3: Clear rejection
review_content: 
This 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.

The paper organization is clear, but some expressions should be improved. The details are listed as below.
Typos: In the Abstract, state-of-the-art should be abbreviated as SOTA, not SOAT.
Typos: $L_\theta(Z)$ after Equation (4) is not defined. Should it be $L_W (Z)$ as used in Equation (4)?
Clarity: 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).”
Clarity: 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?

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

Major questions:
(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.
(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. 
(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.
(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? 
(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. 
(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. 
(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.

[1] Rong, Yu, et al. "Dropedge: Towards deep graph convolutional networks on node classification." International Conference on Learning Representations. 2019.
[2] Xu, Keyulu, et al. "Representation learning on graphs with jumping knowledge networks." arXiv preprint arXiv:1806.03536 (2018).
[3] Gao, Hongyang, and Shuiwang Ji. "Graph u-nets." arXiv preprint arXiv:1905.05178 (2019)

review_title: We carefully review the motivation, approach, and empirical results.

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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).
In 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.
To 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.
The 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.

The paper is easily comprehensible, although it contains some typos and grammatical flaws.
The 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.
In some sense, this is related to PNA [1], and it would be great to discuss this relationship in the paper.
The 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.

The training architecture and the model parameters are learned simultaneously (based on a Gumbel softmax formulation) via gradient descent.
As 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.
Is my understanding correct? And if so, how can the proposed method scale to larger search spaces?
Furthermore, 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.
Furthermore, this manual hyperparameter tuning might make the efficiency comparison to related NAS approaches somewhat unfair.

Additional comments:

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

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

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

* 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?

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

=================== Post Rebuttal Comments ===================

I would like to thank the authors for their insightful rebuttal and clarifications.

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

Furthermore, 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.

Therefore, my rating will stay the same.
review_title: Efficient GNN-NAS approach, but might need more work

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