Graph neural networks and non-commuting operators

Authors: mauricio  velasco
kaiying  o'hare
bernardo  rychtenberg
soledad  villar
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 22:28:08

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.

Main paper: 
 introduction: 
 Graph neural networks (GNNs) [45, 3, 24, 16] 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 on the vertices of a graph (also called signals or vertex features) and use 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 [14] , 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 a graph composed with componentwise non-linearities. Therefore, such networks implement the idea that the values of a function at a 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 theoretical aspects of MPNNs, including, for instance, expressivity [35, 47, 9, 1, 8] , oversmoothing [44] , multi-scale properties [18, 5] , 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 input graphs. The idea is conceptually related to 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 is 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 a solid theoretical foundation to the transferability properties of GNNs. The theory was further developed in [27, 41, 32, 23, 10] , and was extended to other models in [6, 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 graph input or graph signal [42, 7, 13, 22] , and conceptually related to the theory of generalization for GNNs [46, 11, 29, 33, 31] though the techniques are different.In many practical situations a 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 as 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 a crucial difference: whereas the main results in the articles above refer to the Hilbert-Schmidt norm, we define and analyze block-operator-norms on non-commutative algebras acting on function spaces. This choice allows us to prove stronger stability and transferability bounds that when restricted to classical GNNs improve upon or complement the state-of-the-art theory. In particular, we complement work in [42] by delivering bounds that do not exhibit 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 in the multimodal framework where each graph object (or graph tuple) can have several adjacency matrices on a fixed set of vertices. We call this model graph-tuple neural networks (GtNNs). It 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 h(X 1 , . . . , X k ) on the adjacency matrices of the k graphs in our 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 a Universal transferability Theorem for graphon-graph transference which guarantees that every graphon-tuple neural network (without any assumptions) is transferable over sequences of graph-tuples generated from a given graphon-tuple. This means that whatever a GtNN learns on a 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-graph 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 a 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] ). 
