Comments accompanying the rebuttal
**New paragraph referring to related work in the intro**
The goal of this paper is to extend the mathematical theory of GNNs to account for multimodal graph settings. The most closely related existing work is the algebraic neural network theory of Parada-Mayorga, Butler and Ribeiro [PMR1][PMR2][PMR3] who pioneer the use of algebras of non-commuting operators. The setting in this paper could be thought of as a special case of this theory. However, there is a crucial difference: whereas the main results in the articles above refer to the Hilbert-Schmidt norm, we introduce and analyze block-operator-norms on non-commutative algebras acting on function spaces. This choice allows us to prove stronger stability and transferability bounds that when restricted to classical GNNs improve upon or complement the state-of-the-art theory. In particular, we complement work in \cite{ruiz2021graph} by delivering bounds that do not exhibit no-transferable energy, and we complement results in \cite{maskey2023transferability} by providing stability bounds that do not require convergence. Our bounds are furthermore easily computable in terms of the networks' parameters improving on the results of~\cite{PMR2} and in particular allow us to devise novel training algorithms with stability guarantees.
**New writing of example 6:**
Fix $p\in (0,1)$ and let $W(x,y)=p$ for $x\neq y$ and zero otherwise. The graphon Erdos-Renyi graphs $G^{(n)}$ constructed from $W$ as in $(2)$ above are precisely the usual Erdos-Renyi graphs. Part (2) of the sampling Lemma guarantees that
$T_W$ converges to $T_{\hat{G}^{(n)}}$ almost surely in the operator norm. By contrast we will show that the sequence **does not converge** to $T_W$ in the Hilbert-Schmidt norm by proving that $\|T_{\hat{G}^{(n)}}(x,y)-T_W(x,y)\|_{\rm HS}>\min(p,1-p)>0$
almost surely. To this end note that for every $n\in \mathbb{N}$ and every $(x,y)\in [0,1]^2$ with $x\neq y$ the difference $|W_{\hat{G}^{(n)}}(x,y)-W(x,y)|\geq \min(p,1-p)$ since the term on the left is either $0$ or $1$. We conclude that
$\|T_{\hat{G}^{(n)}}(x,y)-T_W(x,y)\|_{\rm HS} = \|W_{\hat{G}^{(n)}}(x,y)-W(x,y)\|_{L^2([0,1]^2)}\geq \min(p,1-p)>0$
for every $n$ and therefore the sequence fails to converge to zero almost surely.
**Short Conclusion (to be added at the end of the article)**
In this paper, we introduce graph-tuple networks, a way of extending GNNs to the multimodal graph setting through the use tuples of non-commutative operators endowed with appropriate block-operator norms.
We show that GtNNs have several desireable properties such as stability to perturbations and a Universal transferability property on convergent graph-tuples, where the transferability error goes to zero as the graph size goes to infinity.
Our transferability theorem improves upon the current state even for the GNN case.
Furthermore our error bounds are expressed in terms of computable quantities from the model.
This motivates our novel algorithm to enforce stability during training.
Experimental results show that our transferability error bounds are reasonably tight, and that our algorithm increases the stability with respect to graph perturbation.
In addition, they demonstrate that the transferability theorem holds even for sparse graph tuples.
Finally, the experiments on the movie recommendation system suggest that allowing for architectures based on GtNNs is of potential advantage in real-world applications.