Deep Neural Networks via Complex Network Theory: A Perspective

1 Introduction

Deep Neural Networks (DNNs) are learning algorithms loosely inspired by the human brain: they consist of layers of interconnected nodes called neurons that process an input to produce an output [Bishop, 1995; Schmidhuber, 2015; Goodfellow et al., 2016]. Such models perform remarkably on many tasks without requiring humans to engineer features manually, as each DNN layer delegates neurons to learning and representing specific features, the so-called hierarchical representation of the input [Singh et al., 2018]. However, the outstanding ability of DNNs to learn these representations is accompanied by the challenge of interpreting both what happens inside the neural networks and the mapping process between a representation (data) and its label (output) [Montavon et al., 2018; Ghorbani et al., 2019]. Since the onset of the modern era of machine learning, interpreting the learning mechanisms of neural networks has emerged as a primary area of research, as highlighted in seminal works such as Erhan et al., Karpathy, and Zeiler et al. [2009; 2015; 2014]. In this work, we seek to unify, understand and represent DNNs and their dynamics through the lens of graph models. Graph models works include, among the others, Graph-Based Models [Kipf and Welling, 2017], Layer-wise Relevance Propagation [Montavon et al., 2019], and Complex Network Theory [Boccaletti et al., 2006]. In particular, Complex Network Theory (CNT) is a branch of mathematics that represents complex systems, from city connectivity to networks of computers [Porta et al., 2006b], by modelling and then simulating their dynamics through graphs where nodes represent entities and vertices relationships [Crucitti et al., 2004; Porta et al., 2006a; Chavez et al., 2010]. CNT offers an intuitive method for conceptualising DNNs, where neurons are analogous to graph nodes and connections to weighted edges.

This paper characterises DNNs as graphs via CNT metrics: we develop and unify a set of metrics that describe a network's weights, neurons, and the hidden layers' behaviour: we uncover consistent trends across various architectures, initialisations, and objective tasks across range of network architectures, including Fully Connected (FC), AutoEncoders (AE), Convolutional (CNNs), and Recurrent Neural Networks (RNN). The visual representations of the CNT metrics provide insights into a DNN's decision process. In synthesis, our work formally connects and grounds the existing work in the field [Testolin et al., 2019; Scabini et al., 2022] by unifying and extending existing CNT metrics such as Link Weigths Dynamics, Nodes Strength and Layers Fluctuation [La Malfa et al., 2021] moving beyond a topological analysis to account for the effect of the input data. Section 2 surveys the literature of CNT applied to DNNs. In Section 3, we introduce our methodology, i.e., a unified framework to study DNNs via CNT metrics and how to compute the various metrics for different DNN architectures. Section 4 reports results for different architectures, activation functions, and shallow and deep networks. We conclude the article with some ideas for further development and future works in this raising area of research.

2 RelatedWorks

Testolin et al. [2019] first used CNT to interpret deep learning models on classification tasks. Their work leverages CNT to retrieve information from Deep Belief Networks, a generative model whose unsupervised learning phase differs from feed-forward neural networks. They conducted experiments on MNIST and discovered a tension between elicited and suppressed neurons when classifying digits and that suppression is correlated with the efficiency of a network on the classification task. Zambra et al. [2020] moved beyond neuron activations and studied DNNs connected components, or 'motifs' as connectivity patterns between neurons or layers. 'Motifs' shed light on how a DNN learns and generalises. They discovered that initialising a neural network weights is key to the emergence of such 'motifs' and connects to accurate learning. In their study, Petri et al. [2021] show the inherent trade-offs between the capacity of a DNN to learn, generalise and execute multiple tasks simultaneously. This finding underscores a critical challenge in developing versatile and efficient AI systems unveiled through the analysis of neural networks using topological representations, an approach akin to CNT that examines a network structure and connectivity. In continuity with Petri et al., Saxe et al. [2022] introduce the Gated Deep Linear Network model. Through this model, they reveal that the learning process in structured networks is a 'neural race' in which different components compete to learn and represent information. This process is biased towards forming structured representations of knowledge, which determine a DNN's ability to generalise, transfer knowledge and handle multiple tasks simultaneously. La Malfa et al. [2021] study the DNNs training dynamics through the lens of CNT. Their approach is local and global in that it studies single networks and populations of evenly initialised DNNs. They formalise metrics for weights, neurons and hidden layers, yet their measures do not account for the value of the input. Scabini et al. [2022] unveil the topological properties of a broad range of FCs and the benefits of randomweight initialisation. They introduce Bag-Of-Neurons, a technique designed to identify topological signatures to group similar neurons (i.e., those dedicated to solving a specific sub-problem of a task such as edge detection).

3 Methodology

First, we provide background notation to describe a DNN via CNT metrics [Testolin et al., 2019; La Malfa et al., 2021]: the reference architecture is an FC network that solves a classification task. We then introduce CNT metrics that account for the input data via sampling from the training distribution. Finally, we show how to compute these metrics for a broad range of neural network architectures, including CNNs and RNNs. We also briefly discuss how attention networks [Vaswani et al., 2017] can be studied as Complex Networks, though we do not cover Transformers as we believe, given their complex architecture, they constitute a separate work.

3.1 Background

DNNs as graphs have three main components: the input layer, which is the 'receptor' of the input data (e.g., pixels of an image, audio samples, textual data, etc.), the hidden layers, which are stacked layers of neurons that transform the input via affine transformation followed by non-linear function activations, and the output, e.g., the network's classification. Formally, we consider an FC network that solves a supervised classification task, i.e., the network learns an inputoutput mapping f : Rd -→ Rm that minimises a generic loss function L(f(x), y), between each input-output pair (x, y). An input x is a d-dimensional vector x ∈ Rd drawn from a distribution, while each corresponding output is either from a discrete set in case of classification, i.e., c ∈ C . |C| = m, or it is continuous in case of regression, i.e., y ∈ Rm. An FC architecture consists of L > 0 dense layers stacked together, each of a variable number of neurons: within each hidden layer ℓ, a neuron n[ℓ] i is connected through a weighted link to all the neurons of the successive layer ℓ + 1. The output z[ℓ] of a layer ℓ is the product of an affine transformation between a matrix of weights Ω[ℓ] , plus eventually a bias term β[ℓ] , namely z[ℓ] = z[ℓ-1]Ω[ℓ] + β[ℓ] , followed by a nonlinear activation function f [ℓ] (z[ℓ] ). For an FC network, Ω[ℓ] is a matrix of size N [ℓ] ×N [ℓ+1] and β[ℓ] is a vector of size N [ℓ+1] . We denote the input and output vectors as x = z[0] and y = z[L] , while Ω[ℓ] and β[ℓ] refer to the parameters of a neural network layer ℓ. The output of the neural network is defined as y = f [L] (z[L] ) = z[L-1]Ω[L] + β[L] . For a classification task, the output is a vector of real numbers y ∈ Rm, from which the argmax operator extracts the predicted class. We refer to the input-output relation of a neural network at layer ℓ as z[ℓ] = f(x, Ω[:ℓ] , β[:ℓ] ).

3.2 Complex Networks Metrics for DNNs

A DNN can be represented as a set of nodes (neurons) connected by weighted edges. This intuition is sufficient to describe a DNNs via CNT. Formally, a DNN is a directed bipartite graph G = ⟨N,E⟩, where each node n[ℓ] i ∈ N corresponds to a neuron in the ℓ-th hidden layer. The intensity of a connection is a real number ω[ℓ] i,j assigned to an edge (en[ℓ] i ,n[ℓ+1] j ∈ E) that connects two neurons.

Link Weights. The Link Weights provide insight into how weights and biases adapt during training. Standard measurements of such metrics are the weights mean and variance at each layer during training. For DNN at layer ℓ they are defined as:

Monitoring weights mean and variance throughout training provides insights into the learning process's effectiveness and stability. If the norm of the weights does not increase, it could indicate over-regularisation in the model. Conversely, excessively large weight values might lead to overfitting.

Nodes Strength. Formally, the strength s[ℓ] k of a neuron n[ℓ] k is the sum of the weights of the edges incident in n[ℓ] k . Since neural network graphs are directed, two components contribute to the Node Strength: the sum of the weights of outgoing edges s[ℓ] out,k , and the sum of the weights of in-going links s[ℓ] in,k .

