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: ICLR 2023 notable top 25% (2023)
Keywords: Invariance
Equivariance
Eigenvectors
Spectral
Neural Networks

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 under certain conditions our networks are universal, i.e., they can approximate any continuous function of eigenvectors with the desired invariances. When used with Laplacian eigenvectors, our networks are provably more expressive than existing spectral methods on graphs; for instance, they subsume all spectral graph convolutions, certain spectral graph invariants, and previously proposed graph positional encodings as special cases. Experiments show that our networks significantly outperform existing baselines on molecular graph regression, learning expressive graph representations, and learning neural fields on triangle meshes. Our code is available at https://github.com/cptq/SignNet-BasisNet.

Published as a conference paper at ICLR 2023
SIGN AND BASIS INVARIANT NETWORKS FOR SPECTRAL GRAPH REPRESENTATION LEARNING
Derek , Robinson"
Lingxiao Zhao Carnegie Mellon University
MIT CSAIL
[dereklim, joshrob) Emit.edi
Tess Smidt
Suvrit Sra MIT LIDS
Haggai Maron NVIDIA Research
Stefanie Jegelka MIT CSAIL
MIT EECS & MIT RLE
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 is -u; and (ii) more general basis symmetries, which occur in higher dimensional eigenspaces with infinitely many choices of basis eigenvectors. We prove that under certain conditions our networks are universal, i.c., they can approximate any continuous function of cigenvectors with the desired invariances. When used with Laplacian eigenvectors, our networks are provably more expressive than existing spectral methods on graphs; for instance, they subsume all spectral graph convolutions, certain spectral graph invariants, and previously proposed graph positional encodings as special cases. Experiments show that our networks significantly outperform existing baselines on molecular graph regression, learning expressive graph representations, and learning neural fields triangle meshes. Our code is available at https: : :/githuu.
thub. com/ cpt./ S /ttiii/iiiiiiiiii gnNet- Basaaaisssss sNet.
INTRODUCTION
Numerous machine learning models process eigenvectors, which arise in various settings including principal component analysis, matrix factorizations, and operators associated to graphs or manifolds. An important example is the of Laplacian cigenvectors to encode information about the structure of a graph or manifold (Belkin & Niyogi, 2003; Von Luxburg, 2007: Lévy, 2006). Positional encodings that involve Laplacian eigenvectors have recently been used generalize Transformers to graphs (Kreuzer et al., ;021; Dwivedi & Bresson, 2021), and to improve the expressive power and empirical performance of graph neural networks (GNNs) (Dwivedi al., 2022). Furthermore, these cigenvectors are crucial for defining spectral operations on graphs that are foundational to graph signal processing and spectral GNNs (Ortega al., 2018; Bruna al., 2014).
However, there are nontrivial symmetries that should be accounted for when processing eigenvectors, as has been noted in many fields (Eastment Krzanowski, 1982; Rustamov et al., 2007; Bro et al., 2008; Ovsjanikov et al., 2008). For instance, if is an cigenvector, then so is -v, with the same eigenvalue. More generally, if an eigenvalue has higher multiplicity, then there are infinitely many unit-norm eigenvectors that can be chosen. Indeed, full set of linearly independent eigenvectors is only defined up to a change of basis in each eigenspace. In the case of sign invariance, for any k eigenvectors there are 2 possible choices of sign. Accordingly, prior works graph positional encodings randomly flip eigenvector signs during training in order to approximately learn sign invariance (Kreuzer et al., 2021; Dwivedi et al., 2020; Kim et al., 2022). However, learning all 2 invariances is challenging and limits the effectiveness of Laplacian eigenvectors for encoding positional information. Sign invariance is a special case of basis invariance when all eigenvalues distinct, but general basis invariance is even more difficult to deal with. In Appendix C.2, we show that higher dimensional eigenspaces are abundant real datasets; for instance, 64% of molecule graphs in the ZINC dataset have higher dimensional eigenspace.
"Equal contribution.

---

Published as a conference paper at ICLR 2023
In this work, we address the sign and basis ambiguity problems by developing new neural networks SignNet and BasisNet. Under certain conditions, our networks are universal and can approximate any continuous function of cigenvectors with the proper invariances. Moreover, networks are theoretically powerful for graph representation Marning-thhe can provably approximate and go beyond both spectral graph convolutions and powerful spectral invariants, which allows our networks to express graph properties like subgraph counts that message passing neural networks cannot. Laplacian eigenvectors with SignNet and BasisNet can provably approximate many previously proposed graph positional encodings, so our networks are general and remove the need for choosing one of the many positional encodings in the literature. Experiments on molecular graph regression tasks, learning expressive graph representations, and texture reconstruction on triangle meshes illustrate the empirical benefits our models' approximation power and invariances.
SIGN AND BASIS INVARIANT NETWORKS
For an symmetric matrix, let A ....S An be the eigenvalues and fi,-... Un the corre- sponding eigenvectors, which we may assume to form an orthonormal basis. For instance, we could consider the normalized graph Laplacian L D-12/ 10-1/2AD--2 1/21/2, where A E RR is the adjacency matrix and D is the diagonal degree matrix of some underlying graph. For undirected graphs, L is symmetric. Nonsymmet- ric matrices can handled very similarly, as we show in Appendix B.
k eigenvectors partitioned
дхn permutation matrix
kxk block diagonal orthogonal matrix
by eigenvalue
P
V/
V/3
V3
Motivation. Our goal is to parameterize class of models (vi,...., v&) taking &t eigenvectors as input in manner that respects the eigenvec- tor symmetries. This is because eigenvectors capture much information about data; for in- stance, Laplacian eigenvectors of graph cap- ture clusters, subgraph frequencies, connectivity, and many other useful properties (Von Luxburg, 2007; Cvetković et al., 1997).
Figure Symmetries of eigenvectors of sym- metric matrix with permutation invariances (e.g. graph Laplacian). A neural network applied to the eigenvectors matrix (middle) should be invariant or equivariant to permutation of the rows (left product with permutation matrix P) and invariant the choice of eigenvectors in each eigenbasis (right product with a block diagonal orthogonal matrix Diag( (Q1, Q2 Q3)).
major motivation for processing eigenvector input is for graph positional encodings, which are additional features appended to each node in a graph that give information about the position of that node in the graph. These additional features are crucial for generalizing Transformers to graphs. and also have been found to improve performance of GNNs (Dwivedi et al., 2020; 2022). Figure 2 illustrates a standard pipeline and the use of our SignNet within it: the input adjacency, node features, and eigenvectors of graph are used to compute a prediction about the graph. Laplacian eigenvectors are processed before being fed into this prediction model. Laplacian eigenvectors have been widely used positional encodings, and many works have noted that sign and/or basis invariance should be addressed in this case (Dwivedi & Bresson, 2021; Beaini et al., 2021; Dwivedi et al., 2020; Kreuzer et al., 2021; Mialon et al., 2021: Dwivedi al., 2022; Kim et al., 2022).
Sign invariance. For any cigenvector e; the sign flipped - is also an eigenvector, so a function f: g R dout (where dout is an arbitrary output dimension) should be sign invariant:
f(e ..., v&) f(.1v),...,554 5kUR)
(l)
for all sign choices s; E 1-) That is, we want f to be invariant to the product group 1-1, This captures all eigenvector symmetries if the eigenvalues X; are distinct and the eigenvectors are unit-norm.
Basis invariance. If the eigenvalues have higher multiplicity, then there are further symmetries. Let Vi,..., Vi be bases of eigenspaces-i.e. V, [0t columns and spans the eigenspace associated with the shared eigenvalue ,4; X Any other orthonormal basis that spans the eigenspace is of the form V.Q for some orthogonal Q E (d.)) C xdd. (see Appendix F.2). Thus, function f RaxE!_n RRu that is invariant
U1a E Ru has orthonormal
Xta,
2

---

