Limitless Stability for Graph Convolutional Networks 
Authors: Christian Koke
Venue: ICLR 2023 poster (2023)
Keywords: Graph Convolutional Networks
Graph Neural Networks
Stability
Transferability
Spectral Graph Theory
Rigorous Proofs

Abstract: This work establishes rigorous, novel and widely applicable stability guarantees and transferability bounds for general graph convolutional networks  -- without reference to any underlying limit object or statistical distribution. Crucially, utilized graph-shift operators are not necessarily assumed to be normal, allowing for the treatment of networks on both directed- and undirected graphs within the developed framework. In the undirected setting, stability to node-level perturbations is related to an 'adequate spectral covering' property of the filters in each layer. Stability to edge-level perturbations is discussed and related to properties of the utilized filters such as their Lipschitz constants. Results on stability to  vertex-set non-preserving perturbations are obtained by utilizing recently developed mathematical-physics based tools. As an exemplifying application of the developed theory, it is showcased that
general graph convolutional networks utilizing the un-normalized graph Laplacian as graph-shift-operator  can be rendered stable to collapsing strong edges in the underlying graph if filters are mandated to be constant at infinity. These theoretical results are supported by corresponding numerical investigations showcasing the response of filters and networks to such perturbations. 

Under review as a conference paper at ICLR 2023
LIMITLESS STABILITY FOR GRAPH CONVOLUTIONAL NETWORKS
Anonymous authors Paper under double-bling review
ABSTRACT
This work establishes rigorous, novel and widely applicable stability guarantees and transferability bounds for graph convolutional networks - without reference to any underlying limit object or statistical distribution. Crucially, utilized graph- shift operators (GSOs) are not necessarily assumed to be normal, allowing for the treatment of networks on both directed- and for the first time also undirected graphs Stability to node-level perturbations is related to an 'adequate (spectral) covering' property of the filters in each layer. Stability to edge-level perturbations is related to Lipschitz constants and newly introduced semi-norms of filters. Results stability to topological perturbations are obtained through recently developed mathematical- physics based tools. As important and novel example, it is showcased that graph convolutional networks are stable under graph-coarse wwwrse-graiiinnngggg procedures (replacing
sub-graphs by single nodes) precisely if the GSO is the graph Laplacian and filters are regular at infinity. These new theoretical results are supported by corresponding numerical investigations.
INTRODUCTION
Graph Convolutional Networks (GCNs) (Kipf & Welling 2017 Hammond et al. 2011: Defferrard jet al. (016)) generalize Euclidean convolutional networks to the graph setting by replacing con- volutional filters by functional calculus filters; i.e. scalar functions applied to a suitably chosen graph-shift-oprator capturing the geometry of the underlying graph. A key concept in trying to understand the underlying reasons for the superior numerical performance of such networks on graph learning tasks (as well as a guiding principle for the design of new architectures) is the concept of stability. In the Euclidean setting, investigating stability essentially amounts exploring the variation of the output of a network under non-trivial changes of its input (Mallat 2012] Wiatowski Bölcskei 2018). In the graph- setting, additional complications are introduced: Not only input signals, but now also the graph shift operators facilitating the convolutions Even worse, there might also occur changes in the topology or vertex sets of the investigated graphs e.g. when two dissimilar graphs describe the same underlying phenomenon under which graph convolutional networks should also remain stable. This last stability property is often also referred to transferability (Levie et al., 2019a). Previous works investigated stability under changes in graph-shift operators for specific filters (Levie et al.] 2019b) Gama et al.] (020) or the effect of graph-rewiring when choosing a specific graph shift operator (Kenlay et al. [02I]. Stability to topological perturbations has been established for (large) graphs discretising the same underlying topological space (Levie et al.; 2019a), the same graphon (Ruiz et al. 2020 Maskey et al. 202T) or
the graphs may vary.
for graphs drawn from the same statistical distribution (Keriven et al.
2020
Gao et al. (021).
Common among all these previous works are two themes limiting practical applicability: First and foremost, the class of filters to which results are applicable is often severely restricted. The same is true for the class of considered graph shift operators; with non-normal operators (describing directed graphs) either explicitly or implicitly excluded. Furthermore when investigating transferability properties - results are almost exclusively available under the assumption that graphs are large and either discretize the same underlying 'continuous' limit object suffieciently well, are drawn from the same statistical distributions. While these are of course relevant regimes, they do not allow to draw conclusions beyond such asymptotic settings, and are for example unable to deal with certain spatial graphs, inapplicable to small-to-mede medium sized social networks and incapable of capturing the inherent multi-scale nature of molecular graphs (as further discussed below). Finally, hardly any

---

Under review as a conference paper at ICLR 2023
work has been done relating the stability to input-signal perturbations network properties such as the interplay of utilized filters or employed non-lincarities. The main focus of this work is to provide alleviation in this situation and develop 'general theory of stability" for GCNs agnostic to the types of utilized filters, graph shift operators and non-linearities; with practically relevant transferability guarantees not contingent on potentially underlying limit objects. To this end, Section 2 recapitulates the fundamentals of GCNs in a language adapted to our endeavour. Sections and
4 discuss stability to node- and edge-level perturbations. Section 3 discusses stability to structural Perturbations. Section O discusses feature aggregation and Section provides numerical evidence.
2
GCNS VIA COMPLEX ANALYSIS AND OPERATOR THEORY
Throughout this work, we will use the label G to denote both a graph and its associated vertex set. Taking a signal processing approach, we consider signals on graphs as opposed to graph embeddings:
Node-Signals: Node-signals a graph are then functions from G the complex numbers; i.e. elements of GIGI (with |G] the cardinality of G). We allow nodes E G in given graph to have weights μ4 not necessarily equal to one and equip the space CIGI with an inner product according to (f.9) = EE pz) to account for this. We denote the hence created Hilbert space by (G).
Characteristic Operators: Fixing an indexing of the vertices, information about connectivity within the graph is encapsulated into the set of edge weights, collected into the adjacency matrix W and (diagonal) degree matrix D. Together with the weight matrix M := diag ((p))__)) 1). various
standard geometry capturing characteristic operators - such as weighted adjacency matrix M M graph Laplacian A == MD W) and normalized graph Laplacian L == -- W) D-> can then be constructed. For undirected graphs, all of these operators are self-adjoint. On directed graphs, they need not even be normal (7*T = T7*). We shall remain agnostic to the choice of characteristic operator; differentiating only between normal and general operators in our results.
Functional Calculus Filters: A crucial component of GCNs are functional calculus filters, which arise from applying a function y to an underlying characteristic operator T; creating a new operator g(T). Various methods of implementations exist, all of which agree if multiple are applicable:
GENERIC FILTERS: If (and only if) T is normal, we may apply generic complex valued functions
9 to T: Writing normalized eigenvalue-eigenvee
pairs of I as (A,, ot) one defines g(T')
))) for any v E (G). One has IT) = supX (g())), with (T)) denoting the spectrum of T. If g is bounded, one may obtain the T T-indepennent bound [g(()) op & [g] z. Keeping mind that g being defined all of (T') (as opposed to all of C) is clearly sufficient, we define a space of filters which will harmonize well with our concept of transferability discussed in Section 5 The introduced semi-norm -oomm will quantify the stability to perturbations in coming sections.
E (ox) g(,)
Definition 2.1. Fix w C and C > O. Define the space 3.00 of continuous filters on Cf(w w). to be the space of multilinear power-series' g(=) = Ep, Auv (w (w z)- for which the semi-norm [g] gront En 1n v|Cutu-? lapul finite.
Denoting by (w) S C the open ball of radius around w, one can show that for arbitrary 5 > 0 and every continuous function g defined on C\ (B, (w)) u (w)) which is regular at infinity - i.c. satisfies lim,-+a g(r2)
E C independent of which 2 * is chosen there is function f E F so that [=() - g(=)| < ô for all z (w) v B, (w)). In other words, functions in cont can approximate a wide class of filters to arbitrary precision. More details are presented in Appendix B
ENTIRE FILTERS: I' is not necessarily normal, one might still consistently apply entire (i.c. everywhere complex differentiable) functions to T' Detail details the mathematical background are given in Appendix C Here we simply note that such a function is representable as an (everywhere convergent) power series g(2) Σx= af=* so that we may simply set g(T) Σx ag T For the norm of the derived operator one easily finds [l)( Σx Jag [[T | using the triangle
2

---

Under review as a conference paper at ICLR 2023
inequality. While entire filters have the advantage that they are easily and efficiently implementable making use only of matrix multiplication and addition - they suffer from the fact that it is impossible to give a [2% op independent bound for lT) op as for continuous filters. This behaviour can be traced back to the fact that no non-constant bounded entire function exists (Bak & Newman 2017).
HOLOMORPHIC FILTERS: To define functional calculus filters that are both applicable non- normal T and boundable somewhat more controlably in terms of T, one may relax the condition that g be entire to demanding that g complex differentiable (i.e. holomorphic) only on an open subset U _ C of the complex plane. Here we assume that U extends to infinity in each direction (i.e. is the complement of a closed and bounded subset of C). For any g holomor- phic on U and regular at infinity we set (with (zld T)- the so called reolvent of T at 2)
ÿ 9(2) (=Id- T)- dzz
g(T) :- g00) Id
8D
2mi
a(T)
0D
a0
for any T whose spectrum a (T) is completely contained in U. Here
we have used the notation g(00) lim 9(rz) and taken D to open set with nicely behaved boundary 2D (more precisely a Cauchy domain; e.f. Appendix Cp. We assume that D completely contains o (T) and that its closure D is completely contained in U. The orientation of the boundary @ is the usual positive orientation on D (such that D 'is on the left' of dD; cf. Fig.
U
Figure 1: Set- Visuuaaisssss
D. Using elementary facts from complex analysis it can be shown that the resulting operator g(T) in LL is independent of the specific choice of D (Ginler 1966). While we will present results below in terms of this general definition remaining agnostic to numerical implementation methods for the most part- - it is instructive to consider a specific exemplary setting with definite and simple numerical implementation of such filters: To this end, chose an arbitrary point E C and set U C [w] in the definitions above. Any function g that is holomorphic on U and regular at op may then be represented
by its Laurent series, which is of the form g(2) -k= bf(2 w) (Bak Newman 2017). For
any T with (T) = U (i.e. w & a (T)) evaluating the integral in ① yields (c.f. Appendix C
8 bg (T -II-
T(T)
(2)
Such filters have already been employed successfully, e.g. in the guise of Cayley filters Levie et al.) 2019c), which are polynomials in z+2
z-1 1 + .-..
21 We collect them into a designated filter space:
Definition 2.2. For a function g(2) Σx k= (g - w) on U ==
CM(w) define the semi-norm
[|g]] gf
hot
Σ [ for C > O. Denote the set of such for which || w.C < oc by Phot.
In order to derive [T' -nnieeppennent bounds for [T) we will need to norm-bound the resolvents
appearing in [ and (2) If T is normal, we simply have [(IId- (o -1 lop = 1/dist(z, or (T)). In the general setting, following Post (2012). we call any positive function "r satisfying (=Id-11
&
7r(2) on (T") a resolvent profile of T', Various methods (e.g. SZzhhr (2014): MichaelGil (012))
to find resolvent profiles. Most notably Bandtlow (2004b) gives a resolvent profile solely in terms of 1/dist(z, a (T)) and the departure from normality of T. We then find the following result:
Lemma 2.3. For holomorphic g and generic T' we have (T) & lg(()))+
2F Sep lg(=)
Furthermore we have for any T with (T(W)) & C, that [g( llop & o b.g. as long as y shot.
Lemma 2.3 (proved in Appendix D finally bounds [T) lop independently of T, as long as appearing resolvents are suitably bounded; which importantly does not force [T||op to be bounded.
Non-Linearittie & Connecting Operators: To each layer of our GCN, we associate a (possibly) non-linear and Ln.-Lppchiize
function Pn. C C satisfying pm, = which acts point-wise on signals in E (G.). This definition allows to choose P., | ReLu, /d or any sigmoid function shifted to preserve zero. To account for recently proposed networks where input- and "processing" graphs are decoupled (Alon& & Yahav |021 Topping al. (021), and graph pooling layers (Lee et al. 2201)), we also allow signal representations in the hidden network layers n to live in varying graph signal spaces (2 (G,).. Connecting operators are then (not necessarily linear) operators
3

---

Under review as a conference paper at ICLR 2023
PA ((Gn-))-B(GG. connecting the signal utilized of subsequent layers. We assume them to be
R, Lipschitz-continune Px()) Pa(g))le Pr(,))le(,,,1) 1) & Rallff - gle))))) and triviality preserving (0) 0). For our original node-signal space we also write (G) = (Go).
Graph Convolutional Networks:
A GCN with N layers is then constructed as follows: Let us denote the width of the network layer by Kn- The collection of hidden signals in this layer can then be thought of single element of
Pn (G..)
(G,)
(G,n1) Pr (3(Cn)
Ln == + (G.). KE
Pn ((G.)
(G.))
Pr. (G,)
Further let us write the collection of functional calculus filters utilized to generate the repre- sentation of this layer by (.) & & Kn-1;1 1 & i K,). Further denoting the char- acteristic operator of this layer by Tn. the update rule (c.f. also Fig. 2 from the representation in Ln- Ln is then defined each constituent in the direct sum Ln as
((Gn-1)
Pn
(G.)
((G.)
Figure 2: Update Rule for a GCN
f7t Pn+1
9
1 (I+1
v1 viisa Kn.
We also denote the initial signal space by Lm := Lo and the final one by Lou == IN.. The hence constructed map from the initial to the final space is denoted by + Lia Loat
STABILITY INPUT SIGNAL PERTURBATIONS
In order to produce meaningful signal representations, a small input signal change should produce only small variation in the output of our GCN, This property is quantified by the Lipschitz constant of the map & associated to the network, which is estimated by our first result below.
Theorem 3.1. With the notation of Section 2 let ΦN Lin Lou be the map associated to
N-layer GCN, We have with B, : (ST Ejek,,, Σiek. l0 (2) 12 for all f, h E Lin that
(N) T (n))ll
I IIf h hl.2.
1--1
T, is normal. For general Tn we have for all (9ig) entire, holomorphic and in Phot respectively:
JEK ΣiEK, ((ag) )al T
Ba :
jek Ka-i EiEK. (00) 2x SoD mr(z)/ Ejeka. EiEK. (=)
IeK,, LiEK,
Shhot
Appendix El contains the corresponding proof and discusses how the derived bound are not necessarily tight for sparsely connected layers. After Lipschitz constants of connecting operators and non- linearities are fixed, the stability constant of the network is completely controlled by the { {B,, ): which for normal T, in turn are controlled by the interplay of the utilized filters on the spectrum of Tu. This allows to combine filters with (T,) l (X)] O(1) but supported on complimentary parts of the spectrum of T, while still maintaining B, = O(1) instead O( P(VK,, Kn, Kn-1). In practice one might thus penalize multippe covering' of the spectrum by more than filter at time during training in order to increase stability to input signal perturbations. Tú is not normal but filters are holomorphic, an interplay persists with filters now evaluated on curve and at infinity.
4 STABILITY TO EDGE PERTURBATIONS
Operators capturing craph-geometrics might only be known approximately in real world tasks; e.g. if edge weights are only known to certain level of precision. Hence it is important that graph
4

---

Under review as a conference paper at ICLR 2023
convolutional networks be insensitive to small changes in the characteristic operators {Tn). Since consider graphs with arbitrary vertex weights 1 we also have to consider the possibility that these weights are only known certain level of precision. In this case, not only do the characteristic operators Tn Tr differ, but also the the spaces (G), (G)) on which they act. To capture this setting mathematically, we assume in this section that there is a linear operator J : (((G)) (G) facilitating contact between signal spaces (of nec-nscessarlly the same dimension). We then measure closeness of characteristic operators in the respective spaces by considering the generalized norm- difference J[ - J)ll: with J translating between the respective spaces. Before investigating the stability of entire networks we first comment on single-filter stability. For normal operators we then find the following result, proved in Appendix A building on ideas first developed in (Wihler) 2009).
Lemma 4.1. Denote by | r the Frobenius norm and let T and T be normal on L (² and ((G) respectively. Let be Lipschitz continuous with Lipschitz constant Dg. For any linear J : (G) (G) we have [[g(T)J - FF & DyITJ - JT
Unfortunately, scalar Lipschitz continuity only directly translates to operator functions if they are applied to normal operators and when using Frobenius norm (as opposed to e.g. spectral norm). For general operators we have the following somewhat weaker result, proved in Appendix
Lemma 4.2. Let T,T be operators on on (G) (()) with |T |oop & &C Let J
(G) - (G) be linear. With Kg 2म Sep (=))) [z)] for holomorphic and = = loCk- for entire, we have (lg(T) Jg(TT) op < Kg JT TJllop-
Each Kg itself is interpretable as a semi-norm. For GCNs we find the following (c.f. Appendix F):
Theorem 4.3. Let N, N be the maps associated to N-layer graph convolutional networks with the same non conlineariites and filters, but based on different graph signal spaces (C) ((G). characteristic operators Tn, Fn and connecting operators Pn, Pa. Assume B,,, B, & B as well as R., Rr & R 0 and all e Assume that there are identification operators Jn : (G.. (G,,) (0 < N) commuting with non-lineessties and connecting operators in the sense of Pn - P. P.P.lll = 0 and (I. - JaPm(s)) (e(...))) = O. Depending on whether normal or arbitrary characteristic operators are used, define D := Ejek.. Σiek, D2 9" or D = EjjKnn Kg Choose D such that Dn D for all n. Finally assume that |, - Jal & 8 and with F if both operators are normal and * = op otherwise. Then we have for all f E Li and with In the operator that the K₂ copies of Jn induce through concatenation that ( (uf) IN
and Ln for some B, R,
N DRL (BRL) N-1 2l
The result persists with slightly altered constants, if identification operators only almost commute with non-linearities and/or connecting operators, Appendix further elucidates. Since we estimated various constants (B,, D.....) of the individual layers by global ones, the derived stability constant is clearly not tight. However it portrays requirements for stability to edge level perturbations well: While the (spectral) interplay of Section 3 remains important, it is now especially large single-filter stability constants in the sense of Lemmata and 4.2 that should be penalized during training.
STABILITY TO STRUCTURAL PERTURBATIONS: TRANSFERABILITY
While the demand that [ī. JT' be small in some norm is well adapted to capture some notions of closeness of graphs and characteristic operators, it is too stringent to capture others. As an illustrative example, further developed in Section 5.2 and numerically investigated in Section below, suppose we are given connected undirected graph with all edge weights of order O(1/5). With the Laplacian as characteristic operator (governing heat-flow in Physics (Cole) 201 we may think of this graph as modelling an array of coupled heat reservoirs with edge weights corresponding to heat-conductivittis. As 1/8 - 30, the conductivities between respective nodes tend to infinity, heat exchange is instantancous and all nodes act as if they are fused together into single large entity with the graph together with its characteristic operator behaving as an effective -ie-imensioonl system. This 'convergent' behaviour is however not reflected in our characteristic operator, the graph Laplacian
5

---

Under review as a conference paper at ICLR 2023
As: Clearly | op 1/6 |&i op 00 as 1/8 - oc. Moreover, we would also expect Cauchy- like behaviour from a conveegeet system', in the sense that if we for example keep 1/6g - 1/6, = constant but let (1/62), (1/6,)
by triangle-inequallin argument. However, we clearly have | - As, lop 11/6- 1/66| A op = | which does not decay. The situation is different however, when considering resolvents of the graph Laplacian. An easy calculation (c.f. Appendix H) yields [[ As,)- (wId - (ild-As)""
would expect A., As, lop
lop = O 66) so that we recover the expected Cauchy behaviour. What is more, we also find the convergence (wId - As) - Po (w - 0) where Po denotes the projection onto the one- me-dimensional lowest lying eigenspace of the Ass (spanned by the vectors with constant entries). We may interpret (w-0)- as the resolvent of the graph Laplacian of a singleton (since such Laplacian is identically zero) and thus now indeed find our physical intuition about convergence to a one-dimensional system reflected in our formulae. Motivated by this example, Section 5. develops general theory for the difference in outputs of networks evaluated on graphs for which the resolvents R == (wid - T) and R == [wId- T of the respective characteristic operators are close in some sense. Subsequently, Section thh further develops our initial example while also considering an additional setting.
5.1 GENERAL THEORY
Throughout this section we fix a complex number w e C and for each operator T assume w, (T). This is always true for w with |س] > [T op. but if T is additionally self adjoint one could set w = i. T is non-negative one might choose Lemma 4.1 can always be satisfied if we chose J = O. To exclude this case where the application of J corresponds to losing too much information we follow Post (2012) in making the following definition:
(-1)). As first step, we then note that the conclusion of
Definition 5.1. J/ ((G)- - ((G) and J: (() (G) be linear, and let T (T) be operators on (L(G)) (G))). We say that J and J are e-quasi-unitary with respect to T, T and w if
|Jflec) {2fe
I( - (U- < <dfle(a)
I(dd- - JJJRafle & <dfeeG) I(Id- - R ((G) & <dlullerry
(4)
The motivation to include the resolvents in the norm estimates 44 comes from the setting where
= A is the graph Laplacian and w = (-1). In that case, the left equation in (4 is for example
automatically fulfilled when demanding Il(Td JJ)
& <(]s]2 + & (J)) 7 with Es())
<, A ()(G)) the (positive) energy form induced by the Laplacian A Post 2012 This can thus be interpreted as a relaxation of the standard demand [(Td - JJ)llop & c. Relaxing the demands of Section 4 we now demand closeness of resolvents instead of closeness of operators:
Definition 5.2. If, for E C and linear J : :((G) - (G) the resolvents Rw and Ri satisfy [[RRJ-JRR ( & <dffleec for all f (G), T and T are called w-c-close with identifica- tion operator J. If additonally JR (()) f le()) they are doubly w-e-close.
Our first result establishes that operators being (doubly- --ooll--------seee indeed has useful consequences:
Lemma 5.3. Let T (?) be operators (G) (62 (7)). If these operators are w-e-close with identification operator J, and RRllop: [R & we have [| (((0))gg(())J J(T) & K, I(R J Jlp with Kg Kg llgl Shat if g Ihol N.C and K2 loll for T, T normal and doubly w-e-close.
1 2n Sa + |z - w/>((=)) + |z ( for holomorphic g.
This result may then be extended to entire networks, as detailed in Theorem 5.4 below whose statement persists with slightly altered stability constants, if identification operators only almost commute with non-linearities and/or connecting operators. Proofs are contained in Appendix [
Theorem 5.4. Let NN, dx be the maps associated N-layer graph convolutional networks with the same non-linearities and functional calculus filters, but based on different graph signal spaces (G.), e (Gn), characteristic operators T,, F, and connecting operators P,, P,.. Assume B,, B,, & B well Rn, Rr R and I., & L for some B, R, T. 0 and all > 0. Assume that

---

Under review as a conference paper at ICLR 2023
there are identification operators Jn ((n)) - ((Ōn) (0 $ n & N) commuting with non- linearities and connecting operators in the sense of -
0 and Pn(Jn))
(fllea.)) 0. define D2 :- Σjsk..1 Liek, K² with kg; as in Lemma 5.3 Choose D such that D, D for all Finally assume that ([] -n)-1 (wId T J lol $ 6. If filters in $0.0 are used, assume additionally that [ 1))= ((wld ((wId-Tn)) " $ c. Then we have for all f E Lin and with In the operator that the Kn copies of Jn induce through concatenation that N (aaff-Jn40mm INDN N (BRL(BRL)) (BRL) -1.fll.2.. C
5.2 EXEMPLARY APPLICATIONS
Collapsing Strong Edges: We first pick our example from the beginning of section 5 up again and generalize it significantly: We now consider the graph that we collapse to single node to be sub-graph (of strong edges) embedded into a larger graph. Apart from coupled heat reservoirs, this setting also e.g. captures the grouping of close knit communities within social networks into single entities, the sale--transition of changing the description of (the graph of) molecule from individual atoms interacting via the coulomb potential Z, Zz R (with R the distance and Z1, Zz atomic charges) to the interaction of (functional) groups comprised of closely co-located atoms, or spatial networks weights are set e.g. inverse distances. In what follows, we shall consider two graphs with vertex sets G and G. We consider G to be a subset of the vertex set & and think of the graph corresponding to G as arising a collapsing procedure from the 'larger' graph G.
More precisely, we assume that the vertex set G can be split into three disjoint subsets G = Geain UGGreek 3 (c.f. also Fig. We assume that the adjacency matrix W when restricted to Latin vertices or a Latin vertex and the exceptional node '*' is of order unity (War ab; W.. a+ = O(1), Va, b E Grain). For Greek indices, we assume that we may write Was was and W Sg* such that (Was, Was = (1) for all a, B e GGne We also assume that the sub-gras sub-graph corresponding vertices in Goreek J(+}} connected. We then take = GLain U(+} (c.f. again Fig, 3. The adjacency ma- trix W on this graph is constructed by defining Wab Wab, Va, b e Grain and setting (with Wa. = W.a)
a
b
d
*
Wa. Wai Wa.
Ws. Wy
Wac W...
W.o = W., + Σ Was BEGone
(Vu GLain)
edge weight ((1/8)
edge-weight O(1)
We also allow our graph to posses node-weights (Rg))ect that are not necessarily equal to one. The Laplace operator Ag acting on the graph signal space g² induces a positive semi-definite and convex
Collapsed (left) and original (right) Graphs
Figure 3:
energy form on this signal space via (n) == (u, 4g4) = Ey Wg - -u(h)] Using this energy form, we now define set comprised of |G] signals, all of which live in ( These signals are used to facilitate contact between the respective graph signal spaces (G) and (G)).
Definition 5.5. For each E G, define the signal dig e (²)) as the unique solution to the convex optimization program
min Ez(u) subject u(h) ōkg for all h E Grain Ul+).
Given the boundary conditions, what is left to determine in the above optimization program are the 'Greek entries" (a) of each v/g. As Appendix I further elucidates, these be calculated explicitly and purely in terms of the inverse of Ag restricted to Greek indices as well as (sub-)columns of the adjacency matrix W. wedg-weights on G are then defined as n.) := Σncc ()((h) Tia- We denote the corresponding signal space by (G). Importantly, one has f - P. for any Latin index and n T1. EneEom Na as 5 O: which recovers our physical intuition about heat reservoirs. To
7

---

Under review as a conference paper at ICLR 2023
translate signals from (G) to (G) and back, define two identification operators J (G) (G)) and J (() (G) via f == Eyec f(g) vig and (Ju)(g) == (u, v / ng for all fee (G),, ue E (G) and g E G. Our main theorem then states the following: Theorem 5.6. With definitions and notation as above, there are constants K1, K2 3 0 such that the operators J and J are (KIvō) -iii----uu--uuitaa with respect to Ag. AG and w = (-1). Furthermore, the operators 4g and Ag are (-1)-(K2vō) close. with identification operator J.
Appendix preedintsseee the (fairly involved) proof of this result. Importantly, the size of the constants K1, K2 is independent of the cardinality (or more precisely the total weight) of Gramee implying that Theorem a.6 also remains applicable in the realm of large graphs. Finally note, that this stability result contingent on the use of the (un-normalized) graph Laplacian (c.f. Appendix [K:
Theorem 5.7. In the setting of Theorem 5.6 denote by T (T) adjaceney matrices or normalized graph Laplacians (G) (G)). There are functions 1/..12 : [o. 1] Rgo with ()(5) - 0 as 8 0 (i 2), families of identification operators J and w C so that J and J are Th (6) -uassi-uunny with respect to T, T and w while the operators T and T remain (-nz(6) close.
The Realm of Large Graphs: In order to relate our transfcrability framework to the literature, we consider an 'increasing' sequence of graphs (G,, E GR+1) approximating a limit object, so that the transferability framework Levie et al. (2019a) is also applicable. We choose the limit object to be the circle of circumference 2n and our approximating graphs be the closed path-graph on N vertices Figure 4: Closed Path-Graphs equidistantly embedded into the circle (c.f. Fig 4. With / = 2T/N the node-distance, we set weights to 1//h; ensuring consistency with the 'continuous' Laplacian the limit N 00. More details are presented in Appendix D which also contains the proof of the corresponding transferability result: Theorem 5.8. In the above setting choose all node- weights equal to one and N to be odd for definiteness. There exists constants K1, K₂ = 0(1) so that for each N > 1, there exist identification operators J, mapping between (GGN) and (G) so that J and J are with respect to AGN A and w = (-1). Furthermore, the operators AGS and Dax are (-1)-(Ka//)) N) close with identification operator J.
N
Jo(T)) for fixed g. This reduces to an ( N -decay for Levie et al. 2019a (ibid. Theorem 5, pt. 3) assuming a similar decay of operator- distances. Our framework might this capture transferability properties other approaches could miss.
Lemma 5.3 then implies ) of -
N
6 GRAPH LEVEL STABILITY
To solve tasks such as graph classification or regression over multiple graphs, graphs of varying sizes need be represented in common feature space. Here we show that aggregating node-level features into such graph level features via p-norms ((fler()) == (Egee (fal (igp))))))) preserves stability. To
(Gout) | 1ere
this end, let Lont be a target space of GCN in the sense of (3). On each of the (in total K 62 (Gmu) summands of Lout, we may apply the map Sa - [[eellesGG Stacking these maps, we
(GG
-Iletc.all
(Gou))
(G
-Ileram R build a map from Lout to IR Kav, Concatenating the map PNy associated to an N-layer GCN with this map yields map from Li to R Kar, We denote it by V and find:
(Goor))
Figure 5: Graph Level Aggregation
Theorem 6.1. For p > 2 we have in the setting of Theorem
V (b))lRKK.. & 4.3 or 5.4 and under the additional
3.1 that I (
(II L, R,, B.) Ilf hllss. In the setting of Theorem assumption that the 'final' identification operator JN satisfies [| fo (Gx)) -ffllleaax & 8- -- (Iilleea for all ʃa (GG)), we have (() (of) RKW & (N DRL K (BRL)) - (BRI) |l 6.
Derived stability results thus persist (under mild assumptions) if graph level features are aggregated via p-nomms. Appendix Mccnttins the corresponding proof.
8

---

Under review as a conference paper at ICLR 2023
7 NUMERICAL RESULTS
We focus on investigating structural perturbations, as correspond- ing results are most involved and novel:
| As.lop
We first consider graph on 5 nodes with an adjacency matrix A
3
with (1nttrrssss (c.f. in Appendix N)). We then scale A by 1/6, and 1/8, (with x_
Ressivane oeffeencee
= 1) respectively and consider the w
Operstar Oefirence
norm-difference between associated Laplacians and resolvents. Fig. 6 (a) then illustrate the theoretical result (c.f. Section that sent
( RR-
resolvent- instead of Laplacian- differences capture the conver-
gence behaviour. Embedding the considered graph into a larger
(a)
1/4,
graph (W R c.f. (31 in Appendix N). we consider the w0
[ JJ JRR lop
collapsing edge setting of Section 5.2 in Fig. 6 (b). As expected,
the corresponding resolvents do approach each other as 8 0.
Contrary to the theoretical bound in Lemma 5.3 differences of
decrease as their power k increases.
Beyond small graphs inaccessible to traditional asymptotic methods- - our method is also applicable to the large-graph setting: Fig. picks up the example of 'increasing' graph sequence
201
"approximating" the circle again. As predicted in Section 5.2 the
difference in resolvents decays (>c (z))). Fig. 10 in Appendix N
(b)
1,25
shows how the difference in Laplacians diverges instead. Hence Figure 6: Edge-Collapse Stability
our framework might capture stability properties traditional ap-
proaches could miss.
Finally, we investigate the transferability of a two-layer GCN with 16 nodes per hidden Layer combined with the aggregation method of Section 6 into graph-level map V. Filters are of the form (2) up to order k = 11. Coefficients {bg) are sampled uniformly from [-100, 100] Feature vectors generated on the QM7 dataset. There each graph represents a molecule; nodes correspond to individual atoms. Adjacency matrices are given by
301.
Nodioe Delverees
[R.aldon... - JRalbo Mew
30'
Wij 7 x. - xzy with Z; (a:;) the atomic charge (equilib- rium position) of atom i. We choose node-weights as jú, Z, and the Laplacian as characteristic operator. Leading up to Fig.
Figure 7: The Large-N N Regime
we consider the graph of methane (5 Nodes; one Carbon (Z1 6) and four Hydrogen nodes (Zz>1 = 1)) and deflect one of the Hy- drogen atoms (i = 2) out of equilibrium and along straight line towards the Carbon atom. We then consider the transferability of: the entire GCN between the resulting graph and an effective graph combining Carbon and deflected Hydrogen into a single node "+" "ith weight μ., Z1 + Zz 7 located at the equilibrium position of Carbon. With translating from effective to original description, consider (f) ( [) (averaged over 100 random unit-norm choices of f) as a function of ||l - x22 - At equilibrium the transferability error is (11. It decreases fast with decreasing Carbon-Hydrogen distance, with the choice of representation (effective vs. original) quickly becoming insignificant for generated feature vectors.
Iny m11 /quillberumm distance)
Figure 8: GCN Transferability
8 DISCUSSION
theoretically well founded framework capturing stability properties of GCNs was developed. We related node-level stability to (spectral) covering properties and edge-level stability to introduced semi-norms of employed filters. For non-normal characteristic operators, tools from complex analysis provided grounds for derived stability properties. We introduced a new notion of stability to structural perturbations, highlighted the importance of the resolvent and detailed how the developed line of thought captures relevant settings of structural changes such as the collapse of strongly connected sub-grapl to a node. There- - precisely if the graph Laplacian was employed - the transfcrability error could be bounded in terms of the inverse characteristic coupling strength the sub-graph.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference Learning Representations, 2021. URL https::/opetteeeeeeeeeee revirneeiii net/ forum? id=1 80CPhOCVH2
Joseph Bak and Donald Newman. Complex analysis. Springer, 2017.
Oscar Bandtlow. Estimates for norms of resolvents and an application to the perturbation of spectra. Mathematische Nachrichten, 267, 2004a.
Oscar F. Bandtlow. Estimates for norms of resolvents and an application to the perturbation of spectra. Mathematische Nachrichten, 267(1):3-11, 2004b. doi: http:://bbi.orr//100000000000//0 200310149, URL htt.ttts//oniinnllirrrre. wwtpw:/wwwwwww////////////////// 1maam// 200310149
L. C. Blum and J.-L. Reymond. 970 million druglike small molecules for virtual screening in the chemical universe database GDB-13. J. Am. Chem. Soc., 131:8732, 2009.
Kevin D. Cole. Heat conduction using Green's 's functions. Taylor and Francis, 2011.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filterin.. Advances in neural information processing systems, 29, 2016.
Fernando Gama, Joan Bruna, and Alejandro Ribeiro. Stability properties of graph neural networks. IEEE Trans. Signal Process., 68:5680-5695, 2020. doi: 10.11099TSP2200033026999 URL 2020. 302...
lutpps://dt //ts: www..org///io http://.....o/1.111111000
Zhan Gao, Elvin Isufi, and Alejandro Ribeiro. Stability of graph convolutional neural networks to stochastic perturbations. Signal Process., 188:108216, 2021. doi: 10. 10.101 1010://siigro222211003333
URL
1016 http:///..........11...1 201.1.11..22211111111.. 108216
Herbert A. Gindler. An operational calculus for meromorphic functions. Nagoya Mathematical Journal, 26:31-38, 1966. doi: 10.1017/50027763000016666
David Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 10(2):129-1500 2011.
Henry Kenlay, Dorina Thanou, and Xiaowen Dong. On the stability of graph convolutional neural networks under edge rewiring. In IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2021, Toronto, ON, Canada, June 6-11, 2021, pp. 8513-8517. IEEE, 2021. doi: 10. 10//SSSS//S33392 2021.9413474. URL
PEASSP39728 2021. 9413474
Nicolas Keriven, Alberto Bietti, and Samuel Vaiter. Convergence and stability of graph convolutional networks on large random graphs. In Hugo Larochelle. Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6- 2020, virtual, 2020. URL BtRL:ttts////prccdddiiio
htm.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representattinss ICLR 2017, Toulon, France, April 24- 26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL URL httttttpss//ppeeeeeeee net / forum?id=sJu440.
Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 3734-3743, PMLR, 09-15 Jun 2019. wtt.lttst//ooeeeiiiiit www.:..www...............ee.re.e prwss v27 2tw.///ee99..0
.ml..
Ron Levie, Michael M. Bronstein, and Gitta Kutyniok. Transferability of spectral graph convolutional neural networks. CoRR, abs/1907.12272. 2019a. URL Ball:tttp//axxxii http:/xwwwwwg//bb/b//aeaaa 12972
10

---

Under review as a conference paper at ICLR 2023
Ron Levie, Elvin Isufi, and Gitta Kutyniok. On the transferability of spectral graph filters. CoRR, abs/1901.10524, 2019b. URL/attp://axxvvccm http:///aab1911111111111
Ron Levie, Federico Monti, Xavier Bresson, and Michael M. Bronstein. Cayleynets: Graph convolu- tional neural networks with complex rational spectral filters. JEEE Trans. Signal Process., 67(1): 97-109, 2019c. doi: 10. N0.1109/TSP.01882255 28779644. URL URI.https://doo http://ooooorr/////// 11..00111999990
201 8 2879624)
Stéphane Mallat. Group invariant scattering. Communications on Pure and Applied Math- ematics, 65(10):133--1398, 2012. doi: http://0bi.rr/11111000////....
URL https
//ot.iiellbbary wwweelibbrrwwweeyye........ wiley. com/ doi/
Sohir Maskey, Ron Levie, and Gitta Kutyniok. Transferability of graph neural networks: an extended graphon approach. CoRR, Abs/22109100999 2021. 10096
Barry Simon Michael Reed. Methods of modern mathematical physics, Volume 1. Academic Press, 1981.
MichaelGil. Norm estimates for resolvents of non-selfadjoint operators having schmitt inverse ones. 2012.
Olaf. Post. Spectral Analysis Graph-like Spaces / by Olaf Post. Lecture Notes in Mathematics, 2039. Springer Berlin Heidelberg. Berlin, Heidelherg, 1st 2012. edition, 2012. ISBN 3-642-23840-8.
Olaf Post and Jan Simmer. Approximation of fractals by discrete graphs: norm resolvent and spectral convergence, 2017. URL htttttttt////tittt org. http://bs/1110...00//
Luana Ruiz, Luiz O. Chamon, and Alejandro Ribeiro. Graphon neural networks and the trans- ferability of graph neural networks. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurlPS 2020, www.::ss..enusieoommmmooo hetp://eeeedd....eeeeeeeeaa../ad
December 12, 2020, virtual, 2020. 2020/ hatpaashhh2bccd5eee http://ccc...aaaaaoocccccccaaaaa AbsutdAbbtrrre html
M. Rupp, A. Tkatchenko, K.-R. Müller, and O. A. von Lilienfeld. Fast and accurate modeling of molecular atomization energies with machine learning. Physical Review Letters, 108:058301, 2012.
Oleg Szehr. Eigenvalue estimates for the resolvent of a non-normal matrix. Journal of Spectral Theory, 4(4):783-813, 2014. doi: 10.4171/jst/86. URL https://doi. org/10, 41718 2F fst
Jake Topping, Francesco Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding over-squashing and bottlenecks graphs via curvature, 2021. URL
https: wwg. 2bs/2/11./21....
Thomas Wiatowski and Helmut Böleskei. mathematical theory of deep convolutional neural networks for feature extraction. IEEE Transactions on Information Theory, 64: 64:1845-1866, 201 8.
T.P. Wihler. On the hölder continuity matrix functions for normal matrices. Journal of inequalities in pure and applied mathematics, 10(4), Dec 2009. ISSN 1443-5756. URL https: /ww em s. (leeJJourals//JPAAA www.://maaaas/// JTPAA///0A_AA//////__
JTPAM/APMMTT2T www. ppff
A SOME CONCEPTS IN LINEAR ALGEBRA
In the interest of self-con self-containedness, provide brief review of some concepts from linear algebra utilized in this work that might potentially be considered more advanced. Presented results are all standard; very thorough reference is Michael Reed (981).

---

Under review as a conference paper at ICLR 2023
Hilbert Spaces: To Hilbert space- often denoted by H. - is vector space the complex numbers which also has an inner product - often denoted by (..-) n. Prototypical examples are given by the Euclidean spaces Cd with inner product (2, y> == > Tili. Associated to an inner product is norm, denoted by || || and defined by | (Ir, x)H for H.
Direct Sums of Spaces: Given two potentially different Hilbert spaces H. and H. one can form their direct sum H @ H. Elements of H @ H are vectors of the form (a. b), with a H and e H. Addition and scalar multiplication are defined the obvious way by
(a, b) + Mce d) (a + Ac, + Ad)
for a, C H. d H and X E C. The inner product the direct sum is defined by
<(a, b). (c, d)) u == (a, cyи
+ (b, d)
As is readily checked, this implies that the norm HaN on the direct sum is given by
(a,, b) M
lal
[b|]
Standard examples of direct sums again the Euclidean spaces, where has Cd C @ CD if m + n = d, as is casily checked. One might also consider direct sums with more than two summands, writing Cd @ C for example. In fact, might also consider infinite sums of Hilbert spaces: The space D Hi is made up of those elements a = (A1, 02 .z.... with ag E Hi for which the norm
|a|| H,
Σ
is finite. This means for example that the vector (1, 0, 0, in while 11,1,1,1, is not.
Direct Sums of Maps: Suppose we have two collections of Hilbert spaces [?4) (A,)_ with Te N or r = c0. Suppose further that for each & I (resp. i < I') we have (not necessarily linear) map J H4 H4. Then the collection (J.) of these 'component" maps induce 'composite' map
24 - 0i_1H,
between the direct sums. Its value element (a1, a2 03 a3,...) ...). oL_1 H4 is defined by
f(a)
Strictly speaking, one has to be a bit more careful in the case where I = oo to ensure that Il (a) 02 A.
00. This can however be ensured 1 & i and some C' independent of all i, since then 1 {a)l A, & C'laall;,, H. & cp. If each J, is linear operator, such C exists precisely if the operator norms (defined below) of all J, are smaller than some constant.
have [ & Claa,llu for all
Operator Norm: Let Jet H be linear operator between Hilbert spaces. We measure its 'size' by what is called the operator norm, denoted by || llop and defined by
A R
sup 1
|
Adjoint Operators Let J 7. - H. be linear operator from the Hilbert space H. to the Hilbert
space H. Its adjoint _ H. H. is operator mapping in the opposite direction. It is uniquely determined by demanding that
(Jf = u'
holds true for arbitrary f H and H.
12

---

Under review as a conference paper at ICLR 2023
Normal Operators: If linear operator A H - 7. maps from and to the same Hilbert space, we can compare it directly with its adjoint. If AA* A* A, we say that the operator is normal. Special instances of normal operators self-adjoint operators, for which have the stronger property A*. an operator is normal, there are unitary maps U H - H diagonalizing A as
U*AU diag())...Ao.)
with eigenvalues C. We call the collection of eigenvalues the speetrum o of A. dim H = we may write a(A) (Aj= It is standard exercise to verify that each eigenvalue satisfies [&d & Allop. Associated to each eigenvalue an eigenvector ø,. The collection of all (normalized) eigenvectors forms orthonormal basis of H. We may then write
A =
Σ X (dis S'H
Resolvent of an Operator: Given operator T on some Hilbert space H. have by definition that the operator (T - 2) H.- - is invertible precisely if # ((')). In this case we write
RT) ()
and call this operator the resolvent of 7 at 2.
If T is normal it can be proved that the norm of the resolvent satisfies
Rg (Tpp dist(2,o(A)))
where dist(2, a()) denotes the minimal distance between and any eigenvalue of A. For non- normal operators, one can prove
[R < Tr(2)
with
(2) = cxp [2177
as is proved in Bandtlow (2004a).
Frobenius Norm: Given two finite dimensional Hilbert spaces Hi and Hgg with orthonormal bases of an operator A Hi - H2 may be defined as ( and (o] (1 fim1 the Frobenius norm
d Aiyl 1
| =
with Ai the matrix representation of A with respect to the bases { and (o standard exercise to verify that this norm is indeed independent of any choice of basis and hence invariant under multiplying with a unitary on either the left the right side. More precisely, U : H2 + H2 and V H1 - Hi are unitary, we have
|UAVI A
Frobenius norms can be used to transfer Lipschitz continuity properties complex functions to the setting of functions applied normal operators:
Lemma A.1. Let - C be Lipschitz continuous with Lipschitz constant Dg. This implies
[lg( J & D, XX YlF.-
for normal operators X on H2. on Hi and any linear map J H4 - H2.
Proof. This proof is modified version of the proof in Wihler (009)). Let U, W be unitary (with respect to the inner product (+r)x) operators diagonalizing the normal operators X and Y as
V* XV diag ...,)) ((X)
WV
diag(/ (4, D(Y).
13

---

Under review as a conference paper at ICLR 2023
Since the Frobenius norm is invariant under unitary transformations find
1l9(X)J-Jg(Y)) - I =
[lo(D(X))V* JW -V
- [I((D(X)) JW -V
Σ
Σ [o(D(X))] JW]ss [V* JWaaa[((((()))
1
Σ WIv" 2 (l(()))))))))))))>{))) -((4))
[[V*W]op D21a, - -Mal?
D2 X Y
B APPROXIMATING BOUNDED CONTINUOUS FILTERS
Let us recall Definition 2.1
Definition B.1. Fix w é C and C' > 0. Define the space F of continuous filters on C Cff w) ="
to be the space multilinear power-series' g(=) = Lipu- Ouv (w =)) th (w-- z) -M for which the norm [ sonn
- 1 + v|Cu+* [ is finite.
We now prove that upon denoting by (w(w) C the open ball of radius around w, one can show that for arbitrary 8 > 0 and every continuous function defined on ()(B(()) U (.)) which is regular at infinity i.e. satisfies lim,- ((2)) c C independent of which
is chosen
there is function f E F so that [f(z) - g(2)l < 5 for all E CB(B, B, (w)).
Making use of the Stone- Weierstrass theorem for complex functions, suffices to prove that for every point in C)(BB(()) J (wF) there are functions f andd g in Roont for which
f(z) # g(2).
But this is obvious since (w 2)-1 is injective C\(B(Ww) U Bc(w)).
C COMPLEX ANALYSIS
A general reference for topics discussed in this section is Bak & Newman (2017) For complex valued function f of a single complex variable, the derivative of f at point 2p E C in its domain of definition is defined as the limit
f(=) ((=o)
('(z))
lim 2
2- 2g
For this limit to exist, it needs to be independent the 'direction' in which approaches zo, which is stronger requirement than being real-differentiable. A function called holomorphic on open set U if it is complex differentiable at every point in U. It is called entire if it is complex differrentiable at every point in C. Every entire function has an everywhere convergent power series representation
(6)
a function g is analytic (i.e. can be expanded into a power series), we have
g(z)
g(A) = 2ri
dz
(7)
X
14

---

Under review as a conference paper at ICLR 2023
for any circle S C encircling by Cauchy's integral formula.
In fact, the integration contour need not be a circle S, but may be the boundary of any so called Cauchy domain containing A:
Definition C.1. A subset D of the complex plane C is called Cauchy domain if D is open, has finite number of components (the closure of two of which are disjoint) and the boundary of eD D composed of finite number of closed rectifiable Jordan curves, no two of which intersect.
Equation forms the backbone of complex analysis. Since the integral
2 f
g(I) -)-
is well defined for holomorphic g(-) and any operator T for which (T) and 2D are disjoint (c.f. e.g. Post (2012) for details), we can essentially take (8) as a defining equation through which one might apply holomorphic functions operators.
While functions that everywhere complex differentiable have series representation according to (6), complex functions that are holomorphic only on Ci(w} have a series representation (called Laurent series) according
20 Σ
g(2)
aR(z w)*
If these functions assumed to be regular infinity, terms with positive exponent permitted and (changing the indexing) we may thus write
g(z) = Σ ax(z - w)
Motivated by this, prove the following consistency result:
Lemma C.2. With the notation of Section
2 we have for any l: > and (T) that
(w Id T)
(w z)- (2Id 72z,
2wi
where we interpret the left hand side of the equation in terms of inversion and matrix powers.
Proof. We first note that may write
8
(T - -a-
for Y\ w| < (T)] using standard results in matrix analysis (namely the 'Neumann Characteri- sation of the Resolvent' which is obtained by repeated application of resolvent identity; c.f. Post (2012) for more details). We thus find
dz
1
Σ (w 2)" R.. (T) n=
2mi
2τi 21d -T
W
aD
Using the fact that
1
f (= w)
-- -1d 8
2
then yields the claim.
15

---

Under review as a conference paper at ICLR 2023
D PROOF OF LEMMA 2.3
We want to prove the following:
Lemma D.1. For holomorphic 9 and generic T we have ll
& |g(x)) +
2x San (x)d)/) Furthermore we have for any T with yr (w) & C, that (g( lop < I1all long as g Fe..
1.
Proof. We first note
o(00) Id+ 2τi f fo())-(211)
1
f g(2) (=Id - -T-
(=Id -T)-dz d2
< 1g((0) Idlop +
2
8D
op
< |g((0)| +
1
f
[=(=) -
- T> d|z|.
2x 0D
The first claim thus follows together with (T) op $ (z). The second claim be derived as follows:
x
Σ
1C - w)
(T - w) op
1 (w)
Σ blick
op
E PROOF OF THEOREM 3.1 AND TIGHTNESS OF RESULTS
We want to prove the following:
Theorem E.1. With the notation of Section N-layer GCN. We have
let dN Lm - Lou be the map associated to an
[2N(f) (1))l))
[ Ln LnRnBBn
11ff-hla h/
with B, (T,) EjEKn., Eiek, ( (2) if T, is normal. For general T, we have for all
{gn) entire. holomorphic and in Fu,o respectively:
E Ej. EiS, (aar)) k=12 [Tr
By :=
jeKn-i Exer, 1 (00) 2n fo (r(2) Eyek... Eie,, (2)
Vjek,. Liek, 10 123.c
Proof. Given input signals f, e Lmn let us sticking to the notation introduced in Section 2 denote the intermediate signal representations in the intermediate layers L, by f" h" e Lr With the update rule described in Section 2 and the norm induced each L, as described in Appendix A we then have
1
1n+1
Kn+1
K
K (Tn+))
Σ
Σ Dij ((nt)))())((3)) Pu+1
Di Σ
Put1
(Gn+))
Knt1
Kn
Kr
Σ Fip
n+1 (T+((T+))
- Σ
Fog
(T++) (a
n+1
1=1
j=1
1=1
(3().11)
Kn+i
= 2
Σ
Σ
Fi
n (Tn41) -
Pn+z(k?)]
((Gn-1)
16

---

Under review as a conference paper at ICLR 2023
We next note
K
Kn
2
Σ 9ij
(Tn+1) (Paz((f))
- Pu+ p
(3(Gn+1)
Ka+1
Kg
2
|10 1
(Tx+1)llp [Pu+i(f]) Pu+1 (k9)) (ea
K n+ Kr
|| 10 (T n++ 11 op
III [P++1(ff) pa+1 [k5]] [ea]]]laeeaa ((.))...
Kn+1 Kn
R
9is 1
(T
III - -1
+1
where the second last step is an application of the Cauchy Schwarz inequality. Proceeding inductively and using our previously established estimates, this proves the claim for all settings in which T, nor normal (using an additional application of the triangle inequality for the case of holomorphic filters).
To prove the claim for normal Tn as well, we note that this setting we have (writing (0a: da ) |a| for a normalozed eigenvalue-eigenveetn sequence of T 1) that we have
K
n+1 Ki
(Tu+1) (P)+i (ht)
((Gu+1)
Ka+i
K
n- ( ( [Pa+i - Patt Pnti (h3)))
Vij
((GG+1)
Knt1 Kn
9ij
n+1 12 [Pn+i Pu+i (
j-1
Kn
Σ
Σ 1ot (2a)
Σ
Koai (Pu+i(())))))) (1)(())))
Bn+ IllI
h
Here we applied Cauchy Schwarz once more in the second to last step and bounded
Elas(Aa)
sup Σ (T) i.j
Loss (A))
To see that these bounds are not necessarily tight, we may simply note that if we have a simple one-layer Network depicted in Fig. 9 below, the stability can be tightened to
T N (f) (h)lle,... & LRB Ilf hlls..
with with B, == max(sup (ea()) (A)) as opposed to with B, = v Suuxxe((T) Eima, 19) if 3-a.b
normal; as an easy calculation shows.
F PROOF OF LEMMA 4.2
We want prove the following:
17

---

Under review as a conference paper at ICLR 2023
(G P E
e (Gous) P (²(Gon))
(o(r)
P (ut
[h(T)
(G))
e (Gout) 8 P out)
Figure 9: Sparsely connected Layer
Lemma F.1. Let T.T be operators on on (G) (c) with | |oop C. Let J (G) - (G) be arbitrary but linear. With K2 = Σ - |g]h for entire and Kg = for holomorphic, we have
2m SaD
(o(T)) - Jg(T)llop & Kg ||T - Top
Proof. Let first verify the claim for entire g. We first that
T J = -i- JT) + ( JT
(TJ- - T -T)- (T -
Thus, with pTlpp Mop & C we find
| JT op & kO* kC*--1 J''ll
The claim now follows from applying the triangle inequality. Now let us prove the bound for holomorphic g. We first note the following:
1
T- [ JT)
1
T T
1
TJ
JT
--2
T
T 2
T T-2
( J +
z
1
(T
2)J
+
2
T
T
T
T
T
T-2
=2
T- J
T -
Thus we have
1 f 1
f
1
lo(())JJg((T]1)
Ry (T) (R (B)
rr
(2))())))
2T 2z|
2
G PROOF OF THEOREM 4K
We prove the following generalization of Theorem 4.3
Theorem G.I. Let v, y be the maps associated to --layer graph convolutional networks with the same nin-lineasssses and functional calculus filters, but based different graph signal spaces (G)), (()) characteristic operators T,, T, and connecting operators P,, P Assume B,, B, B as well as Rn, Rr < R and Ln & for some B, R, L identification operators Jn ((GG)) - ((,)) (0 < n & N) almost commuting with non- linearities and connecting operators in the sense of PP,JJ--ff - J.P JnPffflrr & &ell fallfleerr.) and (pp((Jaf)- (f) ((ā.)) & 61llflle Depending on whether normal or arbitrary characteristic operators are used, define D? := Σjsk.-1 ΣvEK, D2 or D2 = Eyek.., Σiek, K2_ Choose
> and all n > 0. Assume that there are
D such that D, D for all Finally assume that J.,T, FnJull and with F if both
18

---

Under review as a conference paper at ICLR 2023
operators normal and op otherwise. Then we have for all f Li and with IN the operator that the KN copies of JN induced through concatenation that
(T(Jof) IN < N. [RLD6 + 61 BR + 8,BL] (BRL) -
Proof. For simplicity in notation, let us denote the hidden representation of Jof in Ln by fr. We then note the following
In+15
ju+1ll. 1
Ka+1
Kn
K Σ (Tn+t)
Int1Pa+1
Σ Jif
xt
(Inttn))) PPn+1
9is
n+1
Kull
Kn
)
2 (G++)))
An+1Pnt
Σ Hij
n+1 (I++)
Pn-1
Jnt1
Σ
(Tn+1) (Tn+) (I++
9ij
n+1
1=1
5=1
Kn+1
Kn
K₂ Σ (T+t1)
+L
Jn+1
(In+1)
Jij
(G
We can bound the first term by 8, R (BRL)* If s. For the second term we find
K
Kn
K
Jn+1
Σ
n+1 (T (T++1)
-
Σ
gig
n+
(Ta+1)
(Ta+1)
g-1
GG
Kp-1
K
Σ
(Jn+19 n+ (Ta+1) - Dij ( (a
(GGn))))
(n+1Pn=1(f7) - P ( BeTc...)
+LB
Arguing as in the proof of 3.1 we can bound the first term by LD 8R (BRL) For the second term find,
Jat1 PatiP (
LB
(BRL)) + f, M1
arguing as above. Iterating from to n 0 then yields the claim.
H TRANSPERABILITY. GENERAL CONSIDERATIONS
We first prove the statement made at the beginning of Section 5 that
(wId - A6,) (wId A s.
- llop = 0(, 6,).
To this end denote the increasing sequence of eigenvalues (counted without multiplicity) of A by M Recall that Å 0 Denote the sequence of projections the corresponding eigenspaces by (PA.M. We have for the resolvent that
P.. A
wld As
wld 8
W
19

---

Under review as a conference paper at ICLR 2023
Thus have for daz 66 small enough that
1
1
A1
4g
wld - Aoa wld
Ao op
A1
A1
(w
X1)
2 x1)
6a
9n
8n
1
1( =
O(6g 86).
1
{1)
1 A1)
8n
6.
Next note the convergence (wTd - As) we have
11 - Po (w -0) -0)-1
But this is obvious, since for A
1
A 0
as - O.
I PROOFS OF LEMMA 5.3 AND THEOREM 5.4
Lemma I.1. Let T and Î be characteristic operators on (²) and (()) be respectively. If these operators are w-8-close with identification operator J, and | RRllop Rullop & C we have
[J((T) J1o & K2 [| JR,)l
if is holomorphic and Kg = llg) shot if Fhhot If and T are normal as well as doubly w-8-close and g Frontt have
with K2 = - + 1z (1) |z
Kg = l1g geont.
Proof. We first deal with the statement conceringg holomorphic g. To this end we note that Lemma 4.5.9 of Post 2012) proves
| JR2 lop & (1 + (1 +1= w/y RR JRullop
The claim then follows from
1
[Jo(T) - - &
|a(())] R_J- JJ 2/
2n
RD
For E Ghot the claim is proved exactly as in the proof of Lemma 2.3
For ge E Foont we that
(RL)" (R (R*)" (Rw)" [ +
Together with the result
| - JT op < k0* || - JT
established in the proof of Lemma 4.2 the claim then follows from the triangle inequality together with the definition of the semi-nome 9 cont.
As in the previous section, we state a slightly more general version of our main theorem of this section:
Theorem I.2. Let Φb, T be the maps associated to N l-layer graph convolutional networks with the same non-lincarities and functional calculus filters, but based on different graph signal spaces (Gn), ((GG) characteristic operators T., T, and connecting operators P., P... Assume B,, B,, & B as well as R,, Ri & R and In, & T. for some B, R, T. > 0 and all > 0. Assume that there identification operators Jn (G,
((,,) (0 n N) almost commuting with non- S.Paflers & &2lffleG..) and (JnJ) JnPr(DDleeaa 0:l define D = Σjek.-, Eiek, K3 with Kgg as in
linearities and connecting operators in the sense of [|nnn--ff
20

---

Under review as a conference paper at ICLR 2023
Lemma 5.3
Choose D such that Dn & D for all Finally assume that [ - Tn) (wId-
T,)-~Jalle Jallop & If filters in Fronnt are used, assume additionally that | Tx,) )
((wId- - + Jnl op 8. Then have for all f Ln and with IN the operator that the KN copies of JN induced through concatenation that
( IN N. [RLD6 + 6, 82 (BRL) se
Proof. The proof proceeds in complete analogy to the one of Theorem 4.3
J COLLAPSING STRONG EDGES: PROOFS AND FURTHER DETAILS
We utilize the notation introduced in Section 5.2 form induced by the energy functional Eg by
Beyond this, we denote the positive semi-definite
Eg(u, v) (u, AGo)
We further use the notation (g(u) = FG((u, u). With
Fg
Σ
Waslu(a)- - u(())
oeGand
AEGumni
Σ
Waslu(a)-uul u(b)l²
aEGlom
beGram
Σ
Waolu(a) - u(3)12
aEGras BeGGnd
Σ
Watlu(a) u(b))2
aeGome Ge
Σ
Wailu(a) e(+))2
aEGovd
Σ
W.olu(+) u(3))²
ReConst
Σ
Wan (u(a)= - u(+)12
Woolu(*) u(b)1
Similar considerations apply when Ō is replaced by G. Let us next solve the convex optimization program introduced in Definition 5.5 restated here for convenience:
Definition J.1. For each g e G, define the signal vy E ((()) as the unique solution to the convex optimization program
min (u( subject to u(h) ōbg for all Gratin U(+}.
As first step note that all entries of th real and non-negative, which follows since each summand (9h is non-increasing under the map u - |u] due to the reverse triangle |||] & |a- ja-bl. b).
To find the explicit form of uh fix E Gratin U{*} and denote by Xa E e(((G) the signal defined by setting it to (h) ōng for h Gravin U(+) and (g(a)) nf with (ng aeaoreet set of (Gereek]
21

---

Under review as a conference paper at ICLR 2023
free parameters in Rgg. We then have
Eg((a) =2
Σ
Wos Vog~ +
Σ
Wao W 2
+2
Σ
Waolng
aEčr
aEGrow
aEC
Be beG U(+)
Σ
Waelng ng ng1
By definition, X9 depends smoothly on the parameters {ng JoeCcrees Finding the minimizer of the convex optimization program (5) is then equivalent to finding the values SigJas@oreed at which we have
(xo) 0. Ōng
We note
16 4
Wo 9c
+
Σ
W 95
+
Σ
Wag
Σ
Wag
W of
ac Gem agd
Uf+}
oEG@ed
aEGand
Collecting these equations for all parameters into matrix equation, find that the 'Greek entries" of the vector v are given explicitly by
Vi w (g(B)
da
Was
W W g/3
gau
- Wea
dg
(10)
with degrees in & denoted by da. Let us denote the restriction of eig to Greek entries, thought of as vector in ClCarcek) by ngg
Given the degree d, corresponding to a Greek index, we decompose it as
d = d + Wa. + Va
with d accounting for edges from to other greek vertices
WaBt
BeGareek
BeGoreck
and V, accounting for edges from a to Latin vertices
V.
Σ
W
aa.
aeGrain
Recall that we also may write
Wo.
8 Jwa..
We may then write
da
Was
jr
W 0z
War
Va
1
Wea
dg
W
Ba
3
0
waf
:
+
Ll diag (J.) V.
where made the obvious definitions for the matrices L and V and denoted by W. the vector with entries Wo.. Let us also use the notation
h = L diag(w.).
22

---

Under review as a conference paper at ICLR 2023
Next want to establish that h is invertible. For this first note that that L is the graph Laplacian of the subgraph Grreeki which we assume be connected. Hence L is positive semi-defintte with the eigenspace corresponding to the eigenvalue zero being spanned by (entry-wise) constant vectors. Since all entries of w, are non-negative, the operator h also positive semi-definite. Since assume that the vertex * is connected at least one other vertex in GGreeks there is least one entry in 3r that is strictly greater than zero. We show that this already implies that h is in fact also positive definite and hence invertible. Indeed, for any Ø Claarecki
we have
(ū, h (l (ū, di)g((a)) GGreeall
Both terms the right hand side non-negative. If ū constant (non-zero) vector, the first term vanishes, but since at least one entry of w. is strictly positive, with all others being non-negative, the second term on the right hand side strictly positive. If 7' is non-constant, the first term on the right hand side is larger than zero. Hence h is positive definite and thus invertible. Similarly one proves that (for any 0) the operator h + oV is positive definite and hence invertible. Thus we now know that the operator
da
W as
(h 0v)= - Wea
dg
utilized in (10) is indeed invertible. We note (again with the restriction of vig to Greek entries thought of vector in ClGarentl denoted by iiy) that may equivalently write 10 as
(h 5V) 5V) n
5W,
(11)
and
W W nb
ga
W =
thought of as an element of Cloanaal, may write (11) equivalently
To proceed, we now first focus on the case = *, for which
(h 8V) W.. Since W. is independent of 6, we may take the limit 5 - 0 and arrive at
(12)
(L + diag(w..) m W.
which is uniquely solved by t7 (1, 1, l..). = I Grek- Since assume å < 1, we can now investigate the solution 7y for non-zero 5 through perturbation theory. We write
nh
with 20 = and find from 12
using h Grnck T7
the defining equation
5(h + oV) V. Cams"
From this we obtain the estimate
| (()m))))) < ((h 8V) IV &ammlle (()mm)))) 6,
where we denote by l ((Gore) the space graph signal space @ Gareell equipped with node weights (7 ge
We note that both and V/ are positive semi-definite and we thus obtain
Amin (h) Amin(h + 8V)
23

---

Under review as a conference paper at ICLR 2023
for the minimal eigenvalues of the respective operators. Hence
1(h + 5V) & | 11 op:
and thus also
1 ll (Cion))
$ & 1lpp IIV 1-a (((oo))) -
(13)
=:K
Since | 1lop 1/Amin (l) we may write
V 1 Greok Greaklle Amin ())
K
(14)
we know that for g of we have ol We now also want to bound 7g (GGmm))) in terms of 6. We will do this by establishing the relationship
From 11
0.
Σ
fl
(15)
ge
and then utilizing estimate on |1<2 1 (Gamme) established above. To prove (15), we will need the concept of harmonic extensions:
Definition J.2. Denote by E2 (Graiin {*}) the graph signal space C1 equipped with the
node weights geCummurr) Given arbitrary signal (G {+)) harmonic extension of to all of (()) is a signal (G) satisfying
(a) = 0 Va E Gamak and u(h) = u(h) 4 h Grain Ul+).
We first note that the concept of harmonic extensions both well-defined an well-behaved:
Lemma J.3. Fix TE e (Glamin U {+})) There exists unique harmonic extension E P(G) of is given the solution the convex optimization program
min (u(u) subject to u(h) ōāg for all h GLatin Ul+}.
Furthermore if and are the harmonic extensions and V. then (u + v) the (unique) harmonic extension of (ī + T).
Proof. We write a signal ip E ((G) as vi = (v,4) with sb E (G u (x)) and v7 E ((Greet)) We then notice
argmin (g( subject to (h)) = (hh) for all h Grain U(+}
2Eg(1) 0 Va E Gereed and (hh) = (h)) for all h Gratn U(+}
on
Σ W (1((a)) v(v)) = 0 Va E Gamek and vb(hh) (hh) for all h E Grani U(+
B
(Aa+))a)) = Va Goreet and (hh) = Thh) for all h Gromi U(+).
Here, treated to and its complex conjugate independent variables and used that Ea(-) is a real-valued functional for the first equivalence. As harmonic extensions are thus equivalently characterised the solutions of convex minimization programs, they are unique. To prove the last statement, we note that by linearity of the graph Laplacian, (u + v) certainly is harmonic extension of (u + v). Since harmonic extensions are unique, it is the only one.
After this preparatory effort,
ready prove 1.
24

---

Under review as a conference paper at ICLR 2023
Lemma J.4. For any ò > the signals g
get Uf+}
form partition of unity of l (Gúned))
fg Gome
(16)
geC Uf+}
Equivalently we have
Σ nT S.
ge Caaie
As an immediate Corollary we obtain
Corollary J.5. For any > 0 the signals (1/
form a partition of unity of (²)):
gecrum Uf+}
Σ
(17)
gEG U
Proof. Using the 'boundary conditions' in (5). it is straightforward to verify that (16) is equivalent to
17
From Lemma J.3 we know that Vig originally characterised the solution of the problem
min (n) subject to u(h) Öng for all E Gratin Ul+),
is equivalently characterised as the harmonic extension of u(h) -ōng- From the last statement of
Th) Lemma J.3 we know that Eg U(+} Tg is the unique harmonic extension of
Σ
ōng 0 Ul+1
GeGaa U(+)
But this in turn the unique solution of the problem
min Ey(u) subject to u(h) = 1 for all h Grani U(*}.
Since we have
Ez(1a)= =0
which is the lowest possible attainable value of Eg(:), and setting 1 is compatible with the 'boundary condition' w(h) = 1 for all h E GLani Uf+}, we know that is the (unique) harmonic extension of 1 E Ut+3 By the last statement of Lemma J.3 we thus have
Σ
T1g 18
g U(+}
Having established that we may write
Σ
11
Sx:
gEGuum
together with the fact that every entry of each nlg is non-negative, we now know that
(a), -.
Furthermore using our earlier estimate
13
we now casily obtain
Σ
K 8.
geG
12 (Gand))
Hence by positivity of the entries also have for each individual g Grain that
(( & K 8.
25

---

Under review as a conference paper at ICLR 2023
For the weights {pg we then find
Fi & 11 E Fi + 6K
Σ Na
CoEGomm
g + *. We also write ((GGreek) = Landand Pa. If *, we have
p. + -1-100 ())i(GGrre))) & p. p ((.Greek))
Having set the scene, we are now ready to prove Theorem 5.4 Following Post & Simmer (2017). instead of checking the conditions of Definition 5.1 and Defimition 5.2 it is instead sufficient to check the following, with J J as defined Section 5.2 to establish Theorem 5.6
Lemma J.6. In addition to identification operators J, J, assume that there exist additional operators J (G)) - (C) and J. (C)) - (G) that the following set of equations is satisfied with 0
|Jl[| & E'IlIl KJS.)) - (f) < &l1fl
(18)
J--J1 < + Fo(s), [īu & r' /1/1u12 F&((U)
(19)
J /'Vlf12 Eo(s), |Ju Jul é' V1ul1 + E3(u))
(20)
(F Fal(S. Ju)l & VISE + Fo(s) v /ul FT(
(21)
Then the (normal) operators A and Á are (doubly) (-1)- (e 12c') -close with identificationnoperatoo
J.
Here, we always have (G)) and f (()))
Proof. This follows immediately after combining Proposition 4.4.12 with Theorem 4.4.15 of Post (0122).
We set f= f and (f))(x) = u(x) and now determine the individual = c(6) values for which
these equations are satisfied:
Left-hand-side of (18)
For the left hand side of (18) we note (using 2ab & a² + 6² and the fact that the 1o form a partition of unity):
JJ
Σ (u a)
((
h.geG
Σ 1/ Σ
Σ
1f())
Σ
(wi vi (
hEG
gEG
9EG
hEG
Σ 15(1) 1) 1)
Σ
(1
KEG
gEG
Σ 1
gEG
= 1
Here the second to last inequality follows from the definition of the weights pgg. Thus the left hand side of (18) holds with
0.
26

---

Under review as a conference paper at ICLR 2023
Right-hand-side of (18)
The right hand side (18 holds trivially with
0
since we have chosen f J.
Lede-hand-side of (19
Now let us check the h..ss. of 19 We have:
(155 1663 ar
(f - J(f(()) = f(y) f())
f(g)
14
DEG
Using the constant K defined
(14) we have
Bg E ug S Fig + 8K
Σ
Na
CrEGa
if g * We also write ((Grreek) =
n aeGomt
Na. If = we have
n. + (1 -1- () $ u. & pr. + 12 (p((Grree))
We next note
(eg x1 1 //// = -uzdax + TTe (y)
with Wi the vector with entries Wz(g)= = Waag
Thus for y # find
1lf [J-Jof)(Ml & (1- By
// (())
[f(w))+ +
Σ f(g)
gEG gry
We thus find
(ulo 2/dz
If JJfle
Σ
1
By
[f()))+ +
Σ f(g)
or (2
mg
1g
DEG
gEG gfV
Ux.
f(*)
Σ f(g)
gEG
Σ (11
By
2 (s())
Σ
Σ f(g)
(wo 2555
gr
14g
yEG
DEG 83
BEG 1779
g+
(2i0 2018 S.
f(+) s(+)- - Σ f(g)
GEG
To bound the first term of the estimate, we note (for *) and small enough:
11 Bl 1
P
8K p Grreck)
K K (reeck)))))
E
By 8K (.KKa Greek))
8KP, (rGGrr)))
min geGuatin
P9
27

---

Under review as a conference paper at ICLR 2023
We also note (for y #
[f(v)) <
If(1)l
min geGzacin
//g
min vhy geGLatin
Thus find
Σ (1 yEG Mraf
Kii Greekk)
Kjd Kjj
[f()))
&d
Σ 1 =d yEG UF
Ifee
M
min gEGratee
Pa
min geGr.arin
Pa
To estimate the second term, we estimate
(f(g))
Iflecs
min gEGzatmn(s)
VPg
to obtain
v5 (Vg.
(vh 165
Σ f(g)
Σ DEG 19
(
Hay
min gEGiacnn
Vlg
mafl Mg Fyy (3( (Gumn))
|
Σ
min geGratin Vbg
gE 99ty
My
Tyy 13 (Goms))
Σ
min ge Latinni v(x)
Mg
By
977
Thus we find (using that Tg Ty/ e (Gona) is a non-negative number and we have
| 12 < (111
Σ
Σ f(g)
(G
1f
Tg: Try ely/erCa ((GGn))))
1
min gEGLarm
Vkg
Byy
VEG yo
9EG V+ 94
Σ Σ
Tg: Ngl (3(mmm))
min
geG ge
(EG
# gzy
|fl Σ
Tg. Nyg E2 (Gama))
min
JEG 9EG B+
|fle(( (1 Game St (
min GEGLatin
Pig
1
Ifle -1 Allammllett 11522 ((Gom)))
min geGratin
K Vi((GGoe)))
& 5.
min geGzatinu(t)
pig
Let us thus turn the remaining term; corresponding y We have
28

---

Under review as a conference paper at ICLR 2023
(155
vio 80
Cobo
93 166
f(+) Σ f(g)
[f(+)) +
Σ f(g)
ea
(22)
9EG
gEG g+*
We first deal with the left summand. We note
(1b 2/55) (2)
14 nt. (1aand
26. Cant (G)ma))
12
11.
Nu. Grans
50 Gramt
( (3
T0 + Tal (GGGmm))
- 8K SKpa (G(Gm))))
14 T7. (1 Graed 1 Cona (((Gav))
28 + ((E)
S0/ /0///////// (Gana))
2(1 Gons" (x)
fr. Pi Greec)) 8K jKū ji(GGrreck)
(8K) + (C2, (()mm)))))))) 22 Grame (t) S./e2 (
5K7 (K7(
(8K) + 62 + 22ln@amallee (
11.0 12 (G(mm))
p. + ((Grreee)
8K p3( GGreek)
(8K) + (5), (()ma)))))) 2 Game"
2. (27
p. (i(Gmmm)) 8K KKz(( (GGGmm))
(8K) + K2 + 2 (iGGrree)) K8
T/. + M. 8K (Kp( GGrec))
(8K) + K² + 2 (rrrre))) K8
Tt.
Thus, under the assumption & (implying 82 & <)), we have
(2b6 165
K + K2 + 2/ (((Gomet)) K
(3))))
1
n.
This implies that we have
K + K2 + +2 ([GGneee)) K [[fll
f(+) - Σ f(g)
(1(0))))
<
1b
9EG
29

---

Under review as a conference paper at ICLR 2023
For the right-hande side summand of the estimate in
(22
note
Tig Th (l(Game)
Σ f())
97
Σ f(g)
11a
112
9EG gi
gEG g+
l Σ
Ng: Te/ ((
min ge (()
gEG
[f Σ
ng. Me/ (G
min ge geGratin
gEG
Iflecc Come (C
min gEGLammn uff)
Pg
K GGeekk)
8.
|feea
min geazatin
[1g
Putting all together, we find for 8 & that
|l - Hllle 88. KA, [Ifller))
with
KTil Greex) + 2
K ((GGreok)
K + K2 + +2 75 (GmaG K
KAA =
min
Pig
min
Dgg
geG Latin
geGzatin
Thus left hand side of 19 holds with
K.K.
Right-hand-side of (19
Hence let us now check the right hand side of
We note
(Née u) ())(()
(u JJu) =
2/5
Let us denote by M the matrix representation
(155 :)
(()))
M = Id - .J Id
1
x.
zEG
We use the triangle inequality to arrive at
lu- JJu) leics
< 1 ua00uleecc el + 1M155 1M
|u [
(23)
Using the fact that for * * we have nig - Ö an nh = 1 Eams we find in the (8 - 0)-limit that
(0
O O X
Op x Gomaufo
M
(
with
30

---

Under review as a conference paper at ICLR 2023
aa
M
1
Pr
Na
Pig
(iGrneec) + Fr.
acting on e (/Grrel U (+]) For any element u e(G), let us denote its restriction to Grree u (+]
1 P/Gmma J (*]).
We thus find
M
21 ea Comeulo) = <M u. M
we ea (Goma
Σ
Σ
[(i)(()))
Σ
Dia
Paa
Jos
Kig Pil ((GGmoak P..
iil (iGGnneck) + Pi.
iecond (f (eGend)(())
a, (.
Σ
Σ
2 (())((
Σ
8ia
The
Dadas
PoPti
p (((GGroo)) + Pe
P (((GGrod) Pr
iEGomi (EGumsu())
OE (EGumeu())
Σ
Σ
((i)((i) x
ff (EGromo
8egPiaPs
draiodradas
Pil ((Grredd) 7s.
Pul ((GGireett + Pt. (ū(GGreeet + p2a
(EGome
Puste Pu:des To ([GGree) + Tea
Σ
Σ
[(i)e(())
vEGomau { (eGamou(s)
Tiifii
(e(1)) =2())2
(G(Gomot) 50.
(JeGond))))
To proceed, we prove the following Lemma:
Lemma J.7. Let i, E Goreet O (+). Denote by Comauto (1, (1.,) the minimum number of edges for which Wiy 2 needed to connect and j by path. Set
Cammo(())
max irjeGonaU(s)
(
Furthermore set
= min
Wig.
is i+JeGomau(s)
We have
(Cammvitt)
(u)) u00) < o
v (o(w).
Vi2
We call CGamot+) the connectivity constant of the sub-graph Goreet {+) and note that it is well-defined since assume Gand (+) to be connected.
31

---

Under review as a conference paper at ICLR 2023
Proof. Fix i and j. Let {i, .1. In. j} be the vertices traversed by path of minimal length determining C (a) J). We then have
(nii) maiill (x))) a(si) + (u(g)) - u(y2)l + + (u(gn) u(j)l
<8) 1
V (V (u(1) - 2((1)12 V W 0102 (u(r)) u(02)12 + + V Wam.llu(sn)) =mti)²
<0
vn (v Ev(u) + *v EEE(()) +... + v Ez(u)
1
8 Ca
(1)
Ed(u)
VΩ
Camaul+)
/F((u).
VΩ
With the help of this Lemma we then find
M ul e(G) $ 82
C Comeula)
V EE(())
Σ i.e
Pijaa Pa(G Gme))) Pe
vn
CGamuit)
V (i(omn)))) + the
82.
V Ra(l).
VΩ
To derive a bound for M - M op
in the second term of the estimate (3), we write
B A
M M
A' D
Here we denote by
At e (Glati))
l (GGree U {+))
the adjoint of the operator
A (GGre U (+))
((Grain))
Clearly ||Alopp = |At lop so that we have
I M 11op
| + 22| |D D
(24)
To bound B|ppp we note that B is diagonal and we have
Na
B =
74b
32

---

Under review as a conference paper at ICLR 2023
so that
1
| op
max
Ma
LEtinn
1/
1
1
max
Na
aEG Latin
14
Na
5
Pa
max
Na
LEGia
P1 Pa
Pa Pa
max
Na
DEGLutin
Pra
Köjī Greek))
max LEGLaton
Na
puu
K T((GGme)))
< 8
min
To estimate || we note
(o))
(2)))) #
(a))
We can consider the map
A E (Gored u {+}) - (Grain))
composition of maps
A: (.Grre v {x}) Id, ClGomaufoll A C1Gtall 1d (Gramn))
For the map Id: ((Gamed U (+)) ④ (Gmmeu(t)) we find [d]lop
min g
Similarly
find for the map Id 2 (Gaaii)) C GGanal that [Td
max grGnam
T6g
To bound the operator
norm of the map A : C Good Cl Ciaaal, we use that the operator-norm is smaller than the maximal column-sum times v Gooee
{+] Hence for A map from ClGamautt)l C/Gamdl
33

---

Under review as a conference paper at ICLR 2023
find
|| < ViGere u f+]l
Σ (a)
max Croeok
min Hg gEGitmin
-ViGome u {t]
(2(a)
max aE DEG
min Hg geGram
8. K V G6mm [+]]
min gEGr
19
min aeGooa
V Pa
8 8 K v Gome (+]]
min geCram
max v aeGrame
Pla
Here we estimated
(a)a
1150 ((
max oz Gonr
min
V Pax
aeGond
In total, we find for the operator-norm of
A el (GGree U (+}) - (GGaai))
that
max Bi
|Al 8- K. -.-//GGree u {+]1-
geGran
min geGram
Pyg
max oEGomau())
Thus let us now investigate [ op- As before. let us denote by u eGGree u (x)) the restriction of an element E (2 to Garee U {+}. We have
(2/18 (e((Gomo
(u60
[
V
Σ
4/
11
11
DeGrmm
(2h.8
" ((omnuu))))
(Wo )) ((Coma))))) +0
(v
() w.
1) (Gommutt))
150
11
110
(165 (7
(
<1/00
(1 200
205
We note for the matrix representation of the first term, that (with a, Gome u (+3) we have
()
Σ
= Σ (3)))
45
aß
34

---

Under review as a conference paper at ICLR 2023
Using the 'maximal row sum trick' complementary to the 'maximal column sum trick' already used for A above and recalling the definition the weights
ug = Σ (h) N
heG
we find
14
max (+)
V Mx
Goree u {+}]
Σ
Σ
max AeGomeu(t)
min (x))
Cram
Vina
max
1 GGreet u [+]]
re (e
Σ zeGru
ug Ta(())
max aEGomdu())
min yeGomauft)
Why
Thn max uEGamau(s)
Goreet u {+]
Σ Te(a) zeGrni
max Vag (xGoneu())
min vEGomaufs
Tuz max
Gomer u {+]] GEGouuu(s)
(a)a)
max
min yEGonau
My aEGomau(t)
GGmed u [+]
11 (a(G)))))
max
min vEGomo
My
aEGoom
max
P1z
VGGre u [+]]-
K 8.
min yeGomau(s)
35

---

Under review as a conference paper at ICLR 2023
remains to bound the second term. We find (using vi
e (Nons)()))) )
((Gons)(a)))
665
w. es
(vh w ea (Goma
10
14
12 (Gans((a))
1
(W () 4) (2
11
22 (a)ome))))))
(40 u 1 (GGnu 150
12
(Goa))))))
22 (3 (
112
p2)
1
11) e2 (C)mm))))))
<1/ (1) (3
w- (1/, ( w1 -6--6% 5. (ona
10
|we|l (
14
1000 (e) -eelle (Gomauf)))
+2
K Ti (rroo))))
(p X(Gome)) [|u]] ((Goma)(1))
N. + j5l (mmmm
15-
(5. K To Ti(Gored)) VVa + ()GGrrd)) Lull ()))))))))
+2
p. + ((GGrt)))
Thus find
(
Dloop &8. K ((Gonet))
+
Vūn + Tol (iGrn))))
In total, using 23 and 24 we find
[/- JJu) (3)
(Ganau(t) V Pol Grrea) + pr.
<8t
/ Eσ(u)
VΩ
Bg
K (iGeree)))
+6.
1ulleaia)+ +2. K v GGnoe u {x]1-
gEGrain
||ulle
min Ma aEGratin
min By max Grann
aEGama
+8. T ((GGre))
1
+
H1.
Vp. + (GGGre)))
36

---

Under review as a conference paper at ICLR 2023
and may hence set
(Cummiit) VV (((Groo)) Pin
= 52.
V12
max Bg
K Pi (GGGe))))
+8
+ 2..6 K / |Grrect u [+]
Glainn
min Ma LEGia
min
Pg
max (eG
geGram
+8. K 7 ((Greo)))
+
Pr.
V [r. + TV( Grreek)
hifd-hand-ssde of (20):
The left hand side of 20 is true with e 0 by definition.
Right-hand-side of 20
Let us thus check the right hand side of (20):
We have
(Ju- Pu)(a)
1
w) u(x).
Mr
We note
I[Ju Jun-ee
1 &
+/2 (u, u(()) vuz
u)
u(x)
2
ug.
(25)
1
Mx
DEG g++
We first deal with the left hand term of the estimate and note that for x we have
1 1 = Ti.. + Tí Gi(Gmmo))
and in the limit 0 that
1
W u) (())) ca(t)
Σ
u(g)
u(+))
Jr. + jú( (GGGne))
LoECemeu(t)
Σ
u(g) m(())
jr. + jú( TGGGe))))
geGumme
lu(g) u(+)l
R. + Pu( ((GGre)))
gEGomauss
8 (Cemmautt)
Σ
E
71. + Ta( GGmet)
vn2
gEGonauts)
<82 GG U {+]]
(Coomuutt) Vn
V Ez(l))
nr. ((Grreck)
37

---

Under review as a conference paper at ICLR 2023
Here applied Lemmal
J.7 Comparing the 5 > 0 and å = 0 terms, we find
1
1 eeea 114
1) ((
14
Kut v. u) e00)
+
1
1
112
|ule (55llel(Gamm))
+
1
(Nt + 70 Game)) Jullere
P.
112
Kg [uller00) +
(ī. + ]i(GCmat) || eg
n..
[i (Ti+ (i(GGreck)
2K
=6 ||u| ((
Thus we have
1
uu 0t u(())
v 12 <o²
Grree u [x]]
( (Comeeltt)
/ EE(u))
12
V j. + ((Grnook)
vS2
2K +
l2lloa(@)
For the remaining term in 25
we note
2
Σ
(1
u)
(())
r((x))
fr
2
Σ
Ux
|1(())/24
Σ
Ku
Ver u (e Vin.
1
DE DEGio
K8
lu (())
+ Σ
[1/) (
K8
|u|
(=(())
+ 1 ((elle)))
max
V 1 Iulerco
74
K8
|ulea() + +8K Grree)
max Tiz + 8K Pu Greed) Uu (ul
n.
LeEGrane
K8.
max The + VoKT Grrees) VaEGio
||u + 5KK Greek)
Iul
n.
Equation 21
It finally only remains to prove the energy differences of 21 and establish
[E f. Eo(f. F < e
v |ull + (z)
38

---

Under review as a conference paper at ICLR 2023
We note that the (unique) operator associated the energy Eg via
Ea(o. = (g. ()f)
given by
(Aa)(x)
Σ Woy(((s) - f(y)).
Pz wmaz
Here the notation "y ~ x" signifies that nodes x and y connected within G through edges with positive edge-weights Way > O.
Similarly the operator associated to F via
(v u) = (v, eo))
given by
(A
Σ Way(u(x) u(v)) fte y-0z
1
with the equivalence relation ~a precisely signifying that W ay 0. As before. let us denote by E ( (x}) the restriction of an element E f. Ganed u {*). We note
Eg (c u)
(
Aowe(s)
Way(u(x) u(y)) wra
Σ
the smaller graph G. For the graph & we find
Eg(Ve, u) = Σ
Way(u(x)- u(y))
+ Σ
(a) Σ
Wap (ay(u(a) - a(y)).
aeGomt
y~ga
Remembering that we have
J' Σ
Sa) and (Ju)(z)) =u(x),
DEG
we note
Eg(J' f.u) Ec(f,J'ul &
Σ
F(x) E u) - Ec( ui
lIfer
Σ
Ea(Us. u) (b(
min DeGimmu
Tio
Let us first bound the terms corresponding to x * We have
EiG then 2
Σ (ay(u(x) u(v)) W.- - u(+))
g y+
Σ
(ay(u(x)- u(v)) W.. - u(+)),
g G 82
39

---

Under review as a conference paper at ICLR 2023
well
Eg(
Σ W (uy(((x) - u(y)) +
Σ (a(a) Σ
Way(u(a) z(y))
aeGom
y=
Σ
W (uy(u(x) - u(v))
g~
W (u(x)) u(+))
Σ
Wmn (2(2) - -((a))
aEGom
Σ (a) Σ
Wav(u(a) u(y)).
nEGon
Hence (for x +
EG(Ue2 u) - -EG(Ve: u) = (ul(u(x) u(+)) (al(u(x) -u(+)) u(+))
Σ (za(u(x) u(ax)
atGant
Σ
(a) Σ Way(u(a) v(1))
aEGemt
W na
(u(x) u(+))
Σ ararm
Wzr (e(x) (u(x)=u(a))
(26)
(a)
Σ
Way (ul(a) u(y))
aEGond
g
(ao(u(a)) -u(+))
aEGom
Σ (a) Σ
(ay(u(a)- u(y))
Gowe
y~za
=11=
For Is we find using Lemma J.7 that
(Ccomuutt Vn
|La &
Σ
Wan
v Falu))
neGoom
and hence
(Coometat) ) > FF(w).
Σ
1L &
Σ
W
55
vΩ
FEG
.EG aetamt Ligee
40

---

Under review as a conference paper at ICLR 2023
To bound [
note
Σ
The
Σ
W (ay(u(a) u(y))
Σ (2(a)
Σ
Way W (al()(() u(v))
aeGom
g/ c
aEGGnd
g
Σ
Tel
Σ yr
Wy yo
Σ
Wya paluu(a) - =(1)1²
DE oeGum
30
(a).
Σ 2~
W
V Eg())
ga
GEGGrd
Thus we find using Cauchy- Schwarz - that
Σ 11
Σ Σ
(a)=
Σ
W
Eg(u)
ya
REG
BEG att acGrmmt
Σ
Σ yaga
W ya
V (
11550 (((aaa)))))
Σ
Σ W ya
Ez(u)
min
Ma
aEGant
LeGGnd gr
1/4
K8.
Σ
W
Ez(u)
min Via nEGamt
ya
aeGo
K8.
Σ
Jo
. Eg(u).
min
Pa
of NEGut
DEGuimk
Here we denoted by do the degree of the node a. We further note
Σ
J
Σ
Σ
Way
Σ
Σ
Way-
QEG
DE OuGu yeGrom
agGioe VEGomAu(s)
Writing
Hen
Σ
Σ
Way
aEGiom V=Goomo
for the sum of 'internal' degrees of greek nodes within Greek U (+] at 1 and
dexternal = Σ Σ Way
GeGaoe MeGra
for the 'total connection strength' between the Greek and Latin sector, we thus find
Σ [12 < IV
/ dine Vo + / Veeternal 6] min Vmn
K
Eg(u).
FEC
aeGand
remains to bound the x term (66 To this end we note
Eg(D., u)
Σ
W (uy(u(+) - u(y))
41

---

Under review as a conference paper at ICLR 2023
and
Eg((,,, u) = Σ W.y(u(+) - u(y))
g g-0*
Σ (a) Σ
W Wya(u(a) - -2(1))
neGo
m~
For the difference of the energy forms we thus find
Ec( u) - Eg( u) =
Σ
W. (u(x) - u(y))
g
Σ
W. (u+( u(v)) - Σ
T(aa) Σ
Wya(u(a) - u(v))
aeGovd
v~ga
Σ y-c*
W Way(ul) (u(x)) - u(y))
Σ W (.y(u(+) u(v)) -
Σ (a(a)
Σ
W (u(aa()) - u(v))
oeGond
Σ oEGund 3/2
Σ
W (u(a) u(y))
Σ
Σ
W (u(() u(y)).
aE aEGum 11 8~80
We have
Σ
Σ Woa(u(a)- - u(v)) =
Σ
Wna(u(a) - -(()) +
Σ
W (pa()(a) -uy))
GEG GEGGndd
9000
GeG
vecrum
W (ya()(()= - =(())
oeGamd
yEGramd
=0
42

---

Under review as a conference paper at ICLR 2023
with the last tenn vanishing by symmetry. This implies
Ev u) (x u)
Σ aEGront
(a))
Σ (al(u(a) - u(v))
y ya
Σ
W
(u(*) - u(y))
youa
yeCium
Σ Way(u(+) u(y))
Wra(u(a) -((x))
E
Σ
(ay(u(a)- - e(y))
aeGa
aeGa
y-
yEEi
Σ
(1 (1-m((a)
Σ
W (ua(u(() - -u())
arGant
yaza
Σ
W ga
(u(*) - u(v))
y
(EE
yeGrain
Σ
Way (u(() - -u(y))
yNG* yeGond
Σ W.a(u(a) -u(+))
Σ
Σ
W (ay(u(a) - w(v))
aeGovd
GrGG yE
3- aa
Σ
-1-1) (a()
Σ
W (
aeGond
y~ga
Σ
Σ
Wya (u(*) - -(()))
y-u+
(nE(mm))s(1)
Σ
Σ
Way(u(a)-u(()
aeGona
M ga
DEGram
Continuing, find
Eo(D,, E)(
Σ (1- (a)) Σ Wya(u(a) u(y))
aeGiont
30
Σ
Σ
W (ya(u(()) - u(y))
agGant
y-aa*
veGra
(ay(u(a)- -u())
aEGund
yeGrase
(1
Th(())
Σ Wya(u(a)- - u(v))
aeGumt
Σ
W yo (u(+) u(y))
agGum
Σ
W (yn( -u()))
a
y
43

---

Under review as a conference paper at ICLR 2023
This in turn we write
Ec(ú., - =1 =1+1 11
with
Σ
(a) Σ
Wal(u(a) u(y)),
ar Gond
vrga
and
== Σ
Σ - u(a)))
ac aeGom ( DEG
For the first term, we find
| Via
Σ da (B(u))
min
neG
ne neGe
< <[V <IVarr
Dimt vo + v denternal
8) min Via V Fz(u). aEGGad
K
For the second term we note
11 < Σ
W woclu(+)= u(a))
neGave 30 yeGraa
(Caamvltt)
W ya
V Es(u)
VΩ
aEGGme aa
yEGrom
=Vo denternat
Bo(u).
VS2
K PROOF OF THEOREM 5.7
We prove the following theorem:
Theorem K.1. In the setting of Theorem 5.6 denote by T (f) adjacency matrices or normalized graph Laplacians on (G) (G)) There are no functions 77. 77. : [0, 1] Rgo with ()(6) as 5 - 0 (2 2), families identification operators Jé, and w C so that JH and j are m (6) -uua---uauuuiaan with respect to f. T and w while the operators T and T remain w-m2(0) close.
Proof. We prove these two result through contradiction on a graph with two vertices and one edge with weight 1/8, which we collapse. First fix T (T') to be the adjacency matrices
W
8
and
W 0.
The cigenvectors and eigenvalues of W are given by 1 -. 1 and
(+) and 0+
(
44

---

Under review as a conference paper at ICLR 2023
Denote the orthogonal projections onto the corresponding eigenspaces by (P-, Take the function to be defined as
9(A) == 1
Then since g(0) = 0 we have
9(W) O.
Furthermore we have
9(
1
P
P
1
1
P4
P_
P
P-
+i
1
ld
P
P_
1
p1
+
P-
+
0+1
2i
Id
1
P-
8
+
8 +
We interested in
- JJ )
o(
J 8
Pt
8 P-
j
+
Assuming
(o(W) - )
= ((W))
$ m0())
lpp
also find
| oo
i (+:)
-118pp111
82i
()))))
+
+
Thus also
52i
|| oop
m (6) +
1 +1J
8 ii
op
+
Taking the limit and using the condition demand
|| lop < 2, we find that |قر|| - as - 0. Since we
[[J [(J-j+>lo llop < 78(
with
lim (π) 0, 6
also find |olpp ||
O. Next we that have
R,,
and demand
I(Id Jo Rullop - O.
)
However
(Td Jo lop
1
Id J oop
(1 1 1lpp Jllop)
1
0.
[
[w
w
45

---

Under review as a conference paper at ICLR 2023
Thus have our contradiction.
Hence let choose T (T) the normalized graph Laplacians associated to the adja- cency matrices W (W) from above. We thus have
==
and
3 1 -1 7)
The eigenvectors and eigenvalues of L are given by {0, 2) and
i and U2 (-1)
Vo =
Denote the orthogonal projections onto the corresponding cigenspaces by (Po, P2}. Then
T= 2P2.
Chose a function y such that g(0) and without loss of generality assume g(2) 1. Then
9 (( J g(
|2 l.p
(27)
Next we consider the demand
((dd - 76) Rumull & -ull-
(28)
Since (2 - wId) bijective,
28 is implies
((Id - J Jo
(8) |o||||| + 1 |eal]] (0)))) [|w] 2] ||l||
(29)
upon writing
= - -wldo.
We also write
Va
We write
á T
3
6
and
Jd - na(d) (1) + f(0) (
From 27 we know that
lim (6( 0, 6-0
but we do not yet know the behaviour of f()), a² 6 8 - 0.
With the above notation, we find from that
(Id - J
Da f(8)a' U. 5(0)65 vb
(8)) (
Un Ub
1
Ub f(8)a² Ca f(6)6"e,
Va f(8)a' f(0)60
(7()) -4 |||||
Ub f(8)a'c. f(8)6"e,
46

---

Under review as a conference paper at ICLR 2023
Thus, combining this result with 29
we know that
Va f(o)a'v, f(8)6 f( f(5)b v/
0.
Thus, since both entries of the above vector need to tend to zero, we need both well
f(6) a -1 and f(6) 8
(16) a -0 and f()) 8
which yields the desired contradiction.
L PROOF OF THEOREM 5.8
We first note how the graph Laplacian AGN as we have defined it, is consistent with the underlying positive (in the sense non-negative eigenvalues) Laplacian
6²
A gt
082
on the unit circle S'
To this end, fix << Fix a point S¹. For any suitable function f by means of Taylor expansions we may write
f(x + h) f(x) h [ōof]( +
[Agt fl(2) + O(h²)
h2
f(x f()) - h- [8 fxx)
[A st fl(2)) + O(h)).
Adding these two terms, find
[-Ast f((x) 2f(x) - f(x + h)
f(x - h) + O(h).
h2
This motivates setting edgeweights GN 1/h² with h 2 N the distance between evenly spaced nodes on the unit-circle 51.
should be noted that this consistency property - while given a heuristic to choose weights does not (immediately) imply 'convergence' of Ac, to -5r in the sense needed to e.g. apply Levie et al. (2019)). As our proof of Theorem proceeds completely without reference to the limit-circle, do not proceed beyond the above heuristic in investigating in what (relevant) sense Agx approximates As..
Remark L.1.
We thus now want to prove the following result:
Theorem L.2. In the large graph setting of Section 5.2 choose all node-weights equal to one and N to be odd for definiteness. There exists constants K1, K2 O(1) so that for each N > 1, there exist identification operators J mapping between e (Gw) and (GGG++1) that J and J are (Ki/NN-quasi-uniiie
with respect to AGy AGx_, and w = (-1). Furthermore, the operators AGy and AGx-1 are (-1) (-1)-(Ka/N) close with identification operator J.
Proof. We first note that the normalized eigenvectors of Gy are given by
1
(x)
05k<n
VN
The corresponding eigenvalues are easily found to be
N
A/4
sin
k)
22
N
47

---

Under review as a conference paper at ICLR 2023
For definiteness, we have assumed N to be odd, that (N 1) is even. We define the identification operator J: (GNG)) - (++++) via
of
N+1
for K <
(
k+1
N+1
for K
on the orthonormal basis & JoskeN and extend it to all (GGx) via normality. This implies that
precisely the eigenspace spanned by @ N+1 (corresponding to the eigenvalue N+ (N 1)2/m²) Mil
2
does not lie the image of J. We set J to be the adjoint J of Choosing w = 1, we shall now first check the equations of Definition 5.1 Since J is isometric, we have
|J 1fl & 2|
as desired. Since J _d, we have
[ [J-J" 10 0.
Since JJ- IdeaGw)) what remains to be checked is the demand
IIdd- - JJ) & K
N2
We have
(Ud- =
n²2
$ n
1 N2
1 N+1
N
(N+ + 1)2
Thus let us now check that the conditions Definition 5.2 are fulfilled. We note that with our identification operator and by symmetry (A
NN t) we have
|JR_1 Rlop
max 0sk4
1
N2 sin (T
(N+1)² 1+
sin?
x (N+1)
x²
We now need to bound the right hand side uniformly as N - so. To this end we write a = 1/N (which implies NtJ = + a) and x (which for our allowed values implies & x < f). With this have
48

---

Under review as a conference paper at ICLR 2023
+ n² sin (
1+ (N+ sin?
T k.
1
(Ta)?
(Ta)² + sin" (TT)
(ma)² + (1 + a)² sin?
T2 I+0
1
(1 + a)2 sin?
n. )4t) - sin? (T.))
=TTa)²
[(TT)2 + sin? (TT²) [(Ta)² (1 + a)) sin?
T 1
sin
(ा. (to sin" (Tι) + a sin? ाH. I+a
-
+ sin?
TT I40
= =(Ta)²
[(Ta)2 sin? (mr=)] [(Ta))
(1 a) sin?
Tे 1
sin
TT TTa
a sin
mh: e+2 a+1
+ asin
ग T
+ a² sin²
TTd TTU
= (TT)2
[(TT)]2 sin" (πι)
[(Ta)2 + (1 2in
T
sin π. Ita
sin
a+2 a+1
+ a sin"
T. (ta
+ a² sin"
(Ta)²
[sin²
Ita a
] [[TT)2]]
sin (
sin
nxat2 a+1
sin? 2
ThE ita
asin?
Te 14a
a
sin²
バ T+a
sin π: 2=?
sin
a πτ 140
2a + a
sin
πH rta
sin
Ita
Thus we are done if we can show that the function
sin
πx a-2
sin
πe Ita
F(a,x)=
sin
π. 1+a
a sin πe 1+a
1
is bounded on the rectangle [0,1] x [0, } We change variables = (1 + a) and consider
()a,y) = sin (v((a + 2)) sin (ya)
sin (v)
sin (v)
on [0, x [0, ] instead. Away from y = 0 this is obvious. Close to y = 0 we might Taylor expand in numerators and denominators respectively and then (formally) divide them both respectively by to see that the function F(a, y) is indeed regular at = 0 too and hence on the entire compact set [o, 1] [O, 51 As continuous function, F attains its supremum this set. Denote it by K. Hence we now know
1
-
K]+ a= [2+
N
Thus have established the desired dec/y.
M PROOF OF THEOREM 6.
Theorem M.1. For p > 2 we have in the setting of Theorem 3.1 that % (f) Vy (h) n &
(ITN L,p R2 Bn) | Mls,,, In the setting of Theorem 4.3 or 5.4 and under the additional assumption that the 'final" identification operator JN satisfies JN (G)) 1.flle $
49

---

Under review as a conference paper at ICLR 2023
K- -..lllllle for all f. ((G),, have [Q(() (f(fff)lR EN DRL K
(BRL)) (BRL)N-1. 1f12,, 8.
Proof. To prove the first claim, note
|/ (/) V (g)
Σ (1 1
Σ 1 [
iEKout
[[[2x(f): - [
1 (J) 2 (g)l RK
where used the reverse triangle inequality and the fact that || (Gmm) & 11 (1e for p. To finish the proof we now only need apply Theorem
To prove the second claim we note
(() (of))lR
Σ [[ - ( (3mm)))
Kuuu
(Inos//)laa - (I
oeKout
Σ oguo
|
Σ
-
okK
& K 8. ( + (10 - IN
and the claim follows before.
The proof of the third claim proceed in complete analogy.
N ADDITIONAL DETAILS ON EXPERIMENTAL SETUP
Scaling Operators: The adjacency matrix fo the given graph is given by
16
18
19)
16
0
22
3
=
6
90
(30)
18
22
0
23
19
3
90
23
0
Collapsing Edges: We consider the setting introduced in Section 5.2 and consider generic fully
connected graph G with G = 8. We consider splitting into G GLaii GGreet Uf*} with (Graiul = 3 and [G 4. As described in Section 5.2 assume W ab. W.. = O(1), ba G and aa Eydl and W.. = -g== such that (Wop, Wore = O(1) for all a, 3 E Gored. For completeness and reproducibility, the full adjacency matrix W can be found in Appendix N We set
50

---

Under review as a conference paper at ICLR 2023
node weight G to one and discussed construct a graph G with |G] strong edges'.
4 through 'collapsing
The adjacency matrix of the larger "un-collapsed" graph G we consider in Section is given as follows
0
4
10
4
7
4
0
17
8
9
10
11
2
17
42
12
13
14
15
10
9
42
0
16/5
7/6
18/8
19/0
W
(31)
8
12
16/6
0
6/6
22/6
3/0
5
9
13
7/5
6/8
0
1/8
90/6
6
10
14
18/6
22/6
1/6
23/6
7
11
15
19/6
3/8
90/6
23/6
0
The exceptional vertex here carries index "4" ("* = 4"). Node weights are set to unity.
The Realm of Large Graphs: their resolvents:
We also plot the difference in characteristic operators opposed to
|10 d Jaau bor
331
120
3500 2008
Figure 10: Operator Differences
Their distances does not decay.
The dataset we consider the QM7 dataset, introduced in Blum & Reymond (2009): Rupp et al.] (2012). This dataset contains descriptions of 7165 organic molecules, each with up to seven heavy atoms, with all non-hydrogen atoms being considered heavy. A molecule represented by its Coulomb matrix Climb whose off-diagonal elements
Experiments on Molecules:
7 RR -R
Clmb
correspond to the Coulomb-repulsion between atoms and j. while diagonal elements encode polynomial fit of atomic energies to nuclear charge Rupp et al. 2012):
C 2
Clmb
2,2.4
For each atom in any given molecular graph, the individual Cartesian coordinates RG and the atomic charge Z; are also accessible individually. To each molecule an atomization energy calculated via density functional theory is associated. The objective is to predict this quantity, the performance metric mean absolute error. Numerically, atomization energies are negative numbers the range -600 to - 2200. The associated unit is [kcal/mol].
51

---

Under review as a conference paper at ICLR 2023
O NOTATIONAL CONVENTIONS
We provide a summary of employed notational conventions:
Table 1: Classification Accuracies Social Network Datasets
Symbol
Meaning
graph or a vertex set
G
number of nodes in G weight of node weight matrix inner product
M
W
adjacency matrix
degree matrix
graph I Laplacian normalized graph Laplacian
T
generic operator
T
adjoint of T
(T)
spectrum (i.e. collection of eigenvalues) of T an eigenvalue
(()
function applied to operator T
:: I.
operator norm (i.e. spectral norm)
Frobenius norm complex number complex conjugate of complex number open ball of radius uround
(.(w)
complex number determined by and indexed by open set extending to infinity in C
U
D
Cauchy domain C
aD
the boundary of D)
(wId -1- R..
the resolvent T at resolvent profile of T
(r())
f..dd
complex line integral
...d|a/
corresponding real line integral non-linearity
connecting operator
(possibly hidden) feature space associated GCN map associated to GCN
small numbers an identification operator (possibly dependent on some or 6)
J
G
Graph consisting of regular nodes, exceptional node and a strongly connected sub-graph
Gawe
nodes a strongly connected sub-graph exceptional node to which a strongly connected sub-graph collapsed
Grain
regular nodes in G
Ea(-)
Energy form associated the (undirected) graph G distance between nodes the circle
I- lp
p-norm on Rd natural number gruph-level feature map ussociated GCN
p
Z,
atomic charge of atom corresponding to node Cartesian position atom corresponding node i
2,2,
Coulomb interaction between atoms and j Euclidean distance between z; and z;
2 m;
52


Reviews:
[{"review_id": "wAVfmXpFvOZ", "reviewer": "Reviewer_T5hc", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This work establishes rigorous, novel and widely applicable stability guarantees and transferability bounds for general graph convolutional networks – without reference to any underlying limit object or statistical distribution. Theoretical results are supported by corresponding numerical investigations.", "summary_of_the_review": "Except for the lack of practical experimental verification, this is a good theory paper.", "strength_and_weaknesses": "Strength: The paper has a solid theoretical analysis and numerical investigations, numeric results are used to validate the claim.\nWeaknesses: Although the theoretical evidence is strong, practical experiments on real applications are missed. How to validate the practicability of the proposed theory？", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "nIVCXwoe_yn", "reviewer": "Reviewer_4m2L", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This submission provides new stability guarantees and transferability bounds for general graph convolutional networks. The analysis framework can be applied to both directed and undirected graphs based on recent advanced tools. Specifically, node-level and edge-level perturbations with some new properties are presented and discussed. These theoretical results are supported by numerical results.", "summary_of_the_review": "This submission provides new stability guarantees and transferability bounds for general graph convolutional networks. The analysis framework can be applied to both directed and undirected graphs based on recent advanced tools. Specifically, node-level and edge-level perturbations with some new properties are presented and discussed. These theoretical results are supported by numerical results.\n\nOverall, the authors present new theoretical results on the stability of GCNs models using some new tools. I didn't check the correctness of these proofs line by line. However, these theorems are quite solid works.", "strength_and_weaknesses": "Strengths:\n\n1. The submission provides new theoretical stability aspects of graph convolutional neural networks. The stability analysis is quite general and hence can potentially be applied to other problem settings of graph learning problems.\n\n2. The theoretical results are verified numerically.\n\n3. In terms of theoretical novelty, this submission develops a general theory of stability for GCNs.\n\nWeakness:\n1. It would be nice to list notations so that these theoretical results are more accessible to a general audience.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "lf7CEpJCi7", "reviewer": "Reviewer_QkKY", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper provides a holistic theoretical framework to evaluate stability and transferability of graph convolutional networks (GCN). As expected, the various theoretical results provide bounds on the changes in GCN outputs in terms of perturbations to the input signal or the structure. A novel perspective on the transferability of GCNs is presented, where transferability is established between GCNs operating on graphs under the assumption that one graph is a collapsed version of the other. Limited numerical results that validate the proposed theory are also provided. ", "summary_of_the_review": "This paper provides some interesting and novel ideas on transferability. However, a major revision is needed to expand on the motivation, significance, and applicability of these results. More comprehensive experimental evaluations will also improve the paper considerably. \n\n\n**After Author Rebuttal**\nI thank the authors for their detailed response and a significant overhaul of the paper, which help address my concerns to some extent and help improve the paper significantly. The authors have also significantly extended the supplementary material with technical and empirical content, however, I did not go through this carefully.  The contributions of the paper in the domain of stability are now better elucidated. The authors provide additional experiments for larger graphs. Furthermore, the authors added an example to the section on transferability that relates their theory to the existing theory of transferability that relies on limit objects. After considering these aspects, I have raised my score to 6. \n", "strength_and_weaknesses": "Strengths:\n\n1. The presented theory is generalizable to generic utilized filters, graph shift operators as well as non-linearities.\n2. The paper provides a fresh perspective to the transferability of GCNs for graphs with strongly connected edges.\n\nWeaknesses:\n1. While the study of stability and transferability of GCNs is a well motivated research problem, the paper does not provide significantly novel insights into the stability of GCNs. Transferability results are interesting, however, the paper lacks a convincing argument on widespread applicability of these results beyond a narrowly defined category of graphs. \n2. Experiments consider fully connected, small graphs (size = 8) and therefore, provide limited insight.\n3. Paper clarity can be improved (elaborated in the Clarity, Quality, Novelty And Reproducibility section). \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "HJZLUO2ksV5", "reviewer": "Reviewer_ekgB", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper provides theoretical bounds on the stability properties of graph convolutional networks. It does so at multiple levels: input signal perturbations, edge perturbations, and structural perturbations. Input stability refers to the output of the network not changing much if we change the input signal. Similarly, we can consider the change in output if we change the edge weights (edge perturbation) as well as if we collapse nodes connected by strong edges (structural perturbation). Numerical analysis is provided to support some of the claims.", "summary_of_the_review": "I believe the paper could have been clearer and motivated the problem better. Similarly, the empirical analysis could have been more thorough. However, I believe the problem is important and the theoretical contributions is (AFAIK) novel and note-worthy. Therefore, I recommend to accept the paper.", "strength_and_weaknesses": "___Strengths____\n    - I found the stability to structural perturbations very interesting and relevant for the community. \n    - The analysis is very self-contained and complete at multiple levels, from introducing all the necessary concepts, to analyzing a wide variety of perturbations one may face in practice.\n    - Although I didn't check the proofs in detail, the arguments and statements of the bounds are solid.\n___Weakness____\n    - The paper could do better to first motivate the \"Why\" (why do we care about what we are going to be presented). \n    - Similarly, it is lacking a \"So What\" on the bounds provided, which are often just left there as final statements, without an analysis that explains whether 1) they are (likely to be) tight and 2) what this implies for practitioners.\n    - Although well-written, the paper felt quite dense, even compared to other pure-math ML papers. More examples such as Figure 2 would help.\n    - As far as I understood, the assumption on the non-linearities discards the sigmoid and the softmax, which are popular non-linearities. It would be good to acknowledge this directly by name.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster