Rewiring with Positional Encodings for GNNs
Authors: Rickard Brüel Gabrielsson
Mikhail Yurochkin
Justin Solomon
Venue: Submitted to ICLR 2023 (2023)

Abstract: Several recent works use positional encodings to extend the receptive fields of graph neural network (GNN) layers equipped with attention mechanisms. These techniques, however, extend receptive fields to the complete graph, at substantial computational cost and risking a change in the inductive biases of conventional GNNs, or require complex architecture adjustments. As a conservative alternative, we use positional encodings to expand receptive fields to $r$-hop neighborhoods. More specifically, our method augments the input graph with additional nodes/edges and uses positional encodings as node and/or edge features. We thus modify graphs before inputting them to a downstream GNN model, instead of modifying the model itself. This makes our method model-agnostic, i.e. compatible with any existing GNN architectures. We also provide examples of positional encodings that are lossless with a one-to-one map between the original and the modified graphs. We demonstrate that extending receptive fields via positional encodings and a virtual fully-connected node significantly improves GNN performance and alleviates over-squashing using small $r$. We obtain improvements on a variety of models and datasets, and reach  state-of-the-art performance using traditional GNNs or graph Transformers.

Under review as a conference paper at ICLR 2023
REWIRING WITH POSITIONAL ENCODINGS FOR GNNs
Anonymous authors
Paper under double-blind review
ABSTRACT
Several recent works use positional encodings to extend the receptive fields of graph neural network (GNN) layers equipped with attention mechanisms. These techniques, however, extend receptive fields to the complete graph, at substantial computational cost and risking a change in the inductive biases of conventional GNNs, or require complex architecture adjustments. As a conservative alterna- tive, we use positional encodings to expand receptive fields to r-hop neighbor- hoods. More specifically, our method augments the input graph with additional nodes/edges and uses positional encodings as node and/or edge features. We thus modify graphs before inputting them to downstream GNN model, instead of modifying the model itself. This makes our method model-agnostic, i.e. compati- ble with any existing GNN architectures. We also provide examples of positional encodings that are lossless with a one-to-one map between the original and the modified graphs. We demonstrate that extending receptive fields via positional encodings and a virtual fully-connected node significantly improves GNN per- formance and alleviates over-squashing using small We obtain improvements on a variety of models and datasets, and reach state-of-the-art performance using traditional GNNs or graph Transformers.
INTRODUCTION
GNN layers typically embed each node of graph as function of its neighbors' (1-ring's 's embed- dings from the previous layer; that is, the receptive field of each node is its 1-hop neighborhood. Hence, at least stacked GNN layers are needed for nodes to get information about their r-hop neighborhoods. Barceló et (2020) and Alon and Yahav (2021) identify two broad limitations associated with this structure: reachine occurs when the number of layers is insufficient to communicate information between distant vertices, while over-squashing occurs when certain edges bottlenecks for information flow.
Inspired by the success of the Transformer in natural language processing (Vaswani et al., 2017), recent methods expand node receptive fields to the whole graph (Dwivedi and Bresson, 2021; Ying et al., 2021). Since they effectively replace the topology of the graph with that of a complete graph, these works propose positional encodings that communicate the connectivity of the input graph as node or edge features. As these methods operate on fully-connecter graphs, the computational cost of each layer is quadratic in the number of nodes, obliterating the sparsity afforded by conventional 1-ring based architectures. Moreover, the success of the 1-ring GNNs suggests that local feature aggregation a useful inductive bias, which has to be learned when the receptive field is the whole graph, leading to slow and sensitive training.
In this paper, we expand receptive fields from 1-ring neighborhoods to r-ring neighborhoods. where ranges from 1 (typical GNNs) to R, the diameter of the graph (fully-connected). That is, we augment a graph with edges between each node and all others within distance r in the input topol- ogy. We show that performance is significantly improved using fairly small and carefully-chosen positional encodings annotating this augmented graph. This simple but effective approach can be combined with any GNN.
Contributions. We apply GNN architectures to augmented graphs connecting vertices to their peers of distance Our contributions graph with positional encodings as edge and node features. (ii) We compare r-hop positional en- codings on the augmented graph, specifically lengths of shortest paths, spectral computations, and
follows: (i) We increase receptive fields using modified

---

Under review as a conference paper at ICLR 2023
powers of the graph adjacency matrix. (iii) We demonstrate that relatively small r-hop neighbor- hoods sufficiently increase performance across models and that performance degrades in the fully- connected setting.
2 RELATED WORK
The Transformer has permeated deep learning (Vaswani et al., 2017), with state-of-the-art perfor- mance in NI.P (Devlin et al., 2018), vision (Parmar al., 2018), and genomies (Zaheer al., 2020). Its core components include multi-head attention, an expanded receptive field, positional encodings, and a CLS-token (virtual global source and sink nodes). Several works adapt these constructions to GNNs. For example, the Graph Attention Network (GAT) performs attention over the neighborhood of each node, but does not generalize multi-head attention using positional encodings (Veličković et al., 2018). Recent works use Laplacian spectra, node degrees, and shortest-path lengths posi- tional encodings to expand attention to all nodes (Kreuzer et al., 2021; Dwivedi and Bresson, 2021; Rong al., 2020; Ying al., 2021). Several works also adapt attention mechanisms to GNNs (Yun et al., 2019; Cai and Lam, 2019 Hu et al.. 2020; Back et al., 2021; Veličković et al., 2018; Wang al., 2021b; Zhang et al., 2020: Shi al., 2021).
Path and distance information has been incorporated into GNNs more generally. Yang et al. (2019) introduce the Shortest Path Graph Attention Network (SPAGAN), whose layers incorporate path- based attention via shortest paths between center node and distant neighbors, using an involved hierarchical path aggregation method to aggregate a feature for each node. Like us, SPAGAN intro- duces the & k-hop neighbors around the center node as a hyperparameter; their model, however, has hyperparameters controlling path sampling. Beyond SPAGAN, Chen et (2019) concatenate node features, edge features, distances, and ring flags compute attention probabilities. Li et al. (2020) show that distance encodings (i.c., one-hot feature of distance as an extra node attribute) obtain more expressive power than the 1-Weisfeiler-Lehnee tional encodings to apply Transformers to graphs and operates on sampled subgraphs to handle large graphs (Zhang al., 2020). Yang al. (2019) introduce the Graph Transformer Network (GTN) for learning a new graph structure, which identifies "meta-paths" and multi-hop connections to learn node representations. Wang et (2021a) introduce Multi-hop Attention Graph Neural Network (MAGNA) that uses diffusion to extend attention to multi-hop connections. Frankel et al. (2021) extend GAT attention central node. Isufi et al. (2020) introduce EdgeNets, which enable flexible multi-hop diffusion. Luan et al. (2019) generalizes spectral graph convolution and GCN in block Krylov subspace forms.
test. Graph-BERT introduces multiple posi-
eechattically-samplle neighborhood of neighbors within 5-hops of the
Each layer of our GNN attends to the r-hop neighborhood around each node. Unlike SPAGAN and Graph-BERT, our method is model agnostic and does not perform sampling, avoiding their sampling-ratio and number-of-iteration ticular graph structure. Broadly, our approach does not require architecture or optimization changes. Thus, work also joins trend of decoupling the input graph from the graph used for information propagation (Veličković, 2022). For scalability, Hamilton et al. (2017) sample from a node's local neighborhood generate embeddings and aggregate features, while Zhang al. (2018) sample to deal with topological noise. Rossi et al. (2020) introduce Scalable Inception Graph Neural Networks (SIGN), which avoid sampling by precomputing convolutional filters. Kipf and Welling (2017) pre- process diffusion on graphs for efficient training. Topping et al. (2021) use graph curvature to rewire graphs and combat over-squashing and bottlenecks.
hyperparameters. Unlike GTN, we do not restrict to par-
In contrast, our work does not use diffusion, curvature, or sampling. but expands receptive fields via manssformer-nnspire positional encodings. In this sense, we avoid the inductive biases from pre-defined notions of diffusion and curvature, and since we do not remove connectivity, injective lossless changes are easy to obtain.
PRELIMINARIES AND DESIGN
Let G EV,E,fu fe) denote graph with nodes V N, and edges E V V, and let G be the set of graphs. For each graph. let functions fo V Rd. and fe E Rd denote node and edge features, respectively. We consider learning on graphs, specially node classification and graph classification. At inference, the input is graph G. For node classification, the task is to predict
2

---

