Non Commutative Convolutional Signal Models in Neural Networks:
  Stability to Small Deformations
In this paper we discuss the results recently published in~[1] about
algebraic signal models (ASMs) based on non commutative algebras and their use
in convolutional neural networks. Relying on the general tools from algebraic
signal processing (ASP), we study the filtering and stability properties of non
commutative convolutional filters. We show how non commutative filters can be
stable to small perturbations on the space of operators. We also show that
although the spectral components of the Fourier representation in a non
commutative signal model are associated to spaces of dimension larger than one,
there is a trade-off between stability and selectivity similar to that observed
for commutative models. Our results have direct implications for group neural
networks, multigraph neural networks and quaternion neural networks, among
other non commutative architectures. We conclude by corroborating these results
through numerical experiments.
Alejandro Parada-Mayorga, Landon Butler, Alejandro Ribeiro
# Non Commutative Convolutional Signal Models in Neural Networks: Stability to Small Deformations

###### Abstract

In this paper we discuss the results recently published in [1] about algebraic signal models (ASMs) based on non commutative algebras and their use in convolutional neural networks. Relying on the general tools from algebraic signal processing (ASP), we study the filtering and stability properties of non commutative convolutional filters. We show how non commutative filters can be stable to small perturbations on the space of operators. We also show that although the spectral components of the Fourier representation in a non commutative signal model are associated to spaces of dimension larger than one, there is a trade-off between stability and selectivity similar to that observed for commutative models. Our results have direct implications for group neural networks, multigraph neural networks and quaternion neural networks, among other non commutative architectures. We conclude by corroborating these results through numerical experiments.

Alejandro Parada-Mayorga\({}^{*}\), Landon Butler\({}^{\dagger}\), and Alejandro Ribeiro\({}^{*}\)+University of Pennsylvania+University of California, Berkeley+

Footnote †: This document is a conference version of [1] which was recently published in IEEE-TSP. The second author acknowledges support by the NSF Graduate Research Fellowship under Grant No. DGE-2146752.

Non commutative convolutional architectures, Algebraic Neural Networks (AlgNNs), algebraic signal processing (ASP), non commutative algebras, non commutative operators.

## 1 Introduction

Convolutional signal models have become ubiquitous tools in machine learning. Understanding their fundamental properties plays a central role in explaining convolutional neural networks' good performance and limitations in different domains. One such property is that of stability to deformations. Previous works have shown that the good performance of convolutional architectures can be explained in part by the fact that for the same discriminability, a convolutional network is more stable to deformations than the corresponding convolutional filters [2, 3, 4, 5, 6]. These results apply in commutative scenarios such as graph filters and graph neural networks [5], Euclidean filters and traditional convolutional neural networks [4], graphon filters and graphon neural networks [7, 8], and commutative group filters and their associated group neural networks [2, 3]. However, the question of stability has remained open for non commutative signal models and architectures such as multigraph neural networks [9, 10], Lie group neural networks [11, 12], quaternion neural networks [13], and quiver neural networks [14].

In this work we develop a formal description of non commutative signal models as a particular instantiation of an algebraic signal model with a non commutative algebra. We leverage this algebraic representation to study the stability of non commutative convolutional filters and their associated neural networks. We show that although the spectral representations of non commutative convolutional filters are described by spaces whose dimension is larger than one, there is still a trade-off between discriminability and stability, similar to the one observed in commutative scenarios. Additionally, we show that for the same level of discriminability, the neural networks are more stable than the corresponding non commutative convolutional filters, under the notion of deformation and stability used in [2, 3]. We also prove that the stability bounds for non commutative convolutional networks are a scaled version of the bounds derived for the filters. This implies that the networks inherit the stability properties from the filters as a consequence of the attributes of the pointwise nonlinearities and the pooling operators. We conclude with numerical experiments to validate our results.

## 2 Non Commutative Convolutional Signal Models

