Year: 2022

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 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. 1

heading: 1 INTRODUCTION
text: 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 connectivity. Experimentally, these architectures have shown great promises to be impactful in diverse domains such as drug design (Stokes et al., 2020; Gaudelet et al., 2020), social networks (Monti et al., 2019; Pal et al., 2020), traffic networks (Derrow-Pinion et al., 2021), physics (Cranmer et al., 2019; Bapst et al., 2020), combinatorial optimization (Bengio et al., 2021; Cappart et al., 2021) and medical diagnosis (Li et al., 2020c).
Most GNNs (such as Defferrard et al. (2016); Sukhbaatar et al. (2016); Kipf & Welling (2017); Hamilton et al. (2017); Monti et al. (2017); Bresson & Laurent (2017); Veličković et al. (2018); Xu et al. (2019)) are designed with a message-passing mechanism (Gilmer et al., 2017) that builds node representation by aggregating local neighborhood information. It means that this class of GNNs is fundamentally structural, i.e. 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 to 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 message-passing GNNs (MP-GNNs) fail to differentiate two nodes with the same 1-hop local structure. This restriction is now properly understood in the context of the equivalence of MP-GNNs with Weisfeiler-Leman (WL) test (Weisfeiler & Leman, 1968) for graph isomorphism (Xu et al., 2019; Morris et al., 2019).
1Code: https://github.com/vijaydwivedi75/gnn-lspe
The said limitation can be alleviated, to certain extents, by (i) stacking multiple layers, (ii) applying higher-order GNNs, or (iii) considering positional encoding (PE) of nodes (and edges). Let us assume two structurally identical nodes in a graph with the same 1-hop neighborhood, but different with respect to 2-hop or higher-order neighborhoods. Then, stacking several layers (Bresson & Laurent, 2017; Li et al., 2019) can propagate the information from a 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 is to compute higher-order node-tuple aggregations such as in WL-based GNNs (Maron et al., 2019; Chen et al., 2019); though these models are computationally more expensive to scale than MP-GNNs, even for medium-sized graphs (Dwivedi et al., 2020). An alternative technique is to consider a global positioning of the nodes in the graph that can encode a graph-based distance between the nodes (You et al., 2019; Dwivedi et al., 2020; Li et al., 2020b; Dwivedi & Bresson, 2021), or can inform about specific sub-structures (Bouritsas et al., 2020; Bodnar et al., 2021).
Contribution. In this work, we turn to the idea of learning positional representation that can be combined with structural GNNs to generate more expressive node embedding. Our main intent is to alleviate the lack of canonical positioning of nodes in 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 1, that enables GNNs to learn both structural and positional representations at the same time (thus named MPGNNs-LSPE). Alongside, we present a random-walk 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%). In our demonstrations, we formulate LSPE instances of both sparse GNNs, such as 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-GNNs with LSPE surpass the previous state-of-the-art (SOTA) on one dataset by a considerable margin (26.23%), while achieving SOTA-comparable score on the other two datasets. The architecture also shows 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.

heading: 2 RELATED WORK
text: In this section, we review briefly the three research directions theoretical expressivity of GNNs, graph positional encoding, and Transformer-based GNNs.
Theoretical expressivity and Weisfeiler-Leman GNNs. As the theoretical expressiveness of MPGNNs is bounded by the 1-WL test (Xu et al., 2019; Morris et al., 2019), they may perform poorly on graphs that exhibit several symmetries (Murphy et al., 2019), and additionally some message-passing functions may not be discriminative enough (Corso et al., 2020). To this end, k-order EquivariantGNNs were introduced in Maron et al. (2018) requiring O(nk) memory and speed complexities. Although the complexity was improved to O(n2) memory and O(n3) 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.e. 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 to be done (Murphy et al., 2019). Another PE candidate for graphs can be Laplacian Eigenvectors (Dwivedi et al., 2020; Dwivedi & Bresson, 2021) 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 ±1, leading to 2k number of possible sign values when selecting k eigenvectors which a network needs to learn. Similarly, the eigenvectors may be unstable due to eigenvalue multiplicities. You et al. (2019) proposed learnable position-aware 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., 2021) which make MP-GNNs more expressive. But the prior information regarding graph sub-structures needs to be pre-computed, and sub-graph matching and counting require O(nk) for k-tuple sub-structure.
Transformer-based 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-range interactions between far away nodes are critical. To overcome these limitations, there have been recent works that generalize Transformers to graphs (Dwivedi & Bresson, 2021; Kreuzer et al., 2021; Ying et al., 2021; Mialon et al., 2021) which alleviates the long-range issue as ‘everything is connected to everything’. However, these methods either use non-learnable PEs to encode graph structure information (Dwivedi & Bresson, 2021; Ying et al., 2021; Mialon et al., 2021), or inject learned PEs to the Transformer network that relies on Laplacian eigenvectors (Kreuzer et al., 2021), thus inheriting the sign ambiguity limitation.
A 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 a novel architecture with consistent performance gains.

