Graph neural networks and non-commuting operators
Authors: Mauricio Velasco
Kaiying O'Hare
Bernardo Rychtenberg
Soledad Villar
Venue: NeurIPS 2024 poster (2024)
Keywords: graph neural networks
trasferability
stability
non-commuting operators
graphons
Primary area: graph_neural_networks

Abstract: Graph neural networks (GNNs) provide state-of-the-art results in a wide variety of tasks which typically involve predicting features at the vertices of a graph. They are built from layers of graph convolutions which serve as a powerful inductive bias for describing the flow of information among the vertices. Often, more than one data modality is available. This work considers a setting in which several graphs have the same vertex set and a common vertex-level learning task. This generalizes standard GNN models to GNNs with several graph operators that do not commute. We may call this model graph-tuple neural networks (GtNN). 

In this work, we develop the mathematical theory to address the stability and transferability of GtNNs using properties of non-commuting non-expansive operators. We develop a limit theory of graphon-tuple neural networks and use it to prove a universal transferability theorem that guarantees that all graph-tuple neural networks are transferable on convergent graph-tuple sequences. In particular, there is no non-transferable energy under the convergence we consider here. Our theoretical results extend well-known transferability theorems for GNNs to the case of several simultaneous graphs (GtNNs) and provide a strict improvement on what is currently known even in the GNN case.

We illustrate our theoretical results with simple experiments on synthetic and real-world data. To this end, we derive a training procedure that provably enforces the stability of the resulting model.

