Spectral Higher-Order Neural Networks Have Sharp Expressivity Bounds Gianluca Peri, Diego Febbe, Duccio Fanelli Department of Physics, University of Florence & INFN, Italy
arXiv:2607.19042v1 [cs.LG] 21 Jul 2026
{gianluca.peri, diego.febbe, duccio.fanelli}@unifi.it
Abstract—Neural hypergraphs are a natural generalization of neural networks, the reference models in modern machine learning. Yet, their deployment has proven demanding: the number of weighted hyperedges required leads to an intractable parameter explosion. However, a novel parametrization that leverages spectral attributes for neural hypergraphs has been recently proposed, that enables to recycle parameters via a weight sharing scheme and consequently yields a significant reduction of the associated computational cost. Preliminary tests carried out on spectral higher-order architectures pointed to meaningful improvements in both performance and interpretability. Building on these results, we advance the benchmarking efforts by evaluating the spectral higher order framework on N-bit parity tasks, a wellestablished testbed known to be particularly challenging. As we will convincingly argue, Spectral Higher-Order Neural Networks (SHONNs) possess a versatile and highly tunable hypothesis space. Index Terms—machine learning, neural networks, hypergraphs
I. I NTRODUCTION While in the past good old-fashioned artificial intelligence (GOFAI) solved problems by creating ad-hoc algorithms, modern machine learning (ML) defines instead learning algorithms, that in turn produce solving routines. Such an indirect approach proved incredibly powerful, leading to a boom in modern artificial intelligence capabilities that nowadays spans from simple agentic behavior [13] to language models [17]. The foundational paradigm underlying nearly all contemporary machine learning algorithms is the neural network (NN), where solutions are generated by tuning the connections’ weights of a massive network. Over the years, numerous network topologies have been proposed, but the most utilized remains the feedforward neural network (FNN): neurons (i.e. the network’s nodes) are arranged into layers, and then connected by unidirectional bundles of links (see Figure 1a). A natural generalization is represented by higher-order neural network (HONN) [8]–[10], [12], where hyperlinks are also introduced (see Figure 1b for a pictorial representation of the interaction scheme). Although HONNs feature a clearly more general topology, the adoption of even their simplest variant—namely, the triadic HONN shown in This work has been accepted for presentation at COMPENG 2026 – 2026 IEEE Workshop on Complexity in Engineering.
Figure 1b—has been rendered infeasible due to parameter scaling. Indeed, whereas standard neural networks yield an 𝑂 (𝑁 2 ) parameter scaling (with 𝑁 representing the layer size), a naive triadic HONN implementation—associating a single weight with each hyperlink—scales as 𝑂 (𝑁 3 ). Such parameter explosion inevitably hinders the training of these higher-order networks. To overcome these limitations different solutions have been devised [5], [6], [16]. In addition to the above, a new parameterization for triadic HONN s has been recently proposed, drastically reducing the parameter count via a parameter-sharing scheme that leverages the spectral properties of the underlying hypergraph. Higherorder networks based on this latter parameterization scheme benefit from the most compact 𝑂 (𝑁 2 ) scaling known in the literature, and are referred to as spectral HONNs (SHONNs) [14] (see Appendix A for mathematical details on the spectral parameterization). An interesting property of SHONNs is that, contrary to standard NNs, they can operate without enforcing ad hoc non-linearities (e.g., ReLU). This is made possible by the hyperlinks, which provide a source of non-linearity inherent in the network’s topology. As we shall see, this notable property has practical implications: specifically, it allows to fine-tuning the model’s expressiveness, up to a level that is simply out of reach for standard NNs. The rest of the manuscript is structured as follows: in Section II we shall briefly go through the math underpinning triadic HONNs, and then pivot to illustrate the details regarding the parameterization of SHONNs. From there, in Section III, we shall substantiate the claims regarding SHONNs’ tunability, and test their performance on 𝑁-bit parity benchmarks. Finally, in Section IV, we will sum up and elaborate on future research directions. II. HONN S AND SHONN S In the following we shall refer exclusively to a single forward propagation between neural layers. The symbol 𝑥 will refer to activations on the first-layer, whereas 𝑦 identify the activity associated to neurons of the second layer; 𝑤 stands for the involved model’s weights. Symbols 𝜆 or 𝜙 will be used to identify the relevant spectral attributes (namely, eigenvalue or eigenvector elements).
𝑥1
𝑥1
𝑥2
𝑦1
𝑥2
𝑦1
𝑥3
𝑦2
𝑥3
𝑦2
𝑥4
𝑦3
𝑥4
𝑦3
𝑥5
𝑥5
(a) Standard connectivity of a neural network.
(b) Connectivity of a standard higher-order (triadic) net.
Fig. 1: Schematics of different neural architectures. In a standard neural network (panel 1a) the first-layer neurons (blue) generate output activations (denoted by 𝑦 𝑘 ) on the neurons (red) that define the second-layer, via pairwise links (gray arrows), followed by a local non-linearity (not shown). Triadic higher-order networks (panel 1b) extend this architecture by including hyperlinks (in black) that capture three-body interactions (two first-layer neurons associated to one second-layer neuron).
The standard forward propagation of a neural network can be cast as follows: 𝑦𝑘 =
𝑁 ∑︁
𝑤 𝑘𝑖 𝑥 𝑖 .
(1)
𝑖=0
At variance, the simplest triadic HONN propagates the information according to the following mathematical recipe: 𝑦𝑘 =
𝑁 ∑︁
𝑤 𝑘𝑖 𝑥𝑖 +
𝑁 −1 ∑︁
𝑤˜ 𝑘𝑖 𝑗 𝑥𝑖 𝑥 𝑗 .
(2)
0≤𝑖 ≤ 𝑗
𝑖=0
Note the presence in the above expression of the bias neuron in the linear part of the forward pass 1 . We can immediately notice the 𝑂 (𝑁 2 ) vs. 𝑂 (𝑁 3 ) scaling that we anticipated in the previous section. The spectral parameterization solves this problem via a reformulation of the higher-order interactions: 𝑦𝑘 =
𝑁 ∑︁
𝑤 𝑘𝑖 𝑥𝑖 +
𝑁 −1 ∑︁
˜ (𝑜𝑢𝑡 ) ) 𝜙˜𝑘𝑖 𝑗 𝑥𝑖 𝑥 𝑗 . (𝜆˜ 𝑖(𝑖𝑛) 𝑗 − 𝜆𝑘
(3)
0≤𝑖 ≤ 𝑗
𝑖=0
Denote by 𝑁𝑖𝑛 the number of neurons in the first layer, and 𝑁𝑜𝑢𝑡 the number in the second layer. Then, 𝜆˜ 𝑖(𝑖𝑛) is the 𝑗 element of a 𝑁𝑖𝑛 × 𝑁𝑖𝑛 matrix of (spectral) parameters, 𝜆˜ 𝑘(𝑜𝑢𝑡 ) is one entry of a vector of length 𝑁𝑜𝑢𝑡 , and finally 𝜙 𝑘𝑖 𝑗 defines a 𝑁𝑜𝑢𝑡 × 𝑁𝑖𝑛 × 𝑁𝑖𝑛 parameter tensor. The rigorous 1 It is worth remarking that, in principle, a general triadic higher-order network could follow to the more complex transformation:
𝑦𝑘 =
𝑁 ∑︁ 𝑖=0
𝑤𝑘𝑖 𝑥𝑖 +
𝑁 −1 ∑︁
𝑓 ( 𝑥𝑖 , 𝑥 𝑗 ; 𝜽 ) ,
0≤𝑖≤ 𝑗
where 𝑓 represents a generic three-body coupling function, and 𝜽 is the associated parameter vector. However, it is customary to consider only multiplicative couplings [12]. This practice amounts to considering only the first order effects of a possible, more complex, coupling function 𝑓 .
underlying formalism is illustrated in details in Appendix A. The above decomposition in terms of generalized eigenvectors and eigenvalues opens the door to a novel training paradigm where only a portion of the spectral parameters is optimized [4]; for example, one could choose to train only the eigenvalues and a portion of the eigenvectors’ tensor, or, as we shall, solely optimize the eigenvalues, yielding a consequent compression of the parameter scaling down to 𝑂 (𝑁 2 ), even for the higher-order counterpart of the neural model. A priori, While training only a subset of the model’s parameters risks hindering expressivity and performance, existing literature rules out this risk for this specific case, provided enough neurons are present [14]. At this point, it is mandatory to discuss one of the main differences between standard neural networks and higher-order ones: the handling of non-linear mappings. In the standard case the hypothesis space of the model is rendered nonlinear via the application of a suitable activation function 𝜎: When a signal reaches one of the network’s hidden layers, the activation function 𝜎 is applied to it neuron-wise. Without this crucial step, the neural network would be confined to a strictly linear hypothesis space. On the contrary, higher-order neural models are intrinsically expressive: the non-linearity is inherently encapsulated into the topology of the model via its higher-order neural couplings. Because this characteristic obviates the need for an explicit non-linearity 𝜎, higher-order models can be successfully deployed either way. In the following we shall specifically focus on the 𝜎-less case. Remarkably, it has been proven that 𝜎-less triadic neural networks—when equipped with a sufficient number of neurons across enough layers—can approximate any continuous function, even if only their eigenvalues are optimized [14]. In the following we will expand on this notable result, by empirically investigating the expressivity of the triadic models under eigenvalue-only
training, for specific parity tasks as hereafter detailed. III. SHONN S ON PARITY TASKS Even for the simplest standard model—a three-layer MLP—the universal approximation theorem [7] guarantees that the network can approximate any continuous map with arbitrary precision, provided a sufficient number of hidden neurons are used. This kind of unbounded expressivity can be extremely useful, but it can also lead to overfitting problems. Finite-size, spectral, higher-order networks, when used in combination with neural activation functions, are more expressive than traditional neural networks and can, therefore, suffer from similar overfitting problems. However, the higherorder models analyzed herein can also be effectively utilized without activation functions. In this latter setting, the ensuing models are characterized by a restricted hypothesis space whose span can be tuned via simple architectural choices (i.e., the number of layers). Specifically, it has been shown that when integrated into larger neural architectures, these models can act as implicit regularizers [14]. To further explore the expressivity of SHONNs, we here carry out N-bit parity benchmarks on them. Parity tasks are a notoriously challenging problem for standard neural networks: a binary input vector of size 𝑁 𝐼 has to be classified as even or odd, depending on its parity 2 . The intrinsic complexity of the parity mapping stems from its sensitivity: even for large inputs, flipping a single activation in the first layer must trigger a completely opposite output pattern. For 𝑁 𝐼 = 2 the associated parity task collapses to the xor mapping, while for large 𝑁 𝐼 the learning problem becomes challenging really fast. In Figure 2 are reported the performances of simple onehidden-layer MLPs, equipped with ReLU activated hidden units, on parity tasks up to 17 bits (further details on the experimental setup are presented in Appendix B). It is possible to show (see Appendix C) that a ReLU NN with 𝑁 hidden neurons is capable of exactly solving all the parity tasks up to 𝑁-bits. Beyond theoretical bounds, the optimization process in practice fails to drive the network to the global minimum of the loss function, leading to suboptimal performance even under ideal learning conditions. While making the network wider could, in principle, allow the optimizer to find a valid parity mapping for larger 𝑁, doing so forces an increase in the model’s theoretical expressivity, thereby sacrificing the regularization guarantees. SHONNs avoid this problem by decoupling the ease of optimization (that scales with the neural width) from the maximum complexity of the expressed mapping (scaling with the network’s depth). In Figure 3 the same parity benchmarks are performed on SHONNs models (without training the triadic eigenvectors). The comparison with Figure 2 immediately reveals crucial differences: the spectral higher-order models achieve perfect accuracies inside their expressivity bounds, to then sharply drop to the random guessing regime once the number of bits in the input goes over their polynomial expressivity. 2 As an example, the 𝑁 = 3 input vector (+1, −1, −1) has an even number 𝐼 of −1 and is therefore even.
IV. C ONCLUSIONS Given the parity experiments reported in the last section it appears that: • The triadic-eigenvalues-only training paradigm seems to not hinder the expressivity of the higher-order models, if enough hidden neurons are present. • Since the expressivity bounds of SHONN s clearly scale with their layer number, we are free to increase the number of hidden neurons without polluting the hypothesis space; this in turn allows the optimizer to push the model to the edge of its expressivity, giving rise to sharp transitions that are not obtainable using standard MLPs. • SHONN s once again seem to combine ease of training with the ability to set sharp expressivity bounds, making them ideal building blocks to introduce a well-defined implicit regularization in neural models. Further studies should aim to shed light on the possibility of employing these sharp expressivity bounds inside other neural models, expanding on the work already present in the [14]. In particular, implicit regularization stands out as an ideal practical line of application for this research topic, but triadicaugmented PINNs should also be mentioned as a possible interesting prosecution. C ODE AVAILABILITY The code underpinning the presented results can be found at https://github.com/gianluca-peri/shonns-expressiveness ACKNOWLEDGMENTS The authors would like to acknowledge the support by # NEXTGENERATIONEU (NGEU) funded by the Ministry of University and Research (MUR), National Recovery and Resilience Plan (NRRP), project MNESYS (PE0000006)—A multiscale integrated approach to the study of the nervous system in health and disease (DN. 1553 11.10.2022).
Fig. 2: Results of 𝑁-bit parity benchmarks (up to 17 bits) on simple 3-layer MLPs, with 16 and 10 hidden units respectively (further implementation details in Appendix B). As proven in Appendix C, 𝑀 𝐿𝑃(10) (the MLP with 10 hidden units) should hold sufficient expressive power to exactly solve the tasks up to 10 bits; however, in practice, the learning process is unable to optimize the network to this theoretical ideal. A similar pattern is reported for 𝑀 𝐿𝑃(16). Notice that adding extra neurons helps the optimizer to find a better parameter configuration. In practice, it seems that an 𝑀 𝐿𝑃(𝑁) is not able to learn how to solve the 𝑁-bit parity task, despite having the potentiality for it. Adding more neurons helps the optimization process, but also pushes the theoretical expressivity of the model forward, thus creating a fuzzy situation where no sharp expressivity bound can be reached trough learning.
Fig. 3: Results of 𝑁-bit parity benchmarks (up to 17 bits) applied on SHONNs. Specifically, these higher-order models were not equipped with neuron-wise nonlinearities, and also the spectral triadic eigenvectors were not trained, keeping the parameter scaling limited to 𝑂 (𝑁 2 ) (further implementation details in Appendix B). We can see that the expressivity of the models is strictly bound by their layer number: a 3-layer model, for example, can express only up to order 4 polynomial mappings, regardless of the number of hidden neurons; as a consequence, the optimizer is generally able to push the model right to the bounds of its expressivity, giving rise to the observed sharp drop-off phenomena, as depicted in figure.
A PPENDIX A T HE S PECTRAL PARAMETERIZATION Spectral Parametrization for Standard Neural Networks Consider a weight matrix 𝑊𝐾 × 𝑁 of the links between layers of size 𝑁 and 𝐾. The spectral parameterization approach [11] leverages the implied adjacency matrix between the 𝑁 + 𝐾 neurons of the underlying directed bipartite graph: O 𝑁 × 𝑁 O 𝑁 ×𝐾 𝐴= (4) 𝑊𝐾 × 𝑁 O𝐾 ×𝐾 The 𝐴 matrix operates the forward pass on the global activation vector of the neural graph, usually called 𝒂. Crucially, the forward pass of information mediated by 𝐴 is independent of its diagonal elements. This allows us to consider an augmented version of 𝐴, with non-zero diagonal entries, without modifying the activations’ dynamics. We can then express the modified adjacency matrix in the form 𝐴 = ΦΛΦ−1 , with Λ diagonal eigenvalues matrix, and with Φ: I O 𝑁 ×𝐾 Φ = 𝑁 ×𝑁 (5) 𝜙 𝐾 × 𝑁 I𝐾 ×𝐾 where I denotes the identity matrix. At last, given that Φ−1 = 2I − Φ, it is easy to show that the weights 𝑤 𝑘𝑖 , which populate the sub-diagonal block of 𝐴, can be written as: 𝑤 𝑘𝑖 = (𝜆𝑖(𝑖𝑛) − 𝜆 𝑘(𝑜𝑢𝑡 ) )𝜙 𝑘𝑖 ,
(6)
where 𝜆 𝑖(𝑖𝑛) is the 𝑖-th element of the first portion of the eigenvalue diagonal (the first 𝑁), 𝜆 𝑘(𝑜𝑢𝑡 ) is the 𝑘-th of the last one (the last 𝐾), and 𝜙 𝑘𝑖 is the 𝑘, 𝑖 element of the sub-diagonal block 𝜙 𝐾 × 𝑁 . This novel parametrization offers the versatility to achieve a multitude of different goals, spanning pruning techniques, input feature relevance detection, architecture search strategies, parameter reduction paradigms, and the training of dynamical systems [1]–[4], [15]. Spectral Parametrization for Triadic Higher-Order Networks Note that in equation (2) the 𝑤˜ 𝑘𝑖 𝑗 tensor element can be thought as a matrix element, 𝑤˜ 𝑘𝑖 ′ : here 𝑖 ′ represents an appropriate index which enumerates the set of unordered pairs (𝑖, 𝑗), 0 ≤ 𝑖 ≤ 𝑗 < 𝑁 in lexicographical order: (0, 0) → 0, (0, 1) → 1, ..., (0, 𝑁 − 1) → 𝑁 − 1, (1, 1) → 𝑁, ..., (𝑁 − 1, 𝑁 − 1) →
𝑁 (𝑁 + 1) − 1. 2
In close form 𝑖 ′ is given by: 𝑖′ = 𝑗 − 𝑖 +
𝑖−1 ∑︁
(𝑁 − 𝑘).
(7)
𝑘=0
The lexicographical bijection (7) allows the deployment of the spectral parametrization for triadic interactions: we first use (7) to map the tridimensional weight tensor [ 𝑤˜ 𝑘𝑖 𝑗 ] into the weight matrix [ 𝑤˜ 𝑘𝑖 ′ ]; we can then simply express [ 𝑤˜ 𝑘𝑖 ′ ] via the spectral parametrization. So from (2) we get: ∑︁ ∑︁ (𝜆˜ 𝑖(𝑖𝑛) − 𝜆˜ 𝑘(𝑜𝑢𝑡 ) ) 𝜙˜𝑘𝑖 ′ 𝑥 𝑖 ′ 𝑦𝑘 = (𝜆𝑖(𝑖𝑛) − 𝜆 𝑘(𝑜𝑢𝑡 ) )𝜙 𝑘𝑖 𝑥𝑖 + (8) ′ 𝑖′
𝑖
with 𝑥𝑖 ′ = 𝑥𝑖 𝑥 𝑗 . Finally we can expand 𝑖 ′ back to 2 dimensions: 𝑦𝑘 =
∑︁ 𝑖
(𝜆𝑖(𝑖𝑛) − 𝜆 𝑘(𝑜𝑢𝑡 ) )𝜙 𝑘𝑖 𝑥𝑖 +
∑︁
˜ (𝑜𝑢𝑡 ) ) 𝜙˜𝑘𝑖 𝑗 𝑥𝑖 𝑥 𝑗 , (𝜆˜ 𝑖(𝑖𝑛) 𝑗 − 𝜆𝑘
0≤𝑖 ≤ 𝑗
to obtain equation (3). A PPENDIX B D ETAILS ON THE PARITY EXPERIMENTS Refer to Table I for the specifications regarding the MLP experiment. Table II refers instead to the SHONN trainings.
(9)
Hyperparameter / Setting
Value Model Architecture Network Type Multi-Layer Perceptron (MLP) Hidden Layers 1 Activation Function ReLU Output Dimension 1 Dataset & Evaluation Input sequence lengths (𝑁 ) 1, 2, . . . , 17 Dataset Size 2 𝑁 (all possible 𝑁 -parity inputs) Samples per 𝑁 3 Optimization Optimizer Adam Learning Rate 10 −3 Loss Function Binary Cross Entropy with Logits Batch Size min(215 , 2 𝑁 ) Max Epochs 5000 Early Stopping Patience max(100, 20 × 𝑁 ) epochs (on train loss) Gradient Clipping (Max Norm) 1.0
TABLE I: Experiment specifications and hyperparameters for the MLP parity task. Hyperparameter / Setting
Value Model Architecture Network Type Spectral Higher-Order Neural Network (SHONN) Activation Function None Hidden Dimension 128 Output Dimension 1 Dataset & Evaluation Input sequence lengths (𝑁 ) 1, 2, . . . , 17 Dataset Size 2 𝑁 (all possible 𝑁 -parity inputs) Samples per 𝑁 3 Optimization Optimizer Adam Learning Rate 10 −3 Loss Function Binary Cross Entropy with Logits Batch Size min(215 , 2 𝑁 ) Max Epochs 5000 Early Stopping Patience max(100, 20 × 𝑁 ) epochs (on train loss) Gradient Clipping (Max Norm) 1.0
TABLE II: Experiment specifications and hyperparameters for the SHONN parity task. A PPENDIX C R E LU ACTIVATED MLP S ON PARITY TASKS In the literature it has been shown that a one-hidden-layer neural network, with 𝑁 hidden units, is able to perfectly express the 𝑁-bit parity function [18]. However, these previous results are restricted to neural networks with threshold-like activation functions, and are not directly applicable to modern, ReLU activated, networks, outputting logits. The following theorem covers this modern context. Theorem 1. A feedforward neural network with a single, ReLU activated, hidden layer of size 𝑁 is able to compute all the parity mappings up to 𝑁-bits. Proof. We shall now focus on proving that a MLP with one hidden layer of size 𝑁 is able to perfectly solve the 𝑁-bit parity problem. The fact that it’s also able to solve all the other parity tasks up to 𝑁-bits will then easily follow. Let the input vector be 𝒙 ∈ {−1, 1} 𝑁 and consider a one-hidden-layer, ReLU activated, MLP with 𝑁 hidden neurons. We start by constraining the weights of the first layer 𝑤 𝑖(1) 𝑗 to be identically 1: 𝑤 𝑖(1) 𝑗 = 1 ∀𝑖, 𝑗 .
(10)
Consequently, the inputs to all neurons in the hidden layer are simply the same sum 𝑆(𝒙) = sum 𝑆(𝒙) can only take 𝑁 + 1 distinct values: 𝑆 𝑘 ∈ {−𝑁, −𝑁 + 2, . . . , 𝑁 − 2, 𝑁 }
𝑘 ∈ {0, . . . , 𝑁 },
Í
𝑖 𝑥 𝑖 . Because 𝑥 𝑖 ∈ {−1, 1}, the
(11)
where 𝑘 runs on the possible input sequences. We now set the hidden biases to sit between these possible values of 𝑆(𝒙): 𝒃 = {𝑁 − 1, 𝑁 − 3, ..., −𝑁 + 3, −𝑁 + 1}, i.e. 𝑏𝑗 = 𝑁 − 2𝑗 + 1
𝑗 ∈ {1, . . . , 𝑁 }.
(12)
𝑊 (1) = 1 −1
ℎ1 𝑤 (2) 1
−1
𝑤2(2 )
ℎ2
(2 )
𝑦
𝑤3
+1
ℎ3 (2)
𝑤4
−1
(2
ℎ4
)
𝑤0
1
Fig. 4: Depiction of the kind of neural network instance used in Theorem 1. The post non-linearity activation of the 𝑗-th hidden neuron is then ℎ 𝑗 = max(0, 𝑆(𝒙) + 𝑏 𝑗 ). The network’s final output is a linear combination of the ℎs, followed by a sigmoid activation 𝜎(·). Let 𝑧 be the pre-sigmoid logit: 𝑁 ∑︁ (13) 𝑧 = 𝑤 0(2) + 𝑤 (2) 𝑗 ℎ𝑗, 𝑗=1
note that we are adopting the convention of the 0-th bias neuron (backward-detached neuron with constant unitary activation) to express the bias term of the last layer (see Figure 4 for a graphical depiction). We shall have a different value of 𝒉 for each possible input combination (enumerated by 𝑘). Note now that to compute the parity function, and minimize the BCE loss, it is sufficient for the logit 𝑧 to be able to alternate between −𝑀, 𝑀, 𝑀 >> 0 as 𝑘 increases (e.g., 𝑀 even parity, −𝑀 for odd parity). The trick now is to consider the square matrix 𝐴 ( 𝑁 +1) × ( 𝑁 +1) , whose rows span the possible 𝑘 values present in the hidden layers’ neurons after the non-linearity, including the bias neuron: specifically the rows of 𝐴 will contain the distinct 𝑁 + 1 activity vectors of the hidden layer 𝒉(𝑘). It is easy to convince oneself that the resulting matrix will be a particular kind of bordered Toeplitz matrix: 0 © 1 2 𝐴 = 3 .. . 𝑁 − 1 « 𝑁
0 0 1 2 .. .
0 0 0 1 .. .
··· ··· ··· ··· .. .
𝑁 −2 𝑁 −1
𝑁 −3 𝑁 −2
··· ···
0 0 0 0 .. .
0 0 0 0 .. .
1 ª 1® ® 1® ® 1® .. ®® .® ® 1 0 1® 2 1 1¬ ( 𝑁 +1) × ( 𝑁 +1)
(14)
that is promptly proven invertible via Laplace expansion on the first row, giving determinant equal to (−1) 𝑁 . As we already stated, to compute the parity function, and minimize the BCE loss, it is sufficient for the logit 𝑧 to be able to alternate between −𝑀, 𝑀 as 𝑘 increases. This concretely amounts to finding a single weight vector 𝒘 (2) that solves the linear system: 𝐴𝒘 (2) = 𝒕 (15) with 𝒕 having elements 𝑡𝑖 = (−1) 𝑖 𝑀. But this is surely possible given that 𝐴 is invertible. We have thus proven that a MLP with 𝑁 hidden neurons in one layer is able to perfectly express the 𝑁-bit parity mapping; but since we can always detach hidden neurons by setting all their incoming and outgoing weights to zero, it also immediately follows that the same network is able to express all the 𝑀-bit parity tasks with 𝑀 ≤ 𝑁. □
R EFERENCES [1] Lorenzo Buffoni, Enrico Civitelli, Lorenzo Giambagli, Lorenzo Chicchi, and Duccio Fanelli. Spectral pruning of fully connected layers. Scientific Reports, 12(1):11201, 2022. [2] Lorenzo Chicchi, Lorenzo Buffoni, Diego Febbe, Lorenzo Giambagli, Raffaele Marino, and Duccio Fanelli. Estimating global input relevance and enforcing sparse representations with a scalable spectral neural network approach. arXiv preprint arXiv:2406.01183, 2024. [3] Lorenzo Chicchi, Duccio Fanelli, Diego Febbe, Lorenzo Buffoni, Francesca Di Patti, Lorenzo Giambagli, and Raffaele Marino. Deterministic versus stochastic dynamical classifiers: opposing random adversarial attacks with noise. Machine Learning: Science and Technology, 6(3):035054, 2025. [4] Lorenzo Chicchi, Lorenzo Giambagli, Lorenzo Buffoni, Timoteo Carletti, Marco Ciavarella, and Duccio Fanelli. Training of sparse and dense deep neural networks: Fewer parameters, same performance. Physical Review E, 104(5):054312, 2021. [5] Grigorios G Chrysos, Markos Georgopoulos, Jiankang Deng, Jean Kossaifi, Yannis Panagakis, and Anima Anandkumar. Augmenting deep classifiers with polynomial neural networks. In European Conference on Computer Vision, pages 692–716. Springer, 2022. [6] Grigorios G Chrysos, Stylianos Moschoglou, Giorgos Bouritsas, Jiankang Deng, Yannis Panagakis, and Stefanos Zafeiriou. Deep polynomial neural networks. IEEE transactions on pattern analysis and machine intelligence, 44(8):4021–4034, 2021. [7] George V. Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals and Systems, 2:303–314, 1989. [8] Geoffrey E. Hinton et al. David E. Rumelhart, James L. McClelland. Parallel distributed processing: explorations in the microstructure of cognition, vol. 1: foundations. The MIT Press, 1986. [9] Stefania Ebli, Michaël Defferrard, and Gard Spreemann. Simplicial neural networks. ArXiv, 2020. [10] Yifan Feng, Haoxuan You, Zizhao Zhang, R. Ji, and Yue Gao. Hypergraph neural networks. In AAAI Conference on Artificial Intelligence, 2018. [11] Lorenzo Giambagli, Lorenzo Buffoni, Timoteo Carletti, Walter Nocentini, and Duccio Fanelli. Machine learning in spectral domain. Nature Communications, 12(1):1330, 2021. [12] Colin Giles and T. Maxwell. Learning, invariance, and generalization in high-order neural networks. Applied optics, 26 23:4972–8, 1987. [13] Gianluca Peri, Lorenzo Buffoni, Giacomo Chiti, Duccio Fanelli, Raffaele Marino, Andrea Nocentini, and Pier Paolo Panti. Smart walkers in discrete space. Chaos, Solitons & Fractals, 2026. [14] Gianluca Peri, Timoteo Carletti, Duccio Fanelli, and Diego Febbe. Spectral higher-order neural networks. In arXiv preprint arXiv:2603.28420, 2026. [15] Gianluca Peri, Lorenzo Chicchi, Duccio Fanelli, and Lorenzo Giambagli. Spectral architecture search for neural network models. npj Artificial Intelligence, 1(1):43, Dec 2025. [16] Yoan Shin and Joydeep Ghosh. The pi-sigma network: an efficient higher-order neural network for pattern classification and function approximation. IJCNN-91-Seattle International Joint Conference on Neural Networks, i:13–18 vol.1, 1991. [17] Richard E. Turner. An introduction to transformers. ArXiv, 2023. [18] Bogdan M. Wilamowski, David K. Hunter, and Aleksander Malinowski. Solving parity-n problems with feedforward neural networks. Proceedings of the International Joint Conference on Neural Networks, 2003., 4:2546–2551, 2003.