Beyond Multilayer Perceptrons: Investigating Complex Topologies in
  Neural Networks
In this study, we explore the impact of network topology on the approximation
capabilities of artificial neural networks (ANNs), with a particular focus on
complex topologies. We propose a novel methodology for constructing complex
ANNs based on various topologies, including Barab\'asi-Albert,
Erd\H{o}s-R\'enyi, Watts-Strogatz, and multilayer perceptrons (MLPs). The
constructed networks are evaluated on synthetic datasets generated from
manifold learning generators, with varying levels of task difficulty and noise,
and on real-world datasets from the UCI suite. Our findings reveal that complex
topologies lead to superior performance in high-difficulty regimes compared to
traditional MLPs. This performance advantage is attributed to the ability of
complex networks to exploit the compositionality of the underlying target
function. However, this benefit comes at the cost of increased forward-pass
computation time and reduced robustness to graph damage. Additionally, we
investigate the relationship between various topological attributes and model
performance. Our analysis shows that no single attribute can account for the
observed performance differences, suggesting that the influence of network
topology on approximation capabilities may be more intricate than a simple
correlation with individual topological attributes. Our study sheds light on
the potential of complex topologies for enhancing the performance of ANNs and
provides a foundation for future research exploring the interplay between
multiple topological attributes and their impact on model performance.
Tommaso Boccato, Matteo Ferrante, Andrea Duggento, Nicola Toschi
# Beyond Multilayer Perceptrons: Investigating Complex Topologies in Neural Networks

###### Abstract

In this study, we explore the impact of network topology on the approximation capabilities of artificial neural networks (ANNs), with a particular focus on complex topologies. We propose a novel methodology for constructing complex ANNs based on various topologies, including Barabasi-Albert, Erdos-Renyi, Watts-Strogatz, and multilayer perceptrons (MLPs). The constructed networks are evaluated on synthetic datasets generated from manifold learning generators, with varying levels of task difficulty and noise.

Our findings reveal that complex topologies lead to superior performance in high-difficulty regimes compared to traditional MLPs. This performance advantage is attributed to the ability of complex networks to exploit the compositionality of the underlying target function. However, this benefit comes at the cost of increased forward-pass computation time and reduced robustness to graph damage.

Additionally, we investigate the relationship between various topological attributes and model performance. Our analysis shows that no single attribute can account for the observed performance differences, suggesting that the influence of network topology on approximation capabilities may be more intricate than a simple correlation with individual topological attributes.

Our study sheds light on the potential of complex topologies for enhancing the performance of ANNs and provides a foundation for future research exploring the interplay between multiple topological attributes and their impact on model performance.

## 1 Introduction

Modern neural architectures are widely believed to draw significant design inspiration from biological neuronal networks. The artificial neuron, the fundamental
functional unit of neural networks (NNs), is based on the McCulloch-Pitts unit [13], sharing conceptual similarities with its biological counterpart. Additionally, state-of-the-art convolutional NNs incorporate several operations directly inspired by the mammalian primary visual cortex, such as nonlinear transduction, divisive normalization, and maximum-based pooling of inputs. However, these architectures may be among the few examples where the evolutionary structural and functional properties of neuronal systems have been genuinely relevant for NN design. Indeed, the topology of biological connectomes has not yet been translated into deep learning model engineering.

Due to the ease of implementation and deployment, widely-used neural architectures predominantly feature a regular structure resembling a sequence of functional blocks (e.g., neuronal layers). The underlying multipartite graph of a multilayer perceptron (MLP) is typically controlled by a few hyperparameters that define its basic topological properties: depth, width, and layer sizes. Only recently have computer vision engineers transitioned from chain-like structures [32] to more elaborate connectivity patterns [16; 17] (e.g., skip connections, complete graphs). Nevertheless, biological neuronal networks display much richer and less templated wirings at both the micro- and macro-scale [14]. Considering synaptic connections between individual neurons, the _C. elegans_ nematode features a hierarchical modular [5] connectome, wherein hubs with high betweenness centrality are efficiently interconnected [4; 33]. Moreover, the strength distribution of the adult Drosophila central brain closely follows a power law with an exponential cutoff [29].

