Understanding Sparse Neural Networks from their Topology via
  Multipartite Graph Representations
Pruning-at-Initialization (PaI) algorithms provide Sparse Neural Networks
(SNNs) which are computationally more efficient than their dense counterparts,
and try to avoid performance degradation. While much emphasis has been directed
towards \emph{how} to prune, we still do not know \emph{what topological
metrics} of the SNNs characterize \emph{good performance}. From prior work, we
have layer-wise topological metrics by which SNN performance can be predicted:
the Ramanujan-based metrics. To exploit these metrics, proper ways to represent
network layers via Graph Encodings (GEs) are needed, with Bipartite Graph
Encodings (BGEs) being the \emph{de-facto} standard at the current stage.
Nevertheless, existing BGEs neglect the impact of the inputs, and do not
characterize the SNN in an end-to-end manner. Additionally, thanks to a
thorough study of the Ramanujan-based metrics, we discover that they are only
as good as the \emph{layer-wise density} as performance predictors, when paired
with BGEs. To close both gaps, we design a comprehensive topological analysis
for SNNs with both linear and convolutional layers, via (i) a new input-aware
Multipartite Graph Encoding (MGE) for SNNs and (ii) the design of new
end-to-end topological metrics over the MGE. With these novelties, we show the
following: (a) The proposed MGE allows to extract topological metrics that are
much better predictors of the accuracy drop than metrics computed from current
input-agnostic BGEs; (b) Which metrics are important at different sparsity
levels and for different architectures; (c) A mixture of our topological
metrics can rank PaI algorithms more effectively than Ramanujan-based metrics.
The codebase is publicly available at https://github.com/eliacunegatti/mge-snn.
Elia Cunegatti, Matteo Farina, Doina Bucur, Giovanni Iacca
# Peeking inside Sparse Neural Networks using Multi-Partite Graph Representations

###### Abstract

Modern Deep Neural Networks (DNNs) have achieved very high performance at the expense of computational resources. To decrease the computational burden, several techniques have proposed to extract, from a given DNN, efficient subnetworks which are able to preserve performance while reducing the number of network parameters. The literature provides a broad set of techniques to discover such subnetworks, but few works have studied the peculiar topologies of such pruned architectures. In this paper, we propose a novel _unrolled input-aware_ bipartite Graph Encoding (GE) that is able to generate, for each layer in an either sparse or dense neural network, its corresponding graph representation based on its relation with the input data. We also extend it into a multipartite GE, to capture the relation between layers. Then, we leverage on topological properties to study the difference between the existing pruning algorithms and algorithm categories, as well as the relation between topologies and performance.

## 1 Introduction

Pruning Dense Neural Networks (DNNs) has recently become one of the most promising research areas in machine learning. Network pruning consists in removing a portion of network parameters (i.e., weights) aiming at reducing the computational resources and the inference time while avoiding performance degradation. Currently, one of the most important findings in network pruning [26] proved that, inside a randomly initialized DNN, there are subnetworks (the so-called _"winning tickets"_) that once trained in isolation can reach the performance of the overall dense network.

The algorithms proposed to find such subnetworks can be roughly split into four categories, which differ in _how_ and _when_ they uncover the sparse architecture. The earliest works focus on _Post-Training Pruning_, i.e., methods that, once the dense network has been fully trained, are able to uncover the sparse structures using simple heuristics to remove the lower-magnitude weights from the trained network [33, 50, 3, 19]. To decrease the computational cost of training the whole DNN, [54] and [46] propose a dense-to-sparse pruning technique employing Gradual Magnitude Pruning (GMP) to reduce the number of parameters during the training phase. The Lottery Ticket Hypothesis (LTH) [26] discovers the final sparse structure using an iterative process of training-pruning. A second group of algorithms focuses instead on _Pruning at Initialization (PaI)_, where the subnetwork is retrieved prior to training, based on a scoring criterion calculated on randomly initialized weights [35, 8, 37, 44, 1]. A third family of algorithms, called _Dynamic Sparse Training (DST)_ techniques, aims at modifying the structure of the sparse network during the training process [18, 12, 34, 45, 14, 30]. The last category of pruning algorithms, based on the so-called _Strong Lottery Ticket Hypothesis (SLTH)_, differs from the previous categories since the weights are not trained at all [20, 49, 27].

Applying such pruning algorithms to a DNN \(f(x,\theta)\) provides a binary mask \(m\in\{0,1\}^{|\theta|}\) that generates a Sparse Neural Network (SNN) \(f(x,m\ominus\theta)\) characterized by a certain topology. While many papers have investigated _how_ to find sparse architectures, only a few looked at _why_ (from a topological viewpoint) SNNs perform well, and _how_ different pruning algorithms actually produce different SNN topologies. An SNN has indeed a unique topology, whose graph representation can be constructed and analyzed [31, 36]. The state-of-the-art in graph construction for SNNs with convolutional layers is based on _rolled_ representations [17, 36, 13], where each node represents a layer parameter, i.e., either a filter/channel or a kernel value. However, such _rolled_ representations do not capture the complete structure of the network. In fact, in these representations, the kernel parameters are used as static nodes. On the other hand,
convolutional operations use the kernel _dynamically_ over the input data. The latter can be represented as nodes only in _unrolled_ representations, see [4].

