Deep Graph Neural Networks with Shallow Subgraph Samplers

Abstract

While Graph Neural Networks (GNNs) are powerful models for learning representations on graphs, most state-of-the-art models do not have significant accuracy gain beyond two to three layers. Deep GNNs fundamentally need to address: 1). expressivity challenge due to oversmoothing, and 2). computation challenge due to neighborhood explosion. We propose a simple "deep GNN, shallow sampler" design principle to improve both the GNN accuracy and efficiency -- to generate representation of a target node, we use a deep GNN to pass messages only within a shallow, localized subgraph. A properly sampled subgraph may exclude irrelevant or even noisy nodes, and still preserve the critical neighbor features and graph structures. The deep GNN then smooths the informative local signals to enhance feature learning, rather than oversmoothing the global graph signals into just "white noise". We theoretically justify why the combination of deep GNNs with shallow samplers yields the best learning performance. We then propose various sampling algorithms and neural architecture extensions to achieve good empirical results. On the largest public graph dataset, ogbn-papers100M, we achieve state-of-the-art accuracy with an order of magnitude reduction in hardware cost.

arXiv commentThe complete version of this paper is accepted to NeurIPS 2021, available on arXiv under the new title "Decoupling the depth and scope of graph neural networks" (arXiv:2201.07858). This version, "Deep graph neural networks with shallow subgraph samplers", is a short version and we withdraw it to avoid confusion. Please always refer to arXiv:2201.07858

References in corpus (21)

• Adam: A Method for Stochastic Optimization
• Semi-Supervised Classification with Graph Convolutional Networks
• Inductive Representation Learning on Large Graphs
• Simplifying Graph Convolutional Networks
• Representation Learning on Graphs with Jumping Knowledge Networks
• DropEdge: Towards Deep Graph Convolutional Networks on Node Classification
• Towards Deeper Graph Neural Networks
• Open Graph Benchmark: Datasets for Machine Learning on Graphs
• Scaling Graph Neural Networks with Approximate PageRank
• How Powerful are Graph Neural Networks?
• MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing
• DeeperGCN: All You Need to Train Deeper GCNs
• PairNorm: Tackling Oversmoothing in GNNs
• Adaptive Sampling Towards Fast Graph Representation Learning
• Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification
• Benefits of depth in neural networks
• On the Bottleneck of Graph Neural Networks and its Practical Implications
• Tackling Over-Smoothing for General Graph Convolutional Networks
• Efficient Probabilistic Logic Reasoning with Graph Neural Networks
• Graphite: Iterative Generative Modeling of Graphs
• Bayesian Graph Neural Networks with Adaptive Connection Sampling

Cited by in corpus (6)

• Nested Graph Neural Networks
• Evaluating Deep Graph Neural Networks
• Sampling methods for efficient training of graph convolutional networks: A survey
• Network In Graph Neural Network
• Towards Deepening Graph Neural Networks: A GNTK-based Optimization Perspective
• Tree Decomposed Graph Neural Network