As a result, the relationship between the graph structure of a NN and its predictive abilities remains unclear. In the literature, there is evidence that complex networks can be advantageous in terms of predictive accuracy and parameter efficiency [18]. However, past attempts to investigate this connection have yielded conflicting results that are difficult to generalize outside the investigated context. The first experiment on complex NNs was performed in 2005 by Simard et al., who trained a randomly rewired MLP on random binary patterns [31]. Nearly a decade later, Erkaymaz and his collaborators employed the same experimental setup on various real-life problems [12; 11; 9; 10] (e.g., diabetes diagnosis, performance prediction of solar air collectors). The best-performing models featured a number of rewirings consistent with the small-world regime. However, all assessed topologies were constrained by MLP-random interpolation. In [2], an MLP and a NN generated following the Barabasi-Albert (BA) procedure were compared on a chemical process modeling problem. Both models were trained with an evolutionary algorithm, but the MLP achieved a lower RMSE. The _learning matrix_[24], a sequential algorithm for the forward/backward pass of arbitrary directed acyclic graphs (DAGs), enabled the evaluation of several well-known complex networks on classification [24] and regression [26] tasks. The experiments included random and small-world networks, two topologies based on "preferential attachment", a complete graph, and a _C. elegans_ sub-network [7]. Nevertheless, the learning matrix's time complexity limited the network sizes (i.e., 26 nodes), and for each task, a different winning topology emerged, including the MLP. Some recent works have instead focused on mul
tipartite sparse graphs [23, 35]. While these architectures outperformed the complete baselines, their topological complexity was entirely encoded within the connections between adjacent layers.

We propose the hypothesis that, given the same number of nodes (i.e., neurons) and edges (i.e., parameters), a complex NN might exhibit superior predictive abilities compared to classical, more regularly structured MLPs. Unlike previous studies, we conduct a systematic exploration of random, scale-free, and small-world graphs (Figure 1) on synthetic classification tasks, with particular emphasis on the following:

* **Network size.** The defining properties of a complex topology often emerge in large-scale networks. For example, the second moment of a power-law degree distribution diverges only in the \(N\rightarrow\infty\) limit [3], where \(N\) is the network size1. The networks in [24, 26] have 15 and 26 nodes, respectively. We trained models with 128 neurons. Footnote 1: The proposition holds when the degree exponent is smaller than 3.
* **Dataset size.** The _estimation error_ achieved by a predictor depends on the training set size: the greater the number of samples, the lower the error [30]. Except for studies based on multipartite graphs, all previous research works in a small-data regime. Our datasets are three times larger than those used before.
* **Hyperparameter optimization.** Learning rate and batch size are crucial in minimizing the loss function. Ref. [24] is the only one that considers finding the optimal learning rate. The role of batch size has never been investigated. Each DAG, however, could be characterized by its optimal combination of hyperparameters. Hence, we optimized the learning rate and batch size for each topology.

## 2 Theory

### Complex Graph Generators

**Erdos-Renyi (ER).** An ER graph [8], or _random network_, is uniformly sampled from the set of all graphs with \(N\) nodes and \(L\) edges. For \(N\gg\langle k\rangle\), the degree distribution of a random graph is well approximated by a Poisson distribution: \(p_{k}=e^{-\langle k\rangle}\frac{\langle k\rangle^{k}}{k!}\); \(k\) and \(\langle k\rangle\) represent node degree and average degree, respectively.

**Watts-Strogatz (WS).** The WS generator [34] aims to create graphs that exhibit both high clustering and the _small-world_ property; this is achieved by interpolating _lattices_ with random networks. The generation starts from a ring in which nodes are connected to their immediate neighbors. The links are then randomly rewired with probability \(p\).

**Barabasi-Albert (BA).** The well-known BA model [1] can be used to generate networks characterized by the \(p_{k}\propto k^{-3}\)_scale-free_ degree distribution. Being
the model inspired by the growth of real networks, the generative procedure iteratively attaches nodes with \(m\) stubs to a graph that evolves from an initial star of \(m+1\) nodes. Node additions respond to the preferential attachment mechanism: the probability that a stub reaches a node is proportional to the degree of the latter.

