Decoupling the Depth and Scope of Graph Neural Networks

Abstract

State-of-the-art Graph Neural Networks (GNNs) have limited scalability with respect to the graph and model sizes. On large graphs, increasing the model depth often means exponential expansion of the scope (i.e., receptive field). Beyond just a few layers, two fundamental challenges emerge: 1. degraded expressivity due to oversmoothing, and 2. expensive computation due to neighborhood explosion. We propose a design principle to decouple the depth and scope of GNNs -- to generate representation of a target entity (i.e., a node or an edge), we first extract a localized subgraph as the bounded-size scope, and then apply a GNN of arbitrary depth on top of the subgraph. A properly extracted subgraph consists of a small number of critical neighbors, while excluding irrelevant ones. The GNN, no matter how deep it is, smooths the local neighborhood into informative representation rather than oversmoothing the global graph into "white noise". Theoretically, decoupling improves the GNN expressive power from the perspectives of graph signal processing (GCN), function approximation (GraphSAGE) and topological learning (GIN). Empirically, on seven graphs (with up to 110M nodes) and six backbone GNN architectures, our design achieves significant accuracy improvement with orders of magnitude reduction in computation and hardware cost.

arXiv commentAccepted to NeurIPS 2021

Cited by in corpus (9)

• Beyond Low-pass Filtering: Graph Convolutional Networks with Automatic Filtering
• DuETA: Traffic Congestion Propagation Pattern Modeling via Efficient Graph Learning for ETA Prediction at Baidu Maps
• A Network Science perspective of Graph Convolutional Networks: A survey
• Local Augmentation for Graph Neural Networks
• Unsupervised Graph Outlier Detection: Problem Revisit, New Insight, and Superior Method
• SUREL+: Moving from Walks to Sets for Scalable Subgraph-based Graph Representation Learning
• DGDNN: Decoupled Graph Diffusion Neural Network for Stock Movement Prediction
• A Scalable and Efficient Signal Integration System for Job Matching
• Hierarchical graph sampling based minibatch learning with chain preservation and variance reduction