Published as a conference paper at ICLR 2023
to changes of basis in each eigenspace satisfies
[V......; Vi) I(ViQ, ViQi), Qi O(d:).
other words, ʃ is invariant to the product group O(di) x... O(d)). The number of eigenspaces I and the dimensions d; may vary between matrices; we account for this in Section 2.2. As 0(1) {-1,1}, 1}, sign invariance a special case of basis invariance when all cigenvalues are distinct.
Permutation equivariance. For GNN models that output node features node predictions, one typically further desires f to be invariant or equivariant to permutations of nodes, i.e., along the rows of each vector. Thus, for Raxd Rnxdo typically require f(PV1. PV)) Pf(V...... Vi) for any permutation matrix P R2 Figure illustrates of the symmetries.
Universal Approximation. We desire universal models, which approximate any function in a target class. Formally, we say that class of functions Fmodel of domain X' and output space y universally approximates class of functions Fiarget if for any > O, any compact & C X, and any target function f E Frargets there exists an f E Fodee such that [[((x) - f(x)]l < e for all a Q.
Input Graph
Model
Adjacency Matrix
A
Prediction Model
Compute Eigvecs
Node
Features
X
(e.g. GNN, Transformer)
Laplacian
Eigenvectors
V
SignNet
p((((es) + o (()))))
GNN(A, [X, SignNet(V)I)
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 ((,, SignNet((V) denotes concatenation). 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 eigenvalues, node features and adjacency information desired.
2.1 WARMUP: NEURAL NETWORKS ONE EIGENSPACE
Before considering the general setting, we design neural networks that take a single eigenvector or eigenspace input and sign or basis invariant. These single subspace architectures will become building blocks for the general architectures. For one subspace, a sign invariant function is merely an even function, and is easily parameterized.
Proposition 1. A continuous function h R + IR dous is sign invariant if and only if
h(v) o(v) 6(-v)
for some continuous Φ equivariant if and only if (3) holds for continuous permutation equivariant Φ IR" + R².
R" Ro continuous R E. is sign invariant and permutation
In practice, we parameterize é by a neural network. Any architecture choice will ensure sign invari- ance, while permutation equivariance can be achieved using elementwise MLPs, DeepSets (Zaheer al., 2017), Transformers (Vaswani al., 2017), or most GNNs (Gilmer et al., 2017).
Next, we address basis invariance for a single d-dimensional subspace, i.e., we aim to parameterize maps h 1 - R that are (a) invariant to right multiplication by Q E (d), and (b) equivariant to permutations along the row axis. For (a), we use the mapping V + VVT from V to the orthogonal projector of its column space, which is ((d) invariant. Mapping V + VVT does not lose information if treat V as equivalent to VQ for any Q E O(d). This is justified by the classical first fundamental theorem of (dd) (Kraft & Procesi, 1996), which has recently been applied machine learning by Villar et al. (2021).
3

---

Published as a conference paper at ICLR 2023
Regarding (b), permuting the rows of V Pe rows and columns of VVT E R Hence, desire the function Φ Rax" + R" on VVT to be equivariant to simultaneous row and column permutations: o( (VPVV PT) Po(VVT). To parameterize such mapping from matrices to vectors, we use an invariant graph network (IGN) (Maron et al., 2018)-a neural network mapping
to and from tensors of arbitrary order R=" + IR that has the desired permutation equivariance. We thus parameterize a family with the requisite invariance and equivariance as follows:
h(V) IGN(VVT).
(4)
Proposition 2 states that this architecture universally approximates (dd) invariant and permutation equivariant functions. The full approximation power requires high order tensors to be used for the IGN; in practice, we restrict the tensor dimensions for efficiency, as discussed in the next section.
Proposition Any continuous, (d)) invariant h Rnndd Raaa is of the form h(V) = <(VVT) for a continuous 6. For a compact Z C R=xd maps of the form V + IGN(VVT) universally approximate continuous h 2 C Raxd R." that are ((d) invariant and permutation equivariant.
2.2 NEURAL NETWORKS ON MULTIPLE EIGENSPACES
To develop method for processing multiple eigenvectors (or eigenspaces), we first prove general decomposition theorem (see Appendix A for more details). Our result reduces invariance for large product group G1 X .... X G& to the much simpler invariances for the smaller constituent groups G2. Theorem 1 (Informal). Let a product of groups = G1 x ... x Gk act on X1 x ... x Xx. Under mild conditions. any continuous G-invariant function can be written f(11..... Ik) p(01(TI),.. 0x (Ix),, where oi is G2 invariant, and o, and are continuous If X3 = X₂ and G = Gj, then we can take o; 65-
Tkk
The key consequence of this result is that if we know how to design invariant models for the smaller groups G; (of size 2 for sign invariance), then get invariant models for the larger and more complex G (of size 2$ for sign invariance), without losing any expressive power. For eigenvector data, the ith eigenvector (or eigenspace) is in X, and its symmetries are described by G, Thus, we can reduce the multiple-eigenspace case to the single-cigenspace case, and leverage the models we developed in the previous section.
combine them in a simple way to
SignNet. We parameterize our sign invariant network / Raxk + Rdour on eigenvectors U....., Up as:
(5) where @ and p are unrestricted neural networks, and [:]s denotes concatenation of vectors. The form ((v,) + (())) induces sign invariance for each eigenvector. Since we do not yet impose permutation equivariance here, we term this model Linconstrainned-Sinn.a.
f(e1.... vb) p ((o(z) + o(-
To obtain a sign invariant and permutation equivariant f that outputs vectors in RuXdow, we restrict 6 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), most standard GNNs. We name this permutation equivariant version SignNet. If desired, we can use eigenvalues X; an adjacency matrix R=xn and node features X Bnnddiat by adding them arguments to
f(e Uh. Ag.... dR, X) = (lo(v,, A,, A,). + ø( o0-u, A,, A, A))
(6)
BasisNet. For basis invariance, let V, E Ra be orthonormal basis of d; dimensional eigenspace. Then we parameterize our Unconstrained Basissee f by
f(V,..., V/) p (V.V
where each Qd, is shared amongst all subspaces of the same dimension d,, and is the number of eigenspaces (i.e., number of distinct eigenvalues, which can differ from the number of eigenvectors k). As / differs between graphs, we may use zero-padding or a sequence model like a Transformer to parameterize p. Again, d4;; and p are generally unrestricted neural networks. To obtain permutation cquivariance, we make P permutation equivariant and let da, = IGN,, RR" + R" be IGNs from matrices to vectors. For efficiency, we will only use matrices and vectors in the IGNs (that is, no tensors in Rnd for > 2), i.e., we use 2-IGN (Maron et al., 2018). Our resulting BasisNer is
J(V,.... Vi) p (IGNa, (V.VT))))
(8)
4

---

Published as a conference paper at ICLR 2023
Expressive-BasisNet. While restrict SignNet to only vectors and BasisNet to only vectors and matrices, higher order tensors are generally required for universally approximating permutation equivariant invariant functions (Keriven & Peyré, 2019; Maron et al., 2019; Machara & NT. 2019). Thus, we will consider a theoretically powerful but computationally impractical variant of model, in which replace p and IGNa, in BasisNet with IGNs of arbitrary tensor order. We call this variant Expressive-BasiiNee. Universal approximation requires O(n") sized intermediate tensors (Ravanbakhsh, 2020). We study Expressive-Basd Basisseet due its theoretical interest, and to juxtapose with the computational efficiency and strong expressive power of SignNet and BasisNet.
In the multiple subspace case, we can prove universality for some instances of our models through our decomposition theorem- see Section A for details. For a summary of properties and more details about our models, see Appendix B.
THEORETICAL POWER FOR GRAPH REPRESENTATION LEARNING
Next, establish that our SignNet and BasisNet go beyond useful basis invariant and permutation equivariant functions on Laplacian eigenvectors for graph representation learning, including: spectral graph convolutions, spectral invariants, and existing graph positional encodings. Serressive-Basis.. can of course compute these functions, but this section shows that the practical invariant architectures SignNet and BasisNet can compute them well.
3.1 SIGNNET AND BASISNET STRICTLY GENERALIZE SPECTRAL GRAPH CONVOLUTION
For node features X E Baxdea and an cigendecomposition VAVT, spectral graph convolution takes the form AV A, XX) = Σ. 0,0,u, X DDiag(0)V X, for some parameters 0,, that may optionally be continuous functions h(),) = 0₂ of the eigenvalues (Bruna et al., 2014; Defferrard et al., 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 node-wise linear maps, e.g. DDiag(00) (22) a (VDiag(() V XWi) 1) W2 is a two layer spectral permutation equivariant
GNN. It can be seen (in Appendix H.1) 1) that spectral graph convolutions and sign invariant, and if 02 = h(A²)) (i.e. the transformation applied to the diagonal elements is parametric) they additionally invariant
change of bases in each eigenspace.
Our SignNet and BasisNet can be viewed as generalizations of spectral graph convolutions, as our networks universally approximate all spectral graph convolutions of the above form. For instance,
SignNet with p(a1, .......... ..) Σi= Ok and d(e,, A, X) = v., directly yields the spectral graph convolution. This is captured in Theorem 2, which we prove in Appendix H.1. In fact, we may expect SignNet learn spectral graph convolutions well, according the principle of algorithmic alignment (Xu et al., 2020) (see Appendix H.1); this is supported by numerical experiments in Appendix J.3, in which our networks outperform baselines in learning spectral graph convolutions.
Theorem 2. SignNet universally approxinates all spectral graph convolutions. BasisNet universally approximates all parametric spectral graph convolutions.
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. This is captured in Proposition 3: networks can distinguish bipartite graphs from non-bipartite graphs, but spectral GNNs cannot for certain choices of graphs and node signals.
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.
3.2 BASISNET 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 on graphs like subgraph counts (Chen et al., 2020: Tahmasebi al., 2020). These works often compare GNNs to combinatorial invariants on graphs, especially the k- A-Weisfeiler-Lemaan (k- (--WL) tests of graph isomorphism (Morris al., 2021).
A function class Fmoded distinguishes graphs G1, G2 there E Fmode: such that f(G1) # f(G2).
5

---

Published as a conference paper at ICLR 2023
While 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 imvariants, which are computed from the eigenvalues and cigenvectors of graphs There is a rich literature of spectral invariants from the fields of spectral graph theory and complexity theory (Cvetković et al., 1997). For a spectral invariant to be well-defined, it must be invariant to permutations and changes of basis in each eigenspace, a characteristic shared by our networks.
The simplest spectral invariant is the multiset of eigenvalues, which we give as input our networks. Another widely studied, powerful spectral invariant is the collection of graph angles, which are defined as the values aij VIV,V, eyll2. where Vi Raxd, is an orthonormal basis for the ith adjacency matrix eigenspace, and ej is the jth standard basis vector, which is zero besides a 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).
Theorem 3. BasisNet universally approximates the graph angles auj. The eigenvalues and graph angles (and thus BasisNet) can determine the number of length 3, or 5 cycles, whether a graph is connected, and the number of length k closed walks from any vertex to itself.
Relation to WL and message passing. In contrast to this result, message passing GNNs not able to express any of these properties (see (Arvind et al., 2020; Garg et al., 2020) and Appendix H.3). strong, Fürer (2010) shows that the eigenvalues and graph angles-as well as some strictly stronger spectral invariants- are not stronger than the 3-WI. test (or, equivalently, the 2-Folklore-V WerreeLLLsssssst test). Using our networks for node positional encodings in message passing GNNs allows us to go beyond graph angles, as message passing can distinguish all trees, but there exist non non-isomorphic trees with the same eigenvalues and graph angles (Fürer, 2010; Cvetković, 1988).
Although spectral invariants
3.3 SIGNNET AND BASISNET GENERALIZE EXISTING GRAPH POSITIONAL ENCODINGS
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 approximate many previously used graph positional encodings, as we unify these positional encodings by expressing them as either a spectral graph convolution matrix or the diagonal of a spectral graph convolution matrix.
Proposition 4. SignNet and BasisNet can approximate node positional encodings based on heat kernels (Feldman et al., 2022) and random walks (Dwivedi et al., 2022). BasisNet can approximate diffusion and p-step random walk relative positional encodings (Mialon et al., 2021), I), and generalized PageRank and landing probability distance encodings (Li et al., 2020).
4 EXPERIMENTS
We demonstrate the strength of our networks in various experiments. Appendix shows simple pseudo-code and Figure 2 is diagram detailing the use of SignNet as a node positional encoding.
4.1 GRAPH REGRESSION
We study the effectiveness of SignNet for learning positional encodings (PEs) from the eigenvectors of the graph Laplacian on the ZINC dataset of molecule graphs (Irwin et al., 2012) (using the subset of 12,000 graphs from Dwivedi et al. (2020)). We primarily consider three settings: 1) No positional encoding, 2) Laplacian PE (LapPE) the & 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 GIN (Xu et al., 2019) and to be an MLP. We sum over outputs before the ML.P when handling variable numbers of eigenvectors, the SignNet is of
((vx) + 6(-v:) (see Appendix K.2 for further details). We consider four different base models that process the graph data and positional encodings: GatedGCN (Bresson & 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 500k budget.
the form MLP [Ein

---

Published as a conference paper at ICLR 2023
Table 1: Results on the ZINC dataset with a 500k parameter budget. All models use edge features besides the Sparse Transformer. Numbers are the mean and standard deviation over 4 runs, each with different seeds.
Base model
Positional encoding
k
#param
Test MAE (4)
No PE
N/A
492k
0.252 00000
LapPE (flip)
492k
0.198 1.198&0.011 40.011
LapPE (abs.)
492k
1.2044:0.000
GatedGCN
LapPE (can.)
8
505k
0.298
SignNet (Ø(v) only)
495k
0.148
SignNet
495k
0.121 000
SignNet
491k
0. 00100
No PE
N/A
473k
0.283 +0.0000
LapPE (flip)
16
487k
0.22310.007
Sparse Transformer
SignNet
16
179k
0.11510..00 006
SignNet
AlI
486k
0.102
No PE
N/A
470k
0.170
LapPE (tlip)
16
470k
0.178
GINE
SignNet
16
470k
0.147
SignNet
All
417k
0.10220.002
PE
N/A
474K
0.133
LapPE (Ilip)
474k
0.132
PNA
SignNet
8
476k
0.105
SignNet
All
487k
0.084
Table 2: Comparison with SOTA methods graph-level regression tasks. Numbers are test MAE, lower is better. Best models within a standard deviation are bolded.
ZINC (10K) 4
ZINC-full 4
Alchemy (10k)
GIN (Xu et al., 2019)
.170..002
.8882.002
.1804.006
d-2-GNN (Morris et al., 2020b)
3744.022
.0421.003
.118
6-2-LGNN (Morris et al., 2020b)
306+.044
.0454.006
.1224.003
SpeqNet (Morris et al., 2022)
.115+.001
GNN-IR (Dupty & Lec, 2022)
1377.000
.119 +.02
PF-GNN (Dupty et al., 2021)
.1222.01
:.01
Recon-GNN (Cotta et al., 2021)
.1702.006
.125
SignNet (ours)
.084
.0244.003
.113
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. This includes the cases of PNA and GINE, for which Laplacian PE with random sign flipping unable improve performance Our best model a PNA model combined with SignNet, which achieves 0.084 test MAE. Besides SignNet, we consider two non-learned approaches to resolving eigenvector sign ambiguity- canonicalization and element-wise absolute values (see Appendix K.2 for details). Results with GatedGCN show that these alternatives are not more effective than random sign flipping. We also consider an ablation of our SignNet architecture where we remove the sign invariance, using simply (L)(((();)]
using PE.
Although the resulting architecture is no longer sign invariant, & still processes eigenvectors independently. meaning that only two invariances (++) need be learned, significantly fewer than the 2 total sign flip configurations. Accordingly, this non-sign-invartee encoding achieves test MAE of 041,, 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; this is notable as other works typically truncate to a fixed number of eigenvectors.
learned positional
Efficiency. These significant performance improvements from SignNet come with only a slightly higher computational cost. For example, GatedGCN with no PE takes about 8.2 seconds per training iteration on ZINC, while GatedGCN with 8 eigenvectors and SignNet takes about 10.6 seconds;
7

---

Published as a conference paper at ICLR 2023
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 4
LPIPS 4
PSNR f
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
this is only a 29% increase time, for a reduction of test MAE by over 50%. Also, eigenvector computation time is neglible, as we need only precompute and save the eigenvectors once, and it only takes seconds to do this for the 12,000 graphs of ZINC.
Comparison with SOTA. In Table 2, compare SignNet with other domain-agnosta state-of-the art 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). SignNet outperforms all methods on ZINC and ZINC-full. Our mean score is the second best on Alchemy, and is within a standard deviation of the best. We perform much better ZINC (.084) than other state-of-the-ar positional encoding methods, like GNN-LSPE (.090) (Dwivedi et al., 2022), SAN (.1 (.199) (Kreuzer al., 2021), and Graphormer (.122) (Ying et al., 2021).
4.2 COUNTING SUBSTRUCTURES AND REGRESSING GRAPH PROPERTIES
ofgsefTest MSE)
Test MAE
LapPE
0.2
SignNet
Triangle
Tailed
4-Cycle
Star
IBConnected
Diameter
Radius
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 are 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 biology, chemistry, and social networks (Chen et al., 2020; Holland & Leinhardt, 1977). 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 4-layer GIN the base model for all settings, and for SignNet we use GIN as 6 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 augmentation improve performance for counting substructures but not for regressing graph properties, while Laplacian PEs processed by SignNet significantly boost performance on all tasks.
4.3 NEURAL FIELDS ON MANIFOLDS
Discrete approximations the Laplace- Laplace-Beltram 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 the Laplace-Beltrant operator as positional encodings for learning neural fields manifolds. For generalized eigenfunctions Vi..... Uk. at a point on the surface, they parameterize functionn f(p) = MLP(01 (p)..... vx (p)). As these eigenfunctions have sign ambiguity, we p(-0; ((-=o;p))))=....... ), with p and ø being MLPs.
SignNet parameterize f(p) MLP (p)x
Table 3 shows results for texture reconstruction experiments all models from Koestler al. (2022). The total number of parameters in our SignNet- based model kept below that of the original model. We that the SignNet architecture improves over the original Intrinsic NF model and over
8

---

Published as a conference paper at ICLR 2023
other baselines especially in the LPIPS metric, which is often better perceptual metric than PSNR or DSSIM (Zhang et al., 2018a). While we have not yet tested this, we believe that SignNet would allow even more improvement when learning over cigenfunctions of different models, it could improve transfer and generalization. See Appendix D.1 for visualizations and Appendix K.5 for more details.
4.4 VISUALIZATION OF LEARNED POSITIONAL ENCODINGS
Eigvec 11
((11) + 6(-v11)
Eigvec 14
@(M1)) + 6(-m14)
Figure 4: Cotangent Laplacian eigenvectors of the cat model and first principal component of Φ(v) + 6(-r) from our trained SignNet. Our SignNet encodes bilateral symmetry, which useful for reconstruction of the bilaterally symmetric texture.
To better understand SignNet, we plot the first principal component of Φ(v) + o(-v) for two eigenvectors the cat model in Figure 4. We see that SignNet encodes bilateral symmetry and structural information on the cat model. See Appendix for more visualizations and further details.
RELATED WORK
In this section, we review selected related work. A more thorough review is deferred to Appendix
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 message passing GNN (Dwivedi et al., 2020; 2022), or some variant of a Transformer that is adapted to graphs (Dwivedi & Bresson, 2021; Kreuzer et al., 2021; Mialon et al., 2021; Dwivedi et al., 2022; Kim 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.
Graph positional encodings. Other recent methods positional encodings besides Laplacian eigenvectors. These include positional encodings based on random walks (Dwivedi et al., 2022; Mialon al., 2021; Li et 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 et al., 2022). In particular, Wang al. (2022) use 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).
CONCLUSION AND DISCUSSION
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 under certain conditions. When used with Laplacian eigenvectors as inputs they provably go beyond spectral graph convolutions, spectral invariants, and number of other graph positional encodings. These theoretical results are supported by experiments showing that SigmNet 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, as eigenvectors ubiquitous in machine learning.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
We thank anonymous reviewers of this work, especially those of the Topology, Algebra, and Geometry Workshop at ICML 2022, for providing useful feedback and suggestions. We thank Leonardo Cotta for a discussion about automorphism symmetries in real-world and random graphs (Appendix C.3 and C.4), We thank Truong Son Hy for sending us some useful PyTorch codes for invariant graph networks. Stefanie Jegelka and Suvrit Sra acknowledge support from NSF CCF-21 12665 (TILOS Al Research Institute) and NSF BIGDATA IIS- 1754171144. Stefanie Jegelka also acknowledges support from NSF Award 2134108 and NSF Convergence Accelerator Track D 2040636 and NSF C-ACCEI. D636 CRIPT Phase 2. Suvrit Sra acknowledges support from NSF CAREER grant (IIS-1446088). Joshua Robinson partially supported by a Two Sigma fellowship. Derek Lim supported by an NSF Graduate Fellowship.
REFERENCES
Vikraman Arvind, Frank Fuhlbrüick, Johannes Köbler, and Oleg Verbitsky. On weisfeiler-leman invariance: Subgraph counts and related graph properties. In Journal of Computer and System Sciences, volume 113, pp. 42-59. Elsevier, 2020.
Lá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, pp. 310-324, 1982.
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 spectral perspective. In Int. Conference on Learning Representations (ICLR), volume 2020.
Fabian Ball and Andreas Geyer-Schulz. How symmetric real-world graphs? a large-scale study. Symmetry, 10(1):29, 2018.
Dominique Beaini, Saro Passaro, Vincent Létourneau, Will Hamilton, Gabriele Corso, and Pietro Liò. Directional graph networks. In Int. Conference on Machine Learning (ICML), pp. 748-758. PMLR, 2021.
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation, 15(6):1373-1335) 2003.
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.
Filippo Maria Bianchi, Daniele Grattarola, Lorenzo Livi, and Cesare Alippi. Graph neural networks with convolutional arma filters. In IEEE transactions on puttern analysis and machine intelligence. IEEE, 2021.
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.
Xavier Bresson and Thomas Laurent. Residual gated graph ConvNets. In preprint arXiv: 1xXXv:1711.07555 2017.
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 Society, 22(2):135-140, 2008.
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 2017.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and deep locally connected networks on graphs. In Int. Conference on Learning Representations (ICLR), volume 2014.
10

---

Published as a conference paper at ICLR 2023
Chen Cai and Yusu Wang. Convergence of invariant graph networks. In preprint arXiv:220.110129 2022.
Ines Chami, Sami Abu-EI-Haija, Bryan Perozzi, Christopher Ré, and Kevin Murphy. Machine learning on graphs: model and comprehensive taxonomy. In preprint arXiv:2005.088 20020000000.5, 2020.
Guangyong Chen, Pengfei Chen, Chang-Yu Yu Hsich, Chee-Kong Lee, Benben Liao, Renjie Liao, Weiwen Liu, Jiezhong Qiu, Qiming Sun, Jie Tang, al. Alchemy: quantum chemistry dataset for benchmarking ai models. arXiv preprint 19xi::90660000
2019a.
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, pp. 1589-15000 15902, 2019b.
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, pp. 10383-10395, 2020.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovie. Adaptive universal generalized pagerank graph neural network. Int. Conference on Learning Representations (ICLR), volume 9, 2021.
Fan Chung. Spectral graph theory. American Mathematical Soc., 1997.
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pictro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, pp. 13260- 13200,1131,,.00 2020.
Leonardo Cotta, Christopher Morris, and Bruno Ribeiro. Reconstruction for powerful graph rep- resentations. In Advances Neural Information Processing Systems (NeurIPS), volume 34, 2021.
Dragoš Cvetković. Constructing trees with given eigenvalues and angles. Linear Algebra and its Applications, 105:1-8, 1988.
Dragoš Cvetković. Some comments on the eigenspaces of graphs. Publ. Inst. Math. (Beograd) 50 (64):24-32, 1991.
Dragoš Cvetković, Peter Rowlinson, and Slobodan Simic. Eigenspaces of graphs. Number 66 in Encyclopedia of Mathematics and its Applications. Cambridge University Press, 1997.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering, In Advances Neural Information Processing Systems (NeurIPS), volume 29, pp. 3844-3852, 2016.
Mohammed Haroon Dupty and Wee Sun Lee. Graph representation learning with individualization and refinement. arXiv preprint arXiv:2203.0914. 2022.
Mohammed Haroon Dupty, Yanfci Dong, and Wee Sun Lee. Pf-gnn: Differentiable particle fil- tering based approximation of universal graph representations. In Int. Conference on Learning Representations (ICLR), 2021.
Vijay Prakash Dwivedi and Xavier Bresson. A generalization transformer networks to graphs. In AAAI Workshop Deep Learning Graphs: Methods and Applications, 2021.
Vijay Prakash Dwivedi, Chaitanya Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. In preprint arXiv:2003.00982 2020.
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. In Int. Conference on Learning Representations (ICLR), volume 10, 2022.
HT Eastment and WJ Krzanowski. Cross Cross-vali choice of the number of components from principal component analysis. Technometrics, 24(1):73-77, 1982.

---

Published as a conference paper at ICLR 2023
Paul Erdos and Alfréd Rényi. Asymmetric graphs. Acta Math. Acad. Sci. Hungar, 14(295-315)3. 1963.
Or Feldman, Amit Boyarski, Shai Feldman, Dani Kogan, Avi Mendelson, and Chaim Baskin. Weisfeiler and leman go infinite: Spectral and combinatorial pre-colorings. In preprini arXiv:2201. 13410, 2022.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. In ICLR (Workshop on Representation Learning on Graphs and Manifolds), volume 7, 2019.
Matthias Fey, Jan- Gin Yuen, and Frank Weichert. Hierarchical inter-message passing for learning on molecular graphs. arXiv preprint arXiv:2006. 12179, 2020.
Martin Fürer. On the power of combinatorial and spectral invariants. Linear algebra and its applications, 432(9)::373-2388 2010.
Jean Gallier and Jocelyn Quaintance. Differential geometry and Lie groups: computational perspective, volume 12. Springer Nature, 2020.
V. K. Garg. S. Jegelka, and T. Jaakkola. Generalization and representational limits of graph neural networks. In Int. Conference on Machine Learning (ICML), 2020.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp. 1272- PMLR, 2017.
Juan Navarro González. and Juan Sancho de Salas. C C*-differeentiable spaces, volume 1824. Springer, 2003.
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, pp- 855 864, 2016.
Will Hamilton. Graph representation learning. Synthesis Lectures on Artifical Intelligence and Machine Learning, 14(5):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.
Paul W Holland and Samuel Leinhardt. A method for detecting structure in sociometric data. In Social networks, pp. 411 412-432, Elsevier, 1977.
Roger A Hor and Charles R Johnson. Matrix analysis. Cambridge university press, 2012.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, pp. 22118 11118-2213,,31 2020a.
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitmik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre- pre-training graph neural networks. In Int. Conference on Learning Representations (ICLR), volume 8, 2020b.
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), pp. 289-297. SIAM, 2021.
John J Irwin, Teague Sterling, Michael M Mysinger, Erin S Bolstad, and Ryan G Coleman. Zinc: free tool to discover chemistry for biology. Journal of chemical information and modeling, 52(7): 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.
12

