Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes Dropout Graph Neural Networks (DropGNNs), an approach that utlizes dropout in a way that allows GNNs to be more expressive. In DropGNN, multiple runs 
are conducted where, in each run, the nodes of the graph are dropped out with a certain small probability and passed through a 
GNN to produce a distinct embedding. The embeddings of the multiple runs are aggregated (with a sum) after a non-linear 
transformation of the node features. DropGNNs achieve competitive results on synthetic and real-world datasets.


main_review: ### Strengths:

- The idea is simple but clean and interesting; it's also well supported by the theoretical analysis.
- Well-written and accessible paper. Nice examples help illustrate the main point.
- Good generalization results on the synthetic datasets.
- The limitations of DropGNNs are clearly laid out by the authors. 
- Nice studies on the number of runs and the dropout probability.
- Additional results in regression experiments.


### Criticism, Comments, and Questions:

- One issue that is not entirely clear to me from the paper is the scaling behavior of this approach. 
Given that in both tasks the graphs are relatively small, I think it would be important to see 
a study on how this strategy performs and how many runs are needed as the size of the graphs increases, either on synthetic
or on real-world data.

- Modern graph classification benchmarking usually involves some large-scale datasets like the ones in OGB[1] (see also 
the models in the leaderboards).
I think it would improve the legitimacy of the results if the authors brought the graph classification comparisons more in line 
with those standards.

- Computational cost appears to be an important consideration. DropGNNs will take more time to execute due to the need for multiple runs. 
Given that the benefits in graph classification are marginal even in the reported datasets, the tradeoff does not appear particularly enticing unless the size of the instances is small.

- Having a paragraph where the full setup from input to output is described (dimensions of inputs/outputs, aggregation functions, etc.) could help improve clarity.

### Recap:

The paper is well written and accessible, with clearly established limitations and solid theoretical analysis. While the results
on synthetic data show impressive generalization, I am not entirely convinced by the efficacy of this approach when considering the rest of the results on real world graphs and regression. Furthermore, it is also not clear how well the proposed approach will scale,
both in terms of computational cost and accuracy.

Still, I think this is an overall interesting paper, so my current grade is 6, which I am willing to adjust after the rebuttal.


[1]  Hu, Weihua, et al. "Open graph benchmark: Datasets for machine learning on graphs." arXiv preprint arXiv:2005.00687 (2020).

limitations_and_societal_impact: The authors have adequately addressed the limitations and impact of their work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes DropGNN, a novel technique for improving the expressive power of graph neural networks. DropGNN is simple. It removes nodes randomly (even in test time unlike dropout) and aggregates the results of several runs. This paper provides some examples and theoretical results that show when DropGNN improves its expressive power compared to vanilla GNN.
main_review: # Strengthes

* The proposed approach is simple and easy to implement yet has preferable theoretical guarantees.
* DropGNN can control a trade-off between complexity and accuracy via the number $r$ of runs.
* The experiments with synthetic data clearly show the superiority of the proposed method to existing approaches.
* Section 3.4 provides interesting examples. They helped me understand the rationale behind DropGNN.

# Weaknesses

* The improvements on real datasets are marginal (though they are enough for a theoretical paper.)
* While Section 3.4 shows there do exist some graphs that 1-complete dropouts distinguish, it would be better if some theoretical characterizations on what kind of graphs 1-complete dropouts distinguish could be shown.
* DropGNN resembles the existing methods such as rGIN [21] and DropEdge [18]. I would appreciate it if the authors could add more discussions on the differences between them.

# Comments

* The mean and sum aggregations are essentially the same when the sizes of sets are the same (by appropriate scaling). Theorem 5 assumes $|S_1| = |S_2|$. Therefore, the mean aggregation (without dropouts) is as powerful as the sum aggregation (without dropouts) in this case. (Indeed, with dropouts, $|\hat{S}_1| \neq |\hat{S}_2|$ can happen when different numbers of nodes are removed, and the probabilistic discussion is interesting, but) I'm not sure this discussion is a good characterization of the mean aggregation. Example 3 in Section 3.4 shows the mean aggregation works with DropGNN even when $|S_1| \neq |S_2|$. It would be nice if some positive theoretical results of the mean aggregation when $|S_1| \neq |S_2|$ could be shown.