Node strength reflects how strong a connection is for a specific feature. In literature, the Node Strength account for both in- and out-coming edges [La Malfa et al., 2021]; we will consider them separately.

Layers Fluctuation. Layers Fluctuation extends the idea of Nodes Fluctuation [Porta et al., 2006b] to measure the variability of metrics at the level of a network's hidden layers. CNT classically defines Nodes Disparity as Y [ℓ] = ∑N [ℓ] i=1 [ω[ℓ] i /s[ℓ] i ]2 . However, weights generally have positive and negative values that could cancel each other out. To address this issue, we propose a metric designed for DNNs that captures the strength fluctuations within each layer, reflecting the interactions among nodes at the same depth. The Layers Fluctuation is defined as:

where ˆ s[ℓ] is computed as the average value of Nodes Strength at layer ℓ, namely ˆ s[ℓ] = 1 N [ℓ] ∑mi=1 s[ℓ] i , beingN [ℓ] the number of nodes/neurons at layer ℓ. This metric identifies asymmetries and disparities in the network at the layer level rather than focusing on individual nodes. Unlike the standard Nodes Fluctuation, Layers Fluctuation characterises the dynamics of an entire layer and accounts for bottlenecks within the network architecture.

3.3 Data-dependent CNTMetrics

We now introduce and formalise CNT metrics that account for the value of the input data, namely the Neurons Strength and Neurons Activation. Specifically, the training data distribution informs the computation of Neurons Strength and Neurons Activation so that for two different datasets, the results would vary accordingly (while it is not the case for the previous metrics). We then discuss how to compute all the above CNT metrics, including Nodes Strength and Layer Fluctuation to CNNs and RNNs.

Neurons Strength. The mathematical formulation of Neurons Strength for a neuron n[ℓ] k in layer ℓ is given by:

Here, ζ [ℓ] k represents the strength of neuron k in layer ℓ, considering the effects of both the activation functions of previous layers and the input values drawn from a distribution X. This approach provides a more comprehensive understanding of the neuron's role and influence within the network, factoring in the data being processed.

Neurons Activation. In Deep Neural Networks (DNNs), each neuron's activation level is determined by both the input values and the specific activation functions used in the network. The activation of a neuron in layer ℓ can be mathematically expressed as:

This equation highlights how the activation value a[ℓ] k of a neuron depends on the weighted sum of activations from the previous layer, adjusted by the neuron's weights and bias, and then transformed by the activation function f [ℓ] . A neuron exhibiting an unusually high Node Strength transmits a stronger signal than others. In such a scenario, an input does not elicit all the neurons uniformly, i.e., a neuron conveys more significant information for the classification task. Conversely, a neuron that transmits a weak signal might be a candidate for pruning, which can help reduce the overall complexity of the network without significantly impacting the layer's output.

3.4 CNTMetrics: Beyond Fully Connected Layers

The role of architectural inductive biases in enhancing the performance of deep learning models is well-established and supported by decades of extensive research. These biases, integrated into a model architecture, have significantly influenced the field of artificial intelligence. For instance, CNNs were designed with biases towards local connectivity, inspired by the human visual system [Lecun and Bengio, 1995]. Similarly, the development of recurrent networks, particularly the introduction of gates and memory cells in Long ShortTermMemory (LSTM) networks [Hochreiter and Schmidhuber, 1997], exemplifies how these biases enable the retention and accessibility of information over extended time steps. In this section, we adapt CNT metrics to CNN and RNN architectures, thus moving beyond the model of reference in most works on CNT applied to DNNs. We also discuss selfattention, the building block of Transformers [Vaswani et al., 2017], and how its architecture can be reconciled with one amenable to be studied with CNT. However, we leave the formalisation and the experiments for Transformers as future work.

Convolutional Neural Networks. Convolution is the building block operator in CNNs. An input matrix of size w × h (e..g, an image represented as a grid of pixels) is split into (possibly overlapping) patches of size k×k. A point-wise multiplication between each patch and the kernel, which has the same size as each patch, shrinks the input and produces an output that is then activated and fed to the next DNN's layer. In mathematical terms, for an input matrix zℓ of dimensions w×h and a kernel Ω of size m×m (with m ≤ w and m ≤ h), the convolution operation can be represented as z′ = z ∗ Ω. We now report the formula to compute the Neurons Strength for a CNN layer to highlight the differences with the Fully Connected case. For the Neurons Activation, the operations are analogous.

