Graph Neural Networks with Learnable Structural and Positional Representations
Authors: Vijay Prakash Dwivedi
Anh Tuan Luu
Thomas Laurent
Yoshua Bengio
Xavier Bresson
Venue: ICLR 2022 Poster (2022)
Keywords: graph neural networks
graph representation learning
transformers
positional encoding

Abstract: Graph neural networks (GNNs) have become the standard learning architectures for graphs. GNNs have been applied to numerous domains ranging from quantum chemistry, recommender systems to knowledge graphs and natural language processing. A major issue with arbitrary graphs is the absence of canonical positional information of nodes, which decreases the representation power of GNNs to distinguish e.g. isomorphic nodes and other graph symmetries. An approach to tackle this issue is to introduce Positional Encoding (PE) of nodes, and inject it into the input layer, like in Transformers. Possible graph PE are Laplacian eigenvectors. In this work, we propose to decouple structural and positional representations to make easy for the network to learn these two essential properties. We introduce a novel generic architecture which we call \texttt{LSPE} (Learnable Structural and Positional Encodings). We investigate several sparse and fully-connected (Transformer-like) GNNs, and observe a performance increase for molecular datasets, from $1.79\%$ up to $64.14\%$ when considering learnable PE for both GNN classes.

Published as a conference paper at ICLR 2022
GRAPH NEURAL NETWORKS WITH LEARNABLE STRUCTURAL AND POSITIONAL REPRESENTATIONS
Vijay Prakash Dwivedi!
Anh Tuan Luu'
vi vijaypra001 dte.nntu.ed....
anhtuan. luu@ntu.
Thomas 2 claurent& edu
Yoshua Bengio yoshua yoshua.bengioomill. www.iiinnggnlaaa..ooooo..iiaaala
Xavier Bresson
quebec
xavierênus edu sg
Nanyang Technological University, Singapore 2 Loyola Marymount University
3 Mila, University of Montréal
CIFAR
National University of Singapore
ABSTRACT
Graph neural networks (GNNs) have become the standard learning architectures for graphs. GNNs have been applied to numerous domains ranging from quantum chemistry, recommender systems to knowledge graphs and natural language pro- cessing. A major issue with arbitrary graphs is the absence of canonical positional information of nodes, which decreases the representation power of GNNs to distin- guish e-g. isomorphic nodes and other graph symmetries. An approach to tackle this issue is to introduce Positional Encoding (PE) of nodes, and inject it into the input layer, like in Transformers. Possible graph PE are Laplacian eigenvectors. In this work, we propose to decouple structural and positional representations to make easy for the network to learn these two essential properties. We introduce a novel generic architecture which we call LSPE (Learnable Structural and Positional Encodings). We investigate several sparse and fully-connected (Transformer- GNNs, and observe performance increase for molecular datasets, from 1.79% up to 64. 14% when considering learnable PE for both GNN classes.
INTRODUCTION
GNNs have recently emerged as a powerful class of deep learning architectures to analyze datasets where information is present in the form of heteregeneous graphs that encode complex data con- nectivity. Experimentally, these architectures have shown great promises to be impactful in diverse domains such as drug design (Stokes et al. 2020 Gaudelet al. 2020), social networks (Monti et al.
2019 Pal et al. 2020), traffic networks ODerrow-Pinions et al. 2021). physics (Cranmer et al.) 2019
Bapst al. (0200, combinatorial optimization (Bengio et al. 2021 Cappart al. 2021 and medical
diagnosis (Li et al. 2020c).
Most GNNs (such as Defferrard al. (2016); Sukhbaatar et al. (2016); Kipf & Welling 201 7);
Hamilton et al. (2017): Monti et al. (2017) Bresson & Laurent (2017) 70: Veličkovič et al. (2018) Xu
al. )2019)) are designed with a message-passing mechanism (Gilmer et al. (017) that builds node representation by aggregating local neighborhood information. It means that this class of GNNs fundamentally structural, i.c. the node representation only depends on the local structure of the graph. As such, two atoms in a molecule with the same neighborhood are expected to have similar representation. However, it can be limiting have the same representation for these two atoms as their positions in the molecule are distinct, and their role may be specifically separate (Murphy et al. 2019). As a consequence, the popular nodes with the same I-hop local structure. This restriction is now properly understood in the context of the equivalence of MP-GNNs with Weisfeiler-Leman (WL) test (Weisteiler Leman 1968) for
passing GNNs (MP-GNI fail to differentiate two
graph isomorphism (Xu et al. 2019 Morris et al. 2019).
CCode: httpps://githuu..cmm/
75/ gnn- 1spe 1spe

---

Published as a conference paper at ICLR 2022
f
@I
G= (V,4]: ==IM
[
Noda Strustural Feutures
PE: Poeildonal Encoding Matrix e R
f
O
Node Postioona Features
Embd. :iiear Embedding Layer
Edge
fe
MPGMP-GNN--- Layer
Graph
(M Jaer
Node feat.
(MP) c.
= fot "Jao B
Edge
f Ex
Losszue (()
Lose (p)
Position luit.
PEg PM
(of) Ex!
G. (M() (r.)) GD e
9. (f(")) 66 6 ex!
Input Layer
Layer 1
Layer ++1
Output and Loss
Figure I: Block diagram illustration of the proposed MPGNNs- LSPE architecture along with the inputs, general framework of a layer, and the output and loss components.
The said limitation can be alleviated, to certain extents, by (i) stacking multiple layers, (ii) applying higher-order GNNs, (iii) considering positional encoding (PE) of nodes (and edges). Let us assume two structurally identical nodes in graph with the same I-hop neighborhood, but different with respect to 2-hop higher-order neighborhoods. Then, stacking several layers (Bresson &
Laurent 2017 Li et al. 2019) can propagate the information from node to multiple hops, and thus differentiate the representation of two far-away nodes. However, this solution can be deficient for long-distance nodes because of the over-squashing phenomenon (Alon & Yahav 2020). Another approach to compute higher-order node-tuple aggregations such as in WI.-based GNNs (Maron et al. 2019: Chen et al., (219); though these models are computationally more expensive to scale than MP-GNNs, even for medium-sioe sized graphs (Dwivedi et al., 2020). An alternative technique is to consider global positioning of the nodes in the graph that can encode graph-based distance between the nodes You et al., 2019) Dwivedi et al. 2020 Liet 2020b Dwivedi & Bresson (021).
can inform about specific sub-structures (Bouritsas al. 2020 Bodnar et al. (022))
Contribution. In this work, we turn to the idea of learning positional representation that can be expressive node embedding. Our main intent is to
combined with structural GNNs generate alleviate the lack of canonical positioning of nodes arbitrary graphs to improve the representation power of MP-GNNs, while keeping their linear complexity for large-scale applications. For this objective, we propose a novel framework, illustrated with Figure D that enables GNNs to learn both structural and positional representations at the same time (thus named MPGNNs LSPE), Alongside, we present a random-waid diffusion based positional encoding scheme to initialize the positional representations of the nodes. We show that the proposed architecture with learnable PE can be used with any graph network that fits to the MP-GNNs framework, and improves its performance (1.79% to 64.14%). our demonstrations, we formulate LSPE instances of both sparse GNNs, such GatedGCNs (Bresson & Laurent 2017) ) and PNA (Corso et al.) 2020 and fully-connected Transformers- based GNNs (Kreuzer et al., 2021 Mialon et al. 2021). Our numerical experiments on three standard molecular benchmarks show that different instantiations of MP-GNNG with LSPE surpass the previous -fate-of-the-ar (SOTA) on one dataset by a considerable margin (26. 23%). while achieving coma-compa consistent improvements on three non-molecular benchmarks. In addition, our evaluations find the sparse MP-GNNs to be outperforming fully-connected GNNs, hence suggesting greater potential towards the development of highly efficient, yet powerful architectures for graphs.
the other two datasets. The architecture also shows
2 RELATED WORK
In this section, we review briefly the three research directions theoretical expressivity of GNNs, graph positional encoding, and Transformer-based GNNs.
2

---

Published as a conference paper at ICLR 2022
Theoretical expressivity and Weisfeiler-Leman GNNs. As the theoretical expressiveness of MP. 2019), they may perform poorly on graphs that exhibit several symmetries (Murphy et a.. 2019), and additionally some pessage-passingg functions may not be discriminative enough (Corso et al. 2020). To this end, k-order Equivariant-
GNNs is bounded by the 1-WL test (Xu et al. 2019 Morris et al.
GNNs were introduced in Maron et al. (2018) requiring Onn)) memory and speed complexities. Although the complexity was improved to O(n²) memory and Onn²) respectively (Maron et al.
2019; Chen et al. 2019; Azizian & Lelarge 2020), it is still inefficient compared with the linear complexity of MP-GNNS.
Graph Positional Encoding. The idea of positional encoding, i.c. the notion of global position of pixels in images, words in texts and nodes in graphs, plays a central role in the effectiveness of the most prominent neural networks with ConvNets (LeCun et al., 1998), RNNs (Hochreiter & Schmidhuber] 1997), and Transformers (Vaswani et al., 2017). For GNNs, the position of nodes is more challenging due to the fact that there does not exist a canonical positioning of nodes in arbitrary graphs. Despite these issues, graph positional encoding are as much critical for GNNs as they are for ConvNets, RNNs and Transformers, as demonstrated for prediction tasks on graphs (Srinivasan & Ribeiro 2019 Cui et al.) 2021). Nodes in a graph can be assigned index positional encoding (PE). However, such a model must be trained with the n! possible index permutations or else sampling needs be done (Murphy al. 2019). Another PE candidate for graphs can be Laplacian Figenvectors (Dwivedi et al., 20200 Dwivedi & Bresson (021) as they form a meaningful local coordinate system, while preserving the global graph structure. However, there exists sign ambiguity in such PE as eigenvectors are defined up to 11, leading to 2 number of possible sign values when selecting & eigenvectors which a network needs learn. Similarly, the eigenvectors may be unstable due to eigenvalue multiplicities, You et al. (2019) proposed learnable position- embeddings based on random anchor sets of nodes, where the random selection of anchors has its limitations, which makes their approach less generalizable on inductive tasks. There also exists methods that encode prior information about a class of graphs of interest such as rings for molecules (Bouritsas et al. [2020; Bodnar et al. (02I) which make MP-GNNs more expressive. But the prior information regarding graph sub-structures needs to be pre-computed, and sub- sub-graph matching and counting require Onn)) for k-tuple sub-structure.
Transformer-basee GNNs. Although sparse MP-GNNS are very efficient, they are susceptible to the information bottleneck limitation (Alon & Yahav 2020) in addition to vanishing gradient (similar to RNNs) on tasks when long-rany interactions between far away nodes are critical. To overcome these limitations, there have been recent works that generalize Transformers to graphs (Dwivedi & Bresson 202T; Kreuzer et al., 202T Ying et al., 2021 Mialon et al., (02T) which alleviates the long-range issue as evverything is connected to everything". However, these methods either use non-lcarnable PEs to encode graph structure information (Dwivedi & Bresson 2021 Ying et al.] [021] Mialon al. 202T), or inject learned PEs to the Transformer network that relies on Laplacian eigenvectors (Kreuzer et al. 202T), thus inheriting the sign ambiguity limitation.
detailed review of the above research directions is available in the supplementary Section B We attempt to address some of the major limitations of GNNs by proposing novel architecture with consistent performance gains.
PROPOSED ARCHITECTURE
In this work, we decouple structural and positional representations to make it easy for the network to learn these two critical characteristics. This is in contrast with most existing architectures s.a. Dwivedi & Bresson (202I): Beani et al. (202T): Kreuzer et al. (02T) that inject the positional information into the input layer of the GNNs, and You et al. (2019) that rely on distance-measuree anchor sets of nodes limiting general, inductive usage. Given the recent theoretical results on the
importance of informative graph PE for expressive GNNs (Murphy et al., 2019 Srinivasan & Ribeiro 2019 Loukas 2020), we are interested in a generic framework that can enable GNNs to separate positional and structural representations to increase their expressivity. Section 3.1 will introduce our approach to augment GNNs with learnabl graph PE. Our framework can be used with different GNN architectures. We illustrate this ficxibility in Sections C.T and C.2 where the decoupling of structural and positional information is applied to both sparse MP- and fully-connected GNNs.
3

---

Published as a conference paper at ICLR 2022
3.1 GENERIC FORMULATION: MP- MP-GNNS-LSPP
Notation. Let EV, be a graph with V being the set of nodes and & the set of edges. The graph has = | nodes and E = | edges. The connectivity of the graph is represented by the adjacency matrix A E RRaxn where As = 1 if there exists an edge between the nodes and j; otherwise Ag 0. The degree matrix denoted D R"**, The node features and positional features for node i is denoted by h4 and p. respectively, while the features for an edge between nodes i and is indicated by ctj. A GNN model is composed of three main components; an embedding layer for the input features, a stack of convolutional layers, and a final task- bask-based layer, as in Figure [ The layers are indexed by l and = 0 denotes the input layer.
Standard MP-GNNs.
Considering a graph which has available node and edge features, and these are transformed at each layer, the update equations for a conventional MP-GNN layer are defined as:
MP-GNNs: : h
fn (b.. (hg) JEN, c)) hft .1 E
(1)
+ fe (n,, Ny. ol)) ott, .eg ER.
(2)
where fn and fa are functions with learnable parameters, and Nf is the neighborhood of the node i. The design of functions fa and fe depends on the GNN architecture used, see Zhou et al. (2020) for
review. As Transformer neural networks (Vaswani al., (017) are special case of MP-GNNs (Joshil 2020), Eq. ① can be simplified to encompass the original Transformers by dropping the edge features and making the graph fully connected.
Input features and initialization. The node and edge features at layer f = 0 are produced by a linear embedding of available input node and edge features denoted respectively by A." Rd, ei E R%: hg h 0 = LL (hr) = A h + a E IR, e Bd E Rdxds and a, 5 Idd are the learnable parameters of the linear layers.
a0 = (e)) = B in e + 6 E R&,, where A E Raxd,
Positional Encoding. Existing MP-GNNs that integrate positional information usually propose to concatenate the PE with the input node features, similarly to Transformers (Vaswani et al. 2017):
MP-GNNS-PEI PE:
1+1 = In (bh, (1g) JEN: )ex:: SttMMRR
(3)
2+1 = fe (h4, h5, Gig 4
Eij
I+1
.eyy E ER.,
(4)
with initial ,==0 = LLn
= D
+ d
E
(5)
p
and cj = LLo (c()) Bd Bue + 5 ER"
where ph" E R& is the input PE of node i, D E Rd)((.++), a E Rdd are parameters for the linear transformation. Such architecture merges the positional and structural representations together. It has the advantage to keep the same linear complexity for learning, but it does not allow the positional representation to be changed and better adjusted the task hand.
Decoupling position and structure in MP-GNNs. We decouple the positional information from the structural information such that both representations are learned separately resulting in an architecture with Learnable Structural and Positional Encodings, which we call MP-GNNs-LSPP. The layer update equations are defined as:
1 = In (1% ( JENG :66
MP-GNNS-
nett M MEER Rd
c fe (1i,h,;,e)) e.))
e Rd.
(8)
of = fo (ps. pl. (p/ JEM: c)), pft! .pf E
The difference of this architecture with the standard MP-GNNs is the addition of the positional representation update Eq. (9) along with the concatenation of these learnable PEs with the node structural features, Eq. 7 As we will see in the next section, the design of the message-passi function f, follows the same analytical form of fa but with the use of the tanh activation function to allow positive and negative values for the positional coordinates. It should be noted that the inclusion
4

---

Published as a conference paper at ICLR 2022
nodes: 24 unique RWPES.
unique
(a) ZINC molecule (val index 91)
(b) ZINC molecule (val index 212)
Figure 2:
Sample graph plots from the ZINC validation set with each node color in a graph represent- ing a unique RWPE vector, when & 24. The corresponding graph ids, the number of nodes in the graphs and the number of unique RWPEs are labelled against the figures.
of the edge features, efy in the or p update is optional as several MP-GNNs do not include edge features in their h updates. Nevertheless, the architecture we present is made generic to be used for future extensions in a convenient way.
Definition of initial PE. The choice of the initial PE is critical. In this work, consider two PEs: Laplacian PE (LapPH) and Random Walk PE (RWPE). LapPE are defined in Section B.. as P; LapPE Un. U...... Usk E IR*, LapPE provide a unique node representation and are distance- sensitive w.r.t the Euclidean norm. However, they are limited by the sign ambiguity, which requires random sign flipping during training for the network to learn this invariance (Dwivedi et al. 2020).
Inspired by [i et al. (2020b), we propose RWPE, PE based on the random walk (RW) diffusion process (although other graph diffusions can be considered s.a. PageRank (Mialon et al. 2021
Formally, RWPE are defined with k ststeps of random walk as:
p
RWPE
RW RW? - ... RW
R
(10)
where RW- -AD11 is the random walk operator. contrast of Li al. (220b)) which uses the full matrix RW;; for all pairwise nodes, adopt a low-complexity usage of the random walk matrix by considering only the landing probability suffer from the sign ambiguity of LapPE, the network is not required to learn additional invariance. RWPE provide a unique node representation under the condition that each node has a unique k-hop topological neighborhood for sufficient large k. This assumption can be discussed. If we consider synthetic strongly regular graphs like the CSL graphs (Murphy et al. 2019), then all nodes in a graph have the same RWPE for any ls value, since they are isomorphic by construction. However, despite RWPE being the same for all nodes in a graph, these PE are unique for each class of isomorphic graphs, resulting in a perfect classification of the CSL dataset, see Section A.I For graphs such as Decalin and Bicyclopentyl (Sato 2020), nodes which are not isomorphic receive different RWPE for 2 5, also in Section A Finally, for real-world graphs like ZINC molecules, most nodes receive a unique node representation for k 2 24, see Figure 2 for an illustration, where the two molecules have 100% and 71.43% unique RWPES respectively. Section A.3 presents a detailed study.
node to itself, i.e. RW., s. Note that these PE do not
Experimentally, we will show that RWPE outperform LapPE, suggesting that learning the sign invariance is more difficult (as there exist 2* possible sign flips for each graph) than not exactly having unique node representation for each node. As mentioned above for CSL, RWPE are related to the problem of graph isomorphism and higher-order node interactions. Precisely, iterating the random walk operator for suitable number of steps allows coloring non-isomorphic nodes, thus distinguishing several cases of non-isomorphic graphs on which the 1-WL test, and equivalently MP-GNNs, fail s.a. the CSL. Decalin and Bicyclopentyl graphs. We refer Section A.2 for formal presentation of the iterative algorithm. Finally, the initial PE of the network is obtained by embedding the LapPE or RWPE into d-dimensional feature vector:
Pi
t=0
(v,") CoP, + Rd. where CO E dx , TR..
(11)
Positional loss. As we separate the learning of the structual and positional representations, it is possible to consider specific positional encoding loss along with the task loss. A natural candidate
5

---

Published as a conference paper at ICLR 2022
is the Laplacian eigenvector loss (Belkin & Niyogi 2003 Lai & Osher 2014) that enforces the PE to form a coordinate system constrained by the graph topology. As such, the final loss function of MP-GNNs-LLPE is composed of two terms:
((x-tr) + Loss (p' (p'=L),
Loss = LLoSTask
(12)
where f== E Raxd p E R k is the dimension of learned PE, l = L is the final GNN layer, and a >> 0 an hyper-parameter. Observe also that we enforce the final positional vectors pf= have centered and unit norm with mean m))n(p(;*))
0, || 1, vk to better approximate the Laplacian
eigenvector loss defined by LossLaptig (p) = k trace (pe (p + 1|pTp p
IallE with A > 0 and
|| being the Frobenius norm.
3.2 INSTANCES OF LSPE WITH MP-GNNS AND TRANSFORMER GNNS
We instantiate two classes of GNN architectures, both sparse MP-GNNs and fully-comeectdd Trans- former GNNs using our proposed LSPE framework. For sparse MP-GNNs, we consider GatedGCN [Bresson & Laurent 2017) and PNA (Corso et al., (0200), while we extend the recently developed SAN (Kreuzer al., 2021) and GraphiT (Mialon et al. (021) with LSPE to develop Transformer- LSPE architectures. We briefly demonstrate here how GNN can be instantiated using LSPE (Eqs.
9
by developing GatedGCN-L.SE (Eqs. [4 Top). while the complete equations for the four models are defined in Section C of the supplementary material, given the space constraint.
GatedGCN-LSPE: Originally, GatedGCNs are sparse MP-GNNs equipped with a soft-attention mechanism that is able to learn adaptive edge gates to improve the message aggregation step of GCN networks Kippf & Welling 2017). Our proposed extension of this model with LSPE defined as:
h+1 e+1 tt GGateGCNN- (1,, e .....)) h Baxd ee E RRExd p E Raxd
(13)
with h = h ReLU BN (B A1
+ Σ
mh o Ag
))
(14)
P.
JEN(()
of eg ReLLU
(15)
s+1 = p + tanh (Cip) + Σ rh o Chpp).
p.
(16)
sEN(s)
where n/1 = σ (itt)/ (Ey))/ o (mly)) + <). = B + BBh + Bgef h4g elyy P Miz fi e
Rd Af, Ah E Rdx2d and BR, B BS, Cf, C² E Rdddd Notice the p-update in Eq. (6) follows the same analytical form as the h-update in Eq. (4) except for the difference in activation function, and omission of BN, which was not needed in our experiments.
NUMERICAL EXPERIMENTS
We evaluate the proposed MPGNNS- architecture on the instances of sparse GNNs and Transformer GNNs defined in Section 3.2 (all models are presented Section C using Py PyTcc (Paszke et al., 2019) and DGL (Wang et al. 2019) standard molecular benchmarks ZINC [rwin and
et [012))00)) DGBG-MOLTOXT
(Hu et al. (2220). ZINC and MOLTOX2I are of medium scale with 12K and 7.8K graphs respectively, whereas MOLPCBA is of large scale with 437.9K graphs. These datasets, each having a global graph-level property to be predicted, consist of molecules which are represented as graphs of atoms as nodes and bonds between the atoms as edges. Additionally, we evaluate our architecture on three non-molecular graph datasets to show the usefulness of L.PE.. on any graph domain in general, see Section Di the supplementary.
4.1 DATASETS AND EXPERIMENTAL SETTINGS
ZINC is a graph regression dataset where the property to be predicted for a graph is its constrained solubility which is a vital chemical property in molecular design (Jin et al. 2018). We use the 12,000 subset of the dataset with the same splitting defined in Dwivedi al. (220)) Mean Absolute Error

---

Published as a conference paper at ICLR 2022
(MAE) of the property being regressed is the evaluation metric. OGBG-MOLTOX21 is multi-task
binary graph classification dataset where a qualitative (active/inactive) binary label is predicted
against 12 different toxicity measurements for each molecular graph [Tox21 2014 Wu et al. 2018). We use the scaffold-split version of the dataset included in OGB (Hu et al. 2020 that consists of 7,831 graphs. ROC-AUC averaged across the tasks is the evaluation metric. OGBG-MOLPCBB is also multi-task binary graph classification dataset from OGB where an active/inactive binary label is predicted for 128 bioassays (Wang et al., 2012 Wu et al. 2018). It has 437,929 graphs with scaffold- and the evaluation metric is Average Precision (AP) averaged over the tasks.
To evaluate different instantiations of our proposed MPGNNs-LSPE, we follow the same bench- marking protocol in Dwivedi et al. (2020) to fairly compare several models on a fixed number of 500k model parameters, for ZINC. We relax the model sizes to larger parameters for evaluation on the two OGB datasets as observed being practised on their leaderboards (Hu et al. (020). The total size of parameters of each model, including the number of layers used, are indicated in the respective experiment tables, with the remaining implementation details included in supplementary Section E
4.2 RESULTS AND DISCUSSION
The results of all our experiments on different instances of LSPE along with performance without using PE are presented in Table [ whereas the comparison of the best results from Table [ with baseline models and SOTA is shown in Table 2 We now summarize our observations and insights.
Table I: Results the ZINC, OGBG-MOLTOX21 and OGBG-MOLPCBA datasets. All scores averaged over 4 runs with 4 different seeds. Bold: GNN's best score, Red: Dataset's best score.
Model
Init PE
LSPE
PosLass
1.
#Param
TestMAE s.d.
TrainMAEIsd.
Epochs
Epoch/Total
GatedGCN
x
16
504309
0.251 0.251 1.0.00
0,025
440.25
8. 8.76w/1.088 0.0hr
GatedGCN
LapPE
16
505011 1
0,202-+0.006
0,033++00003
426.00
8.91s/1
GatedGCN
RWPE
522870
0.0931100003
0.014110003
440.75
15.17s/1.999
GatedGCN
RWPE
/
16
522870
0.090-10.001
0.013:+00044
460.50
33.06s/4.39hr
ZINC.
PNA
16 369235
0.141110.004
0.020:10.003
451.25
79.67//1000hrr
PNA
RWPE
16
503061
0.095-40.002
0.022++0.02
462.25
127.69s/16.61hr
SAN
10 501314
0. 0.181++0.000
0,017++0.004
433.50
74.3
SAN
RWPE
10
588066
0.104:10004
0.016:+0.002
462.50
134,74s/17 23hr
GraphiT
x
10
501313
0. 181++00006
0.021+00000
493.25
63.544/9.7 33hhr
GraphiT
RWPE
x
10
588065
0.106:10.002
0.028:10.002
420.50
225.399/14.8411
Model
Init PE
LSPE
PosLoss
#Param
TestAUC+s.d.
TrainAUC+sdd
Epochs
Epoch/Total
GatedGCN
8
1003739
0.772-+00006
0,933++0.000
304.25
5. 5.122m.46hr
GatedGCN
LapPE
X
1004355
0.774+
0,921=00006
275.50
5.23s/0
GaledGCN
RWPE
X
8
1063821
0.775.10.003
0.906.10.003
246.50
5. 5.99w0.63hr
HOLIONE
PNA
5244849
0.755 008
0.876:t0.014
214.75
6.25w/0.38hr
PNA
RWPE
$357393
0..017
0.87110.000
215.50
7..1vr
PNA
RWPE
<
5357393
0.758:10.003
0.875:10.112
194.25
18.09s/1.077
SAN
10
957871
0.74410.007
0,9151100155
279.75
18.06s/1. 44hrr
SAN
RWPE
1051017
0.744+:0 008
0.918=20018
281.75
30.82s/2.84h
GraphiT
10
957870
0,743-+0.00
0.919=+0.023
276.50
16.73s/1.366
GraphiT
RWPE
1051788 10
0,746+10.010
0.934=00016
279.75
27. 27.922/2.57rr
Model
Init
LSPE
PosLoss
L
#Param
TestAP=s.d.
TrainAP
Epochs
Epoch/Totar Total
MOLPCBA
GatedGCN
8
1008263
0,262-+0.000
0,401+0.0057
190.50
149, 10.7.90//71111
GatedGCN
LapPE
x
X
8
1008879
0,266+000002
0.391=100003
177.00
152.94//8.290
GatedGCN
RWPE
x
8
1068721
0.267110002
0.403:10.006
181.00
206.43s/11 1.4he
PNA
x
6550839
0.279++0.00
0.448:10.004
129.25
174.75s/6.34hr
PNA
RWPE
x 4
6521029
0.284 0.002
0.383-10.000
320.00
201 101.0022..990 99hr
No PE results in lowest performance. In Ta the GNNs which do not use PE tend to give the worse performance on all the three datasets. This finding is aligned to the recent literature (Sec. B.2h that has guided research towards powerful PE methods for expressive GNNs. Besides, it can be observed that the extent of poor performance of models without PE against using a PE (LapPE or LSPE) is greater for ZINC than the two OGBG-MOL* datasets used. This difference can be explained by the fact that ZINC features are purely atom and bond descriptors whereas OGB-MOL* features consist additional information that is informative of e.g. if an atom is in ring, among others.
7

---

Published as a conference paper at ICLR 2022
Table 2: Comparison of our best LSPE results from Table _ with baselines and state-of-the-art GNNs
(Sec. A.4) on each dataset. For ZINC, all the scores in Table 2a are the models with the ~500k
parameters. The scores on OGBG-MOL * in Tables (2 and 2 are taken from the OGB project and its leaderboards (Hu et al. 2020), where models have different number of parameters.
7INC
OGRG-MOLPCHA
(b) OGBG-MOLTON2I
Model
Test MAE
Model
Test AP
Model
Test ROC-AUC
GCN
0.367=0.011
GCN
0.7529=0.00G
GIN
0.2266=:0. 0028
GAT
0.384=0.007
GIN-VN
0.2703:1000023
GatedGCN-LapPE
0.202=0.006
GCN-VN
0.7746=000086
DeeperGCN-VN
0.2781
GIN
0.7051
GT
0.226-11.014
GIN-VN
0.7757=0.002
PNA
0.2838+00.0033
SAN
0.039=0.006
GatedGCN
0.7743=000073
DGN
0.2885+1000030
Graphormer
0.122=0.006
PHC-GNN
0.294710.0026
GatedGCN
0.7754=0.0032
GatedGCN-LSPE
0.090=0.001
PNA-LSPE
0.2840:40.0211
LSPE boosts the capabilities of existing GNNs. Both sparse GNNs and Transformer GNNs are
improved significantly when they are augmented with LSPE having RWPE initial PE, see Table T For instance, the best GNN without PE for ZINC, i.c. PNA, gives an improvement of 32.62% (0.095 vs. 0.141) when LSPE is used to learn the structural and positional representations manner. On other GNNs, this boost is even higher, see GatedGCN-LSPP which shows gain of 64.14% (0.090 vs. 0.251). On MOLTOX21, PNA-LSPE improves 0.79% (0.761 vs. 0.755) over PNA while the remaining models show either minor gains or attain the same performance when not using PE. This consistent trend is also observed for MOLPCBA where LSPE boosts PNA by 1.79%.
decoupled
Sparse vs. Transformer GNNs. When we compare the performance of sparse GNNs (GatedGCN, PNA) against Transformer GNNs (SAN, GraphiT) augmented with LSPE in Table I the performance of the sparse GNNs is surprisingly better than the latter, despite Transformer GNNs being theoretically well-posed to counter the limitations of long-range interactions of the former. Notably, the evaluation of our proposed architecture, in this work, is molecular graphs local structures seems to be the most critical, diminishes the need of full attention. This also aligns with the insight put forward in Kreuzer et al.) (202T) where the SAN, a Transformer model, benefited less from full attention on molecules. Beyond molecular graphs, there may be other domains where Transformer GNNs could give better performance. but still these would not scale in view of the quadratic computational complexity. Indeed, it is important to notice the much lesser training times of sparse GNNs compared Transformer GNNs in Table 0
which the information among
LSPE improves the state-of-the-art for domain-agnose
GNNs. When we compare the best performing instantiation of the LSPE from Table [ with baseline GNN models from the literature on the three benchmark datasets, our proposed architecture improves the SOTA on ZINC, while achieving compacaeeea performance on remaining datasets, see Table 2 On ZINC, GatedGCN- I.SPE surpasses most baselines by large margin to give test MAF of 0.090 which is an improvement of 35.25% and 26.23% respectively over the two recent-mos Transformer based GNNs, SAN and Graphormer On MOLTOX21, GatedGCN- -SSE reports test ROC-AUC score of 0.7754 which is similar to the best baseline GIN (0.7757) that uses virtual node Finally, LSPE enables PNA to achieve comparable performance to SOTA on MOLPCBA while boosting its performance when no PE was used. We note here that ZINC scores can even be boosted beyond LSPE's SOTA when domain expertise is used (Bouritsas et al. 2020 Bodnar al. 2021) while Graphormer (Ying et al.) 202T) achieved the top score on MOLPCBA when pre-trained on a very large (3.8M graphs) dataset. To ensure fair comparison with other scores, we did not use these two results in Table 2
On Positional loss. It can be observed in Table that the positional loss Eq. 12 further pushes the best LSPE score on ZINC slightly from 0.093 to 0.090, while on MOLTOX2T it only improves the train score though obtaining comparable test performance. We will investigate a more consistent positional loss in a future work.
Finally, we would like to highlight the generic nature of our proposed architecture which can be applied to any MP-GNN in practice as demonstrated by four diverse GNNs in this work.
4.3 ABLATION STUDIES
Through ablation studies, we show i) the usefulness of learning positional representation every layer vs. simply injecting a pre-computed positional encoding in the input layer, and ii) the selection of the number of k for the steps in RWPE in the proposed L.SPE. architecture.
8

---

Published as a conference paper at ICLR 2022
Table 3: Comparing the final LSPE architecture against simpler models which add pre-computed PE at input layer (or final layer) of GNN, using GatedGCN model on ZINC. The column 'Final h' denotes whether only the node structural features are used as final node features (denoted by
h²), or are concatenated with (i) node positional features (denoted by [h ,"") at the final layer, (ii) pre-computed RWPE (denoted by [bt, RWPE).
Model
Init
LSPE
Final A
#Param
Test MAE+s.d.
Train MAE=s.d.
#Epochs
Epoch/ Noteh//Ttal
GatedGCN
16
504309
0,251-0.009
0.025+00005
440.25
8.76x/ .0Khr
GatsdGCN
LapPE
A
16
505011
0.202=0.006
0.033+00003
426.00
8.91s/1 22hr
GatedGCN
RWPE
505947
0.122.10.033
0.013.10.033
436.25
9.14k/1 28hrr
GatedGCN
[AS, RWPE)
515249 16
0.249-0.012
0.024
437,50
10.05</1 .55h
GatedGCN
LapPE
/
16
516722
0.202=0.008
0.032+000055
405.25
15.10s/1 84hr
GatedGCN
LapPF:
16
520734
0.196-00.008
0.023-10.004
454.00
15.22s/2.0hrr
GatedGCN
RWPE
44
16
518150
0.100-0.006
0.01810.012
395.00
15.09s/1.7330
GatsdGCN
RWPE
16
522870
0.093=0.003
0.014+0.003
440.75
15.17s/1 990h
Learning PE at every layer provides the best performance. In Table 3 GatedGCN-RWDD corre- sponds to the model where LapPE are replaced with k-dim pre-computed random walk features at the first layer, and the PE not updated in the subsequent layers. First, we observe significant leap in performance (from 0.202 to 0.122) when the RWPE are injected in place of LapPE at the first layer, suggesting that RWPE could encode better positional information in GNNs they not limited by the sign ambiguity of LapPE. See Section A. in the supplementary material for an example of RWPE's representation power. Note that the injection of RWPE at the final layer instead of the input layer gives poor performance. The reason behind the better performance of concatenating RWPE at the input layer is inform the GNN aggregation function of the node positions order to distinguish them in the case of graph symmetries like isomorphic nodes.
Now, if we observe the training performance, GatedGCN-RWi -WPE leads to an overfit on ZINC. However, when the positional representations are also updated, the overfit is considerably alleviated improving the test score to 0. 100. Finally, when we further fuse the learned positional features at the final layer with the structural features, Eq. (12). the model achieves the best MAE test of 0.093. This study justifies how the GNN model learns best when the positional representations can be tuned and better adjusted to the learning task being dealt with.
The choice of & steps to initialize RWPE. choosing suitable number of k steps for the random walk features that are used initial positional encoding in Section 3.J. This value k is also used to set the final dimension of the learned positional representation in the last layer. Numerical experiments show the best values of l: to be 20 and 16 for ZINC with GatedGCN-LSPE and (GBG-MOLTOXX2 with PNA-LSPE respectively, which are larger values from what was used in Li et al. (2220b) (k: 3, 4) where the RW features are treated as distance encoding. The difference of k value is due to two reasons. First, the proposed RWPE requires to use large k value to possibly provide a unique node representation with different k- k-hop neighborhoods. Second, Li et al. (2020b) not only uses Rw but also considers all pairwise Rw between nodes i and j in a larget set of nodes, which increases the computational complexity.
In Figure (see Scction A.5). we study the effect of
ij
5 CONCLUSION
This work presents a novel approach to learn structural and positional representations separately in a graph neural network. The resultant architecture, LSPE enables a principled and effective learning of these two key properties that make GNN representation even more expressive. Main design components of LSPE are - i) higher-order position informative random walk features as PE initialization, ii) decoupling positional representations at every GNN layer, and iii) the fusion of the structural and positional features finally to generate hybrid features for the learning task. We observe a consistent increase of performance across several instances of our model on the benchmark datasets used for evaluation. Our architecture is simple and universal to be used with any sparse GNNs or Transformer GNNs as demonstrated by two sparse GNNs and two fully connected Transformer based GNNs in our numerical experiments. Given the importance of incorporating expressive positional encodings to theoretically improve GNNs as seen in the recent literature, we believe this paper provides a useful architectural framework that can be considered when developing future models which improve graph positional encodings, for both GNNs and Transformers.

---

Published as a conference paper at ICLR 2022
ETHICS STATEMENT
In this work, we present an approach to improve neural network methods for graphs by considering efficient learnable positional encoding while keeping the linear complexity of the model w.r.t to number nodes. This improves the cost of training such models, as contrast to some previous works that improved GNNs at the cost of higher-order tensor computation. We discover another insight that the linear complexity models (sparse GNNs) can outperform quadratic complexity models (Transformers). Consequently, one beneficial impact of our work is that its use reduce GPU and computational resources, eventually contributing to minimizing the adverse effect of deep learning training on environment. However, the method propose belongs can be used on malicious applications since the internet and several of the processes in its ecosystem can be represented in form of graphs. To prevent such applications, ethical guidelines be and enforced which constraint the usage of our proposed model.
class of architectures that
REPRODUCIBILITY STATEMENT
The authors support and advocate the principles of open science and reproducible research. The algorithms and architectures proposed in this work are open-sourced repository with casy-to-use scripts to reproduce different experiments and evaluations presented. The tables included in the paper mention critical details on the number of layers and the total number of model parameters that trained. Similarly, the visualization and illustrations presented in the main paper as well as the supplementary material contain the exact details on the dataset examples (such as index) used. Finally, detailed table consisting of several hyperparameters used for the experiments are included in the supplementary. ensuring the reproducibility of the results discussed in this work.
free and public code
ACKNOWLEDGMENTS
XB is supported by NRF Fellowship NRFF2017-10 and BUSS-R-252-000-B97-133 This research is supported by Nanyang Technological University, under SUG Grant (0001).-00001). VPD would like to thank Andreea Deac for her helpful feedback, Quan Gan for his support on the DGL library, Gabriele Corso for answering questions related the PNA model, and Chaitanya K. Joshi for useful comments. Finally, the authors would like to thank the anonymous reviewers for their helpful suggestions and feedbacks.
REFERENCES
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. arXiv preprint urXiv:2006.05205, 2020,
Waiss Azizian and Marc Lelarge. Expressive power of invariant and equivariant graph neural networks. arXiv preprint arXiv:2006. / 55666, 2020.
Victor Bapst, Thomas Keck, A Grabska-Bard Barwinska, Craig Donner, Ekin Dogus Cubuk, Samuel Schoenholz, Annette Obika, Alexander WR Nelson, Trevor Back, Demis Hassabis, et al. Unveiling the predictive power of static structure in glassy systems. Nature Physics, 16(4):448-454 2020.
Dominique Beani, Saro Passaro, Vincent Létourneau, Will Hamilton, Gabriele Corso, and Pietro Liò. Directional graph networks. In International Conference on Machine Learning, pp. 748-758. PMLR, 2021.
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural compulation, 15(6): 1373-13177399 2003.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: methodological tour d' d'horizon. European Journal of Operational Research, 290(2):405-4211 2021.
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yu Guang Wang, Pietro Liò, Guido Montúfar, and Michael Bronstein. Weisfeiler and lehman go cellular: Cw networks. arXiv preprint arXiv:2106. /2575, 2021.
10

---

Published as a conference paper at ICLR 2022
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. arXiv preprint arXiv:2006.09252. 2020.
Xavier Bresson and Thomas Laurent. arXiv:/711.07553, 2017.
Residual
gated graph convnets.
arXiv preprint
Quentin Cappart, Didier Chételat, Elias Khalil, Andrea Lodi, Christopher Morris, and Petar Veličkovié. Combinatorial optimization and reasoning with graph neural networks. vrXiv:2102.09544 2021.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. Advances in neural information processing systems, 2019.
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems, 33, 2020.
Miles D Cranmer, Rui Xu, Peter Battaglia, and Shirley Ho. Learning symbolic physics with graph networks. arXiv preprint arXiv: (009://990008800000 2019.
Hejie Cui, Zijie Lu, Pan Li, and Carl Yang. On positional and structural node features for graph neural networks on non-attributed graphs. arXiv preprint arXiv:2107.01495, 2021.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In NIPS, 2016.
Austin Perrow-Pinion, Jennifer She, David Wong, Oliver Lange, Todd Hester, Luis Perez, Marc Nunkesser, Seongjae Lee, Xueying Guo, Peter W Battaglia, Vishal Gupta, Ang Li, Zhongwen Xu, Alvaro Sanchez- Gonzalzz,, Yujia Li, and Petar Veličković. Traffic Prediction with Graph Neural Networks in Google Maps. 2021.
Philipp Dufter, Martin Schmitt, and Hinrich Schütze. Position information in transformers: An overview. arXiv preprint arXiv:2102. 10990, 2021.
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs, In AAAI Workshop on Deep Learning on Graphs: Methods and Applications, 2021.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.00982 2020.
Charless Fowlkes, Serge Belongie, Fan Chung, and Jitendra Malik. Spectral grouping using the nystrom method. IEEE transactions on pattern analysis and machine intelligence, 26(2):214-225, 2004.
Thomas Gaudelet, Ben Day, Arian R Jamasb, Jyothish Soman, Cristian Regep, Gertrude Liu, Jeremy BR Hayter, Richard Vickers, Charles Roberts, Jian Tang, et al. Utilising graph machine learning within drug discovery and development. arXiv preprint arXiv:20/2.057/6. 2020.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference Machine Learning, pp. 1263-1272 PMLR, 2017.
William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31 International Conference on Neural Information Processing Systems, pp. 1025-1035, 2017.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735-1780, 1997.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.00663 2020.
11

---

Published as a conference paper at ICLR 2022
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pp. 448 456. PMLR. 2015.
John J Irwin, Teague Sterling, Michael M Mysinger, Erin S Bolstad, and Ryan Coleman. Zinc: a free tool discover chemistry for biology. Journal of chemical information and modeling, 52(7): 1757-1768, 2012.
Md Amirul Islam, Sen Jia, and Neil D. B. Bruce. How much position information do convolutional neural networks encode? International Conference on Learning Representations, 2020.
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. International conference on machine learning, pp. 2323-2332.
PMLR, 2018.
Chaitanya Joshi. Transformers are graph neural networks. The Gradient, 2020.
Amir Hosein Khasahmadi, Kaveh Hassani. Parsa Moradi, Leo Lee, and Quaid Morris. Memory- based graph networks. In International Conference Learning Representations, 2020. URL
https:// pttp://eepeeeeeeeeeeeeeemee net aeee//oouumiid-rlaaelllll
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
Devin Kreuzer, Dominique Beaini, William L Hamilton, Vincent Létournea,, and Prudencio Tossou. Rethinking graph transformers with spectral attention. arXiv preprint arXiv:2/06.03899, 2021.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Rongjie Lai and Stanley Osher. A splitting method for orthogonality constrained problems. Journal of Scientific Computing, 58(2):431 1119,14994000 2014.
Tuan Le, Marco Bertolini, Frank Noć, and Djork-Arné Clevert. Parameterized hypercomplex graph neural networks for graph classification. arXiv preprint arXiv:2103. 2021.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):227--2324 1998.
Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go deep as cnns? In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 9267-9276, 2019.
Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem. Deepergen: All you need to train deeper gens. arXiv preprint arXiv:2006.07739, 2020a.
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, 33, 2020b.
Yang Li, Buyue Qian, Xianli Zhang, and Hui Liu. Graph neural network-based diagnosis prediction. Big Data, 8(5):379-390, 2020c.
Andreas Loukas. What graph neural networks cannot learn: depth vs width. In International Conference on Learning Representations, 2020.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. arXiv preprint arXiv:1812.09902. 2018.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. arXiv preprint 1905v:1905.11133 2019.
Grégoire Mialon, Dexiong Chen, Margot Selosse, and Julien Mairal. Graphit: Encoding graph structure in transformers. arXiv preprint arXiv:2/06.055: 0566000000666.... 2021.
12

---

Published as a conference paper at ICLR 2022
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 5115-5124, 2017.
Federico Monti, Fabrizio Frasca, Davide Eynard, Damon Mannion, and Michael M Bronstein. Fake news detection on social media using geometric deep learning. arXiv preprint arXiv: 1902.06630. 2019.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4602-4609 4609, 2019.
Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. arXiv preprint arXiv:2007.08663, 2020.
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.
Moni Naor and Larry Stockmeyer. What can be computed locally? SIAM Journal on Computing, 24 (6):1259-1277, 1995.
Aditya Pal, Chantat Eksombatchai, Yitong Zhou, Bo Zhao, Charles Rosenberg, and Jure Leskovec. Pinnersage: Multi-modal user embedding framework for recommendations pinterest. In Pro- ceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2311-2320, 2020.
Jia Yu Pan, Hlung-Jeong Yang, Christos Faloutsos, and Pinar Duygulu. Automatic multimedia cross- modal correlation discovery. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 653-658, 2004.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32: 8026-8037, 2019.
Ryoma Sato. A survey the expressive power of graph neural networks. arXiv preprint arXiv:2003.04073 2020.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Approximation ratios of graph neural networks for combinatorial problems. In Advances in Neural Information Processing Systems, pp. 4081- 4090, 2019.
Balasubramaniam Srinivasan and Bruno Ribeiro. On the equivalence between positional node embeddings and structural graph representations. In International Conference on Learning Repre- sentations, 2019.
Jonathan M Stokes, Kevin Yang, Kyle Swanson. Wengong Jin, Andres Cubillos-Ruiz Nina M Donghia, Craig R MacNair, Shawn French, Lindsey Carfrae, Zohar Bloom- Ackerman,,,,,n,, et deep learning approach to antibiotic discovery. Cell, 180(4):688-702, 2020.
Sainbayar Sukhbaatar, Rob Fergus, et al. Learning Advances in neural information processing systems, 29:2244-2252, 2016.
communiiiionnni with backpropagation.
Tox21. Tox21 challenge. 2014. URL htt.lttppp//rrrppd..i..g///////s
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In NIPS, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
13

---

Published as a conference paper at ICLR 2022
Minjie Wang, Lingfan Yu, Da Zheng, Quan Gan, Yu Gai, Zihao Ye, Mufei Li, Jinjing Zhou, Qi Huang, Chao Ma, et al. Deep graph library: Towards efficient and scalable deep learning on graphs. 2019.
Yanli Wang, Jewen Xiao, Tugba O Suzek, Jian Zhang, Jiyao Wang, Zhigang Zhou, Lianyi Han, Karen Karapetyan, Svetlana Dracheva, Benjamin A Shoemaker, et al. Pubchem's 's bioassay database. Nucleic acids research, 40(D1):D400D441, 2012.
Boris Weisfeiler and Andrei Leman. The reduction of graph to canonical form and the algebra which appears therein. NTI Series, 2(9):12-16, 1968.
Wu, B Ramsundar, EN Feinberg, Gomes, C Geniesse, AS Pappu, K Leswing, and V Pande. Moleculenet: benchmark for molecular machine learning. chem sci 9: 513-530, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? In International Conference on Learning Representations, 2019.
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke. Di He, Yanming Shen, and Tie- Yan Liu. Do transformers really perform bad for graph representation? arXiv preprini (rXiv:2/06055246 2021.
Jiaxuan You, Rex Ying, and Jure Leskovec. Position-awand graph neural networks. In International Conference on Machine Learning, pp. 7134-7143. PMLR, 2019.
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. Al Open, 1:57-81, 2020.
14

---

Published as a conference paper at ICLR 2022
A SUPPLEMENTARY
A.1 DISTINGUISIIIGG NON-ISOMORPIIC GRAPHS USING RANDOM WALK FEATURES
The choice of the initial PE in our proposed architecture can be several based graph diffusion other related techniques. In this section, we study RWPE (Eqn. TÔp which we initialize with k-steps of random walk. Precisely
k-dim vector that encodes the landing probabilities of node to
itself in 1 to & steps. This initial PE vector for node is given by [RW;,, RW N:.. ...... RW R which is pre-computed before the model training. Here, we demonstrate that such PE vector can help distinguish i) structurally dissimilar nodes and ii) non-isomorphic graphs which 1-WL, and equivalently MP-GNNs, fail, thus illustrating the empirically powerful nature of MPGNNs-LSSE that relies on this choice of positional features initialization.
(11,
(11,
[WW]
0.0000
T0.0000
0.0000
00.0000
T0.0000
0.5533
0,2500
0.3500
0.0761
0,0000
0.0741
0.0938
0.0000
0.2099
[0.3846
0.1862
0.1406
0..1719
Figure 3: Left: Example 3-regular graph with nodes from Li et al. 2020b) where the nodes are structurally different and colored accordingly. The 4-dim initial RWPE vector is shown against the corresponding nodes with their respective colors. Right: Example pair of non-isomorphic graphs with 11 nodes and skip-links and 3 from Murphy et al. (2019). Each node in a graph gets the same 4-dim RWPE vector, and shown above in colors the respective graphs' RWPE vectors after averaging across all the nodes.
Hare, RW2
RW3
RW
RW33
0.0000
0.0000
0.0000
0.5000
0.0000
0.44444
T0.0000
0.0000
0.0000
0.4167
0.0000
0.0000
0.4167
0.3542
0.0000
0.0417
0.3542
0.3179
0.0117
0.2824
0.0000
0.0000
0..0417
Figure 4: A pair of non-isomorphic and non-regular graphs (Leff: Decalin, Right: Bicyclopentyl) from Sato (2020). The 5-dim initial PE vector is shown against the corresponding nodes with their respective colors.
We show the simulation of the nodes' initial RWPE vectors on three examples in Figure (Left), Figure 3 (Right), and Figure 4 where the graphs either do not have any node attributes (Figure 3 or have the same node attributes (Figure 4 where each node denotes a Carbon atom). When we apply MPGNNs the graph in (Left), each node will have the same feature representation regular graph without any node attributes. However, there are structurally 3 different kinds of nodes denoted by the same number of different colors. If we initialize the PE for these nodes for
it is
15

---

Published as a conference paper at ICLR 2022
random walk steps, observe that the nodes are being assigned the 4-dim feature vectors that is consistent to their initial structural roles in the graph, thus being distinguishable.
Similarly, Figure (Right) is pair of non-isomorphic graphs from the theoretically challenging and highly symmetric Circulant Skip Link (CSL) dataset from Murphy et al. (2019). can be noticed that every node in graph here has the same structural role the each node has edges with other nodes at same hops. However, in Sakip (11,2), 2), the edges are between nodes at 1, 2 hops whereas in (11, 3), the edges are between the nodes at 1, 3 hops, with 2 and 3 being the skip-links of the two graphs, respectively. In such a scenario, the node in the Gaip (11, 2) gets a different 4-dim initial PE than a node features are pooled to generate the graph feature vector.
3). thus helping eventually to distinguish the two graphs when these node
Finally, in Figure 4 a pair of non-isomorphic and non-regular graphs is shown from Sato (020)) that MPGNNs fail to distinguish. If we use 5 steps of Random Walk to initialize the node's s PE vector, we can observe that the two graphs can easily be distinguished. We note here that the random walk based PE initialization (RWPE) is close to one of the Distance Encoding instantiations used in Li et al. 2020bb). However, we do not require to consider pairwise scores RW between nodes and J and any sub-set of nodes from the original graph, thus making our method less computationally demanding.
A.2 RANDOM WALK PE FEATURE AND GRAPH ISOMORPHISM TEST
Similar to the 1-WL test for graph isomorphism WWeisfeiler & Leman 1968, Morris et al. 2019 Sato 2020), the RWPE can used as a node coloring algorithm to test two graphs are non-isomorphic, as described in Algorithm Note that this algorithm cannot guarantee that two graphs are isomorphic, like the WL test. However, our analysis in Section A. shows this algorithm to be strictly powerful than the 1-WL test the pairs of graphs in Figure (Right) and in Figure are not distinguishable by 1-WL. Although this increase in power is being achieved without the need of maintaining colors for tuple of nodes to encode higher order interactions (as in k-WL.), the algorithm's complexity is of O(k n²)) due to the matrix multiplication in Step 5 (b) and Step (c), compared to O(k n²?) of 1-WL, with & being the number of iterations until convergence.
Algorithm Algorithm to decide whether a pair of graphs are not isomorphic based on random walk landing probabilities of each node to itself.
Input: A pair of graphs G1 = Vi,Ei), G2 = (V2, E2 with n nodes and e edges in each graph. A Rax= and A R denote the adjacency matrices, D1 Ra and D2 E R=x* denote the degree matrices of graphs G1 and G2 respectively.
Output: Return thoniisomrpphic" if G, and G2 are not isomorphic else "possibly isomorphic".
1. (0) A,DT' R"xn
2. (0)) < A2D51 E RRnn
3. cu + M
(0)
Vue
4. d N:0)
Ve V/2
5. for ls 1,2, (until convergence to stationary distribution)
(a) if HASH (fch- R |uu E vill) * HASH (f(att)) E R | |UE vall) then
|
return "non-isomorphic"
(b) ((k M(-1) Raxx
(c) (k) N( R
(d) Cu append ((k) to o (k-1) Vu E Vi
(k)
(e) ((A)) + append (((k) (k-1) Vu E 1/2
6. return "possibly isomorphic"
where HASH is injective hash function and ({...) denotes multiset.
16

---

Published as a conference paper at ICLR 2022
A.3 STUDY OF LAPPE AND RWPE AS INITIAL PE
20
25
Number Lrscc
10
10
Namterr ofracees
(a) LapPE,
(b) RWPE, & 24
Figure 5: Plot of the number of nodes in graph vs. the number of unique PE for LapPE and RWPE. point in the plots represents graph the ZINC validation set (composed of 1000 graphs) where the r-axis is the number of nodes, the y-axis is the number of unique PEs and the point intensity is number graphs with the same pair (zr, y). Besides, Fig. 5a has 36-dim LapPE (trailing dims padded with zero for graph with < 36), and Fig. 5b has 24-dim RWPE.
nodes: 24 unique RWPES: 24
nodes: 21 unique RWPEs: 21
15.8
12.3
13
50
(a) ZINC molecule (val index 91)
(b) ZINC molecule (val index 967)
nodes: RWPEs:
nodes: 18 unique AWPEs: 13
(c) ZINC molecule (val index 212)
(d) ZINC molecule (val index 672)
Figure 6: Sample graph plots from the ZINC validation set with each node color in graph represent- ing unique RWPE vector, when A: = 24. The corresponding graph ids, the number of nodes in the graphs and the number of unique RWPEs are labelled against the figures.
Figure 5) visualizes the uniqueness of the node representation with LapPE and RWPE (which serve as initial PE of our network) using the ZINC validation set of 1000 real-world molecular graphs. If the
17

---

Published as a conference paper at ICLR 2022
initial PE is unique for each node in graph, then the graph lies on the straight diagonal line. Figure Sa shows the result for LapPE, all graphs lie on the diagonal line as Laplacian cigenvectors guarantee unique node coordinates in the Euclidean transformed space. Figure presents the result for RWPE. We observe that not all, but a large amount of ZINC molecular graphs stay close to the straight line, showing that most graphs have large amount of nodes with unique RWPE. For example, there 30 graphs with 24 nodes having 21 unique RWPE, equivalent to 87.5% of nodes with unique PE.
Additionally, we visualize four sample graph plots from the ZINC validation set in Figure where the first two graphs have completely unique RWPE features, while the next two graphs have partially unique RWPEs (71.43% and 72.22% respectively). The visualization assigns a unique node color for each unique RWPE representation. Therefore. graphs in Figures 6a and 6b are plotted with each node assigned to unique color based on their RWPE features, and graphs in Figures [6c] and 6d are represented with 10 and 13 unique colors respectively corresponding to their number of unique RWPE representations.. In particular, observe the green- shade colored nodes in Figure ( bottom-right) well as blue-shade (mid-left) and orange-
(top and (bottom-right) colored nodes in Figure 6d We can easily see that the nodes with the same color are isomorphic in the graph, i.c. their k-hop structural neighborhoods are the same for values & 2 11.
We remind that RWPE provides a unique node representation under the condition that each node have a unique k-hop topoloical neighborhood for sufficient large k. While this condition is experimentally true for most nodes, it is not always satisfied. But despite this approximation, for sufficiently large number k of random walk iterations, RWPE is still able to capture global higher-order positioning of nodes that is used as initial PE, and is beneficial to the proposed LSPE architecture as demonstrated by the gain of performance in several experiments.
A.4 MODELS USED FOR COMPARISON IN TABLE
As a complete reference, the different GNN baselines and SOTA models that are used for the comparison in Table 2 are Graph Convolutional Networks (GCN) (Kipf & Welling 2017). Graph Attention Networks (GAT) (Veličković et al., 2018), GatedGCN-LapPE (Bresson Laurent 2017]
Dwivedi et al.] 2020). Graph Transformer (GT) (Dwivedi & Bresson 2021). Spectral Attention Networks (SAN) (Kreuzer et al. 2021), Graphormer (Ying et al. (021). Graph Isomorphism Networks (GIN) (uu et al. (019),, DeeperGCN (Li al.) (020a). Principle Neighborhood Aggregation (PNA)
(Corso et al., 2020), Directional Graph Networks (DGN) (Beani et al. 2021) and Parameterized
Hypercomplex GNNs (PHC-GNN) (Le et 2021).
A.5 FIGURE FOR THE STUDY OF k STEPS IN RWPE (SECTION 4.3)
GatedGON-LSPE on ZINC (lower better)
PNA-LSPE on TOX21 (higher is better)
3.77
Test MAE
ROC-
12-
0.74
1:50
0.2
32
k
Figure 7: Test scores on selecting different values of k which used determine the number of iterative steps of RW in RWPE as well as the dimension of the learned PE at the final layer, Eqn. 12
B RELATED WORK IN DETAIL.
In this detailed section related work, we first review the limitations of existing MP-GNN architec- tures in terms of their theoretical expressiveness, suggesting possible improvements to make GNNs more powerful. Then, introduce number of non-leamed and learning techniques that can be studied under the umbrella of graph positional encoding. Finally, we highlight the recent develop- ments for generalizing Transformers graphs. Our aim connect meaningful innovations through
18

---

Published as a conference paper at ICLR 2022
the detailed background on these three research directions, the unification of which spearheaded the development of this work.
B.1 THEORETICAL EXPRESSIVITY AND WEISFEILER-LEMAN GNNS
Weisteiler-Leman test. The limitation of GNNs in failing to distinguish -on-isomorppic graphs was first carefully studied in Xu al. (2019) and Morris et al. (2019), ) based on the equivalence of MP-GNNs and the 1-WL isomorphism test (Weisfeiler & Leman 1968). As such, MP-GNNs may perform poorly on graphs that exhibit several symmetries in their original structure, such as node and edge isomorphisms (Murphy et al.) 2019 Srinivasan & Ribeiro, 2019). Besides, some messagg-passing functions may not be discriminative enough (Xu et al. 2019 Corso et al. 2020).
Equivariant GNNs. Graph Isomrrphism Networks (GINs) (Xu et al., 2019) were designed to be as maximally expressive as the original 1-WL. test (Weisfeiler & Leman 1968). However, the 1-WL test can fail to distinguish (simple) non-isomorppic graphs, thus requiring novel GNNs with more expressivity power. As the original 1-WL test only considers 2-tuple of nodes, i.c. the standard edges in a graph, natural approach improve the expressivity power of the 1-WL test is to examine higher-order interactions between nodes with k-tuple of nodes with & 2 3. To this end, k-order Equivariant-GNNs were introduced in Maron al. 2018). But these architectures require Onn*) memory and speed complexities. This is an important practical limitation as k = 3 is at least needed to design more powerful GNNs than GINs. Along this line, the most efficient WL-GNNs that have been proposed are in Maron et al. (2019); Chen et al. (2019); Azizian & Lelarge (022)). which have Onn)) memory and Onn)) speed complexities.
B.2 GRAPH POSITIONAL ENCODING
Importance of Positional Information. The idea of positional encoding, i.c. the notion of global position of pixels in images, words in texts and nodes in graphs, plays central role in the effectiveness of the most prominent neural networks with Conv Nets (LeCun et al., 1998). RNNs (Hochreiter & Schmidhuber] 1997), and Transformers (Vaswani et al.; (017). These architectures integrate structural and positional attributes of data when building abstract feature representations. For instances, ConvNets intrinsically consider regular spatial structure for the position of pixels (Islam al.) 2020 RNNs also build on the sequential structure of the word positions, and Transformers employ positional encoding of words (see Dufter et al.] (2021) for a review). For GNNs, the position of nodes is more challenging due to the fact that there does not exist a canonical positioning of nodes in arbitrary graphs. This implies that there is no obvious notion of global and relative position of nodes, and consequently no specific directions on graphs (like the top, down, left and right directions in images). Despite these issues, graph positional encoding are as much critical for GNNs as they are for ConvNets, RNNs and Transformers, as demonstrated for prediction tasks graphs (Srinivasan & Ribeiro 2019; Cui et al. 2021).
Index Positional Encoding. Loukas (020)) identified another cause of the limited expressivity of the standard MP-GNNs. Such GNNs do not have the capacity to handle anonymous nodes, i.c. nodes which do not have unique node features. This property turns out to be critical show that MP-GNNs can be universal approximators each node in the graph can be assigned to a unique or discriminating feature. The theorem results from an alignment between MP-GNNs and distributed local algorithms (Naor & Stockmeyer] 1995: Sato et al. 2019). In order to address the issue of anonymous MP-GNNs and improve their theoretical expressiveness w.r.t the WL test, Murphy et al. (2019) introduced Graph Relational Pooling. Their model assigns unique identifier to each node, defined by an indexing of the nodes. However, such model must be trained with the n! possible index permutations to guarantee higher expressivity, which is not computationally feasible. As consequence, during training, node indexing uniformly sampled from the n! possible choices in order for their network to learn to be independent to the choice of the index PE at test time. Similarly, random node identifier could be used for breaking the node anonymity. Yet, this PE also suffers from the lack of generalization for unseen graphs (Loukas 2020).
Laplacian Positional Encoding. Besides providing a unique representation for each node, meaning- ful graph PE should also be cormutation-invariaa and sestacce-sensttvv meaning that the difference between the PEs of two nodes far apart on the graph must be large, and small for two nodes nearby. Laplacian eigenvectors (Belkin & Niyogi 2003) appear to be good candidates for graph PE, belonging
19

---

Published as a conference paper at ICLR 2022
to the class of unsupervised manifold learning techniques. Precisely, they are spectral techniques that embed graphs into an Euclidean space, and are defined via the factorization the graph Laplacian A Ln 11111/2/0 AD-1/2 1/2 AU, where I, is the n x n identity matrix, A the n x n adjacency matrix, D the x degree matrix, and X n matrices A and U correspond to the eigenvalues and eigenvectors respectively. The complexity for computing this full factorization is (E23/2) and (n) with approximate Nystrom method (Fowlkes et al. 2004). Laplacian eigenvectors form meaningful local coordinate system, while preserving the global graph structure. As these eigenvectors hold the key properties of permutation-invariane uniqueness, computational efficiency and distance-aware w.r.t. the graph topology, they were proposed as graph PE (Dwivedi et al. 2020 Dwivedi & Bresson 202T). They also naturally generalize the positional encoding used in Transformers (Vaswani et al. 2017) to arbitrary graphs. The main limitation of this graph PE is the existence of sign ambiguity as eigenvectors are defined up to +1. This leads to 2 number of possible sign values when selecting k number of eigenvectors. In practice, we choose k S n eigenvectors given the manifold assumption, and therefore 2 is much smaller n! (the number of possible ordering of the nodes), and therefore smaller amount of ambiguities to be resolved by the network. During the training. eigenvectors are uniformly sampled at random between the 2 possibilities (Dwivedi et al. [2020] Kreuzer et al. 2021 in order for the network to learn to be invariant w.r.t the sign of the eigenvectors.
Other graph PE. Li et al. (020bb proposed the use of distance encoding (DE) as node attributes, and additionally as controller of message aggregation. DE captures relative distances between nodes in a graph using powers of the random walk matrix. The resulting GNN was shown to have better expressivity than the 1-WL test. However, the limitation on regular graphs, and the cost and memory requirement of using power matrices may prevent the use of this technique to larger graphs. Khasahmadi et al. 2020) used random walk with restart (Pan et al. 2004) as topological embeddings with the initial node features.
You et al. (2019) proposed learnable position-awan aware embeddings based on random anchor sets of nodes for pairwise nodes (or link) tasks. This work also seeks develop positional encoding that can be learned along with the structural representation within the GNN. However, the random selection of anchors has its limitations, which makes their approach less generalizable on inductive tasks.
Bouritsas et al. 2020); Bodnar et al. (0021) introduced hybrid GNNs based on the WL-test and the peessageppassingg aggregation mechanism. These networks use prior knowledge about class of graphs of interest such as rings for molecules and cliques for social networks. The prior information then encoded into MP-GNNs obtain more expressive models by showing that the such GNNs are not less powerful than the 3-WL test. They obtained top performance on molecular datasets but the prior information regarding graph sub-structures needs to be pre-computed, and sub- graph matching and counting require ((n²) ) for k-tuple sub- structrree Besides, complexity of the message passing process depends linearly w.r.t. the size of the sub-graph structure. Note that the core idea of substructure counting with e.g. the number of rings associated to an atom provides a powerful higher-order structural information to the network and can improve significantly the tasks related to substructure counting.
B.3 TRANSFORMER-BANE GNNS
MP-GNNs are GNNs that leverage the sparse graph structure as computational graph, allowing training and inference with linear complexity and making them scalable to medium and large-scale graphs. However, besides their low expressivity, these GNNs hold two important and well-identified limitations. Firstly, MP-GNNs are susceptible to the information bottleneck limitation a.k.a. over- squashing (Alon& & Yahav 2020) when messages from across distant nodes are aggregated to node. Secondly, long-range interactions between far away nodes can also be limited, and require multiple layers that can suffer from the vanishing gradient problem. These limitations are similar to the ones present in Recurrent Neural Networks (RNNs) (Hochreiter & Schmidhuber 1997). and can lead MP-GNNs to perform poorly on tasks where long-range intcractions are necessary.
To overcome these limitations, it seems natural to use Transformer networks (Vaswani et al. 2017) which alleviates the long-range issue as *everything is connected to everything" However, it was found that the direct adoption of full-graph operable Transformers perform poorly compared to MP-GNNG on graph structured datasets (Dwivedi & Bresson 202I). Besides, Transformer based GNNs require to replace (n) complexity with On²)). So these GNNs are limited to small graphs
20

---

Published as a conference paper at ICLR 2022
like molecules and cannot scale to larger ones like social graphs knowledge graphs. Dwivedi & Bresson (202T) designed a sparsely-connectee
architecture called GraphTransformer that reduces the complexity to ((E) by considering the graph topology instead of connecting each node to all other nodes, similar to GAT's (Veličković et al. 2018). Still, the GraphTranfformer was unable to outperform SOTA GNNs benchmark datasets. Along this line, [Kreuzer et al. (202T) recently proposed Spectral Attention Networks (SANs), a fully-graph operable Transformer model that improves TrashTrantformer (Dwivedi & Bresson 2021) with two contributions. First, the authors designed learnable PE module based on elffaateetionn applied to the Laplacian eigenvectors, and injected this resultant PE into the input layer of the network. Second, SANs separated the parameters for real edges and complementary (non-real) edges, enabling the model to process the available sparse graph structure and long-range node connections based on the Laplacian eigenvectors, inherently exhibits the limitation of sign ambiguity. Kreuzer et al. (202I) attempted at alleviating the sign ambiguity through another architecture named Edge- Wise LPE. However, the architecture's 's complexity being ( makes it a practically infeasible model. GraphiT (Mialon et al. 2021) and Graphormer (Ying et al. 2021) were also very recently developed as full-graph operable Transformers for graphs with the idea weigh (or, control) the attention mechanism based on the graph topology. Specifically, GraphiT employs diffusion geometry to capture short-range and long-range graph information, and Graphormer uses shortest paths. Altogether, these works exploit different relative positional encoding information to improve the expressivity of Transformers for graphs.
learnable manner. However, their learned PE,
C INSTANCES OF LSPE WITH SPARSE AND TRANSFORMER GNNS
C.I SPARSE GNNS WITH LSPE
In this section, we augment two MP-GNN architectures with learnable positional representation, namely GatedGCN (Bresson & Laurent 2017) and PNA (Corso et al. 2020)
C.1.1 GATEDGCN-ISPP
GatedGCNs (Bresson & Laurent 2017) are sparse MP-GNNs equipped with a soft-attention mech- anism that is able to learn adaptive edge gates to improve the message aggregation step of GCN networks (Kipf & Welling, 2017). We augment this model to develop GatedGCN-LSPE, defined as:
c+1 e+1 pet1 GatedGCN-
(f h E Bundd e E Exd P E Rad
(1
(17)
with h 2+1 = - + ReLU BN A
11 p
+ Σ
mh
h o 1
))
(18)
JEN(()
6+1 = E/ + ReLL 6j
(19)
p
I+1 pf + tanh (Cipf + Σ
n o Chpp).
(20)
SEN())
a (1h))
and v/y = Eyenay o (16y) +c¹
(21)
f/ = Bfh! + BBh + BBely.
(22)
where M e. rhy thy E Rd, Af: Rdxxdd and Bi, Bg, Ct, Cj E Bdxd
C.1.2 PNA LSPE
PNA (Corso et al. 2020 is a sparse MP-GNN model which uses a combination of node aggregators to overcome the theoretical limitation of single aggregator. We propose PNA-L.SP whose layer
21

---

Published as a conference paper at ICLR 2022
update equation is defined as: h p = PNA-LSPP c p.) h E BRxxdd cc E Exd .p Ruxd
(23)
with n1t1 = hy -.RLLUBBN BN (UN
MA
h
)))
(24)
JEA(())
Pi .+1 p + tanh (ig pl. - SEN(()
My (pt.
(25)
1 S(D,a=1) S(D,a=
and +
(26)
max min
where + is the principal aggregator designed in (Corso et al. 2020 LReLU stands for LeakyReLU activation, amd Uh, Up, M, and MA are linear layers (or multi-layer perceptrons) with learnable parameters.
C.2 TRANSFORMER GNNS WITH LSPE
The recently developed SAN (Kreuzer et al. 2021), GraphiT (Mialon et al. 2021) and Graphormer (Ying et al., 202T) are promising full-graph operable Transformers incorporating several methods to encode positional and structural features into the network. In the next sections, we expand these Transformer-basee networks with the proposed LSPE architecture.
C.2.1 SAN-LSPE
Like Transformers, Spectral Attention Networks (SAN) (Kreuzer et al. 202I) operate on full graphs although the network separates the parameters coming from existing edges and non-existing edges in the graph. Furthemore, the contribution of attentions from existing and non-existing edges are weighted by an additive positive scalar 7 which can be tuned for different tasks. SAN also considers a Learnable Positional Encoding (LPE) module which takes in Laplacian eigenvectors and transforms them into a fixed size PE with self-attention encoder. This PE is then used in the main architecture in manner similar to MP-GNNs PE as defined in Eq. (5). We propose to extend SAN by replacing
the LPE module with the LSPE architecture proposed in Section 3.1 where positional representation is learned in line with structural embedding at each GNN layer:
1 1+ et
++
(I,,e") ...... h E Baxd E Rxxxx
P E Baxd
(27)
with h,41 BN (I W/ ReLU (WI ((+))) Rd
(28)
he+1 BN [nξ + -(t+t) E CRR
(29)
H
k.k
a,t1 = 0e( 11 Σ
bj
ER.
(30)
k= JEV
Σ
ev wiy
kl
I4 exp(A kel) lo7 eexp(1 A6,
EfjjEE
Wij
(31)
if E
{
A q: ReeTT
diag
Je / 1 1 /a ER i
/ te ER ifjj
(32)
Ahi = 7 RT diag(
he
he Whe K
Qhe
Q Kh.e_
vhe
Whe E Rund
(33)
12
(1/
ht
he?
Qhe
Whke Rhee_
K Dhe
W E Ruxd
(34)
Df
22

---

Published as a conference paper at ICLR 2022
=c"== -h:0=e Raxxxd
(35)
"1 ||
kl Dag
and pt+t p + tanh (0%
Σ
w k.e pij""
pJ)
k,e)
E Rdd
(36)
Ejev
k=
exp(A
ifje if E
p,6s [
k.t =
It7 exp(
T4y
k.t
pajj
p.15)
(37)
k. = 4p diag
k
mii ) )b3 /
Vd ER
ifj
paj
(38)
kkae Ahit = qp k diag p.ij p.j
dd ER if
P.j
Oh of W kpe = of W
P.V. E Ruxdd
(39)
p.k.
Qhe W.e. Kb. =p W. ke
P.Q.
p.k. p
vkk = w' P.V E Raxd.
(40)
ch. = p.: Ch.0 = p.e E BRaxnx
(41)
where Wf, W E Rdxd, 0 O, E Raddd who Whe W Who W Whe E R2dxds, w.S W.y. W.ke Who ".Q P. p.V. p.Q. p.K: P.V. E Rdxde, W Wk. W W E Rdxds, and d2 - d/H the dimension of the htth head for total of H heads. BN denotes the standard Batch Normalization (Toffe & Szegedy 2013). Finally, we make the balance scalar parameter y 2 0 learnable (also clipping its range in [0, I) differently from (Kreuzer al. 2021 where its optimal value is computed by grid search.
W.k.t
C.2.2 GRAPHIT-LSPE
Similarly to SAN, GraphiT Miialon et al. 2021 is a full-graph operable Transformer GNN which makes use of the diffusion distance to capture short-range and long-range interactions between nodes depending of the graph topology. This pairwise diffusion distance is used as multiplicative weight to adapt the weight scores to the closeness farness of the nodes. For example, if two nodes are close on the graph, them the diffusion distance Kij will have a value close one, and when the two nodes are far away then the value of K,j will be small.
Unlike SAN, the GraphiT model does not consider separate parameters for existing and non-existing edges for a graph. However, following Kreuzer et al. (202I) and our experiments, separating the parameters for each type of edges showed to improve the performance. Therefore, original GraphiT architecture with learnable positional features and use two sets of parameters for the edges and the complementary edges to define GraphiT LSSP. The GraphiT-LSPP model uses the same update equation as SAN-LSPE except for the weight score which are re-defined to introduce the diffusion kernel:
augment the
Kij exp(A Kij exp(A
if E if
k. Wij
(42)
Following Miialon et al. 2021 the diffusion distance is chosen to be the p-step random walk kernel defined as K (I, graph Laplacian matrix respectively. Hyper-parameter controls the amount of diffusion with value
AA) E BB** where I, A E Rgan is the identity matrix and the
between [0.25, 0.50].
D EXPERIMENTS ON NON-MOLECULLR GRAPHS
We conduct experiments on 3 non-molecular graph datasets to demonstrate the effectiveness of the proposed LSPE architecture on any graph domain in general. We select GatedGCN as the GNN instance here. The datasets used are from the domains of social network (IMDB-BINARY and
23

---

Published as a conference paper at ICLR 2022
Table Results on the IMDB-MULTI, IMDB-BINARY and CIFARIO superpixels. All scores are averaged over 4 runs with 4 different seeds. On IMDB- each seed experiment is on 10-fold cross validation. Bold: GNN's best score. No PosLoss is used with LSPE. denotes the result is taken directly from Dwiieddi et al. 2020).
Dataset
Model
Init PE
LSPE
L
#Param
TestAcciisdd
TrainAceis.d.
Epochs
Epoch/Total
GatedGCN
4
87122
66.050+-6.631
67.769
115.85
0.45x00,150 15h
IMDB-B
GatedGON
RWPE
/
91470 4
5..025
72.166+
111.17
0.56g0. 19hr
GatedGCN
4
87139
45.767:1-4.908 9-66
47.725 1,803
109.18
0.55x00. 17h
IMDB-M
GatedGCN
RWPE
/
4
91483
3,9997
48.781
1.568
100.55
0.72g/0
GatedGCN
4
104357
67.312:1:.311
94.553:t 1,018
97.00
154. 154.15s/4.22h
CIFARIO
GatedGCN
RWPE
107237
70.858:00.66
78.616:: 1,006
185.00
68.51s/3.89hr
IMDB-MULTI (Morris et al., 2020 and image superpixels (CIFAR10 (Dwivedi et al. 2020 with graph classification being the prediction task.
IDBM-BINARY and HIDB-MULTY contain 1,000 and 1,500 graphs respectively which are ego- networks extracted from actor collaboration graphs. There are classes in MIDB-BINARY and classes in IMDB-MULT with the class denoting the genre of the graph. CIFARIO 10 is superpixel dataset of 60,000 graphs where each graph represents connectivity structure of the image superpixels nodes. There are 10 classes to be predicted as with the original CIFARIO image dataset (Krizhevsky ctt al. 2009).
In Table 4 show the advantage of using LSPE by instantiating GatedGCN-LSPP to train and evaluate on these non-molecular graphs. For evaluation and reporting of results, we follow the respective protocols specified in Morri et al., (2020); Dwivedi et al. (2020) while comparing two models on a dataset on the similar range of model parameters. In accordance with the molecular datasets (Section 4.2), we consistently observe performance gains each of the three datasets in Table This result further justifies the usefulness of LSPE to be applicable in general for representation learning on any graph domain.
E ADDITIONAL MODEL CONFIGURATION DETAILS
In Table 5 additional details on the hyperparameters of different models used in Table As for hardware information, all models were trained on Intel Xcon CPU ES-2690 v4 server having 4 Nvidia 10801i GPUs, with each single GPU running I experiment which equals parallel experiments on the machine at single time.
I are provided.
24

---

Published as a conference paper at ICLR 2022
Table 5: Additional hyperparamters for the models used in Table 1 is the dimension of PE, the steps of random walk if the PE is RWPE. / and is applicable to GraphiT (Sec. C.2.2). Init and Mín Ir the initial and final learning rates for the learning rate decay strategy where the Ir decays with reduce Factor if the validation score doesn't improve after the Patience number of epochs. o and À applicable when PosLoss is used (Eqn. T2.
Model
Init
LSPE
PosLoss
B
P
Init.Ir
Patience
Factor
Min
a
A
GatedGCN
0.5
GatedGCN
LapPE
8
le-3
25
0,5
le-6
GatedGCN
RWPE
20
le:3
25
0.5
le-6
GatedGCN
RWPE
le:3
0.5
1e-6
1e-1
ZINC
PNA
lo:3
25
0.5
1c-6
PNA
RWPE
/
le33
0.5
1e-6
SAN
3e-4
25
0.5
1c-6
SAN
RWPE
7e-4
25
0.5
1e-6
GraphiT
0.25
16
3e-4
25
0.5
1e-6
GraphiT
RWPE
16
0.25
16
7c-4
25
0.5
1c-6
Model
Init
LSPE
PosLoss
8
P
Init
Patience
Factor
Min Ir
GaledGCN
le:3
0.5
GatedGCN
LapPE
le-3
25
0.5
le-5
GatedGCN
RWPE
le.3
0.5
1e45
MOLTOXET
PNA
5e44
10
0.8
2e.5
PNA
RWPE
5e-4
0.8
20:5
RWPE
5o-4
0.8
2e-5
le-1
100
SAN
7e-4
25
0.5
le-6
SAN
RWPE
7e-4
25
0.5
1e.6
GraphiT
0.25
16
7e-4
25
0.5
le-6
GraphiT
RWPE
16
0.25
16
7e-4
25
0.5
1e-6
Model
LSPE
PosLosss
8
P
Init
Patience
Factor
Min
GatedGCN
le-3
0.5
GatedGCN
LapPE
le-3
25
0.5
le-4
GatedGCN
RWPE
/
1o.3
0.5
lc-4
PNA
5c-4
4
0.8
20-5
PNA
RWPE
16
5e-4
0.8
20:5
25


Reviews:
[{"review_id": "royrnpAbW2s", "reviewer": "Reviewer_ENFN", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "(Sorry, I re-organized the review to meet the guideline)\n\n### points \n(+) motivation sounds reasonable\n\n(+) easy read, appendix full of useful information and explanations\n\n(+) technical contents including formulations are easy to follow\n\n(-) Significance of experimental improvements: are they really significant? \n\n(-) Initialize of PE and the LSPE architecture, which item is important? \n\n### comments\n\nThe manuscript is easy-to-read. I feel no difficulty in understanding the discussions in the manuscript. \nAlso, the appendix provides many useful material to readers, an additional plus (excepting the Section C.2. it is quite complicated lines of equations). \nI am rather new to the PEs for GNNs, but the manuscript helps me understanding the current PE research status and how we can place this work in that context. \n\nI like the idea of allowing PE to be updated through layers. As the manuscript claims, the PE is an important cue to distinguish isomorphism in graphs, but the initial injection of PEs like in Eqs(4-6) is not powerful enough to obtain good embedding features. \nThe proposed formulation Eqs.(7-9) are clear to understand. \n\nThe discussions in Appendix A is powerful enough for me to feel \"in practice\" the RWPE will work fine, though the proposed RWPE(+LSPE) has no theoretical guarantee to distinguish isomorph nodes. \n\nMy main concern is related to the experimental results. \n\nTables 1,2: \nI agree that the LSPE works fine to reduce the regression MAEs on the ZINC dataset. \nHowever, the improvements in the remaining MOLTOX21 and the MOPCBA datasets seems marginal. \nConsidering the standard deviations (thank you authors to provide the s.d. !!), I'm not sure whether these improvements are statistically significant. \nGiven the current manuscript, I need to judge that the proposed LSPE is successful in show solid improvements against the existing PE works in the minority (1 out of 3) of datasets. \n\nSome ideas: \nOne is to conduct statistical tests on the current scores. If the LSPE obtains small p-values in the MOL datasets, then, it is great! \nAnother is to test more diverse datasets. If the LSPE is really powerful (I believe so), the LSPE will achieve clear score improvements in many additional datasets. \n\nPerhaps adding extra metrics to support the efficacy of the LSPE may improve the impression of the manuscript. \nFor example, report memory/space usages of the proposed model. \nOne important motivation for this research is a computational difficulty of stronger GNNs (than 1-WL). \nThen it may be beneficial to show that the existing approach actually does not work with larger graphs. \n\nTable 3:\nThe results in the Table 3 indicates that the choice of the initial PE (LapPE, RWPE) is much important than the LSPE updates. \nPerhaps it may be straightforward to emphasize the importance of the PE Initialization, not the LSPE architecture? \nIn my understanding, the current manuscript weighs more on the LSPE (e.g. the subsection \"contribution\" in Sec. 1 and Fig 1). \n", "summary_of_the_paper": "This paper is concerning the Positional Encoding (PE) for GNNs. \nPE augments the typical GNNs to distinguish isomorphic nodes. However, existing PE models such as Laplacian eigenvectors require huge computational resources.\nThis manuscript proposes LSPE that augments the input to the nodes AND the embedding vectors with PE elements. \nThe LSPE models iteratively updates the embedding for PEs, in addition to the node feature embeddings. \nThe update formula of the PE embedding is similar to those of the node feature embedding, thus the computational requirements of the LSPE does not . \nThe manuscript tests two ways of PEs, one is based on the Laplacian, and the other is based on the random-walk. The manuscript also proposes the PE=only loss to foster the training. \nExperimental results shows that the propose LSPE can improve the graph regression of the ZINC dataset greatly, and also can achieve some improvements in graph classification tasks on the MOLTOX21 and the MOLPCBA datasets.  \n", "summary_of_the_review": "I find the proposed idea reasonable and straightforward (in a positive manner). But I'm not fully sure the experimental results well support the claims. I also have a concern that the most influential time is the PE init., not the PE embed. update formulation. \n\n\n============================================\n\nAfter author feedbacks:\n\nI feel the answers from the authors are largely satisfactory. \n\nOther reviewers raise a concern about the novelty of the proposed methods. I agree that the novelty is minor. \n\nHowever, the experimental results and the statistical test reports indicate the strongness of the proposed framework in practice. \nAdditional experiments on other domains are a positive surprise. \nTherefore I modify the review score one step upward. ", "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": "cLpDt8pPEZk", "reviewer": "Reviewer_uyjX", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The paper discusses the important topic of how to better utilize the structure information in message-passing-based graph neural networks. The proposed structure and way to generate positional embeddings demonstrated good results on several datasets, however, it still lacks a thorough justification of where the improvement comes from and how each component contributes to the final quality.\n\n## Pros\nThe paper tackles the problem of injecting positional embeddings in GNNs, which is an important topic of effectively utilizing structure information. The separate feed-forward network of RWPE demonstrates improved accuracies and can be a simple add-on to multiple GNN structures. \n\n## Cons\n1. The paper proposes two major components: random walk position embeddings and a standalone feed-forward network to update the embeddings. While I think these two strategies are a good add-on to many basic GNN structures, I do feel there are some points that the first part is of limited novelty, and some points are not properly justified in the arguments and experiments.\nThe added LapEig makes the two options of LapEig and RWPE vague in their motivations. In fact, the trace loss: Tr(p^T\\Delta p) is enforcing the positional embeddings to resemble LapEig. While the authors claim that RWPE is better, I was wondering why having the positional embeddings in the “final” layer would contribute to a better output. If that would be the case, would simply appending these embeddings to the final layer give similar quality?\n2. The RWPE itself is not novel, as the authors have also pointed that the idea is inherited from a previous. However, the feed-forward network's effectiveness is not properly proved. Specifically, it is not clear whether the gain attributes to the specific structure instead of the added parameters of the feedforward network. That is, suppose, we have the newly added position embeddings, but without the p_i^{l+1} updating mechanism, will we still have the boost of quality? Moreover, the added positional embeddings are also adding more capacity to the network.\nMinor:\nTypo: Proposed Architecture: first sentence: make easy -> make it easy\nWhy the edge dimension in Equation (2) is of dimension d?\nThe argument of flipping signs in LapPE is not the full story of Laplacian decomposition. In fact, the eigen-vectors of the same eigen-values can be any bases in that subspace (instead of different signs/directions).\n", "summary_of_the_paper": "This paper proposes a framework that utilizes Random Walk Positional Embeddings (RWPE) as extra features to boost the performance of GNNs. In particular, positional embeddings are updated as a separate forward network in each layer. The framework has demonstrated improved quality by injecting its positional embeddings and feed-forward structures in several GNNs.\n", "summary_of_the_review": "The paper discusses new position embeddings and the feed-forward networks. However, the novelty of the first part is limited and the effectiveness of the second part is not properly justified.", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "aXTXRQIZsD", "reviewer": "Reviewer_E8yv", "summary": "", "questions": "", "limitations": "", "rating": 5, "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. consider postional embedding in GNNs, the proposed framework is very general and can be directly used in many existing GNNs.\n\n2. The design is simple, insert the positional embedding to current existing message passing function. And also update the positional embedding as well e.g., in Eq.(9). Some method like Lapalacian or Random Walk are used to initilize the positional embedding.\n\n3. The results are good in the experiements.\n\nWeaknesses:\n\n1. My big concern is that the motivation of positional embedding is not very strong. For example, Eq.(7) can do the similar thing as Eq.(9), just using the vector concatenation. As claimed in the paper, the main different is that the Eq.(9) use the tanh function. Does that mean the Tanh is key for the positional embedding? Experiments on different activation function may be more convicing.\n\n2. The author claim that \"PE as eigenvectors are defined up to ±1, leading to 2k number of possible sign values\". However,  the use of the tanh activation function to allow positive and negative values for the positional coordinates. Will the positive and negative sign also casue the same issue?\n\n3. Some other baselines can be comapred, like \nJiaxuan You, Rex Ying, and Jure Leskovec. Position-aware graph neural networks. In International\nConference on Machine Learning, pp. 7134–7143. PMLR, 2019.\n", "summary_of_the_paper": "In this work, the authors mainly focus on the node positinal embedding for GNN. The proposed positional embedding is geneal and can be applied to many GNNs.", "summary_of_the_review": "In summary, I think the proposed method is this work is very practical. It seems that using a simple positional embedding help a lot. However, it seems that the motivation is not very strong, like how to explain this positional embedding. ", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "JKxzv9VtXb7", "reviewer": "Reviewer_vVMd", "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\n* The problem of message passing neural networks(MPNNs) lacking positional information of nodes is well-motivated by molecules.\n* The Proposal is understandable & straightforward, with an affordable memory cost.\n* Well written and provides detailed related works.\n\nThe idea of decoupling structural and positional encodings in MPNNs while keeping in linear complexity is very simple yet a clear idea to me.  Also, the motivation of this paper is elucidated via molecules where learned node embeddings do not differentiate between positions. Finally, the related works section is well written and explains the problems in the GNN domain clearly.\n\n**Weaknesses**\n* I would expect more experiments on different domains (such as recommendation systems), not just for the molecular domain. \nIntroduced PosLoss does not introduce an important change to results at all. Thus, the existence of this newly introduced loss seems questionable.\n* Claim that achieving SOTA results for the ZINC dataset(12K graphs) seems questionable because [1] achieves a 0.074 MAE score. \n* For the large-scale graph dataset( around 430K graphs), OGBG-MOLPCBA, which is bigger in the number of graphs and more complicated in terms of learning, the benefits are questionable. It seems the choice of aggregation outweighs the effect of positional encoding[2,3]. \n\n\nMy main concern is that the paper claims it is doing more than the listed contributions. First of all, introducing loss for positional encodings seems not working at all. Second, the claim is that achieving SOTA results for the ZINC dataset(12K graphs) seemed false to me as there is a recent paper [1] achieving 0.074 mean-absolute error with edge features. Also, doing more experiments on different domains, I think, is needed to show that this works. Idea working on the molecular domain only does not imply that this idea works well. Experimenting on domains like knowledge graphs would be nice to see its results since the position of nodes also plays a significant role in that domain.\n\nFinally, the most important thing for me is the benefit of learning decoupled positional embeddings in graph neural networks. Graph neural network architectures such as Directional Graph Networks[2] and PHC-GNN[3] seem to outperform the proposed model on the OGBG-MOLPCBA dataset. Even leveraging LSPE on Principal Neighborhood Aggregation[4] gives incremental results. What if we add more aggregators to PNA or use different domains like in PHC-GNN? I would expect a discussion on why these methods outperform the proposed plan as I believe it is important to tell readers why these methods outperform yours. Overall, it is a good paper with a simple idea, but I would expect more reasoning on why this method can fail and more experiments on different domains.\n\n[1]Bodnar, Cristian, et al. \"Weisfeiler and Lehman go cellular: Cw networks.\" arXiv preprint arXiv:2106.12575 (2021).\n\n[2] Beaini, Dominique et al. “Directional Graph Networks.” ICML (2021).\n\n[3] Le, Tuan, et al. \"Parameterized hypercomplex graph neural networks for graph classification.\" arXiv preprint arXiv:2103.16584 (2021).\n\n[4] Corso, Gabriele, et al. \"Principal neighborhood aggregation for graph nets.\" arXiv preprint arXiv:2004.05718 (2020).", "summary_of_the_paper": "This paper introduces the idea of learning positional representations to enrich node representations of graph neural networks(GNN) to improve the representation power of message-passing graph neural networks(MPNNs) while keeping in linear complexity. ", "summary_of_the_review": "Overall, this paper tries to alleviate a significant problem in MPNNs. Still, limited experiments in a single domain and counter-intuitive results for OGBG-MOLPCBA and ZINC datasets make this paper’s contributions questionable.", "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": "0-hVHUnBgUd", "reviewer": "Reviewer_2bUV", "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": "Pros:\n- The idea of disentangling the positional representation is novel.\n- The empirical results are really impressive.\n- The paper is well-organized and the writing is good.\n\nConcerns:\n- The design of this method is complicated and may introduce more parameters. This may cause problems that the model may tend to overfit the data and make it unclear if the improvement comes from the increase of the number of parameters (I wonder why the #Param does not increase so much as listed in the tables as the sizes of A_i's in (14) all double?).\n- How the positional encoding proposed in the paper compares to relative positional encoding in GNN, e.g., that used in Graphormer (Ying et al. 2021)? And is it possible to further boost the performance by combining it?", "summary_of_the_paper": "This paper proposes to use a separate positional representation with its own loss function for graph representation learning and achieve impressive empirical results.", "summary_of_the_review": "The proposed method has strong motivation and empirical results and I vote for an acceptance.", "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": {}}]

Author rebuttal:

Meta-review: This work adds the positional encoding (akin to those in transformers, but adapted) to GNNs.
In their reviews, reviewers raised a number of concerns about this work, in particular, lack of novelty, lack of ablations to demonstrate the claims of the paper, lack of comparison to previous work (e.g., position-aware GNNS, Graphormer and GraphiT which would appear very related to this work), lack of motivation (e.g., the introduced positional loss do not actually improve performance), and whether the experimental results were really significant.
During the rebuttal, the authors replied to the reviews, to address. the concerns that they could. Of the reviewers, unfortunately only one reviewer elected to respond to the authors. It is disappointing that the four other reviewers did not respond and overall the reviewers did not discuss this paper further.

The authors chose to highlight privately to the AC that two reviewers who scored the paper unfavourably did not respond. The authors then argued this should be taken into account in the score (presumably to make acceptance more likely)--however, two favourable reviewers also did not respond (not highlighted by the authors). I understand this kind of private request to the AC to dismiss unfavourable reviews (especially if they do not respond) is becoming common--I find it unhelpful--I can see who and who has not responded.

Nonetheless, looking at the responses to the original concerns of the reviewers highlighted above, I believe the authors have adequately addressed the concerns of the reviewers. Therefore i recommend acceptance but only as a poster.
Decision: Accept (Poster)