{'fraction_non_alphanumeric': 0.02615103329824367, 'fraction_numerical': 0.006814781982381295, 'mean_word_length': 4.8718282368249834, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Pruning Graph Convolutional Networks to select meaningful graph frequencies for fMRI decoding

Graph Signal Processing is a promising framework to manipulate brain signals as it allows to encompass the spatial dependencies between the activity in regions of interest in the brain. In this work, we are interested in better understanding what are the graph frequencies that are the most useful to decode fMRI signals. To this end, we introduce a deep learning architecture and adapt a pruning methodology to automatically identify such frequencies. We experiment with various datasets, architectures and graphs, and show that low graph frequencies are consistently identified as the most important for fMRI decoding, with a stronger contribution for the functional graph over the structural one. We believe that this work provides novel insights on how graph-based methods can be deployed to increase fMRI decoding accuracy and interpretability.


I. INTRODUCTION
The development of Functional Magnetic Resonance Imaging (fMRI) has allowed to observe the brain in vivo and to address one of the central questions of cognitive neuroscience: understanding the relation between brain activation and cognitive functions or experimental conditions. Classical approaches have relied on forward inference (e.g., identifying localised effects in the brain corresponding to a change in the experimental condition) or reverse inference (e.g., inferring the cognitive function from brain activation patterns, which is typically done using single subjects linear statistical models). More recently, it has been suggested that brain decoding (e.g., predicting an experimental condition from patterns of brain activation) is a more formal way to perform reverse inference [1], as it allows to identify brain structures that are selectively engaged during a specific cognitive task. A few works have tested large-scale brain decoding using classic machine learning or deep learning paradigms applied to fMRI data from different subjects and tasks [2], [3]. Some of these studies have taken a step forward and tested graph convolutional networks to decode fMRI brain activity by also taking in account brain structural [4] or functional [5] connectivity, exploiting the promising framework of Graph Signal Processing (GSP).
GSP is a mathematical framework that aims at extending classical Fourier analysis to irregular domains represented by graphs. In particular, notions of graph frequencies, modes, and associated operators such as convolutions or filtering can then be defined. In the context of fMRI decoding, the use of GSPbased methods also brings forward interpretability questions.
In this work, we are interested in better understanding what are the graph frequencies that are the most useful to decode fMRI signals. To this end, we introduce a neural network architecture called spectral ResNet in which graph frequencies are used to define convolutions. Using a pruning technique, we dynamically identify which frequencies are the most useful to decode fMRI signals. We show that these frequencies are robust to changes in the datasets and the considered architectures. We perform experiments with both structural or functional graphs.

II. RELATED WORK
In this document, tensors and matrices are noted in bold uppercase, and vectors in bold lowercase. We access their entries using Python-style indexing, where : denotes all entries along the corresponding dimension. Constants are noted in uppercase, variables in lowercase, and sets in calligraphic.
GSP generalizes Fourier's approach to signals evolving on irregular structures by providing an adapted spectral space to decompose them in meaningful frequencies [6], [7]. In this framework, we consider a weighted and undirected graph G = V, E, W with vertices V = {v 1 , . . . , v N } of cardinal |V| = N , edges E ⊂ V × V, and a weighting function W : E → R. Such a graph can be equivalently represented by its weights matrix if i = j and 0 otherwise. From these two matrices, we can compute the normalized Laplacian matrix L = I N − D −1/2 WD −1/2 of G, where I N is the identity matrix of dimension N . Since L is real and symmetric, it can be diagonalized as L = UΛU , where U is a matrix of orthonormal vectors associated with eigenvalues forming the diagonal matrix Λ, sorted in increasing order. These eigenvalues are analogous to frequencies in Fourier analysis, and are called graph frequencies.
A signal x ∈ R N on G is an observation on each of its vertices. Its Graph Fourier Transformx = GFT(x) = U x shows the various contributions of eigenvalues of L in x. Its inverse x = GFT -1 (x) = Ux transforms a graph spectrum into a graph signal. Following the usual setting of Fourier Analysis, convolution can be defined as entrywise multiplication in the spectral space. In more details, denote h ∈ R N a filter, then convolution is obtained as: In previous works applying GSP to decode brain activity [4], [5], the focus has been mainly on increasing generalization accuracy. Here we aim at investigating which graph frequencies are the most relevant for brain decoding, and compare results for functional and structural graphs. We also assess the reliability of our results by applying the same analysis to two large scale datasets and testing different deep learning architectures. More specifically we address the following questions: 1) Which graph frequencies are the most relevant to predict the experimental task from corresponding fMRI activation maps? 2) Are these frequencies consistent for different underlying graphs (functional vs. structural) and deep learning architectures? 3) Does selecting specific graph frequency bands increase brain decoding performance?