In the previous equation, z[ℓ-1] k ∗ Ω[ℓ] represents the convolution between the input patch z[ℓ-1] k and the entire kernel of weights at layer ℓ. One straightforward method to apply CNT metrics to this convolution operation is to transform the convolution into a dot product operation using a Toeplitz matrix. However, while this method is conceptually simple, it significantly increases both the time and space complexity from linear to quadratic, and it is thus expensive for large networks. Our approach, therefore, is to tackle this challenge efficiently. We isolate each input portion that is element-wise multiplied by the kernel. By linking each input neuron to its corresponding output neuron (as illustrated in Figure 1, left), we can efficiently compute the CNT metrics for any layer. This method allows to apply complex network analysis to convolution operations without the prohibitive computational cost of the Toeplitz matrix approach.

Recurrent Neural Networks. RNNs are designed to process sequential input, where the output of the previous step influences the output at each step in the sequence. Recursion makes RNNs ideal for tasks involving temporal data, like speech recognition or language modelling. The output of a single-layer recurrent RNN for the t > 0 temporal dimension of x is the following:

In the previous equation, where the bias term is omitted for clarity, U represents a matrix of trainable parameters used to process the hidden unit h(t) . Usually the value of h(1) is initialised to zero. To adapt CNT metrics for RNNs, we 'unfold' each input feature along its temporal dimension and treat each recurrent step as a layer-wise multiplication in an FC topology. This transformation is computationally less efficient than relying on symbolic loops, yet it is necessary to compute the CNT metrics for each input feature. The closed form formula to compute the Neurons Activation for an RNN Cell with one hidden layer, at time t > 0, and with parameters Ω and U (as sketched in Figure 1, right) is the following:

In the previous equation, the value of the Neuron Strength is computed by first sampling an input x from the input data distribution X, then by recursively unrolling the RNN and processing each temporal feature x(j) to compute the value of the hidden unit h(j) at times j < t. In the experiments, we show how the Neuron Strength can enhance a model's interpretability of which input features elicit the most neurons in an RNN recursive layer.

Self-attention. We conclude the section with a concise discussion of how self-attention can be expressed in a form amenable to study with CNT metrics. Self-attention (the building block of Transformers) is mathematically expressed as z = softmax(⟨xW K , xW Q⟩)xW V , where ⟨xW K , xW Q⟩ is the dot-product between a key and a query. 1 Being the keyquery a dot-product between two tensors, it can be expressed as an operation between nodes in a Complex Network and thus studied via CNT. The same argument is valid for multiplying the attention scores with xW V . We leave the formalisation of Transformers, the building block of modern Large Language Models, and the experiments to interpret their internal to future works.

4 Experiments

In this section, we conduct experiments to assess to which extent CNT identifies patterns in DNNs: we define three complementary levels of analysis. The first level (I) aims to distinguish dominating CNT patterns for architecturally similar networks: we train on MNIST and CIFAR10 three-layer depth FCs, CNNs, RNNs and AEs equipped with the same activation functions and a comparable number of parameters. While we test FCs, CNNs, and RNNs on image classification, AEs are trained to compress and reconstruct the input. As we keep the architectures as simple as possible, MNIST results in a relatively simple task where all the models perform well, while on CIFAR10, CNNs have better performances aided by their inductive bias towards image classification. The second level (II) studies the incidence of different activation functions (i.e., linear, ReLU, sigmoid) on CNT metrics for FCs, CNNs, RNNs and AEs. Similarly to the previous setting, the networks are architecturally similar in terms of hidden layers and number of trainable parameters, yet differ in their activation functions. The third level of analysis (III) explores the impact of depth (i.e., the number of hidden layers) on CNT metrics. Deeper neural networks learn more complex features from data and positively correlate with a DNN's performance on the task. Also, deeper layers can learn increasingly abstract representations of the data. In image processing, initial layers might detect edges and textures, while deeper layers might identify more complex patterns or objects. We investigate and report the impact of depth by varying the number of hidden layers of FCs and AEs from three to seven (while further analyses are reported in the code repository).