To overcome this limitation, we propose a novel _unrolled input-aware_ Graph Encoding (GE) which fully represents the relation between the layer parameters and the layer input data. This encoding is radically different from all the _rolled_ encodings previously proposed in the literature for the complete graph representation of convolutional layers. In particular, unlike the weighted _unrolled_ GE proposed in [4], which is only designed to associate the weights of a DNN to graph edges, our proposed GE works with both dense and sparse architectures and focuses on the presence/absence of edges, rather than their weights. Furthermore, our GE generates one bipartite graph _for each layer_, rather than one bipartite graph _for each combination of input feature maps and filters_, as in [4]. Our GE works as follows: it takes as input a neural network (dense or sparse), and the input data size, and generates one bipartite graph for each layer. Nodes correspond to that layer's inputs (e.g., in computer vision tasks, these are pixels in feature maps) while edges correspond to the masked/unmasked relation between those inputs and the output features, which in turn is based on the pruned layer parameters (in the case of SNNs; in the case of DNNs, all parameters are considered). We then extend this GE into a multipartite graph, to describe relations between layers.

Finally, we use the proposed GE to thoroughly study different categories of state-of-the-art unstructured pruning algorithms, to "peek inside" the SNNs they generate, and to understand how the _topological features_ of those SNNs are related to their _performance drop_ w.r.t. their corresponding DNNs, especially at extreme sparsity levels. We base our analysis on a large pool of SNNs obtained by combining eleven pruning algorithms, five sparsity ratios, three datasets, and four Convolutional Neural Networks (CNNs) benchmarked in the literature on SNNs, such as Conv-6 [26], as well as on state-of-the-art CNNs, such as ResNet [22], Wide-Resnet [53], and MobileNet [23; 38].

To summarize, the main contributions of this paper can be outlined as follows:

1. a novel _unrolled input-aware_ GE which correctly reflects the convolutional operations, and links consecutive layers into a single multipartite graph representing the whole SNN;
2. an extensive study about how each pruning algorithm (and algorithm category) generates sparse topologies with similar patterns;
3. an analysis of which topological features can predict the performance drop of SNNs.

## 2 Related Work

We summarize the literature on pruning algorithms and graph representations of neural networks.

### Pruning Algorithms

**Pruning at Initialization.** This set of algorithms aims at discovering the best subnetwork (prior to training) and selecting the weights based on some predefined criteria. The earliest approach of this kind is SNIP [35], which aims at selecting the weights based on their influence on the loss function. Moreover, an iterative version of SNIP is presented in [37]. GraSP [8] applies a gradient signal preservation mechanism based on Hessian-gradient product, while SynFlow [44] maximizes the synaptic strengths. More recently, ProsPR [1] has been devised in order to maximize the trainability throughout meta-gradients on the first steps of the optimization process. Lastly, NTK-SAP [51] uses neural tangent kernel theory to remove the less informative connections. These approaches are relatively cheap in terms of computational cost, since the mask is found before training. However, while increasing the sparsity ratios, the performances deteriorate faster than with other categories of pruning algorithms, due to the difficulty of training SNNs from scratch [16; 15] and to the fact that the architecture is statically determined and cannot change during the training phase.

**Dynamic Sparse Training.** This category of algorithms has been proposed to tackle the aforementioned limitations of PaI, thus allowing higher performance at the cost of a slight increase of the computational cost. Using gradient information retrieved during the training, sparse architectures can change their topology based on magnitude pruning followed by a pre-defined growth criteria e.g. based on random growth [12; 34], momentum [45], or absolute gradients [14]. To overcome the limitation of fixed layer-wise sparsity ratio, a few reparametrization techniques have been proposed [34; 45], in order to better allocate parameters over layers.

**Sanity Checks.** Recent works [43; 25] have questioned the ability of PaI algorithms to uncover the most effective architectures, stating that they rather focus on discovering the best _layer-wise sparsity ratios_. Their ability to improve performance over random pruning algorithms has been discussed in [39], which shows how even small perturbations of random pruning (Layer-wise Random Pruning such as ER [12] and ERK [14]) are able to outperform well-engineered PaI algorithms.
### Graph Representation of Sparse and Dense Neural Networks

In order to gain insights from DNN topologies, several works have tried to devise weighted graph representations of the networks. Based on such representations, early-stopping criteria [4], customized initialization techniques [29], and performance predictors [47; 48] have been introduced.

What sets an SNN apart from a DNN is its unique topology, which can provide insight into its ability to solve a given task even when removing a portion of parameters. Grounded in graph theory, the random generation of small sparse structures for both Multi-Layer Perceptrons (MLPs) [6; 42] and CNNs [52] has been studied, showing that performance is associated with the _clustering coefficient_ (which measures the capacity of nodes to cluster together) and the _average path length_ of its graph representation (i.e., the average number of connections across all shortest paths).

To investigate the topological properties of SNNs, different metrics have been proposed. In [31], Graph-Edit-Distance has been used as a similarity measure, computed only on MLPs, to show how the graph topology evolves using a _Dynamic Sparse Training_ algorithm such as SET [12]. By using Singular Vector Canonical Correlation Analysis, in [5; 2] it has been shown that different topologies are able to achieve similar performances. Clusterability has been taken into account in [17], showing that MLPs are more clusterable than CNNs. Finally, the performance of SNNs has been investigated via basic graph properties [41] and by means of Ramanujan graphs for Pal algorithms, indicating that performances are correlate to the graph connectivity [36] and can be predicted e.g. using the Iterative Mean Difference of Bound (IMDB) [13].