Under review as a conference paper at ICLR 2023
node label (v) E R for each vertex e V. Using the node labels, the homophily of graph is defined as the fraction of edges that connect nodes with the same labels (Ma et al., 2022). For graph classification, the task is to predict label la IR for the entire graph G.
Given the tasks above, GNN architectures typically ingest a graph G = f. fc) and output either label or per-node feature. One view these as an abstraction; e.g. GNN for graph classification is a map FB G + IR" with learnable parameters A. These architectures vary in terms of how they implement Pa. Some key examples include the following: (i) Spatial models (Kipf and Welling, 2017) use the graph directly, computing node representations in each layer by aggregating representations of a node and its neighbors (1-ring). (ii) Spectral models (Bruna al., 2014) use the eigendecomposition of the graph Laplacian to perform spectral convolution. (iii) Diffusion models (Wang et al., 2021a; Klicpera et al., 2019) use weighted sums of powers of the adjacency matrix to incorporate larger neighborhoods (r-hops). (iv) In Transformers (Kreuzer et al., 2021; Dwivedi and Bresson, 2021; Rong et al., 2020; Ying et al., 2021), each node forms a new representation by self-attention over the complete graph (R-hop neighborhood) using positional encodings. These approaches incorporate useful inductive biases while remaining flexible enough to learn from data.
Spatial models have been extremely successful, but recent work shows that they struggle with under- reaching and over- werrssqushing (Alon and Yahav, 2021). Spectral approaches share similar convolu- tional bias spatial models and face related problems (Kipf and Welling, 2017). On the other hand, Transformers with complete attention and diffusion aim to alleviate the shortcomings of spatial models and show promising results. Due to complete attention, Transformers carry little inductive bias but are also computationally expensive. Diffusion explicitly incorporates the inductive bias that distant nodes should be weighted less in message aggregation; limiting its breadth of applicability.
We alleviate under-reaching and over-squashing while avoiding the computational load of complete attention by incorporating more general proximity bias than diffusion without committing a specific model. Our method is built on the observation that Fe can be trained to ingest modified versions of the original graph that better communicate structure and connectivity. Hence, we add new edges, nodes, and features to the input graph. To still convey the original topology of the input graph, we add positional encodings. More formally, we design functions g : 9 G that modify graphs and give features to the new nodes and edges. These functions can be prepended to any GNN Fo: G + R" as Fg o g: g + R".
The following are desiderata informing our design of g: (i) ability to capture the original graph, (ii) ability to incorporate long-range connections, (iii) computational efficiency, and (iv) minimal and flexible locality bias. By using positional encodings and maintaining the original graph G as subgraph of the modified graph, we capture the original graph in our modified input (Section 4.2.1). By expanding the receptive field around each node r-hop neighborhoods we reduce computational load relative to complete-grann attention, with limited inductive bias stemming from proximity. Additionally, expanded receptive fields alleviate under-reaching and over-squashing (Section 6.1).
4 APPROACH
We modify graphs before inputting them downstream GNN model, instead of modifying the model itself. Our approach does not remove edges or nodes in the original graph but only adds elements. Given input G EV, fu, fe), we create new graph G' (V', E" f',, ft) such that G is a subgraph of G". Expanded receptive fields are achieved in G' by adding edges decorated with positional encodings as node or edge attributes: we also add a fully-connected CLS node. G' is still graph with node and edge attributes to which we may apply any GNN. This process is represented by a function g : G + G. We decompose the construction of g into topological rewiring and positional encoding, detailed below. In slight abuse of notation, we will subsequently use G to denote only the subset of graphs relevant to given machine learning problem. For example, for graph regression on molecules, G denotes molecule graphs, with atoms as nodes and bonds as edges.
4.1 TOPOLOGICAL REWIRING
We modify the input graph G generate G' in two steps:
3

---

Under review as a conference paper at ICLR 2023
Expanded receptive field. Given graph G (V, E. fe: E 9 and positive integer r N.. add edges between all nodes within r hops of each other in G to create G. = (V,E', f.. If G is annotated with edge features, we assign to each edge in E E an appropriate constant feature C..
CLS node. Following Gilmer et al. (2017), we also include a "CLS"- classification node to graph connected to all others. We follow this procedure: Given graph G, we (i) initialize new graph G" (V", E", f') = G. (ii) add a new node UCLS to V and (iii) set f. ("Cts) := C. for a constant C.. Finally, we set E" == E Uvev ((vCss vers), with f'(((cIs)
[',(U, vCIs)) := C.. where C. is defined above.
4.2 POSITIONAL ENCODINGS
Given only the connectivity of a rewired graph G. E'', from the two-step procedure above, it may not be possible to recover the connectivity of the original graph G = EV E, fer fe). In the extreme, when is large and G' connected, G could become fully-connected, meaning that all topology is rest-removing the central cue for graph- learning. To combat this, we encode the original topology of G into GK, via positional encodings, which are node and/or edge features. We consider several positional encoding functions for edges Pr. G x V" x V + R" or nodes pv G V + IR",, appending the output of Pe as edge or Pv as node features to G, Section 4.2.1 lays out properties to compare choices of Pa and/or p.. Then, Section 4.2.2 provides concrete positional encodings compared in our experiments that trade off between the properties we lay out.
4.2.1 PROPERTIES OF POSITIONAL ENCODINGS
There are countless ways encode the subgraph topology of G within G' in vertex features Pa or edge features Pe- Below, we state a few properties we can check to give a framework for comparing the capabilities and biases of possible choices.
Lossless encoding, While GNN can ignore information in input G', it cannot reconstruct informa- tion that has been lost in constructing G' from G. Yet, there can be benefits in forgetting information, e.g. when dealing with noisy graphs or incorporating stronger inductive bias (Rossi et al., 2020; Klicpera al., 2019). That said, a simple property to check for G' equipped with positional encod- ing features Pe, Pe is whether we can recover G from this information, that is, whether our encoding is lossless (or -on-invasive). As long as it is possible to identify G within g(G), g is an injection and non-invasive. Hence, sufficient condition for lossless positional encodings is as follows: If all edges in G" have unique positional encodings, then g 9 + G is a bijection. One way to achieve this condition is to use additional edge feature that is unique to the 1-ring.
Discriminative power Following work investigating the discriminative power of GNNs (Xu et al., 2019; Brüel Gabrielsson, 2020), Ying et al. (2021) showed that expanded receptive fields together with shortest-path positional encodings are strictly more powerful than the 1- (WL) test and hence more powerful than 1-hop vanilla spatial GNN models (Xu et al., 2019). The combination of increased receptive fields, positional encodings, and choice of subsequent GNN models determines diseriminative power. In fact, follows from (Ying et al., 2021) that the po- sitional encodings presented below together with an increased receptive field 1 and a vanilla spatial GNN model are strictly more powerful than the 1-WL test.
Computational time. Positional encodings may come at substantial computational cost when work- ing with r-hop neighborhoods. The cost of computing positional encodings affects total inference time, which may be relevant in some learning settings. However, in our setting the runtime of com- puting positional encodings an order of magnitude less than the subsequent inference time, and in our implementation the asymptotic runtimes of computing the positional encodings are the same. See Appendix E.
Local vs. global. The positional encoding of a vertex or edge can be local, meaning it incorporates information from a limited-sized neighborhood in G, or global, in which case adding or removing a node wnywhere in G could affect all the positional encodings.
Inductive bias. Our positional encodings can bias the results of the learning procedure, effectively communicating to the downstream GNN which properties of G and G" are particularly important for learning. Without positional encodings. our model would induce a bias stating that distances < in our graph insignificant. More subtly, suppose is the distance (of length between two
4

---

Under review as a conference paper at ICLR 2023
nodes in G corresponding to new edge in E'. Using & directly as positional encoding rather than decaying function, e.g. e af makes it easier or harder (resp.) to distinguish long distances in G.
A related consideration involves whether our model can imitate the inductive bias of past work. For example, graph diffusion has been used to incorporate multi-hop connections into GNNs using fixed weights (Wang et al., 2021a). We can ask whether our positional encodings G' are sufficient to learn to imitate the behavior of a prescribed multi-hop model on G, e.g. whether a layer of our GNN applied to G' can capture multi-hop diffusion along G.
Over-squashing and under-reaching, Section 6.1 demonstrates, via the Neighbors problem (Alon and Yahav, 2021), that increased receptive fields as well the CLS--ode alleviate over- squashing; however, this toy problem is concerned with matching node attributes and not with graph topology. We want positional encodings that alleviate over-squashing the sense that it enables effective information propagation for the task at hand. Our experiments showing that expanded re- ceptive fields alleviate the wver-squshingg problem and that the best performing positional encoding varies across datasets showcase this. Additionally, our experiments on the discriminative power of positional encodings in Appendix D further help discern the different options.
4.2.2 POSITIONAL ENCODING OPTIONS
Taking the properties above into consideration, we now give a few options for positional encodings below, compared empirically in Section 6.
Shortest path. For any edge e E G",, the shortest-path positional encoding takes Pe {0. o........r r)
to be the integer length of the shortest path in G between the corresponding nodes of F. These embeddings are lossless because G is the subgraph of g(G) with Pe = 1. They also are free to compute given our construction of G., from G. But, multiple vertices in the r-neighborhood of vertex in V could have the same positional encoding in V", and shortest path lengths are insufficient to capture complex inductive biases of multi-hop hop GNNs like diffusion over large neighborhoods. Shortest-path positional encoding was previously used by Ying et al. (2021), for extending G to fully-connected graph, but they did not consider smaller r values.
Spectral embedding. Laplacian eigenvectors embed graph vertices into Euclidean space, providing per-vertex features that capture multi-scale graph structure. They are defined by factorizing the graph Laplacian matrix, A D-1 AD- 1/2 where D is the degree matrix and A is the adjacency matrix. We call the result a spectral positional embedding. We can use the smallest non-trivial Laplacian eigenvectors of as a node-based positional encoding Pa : V - IR9, Following Dwivedi et al. (2020), since these eigenvectors are known only up to a sign, randomly flip the sign during training. Prior work consider Laplacian cigenvectors as additional node features without topological rewiring (Dwivedi et al., 2020).
Spectral positional encodings do not necessarily make g injective. Even when q = [V] this encod- ing fails to distinguish isospectral graphs (Von Collatz and Sinogowitz, 1957), but these are rarely encountered in practice. On the other hand, spectral signatures are common for graph matching and other tasks. Moreover, unlike the remaining features in this section, spectral positional encodings capture global information about G rather than only r-neighborhoods. Finally, we note that the dif- fusion equation for graphs can be written as U, = -Au; this graph PDE can be solved in closed-form given the cigenvectors and eigenvalues of A. Hence, given the spectral embedding of G in G", we can simulate diffusion-baar based multi-hop GNN architectures up to spectral truncation.
Powers of the adjacency matrix. Our final option for positional encoding generalizes the shortest path encoding and can capture the inductive biases of diffusion-based based GNNs. The entry at position (i,j) of the k-th power A of the adjacency matrix A of graph G gives the number of paths of length k between node i and j in G. Concatenating the powers from = 1,.... r, we get for each edge in G" an integer vector Pe N' giving the powers of the adjacency matrix positional encoding.
This embedding can be used to recover the shortest-path embedding. This adjacency-deriver em- bedding can also generalize the inductive bias of diffusion-basee multi-hops GNNs. In particu- lar, diffusion aggregation weights are often approximated using a Taylor series, W Σi= 9,44 a Ei_n A,A' := W, where O₂ are prescribed decaying sequence (#, (.+1). The entries of W above can be computed linearly from the udjacency-powwe positional encoding. Hence, it is strictly more general than using prescribed diffusion-based aggregation weights on G.
5

---

Input and readout layers. Typically, GNNs on a graph G = (V, F., Se) first embed node features fe and edge features fe through a small feed-forward network (FFN) input layer. When incorpo- rating positional encodings per edge/node, we embed using small FFN and add them at this input layer. After this layer, it updates node and edge representations through successive applications of GNN layers. Lastly, readout layer is applied to the last GNN layer L. For node classification, it typically FFN applied to each node feature h." For graph classification, is typically an FFN applied to the mean or sum aggregation of all node features h², For graph classification and when Under review as a conference paper at ICLR 2023
Lossless encodings. The previously discussed lossless- lossless-encoding properties of our graph rewiring method are accomplished by two of the Proposition Shortest-path and adjacency matrix positional encodings yield lossless rewirings.
positional encodings:
Proof. Recovering the original graph G = (V, E) from the rewired graph G' = (V,E') )²)) is almost trivial. With the shortest-pate path position encoding the original graph can be recovered via E {ele e
E.. = } and for powers- of-the--atteeee the- adjacency-
mittariney-matrix matrix encodings via E = {ele e E', (pt)1 = 1}. O
5 IMPLEMENTATION DETAILS
Our method is compatible with most GNN architectures. Here we adopt GatedGCN (Bresson and Laurent, 2018), MoNet (Monti et al., 2017), and an implementation of the Transformer (Vaswani et al., 201 7); see Appendix B for details. For each model, consider graph rewiring with different r-hop receptive field around each node, and compare with and without the CLS-node, as well as the three positional encodings introduced in Section 4.2.2.
using the CL.S-node we aggregate by applying the FFN to the CL-S-nodes 's features in the last layer.
EXPERIMENTS
We evaluate performance on six benchmark graph datasets: ZINC, AQSOL, PATTERN, CLUSTER, MNIST, and CIFARIO 10 from (Dwivedi et al., 2020). The benchmark includes a training time limit of 12 hours; we use similar compute their work via a single TeslaV 100 GPU. Training also stops if for certain number of epochs the validation loss does not improve (Dwivedi et al., 2020). Thus, our experiments consider the ease of training and efficient use of compute. For the first two datasets, we run GatedGCN, MoNet, and Transformer to show that rewiring and positional encoding work for different models; for the other datasets we run only GatedGCN to focus on the effects of receptive field size, the CLS node, and positional encodings. For all datasets, we run with increasing receptive fields, with different positional encodings, and with or without the CLS-node In the tables, density is the average of the densities (defined as the ratio [=)) of each graph in the dataset rewired to the respective receptive field size. See Appendix A for details.
Table 1 compares best results with other top performing methods and models. All our top per- forming models come from the GatedGCN, although the Transformer performs comparably: how- ever, the Transformer was harder to train-see Appendix B. MoNet performs worse but still sees significant improvements from our approach. Our GatedGCN implementation was taken from the same work (Dwivedi al., 2020) that introduced the benchmarks and code that we use. Thus, hy- perparameters might be better adapted to the GatedGCN. This highlights the benefits of our model- agnostic approach, which allows to pick the best models from Dwivedi et al. (2020) and combine them with our methods. Our approach with 100K parameters achieves state-of-the oot on all datasets among models with 100K parameters and even outperforms 500K- KorKmaaaeeterr models.
ZINC, Graph Regression. ZINC consists of molecular graphs and the task is graph property re- gression for constrained solubility. Each ZINC molecule represented as a graph of atoms with nodes and bonds as edges. In Table 2 we present results for from 1 to 10. The density column shows that these graphs are sparse and that the number of edges increases almost linearly as the receptive field is increased. Performance across all settings noticeably improves when increasing r above 1. Top performance is achieved with the CLS-node and 4. and at 52% of the edges and compute compared to complete attention. When using the CLS node and/or spectral positional encodings, top performance generally occurs at lower which is likely due to the global nature of these changes to the graphs. The GatedGCN and
the---f------aaenccyy positional
encoding

---

Under review as a conference paper at ICLR 2023
Transformer perfonm comparably for the same settings, with slight edge to the GatedGCN. The two models show the same performance trends between settings, i.e., both increased receptive fields and the CLS-node boost performance. Further, Ying al. (2021) include performance of 0.123 on ZINC with their (raphormer(5000K, i.e., a Transformer with positional encodings and complete attention. However, their training is capped 10,000 epochs while ours is capped 1,000 epochs; training their Graphormer(500K) with same restrictions leads to a score of 0.26 on ZINC.
AQSOL, Graph Regression, AQSOL consists of the same types of molecular graphs as ZINC. The densities of AQSOL graphs are slightly higher than those of ZINC. For all settings not including CLS-node or spectral positional encodings. performance improves significantly when increasing r above 1 (see Table 3); in these settings, better performing are larger than for ZINC. However, when including CLS node or spectral positional encodings, performance changes much less across different This indicates the importance of some form of global bias on this dataset. At least one of larger r' values, spectral positional encoding, or the CLSS-token required to provide the global bias, but the effect of them differs slightly across the two models. GatedGCN performs significantly better, and larger r-values still boosts performance when combined with the CLS-token for MoNet, but not for GatedGCN. MoNet uses Bayesian Gaussian Mixture Model (Dempster et al., 1977) and since MoNet was not constructed with edge-features in mind, we simply add edge embeddings to the attention coefficients. Not surprisingly, this points the importance of including edge features for optimal use of expanded receptive fields and positional encodings.
CLUSTER, Node Classification. CLUSTER is node classification dataset generated using stochastic block model (SBM). The task is to assign a cluster label to each node. There is a total of 6 cluster labels and the average homophily is 0.34. CLUSTER graphs do not have edge features. Table 4 gives results for r-hop neighborhoods from 1 to 3. As can be seen in the density column, at 3 all graphs are fully connected, and more than 99% of them are fully connected at r = 2. Hence, these graphs are dense. Significant improvements are achieved by increasing for all but the spectral positional encoding (again showcasing its global properties), which together with the CLS node perform competitively at r = 1. The CLS node is helpful overall, especially at r 1. The GatedGCN and Transformer perform comparably for all but the spectral positional encodings where the Transformer breaks down. We found that this breakdown was due to the placement of batch normalization, discussed in Appendix B.
PATTERN, Node Classification. The PATTERN dataset is also generated using SBM model, and has an average homophily of 0.66. The task is to classify the nodes into two communities and graphs have no edge features. Table 5 shows results for r-hops from 1 to 3. Similarly to CLUSTER, the density column shows that the graphs are dense. Significant improvements are achieved by increasing Similarly to CLUSTER, the CLS-node helps at r = 1, but for both CLUSTER and PATTERN, top performing model comes from larger r 1 without the CLS-node, suggesting that trade-offs exist between CLS-node and increased receptive fields. Compared to CLUSTER, our approach shows less performance boost for PATTERN, which lead us to hypothesize that our approach is more helpful for graphs with low homophily which we investigate further in Appendix F.
and/or using the CL.S-odee. Performance generally decreases at r 3.
MNIST, Graph Classification. MNIST is an image classification dataset converted into super-pixel graphs, where each node's feature includes super-pixel coordinates and intensity. The images are of handwritten digits, and the task is to classify the digit. Table 6 summarizes results for r from to 3. Not all graphs are fully connected at 3. but training at r 4 exceeds our memory limit. Noticeable performance gains are achieved at r = 2, but performance generally decreases at r = 3. The CLS-node consistently improves performance at 1 but not otherwise, indicating that the CLS-node and increased r-size have subsumed effects.
CIFAR1O, Graph Classification. CIFARIO is an image classification dataset converted into super- pixel graphs, where each node's 's features are the super-pixel coordinates and intensity. The images consist of ten natural motifs, and the task is to classify the motif, e.g., dog, ship, airplane. Table 7 provides results for r from 1 to 3. Not all graphs are fully connected at = 3, but training at = 4 led out-of-memory issues. Top performing versions are all at r 1, and performance degrades for r > 1. As with MNIST, the CLS-node only improves performance at r 1, again indicating its shared (subsumed) effects with increased risizes.
7

---

Under review as a conference paper at ICLR 2023
Table 1: Benchmarking. Higher is better for all but for ZINC and AQSOL where lower is better. Benchmarks can be found in Dwivedi et al. (2020); Corso al. (2020); Bouritsas et al. (2020); Dwivedi and Bresson (2021). The benchmarks (Dwivedi et al., 2020) and corresponding leaderboard have 100K and 500K parameter entries. OOM is short for out-of-memory errors.
Datasets:
PATTERN node class.
CLUSTER node class.
MNIST
CIFARTO
ZINC graph reg.
AQSOL
task:
graph class.
graph class.
graph reg.
graphs:
14000
12000
70000
60000
12000
9823
Avg nodes:
117.47
117.20
70.57
117.63
23.16
17.57
Avg # edges:
4749.15
4301.72
$64,53
941.07
49.83
35.76
MoNei(1OOK)
85.48220.003
58.06420.131
90.805+0.032
54.655+0.518
0.397+0.010
0.395=0.227
GAT(100K)
7 .823
57.73210.323
95.53510.200
64,22310.455
0.47510.000
1.44100.223
GraphhSage(100K)
50.516=0.001
50.454=0.145
97.312+0.097
65.767+0.308
0,468+0..003
1.401=0.011
GIN(100K)
85.590=0.011
08.384=0.236
96.485+0.255
55.255
0.387=0.015
1.894=0.024
PNA(100K)
86.73010.050
63:02010.266
97.940
70.35010.630
0.188
1.08310.011
GatedCCCN 100K)
84.480=0.122
60,404:0.419
97.340+0.143
67.312+0.311
0.328+0.003
1.295=0.011
86, 16.363=0.127
74.088+0.344
OOM
OOM
0.214+0.006
0.996=0.008
GraphTrans (500))
54.941+3.739
27.121+8.471
OOM
OOM
0.598=0.0:49
1.110=0.010
Ours(100K)
86.75720.031
77.57510.149
98.74310.062
13.80
0.14320.006
0.920=0.009
Table 2: Increasing on ZINC/molecules 100K parameters.
Trpp
012-503
0220441003 012
0136600122
0.20644..12
0339-2054
0.25144:.06
0.30600014
0335-1 185
0391-202
0125444.007
1:2
-37
211
0.23541000
0:255-4.000
0:15-40011
0 036500ms
102040110
0.35--8123
0.335.5010
0343.0085
6145.0.63
022660022
6.844:0.14
0325.8013
6.398.0.03
0100.0099
6,44.0866
0.067.0000
0305.5000
0.302.0.05
7:5
0.33hwcatt2
20
0350420115
6:30
6.30048.000
4385-880
0250-0015
1.77500106
0.314-201
0330-2044
0:30001006
0333-201
0:31440000
8:33-1150
01577-41000
0.
0.29.0013
0.51:3005
85
0212:6.012
0190:0000
0.34120035
6235:0.051
0.30.8000
0.388.0.000
000220003
0182.0.012
0126.0019
02:0.0005
0.345:205
0.365.0.06
2.9
0.318xc/877
0338420013
0.21540..00
6:91244100
0211420012
8:35-41177
0.30460335
1.305-0001
0335422077
01312410111
gen: GatedGCN, trans: Transformer, adj: adjacency p.e.. short: shortest-palh p.e.. Ip: spectral p.e.. cls: CLS-mode
p.e..
Table Increasing r on AQSOL 100K parameters.
1y3c
252 2337-36
203-0
030-33)
3xm--ab-26
12 2122-4331
meeap
37
1.36:0011
0:55::001
1233.0319
0367:3006
10000006
0.51:5807
1335:00.00 650
1.35:0045
1.37602.822
1145:0.05
1.19:22011
1.39h00 155
163
164:0005
n554:0015
200-0.11
0961:3017
105:0010
0.5520000
1.20:00 000
27770088
1.26--2017
1.215:0.000
1.36-2203
1.183-0817
2191122012
19668C12
03634cum2
1224500 p40
1.7794101
11854t001
122142185
1.30544:00
146
82
166:0001
0541:0100
0545:3012
1050:0018
055320000
1225-0 851
195:0041
1.306:2033
1115:0044
1.14:20m
1.21500058
1154460014
11535ud1117
1195242181
0134440014
1.255
117960041
1.212401022
3.154at001
1.3942215
1182240119
52
1181
1099640 (89)
1:345 146
131040035
1.20040017
3.100001000
1.306.1.00 1.3840015
1+10
10220000
0956:0
0.51120000
1334:0067
1.16420.007
1.161:0055
1.19520004
1.192:0015
gen: GatedGCN, MoNet, adj: adjacency p.e. short: shortest-path pe., 1p: spectaal plc. S-ode
Table 4: Increasing r on CLUSTER 100K parameters.
Type
5.00
% 6314
133 30224414339
51383-1.807
7633666172 $154012.00
3535468335
1841
724-40315 143
77.50-113 1.
0.136
895LDIN9
54194.1766
gon: GatedGCN, Transformer, adj: adjacency p.e., short: shortest-path p.e., Ip: spectral p.e., cls: Cooee Training converging
Table 5: Increasing r on PATTERN 100K parameters.
Type:
density
gen-adj
gen-adj-els
gen-Ip
gen-Ip-cls 06.713=0.031
gen-short
gen-short-els
1=
.43
85.715=0.036
86.723:0.006
86.547=0.026
00.033
86.732=0.020 86.736=0.014 86073920.027
r=2
>.99
0.029 0.0698=0.047
0.033 86.71820.024 04.65720.977
0.074 86.74420.015
86.757=0.031 86.71220.031
r=3
1.0
05.471=0.949
gen: GaledGCN, adj: adjacency p.e. short: shortest path p.e.. lp: spectral cls CLS mode
Table 6: Increasing r on MNIST 100K parameters.
type:
density
gen-adj
gen-adj-cls
gen-Ip
gen-Ip-cls
gen-short
gen-short-els
.13
98.537=0.089
98.522=0.033
98. 0.099 98. 0.067
98.373+0.122 98.597=0.070 98.570=0.117
98.542=0.079
98.545=0.0577
2
.34
98.630=0.134 98.035=0.094
98.743=00002
08.6305000022
98.552=0.107
3=3
.58
04.11
98.513+0.145
98.315+0.156
98.390=0.100 104
gen: GatedGCN adj: adjacency p.e.. short: shartest- p.e., Ip: spectral p.e., als: Clde-
6.1
MATGHBORSMAATC., OVER- -TERSSQUASHING
Alon and Yahav (2021) introduce a toy problem called NeighborsMatch to benchmark the extent of over-squashing in GNNs, while controlling squashing by limiting the problem radius Tp. The graphs in the dataset are binary trees of depth equal the problem radius rp- Thus, the graphs
8

