DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networks

Pál András Papp; Karolis Martinkus; Lukas Faber; Roger Wattenhofer

Source-linked AI summary

DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networks

Pál András Papp, Karolis Martinkus, Lukas Faber, Roger Wattenhofer

arXiv:2111.06283v1Nov 11, 2021cs.LG

TL;DR

Standard GNNs have expressiveness limits, including graph neighborhoods that message-passing methods cannot distinguish. The paper introduces DropGNNs, which repeatedly run GNNs with independent node dropouts and aggregate the results, and reports stronger expressiveness with competitive benchmark performance.

Problem
Standard GNNs cannot distinguish some graph structures, motivating methods that increase expressiveness beyond their theoretical limits.
Method
DropGNNs execute multiple independent GNN runs with node dropouts, aggregate the resulting embeddings, and analyze the required run count and aggregation limits.
Results
DropGNNs clearly outperform competing methods on problems impossible for standard GNNs and achieve competitive performance on established graph benchmarks.
Takeaways & Limitations
DropGNNs provide a model-agnostic way to trade expressiveness against computational complexity by choosing the number of runs.
Takeaways & Limitations
DropGNNs work best on graphs with smaller degrees, such as molecular graphs, according to the experiments.

Abstract

from arXiv · show

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.

1 Introduction

DropGNNs address expressiveness limits of standard GNNs by running a GNN repeatedly on randomly perturbed graphs and aggregating the results. The paper develops theoretical guarantees and reports strong performance on expressiveness tests and competitive benchmark results.

Standard GNNs achieve strong results on graph data but can fail to recognize even simple graph structures.
DropGNNs execute multiple GNN runs and aggregate their results into a final prediction.
Each run independently drops nodes with probability p, including during training and testing to align dropout distributions.
Dropout variants often separate d-hop neighborhoods that standard GNNs cannot distinguish, extending recognition beyond standard theoretical limits.
The paper analyzes the run count needed for a reasonable dropout distribution and studies DropGNN capabilities and limits across aggregation methods.
DropGNNs outperform competing methods on problems impossible for standard GNNs and remain competitive on established graph benchmarks.

2 Related Work

Related work places DropGNNs among approaches that increase GNN expressiveness beyond the WL-test. Unlike feature augmentation, tuple-based methods, randomized smoothing, or regularization dropout, DropGNNs use perturbed runs while preserving local graph structure.

Message-passing GNNs are bounded by the WL-test, and even GINs cannot distinguish graphs that WL cannot separate.
Feature augmentation uses ports, IDs, random features, or geometric information, but some variants remain insufficient or generalize poorly to unseen random values.
Tuple-based GNNs increase expressiveness but can incur quadratic graph construction costs and destroy local edge-induced semantics.
Randomized smoothing also runs models on perturbed data, but combines embeddings to remove atypical variants for robustness rather than exploiting dropout patterns.
DropGNN node removal differs from regularization dropout because nodes are removed during both training and testing, not only during training.

3 DropGNN

DropGNNs create informative neighborhood variants by independently removing nodes across repeated GNN runs, then aggregate the resulting embeddings. Motivational examples show that these variants can separate WL-indistinguishable graphs, including cases using mean aggregation.

3.1 Message passing: Message passing repeatedly sends, aggregates, and updates node embeddings, while WL refines colors from each node and its neighbors.
3.2 Idea and motivation: In each DropGNN run, every node is independently removed with probability p and contributes no messages or embedding if removed.
3.2 Idea and motivation: Repeated dropouts expose both the original d-hop neighborhood and perturbed variants whose embeddings can distinguish neighborhoods standard GNNs cannot.
3.2 Idea and motivation: Small p keeps neighborhoods close to the original, making 1-dropouts frequent and larger k-dropouts unlikely.
3.2 Idea and motivation: The number of runs r must be large enough for observed dropout combinations to approximate their distribution, especially for relatively common 1-dropouts.
3.3 Run aggregation: Run aggregation merges r embeddings into one permutation-invariant embedding before READOUT, and transformed embeddings can be summed to retain distributional information.
3.4 Motivational examples: In motivational examples, dropout patterns distinguish WL-indistinguishable cycles and feature-structured graphs, while DropGNNs also separate cases with mean aggregation.
3.3 Run aggregation: A transformed run aggregation can distinguish a case occurring with probability about 0.19 from one whose corresponding events have total probability 0.06.