In all the works mentioned above, the graph representation of the convolutional layers is modelled either with a relational graph [52], or with a _rolled_ encoding based only on the kernel parameters [36; 13], rather than on the relationship between the latter and the input data. To the best of our knowledge, so far only [4] proposed an _unrolled_ GE but, besides the fact that it considers the network weights, this method generates several bipartite graphs for each convolutional layer, while our approach generates only one bipartite graph per layer. From a topological point of view, the approach from [4] has in fact two main limitations. Firstly, it does not make possible to directly calculate topological measures for any layer, since each graph contains only partial information about it. Secondly, since in the convolutional operations each \(j^{th}\) filter is convoluted with the \(a^{th}\) input feature map one by one, separating these operations does not allow computing the correct final contribution over the input data.

## 3 Methodology

In this section, we first introduce the novel _unrolled input-aware_ graph encoding and its formulation in the _bipartite_ version. We then extend it to the _multipartite_ version, which links consecutive layers. Finally, we propose topological metrics that can be extracted from such GEs.

### Bipartite Graph Encoding (BGE)

The proposed BGE encodes a neural network as a list of unweighted directed acyclic bipartite graphs \(G=(G_{1},\ldots,G_{N})\), with \(N\) the number of layers in the neural network. The individual graphs are not linked into a single graph. Our notation is summarized in Table 1.

Due to its design, the bipartite graph construction differs for linear and convolutional layers. For linear layers, we use the encoding proposed in [4; 17; 47; 13]: denoting with \(L\) and \(R\) respectively the left and right layer of the \(i\)-th bipartite

\begin{table}
\begin{tabular}{l l} \hline \hline
**Symbol** & **Definition** \\ \hline \(G=(L\cup R,E)\) & bipartite graph with left node set \(L\), right node set \(R\) (for a \\  & total of \(|L|+|R|\) nodes), and edge set \(E\) \\ \hline \(N\) & number of layers \\ \(h,w\) & height and width of the input feature map \\ \(M\) & binary mask of pruned/unpruned weights \\ \(W\) & layer parameters \\ \(h_{\text{\tiny{br}}},v_{\text{\tiny{br}}}\) & height and width of kernel \\ \(c_{\text{\tiny{in}}},c_{\text{\tiny{our}}}\) & number of input and output channels \\ \(P,S\) & padding, stride \\ \hline \hline \end{tabular}
\end{table}
Table 1: Notation used in the paper. We consider the case of vision tasks.
graph, and given a binary mask \(M_{i}\in\{0,1\}^{|L_{i}|\times|R_{i}|}\), its corresponding GE is \(G_{i}=(L_{i}\cup R_{i},E_{i})\), where \(E_{i}\) is the set of edges present in \(M_{i}\), i.e., \((a,b)\in E_{i}\iff M_{i}^{a,b}\neq 0\).

For convolutional layers, our approach is substantially different from all the previous ones proposed in the literature. Specifically, we devise our encoding based on the _unrolled_ input size: given as input, for each \(i\)-th layer, a set of feature maps \(I_{i}\in\mathbb{R}^{h_{i}\times w_{i}\times c_{in}}\), we construct the corresponding bipartite graph as \(G_{i}=(L_{i}\cup R_{i},E_{i})\), where again \(L_{i}\) and \(R_{i}\) are the two layers of the bipartite graph, and \(L_{i}\) corresponds to the flattened representation of the inputs. The size of the layer \(R_{i}\), i.e., the output feature map, is calculated based on the input size \(I_{i}\) and the layer parameters \(W_{i}\in\mathbb{R}^{c_{out}\times c_{in}\times h_{in}\times w_{in}}\):

\[|L_{i}|=h_{i}\times w_{i}\times c_{in}\hskip 28.452756pt|R_{i}|=\left(\frac{h_{ i}-h_{\textit{ker}}}{S}+1\right)\times\left(\frac{w_{i}-w_{\textit{ker}}}{S}+1 \right)\times c_{out}. \tag{1}\]

Differently from the linear layer case, the set of edges \(E\) cannot be directly computed from the convolutional mask \(M_{i}\in\{0,1\}^{c_{out}\times c_{in}\times h_{in}\times w_{in}}\) since the latter is dynamically computed over the input data:1:

Footnote 1: The formula uses cross-correlation.

\[x_{i,j}^{out}=\sum_{u=0}^{c_{in}-1}\sum_{u=-h_{u}}^{h_{\textit{ker}}}\sum_{v=- u_{\textit{ker}}}^{w_{\textit{ker}}}I_{u,v}^{in}\times M_{i+u,j+v}^{out,in} \hskip 14.226378pt\forall\ out\in[0,c_{\textit{out}}). \tag{2}\]

From Eq. (1), we know that \(I_{u,v}^{in}\) and \(x_{i,j}^{out}\) respectively correspond to a node \(a_{(u+v)\times in}\in L_{i}\) and a node \(b_{(i+j)\times out}\in R_{i}\), so in this case the edges of the bipartite graph are constructed during the convolutional operation such that:

\[E_{i}=\{(a_{(u+v)\times in},b_{(i+j)\times out})\mid M_{i+u,j+v}^{out,in}\neq 0 \hskip 5.690551pt\forall\ out,in,u,v\} \tag{3}\]

where the ranges of \(out,in,u,v\) are defined according to Eq. (1), and \(in\) and \(out\) are respectively the IDs of the input and the output channel taken into consideration for that convolutional step2, and \(i+u,j+v\) correspond to one kernel entry. Intuitively, given a layer \(l^{i}\), each input element (e.g., in computer vision tasks, each pixel) represents a node in the graph, and the connection between an element of the input (denoted as \(a\)) and an element of the output feature map (denoted as \(b\)) is present if and only if during the convolutional operation, the contribution of \(a\) for generating \(b\) is not set to zero by the mask \(M_{i}\) in the kernel cell used to convolute the two pixels. An illustration of such encoding, which highlights the construction of the graph throughout the convolutional steps for both dense and sparse networks, is shown in Figure 1.

Footnote 2: In case of depth-wise separable convolution [23], the steps are only computed if \(in=out\).

### Multipartite Graph Encoding (MGE)

The bipartite GE described above has been devised to encode, independently, each single layer (either convolutional or linear) in a network. However, the limitation of this BGE lies in the lack of connections between consecutive (and, indirectly, non-consecutive) layers. As mentioned earlier, this limitation is however common to all the other GEs proposed in the literature [4; 47; 36; 13], that analyze the layers one by one, without connecting consecutive layers \(l_{i}\) and \(l_{i+1}\). On the other hand, differently from the existing encodings, our bipartite GE can be straightforwardly extended into a multipartite GE, in order to encode the whole network as an _unweighted directed acyclic multipartite graph_\(G=(G_{1},\ldots,G_{N})\), where each pair of consecutive graphs \(G_{i}\) and \(G_{i+1}\) is linked such that \(R_{G_{i}}=L_{G_{i+1}}\)3. The set of edges for each partition \(G_{i}\) is computed as described in Section 3.1. However, an extension of the previous encoding is needed for connecting consecutive layers when a pooling operation is employed between them, as explained in Appendix C.

Footnote 3: The graph representation of residual connections is not taken into consideration since the number of parameters is much smaller compared to classical convolutional layers.

### Topological Metrics

The unrolled GE proposed allows us to study the SNNs from a topological perspective, including a first theoretical analysis of the network connectivity between consecutive layers. We compute a number of _topological metrics_ (in the following, referred to for brevity as _topometrics_) over SNN topologies. These topometrics can be broken down into three categories: two structural (that we call **local** and **regional** graph metrics), and one related to the **stability** of pruning.
The **local** graph metrics are those computable over individual nodes or edges. These metrics (1) are computationally inexpensive, and (2) are able to capture some features of the graph connectivity between consecutive layers. Node-based topometrics include the fraction of _sink_, _source_, and _disconnected nodes_ over the MGE. The sink and source4 nodes are, respectively, those with outdegree and indegree of zero. The disconnected nodes are those with neither incoming nor outgoing connections. Considering the sink and source nodes, it is possible to compute the fraction of _removable connections_, which are edge-based topometrics. The out-connections of the set of source nodes (denoted here \(\alpha\)) are \(\text{r-out}=\frac{1}{|E|}\cdot\sum_{n\in\alpha}\text{outdegree}(n)\). The in-connections of the set of sink nodes (denoted here \(\beta\)) are \(\text{r-in}=\frac{1}{|E|}\cdot\sum_{n\in\beta}\text{indegree}(n)\). In fact, both these types of connections are useless for the final SNN performance, since they are ignored at inference.

Footnote 4: Padding nodes are already removed from the source set, since they have zero in-connections by design.

The **regional** metrics are calculated over linked subgraphs in the MGE, such as \(G=(G_{i},G_{i+1})\) (hence any pair of consecutive BGEs, i.e., each tripartite slice). They (1) are more expensive computationally, but (2) can better analyze the connectivity of the networks. These topometrics are: the number of _motifs_ (of size \(3\)), the number of _connected components_ (also known as clusters) and the _edge connectivity_ (i.e., the number of "bridges" or edges to cut in order to disconnect the graph). Each topometric has been normalized based on the number of edges present in the graph representation--to prevent the graph size from being a confounding variable for the topological study conducted in Section 4.

The **stability** metrics are calculated in order to gain insights about how relevant (and stable) the graph edges are for a given task. These metrics, which we call \(SJ\) (Stability-Jaccard) and \(SO\) (Stability-Overlap), can be computed between any two graph representations of SNNs in two settings: 1) an _init_ setting, where the pruning algorithm, sparsity ratio, and dataset are fixed, while the initialization seed is changed, and 2) a _data_ setting, where the pruning algorithm, sparsity ratio, and initialization seed are fixed, while the input dataset is changed. These two metrics are computed over the graph edges respectively using the Jaccard distance (Intersection over Union) and the overlap coefficient (Szymkiewicz-Simpson):