**Multilayer Perceptron (MLP).** The underlying networks of MLPs are called multipartite graphs. In a multipartite graph (i.e., a sequence of bipartite graphs) nodes are partitioned into layers, and each layer can only be connected with the adjacent ones; no intra-layer link is allowed. Additionally, inter-layer connections have to form _bicliques_ (i.e., fully-connected bipartite graphs).

## 3 Methods

### Datasets

The foundation of the datasets developed, as displayed in Figure 2, is established by manifold learning generators2 provided by the scikit-learn machine learning library [25]. To modify the generators for classification purposes, 3D points sampled from one of the available curves (_s curve_ and _swiss roll_) are segmented into n_classes\(\times\)n_reps portions based on their univariate position relative to the primary dimension of the manifold samples. As the term implies, n_classes refers to the number of classes involved in the considered classification. Each segment is then arbitrarily allocated to a class, maintaining task balance (i.e.,

Figure 1: Example feedforward NNs (128 neurons, 732 synaptic connections) based on complex topologies: scale-free (BA), random (ER), and small-world (WS). All graphs are directed and acyclic. Information flows from top to bottom. Input, hidden, and output units are denoted in blue, orange, and green, respectively. Since the networks are defined at the micro-scale, hidden and output nodes implement weighted sums over the incoming edges. In the hidden units, the computational operation is followed by an activation function. The activations of nodes located on the same horizontal layer can be computed in parallel.
precisely n_reps segments have the same label). We define n_reps as the task _difficulty_. An additional aspect of our datasets is the standard deviation \(\sigma\) of the Gaussian noise that can be added to the points. The generation procedure is finalized with a min-max normalization.

### Feedforward Neural Networks

All trainable models are produced following the same 3-step procedure and share \(N\) and \(L\). Consequently, NNs exhibit identical density and parameter counts.

**Undirected Graph Generation.** The initial step in creating a NN involves sampling an undirected graph using the generators detailed in Section 2. Once \(N\) and \(L\) are established, all models exhibit a single parameter configuration compatible with the required density3. The WS generator is the sole exception: the probability \(p\) is allowed to vary between 0 and 1. If the generator is limited to sample networks with a number of links from a finite set (e.g., \(L=m+(N-m-1)m\) according to the BA model), we first generate a graph with slightly higher density than the target before randomly eliminating excess edges. After obtaining the graph, we confirm the existence of a single connected component.

Footnote 3: This statement is accurate if the number of MLP layers is predetermined.

**Directed Acyclic Graph (DAG) Conversion.** Before performing any calculations, the direction for information propagation through the network links

Figure 2: Benchmark classification datasets. **Top**: the _swiss roll_. **Bottom**: the _s curve_. Each dataset is composed of 3D points divided into multiple segments. Classes are color-coded. Datasets differ in terms of difficulty (\(x\) axis) and noise (\(y\) axis).
must be determined; this is accomplished by randomly assigning, without replacement, an integer index from \(\{1,\ldots,N\}\) to the network nodes. It can be shown that the directed graph obtained by setting the direction of each edge from the node with a lower index to the node with a higher index is free of cycles. However, this conversion results in an unpredictable number of sources and sinks. Since classification tasks typically involve a pre-defined number of input features and output classes, it is necessary to resolve such network-task discrepancies. To address this issue, we developed a straightforward heuristic capable of adjusting DAGs without altering the underlying undirected graphs.

**Mapping of Functional Roles.** The last step of the presented procedure consists in mapping computational operations to the DAG nodes. Working at the micro-scale (i.e., connections between single neurons), the operations allowed are two. Source nodes implement constant functions; their role, indeed, is to feed the network with the initial conditions for computations. Hidden and sink nodes, instead, perform a weighted sum over the incoming edges, followed by an activation function:

\[a_{v}=\sigma\Bigg{(}\sum_{u}w_{uv}a_{u}+b\Bigg{)} \tag{1}\]