preliminary definitions: 
 For an integer n we let [n] := {1, 2, . . . , n}. By a graph G on a set V we mean an undirected, finite graph without self-loops with vertex set V (G) := V and edge set denotedE(G). A shift matrix for G is any |V | × |V | symmetric matrix S with entries 0 ≤ S ij ≤ 1 satisfying S ij = 0 whenever i ̸ = j and (i, j) ̸ ∈ E(G).Our main object of study will be signals (i.e. functions) on the common vertices V of a 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, as a vector space, R[V ] ∼ = R |V | however, as we will see later, thinking of this space as consisting of functions is key for understanding the neural networks we consider. Any shift matrix S for G defines a shift operatorT G : R[V ] → R[V ] by the formula T G (f )(i) = j∈V S ij f (j).The layers of graph neural networks (GNNs) are built from univariate polynomials h(x) evaluated on the shift operator T G of a graph composed with componentwise non-linearities. If we have a k-tuple of graphs G 1 , . . . , G k with common vertex set V then it is natural to consider multivariate polynomials evaluated at their shift operators T Gi . 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 1 , . . . , X k ⟩ be the algebra of non-commutative polynomials in the variables X 1 , . . . , X k . This is the vector space having as basis all finite length words on the alphabet X 1 , . . . , X k endowed with the bilinear product defined by concatenation on the basis elements. For example in R⟨X 1 , X 2 ⟩ we have(X 1 + X 2 ) 2 = X 2 1 + X 1 X 2 + X 2 X 1 + X 2 1 ̸ = X 2 1 + 2X 1 X 2 + X 2 2 .The basis elements appearing with nonzero coefficient in the unique expression of any element h(X 1 , . . . , X k ) are called the monomial words of h. The degree of a monomial word is its length (i.e. number of letters). For example there are eight monomials of degree three in R⟨X 1 , X 2 ⟩, namely:X 3 1 , X 2 1 X 2 , X 1 X 2 X 1 , X 2 X 2 1 , X 2 2 X 1 , X 2 X 1 X 2 , X 1 X 2 2 , X 3 2 .More generally there are exactly k d monomial words of length d and k d+1 -1 k-1 monomial words of degree at most d in R⟨X 1 , . . . , X k ⟩. 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. If T 1 , . . . , T k ∈ End(W ) are any set of linear maps on W then the individual evaluations X i → T i extend to a unique evaluation homomorphism R⟨X 1 , . . . , X k ⟩ → End(W ), which sends the product of polynomials to the composition of linear maps. This relationship (known as universal freeness property) determines the algebra R⟨X 1 , . . . , X k ⟩ uniquely. This proves that noncommutative polynomials are the only naturally transferable parametrization for our networks. For a polynomial h we denote the linear map obtained from evaluation as h(T 1 , . . . , T k ).Operator filters and non-commuting operator neural networks. Using noncommutative polynomials we will define operator networks, an abstraction of both graph and graphon neural networks.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 on a fixed domain V endowed with a measure µ V . The measure turns F into an inner product space (see [25, Chapter 2] for background) via the formula ⟨f, g⟩ := V f gdµ V and in particular gives it a natural norm ∥f ∥ := (⟨f, f ⟩) 1 2 which we will use throughout the article. In later sections the set F will be either R[V ] or the space L := L 2 ([0, 1]) of square integrable functions in [0, 1] but operator networks apply much more generally, for instance to the spaces of functions on a manifold V used in geometric deep learning [2] . By an operator k-tuple on F we mean a sequence ⃗ T := (T 1 , . . . , T k ) of linear operators T j : F → F. The tuple is nonexpansive if each operator T j has norm bounded above by one.If h ∈ R⟨X 1 , . . . , X k ⟩ is a noncommutative polynomial then the operator filter defined by h = α c α X α and the operator tuple ⃗ T is the linear operator Ψ(h, ⃗ T ) : F → F given by the formulah(T 1 , . . . , T k )(f ) = α c α X α (T 1 , . . . T k )(f )where X α (T 1 , . . . , T k ) is the composition of the T i from left to right in the order of the word α. Forinstance if h(X 1 , X 2 ) := -5X 1 X 2 X 1 + 3X 2 1 X 2 then the graph-tuple filter defined by h applied to a signal f ∈ F is Ψ(h, T 1 , . . . , T k )(f ) = -5T 1 (T 2 (T 1 (f ))) + 3T 2 1 (T 2 (f )).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 h b,a ∈ R⟨X 1 , . . . , X k ⟩ we define the operator filter determined by H and the operator tuple ⃗ T to be the linear map Ψ(H, ⃗ T ) :F A → F B which sends a vector x = (x a ) a∈[A] to a vector (z b ) b∈[B] using the formula z b = a∈[A] h b,a (T 1 , . . . , T k )(x a )An operator neural layer with ReLU activation is an operator filter composed with a pointwise non-linearity. This composition σ • Ψ(H, ⃗ T ) yields a (nonlinear) map Ψ(H, ⃗ T ) :F A → F B .Finally an operator neural network (ONN) is the result of composing several operator neural layers.More precisely if we are given positive integers α 0 , . . . , α N and N matrices H (j) of noncommutative polynomials H(j) b,a := h (j)b,a (X 1 , . . . , X k ) for (b, a) ∈ [α j+1 ] × [α j ] and j = 0, . . . , N -1, the operator neural network (ONN) determined by ⃗ H := (H (j) ) N -1 j=0 and the operator tuple ⃗ T is the compositionF α0 → F α1 → • • • → F α Nwhere the j-th map in the sequence is the operator neural layer with ReLu activation Ψj (H (j) , ⃗ T ) : F αj → F αj+1 . We write Φ( ⃗ H, ⃗ T ) : F α0 → F α N to refer to the full composite function. See Appendix A for a discussion on the trainable parameters and the transfer to other k-tuples. We conclude the Section with a key instance of operator networks:An Example: Graph-tuple neural networks (GtNNs). Henceforth we fix a positive integer k, a sequence G 1 , . . . , G k of graphs with common vertex set V and a given set of shift operators T G1 , . . . , T G k . We call this information a graph-tuple ⃗G := (G 1 , . . . , G k ) on V .The graph-tuple filter defined by a noncommutative polynomial h(X 1 , . . . , X k ) ∈ R⟨X 1 , . . . , X k ⟩ and ⃗ G is the operator filter defined by h evaluated at ⃗T := (T G1 , . . . , T G k ) denoted Ψ(h, ⃗ T ) : R[V ] → R[V ].Exactly as in Section 2 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 at the tuple ⃗ T above.A , T B : L → L and any two signals f, g ∈ L we have ∥T A (f ) -T B (g)∥ ≤ ∥T A ∥ op ∥f -g∥ + ∥T A -T B ∥ op ∥g∥.In particular, for any two graphons A, B and any two signals X, Y we have∥T A (f ) -T B (g)∥ ≤ ∥f -g∥ + ∥T A -T B ∥ op min(∥g∥, ∥f ∥)3. For any two k-tuples of graphon shift operators ⃗ T W , ⃗ T Z , any two signals f, g ∈ L and any word α ∈ [k] d we havex α ( ⃗ T W )(f ) -x α ( ⃗ T Z )(g) ≤ ∥f -g∥ + min(∥f ∥, ∥g∥) k j=1 q j (α)∥T Wj -T Zj ∥ opwhere q j (α) 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 we have∥T W ∥ op ≤ 1 0 1 0 W (u, v) 2 dudv 1 2and the right hand side is bounded above by one since every graphon satisfies W (u, v) ∈ [0, 1].∥T A (f ) -T B (g)∥ = ∥T A (f ) -T A (g) + T A (g) -T B (g)∥ ≤ ∥f -g∥∥T A ∥ op + ∥T A -T B ∥ op ∥g∥The second inequality follows from combining the inequality that we just proved with part (1) and exchanging the roles of A and B. ∥x α (T A1 , . . . , T A k )(f ) -x α (T B1 , . . . , T B k )(g)∥ = T Aj x β (T A1 , . . . , T A k )(f ) -T Bj x β (T B1 , . . . , T B k )(g)By the second inequality in part (2) and part (1) this is quantity is bounded above by∥x β (T A1 , . . . , T A k )(f ) -x β (T B1 , . . . , T B k )(g)∥+ ∥TA j -TB j ∥op min ∥x β (TA 1 , . . . , TA k )(f )∥, ∥x β (TB 1 , . . . , TB k )(g)∥applying part (1) we know this is quantity is bounded above by∥x β (T A1 , . . . , T A k )(f ) -x β (T B1 , . . . , T B k )(g)∥ + ∥T Aj -T Bj ∥ op min (∥f ∥, ∥g∥)Applying the induction hypothesis to the first term, because β ∈ [k] d-1 , we see that this expression is bounded above by ∥f -g∥ + min(∥f ∥, ∥g∥)k i=1 q i (β)∥T Ai -T Bi ∥ op + ∥T Aj -T Bj ∥ op min (∥f ∥, ∥g∥)where q i (β) is the number of times the index i appears in the word α. For each index i ∈ [k] we haveq i (α) = q i (β) if i ̸ = j q i (β) + 1 if i = jso we conclude that the above sum equals ∥f -g∥ + min(∥f ∥, ∥g∥)k i=1 q i (α)∥T Ai -T Bi ∥ opproving the claimed inequality. ( ⃗ T W )(f ) -h( ⃗ T Z )(g) is bounded above by α∈[k] ≤d |c α | x α ( ⃗ T W )(f ) -x α ( ⃗ T Z )(g)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 C j (h).Proof of Theorem 7. Denote by ⃗ T G be the operators in the graph-tuple Ĝ and let ⃗ T Ĝ denote their induced graphon operators. If f ∈ F A is any signal then Theorem 1 implies that the following inequality holdsΨ(H, ⃗ T W )(f ) -Ψ H, ⃗ T Ĝ (i V • p V (f )) * ≤ ∥f -i V • p V (f )∥ * max b∈[B]   a∈[A] C(h b,a )   + ∥f ∥ max b∈[B]   a∈[A] k j=1 C j (h b,a )∥T Wj -T Ĝj ∥ op   .Since the points in V are equispaced, Theorem 4 implies thatΨ H, ⃗ T Ĝ (i V • p V (f )) = i V • Ψ H, ⃗ T G |V | (p V • i V • p V (f )) = i V • Ψ H, ⃗ T G |V | (p V (f ))where the last equality follows from the fact that p V • i V equals the identity map for any choice of finite set V ⊆ [0, 1]. The proof is completed by substituting this equality in the left-hand side of the previous inequality.Proof of Theorem 8. For a 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 ∥T G (N ) j -T Wj ∥ op → 0 guarantees that the upper bound we obtain converge to zero provided ∥f -i V (N ) • p V (N ) (f )∥ * converges to zero as N → ∞ or equivalently if the function f , or more precisely its components are well approximated by their local averages at the sampling points V (N ) . This is obviously true for essentially bounded functions and happens uniformly for Lipschitz functions with a common constant proving the claim. 
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 A with max-norms ∥z∥ * := maxa∈[A] ∥z a ∥ if z = (z a ) a∈[A] ∈ F A .where the norm ∥ • ∥ on the right-hand side denotes the standard L 2 -norm on F coming from the measure µ V as defined in the previous section. Fix feature sizes α 0 , . . . , α N and matrices ⃗ H := (H (j) ) j=0,...,N -1 of noncommutative polynomials in k-variables of dimensions α j+1 × α j for j = 0, . . . , N -1 and consider the operator-tuple neural networks Φ( ⃗ H, ⃗ T ) : F α0 → F αn defined by evaluating this architecture on 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 normEQUATIONin terms of the input signal difference ∥f -g∥ * and the operator perturbation size as measured by the differences ∥Z j -W j ∥ op . The main result of this Section are perturbation inequalities that depend on easily computable constants, which we call expansion constants of the polynomials appearing in the matrices ⃗ H, 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: If A, B are positive integers and z = (z a ) a∈[A] ∈ F A and R : F A → F B is a linear operator then we defineEQUATIONIf h ∈ R⟨X 1 , . . . , X k ⟩ is any noncommutative polynomial then it can be written uniquely as α c α x α where α runs over a finite support set of sequences in the numbers 1, . . . , k. For any such polynomial we define a set of k + 1 expansion constants via the formulasC(h) := α |c α | and C j (h) := α q j (α)|c α | for j = 1, . . . , kwhere q j (α) equals the number of times the index j appears in α. 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 ∥T j ∥ op ≤ 1 for j = 1, . . . , k).Theorem 1. Suppose ⃗ W and ⃗ Z are two nonexpansive operator k-tuples. For positive integers A, B let H be any B × A matrix with entries in R⟨X 1 , . . . , X k ⟩. The operator-tuple neural layer with ReLu activation defined by H satisfies the following perturbation inequality: For any f, g ∈ F A and for m := min(∥f ∥ * , ∥g∥ * ) we haveEQUATION)The proof is in Appendix C. We apply the previous argument inductively to obtain a perturbation inequality for general graph-tuple neural networks by adding the effect of each new layer to the bound. More concretely if α 0 , . . . , α N denote the feature sizes of such a network and R W and R Z denote the network obtained by removing the last layer thenCorollary 2. Let m := min ∥R ⃗ W (f )∥ * , ∥R ⃗ Z (g)∥ * .The end-to-end graph tuple neural network satisfies the following perturbation inequality:∥Φ( ⃗ H, ⃗ W )(f ) -Φ( ⃗ H, ⃗ Z)(g)∥ * ≤ ∥R ⃗ W (f ) -R ⃗ Z (g)∥ * max b∈[α N ]   a∈[α N -1 ]C(hEQUATIONCorollary 3 below shows that constraining expansion constants allows us to design operator-tuple networks of depth N whose perturbation stability scales linearly with the network depth N , Corollary 3. Suppose ⃗ W and ⃗ Z are two nonexpansive operator k-tuples. If the inequalitymax b∈[α j+1 ]   a∈[α j ] C(h (j) b,a )   ≤ 1holds for j = 0, . . . , N -1 then for m := min(∥f ∥, ∥g∥) * we have:EQUATION)4 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 to 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 a graph having the real numbers in the interval [0, 1] as vertex set. The graphon signals are the space L of square-integrable functions on [0, 1], that isL := L 2 ([0, 1]).In this Section we give a brief introduction to graphons and define graphon-tuple neural networks (WtNN), 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 on 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.W : [0, 1]×[0, 1] → [0, 1] which is measurable and symmetric (i.e. W (u, v) = W (v, u)). A graphon signal is a function f ∈ L := L 2 ([0, 1]).The shift operator of the graphon W is the map T W : L → L given by the formulaT W (f )(u) = 1 0 W (u, v)f (v)dvwhere dv = dµ(v) denotes the Lebesgue measure µ in the interval [0, 1].A graphon-tuple W 1 , . . . , W k consists of a sequence of k graphons together with their shift operators T Wi : L → L. Exactly as in Section 2 and using the notation introduced there, we define (A, B) graphon-tuple filters, (A, B) graphon-tuple neural layers with ReLu activation and graphon-tuple neural networks (WtNN) as their operator versions when evaluated at the k-tuple ⃗ W := (T W1 , . . . , T W k ).For instance, if we are given positive integers α 0 , . . . , α N and matrices H (j) with entries given by noncommutative polynomialsH (j) b,a := h (j) b,a ∈ R⟨X 1 , . . . , X k ⟩ for (b, a) ∈ [α j+1 ] × [α j] and j = 0, . . . , N -1, the graphon-tuple neural network (WtNN) defined by ⃗ H := (H (j) ) N -1 j=0 and ⃗ W will be denoted byΦ( ⃗ H, ⃗ W ) : L α0 → L α N .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 a discretization of the graphon vertex set [0, 1]. More precisely, for every integer n we fix a collection of n intervalsI (n) j := [ j-1 n , j n ) covering [0, 1) and n vertices v (n) j := 2j-1 2n ∈ I j which constitute the set V (n) ⊆ [0, 1].To compare functions on different V (n) we will use an interpolation operator i n and a sampling operator p n . The interpolation operator i n : R[V (n) ] → L extends a set of values at the points of ) ] maps a function f to its conditional expectation with respect to the I j , namely the function g ∈ R[V (n) ] given by the formula g(v j ) := Ij f (v)dv/µ(I j ) = n Ij f (v)dv. The sampling and interpolation operators satisfy the identities p nV (n) to a piecewise-constant function in [0, 1] via i n (g)(u) := n i=1 g(v (n) i )1 I (n) i (u) where 1 Z (x) denotes the {0, 1} characteristic function of the set Z. The sampling operator p n : L → R[V (n• i n = id R[V (n) ], and i n (p n (f )) is the piecewise function which on each interval I j has constant value equal to the average of f on I j . Note that i n • p n (f ) approaches any continuous function f as n → ∞.Any graph G with n vertices and shift matrix S ij ∈ [0, 1] induces a (piecewise constant) graphon W G . The graphon induced by G is given by the formulaW G (x, y) = n i=1 n j=1 S ij 1 I (n) i (x)1 I (n) j (y)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 G 1 , . . . , G k on vertex set V (n) and their induced graphons W j := W Gj the equalityT Wj = i n • T Gj n • p n holds.Moreover, this relationship extends to networks: given feature sizes α 0 , . . . , α N and matrices H (j) of noncommutative polynomials having no constant term and of compatible dimensions α j+1 × α j for j = 0, . . . , N -1 the graphon-tuple neural networkΦ( ⃗ H, ⃗ W ) : L α0 → L α N and the normalized graph-tuple neural network Φ( ⃗ H, ⃗ G/n) : R[V ] α0 → R[V ] α N satisfy the identity Φ(H, ⃗ T ) = i n • Φ(H, ⃗ T G /n) • p nwhere p n and i n are applied to vectors componentwise.Graphon norms. The space of graphons is infinite-dimensional and therefore allows for several norms. In infinite-dimensional spaces it is customary to 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 are topologically equivalent if a sequence converges in one if and only if it converges in the other). Here we describe two specific norms of interest and describe explicit mechanisms for producing converging sequences in the operator norm.The most fundamental norm on graphons is ∥W ∥ □ := supU,V ⊆[0,1] U ×V W (u, v)dudv . Known asthe cut norm, its importance stems from the fact that two graphons differing by a small cut norm must have similar induced subgraphs in the sense of the counting Lemma of Lovasz and Szegedi (see [30, Lemma 10 .23] for details).As an analytic object however, the cut norm is often unwieldy, so it is typically bounded via more easily computable norms. More precisely, the space of graphons admits two topologically inequivalent norms represented by the operator and Hilbert-Schmidt norms of graphon shift operators respectively (Example 6 shows that they are indeed inequivalent and why this is important in the present context).Recall that the operator is defined by ∥T W ∥ op := sup ∥f ∥,∥g∥≤11 0 1 0 W (u, v)f (u)g(v)dudv which is the induced norm of T W as operator from L 2 ([0, 1]) to L 2 ([0, 1]).It is topologically equivalent to the cut norm (see Appendix B). The Hilbert-Schmidt (HS) norm of T W is the ℓ 2 -norm of the eigenvalues of T W or equivalently the norm ∥W ∥ L 2 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 as limit. The family associated to a graphon provides a practical realization of the intuitive idea of a collection of graphs which "represent a common phenomenon".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 (x, y) is a given graphon. For every integer n we fix a finite set of equispaced vertices as above and a collection of intervals I j := [v j , v j+1 ) for j = 1, . . . , n -1 andI n := [0, v 1 ) ∪ [v n , 1].We will produce two kinds of undirected graphs with vertex set V (n) := {v 1 , . . . , v n }:1. A deterministic weighted graph, the weighted template graph H n with vertex set V (n) and shift operator S(v i , v j ) :=I i ×I j W (x,y)dxdy µ(Ii×Ij )on the edge (v i , v j ).2. A random graph, the graphon-Erdos-Renyi graph G n with vertex set V (n) and shift operator S(v i , v j ) ∈ {0, 1} sampled from a Bernoulli distribution with probability W (v i , v j ), 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 T W in suitable norms (see Appendix C for a proof). Note that the second part of the theorem can be seen as a consequence of the analysis in [32] as well.Theorem 5. For any positive integer n let Ĥ(n) and Ĝ(n) be the graphons induced by H n and G n .The following statements hold1. If W is continuous then ∥T W -T Ĥ(n) ∥ HS → 0 2. If W is Lipschitz continuous then ∥T W -T Ĝ(n) ∥ op → 0 almost surely.Example 6. Fix p ∈ (0, 1) and let W (x, y) = p 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 ∥T W -T Ĝ(n) ∥ op → 0 almost surely so this is a convergent graph family in the operator norm. By contrast we will show that the sequence of T Ĝ(n) does not converge to T W in the Hilbert-Schmidt norm by proving that ∥T Ĝ(n) (x, y) -T W (x, y)∥ HS > min(p, 1 -p) > 0 almost surely. To this end note that for every n ∈ N and every (x, y) ∈ [0, 1] 2 with x ̸ = y the difference |W Ĝ(n) (x, y) -W (x, y)| ≥ min(p, 1 -p) since the term on the left is either 0 or 1. We conclude that ∥T Ĝ(n) (x, y)-T W (x, y)∥ HS = ∥W Ĝ(n) (x, y)-W (x, y)∥ L 2 ([0,1] 2 ) ≥ min(p, 1-p) > 0 for every n and therefore the sequence fails to converge to zero almost surely.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 on the Hilbert-Schmidt norm are not applicable even to the simplest families of examples, namely Erdos-Renyi graphs. 
universal transferability: 
 Our next result combines perturbation inequalities for graphon-tuple networks and Theorem 4 which compares graph-tuple networks and their induced graphon-tuple counterparts resulting in a transferability inequality. As a corollary of this inequality we prove a universal transferability result which shows that every architecture is transferable in a 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 ⃗ G be a graph-tuple with equispaced vertex set V ⊂ [0, 1]. Let H be any B ×A matrix with entries in R⟨X 1 , . . . , X k ⟩ and let Ψ(H, ⃗ W ) :L A → L B (resp Ψ(H, ⃗ G) : R[V ] → R[V ]) denote the graphon-tuple neural layer (resp. graph-tuple neural layer) with ReLu activation defined by H. If Ĝi denotes the graphon induced y G i then for every f ∈ L the transferability error for f satisfiesΨ(H, ⃗ T W )(f ) -i V • Ψ H, 1 |V | ⃗ T G (p V (f )) * ≤ ∥f -i V • p V (f )∥ * max b∈[B]   a∈[A] C(h b,a )   + ∥f ∥ max b∈[B]   a∈[A] k j=1 C j (h b,a )∥T Wj -T Ĝj ∥ op   .We are now able to prove the following Universal transferability result:Theorem 8. Suppose ⃗ G (N ) := (G (N ) 1 , . . . , G (N ) k ) is a sequence of graph-tuples having vertex set V (N ) ⊆ [0, 1].If the vertex set is equispaced for every N and the sequence converges to a graphon-tuple ⃗ W in the sense that ∥T Ĝ(N) j -T Wj ∥ op → 0 as N → ∞ for j = 1, . . . ,Φ( ⃗ H, ⃗ T W )(f ) -i V (N ) Φ ⃗ H, 1 |V (N ) | ⃗ T G (p V (N ) (f )) *converges to zero as N → ∞. Furthermore the convergence is uniform among functions f with a fixed Lipschitz constant.6 Training with stability guarantees min c 1 |I| i∈I ℓ(Φ( ⃗ H(c), ⃗ T G )(x i ), y i ) s.t. ⃗ C( ⃗ H(c)) ≤ ⃗ C, ⃗ C j ( ⃗ H(c)) ≤ ⃗ C j for j = 1, . . . , k,where ℓ(•, •) is any nonnegative loss function depending on the task, and c denotes all the polynomial coefficients in the network. If we pick ⃗ C to be an all ones vector (or smaller), by Corollary 3, the perturbation stability is guaranteed to scale linearly with the number of layers N .To approximate the solution of the constrained minimization problem we use a penalty method,EQUATIONwhere p(•) is a componentwise linear penalty functionp( ⃗ C) = (p(C (d) )) N -1 d=0 with p(C (d) ) = max(0, C (d)). The stable GtNN algorithm picks a fixed large enough penalty coefficient λ and trains the network with local optimization methods. 
experimental data and numerical results: 
 We perform three experiments1 : (1) we test the tightness of our theoretical bounds on a simple regression problem on a synthetic dataset consisting of two weighted circulant graphs (see Figure Figure 2 : This is an experiment on the MovieLens 100k database, a collection of movie ratings given by a set of 1000 users [39] to 1700 movies. Using collaborative filtering techniques [19] we extract two weighted graphs that we use to predict ratings of movies by user from a held out test set. See details in Appendix D.3. We report the mean squared error (MSE) in the test set as a function of the number of training iterations (Left) from 0 to 500 and (Right) from 0 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) on various ridge-regularized versions (the legend contains the values of the chosen regularization constants).1 and Appendix D.1 for details) (2) we assess the transferability of the same model (Appendix D.2), and (3) we run experiments on a real-world dataset of a movie recommendation system where 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). 