\[SJ=\frac{\sum_{i=0}^{N}\frac{|E_{i}^{1}\cap E_{i}^{2}|}{|E_{i}^{1}\cup E_{i}^{ 2}|}\times e_{i}}{\sum_{i=0}^{N}e_{i}}\qquad SO=\frac{\sum_{i=0}^{N}\frac{|E_{ i}^{1}\cap E_{i}^{2}|}{\min(|E_{i}^{1}|,|E_{i}^{2}|)}\times e_{i}}{\sum_{i=0}^{N}e_{i}} \tag{4}\]

where \(e_{i}=\frac{|E_{i}^{1}|+|E_{i}^{2}|}{2}\). A value of either \(SO\) or \(SJ\) close to \(1\) has a different meaning per setting. In the _init_ setting, it means that the pruning algorithm finds a topological structure which is not related to the values of the initialized weights. On the other hand, for the _data_ setting a value close to \(1\) means that the algorithm finds the exact same topological structure independently from the input dataset.

Figure 1: Illustration of the proposed unrolled input-aware BGE with \(I=3\times 3\times 3\) and convolutional parameters \((c_{\textit{out}}=2,c_{\textit{in}}=3,w_{\textit{ker}}=2,h_{\textit{ker}}=2,P= 0,S=1)\). (a) and (b) show, respectively, the first and second convolutional steps and how the graph edges are generated assuming that all the kernel parameters are unmasked. (c) shows the complete graph representation before pruning the kernel parameters. (d) shows the final graph representation after pruning the kernel parameters.
Experiments

In this section, we show how our proposed _input-aware unrolled GE_ provides meaningful topometrics from graph representations of SNNs. We then use the topometrics for two purposes: 1) to classify both pruning algorithms and their categories, and 2) to develop a regression analysis to capture which topometrics can predict the accuracy drop of SNNs for different sparsity ratios. The first setting allows us to understand what makes SNNs produced by Pals, DSTs and Layer-wise Random Pruning algorithms topologically different. The second setting allows us to understand how a certain sparse topology affects the architecture performance (from now on, we use "architecture" to refer to each CNN considered in our experimentation) and what may make some pruning algorithms perform better than others. It is worth mentioning that such analyses are based only on the unweighted graph representation of SNNs, hence do not take into consideration the weight values which could be highly dependent on the hyperparameters used in the training processes.

**Experimental Setup.** We generated a large pool of SNNs for our purposes. We use eleven different pruning algorithms: four Pruning at Initialization methods (Table 2), four Dynamic Sparse Training algorithms (Table 4), and three instances of Layer-wise Random Pruning (Table 3).

Since the graph size of the proposed GE is based on the size of the input data, we selected three datasets with the same data sizes, namely CIFAR-10, CIFAR-100 [28], and the downscaled Tiny-ImageNet (of size \(32\times 32\) pixels) [11]. We then used four different architectures designed for such input size, namely Conv-6 [26], Resnet-20 [22], Wide-Resnet-28-2 [53], and MobileNet-V2 [38]. We considered five sparsity values to cover a broad spectrum, namely \(s\in[0.6,0.8,0.9,0.95,0.98]\) (as in [13]). We trained each combination of \(\langle\)pruning algorithm, dataset, architecture,sparsity\(\rangle\) for \(3\) runs, obtaining a pool of \(1,980\) sparse architectures. More information on architectures, datasets, and hyperparameters is in Appendix A; the numerical results in terms of training accuracy (which correctly reproduce those reported in the literature) are in Appendix B.

The topometrics taken into consideration in the following experiments are the ones described in Section 3.3, namely: 1) _local_ metrics, which consist of graph properties over nodes such as the fraction of source, sink, and disconnected nodes, plus metrics over edges, such as the fraction of removable connections (both in and out); 2) _regional_ metrics, which consist of the number of motifs of size \(3\) over our directed acyclic multipartite graphs, the edge-connectivity (i.e., the percentage of bridge connections), and the number of clusters; 3) _stability_ metrics, which are the \(SJ\) and \(SO\) metrics both for the _init_ and the _data_ settings; d) _combination_, which considers all these metrics together. For the classification and regression analysis, we use XGBoost [9].

### Topological Classification

The first step in order to understand if different pruning algorithms provide either similar or diverse topologies is checking if the graph representation can be correctly classified based on its topological features. This analysis has been conducted for classifying both pruning algorithms and their categories (PaI, DST, Linear-wise Random Pruning). To do that, we average the topological properties of the SNNs obtained over different runs for the same combination \(\langle\)architecture, sparsity, dataset\(\rangle\), in order to avoid overfitting, then we remove the duplicate entries. For each type of topometrics, we tested the classification accuracy over two different data subsets: 1) **Sparsity-wise**, i.e., we conduct the classification separately for each sparsity ratio, and 2) **Architecture-wise**, i.e., we conduct the classification separately

\begin{table}
\begin{tabular}{l c c c} \hline \hline
**Algorithm** & **Drop** & **Growth** & **Redistribution** & **Sparse Init.** \\ \hline \hline DSR [34] & \(|\theta|\) & random & random (zero layers) & Uniform \\ SNFS [45] & \(|\theta|\) & momentum & momentum & Uniform \\ RigL [14] & \(|\theta|\) & gradient & ✗ & ERK \\ SET-ITOP [32] & \(|\theta|\) & random & ✗ & ERK \\ \hline \hline \end{tabular}
\end{table}
Table 4: Dynamic Sparse Training Pruning Algorithms.

