On the Stability of Expressive Positional Encodings for Graphs
Authors: Yinan Huang
William Lu
Joshua Robinson
Yu Yang
Muhan Zhang
Stefanie Jegelka
Pan Li
Venue: ICLR 2024 poster (2024)
Keywords: graph neural networks
positional encoding
stability
Primary area: learning on graphs and other geometries & topologies

Abstract: Designing effective positional encodings for graphs is key to building powerful graph transformers and enhancing message-passing graph neural networks. Although widespread, using Laplacian eigenvectors as positional encodings faces two fundamental challenges: (1) *Non-uniqueness*: there are many different eigendecompositions of the same Laplacian, and (2) *Instability*: small perturbations to the Laplacian could result in completely different eigenspaces, leading to unpredictable changes in positional encoding.  Despite many attempts to address non-uniqueness, most methods overlook stability, leading to poor generalization on unseen graph structures. We identify the cause of instability to be the use of "hard partition'' of eigenspaces. Hence, we introduce Stable and Expressive Positional Encodings (SPE), an architecture for processing eigenvectors that uses eigenvalues to ``softly partition'' eigenspaces. SPE is the first architecture that is (1) provably stable, and (2) universally expressive for basis invariant functions whilst respecting all symmetries of eigenvectors. Besides guaranteed stability, we prove that SPE is at least as expressive as existing methods, and highly capable of counting graph structures. Finally, we evaluate the effectiveness of our method on molecular property prediction, and out-of-distribution generalization tasks, finding improved generalization compared to existing positional encoding methods. Our code is available
at https://github.com/Graph-COM/SPE.

Published as a conference paper at ICLR 2024
ON THE STABILITY OF EXPRESSIVE POSITIONAL EN- CODINGS FOR GRAPHS
Yinan Huang".. William Lu Joshua Robinson', Yu Yang', Muhan Zhang Stefanie Jegelka', Pan Li !Georgia Institute of Technology. Purdue University, Stanford University, "Tongji University, "Peking University, MIT CSAIL
(yhuang903, panlij @gatech.edu, lu909spurdue.edu,
yanggru057@@toonggi.edd...u muhan@@ku.edu.cn stefje@mit.edu
ABSTRACT
Designing effective positional encodings for graphs is key to building powerful graph transformers and enhancing message-passing graph neural networks. Al- though widespread, using Laplacian eigenvectors positional encodings faces two fundamental challenges: (1) Non-uniqueness: there are many different eigen- decompositions of the same Laplacian, and (2) Instability: small perturbations the Laplacian could result in completely different eigenspaces, leading to unpre- dictable changes in positional encoding. Despite many attempts to address non- uniqueness, most methods overlook stability, leading to poor generalization on un- seen graph structures. We identify the cause of instability be a "hard partition" of eigenspaces. Hence, we introduce Stable and Expressive Positional Encodings (SPE), an architecture for processing eigenvectors that uses eigenvalues to "softly partition" eigenspaces. SPE is the first architecture that is (1) provably stable, and (2) universally expressive for basis invariant functions whilst respecting all sym- metries of eigenvectors. Besides guaranteed stability, we prove that SPE is at least as expressive as existing methods, and highly capable of counting graph struc- tures. Finally, evaluate the effectiveness of our method molccular property prediction, and -iitt---iittibttiinn gen generalization tasks, finding improved general- ization compared to existing positional encoding methods. Our code is available at https: / / thub. coon/Graph-aee COE.SP...
INTRODUCTION
Deep learning models for graph-structured data such as Graph Neural Networks (GNNs) and Graph Transformers have been arguably one of the most popular machine learning models on graphs, and have achieved remarkable results for numerous applications in drug discovery, computational chem- istry, and social network analysis, etc. (Kipf & Welling, 2017; Bronstein et al., 2017: Duvenaud et al., 2015; Stokes et al., 2020; Zhang & Chen, 2018; Ying et al., 2021; Rampášek et al., 2022b). However, there is a common concern about these models: the limited expressive power. For exam- ple, it is known that message-passing GNNs et al,, Morris et al., 2019) in distinguishing non-isomorphic graphs, and in general cannot even approximate common functions such as the number of certain subgraph patterns (Chen al., 2020; Arvind et al., 2020; Tahmasebi et al., 2020; Huang et al., 2023). These limitations could signifi- cantly restrict model performance, e.g., since graph substructures can closely related the target function in chemistry, biology and social network analysis (Girvan & Newman, 2002; Granovetter, 1983; Koyutürk et al., 2004; Jiang et al., 2010; Bouritsas et al., 2022).
most expressive the Weisfeiler-LLemal test (Xu
To alleviate expressivity limitations, there has been considerable interest in designing effective posi- tional encodings for graphs (You et al., 2019; Dwivedi & Bresson, 2021; Wang et al., 2022a). Gen- eralized from the positional encodings of 1-D sequences for Transformers (Vaswani et al., 2017), the idea is to endow nodes with information about their relative position within the graph and thus make them more distinguishable. Many promising graph positional encodings use the eigenvalue decomposition of the graph Laplacian (Dwivedi et al., 2023; Kreuzer et al., 2021). The eigenvalue
"qqual contribution

---

Published as a conference paper at ICLR 2024
decomposition is strong candidate because the Laplacian fully describes the adjacency structure of a graph, and there is a deep understanding of how these cigenvectors and eigenvalues inherit this information (Chung, 1997). However, cigenvectors have special structures that must be taken into consideration when designing architectures that process eigenvectors.
Firstly, eigenvectors are unique: if is eigenvector, then is u. Furthermore, when there are multiplicities of eigenvalues then there are many more symmetries, since any orthogonal change of basis of the corresponding eigenvectors yields the same Laplacian. Because of this ba- sis ambiguity, neural networks that process eigenvectors should be basis invariant: applying basis transformations to input eigenvectors should not change the output of the neural network. This avoids the pathological scenario where different cigendecompostiion of the same Laplacian pro- duce different model predictions. Several prior works have explored sign and basis symmetries of eigenvectors. For example, Dwivedì & Bresson (2021); Kreuzer et al. (2021) randomly flip the sign of eigenvectors during training so that the resulting model is robust to sign transformation. Lim et al. (2023) instead design new neural architectures that are invariant to sign flipping (SignNet) or basis transformation (BasisNet). Although these basis invariant methods have the right symmetries, they do not yet account for the fact that two Laplacians that are similar but distinct may produce completely different eigenspaces.
This brings to another important consideration, that of stability. Small perturbations to the input Laplacian should only induce a limited change of final positional encodings. This "small change of Laplacians, small change of positional encodings" actually generalizes the previous concept of basis invariance and proposes stronger requirement on the networks. But this stability (or continuity) requirement is a great challenge for graphs, because small perturbations can produce completely different eigenvectors if some eigenvalues are close (Wang et al. (2022a), Lemma 3.4). Since the neural networks process eigenvectors, not the Laplacian matrix itself, they run the risk of being highly discontinuous with respect to the input matrix, leading to an inability to generalize to new graph structures and a lack of robustness to any noise in the input graph's is adjacency. In contrast, stable models enjoy many benefits such as adversarial robustness (Cisse et al., 2017; Tsuzuku et al., 2018) and provable generalization (Sokolić et al., 2017).
Unfortunately, existing positional encoding methods are not stable. Methods that only focus on sign invariance (Dwivedi & Bresson, 2021; Kreuzer et al., 2021; Lim et al., 2023), for instance, not guaranteed to satisfy "same Laplacian, same positional encodings" if multiplicity of eigen- values exists. Basis invariant methods such as BasisNet are unstable because they apply different neural networks to different eigensubspaces. In high-level view, they perform hard partitioning of eigenspaces and treat each chunk separately (see Appendix C for a detailed discussion). The discontinuous nature of partitioning makes them highly sensitive perturbations of the Laplacian. The hard partition also requires fixed cigendecomposition thus unsuitable for graph-level tasks. On the other hand, Wang et al. (2022a) proposes a provably stable positional encoding. But, achieve stability, it completely ignores the distinctness of each eigensubspaces and processes the merged eigenspaces homogeneously. Consequently, loses expressive power and has, e.g., a subpar perfor- mance on molecular graph regression tasks (Rampášek et al., 2022a).
Main contributions. In this work, we present Stable and Expressive Positional Encodings (SPE). The key insight is to perform a soft and learnable "partition" of eigensubspaces in eigenvalue dependent way, hereby achieving both stability (from the soft partition) and expressivity (from dependency on both eigenvalues and eigenvectors). Specifically:
SPE is provably stable. We show that the network sensitivity w.r.t. the input Laplacian is de- termined by the gap between the d-th and (d + 1)-th smallest eigenvalues if using the first d eigenvectors and eigenvalues. This implies our method is stable regardless of how the used d eigenvectors and eigenvalues change.
SPE can universally approximate basis invariant functions and is as least expressive as existing methods in distinguishing graphs. We also prove its capability in counting graph substructures.
We empirically illustrate that introducing more stability helps generalize better but weakens the expressive power. Besides, on the molecule graph prediction datasets ZINC and Alchemy, our method significantly outperforms other positional encoding methods. On DrugOOD (Ji et al., 2023), ligand-based affinity prediction task with domain shifts, our method demonstrates clear and constant improvement over other unstable positional encodings. All these validate the effectiveness of our stable and expressive method.
2

---

Published as a conference paper at ICLR 2024
2 PRELIMINARIES
Notation. We always use n for the number of nodes in a graph, d Σ n for the number of eigenvectors and eigenvalues chosen, and p for the dimension of the final positional encoding for each node. We use |1-1l to denote the L2 norm of vectors and matrices, and ||-IlF for the Frobenius norm of matrices.
Graphs and Laplacian Encodings. Denote an undirected graph with n nodes by g (A, X), where A E IR=xn is the adjacency matrix and X E Rpxp is the node feature matrix. Let D diag( ([Cz=1 As,)(=1) be the diagonal degree matrix. The normalized Laplacian matrix of is positive semi-definie matrix defined by =
L = Vdiag(A)V returns eigenvectors = I - D D-1/2 1///2--11 1-22 Its eigenvalue decomposition and eigenvalues X, which we denote by EVD(L) (V. In practice we may only use the smallest d S eigenvalues and eigenvectors, so abusing notation slightly, we also denote the smallest d eigenvalues by E Red and the corresponding cigenvectors by V E Rxxd A Laplacian positional encoding is function that produces node embeddings Z 12XP given (V, E [gd x Rd as input.
Basis invariance. Given eigenvalues À E Rd, if eigenvalue A; has multiplicity d, then the cor- responding eigenvectors V, E R form a dy-dimensional eigenspace. A vital symmetry of eigenvectors is the infinitely many choices of basis eigenvectors describing the same underlying eigenspace. Concretely, if V; is a basis for the eigenspace of X; then ViQ; is, too, for any orthog- onal matrix Q: E ((d)) The symmetries of each eigenspace
be collected together describe
the overall symmetries of V in terms of the direct sum group O()) := @,0(d) = {+,Q; E R-, d,xX,, d: Qi E (d4)). J. i.e., block diagonal matrices with ith block belonging to O(d)). Namely, for any Q E O()), both (V, X) and (VQ, A) are rigendecompositions of the same un- derlying matrix. When designing a model f that takes eigenvectors as input, we want f to be basis invariant: f(VQAA) = f(V, X) for any (V, A) E Raxd Rd and any Q O()).
Permutation equivariance. Let I1(n) = {P E (0,1)axn : PP I be the permutation matrices of n elements. A function f R - IR" called permutation equivariant, if for any E R" and any permutation P E [[().. it satisfies f(Px) = fzz)). Similarly, f Raxx + R said be permutation equivariant if satisfying (PXP Pf(()..
A PROVABLY STABLE AND EXPRESSIVE PE
In this section we introduce our model Stable and Expressive Positional Encodings (SPE). SPE is both stable and a maximally expressive basis invariant architecture for processing eigenvector data, such as Laplacian eigenvectors. We begin with formally defining the stability of a positional encoding. Then we describe our SPE model, and analyze its stability. In the final two subsections we show that higher stability leads to improved out-o--distribution generalization, and show that SPE universally expressive basis invariant architecture.
3.1 STABLE POSITIONAL ENCODINGS
Stability intuitively means that a small input perturbation yields a small change in the output. For eigenvector-basee positional encodings, the perturbation is to the Laplacian matrix, and should result in small change of node-level positional embeddings.
Definition 3.1 (PE Stability). PE method PF. Raadd RRdd Rexp is called stable, if there exist constants C' 0, such that for any Laplacian L'
||E(EED(L) P.PE(EVD(E')II SC. -C.
(1)
where P. arg min)) PL'PT
|f
is the permutaaiinn matrix matching two Laplacians.
is worth noting that here we adopt a slightly generalized definition of typical stability via Lipschitz continuity (c 1). This definition via Hölder continuity describes more comprehensive stability behavior of PE methods, while retaining the essential idea of stability.
Remark 3.1 (Stability implies permutation equivariance). Note that a PE method is permutation equivariant if it is stable: simply let = PL'P" T for some P E II(m) and we obtain the desired permutation equivariance PE(EVD(PLPTT) P. PE(EEVD(L))
3

---

Published as a conference paper at ICLR 2024
Input
Step 1
(1(2) $2(A)
(2)
Laplacian Decomposition
equianaent
n
Step
[Vdiag(, (A) 1m-12...
Output
V
[diag(A, (2)) 12...
7
VT
dxd
dxn
n
Xxnxm
nxp
P.L.P.
Stability property Z
P.Z
F
const.
Figure Illustration the SPE architecture (first two rows) and its stability property (last row). The input graph is first decomposed into eigenvectors V and eigenvalues A. In step 1, permutation equivariant oe act on À to produce another vector oe In step 2, we compute Vdiag (orgf(r(A) (> for each de and concatenate the results into tensor. This tensor is input into permutation equiv- ariant network to produce final node positional encodings.
Stability is hard to achieve due to the instability of eigenvalue decomposition-22 small perturbation of the Laplacian produce completely different eigenvectors (Wang et al. (2022a), Lemma 3.4). Since positional encoding models process the eigenvectors (and eigenvalues), they naturally inherit this instability with respect the input matrix. Indeed, as mentioned above, many existing positional encodings are not stable. The main issue is that they partition the eigenvectors by eigenvalue, which leads to instabilities. See Appendix C for a detailed discussion.
3.2 SPE: A POSITIONAL ENCODING WITH GUARANTEED STABILITY
To achieve stability, the key insight is avoid a hard partition of eigensubspaces. Simultaneously. we should fully utilize the information in the eigenvalues for strong expressive power. Therefore, we propose to a "soft partitioning" of eigenspaces by leveraging cigenvalues. Instead of treat- apply weighted sum of cigenvectors in eigenvalue
ing each eigensubspace independently, dependent way. If done carefully, this can ensure that as two distinct eigenvalues converge ttese exactly the degenerate points creating instability the way their respective eigenvectors pro- cessed becomes more similar. This means that two eigenvectors are "swapped", as happens at degenerate points, the model output does not change much. The resulting method is (illustrated in Figure I):
SPE SPE(V. A) p (VVdiag( Φi V Vdiig(
Vdiag(Øm. (A))VT) (2)
where the input is the smallest eigenvalues À E Rd and corresponding eigenvectors V E Raxd m a syper-parameted and Φe R. 2d and p m - xa are always permutation equivariant neural networks. Here, permutation equivariance means de(PA) ( for P E ((d)) and p (PAPT)) = Pp(A) for any P E [T(n) and input A. There are many choices of permutation equivariant networks that can be used, such element-wiss MLPs or Deep Sets (Zaheer et al., 2017) for de. and graph neural networks for p. The permutation equivariance of de and ensures that SPE is basis invariant.
Note that in Eq. (2), the term dd looks like a spectral graph convolution op- erator. But they methodologically different: SPE uses V (diag(o;())) V to construct posi- tional encodings, which are not used as a convolution operation to process node attributes (say as V
X). Also, de are general permutation equivariant functions that may express the

---

Published as a conference paper at ICLR 2024
interactions between different cigenvalues instead of elementwise polynomials each eigenvalue separately which are commonly adopted in spectral graph convolution.
It is also worthy noticing that term Vdiag( V will reduce to hard partitions of eigenvec- tors in the L-th eigensubspace if we let [oz = I(3 is the 1-th smallest eigenvalue). To obtain stability, what we need is to constrain Φe to continuous functions to perform continuous "soft partition"..
Assumption 3.1. The key assumptions for SPE as follows:
Φe and are permutation equivariant (see definitions after SPE Eq. (2)).
de is Ke-Lipshitz continuous: for any X, A E RRd, ||0e( ) - de(X')lF I Ke || - X
p is J-Lipschitz continuous: for any [A A2 Aml Raxnxm and [A A/...., A'ml
R=xxxm [|p(Ai, A.,..,, Am) Ai, A2...., A S JI A| AbllF
These two continuity assumptions generally hold by assuming the underlying networks have norm- bounded weights and continuous activation functions, such as ReLUU. As a result, Assumption 3.1 is mild for most neural networks.
Now we are ready to present our main theorem, which states that continuity of Φr and p leads to the desired stability.
Theorem 3.1 (Stability of SPE). Under Assumption 3.1, SPE is stable with respect to the input Laplacian: for Laplacians L, I',
[SPE(EVD(L) P.SPE(EVD( S(an ag) |L P.IP....
(3)
(a2 +as) ( F:
where the constants are 01 2J E
1i=1 Kg, 02 E
i== Me and az J JI Kt. Here
Mr = (u [A)) and again P. = arg min)) L L- P.LPP F. The eigengap 7 =
A Xa is the difference between the (d + 1)-th and d-th smallest eigenvalues, and +00 if
n.
Note that the stability of SPE is determined by both the Lipschitz constants J. K2 and the eigengap 7 = Aa- - Ad+1- The dependence on 7 comes from the fact that we only choose to use eigenvec- tors/eigenvalues. It is inevitable as long as d < and it disappears (? = +oo) if we let d = n. This phenomenon is also observed in PEG (Wang et al. (2022a), Theorem 3.6).
3.3 FROM STABILITY TO OUT-OF-DISTRIBUTTUN GENERALIZATION
An important implication of stability is that characterize the domain generalization gap by the model's Lipschitz constant (Courty et al., 2017; Shen et al., 2018). Although our method satisfies Hölder continuity instead of strict Lipschitz continuity, claim that interestingly, similar bound can still be obtained for domain generalization.
We consider graph regression with domain shift: the training graphs are sampled from source do- main L IPs. while the test graphs are sampled from target domain L ~ PT. With ground- truth function f (LD
and prediction model h(L) E IR, we are interested in the gap be- f(L) and -ut-of-distribution error (, EL-P, [L) f()). The following theorem states that for a base GNN equipped with SPE, we can upper bound the generalization gap in terms of the Hölder constant of SPE, the Lipschitz constant of the base GNN and the Wasseresteiin distance between source and target distributions.
tween in-distribution eтror (h) = EL-Fe (h(L)
Proposition 3.1. Assume Assumption 3.1 hold, and assume base GNN model GNN(L, X) e R that is C-Lipschitz continuous, i.e.,
[GNN(L, X) GNN(L', GNN(L'XX'ISSC min PETI(n)
L PL'PL 1
(4)
for any Laplacians L, L' and node features X,X'. Now let GNN take positional encodings as node features X SPE(EVD(L)) and let the resulting prediction model be h(L) = GNN(L, (L)(E)(())) Then the domain generalization gap ( - Et(s) satisfies
(h) (h) < <20(1= az WPss P7) 2/ 5/1 ((n WPPs, (5)
5

---

Published as a conference paper at ICLR 2024
where W ((ssPP) is the 1- I-Wasserstein distance'.
3.4 SPE IS UNIVERSAL BASIS INVARIANT ARCHITECTURE
SPE is a basis invariant architecture, but is it universally powerful? The next result shows that SPE universal, meaning that any continuous basis invariant function can be expressed in the form of where for brevity,
SPE (Eq. 2). To state the result, recall that SPE(V, A) = p(V
we express the multiple tee channels by Φ (01,..., Pm.
Proposition 3.2 (Basis Universality). SPE can universally approximate any continuous basis in- variant function. That is, for any continuous f for which f(V) = f(VQ) for any eigenvalue X and any Q E O()), there exist continuous p and & such that [(V) p(V
Only one prior architecture, BasisNet (Lim et al., 2023), is known to have this property. However, unlike SPE, BasisNet does not have the critical stability property. Section 5 shows that this has significant empirical implications, with SPE considerably outperforming BasisNet across all eval- uations. Furthermore, unlike prior analyses, of cigenvalues: it can distinguish two input matrices with different eigenvalues using 2-layer MLP models for p and é. In contrast, the original form of BasisNet does not eigenvalues, though it is easy to incorporate them.
show that SPE can provably make effeetive use
Proposition 3.3. Suppose that (V, A) and (V', X) are such that VQ V' for some orthogonal matrix Q E ((d) and X & X. Then there exist 2-layer MLPs for each or and 2-layer MLP p. each with ReLU activations, such that SPE(V. A) F SPE(V', X))
Finally, as a concrete example of the expressivity of SPE for graph representation learning, we show that SPE able to count graph substructures under stability guarantee.
Proposition 3.4 (SPE can count cycles). Assume Assumption 3.1 hold and let p be 2-IGNs (Maron et al., 2019b). Then SPE can determine the number of 3, 4, 5 cycles of a graph.
RELATED WORKS
Expressive GNNs. Since message-passing graph neural networks have been shown be at most
as powerful as the Weisfeiler-Lemaal test (Xu et al., 2019; Morris et al., 2019), there are many attempts to improve the expressivity of GNNs. We can classify them into three types: (1) high-order GNNs (Morris et al., 2020; Maron et al., 2019a;b); (2) subgraph GNNs (You et al., 2021; Zhang & Li, 2021; Zhao et al., 2022: Bevilacqua et al., 2022); (3) node feature augmentation (Li et al., 2020; Bouritsas et al., 2022; Barceló et al., 2021). In some senses, positional encoding can also be seen as an approach of node feature augmentation, which will be discussed below.
Positional Encoding for GNNs. Positional encodings aim to provide additional global positional information for nodes in graphs to make them more distinguishable and add global structural in- formation. It thus serves as node feature augmentation to boost the expressive power of general graph neural networks amessage-passiigg positional encoding methods can be categorized into: (1) Lappaacian--igenvectt---aaes (Dwivedi & Bresson, 2021; Kreuzer et al., 2021; Maskey et al., 2022; Dwivedi et al., 2022; Wang et al., 2022b; Lim et al., 2023; Kim al., 2022); (2) graph-distance-based (Ying et al., 2021; You et al., 2019; Li et al., 2020); and (3) random node features (Eliasof et al., 2023). A comprehensive discussion can be found in (Rampášek et al., 2022a). Most of these methods do not consider basis invariance and stability. Notably, Wang et al. (2022a) also studies the stability of Laplacian encodings. How- ever, their method ignores eigenvalues and thus implements a stricter symmetry that is invariant to rotations of the entire eigenspace. As result, the "over-stability" restricts its expressive power. Bo et al. (2023) propose similar operations as (diag(((A))V) However they focus on a specific architecture design (ø is transformer) for spectral convolution instead of positional encodings, and do not provide any stability analysis.
GNNs, spectral GNNs or graph transformers). Existing
Stability and Generalization of GNNs. The stability of neural networks is desirable as it implies better generalization (Sokolić et al., 2017; Neyshabur et al., 2017; 2018; Bartlett et al., 2017) and
For graphs W (PssPe) := inf min L PL'PT] ||e (L, L')aLaL'. Here (T Pr) the set of product distributions whose marginal distribution is Ps and Ppr respectively.

---

Published as a conference paper at ICLR 2024
Table 1: Test MAE results random seeds) on ZINC and Alchemy.
Dataset
PE method
#PEs
#param
Test MAE
No PE
N/A
575k
0.177210.0040
PEG
8
512k
0.1444
PEG
Full
512k
0.1878:00.0227
SignNet
8
631k
0.1034
ZINC
SignNet
Full
662k
0.0853
BasisNet
8
442k
0..054
BasisNet
Full
513k
0. 0.1155
SPE
8
635k
0.0736440.0007
SPE
Full
650k
0.0693 00.0000
No PE
N/A
1387k
0.112
PEG
8
1388k
0,114
Alchemy
SignNet
Full
1668k
0.113 002
BasisNet
Full
1469k
0.110 001
SPE
Full
1785k
0.108 0.108.00.01
transferability under domain shifts (Courty et al., 2017; Shen et al., 2018). In the context of GNNs, many works theoretically study the stability of various GNN models (Gama et al., 2020; Kenlay et al., 2020; 2021; Yehudai et al., 2020; Arghal al., 2022; Xu al., 2021; Chuang Jegelka, 2022). Finally, some works try to characterize the generalization error of GNNs using VC dimen- sion (Morris et al., 2023) or Rademacher complexity (Garg et al., 2020).
EXPERIMENTS
In this section, we use numerical experiments verify our theory and the empirical effectiveness of our SPE. Section 5.1 tests SPE's strength graph positional encoder, and Section 5.2 tests the robustness of SPE to domain shifts, key promise of stability. Section 5.3 further explores the empirical implications of stability in positional encodings. Our key finding is that there is a trade- off between generalization and expressive power, with less stable positional encodings fitting training data better than their stable counterparts, but leading to worse test performance. Finally, Section 5.4 tests SPE on challenging graph substructure counting tasks that message passing graph neural networks cannot solve, and SPE significantly outperforms prior positional encoding methods.
Datasets. We primarily use three datasets: ZINC (Dwivedi et al., 2023), Alchemy (Chen et al., 2019) and DrugOOD (Ji et al., 2023). ZINC and Alchemy graph regression tasks for molecular property prediction. DrugOOD is an OOD benchmark for Al drug discovery, for which we choose ligand-based affinity prediction three types of domains where distribution shifts arise: (1) Assay: which assay the data point belongs to: (2) Scaffold: the core structure of molecules; and (3) Size: molecule size. For each domain, the full dataset is divided into five partitions: the training set, the in-distribution (ID) validation/test sets, the -utto--distriuution validation/test sets. These OOD partitions are expected be distributed on the domains differently from ID partitions.
classfication task (to determine if drug active). It considers
Implementation. We implement SPE by: Φi either being a DeepSet (Zaheer et al., 2017). element- wise MIPs or siece-wise cubic splines (see Appendix B. for detailed definition); and p being GIN (Xu et al., 2019). Note that the input p many tensors, and then independently give each m tensors, hence we first split into tensors node features to an identical GIN. Finally, we sum over the first n axes to output a permutation equivariant n X p tensor.
Baselines. We compare SPE to other positional encoding methods including (1) No positional encodings, (2) SignNet and BasisNet (Lim et al., 2023), and (3) PEG (Wang et al., 2022a). In all cases adopt GIN as the base GNN model. For fair comparison. all models will have comparable budgets on the number of parameters. We also conducted an ablation study to test the effectiveness of our key component dz, whose results included in Appendix B.
7

---

Published as a conference paper at ICLR 2024
Table AUROC results (5 random seeds) on DrugOOD.
Domain
PE Method
ID-Val (AUC)
ID-Test (AUC)
OOD-Val (AUC)
OOD-Test (AUC)
No PE
92.92.0.14
92.8920.14
71.02
71.68:1.10
PEG
92.51 10.17
92.57 20.22
70.86+0.44
71.98
Assay
SignNet
92. 92.2640.21
92.43=0.22
70.
72 72.27
BasisNet
88.96 88.9611.35
89.42.1.18
71.19
71.6620.05
SPE
92.84
92.94--0.15
71.26+0.62
72.53-j0.00
No PE
96.56.0.1v
87 87.95
79.07
68.00.20.60
PEG
95.65
86.20
79.17
69.15.:0.75
Scaffold
SignNet
95.48.0.34
66.73
+0.81
66.43 1.06
BasisNet
83.80
78, 78.44-12.45
73.36
66.32.5568
SPE:
96.32200.8
88.12 40.44
80.03+0.55
69.6444..9
No PH
93. 13.7880.12
93.60 2.27
82.76
66.04+0.700
PEG
92. 92.46.0.35
92.67
82. $2.12+0.49
66.01 10.10
Size
SignNel
93.30
93.20
80.67
60.00
BasisNet
86.0444.01
85.5144.04
75.97
60.79.3.19
SPE
92. 16.335
92.67.0022
82.12
66.02+1.00
5.1 SMALL MOLECULE PROPERTY PREDICTION
We use SPE to learn graph positional encodings on ZINC and Alchemy. We let di be Deepsets using only the top 8 eigenvectors (PE-8), and element-wise MLPs when using all eigenvectors (PE-full). As before, we take to be a GIN.
Results. The test mean absolute eгrorx (MAEs) are shown in Table On ZINC, SPE performs much better than other baselines, both when using just 8 eigenvectors (0.0736) and all eigenvectors (0.0693). On Alchemy, we always use all eigenvectors since the graph size only ranges from 8 to 12. For Alchemy we observe no significant improvement of any PE methods over base model w/o positional encodings. But SPE still achieves the least MAE among all these models.
5.2 OUT-OI-DISTRIBUTION GENERALIZATION BINDING AFFINITY PREDICTION
We study the relation between stability and cattof-ddisrrbbution generalization using the DrugOOD dataset (Ji al., 2023). We take o be element-wise MLPs and be GIN usual.
The results are shown in Table 2. All models have comparable Area Under ROC (AUC) on the ID-Test set. However, there is big difference in OOD-Test performance on Scaffold and Size domains, with the unstable methods (SignNet and BasisNet) performing much worse than stable methods (No PE, PEG, SPE). This emphasizes the importance stability in domain generalization. Note that this phenomenon is less obvious in the Assay domain, which is because the Assay domain represents concept (labels) shift instead of covariant (graph features) shift.
Results.
5.3 TRADE-OFFS BETWEEN STABILITY, GENERALIZATION AND EXPRESSIVITY
We hypothesize that stability has different effects on expressive power and generalization. Intu- itively, very high stability means that outputs change very little as inputs change. Consequently, we expect highly stable models to have lower expressive power, but to generalize more reliably to new data. To test this behavior in practice the stability by tuning the complexity of underlying neural networks in the following two ways:
evaluate SPE ZINC using 8 eigenvectors. We control
1. Directly control the Lipschitz constant of each MLP in SPE (in both d; and p) by normalizing weight matrices.
Let de be a piecewise cubic spline. Increase the number spline pieces from to 6, with fewer splines corresponding higher stability.
See Appendix for full details. In both cases we use eight de functions. We compute the summary statisties over different random seeds. As measure of expressivity,
report the average training loss over the last 10 epochs on ZINC. As a measure of stability, we report the generalization gap (the difference between the test loss and the training loss) the best validation epoch over ZINC.
8

---

Published as a conference paper at ICLR 2024
Train Firor Individual nun
Text Liror
Commeral Cootton
Test Ener Individaal
com
Generalizacion Gap
Indivitul
4.47
Lipschita Comeant
Lipschitz Constntt
Lipschitz Constort
Training
Test
Generlization pap
Indivilual nun
Individual nmn
Individual
Training Bevve
Test Eanot
Geverallzation altooinionn
spline.n pieces
oplinen_pieces
spiine pleces
Figure 2:
Training error, test error and generalization gap v.s. model complexity (stability). In the first row, we directly change the Lipschitz constant of individual MLPs; in the second row, we choose oe be piecewise spline functions and change the number of pieces.
Results. Figure 2, we show the trend training error, test error and generalization gap as Lipschiz constant of individual MLPs (first row) or the number of spline pieces (second row) changes. We can see that as model complexity increases (stability decreases), the training error gets reduced (more expressive power) while the generalization gap grows. This justifies the important practical role of model stability for the trade-off between expressive power and generalization.
5.4 COUNTING GRAPH SUBSTRUCTURES
log test MAE
counting
To empirically study the expressive power of SPE, we follow prior works that generate random graphs (Zhao et al., 2022; Huang et al., 2023). The dataset contains Erdös-Rent Rensi random graphs and other random regular graphs (see Appendix M.2.1
log (MAI5)
SigaNet BasisNet
in Chen et al. (2020)) and is randomly split into train/valid/test splitting with ratio 3:2:5. and label nodes according the number of substructures they are part of. We aggregate the node labels to obtain the number of substructures the overall graph and view this as a graph regression task. We let di be element-wise MLPs and GIN.
SPB
3-Cycle
4-Cycle
S-Cycle
6-Cycle
Figure 3: log, (Test MAE) over random
seeds on cycle counting task. Lower is better.
Results. Figure 3 shows that SPE significantly out- performs SignNet counting 3,4,5 and 6-cycles. We emphasize that linear differences in log-MAE correspond to exponentially large differences in MAE, This result shows that SPE still achieves very high expressive power, whilst enjoying improved robustness to domain-shiff thanks to its stability (see Section 5.2).
CONCLUSION
We present SPE, learnable Laplacian positional encoding that is both provably stable and ex- pressive. Extensive experiments show the effectiveness of SPE on molecular property prediction benchmarks, the high expressivity in learning graph substructures, and the robustness well as generalization ability under domain shifts. the future, this technique can be extended to link pre- diction other tasks involving large graphs where stability is also crucial and desired. Finally, our analysis provides a general technique for graph eigenspace stability, not just limited to domains of positional encodings and graph learning.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
The authors would like to thank Derek Lim for constructive discussion. Yinan Wang and Pan Li are partially supported by the NSF awards PHY-2117997, I18-2239565.
REFERENCES
Raghu Arghal, Eric Lei, and Shirin Sacedi Bidokhti. Robust graph neural networks via probabilistic lipschitz constraints. In Learning for Dynamics and Control Conference, pp. 1073-1085, PMLR, 2022.
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky. On weisfeiler-leman invariance: Subgraph counts and related graph properties. Journal of Computer and System Sci- ences, 11::22-59, 2020.
Pablo Barceló, Floris Geerts, Juan Reutter, and Maksimilian Ryschkov. Graph neural networks with local graph parameters. Advances in Neural Information Processing Systems, 34:25280-25292 2021.
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally margin bounds for neural networks. Advances neural information processing systems, 30, 2017.
Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M. Bronstein, and Haggai Maron. Equivariant subgraph aggregation net- works. In International Conference on Learning Representations, 2022.
Deyu Bo, Chuan Shi, Lele Wang, and Renjie Liao. Specformer: Spectral graph neural networks meet transformers. In The Eleventh International Conference on Learning Representations, 2023.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45()):657-663 2022.
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geomet- ric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18 42,
2017.
Guangyong Chen, Pengfei Chen, Chang- Yu Hsich, Chee- Chee-Kong Lee, Benben Liao, Renjie Liao, Wei- wen Liu, Jiezhong Qiu, Qiming Sun, Jie Tang, Richard S. Zemel, and Shengyu Zhang. Alchemy: A quantum chemistry dataset for benchmarking ai models. CoRR, (bbs/1906.09427, 2019.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? Advances in neural information processing systems, 33:10383-10395, 2020.
C. Chuang and Jegelka. Tree mover's distance: Bridging graph metrics and stability of graph neural networks. In Neural Information Processing Systems (NeurIPS), 2022.
Fan RK Chung. Spectral graph theory, volume 92, American Mathematical Soc., 1997.
Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. Parseval networks: Improving robustness to adversarial examples. In International conference on machine learning, pp. 854 863. PMLR, 2017.
Nicolas Courty, Rémi Flamary, Amaury Habrard, and Alain Rakotomamonjy. Joint distribution optimal transportation for domain adaptation. Advances in neural information processing systems, 30, 2017.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams. Convolutional networks graphs for learning molecular fingerprints. Advances in neural information processing systems, 28, 2015.
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. AAAI Workshop Deep Learning on Graphs: Methods and Applications, 2021.
10

---

Published as a conference paper at ICLR 2024
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. In International Conference on Learning Representations, 2022.
Vijay Prakash Dwivedi, Chaitanya K. Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24(43):1-48, 2023.
Moshe Eliasof, Fabrizio Frasca, Beatrice Bevilacqua, Eran Treister, Gal Chechik, and Haggai Maron. Graph positional encoding via random feature propagation. International Conference on Machine Learning. 2023.
Fernando Gama, Joan Bruna, and Alejandro Ribeiro. Stability properties of graph neural networks. IEEE Transactions on Signal Processing, 68:5680-5695, 2020.
Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. In International Conference on Machine Learning, pp. 1430.
PMLR, 2020.
Michelle Girvan and Mark EJ Newman. Community structure in social and biological networks. Proceedings of the national academy of sciences, 99(12):7821-722) 2002.
Mark Granovetter. The strength of weak ties: A network theory revisited. Sociological theory, PD- 201-233, 1983.
Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012.
Yinan Huang, Xingang Peng, Jianzhu Ma, and Muhan Zhang. Boosting the cycle counting power of graph neural networks with 2N-2N.GNSs. In The Eleventh International Conference on Learning Representations, 2023.
Yuanfeng Ji, Lu Zhang, Jiaxiang Wu, Bingzhe Wu, Lanqing Li, Long-Kai Huang, Tingyang Xu, Yu Rong, Jie Ren, Ding Xue, Houtim Lai, Wei Liu, Junzhou Huang, Shuigeng Zhou, Ping Luo, Peilin Zhao, and Yatao Bian. Drugood: Out-of-distribution dataset curator and benchmark for ai-aided drug discovery a focus on affinity prediction problems with noise annotations. Pro- ceedings of the AAAI Conference on Artificial Intelligence, 37(7):8023-800 8031, 2023.
Chuntao Jiang, Frans Coenen, and Michele Zito. Finding frequent subgraphs in longitudinal social network data using weighted graph mining approach. In Advanced Data Mining and Appli- cations: 6th International Conference, ADMA 2010, Chongging, China, November 19-21, 2010, Proceedings, Part I 6, pp. 405-416. Springer, 2010.
Henry Kenlay, Dorina Thanou, and Xiaowen Dong. On the stability of polynomial spectral graph filters. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 5350-5354. IEEE, 2020.
Henry Kenlay, Dorina Thano, and Xiaowen Dong. On the stability of graph convolutional neural net- works under edge rewiring. In ICASSP 2022222222222 22201 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3513-8517, IEEE, 2021.
Jinwoo Kim, Dat Nguyen, Seonwoo Min, Sungjun Cho, Moontae Lee, Honglak Lee, and Seunghoon Hong. Pure transformers are powerful graph learners. Advances in Neural Information Processing Systems, 11512112--4555 2022.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference Learning Representations, 2017.
Mehmet Koyutürk, Ananth Grama, and Wojeiech Szpankowski. An efficient algorithm for detecting frequent subgraphs in biological networks. Bioinformatics, 20(spppl 1):200-i2077, 2004.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Re- thinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 34, 2021.
11

---

Published as a conference paper at ICLR 2024
Pan Li, Yanbang Wang. Hongwei Wang. and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. Advances in Neural Information Processing Systems, 2020.
Derek Lim, Joshua David Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and basis invariant networks for spectral graph representation learning. In The Eleventh International Conference Learning Representations, 2023.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Advances in Neural Information Processing Systems, pp. 2153-2164, 2019a.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In International Conference on Learning Representations, 2019b.
Sohir Maskey, Ali Parviz, Maximilian Thiessen, Hannes Stärk, Ylli Sadikaj, and Haggai Maron. Generalized laplacian positional encoding for graph representation learning. In NeurIPS 2022 Workshop on Symmetry and Geometry in Neural Representations, 2022.
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 Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4602 4609, 2019.
Christopher Morris, Gaurav Rattan, and Petra Mutzel. Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings. Advances in Neural Information Processing Systems, 01221824-18444 2020.
Christopher Morris, Floris Geerts, Jan Tönshoff, and Martin Grohe WL meet VC. In Proceedings of the 40th International Conference on Machine Learning, pp. 25275-25302 PMLR, 2023.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring general- ization in deep learning. Advances neural information processing systems, 30, 2017.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A PAC-bayesian approach to
spectrally-normaazzed margin bounds for neural networks. International Conference on Learn- ing Representations, 2018.
Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for a general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 35: 111114400-155555 2022a.
Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for a general, powerful, scalable graph transformer. Advances Neural Information Processing Systems, 35: 11445511-4555 2022b.
Jian Shen, Yanru Qu, Weinan Zhang, and Yong Yu. Wasserstein distance guided representation learning for domain adaptation. Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Jure Sokolić, Raja Giryes, Guillermo Sapiro, and Miguel RD Rodrigues. Robust large margin deep neural networks. IEEE Transactions on Signal Processing, 65(16):4265 4288- 2017.
Gilbert W Stewart and Ji-guang Sun. Matrix perturbation theory. 1990.
Jonathan M Stokes, Kevin Yang, Kyle Swanson, Wengong Jin, Andres Cubillos-Ruiz, Nina M Donghia, Craig R MacNair, Shawn French, Lindsey A Carfrae, Zohar Eloom-Ackermann, et al. A deep learning approach to antibiotic discovery. Cell, 18804)668--702 2020.
Behrooz Tahmasebi, Derek Lim, and Stefanie Jegelka. Counting substructures with higher-order graph neural networks: Possibility and impossibility results. arXiv preprint arXiv:20/2.03174, 2020.
Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. Lipschitz-margin training: Scalable certi- fication of perturbation invariance for deep neural networks. Advances in neural information processing systems, 31, 2018.
12

---

Published as a conference paper at ICLR 2024
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural informa- tion processing systems, 30, 2017.
Haorui Wang, Haoteng Yin, Muhan Zhang, and Pan Li. Equivariant and stable positional encoding for more powerful graph neural networks. In International Conference on Learning Representa- tions, 2022a.
Haorui Wang, Haoteng Yin, Muhan Zhang, and Pan Li. Equivariant and stable positional encoding for more powerful graph neural networks. In International Conference on Learning Representa- lions, 2022b.
K. Xu, M. Zhang, J. Li, S. Du, K. Kawarabayashi, and S. Jegelka. How neural networks extrap- olate: From feedforward to graph neural networks. In International Conference Learning Representations, 2021.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations, 2019.
Gilad Yehudai, Ethan Fetaya, Eli Meirom, Gal Chechik, and Haggai Maron. On size generalization in graph neural networks. 2020.
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? Advances in neural information processing systems, 34:28877-28888, 2021.
Jiaxuan You, Rex Ying, and Jure Leskovec. Position-awand aware graph neural networks. In International Conference on Machine Learning, pp. 7134-7143, PMLR, 2019.
Jiaxuan You, Jonathan M Gomes-Selman, Rex Ying, and Jure Leskovec. Identity-aware graph neural networks. Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 10737-10745, 2021.
Yi Yu, Tengyao Wang, and Richard Samworth. A useful variant of the davis-kahar theorem for statisticians. Biometrika, 102(2):315-323, 2015.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander Smola. Deep sets. Advances in neural information processing systems, 30, 2017.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in neural information processing systems, 31, 2018.
Muhan Zhang and Pan Li. Nested graph neural networks. Advances in Neural Information Process- ing Systems, 34:15734-15747, 2021.
Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any GNN with local structure awareness. In International Conference on Learning Representations, 2022.
13

---

Published as a conference paper at ICLR 2024
A DEFERRED PROOFS
denote integer intervals. Let [[()) be the symmetric group on n elements. Unless otherwise stated, eigenvalues are counted with mul- tiplicity; for example, the first and second smallest eigenvalues of E IR are both 1. Let |||]| and ||-IlF be n.2 and Frobenius norm of matrices.
Basic conventions. Let [n] = 2 n [1, and [a, zr [a. [a
Matrix indexing. For any matrix A E R"xd:
Let [A] k E R be the entry at row and column j
Let
[A] (1) E IRd be row i represented as a column vector
Let
[
R be column j
For any set J (i,,.. :w S [d]. let [A], E Raxdd he columns .h jar arranged in matrix
n d, let diag( (A) E R" be the diagonal represented as a column vector
Special classes matrices. Define the following sets:
{ {D E Raxa Vi # [D), =0]
All n x n diagonal matrices: D(n) =
The orthogonal group in dimension i.e. all n x orthogonal matrices: O(n)
{Q E R Q-=
All x permutation matrices: [I(n) P {0,1] p-1= }T}
All n x n symmetric matrices: S(n) = { E Raxn A
Spectral graph theory. Many properties of an undirected graph are encoded in its (normalized) Laplacian matrix, which is always symmetric and positive semidefinite. In this paper, only sider connected graphs. The Laplacian matrix of a connected graph always has a zero eigenvalue with multiplicity 1 corresponding The Laplacian eigenmap technique uses the eigenvectors corresponding to the d smallest positive eigenvalues vertex positional encodings. We assume the dth and (d+ 1)th smallest positive eigen- values of the Laplacian matrices under consideration are distinct. This motivates definitions for the following sets of matrices:
eigenvector of all ones, and all other eigenvalues positive.
All n x n Laplacian matrices satisfying the properties below:
La(n) [(L E S(n) L 2 0 rank(L) = n A L1 =0
(6)
d-th and (d 1)-th smallest positive eigenvalues distinct)
All x diagonal matrices with positive diagonal entries: (4 (D E D(n) D
All n matrices with orthonormal columns: O(n, d) {Q Raxd [Q], [Q], 1 5
Eigenvalues and eigenvectors. For the first two functions below, assume the given matrix has least dl positive eigenvalues.
Let Aa
Unza S(n) + (d) return diagonal matrix containing the d smallest positive eigenvalues of the given matrix, sorted in increasing order.
Let X, Unza S(n) - (n,, d) return a matrix whose columns contain an unspecified set of or- thonormal eigenvectors corresponding to the smallest positive eigenvalues (sorted in increasing order) of the given matrix.
Let X(4) Unza S(n) + O(n, d) return matrix whose columns contain unspecified set of orthonormal eigenvectors corresponding to the d smallest eigenvalues (sorted in increasing order) of the given matrix.
Let Ad Un S(n) D(d) return a diagonal matrix containing the d greatest eigenvalues of the given matrix, sorted in increasing order.
14

---

Published as a conference paper at ICLR 2024
Let X Unna - (n, return matrix whose columns contain unspecified set of orthonormal eigenvectors corresponding to the d greatest eigenvalues (sorted in increasing order) of the given matrix.
Batch submatrix multiplication. Let A E Ru be a matrix and let (Ja)e= be a partition of [d]. For each E [p], let dy = [Tx] and let Bą E IR xds matrix. For notational convenience, let B (Bk, Ja) 1 Define binary star operator such that
* B Roxd the matrix where Ak [p], [A Bl = [A] B
(7)
We primarily use batch submatrix multiplication in the context orthogonal invariance, where an orthogonal matrix is applied to each cigenspace. For any (eigenvalue) matrix A D(d), define
{
O(A) (1Q...)) 1QUEE II((da))
R=1
where Ts { [d] [diag(A)], = on for each & E [p] and {or)k- are the distinct values in diag(A). this context, ((A) the domain of the right operand of
A.1 PROOF OF THEOREM 3.1
Theorem 3.1 (Stability of SPE). Under Assumption 3.1, SPE is stable with respect to the input Laplacian: for Laplacians L'.
|SPE(EVD(L) P.SPE(EVD(L)))) S(an + a2)dd// V 1L- - P.LP.
(3)
+ (10 +03) - P.LPP |F:
where the constants are on = I Ke, 02 = 4V2J m Mr and 0g = Eth Kr. Here Mj = suPxe(0.2] [X)]l and again P. = arg pe LL P.LP. 1|.. The eigengap 7 = Ad+1 - Xa the difference between the (d + 1)-th and d-th smallest eigenvalues, and 7 = +00 if
d ==
Proof. Fix Laplacians L, L' La(n). We will show that for any permutation matrix P E II(n),
[SPE(EVD(L)) SPE(EVD(Z)))ll E (an + a2)
- -PPLP
(9)
(000 + || PL'P 1|
Fix P E [l(n). For For notational convenience, we denote diag(p (p()) by p(A) with A diag (A}. and
let X = X,(L), = (L) X' = Xa(L'), and = Aa(L'). Then
(SPE(EVD(L)) PSPE(EVD(E'))ll
(10)
|()x X (A)X PP(x''s(
X' XA) Il (11)
( (A) - ((PX ... PX' (A')x' PT)
|F
(12)
(c)
m JJ) XOX(A)X PT
(13)
[ PX PTI
(14)
PX PXON(A" PT IF
(c)
Xxx PX + X XT)
X'
(15)
15

---

Published as a conference paper at ICLR 2024
where (a) holds by definition of SPE, (b) holds by permutation equivariance of (c) holds by Lips- chitz continuity of p. (d) holds by the triangle inequality, and (e) holds by permutation invariance of Frobenius norm.
Next, we upper-bound I Let min ( | L because
The 0 case is trivial,
ô -=0 = PL
SPE(EVD(L) )
(16)
SPE(EVD(L) P (SPE(EVD(E'),
where (a) holds due to permutation equivariance of SPE. Thus, assume d > 0 for the remainder of this proof. Let
= = (i) 2 1 < <.. < jp+1 d +
(17)
be the keypoint indices at which eigengaps are greater than or equal to where (a) holds because
Adp1 - Aa = 2 min 7 || PI'P
(18)
For each l E [p). let T. = (j E [d] jxx S < jx+1} be a chunk of contiguous indices at which
eigengaps are less than 8, and let dy = 1J&l be the size of the chunk. Define matrix A E D(d)
vk [p). Aj E Tk. ddag (A)], >
(19)
follows that
! X - (x)(A)x x
+ x Φe
A X - -X'' X X PT
F
(20)
+
PX Φe
A
X PT - -X PT
@ X X (A) (A)x X
(
+ X Φ
A x -PX's A X PT
(21)
X Φ 1 X - X'Ox
(c)
| (ee(A) Φe (a{(A))) + x - - _T
-PX'
(22)
+ 1 2 0b (A) -(c(A) /|=
(1) 2 (A) Φ (A)
+ x (A) (A) PX'0: Φ5 (A)XTPT) PT
(23)
(c) $ 2K
A Á
+ x (A) (A)x - PX' o/ (A)x
(24)
S 2Kg
p
X 3h
Φ [A)]
[ Ju -
X Io (e (A)
[X]
PT
Je.T
Ju.Jr
F
(25)
(g) <
2Kg
A
Ä
+
Jn
de (A)
JunFu
[X]] Jo
P
J.
(e (A)]
Jn.Ja
[X T
13h
PT
(26)
where (a) holds by the triangle inequality, (b) holds by permutation invariance of Frobenius norm, (c) holds by lemma A. (d) holds because X and X' have orthonormal columns, (e) holds by Lipschitz
16

---

Published as a conference paper at ICLR 2024
continuity of Φ2. (f) holds by block matrix algebra, and (g) holds by the triangle inequality. Next, we upper-bound 3::
P
Σ JEJ
(1
Aje)²
(27)
(Ay 13-1)
(28)
f'= k=Ij
8
(29)
k= JEJ
デ'=
8
Σ
1 jzh)
(30)
JEJJ
d
8
(31)
$ 8
(32)
where (a) holds by definition of A, (b) holds because the innermost sum (b) telescopes, (c) holds because Ts is a chunk of contiguous indices at which eigengaps are less than 8, and (d) holds because Th is a contiguous integer interval.
Next, we upper-bound ④ By definition of A, the entries [diag (A)], are equal for all j E Tk-
By permutation equivariance of de, the entries [diag( de ( are equal for all j E Tk. Thus, J..r Mee I for some μe, E IR. As de is Lipschitz continuous and defined on a bounded domain [0, 2) it must be bounded by constant Mr- = (0 (e(A). Then by boundedness of Φr.
(e (A)
|pe
1 vdx
||
1
|000 (A) Je.Tke S
0e AA) 1|
S
Mr Vdz
(33)
vdl
Therefore,
||x),,0 Th (Me, I) [x|_. Jr. PIX' To (ME
(X)] T Jn
PT
(34)
F
|ue,ul
T PT [ [X] 1/. - -P [x13]
[x]_
(35)
Me
S
[ [ Jr.
[X]
J6 P J4 [X]] 31 PT]
(36)
dz
Now, we consider two cases. Case 1: 2 2 or \ - No 2
Define the matrices
Z X l and Z/ [X' 1
(37)
There exists orthogonal matrix Q2 E O(ds) such that
10 Onl|
|| 1Zx -z
[ (xa (PL'PPL
(38)
v8 L PL'PTI
(39)
min (dia Ajo-1, djen Ajunn-1}
17

---

Published as a conference paper at ICLR 2024
10) / L PL'PT
(40)
6
where (a) holds by lemmas A.2 and A.3, (b) holds by proposition A. and (c) holds because ju and JR+1 keypoint indices at which eigengaps greater than equal to 6.
Case 2: k and A1 A 8. Define the matrices
1 =
J. and Zi = v
11
(41)
vn
There exists an orthogonal matrix Q1 E O(d1 + 1) such that
1
PzlQ FF
[dd +1) (L) ((d (PL'PT)
(42)
v8 L - PL' P
(43)
X/2 Aj2-1
v8 L - PL'PTI
(44)
where (a) holds by lemmas A.2 and A.3, (b) holds by proposition A.1,² and (c) holds because ja is keypoint index at which the eigengap is greater than or equal to 6.
Hence, in both cases,
X
P Ju
X J1
P
Z
PZ p l|F
(45)
(
Z P Z P
(46)
(0)
12 Z z PT
+ Z Z PT
PZ z PM
(47)
(4)
Z 1 Q 1 PT
|F 1| 1H IP|
(48)
(
Q z P 1F + 1 - -2
(49)
1 2
PZ Q
(50)
2
32
L PL'P lFF
(51)
8
where (a) holds in Case 2 because
[X]
[X] 5h
P P
[X] T
PT
(52)
Th
Jh
1
11T
+[X], Jo
[x]]
111
P
[X' Pt
(53)
n
71
111TT
T
[X], Jh
[x]
-11T
1
+
[X
Xx1J1 T
PT
(54)
n
11
[1]
1
1
[X],]
Vn
P
[1
P
(55)
Vn
Jr
X Jk
VR
[
Z - P PT.
(56)
(b) holds because Q = I, (c) holds by the triangle inequality, (d) holds by lemma A. 1 (e) holds because Zy and Z% have orthonormal columns and Q2 and P are orthogonal, (1) holds because Frobenius norm is invariant to matrix transpose, and (g) holds by substituting in eqs. (40) and (44). Combining these results,
322 Mr L - PL'PT
(57)
Vd 8
We can apply proposition A.I because Xis extracts the same contiguous interval of eigenvalue indices for any matrix (m) and PL PT (T.(m) by lemmas A.2 and A.3.
We can apply proposition A.1 because Y(a, +1) extracts the same contiguous interval of eigenvalue indices
for any matrix.
18

---

Published as a conference paper at ICLR 2024
Next, we upper-boune bound 2::
(a)
XXI (10: O
(58)
(6)
(A)(AA) (c(AA)
(59)
Ke A - A
(60)
@ Ke,
Σ (hg X2)²
(61)
(c) S Ke L PL'P 1|
(62)
where (a) holds by lemma A. (b) holds because X' has orthonormal columns, (c) holds by Lip- schitz continuity of Φr. the notation X, in (d) is the jth smallest positive eigenvalue of L', and (e) holds by proposition A.3 and lemma A.3.
Combining our results above,
|SPE (D)
P SPE,, n. (L))
(63)
17
p 4v22 Me | L- PL'P
lF
2Kg8
Σ
+ K3ElL
PL'P
lF
(64)
vd
k=1
(6)
m
L L- PL'P
1F F +KKell LUIL--PLPPTI
2Kdd 8 2
(65)
L - PL'P
ajd 6 + and
+ | PPLPP 1F
(66)
(
_ (a) + 02) d
L - PL'PTIE
22 + t0)
IL-PL'P
(67)
F
as desired, where (a) holds by substituting in D (b) holds because E o <E
d2) =
d3 and Eh-1 Vdv sp d, (c) holds by the definition of aj through 03, and (d) holds because
8 2
L - PLPP
(68)
L - PL'P
- P-PPPP
F
dt
L
PLP
(69)
8
A.2 PROOF OF PROPOSITION 3.1
Proposition 3.1. Assume Assumption 3.1 hold, and assume a base GNN model GNN(L, X) e TR. that is C-Lipschitz continuous, i.e.,
IGNN(L, x) GNN(L', CCNN(E'XX'ISC min (LL-PL'P) - PETI(n)
(4)
for any Laplacians L. L' and node features X.X'. Now let GNN take positional encodings
as node features = SPE(EVD(L)) and let the resulting prediction model be h((L) =
Then the domain generalization gup (h) =x((s) satisfies
(h( ch))) < 2C a2 (P)) Pr) 2Cd // +2))+ W(Ps..P), (5)
where (PPsPP)) is the I-Wasserstein distance
(L, L')dLdL' Here 'For graphs, W(psPPt = inf f min (in(())))))))) L- PL-PL'P *L,
(T PT) is the set of product distributions whose marginal distribution is Ps and Pr respectively.
19

---

Published as a conference paper at ICLR 2024
Proof. The proof goes in two steps. The first step shows that Lipschitz continuous base GNN with a Hölder continuity SPE yields an overall Hölder continuity predictive model. The second step shows that this Hölder continuous predictive model has a bounded generalization gap under domain shift.
Step 1: Suppose base GNN model GNN( X) is C-Lipschitz and SPE method SPE(L) satifies
Theorem 3.1. Let our predictive model be (() GNPEE,)PE()))(E)) R. Then for any Laplacians L, L' E and any permutation P E [m) we have
[L(L) - h(L') - |GNN(L, SPE(EVD(()) - GNN (PE(EVD(L))
(70)
(a) - C PLLPP + |SPE(EVD(L)) PSPE(EVD(Z')II)
(71)
16) c
1+ 12
02 d
+03)
- PL'P || + C + l/4 L PL'P
|
1/2
(72)
Ci -
1/2
(73)
where (a) holds by continuity assumption of base GNN, and (b) holds by the stability result Theorem 3.1.
Step 2: Suppose the ground-truth function h lies in our hypothesis space (thus also satisfies eq.
(73)). The absolute risk source and target domain are defined (h) EL-Ps h/ h-d (L)
and (h) = EE-eP [L) - ht (L) respectively. Note that function [L) = [h(L) - h- (L) is also
Hölder continuous but with two times larger Hölder constant. This is because
[M(L) - h* (L) $ [k(L) h(zz)) + (M(L') hL))
(triangle's inequality for arbitrary L') (74)
[h(L) h(Zz) + (1((=)))+)())))---)))))()))))>)) -=== -='))(())))))))))))))))) ('(L') (triangle's inequality); (75)
and thus for arbitrary L,
((L)-((L') = (L(L)) - 11" (L) 1m(1) -((())
-(L') + (L) (L')))
(76)
S 20 L- PL'P + | L- -LLP 1| 1/2
(77)
We can show the same bound for S(L') -LL). Thus ʃ is Hölder continuous with constants 2C,, 2C2, and we denote such property by [I S (2C1, 202) for notation convenience.
An upper bound of generalization gap (h) - (h) can be obtained:
(h) - (h) = EL-F, (h(L) - l1" (L) - EL (onss/((())) - (L)
(78)
(a)
<
sup 11 ((C,CC)
EL f(L) - ELLFsf(L)
(79)
sup
[(L)(P PL(L))
(80)
((C,C.))
inf *EI(())(FT.s) |10 S(C, / (((())((E'))(L( L')aLa''
sup
(81)
where (a) holds because [||((L) - (D) < (C1, C2), and (b) holds because of the definition of product distribution
I[FF.PP)) - [: f T(L, "(L'''''''''' PT(L) / ((LLL''aL=PP(L))
Notice the integral can be further upper bounded using Hölder continuity of f:
/ (U(L)) sup II S(C,,,(
L')ddL'
(82)
/(22
20 min Pell(a)
LL'PP PL'P || + 2Cr min Pell(n)
[L PI/P 1/2 T(L, L')aLa'. F
20

---

Published as a conference paper at ICLR 2024
Let us define the Wasserstein distance of Py and Ps be
/
WTT,, Ps)
inf =En(Pr.Fa (F)) Pell(n)
min
| - PL'P || (L, L'dddE
(83)
Then plugging eqs. (82, 83) into (81) yields the desired result
/
(h) =x(h) = 2C1 2C Ps))
inf
min Pell(n)
PL'P +L,,
(84)
(2) $ PCs 202 inf rEll(F,Pss)
(
1/2
min Pell(n)
| PL'P
n (L, L'd
(85)
20 W (P Ps) + Ps),
(86)
where (a) holds due to the concavity of sqrt root function.
L
A.3 PROOF OF PROPOSITION 3.2
Proposition 3.2 (Basis Universality). SPE can universally approximate any continuous basis in- variant function. That is, for any continuous f for which f(V) = f(VQ) for any eigenvalue X and any Q O()), there exist continuous p and á such that f(V) p( didig(((\)))
Proof. In the proof we are going to show basis universality by expressing BasisNet. Fix eigen- values E Rdd Let Ā E R² be a sorting cigenvalues without repetition, i... x = i-th smallest eigenvalues. Assume eigensubspaces. Recall that BasisNet is of the following form:
d. For eigenvectors V, let Ie C [d] be indices of f-th
BasisNet(VV V, A) (B)
(0)
(B) (VVVV
B (V1 V..)) 10
(87)
where T. is number of eigensubspaces.
For SPE, let us construct the following de:
I; = do,
2i de
1
if E (Ae,
de- Xe
[dr(x)]
(88)
Xe-1
if (de-1;ãe))
x
0, otherwise.
Note that this is both Lipschitz continuous with Lipschitz constant 1/ minn((A+ λe), and per- mutation equivariant (since elementwise). Now we have Vdiag(o:(A)) Vz, V since du (A) is either 1 (when A; Xx) or 0 otherwise. For e f>> L. we let th = 0 by default. Then simply let p be:
pl A Am) (1)) (0l (A1)
(5) (Am) = ( (013) (A1) 06 (AL)).
(89)
Here oi (8) (Ar) = ( (Ar) for A, + 0 and WLOG (5) (As) 0 if Ar = 0. And p(9) is of
function that first ignores ( matrices and mimic (B)) Therefore,
SPE(V, pl didiggl (A))TT Vdiag @m (A))VT)
((5) (11)) (Vz, Vz (S) (Vz. VTTT) BasisNet (V, A).
(90)
Since BasisNet universally approximates all continuous basis invariant function, SPE.
n
21

---

Published as a conference paper at ICLR 2024
A.4 PROOF OF PROPOSITION 3.4
Proposition 3,4 (SPE count eycles). Assume Assumption 3.1 hold and let p be 2-IGNs (Maron et al., 2019b). Then SPE can determine the number of 3, 4, 5 cycles of a graph.
Proof. Note that from Lim et al. (2023), Theorem 3 we know that BasisNet can count 3, 4, 5 cycles. One way to let SPE count cycles is to approximate BasisNet first and round the approximate error, thanks to the discrete nature of cycle counting. The key observation that the implementation of BasisNet to count cycles is special case of SPE:
#cycles of each node = BasisNet V. A) = p(Vdiag ( 3...y Vdiag @m (A)) (91)
where (A)]; = [A, is the E-th smallest eigenvalue) and continuous. Unfortunately, these &e are not continuous so SPE cannot express them under stability requirement. Instead, we can construct a continuous function de to approximate discontinuous o with arbitrary precision s, say,
AA E 10,2]
(((()) o(2) <E.
(92)
Then we can upper-bound
v V -V de
V | (c)))
<E
<E
(93)
where (a) holds due to the Lemma A.I. Moreover, using the continuity of (defined in Assumption 3.1), we obtain
(BasiNNet V. A)
A) S
Σ V - -V
||
< Jde.
(94)
Now, let Jd/2, then we can upper-bound the maximal error of node-level counting:
max #cycles node SPE(V, 2))² < sE/n
|BasssNet( A) SPE(V, A)ll < J2 = 1/4.
(95)
max #cycles of node i SPE(V, A) 1/2.
(96)
2E|n]
Then, by applying an MLP that universally approximates rounding function, we are done with the proof.
A.5 PROOF OF PROPOSITION 3.3
Proposition 3.3. Suppose that (V, A) and (V', ,') are such that VQ = V' for some orthogonal matrix Q E ((d) and X + X. Then there exist 2-layer MLPs for each de and 2-layer MLP p. each with ReLU activations, such that SPE(V. A) + SPE(V', X))
Proof. Our proof does not require the use of the channel dimension-i.e, we take m and p to equal 1. The argument is split into two steps.
First show that for the given X, X' and any o, d' d there is choice of two layer network ((A) = W20 W, A + b,) + b2 such that d(A) Φ and o(X') = d'. Our choices of W,, W2 will have dimensions x d, b, by E Rd and denotes the ReLU activation function.
Second choose o, o' e Rd such that VØVT has strictly positive entries, whilst V' (the matrix of all zeros). The argument will conclude by choosing 41, a2 by by E such that the layer network (on the real line) p(x) d2 a a + b1)+b layer MLP on the real line, applied element-wise to matrices then summed over both n dimensions) produces distinct embeddings for (V, A) and (V', X²).
We begin with step one.
22

---

Published as a conference paper at ICLR 2024
Step If Φb = Ø' then may simply take W1 and bı to be the zero matrix and vector respectively. Then (W + b1) = o ( + b1) = 0. Then we may take W2 = (identity) and b2 = Ø, which guarantees that o( Φ and @(X)) D'.
So from now assume that Φ * ø'. Let X and X' differ in their ith entries X, X₁ and assume without loss of generality that X; < X,. Let W1 = 10....,..
0, e; O, O.....0) the matrix of all zeros,
except the ith column which is the ith standard basis vector. Then W is the vector of all zeros, except for i entry equaling X (similarly for X). Next take b to be the vector of all zeros, except for ith entry - (A): + X)/2, the midpoint between the differing eigenvalues. These choices make z o (Wi + b1)= = O. and z' = = + bi) such that zjj 0 for j # i, and 2 = (X; 22) Next, taking W22 [0...., O, c, O,... 0j where the ith column is C; 2( 1 - X₂) ensures that
2 = 0,
(97)
W22' = 0b' - Φ
(98)
Then we may simply take b2 Φ producing the desired outputs:
( = W2o(W, A + b1) + b2 = Φ. ( = W20 W + b1) + b2 = d'
(99)
(100)
as claimed.
Step 2: Expanding the matrix multiplications into their sums have:
(Vdiag()) 185 Σ Derisyid
(101)
V'diag Φ V 1ú Σ
(102)
Our first choice is take ø'= Next, we aim to pick Φ such that V -e-j" > 0 for some indices i" .j" In fact, this is possible for an i.j pair since each pair of eigenvectors is orthogonal, and non-zero, so for each i.j there must be d' such that Uia Ujd- >> 0, and we can simply take Φa = 1 if d = d" and Φa = 0 for a d'.
= O, ensuring that V "'diag(''VV"
0 (an n n matrix of all zeros).
Thanks to the above choices, taking di and b ensures that
(a V'diag (ongg(o'V'' VT + b1)
(103)
but that,
(a Vdiag( VT + bbi)),; >
(104)
for some j.j. Note that in both cases, the scalar operations are applied to matrices element-win
Finally, taking 02 =1/ Eizlo(aa- Vdiag( V + b1)] ij > 0 and by = 0 produces embeddings
SPE(V, A) = 1 + 0 = SPE(V' (') X')
(105)
A.6 AUXILIARY RESULTS
Proposition A.1 (Davis-Kahan theorem (Yu et al., 2015, Theorem 2)). Let A' E S(n). Let A S ... S An be the eigenvalues of A, sorted in increasing order. Let the columns of x, x' O(n) contain the orthonormal eigenvectors of A and A', respectively, sorted in increasing order of their corresponding eigenvalues. Let J = [s. t| be a contiguous interval of indices in [n]. and let d d= T be the size the interval. For notational convenience, let do -oo and An+1 co. Then there exists an orthogonal matrix Q E O(d) such that
V8 { [vaiL L'1l II I'llF]
|| - - Q11= <
(106)
min (ue Xo- de+1 dc3
23

---

Published as a conference paper at ICLR 2024
Proposition A.2 (Weyl's inequality). Let X S(n) R return the ith smallest eigenvalue of the given matrix. For all A, A' S(n) and all i E [m]. (,(A) - x, =|A- A'll.
Proof. By Horn & Johnson (2012, Corollary 4.3.15).
X(AA) + (1 A & (A) I A(A) + (A A). (A') [A A)), A, (A A')], and
(107)
Therefore (A)
(A(A) A((A') max (Ar(A) A. (A((A))
(108)
S max (An(A- A),, -A A)}
(109)
max Ar(A AA'l
(110)
iE|ni
max AA
(111)
= I|A A'll
(112)
Proposition A.3 (Hoffman- -iieladd corollary (Stewart Sun, 1990, Corollary IV.4.1))). Let A S(n) + R return the ith smallest eigenvalue of the given matrix. For all A, A' E S(m),
(A((A) ((A)) & ||A A'I
(113)
Lemma A.1. Let {Ax}e
compatible matrices. For any E [p],
II
Ax
< II
||ellF
II ||
(114)
1=11
M==++1
Proof. First, observe that for any matrices A E Ruxr and B E R"xx
12
|AB||
|BB),
Σ
ABee
|| | 2 Beyll |||||
Σ
[B]
==1
j=1
= |||l||
|B|
(115)
Therefore,
P
3V
[-11
A
|
A
(116)
k=
||A
(117)
11-1
(p-E-1
|
II k=O
||A]=|l|
||
lFF
(118)
k=1
(t-1
P II || A=2++
II
|
|
(119)
where (a) and (c) hold by applying eq. (115) recursively, and (b) and (d) hold because Frobenius norm is invariant matrix transpose.
Lemma A.2 (Permutation equivariance of eigenvectors). Let A Roxa and P E P(n). Then for any E R., Pæ is an eigenvector of P PAP iff is eigenvector of A.
24

---

Published as a conference paper at ICLR 2024
Proof.
Pæ is an cigenvector of PAPT
R, PAP Px = XPx
(120)
EE R, PAx AP
(121)
EE R, PAx PAæ
(122)
EXR Ax= A
(123)
x is an eigenvector of A,
(124)
where (a) is the definition of eigenvector, (b) holds because permutation matrices are orthogonal, (c) holds by linearity of vecrox-vector multiplication, (d) holds because permutation matrices are invertible, and (e) is the definition of eigenvector.
Lemma A.3 (Permutation invariance of cigenvalues), Let A E Rax" and P E P(n). Then À E R an eigenvalue of PAP iff is an eigenvalue of A.
Proof.
À is an eigenvalue of PAP
Ey+0, 0, PAPTy = Xy
(125)
Ey 0, PAP XPP
(126)
Ey 0, PAP = PAP
(127)
Ex 00 PAæ Phæ
(128)
T 00, Ax x
(129)
X is an eigenvalue of A,
(130)
where (a) is the definition of eigenvalue, (b) holds because permutation matrices are orthogonal, (c) holds by linearity matrix-vector multiplication, (d)-(e) hold because permutation matrices are invertible, and (f) is the definition of eigenvalue.
B EXPERIMENTAL DETAILS AND ADDITIONAL RESULTS
B.1 IMPLEMENTATION OF SPE
SPE includes parameterized permutation equivariant functions p R 2xaxm
- R and Φe
Rdd + Rd.
For de. we treat input À as d vectors with input dimension and use either elementwise-MI.Ps i.e., [dr(A)]; = MLP((,,, or Deepsets to process them. We also use piecewise cubic splines, which is R to H piecewise function with cubic polynomials each piece. Given number of pieces hy- perparameter, the piece interval is determined by uniform chunking [0, 2), the range eigenvalues. The learnable parameters the coefficients of cubic functions for each piece. To construct òe, simply let one piecewise cubic spline elementwisely act on each individual eigenvalues:
[b){ spline(A:).
(131)
For p. in principle any permutation equivariant tensor neural networks can be applied. But in our experiments we adapt GIN as p. Here is how: for input Rexaxm we first partition along the second axis into many matrices A, E R=xm (in code we do not actually need to partition them since parallel matrix multiplication does the work). Then we treat A, as node features of the original graph and independently and identically apply GIN to this graph with node features A, This will produce node representations Z, R from A, Finally we let Z Σn= Z; be the final output of p. Note that this whole process makes p permutation equivariant.
25

---

Published as a conference paper at ICLR 2024
B.2 IMPLEMENTATION OF BASELINES
For PEG, we follow the formula of their paper and augment edge features by
Gijj f Gig MLP([IV: - V=-ll)-
(132)
For SignNet/BasisNet, we refer to their public code release BasisNet. Specifically, SignNet uses GINs 6 and BasisNet uses 2-IGN Ø. Note that the original BasisNet does not support inductive learning, i.c., it cannot even apply to new graph structures. This because it has separate weights for eigensubspaces with different dimension. Here simply initialize an unlearned weights for eigensubspaces with unseen dimensions.
https//ggihuu.com/qqq////iii
B.3 OTHER TRAINING DETAILS
We Adam optimizer with an initial learning rate 0.001 and 100 warm-up steps. We adopt linear decay learning rate scheduler. Batch size is 128 for ZINC, Alchemy and substructures counting, 64 for DrugOOD.
B.4 CONTROLLING LIPSCHITZ CONSTANT OF MLPS
Here we state how we control the Lipschitz constant of MLPs in Section 5.3. Technically, by Lips- chitz constant we actually mean an upper bound for best Lipschitz constant (the minimal Lipschitz constant for function). Note that for compositition of Lipschitz functions (fi fo o fu) with individual Lipschitz constants C₁ C2 .... C.. the product C₁ C2 ... C3 a valid Lipschitz con- stant. A MI.P consists of linear layers and ReLU activation. The Lipschitz constants of linear layers are simply the operator norm of weight matrices, while ReI.U is 1-Lipschitz. So we can easily get the Lipschitz constant of MLPs by multiplying the operator norm of weight matrices. As result, we can control the Lipschitz constant to be by first normalizing weight matrices to be unit norm and then multiply a constant / between layers assuming there are & layers.
B.5 GENERALIZATION GAP ON ZINC
We show the training loss and the generalization gap (test loss training loss) ZINC dataset as shown below. These loss are all evaluated at the epoch with minimal validation loss. We can see that though SignNet and BasisNet achieve a pretty low training MAE (high expressive power), their generalization gap is larger than other baselines (poor stability) and thus the final test MAE is not the best. For baseline GNN and PEG, they pretty stable with small generalization gap, but the poor expressive power make them hard to fit the dataset well (training loss is high). In contrast, SPE has not only lowest training MAE (high expressive power) but also small generalization gap (good stability). That is why it can obtain the best test performance among all the models.
Table 3: Test/training MAE and generalization gap results random seeds) on ZINC. Bold-face black, blue and pink are used to denote the first, second and third best method for each column (each method only counts once as there are multiple configurations).
Dataset
PE method
#PEs
#param
Test MAE
Training MAE
General. Gap
No PE
N/A
575k
0.1772++..0ul
0.1509 00.0086
0.0263+0.0113
PEG
8
512k
0.1444440.0076
0.1088 00.0066
0.0382+0.0100
PEG
Full
512k
0.1878+0.0027
0.148644..199
0.0342+0.0206
SignNet
631k
0.1034=2..0066
0.0418+0.0100
0.0602+0.0112
ZINC
SignNet
Full
662k
0.0853+4.002z
0.0349
0.0349440.0777 00.0088
0.0502+0.0100
BasisNet
442k
0.1554+0.00655 000068
0.0513
0.1042
BasisNet
Full
513k
0.1555
0.068440.0202
0.0989+0.cm
SPE
8
635k
0.0736=0.0007
0.032440.0058
0.0413+0.0057
SPE
Full
650k
0.069310.0040
0.033444.0054
0.035940.0087
26

---

Published as a conference paper at ICLR 2024
B.6 RUNNING TIME EVALUATION
We evaluate the running time of SPE and other baselines on ZINC and DrugOOD. The results represents the training/inference time on the whole training dataset (ZINC or DrugOOD) over trials. We can see that the speed SPE overall comparable to SignNet, and is much faster than BasisNet. This is possibly because BasisNet has to deal with the irregular and length-varying input [Vi V2VV2"... ....]. which is hard for parallel computation in a batch, while SPE simply needs to deal with the more uniform V'dia(((A))VV ((A))T
Table 4: Training and inference time (average over 5 trials) on ZINC and DrugOOD, evaluated on the whole training dataset. GPU Quadro RTX 6000
Dataset
PE method
#PEs
Train Time (s)
Inference Time (s)
No PE
N/A
3.31910.1p
2.85240.310
PEG
8
3.785+0.42
3.590
PEG
Full
3.639+4..37
3.518+00311
SignNet
8
8.72440.686
3.546:40.366
ZINC
SignNet
Full
23. #1.1939
7.883
BasisNet
8
49.923+ +.3311
18. 18.295=0.569
BasisNet
Full
66.176 +4.015
27.5 27.546400622
SPE
8
10.888 +0.416
5.336+10.736
SPE
Full
11 11.576+0.472
5.40644.499
No PE
N/A
13.560+0.657
4.260
PEG
32
14.212+1.066
4.780
DrugOOD
SignNet
32
30. +0.723
12.844
BasisNet
32
199.364
86.529
SPE
32
37.577 +0.833
21.706+0.850
To see how complexity grows with graph size, we construct Erdos-Renyy random graphs for dif- ferent graph sizes, ranging from 10 to 320. For each graph size, construct 1,000 such random graphs with fixed node degree 2.5. Then we train and test each methods on these 1,000 graph for 10 epochs estimate the time complexity. For fairness, each model has 60k parameters. By default use batch size 50, and if it is out-of-memory (OOM), we use batch size 5 then. It batch size 5 still leads to OOM, we will denote OOM in the results. Below we report the average training/inference time per epoch.
Graph size
GINE
PEG
SignNet
SPE
BasisNet
10
0.505 277
0.574+0.321
1.750
1.357+0.321
5.185
20
0.535
0.631
1.64840.325
1.323
3.41840.323
40
0.56140.297 297
0.644 332
2.293
1.507 +0.322
6.019
80
0.609 294
0.750+0..0 338
5.81040.333
4.030
40.848
160
1.056 10.271
1.410.1..355 0.356
21.153 10.275
55.256 100777
OOM
320
2.71410.411
4.403
83.833 10.188
OOM
OOM
Table 5: Average training time (s) on random graph dataset over 10 epochs.
Graph size
GINE
PEG
SignNet
SPE
BasisNet
10
0.12540.001
0.154_..001
0.465
0.385+0.002
2.32640.266
20
0.163
0.2044..uur
0.434 00.44:0.000 002
0.299
1.659 00006
40
0.174 00001
0.21221.uu0
0.986 40.002
0.543+0.0002
3.167 10.101
80
0.213 +
0.300-10.004
2.97644..01
2.09340.000
22.054440.017
160
0.512
0.778
11. 11.88610.155
38.747 10.247
OOM
320
1.500 098
2.841 +0.113
48.179400 17.17790.224
OOM
0OM
Table 6: Average inference/test time (s) random graph dataset over 10 epochs.
27

---

Published as a conference paper at ICLR 2024
B.7 ABLATION STUDY
One key component of SPE is to leverage eigenvalues using de( Here We try removing the use of eigenvalues, i.e., set (x) = 1 to see the difference. Mathematically, this will result in SPE(V, A) = p([VV V T IEe). This is pretty similar to PEG and we loss expressive power from this over-stable operation VV As shown in the table below, removing eigenvalue information leads to a dramatic drop of performance on ZINC-subset. Therefore, the processing of eigenvalues is an effective and necessary design in our method.
Method
Test MAE
SPE (Ør MLPSs) SPE (Ør = 0)
0.0693110 10.0040 0.123010.00
Table 7: Abalation study for SPE on ZINC (subset),
B.8 MORE RESULTS ON TUDATASETS
We further conduct experiments TUDatasets. For each task, we randomly split dataset into train- ing, validation and test by 8:1:1. We uniformly use batch size 128 and train 250 epoch. Architectures ZINC. We report the test accuracy the epoch with highest validation accuracy over 5 random seeds. See Table 8 for results.
and hyperparameters follows the same
GINE
EPG
SignNet
BasisNet
SPE
PROTEINS
21.07
70.71
43.27
63.5712.42
74.82
ENZYMES
51.33
57.00
45.00
32.00
52.34
PTC_MR
54.86=1101
+8.55
54.86+12.67
57. 57.14
58. 38.29+8.08
MUTUG
85.00 6.29
84.00 1750
85.00 :: 14.36
79.00 18.54
89.00 14.08
Table 8: Test accuracy over 5 random seeds TUDatasets.
C WHY PREVIOUS POSITIONAL ENCODINGS ARE UNSTABLE?
C.I ALL SIGN-INVARIANT METHODS ARE UNSTABLE
One line of work (Dwivedi & Bresson, 2021; Kreuzer et al., 2021; Lim al., 2023) is consider the sign ambiguity of each individual eigenvectors and aim to make positional encodings invariant to sign flipping. The underlying assumption is that eigenvalues are all distinct so eigenvectors are equivalent up to sign transformation. However, we are going to show that all these sign-invariant methods are unstable, regardless of the eigenvalues being distinct or not.
Firstly, suppose eigenvalues are distinct. Lemma 3.4 in Wang et al. (2022a) states that
Lemma C.I. For any positive semi-definite matrix B NNN without multiple eigenvalues, positional encoding PE(B) as the eigenvectors given by the smallest eigenvalues sorted as 0 = A1 < X2 < ... >xp >pt1) of B. For any suffciently small 0, there exists a perturbation AB, |B such that
min [|PE(B) PE(B + AB)| 2 0.99 max DA+11 -11 o SESN(P)
(133)
12:5P
where SN(p) = (Q RRXP: Q. +1, Qu, = 0.for f # j} is the flipping operations.
This Lemma shows that when there are two closed eigenvalues, a small perturbation to graph may still yield huge change of eigenvectors that cannot be compensated by sign flipping. Therefore, these sign-invariant methods are highly unstable on graphs with distinct but closed eigenvalues.
On the other hand, eigenvalues have repeated values, then the same graph may produce different eigenvectors that are associated by basis transformations. Simply invariant to sign flipping cannot
28

---

Published as a conference paper at ICLR 2024
[0:(A]
2.00
175
125
0.6
2 1.00
0.50
02
0.00
0.0
1.30
Au
Figure 4: illustration of [0] (A)]2 for = (A1, A2). Clearly Φ1 discontinuous.
handle this basis ambiguity. As result, these sign- ingnrinvrriant methods will produce different positional encodings for the same input graph. That means there is no stability gurantee for them at all.
C.2 BASISNET IS UNSTABLE
Another line of work (e.g, BasisNet (Lim et al., 2023)) further consider basis invariance of eigen- vectors by separately dealing with each eigensubspaces instead of each individual eigenvectors. The idea is to first partition eigenvectors V Raxd into their corresponding eigensubspace (V,, V2....) according to eigenvalues, where Ví E Rxxd is the eigenvectors in k-th eigensubspace of dimen- sion de. Then neural networks Φd, Raxa Tx is applied each V.VV and the output will be p(ós, (V da, (V2V2T) ...) where p ()) + Raxp is MLP. Intuitively, this method unstable because perturbation of graph
change the dimension of eigensubspace and thus dramatically change the input (V, V2..... As an example, let us say we have three eigenvectors (d 3), and denote the three columns of V uı, 02 ug- We construct graph A has A = X2 < Ag while the perturbed graph A' has Xj < X/2 < X/. Two graphs share the same eigenvectors. Note that the difference between and A' can be arbitrarily small to make X₂ little bit different from Az. BasisNet will produce the following embeddings:
graphs: the original
BasisNet( A) = p(02(uru + uzuz) oi (uzu3)
BasisNet(AA) p(0) (u Clearly as the input to p completly different, there is no way to ensure stability even if and are continuous.
u, ) oi (uzuz ), Φ2 (uzu)))
C.3 WHYY STABILITY THEOREM 3.1 CANNOT BE APPLIED FOR PREVIOUS METHODS
One may wonder why cannot prove the stability of previous hard-partition methods following the same argument Theorem 3.1. The reason is that they do not satisfy Assumption 3.1 or the requirement that is equivariant, both of which the key to prove stability result in Theorem 3.1.
To this, let us first consider sign-in invariatt methods (e.g., SignNet). Using the notation of SPE, it equivalent to use a (ee to separate the l-th eigenvectors, thus whose k-th entry is
[e)( = 6t.--
(134)
This ó function does not rely on À and thus is Lipschitz continuous. However, it is not permutation equivariant to vector. So it violates " is always permutation equivariant" as stated in the defini- tion of SPE, and thus cannot apply Theorem 3.1 sign-invariant methods (and they are indeed
29

---

Published as a conference paper at ICLR 2024
unstable shown before). On the other hand, let us consider (e.g., BasisNet). In this case, the k-tth entry of the hard partition @x(A) is
methods using hard partition of eigensubspaces
if As is f-th smallest eigenvalue
[de(
0, otherwise
This e function is actually discontinuous. As an example, we may consider A= (A1 A2) and plot the figure of [d] (A)]2 below. Clearly there is sharp transition from 0 to 1 when A2 approches Å1. Therefore, or(A) is more like a step function instead a constant function. They are discontinuous, and thus are not Lipschitz continuous. So Assumption 3.1 does not hold and Theorem 3.1 cannot be applied for such hard partition functions.
30


Reviews:
[{"review_id": "wKGTBbOHdK", "reviewer": "Reviewer_Fdup", "summary": "This works further deepens results on basis-invariant GNNs building on work of e.g. Wang et al (ICLR 2022) and Lim&Robinson et al (ICLR 2023). The authors propose a simple generalization of basis-net, with strong theoretical guarantees (Hölder-smoothness / stability and basis-invariance). They achieve strong performance in standard molecular benchmarks, out-of-distribution benchmarks and cycle count tasks.", "questions": "Please provide runtimes for your proposed method. Preferably for pre-processing and overall runtime. This would help to put the achieved results into context with basis-net, etc.\n\nWhile the OOD generalization bound is very interesting, can you also state a standard PAC-style generalization bound (same distribution for train and test)?\n\nDo you have a counter-example where SPE cannot count $k$-cycles for $k\\leq 6$?\n\nThe $n\\times n\\times m$ might be somewhat excessive for certain datasets. Would it be possible to exchange $V\\\\phi(\\cdot) V^T$ to $V^T\\phi(\\cdot) V^T$ to get the much smaller $d\\times d\\times m$ instead? If not what would this more compact model correspond to?\n\nIf I am notmistaken SPE and basis-net should have the same expressivity and thus at least theoretically be both equally capable of counting cycles etc. Can you provide some intuition why SPE performs significantly better than basis-net in this task (Figure 3)?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "Extremely well written and easy to follow. Figure 1 is nice!\n\nThe proposed model SPE (Eq. 2) is a simple generalization extension of basis-net. It is very interesting to see that such a straightforward modification yields such strong (and non-trivial) theoretical results (Theorem 1, etc.).\n\nEmpirical performance is very convincing, e.g. for Zinc and the OOD tests.\n\n------ during rebuttal ------\nas reviewers addressed my concerns and in fact added clarifications on runtime and more importantly on the unstability of previous methods I raised my score and now clearly vote for acceptance.", "weaknesses": "The achieved theoretical and empirical results, while very interesting, seem somewhat incremental compared to Wang et al (ICLR 2022) and Lim&Robinson et al (ICLR 2023). The authors should discuss the differences more clearly. In particular:\n* The reason for Hölder continuity ($c\\neq1$) is not fully clear. E.g. does PEG / standard basis-net already already satisfy your stability criterion Def 3.1 and / or Assumption 3.1.? If yes, what is the conceptual / theoretical benefit of your proposed architecture. If not, could you please provide an argument why the assumptions fail for PEG / basis-net.\n* Is $c\\neq 1$ crucial for any proof / guarantee / assumption? \n* Are there cases where SPE satisfies the stability assumption of Wang et al (ICLR 2022), i.e., with $c=1$?\n\nPlease see also the questions below.\n\nMinor:\n* Remark 3.1 Should probably be attributed to Wang et al (ICLR 2022), as they have the same statement for $c=1$.\n\nI am happy to raise my score, if the authors properly address my concerns and questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bdWYLwARw6", "reviewer": "Reviewer_fM7Q", "summary": "This paper proposes stable and expressive Laplacian positional encodings (SPE) by performing a soft and learnable partition of eigensubspaces. The encoding guarantees that small perturbations to the input Laplacian induce a small change to the final positional encodings. The empirical results suggest a trade-off between stability (correlated with better generalization) and expressive power.", "questions": "Please refer to my review.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The idea to address the stability of LapPE is novel, with SPE being a universal basis invariant architecture. \n- The motivation is well established, the difference to other related works is concise, the propositions are described well and the strength of SPE as a universal basis invariant architecture is presented thoroughly. \n- The experiments show the improvement in generalisation for SPE and its improved capabilities in recognising substructures, which are interesting outcomes of the architecture.", "weaknesses": "- The novelty of the method itself is partially limited as the idea to use a weighted correlation over the eigenvectors closely resembles the correlation used in BasisNet. \n- The experiments are limited. The performance of SPE in Table 1 is sub-par, and details of the experimental results in Figure 2 are unclear and the hyperparameters seem not to be reported, which makes it hard to reproduce the experiments. \n- The point regarding the trade-off between expressivity and generalisation is unclear. Is there a formal explanation which we can quantify? \n- Perhaps additional experiments could be useful, e.g.,:\n  - An experiment comparing the generalisation gap of LapPE/BasisNet/SPE.\n  - Evaluating the performance of LapPE/BasisNet/SPE on LRGB or TUDatasets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wKNS3L4lkD", "reviewer": "Reviewer_TVwL", "summary": "This paper introduces Stable and Expressive Positional Encodings (SPE), an architecture that mainly addresses the challenges of instability in using Laplacian eigenvectors as positional encodings for graph neural networks. The key insight to overcome instability is to avoid `hard partitions' of eigen-subspaces, and instead, use soft partitions via Lipshitz continuous functions over the spectrum. The stability of SPE is proved and validated via out-of-distribution generalization experiments.  Universal expressiveness is also proved, mainly based on another work, i.e., BasisNet.", "questions": "Please check W1, W2, and W3. Below is an additional question: \n\nQ1: Would the learned  $\\\\{\\phi_i\\\\}_{i=1}^{m}$ be close to each other? This would lead to similar position encodings.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- S1. I like the design of the experiment in that the authors validate the stability of SPEs from an aspect of out-of-distribution generalization.\n\n- S2. The authors target at robustness/instability and generalization of PEs, which is novel in the literature.\n\n- S3. The paper is overall well written.", "weaknesses": ">  W1. The instability of prior method (i.e., the so-called hard partition method) is not proved. \n\n The authors point out under Eq.2 that **hard partition** is induced when $\\[\\phi_{\\ell}(\\boldsymbol{\\lambda})\\]_j=\\mathbb{1}$(other places in $\\phi(\\cdot)$ are zeros), \n\nand then $\\boldsymbol{V}\\text{diag}(\\phi_{\\ell}(\\boldsymbol{\\lambda}))\\boldsymbol{V}^{T}$ is the $\\ell$-th subspace. \n\nThe problem is that, if we set $\\\\{ \\phi_i \\\\}_{i=1}^{m}$ that induce the hard partitions, \n\nthen they are **constant functions** and meet the $K_{\\ell}$-Lipschitz continuous assumption in Assumption 3.1, which is then used to prove the stability of SPE. \n\nTherefore, the question is,  **is the prior method (i.e., the counterpart that uses hard partitions) really unstable?** It seems that hard-partitioned SPE can be proved to be stable via exactly the same proof of Theorem 3.1.\n\n> W2. Equivalence for $\\\\{\\phi_i\\\\}_{i=1}^{m}$ .\n\nThe authors restrict $\\\\{\\phi_i\\\\}_{i=1}^{m}$ to be permutation equivariant, whose input is the Laplacian spectrum. Here, the authors are asking for equivalence under the reordering of eigenmaps/eigenvalues, instead of the reordering of graph nodes. \n\n> W3. On the universal expressiveness. \n\nThe proof of this SPE's universality relies on being reduced to BasisNet. Therefore, two problems arise: \n\n- The experiment regarding expressiveness, i.e., the graph substructure counting, does not include BasisNet.\n- According to Lim et al. (2023), the instance of BasisNet, Unconstrained-BasisNet, universally approximates any continuous basis invariant function. In Unconstrained-BasisNet,  IGN-2 (Maron et al., 2018) is the core part to achieve such expressiveness. However, in implementation, the authors set $\\rho$ to be one identical GIN (Xu et al., 2019),  which would surely limit the expressiveness. \n\n> W4. Lack of description of baseline models.\n\nFor the same reason as in W3, in the experimental part, specific choices of baseline instances, i.e.,  $\\rho$ and $\\phi$ of BasisNet, should be described more clearly.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HB5HEzVcb8", "reviewer": "Reviewer_qQbF", "summary": "This paper proposes a new approach for generating positional encodings which are stable and can universally approximate basis invariant functions. To compute those encodings, the method first decomposes the Laplacian matrix, it then applies different permutation equivariant functions to the eigenvalues, and uses the output of those layers to produce matrices of dimension $n \\times n$ which are then fed to another permutation equivariant network (e.g., a GNN). The proposed method is evaluated on molecular property prediction datasets and also on a dataset with domain shifts where it outperforms other positional encoding methods in most cases.", "questions": "In Figure 2, how did you compute the Lipschitz constant of MLPs? We can compute the Lipschitz constant for models that consist of a single layer, but exact computation of the Lipschitz constant of MLPs\nis NP-hard [1].\n\n[1] Virmaux, Aladin; Scaman, Kevin. Lipschitz regularity of deep neural networks: analysis and efficient estimation. Advances in Neural Information Processing Systems, 2018.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The stability of graph learning algorithms is a topic that has not been explored that much yet and deserves more attention from the community. The results presented in this paper contribute to this direction.\n\n- In my view, the paper has some value since several individuals from the graph learning community would be interested in knowing its findings. Practitioners would also be interested in utilizing the proposed encodings since in many settings, existing GNN models fail to generalize to unseen domains.\n\n- The proposed model achieves low values of MAE on the ZINC and Alchemy datasets and outperforms the baselines. This might be related to the model's ability to identify and count cycles of different lengths.", "weaknesses": "- I feel that the paper lacks some explanations. It is not clear which modules of the proposed method contribute to it being stable. If no $\\phi_\\ell$ layers are added, wouldn't $K_\\ell$ be equal to 1? In my understanding, this wouldn't hurt stability. Also, it seems to me that as $m$ increases the bound becomes looser and looser. If that's the case, why do we need multiple such permutation equivariant layers?\n\n- One of the main weaknesses of this paper is the proposed model's complexity. Function $\\rho$ takes a tensor of dimension $n \\times n \\times m$ as input. This might not be problematic in case the model is trained on molecules since molecules are small graphs. But in case of other types of graphs such as those extracted from social networks which are significantly larger, this can lead to memory issues.\n\n- The proposed approach is much more complex that a standard GNN model, but in most cases it provides minor improvements over a model that does not use positional encodings. For instance, the improvement on Alchemy is minor, and also on DrugOOD, SPE provides minor improvements in the Assay and Scaffold domains and no improvements in the Size domain.\n\n- No running times of the different models are reported in the paper. \n\n- The proposed model seems to advance the state of the art in the field of positional encodings for graphs, however, it is not clear whether it also advances the state of the art in the graph learning community. I would suggest the authors compare the proposed approach against some recently proposed GNN models, and not only against methods that produce positional encodings.\n\nTypos:\\\np.6: \"hold and Let\" -> \"hold and let\"\\\np.7: \"we take to $\\rho$ to be\" -> \"we take $\\rho$ to be\"\\\np.8: \"which hypothesizes is because\" -> \"which is because\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "L2j7GKiKUL", "reviewer": "Reviewer_mePj", "summary": "This paper studies the stability of eigenvector-based positional encodings while previous methods mainly focus on the sign- and basis-invariant properties. The authors claim that the instability of the previous method is caused by the hard partition of eigenvectors and the ignorance of eigenvalues. To address this challenge, this paper proposes SPE, which leverages the eigenvalues to re-weight the eigenvectors in a soft partition way. SPE is provably stable and shows great expressive power. Experiments on various tasks validate the superiority of the proposed method over baselines.", "questions": "Here are some concepts that I am not sure I fully understand. Please correct me if there are any misunderstandings.\n\n1. In equation (1), what does $\\mathbb{R}^{n \\times d} \\times \\mathbb{R}^d \\rightarrow \\mathbb{R}^{n \\times p}$ mean? I understand that $\\mathbb{R}^{n \\times d} \\rightarrow \\mathbb{R}^{n \\times p}$ represents the function applied to the position features of each node. What does $\\mathbb{R}^d$ indicate? Operation on eigenvalues?\n\n2. What is the difference between a hard partition and a soft partition?  I do not see a clear definition. Does hard partition indicate a fixed number of eigenvectors and does soft partition mean it can handle a variable number of eigenvectors?\n\n3. Is it possible to replace the element-wise MLPs of $\\phi$ with polynomial functions? In this situation, I think the complexity can be significantly reduced and the expressiveness can be preserved since polynomials are also non-linear.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed SPE is provably stable, which means that it can generalize to unseen graphs. I think this strong inductive learning ability is crucial for graph representation learning. The theoretical contribution is great.\n\n2. The proposed SPE shows great expressive power, which not only universally approximates previous basis invariant functions but also can distinguish the cycles in graphs. Experimental results validate the effectiveness of the proposed method.\n\n3. In addition to previous methods that conduct experiments in the basic molecular property prediction tasks, this paper also considers a more challenging out-of-distribution (OOD) task for evaluation.", "weaknesses": "1. The complexity of the proposed SPE is much larger than previous positional encoding methods because it needs to reconstruct graph structures, i.e., $\\boldsymbol{V} \\operatorname{diag}\\left(\\phi(\\boldsymbol{\\lambda})\\right) \\boldsymbol{V}^{\\top}$, whose complexity is $\\mathcal{O}(KN^{2})$. In contrast, the Transformer-based methods, e.g., BasisNet, only have the complexity of $\\mathcal{O}(NK^{2})$, where $K \\ll N$.\n\n2. In the molecular property prediction task, SPE has more parameters than baselines. It would be better if the authors could align the number of parameters across different methods. Additionally, in the OOD tasks, the improvement of SPE over baselines is marginal.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)