MIT博士论文 | 图指导的预测（含GNN的泛化能力和表示能力分析）

下载链接：

链接: https://pan.baidu.com/s/1eIZdR6l_dWYrO4PnZYxk4A?pwd=gkac

提取码: gkac

Graph neural networks (GNNs) are naturally suited for making predictions based on graphs but they remain poorly understood in terms of what they can and cannot do. We analyze whether GNNs can distinguish graphs that differ in properties such as cycles, but have similar local structure. We also investigate data dependent generalization bounds for GNNs.

3 Generalization and Representational Limits of Graph Neural Networks 59

3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

3.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

3.3 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

3.4 Representation limits of GNNs . . . . . . . . . . . . . . . . . . . . . . . . . 66

7 3.5 Generalization bounds for GNNs . . . . . . . . . . . . . . . . . . . . . . . . 71

3.5.1 From Graphs to Trees . . . . . . . . . . . . . . . . . . . . . . . . . . 74

3.5.2 Generalization Bound for GNNs . . . . . . . . . . . . . . . . . . . . 75

3.5.3 Toward generalization analysis for CPNGNNs . . . . . . . . . . . . . 80

3.6 Appendix: Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88