Neurodiversity Meets Colors: Does Position Awareness Destroy Generalization in Brain Graph Learning?

Graph Neural Networks (GNNs) rely on permutation invariance to exploit symmetries in graph data using principles of Geometric Deep Learning. However, in machine learning models that process fMRI data using a brain atlas, each node corresponds to a region with its own position and neurological function. Thus, permutation invariance would make the model unaware of these aspects, causing a significant loss of biological interpretability and predictive information. For this reason, many GNN architectures opt for assigning each ROI ("Region Of Interest" in the brain) a unique node representation, either explicitly or implicitly through feature engineering, before using the graph as input for the GNN. In this theoretical study, we investigate the consequences of that choice. First, we prove that, if each ROI is explicitly identified with a unique color, it is possible to achieve perfect expressivity using a GNN with a single max-aggregation message-passing layer, which suffices to attain the maximal Rademacher complexity and very loose VC dimension's bounds. Building on that, we derive generalization bounds based on concrete parameters of the model, such as ROI embedding dimension and atlas size, revealing ways in which this tradeoff could manifest in practice. These findings are particularly relevant in the context of fMRI graph learning, where, despite severe struggles with overfitting and data scarcity, generalization theory is still underexplored.