1 The normalisation factor inside the softmax can be, without loss of generality ignored.

We conduct all the experiments on two standard datasets in pattern recognition and computer vision, namely MNIST and CIFAR10 [Lecun and Bengio, 1995; Krizhevsky et al., 2010]. While relatively simple, these two benchmarks set a baseline for future analyses on more complex tasks; we stress that our framework can be applied to any dataset a DNN can tackle. Generally, we compute all the CNT metrics on a 30 trained neural network pool. We initialise the weights of each DNN via sampling from a Gaussian distribution of known variance between 0.05 (MNIST) and 0.5 (CIFAR10). 2

I. CNT Metrics of different architectures. MNIST images consist of white-scaled digits on a dark background. As reported in the literature, FC networks tend to present 'dead units', i.e. an abundance of negative or close to zero weights, a hint of an over-parametrised network [Testolin et al., 2019]. Our results confirm this trend for FCs and extend it to all the other architectures (CNNs, RNNs and AEs), as we show in Figure 2; yet, for AEs, the phenomenon is more remarked, with a probability distribution of Neurons Strength and Activation peaked respectively around negative values and at the extremes of the distribution. We further notice that AEs compress information by design, i.e., a 'bottleneck', as shown in the third layer of Figure 2. On the other hand, CNNs' Nodes Strength and Neurons Strength are multimodal, with spikes corresponding to the patterns a network learns to perform local edge detection. We hypothesise that CNNs specialise neurons within the same layer to activate them for different input values. For example, the spikes may represent the information relative to the number of edges in a digit, as that is one of the sub-tasks that requires more information to be encoded. Globally, the influence of positive and negative weights in FC, AEs and RNNs seems balanced, while CNNs exhibit a profusion of negative weights. This suggests that, during the training phase, CNNs may prioritise different input features than FCs, RNNs and AEs. RNNs' Neuron Strength distribution exhibits a pronounced Kurtosis, a feature that isn't observed when analysing Node Input Strength alone and is thus imputable to the data distribution. Additionally, the Neuron Activation displays a unique pattern: unlike other architectures, the density is distributed not just at the extremes of the sigmoid function, but also significantly in the middle (between 0.4 and 0.6), a sign that recurrent architectures are less likely to settle at the extremes, resulting in more varied activation patterns. Regarding interpretability, we further investigate the dynamics of the Neurons Strength in an RNNs' autoregressive loop. This approach involves an RNN sequentially processing a segment of the input, updating its hidden states, and ultimately classifying the image. In Figures 3, we compare the Neurons Strength of trained and untrained RNNs on the MNIST and CIFAR10 datasets. In both cases, the Neurons Strength of trained RNNs localises a specific image region that elicits the neurons the most, while that doesn't occur for untrained networks. This suggests that the training phase calibrates a model to activate mostly on specific patterns located in the central part of the input. We compare our results with that of Layer-Wise Relevance Propagation (LRP) [Bach et al., 2015] on a sample of inputs of the same class as those in Figure 3 (top), a standard interpretability framework that identifies the most activated neurons at inference time and maps them to specific pixels in the input region. We report the interpretability heatmaps for different LRP implementations in Figure 6 on the MNIST dataset. Unlike CNT metrics, LRP is local (i.e., it allows determining the salient features of a single input point), works backwards (from the output to the input), and covers only neurons. Our techniques are global and local (they allow us to analyse single and multiple data points), work forward (neural networks are not invertible, which causes a loss of information in LRP), and extend to weights, neurons, and layers. Interestingly, LRP and CNT metrics identify different activation patterns in the input. For the MNIST dataset, LRP usually identifies the receptive field of the input numbers. At the same time, CNT discriminates based on the upper region of each image, a result that requires further investigation in future works.

2 Higher variance in the parameter initialisation can sometimes help the network to escape poor local minima early in training, which are more prevalent in datasets like CIFAR10.