Graph neural networks and non-commuting operators
Mauricio Velasco
Kaiying O'Hare
Departamento de Informática
Departament of Applied Mathematics and Statistics
Universidad Católica del Uruguay
Johns Hopkins University
Montevideo, Uruguay mauricio, velasco@ucu, edu.uy
Baltimore, Maryland
kohare30jh. edu
Bernardo Rychtenberg
Soledad Villar
Departamento de Informática
Departament of Applied Mathematics and Statistics
Universidad Católica del Uruguay
Johns Hopkins University
Montevideo, Uruguay
Baltimore, Maryland svillar3a hu edu
bernardo hww.aardd.rychteeberreeeeeee edu.uy
Abstract
Graph neural networks (GNNs) provide state-of-the-art results a wide variety of tasks which typically involve predicting features the vertices of graph. They are built from layers of graph convolutions which serve as powerful inductive bias than
for describing the flow of information among the vertices. Often, data modality is available. This work considers a setting in which several graphs have the vertex set and common vertex-level learning task. This generalizes standard GNN models to GNNs with several graph operators that do not commute. We may call this model graph-tuple neural networks (GtNN).
this work, we develop the mathematical theory to address the stability and transferability of GtNNs using properties of non-commuting non-expansive op- erators. We develop limit theory of graphon-tuple neural networks and use it prove universal transferability theorem that guarantees that all graph-tuple neural networks are transferable on convergent graph-tuple sequences. In particular, there is no non-transferable energy under the convergence we consider here. Our theoretical results extend well-known transferability theorems for GNNs to the case of several simultaneous graphs (GtNNs) and provide strict improvement what is currently known even in the GNN case.
We illustrate our theoretical results with simple experiments synthetic and real- world data. To this end, we derive a training procedure that provably enforces the stability of the resulting model.
Introduction
Graph neural networks (GNNs) 45
are a widely-used and versatile machine learning tool to process different kinds of data from numerous applications, including chemistry [15), molecular geometry [48), combinatorial optimization 21 [36.. among many other. Such networks act on functions the vertices of graph (also called signals vertex features) and the structure of the graph as a powerful inductive bias to describe the natural flow of information among vertices. One of the most common graph neural networks are based on graph convolutions [4], which generalize the notion of message passing. The typical architecture has building blocks which are polynomial functions of the adjacency matrix (or more generally of the shift operator) of graph composed with componentwise non- -oneiinarsiies. Therefore, such networks implement the idea that the values of
S
24 16
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

function at vertex are related with the values at the immediate neighbors of the vertex and also with the values at the neighbors of its neighbors, etc.
Due to the significant practical success and diversity of applications of GNNs, there is a growing interest in understanding their mathematical properties. Researchers have delved into various theoret- ical aspects of MPNNs, including, for instance, expressivity [35 47 9 g oversmoothing [44], multi-scale properties
and model relaxations [12 17. One of the fundamental properties of graph neural networks is their remarkable transferability property, which intuitively refers to their ability to perform well in large networks when trained in smaller networks, thus transfering knowledge from one to the other. This is in part possible because the number of parameters that defines a GNN is independent of the size of the imput graphs. The idea conceptually related the algebraic notion of representation stability that has been recently studied in the context of machine learning models 28 More precisely, if two graphs describe similar phenomena, then a given GNN should have similar repercussions (i.e. similar effect on similar signals) on both graphs. In order to describe this property precisely, it necessary to place signals and shift operators on different graphs (of potentially different sizes) in an equal footing to allow for meaningful comparisons and to characterize families of graphs describing "similar" phenomena. The seminal work [40] has used the theory of graphons to carry out these two steps, providing solid theoretical foundation to the transferability properties of GNNs. The theory was further developed in [27 41 32 23
[18] 5
10], and was extended to other models in 66 26 43 The transferability theory is very related to the stability or perturbation theory of GNNs that studies how GNN outputs change under small perturbations of the 3 22), and conceptually related to the theory of generalization though the techniques are different.
graph input graph signal 42
for GNNs 46
29 33
31
In many practical situations fixed collection of entities serves as common vertices to several distinct graphs simultaneously that represent several modalities of the same underlying object. This occurs, for instance, in recommendation systems where the items can be considered vertices of several distinct similarity graphs. It occurs in the analysis of social networks because individuals often participate in several distinct social/information networks simultaneously and in a wide array of multimodal settings.
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 38 37 4
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 crucial difference: whereas the main results in the articles above refer to the Hilbert-Schmidt norm, we define and analyze boock-operator-nooe 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-a art theory. particular, we complement work in 42 by delivering bounds that do not exhibit no- no-transferable energy, and we complement results in 32 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 (37] and in particular allow us to devise novel training algorithms with stability guarantees.
Our contributions. The main contribution of this work is a theoretical analysis for graph neural networks the multimodal framework where each graph object (or graph tuple) can have several adjacency matrices on fixed set of vertices. We call this model graph-tuple neural networks (GINNs). generalizes GNNs and is naturally suited for taking into account information flows along paths traversing several distinct graphs. This architecture replaces the polynomials h(X) underlying graph convolutional neural networks with non-commutative polynomials (X on the adjacency matrices of the k graphs in tuple. More generally our approach via operator networks gives a general and widely applicable parametrization for such networks. Our approach is motivated by the theory of switched dynamical systems, where recent algorithmic tools have improved our understanding of the iterative behaviour of non-commuting operators 34 Our main results are tight stability bounds for GtNNs and GNNs.
The second contribution of this article is the definition of graphon-tuple neural networks (WtNNs) which are the natural limits of (GtNNs) as the number of vertices grows to infinity. Graphon-tuple neural networks provide a good setting for understanding the phenomenon of transferability. Our main theoretical result is Universal transferabiliry Theorem for graphon- graph transference which guarantees that every graphon-tupp neural network (without any assumptions) is transferable over
2

---

sequences of graph-tuples generated from given graphon-tuple. This means that whatever a GINN learns on graph-tuple with sufficiently many vertices, instantaneously transfers with small error to all other graph-tuples of sufficiently large size provided the graph-tuples we are considering describe a "similar" phenomenon in the sense that they have a common graphon-tuple limit. Contrary to some prior results, under the convergence we consider in this paper, there is no no-transferable energy, meaning that the graphon-graphe transferability error goes to zero as the size of the graph goes to infinity.
We show with simple numerical experiments that our theoretical bounds seem tight. In Section 7 we provide experiments on synthetic datasets and real-world movie recommendation dataset where two graphs are extracted from incomplete tabular data. The stability bounds we obtain are within a small factor of the empirical stability errors. And remarkably, the bounds exhibit the same qualitative behavior as the empirical stability error. In order to perform this experiment we introduce a stable training procedure where linear constraints are imposed during GNN training. The stable training procedure could be considered of independent interest (see, for instance, 7
2 Preliminary definitions
For an integer n we let [n] := {1, (1, n). graph without self-loops with vertex set V(G)= V and edge set denoted E(G). A shift matrix for G is any V symmetric matrix S with entries S S.y I satisfying Si = 0 whenever i + and (1,5) & E(G).
By a graph G on a set V we mean an undirected, finite
Our main object of study will be signals (i.e. functions) on the common vertices V of set of graphs so we introduce notation for describing them. We denote the algebra of real-valued functions on the vertex set V by R [V]. Any function f V - R is completely determined by its vector of values so, will see later, thinking of this space consisting of functions is key for understanding the neural networks we consider. Any shift matrix S for G defines a shift operator To [[]] + [V] by the formula To (f) = Ejev Si).()).
as vector space, R [V[] = RIV however,
The layers of graph neural networks (GNNs) are built from univariate polynomials h(x) evaluated on the shift operator TG of a graph composed with componentwise non-linearities. If we have a k-tuple of graphs .... Gg with common vertex set V then it is natural to consider multivariate polynomials evaluated at their shift operators TG.. Because shift operators of distinct graphs generally do not commute this forces us to design an architecture which is parametrized by noncommutative polynomials. The trainable parameters of such networks will be the coefficients of these polynomials.
Noncommutative polynomials. For a positive integer k. let R(X,,..., Xx) be the algebra of non-come con-commuteeeve polynomials in the variables XI...., Xx. This is the vector space having as basis all finite length words the alphahet X1,--., Xx endowed with the bilinear product defined by concatenation on the basis elements. For example in (X1,,, X2) we have (X1 + X2)² = X + X, + X2X, + X? # X7 + 2X,X++
The basis elements appearing with nonzero coefficient in the unique expression of any element h(X,.... X²) are called the monomial words of h. The degree of monomial word is its length (i.e. number of letters). For example there are eight monomials of degree three in IR (X,,, 11, X2), namely: x3, X2X,, X2X,, N.xXXXX3xx X2X, X2, X,33 X3. More generally there are exactly kd k-1 monomial words of degree at most d in (X,,...., Xx)).
monomial words of length d and bd+1
Noncommutative polynomials have a fundamental structural relationship with linear operators which makes them suitable for transference. If W is any vector space let End( W) denote the space of linear maps from W to itself. Ti. T& E (W) are any set of linear maps on W then the individual evaluations X; T; extend to unique evaluation homomorphism 2(.1..... Xx) which sends the product of polynomials to the composition of linear maps. This relationship (known as universal freeness property) determines the algebra R(X,.... ........ X₂) uniquely. This proves that noncommutative polynomials are the only naturally transferable parametrization for our networks. For polynomial h we denote the linear map obtained from evaluation I(T)...., TTk).
+ End( W),
Operator filters and commuuin operator neural networks. Using noncommutative polyno- mials we will define operator networks, abstraction of both graph and graphon neural networks.
3

---

Operator networks will provide us with a uniform generalization to graph-tuple and graphon-tuple neural networks and allow us to describe transferability precisely.
The domain and range of our operators will be powers of a fixed vector space F of signals. More formally, F consists of real-valued functions measure turns F into an inner product space (see [25] Chapter 2] for background) via the formula (f.g) : Jv fgduy and in particular gives it natural norm II := (ff.f)) which we will use throughout the article. In later sections the set F will be either [V] or the space I. == ([0, 1]) of square integrable functions in [o. 1] but operator networks apply much more generally, for instance to the spaces of functions on manifold V used in geometric deep learning 12]. By operator k-tuple on F we mean sequence T (Ti..... .T) of linear operators T} F - F. The tuple is nonexpansive if each operator T, has norm bounded above by one.
fixed domain V endowed with measure µvy The
If h E R(..,...., X&) is noncommutative polynomial then the operator filter defined by h. Ea ca and the operator tuple T is the linear operator (h, T) F - F given by the formula
h(Tr..... (f) = Xa [T.. (f)
where X"( Tk) is the composition of the T, from left to right in the order of the word For instance if ( X2) )-== == -5 + 3x3 then the graph-tuple filter defined by h applied to signal E is Th,, (f) (T) (TT(( (T)))
More generally, we would like to be able to manipulate several features simultaneously (i.e. to manipulate vector-valued signals) and do so by building block-linear maps of operators with blocks defined by polynomials. More precisely. if A, B are positive integers and H is a B A matrix whose entries are non-commutative polynomials ha.a E (R,,,...... Xx) we define the operator filter determined by H and the operator luple T to be the linear map (HHTT) JA FB which sends vector z = (Ia)aE[A) to a vector (2b) using the formula
26
Σ aE[A]
hs, (T (x)
An operator neural layer with ReLU activation is operator filter composed with a pointwise non-linearity. This composition a Te (H,T) T) yields (nonlinear) map ( T): F + F
Finally an operator neural network (ONN) is the result of composing several operator neural layers. More precisely if we are given positive integers ag...., Cny and N matrices HO) of noncommutative polynomials H[[ == 1 (X....., for (b, a) E [aj+a] x [ay] and j = O..... N 1, the operator neural network (ONN) determined by 11 := ( and the operator tuple T is the composition F + F + ..... ....... Foy where the j-th map in the sequence is the operator neural layer with Relu activation (H()),, Fo, + Fa;-1. We write Φ(H T) Fou + Foy to refer to the full composite function. See Appendix [A] discussion on the trainable parameters and the transfer to other k-tuples, We conclude the Section with key instance of operator networks:
An Example: Graph-tuple neural networks (GtNNs). Henceforth we fix positive integer k, a sequence Gi....; : G2 of graphs with common vertex set and given set of shift operators To.....,Te: We call this information a graph-tuple G == (GI,..., G&) on V.
The graph-tuple filter defined by noncommutative polynomial l(X,,.... Xx) E E( X and Ō is the operator filter defined by h evaluated π (Ta,..... Ta,) denoted (h T) V + R[V]. Exactly as in Section and using the notation introduced there, we define graph-tuple filters, graph-tuple neural layers with ReLu activation and graph-tuple neural networks (GtNN) on the graph-tuple G as their operator versions when evaluated the tuple T above.
3 Perturbation inequalities
In this Section we introduce our main tools for the analysis of operator networks, namely perturbation inequalities. To speak about perturbations we endow the Cartesian products F with norms
||
max aE[A]
|| 1zal if = (za)aE(A) E F

---

where the norm on the right-hand side denotes the standard L -orm on F coming from the measure Ho as defined in the previous section. Fix feature sizes ag. ......,,,, aN and matrices ag....,
1 = (11 =N....N- of noncommutative polynomials in k-variables of dimensions 0j+1 x aj for j = 0 0...,, 1 and consider the operator-tuple neural networks (HH,T) F + F defined by evaluating this architecture k-tuples T of operators on the given function space F. A perturbation inequality for this network is an estimate on the sensitivity (absolute condition number) of the output when the operator-tuple and the input signal are perturbed in their respective norms, more precisely perturbation inequalities are upper bounds on the norm
+ Hr, W) ( H 2 (g)
terms of the input signal difference ||ʃ |1 and the operator perturbation size as measured by
the differences Z Wyllop. The main result of this Section are perturbation inequalities that depend on easily computable constants, which we call expansion constants of the polynomials appearing the matrices 17, allowing us to use them to obtain perturbation estimates for a given network and to devise training algorithms which come with stability guarantees. A key reason for the success of our approach is the introduction of appropriate norms for computations involving block-operators: A, B are positive integers and (Ea)ae[A) E FA and R: F + F is linear operator then define
R
sup
[1(2)]
(2)
op
=:||=||
If R .x)) is any noncommutative polynomial then it can be written uniquely as E. Cax" where runs over a finite support set of sequences in the numbers I..... k. For any such polynomial we define a set of k + expansion constants via the formulas
C(h) : Σ |cal and Cy(h) =
Σ (s(a]]cal for = =.j=,..... I....,k
where 9; (a) equals the number times the index j appears in a. Our main result is the following perturbation inequality, which proves that expansion constants estimate the perturbation stability of nonexpansive operator-tuple networks (i.e. those which satisfy [Tyllop S for = l,....))).
Theorem 1. Suppose W and Z are nonexpansive operator k-tuples For positive integers A, B let H be any A matrix with entries in RX. Xx). The operator-tuple neural layer with Relu activation defined by H satisfies the following perturbation inequality: For any J,g E FA and for m min()
19
we have
(((H,W)() (H, ((H,Z))()
IIf - 911
max DE[B]
C(ho.a)
+ m max
Σ E 4E 1=1
Cho,,)))l,, - Zzllop
(3)
BE[B]
[A(A]
The proof is in Appendix We apply the previous argument inductively obtain perturbation inequality for general graph-tuple neural networks by adding the effect of each new layer to the bound. More concretely if ag.... ... aN denote the feature sizes of such network and Rw and Rz denote the network obtained by removing the last layer then
Corollary 2.
Let m == min
( (1) |R
The end-to-end graph tuple neural
network satisfies the following perturbation inequality:
( W))) (H, (o)l S
|Ry (f) (g(g))
max
Σ
C(1 (N--1)
+m max
Σ Σ
- Esllop
[E[NN]
DE(
oE(an-1)-=1
(4)
5

---

Corollary 3 below shows that constraining expansion constants allows us to design operator-tuple networks depth N whose perturbation stability scales linearly with the network depth N.
Corollary 3. Suppose W and are two nonexpansive operator k-tuples. If the inequality
max bE(ag-11
Σ
(
1
holds for j = .,....N
N - then m (ll
we have:
- (g)ll 111
max
Σ
Zzllop- (5)
bE(04+1]
ac/ool j=l
Graphons and graphon-tuple neural networks (WtNNs).
In order to speak about transferability precisely, we have to address two basic theoretical challenges. On one hand we need to find a space which allows us to place signals and shift operators living on different graphs in equal footing in order allow for meaningful comparisons. On the other hand objects that are close in the natural norm in this space should correspond to graphs describing "similar" phenomena. As shown in 41, both of these challenges can be solved simultaneously by the theory of graphons. A graphon is a continuous generalization of graph having the real numbers in the interval [0. 1] as vertex set. The graphon signals are space of square-integrable functions on [0, 1]. that is I, == 1,2 1)). In this Section we give a brief introduction to graphons and define graphon-tuple neural networks (WINN), the graphon counterpart of graph-tuple neural networks. Our first result is Theorem 4 which clarifies the relationship between finite graphs and signals on them and their induced graphons and graphon signals respectively allowing us to make meaningful comparisons between signals graphs with distinct numbers of vertices. The space of graphons has two essentially distinct natural norms which we define later in this Section and review in Appendix B Converging sequences under such norms provide useful models for families of "similar phenomena" and Theorem 5 describes explicit sampling methods for using graphons as generative models for graph families converging in both norms.
Comparisons via graphons. graphon a function W [0. 1] x 1] - [0. 1] which is measurable and symmetric (i.e. W W(u,r) W W(v, w)). A graphon signal is function I E T. (,2 1)). The shift operator of the graphon W the map Tw L - given by the formula
[ ((,,))(())) u)f(v)de
Tw Tw())
where de = du(() denotes the Lebesgue measure y in the interval [].
A graphon-tuple WI...., WA consists of a sequence of k graphons together with their shift operators Tw, T. T.. Exactly as Section 2 and using the notation introduced there, we define (A, B) graphon-tuple filters, (A, B3) graphon-tupp tuple neural layers with ReLu activation and graphon- tuple neu- ral networks (WINN) as their operator versions when evaluated at the k-tuple W := (Tw...... Tw.)).
For instance, if we are given positive integers og...., AN and matrices H with entries given by noncommutative polynomials H(1) == (1) E IE(,,...,,X, for (b, a) [aj+1] [ay] and j ... N 1, the graphon-tuple neural network (WINN) defined by H = (H N-1 and W will be denoted by ( W) L + LaN
Next we focus on the relationship between (finite) graphs and graphons. Our main interest are signals (i.e. functions) on the common vertex set V of all the graphs which we think of as discretization of the graphon vertex set [0, 1]. More precisely, for every integer n we fix collection
of n intervals (n)) := |_-1_ 2) covering [0, 1) and vertices by
2j-1 E Iy which constitute
the set (m)) C [0, 1].
To compare functions different (m) we will use interpolation operator i, and sampling operator Pn. The interpolation operator i, [n) + L extends set of values at the points of (n)

---

to piecewise-constant function in [0. 1] via (n) = Ei (o where 1 2 (xx denotes
the (0. }} characteristic function of the set Z. The sampling operator pr, I. R((()) maps function its conditional expectation with respect to the 1 namely the function g R[V(n) given by the formula g(0;) :- J1, f(w)do/((L) = J1, f(v)do. The sampling and interpolation operators satisfy the identities Ps. hn idz[v(n)) and i, (Pn(()) is the piecewise function which each interval I has constant value equal the average of on I,. Note that in o pf) approaches any continuous function ʃ as + 00.
Any graph G with vertices and shift matrix Sy [0, induces (piecewise constant) graphon Wg. The graphon induced by G is given by the formula
11
Wc(2,8)
(1))))))
The following Theorem clarifies the relationship between the shift operator of a graph and that of its induced graphon and how this basic relationship extends to neural networks. Part (2) will allow us to compare graph-tuple neural networks on different vertex sets by comparing their induced graphon-tuple networks (the proof is in Appendix C
Theorem 4. For every graph-tuple G1....: Gk on vertex set V(n) and their induced graphons W == Wa, the equality
To T1
Tw, = in
Pr.
holds. Moreover, this relationship exlends to networks: given feature sizes . ON and matrices HD) of noncommutative polynomials having no constant term and of compatible dimensions 0x+11 x aj for .,...,N 1 the graphon-tupp tuple neural network 4 [,, W) L + L and the normalized graph-tuple neural network & (HH, G/n) VV - [V[aaa satisfy the identity
& (HH = (HH,TT/n)) Pr.
where Pn and in are applied to vectors componentwise.
Graphon norms. The space of graphons is norms. In aefiiitedimmnsiine. spaces it is customary speak about equivalent norms, meaning pairs that differ by multiplication by a constant, but also about the coarser relation of topologically equivalent norms (two norms topologically equivalent if sequence converges in one if and only it converges in the other). Here we describe two specific norms interest and describe explicit mechanisms for producing converging sequences in the operator norm.
and therefore allows for several
U.V Juxv W(u, v dddud Known as Ml
The most fundamental norm on graphons is |Wllo == sup
the cut norm, its importance stems from the fact that graphons differing by small cut norm must have similar induced subgraphs in the sense of the counting Lemma Lovasz and Szegedi (see 30 Lemma 10.23] for details).
As an analytic object however, the cut norm is often unwieldy, so typically bounded via more easily computable norms. More precisely, the space of graphons admits two topologically inequivalent norms represented by the operator and Hillert-Schmiin norms of graphon shift operators respectively (Example 6 shows that they indeed inequivalent and why this is important in the present context).
Recall that the operator is defined by ||T == sup J' 1'' W(u, v)f(w)g(v)dddd which
1 1
the induced norm of Tw as operator from ([0 1)) to ( 1)). is topologically equivalent to the cut norm (see Appendix B). The Hilbert--chmiit (HS) norm of Tw is the norm of the eigenvalues of Tw or equivalently the norm ||W|| r thinking of W as a function in the square.
Graphons as generative models. Given a graphon W we explicitly construct families of graphs of increasing size which have W limit. The family associated to graphon provides practical realization of the intuitive idea of a collection of graphs which "represent common phenomenon".
7

---

Explicitly constructing such families is of considerable practical importance since they provide us with a controlled setting in which properties like transferability can be tested experimentally over artificially generated data.
Assume W(a (a: y) is given graphon. For every integer n. we fix finite set of equispaced vertices as above and a collection of intervals 1 := [ey, 1/-1) for j = I,..., - 1 and In := [0, v1) U [en, 1].
We will produce two kinds of undirected graphs with vertex set V(n) := fU1..... )
1. A deterministic weighted graph, the weighted template graph H, with vertex set ((n) and shift operator S(s, = Iii,,,, W Waaaydddyy on the edge (vi, Uz).
((lxx1))
2. A random graph, the graphon-Frdos- Renyi graph G2 with vertex set V(n) and shift operator S (1g E {0. 1} sampled from a Bernoulli distribution with probability W(s,, By), which is independent for distinct pairs of vertices.
The main result in this Section is that, under mild assumptions on the function W, the weighted template graphs and the random graphon-Erdos- Renyi have induced shift operators converging to Tw in suitable norms (see Appendix C for proof). Note that the second part of the theorem can be seen consequence of the analysis
32 as well.
Theorem 5, For any positive integer n let ( and ((n) be the graphons induced by H and Gu- The following statements hold
1. If W is continuous then [Tw T B8o0 lls + +0
2. ISW is Lipschitz continuous then 1/T - Tarm; llop + 0 almost surely.
Example 6. Fix E (0,1) and let W W(x, y) = for x + 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. Theorem 5 part (2) guarantees that ||Tw - -Tgu. 1lop - 0 almost surely so this is a convergent graph family in the operator norm. By contrast we will show that the sequence of ((t))
does not converge to Tw in the Kilbeet-Schmiin norm by proving that [[Tgu)) (x. - Tw (zt, y) ||] HS > min(p, 1 p) > [0. 1]2 with + the difference |W (z. y) - W(x, y)1 2 min(p, 1 p) since the term on the left is either 0 or 1. We conclude that (Te (xz, 3/) Tw (2, lns = [[ (I, y) (D)-Wir (xx, y) v)llza(0.17)) 2 min(p, 1-11-11 p) > O for every n and therefore the sequence fails to converge to zero almost surely.
almost surely. To this end note that for every n E N and every (x. y)
The previous example is important for two reasons. First it shows that the operator and Hilbert- Schmidt norm are not topologically equivalent in the space of graphons. Second, the simplicity of the example shows that for applications to transferability, we should focus on the operator norm. More strongly, it proves that trasferability results that depend the Hilbert-Schmidt norm applicable even to the simplest families of examples, namely Pedos--Reni graphs.
5 Universal transferability
Our next result combines perturbation inequalities for graphon-tuple networks and Theorem which compares graph-tuple networks and their induced graphon-tuple counterparts resulting in transferability inequality. As a corollary of this inequality we prove universal transferability result which shows that every architecture is transferable in converging sequence of graphon-tuples in the sense that the transferability error goes to zero as the index of the sequence goes to infinity. This result is interesting and novel even for the case of graphon-graph transferability (i.e. when k = 1).
Theorem 7. Let W be a graphon-tuple and let Ō be a graph-uppl with equispaced vertex set LA V C. [0, 1]. Let H be any B x A matrix with entries in IR (XI...... Xx) and let ( W) LA + L (resp (HH G): R[V] + R(V) denote the graphon-tupp tuple neural layer (resp. graph-tuple neural layer) with ReLu activation defined by H. If G. denotes the graphon induced y G, then for every
8

---

f E L the transferability error for satisfies
((H,TWW)() iv o V H, |
_ To (ov(l))
|/ - iv
max bE
C(hraa
max + +IIlI
C,0hn,)llT,, Te, llp s-
Σ Σ
ME
We are now able to prove the following Universal transferability result:
Theorem 8. Suppose G(V) == (G( . is sequence of graph-tuples having vertex set V(N) S [0, 1]. If the veriex set is equispaced for every N and the sequence converges to graphon-tuple W the sense that a Tw, Wool 0 as 20 for -,..., k then every
graphon-tuple neural network on W transfers. More precisely, for every neural network architecture Tb (H, o) and every essentially bounded function f E [10, 1]) the quantity
T ((H,Tw))(F) ivvcn) + (H, (H.IiiN)
1 To (pvCNo (f))
converges zero N - oc. Furthermore the convergence is uniform among functions with fixed Lipschitz constant.
Training with stability guarantees
Following our perturbation incqualities (i.c., Theorem ! and Corollary 3 propose training
algorithm to obtain a GINN that enforces stability by constraining all the expansion constants C(h)
and (h). Consider a GtNN & [, To) and nonexpansive operator k- k-tuples Tc. Denote the set of + expansion constants for each layer O.....N as
C(H(d)= = max
Σ C(1(a)) and C2(H(()) = max aE(oal
Σ
hga for -,...,k k
bE (a(++))
bE(0 DE[oa]
and write C(A) = (C(H)())) and ()) (C,((L( for j I,.... Given & + vectors of target bounds Č = (C and C := (c(a) ya= for = =1 1,.... k and training data (1r4s v.) Fou Fux for E 1, train the network by constrained minimization problem
(( (C), s.t. C(i(C)) S C,(ū(()) s Õ3 for j = ,....,k,
min
EET
where ((:-)) is any nonnegative loss function depending the task, and denotes all the polynomial coefficients in the network. we pick Č be an all ones vector (or smaller), by Corollary the perturbation stability is guaranteed to scale linearly with the number of layers N.
To approximate the solution of the constrained minimization problem
a penalty method,
min 1 Σ (((((()),
k -) +)
App(
Σ pl ( - (6)
1 VET
where p(-) is a componentwise linear penalty function p(O) = (p(Ctt))) with p(C(d) = ma C(d)). The stable GINN algorithm picks fixed large enough penalty coefficient and trains the network with local optimization methods.
7 Experimental data and numerical results
We perform three experiments (1) we test the tightness our theoretical bounds on a simple regression problem synthetic dataset consisting of two weighted circulant graphs (see Figure
'Code available: (tw.e//www.....///........o.///a and antlttt:://github.cm
www.aahteeeeiirrllaatt.tttttttot ggrahss

---

GINN: CUN)
GINN: 1PC77
output porturtsatos
30
unttle case (ooW-n hou
GINN: C1n1
stable GLNN: [A
20-
Tobbiity
10-
GAN
stable caNM
2000
4000
6000
2000
4000
6000
0.0
0.4
0.6
opocns
spochs
grapp perturbation
Figure 1: We assess the tightmess of our theoretical results on regression problem on a synthetic data toy example consisting of two weighted circulant graphs. See Appendix [.1 for details. (Left) Numerical stability hound (hh) (dashed) and stability metrics [[h(T))] (solid) with respect to input signal perturbation as a function of the number of epochs for both the standard (1-layer) GtNN (orange) and (1-layer) stable GtNN (blue). (Middle) Similar plot for the stability metrics with respect to the graph perturbation [[ - h( o()) and its upper bound (Lemma 12 part and 3b). For this plot we take W T. and Ž is a random perturbation from 7 with 21 - Wallop 1 Wallop 0.33. (Right) For all four models, compute the 2-norm of the vector of output perturbations from Equation ① over the test set for various sizes graph perturbation (ITT- - W op + |72 ///, where the additive graph perturbation Ti Wi and 722 - W2 are symmetric matrices with iid Gaussian entries. In addition, each Tj and W, are normalized such that [[T] S and |[Wlllo for j 2, so they are nonexpansive operator-tuple networks. (All) We observe that adding stability constraints does not affect the prediction performance: the testing R squared value for GINN is O. 0.6866,
while for stable GtNN is 0.6543.
CMP (0____00_11100000
CMV
0.78
CMV reg 0.5 COs
075-
2CNU anc 0.175 00x
074-
0.30
0.7
0.33
0.38
0:22
CNL /90 01 COS
0.53
0.72
2CNU 0.0 000
0.54
8.70
200
200
6003
1700
Figure 2: This is an experiment on the MovieLens 100k database, collection of movic ratings given by a set of 1000 users [39] to 1700 movics. Using collaborative filtering techniques [19 we extract weighted graphs that we
predict ratings of movies by user from held out test set. See details in Appendix [D.3] We report the mean squared error (MSE) the test set as a function of the number training iterations (Left) from O to 500 and (Right) from O to 1500 for the movie recommendation system experiments. We compare the two models GtNN on the tuple of two graphs (2ONN) and GNN on the best single graph between those two (GNN) various ridge-regularized versions (the legend contains the values of the chosen regularization constants).
T and Appendix D for details) (2) we assess the transferability of the same model (A (Appendix D.2p. and (3) we run experiments the information is summarized in two graphs via collaborative filtering approaches [19] and it is combined to infer ratings by new users via the GtNN model (see Figure 2 and Appendix D.3
real-world dataset of movie recommendation system where
Conclusions
In this paper, we introduce graph-tuple networks (GtNNs), a way of extending GNNs multi- modal graph setting through the use tuples of non-commutative operators endowed with appropriate block-operator norms. We show that GtNNs have several desirable properties such as stability to perturbations and a universal transfer property on convergent graph-tuples, where the transfcrability error goes zero the graph size goes infinity. Our transferability theorem improves upon the current state-of-thee art even for the GNN case. Furthermore, our eтror bounds are expressed in terms of computable quantities from the model. This motivates 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. They also suggest that the transferability theorem holds 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.
10

---

Acknowledgments
We thank Alejandro Ribeiro for fostering our interest in this topic through various conversations, and Teresa Huang for helpful discussions about theory and code implementation. We thank the organizing committee of the Khipu conference (Montevideo, Uruguay, 2022) for providing setting leading to the present collaboration. SV is partially supported by NSF CCF 221 2212457, the NSF-Simons Research Collaboration on the Mathematical and Scientific Foundations Deep Learning (MoDL) (NSF DMS 2031985), NSF CAREER 2339682, and ONR N00014-22-1-2126, Mauricio Velasco was partially supported by ANII grants FCE- 1-EE1--------61727 and 1-0E----222----1 1-176242. Bernardo Rychtenberg partially supported by ANII grant FCE- 1-2023-1-176242
References
[1] Jan Böker, Ron Levie, Ningyuan Huang, Soledad Villar, and Christopher Morris. Fine-grained expressivity of graph neural networks. Advances in Neural Information Processing Systems, 36, 2024.
[2] Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv preprint arXiv: 104. 13478, 2021.
[3] Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and deep locally connected networks on graphs. In 2nd International Conference on Learning Representations, ICLR 2014, 2014.
[4] Landon Butler, Alejandro Parada-Mayorg and Alejandro Ribeiro. Learning with multigraph convolutional filters. In ICASSP 2023 2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 1-5, 2023.
[5] Chen Cai. Local-to-globa -lobbll perspectives graph neural networks. arXiv preprint arXiv:2306.065:4 06547, 2023.
[6] Chen Cai and Yusu Wang. Convergence of invariant graph networks. In International Conference Machine Learning, pages 2457-2484. PMLR, 2022.
[7] Juan Cerviño, Luana Ruiz, and Alejandro Ribeiro. Training stable graph neural networks through constrained learning. In ICASSP 2022 2022 IEEE International Conference on Acoustics, Speech and Signal Processing, pages 4223 0237-427,22 2022.
[8] Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? Advances neural information processing systems, 33: 33:10383-10395 2020.
[9] Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. Advances in neural information processing systems, 32, 2019.
[10] Matthieu Cordonnier, Nicolas Keriven, Nicolas Tremblay, and Samuel Vaiter. Convergence of message passing graph neural networks with generic aggregation on random graphs. In Graph Signal Processing workshop 2023, 2023.
[11] Simon S Du, Kangcheng Hou, Russ R Salakhutdinov, Barnabas Poczos, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. Advances in neural information processing systems, 32, 2019.
[12] Ben Finkelshtein, ismail ilkan Ceylan, Michael Bronstein, and Ron Levie. Learning on large graphs using intersecting communities. arXiv preprint arXiv:2405.20724. 2024.
[13] Fernando Gama, Joan Bruna, and Alejandro Ribeiro. Stability properties of graph neural networks. IEEE Transactions on Signal Processing, 68:5680-5695, 2020.
[14] Fernando Gama, Antonio G Marques, Geert Leus, and Alejandro Ribeiro. Convolutional neural network architectures for signals supported on graphs. IEEE Transactions on Signal Processing, 67(4):1034-1044 2018.

---

[15] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pages 1263-1272. PMLR, 2017.
[16] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. Advances in neural information processing systems, 30, 2017.
[17] Ningyuan Huang, Ron Levie, and Soledad Villar. Approximately equivariant graph networks. Advances in Neural Information Processing Systems, 36, 2024.
[18] Ningyuan Huang, Soledad Villar, Carey Priebe, Da Zheng, Chengyue Huang, Lin Yang, and Vladimir Braverman. From local to global: Spectral-inspired graph neural networks. arXiv preprint arXiv: 12054, 2022.
[19] Weiyu Huang, Antonio G. Marques, and Alejandro R. Ribeiro. Rating prediction via graph signal processing. IEEE Transactions Signal Processing, 66(19):5066-5088 2018.
[20] Svante Janson. Graphons, cut norm and distance, couplings and rearrangements. New York journal of mathematics, 2013.
[21] Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv:1906.01227, 2019.
[22] Henry Kenlay, Dorina Thano, and Xiaowen Dong. On the stability of graph convolutional neural networks under edge rewiring. In ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 8513-8517, IEEE, 2021.
[23] Nicolas Keriven, Alberto Bietti, and Samuel Vaiter. Convergence and stability of graph convolutional networks on large random graphs. Advances in Neural Information Processing Systems, 33:21512-21523, 2020.
[24] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2016.
[25] Alexei I. Kostrikin and Yuri I. Manin. Linear algebra and geometry, volume of Algebra, Logic and Applications. Gordon and Breach Science Publishers, Amsterdam, english edition, 1997. Translated from the second Russian (1986) edition by M. E. Alferieff.
[26] Thien Le and Stefanic Jegelka. Limits, approximation and size transferability for gnns on sparse graphs via graphops. Advances in Neural Information Processing Systems, 36, 2024.
[27] Ron Levie, Wei Huang, Lorenzo Bucci, Michael Bronstein, and Gitta Kutyniok. Transferability of spectral graph convolutional neural networks. Journal of Machine Learning Research, 22(272):1-59, 2021.
[28] Eitan Levin and Mateo Díaz. Any-dimensional equivariant neural networks. In International Conference on Artificial Intelligence and Statistics, pages 2773-2781. PMLR, 2024.
[29] Renjie Liao, Raquel Urtasun, and Richard Zemel. A pac-bayesian approach to generalization bounds for graph neural networks. In International Conference on Learning Representations, 2020.
[30] László Lovász. Large networks and graph limits, volume 60. American Mathematical Soc., 2012.
[31] Sohir Maskey, Gitta Kutyniok, and Ron Levie. Generalization bounds for message passing networks mixture of graphons. arXiv preprint arXiv:2404.034733 2024.
[32] Sohir Maskey, Ron Levie, and Gitta Kutyniok. Transferability of graph neural networks: an extended graphon approach. Applied and Computational Harmonic Analysis, 63:48-83, 2023.
[33] Sohir Maskey, Ron Levie, Yunseok Lee, and Gitta Kutyniok. Generalization analysis of message passing neural networks on large random graphs. Advances in neural information processing systems, 2022.
12

---

[34] Elvira Moreno and Mauricio Velasco. On random walks and switched random walks on homogeneous spaces. Combinatorics, Probability and Computing. 2023.
[35] Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 4602-4609 2019.
[36] Alex Nowak, Soledad Villar, Afonso S Bandeira, and Joan Bruna. Revised note learning quadratic assignment with graph neural networks. In 2018 IEEE Data Science Workshop (DSW), pages 1-5. IEEE, 2018.
[37] Alejandro Parada-Mayorge Landon Butler, and Alejandro Ribeiro. Convolutional filters and neural networks with noncommutative algebras. IEEE Transactions on Signal Processing, 71:2683 2698, 2023.
[38] Alejandro Parada Mayooga and Alejandro Ribeiro. Algebraic neural networks: Stability to deformations. IEEE Transactions on Signal Processing, 69:3351-3366, 2021.
[39] Paul Resnick. Neophytos lacovou, Mitesh Suchak, Peter Bergstrom, and John Riedl. Grouplens: an open architecture for collaborative filtering of netnews. In Proceedings of the 1994 ACM Conference Computer Supported Cooperative Work, CSCW '94, page 175-186, New York, NY, USA, 1994. Association for Computing Machinery.
[40] Luana Ruiz, Luiz Chamon, and Alejandro Ribeiro. Graphon neural networks and the transferability of graph neural networks. Advances in Neural Information Processing Systems, 33:1702-1712, 2020.
[41] Luana Ruiz, Luiz FO Chamon, and Alejandro Ribeiro. Transferability properties of graph neural networks. IEEE Transactions on Signal Processing. 2023.
[42] Luana Ruiz, Fernando Gama, and Alejandro Ribeiro. Graph neural networks: Architectures, stability, and transferability. Proceedings of the IEEE, 109(5):660 682, 2021.
[43] Luana Ruiz, Ningyuan Teresa Huang, and Soledad Villar. A spectral analysis of graph neural networks on dense and sparse graphs. ICASSP 2024-2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 9936-9940. IEEE, 2024.
[44] T Konstantin Rusch, Michael M Bronstein, and Siddhartha Mishra. survey on oversmoothing in graph neural networks. arXiv preprint M:XXv:2303.19900 2023.
[45] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80) 2008.
[46] Franco Scarselli, Ah Chung Tsoi, and Markus Hagenbuchner. The supnik-chervonenkii dimension of graph and recursive neural networks. Neural Networks, 108:248-255 2018.
[47] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2018.
[48] Xuan Zhang, Limei Wang, Jacob Helwig, Youzhi Luo, Cong Fu, Yaochen Xie, Meng Liu, Yuchao Lin, Zhao Xu, Keqiang Yan, et al. Artificial intelligence for science in quantum, atomistic, and continuum systems. arXiv preprint 2.0.:22007.0842333 2023.
13

---

A Training and transference in operator networks
The trainable parameters of operator network precisely the coefficients of the noncommutative polynomials involved. For instance, if we have feature sizes oo....., ON and all involved noncommutative polynomials have degree most then the number of trainable 1--1 k-1 Ei=o 0,04+1. For each choice o'o such coefficients the network defines function & (cH()), T) F FMN.
parameters of the operator network equal to
For a fixed collection of coefficients (for instance the one obtained from training on the data (s,, Mi) for E 7), the resulting polynomials in their respective matrices HQ) (c) allow us to evaluate the trained operator network Φ ( (c), Ti, ...... T&)
any other k-tuple of operators
M (M1 M2). Here the Mj linear maps acting vector space of functions L (possibly different from F) so evaluation defines a new network & [ (c), M) - - _ax, Because the coefficients ē were obtained by training using the operators T, this network is said to be built by transference from T to M.
B Graphon norms
The following facts about norms in the space of graphons are well-known:
1. The cut-norm equivalent norm computable from the shift operator. More precisely, define
I.J.J. W(u, v) (())(())))d
Will Il Iooll
sup
and note that this norm is expressible terms of Tw as [[ = ||T olopeop, which is the operator norm of Tw map from o ((0, 1) to L [ 1)). By (20) Equation 4.4] the cut norm and ll are equivalent because || l - || S 4||Wll
2. The cut-norm and the standard operator norm are topologically equivalent. This can be seen by letting p + oc in (20) Lemma E.7, part I] obtaining the inequality
| S |Twllop S v2[W
3. The elementary inequalities |[T llop - ||TT Hs and || S || hold where W | L. is defined by thinking of W function on the square, that is as
W LL == Jf [W (æ, y) drdy.
4. The Filbert-Schmite norm is topologically equivalent to ||.. This is implied by the
inequality in (20 Lemma E.7, part 2] namely ||W]| < [Twllss S [W]]...
C Proofs
C.1 Proof of Theorem 1 (operator-tuple perturbation inequality).
Our first lemma gives a formula for computing the block operator norms introduced in Section Recall that for positive integer A and 2 (za)aE(A) FA have ||2/ max,e(A] =
where + is the norm defined by the measure on V and a FA + F denotes the componentwise ReLu. Furthermore for positive integers A, B and a linear operator T: 1 L we have
[T(=))
sup
op
#
Lemma 9. For any linear operator M FA
FB with block blooppeecooioositinn
(2))) =Cee[A] Mr.o (za)(Za) for E [B] we have
|M
max be [
||
op
AE(4
14

---

Proof. Assume |||||
$ 1. By definition of the norm
we have
M
(x)
max [E
Mo.a (Za)
MEIA
By the triangle inequality and the definition of operator norm the last term is bounded by
max
M zall
max bE[B] aE[A]
||
S
max
Σ
||Mssallop
DEIB dE|A
bE[B]
[E[AA
where the last inequality follows since | S. 1. To prove the equality let 6 be the index for
which the sum EæElA| alsp achieves the maximum and for E [A] let ag be unit vector in JF
with |iMe (2t)) | = .alop... Letting 2 = (²")aE(A) we have || I 1 and
[M maxbe[B] (Eee(a) Mb llp) claimed.
Lemma 10. The componentwise ReLu contractive in the norm, that is
[la(f) o || - holds for every fig FA.
91
Proof. For any two real valued functions f3:9; 9, on any space V the inequality
mma(00,f(xi)) max(0, 9j (u)) s (f)(2) gy(w)
holds at every point. Since the left hand side equals the absolute value of component of of) (g) the claim proven by squaring, integrating and taking square roots on both sides and finally maximizing over j.
Remark 11. The previous proof shows that the same conclusion as for ReLu holds for any componentwise non non-lineate ae--iinerity with the property that its derivative exists almost everywhere and has absolute value uniformly bounded by one.
The following Lemma summarizes some key inequalities for nonexpansive operator-tuples.
Lemma 12. Assume T, W and Ž are non-expansive operator k-muples. The following inequalities hold:
1. For every a E [k] we have ( S for every noncommutative polynomial we have
[IT(T))lap C(h)
2. For every E [k] we have (W) xa (2) every noncommutative polynomial h we have
Zzllop and for
[|((W) k(2))lop S Σ C,)W)I Zillop
3. If H is any B x A matrix with entries in R(XI,..., Xx) then:
(a) | (H, T
maxse(B] (EeELA) C(ho,a) and
op
(b) IH, W VHH, Z)
op < maxbe[B]
(Eee(a) Σj Cy(b,.) Zzllon)
Proof. (1) The statement holds for a monomial xx because operator norms are multiplicative and each T3 has I|o by nonexpansivity. The claim for h(z) Σ c.x follows from the triangle
15

---

inequality. (2) First, for any two bounded linear operators Ta. F - F and any two signals f. the triangle inqquality implies that
(TA(f) Tx(l) - [TAllopl]. - gl1 + 11TA TB llop
In partieular, for any two nonexpansive operators TA. TB have
[Tx(f) - TB(g))l - fl gll + |T TBllop min(Ilgll, Iill
Applying this observation inductively to Σ, W, any two signals J g and any word a E [k]] we have
a (W())- -0 = Ilf all min Holl Σ b(a))
Zzllup
where (a) is the number of times the index j appears in the word a. Setting f = to be any signal with ||]|]] S 1 we conclude
|| 2z')1p (,(a)llW, - Zyllop
Combining the previous conclusion with the triangle inequality yields
[I^(W) - ll) S
C,OIIW, Zzllop
for any noncommutative polynomial (3a) By Lemma
|
max
||
llop
be [B
aE[A]
and the claim follows by applying the upper bound we just proved part (1). (3b) By Lemma (H, W) ( 2)
op
B RE[A]
max
Σ
[ha.a(W)
ha,a 2 llop
and the claim follows from applying the upper bound we just proved in part (2).
are now ready to prove the main result of this Section,
Proof of Theorem By Lemma 10 we have
(H, - (HH < ()HH, ((, ())
By the triangle inequality the quantity above is bounded by the smallest of
[H, W) - (H, 2)
+ [H, 2)
and
(H, W) VHH, 7
op 1g
+ T W)
g
The Theorem is proven by applying Lemma 12 minimum of the resulting upper bounds.
part (3) to the operator norms and taking the
We expect the bounds of the previous Theorem to be reasonably tight. To establish a precise result in this direction it suffices to prove that the bounds describe the true behavior in special cases. Consider the case with 0 Tw < Ty I 1 (a similar reasoning applies to the case of simultaneously diagonal
Remark 13.
assuming Tv, Tw and f 2 are nonnegative sealars
16

---

nonexpansive operator tuples of any size). For a univariate polynomial h(X) = Σラ= h nonnegative coefficients we have
with
d (1 - 9) - Σ
d
- -
nTT
Ing(s -9)
1=0
==
with equality when Tv = and
4
I((v))())M(WW)) Σ ==0
hi
f
Σ hy (T j=0
where the second equality follows from the intermediate value theorem (for some v()) in the interval [Tw: Tv]). This equality shows that C1 (h) is the optimal constant bound since the ratio of the left-hand side by Tv - Tw approaches C1 (h) as Ty and Tw simultaneously approach one.
C.2 Proofs of Graphon perturbation Theorems
Lemma 14. The following statements hold:
1. For every graphon W the inequality \[Tw lop S 1 holds. As a result, for every a E [b:] and any k-tuple of graphon shift operators the inequality
Tw. Olop I holds.
2. For any two bounded linear operators TA, Tn L and any signals J g we have
l[Ta(f) - TB(g))l & |op II all + a TB sellopllggt Ilgll- In particular, for any two graphons A, and any two signals X, Y we have
[Ta(]) - Tn(g) s |l all A Tallop min lI/ll)
3. For any two k-tuples of graphon shift operators Tw. Tz, any two signals f. E L and any word [k]d we have
&
a [TWW s lIf - all + fll (all) Σ gg(a)][Ti Tz, llop
where qj (a) is the number of times the index j appears in the word
Proof. (1) Since the operator norm is bounded above by the Hilbert Schmidt norm have
1
WTw lop S (L Jo W(u, u)),
and the right hand side is bounded above by one since every graphon satisfies W(u, v) E [0, 1]. The inequality on operator norms of monomial words follows from what we have just proven and the submultiplicatiiiyy (i.e. ||AB|| op I [| of operator norms. (2) The triangle inequality implies that
[TT (b()) (T()) (g) (g) TB(g)) |l T lop I|T TB (lllllll)
The second inequality follows from combining the inequality that we just proved with part (1) and exchanging the roles of and B. (3) We prove the statement by induction on d 2 If d then
= 0, xxth is the identity and the claimed inequality holds with equality. If d > 0 let j a<(1) and let [ E [k]d-1 be the word obtained from a removing the first (leftmost) term. By construction the equality x² x holds and therefore
||x (TAI... (TA....,TA.(())) x² (TB. TB)l
= =|TT, (TAI... TFf(()) TB, (Te..... TT. [g)l
17

---

By the second inequality in part (2) and part (1) this is quantity is bounded above by || (TA.. ................................ (A) x (TB. .......... --)))l
[[A, - Te, op min (1 (TAI..... TADDII (T'. Ts, (a)l
applying part (1) we know this is quantity is bounded above by
|| (TAi) TA.) _ (TB.,.... TB. Xo)ll + [[a, TB, llop min (Ilf Illl))
Applying the induction hypothesis to the first term, because B E [R]0-1, that this expression is bounded above by
(IIf gll + min (lll)
(T) - -Teillop/ + |[TA,
TB, llop min (Ilfll, II
where q: (5) is the number of times the index appears in the word a. For each index E [k] we have
({( (a) (
so we conclude that the above sum equals
Ilf all + min((1fl) Holl Σ (a))lTA -Tn,llop
proving the claimed inequality.
Lemma 15. Let A, B be positive integers.
1. The componentwise ReLu is contractive in the
norm, that is
|a((f) - ( S Ilf
gll holds for every f.g LA.
2. Let W and Z be two graphon k-tuples. If H is any B x A matrix with entries in (X. then the perturbation of the filter | (H, Tw) - V (H T2
op is
bounded above by
Σ Σ C,o,,,))TT, Tz, ol
max bE(B
a=
and furthrmorre
(IN (I,(HTW)) op
max
|V
op
is bounded above by maxbe[B] (EoELa) C(hb,a))
Proof. The Claim follows by applying this inequality to M == V Tw) and to the difference M = WH, Tw) - (H,, Tz) together with the operator norm estimates of Lemma
Lemma 16. If W == (W1.... Wx) and Ž = (Zi...., Zx) are two operator-tuplle then for any two signals f.g L the quantiry [((T))(F))))) ((T2)()) is bounded above by
C(h)lif all min Ilgl Cy(h)]TW, Tz, llop
18

---

Proof. By the triangle inequality, for any f. the quantity above by
(f) (o)
is bounded
Σ [E
cal
so the claim follows by applying Lemma 14 part (3), reordering the second sum and using the definitions of the expansion constants C(h) and (h).
Denote by To be the operators in the graph-tuple G and let To denote their induced graphon operators. If f FA is any signal then Theorem implies that the following inequality holds
Proof of Theorem 7
(HH TW)())
(H) (vv pr((f))
S
||ʃ opr
Σ MM
C(huaa
+ IIlll
ΣΣ
Cg(hn,))1lw Tā, (lop)
BE F3
BE(
aE[A|
Since the points in V equispaced, Theorem 4 implies that
i H, (T)T)) (iv (f) = o o $ H. To (pv in opr o
To M
(pr
where the last equality follows from the fact that py o 'v equals the identity map for any choice of finite set V C [0, 1]. The proof is completed by substituting this equality in the left-hand side of the previous inequality.
LI
Proof of Theorem 8 For positive integer N apply Theorem 7 to the graphon-tuple W and the graph-tuple G(N) inductively for every layer of the given architecture H. Since the matrices H defining our architecture involve only finitely many polynomials the hypothesis
IIT (g)) - -Tw, llo > 0 guarantees that the upper bound we obtain converge to zero provided
||/ iymo o Pytn (fll converges to zero as N - xc: or equivalently if the function f, or more
precisely its components are well approximated by their local averages at the sampling points (M)) This is obviously true for essentially bounded functions and happens uniformly for Lipschitz functions with common constant proving the claim.
C.3 Proof of Theorem
We begin with the following preliminary Lemma,
Lemma 17. For a positive integer n. let G be graph with vertex set V(r) and let Wa be its induced graphon. The following statements hold:
1. If f L then the equality (J) in n polynomial h with zero constant term we have
(f) holds. More generally for any
h(Tw) i, h(Ta/n) Pn
2. If E (G) is any function on the vertices of G and h(x)) is any univariate polynomial with zero constant term then
k(TW)(Gn(g) = in (b(Ta/m))))))
3. If denote the componentwise ReLu functions in and [V] respectively then the equality T in in holds.
19

---

Proof. (1) Recall that for f L we have (w) = fo Wo(z. v)f(dd which equals
Sty / (x) (0
j=1
Sts ym)) (x)) { f(y)dy=
1800
(grn (loodal (0))(a)===
(
1=1
Tc in pplll)) (z)
where the last equality holds by definition of p.. and in and because (1(T"))) 1/n for all j. For the
second claim note that both sides are linear operators suffices to prove the claim when h(x) a
monomial of degree k: 2 1. This follows immediately by induction using the fact that Pn in = [do for every n. (2) Apply the identity proven in part (1) to the function i, (g) and use the equality Pn in = idg.ytoy (3) If E R[V] then
((nn(9)) 0 Σeley (00))))
Σ max(g(1)).0)1100000 i, (o)))))
Remark 18. If the points of the set V are not equally spaced in [0, 1] then the identity in part (1) above does not hold. This is a common misconception appearing in several articles in the literature.
Proof of Theorem 4 The first claim Lemma 17 part (1). For the second claim apply Lemma inductively on layers.
C.4 Proof of the sampling Theorem
Proof of Theorem 5 (1) By compactness of the square [0, 1]2 given <> 0 there exists 5 such that for all sufficiently large, every rectangle I; I, is entirely contained in balls of radius ó with the property that [W (a;, x W Waa,00 a;)] < c whenever (z,, x.y) and (a,, 0,) are I x I,. In particular, at every point of each square the function deviates at most from its mean on this square proving that I[ - f7(x)) I < From the results summarized in Section we conclude that ||Tw - or |ls - 0 in the operator norm claimed. (2) For positive integer let ((n) be the discretization of the graphon W from the values (n) (m) defined by
B (z. v)
W(w!") (3) (x)1,,
Via the triangle inequality we estimate || - G ||o from above as the sum of |[ - B(")|l and
[[(()) ( The first term satisfies the inequality IIW - B60 < ||W- 1r7-Blyy BB") and thus goes zero by continuity of W by the argument from part (1). For the second term
[[(") ((1) note that both graphons are constant the squares I3 x 1y and therefore
n n
W(, (m)
(n) -s(m)
Sig g(m)
(n))) ((0))l
max a.be 10
a,b
n
==1
where the s(() independent Berouuli random variables with success probability W(v.") 0 ((n)).
(n)
W(n .n ( sto)
Given > 0, let A. be the event that ma
En Σj= a,b,
2 E where
nd
20

---

1/n² = pI, 1ÿ) for every Ł.j. We will show that the series E,, P(An) < ac concluding by the
Borel-Cantelli Lemma that [| m) - 1 I for all but finitely many integers Since
was arbitrary this proves that [B(r) G 0 almost surely as claimed. To verify the summability we will use simple concentration inequality. The probability P(A,) equals
(n) :0j
((m) Eg
U
ΣV
26
n
0. (0.1)²
i= i=
which is bounded above by
(m) W(o
.uj (())
Sig
Σ
P
a;
n
a.bE(0.1)"
Since each of the summands is the sum of < n² independent Bernuuli random variables shifted by their mean and divided by n?, Bernstein's 's inequality implies that the sum bounded above by
2,2 2n+l 2(++/53)
2(1-
+ log(2)
this quantity summable by the ratio test proving the claim. From the results summarized in Section 4 we know that llo is topologically equivalent to llop and we conclude that
[|Tw Too llop - proving the theorem.
Remark 19. is necessary add some assumption on W for the conclusions of the Lemma above to hold. For instance if is just in L2 1] x [0. then it can be modified in the countable, and thus Lebesgue measure zero, set Un (V(*) x v(n)) without altering the operator Tw making an approximation scheme as suggested above impossible.
D Experimental details and additional experiments
The code for experiments stability for graph tuples and experiments on transferability for sparse graph tuples are available here:
https://gi whwb. www.eccooniooeeeee http///kyiiee/ttti..eeieeeeeeeee http:///w...aoaooaa..rrraaaaaaaa .ggttsss.gttt.... And the code for experiments on world data from a movie recommendation system available here:
https://githube http:///w......aoo.eeaaa//a////a
git
D.1 Details of experiments on stability for graph tuples
For this experiments we consider weighted circulant graph of size n with shift matrix S0)
p. (1-p)/2, s = (1
if = if i mod n otherwise.
0,
We generate our data pair (æ,, Vi) E F x F with = [ as
gx) g(1)) 0.335 + 0.3 0.3( + te,
where each value of x; is uniformly distributed between [0. 11, E F is normal distributed with standard deviation
0.1, and we pick 293, p 0.05, 1 1, and 30. Noted that both input and output have only one feature, i.e., Qg = ONN = 1. We train our model with 800 training data and test it 200 testing data hest- We use MSE loss, and ADAM with learning rate 0.01, 31 0.9 and 32 = 0.999 to train our models. Running these experiments took a few hours on a regular laptop (just CPU).
Denote Tj and T3 as the shift operator corresponding to 5(4) and S(12) respectively. Recall from the main text (Section 7 that we consider four different models: (i) one layer unconstrained GtNN (i.e., A = 0 in (). (ii) one layer stable GtNN (with X = 10), (iii) two layers GtNN with number of hidden feature a 2, and (iv) two layers unconstrained GtNN (with 10 and o 2). For all four models, we set the non-commutative polynomial h(Ti, Tb) to be any polynomial of degree at most
21

---

d = 3. Thus, we have 15 trainable coefficients for both one layer models and 60 for both two layer models. For the stable GtNN model, we constrain the expansion constants to at most half of the corresponding expansion constants obtained after training the unconstrained model. Specifically, let ()) and ()) denotes the resulting expansion constants vectors for model (i). Then, we set the constraints for model (ii) to be C = C(FF)) 22 and C ( for j = 1, Similarly, /2 and C - C (x0)) //2 for = 1, 2. we set the constraints for model (iv) to be C (18)))
Figure I shows the empirical stability metrics and the corresponding upper bounds as function of the number of epochs for the one layer models (i) and (ii).
As we see in the proof of Theorem I
(equation and equation 8
the equation
|| (H, T op [|A(T)) op shows the output perturbation due to the perturbation from input
signal, and [H, W) (HI, 2) op ||A(W)) - 1( h(Z)llop shows the output perturbation due to
the perturbation from the graph. Mcanwhile, Chh) and (h) are the expansion constants that we constrained for the stable GtNN model. We note that the upper bounds exhibit the same qualitative behavior as the empirical stability metrics, especially for the stable GtNN model where all the curves drop due to the parameter reaching the boundary of the constraint sets. This suggests that our stability bound tight, and controlling the expansion constants increase the model stability. In addition, adding stability constraints has no harm on the prediction performance, since the testing R squared value for GINN is 0.6867, while for stable GINN is 0.6864.
To demonstrate the improvement on stability by our algorithms, we test all four models on various perturbed graphs (while fixing input signal). As shown in Figure rrgght) the stable GtNNs increases the stability under graph perturbations, especially in the 2-layer model.
D.2 Experiments on transferability for sparse graph tuples
We test the transferability behavior on the weighted circulant graph model from Appendix D.I We are motivated by the practical setting where we aim to train a model on a small graphs and evaluate on larger graphs. We consider piecewise constant graphon tuple (W1, W2) induced from the n = 300 circulant graph tuple, and similarly we generate a piecewise constant functions by the interpolation operator i, for each data point.
Next, we use this graphon and piecewise constant function as a generative model to generate deterministic weighted graphs (G1, G2) of size m S n as training graphs (normalized by m) and to generate training data by the sampling operator pm Since [[,, - Tc, llop + 0 as m + n, according to Theorem 7 the transferability error goes to too. To demonstrate this, we train five different models, trained with graphs tuples of fixed size m 100, 150, 200, 250, 300 (respectively) and compare the performance of the testing data with n = 300.
0.36
0.16
Stable100
GoNM:100 1.00 Statrw 1C0
0.14
Statie:150
0.30
0.12
Stable:200
Statil:55
Rasthu HEE
0.00
0.32
0.06
062
0
3000 2000
3000
2000
5000 MA2D
1000
2000
2000 spochic
3020 4000
500G
e30chs
Mean squared error (MSE) on the test set (with testing graph of size n 300) as function of the number of training epochs for (Left) (1-layer) GINN and (Middle) (1-layer) stable GtNN. In both plots we depict the performance of five different models, trained with graphs of sizes m 100, 150, 200, 250, 300 respectively. (Right) Comparison of testing MSE between (1-layer) GtNN (blue) and (1-layer) stable GtNN (orange) for training graphs of size m 100 as a function of the number of epochs.
Figure 3:
Figure 3 shows that the best testing MSE decreases as the training size approaches for the GtNN, which shows transferability holds for sparse graph tuples. For the stable GtNN, the general trend of the testing MSE curves also indicates transfcrability, In addition, the performance comparison
22

---

between GtNN and stable GINN for m 100 shows that our stability constraint improves the transferability by reducing the best testing MSE. However, this improvement only appears for the m 100 case. All the other cases have worse performance for the stable GtNN. We conjecture this because the stability constraint makes the training process take longer time to converge, and whenever it hits the constraint boundaries the MSE jumps, which also makes it harder to converge to a local minimum. It will be interesting to see if other learning algorithms or penalty functions for the stability constraints help improve the performance.
D.3 Experiments on real-world data from movie recommendation system
Finally, we present results on the behavior of graph-tuple neural filters on real data as a tool for building movie recommendation system. We use the publicly available Movielens 100k database, a collection of movie ratings given by set of 1000 users [39] to 1700 movies. Our objective is to interpolate ratings among users: starting from the ratings given by a small set of users to certain movie, we wish to predict the rating given to this movie by all the remaining users. Following [1] we center the data (by removing the mean rating of each user from all its ratings) and try to learn deviation from the mean rating function. More precisely, letting be the set of users, we wish to learn the map ø R[U] - IR[]] which, given partial deviation from the mean ratings function f: U + 1,2,.... 5 (with missing data marked as zero) produces the full rating function f = o(f) where [u) contains the deviation of the mean ratings for user u.
The classical Collaborative filtering approach to this problem consists of computing the empirical correlation matrix B among users via their rating vectors. A more recent approach [9] defines a shift operator S on the set of users by sparsifying B. More precisely we connect two users whenever their pairwise correlation is among the highest for both and then approximate ó as a linear filter or more generally GNN evaluated S. Although typically superior collaborative filtering, this approach has a fundamentally ambiguous step: How to select the integer k?? To the best of our knowledge, there is no principled answer this question so we propose considering several values simultaneously, defining tuple of shift operators, and trying to learn 6 via graph-tuple neural networks on IR [U]. More specifically we compute two shift operators Ti, T2 by connecting each user to the 10 and 15 most correlated other users respectively, and compare the performance of the GINN on the tuple (Ti, Tp) (2ONN) with the best between the GNNs on each of the individual operators Ti and T/ (GNN). To make the comparison fair we select the degrees of the allowed polynomials so that all models have the same number of trainable parameters (seven).
Figure 2 (left) shows that an appropriately regularized Graph-tuple network significantly outperforms all other models at any point throughout the first 500 iterations (the minimum occurs when the training error stops improving significantly). However, if the model over-trained as in the right plot of Figure then can suffer from a vanishing gradients limitation which may lead trained model worse than the best one obtained from standard graph filters. This example suggests that graph-tuple neural networks are of potential relevance applications.
23

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main contribution of the paper are the theoretical results described the abstract. A small set of experiments to verify the theoretical claims provided in Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The assumptions under which the theoretical claims are valid are clearly
stated.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets with few runs. general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
24

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The theorem statements have the full set of assumptions. The proofs are provide in Appendix
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The experiments setup and data are described in Appendix Din detail. The code is publicly available.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (c.g., in the case of large language model), releasing of model checkpoint, other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is a new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the partieular way they provide for reproducibiliity In the case of closed-source models, it may be that access to the model is limited in
25

---

some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
The code is publicly available.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines
for more details. While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this central to the contribution (e.g., for a new open- benchmark).
(https://nip) wttp::pcpcppppcpcccccce//////e/e
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https://nipp) http://titppcccp.llaiip wwtiic//gg////ieeeeeeeee
for more details. The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification:
See Appendix D
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: We didn't compute error bars. The experiments are simply used to illustrate the theory.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
26

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: See Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: htt////eerripp.eee cwturrps.cc/publliee http.//c/cbcitethcccccieeeeeeeee
Answer: [Yes]
Justification:
We conducted the research ethically.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consideration due laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is thcoretical work on stability and transfcrablity of GNNs. We don't identify any socictal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
27

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations
(e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse dual-use should be released with necessary safeguards allow for controlled use the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safery filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from particular source (e-g., website), the copyright and terms of service of that source should be provided.
28

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- e-packagged both the original license and the license the derived asset (if it has changed) should be provided. this information is not available online, the authors are encouraged to reach out the asset's s creators.
13. New Assets
Are new assets introduced the paper well documented and the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection. curation, or other labor should be paid at least the minimum wage in the country the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may required for any human subjects research. you obtained IRB approval, you should clearly state this in the paper.
29

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
30


Reviews:
[{"review_id": "JGn2NWaObB", "reviewer": "Reviewer_eJ8g", "summary": "This paper considers the node-level learning task with several graphs sharing the same vertex set called graph-tuple neural networks (GtNNs). The stability and transferability of GtNNs are studied using properties of non-commuting non-expansive operators. The authors show that all GtNNs are transferable on convergent graph-tuple sequences using graphon-tuple neural network limits. They also illustrate the theoretical results with experiments on synthetic data.", "questions": "1. Can the operator network framework be adapted to the case when the graphs have only partial overlap rather than the same set of vertices?\n2. Is it possible to extend the current work to *sparse* graphs when there are no induced graphons?", "limitations": "The authors adequately addressed the limitations of the work and clearly stated the assumptions.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. A theoretical framework based on operator networks for analyzing graph neural networks on multimodal data where several graphs share the same set of nodes is proposed. Using this framework, a perturbation inequality, which provides the perturbation stability of non-expansive operator-tuple networks, is proven. The proposed framework may be extended to accommodate other settings and can be used to study other tasks related to GNNs.\n2. The authors also define the graphon-tuple neural networks (WtNNs) which are natural limits of GtNNs. Further, a Universal transferability Theorem for graphon-graph transference, which guarantees that the GtNN learned on a graph-tuple with sufficient many vertices transfers to other graph-tuples, is shown. This transferability result is original and addresses the multimodal learning aspect in GNNs.\n3. This work contributes to the literature of analyzing GNNs through graph limits and the study of the multimodal setting through operator networks is original. The paper is clearly written.", "weaknesses": "1. The tightness of the bounds is only demonstrated through numerical experiments rather than formal theoretical analysis.\n2. The results are based on strong assumptions such as the existence of graphons induced by the graphs, the continuity of the graphons, the equispaceness of the vertex set, and the graph-tuple convergence in the operator norm. However, these assumptions may be standard in the literature.\n3. The results lack support from real-world experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful comments and positive feedback. We address each of your comments and questions below:\n\n> The tightness of the bounds is only demonstrated through numerical experiments rather than formal theoretical analysis.\n\nThank you for pointing this out. We have added a theoretical analysis showing that the bounds are tight for some simultaneously diagonal operator tuples that we reproduce here using the notation of the paper: \n\n**Remark 13 Appendix C**\n\nWe expect the bounds of the previous Theorem to be reasonably tight. To establish a precise result in this direction it suffices to prove that the bounds describe the true behavior in special cases. Consider the case $k=1$, $n=1$ assuming $T_V,T_W$ and $f\\geq g$ are nonnegative scalars with $0\\leq T_W\\leq T_V\\leq 1$ (a similar reasoning applies to the case of simultaneously diagonal nonexpansive operator tuples of any size). For a univariate polynomial $h(X)=\\sum_{j=0}^d h_jX^j$ with nonnegative coefficients we have\n$ |h(T_V)(f)-h(T_V)(g)| =\\left(\\sum_{j=0}^d h_j T_V^j \\right)(f-g)\\leq \\sum_{j=0}^d |h_j|(f-g)$\nwith equality when $T_V=1$ and\n\n$|h(T_V)(f)-h(T_W)(f)| =\\sum_{j=0}^d h_j\\left(T_V^j-T_W^j\\right)f$  =  $\\sum_{j=0}^d h_j \\left( j v_{(j)}^{j-1} (T_V-T_W) \\right) f \\leq C_1(h) |T_V-T_W| f$\n\nwhere the second equality follows from the intermediate value theorem (for some $v_{(j)}$ in the interval $[T_W,T_V]$). This equality shows that $C_1(h)$ is the optimal constant bound since the ratio of the left-hand side by $T_V-T_W$ approaches $C_1(h)$ as $T_V$ and $T_W$ simultaneously approach one.\n\n> The results are based on strong assumptions such as the existence of graphons induced by the graphs, the continuity of the graphons, the equispaceness of the vertex set, and the graph-tuple convergence in the operator norm. However, these assumptions may be standard in the literature.\n\nYes, they are. The only currently known approach for thinking about transferability is by showing it is a property automatically inherited along convergent graph sequences. Graphons are only one possibility. Crucially, our results show that the comparatively weaker operator norm convergence is sufficient for transferability and this should simplify proving many other transferability results (much of the existing literature focuses on the much stronger –and thus less applicable– Hilbert Schmidt norm convergence). \n\nFurthermore we point out that the perturbation inequalities (stability results) do not require any form of convergence, nor sampling from graphons (equispaced or otherwise). These assumptions are used only for the transferability results. The assumptions we make are not the only possibility, but some assumptions will be needed because in order to establish transferability we need to define what it means to grow the size of graphs consistently (which is equivalent to saying what it means for a sequence of growing size graphs to converge to a limiting distribution). This is needed to have a notion of ground truth to be able to say “if we train a GNN on graphs with $m$ vertices and evaluate it in graphs of $n$ vertices the error is bounded by epsilon” (such a statement relies on an implicit notion of graph convergence).\n\nHere we focus on graphons and the operator norm convergence (and we justify why this convergence is preferable over the Hilbert Schmidt). However, extending our results to other notions of convergence and limiting objects could be of interest. In particular the “Stretched Graphon Model” [1] replaces the notion of graphon $W : [0, 1]^2 → [0, 1]$ by stretching its domain from $[0, 1]$ to $\\mathbb R_{+}$  while preserving the integrality condition, to generate sparse graphs. The equispaced sampling in $[0,1]$ is typically replaced by a Poisson sampling in $\\mathbb R$. Similarly, the Graphex model introduced in [2] relates to an alternative notion of graph convergence known as sampling convergence [3]. \n\t\t\t\t\t\t\n>The results lack support from real-world experiments.\n\nWe agree with the reviewers’ comment and have added the results of our initial experiments on Recommendation Systems on real-world  data in a new Final Section “Experiments with real-world data” (see global rebuttal for details). We believe this is a very interesting direction which deserves further exploration and we intend to make it the focus of future work. \n\n>Can the operator network framework be adapted to the case when the graphs have only partial overlap rather than the same set of vertices?\n\nIf the union of all vertex sets is called $U$ and we have a shift operator $S$ on a subset $V$ then we can extend the matrix $S$ to a $|U|\\times |U|$ matrix $\\tilde{S}$ by making all the missing entries zero. In some applications with centered data (for instance in recommendation systems where the scores are centered to have mean zero) this extension by zero is harmless and leads to a satisfactory result. However it should not be used blindly since it could introduce extra unwanted zeroes (blurring the difference between a zero rating and a missing rating) \n\n>Is it possible to extend the current work to sparse graphs when there are no induced graphons?\n\nThe perturbation inequality would work over any convergent sequence on the operator norm. As we mention above, even if we don’t use graphons we need a notion of graph limits in order to establish transferability. There are some attempts in the literature to define limiting objects for certain families of sparse graphs [1,2,3] and our theory might immediately apply to those. It would be an interesting research direction to carry this idea forward.\n\n[1] C Borgs, JT Chayes, H Cohn, and N Holden. Sparse exchangeable graphs and their limits via graphon processes. JMLR, 2018. \n[2] V Veitch and DM Roy. The class of random graphs arising from exchangeable random measures, 2015. \n[3] C Borgs, JT Chayes, H Cohn and V Veitch. Sampling perspectives on sparse exchangeable graphs. Ann. Prob., 2019.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "07s4AWaJrW", "reviewer": "Reviewer_hLUB", "summary": "This paper introduces a new type of neural network called graph-tuple neural networks (GtNN) that can handle multiple graphs with the same set of nodes and non-commuting graph operators. The authors develop a mathematical theory to show the stability and transferability of GtNNs and derive related bounds, proving a universal transferability theorem for these networks. Their results extend existing transferability theorems for traditional graph neural networks and include experiments on synthetic data to demonstrate their findings.", "questions": "1.\tCan this method be viewed as a training strategy that improves every existing Graph Mining method?\n2.\tSince WtNNs are “the natural limits of (GtNNs) as the number of vertices grows to infinity”, why did you discuss WtNNs right after the Perturbation inequalities instead of elaborating on GtNNs first.\n3.\tWhat is the convergence order, i.e. O(N^k), of the quantity when N goes to infinity?", "limitations": "The authors did not adequate discuss the limitation of their work. They may consider talk about how to implement their complicate theories in a understandable way to help this work to gain influence.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1.\tThe author put forward a novel theoretical framework GtNN to model a general case when considering transferability and stability, and the Universal transferability Theorem to quantify.\n2.\tA generative method of mentioned graph sequence is provided instead of merely assuming the existence of the sequence they used in their theoretical framework.\n3.\tDefine the graphon-tuple neural networks (WtNNs) to help theoretical derivation.", "weaknesses": "1.\tNo experiments on real data to prove the transferability and stability gain using their method compared to GNN.\n2.\tThe theoretical background knowledge is not adequately provided.\n3.\tLacking proper reasoning phases to connect each sections.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive comments and questions. We address them below:\n\n>No experiments on real data to prove the transferability and stability gain using their method compared to GNN.\n\nWe have included some initial results on using operator networks in real-world data in a new final Section of the article (see brief summary in the global rebuttal), we have also added some synthetic transferability experiments. The main contribution of the article is however Theoretical and we have added a proof of tightness of our inequalities in the new Remark 13 in Appendix C as objective proof of the applicability of our results (see rebuttal to Reviewer eJ8g). \n    \n>The theoretical background knowledge is not adequately provided.\n\nWe have made an effort to add some background knowledge via adding a reference to Hilbert spaces and norms [1] that are needed for a thorough understanding of the article. We also have verified that all novel terms are defined in a rigorous and logically consistent fashion. We kindly ask the reviewer to let us know what background needs further clarification so we can improve the manuscript.\n\n[1] Kostrikin, Alexei I.; Manin, Yuri I. Linear algebra and geometry. Translated from the second Russian (1986) edition by M. E. Alferieff. Revised reprint of the 1989 English edition. Algebra, Logic and Applications, 1997.\n\n>Lacking proper reasoning phases to connect each sections.\n\nWe disagree with the reviewer. Each Section begins with clarifying how it connects with the rest of the paper. Due to space limitations it has not been possible to make this more extensive.\n\n>Can this method be viewed as a training strategy that improves every existing Graph Mining method?\n\nIn order to apply this method as a training strategy one needs computable bounds which estimate the stability of the resulting network for each choice of the parameters. The main contribution of our work is the discovery of an easily computable form for such bounds: this is the key behind the training strategy. The same method could thus apply to any area where such bounds are available.\n\n>Since WtNNs are “the natural limits of (GtNNs) as the number of vertices grows to infinity”, why did you discuss WtNNs right after the Perturbation inequalities instead of elaborating on GtNNs first.\n\nWe agree and thank the reviewer for pointing this out! We have moved the key example of GtNNs to the end of Section 2, which occurs before the definition of graphon, as it should be to facilitate understanding.\n\n>What is the convergence order, i.e. O(N^k), of the quantity when N goes to infinity?\n\nThe proof of the Theorem 8 clarifies that the speed of convergence is determined by the speed at which the sequence of induced graphons converges to the limiting  graphon multiplied by a computable constant which depends on the coefficients of the noncommutative polynomials (as in Theorem 7). This quantity is not a fixed N^k, it could vary drastically from one graphon sequence to another.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1uKBFEQul0", "reviewer": "Reviewer_RRVw", "summary": "This paper considers the tasks of extending GNNs to multiple graphs with a shared node set (and the edges representing different types of relations).\n\nIn order to do this in a principled manner, the authors consider the algebra of non-commutative polynomials and provide a detailed analysis of stability to perturbations. The authors also extend their setting to graphons and show several consistency results (where the practical implications are to transferability). Notably, the proofs are well written with careful attention to detail and do not suffer from many of the issues common to proofs in ML papers. (See e.g., Remark 16.)\n\nOverall, this paper provides a solid, easily understandable, theoretical framework for an important problem (learning on multigraphs). Acceptance is recommended.", "questions": "Does any of the graphon theory extend to random graphs derived from graphons?\n\nDo you think that analogs of the transferability results for graphon operators can be produced for settings where the graph is derived by subsampling a manifold as in https://arxiv.org/pdf/2305.18467, https://arxiv.org/pdf/2210.00376, https://arxiv.org/pdf/2212.12606, https://arxiv.org/pdf/2307.04056\n\nHow does theorem 1 compare with theorem 2 of this paper https://arxiv.org/pdf/2108.09923\n\nIs it possible to define things in any sort of Fourier domain?", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Section 6, connecting the stability guarantees to the training procedure is interesting!\n\nTheory is novel, interesting and well explained. \n\nThe paper is generally well written and well motivated \n\nThe introduction go WtNNs is interesting, well motivated, and provides a solid theoretical framework for transferability of NNs on multigraphs", "weaknesses": "It would be helpful if the sections on non-commutative polynomials and operator filters discussed related work on algebraic signal processing and defining neural nets on arbitrary measure spaces, e.g., https://arxiv.org/pdf/2210.17425, https://arxiv.org/pdf/2108.09923, https://arxiv.org/pdf/2210.16272, https://arxiv.org/pdf/2009.01433, https://arxiv.org/abs/2208.08561\n\nCorollaries 2 and 3 are nice, but should probably be combined into a single corollary. Additionally, it looks like equation 5 could be fit onto a single line (possibly with a small amount of negative hspace.)\n\nA more detailed explanation of Example 6 would be helpful. I had to read it several times in order to understand\n\nHaving some experiments with real data would be helpful (although I do recognize that the contributions of this paper are primarily theoretical).\n\nA short conclusion would be nice in the camera ready copy.\n\nLine 494: It is not clear where \"block operator\" norms were introduced\n\nIn Lemma 10 (and throughout) the authors should make it more clear that \\| \\cdot \\| refers to the \\ell^2 norm since there are many different spaces in this paper.\n\nLemma 14 is out of place, it should be before the proof of Lemma 14 (which means it would then become Lemma 13) \n\nMore details should be added to the proof of theorem 7\n\nReleasing a colab notebook after the review process is okay, but an anonymous github would have been better to improve upon reproducibility\n\nMinor:\n\nLine 91: \"behavior than\" should be \"behavior as\"\n\nLine 97: the phrase \"loopless\" could be confusing. Should make it more clear you mean no self loops\n\nThe term End(W) is used without definition. I know what this means, but it would be better to discuss in order to keep the paper self contained for an ML audience. \n\nLine 167: Cartesian should have a capital C. The authors should check throughout for other words derived from last names, e.g., Euclidean or Laplacian\n\nLine 237: V^{(s)} should be V^{(n)}, right?\n\nLine 313: \"Corollary\" should be \"corollary\"\n\nLinne 494: \"Lemma\" should be \"lemma\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough and positive review. See below our comments and answers to your questions.\n\n\n>Discuss related work ...\n\nWe thank the reviewer for pointing this out. We have added all the above references as relevant related work in the Introduction. The new paragraph is in a comment for completeness\n\n>Corollaries 2 and 3 are nice, but should probably be combined into a single corollary.\n\nWe believe keeping two corollaries is useful since the first only applies to single blocks and could potentially be used as a step for understanding stability on a different architecture whereas the second one is useful to speak about a large class of examples. \n\n>A more detailed explanation of Example 6 would be helpful. I had to read it several times in order to understand\n\nWe have rewritten Example 6 aiming to improve its clarity. We paste it in a comment for completeness.\n\n>Having some experiments with real data would be helpful (although I do recognize that the contributions of this paper are primarily theoretical).\n\nWe agree with the reviewers’ comment and have added the results of our initial experiments on Recommendation Systems on real-world  data in a new Final Section entitle “Experiments with real-world data” (see global rebuttal for details). We believe this is a very interesting direction which deserves further exploration and we intend to make it the focus of future work. \n\n>A short conclusion would be nice in the cam ready copy.\nWe have added it. Please see Comments for details.\n\n>Line 494: It is not clear where \"block operator\" norms were introduced\nWe have added a reference to the precise Section.\n\n>In Lemma 10 (and throughout) the authors should make it more clear that |  | refers to the \\ell^2 norm since there are many different spaces in this paper. We have rewritten the first paragraph of the Section to clarify the meaning of block norms and the fact that on individual components we are referring to the L^2 norm defined by the measure \\mu_V\n\n>Lemma 14 is out of place, it should be before the proof of Lemma 14 (which means it would then become Lemma 13)\nWe agree and thank the reviewer for pointing this out! We have placed it properly.\n\n>More details should be added to the proof of theorem 7\nWe rewrote the proof to make it clearer. The new version is in a comment for completeness.\n\n>Releasing a colab notebook after the review process is okay, but an anonymous github would have been better to improve upon reproducibility\n\nWe have added two github repositories containing the scripts used for the article:\n\nhttps://anonymous.4open.science/r/GtNN_weighted_circulant_graphs-27EB\nhttps://anonymous.4open.science/r/operatorNetworks-508F\n\n>Does any of the graphon theory extend to random graphs derived from graphons?\n\nPlease see rebuttal of point 2 of reviewer (eJ8g) for a general perspective.  \n\n> Do you think that analogs of the transferability results for graphon operators can be produced for settings where the graph is derived by subsampling a manifold as [references]?\n\nWe believe the answer is yes. Our Theorems imply that whenever one is given a family of converging operators in the rather weak, (and thus widely applicable) operator norm, transferability results hold. In particular it should be possible to use the spectral theory of convergence of laplacian graphs on manifolds (as developed for instance in the interesting work of Calder and Garcia-Trillos [1]) to prove novel transferability results for operator networks operating in this setting.\n\n[1] Jeff Calder, Nicolás García Trillos, Improved spectral convergence rates for graph Laplacians on ε-graphs and k-NN graphs, Applied and Computational Harmonic Analysis, Volume 60,2022.\n\n>How does theorem 1 compare with theorem 2 of this paper https://arxiv.org/pdf/2108.09923\n\nWe thank the reviewer for pointing out the above article [denoted PBR]. There are commonalities between the current submission and [PBR] so we have added it as important previous work. Both [PBR] and our article are interested in the stability of filters obtained from representations of operator algebras. The key difference between our stability results and those of [PBR] stem from the choice of norm.\nMore specifically: Theorem 2 in [PBR] gives a local perturbation result in the Hilbert-Schmidt norm and contains an unspecified error term. By contrast in our Theorem 1 we give up on the Hilbert-Schmidt norm and instead obtain an upper bound in the operator norm without any unspecified error term. Our result is easily computable, because it depends explicitly on the coefficients of noncommutative polynomials. Our Theorem 1 and [BPR, Theorem 2] are thus complementary inequalities, neither objectively stronger than the other and both could be applied in different circumstances.\nFor the kinds of applications we discuss--transferability, the operator norm is a clearly advantageous choice,giving novel Universal transferability results. The fact that our stability bounds are easily computable in terms of polynomial coefficients plays a key role in the novel \"stable\" training algorithms we propose.\n\n>Is it possible to define things in any sort of Fourier domain?\nWe believe the answer is no in general. The Fourier signal processing point of view is basically about diagonalizing the shift operator, however from basic matrix theory we know that a family of operators is simultaneously dagonalizable if and only if it is commutative and each element of the family is diagonalizable so commutativity seems essential. An interesting possible extension is to operator tuples  which are representations of reductive noncommutative groups. However, even for that case the matrices would become only simultaneously block diagonal which would be rather far from the original Fourier transform (although there is a noncommutative Fourier transform that could provide a weak substitute in that case). Nothing like this is available for general noncommuting operators, which are the main focus.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their thorough reading and constructive comments. We are encouraged that all three reviewers found the paper interesting. The paper’s main weakness, according to the reviews, was the lack of a more thorough empirical evaluation. To address this, we include two additional experiments, one of transferability on a synthetic dataset, and one on a real-world dataset of a movie recommendation system where information from two graphs is combined using the GtNN model. Figures 2 and 3, and references are included in the PDF.

**Experiments on transferability for sparse graph tuples**

We test the transferability behavior on the weighted circulant graph model from Appendix D. We are motivated by the practical setting where we aim to train a model on a small graphs and evaluate it on larger graphs. We consider a piecewise constant graphon tuple $(W_1,W_2)$ induced from the $n=300$ circulant graph tuple, and similarly we generate a piecewise constant functions by the interpolation operator $i_n$ for each data point. 

Next, we use this graphon and piecewise constant function as a generative model to generate deterministic weighted graphs $(G_1,G_2)$ of size $m \leq n$ as training graphs (normalized by $m$) and to generate training data by the sampling operator $p_m$.  Since 
$||T_{W_j}-T_{\hat{G}_j}|| _{\rm op} \to 0$   as $m\to n$, according to Theorem 7 the transferability error goes to $0$ too. To demonstrate this, we train five different models, trained with graphs tuples of fixed size $m=100,150,200,250,300$ (respectively) and compare the performance of the testing data with $n=300$. 

Figure 2 shows that the best testing MSE decreases as the training size $m$ approaches $n$ for the GtNN, which shows transferability holds for sparse graph tuples. For the stable GtNN, the general trend of the testing MSE curves also indicates transferability. In addition, the performance comparison between GtNN and stable GtNN for $m=100$ shows that our stability constraint improves the transferability by reducing the best testing MSE. However, this improvement only appears for the $m=100$ case. All the other cases have worse performance for the stable GtNN. We conjecture this is because the stability constraint makes the training process take a longer time to converge, and whenever it hits the constraint boundaries the MSE jumps, which also makes it harder to converge to a local minimum. It will be interesting to see if other learning algorithms or penalty functions for the stability constraints help improve the performance.

**Experiments on real-world data from a movie recommendation system**

Finally, we present results on the behavior of graph-tuple neural filters on real data as a tool for building a movie recommendation system. We use the publicly available MovieLens 100k database, a collection of movie ratings given by a set of 1000 users [1] to 1700 movies. Our objective is to interpolate ratings among users: starting from the ratings given by a small set of users to a certain movie, we wish to predict the rating given to this movie by all the remaining users. Following [2] we center the data (by removing the mean rating of each user from all its ratings) and try to learn a \emph{deviation from the mean rating function}. More precisely, letting $U$ be the set of users, we wish to learn the map $\phi:\mathbb R[U]\rightarrow\mathbb R[U]$ which, given a partial deviation from the mean ratings function $f:U\rightarrow \{1,2,\dots,5\}$ (with missing data marked as zero) produces the full rating function $\hat{f}=\phi(f)$ where $f(u)$ contains the deviation of the mean ratings for user $u$. 

The classical Collaborative filtering approach to this problem consists of computing the empirical correlation matrix $B$ among users via their rating vectors. A more recent approach [2] defines a shift operator $S$ on the set of users by sparsifying $B$. More precisely we connect two users whenever their pairwise correlation is among the $k$ highest for both and then approximate $\phi$ as a linear filter or more generally a GNN evaluated on $S$. Although typically superior to collaborative filtering, this approach has a fundamentally ambiguous step: How to select the integer $k$?  To the best of our knowledge, there is no principled answer to this question so we propose considering several values simultaneously, defining a tuple of shift operators, and trying to learn $\phi$ via graph-tuple neural networks on $\mathbb R[U]$. More specifically we compute two shift operators $T_1,T_2$ by connecting each user to the $10$ and $15$ most correlated other users respectively, and compare the performance of the GtNN on the tuple $(T_1,T_2)$ (2ONN) with the best between the GNNs on each of the individual operators $T_1$ and $T_2$ (GNN). To make the comparison fair we select the degrees of the allowed polynomials so that all models have the same number of trainable parameters (seven). 

Figure 3 (left) shows that an appropriately regularized Graph-tuple network significantly outperforms all other models at any point throughout the first $500$ iterations (the minimum occurs when the training error stops improving significantly). However, if the model is over-trained as in the right plot of Figure 3 then it can suffer from a vanishing gradients limitation which may lead to a trained model worse than the best one obtained from standard graph filters. This example suggests that graph-tuple neural networks are of potential relevance to applications.

Meta-review: This paper introduces graph-tuple neural networks (GtNNs) to handle multiple graphs with shared node sets. The theoretical contributions on stability and transferability of GtNNs are strong and well-developed. All reviewers found the work interesting and technically sound. The main weakness noted was limited experimental evaluation, especially on real-world data. The authors have addressed this in their rebuttal by adding experiments on a movie recommendation dataset. Overall, the novel theoretical framework and analysis represent a valuable contribution. The paper is recommended for acceptance, with the suggestion to incorporate the additional experiments in the final version.
Decision: Accept (poster)