heading: 3 PROPOSED ARCHITECTURE
text: 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 (2021); Beani et al. (2021); Kreuzer et al. (2021) that inject the positional information into the input layer of the GNNs, and You et al. (2019) that rely on distance-measured 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 learnable graph PE. Our framework can be used with different GNN architectures. We illustrate this flexibility in Sections C.1 and C.2 where the decoupling of structural and positional information is applied to both sparse MP-GNNs and fully-connected GNNs.
3.1 GENERIC FORMULATION: MP-GNNS-LSPE
Notation. Let G = (V, E) be a graph with V being the set of nodes and E the set of edges. The graph has n = |V| nodes and E = |E| edges. The connectivity of the graph is represented by the adjacency matrix A ∈ Rn×n where Aij = 1 if there exists an edge between the nodes i and j; otherwise Aij = 0. The degree matrix is denoted D ∈ Rn×n. The node features and positional features for node i is denoted by hi and pi respectively, while the features for an edge between nodes i and j is indicated by eij . 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-based layer, as in Figure 1. The layers are indexed by ` 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`+1i = fh ( h`i , { h`j } j∈Ni , e`ij ) , h`+1i , h ` i ∈ Rd, (1)
e`+1ij = fe ( h`i , h ` j , e ` ij ) , e`+1ij , e ` ij ∈ Rd, (2)
where fh and fe are functions with learnable parameters, and Ni is the neighborhood of the node i. The design of functions fh and fe depends on the GNN architecture used, see Zhou et al. (2020) for a review. As Transformer neural networks (Vaswani et al., 2017) are a special case of MP-GNNs (Joshi, 2020), Eq. (1) 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 ` = 0 are produced by a linear embedding of available input node and edge features denoted respectively by hini ∈ Rdv , einij ∈ Rde : h`=0i = LLh(h in i ) = A 0hini + a 0 ∈ Rd, e`=0ij = LLe(einij) = B0einij + b0 ∈ Rd, where A0 ∈ Rd×dv , B0 ∈ Rd×de and a0, b0 ∈ Rd are the learnable parameters of the linear layers. 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-PE : h`+1i = fh ( h`i , { h`j } j∈Ni , e`ij ) , h`+1i , h ` i ∈ Rd, (3)
e`+1ij = fe ( h`i , h ` j , e ` ij ) , e`+1ij , e ` ij ∈ Rd, (4)
with initial h`=0i = LLh ([ hini pini ]) = D0 [ hini pini ] + d0 ∈ Rd, (5)
and e`=0ij = LLe(e in ij) = B 0einij + b 0 ∈ Rd, (6)
where pini ∈ Rk is the input PE of node i, D0 ∈ Rd×(dv+k), d0 ∈ Rd 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 to the task at 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-LSPE. The layer update equations are defined as:
MP-GNNs-LSPE : h`+1i = fh ([ h`i p`i ] , {[ h`j p`j ]} j∈Ni , e`ij ) , h`+1i , h ` i ∈ Rd, (7)
e`+1ij = fe ( h`i , h ` j , e ` ij ) , e`+1ij , e ` ij ∈ Rd, (8)
p`+1i = fp ( p`i , { p`j } j∈Ni , e`ij ) , p`+1i , p ` i ∈ Rd, (9)
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-passing function fp follows the same analytical form of fh 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
of the edge features, e`ij in the h 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 as generic so as 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, we consider two PEs: Laplacian PE (LapPE) and Random Walk PE (RWPE). LapPE are defined in Section B.2 as pLapPEi = [ Ui1, Ui2, · · · , Uik ] ∈ Rk. LapPE provide a unique node representation and are distancesensitive 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 Li et al. (2020b), we propose RWPE, a 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-steps of random walk as:
pRWPEi = [ RWii,RW2ii, · · · ,RWkii ] ∈ Rk, (10)
where RW = AD−1 is the random walk operator. In contrast of Li et al. (2020b) which uses the full matrix RWij for all pairwise nodes, we adopt a low-complexity usage of the random walk matrix by considering only the landing probability of a node i to itself, i.e. RWii. Note that these PE do not suffer from the sign ambiguity of LapPE, so 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 a 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 k 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.1. For graphs such as Decalin and Bicyclopentyl (Sato, 2020), nodes which are not isomorphic receive different RWPE for k ≥ 5, also in Section A.1. Finally, for real-world graphs like ZINC molecules, most nodes receive a unique node representation for k ≥ 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.
Experimentally, we will show that RWPE outperform LapPE, suggesting that learning the sign invariance is more difficult (as there exist 2k 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 a 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 to Section A.2 for a formal presentation of the iterative algorithm. Finally, the initial PE of the network is obtained by embedding the LapPE or RWPE into a d-dimensional feature vector:
p`=0i = LLp(p PE i ) = C 0pPEi + c 0 ∈ Rd, where C0 ∈ Rd×k, c0 ∈ Rd. (11)
Positional loss. As we separate the learning of the structual and positional representations, it is possible to consider a specific positional encoding loss along with the task loss. A natural candidate
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-LSPE is composed of two terms:
Loss = LossTask
([ h`=L
p`=L
]) + α LossLapEig(p`=L), (12)
where h`=L ∈ Rn×d, p`=L ∈ Rn×k, k is the dimension of learned PE, ` = L is the final GNN layer, and α > 0 an hyper-parameter. Observe also that we enforce the final positional vectors p`=L to have centered and unit norm with mean(p`=L·,k ) = 0, ‖p`=L·,k ‖ = 1, ∀k to better approximate the Laplacian eigenvector loss defined by LossLapEig(p) = 1k trace ( pT∆p ) + λk
∥∥pT p − Ik∥∥2F with λ > 0 and ‖ · ‖2F 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-connected Transformer GNNs using our proposed LSPE framework. For sparse MP-GNNs, we consider GatedGCN (Bresson & Laurent, 2017) and PNA (Corso et al., 2020), while we extend the recently developed SAN (Kreuzer et al., 2021) and GraphiT (Mialon et al., 2021) with LSPE to develop TransformerLSPE architectures. We briefly demonstrate here how a GNN can be instantiated using LSPE (Eqs. (7-9)) by developing GatedGCN-LSPE (Eqs. (14-16)), 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 (Kipf & Welling, 2017). Our proposed extension of this model with LSPE is defined as:
h`+1, e`+1, p`+1 = GatedGCN-LSPE ( h`, e`, p` ) , h ∈ Rn×d, e ∈ RE×d, p ∈ Rn×d, (13)
with h`+1i = h ` i + ReLU ( BN ( A`1 [ h`i p`i ] + ∑
j∈N (i)
η`ij A`2 [ h`j p`j ])) , (14)
e`+1ij = e ` ij + ReLU ( BN ( η̂`ij )) , (15)
p`+1i = p ` i + tanh ( C`1p ` i + ∑ j∈N (i) η`ij C`2p`j ) , (16)
where η`ij = σ ( η̂`ij ) / (∑ j′∈N (i) σ ( η̂`ij′ ) + ) , η̂`ij = B ` 1h ` i + B ` 2h ` j + B ` 3e ` ij , h ` i , e ` ij , p ` i , η ` ij , η̂ ` ij ∈ Rd, A`1, A`2 ∈ Rd×2d and B`1, B`2, B`3, C`1, C`2 ∈ Rd×d. Notice the p-update in Eq. (16) follows the same analytical form as the h-update in Eq. (14) except for the difference in activation function, and omission of BN, which was not needed in our experiments.

heading: 4 NUMERICAL EXPERIMENTS
text: We evaluate the proposed MPGNNs-LSPE architecture on the instances of sparse GNNs and Transformer GNNs defined in Section 3.2 (all models are presented in Section C), using PyTorch (Paszke et al., 2019) and DGL (Wang et al., 2019) on standard molecular benchmarks – ZINC (Irwin et al., 2012), OGBG-MOLTOX21 and OGBG-MOLPCBA (Hu et al., 2020). ZINC and MOLTOX21 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 LSPE on any graph domain in general, see Section D in the supplementary.

heading: 4.1 DATASETS AND EXPERIMENTAL SETTINGS
text: 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 et al. (2020). Mean Absolute Error
(MAE) of the property being regressed is the evaluation metric. OGBG-MOLTOX21 is a 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-MOLPCBA is also a 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-split 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 benchmarking 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., 2020). 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.

heading: 4.2 RESULTS AND DISCUSSION
text: The results of all our experiments on different instances of LSPE along with performance without using PE are presented in Table 1 whereas the comparison of the best results from Table 1 with baseline models and SOTA is shown in Table 2. We now summarize our observations and insights.
No PE results in lowest performance. In Table 1, 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.2) 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.
LSPE boosts the capabilities of existing GNNs. Both sparse GNNs and Transformer GNNs are improved significantly when they are augmented with LSPE having RWPE as initial PE, see Table 1. For instance, the best GNN without PE for ZINC, i.e. PNA, gives an improvement of 32.62% (0.095 vs. 0.141) when LSPE is used to learn the structural and positional representations in a decoupled manner. On other GNNs, this boost is even higher, see GatedGCN-LSPE which shows a 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%.
Sparse vs. Transformer GNNs. When we compare the performance of sparse GNNs (GatedGCN, PNA) against Transformer GNNs (SAN, GraphiT) augmented with LSPE in Table 1, 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 on molecular graphs on which the information among 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. (2021) 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 to Transformer GNNs in Table 1.
LSPE improves the state-of-the-art for domain-agnostic GNNs. When we compare the best performing instantiation of the LSPE from Table 1 with baseline GNN models from the literature on the three benchmark datasets, our proposed architecture improves the SOTA on ZINC, while achieving SOTA-comparable performance on remaining datasets, see Table 2. On ZINC, GatedGCN-LSPE surpasses most baselines by a large margin to give a test MAE of 0.090 which is an improvement of 35.25% and 26.23% respectively over the two recent-most Transformer based GNNs, SAN and Graphormer. On MOLTOX21, GatedGCN-LSPE reports a test ROC-AUC score of 0.7754 which is similar to the best baseline GIN (0.7757) that uses virtual node (VN). 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 et al., 2021) while Graphormer (Ying et al., 2021) 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 1 that the positional loss Eq. (12), further pushes the best LSPE score on ZINC slightly from 0.093 to 0.090, while on MOLTOX21 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.

