Approximately Equivariant Graph Networks
Authors: Ningyuan Teresa Huang
Ron Levie
Soledad Villar
Venue: NeurIPS 2023 poster (2023)
Keywords: graph neural networks
equivariant machine learning
symmetry
generalization
statistical learning
TL;DR: We focus on the active symmetries of signals supported on a fixed graph domain, and show a bias-variance tradeoff between expressivity and regularity of the estimator controlled by the choice of symmetry.

Abstract: Graph neural networks (GNNs) are commonly described as being permutation equivariant with respect to node relabeling in the graph. This symmetry of GNNs is often compared to the translation equivariance of Euclidean convolution neural networks (CNNs). However, these two symmetries are fundamentally different: The translation equivariance of CNNs corresponds to symmetries of the fixed domain acting on the image signals (sometimes known as active symmetries), whereas in GNNs any permutation acts on both the graph signals and the graph domain (sometimes described as passive symmetries). In this work, we focus on the active symmetries of GNNs, by considering a learning setting where signals are supported on a fixed graph. In this case, the natural symmetries of GNNs are the automorphisms of the graph. Since real-world graphs tend to be asymmetric, we relax the notion of symmetries by formalizing approximate symmetries via graph coarsening. We present a bias-variance formula that quantifies the tradeoff between the loss in expressivity and the gain in the regularity of the learned estimator, depending on the chosen symmetry group. To illustrate our approach, we conduct extensive experiments on image inpainting, traffic flow prediction, and human pose estimation with different choices of symmetries. We show theoretically and empirically that the best generalization performance can be achieved by choosing a suitably larger group than the graph automorphism, but smaller than the permutation group.

