Laplacian Canonization: A Minimalist Approach to Sign and Basis Invariant Spectral Embedding
Authors: George Ma
Yifei Wang
Yisen Wang
Venue: NeurIPS 2023 poster (2023)
Keywords: Graph Neural Networks
Positional Encoding
Spectral Embedding
Laplacian Eigenvectors

Abstract: Spectral embedding is a powerful graph embedding technique that has received a lot of attention recently due to its effectiveness on Graph Transformers. However, from a theoretical perspective, the universal expressive power of spectral embedding comes at the price of losing two important invariance properties of graphs, sign and basis invariance, which also limits its effectiveness on graph data. To remedy this issue, many previous methods developed costly approaches to learn new invariants and suffer from high computation complexity. In this work, we explore a minimal approach that resolves the ambiguity issues by directly finding canonical directions for the eigenvectors, named Laplacian Canonization (LC). As a pure pre-processing method, LC is light-weighted and can be applied to any existing GNNs. We provide a thorough investigation, from theory to algorithm, on this approach, and discover an efficient algorithm named Maximal Axis Projection (MAP) that works for both sign and basis invariance and successfully canonizes more than 90\% of all eigenvectors. Experiments on real-world benchmark datasets like ZINC, MOLTOX21, and MOLPCBA show that MAP consistently outperforms existing methods while bringing minimal computation overhead. Code is available at https://github.com/PKU-ML/LaplacianCanonization.

Laplacian Canonization: A Minimalist Approach to Sign and Basis Invariant Spectral Embedding
Jiangyan Ma Yifei Wang Yisen Wang
School of Electronics Engineering and Computer Science, Peking University
2 School of Mathematical Sciences, Peking University
National Key Lab of General Artificial Intelligence,
School of Intelligence Science and Technology, Peking University
Institute for Artificial Intelligence, Peking University
Abstract
Spectral embedding is a powerful graph embedding technique that has received a lot of attention recently due to its effectiveness Graph Transformers. However, from a theoretical perspective, the universal expressive power of spectral embedding comes at the price of losing two important invariance properties of graphs, sign and basis invariance, which also limits its effectiveness on graph data. To remedy this issue, many previous methods developed costly approaches to learn new invariants and suffer from high computation complexity. In this work, we explore a minimal approach that resolves the ambiguity issues by directly finding canonical directions for the eigenvectors, named Laplacian Canonization (LC). As a pure pre pre-processing method, LC is light- weighted and can be applied to any existing GNNs. We provide a thorough investigation, from theory to algorithm, on this approach, and discover (MAP) that works for both sign and basis invariance and successfully canonizes more than 90% of all eigenvectors. Experiments real-world benchmark datasets like ZINC, MOLTOX21, and MOLPCBA show that MAP consistently outperforms existing methods while bringing minimal computation overhead. Code available at https:// /gi thub.
efficient algorithm named Maximal Axis Projection
Introduction
Despite the popularity of Graph Neural Networks (GNNs) for graph representation learning [55, 56, 54, 27. 13], it is found that many existing GNNs have limited expressive power and cannot tell the difference between many non-isomorphic graphs [57, 35]. Existing approaches improve expressive power, such as high-order GNNs [35] and subgraph aggregation [9], often incur significant computation costs over vanilla GNNs, limiting their use practice. In comparison, a simple but effective strategy is to use discriminative node identifiers. For example, GNNs with random features can lead universal expressive power [44, 1]. However, these unique node identifiers often lead to the loss of the permutation invariance property of GNNs, which is an important inductive bias of graph data that matters for sample complexity and generalization [24]. Therefore, during the pursuit of more expressive GNNs, we should also maintain the invariance properties of graph data. Balancing these two conflicting demands presents a significant challenge for the development of advanced GNNs.
Spectral embedding (SE) is a classical approach to encode node positions using eigenvectors of the Laplacian matrix L, which has the advantage of being expressive and permutation equivariant.
"qqual Contribution.
*Corresponding Author: Yisen Wang (yisen.wang
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Table 1:
Comparison between prior works and our method. is the number of nodes, m is the exponent of the feature dimension of BasisNet [29, 33].
pre-processing time
permutation invariance
addresses sign anbiguity
addresses basis ambiguity
feature dimension
Method
universality
LapPE [17]
e n1
x
x
n
RandSign [17]
0 3
x
x
SAN [25]
(n
x
SignNet [29]
(n
x 2n
BasisNet [29]
(n
V
td
MAP (ours)
O(n²²)
n
GNNs using SE can attain universal expressive power (distinguishing any pair of non-isomorphic graphs) even under simple architectures (results in Section 2). However, spectral emhedding faces two additional challenges in preserving graph invariance: sign ambiguity and basis ambiguity, due to the non- non-uniqueness of cigendccomposition. These ambiguities could lead to inconsistent predictions for the same graph under different eigendecommositions.
Many methods have been proposed to address sign and basis ambiguities of spectral embedding. popular heuristic is RandSign [17] which randomly flips the signs of the eigenvectors during training. Although is simple to use, this data augmentation approach does not offer any formal invariance guarantees and can lead to slower convergence due to all possible 2n sign flips. An alternative involves using sign-invariant eigenfunctions to attain sign invariance [25], which significantly increases the time complexity to (n*)) Another solution is to design extra GNN modules for sign and basis invariant embeddings, e.g., SignNet and BasisNet [29], which can also add a substantial computational burden. Therefore, as summarized in Table 1, existing spectral embedding methods are all detrimental in a certain way that either hampers sign and basis invariance, or induces large computational overhead. More discussions about the related work can be found in Appendix B.
In this work, we explore new approach called Laplacian Canonization (LC) that resolves the ambiguities by identifying a unique canonical direction for each eigenvector, amongst all its sign and basis equivalents. Although is relatively easy to find canonization rule that work for certain vectors, up to now, there still lacks a rigorous understanding of what kinds of vectors are canonizable and whether we could find a complete algorithm for all canonizable features. In this paper, we systematically answer this problem by developing a general theory for Laplacian canonization and characterizing the sufficient and necessary conditions for sign and basis canonizable features.
Based on these theoretical properties, we propose practical canonization algorithm for sign and basis invariance, called Maximal Axis Projection (MAP), that adopts the cormutation-invarii axis projection functions to determine the canonical directions. We theoretically characterize the conditions under which MAP can guarantee sign and basis canonization, and empirically verify that this condition holds for most synthetic and real-world graphs. It is worth noting that I.C is lightweight approach since is only a pre-processing method and does not alter the dimension of the spectral embedding. Empirically, we show that employing the MAP-canonized spectral embedding yields significant improvements over the vanilla RandSign approach, and even matches SignNet on large-scale benchmark datasets like OGBG [20]. We summarize our contributions as follows:
We explore Laplacian Canonization (LC), new approach to restoring the sign and basis invariance of spectral embeddings via determining the canonical direction of eigenvectors in the pre-processing stage. We develop general theoretical framework for LC and characterize the canonizability of sign and basis invariance.
We propose efficient algorithm for Laplacian Canonization, named Maximal Axis Pro- jection (MAP), that works well for both sign and basis invariance. In particular, we show that MiP-sign is capable of canonizing all sign canonizable eigenvectors and thus is com- plete. The assessment of its feasibility shows that MAP can effectively canonize almost all eigenvectors random graphs and more than 90% eigenvectors real-world datasets.
We evaluate the MAP-canonized spectral embeddings on graph classification benchmarks including ZINC, MOLTOX21 and MOLPCBA, and obtain consistent improvements over previous spectral embedding methods while inducing the smallest computational overhead.

---

2 Benefits and Challenges of Spectral Embedding for GNNs
Denote a graph G EV X) where Vis is the vertex set of size n. E is the edge set, and X E Raxd the input node features. We denote A as the adjacency matrix, and let A D AD D- + A) 3 be the normalized adjacency matrix, where I denotes the augmented self-loop, D is the diagonal degree matrix of Á defined by Di, = Σj= At.-- A graph function f[[x, A)) permutation invariant if for all permutation matrix P E Raxn we have f((PX, PAPTT) [[x,A)). Similarly, f is permutation equivariant if
= Pf(X,
Spectral Embedding (SE). Considering the limited expressive power of MP-GNNs, recent works explore more flexible GNNs like graph Transformers [58, 62, 16, 25, 42]. These models bypass the explicit structural inductive bias in MP-GNNs while encoding graph structures via positional embedding (PE). A popular graph PE is spectral embedding (SE), which uses the eigenvectors U of the Laplacian matrix = I - Á with eigendecomposition L = U U where = diag (A) is the diagonal matrix of ascending cigenvalues λ I S An. and the i-th column of U is the eigenvector corresponding to A, It is casy to see that spectral embedding is permutation equivariant: for any node permutation P of the graph, PU is the spectral embedding of the new Laplacian since PLP = (PU) Therefore, a commutatioo-invariian GNN (e.g., DeepSets [63], GIN [57],
Graph Transformer [16)) using the SE-augmented input features X = [ U] remains permutation invariant.
Reweighted Spectral Embedding (RSE). Previous works have shown that using spectral embedding improves the expressive power of MP-GNNs [6]. Nonetheless, we find that SE alone is insufficient to approximate an arbitrary graph function, as it does not contain all information about the graph, in particular, the eigenvalues. Consider two non-isomorphic graphs whose Laplacian matrices have identical eigenvectors but different eigenvalues. As their SE is the same, a network only using SE cannot tell them apart. To resolve this issue, propose reweighted spectral embedding (RSE) that additionally reweights each eigenvector u, with the square-root of its corresponding eigenvalue As i..,, URSE = UA! With the reweighting technique, RSE incorporates eigenvalue information without need extra dimensions.
Universality of RSE. In the following theorem, we prove that with RSE, any universal network on sets (e.g., DeepSets [63] and Transformer [61]) is universal on graphs while preserving permutation invariance. All proofs are deferred to Appendix K.
Theorem Let Q C Raad x Ruxa be a compact set of graphs, [X, A] E S. Let NN be a universal neural network on sets. Given any continuous invariant graphfunction
function I defined over Ω and arbitrary
e >>00 0, there exist set of NN parameters such that for all graphs [X, A] E Ω
INN(X, (N((XUUnSE))
(((X,A) <.
As far as we know, this theorem is the first to show that, with the help of graph embeddings like RSE, even an MLP network like DeepSets [63] (composed of a node-wise MI.P, global pooling layer, and a graph-level MLP) can achieve universal expressive power to distinguish any pair of non-isomorphic graphs. Notably, it does not violate the NP- SP-hardness of graph isomorphism testing, since training NN itself is known to be NP-hard [10]. Actually, it is not always necessary to use all spectra of the graph. Existing studies find that high-frequency components are often unhelpful, or even harmful for representation learning [5, 19]. Thus, in practice, we only use the first k low-frequency components of RSE. An upper bound on the approximation error of truncated RSE can be found in Appendix K.10.
Ambiguities of eigenvectors. Although RSE enables universal GNNs, there exist two types of ambiguity in eigenvectors that hinder their applications. The first one, known as sign ambiguity, arises when an eigenvector ux corresponding to eigenvalue X, is equally valid with its sign flipped, i.e., u, is also eigenvector corresponding to A, The second one, termed basis ambiguity, occurs when eigenvalues with multiplicity degree d, > can have any other orthogonal basis in the subspace spanned by the corresponding eigenvectors as valid eigenvectors. To be specific, for multiple eigenvalues with multiplicity degree de > 1, the corresponding eigenvectors Ux, E R form an orthonormal basis of subspace. Then any orthonormal matrix Q E Rdd can be applied to Ux to generate a new set of valid eigenvectors for X; Because of these ambiguities, we can get distinet GNN outputs for the same graph, resulting in unstable and suboptimal performance [17, 25, 18, 29]. In Appendix A, we elaborate the challenges posed by these ambiguitics.
3

---

Table 2: The ratio of uncanonizable eigenvectors W.E. each invariance property with our MAP algorithm on three woaldworld datasets: ZINC, MOLTOX21, and MOLPCBA.
Invariance
ZINC
MOLTOX21 MOLPCBA
Sign
2.46 %
3.04 %
2.24 %
Basis Total
1.59 %
3.31 %
7.37 %
4.05 %
6.35 %
9.61 %
3 Laplacian Canonization for Sign and Basis Invariance
Rather than incorporating additional modules to learn new sign and basis invariants [25, 29], we explore straightforward, learning-free approach named Laplacian Canonization (LC). The general idea of LC is to determine a unique direction for each eigenvector u among all its sign and basis equivalents. In this way, the ambiguities can be directly addressed the pre-proce pro-procssiing stage. For example, for two sign ambiguous vectors u and uu, we aim to find an algorithm that determines a unique direction among them to obtain sign invariance. Despite some na've canonization rules (discussed in Appendix G. there still lacks systematical understanding of the following key questions of I.C.
1. What kind of canonization algorithm should we look for? (Section 3.1)
2. What kind of cigenvectors are canonizable or non-canonizable? (Section 3.2)
3. Is there an efficient canonization algorithm for all canonizable features? (Section 3.3)
In this section, answer the three problems by establishing the first formal theory of Laplacian canonization and characterizing the canonizability for sign and basis invariance; based on these analyses, we also propose an efficient algorithm named MAP for LC that is guaranteed to canonize all sign canonizable features. To get a glimpse of our final results, Table 2 shows that MAP can resolve both sign and basis ambiguities for more than 90% of all eigenvectors on real-world data.
3.1 Definition of Canonization
To begin with, we first find out what properties a desirable canonization algorithm should satisfy. The ultimate goal of canonization is to eliminate ambiguities by selecting canonical form among these ambiguous outputs. Generally speaking, we can characterize ambiguity as a multivalued function f: X ), i.e., there could be multiple outputs yı,..., - Yn corresponding to the same input In our sign/basis ambiguity case, ff refers to a mapping from graph x E X' to the eigenvectors a certain eigenvalue via the ambiguous eigendecompossttin. The ambiguous eigenvectors are not independent; they are related by a sign/basis transformation. In general, we can assume that all possible outputs .1..... Vn of any x belong the same equivalence class induced by some group action g E G, where G acts on y. That is, if (x) = 21 = 3/. then there exists E G such that y1 = 9V22 Moreover, eigenvectors of graphs obey a fundamental symmetry: permutation equivariance. In general, we assume that f is equivariant to group H acting on X' and y. That is, for any h E H, if y1..... are all possible outputs of x, then hy1. hyn are all possible outputs of hz.
Specifically, for the goal of canonizing ambiguous eigenvectors, iee,, Laplacian canonization, we are interested in algorithms invariant to sign/basis transformations in the corresponding orthogonal group G (0(1) for sign invariance and (dd) for basis invariance). Meanwhile, to preserve the symmetry of graph data, this algorithm should also maintain the permutation equivariant property of eigenvectors (Section 2) w.r.f the permutation group H. Third, it also should still be discriminative enough to produce different canonical forms for different graphs (like the original spectral embedding). Combining these desiderata, we have a formal definition of canonization.
Definition 1. A mapping A: y - y is called a (f, G, H cannnizatiin when it satisfies:
A is G-invariant: Vy V.9 E G. A(y) A(gv);
A H-equivariant:
Yx X, E H, ( hA(s(=));
A is universal: Vx E X, H, + hx = A(f(z) # A(f(x)).

---

Accordingly, for any Z E X, if there exists a canonization f x, we say x is canonizable.
3.2 Theoretical Properties of Canonization
Following Definition I, we are further interested in the question that whether any eigenvector is canonizable, i.e., there exists a canonization that can determine its unique direction. Unfortunately, the answer is NO. For example, the vector (1, 11 cannot be canonized by any canonization algorithm, since a permutation of u gives (-1. 1) that equals to - =u. But as long as there only a small number of uncanonizable eigenvectors like u, canonization algorithm can still resolve the ambiguity issue to a large extent.
Therefore, we are interested in the fundamental question of which eigenvectors are canonizable. The following theorem establishes a general necessary and sufficient condition of the canonizability for general groups G, H, which may be of independent interest.
Theorem 2. An imput x X canonizable on the embedding function f iif there does not exist h H and E G such that x + ha and f f(ax) (x).
This theorem states that for inputs from the same equivalence class in X' (induced by H), as long as they are not mapped to the same equivalence class in ) (induced by G), these inputs are canonizable. In particular, by applying Theorem 2 to the specific group G induced by sign/basis invariance, we can derive some simple rules to determine whether there exists canonizable rule for given eigenvector(s).
Corollary (Sign canonizability). A vector u E R is canonizable under sign ambiguity iff there does not exist permutation matrix P E Rux* such that u = -Pu.
Corollary 2 (Basis canonizability). The base eigenvectors U gaxd of the eigenspace V are canonizable under basis ambiguity iff there does not exist a permutation matrix P E Baxx such that U + PU and span PU) = span(U) V.
Remark. From probabilistic view, almost all eigenvectors canonizable. Let U Raxd be basis vectors sampled from a continuous distribution in R", then Pr(U is canonizable] = 1.
In the next subsection, we will further design an efficient algorithm to canonize all sign and basis canonizable eigenvectors in the pre-process reepprocssiing stage, so the network does not have to bear the ambiguities of these eigenvectors.
3.3
MAP: A Practical Algorithm for Laplacian Canonization
Built upon theoretical properties in Section 3.2, we aim design general, powerful, and efficient canonization to resolve both sign and basis ambiguities for as many eigenvectors as possible. Here, we choose adopt axis projection the basic operator in our canonization algorithm named Maximal Axis Projection (MAP). The key observation is that the standard basis vectors (i.e., the axis) of the Euclidean space e; E I are permutation equivariant, and in the meantime, the eigenspace spanned by the eigenvectors V span(U) are also permutation equivariant. This means that when projecting the axis the eigenspace, the obtained angles are also permutation equivariant, based on which we could apply permutation invariant functions (such as max) to obtain permutation invariant statistics that can be used for canonization. Meanwhile, due the generality of projection, it can be applied to both sign ambiguity (for a single eigenvector) and basis ambiguity (for the eigenspace with multiple eigenvectors). We provide illustrative examples to help understand this algorithm in Appendix F.
Preparation step: Axis projection. Consider unit eigenvector(s) U E Rexd corresponding to an eigenvalue À with geometric multiplicity d > 1. These eigenvectors span a d-dimensional eigenspace V= SUan(U) with the projection matrix P = T To start with, we calculate the projected angle between V and each standard basis (i.e., the axis) of the Euclidean space e; (a one-hot vector whose i-th element is 1), i.e., a; = |e, i = 1,..., Assume that there are i distinct values in {a,, = 1, ...... , n), according which we can divide all basis vectors {e,) into A disjoint groups B, (arranged in descending order of the distinct angles). Each B; represents an equivalent class of axes that u, has the same projection on. Then, we define summary vector æ; for the axes in each group B; as their total sum x; Ee, Ej + c, where is tunable constant. Next, we introduce how to adopt these summary vectors canonize the eigenvectors for sign and basis invariance, respectively.
In this case, sign invariance conflicts with permutation equivariance: making u and -u output the same vector violates permutation equivariance, and vice versa.
5

---

3.3.1 Sign Canonization with MAP
Step 1. Find non-orthogonal axis. For sign canonization, we calculate the angles between the eigenvalue and each summary vector e; one by one, and terminate the procedure as long as we find a summary vector æs with non-zero angle ar u + 0. and return <none> otherwise.
min; 0 if Φ + 2 <none?,
where & {i au 0; 03.
Φ 2,
Assumption 1. There exists summary vector æt that is non-orthogonal to i.e., u Th + 0,
Step 2. Sign canonization. As long as Assumption holds, we can utilize æn to determine the canonical direction u² by requiring its projected angle to be positive, i.e.
u,
if u x > 0, u. if T Th <
(2)
We call this algorithm MAP-sign, and summarize it in Algorithm in Appendix C.I. The following theorem proves that it yields valid canonization for sign invariance under Assumption 1.
Theorem 3.
Under Assumption 1, our MAP-sign algorithm gives a sign-invariant, permutaaiion equivariant and universal canonization of
One would wonder how restrictive the non non-orthogonality condition (Assumption 1) is for sign canonization. In the following theorem, we establish a strong result showing that sign canonizability is equivalent to non-orthogonality. In other words, any sign canonizable eigenvectors can be canonized by Min-sign. Due to this equivalence, MAP-sign can also serve as complete algorithm to determine sign canonizability: vector u is sign canonizable iff æn is not <none> in equation 1.
Theorem 4. A vector u E RR is sign canonizable iff there exists a summary vector In s.f. u z4 *
proved in Appendix K.5 and experimentally verified in Appendix C.2. We also show that MAP is not the only complete canonization algorithm for sign sinvariance by proposing another polynomial-basee in real-world datasets are sign canonizable. For instance, on the ogbg-molhiy dataset, the ratio of non-canonizable eigenvectors is only 2.8%. A thorough discussion on the feasibilty of Assumption is in Appendix G.I. For the left non-canonizable eigenvectors, we could apply previous methods (like RandSign, SAN, and SignNet) to further eliminate their ambiguity, which could save more compute since there are only few non-canonizable eigenvectors. In practice, we also obtain good performance by simply ignoring these non-camonizable features.
Remark. Theorem
algorithm Appendix K.9. We observe that most eigenvectors
3.3.2 Basis Canonization with MAP
We further extend MiP-sign to solve the more challenging basis ambiguity with multiple eigenvectors, named MAP-basis. Now, MAP relies on two conditions to produce canonical cigenvectors. The first one requires there are enough distinctive summary vectors determine d canonical eigenvectors.
Assumption 2. The number of distinctive angles k (i.e., the number of summary vectors (z;}) is larger or equal to the multiplicity i.e., k 2 d.
Under this condition, we can determine each iteratively with the corresponding summary vector T;S At the i-th step where ui.... un-1 have already been determined, we choose u, to be the vector that is closest the summary vector æ; in the orthogonal complement space of (u1,..., (1-1) in V:
u: arg max u
D
s.t. u (u
1u =1
With compact feasibility region, the maximum is attainable, and we can further show that the solution u, unique (c.f., the proof of Theorem 5). Equation can be directly solved using the projection matrix of (u1,..., 1 (see details in Algorithm 3 in Appendix C.1). Repeating this process gives us a canonical basis of V. We also require non-orthogonality condition at each step to obtain a valid eigenvector.

---

Assumption 3. For any 1 S S d, z; is not perpendicular to (ui,.....
u,-1)
We summarize MAP-basis Algorithm in Appendix C.I. In Theorem 5, we prove under Assump- tion 2 and Assumption 3, MAP-basis gives basis-invariant, permutation-qquivariaat and universal canonization of U. Though, in this scenario, MAP- -aaiiss cannot canonize all basis canonizable features, and whether such an algorithm exists remains open problem for future rescarch.
Theorem 5. Under Assumption 2 and Assumptioo 3, our MAP-basis algorithm gives a basis-invarian, permutation-eeuivvrrian equivariant and universal canonization of U.
Remark. Assumption and Assumption 3 exclude some symmetries of the eigenspace, which we discuss in details in Appendix G.2. For random orthonormal matrices, the possibility that either assumption is violated is equal to 0, which we verify with random simulation in Appendix C.3. For real-world datasets, these assumptions are not restrictive either. For instance, on the large ogbg- molpeba dataset, the eigenvalues violating Assumption 2 or Assumption 3 make up 0.87% of all eigenvalues. More statistics and discussions are provided in Appendix G.2.
3.3.3 Summary
We provide the complete pseudo-code of MAP to address both sign and basis invariance in Ap- pendix C. along with a detailed time complexity analysis. Overall, the extra complexity introduced by MAP is On log n)). which is better than eigendecomposition itself with O(z)). ). It only needs to be computed once per dataset and can be easily incorporated with various GNN architectures.
Combining Theorem 1, Theorem 3 and Theorem 5 gives us the universality of first-order GNNs [33] such that it respects all graph symmetries under certain assumptions (Assumptions 1, 2 & 3). We show that the probability of violating these assumptions asymptotically converges to zero on random graphs (see Appendix H). We also count the ratio of violation in real-world datasets in Table 2, and observe that the ratio of uncanonizable eigenvectors is less than 10% on all datasets. Thus, MAP greatly eases the harm caused by sign and basis ambiguities.
So far only GNNs using higher-order tensors have achieved universality while respecting all graph symmetries [33, 24]. but they are typically computationally prohibitive in practice. It is still an open problem whether it is also possible for first-order GNNs. The proposed Laplacian Canonization presents approach in this direction trying to alleviate the harm of sign and basis ambiguities in a minimalist approach. By establishing snweerality-invarinne results for first-order GNNs under certain assumptions, LC could hopefully could bring some insights to the GNN community.
4 Experiments
We evaluate the proposed MAP positional encoding on sparse MP-GNNs and Transformer GNNs using PyTorch [40] and DGL [53]. For sparse MP-GNNs we consider GatedGCN [11] and PNA [15], and for Transformer GNNs we consider SAN [25] and GraphiT [34]. We conduct experiments three standard molecular benchmarks -ZINC [22], GGBG-MOLTOX21 and OGBG-MOLPCBA [20]. ZINC and MOLTOX21 are of medium scale with 12K and 7.8K graphs respectively, whereas MOLPCBA is of large scale with 437.9K graphs. Details about these datasets are described in Appendix L. We follow the same protocol as in Lim et al. [29], where replace their SignNet with a normal GNN and the Laplacian eigenvectors with our proposed MAP. We fairly compare several models on fixed number of 500K model parameters on ZINC and relax the model sizes to larger parameters for evaluation on the two OGB datasets, as being practised on their leaderboards [20]. We also compare our results with GNNs using LapPE and random sign (RS) [17], GNNs using SignNet [29], and GNNs with no PE. For a fair comparison, all models use limited number k of cigenvectors for positional encodings. The results of all our experiments are presented in Table 3, 5, Further implementation details are included in Appendix M.
4.1 Performance on Benchmark Datasets
As shown in Table 3, & 5, using MAP improves the performance of all GNNs on all datasets, demonstrating that removing ambiguities of the eigenvectors is beneficial for graph-level tasks. First, by comparing models with LapPE and RS with models with no PE, we observe that the use of LapPE significantly improves the performance on ZINC, showing the benefits of incorporating expressive
7

---

PEs with GNNs, especially with MP-GNNS whose expressive power is limited by the 1-WL test. However, on MOLTOX21 and MOLPCBA, using LapPE has no sigmificant effects. This is because unlike ZINC, OGB-MOI. datasets contain additional structural features that are informative, e.g., an atom is in ring, among others [18]. Thus the performance gain by providing more positional information is less obvious. Second, MAP outperms LapPE with RS by large margin especially on ZINC. Although RS also alleviates sign ambiguity by randomly flipping signs during training, MAP removes such ambiguity before training, enabling the network to focus on the real meaningful features and achieves a better performance. Third, we also observe that MAP and SignNet achieve comparable performance. This is because both methods aim at the same However, SignNet does so in the training stage while MAP does so in the pre-processing stage, thus the latter is more computationally efficient. Lastly, would also like to highlight that as a kind of positional encoding, MAP can be easily incorporated with any GNN architecture by passing the pre_ pre_transfor transfono function to the dataset class with single line of code.
elaminatin ambiguity.
Table 3: Results on ZINC. All scores averaged over 4 runs with 4 different seeds.
Model
PE
k
#Param
MAE
GatedGCN
None
0
504K
0.251 0,009
GatedGCN
LapPE + RS
505K
0.202 0.006
GatedGCN
SignNet (é(v) only)
8
495K
0.148 = 0.007
GatedGCN
SignNet
495K
0.121 # 0.005
GatedGCN
MAP
486K
0.120 0.002
PNA
None
369K
0.141 0.004
PNA
LapPE RS
8
474K
0.132 + 0.010
PNA
SignNet
476K
0.105 0.007
PNA
MAP
8
462K
0.101 # 0.005
SAN
None
501K
0.181 = 0,004
SAN
MAP
16
230K
0.170 # 0.012
GraphiT
None
501K
0.181 - 0.006
GraphiT
MAP
16
329K
0.160 0.006
Table 4: Results MOLTOX21, All scores are averaged over 4 runs with 4 different seeds.
Model
PE
k
#Param
ROCAUCT
GatedGCN
None
1004K
0.772 0.006
GatedGCN
LapPE + RS
3
1004K
0.774 # 0.007
GatedGCN
MAP
1505K
0.784 0.005
PNA
None
5245K
0.755 0.008
PNA
MAP
16
1951K
0.761 + 0.002
SAN
None
958K
0.744 0.007
SAN
MAP
12
1152K
0.766 + 0.007
GraphiT
None
0
958K
0.743 + 0.003 0.769 0.011
GraphiT
MAP
590K
Table 5: Results on MOLPCBA. All scores are averaged over runs with 4 different seeds.
Model
PE
k
#Param
AP
GatedGCN
None
1008K
0.262 0.001
GatedGCN
LapPE + RS
1009K
0,266 # 0.002
GatedGCN
MAP
2658K
0.268 0.002
PNA
None
6551K
0.279 0.003
PNA
MAP
16
4612K
0.281 0.003
8

---

4.2 Empirical Understandings
Computation time. We demonstrate the efficiency of MAP by measuring the pre-processing time and training time the large OGBG-MOLPCCRA dataset, and compare them with SignNet. For fair comparison, we use identical model size, hyperparameters and random seed and conduct experiments on the same NVIDIA 3090 GPU. The results are shown in Table 6. We observe that model with MAP train 1 faster than its SignNet counterpart, saving 44 hours of training time. Since SignNet takes the form p( (o()) + o(-)) while we use models taking the form p(((u), models with MAP would always train faster than those with SignNet under the same hyperparameters. We also observe that the pre-pre pre-processing time is negligible compared with training time (< 3%), since pre-procsssing only needs to be done once. This makes MAP overall more efficient while achieving the same goal of tackling ambiguities.
Table Comparison of pre-processing and training time between models with MAP or SignNet as PE, on the MOLPCBA dataset. Experiments are run with the same model size and hyperparameters, the same random seed, on the same NVIDIA 3090 GPU.
Model
Pre-processing time
Training Time
Total Time
GatedGCN + MAP
1.70h 0.27 h
63.02 108.51 h
64.72h 108.78 h
GatedGCN + SignNet
Spectral embedding dimension. Next, we study the effects of k. We train GatedGCN with MAP on ZINC with different number of eigenvectors used in the PE and report the results in Table 7. The hyperparameters are the same across these experiments. It can be observed that the performance drops when & is too small, meaning that SE provides crucial structural information to the model. Using larger & has limited influence on the performance, meaning that the model relies more on low-frequency information of spectral embedding.
Table 7: Effects of k. where & is the number of eigenvectors used.
0
16
Test MAE 0.256 + 0.012 0.138 + 0.004 0.120 + 0.002 0.124 = 0.002
Ablation study. Finally, we conduct ablation study of MAP by removing each component of MAP and evaluate the performance. The results are shown in Table 8. Removing sign invariance hurts the performance the most, because most eigenvectors influence on the model's performance. Removing basis invariance also has negative effects since small portion of cigenvalues are multiple. Removing eigenvalues has moderate negative effects, showing that the incorporation of eigenvalue information is beneficial for the network.
single and thus sign ambiguity has the most
Table 8: Effects of the three components of MAP (GatedGCN on ZINC).
PE
full MAP
without can. sign
without can. basis without eigenvalues
Test MAE
0.120 + 0.002
0.131 + 0.003
0.122 + 0.003
0.125 + 0.001
5 Conclusion
In this paper, we we explored a new approach called Laplacian Canonization for addressing sign and basis ambiguities of Laplacian eigenvectors while also preserving permutation invariance and universal expressive power. We developed novel theoretical framework to characterize canonization and the canonizability of eigenvectors. Then we proposed a practical canonization algorithm called Maximal Axis Projection (MAP). Theoretically, it is sign/basis-invarte and universal. Empirically, it canonizes most eigenvectors on synthetic and real-world data while showing promising performance various datasets and GNN architectures.
permutation-eqqivaiinn

---

Acknowledgements
Yisen Wang was supported by National Key R&D Program of China (2022200160304)) National Natural Science Foundation of China (62006153, 62376010, 92370129), Open Research Projects of Zhejiang Lab (No. 2022RC0AB0S), and Beijing Nova Program (20230483344).
References
[1] Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewiez. The Surprising Power of Graph Neural Networks with Random Node Initialization. In IJCAI, 2021.
[2] Rohith Agaram, Shaurya Dewan, Rahul Sajnani, Adrien Poulenard, Madhava Krishna, and Srinath Sridhar. Canonical Fields: Self-Supervised Learning of Cose-Canonicallize Neural Fields. arXiv preprint arXiv:2212.024999 2022.
[3] Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama. Optuna:
A Next-generation Hyperparameter Optimization Framework. In KDD, 2019.
[4] Greg W Anderson, Alice Guionnet, and Ofer Zeitouni. An Introduction to Random Matrices. Cambridge university press, 2010.
[5] Muhammet Balcilar, Renton Guillaume, Pierre Héroux, Benoit Gaüièèe, Sébastien Adam, and Paul Honeine. Analyzing the Expressive Power of Graph Neural Networks in a Spectral Perspective. In ICLR, 2021.
[6] Dominique Beaini, Saro Passaro, Vincent Létourneau, Will Hamilton, Gabriele Corso, and Pietro Liò. Directional Graph Networks. In JCML, 2021.
[7] Mikhail Belkin and Partha Niyogi. Laplacian Eigenmaps for Dimensionality Reduction and Data Representation. Neural Computation, 15(6):1373-3366 2003.
[8] Florent Genaych-Georgee and Raj Rao Nadakuditi. The singular values and vectors of low rank perturbations of large rectangular random matrices. Journal of Multivariate Analysis, 111: 120-135, 2012.
[9] Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M Bronstein, and Haggai Maron. Equivariant Subgraph Aggregation Networks. In ICLR, 2022.
[10] Avrim Blum and Ronald Rivest. Training a 3-Node Neural Network is NP-Complete. In NeurlPS, 1988.
[11] Xavier Bresson and Thomas Laurent. Residual Gated Graph ConvNets. arXiv preprint 17110:/71 2017.
[12] 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
[13] Qi Chen, Yifei Wang, Yisen Wang, Jiansheng Yang, and Zhouchen Lin. Iidimization-nnducce Graph Implicit Nonlinear Diffusion. In ICML, 2022.
[14] Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with GNNs. In NeurIPS, 2019.
[15] Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal Neighbourhood Aggregation for Graph Nets. In NeurIPS, 2020.
[16] Vijay Prakash Dwivedì and Xavier Bresson. A Generalization of Transformer Networks to Graphs. In AAAI Workshop on Deep Learning on Graphs: Methods and Applications, 2021.
[17] Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking Graph Neural Networks. arXiv preprint 2rXivx2003.00982, 2020.
10

---

[18] Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph Neural Networks with Learnable Structural and Positional Representations. ICLR. 2022.
[19] NT Hoang and Takanori Maehara. Frequency Analysis for Graph Convolution Network. In ICLR, 2020.
[20] 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. arXiv preprint wrXiv:2005.00687, 2020.
[21] Yinan Huang, William Lu, Joshua Robinson, Yu Yang, Muhan Zhang, Stefanic Jegelka, and Pan Li. On the Stability of Expressive Positional Encodings for Graph Neural Networks. arXiv preprint arXiv:2310.02579 2023.
[22] John J Irwin, Teague Sterling, Michael M Mysinger, Erin S Bolstad, and Ryan G Coleman. ZINC: A Free Tool Discover Chemistry for Biology. Journal of chemical information and modeling, 52(7): 2012.
[23] Sékou- Kaba, Arnab Kumar Mondal, Yan Zhang, Yoshua Bengio, and Siamak Ravan- bakhsh. Equivariance with Learned Canonicalization Functions. In NeurlPS Workshop on Symmetry and Geometry in Neural Representations, 2022.
[24] Nicolas Keriven and Gabriel Peyré. Universal Invariant and Equivariant Graph Neural Networks.
In NeurlPS. 2019.
[25] Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. In NeurIPS, 2021.
[26] Rongjie Lai and Hongkai Zhao, Multiscale Nonrigid Point Cloud Registration Using Rotation- Invariant innserrease Distance via Laplace-Beltran Beltrami Eigenmap. SIAM Journal Imaging Sciences, 10(2):449-443 2017.
[27] Mingjie Li, Xiaojun Guo, Yifei Wang, Yisen Wang, and Zhouchen Lin. G2CN: Graph Gaussian Convolution Networks with Concentrated Graph Filters. In ICML, 2022.
[28] Pan Li, Yanbang Wang. Hongwei Wang, and Jure Leskovec. Distance Encoding-Desse Provably More Powerful GNNs for Structural Representation Learning. In NeurlPS, 2020.
[29] Derek Lim, Joshua Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and Basis Invariant Networks for Spectral Graph Representation Learning. Learing, In ICLR, 2023.
[30] Andreas Loukas. What Graph Neural Networks Cannot Learn: Depth vs Width. In ICLR, 2020.
[31] Haggai Maron, Heli Ben Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably Powerful Graph Networks. In NeurIPS, 2019.
[32] Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and Equivariant Graph Networks. In /CLR, 2019.
[33] Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the Universality of Invariant Networks. In ICML, 2019.
[34] Grégoire Mialon, Dexiong Chen, Margot Selosse, and Julien Mairal. GraphiT: Encoding Graph Structure in Transformers. arXiv preprint axXiv:2106..5667, 2021.
[35] Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks. In AAAI, 2019.
[36] Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational Pooling for Graph Representations, In ICML, 2019.

---

[37] Sean O' Rourke, Van Vu, and Ke Wang. Eigenvectors of random matrices: A survey. Journal of Combinatorial Theory, Series A, 144:361-42,, 2016.
[38] Sean O' O'Rourke Van Vu, and Ke Wang. Random perturbation of low rank matrices: Improving classical bounds. Linear Algebra and its Applications, 540:26-59, 2018.
[39] Richard S Palais and Chuu-Lian Terg. A General Theory of Canonical Forms. In Transactions of the American Mathematical Sociery, 1987.
[40] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. PyTorch: An Imperative Style, High- Piifo-Performance Deep Learning Library. In NeurIPS, 2019.
[41] Omri Puny, Heli Ben- Ben-Hamu, and Yaron Lipman. Global Attention Improves Graph Networks Generalization. arXiv preprint arXiv:2006. 07846, 2020.
[42] Ladislav Rampášek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for a General, Powerful, Scalable Graph Transformer. In NeurIPS, 2022.
[43] Rahul Sajnani, Adrien Poulenard, Jivitesh Jain, Radhika Dua, Leonidas Guibas, and Srinath Sridhar. ConDor: Self-Supervised Canonicalization of 3D Pose for Partial Shapes. In CVPR, 2022.
[44] Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random Features Strengthen Graph Neural Networks. In SDM, 2021.
[45] Balasubramaniam Srinivasan and Bruno Ribeiro. On the Equivalence between Positional Node Embeddings and Structural Graph Representations, In ICLR, 2020.
[46] Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: A Simple Way to Prevent Neural Networks from Overfitting. The Journal of Machine Learning Research, 15:1929-1958, 2014.
[47] Weiwei Sun, Andrea Tagliasacchi, Boyang Deng, Sara Sabour, Soroosh Yazdani, Geoffrey Hinton, and Kwang Moo Yi. Canonical Capsules: Self-Supervieed Capsules in Canonical Pose. In NeurlPS, 2021.
[48] Edric Tam and David Dunson. Multiscale Graph Comparison via the Embedded Laplacian Discrepancy. arXiv preprint arXi::2201. 2022.
[49] Terence Tao and Van Vu. Random matrices: Universal properties of eigenvectors. Random Matrices: Theory and Applications, 1(01):1150011, 2012.
[50] Terence Tao and Van Vu. Random matrices have simple spectrum. Combinatorica, 2017.
37:t:ttrrriaa.339935555 37:539-553,
[51] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention All You Need. In NeurIPS, 2017.
[52] Haorui Wang, Haoteng Yin, Muhan Zhang, and Pan Li. Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networks. In ICLR, 2022.
[53] Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang. Deep Graph Library: Towards Efficient and Scalable Deep Learning on Graphs. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
[54] Yifei Wang, Yisen Wang, Jiansheng Yang, and Zhouchen Lin. Dissecting the Diffusion Process in Linear Graph Convolutional Networks. In NeurlPS, 2021.
[55] Max Welling and Thomas N Kipf. Semi- Semi-Supervised Classification with Graph Convolutional Networks. In ICLR, 2017.
12

---

[56] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying Graph Convolutional Networks. In ICML, 2019.
[57] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How Powerful are Graph Neural Networks? In ICLR, 2019.
[58] Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie- Yan Liu. Do Transformers Really Perform Badly for Graph Representation? In NeurlPS, 2019.
[59] Jiaxuan You, Rex Ying, and Jure Leskovec. Position-awar Graph Neural Networks. In ICML, 2019.
[60] Jiaxuan You, Jonathan M Gomes-Selman, Rex Ying, and Jure Leskovec. Identity Graph Neural Networks. In AAAI, 2021.
[61] Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J Reddi, and Sanjiv Kumar. Are Transformers universal approximators of pruuence-to-eqqeene functions? In ICLR, 2020.
[62] Seongjun Yun, Minbyul Jeong, Raehyun Kim, Jaewoo Kang, and Hyunwoo J Kim. Graph Transformer Networks. In NeurlPS, 2019.
[63] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander Smola. Deep Sets. In NeurlPS, 2017.
13

---

Appendix
Table of Contents
A Why sign and basis invariance matters
15
B Related work
18
Implementation and verification
C.I Complete pseudo-code of MAP
C.2 Verifying the correctness of Theorem
C.3 Verifying the correctness of Theorem "eae............................
20
23
C.4 Verifying the correctness of Theorem
23
D Synthetic experiment on basis invariance
24
E Other positional encoding methods
25
F Toy Examples
26
F.1 Toy examples for Algorithm
26
F2 Toy examples for Algorithm
27
G Discussions on the assumptions
27
G.1 Discussions on Assumption
27
Discussions on Assumption Assumption
28
H Discussions random graphs
29
I Further weakening the assumptions
32
I.1 Further weakening Assumption 1
32
I.2 Further weakening Assumption 2 and Assumption 3
32
J alternative approach dealing with sign ambiguity
K
Proofs
34
K.1
Proof of Theorem
34
K.2 Proof of Theorem 2
35
K.3 Proof of Corollary 1
35
K.4
Proof of Corollary 2
35
K.5 Proof Theorem
35
K.6 Proof Theorem
36
K.7 Proof of Theorem 5
36
K.8 Proof of Theorem
37
K.9 Proof of Theorem 14
38
K.10 Proof of Theorem 15
39
L Dataset details
40
Hyperparameter settings
40
M. Real-world tasks
40
M.2 Synthetic tasks
42
14

---

A Why sign and basis invariance matters
It is perfectly understandable that one may not see the significance and benefits of sign and basis invariance at once. For instance, below is a quote from one of the reviews of Lim et al. [29] when they first submitted their paper to NeurlPS 2022:
It is not clear "why" to preserve the two symmetries this paper proposes to pre- serve including sign invariance and basis invariance. In graph & molecule setting, two important symmetries are permutation (i.e. if we permute the nodes/atoms, the output stays the same) and rotation (i.e. if we rotate the 3D coordinates associating with each atom, the prediction for a physical property stays the same). I don't 't see a strong evidence that suggests preserving sign & basis invariances on top of permutation & rotation invariances brings any benefits.
Indeed, it is not easy to see why issues related with something matters if they don't even use it. One may overlook the importance of sign and basis invariance for two reasons: (1) people not familiar with Laplacian PE may not even realize sign/basis ambiguity a thing; (2) people that does have some knowledge about Laplacian PE may not realize sign and basis ambiguities are markedly hindering its performance. Nonetheless, Laplacian PE does have advantages over other commonly used PEs that is worth the efforts addressing their drawbacks. For these reasons we feel it is of great significance that we explain the motivation behind preserving sign and basis invariances more details.
Why use spectral embedding: trade-off between universality and ambiguities. Sign and basis ambiguities arise only in spectral embeddings, so the first important question is why to use them. There are many kinds of positional encodings in the literature, such as Random Walk PE (RWPE), Position-await Encoding, Relational Pooling (RP), random features, etc. Without addressing sign and basis ambiguities, some works even reported superior performance of RWPE over spectral embedding [18, 42]. However, these other PEs all have drawbacks either in their expressive power or permutation equivariance. RP and random features are universal, but they do not guarantee permutation equivariance, which is an important inductive bias graph-structured data. RWPE and positional- aware encoding are permutation equivariant, but their expressive power is limited. Thus one may wonder whether there exists a kind of positional encoding method that achieves both. Spectral Embedding, as it turns out, is both permutation equivariant and universal (when coupled with eigenvalue information, see Sec 2). The good thing about SE is that through eigendecomposition, transforms a "harder" permutation equivariance formulated by
f(P AP) = PT f(A)P,
(4)
into a "easier" permutation equivariance formulated by f(PU)= = Pf()),
(5)
where P is an arbitrary permutation matrix, À is the normalized adjacency matrix of the graph and U its eigenvectors. Universality and equivariant results for equation 4 are only known for high-order tensor networks [32]. but similar results for equation 5 have long been known to be achievable even by first-order networks such as DeepSets [63]. Thus SE enables efficient and universal graph neural networks that respects permutation equivariance. However, SE also brings new problems, sign and basis ambiguities. It is not fair to say models with SE are universal without achieving sign and basis invariance, since we expect graph neural networks to respect all symmetries among isomorphic graphs.
Sign and basis invariances are well-established problems in the literature. Sign and basis ambiguities have been recognized by numerous works in the literature to be challenging and important issues when incorporating SE as positional encoding. Below we list some existing discussions in these papers.
Quote from Dwivedi et al. [17]:
We propose an alternative to reduce the sampling space, and therefore the amount of ambiguities to resolved by the network. Laplacian eigenvectors are hybrid positional and structural encodings, as they are invariant by node re- parametrization. However, they are also limited by natural symmetries such as the arbitrary sign of cigenvectors (after being normalized to have unit length). The
15

---

number of possible sign flips is 2", where k is the number of eigenvectors. In practice we choose < n, and therefore 2 is much smaller than n! (the number of possible ordering of the nodes). During the training. the eigenvectors will be uniformly sampled random between the 2 possibilities. If we do not seek to learn the invariance w.r.f all possible sign flips of eigenvectors, then we can remove the sign ambiguity of cigenvectors by taking the absolute value. This choice seriously degrades the expressivity power of the positional features.
Quote from Kreuzer et al. [25]:
As noted earlier, there is sign ambiguity with the eigenvectors. With the sign of being independent of normalization, we are left with a total of 2 possible combination of signs when choosing k eigenvectors of a graph. Previous work has proposed do data augmentation by randomly flipping the sign the eigenvectors [6. 16, 17], and although it can work when & is small, it becomes intractable for large
Quote from Beaini al. [6]:
For instance, pair of eigenvalues can have multiplicity of 2 meaning that they can be generated by different pairs of orthogomal eigenvectors. For an eigenvalue of multiplicity I, there are always two unit norm eigenvectors of opposite sign, which poses problem during the directional aggregation. We can make choice of sign and later take the absolute value. An alternative take sample of orthonormal basis of the eigenspace and use each choice to augment the training.
Quote from Mialon et al. [34]:
Note that eigenvectors of the Laplacian computed on different graphs could not be compared to each other in principle, and are also only defined up =1 factor. While this raises a conceptual issue for using them in an absolute positional encoding scheme, it is shown Dwivedi and Bresson [16]-and confirmed our experiments-that the issue is mitigated by the Fourier interpretation, and that the coordinates used in LapPE are effective in practice for discriminating between nodes in the same way as the position encoding proposed in Vaswani et al. [51] for sequences. Yet, because the eigenvectors are defined up to a =1 factor, the sign of the encodings needs to be randomly flipped during the training of the network.
Quote from Dwivedi and Bresson [16]:
In particular, Dwivedì et al. [17] make the use of available graph structure to pre- compute Laplacian eigenvectors [7] and use them node positional information. Since Laplacian PEs are generalization of the PE used in the original transformers [51] graphs and these better help encode distance-aware information (i.e., nearby nodes have similar positional features and farther nodes have dissimilar positional features), we Laplacian eigenvectors PE in Graph Transformer. Although these eigenvectors have multiplicity occuring due to the arbitrary sign of eigen- vectors, we randomly flip the sign of the eigenvectors during training, following Dwivedi et al. [17].
Quote from Dwivedi et al. [18]:
Another PE candidate for graphs can be Laplacian Eigenvectors [17, 16) as they form meaningful local coordinate system, while preserving the global graph structure. However, there exists sign ambiguity defined up +1, leading 2 number of possible sign values when selecting k eigenvectors which a network needs to learn. Similarly, the eigenvectors may be unstable due eigenvalue multiplicities.
such PE as eigenvectors are
Quote from Lim al. [29]:
16

---

However, there are nontrivial symmetries that should be accounted for when processing eigenvectors. If is a unit-norm eigenvector. then so is u, with the same eigenvalue. More generally, if an eigenvalue has higher mulriplicity, then there are infinitely many unit-norm eigenvectors that can be chosen. Indeed, a full set of orthonormal 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 randomly flip eigenvector signs during training in order to approximately learn sign invariance [25, 17J. 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 are distinct, but higher dimensional basis invariance is even more difficult to deal with, and we show that these higher dimensional eigenspaces are abundant in real datasets.
Quote from Wang al. [52]]
Srinivasan and Ribeiro [45] states that PE using the eigenvectors of the ran- domly permuted graph Laplacian matrix keeps permutation equivariant. Dwivedi et al. [17], Kreuzer et al. [25] argue that such eigenvectors are unique up to their signs and thus propose PE that randomly perturbs the signs of those eigenvectors. Unfortunately, these methods may have risks. They cannot provide permutation equivariant GNNs when the matrix has multiple eigenvalues, which thus are danger- ous when applying to many practical networks. For example, large social networks, when not connected, have multiple 0 eigenvalues; small molecule networks often have non-trivial automorphism that may give multiple eigenvalues. Even if the eigenvalues are distinct, these methods are unstable. We prove that the sensitivity of node representations to the graph perturbation depends on the inverse of the smallest gap between two consecutive eigenvalues, which could be actually large when two eigenvalues are close.
Sign and basis invariances make the learning tasks easier. Permutation invariance is an important inductive bias in graphs in the sense that applying permutations graphs results in isomorphic graphs and they should have the same properties and produce the same outputs. Empirically constraining the network to be invariant such permutations benefits the performance, since otherwise the network has to learn these n! ambiguities by itself. Similarly, sign and basis ambiguities result in 2 and infinite possible choices of positional features respectively that a network has to learn, which could degrade its performance greatly. By preserving sign and basis invariance, a network will not need to learn the equivalence between all these possible choices and the learning task is significantly easier.
There are less ambiguity signs than in permutations. For given graph, there are n! possible ordering of the nodes that all represent the same graph, resulting in n! number of ambiguities. Considering that the vast majority of cigenvectors on real-world data have distinct cigenvalue (Table 9), when selecting & eigenvectors as positional encoding to present structural information, the number of ambiguities is 24, which is much smaller than n!. This transformation from permutation ambiguity sign ambiguity greatly reduces the amount of random noise in the input data and makes the model much more stable.
When sign invariance meets permutation equivariance. Sign ambiguity is not an issue when we do not take permutation symmetry into account. For each eigenvector pair u. we can choose the one whose first non-zero entry is positive. This simple canonization solves the sign ambiguity problem with ease. The problem of sign ambiguity is only non-trivial when combined with permutation equivariance, that is, require the canonization process to be both sign-invane sign-invariant and permutation- cquivariant. Since the eigenvectors can now be permuted arbitrarily, there is no "first" non-zero entry and the simple canonization above fails.
Moreover, such canonization only makes sense when we require it to be universal. For instance, mapping all eigenvectors to jo = (1, 1, 1) is also a sign-invan sign-invariant and permutation-equivarte canonization, but this canonization provides us with no information. Thus one may wonder whether a network can be both sign-invariant, permutation-equivaare nately, as far as we know, no existing work addresses all of them. The universality of SignNet only considers sign invariance, as stated in their theorem:
and universal at the same time. Unfortu-
17

---

Theorem 6 (Universal representation for SignNet). A continuous function f: (S--1)4 - R is sign invariant, i.e. f( $g.Uk f(e...... Uv.) for any S; E {-1,1), if and only if there exists continuous Φ: R -> R2n and continuous p: 122 2)
- RR such that
fur vk) = p((((u)) o 0/ m1))
In fact, being ign-invariint, permutation--equivane well-defined. As mentioned the main text, for an uncanonizable eigenvector u with u = = Pu for some permutation matrix P. let f be an arbitrary continuous sign-invariant, permutation-cquiiariaan and universal function and denote (u) y. The sign invariance property requires that ((-u) y. while the permutation equivariance property requires that ((Pu) Py. Since u Pu, we have Py. However u o Pu, thus universality is not satisfied, leading to a contradiction. This can be illustrated in Figure I, where the three properties cannot be met at the same time.
and universal at the same time is not even
permutation equivariance
SignNet
MAP
MLP
sign invariance
universality
Figure 1:
The dilemma where permutation-qquivarianne, sign-invariance and universal expressive power cannot be achieved at the same time.
Remark. The universality in Definition is defined on eigenvectors U E R=*" The permutation equivariance property of eigenvectors is defined as (PUU = PSUU), and here universality implies that if two eigenvectors are not equal up to permutation, then I should be able to tell them apart. As mentioned above, such set-universal networks (like DeepSets or MLP) cannot be permutation equivariant and sign invariant at the same time. In the context of graphs, we may also care about universality defined on the adjacency matrix A E RTx=, in which case the permutation equivariance (AA) Such graph-univen
property is defined as f(PAP two -oniosomo adjacency matrices apart. We can view f(A) as function of U (we omit the eigenvalues for simplicity), and we denote g (U) = (A), then to achieve the graph universality of f. g does not have be set-universal, thus may not suffer from the dilemma above.
networks are always able to tell
Much effort has been devoted to the structure of invariant and equivariant networks the literature, but few has studied the case when invariance and equivariance combine (in this case you may have to sacrifice some invariance, or some equivariance, or some expressive power). Our work takes step in this direction, providing some insights to this dilemma and characterize the necessary and sufficient conditions where these three properties conflict with each other.
B Related work
Theoretical Expressivity It has been shown that haabbborhooo-gggrggatttt based GNNs not more powerful than the WL test [57, 35]. Since then, many attempts have been made to endow graph neural networks with expressive power beyond the 1-WL test, such as injecting random attributes [36, 44, 59, 45, 17], injecting positional encodings [28, 60), and designing higher-order GNNs [35, 32, 33, 31, 14].
Positional Encodings Recently, there are many works that aim to improve the expressive power of GNNs by positional encoding (PE). Murphy et al. [36] assigned each node an identifier depending on its index. Li et al. [28] proposed to use distances between nodes characterized by powers of the random walk matrix. You et al. [59] proposed to use distances of nodes to sampled anchor set of nodes. Using random node features can also improve the expressiveness of GNNs, even making them universal [44, 1], but it has several defects: (1) loss of permutation invariance, (2) slower convergence, (3) poor generalization on unseen graphs [59, 30]. More detailed discussion can be found in Appendix E.
Laplacian PE Another candidate for graphs is Laplacian Eigenvectors [16, 17] which form meaningful local coordinate system while preserving global structure. However, there exists
18

---

ambiguities in sign and basis that the network needs to learn, which harms the performance of GNNs. To address these ambiguities, many approaches have been proposed such as randomly flip the signs [17], use eigenfunctions over the edges [25] or use invariant network architectures [29].
Sign Invariance Several prior works have proposed ways of addressing sign ambiguity. A popular heuristic is Random Sign (RS), which randomly flips the signs of cigenvectors during training to encourage the insensitivity to different signs [17]. However, the network still has to learn these signs, leading to slower convergence and harder curve fitting task. Bro et al. [12] developed a 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 rotational ambiguities in higher dimensional eigenspaces. Kreuzer et al. [25] proposed to use the relative Laplace embeddings of two nodes. However, their approach suffers from major computational bottleneck with Onn") complexity. Lim et al. [29] proposed SignNet that passes both u and u to the same network, adds the outputs together and then passes them to another network. As both outputs of u and u need to be computed, their approach adds to the training cost. Our approach happens at pre-processing time with (n²*) complexity.
Basis Invariance The only works we know addressing basis ambiguity are Lim et al. [29] and Huang et al. [21]. Lim et al. [29] proposed BasisNet that is basis invariant. However, to achieve universality, the components of BasisNet need to use higher order tensors in H where & can be as large as n( [33]. rendering BasisNet impractical. Huang et al. [21] generalized BasisNet and proposed SPE that is both basis-invariant and stable to perturbation to the Laplacian matrix, but it still suffers from exponential complexity as BasisNet. In this paper, we showed that under certain assumptions, the issue of basis ambiguity can be resolved more efficiently in the pre- prepprocessing stage.
There is also a literature beyond GNN that also considers spectral embeddings of graphs and going around the sign/basis ambiguity problems. Lai and Zhao [26] proposed to address sign/basis ambiguities using optimal transport theory that involves solving non-convex optimization problem, thus it could be less efficient than our approach. Tam and Dunson [48] proposed to symmetrize the embedding using a heuristic measure called ELD that quite similar the form of SignNet, while our MAP algorithm offers an axis projection approach and establish its theoretical guarantees.
Canonical Forms The theory of canonical forms has been widely studied in mathematics [39] and applied to many fields of machine learning. Sajnani et al. [43] proposed a self-super method named ConDor that learns canonicalize the 3D orientation and position for full and partial 3D point clouds. Agaram et al. [2] presented Canonical Field Network (CaFi-Net), a self-supervised method to canonicalize the 3D pose of instances from an object category represented as neural fields, specifically neural radiance fields (NeRFs). Sun et al. [47] proposed an unsupervised capsule architecture for 3D point clouds. Kaba al. [23] proposed decouple the equivariance and prediction components of neural networks by predicting a transformation that can be used to align the input data to some canonical pose. After this alignment the remaining layers do not have to be equivariant anymore. However, as far as we know, no existing work addresses the issue of ambiguities, which arises when some function (e.g.. eigendecomposition) is required to be both equivariant on the input space and invariant on the output space. No existing work addresses the canonizability of input data, which only arises when the invariance and equivariance property conflicts. Instead, we develop a novel theoretical framework that addresses these issues.
C Implementation and verification of MAP
C.1 Complete pseudo-code of MAP
A simplified pseudo-code for sign canonization with MAP is shown in Algorithm 1. A simplified
pseudo-code for basis canonization with MAP is shown in Algorithm 2. (j = 1,, 1, 1) E TR²)
The complete pseudo-code of MAP is shown in Algorithm 3. Despite the sophisticated workflow, programmers do not have to know the principles of our algorithm to use it. The entire module can be passed as a pre_ pre_transt transf frmm orm function to the dataset class with a single line of code.
There are three steps in Algorithm 3. The first is to eliminate sign ambiguity with O(n log n) time complexity. The second is to eliminate basis ambiguity with Onn2dm time complexity, where d is the multiplicity of the eigenvalue and m is the number of multiple eigenvalues of A. The third is
19

---

Algorithm Maximal Axis Projection for eliminating sign ambiguity
Require: Input graph G (V, IE X) Ensure: Spectral embedding of G
Calculate the eigendecompooition À UAUT for each eigenvector u do
D ((n)) complexity O(n" log nz) complexity
Ij Ze,EB, EB, ej + cj, i == l...,,, k
Th < non-orthogonal summary vector with smallest h (equation 1)
, is not <none> then
- u" (choose the direction with u 2n >> as in equation 2)
else
t (no canonization)
end if end for return U
Algorithm 2 Maximal Axis Projection for eliminating basis ambiguity
Require:
Eigenvalue À with multiplicity d > 1 Spectral embedding corresponding to À Calculate the eigenvectors U E Ruxd of À through eigendecomposition
Ensure:
On complexity O( d) complexity
for i 1.2....,d do
I; - Le,eB, Ej + cj
Choose u. E (UI,..., -i-1)+, /1sl = 1, s.I. f(u:) = u, æ. maximized (equation 3)
end for return Un = [1...... Udl
incorporate eigenvalue information with O(n²) time complexity. The overall time complexity is (nn)) with the bottleneck being the eigendecomposition.
The second part of our algorithm (eliminating basis ambiguity) has time complexity O(n dm). We point out that in world datasets m often quite small. As shown Table 9, multiple eigenvalues only make up around % of all eigenvalues, thus in practice the time complexity of the second part (n²d), better than eigendecomposition. (Note it is important to take floating-poin errors into account when counting these multiple eigenvalues)
Table 9: The number of multiple eigenvalues in real-world datasets.
Datesct
ogbg-molesol
ogbg-mnllreesoly
ogbg-molhiv
ogbg-mollipo
ogbg-mollou22
oghg-molooncest
ogbg-molpeha
#nultippe cigenvalues
738
286
52367
5391
8772
10556
191
Hall eigenvalues
13420
4654
952055
104669
129730
141042
10627757
Ratio
5,50 %
6.15%
5.50 %
5,15 %
6.76
7.48%
4.62 %
Some parts of Algorithm 3 have time complexity O(nd)), We also point out that d is usually small real datasets. We show the number of eigenvalues and their multiplicities logarithmic scale in Figure 2.
The details of the datasets listed in Table 10.
C.2 Verifying the correctness of Theorem 3
We verify the correctness of Theorem 3 through random simulation. The program is shown in Algorithm Let U be a random orthonormal matrix, P random permutation matrix and S be random sign matrix (diagonal matrix of and -1). We pass U. PU, US, PUS to the UNiQuESIGN function (Algorithm 1) and compare the outputs. If our algorithm is correct, U and US should have invariant outputs, while U, PU and PUS should have equivariant outputs.
We conduct 1000 trials. The results are P_correel = q_correct = pq_eorvect total = 1000, showing that Algorithm 1 is both permutation-cquivariiie and unique (unambiguous).
20

---

Algorithm 3 Maximal Axis Projection
Require: Graph G (V, E), its normalized adjacency matrix A
Ensure: Maximal Axis Projection of G Calculate the eigendecomposition = UAUT for each single eigenvector _= do
P ((n)) complexity
On log n)) complexity
proj +- (Juu') e1 12l.//l
e2),..., uuu' en.
(()) complexity
len, ind 6- SORT(proj)
O(n log n) complexity
Ien <- UNIQUE(Len)
< len
for i 1.2..... k do
O(n) complexity
2, t- Σ, Eindb]] such that proj ind[s] = len[i]
0; -- 3. + cj
Ug NORMALIZE(uu! xx,)
uu || > E then
floating-pon point errors are considered
substitute with up break
end if end for end for
for each multiple eigenvalue and its eigenvectors U E Ruudd do proj < (IUU Trl. (UU "2l...., (UT en.))
O (n²2m) complexity O(n2d) complexity
len, ind t SORT(proj)
len + UNIQUE((en)
if k < d then
break end if
Assumption 2 not satisfied
for
i
1,2....,d do
O(n) complexity
x; 5 E; iiddsi] such that proj len
2; - 2. + cg
end for
U Uspan t empty matrix of shape n
Uperp + U
b> orthogonal complementary space O(nd*) complexity Ond) complexity
for i = 1,2,...
do
u; +- U perp ae
if Julll < e then
floating-poin errors are considered Assumption 3 not satisfied
break
end if'
u, + NORMALIZE(w.)
substitute U.. with u,
U Uspan U Upsan u.}
Ubase - Uspan
for j = =1,2.... do
O(nd)) complexity
Utemp +- [Ubase Un
if rankk rank (etemp)))))
+ then
O(dd)) complexity
Ubase Utemp end if if U
hass RRaxd then break end if
end for
U Vasse f- GRLNASCCAADDOOTHOOONALZZZTOOOOO base)
O(nd?) complexity
U perp (Ubaso),it1dd
end for
end for
U + UA
D O(n?) complexity
return U
21

---

molcsol
molfrecsolv
molbiv
Ragenabes
10a
10'
10a
10'
10
10
10
mollipo
molloxx1
moltoxcast
10
10
10
10
10
molpcha
sagencibes
10a
10
mulippicity
Figure 2: #Eigenvalues w.s. their multiplicities in real-world datasets (in logarithmic scale).
Table 10: The details of the datasets. Reg: Regression; Bin: Binary classification.
Dataset
ogbg-molesol
ogbg-molreesecl
ogbg-molhiv
ogbg-mollipo
ogbg-moltux21
ogbg- gobg-moltoxcast
ogbg-molppcb
#Graphs
1128
642
41127
4200
7831
8576
437929
Avg #Nodes
13.3
8.7
25.5
27.0
18.6
18.8
26.0
Avg #Edges
#Tasks
1
1
12
617
128
Type
Reg RMSE
Reg RMSE
Metric
RMSE
ROC-AUC
ROC-AUC
ROC-AUC
AP
Algorithm 4 Verify the correctness of Theorem
P_ correct 0, correct 0, pq_corvect 0, total +- for i = 1, 2,..., trials do +- a random positive integer
U + a random orthonormal matrix in Raxx
U, <- UNIQUESIGN(U)
P + random permutation matrix
V <- PU
V. UNIQUESSIGN(V)
p_ correct + P_ Pocoreed + 1 PUU Vol <e
test permutation-eqqiiariinee
S +- random sign matrix (diagonal matrix of and -1)
W +- -US
Wo +- UNIQUESIGN(W)
q_ correct + correct + 1ff Wo <
b test uniqueness
Y < PW
Yo + UNIQUESIGN(Y))
pq_ correct pq_ correct if PU, Yol <E
test both
lotal +- total +1
end for
print out the values p_correct, q_correct, po_correct and total
22

