summaries: 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.   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. 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. 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.
abstractText: 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.
authors.name: Pál András Papp
authors.name: Karolis Martinkus
references.authors: R. Abboud İ.İ. Ceylan M. Grohe T. Lukasiewicz
references.title: The surprising power of graph neural networks with random node initialization
references.venue: arXiv preprint arXiv:2010.01179,
references.authors: J. Atwood D. Towsley
references.title: Diffusion-convolutional neural networks
references.venue: In Advances in neural information processing systems,
references.authors: P.W. Battaglia J.B. Hamrick V. Bapst A. Sanchez-Gonzalez V. Zambaldi M. Malinowski A. Tacchetti D. Raposo A. Santoro R. Faulkner
references.title: Relational inductive biases, deep learning, and graph networks
references.venue: arXiv preprint arXiv:1806.01261,
references.authors: A. Bojchevski J. Klicpera S. Günnemann
references.title: Efficient robustness certificates for discrete data: Sparsity-aware randomized smoothing for graphs, images and more
references.venue: In Proceedings of the 37th International Conference on Machine Learning,
references.authors: J. Bruna W. Zaremba A. Szlam Y. LeCun
references.title: Spectral networks and locally connected networks on graphs
references.venue: In 2nd International Conference on Learning Representations,
references.authors: Z. Chen L. Chen S. Villar J. Bruna
references.title: On the equivalence between graph isomorphism testing and function approximation with gnns
references.venue: Advances in neural information processing systems,
references.authors: J. Cohen E. Rosenfeld Z. Kolter
references.title: Certified adversarial robustness via randomized smoothing
references.venue: In Proceedings of the 36th International Conference on Machine Learning,
references.authors: M. Defferrard X. Bresson P. Vandergheynst
references.title: Convolutional neural networks on graphs with fast localized spectral filtering
references.venue: In Advances in neural information processing systems,
references.authors: W. Feng J. Zhang Y. Dong Y. Han H. Luan Q. Xu Q. Yang E. Kharlamov J. Tang
references.title: Graph random neural networks for semi-supervised learning on graphs
references.venue: Advances in Neural Information Processing Systems,
references.authors: M. Fey J.E. Lenssen
references.title: Fast graph representation learning with pytorch geometric
references.venue: arXiv preprint arXiv:1903.02428,
references.authors: V. Garg S. Jegelka T. Jaakkola
references.title: Generalization and representational limits of graph neural networks
references.venue: In Proceedings of the 37th International Conference on Machine Learning,
references.authors: J. Gilmer S.S. Schoenholz P.F. Riley O. Vinyals G.E. Dahl
references.title: Neural message passing for quantum chemistry
references.venue: In International Conference on Machine Learning (ICML),
references.authors: W. Hamilton Z. Ying J. Leskovec
references.title: Inductive representation learning on large graphs
references.venue: In Advances in neural information processing systems,
references.authors: F. Harary
references.title: A survey of the reconstruction conjecture
references.venue: Graphs and Combinatorics,
references.authors: W. Hu B. Liu J. Gomes M. Zitnik P. Liang V. Pande J. Leskovec
references.title: Strategies for pre-training graph neural networks
references.authors: S. Ioffe C. Szegedy
references.title: Batch normalization: Accelerating deep network training by reducing internal covariate shift
references.venue: In International conference on machine learning,
references.authors: D.P. Kingma J. Ba
references.title: Adam: A method for stochastic optimization
references.venue: In ICLR (Poster),
references.authors: T.N. Kipf M. Welling
references.title: Semi-supervised classification with graph convolutional networks
references.venue: In International Conference on Learning Representations ICLR,
references.authors: J. Klicpera J. Groß S. Günnemann
references.title: Directional message passing for molecular graphs
references.venue: In International Conference on Learning Representations,
references.authors: A. Loukas
references.title: What graph neural networks cannot learn: depth vs width
references.venue: In 8th International Conference on Learning Representations,
references.authors: H. Maron H. Ben-Hamu H. Serviansky Y. Lipman
references.title: Provably powerful graph networks
references.venue: arXiv preprint arXiv:1905.11136,
references.authors: C. Morris M. Ritzert M. Fey W.L. Hamilton J.E. Lenssen G. Rattan M. Grohe
references.title: Weisfeiler and leman go neural: Higher-order graph neural networks
references.venue: In Proceedings of the AAAI Conference on Artificial Intelligence,
references.authors: M. Niepert M. Ahmed K. Kutzkov
references.title: Learning convolutional neural networks for graphs
references.venue: In International conference on machine learning,
references.authors: A. Paszke S. Gross F. Massa A. Lerer J. Bradbury G. Chanan T. Killeen Z. Lin N. Gimelshein L. Antiga
references.title: Pytorch: An imperative style, high-performance deep learning library
references.venue: arXiv preprint arXiv:1912.01703,
references.authors: R. Ramakrishnan P.O. Dral M. Rupp O.A. Von Lilienfeld
references.title: Quantum chemistry structures and properties of 134 kilo molecules
references.venue: Scientific data,
references.authors: Y. Rong W. Huang T. Xu J. Huang
references.title: Dropedge: Towards deep graph convolutional networks on node classification
references.venue: In 8th International Conference on Learning Representations,
references.authors: A. Sanchez-Gonzalez J. Godwin T. Pfaff R. Ying J. Leskovec P. Battaglia
references.title: Learning to simulate complex physics with graph networks
references.venue: In International Conference on Machine Learning,
references.authors: R. Sato M. Yamada H. Kashima
references.title: Approximation ratios of graph neural networks for combinatorial problems
references.venue: In Neural Information Processing Systems (NeurIPS),
references.authors: R. Sato M. Yamada H. Kashima
references.title: Random features strengthen graph neural networks
references.venue: In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM),
references.authors: F. Scarselli M. Gori A.C. Tsoi M. Hagenbuchner G. Monfardini
references.title: The graph neural network model
references.venue: IEEE Transactions on Neural Networks,
references.authors: N. Shervashidze P. Schweitzer E.J. Van Leeuwen K. Mehlhorn K.M. Borgwardt
references.title: Weisfeiler-lehman graph kernels
references.venue: Journal of Machine Learning Research,
references.authors: N. Srivastava G. Hinton A. Krizhevsky I. Sutskever R. Salakhutdinov
references.title: Dropout: a simple way to prevent neural networks from overfitting
references.venue: The journal of machine learning research,
references.authors: P. Velickovic G. Cucurull A. Casanova A. Romero P. Liò Y. Bengio
references.title: Graph attention networks
references.venue: In International Conference on Learning Representations (ICLR),
references.authors: Z. Wu B. Ramsundar E.N. Feinberg J. Gomes C. Geniesse A.S. Pappu K. Leswing V. Pande
references.title: Moleculenet: a benchmark for molecular machine learning
references.venue: Chemical science,
references.authors: Z. Wu S. Pan F. Chen G. Long C. Zhang S.Y. Philip
references.title: A comprehensive survey on graph neural networks
references.venue: IEEE Transactions on Neural Networks and Learning Systems,
references.authors: K. Xu C. Li Y. Tian T. Sonobe K.-i. Kawarabayashi S. Jegelka
references.title: Representation learning on graphs with jumping knowledge networks
references.venue: In International Conference on Machine Learning (ICML),
references.authors: K. Xu W. Hu J. Leskovec S. Jegelka
references.title: How powerful are graph neural networks
references.venue: In International Conference on Learning Representations,
references.authors: P. Yanardag S. Vishwanathan
references.title: Deep graph kernels
references.venue: In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining,
references.authors: M. Zhang Z. Cui M. Neumann Y. Chen
references.title: An end-to-end deep learning architecture for graph classification
references.venue: In Proceedings of the AAAI Conference on Artificial Intelligence,
sections.heading: 1 Introduction
sections.text: 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-art performance in various fields such as quantum chemistry, physics, or social networks [12; 27; 18]. On the other hand, GNNs are also known to have severe limitations and are sometimes unable to recognize even simple graph structures.
  In this paper, we present a new approach to 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 p. 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 a 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 a 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 easily separated by DropGNNs. We then analyze the theoretical properties of DropGNNs in detail. We first show that executing Õ(γ) different runs is often already
  35th Conference on Neural Information Processing Systems (NeurIPS 2021).
  sufficient to ensure that we observe a reasonable distribution of dropouts in a 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 to 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.
sections.heading: 2 Related Work
sections.text: GNNs apply deep learning to graph-structured data [30]. 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 [23; 8; 13], 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-Lehman test (WL-test) [37], a heuristic to the graph isomorphism problem. The work of [37] proposes a 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; 1]. Another idea is to use angles between edges [19] from chemistry (where edges correspond to electron bonds).
  However, all of these approaches have some shortcomings. For ports and angles, there are 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 to this, DropGNNs observe a similar distribution of embeddings during training and testing, and hence they also generalize well to test set graphs.
  The second approach exploits the fact that running the WL-test on tuples, triples, or generally ktuples keeps increasing its expressiveness. Thus a GNN operating on tuples of nodes has higher expressiveness than a standard GNN [22; 21]. 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 a 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 a small overhead (through run repetition), while also keeping the local graph structure intact.
  Our work is also somewhat similar to the randomized smoothing approach [7], which has also been extended to GNNs recently [4]. This approach also conducts multiple runs on slightly perturbed variants of the data. However, in randomized smoothing, the different embeddings are combined in a 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 to find and identify these perturbed special cases which are notably different from the original neighborhood, since these allow us to distinguish graphs that otherwise seem identical.
  Finally, we note that removing nodes is a common tool for regularization in deep neural networks, which has also seen use in GNNs [26; 9]. However, as mentioned before, this is a different dropout concept where nodes are only removed during training to reduce the co-dependence of nodes.