---

Under review as a conference paper at ICLR 2023
Table 7: Increasing on CIFARIO 100K parameters.
type:
density
gen-adj
gen-adj-cls
gen-ip
gen-Ip-cls
gen-short
gen-short-cls
1=
.08
03.415=0.717
0.8449
0.471
02.610=0.574 71.745=0.325 70.318=0.295
73.808 0.193
=..250=0.520
r=2
.21
72.037=00400 70.688=0.171
72.480=0.420 69.580=0.488
72.085+0.487 70.380=0.308
12.127=0.471 71.285=0.722
71.470=0.508
3=3
.38
71.18820.498
gen: GatedGCN, adj: adjacency p.o.. short: shortest-path p.c.. spectral p.c.. CLS-node
structured and sparse, and the number of edges grows linearly with the increased receptive field r. See Figure 1, Appendix C, for results with GatedGCN. Increasing the receptive field with step of 1 increases the attainable problem radius with a step of 1, while using the CLS-node at r falls in between the performance of showcases the subsumed as well as different effect (complementary and conflicting) the receptive field and the CLS-node have, as also observed the other benchmarks.
and 3 but with much longer tail. Thus, this further
6.2 COMPUTATIONAL ANALYSIS
For all positional encodings, the number of edges determines the asymptotic runtime and memory use. The Code only introduces an additive factor. Figures and 5 in Appendix show that the runtime in practice scales roughly the same as the density, the receptive field size is increased; though real runtime has significant constant factor.
6.3 SELECTING POSITIONAL ENCODING AND HOPS SIZE
We recommend the adjacency positional encodings together with the CLS-node. In terms of ranked performance across the 6 datasets, adjacency- and spectral positional encodings perform the same, but the spectral encoding performs considerably worse on the ZINC dataset, while the differences are smaller on the other datasets. Additional experiments in Appendix D, Figure 2, assess the dis- criminative power of the different encodings. However, there is no positional encoding superior in all aspects. Instead, each one has unique benefits as well as drawbacks. This is made apparent by considering r as a parameter and observing the performance differences across values of r. Fur- thermore, the CLS- CLS-node is part of the best-performing configuration more often than not. Similarly, no fixed r optimal for all datasets. Instead, optimal r depends on the dataset and the amount of compute. Appendix F shows that increased r diminishes the reliance homophily bias, and thus low homophily If the density does not change much from a change in then neither does performance. The use of the spectral positional encodings, the CLS-node, or increased have subsuming effects for multi- ple datasets; here the CLS-node spectral positional encodings may be preferred, computationally cheaper, alternatives to increasing r.
inductive a dataset could be used as an indicator for selecting an increased r.
From this empirical study, for picking optimal r, we recommend computing the densities for increas- ing r and picking the first one where the average density exceeds 0.5 to reap most of the performance boosts. This seems to maintain a helpful locality bias as well as significantly reduce the compute compared to complete attention. See Appendix G for further discussion.
7 DISCUSSION
Our simple graph rewiring and positional encodings achieve state-of-the-as performance, widening receptive fields while alleviating over-squashing This is much due the ability to easily apply our method to models that stem from large body of work on GNNs, highlighting the benefits of our model-agnostic approach.
The reality is that attention with complete receptive fields is still computationally intractable for most practitioners and researchers. However, here we show that significant performance boosts via attention and increased receptive fields can be obtained by increasing the receptive field only slightly. Thus, opening up recent work to a broader range of practitioners as well as giving more fair conditions for comparing GNNs. In addition, the systematic investigation of increased receptive fields and positional encodings gives further insights into the necessity of homophily for the success of GNNs and highlights other implicit biases in GNN architectures.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Uri Alon and Eran Yahav, On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021.
Jinheon Baek, Minki Kang, and Sung Ju Hwang. Accurate learning of graph representations with graph multiset pooling, 2021.
Pablo Barceló, Egor V. Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan Pablo Silva. The logical expressiveness of graph neural networks. In International Conference on Learning Representations, 2020.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M. Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. CoRR, abs/2006.09252, 2020.
Xavier Bresson and Thomas Laurent. Residual gated graph convnets, 2018.
Rickard Brüel Gabrielsson. Universal function approximation on graphs. In H. Larochelle, M. Ran- zato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 19762-19772. Curran Associates, Inc., 2020.
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks graphs. In Yoshua Bengio and Yann LeCun, editors, 2nd International Conference on Learning Representations, ICLR 2014, Banff. AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014.
Deng Cai and Wai Lam. Graph transformer for graph-to-sequence learning. CoRR, ab5/199 2019.
Benson Chen, Regina Barzilay, and Tommi Jaakkola. Path- aath-augmented graph transformer network, 2019.
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. In Advances in Neural Information Processing Sys- tems, 2020.
Zihang Dai, Zhilin Yang, Yiming Yang, Jaime G. Carbonell, Quoc V. Le, and Ruslan Salakhut- dinov. Transformer-xl: Attentive language models beyond a fxxet-lentth context. CoRR, abs/1901.02880 002600, 2019.
A. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the em algorithm. Journal of the Royal Statistical Society. Series B (Methodological), 39(1):1-38, 1977. ISSN 00359246. URL http: / /www. jstor. org/ sttale/eeeeaaa
Jacob Devlin, Ming-Wes Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04800 2018.
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs, 2021.
Vijay Prakash Dwivedi, Chaitanya K. Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks, 2020.
Ari Frankel, Cosmin Safta, Coleman Alleman, and Reese Jones. Mesh-based graph convolutional neural networks for modeling materials with microstructure, 2021.
Justin Gilmer, Samuel Schoenholz. Patrick Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings the 34th International Conference on Machine Learning Volume 70, ICML' 17, page 1263-1272. JMLR.org. 2017.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
10

---

Under review as a conference paper at ICLR 2023
Ziniu Hu, Yuxiao Dong, Kuansan Wang, and Yizhou Sun. Heterogeneous graph transformer. CoRR, abs/2003.01332, 2020.
Elvin Isufi, Fernando Gama, and Alejandro Ribeiro. Edgenets: Edge varying graph neural networks. CoRR, 0oos/2001.0762/) 2020.
Guolin Ke, Di He, and Tie- Yan Liu. Rethinking positional encoding in language pre-training. CoRR, abs/2006. 15595, 2020.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
Thomas N. Kipf and Max Welling. Semi- Semi-supervised classification with graph convolutional net- works. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017
Johannes Klicpera, Stefan Weißenbbrger, and Stephan Günnemann. Diffission Improves Graph Learning. Curran Associates Inc., Red Hook, NY, USA, 2019.
Devin Kreuzer, Dominique Beaini, William L. Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. CoRR, abs/2106.03893,, 2021.
Pan Li, Yanbang Wang. Hongwei Wang. and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning, 2020.
Sitao Luan, Mingde Zhao, Xiao-Was Wen Chang, and Doina Precup. Break the ceiling: Stronger multi-scale deep graph convolutional networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Sys- tems, volume 32. Curran Associates, Inc., 2019. URL https: http::::ss///cceeeiieieeo neurips. co/paper / 22122/111 9 wwwee//cafffa
0ate2//9990e0ea44444444eeeaaa00. Paweoodaaaappppppeeee pdf.
Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily necessity for graph neural networks?, 2021. URL https: / aarxiv.vvv...///.i///aaa//aaaavv org/ aass/2166 06134.
Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily necessity for graph neural networks? In International Conference Learning Representations, 2022. URL https: / //operreview net/ formmmormmmmmm www.umiiiduuusssseesec..
Monti, D. Boscaini, J. Masci, E. Rodola, Svoboda, and M. M. Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. In 2017 IEEE Confer- ence on Computer Vision and Pattern Recognition (CVPR), pages 5425-5434, Los Alamitos, CA, USA, jul 2017. IEEE Computer Society. doi: 10.1109/CVPR.2217..550 URL https: //doi.
fefooc..eeccoomio weweccmptteeeee...............ee www.pitt........o...........tte. .org//rgg//.o 100000..000 11 09 CVWR. 2017.576.
Niki Parmar, Ashish Vaswani, Jakob Uszkoreit, Lukasz Kaiser, Noam Shazeer, Alexander Ku, and Dustin Tran. Image transformer. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 4055-4064, PMLR, 10-15 Jul 2018
Yu Rong, Yatao Bian, Tingyang Xu, Weiyang Xie, Ying WEI, Wenbing Huang, and Junzhou Huang. Self-supervised graph transformer on large-scale molecular data. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances Neural Information Processing Sys- lems, volume 33, pages 12559-12571. Curran Associates, Inc., 2020.
Emanuele Rossi, Fabrizio Frasca, Ben Chamberlain, Davide Eynard, Michael M. Bronstein, and Federico Monti. Sign: Scalable inception graph neural networks. CoRR, abs/2004.11198 2020.
Yunsheng Shi, Zhengjie Huang, Shikun Feng, Hui Zhong, Wenjin Wang, and Yu Sun. Masked label prediction: Unified message passing model for semi-supervised classification, 2021.
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. arXiv preprint arXiv:2/11./4m 14.22 2021.
11

---

Under review as a conference paper at ICLR 2023
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, ukasz Kaiser, and Illia Polosukhin. Attention all you need. In Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Gamett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
Petar Veličković. Message passing all the way up, 2022. URL https: http:///axxv..rrro 2202. 11097.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks, 2018.
Lothar Von Collatz and Ulrich Sinogowitz. Spektren endlicher grafen. In Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, volume 21, pages 63-77. Springer, 1957.
Guangtao Wang, Rex Ying, Jing Huang, and Jure Leskovec. Multi-hop attention graph neural net- works. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI), pages 3089-3096, 2021a.
Guangtao Wang, Rex Ying, Jing Huang, and Jure Leskovec. Multi-hop attention graph neural net- work, 2021b.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Learning Representations, 2019.
Yiding Yang, Xinchao Wang, Mingli Song, Junsong Yuan, and Dacheng Tao. Spagan: Shortest path graph attention network. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19, pages 4099-4105 International Joint Conferences on Artificial Intelligence Organization, 7 2019. doi: 20244966/jccii2201/5559
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? CoRR, abs/2106.05234, 2021.
Seongjun Yun, Minbyul Jeong, Raehyun Kim, Jaewoo Kang, and Hyunwoo J Kim. Graph trans- former networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garneut editors, Advances in Neural Information Processing Systems, volume 32. Curran As- sociates, Inc., 2019.
Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, and Amr Ahmed. Big bird: Trans- formers for longer sequences. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 17297- Curran Associates, Inc., 2020.
Jiawei Zhang, Haopeng Zhang, Congying Xia, and Li Sun. Graph-bert: Only attention is needed for learning graph representations, 2020.
Yingxue Zhang, Soumyasundar Pal, Mark Coates, and Deniz Ustebay. Bayesian graph convolutional neural networks for supervsee classification, 2018
12

---