---

C.3 Verifying the correctness of Theorem 5
We verify the correctness of Theorem through random simulation. The program is shown in Algorithm 5. Let U be random orthonormal matrix in Raxd, P be a random permutation matrix and Q be random orthonormal matrix in 1dxd We pass U, PU, UQ. PUQ the UNIQUEBASIS function (Algorithm 2) and compare the outputs. If our algorithm is correct, U and UQ should have invariant outputs, while U, PU and PUQ should have equivariant outputs.
Algorithm 5 Verify the correctness of Theorem 5
p_ correct <- 0, correct +- 0, po_correct + 0, total <- 0
for i = 1, 2,2,... f- a random positíve integer (greater than 1)
trials do
- a random positive integer (less than n)
U <- random orthonormal matrix in Raxd
Uo < UNIQUEBASIS(UU)
P <- random permutation matrix
V < PU
VO UNIQUEBASIS(V)
p_ correct + P_correct + if PU, - Vol <
D test permutation-equiivriaane
Q < a random orthonormal matrix in Rdxd
W + UQ
Wo < UNIQUEBASIS(W)
4_ correct +- correct + 1f Wol <E
> test uniqueness
Y < -PW
Yo UNIQUEBASIS(Y)
p9_correct & pg_correct if PU, Yol <E total total +
D test both
end for print out the values of p_correct, q_correel, po_correcl and lotal
We conduct 1000 trials. The results are p__orrect = __correct = pq_ correct total = 1000, showing that Algorithm both permutation-equivaree raises an assertion error when either Assumption 2 or Assumption 3 is violated, so Algorithm 5 also shows that random orthonormal matrices violate these assumptions with probability 0.
and unique. The function UNIQUEBASIS
C.4 Verifying the correctness of Theorem 1
We conduct experiment on the EXP dataset proposed in Abboud et al. [1], which is designed to explic- itly evaluate the expressive power of GNNs. The dataset consists of set of 1-WI. indistinguishable non-isomorppic graph pairs, and each graph instance is graph encoding of a propositional formula. The classification task determine whether the formula is satisfiable (SAT). Since the graph pairs in the ExP dataset are not distinguishable by 1-WL test, if a model shows above 50% accuracy on this dataset, should have expressive power beyond the 1-WL algorithm.
The models we used on EXP dataset are as follows: an 8-layer GCN, GIN [57]. PPGN [31], 1-2- (DeepSets with Random Node Initialization (RNI) [1]), GCN-RNI (GCN with Random Node Initialization (RNI)), Linear-RSE (linear network with RSE), and DeepSets-RSE. GCN and GIN belongs to the family of MP-GNNs whose expressive power is bounded by 1-WL., and RNI is method to improve the expressive power of MP-GNNs. We verify the expressive power gain of RSE-based models by comparing them with GCN, and evaluate their efficiency by comparing them with other expressive models.
3-GCN-L [35], 3-GCN [1], DeepSets
We evaluate all models on the EXP dataset using 10-fold cross-validation, and train each model for 500 epochs per fold. Mean test accuracy across all folds is measured and reported. The results reported in Table 11. In addition, also measure the learning curves of models to show their convergence rate, as shown in Figure 3.
In Table 11, we observe that vanilla GCN and DeepSets-RNI only achieves 50% accuracy, because they not have expressive power beyond the 1-WI, test. DeepSets-RSF: achieves the best perfor- mance among all models with near 100% accuracy, which demonstrates the expressive power of
23

