Sign and Basis Invariant Networks for Spectral Graph Representation Learning
Authors: Derek Lim
Joshua David Robinson
Lingxiao Zhao
Tess Smidt
Suvrit Sra
Haggai Maron
Stefanie Jegelka
Venue: NeurIPS 2022 Submitted (2022)
Keywords: Invariance
Equivariance
Graph Neural Networks
Eigenvectors
Spectral

Abstract: We introduce SignNet and BasisNet---new neural architectures that are invariant to two key symmetries displayed by eigenvectors: (i) sign flips, since if v is an eigenvector then so is -v; and (ii) more general basis symmetries, which occur in higher dimensional eigenspaces with infinitely many choices of basis eigenvectors. We prove that our networks are universal, i.e., they can approximate any continuous function of eigenvectors with the desired invariances. Moreover, when used with Laplacian eigenvectors, our architectures are provably expressive for graph representation learning: they can approximate any spectral graph convolution, can compute spectral invariants that go beyond message passing neural networks, and can provably simulate previously proposed graph positional encodings. Experiments show the strength of our networks for molecular graph regression, learning expressive graph representations, and learning neural fields on triangle meshes.

Sign and Basis Invariant Networks for Spectral Graph Representation Learning
Anonymous Author(s)
Affiliation Address
email
Abstract
We introduce SignNet and BasisNet-new new neural architectures that are invariant two key symmetries displayed by eigenvectors: (i) sign flips, since if an eigenvector then so is =u; and (ii) more general basis symmetries, which occur in higher dimensional eigenspaces with infinitely many choices of basis eigenvectors. We prove that our networks are universal, i.e., they can approximate any continu- ous function of eigenvectors with the desired invariances. Moreover, when used with Laplacian eigenvectors, our architectures are provably expressive for graph representation learning: they can approximate any spectral graph convolution, can compute spectral invariants that go beyond message passing neural networks, and can provably simulate previously proposed graph positional encodings. Experi- ments show the strength of our networks for molecular graph regression, learning expressive graph representations, and learning neural fields on triangle meshes.
10
11
12
Introduction
14 Numerous machine learning models process eigenvectors, which arise in various scenarios including principal component analysis, matrix factorizations, and operators associated to graphs manifolds. 16 An important example is the use of Laplacian eigenvectors to encode information about the structure of a graph manifold [Belkin and Niyogi, 2003, Von Luxburg, 2007, Lévy, 2006]. Positional
18 encodings that involve Laplacian eigenvectors have recently been used to generalize Transformers to graphs [Kreuzer et al., 2021, Dwivedi and Bresson, 2021], and improve the expressive power
20 and empirical performance of graph neural networks (GNNs) [Dwivedi et al., 2022]. Furthermore,
21 these eigenvectors crucial for defining spectral operations graphs that foundational to graph
22 signal processing and spectral GNNs [Ortega et al., 2018, Bruna et al., 2014].
23 However, there are nontrivial symmetries that should be accounted for when processing eigenvectors.
24 For instance, if v an eigenvector, then so is -u, with the same eigenvalue. More generally, an eigenvalue has higher multiplicity, then there are infinitely many unit-norm eigenvectors that can 26 be chosen. Indeed, a full set orthonormal eigenvectors is only defined up to a change basis in each eigenspace. In the case of sign invariance, for any & eigenvectors there 2 possible
28 choices of sign. Accordingly, prior works randomly flip eigenvector signs during training in order to approximately learn sign invariance [Kreuzer et al., 2021, Dwivedi et al., 2020]. However, learning 30 all 2 invariances is challenging and limits the effectiveness Laplacian eigenvectors for encoding positional information. Sign invariance is special case of basis invariance when all eigenvalues
32 distinct, but general basis invariance even more difficult to deal with. In Appendix C.2, we show that higher dimensional eigenspaces are abundant in real datasets; for instance, 64% of molecule
34 graphs in the ZINC dataset have higher dimensional eigenspace.
In this work, we address the sign and basis ambiguity problems by developing new neural networks
36 SignNet and BasisNet. Our networks are universal and can approximate any continuous function
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

37 of eigenvectors with the proper invariances. Moreover, our networks are theoretically powerful Feldman et al., 2022]. Experiments representations, and texture reconstruction on triangle meshes illustrate the empirical benefits of our models' approximation power and invariances.
38 for graph representation learning than can approximate spectral graph convolutions and compute powerful spectral invariants, which allows our networks to express graph properties like subgraph 40 counts that message passing neural networks cannot. Finally, Laplacian eigenvectors with SignNet and BasisNet can approximate many previously proposed graph positional encodings, including those
41
42 based on random walks [Li et al., 2020, Dwivedi et al., 2022] and heat kernels [Mialon et al., 2021,
molecular graph regression tasks, learning expressive graph
44
2 Sign and Basis Invariant Networks
47 For an n x n symmetric matrix, let A ... An be the eigenvalues and .1....: Un the corre-
eigenvectors partitioned by eigenvalue
49 sponding eigenvectors, which we may assume 50 to form orthonormal basis. For instance, could consider the normalized graph Laplacian where A E =R"X is the adjacency matrix and D is the diagonal degree matrix of some underlying graph. For undirected graphs, L is symmetric. Nonsymmet- 56 ric matrices can be handled very similarly, as we show in Appendix B.I. Our goal is parame- terize a class models / (u1,..., 0&) taking k cigenvectors as input in a manner that respects the cigenvector symmetries.
permutation matrix
kxk block diagonal rotation matrik
51
52 =
D-12AA
Q2
54
57
58
Figure 1 Symmetries of eigenvectors of sym- metric matrix with permutation symmetries (e.g. graph Laplacian). A neural network applied to the eigenvector matrix (middle) should invariant or equívariant to permutation of the rows (left product with permutation matrix P) and invariant to the choice of eigenvectors in each eigenbasis (right product with a block diagonal orthogonal matrix Diag(Q1, Q2 Qa)).
59
80
Sign invariance. For any of the us the sign flipped -u 12 is also an eigenvector, so a function R + RR (where is arbitrary output dimension) should be sign invariant:
62
64
f(11,..., vx) (8101,..-. SkaRk
(1)
65
for all sign choices 8, E 1). That is, we want f to be invariant to the product group 1-1, 1}a. This captures all eigenvector symmetries if the eigenvalues A, are distinct.
66
Basis invariance. If the eigenvalues have higher multiplicity, then there are further symmetries. 69 Let Vi...., V/2 be bases of eigenspaces-i.e. V, [U; columns and spans the eigenspace associated with the shared eigenvalue 14; = >; = Xia,,-
66
Via, RR has orthonormal
70
71
Any other orthonormal basis that spans the eigenspace is of the form ViQ for some orthogonal
72 Q E (d,) C I24 (see Appendix F.2). Thus, function f R Eis d; + E that is invariant to
changes of basis in each eigenspace satisfies
f(V....., Vi) = f(V'). VIQU), Q E Od.))
(2)
The number of eigenspaces I and the dimensions d; may vary between matrices; we account for this in Section 2.2. As O(1) (-1,1), sign invariance is special case of basis invariance when all eigenvalues are distinct.
In other words, is invariant to the product group O(d,) x...
x (dd).
75
76
77
Permutation equivariance. For GNN models that output node features or node predictions, one typically further desires f to be invariant equivariant to permutations of nodes, i.c., along the entries (or rows) of each vector. Thus, for f gn + guxd, we typically also require f(PV,..... PVi) = P Pf(V,.... Vi) for any permutation matrix P _x Figure/ 1 illustrates the full setup.
79
81
Graph Positional Encodings. major motivation for processing eigenvector input is for graph positional encodings, which are additional features appended to each node in graph that give information about the position of that node in the graph. These additional features are crucial for
82
85
84 generalizing Transformers to graphs, and also have been found to improve performance of GNNs.
85 Figure 2 illustrates standard pipeline and the use of our SignNet within it: the input adjacency, node features, and eigenvectors of graph used to compute prediction about the graph. Laplacian

---

87 eigenvectors are processed before being fed into this prediction model. Laplacian eigenvectors
86 have been widely used as positional encodings, and many works have noted that sign and/or basis invariance must be dealt with in this case [Dwivedi and Bresson, 2021, Beaini et al., 2021, Dwivedi al., 2020, Kreuzer et al., 2021, Mialon al., 2021, Dwivedi al., 2022].
90
Graph Adjacency
Prediction Model
A
(n
NN
Node
Features
X
(n
SignNet
Laplacian Eigvecs xn
p
+ Φ
+
Figure 2: Pipeline for using node positional encodings. After processing by our SignNet, the learned positional encodings from the Laplacian eigenvectors are added as additional node features of an input graph. These positional encodings along with the graph adjacency and original node features are passed to prediction model (e.g. GNN). Not shown here, SignNet can also take in eigenvalues and node features if desired.
2.1 Warmup: Neural Networks on One Eigenspace
92 Before considering the general setting, we design neural networks that take a single eigenvector or eigenspace input and are sign basis invariant. These single subspace architectures will become building blocks for the general architectures. For one subspace, a sign invariant function is merely an function, and is easily parameterized.
94
98
Proposition A continuous function h 12n R sign invariant if and only if h(u) = σ(v) + o(-v)
(3)
97 for some continuous Φ I + R A continuous h IR" - RR" is sign invariant and permutation equivariant if and only if (3) holds for a continuous permutation equivariant Φ IR" R
98
99 In practice, we parameterize & by neural network. Any architecture choice will ensure sign invariance, while permutation equivariance can be achieved using elementwise MLPs (Multi-Layer Perceptrons), DeepSets [Zaheer et al., 2017], Transformers [Vaswani et al., 2017], or GNNs.
100
101
102 Next, we address basis invariance for a single d-dimensional subspace, i.e., we aim to parameterize maps h x R that are (a) invariant right multiplication by Q E Odd) and (b) equivariant permutations along the axis. For (a), use the mapping V - VVT from V to the orthogonal projector of its column space, which is (dd) invariant. Mapping V + VVT does not lose information if treat V equivalent VQ for any Q (d). This is justified by the classical first fundamental theorem of ((d) [Kraft and Procesi, 1996], which has recently been applied in machine learning by Villar et al. [2021].
103
105
107
108
Regarding (b), permuting the rows of V permutes rows and columns of VV E Rn Hence, we desire the function á " R VVT be equivariant both and column permutation: @PPV PT) = PO(VVT) To parameterize such a mapping from matrices to vectors, we use an invariant graph network (IGN) [Maron et al., 2018] neural network mapping to and from tensors of arbitrary order T -> R that has the desired permutation equivariance. We thus parameterize family with the requisite invariance and equivariance as follows:
109
111
113
114
h(V) IGN(VVT).
Proposition 2 states that this architecture universally approximates (dd) invariant and permutation equivariant functions. The full approximation power requires high order tensors to used for the IGN; in practice, restrict the tensor dimensions for efficiency, discussed in the next section.
116

---

Proposition 2. Any continuous, ((d) invariant h R - IR' is of the form h(V) = ) a continuous c). For compact domain 2 C Raxd, maps of the form V + IGN(VVT) universally approximate continuous h : 2 Raxd + R" that are O(d) invariant and permutation equivariant.
118
119
120
121
2.2
Neural Networks on Multiple Eigenspaces
122
models oi (V) as building blocks for model on multiple eigenspaces. To do so, we use functions of the form ,(V,,..,, Vi) = p( (Vi), (Vi)), i.e., we first process each eigenspace individually with an invariant network, and then aggregate them via function p. This approach is grounded in a general decomposition theorem for product spaces that
Next, we use the
125
124
125
126
we prove in Section A.
SignNet. We parameterize our sign invariant network f Ruxk R on eigenvectors V1 01..... Uk as
127
f(n,,... v&) (ld(us) + ~ )(=1)
(5)
128
where & and p are unrestricted neural networks, and [:]s denotes concatenation of vectors. The form ((v,) + ((-u)) induces sign invariance for each eigenvector. Since we do not yet impose permutation equivariance here, we term this model Unconsttraineed-SSguane
130
To obtain a sign invariant and permutation equivariant f that outputs vectors in R*x*, we restrict ø and P to be permutation equivariant networks from vectors to vectors, such as elementwise MLPs, DeepSets [Zaheer et al., 2017], Transformers [Vaswani et al., 2017], or most standard GNNs. We name this permutation equivariant version SignNet. If desired, we can additionally use eigenvalues A and node features X E _xx by adding them as arguments to Ø:
132
134
f(r)...... U,, A ARe X) = (lo(0;, X, X) + o(-ci, X)]
(6)
BasisNet. For basis invariance, let V, E Rand, be an orthonormal basis of de dimensional eigenspace. Then we parameterize our Unconstrained-Baat Baiieedee--aitttttttt f by
136
137
f(V...., Vi) = (VVV, (VVV
138
where each dd, is shared amongst all subspaces of the same dimension d,, and l is the number of eigenspaces (i.e., number of distinct eigenvalues, which can differ from the number of eigenvectors k). As 7 differs between graphs, we may use zero-padding or a sequence model like a Transformer to parameterize p. Again, dd, and are generally unrestricted neural networks. To obtain permutation
139
140
141
equivariance, we make P permutation equivariant and let od, IGNN, IR" + R" be IGNs from matrices to vectors. For efficiency. we will only use matrices and vectors in the IGNs (that is, no tensors in Rn for p > 2), i.e., we use 2-IGN. Our resulting BasisNer is
142
143
f(Vi.... Vi) (IGNa, )VV.)
(8)
145
Batssssive-BasisNet. While we restrict SignNet to only use vectors and BasisNet to only vectors and matrices, higher order tensors are generally required for universally approximating permutation equivariant invariant functions [Keriven and Peyré, 2019, Maron et al., 2019, Maehara and NT, 2019]. Thus, we will consider a theoretically powerful but computationally impractical variant of our model, in which we replace p and IGN, BasisNet with IGNs of arbitrary tensor order. We Universal approximation requires 2(n") sized intermediate
146
147
148
149
150
call this variant Supressive-Basssttee tensors [Ravanbakhsh, 2020]. We study Serressive-BasisNee due its theoretical interest, and to
151
152
juxtapose with the computational efficiency and strong expressive power of SignNet and BasisNet.
For summary of properties and more details about our models, see Appendix B.
154
In the multiple subspace case, we can prove universality of our models through general decomposi- tion theorem, which reduces the multiple subspace case to the single subspace case. See Section A for details; we have temporarily moved this Section in the revision due to space constraints, and we will move this Section into the main paper in the camera-ready version.
155
156
3 Theoretical Power for Graph Representation Learning
159
Next, we establish that our SignNet and BasisNet can compute useful basis invariant and permutation equivariant functions Laplacian cigenvectors for graph representation learning, including: spectral

---

graph convolutions, spectral invariants, and existing graph positional encodings. Expressive Baesssee can of course compute these functions, as universal, but this section shows that the practical invariant architectures SignNet and BasisNet can compute them as well.
162
163
164
3.1
SignNets and BasisNets Generalize Spectral Graph Convolution
For node features X R and eigendeccomposition VAVT, speecrall graph convolution takes the form (V 0,0,y; X = V X, for some parameters 8,, that may optionally be continuous functions h(>:) 02 of the eigenvalues [Bruna et al., 2014, Defferrard et al.,
186
168
2016]. This family includes important functions like heat kernels and generalized PageRanks on graphs [Li et al., 2019]. A spectral GNN is defined as multiple layers of spectral graph convolutions and mode-wise linear maps, e.g. VDiag(02) (2)) (VDiag(0))) ) VV
169
( XWi W2 is a two layer spectral GNN. It can be seen (in Appendix H.1) that spectral graph convolutions are permutation equivariant and sign invariant, and if 0; = (ax;) (i.e. the spectral graph convolution is parametric) they are additionally invariant to a change of bases in each eigenspace.
170
171
172
173
174
Our SignNet and BasisNet can be viewed as generalizations of spectral graph convolutions, as our networks can universally approximate all spectral graph convolutions of the above form. For instance,
SignNet with p(at,.... ,+)) = E Og and ó(v, Ai X) = 1 10,, X directly yields the spectral graph convolution. This is captured in Theorem I, which we prove in Appendix H.1. In fact, we may expect SignNet learn spectral graph convolutions well, according to the principle of algorithmic alignment [Xu et al., 2020] (see Appendix H.1); this is supported by numerical experiments in Appendix J.2, in which our networks outperform baselines in learning spectral graph convolutions.
178
177
178
179
180
181
Theorem 1. SignNet universally approximates all spectral graph convolutions. BasisNet universally
182
approximates all parametric spectral graph convolutions.
183
In fact, SignNet and BasisNet are strictly stronger than spectral graph convolutions; there are functions computable by SignNet and BasisNet that cannot be approximated by spectral graph convolutions or spectral GNNs. One way to see this is through graph isomorphism power, as captured in this next result.
185
187
Proposition 3. There exist infinitely many pairs of non-isomonn -oniisooopppic graphs that SignNet and BasisNet can distinguish, but spectral graph convolutions or spectral GNNs cannot distinguish.
3.2
BasisNets can Compute Spectral Invariants
Many works measure the expressive power of graph neural networks by comparing their power for testing graph isomorphism [Xu et al., 2019, Sato, 2020], or by comparing their ability to compute certain functions graphs like subgraph counts [Chen et al., 2020, Tahmasebi al., 2020]. These works often compare GNNs to combinatorial invariants on graphs, especially the k: t-Weisfeileer-Lehman (k-WL) tests of graph isomorphism [Morris et al., 2021].
191
182
199
194
195 While we may also compare with these combinatorial invariants, as other GNN works that use spectral information have done [Beaini et al., 2021]. we argue that it is more natural to analyze our networks in terms of spectral invariants, which are computed from the eigenvalues and eigenvectors of graphs There is rich literature of spectral invariants from the fields of spectral graph theory and complexity theory [Cvetković et al., 1997]. A spectral invariant must be invariant to permutations and changes of basis in each eigenspace, a characteristic shared by our networks.
197
199
201
The simplest spectral invariant is the multiset of eigenvalues, which we give as input to our networks. Another widely studied, powerful spectral invariant is the collection of graph angles, which are defined as the values aij = VIV,V, ezll2. where V/ E R an orthonormal basis for the ith adjacency matrix eigenspace, and E; is the jth standard basis vector, which is zero besides one in the jth component. These are easily computed by our networks (Appendix H.3), so our networks inherit the strength of these invariants. We capture these results in the following theorem, which also lists& a few properties that graph angles determine [Cvetković, 1991].
202
203
205
207
Theorem 2. BasisNet universally appreximates the graph angles auj- The eigenvalues and graph
angles (and thus BasisNet) can determine the number of length 3, 4, or 5 cycles, whether a graph is connected, and the number of length k closed walks from any vertex to itself.
209
5

---

Relation to WL and message passing. In contrast to this result, message passing GNNs are not able to express any of these properties (see [Arvind et al.. 2020. Garg al., 2020] and Appendix H.3). Although spectral invariants are strong, Fürer [2010] shows that the eigenvalues and graph angles
212
214
well as some strictly stronger spectral invariants are not stronger than the 3-WI. test (or, equivalently, the 2-Folklore-Wi test). Future work could study the combination of spectral invariants or spectral
215
216
graph positional encodings with combinatorial algorithms and graph neural networks.
217
3.3
SignNets and BasisNets Generalize Existing Graph Positional Encodings
218
Many graph positional encodings have been proposed, without any clear criteria on which to choose for a particular task. We prove (in Appendix H.2) that our efficient SignNet and BasisNet can universally approximate many previously used graph positional encodings, because we unify these positional encodings by expressing them as either spectral graph convolution matrix or the diagonal of spectral graph convolution matrix.
219
220
222
223
Proposition 4. SignNet and BasisNet universally approximate node positional encodings based on
heat kernels [Feldman al., 2022] and random walks (Dwivedi al., 2022]. BasisNet universally approximates diffusion and p-step random walk relative positional encodings [Mialon et al., 2021], and generalized PageRank and landing probability distance encodings [Li et al., 2020).
225
227
We note that diagonals of spectral convolutions are used as feature descriptors in the shape analysis literature, such the heat kernel signature [Sun et al., 2009] and wave kernel signature [Aubry
229
et al., 2011]. 1]. In the language of recent works in graph machine learning, these are node positional encodings computed from discrete Laplacian of triangle mesh. This connection appears to be unnoticed in recent works on graph positional encodings.
231
Experiments
232
We demonstrate the strength of our networks in various experiments. Appendix B shows simple pseudo-code and a diagram detailing the use of SignNet as node positional encoding.
234
235
4.1
Graph Regression
Table I: Results on the ZINC dataset with a 500k parameter budget. All models use edge features. Numbers are the mean and standard deviation over runs, each with different seeds.
Base model
Positional encoding
k
#param
Test MAE (1)
No PE
N/A
192k
0.25220.00
LapPE (flip)
8
492k
0.198
LapPE. (abs.)
492k
0.20440.00m
GatedGCN
LapPE (can.)
505k
0,298
SignNet (o(v) only)
8
495k
0,148
SignNet
8
495k
0.121
SignNet
All
491k
0.100 0.007
No PE
N/A
473k
0.283
LapPE (flip)
16
487k
0.223
Sparse Transformer
SignNet
479k
0.115 0000
SignNet
All
486k
0.102
No PE
N/A
470k
0.170=2.002
LapPE (flip)
16
470k
0.178
GINE
SignNet
16
470k
0.147
SignNet
All
417k
0.102
No PE
N/A
474k
0.133
LapPE (flip)
474k
0.132
PNA
SignNet
476k
0.105
SignNet
AlI
487k
0.0844..00m
296 study the effectiveness of SignNet for learning positional encodings (PEs) from the eigenvectors of the graph Laplacian on the ZINC dataset of molecule graphs [lrwin et al., 2012] (using the

---

Table 2: Comparison with SOTA methods on graph-level regression tasks. f denotes domain sppecifcc model. Numbers are test MAE, so lower is better. Best models within a standard deviation are bolded.
ZINC (10K) 4
ZINC-full +
Alchemy (10k) 4
HIMP t [Fey et al., 2020]
+,01
.3644.002
CIN-smal f [Bodnar et al., 2021]
2.44..004
.044..00
CIN f [Bodnar et al., 2021]
.099.000
.022..002
GIN [Xu et al., 2019]
170..002
1.08
.180=.000 008
6-2-GNN [Morris et al., 2020b]
.344 022
.042+.003
.118_.001
6-2-LGNN [Morris et al., 2020b]
306 .44
.045..006 000
.122 003
SpeqNet [Morris et al., 2022]
GNN-IR [Dupty and Lee, 2022]
.137 17
.119=
s. 000
PF-GNN [Dupty ct al., 2021]
.222..01
.111
Recon-GNN [Cotta et al., 2021]
.700.000
.125 #.01
SignNet (ours)
.084 006
.024 003
.113_.002
238
subset of 12,000 graphs from Dwivedi et al. [2020]). We primarily consider three settings: 1) No positional encoding, 2) Laplacian PE (LapPE)-the k eigenvectors of the graph Laplacian with smallest eigenvalues are concatenated with existing node features, 3) SignNet positional features- passing the eigenvectors through SignNet and concatenating the output with node features. We parameterize SignNet by taking & to be a GIN [Xu et al., 2019] and p to be an MLP. We sum over ø outputs before the MLP when handling variable numbers of cigenvectors, so then the SignNet is of
240
242
the form MLP E p(v;) + ((-v,) (see Appendix K.2 for further details). We consider four different base models that process the graph data and positional encodings: GatedGCN [Bresson and Laurent, 2017], Transformer with sparse attention only over neighbours [Kreuzer et al., 2021], PNA [Corso et al., 2020], and GIN [Xu et al., 2019] with edge features (i.e. GINE) [Hu et al., 2020b]. The total number of parameters of the SignNet and the base model is kept within a 500k budget.
244
245
247
240
Table shows the results. For all 4 base models, the PE learned with SignNet yields the best test MAE (mean absolute error) - lower MAE is better. Notably, this includes the cases of PNA and GINE, for which Laplacian PE with simple random sign flipping was unable to improve performance over using no PE at all. Our best performing model is PNA base combined with SignNet, which achieves 0.084 test MAE. Besides SignNet, we consider two non-learned approaches to resolving eigenvector sign ambiguity- lea---aaocccaaaatiiiooo and taking element-wiss absolute values (see Appendix K.2 for details).
250
251
252
253
254
255
Results with GatedGCN show that these alternatives are not more effective than random sign flipping for learning positional encodings. We also consider an ablation of our SignNet architecture where we remove the sign invariance, using simply ([)((((vs))) } Although the resulting architecture is no longer sign invariant, ø still processes cigenvectors independently, meaning that only two invariances (+1) need be learned, significantly fewer than the 2 total sign flip configurations. Accordingly, this nin-sign invariant learned positional encoding achieves test MAE of 0.148, improving over the Laplacian PE (0.198) but falling short of the fully sign invariant SignNet (0.121). In all cases, using all available eigenvectors in SignNet significantly improves performance over using fixed number of eigenvectors. In Appendix J.1, we also show that SignNet improves performance when no edge features are included in the data.
257
259
261
262
263
265
These significant performance improvements from SignNet come with only a slightly higher compu- tational cost, For example, GatedGCN with no PE takes about 8.2 seconds per training iteration on ZINC, while GatedGCN with 8 cigenvectors and SignNet takes about 10.6 seconds; this is only a 29% increase in time, for a reduction of test MAE by over 50%. Also, eigenvector computation time is neglible, we need only precompute and save the eigenvectors once, and it only takes 15 seconds to do this for the 12,000 graphs of ZINC.
267
269
271
Comparison with SOTA. In Table 2, we compare SignNet with sfate-of-the-ar methods on graph- level molecular regression tasks on ZINC (10,000 training graphs), ZINC-full (about 250,000 graphs), and Alchemy [Chen et al., 2019a] (10,000 training graphs). We compare against both methods that use domain-specifi, knowledge about molecules, and domain-agnostic GNNs of various architectures.
272
273
We see that SignNet outperforms all domain-agnostic methods on ZINC and ZINC-full, and within standard deviation of the best domain-specifie method. Our mean score is the second best on
275
7

---

Table Test results for texture reconstruction experiment on cat and human models, following the experimental setting of [Koestler et al., 2022]. We use 1023 eigenvectors of the cotangent Laplacian.
Cat
Human
Method
Params
PSNR
DSSIM
LPIPS
PSNR
DSSIM
LPIPS $
Intrinsic NF
329k
34.25
.099
.189
32.29
.119
.330
Absolute value
329k
34.67
.106
.252
32.42
.132
.363
Sign flip
329k
23.15
1.28
2.35
21.52
1.05
2.71
SignNet
324k
34.91
.090
.147
32.43
.125
.316
Alchemy, and is within standard deviation of the best. We perform much better ZINC (.084) than other state-of-the-art positional encoding methods, like GNN-LSPE (.090) [Dwivedi et al., 2022], SAN (.139) [Kreuzer al., 202 I], and Graphormer (.122) [Ying al., 2021].
278
279
280
4.2
Counting Substructures and Regressing Graph Properties
log MSE
NoPE
0.3
LapPE
-2
Test
0.2
SignNet
Trinngle
4-Cycle
IsConnected
Diameter
Counting Substructures
Graph properties
Figure 3: Counting substructures and regressing graph properties (lower is better). With Laplacian PEs, SignNet improves performance, while sign flip data augmentation (LapPE) is less consistent. Mean and standard deviations reported on 3 runs. All runs use the same 4-layer GIN base model.
Substructure counts (e.g. of cycles) and global graph properties (e.g. connectedness, diameter, radius) are important graph features that are known to be informative for problems in bio- and chemo-informatics [Chen al., 2020, Corso al., 2020]. Following the setting of Zhao et al. [2022], we show that SignNet with Laplacian positional encodings boosts the ability of simple GNNs to count substructures and regress graph properties. We take a 4-layer GIN as the base model for all settings, and for SignNet we use GIN and a Transformer as to handle variable numbers of eigenvectors (see Appendix K.4 for details). As shown in Figure 3, Laplacian PEs with sign-flip data
282
283
285
286
287
augmentation improve performance for counting substructures but not for regressing graph properties, while Laplacian PEs processed by SignNet significantly boost performance all tasks.
289
290
4.3
Neural Fields on Manifolds
291
Discrete approximations to the Laplace- Beltrami operator on manifolds have proven useful for processing data on surfaces, such as triangle meshes [Lévy, 2006]. Recently, Koestler et al. [2022] propose intrinsic neural fields, which use eigenfunctions of the Laplace-Bellramn operator as positional encodings for learning neural fields on manifolds. For generalized eigenfunctions v1, Uk. at point on the surface, they parameterize functions f()) ML.((e) (p), .... (p)))). As these cigenfunctions have sign ambiguity, we use our SignNet to parameterize f(p) MLP( ( (p))
Laplace-Beltrami
292
294
296
6( 6(-v; (p))) ), with p and á being MLPs.
298
Table 3 shows our results for texture reconstruction experiments on all models from Koestler et al. [2022]. The total number of parameters in our SignNet-basee model is kept below that of the original model. We see that the SignNet architecture improves over the original Intrinsic NF model and over other baselines especially in the LPIPS (Learned Perceptual Image Patch Similarity) metric, which
300
302
has been shown to be a typically better perceptual metric than PSNR or DSSIM [Zhang et al., 20]8a].
While we have not yet tested this, we believe that SignNet would allow even better improvements when learning over eigenfunctions of different models, as it could improve transfer and generalization.
304
See Appendix D.I for visualizations and Appendix K.5 for more details.