where \(a_{v}\) is the activation of node \(v\), \(\sigma\) denotes the activation function4 (SELU [20] for hidden nodes and the identity function for sinks), \(u\) represents the generic predecessor of \(v\), \(w_{uv}\) is the weight associated with edge \((u,v)\) and \(b\) the bias. In order to implement the map of functional roles, we made use of the 4Ward library5[6], developed for the purpose. Starting from a DAG, the package returns a working NN deployable as a PyTorch Module.

Footnote 4: Depending on the context, we use the same \(\sigma\) notation for both the standard deviation of the dataset noise and the activation function.

Footnote 5: [https://github.com/BoCtrl-C/forward](https://github.com/BoCtrl-C/forward)

### Experiments

**Dataset Partitioning.** Each generated dataset is randomly divided into 3 non-overlapping subsets: the train, validation and test splits. All model trainings are performed over the train split while the validation split is exploited in validation epochs and hyperparameter optimization. Test samples, instead, are accessed only in the evaluation of the final models.

**Model Training.** Models are trained by minimizing cross entropy with the Adam [19] optimizer (\(\beta_{1}=0.9\), \(\beta_{2}=0.999\)). A scheduler reduces the learning rate by a factor of 0.5 if no improvement is seen on the validation loss for 10 epochs. The training procedure ends when learning stagnates (w.r.t. the validation loss) for 15 epochs, and the model weights corresponding to the epoch in which the minimum validation loss has been achieved are saved.

**Hyperameter Optimization.** Hyperparameters are optimized through a grid search over a predefined 2D space (i.e., learning rate/batch size). We generate networks of the same topological family starting from 5 different random seeds.
In the MLP case, models differ only in the weight initialization. For each parameter pair, the 5 models are trained accordingly, and the resulting best validation losses are collected. Then, the learning rate and batch size that minimize the median validation loss computed across the generation seeds are selected as the optimal hyperparameters of the considered graph family.

**Topology Evaluation.** Once the optimal learning rate and batch size are found, we train 15 new models characterized by the considered topology and compute mean classification accuracy and standard deviation on the dataset test split. The procedure is repeated for each investigated graph family and a Kruskal-Wallis (H-test) [21] is performed in order to test the null hypothesis that the medians of all accuracy populations are equal. If the null hypothesis is rejected, a Mann-Whitney (U-test) [22] post hoc analysis follows.

**Robustness Analysis.** We use the final trained models in a _graph damage_ study to investigate their _functional_ robustness (accuracy vs. fraction of removed nodes). The _topological_ robustness (giant component vs. fraction of removed nodes) is already well-studied in network science. We randomly remove a fixed fraction of nodes, \(f\), from a neural network and compute the accuracy achieved by the resulting model on the test dataset. Practically, node removal is implemented using PyTorch's Dropout6, which zeroes some network activations by sampling from i.i.d. Bernoulli distributions. As each batch element is associated with specific random variables, activations produced by different dataset samples are processed by differently pruned neural networks. Therefore, the figure of interest is averaged over the dataset and the 15 generation seeds. In a typical topological analysis, when \(f=0\), the giant components of all tested graphs have the same size (i.e., \(N\)). We adopt this convention in our experimental setup by replacing test accuracy with _accuracy gain_: \(\mathcal{A}(f)\). The metric is defined as the ratio between the accuracy obtained by a pruned network and the accuracy obtained by the original one (i.e., \(f=0\)). An accuracy gain \(<1\) indicates a decline in model performance. Consequently, the figure of merit for our analysis is the mean accuracy gain, with the expectation taken over the generation seeds.

Footnote 6: [https://pytorch.org/docs/stable/generated/torch.nn.Dropout.html](https://pytorch.org/docs/stable/generated/torch.nn.Dropout.html)

## 4 Results

We obtained the presented results by following the experimental protocol outlined in Section 3 using the specified topologies (i.e., BA, ER, MLP, and WS) and datasets. We set n_classes = 3 and n_reps \(\in 3,6,9,12\); for the _swiss roll_ dataset, \(\sigma\in 0.0,1.0\), while for the _s curve_, \(\sigma\in 0.0,0.3\). The train, validation, and test split sizes were 1350, 675, and 675, respectively. Given that in a 1-hidden layer MLP (h1 notation) the number of synaptic connections depends solely on \(N\) (i.e., \(L=3\times H+H\times 3\), with \(H=N-3-3\)), we chose an MLP with 128 neurons as a reference model and calculated the hyperparameters for the complex networks to achieve graphs with \(L=732\) edges. The additional
degree of freedom in the WS generator enabled us to separate the small-world topology into three distinct graph families: p.5 (\(p=0.5\)), p.7 (\(p=0.7\)), and p.9 (\(p=0.9\)). The hyperparameter optimization searched for learning rates in {0.03, 0.01, 0.003, 0.001} and batch sizes in {32, 64}.

Figure 3 displays the mean test accuracy achieved by each group of models as a function of task difficulty. All manifolds, noise levels, and difficulties are represented. Excluding difficulty level 9 in the _swiss roll_ dataset, the accuracy curves exhibit a clear decreasing trend. Specifically, as the difficulty increases, the performance of the MLPs degrades more rapidly than that of complex networks. Confidence intervals, on the other hand, are wider in the high-difficulty plot regions. As expected, noisy tasks were more challenging to learn.

In Figure 4, the results obtained by the models for the two highest levels of task difficulty are shown in detail. The H-test null hypothesis is rejected for all experiments, and the U-test statistical annotations are displayed. Regardless of the scenario considered, a complex topology consistently holds the top spot in

Figure 3: Mean test accuracy as a function of the task difficulty. Confidence intervals (\(\pm\) standard deviation) are reported as well. Different subplots correspond to different datasets. Each curve denotes the trend of a specific network topology.
the mean accuracy ranking. MLPs, in contrast, are always the worst-performing models. Moreover, the MLP performance differs significantly from that of the complex networks, in a statistical sense. Conversely, only 3 out of 8 experiments exhibit statistical differences within the group of complex networks.

Figure 5 presents the results of the robustness analysis. We investigated \(f\in\{0.0,0.1,\ldots,0.5\}\) and removed nodes from the models trained on the datasets characterized by the lowest level of difficulty. On these tasks, indeed, all models behave approximately the same (see Figure 3), hinting at a fair comparison. Unsurprisingly, node removal has the same effect on all topologies: the accuracy gain decreases as \(f\) increases. MLPs, however, show enhanced robustness to random deletions. Confidence intervals of the complex graph families overlap. It is worth noting that the chance level (i.e., accuracy of \(1/3\)) could be reached by different accuracy gains depending on the task; the best accuracy under \(f=0\), indeed, varies between the manifold/noise pairs.

## 5 Discussion

The most significant finding from the experiments performed is the performance in terms of accuracy attained by the architectures built on complex topologies in the high-difficulty regime. In this context, and in light of the statistical tests

Figure 4: Mean test accuracy at the highest difficulty levels. **Left**: difficulty \(=9\). **Right**: difficulty \(=12\). The bars display both means and standard deviations. Each bar corresponds to a specific network topology and is represented by a consistent color across all histograms (following the color scheme from Figure 3). Statistical annotations appear above the histograms, with each segment indicating a significant difference between two accuracy distributions.
Figure 5: Robustness analysis. The horizontal axis reports the fraction of removed nodes (i.e., \(f\)) while the vertical one the accuracy gain (i.e., \(\mathcal{A}(f)\)). Each curve refers to a different network topology. Confidence intervals (\(\pm\) standard deviation) are reported.
carried out, the complex models prove to be a solid alternative to MLPs.

Formally justifying the observed phenomenon is challenging. Fortunately, in 2017, Poggio et al. discussed two theorems [28] that guided our explanation. According to the first theorem7, a shallow network (e.g., an MLP h1) equipped with infinitely differentiable activation functions requires \(N=\mathcal{O}(\epsilon^{-n})\) units to approximate a continuous function \(f\) of \(n\) variables8 with an approximation error of at most \(\epsilon>0\). This exponential dependency is technically called the _curse of dimensionality_. On the other hand, the second theorem states that if \(f\) is compositional and the network presents its same architecture, we can escape the "curse". It is important to remember that a compositional function is defined as a composition of "local" constituent functions, \(h\in\mathcal{H}\) (e.g., \(f(x_{1},x_{2},x_{3})=h_{2}(h_{1}(x_{1},x_{2}),x_{3})\), where \(x_{1},\ x_{2},\ x_{3}\) are the input variables and \(h_{1},\ h_{2}\) the constituent functions). In other words, the structure of a compositional function can be represented by a DAG. In this approximation scenario, the required number of units depends on \(N=\mathcal{O}(\sum_{h}\epsilon^{-n_{h}})\), where \(n_{h}\) is the input dimensionality of function \(h\). If \(\max_{h}n_{h}=d\), then \(\sum_{h}\epsilon^{-n_{h}}\leq\sum_{h}\epsilon^{-d}=|\mathcal{H}|\epsilon^{-d}\).

Footnote 7: We invite the reader to consult ref. [28] for a complete formulation of the theorems.

Footnote 8: Depending on the context, we use the same \(f\) notation for both the fraction of removed nodes and the function to be approximated.

The primary advantage of complex networks is their potential to avoid the curse of dimensionality when relevant graphs for the function to be learned are present. Under the assumption that the function linking the _swiss roll_ and _s curve_ points to the ground truth labels is compositional (intuitively, in non-noisy datasets, each class is a union of various segments), we conjecture that our complex NNs can exploit this compositionality. In the high-difficulty regime, the necessary network size for MLP h1 to achieve the same accuracy as complex models likely exceeds the size set for experiments. While one could argue that the datasets employed were compositionally sparse by chance, according to [27], all _efficiently computable functions_ must be _compositionally sparse_ (i.e., their constituent functions have "small" \(d\)). Performance differences on noisy datasets are less noticeable, possibly due to the minimal overlap between the functions to be approximated and the studied topologies. Notably, our setup does not precisely match the theorem formulations in [28] (e.g., SELUs are not infinitely differentiable), but Poggio et al. argue that the hypotheses can likely be relaxed. No statistically significant differences emerged between the complex graph families from the results of Section 4. Various explanations exist for this outcome: all tested topologies could be complex enough to include relevant subgraphs of the target \(f\) functions; the random DAG conversion heuristic might have perturbed hidden topological properties of the original undirected networks; or the degree distribution of a network may not be the most relevant topological feature in a model's approximation capabilities.

However, the higher accuracy in complex networks comes with trade-offs. Although the methodology in [6] improves the scalability of complex NNs and enables experimentation with arbitrary DAGs, it is important to note that 1-hidden layer MLPs typically have faster forward pass computation. In these models, the forward pass requires only two matrix multiplications, whereas, in
NNs built using 4Ward, the number of operations depends on the DAG _height_. Moreover, the analyses in Figure 5 demonstrate MLPs' superiority in a graph damage scenario. We speculate that the hidden units in an MLP h1 contribute equally to the approximation of the target function. In contrast, the ability of complex networks to exploit the compositionality of the function to be learned might lead to high specialization of some hidden units.

## 6 Conclusion

Our study provides valuable insights into the influence of network topology on the approximation capabilities of artificial neural networks (ANNs). Our novel methodology for constructing complex ANNs based on various topologies has enabled a systematic exploration of the impact of network structure on model performance. The experiments conducted on synthetic datasets demonstrate the potential advantages of complex topologies in high-difficulty regimes when compared to traditional MLPs.

While complex networks exhibit improved performance, this comes at the cost of increased computational requirements and reduced robustness to graph damage. Our investigation of the relationship between topological attributes and model performance (Appendix A) reveals a complex interplay that cannot be explained by any single attribute. This finding highlights the need for further research to better understand the interactions among multiple topological attributes and their impact on ANN performance.

As a result of this study, researchers and practitioners can consider the potential benefits and limitations of complex topologies when designing ANNs for various tasks. Moreover, our work provides a foundation for future research focused on identifying optimal topological features, understanding the impact of multiple attributes, and developing new methodologies for constructing more efficient and robust ANN architectures. By further exploring the role of network topology in ANNs, we can unlock new possibilities for improving the performance and adaptability of these models across diverse applications.