---

100
Table 11: Accuracy results ExP.
90-
Model
Test Accuracy (%)
Test accurncy (%)
GCN
50.0
GIN
50.0
70-
PPGN
50.0
1-2-3-GCN-L
50.0
GCN-RNI
60
3-GCN
99.7 = 0.0
DeepSets-RSE
DeepSets-RNI
50.0
Linear-RSE
GCN-RNI
97.6 + 2.5
Linear-RSE
99.1 + 1.8
100
200
300
400
DeepSets-RSS RSE
99.8 + 0.5
Epoch
Figure 3: Learning curves on EXP.
RSE-based models is beyond the 1-WL test. Other models, namely Linear- RSE and GCN-RNI, also achieve comparable performance. It's worth mentioning that even a simple linear model (Lincar-RSEl could achieve performance above 99%. This indicates that the universal expressiveness of models with RSE is mostly from RSE itself, rather than the network structure.
From Figure 3, we find that the convergence rate of RSE-based models are much faster than their RNI-based counterpart. This because RSE-based models are deterministic, while RNI-based models are random and require more training epochs to converge. The structures of DeepSets-RSE and Linear-RSE. are simpler, which means they also train much faster than GCN-RNI.
D Synthetic experiment on basis invariance
As mentioned in Appendix B, SignNet [29] only deals with sign ambiguity, while BasisNet [29] has a prohibitive computational overhead. On the other hand, our proposed MAP addresses basis ambiguity efficiently, albeit with the existence of uncanonizable eigenspaces. In this section, conduct synthetic experiment to verify the ability of MAP on addressing basis ambiguity. We graph isomorphic testing, traditional graph task. Our focus is 10 non-isomorppic random weighted graphs belonging to the same eigenspace). We sample 20 instances for each graph, introducing different permutations and basis choices for the initial eigenspace. The dataset is then split into a 9:1 ratio for training and testing, respectively. The task is 10-way classification, where the aim is determine the isomorphism of a given graph to one of the 10 original graphs. The model is given the first eigenvectors input (i.e. k = 3). The results averaged over 4 different runs.
Gin. all exhibiting basis ambiguity issues (with the first three eigenvectors
Table 12: Test accuracy of the synthetic graph isomorphic testing task with DeepSets [63] using different PEs.
Positonal Encoding
Accuracy
LapPE
0.11 0.08
LapPE RS
0.10 0.09
LapPE + SignNet
0.10 0.03
LapPE MAP
0.84 0.21
As evident from the results in Table 12, approaches that address sign ambiguity (like RandSign and SignNet) cannot obtain nontrivial performance on this task. Conversely, MAP shows commend- able performance. The 84% accuracy, although impressive, indicates potential avenues for further enhancement. We believe this synthetic task could also serve valuable benchmark for future studies addressing basis invariance through canonization. Code for this experiment available at https:/ // //gi thub. com Gamm/eorgeMMLPP/ /bsiss-aasssseeee invariance invariance-yyttheiic..

---

E Other positional encoding methods
In this paper, we proposed MAP, which is a kind of positional encodings. In the field of graph representation learning, many other positional encoding methods have also been proposed. Murphy et al. [36] proposed Relational Pooling (RP) that assigns each node with an identifier that depends on the index ordering. They showed that RP-GNN is strictly more expressive than the original WL-GNN. However, to ensure permutation equivalence, we have to account for all possible n! node orderings. which is computationally intractable. You et al. [59] proposed learnable position-awas aware embeddings by computing the distance of a target node to an anchor-set of nodes, and showed that P-GNNs have more expressive power than existing GNNs. However, the expressive power of their model is dependent on the random selection of anchor sets. Sato et al. [44], Abboud et al. [1] proposed to use full or partial random node features and proved that their model has universal expressive power, but has several defects: (1) the loss of permutation invariance, (2) slower convergence, and (3) poor generalization on unseen graphs [59, 30J. Li et al. [28] proposed Distance Encoding (DE) that captures the distance between the node set whose representation is to be learned and each node in the graph. They proved that DE can distinguish node sets embedded in almost all regular graphs where traditional GNNs always fail. However, their approach fails on distance regular graphs, and computation of power matrices can be a limiting factor for their model's scalability. Dwivedi et al. (18) proposed Learnable Structural and Positional Encodings (LSPP)) that decouples structural and positional representations by inserting MPGNNs-L.SPE layers and showed promising performance on three molecular benchmarks.
In particular, we will show that with Random Node Initialization (RNI). (1) A linear network is universal on a fixed graph, and (2) An MLP with just one additional message passing layer can be universal on arbitrary graphs.
In our work, we denote RNI as concatenating a random matrix to the input node features. The random matrix can be sampled from Gaussian distribution, uniform distribution, etc. Without loss of generality, we will assume that each entry of the random matrix is sampled independently from the standard Gaussian distribution NO0, 1).
Definition 2. A GNN with RNI is defined by concatenating a random matrix R. to the input node features, i.e., X' [X, R., where X are the original node features, X' the modified node features and each entry of R. is sampled independently from the standard Gaussian distribution (0, 1). The value of R is sampled at every forward pass of GNN.
To study the effects of RNI on the expressiveness of GNNs, we consider two types of tasks: tasks on fixed graph (e.g., node classification) and tasks arbitrary graphs (e-g. graph elassification). On fixed graph, we aim to learn a function f: IRaxd Raaxd' that transforms the feature of each node 2s to a presentation vector Ze: E R 1xd' We claim that a linear GNN with RNI in the form
R.R =Z
(6)
d' is universal, where W E Rdxd' are the network parameters, and Z E R=xdd is the desired output. In other words, we have the universality theorem of linear GNNs with RNI on a fixed graph:
Theorem 7. On fixed graph G. a linear GNN with RNI defined by Equation 6 is equivariant and can produce any prediction Z E guxd' with probability 1.
We prove Theorem in Appendix K.8.
On arbitrary graphs, the target function is not only dependent on the node features, but on the graph structure A E R"x* as well. Let Ω C Bxd x Rax= be a compact set of graphs with [X, A] E Q where X are the node features and Á is the normalized adjacency matrix. We wish to learn function f: . + IR that transforms each graph to its label. Since is also dependent Á, MLP-based network with X' as input is not expressive enough, and we need additional graph convolutional layers to obtain information about the graph structure. However, Puny al. [41] proved that with just one additional message passing layer, an MLP with RNI can approximate any continuous invariant graph function f.
Theorem 8 (Puny et al. [41]). Given compact set of graphs Ω C Raxd x Raxn, GNN with one message passing layer, an ML. network with RNI can approximate an arbitrary continuous invariant graph function f: Ω + R to an arbitrary precision.
25

---

Theorem 8 is a direct inference of the proof of Proposition in Puny et al. [41], where the authors constructed RGNN that first transfers the graph structural information to the node features through message passing layer, and then approximates / with a DeepSets network, which is an MI.P-based network.
F
Toy Examples
F1
Toy examples for Algorithm 1
u
+
u
hh
2hh e
(+2) T
4
Step 1: (u, e2)
(u, eyy < (u, ex), we let mb 6z
Step 2: (+u) " 2h 0 (-u)² T wh. so we choose + as PE
z
(+u) Ton
Th = ez + Cy
u
+
+
y
Thh
Step 1: (u, e.) {u, ey) < (u, e.), so we let æ, e, Ey Step 2: (+u)" 0 (-u)= Twn. so we choose +u as PE
Figure 4: toy example illustrating our algorithm for eliminating sign ambiguity. Top: The angle between the z-axis and u is the smallest, between both x and y-axes and u are the smallest, so we choose +u to maximize (e, + ey).
choose +u maximize u e.. Bottom: The angle
We give toy examples to help illustrate our MAP-sign algorithm. As shown on the top row of Figure 4, we have = 3 and two possible sign choices for the eigenvector u. Our algorithm first compares the angles (or equivalently, the absolute value of inner product) between u and the standard basis: Cz, ey Cz, and pick the smallest one (the one with the largest absolute inner product), in this eg. Thus let 2t e, and choose the sign that maximize u The In the first example have (+u) Fh > 0 > (-u) Th thus +u is chosen instead of -u. This choice unique and permutaaionneequivaiinn
is possible though, that the angle between u and more than basis vectors are equal. shown on the bottom row of Figure 4, the angle between both ea, ey and are maximum. In this case we let ex + e, be their sum and maximize u." æn, thus +u is chosen. A special case is when a and at, are perpendicular. If this happens, we go on to pick the basis vector with the second largest angle and continue this process.
26

---

01 == C.5
D22 = Cy
V
V
y
22
find u1 E V maximize ufa
find u2 E (u1)+ to maximize uby 222
82
11
122
(u))
Step 1: (V, ex) (V, < (V, let ay 6z₁ D2 Cy
Step 2: find u E V to maximize u Φ
Step 3: find E (ui)
to maximize u x²
Figure 5: A toy example illustrating our algorithm for eliminating basis ambiguity. First, we sort angles between and the standard basis vectors, and set æ == Cxy 22 == Ey. Next, we choose u E V that maximizes u. x1. Finally, we choose u2 E (u1)+ that maximizes u 222 This gives us unique basis u1, of V.
F.2 Toy examples for Algorithm
We give toy example to help illustrate our MAP-basis algorithm. As shown in Figure 5, we have n = 3, d with a two-dimensional eigenspace V. Our algorithm first compares the angles (or equivalently, the length of orthogonal projection) between V and the standard basis: eus Ey, e., and pick the two smallest one (the two with the largest and second largest lengths of orthogonal projection), in this case eg and ey. Thus let I1 Cz. 22 ey. Then we choose u1 V that maximizes u, æı. which is just the orthogonal projection of æı onto V. Finally choose u2 E (u,)) that maximizes u. D2, which is the orthogonal projection of æ2 onto (u,) This gives us a basis u U2 V. This choice is unique and permutation--qqiivaiiai
is possible though, that the angle between V and more than 1 basis vectors are equal. For example, if (V, ez) (V,e,) eg) are both the smallest angles between V and the standard basis, then we let 2 e, ey. The same goes for the second smallest angle, the third smallest angle, and so on.
G Discussions on the assumptions
G.1 Discussions on Assumption
The purpose of Section 3.3.1 is to uniquely determine the signs of the eigenvectors while also preserving their choosing the signs such that the sum of the entries of eigenvectors are positive, or signs such that the element with the greatest absolute value positive, In fact, Lim al. [29] has proposed more general way of choosing signs:
One could easily come up with simple solutions such as
We also consider ablations in which we we... choose a canonical sign for each cigenvector by maximizing the norm of positive entries.
27

---

This "canonical sign" approach did not work well because (I) a large percentage of eigenvectors in real-world datasets have the same norm for positive and negative entries, thus this approach does not actually solve sign ambiguity of these eigenvectors; (2) this approach cannot be generalized to multiple eigenvalues. As reference, we list the number of eigenvectors that "canonical sign" fails in Table 13.
Table 13: The number of eigenvectors with the same norm for positive and negative entries, the total number eigenvectors, and the ratio of eigenvectors that "canonical sign" approach fails in real-world datasets.
Dataset
ughg molesal
ogbg molfreeslly
ogbg mathiv
ogbg mollipo
oghy- mollox11
oghg molloxcast ogbg molppha
#Violation
15115
1536415
#Eigenvectors
14991
5600 38. %
1049163
113568
145459 21.56
161088 21.84
11373137
Ratio
27.08
9.84
13.51
Some examples of such eigenvectors in real-world datasets are as follows.
0. 0000, 0.0000, -0.0000, 0.0000, 0.1364, -9.0965, -0.0965, -0.1575,
0. 0965, -0.0000, 0.1575, -0.0965, -0.2784, 0.2227, -0.1364, -0.0000,
0. 033311, -0.2363, -0.2363, -0.1364, 0.2227, -0.0000, -0.0487,
0.0345,
0345 -0.0877, 0.0620, 0.0620, 0.2784, -0.2227,
0.1364,
0.0000,
-3.3341, 0.2363,
0.2363, 0.1364,
-0.2227],
0000,0 0.0000,
0.0000, -0.0796,
0.0796,
0. 0975
-0.0796, -0.0563,
0. 0000000 0.2087,
-0.3615, 0.2951,
0.0000,
-0. 1815,
0.1815,
0.4767,
-0.4767, -0.0029,
0.0051,
-0.0042,
0.0000,
0458,
0.0458,
0.0416,
-0. 0.0416, 1495,
O. 0.2589, 0.2114,
0.0000, 0. 0975,
0.0975,
-0. 1139,
0. 0139]]
0000,0,
0.0000,
0.0000, -0. 0.0025,
0.0025, 0. 0.3031,
-0.0025, -0.0088
0000, -0.0025,
0.0043, 00.0055,
-0.0000, 098877,
0.0987, 0.0952,
-0. 00.9952 -0.1271,
0.2202, -0.1798, 0.0000, -0.3244,
0.3234,
0434
1436,
0.1313,
-0.2275, 0.1858, 0.0000, 25.2444,
0.2524,
0.4381,
-0.4381]
Assumption 1, on the other hand, is less restrictive. requires that the eigenvectors are not per- pendicular at least of the vectors 2;. For random unit vectors random weighted graphs, Assumption has possibility of being violated. The number eigenvectors violating Assumption in real-world datasets are listed in Table 14. be observed that the ratio of violation tends to become smaller as the graph size becomes larger.
Table 14: The number of eigenvectors violating Assumption 1, the total number of eigenvectors, and the ratio of violation in real-world datasets. We ignore small graphs with more than 5 nodes.
Dataset
ogbg- ogbg-molesol
gubg-melfteesohy
ogbg-molhiv
ogbg-mollipo
ogbg-moltox21
ogbg-moltxxcist
ogbg-molpcha.
#Violation
3328
343088
#Eigenvectors
14551
5048
1049101
113568
144421 3.75%
159987
11372381
Ratio
5.00
7.69
2.82
2.93 %
3.77
3.02 %
G.2 Discussions on Assumption 2 and Assumption 3
Assumption 2 requires that the projections of ,1, En on V have at least d distinct lengths, while Assumption 3 requires that each is not perpendicular to (ui,.... ---1)-- which is subspace of V. We illustrate two examples of these assumptions being violated when n = 3 and d 2 in Figure 6. In the left figure, the projections of e1, e2, e3 V all have the same lengths, thus = < d, violating Assumption complementary space of span(u;, (u,) in V. violating Assumption 3. We observe that the eigenspace V needs to obey certain kinds of symmetries in order to violate either assumptions. For random orthonormal matrices and random weighted graphs, these assumptions have possibility of being violated; and in real-world datasets, the ratio of violation tends to become smaller as the graph size becomes larger.
In the right figure, 22 is perpendicular to the orthogonal
The number of multiple eigenvalues violating these assumptions in real-world datasets are listed in Table 15. Indeed there is still around 20 % of violation large datasets, but since multiple
28

---

22
E1
u1
Figure 6: Examples of Assumption and Assumption being violated when n = 3 and =
Left: the projections of e1, e2, E3 of the same length, thus k = 1 < d, violating Assumption 2.
Right: T2 perpendicular to the orthogonal complementary space of span(u1) in V, violating Assumption 3.
cigenvalues only make up a small portion all eigenvalues (Table 9), the ratio of violation is relatively small and has negligible influence the model performance.
Table 15:
The number of eigenvalues violating Assumption Assumption in real-world datasets. Ry: the number of eigenvalues violating Assumption 2. n2: the number of eigenvalues not violating Assumption 2 but violating Assumption 3. Ni: the total number of multiple eigenvalues. pı: the ratio of multiple eigenvalues violating Assumption 2. P2: the ratio of multiple eigenvalues violating Assumption N2: the total number of eigenvalues. P3: the ratio of all eigenvalues violating Assumption 2. P1: the ratio of all cigenvalues violating Assumption 3. We ignore small graphs with no more than 5 nodes.
Dataset
ogbg-molesol
ogbg-mellircesolv
ogbg-molhiv
ogbg-mollipo
ogbg-moltox21
ogbg-moltoxcast
ogbg-molpeba
39
30
5315
440
646
873
30844
R2
126
45
6329
599
1073
1450
61318
N1
738
286
52367
5391
8772
10556
491247
5.28 %
10.49 %
10.15 %
8.16 %
7.36 %
8.27
6.28 %
Pj
17.07 %
15.73
12.09
11.11 %
12.23 %
13.74%
12.48
N₂
13420
4654
952055
104669
129730
141042
10627757
Fa
0.64
0,56 %
0.42
0.62
0.94 S
0.97 %
0.66 %
0.57 %
0.83
1.03 %
0,58 Si
H Discussions on random graphs
In this section summarize some existing results random graphs and more generally random trices. These discussions help us to have better understanding of how eigenvalues and eigenvectors of random graphs distribute, and the probability that they uncanonizable by our MAP algorithm. Due to the theoretical complexity, we do make some simplifications in our discussions.
We first give some basic definitions about random matrices and random graphs.
Definition 3 (Wigner matrix). Let E.C F.C. be real random variables with mean zero. We say W is a Wigner matrix of size n with atom variables E, if W (wi))f is a random real symmetric n x n matrix that satisfies the following conditions.
(independence) {wig: isisisn 3)
collection of independent random variables.
(off- coff-diagonal entries) {wo: Siiis n) is a collection of independent and identically distributed (iid) copies E.
(diagonal entries) {wo: 1 15 < n is a collection of iid copies C.
If & and Ç have the same distribution, say W is Wigner matrix with atom variable We always assume that Ş is non-degenerate, namely that there no value c such that P(E =.
Definition 4 (symmetric Bernoulli matrix), Let O p and take & to be the random variable
p.
with probability p.
p.
with probability p.
29

---

Then & has zero mean. Let Bn (p) denote the nt X n Wigner matrix with atom variable &. We refer to B, (p) as a symmetriic Bernoulli matrix (with parameter p).
Definition (sub-exponential), random variable & is called sub-exponential with exponent a > if there exists a constant B > 0 such that
P(K 1) Bexp(-1 for all l. 1>0. 0.
Definition (Erdōs-Rényi random graph). Let G(n, denote the Erdös-Réwv Kénéi random graph on n. vertices with edge density p. That is, G(n. p) is simple graph on vertices such that each edge {i.j} is in ((n.)) with probability p. independent of other edges.
Let (p) be the zero-one adjacency matrix of G(n,p). An(p) not a Wigner matrix since its entries do not have mean zero. Let C(n. p) denote the Erdös- Réndi random graph with loops on n vertices with edge density Let An (p) denote the zero-one adjacency matrix Gn, p). Technically, A, (p) is not Wigner random matrix because its entries do not have mean zero. However, we can view A, (p) low rank deterministic perturbation of Wigner matrix. That is, can write A, (p)
(p) pJn, + Bn)p),
where Jn the all-ones matrix.
Simplification in our discussions. The adjacency matrix of Erdös-Rén Rényi random graphs can be viewed as a rank-one perturbation of zero-mean symmetric random matrix, which has effect on the distribution of eigenvalues in the limit n + oo [8]. In the finite case, the difference between eigenvalues and eigenvectors of the perturbed and unperturbed random matrices can be bounded as well, as stated in the following theorems.
Theorem 9 Ro'Ror et al. [38]. Let E be an n. X n Bernoulli random matrix, and let A be be singular values of A, v1, U2,--... : n) be corresponding singular vectors of A, o 2 .... o minnm,
an X n matrix with rank r. Let σn 02 2 2... mi.
0 be
singular values of A + E, "q.....,min((m.. be corresponding singular vectors of A + E. For
every >> O there exists constants Co. do > 0 (depending only on E) such that if 5 > 8o and T1 2 max(n, vn8), then, with probability at least 1 E,
sin (11, v1) CVT
Theorem 10 (O Rourke et al. [38]). Let E be an n x n Bernoulli random matrix, and let A be an matrix with rank satisfying os 2 n. For every 8 >> O, there exists constant Co (depending only on e) such that, with probability at leas! 1 -
C1-55d So CVF.
In particular, when the rank r is significantly smaller than n, the bounds in the above theorems are significantly better. Thus the rank-one perturbation has little or no effect on the spectral distribution of the adjacency matrix. In the following discussions will ignore the rank-one perturbation and assume that the adjacency matrix of random graphs have zero mean.
We will study two cases: (1) the adjacency matrix of the random graph is continuously distributed (random weighted graph); (2) the adjacency matrix of the random graph discretely distributed (random unweighted graph).
It is easy see that for a Wigner matrix with atom variables &, Ç. if the distribution of & is continuous, then with probability it has simple spectrum (i.e., all eigenvalues have multiplicity one), thus no basis ambiguity exists. For its single eigenvectors, we also expect these eigenvectors to be continuously distributed on the unit sphere, thus the probability that they are uncanonizable is equal 1. In fact, we can even give a explicit formula for the distribution of some simple random matrices, as follows.
Definition 7 (GOE). The Gaussian orthogonal ensemble (GOE) is defined Wigner random matrix with atom variables &, where is a standard normal random variable and Ç a normal random variable with mean and variance 2.
30

---

Theorem 11 (Anderson et al. [4], Section 2.5.1). Let M be a X real symmetric matrix drawn from the GOE, with eigenvalues À1 S... S Xn and corresponding eigenvectors V1..... : Then the eigenvectors U1,..., Un are uniformly distributed on
5m-1 ( In) E S" 5--1: :1 00];
(F1,...,,
and the eigenvalues A1..... An have joint density
Pa Pa(A Pa(A An) = 2n Ihsissa PA - IT e At/4 if I...... Au
0,
otherwise,
where Zn is normalization constant.
Thus the eigenvectors of such Gaussian random matrices are uniformly distributed on the unit sphere, meaning they are canonizable with probability 1.
The discrete case is trickier, because when is finite, the probability that the eigenvectors uncanonizable no longer O. We wish that this probability can be upper bounded and asymptotically converges to zero. The first fact is that for large class of random matrices, perturbed or not, they have simple spectrum with probability o(1.
Theorem 12 (Tao and Vu [50]). Consider real symmetric random matrices M,, = (Eij)
where the entries Eig for j are jointly independent with Eyi = Eúj, the upper-triangular entries Exj. i < have non-trivial distribution E for some fixed p. 0 such that IP = x) S for all x E R. The diagonal entries Çüs S i S n can have an arbitrary real distribution (and can be correlated with each other), but are required to be independent of the upper diagonal entries Sij, 1 S < S n. Then for every fixed
0 and n sufficiently large (depending on A, p), the spectrum of Ma is simple with probability at least A
Thus with probability - (1) no basis ambiguity exists.
For sign ambiguity, we expect that the probability that the single eigenvectors are canonizable asymptotically converges 1 as
R" the all-one vector, j = (7. V...... ) Rn the normalized all-one vector. One obvious fact is that for an eigenvector u E IR", if it is non-canonizable, then u u.j O. Thus it suffices to show that the probability of the inner product between and being zero converges derived from the following theorem.
co. Denote (1,
- This can be
Theorem 13 (Tao and Vu [49]). Let &,C be random variables such that
E and & are sub-exponential random variables,
EE() EE() = E{E3)= =
EE(?) 1, = 3, E(c2) = 2,
and assume & is a symmetric random variable. For each n 2 1, let Wn be an n X n Wigner matrix with atom variables E. Let {an} be sequence of unit vectors with a, Snn1 such that lim [a,lee = O, and let (in) be a sequence of indices with in E [n]. Then
Vovs, (Wa) On + N(,1)
in distribution as co.
Thus in the limit as oo, by taking a, j. we have the inner product between the eigenvector and j following a normal distribution. The probability that they have zero inner product is 0, indicating these eigenvectors almost always canonizable.
Related readings. We refer the readers to Anderson al. [4] for a introduction random matrices, Benaych-Georges and Nadakuditi [8] for survey about the singular values and vectors of low rank perturbations of large random matrices, O'Rourke et al. [37] for comprehensive survey about eigenvectors of random matrices.
31

---

I Further weakening the assumptions
L1 Further weakening Assumption
In Section 3.2, we mentioned that some cigenvectors are intrinsically uncanonizable, meaning that impossible to canonize them based on themselves. However, in graph-level tasks, the input is whole graph with n eigenvectors, not single eigenvector. When the input graph is permuted by a permutation all the eigenvectors also permuted in the same way. This raises the question of whether we can canonize one eigenvector based on other eigenvectors in the same graph.
Thus we propose to further weaken Assumption in the following steps. For given input graph, we first divide its eigenvectors into two sets: Si, containing uncanonizable eigenvectors; and S2. containing all canonizable eigenvectors. Suppose [S|] d1, |S2] = d2, where di + d2 Define the matrix of canonizable eigenvectors
Ucan [.1,.... Udzl where UI...... Und are all the eigenvectors in S2.
We fist canonize all the eigenvectors in S2, using our MAP-sign algorithm. This gives us a matrix of canonized eigenvectors U E R2 Using a hash function, we can compress the matrix U into a vector Ucan that preserves all the information of S2:
Ucan R", where (Neam);
( ".
Then we can define the summary vectors I; of uean in the same way as in Section 3.3, and use them to canonize the cigenvectors in Sj. Denote the projection matrix P Uean U and the projected angles 0g 1eyl, I i S n. Assume that there are k distinct values {a;, according to which descending order the distinct angles). Each B; represents an equivalent class axis that Uean has the same projection on. Then we define summary vector æ; of Ucan for the axes in each group B; as their total sum 2; Ee,en, Ej + C, where c is tunable constant.
1....,,) n). divide all basis vectors {e;} into k disjoint groups B, (arranged in
For each u E S1, we can try to canonize it using the MAP-sign algorithm as in Section 3.3.1, with the summary vectors of replaced by the summary vectors of Wcan- We find the first non-orthongonal summary vector with u, denoted by Th, and choose the sign that maximizes u. T zt.- In this way, we are able canonize some eigenvectors in S1 that are originally uncanonizable, thus further weakening Assumption 1. The complete workflow is shown in Algorithm 6.
Algorithm 6 A stronger algorithm for eliminating sign ambiguity
Require: Input graph G (V, E, X)
Ensure: Spectral embedding of G
Calculate the eigendecomposition À T
S the of all uncanonizable eigenvectors of
S2 + the set of all canonizable eigenvectors of G Canonize all eigenvectors in S2, using Algorithm
U can + .u.,..., "igh where ui,.... Udd are all the canonized eigenvectors, d2 = |S21
Ucan + (hashi can TT a; + Peil,,siss
P +- Ucan U
+ the number of distinct values in fa,)
Divide all basis vectors {e,} into & disjoint groups B, according to the values of {as}
Φ; Ee,eB, e, + cj. i,...k.... lk...,k
for each eigenvector u E do
34 f- non-orthogonal summary vector with smallest / if u 34
end for
return the canonized eigenvectors
I.2 Further weakening Assumption and Assumption 3
When reading Algorithm 2, some may find it not as strong as Algorithm 1. In Algorithm 1, we search over the summary vectors 2; one by one, until we find summary vector 26 that is not
32

---

orthogonal to u. However, in Algorithm 2, we just assumed that is not orthogonal to V, 22 is not orthogonal (u1) 33 is not orthogonal to (u, u2) etc. We did not search for non-orthogonal summary vectors; we just assumed that they are. This observation is more obvious when we look at the special case of Algorithm when d = In this case, Assumption Assumption 3 requires that # is not orthogonal to ut which is stricter than Assumption 1 in our MAP-sign algorithm. This raises the question of whether we can strengthen Algorithm 2 such that is as powerful Algorithm I when taking d 1.
always satisfied, and
This can be achieved by searching for non-orthogonal summary vectors at each step just as in Algorithm 1. Suppose we have obtained the summary vectors æ,, i = 1..... k. First we search (a;} for the first summary vector of that is not orthogonal to V, and choose in V that maximizes uf=, at- Next search {a:;} for the first summary vector æ that is not orthogonal choose U2 E (u1)+ that maximizes u2 22.. Then we search { for the first summary vector æ3 that is not orthogonal to (u,, u2)-, and choose U3 E (ui, u2) that maximizes ug æzj. and so on. The complete workflow is shown in Algorithm
(un)+, and
Algorithm 7 A stronger algorithm for eliminating basis ambiguity
Require: Eigenvalue À with multiplicity d >
Ensure:
Spectral embedding corresponding to X
Calculate the eigenvectors U E Roxd of X through eigendecomposition
P < UUT
A +- the number of distinct values in {a,)
Divide all basis vectors {e: into i disjoint groups B, according to the values of {as}
2; 4- Le,eB, Ej + cj. .k
for i 1,2,...,dl do xº- f- the first summary vector in {æ:) not perpendicular to (ui,..., 1 Choose u, E (ui,...,, u,-1) |usl = s.t. f(u:)) = u. x; is maximized
end for return Un = U1...... ual
In order for Algorithm 7 to succeed, we require that such non-orthogonal summary vector 2; exists at each step, which is less restrictive than Assumption and Assumption 3. Thus we obtain a stronger algorithm for eliminating basis ambiguity.
J An alternative approach to dealing with sign ambiguity
In our design for algorithms that eliminate sign ambiguity, we find one type of eigenvectors especially difficult to deal with. That is, uncanonizable eigenvectors u E IR" such that there exists a permutation matrix P E R= satisfying u - Puu. This means that u and -u only differ by permutation. Since they are uncanonizable by Corollary 1, none of the solutions mentioned in Appendix G.I can handle such eigenvectors. However, depending cause umbiguities at all. For example, consider the DeepSets- like architecture p(Σ (u))), where ó is coimutatioo-invariann Then since u and u only differ by a permutation, they produce the same output when fed to a permutation-invarree delay the handling of uncanonizable eigenvectors to the training stage, though it may result in loss of expressive power.
the model architecture, such eigenvectors may not
network, thus no ambiguities exist. This shows we can
On the other hand, for eigenvectors that are canonizable, we already know that Algorithm canonizes them. Here we give an equivalent algorithm for removing sign ambiguity, shown Algorithm 8.
Theorem 14. Algorithm 8 uniquely decides the signs of canonizable eigenvectors and is permutation- equivariant.
Theorem 14 is proved in Appendix K.9.
Algorithm 8 is well-motivated and better to understand than Algorithm in some sense. Consider naïve canonization of where we choose the sign such that u has positive sum. This canonization algorithm is quite simple, but it cannot canonize all canonizable eigenvectors, such as the ones with
33

---

Algorithm 8 An alternative approach to dealing with sign ambiguity
Require: Input graph G (V, IE X) Ensure: Spectral embedding of G
Calculate the eigendecomposition Á UAUT for each eigenvector u E IR" do
f the smallest positive odd integer such that Ei=1 uf #0 Substitute u with -u E u < end for return U
sum. What Algorithm does is go to look at the of the 3rd power of and, if it is non-zero, choose the sign such that it is positive. If unfortunately it zero, we go on to look at the It can be proved that there must exists positive odd integer h I such that the sum of the h-th power of u is non-zero. Thus Algorithm 8 terminates within 2++1 steps, successfully canonizing all canonizable eigenvectors.
sum of the 5th power and
2
Algorithm 8 offers an alternative approach to dealing with sign ambiguity in addition to Algorithm 1, though it cannot generalize to the basis ambiguity case. The time complexity of Algorithm 8 is On log n).
K
Proofs
K.1 Proof of Theorem
We first prove that U is a real-valued matrix.
Lemma 1. Suppose Å is the normalized adjacency matrix of a graph G, and Á = UAUT is its spectral decomposition. Then, UA Raxx.
Proof. Let A = diag(A) (). It suffices to show that X; 2 0 for i 1,2......
Let (V, where V is the vertex set and E is the edge For node i, denote the degree of node i by d,. For any x E R", we have
x Ax = x (I Å)æ
Σ +
Σ
20
Σ
E
2 0,
Vdid,
d
SEV
(K.))
thus the Rayleigh quotient of Á is bounded by Aæ 0. The Rayleigh quotient gives the lower bound of eigenvalues of Å, therefore we have A; 2 0, and this completes the proof.
Then we give the proof Theorem
Proof. We can rewrite f such that is continuous set invariant function on the set consisting of the rows of its input:
((X,AA) f([ f(XX (Xx,))))(((X())))X)))))" =FX,
Using the permutation invariance property of verify that F is set invariant by observing:
F(APX) ( (PUA))(UAA)))TT
=[PXX PAP f([x F F((
Thus universal network on sets approximate F to arbitrary precision.
34

---

K.2
Proof of Theorem 2
Proof. On the one hand, if f(hz) = gz) holds for some h H and g G. then we have A(f()) by the invariance property of A. However, since A is a mapping and f(hx) gf(x), there must be ((f())) (x) and thus A(f(z)) = hf(f(z)). Now we have x & hæ and A(f(x)) = hA(f(x)), contradicting the universality property of A.
((J(kr)) (x)) by the equivariance property of A and ((g
On the other hand, if there does not exist h E H and E G such that x + hæ and f(hx) (z), we can construct canonization of follows. First arbitrarily choose yo such that f(x) yo- and let A()
yo- For any h H such that I * hæ, by the equivariance of f we know that f(xx) = heyo. thus we let A(x()z) yo * hyjo thus the universality property of A holds. A is also invariant, since (()))) is uniquely determined; and equivariant, since (fxr) = huo (f))) for any h. We can repeat this process for all equivalence classes in X' and obtain invariant, equivariant and universal canonization
hyo. Since f(hr) + gf for any g. we know that
for all inputs.
K.3 Proof of Corollary
Proof. Under sign ambiguity, we have H S, and G = (+1,-11), 11. By Theorem 2, u is canonizable
and only if there does not exist a permutation a such that u * (u) and u = = (w)) This is equivalent to say that there does not exist a permutation matrix P E _2=x such that u Pu. O
K.4 Proof of Corollary 2
Proof. Under basis ambiguity, we have H S, and = O(d). By Theorem 2, U is canonizable if and only if there does not exist a permutation and an orthonormal matrix Q E O(d) such that U + (U) and U a Q.)Q. This is equivalent to say that there does not exist a permutation matrix PE TR such that U + PU and U and PU span the same d-dimensional subspace V C IR". Note here we used a lemma from Lim al. [29]: for any orthonormal bases V and W of the same subspace, there exists orthogonal Q ((d) such that VQ W.
K.S Proof of Theorem 3
Without loss of generality, not, we can simply rearrange e; to make them sorted and proceed in the same way):
Proof.
always assume that the angles {ay} are sorted (if they
Pei = =... |Pe,, Pen, +i =... Pen tmzl
Pen, +
Pen
where k is the number of distinct lengths of Pe; E n4 Here divide e, into k groups according to the angles between them and the eigenspace, with each group sharing the same |Pe.| Define (1, 1, ..,, 1) R then æ; can be expressed
xC = en, + +n + + enj-..tn, + cj. isisk.
The sign of ug is selected based on the sign of u sn(4 0), which is sign-equivariant. No matter what the sign of is, we will always choose the one that maximizes u." æn, thus un is sign-invariant.
Suppose the entries of the input eigenvector u permutated by a E Sa, where Sn the permutation group of order n. Then we have n² Mo(() (1 sist
S n) and
l =..l=..-- =/o'/ er(nz)) lu'u' co(m1+t) ... lu'u'' co(mi+na) > > u'uuT
+1y1 -... |u'uu' co(nttt.na))
thus (x/)x (z)))(t), i.e., the vectors 21 sis k) are permutation-cquivarianl as in Section 3.3.1 (the number h is permutation-invant
Let æ/ be defined
because each uu xr is permutation- invariant). The sign of ung is determined by the sign of the dot product of u and 2/, both of which permutation--quuvarian This indicates that the sign of u" 2%,, (and thus the sign of un) is
35