The general notion of a convolutional signal model in the algebraic sense was first introduced by Puschel in [15, 16, 17, 18] and is known as _algebraic signal processing (ASP)_. In this context, any convolutional signal model is given by a triplet \((\mathcal{A},\mathcal{M},\rho)\), where \(\mathcal{A}\) is a unital associative algebra, \(\mathcal{M}\) is a vector space and \(\rho\) is a homomorphism from \(\mathcal{A}\) to the space of endomorphisms of \(\mathcal{M}\), \(\text{End}(\mathcal{M})\). The elements in \(\mathcal{A}\) are the filters, signals are the elements of \(\mathcal{M}\) and \(\rho:\mathcal{A}\rightarrow\text{End}(\mathcal{M})\) instantiates the abstract filters in \(\mathcal{A}\) into concrete operators acting on \(\mathcal{M}\).

Most applications of the ASP paradigm are associated with scenarios where the filters are determined by commutative operators [7, 8, 19, 20, 21]. However, it is possible to rely on the same framework to introduce convolutional non commutative models choosing \(\mathcal{A}\) as a non commutative algebra [1]. Then, any non commutative convolutional model to be considered in this paper can be described by the triplet \((\mathcal{A},\mathcal{M},\rho)\) where \(\mathcal{A}\) is a non commutative algebra. If \(\mathbf{x}\in\mathcal{M}\) is a signal, we refer to the signal \(\mathbf{y}=\rho(a)\mathbf{x}\) as the filtered version of \(\mathbf{x}\) by means of the filter \(a\in\mathcal{A}\). More specifically, we say that \(\mathbf{y}\) is the result of performing a convolution between the filter \(a\in\mathcal{A}\) and the signal \(\mathbf{x}\in\mathcal{M}\).

To simplify the representation of the elements in \(\mathcal{A}\), we leverage the concept of a _generator set_ of an algebra. We say that the set \(\mathcal{G}\subset\mathcal{A}\) generates the algebra \(\mathcal{A}\) if any element of \(\mathcal{A}\) can be written as a polynomial of the elements in \(\mathcal{G}\). For instance, if \(\mathcal{G}=\{g_{1},g_{2}\}\), then any element \(a\in\mathcal{A}\) can be written as \(a=p(g_{1},g_{2})\), where \(p\) is a polynomial with two independent variables. If \(\mathcal{A}\) is non commutative, the elements of \(\mathcal{G}\) do not commute. The image of a generator, \(g\in\mathcal{G}\), under \(\rho\) is known as a _shift operator_, which we denote by \(\mathbf{S}=\rho(g)\). Since \(\rho\) is a homomorphism, it is a linear map that preserves the products in \(\mathcal{A}\). Therefore, the image of any filter in \(\mathcal{A}\) can be written as a polynomial of the shift operators. Additionally,
the coefficients of such polynomials are the same used for the filter in \(\mathcal{A}\). For instance, if \(\mathcal{G}=\{g_{1},g_{2}\}\) and \(a=p(g_{1},g_{2})\), we have \(\rho(a)=p(\mathbf{S}_{1},\mathbf{S}_{2})\) where \(\mathbf{S}_{i}=\rho(g_{i})\).

## 3 Fourier decompositions of convolutional non commutative filters

The notion of Fourier decomposition in ASP is rooted in the concept of _decomposition in terms of irreducible subrepresentations_[1, 2, 15]. To see this, let us recall a few basic facts about ASM using concepts from representation theory of algebras. First, we emphasize that for any ASM, \((\mathcal{A},\mathcal{M},\rho)\), the pair \((\mathcal{M},\rho)\) constitutes a representation of \(\mathcal{A}\) in the sense of [22, 23]. Then, a representation \((\mathcal{U},\rho)\) of \(\mathcal{A}\) is a _subrepresentation_ of \((\mathcal{M},\rho)\) if \(\mathcal{U}\subseteq\mathcal{M}\) and \(\rho(a)u\in\mathcal{U}\) for all \(u\in\mathcal{U}\) and \(a\in\mathcal{A}\)[1]. A subrepresentation of \((\mathcal{M},\rho)\) can be obtained when one finds a subspace of \(\mathcal{M}\) invariant under the action of any operator \(\rho(a)\). Using this concept, we introduce the essential concept of irreducible representation. We say that \((\mathcal{M},\rho)\), when \(\mathcal{M}\neq 0\), is _irreducible_ or simple if the only subrepresentations of \((\mathcal{M},\rho)\) are \((0,\rho)\) and \((\mathcal{M},\rho)\). Finally, we state the notion of decomposition of a representation as a sum of other representations. Let \((\mathcal{U}_{1},\rho_{1})\) and \((\mathcal{U}_{1},\rho_{2})\) be two representations of \(\mathcal{A}\). Then, we can obtain a new representation called the _direct sum representation_, given by \((\mathcal{U}_{1}\oplus\mathcal{U}_{1},\rho)\), where \(\rho(a)(u_{1}\oplus u_{2})\cong\rho_{1}(a)u_{1}\oplus\rho_{2}(a)u_{2}\).