Approximately Equivariant Graph Networks
Ningyuan (Teresa) Huang Johns Hopkins University nhuang1 90 juu edu
Ron Levie
Technion Israel Institute of Techholoog
Levieronn@tecnionn.ac ac.
Soledad Villar Johns Hopkins University svi svillar30jhu. edu
Abstract
Graph neural networks (GNNs) are commonly described being permutation equivariant with respect to node relabeling in the graph. This symmetry of GNNs is often compared to the translation equivariance of Euclidean convolution neural networks (CNNs). However, these two symmetries are fundamentally different: The translation equivariance of CNNs corresponds to symmetries of the fixed domain acting on the image signals (sometimes known as active symmetries), whereas in GNNs any permutation acts on both the graph signals and the graph domain (sometimes described as passive symmelries). In this work, we focus on the active symmetries of GNNs, by considering learning setting where signals are supported on a fixed graph. In this case, the natural symmetries of GNNs are the automor- phisms of the graph. Since real-world graphs tend be asymmetrie, we relax the notion of symmetries by formalizing approximate symmetries via graph coarsening. We present bias- variine formula that quantifies the tradeoff between the loss expressivity and the gain in the regularity of the learned estimator, depending on the chosen symmetry group. To illustrate our approach, we conduct extensive ex- periments on image inpainting, traffic flow prediction, and human pose estimation with different choices of symmetries. We show theoretically and empirically that the best generalization performance can be achieved by choosing a suitably larger group than the graph automorphism, but smaller than the permutation group.
Introduction
Graph Neural Networks (GNNs) are popular tools to learn functions on graphs. They are commonly designed permutation equivariant since the node ordering can arbitrary (in the matrix representation of a graph). Permutation equivariance serves as a strong geometric prior and allows GNNs to generalize well [3 Yet in many applications, the node ordering across different graphs is matched or fixed priori, such as time series of social networks where the nodes identify the same users, or a set of skeleton graphs where the nodes represent the same joints. In such settings, the natural symmetries arise from graph automorphisms, which effectively only act the graph signals; This is inherently different from the standard equivariance in GNNs that concerns all possible permutations acting both the signals and the graph domain. A permutation of both the graph and the graph signal can be seen as a change of coordinates since it does not change the object represents, just the way to express it. This parallels the passive symmetries in physics, where physical observables are independent of the coordinate system one uses to express them 4 [ In contrast, a permutation of the graph signal representation. This parallels the active symmetries in physics, where the coordinate system (in this case, the graph or domain) is fixed but group transformation on the signal results predictable
fixed graph potentially transforms the object itself, not only its
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

transformation of the outcome (e.g., permuting left and right joints in the human skeleton changes a aeft-handed person to sigh-handee). The active symmetries on a fixed graph are similar to the translation equivariance symmetries in Euclidean convolutional neural networks (CNNs), where the domain is a fixed-size grid and the signals are images.
In this work, we focus on active symmetries in GNNs. Specifically, we consider fixed graph domain G with N nodes, an adjacency matrix A N and input graph signals X E gNxd, We are interested in learning equivariant functions f that satisty (approximate) active symmetries
(I) where G is a subgroup of the permutation group SN that depends on G. For example, G can be the graph automorphism group AG = {II IIA = }.T]. Each choice of g induces hypothesis class Hg for f: the smaller the group G, the larger the class Hg. We aim to select G so that the learned function / E Hg generalizes well, also known the model selection problem 6 Chp.4]. In contrast, standard graph learning methods (GNNs, spectral methods) are defined to satisfy passive symmetries, by treating A as input and requiring A(ITAII) IIX) = [TS( (A, X) for all permutations II E Sy and all N. But for the fixed graph setting, we argue that active symmetries are more relevant. Thus we use A to define the hypothesis class rather than treating it input. By switching from passive symmetries to active symmetries, we will show how to design GNNs for signals supported on a fixed graph with different levels of expressivity and generalization properties.
f fILX) s IX) for permutations II E G C SN.
While enforcing symmetries has been shown to improve generalization when the symmetry group is known priori [3]. the problem of symmetry model selection is not completely solved, particularly when the data lacks exact symmetries (see for instance [14 and references therein). Motivated by this, we study the symmetry model selection problem for learning on a fixed graph domain. This setting is particularly interesting since (1) the graph automorphism group serves as the natural oracle symmetry: (2) world graphs tend to be asymmetric, but admit cluster structure or local symmetries. Therefore, we define approximate symmetries of graphs using the cut distance between graphs from graphon analysis. An approximate symmetry of graph G is symmetry of any other graph G' that approximates G in the cut distance. In practice, we take G' as yoarse-graining (or clusterings) of G. as these typically guaranteed to be close in cut distance to G. We show how to induce approximate symmetries for G via the automorphisms of G'. Our main contributions include:
1. We formalize the notion of active symmetries and approximate symmetries of GNNs for signals supported on fixed graph domain, which allows us to study the symmetry group model selection problem. (See Sections 2 4
2. We theoretically characterize the statistical risk depending on the hypothesis class induced from the symmetry group, and show bias-variance tradeoff between the reduction in expressivity and the gain in regularity of the model. (See Sections 3 4
3. We illustrate our approach empirically for image inpainting, traffic flow prediction, and human pose estimation. (See Section S for an overview, and Appendix [D] the details on how to implement equivariant graph networks with respect to different symmetry groups).
1.1 Related Work
are typically permutation--quivarian (with respect to node relabeling). These include passsgg- neural networks (MPNNs) [1921], spectral GNNs 18 24] and subgraph-based GNNs (25
Graph Neural Networks and Equivariant Networks. Graph Neural Networks (GNNs)
30 Permutation equivariance in GNNs can extend edge types [31 and higher-order tensors
representing the graph structure [32 33 Equivariant networks generalize symmetries on graphs
[35], shapes (3 37,, point clouds (38,42), manifolds [343] 44], and physical systems [45 46) among many others. Notably, many equivariant machine learning problems concern the setting where the domain is fixed, e.g., learning functions on fixed sphere 47,, and thus focus on active symmetries rather than passive symmetries such as the node ordering in standard GNNs. Yet learning on fixed graph domain arises naturally many applications such as molecular dynamics modeling [48). This motivates us to consider active symmetries of GNNs for learning functions on a fixed graph. Our work closely related to Natural Graph Networks (NGNs) in [49]. which use global and local graph isomorphisms to design maximally expressive GNNs for distinguishing different graphs. contrast, we focus on generalization and thus consider symmetry model selection on a fixed graph.
to other objects, such as sets [34,, images
2

---

Generalization of Graph Neural Networks and Equivariant Networks. Most existing works focus on the graph-level tasks, where in-distribution generalization bounds of GNNs have been derived using statistical tearning-theoretie measures such as Rademacher complexity [50) and Vap- nik-Chervonenkis (VC) dimension [5] (2]. or uniform generalization analysis based on random graph models [ Out-of-distribution generalization properties have been investigated using different notions including transferability [54] (also known as size generalization [56]), and extrapolation [57] In general, imposing symmetry constraints improves the sample complexity and the general- ization error [7H33. Recently, Petrache and Trivedi (58) investigated
wwwooimmationggnnraiizaee tradeoffs using approximate symmetries for general groups. Their results are based on uniform convergence generalization bounds, which measure the worst-case performance of all functions in a hypothesis class and differ from non-uniform analysis.
Approximate Symmetries. For physical dynamical problems, Wang et al. 45 formalized ap- proximate symmetries by relaxing exact equivariance to allow for a small equivariance error. For reinforcement learning applications, Finzi et al. (59] proposed Residual Pathway Priors to expand network layers into a sum of equivariant layers and non-equivariant layers, and thus relax strict equivariance into approximate equivariance priors. In the context of self-supervised learning, Suau et al. [60]. Gupta et al. [6]] proposed to learn structural latent representations that satisfy approximate equivariance. Inspired by randomized algorithms. Cotta et al. [62] formalizes probabilistic notions of invariances and universal approximation. In [63]. scattering transforms (a specific realization of CNN) are shown to be approximately invariant to small deformations in the image domain, which can be seen form of approximate symmetry. Scattering transforms graphs are discussed in 66 66]. Additional discussions on approximate symmetries can be found in (67 Section 6).
2 Problem Setup: Learning Equivariant Maps on a Fixed Graph
Notations. We let I, R+ denote the reals and the nonegative reals. I denote the identity matrix and denote the all-ones matrix. For matrix Y E R Rx we write the Frobenious norm as |||||. We denote by X @ Y the element wise multiplication of matrices X and Y. We write [N] = (1. (1.....N7 N) and SN as the permutation group on the set [N]. Groups are typically noted by calligraphic letters. Given H. IC groups, we denote a semidirect product by H. x K. For a group 9 with representation ø we denote by Xøle the corresponding character (see Definition 6 in Appendix A.I. Denoting H < G means that H is a subgroup of G.
Equivariance. We consider a compact group G with Haar measure À (the unique G-invariant prob- ability measure on 9). Let & act on spaces X' and y by representations and eb, respectively. We say that map f X + y is G-equivariant if for all g e G. E X, (b () æ) = f(x). Given any map f X + y, a projection of onto the space of G-equivariant maps can be computed by averaging over orbits with respect to À
J{ Vlg (( (ò(g)z) dX(g).
(Qof) =
(2)
For u, v E V, let (u, v) be a G-invariant inner product, i.e. (Vgg), x(g))) = (u, u) for all g E G, for ull y. Given two maps f2: X + Y, define their inner product as (J1, f2) (F)(),) (2), [xx) du((r), where y is a G-invariant measure on X. Let V be the space of all (measur- able) map x + Y such that |[ = f. < 80.
Graphs. We consider edge-node weighted graphs = ([N], A, b). where [N] a finite set of nodes, A E [0, 1j XN is the adjacency matrix describing the edge weights, and b= (bi,...,by C IR are the node weights. An edge weighted graph is a special case of G where all node weights are 1. A simple graph is special case of an edge weighted graph, where all edge weights are binary. Let Ag be the automorphism group of a graph defined as Ag == (1I E Sy 11 A characterizes the symmetries of G. Hereinafter, G is assumed to be a subgroup of Sx.
w = A, blbb = b}. which
Graph Signals and Learning Task. We consider graph signals supported in the nodes of fixed graph G and maps between graphs signals. Let X' = IR Nxd_ = R x be the input and output graph signal spaces. We denote by ʃ a map between graph signals, f X - y. Even though the functions f depend on G, we don't explicitly write G as part of the notation of f because G is fixed. Our goal is to learn a target map between graph signals / X - y To this end, we assume access to training set {(X,, Y.)} where the X, are i..dd sampled from an S Sn-invariant distribution μ on
3

---

X' where Sn acts on X' by permuting the rows, and Y; = (X,, + &, for some noise &, A natural assumption is that f approximately equivariant with respect to Ag in some sense. Our symmetry model selection problem concerns sequence of hypothesis class {Hgz} indexed by g. where we choose the best class Kg such that the estimator f E Ng gives the best generalization performance.
Equivariant Graph Networks. We propose to learn the target function I" on the fixed graph using g- equivariant gruph networks (G-Net), which are equivariant to a chosen symmetry group G depending on the graph domain. Using standard techniques from representation theory, such as Schur's 's lemma and projections to isotypic components [68]. we can parameterize G-Net by interleaving G-equivariant linear layers fg : I2 xd + RR- with pointwise nonlincarity, where the weights in the linear map fg are constrained in patterns depending on the group structure (also known parameter sharing or weight tying [69], see Appendix A. for technical details). In practice, we can make G-Net more flexible by systematically breaking the symmetry, such as incorporating graph convolutions (i.e., A Afe) and locality constraints (i.e., A @ fg). Compared to standard GNNs (described in Appendix D.Ip. G-Net uses more expressive linear map to gather global information (i.e., weights are not shared among all nodes). Importantly, G-Net yields a suite of models that allows us to flexibly choose the hypothesis class (and estimator) reflecting the active symmetries in the data, and subsumes standard GNNs that are permutation-equivarinn with respect to passive symmetries (but not necessarily equivariant with respect active symmetries).
Graphons. A graphon is a symmetric measurable function W : [0, - [0, 1]. Graphons represent (dense) graph limits where the number of nodes goes to infinity: they can also be viewed random graph models where the value W(x, y) represents the probability of having an edge between the nodes and y. Let W denote the space of all graphons and 17 denote the Lebesgue measure. Lovász and Szegedy [70] introduced the cut norm on W as
IS W(u, v) dnj()) an(w))
lo =
sup S,TC(0,1] memasuureb
(3)
Based on the cut norm, Borgs et al. [7I defined the cut distance between two graphons W.U U e W,
(W,UU) = inf IW lln,
(4)
SES
where 1to.11 is the set of all measure- bijective measurable maps between [0, 1] and itself, and U (I. y) = (=)) (v)). Note that the cut distance is cormuutaiooninvariann where measure preserving bijections are seen as the continuous counterparts of permutations.
3 Generalization with Exact Symmetry
In this section, we assume the target map f is Ac-equivariant and study the symmetry model selection problem by comparing the (statistical) risk of different models. Concretely, the risk quantifies how given model performs on average on any potential input. The smaller the risk, the better the model performs. Thus, we use the risk gap of two functions f. f', defined as
A(f E [|Y f(x) IE ||| - f'()
(5)
as our model selection metric. Following ideas from Elesedy and Zaidi (8) we analyze the risk gap between any function f E V and its G-equivariant version, for G C SN-
xd y = Nxk be the imput and output graph signal spaces on a fixed graph G. Let X μ where μ is Sx -invariraatt distribution on X. Let f (X) + where & E Nx is random, independent of X with zero mean and finite variance and f : X - y is Ac-equivariant. Then, for any f E V and for any compact group & C SN, we can decompose f as
Lemma (Risk Gap). Let X' = Nxd
f= + fā.
where Jg 2of.Jz f Jo. Moreover, the risk gap satisfies
Alf = E [||x - -(()) - [[LY - Fo(X)113)= = --2
mismatch
constroint

---

Lemma 1 proven in Appendix B.1 "mismatch" between the chosen group and the target group Ag. plus the symmetry "constraint" captured by the norm of the anti-symmetric part of with respect to G. Our symmetry model selection problem aims to find the group 9 S SN such that the risk gap is maximized. Note that for 9 S Ac. the mismatch term vanishes since f is Ac-equivariant, but the constraint term decreases with 9; When G = Ag. we recover Lemma in [8]. On the other hand, for G > Ac. the mismatch term can be positive, negative or zero (depending on f*) whereas the constraint term increases with G.
adapts ideas from 8 to equate the risk gap to the symmetry
3.1 Linear Regression
In this section, we focus on the linear regression setting and analyze the risk gap of using the equivariant estimator versus the vanilla estimator. We consider linear estimator é IR Nxd + NN that predicts Y = le (X) = θ X. Given a compact group 9 and any linear map θ we obtain its G-equivariant version via projection the G-equivariant space (also known as intertwiner average),
(g( / ((g) + (g d)()).
We denote (e) = θ ( the projection of θ to the orthogonal complement of the G-equivariant space. Here V instantiates the orbit-average operator 2g (eqn. 2 for linear functions.
Theorem 2 (Bias- Variance-Tradeoff) Let X' R y y Nxk be the graph signals spaces on fixed graph G. Let SN act on X and y by permuting the rows with representations 6 and V. Let G be subgroup of SN acting with restricted representations Φlg on X and vplg g on Y. Let Xis)) i.id. N (0, xx) and Y = (X) & where f*(x) @ x is Ac-equivariant and E R.NNN Assume S1.55 is random, independent of X, with mean 0 and [SE = =o < co. Let θ be the least- squares estimate of O from n i.i.d. examples {(X,, Y2) : I.... n.). 5 be its equivariant version with respect G. Let (Xéle Xola) Ig ( (g) (g) denote the inner product of the characters. If >> Nd + the risk gap is
22dk (Xotla I Xola)
E A (1o:
= xx (
+ de
n Nd -
biax
variance
The bias term depends on the anti-symmetric part of θ with respect to G, whereas the variance term captures the difference of the dimension between the space of linear maps IR + R.Nk (measured by N dk). and the space of G-equivariant linear maps (measured by (Xwla Xola); aroof can be found in [72] Section 2.2]). The bias term reduces to zero for 9 < AG and we recover Theorem in [8) when G = Aç. Notably, by using a larger group G, the dimension of the equivariant space measured by (X#le (xla)) is smaller, and thus the variance term increases; meanwhile, the bias term decreases due to extra (symmetry) constraints on the estimator. We remark that (Xelo Xo ) depends d, A as well: For d = k k= =, o(g) ((g)) RNN are standard permutation matrices; For general d > k > 1, K(g) E Ndx.d Nd (g)) E N are block-diagonal matrices, where each block is a permutation matrix.
proof
To understand the significance of the risk gap, we note that (see Appendix B. when n > Nd 1, the risk of the least square estimator is
E
[|I
-
Nd
Nd + oe
Thus, when n is small enough so that the risk gap in Theorem 2 is dominated by the variance term, enforeing equivariance gives substantial generalization gain of order N (os--(xx1gxxxx (xelg)
Nd-1
Example 3.1. In Appendix
C.1 we construct an example with X x R R3S and x ~ (0, xx Ia). We consider a target linear function f that is Sz-equívariant and approximately Sæ-qquivariant, and compare the estimators (6) versus f (ey When the number of training samples is small,
Gemeral Brroe
52
5

---

Wi
Wi
1':3" 2
Ba g2
blow-up
do
< x(e)
1/6
Aa
Sq
Go id
Figure Overview of Definitions for Approximate Symmetries: (a) Graph G and its coarsened graph G"; (b) Induced graphons Wa, Wa with small cut distance d and their symmetries Aç S2, Ag = {e]. The induced symmetry group GG-G yields more symmetries for G; (c) Approximate equivariant mapping f that is close to fōo .c'
using a Sy-equivariant least square estimator yields better test error than the Sz-equivariant one, as shown in figure inset. The dashed vertical line denotes the theoretical threshold n² as 35, before which using S3 yields better generalization than S2. This is an example where enforcing more symmetries than the target (symmetry) results on better generalization properties.
4 Generalization with Approximate Symmetries
Large graphs are typically asymmetric. Therefore, the assumption of I" being Ag-equivariant in Section 3 becomes trivial. Yet, graphon theory asserts that graphs can be as living in "continuous" metric space, with the cut distance (Definition [T] Since graphs are continuous entities, the combinatorial notion of exact symmetry of graphs not appropriate. We hence relax the notion of exact symmetry to property that is "continuous" in the cut distance. The regularity lemma [73] Theorem 5.1] asserts that any large graph can be approximated by coarser graph in the cut distance. Since smaller graphs tend to exhibit more symmetries than larger ones, we are motivated to consider the symmetries of coarse-pe gausee-rained versions of graphs as their approximate symmetries (Definition 2 3.. We then present the notion of approximately equivariant mappings (Definition 4 which allows us precisely characterize the bias-variance tradeoff (Corollary 3 in the approximate symmetry setting based on Lemma T Effectively, we reduce selecting the symmetry group to choosing the coarsened graph G'. Moreover, our symmetry model selection perspective allows for exploring different coarsening procedures and choosing the one that works best for the problem.
Definition (Induced graphon). Let G be a (possibly edge weighted) graph with node set [N] and adjacency matrix A = {ar. [0,1])),==-- Let PN {1N ("Nt,, x })}> be the equipartition of [0, to intervals (where formally the last interval is the closed interval N-1 1)). We define the graphon We induced by G as
N We(z.y) = E
ar.s (x)
i-==
where 1 1iy. is the indicator function of the set I'y C [0, I...,,
We induce graphon from an edge-node weighted graph G' (IM), A. b), with rational node weights b, follows. Let N N be a value such that the node weights can be written in the form N' JM for some Zm E Nzo, m 1,..., M. We blow-up G" to edge weighted graph GN of Σ pm nodes by splitting each node of G' into 9m nodes {nd, fj=1 of weight 1, and defining the adjacency matrix AN with entries a
b = (bm fon
wi ne' = am.m' Note that for any two choices N2 E N in the above construction, 6 GNy W Wayy 0, where the infimum in the definition of ôm realized on some permutation intervals [0, 1]. as explained below. We hence define the induced graphon of the edge-node weighted graph G' by Wo == Wa,, for some N, where, in fact, each choice of N gives representative of an equivalence class of piecewise constant graphons with zero d distance.
Definition 2. Let be an edge-node weighted graph with M nodes and node weights (bm 1m satisfying {gm Im No20 and Σ 9m = N, and let G be edge weighted graph with N
LM

---

nodes. We say that G' coarsens G up to error e if
6 Wo)) <e
Suppose that G' coarsens G. This implies the existence of an assignment of nodes of G to nodes of G". Namely, the supremum underlying the definition of dn over the measure preserving bijections
o : [] + [o, 1] is realized by permutation II [N] + [N] applied on the intervals {IN fi= With this permutation, the assignment CG-GG defined by [N] Đ I[ + m E [M], for every ... Im is called cluster assignment of G to G".
1,..., . and j l....,
Let G", with M nodes, be a edge-node weighted graph that coarsens the simple graph G of N nodes. Let Cc-G" be a cluster assignment of G to G'. Let Ag be the automorphism group of G". Note that two nodes can belong to the same orbit of Ag only if they have the same node weight. Hence, for every two nodes m, m' in the same orbit of Ag (i.c., equivalent clusters), there exists bijection Wm.m' CG-c [m] - CG-o {m'}. We choose a set of such bijections, such that for every m, m' on the same orbit of Ag
Vmmm .m
We moreover choose im as the identity mapping for each m = 1,..., M. We identify each element g of Ag with an element y in a permutation group Ag of [N]. called the blown-up symmetry group, as follows. Given E Agr, for every m E [M] and every n E Ca-ar {m], define
gn == Vm.gm..
Definition Let G', with M nodes, be a edge-node weighted graph that coarsen the (simple or weighted) graph G of N nodes. Let CG-G" be a cluster assignment of G to G' with cluster sizes G', and Ag be the blown-up symmetry group of [N]. For every 1,... M, let Sem, be the symmetry group of CG-or {m). We call the group of permutations
CI...,,Ca Cas. Let AG be the automorphism group G',
Gc-G = (Ser x Soy
x.. Sexs) Se,.... ...
x Ag SNN
the symmetry group of G induced by the coarsening G'. We call any element 9G-sGr an approxi- mate symmetry of G.
Specifically, every element E GG-- can be written in coordinates by
8 = 8182 83 ~ (S1, 8,,, a);
for unique choice of sy Sey. = M, and E Aor (see Appendix B.2 for details).
In words, we consider the symmetry of the graph G N nodes not by its own automorphism group, but via the symmetry of its coarsened graph G". The nodes in the same orbit in G' are either in the same cluster of G' (i.e., from the same coarsened node), or the equivalent clusters of G' (i.e., they belong to the same orbit of the coarsened graph and share the same cluster size). See Figure I (and Figure in Appendix(A.2) for examples.
Definition 4. Let G be a graph with N nodes, and X = Rxd be the space of graph signals. Let
g X p where is Sy-invariant measure on R Nxd, We call f RRNx N an approximately
cquivariant mapping if there exists a function K R4 + RR satisfying lime-o k(e) = 0 (called the equivariance rate), such that for every > O and every edge-node weigted graph G' that coarsen G up to error e,
- - 11 S <x((),
where faa-ar = -so-cr is the intertwining projection of f with respect to GG--V-
Example 4.1. Here we give an example of an approximately equivariant mapping in natural setting. Suppose that G is a random geometric graph, namely, a graph that was sampled from probbiipoobabilityy space M by randomly and independently sampling nodes { C M. Hence, G can be viewed as discretization of M, and the graphs that coarsen G can be seen as coarser discretizations M. Therefore, the approximate symmetries are local deformations permutations that swap nodes if they are close in the metric of M. This now gives an interpretation for approximately equivariance mappings of geometric graphs: these are mappings that are stable to local deformations. In Appendix C.2 develop this example in detail.
G, namely,
7

---

We are ready to present the bias- tradeoff in the setting with approximate symmetries. The proofs are deferred to Appendix [3.2]
Corollary 3 (Risk Gap via Graph Coarsening). X'= =
= R be the input and output gruph signal spaces on a fixed graph G. Let X ~ μu where μ is a Sx-invariant distribution on X. Let ==="(x +G, where
R is random, independent of X with zero mean and finite variance, and f : :gNxd + BRN be approximately equivariant mapping with equivariance rate Then, for any G' that coarsens G up to error e, for any f E V, we have
0 -0l 11 2x(() |6o0all 11, + +IIscoorr1
Ag.Jaa .cr) 2S +
mismateh
construint
Notably, Corollary illustrates the tradeoff explicitly in the form of choosing the coarsened graph G": If we choose G" close to G such that the coarsening error and Il - l| are small, then the mismatch term is close to zero; meanwhile the constraint term is also small since Ag is typically trivial. On the other hand, if we choose G" far from G that yields large coarsening error e, then the constraint term l l also increases.
Corollary
via Graph Coarsening). Consider the same linear regression setting in Theorem [ except now I* is an approximately equivariant mapping with equivariance rate K, and G GG-G' is controlled by G' that coarsens G up to error e. Denote the canon- ical permutation representations of GG-G' on X.Y as ø', v' respectively. Let (x= Xe) = Sgc Xx (g)(g)x> (g) denote the inner product of the characters. If > Nd the risk gap is bounded by
Laas-Variance-Tradeee
22 (Xw Xwr)
N - (xwr Xxx)
E A
(e: V
(8) 2 -2((e) oe
og
Nd -1
Nd -1
5 Experiments
We illustrate our theory in three real-world tasks for learning on a fixed graph: image inpainting, traffic flow prediction, and human pose estimation For image inpainting, we demonstrate the bias- variance tradeoff via graph coarsening using g-Net; For the other two applications, we show that the tradeoff not only emerges from G-Net that enforces striet equivariance, but also G-Net augmented with commeety--reakingg modules, allowing us to recover standard GNN architectures as a special case. Concretely, we consider the following variants (more details in A....dixD...2).
D.4.2):
1. G-Net with strict equivariance using equivariant linear map fg-
2. G-Net augmented with graph convolution (f) denoted as G-Net(ge).
3. G-Net augmented with graph convolution and learnable edge weights: G-Net(gc+ew).
4. G-Net augmented with graph locality constraints (A O (z) and learnable edge weights, denoted as G-Net(pt+ew).
G-Net serves as a baseline to validate our generalization analysis for equivariant estimators (see (oction3)..o Yet in practice, we observe that augmenting G-Net with symmetry breaking can further improve performance, thereby justifying the analysis for approximate symmetries (see Section 4). In particular, G- G-Net(ge) and G-Net(gctew) are motivated by graph convolutions used in standard GNNs; g-Net(pt+ew) inspired by the concept of locality in CNNs, where A @ fg effectively restricts the receptive field to the 1-hop neighrborhood induced by the graph A.
5.1 Application: Image Inpainting
We consider a 28 28 grid graph as the fixed domain, with grey-scale images as the graph signals. The learning task is to reconstruct the original images given masked images as inputs (i.c., image inpainting). We use subsets of MNIST (74) and FashionMNIST [75]. each comprising 100 training samples and 1000 test samples. The input and output graph signals are (m, O I;, Fi), where z; E 288x28 784 denotes the image signals and m; denotes random mask (size 14 x 14 for MNIST and 20 x 20 for FashionMNIST). We investigate the symmetry model selection problem by clustering
'The source code is available at att.pprr//gtttb...cmm/mm///////p

---

the grid into M patches with size d x d. where d {28, 1,,7,4,2,,1 4, Here d = 28 means one cluster (with SN symmetry); d is 784 singleton clusters with no symmetry (trivial).
We consider Ga- -quiiviequivariant networks G-Net with ReLU nonlinearity. We parameterize the equiv- ariant linear layer f : R + RN with respect to Gc-c' = (Se, x x... x Sex) x Ag using the following flock-matrix form (assuming the nodes are ordered by their cluster assignment), with fui denoting block matrices, and ag. bk. Cki representing scalars:
fu
fIM
f=
Sak = ax + by 11 fui = 11 for F
[fMi
fnaM]
The coarsened graph symmetry Ag induces constraints on ag, by, Ctr. If Ag trivial, then these scalars are unconstrained. In the experiment, we consider a reflection symmetry on the coars- ened grid graph, i.c., Ag = S2 which acts by reflecting the left (coarsened) patches to the right (coarsened) patches. Suppose the reflected patch pairs are ordered consecutively, then dg
ak+1, by b for & {1, (1.3..... M 1), and eki Ck+1,1-1 for l E {1. .... M - 11.1 E {2.
M (see Figure inset for an illustration). In practice, we extend the parameterization to f Rxdx N More details can be found Appendix D.2
Figure shows the empirical risk first decreases and then increases as the group decreases, illustrating the bias-variance tradeoff from our theory. Figure (left) compares a 2-layer G-Net with 1-layer linear G-Net, demonstrating that the tradeoff occurs in both linear and nonlinear models. Figure 2 (right) shows that using reflection symmetry of the coarsened graph outperforms the trivial symmetry baseline, highlighting the utility of modeling coarsened graph symmetries.
WRAST
Fesh OnNNEST
rasticnnonsst--rllpp reflection symmetry
6:41
laper Vit
Trivia
642
kap
layee
0.22
Au %
7 833
633
0.16
15
Figure 2: Bias-variance tradeoff via graph coarsening. Left:2-layer G-Net(blue) and 1-layer linear G-equivariant functions (orange), assuming the coarsened graph is asymmetric; Right: 2-layer G-Net with both trivial and non-trivial coarsened graph symmetry. See Table 7 for more numerical details.
5.2 Application: Traffic Flow Prediction
The traffic flow prediction problem can be formulated follows: Let X E Raxdd represent the traffic graph signal (e.g.. speed or volume) observed at time I. The goal is to learn a function h(..) that maps 7" historical traffic signals to T future graph signals, assuming the fixed graph domain G:
[x(-T'+1)
x(O G mi-] (1-))) [x(+))...,,x(777)
x((+T)
The traffic graph is typically large and asymmetrie. Therefore leverage our approximate symmetries to study the symmetry model selection problem (Section 4p. We the METR-LA dataset which represents traffic volume of highways in Los Angeles (see figure inset). We use both the original graph G from 76), and its sparsified version G2 which is more faithful the road geometry. In G., the (edge exists if and only if nodes i lie on the same highway. We first validate our Definition 4 in such dataset (see Appendix D.3.I I). In terms of the models, we consider simplified version of DCRNN model proposed in [76]. where the spatial module modelled by standard GNN, and the temporal module is modelled via an encoder-decoder modelling. We follow the same temporal module and extending its GNN module using G-Net(ge), which recovers DCRNN when choosing Sx. We then consider different choices of the coarsened graph G' (to induce approximate symmetries). As shown in Table 3 using 2 clusters as approximate symmetries yields better generalization error than using clusters, or the full permutation group SN.
architecture for sequence-to-sequeee

---

G-Noligoeen)
Rebos-Sia
(8.))
Trivial
G-Nerigel
8x
S., X S.S.
S, X... S..
MPIPE
0.88
42.18 0.49
0.32
Graph
3.173
3.150 0.008
3.234 0.006
P-PPIE
36,48 0:54
81.38
$2.08 0.20
31.
0.17
Graph
3.106 = 0.033
3.092 0.008
3.174 0.013
Table 4: Human pose estimation with different choices of symmetries. Table shows mean per-joint position error (MPJPE) and MPJPE after alignment (P-MPJPE) across 3 runs.
Table 3: Traffic forecasting with different choices of graph clustering. Table shows Mean Absolute Error (MAE) across runs,
5.3 Application: Human Pose Estimation
We consider the simple (loopy) graph G' with adjacency matrix A {0, 1] rep- resenting 16 human joints, illustrated on the right. The input graph signals X E R 16x2 describe the joint 2D spatial location. The goal is to learn a map to reconstruct the 3D pose Y E 16x3 We use the standard benchmark dataset Human3 3.6M [77] and follow the evaluation protocol in (78) The generalization performance is measured by mean per joint position error (MPJPE) and MPJPE after aligntment (P-MPJPE). We implement a 4-Layer G-Net(gc+ew) which recovers the same model architecture in SemGCN (78)
when choosing
G = S16 (further details are provided in Appendix D.4.1).
We consider the following symmetry groups: the permutation group S16, the graph automorphism
Ag. and the trivial symmetry. Note that the human skeleton graph has Ag = (S²)² (corresponding investigate an approximate symmetry called Relax-S16: This relaxes the global weight sharing in S16 (that only learns 2 scalars per equivariant linear layer
to the arm flip and leg flip). Additionally,
Jsn IR-N - TR where fsig i] = a, Ssi [i. = b for * j) to local weight sharing (that learns 2 x 16 = 32 scalars, where /Relax.S,, S1 [ i] = 0z, fReaxx Sıg [i = b3 for * j). Table 4 shows that the best performance is achieved at the hypothesis class induced from Relax-S1s. which is smaller than Si6 but differs from Ag. Furthermore, using G-Net(gc improvement over Sie (representing SemGCN in (8)). This demonstrates the utility of enforeing active symmetries in GNNs that results in more expressive models. More details and additional ablation studies can be found in Appendix D.4
with Relax-S1e gives a substantial
6
Discussion
In this paper, we focus on learning tasks where the graph is fixed, and the dataset consists of different signals on the graph. We developed an approach for designing GNNs based on active symmetries and approximate symmetries induced by the symmetries of the graph and its moarse-graines versions. layer of an approximately equivariant graph network uses a linear map that is equivariant to the chosen symmetry group: the graph is not used as input but rather induces hypothesis class. In practice, we further break the symmetry by incorporating the graph in the model computation, thus combining symmetric and asymmetric components.
We theoretically show a bias- variina tradeoff between the loss of expressivity due to imposing sym- metries, and the gain in regularity, for settings where the target map is assumed to be (approximately) equivariant. For simplicity, the theoretical analysis focuses on the equivariant models without symme- try breaking; Theoretically analyzing the combination of symmetric and asymmetric components in machine learning models is an interesting open problem. The bias-variance formula is computed only for simple linear regression model with white noise and in the underparamterized setting; Extending it to more realistic models and overparameterized settings is a promising direction.
As proof of concept, our approximately equivariant graph networks only consider symmetries of the fixed graph. An interesting future direction is to extend our approach to also account for (approximate) symmetries in node features and labels, using suitably generalized cut distance (e.g., graphon-signa cut distance in [79]; see Appendix C.2 for an overview). Our network architecture consists only of linear layers and pointwise nonlinearity. Another promising direction is to incorporate pooling layers (e.g., [2 80) and investigate them through the lens of approximate symmetries. Finally, extending our analysis to general groups is natural next step. Our techniques are based on compact groups with orthogonal representation. While we believe that the orthogonality requirement can be lifted straightforwardly, relaxing the compactness requirement appears to be more challenging (see related discussion in [46)).
10

---

Acknowledgments
This research project was started at the BIRS 2022 Workshop "Deep Exploration of non- non-Fuulidean Data with Geometric and Topological Representation Learning" held at the UBC Okanagan campus in Kelowna, B.C. The authors thank Ben Blum-Smith (JHU), David Hogg (NYU), Erik Thiede (Cornell), Wenda Zhou (Open AI), Carey Priebe (JHU), and Rene Vidal (UPenn) for valuable discussions, and Hong Ye Tan (Cambridge) for pointing out typos an earlier version of the manuscript. The authors also thank the anonymous NeurlPS reviewers and area chair for helpful feedback. Ningyuan Huang is partially supported by the MINDS Data Science Fellowship from Johns Hopkins University. Ron Levie is partially funded by ISF (Israel Science Foundation) grant # #1937/23. Soledad Villar is partially funded by the NSF-Simons Research Collaboration on the Mathematical and Scientific Foundations of Deep Learning (MoDL) (NSF DMS 2031985), NSF CISE 2212457, ONR NO00 4-22---22-1 and an Amazon A12AI Faculty Research Award.
References
[1] M. M. Bronstein, J. Bruna, Y. LeCun, A. Szlam, and P. Vandergheynst. Geometric deep learning:
Going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18 42, 2017.
[2] Fernando Gama, Joan Bruna, and Alejandro Ribeiro. Stability properties of graph neural networks. IEEE Transactions on Signal Processing, 68:5680-5695, 2020.
[3] Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges, 2021.
[4] Carlo Rovelli and Marcus Gaul. Loop quantum gravity and the meaning of diffcomorphism invariance. In Towards Quantum Gravity: Proceeding of the XXXV International Winter School on Theoretical Physics Held in Polanica, Poland, 2-11 February 1999, pages 277-324. Springer,
2000.
[5] Soledad Villar, David W Hogg, Weichi Yao, George A Kevrekidis, and Bernhard Schölkopf. The passive symmetries of machine learning. arXiv preprini arXiv:2301. 137244, 2023.
[6] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
[7] Alberto Bietti, Luca Venturi, and Joan Bruna. On the sample complexity of learning under invariance and geometric stability, 2021.
[8] Bryn Elesedy and Sheheryar Zaidi. Provably strict generalisation benefit for equivariant models.
In International Conference on Machine Learning, pages 2959-2969, PMLR, 2021.
[9] Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Learning with invariances in random features and kernel models. arXiv preprint arXiv:2102.13211 2021.
[10] Clare Lyle, Mark van der Wilk, Marta Kwiatkowska, Yarin Gal, and Benjamin Bloem-Reddy. On the benefits of invariance in neural networks. arXiv preprint 20Xiv:2005.00/78. 2020.
[11] Bryn Elesedy. Group symmetry in pac learning. In ICLR 2022 Workshop on Geometrical and Topological Representation Learning. 2022.
[12] Bryn Elesedy. Provably strict generalisation benefit for invariance in kernel methods. Advances Neural Information Processing Systems, 34:17273-17283, 2021.
[13] Arash Behboodi. Gabriele Cesa, and Taco Cohen. A pac-bayesiaa generalization bound for equivariant networks. arXiv preprint arXiv:2210. 13150, 2022.
[14) Gregory Benton, Marc Finzi, Pavel Izmailov, and Andrew G Wilson. Learning invariances in neural networks from training data, Advances in neural information processing systems, 33: 17605-17616, 2020.
[15] Jameson Cahill, Dustin G Mixon, and Hans Parshall. Lie pea: Density estimation for symmetric manifolds. Applied and Computational Harmonic Analysis, 65:279-295. 2023.
[16] Vasco Portilheiro. A tradeoff between universality of equivariant models and learnability of symmetries. arXiv preprint arXiv:2210.0944 2022.
[17] Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini. The graph neural network model. IEEE Transactions Neural Networks, 20(1):61-80, 2009.
11

---

[18] J. Bruna, W. Zaremba, A. Szlam, and Y. LeCun. Spectral networks and deep locally connected networks on graphs. In International Conference on Learning Representation, 2014.
[19]
Justin Gilmer, Samuel S. Schoenholz, Patrick Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning, pages 1263-1272, 2017.
[20] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference Learning Representations, 2017.
[21] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations 2018.
[22] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems, pages 3837-3845, 2016.
[23] F. Gama, A. G. Marques, G. Leus, and A. Ribeiro. Convolutional neural network architectures for signals supported on graphs. IEEE Transactions Signal Processing, 67(4):1034-1044 2019.
(24] R. Levie, F. Monti, X. Bresson, and M. M. Bronstein. Cayleynets: Graph convolutional neural networks with complex rational spectral filters. IEEE Transactions on Signal Processing, 67(1): 97-109, 2019.
[25] Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? Advances neural information processing systems, 33:10383 10395, 2020.
[26] Erik Henning Thiede, Wenda Zhou, and Risi Kondor, Autobahn: Automorphism-based graph neural nets, 2021. lttps://s//// hatg//bb//// abtp///....... 01710
[27] Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks. arXiv preprint
2021.
[28) Giorgos Bouritsas, Fabrizio Frasca, Stefanos P Zafeiriou, and Michael Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
[29] Fabrizio Frasca, Beatrice Bevilacqua, Michael M Bronstein, and Haggai Maron. Understanding and extending subgraph gnns by rethinking their symmetries. arXiv preprint arXiv:2206./1140, 2022.
[30] Bohang Zhang, Guhao Feng, Yiheng Du, Di He, and Liwei Wang. A complete expressiveness hierarchy for subgraph gnns via subgraph weisfeiler-lehman tests. CoRR, abs/2302.07090, 2023.
[31] Jianfei Gao, Yangze Zhou, and Bruno Ribeiro. Double permutation equivariance for knowledge graph completion. arXiv preprint arXiv:2302.01313, 2023.
[32] Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. arXiv preprint 11X.0.1812.099002.200 2018.
[33] Christopher Morris, Martin Ritzert, Matthias Fey, William L.. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI Conference Artificial Intelligence, pages 4602-4609, 2019.
[34] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander J Smola. Deep sets. Advances in neural information processing systems, 30, 2017.
[35] Taco Cohen and Max Welling. Group equivariant convolutional networks. In International conference on machine learning, pages 2990-2999. PMLR, 2016.
[36] Yashil Sukurdeep et al. Elastic shape analysis of geometric objects with complex structures and partial correspondences. PhD thesis, Johns Hopkins University, 2023.
[37] Jameson Cahill, Joseph W Iverson, Dustin G Mixon, and Daniel Packer. Group-invariant max filtering. arXiv preprint arXiv:2205. 2022.
12

---

[38] Nathaniel Thomas, Tess Smidt, Steven Kearnes, Lusann Yang, Li Li, Kai Kohlhoff, and Patrick Riley. Tensor field networks: Rotation-and and translation-equivarian neural networks for 3d point clouds. arXiv: /802.0822. 2018.
[39] Fabian Fuchs, Daniel Worrall, Volker Fischer, and Max Welling. Se (3)-transformers: 3d roto-translation equivariant attention networks. Neural Information Processing Systems, 33, 2020.
[40] Mario Geiger and Tess Smidt. arXiv:2207.09453 2022.
e3nn: Euclidean neural networks. arXiv preprint
[41] Soledad Villar, David W Hogg, Kate Storey-Fisher, Weichi Yao, and Ben Blum-Smith. Scalars are universal: Equivariant machine learning, structured like classical physics. Advances in Neural Information Processing Systems, 34:28848-28863, 2021.
[42] Ben Finkelshtein, Chaim Baskin, Haggai Maron, and Nadav Dym. A simple and universal rotation equivariant point-cloud network. In Topological. Algebraic and Geometric Learning Workshops 2022, pages 107-115. PMLR, 2022.
[43] Risi Kondor, Zhen Lin, and Shubhendu Trivedi. Clebsch-gordan nets: fully fourier space spherical convolutional neural network. Advances Neural Information Processing Systems, 31:10117-10126, 2018.
[44] Maurice Weiler, Patrick Forré, Erik Verlinde, and Max Welling. Coordinate independent convolutional networks-isometry and gauge equivariant convolutions on riemannian manifolds. arXiv preprint arXi::2106.0660 06020, 2021.
[45] Rui Wang, Robin Walters, and Rose Yu. Approximately equivariant networks for imperfectly symmetric dynamics. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learming, volume 162 of Proceedings of Machine Learning Research, pages 23078 mlr...ss..r...oomm wwtps//ew//ewwe//////2
23091. PMLR, 17-23 Jul 2022. html
[46] Soledad Villar, Weichi Yao, David W Hogg, Ben Blum-Smith, and Bianca Dumitrascu. Dimen- sionless machine learning: Imposing exact units equivariance. Journal of Machine Learning Research, 24(109):1-32 2023.
[47] Taco S. Cohen, Mario Geiger, Jonas Koehler, and Max Welling, Spherical cnns, 2018.
[48] Jiaqi Han, Wenbing Huang, Tingyang Xu, and Yu Rong. Equivariant graph hierarchy- neural networks. Advances in Neural Information Processing Systems, 35:9176-91 118699977,7111 2022.
[49] Pim de Haan, Taco S Cohen, and Max Welling. Natural graph networks. Advances in Neural Information Processing Systems, 33:3636-3646, 2020.
[50] Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine I Learning Research, pages 3419-3430. PMLR, 13-18 Jul 2020.
mlr. prwpseesvvvv... srress/vv19/eee http///11/9/////ee/e/ html
[51] Pascal Esser, Leena Chennuru Vankadara, and Debarghya Ghoshdastidar, Learning theory can (sometimes) explain generalisation in graph neural networks. Advances in Neural Information Processing Systems, 34:27043-27056, 2021.
[52] Christopher Morris, Floris Geerts, Jan Tönshoff, and Martin Grohe. WI meet vc, 2023.
[53] Sohir Maskey, Ron Levie, Yunseok Lee, and Gitta Kutyniok. Generalization analysis of message passing neural networks on large random graphs. In Advances in Neural Information Processing Systems, 2022.
[54] Ron Levie, Wei Huang. Lorenzo Bucci, Michael Bronstein, and Gitta Kutyniok. Transferability of spectral graph convolutional neural networks. Journal of Machine Learning Research, 22 (272):1-59, 2021.
[55] Luana Ruiz, Luiz Chamon, and Alejandro Ribeiro. Graphon neural networks and the trans- ferability of graph neural networks. Advances Neural Information Processing Systems, 33: 1702-1712, 2020.
13

---

[56] Beatrice Bevilacqua, Yangze Zhou, and Bruno Ribeiro. bize-invariant graph representations for graph classification extrapolations. In International Conference on Machine Learning, pages 837-851. PMLR, 2021.
[57] Keyulu Xu, Mozhi Zhang, Jingling Li, Simon S Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. How neural networks extrapolate: From feedforward graph neural networks. arXiv preprint arXiv:2009. 1848, 2020.
[58] Mircea Petrache and Shubhendu Trivedi. Approximatiion-generaaaaziz trade-offs under (ap- proximate) group equivariance, 2023.
[59] Mare Finzi, Gregory Benton, and Andrew G Wilson. Residual pathway priors for soft equiv- ariance constraints. Advances in Neural Information Processing Systems. 34:30037-30049, 2021.
[60] Xavier Suau, Federico Danieli, TT Anderson Keller, Arno Blaas, Chen Huang, Jason Ramapu- ram, Dan Busbridge, and Luca Zappella. Duet: 2d structured and approximately equivariant representations. In International Conference on Machine Learning. PMLR, 2023.
[61] Sharut Gupta, Joshua Robinson, Derek Lim, Soledad Villar, and Stefanie Jegelka. Structuring representation geometry with rotationally equivariant contrastive learning. arXiv preprint arXiv:2306. 13924, 2023.
[62] Leonardo Cotta, Gal Yehuda, Assaf Schuster, and Chris Maddison. Probabilistic invariant learning with randomized linear classifiers. arXiv preprint arXiv:2308.044: 2023.
[63] Stéphane Mallat. Group invariant scattering. Communications on Pure and Applied Mathematics, 65(10):1331-1399 2012. doi: htpp://dbi.org//001000///
[64] Fernando Gama, Alejandro Ribeiro, and Joan Bruna. Diffusion scattering transforms on graphs. arXiv preprint arXiv: 1806.0882, 2018
[65] Michael Perlmutter, Feng Gao, Guy Wolf, and Matthew Him. Understanding graph neural networks with asymmetric geometric scattering transforms. arXiv preprint 1rXiv:1911.06253, 2019.
[66] Dongmian Zou and Gilad Lerman. Graph convolutional neural networks via scattering. Applied and Computational Harmonic Analysis, 49(3): 1046-1 2020.
[67] Alexander Bogatskiy, Sanmay Ganguly, Thomas Kipf, Risi Kondor, David W Miller, Daniel Murnane, Jan T Offermann, Mariel Pettee, Phiala Shanahan, Chase Shimmin, et al. Symmetry group equivariant architectures for physics. arXiv preprint MoKiv:2203.0615.. 2022.
[68] William Fulton and Joe Harris. Representation theory: a first course, volume 129. Springer Science& & Business Media, 2013.
[69] Siamak Ravanbakhsh, Jeff Schncider, and Barnabas Poczos. Equivariance through parameter- sharing. In International conference machine learning, pages 2892-2901. PMLR, 2017.
[70] László Lovász and Balázs Szegedy. Limits of dense graph sequences. Journal of Combinatorial Theory, Series B, 96(6):933-957, 2006.
[71] Christian Borgs, Jennifer T Chayes, László Lovász, Vera T Sós, and Katalin Vesztergombi. Convergent sequences of dense graphs i: Subgraph frequencies, metric properties and testing. 2008
Advances in Mathematics, (19(6):8811-188
[72] Mark Reeder. Notes on representations of finite groups, 2014.
[73] László Lovász and Balázs Szegedy. Szemerédi's lemma for the analyst. GAFA Geometric And Functional Analysis, 1711):22-2270, 2007.
[74] Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/nnist// 1998.
[75] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnise novel image dataset for 2017..
benchmarking machine learning algorithms. arXiv preprint
[76] Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu. Diffusion convolutional recurrent neural network: Data-driven traffic forecasting. arXiv preprint urXiv 20117 2017.
[77] Catalin Tonescu, Dragos Papava, Vlad Olaru, and Cristian Sminchisescu. Human3. 6m: Large scale datasets and predictive methods for 3d human sensing in natural environments. IEEE transactions pattern analysis and machine intelligence, 36(7): 2013.
14

---

[78] Long Zhao. Xi Peng, Yu Tian, Mubbasir Kapadia, and Dimitris N Metaxas. Semantic graph convolutional networks for 3d human pose regression. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 3425-3435, 2019.
[79] Ron Levie. A graphon-signal analysis of graph neural networks, 2023.
[80] Alejandro Parada-Mayorga, Zhiyang Wang, and Alejandro Ribeiro. Graphon pooling for
reducing dimensionality of signals and convolutional operators graphs, 2022.
[81] Daniel A. Spielman. Testing isomorphism of graphs with distinet eigenvalues, 2018.
[82] Bruce Sagan. The symmetric group: representations, combinatorial algorithms, and symmetric functions, volume 203. Springer Science & Business Media, 2001.
[83] Jean-Pierre Serre al. Linear representations of finite groups, volume 42. Springer, 1977.
[84] Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. The Annals of Statistics, 50(2):949 986, 2022.
[85] Ningyuan Huang, David W. Hogg, and Soledad Villar. Dimensionality reduction, regularization, and generalization overparameterized regressions. SIAM Journal on Mathematics of Data Science, 1187721
feb 2022. doi: 10. 1371220mm118822 URL htttht/////oo org/ 10
[86] Somesh Das Gupta. Some aspects of discrimination function coefficients. Sankhyā: The Indian Journal of Statistics, Series A, pages 387-400, 1968.
[87] Hosagrahar Jagadish, Johannes Gehrke, Alexandros Labrinidis, Yannis Papakonstantinou, Jignesh M Patel, Raghu Ramakrishnan, and Cyrus Shahabi. Big data and its technical challenges. Communications of the ACM, 57(7):86-94, 2014.
[88] Dario Pavllo, Christoph Feichtenhofer, David Grangier, and Michael Auli. 3d human pose estimation in video with temporal convolutions and semi-supervised training. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 7753-7762, 2019.
15

---

A Parameterization of equivariant linear Maps
We consider group 9 acting on spaces X' and y via representations & and v. respectively. Our goal is to find the equivariant linear maps f X - y such that f(((g)=) = (fg)f()) for all g E g and
X. The standard way do this, used extensively in the equivariant machine learning literature (e.g. [40] 43 is to decompose & and &b in irreducibles and use Schur's 's lemma.
In nutshell, group representation yP an homomorphism 9 GL(V), where GL(V) denotes the General Linear group of the vector space V (sometimes mathematicians say that a representation of G. but we need know the homomorphism yp too). One way to interpret the group homomorphism (i.e. p(gh) (p(g) v(h)) is that the group multiplication corresponds to the composition of linear invertible maps (i.e. matrix multiplication). A linear subspace W of V is said be a subrepresentation of yp if (W) C W. An irreducible representation is one that only has itself and the trivial subspace as subrepresentations.
Schur's lemma states that if V, W are vector spaces over C and yv, fW are irreducible represen- tations, then either (1) by and fow
isomorphic as representations (and the only equivariant linear map between V. W is the zero map), or (2) yv and yPw are isomorphic and the only non-trivial equívariant maps are of the form À where À C and 7 is the identity (See Chapter of 68
Given G acting on spaces X' and y via representations @ and vh. respectively, one can decompose Ø and di in irreducibles over C
= 0
(this notation assumes the same irreducibles appear in both decompositions, which can be done if we allow some of the ag and by to be zero). Then one can parameterize the equivariant linear maps by having one complex parameter per irreducible that appears in both decompositions.
These ideas can be applied to real spaces too. By Maschke's theorem we can decompose the representation in irreducibles over R. Then we can check further how to decompose these irreducibles over C, and apply Schur's lemma. We have 3 cases for the decomposition:
1. The irreducible over R is also irreducible over C. In this case we directly apply Schur's lemma.
2. The irreducible over R decomposes in two different irreducibles over C. In this case we can send each CCirreducible to their isomorphic counterpart.
3. The irreducibles over R decompose in two copies of the same irreducible over C. In this case can send each irreducible to any isomorphic copy independently.
Therefore, finding the equivariant linear maps reduces to decomposing the corresponding representa- tions in irreducibles. In the next sections explain in detail how do this for the specific problems described in this paper. The appendix is organized as follows: We first show how to parameterize equivariant linear layers for abelian group using isotypical decomposition Seectoon[.1), and then discuss the case for the symmetry group induced by graph coarsening, which further considers parameterizing permutation-equivarian linear maps model the within-cluster symmetries (Section A.2).
A.1 Equivariant Linear Maps via Isotypical Decomposition
In this section, assume that the graph adjacency matrix A has distinct eigenvalues À1 A2 > An. Then Ag is an abelian group [81] Lemma 3... Under this assumption, we present the construction of Ac-equivariant linear maps using isotypical decomposition (i.e. decomposition into isomorphism classes of irreducible representations) and group characters. We remark that such construction extends non-abelian groups and refer the interested reader for the ease of exposition.
82 but we omit it here
We consider the simplest setting where f N - R is linear function that maps graph signals. Let x E N be the node features, then Aquequivariance requires
f(gx) = g fx) for all g E Ao-
To construct equivariant linear functions f. our roadmap is outlined follows:
16

---

1. Decompose the vector space X' = RN into a sum of components such that different components cannot be mapped to each other equivariantly (also known as the isotypic decomposition);
2. Given X' @ an isotypic representation, we then parameterize f by linear maps each X₂ such that for all i, f(X,) S X,
To this end, we need the following definitions. Definition 5. (G-module, 182) Defn 1.3.1]) Let X' be a vector space and G be group. We say the vector space X' is a G-module or X carries a representation of 9 if there is group homomorphism p: p:g + GT(X), where GL. denotes the General Linear group. Equivalently, if the following holds:
1. go EX
2. g(ev + +d)) c(go)= + d(gw),
3. (gh)u- = g(hv),
4.
for all h E G; E X and scalars d E C (e E G denotes the identity element).
In what follows, we consider X' NRN carries representation of G. Definition 6. (Group characters) Given a group G and a representation Φ - GI.(V, the group character is function
9 > R (or C) defined as x(9) == tr ((g).
Definition (Group orbits) Let be a vector space and be a group. The group orbit of an element E X is (xx)= = {gg= 9 E g).
Let 91..... Is be the generators of AG C (S2)", or simply Ag = (S2)* for some & < n. Since Ag is abelian, any irreducible representation is 1-dimensional [68 p.8]. In other words, the irreducible representations of an abelian group are homomorphisms
p: Ag + C.
(10)
Since all the elements of the group AG = (S2)* th of order 1 or 2, the homomorphisms are p: Ac - [ C R. By Definition 6 the irreducible characters (i.e., characters of irreducible matrix representation) are also homomorphisms p AG + {+1]. In other words, x(g) E {=1} for g e Ag. Then we can write down the 2 2 character table, where the rows are the characters X, and the columns are the group elements E Ag (see Table [ an example), Now, define the projection onto the isotypic component of the representation as
deg(X)
Px
Σ
x
Σ x(9)g.
(11)
AGG
AG
BEAA
gEAG
where the second equality uses the fact that Ag is abelian.
Intuitively, applying Px on X' span pran((e,..... eNT) picks out all X' that stays in the same subspace defined by the group character x. (Note that for the (82)* case x (g) x(g) since x(g) E {+)
Algorithm presents the construction of equivariant linear map f with respect an abelian group. Such construction can parameterize all abelian Ac-equivariant linear maps, as shown Lemma
Lemma 5. is linear, equivariant with respect to the abelian group AG if and only if f can be written as 133 in Algorithm T
Proof. By construction in Algorithm 1. f is linear and equivariant. To show the converse, first recall some useful facts and notations. Since Ag is abelian with all irreducible representations being one-dimensional, for isotypic components Xxi 2 Xx.. we have
g U1 (g) U1,
for all G, E E
(14)
U/ = >2(g) U2, for all E G, 02 E Xx..
(15)
where there exists some g E g such that (g * >2(()). To show f being linear and equivariant implies for all u E Xx. fv) Xx, we prove by contradiction. Without loss of generality, suppose
f(ex)) auux a2tixa
(16)
17

---

Algorithm 1 Parameterizing equivariant linear functions f RN RR for abelian group
Require:
Abelian group AG (S2)*
1. Construct the character table of Xireps for Ag. i.e. Xi A - {+1} 1....e;
2. For each character Xs in the character table, compute the projection matrix
- (Ex( (eN)] ERNN;
=
(12)
followed by computing the basis from Pxe (X) and call Xx - [6 ........... (.)
3. X' = where Xx; are the isotypic component. Then is any linear function satisfying that f(xx;) S Xxx for all = 1, ,, In particular, in the basis [ lesccssesk I can be written as a block diagonal matrix _xxa with each block My. being the linear map from Xx: + Xx.
Mx
Mx3
(13)
M
return f
Xe
1
1
X2
-1
Table 1: Character table for aut(Pa) _ Z2
for scalars a1, 02 and 8x1 Ex 8x2 Xx. Then (14 for all 9 G, f(g = (g) Ux1) = (1(0))((x))) = (1 -2( Now, since f is equivariant, for all g EG
(17)
f() (1x) g + (222)))= = (g) X2(9)a21xx- But there exists some o' E 9 such that (g')) # >2(g'), which leads to ((g'vx)) # f(g (x
(18)
contradiction. One can easily extend the proof strategy to the general case for f(ex)) = Σl Ux
Example A.1. Consider the path graph on 4 nodes (i.e., P4). We have aut(Ps) = {e, (14) ~ Z-
Steps 1: Note that Zg abelian and thus all irreducible characters x(g) E {+1), for all E Zz. The character table is shown in Table
Step 2: using
we have
0
1
1
0
e2:
which yields basis B(Px.) [e1 + e1: te]]
2
1
1
0
1
0
0
1
0
-17
Pralecsegeessea 1
0
1
-1
0
which yields basis B(Pxa) = [e1 64:42 -e3]
2
0
-1
-1
0
Step 3: Parameterize IR$ - Rd by f B(P x.)) - B(Pxx) and f B(Px)) B(P, ((Px.). For all
E R write ci(e1 + e4) + c2(e2 + e3) + c2(c: ed) + c1(e2 es). then
f(v) [1i
02
[
+
[as
06
c3
(19)
as
a4
C2
a7
as
C4
where 0i,,... ag are (learnable) real scalars. Now is linear, equivariant by construction.
18

---

A.2 Equivariant Linear Map for Symmetries Induced by Graph Coarsening
In this section, we provide additional details of constructing equivariant linear maps for using the symmetry group induced by graph coarsening (Definition B). Recall the symmetry group with M clusters of G (with the associated coarsened graph G') given by
GG-o' = (1 S2... SM) x A C C
We first assume that Agr trivial and show how to parameterize equivariant functions with respect products of permutations. Then we discuss more general cases, for instance if Ag is abelian. For the ease of exposition, we consider X E RR,Y R.
Suppose Ag is trivial we claim that a linear function f: RRR V - R is equivariant with respect to GG-G* if and only if it admits the following block-matrix form:
fu
f12
fLM
f21
fr2
fear
fkk axter + Le, 11 fki eas 1 for k + (20)
fM1
fM2
farm]
where fai are block matrices, Is is a size-k identity matrix, ll length-k vector of all ones, and ax, bu, eat are scalars. The subscript eд denotes the size of the k-th cluster. Figure 5 illustrates the block structure of f.
We provide a proof sketch of our claim. Since Ag is trivial by assumption, it remains to show any function that is equivariant the product of permutations (S, S2 Sy admits the form in
eqn. 20
We justify as follows:
(within-cluster) fKa a linear permutation-equivaant function if and only its diagonal elements are the same and its off-diagonal elements are the same (14 Lemma 3.));
2. (across-cluster) fui for * is constant matrix since nodes within cluster are in- distinguishable; moreover, еşg are unconstrained since the coarsened symmetry Ag is trivial.
fx
f12
fuM
fa
fz
fax
fan
fun
famM
Figure 5: The block structure of equivariant linear function f: RD - RR" with respect to GG-+G* (where G, G' asymmetric): Each diagonal block fuX is diagonally constant and off-diagonally constant; Each off-diagonal block fuI is a constant matrix.
As example, we illustrate the equivariant linear layer for two-cluster graph coarsening. Without loss of generality, assume that the node signals X are ordered according to the cluster assignment (e.g., X[Iiv,]] node features for the first cluster, etc). Let X(1). X(2) denote the node features for the first and second cluster, W (1) W
(2) denote the weights on the block diagonal for self-featee relf-feature
transformation, W (1)* WT denote the weights on the block diagonal for within-cluster neighbors, and Wa (12)) W(21) denote the weights off the block diagonal for across neighbors. Let denote
the identity matrix, 1 1 (2) denote the all-ones matrices with the same size the corresponding
19

---

cluster, and (12). (21) denote the all-ones matrices mapping across clusters. Recall @ denotes the Dlement-wist multiplication of two matrices. Then the equivariant linear layer parameterized as
(1 Wi) X W (2)
(2) - 1 O + (Po
X X W (2)
[ ((1))
1
(12)
(()) W (ii)) X W (21)
10
+
C
(21).
For cases where Ag is nontrivial, if Ag is abelian, 8.2). Observe that the symmetry of Ac effectively constrains the patterns of G&t in equation 20 We provide an example where Ag = S2 in our image inpainting experiment (see Section 5.1 and defer the investigation of general cases for future work.
use construction by Serre (83) Section
B Proofs of Our Theoretical Results
B.1 Proofs of Generalization with Exact Symmetries
Lemma (Risk Gap). Let = RNdd y &N the input and output graph signal spaces on fixed graph G. Let X ~ μ where p. is Sx-invariant distribution on X. Let Y Y= (X) &. where & E R is random, independent of X with zero mean and finite variance and f : X - y is Ae-equivaian Then, for any f V and for any compact group C SN, we can decompose f as
5= Jg + fg.
where fg Qgf. = - fg. Moreover, the risk gap satisfies
fgf = E [||Y f(X)i)) -E [|L fx)1
||
mirouathh
Lemma is is straightforward extension of Lemma 6 in [8) which makes use of Lemma in 8
Lemma 1 in 8]. Ler U be any subspace of V that closed under Q. Define the subspaces and A of. respectively, the G-symmetric and G-anti-symmetrin functions in U S = (f U is G-equivariant and A = E Qf = 0}. Then U admits admits an orthogonal decomposition
into symmetric and anti-symmetric parts
U U= SSOL A
Proof of [ The first part of Lemma the second part, by the assumption that the noise & is independent of X with zero mean and finite variance, we can simplify the risk gap as
f = fg + fg follows from Lemma in (8. For
A(S, fo) = E [IL - s(x) - [|LY - [x()]]
= E
- - [X)
- Fx(
(22)
Substituting f f= fg f yields
E (X) (X),,, (x)1I)
= - 11
(23)
We remark that Lemma 6 in assumes that f" is G-equivariant, the first term in 23 vanishes. We are motivated from the symmetry model selection problem, and thereby relax the assumption of the chosen symmetry group G can differ from the target symmetry group Ag.
Theorem 2 (Bias- Variance-Tradeoff) Let X = RNxd = N be the graph signals spaces on fixed graph G. Let SN aci on and y by permuting the rows with representations and sb. Let G be subgroup of Sy acting with restricted representations Ølg on X and wh Y.
20

---

Let Xig) Lid. (0,03)) and Y Y= fX) + where (*(x) OTx x is Aquevvivaiiant and +E RRNNN Assume Ep-i] is random, independent of X, with mean 0 and [55 = =o²- < co. Let Ô be the least- squarrs estimate of from n i..dd examples {(X,, Yi) : ,..., n.,, v be its equivariant version with respect G. Let (Xelg Xøls) lg X Xola (g) denote the inner product of the characters. If Nd the risk gap is
N2 (Xillo Xola)
E B (16:
=
x 1 | +
n Nd 1
bias
Theorem 2 presents the risk gap in expectation, which follows from Lemma by taking as the least-squares estimator and using assumptions in the linear regression setting. To this end, we denote X E 1xxNN Y E gexNk,& & E ==**N* as the training data arranged in matrix form, where = (X) &. Recall that the least-squares estimator of & in the classic regime (n > Nd) is
given by
:=
x -
(24)
while its equivariant map is
1 ( = / وو (())
(25)
Our proof makes use of the following results in which we restate adapted versions here for our setting.
Proposition 11 in []. Let V = {fw : (x) = WT x, W E Baxk x E R denote the space of linear functions. Let X ~u y with B[XX = For any linear functions sw,, Sw, V, the inner product on V satisfies
(fwi fwa), Tr(W, BP(WTEW) EW2).
(26)
Theorem 13 in 18 (Simplified, Adapted). Consider the same setting Theorem For n > Nd
B& V xxxxx* + xT E of 22 (Xela Xola)
n Nd -
We first plug in the least-squares expressions Ô, M (g(O) to Lemma and treat the mismatch term and constraint term separately; We complete the proof by collecting common terms together.
Proof of Theorem 2
For the mismatch term, our goal is to compute
- 2 ((,, θ 4 (+)
(27)
where the expectation is taken over the test point X and the training data X,
To that end, we write
X (o - vo(()) e.e x x) x)- x
(00 (OT + x X(XXXXXXXX (()))
(28)
Taking expectation yields
Ex.x, ((,,6 è (g)())) = ||01 Ex.x x X(Xxx)-x
- -xxx (0 x, / (1 (OT - T x Φ(9) dX(g))
(29)
Note that & is independent with X and mean 0, so the second term in 29 vanishes. Similarly, the part Ex.x (g (E X(X x)-1) Φ(g)z dl(g)) also vanishes (by first taking conditional
21

---

expectation of & conditioned on X). Thus, we arrive at
E [ θ [g(())) ||el E. (eT x, [:vo ( (())z
|| (e, ()()))
--20 1
(30)
where the last equality follows from Proposition 11 in [ with the assumption that E ox. This finishes the computation for the mismatch term.
Now for the constraint term, we have
f I (+) = xx Ex W +x+(x x) E) 11
(31)
(32)
x I + ox Ex
1 ( x) E) 1|:
(33)
where the last equality follows from linearity expectation, E[[ = and & independent of x.
Combining the mismatch term in (30) with the constraint term in b3). the risk gap becomes
E A (v.
- W.g. (0)]l +ox Ex & I (XXX) x E) 1P?
(34)
Applying Theorem 13 in [8) the second term in 34 reduces to
o Ex E ((x T x) x E) 11 of 2 (Xwla X
(35)
Nd -
from which the theorem follows immediately.
Finally, state well-known result for the risk of (Ordinary) Least-Squares Estimator (see and references therein).
84
85
Lemma 6 (Risk of Least-Squares Estimator). Consider the same set-up as Theorem For Nd+1, 1,
[[1Y - = oe n Nd
Nd + t
Proof of Lemma Recall X, Y denote the test sample. We denote the risk of the least-squares estimator conditional on the training data X E RaxNd R(O X), which has the following vlas-variance decomposition:
R(Ô x) E
||Y T x
(36)
E
[|0 x
θ
x
(37)
[1(e-)) X
x
+ o
(38)
where the last equality follows from being zero mean and independent with X. The second term o² also known as irreducible error. We decompose the first term into
E - θ)
O)
x
2
x
= E.
[[[e E(²)) X + [[
6) T X x
(39)
Recall that è
X - (x
+ - (X X 1 TT. Thus
Ł = and simplifies to E
[|(
-
6) T x]
22

---

We finish computing the risk by taking expectation over X, and using B[O] 6 (XTX)
E -
IE R( xx)
(40)
Ex [xxs [[ 6) X1 X og
(41)
E [I (I xx= E) x
(42)
oe tr (B[((X) x) - 1 + +
(43)
By 86 Lemma 2.3), for Nd + 1, E[ the proof.
x)- (
Nd No
1. Putting this in (43 completes
B.2 Proofs of Generalization with Approximate Symmetries
In Definition product,
3
we construct the symmetry group of G induced by the coarsening G' via a semidirect
Gc-G = (Sen x Sez... x Sex) Age.
We explain the construction in more details here. We first recall the definition of semidirect product.
Given groups 91 G2 and group homomorphism yp G2 - (91). construct group 91 x 92, called the semidirect product of 91, G2 with respect to şo as follows:
1. The underlying is the Cartesian product G1 G2;
2. The group operation o is determined by the homomorphism yo, such that
o: : (91 X (2) x (91 X (2) + (91 X 92) (g1,g2) o (gi.g2) = (g) Po ( g2g2), 91.9' E Gii g2:g2 E G2,
Take 91 = (So -(o, x Sce Sexc) G2 A Note that G1 is a normal subgroup in GG Namely, for all E GG--G' E 91, we have #91 8918-1 E 91- Thus, the map > = an automorphism of G1. In particular, the homomorphism Poz (91) = 92 91 92 for g2 E G2 describes the action of G2 on Gi by conjugation I In the context of a graph with N nodes and its coarsening G" with M clusters, the homomorphism describes how across-cluster permutations in G' act on the original graph G. Note that in the special case where A acts transitively on the coarsened nodes, we recover the wreath product- - special kind of semidirect product. Our construction of GG-+G' can be seen as a natural generalization of the wreath product.
Corollary 3 (Risk Gap via Graph Coarsening). Let -xx.= Nxk be the input and output graph signal spaces on a fixed graph G. Let X μ where j is Sy-invariant distribution on X. Let Y = (X) + E, where E TRN is random, independent of X with zero mean and finite variance, and f Nxd Nx be an approximately equivariant mapping with equivariance rate Then, for any G' that coarsens G up to error e, for any f E V, we have
1. 2xx(E) | 11, + -|Istaaoll
f0 [f fgf.a)))) -2f",, fa
f0
mismotch
In our context, it is sensible to write Pas (91) = 92 91 97 given that Gi, G2 are originally inside a common group Sx. Yet semidirect product applies two arbitrary groups - not necessarily inside a common group initially, where aou (91) is an abstraction of g2 g1 g192"
-1
23

---

Proof of Corollary 3
We start by simplifying the mismatch term in Lemma
!
-2
fzo
22E -2
foa (z) + fea-or (z), foa (x)) (x)
-2 (f" S8 (x),
S (x)
S2.unniisymmettn of Sr.annttsymmettii part of
2 - 2 - -S lle II lla
(By Cauchy Schwarz. Ineq.)
2 < IIfe. llu. (By Definition 4 Approx. Equiv, Map)
Putting this together with the constraint term completes the proof.
Consider the same linear regression setting in Theorem 2 except now f is an approximately equivariant mapping with equivariance rate K, and G Ga-a is controlled by G' that coarsens G up error Denote the canon- ical permutation representations of GG-a' on X, as ø', v' respectively. Let (Xe' Xex) = Jga-ar Xv (g)xx' (g)dX(g) denote the inner product of the characters, If > Nd the risk gap is bounded by
Corollary (Bias- Variance-Tradeol via Graph Coarsening).
E A (fo:
2 -2x()) 02
N2dk (Xv' Xwr)
n Nd -1 to N dk: (Xwr (xv)
n Nd -
Proof of Corollary
4
It follows immediately from applying Theorem 13 in
to Corollary 3 with
g = Ga-GG.
C
Examples
C.1 Example: Gaussian data model with approximate symmetries
Example 3.1 considers G = Sz. 9 X R R.3 and (O, Ta). The target function linear, i.e., f*)x θ for some θ 3x33 In other words, we are learning linear functions on a fixed graph domain with 3 nodes. Suppose the target function is Sz-equivariant such that it has the form
a
b
c
θ
b
a
c
a,b.C.d,EEE.
(44)
d
d
e
Now, we project θ in 46L to S Ss-equivariant space using the intertwined average with the canonical permutation representation of S3, direct calculation yields
} (2a +)
{b 3 (2a+ ((b+ctd)
$ (b + c + d)
s.s
(b (b+c+00 d) !
3 (b (b+co c d)
(45)
c
(2a
(( -e e)
] - c- d) (a e)
3 [ 2c d)
1 ( (0) - (+)=
1 c- d)
3 ( 2c d)
(46)
[ + 2d)
[ c+ 2d)
( + 2e).
Therefore, the bias term evaluates to
x I (0) = -ox 2((a (((a-))² 26-2b + + d)2
2(b 2c + d)2
2(b + c 22d)
+
+
9
9
(47)
For the variance term, recall X Xos, are both the canonical permutation representations of Sy, we have
(Xwee X(oe) (32 12
12
12
0²
0²)
(48)
24

---

(c) 55/51 [[0.57 0.13 0.12] [0.13 0.57 0.12] [0.12 0.12 0.52]
(d) 5 [[0.55 0.12 0.12] [0.12 0.55 0.12] [0.12 0.12 0.551]
0.46 0.10 0.26] [ 0.59 0.49 -0.26]
[[0.38 0.09 0.21]
[0.09 0.38 0.21]
[0.25 0.04 0.03]]
[0.48 0.48 0.40]]
Generalization Error
S3
20
30
40 20 30
40
20 30
40 20 30
40
0
Figure 6: Choosing the symmetry group corresponding the target function usually yields the best generalization ((a), (b), (d)), but not always: when the number of training data n is small and the target function is approximately equivariant with respect symmetry group could yield further generalization gain, as shown in (c) empirically. The dashed gray vertical line highlights the theoretical threshold n* 35, before which using Sa yields better generalization than S2, validating our theoretical analysis. We set ox = 1, 62 conduct 10 random runs and compute the generalization error based on 300 test points. We obtain the estimators via stochastic gradient descent, and enforce the symmetry via tying weights. The titles of each subplot indicate the symmetry of the target function, and display the target function values.
larger group, choosing the larger
Therefore, the variance term evaluates
N2 (X Xwll) o
7
(49)
Putting (47 and (49) together yields the generalization gap of for the least square estimator fa compared its Sq-equivariant version f f
As a comparison, when choosing the symmetry group of the target function G S2, the bias vanishes and note that (Xvs, (0ss)= (3² + 12) 5, generalization gap is
o 4
E A fus,
(50)
We see that choosing g S3 is better if a z e. 20 c = d (i.e., f is approximately Sy-invariant) and the training sample size small, whereas S2 is better vice versa. This analysis illustrates the advantage of choosing (suitably) larger symmetry group to induce a smaller hypothesis class when learning with limited data, and introduce useful inductive bias when the target function is approximately symmetric with respect to a larger group. We further illustrate our theoretical analysis via simulations, with details and results shown in Figure
C.2 Example: Approximately Equivariant Mapping Geometric Graph
In this section, we illustrate construction of an approximately equivariant mapping. We focus on version of Definition 3 that does not take to account the symmetries of G'. Namely, consider definition of the approximate symmetries as
G Se, So, ... x Sext C. Sx.
Equivalently, we restrict the analysis to coarsening graphs G' that are asymmetric.
Background from graphon-signal analysis. To support our construction, we cite some definitions and results from 79].
Definition 8. Let 0. The suophon-signal space with signals bounded by is WL, W x L [0, 1), where L [0. 1] is the ball of radius r in L 1). The distance WL, is defined for (W, (V.)) WL, by
s)( = [[(W,)) (V. = II -Vlla + I|s -|11.
25

---

Moreover:
ón (n s). (V. inf dn (WW, s). (Vo, g)))
where g (x) g(((z)) and & is a measure preserving bijection.
Any graph-signal induces graphon signal in the natural way, in Definition 1 The norm and distance between two graph-signals is defined to be the cut norm and distance between the two induced graphon-sigan respectively. Similarly, the L1 distance between signal a signal on [0, 1] is defined to be the L1 distance between the induced signal from q and s. The supremum in the definition of cut distance between two induced graphon-signals is realized by some measure preserving bijection.
graph and
Sampling graphon-signals. The following construction is from [79] Section 3.4]. Let A (A1,-. ........ Ax) E [0. 1j be N independent uniform random samples from [0, 1), and (W, s) E WC,. We define the random weighted graph W ((A) as the weighted graph with N nodes and edge weight Wi, = ( >1)) between node and node j. We similarly define the random sampled signal s(A) with value 8; s\,)) each node i. Note that (() and s(A) share the sample points A. We then define a random simple graph as follows. We treat each Wa,j = (A,, 23) as the parameter of a Bernoulli variable e. where P(ei. 1) Wi,j and P(et. = 0)
wa,j- We define the random simple graph G(W, as the simple graph with an edge between each node and node j if and only if ei,- = 1. The following theorem is 779 Theorem 3.6]
Theorem 3.6 from (79] (Sampling lemma for graphon-signals). Let 1. There exists constant
No > 0 that depends on т. such that for every N 2 No. every (W,s) E WL,, and for A (A1, (A1....AW E 1| independent uniform random samples [0, 1}. we have
E 6n ((0n((W.)) (G(W,A),
B(
15
(51)
v Vlo((N)
By Markov's inequality and the choice of A) in which
51 for any 0 < < 1, there is event of probability p (regarding
15
5 (G(,A))) [Vl
(52)
Stability deformations of mappings on geometric graphs. Let M be metric space with an atomless standard probability measure defined over the Borel sets (up to completion of the measure). Such a probability space equivalent to the standard probabiltiy space [0, 1] with Lebesgue measure. Namely, there are co-null sets A C .M and B c [0. 1], and measure preserving bijection á : A - B. Hence, graphon analysis applied as-is when replacing the domain [0. 1] with M. Suppose that we are interested in target function JM L (M) + L (M) that is stable to deformations in the following sense.
Definition 9. Let > A measurable bijection - + M called a deformation up e, if there exists an event B, C M with probability greater than 1 e such that for every x E B.
dm(((x), <e
The mapping fm: : (M) + (MM) called stable to deformations with stability constant C, if for any deformation v up to e, and every a L (MM), we have
[m((s) [M(SoN)ou 111 Ce.
Suppose that we observe discretized version of the domain M, defined as follows. There is a graphon W M2 [0, 1] defined as
v) r 8)).
(53)
where r -R. + [0, 1] is a decreasing function with support [0, p). Instead of observing W, we observe graph G = G(W, A) with node set sampled from W on the random independent points = { C M as above. Suppose moreover that any graph signal is sampled from a signal in L (M), on the same random points A, as above. Suppose that the target fM the continuous
26

---

domain is well approximated by some mapping f ['[N] + [N on the discrete domain in the following sense. For every E L'' (M), let sq be the graph signal sampled on the random samples {An Jn- Then there is an event of high probability such that
|| sC (E.M))))EE)))))))) <e
for some small e. We hence consider f as the target mapping of the learning problem. One example of such scenario is when there exists some Lipschitz continuous mapping θ W/ WL, with Lipschitz constant L, such that fM = O(W: -) and f @ .). Indeed, by (22) for some p as small like, there an event of probability
p in which, up a measure preserving bijection,
llfms f fa - ón 5n (ws)s (G.
s Tud T (W, (G,
15L
<
(54)
PVlog(N)
concrete example when @ is message passing neural network (MPNN) with Lipschitz continu- ous message and update functions, and normalized sum aggregation 779 Theorem 4.1].
Let G" be graph that coarsens G up to enror In the same event as above, by (52). up measure preserving bijection,
W W) do We) (W W) Sete=u.
(55)
We next show an approximation property that we state here informally: Since W(x, y) ~ 0 for x away from y. must have Wo (x, y) ss 0 well for of high measure. Otherwise, (W W) cannot be small. By this, any approximate symmetry of G is a small deformation, and, hence, f is an approximately equivariant mapping.
Equivariant mappings on geometric graphs. In the following, we construct a scenario in which f" can be shown to be approximately equivariant in restricted sense. For simplicity. assume (*G) E [0, 1]. and restrict to the case r = 1l [o in the geometric graphon W of (53). Denote the induced graphon Wo T. Given h 0, define the h-diagonal
d = {x,,)) E M² dd(x,y) S h}.
In the following, all distances are assumed to be up to the best measure preserving bijection.
If there is domain S' x T" M outside the p-diagonal in which T(x. v) > c for some >> 0, by reverse triangle inequality, we must have
/ TT
I -T
T(x, v)dydr cp((S))((T))
Hence, since by 55 W - - < for every S' x T" that does not intersect dp, we must have
{ T(x, dyde S u.
In other words, for any two sets S, with distance more than o (infees,eT ds(s,t) > p), we have
J (xx.))ddd= S u.
This formalizes the statement "Wor (z, 0 for away from y" from above.
Next, we develop the analysis for the special case = probability measure. We note that the analysis can be extended to M [0, 1j for general
= [0, 1] with the standard metric and Lebesgue
dimension D N. For every = E [0, 1]. we have
T(x, y)dddr S a,
10.---//2
and
T(x, y)dydr S
27

---

Let > 0. We take grid {2,} E [0, 1] of spacing V2v. The sets x [0, 2 p/v2],
cover d, (where dē is the complement of d,). Hence,
1/vBv
[| dg
Sestoraan So 10220-vv p/v2
( yddydr S
Σ jml
(xx, y dddd
1/v2u
Σ
Tzz, ydddd
2
1 V2v
We take 2 u = t, for u < t < namely, = v24. For example, we may take t = /2u and /2v 22/3, assuming that 1/3 Hence, we have
J| T(x,8) S 1/ 22/3
To conclude, the probability of having edge between nodes A and X in G" which are further away than u2/3, namely, (Ai, A1) 2//3, is less than 1/3
Suppose that G' asymmetric. This means that symmetries of 9G-G0 can only permute between nodes that have an edge between them in the blown-up graph G N- The probability of having an edge between nodes further away than 2//3 is less than 2/3 Hence, symmetry GG-GG can seen as small deformation, where for each node X; and a random uniform E GG-GG. the probability that A it is mapped by g to a node of distance less than 2//3 is more than - 2/3,
Any symmetry in Ga-Gr induces measure preserving bijection in M [0, 1]. by permuting the intervals of the partition Py of Definition | As result, the set of points that are mapped further away than 2/3 under has probability upper bounded by 123 and symmetries in GG-+G can be seen small deformation according to Definition 9 (in high probability). This means that, for any E GG-+Gr,
(s) fM(s g)
'11 < 1/3
so by the triangle inequality, combining with equation [4 we have
(sf* gf---( < 2e + C/2 =
(56)
Equation 56
leads to
(sc) Qs (f))s)
Σ
('so)ll
(57)
Ga-crl
(If"(s)) - - <E.
(58)
Ga-col
gEGa-
Since for any y E 12 1] ( 1] we have Ila12 < Iull, we can bound
(sa) Dsawc (fa)()) < (I(((sa) Dsawc (sa)l
(sa)ll + 1Q (sa)llaeee
(59)
where the last inequality follows from Q9a ( (so) (sc)
28

---

Denote || := (f du((s)) and suppose that II is finite. Hence, if is probabil- ity measure, we have
(f*) <
This shows example of approximately equivariant mapping based on random geometric graph, where the approximation rate is also a function of the size the graph N, and goes to zero as N oo and O.
In future work, we will extend this example to more general metric space M and to non-trivial symmetry groups Ag Intuitively, most random geometric graphs are "close asymmetric". This means that for "most" G", the symmetries of Ag can only permute between nodes connected by an edge, and so are the symmetries of Ga-cr. For this, we need to extend Definition by treating G' probabilistically.
D Experiment Details
In this section, we provide additional details of our experiments. We first give a brief introduction of standard graph neural networks (Section D.I). followed by in-depth explanations of our applications in image inpainting (Section D.2). traffic flow prediction (Section D.3). and human pose estimation (Section D.4p. All experiments were conducted on server with 256 GB RAM and NVIDIA RTX A5000 GPU cards.
D.1 Graph Neural Networks (GNNs)
We consider standard cesssae-passing graph neural networks (MPNNs) [9 21 defined follows. A L-layer MPNN maps input X E xxx to output Y R following iterative scheme: At initialization, ()) = Xx At each iteration 1, the embedding for node is updated to
(h (1-1) A.
h =
h
Σ v (n (EN(()
(60)
where 6, ub are the update and message functions, (i) denotes the neighbors of node i, and A A represents the (i, (eedge weight. MPNNs typically have two key design features: (I) Φ, & are shared across all nodes in the graph, typically chosen to be linear transformation multi-layer perceptions (MLPs), known as global weight sharing; (2) the graph used for (spatial) convolution.
D.2 Application: Image Inpainting
We provide additional details of the data, model, and optimization procedure used in the experiment.
Data. We consider the datasets MNIST 774 and FashionMNIIT (75). For each dataset, we take 100 training samples and 1000 test samples via stratified random sampling. The input and output graph signals are (m, O.r,, 2²) (@ entrywise multiplication). Here z; E IR 28
784 denotes the image signals and m, denotes a random mask (size 14 x 14 for MNIST and 20 x 20 for FashionMNIST), For experiments with reflection symmetry on the coarsened graph, we further transform each image in the FashionMNIST subset using horizontal flip with probability 0.5 (FashionMNIST--hiing We remark that is possible to model the dihedral group D4 on the square as the coarsened graph symmetry, we only consider the reflection symmetry S2 to simplify the parameterization (since it Abelien while D2 is not) while capturing the most relevant symmetries.
Model. We consider a 2-layer fic--c--euiiarraan networks G-Net, composition of four ReLU fin. where fin- four denote the input/output equivariant linear layers. The input and output feature dimension is 1 (since the signals are grayscale images). and the hidden dimension is set as 28. For comparison, we also consider a simple 1-layer Sc-cr-equivarian networks G-Net.
We train the models with ADAM (learning rate 0.01, no weight decay, at most 1000 epochs). We report the best test accuracy at the model checkpoint selected by the best validation accuracy (with 80/20 training-validation split).
We supplement Figure 2 with Table for further numerical details.
29

---

MSE (KIe
(Suu)* (Swva)
(Spu) (Suna)
(Sur)) (Suyu)
(Sp)) JMM (Swyne)) pis
(Suma))
MNIST
41.56 + D.16
40.03 0.226
36.06 + 0.24
34.08 + D.G
33.667 +: 0.07
31.92 + 0.04
Fashion
23.48 0.14
22 25 0.02
16.94 :: 0.08
15.16 U.1.
14.47 + 0.11
14.75 0.11
Table 7: Image inpainting using G-Net with different levels of coarsening. Table shows mean squared error (MSE) across runs on the test set, supplementing Figure (Left, blue curves).
D.3 Application: Traffic Flow Prediction
Data. The METR-LA traffic dataset, [76). contains traffic information collected from 207 sensors in the highway of Los Angeles County from Mar 1st 2012 to Jun 30th 2012 [87. We use the same traffic
data normalization and 70/10/20 train/validattinntess data split as 76 We consider two different traffic graphs constructed from the pairwise road network distance matrix: (1) the sensor graph G introduced in (76) based on applying thresholded Gaussian kernel (degree distribution in Figure Sep; (2) the sparser graph G, based on applying the binary mask where the (i. () entry is nonzero and only if nodes j lie the same highway (degree distribution in Figure (d). We construct the
second variant to more faithfully model the geometry of the highway, illustrated in Figure Sa
Graph coarsening, We choose 2 clusters based on highway intersection and flow direction, indicated
by colors (Figure 8b (b)), and 9 clusters based on highway labels (Figure 8c (c)).
0.00
0.10
400
(a) Our faithful traffic graph
(b) Graph clustering (2 clusters)
(c) Graph clustering (9 clusters)
Dopse Eslopam VETR tullc Gusph Sporaifed
Decyne Ietegoon METAA Totti Grugh
175
13.0
25.0
120
(d) Our faithful graph degree dis-
(e) Original sensor graph degree distribution
tribution
Figure 8: METR-LA traffic graph: visualization, clustering, and degree distribution
Model. We use a standard baseline, DCRNN proposed in 76 DCRNN built on a core recurrent module, DCGRU cell, which iterates as follows: Let Let, e, hi denote the i-th node feature and hidden state vector at time f; Let X1, RG, H;-1 be the matrices of stacking feature vectors Ti, Ti,t, fi, as rows.
Z4,t 0g (i,t - U2 U2ha,-1 bz)
(61)
Fia = o, I, + U, h, b,)
(62)
Jy. = dn (IAX W + [A, ④ H,_1) Un]T. + bn)
(63)
hi 24 h4-1 1 -1-20 2.) の hes
(64)
where W., U., b,, U,, W,, Wh, Un, by are learnable weights and biases, 0g is the sigmoid func- tion, dy is the hyperbolic tangent, and h2 = 0 for all at initialization. The crucial different from a vanilla GRU lies in eqn (63) where graph convolution replaces matrix multiplication.
We then modify the graph convolution in 63 from global weight sharing to tying weights among D.4pendixD..41000
clusters of nodes, similar to the implementation in Appendix D.4 for Relax-S16. For example, in the
30

---

case of two clusters (orbits), we change X to
swap (concat[Xx, Wh, X Wh.co)):
(65)
where Xx, denotes the submatrix of X including the rows of nodes from cluster i only, and Wh.cr Wh,c two learnable matrices. In words, we perform cluster-specifie linear transformation, combine the transformed features, and reorder the rows (i.e., swap) to ensure compatibility with the graph convolution.
Experiment Set-up. For our experiments, we use DCRNN model with 1 RNN layer and diffusion step. We choose T' = 3 (i.e., 3 historical graph signals) and T = 3 (i.e., predict the next 3 period graph signals). We train all variants for 30 epochs using ADAM optimizer with learning rate 0.01. We report the test set performance selected by the best validation set performance.
D.3.1
Assumption Validation: Approximate Equivariant Map
Before applying our construction of approximate symmetries, we validate the assumption of the target function f being an approximately equivariant mapping using trained DCRNN model as proxy. We proceed as follows:
Data. We use the validation set of METR-LA (traffic graph signals in LA), which has 207 nodes and consists of 14, 040 input and output signals. Each input X 22207x2 represents the traffic volume and speed in the past at the 207 stations, and output Y E 207 representing future traffic volume.
Model. We use trained DCRNN model X = 3, 1r- E x3x207 x2 to predict the future signals Y = XX4, XT+2) e 3 We denote this model f. It gives reasonable performance with Mean Absolute Error x 3, and serves as a good proxy for the target (unknown) function f"
faithful graph, with input being 3 historical signals
Neighbors. We take our faithful traffic graph that originally has 397 non-loop edges, and only consider a subset of 260 edges by thresholding the distance values eliminate geometrically far-away nodes. This defines our 260 neighboring node pairs.
Equivariance error. For each node pair (i,j), swap their input signals by interchanging the (i,j)-th slices in the node dimension of the tensor X, denoted as ((.)). and check if the swapped output ((.)) ((x()) is close to the original output Ý f(X) with (i,j)-th slices swapped.
We measure "closeness" via the relative equivariant error at the node pair. Concretely, let X [i, j] denote the tensor slices at the ji node pair, and X [j, i] being the swapped version by interchanging
(i,j)-th -thh slices. The relative different is computed
Yanlii /issi//Y
where / denotes element- deement-wise division. We then compute the mean relative equivariance error over all instances in the validation set, which equals to 5.%. This gives concrete justification to enforce approximate equivariance in the traffic flow prediction problems.
D.4
Application: Human Pose Estimation
D.4.1 Equivariant Layer for Human Skeleton Graph
We apply the constructions in Section A. to our human skeleton graph. We first show how to parameterize all linear Ac-equivariant functions. Observe that Ag 2 (S2)² {c, a, al), where the nontrivial actions correspond to the arm flip with respect to the spine, the leg flip with respect to the spine, and their composition. To fix ideas, we first treat both input and output graph signals as vectors, and construct Aq-eqivvriint linear maps f IR. - 16
Step 1: Obtain the character table for (S2)²
31

---

a
[
al
Xe
1
1
X2
-1
X3
-1
-1
X4
-1
-1
1
Table 2: Character table for (S²)²
Step 2: Construct the basis for isotypic decomposition. Here we choose to index the leg, joint pairs as
(1, 4), (2, 5), (3, 6), joint pairs as (10, 13), (11, 14), (12, and spline joints 0, 7, 8,8,9.
B = 2 e7: e7: Eg] E 16
where
B(Px.) ) [(ei
[P = [(ei - - co) R16x3
((Px) xa [e10 (2ao e1s\/ R
((Pxa) = 0
(66)
Step 3: Parameterize f: : 16 + 16 by f :(P()) B(xx) and f : B(xx)), i.e. for
all E 16 = B(xx. Ce B(P 22) C2 + ((xxa) Ca. then
f(v) W. + W2 W3 where W. 10 W2 E 3x33 W3 E R3x3 are (learnable) weight matrices. Now expresses all linear, equivariant maps w.r.t (S²)²
(67)
The following calculation based on f RR R shows how much degree of freedom (measured by learnable parameters) is gained by relaxing the symmetry from global (group S1G), exact Ag (Sa)² to trivial group (i.e.. no symmetry).
fs = w I + w1(1 Iιs, (2 parameters);
(68)
fA We + W2 @ Wa, (118 parameters on the isotypic components);
(69)
fuv. = W, (256 parameters).
(70)
To parameterize equivariant linear function f : 16xd + R 16xd' proceed by decoupling the input
space into IR 10xd g3xd 3xxd and the output space into m 3xxd 123xd" Now the learnable
weight matrices for multidimensional input/output become W. E R 10dxx 10d"
W2 3dxx3d Wa
R3dx3d' The construction is summarized in Algorithm
Algorithm 2 Equivariant layer SAo R 16xd >> TR 16xd for Ag = (S2)²
Require: The basis B R16xd
R 16x16 in (66 for isotypic decomposition of Ag (S2) input h!
Initialize: The learnable weights ((()) 110d' x 10d, w: w:O Radd"3d,
x3d, M/ E I8 16161
1. Project (()) to the isotypic component: z(() B 100;;
2. Perform block-wist wise linear transformation:
Ze W. flatten (2 (.:10])
(t)
W2 flatten( ((1)
(1)
23 W3 flatten( [1133]
(1+1) = concat ke; 22; 23] E R 16xdd
3. Project back to the standard basis: ((+1) 1) = ((111)
4. Perform pointwise nonlinearity: ((+1) (b((+))))
return (1+1)
32

---

blowssp
cieane syth.
Ag S2 x S2
Go :a (S2 S2) Aa
g S2 x S2 x Ag
Figure 9: Human skeleton graph G, its coarsened graph G" (clustering leg joints), and blow-up of G'
D.4.2 Experiment Details
Data. We use the standard benchmark dataset, Human3.6M [77]. with the same protocol as in 78 We train the models on 1.56M poses (from human subjects S1, S5, S6, S7, 58) and evaluate them on 0.54M poses (from human subjects 59, S11). We use the method described in (88) to normalize the inputs (2D joint poses) to [-1, and align the targets (3d joint poses) with the root joint.
Model. We give detailed description of G-Net and its variants used the experiments. Figure inset illustrates the architecture of G-Net.
For the human skeleton graph with N 16, have fg R 16xd + R 16xk where d, l represent the input dimension and output dimension (for each layer). Let foli.J ]] R + R denote its (i.j)-th -h slice.
(16.2)
Ineer Map
1. G-Net with strict equivariance using equivariant linear map fg (see Table 3
Sie: Ssio li, E 16x116 a diagonal matrix, with one learnable scalar a diagonal and another learnable scalar off diagonal.
ineer Map
Relax-Sia: We relax [i by having 16 different pairs of scalars (a,, be), i [16]. such that each node can map itself and communicate to its neighbors in different way (controlled by (a;, b))), while still treat all neighbors equally (by using the same b, for nodes i).
Nealinnariy
Aa S We use Algorithm 2
Trivial: We allow f[i.j] 16x16 to be arbitrary, i... it has 16 16 Icarnable scalars.
(16,3)
We remark that for S16 and Relax-S16, implement them by tying weights; for Ac. implement them by projecting to isotypic component as shown in Algorithm 2
G-Net augmented with graph convolution Afc(2), denoted as G-Net(ge) (see Table 3): apply
the equivariant linear map fg in 1. and obtain the output fa(x) 16 We then apply graph convolution by multiplication from the left, i.e., Afa(w) R 116xk
3. G-Net augmented with graph convolution and learnable edge weights, denoted as G-Net(getew) (see Table 4): We further learn the edge weights for the adjacency matrix A, by softmax [M @ A) where M E R represents the learnable edge weights, and M,, is nonzero when A 0 and 0 elsewhere. This is inspired from SemGCN [78.. Besides the groups discussed above, we also implemented Relax-(Sa)2 which corresponds tying weights among the coarsened graph orbits, consists of 4 spline nodes (singleton orbits) and orbits for the left/right arm and leg nodes.
4. g-Net augmented with graph locality constraints (A O (x) and learnable edge weights, denoted G-Net(pttew) (see Table 3): We perform pointwise multiplication A @ fg fi, j] at each (i, slice fz- In practice, we also allow learnable edge weights as done 3.
Experimental Set-up. We design G-Net to have layers (with batch normalization and residual connections between the hidden layers). 128 hidden units, and use ReLU nonlinearity. This allows G-Net(gctew) to recover SemGCN [78 when choosing G Sic- We train our models for most 30
33

---

epochs with early stopping. For comparison purpose, we use the same optimization routines as in SemGCN [78] and perform the prper-paraeeter search of learning rates {0.001, 0.002).
Evaluation. Table shows results of G-Net and its variants when varying the choice of G. We observe that using the automorphism group Ag does not give the best performance, while imposing symmetries (Trivial) or a relaxed version of S16 yields better results. Here, enforcing no symmetry achieves better performance since the human skeleton graph very small with 16 nodes only. As shown in other experiments with larger graphs (e.g. image inpainting), enforcing symmetries indeed yields better performance.
Table 3: 3D human pose prediction using G-Net and its variants. Error (# std) measured by Mean Per-Joint Position Error (MPJPE) and MPJPE after rigid alignment (P-MPJPE) across 3 runs. All methods use the same hidden dimension 128. Bold type indicates the top-2 performance among each variant. "NA" indicates the loss fails to converge.
MPJPE 4
S16
Relax-S16
Ag = (Sz)
Trivial
G-Net
NA
47.97
0.47
48.30 0.69
42.86 0.64
G-Netge)
NA
54.50 4.33
49.40 + 1.37
43.24 0.82
G-Net(prow)
41.54 0.47
40.44 0.61
40.63 0.26
38.41 0.31
P-MPJPE
S16
Relax-S1o
Ag (S,)²
Trivial
G-Net
NA
36.45 = 0.56
37.17 + 0.59
32.59 = 0.62
G-Net(ge)
NA
40.61 0.99
37.62 + 1.32
33.05 = 0.81
G-Net(pttew)
32.31 t 0.03
31.11 = 0.68
31.35 t 0.14
29.68 = 0.22
Additional Evaluation. Table shows the experiments when we keep the number of parameters roughly the same across different choices of G.
Table 4: 3D human pose prediction using G-Net(gc+ew), where the models induced from each choice of G are set to have roughly the same number of parameters. denotes the number of hidden units.
G-Net
Number of Parameters
Number of Epochs
MPJPE
P-MPJPE
SI6
0.27M (d 128)
50
43.48
34.96
Relax-S16
0.27M 32)
20
40.08
32.08
AG = (52)²
0,22M = 16)
30
14.10
34.12
Trivial
0.22M (d 10)
30
45.05
34.79
34


Reviews:
[{"review_id": "QUa2ojZiIv", "reviewer": "Reviewer_YT16", "summary": "The authors observe that – while graphs considered as a class have global permutation symmetry – for specific problems, e.g. when learning on a fixed graph, the graph has a much smaller symmetry. Consequently, they attempt to answer the question of how symmetric the model should be in comparison with global permutation symmetry or the graph’s natural symmetries. They quantify this model selection problem as a bias-variance tradeoff, which they validate with numerical experiments.\n", "questions": "This question might reflect my unfamiliarity with a subset of the literature, but to what extent is the bias-variance tradeoff that the authors propose a perspective that has been used for more general equivariant neural networks where the symmetry of the model is greater than the symmetry of the data? Am I correct in thinking that this perspective on the use of overly-symmetric models is novel for general equivariant-ML, not just for graph ML? If so, maybe this should be noted in the text, e.g. by noting in the discussion that these results should translate to other groups and analyzing this as a future direction.", "limitations": "Limitations and potential negative societal impacts are appropriately addressed.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "To my knowledge, this paper contains several new ideas. The concept of choosing a supergroup of an object’s natural symmetry group as a statistical strategy motivated by bias-variance trade-off is a novel one in equivariant ML as well as in graph-ML. Similarly, the concept of explicitly considering the natural symmetry of a fixed graph in devising the learning algorithm rather than assuming global permutation symmetry is novel as well. Finally, the concept of using graphon distances to define a notion af approximate equivariance on graphs is yet another novelty that addresses the issue of defining approximate equivariance on a space of objects that is fundamentally discrete.\n\nMethodologically, I found the mathematical approaches taken to be appropriate, and the experiments to be clean tests of the ideas presented. In particular, the authors demonstrate the existence of the proposed bias-variance trade-off in multiple settings.\n\nFinally, I found the author’s argument that the use of overly-equivariant models should be viewed as a statistical strategy that purposefully introduces some systematic error to gain regularity to be a good perspective on the current state of graph neural networks, where people have seen good practical success with permutation-equivariant GNNs on problems that have much lower natural symmetry.\n", "weaknesses": "The paper could do with being run through a spell-check: there are a few obvious typos, e.g. “neighrborhood” in line 289. Moreover, I did not feel like the choice of using graphons to construct a distance between graphs was properly motivated: additional discussion on why the authors chose to use graphons to compare graphs would help motivate the direction of the paper. Is it only to embed the graphs in a continuous space?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for carefully examining our work and appreciating the novelty and the impactfulness of our paper. We provide detailed responses to the Weakness and Questions section.\n\n### Responses to Weaknesses: \n1. (spell check): We thank the reviewer for pointing this out and will fix all the typos for the camera-ready version.\n\n2. (motivation of graphon): We thank the reviewer for the question. Graphons are generalizations of graphs in the sense that any graph induces a graphon (see Definition 1 of the main text, also Figure 1 for an illustration). Therefore we can use the cut distance (defined on graphons) as a graph metric. **The cut distance is a natural similarity measure for graphs of different sizes**, as we now explain. By the weak regularity lemma [1], the cut distance between a large graph and a small graph can be interpreted as follows. *Seeing the small graph as a stochastic block model (SBM), the distance is small if the large graph “looks like” it was randomly sampled from the SBM*. The meaning of “looks like” has a precise meaning via the regularity lemma. Namely, the number of edges between any two subsets of nodes of the large graph behave like the expected number of nodes between these sets, if the graph was sampled via the SBM. This is comuted exactly by the cut distance, which is the reason to consider cut distance when working with fine graphons and their coarse-grained versions. We will clarify this motivation in the camera-ready version of the paper and add the above reference.   \n\n### Responses to Questions: \n1. (Extension to general equivariant ML): We thank the reviewer for raising this important point. Indeed, **our bias-variance tradeoff results can extend to general equivariant machine learning models**. Our current formulation requires that the group is compact and acts on the input/output spaces via an orthogonal representation. We believe the orthogonality requirement can be lifted straightforwardly, but the compactness requirement seems much harder to lift (see discussion in [2]). We will include this in the discussion section and outline interesting future directions.\n\nReferences:\n1. Lovász, László, and Balázs Szegedy. \"Szemerédi’s lemma for the analyst.\" GAFA Geometric And Functional Analysis 17 (2007): 252-270.\n\n2. Villar, Soledad, et al. \"Dimensionless machine learning: Imposing exact units equivariance.\" arXiv preprint arXiv:2204.00887 (2022)."}, {"review_id": "iQ60KQB6Pz", "reviewer": "Reviewer_van5", "summary": "The authors discuss the generalization of learning a map that is equivariant to one group, while the ground truth is (approximately) equivariant to another group. Their theoretical analysis first considers the case where the ground truth is exactly equivariant and finds a bias-variance trade-off: making the hypothesis equivariant to a larger group increases bias, while reducing variance. When the hypothesis equivariance group is smaller than the ground-truth group, the bias is 0. Next, the authors define a graph coarsening criterion via graphon theory, that results in a coarse graph $G'$ and whose nodes are a clustering of the nodes of the fine graph $G$. This gives a new symmetry group on the fine graph $G$, called $\\mathcal G_{G \\to G'}$, which equals the automorphisms of the coarse graph times the permutations of nodes in the clusters. The ground truth graph function is then assumed to be $\\epsilon$ close to a function equivariant to $\\mathcal G_{G \\to G'}$. Theoretically, the authors find a trade-off in a lower bound the risk gap (the difference in test loss between a hypothesis and its symmetrization to the approximate symmetry group). In their experiments, on fixed graphs, the authors use neural networks that combine graph methods on $G$ with methods equivariant to permutations in clusters in the graph. They evaluate different cluster sizes and find an optimum between clusters between size 1 and all nodes clustered together.", "questions": "- Schur's lemma doesn't apply always naively on the real numbers (as they're not algebraically closed.) How do the authors apply the complex results to the real field, as mentioned in line 575 of the appendix? Do they ignore the possible additional intertwiners?\n- In section 3, it is not so clear which results rely on the group acting via a permutation of rows (so related to graphs), and which parts could generalize to other groups and representations. Could the authors comment on that?\n- In line 168, the authors say that the mismatch term goes below zero, presumably because an inner product goes above zero. However, it is unclear to me why the sign of the inner product is known in general.\n- In line 178, the authors make a comment on an inner product of characters increasing when the group increases. Can the authors clarify why this holds in general, or make the comment more specific?\n\nMinor points:\n- The authors appear to be confusingly using both the symbols $\\Psi$ and $\\mathcal Q$ for the symmetrization operation.\n- What are the two measures in (3)? Shouldn't these both be the Lebesgue measure? $\\mu$ is already used for a measure on $\\mathcal X$ .", "limitations": "The authors are not quite transparent about the mismatch between their theory and experiments.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Very interesting formalization of approximate graph symmetry via graph coarsening with graphons and the group $\\mathcal G_{G \\to G'}$ .\n- The authors develop novel theoretical results on generalization with approximate symmetries.\n- The ideas give an interesting theoretical insight in using clustering and permutation equivariant networks on graphs.\n- The paper mostly clearly written.", "weaknesses": "- The paper should explain better (in the main paper) why the risk gap is an important criterion for model selection. Lines 183-186 are hard to follow.\n- There appears to be a substantial mismatch between the theory and the experiments: the experiments rely substantially on combining equivariant nets to $\\mathcal G_{G \\to G'}$ with the ( $G$ -automorphism equivariant) graph nets on $G$ . The theory does not discuss this combination of symmetries. Also, the graph cut distance doesn't appear to be computed in practice.\n- The theoretical results talk about the symmetry group  $\\mathcal G_{G \\to G'}$ being a combination of cluster permutations and coarse graph $G'$ automorphisms. However, in their experiments the authors assume those automorphisms to be trivial, so that they only work with cluster permutations. This is a substantially less interesting class of groups, which should be more fairly stated in the paper.\n- The coarsening group $\\mathcal G_{G \\to G'}$ appears quite similar to the groupoid of nodes used in [1], which contains the automorphism group of node neighbourhood (akin to the cluster permutations in this paper) and maps between similar neighbourhoods (akin to the automorphism group of $G'$ ). The authors should consider comparing to this paper.\n- The neural network architecture $\\mathcal G$ -Nets used in the experiments should be more fully defined in the main paper.\n\n[1] P de Haan and TS Cohen. 2020. “Natural Graph Networks.”", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the critical assessment and constructive feedback of our work. We provide detailed responses to the each section point by point:\n\n### Responses to Weaknesses: \n1. (why risk gap) We will add more motivation in Section 3 for the risk gap. To summarize: The risk quantifies how a given model performs on average on any potential input. The smaller the risk, the better the model performs. The risk gap computes the difference of the risk between two models (satisfying different symmetries), and thus allows us to **perform model selection**. Lines 183-186 intend to explain the significance of the risk gap (i.e., choosing different symmetry affects generalization nontrivially in the small $n$ regime).\n\n2. (mismatch between theory and experiments) \n- We thank the reviewer for pointing this out, and we are providing **a new set of experiments which solely use our proposed $\\mathcal{G}$-Net without any further augmentation**. The details are thoroughly described in the common response, and we give a summary below. We consider a regular 2D grid as our fixed graph domain, and images as our graph signals. The goal is to reconstruct the original images given masked images. We perform the symmetry model selection via graph coarsening: We cluster the grid into $d \\times d$ patches, where $d$ ranges from $1$ (no clustering, corresponding to the trivial symmetry) to $N$ (one giant cluster, corresponding to the $\\mathcal{S}\\_N$ symmetry). Figure 6 in PDF shows the empirical risk first decreases and then increases as the group decreases, illustrating the bias-variance trade-off from our theory. \n- We also want to point out that the graph cut distance serves as a theoretical tool for our construction; in practice, we construct the coarse-grained versions of the graphs not by minimizing the cut-distance, but rather by using off-the-shelf clustering methods. In this sense, the theory motivates the implementation but does not justify it completely rigorously. We will clarify this in the camera-ready version.\n\n3. (experiment assumes trivial coarsened graph symmetry) \nWe thank the reviewer for raising this point. We added **new experiments with nontrivial $\\mathcal{A}\\_{G’}$ symmetries**. Concretely, we consider a global reflection symmetry for the coarsened grid graph of FashionMNIST. We compare the non-trivial coarsened graph symmetry with the trivial case in the inpainting problem (c.f. Figure 6 - right in the PDF). Our results show the utility of using the coarsened graph symmetry, which leads to better performance. \n\n4. (comparison to NGN) \nWe thank the reviewer for these remarks and will include a more detailed comparison to Haan and Cohen’s paper for the camera-ready version. Concretely: \n- Our set-up focuses on learning on a fixed graph and thus graph automorphism, whereas their set-up considers different graphs and thus graph isomorphism. \n- Our goal is to choose the best symmetry for generalization, whereas their goal is to design maximally expressive graph networks.\n\n5. (experimental details) We now provide a new set of experiments with detailed information on the architectures and set-up in the common response and the attached PDF. We will also re-organize the main paper to include additional important information from the previous experiments.\n\n### Responses to Questions: \n1. (Construction of equivariant maps on the reals) We thank the reviewer for raising this question. We didn’t explain the general construction in the appendix of the paper because we didn't need it in the experimental setting. We will add the general construction in the appendix of the revised version for completeness, and outline the key ideas here. By Maschke’s theorem we can decompose the representation in irreducibles over $\\mathbb R$. Then we can check further how to decompose these irreducibles over $\\mathbb C$, and apply Schur's lemma. We have 3 cases for the decomposition:\n- The irreducible over $\\mathbb R$ is also irreducible over $\\mathbb C$: We can directly apply Schur’s lemma.\n- The irreducible over $\\mathbb R$ decomposes in two different irreducibles over $\\mathbb C$: We can send each $\\mathbb C$-irreducible to their isomorphic counterpart.\n- The irreducibles over $\\mathbb R$ decompose in two copies of the same irreducible over $\\mathbb C$: We can send each irreducible to any isomorphic copy independently.\n\n2. (Generalization to other groups/representations) Yes, our results are built on the results from Elsedy et al. (2021), which **can be used for general compact groups with orthogonal representations**. We believe it may be possible to extend the results to other representations of compact groups. Extending the results to non-compact groups seems much harder. We will comment on this in the camera-ready version.\n\n3. (Sign of the inner product) We thank the reviewer for raising this point and agree that the original remark in line 168 is incorrect. Indeed, the inner product $\\langle f^*, f_G^{\\perp} \\rangle$ can be negative. We fixed the discussion in line 167-168 to \"...when $\\cal{G} > \\cal{A}_G$, the mismatch term can be positive, negative or zero (depending on $f^*$) whereas the constraint term increases with $\\cal{G}$ \". \n\n4. (Inner product of characters) We thank the reviewer for catching this confusing comment. The correct version of the remark holds in general and it reads as follows:\nThe inner product of characters measures the dimension of the linear equivariant space (this is a standard result, but we will add the proof in the appendix for completeness). Thus it decreases as the group increases. Consequently in the risk gap formula that measures the generalization gain, the variance term increases, whereas the bias term decreases (since the projection to the orthogonal complement of $\\mathcal{G}$-equivariant space increases, and negates by the minus sign).\n\n5. Minor points: We apologize for the confusing notations and will fix them in the final version."}, {"review_id": "IppvTCBT22", "reviewer": "Reviewer_RNWs", "summary": "This paper formalizes the notion of active symmetries and approximate symmetries of GNNs on a fixed graph domain. Furthermore, it theoretically characterizes the statistical risk of linear regression with symmetries and show a bias-variance tradeoff. For graph tasks, it utilize \ncoarsed graph for approximate symmetries. Experimental results on human pose estimation and traffic flow prediction valid the proposed method.", "questions": "1. As shown in the Weaknesses section, please add a more concrete description of your method in the maintext. \n2. Please provide experimental results on more general graph tasks, like link prediction.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "1. Novel theoretical results and methods. To my best knowledge, its the first risk gap with a combination of symmetries and graphon. The approximating symmetry by coarsened graph is also fancy.", "weaknesses": "1. The result in Section 3.1 seems trivial and useless.\n2. The experiment section is hard to read as all implementations are put in Appendix. \n3. Graph coarsening is vital for the proposed method. But coarsening method for general graph task in unknown.\n4. The experiments is conducted on small and specific tasks only rather than general graph task, like link prediction [1].\n\n[1] https://ogb.stanford.edu/docs/linkprop/", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments and appreciation of our theoretical contribution. We provide detailed responses to the each section point by point:\n\n### Responses to Weaknesses: \n1. (Result in Section 3.1 seems trivial and useless) We want to remark that considering simplistic models to analyze complex phenomena is very common in machine learning research, and in science in general. **Insights from simplistic models often transfer to the real-life phenomenon. We hence do not see Section 3.1 as useless**. The set-up in Section 3.1 is indeed simple, using a linear regression model with white noise. Yet we hope to make a first step to analyze the symmetry model selection using a very simple setting, such that the results are clear to state and prove, and verifiable through simulation. Although linear regression setting is simple and may seem trivial compared to deep neural networks used in practice, **analysis in linear regression allows us to (1) precisely characterize the bias-variance tradeoff; (2) illustrate the phenomenon we observe in practice for non-linear models**. Moreover, we now added a new set of experiments (see attached PDF), where Figure 6 (left) shows that **the bias-variance tradeoff can be observed both in simple linear models and nonlinear models**. \n\n2. (Experimental details) We thank the reviewer for the suggestions, and we have supplemented **a new set of experiments which solely use our proposed $\\mathcal{G}$-Net without any further augmentation**. The details are thoroughly described in the common response, and we give a brief summary below. We consider a regular 2D grid as our fixed graph domain, and images as our graph signals. The goal is to reconstruct the original images given masked images by learning a mapping $f: \\mathbb R^N \\to \\mathbb R^N$, also known as image inpainting. We make use of standard image datasets (MNIST, FashionMNIST) and perform the symmetry model selection via graph coarsening: We cluster the grid into $d \\times d$ patches, where $d$ ranges from $1$ (no clustering, corresponding to the trivial symmetry) to $N$ (one giant cluster, corresponding to the $\\mathcal{S}\\_N$ symmetry). Figure 6 in PDF shows the empirical risk first decreases and then increases as the group decreases, illustrating the bias-variance trade-off from our theory. \n\n3. (Graph coarsening method) \n- We agree with the reviewer that there is no ground-truth optimal coarsening for general tasks. Indeed we do not propose a computational method to derive a ground-truth optimal coarsening for general graphs and general tasks. **We envision our approach being used for model selection. Namely, one should implement different coarsening procedures and find the one that works best for the problem**. Our symmetry model selection perspective suggests that a natural coarsening recipe is to sweep from a few large coarsened nodes to many small coarsened nodes. We will clarify this motivation in the camera-ready version.\n- That said, graph clustering is a form of graph coarsening that is very widely studied in the literature and used in practice. For instance, if the graphs are instances of social networks, clustering is a natural approach. Under certain random graph model assumptions, spectral clustering, message-passing algorithms and semidefinite programs enjoy theoretical guarantees, see for example\n  - Lyzinski, Vince, et al. \"Perfect clustering for stochastic blockmodel graphs via adjacency spectral embedding.\" (2014): 2905-2922.\n  - Qin, Tai, and Karl Rohe. \"Regularized spectral clustering under the degree-corrected stochastic block model.\" Advances in neural information processing systems 26 (2013).\n  - Abbe, Emmanuel. \"Community detection and stochastic block models: recent developments.\" The Journal of Machine Learning Research 18.1 (2017): 6446-6531\n- To summarize, in practice we construct the coarse-grained versions of the graphs not by minimizing the cut-distance, but rather by using off-the-shelf clustering methods. Hence, the theory heuristically motivates the implementation. \n\n4. (More experiments including link prediction) Our experiments are intended to illustrate the learning task on a fixed graph setting. Concretely, we are given a dataset of input/output graph signals supported on a **fixed** graph domain, and aim to learn the best function to map the input signal to output signal. On the other hand, **link prediction** usually aims to predict unobserved edges given a partially observed graph, which **does not fit into our setting in a direct way**. However, we did extend our experiments to more tasks, like image inpainting as explained thoroughly in our common response. \n\n### Responses to Questions: \n1. Please refer to the previous Section, Responses 2 (Experimental details)\n2. Please refer to the previous Section, Responses 4 (More experiments including link prediction)\n"}, {"review_id": "J7TwQ3L8oe", "reviewer": "Reviewer_KAcz", "summary": "This work discusses a non-trivial case of equivariant graph networks. In this scenario, the input graph $G$ remains fixed, and therefore, the relevant permutations that act on the graph signals are the automorphisms of $G$. Under this assumption, the authors describe a bias-variance tradeoff with respect to the symmetry group to which the hypothesis class is restricted. Since the automorphism group tends to be trivial in large graphs, the authors introduce the concept of approximated symmetry by considering a symmetry group associated with a coarser version of the graph. The main result of the paper formalizes the bias-variance tradeoff in relation to the approximated symmetries.", "questions": "* Definition 1 - What does the J in summation stand for? should it be N?\n\n*  The implementation of this method on an arbitrary graph, which lacks any inductive bias concerning the graph's structure, remains unclear. Are the authors able to offer any insights or intuition regarding a general approach or recipe for graph coarsening in such cases?", "limitations": "There is no potential negative impact to this work", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "* The paper introduces a novel perspective and analysis of equivariant graph networks, both in terms of the fixed graph scenario and the approximated equivariance via graph coarsening.  \n\n* The use of Graphons to define a metric over graph spaces is interesting and could have many applications.\n\n* The theoretical claims are very clear and explained in a detailed manner.", "weaknesses": "* An explanation regarding the clustering methods is missing in the main text. The method section in the paper does not suggest how to coarsen a graph G, therefore it would be helpful to explain how it is done, specifically in the traffic flow experiment.\n\n* Although the appendix provides some explanation, additional information about the architectures employed in the experimental section would be beneficial for a more comprehensive understanding of the empirical results.\n\n* The empirical results presented in Table 2 do not provide strong evidence supporting the necessity of approximated equivariance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive feedback and appreciation of our work. We provide detailed responses to the each section point by point:\n\n### Responses to Weaknesses: \n1. (Graph coarsening details) We thank the reviewer for raising this point and will add more discussion of graph coarsening methods in the camera-ready version. The clustering choice of the traffic flow experiments are included in the supplementary information (Figure 5) due to the page limit. We also give a detailed explanation of the graph clustering choices in our new set of experiments. We note that theoretically, we assume that the coarse-grained graph approximates the fine graph in cut distance. However, in practice **we construct the coarse-grained versions of the graphs not by minimizing the cut-distance, but rather by using off-the-shelf clustering methods**. In this sense, the theory does not justify the implementation completely rigorously, but rather heuristically motivates it. We will clarify this point in the camera-ready version.\n\n2. (Experimental details) We now provide a new set of experiments with detailed information of the architectures and set-up in the common response and in the attached PDF. We will also re-organize the main paper to include additional important information of the previous experiments.\n\n3. (Experiments in Table 2 do not strongly support the theory) \n- To further support our theory, we now provide **a new set of experiments (see attached PDF) that clearly illustrates the benefits of approximate equivariance** (induced from graph coarsening). The details are thoroughly described in the common response, and we give a brief summary below. \n- We consider a regular 2D grid as our fixed graph domain, and images as our graph signals. The goal is to reconstruct the original images given masked images by learning a mapping $f: \\mathbb R^N \\to \\mathbb R^N$, also known as image inpainting. We make use of standard image datasets (MNIST, FashionMNIST) and perform the symmetry model selection via graph coarsening: We cluster the grid into $d \\times d$ patches, where $d$ ranges from $1$ (no clustering, corresponding to the trivial symmetry) to $N$ (one giant cluster, corresponding to the $\\mathcal{S}\\_N$ symmetry). Figure 6 in PDF shows the empirical risk first decreases and then increases as the group decreases, illustrating the bias-variance trade-off from our theory. \n- Note that the 2D grid as a graph has global reflection symmetries (from vertical and horizontal axis), but nodes from a local $d \\times d$ patch are not symmetrical in the original grid. Yet enforcing approximate symmetries among nodes in local patches suitably can outperform trivial symmetries, see for example Figure 6 where using $2 \\times 2$ patches with the coarsened symmetry ${\\cal S}_{4}^{196}$ yields better test error than the trivial symmetry case.\n- We agree that for the traffic flow prediction task, empirical results in Table 2 don’t seem to show strong advantage of approximate equivariant. We want to remark that the traffic flow prediction concerns both the spatial graph domain and the temporal dimension, which is likely to downplay the gain in the spatial domain. We nevertheless include the experiment in the paper since it illustrates the potential to enhance standard GNNs architectures with approximately equivariant modules. \n- In light of the reviewer’s feedback, we plan to replace our original experiments with the new experiments in the main text to clearly illustrate our theory, and defer most of the original experiments to the Appendix.\n\n### Responses to Questions: \n1. (Notation) We thank the reviewer for catching this typo and indeed the summand should be N. We will correct this typo in the camera-ready version.\n2. (Graph coarsening method)\n- Indeed we do not propose a computational method to derive a ground-truth optimal coarsening for general graphs and general tasks. **We envision our approach being used for model selection. Namely, one should implement different coarsening procedures and find the one that works best for the problem**. Our symmetry model selection perspective suggests that a natural coarsening recipe is to sweep from a few large coarsened nodes to many small coarsened nodes. We will clarify this motivation in the camera-ready version.\n- That said, graph clustering is a form of graph coarsening that is very widely studied in the literature and used in practice. For instance, if the graphs are instances of social networks, clustering is a natural approach. Under certain random graph model assumptions, spectral clustering, message-passing algorithms and semidefinite programs enjoy theoretical guarantees, see for example\n  - Lyzinski, Vince, et al. \"Perfect clustering for stochastic blockmodel graphs via adjacency spectral embedding.\" (2014): 2905-2922.\n  - Qin, Tai, and Karl Rohe. \"Regularized spectral clustering under the degree-corrected stochastic block model.\" Advances in neural information processing systems 26 (2013).\n  - Abbe, Emmanuel. \"Community detection and stochastic block models: recent developments.\" The Journal of Machine Learning Research 18.1 (2017): 6446-6531\n- To summarize, in practice we construct the coarse-grained versions of the graphs not by minimizing the cut-distance, but rather by using off-the-shelf clustering methods. Hence, the theory heuristically motivates the implementation. \n"}]

Author rebuttal:
## Common Response

We thank the reviewers for their detailed assessment of our work, and their appreciation for the novelty and the impactfulness of our paper. We are encouraged that all reviewers found that our theoretical results are novel and interesting, particularly on the symmetry bias-variance tradeoff perspective (YT16) and the formulation of approximate symmetries via graphon analysis (van5, RNWs, KAcz), and that our graphon analysis techniques “could have many applications” (KAcz). We are grateful for all the comments and constructive feedback, which will undoubtedly contribute to increasing the overall quality of the paper.

Along with detailed responses to each reviewer, we synthesize below the common questions and responses to all reviewers:
1. Experiments details (van5, RNWs, KAcz); mismatch between theory and practice (van5): 

 - **We provided a new set of experiments that more accurately match our theory and illustrate our bias-variance tradeoff perspective**, together with a thorough explanation of the architecture and set-up; see explanations below and PDF attached. 

2. Graph coarsening methods and guarantees (RNWs, KAcz): 
- We added a more detailed discussion on existing graph coarsening methods based on clustering with proven guarantees (i.e., small cut-distance to the generative graphon)
- We want to highlight that **our symmetry selection perspective** (using symmetry induced from the coarsened graph) **allows us to compare different coarsening procedures, and choose the one that works the best for the target application** (which balances optimally the bias from coarsening error and the variance from constraining the hypothesis class). 

3. Extension to general groups (YT16, van5):
- We explained the **applicability of our analysis to general compact groups with orthogonal representation**, and remarked on the possibility of lifting some of the requirements (van5).
- We added a discussion on the implications of our work to general equivariant ML beyond graph ML with pointers to related work (YT16).

### New Experiments

To illustrate our theory, we consider a $28 \times 28$ grid graph as the fixed domain, and grey-scale images as the graph signals. The learning task is to reconstruct the original images given masked} images as inputs (a.k.a *image inpainting*). We investigate the symmetry model selection problem by clustering the grid into $d \times d$ patches, where $d \in \\{28, 14, 7, 4, 2, 1 \\}$. Here $d = 28$ means one cluster (with full permutation symmetry); $d = 1$ is $784$ singleton clusters with no symmetry (trivial). 

**Data.** We consider the datasets MNIST and FashionMNIST. For each dataset, we take $100$ training samples and $1000$ test samples via stratified random sampling. The input and output graph signals are $(m_i \odot x_i, x_i)$ ($\odot$ is entrywise multiplication). Here $x_i \in \mathbb R^{28 \times 28} \equiv  \mathbb R^{784}$ denotes the image signals and $m_i$ denotes a random mask (size $14 \times 14$ for MNIST and ${20 \times 20}$ for FashionMNIST). For experiments with *reflection symmetry on the coarsened graph*, we further transform each image in the FashionMNIST subset using horizontal flip with probability $0.5$ (FashionMNIST+hflip).

**Model.**  We consider $2$-layer $\mathcal{G}$-equivariant networks, a composition of $f_{\text{out}} \circ \texttt{ReLU} \circ f_{\text{in}}$, where $f_{\text{in}}, f_{\text{out}}$ denote the input/output linear equivariant layers. We use a hidden size $28$ for all models. $f_{\text{in}}, f_{\text{out}}$ are parameterized as eqn. (1) below. Concretely, any linear equivariant function $f: \mathbb R^N \to \mathbb R^N$ with respect to the symmetry group induced by the coarsening $\mathcal{G} = \mathcal{S}\_{c\_1} \\ldots \mathcal{S}\_{c\_M}  \times \mathcal{A}\_{G'}$ (c.f. Defn 3) admits the following block-matrix form (assuming the nodes are ordered by their cluster assignment) with $f_{kl}$ block matrices, and $a_k, b_k, c_{kl}$ scalars:

$$
 f = \\begin{bmatrix}
        f_{11} &  \\cdots & f_{1M} \\\\
        &   \\ddots &  & \\\\
        f_{M1} &  \\cdots & f_{MM}
       \\end{bmatrix},  \\, f_{kk} = a_k \\mathbf{I} + b_k \\mathbf{1} \\mathbf{1}^{\top}, \\, f_{kl} = c_{kl} \\mathbf{1} \\mathbf{1}^{\top} \\text{ for } k \\neq l.  \\quad (1)
$$

The coarsened graph symmetry $ \mathcal{A}\_{G'}$ induces constraints on $a_k, b_k, c_{kl}$. If $ \mathcal{A}\_{G'}$ is trivial, then these scalars are unconstrained. In the experiment, we consider a reflection symmetry on the coarsened grid graph, i.e., $ \mathcal{A}\_{G'}= \mathcal{S}\_2$ which acts by reflecting the left (coarsened) patches to the right (coarsened) patches. Suppose the reflected patch pairs are ordered consecutively, then $a_k = a_{k+1}, b_k = b_{k+1}$ for $k \in \\{1, 3, \ldots, M-1 \\}$, and $c_{kl} = c_{k+1, l-1}$ for $k \in \\{1, 3, \ldots, M-1 \\}, l \in \\{2, 4, \ldots, M \\}$ (see Figure 8 in PDF for an illustration). 

In practice, we extend the formulation to $f: \mathbb R^{N \times d} \to \mathbb R^{N \times k}$. 
We train the models with ADAM (learning rate $0.01$, no weight decay, at most $1000$ epochs). We report the best test accuracy at the model checkpoint selected by the best validation accuracy (with a $80/20$ training-validation split). 

Figure 6 in PDF shows the **empirical risk first decreases and then increases as the group decreases, illustrating the bias-variance trade-off from our theory**. We perform further ablation studies on the effect of the $\mathcal{G}$-Net architecture and the coarsened graph symmetry $\mathcal{A}\_{G'}$. Figure 6 (left) compares $2$-layer and $1$-layer linear $\mathcal{G}$-Net, **demonstrating that the tradeoff occurs in both linear and nonlinear models**. Figure 6 (right) shows that **using reflection symmetry of the coarsened graph outperforms the trivial symmetry baseline**, highlighting the utility of modeling coarsened graph symmetries. 

Meta-review: This paper introduces several novelties in equivariant fixed graph learning: (i) using hypothesis with equivariance group that is super/sub-group of the target equivariance group to adjust a tradeoff between bias and variance; (ii) Using graphon theory to define an approximate symmetry group using coarsening. (iii) Providing risk bounds for approximate equivariant linear regression. (iv) Experiments aiming to validate the theoretical findings.

Some points that would be good to address (to some extent at-least) in the final version: Better illustration of the connection of the theory and experiments; adding missing detail; and provide validation to the practical necessity of certain parts of the theory (i.e., approximate equivariance).
Decision: Accept (poster)