Why Does Your Graph Neural Network Fail on Some Graphs? Insights from Exact Generalisation Error

Nil Ayday, Mahalakshmi Sabanayagam, Debarghya Ghoshdastidar · 2025

Read Why Does Your Graph Neural Network Fail on Some Graphs? Insights from Exact Generalisation Error by Nil Ayday, Mahalakshmi Sabanayagam, Debarghya Ghoshdastidar (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-10337.txt.

Introduction

Nil Ayday and two co-authors compute the exact generalization error of linear graph neural networks in this 2025 machine learning paper. Rather than loose bounds, they derive the precise gap between predictions and true values for convolutional, PageRank-based, and attention-style models, viewing the networks through signal processing.

Their exact formula exposes a skew in the field's favorite benchmarks: popular datasets line up node features with graph structure so neatly that some architectures win by construction. They also show that homophily, the tendency of connected nodes to resemble each other, decides which architecture suits a given graph. The upshot is a clearer explanation of when graph networks truly exploit structure, and why reported results vary so much between lookalike models.

Catalog record

CREATORNil Ayday, Mahalakshmi Sabanayagam, Debarghya Ghoshdastidar
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE95 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-10337

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Why Does Your Graph Neural Network Fail on Some Graphs? Insights from Exact Generalisation Error Nil Ayday, Mahalakshmi Sabanayagam, Debarghya Ghoshdastidar Abstract Graph Neural Networks (GNNs) are widely used in learning on graph-structured data, yet a principled understanding of why they succeed or fail remains elusive. While prior works have examined architectural limitations such as over-smoothing and over-squashing, these do not explain what enables GNNs to extract meaningful representations or why performance varies drastically between similar architectures. These questions are related to the role of generalisation: the ability of a model to make accurate predictions on unlabelled data. Although several works have derived generalisation error bounds for GNNs, these are typically loose, restricted to a single architecture, and offer limited insight into what governs generalisation in practice. In this work, we take a different approach by deriving the exact generalisation error for GNNs in a transductive fixed-design setting through the lens of signal processing . From this viewpoint, GNNs can be interpreted as graph filter operators that act on node features via the graph structure. By focusing on linear GNNs while allowing non-linearity in the graph filters, we derive the first exact generalisation error for a broad range of GNNs, including convolutional, PageRank-based, and attention-based models. The exact characterisation of the generalisation error reveals that only the aligned information between node features and graph structure contributes to generalisation. Furthermore, we quantify the effect of homophily on generalisation. Our work provides a framework that explains when and why GNNs can effectively leverage structural and feature information, offering practical guidance for model selection. 1 Introduction Graph Neural Networks (GNNs) have emerged as a central paradigm, achieving state-of-the-art results on non-Euclidean, graph-structured data across various tasks ranging from social networks analysis ( Fan et al. 2019 ) to molecular property prediction ( Buterez et al. 2024 ) . Their success is primarily attributed to their ability to learn meaningful representations by effectively integrating node features and graph structure information. Despite widespread application and progress in developing a suite of GNNs, the statistical understanding of what allows GNNs to extract meaningful representations and what limits their performance remains largely incomplete. Recent theoretical works have attempted to shed light on GNNs from multiple perspectives, including signal processing, expressivity analysis, and generalisation error bounds. From a signal processing perspective, GNNs can be considered as graph filters ( NT and Maehara 2019 ) that operate on signals defined over the nodes of a graph. In this context, the signal refers to the feature vectors associated with each node, representing the information to be propagated across the graph. A graph filter modifies these signals by using the graph structure and producing meaningful representations. Analogous to traditional signal processing, where the goal is to extract informative patterns from raw signals, GNNs aim to learn useful representations by combining the feature information with graph structure. The signal processing view is closely related to the traditional distinction between spectral and spatial GNNs. Spectral GNNs ( Defferrard et al. 2016 , Klicpera et al. 2019 , Chien et al. 2021 , He et al. 2022 ) define the aggregation process, namely the propagation of features across the graph in the spectral domain of the graph Laplacian, which is a matrix representation of a graph that encodes structure information. Whereas, spatial GNNs ( Kipf and Welling 2017 , Xu et al. 2019 , Velickovic et al. 2018 ) define neighbourhood-based operations directly on the graph topology. Recent work ( Balcilar et al. 2021 ) has shown that this distinction can be bridged: many GNN architectures can be defined by their frequency response , a spectral function applied to the eigenvalues of the Laplacian. The frequency response reveals the kind of filter a GNN can represent. For example, Graph Convolutional Networks (GCNs) ( Kipf and Welling 2017 ) are known to behave as low-pass filters ( NT and Maehara 2019 ) suppressing high-frequency components. While this characterisation has deepened our understanding of the representational power of GNNs, a principled analysis of their generalisation ability from this perspective remains underexplored. On the other hand, a significant body of research has focused on expressivity analysis to characterise the representational power of GNNs through the lens of the model’s ability to distinguish between different graph structures ( Zhang et al. 2025 ) . The typical analysis is based on the Weisfeiler–Lehman (WL) graph isomorphism test, which determines whether two graphs are topologically equivalent, i.e., isomorphic. Specifically, Xu et al. 2019 and Morris et al. 2019 show that most spatial GNNs are at most as powerful as the 1-WL test in distinguishing graph structures. However, expressivity alone fails to explain the observed generalisation behaviour of these models. Notably, GCNs and Graph Attention Networks (GAT) ( Velickovic et al. 2018 ) are both bounded by 1-WL expressivity, yet exhibit significantly different performance across datasets–GAT performs better than GCN. This disparity highlights that expressivity can only characterise what a model could learn in principle, but not how well it generalises across different input signals. Generalisation error measures a model’s predictive performance on data with unknown targets (labels). While empirical results can demonstrate that a model works in practice, they often cannot explain the underlying reasons for good performance. On the other hand, deriving the generalisation error enables us to understand the conditions under which a GNN is expected to succeed or fail. Prior works on understanding the failure scenarios of GNNs have primarily focused on oversmoothing ( Keriven 2022 ) , where node representations become indistinguishable, but oversmoothing alone does not fully explain the performance gap across different models or input data, motivating a deeper investigation of the generalisation error. Several prior works have bounded the generalisation error of GNNs using tools from statistical learning theory. These include approaches based on algorithmic stability ( Verma and Zhang 2019 , Zhou and Wang 2021 ) , Rademacher complexity ( Esser et al. 2021 , Lv 2021 ) , and PAC-Bayes theory ( Liao et al. 2021 ) . However, these bounds are often restricted to a single architecture, loose, and do not capture the true generalisation. Recent works explore connections between generalisation and expressivity ( Rauchwerger et al. 2025 , Li et al. 2025 ) , but their bounds are limited to spatial GNNs and offer limited practical insight. Even deriving bounds for GNNs is challenging due to the dependencies in the graph data, unlike traditional machine learning settings with independent data samples ( Bartlett et al. 2019 ) . We therefore ask the following questions: Is it possible to derive exact generalisation error for GNNs? Consequently, can we gain insights into the role of the graph data—features, structure, and targets—as well as the effect of the graph filter? Technical Contributions. We answer both questions positively by developing a novel theoretical framework based on a signal processing perspective. We consider a semi-supervised learning problem, where the model has access to the Laplacian, node features, and targets of the nodes in the training set, and the task is to predict the targets of the test nodes. In Section 3 , we derive the exact generalisation error of GNNs as a function of the eigenvalues of the Laplacian. Unlike previous works typically restricted

Read the complete text