sections.heading: 3 DropGNN
sections.heading: 3.1 About GNNs
sections.text: Almost all GNN architectures [33; 18; 37; 8; 35; 13; 36] follow the message passing framework [12; 3]. Every node starts with an 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, a 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 is 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 own 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 a 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.
sections.heading: 3.2 Idea and motivation
sections.text: 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 v is removed during a run, then v 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 v (and its incident edges) were not present in the graph in the specific run, and no embedding is computed for v in this run (see Figure 1 for an illustration).
  Over the course of multiple runs, dropouts allow us to not only observe the d-hop neighborhood around any node u, but also several slightly perturbed variants of this d-hop neighborhood. In the different runs, the embedding computed for umight also slightly vary, depending on which node(s) are missing from its d-hop neighborhood in a 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, we will have different nodes dropping out of the GNN. As such, the GNN is only guaranteed to produce the same node embeddings in two runs if we have exactly the same subset of nodes dropping out. Given the d-hop neighborhood of a node u, we will refer to a specific subset of nodes dropping out as a dropout combination, or more concretely as a 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 a few nodes are removed (or none at all), and
  thus the GNN will operate on a d-hop neighborhood that is similar to the original neighborhood of u. As a result, 1-dropouts will be frequent, while for a 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; we denote this number of runs by r. For a 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 to the actual probability distribution of dropouts. In practice, this will not be feasible for k-dropouts with large k 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.
sections.heading: 3.3 Run aggregation
sections.text: 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 a node u. Hence we 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 to transform a multiset of embeddings into a single embedding; furthermore, it has to be a permutation-invariant function (similarly to neighborhood aggregation), since the ordering of different runs carries no meaning.
  We note that simply applying a popular permutation-invariant function for run aggregation, such as sum or 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, a simple transformation x → σ (Wx+ b), where σ 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.
sections.heading: 3.4 Motivational examples
sections.text: 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 a fundamental example of two different graphs that cannot be distinguished 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 [11].
  The simplest solution here is to consider a GNN with d = 2 layers; this already provides a very different distribution of dropouts in 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 1 neighbor at distance 2; such a situation is not possible in the 4-cycle at all. Alternatively, the 4-cycle has a 1-dropout case with probability p · (1− p)2 where u has 2 direct neighbors, but no distance 2 neighbors at all; this only happens for a 2-dropout in the 8-cycle, i.e. with a probability of only p2 · (1 − p)2. With appropriate weights, a GNN can learn to recognize these situations, and thus distinguish the two cases.
  Example 2. 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 an algorithmic perspective, it is not hard to distinguish the two graphs from specific 1-dropout cases. Let u and v denote the two gray nodes in the graphs, and consider the process from u’s perspective. In both graphs, u can recognize if v is removed in a run since u does not receive a “gray” message in the first round. However, the dropout of v has a different effect in the two 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 a gray node (itself) in a 3-hop distance.
  Thus by identifying the 1-dropout of v, an algorithm can distinguish the two graphs: if we observe runs where u receives no gray message in the first round, but it receives an (aggregated) gray message
  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.
  Example 3. Note that using a sum function for neighborhood aggregation is often considered a 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, it the computed values do not increase with the degree of the node.
  We show that dropouts also increase the expressive power of GNNs with mean aggregation, thus possibly making mean aggregation a better choice in some applications. In particular, a DropGNN with mean aggregation is still able to separate the two cases on Figure 2c.
  Assume that the two colors in the figure correspond to feature values of 1 and −1, and let p = 14 . In the left-hand graph, there is a 1-dropout where u ends up with a single neighbor of value 1; hence mean aggregation yields a value of 1 with probability 14 · 3 4 ≈ 0.19 in each run. However, in the right-hand graph, the only way to obtain a mean of 1 is through a 2-dropout or some 3-dropouts; one can calculate that the total probability of these is only 0.06 (see Appendix A). If we first transform all other values to 0 (e.g. with σ(x− 0.5), where σ is a 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.
sections.heading: 4 Theoretical analysis
sections.heading: 4.1 Required number of runs
sections.text: We analyze DropGNNs with respect to the neighborhood of interest around a node u, denoted by Γ. That is, we select a specific region around u, and we want to ensure that the distribution of dropout combinations in this region is reasonably close to the actual probabilities. This choice of Γ then determines the ideal choice of p and r in our DropGNN.
  One natural choice is to select Γ as the entire d-hop neighborhood of u, since a GNN will always compute its final values based on this region of the graph. Note that even for this largest possible Γ, the size of this neighborhood γ := |Γ| does not necessarily scale with the entire graph. That is, input graphs in practice are often sparse, and we can e.g. assume that their node degrees are upper 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 d = O(1) layers implies that γ is also essentially a constant, regardless of the size of the graph.
  However, we point out that Γ can be freely chosen as a neighborhood of any specific size. That is, even if a GNN aggregates information within a distance of d = 5 layers, we can still select Γ to denote, for example, only the 2-hop neighborhood of u. The resulting DropGNN will still compute a final node embedding based on the entire 5-hop neighborhood of u; however, our DropGNN will now only ensure that we observe a reasonable distribution of dropout combinations in the 2-hop neighborhood of u.
  In this sense, the size γ is essentially a trade-off hyperparameter: while a smaller γ will require a smaller number of runs r until the distribution of dropout combinations stabilizes, a larger γ allows us to observe more variations of the region around u.
  1-complete dropouts. From a strictly theoretical perspective, choosing a sufficiently large r always allows us to observe every possible dropout combination. However, since the number of combinations is exponential in γ, this approach is not viable in practice (see Appendix B for more details).
  To reasonably limit the number of necessary runs, we focus on the so-called 1-complete case: we 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 Γ where a single node is removed, then this might already allow a sophisticated algorithm to reconstruct a range of useful properties of Γ. Note that in all of our examples, a specific 1-dropout was already sufficient to distinguish the two cases.
  For any specific node v ∈ Γ, the probability of a 1-dropout for v is p · (1− p)γ in a run (including the probability that u is not dropped out). We apply the p value that maximizes the probability of such a 1-dropout; a simple differentiation shows that this maximum is obtained at p∗ = 11+γ .
  This choice of p also implies that the probability of observing a specific 1-dropout in a run is
  1 1 + γ · ( γ 1 + γ )γ ≥ 1 1 + γ · 1 e .
  Hence if we execute r ≥ e · (γ + 1) = Ω(γ) runs, then the expected number of times we observe a specific 1-dropout (let us denote this by E1) is at least E1 ≥ r · 1e · 1 1+γ ≥ 1.
  Moreover, one can use a Chernoff bound to show that after Ω(γ log γ) runs, the frequency of each 1-dropout is sharply concentrated around E1. This also implies that we indeed observe each 1-dropout at least once with high probability.
  For a more formal statement, let us consider a constant δ ∈ [0, 1] and an error probability 1t < 1. Also, given a node v ∈ Γ (or subset S ⊆ Γ), let Xv (or XS) denote the number of times this 1-dropout (|S|-dropout) occurs during our runs.
  Theorem 1 If r ≥ Ω (γ log γt), then with a probability of 1 − 1t , it holds that for each v ∈ Γ, we have Xv ∈ [ (1−δ) · E1 , (1+δ) · E1 ].
  With slightly more runs, we can even ensure that each k-dropout for k ≥ 2 happens less frequently than 1-dropouts. In this case, it already becomes possible to distinguish 1-dropouts from multipledropout cases based on their frequency.
  Theorem 2 If r ≥ Ω ( γ2 + γ log γt ) , then with a probability of 1− 1t it holds that
  • for each v ∈ Γ, we have Xv ∈ [ (1−δ) · E1 , (1+δ) · E1 ],
  • for each S ⊆ Γ with |S| ≥ 2, we have XS < (1−δ) · E1.
  Since the number of all dropout combinations is in the magnitude of 2γ , proving this bound is slightly more technical. We discuss the proofs of these theorems in Appendix B.
  Note that in sparse graphs, where γ is essentially a constant, the number of runs described in Theorems 1 and 2 is also essentially a constant; as such, DropGNNs only impose a relatively small (constant factor) overhead in this case.
  Finally, note that these theorems only consider the dropout distribution around a specific node u. To ensure the same properties for all n nodes in the graph simultaneously, we need to add a further factor of n within the logarithm to the number of necessary runs in Theorems 1 and 2. However, while this is only a logarithmic dependence on n, it might still be undesired in practice.
sections.heading: 4.2 Expressive power of DropGNNs
sections.text: In Section 3.4, 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; we study this question for multiple neighborhood aggregation methods separately.
  We consider neighborhood aggregation with sum and mean in more detail; the proofs of the corresponding claims are discussed in Appendices C and D, respectively. Appendix D also discusses briefly why max aggregation does not combine well with the dropout approach in practice.
  Aggregation with sum. Previous work has already shown that sum neighborhood aggregation allows for an injective GNN design, which computes a 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 a general-purpose d-hop distributed algorithm in the corresponding model, i.e. without IDs or port numbers. Hence to understand the expressiveness of DropGNNs in this case, one needs to analyze which embeddings can be computed by such a distributed algorithm from a specific (observed) distribution of dropout combinations.
  It is already non-trivial to find two 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 a 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 3 There exists a pair of neighborhoods that cannot be distinguished by 1- and 2-dropouts.
  We illustrate a simpler example for only 1-dropouts in Figure 3. For a construction that also covers the case of 2-dropouts, the analysis is more technical; we defer this to Appendix C.
  We note that even these more difficult examples can be distinguished with our dropout approach, based on their k-dropouts for larger k values. However, this requires an even higher number of runs: we need to ensure that we can observe a reliable distribution even 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 an algorithm to determine all paths to the removed node in a 1-dropout, which in turn allows us to reconstruct the entire d-hop neighborhood of u. As such, in this case, 1-complete dropouts already allow us to distinguish any two neighborhoods.
  Theorem 4 In the setting of Theorem 1, a 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 is closely related to the graph reconstruction problem, which is a major open problem in theoretical computer science since the 1940s [14]. We discuss the differences between the two settings in Appendix C.
  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 S1 and S2 of features) which look identical to a standard GNN. One can also prove in general that a similar separation is possible in various cases, e.g. whenever the two multisets have the same size.
  Lemma 1 Let S1 6= S2 be two multisets of feature vectors with |S1| = |S2|. Then S1 and S2 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. In particular, in Appendix C, we also describe an example of multisets S1 ∩ S2 = ∅ where the distribution of means obtained from 0- and 1-dropouts is essentially identical in S1 and S2. This implies that if we want to distinguish these multisets S1 and S2, then the best we can hope for is a more complex approach based on multiple-node dropouts.