conclusions: 
 In this paper, we introduce graph-tuple networks (GtNNs), a way of extending GNNs to a multimodal 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 transferability error goes to zero as the graph size goes to infinity. Our transferability theorem improves upon the current state-of-the-art even for the GNN case. Furthermore, our error bounds are expressed in terms of computable quantities from the model. This motivates a 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. 
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 theoretical work on stability and transferablity of GNNs. We don't identify any societal impact.Guidelines:• The answer NA means that there is no societal impact of the work performed.• 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 a 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 a generic algorithm for optimizing neural networks could enable people to 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 as 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?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 or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety 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 we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?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 or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?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/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing 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 as 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 is 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 of the data collector. 
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 an equivalent approval/review based on the requirements of your country or institution) were obtained?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. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. 
 
 Appendix: The trainable parameters of an operator network are precisely the coefficients of the noncommutative polynomials involved. For instance, if we have feature sizes α 0 , . . . , α N and all involved noncommutative polynomials have degree at most d then the number of trainable parameters of the operator network is equal tok d+1 -1 k-1 N -1 i=0 α i α i+1 . For each choice ⃗ c of such coefficients the network defines a function Φ( ⃗ H(c), ⃗ T ) : F α0 → F α N .For a fixed collection ⃗ c of coefficients (for instance the one obtained from training on the data (x i , y i ) for i ∈ I), the resulting polynomials in their respective matrices H (j) (c) allow us to evaluate the trained operator network Φ( ⃗ H(c), T 1 , . . . , T k ) on any other k-tuple of operators ⃗ M := (M 1 , . . . , M k ). Here the M j are linear maps acting on a vector space of functions L (possibly different from F) so evaluation defines a new network Φ( ⃗ H(c), ⃗ M ) : L α0 → L α N . Because the coefficients ⃗ c were obtained by training using the operators ⃗ T , this network is said to be built by transference from ⃗ T to ⃗ M .The following facts about norms in the space of graphons are well-known:1. The cut-norm is equivalent to a norm computable from the shift operator. More precisely, defineEQUATION0 1 0 W (u, v)f (u)g(v)dudvand note that it this norm is expressible in terms of T W as ∥W ∥ ♢ = ∥T W ∥ op,∞,1 which is the operator norm of T W as map from L ∞ ([0, 1]) to L 1 ([0, 1]).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 3. Proof. For any two real valued functions f j , g j on any space V the inequality| max(0, f j (u)) -max(0, g j (u))| ≤ |f j (u) -g j (u)|holds at every point. Since the left hand side equals the absolute value of a component of σ(f ) -σ(g) the claim is 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-linearity 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 ⃗ Z are non-expansive operator k-tuples. The following inequalities hold:1. For every α ∈ [k] d we have ∥x α ( ⃗ T )∥ op ≤ 1 and for every noncommutative polynomial h we have ∥h(T )∥ op ≤ C(h)2. For every α ∈ [k] d we have ∥x α ( ⃗ W ) -x α ( ⃗ Z)∥ op ≤ k j=1 q j (α)∥W j -Z j ∥ op and for every noncommutative polynomial h we have∥h( ⃗ W ) -h( ⃗ Z)∥ op ≤ k j=1 C j (h)∥W j -Z j ∥ op 3. If H is any B × A matrix with entries in R⟨X 1 , . . . , X k ⟩ then: (a) ∥Ψ(H, ⃗ T )∥ op ≤ max b∈[B] a∈[A] C(h b,a ) and (b) ∥Ψ(H, ⃗ W ) -Ψ(H, ⃗ Z)∥ op ≤ max b∈[B] a∈[A] k j=1 C j (h b,a )∥W j -Z j ∥ op .Proof.(1) The statement holds for a monomial x α because operator norms are multiplicative and each T j has ∥T j ∥ op ≤ 1 by nonexpansivity. The claim for h(x) = c α x α follows from the triangle inequality.(2) First, for any two bounded linear operators T A , T B : F → F and any two signals f, g the triangle inequality implies that∥T A (f ) -T B (g)∥ ≤ ∥T A ∥ op ∥f -g∥ + ∥T A -T B ∥ op ∥g∥.In particular, for any two nonexpansive operators T A , T B we have∥T A (f ) -T B (g)∥ ≤ ∥f -g∥ + ∥T A -T B ∥ op min(∥g∥, ∥f ∥)Applying this observation inductively to ⃗ Z, ⃗ W , any two signals f, g and any word α ∈ [k] d we havex α ( ⃗ W )(f ) -x α ( ⃗ Z)(g) ≤ ∥f -g∥ + min(∥f ∥, ∥g∥) k j=1 q j (α)∥W j -Z j ∥ opwhere q j (α) is the number of times the index j appears in the word α. Setting f = g to be any signal with ∥f ∥ ≤ 1 we conclude∥x α ( ⃗ W ) -x α ( ⃗ Z)∥ op ≤ k j=1 q j (α)∥W j -Z j ∥ opCombining the previous conclusion with the triangle inequality yields∥h( ⃗ W ) -h( ⃗ Z)∥ op ≤ k j=1 C j (h)∥W j -Z j ∥ opfor any noncommutative polynomial h. (3a) By Lemma 9∥Ψ(H, ⃗ T )∥ op = max b∈[B] a∈[A]∥h b,a ( ⃗ T )∥ op and the claim follows by applying the upper bound we just proved in part (1). (3b) By Lemma 9∥Ψ(H, ⃗ W ) -Ψ(H, ⃗ Z)∥ op = max b∈[B] a∈[A] ∥h b,a ( ⃗ W ) -h b,a ( ⃗ Z)∥ opand the claim follows from applying the upper bound we just proved in part (2).We are now ready to prove the main result of this Section, Proof of Theorem 1. By Lemma 10 we haveΨ(H, ⃗ W )(f ) -Ψ(H, ⃗ Z)(g) * ≤ ∥Ψ(H, ⃗ W )(f ) -Ψ(H, ⃗ Z)(g)∥ *By the triangle inequality the quantity above is bounded by the smallest ofEQUATIONandEQUATION)The Theorem is proven by applying Lemma 12 part (3) to the operator norms and taking the minimum of the resulting upper bounds.Remark 13. 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 k = 1, n = 1 assuming T V , T W and f ≥ g are nonnegative scalars with 0 ≤ T W ≤ T V ≤ 1 (a similar reasoning applies to the case of simultaneously diagonal nonexpansive operator tuples of any size). For a univariate polynomial h(X) = d j=0 h j X j with nonnegative coefficients we have|h(T V )(f ) -h(T V )(g)| =   d j=0 h j T j V   (f -g) ≤ d j=0 |h j |(f -g)with equality when T V = 1 and|h(T V )(f )-h(T W )(f )| = d j=0 h j T j V -T j W f = d j=0 h j jv j-1 (j) (T V -T W ) f ≤ C 1 (h)|T V -T W |fwhere 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.Lemma 14. The following statements hold:1. For every graphon W the inequality ∥T W ∥ op ≤ 1 holds. As a result, for every α ∈ [k] d and any k-tuple of graphon shift operators the inequality ∥x α (T W1 , . . . , T W k )∥ op ≤ 1 holds.We begin with the following preliminary Lemma, Lemma 17. For a positive integer n let G be a graph with vertex set V (n) and let W G be its induced graphon. The following statements hold:1. If f ∈ L then the equality T W G (f ) = i n • T G n • p n (f ) holds.More generally for any polynomial h with zero constant term we have ) ] is any function on the vertices of G and h(x) is any univariate polynomial with zero constant term thenh(T W ) = i n • h(T G /n) • p n 2. If g ∈ R[V (Gh(T W )(i n (g)) = i n (h(T G /n)(g)) .3. If σ, σ denote the componentwise ReLu functions in L and R[V ] respectively then the equality σ• i n = i n • σ holds. Proof. (1) Recall that for f ∈ L we have T W (f )(x) = 1 0 W G (x, y)f (y)dy which equals = 1 0 n i=1 n j=1 S ij 1 I (n) i (x)1 I (n) j (y)f (y)dy = = n i=1 n j=1 S ij 1 I (n) i (x) I (n) j f (y)dy = = n i=1   n j=1 S ij µ(I (n) j ) I (n) j f (y)dy/µ(I (n) j )   1 I (n) i (x) = = i n • T G n • p n (f ) (x)where the last equality holds by definition of p n and i n and because µ(I(n) j ) = 1/n for all j.For the second claim note that both sides are linear operators it suffices to prove the claim when h(x) is a monomial of degree k ≥ 1. This follows immediately by induction using the fact thatp n • i n = id R[V (n) ] for every n. (2)Apply the identity proven in part (1) to the function i n (g) and use the equalityp n • i n = id R[V (n) ] . (3) If g ∈ R[V ] then σ(i n (g)) = σ   n j=1 g(v j )1 I (n) j (x)   = n j=1 max(g(v j ), 0)1 I (n) j (x) = i n (σ(g)).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 is Lemma 17 part (1). For the second claim apply Lemma 17 inductively on layers.Proof of Theorem 5. (1) By compactness of the square [0, 1] 2 given ϵ > 0 there exists δ > 0 such that for all n sufficiently large, every rectangle I i × I j is entirely contained in balls of radius δ with the property that |W (x i , x j ) -W (a i , a j )| < ϵ whenever (x i , x j ) and (a i , a j ) are in I i × I j . In particular, at every point of each square the function deviates at most ϵ from its mean on this square proving that ∥W -Ĥ(n) ∥ L 1 ≤ ϵ. From the results summarized in Section 4 we conclude that ∥T W -T Ĥ(n) ∥ HS → 0 in the operator norm as claimed. (2) For a positive integer n let B (n) be the discretization of the graphon W from the values at V (n) × V (n) defined byB (n) (x, y) = n i=1 n j=1 W (v (n) i , v (n) j )1 Ii (x)1 Ij (y)Via the triangle inequality we estimate ∥W -Ĝ(n) ∥ ⋄ from above as the sum of ∥W -B (n) ∥ ♢ and ∥B (n) -Ĝ(n) ∥ ♢ . The first term satisfies the inequality ∥W -B (n) ∥ ♢ ≤ ∥W -B (n) ∥ L 1 and thus goes to zero by continuity of W by the argument from part (1). For the second term ∥B (n) -Ĝ(n) ∥ ♢ note that both graphons are constant in the squares I j × I k and therefore∥B (n) -Ĝ(n) ∥ ♢ = max a,b∈{0,1} n n i=1 n j=1 a i b j W (v (n) i , v (n) j ) -S (n) ij n 2where the S (n) ij are independent Bernoulli random variables with success probability W (vEQUATIONGiven ϵ > 0, let A n be the event that max a,b∈{0,1}n n i=1 n j=1 a i b j W (v (n) i ,v (n) j )-S (n) ij n 2≥ ϵ where 1/n 2 = µ(I i × I j ) for every i, j. We will show that the series n P(A n ) < ∞ concluding by the Borel-Cantelli Lemma that ∥B (n) -Ĝ(n) ∥ ♢ ≤ ϵ for all but finitely many integers n. Since ϵ > 0 was arbitrary this proves that ∥B (n) -Ĝ(n) ∥ ♢ → 0 almost surely as claimed. To verify the summability we will use a simple concentration inequality. The probability P(A n ) equalsP    a,b∈{0,1} n n i=1 n j=1 a i b j W (v (n) i , v (n) j ) -S (n) ij n 2 ≥ ϵ    which is bounded above by ≤ a,b∈{0,1} n P    n i=1 n j=1 a i b j W (v (n) i , v (n) j ) -S (n) ij n 2 ≥ ϵ   Since each of the summands is the sum of ≤ n 2 independent Bernoulli random variables shifted by their mean and divided by n 2 , Bernstein's inequality implies that the sum is bounded above by2 n+1 e -n 2 ϵ 2 2(1+ϵ/3) = e -n 2 ϵ 2 2(1+ϵ/3) +(n+1) log(2)this quantity is summable by the ratio test proving the claim. From the results summarized in Section 4 we know that ∥ • ∥ ♢ is topologically equivalent to ∥ • ∥ op and we conclude that ∥T W -T Ĝ(n) ∥ op → 0 proving the theorem.Remark 19. It is necessary to add some assumption on W for the conclusions of the Lemma above to hold. Forinstance if W is just in L 2 ([0, 1] × [0, 1]) then it can be modified in the countable, and thus Lebesgue measure zero, set n V (n) × V (n) without altering the operator T W making an approximation scheme as suggested above impossible.The code for experiments on stability for graph tuples and experiments on transferability for sparse graph tuples are available here: https://github.com/Kkylie/GtNN_weighted_circulant_graphs.git. And the code for experiments on real-world data from a movie recommendation system is available here: https://github.com/mauricio-velasco/operatorNetworks.git.For this experiments we consider a weighted circulant graph of size n with shift matrix S (l) asS (l) ij =    p, if i = j (1 -p)/2, if |i -j| mod n = l 0,otherwise.We generate our data pair(x i , y i ) ∈ F × F with F = R[V ] as y i = [0.76S (l2) S (l1) + 0.33S (l1) S (l2) + 0.3(S (l1) ) 3 ]x i + ϵ i ,where each value of x i is uniformly distributed between [0, 1], ϵ i ∈ F is normal distributed with standard deviation σ = 0.1, and we pick n = 293, p = 0.05, l 1 = 1, and l 2 = 30. Noted that both input and output have only one feature, i.e., α 0 = α N = 1. We train our model with 800 training data I and test it on 200 testing data I test . We use MSE loss, and use ADAM with learning rate 0.01, β 1 = 0.9 and β 2 = 0.999 to train our models. Running these experiments took a few hours on a regular laptop (just CPU).Denote T 1 and T 2 as the shift operator corresponding to S (l1) and S (l2) respectively. Recall from the main text (Section 7) that we consider four different models: (i) one layer unconstrained GtNN (i.e., λ = 0 in (6)), (ii) one layer stable GtNN (with λ = 10), (iii) two layers GtNN with number of hidden feature α 1 = 2, and (iv) two layers unconstrained GtNN (with λ = 10 and α 1 = 2). For all four models, we set the non-commutative polynomial h(T 1 , T 2 ) to be any polynomial of degree at most 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 be at most half of the corresponding expansion constants obtained after training the unconstrained model. Specifically, let ⃗ C( ⃗ H (i) ) and ⃗ C j ( ⃗ H (i) ) denotes the resulting expansion constants vectors for model (i). Then, we set the constraints for model (ii) to be ⃗ C = ⃗ C( ⃗ H (i) )/2 and ⃗ C j = ⃗ C j ( ⃗ H (i) )/2 for j = 1, 2. Similarly, we set the constraints for model (iv) to be ⃗ C = ⃗ C( ⃗ H (iii) )/2 and ⃗ C j = ⃗ C j ( ⃗ H (iii) )/2 for j = 1, 2.Figure 1 shows the empirical stability metrics and the corresponding upper bounds as a function of the number of epochs for the one layer models (i) and (ii).As we see in the proof of Theorem 1 (equation (7) and equation ( 8)), the equation ∥Ψ(H, ⃗ T )∥ op = ∥h( ⃗ T )∥ op shows the output perturbation due to the perturbation from input signal, and∥Ψ(H, ⃗ W ) -Ψ(H, ⃗ Z)∥ op = ∥h( ⃗ W ) -h( ⃗ Z)∥ op shows the output perturbation due to the perturbation from the graph. Meanwhile, C(h) and C j (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 is 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 GtNN is 0.6867, while for stable GtNN 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 1 (right) the stable GtNNs increases the stability under graph perturbations, especially in the 2-layer model.We test the transferability behavior on the weighted circulant graph model from Appendix D.1. 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. Figure 3 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.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 [39] 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 [19] we center the data (by removing the mean rating of each user from all its ratings) and try to learn a deviation from the mean rating function. More precisely, letting U be the set of users, we wish to learn the map ϕ : R[U ] → R[U ] which, given a partial deviation from the mean ratings function f : U → 1, 2, . . . , 5 (with missing data marked as zero) produces the full rating function f = ϕ(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 [19] 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 ϕ 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 ϕ via graph-tuple neural networks on 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 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 is over-trained as in the right plot of Figure 2 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. some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. Justification: We conducted the research ethically.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).Code available: https://github.com/Kkylie/GtNN_weighted_circulant_graphs and https://github.com/mauricio-velasco/operatorNetworks 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 1. The tightness of the bounds is only demonstrated through numerical experiments rather than formal theoretical analysis.
2. 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.
3. The results lack support from real-world experiments.
questions: 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?
2. Is it possible to extend the current work to *sparse* graphs when there are no induced graphons?
limitations: limitations: The authors adequately addressed the limitations of the work and clearly stated the assumptions.
paper_summary: paper_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.
strength_weakness: strength_weakness: 1.	No experiments on real data to prove the transferability and stability gain using their method compared to GNN.
2.	The theoretical background knowledge is not adequately provided.
3.	Lacking proper reasoning phases to connect each sections.
questions: questions: 1.	Can this method be viewed as a training strategy that improves every existing Graph Mining method?
2.	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.
3.	What is the convergence order, i.e. O(N^k), of the quantity when N goes to infinity?
limitations: 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.
paper_summary: paper_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).

In 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.)

Overall, this paper provides a solid, easily understandable, theoretical framework for an important problem (learning on multigraphs). Acceptance is recommended.
strength_weakness: strength_weakness: 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

Corollaries 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.)