---

Published as a conference paper at ICLR 2023
Jinwoo Kim, Saeyoon 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.
Jinwoo Kim, Tien Dat Nguyen, Seonwoo Min, Sungjun Cho, Moontae Lee, Honglak Lee, and Seunghoon Hong. Pure transformers are powerful graph learners. arXiv preprini arXiv:2207.02550 2022.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 141166980, 2014.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In Int. Conference on Learning Representations (ICLR), volume 5, 2017.
Lukas Koestler, Daniel Grittner, Michael Moeller, Daniel Cremers, and Zorah Lähner. Intrinsic neural fields: Learning functions manifolds. arXiv preprint arXIv:2203.07967, 2022.
Hanspeter Kraft and Claudio Procesi. Classical invariant theory, a primer. Lecture Notes., 1996.
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.
John M Lee. Smooth manifolds. In Introduction to Smooth Manifolds. Springer, 2013.
Thomson Leighton and Gary Miller. Certificates for graphs with distinct eigen values. Orginal Manuscript, 1979.
Ron Levie, Federico Monti, Xavier Bresson, and Michael Bronstein. Cayleynets: Graph con- volutional neural networks with complex rational spectral filters. IEEE Transactions Signal Processing, 67(1):97-109, 2018.
Bruno Lévy. Laplace-beltrami eigenfunctions towards an algorithm that" understands" geometry. In IEEE International Conference on Shape Modeling and Applications 2006 (SMI006), pp. 13-13. IEEE, 2006.
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.
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design prov- ably more powerful neural networks for graph representation learning, In Advances in Neural Information Processing Systems (NeurIPS), volume 33, pp. 4465-4478, 2025.
Takanori Maehara and Hoang NT. A simple proof of the universality of invariant/equivariant graph neural networks. arXiv preprint 1rXiv:19/0.033802, 2019.
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.
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. Int. Conference on Machine Learning (ICMI.), pp. 4363 4371. PMIR, 2019.
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, pp. 43-52, 2015.
Grégoire Mialon, Dexiong Chen, Margot Selosse, and Julien Mairal. GraphiT: Encoding graph structure in transformers. In preprint arXiv:2106.0566) 2021.
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 Graph Representation Learning and Beyond, 2020a.
13

---

Published as a conference paper at ICLR 2023
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.
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:21 12.00999,, 2021.
Christopher Morris, Gaurav Rattan, Sandra Kiefer, and Siamak Ravanbakhsh. Speqnets: Sparsity- aware permuaation-euuivarian graph networks. arXiv preprini arXiv:2203. 13913, 2022.
Arvind Narayanan and Vitaly Shmatikov. De-anonymizing social networks. 2009 30th IEEE symposium security and privacy, pp. 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 (5):808 828, 2018
Maks Ovsjanikov, Jian Sun, and Leonidas Guibas. Global intrinsic symmetries of shapes. In Computer graphics forum, volume 27, pp. 1341-1348. Wiley Online Library, 2008
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 on World Wide Web, pp. 201-210, 2007.
Pál András Papp. Karolis Martinkus, Lukas Faber, and Roger Wattenhofer. Dropgnn: random
dropouts increase the expressiveness of graph neural networks. Advances in Neural Information Processing Systems, 34, 2021.
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 Veto,, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, gegh-performance deep learning library. In Advances in Neural Information Processing Systems (NeurIPS), pp. 8024-8035. Curran Associates, Inc., 2019.
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, pp. 701-710, 2014.
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.
Siamak Ravanbakhsh. Universal equivariant multilayer perceptrons. In International Conference on Machine Learning, pp. 7996-8006. PMLR, 2020.
Kaspar Riesen and Horst Bunke. lam graph database repository for graph based pattern recognition and machine learning. In Joint IAPR International Workshops on Statistical Techniques in Pattern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR), pp. 287-297. Springer, 2008.
Raif M Rustamov al. Laplace-beltrami eigenfunctions for deformation invariant shape representa- tion. In Symposium on geometry processing, volume 257, pp. 225-233, 2007.
Horst Sachs and M Stiebitz. Automorphism group and spectrum of graph. In Studies in pure mathematics, pp. 587-604. Springer, 1983.
Ryoma Sato. A survey on the expressive power of graph neural networks. In preprint arXiv:2003.04078. 2020.
Nimrod Segol and Yaron Lipman. On universal equivariant set networks. In Int Conference on Learning Representations (ICLR), volume 7, 2019.
14

---

Published as a conference paper at ICLR 2023
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Ehiass--Rad. Collective classification in network data. Al magazine, 29(3):93 93, 2008.
Oleksandr Shchur, Maximilian Mumme, Alcksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. In NeurlPS Workshop on Relational Representation Learning. 2018.
Balasubramaniam Srinivasan and Bruno Ribeiro. On the equivalence between positional node embeddings and structural graph representations. In Int. Conference on Learning Representations (ICLR), 2019.
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.
Behrooz Tahmasebi, Derek Lim, and Stefanie Jegelka. Counting substructures with higher-order graph neural networks: Possibility and impossibility results. In preprint arXiv:2012.03/74 2020.
Edric Tam and David Dunson. Multiscale graph comparison via the embedded laplacian distance. In preprint arXiv:2201.12066 2022.
Terence Tao and Van Vu. Random matrices have simple spectrum. Combinatorica, 37(3):539-553,
2017.
Yasuo Teranishi. Eigenvalues and automorphisms of graph. Linear and Multilinear Algebra, 57(6): 577-585, 2009.
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 graph. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, pp. 2347-2356, 2018.
Fabio Urbina, Filippa Lentzos, Cédric Invernizzi, and Sean Ekins. Dual use of artiffcial-inteliiennee- powered drug discovery. Nature Machine Intelligence, (3):189-191. 2022.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in Neural Information Processing Systems (NeurIPS), volume 30, pp. 5998 6008,008800 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. Int. Conference on Learning Representations (ICLR), volume 6, 2018.
Saurabh Verma and Zhi-Li Zhang. Hunt for the unique, stable, sparse and fast feature learning graphs. In Advances in Neural Information Processing Systems (NeurIPS), volume 30, pp. 88-98, 2017.
Soledad Villar, David Hogg. Kate Storey-Fisher, Weichi Yao, and Ben Blum-Smith Scalars universal: Equivariant machine learning. structured like classical physics. In Advances Neural Information Processing Systems (NeurIPS), volume 34, 2021.
Ulrike Von Luxburg. A tutorial on spectral clustering. Statistics and computing, 17(4):395 2007.
Haorui Wang, Haoteng Yin, Muhan Zhang, and Pan Li. Equivariant and stable positional encoding for more powerful graph neural networks. In Int. Conference on Learning Representations (ICLR), volume 10, 2022.
Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma. Lingfan Yu, Yu Gai, al. Deep graph library: A graph-centric, highly-pe package for graph neural networks. arXiv preprint 190.v:1909.01315 2019.
Hassler Whitney. The self-intersections of smooth n n-manifold in 2n-space. In Annals of Mathemat- ics, pp. 220-246, 1944.
15

---

Published as a conference paper at ICLR 2023
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-5533 530, 2018.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S Yu. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 32(1):4 244 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In Int. Conference on Learning Representations (ICLR), volume 7, 2019.
Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. What can neural networks reason about? In Int. Conference on Learning Representations (ICLR), volume 8, 2020.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1365-1374, 2015.
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Ya Liu. Do transformers really perform badly for graph representation? In Advances in Neural Information Processing Systems (NeurIPS), volume 34, 2021.
Jiaxuan You, Jonathan M Gomes-Selman Rex Ying, and Jure Leskovec. Identity- graph neural networks. In Association for the Advancement of Artificial Intelligence (AAAI), volume 35, pp. 10737-10745, 2021. 2021.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander J Smola. Deep sets. In Advances in Neural Information Processing Systems (NeurIPS), volume 30, pp. 3391-3401, 2017.
Jiawei Zhang, Haopeng Zhang, Congying Xia, and Li Sun. Graph-BERT: Only attention is needed for learning graph representations. In preprint arXiv:2001.05140, 2020.
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, pp. 586-595, 2018a.
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, pp. 3964-3974, 2018b.
Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any GNN with local structure awareness. In lnt. Conference Learning Representations (ICLR), volume 10, 2022.
16

---

Published as a conference paper at ICLR 2023
A UNIVERSALITY FOR MULTIPLE SPACES
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. Under certain conditions, the universality of our architectures follows as a corollary of the following general decomposition result, which may enable construction of universal architectures for other invariances as well.
Theorem 4 (Decomposition Theorem). Let XI...., be topological spaces, and let G3 be group acting on X; for each We assume mild topological conditions on X; and G; hold. For any continuous X = X1 x ....% X 2s - Rdouu that is invariant the action of G G1 ... x Gk. there exists continuous @; and a continuous p: 2: IR"
Rdow such that
f(v1..... ub) = p(or(1i)...... ox(U)))
(9)
Furthermore: (1) each di can be taken to be invariant to Go (2) the domain 2 of p is compact if each X, is compact, (3) if X; = X3 and G, = G. then o5 can be taken to be equal to Øj-
This result says that when a product of groups G acts on a product of spaces X, for invariance the product group G it suffices to individually process each smaller group G2 on 2; and then aggregate the results. Along with the proof of Theorem 4, the mild topological assumptions are explained in Appendix 1. The assumptions hold for sign invariance and basis invariance, when not enforcing permutation equivariance. By applying this theorem, we can prove universality of some instances of networks:
Corollary 1. Unconstrained- -iggNNet can represent any sign invariant function and Unconstrained- BasisNet can represent any basis invariant function. Expressive Sspressive-aasiiNet is a universal approximator functions that are both basis invariant and permutation equivariant.
This result shows that Sicconstrained-Sinhlee take the correct functional form for their respective invariances (proofs in Appendix G.2). Note that Expressive- Expressive-BasisNet approximates all sign invariant functions as special case, by treating all inputs as one dimensional eigenspaces. Further, note that we require Expressive-BasisNert high order tensors to achieve universality when enforcing permutation equivariance. Universality under permutation equivariance is generally difficult to achieve when dealing with matrices with permutation symmetries (Maron et al., 2019; Keriven & Peyré, 2019), but it may be possible that more efficient architectures can achieve it in our setting.
Unconstrained -taisssrriinedBBBiSeettet and Expressivv-BaasisNe
Accompanying the decomposition result, show corresponding universal approximation result (proof in Appendix G.3). Similarly to Theorem 4, the problem of approximating = G₁ x... Gk invariant functions is reduced approximating several Gi-invariant functions.
B MORE DETAILS ON SIGNNET AND BASISNET
Table 4: Properties of our architectures: Unconstrained--iinnle SignNet, eecconstrained-Basistee. and Expressive- BasisNet. The properties are: permutation equivariance, universality (for the proper class of continuous invariant functions), and computational tractability.
Aicconstr-SSinNee
SignNet
Unconstr-BasisNG
BasisNet
Expr.BasisNeet
Perm. equivariant
Universal Tractable
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 5, we give pseudo-code of SignNet for learning node positional encodings with a GNN prediction model.
17

