PAC-Bayesian Generalization Bounds for Graph Convolutional Networks on Inductive Node Classification
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Node ClassificationSimilar Papers 제목 키워드 기반
PAC-Bayesian Adversarially Robust Generalization Bounds for Graph Neural Network
Graph neural networks (GNNs) have gained popularity for various graph-related tasks. However, similar to deep neural networks, GNNs are also vulnerable to adversarial attacks. Empirical studies have shown that adversaria…
Generalization BoundsGraph Neural NetworkA PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks
In this paper, we derive generalization bounds for the two primary classes of graph neural networks (GNNs), namely graph convolutional networks (GCNs) and message passing GNNs (MPGNNs), via a PAC-Bayesian approach. Our r…
Generalization BoundsTopology-Aware PAC-Bayesian Generalization Analysis for Graph Neural Networks
Graph neural networks have demonstrated excellent applicability to a wide range of domains, including social networks, biological systems, recommendation systems, and wireless communications. Yet a principled theoretical…
Stochastic OptimizationRecommendation SystemsGraph ClassificationGeneralization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusion
Graph neural networks are widely used tools for graph prediction tasks. Motivated by their empirical performance, prior works have developed generalization bounds for graph neural networks, which scale with graph structu…
Generalization BoundsPAC-Bayesian Margin Bounds for Convolutional Neural Networks
Recently the generalization error of deep neural networks has been analyzed through the PAC-Bayesian framework, for the case of fully connected layers. We adapt this approach to the convolutional setting.