Expressive Sign Equivariant Networks for Spectral Geometric Learning
Authors: Derek Lim
Joshua Robinson
Stefanie Jegelka
Haggai Maron
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Eigenvectors
spectral
geometry
universal approximation
graph
equivariance
invariance
TL;DR: We prove that a novel type of equivariance to eigenvector symmetries is useful in several applications, and develop provably expressive networks with this equivariance.

Abstract: Recent work has shown the utility of developing machine learning models that respect the structure and symmetries of eigenvectors. These works promote sign invariance, since for any eigenvector v the negation -v is also an eigenvector. However, we show that sign invariance is theoretically limited for tasks such as building orthogonally equivariant models and learning node positional encodings for link prediction in graphs. In this work, we demonstrate the benefits of sign equivariance for these tasks. To obtain these benefits, we develop novel sign equivariant neural network architectures. Our models are based on a new analytic characterization of sign equivariant polynomials and thus inherit provable expressiveness properties. Controlled synthetic experiments show that our networks can achieve the theoretically predicted benefits of sign equivariant models.

Expressive Sign Equivariant Networks for Spectral Geometric Learning
Derek Lim MIT CSAIL derekl im@mit edu
Joshua Robinson" Stanford University
Stefanie Jegelka TU Munich, MIT CSAIL
Haggai Maron Technion, NVIDIA
Abstract
Recent work has shown the utility of developing machine learning models that respect the structure and symmetries of eigenvectors. These works promote sign invariance, since for any eigenvector u the negation - is also an eigenvector. However, show that sign invariance is theoretically limited for tasks such building orthogonally equivariant models and learning node positional encodings for link prediction in graphs. In this work, we demonstrate the benefits of sign equivariance for these tasks. To obtain these benefits, we develop novel sign equivariant neural network architectures. Our models are based on new analytic characterization of sign equivariant polynomials and thus inherit provable expres- siveness properties. Controlled synthetic experiments show that our networks achieve the theoretically predicted benefits of sign equivariant models.
Introduction
The need to process eigenvectors is ubiquitous in machine learning and the computational sciences. For instance, there is often a need to process eigenvectors of operators associated with manifolds or graphs [Belkin and Niyogi, 2003, Rustamov et al., 2007], principal components (PCA) of arbitrary datasets [Pearson, 1901], and eigenvectors arising from implicit or explicit matrix factorization methods [Levy and Goldberg. 2014, Qiu al., 2018]. However, eigenvectors not merely unstructured data-they have rich structure in the form of symmetries [Ovsjanikov et al., 2008).
Specifically, eigenvectors have sign and basis symmetries. An eigenvector is sign symmetric the sense that the sign-flipped vector is also eigenvector of the same cigenvalue. Basis symmetries occur when there is a repeated eigenvalue, as then there are infinitely many choices of eigenvector basis for the same eigenspace. Prior work has developed neural networks that invariant these symmetries, improving empirical performance in several settings [Lim et al., 2023].
Sign
Pi 22
f(s, 25)
11
The goal of this paper is to demonstrate why sign equivari- ance can be useful and to characterize fundamental expressive sign equivariant architectures. Our first contribution is to show that sign equivariant models are a natural choice for several applications, whereas sign invariant architectures insufficient for these applications. First, we show that sign and basis invariant networks tions (and more generally multi-node node representations) in graphs because they learn structural node embeddings that are known to be limited for link prediction and multi-node tasks [Srinivasan and
Figure Illustration of sign equivariant function f. When col- umn of input is negated, col- umn I of the output is also negated.
provably
theoretically limited in expressive power for learning edge representa-
Work completed whilst MIT.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Ribeiro, 2019, Zhang et al., 2021]. In contrast, we show that sign equivariant models can bypass this limitation by maintaining positional information in node embeddings. Furthermore, we show that sign equivariance combined with PCA can be used to parameterize expressive orthogonally equivariant point cloud models, thus giving an efficient alternative to PCA-based frame averaging [Puny et al., 2022, Atzmon et al., 2022]. In contrast, sign invariant models can only parameterize orthogonally invariant models in this framework, which excludes many important application areas.
The second contribution of this work is to develop the first sign equivariant neural network archi- tectures, with provable expressiveness guarantees. We first present a difficulty in developing sign equivariant models: the "Geometric Deep Learning Blueprint" [Bronstein et al., 2021] suggests developing an equivariant neural network by interleaving equivariant linear maps and equivariant elementwise nonlinearities [Cohen and Welling, 2016, Ravanbakhsh et al.. 2017, Finzi et al., 2021], I, but we show that our attempts to apply this approach are insufficient for expressive sign equivari- ant models. Namely, we show that sign equivariant linear maps between various input and output representations are very limited in their expressive power.
Hence, to develop our models, we derive a complete characterization of the sign equivariant polyno- mial functions. The form of these equivariant polynomials directly inspires our equivariant neural network architectures. Further, our architectures inherit the theoretical expressive power guarantees of the equivariant polynomials. Our characterization is also broadly useful for analysis and development of sign-symmetry respectinng architectures for instance, we provide a new proof of the universality of SignNet [Lim et al., 2023] by showing that it can approximate all sign invariant polynomials.
To validate our theoretical results, we conduct various numerical experiments on synthetic datasets. Experiments in link prediction, n-body problems, and node clustering in graphs support our theory and demonstrate the utility of sign equivariant models.
1.1 Background
Let f Ra*k + -a be a function that takes eigenvectors U1,.... Vi....,, Uk E I2 of an underlying matrix as input, and outputs representations f(U1,..., Ux). We often concatenate the eigenvectors into a matrix V = ['i,..., ux] E = and write f(V) as the application of f. For simplicity, in this work we assume the eigenvectors come from symmetric matrix, so they are taken to be orthonormal.
Sign and basis symmetries. Eigenvectors have symmetries, because there are many possible choices of eigenvectors of matrix. For instance, if is a unit-norm eigenvector of matrix, then so is the sign-flipped -v If the eigenvalue of v is simple, then -v is the only other choice of unit-norm eigenvector of this eigenvalue.
If v1.... Um are an orthonormal basis of eigenvectors for the same eigenspace (meaning they all have the same eigenvalue), then there are infinitely many other choices of orthonormal basis for this eigenspace; these other choices of basis can be written VQ, where = [e] ... um]] E B and Q E +00mm (m) is an arbitrary orthogonal matrix.
We refer to these symmetries collectively as sign and basis symmetries. or more simply as eigenvector symmetries. Note that sign symmetries are a special case of basis symmetries, as -1 and 1 are the only orthogonal 1 matrices. Previous work has developed neural networks that are invariant to these symmetries-thee is, networks that have the same output for any choice of sign or basis of the eigenvector inputs [Lim et al., 2023].
Sign equivariance means that if we flip the sign of an eigenvector, then the corresponding column of the output of function f has its sign flipped. In other words, for all choices of signs s 8k {-1,
[(ivi,,.... sh u.) = [v) ux). )
(1)
where A.g is the j-th column of an n x l matrix A. See Figure for an illustration. matrix form, letting diag([-1, 1))) represent all le x i diagonal matrices with -1 or on the diagonal, f is sign equivariant if
F(VS) f(V)s for all S ddigg{ (dag((-1,1)**)
(2)
As =(1)= of orthogonal groups O(1) x. x O11) This is different from the equivariance to a single orthogonal group Odd) considered in works Euclidcan-gre group equivariant networks [Thomas et al.. 2018).
= (-1,1) we can write sign equivariance equivariance with respect to a direct product

---

U22
important example of node (a) Eigenvector 1
(b) Sign Invariant
(c) Sign Equivariant
Figure 2: (a) First nontrivial normalized Laplacian eigenvector of graph, which is positional. Nodes M1 and U2 are far apart in the graph, but automorphic. (b) Sign invariant node features, which are structural. Nodes Uj and u2 have the same feature. (c) Sign equivariant node features, which are positional. Nodes
and have opposite signs. A link prediction model with sign invariant node features assigns リ and u2 the same probability of connecting to w, while sign equivariant node features could give higher probability to u1.
Permutation equivariance is often also a desirable property of our functions f. We say that f is permutation equivariant f(PV) PFVV) for all permutation matrices P. For instance, cigenvectors of matrices associated with simple graphs of size have such permutation symmetries, as the ordering of nodes is arbitrary.
Applications of Sign Equivariance
In this section, we present several applications for which modeling networks with sign equivariant architectures is beneficial. We identify that sign invariant networks are provably insufficient for these tasks, motivating the development of sign equivariant networks address these limitations.
2.1 Multi-Node Representations and Link Prediction
In several settings, desire machine learning model that computes representations for tuples of several nodes graph. For instance, link prediction tasks generate probabilities for pairs nodes, and both hyperedge prediction and subgraph prediction tasks learn representations for collections of nodes in a graph [Alsentzer et al., 2020, Wang et al., 2023]. For ease of exposition, the rest this section discusses link prediction, though the discussion applies general multi-node tasks well.
In link prediction, we typically want to learn structural node-pair representations, meaning adjacency- permutation equivariant functions that give representation for each pair of nodes; more precisely, structural node-pair representation is map f: " + _ such that f(PAP = P where f(A)..) is the representation of the pair of nodes (i,j) in the graph with adjacency matrix A [Srinivasan and Ribeiro, 2019] (see Appendix A.5 for more discussion). One method to do this is to graph model such standard GNN learn node representations 2, and then obtain node- pair representation for (i. j) as some function fdecode (2, 2,, of 2, and 2j. However, this approach is limited because standard GNNs learn structural node encodings that is, cecfaeennc--permttan equivariant node features Sunde x -> TR. such that Snode (PAPT = Punode (A)) [Srinivasan and Ribeiro, 2019, Zhang al., 2021]. Structural node encodings give automorphic nodes the same representation, which can be problematic since automorphic nodes can be far apart in the graph. For instance, Figure 2, 21 and U2 are automorphic, so a link predictor based on structural node encodings would give both 1 and the same probability of connecting to w, but one would expect i1 have higher probability of connecting w. Most state-of-the-art link prediction methods on the Open Graph Benchmark leaderboards [Hu et al., 2020] were deliberately developed to avoid the issues of structural node encodings.
One way to surpass the limitations of structural node encodings is to use positional node embeddings, which assign different values automorphic nodes. Intuitively, positional encodings capture information such as distances between nodes and global position of nodes in the graph (see [Srinivasan and Ribeiro, 2019] for formal definition). Laplacian eigenvectors
2This adjacency permutation equivariance is different from permutation equivariance of general vectors as detined in Section 1.1.

---