---

Published as a conference paper at ICLR 2023
PyTorch-like pseudo-code for SignNet
class SignNetGHII (mm.aduule..
def -- Liiit__.. (self, self phi = GIN(1, D1) # in dim=1, out din=D1
D1, D2, out_dim):
self.rho MLP(k++11, D2)
base_model CNN(d+D2, out_dim)
def forxard(salf,
eigvecs):
g contains graph information
shape:
eigvecs shape:
n, eigvecs.
eigvecs eigvecs reshapee k, 1)
pe self.phi(g, eigvecs) + self -elff.hi (g, -eggveca) pe (u, -1) # a k D1 -> k4D1
pe self-rho(pe)
return self base model (g, pa)
Figure PyTorch-like pseudo-code for using SignNet with a GNN prediction model, where e GIN and p MLP as in the ZINC molecular graph regression experiments. Reshaping eigenvectors from
1 allows ø to process each eigenvector (and its negation) independently in Py PyTorch-like deep learning libraries.
B. GENERALIZATION BEYOND S SYMMETRIC MATRICES
In the main paper, we assume that the eigenspaces come from symmetric matrix. This holds for many cases of practical interest, as e.g. the Laplacian matrix of undirected graph is symmetric. However, we may also want to process directed graphs, or other data that have associated nonsymmetric matrices. Our SignNet and NasisNet generalize matrices, as we detail here. Let A E Rax= be a matrix with a diagonalization A = VAV-! where Diag(A1.- An) contains the eigenvalues A and the columns of V [0] ... Vn. are eigenvectors. Suppose we want to learn a function on the eigenvectors UI,..., Unlike in the symmetric matrix case, the eigenvectors are not necessarily orthonormal, and both the eigenvalues and eigenvectors can be complex.
straightforward way handle nonsymmetric diagonalizable
Real eigenvectors. First, we assume the eigenvectors v; are real vectors in R We can take the eigenvectors to be real if A is symmetric, or if A has real eigenvalues (see Horn & 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 we have that cu is an eigenvector of the same eigenvalue. the eigenvalues are distinct, then the eigenvectors of the form are the only other eigenvectors in the same eigenspace u. Thus, want a function to be invariant to scalings:
R \ {0} and eigenvector
f(r
2k) f(eim,,...
c E TR| (0).
(10)
This can be handled by SignNet, by giving umit normalized vector inputs:
f(ei....,.. vx) P (1b(vs//lvx]]) + oi (
(11)
Now, say have bases of eigenspaces Vi...., Vi with dimensions di,.... dj. For basis V,, have that any other basis of the same space can be obtained as V.W for some W E GLg(d,), the set of real invertible matrices in Rdd Indeed, the orthonormal projector for the space spanned by the columns of V, is given by VG(V, V. Thus, if Z E R is another basis for the column space of V., we have that VIVV - = 7(7 7) -T so
Vi(V, - 2 Z(Z -
(12)
so let W VV TTZ E pd.xd. Note that W invertible, because it has inverse (Z Z) 10- Z TTV, so indeed V.W Z for W GLR(d.). Thus, basis invariance in this case is
of the form
S(V. ....,, Vi) SVW,,,....... ..... VW))
W, E GLa(d))
(13)
18

---

Published as a conference paper at ICLR 2023
Note that the distinct eigenvalue invariance is special case of this invariance, as G1((1) = R \ {0].
We can again achieve this basis invariance by using a BasisNet, where the inputs to the Φz, are orthogonal projectors of the corresponding eigenspace:
S(V,,-- -.....1 Vi) ( (V.VV 'V, 1. I.m......
(14)
Recall that if V; is an orthonormal basis, then the orthogonal projector is just V.V,T, so this is a direct generalization of BasisNet in the symmetric case.
Complex eigenvectors. More generally, suppose V 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
f(cI,..., vk) f(erv),...., CkUR)
c: E &EC (O).
(15)
However, this symmetry can not be as easily reduced to a unit normalization and a discrete sign invariance, it be in the real case. Nonetheless, the basis invariant architecture directly generalizes, so we can handle the case of distinct eigenvalues by a more general basis invariant architecture well. The basis invariance is
S(V,, Vi) SVV 1...., VW)
W. GLc(d).
(16)
The orthogonal projector of the image of V, is V.(V;VV)) - 'V,, where there are conjugate transposes replacing the transposes. Thus, BasisNet takes the form:
J(V Vi) = (VVVVVV (V))....))
(17)
B.2 BROADER IMPACTS
We believe that our models and future sign invariant or basis invariant networks could be useful in a wide variety of applications. As eigenvectors arise in many domains, it is difficult predict the uses of these models. We test on several molecular property prediction tasks, which have the potential for much positive impact, such in drug discovery (Stokes al., 2020). However, recent work has found that the same models that we use for finding beneficial drugs can also be used to design biochemical weapons (Urbina et al., 2022). Another major application of graph machine learning is in social network analysis, where positive (e.g. malicious node detection (Pandit et al., 2007)) and negative (e.g. deanonymization (Narayanan & Shmatikov, 2009)) uses of machine learning are possible. Even if there is no 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.
B.3 COMPLEXITY OF SIGNNET AND BASISNET
Here, we give simplified but intuitive analysis of the complexity of SignNet and BasisNet. Suppose we have graph nodes, with & eigenvectors "
A standard GNN that naively inputs the eigenvectors node features forms tensors of size O(nk nd), where is the hidden dimension of the learned node features.
SignNet forms tensors of size ((kkd), where d is the hidden dimension or output dimension of Φ. This is because for each the 2 eigenvectors v; and -U;, we must put through our & network.
Similarly, BasisNet forms tensors of size (nnld)) where / is the number of eigenspaces and d is the hidden dimension or output dimension of the Φd,- Thus, there is an extra multiplicative factor of when compared with SignNet. If we instead use p-IGNs with order p tensors, then the complexity is (nPld).
Moreover, note that naive version of BasisNet requires separate IGN to be learned for each multiplicity d, This may be intractable for datasets with eigenspaces of many sizes. One way to get around this would be to parameterize single IGN, and define du, (V.VT))
IGN(VVVT d.); in other words, we simply input the dimension to the shared IGN, We have not tested the learning capabilities of this more efficient model in this work, but it could be promising for future work.
19

---

Published as a conference paper at ICLR 2023
B.4 OTHER ARCHITECTURAL NOTES
There are several alternatives available in the design of SignNet and BasisNet that we now discuss. Our approach, as outlined in Figure 2, processes the eigenvectors independently to compute learned positional encodings and then uses these learned positional encodings along with the node features X final base model (say, a GNN) to get a prediction. Another possibility is to process eigenvectors and node features jointly. One way to do this is to add X as input to c, so for instance SignNet would include (bv; X) + Φ 1; X). However, this requires processing X 2k times with Φ which may be inefficient.
Another possibility to parameterize a sign invariant architecture is through taking elementwise abso- lute values of eigenvectors, and then composing with arbitrary functions, e.g. ((I |vx D), where the MLP acts independently on each node. Empirically, this often does not work well (see our results ZINC as well as those of Dwivedi et al. (2020)). Intuitively, these elementwise absolute -
values remove distance information, since for instance nodes and j which 0 =- are typically far in the graph, but they will have the same value in this eigenvector under the absolute value mapping. Nonetheless, the & in SignNet is taken to be an elementwise function, meaning R" + Ruxd satisfies Φ(v); (b(,) for some & applied independently to each node, then SignNet is equivalent in expressiveness to MLP([11]....... [v. where the MLP acts independently on each node.
C MORE ON EIGENVALUE MULTIPLICITIES
In this section, we study the properties of cigenvalues and eigenvectors computed by numerical algorithms on real-world data.
C.1 SIGN AND BASIS AMBIGUITIES IN NUMERICAL EIGENSOLVERS
When processing real-world data, we use eigenvectors that are computed by numerical algorithms. These algorithms return specific eigenvectors for each eigenspace, so there some choice of sign or basis of each eigenspace. The general symmetric matrix eigensolvers numpy .iiallg............. eigh and scipy. linalg.......... eigh both call LAPACK routines. They both proceed as follows: for a symmetric matrix A, they first decompose it as A QTQ T for orthogonal Q and tridiagonal T, then they compute the eigendecomposition of T = W WAWT, so the eigendecomposition of A is A (QW)AAWWT QT). There are multiple ambiguities here: for diagonal sign matrices S = Diag($1.... 8n) and S' = Diag(s *,,,, where 8i, 8 E [-1,1}. we have that A = S)Q is also a valid tridiagonalization, as QS is still orthogonal, SS = I, and STS is still tridiagonal. Also, T (WS') ((S'W) is a valid cigendecomposition of T, W is still orthogonal.
In practice, we find that the general symmetric matrix eigensolvers numpy www.llnnlg.....................l eigh and scipy. lina 1g eigh differ between frameworks but are consistent with the same framework. More specifically, for symmetric matrix A, we find that the eigenvectors computed with the default settings in numpy tend to differ by a choice of sign or basis from those that are computed with the default settings scipy. On the other hand, the called LAPACK routines are deterministic, so the cigenvectors returned by numpy are the same in each call, and the eigenvectors returned by scipy are likewise the same in each call.
Eigensolvers for sparse symmetric matrices like scipy. 1 liialll....... minaagg.eggh... 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.
Bro et al. (2008) develop 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 's entries are in the largest lexicographic order (Tam & Dunson, 2022). This choice of sign may work poorly for learning on graphs, is sensitive to permutations on nodes. For some graph regression experiments in Section 4.1, we try a choice of sign that is permutation invariant, but we find it to work poorly.
20

---

Published as a conference paper at ICLR 2023
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. >
ZINC
12,000
9-37
9
64.1
ZINC-full
249,456
6-38
10
63.8
ogbg-molhiv
41,127
222
42
68.0
IMDB-M
1,500
7-89
37
99.9
COLLAB
5,000
32-492
238
99.1
PROTEINS 1,113
4-620
20
77.3
COIL-DEL 3,900
3-
4
4.00
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
Distinet
# Mult.
Max Mult.
Vees mult.
32 x 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
C.2 HIGHER DIMENSIONAL EIGENSPACES IN REAL GRAPHS
Here, investigate the normalized Laplacian eigenspace statistics real-world graph data. For any graph that has distinct Laplacian eigenvalues, only sign invariance is required in processing eigenvectors. However, we find that graph data tends to have higher multiplicity eigenvalues, so basis invariance would be required for learning rymmetry-respecting functions on eigenvectors.
Indeed, we show statistics for multi-graph datasets in Table and for single-graph datasets with more nodes per graph in Table 6. For multi-graph datasets, we consider:
Molecule graphs: ZINC (Irwin et al., 2012; Dwivedi et al., 2020), ogbg-molhin (Wu et al., 2018; Hu et al., 2020a)
Social networks: IMDB-M, COLLAB (Yanardag & Vishwanathan, 2015; Morris al., 2020a),
Bioinformatics graphs: PROTEINS (Morris et al., 2020a)
Computer vision graphs: COIL-DEL (Riesen & Bunke, 2008; Morris et al., 2020a).
For single-graph datasets, we consider:
The 32 x 32 image grid as in Section J.3
Citation networks: Cora, Citeseer (Sen et al., 2008)
Co-purchasing graphs with Amazon Photo (McAuley et al., 2015; Shchur et al., 2018).
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-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-grahh datasets have large proportion of their cigenvectors belonging to higher dimensional eigenspaces. Thus, basis invariance may play large role in processing spectral information from these graph datasets.
21

---

Published as a conference paper at ICLR 2023
C.3 RELATIONSHIP TO GRAPH AUTOMORPHISMS
Higher multiplicity eigenspaces are related to automorphism symmetries in graphs. For an adjacency matrix A, the permutation matrix P is an automorphism of the graph associated to A if PAP A.
P is an automorphism, then for any eigenvector v of A with eigenvalue X, we have
AP = PAP Pv PAv Pλ = APv.
(18)
so Po is an eigenvector of A with the same eigenvalue X. If Py and v are linearly independent, then has higher dimensional eigenspace. Thus, under certain additional conditions, automorphism symmetries of graphs lead to repeated cigenvalues (Sachs & Stiebitz, 1983; Teranishi, 2009).
C.4 MULTIPLICITIES IN RANDOM GRAPHS
is known that almost all random graphs under the Erdös-Renyi model have no repeated cigenvalues in the infinite number of nodes limit (Tao & Vu, 2017). Likewise, almost all random graphs under the Erdōs-Renyi model are asymmetric the sense having no nontrivial automorphism symme- tries (Erdos & 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 data have been found to possess nontrivial automorphism symmetries (Ball & Geyer-Schulz, 2018). This demonstrates potential downside of using random graph models to study real-world data: the eigenspace dimensions and automorphism symmetries of random graphs may not agree with those of real-world data.
22

---

Published as a conference paper at ICLR 2023
D VISUALIZATION OF SIGNNET OUTPUT
D.I CAT MODEL VISUALIZATION
Eigenvector
6(0)) - ((-11)
Eigenvector 9
6(vb) - o
Figenvector 11
Φ(v1) ol (--v1)
Figenvector
((V1s) - 6(-v14)
Bigenvector 1023
((Vuu2)) - øl (1-21)
Figure 6: (Left) Cotangent Laplacian eigenvectors of the cat model. (Right) First principal component of (vv) + ((-r) from our trained SignNet.
In Figure 6, we plot the eigenvectors of the cotangent Laplacian on a cat model, as well as the first principal component of the corresponding learned σ0v) + o(-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 is useful for the texture reconstruction task, the texture regression target has bilateral symmetry.
23

---

Published as a conference paper at ICLR 2023
Figure 7: First three principal components of the full SignNet output on the cat model.
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 to be close to the texture that is the task involving eigenvectors of multiple
regression target. If instead we trained the network models, then we may expect the SignNet to learn more structurally interpretable mappings (as the case of the molecule tasks).
D.2 MOLECULE VISUALIZATION
To better understand SignNet, in Figure we visualize the learned positional encodings of SignNet with 6 GIN, p MLP (with summation handle variable eigenvector numbers) trained ZINC as in Section 1. SignNet learns interesting structural information such as cut nodes (PC 3) and appendage atoms (PC 2) that qualitatively differ from any single eigenvector of the graph.
For this visualization we use SignNet trained with GatedGCN base model on ZINC, as in Section 4.1. This SignNet uses GIN and p MLP (with sum before handle variable numbers of eigenvectors), and takes in all eigenvectors of each graph. See Figure 8 for all of the eigenvectors of fluorescein.
E MORE RELATED WORK
E. GRAPH POSITIONAL ENCODINGS
Various graph positional encodings have been proposed, which have been motivated for increasing ex- pressive power or 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 & Leskovec, 2016), which have been recently integrated into GNNs that respect their invariances by Wang et al. (2022). Further, Li al. (2020) studies the theoretical and practical benefits of incorporating distance features into graph neural networks. Dwivedi et al. (2022) proposes a method to inject learnable positional encodings into each layer of graph neural network, and uses simple random walk based node positional encoding. You et al. (2021) proposes a node positional encoding diag(A*). (A*), which captures the number of closed walks from node to itself. Dwivedi al. (2020) propose use Laplacian eigenvectors as positional encodings in graph neural networks, with sign ambiguities alleviated by sign flipping data augmentation. Srinivasan & Ribeiro (2019) theoretically analyze node positional embeddings and structural representations in graphs, and show that most-expressive structural representations contain the information of any node positional embedding.
While positional encodings in 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 & 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 cigenvalues et al. (2021) uses spectral kernels such as the diffusion kernel to define relative positional encodings that modulate the attention matrix. Ying et al. (2021) achieve ofte-oo-the-ar empirical performance
learn node or edge positional encodings. Mialon
24

---

Published as a conference paper at ICLR 2023
Eigenvector
Eigenvector
Eigenvector 3
Figenvector
-43
Eigenvector
Eigenvector
Eigenverter 7
Eigenvector
es
es
Figenvector
Eigenvector 10
Eigenvector 11
Elgenvector 12
geneeector
Eigenvector
Eigenvector 15
Elgenvector
Aa
Figenvector
Eigenvector
Figenvector 19
Eigenvector 20
Eigenvector 21
Eigenvector 22
Eigenvector 23
Eigenvector
Figure All normalized Laplacian eigenvectors of the fluorescein graph. The first principal components of SignNet's learned positional encodings do exactly match any eigenvectors.
with simple Transformers that incorporate shortest-path based relative positional encodings. Zhang et al. (2020) also utilize shortest-path distances for positional encodings in their graph Transformer. Kim al. (2021) develop higher-order transformers (that generalize invariant graph networks), which interestingly perform well on graph regression using sparse higher-order transformers without positional encodings.
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 & 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-body problems). However, discrete graph Laplacians are known and in Appendix C.2 we find this to be true in
to have higher multiplicity eigenvalues in many various types of real-world graph data. Graphs without higher multiplicity eigenspaces are easier to deal with; in fact, graph isomorphism can be tested in polynomial time graphs of bounded
25

---

Published as a conference paper at ICLR 2023
Eigenvector
Eigenvector 2
Eigenvector
Elgenvector 24
-13
SignNet PC 1
SignNet PC
SignNet PC 3
SignNet PC
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((((u) v.) + ((-u:))==.....))) of SignNet.
multiplicity for adjacency matrix eigenvalues (Babai al., 1982; Leighton & I. Miller, 1979), with time complexity that is lower for graphs with lower maximum multiplicities.
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=* they parameterize functions f(Z) such that f(Z) = f(ZQ) for all E Ok)). This indeed makes sense for network embeddings like node2vec (Grover & Leskovec, 2016), as their objective functions are based on inner products and are thus orthogonally invariant. While they prove stability results when enforeing full orthogonal invariance for eigenvectors, this is a very strict constraint compared to our basis invariance, For instance, when = n and all eigenvectors are used in V, the condition f(V) f(VQ) implies that f is constant function orthogonal matrices, since any orthogonal matrix W can be obtained as W VQ for Q VTW E (n)). In other words, Vi...., Vi and V [V] ... Vi], Wang et al. (2022) enforces VQ = V. while enforce VDiag(Q1 ..... Qi) V. While the columns of VDiag(Q1..... Qi) are still eigenvectors, the columns of VQ generally
bases of eigenspaces
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 on graph spectra, which use robust and discriminative notions of generalized spectral distance (Verma & Zhang, 2017), the spectral density states (Huang et al., 2021), random walk return probabilities (Zhang et al., 201 8b), or the trace of the heat kerne (Tsitsulli et al., 201 8). Graph signal processing relics on spectral operations to define Fourier transforms, frequencies, convolutions, and other usefuu 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.
F DEFINITIONS, NOTATION, AND BACKGROUND
F.1 BASIC TOPOLOGY AND ALGEBRA DEFINITIONS
We will use some basic topology and algebra for our theoretical results. A topological space (X, 7) is set X' along with family of subsets 2 satisfying certain properties, which gives useful notions like continuity and compactness. From now on, we will omit mention of т, and refer to topological space as the set A' itself. For topological spaces X' and y, write X' e y and say that
26