II. Incidence of the activation function. Non-linear activation functions allow models to learn complex patterns in data. We compare the effects of linear, ReLU, and sigmoid activation functions for FCs, CNNs, RNNs and AEs on CIFAR10. Linear activations, lacking the ability to model non-convex optimisation landscapes, typically lead to Neurons Strength and Neurons Activation distributions centred around zero. In contrast, ReLU and sigmoid activations result in asymmetric distributions, favouring negative values, often correlating with enhanced accuracy. Notably, ReLU's inherent asymmetry results in distributions skewed more significantly towards extreme negative values than those observed with sigmoid, as we report in Figure 4 (first column). AEs with linear and ReLU activations show similar behaviours to FCs. However, models equipped with sigmoid exhibit Neuron Activation distributed evenly around its support. This phenomenon suggests the AEs correctly reconstruct the input data with dynamics that diverge from FCs, CNNs and RNNs, which solve a different task (classification). For linear models, CNNs' Neurons Activation centres around zero, with low variance compared to other architectures. Conversely, nonlinear activations skew the distribution of the metrics toward zero. Both ReLU- and sigmoid-activated networks leverage negatively activated neurons to discriminate between different classes. This phenomenon is remarkably different from what happens with FCs and RNNs where the Neurons Activation accumulates around the extreme values of the activation (zero and one), suggesting that the decision rules encoded internally by CNNs may diverge from that of other architectures.

III. Incidence of neural network depth. We conclude with an analysis of the effect of depth on the dynamics of CNT metrics on CIFAR10. We compare FCs and AEs with three and seven layers, respectively. While FCs perform classification, AEs are trained to reconstruct the input with minimal data loss. 3 In Figure 7, we report the Neurons Strength and Activation, which we further correlate with the Nodes Strength. Shallow FC architectures operate with similar dynamics as deeper networks, with the second and third layers of Figure 7 (top) that overlap with respectively the fourth and seventh of Figure 5 (top): in conclusion, deeper networks exhibit more complex patterns in their hidden layers, that shallow lack. For this task, deeper networks leverage the same 'building block' of shallow networks to build increasingly complex input representations and solve the task more accurately. Conversely, the dynamics of shallow and deep AEs diverge sensibly: seven-layer AEs seem not to leverage existing 'building blocks' of shallow architectures, suggesting that data compression is a dynamic process heavily influenced by the number of layers in a network. We also notice that the Nodes Strength does not correlate with the Neurons Strength or Activation, supporting the development of CNT metrics that incorporate the effect of data in their dynamics.

5 Conclusions and FutureWorks

This paper introduces a unified framework for representing neural networks via CNT, incorporating new metrics influenced by input data and enhancing traditional topological CNT analysis. Our extensive experiments on FCs, CNNs, RNNs, and AEs reveal distinct dynamics and training patterns across architectures, activation functions, and depths. our key findings include over-parametrisation in most architectures, especially with the MNIST task, and CNNs demonstrating localised learning through multimodal Nodes and Neurons Strength. Non-linear activations in models lead to asymmetric distributions, causing complex pattern learning. AEs' Neurons Activation distribution in deeper models suggests their learning dynamics do not leverage the same dynamics as shallow architectures. Unlike FCs and RNNs, CNNs with non-linear activations learn discriminative patterns for classification, mostly in negative regions of the activation function. In future works, we will extend this framework to advanced architectures, both theoretically and empirically. In particular, we believe that CNT can contribute to interpreting self-attention [Vaswani et al., 2017], an architecture that powers language and computer vision models. This work is also meant to encourage other researchers with expertise in both machine learning and physics to contribute to the formalisation of learning systems as graphs to unveil their training dynamics as the current state-of-the-art approaches do not study the evolution of untrained networks during the learning phase.

3 Results for the other architectures on MNIST and CIFAR10, for five and nine layers, are reported in the code repository.

Acknowledgments

G.L.M.'s work was supported by UK Research and Innovation [grant number EP/S023356/1], in the UKRI Centre for Doctoral Training in Safe and Trusted Artificial Intelligence (www.safeandtrustedai.org).

G.N. thanks the University of Cambridge for the extended research periods and the opportunity to be a Visiting Professor during the Sabbatical year. Moreover, G.N. thanks Wolfson College, the Department of Biochemistry, and the Cambridge Systems Biology Centre for the hospitality and warm welcome that allowed for peaceful studies, novel, interesting collaborations, and fruitful research activities.

V.L. acknowledges support from the European Union, NextGenerationEU, GRINS project (GRINS PE00000018 - CUP E63C22002120006).