sections.heading: 5 Experiments
sections.text: In all cases we extend the base GNN model to a DropGNN by running the GNN r 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 13 of the final loss. Unless stated otherwise, we set the number of runs to m and choose the dropout probability to be p = 1m , where m is the mean number of nodes in the graphs 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 0. See Appendix E for more details about the experimental setup and dataset statistics. The code is publicly available1.
sections.heading: 5.1 Datasets beyond WL
sections.text: 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 et al. [29] that are 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 on the two counterexamples LIMITS 1 (Figure 2a) and LIMITS 2 from Garg et al. [11] where we compare two smaller structures versus one larger structure. We employ the dataset by Loukas [20] to classify graphs on containing a cycle of length 4 (4-CYCLES). We increase the regularity in this dataset by ensuring that each node has a degree of 2. Finally we experiment on circular graphs with skip links (SKIP-CIRCLES) 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 a vanilla GNN on these datasets. We then extend this base GNN with (i) ports [28] (randomly assigned), (ii) node IDs [20] (randomly permuted), and (iii) a random feature from the standard normal distribution [29]. The architecture for all GNNs is a 4-layer GIN with sum as aggregation and ε = 0. 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 a new graph (with new features). We report training and testing averaged across 10 initializations in Table 1. We can see that DropGNN outperforms the competition.
sections.heading: 5.2 Sensitivity analysis
sections.text: 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 to a smaller number. We measure the average accuracy over 10 seeds with 10 tests each and plot this average in Figure 4 on three datasets: LIMITS 1 (Figure 4a), 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
  1https://github.com/KarolisMart/DropGNN
  p on an exponential scale from 0.01 to 0.64. We also try 0 (no dropout) and 0.95 (almost everything is dropped). Figure 5 shows the accuracy for each dropout probability, again averaged over 10 seeds with 10 tests each. Generally, DropGNN is robust to different values of p until p becomes very large.