---

Eigvec 11
((v1)) + 6(-v11)
Eigvec 14
Φ(v1a) + ((-v14)
Figure 4: Cotangent Laplacian eigenvectors of the cat model and first principal component of <(v) <(-c) from our trained SignNet.
306
4.4
Visualization of Learned Positional Encodings
307
To better understand SignNet, we plot the first principal component of @(v) + o(-v) for two eigenvectors on the cat model in Figure We see that SignNet encodes bilateral symmetry and structural information on the cat model. See Appendix D for plots of more eigenvectors and further details.
308
310
Related Work
311
In this section, we review selected related work. A more thorough review is deferred to Appendix E.
Laplacian eigenvectors in GNNs. Various recently proposed methods in graph deep learning have directly used Laplacian eigenvectors as node positional encodings that are input to a neural network that is, c.g., message passing GNN [Dwivedi et al., 2020, 2022]. or some variant of a Transformer that is adapted to graphs [Dwivedi and Bresson, 2021, Kreuzer et al., 2021, Mialon et al., 2021, Dwivedi et al., 2022]. None of these methods address basis invariance, and they only partially address sign invariance for node positional encodings by randomly flipping eigenvector signs during training.
314
315
318
317
Graph positional encodings. Other recent methods positional encodings besides Laplacian cigenvectors. These include positional encodings based on random walks [Dwivedi et al., 2022, Mialon al., 2021, Li al., 2020], diffusion kernels graphs [Mialon et al., 2021, Feldman et al., 2022], shortest paths [Ying et al., 2021, Li et al., 2020], and unsupervised node embedding methods [Wang al., 2022]. In particular, Wang al. [2022]
320
322
Laplacian eigenvectors for relative positional encodings in an invariant way, but they focus on robustness, so they have stricter invariances that significantly reduce expressivity (see Appendix E.2 for more details). These previously used positional encodings are mostly ad-hoc, less general since they can be provably expressed by SignNet and BasisNet (see Section 3.3), and/or are expensive to compute (e.g., all pairs shortest paths).
324
325
326
327
Conclusion and Discussion
328
329
SignNet and BasisNet are novel architectures for processing eigenvectors that are invariant to sign flips and choices of eigenspace bases, respectively. Both architectures are provably universal: they can represent any continuous function with the corresponding invariances. When used with Laplacian eigenvectors as inputs they can provably approximate spectral graph convolutions, spectral invariants, graph properties such as subgraph counts, and a number of other graph positional encodings. These theoretical results are supported by experiments showing that SignNet and BasisNet are highly expressive in practice, and learn effective graph positional encodings that improve the performance of message passing graph neural networks. Initial explorations show that SignNet and BasisNet can be useful beyond graph representation learning, eigenvectors are ubiquitous.
330
332
334
336
338
While we conduct experiments on graph machine learning tasks and particular task on triangle meshes, SignNet and BasisNet should also be applicable to processing eigenvectors in other settings, such recommender systems and tasks in shape analysis. We show significant empirical benefit in the tasks that we consider, but we expect less benefit in cases where node features are sufficient to do well on the task, or the task does not require much sophisticated graph structure information to solve. Moreover, while we primarily consider eigenspaces in this work, sign invariance and basis invariance applies to any model that processes subspaces of a vector space; future work may explore models general subspaces.
329
340
342
344

---

References
348
347
Vikraman Arvind, Frank Fuhlbrücc, Johannes Köbler, and Oleg Verbitsky. On weisfeiler- invariance: Subgraph counts and related graph properties. In Journal of Computer and System Sciences, volume 113, pages 42-59. Elsevier, 2020.
349
350
Mathieu Aubry, UIrich Schlickewei, and Daniel Cremers. The wave kernel signature: A quantum mechanical approach shape analysis. In 2011 IEEE international conference on computer vision workshops (ICCV workshops), pages 1626-1633. IEEE, 2011.
351
352
353
I ászló Babai, Dmitry Y Grigoryev, and David M Mount. Isomorphism of graphs with bounded eigenvalue multiplicity. In Proceedings of the fourteenth annual ACM symposium on Theory of computing, pages 310-324, 1982.
354
Muhammet Balcilar, Guillaume Renton, Pierre Héroux, Benoit Gaüzère, Sébastien Adam, and Paul Honeine. Analyzing the expressive power of graph neural networks in a spectral perspective. In Int. Conference on Learning Representations (ICLR), volume 8, 2020.
357
358
359
Fabian Ball and Andreas Geyer-Schulz. How symmetric are real-world graphs? a large-scale study. Symmetry, 10(1):29, 2018.
380
Dominique Beaini, Saro Passaro, Vincent Létourneau, Will Hamilton, Gabriele Corso, and Pietro
362
Liò. Directional graph networks. Int. Conference on Machine Learning (ICML), pages 748-758. PMLR, 2021.
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation, 15(6):1333-136, 2003.
385
386
Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks. In Int. Conference on Learning Representations (ICLR), volume 10, 2022.
367
368
Filippo Maria Bianchi, Daniele Grattarola, Lorenzo Livi, and Cesare Alippi. Graph neural networks with convolutional arma filters. In IEEE transactions on pattern analysis and machine intelligence. IEEE, 2021.
370
372
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang, Pietro Lio, Guido F Montufar, and Michael Bronstein. Weisfeiler and lehman go cellular: Cw networks. Advances in Neural Information Processing Systems, 34:2625-2640, 2021.
373
374
375
Xavier Bresson and Thomas Laurent. Residual gated graph ConvNets. In preprint arXiv: 17::: 171.0533 2017.
376
Rasmus Bro. Evrim Acar, and Tamara G Kolda. Resolving the sign ambiguity in the singular value decomposition. Journal of Chemometrics: A Journal of the Chemometrics Sociery, 22(2):135-140) 2008.
378
380
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18-42, 2017.
381
382
383
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and deep locally connected networks on graphs. In Int. Conference Learning Representations (ICLR), volume 2, 2014.
385
386
Chen Cai and Yusu Wang. Convergence of invariant graph networks. In preprint 21X1122001.10129, 2022.
387
388
Ines Chami, Sami Abu-al-Haija. Bryan Perozzi, Christopher Ré, and Kevin Murphy. Machine learning on graphs: A model and comprehensive taxonomy. In preprint arXiv:2005.03672 2020.
389
Guangyong Chen, Pengfei Chen, Chang- Yu Hsieh, Chee-Kong Lee, Benben Liao, Renjie Liao, Weiwen Liu, Jiezhong Qiu, Qiming Sun, Jie Tang, et al. Alchemy: A quantum chemistry dataset for benchmarking ai models. arXiv preprint arXiv: 1906. 110..999299777 2019a.
391
10