heading: 4.3 ABLATION STUDIES
text: Through ablation studies, we show – i) the usefulness of learning positional representation at 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 LSPE architecture.
Learning PE at every layer provides the best performance. In Table 3, GatedGCN-RWPE corresponds to the model where LapPE are replaced with k-dim pre-computed random walk features at the first layer, and the PE are not updated in the subsequent layers. First, we observe a 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 as they are not limited by the sign ambiguity of LapPE. See Section A.1 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 to inform the GNN aggregation function of the node positions in order to distinguish them in the case of graph symmetries like isomorphic nodes.
Now, if we observe the training performance, GatedGCN-RWPE 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 k steps to initialize RWPE. In Figure 7 (see Section A.5), we study the effect of choosing a suitable number of k steps for the random walk features that are used as initial positional encoding in Section 3.1. 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 k to be 20 and 16 for ZINC with GatedGCN-LSPE and OGBG-MOLTOX21 with PNA-LSPE respectively, which are larger values from what was used in Li et al. (2020b) (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 a large k value to possibly provide a unique node representation with different k-hop neighborhoods. Second, Li et al. (2020b) not only uses RWkii but also considers all pairwise RW k ij between nodes i and j in a target set of nodes, which increases the computational complexity.

heading: 5 CONCLUSION
text: 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.

heading: ETHICS STATEMENT
text: 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 the number of 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 can reduce GPU and computational resources, eventually contributing to minimizing the adverse effect of deep learning training on environment. However, the method we propose belongs to a class of architectures that 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 can be set and enforced which constraint the usage of our proposed model.

heading: REPRODUCIBILITY STATEMENT
text: The authors support and advocate the principles of open science and reproducible research. The algorithms and architectures proposed in this work are open-sourced in a free and public code repository with easy-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 are 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, a 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.

heading: ACKNOWLEDGMENTS
text: XB is supported by NRF Fellowship NRFF2017-10 and NUS-R-252-000-B97-133. This research is supported by Nanyang Technological University, under SUG Grant (020724-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 to 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.

heading: A SUPPLEMENTARY

heading: A.1 DISTINGUISHING NON-ISOMORPHIC GRAPHS USING RANDOM WALK FEATURES
text: The choice of the initial PE in our proposed architecture can be several based on graph diffusion or other related techniques. In this section, we study RWPE (Eqn. 10) which we initialize with k-steps of random walk. Precisely we use a k-dim vector that encodes the landing probabilities of a node i to itself in 1 to k steps. This initial PE vector for a node i is given by [RWii,RW2ii, . . . ,RW k ii] ∈ Rk 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 on which 1-WL, and equivalently MP-GNNs, fail, thus illustrating the empirically powerful nature of MPGNNs-LSPE that relies on this choice of positional features initialization.
We show the simulation of the nodes’ initial RWPE vectors on three examples in Figure 3 (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 on the graph in 3 (Left), each node will have the same feature representation as it is a 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 k = 4
random walk steps, we can 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 3 (Right) is a pair of non-isomorphic graphs from the theoretically challenging and highly symmetric Circulant Skip Link (CSL) dataset from Murphy et al. (2019). It can be noticed that every node in a graph here has the same structural role as the each node has edges with other nodes at same hops. However, in Gskip(11, 2), the edges are between nodes at 1, 2 hops whereas in Gskip(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 Gskip(11, 2) gets a different 4-dim initial PE than a node in Gskip(11, 3), thus helping eventually to distinguish the two graphs when these node features are pooled to generate the graph feature vector.
Finally, in Figure 4, a pair of non-isomorphic and non-regular graphs is shown from Sato (2020) that MPGNNs fail to distinguish. If we use 5 steps of Random Walk to initialize the node’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. (2020b). However, we do not require to consider pairwise scores RWkij between nodes i and j and any sub-set of nodes from the original graph, thus making our method less computationally demanding.

heading: A.2 RANDOM WALK PE FEATURE AND GRAPH ISOMORPHISM TEST
text: Similar to the 1-WL test for graph isomorphism (Weisfeiler & Leman, 1968; Morris et al., 2019; Sato, 2020), the RWPE can be used as a node coloring algorithm to test if two graphs are non-isomorphic, as described in Algorithm 1. Note that this algorithm cannot guarantee that two graphs are isomorphic, like the WL test. However, our analysis in Section A.1 shows this algorithm to be strictly powerful than the 1-WL test as the pairs of graphs in Figure 3 (Right) and in Figure 4 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 ∗ n3) due to the matrix multiplication in Step 5 (b) and Step 5 (c), compared to O(k ∗ n2) of 1-WL, with k being the number of iterations until convergence.
Algorithm 1 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 = (V1, E1), G2 = (V2, E2) with n nodes and e edges in each graph. A1 ∈ Rn×n and A2 ∈ Rn×n denote the adjacency matrices, D1 ∈ Rn×n and D2 ∈ Rn×n denote the degree matrices of graphs G1 and G2 respectively. Output: Return “non-isomorphic” if G1 and G2 are not isomorphic else “possibly isomorphic”.
1. M (0) ← A1D−11 ∈ Rn×n 2. N (0) ← A2D−12 ∈ Rn×n
3. c(0)u ← M (0)u,u ∀u ∈ V1 4. d(0)v ← N (0)v,v ∀v ∈ V2 5. for k = 1, 2, · · · (until convergence to stationary distribution)
(a) if HASH ( {{c(k−1)u ∈ Rk | u ∈ V1}} ) 6= HASH ( {{d(k−1)v ∈ Rk | v ∈ V2}} ) then
return “non-isomorphic” (b) M (k) ← M (k−1)M (0) ∈ Rn×n (c) N (k) ← N (k−1)N (0) ∈ Rn×n (d) c(k)u ← append M (k)u,u to c(k−1)u ∀u ∈ V1 (e) d(k)v ← append N (k)v,v to d(k−1)v ∀v ∈ V2
6. return “possibly isomorphic”
where HASH is an injective hash function and {{. . .}} denotes a multiset.

heading: A.3 STUDY OF LAPPE AND RWPE AS INITIAL PE
text: 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
initial PE is unique for each node in a graph, then the graph lies on the straight diagonal line. Figure 5a shows the result for LapPE, all graphs lie on the diagonal line as Laplacian eigenvectors guarantee unique node coordinates in the Euclidean transformed space. Figure 5b 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 a large amount of nodes with unique RWPE. For example, there are 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 6 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 a 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 6c (top and bottom-right) as well as blue-shade (mid-left) and orange-shade (bottom-right) colored nodes in Figure 6d. We can easily see that the nodes with the same color are isomorphic in the graph, i.e. their k-hop structural neighborhoods are the same for values k ≥ 11. We remind that RWPE provides a unique node representation under the condition that each node have a unique k-hop topological neighborhood for a sufficient large k. While this condition is experimentally true for most nodes, it is not always satisfied. But despite this approximation, for a 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.

heading: A.4 MODELS USED FOR COMPARISON IN TABLE 2
text: 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) (Veličković 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., 2021), Graph Isomorphism Networks (GIN) (Xu et al., 2019), DeeperGCN (Li et al., 2020a), Principle Neighborhood Aggregation (PNA) (Corso et al., 2020), Directional Graph Networks (DGN) (Beani et al., 2021) and Parameterized Hypercomplex GNNs (PHC-GNN) (Le et al., 2021).
A.5 FIGURE FOR THE STUDY OF k STEPS IN RWPE (SECTION 4.3)

heading: B RELATED WORK IN DETAIL
text: In this detailed section on related work, we first review the limitations of existing MP-GNN architectures in terms of their theoretical expressiveness, suggesting possible improvements to make GNNs more powerful. Then, we introduce a number of non-learned and learning techniques that can be studied under the umbrella of graph positional encoding. Finally, we highlight the recent developments for generalizing Transformers to graphs. Our aim is to connect meaningful innovations through
the detailed background on these three research directions, the unification of which spearheaded the development of this work.

heading: B.1 THEORETICAL EXPRESSIVITY AND WEISFEILER-LEMAN GNNS
text: Weisfeiler-Leman test. The limitation of MP-GNNs in failing to distinguish non-isomorphic graphs was first carefully studied in Xu et 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 message-passing functions may not be discriminative enough (Xu et al., 2019; Corso et al., 2020).
Equivariant GNNs. Graph Isomorphism 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-isomorphic graphs, thus requiring novel GNNs with more expressivity power. As the original 1-WL test only considers 2-tuple of nodes, i.e. the standard edges in a graph, a natural approach to improve the expressivity power of the 1-WL test is to examine higher-order interactions between nodes with k-tuple of nodes with k ≥ 3. To this end, k-order Equivariant-GNNs were introduced in Maron et al. (2018). But these architectures require O(nk) 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 (2020), which have O(n2) memory and O(n3) speed complexities.

heading: B.2 GRAPH POSITIONAL ENCODING
text: Importance of Positional Information. The idea of positional encoding, i.e. 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). 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 et 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 on graphs (Srinivasan & Ribeiro, 2019; Cui et al., 2021).
Index Positional Encoding. Loukas (2020) identified another cause of the limited expressivity of the standard MP-GNNs. Such GNNs do not have the capacity to handle anonymous nodes, i.e. nodes which do not have unique node features. This property turns out to be critical to show that MP-GNNs can be universal approximators if 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 a unique identifier to each node, defined by an indexing of the nodes. However, such a model must be trained with the n! possible index permutations to guarantee higher expressivity, which is not computationally feasible. As a consequence, during training, node indexing is 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, meaningful graph PE should also be permutation-invariant and distance-sensitive, 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
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 of the graph Laplacian ∆ = In −D−1/2AD−1/2 = UTΛU , where In is the n× n identity matrix, A the n× n adjacency matrix, D the n× n degree matrix, and n× n matrices Λ and U correspond to the eigenvalues and eigenvectors respectively. The complexity for computing this full factorization is O(E3/2) and O(n) with approximate Nystrom method (Fowlkes et al., 2004). Laplacian eigenvectors form a meaningful local coordinate system, while preserving the global graph structure. As these eigenvectors hold the key properties of permutation-invariant, uniqueness, computational efficiency and distance-aware w.r.t. the graph topology, they were proposed as graph PE (Dwivedi et al., 2020; Dwivedi & Bresson, 2021). 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 a sign ambiguity as eigenvectors are defined up to ±1. This leads to 2k number of possible sign values when selecting k number of eigenvectors. In practice, we choose k ≤ n eigenvectors given the manifold assumption, and therefore 2k 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 2k 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. (2020b) 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-aware embeddings based on random anchor sets of nodes for pairwise nodes (or link) tasks. This work also seeks to 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. (2021) introduced hybrid GNNs based on the WL-test and the message-passing aggregation mechanism. These networks use prior knowledge about a class of graphs of interest such as rings for molecules and cliques for social networks. The prior information is then encoded into MP-GNNs to 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 O(nk) for k-tuple sub-structure. 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.

heading: B.3 TRANSFORMER-BASED GNNS
text: 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. oversquashing (Alon & Yahav, 2020) when messages from across distant nodes are aggregated to a 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 interactions 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-GNNs on graph structured datasets (Dwivedi & Bresson, 2021). Besides, Transformer-based GNNs require to replace O(n) complexity with O(n2). So these GNNs are limited to small graphs
like molecules and cannot scale to larger ones like social graphs or knowledge graphs. Dwivedi & Bresson (2021) designed a sparsely-connected architecture called GraphTransformer that reduces the complexity to O(E) by considering the graph topology instead of connecting each node to all other nodes, similar to GATs (Veličković et al., 2018). Still, the GraphTransformer was unable to outperform SOTA GNNs on benchmark datasets. Along this line, Kreuzer et al. (2021) recently proposed Spectral Attention Networks (SANs), a fully-graph operable Transformer model that improves GraphTransformer (Dwivedi & Bresson, 2021) with two contributions. First, the authors designed a learnable PE module based on self-attention 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 in a learnable manner. However, their learned PE, based on the Laplacian eigenvectors, inherently exhibits the limitation of sign ambiguity. Kreuzer et al. (2021) attempted at alleviating the sign ambiguity through another architecture named Edge-Wise LPE. However, the architecture’s complexity being O(n4) 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 to 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.
C INSTANCES OF LSPE WITH SPARSE AND TRANSFORMER GNNS
C.1 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-LSPE
GatedGCNs (Bresson & Laurent, 2017) 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 (Kipf & Welling, 2017). We augment this model to develop GatedGCN-LSPE, defined as:
h`+1, e`+1, p`+1 = GatedGCN-LSPE ( h`, e`, p` ) , h ∈ Rn×d, e ∈ RE×d, p ∈ Rn×d, (17)
with h`+1i = h ` i + ReLU ( BN ( A`1 [ h`i p`i ] + ∑
j∈N (i)
η`ij A`2 [ h`j p`j ])) , (18)
e`+1ij = e ` ij + ReLU ( BN ( η̂`ij )) , (19)
p`+1i = p ` i + tanh ( C`1p ` i + ∑ j∈N (i) η`ij C`2p`j ) , (20)
and η`ij = σ ( η̂`ij )∑
j′∈N (i) σ ( η̂`ij′ ) + , (21)
η̂`ij = B ` 1h ` i +B ` 2h ` j +B ` 3e ` ij , (22)
where h`i , e ` ij , p ` i , η ` ij , η̂ ` ij ∈ Rd, A`1, A`2 ∈ Rd×2d and B`1, B`2, B`3, C`1, C`2 ∈ Rd×d.
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 a single aggregator. We propose PNA-LSPE whose layer
update equation is defined as: h`+1, p`+1 = PNA-LSPE ( h`, e0, p` ) , h ∈ Rn×d, e0 ∈ RE×d, p ∈ Rn×d, (23)
with h`+1i = h ` i + LReLU ( BN ( U `h [h`i p`i ] , ⊕
j∈N (i)
M `h ([ h`i p`i ] , e0ij , [ h`j p`j ]))), (24) p`+1i = p ` i + tanh ( U `p p`i , ⊕ j∈N (i) M `p ( p`i , e 0 ij , p ` j
)), (25) and ⊕ = [ I
S(D,α = 1) S(D,α = −1)
] ⊗  µσmax min , (26) where ⊕ is the principal aggregator designed in (Corso et al., 2020), LReLU stands for LeakyReLU activation, amd U `h, U ` p,M ` h and M ` p 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., 2021) 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-based networks with the proposed LSPE architecture.
C.2.1 SAN-LSPE
Like Transformers, Spectral Attention Networks (SAN) (Kreuzer et al., 2021) 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 γ, 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 a self-attention encoder. This PE is then used in the main architecture in a 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:
h`+1, p`+1 = SAN-LSPE ( h`, e0, p` ) , h ∈ Rn×d, e0 ∈ Rn×n×d, p ∈ Rn×d, (27)
with h`+1i = BN ( h̄`+1i +W ` 2 ReLU ( W `1 h̄ `+1 i )) ∈ Rd (28)
h̄`+1i = BN ( h`i + ĥ `+1 i ) ∈ Rd, (29)
ĥ`+1i = O ` ( Hn k=1 ∑ j∈V wk,`ij∑ j′∈V w k,` ij′ vk,`j ) ∈ Rd, (30)
wk,`ij =
{ 1
1+γ · exp(A k,` ij ) if ij ∈ E
γ 1+γ · exp(Ā k,` ij ) if ij 6∈ E
, (31)
{ Ak,`ij = q k,` i T diag(ck,`ij )k k,` j / √ dk ∈ R if ij ∈ E
Āk,`ij = q̄i k,`T diag(c̄k,`ij )k̄ k,` j / √ dk ∈ R if ij 6∈ E
(32)
Qk,` =
[ h`
p`
] W k,`Q , K k,`= [ h`
p`
] W k,`K , V k,`= [ h`
p`
] W k,`V ∈ Rn×dk (33)
Q̄k,` =
[ h`
p`
] W̄ k,`Q , K̄ k,`= [ h`
p`
] W̄ k,`K , V̄ k,`= [ h`
p`
] W̄ k,`V ∈ Rn×dk (34)
Ck,0 =e0W ke , C̄ k,0 =e0W̄ ke ∈ Rn×n×dk (35)
and p`+1i = p ` i + tanh ( O`p ( Hn k=1 ∑ j∈V wk,`p,ij∑ j′∈V w k,` p,ij′ vk,`p,j )) ∈ Rd, (36)
wk,`p,ij =
{ 1
1+γ · exp(A k,` p,ij) if ij ∈ E
γ 1+γ · exp(Ā k,` p,ij) if ij 6∈ E
, (37)
{ Ak,`p,ij = q k,` p,i T diag(ck,`p,ij)k k,` p,j/ √ dk ∈ R if ij ∈ E
Āk,`p,ij = q̄p,i k,`T diag(c̄k,`p,ij)k̄ k,` p,j/ √ dk ∈ R if ij 6∈ E
(38)
Qk,`p =p `W k,`p,Q, K k,` p =p `W k,`p,K , V k,` p =p `W k,`p,V ∈ Rn×dk (39)
Q̄k,`p =p `W̄ k,`p,Q, K̄ k,` p =p `W̄ k,`p,K , V̄ k,` p =p `W̄ k,`p,V ∈ Rn×dk (40)
Ck,0p =e 0W kp,e, C̄ k,0 p =e 0W̄ kp,e ∈ Rn×n×dk (41)
where W `1 ,W ` 2 ∈ Rd×d, O`, O`p ∈ Rd×d, W k,` Q ,W k,` K ,W k,` V , W̄ k,` Q , W̄ k,` K , W̄ k,` V ∈ R2d×dk , W k,`p,Q,W k,` p,K ,W k,` p,V , W̄ k,` p,Q, W̄ k,` p,K , W̄ k,` p,V ∈ Rd×dk , W ke , W̄ ke ,W kp,e, W̄ kp,e ∈ Rd×dk , and dk = d/H is the dimension of the kth head for a total of H heads. BN denotes the standard Batch Normalization (Ioffe & Szegedy, 2015). Finally, we make the balance scalar parameter γ ≥ 0 learnable (also clipping its range in [0, 1]) differently from (Kreuzer et al., 2021) where its optimal value is computed by grid search.
C.2.2 GRAPHIT-LSPE
Similarly to SAN, GraphiT (Mialon 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 a multiplicative weight to adapt the weight scores to the closeness or farness of the nodes. For example, if two nodes are close on the graph, them the diffusion distance Kij will have a value close to one, and when the two nodes are far away then the value of Kij 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. (2021) and our experiments, separating the parameters for each type of edges showed to improve the performance. Therefore, we augment the original GraphiT architecture with learnable positional features and use two sets of parameters for the edges and the complementary edges to define GraphiT-LSPE. The GraphiT-LSPE model uses the same update equation as SAN-LSPE except for the weight score which are re-defined to introduce the diffusion kernel:
wk,`ij = { Kij · exp(Ak,`ij ) if ij ∈ E Kij · exp(Āk,`ij ) if ij 6∈ E . (42)
Following (Mialon et al., 2021), the diffusion distance is chosen to be the p-step random walk kernel defined as K = (In − β∆)p ∈ Rn×n where In,∆ ∈ Rn×n is the identity matrix and the graph Laplacian matrix respectively. Hyper-parameter β controls the amount of diffusion with value between [0.25, 0.50].

heading: D EXPERIMENTS ON NON-MOLECULAR GRAPHS
text: 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
IMDB-MULTI (Morris et al., 2020)) and image superpixels (CIFAR10 (Dwivedi et al., 2020)) with graph classification being the prediction task.
IDBM-BINARY and IMDB-MULTI contain 1,000 and 1,500 graphs respectively which are egonetworks extracted from actor collaboration graphs. There are 2 classes in IMDB-BINARY and 3 classes in IMDB-MULTI with the class denoting the genre of the graph. CIFAR10 is a superpixel dataset of 60,000 graphs where each graph represents a connectivity structure of the image superpixels as nodes. There are 10 classes to be predicted as with the original CIFAR10 image dataset (Krizhevsky et al., 2009).
In Table 4, we show the advantage of using LSPE by instantiating GatedGCN-LSPE to train and evaluate on these non-molecular graphs. For evaluation and reporting of results, we follow the respective protocols as specified in Morris 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 on each of the three datasets in Table 4. This result further justifies the usefulness of LSPE to be applicable in general for representation learning on any graph domain.

heading: E ADDITIONAL MODEL CONFIGURATION DETAILS
text: In Table 5, additional details on the hyperparameters of different models used in Table 1 are provided. As for hardware information, all models were trained on Intel Xeon CPU E5-2690 v4 server having 4 Nvidia 1080Ti GPUs, with each single GPU running 1 experiment which equals to 4 parallel experiments on the machine at a single time.

Review summaries:
This paper is concerning the Positional Encoding (PE) for GNNs.  PE augments the typical GNNs to distinguish isomorphic nodes. However, existing PE models such as Laplacian eigenvectors require huge computational resources. This manuscript proposes LSPE that augments the input to the nodes AND the embedding vectors with PE elements.  The LSPE models iteratively updates the embedding for PEs, in addition to the node feature embeddings.  The update formula of the PE embedding is similar to those of the node feature embedding, thus the computational requirements of the LSPE does not .  The 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.  Experimental 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.   

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.