With these concepts at hand, we present the definition of Fourier decomposition that we will use for the frequency characterization of convolutional non commutative filters.

**Definition 1** (Fourier Decomposition [1]).: _For an algebraic signal model \((\mathcal{A},\mathcal{M},\rho)\), we say that there is a spectral or Fourier decomposition if_

\[(\mathcal{M},\rho)\cong\bigoplus_{(\mathcal{U}_{i},\phi_{i})\in\text{Im}r( \mathcal{A})}(\mathcal{U}_{i},\phi_{i}), \tag{1}\]

_where the \((\mathcal{U}_{i},\phi_{i})\) are irreducible subrepresentations of \((\mathcal{M},\rho)\). Any signal \(\mathbf{x}\in\mathcal{M}\) can be therefore represented by the map \(\Delta\) given by \(\Delta:\mathcal{M}\rightarrow\bigoplus_{(\mathcal{U}_{i},\phi_{i})\in\text{Im}r (\mathcal{A})}\mathcal{U}_{i}\), with \(\mathbf{x}\mapsto\hat{\mathbf{x}}\), known as the Fourier decomposition of \(\mathbf{x}\). The projection of \(\hat{\mathbf{x}}\) on \(\mathcal{U}_{i}\) is the \(i\)-th Fourier component of \(\mathbf{x}\) and is represented by \(\hat{\mathbf{x}}(i)\)._

Although abstract, Definition 1 offers a consistent, general and rigorous description of the Fourier transform under any ASM, which is independent from the domain of the signals. Additionally, from Definition 1, there are three fundamental observations in terms of the practicality of the Fourier decomposition and how to find it. First, the Fourier decomposition emphasizes a decomposition of the signals in terms of spaces that are invariant under the action of any \(\rho(a)\). Second, such minimum invariant subspaces are given by the irreducible subrepresentations of \((\mathcal{M},\rho)\). Third, the restriction of \(\rho(a)\) to each invariant subspace \(\mathcal{U}_{i}\) is determined by a homomorphism \(\phi_{i}(a)\) acting from \(\mathcal{A}\) to \(\text{End}(\mathcal{U}_{i})\). Additionally, the \(\phi_{i}(a)\) determine the Fourier representation of \(a\) in the \(i\)-th frequency component.

Note that Definition 1 is used for commutative and non commutative models alike. However, its instantiation in both scenarios have substantial differences. While for a commutative model \(\text{dim}(\mathcal{U}_{i})=1\), in non commutative models it must be that \(\text{dim}(\mathcal{U}_{i})>1\) for at least one \(i\)-th. This implies that the spectral representation of non commutative filters are characterized by matrix polynomials. To see this, let us consider the scenario where \(\mathcal{A}\) is non commutative with generator set \(\mathcal{G}=\{g_{1},g_{2}\}\). Since for at least one of the \(\mathcal{U}_{i}\) we have \(\text{dim}(\mathcal{U}_{i})>1\), the space of endomorphisms \(\text{End}(\mathcal{U}_{i})\) is a space of matrices of size \(\text{dim}(\mathcal{U}_{i})\times\text{dim}(\mathcal{U}_{i})\). Then, the Fourier representation of a filter \(a=p(g_{1},g_{2})\) is given by \(\phi_{i}(a)=p(\phi_{i}(g_{1}),\phi_{i}(g_{2}))\) which is a matrix polynomial where the independent variables are the matrices \(\phi_{i}(g_{1})\) and \(\phi_{i}(g_{2})\). The projection of \(\mathbf{x}\) on \(\mathcal{U}_{i}\), \(\hat{\mathbf{x}}(i)\), is the \(i\)-th Fourier component of \(\mathbf{x}\).

