为动态图上的节点分类提供理论保障，揭示了GCN泛化能力的关键条件。
PAC-Bayesian Generalization Bounds for Graph Convolutional Networks on Inductive Node Classification
- 用PAC-Bayesian框架分析依赖性节点的泛化性能，考虑数据非独立同分布。
- 证明单层GCN在节点数增加时泛化误差趋于零，需满足特定图结构条件。
- 拓展到两层网络，发现对图拓扑要求更强，适合研究动态图学习的学者。
图神经网络（GNNs）在处理各类图结构数据中取得了显著成功。真实世界图具有动态特性，新节点持续加入，连接关系可能随时间变化。以往的理论研究多基于归纳学习框架，难以充分建模这种时间演化与结构动态性。本文针对归纳节点分类任务，对图卷积网络（GCNs）进行了PAC-Bayesian理论分析，将节点视为相关且非独立同分布的数据点。我们推导出适用于单层GCN的新泛化界，明确引入了数据依赖性和非平稳性的影响，并建立了当节点数量增加时泛化差距趋于零的充分条件。进一步地，我们将分析扩展至两层GCN，发现需对图拓扑施加更强假设才能保证收敛。该工作为理解并改进动态图环境下GNN的泛化能力提供了理论基础。
原文摘要 · Abstract (English)
Graph neural networks (GNNs) have achieved remarkable success in processing graph-structured data across various applications. A critical aspect of real-world graphs is their dynamic nature, where new nodes are continually added and existing connections may change over time. Previous theoretical studies, largely based on the transductive learning framework, fail to adequately model such temporal evolution and structural dynamics. In this paper, we presents a PAC-Bayesian theoretical analysis of graph convolutional networks (GCNs) for inductive node classification, treating nodes as dependent and non-identically distributed data points. We derive novel generalization bounds for one-layer GCNs that explicitly incorporate the effects of data dependency and non-stationarity, and establish sufficient conditions under which the generalization gap converges to zero as the number of nodes increases. Furthermore, we extend our analysis to two-layer GCNs, and reveal that it requires stronger assumptions on graph topology to guarantee convergence. This work establishes a theoretical foundation for understanding and improving GNN generalization in dynamic graph environments.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。