A Spectral Characterization of Generalization in GCN: Escaping the Curse of Dimensionality
Lists
Only you see this
Abstract
Empirically it is observed that Graph Convolution Networks (GCNs) often generalize better than fully connected neural networks (FCNNs) on graph-structured data. While this observation is often attributed to the ability of GCNs to exploit knowledge about the underlying graph structure, a rigorous theoretical explanation remains limited. In this work, we theoretically prove that one factor for the improved generalization of GCNs arises from the spectral representation of the filters or graph convolutional layers. Specifically, we derive generalization bounds that are independent of the number of parameters and instead scale nearly linearly with the number of graph nodes, offering a compelling explanation for their superior performance in over-parameterized regimes. Furthermore, in the limit of infinite number of nodes, we prove that under certain regularity conditions on the spectrum, GCNs escape the curse of dimensionality and continue to generalize well. We demonstrate our conclusions through numerical experiments.
BibTeX
@misc{tadipatri2026spectral,
author = {Uday Kiran Reddy Tadipatri and Benjamin David Haeffele and Alejandro Ribeiro and Rene Vidal},
title = {{A Spectral Characterization of Generalization in GCN: Escaping the Curse of Dimensionality}},
year = {2026},
url = {https://openreview.net/forum?id=5e8T1EAsf6},
howpublished = {OpenReview},
note = {Submitted to ICLR 2026},
}Loading related content...