As pointed out in [9, 10], when the dimension of \(\mathcal{M}\) is finite, the problem of finding the Fourier decomposition of an ASM translates into solving a joint block diagonalization problem involving the shift operators. To see this, consider that \(\mathcal{A}\) has an arbitrary number of generators, \(m\), and let \((\mathcal{A},\mathcal{M},\rho)\) be an ASM with shift operators \(\{\mathbf{S}_{i}\}_{i=1}^{m}\), which have a joint block diagonalization given by \(\mathbf{S}_{i}=\mathbf{U}\text{diag}\left(\mathbf{\Sigma}_{1}^{(i)},\ldots, \mathbf{\Sigma}_{\ell}^{(i)}\right)\mathbf{U}^{T}\), with \(\mathbf{\Sigma}_{\ell}^{(i)}\in\mathbb{R}^{p_{j}\times p_{j}}\), and \(\mathbf{U}\) is orthogonal. Then, if we choose \(d=\max_{j}\{p_{j}\}\) and \(\mathbf{\Lambda}_{i}\in\mathbb{R}^{d\times d}\), we have that the Fourier representation of a filter \(p(\mathbf{S}_{1},\ldots,\mathbf{S}_{m})=\rho\left(p(g_{1},\ldots,g_{m})\right)\) is given by the matrix polynomial

\[p\left(\mathbf{\Lambda}_{1},\ldots,\mathbf{\Lambda}_{m}\right):\left(\mathbb{R}^{d \times d}\right)^{m}\rightarrow\mathbb{R}^{d\times d}, \tag{2}\]

where \(\left(\mathbb{R}^{d\times d}\right)^{m}\) is the \(m\)-times cartesian product of \(\mathbb{R}^{d\times d}\). To clarify the concepts discussed above, we present the following example.

**Example 1**.: Let \((\mathcal{A},\mathbb{R}^{3},\rho)\) be a non commutative ASM where \(\mathcal{A}\) has generator set \(\mathcal{G}=\{g_{1},g_{2}\}\) and where \((\mathcal{M},\rho)=(\mathcal{U}_{1},\phi_{1})\oplus(\mathcal{U}_{2},\rho_{2})\) with \(\text{dim}(\mathcal{U}_{1})=1\) and \(\text{dim}(\mathcal{U}_{2})=2\). Then, the Fourier representation of the filter \(p(g_{1},g_{2})=g_{1}+5g_{1}g_{2}+g_{2}^{2}\) is given by the matrix polynomial \(p(\mathbf{\Lambda}_{1},\mathbf{\Lambda}_{2})=\mathbf{\Lambda}_{1}+5\mathbf{ \Lambda}_{1}\mathbf{\Lambda}_{2}+\mathbf{\Lambda}_{2}^{2}\) where \(\mathbf{\Lambda}_{i}\in M_{2\times 2}\).
where \(\sigma_{\ell}\) is the composition between the pointwise nonlinearity, \(\eta_{\ell}\), and the pooling operator, \(P_{\ell}\). \(\mathcal{P}_{\ell}\) indicates a subset of filters, and \(\mathcal{S}_{\ell}\) is the set of admissible shift operators. We use the symbol \(\Phi(\mathbf{x}_{\ell-1},\mathcal{P}_{\ell-1},\mathcal{S}_{\ell-1})\) to emphasize that the filters used in the processing of the signal \(\mathbf{x}_{\ell-1}\) belong to the subset \(\mathcal{P}_{\ell}\subset\mathcal{A}_{\ell}\). The map associated with the whole AlgNN is \(\Phi\left(\mathbf{x},\{\mathcal{P}_{\ell}\}_{\ell}^{L},\{\mathcal{S}_{\ell}\}_ {\ell}^{L}\right)\) acting on an input signal \(\mathbf{x}\). We will use \(\{(\mathcal{A}_{\ell},\mathcal{M}_{\ell},\rho_{\ell};\sigma_{\ell})\}_{\ell=1}^ {L}\) to denote an AlgNN with \(L\) layers, emphasizing the convolutional model used in each layer, \((\mathcal{A}_{\ell},\mathcal{M}_{\ell},\rho_{\ell})\), and the map \(\sigma_{\ell}\).