A more detailed explanation of Example 6 would be helpful. I had to read it several times in order to understand

Having some experiments with real data would be helpful (although I do recognize that the contributions of this paper are primarily theoretical).

A short conclusion would be nice in the camera ready copy.

Line 494: It is not clear where "block operator" norms were introduced

In 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.

Lemma 14 is out of place, it should be before the proof of Lemma 14 (which means it would then become Lemma 13) 

More details should be added to the proof of theorem 7

Releasing a colab notebook after the review process is okay, but an anonymous github would have been better to improve upon reproducibility

Minor:

Line 91: "behavior than" should be "behavior as"

Line 97: the phrase "loopless" could be confusing. Should make it more clear you mean no self loops

The 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. 

Line 167: Cartesian should have a capital C. The authors should check throughout for other words derived from last names, e.g., Euclidean or Laplacian

Line 237: V^{(s)} should be V^{(n)}, right?

Line 313: "Corollary" should be "corollary"

Linne 494: "Lemma" should be "lemma"
questions: questions: Does any of the graphon theory extend to random graphs derived from graphons?

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 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

How does theorem 1 compare with theorem 2 of this paper https://arxiv.org/pdf/2108.09923

Is it possible to define things in any sort of Fourier domain?
limitations: limitations: Yes

Comments: title: Question to reviewers
Reply to rebuttal
Good Job
Anonymous Github repositories
Comments accompanying the rebuttal
comment: We thank the reviewers for their time and the constructive and positive feedback we received.
Since all of them requested experiments on real data, we'd like to ask them whether the experiment on the movies dataset we provide in this global rebuttal satisfies their request.
Thank you to the authors for your rebuttal. After reading the rebuttal, I decide to maintain my score.
I thank the authors for the detailed responses and agreeing to address some of the criticism. I maintain my positive score of the paper.
I thank the authors for their thorough response.
We have added two anonymous Github repositories containing the scripts used for the article:

https://anonymous.4open.science/r/GtNN_weighted_circulant_graphs-27EB 
https://anonymous.4open.science/r/operatorNetworks-508F
**New paragraph referring to related work in the intro**

The goal of this paper is to extend the mathematical theory of GNNs to account for multimodal graph settings. The most closely related existing work is the algebraic neural network theory of Parada-Mayorga, Butler and Ribeiro [PMR1][PMR2][PMR3] who pioneer the use of algebras of non-commuting operators. The setting in this paper could be thought of as a special case of this theory. However, there is a crucial difference: whereas the main results in the articles above refer to the Hilbert-Schmidt norm, we introduce and analyze block-operator-norms on non-commutative algebras acting on function spaces. This choice allows us to prove stronger stability and transferability bounds that when restricted to classical GNNs improve upon or complement the state-of-the-art theory. In particular, we complement work in \cite{ruiz2021graph} by delivering bounds that do not exhibit no-transferable energy, and we complement results in \cite{maskey2023transferability} by providing stability bounds that do not require convergence. Our bounds are furthermore easily computable in terms of the networks' parameters improving on the results of~\cite{PMR2} and in particular allow us to devise novel training algorithms with stability guarantees.

**New writing of example 6:**

Fix $p\in (0,1)$ and let $W(x,y)=p$ for $x\neq y$ and zero otherwise. The graphon Erdos-Renyi graphs $G^{(n)}$ constructed from $W$ as in $(2)$ above are precisely the usual Erdos-Renyi graphs. Part (2) of the sampling Lemma guarantees that
$T_W$ converges to $T_{\hat{G}^{(n)}}$ almost surely in the operator norm. By contrast we will show that the sequence  **does not converge** to $T_W$ in the Hilbert-Schmidt norm by proving that $\|T_{\hat{G}^{(n)}}(x,y)-T_W(x,y)\|_{\rm HS}>\min(p,1-p)>0$