---

Published as a conference paper at ICLR 2023
X' is homeomorphic to }/ if there exists continuous bijection with continuous inverse from X' to V. 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 it can generally be substituted with homeomorphism), For function f : -> y between topological spaces X' and y the image imf is the set of values that f takes, imf {f(x)=
X) This is also denoted f (2)). A function f X y is called topological embedding if it is a homeomorphism from X' to its image.
group G is set along with a multiplication operation G x G ++ G. such that multiplication is associative, there is a multiplicative identity e E G, and each E G has a multiplicative inverse g y² topological group a group that is also a topological space such that the multiplication and inverse operations are continuous.
group G may act on a X by a function : G + X. We usually denote g x as gz. A a topological space X' if is continuous. For any
topological group is said to act continuously group G and topological space X, we define the coset Gr = {gr 9 E 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/G (G=: x E } is the set all such equivalence classes, with a topology induced by that of X. The quotient map π X + X/G is surjective continuous map that sends to its coset, π (zx) = Ga.
For Rdd |>l|| denotes the standard Euclidean norm, By the norm of functions f: Z - Rd from a compact Z to a Euclidean space IR,, we mean |o = supsez (=)]le.
F.2 BACKGROUND ON EIGENSPACE INVARIANCES
Let V [01 ... ea] and W = [wi ... wa] E Ruxd be two orthonormal bases for the same dimensional subspace of R Since V and W span the same space, their orthogonal projectors
the same, so VVT WWT. Also, since V and W have orthonormal columns, we have VTV= = E gdxd Define Q = V W. Then Q is orthogonal because
Q WQ= Tw W WW WWTW=1 W
(19)
Moreover, have that
= VQ = VV = WWWW> W= W
(20)
Thus, for any orthonormal bases V and W of the same subspace, there exists orthogonal Q E (dd) such that VQ = W.
For another perspective this, define the Grassmannian Gr(d, n) the smooth manifold consisting of all d dimensional subspaces of R" Further define the Stiefel manifold St n) as the set of all orthonormal tuples [01 ... val Raxdd of vectors in T Letting ((d) act by right multiplication, holds that (t.d, on (d, n) can be viewed as a function on subspaces. See e.g. Gallier & Quaintance (2020) Chapter 5 for more information on this. We will use this relationship in our proofs of universal representation.
= Gr(d, n). This implies that any (d) invariant function
When consider permutation invariance or equivariance, the permutation acts on dimensions of size n. Then a tensor X I2* is called an order i tensor with respect to this permutation symmetry, where order 0 are called scalars, order tensors matrices. Note that this does not depend on d; in this work, we only ever consider vectors and scalars with respect to the (d) action.
called vectors, and order 2 tensors are called
G PROOFS OF UNIVERSALITY
We begin by proving the two propositions for the single subspace case from Section 2. Proposition A continuous function h R - dous is sign invariant if and only if
h(w)) = ((v) + d(-v)
for some continuous Φ- 1 - TR continuous T - R. is sign invariant and permutation equivariant if and only if (3) holds for continuous permutation equivariant 6 _ 1
Proof. If ((()) = σ(v) + 6(-)), then h is obviously sign invariant. On the other hand, h is sign invariant, then letting ((v) = h(w)/2 gives that h(v)) ((v) vi(-r), and is of course continuous.
27

---

Published as a conference paper at ICLR 2023
If h(2) o(t) + ((-o) for a permutation equivariant é, then h(-Pu) ((-Po) + o(Pe) = Po(-o)+ = P + = Ph(v), so is permutation equivariant and sign invariant. If h is permutation equivariant and sign invariant, then define @(v) h(t)/2 again; it is clear that is continuous and permutation equivariant.
Proposition 2. Any continuous, O(d) invariant h : Raxdd + Redo is of the form h(V) = 6(VVT)
for continuous Φ. For compact domain 2 Raxd maps of the form V IGN(VVT)
universally approximate continuous functions h : Z C RRaxd - IR" that are O(d) invariant and permutation equivariant.
Proof. The case without permutation equivariance holds by the First Fundamental Theorem of (d) (Lemma 2).
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 compact set. Since h is ((d) invariant, the first fundamental theorem of (d) shows that there exists a continuous function ø 2' R=** - R such that h(V) = <(VVT) Since h is permutation equivariant, for any permutation matrix P we have that
h(PV)= P- 6(PVV = PP
(21)
(22)
so &i a continuous permutation equivariant function from matrices to vectors. Then note that Keriven & 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 compact sets of matrices. Thus, an IGN can e-approximate o, and hence V + IGN(VVV) c-approximate h.
can
G.1 PROOF OF DECOMPOSITION THEOREM
X1 x... Xx
f = for
② = O
Ti X ... TT
(Xi/Gi) x... x Gxz/Ga)
I dout
2 (m) C R K
1 1 ... x 1/k
p
1
Figure 10: Commutative diagram for our proof of Theorem 4. Black arrows denote functions from topological constructions, and red dashed lines denote functions that we parameterize by neural networks (Ø = Φ1 .... x ox and p).
Here, we give the formal statement of Theorem 4, 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 topological embedding of each quotient space into some Euclidean space. That the group action is continuous is a very mild assumption, and it holds for any finite or compact matrix group, which all of the invariances we consider in this paper can be represented as.
topological embedding of the quotient space into a Euclidean space is desired, as we know how to parameterize neural networks with Euclidean outputs and inputs, whereas dealing with a quotient space is generally difficult. Many different conditions can guarantee existence such an embedding. For instance, if the quotient space is smooth manifold, then the Whitney Embedding Theorem
28

---

Published as a conference paper at ICLR 2023
(Lemma 5) guarantees such an embedding. Also, if the base space X; is Euclidean space and G; is a finite or compact matrix Lie group, then a map built from G-invariant polynomials gives such an embedding (González & de Salas (2003) Lemma 11.13).
Figure provides a commutative diagram representing the constructions in our proof.
Theorem 4 (Decomposition Theorem). Let , be topological spaces, and let G3 be topological group acting continuously on X, for each i. Assume that there a topological embedding v; : X, + R of each quotient space into a Euclidean space R for some dimension o,, Then, for any continuous function
X = Xi x .... X₂ + Rddo that is invariant to the action of G G1 x Gh. there exists continuous functions di Xr Raa and continuous function p: R - RR dous, where a = Ei ag such that
[(v1,.... vk) (v1) (vx)))
(23)
Furthermore: (1) each oe can be taken to be invariant to G5. (2) the domain Z is compact if each X, compact, (3) if X₂ X2 and G, G then di can be taken be equal to dj.
Proof. Let q. : X; - X//G, denote the quotient map for X; X//;; Since each G; acts continuously, Lemma 3 gives that the quotient of the product space the product of the quotient spaces, i.c. that
(R .... x ( ....Gr... .....) = (Rg/ x x (&e/Ga),
(24)
and the corresponding quotient map X/ P/G is given by
ı7 X The
n (z mR) (TI(II), ..... (xx)))
(25)
By passing to the quotient (Lemma 1), there exists continuous f X//G Rd the quotient space such that f a æ. By Lemma 4, each X, \/G; is compact X; compact. Defining the image 2, = vh (2/ G.) C RR: we thus know that 2, is compact if X; is compact.
Moreover, as vi is a topological embedding, it has continuous inverse w, on its image 2,. Further, we have a topological embedding X/G > Z Z1 ... 2% given by & 4/2 ... thk with continuous inverse wー 0. ... x 2/2
Note that
f= f=fo== v (boT).
(26)
So we define
i /
2: + Bdat
(27)
6. vi o
Φ: : X + Zi
(28)
10 o = Φ1 ... x dn
X 2
(29)
Thus,
.... x dx), so equation (9) holds. Moreover, the p and dy are continuous, as they are compositions of continuous functions. Furthermore, (1) holds as each di is invariant to G; because each म; is invariant to G, Since each E, is compact if X, is compact, the product 2 2 X ... x Zμ is compact if each X; is compact, thus proving (2).
To show the last statement (3), note simply that if X; X; and G; Gj. then the quotient maps equal, i.e. π. J.. Moreover, we can choose the embeddings to be equal, so say th: = 1/3. Then, 6 3/ bh rTy Φj are done.
G.2 UNIVERSALITY OF SIGNNET AND BASISNET
Here, prove Corollary 1 on the universal representation and approximation capabilities of our Unconstrained-Sigee -iggneess, Unconstrained Baaanstrained-Bassseetttt and Expressive- Expressive-BasisNets. We proceed sev- eral steps, first proving universal representation of continuous functions when do not require permutation equivariance, then proving universal approximation when we do require permutation equivariance.
29

---

Published as a conference paper at ICLR 2023
G.2.1 SIGN INVARIANT UNIVERSAL REPRESENTATION
Recall that gn-1 denotes the unit sphere in R As we normalize eigenvectors to unit norm, the domain of our functions on k eigenvectors are on the compact space (S"-1)².
Corollary 2 (Universal Representation for SignNet). A continuous function f (8"-1)k - Roout sign invariant, i.e. (..1,,,..., ,g.Uk) = f(V,,..., Un. for any 8; E [-1,1}, if and only if there exists a continuous Φ TR - 222n-2 and a continuous p (2(22 _> dous such that
fem..... Uk) - ((o(v)) ol (-v)))
(30)
Proof. It can be directly that any f of the above form is sign invariant.
Thus, we show that any sign invariant f can be expressed in the above form. First, we show that can apply the general Theorem 4. The group G; = -1) acts continuously and satisfies that 8n-1/(1, [[] = IRP~11 where RP is the real projective space dimension n - 1. Since IRP--1is is smooth manifold of dimension n Whitney's embedding theorem states that there exists a (smooth) topological embedding 1/v RPP-1 + IR 2n (Lemma 5).
Thus, we can apply the general theorem to see that f = a 3² for some continuous and S Note that each di = Φ is the same, as each X; S and G; {1, -1} is the same. Also, Theorem says that we may assume that á is sign invariant, so Φ(x) = o( (-z)). Letting <(x) = / we are done with the proof.
G.2.2 SIGN INVARIANT UNIVERSAL REPRESENTATION WITH EXTRA FEATURES
Recall that we may want our sign invariant functions to process other data besides cigenvectors. such as eigenvalues 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 a simple extension of Corollary 2, but provide the technical details for completeness.
Corollary 3 (Universal Representation for SignNet with features). For compact space of features Ω C Rd, let f( Uk, ..... zx) be a continuous function f (Sa-1 Ω7* + Rdow.
Then is sign invariant for the inputs the sphere, i.e.
f(siv).... S5U2, ;I,..., f(V1..... Uks T1...., xK)
9; (1, -1},
(31)
if and only if there exists a continuous vb gu+ + 2n 22d Rdwn such that
2td and a continuous p: (2n -+))k
f(r vn) = (6((1, o(-v1, v1, ... ((U,, #k) Φ6 (0--kk, vx))
(32)
Proof. Once again, the sign invariance of any f in the above form is clear.
We follow very similar steps to the proof of Corollary to show that we may apply Theorem 4. We
can view Ω as a quotient space, after quotienting by the trivial group that does nothing, Ω > [1]. The corresponding quotient map idg, the identity map. Also, Q trivially topologically embeds in dd by the inclusion map.
As G. [-1,1} x (1) acts continuously, by Lemma 3 we have that
SS x (0)((1,-1)) x (1)) = (s"-1 /11, -1)) x (2/(1)) = RF"-1 x Ω
(33)
with corresponding quotient map x idg, where is the quotient map to RP--1
Letting e be the embedding of P + 2=22 guaranteed by Whitney's embedding theorem (Lemma 5), we have that vp = & x idg is an embedding of RFa-1 x Ω - 222=-2+ Thus, we can apply Theorem 4 to write f = p 3 for o = (0 idg) o (N idg), so
,(v,, = (z((0) x;))), x;):
(34)
where 2(1,, = H(-vi, R.I). Letting ((v;, H(vi, .r:) /2, are done.
30

---

Published as a conference paper at ICLR 2023
G.2.3 BASIS INVARIANT UNIVERSAL REPRESENTATION
Recall that St(d,n) n) is the Stiefel manifold of d-tuples of vectors (U1y..., va) where v, R" and P1..... are orthonormal. This is where our inputs lie, as our eigenvectors are unit norm and orthogonal. We will also make use of the Grassmannian (rdd, n). which consists of all d-dimensional subspaces in R This is because the Grassmannian is the quotient space for the group action we want, Gr(d, n) St(d, mi/ (d)), where Q E O(d) acts on V St(d n) C Raxd by mapping V to VQ (Gallier & Quaintance, 2020).
Corollary 4 (Universal Representation for BasisNet). For dimensions di....,dh S. n. let I be continuous function on St,d1,, n) x ... x St(di; n). Further assume that I is invariant to O(d,) x x (d)),, where ((d)) acts St(d,, r2) by multiplication the right.
Then there exist continuous p. ER (d:(n-d))) (n-d(n-dd) such that
+ Idon and continuous o, St(d,, n) +
f(V,...., Vi) = p (V1), (v())) where the di are (dd)) invariant fiantiins, and can take 6; = Øj if dj.
(35)
Proof. Letting X; (t,,, nt) and G; = Odd)) can be seen that G. acts continuously on X. Also, we have that the quotient space Stdd, (d:) = Gr(d, n) is the Grassmannian of de dimensional subspaces in RR,, which is a smooth manifold dimension dı(n - d.). Thus, the Whitney embedding theorem (Lemma 5) gives a topological embedding dyy Gr(d,, n) + (nd()_-d))
Hence, we may apply Theorem to obtain continuous ((4) invariant di St(d; n) + RR2d. (n- and continuous p IR Eis (d((n-d:) + Rdoo,, such that f = p o (01 x... x Φ1). Also, if d; dj- then X₁ X3 and G, Gj. so we can take Φ; Φj.
G.2.4 BASIS INVARIANT AND PERMUTATION EQUIVARIANT UNIVERSAL APPROXIMATION
With the restriction that f( Vi): RRR R be permutation equivariant and basis invari- ant, we need to use the impractically expensive Bassessive-BasisNet to approximate f. Universality of permutation invariant or equivariant functions from matrices to scalars or matrices to vectors is difficult to achieve in computationally tractable manner (Maron et al., 2019; Keriven & Peyré, 2019; Machara & NT. 2019). One intuitive reason to expect this is that universally approximating such functions allows solution of the graph isomorphism problem (Chen et al., 2019b). which is computationally difficult problem. While we have exact representation of basis invariant functions by continuous and o; when there is permutation equivariance constraint, we can only achieve approximation up to an arbitrary e > O when we require permutation equivariance.
Let f(V,...., Vi) St(d1, n) x x St(d,, n) - R be continuous, ((di) x... x (dd)) invariant, and permutation equivariant. Then J can be e-approximated by an SepressivveBasishie
Corollary (Universal Approximation for Expressive-BasisNers BasisNets).
Proof. By invariance, Corollary 4 of the decomposition theorem shows that f can be written as
S(V..... Vi) = p (Pe,, (Vi),... -Pd (V))
(36)
for some continuous (dd) invariant Sa, and continuous p. By the first fundamental theorem of (d) (Lemma 2), each ya, can be written as Pa, (V,) = Φa, (V.V.)) for some continuous Φd,- Let
z [ViVV ..... ,VvTT) V, E St(d,, m)) C R
(37)
which is compact as it is the image of the compact space St(d1, n) x... St((d, n) under a continuous
function. Define 2 C TR xl - Rn by
WVVVV .... vVTT) (0a, (VIVT)...., (VVTT))
(38)
Then note that h is continuous and permutation equivariant from matrices to vectors, so it can be e-approximated by invariant graph network (Keriven & Peyré, 2019), call it IGN. If we define
31

---

Published as a conference paper at ICLR 2023
IGN and a (VVV") V.V." (this identity operation is linear and permutation equivariant, so it can exactly expressed by an IGN), then we have e-approximation f by
(39)
L
G.3 PROOF OF UNIVERSAL APPROXIMATION FOR GENERAL DECOMPOSITIONS
Theorem 5. Consider the same setup as Theorem 4, where X₂ are also compact. Let D; be family of Gæ-invariant functions that universally approximate G;-invariant continuous functions X; - RR: and let RR be set of continuous function that universally upproximate continuous functions C IR_e + Rdow for every compact Z, where a = E; a, Then for any s > 0 and any G-invariant continuous function f : X1 x ... x Xx - Rddwu there exists @ E and p E R such that |lf
0k)]l E.
Proof. Consider a particular G-invariant continuous function f X1 x... X 24. Rd By Theorem there exists G--invariant continuous functions of _ and continuous function Rdout (where a = >; E(a,) 0.) such that
Z Ra
[(1 vk) (v1 (. (vx)).
Now fix an & > O. For any p E R and any di E 4 (i - 1,... k)) we may bound the difference from as follows (suppressing the v for brevity),
f p ............ Φx))l
1| (''('
0%) p( ... 2x)
1l 1p'(di
06) p( ..... 0%) p(o 8%) p(o1..... p())....,,))ll.
S 1l
16) p(o),...,))lll. + |l((d)...... p(oi..... 22)
I++1 II
Now let K" = =I= im Since each di is continuous and defined compact set X, know that im is compact, and so the product K is also compact. Since K' is compact, it is contained in closed ball (r) of radius r + centered at the origin, so K contains K' and a ball of radius 1 around each point of K'. We may extend p' continuously to as needed, so assume p' K R.bat By universality of may pick particular p: K + R Rout,
centered at the origin. Let be the closed ball Brr + of radius
R such that
I= sup (u
1''' oe) - p( Bi)l. S sup (Ip(()) p(2)]1 < 5/2 =ek
Keeping this choice of p. it remains only to bound II. As p continuous on compact domain, is in fact uniformly continuous. Thus, we can choose 8' > 0 such that if ||ı 2||2 S 8', then (((()) p(=)]l < e/2, and then we define = min(8', 8 1).
Since 4 universally approximates of we may pick Φ; E ④, such that ||o: - &illoo < 6/ and thus || ( ②k) (#f....oh K+ I &. With this choice of di we know that I im C K
(x(x))) (because each oi (ax) is within distance of (x:)). Thus, p( (.))........
well-defined,
and we have
I1 |le(ő),.....
.,) -x)le
sup (n).( - p(d1(x))...... (x)))))
(MEX))
<e/²
due to choice of 6, which completes the proof.
32

---

Published as a conference paper at ICLR 2023
H BASIS INVARIANCE FOR GRAPH REPRESENTATION LEARNING
H.1 SPECTRAL GRAPH CONVOLUTION
In this section, we consider spectral graph convolutions, which for node features E _ take the form J(V, A, X) = =E=1 0, X for some parameters 0g. We can optionally take 8; ((a,) for some continuous function h + of the 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 be some analytic function such as a simple affine function (Kipf & Welling. 2017), linear combination in polynomial basis (Defferrard et al., 2016; Chien et al., 2021), or a parameterization of rational functions (Levie et al., 2018; Bianchi et al., 2021).
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) = Eo.Po.T PX- = C.PPo: x P
(40)
Also, it is easy to that they sign invariant, (-o:)--;;) = However, if the 0g do depend on the cigenvalues, then the spectral graph convolution is not necessarily basis invariant. For instance, if U1 and U2 are in the same eigenspace, and change basis by permuting v U2 and 2/2 then if 0 * 0₂ the spectral graph convolution will generally change as well.
On the other hand, 0, = h(2a)) for some function h R R, then the spectral graph convolution is basis invariant. This is because if Us and l/ belong to the same eigenspace, then X; Xy so I(A.) h(2)). Thus, if Us,..... Us are eigenvectors of the same eigenspace with eigenvalue X, we have that Σi= ((Aa)),, v. = h(A) Σ U2 U Now, note that Σi Ui v. is the orthogonal projector onto the eigenspace (Trefethen Bau III. 1997). A change of basis does not change this orthogonal projector, so such spectral graph convolutions are basis invariant.
Another way to see this basis invariance is with a simple computation. Let Vi,..., Vi the eigenspaces of dimension di...., di, where V; E [gaxd Let the corresponding eigenvalues be M... Then for any orthogonal matrices Q2 E (d,), we have
Σ h(N)ooy
Va,
(41)
Σ VMM,)),,,003V
(42)
Σ (VOMMM
(43)
so the spectral graph convolution is invariant to substituting V,Q, for Vy.
Now, give the proof that shows SignNet and BasisNet can universally approximate spectral graph convolutions.
Theorem (Learning Spectral Graph Convolutions). Suppose the node features E Rexx take values in compact sets. Then SignNet can universally approximate any spectral graph convolution, and both BasisNet and Expressive-Batt BaaiiNeet can universally approximate any parametric spectral graph convolution.
Proof. Note that eigenvectors and cigenvalues of normalized Laplacian matrices take values in compact sets, since the eigenvalues are in [0, and we take eigenvectors have unit-norm. Thus, the whole domain of the spectral graph convolution is compact.
Let E > First, consider a spectral graph convolution f(V, X) Σt A,,00 X. For SignNet, let o(v; As. approximate the function Φ(v, A, X) = 0,u0o X within s/n error, which DeepSets can do since this is continuous permutation equivariant function from vectors vectors
33

---

Published as a conference paper at ICLR 2023
(Segol & Lipman, 2019) (note that we can pass A as vector in R" by instead passing A,1, where 1 is the all ones vector). Then p = >x= is a linear permutation equivariant operation that can be exactly expressed by DeepSets, so the total error is within E. The same argument applies when 0. = h(xa) for some continuous function h.
For the basis invariant case, consider a parametric spectral graph convolution f(V, A, X) (,m,((A) X. Note that if the eigenspace bases are Vi,..., V/2 with eigenvalues (i,..., M4, we (5=n(( X. Again, will let p = Ei=1 be sum function, which can expressed exactly by DeepSets. Thus, it suffices to show that V3V X can be e/n approximated by 2-IGN (i.e. an IGN that only uses vectors and matrices).
can write the J(V,A,X)
Note that since h is continuous, we can use an elementwise MLP (which IGNs can Iearn) to approximate (xl11 VVV
(h(p)111, T, VVT xX) to arbitrary precision (note that we rep- resent the eigenvalue μ constant matrix pll1) Also, since 2-IGN can learn matrix vector multiplication (Cai & Wang (2022) Lemma 10), we can approximate fz(h(p)11 .VVT, ,X) = (h(p)11T, , VVT x). as V.V;T E I is matrix and X E Ruxddow is vector with respect to permu- tation symmetries. Finally, we use an elementwise MLP to approximate the scalar-vector multiplica- tion fa (h((4) VVT .X) h(2)VVT X. Since fa o f2 o fi f((111 .VV X) = Vu) X, and since 2-IGNs universally approximate each fi, applying Lemma shows that a 2-IGN can approximate h(u)) VVTX X to e/n accuracy, we are done. Since Expressive-Basiska is stronger than BasisNet, it can also universally approximate these functions.
From the proof, we can see that SignNet and BasisNet need only learn simple functions for the p and é when h is simple, or when the filter is non-parametric and we need only learn 0;. 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 vell-approximated 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 a simple linear function with coefficients 1, and X, X) h(A)VV X is quadratic in V and linear in X, so it is simple if h is simple.
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.
Proof. The idea is as follows: we will take graphs G and give them the node feature matrix XG D1/21, i.e. each node has as feature the square root of its degree. Then any spectral graph convolution (or, the first layer of any spectral GNN) will map V Diag(O)VV XX to something that only depends on the degree sequence and number of nodes. Thus, any spectral graph convolution or spectral GNN will have the same output (up to permutation) for any such graphs G with node features XG and the 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 (X Gau ( ) and the same number of nodes and degree sequence; this is because SignNet and BasisNet can tell when a graph bipartite.
For each 5, we will define (()) and (22) connected graphs with nodes, with the same degree sequence. Also, we define G()) to have node features x( = ( where d()) is the degree of node i in G()), and similarly 2 has node features x(!) / dd Now, note that (2) is an cigenvector of the normalized Laplacian of G and it has eigenvalue 0. As we take the eigenvectors to be orthonormal (since the normalized Laplacian is symmetric), for any spectral graph convolution we have that
Σ 0,,,, (() = A =0,000,,,00000000000 -,D/311///1)///// = 0, Da
(44)
Where Dj is the diagonal degree matrix of G(L), Likewise, any spectral graph convolution outputs 0, (d for ((2), Since D, and D2 are the same up to a permutation, we have that any spectral graph convolution has the same output for (()) and ((2) up to a permutation. In fact, this
34

---

Published as a conference paper at ICLR 2023
W1
1/5
W2
W3
1/
GOI
G(
Figure 11: Illustration of our constructed GO) and G(2) for n 5, as used in the proof of Proposi- tion
W44
WG
W6
U3
W2
W3
D2
U4
T6
U5
GO)
((
Figure 12: Illustration of our constructed G()) and G22) for n = 6, as used the proof of Proposi- tion 3.
also holds for spectral GNNs, as the first layer will always have the same output (up to a permutation) on G and G(2), so the latter layers will also have the same output up permutation.
Now, we concretely define G()) and ((2) This is illustrated in Figure 11 and Figure 12. For let ((1) contain triangle with nodes wi, W2, W3, and have path of length coming out of one of the nodes the triangle, say wi connects to Wis and wy connects to Wy. This is not bipartite, as there triangle. Let ((2) be bipartite graph that has nodes on the left (v1, 12) and 3 nodes on the right (V3, U4, Us). Connect with all nodes on the right, and connect dg with Uy and 24.
Note that both G()) and (( have the same number of nodes and the same degree sequence (3. 2, 2, 2, 1). Thus, spectral graph convolutions or spectral GNNs cannot distinguish them. How- ever, SignNet and BasisNet can distinguish them, as they can tell whether graph is bipartite by checking the highest eigenvalue of the normalized Laplacian. This is because the multiplicity of the eigenvalue 2 is the number of bipartite components. In particular, SignNet approximate the function Φ(v,, de X) = X; and p R max Likewise, BasisNet can approximate the function da, (VVTT, Ar) = X; and p 2 max
This in fact gives an infinite family of graphs that SignNet / BasisNet can distinguish, but spectral graph convolutions or spectral graph GNNs cannot. To see why, suppose we have G11) and G(2) for some n 2 Then we construct a pair of graphs on n + nodes with the same degree sequence. To do this, add another node the path of ((1), thus giving it degree sequence {3, 2, ... 2, 1}. For ((2), we add node 0,+1 the side that 2, is not contained on (e.g. for 5, add 4/ the left side, as is was on the right), then connect e, to Up-1 to also give degree sequence {3, .,,.. 2, 1}.
Note that the non-bipartiteness of (1) and bipartiteness of (2) are preserved.
35

---

Published as a conference paper at ICLR 2023
H.2 EXISTING POSITIONAL ENCODINGS
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.
Proposition 5. If the eigenvalues take values in a compact set, SignNets and BasisNets universally ap- proximate the diagonal of any spectral graph convolution matrix J(V, diag (Ei=) M(x.)u, BasisNets can additionally universally approximate any spectral graph convolution matrix f(V, EL=1 h(A.)u,..
Proof. Note that the come from compact they of unit norm. The X, are from compact set by assumption; this assumption holds for the normalized I Laplacian, as X E [0, 2]. Also, as diag is linear, the spectral graph convolution diagonal can be written E ((,,) ((2)))iaa((;)))
Let > 0. For SignNet, let p Σ which can be exactly expressed as it is permutation equivariant linear operation from vectors to vectors. Then o(v;, A,) can approximate the function (1, to arbitrary precision, it is permutation equivariant function from vectors to vectors (Segol & Lipman, 2019). Thus, letting & approximate the function to e/n accuracy, SignNet accuracy.
approximate
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 dd,, since it a linear permutation equivariant function from matrices to vectors. A 2-IGN can universally approximate the function [1 V.V.T) (h(ps), VVV,T), ), as it can express any elementwise MLP. Also, a 2-IGN can universally approximate the scalar-matri multiplication f2(h(p;), V.V.T) = h(p,) V.VT by another elementwise MLP. Since b(,,))VV = f2 fi (ms, V.V,T), Lemma 6 shows that a single 2-IGN can approximate this composition c/l accuracy,
Let / be the number of eigenspaces Vi...., Vi, so f(VA)) = E
are done.
Proposition 4. SignNet and BasisNet can approximate node positional encodings based on heat kernels (Feldman et al., 2022) and random walks (Dwivedi et al., 2022). BasisNet can approximate diffusion and p-step random walk relative positional encodings (Mialon et al., 2021) 1), and generalized PageRank and landing probability distance encodings (Li al., 2020).
Proof. 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 diag (Σ 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) just the matrix of this heat kernel, and the p-step random walk kernel is > (1 7A. Pe.u for some parameter y, so BasisNets can universally approximate both of these.
For the other positional encodings, we let vy be the eigenvectors of the random walk Laplacian I D-D A instead of the normalized Laplacian / - D- 1-1122AD-1 The eigenvalues of these two Laplacians are the same, and if ū; is an eigenvector of the normalized Laplacian then D-1/2 is an eigenvector of the random walk Laplacian with the same eigenvalue (Von Luxburg, 2007).
Then with v; as the eigenvectors of the random walk Laplacian, the random walk positional encodings (RWPE) in Dwivedi al. (2022) take the form
n
diag ((D-A))*) diag
Ia (11-))) u)0
(45)
for any choices of integer k.
The distance encodings proposed in Li et al. (2020) take the form
/ADD-1 (AD (AD
(46)
36

---

Published as a conference paper at ICLR 2023
for some function fs. We restrict to continuous fs here; shortest path distances can be obtained by discontinuous fa that we discuss below. Their generalized PageRank based distance encodings can be obtained by
Σ
na - 21)*
(47)
for some Y/A E I,, so this is a spectral graph convolution. They also define so-called landing probability based positional encodings, which take the form
Ea-M) A.
(48)
for some choices of integer k. Thus, BasisNets approximate these distance encoding matrices.
Another powerful class of positional encodings is based on shortest path distances between nodes in the graph (Ying et al., 2021; Li et al., 2020). Shortest path distances can expressed a form similar to the spectral graph convolution, but require highly discontinuous function. If we millii,,00 i to be the lowest index such that 2; is nonzero, then we can write the shortest path distance matrix as fa(D AA, matrix. As - (D-IA)"), where fa is applied A eeu, BasisNets can learn the inside arguments, but cannot learn the discontinuous function f3-
define fa(
elementwise to return
H.3 SPECTRAL INVARIANTS
where Here, we consider the graph angles auj = IVVV e,ll2. for I,...,, where is the number of eigenspaces, and j 1, ...... 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 graph, and the number of length ic closed walks is all shown in Chapter 4 of Cvetković al. (1997). Other properties may be of for graph representation learning as well. For instance, the eigenvalues of node-deleted subgraphs of a graph G are determined by the eigenvalues 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., 2021; Tahmasebi al., 2020).
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 graph an integer). Thus, any two graphs that differ in these properties will differ by at least 1, so as long as we have approximation to e < 1/2, we can distinguish any two graphs that differ in these properties. Recall the statement of Theorem 3.
Theorem 3. BasisNet can universally approximate the graph angles aij. The eigervalues and graph angles (and thus BasisNets) can determine the number of length 4, and cycles, whether a graph is connected, and the number of length k closed walks from any vertex to itself.
Proof. Note that the graph angles satisfy
e,, where V; is a basis for the ith adjacency matrix eigenspace, and ej V.V.T e, is the (j.j) of V.V.T. These graph angles are just the elementwise square roots of the diagonals of the matrices V.V.T. As f: (VVV,T = diag(VVV,TT is permutation equivariant linear function from matrices to vectors, 2-IGN on V.V,T can exactly compute this with 0 eπror. Then 2-IGN can learn an elementwise MLP to approximate the elementwise square root (oddia((V,V, = /diag(V.W) VVV, to arbitrary precision. Finally, there may be remaining operations fa that are permutation invariant or permutation equivariant from vectors to vectors: for instance, the ary typically gathered into matrix of size I n where the columns are lexicographically sorted (1 is the number of eigenspaces) (Cvetković et al., 1997), or may have permutation invariant readout compute subgraph count. A
ai = [IV.V e, Ve
(49)
37

---

Published as a conference paper at ICLR 2023
DeepSets can approximate fs without any higher order tensors besides vectors (Zaheer al., 2017; Segol & Lipman, 2019).
As 2-IGNs can approximate each individually, single 2-IGN can approximate fa o f2 fi by Lemma 6. 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.
L
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 2 3, let C2 denote the cycle graph of size k. and Cg + Cs denote the graph that is the union of two disjoint cycle graphs of size k. MPNNs cannot distinguish between C2R and C + C 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 Cas is but C2 + Cg is not. Also, it cannot count the number of 3, 4, or 5 cycles, as Cj + C₁ has two k cycles while C2s has no cycles. Likewise, any node in Ck + Ck has more length closed walks than any node in C2k. This is because any length & closed walk in C24 has analogous closed walk in Ck + Ck. but the nodes in C + Cj also have a closed walk that completely goes around a cycle.
I USEFUL LEMMAS
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.
Lemma (Passing to the quotient). Let X and y topological spaces, and let //G be a quotient space, with corresponding quotien! map a. Then for every continuous G-invariant function f X Y, there is unique continuous f X// + y such that f f= f o.
Proof. For z E X/G. by surjectivity of i we can choose an T2 E X such that ((x2) = z. Define f: B//G- + by f(2) = f(zz). This is well-defined, since if (x22) = x(x) for any other æ E X, then gx, = x for some g so
f(x) = f(gx)) = f(x=)= f(2),
(50)
where the second equality the G-invariance of ʃ. Note that f is continuous by the universal property of quotient spaces. Also, ff is the unique function such that f o σ; if there were another function h X/G +/G+>) y with h(z)) # f(=), then h(=)) + f(x2), (xT()))) = l(==) + f(x2).
Next, we give the First Fundamental Theorem of (d), a classical result that has been recently used for machine learning by Villar et al. (2021). This result shows that orthogonally invariant f(V) can be expressed as function (VVVT). We give a proof that if f is continuous, then h is also continuous.
Lemma 2 (First Fundamental Theorem of O(d)). continuous function f BRo + Wdow is orthogonally invariant, i.e. f(VQ) = for all Q E O(d), if and only if f(V) = h(VV ) for some continuous h.
Proof. If f(V) = h(VVT), then we have f(VQ) = h(VQQ = 1(VVT) so f is orthogonally invariant.
For the other direction, invariant theory shows that the O(d) invariant polynomials are generated by the inner products of_ Uj. where v; E dRd are the rows of V (Kraft & Procesi, 1996). Let p: Raad > R be the map p(V) VVT Then González & de Salas (2003) Lemma 11.13 shows that the quotient space nxd /Odd) is homeomorphic to closed subset p(Raxd)
2 C Raxn Let 인 refer to this homeomorphism, and note that P o क = p by passing to the quotient (Lemma I). Then any continuous O(d) invariant / passes a unique continuous f RRaxd R /O(d) - Te (Lemma 1), so f = =for π where π is the quotient map. Define h Z - Rdaa by h = f o p-! and note that h is composition of continuous functions and hence continuous. Finally, we have that 1(VVT)= h (VV) i =VV S(V), so are done.
38

---

Published as a conference paper at ICLR 2023
The next lemma allows us to decompose quotient of product space into product of smaller quotient spaces.
Lemma 3. Let 2i....;2', Ns be topological spaces and GI...., G& be topological groups such that each G2 acts continuously X. Denote the quolient maps by T, X, - X, K./Gy. Then the quolient of the product is the product of the quotient, i.e.
(Xi X ... x \G) X ... G+) = (M//GI) x x... ... x (Ne/Gu), and # .... X T X1 X Xx + (R1/G1) x .... (Nz/Ga) quotient map.
(51)
First, we show that गı x ... Ty is a quotient map. This is because the quotient map of any continuous group action is an open map, so each is an open map, 2. the product of open maps is an open map, so #1 x ... Ty is an open map and 3. a continuous surjective open map is a quotient map, TT X .... Tk. which is continuous and surjective, is quotient map.
Proof.
Now, we need only apply the theorem of uniqueness of quotient spaces to show (51) (see e.g. Lee (2013), Theorem A.3I). Letting q X1 x... X₂ - (X1 x
G₂) denote the quotient map for this space, it is easily seen that g(z1..... 2x) = ((31 ((....... 3kk) if and only T& (3/1 Vks), since either of these true if and only if there exist Di E G. such that F; = 9e3li for each i. Thus, we have an isomorphism of these quotient spaces.
(G1
Ti Ty (Z1, ................................ IKk ,
The following lemma shows that quotients of compact spaces are also compact, which is useful for universal approximation on quotient spaces.
Lemma 4 (Compactness of quotients of compact spaces), Let X be a compact space. Then the quotient space X // is compact.
Proof. Denoting the quotient map by т X - X/G and letting {UaJa be an open cover of X/G. we have that {T ( a is an open cover of X. By compactness of X, we can choose a finite (Ua))
subcover {π (Ua.))=II.... Then (U,,)
= Jim,...... by surjectivity, and
is thus an open cover of X/G.
The Whitney embedding theorem gives nice condition that we apply to show that the quotient spaces X/G that we deal with embed into Euclidean space. says that when X' X/G is a smooth manifold, then it can be embedded into Euclidean space of double the dimension of the manifold. The proof is outside the scope of this paper.
Lemma (Whitney Embedding Theorem (Whitney, 1944)). Every smooth manifold M of dimension 0 can be smoothly embedded in 2
Finally, we give a lemma that helps prove universal approximation results. It says that if functions that we want approximate can be written as compositions f fz c .... o f1, then it suffices to universally approximate each fi and compose the results to universally approximate the f. This especially useful for proving universality of neural networks, as we may use some layers to approximate each Si, then compose these layers to approximate the target function
Lemma 6 (Layer-wise universality implies universality). Let Z C Rdo be a compact domain, let Fi.....FF Fr, be families of continuous functions where F, consists of functions from Rdi:1 -> RRd. for some di....,1ı. Let F be the family of functions {Jr. o... 2 + Rdz, fs E Fi} that are compositions of functions ft E F,
For each i, let D be a family of continuous functions that universally approximates F., Then the family of compositions = (Ør .... . 00 : Oi E D.) universally approximates F.
Proof. Let f fLo.... f1 F. Let 2 Z, and then for > 2 ž, (z, Then each 2, is compact by continuity of the ft. For i L, let 2, 2,, and for i = L. let 2, be compact set containing 2,, such that every ball of radius
centered a point in 2,, is still contained in Z,,-
Let E > O. We will show that there is Φ E & such that || م1|b0 < e by induction on L. This holds trivially for I. as then +- $1.
39

---

Published as a conference paper at ICLR 2023
Now, let L 2 2, and suppose it holds for L 1. By universality of L2, choose a ØL 2
Ie E & such that l - fu ll < c/2. As ΦL is continuous on compact domain, it is also
uniformly continuous, so we can choose 8 > 0 such that lly ø112 < ā = ( - 22 < e/2.
Let d min(ō, 1). By induction, we can choose ΦL-1 o... ... o 01. de D such that
| o... 01 f ..... om <
(52)
Note that d ..... (1 ZL, because for each 2, Φ ... oi (x) is within 8 I 1 Euclidean distance ft.11 o... f1 (x) Zr., it contained in 3₁. by construction. Thus, may define Φ Φr. o ... 01 2
IRd, and compute that
g fl I 1 02 o fL-1
fill 11 fL- o.... fll < 1 oz o fL-10 o... fill + c/22
(53)
(54)
since |0 fo < c/2. To bound this other term, let x E 2, and for y -L-11 ...
(z)
and = fL-1 .... o fi (2), we know that [ly 2112 < 6, so (yo - @ < c/2 by uniform
continuity. As this holds for all x, we have ( or fi-1 .... filloc S e/2, | /llo <
and we are done.
FURTHER EXPERIMENTS
J.1 GRAPH REGRESSION WITH NO EDGE FEATURES
Table 7:
Results the ZINC dataset with 500k parameter budget and edge features. Numbers the mean and standard deviation over 4 runs each with different seeds.
Base model
Positional encoding
k
#params
Test MAE (L)
No PE
16
497k
0.348
GIN
LapPE (flip)
16
498k
0.341
SignNet
16
500k
0.238
No PE
16
501k
0.46440.011
GAT
LapPE (flip)
16
502k
0.462+4.013
SignNet 16
499k
0.24310.008
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 Laplacian positional encodings with sign flipping data augmentation.
J.2 COMPARISON WITH DOMAIN SPECIFIC MOLECULAR GRAPH REGRESSION MODELS
Table 8: Comparison with domain specific methods on graph-level regression tasks. Numbers are test MAE, so lower is better. Best models within a standard deviation are bolded.
ZINC (10K) 1
ZINC-full 1
HIMP & (Fey al., 2020)
.151 .006
.036
CIN-small i (Bodnar et al., 2021)
.0944.00 .004
.0444.003 0003
CIN f (Bodnar et al., 2021)
.079
.022 .002
SignNet (ours)
.084 006
.024 .003
In Table 8, we compare our model against methods that have domain-specific information about molecules built into them: HIMP (Fey et al., 2020) and CIN (Bodnar et al., 2021). We see that SignNet is better than HIMP and CIN-small these tasks, and is within standard deviation of CIN. The SignNet models are the same as the ones reported in Table 2. Once again, we emphasize that SignNet is domain-agnostic.
40

---

Published as a conference paper at ICLR 2023
J.3 LEARNING SPECTRAL GRAPH CONVOLUTIONS
Table Sum of squared errors for spectral graph convolution regression (with no test set). Lower better. Numbers are mean and standard deviation over 50 images from He et al. (2021).
Low-pass
High-pass
Band-pass
Band-rejection
Comb
GCN
.111 0008
3.092
1.720
1 1.418
1.753+11.17
GAT
.113_
.954 696
1.105
4543
.638
GPR-GNN
.033_ 032
.012 007
.137
.256
.369
ARMA
.053 029
0422..024 024
.107
.148 1.09
.202..116
ChebNet
.003 1039_000 .02
.001 1.001
.005..003
.009 1.006
.022:.0016
BernNet
.001
.001 1.001
,000
0488..042
1.079.019
Transformer
3.662
3.715 11.8
1,30
1,506
3.178
Transformer Eig Flip
4.454_2.32
4.425 +2.38
1.651
2.567
3.720
Transformer Big Abs
2.727
3.172+1..1
1. 1.264
1.445
2.607
DeepSets SignNet
.004_.013
0886
.021
0088
.003
Transformer SignNet
.003_.016
.004+.025
10014.04
.0061.023
.0931.641
DeepSets BasisNet
_009_.018
003
.008
.004
.015
Transformer BasisNet
.079-.771
.014+.038
+005
.006+.016
.014+.051
To numerically test the ability of our basis invariant networks for learning spectral graph convolutions, we follow the experimental setups of Balcilar et 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. Then apply the same spectral graph convolutions them as in He et al. (2021), and train neural networks to learn these as regression targets. As in prior work, we report sum of squared errors the training set to measure expressivity.
We compare against message passing GNNs (Kipf & Welling, 2017: Veličković et al., 2018) and spectral GNNs (Chien et al., 2021; Bianchi et al., 2021; Defferrard et al., 2016; He et 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) in BasisNet for é, use a DeepSets for in both cases, and then feed the features into another DeepSets or a standard Transformer (Vaswani al., 2017) to make the final predictions. That is, we are only given graph information through the eigenvectors and eigenvalues, and we do not use message passing.
Table 9 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 spectral GNNs GPR-GNN and ARMA on all tasks. Also, our networks outperform all other methods on the band-rejection and comb filters, and are mostly close to the best model on the other filters.
Runtimes. these experiments, for 100 epochs on the same machine, GCN takes .435 seconds, ChebNet takes .675, DeepSets SignNet takes 3.741 seconds, and DeepSets BasisNet takes 6.196 seconds. SignNet and BasisNet are significantly more expensive than the GNN methods in this experiment, in large part because use all 1024 eigenvectors of the 1024 node graph here. In contrast, recall that in Section 4.1, SignNet does not have much overhead over base GNNs on the task with smaller molecular graphs.
K. FURTHER EXPERIMENTAL DETAILS
K.1 HARDWARE, SOFTWARE, AND DATA DETAILS
All experiments could fit one GPU time. Most experiments were run server with 8 NVIDIA RTX 2080 Ti GPUs. We run all of our experiments in Python, using the PyTorch (Paszke 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 & Lenssen, 2019) (MIT License) for experiments with graph data.
41

---

Published as a conference paper at ICLR 2023
The data are all freely available online. The datasets we are ZINC (Irwin 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 free3d. com/3d-mode -ate/aaaatiiaaeeeeeee
.t.ll (Personal Use License), and the human mesh from turbosquid. com/ 3d- models Is water--przz slides 3d-max/ / 10032667 67 (TurboSquid 3D Model License). If 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.
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 a few low resolution images of humans that do not appear to have offensive content. The only other human-related data appears to be the human mesh, which appears to be from a 3D scan of a human.
K.2 GRAPH REGRESSION DETAILS
ZINC. In Section 4.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 be an 8 layer GIN with ReLU activation. The input eigenvector 2y E IR", where 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 layer MLP with batch normalization and ReLU activation. The aggregator is applied separately to the concatenatation of the & different embeddings for each node in a graph, resulting in one single embedding per node. This embedding is concatenated to the node features for that node, and the result passed as input 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 variable quantity, equal to the number of nodes in the underlying graph, an MLP cannot be used for To handle the variable sized input in this case, we take p be an MLP preceded by sum over the outputs. In other words, the SignNet is of the form MLP (E o(e;) + )(-e;) in this case.
As well as testing SignNet, we also checked whether simple transformations that resolve the sign ambiguity of the Laplacian eigenvectors p (Vi,.... .xx) could serve as effective positional encoding. We considered three options. First is to randomly flip the sign of each tu, during training. This is common heuristic used in prior work Dwivedi et al., 2020). Second, take the element-wiss absolute value luy]. This is a 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 e that the majority of entries are non-negative, with ties broken by comparing the - of positive and negative parts. When the tie-break also fails, the sign is chosen randomly. Results for GatedGCN base model on ZINC in Table show that all three of these approaches are significantly poorer positional encodings compared to SignNet.
Laplacian positional encoding (Kreuzer et al., 2021;
Our training pipeline largely follows that of Dwivedi al. (2022), and we use the GatedGCN and PNA base models from the accompanying implementation (see https: //gtthubbbb////////// com/ vi jayadiiiivve vedi75d / gspe) The Sparse Transformer base model architecture we use, which 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 & Lenssen, 2019). For the state-of-the-ar comparison, all baseline results are from their respective papers, except for GIN, which we run.
We used edge features for all models except the Sparse Transformer. For the Sparse Transformer, we found our method of using edge features to somewhat increase training instability, so standard deviation was higher, though mean test MAE was mostly similar to the runs without edge features.
We also run our method on the full ZINC dataset, termed ZINC-full. The result we report for SignNet is 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 al., 2021).
ZINC-full.
42

---

Published as a conference paper at ICLR 2023
Alchemy. We run method and compare with the state-of-the-art Alchemy (with 10,000 training graphs). We use the same data split as Morris et al. (2020b). Our base model is a GIN that takes in edge features (i.e. GINE). The SignNet consists of GIN for & and a Transformer for A. 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 al. (2022), as we build off of their code. We train with an Adam optimizer (Kingma & Ba, 2014) with a starting learning rate of ,001, and minimum learning rate of .000001. The learning rate schedule cuts the learning rate in half with 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).
K.3 SPECTRAL GRAPH CONVOLUTION DETAILS
In Appendix J.3, 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 are the grayscale pixel intensities of each node. Just as 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 28 x 28 middle section). For all experiments we limit each model to 50,000 parameters. We use the Adam (Kingma & Ba, 2014) optimizer for all experiments. For each of the GNN baselines (GCN, GAT, GPR-GNN ARMA, ChebNet, BernNet), settings: either or convolution layers, and a hidden dimension of size 32 or D, where is just large enough to stay with 50,000 parameters (for instance, D 128 for GCN, GPR-GNN, and BernNet).
1024-node graph. The node features X TR.
select the best performing out of 4 hyperparametter
We use DeepSets standard Transformers our prediction network. This takes in the output of SignNet or BasisNet and concatenates it with the node features, then outputs a scalar prediction for each node. We a layer output network for DeepSets SignNet, and 2 layer output networks for all other configurations. All networks use ReLU activations.
For SignNet, we use DeepSets for both & and p. Our è takes in eigenvectors only, then our p takes the outputs of 6 and the cigenvalues. We use three layers for & and
For BasisNet, we use the same DeepSets for o as in SignNet, and 2-IGNs for the Φa. There are three distinct multiplicities for the grid graph (1, 2, and 32), so we only need 3 separate IGNs. Each IGN consists of an 1x*x1 + x layer and two mx + Raxdd layers, where the d' hidden dimensions. There are no matrix to matrix operations used, as the memory requirements are intensive for these > 1000 node graphs. The dd, only take in V.V,T from the eigenspaces, and the p takes the output of the Φd. as well as the eigenvalues.
K.4 SUBSTRUCTURES AND GRAPH PROPERTIES REGRESSION DETAILS
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 model 4-layer GIN model with hidden size 128. We choose ó as a 4-layer GIN (independently applied to every eigenvector) and p as a 1-layer Transformer (independently applied to every node). Combined with proper batching and masking,
have SignNet that takes Laplacian eigenvectors V E R and outputs fixed size sign-invariant encoding node features f(V, A, X) E RRaxd, where varies between graphs but d is fixed. We use this SignNet in our experiments and compare with other methods of handling PEs.
K.S TEXTURE RECONSTRUCTION DETAILS
Table 10: Parameter settings for the texture reconstruction experiments.
Params
Base MLP width
Base MLP layers
@ out dim
p out dim
P. Φ width
Intrinsic NF
328,579
128
6
SignNet 323,563
108
43

---

Published as a conference paper at ICLR 2023
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 a triangle mesh with the lowest 1023 eigenvectors besides the trivial eigenvector of eigenvalue O. We implemented SignNet in the authors' original code, which was privately shared with us. Both and Φ are taken to be MLPs. Hyperparameter settings and number of parameters are given in Table 10. We chose hyperparameters so that the total number of parameters in the SignNet model was no larger than that of the original model.
44


Reviews:
[{"review_id": "z1bJO0H5uos", "reviewer": "Reviewer_BB19", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, SignNet and BasisNet new neural structures are proposed, which are the same as the two key SY invariants displayed by eigenvectors. It is also proved that under certain conditions, they can approximate any continuous function of invariants with the expected eigenvectors. The experimental results show that the proposed method is superior to the forward baseline in molecular graph regression, learning expression graph representation and learning neural field on triangular grid.", "summary_of_the_review": "My research field is not related to this manuscript and I am not very familiar with the research content. ", "strength_and_weaknesses": "In this paper, SignNet and BasisNet new neural structures are proposed, which is interesting", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "fXpgDiAZOd", "reviewer": "Reviewer_aMn3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose SignNet and BasisNet which are invariant to the sign and rotation symmetries that exist in eigenspaces, particularly in the Laplacian context for graphs. They demonstrate a universal approximation theorem with the approach under some conditions. They evaluated SignNet and BasisNet with various experimental tasks/datasets. ", "summary_of_the_review": "Overall a strong paper. Would be stronger if they make their theoretical statements more clear/specifically stated. ", "strength_and_weaknesses": "Strengths:\n\n- The task that the authors are tackling is of general interest and importance, especially given the prevalence of Laplacian eigendecompositions in the literature, and the method/architecture that they propose are to the best of my knowledge novel and original. \n\n- The paper is well written and clearly motivated. \n\n- Their theorem on universal approximation for spectral graph convolutions is significant. \n\n- Their experimental evaluation is comprehensive and demonstrates the efficacy of the proposed approach well. \n\nWeaknesses: \n\n- Proposition 2, Theorem 2 and Proposition 3 are stated somewhat verbally/informally in the main paper. It would be ideal to include a mathematically rigorous statement in the main paper. In particular, given how commonly the term \"universally approximates\" is used in the paper, it was not rigorously defined in the main paper.  Given that there can be different types of universal approximation, it would be best to rigorously define it in the main paper to avoid any ambiguity/confusion. \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "ZZCwLRwje1N", "reviewer": "Reviewer_a8ck", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper introduces two architectures SignNet and BasisNet that respect some basic symmetries inherited by spectral graph methods i) sign flips: if v is an eigenvector then so is −v; and (ii) more general basis symmetries: in higher dimensional eigenspaces there might be infinitely many choices of basis eigenvectors. The authors show that under certain conditions the proposed architectures are universal and can approximate any continuous function of eigenvectors with the proper invariances. Moreover, the networks are theoretically powerful for graph representation learning—they can provably approximate and go beyond both spectral graph convolutions and powerful spectral invariants. Experimental results are shown on molecular graph regression tasks, learning expressive graph representations, and texture reconstruction on triangle meshes. ", "summary_of_the_review": "In summary, this is a strong paper with nice theoretical results. Some aspects that I think should be clarified are the following:\n\n1) While Theorem 1 is interesting and insightful, could you please provide an explanation of what it implies in practice? Does it mean that when the group is a product, we could do separate sums over the elements of the group to achieve invariance? \n\n2) How does the computational complexity of IGN affect the overall complexity of the algorithm?\n\n3) Is there an inductive bias towards locality in SignNet (as in other graph convolutional methods)? \n\n4) Figure 2 needs more explanation. Since the proposed positional encoding schemes can take as input node features, why do we need another GNN layer i.e., GNN(A,X,sigNet or basisNet(V,X)) on the top of that? Is that related to localisation aspects? ", "strength_and_weaknesses": "Strength: Designing proper architectures that preserve symmetries and are more expressive than current ones is a very interesting and open topic in the graph machine learning literature. The proposed architectures in the paper are theoretically sound, and lead to nice integrations of symmetry-preserving positional encodings into a GNN framework. The results are adequately analysed and sufficiently supported.\n\nWeaknesses: Some of the notions are not easy to understand from the text. Theorem 1 which is one of the main results of the paper should be discussed and explained more. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "X6Oss5ht8O_", "reviewer": "Reviewer_cG9j", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work investigates the function invariance w.r.t. eigenvectors of graph Laplacian to reduce the learning complexity, including sign invariance and basis invariance. Then it proposes corresponding SignNet and BasisNet to incorporate these two invariances where many popular models can be directly plugged in as basic models. Moreover, it provides theoretical guarantees that the proposed models are expressive enough to conduct tasks beyond eigenvectors. Finally, the proposed methods are evaluated by synthetic and real-world experiments.", "summary_of_the_review": "I would like to suggest an acceptance.\n\n=== Acknowledgement ===\n\nDue to time limit, I did not check proof in Appendix. The theorems seem to be good intuitively.", "strength_and_weaknesses": "Pros:\n1. The motivation of introducing invariances into the model naturally reduces the learning complexity, which is verified sufficiently by excellent performance on real tasks against strong baselines.\n2. It is very easy to directly plug many popular GNNs into SignNet to achieve performance boost, as shown in Table 1.\n3. The theoretical arguments are comprehensive, including constructing SignNet and expressiveness of SignNet/BasisNet.\n\nCons:\n1. Is BasisNet included in any experiment other than Appendix J.3? I am wondering whether BasisNet suffers high complexity because there might be many distinct multiplicities $d_i$ so that too many IGNs are included. In that sense, is there any way to implement BasisNet efficiently? Also, how is the runtime of BasisNet in Table 9?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%