\begin{table}
\begin{tabular}{l c c c} \hline \hline
**Pruning Method** & **Drop** & **Sanity Check** & **Training Data** & **Iterative** \\ \hline SNIP [35] & \(|\nabla_{\theta}L(\theta)|\) & ✗ & ✓ & ✗ \\ GraSP[8] & \(-H\nabla\phi\,L(\theta)\) & ✗ & ✓ & ✗ \\ Synflow [44] & \(\frac{\partial\mathcal{R}}{\partial\theta}\theta,\mathcal{R}=1\top(\prod_{l=1} ^{l}|\theta^{l}|)1\) & ✗ & ✗ & ✓ \\ ProsPr [1] & \(|\nabla_{\theta_{e}}L(\theta_{e})|\) & ✗ & ✓ & ✓ \\ \hline \hline \end{tabular}
\end{table}
Table 2: Pruning at Initialization Algorithms.

\begin{table}
\begin{tabular}{l c c c} \hline \hline
**Algorithm** & **Layer-wise Sparsity** & **\(s^{t}\ \lor\ l\in[0,N)\)** \\ ER [12] & \(1-\frac{n^{t-1}+n^{t}}{n^{t-1}\times n^{t}}\) \\ ERK [14] & \(1-\frac{n^{t-1}+n^{t}+n^{t}+h^{t}}{n^{t-1}\times n^{t}\times w^{t}\times h^{t}}\) \\ \hline \hline \end{tabular}
\end{table}
Table 3: Random Pruning Algs.
for each architecture. We also consider the case where all data are taken together (this case is referred to as "General"). We report the results in Table 5.

The results prove how different pruning algorithm categories generate SNNs with _different topological features_, which can be effectively classified with an average cross-validation balanced accuracy \(\sim 0.9\). It is also clear that the network topologies become more _separable_ (i.e., the classification accuracy increases) with increasing sparsity ratio. For the classification of the pruning algorithms, the accuracy is computed over \(11\) classes, which means fewer samples per class available for training (compared to the classification by algorithm categories). However, on average, it is still possible to reach an accuracy \(\sim 0.7\). For both Sparsity-wise and Architecture-wise classification, the best results are achieved when all the topometrics are used all at once. In Appendix D, we report the feature importance scores for both the classification tasks in the "General" case.

### Performance Prediction

The previous analysis showed that, from a classification perspective, different pruning algorithms (and categories thereof) generate network topologies with topological features. However, this analysis does not reveal how those features are associated with the **performance drop** of SNNs. It is already known that: 1) the performance drop is not always proportional to sparsity ratio, and 2) the performance of SNNs for some (sparsity, architecture, dataset) combinations could be even better than that of their dense counterparts [26; 25; 39]. Aiming at discovering associations between the topometrics and the performance drop, we conduct the following analysis. Starting from our pool of SNNs, we train a regression model and analyze its coefficient of determination \(R^{2}\) (which is computed as \(1-\frac{\sum_{i}(y_{i}-\hat{y_{i}})^{2}}{\sum_{i}(y_{i}-\hat{y})^{2}}\)), which has been proved to be the most informative measure for discovering associations between input features and predicted variables [10]. For the regression, we use as inputs the same topometrics introduced before, and compute the performance drop as \(1-\frac{accuracy_{k}}{accuracy_{d}}\), where \(s\) and \(d\) respectively correspond to the sparse and deep version of any given architecture. We conduct this analysis separately for each dataset. This has been done due to the fact that the performance drop is highly related to the over-parametrization relation between the dataset and the architecture.

Then, for each dataset, we study the association between the topometrics and the performance drop for both the Sparsity-wise and Architecture-wise cases. These two analyses allow us to investigate from a topological perspective: 1) what makes certain SNNs, given the same fraction of parameters w.r.t. the dense version, perform better than others, and 2) what topological properties, for a given architecture, make its sparse version perform worse.

The \(R^{2}\) coefficient values obtained using the _combination of all the proposed topometrics_ are shown in Table 6. The results for each single category of topometrics (_local_, _regional_ and _stability_) are available in Appendix D.2. Also for this study, the results reported are based on stratified cross-validation over \(100\) runs. To further assess the validity of our results, we also conducted an _ablation_ study. For the Sparsity-wise case, we calculated the \(R^{2}\) coefficient between architectures and corresponding performance drops separately for each value of sparsity ratio. For the Architecture-wise case, we calculated the \(R^{2}\) coefficient between sparsity ratios and performance drops separately for each architecture. It can be clearly noticed that our topological approach reaches a \(R^{2}\) coefficient much higher than that of the ablation studies, meaning that the proposed topometrics: 1) have a much higher predictive power than sparsity ratio and architecture alone, and 2) particularly for the Architecture-wise case, they add valuable information that is not captured when considering only the sparsity.

In addition, we analyzed the feature importance scores (using permutation importance) obtained during the regression analysis to find the most discriminative topometrics. Figure 2 (top-row) shows the feature importance for the Sparsity-wise case. The results have been averaged over \(100\) runs and then averaged over the three datasets (the results for each dataset are reported in Appendix D.2). For the Sparsity-wise case, the feature importance follows a clear pattern when increasing the sparsity ratio. Overall, the most discriminative feature turns out to be the number of motifs, i.e.,