---

393
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with GNNs. In Advances in Neural Information Processing Systems (NeurIPS), volume 32, pages 1589-15902, 2019b.
394
396
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.
397
398
389
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In Int. Conference on Learning Representations (ICLR), volume 2021.
401
Fan Chung. Spectral graph theory. American Mathematical Soc., 1997.
402
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, pages 13260-13271, 2020.
403
405
Leonardo Cotta, Christopher Morris, and Bruno Ribeiro. Reconstruction for powerful graph rep- resentations. In Advances in Neural Information Processing Systems (NeurIPS), volume 34, 2021.
406
407
408
Dragoš Cvetković. Some comments on the eigenspaces of graphs. Publ. Inst. Math. (BeogrBeegr,)) 50 (64):24-32, 1991.
409
410
Dragoš Cvetković, Peter Rowlinson, and Slobodan Simic. Eigenspaces of graphs. Number 66 in Encyclopedia of Mathematics and its Applications. Cambridge University Press, 1997.
412
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering, In Advances in Neural Information Processing Systems (NeurIPS), volume 29, pages 3844-384 3352, 2016.
414
415
Mohammed Haroon Dupty and Wee Sun Lee. Graph representation learning with individualization and refinement. arXiv preprint urXiv:2203.09141 2022.
416
417
Mohammed Haroon Dupty, Yanfei Dong, and Wee Sun Lee. Př-gnn: Differentiable particle fil- tering based approximation of universal graph representations. In Int. Conference on Learning Representations (ICLR), 2021.
418
420
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs, In AAAI Workshop on Deep Learning on Graphs: Methods and Applications, 2021.
421
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. In preprint arXiv:2003.00982 2020.
423
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. Int. Conference on Learning Representations (ICLR), volume 10, 2022.
425
427
Paul Erdos and Alfréd Rényi. Asymmetric graphs. Acta Math. Acad. Sei. Hungar, 14(295-315):3, 1963.
428
429
Or Feldman, Amit Boyarski, Shai Feldman, Dani Kogan, Avi Mendelson, and Chaim Baskin. Weisfeiler and leman go infinite: Spectral and combinatorial pre-colorings. In preprint
430
431
arXiv:2201.134100 2022.
432
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. In
433
ICLR (Workshop on Representation Learning on Graphs and Manifolds), volume 7, 2019.
434
Matthias Fey, Jan-Gin Yuen, and Frank Weichert. Hicrarchical inter-message passing for learning on molecular graphs. arXiv preprint arXiv:2006. 127 2020.
436
Martin Fürer. On the power of combinatorial and spectral invariants. Linear algebra and its applications, 4323 2010.

---

438
Jean Gallier and Jocelyn Quaintance. Differential geometry and Lie groups: computational perspective, volume 12. Springer Nature, 2020.
439
440
V. K. Garg, S. Jegelka, and T. Jaakkola. Generalization and representational limits of graph neural networks. In Int. Conference on Machine Learning (ICML), 2020.
442
Juan Navarro González and Juan Sancho de Salas. C -e-differentiable spaces, volume 1824. Springer, 2003.
443
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 855 864, 2016.
445
447
Will Hamilton. Graph representation learning. Synthesis Lectures on Artifical Intelligence and Machine Learning, 14(3):1-159, 2020.
Mingguo He, Zhewei Wei, Hongteng Xu, et al. Bernnet: Learning arbitrary graph spectral filters via bernstein approximation. In Advances in Neural Information Processing Systems (NeurIPS), volume 34, 2021.
450
452
Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012.
455
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, pages 22118 2111-22133, 2020a.
455
456
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-traine pre-training graph neural networks. In Int. Conference on Learning Representations (ICLR), volume 8, 2020b.
457
458
Leo Huang, Andrew J Graven, and David Bindel. Density of states graph kernels. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM). pages 289-297. SIAM, 2021.
480
461
John J Irwin, Teague Sterling, Michael M Mysinger, Erin S Bolstad, and Ryan G Coleman. Zinc: free tool discover chemistry for biology. Journal of chemical information and modeling, 52(7):
462
463
1757-1768, 2012.
Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. In Advances in Neural Information Processing Systems (NeurIPS), volume 32, 2019.
465
486
Jinwoo Kim, Sacyoon Oh, and Seunghoon Hong. Transformers generalize deepsets and can be extended to graphs & hypergraphs. In Advances in Neural Information Processing Systems (NeurIPS), volume 34, 2021.
467
468
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 2014.
470
471
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In Int. Conference on Learning Representations (ICLR), volume 5, 2017.
472
473
Lukas Koestler, Daniel Grittner, Michael Moeller, Daniel Cremers, and Zorah Lähner. Intrinsic neural fields: Learning functions manifolds. arXiv preprint 27X11.2203.07967, 2022.
475
Hanspeter Kraft and Claudio Procesi. Classical invariant theory, primer. Lecture Notes., 1996.
476
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Re- thinking graph transformers with spectral attention. In Advances in Neural Information Processing Systems (NeurIPS), volume 34, 2021.
478
479
John M Lee. Smooth manifolds. In Introduction to Smooth Manifolds. Springer, 2013.
Ron Levie, Federico Monti, Xavier Bresson, and Michael M Bronstein. Cayleynets: Graph con- volutional neural networks with complex rational spectral filters. IEEE Transactions on Signal Processing, 67(1):97-109, 2018.
481
12

---

483
Bruno Lévy. haplace-beltrann eigenfunctions towards an algorithm that" understands" geometry. In IEEE International Conference on Shape Modeling and Applications 2006 (SMI '06), pages 13-13. IEEE, 2006.
484
Pan Li, Eli Chien, and Olgica Milenkovic. Optimizing generalized pagerank methods for seed- expansion community detection. In Advances in Neural Information Processing Systems (NeurIPS), volume 32, 2019.
487
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 4465 4478, 2020.
490
Takanori Maehara and Hoang NT. A simple proof of the universality of invariant/equivariant graph neural networks. arXiv preprint 1rXiv:19/00033802, 2019.
493
494
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In Int. Conference on Learning Representations (ICLR), volume 6, 2018
495
496
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. In Int. Conference on Machine Learning (ICML), pages 4363-4371, PMLR, 2019.
497
498
Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton Van Den Hengel. image-based recommendations on styles and substitutes. In Proceedings of the 38th international ACM SIGIR conference on research and development in information retrieval, pages 43-52, 2015.
499
Grégoire Mialon, Dexiong Chen, Margot Sclosse, and Julien Mairal. GraphiT: Encoding graph structure in transformers. In preprint arXiv:2106.0566) 2021.
502
503
Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. In ICML workshop on Graph Representation Learning and Beyond, 2020a.
505
506
Christopher Morris, Gaurav Rattan, and Petra Mutzel. Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings. Advances in Neural Information Processing Systems, 33: 21824-21840, 2020b.
507
508
509
Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M Kriege, Martin Grohe, Matthias Fey, and Karsten Borgwardt. Weisfeiler and leman go machine learning: The story so far. arXiv preprint arXiv:2112.0999000 2021.
510
511
512
Christopher Morris, Gaurav Rattan, Sandra Kiefer, and Siamak Ravanbakhsh. Speqnets: Sparsity- aware permutation--quivariine graph networks. arXiv preprint arXiv:2203. 13913, 2022.
513
514
Arvind Narayanan and Vitaly Shmatikov. De-anonymizing social networks. In 2009 30th IEEE symposium security and privacy, pages 173-187. IEEE, 2009.
Antonio Ortega, Pascal Frossard, Jelena Kovačević, José MF Moura, and Pierre Vandergheynst. Graph signal processing: Overview, challenges, and applications. Proceedings of the IEEE, 106 11880-882. 2018
517
519
Shashank Pandit, Duen Horng Chau, Samuel Wang, and Christos Faloutsos. Netprobe: fast and scalable system for fraud detection in online auction networks. In Proceedings of the 16th international conference World Wide Web, pages 201-210, 2007.
520
522
Pal András Papp. Karolis Martinkus, Lukas Faber, and Roger Wattenhofer. Dropgan: random dropouts increase the expressiveness of graph neural networks. Advances in Neural Information Processing Systems, 34, 2021.
523
524
525
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary Vito,o Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems (NeurIPS), pages 8024-8035. Curran Associates, Inc., 2019.
526
527
$29
13

---

531
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 701-710, 2014.
532
Omri Puny, Matan Atzmon, Heli Ben-Hamu, Edward J Smith, Ishan Misra, Aditya Grover, and Yaron Lipman. Frame averaging for invariant and equivariant network design. In Int. Conference on Learning Representations (ICLR), volume 10, 2022.
535
536
537
Siamak Ravanbakhsh. Universal equivariant multilayer perceptrons. In International Conference on Machine Learning, pages 7996- 8006. PMIR, 2020.
538
539
Kaspar Riesen and Horst Bunke. lam graph database repository for graph based pattern recognition and machine learning. In Joint IAPR International Workshops on Staristical Techniques in Pattern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR), pages 287-297, Springer, 2008
541
545
Raif M Rustamov et al. Laplace-beltrami eigenfunctions for deformation invariant shape representa- tion. In Symposium on geometry processing, volume 257, pages 225-233 2007.
545
Horst Sachs and M Stiebitz. Automorphism group and spectrum of graph. In Studies in pure mathematics, pages 587-604. Springer, 1983.
547
Ryoma Sato. A survey the expressive power of graph neural networks. In preprint 2003::2000,,4078, 2020.
548
Nimrod Segol and Yaron Lipman. On universal equivariant set networks. In Int. Conference
550
Learning Representations (ICLR), volume 7, 2019.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):93 93093399322333 2008
652
553
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. In NeurlPS Workshop on Relational Representation Learning, 2018
554
556
Balasubramaniam Srinivasan and Bruno Ribeiro. On the equivalence between positional node embeddings and structural graph representations. In Int. Conference on Learning Representations (ICLR), 2019.
557
558
559
Jonathan M Stokes, Kevin Yang, Kyle Swanson, Wengong Jin, Andres Cubillos-Ruiz, Nina M Donghia, Craig R MacNair, Shawn French, Lindsey Carfrae, Zohar Bloom-Ackermann, et al. A deep learning approach to antibiotic discovery. Cell, 180(4):688-)) 702, 2020.
560
Jian Sun, Maks Ovsjanikov, and Leonidas Guibas. A concise and provably informative multi-scale signature based on heat diffusion. Computer graphics forum, 1885)13333-1392, 2009.
563
Behrooz Tahmasebi, Derek Lim, and Stefanie Jegelka. Counting substructures with higher-order graph neural networks: Possibility and impossibility results. In preprint arXiv:2012.03//2 2020.
565
566
Edric Tam and David Dunson. Multiscale graph comparison via the embedded laplacian distance. In preprint arXiv:2201. 2022.
567
588
Terence Tao and Van Vu. Random matrices have simple spectrum. Combinatorica, 37(3)533--53,
569
2017.
570
Yasuo Teranishi. Eigenvalues and automorphisms of a graph. Linear and Multilinear Algebra, 57()): 577-585, 2009.
571
572
Lloyd N Trefethen and David Bau III. Numerical linear algebra, volume 50. SIAM, 1997.
Anton Tsitsulin, Davide Mottin, Panagiotis Karras, Alexander Bronstein, and Emmanuel Müller. Netlsd: hearing the shape of a graph. In Proceedings of the 24th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 2347-2356, 2018.
574
14

---

578
Fabio Urbina, Filippa Lentzos, Cédric Invernizzi, and Sean Ekins. Dual use of artificial- intelligeece- powered drug discovery. Nature Machine Intelligence, 4(3):189-191, 2022.
577
578
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems (NeurIPS), volume 30, pages 5998-6008 2017.
578
580
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. Inl. Conference on Leurning Representations (ICLR), volume 6, 2018.
582
584
Saurabh Verma and Zhi-Li Zhang. Hunt for the unique, stable, sparse and fast feature learning on graphs. In Advances in Neural Information Processing Systems (NeurIPS), volume 30, pages 88 18-98,22 2017.
585
586
587
Soledad Villar, David Hogg, Kate Storey-Fisher, Weichi Yao, and Ben Blum-Smith. Scalars are universal: Equivariant machine learning. structured like classical physies. In Advances in Neural Information Processing Systems (NeurIPS), volume 34, 2021.
589
Ulrike Von Luxburg. A tutorial on spectral clustering. Statistics and computing, 17(4):395-416 2007.
591
592
Haorui Wang, Haoteng Yin, Muhan Zhang, and Pan Li. Equivariant and stable positional encoding for more powerful graph neural networks. In Int. Conference on Learning Representations (ICLR), volume 10, 2022.
593
594
Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, et al. Deep graph library: A graph-centric, highly-performant package for graph neural networks. arXiv preprint arXhv:190.001315, 2019.
596
2019.
596
Hassler Whitney. The seff-intersections of smooth n-manifold in 2n-space. In Annals of Mathemat- ics, pages
589
1944.
Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. Moleculenet: benchmark for molecular machine learning. Chemical science, 9(2):513-530 2018.
601
602
603
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S Yu. A
comprehensive survey graph neural networks. IEEE transactions neural networks and learning systems, 32(1):4-24, 2020.
605
608
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanne Jegelka. How powerful are graph neural networks? lnt. Conference on Learning Representations (ICLR), volume 7, 2019.
607
608
Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. What neural networks reason about? In Int. Conference Learning Representations (ICLR), volume 8, 2020.
610
Pinar Yanardag and SVN Vishwanathan. Deep graph kemels. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pages 1365-1374, 2015.
612
614
Chengxuan Ying. Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie- Yan Liu. Do transformers really perform badly for graph representation? In Advances in Neural Information Processing Systems (NeurIPS), volume 34, 2021.
615
616
617 Jiaxuan You, Jonathan M Gomes-Selman, Rex Ying, and Jure Leskovec. awaree graph neural networks. In Association for the Advancement of Artificial Intelligence (AAAI), volume 35, pages 10737-10745, 2021.
619
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.
621
15

---

623
Jiawei Zhang, Haopeng Zhang, Congying Xia, and Li Sun. Graph-BERT: Only attention is needed for learning graph representations. In preprint XXi1:20010051400, 2020.
624
625
Richard Zhang, Phillip Isola, Alexei A Efros, Eli Shechtman, and Oliver Wang. The unreasonable effectiveness of deep features as a perceptual metric. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 586-595, 201 8a.
626
627
Zhen Zhang, Mianzhi Wang, Yijian Xiang, Yan Huang, and Arye Nehorai. RetGK: Graph kernels based on return probabilities of random walks. In Advances in Neural Information Processing Systems (NeurIPS), volume 31, pages
629
630
3974, 2018b.
Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any GNN with local structure awareness. Int. Conference on Learning Representations (ICLR), volume 10, 2022.
632
Checklist
634
635
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] We support the claims with theoretical and/or empirical evidence.
637
638
639
(b) Did you describe the limitations of your work? [Yes] We discuss some limitations in the conclusion.
640
641
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Appendix B.2.
642
643
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] We have read the guidelines; our paper conforms to them.
644
845
2. If you are including theoretical results...
646
(a) Did you state the full set of assumptions of all theoretical results? [Yes] We state all assumptions either in the main text or in the appendix.
647
648
(b) Did you include complete proof' of all theoretical results? [Yes] We include all proof's
649
in the appendix.
650
3. If you ran experiments...
651
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or URL)? [Yes] We include experimental code and instructions on the usage.
653
654
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] We try to give most experimental details in the main paper and appendix.
655
656
657
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] We report standard deviations for multiple runs and/or seeds for graph-level tasks, but not the texture reconstruction task.
658
659
680
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix K.
661
4. If you using cxisting assets (c.g., code, data, models) or curating/releasing new assets...
663
(a) If your work uses existing assets, did you cite the creators? [Yes] We cite the creators of software libraries, data, and machine learning models.
664
685
(b) Did you mention the license of the assets? [Yes] See Appendix K.
686
(c) Did you include any new assets either in the supplemental material or as URL? [Yes]
687
We provide our code. We will also link to an open source version after anonymous review.
668
669
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [Yes] See Appendix K.
670
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [Yes] Yes, we discuss this in Appendix K.I; the data most likely does not have personally identifiable information or offensive content.
672
16

---

674
5. If you used crowdsourcing conducted research with human subjects...
675
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A] No crowdsourcing human subjects used.
677
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A] No crowdsourcing or human subjects used.
679
680
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A] No crowdsourcing human subjects used.
17

---

