DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networks
Authors: Pál András Papp
Karolis Martinkus
Lukas Faber
Roger Wattenhofer
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: graph neural networks
GNN
expressivity
WL
molecular graphs

Abstract: This paper studies Dropout Graph Neural Networks (DropGNNs), a new approach that aims to overcome the limitations of standard GNN frameworks. In DropGNNs, we execute multiple runs of a GNN on the input graph, with some of the nodes randomly and independently dropped in each of these runs. Then, we combine the results of these runs to obtain the final result. We prove that DropGNNs can distinguish various graph neighborhoods that cannot be separated by message passing GNNs. We derive theoretical bounds for the number of runs required to ensure a reliable distribution of dropouts, and we prove several properties regarding the expressive capabilities and limits of DropGNNs. We experimentally validate our theoretical findings on expressiveness. Furthermore, we show that DropGNNs perform competitively on established GNN benchmarks.

DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networks
Pál András Papp
Karolis Martinkus ETH Zurich martinkus@@thh..cm ch
Lukas Faber ETH Zurich 1faber@ethz.cht
Roger Wattenhofer ETH Zurich
ETH Zurich apapp0ethz.co ch
wattenhofer@ethz.. ch
Abstract
This paper studies Dropout Graph Neural Networks (DropGNNss) new approach that aims to overcome the limitations of standard GNN frameworks. In DropGNNs, we execute multiple runs of GNN on the input graph, with some of the nodes randomly and independently dropped in each of these runs. Then, we combine the results of these runs obtain the final result. We prove that DropGNNs can distinguish various graph neighborhoods that cannot be separated by message passing GNNs. We derive theoretical bounds for the number of runs required ensure reliable distribution of dropouts, and we prove several properties regarding the expressive capabilities and limits of DropGNNs. We experimentally validate our theoretical findings on expressiveness. Furthermore, show that DropGNNs perform competitively on established GNN benchmarks.
Introduction
Neural networks have been successful in handling various forms of data. Since some of the world's most interesting data is represented by graphs, Graph Neural Networks (GNNs) have achieved state-of-the-at performance in various fields such as quantum chemistry, physics, or social networks On the other hand, GNNs are also known have severe limitations and are sometimes unable to recognize even simple graph structures.
12 27 18]
In this paper, present new approach increase the expressiveness of GNNs, called Dropout Graph Neural Networks (DropGNNs). Our main idea is to execute not one but multiple different runs of the GNN. We then aggregate the results from these different runs into a final result.
In each of these runs, we remove ("drop out") each node in the graph with a small probability As such, the different runs of an episode will allow us to not only observe the actual extended neighborhood of a node for some number of layers d, but rather to observe various slightly perturbed versions of this d-hop neighborhood. We emphasize that this notion of dropouts is very different from the popular dropout regularization method; in particular, DropGNNs remove nodes during both training and testing, since their goal is to observe similar distribution of dropout patterns during training and testing.
This dropout technique increases the expressive power of our GNNs dramatically: even when two distinct d-hop neighborhoods cannot be distinguished by a standard GNN, their dropout variants (with few nodes removed) are already separable by GNNs in most cases. Thus by learning to identify the dropout patterns where the two d-hop neighborhoods differ, DropGNNs can also distinguish a wide variety of cases that are beyond the theoretical limits of standard GNNs.
Our contributions. We begin by showing several example graphs that are not distinguishable in the regular GNN setting but can be casily separated by DropGNNs. We then analyze the theoretical properties of DropGNNS detail. We first show that executing Ö(7) different runs is often already
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