sections.heading: 5.3 Graph classification
sections.text: We evaluate and compare our modified GIN model (DropGIN) with the original GIN model and other GNN models of various expressiveness levels on real-world graph classification datasets. We use three bioinformatics datasets (MUTAG, PTC, PROTEINS) and two social networks (IMDB-BINARY and IMDB-MULTI) [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 5 we can see that it is usually safer to use a slightly larger p than a slightly smaller one. Due to this, we set the node dropout probability to p = 2m , 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 bioinformatics 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-WL and O(n4) time complexity, and the Provably Powerful Graph Network (PPGN) [21] which has 3-WL expressive power and O(n3) time complexity. Compared to that, our method has only O(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.
sections.heading: 5.4 Graph property regression
sections.text: 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 real-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 [12] 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 is split into 80% training, 10% validation, and 10% test sets. Both DropGNN model versions are trained for 300 epochs.
  From Table 3 we can see that Drop-1-GNN improves upon 1-GNN in most of the cases. In some of them, it even outperforms the much more computationally expensive 1-2-3-GNN, which uses higherorder graphs and has three times more parameters [22]. Meanwhile, DropMPNN always substantially improves on MPNN, often outperforming the Provably Powerful Graph Network (PPGN), which as you may recall scales as O(n3). 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, 1-GNN does not use skip connections, which might make retaining detailed information about the node’s extended neighborhood much harder and this information is crucial for our dropout technique.
sections.heading: 6 Conclusion
sections.text: 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-agnostic architecture improvement for GNNs. We do not strive to solve a 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.
title: DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networks