III. METHODOLOGY
In this work, we aim at exploiting the graph on which input signals are defined to improve the classification of these signals and its interpretability in terms of relevant brain spatial patterns. The core idea of the proposed approach is to select by a learning process the appropriate graph frequencies within the signals. Beyond the performance aspect, this also provides an understandable representation of the signal features that are used for training a model. To reach this goal, we build a spectral model around a GSPConv layer, defined below.

A. GSPConv layer
A GSPConv layer is defined using a graph G with N vertices. It takes as input a matrix X ∈ R N ×cin seen as a graph signal with c in channels and outputs a matrix Z ∈ R N ×cout seen as a graph signal with c out channels. It contains a weight tensor Θ ∈ R N ×cin×cout and its mathematical function is: where GFT and GFT -1 are applied to each channel independently, σ is a nonlinear activation function, and ⊗ is such that In other words, a GSPConv is a natural extension of usual convolutional layers used in regular 1d or 2d domains.

B. Considered architectures
Using the GSPConv layer, we build a spectral ResNet, inspired by regular ResNets [8]. Such a model consists in assembling a first GSPConv layer, then spectral ResNet blocks (c.f. Figure 1), and finally a fully connected layer applied on globally averaged values over the graph. This architecture is summarized in Figure 1. It is parametrized by a depth d, and a number of channels γ. It contains a total number of trainable parameters O(γN + 2dγ 2 N + γC) where C is the number of classes in the considered problem.
For comparison purposes, we also propose an architecture based on a standard Multi-Layer Perceptron (MLP) which input domain is the graph frequency domain. For simplicity, we use a fixed number h of hidden neurons in each layer and a depth d. Such a model contains a total of O(hN +h 2 d+hC) trainable parameters.
C. Using pruning to identify important graph frequencies In the field of classification, pruning [9] is a very active topic of research that aims at identifying unimportant portions of deep learning architectures and remove them while maintaining a steady level of accuracy. The motivation is usually to reduce the number of parameters, hence the memory usage and the number of computations, resulting in lightweight models that can better fit constrained environments (e.g., edge computing). In this work, our aim is to adapt pruning in order to automatically identify the least important graph frequencies in our models, then prune them.
A pruning method usually combines multiple ingredients: 1-a pruning criterion which associates a subset of parameters in the considered architecture with an importance score, 2a pruning technique which is typically deployed onto the parameters with the lowest importance score and 3-a pruning schedule which defines how the pruning ingredients interact with the global learning schedule of the considered architecture. We choose to implement Selective Weight Decay (SWD) [10] because it has the asset of allowing any subset of frequencies to be removed at any time during the training procedure, avoiding harsh sudden effects of other methods, while being state-of-the-art in competitive vision benchmarks.
In short, SWD consists of the following: at each step of the learning process, we aggregate all weights associated with a particular graph frequency l into a linearized vector. For MLP, only the first layer of the architecture is concerned, whereas for Spectral ResNets, we combine all layers weight tensors Θ [l, ·, ·]. We then compute the magnitude of obtained vectors, and sort them in descending order. The K first vectors of weights are left untouched, and the remaining ones are applied an additional weight decay. This additional weight decay grows exponentially during the learning procedure, starting at a very low value α min so that the effect of SWD is almost unnoticeable, and finishing at a value α max so large that it boils down to nullifying the considered values. Once the procedure is finished, we identify the least important graph frequencies and remove them from the model, then we retrain the remaining parameters using the same scheduler as for baseline architectures, what is referred to as LR-rewinding [11] in the literature.
Note that pruning graph frequencies has a very different impact on the total number of parameters of considered models. For MLP, it reduces the parameters to O(hK + h 2 d + hC) whereas for Spectral ResNets, it reduces to O(γK +2dγ 2 K + γC), resulting in a way more dramatic effect. Fig. 1. Illustration of the Spectral ResNet model introduced in this paper. The input is seen as a graph signal with 1 channel, it is first embedded as a graph signal with γ channels using a GSPConv layer. Then it goes through d ResNet blocks consisting of the sum between a shortcut path and a sequential path containing 2 GSPConv layers. The output is seen as a graph signal with γ channels. The values are averaged over the graph before being fed to a classical logistic regression.

