DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networks
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.
Code (1)
Tasks
Graph ClassificationGraph RegressionMolecular Property PredictionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Emulation-based Stabilization for Networked Control Systems with Stochastic Channels
This paper studies the stabilization problem of networked control systems (NCSs) with random packet dropouts caused by stochastic channels. To describe the effects of stochastic channels on the information transmission, …
SchedulingAn Empirical Study of Realized GNN Expressiveness
Research on the theoretical expressiveness of Graph Neural Networks (GNNs) has developed rapidly, and many methods have been proposed to enhance the expressiveness. However, most methods do not have a uniform expressiven…
Effects of Random Edge-Dropping on Over-Squashing in Graph Neural Networks
Message Passing Neural Networks (MPNNs) are a class of Graph Neural Networks (GNNs) that leverage the graph topology to propagate messages across increasingly larger neighborhoods. The message-passing scheme leads to two…
Gene Regulatory Network Inference in the Presence of Dropouts: a Causal View
Gene regulatory network inference (GRNI) is a challenging problem, particularly owing to the presence of zeros in single-cell RNA sequencing data: some are biological zeros representing no gene expression, while some oth…
ImputationChordless Structure: A Pathway to Simple and Expressive GNNs
Researchers have proposed various methods of incorporating more structured information into the design of Graph Neural Networks (GNNs) to enhance their expressiveness. However, these methods are either computationally ex…
Graph Neural Network