4 Theoretical analysis

The theoretical analysis characterizes how many dropout runs are needed to sample neighborhood variations reliably and identifies both the expressive gains and limits of DropGNNs. It also shows that aggregation choices and added port numbers materially affect distinguishability.

Required number of runs: Choosing Γ as a neighborhood of size γ controls the dropout-distribution guarantee and creates a trade-off between fewer runs and more observed variations.Γ may be smaller than the full d-hop neighborhood, while the final embedding still depends on the entire neighborhood.
Required number of runs: p*=1/(1+γ) maximizes the probability of observing any specific 1-dropout, which is at least 1/(e(1+γ)).For a specific node v, the 1-dropout probability is p·(1−p)^γ.
Required number of runs: Ω(γ log γ) runs sharply concentrate every 1-dropout frequency around its expectation and ensure that each 1-dropout appears at least once with high probability.Theorem 1 bounds each X_v within [(1−δ)·E1,(1+δ)·E1] with probability 1−1/t when r meets its stated bound.
Required number of runs: In sparse graphs, the required run count is essentially constant, but guaranteeing the same distribution for all n nodes adds a factor of n inside the logarithm.The all-node guarantee has only logarithmic dependence on n, though the paper notes that this may still be undesirable in practice.
Expressive power of DropGNNs: With port numbers, 1-complete DropGNNs can distinguish any two non-isomorphic d-hop neighborhoods, whereas max aggregation does not combine well with dropout in practice.Port numbers allow paths to removed nodes to be determined, enabling reconstruction of the entire d-hop neighborhood.
Expressive power of DropGNNs: DropGNNs can distinguish equal-size feature multisets under mean aggregation, yet some non-isomorphic neighborhoods remain indistinguishable by 1- and 2-dropouts.Larger k-dropouts can distinguish such examples, but require more runs to obtain a reliable distribution.

5 Experiments

The experiments evaluate DropGNN on synthetic expressiveness tasks, graph classification, graph regression, and sensitivity to runs and dropout probability. DropGNN generally improves or competes with expressive GNNs, while accuracy depends on the number of runs, dropout probability, and base architecture.

Experimental setup: DropGNN uses parallel GNN runs with mean aggregation before graph readout and an auxiliary per-run prediction loss.Unless stated otherwise, the implementation uses m runs and dropout probability p = 1/m, with randomly selected node features set to 0.
Datasets beyond WL: On challenging synthetic datasets beyond WL expressiveness, DropGNN outperforms the compared GNN modifications on averaged training and test accuracy.The evaluation uses a 4-layer GIN with sum aggregation, 50 DropGNN runs, and averages results across 10 initializations.
Sensitivity analysis: More runs directly translate to higher accuracy on LIMITS 1, 4-CYCLES, and TRIANGLES, because they more reliably produce informative dropout patterns.The sensitivity analysis averages accuracy over 10 seeds with 10 tests each.
Sensitivity analysis: DropGNN remains robust across dropout probabilities until p becomes very large, with p ≈ γ^-1 presented as a reasonable default.Figure 5 varies p from 0.01 to 0.64 and also tests p = 0 and p = 0.95.
Graph classification: On graph classification benchmarks, DropGNN improves over GIN on bioinformatics datasets and is generally competitive with more complex expressive GNNs.The method slightly underperforms GIN on IMDB-M, where higher expressiveness may rarely be needed and stable dropout distributions require many runs.
Graph property regression: On QM9 regression, Drop-1-GNN improves upon 1-GNN in most cases, while DropMPNN always substantially improves on MPNN and often outperforms PPGN.The results also show that final performance depends strongly on the base GNN, including whether it retains detailed extended-neighborhood information.

6 Conclusion

The paper introduces DropGNN as a theoretically motivated way to increase the expressive power of message passing GNNs in theory and practice. It can trade expressiveness against computational complexity by adjusting the number of rounds, with strongest observed performance on graphs with smaller degrees such as molecular graphs.

Conclusion: DropGNN increases the expressive power of existing message passing GNNs while remaining competitive with more complex high-expressiveness architectures.The framework is presented as applicable in both theory and practice.
Conclusion: Choosing the number of rounds r provides an arbitrary trade-off between expressiveness and computational complexity.More rounds can be selected when greater expressive power is desired, within the framework’s stated trade-off.
Conclusion: The experiments found that DropGNN works best on graphs with smaller degrees, such as molecular graphs.The paper identifies these scenarios as especially interesting for further exploration.

A Concrete GNN representations for the examples

The paper gives concrete GNN constructions that separate example graphs by exploiting dropout-dependent neighborhood patterns and aggregating run outputs. These constructions use simple update rules, nonlinearities, and sum or mean aggregation to expose differences hidden from standard runs.

Example 1: With two layers, 1-dropouts produce values 5, 5, 7 in the left graph but 5, 5, 8, 8 in the right graph.A transformation that activates only at 8 therefore separates the distributions with sum aggregation.
Example 1: Using σ(x −8), sum aggregation counts runs whose final embedding is 9, and the expected counts differ by at least Ω(p · r).The difference arises because the two graphs have different 0-dropout probabilities.
Update rule: A simple binary update keeps a node’s embedding at 1 only when its own value and exactly two neighbors have value 1.Otherwise, the embedding becomes 0 permanently.
Example 2: The cycle remains at embedding 1, whereas a non-cycle component reaches 0 within at most d = 3 rounds after dropout.This makes dropout behavior distinguish the two graphs.
Example 2: The left graph has more dropout configurations yielding embedding 1, so after r runs its expected frequency exceeds the right graph by at least Ω(p · r).Run aggregation with sum or mean separates the cases.
Example 3: For a mean-aggregation example, the left and right graphs produce final embeddings converging to 0.19 and 0.06, respectively.The separation works with either mean or sum run aggregation.

B Required number of runs

The run count must be large enough for dropout configurations to appear with controlled frequencies across neighborhoods. The required count grows with neighborhood size, accuracy parameters, and union bounds over dropout types and nodes, while rare multi-dropouts can create substantial practical overhead.

Theorem 1: For 1-dropouts in a neighborhood of size γ, the analysis gives a sufficient run count of Ω(γ · log(γt)).This follows from concentration and a union bound over the γ possible 1-dropouts.
Theorem 2: For all k-dropouts, the sufficient run count is Ω((γ + 1) · γ · log(2 · γ · t)).The proof combines concentration bounds with union bounds over dropout subsets and k values.
All nodes: Ensuring the property simultaneously for all n graph nodes adds a factor of n inside the logarithm of the final run-count bound.This is another union bound over nodes.
Practical limitation: A specific k-dropout can require r ≥ γ^k runs just to appear once in expectation when p ≈ γ^-1.Although asymptotically constant for fixed γ, this creates large practical overhead even for modest k and γ.
Choosing p: The global dropout probability p is well matched by the analysis only when neighborhood sizes γ are relatively homogeneous across nodes.Using an average or maximum γ can remain practical, and the approach is reported as robust to moderate changes in p and the run count.

C.1 Proof of Theorem 3

Theorem 3 constructs non-isomorphic 2-hop neighborhoods whose dropout observations remain identically distributed through 2-dropouts. Thus bounded dropout order does not always separate neighborhoods.

Construction: The proof constructs two non-isomorphic d = 2 neighborhoods that produce the same observation distribution for all k-dropouts with k ≤ 2.This directly establishes a limitation of using only low-order dropout cases.
0- and 1-dropouts: For ℓ = 5, the two graphs have identical 0-dropout and 1-dropout observations around u.There are 10 possible 1-dropouts in each graph, and the resulting 2-hop neighborhoods match.
Construction: The example generalizes two cycles of length ℓ versus one cycle of length 2ℓ, with an extra node u connected to all cycle nodes.The construction is chosen to match dropout observations around u.
2-dropouts: The three possible 2-dropout distance patterns occur with matching counts in the two graphs.The cases are neighboring nodes, distance-two nodes, and nodes separated by at least three positions or lying in different cycles.
Conclusion: Consequently, the distributions of observed neighborhoods are identical for 2-dropouts as well.This completes the indistinguishability argument for the constructed pair.

C.2 Proof of Theorem 4

Theorem 4 shows that sufficiently complete 1-dropout observations can reconstruct a port-numbered d-hop neighborhood. The result also exposes a caveat: different port assignments on isomorphic neighborhoods may yield different embeddings unless run aggregation is made more sophisticated.

1-complete setting: With sufficiently many runs to observe every 1-dropout, the set of observed neighborhoods can separate any two neighborhoods regardless of multi-dropout frequencies.The proof reconstructs the neighborhood inductively from dropout variants.
Reconstruction: The reconstruction identifies when edges from different boundary nodes lead to the same outer node by checking single-node disappearance patterns.This resolves node correspondences in successive neighborhood layers.
Induction: The proof first recovers the 1-hop neighborhood from the 0-dropout, then extends the reconstruction layer by layer to distance d.It also reconstructs adjacencies among boundary nodes at each step.
Limitation: Port-numbered GNNs can assign different embeddings to isomorphic neighborhoods that differ only in port numbering.This is the opposite of the intended separation between genuinely different neighborhoods.
Limitation: More sophisticated run aggregation can recognize the same neighborhood regardless of port numbering, although the required graph-isomorphism computation is challenging in practice.The paper notes that a sufficiently complex MLP can implement the mapping in theory.

D.1 Proof of Lemma 1

The proof shows how DropGNNs distinguish multisets using thresholded dropout means and sum aggregation, covering unequal means and equal-mean cases with controlled dropout probabilities. It also extends the argument to multidimensional features and establishes concentration-based run requirements.

Generalization: The argument applies to multidimensional node features by applying the one-dimensional proof independently to each feature dimension.Since the multisets differ, at least one dimension provides a separating coordinate.
When the means are different: A threshold τ between the means makes 0-dropouts produce different binary outputs, which sum aggregation can separate with high probability.The construction uses a Heaviside threshold, with logistic activation also sufficient as an approximation.
When the means are different: r ≥ Ω(log t) runs suffice to obtain separated sums below 0.48 · r and above 0.52 · r with high probability.Chernoff concentration ensures enough 0-dropouts in both multisets.
When the means are the same: When multisets have equal size but differ in an ordered element, a threshold between corresponding reduced means separates their 1-dropout frequencies.The proof chooses p = 1/(2γ^2) so multiple-dropout cases are sufficiently uncommon.
When the means are the same: With p = 1/(2γ^2), 1-dropouts occur with probability at least 7/(16γ^2), exceeding the cumulative probability of multiple-dropout cases.This imbalance preserves a probability gap even under unfavorable multiple-dropout outcomes.

D.2 Construction for similar mean distribution

The construction gives equal-mean multisets whose 0- and 1-dropout mean distributions are effectively indistinguishable, exposing a limitation of shallow mean-based dropout analysis. It also shows that max aggregation may require extremely rare dropout patterns.

Similar mean distributions: S1 and S2 can have equal means but different sizes, while their 0- and 1-dropout mean distributions remain essentially identical.For ℓ = 4, the example is S1 = {−3, −3, 3, 3} and S2 = {−4, −4, 0, 4, 4}.
Similar mean distributions: For these multisets, separating the cases requires analyzing multiple-node dropouts because 2-dropouts can bridge the small frequency difference between 1-dropouts.The paper states that a purely 1-dropout-based approach is not viable without deeper distributional analysis.
Max aggregation: Max aggregation may distinguish multisets differing only in their smallest element only through a specific (γ − 1)-dropout.That event has probability p^(γ−1) · (1 − p)^2, requiring many runs when p is reasonably small.

E Details of the experimental setup

The experiments use established GIN-based configurations across synthetic, graph-classification, and graph-regression benchmarks, with DropGNN variants layered onto these models. Implementations trade lower sequential memory for higher parallel memory consumption.

Implementation: Executing runs sequentially can use O(n) memory, whereas parallel execution reduces compute time but increases memory consumption.The implementation performs all r runs in parallel.
Synthetic benchmarks: Synthetic benchmarks use a four-convolution-layer GIN with sum aggregation, ε = 0, and generally 16 hidden units.The setup covers LIMITS 1, LIMITS 2, 4-CYCLES, LCC, TRIANGLES, and SKIP-CIRCLES, with dataset-specific exceptions.
Dataset construction: The synthetic datasets are regenerated across random seeds, with some fixed structures differing only by permuted node IDs and others using changing random graph structures.All nodes in these datasets have the same degree.
Graph classification: Graph classification experiments apply the dropout technique to the original four-convolution-layer GIN, while DropGIN uses mean aggregation across runs.In this setting, sum and mean run aggregation differ only by a constant multiplicative factor.
Graph regression: QM9 regression augments 1-GNN and MPNN models, trains for 300 epochs, and selects the epoch with the best validation score.The implementation follows the original 1-GNN training and evaluation procedure where applicable.