positional embeddings that capture much useful information of graphs [Chung, 1997, Von Luxburg, 2007]. In Figure 2 (a), the first nontrivial Laplacian eigenvector captures cluster structure in the graph, and as such assigns i1 and u2 very different values.
Pitfalls of sign and basis invariance. When processing eigenvectors of matrices associated with graphs, invariance to the symmetries of the eigenvectors has been found useful [Dwivedi et al., 2022a, Lim et al., 2023], especially for graph classification tasks. However, we show that exact invariance to these symmetries removes positional information, and thus the outputs of sign invariant or basis invariant networks are in fact structural node encodings (see Appendix A.5). Hence, eigenvector- symmetry invarrint networks cannot learn node representations that distinguish automorphic nodes, and thus face the aforementioned difficulties when used for link prediction or multi-node tasks:
Raa - T.ddd be a permutation equivariant function, and let V [ui....,,uk] 2x] [2n be k orthonormal eigenvectors of an adjacency matrix A. Let nodes i and j be automorphic, and let and 2j E Bedw be their embeddings, i.e, the ith and jth row of Z = f(V).
Proposition 1. Let f
If f is sign invariant and the eigenvalues associated with the is are simple and distinct, then 24 = =2-
If f is basis invariant and Uly...,UU Up are basis for some number of eigenspaces of A then 2; Zz.
A novel link prediction approach via sign equivariance. The problem 2; = 23 arises from the sign/basis invariances, which remove crucial positional information. We instead propose using sign equivariant networks (as in Section 3) to learn node representations 2; = f(V),, E R These representations 2; maintain positional information for each node thanks to preserving sign information (see Figure 2 (c)). Then we use a sign invariant decoder fdecode (zi, 22) = fdecode (S2,, S2y) for S diag(f (1,, to obtain node-pair representations. For instance, the commonly used faecode = MLP(22 C 2,), where @ is the elementwise product, is sign invariant. When the cigenvalues distinct, this approach has the desired invariances (yielding structural node-pair representations) and also maintains positional information in the node embeddings; see Appendíx A.5 for proof of the invariances, and Appendix 1 for an example of where sign equivariant models can be used to compute strictly more expressive node-pair representations than sign invariant models. More details and the proof of Proposition are in Appendix A.4.
Our sign equivariance based approach differs substantially from existing methods for learning structural pair representations without being bottlenecked by structural node representations, Many of these methods are based on labeling tricks [Zhang et al., 2021, Wang et al., 2023], whereby the representation for a node-pair is obtained by labeling the two nodes in the pair and then processing an enclosing subgraph. Without special modifications [Zhu et al., 2021, Chamberlain et al., 2023), this requires a separate expensive subgraph extraction and forward pass for each node-pair. In contrast, our method only requires one forward pass the original graph to compute all positional node embeddings, after which pair representations can be obtained with a cheap, parallelizable decoding.
2.2 Orthogonal Equivariance
For various applications in modelling physical systems, desire equivariance to rigid transfor- mations; thus, orthogonally equivariant models have been a fruitful research direction in recent years [Thomas et al., 2018, Weiler et al., 2018, Anderson et al., 2019, Deng et al., 2021]. We say that a function f = + Ra*k is orthogonally equivariant if f(XQ) (Q)Q for any Q E O(k), where Okk) is the set of orthogonal matrices in & Orthogonal equivariance imposes infinitely many constraints on the function f- Several works have approached this problem by reducing to finite set of constraints using so-called Principal Component Analysis (PCA) based frames [Puny al., 2022, Atzmon et al., 2022, Xiao et al., 2020].
PCA-frame methods take an input X E g compute orthonormal eigenvectors Rx E O(k) of the covariance matrix cXv(X) = (X 1 x1ixx)T(3 cigenvalues), then average outputs of a base model h for each of the 2 sign-flipped inputs X where S E 11) We instead suggest using a sign equivariant network to parameterize an efficient O(k) equivariant model, which allows us to bypass the need to average the exponentially
1 1111X X) (assumed to have distinct
When there repeated eigenvalues, sign invariant embeddings maintain some positional information.

---

R
h
RT
R
h
R
Figure 3: Using sign equivariant functions h to parameterize orth equivariant f(X) = 1(X Rx) R where Rx a choice of principal components for the point cloud. We first transform X via Rx into orientation that is unique up to sign flips, then process X RRx using the sign e equivariant model h, and finally reintegrate orientation information back into the output via Rxx
Table 1: Sign invariant or equivariant polynomials and corresponding neural network architectures for different input and output spaces. U E I or V E Ra are inputs to the polynomials or networks. Appendix C contains more details the polynomials.
Constraints
Polynomials
Networks
R+ R Rinv Ronk - R inv.
Edg.... da =o Wa Way.. ((Va Vigal (ee)
2dk
MLP((e))
(V)) = p((((r)) + o(-r))ii-i...
R + R² equiv.
@ Pinr (0)) w (WWWV) @ (V))
V MLP((M)
xnnk + Re" xk equiv.
W oi........ W, vul @ SignNet,
many sign-flipped inputs. For a sign equivariant network h, we define our model f to be
= (XXRx
(3)
See Figure 3 for an illustration. Intuitively, this first transforms X by Rx into a nearly canonical orientation that is unique up to sign flips; this can be seen as writing the points in the principal components basis, or aligning the principal components of X with the coordinate axes. Then we process X using the model h that respects the sign symmetries, and finally, we incorporate orientation information back into the output by post-multiplying by Rx. Our approach only requires one forward pass through h, whereas frame averaging requires 2 forward passes through base model. The following proposition shows that f is (kk) equivariant, and inherits universality properties of h.
Proposition 2. Consider a domain X C Baxk such that each X E X has distinct covariance eigenvalues, and let Rx be choice of orthonormal eigenvectors of cov for each X E X. If h : X C Rnxk + BR** is sign equivariant, and if f(X) = h(XRx) then f is well defined and orthogonally equivariant.
Moreover, if h is from a universal class of sign equivariant functions, then the I of the above form universally approximate O(k) equivariant functions on X.
We include a proof of this result in Appendix A.6. This result also follows from Theorems 3. and 3.3 of Kaba et al. [2023], who show that generally group G, and achieve G-equivariance via a K Keequivariant base predictor. In our case, = O(k) and K = 1)
ennonicalize up subgroup K of
Sign invariance only gives orthogonal invariance. In similar way, a sign invariant model can be used to obtain an orthogonally invariant model with PCA frames, but cannot used for orthogonal equivariance; instead, sign equivariance is needed.
5

---

3 Sign Equivariant Polynomials and Networks
In this section, we analytically characterize the sign equivariant polynomials, and use this characteri- zation to develop sign equivariant architectures. As equivariant polynomials universally approximate continuous equivariant functions [Yarotsky, 2022], our architectures inherit universality guarantees. We summarize our results on polynomials and neural network architectures in Table 1. Our character- ization of the invariant polynomials also allows us give an alternative proof of the universality of the sign invariant neural network SignNet [Lim et al., 2023] (see Appendix C.4).
3.1 Sign Equivariant Linear Maps
First, we consider the important case of degree one polynomials, i.e. sign equivariant linear maps from Rnxk + 1n' These maps are very limited in expressive power, as they act independently on each eigenvector.
Lemma 1. A linear map W Bunk + B.'''x is sign equivariant if and only if it can be written as W(X)= = [ ... WkX
for some linear maps WI...., We R - R",, where X3 E IR is the ith column of X E R
See Appendix B.1 for the proof. Notably, when n'' = 1. the linear maps are diagonal matrices.
This means a model with elementwise nonlinearities and sign equivariant linear maps will not capture any interactions between eigenvectors. For instance, when used for parameterizing orthogonally equivariant models as in Section 2.2, such a model would process each principal component direction of the point cloud independently. Hence, the popular approach -outlined in the "Geometric Deep Learning Blueprint" [Bronstein et al., 2021] interleaving equivariant linear maps and equivariant nonlinearities [Cohen and Welling, 2016, Zaheer et al., 2017, Kondor and Trivedi, 201 8, Maron et al., 2018, 2019, Finzi et al., 2021] is not as fruitful here.
However, one may choose instead different group representations for the input and output space, but our attempts do this do not lead to efficient models. For instance, a common method improve expressive power of models that use equivariant linear maps is to use tensor representations [Maron et al., 2018, 2019, Finzi al., 2021]; our case, this would correspond having equivariant hidden representations in Roxk" for some tensor order m. This is also inefficient, as we explain in Appendix ?? we show that such an approach would have to lift to tensors of at least order 3, and that there are many sign equivariant linear maps between tensors of order 3. There is possibility that some other group representations may allow the Geometric Deep Learning Blueprint to work better for sign equivariant networks, but could not find any such representations.
For these reasons, we will now analyze the entire space of sign equivariant polynomials.
3.2 Sign Equivariant Polynomials
Consider polynomials p R + g=''k that are sign equivariant, meaning P(VS) p(V)S for We can show that polynomial is sign equivariant if and only if it can be written as the elementwise product a simple (linear) sign equivariant polynomial and a general sign invariant polynomial, followed by another linear sign equivariant map.
S E
Theorem 1. A polynomial Baak + Rn xk is sign equivariant if and only if it can be written
p(V) (22) ((W(V) Pino
(5)
for sign equivariant linear 222) and (1)), and a sign invariant polynomial Pinv : :Bnxk + Inn' xk
This reduction of sign equivariant polynomials to sign invariant polynomials combined with simple operations is convenient, as it enables us to leverage recent universal models for sign invariant functions [Lim et al., 2023]. The proof of this statement is in Appendix C, which proceeds by showing that sign equivariance leads to linear constraints on the coefficients of a polynomial, which requires the polynomial to take the form stated in the Theorem.
A class of model functions F.. from X + y is universal with respect a target class Fi if for all compact D S X. fi E Fe, and 0, there is an fi Fm such that (m))))) f((x)) < é for all D.

---

Table 2: Link prediction AUC and runtime per epoch for structural edge models.
Erdös-Rényi
Barabási-Alber
Model
Test AUC
Runtime (s)
Test AUC
Runtime (s)
GCN (constant input)
.49.4.06
.088+.00
.7054.01
.048+t.00
SignNet
.48:+.00
.120+:.00
.707+_00
.095++.00
V1 V3,
.570:1.01
.010::01
.5974.01
.008+.000
ML,((V, @ V3.)
.614::02
.050+:00
.651+.03
.040:1.00
Sign Equivariant
.751::00
.063#000
.7732.01
.054:t.0
3.3 Sign Equivariance without Permutation Symmetries
Using Theorem 1, we can now develop sign equivariant architectures. We parameterize sign equivari- functions f R R= composition of layers fi, each of the form
fi(V) [w U1 wh us] O SignNet,(V),
(6)
in which the 10O _R + Rn are arbitrary linear maps, and SignNet, Bnnk + RR is sign invariant [Lim et al., 2023]. In the case of n' = 1, there is a simple universal form: we can write sign equivariant function ʃ I + R f(v) @ MLP((w)), where [w] is the elementwise absolute value. These two architectures are universal because they can approximate sign equivariant polynomials. Here, the sign invariant part captures interactions between eigenvectors that the equivariant linear maps cannot.
Proposition Functions of the form u >> u MLP(())) universally approximate continuous sign equivariant functions f Ik +2k.
Compositions f2 fi of functions fi as in equation 6 universally approximate continuous sign equivariant functions f. |
R R
3.4 Sign Equivariance and Permutation Equivariance
For models eigenvectors that stem from graphs point clouds, in addition to sign equivariance, we may demand permutation equivariance, i.e., f(PV) = PJ(V) for permutation matrices P E Ra*x", To add permutation equivariance to our neural network architecture from Section 3.3, we use it within the framework of DeepSets for Symmetric Elements (DSS) [Maron et al., 2020]. For hidden dimension size of dy. each layer fi Rexxxd n=xxdy of our DSS- OSS-based sign equivariant network takes the following form on row i:
fi();; = f( (Vi.) + (2)
Vo:).
(7)
1, where y(") and n(22) are sign equivariant functions as in Section 3.3. Sometimes we take d, = in which case we can use the simpler R - R& sign equivariant networks (o @ MLP((u)) as ((()) and f((²) If we have graph information, then j of to a sum over a neighborhood of node i. DSS has universal approximation guarantees [Maron al., 2020], but they only apply for groups that act as permutation matrices, whereas the sign group {-1, 1 does not. Hence, the universal approximation properties of our proposed DSS-based architecture still an open question.
do message-passing by changing the over
Experiments
Our theoretical results in Section 2 predict benefits of sign equivariance in various tasks: link prediction in nearly symmetric graphs, orthogonally equivariant simulations n-body problems, and node clustering with positional information. Next, probe these suggested benefits empirically.
4.1 Link Prediction in Nearly Symmetric Graphs.
We begin with synthetic link prediction task, which is carefully controlled to test the theoretically foreseen benefits of sign equivariance explained in Section 2.1. With the intuition of Figure we first

---

either generate an Erdós-Rényi [Erdós et al., 1960] or Barabási-Albert [Barabási and Albert, 1999] random graph H of 1000 nodes. Then we form a larger graph G that contains two disjoint copies of H, along with 1000 uniformly-randommy added edges (both between and within copies of H). Without the random edges, each node one copy of H is automorphic to the corresponding node in the other copy, so we expect many nodes to be nearly automorphic with the randomly added edges.
In Table we show the link prediction performance of several models that learn structural edge representations. The methods that use eigenvectors have sign invariant final prediction for each edge. GCN [Kipf and Welling, 2017] where the node features are all ones and SignNet [Lim et al., 2023] both completely fail on the Erdös- Erdós-Rényi task (these two models map automorphic nodes to the same embedding), while our sign equivariant model outperforms all methods. We also try two eigenvector baselines that maintain node positional information, but do not update eigenvector representations: taking the dot product V..VV. to be the logit of a link existing, or learning simple decoder ML,(V,, @ V.))) Both perform substantially worse than our sign equivariant model, which shows that updating eigenvector representations is important here. Further, the sign equivariant model takes comparable runtime to GCN, and is significantly faster than SignNet. This because we use networks of the form + @ ([P(( in these experiments instead of the full SignNet-based model equation 6. See Appendix E.2 for more details.
4.2 Orthogonal Equivariance in n-body Problems
Seconds ''poch
6-
Sign
Sign
Frame
Frame
10
4-
MSE
2-
10"
3
7
11
Dimension
Dimension
Figure 4: Sign equivariant model versus frame averaging model for n-body experiments in varying dimensions. Lower y-axis is better for both plots. (Left) The runtime of frame averaging increases exponentially in dimension while the sign equivariant runtime is approximately constant. Frame averaging runs out of memory on d = 11. (Right) The error of the sign equivariant model is very similar to that of frame averaging.
In this section, we empirically test the ability of our sign equivariant models to parameterize or- thogonally equivariant functions on point clouds, as outlined in Section 2.2. For this purpose, we consider simulating n-body problems, following the setup in Fuchs et al. [2020] and building on the code from Puny et al. [2022]. To test the favorable scaling of our method in the dimension d of the problem against the exponential 2d scaling of frame averaging, we generalize this problem to general dimensions d 3. We maintain the choice of n 5 particles, and generate new point clouds using the same procedure as in Fuchs et al. [2020] (sampling random points and initial velocities in a general dimension d). We measure model performance via mean squared error (MSE). We use model that we describe in more detail in Appendix E.3.
Figure 4 illustrates the runtime and MSE. The sign equivariant model scales well with dimension- the pime-per-epoch is nearly constant as we increase the dimension. In contrast, frame averaging suffers from the expected exponential slowdown with dimension, and runs out of memory on 32GB V100 GPU for d = 11. Considering the MSE, the equivariant model's performance closely follows that of frame averaging, i.e., only have a small loss in accuracy with much better scalability. For d = the sign equivariant model has an MSE of .00646, compared to the .00575 of frame averaging [Puny al., 2022]. Additional d = 3 comparisons to other baselines are included in Appendix E.3.
4.3 Node Clustering with Positional Information
As explained in Section 2.1, some applications on graph data call for positional node embeddings that can assign different representations to automorphic nodes. For instance, consider community detection node clustering tasks graphs, where a model makes prediction for each node that
8

---

assigns it to a cluster. Structural encodings are insufficient for this task, as there may be automorphic or eearly-automorphie nodes that are far apart in the graph but look alike in structural encoding. Hence, node structural encodings would guide the model to assign these nodes to the same cluster, even though they should belong to different clusters. As a concrete example, consider a graph of two clusters, and using Laplacian eigenvectors
positional encodings. The first nontrivial eigenvector will tend to assign a positive sign to one cluster and a negative sign to the other cluster. Thus, the sign information in the eigenvectors is crucial, so we expect sign equivariant models to perform well.
We test models on the CLUSTER dataset [Dwivedi et al., 2022a] for supervise node clustering (viewed as node classification) in synthetic graphs. In these experiments, we build on the empirically well-performing GraphGPS model [Rampasek al., 2022], and incorporate our sign equivariant models to update eigenvector representations within the ver- sion of GraphGPS that uses PEG [Wang et al., 2022] to process positional encodings. See Appendix E.4 for more experimental details.
Table 3: Results on the CLUSTER node classi- fication task, for which positional information is needed. We compare different SOTA and Laplacian eigenvector-based methods.
Model
Test Acc. (%)
GCN [Kipf and Welling. 2017|
68. 49. 49.-+0.970
GIN [Xu al., 2019]
64.716111 1.5
GAT [Veliškovid et al., 2018]
70.587
GatedGCN [Bresson and Laurent, 2017]
73. 73.84004...0 +0.528
SAN [Kreuzer al., 2021]
76, (666991, 850
K. S.Suhgraph SAT [Chen et al., 2022]
77.856 104
As seen in Table 3, our sign equivariant models outperform all of the other GraphGPS- -aased eigen- vector methods. Moreover, we achieve the second best performance across all methods, showing that sign equivariant models can indeed achieve the the- oretically expected benefits in this setting.
EGT [Hussain al., 2022]
79.2322+0.54
GPS [Rampusek et al., 2022]
78.016++0.160
Eigenvector Methods (GPS base model)
No
77. 77.423...22 241
LapPE [Dwivedi al., 2022a]
77.250 250
PEÙ [ [Wang et 20221
77.945++0
SignNet [Lim 2023]
77.442 102
Sign Equivariant (ours)
78.201+4..0
Related Work
Structural and Positional Representations. Es- pecially for link prediction, the need for structural node-pair representations that are not obtained from structural node representations has been dis- cussed in several works [Srinivasan and Ribeiro, 2019, Zhang et al., 2021, Cotta et al., 2023]. As such, various methods have been developed for learning structural node-pair representations that incorporate node positional information. SEAL and other labeling-trick based methods [Zhang and Chen, 2018, Zhang et al., 2021] use added node features depending on the node-pair that we want a representation of. This is empirically successful in many tasks, but typically requires separate subgraph extraction and forward pass through a GNN for each mode-pair under consideration. Distance encoding [Li et al., 2020] uses relative distances between nodes to capture positional information. PEG [Wang et al., 2022] similarly maintains positional information by using eigenvector distances between nodes in each layer of GNN, but does not update eigenvector representations. Identity-aware GNNs (You et al., 2021] and Neural Bellman-Ford Networks [7hu et al., 2021] learn pair representations by conditioning on source node from the pair.
Eigenvectors as Graph Positional Encodings. When using eigenvectors of graphs as node po- sitional encodings for graph models like GNNs and Graph Transformers, many works have noted the need address the sign ambiguity of the eigenvectors. This is often done by encouraging sign invariance through data augmentation- signs of the eigenvectors are chosen randomly in each iteration of training [Dwivedi et al., 2022a,b, Kreuzer et al., 2021, Mialon al., 2021, Kim et al., 2022, He et al., 2022, Müller et al., 2023]. In contrast, SignNet [Lim et al., 2023] enforces exact sign invariance, by processing eigenvectors with a sign invariant neural architecture; this approach has been taken by some recent works [Rampasek et al., 2022, Geisler et al., 2023, Murphy et al., 2023].
Equivariant Neural Network Design. Equivariant neural network architectures have been pro- posed for various types data and symmetry groups A common paradigm interleave equivariant linear maps and equivariant pointwise nonlinearities [Wood and Shawe-Taylon, 1996, Cohen and Welling, 2016, 2017, Ravanbakhsh et al., 2017, Maron et al., 2018, Kondor and Trivedi, 2018, Finzi et al., 2021, Bronstein et al., 2021, Pearce-Crump. 2022]; this is often used when the group acts as some subset of the permutation matrices. However, the sign group does not act as permutation matrices, and we explained above this approach is not expressive for sign equivariant models.

---

More similarly to our approach, many equivariant machine learning works heavily leverage invariant or equivariant polynomials (or other equivariant nonlinear functions). These works include polyno- mials as operations within network (TThomas et al., 2018, Puny et al., 2023], add polynomials as features [Yarotsky, 2022, Villar et al., 2021], build networks that take a similar form to equivarian polynomials [Villar et al., 2021], and/or analyze neural network expressive power by determining which equivariant polynomials a given architecture can compute [Zaheer et al., 2017, Segol and Lipman, 2019, Maron et al., 2019, 2020, Chen et al., 2020, Dym and Maron, 2021, Puny et al., 2023].
6 Conclusion
In this work, we identify and study an important method of respecting the symmetries of eigenvector data-sigh sigg equivariant models. For multi-node representation tasks, link prediction, and orthogonally equivariant tasks, sign equivariance provides natural inductive bias; in contrast, we show that sign invariant models are provably limited in these tasks. To develop sign equivariant neural networks, we analytically characterize the sign equívariant polynomials, and then define neural networks that parameterize functions of similar form. Our neural networks are thus expressive, and inherit universal approximation guarantees of the equivariant polynomials. In several experiments, show that our neural networks can indeed achieve the theoretically predicted benefits of sign equivariant models.
Limitations and Future Work. While developed sign equivariant architectures in this work, did not explore basis-change equivariant architectures, which would have the desired symmetries for inputs with repeated eigenvalues. As eigenvalue multiplicities are known occur in many real-world graphs [Lim et al., 2023], future work in this area could be useful. Further, we give evidence that sign equivariance could help in some node-level and multi-node-level prediction tasks on graphs but we do not have theoretical reason to believe that sign equivariance could help in graph-level representation tasks, which for instance are common in molecule processing. Our theoretical results are focused on expressive power, but we do not have results on other properties that are important for learning, such as optimization [Xu et al., 2021], stability [Wang al., 2022, Huang et al., 2023], or generalization [Keriven and Vaiter, 2023]. Finally, while we can prove universality of our models setting, we do not know of the exact expressive power in the
in the non-perm permuuationnequivaan permutation equivariant setting. Iim et al. [2023] also faces this issue for sign invariant models; future work on analyzing and possibly improving the expressive power of these models if they are not universal - is promising.
Acknowledgments
We would like to thank Yaron Lipman for contributing significantly early on in this work. We would like to thank Maks Ovsjanikov for noting that basis invariant models give automorphic nodes the same representation, and also Johannes Lutzeyer and Michael Murphy for helpful comments. We would also like to thank the reviewers of the Physics4ML workshop ICLR 2023 for helpful feedback and close reading- DL is supported by an NSF Graduate Fellowship. SJ acknowledges support from NSF AI Institute NSF CCF-21 12665, NSF Award 21 2134108, and Office of Naval Research Grant N00014-20-1-2023 (MURI ML-SCOPE).
References
Emmanuel Abbe, Community detection and stochastic block models: recent developments. The Journal of Machine Learning Research, 18(1):6446 66446-6331, 2017.
Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. In International Joint Conference on Artificial Intelligence, 2021.
Emily Alsentzer, Samuel Finlayson, Michelle Li, and Marinka Zitik.. Subgraph neural networks. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, pages 8017-8029, 2020.
Brandon Anderson, Truong Son Hy, and Risi Kondor. Cormorant: Covariant molecular neural networks. In Advances in Neural Information Processing Systems (NeurIPS), volume 32, 2019.
10

---

Matan Atzmon, Koki Nagano, Sanja Fidler, Sameh Khamis, and Yaron Lipman. Frame averaging for equivariant shape space learning. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 631-641, 2022.
Albert-LászIó Barabási and Réka Albert. Emergence of scaling in random networks. In Science, pages 509-512. American Association for the Advancement of Science, 1999.
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural compulation, 15(6):1373-139, 2003.
Xavier Bresson and Thomas Laurent. Residual gated graph ConvNets. In preprint arXiv: arXiv:1711.07553 2017.
Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learning: Grids, groups, graphs, geodesies, and gauges. preprint arXiv:2104. 13478, 2021.
Benjamin Paul Chamberlain, Sergey Shirobokov, Emanuele Rossi, Fabrizio Frasca, Thomas Markovich, Nils Hammerla, Michael M Bronstein, and Max Hansmire. Graph neural networks for link prediction with subgraph sketching. In International Conference on Learning Representations (ICLR), 2023.
Dexiong Chen, Leslie O'Bray, and Karsten Borgwardt. Structure-aware transformer for graph representation learning. In International Conference on Machine Learning (ICML), pages 3469- 3489. PMLR, 2022.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? In Advances in Neural Information Processing Systems (NeurIPS), volume 33, pages 10383-10395, 2020.
Fan Chung. Spectral graph theory. American Mathematical Society, 1997.
Taco Cohen and Max Welling. Group equivariant convolutional networks. In International Conference on Machine Learning (ICML), pages 2990-2999. PMLR, 2016.
Taco S. Cohen and Max Welling. Steerable CNNs. In International Conference on Learning Representations (ICLR), 2017.
Leonardo Cotta, Beatrice Bevilacqua, Nesreen Ahmed, and Bruno Ribeiro. Causal lifting and link prediction. preprint arXiv:2302.01198 2023.
Congyue Deng, Or Litany, Yueqi Duan, Adrien Poulenard, Andrea Tagliasacchi, and Leonidas Guibas. Vector neurons: A general framework for S0(3) networks. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 12009, 2021.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. JMLR, 2022a.
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. In International Conference on Learning Representations (ICLR), volume 10, 2022b.
Nadav Dym and Steven J Gortler. Low dimensional invariant embeddings for universal geometric learning. preprint 2rXiv:2205.02956 2022.
Nadav Dym and Haggai Maron. On the universality of rotation equivariant point cloud networks, In International Conference on Learning Representations (ICLR), 2021.
Paul Erdós, Alfréd Rényi, al. On the evolution of random graphs. Publ. Mathematical Institute Hungarian Academy of Science, 5(1):17-60, 1960.
Marc Finzi, Max Welling, and Andrew Gordon Wilson. A practical method for constructing equivari- ant multilayer perceptrons for arbitrary matrix groups In International Conference on Machine Learning (ICML), pages 3318-3328, PMLR, 2021.

---

Fabian Fuchs, Daniel Worrall, Volker Fischer, and Max Welling, translation equivariant attention networks. Advances in Neural Information Processing Systems (NeurIPS), volume 33, pages 1970-1981, 2020.
3D roto-
William Fulton and Joe Harris. Representation theory: a first course, volume 129, Springer Science & Business Media, 2013.
Simon Geisler, Yujia Li, Daniel Mankowitz, Ali Taylan Cemgil, Stephan Günnemann, and Cosmin Paduraru, Transformers meet directed graphs. preprint arXiv:2302.0000 2023.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning (ICML), pages 1263-1272. PMLR, 2017.
Aric Hagberg, Pieter Swart, and Daniel Chult. Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National Lab((LAN)), Los Alamos, NM (United States), 2008.
Xiaoxin He, Bryan Hooi, Thomas Laurent, Adam Perold, Yann LeCun, and Xavier Bresson. A generalization of ViT/MLP-Mixer to graphs. preprint arXiv:2212.133350 2022.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong. Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovee. Open graph benchmark: Datasets for machine learning on graphs. In Advances in Neural Information Processing Systems (NeurlPS), volume 33, pages 221 18 18-1213,, 2020.
Yinan Huang, William Lu, Joshua Robinson, Yu Yang, Muhan Zhang, Stefanie Jegelka, and Pan Li. On the stability of expressive positional encodings for graph neural networks. arXiv preprint 0rXiv:2310.02579 2023.
Md Shamim Hussain, Mohammed J Zaki, and Dharmashankar Subramanian. Global self-attention as a replacement for graph convolution. Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 655-665. 2022.
Sékou-Qumar Kaba, Arna Kumar Mondal, Yan Zhang, Yoshua Bengio, and Siamak Ravanbakhsh. Equivariance with learned canonicalization functions. International Conference on Machine Learning (ICML), pages 15546 15566. PMLR, 2023.
Nicolas Keriven and Samuel Vaiter. What functions can graph neural networks compute on random graphs? the role of positional encoding. arXiv preprint arXiv:2305. 14814, 2023.
Jinwoo Kim, Tien Dat Nguyen, Seonwoo Min, Sungjun Cho, Moontae Lee, Honglak Lee, and Se- unghoon Hong. Pure transformers are powerful graph learners. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015.
Thomas Kipf, Ethan Fetaya, Kuan-Chieh Wang, Max Welling, and Richard 7emel. Neural relational inference for interacting systems. In International Conference on Machine Learning (ICML), pages 2688-2697. PMLR, 2018.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), volume 5, 2017.
Jonas Köhler, Leon Klein, and Frank Noé. Equivariant flows: exact likelihood generative learning for symmetric densities. In International Conference on Machine Learning (ICML), pages 5361-5370. PMLR, 2020.
Risi Kondor and Shubhendu Trivedi. On the generalization of equivariance and convolution in neural networks to the action of compact groups. In International Conference on Machine Learning, pages 2747-2755. PMLR, 2018.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent I Létourneau, and Prudencio Tossou. Re- thinking graph transformers with spectral attention. In Advances in Neural Information Processing Systems (NeurIPS), volume 34, 2021.
12

---

Yann LeCun, Bernhard Boser, John Denker, Donnie Henderson, Richard Howard, Wayne Hubbard, and Lawrence Jackel. Handwritten digit recognition with back-propagation network. In Advances in Neural Information Processing Systems (NeurIPS), volume 2, 1989.
Shyi-Long Lee, Yeung-Long Luo, Bruce E Sagan, and Yeong-Nan Yeh. Figenvector and eigenvalues of some special graphs. IV. Multilevel circulants. International journal of quanium chemistry, 41 (1):105-116, 1992.
Omer Levy and Yoav Goldberg, Neural word embedding as implicit matrix factorization. In Advances in Neural Information Processing Systems (NeurIPS), volume 27, 2014.
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovee. Distance encoding: Design prov- ably more powerful neural networks for graph representation learning. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, pages
2020.
Derek Lim, Joshua David Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and basis invariant networks for spectral graph representation learning. In International Conference on Learning Representations (ICLR), 2023.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In International Conference on Learning Representations (ICLR), volume 6, 2018.
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. In International Conference on Machine Learning (ICML), pages 4363-4371. PMLR, 2019.
Haggai Maron, Or Litany, Gal Chechik, and Ethan Fetaya. On learning sets of symmetric elements. In International Conference on Machine Learning (ICML), pages 6734-6744, PMLR, 2020.
Grégoire Mialon, Dexiong Chen, Margot Selosse, and Julien Mairal. GraphiT: Encoding graph structure in transformers. In preprint arXiv:2106.0566) 2021.
Luis Müller, Mikhail Galkin, Christopher Morris, and Ladislav Rampášek. Attending to graph transformers. preprint arXiv:2302.0418/ 2023.
Michael Murphy, Stefanie Jegelka, Ernest Fraenkel, Tobias Kind, David Healey, and Thomas But- ler. Efficiently predicting high resolution mass spectra with graph neural networks. preprint 2rx1v:2301.11419, 2023.
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In International Conference Machine Learning (ICML), pages 4663 4673. PMLR, 2019.
Maks Ovsjanikov, Jian Sun, and Leonidas Guibas. Global intrinsic symmetries of shapes. In Computer graphics forum, volume 27, pages 1341-1348. Wiley Online Library, 2008
Edward Pearce-Crump. Brauer's group equivariant neural networks. preprint arXiv:2212.08630.
2022.
Karl Pearson. LIII. On lines and planes of closest fit to systems of points in space. The London, Edinburgh, and Dublin philosophical magazine and journal of science, 2(11):559-577 1901.
Daniel L Pimentel-Alaree Nigel Boston, and Robert D Nowak. A characterization of deterministic sampling patterns for low-rank matrix completion. IEEE Journal of Selected Topics in Signal Processing, 10(4):623 6366662666666-6 2016.
Omri Puny, Matan Atzmon, Heli Ben- Nen-Hamu, Edward Smith, Ishan Misra, Aditya Grover, and Yaron Lipman. Frame averaging for invariant and equivariant network design. In International Conference on Learning Representations (ICLR), volume 10, 2022.
Omri Puny, Derek Lim, Bobak T Kiani, Haggai Maron, and Yaron Lipman. Equivariant polynomials for graph neural networks. preprint 11555 2023.
13

---

Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. Network embedding as matrix factorization: Unifying Wal, LINE, PTE, and node2vec. In Proceedings of the eleventh ACM international conference on web search and data mining, pages 459 1599-467, 2018.
Ladislav Rampasek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for general, powerful, scalable graph transformer. In Advances in Neural Information Processing Systems (NeurIPS). 2022.
Siamak Ravanbakhsh, Jeff Schneider, and Barnabas Poczos. Equivariance through warameter-sharing In International Conference on Machine Learning (ICML), pages 2892-20822 29011. PMLR, 2017.
Raif M Rustamov et al. Laplace-Beltrant cigenfunctions for deformation invariant shape representa- tion. In Symposium on geometry processing, volume 257, pages 225-233, 2007.
Victor Garcia Satorras, Emiel Hoogeboom, and Max Welling. (n) equivariant graph neural networks. PMLR, 2021.
In International Conference on Machine Learning (ICML), pages
Nimrod Segol and Yaron Lipman. On universal equivariant set networks. In International Conference on Learning Representations (ICLR), volume 7, 2019.
Balasubramaniam Srinivasan and Bruno Ribeiro. On the equivalence between positional node embeddings and structural graph representations. In International Conference on Learning Repre- sentations (ICLR), 2019.
Nathaniel Thomas, Tess Smidt, Steven Kearnes, Lusann Yang, Li, Kai Kohlhoff, and Patrick Riley. Tensor field networks: Rotation-ant and translation-equivant neural networks for 3D point clouds. In NeurlPS Molecules and Materials Workshop, 2018.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations (ICLR), volume 6, 2018.
Soledad Villar, David Hogg. Kate Storey-Fisher, Weichi Yao, and Ben Blum-Smith. Scalars universal: Equivariant machine learning, structured like classical physics. In Advances in Neural Information Processing Systems (NeurIPS), volume 34, 2021.
Ulrike Von Luxburg. tutorial on spectral clustering. Statistics and computing, 17(4):395 2007.
Haorui Wang, Haoteng Yin, Muhan Zhang, and Pan Li. Equivariant and stable positional encoding for more powerful graph neural networks. In International Conference on Learning Representations (ICLR), volume 10, 2022.
Xiyuan Wang, Pan Li, and Muhan Zhang. Improving graph neural networks on multi-node tasks with labeling tricks. preprint 230.v:2304. 2023.
Maurice Weiler, Mario Geiger, Max Welling, Wouter Boomsma, and Taco Cohen. 3D steerable CNNs: Learning rotationally equivariant features in volumetric data. In Advances in Neural Information Processing Systems (NeurIPS), volume 31, 2018
Jeffrey Wood and John Shawe-Taylon Representation theory and invariant neural networks. Discrete applied mathematics, 69(1-2):33 60, 1996.
Zelin Xiao, Hongxin Lin, Renjie Li, Lishuai Geng, Hongyang Chao, and Shengyong Ding. Endow- ing deep 3D models with rotation invariance based on principal component analysis. In IEEE International Conference on Multimedia and Expo (ICME), pages 1-6. IEEE, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations (ICLR), volume 7, 2019.
Keyulu Xu, Mozhi Zhang, Stefanie Jegelka, and Kenji Kawaguchi. Optimization of graph neural networks: Implicit acceleration by skip connections and more depth. In International Conference on Machine Learning, pages 1 11592-11602. PMLR, 2021.
14

---

Dmitry Yarotsky. Universal approximations of invariant maps by neural networks. Constructive Approximation, 55(1):407-474, 2022.
Jiaxuan You, Jonathan M Gomes-Selman, Rex Ying, and Jure Leskovec. Identity-aware graph neural networks. In Association for the Advancement of Artificial Intelligence (AAAI), volume 35, pages 10737-10745, 2021.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander J Smola. Deep Sets. In Advances in Neural Information Processing Systems (NeurIPS), volume 30, pages 3391-3401, 2017.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Advances in Neural Information Processing Systems (NeurIPS), volume 31, 2018.
Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: theory of using graph neural networks for multi-node representation learning. In Advances in Neural Information Processing Systems (NeurIPS), volume 34, pages 9061-9073, 2021.
Zhaocheng Zhu, Zuobai Zhang, Louis-Pascal Xhonneux, and Jian Tang. Neural bellman-food ford networks: A general graph neural network framework for link prediction. In Advances in Neural Information Processing Systems (NeurIPS), volume 34, pages 19476-29490, 2021.
15

---

A Applications of Sign Equivariance
A.1 Improving Invariant Eigenvector Networks
Neural networks that are invariant to eigenvector symmetries have been shown to empirically improve graph learning models and achieve theoretically high expressive power. SignNet [Lim al., 2023], sign invariant neural network, takes the form
f(1,,..., ................................ 22) p(p((1) + +0- (((x) ((-vz))
(8)
for neural networks and Φ. This directly enforces invariant representations, without any intermediate equivariant representations. However, many successful invariant models first have many equivariant layers before final invariant operation as equivariant layers are more expressive: this includes convolutional neural networks [LeCun et al., 1989], message passing graph neural networks [Gilmer et al., 2017], invariant graph networks [Maron et al., 2018], and group convolutional neural net- works [Cohen and Welling, 2016]. Thus, sign equivariant layers may lead to better sign invariant networks. Moreover, sign equivariant layers may improve on other aspects of SignNet, such as expressiveness of node features (Proposition 1) and efficiency (Appendix A.2)
A.2 Efficiency Gains from Sign Equivariant Networks
Here, we show that our sign equivariant models can reduce the complexity of equivariant or invariant networks for two different types of applications. Throughout, we consider functions f Ra > Rn*k, and we consider our permutation equivariant and sign equivariant DSS-based architecture from Section 3.4.
The time cost (in floating point operations) per layer of our DSS-based model is O(n(kd + d²)). where d is the maximum hidden dimension of the MLP and we assume constant depth MLPs. To see this, note that we can precompute Σ}= Vj.,, so that each Ejzi Vj.: can be computed in constant time by subtracting V.. from the total sum. Then for each of the n rows, the MLPs require O(kd+d") evaluate matrix multiplications. In this process, we only form tensors of size O(n(k + d)), as the inputs and outputs are of size (nk), and the hidden layers of the MLPs form tensors of size (nd).
A.2.1 Efficient Orthogonally Equivariant Networks
Consider the case of O(k) equivariant models f: Bank - Baxk such that f(XQ) ((XQ for all orthogonal matrices Q & Ok)). There are many orthogonally equivariant neural architectures that are specialized to the special case of k: = 3. which is very useful for applications in the physical sciences [Thomas et al., 2018, Fuchs et al., 2020]. Here we consider models that directly work for general dimension k.
Frame averaging approaches [Puny et al., 2022, Atzmon et al., 2022) require 2 forward passes of a base network for one for each sign flip of the principal components. Letting their base network be permutation equivariant DeepSets [Zaheer et al., 2017], this means that they require (n + +d? )2))2* time to evaluate their model, where d is the hidden dimension of the base model. Note that this has an extra exponential 2 factor compared to our O(n(kd + d²)) cost.
Another general approach with universality guarantees comes from Villar et al. [2021], who analyze invariant polynomials to develop equivariant architectures. However, their method for O(k) invariance or equivariance requires forming XXT, an n x n matrix. Thus, the complexity which is problem in applications, since oftentimes n is much larger than k. Variants of their method do not need compute all O(n)) inner products, but it is unclear how to maintain permutation equivariance when doing this.
least O(n?).
A.2.2 Efficient Sign Invariant Networks
Consider again the form of SignNet [Lim et al., 2023], permutation equivariant version, e.g. when & is DeepSets [Zaheer et al., 2017] or a message passing neural network [Gilmer al., 2017], maps from IR + Raxd where is the hidden dimension. Thus, computing ((v)) + o( vx) for all & vectors v; require ((kk)) sized tensor to be formed (even if the output space of d is RR,, vectorized implementation computes all ((v)) + ((-v:) in two batched inference calls to o. which would require ((nkd) sized intermediate tensors). This is
+ +(==)))==.....) In the
16

---

multiplicative factor larger than the sign equivariant requirement of O(n(k + d)) sized tensors. Moreover, it would take (nkdd)) time to compute (((;))((-v; for each i, which is multiplicative factor larger than the (n(kk + d²)) time for the sign equivariant architecture.
A.3 Potential Societal Impacts
We do not foresee direct societal impacts from our work. This project is primarily theoretical and aims to improve models for two general application areas: multi-node representation learning and orthogonal equívariant models. Potential societal impacts may arise in downstream applications that may be affected by general progress in geometric machine learning, such as social network analysis and recommender systems. These two applications are known to have negative socictal impacts in certain circumstances, so care must be taken in future related work to avoid major negative consequences.
A.4 Edge Representations and Link Prediction
A.4.1 Sign Invariant Link Prediction Decoders
Here, we present an ansatz for universal permutation invariant and sign invariant functions for n = 2, that is f R2*k + Rdot, Note that SignNet is only known to be universal for such functions for n 1, where there are no permutation symmetries [Lim et al., 2023].
We will parameterize such functions
- vx) = yp (#1 @ 01,01 @ rev(w)),.... vh @ Uky up O rev(u)))
Here, rev IR2 + R22 reverses the vector, so rev(a)1 22x2k - BRd is a permutation invariant neural network, so (PX) =(X) for all 2 x 2 permutation matrices P. Note that it easy to parameterize permutation invariant functions y in maximally expressive way, e.g. via DeepSets [Zaheer et al., 2017]. Now, we show that this parameterization is universal:
and rev(a)2 = 01 Moreover,
Proposition 4. Functions f B2 + Bdduu of the above form are permulation invariant and sign invariant, and they universally approximate permutation invariant and sign invariant functions.
Proof. Invariance of is easy to see; let be 2 2 permutation matrix and s; E (-1, for each Then
[(PV1SI,.... PURSs)
+p ((Po181) o (Pv1s1), (Prrsi) O rev(Pu1s1))...)
(10)
= p (P(risi O U1s1), P(eis) @ rev((1s1)))...) pp (P(e) @ v1), P(u1 O rev(ei))....) = Pp (n) 0 O rev(v))....) f(e......v))
(11)
(12)
(13)
(14)
where the second to last inequality is by permutation invariance yp Next, we show universal approximation.
Let h R2xk - Rdome be continuous permutation invariant and sign invariant function. Then by the decomposition theorem in Lim et al. [2023], we can write
h(v1...., vk) = p(o(v1u "..... )...., (((k
(15)
for continuous functions p and As composition of continuous functions, the function 1 B C 22 - Rew given by ((A1,....,
= p(o(A)),.... ((A)) is continuous, where B is the subset of 2222 consisting of (wle rg ) such that each v; E R.2, Note that s is permutation invariant on B, in the sense that for any 2 x permutation matrix P, we have
(PA,PP PT.PT) = ((A
As).
(16)
because u...T = A,, then b(PAP ..... PAAPT)= (iPT)=>(PPr)))) h(Po Pvx) = h(v v1) (A)... Ap),
(17)
by permutation invariance of h.
17

---

Now, we define our permutation invariant function C C 2222 7 R on the domain
C [[1 01 01 @ vev( Uk Uk @ rev(ux)] us R²}.
(18)
We define yp by
((A)= = ([A:2
A2.2
A1.3
A2,4
21
22,2k A2,22
1):
(19)
A2.1
A2,4
A2,3
A2,2
0 1
To that so is permutation invariant, we need only consider the case where P case
in which
1
0
A2,1
A1
A2,3
A1,1
A2,2k-1
11
((PA) =
(20)
A1,2
A1.1
A1,4
A1,3
A1.2k
A1,2k-
A111
A2
A1,3
A2,1
[
A2,2k
P
PT, P
PT .....
P
pT
(21)
12,2
A2,1
12,4
A2,3
12,22
A2,28-1
[A111
A2,2
[1133
A2,4
11,2k11
A2,20-1 1)
A2,2k
(s) perm. inv.) (22)
A2,2
A2.1
[22,4
A2,3
A2,2k
(A),
(23)
where in the second equality, we use the fact that A2,2j A1,2j. j I,...,, for A E C, because A2.2j = (2, @ rev(u,))2 (vy @ rev(e,)) A1,2 for some bj R². Morcover, yp is clearly
continuous and sign invariant. Defining f B2xx Rdomt using this
compute that
f(11.... vk) = x (w) @ U1, U1 @ rev((e))
Uk O Uk, th O rev(vx))
(24)
Ui,1
11,1
Pk.1UK. Uk
= +
(25)
01,101,2
vī.2
= v (1ln) ..... 222k)
(26)
=
(27)
so we are done.
op instead comes from a universally approximating class permutation invariant neural networks (rather than being an arbitrary continuous permutation invariant function), then on a compact domain we can get approximation of f to h by letting &p approximate v to accuracy.
A.4.2 Proof of Proposition 1
Proposition 1. Let f Raxk > R be permutation equivariant function, and let V [ui,..., uk] 1 be orthonormal eigenvectors of an adjacency matrix A. Let nodes and j be
automorphic, and let 2, and 2j E Rddw be their embeddings, iee, the ith and jth row of Z f(V).
If is sign invariant and the eigenvalues associated with the on are simple and distinct, then 2: zj--
I f is basis invariant and VI...., Uy are a basis for some number of eigenspaces of then 2; = Zj-
Proof. We only prove the basis invariance claim, the sign invariance claim is special case; basis invariance sign invariance when cigenvalues are distinct.
Let P E RR be a permutation matrix associated to an automorphism that maps node i to node j. so PAPT = and Pe; = ej. where e the Ith standard basis vector. Let V, = [Mr,.... Ura, be the matrix whose columns are the eigenvectors U,, that are associated to eigenvalue A;- The columns of V, are thus an orthonormal basis for the eigenspace associated to A, Note that for any of these eigenvectors, we have
A(Pe,) = PAP PAP (Pv,.) = PAu,, = Pλye, = (Pur)))
(28)
Pvr, is also an eigenvector of A with eigenvalue d As P is orthogonal, note that Per...... Pura, still an orthonormal basis of the eigenspace. Thus, there exists an orthogonal matrix Q E RRd xd. such that PV, ViQu-see see Lim et al. [2023].
18

---

Repeat the above argument to get such a Qi for each of the eigenbases Vi.... Vi. We can then see that
2j J(V.. Vi),,:
f(ViQ) viQ1)s;
basis invariance
=S(PV PVi);:
choice of Q+
-PP((V,....... Vi))s
permutation equivariance
f(V....... vi)s:
choice of P
21.
So we are done.
A.5
Sign Invariance and Structural Node or Node-Pair Encodings
In this section, show that when the eigenvalues A1....; Ag are distinct, then sign invariant functions of the orthonormal eigenvectors ,i,.... Up give structural node or node-pair representations. This can also be generalized in straightforward way larger tuples of nodes beyond pairs. though only consider nodes and node-pairs for ease of exposition. First, we give formal definitions.
Definition 1 (Structural Representations [Srinivasan and Ribeiro, 2019]). Let A Raxa be the adjucency matrix of graph node set nI.....m..
A function f :. + 12" a node structural representation if f(PAPT) = (A) for all x permutation matrices P.
A function f RR Raxa node-pair structural representation ((PATT) PF(A)PT for all n x n permutation matrices P.
Importantly, these structural representations are permutation equivariant functions of adjacency matrices, not arbitrary matrices. For each adjacency matrix A, let ((4) [ej (A)....: ...)...... Us (A)] be choice of orthonormal eigenvectors for the first eigenvalues x (A), Ax We assume this section that these first & eigenvalues are distinct for all A under consideration,
V(A) is defined up
to sign flips. Let h : Rn*k + R" be a permutation equivariant function of sets, so h(PX) ) = Ph(X) for all permutations matrices P. Then of course h hPPV(A) (A)) Ph(V(AA) (A)), but this does not make node structural encoding. This is because A ~ ((V( is in general not a well-defined function of the adjacency, since the choice of ((A) not well-defined (the choices of sign are arbitrary). If we constrain h to not depend on the signs (sign invariance), to depend on the signs in a predictable way (sign equivariance), then we can compute structural node or node-pair encodings from eigenvectors.
We capture these observations in the below proposition. First, we define three types of functions:
Let fnode : Baxk R be sign invariant and permutation equivariant; that is, (Poie( PULSK) matrix.
ux) for 8; E (-1,1) and P a permutation
Let fdecode 2 - R be sign invariant; that is, faecode (Szz, S2y) Adecodo Zz) for S E diag(1 1)
Let fequiv -R n be permutation equivariant and sign equivariant function; that is, fequiv (PV())S) = Pfeuuv (V(A))5 for S diag((-1,1}* and P permutation matrix.
Proposition 5. Let A C guxn denote the matrices with distinct first-k eigenvalues. For A E A, let V(A) = (A),...... 2s (A)) be choice of orthonormal eigenvectors of A, associated to the first-k (distinct) eigenvalues >1 (A(A). ... .. (A). Then
(a) The map Gnode A + RR" given by Gnode(A) fnode (Foquiv (V())) is well-defined and gives structural node representation.
(b) The map Opair A > Raxx defined by qpair (pair(A),, (A)a,) = Sdccode (Sequiv (V())) (V (V()))
is well-ae well-defined and gives structural node-pair representation.
Note that the identity mapping V(A) + V(A) permutation equivariant and sign equivariant, so using fnode faecode directly eigenvectors also gives structural representations, The statement
19

---

(b) means that our link prediction pipeline with sign equivariant node features and sign invariant decoding produces structural node-pair representations.
Proof. Part (a) We first show that Inode A - R is well-defined. Suppose we had another choice of eigenvectors, so the eigenvectors we input are V ((A)S for some diag({ -1, 1)²). Then
Juode (Squiiv (V(A)))) funde (Jequiv (V())) Snode (Jequix (V()))
(29)
where the first equality is by sign equivariance, and the second equality by sign invariance. Thus, the value gnode (A) is unchanged.
Now, let P be any permutation matrix. Then for each eigenvector v; E [k.] we have (PAPT) (A) = (A) = (uA)) so (A)(A) is an eigenvector of PAPT associ- ated to (A( = (( Hence, we denote v, (PAPT) (A((A) (the choice of sign does not matter as q does not depend the sign. Now, have that
Inode! (PAPT)
Snode (Joquin(V (V(PAPT))
(30)
fnode (fequiv (PV())))
(31)
Pnode (Sequiv (V (V(A))
(32)
Pooode (A)
(33)
where the second to last equality is by permutation equivariance of Snode and fequiv-
Part (b) That Opair A - _=x" is well-defined follows from similar argument to the moode case. Let P be permutation matrix, and a : [n]] + [ni] its underlying permutation. We compute that
9pair (PAPT) = faecode (fequiiv ( (V(PAPT) )),,, fequiv (V(PAPT))
(34)
Sâvcodo (Joquiv (P)((A))::))))))) S Sequiv (V(A));:
(35)
fdecade ((P fequiv (V(A)) [Pfequiv (V()))s
(36)
fdecode (Fequiv (V (V (A)) 16).;: Soquiv (V (A)))-1())))
(37)
Spair (1),o-)))))
(38)
= (Papair ( (A) A)PT)).).)
(39)
A.5.1 Sign Equivariance is Provably More Expressive for Link Prediction
Our arguments in Section 2.1 and Figure 2 explain why we can expect sign equivariant models to be more powerful than sign invariant models link prediction. To give theoretically rigorous explanation. here we provide example where sign equivariant models can provably compute more expressive link representations than sign invariant models.
Consider cycle graph Czu for some even length 2k, where k 2 3. All nodes are automorphic in this graph, so any model based structural node representations must assign the same representation to each node-pair. For instance, consider the eigenvalue -2 of the adjacency matrix, which is a simple eigenvalue with eigenvector [1, 11, 1,..................... 1, -1] [Lee et al., 1992]. Then a sign invariant model will lose the sign information and map each node to the same encoding, which means that each node-pair will also have the same encoding. However, a sign equivariant model can preserve the sign of each node (for instance by learning the identity function). Then for any pair of nodes that are one hop away, it can take a dot product compute the pair representation 11, whereas it can take a dot product between any nodes that are two hops away to compute the pair representation 1. Of course, using more eigenvectors would allow for more complex representations be computed.
A.5.2 More on Sign Equivariance and Link Prediction
Key to our method is the ability to update positional node embedding in an equivariant way, which respects the graph symmetries. To elaborate, consider the aforementioned definition of node positional encodings samples from a permutation equivariant probability distribution over node features [Srinivasan and Ribeiro, 2019]. Laplacian eigenvector positional embeddings are samples from the distribution of orthonormal bases of the eigenspaces of the Laplacian. Our sign equivariance
20

---

based approach is possible because the randomness in Laplacian eigenvector positional encodings is exceptionally structured (consisting only of sign flips when eigenvalues are distinct). In contrast, general way to obtain structural pair representations from node positional embeddings is to average some function over the randomness of the positional encoding (i.e., over many samples of the positional encoding) [Srinivasan and Ribeiro, 2019], but this is highly expensive, often intractable, and introduces substantial variance into the learning procedure. For instance, one may have to average samples of the n! assignments of unique node identifiers [Murphy et al., 2019] or approximate an integral over Gaussian random features [Abboud et al., 2021J.
A.6 Proof of Proposition 2, Orthogonal Equivariance via Sign Equivariance
Proposition 2. Consider a domain X C R such that each X E X has distinct covariance eigenvalues, and let Rx be choice of orthonormal eigenvectors of cov(X) for each X. h X _ Rxxd -> Baxd is sign equivariant, and if f h(XRx) then f is well defined and orthogonally equivariant.
Moreover, is h is from universal class of sign equivariant functions, then the J of the above form universally approximate O(k) equivariant functions on X.
Proof. First, we show that f is well defined. Rx is only unique up to sign flips, Rx S is an orthonormal set of eigenvectors of cov(X) for S E 1)) However, no matter the choice of signs, f(X) takes the same value, since
{(x x(X RX
(40)
((XXx)SS R
sign equivariance
(41)
= =((XRx)R)
(42)
Next, we show that f is (k) equivariant. Let Q E +(k) be any orthogonal matrix. Note that
cov = xQ - n - [XQ
11 - = QT cov co)(
(43)
n
Thus, QT Rx is an orthonormal set of eigenvectors of cov(xQ) This means that there is choice of signs S E diag({ 11 1),) such that Q RxS RxQ. Hence, we have that
S(XQ) ((XQRxx) RXo
(44)
=(XQQ Rx Rx
(45)
=S(XR))SST RIQ
sign equivariance
(46)
=
(47)
=(X))
(48)
so f Ok) equivariant.
Universal Approximation. Our proof of the universality of this class of functions builds on the proof of the universality of frame averaging [Puny et al., 2022]. Let fwarge be a continuous O(k) equivariant function and let >> 0 be a desired approximation accuracy. Then ftarget is also sign cquivariant (as the sign matrices S E diag(f-1,1)") are orthogonal).
Hence, by sign equivariant universality, [|n(X) - ftarget (xiget(() (X)ll < e for all X (where ||-|| is the Frobenius norm). Define the O(k)
can choose sign equivariant h such that
cquivariant f(X) = (xXRxx)xxx))) RI. Then for all E X' we have that
feareet (X) f(X)]l fearget (X)
(49)
f Starget (X)Rx 1(XR))
Rx orthogonal
(50)
Stargor X (R -
orthogonal equivariance
(51)
Itarget (XRx) - h(XRx)l
Rx orthogonal
(52)
(53)
So approximates frarget within accuracy on X, and we done.
21

---

B Sign Equivariant Linear Maps
B.1 Sign Equivariant Linear Map Characterization
We first prove our result characterizing the form of the equivariant linear maps from Ra Rx Lemma 1. linear map W B R='xx x sign equivariant if and only if it can be written as ( = [W1X] W&X
(54)
for some linear maps W1,..., WA: R" - RR",, where X; R is the ith column of X B
Proof. For one direction, suppose W can be written as equation 4. To see that W is sign equivariant, note that for any S diag((-1, 1) have
W(XS) = [s W se W = [ W W(X)S.
(55)
For the other direction, let W be sign equivariant linear map. For any i' [n''] and j" [K]] write the action as
W(X)
Xa.
(56)
where W E I are coefficients representing the linear map. Let + jí be a column that is not j'. Further, for any row I [n]. let X Bank be such that X 1, and X is zero elsewhere. Then we have that
W(X)e Je Who 8
(57)
Now, let S E ciag((-1,1}{) have -1 in the j'th column and a elsewhere. Then Xs = X. This implies that
why = W())ss''
(58)
W(X5)
(59)
= (()))e))
(60)
=-W 8ig
(61)
where in the second to last equality we used sign equivariance. This implies that who Pgg 0.
Hence, for any E [n'].j" E [k'], we have that W W only depends on Xy, so we are done.
B.2 Sign Equivariant Linear Maps between Tensor Representations
Since the sign equivariant linear maps from Boxk - Rn x are very weak, we now characterize sign equivariant linear maps between higher order tensor representations, as past work has done for other groups [Maron et al., 2018, 2019, Finzi et al., 2021]. particular, we will consider representations I&* m for natural numbers m. The action of {-1, 1 on k& as follows:
(s V) V) = Si, ......... Sim V Vi
(62)
for i1.......................... ................................ im [k). We prove a result showing that there no sign equivariant linear maps between many pairs of tensor representations.
Proposition 6. If mı + m2 is odd, then the only sign equivariant linear map L the zero map.
p is
Let L R 2 " R This means that for V E k for ii,.... img E [ki] we have that
Proof.
be the matrix associated with sign equivariant linear map from I
(LV
Li big Stnnn V Vin..-Smy
(63)
fuuntmm =1
22

---

Then by sign equivariance, we have that
L(s V) = (LV),
(64)
for {-,,1) which means that for all i,,...; [k].
Li st timmmm 8/1 ... 8mg Viniitt
(65)
Jamendmy =1
k
8img
Σ
I big Jiunddm V Vinnimy
(66)
=1
which means that
Liggondngddinnna 8is ... Sim2 831 ... 8jm1 Viundmy
(67)
Jtvendm =1
Li figgniig Jmy
V Vinniiin
(68)
Jioodmm =1
This gives that s = L. Choose some arbitrary indices i...... 4mz J1..... .......Im.... Jm, [k]]. Since mi + m2 is odd, then one of these values appears an odd number times say some index E [k]. Let E 1} have s; = for i and 8p -. Then s L = L implies that
Li im. In Jm
Li St
(69)
Which implies that T. is zero at these indices, and hence 0 everywhere, since these were arbitrarily chosen indices.
This implies that we cannot map from R* + R using sign equivariant linear maps. Thus, if we want to lift our order-one tensor input to higher tensor orders in linear way, then we need to at least map to third order tensors in R&* This requires substantial memory cost. Furthermore, that even if we could map to third order tensors, learning representations of third order tensors with sign equivariant linear maps expensive.
show
Proposition 7. The dimension of the space of sign equivariant linear maps from R
RR
1
Σ
(81 +
) tm2
8k
(70)
2
Proof. This direct consequence of First Projection Formula: see Fulton and Harris [2013] Section 2.2. In particular, it can be seen that the dimension of this space is equal to
Σ
trace( (mm))
(71)
2
SEDiag(f 1,11*)
by the First Projection Formula. Since trace( A 2 B) = (A) trace B), this is equal to
Σ
(race(S)m111t = 2k
1
Σ
(s1 + 24) mm
(72)
2k
-.Diag(f-1111
1,13*
Using Proposition 7, we have numerically computed the dimension of the space of sign equivariant
linear maps from IR** k see Table The dimension appears be 15A 30k 16k for up to 20. In particular, when & = 8, we compute that the space of sign equivariant linear maps from k + & is of dimension 5888, which is already quite large.
23

---

Table 4: Dimension of the space of sign equivariant linear maps between third-order tensor represen-
tations R IR
k
Dimension
1
2
32
3
183
544 4
5 1,205
6 2,256
7 3,787
8
5,888
9 8,649
10
12,160
16,511 11
12 21,792
28,093 13
35,504 14
44,115 15
16
54,016
65,297 17
18
78,048
19
92,359
20
108,320
C Characterization of Sign Equivariant Polynomials
In this Appendix, characterize the form of the sign equivariant polynomials. This is useful, because for a finite group, equivariant polynomials universally approximate equivariant continuous functions [Yarotsky, 2022]; thus, if a model universally approximates equívariant polynomials, then it universally approximates equivariant continuous functions. Using equivariant polynomials to analyze or develop equivariant machine learning models has been done successfully in many contexts [Zaheer et al., 2017, Yarotsky, 2022, Segol and Lipman, 2019, Dym and Maron, 2021, Maron et al., 2019, 2020, Villar al., 2021, Dym and Gortler, 2022, Puny al., 2023].
C.1 Sign Invariant Polynomials I +
Next, we characterize the form of sign invariant and equivariant polynomials. For simplicity, start with the case of sign invariant polynomials IR - R. The sign equivariant polynomials take very similar form. We can write any polynomial from IR in the form
D Σ di....d::0
p(v) =
W
de
(73)
for some coefficients Wa E IR and some D E N. Sign invariance tells us that for any = diag(s1...... sk) 3x) ) we must have
Σ Wa ..... de = vvv) p(Su)- =
Σ di di...d===
W
ok de de ... (74)
di...d==UU
This holds for any E Rk so for all choices of di...., d, we must have
W
di
W Wa dey for all (81....,, 8x) E (-1,1)*.
(75)
Note that d if d; an even number. Hence, there are no constraints on Wd,....d, if all d, are even. On the other hand, suppose dy is odd for some Let s; for af j and s, = -1 Then the
24

---

constraint says that di.....de Wd so we must have We.....dd = 0. To summarize, we have
free
de even for each
W W wi...
(76)
else
Where being free means that the coefficient may take any value in I.. Thus, any sign invariant p only has terms where each variable v; is raised even power. It is also easy see that any polynomial where each variable U, is raised to only even powers is sign invariant, so we have the following proposition:
Proposition 8. A polynomial p. IR + R is sign invariant if and only if it can be written
p(u) = Σ
2d. V1 N4
1k
(77)
di...,d==
for some coefficients Wa E R and D
In other words, sign invariant if and only if there exists polynomial q RR R such that p(u) =
C.2
Sign Equivariant Polynomials I2* + R
The case of sign equivariant polynomials p= IR R& is very similar. For E [k). the Ith output dimension of any polynomial p IR IR* can be written
D
p(u) =
Σ
W di.....e
2i
de
(78)
where W di....dy R are coefficients (note the extra index, so there are k times more coefficients than in the invariant case). By sign equivariance, we have
St u(u)))) p(Su),
(79)
D
81
Σ
O
di
de
Σ
W
de....de
dx
(80)
di...,
dI
As this holds for all inputs v E R we have the following constraints on the coefficients:
st w
da = $1 ...8% (())
(81)
di
O d = S1 -1
( d2
(82)
where we use the fact that 81 = 1/st since 81 E f- If d, is odd for j * I, then similarly to the invariant case,
take 8; 1 for i X j and sj -I in the above equation to that
((() di....du = O. If di is even, then di + is odd, so we have that w()) di....d = 0 by the same argument.
Thus, we must have
f free di odd, and d2 even for each i
(83)
di
else
Thus, the /th entry p(e) only contains monomials of the term o uf
ui 2ds where each term besides vi is raised an even power. We can factor by and write such terms vz uddh u... 2ds, It is also easy see that any polynomial with monomials only of this form is sign equivariant. Thus, we have proven Proposition 9.
2dc
Proposition 9, A polynomial p Iet + R is sign equivariant if and only it can be written
D
p(r): = 01
Σ
2dc
(84)
di....de
In vector format, is sign equivariant if and only if it can be written p(u) Paa (v) for sign invariant polynomial Pinv k - l2
25

---

C.3 Sign Equivariant Polynomials R - Ra'
Finally, we will handle the case of polynomials p R=** - R²'x equivariant to This is the case we most often deal with in practice, when we have input = [e] [x] for k eigenvectors Uy IR of some x matrix. For E [n') and b E [Ri], the (a, b)th output of polynomial Ro*k + R is
D E
PVa Jab
w
des V.'
(85)
d,,==
i=1j=1
where the sum ranges over dis (O....,D)
D} for
[n| and j [k]. and
d = (di.1...... d drr)) is a shorthand to index coefficients W ariance, we have that:
E R. By sign equiv-
Sb P(V)a, = p(V
(86)
D
k
D Σ d=-=0
w(abb)
wla.b)
36
(87)
where d, = Ex dr. y is the number of times that entry from column of V appears in the product 1I- 11ş-1 Vil. As this holds over all V, we thus have that
w(a s6 s di
S w(a.b)
(88)
By analogous arguments to the previous subsections, if dj is odd for j # b, we have that the w(o = 0. Likewise, if dy is even, we have W(( = 0. Thus, the constraint on W
(o.b) free 0
di odd, and E. di, even for each j # else
(89)
In particular, this means that the only nonzero terms in the sum that defines p( )o,6 have an even number of entries from column for j * and an odd number of entries from column Thus, each term can be written as V.g.b Piav (V)a Pinv((Va for some index ia E [n] and sign invariant polynomial Pine- Moreover, it can be seen that any polynomial that only has terms of this form is sign equivariant. Thus, we have shown the following proposition:
x is sign equivariant if and only if can be written Proposition 10. A polynomial p R R= as
(V)).b Ja,b Σ
w(a V Vig
Pine (V),,
(90)
d.,=0
where Plav is a sign invariant polynomial, the sum ranges over all d, and ia E [n] for each d.
Now, we show that this implies Theorem 1. In particular, we will write p in the form
p(V) (2) (wWWV) (V)).
(91)
for sign equivariant linear maps (2) and W(1, and a sign equivariant polynomial finv- To do so, let D denote the number of all possible d that the sum in equation 90 ranges over. We take W(1) R + I Dn's x and (2(2) RDnn x - IRn xk These sign equivariant linear maps have to independently on each column of their input, y [1 U1,... w ......W!! uk] for linear maps
W:(1) RR + DD' We define w to be the linear map such that (W-("), 1))a,, a, w/(ab) V. for
a E [n']. For the sign invariant polynomial ginv. we take gnv (V)aaV), = Pinv ( ).
Finally, we define (2) to compute the sum in equation 90. In particular. for X [a 1Fi...,,4y
ōn' xk we write ( x [W(2) Ii,..., w2(2) æx]. where (W (2) 2b)aa Ea Zig.b- It can be seen that with these definitions of (2), (L),, and glvv. we have written p in the desired form.
26

---

C.4 Sign Invariant Polynomials and SignNet
For completeness, here we state the form of the sign invariant polynomials p. : B + R on inputs V = [V1,.... [s] E Bank The derivation very closely follows that of the sign equivariant polynomials from Baxk - R in Appendix C.3,
omit this derivation.
Proposition 11. polynomial p= B + R is sign invariant if and only if be written
D
p(V) = Wa
Σ
(92)
=1
where Wa # for d (di, 1 212 k only if Ei= da.j is even for each column j E [k).
In particular, p is sign invariant if and only there is a polynomial q Raxxxk IR such that
p(V) = ((Vi Vind)litno).setno..eE.
The polynomials V - Vio Vig for in, i2 E [n) and j E [k] are thus generators of the ring of sign invariant polynomials from Rax + IR.
Notably, Lim et al. [2023] propose universal sign invariant neural architectures, but do not characterize or otherwise use the sign invariant polynomials. Instead, their proof of universality uses topological constructions and shows that all sign invariant continuous functions
be decomposed in simple for continuous functions p and Φb Our characterization of sign invariant polynomials provides another path to developing and analyzing the expressive power of sign invariant architectures.
form-namely, pl ((((:)) + Φf ((-r)))i=1,.....
In particular,
give alternative proof for the universality of SignNet.
Proposition 12 (Universality of SignNet). Let f X C guxk E be continuous sign invariant function compact domain X, and let 0. Then there exists continuous p:: R + R. and continuous o R RRn such that [f(V) p((((u) ((-..)))=.....k) for all V X.
Proof. First, let p be sign invariant polynomial that approximates / to within on X. Then using Proposition 11, let be a polynomial such that p(V) = <(Vi... (lad)))))))))eeeleeeee)))))
Define Φ R" + Rn² to map a E R to the vector of pairwise products of elements in v scaled by 1/2, that is
d(v) vec(ve))
(93)
Then p(v) + o( v) is equal to the vector of pairwise products of v. Finally, we let p q. which gives that
p(V) p((á(v)) - Φ( -
(94)
and hence
[f() p((((=)) + ((- (((=:))i=,.....))) (5(V) -P(V) <c
(95)
for all E X
Given the form of the sign invariant polynomials, this proof quite simple. However, is technically weaker than the result of Lim et al. [2023], they invoke the Strong Whitney Embedding Theorem and only require á to map to 8 instead of R=² Still, further arguments could probably reduce the dimension required to about 2n this polynomial-bas based proof: as the Gram matrix vr T is rank one, it can be recovered almost always from about 2n of its entries (Pimentel-Alaree et al., 2016).
D Sign Equivariant Architecture Universality
In this section, we prove Proposition 3 on the universality of our proposed sign equivariant architec- tures, which we restate here:
27

---

Proposition 3. Functions of the form + @ MLP((el) universally approximate continuous sign equivariant functions f IR= R
Compositions f2 fi of functions fi in equation 6 universally approximate continuous sign equivariant functions f Bgaxk 1 xk
We prove the statements the proposition in the next subsections.
D.1 Universality for functions E F
Proof. Let X' S R a compact set, let e > O, and let fuagee : X - F be a continuous sign equivariant function that wish to approximate within Choose sign equivariant polynomial that approximates ftarget within e/2 on X. By compactness, we can choose a finite bound such that ley] B for all E X.
By Proposition approximation theorem for multilayer perceptrons, we can choose a MLP : X - R2 such that 2dx approximates q(v)= = Ed Wat....de uid ... ..k up to e/(2) Note that g(v=)) = q
write p(u)
Ed Edi W dr vi
2d. 2ds By the universal
Uk
+ M[P((e)) also approximates q within c/(2B) accuracy.
Thus, for all X, we have that
[f(v), - -(()- MMM(M()
1/3
W di de 11
24h
1
2du
(96)
|<::|MMP(((o))
Σ
W Wag....de
11
2di ... -b
2dx
(97)
d=1
B. |MLP((
Σ
W de
2d1
2du
(98)
d=1
c/2
(99)
so |f plloo </2 on X' and done by the triangle inequality.
D.2 Universality for functions gank In xk
Recall that each layer our sign equivariant network from R + pg' takes the form
(V) ( v...... w(( Up] SignNet,
Proof. Let X' C Ba p be compact, and let ftarget X' + R=' x be continuous sign equivariant function that wish approximate. Since X' is compact,
choose finite bound B >> 0 such that |Vyl B for all V X. Let : X B RR be sign equivariant polynomial that approximates frarget to e/2 accuracy, Using Proposition 10, we can write
p(V)..b Σ
w(a Via.b Piav (V)d.
di,==0
for some sign invariant polynomials Pinv (V)a. We will have one network layer f1 approximate the summands, and have the second network layer Ja compute the sum.
First, absorb the coefficients w(a.b) into the sign invariant part, by defining the sign invariant polynomial qine (V) (V) = W(a.)) Pinv (V), so we can write
aV)..
Σ Vin. Tine (V) J.
di,==0
Now, let dhidden N denote the number of all possible that appear in the sum, multiplied by n'.
We define fi X' - Id daidden xk follows. As SignNet [Lim et al., 2023] universally approximates
28

---

sign invariant functions on compact sets, we can let SignNet, & + Rddidde x be SignNet that approximates (V) up to e2B) accuracy.
SiggnNet, (V) Tin (V)d. < 2B dhidden
(100)
For b E [k], we also define the weight matrices W; E lR [Bdaideen xn of the layer by letting the (d, a a)th row (W, (1) (d,a), for any [n)] only be nonzero in the iath index, where it is equal to 1. Thus,
(W eb)ad.a) = Via.b
(101)
Hence, the first layer takes the form
... Via SignNet, (V)d. E ER. (102) (i(Vid..). [Va., SignNet,(V
Now, for the second layer, we let (V))) = for i [r].] E [K], which can be represented exactly. Then for each column ò E [A] will define weight matrices w.!" such that (W(2)) (d.i)) = if a and is O otherwise. Then we can see that
f2 (i(V), Do,b
Σ Via. SignNet, (d,a),
(103)
To that this approximates the polynomial p. for any V X we can bound
a,, f2 (V
Σ Vig.b (yiur V. SignNet, (V).)))))))
(104)
Via.bll (ginv (Clnnn(Vadaaa (V)d.,b SiguNet, (V) (d..))))))
(105)
d
B
(gune (V)d,a. SiguNet, (1) (V)d))).)
(106)
d
B
Σ
(107)
d 2Bd
e
(108)
2
By the triangle inequality, f2 fi is e-close ftarget, are done.
E Experimental Details
E.1
Miscellaneous Experimental Details
We ran the experiments on a HPC server with CPUs and GPUs. Each experiment was run on a single NVIDIA V100 GPU with 32GB memory. The runtimes for some of our experiments are included in the main paper. Our codes for our models and experiments will be open-sourced and permissively licensed.
E.2 Link Prediction in Nearly Synthetic Graphs
The base graphs H we generate are Erdös-Renyi or Barabási-Albert graphs with 1000 nodes. We use NetworkX [Hagberg al., 2008] to generate and process the graphs. The Erdös-Renyl graphs have edge probability Let V [=....... 2x be Laplacian eigenvectors of the graph. We take The unlearned decoder baseline simply takes the predicted probability of a link between and j to be proportional to the dot product of the eigenvectors embeddings of node and node j; this has no learnable parameters. In other words, the node embeddings z; and z₁ are taken to be Vi, and Vj. respectively, and the edge prediction is 2. 2j. The learned decoder baseline takes the same and 2j.
.05 and the Barabási-Allerr graphs have = 20 new edges per new node.
16 in these experiments.
29

---

Results are but takes the edge prediction to be (2; @ 2z). Every other method learns node embeddings 24 and 2j. and takes the edge prediction to be 2 Zj.
Each model is restricted to around 25,000 learnable parameters (besides the Unleamed Decoder, which has no parameters). We train each method for 100 epochs with an Adam optimizer [Kingma and Ba, 2015] learning rate of .01. The train/validationntest split is 80%//0%//00% and is chosen uniformly at random.
E.3 Details on n-body Simulations
We follow the experimental setting and build on the code of Puny et al. [2022] (no license as far as we can tell) for the n-body learning task. The code for generating the data stems from Kipf et al. [2018] (MIT License) and Fuchs al. [2020] (MIT License). There 3000 training trajectories, 2000 validation trajectories, and 2000 test trajectories. We modify the data generation code to apply to general dimensions d 3. We do not change any of the scaling factors in doing For each dimension d, we use the same hyperparameters for both the frame averaging model and the sign equivariant model.
Table 5: n-body simulation results for dimension d 3. Lower MSE better. from [Satorras et al., 2021, Puny et al., 2022, Kaba et al., 2023].
Model
Test MSE
Linear
.0819
SE(3) Transformer [Fuchs et al., 2020]
.0244
TEN [Thomas et al., 2018]
.0155
Radial Field [Köhler al., 2020]
.0104
EGNN [Satorras et al., 2021]
.0071
FA-GNN [Puny et al., 2022]
.0057
CN-GNN [Kaba et al., 2023]
.0043
Sign Equivariant (Ours)
.0065
In Table
E.4 Node Classification on CLUSTER
In Section 4.3, show results for the node classification task CLUSTER (Dwivedi al., 2022a]. where the task is to cluster nodes in graphs drawn from Stochastic Block Models [Abbe, 2017]. Models are restricted setting of Rampasek et al. [2022], except we report results for the eigenvector based methods on runs instead of 10.
a 100k learnable parameter budget. We largely follow the experimental
We test several eigenvector based methods within the GraphGPS framework and codebase [Rampasek al., 2022] (MIT License), which is state of the art Transformer / GNN hybrid. Firstly, make use of the PEG style GraphGPS, which means that the MPNN in the /th GraphGPS layer takes as edge
features e (2 (1() 1 where V.()) R is the eigenvector embedding of node i in layer L. This is fully (kk) invariant (which is much stricter than sign basis invariance), so we relax this to just be sign invariant our model by learning a diagonal matrix (()) such that (!) = viOT D())()) Also, the standard GraphGPS only updates eigenvector representations (in non-equivariant manner) before most of neural network modules. When we add our sign equivariant model, we instead update eigenvector representations within each GraphGPS layer via (L)) = f( (v(1-1) for sign equivariant (()) Raxk -> Back
30


Reviews:
[{"review_id": "wwdoUvSJxX", "reviewer": "Reviewer_YXFy", "summary": "This paper proposes to build sign equivariant neural networks with applications of the method in O(n) equivariant modeling and graph representation learning. They show that corresponding equivariant MLPs are inexpressive, by contrast to the proposed method which is universal (non-permutation equivariant version) or plausibly much more expressive (permutation equivariant version). Experiments are performed on artifcial datasets and show that the proposed method achieve comparable or better results than alternatives. ", "questions": "(Q1) Can the authors provide a comparaison of their theoretical results with [Villar 2021] and discuss how their work compares?\n\n(Q2) Would you elaborate on some limitations of this work and potential future directions?", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This is a well written and motivated paper. I also appreciate the detailed appendix.\n\nThe experimental protocol seems rigorous and results are presented for a few different settings.\n\nThe paper highlights interesting and potentially useful applications of sign (O(1)) equivariance. ", "weaknesses": "(W1) I think the main result of this paper could be obtained from the results of [Villar 2021]. They already show how to use invariants to builds equivariant functions. Sign equivariance is O(1) equivariance, so it is a particular case of O(n) equivariance. This connection is not mentioned by the authors and would be important to investigate. As such polynomials may not really be needed, the results from invariant theory could be sufficient. Also, Proposition 11 from the aforementioned work may offer a way to obtain the desired permutation equivariance with universality.\n\n(W2) More generally, given the previous comment, I feel like the paper should situate itself more within the literature on O(n) equvariance, since sign and basis equivariance are that. I appreciate that some of the applications considered included processing eigenvectors, which is different from most of what is done in that literature, but this was already put forward by [Lim 2023].\n\n(W3) The experiment on CLUSTERS is interesting but the improvement to other methods is not too important and has not convinced me of the practical usefulness of the method. Especially, since CLUSTERS is a synthetic task. It would also be great to have results on real-world graphs to see if the method brings a performance increase there.\n\n(W4) It seems like the proposal for orthogonal equivariance is a realization of the partial canonicalization framework of [Kaba 2023]. Partial canonicalization is performed with respect to SO(3), with the reminder handled by a sign equivariant function. Proposition 2 follows from their results. The results on the N-body problem seem worst compared to learned canonicalization, which should be included for comparison. There are also many other methods outside of those presented in [Puny 2022] that could be compared against.\n\n(W5) The paper [Sachs 1983] is relevant to the Proposition 1 presented in this paper and should be mentioned.\n\n(W6) I think the application on link prediction is the most promising aspect of the submission. The authors should compare with the setup/methods that was proposed by [Sartorras 2021] in their autoencoding experiment. In that paper, the method was used to solve a similar issue caused by automorphic nodes.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their in-depth comments and suggestions for our paper! Here we address the comments:\n\n> “(W1) I think the main result of this paper could be obtained from the results of [Villar 2021]. ... Sign equivariance is O(1) equivariance, so it is a particular case of O(n) equivariance… ”\n\nWe kindly disagree. The key difference is that they only consider $O(d)$ (or $O(1)$), whereas the main group we consider is a direct product $O(1) \\times \\ldots \\times O(1)$ (for sign equivariance) or $O(d_1) \\times \\ldots \\times O(d_l)$ (for basis invariance). \n\nThese are related, but the direct product group has specific challenges of its own. For instance, interactions between eigenspaces cannot be obtained by simple methods like equivariant linear maps (as explained in Section 3.1).\n\nWe are not aware of any way to directly obtain our results using the results of [Villar et al. 2021]. But we are open to more specific suggestions if the reviewer has any.\n\n> ”such polynomials may not really be needed, the results from invariant theory could be sufficient”\n\nWe are not aware of a result in invariant theory from which our results follow directly. Invariant theory is (in large part) the study of equivariant or invariant polynomials, and our derivations allow us to find a form specifically for the sign equivariant polynomials.\n\n> “Also, Proposition 11 from the aforementioned work may offer a way to obtain the desired permutation equivariance with universality.”\n\nThanks for the suggestion. We were very much aware of this work and these results, but we did not figure out a way to use them for our case. Also, this result does not lead to an efficient network architecture (directly parameterizing the functions would require $nd$ neural networks, with permutation constraints that must be enforced as in equation 13 of their arxiv version).\n\n> “(W2) … paper should situate itself more within the literature on O(n) equvariance, since sign and basis equivariance are that. I appreciate that some of the applications considered included processing eigenvectors … but this was already put forward by [Lim 2023].”\n\nSign and basis equivariance are not quite $O(d)$ equivariance, but rather $O(d_1) \\times \\ldots \\times O(d_k)$ equivariance (as mentioned above). They are related though, and we will include more information in the revision about the connection to $O(d)$ equivariance literature. At the moment we have some relevant content on this in Appendix A.2.1. Some key differences in our case are the proof techniques (the direct product adds complexity, but the fact that we mostly consider $d=1$ for the sign group allows us to use simpler linear algebraic techniques).\n\nWe indeed do process eigenvectors as in [Lim 2023], but as noted in Sections 2.1 and 2.2, sign invariance [Lim 2023] is provably limited in learning multi-node representations or $O(d)$ equivariant functions, whereas our sign equivariance methods are provably expressive here.\n\n> “(W4) It seems like the proposal for orthogonal equivariance is a realization of the partial canonicalization framework of [Kaba 2023] ... Proposition 2 follows from their results. The results on the N-body problem seem worst compared to learned canonicalization, which should be included for comparison … .”\n\nThanks for this, you are correct in that our method works within the [Kaba et al. 2023] framework of partial canonicalization, in which our subgroup is $K = \\\\{-1, 1\\\\}^d$ of the orthogonal group $G = O(d)$. Moreover, our Proposition 2 does follow from their Theorems 3.1 and 3.3. We will note this nice connection in our revision, though we will keep our own proof as well for clarity.\n\nOur novel contributions in relation to [Kaba et al. 2023] are:\n\n1. We choose $K = \\\\{-1, 1\\\\}^d$. This is an important design choice, and Kaba et al only choose the trivial group $K = I$ when dealing with $G = O(d)$ in practice.\n2. We choose an unlearned canonicalization up to $K$, via PCA frames [Puny et al. 2022]. Kaba et al. achieve their best results with learned canonicalizations.\n3. We are the first to design a $K = \\\\{-1, 1\\\\}^d$ equivariant network. This is a necessary component, and we are also able to do this in a provably universal way, which is required to apply Theorem 3.3 of Kaba et al.\n\nWe will add discussion of this to the revision, and we will add comparison to more recent $O(d)$ equivariant models like Kaba et al.\n\n> “(W5) The paper [Sachs 1983] is relevant to the Proposition 1 presented in this paper and should be mentioned.”\n\nWe assume you are referring to the paper “Automorphism group and spectrum of a graph.“ In our opinion it is not necessarily so relevant to our Proposition 1, in the sense that one can understand either without understanding the other.\n\nHowever, what is certainly relevant is the general connection between graph automorphisms and repeated eigenvalues. We will add some discussion to our paper about this. In summary, graph automorphisms often lead to repeated eigenvalues, but not always. We will add this reference and discussion to our paper.\n\n> “(W6) I think the application on link prediction is the most promising aspect of the submission. The authors should compare with the setup/methods that was proposed by [Sartorras 2021] in their autoencoding experiment ...”\n\nGreat point, perhaps our method could be used for their autoencoding experiment, but we did not have time to try it; our method would take eigenvectors as additional node features to break node symmetry (instead of random noise), and decode in a similar sign invariant way. This is nice, as our method would learn structural node-pair representations if eigenvalues are distinct, whereas their method is not exactly permutation equivariant (since they use random noise). We may try this experiment in a later version of our paper.\n\n> “(Q1) Can the authors provide a comparaison of their theoretical results with [Villar 2021] ...”\n\nYes, see above. We will add further discussion to our paper.\n"}, {"review_id": "d1Zdg37Nke", "reviewer": "Reviewer_HW6g", "summary": "This paper focuses on addressing the sign ambiguity problem of eigenvectors. It argues that previous sign-invariant models are insufficient for some applications, e.g., link prediction and multi-node tasks. To solve this problem, the authors propose a sign-equivariant neural network with provable expressiveness guarantees, which is more powerful than the sign-invariant models and sign-equivariant linear maps. Experiments on various tasks validate the superiority of the proposed method.", "questions": "This paper considers both sign-equivariance and permutation-equivariance. I wonder why the authors do not discuss the basis-equivariance for eigenvectors.", "limitations": "This paper should discuss the limitation of sign-equivariance from the perspectives of efficiency and scalability.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper is the first to study the sign-equivariance problem of eigenvectors. It finds that the signs of eigenvectors contain meaningful positional information but the sign-invariant models can only preserve the structural information. Therefore, the sign-invariant models cannot distinguish automorphic nodes and are insufficient for link prediction or multi-node tasks.\n\n2. This paper proves that the sign equivariant polynomial can be implemented by the elementwise product between a linear sign-equivariant polynomial and a general sign-invariant polynomial. The linear sign-equivariant polynomial cannot learn the interactions between eigenvectors, and the sign-invariant polynomial cannot preserve positional information. This theoretical discovery combines the advantages of both methods and addresses their shortcoming.\n\n3. Based on the characterization of sign-equivariant polynomial functions, this paper provides a general framework for analyzing the sign-symmetry models and gives a new perspective on the universality of SignNet.", "weaknesses": "The major weakness of this paper is that it lacks experiments on real-world data. This paper uses three tasks, e.g., link prediction, n-body problem, and node clustering, to validate the effectiveness of the proposed method. However, all the experiments are based on synthetic data, which makes the results unconvincing. I think there are many real-world datasets for both link prediction and node clustering tasks, and the authors should give more empirical results on at least these two tasks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their work in improving our paper! We are glad that the reviewer appreciates our theoretical characterization of sign equivariant functions and improvements over sign invariant networks. Here we address the comments:\n\n> “The major weakness of this paper is that it lacks experiments on real-world data. This paper uses three tasks, e.g., link prediction, n-body problem, and node clustering, to validate the effectiveness of the proposed method. However, all the experiments are based on synthetic data …”\n\nTrue, even though the n-body task and node clustering tasks are standard benchmarks, they do consist of synthetic data. We did not manage to run more experiments for the rebuttal, but we believe that our experiments do support our theoretical insights, and note that other reviewers appreciate our experiments.\n\n> “This paper considers both sign-equivariance and permutation-equivariance. I wonder why the authors do not discuss the basis-equivariance for eigenvectors.”\n\nThis is a good point and a good idea for future work. The neural architecture would be more difficult to derive for the continuous symmetries in basis equivariance, and it would probably require different methods than our sign equivariant networks, which is why we do not cover it much. Basis equivariance would indeed be useful to handle repeated eigenvalues. For instance, basis equivariance could be used in Section 2.1 to obtain structural node-pair representations when the graphs have repeated eigenvalues. We will add discussion of this latter point to the revised paper.\n\n> “This paper should discuss the limitation of sign-equivariance from the perspectives of efficiency and scalability.”\n\nWe are not sure what the reviewer means here, please let us know if we have misunderstood. In our paper, we explain that for both of our main application areas, sign equivariant networks have efficiency and scalability benefits over certain baselines. In link prediction, sign equivariant networks only require one forward pass whereas most subgraph-based methods need a forward pass and graph construction for each predicted edge (Section 2.1, last paragraph). For orthogonal equivariance, sign equivariant networks only require one forward pass for inference on $d$-dimensional point clouds, whereas frame averaging requires $2^d$ forward passes (see also Figure 4 and Section 2.2, paragraph before the Proposition). See also Appendix A.2, A.2.1, and A.2.2 for discussion of complexity.\n\nAs for general limitations, we will add them to the revision, see general reviewer comment for more information.\n"}, {"review_id": "428EappdiA", "reviewer": "Reviewer_a3kf", "summary": "This paper contributes construction and analysis of sign equivariant neural network architectures for processing eigenvectors while respecting their symmetries. While a similar approach has been proposed by a prior work (Lim et al., 2023), this work is motivated by the fact that sign invariance, pursued in prior work, is in general not sufficient for multi-node tasks as sign invariance leads to structural node representations that does not distinguish automorphic nodes while multi-node tasks require positional node representations that provides a form of node identification (Srinivasan et al., 2019). The authors provide a construction of sign equivariant neural network architecture with analysis and provable guarantee on expressive power, and also propose its application as an alternative to PCA-based frame averaging which requires only a single evaluation of base model (while frame averaging requires 2^k) while guaranteeing equivariance to orthogonal groups in arbitrary dimensions. The developed architectures are empirically demonstrated for link prediction on graphs, n-body dynamics prediction, and node clustering on SBM graphs, which support the main claims of the paper.\n\nLim et al., Sign and Basis Invariant Networks for Spectral Graph Representation Learning (2023)\n\nSrinivasan et al., On the equivalence between positional node embeddings and structural graph representations (2019)", "questions": "I have no specific questions for now other than W1.", "limitations": "As far as I can tell, the authors didn't address the limitations and potential societal impact of the work. I encourage the authors to discuss them in the next revision of the paper.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "S1. The paper tackles an important and practical problem of developing expressive neural architectures that respect symmetry of eigenvectors, and successfully complements and improves key prior work (Lim et al., 2023) by achieving sign equivariance. Also, the paper is overall well written and easy to read, and the provided illustrations are clear.\n\nS2. The motivation for sign equivariance over invariance only is clearly presented in Section 2.1 where multi-node tasks are considered, and I find the discussion sound and informative.\n\nS3. In addition to multi-node tasks, a novel (as far as I can tell) and powerful alternative based on sign equivariance to PCA based frame averaging for modeling O(k) equivariant functions is provided. The approach trades off generality, as the base model (h) should satisfy sign equivariance unlike frame averaging that works with arbitrary base functions, but more efficient as it eliminates the requirement of frame averaging for 2^k forward passes.\n\nS4. The proposed parameterization of sign equivariant polynomial is novel and theoretically sound as it is grounded to the theory of equivariant polynomials. A strong theoretical guarantee on universality is provided for the non permutation equivariant case as well.\n\nS5. Overall, the experimental results overall seem sound and support the main claims of the paper.\n\nLim et al., Sign and Basis Invariant Networks for Spectral Graph Representation Learning (2023)", "weaknesses": "W1. The description of how sign equivariant network is applied in Appendix D.4 was a bit unclear to me. In in the equation e_ij = V_i^TDV_j, does the V refer to the output of sign equivariant module within the given GraphGPS layer? Is V passed and updated across GraphGPS layers?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments. We are especially glad that the reviewer liked section 2.1 on multi-node representations and link prediction, as we originally had trouble writing it, but spent time iterating on it.\n\n> “W1. The description of how sign equivariant network is applied in Appendix D.4 was a bit unclear to me. In in the equation e_ij = V_i^TDV_j, does the V refer to the output of sign equivariant module within the given GraphGPS layer? Is V passed and updated across GraphGPS layers?”\n\nThank you for pointing this out. Yes, $V \\in \\mathbb{R}^{n \\times k}$ are eigenvector representations, which we compute using our sign equivariant module. This $V$ is passed and updated in each GraphGPS layer using our module.\n\nTo make this clearer, in the revision we will denote the eigenvector representation of layer $l$ as $V^{(l)}$. Then $V^{(0)}$ are the original eigenvectors, and $V^{(l)} = \\mathrm{SignEquivariant}^{(l)}(V^{(l-1)})$. In contrast, the prior work PEG [Wang et al. 2022] takes $V^{(l)} = V^{(l-1)}$, meaning they do not update eigenvector representations.\n\n> “As far as I can tell, the authors didn't address the limitations and potential societal impact of the work. I encourage the authors to discuss them in the next revision of the paper.”\n\nThanks for the suggestion, we include a discussion in the general reviewer comment, and will add discussion to our paper.\n"}, {"review_id": "oAJ8QuWB7W", "reviewer": "Reviewer_p512", "summary": "The paper proposes a sign-equivariant design for processing spectral features in geometric deep learning.\nThis is particularly useful to process the eigenvectors of graph Laplacians and generate graph positional encodings, especially for link prediction tasks.\nThe equivariant, rather than invariant, approach guarantees improved expressivity of the models, which is verified in a numberof experiments.\n", "questions": "I don't think the claim that the Geometric Deep Learning approach fails here is correct.\nThe issue you describe is due to a bad design choice of intermediate representation within the network (i.e. the same as the input and output representation).\nNote that this choice is not common in other equivariant networks either; for instance, in group-convolution NNs (GCNNs), the input representation is an image (this is a quotient representation of $SE(2)$) but intermediate features transform like a regular representation (the output of a group convolution is a function over the full group, not only the pixels).\nThis step is fundamental to achieve universal approximation.\nThe limited expressive power you mention in line 48 is only due to the choice of intermediate representations (similarly, in a GCNN, if the intermediate features are constrained to transform as images, equivariance requires isotropic filters, which are indeed less expressive).\n\nIn any case, while a group-convolution approach is probably a poor choice here (the group $(-1, 1)^k$ has size $2^k$), smaller representations which can provide a better trade off might exist.\nYour method seems to provide a nice solution to this, so I would argue it still fits within the GDL framework but provides a more efficient solution than its naive implementation.\n\n\nIsn't computing the eigenvectors of the graph Laplacian an expensive preprocessing step?\nEstimating these features has $O(n^3)$ complexity, which seems to exceed the $O(n)$ operations in the DSS layers (or $O(n^2)$ is an attention-based or message-passing based model).\nIn Appendix A.2 you discuss the computational complexity of your method but do not include this aspect.\nCould you comment on this?\n\nCould you report the table with all baselines and their performance in Section 4.2?\nAlso, is there any more recent work on this dataset you could include?\n", "limitations": "I did not see an explicit discussion of the limitations in the paper, which I think would be a nice addition.\nFor example, the authors could comment further on the complexity of computing the eigenvectors.\n", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is clearly written and well motivated.\nI liked this simple yet effective design and I think the proposed method could be useful for many future works in the field.", "weaknesses": "I don't see major flaws in the paper.\nSee \"Questions\" for other comments.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful comments on the choice of group representations in intermediate layers. Here, we respond to the comments; we will add discussion about this to the main paper, which we think will be interesting to people in the equivariant machine learning community.\n\n> “I don't think the claim that the Geometric Deep Learning approach fails here is correct. The issue you describe is due to a bad design choice of intermediate representation within the network … “\n\nThe reviewer makes a great point here, the claim is more nuanced than how we wrote it in this paper. We will change our wording of the point to be less strong and capture more of the nuance (namely, the approach does not work for some choices of group representation, but other group representations may allow it to succeed). We also had some more results that we did not end up adding to the paper, which we now plan to add to support this point a bit more. \n\nIn particular, we derived the sign equivariant linear maps between tensor representations, and found that it would not be efficient to use tensor representations either. That is, at $n=1$ we considered the sign equivariant maps from $\\mathbb{R}^{k^{d_1}} \\to \\mathbb{R}^{k^{d_2}}$ for $d_1, d_2 > 0$. The sign group acts on $\\mathbb{R}^{k^{d_1}}$ via $((s_1, \\ldots, s_k) \\cdot x)_{i\\_1, \\ldots, i\\_{d_1}} =s\\_{i\\_1} \\cdots s\\_{i\\_{d_1}} x\\_{i\\_1, \\ldots, i\\_{d\\_1}}$. Note that the $d_1 = d_2 = 1$ case is the one considered in the current paper, where the only equivariant linear maps are diagonal matrices, so the equivariant linear maps have dimension $k$.\n\nWe can show that there are no sign equivariant linear maps (besides the zero map) between $\\mathbb{R}^{k^{d_1}} \\to \\mathbb{R}^{k^{d_2}}$ when $d_1 + d_2$ is an odd number. Note that this is also the case for the orthogonal group, as can be seen numerically in Table 6 of Finzi et al. 2021. In particular, this means that there is no linear way to map $\\mathbb{R}^{k} \\to \\mathbb{R}^{k^2}$ or back $\\mathbb{R}^{k^2} \\to \\mathbb{R}^k$, so if we want to lift our $\\mathbb{R}^{k}$ input to a tensor representation, you have to at least go to order 3 tensors (in $\\mathbb{R}^{k^3}$). This would already be quite expensive, and the linear maps between order 3 tensors ($\\mathbb{R}^{k^3} \\to \\mathbb{R}^{k^3}$) are also expensive, since they span a space of dimension 5888 when $k=10$.\n\nThis made us feel that the equivariant linear maps approach with tensor representations is too inefficient, so we did not pursue it further. We will add proofs of these points in the revised version, as others may find it interesting or useful.\n\n> “smaller representations which can provide a better trade off might exist. Your method seems to provide a nice solution to this, so I would argue it still fits within the GDL framework but provides a more efficient solution than its naive implementation.”\n\nThis is a good point! As argued above, the natural tensor representations (as used e.g. in [Maron et al. 2019] https://arxiv.org/abs/1812.09902 and [Finzi et al. 2021] https://arxiv.org/abs/2104.09459) are not a good choice for equivariant linear map based architectures for the sign group. We agree with you that regular representations of size $2^k$ are also too expensive without any tricks. However, other representations may be useful, and we will note this possibility in the main paper.\n\n> “Isn't computing the eigenvectors of the graph Laplacian an expensive preprocessing step? … Estimating these features has $O(n^3)$ complexity…”\n\nAs is commonly done in practice, we only use some subset of the Laplacian eigenvectors corresponding to the smallest $k$ eigenvalues (e.g. $k=16$ for our link prediction experiments). Then standard iterative eigensolvers can be used (e.g. scipy.sparse.linalg.eigsh), which are very efficient for sparse graphs. The time complexity is closer to $O(|E| k)$, where $|E|$ is the number of edges, which is usually close to linear in the number of nodes. For instance, on a standard laptop, computing the smallest $k=16$ eigenvectors of an Erdos-Renyi graph with average degree 10 takes 0.3 seconds for 10,000 nodes and 9.0 seconds for 100,000 nodes.\n\nFor the n-body experiments, the covariance matrix is $d \\times d$, where $d$ is the ambient dimension, which is typically quite small. Thus, there are no efficiency issues here as well.\n\n> “Could you report the table with all baselines and their performance in Section 4.2? Also, is there any more recent work on this dataset you could include?”\n\nAs suggested by Reviewer YXFy, we can also add the Kaba et al. paper just published at ICML 2023 https://arxiv.org/abs/2211.06489; this method achieves .0043 MSE in $d=3$ dimensions (hence outperforming our method in accuracy here), but the runtime scaling in $d$ may be worse, since their canonicalization network has to output a $d \\times d$ matrix that must then be orthogonalized via Gram-Schmidt, which has $O(d^3)$ complexity. Further, they do not test their methods on $d > 3$, and we do not have access to their code.\n\nFor the other baselines, we will include a table (possibly in the Appendix due to space constraints), but this would only include $d=3$ (as many methods only test on $d=3$, or only work on $d=3$).\n\n> “I did not see an explicit discussion of the limitations in the paper, which I think would be a nice addition. For example, the authors could comment further on the complexity of computing the eigenvectors.”\n\nThank you for the suggestion, see the general comment to all reviewers for limitations.\n"}, {"review_id": "tmmM2tu49O", "reviewer": "Reviewer_nERC", "summary": "The authors proposed a novel sign-equivariant model that is equivariant to the sign flip of eigenvectors for spectral graph learning. They demonstrated that the proposed architecture could capture the information when sign-invariant models would fail. The authors then made theoretical analyses of the sign-equivariant polynomial space and also proposed some constructible neural network architecture with sign-equivariance guaranteed by design. Experimental results on both the synthetic and real-world datasets demonstrate superior performance on link prediction, especially when automorphism exists.", "questions": "1. In Proposition 1, the first result claims that if $f$ is sign invariant and the eigenvalues are distinct, then the node-wise representations are the same for automorphic nodes. Consider the complete graph of 3 nodes, the adjacency matrix is\n$$\n\\begin{pmatrix}\n0&1&1\\\\\\\\\n1&0&1\\\\\\\\\n1&1&0\\\\\\\\\n\\end{pmatrix}\n$$\nWe have eigenvector $v_1=(1,1,1)$ belonging to $\\lambda=2$ and $v_2=(0,1,-1)$ belong to $\\lambda=-1$ (normalization is ignored for conciseness). Let $f$ be the pointwise absolute function, then $f$ is clearly sign-invariant (but not necessarily basis-invariant). In this graph, all three nodes are automorphic, but we have $z_1=(1,0)$ and $z_2=(1,1)$. This is probably because the eigenspace corresponding to $\\lambda=-1$ is 2-dimensional. Therefore, I believe basis-invariance is also a necessary condition. The first claim is also not directly proven in Appendix A.3.2. Please provide a more detailed justification.\n\n2. Similarly, the scenario when the dimension of the eigenvalue is greater than 1 is not explicitly discussed. In the above example, the sign-invariant model may still be capable of distinguishing the automorphic nodes. In footnote 2, the authors mentioned that sign invariant embeddings maintain \"some positional information\". The authors may provide a more accurate description using mathematical formulations similar to Proposition 1.\n\n3. What are the potential limitations of the proposed model architecture?\n\n", "limitations": "No potential negative societal impact is expected.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The paper is well-organized and easy to follow. The authors first provided an example to demonstrate the limitation of the previous \"sign-invariant\" models and then made theoretical analyses. Experiments were followed to demonstrate superior performance over the baselines.\n\n2. The problem that the authors tried to address is novel. The authors pointed out the limitation of sign-invariant models and mathematically supported their claim in Proposition 1. The proposed \"sign-equivariant\" architecture can properly address the limitation, both theoretically and empirically.\n \n3. The mathematics are solid and the claims are well-supported. The definitions of sign-equivariance and -invariance are well-formulated. Sign-equivariance of polynomials and neural networks is proven in the appendices. Universality is also proven and guaranteed.\n\n4. Experiments on graphs with high symmetries demonstrated the effectiveness of the proposed model architecture. State-of-the-art performance was also achieved.", "weaknesses": "1. Proposition 1 lacks some detail (See Question 1 & 2).\n2. Limitation of the proposed architecture is not explicitly discussed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> “Proposition 1 lacks some detail (See Question 1 & 2).”\n\n> “In Proposition 1, the first result claims that if $f$ is sign invariant and the eigenvalues are distinct, then the node-wise representations are the same for automorphic nodes. Consider the complete graph of 3 nodes, the adjacency matrix is…”\n\nIndeed, this issue that you note here arises because the eigenspace corresponding to $\\lambda=-1$ is two-dimensional. This misunderstanding is because we do not exactly define what we mean in Proposition 1 when we say “the eigenvalues associated with the $v_l$ are distinct.” By this, we mean that the eigenvalues $\\lambda_l$ are all simple eigenvalues, meaning that they all belong to one-dimensional eigenspaces, and also no two of the eigenvectors belong to the same eigenvalue. We will make this clear in the revision.\n\nWith this correct interpretation of our assumptions, we are confident that the proposition is correct in the sign invariance case: we only need that the eigenvalues corresponding to the input $v_1, \\ldots, v_k$ are all simple eigenvalues. The proof of the sign invariant case is exactly the same as the general basis invariant case; the orthogonal matrices $Q_t$ are just $1$ dimensional and hence they are signs.\n\n> “Similarly, the scenario when the dimension of the eigenvalue is greater than 1 is not explicitly discussed. In the above example, the sign-invariant model may still be capable of distinguishing the automorphic nodes. In footnote 2, the authors mentioned that sign invariant embeddings maintain \"some positional information\". The authors may provide a more accurate description using mathematical formulations similar to Proposition 1.”\n\nTrue, the repeated eigenvalues do arise in practice, and sign invariant embeddings are partially positional in this case since they are not fully basis invariant. It is hard to say too much in this setting, since the sign invariant embeddings are not even well-defined / deterministic here (the embeddings would depend on the choice of basis of the eigenspaces used as input). This also means that sign invariant embeddings would not lead to structural node-pair representations when there are repeated eigenvalues. We will make this latter point in the revision.\n\n> “Limitation of the proposed architecture is not explicitly discussed.”\n> “What are the potential limitations of the proposed model architecture?”\n\nThanks for the suggestion, see general comment to all reviewers for discussion of limitations.\n"}]

Author rebuttal:
We would like to sincerely thank all of the reviewers for the work they put into their reviews. The reviews are thoughtful, and the reviewers are each clearly experts in at least some of the several subject areas related to the submission (geometric deep learning, orthogonally equivariant models, spectral graph theory, graph neural networks); we very much appreciate these different viewpoints.

The reviewers suggested adding limitations (and potential societal impacts) several times, so we address them here. We will add these points to the revised version:
1. Limitation: we did not develop architectures for basis equivariance in the case of repeated eigenvalues. Repeated eigenvalues are known to occur in many real-world graphs [Lim et al. 2023], so future work in this area could be useful.
2. Limitation: though we expect the most gain in some node-level and multi-node level tasks on graphs, we do not have theoretical reasons to expect as much impact of sign equivariance on graph-level representations tasks, which for instance is common in molecular processing.
3. Limitation: our theoretical results and model design are focused on expressive power. We do not have results on optimization (e.g. [Xu et al. 2021]), robustness (e.g. [Wang et al. 2022]), or generalization (e.g. [Keriven & Vaiter 2023]). These latter three properties are very important for learning, so future work should address them.
4. Limitation: while we can achieve universal approximation in the non-permutation-equivariant setting, we do not know of the exact expressive power in the permutation-equivariant setting. We can not directly apply existing results from Maron et al. 2020, because the sign group does not act via permutation matrices here. Note that Lim et al. 2023 also faces this issue, and the exact expressive power for their permutation equivariant and sign invariant networks is unknown.
5. Societal impact: we do not foresee direct societal impacts from our work. This project is primarily theoretical and aims to improve models for two general application areas: multi-node representation learning and orthogonal equivariant models. Potential societal impacts may arise in downstream applications that may be affected by general progress in geometric machine learning, such as social network analysis and recommender systems. These two applications are known to have negative societal impacts in certain circumstances, so care must be taken in future related work to avoid major negative consequences.

**References**  
[Lim et al. 2023] Sign and Basis Invariant Networks for Spectral Graph Representation Learning.  
[Xu et al. 2021] Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depth.  
[Wang et al. 2022] Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networks  
[Keriven & Vaiter 2023] What functions can Graph Neural Networks compute on random graphs? The role of Positional Encoding


Meta-review: Reviewers were all positive about the paper, noting that: The problem of sign equivariance is important and well motivated. The paper is well written, well organized and easy to follow. The architecture design is simple yet effective. The mathematics is solid, and provides theoretical (universality) guarantees. The claims of the paper are well supported by experiments, and strong results are obtained. As such I am happy to recommend the paper to be accepted.
Decision: Accept (spotlight)