Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networks
Authors: Haorui Wang
Haoteng Yin
Muhan Zhang
Pan Li
Venue: ICLR 2022 Poster (2022)
Keywords: Graph Neural Network
Spectral Graph Theory
System Stability

Abstract: Graph neural networks (GNN) have shown great advantages in many graph-based learning tasks but often fail to predict accurately for a task-based on sets of nodes such as link/motif prediction and so on.  Many works have recently proposed to address this problem by using random node features or node distance features. However, they suffer from either slow convergence, inaccurate prediction, or high complexity. In this work, we revisit GNNs that allow using positional features of nodes given by positional encoding (PE) techniques such as Laplacian Eigenmap, Deepwalk, etc. GNNs with PE often get criticized because they are not generalizable to unseen graphs (inductive) or stable.  Here, we study these issues in a principled way and propose a provable solution, a class of GNN layers termed PEG with rigorous mathematical analysis. PEG uses separate channels to update the original node features and positional features. PEG imposes permutation equivariance w.r.t. the original node features and rotation equivariance w.r.t. the positional features simultaneously. Extensive link prediction experiments over 8 real-world networks demonstrate the advantages of PEG in generalization and scalability. Code is available at https://github.com/Graph-COM/PEG.

Published as a conference paper at ICLR 2022
EQUIVARIANT AND STABLE POSITIONAL ENCODING FOR MORE POWERFUL GRAPH NEURAL NETWORKS
Haorui Wang' Haoteng Yin", Muhan Zhang*,, Pan Li
1 School of Computer Science, Wuhan University
2 *Department of Computer Science. Purdue University 3 Institute for Artificial Intelligence, Peking University, & "BIGAI
[r__wan@eee @whu. edu, en, muhan@@uu.. edu. cn, (yinht, panlil i 8purdue edu
ABSTRACT
Graph neural networks (GNN) have shown great advantages in many sraph-based learning tasks but often fail to predict accurately for task based on sets of nodes such as link/motif prediction and so on. Many works have recently proposed address this problem by using random node features or node distance features. However, they suffer from either slow convergence, inaccurate prediction or high complexity. In this work, we revisit GNNs that allow using positional features of nodes given by positional encoding (PE) techniques such as Laplacian Eigenmap, Deepwalk, etc.. GNNs with PE often get criticized because they are not gener- alizable to unseen graphs (inductive) or stable. Here, we study these issues in a principled way and propose provable solution, class of GNN layers termed PEG with rigorous mathematical analysis. PEG uses separate channels to update the original node features and positional features. PEG imposes permutation equivari- ance w.r.t. the original node features and rotation equivariance w.r.t. the positional features simultaneously. Extensive link prediction experiments over real-world networks demonstrate the advantages of PEG in generalization and scalability!
INTRODUCTION
Graph neural networks (GNN), inheriting from the power of neural networks (Hornik et al. 1989), ). have recently become the de facto standard for machine learning with stuhh-strutturd data (Scarselli al.] 2008). While GNNs can easily outperform traditional algorithms for single-node tasks (such as node classification) and whole graph tasks (such as graph classification), GNNs predicting over a set of nodes often achieve subpar performance. For example, for link prediction, GNN models, such as GCN (Kipf & Welling 2017). GAE (Kipf & Welling 2016 may perform even worse than some simple heuristics such as common neighbors and Adamic Adar
& Kleinberg 2007) (see the performance comparison over the networks Collab and PPA in Open Graph Benchmark (OGB) (Hu et al.. ).20). Similar issues widely appear in node-set-based tasks such network
motif prediction (Liu et al. 2022 Besta et al., (021). motif counting (Chen et al. (2020). relation prediction (Wang et 202 Teru et al. 2020) and temporal interaction prediction (Wang et al.
2021b), which posts a big concern for applying GNNs to these relevant real- real-world applications.
The above failure is essentially induced by the loss of node identities during the intrinsic computation of GNNs. Nodes that get matched under graph automorphism will be associated with the same representation by GNNs and thus are indistinguishable (see Fig. ii). A naive way to solve this problem is to pair GNNs with one-hot encoding as the extra node feature. However, it violates the fundamental inductive bias, i.e., permutation equivariance which GNNs are designed for, and thus may lead to poor generalization capability: The obtained GNNs are not transferable (inductive) across different node sets and different graphs or stable to network perturbation.
Many works have been recently proposed to address such an issue. The key idea is to use augmented node features, where either random features (RF) or deterministic distance encoding (DE) can be adopted. Interested readers may refer the book chapter (Li & Leskovec) 2021) for detailed discussion. Here we give a brief review. RF by nature distinguishes nodes and guarantees permutation equivariance if the distribution generate RF keep invariant across the nodes. Although GNNs paired with RF have been proved to be more expressive (Murphy et al.) 20119] Sato et al. 2021). the training procedure is often hard converge and the prediction is noisy and inaccurate due to the
Wang was an intern at Purdue University when doing this project.
Code available whhttps: httpps////hhhii chub.

---

Published as a conference paper at ICLR 2022
(-03990.5)
(0.39.0.5)
Rotation
original features
Us
equavoriance
(-045,000)
(0 (0.45,0.0)
Positional
32
Encoding
(0.30 0.5)
(10)
Figure 1: Illustration of Positional Encoding (PE): (i) GNNs cannot distinguish nodes a.b. because the graph has automorphism where is mapped to b, c, d. GNNs fail to predict whether (a.b) or (a.d) is more likely to have a link; (ii) PE associates each node with extra positional features that may distinguish nodes; (iii) An example of PE uses the cigenvectors that correspond to the 2nd and 3rd smallest eigenvalues of the graph Laplacian as positional features (denoted as the 2-dim vectors besides cach node). The proposed GNN layer PEG keeps rotation equivariance when processing these features.
injected randomness (Abboud et al. 2020). On the other hand, DE defines extra features by using the distance from a node to the node set where the prediction is to be made (Li et al. 2020). This technique theoretically sound and empirically performs well (Zhang & Chen 2018
et al. 2020,
Zhang et al., 2020). But it introduces huge memory and time consumption. This is because DE is specific to each node set sample and no intermediate computational results, e.g., node representations in the canonical GNN pipeline can be shared across different samples.
To alleviate the computational cost of DE, absolute positions of nodes in the graph may be used as the extra features. We call this technique positional encoding (PE). PE may approximate DE by measuring the distance between positional features and can be shared across different node set samples. However, the fundamental challenge is how to guarantee the GNNs trained with PE keep permutation equivariant and stable. Using the idea of RF, previous works randomize PE to guarantee permutation equivariance. Specifically, You et al. (2019) designs PE as the distances from a node to some randomly selected anchor nodes. However, the approach suffers from slow convergence and achieves merely subpar performance. [Srinivasan & Ribeero (2020) states that PE using the eigenvectors of the randomly permuted graph Laplacian matrix keeps permutation cquivariant. Dwivedi & Bresson (020); Kreuzer et al. (2021) argue that such eigenvectors are unique up to their signs and thus propose PE that randomly perturbs the signs of those eigenvectors. Unfortunately, these methods may have risks. They cannot provide permutation equivariant GNNs when the matrix has multiple eigenvalues, which thus are dangerous when applying to many practical networks. For example, large social networks, when not connected, have multiple O eigenvalues; small molecule networks often have non-trivial automorphism that may give multiple eigenvalues. Even if the cigenvalues are distinct, these methods are unstable. We prove that the sensitivity of node representations to the graph perturbation depends on the inverse of the smallest gap between two consecutive eigenvalues, which could be actually large when two eigenvalues are close (Lemma 3.4..
In this work, propose a principled way of using PE to build more powerful GNNs. The key idea is to use separate channels to update the original node features and positional features. The GNN architecture keeps not only permutation equivariant w.r.l. node features but also rotation equivariant w.rl. positional features. This idea applies to a broad range of PE techniques that can be formulated matrix factorization (Qiu et al. (2018) such as Laplacian Eigenmap (LE)) (Belkin & Niyogi 2003) and Deepwalk (Perozzi et al. 22044). We design a GNN layer PEG that satisties such requirements. PEG is provably stable: In particular, we prove that the sensitivity of node representations learnt by PEG only depends on the gap between the pth and (p + jth eigenvalues of the graph Laplacian if p-dim LE adopted as PE, instead of the smallest gap between any two consecutive eigenvalues that previous works have achieved.
PEG gets evaluated in the most important node-set-based task, link prediction, over 8 real-world networks. PEG achieves comparable performance with strong baselines based on DE while having much lower training and inference complexity. PEG achieves significantly better performance than other baselines without using DE. Such performance gaps get enlarged when we conduct domain-shiff link prediction, where the networks used for training and testing are from different domains, which effectively demonstrates the strong generalization and transferability of PEG.
1.1 OTHER RELATED WORKS
As long as GNNs can be explained by a node-feature-refinee Gilmer et al. 2017 Morris et al.) 2019 Veličković et al. 2018) Klicpera et al. 2019 Chien et al. 2021), they suffer from the aforementioned node ambiguity issue. Some GNNs cannot be explained as feature refinement as they directly track node-set representations (Maron et al. 2019b Morris
procedure (Hamilton et al. 2017
2

---

Published as a conference paper at ICLR 2022
al. 2019 Chen et al., 2019 Maron al. 2019a). However, their complexity is high, as they need to compute the representation of each node set of certain size. Moreover, they were only studied for graph-level tasks. EGNN (Satorras et al. 2021 seems to be relevant work as it studies when the nodes have physical coordinates given in prior. However, no analysis of PE has been provided.
A few works studied the stability of GNNs by using tools like graph scattering transform (for graph-level representation) (aaa et al. 2019a b) and graph signal filtering (for node-level represen-
tations) (Levie al. 2021| Ruiz et al. 2020 2021 Gama al. 2020; Nilsson & Bresson 2020).
They all focus on justifying the stability of the canonical GNN pipeline, graph convolution layers in particular. None of them consider positional features let alone the stability of GNNs using PE.
NOTATIONS AND PRELIMINARIES
In this section, we prepare the notations and preliminaries that are useful later. First, we define graphs. Definition 2.1 (Graph), Unless specified, we always consider undirected graphs of N nodes and let [N] = {1, 2......... N.. One such graph can be denoted as g = (A, X)), where A is the adjacency matrix. X E NxF denotes the node features, where the uth row, X5, is the feature vector of node v. A graph may have self loops, i.e., A has nonzero diagonals. Denote D as the diagonal degree matrix where Dev = Ene[N] Ava for U E [N]. Let dmax = max,ejN] Dev. Denote the normalized Á.
adjacency matrix as Å D- AAD and the normalized Laplacian matrix as L. Definition 2.2 (Permutation). An --mim permutation matrix P is a matrix in {0, 1]Nx where each row and each column has only one single 1. All such matrices are collected in IT(N), simplified TT.
We denote the vector f--nrrm as || ||, the Frohenius norm as || ||r and the operator norm as || llop- Definition 2.3 (Graph-matching). Given two graphs g( (A(1) x()) and their normalized
Laplacian matrices (t) for i {1,2), their matching can be denoted by permutation matrix P E II that best aligns the graph structures and the node features.
('(()), g( e arg min (I] PL ( | + [Xx - 1X
PETT
Using L instead of A to represent graph structures is for notational simplicity. Actually for an unweighted graph, there is bijective mapping between L and A. One can rewrite the first term with A. Later, we use P by not specifying 9n and G2 if there is no confusion. The distance between the two graphs can be defined as d(G), G2) = -I(( P* (() pa
F + [ - P* p"x II
Next, we review eigenvalue decomposition and summarize arguments on its uniqueness in Lemma 2.6 Definition 2.4 (Eigenvalue Decomposition (EVD)). For a positive semidefinite (PSD) matrix B E NNN, it has eigenvalue decomposition B UAUT where is real diagonal matrix with the eigenvalues of B, 0 < x I X2 < < An as its diagonal components. U = [uI, W2, ..., uN] is an orthogonal matrix where u, E R the ith eigenvector, i.e. Bug ApU4.
Definition 2.5 (Orthogonal Group in the Euclidean space). SO(k) = (Q E B QQ" = Q"QQ /} includes all k-by-k orthogonal matrices. A subgroup of SO includes all diagonal matrices with +1 as the diagonal components, SN(k) = (Q E R Qu E (1,, 13,1,1112 Qi = 0, for + j}.
Lemma 2.6. EVD is not unique. If all the eigenvalues are distinct, i.e., X + >y.. U is unique up to the signs of its columns, i.e., replacing u, by -u; also gives EVD. If there are multiple eigenvalues, say (A,-1 <)>; A4+1 ... \++*-1(< {+(+), then [u, U441 u++&-1] 1] lie in an orbit induced by the orthogonal group SO(K), i.e., replacing [i4, Us+1. 1 by [Mt, u4+1, 4 1 for any Q sO(k) while keeping eigenvalues and other eigenvectors unchanged also gives EVD.
Next, we define Positional Encoding (PE), which associates each node with a vector in a metric space where the distance between two vectors can represent the distance between the nodes in the graph. Definition 2.7 (Positional Encoding). Given graph g X). PE works on A and gives Z = (E(A)
E IR Xx where each row Z, gives the positional feature of node U.
The absolute values given by PE may not be useful while the distances between the positional features are more relevant. So, we define metchiiging that allows rotation to best match positional features, which further defines the distance between two collections of positional features.
Definition 2.8 (PE- (PE-matching). Consider two groups of positional features ( (2) E Xx,, Their matching is given by (Z((11) 2 A arg minl (1) 2(1) Later, Q" is used if it causes no confusion. Define the distance between them as (2(2), 2(2)) = 1 - 2(2)
3

---

Published as a conference paper at ICLR 2022
Chesser
Citesoor
Twithh/PT)
TwachiPT)
Figure 2: Eigenvalues Ap and the stability ratio Pp
AAp Aptal
PEG with sensitivity [Ap >
gisg Dy A
is far more stable than previous methods with sensitivity maXisks) Ax A 1__ Over Citeseer, Pp is extremely large hecause there are multiple eigenvalues (pp is still finite due to the numerical approximation of the eigenvalues). Over TWitch(PT), even if there are no multiple eigenvalues, Pp is mostly larger than 10.
3
EQUIVARIANT AND STABLE POSITIONAL ENCODING FOR GNN
In this section, we will study the equivariance and stability of a GNN layer using PE
3.1 OUR GOAL: BUILDING PERMUTATION EQUIVARIANT AND STABLE GNN LAYERS
A GNN layer is expected to be permutation equivariant and stable. These two properties, if satisfied, guarantee that the GNN layer is transferable and has better generalization performance. Permutation equivariance implies that model predictions should be irrelevant to how one indexes the nodes, which captures the fundamental inductive bias of many graph learning problems: A permutation equivariant layer can make the same prediction over a new testing graph that over training graph if the two graphs match each other perfectly, i.e. the distance between them is O. Stability is actually an even stronger condition than permutation equivariance because it characterizes how much gap between the predictions of the two graphs is expected when they do not perfectly match each other.
Specifically, given a graph A with node features X, we consider a GNN layer 9 updating the node features, denoted X 0(4, We define permutation equivariance and stability as follows.
Definition 3.1 (Permutation Equivariance). A GNN layer ğ is permutation equivariant, if for any P E 1I and any graph G = (A, X), P?(A, = g(PAPT ,P)).
Definition 3.2 (Stability). A GNN layer ğ is claimed to be stable, if there exists constant C > for any two graphs g(1) (A(2), X (1) and (( (A(2), x(2)), letting P ((gg),ga)
denote their matching, 9 satisfies llğ (A))) (x()))))))))))))) PP))(A(3) xx Cd(g g(2)). By setting A (2) pT and (1) PX (2) for some P 11, the RHS becomes zero, so a stable makes the LHS zero too. So, stability is a stronger condition than permutation equivariance.
Our goal is guarantee that the GNN layer that utilizes PE is permutation equivariant and stable. To distinguish from the GNN layer I that does not use PE, we use to denote a GNN layer that uses PE, which takes the positional features Z as one input and may update both node features X and Z, i.e. (X, 2) (AA, Z). Now, we may define PE-equivariance and PE-stability for the GNN layer g. Definition 3.3 (PE-stability & PF-equivariance). Consider GNN layer g that uses PE. When it works on any two graphs g (A X (9), i E {1, 2) and gives (X (0, 20)) ((A()) X00 2()), let pa be the matching between the two graphs. g is PE-stable, if for some constant C we have
|}())) p* X + (2(1), p 22)) Cd(g()) g(()))
Recall n(s))) measures the distance between two sets of positional features as defined in Def. 2.8 Similar as above, a weaker condition of PE-stability is PE-equivariance: If A(1) P (2 and ( = (2) for some P ПI, expect a perfect match between the updated node features and positional features, (1) X and (1)11), (2(2)) 0.
Note that previous works also consider that updates only node features, i.c., X = (A, 2). In this case, PE-stability can be measured by removing the second term on 2 from Eq
3.2 PE-STABLE GNN LAYERS BASED ON LAPLACIAN EIGENMAP AS POSITIONAL ENCODING
To study the requirement of the GNN layer that achieves PE-stability, let us start from a particular PE technique, i.e., Laplacian eigenmap (LE) (Belkin & Niyogil 2003) to show the key insight behind. Later, we generalize the concept to some other PE. Let 2,, denote LE, which includes the eigenvectors that correspond to the p smallest eigenvalues of the normalized Laplacian matrix T..
4

---

Published as a conference paper at ICLR 2022
Previous works failed to design PE-equivariant PE-stable GNN layers. Srinivasan & Ribeiro (2020) claims that if a GNN layer 9(A,X) X) that does not rely on PE is permutation equivariant, PE-cquivariance may be kept by adding ZL to node features, i.c., g A(A.X, LI.) 9A Ml.P(ZLE)). where MI.((.) is a multilayer perceptron that adjusts the dimension properly. This statement is problematic when ZLÆ is not unique given the graph structure A. Specifically, though sharing graph structure A()) = A(2), if different implementations lead to different LEs ZL-E + 2 then ((A (1) MLP Z (1) A ((A ( + MLP MLP(Z),)) which violates PE-equivariance. Srinivasan & Ribeiro (2000) suggests using graph permutation augmentation to address the issue, which makes assumptions on an invariant distribution of LE that may not be guaranteed empirically,
Dwivedi & Bresson (2020); Kreuzer et al. (2021) claim the uniqueness of ZLE up to the signs and suggest building GNN layer that uses random EE as g(A, X, ZLæ)
İ(A, X + MLP(ZLES)) where S is uniformly at random sampled from SN(p). They expect PE-equivariance in the sense of expectation. However, this statement is generally incorrect because it depends on the condition that all eigenvalues have to be distinct as stated in Lemma [.6] Actually, for multiple eigenvalues, there are infinitely many eigenvectors that lie in the orbit induced by the orthogonal group. Although many real graphs have multiple eigenvalues such as disconnected graphs or graphs with some non-trivial automophism, one may argue that the methods work when the eigenvalues are all distinct. However, the above failure may further yield PE-instability even when the eigenvalues are distinct but have small gaps due to the following lemma.
Lemma 3.4. For any PSD matrix B E TRNN without multiple eigenvalues, set positional encoding PE(B) the eigenvectors given by the smallest p eigenvalues sorted as 0 = >1 X2 < ... < Xp
Ap+1) of B. For any sufficiently small e > 0, there exists a perturbation A B. || BlF S such that
min SESN(p)
[PE(B) - PE((B + A 2 0.99 max A4+1 - A I | |F + o(e).
(2)
1SiSP
Lemma LLemma..4jjmppa 3.4jimllies that small perturbation of graph structures may yield a big change of eigenvectors
if there is a small eigengap. Consider two graphs g(2) = (A(), x(1) and g(2) = (A x(1), where (1) x() and (2) is (1)) with small perturbation AA(1) The perturbation is small enough so that the matching P* (*(((), g(2)) = I. However, the change of PE even after removing the effect of changing signs minsesN(p) ||PE(A()) PE(A(2))S)) could be dominated by the largest inverse eigengap among the first p + 1 eigenvalues max D A practice, it is hard to guarantee all these eigenpairs have large gaps, especially when a large p is used to locate each node more accurately. Plugging this PE into GNN layer gives the updated node features (+) large change (I - (2)r and thus violates PE-stability.
PE-stable GNN layers. Although a particular eigenvector may be not stable, the eigenspace, i.c., the space spanned by the columns of PE(A) could be much more stable. This motivates our following design of the PE-stable GNN layers. Formally, we use the following lemma that can characterize the distance between the eigenspaces spanned by LEs of two graph Laplacians. The error is controlled by
the inverse eigengap between the pth and (p + 1)th eigenvalues min;=1.2((1] - (1) 1- which
by properly setting p is typically much smaller than maxiskáp [A - A in Lemma 3.4 We
compute the ratio between these two values over some real-world graphs as shown in Fig. 2
Lemma 3.5. For two PSD matrices B(1, B(2) e NNN, set PE(B) as the eigenvectors given by
the p smallest eigenvalues of B. Suppose ((6) has eigenvalues 0 = x(r) < (6) < ... S
x (5) (i)
and 8 = 1min;_1.2(()))
(6) - < x.. Then, for any permutation matrix e
7 (PE(B()), (PE(B( < 2 ( PB(2) 1T [b - P
(3)
Inspired by the stability of the eigenspace, the idea to achieve PE-stability is to make the GNN layer invariant to the selection of bases of the eigenspace for the positional features. So, our proposed PE- stable GNN layer g that uses PE should satisfy two necessary conditions: 1) Permutation equivariance w.r.t. all features; 2) Rotation equivariance w.r.t. positional features, i.e.,
PF-stable layer cond. 1:
(PX, PÝ) = g(PAPT PX, PZ), VP &PEN(N ITN),,
(4)
PE-stable layer cond. 2: (X, (Q) ((A,x, ZQ), AQ E SO(p).
(5)
5

---

Published as a conference paper at ICLR 2022
Rotation equivariance reflects the eigenspace instead of particular selection of eigenvectors and thus achieves much better stability. Interestingly, these requirements can be satisfied by EGNN recently proposed (Satorras et al., 2021) as can view the physical coordinates of objects considered by
EGNN as the positional features. EGNN gets briefly reviewed in Appendix Thm. 3.6 proves PE-equivariance under the conditions Eqs. 5
Theorem 3.6. A GNN layer g(A, X, 2) that uses Z = ZI.F and satisfies Eqs. 4 is PE-equivariant the yth and (p + 1 )th eigenvalues of the normalized Laplacian matrix L. are different, i.e., Ap * Ap+1-
Note that satisfying Eqs. 45 is insufficient to guarantee PE-stability that depends on the form of g.
We implement 9 in our model PEGN with further simplification which has already achieved good empirical performance: Use GCN layer with edge weights according the distance between the end nodes of the edge and keep the positional features unchanged. This gives the PEG layer.
PEG: (A, 2) = & [(Ao=) XW] 2). where E..- Zl. Z. II). Vu, [N]
(6) Here t is an clement-wise activation function, Φ is an MLP mapping from IR - R and @ is the Hadamard product. Note that if Å is sparse, only Eue for an edge we needs to be computed.
We may also prove that the PEG layer OPeG satisfies the even stronger condition PE-stability.
Theorem 3.7. Consider two graphs g(+) (A x()) i 1, 2. Denote their normalized Laplacian matrices' pth eigenvalue as A and (p+ 1)th eigenvalue X Assume that 8 = min;=
) < co. Also, assume that v and @ in the PEG layer in Eq. 6 are Lup. L--Lipschitz continuous respectively. Then, the PEG layer that uses Z ZLE satisfies PE-stability with the constant C' in Eq. as C = (1) + 2d ) l [ lop + 36].
Note that to achieve PE-stability, we need to normalize the node initial features to keep | llop bounded, and control |[]|lap and la- In practice by S is typically satisfied, e-g. setting as ReLUU. Here, the most important term is ö. PE-stability may only be achieved when there is an eigengap between X, and Ap+1 and the larger eigengap, the more stable. This observation may be also instructive to select the p in practice. As previous works may encounter smaller eigengap (Lemma 3.4), their models will be generally more unstable.
Also, the simplified form of (PFG is not necessary to achieve PE-stability. However, as it has already given consistently better empirical performance than baselines, we choose to keep using JPEG-
3.3
GENERALIZED TO OTHER PE TECHNIQUES: DEEPWALK AND LINE
is well known that LE, as compute the smallest eigenvalues, can be written as low-rank matrix optimization form ZLE E arg min Z tr Lx Z ), s.t. 7. 7 T. Other PE techniques, such as Deepwalk (Perozzi et al. 2014), Node2vec (Grover & Leskovec 2016) and LINE (Tang et al. (015) can be unified into a similar optimization form, where the positional features Z are given by matrix factorization M z'z" (MI may be asymmetric so Z' E I Nxx may not be 2) and M satisfies
M = arg min (pE(A, (A))(() + (D)g(- s.t. rank (M) S (7)
MERNXN
typically revises A by combining degree normalization and a power series of A. f-(:) NNN + B corresponds to edge negative sampling that may be related to node degrees, and g(-) is component-wise log-sigmoid function x - log(1 +exp(x)). E.g. in LINE, (4) A, f- (D) T Dē, for some positive constant where 1 is the all-one vector. More discussion on Eq and the forms of f+ and f- for other PE techniques are given in Appendix C
Here f4()) NNN + R N
According to the above optimization formulation of PE, all the PE techniques generate positional features Z based on matrix factorization, thus are not unique. Z always lies the orbit induced by SO(p), i.e., if Z solves Eq 7 ZQ for Q E SO(p) solves it too. A GNN layer y still needs to satisfy Eqs. 5 to guarantee PE-equivariance. PE-stability actually asks even more.
Theorem 3.8. Consider general PE(A) technique that has optimization objective as Eq computes its optimal solution M and decomposes M = Z'zT. s.t. zTZ = E RPXP to get positional features Z. Essentially, Z consists of the right-singular vectors of M If Eq has unique solution M rank(M = and f- therein satisfy f+ (PAPT) Pf. (A) PT and
f- (PDPP") Pf- (D)P then GNN layer (A, X, Z) that satisfies Eqs. 4 is PE-equivariant.

---

Published as a conference paper at ICLR 2022
Note that the conditions on f+ and f- are generally satisfied by Deepwalk, Node2vec and LINE. However, solving 7 to get the optimal solution may not be guaranteed in practice because the low-rank constraint is non-convex. One may consider relaxing the low-rank constraint into the nuclear norm || ك r for some threshold T (Recht et al., 2010), which reduces the optimization Eq 7 into convex optimization and thus satisfies the conditions in Thm. Th.. Empirically, this step and the step of computing SVD seem unnecessary according to our experiments. The PE-stability is related to the value of the smallest non-zero singular value of M'. We leave the full characterization of PE-equivariance and PE-stability for the general PE techniques for the future study.
4 EXPERIMENTS
In this work, use the most important mude-set-basee task link prediction evaluate PEG, though it may apply to more general tasks. Two types of link prediction tasks are investigated: traditional link prediction (Task 1) and domain-shift link prediction (Task 2). In Task 1, the model gets trained, validated and tested over the same graphs while using different link sets. In Task 2, the graph used for training/valicon validation is different from the one used for testing. Both tasks may reflect the effectiveness of model while Task 2 may better demonstrate the model's generalization capability that strongly depends on permutation equivariance and stability. All the results are based on 10 times random tests.
4.1 THE EXPERIMENTAL PIPELINE OF PEG FOR LINK PREDICTION
We use PEG build GNNs. The pipeline contains three steps. First, we adopt certain PE techniques to compute positional features Z. Second, we stack PEG layers according to Eq. 6 Suppose the final node representations are denoted by (X, 2). Third, for link prediction over (u, v),, we concatenate (Xx.T. Z,ZZ,) denoted as Huv and adopt MLP(H ) to make final predictions. In the experiments, we test LE and Deepwalk as PE, and name the models PEG-LE and PEG-DW respectively. To verify the wide applicability of our theory, we also apply PEG Graph AAGE Hammlton et al.. (2017) by similarly using the distance between PEs to control the neighbor aggregation according to Eq. 6 and term the corresponding models PE-SAGE-LE and PE-SAGE-DW respectively.
For some graphs, especially those small ones where the union of link sets for training, validation and testing cover the entire graph, the model may overfit positional features and hold large generalization gap. This is because the links used as labels to supervise the model training are also used to generate positional features. To avoid this issue, we consider a more elegant way to use the training links. We adopt a 10-fold partition of the training set. For each epoch, we periodically pick one fold of the links to supervise the model while using the rest links to compute positional features. Note that PEs for different folds can be pre-computed by removing every fold of links, which reduces computational overhead. In practice, the testing stage often corresponds to online service and has stricter time constraints. Such partition is not needed so there is computational overhead for testing. We term the models trained in this way as PEG-LE+ and PEG-DW+ respectively.
4.2 TASK - TRADITIONAL LINK PREDICTION
Datasets. We use eight real graphs, including Cora, CiteSeer and Pubmed (Sen et al. 2008), Twitch (RU), Twitch (PT) and Chameleon (Rozemberezki et al. I), DDI and COLLAB (Hu et al. 2021). Over the first 6 graphs, we utilize 85%, 5%, 10% to partition the link set that gives positive examples for training, validation and testing and pair them with the same numbers of negative examples (missing edges). For the two OGB graphs, we adopt the dataset splits in (Hu et al.) 2020).. The links for validation and test are removed during the training stage and the links for validation are also not used in the test stage. All the models are trained till the loss converges and the models with the best validation performance is used to test.
Baselines. We choose 6 baselines: VGAE (Kipf & Welling 2016), P-GNN You et al. 2019), SEAL
(Zhang & Chen 2018). GNN Trans. (Dwivedi & Bresson 2020). LE (Belkin& & Niyogi, 2003) and Deepwalk (DW) (Perozzi et al. 2014). VGAE is a variational version of GAE (Kipl & Welling 2016) that utilizes GCN to encode both the structural information and node feature information, and then decode the node embeddings to reconstruct the graph adjacency matrix. SEAL is particularly designed for link prediction by using enclosing subgraph representations of target node-pairs. P-GNN randomly chooses some anchor nodes and aggregates only from these anchor nodes. GNN Trans. adopts LE as PE and merges LE into node features and utilizes attention mechanism to aggregate information from neighbor nodes. For VGAE, P-GNN and GNN Trans., the inner product of two node embeddings is adopted to represent links. LE and DW are two network embedding methods, where the obtained node embeddings are already positional features and directly used predict links.
7

---

Published as a conference paper at ICLR 2022
Table Performance on the traditional link prediction tasks, measured in ROC AUC (mean=tstd%)
Method
Feature
Cora
Ciesserr
Puhmed
Twitch-RU
Twitch-PT
Chameleon
N.
89,89 + 0.06
90.11 = 0.08
94,62 0 0.02
83.13 # 0.07
82.89 # 0.08
97.98 = 0.01
C.
55.68 0.05
61.45 0.36
69.03
85.37 0.02
85,69 0.09
83.13
O.
83.97 + 0.05
77.22 = 0.04
02.04
84,76 0.09
87.91 + 0.05
97.67 = 0.04
VGAE
P.
83,82 a: 0.12
78.68 0.25
0.17
85.06 0.14
85.06 a 0.14
97.91 +: 0.03
R.
68.43 a 0.42
71.21 0.78
6.231
6.44
68.49 0.73
73.44
N. P.
87.96 +: 0.29
80.04 a 0.60
85.26 0.17
84,59 a 0.37
88.27 a 0.19
98.01 + 0.12
PONN
N. P
N6.92 + 0.02
90.26 + 0.02
88.12 + 0.06
83.21
0.000
82.37 * 0.02
94,25 + 0.01
GNN-Trans.
N.
79.31
77.49
81.23 0.12
79.24 0.33
75.44 0.14
86.23 + 0.12
SEAL
N. D.
91.32 a: 0.91
89,49 0.43
97.16 0.28
92.12
0.10
93.21 0.06
99.31 0.18'
LE
P.
84.43 + 0.012
78.36 = 0.08
84.35 14.35=00000 0.04
78,80 + 0.10
67.56 * 0.02
88.47 = 0.03
DW
86.82 + 0.18
87.93 0.11
85.79 0.06
83.10 0.05
83,47 = 0.03
92.15 0.02
PEG-DW
N.
89.51 = 0.08
91.670.11
0.229
90.21 0.04
89.67 0.03
98.33 0.01
PEG-DW
C. P.
88.36 + 0.10
88 38 0.10
88.80 + 0.11
90.32 0.09
90.88 + 0.05
97.30 0.03
PEG-LE
N. P.
94.20 + 0.04
92.53 = 0.09
87.70 + 0.31
92.14 0.05
92.28 + 0.02
98. + 0.02
PEG-LE
C. P..
86.88
76.96
0.02
91.15 0.13
98.73 +
PEG-DW+
N. P.
93.32 + 0.08
94.11 0.14
97.88 0.05
91.68 0.01
92.15 + 0.02
98.20 0.01
PEG-DW+
C. P.
90.78 + 0.09
91.22 = 0.12
93.44 + 0.05
90.22 # 0.04
91.37 = 0.05
97.50 0.03
PEG-LE++
N. P.
93.78 + 0.033
95.73 = 0.091
97.92 + 0.11
92.29 + 0.11
92.37 * 0.06
98.18-2 + 0.02
PEG-LE+
C.
88.98 + 0.14
78.61 0.27
94.28 0.05
92.35 + 0.02
92.50 + 0.06
97.79 + 0.01
Table 2: Performance on OGB datasets, measured in Hi and Ho (tdd)))-sd%). Codes are run on CPU: Intel(R) Xeon(R) Gold 6248R @ 3.00GHZ and GPU: NVIDIA QUADRO RTX 6000.
Method
ogbi-ddi (Hin))2(3))
ogbi-collab (0())))0(3))
training time
test time
Validution
test
training time
lest time
Validation
rest
GCN
29min 27s
0.200s
55.27
37.11
1h38min177
1.38%
$2.71
0.01
GraphS.AE
1mmin 26s
0.24s
67.11 1.21
52.81 1 8.75
38min 10s
0.83s
57.16 0.70
48.45 1 0.80
SEAL
2h D4min 32s
12.04s
28.29 : 0.38
30.23 + 0.24
2h29min005
51.28s
64.95 0.04
54.71 0.01
PGNN
9min 49. 39s
0.28s
2.66 2:16
1.74 + 0.11
NIA
N/A
NIA
N/A
GNN
53min 26s
0.35s
15.63
0.21
1h52min22s
1.86s
18.17
11.19 0.42
DW
36min 41s
0.23s
0.04 2:012000 0.00
0.02 0,00
34min10s
1.08s
$3.64 0.03
44,79 1: 0.02
LE
33min 42s
0.29%
0:00
0.00
37min22s
0.10
0.12 0.002
PEG-DW
29min 56s
0.27s
56.47 a 0.35
43,80 0.33
1h42min 05s
1.51s
63.98 0.05
51.35 1: 0.06
PEG-LE
32s
0.29%
0.47
1142mind3s
56.52 0.12
48,76 0.92
PE-SAGE-DW
28min 11s
0.31s
68.05 + 0.96
56.16 5.50
56min54s
0.97s
63.43 0.48
54.17 + 01.54
PE-SAGE-LE
19s
0.32s
0.78
9.711
55min59;
49,75
PEG-DW-
48min (1&s
0.284
59.70 + 6.87
47.93 + 0.21
1h37min43s
1.486
62.51 0.19
53.71 + 8.02
PEG-LE+
S1min 25.35s
0.29s
$8.44 1.71
28.32 + 7.34
Ih33min29s
1.39s
$2.91 + 1.24
45,96 9.98
Implementation details. For VGAE, we consider six types of features: (1) node feature (N.): original feature of each node. (2) constant feature (C.): node degree. (3) positional feature (P.): PE extracted by Deepwalk. (4) one-hot feature (O.): one-hot encoding of node indices. (5) random feature (R.): random value r, ~ (0, 1) (6) node feature and positional feature (N. + P.): concatenating the node feature and the positional feature. P-GNN uses node features and the distances from a node to some randomly selected anchor nodes as positional features (N. + P.). GNN Trans. utilizes node features and LE as positional features (N. P.). SEAL adopt Double- Node Labeling (DRNL) to compute deterministic distance features (N. + D.). For PEG, we consider node features plus positional features (N. P.) constant feature plus positional features (C. P.).
Results are shown in Table D and Table 2 Over the small datasets in Table I VGAE with node features outperforms other features in Cora, Citeseer and Pubmed because the nodes features therein are mostly informative, while this is not true over the other three datasets. One-hot features and positional features almost achieve the same performance, which implies that that GNNs naively using PE makes positional features behave like one-hot features and may have instability issues. Constant features are not good because of the node ambiguity issues. Random features may introduce heavy noise that causes trouble in model convergence. Concatenating node features and positional features gives better performance than only using positional features but is sometimes worse than only using node features, which is again due to the instability issue by using positional features.
Although PGNN and GNN Trans. utilize positional features, they achieve subpar performance. SEAL outperforms all of the state-of-art methods, which again demonstrates that the effectiveness of distance features (Li et al. 2020 Zhang et al. 2020). PEG significantly outperforms all the baselines except SEAL. PEG+ by better using training sets achieves comparable or even better performance than SEAL, which demonstrates the contributions of the stable usage of PE. Moreover, PEG can achieve comparable performance in most cases even only paired with constant features, which benefits from the more expressive power given by PE (avoids node ambiguity). Note that PE without GNNs (L.E DW solo) does not perform well, which justifies the benefit by joining GNN with PE.
8

---

Published as a conference paper at ICLR 2022
Table 3: Performance on the domain-shif link prediction tasks, measured in ROC AUC (tdan=tstd%)
Mchood
Features
-iteeer
PormmPu
ES-PP
EN-RE RU
PPI
N.
62.74 = 0.03
63.53 0.27
0.17
60.08 = 0.02
83.24 +
C.
62.16 = 0.08
56.89 0.36
91,23 1: 0.07
75.27 a: 0.89
VGAE
70.59 = 0.03
0.27
0.224
0.01
77.61 : 0.47
R.
68.44 = 0.63
71.27 0.37
7.336
69.37 0.33
75.88 : 0.49
N. + P.
76.45 = 0.55
65.62 + 0.42
84.00
84.67 = 0.22
PGNN
N
85.02 = 0.28
76.88 +
70.41 0.07
63.27 + 0.27
80.84 # 0.03
GNN-Trans.
N.+
61.60 0.52
76.35
6..4
62.87 0.22
79.82 0.17
SEAL
N.
91.36 0.93*
89.62
93.37 0.05'
92.34
88.99
LE
P.
77.62 = 0.04
84.03
67.75 00.09
77.57 + 0.15
72.14 + 0.82
DW
P.
86.48 = 0.14
86.97 0.06
83,56
83.41 + 0.04
85.18 + 0.20
PEG-DW
N.
89.91 0.03
8..2
91.82
91.14
87.36 0.11
PEG-DW
C.+PP
0.07
0.00
9.02
90.26
86.42 = 0.20
PEG-LE
+ 62.57=000
0.224
91.61
0.13
85.34 0.14
PEG-LE
C.+.P. 79.60
88.89
91.38
9..40
85.22 + 0.16
PEG-DW+
N.
0
0.09
0.12
91.91 0.00
89,92 = 0.17
PEG-DW+
C.+
91.32 = 0.011
90.93
91.22
12.1440.00
88 # 0.29
PEG-LE+
N. P.P.
86.72 = 0.05
93.34
91.67 = 0.13
9
86.77 # 0.36
PEG-LE+
C.
87.62 # 0.04
92.21 à 0.20
91.37 4 0.19
93.12 a 0.21
86.21 4: 0.27
Regarding the OGB datasets, PGNN and GNN Trans. do not perform well either. Besides, PGNN cannot scale to large graphs such as collab. The results of DW and LE demonstrate that the original positional features may only provide crude information, so pairing them with GNNs helpful. PEG achieves the best results on ddi, and performs competitively with SEAL on collab. The complexity of PEG is comparable to canonical GNNs. Note that we do not count the time of PE as it relates to the particular implementation. If PEG is used for online serving when the time complexity is more important, PE can be computed in prior. For a fair comparison, we also do not count the pre- pre-processing time of SEAL, PGNN GNN Trans.. Most importantly, PEG performs significantly faster than SEAL on test because SEAL needs to compute distance features for every link while PE in PEG is shared by links. Interestingly, DW seems better than LE as a PE technique for large networks.
4.3 TASK -OMAAN- SHIFT LINK PREDICTION
Datasets & Baselines. Task better evaluates the generalization capability of models. We consider 3 groups, including citation networks (cora->citesee) and cora corbmmdd (Sen et al. 2008), user- interaction networks (Twitch -Twich (RU) and Twitch (ES)->Twitch (PT)) (Rozemberczki et al. and biological networks (PPI) (Hamilton et al.) 2017). For citation networks and user- interaction networks, we utilize 95%, 5% dataset splitting for training and validation over the training graph, and we use 10% existing links as test positive links in the test graph. For PPI dataset, we randomly select 3 graphs as training, validation and testing datasets and we sample 10% existing links in the validation/testing graphs validation/test positive links.
Baselines & Implementation details. We use the same baselines as Task 1, while we do not use one-hot features for VGAF, since the training and test graphs have different sizes. As for node features, we randomly project them into the same dimension and then perform row normalization on them. Other settings are the same as Task PE is applied to training and testing graphs separately while PE over testing graphs is computed after removing the testing links.
Results are shown in Table 3 Compared with Table for VGAE, we notice that node features perform much worse (except PPI) than Task 1, which demonstrates the risks of using node features when the domain shifts. Positional features, which is not specified for the same graph, possibly more generalizable over different graphs. Random features are generalizable while still hard to converge. PGNN and GNN Trans. do not utilize positional features appropriately and perform far from ideal. Both SEAL and PEG outperform other baselines significantly, which implies their good stability and generalization. PEG and SEAL again achieve comparable performance while PEG has much lower training and testing complexity. Our results successfully demonstrate the significance of using permutation equivariant and stable PF.
5 CONCLUSION
In this work, we studied how GNNs should work with PE in principle, and proposed the conditions that keep GNNs permutation equivariant and stable when PE is used to avoid the node ambiguity issue. We follow those conditions and propose the PEG layer. Extensive experiments link prediction demonstrate the effectiveness of PEG. In the future, we plan to generalize the theory to more general PE techniques and test PEG over other graph learning tasks.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
We greatly thank the actionable suggestions given by reviewers. H. Yin and are supported by the 2021 JPMorgan Faculty Award and the National Science Foundation (NSF) award HDDR-2117997
REFERENCES
Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. arXiv preprinl arXiv:2010.01/79 2020.
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation, 15(6):1373-1333 2003.
Maciej Besta, Raphael Grob, Cesare Miglioli, Nicola Bernold, Grzegorz Kwasniewski, Gabriel Gjini, Raghavendra Kanakagiri, Saleh Ashkboos, Lukas Gianinazzi, Nikoli Dryden, et al. Motif prediction with graph neural networks. arXiv preprint arXiv:2 106.00761, 2021.
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. In Advances in Neural Information Processing Systems, pp. 15866-15876, 2019.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? Advances in Neural Information Processing Systems, 2020.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovie. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations, 2021.
Chandler Davis and William Morton Kahan. The rotation of eigenvectors by perturbation. iii. SIAM Journal on Numerical Analysis, 7(1):1-46, 1970.
Vijay Prakash Dwivedi and Xavier Bresson. generalization of transformer networks graphs arXiv preprint 2rXiv:2012.09669 2020.
Fernando Gama, Joan Bruna, and Alejandro Ribeiro. Diffusion scattering transforms graphs. In International Conference on Learning Representations, 2019a.
Fernando Gama, Alejandro Ribeiro, and Joan Bruna. Stability of graph scattering transforms.
Advances in Neural Information Processing Systems, 32:8038-8048, 2019b.
Fernando Gama, Joan Bruna, and Alejandro Ribeiro. Stability properties of graph neural networks. IEEE Transactions on Signal Processing, 68:5680-5695, 2020.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning, pp. 1263-1272. PMLR, 2017.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. Proceedings of the 22nd ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pp. 855-864, 2016.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pp. 1024-1034, 2017.
Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks, 109) 1983.
Kurt Homik, Maxwell Stinchcombe, Halbert White, al. Multilayer feedforward networks universal approximators. Newral Networks, 2(5):359-366, 1989.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong. Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in Neural Information Processing Systems, 2020.
10

---

Published as a conference paper at ICLR 2022
Weihua Hu, Matthias Fey, Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskovec. Ogb-Isc: A large-scale challenge for machine learning on graphs. arXiv preprint Nttv:22033.04430,, 2021.
Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXiv:1611.07308. 2016.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Learning Representations, 2019.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 34, 2021.
Ron Levie, Wei Huang, Lorenzo Bucci, Michael Bronstein, and Gitta Kutyniok. Transferability of spectral graph convolutional neural networks. Journal of Machine Learning Research, 22(272): 1-59, 2021.
Omer Levy and Yoav Goldberg, Neural word embedding as implicit matrix factorization. Advances in Neural Information Processing Systems, 27:2177-2185, 2014.
Pan Li and Jure Leskovec. The expressive power of graph neural networks. In Lingfei Wu, Peng Cui, Jian Pei, and Liang Zhao (eds.), Graph Neural Networks: Foundations, Frontiers, and Applications, chapter 5, pp. 63-98. Springer, Singapore, 2021.
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.
David Liben-Nowell and Jon Kleinberg. The link- link-prediction problem for social networks. Journal of the American society for information science and technology. 58(7):1019-101,, 2007.
Yunyu Liu, Jianzhu Ma, and Pan Li. Neural higher-order pattern prediction in temporal networks. In The International Conference of World Wide Web, 2022.
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.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed representations of words and phrases and their compositionality. In Advances in Neural Information Processing Systems, pp- 3111-3119, 2013.
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 Artificial Intelligence, volume 33, pp. 4602-4609, 2019.
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In International Conference on Machine Learning, pp. 4663-4673, PMLR, 2019.
Axel Nilsson and Xavier Bresson. An experimental study of the transferability of spectral graph networks. arXiv preprint arXiv:2012.10255, 2020.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 701-710, 2014.
11

---

Published as a conference paper at ICLR 2022
Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, pp. 459-467, 2018.
Benjamin Recht, Maryam Fazel, and Pablo Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM review, 52(3):47--50,, 2010.
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 9()xcnab014, 2021.
Luana Ruiz, Luiz Chamon, and Alejandro Ribeiro. Graphon neural networks and the transferability of graph neural networks. Advances in Neural Information Processing Systems, 33, 2020.
Luana Ruiz, Fernando Gama, and Alejandro Ribeiro. Graph neural networks: Architectures, stability, and transferability. Proceedings of the IEEE, 109(5):660-66)) 66266666622620 2021.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM International Conference on Data Mining, pp. 333-341.
SIAM, 2021.
Vicctor Garcia Satorras, Emiel Hoogeboom, and Max Welling. E (n) equivariant graph neural networks. In International Conference on Machine Learning, pp. 9323 93332. PMLR, 2021.
Franco Searselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1): 2008.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification network data. Al magazine, 29(3):93-99 2008
Balasubramaniam Srinivasan and Bruno Ribeiro. On the equivalence between positional node embeddings and structural graph representations. In International Conference on Learning Repre- sentations, 2020.
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large-
scale information network embedding. In The International Conference of World Wide Web, pp. 1067-1077, 2015.
Komal Teru, Etienne Denis, and Will Hamilton. Inductive relation prediction by subgraph reasoning. In International Conference on Machine Learning, pp. 9448-9457. PMLR, 2020.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Hongwei Wang, Hongyu Ren, and Jure Leskovee. Relational message passing for knowledge graph completion. Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1697-1707, 2021a.
Yanbang Wang. Yen-V Yu Chang, Yunyu Liu, Jure Leskovec, and Pan Li. Inductive representation learning in temporal networks via causal anonymous walks. In International Conference Learning Representations, 2021b.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. International Conference on Machine Learning, pp. 40-48. PMLR, 2016.
Jiaxuan You, Rex Ying, and Jure Leskovec. Position-aware graph neural networks. In International Conference on Machine Learning, pp. 7134-7143. PMLR, 2019.
Yi Yu, Tengyao Wang, and Richard Samworth. A useful variant of the kahis theorem for statisticians. Biometrika, 102(2):315-323, 2015.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in Neural Information Processing Systems, 31:5165-5175. 2018.
12

---

Published as a conference paper at ICLR 2022
Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Revisiting graph neural networks for link prediction. Advances in Neural Information Processing Systems, 2020.
Marinka Zitnik and Jure Leskovec. Predicting multicellular function through multi-layer tissue networks. Bioinformatics, 33(14):1100ii198, 2017.
A PROOF OF LEMMA 3.4
Recall the eigenvalues of the PSD matrix B are 0 A < A2 < < Ap < Ap41 S S S S
AN. Suppose one EVD of B = UAU In U = [w1, W2; uN). uy is the eigenvector of X so
Bug A4u4 Without loss of generality, we set PE(B) [U1, U2 ..., Up].
Suppose k: = arg igis Ai+1 Asl. Now, we perturb / by slightly perturbing un and up+1. We
"/4 = /1 - 22 + 602+1
4/411 = -u + / - -1---au e2
Set u/ u, for i [N] i k, + 1. Note that || |1 = and uf u//41 0. Then, the columns of U" [u 122 .... u'y] still give group of orthogonal bases.
Now denote the above perturbation of B B AB E Aeulfuf. Then, PE(D + AB) could be [u/, u2,,.., 4/15" for any S" E SN(p). Therefore, for sufficiently small >>>> 0,
PE + AB)S' PE(B)l S' S'ESN(p)
min
=Il((V] 2 1) Euk+1, (V1 - 11)+++ -ux]lf
=Il(v1 - - + cux+1ll2 + |1( - 2 - 1)u6+1 c2
=411 v1 - 62)
=2e² + o(E?).
(8)
Next, we characterize ABII.
N
N
JABIE = | + AB - B = Σ
Aaduu Σ
=11u (HuT)) + ARt1 (1' 1
IT' - uK+1
=I1(A++ Xa) -e? - - u u up+1)) -eve- e² (uuukt + 12)11b7) 112
-(N411 >v) (E? ue414b + +((e))
-2(A++1 (x) +((2))
Combining Eqs. 8 we have, for sufficiently small 0,
min |PE(B + AB)S - PE(B)]| > 0.99 - > [[ABBl+++(())) o(c), ('ESN(p)
which concludes the proof.
B PROOF OF LEMMA 3.5
The result the Lemma 3.5 can be derived from the Davis-Kahan theorem (Davis & Kahan 1970)
and its variant (Yu al. 2015) that characterizes the eigenspace perturbation. We apply the Theorem 2 Eq.3 of (Yu et al. 2015) to two PSD matrices.
Theorem B.1 (Theorem 2 Yu et al. 2015)). Let two PSD matrices B(1), B E NxN with
eigenvalues 0 (
(3) ... X such that (1) X > 0. For
2
13

---

Published as a conference paper at ICLR 2022
i 1, let U1) (ui U2 :...;; up have orthonormal columns satisfying B( (3)
(6) (1)
(8) for Au
k = 1, 2, ........ p. Then, there exists an orthogonal matrix Q E SO(p) such that
- 11 2 min(p' /2 (()) B lop ||B() ((2
x 1
p+1 Xp
By symmetry, use the above theorem again and we know there exists Q' E SO(p)
2 min(p' B()) - ( op.
B B (1+)
| u1 -
p+l 1p (2
(2)
Because | - 112
-T 1. then there exists Q E SO(p).
|1 - 10 S 23//2 min(p) - BB lop, |I (r)
(10)
where 5 = min - ) (2 )1)
When we apply permutation matrix P to permute the rows and columns of B(2), then (PB()) (P (Puk (2)) = u = x Put for any k. Moreover, permuting the rows and columns of PSD matrix will not change its eigenvalues. This means that (2 can be replaced by ( PT in Eq a0 as long as (?2) replaced by PU(2), Therefore,
Q Q < 2 min (B pT pT lop, |
PB(2))
C PROOF OF THEOREM 3.6
To prove PE-equivariance, consider two graphs g(l) (4()) (4())())) and g(2) (A(2)))(())) that have perfect matching Pa, So, (() p* (2) P.T x(1) p2)(2)
Let ( denote the Laplacian eigenmaps of [ 1, Set B L i 1, and P = P
and use Lemma 3.5 Because (1)) = pa (2) p=T and X * Ap+1. then there exists Q E SO(p).
2 = pr 2
(11)
Now, we consider GNN layer g that satisfies Eqs.
5
Also denote the output as (8(1) 2())
(( ())) and (X((), 2(2)) = (2) 2
(X11) 201) - (1),,,
(0) 1(2 p.t p x(2) ((1))i"'270
p' (()
( P'g(A(2) x(2) z(0
(P* p* 2
Here (a) is because the perfect matching between (1) and (2 and Eq. 11 (b) is due to Eq. 4 and (c) is due to Eq. 5
Therefore, (1) = pa (2) and ()2(1), ((2) = 0, which implies that satisfies PE-equivariance.
D PROOF OF THEOREM 3.7
To prove PE-stability, consider two graphs (())
(40)x(0) and (())
(A(2), (A(2))x(1))
Let ps denote their matching. We study the PEG layer in Eq. 6 and denote (X10) 200) OPEG (A(1), x()) 2() for 1,2.
14

---

Published as a conference paper at ICLR 2022
Let us first bound the easier term regarding the positional features ny(21), P 2(2)). Because 2
70, .2((1) P 2 77 (1)) p* 7(2)), while the bound of the later is given by Lemma 3.5 Set B L6,, i 1,2 and P P Then, there exists Q SO(p),
| - 11: - 23/2 minmmmn(ppp (2110 PP pMT lop, |I - P' - (-T I1)) (12)
Next, we bound the harder part [|x(0) p 8 |p. First,
| - P" |F = 1/ [444] e ) x( pnb (A (A E x(2 11.. (13)
Here, without loss of generality, we set 2 (1|2!! 2 (]) for u, v E [N] such that A +
and otherwise O. Moreover, =(f) is bounded because = = ((1 - S Es /
Z (
||
lo ( + ||z II) = 26 because of the Le-Lipschitz continuity of & and 1 || 3
Compute the difference
1e [44) ) x -P' x - )1"))
x x(]]] ||:
(0)
S drll (A'))
の E x - p" (10) o ) w/1FF
E Toll
A1 + ) x (1)
p' ) x 11
1 1p
(A ( p' ( و ) ) x + p' (E (D-Tx(11 xx2))]l=
(2)
[ c - pr (A (A ) pTu 1EI1
(14)
||P- (A || (())) - 1 [|]]
x(1)
l W [1A 22("o=" - pr ) pat || ||| [|op + 1 1 x(1) p x'x |r
(15)
Here, (a) is due to the fa- LipLsihchhtz continuity of the component-wise function db. (b) and (d) use that for any two matrices A, B, ||AB]]| || I min BB| op: ||Allpp] BllF} and (d) also uses the triangle inequality of ||. ||r. (e) uses |AAllppp = ||AAllop and | FF = || Allp for any P E II.
Next, we only need bound ||A()) e O p- (A o E p- and || C ( lopp
[1 @ OE@) - P (1 ) |'
(a) ||Á(0) o (1) 1 ( (P) 2 (P') ||F
WV I WI ||A(0) @ [E() - (' p*T)
||r || (A p (()) p(T) c (P'E(() prT) ll:
max [,
A -1
uu
|| +
max N
| || A pm (22) peT |
- - pxT ||F + -
(16)
where (a) is because P(A ④ B) = (PAPT) 3 (PBPT) for any P E IT (b) is because for any two matrices A, B, | 0 BlIF < max.,v A Bl|F. (c) is because max AAW <
1, =E [ < ls-
| O 2 op
| op | 2) lop (b) ((()) (p S 2. ( d Ea = max ls
(c)
(17)
where (a) is because for any two matrices A, B. ||A Blp < ||Allop]| B1llpp|/1loppp op. (b) is because graphs are undirected and both 1 and ( are symmetric matrices. Hence, ( and E(2) can be diagonalized. For diagonalizable matrices, their operator norms equal their spectral radius p. (c) is because the
15

---

Published as a conference paper at ICLR 2022
following facts: is known that degree normalized adjacency matrix A has eigenvalues between
-1 and 1; And, ((E(2)) I max Ex=1 I max d 2d l. Here, we use
that E!1 not zero iff vu is an edge in the graph.
Lastly, need to bound | - P- || in Eq 16 Let [N] [N] denote the permutation
mapping defined by P i.e., uu when π (u) and Pae otherwise. Pick the Q SO(p)
that matches the two groups of positional features z z
EEO)
Σ
(
Zt
1Z Z i
0,0
(1ZE)) 1 1200 20 011 12 -222 Q1 1 H(u)
2 Q11
2
2 Σ
(1ZH. -
1-
-20 01)) + (1Z25)
2
2 Q1 1| Q
Q10
0,8
(6)
> (1265) 01 - 211))
28, 12
p 2
= 22) P )
(18)
where (a) is due to the L. Lipschitt continuity of the component-wise function & and (b) is because
of triangle inequalities.
Plugging Eq 18 into Eq and plugging Eqs 16 17
into Eq 15 further using Eqs 13 12 we achieve
|1 P X (2)
l|F
Shol ll (25 + 1)II 1II (1) p L (2) p ||r + 2d (x(((())))) 11
<(76)|x(())0g) llop + ) Eo |
(I )(
(19)
Combining Eq 19 with the bound on positional features in Eq 12 we conclude the proof by
||(00) P X (2) + (1) p 2
$ [[78|||x 1ap + 2d eo L lop + 30)d(g(),
(20)
E PROOF OF THEOREM 3.8
To prove PE-equivariance, consider two graphs g(t) (A(1), (()) and g(2) = -AAA)) (()) that have perfect matching P", (() = (2)) (
= p (2))
Let (6) denote the positional features obtained by decomposing the optimal solution ( to
the optimization problem Eq 7 Because [,(1) p* (2) p'T we have A(1) p (2) p and
D(1) = p* p(2)p==? Then,
Mi)+ arg min (((
(M)
(a)
arg min tr(P" ((T)) M=sp
9(-M))
arg min Ms) (A P*T 9(M)) +f PT PTT 9(-
arg min M=Tnk(Mf)Sp
tr(
MP"))
p" (2) T
16

---

Published as a conference paper at ICLR 2022
Here (a) is because A = P p.T and the assumptions on f+ and f-. (b) is because for two squared matrices A, B. tr(AB) = tr(BA). (c) is because 9 is component-wise function. (d) is because M is the unique solution of arg Mam tr ff
Recall M()+ (2 (1)
z(IT, z 7(1) 7 and M(2)* 7 (2) 7(2)T 2 7 T. Note that z(1, z that satisfy such decompositions are not unique, As rank rank = so
2 .2." (1) and P 2(2) P Z have full-rank columns.
(2) 2 (2) p+t Because 7 (1) has full-rank Since M()+ Pa x()) p-T" 7111 z(U) = Pr (2)
columns, Z' is non-singular. Let Q
(2)T p.t z (1) (1)
(1) 7 (1)) Then, z()
P* Q. Since, Z()7 z = 7 z(2) = I, we have Q = I. Q is squared matrix so QE E SO(p). That means (() = P ( Q for some Q E SO(p).
Now, we consider GNN layer g that satisfies Eqs.
5
Also denote the output as (8(1) 2 =
,(4 (()) and (x) ((2) 9(A
Z )).
= (X 2 ((A 10,,,
(0) g(p ((2) 1 pd.
x(2), pd Q)
@ (')(AA x(2 ()
( (P' p Q)
Here (a) is because the perfect matching between (1) and (2)), and z(1) = p (2)(2) (b) is due to Eq. and (c) is due Eq.
Therefore, (1) p (2) and m((1), _(2)) O. which implies that g satisfies PE-equivariance.
F REVIEW OF THE E-GNN LAYER
Satorras et al. 22021) studies the problem when the nodes of a graph have physical coordinates as features and proposes E-GNN deal with this kind graph data. E-GNN aims to keep permutation equivariant with respect to the node order, and translation equivariant, rotation equivariant with respect to the physical coordinate features. As E-GNN asks even more (translation equivariance) than Eqs. [ E-GNN can be adopted to leverage PE techniques to keep PE-equivariance. The specific form of E-GNN is as follows.
Given a graph 9 = (V,E) with nodes E V and edges eij E. E-GNN layer takes the node embeddings h' (h/ .... h coordinate embeddings x' = (x/, ..., x (xpp....xh--1)
and edge information E = (Ct)) as input and outputs [+1 and + respectively. Thus, the E-GNN layer can be denoted
as: h ++ 1+1 EGCL(h', x E). The layer is defined as following:
mij = de (h., h1: ||xt - x,112 (is))
(1+1) x + Σ (x) -x)) (m.j))
m: (mij)
JEN.
(1+1)
(h
(1)
m
Where aij is the edge attributes, o, represents edge operation, o, represents edge embedding operation and on represents node operation.
17

---

Published as a conference paper at ICLR 2022
G THE OPTIMIZATION FORM FOR GENERAL PE TECHNIQUES
Given an undirected and weighted network G= EV, A) with N nodes, LINE (Tang et al. 2015) with the second order proximity (aka LINE (2nd)) aims extract latent representation matrices Z, Z' E RNX,, Let Zi Z denote the ith row Z and the ith row of Z', respectively. The objective function of LINE (2nd) follows
N
N
+ +6 ΣΣ Aigg(ZZZ)))
L6 i=1
BRnry (g( (())Z
max 2,2'
=1
where g(x) the log sigmoid function g(x) x log(1 + exp(x)) and b a positive constant. The first term corresponds to the positive examples, i.c. links in the graph while the second term is based on network negative sampling. Also, Pv is some distribution defined over the node set. LINE adopts (J) x de where dj is the degree of node j. By filling the expectation and using matrix form to rewrite the objective, we have
ΣΣ
Agg(ZZ,)
+ Σ
By -ry (9(- (o(-7.777)))
1=1
N
+ > dd k,777)
tr 9(Z2') +r(c 9(ZZ')
(tgggg(Z + c11 Dà
where c Σg= 877 So for LINE, f+(A) = A and f-(D) D1, easy to validate that for all P f+ (PAP") (f) and ( PD) which satisfies the condition in Theorem 3.8.
Deepwalk (Perozzi et al. 2014 can be rewritten by following the similar idea. Deepwalk firstly performs random walks with certain length for many times starting from each node and then treat each walk as a sequence of node-id strings. Deepwalk trains a skip-gram model on these node-id strings (Mikolov et al. 2013). Now consider the skip-gram model with negative sampling (SGNS). Denote the collection observed words and their context pairs as D. # (w, c) denotes the number of times that the pair (w, c) appears in D. #(w) and #(c) indicates the number of times and occurred 'D. Let Z denote the vector representation of uo and Z' denote the vector representation of c. According (Levy & Goldberg 2014), the objective function of SGNS follows
# (Z Z.) + Σ # (w))E. (oco:=--(((-00 (o(- 2 W
to
Deepwalk adopts this objective by viewing each node v in V as a word and viewing any node that gets sampled simultaneously with within 7 hops of the random walk the context c. Let 4 - A denote the random walk matrix of the graph. In this case, for node v as the word and for another node the context, the expected number # #(,, u) 4' expected number # (v) x d, which uses the stationary distribution random walk over a connected graph is proportional to the node degrees. We also set the negative context sampling probability P. is proportional to the node degrees, i,e., Pe(u) x dy, Then, in Deepwalk, the SGNS objective reduces
(d* )ou d, (u))w)) The
N Φ
(Z,g) + ΣΣ dodug( Z2
for some positive constant c. Similar to the derivation for LINE, we can rewrite it into the matrix form
((0'g(Z'zz) D11 Dg D01"DD((22 Dzz(-
18

---

Published as a conference paper at ICLR 2022
Table 4: Summary of Twitch dataset
DE
EN
ES
FR
PT
RU
Nodes
9,498
7,126
4,648
6,549
1,912
4,385
Edges
153,138
35,324
59,382
112,666
31,299
37,304
Features
3,170
3,170
3,170
3,170
3,170
3,170
Therefore, for Deepwalk, [A) = Φ' (D +TTKD) and f-(D) =DD1 where = -D-1A and с a positive constant. also easy to verify that for all P E II, f- (PAPT) (A) and f-(PDP') Pf_ P (D)P², which satisfies the conditions in Theorem 3.8
As for Node2vec (Grover & Leskovee 2016). it performs a 2nd-order random walk to collect node-id strings and then train SGNS model. The optimization form is more involved, interested readers Grover & Leskovec 2016) for more details.
could check (Qiu et al. 2018
H SUPPLEMENT FOR EXPERIMENTS
We put more specifics of datasets and basclines adopted in Sec. H.l and Sec. H.2 respectively, We describe how we tune our model in Sec. S.3.H.3. We list further experimental results in Sec. [H.4 We further conduct three supplementary experiments demonstrate the generalization capability, stability and wide applicability of our theory and proposed PEG layer in Secs. H.6 H.8
H.1 DATASETS
The citation networks-Cora, Citeseer and Pubmed are collected by Sen et al. (2008), where nodes represent documents and edges (undirected) represent citations. Node features are the bag-of-words representation of documents. The Cora dataset contains 2708 nodes, 5429 edges and 1433 features per node. The Citeseer dataset contains 3327 nodes, 4732 edges and 3703 features per node. The Pubmed dataset contains 19717 nodes, 44338 edges and 500 features per node.
Twitch obtained from Rozemberezki et al. (202T). Twitch a user-user networks of gamers, where nodes correspond to users and edges correspond to mutual friendship between them. Node features correspond to the games they played and liked, users' location and streaming habits. Twitch contains 7 user networks over different countries, including Germany (DE), England (EN), Spain (ES), France (FR), Portugal (PT) and Russia (RU). The details of these datasets are shown in Table
Chameleon is used in Chien al. (2021). Chameleon is page-page network topic 'Chameleon' in Wikipedia (December 2018), where nodes correspond to articles and edges represent mutual links between the articles. Node features indicate the presence of several informative nouns in the articles and the average monthly traffic (October 2017 November 2018). Chamelcon dataset contains 2277 nodes, 36101 edges and 2325 features per node.
Protein-protein interaction (PPI) dataset contains 24 graphs corresponding to different human tissues (Zitnik & Leskovec 2017). We adopt the preprocessed data provided by Hamilton al. (2017) to construct graphs. The average number of nodes per graph is 2372 and each node has 50 features, which correspond positional gene sets, motif gene sets and immunological signatures.
Ogbl-ddi and ogbl-collab are chose from the open graph benchmark (OGB) (Hu et al. 2021). which adopt more realistic train/validation/test splitting, such by time (ogbl-collab) and by by drug target in the body (ogbl-ddi). ogbl-ddi is drug-drug interaction network, where nodes represent drugs and edges represent interaction between drugs, where the joint effect of taking the two drugs together is considerably different from the effect that taking either of them independently. Ogbl-collab is an author collaboration graph, where nodes represent authors and edges represent the collaboration between authors. The 128 dimension node features of ogbl-collab is extracted by by averaging the word embeddings of the authors' papers. Ogbl-ddi has 4267 nodes and 1.3M edges. Obdl-collab has 0.23M nodes and 1.3M edges.
19

---

Published as a conference paper at ICLR 2022
Aupmed
Pubmed
2
(Ri)ch(RU))
Twitch/RUy
Chameleon
Chameleon
Figure 3: Eigenvalues Xp and the stability ratio mang IAu A PEG with sensitivity [A Apt1l"
14y
far more stable than previous methods with sensitivity maxiçkçp A -x+1| -- Over Cora, Pp extremely large because there are multiple eigenvalues (pp still finite due to the numerical approximation the eigenvalues). Over Pubmed, Twitch(RU) and Chameleon even if there are no multiple eigenvalues, Pp is mostly larger than 5.
H.2 BASELINE DETAILS
We have 4 baselines based on GNNs and 2 baselines based on network embedding techniques, namely, LE (Belkin & Niyogi 2003) and Deepwalk (DW) (Perozzi al., 2014). We will first introduce the implementation of LE and DW, then discuss other baselines.
Both LE and DW embed the networks in R:128 an unsupervised way. For LE, we factorize of the graph Laplacian matrix: A = I D AD- = UAUT, where is the adjacency matrix, is the degree matrix, and A, U correspond respectively to the eigenvalues and eigenvectors. We use the 128 smallest eigenvectors as LE. For DW, we use the code provide by OpenNI Both methods use the inner product between pairwise node representations as the link representations. Then, the link representations are fed to an MLP for final predictions.
Regarding GNN-based baselines, VGAE is implemented according to the code (iipf & Welling 2016) given by the original paper, with 2 message passing layers with 32 hidden dimensions. P-GNN implemented by adopting the code") provided by the original paper (You et al. 2019). with message passing layers with 32 dimensions, with a tuned dropout ratio in (0, 0.5). GNN transformer layer is implemented by adopting the code provided by the original paper (Dwivedi & Bresson 2020) with 2 message passing layers with 128 hidden dimensions. SEAL is implemented by adapting code provided by the original paper. Notice the ogbl-ddi graph contains no node features, so the use prce-paramcter node embeddings the input node features and train them together with the GNN parameters. We slightly tune the hidden dimensions and layers of these baselines and present the best results.
codeF)
Moreover, we aim to understand whether PEG sensitive to the dimension of positional features. We conduct experiments Cora, Pubmed and Twitch(RU) to test the sensitivity of the dimension positional features. In Fig. we compare the performance of PEG-DW, PEG-LE, PEG-DW+ and PEG-LE+ with PE in different dimensions. All the experiment settings follow the setting to get Table D except for the dimension of positional features.
H.3 HYPERPARAMETERS TUNING FOR PEG
Table lists the most important hyperparameters. which applies to our proposed model PEG. Grid research is used to find the best hyperparameter combination. Note that our model actually got very slightly tuned. We believe more extensively hyperparameter tuning may yield even better results.
https:/ggthuh..m///aaaaaaann hhans///ghhh..cmmmmmmaaaaaaAAAA
20

---

Published as a conference paper at ICLR 2022
Cara
Pubredd
Twilch(RU)
0.54
0.25
0.5
0.45
0.220
0.41
0.915
RGG
WOHL
0.02
REGLEE
0410
PGG uS+
0.50
0905
0.89
0900
120
1G5
PE: dimerran
Ps dinemsion
PE dimersion
Figure 4: The performance (AUC) of PEG with different dimensions of positional encodings for traditional link prediction (Task I).
The models are trained until the loss converges and we report the best model by running each for 10 times. We provide our code for reproducing the experimental results to the reviewers and area chairs in the discussion forums.
Table 5: List of hyperparameters and their value/range
Hyperparameters
Value/Range
batch size
64, 128, 64x (024(ogb)
learning rate
le-2, le-3
optimizer conv. layers
Adam
conv, hidden dim PE. dim
128
128
H.4 FURTHER ANALYSIS
As a supplement to the Lemma 3.4 and Lemma 3.5
we compute the ratio between the inverse Aptil -1] and maxigasp D A
eigengap between the pth and (p- 1 th eigenvalues (P>p over more graphs as shown Fig.
Fig. shows that different PE techniques have different dimensional sensitivity. In general, DW seems to be more stable than LE over the three datasets and PEG-DW+ achieves stable performance. When the dimension increases, PEG more likely achieve higher performance, but will be more time consuming.
H.5 EDGE WEIGHT VISUALIZATION
In the PEG layer, we calculate an edge weight according to the distance between the representations of the end nodes of the edge. To further understand the learnt relationship between edge weights and the distance between node representations, we visualize the edge weight transformation curves. We
run the experiment traditional link prediction (task 1) and use DW the node positional embedding, i.e., the model PEG-DW. For each dataset, we draw the edge weight transformation curves in Fig. 5 Note that each curve ranges in x-axis from the smallest distance the largest distance observed from the corresponding graph, we also randomly select 500 distances from each graph and scatter them on the curve as shown in Fig. Fig. 5 shows that the edge weight increases monotonically with respect to the input distance, but the relationship between them is non-linear. Most of the weights are close but few weights are much smaller.
H.6 LINK PREDICTION OVER RANDOM GRAPHS
To further demonstrate the generalization of our model, we conduct inductive link prediction over random graph models. Specifically, we use stochastic block models (SBM) with two blocks Holland et al. (1983) to generate random graphs. Each block contains 500 nodes and the probability to form link between two nodes within each block is 0.3, while the probability to form a link between two nodes across different blocks is O.I. Here, randomly select links inside the blocks positive
21

---

Published as a conference paper at ICLR 2022
1.0
237
130
16
00
Figure 5: The edge weight transformation curve of PEG for each dataset. 500 selected edges are represented as red points.
1.0
JCGLE
GAL poeiional featurs (u))
GdE conetatt teature
0.9
64E randem foature
0.7
0.6
0.5
10
30
50
the number graphs for training
Figure 6: The comparison of AUC-ROC between PEG and GAE baselines for link prediction on random graphs.
samples, and randomly select the missing links (unconnected node pairs) from the generated graph as negative samples. The model is trained by using various numbers of graphs (e.g. 1, 10, 30, 50), validated and tested 10 random graphs respectively. For each graph that is used for training or testing, we utilize 10% positive links and pair them with the same number of negative missing links for training or testing respectively. The rest settings remained the same as in Task 2. We choose three variants of GAE that use constant features (node degree), random features and positional features as baselines. All the models are trained until they converge and the models with the best validation performance are used to report the results (averaged by 10 independent runs), which are shown in Fig. For various sizes of input graphs, PEG achieves AUC around 0.98 by just using one training graph and slightly improves AUC by using more training graphs, which consistently outperforms all three GAE variants that even use the entire 50 training graphs with large margins. This directly demonstrates the stability and better generalization of PEG models.
H.7 THE STUDY OF PE STABILITY BY PERTURBING THE INPUT GRAPHS
To further investigate PE stability, we consider two versions of models utilizing PE PE-one is PEG, which is PE equivariant and stable, and the others are GAE/VGAE (N./C P.). which fail to satisfy the two equivariant properties and thus may not be stable. These two versions of models are evaluated on the Cora dataset. All the models are trained over the original graph. Then, we perturb the input graph by randomly adding or dropping certain percentage of links during the inference. The rest of the settings remain the same for link prediction. Specifically, after training the model, we inject a perturbation top of the input graph by adding extra links (negative samples) or dropping positive links with the ratio of 10%. 20% and 30%, respectively. We recompute the positional encodings to reflect the structural perturbation of the given graph and plug in the perturbed positional encodings into different models. Other experiment settings remain the same as in Task The results are summarized and plotted in Fig.
22

---

Published as a conference paper at ICLR 2022
Adding edge (Node feature)
Adding edge (Constant feature)
0.95
0.90
0.90
0.85
0.85
0.80
0.80
0.75
AUC
0.75
0.70
REG-DW++Ch,
PEG-OW-II,
LEGILEHIN,
LEG.
REG-DW (N. P)
0.60
PEG DW IC. PP)
0.05
FEG LE (N. hg
PEG LE LPI
0.55
VEARIE
CAPEN.
DANE
0.50
20
adding edge percent
adding edge percent
Dropping edge (Node feature)
Dropping edge (Constant feature)
0.95
0.90
0.85
0.85
0.80
0.80
0.75
0.75
0.70
REG-LE R)
0.70
DEG.DW IN. P3
0.65
PCG DW IC.
PEG-LE (h.
PEG-LE
0.60
0.60
GASIN. +
GAEIC + LE)
20
30
10 dropping edge percent
30
dropping edge percent
Figure 7: The AUC-ROC of PEG and GAE/VGAE for link prediction in terms of PE stability (w. node or constant feature and w. adding or dropping edges). To perturb the input graphs, we can randomly add or delete some edges with the percentage shown in the X-axis before the inference.
By comparing the models with different levels of input perturbation, we can observe from Fig. 7 that PEG achieves consistently and significantly better performance with either node features or constant features in all four scenarios, which is far more robust than GAE/VGAE-based models that adopt PE under the same level of perturbations. Compared with adding edges, removing edges is more destructive for small-size graphs such as Cora, and thereby does more harm to the model performance. Particularly, all the models using C. + P. achieve subpar performance when considerable number of edges are removed. However, PEG can still show strong resilience against this type of perturbation (especially with node features), while GAE/VGAE generally collapses. These results further support that the performance boost indeed benefits from the equivariance and stability with PEs instead of simply using PE variants.
H.8 PRELIMINARY RESULTS FOR NODE CLASSIFICATION BASED ON PE
In order to evaluate PEG on a wider category of tasks, we consider node classification on citation networks- Cora, Citeseer and Pubmed (Sen et al. 2008) and closely follow the transductive experimental setup of Yang et al. (016). Suppose the final readout of PEG is denoted (X, Z). To classify the node u, we only utilize its node representation X2 to make the final predictions. The rest parts and the hyperparameters of the model are kept the same as the one that is good for our task 1 (traditional link prediction). We did not specifically tune the model for node classification. The results of evaluation on node-level are summarized in Table We report the mean accuracy with standard deviation of classification on the test set of our method after 10 runs.
Both PEG-LE and PEG-DW significantly outperform GCN and provide comparable results against GAT, which illustrates the effectiveness of the proposed PEG on node level tasks. Recall that we almost did not tune our model to achieve such results. Even better results may be expected by further finer tuning the model on each dataset. Moreover, GAT uses multi-head attention to aggregate information from neighbours where the attention weights are based node features, while PEG only adopts GCN layers with some edge weights derived from positional encodings that merely depend on the network structures. PEG and GAT essentially utilize orthogonal information source to re- weiighht
23

---

Published as a conference paper at ICLR 2022
Table 6: Summary of results in terms of node classification accuracy (mean std%), for Cora, Citeseer and Pubmed.
Method
Cora
Citeseer
PubMed
PEG-DW
8
71.22 0.01
79.83 + 0.02
PEG-LE
82.16 0.02
71.93 0.01
79.85 0.01
GCN
81.50
70.38
79.03 0.03
GAT
83.03 # 0.07
72.52 0.07
79.06 + 0.03
the edges. Hence, PEG should be easily further combined with the attention mechanism based on node features to get even better predictions, which this is out of the scope of this work, we leave it for future study.
24


Reviews:
[{"review_id": "cXJO6Giv_Xz", "reviewer": "Reviewer_L7CF", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I appreciate the reasonable motivation and rigorous analysis in the paper. I only have some comments on it.\n\n1) The analysis of matching is limited to graphs of the same size. Is there any possibility to generalize to different sizes? How does it consistent with experiments where two graphs are of different sizes?\n2) The idea actually smartly borrows from SE(3)-transformer (or etc) with positional encoding (PE) to replace the physical coordinate. The inner product in eq (6) makes it only rotation equivariant while it is easy to use L2 distance (or etc) to make it also translation equivariant.\n3) Do authors have any intuitive interpretation on PE, why do we need it to be rotation (or translation) equivariant? Some examples would help the audience further to understand the significance.", "summary_of_the_paper": "The paper focuses on tasks of a set of nodes handled by graph neural networks (GNNs), which generally requires random feature (RF) or positional encoding (PE) to recognize the node identity. When RF is hard to converge and PE is less generalizable and stable to unseen graphs, authors propose a new architecture name PEG, processing node features and PE in different channels. Rigorous theoretical analysis shows PEG is permutation invariant to node features and rotation equivariant to PE, and its stability is guaranteed. Extensive experiments on link prediction (the task on node pairs) demonstrate the advantage of PEG.", "summary_of_the_review": "I am generally satisfied with the content of the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "YnLoIL8nlX", "reviewer": "Reviewer_FBSc", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: the paper is well written and I liked the theoretical part (Section 3). The ideas are very natural and nicely presented. The notion of stability will likely be picked up in future works and the authors show how to construct PE-stable layers which can be useful.\n\nWeakness: the evaluation in Section 4 is very disappointing. Equivariance is only useful for inductive task but the link prediction task considered by the authors is a transductive task. For task 1, I do not see why you would ask your algorithm to be equivariant as the learning algorithm is trained on one graph. In such a case, you can choose an ID for each node and use this ID to make your link prediction. Task 2 is better to test equivariant architecture. But for task 2, I do not understand why the authors look at the link prediction problem. For example, the PPI dataset is typically not used to do link prediction so why doing this here?\nIndeed, the authors are aware of this weakness as they write: 'Both tasks may reflect the effectiveness of a model while Task 2 may better demonstrate the model’s generalization capability that strongly depends on permutation equivariance and stability.'\nTo validate their theoretical results, the authors should consider a task where equivariance is 'crucial'. The QAP problem studied in 'Expressive Power of Invariant and Equivariant Graph Neural Networks' by Azizian and Lelarge (ICLR 2021) is probably a good candidate.\n", "summary_of_the_paper": "This paper studies positional encoding (PE) for Graph Neural Networks (GNN). A positional encoding can be seen as a computed feature for each node from characteristics of the graph. A well-known example of PE are the components of the eigenvectors of the Laplacian of the graph. Unfortunately, such a PE is not permutation equivariant. This is mainly due to the fact that eigenvectors are not uniquely defined.\nThis paper address this issue with some care (correcting some mistakes made in previous works).\nSection 3 of the paper presents the main theoretical results of the paper. In particular, the authors introduce a notion of stability that is stronger than equivariance: if two input graphs are 'similar' then their outputs through a stable layer should also be 'similar' with a 'Lipschitz' constant. This notion is interesting. Then, the authors explain some errors made in the literature and address these issue by proposing a PE-stable layer that is shown to be PE-stable under some conditions on the spectrum of the Laplacian. Some other techniques to get PE-stable layers are provided in section 3.3\nIn Section 4, experimental results are provided with this new architecture for task 1: link prediction and task 2: domain-shift link prediction. These experiments demonstrate the effectiveness of PE-stable layers.", "summary_of_the_review": "There is a mismatch between the theoretical part of the paper and the experiments.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "UKq0T74XZ6u", "reviewer": "Reviewer_eyVz", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1.\tThe proposed approach is well motivated and mathematically rigorous.\n2.\tThe writing is in general clear and well-reasoned.\n3.\tThe experimental results have demonstrated the superiority of the proposed approach on multiple datasets.\n\n\nWeaknesses:\n1.\tThe stability definition needs better justified, as the left side can be arbitrarily small under some construction of \\tilde{g}. A more reasonable treatment is to make it also lower bounded.\n2.\tIt is expected to see a variety of tasks beyond link predict where PE is important.\n", "summary_of_the_paper": "This paper proposes a novel GNN layer called PEG layer to address the issue that existing positional encoding are not generalized to unseen graph very well. PEG designs different operators for raw features and positional features separately, which is able to ensure permutation equivariance and rotation equivariance for each type of feature, respectively. The experimental results have also demonstrated the power of the proposed approach.", "summary_of_the_review": "This paper provides a through discussion on limitations of existing PE approaches and proposes the criterions of PE-equivariance and PE-stable. Mathematically, this paper proves the proposed PEG layer is able to preserve permutation equivariance as well as to achieve PE-stability. The proposed technique is solid and novel. There are some minor concerns as raised in weaknesses, but overall it is a paper worth of accept. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "7NeVZHKk-L", "reviewer": "Reviewer_KJUw", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: \n\n1) Lemma 3.4, where the authors theoretically show the particular PE design (of matrix B) violates PE-stability is very useful. Theorem 3.7 where the authors have explicitly derived the value of the constant C for equation 1 is particularly relevant (although the bound can be made tighter).\n\n2) The authors have also put some effort into pointing out the generalizations to other methods. Further, they provide some guarantees for PE methods that follow the optimization objective in equation 7 and show their PE equivariance.\n\n3) Figures 2 and 3 have interesting observations on real world data.\n\n4) I found the Domain-shift link prediction experiments to be very practical and highly interesting. \n\n5) The design choice for the PEG layer in equation 6 is sufficiently simple and easy to compute. The conditions in equation 4 and 5 are very sound. Table 2 shows that the proposed method is also substantially faster than the best performing baseline SEAL.\n\n\nWeaknesses (and questions for authors): \n\n1) “A GNN layer is expected to be permutation equivariant and stable. These two properties, if satisfied, guarantee that the GNN layer is transferrable and have better generalization performance” - the authors do provide an intuition in subsequent lines and experiments to support their claim in section 4.3, but are there any relevant works that they can direct to? Can, or more concretely, does it hold for any other type of generalization?\n\n2) Can the experiments be done on a wider category of tasks? Although the authors do mention it as a future work, it will be quite interesting to see some evaluation on at least one of: node / graph classification / community detection tasks as well.\n\n3) Can the authors also consider at least one more recent and strong baseline, such as [1]? The evaluation is quite thorough and I understand that it might be difficult to perform these experiments, but it will be quite interesting to see the outcomes, since at least one of the recent methods, ie SEAL, is performing very competitively (and [1] has been shown to outperform SEAL in some cases).\n\n4) Can the authors provide more intuition on why they arrived at the proposed choice in Equation 6? Also, is there any other reason for choosing GCN apart from its simplicity and ease of incorporating the permutation equivariance? \n\n5) The zig-zag patterns in figure 4 are very interesting. I understand that it may or may not be trivial, but it will be helpful if the authors can provide some more intuition for such behavior apart from what is stated in section H.4 .\n\n6) Can the authors elaborate the related works section 1.1 a bit more? Particularly, more details on the methods that propose an explicit use of PE techniques such as [2] and [3] might be helpful.\n\n7) Although intuitively sound, as I have mentioned in the strengths subsection above, it will be great if the authors can provide some reference or more conclusive evidence to this statement - “Inspired by the stability of the eigenspace, the idea to achieve PE-stability is to make the GNN layer invariant to the selection of bases of the eigenspace for the positional features” on the second last paragraph on page 5.\n\n[1] S. Abu-El-Haija, B. Perozzi, R. Al-Rfou, and A. A. Alemi, “Watch your step: Learning node embeddings via graph attention,” in Advances in Neural Information Processing Systems, 2018\n\n[2] Srinivasan, Balasubramaniam, and Bruno Ribeiro. \"On the equivalence between positional node embeddings and structural graph representations.\" arXiv preprint arXiv:1910.00452 (2019)\n\n[3] Dwivedi, Vijay Prakash, and Xavier Bresson. \"A generalization of transformer networks to graphs.\" arXiv preprint arXiv:2012.09699 (2020).", "summary_of_the_paper": "The authors propose a novel PEG layer to account for positional encodings in graph neural networks and state some necessary conditions for its stability and permutation equivariance while providing theoretical insights for the same. They show that their proposed layer is PE-equivariant under some conditions (theorem 3.6) and also derive the value of the constant C for equation 1 to guarantee PE-stability. Extensive experiments done for the task of link prediction clearly show that the proposed layer is indeed useful and the only subpar baseline method is SEAL (which outperforms PEG in some cases). The authors have also performed experiments to vividly show the generalization ability of their layer using the task of domain-shift link prediction, which are indeed interesting. The simplicity of their approach complemented with a reasonable runtime further adds to the overall utility of this work. The tweak used in section 4.1 for training on graphs where the union of link sets for training, validation and testing cover the entire graph is also useful and can also be leveraged in other methods having explicit positional encodings for GNNs.\n\nGiven the recent upsurge in the amount of work done to incorporate positional encodings in GNNs, work such as this that addresses the shortcomings of previous methods and also provides a theoretical framework was necessary. \n\nSmall typo on page 4 and 5 - “features” spelled as “feautures” .\n", "summary_of_the_review": "Overall the paper is very well written, has some interesting theoretical insights and very practical results. It will be very helpful if the authors can further address some of the  questions and weaknesses as pointed out in the previous subsection of this review. I believe that the authors should at least perform more diverse experiments to completely support their arguments regarding generalization and higher stability. After addressing these minor pointers, I believe that the contributions will be worth presenting at the conference. I additionally support the simplicity of the proposed approach, both analytically and computationally.\n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "--KhlF2wr0j", "reviewer": "Reviewer_rbLd", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "(a) -- Comments, with strengths:\n- *Positioning*: The location of this work with respect to the literature is detailed and comprehensive as the limitations of existing works along this line is properly described. In particular, the discussion with Laplacian eigenvectors based PEs that could have ambiguities due to the sign and multiplicity is reviewed clearly and the work attempts to address the issues henceforth.\n- *Writing*: The writing is easy to follow for readers aware with the research direction. Equivariance and stability of PEs to be used in GNNs is at the centre of the paper and their definitions, formalization and relevant conditions are clearly expressed.\n- *Significance*: The contribution of the paper thus is helpful for the community given there are several papers recently that are attempting to use graph PEs to improve GNNs expressivity. In those works, the equivariance/stability issues of PEs were not explicitly addressed. The PEs were more like augmentations to GNNs in terms of supplying higher structural information when they learn on graphs; as nodes in graphs would not be canonically defined in terms of positions.\n- *Empirical results/Experiments*: The focus in this work is only on link prediction tasks. Although I believe the work can be applied to general graph representation learning for other tasks as well. Experiments on the proposed model *compared to baselines* show the advantage of using the PE in the proposed model that uses these as edge weights. However, these models do not provide SOTA results and lag *behind the top scores* on the leaderboards of two OGB datasets considered [1]. In this respect, it may not be clear how the satisfiability of the two conditions leads to a powerful model, in practice.\n\n\n(b) -- Other comments/concerns:\n- In page 6, \"We implement g in our model PEGN with further simplification\". => Does this mean the paper does not present a GNN 'g' which is PE-equivariance and PE-stable in general? Are the results of satisfying the two conditions *tied* to the instantiation of g_PEG only? [Since, g_PEG seems a modification of the GCN with edge weights that are supplied with positional features of source and destination nodes.] \n- In page 2, the paper claims \"The key idea is to use separate channels to update the original node features and positional features.\" However, to the best of my understanding of the paper, I feel this is not (necessarily) enforced. For instance, the Eqn. 6 does *not update positional features*.\n- In page 2, the paper states \"PEG achieves comparable performance with strong baselines based on DE\". I could not find comparisons on the datasets where PEG is compared against DE.\n- During the discussion of non-uniqueness of LE as PE used in previous works, I believe simply using absolute signs of the eigenvectors would guarantee permutation equivariance; although I understand the stability issues. \n- The title of the paper says \".... More Powerful Graph Neural Networks\". I feel this addition of power is not discussed in the paper. I understand that its necessary to sort (and get rid of) the issues of Z_LE while using them as PE. But is the power being added just because of the equivariance/stability conditions met? This is also reflected in the experiments where the scores on the 2 OGB datasets do not compare to SOTA results. In other words, I am still unable to ascertain to myself whether the performance boost (compared to baselines) comes from i) simply the PE variants used (as they may be bringing other higher structural information to the GNN used). or ii) the addressal of the issues of equivariance and instability with the PEs? To this end, a fair study of two model versions where one version has the issues of instability and the other does not have, leaving all other settings intact for the two versions, would help addressing this question!\n\n\n\n(c) Minor comments: \n* Page 8; under the heading \"Implementation details\": typo constant feature (P) ==> constant feature (C)?\n* The comparison of the results on the datasets with other GNN SOTA is not presented?\n* In the experiment tables, the mean and s.d. is reported. How are these reported on? How many runs? These details can help reproducibility.\n\n\n\nReferences:  \n[1] OGB link property prediction leaderboards: https://ogb.stanford.edu/docs/leader_linkprop/  \n[2] Srinivasan, B. and Ribeiro, B., 2019. On the equivalence between positional node embeddings and structural graph representations. arXiv preprint arXiv:1910.00452.\n\n", "summary_of_the_paper": "The paper considers the topic of equivariant and stable positional encodings (PEs) for graph neural networks. It goes along a recent line of research that develop PEs for GNNs to: i) disambiguate structurally different nodes using positions and ii) improve the GNN in consideration. \nThis work formally studies the two conditions of equivariance and stability for graph PEs (Section 3.1). A new GNN layer is proposed (Section 3.2) based on modification of a GCN based layer with edge features that can satisfy the two conditions. Experiments are conducted on several small-scale link prediction datasets with performance improvements over baselines.\n", "summary_of_the_review": "Overall, I feel this work is interesting and important in this direction of *designing PEs for GNNs* that do not have any issues violating the beauty of using GNNs in the first place; and critical for link prediction tasks as known from the literature [2]. However, it seems the empirical results may not be adequate to reflect on the technical contributions of the paper. In summary, my evaluation of ‘correctness’ and ‘technical novelty and significance’ measures of this paper are positive, while the evaluation of ‘empirical significance’ does not seem to align to the technical contribution.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work studies the question of increasing the expressive power of GNNs by adding positional encodings while preserving equivariance and stability to graph perturbations. 
Reviewers were generally positive about this work, highlighting its judicious problem setup, identifying the right notion of stability and how it should drive the design of positional encodings. Despite some concerns about the discrepancy between the theoretical results and the empirical evaluation, the consensus was ultimately that this work is an interesting contribution, and therefore the AC recommends acceptance.
Decision: Accept (Poster)