---

invariant (i.e,, unique). Since ug u' or un = -u', un is permutation-equivanee as well.
there exists a permutation a (acting on entries of u) such that u & (u) ) but they have the same canonical form, then either (u) or (u)). The former is impossible since already assumed they are not equal, and the latter violates Assumption 1, leading to contradiction. Thus the canonization of is universal.
K.6 Proof of Theorem
Proof.
Without loss of generality, always assume that the angles {a;} are sorted (if they not, we can simply rearrange e; to make them sorted and proceed in the same way):
Pei = ...... Pen,, Pen =... Pen >
Pea t
where k is the number of distinct lengths of Pe; Σ n4 n== Here we divide e, into k groups according to the angles between them and the eigenspace, with each group sharing the same |Pel Define (1, 1, ............ 1) E R", then æ; can be expressed
a; enz + tn
Cnyy tny + cj. isisk.
Notice that Pe; |uu" T eil Us lu), thus
Jun
Unn
Uny
+ tm -
|n 4..
Suppose u violates Assumption
1. Then for any 1 S < k, we have
+ + t +.. = 0.
tay +ny The above equations show that (1) the absolute value of the entries of ū, are all equal; (2) the sum of the entries of ú, is O. Thus for any entry of ü, either is 0 or its positive and negative value appears in pairs. conclusion, +ú, and - -ú are equal up to permutation for all thus +u and -u equal up to permutation. By Theorem it is not canonizable.
Let ú == (Wan+-.-t
On the other hand, suppose satisfies Assumption 1. Then there exists S S h such that
Uny Fng 1+1 + tnit + 0.
Let új = (u too 1 In Uny +n) TT_ ü, contains all entries of u with absolute value t-. Since the sum of ú is non-zero, the numbers of positive and negative entries in ū, are different. No matter how permute Thus + and - u are not equal up to any permutation. By Theorem 1, it is canonizable.
and uu, their corresponding entries in ü, will not align.
K.7 Proof of Theorem 5
We first point out that the orthogonal projector = UU is invariant to the choice of basis.
Lemma 2. Let = [ui,..., ua] E Raxd and V = [u,,..., va] Raxd be two sets of orthonor- mal vectors that span the same d-dimensional subspace V IR". Then UUT =VV.
Proof. We have U = VTV = by the definition of U and V. Let U VQ where Q is an invertible matrix, then
UUT UUUTU)-'
= =VQIQ'V
= -vo0--11nn-1))000VVV-
36