A
Universality for Multiple Spaces
682
683
We have temporarily moved this section to the Appendix due to space constraints, we will move back to the main paper in the camera-ready version.
684
685
While the networks introduced in the Section 2.2 possess the desired invariances, is not immediately obvious whether they are powerful enough to express all functions with these invariances. The universality of our architectures follows corollary of the following general decomposition result, which may enable construction of universal architectures for other invariances as well.
686
687
688
689
Theorem 3 (Decomposition Theorem). Lel , Ns. be lopological spaces, and let G; be group acting X; for each We assume mild topological conditions on X; and G; hold. For any continuous = X1 x x... x Xx + Re that is invariant to the action of G = G1 x x Gk. there exists continuous &ú and continuous p= 2 RR -> IR such that
680
681
f(v1...... .........00 vk)
..... Φx(U))).
(9)
Furthermore: (1) each d; can be taken to be invariant G (2) the domain Z of p compact if each 694
X, is compact, (3) if X = X3 and G, = Gj. then @; can be taken to equal to Φ.-
This result says that when a product of groups G acts product of spaces X' for invariance the product group G it suffices to individually process each smaller group G; on X; and then aggregate the results. Along with the proof of Theorem 3, the mild topological assumptions Appendix G.I. The assumptions hold for sign invariance and basis invariance. By applying this theorem, can prove universality of our networks:
696
explained in
698
689
Corollary 1. Unconstrained- Siionstrrined-SignNeeer can represent any sign invariant function and Unconstrained- Expressive-BasisNet
701
BasisNet can represent any basis invariant function. Expressive- BasisNet a universal approximator of functions that are both basis invariant and permutation equivariant.
703
This result shows that Unconstrained SheoonttrineddSSgnNee,,,, Unconstrained -Bttsseet and Expressive- Expressive-aasisNet take the correct functional form for their respective invariances (proofs in Appendix G.2). Note that Serressvve-BasiSMee approximates all sign invariant functions as special case, by treating all inputs as one dimensional eigenspaces. Accompanying the decomposition result, we show corresponding universal approximation result (proof in Appendix G.3). Similarly to Theorem 3,
704
705
708
707
708
the problem of approximating G G1 x ... G₁ invariant functions is reduced approximating
709
several G inviaiiia functions.
B More Details on SignNet and BasisNet
Table 4: Properties of our architectures: Unconstrained-SignNee SignNet, eecconstriine-Baassshae and Saaressive-BasisMee The properties are: permutation equivariance, universality (for the proper class of continuous invariant functions), and computational tractability.
Unconstr-SignNe SignNet Unconstr. -assisNe
BasisNet
Expr. Expr.BaasiNNet
Permutation equiv.
Universal Tractable
711 In Figure 2, we show a diagram that describes how SignNet is used as a node positional encoding for a graph machine learning task. In Table 4, we compare and contrast properties of the neural architectures that we introduce. In Figure we give pseudo-code of SignNet for learning node positional encodings with a GNN prediction model.
712
713
714
B.1
Generalization Beyond Symmetric Matrices
716
the main paper, we assume that the eigenspaces come from a symmetric matrix. This holds for many cases of practical interest, as e.g. the Laplacian matrix of undirected graph is symmetric. However,
718
we may also want to process directed graphs, or other data that have associated nonsymmetric matrices.
Our SignNet and BasisNet generalize in straightforward way to handle nonsymmetric diagonalizable
18

---

PyTorch-lik -ike pscudo-code for SignNet
class Signket (mn.Muuuuelleee)
def Limi __iiitt__eeef, d, D1, D2, out_dim):
self self.phi phi = GIN(1, D1) # in dim=1, out dim=D1
rho (K41, D2)
self base_maaeas sadel_ CNN(d4D2, out_dim)
def forward(salf, & x, eigvecs):
g contains graph information
shape: aigveca shape: n.x.
n, Higvecs.chape
eigvecs eigvecs reehaae (n, k, 1)
self-phi eigvecs) + self selffphi (si eeggeecs) pe pe pe.reshape -1) # manka D1 K4D1
pe seef (pe)
return self base base_model x, pe)
Figure 5: PyTorch-like pseudo-code for using SignNet with GNN prediction model, where eb GIN and p = MLP as in the ZINC molecular graph regression experiments. Reshaping eigenvectors from
k 1 allows ø to process each eigenvector (and its negation) independently in PyTorch-like deep learning libraries.
matrices, detail here. Let A E R=x" be matrix with diagonalization A = VAV-1 where = Diag(Ai..... .nn) contains the eigenvalues A; and the columns of = [0] Un are eigenvectors. Suppose want learn function the eigenvectors 01,-.... Mt. Unlike in the
721
723
symmetric matrix case, the eigenvectors are not necessarily orthonormal, and both the eigenvalues
724
and eigenvectors can be complex.
725
Real eigenvectors. First, we assume the eigenvectors e; are all real vectors in R" We can take the eigenvectors be real if A is symmetric, or if A has real cigenvalues (see Horn and Johnson [2012] Theorem 1.3.29). Also, suppose that we choose the real numbers R as our base field for the vector space in which eigenvectors lie. Note that for any scaling factor
727
R \ {0} and eigenvector we have that cv is an eigenvector of the same eigenvalue. the eigenvalues are distinct, then the
729
eigenvectors of the form are the only other eigenvectors in the same eigenspace u. Thus,
731
want a function to be invariant to scalings:
f(r1. 2k) f(c C&UL)
c; E RR (0).
(10)
732
This can handled by SignNet, by giving unit normalized vector inputs:
f(r vx) (ló(u;/ -(-
(11)
733
Now, say have bases of eigenspaces Vi...., V/2 with dimensions di...., dj. For basis V,, we have that any other basis of the same space can be obtained V.W for some W GLR (LR,d.), the set of
734
real invertible matrices in Rd,, xd: Indeed, the orthonormal projector for the space spanned by the
columns of V; is given by VI(V, VV)--V' Thus, if Z E nadd: is another basis for the column
736
space of V4, we have that VVVV V.) V/)-'v," = 2(Z 2) -12
737
VIVV. V/) -V, VTT 2(7 Z) zT
(12)
so let W -IT,V-VVTL E gd,xd, Note that W invertible, because it has inverse (Z Z)= 1 ZTV, so indeed V.W Z for W GLR (d.). Thus, basis invariance in this case is
738
740
of the form
S(V..., Vi) -VWVV VWW) W. E GLa(d.).
(13)
Note that the distinct eigenvalue invariance is special case of this invariance, as GR(11 = R \ {0). We can again achieve this basis invariance by using BasisNet, where the inputs the Φd. are orthogonal projectors of the corresponding eigenspace:
742
743
S(V....., Vi) = (lou (V.(VTVV) (V))...))......) I........
(14)
19

---

744
Recall that if V; is an orthonormal basis, then the orthogonal projector is just V.V,', so this is a direct generalization of BasisNet in the symmetric case.
745
746
Complex eigenvectors. More generally, suppose V E C are complex eigenvectors, and we take the base field of the vector space to be C. The above arguments generalize the complex case; in the case of distinct eigenvalues, we want
748
f(FI...., Uk)
((UU
C; E C (O).
(15)
749
However, this symmetry can not be as easily reduced to a unit normalization and a discrete sign invariance, as it can be in the real case. Nonetheless, the basis invariant architecture directly generalizes, so we can handle the case of distinct cigenvalues by a more general basis invariant architecture as well. The basis invariance
750
751
752
f(V fV.,,,...., V(W) W2 E GL)(d:).
(16)
753
The orthogonal projector of the image of V; V.(V;V 'V, where there are now conjugate transposes replacing the transposes. Thus, BasisNet takes the form:
754
f(V Vi) =
(17)
755
B.2
Broader Impacts
756
We believe that our models and future sign invariant or basis invariant networks could be useful in wide variety of applications. As cigenvectors arise in many domains, it is difficult to predict the uses of these models. We test several molecular property prediction tasks, which have the potential for much positive impact, such as in drug discovery [Stokes et al., 2020]. However, recent work has found that the same models that use for finding beneficial drugs can also be used to design biochemical weapons [Urbina et al., 2022]. Another major application of graph machine learning in social network analysis, where positive (e.g. malicious node detection [Pandit et al., 2007]) and negative (e.g. deanonymization [Narayanan and Shmatikov, 2009I) uses of machine learning possible. Even if there is negative intent, bias in learned models can differentially impact particular subgroups of people. Thus, academia, industry, and policy makers must be aware of such potential negative uses, and work towards reducing the likelihood of them.
757
759
761
763
785
788
C
More on Eigenvalue Multiplicities
787
788
In this section, we study the properties of cigenvalues and eigenvectors computed by numerical algorithms on real-world data.
789
770
C.1
Sign and Basis Ambiguities in Numerical Eigensolvers
771
When processing world data, we use eigenvectors that are computed by numerical algorithms. These algorithms return specific eigenvectors for each eigenspace, there is some choice of sign or basis of each eigenspace. The general symmetric matrix eigensolvers numpy llnallg.ee.. eigh and scipy. 1 lliallg.eiiie symmetric matrix A, they first decompose it as = nal T, then they compute the cigendccomposition of T' W WW so the eigendecomposition of A is A = (QW)A(W (AATTQQ) (Q"). There are multiple ambiguities here: for diagonal sign matri-
773
both call LAPACK routines. They both proceed follows: for
775
for orthogonal Q and tridiago-
778
777
ces S = Diag(s1, sn) and S' Diag(s 5n)). where s E (1,, we have that A = QS QSST is also valid tridiagonalizattoon, QS is still orthogonal, SS 1, and STS
778
779
is still tridiagonal. Also, T (WS')A is valid cigendecomposition T. as S" is still orthogonal.
781
782 In practice we find that the general symmetric matrix eigensolvers numpy wwlallgnnggg.... eigh and scipy. www.alnnll....m eigh differ between frameworks but are consistent with the same framework. More specifically, for a symmetric matrix A, we find that the eigenvectors computed with the default settings numpy tend to differ by a choice of sign or basis from those that are computed with the default settings in scipy. On the other hand, the called LAPACK routines are deterministic, so the eigenvectors returned by numpy are the same in each call, and the eigenvectors returned by seipy are
783
784
785
787
likewise the same in each call.
20

---

Table 5: Eigenspace statistics for datasets of multiple graphs. From left to right, the columns are: dataset name, number of graphs, range of number of nodes per graph, largest multiplicity, and percent of graphs with an eigenspace of dimension 1.
Dataset
Graphs
# Nodes
Max. Mult
% Graphs mult. > 1
ZINC
12,000
9-37
9
64.1
ZINC-full
249,456
6-38
10
63.8
oghg-molhiv
41,127
2-222
42
68.0
IMDB-M
1,500
7-89
37
99.9
COLLAB
5,000
-22
238
99.1
PROTEINS 1,113
426
20
77.3
COIL-DEL 3,900
3-
4
4.00
Eigensolvers for sparse symmetric matrices like boy.lanlgg. eigsh are required for large scale problems. This function calls ARPACK, which uses an iterative method that starts with a randomly sampled initial vector. Due to this stochasticity, the sign and basis of eigenvectors returned differs between each call.
790
792
793
Bro et al. [2008] develops data-dependent method to choose signs for each singular vector of singular value decomposition. Still, in the worst case the signs chosen will be arbitrary, and they do not handle basis ambiguities in higher dimensional eigenspaces. Other works have made choices of sign, such as by picking the sign so that the eigenvector's entries are the largest lexicographic order [Tam and Dunson, 2022]. This choice of sign may work poorly for learning graphs, it is sensitive to permutations on nodes. For some graph regression experiments in Section 4.1, we try choice of sign that is permutation invariant, but we find it to work poorly.
794
795
796
798
C.2 Higher Dimensional Eigenspaces in Real Graphs
Here, we investigate the normalized Laplacian eigenspace statistics of real-world graph data. For any graph that has distinet Laplacian eigenvalues, only sign invariance required in processing eigenvectors. However, we find that graph data tends to have higher multiplicity eigenvalues, so basis invariance would be required for learning symmetry-respecting functions on eigenvectors.
802
804
805
Indeed, we show statistics for multi-graph datasets in Table 5 and for single-graph datasets with more nodes per graph in Table 6. For multi-graph datasets, we consider: :
808
Molecule graphs: ZINC [Irwin et al., 2012, Dwivedi et al., 2020], ogbg-molhiv [Wu et al., 2018, Hu et al., 2020a]
808
809
Social networks: IMDB-M, COLLAB [Yanardag and Vishwanathan, 2015, Morris et al., 2020a).
Bioinformatics graphs: PROTEINS [Morris et al., 2020a]
812
Computer vision graphs: COIL-DEL [Riesen and Bunke, 2008, Morris et al., 2020a].
813
For single-graph datasets, we consider:
814
The 32 x 32 image grid as in Section J.2
815
Citation networks: Cora, Citeseer [Sen et al., 2008]
816
Co-purchasing graphs with Amazon Photo [McAuley et al., 2015, Shchur et al., 2018].
817
We see that these datasets all contain higher multiplicity eigenspaces, so sign invariance insufficient for fully respecting symmetries. The majority of graphs in each multi multi-graph dataset besides COIL- DEL contain higher multiplicity eigenspaces. Also, the dimension of these eigenspaces can be quite large compared to the size of the graphs in the dataset. The single-graph datasets have large proportion of their eigenvectors belonging to higher dimensional eigenspaces. Thus, basis invariance may play large role in processing spectral information from these graph datasets.
818
819
821
21

---

Table 6: Eigenspace statistics for single graphs. From left to right, the columns are: dataset name. number of nodes, distinct eigenvalues (i.e. distinct eigenspaces), number of unique multiplicities, largest multiplicity, and percent of eigenvectors belonging to an eigenspace dimension >
Dataset
Nodes
Distinct
# Mult.
Max Mult.
% Vecs mult.
32 32 image
1,024
513
3
96.9
Cora
2,708
2,187
11
300
19.7
Citeseer
3,327
1,861
12
491
44.8
Amazon Photo
7,650
7,416
8
136
3.71
823
C.3
Relationship to Graph Automorphisms
Higher multiplicity eigenspaces are related to automorphism symmetries in graphs. For adjacency matrix A, the permutation matrix P is an automorphism of the graph associated to A if PAPT A. If P is an automorphism, then for any eigenvector of A with eigenvalue X, we have
825
826
AP P Pv PAv Pλe XPv,
(18)
827
so Pv is eigenvector of A with the same eigenvalue X. If Pv and are linearly independent, then has a higher dimensional eigenspace. Thus, under certain additional conditions, automorphism symmetries of graphs lead to repeated eigenvalues [Sachs and Stiebitz, 1983, Teranishi, 2009].
828
C.4 Multiplicities in Random Graphs
is known that almost all random graphs under the Erdös-Renyi model have no repeated eigenvalues in the infinite number of nodes limit [Tao and Vu, 2017]. Likewise, almost all random graphs under the Erdös- Renyi model are asymmetric in the sense having no nontrivial automorphism symmetries [Erdos and Rényi, 1963]. These results contrast sharply with the high eigenvalue multiplicities that we see in real-world data in Section C.2. Likewise, many types of real-world graph
832
833
834
835
data have been found to possess nontrivial automorphism symmetries [Ball and Geyer-Schulz, 201 8).
837
This demonstrates a potential downside of using random graph models to study real-world data: eigenspace dimensions and automorphism symmetries of random graphs may not agree with those of
839
roal-world data.
22

---

D Visualization of SignNet output
840
D.1 Cat Model Visualization
Eigenvector
o(0i) o(-v1)
Eigenvector
<(vs) (-v))
Eigenvector 11
<(v1) + é(-vri)
Eigenvector 14
@(via) + 6(-v1a)
Figenvector 1023
6(V1023) (1-2))22)
Figure 6: (Left) Cotangent Laplacian eigenvectors of the cat model. (Right) First principal component of ((v) + ((-)) from our trained SignNet.
842
In Figure we plot the eigenvectors of the cotangent Laplacian on a cat model, as well as the first principal component of the corresponding leameed ((v) + ő from our SignNet model that was trained on the texture reconstruction task. Interestingly, this portion our SignNet encodes bilateral symmetry; for instance, while some eigenvectors differ between left feet and right feet, this portion of our SignNet gives similar values for the left and right feet. This useful for the texture reconstruction task, the texture regression target has bilateral symmetry.
843
844
846
23

---

Figure 7: First three principal components of the full SignNet output on the cat model.
848
We also show principal components of outputs for the full SignNet model in Figure 7. This is not as interpretable, as the outputs are high frequency and appear be close the texture that is the regression target. If instead we trained the network on a task involving eigenvectors of multiple models, then may expect the SignNet learn more structurally interpretable mappings (as in the case of the molecule tasks).
819
850
852
D.2 Molecule visualization
854
To better understand SignNet, in Figure we visualize the learned positional encodings of SignNet with o GIN, م MLP (with summation handle variable eigenvector numbers) trained on ZINC as in Section 4.1. SignNet learns interesting structural information such as min-cuts (PC 3) and appendage atoms (PC 2) that qualitatively differ from any single eigenvector of the graph.
856
858
For this visualization we use SignNet trained with GatedGCN base model on ZINC, as in Section 4.1. This SignNet uses GIN as & and p an MLP (with sum before it to handle variable numbers of eigenvectors), and takes in all eigenvectors of each graph. See Figure 8 for all of the eigenvectors of fluorescein.
860
862
E
More Related Work
E.1
Graph Positional Encodings
864
Various graph positional encodings have been proposed, which have been motivated for increasing ex- pressive power practical performance of graph neural networks, and for generalizing Transformers to graphs. Positional encodings are related to so-called position-aware network embeddings [Chami al., 2020], which capture distances between nodes in graphs. These include network embedding methods like Deepwalk [Perozzi et al., 2014] and node2vec [Grover and Leskovee, 2016), which have been recently integrated into GNNs that respect their invariances by Wang et al. [2022]. Further, Li
866
867
868
869
870
et al. [2020] studies the theoretical and practical benefits of incorporating distance features into graph neural networks. Dwivedì et al. [2022] proposes method to inject Iearnable positional encodings into each layer of a graph neural network, and uses simple random walk based node positional encoding.
871
872
You et [2021] proposes node positional encoding diag(A) (A*), which captures the number of closed walks from a node to itself. Dwivedi et al. [2020] propose to use Laplacian eigenvectors as positional encodings in graph neural networks, with sign ambiguities alleviated by sign flipping data augmentation. Srinivasan and Ribeiro [2019] theoretically analyze node positional embeddings and structural representations graphs, and show that most-expressive structural representations contain the information of any node positional embedding.
873
874
875
877
879
While positional encodings sequences as used for Transformers [Vaswani et al., 2017] are able to leverage the canonical order in sequences, there is no such useful canonical order for nodes in graph, due in part to permutation symmetries. Thus, different permutation equivariant positional encodings have been proposed to help generalize Transformers to graphs. Dwivedi and Bresson [2021] directly add in linearly projected Laplacian eigenvectors to node features before processing these features with a graph Transformer. Kreuzer et al. [2021] propose an architecture that uses attention over Laplacian eigenvectors and eigenvalues to learn node or edge positional encodings. Mialon al. [2021] uses spectral kernels such as the diffusion kernel to define relative positional encodings that
880
881
882
883
884
885
887
modulate the attention matrix. Ying et [2021] achieve ofate-of-the-ard empirical performance with simple Transformers that incorporate shortest-path based relative positional encodings. Zhang
24

---

Eigenvector
Eigenvector
Eigenvector 3
Eigenvector
Eigenvector
Eigenvector
Eigenvector
Eigenvector
Figenvector 9
Eigenvector 10
Eigenvector 11
Eigenvector 12
-as
Eigenvector
Eigenvector
Eigenvector 15
Eigenvector 17
Eigenvector 18
Eigenivector 19
Eigenvector
Eigenvector 21
Eigenvoctor
Eigenvector 23
Eigenvector 24
Figure All normalized Laplacian eigenvectors of the fluorescein graph. The first principal components of SignNet's ' learned positional encodings do not exactly match any eigenvectors.
et al. [2020] also utilize shortest-pale distances for positional encodings in their graph Transformer. Kim et al. [2021] develop higher-order transformers (that generalize invariant graph networks), which interestingly perform well graph regression using sparse higher-order transformers without positional encodings.
890
892
883
E.2
Eigenvector Symmetries in Graph Representation Learning
Many works that attempt to respect the invariances of eigenvectors solely focus on sign invariance (by using data augmentation) [Dwivedi et al., 2020, Dwivedi and Bresson, 2021, Dwivedi et al., 2022, Kreuzer et al., 2021]. This may be reasonable for continuous data, where eigenvalues of associated matrices may be usually distinct and separated (e.g. Puny et al. [2022] finds that this empirically holds for covariance matrices of n--bdy problems). However, discrete graph Laplacians are known to have higher multiplicity eigenvalues in many cases, and in Appendix C.2 we find this to be true in
885
896
887
898
various types of real-world graph data. Graphs without higher multiplicity eigenspaces are easier
900
to deal with; in fact, graph isomorphism can be tested in polynomial time on graphs of bounded
25

---

Eigenvector
Eigenvector 2
Eigenvector 23
Eigenvector
SignNet PC 1
SignNet PC
SignNet PC
SignNet PC
65
Figure 9; Normalized Laplacian eigenvectors and learned positional encodings for the graph of fluorescein. (Top row) From left to right: smallest and second smallest nontrivial eigenvectors, then second largest and largest eigenvectors. (Bottom row) From left to right: first four principal components of the output p((ó(v) + ø( ((-=:)]=11....))) of SignNet. Note: we will put this back the main paper for the camera-ready.
multiplicity for adjacency matrix eigenvalues [Babai et al., 1982], with time complexity that is lower for graphs with lower maximum multiplicities.
903
A recent work of Wang al. [2022] proposes full orthogonal group invariance for functions that process positional encodings. In particular, for positional encodings Z E [R**k they parameterize functions f(2) such that f(Z) = f(ZQ) for all Q E (k)). This indeed makes sense for network embeddings like node2vec [Grover and Leskovec, 2016], as their objective functions are based inner products and are thus orthogonally invariant. While they prove stability results when enforcing full orthogonal invariance for cigenvectors, this is a very strict constraint compared to basis invariance. For instance, when k = and all eigenvectors
905
907
909
used in V, the condition f(V) f(VQ) implies that f is constant function on orthogonal matrices, since any orthogonal VQ for Q = V W E O(n). In other words, for bases of eigenspaces Vi..., Vi and V = VVi
911
912
matrix W can be obtained as
ViJ. Wang et al. [2022] enforces VQ z V. while we enforce / Diagg QQ...........................Q Qi) V. While the columns ViDaa(Q1..... Qi) are still eigenvectors, the columns of VQ generally are not.
914
916
E.3
Graph Spectra and Learning on Graphs
More generally, graph spectra are widely used in analyzing graphs, and spectral graph theory [Chung, 1997] studies the connection between graph properties and graph spectra. Different graph kernels have been defined based graph spectra, which use robust and discriminative notions of generalized spectral distance [Verma and Zhang, 2017], the spectral density of states [Huang et al., 2021], random walk return probabilities [Zhang et al., 2018b], the trace of the heat kernel [Tsitsulin et al., 2018]. Graph signal processing relics on spectral operations to define Fourier transforms, frequencies, convolutions, and other useful concepts for processing data graphs [Ortega et al., 2018). The closely related spectral graph neural networks [Wu et al., 2020, Balcilar et al., 2020] parameterize neural architectures that are based similar spectral operations.
918
920
922
924
926
F
Definitions, Notation, and Background
927
F.1
Basic Topology and Algebra Definitions
We will use some basic topology and algebra for our theoretical results. A topological space (X, set X' along with family of subsets 2 satisfying certain properties, which gives useful notions like continuity and compactness. From now will omit mention of and refer to
329
26

---

931
topological space as the set X' itself. For topological spaces X' and V, we write X' = y and say that X is homeomorphic to if there exists a continuous bijection with continuous inverse from X' to Y. We will say X' y if the underlying sets and topologies are equal as sets (we will often use this notion of equality for simplicity, even though can generally be substituted with homeomorphism).
932
934
925 For function f x -> ) between topological spaces X' and V the image im is the set of values
936 that f takes, im = {f(2) : x E X). This is also denoted f (2²). A function f X + 3 is called a topoloical embedding if it is a homeomorphism from X to its image.
938
group G is set along with a multiplication operation G x G - G. such that multiplication is associative, there is multiplicative identity e G, and each E G has multiplicative inverse g g- topological group a group that is also a topological space such that the multiplication and inverse operations are continuous.
939
940
A group G may act a set X' by a function G x X' + X. We usually denote 9 x as ge. A topologiaal group is said to act continuously on a topological space X' if is continuous. For any group G/ and topological space X, we define the coset Gx = {gx 9 G}. which can be viewed as an equivalance class of elements that can be transformed from one to another by group element. The quotient space X/ X/G (Gx x E } is the of all such equivalence classes, with topology induced by that of X' The quotient map π X - X/G is a surjective continuous map that sends x to its coset, π (zz) Ga.
943
944
945
948
947
948
949
For x E R", || denotes the standard Euclidean norm, By the oo norm of functions f: z + F from compact 2 to a Fuclidean space IR* we mean ||]| sup=ezll/
950
951
F2
Background on Eigenspace Invariances
952
Let V [v1
va] and W- [wo d dimensional subspace of Rt. Since V and W span the same space, their orthogonal projectors
wal E R be two orthonormal bases for the same
953
are the same, so VVT WWT T. Also, since V and W have orthonormal columns, we have
954
955 V V = W W = I gdxd Define Q = V W. Then Q is orthogonal because
Q q=Q=wTTv
W WTWWTW=1
(19)
956
Moreover, we have that
VQ = VV W WW W = W
(20)
957
Thus, for any orthonormal bases V and W of the same subspace, there exists an orthogonal Q E (d) such that VQ = W.
959
For another perspective on this, define the Grassmannian Gr(d, n) as the smooth manifold consisting of all d dimensional subspaces of IR". Further define the Stiefel manifold St(d, n) as the set of all orthonormal tuples [0]
980
va] E Raxdd of d vectors in IR. Letting (dd) act by right multiplication, it holds that (s,
951
a Gr(d, This implies that any O(d) invariant function on St d, n) can be viewed as a function on subspaces. See e.g. Gallier and Quaintance [2020] Chapter for more information on this. We will use this relationship our proofs of universal representation.
982
963
984
965
When we consider permutation invariance or cquivariance, the permutation acts on dimensions of size n. Then a tensor X E IT* xd is called an order l tensor with respect to this permutation symmetry, where order 0 are called scalars, order tensors are called vectors, and order 2 tensors are called matrices. Note that this does not depend on d; in this work, we only ever consider vectors and scalars
966
967
988
with respect to the (d) action.
969
G Proofs of Universality
971 We begin by proving the two propositions for the single subspace case from Section 2.1. Proposition 1. A continuous function h R² + IR is sign invariant if and only if
h(w)= <(v) d(-v)
973 for some continuous Φ) RR
RR + RRa continuous h T - Rh is sign invariant and permutation equivariant if and only if (3) holds for continuous permutation equivariant Φ : 18 - R.
27

---

975 Proof. If h(v) = o(v) + 6 then h is obviously sign invariant. On the other hand, if h is sign invariant, then letting ((v) h(v)/2 gives that h(v) (()) (- and á is of course continuous.
978
977
for a permutation equivariant Φ, then ( Pu) = Φ Po) + (Pu) = Po(- P (( +(-))) Ph(e), so h is permutation equivariant and sign invariant. If h is permutation equivariant and sign invariant, then define ((v)= h(v)/2 2 again; it is clear that ø
If o())
978
979
980
continuous and permutation equivariant.
981
Proposition 2.
Any continuous, (d) invariant h R - ER is of the form h(V) (VVVT) for continuous Φ. For compact domain 2 C Raad maps of the form V + IGN(VVT) universally
982
approximate continuous functions h Z C Raxd + IR" that are O(d) invariant and permutation equivariant.
984
985
The case without permutation equivariance holds by the First Fundamental Theorem of (d) (Lemma 2).
Proof.
986
For the permutation equivariant case, let z' (VVT: V 2} and let e 0. Note that z' is compact, as it is the continuous image of a compact set. Since is O(d) invariant, the first fundamental theorem of O(d) shows that there exists a continuous function o: Z' Baxa R such that h(V) <VVVT). Since h is permutation equivariant, for any permutation matrix P have that
987
988
989
981
= = @(PVV = P P P
(21)
(22)
992
so Ø is a continuous permutation equivariant function from matrices to vectors. Then note that Keriven and Peyré [2019] show that invariant graph networks (of generally high tensor order in hidden layers) universally approximate continuous permutation equivariant functions from matrices to vectors on
994
compact sets of matrices. Thus, IGN can e-approximate é, and hence V + IGN(VVT) can appproximate h.
985
986
987
G.1
Proof of Decomposition Theorem
X1 X x Nx
for
=
1/
π = T1 X T
(ZI/Gi) x Gxz/Ge)
R
1/11
1 = 1 x ... x 1/k
2 im) C R
p 0 -1
Figure 10: Commutative diagram for our proof of Theorem 3. Black arrows denote functions from topological constructions, and red dashed lines denote functions that we parameterize by neural networks (Ø = Φ1 x ... x d2 and p).
998
Here, we give the formal statement of Theorem 3, which provides the necessary topological assump- tions for the theorem to hold. In particular, we only require the G, be a topological group that acts continuously on X₁ for each i, and that there exists a topological embedding of each quotient space into some Euclidean space. That the group action is continuous is very mild assumption, and it holds for any finite or compact matrix group, which all of the invariances we consider in this paper be represented as.
1000
1001
1002
1003
1004
topoloiical embedding of the quotient space into a Fuclidean space is desired, as we know how to parameterize neural networks with Euclidean outputs and inputs, whereas dealing with a quotient
1005
28

---

1006
space is generally difficult. Many different conditions can guarantee existence of such an embedding. For instance, if the quotient space smooth manifold, then the Whimey Embedding Theorem (Lemma 5) guarantees such an embedding. Also, if the base space X; is Fuclidean space and G; is a finite or compact matrix Lie group, then map built from G-invariant polynomials gives such an embedding (González and de Salas [2003) Lemma 11.13).
1007
1008
1009
1010
1011
Figure 10 provides a commutative diagram representing the constructions in our proof.
1012
Theorem 3 (Decomposition Theorem). Let Xi....,&i Ny be topologiaal spaces, and let G2 be
1013
topological group acting continuously on X, for each i. Assume that there is a topological embedding
1014
4/: X./Gr + Ih: of each quotient space into a Euclidean space R for some dimension a;- Then, for any continuous function f x:x= = x x X₂ + R that is invariant to the action of
1015
1016
G G1 x .... Gk, there exists continuous functions di X. - Rai and continuous function
2: C R + IR.", where = =;; (i such that
1017
J(vI,.... uk) - (()) ...., Oz (Ux)).
(23)
1018
Furthermore: (1) each o; can be taken to be invariant to G. (2) the domain Z is compact if each X; is compact, (3) if X; X2 and G; G. then &i can be taken to be equal to 6j.
1019
1020
Proof. Let n. X; - X//C; denote the quotient map for X; // Since each G; acts continuously, Lemma 3 gives that the quotient of the product space is the product of the quotient spaces, i.e. that
1021
(24 x x... \ x ...
Ga) = (X1/ x x (Xx/Gk),
(24)
1022
and the corresponding quotient map : 2// is given by
π = ग X X The
TT.,,..., = (TI(II), Th (x
(25)
By passing to the quotient (Lemma 1), there exists a continuous f X/G + R on the quotient space such that f /= fo a æ. By Lemma 4, each X, X//G; is compact X; compact. Defining the image Z, v. (2//G) C R", we thus know that Z, is compact if X; is compact.
1023
1024
1025
Moreover, as th is a topological embedding, it has a continuous inverse w, on its image Z, Further, we have a topological embedding vé : X/G + Z Z, ... 3n given by 1h di ... tbk.
1026
1027
with continuous inverse w/ = + ... x v/2
1028
1029
Note that
1= j = ( o b (b).)
(26)
1030
So we define
P = f f
P: 2 + R
(27)
8 1/ o n
Φ: : X4 + Z;
(28)
Φ = e o π = Φ1 x... x ΦK
6: + Z
(29)
1031
Thus, f- = poo po (01 x... x dx), so equation (9) holds. Moreover, the p and di are continuous,
1032
as they are compositions of continuous functions. Furthermore, (1) holds as each d; is invariant
1033
to G, because each æ; is invariant to G, Since each 2, is compact if X, is compact, the product
1034
Z 3, x ....& x Z% compact if each X, is compact, thus proving (2).
1035
To show the last statement (3), note simply that if X; X2 and G; = Gj. then the quotient maps are equal, i.e. n. ky. Moreover, we can choose the embeddings be equal, so say vi = 1/.. Then, Φi 3 n. = wi o πīj- = Φj. so we are done.
1036
1037
1038
G.2
Universality of SignNet and BasisNet
1039
Here, we prove Corollary 1 on the universal representation and approximation capabilities of our Unconstrained-SinnNet Unconstrained- Nettsssssss,, and Expressive- BasisNets.. We proceed sev- eral steps, first proving universal representation of continuous functions when we do not require permutation equivariance, then proving universal approximation when we do require permutation equivariance.
1040
1041
1042
1013
29

---

1044
G.2.1
Sign Invariant Universal Representation
Recall that Sn-1 denotes the unit sphere in RT, As we normalize eigenvectors to unit norm, the domain of our functions on l eigenvectors are on the compact space (S"-1)².
1045
1046
Corollary 2 (Universal Representation for SignNet). A continuous function f (8"-13k - R is
1047
1048
sign invariant, iee. (11111,... ,8gU)) [(vi,..., (x)) for any 8, E {-1,1], if and only if there
exists a continuous Φ : IR + 222n-2 and a continuous p (222m222k 2)k - IR. such that
1049
f(ui...., U6) = (lo(u)) + (()=))))
(30)
1050
Proof. It can be directly seen that any f of the above form sign invariant.
1051
Thus, we show that any sign invariant f can be expressed in the above form. First, we show that
1052
can apply the general Theorem 3. The group G; = {1, -1} acts continuously and satisfies that $--1/(1,-1
1053
= |P==11 where RPp-1 is the real projective space of dimension Whitney's embedding theorem states that there exists a (smooth) topological embedding 1/v RIp-- - IR 2- (Lemma 5).
1. Since
1054
RPP--1 is smooth manifold of dimension
1055
Thus, we can apply the general theorem to see that f = p Ø² for some continuous p and J Note that each o; = Φ is the same, as each X; = S- and G, = [1,-1] -1] is the same. Also, Theorem
1056
1057
says that we may assume that @ is sign invariant, so ((x) = Φ0 (r...) Letting 6(x) = ((r)/2, we are
1058
1059
done with the proof.
L
1060
G.2.2
Sign Invariant Universal Representation with Extra Features
1061
Recall that we may want our sign invariant functions process other data besides eigenvectors, such as eigenvalues or node features associated to a graph. Here, we show universal representation for when we have this other data that does not possess sign symmetry. The proof simple extension of
1062
1083
1064
Corollary 2, but we provide the technical details for completeness.
1085
Corollary 3 (Universal Representation for SignNet with features). For compact space of features Ω C Rd, let ['I,,...; Uky I1, ..ll, H&) be a continuous function f (Sn-1 22)* + Rs.
1086
1087
Then f is sign invariant for the inputs on the sphere, i.e.
f(s1V)...., SKUU, L1, II,...,,
Ix) = =f(vI.....
Uk: T1. Ik)
9; E (1, (1,
(31)
and only if there exists a continuous vb R - RR 2 2+d and a continuous p (2 - R
1088
1089
such that
f(ei....,ua) vk) (6(11, 2()v1,2)), ..... (x) + 6(-UU,
(32)
1070
Proof. Once again, the sign invariance of any f in the above form is clear.
1071
We follow very similar steps to the proof of Corollary 2 to show that may apply Theorem 3. We
1072
can view Ω as a quotient space, after quotienting by the trivial group that does nothing, Ω = 1/(11.
1073
The corresponding quotient map is idg, the identity map. Also, Ω trivially topologically embeds in
1074
Rd by the inclusion map.
1075
11 x (1) acts continuously, by Lemma 3 we have that As G.
(S--1 x (0)(((1-11) x {1}) (5--1 /[1, (1)) x (22/(1)) = RP--1 x Q
(33)
with corresponding quotient map π x idg, where π is the quotient map to RP--1
1076
Letting & be the embedding of PM + 2 guaranteed by Whitney's embedding theorem (Lemma 5), we have that = &b x idg an embedding of RPm-1 x Ω - 222d Thus, we can
1077
1078
apply Theorem write f = p o 3 for x = ( ida) o (N idg), so
1079
,(,,,,,) (vx)),,
(34)
where ō(0;, =ō(-v,, x;). Letting o(v,,,, = 2 x. /2, are done.
1080
30

---

1081
G.2.3
Basis Invariant Universal Representation
1082
Recall that St(d, n) is the Stiefel manifold of d-tuples of vectors (UI,..., ea) where E R and 01,.... Ei are orthonormal. This is where our inputs lie, as our eigenvectors are unit norm and orthogonal. We will also make use of the Grassmannian Gr(d, n), which consists of all d-dimensional
1083
1084
1085
subspaces in R". This is because the Grassmannian is the quotient space for the group action we
want, Gr(d, n) = SU,d, (O)), where Q O(d) acts on V E St(d, n) C <Raxd by mapping V to
1086
1087
VQ [Gallier and Quaintance, 2020].
1088
Corollary 4 (Universal Representation for BasisNet). For dimensions di....,dh di S n let f be continuous function on St(d1, n) x... x St(di, n). Further assume that f is invariant to (d1) x
1089
1080
x (z), where (dd acts on St(d;, n) by multiplication on the right.
Then there exist continuous p: 1R= (n-d) - IR and continuous o; : :St(d; n) (22d(nnd.))
1081
1082
such that
S(V,.... Vi) - p (ó) (V)........( where the o; are (dd:) invariant functions, and we can take o; = 2j if dj.
(35)
1093
Proof. Letting X; St(d,, n)) and G; = Odd)). can be seen that G, acts continuously on X, Also, we have that the quotient space Bifd;,n//Of = Gr(d,, n) is the Grassmannian of de dimensional subspaces in R",,, which is smooth manifold of dimension d: d.). Thus, the Whitney embedding theorem (Lemma 5) gives a topological embedding 14y Gr(d,, n) + (2d((a-)).
1094
1085
1086
1097
Hence we may apply Theorem 3 to obtain continuous (d4)) invariant di St(di, n) + (ndd and continuous p= Ei 2d, (n- + TKe, such that f = po ( ... x Φ1). Also, if de = dj. then X = X3 and G; = Gj, so we can take di Dj-
1098
1089
1100
1101
G.2.4 Basis Invariant and Permutation Equivariant Universal Approximation
1102
With the restriction that f(V...., Vi) R"xE. + R be permutation equivariant and basis invari- ant, we need use the impractically expensive Expressive-BasisNel to approximate Universality of permutation invariant or equivariant functions from matrices to scalars or matrices to vectors is difficult to achieve in a computationally tractable manner [Maron al., 2019, Keriven and Peyré,
1103
1104
1105
1106
1107
2019, Maehara and NT, 2019]. One intuitive reason to expect this is that universally approximating
1108
such functions allows solution of the graph isomorphism problem [Chen al., 2019b], which is a computationally difficult problem. While we have exact representation of basis invariant functions by continuous p and &; when there is no permutation equivariance constraint, we can only achieve approximation up to an arbitrary >> O when we require permutation equivariance.
1109
1110
1111
1112
Corollary 5 (Universal Approximation for Expressive Expressive-BasisNets) Let (V Vi) St(d1, n) x x St(d,, n) + R" be continuous, ((dy) X x (dd)) invariant, and permutation equivariant. Then can be c-approximated by an Expressive BassisNet.
1113
1114
1115
Proof. By invariance, Corollary 4 of the decomposition thcorem shows that f can be written as
f(V....., Vi) = p (Pa, (Vi),..., iPd (Vi)
(36)
1116
for some continuous ((4) invariant a and continuous p. By the first fundamental theorem of (d)
(Lemma 2), each Pa, can be written as sa, (V²) Φa (V.V,T) for some continuous Φd,- Let
1117
2 [VVVV
VyyT) V, E St(d; m)) C B
(37)
1118
xSt(di, which is compact as it the image of the compact space St(di, m)x...Xt(dd; under a continuous function. Define h Z C "x= + R" by
1119
M(VVV
VVVT) = p (0a, (VVVT),.... de (VVVT))-
(38)
1120
Then note that h is continuous and permutation equivariant from matrices to vectors, so it can be e-approximated by an invariant graph network [Keriven and Peyré, 2019], call it IGN. If we define
1121
IGN and IGN,, (V,VT)) V.V.T (this identity operation is linear and permutation equivariant, so it can be exactly expressed by an IGN), then we have e-approximation of f by
1122
1123
V. vVy" (IGN&, (V.VT),, ..NT).....,,,,,,,,, (GNV,
(39)
1124
31

---

1125
G.3
Proof of Universal Approximation for General Decompositions
1126
Theorem 4. Consider the same setup as Theorem where X; are also compact. Let 4; be family of -ivinvariant functions that universally approximate G--imvrrant continuous functions X; + R and let R be set of continuous function that universally approximate continuous
1127
1128
functions 2 C IR - Rs, for every compuct 2, where Ei,t, 0g. Then for any 0 and any G-invariant continuous fontitt f :2 x... Xx -> TR. there exists and p E such that
1130
|1 - ploi,..... .K)) K.
1131
1132
Proof. Consider a particular G-invariant continuous function / X1 X... x & R*. By
1133
Theorem 3 there exists G--invariant continuous functions & Xi - RR and a continuous function >; a,) such that
1134
p' c Ra + I2 (where
f(v1, 0k) (vi((v)), 2 (vx)).
1135
Now fix an O. For any p E R and any d, D (i 1.... k) may bound the difference from f as follows (suppressing the 0, 's for brevity),
1136
f p 22))le
(1'(d' 1k) p 2k)1
1I (di
0/) p( ................................ 0%) plo 4/) ,,,)
S 11' 16 p(o),...,, Rl + |l 12)
0x)1
I++1 II
Now let K" II== im Since each de is continuous and defined on compact set X, know that im is compact, and so the product K is also compact. Since K' is compact, it is contained in a centered at the origin. Let K be the closed ball B 1) of radius r + centered at the origin, so K contains K' and a ball of radius around each point of K'. We
1137
1138
1139
closed ball (r) of radius
1140
may extend p' continuously to K needed, assume p' K - R By universality of R may pick particular p K RR, R such that
1142
I= sup (u:EA.)
l1''(d'....... . o') p(ó
K S sup (ld'(2) p(=)lp < <//2.
=eK
1143
Keeping this choice of p. it remains only to bound II. As p is continuous on compact domain, it in fact uniformly continuous. Thus, we can choose > such that [yy 2112 I 8', then (le(y) xl e/2, and then we define ö = min(8', 1).
1144
Since 4; universally approximates of we may pick Φ; E ④ such that l| o1lo < 6/vk, and thus (I Φx) - (di.... Kl S 8. With this choice of di, we know that I imó; C K (because each o, (x;; is within distance of (z;)). Thus, (())(21).... dn (xx)) is well-defined,
1146
1147
1148
1149
and we have
11 -1p((())..... H6)) p( ......... ... dx)llo
sup (z(()(z)). ..... - (. ox (M
<e/2
1150
due to our choice of 6, which completes the proof.
H Basis Invariance for Graph Representation Learning
1151
1152
H.1 Spectral Graph Convolution
1153
In this section, we consider spectral graph convolutions, which for node features X =x take the form f(V, X)) Σn = 8,0,0 X for some parameters 6,. We can optionally take 6, h(A:) ) for some continuous function h : - R of eigenvalues. This form captures most popular spectral graph convolutions in the literature [Bruna et al., 2014, Hamilton, 2020, Bronstein et al., 2017]; often, such convolutions are parameterized by taking to some analytic function such as simple affine function [Kipf and Welling, 2017], linear combination in polynomial basis [Defferrard et al.,
1154
1155
1155
1157
32

---

1159
2016, Chien et al., 2021], or parameterization of rational functions [Levie et al., 2018, Bianchi et al., 2021].
1180
1181
First, it is well known and easy to see that spectral graph convolutions are permutation equivariant, as for permutation matrix P we have
J(PV,A,PX) Σ P PTPX Eo.PU, P)(V,A,)).
(40)
Also, it is easy to see that they are sign invariant, as (-m) v.u. However, the 0g do not depend on the eigenvalues, then the spectral graph convolution is not necessarily basis invariant. For instance, if U1 and 122 are in the same eigenspace, and we change hasis by permuting v' = 1/2 and
1183
1184
1185
1166
1/2 U1, then if 01 7 02 the spectral graph convolution will generally change as well.
1167
On the other hand, 0;- = ((aa)) for some function h IR + R, then the spectral graph convolution is basis invariant. This is because if v; and vi belong to the same eigenspace, then X; Xj so h(A.) = h()z). Thus, if Us U,,...... Us are eigenvectors of the same eigenspace with eigenvalue X, we have that 2 ((A;;) U,, U. projector onto the eigenspace [Trefethen and Bau III. 1997]. A change of basis does not change this orthogonal projector, so such spectral graph convolutions are basis invariant.
1168
1189
--1 U4 V, Now, note that V Ui, v/2 is the orthogonal
1170
1171
1172
1173
Another way to see this basis invariance is with a simple computation. Let VI...., Vi be the eigenspaces of dimension d1.... dj, where V3 E Rexd, Let the corresponding eigenvalues be
1174
M1sui Hg. Then for any orthogonal matrices Qi E Od,)), we have
1175
M(Neeey = Σ Va
(41)
Σ V
(42)
Σ (1)))
(43)
1176
so the spectral graph convolution is invariant to substituting VjQj for V,,
1177
Now, give the proof that shows SignNet and BasisNet can universally approximate spectral graph convolutions.
1178
1179
Theorem 1 (Learning Spectral Graph Convolutions). Suppose the node features X E Raxq take values in compact sets. Then SignNet can universally approximate any spectral graph convolution, and both BasisNet and Snprresivve-BsiiNie can universally approximate any parametric spectral graph convolution.
1180
1181
1183
Proof. Note that eigenvectors and eigenvalues of normalized Laplacian matrices take values in compact sets, since the eigenvalues are in [0, 2] and we take eigenvectors to have unit-norm. Thus, the whole domain of the spectral graph convolution compact.
1184
1185
Let E > O. First, consider a spectral graph convolution f(V,A, = -E 0,0,, X. For SignNet, let o(v, X, approximate the function ő(v,, X) = U,,8oo X to within E/n error, which DeepSets can do since this a continuous permutation equivariant function from vectors to vectors (Segol and Lipman, 2019] (note that we can pass X; as vector in R" by instead passing ); where is the all ones vector). Then / Σ is linear permutation equivariant operation that can be exactly expressed by DeepSets, so the total error is within The same argument applies when
1186
1187
1188
1189
1190
1191
1192
0, = ((A)) for some continuous function
1183
For the basis invariant case, consider a parametric spectral graph convolution f(V, [VV,,,A X) E. ((Ac)uoo X. Note that if the eigenspace bases are Vi,... V/2 with eigenvalues fi,... Ml, we write the AV X)= E V,, X. Again, will let p E'=1 be function, which can expressed exactly by DeepSets. Thus, it suffices to show that VV, X can be e/n approximated by 2-IGN (i.c. an IGN that only uses vectors and matrices).
1184
1196
1197
33

---

1198
Note that since h is continuous, we can use an elementwise MLP (which IGNs can learn) to approximate fi (M11 VVV,)) (h(p)11 T VVV X) arbitrary precision (note that we rep- resent the eigenvalue μ. as a constant matrix yall" TT. ). Also, since a 2-IGN can learn matrix vector
1199
1200
multiplication (Cai and Wang [2022] Lemma 10), we can approximate f2(h(p)111, , VVVT, XX) (h(m) VVVX), as V.V;" E 2n' is a matrix and X E [ is a vector with respect to permuta-
1201
1202
1203
tion symmetries. Finally, we use elementwise MLP to approximate the scalar- multiplication fa(h())11 VVT, X)= h(u)VVTXX X. Since fa o f2 o f1 (I .) = hhu)VV X, and
1204
VVV since 2-IGNs universally approximate each fú, applying Lemma 6 shows that a 2-IGN can approx- imate M(u)VV X to e/n accuracy, so we are done. Since Expressive-BasiSN. Bat is stronger than BasisNet, it can also universally approximate these functions.
1205
1206
1207
1208
From the proof, we can see that SignNet and BasisNet need only learn simple functions for the p and e when h is simple, or when the filter is non-parametric and we need only learn O,. Xu et al. [2020] propose the principle of algorithmic alignment, and show that if separate modules of a neural network each need only learn simple functions (that is, functions that are well-aaproximated by low-order polynomials with small coefficients), then the network may be more sample efficient. If we do not require permutation equivariance, and parameterize SignNet and BasisNet with simple MLPs, then algorithmic alignment may suggest that our models are sample efficient. Indeed, p Σ is simple linear function with coefficients 1, and @(V, A, X) = h(A)VV X is quadratic in V and linear in X, so it is simple if h is simple.
1209
1210
1211
1212
1213
1214
1215
1216
1217
Proposition 3. There exist infinitely many pairs of non-isomorphic graphs that SignNet and BasisNet can distinguish, but spectral graph convolutions or spectral GNNs cannot distinguish.
1218
1219
The idea is follows: we will take graphs G and give them the node feature matrix XG 11/21, i.c. each node has as feature the square root its degree. Then any spectral graph convolution (or, the first layer of any spectral GNN) will map V Diag(0)V XX to something that only depends on the degree sequence and number of nodes. Thus, any spectral graph convolution or spectral GNN
Proof.
1220
1221
1222
1223
will have the same output (up to permutation) for any such graphs G with node features XG and the
1224
same number of nodes and same degree sequence. On the other hand, SignNet and BasisNet can
distinguish between infinitely many pairs of graphs (G(1), G(2) with node features (Xgas, X ) and the same number of nodes and degree sequence; this is because SignNet and BasisNet can tell when graph is bipartite.
1225
1226
1227
For each n 2 5, we will define (()) and (22) as connected graphs with n nodes, with the same
1228
degree sequence. Also, we define (!)) to have node features x(()
(1) where af!) is the degree
1229
of node i in G(), and similarly (2 has node features x!() / a(a)) Now, note that (2) is an cigenvector of the normalized Laplacian of (1)) and it has eigenvalue 0. As we take the eigenvectors
1230
1231
1232
to be orthonormal (since the normalized Laplacian is symmetric), for any spectral graph convolution
1238
we have that
= 0, Σ "
Σ Overy x() = =1000 x() =
1/2
(44)
Where D2 is the diagonal degree matrix of G(), Likewise, any spectral graph convolution outputs 0, Ed(d DD for ((2), Since Dj and D2 are the same up permutation, we have that any
1234
1235
spectral graph convolution has the same output for GO) and ((2), up to a permutation. In fact, this also holds for spectral GNNs, as the first layer will always have the same output (up to a permutation)
1236
1237
on (11) and ((2), so the latter layers will also have the same output up to permutation.
1238
Now, we concretely define GO) and (2)), This is illustrated in Figure 11 and Figure 12. For n 5, let (1)) contain triangle with nodes W1, Wa, W3, and have path of length 2 coming out of one of the nodes in the triangle, say Wi connects to wa, and wa connects to Ws. This is not bipartite, as there
1239
1240
1241
is triangle. Let (( be bipartite graph that has 2 nodes on the left (u,, and 3 nodes on the right (Va, U4, 05). Connect Uj with all nodes on the right, and connect 02 with U3 and u4.
1242
1243
Note that both (()) and ((2) have the same number of nodes and the same degree sequence {3, 2, 1}. Thus, spectral graph convolutions or spectral GNNs cannot distinguish them. How-
1244
1245
34

---

W1
Wi
U1
2/2
W3
U2
14
U5
G
((2)
Figure 11: Illustration of our constructed G() and G for n = 5, as used the proof of Proposi-
tion 3.
W1
W4
W5
W6
11
V3
102
1/2
U4
16
U5
G(1)
((2)
Figure 12: Illustration of our constructed (()) and (22) for 6, used in the proof of Proposi-
tion 3.
1246
ever, SignNet and BasisNet can distinguish them, as they can tell whether a graph is bipartite by checking the highest eigenvalue of the normalized Laplacian. This is because the multiplicity of the eigenvalue is the number of bipartite components. In particular, SignNet can approximate the function (b1,, di, X)= X; and p R max Likewise, BasisNet approximate the function
1248
1249
6d, (VVVT, A.) A; and p max
1250
1251
This in fact gives an infinite family of graphs that SignNet / BasisNet can distinguish, but spectral graph convolutions or spectral graph GNNs cannot. To why, suppose have G(1) and ( for
1252
1253
some n 2 5. Then we construct a pair of graphs on n + nodes with the same degree sequence. To
do this, we add another node to the path of G(I), thus giving it degree sequence {3, 2.., 2, 1}. For G(2), we add node un+1 to the side that 2, not contained on (e.g. for n = 5, we add U/ to the left side, is was the right), then connect 2n to Un-1 also give degree sequence {3,2, (3.2..... 1}.
1254
1255
Note that the non con-bipartiteness of (1) and bipartiteness of (2) are preserved.
1257
1258
1259
H.2
Existing Positional Encodings
1250
Here, we show that our SignNets and BasisNets universally approximate various types of existing graph positional encodings. The key to show that these positional encodings are related spectral graph convolution matrices and the diagonals of these matrices, and to show that our networks can approximate these matrices and diagonals.
1261
1263
1264
Proposition 5. If the eigenvalues take values in compact set, SignNets and BasisNets universally ap-
proximate the diagonal of any spectral graph convolution matrix f(V, diag (E h())))))) Do,,
1265
1256
BasisNets can additionally universally approximate any spectral graph convolution matrix f(V,
1287
Σ 1 h(Ac)uze.
1288
Proof. Note that the i; come from a compact set as they are unit norm. The X are from a compact set by assumption; this assumption holds for the normalized Laplacian, as x E 20, Also, diag is linear, the spectral graph convolution diagonal can be written Σn, h ((Aa)dii(
35

---

1271 Let e > O. For SignNet, let p
Ei=r' which can be exactly expressed as it is permutation equivariant linear operation from vectors to vectors. Then o(u;, A:) can approximate the function
1272
1273
A,diag(u,,,) to arbitrary precision, as it is a permutation equivariant function from vectors to vectors (Segol and Lipman, 2019]. Thus, letting approximate the function to e/n accuracy, SignNet can approximate f accuracy.
1274
1275
Let be the number of cigenspaces Vi...., Vi, so f(V,A) = L.: For BasisNet, we need only show that it can approximate the spectral graph convolution matrix to e/l accuracy, as 2-IGN can exactly express the diag function each Ød. since it a linear permutation equivariant
1278
1277
1278
function from matrices to vectors. A 2-IGN can universally approximate the function fi (14, V.V,))
1279
1280
(h()s), V.V.") ), as it can express any elementwise MLP. Also, 2-IGN can universally approximate the scalar-matrix multiplication f2(h(p:), V.VT)) = V(,,VVVV by another elementwise MLP. = f2 f1 (1s, VVVT), Lemma 6 shows that single 2-IGN can approximate this composition e/l accuracy, so we are done,
1281
1282
Since
1283
1284
1285
SignNet and BasisNet universally approximate node positional encodings based on heat kernels [Feldman et al., 2022] and random walks [Dwivedi et al., 2022]. BasisNet universally approximates diffusion and p-step random walk relative positional encodings [Mialon et al., 2021], and generalized PageRank and landing probability distance encodings [Li et al., 2020].
Proposition
1286
1287
1288
1289
We will show that we can apply the above Proposition 5, by showing that all of these positional encodings are spectral graph convolutions. The heat kernel embeddings are of the form
Proof.
1290
1291
diag (Ei=1 exp(-tA.))
for some choices of the parameter t, so they can be approximated by SignNets or BasisNets. Also, the diffusion kernel [Mialon al., 2021] is just the matrix of this heat kernel, and the p-step random walk kernel is Σ (1 (1-7)) Pe,, for some parameter y, so BasisNets can universally approximate both of these.
1292
1293
1294
1295
For the other positional encodings, we let v; be the eigenvectors of the random walk Laplacian The eigenvalues of these two Laplacians are the same, and if i; is an eigenvector of the normalized Laplacian then D D-1/2 is an eigenvector of the random walk Laplacian with the same eigenvalue [Von Luxburg, 2007].
D 1 instead of the normalized Laplacian 1 D 10-122AD 1011//
1/2,
1296
1297
1298
1299
Then with iú the eigenvectors of the random walk Laplacian, the random walk positional encodings (RWPE) in Dwivedi et al. [2022] take the form
1300
diag ((D- = diag > (1-MM E1-A))u,11 x)
(45)
1301
for any choices of integer
1302
The distance encodings proposed in Li et al. [2020) take the form
fa(AD-1,
(46)
1303
for some function f3. We restrict to continuous fa here; shortest path distances can be obtained by a discontinuous ja that we discuss below. Their generalized PageRank based distance encodings can be obtained by
1304
1305
Σ
1h Σ
A1)*
(47)
1308
for some ?/ E IR, so this is a spectral graph convolution. They also define so-called landing probability based positional encodings, which take the form
1307
(1-x) A.
(48)
1308 for some choices of integer k. Thus, BasisNets can approximate these distance encoding matrices.
1309
Another powerful class of positional encodings is based on shortest path distances between nodes 1310 in the graph [Ying et al., 2021, Li et al., 2020]. Shortest path distances can be expressed in
36

---

1311
form similar to the spectral graph convolution, but require highly discontinuous function. If we define fa( .n) mi i to be the lowest index such that x; is nonzero, then we can write the shortest path distance matrix as (ADD-A,, ..... (D-1A)"), where fa is applied matrix. As (D- = Ei= (1 Ar,, BasisNets can learn the inside arguments, but cannot learn the discontinuous function fa-
1312
1313
1314
elementwise to return an
1315
1316
H.3
Spectral Invariants
Here, we consider the graph angles aij = VVVV e,ll2. for I,...,I where is the number of eigenspaces, and j .,.... It is clear that graph angles are permutation equivariant and basis invariant. These graph angles have been extensively studied, so we cite a number of interesting properties of them. That graph angles determine the number of length 3, 4 and 5 cycles, the connectivity of a graph, and the number of length &s closed walks is all shown in Chapter 4 of Cvetković et al. [1997]. Other properties may be of use for graph representation learning as well. For instance, the cigenvalues of node-deleted subgraphs of a graph G are determined by the cigenvalues and graph angles of G; this may be useful in extending recent graph neural networks that are motivated by node deletion and the reconstruction conjecture [Cotta et al., 2021, Bevilacqua et al., 2022, Papp et al.,
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
2021, Tahmasebi et al., 2020].
1327
Now, we prove that BasisNet can universally approximate the graph angles. The graph properties we consider in the theorem are all integer valued (e.g. the number of cycles of length 3 in a graph is an integer). Thus, any two graphs that differ these properties will differ by at least I, so as long as we have approximation to g < 1/2, we can distinguish any two graphs that differ in these properties.
1328
1329
1330
1331
Recall the statement of Theorem 2.
1332
Theorem BasisNet can universally approximate the graph angles auy- The eigenvalues and graph angles (and thus BasisNets) can determine the number of length 3, 4, and 5 cycles, whether a graph is connected, and the number of length k closed walks from any vertex to itself.
1333
1334
1335
Proof. Note that the graph angles satisfy
ai = IVVVV e, -
VeVVV eS,
(49)
where V; is a basis for the ith adjacency matrix eigenspace, and e, V.V,T e, is the (i-t)-entry of V.V.T. These graph angles are just the elementwise square roots of the diagonals of the matrices V.V,T. diag(VVVV]] is a permutation equivariant linear function from matrices vectors, 2-IGN V.V.T can exactly compute this with 0 error. Then 2-IGN can learn elementwise = v (dia)((VV)) to arbitrary precision. Finally, there may be remaining operations f' that are permutation invariant or permutation
1336
1337 As fi (VVV))
1338
1339
MLP to approximate the elementwise square root "2(diag(VVVV
1340
1341
1342
equivariant from vectors to vectors; for instance, the axj are typically gathered into a matrix of size
1343 1 X where the columns are lexicographically sorted (1 is the number of eigenspaces) [Cvetković
1344 et al., 1997], or we may have a permutation invariant readout to compute a subgraph count. A
1345
DeepSets can approximate fa without any higher order tensors besides vectors [Zaheer et al., 2017, Segol and Lipman, 2019].
1346
1347
As 2-IGNs can approximate each ft individually, a single 2-IGN can approximate fa o f2 o fi by Lemma Also, since the graph properties considered in the theorem are integer-valued, BasisNet can distinguish any two graphs that differ in one of these properties.
1348
1349
1350
To see that message passing graph neural networks (MPNNs) cannot determine these quantities, we use the fact that MPNNs cannot distinguish between two graphs that have the same number of nodes and where each node (in both graphs) has the same degree. For k > 3. let C2 denote the cycle graph of size k, and C₁ + C2 denote the graph that is the union of two disjoint cycle graphs of size k.
1351
1352
1353
1354
MPNNs cannot distinguish between Cz and C + C2 for k 2 3. because they have the same number of nodes, and each node has degree 2. Thus, MPNNs cannot tell whether a graph is connected, as On is but Cs + C& is not, Also, it cannot count the number of 3, 4, or cycles, as Cs + C2 has two
1355
1356
1357 k cycles while Cas has no l cycles. Likewise, any node in Cs + C& has more length k closed walks than any node in Czt- This is because any length io closed walk in C2 has an analogous closed walk
1358
1359
in Ck + Ck. but the nodes in Cj + C₁ also have closed walk that completely goes around cycle.
37

---

I
Useful Lemmas
1380
1361
In this section, we collect useful lemmas for our proofs. These lemmas generally only require basic tools to prove. Our first lemma is a crucial property of quotient spaces.
1362
1363
Lemma 1 (Passing to the quotient). Let X and y be topological spaces. and let X //G be quotient
space, with corresponding quotient map π. Then for every continuous G-invariant function f X
1384
y, there is a unique continuous f X/G +y Y such that f = f n.
1365
1366
Proof For E X/G. by surjectivity of π we can choose Tzz X such that ((x2) = z. Define f: X/G - y/ by f(z) f(x)). This is well-defined, since if π (x=2) (x)) for any other E X, then gI= = x for some E G, so
1367
1368
f(x) = f(gx)) - f()),
(50)
where the second equality uses the G-invariance of f. Note that f is continuous by the universal
1369
property of quotient spaces, Also, f is the unique function such that f = f o x; if there were another
1370
function h: : X/G + y with h(z) + f(z), then h(z) # f(zz). so (xx(2))) = h(=) + f(x)). O
1371
1372
Next, we give the First Fundamental Theorem of (dd) a classical result that has been recently used for machine learning by Villar et al. [2021]. This result shows that orthogonally invariant f(V)
1373
can be expressed as function h(VVT). We give a proof that if f is continuous, then h is also continuous.
1374
1375
Lemma 2 (First Fundamental Theorem of O(d). A continuous function f Ruxd + R is orthogonally invariant, iee. f(VQ) = for all Q E O(d), if and only if f(V) = N(VV for some continuous h.
1378
1377
1378
Proof. f(V) = h(VVT), then we have f(VQ) = N(VQQTVT) = N(VVT) so f is orthogonally
1379
1380
invariant.
1381
For the other direction, invariant theory shows that the (dd) invariant polynomials are generated by the inner products v. V/g where 2s E Ra are the rows of V [Kraft and Procesi, 1996]. Let p Raxd Raxa be the map pVV) = VVT. Then González and de Salas [2003] Lemma 11.13 shows that the quotient space 12 (O(d) is homeomorphic to closed subset p(R"xd)
1382
1383
1384
Z C Rax= Let ğ refer to this homeomorphism, and note that ý o x = p by passing to the quotient (Lemma 1). Then any continuous (d) invariant f passes to a unique continuous f : Raxd/ (O() + R
1385
1386
(Lemma 1), so f = f o π where π is the quotient map. Define h : Z + IR by h = f o p- and note that h is composition of continuous functions and hence continuous. Finally, we have that h(VVT)= h(p π (V)) = f (V) = f(V), so we are done.
1387
1388
1389
1390
The next lemma allows us to decompose quotient of product space into a product of smaller quotient spaces.
1391
1392
Lemma 3. Let ,y....,Xy Xs be topological spaces and G....., G5 be topological groups such that each G3 acts continuously on X. Denote the quotient maps by n. X, - X2/Gi, Then the quotient of the product is the product of the quofient, i.e.
1383
1394
(X1 X ... x Xx) (G1 X ... Gx) = (X//.)) x ... x (Xx/GH), and T1 ....... X TK X1 X Xx /1) x .... (X+/Gz) is quotient map.
(51)
1395
1396 Proof. First, we show that 1 x... x my is a quotient map. This is because 1. the quotient map of any continuous group action is open map, so each is open map, 2. the product of open maps is an open map, so 1 x... X Th is an open map and 3. a continuous surjective open map is a quotient map, Ti X .... ... Tk. which is continuous and surjective, is quotient map.
1397
1396
1399
1400
Now, we need only apply the theorem of uniqueness of quotient spaces to show (51) (see e.g. Lee [2013], Theorem A.31). Letting X2 X .... x X' + (X₂ x x Xx)/ x x G₂) denote #x) = 7(11 .........'... if and only I X x n& (Z1, ... , n X TA (y)...., Mk,, since either of these is true if and only if
1401
1402
the quotient map for this space, it is easily seen that q(z),
1403
1404
there exist gi E G. such that x; = 9:34 for each Thus, we have an isomorphism of these quotient
1405
spaces.
D
38

---

1406
The following lemma shows that quotients of compact spaces are also compact, which is useful for universal approximation on quotient spaces.
1407
1408
Lemma 4 (Compactness of quotients of compact spaces), Let X' be a compact space. Then the quotient space X R/G is compact.
1409
1410
Denoting the quotient map by π X - X/G and letting (Ua Ja be an open cover of X/G. we have that { - (U.)) is an open cover of X. By compactness of X, we can choose a finite subcover { (Uaz) az l....... Then ( ()),)))==,,.....
Proof.
1411
1412
Ji by surjectivity, and
Fim...... is thus an open cover of X/G.
1413
1414
The Whitney embedding theorem gives a nice condition that we apply show that the quotient spaces //G that we deal with embed into Euclidean space. It says that when X / is a smooth manifold, then it can be embedded into a Euclidean space of double the dimension of the manifold. The proof is outside the scope of this paper.
1415
1416
1417
1418
Lemma 5 (Whitney Embedding Theorem [Whitney, 1944)). Every smooth manifold M of dimension can be smoothly embeileed in R
1419
1420
Finally, we give a lemma that helps prove universal approximation results. says that functions that we want approximate can be written as compositions f = fr. ... S1, then it suffices to universally approximate each fi and compose the results to universally approximate the f. This is especially useful for proving universality of neural networks, as may some layers to approximate each fi, then compose these layers to approximate the target function f.
1421
1422
1428
1424
Lemma 6 (Layer-wise universality implies universality). Let Z S R be compact domain, let FI.....FF, be families of continuous functions where F, consists of functions from Rd:-1 - Rdd, for some di,...,d d1., Let FF be the family of functions {Sr. f 2 + Rdd, S E Fi} that are compositions of functions Si E F,
1425
1426
1427
1428
1429
For each i, let D. be a family of continuous functions that universally approximates F.. Then the family of compositions
1430
{ØL .... o 01 : 0i E 4.} universally approximates F.
Proof. Let f -1= fi E F. Let Ê Z, and then for > let E, = fi- Then each Z, is compact by continuity of the ft. For 1 S i < let Z, = 2,, and for i = L let 2, be compact set containing 2L such that every ball of radius one centered at a point in 2g is still contained in Zz.
1431
1432
1433
1434
Let O. We will show that there is Φ E o such that [| 21100 by induction on L. This holds trivially for L = 1, as then + = $1.
1435
1436
Now, let L 2 2, and suppose it holds for L - 1. By universality of o,,, we can choose a Φr, 2,, + Rdd E 4,, such that ||,,, fr.llse < e /2. As Φr.. is continuous on compact domain, it is also uniformly continuous, so we can choose 8 > 0 such that |yy 2||2 < d = (ι - < <
1437
1438
1439
c/2.
1440
Let 8 min(ō, 1). By induction, we can choose dI,-1
d., di E o such that
| .... . - Sr.- ..... si fi <
(52)
1441
Note that dr.-1 ................................ ... (1 S Z,, because for each Z, Φ1.-1 o ... di (x) is within 5 < 1 Euclidean distance to fi-1 .... fz) E Zt, it is contained in Z by construction. Thus,
1442
1448 may define o Φ2 o o 01 2 - Red2, and compute that
1 fllo0 S | 21 o ft- o
.... o filloo h + 11 ft-1 .... f1 fillo e/22
(53)
< 1 o. fí-1
(54)
1444 since | Sr.loo < e/2. To bound this other term, let x E 2, and for y = -1.11 0 .... 1 (a)
1445 and = == f .... fi (zr), we know that |y 2||2 < 8, so (1))(1) - (z)11) < t 2 by uniform
1446
continuity. As this holds for all x, we have ( or. fr.-1 .... o li S <//,, so 1 flloo <6
1447
and we are done.
39

---

Table 7: Results on the ZINC dataset with 500k parameter budget and no edge features. Numbers are the mean and standard deviation over 4 runs each with different seeds.
Base model
Positional encoding
k
#params
Test MAE (1)
No PE
16
497k
0.3 014
GIN
LapPE (flip)
16
498k
0.0011
SignNet
16
500k
0. 0.238
PE
16
501k
0.46410.011
GAT
LapPE. (flip)
16
502k
0.462.10.01
SignNet
16
499k
0.24310.000
J Further Experiments
1448
1449
J.1
Graph Regression with no Edge Features
1450
All graph regression models in Table use edge features for learning and inference. To show that SignNet is also useful when no edge features are available, we ran ZINC experiments without edge features as well. The results are displayed in Table 7. In this setting, SignNet still significantly improves the performance over message passing networks without positional encodings, and over
1451
1452
1453
1454
Laplacian positional encodings with sign flipping data augmentation.
1455
J.2
Learning Spectral Graph Convolutions
Table 8: Sum of squared errors for spectral graph convolution regression (with no test set). Lower is better. Numbers are mean and standard deviation over 50 images from He al. [2021].
Low-pass
High-pass
Band-pass pass-pass
Band- Band-rejection
Comb
GCN
.111 = 068
3. 1.
1.720
1 1.418
1.753
GAT
.113__00 065
.954 696
1.1054.964
..43
.638..446
GPR-GNN
.033_ 002
.012+.007 007
.1374.081
1956..197
.3694.460
ARMA
.053_
_229 029
.042+.024 024
.107+.039
.148 2.0
.202+.116
ChebNet
.003_
.001 001
.005
.009 D00
.022+.016
BernNet
.001
.001 001
.0004.000
.048 2.22
.027+.019
Transformer
3.662=1.97
3.715
1.531 1:330
1 1.506
3.178
Transformer Fig Flip
4.454_2.32
4.425
1.651
2.567+1.73
3.720
Transformer Eig Abs
2.727
3.172+1.61
1.2644.788
1.445 9943
2.607
DeepSets SignNet
.004-.013
.086+.405
.021 1.15
.008 4.077
.003
Transformer SignNet
.003-.014 .016
.004
.001 4.004
.0064.023
.093
DeepSets BasisNet
.009-.018
.0034.015
4.08
.004
4.60
Transformer BasisNet
.079_.471
038
.0051.016
.0061.016
.014
1456 To numerically test the ability of our basis invariant networks for learning spectral graph convolutions, we follow the experimental setups of Balcilar al. [2020], He et al. [2021]. We take the dataset of 50 images in He et al. [2021] (originally from the Image Processing Toolbox of MATLAB), and resize them from 100x 100 to 32 x2. Then we apply the same spectral graph convolutions on them as in
1457
1458
1459
1460
He et al. [2021], and train neural networks to learn these as regression targets. As in prior work, we report sum squared errors on the training set to mcasure expressivity.
1481
1482
We compare against message passing GNNs [Kipf and Welling, 2017, Veličković et al., 2018] and spectral GNNs [Chien et al., 2021, Bianchi et al., 2021, Defferrard al., 2016, He al., 2021]. Also, we consider standard Transformers with only node features, with eigenvectors and sign flip augmentation, and with absolute values of eigenvectors. These models are all approximately sign invariant (they either use eigenvectors in a sign invariant way or do not use eigenvectors). We use DeepSets [Zaheer et al., 2017] in SignNet and 2-IGN [Maron et al., 2018)
1463
1464
1485
1486
1467
BasisNet for é, use DeepSets for in both cases, and then feed the features into another DeepSets or standard Transformer [Vaswani al., 2017] to make the final predictions. That is, we are only given graph information through the cigenvectors and eigenvalues, and we do not use message passing.
1458
1469
40

---

1471
Table 8 displays the results, which validate our theoretical results in Section 3.1. Without any message passing, SignNet and BasisNet allow DeepSets and Transformers to perform strongly, beating the
1472
1479
spectral GNNs GPR-GNN and ARMA on all tasks. Also, our networks outperform all other methods on the hand-rejection and comb filters, and are mostly close to the best model on the other filters.
1474
1475
K
Further Experimental Details
1476
K.1
Hardware, Software, and Data Details
1477 All experiments could fit on one GPU at time. Most experiments were run on a server with 8 NVIDIA RTX 2080 Ti GPUs. We run all of our experiments in Python, using the PyTorch [Paszke et al., 2019] framework (license URL). We also make use of Deep Graph Library (DGL) [Wang et al., 2019] (Apache License 2.0), and PyTorch Geometric (PyG) [Fey and Lenssen, 2019] (MIT License) for experiments with graph data.
1478
1479
1480
1481
1482
We open source our code [redacted for anonymous review].
1489
The data we use are all freely available online. The datasets we use are ZINC [lrwin et al., 2012], Alchemy [Chen et al., 2019a], the synthetic counting substructures dataset [Chen et al., 2020], the multi-task graph property regression synthetic dataset [Corso et al., 2020] (MIT License), the images dataset used by Balcilar et al. [2020] (GNU General Public License v3.0), the cat mesh from html (Personal Use License), and the human mesh htt///wtterrrrrree park-aaiddesssss. Model License). If no license is listed, this means that we cannot find a license for the dataset. As they appear to be freely available with permissive licenses or no licenses, we do not ask for permission from the creators or hosts of the data.
1484
1485
1488
1487
free3d. com/ hts//dddmmodee www.mmmmattt----mmemmaa
1488
from turbosquid. d.
1093267 (TurboSquid 3D
1489
1490
1491
1482
We do not believe that any of this data contains offensive content or personally identifiable information. The 50 images used in the spectral graph convolution experiments are mostly images of objects, with few low resolution images of humans that do not appear to have offensive content. The only other
1499
1494
1495
human-related data appears to be the human mesh, which appears to be from a 3D scan of a human.
1498
The human mesh does have tattoos, but they do not appear to be offensive.
1497
K.2
Graph Regression Details
1498
In Section 4.1 1 we study the effectiveness of SignNet for learning positional encodings to boost the expressive power, and thereby generalization, on the graph regression problem ZINC. In all cases we take our & encoder to be an 8 layer GIN with ReLU activation. The input eigenvector v/ E IR", where n is the number of nodes in the graph, is treated as a single scalar feature for each node. In the case of using a fixed number of eigenvectors k, the aggregator p is taken to be an 8 layer MLP with batch normalization and ReLU activation. The aggregator p is applied separately to
ZINC.
1499
1500
1501
1502
1503
1504
the concatenatation of the & different embeddings for each node in graph, resulting in single embedding per node. This embedding is concatenated to the node features for that node, and the result passed imput to the base (predictor) model. We also consider using all available eigenvectors in each graph instead of a fixed number k. Since the total number of eigenvectors is a variable quantity, equal to the number of nodes in the underlying graph, MLP cannot be used for p. To handle the variable sized input in this case, we take to be an MLP preceded by a sum over the ø outputs. In
1505
1506
1507
1508
1509
other words, the SignNet of the form MLP [E/n ((v+) + d(-r:) in this case.
1510
1511 As well as testing SignNet, we also checked whether simple transformations that resolve the sign ambiguity of the Laplacian eigenvectors p- = (VI...., . Ux) could serve as effective positional encoding. We considered three options. First is to randomly flip the sign of each =v; during training. This common heuristic used in prior work on Laplacian positional encoding [Kreuzer al., 2021, Dwivedi et al., 2020]. Second, take the element-wise absolute value |Uy]. This is non-injective map, creating sign invariance at the cost of destroying positional information. Third is different canonicalization that avoids stochasticity and use of absolute values by selecting the sign of each
1512
1513
1514
1515
1516
1517
1518
V/ so that the majority of entries are neg-tegative, with ties broken by comparing the E -nor of positive and negative parts. When the tie-break also fails, the sign is chosen randomly. Results for
1519
1520
GatedGCN base model on ZINC in Table show that all three of these approaches are significantly
1521
poorer positional encodings compared to SignNet.
41

---

1522
Our training pipeline largely follows that of Dwivedi et al. [2022], and we use the GatedGCN and PNA base models from the accompanying implementation (see https://githii thub. com/ vi jaydwivedi75/ gssppe The Sparse Transformer base model architecture we use, which
1523
1524
1525
like GAT computes attention only across neighbouring nodes, is introduced by Kreuzer et al. [2021]. Finally, the GINE implementation is based on the PyTorch Geometric implementation [Fey and Lenssen, 2019]. For the state-of-the-art comparison, all baseline results are from their respective
1526
1527
1528
papers, except for GIN, which we run.
1529
ZINC-full. We also run our method on the full ZINC dataset, termed ZINC-full. The result we report for SignNet is a larger version of the GatedGCN base model with SignNet that takes in all eigenvectors. This model has 994, 113 parameters in total. All baseline results are from their respective papers, except for GIN, which is from [Bodnar et al., 2021].
1530
1531
1532
1538
Alchemy. We run our method and compare with the state-of-the-art on Alchemy (with 10,000 training graphs). We use the same data split as Morris et al. [2020b]. Our base model is GIN that takes in edge features (i.e. GINE). The SignNet consists of GIN for & and a Transformer for p. as in the counting substructures and graph property regression experiments in Section 4.2. The model has 907,371 parameters in total. Our training setting is very similar to that of Morris et al. [2022],
1534
1535
1538
1537
1538
as we build off of their code. We train with an Adam optimizer [Kingma and Ba, 2014] with a starting learning rate of ,001, and minimum learning rate of .000001. The learning rate schedule
1539
1540
cuts the learning rate in half with a patience of 20 epochs, and training ends when we reach the minimum learning rate. All baseline results are from their respective papers, except for GIN, which is from [Morris et al., 2022].
1541
1542
1543
K.3
Spectral Graph Convolution Details
1544
In Appendix J.2, we conduct node regression experiments for learning spectral graph convolutions. The experimental setup is mostly taken from He et al. [2021]. However, we resize the 100 x 100 images to 32 x 32. Thus, each image is viewed as 1024-node graph. The node features X E IR" are the grayscale pixel intensities of each node. Just in He et al. [2021], we only train and evaluate on nodes that are not connected to the boundary of the grid (that is, we only evaluate on the
1545
1546
1547
1548
1549
28 x 28 middle section). For all experiments we limit each model to 50,000 parameters. We use the
1550
Adam [Kingma and Ba, 2014] optimizer for all experiments. For each of the GNN baselines (GCN,
1551
GAT, GPR-GNN ARMA, ChebNet, BernNet), we select the best performing out of 4 hyperparameter settings: either or convolution layers, and a hidden dimension of size 32 or D, where is just
1552
1553
large enough to stay with 50,000 parameters (for instance, D = 128 for GCN, GPR-GNN, and
1554
Nern
1555 We use DeepSets or standard Transformers as our prediction network. This takes in the output of SignNet or BasisNet and concatenates with the node features, then outputs a scalar prediction for each node. We use a 3 layer output network for DeepSets SignNet, and 2 layer output networks for all other configurations. All networks use ReLU activations.
1556
1557
1558
1559
For SignNet, we use DeepSets for both & and p. Our á takes in eigenvectors only, then our p takes the outputs of á and the eigenvalues. We use three layers for e and p.
1580
1561 For BasisNet, we use the same DeepSets for p as in SignNet, and 2-IGNs for the da,- There are three distinct multiplicities for the grid graph (1, 2, and 32), we only need separate IGNs. Each IGN consists of an 2x + = layer and two R=xd" + gaxd" layers, where the d' are hidden dimensions. There are no matrix to matrix operations used, as the memory requirements are intensive for these > 1000 node graphs. The Φd, only take in V.V,T from the eigenspaces, and the p takes the output of the Φd, as well as the eigenvalues.
1562
1583
1584
1565
1566
1567
K.4
Substructures and Graph Properties Regression Details
1588
We use the random graph dataset from Chen et al. [2020] for counting substructures and the synthetic dataset from Corso et al. [2020] for regressing graph properties. For fair comparison we fix the base
1589
1570
model as a 4-layer GIN model with hidden size 128. We choose & as 4-layer GIN (independently
applied to every eigenvector) and p as 1-layer Transformer (independently applied to every node).
1571
1572
Combined with proper batching and masking, we have a SignNet that takes Laplacian eigenvectors
1573 VE E _ and outputs fixed size sign- sign-invariant encoding node features fVV, A, X) 1xdd where
42

---

1574
varies between graphs but d is fixed. We use this SignNet in our experiments and compare with other methods of handling PEs.
1575
1578
K.S
Texture Reconstruction Details
Table 9: Parameter settings for the texture reconstruction experiments.
Params
Base MLP width
Base MLP layers
out dim p out dim
p. ø width
Intrinsic
328,579
128
SignNet 323,563
108
6
64
8
1577
We closely follow the experimental setting of Koestler et al. [2022] for the texture reconstruction experiments. In this work, we use the cotangent Laplacian [Rustamov et al., 2007] of triangle mesh with the lowest 1023 eigenvectors besides the trivial eigenvector of eigenvalue O. We implemented
1578
1579
1580
SignNet in the authors' original code, which was privately shared with us. Both and Φ are taken
1581
to be MIPs. Hyperparameter settings and number of parameters are given in Table 9. We chose
1582
hyperparameters so that the total number of parameters in the SignNet model was no larger than that of the original model.
43


Reviews:
[{"review_id": "znzlKia8B96", "reviewer": "Reviewer_1KhG", "summary": "This work proposes a node position encoding scheme for graph representation learning, which respects two symmetric properties of an eigensystem, such as sign invariance, permutation invariance, and basis invariance. The new graph representation is believed spectral invariant and they are more capable for bio- or chemo-applications, where the graph substructures and global graph properties are important.", "questions": "1. Figure 1, why there are 0-vector rows/columns in the P matrix? (the reviewer assumes black boxes are 1 and the rest gray area are filled with 0 values.)\n2. Line 91, it seems (2) defines basis invariant, why here is discussing permutation invariance instead?\n3. Line 122, does any arbitrary GNNs satisfy permutation equivariant? If not, this statement is inaccurate.\n4. Line 162 (corollary 1), why sign invariant is not discussed here? Does basis invariant always imply sign invariance?\n5. Line 176, why the spectral convolution can be written in this form? Usually a spectral graph convolution is defined as $f(X) =V^{\\top}\\theta VX$. The result keeps the dimension of $n\\times q$. However here $f(V,\\Lambda,X)\\in\\R^{q}$ is a vector (the understanding might be incorrect here, but the reviewer assumes $\\theta$ is a vector. Even though, unless $\\theta\\in\\R^{n\\times n}$, the new dimension is inconsistent with the former form.\n6. Line 201, does it imply that spectral invariant equals basis invariant and permutation invariant?\n7. In the experiment, why BasisNet is not studied?\n8. Line 241, is $k$ a hyper-parameter?\n9. Figure 5 (it is not a question though), consider changing orange to another color, as both node feature and position encoding modules are using the orange color, but they are not directly connected. \n", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "strengths:\n- originality: The authors value the important spectral information provided by eigenvectors of the graph Laplacian, which are usually ignored by message passing methods. On top of that, they make transformations to the eigenvectors to encode position information of a graph while preserving certain properties. Such symmetric properties, to the best of the reviewer’s knowledge, have never been analyzed by existing work. \n\n- quality: Abundant analyses were provided in the main text and in appendices to consolidate the encoding scheme. In addition, experiments are designed from different perspectives to support the main claims of the work.\n\nweaknesses:\n- clarity: While the reviewer acknowledges that there are too many details to show in a limited number of pages, introducing the main algorithm in the appendix indeed prevents a reader from immediately understanding the workflow of the proposed method in a representation learning task. For the general audience, especially those without a solid mathematical background, to build a holistic view effortlessly, the reviewer highly recommends that the authors could consider rearranging some parts of the paper. In addition, some paradigms are used before a proper definition, which makes the paper more difficult to follow. For instance, the “higher dimensional basis” in the introduction was discussed without first explaining what is it.\n\n- significance: The reviewer was mainly concerned with the empirical significance of the framework. Although it is claimed that symmetries are important for an eigensystem, and capturing graph properties (such as substructures) are important for bio- or chemo-applications, the experiments did not show a significant underperformance of the baseline methods over the proposed SignNet. A simple demonstration showing how ignoring such properties cause trouble in graph representation learning would be helpful. In addition, as the model does not outperform other methods significantly on the three benchmark datasets, it is questionable how much more computational cost was made to trade for a smaller MAE score?  \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "damCCOJr2eg", "reviewer": "Reviewer_LMmf", "summary": "This paper proposes SignNet and BasisNet, two neural architectures, which can approximate any continuous function of eigenvectors with  invariances. The authors demonstrate theoretically that the proposed mothods  can approximate spectral graph convolutions and compute powerful spectral invariants. Experiments on several tasks illustrate the empirical benefits of the models’ approximation power and invariances.", "questions": "Should eigendecomposition be carried out if SignNet is to be utilized for GNNs, learning arbitrary Spectral Graph Convolutions? If so, does its high time cost limit its scalability?", "limitations": "Yes. The authors suggest that a potential limitation of the proposed method is that it only consider eigenspaces, not general subspaces.\n", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths:\n1) The symmetries and  invariances of eigenspaces are significant and promising problems.\n2) The advantages of using SignNet and BasisNet is clear,  making sign flips and choices of eigenspace bases invariant.\n3) The theoretical analysis and proofs of the proposed method looks sound to me.\n4) The experiments reveal some intriguing findings. SignNet, for example, encodes bilateral symmetry and structural information on a cat model, which seems to demonstrate its great performance.\n\n### Weaknesses:\n1) The technical section of the paper is relatively dense, which may be difficult for non-experts in the invariant Networks to understand.\n2) The papers writing may need to double check. For instance, the references (1) and (2) in lines 92, 93, and 98 are invalid.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "H3TvFRXcSeU", "reviewer": "Reviewer_Lzrs", "summary": "This paper proposes a SignNet and Basisnet to obtain invariant graph neural network by using eigenspaces. The paper provide significant improvements with the proposed method with several applications.  ", "questions": "What are the limitations of the proposed methods?\n\n\nAll experiments show improved performance compared to baseline methods. I am wondering if there are any data that may not give inferior performance. Are there any datasets or settings where the proposed method may not give good performance? \n\n\nIs it possible to directly compare permutation based invariant/equivariant graph neural networks with the proposed method?   \n", "limitations": "Limitation are not clearly stated.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper makes an a useful and novel contribution to invaraint graph neural networks. Overall, the paper is well written and easy to understand. Experiments are extensive and covers several domains. All experiments show improved performances. However, the paper does not indicate any evidence where the proposed method could provide inferior performance.   ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7FSgm0J0Ns", "reviewer": "Reviewer_xhbi", "summary": "Contributions:\n(1) A neural architecture that preserves two symmetries (i) sign invariance and (ii) basis invariance, built based on the existing equivariant neural networks.\n(2) Extensive experiments on various settings.", "questions": "I don't see the theoretical value of Theorem 2. \n\nA quick review of spectral graph convolution: The spectral graph convolution is built based on Graph Fourier Transform (GFT) as in [Bruna et al., 2014] and [Defferrard et al., 2016]. GFT constructs the Fourier basis as the eigenvectors of the (normalized) graph Laplacian. GFT allows us to do Fourier transform of a graph signal or function f: V -> R where V is the set of nodes (i.e. each node is associated with a number) into the spectral domain. Then, based on the convolution theorem, we can define the graph convolution between a graph signal and a filter based on their Fourier transforms in the spectral domain.\n\nIn this paper, given the construction of SignNet and BasisNet using the eigenvectors, I think it is just a tweaked form of spectral graph convolution. The authors use the existing permutation equivariant neural networks and add the minus sign to the eigenvectors, but I find this modification brings no novelty.", "limitations": "The reasons we want a neural network to preserve symmetries and build equivariant neural networks are because these symmetries arise in the data. In graph and molecule data, only two symmetries are important: permutation and rotation. We want permutation- and rotation-equivariant neural networks to learn and generate graph and molecule data, because both theoretical and empirical evidences have shown that preserving the two symmetries reduces the amount of training data, makes the model robust against data noise and smaller (i.e. less parameters), and importantly allows us to embed physical knowledge into the model. These are the fundamental motivations for preserving permutation and rotation symmetries that obviously arise from the data.\n\nThe fundamental limitation of this work is a lack of motivation and evidence for the two symmetries they propose to preserve (i) sign invariance and (ii) basis invariance. I highly doubt if these two symmetries are relevant and important. Given this limitation, I vote to reject this paper. However, I keep the rating to be 4 (borderline reject) because I am willing to listen to the authors' rebuttals.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n(1) Paper is easy to follow and well-written.\n(2) The proposed methods are simple to implement using the existing codes of permutation equivariant neural networks.\n(3) Many experiments.\n\nWeaknesses: It is not clear \"why\" to preserve the two symmetries this paper proposes to preserve including sign invariance and basis invariance. In graph & molecule setting, two important symmetries are permutation (i.e. if we permute the nodes/atoms, the output stays the same) and rotation (i.e. if we rotate the 3D coordinates associating with each atom, the prediction for a physical property stays the same). I don't see a strong evidence that suggests preserving sign & basis invariances on top of permutation & rotation invariances brings any benefits. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject