Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networks

Abstract

It is known that the current graph neural networks (GNNs) are difficult to make themselves deep due to the problem known as over-smoothing. Multi-scale GNNs are a promising approach for mitigating the over-smoothing problem. However, there is little explanation of why it works empirically from the viewpoint of learning theory. In this study, we derive the optimization and generalization guarantees of transductive learning algorithms that include multi-scale GNNs. Using the boosting theory, we prove the convergence of the training error under weak learning-type conditions. By combining it with generalization gap bounds in terms of transductive Rademacher complexity, we show that a test error bound of a specific type of multi-scale GNNs that decreases corresponding to the number of node aggregations under some conditions. Our results offer theoretical explanations for the effectiveness of the multi-scale structure against the over-smoothing problem. We apply boosting algorithms to the training of multi-scale GNNs for real-world node prediction tasks. We confirm that its performance is comparable to existing GNNs, and the practical behaviors are consistent with theoretical observations. Code is available at https://github.com/delta2323/GB-GNN.

9 pages, Reference 6 pages, Supplemental material 18 pages. Accepted at Neural Information Processing Systems (NeurIPS) 2020

References in corpus (21)

• PyTorch: An Imperative Style, High-Performance Deep Learning Library
• Inductive Representation Learning on Large Graphs
• Neural Message Passing for Quantum Chemistry
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Simplifying Graph Convolutional Networks
• Representation Learning on Graphs with Jumping Knowledge Networks
• DropEdge: Towards Deep Graph Convolutional Networks on Node Classification
• Simple and Deep Graph Convolutional Networks
• Algorithms for Learning Kernels Based on Centered Alignment
• Revisiting Graph Neural Networks: All We Have is Low-Pass Filters
• Topology Adaptive Graph Convolutional Networks
• PairNorm: Tackling Oversmoothing in GNNs
• LanczosNet: Multi-Scale Deep Graph Convolutional Networks
• Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels
• Data-dependent Sample Complexity of Deep Neural Networks via Lipschitz Augmentation
• Generalization and Representational Limits of Graph Neural Networks
• GResNet: Graph Residual Network for Reviving Deep GNNs from Suspended Animation
• Deterministic PAC-Bayesian generalization bounds for deep networks via generalizing noise-resilience
• AdaGCN: Adaboosting Graph Convolutional Networks into Deep Models
• Generalized Boosting Algorithms for Convex Optimization
• Semi-supervised learning of hierarchical representations of molecules using neural message passing