论文标题
通过梯度提升和应用于多尺度图神经网络的梯度进行过渡的优化和概括分析
Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networks
论文作者
论文摘要
众所周知，由于所谓的过度平滑的问题，当前的图形神经网络（GNN）很难使自己深入。多尺度的GNN是缓解过度平滑问题的有前途的方法。但是，从学习理论的角度来看，几乎没有解释它为何从经验上起作用。在这项研究中，我们得出了包括多规模GNN在内的跨隔离学习算法的优化和概括保证。使用增强理论，我们证明了在弱学习类型条件下训练误差的收敛性。通过将其与泛化间隙界限结合在转导ademacher复杂性方面，我们表明，特定类型的多尺度GNN的测试误差绑定，该误差降低了与某些条件下的节点聚集数量相对应的。我们的结果为多尺度结构针对过度平滑问题的有效性提供了理论上的解释。我们将增强算法应用于对现实节点预测任务的多尺度GNN的培训。我们确认其性能与现有的GNN相当，并且实际行为与理论观察一致。代码可从https://github.com/delta2323/gb-gnn获得。
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.