## 5 Perturbations in Non Commutative Convolutional Models

The homomorphism, \(\rho\), in any ASM, \((\mathcal{A},\mathcal{M},\rho)\), instantiates or implements the filters in the algebra. Therefore, it is natural to consider perturbations as deformations on the homomorphism [1, 2]. In this context we say that \((\mathcal{A},\mathcal{M},\tilde{\rho})\) is a perturbed version of \((\mathcal{A},\mathcal{M},\rho)\), with the action of \(\tilde{\rho}\) given by

\[\tilde{\rho}(p(g_{1},\ldots,g_{m}))=p\big{(}\tilde{g}_{1},\ldots,\tilde{g}_{m }\big{)}=p\big{(}\tilde{\mathbf{S}}_{1},\ldots,\tilde{\mathbf{S}}_{m}\big{)}, \tag{4}\]

where \(\tilde{\mathbf{S}}_{i}=\mathbf{S}_{i}+\mathbf{T}(\mathbf{S}_{i})\) and \(\mathbf{T}(\mathbf{S}_{i})\) is a small diffeomorphism in the space of operators, such that the perturbation on the homomorphism acts as a perturbation on the shift operators. For our discussion, we consider perturbations of the form

\[\mathbf{T}(\mathbf{S}_{i})=\mathbf{T}_{0}+\mathbf{T}_{1}\mathbf{S}_{i}, \tag{5}\]

where the \(\mathbf{T}_{i}\) are fixed compact normal operators with \(\|\mathbf{T}_{i}\|\ll 1\) and \(\|\mathbf{T}_{i}\|_{F}\leq\delta\left\|\mathbf{T}_{i}\right\|,\) with \(\delta>0\).

When considering the perturbation of an AlgNN, we will use \(\{(\mathcal{A}_{\ell},\mathcal{M}_{\ell},\tilde{\rho}_{\ell};\sigma_{\ell})\}_ {\ell=1}^{L}\) to denote the perturbed version of \(\{(\mathcal{A}_{\ell},\mathcal{M}_{\ell},\rho_{\ell};\sigma_{\ell})\}_{\ell=1}^ {L}\). In this way, we emphasize that we consider perturbations for all convolutional operators in the network.

## 6 Stability Results

Taking into account the notion of perturbation/deformation introduced before, we now introduce the definition of stability considered under our analysis.

**Definition 2** ([1, 2]).: _Given filters \(p(\mathbf{S}_{1},\ldots,\mathbf{S}_{m})\) and \(p(\tilde{\mathbf{S}}_{1},\ldots,\tilde{\mathbf{S}}_{m})\) defined on the models \((\mathcal{A},\mathcal{M},\rho)\) and \((\mathcal{A},\mathcal{M},\tilde{\rho})\) respectively, we say that \(p\) is stable if there exist constants \(C_{0},C_{1}>0\) such that_

\[\Big{\|}p(\mathbf{S}_{1},\ldots,\mathbf{S}_{m})\mathbf{x}-p( \tilde{\mathbf{S}}_{1},\ldots,\tilde{\mathbf{S}}_{m})\mathbf{x}\Big{\|}\leq\] \[\left[C_{0}\sup_{\mathbf{S}_{i}\in\mathcal{S}}\|\mathbf{T}( \mathbf{S}_{i})\|+C_{1}\sup_{\mathbf{S}_{i}\in\mathcal{S}}\left\|D_{\mathbf{ T}}(\mathbf{S}_{i})\right\|+\mathcal{O}\left(\|\mathbf{T}(\mathbf{S}_{i})\|^{2} \right)\right]\|\mathbf{x}\|, \tag{6}\]

_for all \(\mathbf{x}\in\mathcal{M}\). In (6), \(D_{\mathbf{T}}(\mathbf{S})\) is the Frechet derivative of the perturbation operator \(\mathbf{T}\)._