D. Neuroimaging Data and Graphs
Two datasets of spatial brain activation maps (obtained using general linear models of functional MRI signals [12]) were fetched from Neurovault [13]: the second release of IBC [14] (Neurovault collection 6618), consisting of 13 subjects with many experimental tasks, and 788 subjects out of the 900 subjects release of the Human Connectome Project [15] (Neurovault collection 4337). As labels for classification, we used the 24 tasks for IBC, and the 7 tasks for HCP. Here, we consider a large spectrum of experimental conditions ranging from motor to memory and social tasks. The datasets were split in training, validation and test splits. Following the usual supervised learning pipeline, training data was used to tune model parameters, validation data to monitor generalisation accuracy without parameter tuning, and the final accuracy reported is measured on the test set, using the model with the best validation accuracy. For HCP, 70 % of subjects were used for training, 15 % for validation and 15 % for test. For IBC eight subjects were used for training, three for validation and two for test. The obtained splits were all balanced.
In this work, we considered two brain graphs to build spectral filters. The first is an average structural graph estimated from diffusion weighted images of the HCP dataset (56 healthy subjects). Graph nodes correspond to the 360 regions of the Glasser atlas [16] while graph edges are a measure of structural connectivity strength, as described in [17]. We also considered another consensus graph, estimated from resting state fMRI data of 1080 HCP healthy subjects. Also, for the functional graph, the nodes correspond to the 360 regions of the Glasser atlas, while edges are a measure of the Pearson correlation between fMRI time-series during resting state [5]. In order to ensure that the brain graphs had good spectral properties while remaining connected, binarized k-nearest-neighbor graphs were built from the original structural and functional graphs by connecting each node to its k = 8 neighbors with strongest connectivity. All the considered models and datasets are available at our Github 1 .

IV. EXPERIMENTS
We conducted a set of experiments to answer the series of questions established in Section II.

A. Experimental details
As a first step, we ran numerous experiments to find good hyperparameters for our considered architectures. The optimal hyperparameters are displayed in Table I. Note that ResNets contain way more parameters than their MLP counterpart, but as mentioned in Section III, the number of these parameters dramatically reduces as we restrain the number of considered graph frequencies. We used batch normalization at the output of each GSPConv layer and rectified linear units as activation functions. We standardized the datasets (so that data is centered and unit-normed) before training and used mixup [18] during training. We report the averages and 95% confidence intervals over multiple runs.
We observe that there is no model that is universally better than the others in terms of raw performance. Yet the structural version of ResNet performs very poorly on IBC compared to the alternatives, suggesting the structural graph is less adapted to the considered datasets than its functional counterpart.

B. Impact of graph frequencies
To set up a baseline for the pruning methodology, we first evaluate the performance of the proposed architectures when we apply a band selection of the graph frequencies. To this end, we first identify which parts of the spectrum seem the most useful for decoding fMRI signals. The results are depicted in Figures 2(a) and 2(b). We fixed a bandwidth of 60 frequencies and varied the offset, which corresponds to the x axis. We observe that no matter the architecture nor the graph, best results are obtained by keeping the low graph frequencies.
In Figure 2(c), we vary the bandwidth when the offset is set to 0. We observe that keeping more than 60 frequencies does not benefit accuracy by a large margin. We again observe that the functional graph leads to better results overall than the structural one. Interestingly, in some cases keeping a portion of the frequencies leads to better results than the baselines.

C. Automated selection of optimal graph frequencies
We now test the proposed pruning methodology.  Figure 2(c), we observe that the baseline cannot be outperformed with a limited number of selected frequencies. Again, the structural graph leads to poorer performance, suggesting that it is not only its lower spectrum that is not aligned with the task but that overall it offers poorer discrimination capabilities on our benchmarks. Table II reports the best achieved gains with respect to our baselines, when using either the band or pruning method. We observe that pruning can consistently lead to improvements over all our experiments, whereas band selection degrades the performance in most considered scenarios. This table highlights the benefits of using the pruning methodology.
In Figure 3(c), we depict the frequencies selected using the pruning methodology, for various values of K, in the case of the spectral ResNets on the functional graph and IBC dataset. We perform 20 runs, and report the number of times each frequency was selected. Interestingly, we observe that the lower spectrum is overall preferred, even though it is not exactly a band of frequencies that is selected, explaining for the potential benefits over the predetermined frequency bands. We computed Intersection over Union (IoU) measures to quantify how reproducible these results are across datasets and architectures. Our IoU scores are typically above 50%, suggesting high reproducibility.
In Figure 4, we visualize on the glass brain the most frequently selected eigenvectors of the functional graph.  9] includes medial contributions of the default mode network [19]. These results show how the proposed methodology is able to identify meaningful graph frequencies (interpreted here as spatial patterns) for brain activity decoding. As we consider the graph frequencies common to all the tasks combined, general purpose brain patterns were found, consistent with the literature [20]. In future work we will investigate the potential of this methodology to identify spatial patterns characteristics of a specific decoded task or of a patient profile.

V. CONCLUSIONS
In this paper, we have introduced a simple deep learning architecture based on ResNets to process graph-based signals and applied it to fMRI decoding tasks. Using a pruning methodology, we selected the most important graph frequencies and observed that keeping 60 out of the 360 initial frequencies could lead to improved performance. Interestingly, the selected frequencies seem to be reproducible with other architectures and datasets. We believe that this study could help designing more efficient and interpretable graph neural networks for this important domain of application.

VI. ACKNOWLEDGMENT
We would like to thank Yu Zhang for providing the consensus functional graph. We also thank the region of Brittany for its support.