---

Lemma 2 shows that Pe; (and thus 2;) is invariant to the choice of basis in V. If we permute CI...... en by a E Sn, then the sorted sequence of Pe; is also permuted by a. Thus the elements of each a; is permuted by as well. This shows the choice of æ; is permutation-equiivvree
Then we prove Theorrm 5.
Proof. Without loss of generality, can always assume that the angles {az} are sorted (if they are not, we can simply rearrange e; to make them sorted and proceed in the same way):
Pei = Pee, Pen
ten >
> Pear +me-++1 =.... Pen
where k is the number of distinct lengths of Pe, E ny = n. Here we divide into k groups according the angles between them and the eigenspace, with each group sharing the same |Pe Define = (1, 1, ...,,,,,,, E I"", then I; can be expressed as
2; En tm
En +m - cj, isis k.
We have already shown the existence of the maximum value of f(u). To show that insis-invariance of Uo. it suffices to show the uniqueness of the maximum point of f(u). Thus no matter what basis of U is, Algorithm always yields the same output.
Notice that f--u)= = -f f()), thus either the maximum value of f(u) is positive, or f(u) = u x = However, f(u) implies that æ; is perpendicular to (u1...., u violating Assumption Thus conclude the maximum value of f(u) is positive.
Suppose there exists w' * u² such that f(u') f(u") takes maximum value. Consider the vector anx + azu" where a V 2[1+ wh) 1/2 Obviously, au' + arl" (ui,..., 11-1)+, Jonu + oou"l |I 1, and (au' ((ou'+au")) 20u2 T n, > u' uTT,, the choice of is unique.
my This leads to a contradiction. Therefore,
The permutation-cquivaiinie
of Algorithm 2 can be proved by observing that each step of Algo- rithm 2 is cettuuatttoonqqvvaiirnea Since each æ; is permutation-cquivariin its eigenprojection on the subspace V (and thus Un) is also eermutation-equvaarinnn
there exists a permutation a (acting on rows of U) such that U * oU) but they have the same canonical form, then U and a (U) spans the same subspace. On the one hand, U (UU) means that at least one of the eigenvectors permuuation-equivariant but unchanged after a, they all r-invariant. This leads to contradiction, since it impossible to have a non-o-invariant eigenvector in a --invariant eigenspace.
U not o-invariant, On the other hand, since all uı, Un are
K.8 Proof of Theorem
We first prove the following lemmas.
Lemma 3. Let R R
n be random matrix, and each entry of R is sampled independently from the standard Gaussian distribution N (0, 1). Then with probability 1, R has full rank.
Proof. We denote the first column of R by R. It linearly independent because R. = with probability 1. Then we view R., as fixed, and consider the second column R.2. The probability that R. falls into the span of R.,1 O, thus with probability 1, R., and R. are linearly independent.
Generally, let us consider the k-th column R. The first k - columns of R. forms a subspace in T whose Lebesgue measure is O. Thus R.,. falls into this subspace with probability 0. By inference, have all the columns of R are linearly independent with probability 1, i.e., P (raank(R) = =n) = 1. O
Lemma 4. Let A E Raxn, B E I2xxm be two matrices. Then the equation AX- = B has solution iff. rank(A) rank[[A, Bl).
Proof. First prove the necessity. Suppose AX BB has solution. Then,
1 A,
A X B.
37

---

where i denotes the i-th column of matrix M. This means each column of B can be expressed as linear combination the columns of A, and therefore each column of [A, B] can be expressed as linear combination of the columns of A.
On the other hand, it is obvious that each column of A can be expressed as linear combination of the columns of [A, B). Thus we have rank( () rank([A, BJ).
Then we prove the sufficiency. Since rank(A) expressed as a linear combination columns [A, BB. we have the columns of and the columns of A, B) equivalent. Therefore, each column of B be expressed a linear combination of columns of A, i.e., Ax B has a solution for = 1, .,...;". m. Thus the equation AX = has solution.
rank([A, BJ), and each column of A can be
Then we give the proof of Theorem 7.
Proof. For any prediction Z E Raxd", wish to prove that with probability there exists parameters of linear GNN with RNI W E Baxd such that
X X = Z.
(7)
By Lemma 4, the necessary and sufficient condition that Equation 7 has a solution W is rank([X, RJ) rank([X, R, Z)).
By Lemma 3, with probability rank(R) n, therefore rank([X, RJ) rank([X R. Z]) n.
Thus, in conclusion, with probability there exists parameters of linear GNN with RNI W Raxd such that the GNN produces Z.
We can also prove linear GNNs' equivariance by observing that for any permutation matrix P Rax"
[X = P[X,R]W PZ,
where we used PR = R. because each entry of PR is also sampled from the standard Gaussian matrix (0, 1).
K.9 Proof Theorem
The following lemmas are used in our proof.
Lemma 5 (Newton's 's Identities). Let 2 32, ........00 In be variables, denote for k 2 1 by Ps the k-th
power sum:
P =
x
for 2 denote by e the elementary symmetric polynomial. Then we have
Pk (-1) kee Σ (-1)* 1-1)
for all n 2 1 and n 2 1.
Lemma (Vieta's Formulas). Let f(x) an R + (nn-x2"-1 1- + ... taæ an be a polynomial of
degree n, eg be the elementary symmetric polynomial. Then we have
On-1
an-2
En = (-1)n ag
E1
E2
On
On
We first show that h exists.
Lemma 7. Let u R... Assume that there does not exists a permutation matrix E Raxa such that - Pu. Then there exists positive odd integer h S such that Σn= u * 0.
38

---

Proof. Suppose the opposite holds, i.e., P: = 0 for all odd 1 Lis S where P; is the i-th power sum of entries of u. Let u1 U2..... Un be the roots of the polynomial f(x) a, + On 12- 12
... or + ag.
If is even, by Lemma
0 Pi e1
0 = P3 = ei P2 e2p1 + 3e3,
0 = P3 e, P4 c2p3 + c3p PI 5e0,
:
0 = Pn-1 = c1P C2 PpPa-3 +... (n 1)en-1.
which gives us 61 6g ..... = 6n-1 0. Then, by Lemma 6, we have ap-1 Qn-3
a1 O. This indicates that f(x) = g for some polynomial g(r). Similarly, if is odd, by Lemma 5,
0 = Pi 61
0 P3 61 e2p 3e3,
0 == P3 = e1P1 e2P3 + tep2 - PI + 5e5.
0 = Pa = 6, - -
....4 nen:
which gives us 61 = 6g 6g
en
Then, by Lemma 6, we have an-1 = 0gg
This indicates that f(x) xg(x²) for some polynomial g(z). Either way, all n roots of f(z) are symmetric with respect to the y-axis. Then there must exist a permutation matrix such that u Pu. leading to contradiction. Thus Lemma 7 holds.
Then we prove Theorem 14.
Proof. By Lemma 7, we have shown the existence of h. Since flipping the sign of u also flips the sign of >i=1 uf outputs either u uu, it is also permutation-qquiiariaan.
(because h is odd), Algorithm 8 uniquely decides the sign u. Since the algorithm
K.10 Proof of Theorem 15
We prove that under mild conditions, the loss of expressive power induced by truncating RSE can be upper bounded, as shown in the following theorem.
Theorem 15. Let Ω C. Raxd x R be compact set of graphs, [X E Q. Let NN be universal neural network on sets. Given an invariant graph function I defined over fi that can be e-approximated by an Lipisccchttz continuous function and arbitrary E > 0, for any integer 0 < k E n, there exist parameters of NN such that for all graphs [X, A E
|[[X A]) NN([X, (UA+).
< Vn - -LLAA- +
Here the Li--schctitz continuity of is defined using the Frobenius norm the input domain, 0 \1 5 S An < are the eigenvalues of Á. (n--k)))
We can see from Theorem 15 that the upper bound of the loss of expressive power decreases when increases, and when &o the network becomes universal. We give its proof follows.
By Lemma 1, we know that X; 2 0 for 1,2..... n. Next we prove that X; Lemma 8. Suppose Å is the normalized adjacency matrix of a graph 9, and A <... < An are its eigenvalues. Then Xa 2, for = 1,2.....
Proof. In the proof of Lemma 1, we proved x: (I+ AAxx 2 0. Similarly, we have
x. (I - A)Ø= Σ
20 0.
Vd,
ddz
(K))E
39

---

Thus,
====-- = A) 2x x 5 2x To x.
This shows that the Rayleigh quotient is bounded by "² An Then we give the proof of Theorem 15.
x I therefore X $ 2.
Proof. Let 0 S \1 S S An S 2 be the eigenvalues of and u..... un be the corresponding eigenvectors. Then
À ) + An 2n
We also define
À' == An Un k k+1 + + X Un
By Theorem I and the assumptions in theorem, we know that there exists permutation-invariaat network on sets such that
F(X, (U*+). 0)) NN(( -U 0))
E
2
Since f can be approximated by an 1 -pplcipcciizz continuous function, we have
[[(x, A) F[[X, (U ) ko; 0)) = |[[x, A) - f((x, A1)
- |p| A XX, A ||| + 2
= Lpl X 21 + + An- k un
u n
= -.p/A \> + ... 22 + 8
2
S - k-n--Lpp----
Combining the two inequalities above gives us
[s((X - NN([N, (UA)( 0)) <vn kLp
L
Dataset details
ZINC (MIT License) consists of 12K molecular graphs from the ZINC database of commercially
available chemical compounds. These molecular graphs between 9 and 37 nodes large. Each node represents a heavy atom (28 possible atom types) and each edge represents bond (3 possible types). The task is regress constrained solubility (logP) of the molecule. The dataset comes with predefined 10K/1K/IK train/validation/eest split.
OGBG-MOLTOX21 and OGBG-MOLPCBA (MIT License) are molecular property prediction datasets adopted by OGB from MoleculeNet. These datasets use a common node (atom) and edge (bond) featurization that represent chemophysical properties. OGBG-MMLTTOX1 is multi-mask binary graph classification dataset where a qualitative (active/inactive) binary label is predicted against 12 different toxicity measurements for each molecular graph. OGBG-MOLPCB. is also a multi-task binary graph classification dataset from OGB where an active/inactive binary label is predicted for 128 bioassays.
Details of the three datasets are summarized in Table 16.
M Hyperparameter settings
M.1 Real-world tasks
We evaluate the proposed MAP on three real-world datasets: ZINC. OGBG-MOLTOX2! and OGBG- MOLPCBA, on server with 6 NVIDIA 3080 Ti GPUs and 2 NVIDIA 1080 Ti GPUs. We consider
40

---

Table 16:
Details of the datasets.
Dataset
ZINC
ogbg-moltose moltox21
egbg-molpehe
#Graphs
12000
7831
437929
Avg #Nodes
23.2
18.6
26.0
Avg #Edges
24.9
19.3
28.1
Task Type Metric
Regression MAE
Binary Classification Binary Classification ROC-AUC
AP
4 GNN architectures: GatedGCN, PNA, SAN and Graphi'T, with 4 different positional encodings: PE, LapPE with random Sign, SignNet and MAP. We follow the same settings as Dwivedi et al. [18] for models with PE or LapPE, and same settings
Lim al. [29] for models with SignNet or MAP. All baseline scores reported in Table 3, 4 & 5 are taken from the original papers. As shown in Figure for models with no PE LapPE, the input features are directly fed into the base model; for models with SignNet, the eigenvectors are first processed by SignNet and then concatenated with the original node features as input the base model; for models with MAP, the PEs are first processed by normal GNN and then concatenated with the original node features as input to the base model. These settings align with the original papers.
X or [
base model
Y no PE/LapPE
p(o(u) + 66 ó(-)))
base model
Y
SignNet
x
UA
p(δ(u))
base model
Y
MAP
X
Figure 7: Our experiment settings with different PEs.
The main hyperparameterss in our experiments are listed as follows.
k: the number of eigenvectors used in the PE.
L1 the number of layers of the base model.
hj: the hidden dimension of the base model.
b2: the output dimension of the base model.
A: the initial learning rate.
t: the patience of the learning rate schedular.
the factor of the learning rate schedular.
Amin' the minimum learning rate of the learning rate schedular.
Lz the number of layers of SignNet the normal GNN (when using MAP PR).
h3: the hidden dimension of SignNet or the normal GNN (when using MAP as PE),
The values of these hyperparameters in experiments are listed in Table 17.
41

---

Table 17: Hyperparameter details for experiments on real-wordd datasets.
Model
PE
k
L1
h1
h2
A
t
Amin
h3
GatedGCN
None
0
16
78
78
0.001
25
0.5
le-6
GatedGCN
LapPE RS
8
16
78
78
0.001
25
0.5
lc-6
GatedGCN
SignNet
8
16
67
67
0.001
25
0.5
le-6
67
GatedGCN
MAP
8
16
69
67
0.001
25
0.5
le-5
6
69
PNA
None
0
16
70
70
0.001
25
0.5
1c-6
ZINC
PNA
LapPE RS
8
16
80
80
0.001
25
0.5
le-6
PNA
SignNct
8
16
70
70
0.001
25
0.5
lc-6
8
70
PNA
MAP
8
16
70
70
0.001
25
0.5
le-6
6
70
SAN
None
0
10
64
64
0.0003
25
0.5
1c-6
SAN
MAP
16
40
40
0.0007
25
0.5
le-5
GraphiT
None
0
10
64
64
0,0003
25
0.5
1c-6
GraphiT
MAP
16
10
48
48
0.0007
25
0.5
le-6
48
GatedGCN
None
0
8
154
154
0.001
25
0.5
le-5
GatedGCN
LapPE- RS
3
8
154
154
0.001
25
0.5
1e-5
MOLTOX21
GatedGCN
MAP
3
8
150
0.001
22
0.14
5e-6
PNA
None
0
8
206
206
0.0005
10
0.8
2e-5
PNA
MAP
16
8
115
113
0.0005
10
0.8
8c-5
7
115
SAN
None
0
10
88
88
0.0007
25
0.5
le-6
SAN
MAP
12
10
88
88
0.0007
25
0.5
lc-5
8
88
GraphiT
None
0
10
88
88
0.0007
25
0.5
le-6
GraphiT
MAP
16
10
64
64
0.0007
25
0.5
1e-6
64
MOLPCBA
GatedGCN
None
0
8
154
154
0.001
25
0.5
lc-4
GatedGCN
LapPE RS
3
8
154
154
0..01
25
0.5
le-4
GatedGCN
MAP
3
8
200
200
0.001
25
0.5
1e-5
8
200
PNA
None
0
4
510
510
0.0005
4
0.8
2e-5
PNA
MAP
16
4
304
304
0.0005
10
0.8
2e-5
304
M.2 Synthetic tasks
To verify the expressive power of RSE, we conduct experiments on the synthetic ExP dataset. The dataset consists of a set of 1-WL indistinguishable non-isomorphic graph pairs. If a network reaches above 50 % accuracy on this dataset, must have expressive power beyond the 1-WL test. DeepSets- RSE is two-layer DeepSets model with RSE PE, whereas Linear-RSE is one-layer linear model with RSE as PE. We use Optuna [3] to optimize the hyperparameters of our models. The values of hyperparameters of models
follows:
DeepSets-RSED the learning rate = 0.0023556029412333366 the hidden dimension of the first linear layer wi 60, the hidden dimension of the second linear layer w2 76, the dropout rate [46] = 0. 7.133925777035525184, the weight decay of Adam optimizer
wd 0.0005.
Linear-RSE: the learning À 0.00066077365669787745 the hidden dimension 109, the weight decay of Adam optimizer wd = 0.0001.
42


Reviews:
[{"review_id": "pqriuAMCPE", "reviewer": "Reviewer_pkjp", "summary": "This paper explores the Laplacian canonization approach to address the sign and basis ambiguities of eigenvectors. Previous sign- and basis-invariant methods suffer from high complexity and the proposed canonization method is light-weighted and can be used for any graph neural networks. Since the Laplacian canonization algorithm only runs in the pre-processing stage, it significantly reduces the forward and backward overhead of the neural networks. Experimental results on various graph classification datasets validate the effectiveness and efficiency of the proposed method.", "questions": "See weakness.", "limitations": "This paper discusses the limitation of the proposed algorithm that not all eigenvectors can be canonized and shows that this situation does not have a potential impact on the model.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed canonization method is effective and efficient. Existing sign- and basis-invariant models suffer from high complexity. And this paper addresses this issue by proposing a new pre-processing algorithm, which not only reduces the training computation costs but also makes the model suitable for any graph neural network.\n\n2. This paper gives a theoretical framework for Laplacian canonization and detailly discusses the conditions for canonizing the sign and basis invariance of eigenvectors, which I think is important for this community. Based on the theoretical results, this paper proposes an efficient canonization algorithm that can heuristically determine the signs of eigenvectors.\n\n3. This paper is well-written and easy to follow.", "weaknesses": "In the experiment, this paper tests the performance of different positional encoding methods with the same base model. To ensure fairness, the authors should ensure that different methods have similar model parameters. For example, in the PCBA dataset, the model parameters of GatedGCN-MAP are 2.5 times that of the GatedGCN-LapPE but the performance improvement is negligible. Besides, it is confusing that the parameters of PNA-None and GraphiT-None are fewer than PNA-MAP and GraphiT-MAP. Why removing the positional encoding will increase the number of parameters?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer pkjp for appreciating our method and theoretical results. We address your concerns on parameter sizes.\n\n---\n\n**Q1**. To ensure fairness, the authors should ensure that different methods have similar model parameters.\n\n**A1**. In our experiments, we allow a flexible choice of model architectures (layers, hidden dimensions) to achieve the best performance.  This setting is consistent with prior works, specifically [1] and [2]. Following your suggestion, we further ensure the same model size for baseline methods. As shown below, the results are consistent with the original ones as our MAP still outperforms LapPE+RS.\n\n*New Results on MOLPCBA under similar model size.*\n\n| Model | PE | $k$ | #Param | AP |\n| --- | --- | --- | --- | --- |\n| GatedGCN | None | 0 | 2641K | 0.265 ± 0.003 |\n| GatedGCN | LapPE + RS | 3 | 2642K | 0.266 ± 0.002 |\n| GatedGCN | MAP | 3 | 2658K | **0.268 ± 0.002** |\n\n---\n\n**Q2**. Why the parameters of PNA-None and GraphiT-None are fewer than PNA-MAP and GraphiT-MAP? Why removing the positional encoding will increase the number of parameters?\n\n**A2**. We note that removing PE alone does not increase the number of parameters on a fixed model, but decreases it a bit with smaller input size. Similar to **A1**, we also allow a flexible choice of model size to achieve the best performance, which may choose an even smaller model than the baseline. In these cases, MAP-based models can outperform baselines with even fewer parameters, showing their effectiveness. Here, we further rerun MAP with roughly the same model size as the baseline methods (PNA/GraphiT) on MOLTOX21. It can be seen that MAP-based models still consistently outperform their baselines.\n\n*New Results on MOLTOX21 under similar model size.*\n\n| Model | PE | $k$ | #Param | ROCAUC |\n| --- | --- | --- | --- | --- |\n| PNA | None | 0 | 5245K | 0.755 ± 0.008 |\n| PNA | MAP | 16 | 4716K | **0.758 ± 0.003** |\n| GraphiT | None | 0 | 958K | 0.743 ± 0.003 |\n| GraphiT | MAP | 16 | 916K | **0.755 ± 0.005** |\n\n**References:**\n\n[1] Dwivedi, V. P., Luu, A. T., Laurent, T., Bengio, Y., & Bresson, X. (2021). Graph neural networks with learnable structural and positional representations. *arXiv preprint arXiv:2110.07875*.\n\n[2] Lim, D., Robinson, J., Zhao, L., Smidt, T., Sra, S., Maron, H., & Jegelka, S. (2022). Sign and basis invariant networks for spectral graph representation learning. *arXiv preprint arXiv:2202.13013*.\n\n---\n\nHope our explanations and new experiments above could address your concerns. Please let us know if there is more to clarify."}, {"review_id": "tKt9rbZEQH", "reviewer": "Reviewer_zwuu", "summary": "The authors propose Laplacian canonization, a way to select canonical Laplacian embeddings that resolve the sign and basis ambiguities often present in graph embeddings. The proposed method is a preprocessing step that is relatively fast. The authors perform experiments to evaluate the performance of Laplacian canonization. ", "questions": "- See above section ", "limitations": "- See above section on weakness. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- Originality: Laplacian canonization is an original idea. To the best of my knowledge, this is a novel contribution. \n\n- Quality: I see this paper as mainly making a methodological contribution. As such, the quality of the experiments are sufficiently extensive to be convincing, and the arguments/theoretical derivations are sound, to the best of my knowledge. \n\n- Clarity: The presentation of the paper and the motivations are clear.  \n\n- Significance: It is certainly very relevant and important to study graph embeddings for GNNs these days. The approach is novel and works well. It is significant enough to warrant publication at a venue like NeurIPS. ", "weaknesses": "- One potential weakness is the theoretical portion of the paper, whose results are rather marginal and unsurprising. However, I see this as a methods paper, and the empirical good performance of the proposed method more than makes up for it. \n\n- One potential limitation of this approach is that not all eigenvectors can be canonized (even though in the datasets 90% of them can be). The authors seem to regard the 90% canonizable rate as a good feature of their approach, rather than a shortcoming. This is a fair perspective. But to provide a more balanced discussion, I would like to see the authors discuss more on this potential limitation, especially since 1. other methods for resolving ambiguities do not suffer from this issue and 2. it is unclear to me whether it is possible that the non-canonizable eigenvectors share any common patterns/structures in real datasets that might bias the results. \n\n- There is a literature (beyond GNN) that also considers spectral embeddings of graphs and going around the basis/sign ambiguity problems. For example, in point cloud registration, Lai and Zhao's \"Multiscale Nonrigid Point Cloud Registration Using Rotation-Invariant Sliced-Wasserstein Distance via Laplace-Beltrami Eigenmap. SIAM J. Imaging Sci. 10(2): 449-483 (2017)\", and in graph comparison Tam and Dunson's  \"Multiscale graph comparison via the embedded laplacian distance. arXiv preprint arXiv:2201.12064 (2022).\" I suggest incorporating these references and others to round out the prior work section in the appendix. \n\n\n- Typos: \n\nline 347: practical", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer zwuu for appreciating the originality and effectiveness of the proposed canonization method. We address your concerns as follows.\n\n---\n\n**Q1**. One potential weakness is the theoretical portion of the paper, whose results are rather marginal and unsurprising. However, I see this as a methods paper, and the empirical good performance of the proposed method more than makes up for it.\n\n**A1**. Thank you for appreciating the good performance of our method. However, we are a bit confused about your comments on the theory part as “marginal and unsurprising”. As far as we could see, our theoretical results establish the theoretical formulation and prove some important properties for Laplacian canonization, making it a theoretically rigorous approach for resolving the ambiguities. ****Reviewer pkjp comments that this theoretical formulation is “important for this community”****. Here, we highlight some ***new and valuable results that have not been observed by prior works***:\n\n1. We constructed a theoretical framework for canonical forms with differnet invariances and equivariances. **Prior works only consider canonical forms with one kind of invariance or equivariance, and do not face the issue of uncanonizability**, thus their theories do not apply to the sign/basis ambiguity of Laplacian eigenvectors.\n2. Using this theoretical framework, we found that universality, permutation equivariance, and sign/basis invariance cannot be achieved at the same time (last point in Appendix A). **Past works on sign/basis ambiguity do not propose this observation**, and SignNet actually tries to propose a “universal” sign-invariant network. However, as we discussed in Appendix A, their “universality” does not take permutation equivariance into account, and it’s impossible to be universal when you do.\n3. We gave the necessary and sufficient condition of uncanonizability and showed their ratio on real datasets. **Previously we knew that sign/basis ambiguity is harmful for LapPE, but didn’t know the extent, and we were not aware why LapPE still underperforms RWPE even after removing sign ambiguity in some experiments [1].** The characterization of these uncanonizable eigenvectors can help us better understand the harm brought by sign/basis ambiguities.\n\nHope the explanations above could ease your concerns. If there are more specific questions on the theory part, and we are happy to address them in the discussion stage.\n\n**References:**\n\n[1] Rampášek et al. (2022). Recipe for a general, powerful, scalable graph transformer. *NeurIPS*.\n\n---\n\n**Q2**. I would like to see the authors discuss more on this potential limitation, especially since 1. other methods for resolving ambiguities do not suffer from this issue and 2. it is unclear to me whether it is possible that the non-canonizable eigenvectors share any common patterns/structures in real datasets that might bias the results.\n\n**A2**. Thanks for your suggestions. We highlight that as elaborated in **A1**, three desirable properties of GNNs, universality (U), permutation equivariance (P), and sign invariance (S) **cannot be achieved at the same time**. So when preserving permutation equivariance, there is **a fundamental tradeoff between universality (expressive power) and sign invariance**. Accordingly, the fact that other methods attain both P and S (like SignNet) cannot attain universal expressive power. Instead, our methods attain universality and permutation invariance, while preserving S as much as possible by Laplacian Canonization.\n\nAs for the common patterns of these non-canonizable eigenvectors, **Corollary 1** suggests that they are highly symmetric (having identical positive and negative parts up to a permutation). Intuitively these non-canonizable eigenvectors would appear more often in graphs that are more symmetric (e.g. having high-order automorphisms), and predictions of these graphs might be more negatively affected. Of course it still requires more rigorous research as to how structural symmetries are related with non-canonizable eigenvectors and how they might bias the results.\n\n---\n\n**Q3**. There is a literature (beyond GNN) that also considers spectral embeddings of graphs and going around the basis/sign ambiguity problems. For example, in point cloud registration, [1] Lai and Zhao’s “Multiscale Nonrigid Point Cloud Registration Using Rotation-Invariant Sliced-Wasserstein Distance via Laplace-Beltrami Eigenmap. *SIAM J. Imaging Sci. 10(2)*: 449-483 (2017)” and in graph comparison [2] Tam and Dunson’s “Multiscale graph comparison via the embedded laplacian distance. *arXiv preprint arXiv:2201.12064* (2022).”\n\n**A3**. Thanks for your suggestion, and we will incorporate these works in the related works. Both papers proposed ways to address the sign/basis ambiguity issue of Laplacian eigenvectors. The paper [1] proposed to address sign/basis ambiguities using optimal transport theory that involves solving a non-convex optimization problem, thus it could be less efficient than our approach. The paper [2] proposed to symmetrize the embedding using a heuristic measure called ELD that is quite similar to the form of SignNet, while our MAP algorithm offers an axis projection approach and establish its theoretical guarantees.\n\n---\n\nHope our elaborations above could address your concerns. Please let us know if there is more to clarify."}, {"review_id": "KRPJ1r0Dlw", "reviewer": "Reviewer_NB7V", "summary": "The recently emerging graph transformers uses the spectral embedding. \nThe spectral embedding has two empirically known problems; I) sign invariance ii) basis invariance.  \nThe existing remedy for these problem comes at the cost.\nThis paper addresses this problem by the method this paper proposes called Laplacian Canonization (LC).\nThis paper provide the theoretical analyses of LC.\nAlso, the experimental results show that the LC outperforms the existing methods.", "questions": "Regarding Table 2.\nFrom the intuition, the basis invariance is quite rare, while the sign invariance always happens, since the basis invariance needs the \"shared eigenvalues.\"\nBut looking at the table 2, sign non-canonized is less than basis invariance. \nThus, how do you justify the definition of the canonization? Or basis invariance matters more?\nAlso, if the basis invariance is more frequent than sign invariance, how do you defend the little improvement from SignNet?\n\n\n\nBasis invariance vs. sign invariance. \nAs I raise the weakness section, the LC improves the accuracy of the SignNet only marginally. But seeing the Table 2, the there are more basis invariance. \nIs this an indirect evidence that the LC does not deal with sign not quite well? Or basis invaraince actually does not matter?\n\nIt will be interesting if the authors conduct the experiments using the \"separate\" MAP regarding basis and sign.\n\nThus, I believe that at least one of the following is happening\n\ni) some non-intuitional thing is happening in Table 2 regarding the number of noncanonization of sign v basis. \n\nii) Even if the number of non canonization of the basis, basis does not matter\n\niii) The proposed method deal with the sign case less well than SignNet.\n\nAs I wrote in this section, I am not clear the point how much the sign and basis matters, and how MAP addresses each invariance, and therefore I'm giving 4.\n\n---\nPOST REBUTTAL: Given the synthetic data experiment regarding basis, I slightly increase my score from 4 to 5. \n\n\nAlso, the discussion above on Table 2 contains my misunderstanding. Please see the discussion below for the details.", "limitations": "The whole community does not know why the sign and basis invariance hamper the performance of PE as I raised in the weakness section, as far as I understand. This study is built on these studies. But although I read the Appendix A where the authors summarize the point of basis and invariance ambiguity, I'm less confident on this point.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The simplicity of the proposed algorithm. \n\n- Theoretical guarantee of the canonoization for the MAP algorithm.", "weaknesses": "- We do not know **why** the sign and basis invariance hinder the performance of PE.\nThus, I kind of feel little anxious that the readers cannot judge if the work on top of the series of these studies is in the right direction or not to address the fundamental problems. See also the limitation section.\n\n- Seeing the experiment, there is a little improvement from SignNet even though the LC deals with not only sign but also the basis invariance. \nWhy some method is not conducted with sign net? The basis invariance does not matter? Or The LC show the weaker accuracy performance regarding sign ambiguity than SignNet?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer NB7V for appreciating the simplicity and theoretical guarantees of our approach. We address your main concerns below, especially those on the meaning of studying sign and basis invariance.\n\n---\n\n**Q1**. We do not know **why** the sign and basis invariance hinder the performance of PE.\n\n**A1**. Indeed this is a good question. First, it is a well-known principle (and practice) that we need to obey the symmetry properties of graphs when designing GNNs. For example, graph convolution and aggregation operators preserve the permutation invariance property of graphs. Similarly, **sign and basis invariance is also an intrinsic symmetry property of the graph data (the graph structure is invariant under different sign/basis choices of eigenvectors),** so similarly, we also need to preserve this symmetry when designing GNNs. As noted by Reviewer R8b6, *“designing proper architectures that preserve symmetries and are more expressive is an important and open topic currently in GNN literature.”* As also mentioned by Reviewer zwuu, sign/basis ambiguities are important problems not only in the GNN community, but in other fields as well. \n\n| Model | Method for Sign/Basis Invariance | MAE on ZINC |\n| --- | --- | --- |\n| GatedGCN + LapPE | None | 0.319 ± 0.010 |\n|  | RandomSign (RS) | 0.202 ± 0.006 |\n|  | SignNet ($\\phi(v)$ only) | 0.148 ± 0.007 |\n|  | SignNet | 0.121 ± 0.005 |\n|  | MAP (ours) | 0.120 ± 0.002 |\n\n**Reasons.** Intuitively, GNNs without symmetries can waste a lot of model capacity on fitting exponentially many permutation/sign/basis ambiguities of the same graph, while GNNs obeying symmetries do not need to. Concretely, the benefits of this principle can be justified in two folds: \n\n- **Empirically**, as shown in the table above (quoted from Table 3), **encouraging sign/basis invariance by RS, SignNet, and our MAP can all bring significant improvements on real-world datasets**.\n- **Theoretically**, a recent paper [1] rigorously shows that we can **gain sample complexity by obeying data symmetry**. The upper bound of the generalization error in Theorem 3.1 [1] contains a term $\\mathop{\\mathrm{vol}}(M/G)$, the volume of the quotient space that is invariant to group $G$ on the manifold $M$. As the group size $G$ grows (more symmetries), we observe a decreasing generalization error (or equivalently, reduced sample size to attain the same error).\n\nThus, sign/basis ambiguity is not only a well-established problem, but also solving it brings concrete benefits empirically and theoretically. We will add these discussions in the revision.\n\n**References:**\n\n[1] Tahmasebi, B., & Jegelka, S. (2023). The Exact Sample Complexity Gain from Invariances for Kernel Regression on Manifolds. *ICML 2023 Workshop on Topology, Algebra, and Geometry in Machine Learning (TAG-ML)*.\n\n---\n\n**Q2**. Why some method is not conducted with sign net? The basis invariance does not matter? Or The LC show the weaker accuracy performance regarding sign ambiguity than SignNet?\n\n**A2**. Here, for a fair comparison, we compare with reported scores from the original papers of LapPE and SignNet. In the SignNet paper and their official code, for graph tasks, **they only provide results on ZINC,** as we included in Table 3. We also find that directly porting their code to other datasets leads to much worse performance and requires costly tuning. To be more complete, here we reproduce a delicately tuned SignNet result on MOLTOX21, and we can see that MAP still outperforms SignNet.\n\n| Model | PE | $k$ | #Param | ROCAUC |\n| --- | --- | --- | --- | --- |\n| GatedGCN | None | 0 | 1004K | 0.772 ± 0.006 |\n| GatedGCN | SignNet | 3 | 1754K | 0.782 ± 0.004 |\n| GatedGCN | MAP | 3 | 1505K | **0.784 ± 0.005** |\n| PNA | None | 0 | 5245K | 0.755 ± 0.008 |\n| PNA | SignNet | 16 | 1367K | 0.745 ± 0.008 |\n| PNA | MAP | 16 | 1951K | **0.761 ± 0.002** |\n\n---\n\n**Q3**. From the intuition, the basis invariance is quite rare, while the sign invariance always happens, since the basis invariance needs the \"shared eigenvalues.” Seeing the Table 2, there are more basis invariance than sign invariance.  [Several questions are further raised based on this observation.]\n\n**A3**. We are afraid there are some misunderstandings of the Table 2 here. As you noted, there are indeed much fewer basis ambiguities (only around **5-6%**, see **Table 9**) than sign ambiguities (**100%**) in all eigenvectors. Clearly, **sign ambiguity is indeed more frequent and more important than basis ambiguity.** Table 2 lists the proportion of MAP-uncanonizable eigenvectors (i.e., **all the other can be canonized by MAP**), e.g., 2.5% for sign and 1.6% for basis on ZINC. Thus, **our MAP algorithm can successfully resolve ~97.5% sign ambiguities and ~3.4% basis ambiguities** (70% within basis itself) among all eigenvectors. So MAP indeed did better at solving sign ambiguity, which also contributes most to its improvements (see **Table 8**)**.** We will explain this relationship more clearly to avoid possible confusion in the revision.\n\nWe believe that this clarification could also help address your sequential concerns on the importance of sign and basis invariance. Please let us know if there is more to clarify. \n\n---\n\n**Q4**. It will be interesting if the authors conduct the experiments using the “separate” MAP regarding basis and sign.\n\n**A4**. We note that in **Table 8**, we have included an ablation study on the MAP-sign and MAP-basis methods. We can see that while both methods contribute to the final performance, removing MAP-sign hurts the performance more than removing MAP-basis, which also confirms our explanations above.\n\n---\n\nHope our elaboration on the meaning of the problem, and our clarification on the quantities in Table 2 could address your concerns. We are very happy to take your further questions."}, {"review_id": "kbn6rDzx1w", "reviewer": "Reviewer_ZUZt", "summary": "This paper introduces a new approach called Laplacian Canonization (LC) for ensuring the sign and basis invariance of spectral embeddings. This is done by determining the canonical direction of eigenvectors in the pre-processing stage. They propose to perform the Laplacian Canonization via Maximal Axis Projection (MAP) algorithm that is guaranteed to canonize all sign canonizable features. Experiments are performed on  molecular benchmarks. ", "questions": "Besides the questions, listed in the weaknesses section, I have a few more minor questions:\n- In the axis projection step, why do you need c?\n- I suppose that in practice alpha_i will not be exactly the same. Do you then consider all values or do you apply some binning algorithm to get B_i? I also wonder what is k in practice?\n- in Tables 4 and 5, why is it that MAP increases the number of parameters?\n", "limitations": "I have no limitations to point out and the code is provided in the supplementary material.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper is well written, contains clear rigorous definitions and is easy to follow. \n- Experiments show consistent improvements.\n", "weaknesses": "With my limited knowledge of the topic, I could not point out any obvious weaknesses of the method. I do have two questions regarding the guarantees of the method: \n- The authors claim that the method can canonize more than 90% of all eigenvectors, however, this has only been tested on molecular graphs. Are there any guarantees for other graphs?\n- You observe that your assumptions are violated for some small percentage of eigenvectors on real-world datasets. I was wondering if these eigenvectors are evenly spread out over the eigenvalue spectrum or could it be the case that these are all for the lowest eigenvalues? This could be problematic since these are the eigenvectors one would like to use.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer for appreciating our paper. We address your questions in the following points.\n\n---\n\n**Q1**. The authors claim that the method can canonize more than 90% of all eigenvectors, however, this has only been tested on molecular graphs. Are there any guarantees for other graphs?\n\n**A1**. Following your suggestions, we also evaluate the proposed method on other kinds of graphs. From the table below, we can see that we can also canonize >90% on other kinds of graphs (like networks and database), and have *even less* uncanonizable features, like 2.59% on COLLAB. This is because molecular graphs are already more symmetric than other kinds of real-world graphs.\n\n| Dataset | Ratio of sign-uncanonizable eigenvalues | Ratio of basis-uncanonizable eigenvalues | Total |\n| --- | --- | --- | --- |\n| MOLPCBA (molecular) | 2.24% | 7.37 % | 9.61% |\n| COLLAB (network) | 0.88 % | 1.71 % | 2.59% |\n| IMDB-BINARY (movie database) | 2.29 % | 6.32 % | 8.61% |\n| github-stargazers (network) | 2.81 % | 3.44 % | 6.25% |\n\n---\n\n**Q2**. You observe that your assumptions are violated for some small percentage of eigenvectors on real-world datasets. I was wondering if these eigenvectors are evenly spread out over the eigenvalue spectrum or could it be the case that these are all for the lowest eigenvalues? This could be problematic since these are the eigenvectors one would like to use.\n\n**A2**. We measured the number of sign-uncanonizable eigenvectors with low, mid, and high frequency on 3 datasets. It appears that uncanonizable eigenvectors are distributed more in high frequency, which is good news as studied in the LapPE paper, as low frequency components usually matter the most for model performance. \n\n| Dataset | Low | Mid | High |\n| --- | --- | --- | --- |\n| MOLTOX21 | 130 | 1271 | 4017 |\n| MOLTOXCAST | 170 | 1413 | 4449 |\n| MOLPCBA | 8723 | 54004 | 280361 |\n\n---\n\n**Q3**. In the axis projection step, why do you need c?\n\n**A3**. Here, adding a constant $c$ does not affect the correctness of our theorem. But with different $c$’s, we can get different numbers of uncanonizable eigenvectors. Therefore, we can tune $c$ to attain better canonization. In practice, we set $c$ to 10 for all cases as a good default choice.\n\n---\n\n**Q4**. I suppose that in practice alpha_i will not be exactly the same. Do you then consider all values or do you apply some binning algorithm to get B_i? I also wonder what is k in practice?\n\n**A4**. That is a good point. We do not use binning here. Instead, we judge two float numbers `(a, b)`  to be the same if they are close enough. Specifically, we use the PyTorch function `torch.allclose(a, b)` that checks if two floating point numbers are equal up to some tolerance.\n\nWe also measure the average value of $n$ (#nodes) and $k$ (#distinct $\\alpha$ values) in 3 datasets. From the table below we can see on average $k$ is slightly smaller but also close to $n$, because there are rather few repeated $\\alpha_i$’s.\n\n| Dataset | $n$  | $k$ |\n| --- | --- | --- |\n| MOLTOX21 | 19.1 | 17.3 |\n| MOLTOXCAST | 19.2 | 16.8 |\n| MOLPCBA | 26.0 | 20.2 |\n\n---\n\n**Q5**. In Tables 4 and 5, why is it that MAP increases the number of parameters?\n\n**A5**. In our experiments, we allow a flexible choice of model architectures (layers, hidden dimensions) to achieve the best performance. This setting is consistent with prior works, specifically [1] and [2]. When further ensuring a similar model size, as shown below, the results are still consistent with the original ones as our MAP still outperforms LapPE+RS.\n\n*New Results on MOLPCBA under similar model size.*\n\n| Model | PE | $k$ | #Param | AP |\n| --- | --- | --- | --- | --- |\n| GatedGCN | None | 0 | 2641K | 0.265 ± 0.003 |\n| GatedGCN | LapPE + RS | 3 | 2642K | 0.266 ± 0.002 |\n| GatedGCN | MAP | 3 | 2658K | **0.268 ± 0.002** |\n\n**References:**\n\n[1] Dwivedi, V. P., Luu, A. T., Laurent, T., Bengio, Y., & Bresson, X. (2021). Graph neural networks with learnable structural and positional representations. *arXiv preprint arXiv:2110.07875*.\n\n[2] Lim, D., Robinson, J., Zhao, L., Smidt, T., Sra, S., Maron, H., & Jegelka, S. (2022). Sign and basis invariant networks for spectral graph representation learning. *arXiv preprint arXiv:2202.13013*.\n\n---\n\nHope our new results above could address your concerns. We are very happy to take your further questions."}, {"review_id": "ubwFOiwJCu", "reviewer": "Reviewer_R8b6", "summary": "The authors address the problem of expressiveness in graph neural networks. Positional encodings using spectral approaches have suffered from sign and basis invariance. The authors propose Laplacian canonization which finds unique representations, and they analyze what properties the canonization should preserve and in practice what is the ratio of eigenvectors that fulfill these conditions. They propose a new simple canonization algorithm for sign and  basis invariance—Minimal Axis Projection (MAP)---that uses axis projection functions to identify canonical directions. They also present conditions under which MAP can guarantee sign and basis canonization. Experimental results evaluate MAP on graph classification benchmarks and show improved results with lowest computational runtime.", "questions": "1. RSE: the eigenvectors should be unit-normalized (or normalized to same length) \n2. If using the low frequency eigenvectors, the corresponding eigenvalues are the smallest, and thus the values are very small (especially if also unit normalized and n is large). How is this useful in practice? Are these concatenated scaled in some way at input to the network? \n3. Are the uncanonizable eigenvectors in the datasets concentrated in low or high frequency, or spread uniformly? \n4. How would this method work for a ring graph (cycle)?\n5. Why are result using SignNet not included for tables 4 and 5?\n6. Figures 4 and 5 in the appendix are very useful toy illustration that should be moved to the main paper\n7. What if all eigenvectors are used for MAP, as in the BasisNet paper (k=all)? \n\nMinor comments:\n* line 176: “question that which…” \n* line 190 - can reference Table 2\n* 3.3.3 - heading should be “summary” not “summarization” \n* line 273: eigendecomposition complexity is cubic for dense Laplacians, whereas most real world graphs are sparse, so that is a worst case complexity. In practice it is lower.  \nLine 336: why does increasing k (8–>16) make performance worse? Shouldn’t the network just utilize the lower freq vectors if they are more important? \n\n\n", "limitations": "limitations aren't discussed ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Originality: the approach appears to be novel.\n\nSignificance: Designing proper architectures that preserve symmetries and are more expressive is an important and open topic  currently in GNN literature. \n\nQuality: the approach is both simple and fast. Experiments show pairing MAP with multiple architectures to obtain gains in performance.  The ablation study demonstrates the contributions of the different parts of the approach. Full implementation details are provided in the supplement. \n\nClarity:  the paper is well-written.\n", "weaknesses": "Experimental results show incremental / modest improvement compared to BasisNet. The main contribution is in reduced runtime. Furthermore, BasisNet model with k=all in their paper (Table 1) achieve better performance than MAP in the current paper (Table 3). Authors should explain decision to not include these results from the BasisNet paper \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer R8b6 for appreciating the simplicity and significance of our paper. We address your concerns as follows.\n\n---\n\n**Q1.** SignNet model with k=all in their paper (Table 1) achieve better performance than MAP in the current paper (Table 3). Authors should explain decision to not include these results from the BasisNet paper.\n\n**A1**. Among all the baselines of our paper (LapPE, RS, SignNet) and also other papers that also use LapPE [1-2], we find that SignNet seems the only one that incorporates all eigenvectors in PE, which could be problematic for larger graphs (e.g., MalNet-Tiny has 1410 nodes on average). For a consistent comparison, we adopt $k=8$ in our comparison.\n\n**References:**\n\n[1] Kreuzer et al. (2021). Rethinking graph transformers with spectral attention. *NeurIPS.*\n\n[2] Rampášek et al. (2022). Recipe for a general, powerful, scalable graph transformer. *NeurIPS.*\n\n---\n\n**Q2**. RSE: the eigenvectors should be unit-normalized (or normalized to same length).\n\n**A2**. Here, the eigenvectors in $\\mathbf{U}$ are already unit-normalized, and we reweight them with $\\mathbf{\\Lambda}^{1/2}$ to add eigenvalue information. We will state it clearer in the revision.\n\n---\n\n**Q3**. If using the low frequency eigenvectors, the corresponding eigenvalues are the smallest, and thus the values are very small (especially if also unit normalized and n is large). How is this useful in practice? Are these concatenated scaled in some way at input to the network?\n\n**A3**. In practice, we used the eigen-decomposition of the adjacency matrix $\\hat{\\mathbf{A}}=\\mathbf{I}-\\mathbf{L}$, which has the same eigenvectors as the Laplacian while avoiding the small-eigenvalue issue (whose eigenvalues are $1-\\lambda_i$ instead).\n\n---\n\n**Q4**. Are the uncanonizable eigenvectors in the datasets concentrated in low or high frequency, or spread uniformly?\n\n**A4**. We measured the number of sign-uncanonizable eigenvectors with low, mid, and high frequency on 3 datasets. It appears that uncanonizable eigenvectors are distributed more in high frequency, which is good news as studied in the LapPE paper, as low frequency components usually matter the most for model performance.\n\n| Dataset | Low | Mid | High |\n| --- | --- | --- | --- |\n| MOLTOX21 | 130 | 1271 | 4017 |\n| MOLTOXCAST | 170 | 1413 | 4449 |\n| MOLPCBA | 8723 | 54004 | 280361 |\n\n---\n\n**Q5**. How would this method work for a ring graph (cycle)?\n\n**A5**. This is an interesting question. As shown below, we find that a larger node size $n$ leads to more uncaonizable features, suggesting a close correlation between automorphism and uncanonizable features. This is understandable because an automorphic graph like rings can rotate itself and stay the same, we cannot specify a unique location for a node. We believe that the theoretical relationship between automorphism and sign/basis canonizability would be an interesting open problem to explore in the future.\n\n| #Nodes | Ratio of sign-canonizable eigenvectors | Ratio of basis-canonizable eigenspaces |\n| --- | --- | --- |\n| 5 | 3/5 | 0/2 |\n| 6 | 2/6 | 0/2 |\n| 7 | 4/7 | 0/3 |\n| 8 | 1/8 | 0/3 |\n| 9 | 5/9 | 0/4 |\n| 10 | 3/10 | 0/4 |\n\n---\n\n**Q6**. Why are results using SignNet not included for tables 4 and 5?\n\n**A6**. All accuracy performance of the baselines are taken from the original papers of LapPE and SignNet. Some models are not conducted with SignNet because the original paper did not provide them. The SignNet authors only provided codes on ZINC and did not implement them on SAN and GraphiT. To be more complete, here we also reproduce some newly tuned SignNet results on MOLTOX21, where MAP still outperforms SignNet under different backbones.\n\n| Model | PE | $k$ | #Param | ROCAUC |\n| --- | --- | --- | --- | --- |\n| GatedGCN | None | 0 | 1004K | 0.772 ± 0.006 |\n| GatedGCN | SignNet | 3 | 1754K | 0.782 ± 0.004 |\n| GatedGCN | MAP | 3 | 1505K | **0.784 ± 0.005** |\n| PNA | None | 0 | 5245K | 0.755 ± 0.008 |\n| PNA | SignNet | 16 | 1367K | 0.745 ± 0.008 |\n| PNA | MAP | 16 | 1951K | **0.761 ± 0.002** |\n\n---\n\n**Q7**. Figures 4 and 5 in the appendix are very useful toy illustration that should be moved to the main paper.\n\n**A7**. Thanks for your suggestion. We will move Figures 4 and 5 to the main paper.\n\n---\n\n**Q8**. What if all eigenvectors are used for MAP, as in the BasisNet paper (k=all)?\n\n**A8**. We try using all eigenvectors with GatedGCN on ZINC and the results are provided below. We can see that MAP has no improvement by using k=all, and thus underperforms SignNet. We believe this is attributed to the uncanonizable eigenvectors being more densely distributed in high frequencies, as shown in **A4**. In comparison, SignNet achieves sign-invariance w.r.t. these uncanonizable eigenvectors (although with more computation cost and losing expressive power) and attains better performance. To validate this hypothesis, we mask the uncanonizable eigenvectors of MAP and conduct experiments again. We call this variant **MAP-mask**. The result shows that masking uncanonizable eigenvectors significantly improves the performance of MAP, reaching comparable performance with SignNet. We believe that in the future, developing better canonization algorithms could further close this gap.\n\n| Model | Test MAE |\n| --- | --- |\n| SignNet  (k=all) | 0.100 ± 0.007 |\n| MAP (k=8) | 0.120 ± 0.002 |\n| MAP (k=all) | 0.121 ± 0.003 |\n| MAP-mask  (k=all) | 0.106 ± 0.001 |\n\n---\n\n**Q9**. Why does increasing k (8–>16) make performance worse? Shouldn’t the network just utilize the lower freq vectors if they are more important?\n\n**A9**. Here, for efficiency, we only tune hyperparameters on $k=8$ and deploy them to other $k$’s. When further tuned under $k=16$, we can see that they attain the same performance.\n\n| $k$ | 8 | 16 |\n| --- | --- | --- |\n| Test MAE | 0.120 ± 0.002 | 0.120 ± 0.004 |\n\n---\n\nHope our elaborations and new experiments above could address your concerns. Please let us know if there is more to clarify."}]

Author rebuttal:

Meta-review: This paper proposes the Laplacian canonization approach to address the sign and basis ambiguities of eigenvectors. The proposed canonization method is light-weighted and can be used for any graph neural networks. Experimental results validate the efficacy of the proposed approach. The proposed Laplacian canonization is novel. The paper is well written and the experiments are convincing.
Decision: Accept (poster)