To formally state the stability results, we need to first introduce definitions regarding subsets of filters in the algebra. To do so, we exploit the Fourier representation of the filters. We say that a filter \(p(g_{1},\ldots,g_{m})\in\mathcal{A}\) with Fourier representation \(p(x_{1},\ldots,x_{m})\) is \(L_{0}\)-Lipschitz if

\[\|p(x_{1},\ldots,x_{m})-p(\tilde{x}_{1},\ldots,\tilde{x}_{m})\|\\ \leq L_{0}\left\|(x_{1},\ldots,x_{m})-(\tilde{x}_{1},\ldots,\tilde{ x}_{m})\right\|, \tag{7}\]

for all \(x_{i}\), \(\tilde{x}_{i}\). Additionally, we say that \(p(g_{1},\ldots,g_{m})\) is \(L_{1}\)-integral Lipschitz if there exists \(L_{1}>0\) such that

\[\left\|\mathbf{D}_{p|x_{i}}(x_{1},\ldots,x_{m})\left\{(\cdot)\,x_{i}\right\} \right\|\leq L_{1}, \tag{8}\]

for all \(x_{i}\), where \(\mathbf{D}_{p|x_{i}}(x_{1},\ldots,x_{m})\) is the partial Frechet derivative of \(p(x_{1},\ldots,x_{m})\), and \(\|\cdot\|\) is the operator norm. We will denote by \(\mathcal{A}_{L_{0}}\) and \(\mathcal{A}_{L_{1}}\) the sets of \(L_{0}-\)Lipschitz and \(L_{1}\)-integral Lipschitz filters in \(\mathcal{A}\), respectively.

With these results at hand, we are ready to introduce our first stability result.

**Theorem 1** ([1]).: _Let \((\mathcal{A},\mathcal{M},\rho)\) be a non commutative ASM where \(\mathcal{A}\) has generators \(\{g_{i}\}_{i=1}^{m}\). Let \((\mathcal{A},\mathcal{M},\tilde{\rho})\) be a perturbed version of \((\mathcal{A},\mathcal{M},\rho)\) associated to the perturbation model in (5). If \(p\in\mathcal{A}_{L_{0}}\cap\mathcal{A}_{L_{1}}\subset\mathcal{A}\), the operator \(p(\mathbf{S}_{1},\ldots,\mathbf{S}_{m})\) is stable in the sense of Definition 2 with \(C_{0}=m\delta L_{0}\) and \(C_{1}=m\delta L_{1}\)._

Proof.: See [1]. 

Theorem 1 shows that one can find stable filters in non commutative convolutional models, and that stability is linked to the selectivity of the filters. More specifically, a reduction in the magnitude of \(L_{0}\) and \(L_{1}\) implies a reduction in the values of the stability constants, i.e. the filter is more stable. However, low values of \(L_{0}\) and \(L_{1}\) imply that the variability of the filter is reduced. In particular, a small value of \(L_{1}\) forces the filter to be flat for large frequencies. From these observations, we can see that although the non commutativity of the signal model substantially changes the nature of the Fourier representation of the filters (matrix functions instead of scalar functions), there is still a trade-off between selectivity and stability analog to that observed for commutative models.

Now, we state a stability result for the operator for an arbitrary layer of any non commutative algebraic neural network.

**Theorem 2** ([1]).: _Let \(\{(\mathcal{A}_{\ell},\mathcal{M}_{\ell},\rho_{\ell};\sigma_{\ell})\}_{\ell=1}^ {L}\) be an algebraic neural network and \(\{(\mathcal{A}_{\ell},\mathcal{M}_{\ell},\tilde{\rho}_{\ell};\sigma_{\ell})\}_ {\ell=1}^{L}\) its perturbed version by means of the perturbation model in (5). We consider one feature per layer and non commutative algebras \(\mathcal{A}_{\ell}\) with \(m\) generators. If \(\Phi\left(\mathbf{x}_{\ell-1},\mathcal{P}_{\ell},\mathcal{S}_{\ell}\right)\) and \(\Phi\left(\mathbf{x}_{\ell-1},\mathcal{P}_{\ell},\tilde{\mathcal{S}}_{\ell}\right)\) represent the \(\ell\)-th mapping operators of the AlgNN and its perturbed version, it follows that_

