Graph Convolutional Networks: A Critical Review

Graph convolutional networks (GCNs) extend deep learning to graph-structured data using spectral graph theory and spatial message passing. Despite their success, their mathematical foundations remain fragmented. This review mathematically analyzes GCNs by focusing on architecture, theoretical foundations, and fundamental limitations. We propose a unified perspective on graph convolutions by analyzing when spectral filtering and spatial aggregation coincide or diverge, thereby clarifying how convolution can be rigorously defined on irregular graph domains. A central theme is the expressive power of GCNs, which is formulated through the lens of the Weisfeiler–Lehman test and the structural bottlenecks it imposes on graph discrimination. We examine over-smoothing by characterizing how repeated message passing leads to representational collapse, and we complement these analyses with visualizations of entropy loss in node embeddings as depth increases. In addition, we review recent theoretical results on the optimization landscape and convergence behavior of GCN training, highlighting how depth, normalization, and regularization influence trainability. The review further addresses GCN generalization by analyzing theoretical guarantees and failure modes under structural distribution shifts, random perturbations, and adversarial noise. The assessment includes an in-depth spectral analysis of perturbation sensitivity and its relation to the eigenvalue spectrum of the graph Laplacian. The findings highlight that GCNs suffer from limited expressivity and generalization under structural shifts and adversarial perturbations. We advocate for future research on expressive and stable architectures via Lipschitz-continuous designs, denoising-based preprocessing, and spectral regularization. This review serves as a resource and a roadmap for advancing theoretical understanding and practical robustness in GCNs.