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

arXiv: https://arxiv.org/abs/2006.08550 · HTML: https://mlsanity.com/paper/2006.08550/

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jun 2020.

## Built on by (most cited first, 30 of 31)

- [On Provable Benefits of Depth in Training Graph Convolutional Networks](https://mlsanity.com/paper/2110.15174/) (2021)
- [Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depth](https://mlsanity.com/paper/2105.04550/) (2021)
- [Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networks](https://mlsanity.com/paper/2112.03968/) (2021)
- [Towards Understanding the Generalization of Graph Neural Networks](https://mlsanity.com/paper/2305.08048/) (2023)
- [A review of ensemble learning and data augmentation models for class imbalanced problems: combination, implementation and evaluation](https://mlsanity.com/paper/2304.02858/) (2023)
- [Generalization Guarantee of Training Graph Convolutional Networks with Graph Topology Sampling](https://mlsanity.com/paper/2207.03584/) (2022)
- [What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding](https://mlsanity.com/paper/2406.01977/) (2024)
- [Towards Bridging Generalization and Expressivity of Graph Neural Networks](https://mlsanity.com/paper/2410.10051/) (2024)
- [Deeper Insights into Deep Graph Convolutional Networks: Stability and Generalization](https://mlsanity.com/paper/2410.08473/) (2024)
- [GEFL: Extended Filtration Learning for Graph Classification](https://mlsanity.com/paper/2406.02732/) (2024)
- [Generalization Error of Graph Neural Networks in the Mean-field Regime](https://mlsanity.com/paper/2402.07025/) (2024)
- [Foundations and Frontiers of Graph Learning Theory](https://mlsanity.com/paper/2407.03125/) (2024)
- [Learning from one graph: transductive learning guarantees via the geometry of small random worlds](https://mlsanity.com/paper/2509.06894/) (2025)
- [Layer-wise Adaptive Graph Convolution Networks Using Generalized Pagerank](https://mlsanity.com/paper/2108.10636/) (2021)
- [Information-Theoretic Generalization Bounds for Transductive Learning and its Applications](https://mlsanity.com/paper/2311.04561/) (2023)
- [PAC-Bayesian Generalization Bounds for Knowledge Graph Representation Learning](https://mlsanity.com/paper/2405.06418/) (2024)
- [On the Interplay between Graph Structure and Learning Algorithms in Graph Neural Networks](https://mlsanity.com/paper/2508.14338/) (2025)
- [Relational Graph Neural Network Design via Progressive Neural Architecture Search](https://mlsanity.com/paper/2105.14490/) (2021)
- [A Model-Agnostic Graph Neural Network for Integrating Local and Global Information](https://mlsanity.com/paper/2309.13459/) (2023)
- [Generalization of Graph Neural Networks through the Lens of Homomorphism](https://mlsanity.com/paper/2403.06079/) (2024)
- [Tuning Algorithmic and Architectural Hyperparameters in Graph-Based Semi-Supervised Learning with Provable Guarantees](https://mlsanity.com/paper/2502.12937/) (2025)
- [RCCFormer: A Robust Crowd Counting Network Based on Transformer](https://mlsanity.com/paper/2504.04935/) (2025)
- [A Note on Graphon-Signal Analysis of Graph Neural Networks](https://mlsanity.com/paper/2508.18564/) (2025)
- [Graph Polynomial Convolution Models for Node Classification of Non-Homophilous Graphs](https://mlsanity.com/paper/2209.05020/) (2022)
- [Stability and Generalization of lp-Regularized Stochastic Learning for GCN](https://mlsanity.com/paper/2305.12085/) (2023)
- [UPL: Uncertainty-aware Pseudo-labeling for Imbalance Transductive Node Classification](https://mlsanity.com/paper/2502.00716/) (2025)
- [Theoretical Learning Performance of Graph Neural Networks: The Impact of Jumping Connections and Layer-wise Sparsification](https://mlsanity.com/paper/2507.05533/) (2025)
- [PAC-Bayesian Generalization Bounds for Graph Convolutional Networks on Inductive Node Classification](https://mlsanity.com/paper/2509.06600/) (2025)
- [On Local Limits of Sparse Random Graphs: Color Convergence and the Refined Configuration Model](https://mlsanity.com/paper/2510.21392/) (2025)
- [Rethinking Generalization in Graph Neural Networks: A Structural Complexity Perspective](https://mlsanity.com/paper/2605.13597/) (2026)

## Abstract (arXiv)

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.