\[\Big{\|}\Phi\left(\mathbf{x}_{\ell-1},\mathcal{P}_{\ell},\mathcal{S}_{ \ell}\right)-\Phi\left(\mathbf{x}_{\ell-1},\mathcal{P}_{\ell},\tilde{ \mathcal{S}}_{\ell}\right)\Big{\|}\leq\] \[C_{\ell}\delta\|\mathbf{x}_{\ell-1}\|m\left(L_{0}^{(\ell)}\sup_{ \mathbf{S}_{i,\ell}}\|\mathbf{T}^{(\ell)}(\mathbf{S}_{i,\ell})\|\right.\] \[\left.+L_{1}^{(\ell)}\sup_{\mathbf{S}_{i,\ell}}\|D_{\mathbf{T}^{( \ell)}}(\mathbf{S}_{i,\ell})\|\right), \tag{9}\]

_where \(C_{\ell}\) is the Lipschitz constant of \(\sigma_{\ell}\), and \(\mathcal{P}_{\ell}=\mathcal{A}_{L_{0}}\cap\mathcal{A}_{L_{1}}\) represents the domain of \(\rho_{\ell}\). The index \(\ell\) makes reference to quantities and constants associated to the layer \(\ell\)._

Proof.: See [1]. 

From Theorem 2, we can observe that the map \(\sigma_{\ell}\), i.e. the composition between the point-wise nonlinearity and the pooling operator, scales the stability bound derived for the filters but does not affect its functional structure.
Now, we present the stability result for the operators that entirely characterizes any non commutative AlgNN.

**Theorem 3**.: _Let \(\left\{\left(\mathcal{A}_{\ell},\mathcal{M}_{\ell},\rho_{\ell};\sigma_{\ell} \right)\right\}_{\ell=1}^{L}\) be an algebraic neural network and \(\left\{\left(\mathcal{A}_{\ell},\mathcal{M}_{\ell},\tilde{\rho}_{\ell};\sigma_{ \ell}\right)\right\}_{\ell=1}^{L}\) its perturbed version by means of the perturbation model in (5). We consider one feature per layer and non commutative algebras \(\mathcal{A}_{\ell}\) with \(m\) generators. If \(\Phi\left(\mathbf{x},\{\mathcal{P}_{\ell}\}_{1}^{L},\{\mathcal{S}_{\ell}\}_{1 }^{L}\right)\) and \(\Phi\left(\mathbf{x},\{\mathcal{P}_{\ell}\}_{1}^{L},\{\tilde{\mathcal{S}}_{ \ell}\}_{1}^{L}\right)\) represent the mapping operator and its perturbed version, it follows that_

\[\left\|\Phi\left(\mathbf{x},\{\mathcal{P}_{\ell}\}_{1}^{L},\{ \mathcal{S}_{\ell}\}_{1}^{L}\right)-\Phi\left(\mathbf{x},\{\mathcal{P}_{\ell} \}_{1}^{L},\{\tilde{\mathcal{S}}_{\ell}\}_{1}^{L}\right)\right\|\\ \leq\sum_{\ell=1}^{L}\mathbf{\Delta}_{\ell}\left(\prod_{r=\ell}^ {L}C_{r}\right)\left(\prod_{r=\ell+1}^{L}B_{r}\right)\left(\prod_{r=1}^{\ell-1 }C_{r}B_{r}\right)\left\|\mathbf{x}\right\|, \tag{10}\]

_where \(C_{\ell}\) is the Lipschitz constant of \(\sigma_{\ell}\), \(\|\rho_{\ell}(a)\|\leq B_{\ell}\) for all \(a\in\mathcal{P}_{\ell}\), and \(\mathcal{P}_{\ell}=\mathcal{A}_{L_{0}}\cap\mathcal{A}_{L_{1}}\) represents the domain of \(\rho_{\ell}\). The functions \(\mathbf{\Delta}_{\ell}\) are given by_