Under review as a conference paper at ICLR 2023
A TRAINING DETAILS
Both code and training follow Dwivedi et al. (2020) closely, and to lesser extent (Dwivedi and Bresson, 2021), which uses the same code base.
Like (Dwivedi et al., 2020), we use the Adam optimizer (Kingma and Ba, 2015) with the same learn- ing decay strategy. The initial learning rate is 10 and is reduced by half if the validation loss does not improve after a fixed ("Ir_schedule, (iitscccuullpppttineeee)) number of epochs, either or 10. In- stead of setting maximum number of epochs, the training stopped either when the learning rate has reached 10 or when the computational time reaches 12 hours (6 hours for NeighborsMatch). Experiments are run with different seeds; we report summary statisties from the 4 results.
Below we include training settings for the different datasets.
A.1 ZINC
"model": GatedGCN and Transformer, "batch_size"; 128, "ir _ir__schduule__ _tt_echheuu___paiieee.. 10, : 12
A.2 AQSOL
"model": GatedGCN and MoNet, "batch_size": 128, "ir "Ir_schedule_patee lateee_paieecce.. 10, "max_time")
A.3 CLUSTER
"model": GatedGCN and Transformer,
sbbatchssize,, 48 (GatedCCN), 32 or 16 (Transformez). "Ir " 5, "max_time": 12
patience";
A.4 PATTERN
"model"; GatedGCN, "batch_size" 48, wwt.sschdule__pptieeeeee 5, "max_time": 12
A.5 MNIST
"model": GatedGCN, "batch_size"; 128, "1r_schedule_pi setiuuleeppp____ "max_time"; 12
ence": innce"""": 10,
A.6 CIFAR10
"model": GatedGCN, bbatch_size"" 128, "1r_schedule, Battileleepp___aeeee ience": 10, "max_time"; 12
A.7 MATCH
"model" ": GatedGCN,
13

---

Under review as a conference paper at ICLR 2023
"batch_size"; 256, patience": 10,
_ir_sshedule, _et_echheeee__ptieeee.... maax_time":
B TRANSFORMER IMPLEMENTATION
We implemented a simple version of the Transformer adapted to graphs:
1/4 =BN(
H
Σ
w1 +
k=1
jeNiu(s)
M H)N( +
with
4 -BN(c
d ((A,,)))) (B +
exp(a cllk
1.k
" EseNiuls exp(d 1 =FFN(CE.) t
Here, h and are node and edge features (resp.) from the previous layer. WR, A, B e Rxd and C' e Rixd are learnable weight-matrices, H is the number of attention heads, and BN is short for batch normalization. | denotes the concatenation of the attention heads.
B. DESIGN CHOICES AND CHALLENGES
There are many variations on the Transformer model. Following Ying et al. (2021), we put the nor- malization before the multi-head attention, which caused instability when training on CLUSTER with Laplacian (spectral) positional encodings. This was fixed by putting the normalization after or using layer normalization instead of batch normalization; however, these changes reduced perfor- mance ZINC. While the GatedGCN worked well with identical architecture parameters across datasets, we found that the Transformer needed more variations to stay competitive on MNIST and CIFAR10; in particular, fewer layers and larger hidden dimensions.
Transformers use multi-hean attention which puts number-of-heree dimension vectors on each Sege-seenn directed. Hence, the memory load becomes 2 x EE] x num heads (in our experiments, num_heads 6), which compared for GatedGCN is only EE. This causes a memory bottleneck for the Transformer that may force one to use reduced batch size to avoid memory issues.
B.2 OTHER VARIANTS
We implemented other variants, including more involved Transformers. As in (Vaswani et al., 2017), ran the auth-integers through sine and cosine functions of different frequencies, and inspired by (Dai et al., 2019; Ke et al., 2020) we implemented a more involved incorporation relative positions in the multi-head attention (see below); however, we found performance be comparable.
In natural language processing, the input a sequence (a line graph) x = (I1,..., ...) of text
tokens from a vocabulary set V, with each token having a one-hot-encoding fv : V. - [0, 1 1
The word embeddings E Ruxd for n tokens are formed as E (Wembedffv (I;) x x) where Wembed dddx is learnable weight matrix.
The original Transformer model used absolute positional encodings. This means that add the po- sitional encoding to the node embedding at the input layer. Consider a positional encoding function Pe No d Then the first input is
h
(W embed (x())) pp)( i= .......) ..) F
14

---

Under review as a conference paper at ICLR 2023
Table 8: Increasing ZINC/molecules 100K parameters.
type:
trans-adj
trans-short-cls
r=1
0.338+0.020
0.274=0.021
2=2
0.296=0.010
0.179:0.011
r=3
0.260=0.013
0.183=0.018
r=4
0.255=0.009
0.271=0.036
r=
0.235+0.022
0.227
0.226+0.015
0.264+0.042
r=7
0.219+0.012
0.251+0.039
r=8
0.210=0.009
0.278+0.026
0.213+0.010 r=9
0.289+0.042
1=10
0.564+02221
0.327=0.023
Table Increasing r on CLUSTER 100K parameters.
type:
trans-adj-cls
trans-adj
trans-short-els
trans-short
r=
74.262=0.18
73.445=0.068 77.399=0.200 68.384=7.975
74.717+0.308
72.947
2
0.188
76.771 76.770+0.094
76.454+0.084 76.521=0.250
r=3
0.221
where U ( Raxd Typically P. contains sine and cosine functions of different frequencies:
Pe 2c x sin($/10000(2xx)44
Pe (k, x 1) cos(4/110000
where i e N is the position and 1 N is the dimension. That is, each dimension of the positional encoding corresponds to sinusoid. The wavelengths form geometric progression from 2 to 10000 2 This function was chosen because it was hypothesized that would allow the model to easily learn to attend by relative positions, since for any fixed offset m, P. + m) is a linear function of pe (k). was also hypothesized that may allow the model to extrapolate sequence lengths longer than the ones encountered during training.
In many cases, absolute positional encodings have been replaced with relative fully learnable posi- tional encodings and relative partially learnable positional encodings (Dai et al., 2019). To justify these, consider the first attention layer with absolute positional encodings:
An E., W W ET, + Ex, W, UJ + U.W.WI E", + U.W.WTUT
For relative (fully and partially) learnable positional encodings we have instead:
A Ez, W2 W.W,,EE, Ez,, NeW,WWe W,WWeRRR.. uW W., oW WWE
where U 1xd are learnable weights and Ri-j I Iidd is a relative positional encoding between i and j. Each term has the following intuitive meaning: term (1) represents content-based addressing, term (2) captures content- -deeentt positional bias, term (3) governs global content bias, and (4) encodes a global positional bias.
For relative fully learnable positional encodings, WT. W., is a learnable weight in IRxx1 for each i-je N. while for relative partially learnable positional encodings R.,, = Pe Pe ( where pa the sinusoidal function from before.
We implemented both fully and partially learnable positional encodings for the shortest-path posi- tional encodings (integer-valued) and related versions for the other positional encodings (in Rd). We include results in Tables 8 and 9.
C OVER-SQUASHING
Results for over-squashing experiment can be found in Figure 1.
15

---

Under review as a conference paper at ICLR 2023
0.9
0.8
0.7
Accuracy
0.6
0.5
0.4
0.3
+
r 2
== 3
0.2
r= 4
0.1
r
1,CLS
0
2
5
7
8
Tp (problem radius)
Figure 1: Neighbors (Alon and Yahav, 2021). Benchmarking the extent of over-squashing via
the problem radius Tp-
D ADDITIONAL EVALUATION OF POSITIONAL ENCODINGS
Here provide start toy data and task for comparing positional encodings. this task wish to assess how powerful the positional encodings are in practice, i.e. how well they discriminate between different graph isomorphism classes. Specifically, we generate 100 random Erdos graphs and then expand the receptive field so that the graph is fully connected. Thus, the positional en- codings become
mere instrument for communicating the connectivity/topoogyy of original graph. The task is to retrieve specific graph among all 100 graphs, i.c. the task is graph classifi- cation and there is a 100 classes. Hence, achieving 100% accuracy means that the GNN, based on the positional encodings, has been able to discriminate between all graphs. We only look train accuracy here, since we're interested in the power to overfit, not to generalize. Results can be found in Figure 2.
All positional encodings are able to solve that task after a sufficient amount of training. besides Adj- 10. Adj-5 and Adj-10 10 encode the adjacency matrix the power of 5 and 10 respectively (at both points all graphs are fully connected). Adj-10 encodes between any two nodes the number of paths of length 10, number of path of length 9, and so on. The experiments indicate that too much such information confuses the GNN and makes it harder to discriminate between graphs. The shortest and Adj-5 positional encodings are the fastest solving the task. This can be due the fact that the Laplacian positional encoding is only unique up to sign and that we randomly switch the sign during training.
E COMPUTATIONAL RUNTIME AND MEMORY USE
In our implementation, the step of computing the positional encodings well as expanding the hops of the graph is done in the same process for shortest-patte and adjacency positional encodings; thus this step always occur and we found that implementing via iterative matrix multiplications of the adjacency matrix gave the fastest results. How this scales with the r-size can be found in Figure 3. Since each increment the r-size results in an additional matrix multiplication, the linear increase is expected. The spectral positional encoding has the same additíve runtime per graph across r-sizes of 1.3 x 10 seconds. These matrix multiplications are done on CPU rather than GPUs, but running them GPUs could results in speed-ups. However, the runtime for computing these positional encodings is at least an order of magnitude smaller (per graph) than the runtime for running the subsequent GNN GPU, there need to optimize this runtime further.
16

---

Under review as a conference paper at ICLR 2023
Laplacian
Shortest
0.9
Adj-5
0.8
Adj-10
Train Accuracy
0.7
0.6
0.5
0.4
0.3
0.2
0.1
11)
25
50
75
100
125
150
175 200 225
250
Num. Epochs
Figure 2: Learning to retrieve random Erdos graphs.
In Figures 4 and we include actual runtime of the GNN (on GPU) of different positional encodings and hops sizes, juxtaposed with the density of the modified graphs, for the ZINC and CIFARIO datasets. Note, we are here excluding the computation of the positional encoding on the input graph, which can be found in Figure 3.
Most graphs to which GNNs are applied to are connected and typically the number of edges are greater than the number of nodes, i.e. |F] IV. Since all established GNNs make of the edges in one way or another, the number of edges usually determines the asymptotic behavior of the runtime and memory use, i.c. they are in O(E)). With modern deep learning and specialized graph learning framework, GPU-parallelization and other more technical aspect affect memory and runtime. Thus, Figures 4 and compare theoretical runtime (dominated by the density) with actual runtime of code run on GPUs. We find that density and actual runtime strongly correlated. In Figure we include the memory use for increasing radius on ZINC dataset, and find its roughly linear with the density as well.
F HOMOPHILY SCORE AND PERFORMANCE
We include experiments to investigate the correlation between homophily score (Ma al., 2021) and performance when increasing hops size. This applies to the node classification datasets. CLUSTER three buckets, which is just sorted segmen-
and PATTERN, that we used. We split the test tation of the graphs with increasing homology scores. We evaluate trained Gated- RCN models with adjacency positional encodings for r-values and 2 See Tables 10 and 11 for results.
almost all graphs are fully connected).
We find that high homophily score correlates much stronger with performance when r 1 than it does at 2. This indicates that increased r-size diminishes the reliance on homophily as an inductive bias.
Table 10: Increasing on CLUSTER homophily buckets.
density .311
homophily score:
0.315=0.008
0.336+0.006
0.366+0.0160
r=1
72.361=0.462 77.010+0.234
71.494+0.619
73.812+0.266
>.99
2=2
76.660= 0.143
76.965+0.242
17

---

Under review as a conference paper at ICLR 2023
11
10
Avg. time per graph, x10
4
3
Adj. Short, LP
Density
1
2
3
5
6
8
9
10
r-hops
Figure 3: P.E. Computational Time on ZINC/molecules
30
Avg. time per epoch
25
20
Laplacian
Shortest
Adj
15
Adj-CLS
Density
2
3
5
6
7
9
10
r-hops
Figure 4: GNN Computational Time on ZINC/molecules
18

---

Under review as a conference paper at ICLR 2023
400
Laplacian
350
Shortest
Adj
Avg. time per epoch
300
Adj-CLS
Density
250
200
150
100
1
2
3
r-hops
Figure 5: GNN Computational Time CIFARIO
2,500
2,400
2,300
MiB memory use
2,200
2,100
2,000
1,900
1,800
1,700
1,600
1,500
1,400
Adj
1,300
Density
2
3
5
6
7
9
10
r-hops
Figure 6: GNN Memory use on ZINC/molecules
19

---

Under review as a conference paper at ICLR 2023
Table 11: Increasing PATTERN homophity buckets.
density .43
homophily score:
0.567=0.031
0.652+0.026
0.774=0.051
r=1
83.958+0.031
86.862=0.021 84.19740.048
92.154+0.492
>.99
2
87.214 0.062
87.085+0.082
G OPTIMAL POSITIONAL ENCODING AND HOPS SIZE
Again, we recommend the adjacency positional encodings together with the CLS-node. We find that terms of ranked performance on the datasets, adjacency- and spectral positional encod- ings perform at the same level, but the spectral encoding perform considerably worse the ZINC datasets, while the differences are smaller on the other datasets. The spectral encoding hardcode global-to-local information on the nodes and the size of the encoding-vector is hyper parameter; we found performance not to be too sensitive to this hyper-parameter but future work could further investigate this. Spectral embeddings also use less memory it does encode its embeddings as edge-features; however, since information still is propagated along edges we find this memory saving to significant but not asymptotically different. Adjacency encoding breaks down faster as the r-size is increased compare to the other positional encodings, we believe this to be due to the corresponding increase in size of the embedding- vectors and its introducing low-signal information that is also easy to overfit to, e.g. the number of paths of length 10 between two nodes (where any edge can be used multiple times). The Erdos experiments Appendix support this observation. However, all in all, the adjacency encoding stands out slightly considering the performance, runtime, memory use, and toy experiments. Furthermore, the CLS-node part the best performing config- uration more times than it is not, and it has the additional advantage of leading to peak performance at lower r-sizes where in some cases it also has reduced runtime and memory use compared instead to increasing the r-size.
In this work we do not find fixed r-size that is optimal for all datasets. The optimal r depends on the dataset and the amount of compute available. Given the fixed amount of compute used in our experiments, we found that all the best performance was found at r-size four or smaller. We provide heuristic for selecting a good r-size but ultimately depends on the amount of compute and memory available.
20


Reviews:
[{"review_id": "ur07K34e8ia", "reviewer": "Reviewer_37EK", "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": "", "summary_of_the_paper": "Recent efforts towards addressing under-reaching and over-squashing in graph neural networks (GNNs) include graph transformers (GTs) with topology-based positional encodings; however, the computational cost is quadratic in nature (since vanilla GTs act on fully connected graphs).\n\nThis paper proposes and studies a model-agnostic graph rewiring approach with\n* edges added between nodes and their r-hop neighbours (the paper studies different values of $r$ from 1 to the graph diameter) and\n* a virtual node connecting all the other nodes of the original graph (to encode global graph information).\n\nTo retain the graph toplogical information, the paper also empirically studies three types of positional encodings, viz., (i) shortest path, (ii) Laplacian eigenvectors, (iii) adjacency powers, in the form of node/edge features and shows that GNNs acting on the rewired graph + positional encodings are more effective than traditional baselines (even for small values of $r$) on several datasets.\n\n___", "summary_of_the_review": "While the proposed methods are evaluated on several datasets with several baselines, the paper can be strenghtened by positioning with relevant existing prior work and more empirical evaluation on real-world data.\n\n___", "strength_and_weaknesses": "\\\n**Strengths**\n\n\\+ The proposed methods are evaluated on node classification, graph classification, regression tasks (two datasets each) and the NeighboursMatch problem (for oversquashing) and compared with seven baseline models.\n\n\\+ Based on the empirical evaluations of different $r$ values with and without virtual nodes and three different positional encodings, the authors conclude that the adjacency positional encoding with virtual nodes works best and an optimal $r$ (i.e., hop size) generally depends on the homophily of the dataset.\n\n\n\\\n**Weaknesses**  \n\n\\- The node classification datasets (PATTERN, CLUSTER) are generated using the stochastic block model (i.e., synthetic in nature).\n\n\\- The ideas of using positional encodings (PEs) for GNNs on molecular graph regression is not new, see for instance a prior work [Graph Neural Networks with Learnable Structural and Positional Representations, In ICLR'22].\n\n\\- The idea of using a virtual node connecting all existing graph nodes without affecting the graph topology (i.e., ensuring that there is an inverse map back to the original graph) is also not new, see for instance a relevant prior work [Boosting Graph Structure Learning with Dummy Nodes, In ICML'22].\n\n___", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": "_p9mVc2b6iF", "reviewer": "Reviewer_apU4", "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": "", "summary_of_the_paper": "This paper proposes a method to enlarge the receptive field of GNNs by augmenting graphs with r-hop neighborhoods, positional encodings and classification node. Extensive experiments are conducted on six benchmark graph datasets including ZINC, AQSOL, PATTERN, CLUSTER, MNIST, and CIFAR10 to demonstrate the effectiveness of the proposed method.", "summary_of_the_review": "My main concerns are the limited novelty of this work compared to previous works in multi-hop GNNs and the positioning encoding of GNNs and the inconclusive evaluations on the graph benchmark with heavy hyperparameters and GNN design choices tunings.", "strength_and_weaknesses": "Pros:\n\nThe detailed experimental results in Section 6 are appreciated.\n\nA thorough analysis of runtime and memory consumption is presented in the appendix which is helpful.\n\n\nCons:\n\nThe technical novelty of the paper is limited compared to previous works in multi-hop GNNs and positioning encoding of GNNs. Two pages are used to discuss position encodings in Section 4.2. However, it is not clear what is the novel contribution of this work on position encodings. Since this work does not propose a new position encoding, I recommend the authors compress Section 4.2 and move some content to related work.\n\nIt is not clear how the results of Table 1 are obtained in section 6. What value of the hyperparameter $r$ and what GNN models are used? Is $r$ the same across datasets or is it tuned for each dataset? The results seem to be aggregated from the best models in Table 2-6. If this is the case, the hyperparameter $r$ are GNN layers are chosen on the test set results with heavy hyperparameter tuning which is not encouraged. Different $r$ and with/without CLS nodes are used in different datasets which also makes in results inconclusive.\n\nThis work is a combination of multi-hop GNN methods and positioning encoding methods on graphs. I believe a comparison with multi-hop GNNs is necessary such as MixHop.\n\nMinor:\n\n\"Section 4: we also add a fully-connected CLS node.\" \"CLS\" node should be clearly defined here.\n\n[1] Abu-El-Haija, S., Perozzi, B., Kapoor, A., Alipourfard, N., Lerman, K., Harutyunyan, H., Ver Steeg, G. and Galstyan, A., 2019, May. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In international conference on machine learning (pp. 21-29). PMLR.", "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": "XIAQvgq4nM9", "reviewer": "Reviewer_qbsV", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Main concern. A catalog of experiments to find the best combination of positional encoders for any explored type of graphs. The most successful encoding (powers of adjacency matrices) is not scalable unless large graphs are previously sampled. The argument that the powers of adjacencies for small r=1,2 beats full attention is true, but this is not enough to validate the approach. \n\nI agree with the model agnosticism of the proposal but it is not inductive at all (positional encodings must be computed for any input graph in the case of graph classification). \n\nPOSITIONAL ENCODINGS: ONLY TESTED WITH SBMs and KNN-GRID graphs. The conclusions obtained for spectral positional encoding match the intuition and can be expected by the analysis of the type of graph. In any case, incorporating the above analysis makes the paper less “empirical” and more “principled”. \n\na) In SBM; graphs is logical that spectral positional encoding do not work well for r>1 because the structure of the SBM is encoded by the first  K non-trivial Laplacian eigenvalues if there are K communities (depending on the inter-class structural noise). For instance, a nice experiment should be to track the performance of the positional encoders as the inter-class structural noise increases. In the experiments in the paper one can infer that if the spectral info is not useless for r<3 in CLUSTER/PATTERN is because the interclass structural noise is large \n\nb) On the other hand, KNN graphs (e.g. CIFAR) or GRID graphs (MNIST) are typically broken in two communities just using the first non-trivial eigenvector (Fiedler vector). For this analysis see “SPECTRE: Spectral Conditioning Helps to Overcome the Expressivity Limits of One-shot Graph Generators”. \n\nRegarding the success of adjacency powers (which generalize shortest paths), it is interesting to confirm how not too many hops are needed in general. I suggest addressing these powers in terms of how powerful are to encode different orders of transitive information. However, the main drawback is that this method does not scale well in real-life graphs (e.g. reported out-of-memory in MNIST). \n\nThere are no experiments on SOCIAL NETWORKS (e.g. power-law) where hubs do exist and incorporate naturally the CLS-node concept. They also make shortest paths almost uniform (unit length), E.g. in the case of Facebook (“friends circles”) with two-step (r=2) separation, the proposed positional encoders become more ambiguous. \n", "summary_of_the_review": "A quite empirical paper that selects the best way of  \"static\" (not inductive) \"topological rewiring\" depending on the type of graphs. No theoretical insights are given beside a shallow spectral analysis. An important experimental limitation is that no social network is analyzed. The most challenging rewiring strategy (adjacency powers) is not scalable (see also the plots in the appendix). ", "strength_and_weaknesses": "* Strength: Model agnosticism is interesting,\n* Weaknesses: As stated above, the approach is neither inductive (positional encodings must be computed for every input graph in graph classification) nor scalable (e.g. the computation of transitive information even when r=1,2 may be prohibitive). The number of experimental baselines is very limited. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Uog8h4S7eO", "reviewer": "Reviewer_CvhJ", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "This paper proposes a method to augment the input graph with additional nodes/edges and use positional encodings as the node and/or edge features, expanding receptive fields from 1-ring neighborhoods to r-ring neighborhoods. Empirical experiments show that relatively small r-hop neighborhoods sufficiently increase performance across models and that performance degrades in the fully connected setting.", "summary_of_the_review": "The authors propose a method to augment the input graph with additional nodes/edges and use positional encodings as the node and/or edge features, expanding receptive fields from 1-ring neighborhoods to r-ring neighborhoods. However, this work lacks some innovation and has obvious limitations and deficiencies in the experimental datasets and baselines. ", "strength_and_weaknesses": "Strength\n1. The intrinsic design idea and logic of this framework are straightforward and clear, and with sufficient analysis and summary of related works, derivation, and proof, the rationality and validity of the framework are verified theoretically.\n2. The experimental settings are very detailed, and the experimental results can demonstrate the effectiveness and superiority of this method. \n\nWeaknesses\n1. In my opinion, the biggest problem in your framework is the lack of innovation. The positional coding method and virtual node strategy used in your method are existing methods in the existing work. It can be concluded that your work is to expand the perception threshold from 1-hop neighbor to r-hop neighbor and analyze its effect, which lacks innovation and originality.\n2. Though your experiment setup is very complete and the experiment data is very informative, your experiment dataset is kind of small compared to the real-world ones. Try to evaluate it on a larger dataset. Also, why not have some well-known position-encoding based GNNs as your baseline? Such as P-GNN (Position-aware graph neural networks, ICML 2019.) and Graphormer (Do transformers really perform badly for graph representation, NIPS 2021.) There is also a recent work that incorporates position encodings for graph rewiring (Position-aware Structure Learning for Graph Topology-imbalance by Relieving Under-reaching and Over-squashing, CIKM 2022), which also should be included in your baselines. \n3. In the main text part, it is best to use a diagram to explain your method design. In addition, in the experimental section of the main text, more interesting experimental results should be emphasized and further analysis should be given. Moreover, a large part of the main text introduces or summarizes other works, and the original work is relatively few.\n", "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": {}}]

Author rebuttal:

Decision: Reject