Towards Deepening Graph Neural Networks: A GNTK-based Optimization Perspective
arXiv:2103.03113
Abstract
Graph convolutional networks (GCNs) and their variants have achieved great success in dealing with graph-structured data. Nevertheless, it is well known that deep GCNs suffer from the over-smoothing problem, where node representations tend to be indistinguishable as more layers are stacked up. The theoretical research to date on deep GCNs has focused primarily on expressive power rather than trainability, an optimization perspective. Compared to expressivity, trainability attempts to address a more fundamental question: Given a sufficiently expressive space of models, can we successfully find a good solution via gradient descent-based optimizers? This work fills this gap by exploiting the Graph Neural Tangent Kernel (GNTK), which governs the optimization trajectory under gradient descent for wide GCNs. We formulate the asymptotic behaviors of GNTK in the large depth, which enables us to reveal the dropping trainability of wide and deep GCNs at an exponential rate in the optimization process. Additionally, we extend our theoretical framework to analyze residual connection-based techniques, which are found to be merely able to mitigate the exponential decay of trainability mildly. Inspired by our theoretical insights on trainability, we propose Critical DropEdge, a connectivity-aware and graph-adaptive sampling method, to alleviate the exponential decay problem more fundamentally. Experimental evaluation consistently confirms using our proposed method can achieve better results compared to relevant counterparts with both infinite-width and finite-width.
arXiv comment26 pages
References in corpus (23)
- Semi-Supervised Classification with Graph Convolutional Networks
- Neural Message Passing for Quantum Chemistry
- Neural Tangent Kernel: Convergence and Generalization in Neural Networks
- Representation Learning on Graphs with Jumping Knowledge Networks
- Variational Graph Auto-Encoders
- A Convergence Theory for Deep Learning via Over-Parameterization
- DropEdge: Towards Deep Graph Convolutional Networks on Node Classification
- Deep Neural Networks as Gaussian Processes
- Towards Deeper Graph Neural Networks
- Simple and Deep Graph Convolutional Networks
- On Exact Computation with an Infinitely Wide Neural Net
- Exponential expressivity in deep neural networks through transient chaos
- DeeperGCN: All You Need to Train Deeper GCNs
- Scaling Limits of Wide Neural Networks with Weight Sharing: Gaussian Process Behavior, Gradient Independence, and Neural Tangent Kernel Derivation
- Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels
- How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks
- Towards Deeper Graph Neural Networks with Differentiable Group Normalization
- Tensor Programs II: Neural Tangent Kernel for Any Architecture
- Dynamics of Deep Neural Networks and Neural Tangent Hierarchy
- Infinite attention: NNGP and NTK for deep attention networks
- Critical percolation clusters in seven dimensions and on a complete graph
- Deep Graph Neural Networks with Shallow Subgraph Samplers
- On the Neural Tangent Kernel of Deep Networks with Orthogonal Initialization