sufficient to ensure that we observe a reasonable distribution of dropouts in neighborhood of size We then discuss the theoretical capabilities and limitations of DropGNNs in general, as well as the limits of the dropout approach when combined with specific aggregation methods.
We validate our theoretical findings on established problems that are impossible solve for standard GNNs. We find that DropGNNs clearly outperform the competition on these datasets. We further show that DropGNNs have a competitive performance on several established graph benchmarks, and they provide particularly impressive results in applications where the graph structure is really a crucial factor.
2 Related Work
GNNs apply deep learning to graph-structured data 130 In GNNs, every node has an embedding that is shared over multiple iterations with its neighbors. This way nodes can gather their neighbors' features. In recent years, many different models have been proposed to realize how the information
between nodes is shared (35) Some approaches take inspiration from convolution (2 & [3] others
from graph spectra 18 5. others from attention (33, and others extend previous ideas of established concepts such as skip connections (36
Principally, GNNs are limited in their expressiveness by the Weisfeiler-Lelman test (WL-test) [37 heuristic to the graph isomorphism problem. The work of (37] proposes new architecture, Graph Isomoprhism Networks (GIN), that is proven to be exactly as powerful as the WL-test. However, even GINS cannot distinguish certain different graphs, namely those that the WL-test cannot distinguish. This finding [11 motivated more expressive GNN architectures. These improvements follow two main paths.
The first approach augments the features of nodes or edges by additional information to make nodes with similar neighborhoods distinguishable. Several kinds of information have been used: inspired from distributed computing are port numbers on edges (28), unique IDs for nodes (20). or random features on nodes [29 M. Another idea is to use angles between edges [ from chemistry (where
edges correspond to electron bonds).
However, all of these approaches have some shortcomings. For ports and angles, there some simple example graphs that still cannot be distinguished with these extensions 11.. Adding IDs or random features helps during training, but the learned models do not generalize: GNNs often tend to overfit to the specific random values in the training set, and as such, they produce weaker results on unseen test graphs that received different random values. In contrast this, DropGNNs observe similar distribution of embeddings during training and testing, and hence they also generalize well to test graphs.
The second approach exploits the fact that running the WL-test on tuples, triples, or generally k- tuples keeps increasing its expressiveness. Thus a GNN operating on tuples of nodes has higher expressiveness than a standard GNN [1] However, the downside of this approach is that even building a second-order graph blows up the graph quadratically. The computational cost quickly becomes a problem that needs to be to addressed, for example with sampling [22]. Furthermore, second-order graph creation is global operation of the graph that destroys the local semantics induced by the edges. In contrast to this, DropGNN can reason about graphs beyond the WL-test with only small overhead (through run repetition), while also keeping the local graph structure intact.
Our work is also somewhat similar to the randomized smoothing approach 77. which has also been extended to GNNs recently [4]. This approach also conducts multiple runs slightly perturbed variants of the data. However, in randomized smoothing, the different embeddings are combined in smoothing operation (e.g. majority voting), which specifically aims to get rid of the atypical perturbed variants in order to increase robustness. In contrast to this, the main idea of DropGNNs is exactly find and identify these perturbed special cases which notably different from the original neighborhood, since these allow us to distinguish graphs that otherwise seem identical.
Finally, we note that removing nodes is common tool for regularization in deep neural networks, which has also seen use in GNNs 26: 9.. However, as mentioned before, this a different dropout concept where nodes are only removed during training to reduce the co-dependence of nodes.

---

Figure I: Illustration of 4 possible dropout combinations from example 2-hop neighborhood around O-dropout, two different 1-dropouts and 2-dropout.
DropGNN
3.1 About GNNs
Almost all GNN architectures [8 37 35 13 36 follow the message passing framework [12 Every node starts with embedding given by its initial features. One round of message passing has three steps. In the first MESSAGE step, nodes create a message based on their embedding and send this message to all neighbors. Second, nodes AGGREGATE all messages they receive. Third, every node UPDATES its embedding based on its old embedding and the aggregated messages. One such round corresponds to one GNN layer. Usually, GNN performs d rounds of message passing for some small constant d. Thus, the node's ' embedding in a GNN reflects its features and the information within its d-hop neighborhood. Finally, a READOUT method translates these final embeddings into predictions. Usually, MESSAGE, AGGREGATE, UPDATE and READOUT are functions with learnable parameters, for instance linear layers with activation functions.
This GNN paradigm closely related to the WL-test for a pair of graphs, which is an iterative color refinement procedure. In rounds 1,... d, each node looks at its color and the multiset of colors of its direct neighbors, and uses a hash function to select a new color based on this information. As such, if the WL-test cannot distinguish two graphs, then standard GNN cannot distinguish them either: intuitively, the nodes in these graphs receive the same messages and create the same embedding in each round, and thus they always arrive at the same final result.
3.2 Idea and motivation
The main idea of DropGNNs is to execute multiple independent runs of the GNN during both training and testing. In each run, every node of the GNN is removed with probability p. independently from all other nodes. If a node is removed during run, then does not send or receive any messages to/from its neighbors and does not affect the remaining nodes in any way. Essentially, the GNN behaves as if (and its incident edges) were not present in the graph in the specific run, and no embedding computed for in this run (see Figure for an illustration).
Over the course of multiple runs, dropouts allow us to not only observe the d-hop neighborhood around any node but also several slightly perturbed variants of this d-hop neighborhood. In the different runs, the embedding computed for u might also slightly vary, depending on which node(s) are missing from its d-hop neighborhood in specific run. This increases the expressive power of GNNs significantly: even when two different d-hop neighborhoods cannot be distinguished by standard GNNs, the neighborhood variants observed when removing some of the nodes are usually still remarkably different. In Section 3.4 we discuss multiple examples for this improved expressiveness.
Our randomized approach means that in different runs, will have different nodes dropping out of the GNN. As such, the GNN is only guaranteed to produce the same node embeddings two runs have exactly the same subset of nodes dropping out. Given the d-hop neighborhood of node we will refer to a specific subset nodes dropping out as a dropout combination, or more concretely k-dropout in case the subset has size k.
In order to analyze the d-hop neighborhood of u, the reasonable strategy is to use a relatively small dropout probability p. this ensures that in each run, only few nodes removed (or none at all), and

---

thus the GNN will operate on d-hop neighborhood that is similar to the original neighborhood of u. As result, 1-dropouts will be frequent, while for larger k. observing a k-dropout will be unlikely.
To reduce the effect of randomization on the final outcome, we have to execute multiple independent runs of our GNN; denote this number of runs by For successful application of the dropout idea, we have to select r large enough to ensure that the set of observed dropout combinations is already reasonably close the actual probability distribution of dropouts. In practice, this will not be feasible for k-dropouts with large A that occur very rarely, but we can already ensure for a reasonably small r that e.g. the frequency of each 1-dropout is relatively close to its expected value.
3.3 Run aggregation
Recall that standard GNNs first compute a final embedding for each node through d layers, and then they use a READOUT method to transform this into a prediction. In DropGNNs, we also need to introduce an extra phase between these two steps, called run aggregation.
In particular, we execute r independent runs of the d-layer GNN (with different dropouts), which altogether produces r distinct final embeddings for node u. Hence also need an extra step to merge these r distinct embeddings into a single final embedding of u, which then acts as the input for the READOUT function. This run aggregation method has transform multiset of embeddings into a single embedding; furthermore, it has to be a neighborhood aggregation), since the ordering of different runs carries no meaning.
function (similarly to
We note that simply applying a popular permutation-inwe invvarinn function for run aggregation, such as sum max, is often not expressive enough to extract sufficient information from the distribution of runs. Instead, one natural solution is to first apply a transformation on each node embedding, and only execute sum aggregation afterward. For example, simple transformation x (Wx: + b). where a denotes a basic non-linearity such as a sigmoid or step function, is already sufficient for almost all of our examples and theoretical results in the paper.
3.4 Motivational examples
We discuss several examples to demonstrate how DropGNNs are more expressive than standard GNNs. We only outline the intuitive ideas behind the behavior of the DropGNNs here; however, in Appendix A we also describe the concrete functions that can separate each pair of graphs.
Example 1. Figure 2a shows fundamental example of two different graphs that cannot be distin- guished by the 1-WL test, consisting of cycles of different length. This example is known to be hard for extended GNNs variants: the two cases cannot even be distinguished if we also use port numbers or angles between the edges
The simplest solution here is to consider a GNN with d = 2 layers; this already provides a very different distribution of dropouts the two graphs. For example, the 8-cycle has 2 distinct 1-dropouts where u retains both of its direct neighbors, but it only has I neighbor at distance 2; such a situation not possible in the 4-cycle all. Alternatively, the 4-cycle has a 1-dropout case with probability p. (1 - (1 where has 2 direct neighbors, but no distance 2 neighbors at all; this only happens for 2-dropout in the 8-cycle, i.c. with a probability of only p² (1 p)?. With appropriate weights, a GNN can learn to recognize these situations, and thus distinguish the two cases.
Figure 2b shows another example of two graphs that cannot be separated by a WL test; note that node features simply correspond to the degrees of the nodes. From algorithmic perspective, it is not hard to distinguish the two graphs from specific I-dropout cases, Let u and denote the two gray nodes in the graphs, and consider the process from u's ''s perspective. In both graphs, u can recognize if is removed in a run since u does not receive a "gray" message in the first round. However, the dropout of has different effect in the graphs later in the process: in the right-hand graph, it means that there is no gray neighbor at a 3-hop distance from u, while in the left-hand graph, u will still see gray node (itself) in a 3-hop distance.
Example 2.
Thus by identifying the 1-dropout of v, an algorithm can distinguish the two graphs: if we observe runs where u receives gray message in the first round, but it receives (aggregated) gray message

---

Figure 2: Several example graphs which show that DropGNNs are more expressive than standard GNNs in various cases. Different node colors correspond to different node features.
in the third round, then u has the left-hand neighborhood. This also means that a sufficiently powerful GNN which is equivalent to the 1-WL test can also separate the two cases.
function for neighborhood aggregation is often considered superior choice to mean, since u cannot separate e.g. the two cases shown in Figure 2c with mean aggregation [37]. However, the mean aggregation of neighbors also has some advantages over sum; most notably, the computed values do not increase with the degree of the node.
Example 3. Note that using
We show that dropouts also increase the expressive power of GNNs with mean aggregation, thus possibly making mean aggregation a better choice some applications. In particular, a DropGNN with mean aggregation is still able to separate the two cases Figure 2c
Assume that the two colors in the figure correspond to feature values of 1 and 1, and let p = 1 In the left-hand graph, there is a 1-dropout where ends mean aggregation yields value of with probability T. with single neighbor of value 1; hence 0.19 in each run. However, in the right-hand graph, the only way to obtain mean of is through 2-dropout or some 3-dropouts; one can caleulate that the total probability of these only 0.06 (see Appendix (A). we first transform all other values to 0 (e.g. with o(z 0.5), where is step function), then run aggregation with mean or sum can easily separate these cases. Note that if we apply a more complex transformation at run aggregation, then separation is even much easier, since e.g. the mean value of 0.33 can only appear in the right-hand graph.
4 Theoretical analysis
4.1 Required number of runs
We analyze DropGNNs with respect to the neighborhood of interesi around a node u, denoted by r. That is, we select specific region around u, and want ensure that the distribution of dropout combinations in this region is reasonably close to the actual probabilities. This choice of I then determines the ideal choice of p and in our DropGNN.
One natural choice is to select I as the entire d-hop neighborhood of u, since a GNN will always compute its final values based this region of the graph. Note that even for this largest possible I, the size of this neighborhood y == [T] does not necessarily scale with the entire graph. That is, often sparse, and
input graphs in practice bounded by a constant; this is indeed realistic in many biological or chemical applications, and also a frequent assumptions in previous works (28). In this case, having ((1) layers implies that 7 is also essentially a constant, regardless of the size of the graph.
e.g. assume that their node degrees upper
However, point out that I' can be freely chosen even a GNN aggregates information within a distance of = 5 layers, we can still select I' to denote, for example, only the 2-hop neighborhood of u. The resulting DropGNN will still compute final node embedding based on the entire 5-hop neighborhood of u; however, our DropGNN will now only ensure that observe reasonable distribution of dropout combinations in the 2-hop neighborhood u.
neighborhood of any specific size. That is.
In this sense, the size is essentially trade-off hyperparameter: while smaller 7 will require smaller number of runs r until the distribution of dropout combinations stabilizes, larger y allows us observe more variations of the region around

---

1-oomleeee dropouts. From a strictly theoretical perspective, choosing sufficiently large r always allows us to observe every possible dropout combination. However, since the number of combinations is exponential in y, this approach is not viable in practice (see Appendix B for more details).
To reasonably limit the number of necessary runs, we foeus the so-called 1-complete case: want to have enough runs to ensure that at least every 1-dropout is observed a few times. Indeed, if we can observe each variant of I where a single node is removed, then this might already allow a sophisticated algorithm to reconstruct a range of useful properties of p. Note that in all of our examples, a specific 1-dropout was already sufficient distinguish the two cases.
For any specific node v E r, the probability of a al--ddd 1-dropout for is p. (1-p)² in a run (including the probability that is not dropped out). We apply the p value that maximizes the probability of such a 1-dropout; simple differentiation shows that this maximum is obtained at p I+7"
This choice p also implies that the probability of observing a specific I-dropout in a run
( 11+7 2 1
1+7
1+7
Hence we execute r 2 e. (7 + 1) = 22()) runs, then the expected number of times we observe a specific 1-dropout (let us denote this by E1) is at least E, 2 +
Moreover, one can use Chernoff bound to show that after 21 log 7) runs, the frequency of each 1 1-dropout is sharply concentrated around E,. This also implies that we indeed observe each 1-dropout least once with high probability.
For a more formal statement, let us consider a constant E [0, 1] and an error probability < 1. Also, given node e E I (or subset S _ I), let X, (or X2) denote the number of times this 1-dropout ([S) -roopout) occurs during our runs.
it holds that for each v E T, we Theorem r 2 Ω (y log then with a probability of 1 8. have X. [[1 (1- E1, (1+6) E.}.
With slightly more runs, than I-dropouts. In this case, it already becomes possible to distinguish 1-dropouts from multiple- dropout cases based their frequency.
ensure that each d--ropou for k 2 2 happens less frequently
Theorem Ifr 2 2 (7² + y log yt), then with probability of 1 it holds that
for each E D, have X E [[(-8) E1, (1+6) ],
for each C T with [S] 2 2, we have X < (1 8)) Ez.
Since the number of all dropout combinations is in the magnitude of 27, proving this bound is slightly more technical. We discuss the proofs of these theorems in Appendix B
Note that in sparse graphs, where y is essentially constant, the number of runs described in Theorems and is js also essentially a constant; as such, DropGNNs only impose a relatively small (constant Tactor) overhead this case.
Finally, note that these theorems only consider the dropout distribution around a specific node u. To ensure the same properties for all nodes in the graph simultancously, we need to add further factor of n within the logarithm to the number of necessary runs in Theorems [ [nd However, while this only logarithmic dependence n, it might still be undesired in practice.
4.2 Expressive power of DropGNNs
we have seen that DropGNNs often succeed when a WL-test fails. It is natural to wonder about the capabilities and limits of the dropout approach in general; study this question for multiple neighborhood aggregation methods separately.
In Section 3.4
We consider neighborhood aggregation with sum and mean in more detail; the proofs of the cor- responding claims are discussed in Appendices C and respectively. Appendix aalso discusses briefly why aggregation does not combine well with the dropout approach in practice.

---

I-drooouss
a
Figure 3: Example of two graphs not separable by 1-dropouts (left side). In both of the graphs, for any of the 1-dropouts, observes the same tree structure for d 2, shown the right side.
Aggregation with sum. Previous work has already shown that sum neighborhood aggregation allows for an injective GNN design, which computes different embedding for any two neighborhoods whenever they are not equivalent for the WL-test [37] Intuitively speaking, this means that sum aggregation has the same expressive power as general-purpose d-hop distributed algorithm in the corresponding model, i.e. without IDs or port numbers. Hence to understand the expressiveness of DropGNNs this case, one needs analyze which embeddings can be computed by such distributed algorithm from a specific (observed) distribution of dropout combinations.
It is already non-trivial find distinct neighborhoods that cannot be distinguished in the 1- complete case. However, such an example exists, even if we also consider 2-dropouts. That is, one can construct pair of d-hop neighborhoods that are non-isomorphic, and yet they produce the exact same distribution of 1- and 2-dropout neighborhoods in a d-layer DropGNN.
Theorem There exists pair of neighborhoods that cannot be distinguished by 1- and 2-dropouts.
We illustrate a simpler example for only 1-dropouts in Figure For a construction that also covers the case of 2-dropouts, the analysis is more technical; we defer this to Appendix
We note that even these more difficult examples can be distinguished with dropout approach, based on their k-dropouts for larger l values. However, this requires an even higher number of runs: need to ensure that we can observe reliable distribution
for these many-node dropouts.
On the other hand, our dropout approach becomes even more powerful if we combine it e.g. with the extension by port numbers introduced in (28). Intuitively speaking, port numbers allow algorithm to determine all paths to the removed node in a I-dropout, which turn allows us to reconstruct the entire d-hop neighborhood of u. As such, in this case, 1-complete dropouts already allow to distinguish any two neighborhoods.
Theorem 4 In the setting of Theorem 7 DropGNN with port numbers can distinguish any two non-isomorphic d-hop neighborhoods.
Finally, we note that the expressive power of DropGNNs in the 1-complete case closely related to the graph reconstruction problem, which is major open problem in theoretical computer science since the 1940s [4] We discuss the differences between the two settings in Appendix
Aggregation with mean. We have seen in Section 3.4 that even with mean aggregation, DropGNNs can sometimes distinguish 1-hop neighborhoods (that is, multisets S and S₂ of features) which look identical to standard GNN. One also prove in general that similar separation is possible in various cases, e.g. whenever the two multisets have the same size.
Lemma Let S1 S2 be two multisets feature vectors with |S1| = [S2). Then S1 and Sa can be distinguished by a DropGNN with mean neighborhood aggregation.
However, in the general case, mean aggregation does not allow us to separate any two multisets based
on 1-dropouts. particular, in Appendix we also describe an example multisets S n where the distribution of means obtained from 0- and 1-dropouts is essentially identical in S₁ and Sa. This implies that we want distinguish these multisets and S2, then the best we can hope for more complex approach based on multiple-node dropouts.
7

---

5 Experiments
In all cases extend the base GNN model to DropGNN by running the GNN times in parallel, doing mean aggregation over the resulting r node embedding copies before the graph readout step and then applying the base GNN's graph readout. Additionally, an auxiliary readout head is added to produce predictions based on each individual run. These predictions are used for an auxiliary loss term which comprises 3 of the final loss. Unless stated otherwise, we set the number of runs m and choose the dropout probability to be p = m. in the dataset. This is based on the assumption, that in the datasets we use the GNN will usually have the receptive field which covers the whole graph. We implement random node dropout by, in each run, setting all features of randomly selected nodes to O. See Appendix E for more details about the experimental setup and dataset statistics. The code is publicly available
1. where m is the mean number of nodes in the graphs
5.1 Datasets beyond WL
GIN
+Ports
+DDs
+Random Feat.
+Dropout
Dataset
Test
Train
Test
Train
Train
Test
LIMITS
0.50 10.00
0.50 00.00
0.50 10.00
20.000:00
1.00 10.00
0.59 .0.19
0.66 10.19
0.66 10.22
1,00 10.00
1.00 :0.00
LIMITS 2
117
0.50 10.00
0.50
=0.00
0.50 20.00
0.50000.00
1.00:0::00
0.61 =0.26
0.72 =0.17
0.64 =0.19
1.00 10.000000
1.00 :0.00
4-CYCLIS DS
200
0.50 :0:00
0.50 =0.00
1.00 00.00
:0.07
1.001 10.00
0:58 =0.07
0.75 =0.05
0.77 :0.05
0.99 :0.03
1.00 :0.01
LCC
0.41 10.09
0.38
1.0 10.00.00
:0.09
1.00 10.00
50.08
0.45 10.16
0.46 20.08
1.00 10:00
0.99 :0.02
TRIANGLES
29
0.53 10.15
-0.15
1.0
-0.11
1.00
0.67
SRIP-CTECLLS
0.30
=0.00
50:00
0:14 :0.08
1.00 00.00
0.10 20.09
0.16
0.16:00.5
0.81 +0.28
0.82 =0.28
Table 1: Evaluation of techniques that increase GNN expressiveness on challenging synthetic datasets.
We highlight the best test scores in bold. Compared to other augmentation techniques DropGNN (GIN +Dropout) achieves high training accuracy but also generalizes well to the test set.
To see the capabilities of DropGNN in practice we test on existing synthetic datasets, which are known to require expressiveness beyond the WL-test. We use the datasets from Sato al. (29 that based on 3 regular graphs. Nodes have to predict whether they are part of a triangle (TRIANGLES) or have to predict their local clustering coefficient (LCC). We test the two counterexamples LIMITS 1 (Figure 2ab and LIMITS 2 from Garg et al. [1I] where we compare two smaller structures versus one larger structure. We employ the dataset by Loukas [20] classify graphs on containing a cycle of length 4 (4-CYCLES). We increase the regularity in this dataset by ensuring that each node has degree of 2. Finally we experiment on circular graphs with skip links (SKIP-CIRCH) CIICCES)) by Chen et al. (6) where the model needs to classify if a given circular graph has skip links of length (2, 3, 4, 5, 6, 9, 11, 12, 13, 16).
For comparison, we try several other GNN modifications which increase expressiveness. For control, we run vanilla GNN on these datasets. We then extend this base GNN with (i) ports (28 (randomly assigned), (ii) node IDs 200 (randomly permuted), and (iii) a random feature from the standard normal distribution 29 The architecture for all GNNs is 4-layer GIN with sum as aggregation and
& = O. For DropGNN r = 50 runs are performed. For the SKIP-CIRCLES dataset we use a 9-layer
GIN instead, as the skip links can form cycles of up to 17 hops.
We train all methods for 1, 000 epochs and then evaluate the accuracy on the training set. We then test on new graph (with new features). We report training and testing averaged across 10 initializations in Table I We can see that DropGNN outperforms the competition.
5.2 Sensitivity analysis
We investigate the impact of the number of independent runs on the overall accuracy. Generally, we expect an increasing number of runs to more reliably produce informative dropouts. We train with a sufficiently high number of runs (50) with the same setting as before. Now, we reevaluate DropGNN but limit the runs a smaller number. We measure the average accuracy over 10 seeds with 10 tests each and plot this average in Figure three datasets: LIMITS 1 (Figure 4-CYCLES (Figure/4b). and TRIANGLES (Figure 4c). In all three datasets, more runs directly translate to higher accuracy.
Next, we investigate the impact of the dropout probability p. We use the same setting as before, but instead of varying the number of runs in the reevaluation, we train and test with different probabilities
8

---

(a) LIMITS
(b) C-CLLE
(c) TRIANGLES
Figure 4: Investigating the impact of the number of runs (z- axis) versus the classification accuracy (y azis). In all three plots, having more runs allows for more stable dropout observations, increasing accuracy. The tradeoff is higher runtime since the model computes more runs.
44-
(a) LIMITS
(h) CYCCESS
(c) TRIANGLES
Figure 5: Investigating the impact of the dropout probability (x-axis) versus the classification accuracy ay-)x.s). DropGNN is robust to the choice of for decently small p. Choosing p = 7 is decent default that is shown by vertical black lines.
p exponential scale from 0.01 to 0.64. We also try 0 (no dropout) and 0.95 (almost everything is dropped). Figure 5hoos the accuracy for each dropout probability, again averaged over 10 seeds with 10 tests each. Generally, DropGNN is robust to different values of until p becomes very large.
5.3 Graph classification
Model
Complexity
MUTAG
PTC
PROTEINS
IMDB-B
IMDB-M
subtree
33
31
O(n)
90.4 +5.7
59.9 =4.3
75.0 +3.1
73.8 +3.9
50.9 +3.8
DCNN 2
O(a)
61.6
49.1 11.4
33.5 1..4
PatchySun
O(n)
89.0 +4.4
65.7
75.0
71.0
45.2
DGCNN 39
((n)
85.8
$8.6
GIN 37
O(n)
89.4
+2.8
75.1 #5.1
52.3 +2.8
DropGIN (ours)
O(rm), xs 20
90.4
66.3 8.6
76.3 16.1
75.7
51.4
1-2-3 GNN 22
(nn))
86.1
60.9
75.5
74.2
49.5
PPGN 2
(nn))
90.6
18.7
66.2
16.5
77.2
14.7
73
15.8
50.5
.3.6
Table 2: Graph classification accuracy (%). The best performing model in each complexity class is highlighted in bold. #We report the best result achieved by either the three versions of their model.
We evaluate and compare our modified GIN model (DropGIN) with the original GIN model and other GNN models of various expressiveness levels real-world graph classification datasets. We use three bioinformatics datasets (MUTAG, PTC, PROTEINS) and two social networks (IMDB-BINAR) and
(38. Following 37 node degree is used as the sole input feature for the IMDB datasets, while for the bioinformatics datasets the original categorical node features are used.
We follow the evaluation and model selection protocol described in 37 and report the 10-fold cross-validation accuracies 38 We extend the original 4-layer GIN model described in [37 and use the same hyper-parameter selection as 37 From Figure we can see that it is usually safer to use slightly larger p than slightly smaller one. Due this, we set the node dropout probability to p 2. where m is the mean number of nodes in the graphs in the dataset.

---

Our method successfully improves the results achieved by the original GIN model on the bioinfor- matics datasets (Table 2 and is, in general, competitive with the more complex and computationally
expensive expressive GNNs. Namely, the 1-2-3 GNN 22 which has expressive power close to
that of 3-WI. and (n*)) time complexity, and the Provably Powerful Graph Network (PPGN) [21] which has 3-WL. expressive power and (n²) time complexity. Compared to that, our method has only (rn) time complexity. However, we do observe, that our approach slightly underperforms the original GIN model on the IMDB-M dataset. Since the other expressive GNNs also underperform when compared to the original GIN model, it is possible that classifying graphs in this dataset rarely requires higher expressiveness. In such cases, our model can lose accuracy compared to the base GNN as many runs are required to achieve a fully stable dropout distribution.
5.4
Graph property regression
Property
Unit
MPNN 34
1-GNN
1-2-3 GNN 22
PPGN 21
DropMPNN
Drop-I-GNN
Dehye
0.358
0.493
0.473
0.0934
0,059-
0.453*
Bohr"
0.89
0.78
0.27
0.318
0,173
0.767*
<HOMO
Hartree
0.00541
0,00321
0.00337
0,00174
0.00193
0.00306*
Hartree
0.00623
0,00350
0.00351
0.0021
0.00177
0.00306*
A
Hartree
0,0066
0.0049
0.0048
0.0029
0.00282
0.0046+
(R2)
Bohr?
28.5
34.1
22.9
3.78
0.392
30,83*
ZPVE
Hartree
0.002116
0.00124
0.00019
0,000399
0.000112
0,000895*
U
Hartree
2.05
2.32
0.0427
0.022
0,0409
1.80"
Hartree
2.0
2.08
0.111
0,0504
0.0536
1.86
Hartree
2.02
2.23
0.0419
0.0294
0.0481
2,00*
G
Hartree
2.02
1.94
0,0469
0.24
0.0508
2.12
C.
cal/(mol K)
0.42
0.27
0.0944
0.0144
0,0596
0,259*
Table 3: Mean absolute errors on QM9 dataset [25] Best performing model is in bold and DropGNN
versions that improve over the corresponding base GNN are marked with a *
We investigate how our dropout technique performs using different base GNN models on a different, graph regression, task. We use the QM9 dataset (25] which consists of 134k organic molecules. The task is to predict 12 veal-valued physical quantities for each molecule. In all cases, a separate model is trained to predict each quantity. We choose two GNN models to augment: MPNN [22 and 1-GNN (22. We set the DropGNN run count and node dropout probability the same way as done for graph classification. Following previous work [22 21 the data split into 80% training, 10% validation, and 10% test sets. Both DropGNN model versions are trained for 300 epochs.
From Table 3 we can that Drop-I-GNI improves upon I-GNN in most of the cases. In some of them, it even outperforms the much more computationally expensive 1-2-3-GNN, which uses higher- order graphs and has three times more parameters 222 Meanwhile, DropMPNN always substantially improves on MPNN, often outperforming the Provably Powerful Graph Network (PPGN), which as you may recall scales as O(n²). This highlights the fact that while the DropGNN usually improves upon the base model, the final performance is highly dependent on the base model itself. For example, I-GNN does not use skip connections, which might make retaining detailed information about the node's 's extended neighborhood much harder and this information is crucial for our dropout technique.
6 Conclusion
We have introduced a theoretically motivated DropGNN framework, which allows us to easily increase the expressive power of existing message passing GNNs, both in theory and practice. DropGNNs are also competitive with more complex GNN architectures which are specially designed to have high expressive power but have high computational complexity. In contrast, our framework allows for an arbitrary trade-off between expressiveness and computational complexity by choosing the number of rounds r accordingly.
Societal Impact. In summary, we proposed a model architecture improvement for GNNs. We do not strive to solve particular problem but to enhance the GNN toolbox. Therefore, we do not see an immediate impact on society. We found in our experiments that DropGNN works best on graphs with smaller degrees, such as molecular graphs. Therefore, we imagine that using DropGNN in these scenarios is interesting to explore further.
10

---

References
[1] R. Abboud, i. I. Ceylan, M. Grohe, and T. Lukasiewicz. The surprising power of graph neural networks with random node initialization. arXiv preprint arXiv:2010.01179, 2020.
[2] J. Atwood and D. Towsley. crffusion-convllutiin neural networks. In Advances in neural information processing systems, pages 1993-2001, 2016.
[3] W. Battaglia, J. B. Hamrick, V. Bapst, A. Sanchez-Gonzalez V. Zambaldi, M. Malinowski,
A. Tacchetti, D. Raposo, A. Santoro, R. Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint
002.0660016,,.... 2018.
[4] A. Bojchevski, J. Klicpera, and S. Günnemann. Efficient robustness certificates for discrete data: Sparsity-aware randomized smoothing for graphs, images and more. In Proceedings of the 37th International Conference on Machine Learning, pages 1003-1013, PMLR, 2020.
[5] J. Bruna, W. Zaremba, A. Szlam, and Y. LeCun. Spectral networks and locally connected networks graphs. In 2nd International Conference Learning Representations, ICLR 2014, Banff. AB, Canada, April 14-16, 16, 2014, Conference Track Proceedings, 2014.
[6] Z. Chen, I.. Chen, S. Villar, and J. Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. Advances in neural information processing systems, 2019.
[7] J. Cohen, E. Rosenfeld, and Z. Kolter. Certified adversarial robustness via randomized smooth- ing. In Proceedings of the 36th International Conference on Machine Learning, pages 1310- 1320. PMLR, 2019.
[8] M. Defferrard, X. Bresson, and P. Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in neural information processing systems, 2016.
[9] W. Feng, J. Zhang, Y. Dong, Y. Han, H. Luan, Q. Xu, Q. Yang, E. Kharlamov, and J. Tang. Graph random neural networks for semi-supervised learning on graphs. Advances in Neural Information Processing Systems, 33, 2020.
[10] M. Fey and J. E. Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv: 02428, 2019.
[11] V. Garg. S. Jegelka, and T. Jaakkola. Generalization and representational limits of graph neural networks. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 3419-3430. PMLR, 13-18 Jul 2020.
[12] Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning (ICML), Sydney, Australia, Aug. 2017.
[13] W. Hamilton, Z. Ying, and J. Leskovee. Inductive representation learning on large graphs. In Advances in neural information processing systems, 2017.
[14] F. Harary. A survey of the reconstruction conjecture. In R. A. Bari and F. Harary, editors, Graphs and Combinatorics, pages 18-28, Berlin, Heidelberg, 1974. Springer Berlin Heidelberg. ISBN 378-3-540-37809-9
[15) W. Hu, B. Liu, J. Gomes, M. Zitnik, P. Liang, V. Pande, and J. Leskovec. Strategies for pre-training graph neural networks. arXiv preprint arXiv: /905. 12265, 2019.
[16] loffe and C. Szegedy, Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on muchine learning, pages 448-456. PMLR, 2015.
[17] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In ICLR (Poster), 2015.
[18) N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations ICLR, Toulon, France, Apr. 2017.
11

---

[19] J. Klicpera, J. GroB, and S. Günnemann. Directional message passing for molecular graphs. In International Conference on Learning Representations, 2020.
[20] A. Loukas. What graph neural networks cannot learn: depth vs width. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
[21] H. Maron, H. Ben- H. Serviansky, and Y. Lipman. Provably powerful graph networks. arXiv preprint 1905: 2019.
[22] C. Morris, M. Ritzert, M. Fey, W. L. Hamilton, J. E. Lenssen, G. Rattan, and M. Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 4602-4609, 2019.
[23] M. Niepert, M. Ahmed, and K. Kutzkov. Learning convolutional neural networks for graphs. In International conference on machine learning, pages 2014-2001 4023. PMLR, 2016.
[24] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, et al. Pytorch: An imperative style, high-peeformance deep learning 2019.
library. arXiv preprint
[25] R. Ramakrishnan, P. O. Dral, M. Rupp, and O. A. Von Lilienfeld. Quantum chemistry structures and properties of 134 kilo molecules. Scientific data, 1(1):1-7, 2014.
[26] Y. Rong, W. Huang, T. Xu, and J. Huang. Dropedge: Towards deep graph convolutional networks on node classification. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
[27] A. Sanchez-Gonzalez J. Godwin, T. Pfaff, R. Ying, J. Leskovec, and P. Battaglia. Learning simulate complex physics with graph networks. In International Conference on Machine Learning, pages 8459-8468. PMLR, 2020.
[28] R. Sato, M. Yamada, and H. Kashima. Approximation ratios of graph neural networks for combinatorial problems. In Neural Information Processing Systems (NeurIPS), 2019.
[29] R. Sato, M. Yamada, and H. Kashima. Random features strengthen graph neural networks. In Proceedings of the 202/ SIAM International Conference on Data Mining (SDM), pages 333-341. SIAM, 2021.
[30] Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 2008.
[31] N. Shervashidze, P. Schweitzer, F. J. Van Leeuwen, K. Mehlhorn, and K. M. Borgwardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(9), 2011.
[32] N. Srivastava, G. Hinton, A. Krizhevsky, I. Sutskever, and R. Salakhutdinov. Dropout: simple way to prevent neural networks from overlitting. The journal of machine learning research, 15 (1):1929-1958, 2014.
[33] Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio. Graph attention networks. In International Conference on Learning Representations (ICLR), Vancouver, BC, Canada, May 2018
[34] Z. Wu, B. Ramsundar, E. N. Feinberg, J. Gomes, C. Geniesse, A. S. Pappu, K. Leswing, and V. Pande. Moleculenet: a benchmark for molecular machine learning. Chemical science, 9(2): 513-530, 2018.
[35] Z. Wu, S. Pan, F. Chen, G. Long. C. Zhang, and S. Y. Philip. A comprehensive survey graph neural networks. IEEE Transactions on Newral Networks and Learning Systems, 2020.
[36] K. Xu, C. Li, Y. Tian, T. Sonobe, K.-i. Kawarabayashi, and S. Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference on Machine Learning (ICML), Stockholm, Sweden, July 2018
12

---

[37] K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
[38] Yanardag and Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD international conference knowledge discovery and data mining, pages 1365-1374, 2015.
[39] M. Zhang, Z. Cui, M. Neumann, and Y. Chen. An end-to-end deep learning architecture for graph classification. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
13


Reviews:
[{"review_id": "meUY2AaOVF8", "reviewer": "Reviewer_6SSD", "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 \nare conducted where, in each run, the nodes of the graph are dropped out with a certain small probability and passed through a \nGNN to produce a distinct embedding. The embeddings of the multiple runs are aggregated (with a sum) after a non-linear \ntransformation of the node features. DropGNNs achieve competitive results on synthetic and real-world datasets.\n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Strengths:\n\n- The idea is simple but clean and interesting; it's also well supported by the theoretical analysis.\n- Well-written and accessible paper. Nice examples help illustrate the main point.\n- Good generalization results on the synthetic datasets.\n- The limitations of DropGNNs are clearly laid out by the authors. \n- Nice studies on the number of runs and the dropout probability.\n- Additional results in regression experiments.\n\n\n### Criticism, Comments, and Questions:\n\n- One issue that is not entirely clear to me from the paper is the scaling behavior of this approach. \nGiven that in both tasks the graphs are relatively small, I think it would be important to see \na study on how this strategy performs and how many runs are needed as the size of the graphs increases, either on synthetic\nor on real-world data.\n\n- Modern graph classification benchmarking usually involves some large-scale datasets like the ones in OGB[1] (see also \nthe models in the leaderboards).\nI think it would improve the legitimacy of the results if the authors brought the graph classification comparisons more in line \nwith those standards.\n\n- Computational cost appears to be an important consideration. DropGNNs will take more time to execute due to the need for multiple runs. \nGiven 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.\n\n- Having a paragraph where the full setup from input to output is described (dimensions of inputs/outputs, aggregation functions, etc.) could help improve clarity.\n\n### Recap:\n\nThe paper is well written and accessible, with clearly established limitations and solid theoretical analysis. While the results\non 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,\nboth in terms of computational cost and accuracy.\n\nStill, I think this is an overall interesting paper, so my current grade is 6, which I am willing to adjust after the rebuttal.\n\n\n[1]  Hu, Weihua, et al. \"Open graph benchmark: Datasets for machine learning on graphs.\" arXiv preprint arXiv:2005.00687 (2020).\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "X79HiM-dZAt", "reviewer": "Reviewer_YyQ1", "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.", "questions": "", "limitations": "", "rating": 7, "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": "# Strengthes\n\n* The proposed approach is simple and easy to implement yet has preferable theoretical guarantees.\n* DropGNN can control a trade-off between complexity and accuracy via the number $r$ of runs.\n* The experiments with synthetic data clearly show the superiority of the proposed method to existing approaches.\n* Section 3.4 provides interesting examples. They helped me understand the rationale behind DropGNN.\n\n# Weaknesses\n\n* The improvements on real datasets are marginal (though they are enough for a theoretical paper.)\n* 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.\n* 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.\n\n# Comments\n\n* 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.\n\n---\n\n## After Discussions\n\nI'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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "PaXfMVMHoY6", "reviewer": "Reviewer_LU6D", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n* The proposed method is conceptually simple yet comes with theoretical advantages over traditional GNNs.\n* The method is relatively efficient compared to extensions such as 1-2-3-GNNs.\n* Experiments on synthetic datasets suggest that the method can improve upon the baselines.\n\nWeaknesses:\n* 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 ±.\n* There is no study of the runtime of the approach.\n* 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.\n\nMore details:\n* Figure 3 is not clear to me. What exactly does the tree structure on the right depict?\n* What do the shaded regions in Figures 4 and 5 indicate?\n* What are the results when not modifying the 4-CYCLES dataset?\n* 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?\n* 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).\n* line 177: typo. transforms => transform", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "ELWXQUHSN94", "reviewer": "Reviewer_71WX", "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.", "questions": "", "limitations": "", "rating": 7, "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": "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. \nA few points regarding the paper:\n1. (line 135) Does the \"simple transformation on each node\" has any contribution to the method?\n2. 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.\n3. Figure 5 mentions choosing $p=\\gamma^{-1}$, but $\\gamma$ is defined by an arbitrary graph node. Which $\\gamma$ should be used?\n4. 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.\n5. 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As mentioned above, I would like to see the scalability of the method addressed. \nI have no concerns regarding potential negative societal impact. ", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

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)