---

## After Discussions

I've read the authors' responses and other reviews. They addressed most of my concerns. I've increased my score from 6 to 7. I vote for acceptance.
limitations_and_societal_impact: This paper provides some negative theoretical results as well (Theorem 3 and Section D.2.) I couldn't find any direct societal impacts.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors propose DropGNN, a GNN exension where multiple forward passes of the model are aggregated. In each of the passes, each node in the graph is dropped with probability $p$ independently. Aggregating a sufficiently large number of dropout combinations effectively breaks symmetries that lead to traditional GNNs to not be able to distinguish between certain neighborhoods. The authors present theoretical results that DropGNNs can distinguish neighborhoods that traditional GNNs (e.g., GIN) cannot. The authors evaluate their method on both synthetic and real-world datasets.
main_review: Strengths:
* The proposed method is conceptually simple yet comes with theoretical advantages over traditional GNNs.
* The method is relatively efficient compared to extensions such as 1-2-3-GNNs.
* Experiments on synthetic datasets suggest that the method can improve upon the baselines.

Weaknesses:
* The evaluation on real-world datasets is not completely convincing; the improvements over the baseline are typically very small compared to the confidence intervals denoted by ±.
* There is no study of the runtime of the approach.
* In general, the paper mentions and explores relatively few real-world applications for the approach. While this is not a major problem for a more theoretical paper, it is generally desirable to show real-world impact.

More details:
* Figure 3 is not clear to me. What exactly does the tree structure on the right depict?
* What do the shaded regions in Figures 4 and 5 indicate?
* What are the results when not modifying the 4-CYCLES dataset?
* The approach seems to resemble some similarity to randomized smoothing [Cohen et al. 2019], which has been extended to graphs by [Bojchevski et al. 2020]. Essentially, the expectation of a classifier under some noise distribution is approximated via Monte Carlo sampling, similar to Theorem 1. Can DropGNN be phrased as a randomized smoothing approach?
* What about dropping edges instead of nodes? Effectively we can view node dropping as a special case of dropping edges (i.e., drop all incoming and outgoing edges of a node).
* line 177: typo. transforms => transform
limitations_and_societal_impact: The authors do not mention limitations in the main text. They do have a section in the Appendix, however this is not completely fair to authors who actually used scarce main-text space to highlight their limitations.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper suggests a method to the GNN toolbox. The proposed method applies multiple, independent evaluations of a graph, each including random dropout applied to the graph nodes. The different evaluations are then aggregated to a single classification/regression result.
main_review: I find this paper's contributions to be clear. The main idea and ways of implementations are easy to understand, and the empirical results seem adequate. 
A few points regarding the paper:
1. (line 135) Does the "simple transformation on each node" has any contribution to the method?
2. I'm not confident this method can scale to large graphs. The authors refer to $\gamma$ almost as a constant. One of the upside of the method is that its runtime efficiency is low compared to other, stronger than 2-WL methods, though tackling larger graphs (not feasible for other methods) is likely to result in a very large $\gamma$.  As a result, to theoretical $r$ needed is also very large.
3. Figure 5 mentions choosing $p=\gamma^{-1}$, but $\gamma$ is defined by an arbitrary graph node. Which $\gamma$ should be used?
4. I'd like to see the some information of the number of graph nodes in each of the dataset used, both in table 1 and 2, to understand how well the method preforms on different sizes of graphs.
5. A runtime comparison of the method and a baseline from $O(n)$, $O(n^{3/4})$, or the method with itself for different $r$ will help understand the computational vs accuracy tradeoff.
limitations_and_societal_impact: As mentioned above, I would like to see the scalability of the method addressed. 
I have no concerns regarding potential negative societal impact.
review_title: null

Meta-review: The paper proposes a simple idea for improving the expressive power of standard graph neural networks at the expense of speed/memory. 

* The reviewers agreed that the paper is well-written and that the proposed idea is elegant and simple to implement. 

* The evaluation also shows that DropGNN can improve upon baselines relying upon feature augmentation.

Overall, this is a very good work that meaningfully contributes to the growing GNN literature. 
Decision: Accept (Spotlight)