almost surely. To this end note that for every $n\in \mathbb{N}$ and every $(x,y)\in [0,1]^2$ with $x\neq y$ the difference $|W_{\hat{G}^{(n)}}(x,y)-W(x,y)|\geq \min(p,1-p)$ since the term on the left is either $0$ or $1$. We conclude that 

$\|T_{\hat{G}^{(n)}}(x,y)-T_W(x,y)\|_{\rm HS} = \|W_{\hat{G}^{(n)}}(x,y)-W(x,y)\|_{L^2([0,1]^2)}\geq \min(p,1-p)>0$

 for every $n$ and therefore the sequence fails to converge to zero almost surely.


**Short Conclusion (to be added at the end of the article)**

In this paper, we introduce graph-tuple networks, a way of extending GNNs to the multimodal graph setting through the use tuples of non-commutative operators endowed with appropriate block-operator norms.
We show that GtNNs have several desireable  properties such as stability to perturbations and a Universal transferability property on convergent graph-tuples, where the transferability error goes to zero as the graph size goes to infinity.
Our transferability theorem improves upon the current state even for the GNN case.
Furthermore our error bounds are expressed in terms of computable quantities from the model.
This motivates our novel algorithm to enforce stability during training.
Experimental results show that our transferability error bounds are reasonably tight, and that our algorithm increases the stability with respect to graph perturbation.
In addition, they demonstrate that the transferability theorem holds even for sparse graph tuples.
Finally, the experiments on the movie recommendation system suggest that allowing for architectures based on GtNNs is of potential advantage in real-world applications.