\begin{table}
\begin{tabular}{l l c c c c c c c c c c} \hline \hline \multirow{2}{*}{**Classes**} & \multirow{2}{*}{**Topometrics**} & \multicolumn{3}{c}{**Accuracy**} & \multicolumn{3}{c}{**Accuracy (Sparsity-wise)**} & \multicolumn{3}{c}{**Accuracy (Architecture-wise)**} \\ \cline{3-11}  & & **(General)** & 0.6 & 0.8 & 0.9 & 0.95 & 0.98 & Conv-6 & Resnet-20 & Wide-Resnet-28-2 & MobileNet-V2 \\ \hline \multirow{4}{*}{**Pruning**} & **Local** & 7.5\(\pm\)0.1 & 66\(\pm\)0.2 & 71\(\pm\)0.2 & 73\(\pm\)0.3 & 81\(\pm\)0.3 & 85\(\pm\)0.3 & 76\(\pm\)0.2 & 67\(\pm\)0.3 & 79\(\pm\)0.2 & 93\(\pm\)0.2 \\  & **Regional** & 8.3\(\pm\)0.2 & 74\(\pm\)0.3 & 85\(\pm\)0.3 & 86\(\pm\)0.3 & 88\(\pm\)0.3 & 91\(\pm\)0.2 & 87\(\pm\)0.2 & 73\(\pm\)0.3 & 84\(\pm\)0.3 & 93\(\pm\)0.2 \\ \cline{1-1}  & **Stability** & 76\(\pm\)0.1 & 79\(\pm\)0.3 & 83\(\pm\)0.3 & 76\(\pm\)0.4 & 80\(\pm\)0.3 & 79\(\pm\)0.4 & 76\(\pm\)0.3 & 74\(\pm\)0.3 & 74\(\pm\)0.3 & 72\(\pm\)0.3 & 77\(\pm\)0.4 \\ \cline{1-1}  & **Combination** & **.95\(\pm\)0.1** & **89\(\pm\)0.3** & **93\(\pm\)0.3** & **92\(\pm\)0.3** & **93\(\pm\)0.2** & **95\(\pm\)0.2** & **94\(\pm\)0.2** & **89\(\pm\)0.2** & **91\(\pm\)0.3** & **96\(\pm\)0.2** \\ \hline \multirow{4}{*}{**Pruning**} & **Local** & 39.0\(\pm\)0.1 & 31\(\pm\)0.2 & 39\(\pm\)0.2 & 40\(\pm\)0.3 & 40\(\pm\)0.3 & 50\(\pm\)0.4 & 36\(\pm\)0.3 & 33\(\pm\)0.3 & 34\(\pm\)0.3 & 64\(\pm\)0.3 \\ \cline{1-1}  & **Regional** & 49\(\pm\)0.2 & 57\(\pm\)0.4 & 57\(\pm\)0.4 & 53\(\pm\)0.3 & 55\(\pm\)0.4 & 58\(\pm\)0.4 & 60\(\pm\)0.4 & 44\(\pm\)0.3 & 52\(\pm\)0.4 & 60\(\pm\)0.4 \\ \cline{1-1}  & **Stability** & 57\(\pm\)0.2 & 67\(\pm\)0.3 & 70\(\pm\)0.3 & 61\(\pm\)0.4 & 63\(\pm\)0.3 & 60\(\pm\)0.4 & 58\(\pm\)0.3 & 55\(\pm\)0.3 & 55\(\pm\)0.3 & 58\(\pm\)0.3 \\ \cline{1-1}  & **Combination** & **.72\(\pm\)0.2** & **74\(\pm\)0.3** & **80\(\pm\)0.3** & **73\(\pm\)0.3** & **72\(\pm\)0.3** & **77\(\pm\)0.3** & **73\(\pm\)0.3** & **65\(\pm\)0.3** & **66\(\pm\)0.4** & **71\(\pm\)0.3** \\ \hline \hline \end{tabular}
\end{table}
Table 5: Cross-validation balanced accuracy, using stratified k-fold with \(k=5\), for both pruning algorithm and algorithm category classification. The values have been averaged over \(100\) runs.
the number of significant recurrent subgraphs of size \(3\) in the graph representation. Another clear trend regards the different categories of topometrics: as the sparsity ratio increases, the _local_ metrics start to be more discriminative, while the _regional_ and _stability_ ones follow the inverse trend. Different sparsity ratios remove a different portion of parameters (and the corresponding edges in the graph representation) and disconnect the networks in different ways: for this reason, the feature importance scores "evolve" with the sparsity ratios. For instance, the importance of _clusters_ and _removable connections_ increases when the networks are sparser, therefore such metrics start to be effective in the regression analysis.

The same analysis was done over the Architecture-wise case, see Figure 2 (bottom-row), where the results previously discussed have been confirmed yet again. Also in this case, the number of motifs is the most discriminative feature, followed by edge connectivity (no. of bridges). It is also interesting to analyze how in a smaller network such as Resnet-20 (whose number of parameters is \(\sim 0.1-0.2\%\) w.r.t. the other considered networks), the most discriminative feature turns out to be the number of removable connections. Overall, the metrics that are mostly associated with the performance drop are the ones related to network connectivity.