\[\mathbf{\Delta}_{\ell}=\delta m\left(L_{0}^{(\ell)}\sup_{\mathbf{S}_{i,\ell} }\|\mathbf{T}^{(\ell)}(\mathbf{S}_{i,\ell})\|\ +L_{1}^{(\ell)}\sup_{\mathbf{S}_{i,\ell}}\|D_{\mathbf{T}^{(\ell)}}( \mathbf{S}_{i,\ell})\|\right), \tag{11}\]

_with the index \(\ell\) indicating quantities and constants associated to the layer \(\ell\)._

Proof.: See [1]. 

One of the fundamental observations from Theorem 3 is that the AlgNN can be stable to perturbations, and that stability is inherited from the convolutional filters. This is expected since the maps \(\sigma_{\ell}\) only scale the stability bounds derived for the filters. However, it is important to remark that while the stability bounds derived for filters, layer operators and AlgNNs are essentially the same (with appropriate normalization of \(C_{\ell}\) and \(B_{\ell}\)[1]), the discriminability power of each of these operators is substantially different. This is one of the aspects that explains why convolutional networks perform better than filter banks [1, 2]. Due to the fact that the AlgNN is enriched with point-wise nonlinearities for the same level of stability, AlgNNs are more stable than the corresponding convolutional filters. Additionally, notice that the redistribution of information in the frequency domain performed by \(\sigma_{\ell}\) occurs by mapping information between spaces of dimension larger than one.

## 7 Numerical Experiments

In this section, we demonstrate the stability properties of the non commutative filters employed in multigraph neural networks [9, 10]. Under the multigraph signal model, which is associated with the regular algebra of polynomials with multiple independent variables, the existence of subclasses of filters that are Lipschitz and Integral Lipschitz are guaranteed (Theorem 1). Therefore, it is possible to learn filters that can mitigate the effect of deformations on the shift operators. To do so, we train an architecture to learn filters using a cost function that adds a penalty based on the filter's Integral Lipschitz constants, and showcase that this model is much more resilient to perturbations enforced on the graph.

We consider the application of multigraph learning for a rating prediction task on the Jester dataset [24]. For our multigraph model, we consider two classes of edges connecting the jokes: one representing sentence similarity and the other modeling rating similarity amongst users in the training set. The multigraph is sparsified by keeping only the 20 strongest edges of each class per node. We arbitrarily selected the first joke for evaluating the performance of our predictions.

For our experiment, we compare the performance of a learned linear multigraph filter (MFilter), a multigraph neural network (MGNN), and another which is regularized by an estimate of the filter's Integral Lipschitz constant (MGNN IL). All architectures are composed of a convolutional layer with 3 filter taps and a readout layer mapping to a rating estimate. We report the root mean squared error (RMSE) and the standard deviation after training for 40 epochs across 5 random splits of the dataset.

To simulate stability towards estimation error of the shift operators, we first train each architecture on 90% of the training set. At evaluation, we replace the rating similarity shift operator with an estimate generated by a random subset of the training set ranging from 10% to 90% of the overall dataset and compare the difference in RMSE between the trained and evaluated models. As can be seen in Figure 2, the penalized MultiGNN consistently maintains the smallest difference in error for each size of the test set, demonstrating the most stability towards estimation error.

## 8 Conclusions

We leveraged algebraic signal processing (ASP) to model general non commutative convolutional filters and showed that neural networks built upon these models can be stable to deformations. The results obtained apply to existing architectures such as multigraph-CNNs, quaternion-CNNs, quiver-CNNs and non commutative group-CNNs. We proved that non commutative convolutional neural networks can be stable, which is an attribute inherited from the stability of the filters. This is due to the fact that the inclusion of pointwise nonlinearities and pooling operators only change the stability bounds derived for the filters by a scalar factor. The differences between the Fourier representations of non commutative and commutative filters lead to stability conditions that are different for both scenarios. While in commutative signal models the stability conditions are imposed on scalar valued functions, in non commutative models such conditions are imposed on matrix polynomials. We demonstrated that the polynomial representations in non commutative models exhibit a similar trade-off between stability and selectivity.

Figure 2: Results of the stability experiment.