\begin{table}
\begin{tabular}{l l c c c c c c c c c} \hline \hline \multirow{2}{*}{**Dataset**} & \multirow{2}{*}{
\begin{tabular}{c} **Input** \\ **features** \\ \end{tabular} } & \multicolumn{4}{c}{\(\boldsymbol{R^{2}}\) **(Sparsity-wise)**} & \multicolumn{4}{c}{\(\boldsymbol{R^{2}}\) **(Architecture-wise)**} \\ \cline{3-11}  & & 0.6 & 0.8 & 0.9 & 0.95 & 0.98 & Conv-6 & Resnet-20 & Wide-Resnet-28-2 & MobileNet-V2 \\ \hline \multirow{2}{*}{**CIFAR-10**} & **Topometrics** & **73\(\pm\)0.04** & **76\(\pm\)0.07** & **81\(\pm\)0.05** & **80\(\pm\)0.09** & **77\(\pm\)0.07** & **89\(\pm\)0.03** & **92\(\pm\)0.02** & **89\(\pm\)0.05** \\  & **Architectures** & 02\(\pm\)0.02 & 03\(\pm\)0.02 & 11\(\pm\)0.06 & 15\(\pm\)0.07 & 49\(\pm\)0.07 & - & - & - & - & - \\  & **Sparsity ratios** & - & - & - & - & - & - & - & - & - \\ \hline \multirow{2}{*}{**CIFAR-100**} & **Topometrics** & **49\(\pm\)0.07** & **69\(\pm\)0.07** & **73\(\pm\)0.05** & **72\(\pm\)0.08** & **80\(\pm\)0.05** & **95\(\pm\)0.02** & **95\(\pm\)0.01** & **91\(\pm\)0.02** & **92\(\pm\)0.04** \\  & **Architectures** &.01\(\pm\)0.01 &.03\(\pm\)0.02 &.40\(\pm\)0.06 &.46\(\pm\)0.07 & 40\(\pm\)0.06 & - & - & - & - \\  & **Sparsity ratios** & - & - & - & - & - &.58\(\pm\)0.03 &.86\(\pm\)0.01 &.78\(\pm\)0.03 &.64\(\pm\)0.05 \\ \hline \multirow{2}{*}{**Tiny-ImageNet**} & **Topometrics** & **74\(\pm\)0.06** & **58\(\pm\)0.04** & **86\(\pm\)0.03** & **85\(\pm\)0.05** & **81\(\pm\)0.05** & **93\(\pm\)0.02** & **91\(\pm\)0.02** & **92\(\pm\)0.03** & **89\(\pm\)0.05** \\  & **Architectures** & 23\(\pm\)0.07 & 51\(\pm\)0.08 &.51\(\pm\)0.06 &.57\(\pm\)0.04 &.55\(\pm\)0.03 & - & - & - & - & - \\  & **Sparsity ratios** & - & - & - & - & - &.52\(\pm\)0.06 &.78\(\pm\)0.01 &.63\(\pm\)0.04 &.69\(\pm\)0.05 \\ \hline \hline \end{tabular}
\end{table}
Table 6: \(R^{2}\) computed using stratified k-fold with \(k=5\) over \(100\) runs.

Figure 2: Feature importance scores for the regression analysis in the **Sparsity-wise (top row)** and **Architecture-wise (bottom row)** case. Colors highlight the contribution of different sets of metrics: _local_ (red), _regional_ (green), _stability_ (blue).
Conclusions

In this paper, we presented an in-depth analysis of the topologies of SNNs and their association with the performance drop. To do that, we studied the SNNs from a graph theory perspective, relying on a novel _unrolled input-aware_ graph encoding which correctly reflects the convolutional steps and links across layers. The main limitation of our proposed GE is the time and space complexity for the encoding creation: for each layer of the MGE, i.e., for each BGE, the time complexity is \(\mathcal{O}(c_{\textit{in}}\times c_{\textit{out}}\times step)\), while the space complexity is \(\mathcal{O}(L+R+E)\), where \(step=(\frac{l_{\textit{in}}-d_{\textit{in}}}{S}+1)^{2}\) and \(|E|=c_{\textit{in}}\times|W\setminus\{0\}|\times step\), assuming square feature maps and kernels.

On the other hand, we showed the practical applicability of our proposed GE through an analysis, both in terms of classification and prediction of the SNN performance based on topological metrics, of the most recent pruning algorithms from the literature.

Our findings are in line with the No-Free-Lunch-Theorem (NFLT) for pruning algorithms, i.e., _"No single method is SOTA at initialization. Depending on the network, dataset, and sparsity, there is a setting where each early pruning method reaches the highest accuracy."_[25]. We in fact proved how, for the sake of accuracy prediction, the importance of most topometrics changes depending on the sparsity ratio and architecture. Even though association does not imply causation, our results suggest new hints to the NFLT, namely: 1) as we showed in our classification analysis, different pruning algorithms are designed differently, and, by construction, they generate SNNs with different topological features; 2) as shown in our performance prediction analysis, the topological features that are positively associated with the performance depend on the specific sparsity ratio and architecture, hence there is no guarantee that subnetworks found by any given pruning algorithm will perform well regardless of the sparsity ratio and architecture. Taken together, our analysis sheds therefore new light on the reason why the NFLT may hold true. However, while previous studies focused on the effects of the weights in SNNs, here we were able to investigate the properties and performance of the SNNs only looking at their topology, regardless of the weight values.
