Rewiring with Positional Encodings for Graph Neural Networks
Authors: Rickard Brüel Gabrielsson
Mikhail Yurochkin
Justin Solomon
Venue: Accepted by TMLR ()

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 of the 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 competitive performance using traditional GNNs or graph Transformers.

Published in Transactions on Machine Learning Research (10/2023)
Rewiring with Positional Encodings for Graph Neural Net- works
Rickard Brüiel-Gabrielsson
brg@mmit. edu
Massachusetts Institute of Technology MIT-IBM Watson Al Lab
Mikhail Yurochkin
wwkhaail.uurocchiii..c com
MIT-IBM Walson AI Lab
IBM Reseorch
Justin Solomon
jsolomon edu
Massachusetts Institute of Technology
MIT-IBM Watson AT Lab
Reviewed on OpenReview: https: // operrevie.. net/ net/foree forum? dn3ZkqG2YV
Abstract
Several recent works use positional encodings extend the receptive fields of graph neural network (GNN) layers equipped with attention mechanisms. These techniques, however, extend receptive fields to the complete graph, substantial computational cost and risking change in the inductive biases of conventional GNNs, 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 a downstream GNN model, instcad of modifying the model itself. This makes our method model-agnostic i.e., compatible with any of the existing GNN architectures. We also provide examples of positional encodings that are lossless with 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 varicty models and datasots and reach competitive performance using traditional GNNs or graph Translormers.
1 Introduction
GNN layers typically embed each node of a graph as a function of its neighbors' (1-ring's) embeddings from the previous layer; that is, the receptive field of each node is its 1-hop neighborhood. Hence, at least r stacked GNN layers are needed for nodes to get information about their r-hop neighborhoods. Barceló et al. (2020) and Alon and Yahav (2021) identify two broad limitations associated with this structure: under-reaching occurs when the number of layers is insufficient communicale information between distant vertices, while over-squashing occurs when certain edges act as 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 the graph with that of a complete graph, these works propose positional encodings that communicate the connectivity of the input graph as node or odge features. As these methods operate on fully-connected 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,

---

Published in Transactions on Machine Learning Research (10/2023)
the success of the 1-ring GNNs suggests that local feature aggregation is 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 r ranges from (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 topology. We demonstrate the cumpute-performant trade-offs for different r-values and show that performance 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 graphs augmented with edges connecting vertices to their peers within distance S r. Our contributions are as follows: (i) We increase receplive fields using a simple pre- processing of graphs with positional encodings as edge and node features. (ii) We compare r-hop positional encodings on the augmented graph, specifically lengths of shortest paths, spectral computations, and powers of the graph adjacency matrix. (iii) We demonstrale that GNNs, with limited computational budget and without changing the architecture, can benefit from positional encodings and expanded receptive views that are smaller than the fully-connected setting, and we illustrate the compute-performat trade-offs.
2 Related Work
The Transformer has permeated deep learning (Vaswani et al., 2017), with state-of-the-art performance in NLP (Devlin et al., 2018), vision (Parmar et al., 2018), and genomics (Zaheer et al., 2020). Its core components include multi-hean 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 cach 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 as positional encodings to expand attention to all nodes (Kreuzer et al., 2021; Dwivedi and Bresson, 2021; Rong et al., 2020; Ying et al., 2021). Several works also adapt atlention mechanisms to GNNs (Yun et al., 2019; Cai and Lam, 2019; Hu et al., 2020; Baek et al., 2021; Veličkovíć et al., 2018; Wang et al., 2021b; Zhang et al., 2020; Shi et al., 2021). Furthermore, there is a recent line of work that seeks to improve Transformers on graphs: Rampášek et al. (2022) provide a taxonomy of positional encodings and present an alternative Transformer architecture for sub-quadratic attention; Shirzad et al. (2023) build on this work by introducing a sparse attention mechanism through virtual global nodes and expander graphs. Lastly, Kim et al. (2022) demonstrate that Transformers without graph-specific modifications can obtain promising results in graph learning both in theory and practice, by simply treating nodes and edges as independent tokens. In contrast with these papers, our work is architocturo-annosiic, demonstrating that augmentation and positional encodings can benefit Transformer- free GNN architectures and Transformer GNNs alike.
Ying et al. (2018); Gao and Ji (2019) and others introduce hierarchical pooling and improved information flow by shrinking the graph rather than extending it. This, therefore, represents an alternative to the multi-hop aggregation approach adopted in our work.
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 a center node and distant neighbors, using an involved hierarchical path aggregation method to aggregate a feature for each node. Like us, SPAGAN introduces the & k-hop neighbors around the center node as a hyperparameter; their model, however, has hyperparameters controlling path sampling, Beyond SPAGAN, Chen et al. (2019) concatenate node features, edge features, distances, and ring flags to compute attention probabilities. Li et al. (2020) show that distance encodings (i.e., one-hot feature of distance as an extra node attribute) obtain more expressive power than the 1-Weisfeiler-Lehma test. Chen et al. (2021) roduce graph-augmented multi-layer perceptrons (MLPs) that incoroprate multi-hop connections via powers of the adjacency matrix and focus on establishing the expressive power of graph-augmenter MLPs relative to graph neural networks. Sun et al. (2021) also use powers of the adjacency matrix but for multi- hop connections combined with self-label enhanced training. Graph-BERT introduces multiple positional encodings to apply Transformers to graphs and operates on sampled subgraphs to handle large graphs (Zhang
2

---

Published in Transactions on Machine Learning Research (10/2023)
et al., 2020). Yang et al. (2019) introduce the Graph Transformer Network (GTN) for learning new graph structure, which identifies "mela-paths" and multi-hop connections to learn node representations. Wang et al. (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 to a stochastically-sammlee neighborhood of neighbors within 5-hops of the central node. Isufi et al. (2020) introduce EdgeNets, which enable flexible multi-hop diffusion. Luan et al. (2019) generalize spectral graph convolution and GCN in block Krylov subspace forms. Abu-El-Haija et al. (2019) introduce a specialized MixHop Graph Convolution Layer for higher-order message passing. You et al. (2019) capture nodes' positions by sampling anchor nodes and learning non-linear disthnce-weighted aggregation from target nodes to the anchor-sets. Feng et al. (2023); Nikolentzos et al. (2020) explore the expressive power of r-hop GNNs and introduces specific r-hop GNN architectures aimed at augmenting this expressive capability. While the enhanced theoretical expressive power of GNNs achieved through r-hops aligns with our approach, our primary focus is on examining the empirical performance improvements that result from docoupling the r-hop rewiring from the GNN, as evaluated across various GNNs within a constrained computational budget.
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 mfmerroffiterations hyperparameters. Unlike GTN, we do not restrict to a particular graph structure. Broadly, our approach does not require architecture or optimization changes. Thus, our work also joins a 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 to generate embeddings and ag- gregate features, while Zhang et al. (2018) sample to deal with topological noise. Rossi al. (2020) introduce Scalable Inception Graph Neural Networks (SIGN), which avoid sampling by precomputing convolutional filters. Kipf and Welling (2017) preprocess dilfuusin on graphs for efficient training. Topping et al. (2021); Nguyen et al. (2023) use graph curvature to rewire graphs and combat over-squashing and bottlenecks.
In contrast, our work docs not use diffusion, curvature, or sampling, but expands receptive fields via meausformer-insppred 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.
3 Preliminaries and Design
Let G (V, denote directed graph with nodes V c No and edges V and let g be the set of graphs. For each graph, let functions fu : V + Rd and fe E - Rd denole node and edge features, respectively, and we let R denote the diameter of the graph. We consider learning on graphs, specifically node classification and graph classification. At inference, the input is a graph G. For node classification, the task is to predict a node label (v) R for each vertex e V. Using the node labels, the homophily of a 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 a label la R for the entire graph G.
Given the tasks above, GNN architectures typically ingest graph G (V,E, f., fe) and output either label or a per-node feature. One can view this as an abstraction; e.g. a GNN for graph classification is a map Fg: G - _ with learnable parameters 0. These architectures vary in terms of how they implement F'g 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 et al., 2014) use the cigendecomposition of the graph Laplacian to perform spectral convolution. (iii) Diffuusin models (Wang el al., 2021a; Kliepera 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 undcr-r and over-squahhin (Alon and Yahav, 2021). Spectral approaches share similar convolutional bias as spatial models and face related problems (Kipf and Welling, 2017). On the other hand, Transformers with complete
3

---

Published in Transactions on Machine Learning Research (10/2023)
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 a more general proximity bias than diffusion without committing to a specific model. Our method is built on the observation that F9 can be trained to ingest modified versions of the original graph that better communicate structure and connectivity. Hence, input graph. To preserve the information about the original topology of the input graph, we add positional encodings. More formally, we design functions g 9 - 9 that modify graphs and give features to the new nodes and edges. These functions can be prepended to any GNN Fg : g + R" as Fg og::g G RR.
add new edges, nodes, and features to the
The following are desidcrata 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 to r-hop neighborhoods we reduce computational load relative to complete-gras graph 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 to a 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 imput G = (V, E, fe), we create a new graph G" = E', such that G a subgraph of G'. Expanded receptive fields are achieved in G' by adding edges docorated with positional encodings as node or edge attributes; we also add a fully-connected CLS node ("CLS" is short for classification per Devlin et al. (2018)). G" is still a graph with node and edge attributes to which 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 a 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 to generate G' in two steps:
e 9 and a positive integer r é N,, we add edges between all nodes within r hops of each other in G to create G. = =V, fr fc). G annotated with edge features, we assign to cach edge in E an appropriate constant feature Ce. See Figure for an illustration of the expanded receptive field around node.
Expanded receptive field. Given a graph G =
CLS node. Following Gilmer et al. (2017), we also include "CLS" or classification node to graph connected to all others. We follow this procedure: Given graph G, we (i) initialize a new graph G' (V', F l f') G, (ii) add a new node VeLs to V', and (iii) set (VCL)) == Co for a constant. C.- Finally, we set E' := Eu UnEV v), (1, vCLs)), with f(((VCL)))) ((((U, == Ce, where C. defined above.
4.2 Positional Encodings
Given only the connectivily of a rewired graph G, (V'''', from the two-step procedure above, it may not be possible to recover the connectivity of the original graph G E, E, fe). In the extreme, when large and G is connected, G¹, could become fully-connected, meaning that all topology is lost-removing the central eue for graph-based learning. To combat this effect, we encode the original topology of G into G² via positional encodings, which are node and/or edge features. We consider several positional encoding
4

---

Published in Transactions on Machine Learning Research (10/2023)
Original edge
Added edge
Rewire
r r= 2
e5
61
61
e4
e8
E3
C3
C7
Figure 1: Topological rewiring from the perspective of the black center node. Left: Original graph G. Right: Rewired graph G" with r= 2 and new edges es; <B, 67, and eg. Various subsequent positional encodings allow the NN (on input G,)) to discern certain or all aspects of the original topology (i.e., G) while alleviating over-squashing and under-reaching.
functions for edges Ps 9 V x V Th or nodes P. : 9 V R", appending the output of Pe as edge or Pe as node features to Gy Section 4.2.1 lays out propertics compare choices of pe and/or Pv- 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 to encode the subgraph topology of G within G' in vertex features pe or edge features Pa- Below, we state a few propertics we can check to give framework for comparing the capabilitics and biases of possible choices.
Lossless encoding. While GNN can ignore information in input G', it cannot reconstruct information that has been lost in constructing G' from G. Yel, there can be benefits in forgetting information, e.g., when dealing with noisy graphs or incorporating stronger inductive bias (Rossi et al., 2020; Klicpera et al., 2019). That said, a simple property to check for G' equipped with positional encoding features Pe is whether we can recover G from this information, that is, whether our encoding lossless (or non-ireusive). As long as it is possible to identify within g(G), 9 an injection and non-invasive. Hence, sufficient condition for Jossless positional encodings as follows: If all edges in G' have positional-encoding values not shared with any edge in G, then g : + 9 is bijection. One way to achieve this condition is to use an additional edge feature that is unique to the 1-ring, i.e., unique to G.
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-Weisfeiler-Lehmmal (WI.) test and hence more powerful than 1-hop vanilla spatial GNN models (Xu al., 2019). The combination of increased receptive fields, positional encodings, and choice of subsequent GNN models determines discriminative power. In fact, it follows from Ying et al. (2021) that the positional encodings presented below together with increased receptive field r>1 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 working with r-hop neighborhoods. The cost computing positional encodings affects total inference time, which may be relevant some lcarning settings. However, our sctting, the runtime of computing positional encodings is an order of magnitude less than the subsequent inference time, and in our implementation the asymptotic runtimes of computing the positional encodings the same. See Appendix F.
5

---

Published in Transactions on Machine Learning Research (10/2023)
Local vs. global. The positional encoding of vertex 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 anywhere in G could affect all of the positional encodings.
Inductive bias. Our positional encodings can bias the results of the learning procedure, effectively com- municating 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 are insignificant. More subtly, suppose e is the distance (of length S r)) between two nodes in G corresponding to new edge in E'. Using & directly as positional encoding rather than a decaying function, e.g. e- makes it casier 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 on G' are sufficient to learn to imitate the behavior of prescribed multi-hop model on G, e.g. whether a layer of our GNN applied to G' can capture molti-hop diffusion along G.
Over-squashing and under-reaching. Section 6.1 demonstrates, via the NeighborsMatch problem (Alon and Yahav, 2021), that increased receptive fields as well as the CLS-node 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 in the sense that it enables effective information propagation for the task at hand. Our experiments showing that expanded receptive fields alleviate the over-squashing 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 GY,, the shortest-path positional encoding takes Pe E I.. r) to be the integer length of the shortest path in G between the corresponding nodes of E. 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 GNNs like diffusion over large neighborhoods. Shortest-path positional encoding was previously used by Ying et al. (2021) for extending G to a 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 = - 1/21 where D is the degree matrix and A is the adjaccncy matrix. We call the result spectral positional embedding. We can use the q smallest non-trivial Laplacian eigenvectors of G as node-based positional encoding Po V + IR;; i.e., Pe is the spectral embedding of G in G'. Note that q represents an additional approximation as it truncates the spectrum. Following Dwivedi et al. (2020), since these eigenvectors are known only up to a sign, we randomly flip the sign during training. Prior work consider Laplacian eigenvectors 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 encoding fails to distinguish isospectral graphs (Von Collatz and Sinogowitz, 1957), but these are rarely encountered in practice. On the other hand, spectral signatures common for graph matching and other tasks (Hu et al., 2014). Morcover, unlike the remaining features in this section, spectral positional encodings capture global information about G rather than only r-neighborhoods. Finally, we nole that the diffusion equation for graphs can be written as u = -Au, where u is a function of vertex and time, and U, is the derivative of u with respect to time; this graph PDE can be solved in closod-form given the cigenvectors and eigenvalues of A. Hence, given the spectral embedding of G in G', we can simulate diffusion- multi-hop GNN architectures up to spectral truncation.
6

---

Published in Transactions on Machine Learning Research (10/2023)
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 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 and j in G. Concatenating the powers from h = l,....r, we get for cach edge e G' an integer vector Pe e N" giving the powers of the adjacency matria positional encoding.
This embedding can be used to recover the shortest-path embedding. This adjacency-derived embedding also generalize the inductive bias of diffusion- based multi-hops GNNs, In particular, diffusion aggre- gation weights often approximated using a Taylor series, W = Ei=o 0,A' s Σi 6,A' f := W, where 8 are prescribed decaying sequence (0; > 0z-1). The entries of W above can be computed lincarly from the adjacency-powers positional encoding. Hence, assuming the underlying model is an universal function ap- proximator, up to truncation of the series the adjacency-powert positional encoding is strictly more general than using prescribed diffusion-based aggregation weights on G.
Lossless encodings. The previously discussed Jossless-encodiing properties of our graph rewiring method are accomplished by two of the mentinee positional encodings:
Proposition 1. Shortest-pate and adjacency matriz positional encodings yield lossless rewirings.
Proof. Recovering the original graph G= EV from the rewired graph G' = (V,E") is almost trivial. With the shortest-path position encoding the original graph can be recovered via {ele E', E', 13 and for poverssof-heexdjjcecyy--attt encodings via E (ele e E", (pa) =1.
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., 2017); see Appendix B for details. For cach model, consider graph rewiring with different r-hop receptive field around each node, and compare with and without the CLS-node, well as the three positional encodings introduced in Section 4.2.2.
Input and readout layers. Typically, GNNs on a graph G = Sr, first embed node features fu and edge features fe through a small foed-forward network (FFN) imput layer. When incorporating positional encodings per odge/node, we embed using a 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, a readout layer is applied to the last GNN layer L. For node classification, it is typically FFN applied to each node feature hg. For graph classification, it is typically node features h4. For graph classification and when using the CLS-node, we aggregate by applying the FFN to the CLS-node's features in the last layer.
FFN applied to the mean sum aggregation of all
6 Experiments
We evaluate performance on six benchmark graph datasets: ZINC, AQSOL, PATTERN, CLUSTER, MNIST, and CIFAR10 from (Dwivedi et al., 2020). The benchmark includes a training time limit of 12 hours; we use similar compute to their work via a single TeslaV100 GPU. Training also stops for a 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 datasots, 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, densily is the average of the densities (defined as the ratio (Fl//v/)) of each graph in the dataset rewired to the respective receptive field size. See Appendix A for details.
Table compares our best results with other top performing methods and models. All our top performing models come from the GatedGCN, although the Transformer performs comparably; however, the Transformer harder to train see Appendix B. MoNet performs worse but still sees significant improvements from
7

---

Published in Transactions on Machine Learning Research (10/2023)
our approach. Our GatedGCN implementation was taken from the same work (Dwivedi et al., 2020) that introduced the benchmarks and code that we use. Thus, hyperparameters might be better adapted to the GatedGCN. This highlights the benefits of our model-agnostic approach, which allows us to pick the best models from Dwivedi et al. (2020) and combine them with our methods. Our approach with 100K paramoters achieves top performance on all datasets among models with 100K parameters and even purforrmm 500K- parameter models.
ZINC, Graph Regression. ZINC consists of molecular graphs and the task is graph property regression for constrained solubility. Each ZINC molecule is represented as 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 r is increased. Performance across all settings noticeably improves when increasing r above 1. Top performance is achieved with the CL.--ood and powers-of- nowers-of-the-adjacee the-adjacency positional encoding at = 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 v, which is likely due the global nature of these changes to the graphs. The GatedGCN and Transformer perform comparably for the same settings, with a slight edge to the GatedGCN. The two models show the same performance trends between scttings, i.c., both incrcased receptive fields and the CLS-node boost performance. Further, Ying et al. (2021) include a performance of 0.123 on ZINC with their Graphormer(500K) i.e., a Transformer with positional encodings and complete attention. However, their training is capped at 10,000 epochs while ours is capped at 1,000 epochs; training their Graphormer(500KK with same restrictions leads to 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 (see Table 3); in these settings, better performing r are larger than for ZINC. However, when including CLS node or spectral positional encodings, performance changes much less across different r. This indicates the importance of some form of global bias on this dataset. At least one of larger r values, spectral posit encoding, or the CLS-token is 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 to the importance of including edge features for optimal use of expanded receptive ficlds and positional encodings.
CLUSTER, Node Classification. CLUSTER is a node classification dataset generated using a stochastic block model (SBM). The task is to assign a cluster label to each node, There is 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 r 3 3 all graphs are fully connected, and more than 99% of them are fully connected at = 2. Hence, these graphs are dense. Significant improvements are achieved by increasing r 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.1.
PATTERN, Node Classification. The PATTERN dataset is also generated using an 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 to 3. Similarly to CLUSTER, the density column shows that the graphs are dense. Significant improvements are achieved by increasing r > and/or using the CLS-node. Performance generally decreases at r = 3. Similarly to CLUSTER, the CLS-node helps at r= 1, but for both CLUSTER and PATTERN, top performing model comes from a larger >> 1 without the CLS--ode, suggesting that trade-offs exist between CL.S-node and increased receptive fields. Compared to CLUSTER, our approach shows a smaller performance boost for PATTERN, which suggests that our approach is more helpful for graphs with low homophily. We investigate this further in Appendix F.
8

---

Published in Transactions on Machine Learning Research (10/2023)
Table 1: Benchmarking. Higher is better for all but for ZINC and AQSOL where lower is better. Benchmarks can be found Dwivedi et al. (2020); Corso et al. (2020); Bouritsas et al. (2020); Dwivedi and Bresson (2021).
The benchmarks (Dwivedi et al., 2020) and corresponding leaderboard have 100K and 500K paramcter entries. OOM is short for out-of-memory errors.
Datasets:
PATTERN
CLUSTER
MNIST
CIFAR1O
ZINC
AQSOL
task:
node class.
node class,
graph class.
graph class.
graph reg.
graph reg.
# graphs:
14000
12000
70000
60000
12000
9823
Avg # nodes:
117.47
117.20
70.57
117.63
23.16
17.57
Avg ff odges:
4749.15
4301. 72
564.53
941.07
49.83
35.76
MoNee(100K)
85.48220.037
58.064 131
90.805+0.000 0.032
04.655+0.518
0.397=0.0110
1.395
(10O)))
75.824= 1.33
57. 37.732+0.338 323
95. 0. 205
64.22330.455 453
0.475=0.0007
1.441 023
GraphSage(1000) 100K)
50.516=0.001
50.45440. 145
0.
65.76770.300
0.468=000003
1.431
GIN (10K)
85.59000.011
58.384+ 236
96 06 252
55. 55.255 I. .527
0.387=0.0155
0.894+0.024
PNA(100K)
86.730=0.0500
63.020+0.266 262
97.940=0.122 120
70.350+0.630
0.188=0.004
1.083+0.011
(100)GC
$4.48000.1222
60.40440.419
97.340+0.143
67.312+0.311
0.328:0.003
0.295+0.016
CateeGCCNPPE/E(6000
86.363 127
+4.08880.344
OOM
OOM
0.214=0.006
0. 0.996
Graph (500k)
54.941 739
27.121 471
OOM
00M
0.598=0.049
1.110#0.010
Ours(10KK)
86.757=0.031
77.575=0.149
08.74
73.808=0.193
0.143=0.006
0.920=0.009
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 hand- written 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 r = 3, but training at r 4 excceds our memory limit. Noticoable perfor- mance gains are achieved at r- 2, but performance generally decreases at r The CLS-node consistently improves performance at r= 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 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, or airplane. Table 7 provides results for r from to 3. Not all graphs are fully connected at r 3 but training at r = led to out-of-memory issues. Top performing versions are all at r 1, and performance degrades for r> 1. As with MNIST, the CL.S-node only improves performance at r = 1, again indicating its shared (subsumed) effects with increased r-sizes.
Table 2: Increasing r on ZINC/molecules 100K parameters.
danery
traseadpph
tmasedhort
tranedorridd
crun-lp
tean-lppele
gen-sbor
gea-p
pes-ppck
sw1
.14
0.54L40.044
0.20000.012
0 0.58
2012
0.265.0014
0.220un
0.25
122
0.265400455
022140022
0.27441/227
-17
a 3.37-00009
o 135-40.000
0.200-6.0000
0.365-0.024
03355-0000
0330--0011
0.156-0011
0355-0019
8 0:30400022
0.253-0.023
0.198-0.000
m:
-00
a 0200-00000
100000000
8.247-8.024
119770.015
0297-0001
0245-00118
0110--007
0135-00077
0215-0005
0.155-0.005
0355-0005
0
a 0.217-00011
0.145-11.000
0.2 0:20144:0077
0.194-11.44
0:32500::3
0225--0122
011000000
0.145-0.006
0,236-00005
0.167-0000
0335-0000
0:37--1.85
mib
a 8223
0300432:02
6:20000011
0:351-01819
0.165-00010
0.241-0005
0:25--0055
0.12540005
0:331-0.:3
0.29--1.12
.21
0.200...0005
c:20000.010
03752888:2
0.315-00000
0.17140007
0.152-0007
0:255.0000
0.18540000
0.35280005
.70
ASS8ac:012
6:211
0.371-8023
0.358.0005
0.172.0003
0.152.00014
0:25000115
0.157410044
0.51482005
0.227A11.:22
2-8
.65
0:21240:012
0.541a0.055
0.28540.001
0,258LI0005
0.19210005
0.180.0012
0.276.0013
02200100255
90
0:385+0:013
0.305.0.000
0.386-000
0.319-11077
0311-00'
0:357-0
03250-0055
0-305-0011
0365-8017
0.332-0011
1:10
8.202w00001
8120940..01
0.30046.007
0.20550..00
0.306-0.000
0.350-00:1
0.27600015
0.30-00
0.275-0005
0:30600003
0337580.03
0.336+0.00
gen: GatedGCN, trans: Transformer, adj: adjacency p.e., short: shortest-path p.e., 1p: spectral p.e., cla: CLS-node
Table 3: Increasing r on AQSOL 100K parameters.
demery
grssbbrrt
gm
mestwad)
menealpplle
mon-lppc
1
.17
1.22440100
0.920-0.00
1251-0007
0.227-0.019
6:00640.001
1.50
12614f1117
L.0040015
131
0.15400000
12H4
.37
12254
L275.00.9
L.0000.010
1.5770.00
120540000
13784002
L1650005
126540
11641000
12300085
0351-0017
100500.010
0.56120.000
1.2040.000
127720.085
1289L0017
121600070
LIB040IC1
L155.0.017
.57
L132L0012
0.55.0.0
1550u5.000
0.507.0.010
122010.008
1183200077
LiSSL0027
L158000006
LI07ADUOL
1-5
.76
LISOLNEE
0.5L.0002
1.4655.002
0:012.0.012
123110.000
1.106..0200
1.170.0.000
12011000
1205LIIDE
1:6
.22
1 1155411001
B311+0100
1055400:77
0335-0012
145140.018
(102340.00
1.25+01011
1 115580011
1226-0015
1151-0015
119143.011
.47
L81S-0002
030.0000
1.00600.01
0.330-0.004
1.25++0.0
1 1155-000
L19740024
1.141-00055
12:1
.30
1.054-0.014
03322.0000
1685500.000
0:00140.014
1.213-0.025
1 112960043
12:240022
114450000
2-0
.02
LIMOLEU00
LJ4221092
0335500000
1608,0.011
0:6220.000
1.24540.044
1205501165
126650017
1180000000
1118110044
1.20510005
2-10
.05
LIM2L1U00
0096610000
1.085.0.000
0,35380008
1607,0.011
0:56100.000
1.22540.001
129410.007
11641001
L161.0015
1.1510004
gen: GatedGCN, mon: MoNet, adj: adjacency p.e, short: shortest-path p.e., 1p: spectral p.e., cle: nod-
9

---

Published in Transactions on Machine Learning Research (10/2023)
Table 4: Increasing r on CLUSTER 100K parameters.
Eype creatt
Boneehertee 74
Bead (2400:8.99
Se 13.27-0.107 01.50622
rel
1856666119
08.8587..80
4E
1/0
77.096-0.201
17.200
17.077
77.508.0.150
GatedGON, trans: Transformer, adj: adjacency short: shortest-path p.e., Ip: spectral p.e., cls: CLS-node, * Training not
converging
Table 5: Increasing
PATTERN 100K parameters.
type:
density
gen-adj
gen-adj-cls
gen-lp
gen-lp-cls
gen-short
gen-short-cls
r=1
.43
85.715=0.036
86.723=0.006
86.547+0.026
86.713=0.031
85.681=0.033
86.73220.020
>.99
86.69
86.707a0.029
86.723
86.74710.011 86.744=0.015
86.75720.031 86.712=0.031
86.73660.011
r=
1.0
85.471=0.949
84.657+0.977
86.718+0.00 024
86.739=0.027
gen: GatedGCN, adj: adjacency p.e, short: shortest-path p.e., lp: spectral p.e., cls: CLS-node
Table 6: Increasing on MNIST 100K parameters.
type:
density
gen-ad
gen-adj-cls
gen-lp
gen-lp-els
gen-short
gen-short-cls
r=1
.13
08.537=0.089
98.522+0.083
98.395+
98.542=0.079
98.373=0.
98.545=0.057
r-2
.34
98.630=0.134
98.74330.062
98.720=0.067
98.60510.032 98.570=0.117
98.59710.070 98.315
98.552+0.107
r-3
.58
98.035+0.094
98.190.0.141
98.51310.14 0415
98.390=0.104
gen: GatedGON adj: adjacency p.e., short: ahortest-path p.e., Ip: spectral p.e., cla: CLS-node
Table 7: Increasing r on CIFAR10 100K paramcters.
type:
density
gen-adj
gen-adj-cls
gen-lp
gen-lp-cls
gen-short
gen-short-cls
r-1
.08
73.415=0.717
73.498=0.842
72.525=0.471
73.808+0.193 71.745=0.325 70.318=0:295
72.610#0.574
72.950+0.520
r=2
.21
72.037=0.400
72.480+0.420
02.085+0.487 70.380+0.300
72.127=0.471 71.285=0.729
71.470=0.508
r-3
.38
70.688+0.171
69.580+0.488
71.188+0.498
gen: GatedGCN, adj: adjacency p.e., short: shortest-path p.e., 1p: spectral p.e., cls: CLS-node
6.1
NeighborsMatch, Over-squashing
Alon and Yahav (2021) introduce a toy problem called NeighborsMatch to benchmark the extent of over- squashing in GNNs, while controlling over-squashing by limiting the problem radius Fp. The graphs in the dataset are binary trees of depth equal to the problem radius Ty. Thus, the graphs are structured and sparse, and the number of edges grows linearly with the increased receptive field See Figure 2, Appendix C, for results with GatedGCN. Increasing the receptive field with a 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 r 2 and r but with a much longer tail. Thus, this further showcases the subsumed as well as different effect (complementary and conflicingg the receptive field and the CLS-node have, as also observed on the other benchmarks.
6.2 Computational Analysis
For all positional encodings, the number of edges determines the asymptotic runtime and memory use. The CLS-node only introduces an additive factor. Figures 5 and in Appendix E show that the runtime in practice scales roughly the same as the density, as the receptive field size increased; real runtime has a significant constant factor.
6.3 Selecting Positional Encoding and Hops Size
We recommend the adjacency positional encodings logether with the CLS-node. In terms of ranked perfor- mance across the datasets, adjacency and spectral positional encodings perform the same, but the spectral encoding performs considerably worse on the ZINC datasct, while the differences are smaller on the other datascts. Additional experiments in Appendix D, Figure 3, assess the discriminative power of the different encodings. However, there is no positional encoding superior in all aspects. Instead, each one has unique
10

---

Published in Transactions on Machine Learning Research (10/2023)
benefits well as drawbacks. This is made apparent by considering performance differences across values of r. Furthermore, the CLS--ode is part of the best-performing config- uration more often than not. Similarly, no fixed r is optimal for all datasets. Instead, optimal r depends on the dataset and the amount compute, and our experiments showcase the compute-perforaace tradc-off. Appendix shows that increased diminishes the reliance on homophily as an inductive bias, and thus low homophily of dataset could be used as an indicator for selecting an increasod r. 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 multiple datasets; here the CLS-node spectral positional encodings may be preferred, computationally cheaper, alternatives to increasing
parameter and observing the
From this empirical study, for picking optimal r, we recommend computing the densities for increasing 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 to significantly reduce the compute compared to complete attention. See Appendix for further discussion.
7 Discussion
Our simple graph rewiring and positional encodings achieve competitive performance, widening receptive fields while alleviating over-squashing. This is much due to the ability to easily apply our method to models that stem from a large body of work on GNNs, highlighting the benefits of our model-agnostic approach.
The reality that attention with complete receptive fields still computationally intractable for most practitioners and researchers. However, here we show the compute-performance trade-offs of increased receptive fields and that significant performance boosts 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 GNN architectures.
Acknowledgements
The MIT Geometric Data Processing group acknowledges the generous support of Army Research Office grants 1911N1200116 and W911NF2110293, of Air Force Office of Scientific Research award FA9550-19- 1-031, of National Science Foundation grant CHS-1955697, from the CSAIL Systems that Learn program, from the MIT IBM Watson AI Laboratory, from the Toyota CSAIL Joint Research Center, from a gift from Adobe Systems, and from a Google Research Scholar award.
References
Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyun- yan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing, 2019.
Cri 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, has/2006.0925, 2020.
11

---

Published in Transactions on Machine Learning Research (10/2023)
Xavier Bresson and Thomas Laurent. Residual gated graph convnets, 2018.
Rickard Brüel Gabriclsson. Universal function approximation on graphs. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 19762-196 -9772. Curran Associates, Inc., 2020.
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. In Yoshua Bengio and Yann LeCun, editors, 2nd International Conference on Learning Representations, ICLR 2014, Bonff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014.
Deng Cai and Wai Lam. Graph transformer for graph-to-sequence learning. CoRR, abs/1911.07470, 2019.
Benson Chen, Regina Barzilay, and Tommi Jaakkola. Path-augmented graph transformer network, 2019.
Lei Chen, Zhengdao Chen, and Joan Bruna. On graph neural networks versus graph-augmented (mlp)s. In International Conference on Learning Representations, 2021. URL tiqI7w64JG2.
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. In Advances in Newral Information Processing Systems, 2020.
Zihang Dai, Zhilin Yang, Yiming Yang, Jaime G. Carbonell, Quoe V. Le, and Ruslan Salakhutdinov. Transformer-xl: Attentive language models beyond fixed-length context. CoRR, abs/1901.0220 2019.
A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the em algorithm. Journal of the Royal Stotistical Sociely. Series B (Methodological), 39(1):1 38, 1977. ISSN 00359246. URL http: http:://wwwwjsooo
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.044: 04805, 2018.
Vijay Prakash Dwivedi and Xavier Bresson. generalization of transformer networks to graphs, 2021.
Vijay Prakash Dwivedi, Chaitanya K. Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Bench- marking graph neural networks, 2020.
Jiarui Feng, Yixin Chen, Fuhai Li, Anindya Sarkar, and Muhan Zhang. How powerful are k-hop message passing graph neural networks, 2023.
Ari Frankel, Cosmin Salta, Coleman Alleman, and Reese Jones. Mesh-based graph convolutional neural networks for modeling materials with microstructure, 2021.
Hongyang Gao and Shuiwang Ji. Graph u-nets. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Ma- chine Learning Research, pages 2083 2092. PMLR, 09 15 Jun 2019. URL https://proceedings mlr. press/v97/ hatps//v//gaol9// gwwgga.99..... htmll.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 94th International Conference on Machine Learning Volume 70, ICML''1, page 1263-1272. JMT..org, 2017.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In T. 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.
Nan Hu, Raif M. Rustamov, and Leonidas Guibas. Stable and informative spectral signatures for graph matching. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition (CVPR), June 2014.
Ziniu Hu, Yuxiao Dong, Kuansan Wang, and Yizhou Sun. abs/2003.01332, 2020.
Heterogencous graph transformer. CoRR,
12

---

Published in Transactions on Machine Learning Research (10/2023)
Elvin Isufi, Fernando Gama, and Alejandro Ribeiro. Edgenets: Edge varying graph neural networks. CoRR, abs/22011.07 .07620, 2020.
Guolin Ke, Di He, and Tie-Ya Liu. Rethinking positional encoding in language pre-training. CoRR, abs/2006. 15595, 2020.
Jinwoo Kim, Tien Dat Nguyen, Seonwoo Min, Sungjun Cho, Moontae Lee, Honglak Lee, and Seunghoon Hong. Pure transformers are powerful graph learners, 2022.
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-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, JCLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
Johannes Klicpera, Stefan Weißenberger, and Stephan Güinnemann. Diffusion Improves Graph Learning. Curran Associates Tnc., Red Hook, NY, USA, 2019.
Devin Kreuzer, Dominique Beaini, William L. Hamilton, Vincent Létourneau, and Prudencio Tossou. Re- thinking graph transformers with spectral attention. CoRR, 2tee/2106.088900 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-Wen Chang, and Doina Precup. Break the ceiling: Stronger multi- scale deep graph convolutional networks. In Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, E. Fax, and R. Garnett, editors, Advances in Newral Information Processing Systems, vol- ume 32. Curran Associates, Inc., 2019. URL attps://proceedings neuripe. haarripp.c/paperr201///// ccc1344e2fa000fffcca111aaaaa3 Paper pdf.
Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily necessity for graph neural networks?, 2021. URL /ttps://arxxi..rrg 06144
Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Ts homophily a necessity for graph neural networks? In International Conference on Learning Representations, 2022. URL https://openreviee wtw.sewww.nno.oooonnneeo ucASPPD9GKN.
F. Monti, D. Boscaini, J. Masci, F. Rodola, J. Svoboda, and M. M. Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. In 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 5425-5434 Los Alamitos, CA, USA, jul 2017. IEEE Computer Society. doi: CW00///VP..01..557. URL https: weeecomppteesoccittoo.... org/ 10. #109/CVPR.225 2017.200..00 576.
Khang Nguyen, Nong Minh Hieu, Vinh Duc Nguyen, Nhat Ho, Stanley Osher, and Tan Minh Nguyen. Revisiting over-smoothing and over-squashing using ollivier-ricci curvature. In Andreas Kranse, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 25956 25979. PMLR, 23 29 Jul 2023. URL https: htop:://prooo https://proceedingg. mml.innnmmm.......mmmmmm..mm...m press/v202/ nguyen23c. html.
Giannis Nikolentzos, George Dasoulas, and Michalis Vazirgiannis. k-hop graph neural networks, 2020.
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.
13

---

Published in Transactions on Machine Learning Research (10/2023)
Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for a general, powerful, scalable graph transformer. In S. Koyejo, S. Mohamed, A. Agar- wal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, vol- ume 35, pages 14501-14515. Curran Associates, Inc., 2022. URL http:///000001111000000040042200
paper wwt.ss/papee//022//555/5
Conference pdf.
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. Balean, and H. Lin, editors, Advances in Newral Information Processing Systems, volune 33, pages 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.11199 2020.
Yunsheng Shi, Zhengjie Huang, Shikun Feng, Hui Zhong, Wenjin Wang, and Yu Sun. Masked label prediction: Unified message passing model for semi-superviset classification, 2021.
Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J. Sutherland, and Ali Kemal Sinop. Exphormer: Sparse transformers for graphs, 2023.
Chuxiong Sun, Hongming Gu, and Jie Hu. Scalable and adaptive graph neural networks with self-label- enhanced training, 2021.
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. arXio preprinl arXiv:2111.14522 2021.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In 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.
Petar Veličković. Message passing all the way up, 2022. URL httpp///aaaxii../aaaa/////////
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. Tn Abhandlungen aus dem Mathema- tischen Seminar der Universität Hambury, volume 21, pages 63 77. Springer, 1957.
Guangtao Wang, Rex Ying, Jing Huang, and Jure Leskovec. Multi-hop attention graph neural networks. In Proceedings of the Thirlieth International Joint Conference Artificial Intelligence (IJCAT), pages 3089 3089-3096, 2021a.
Guangtao Wang, Rex Ying, Jing Huang, and Jure Leskovec. Multi-hop attention graph neural network, 2021b.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
Yiding Yang, Xinchao Wang, Mingli Song, Junsong Yuan, and Dachong Tao. Spagan: Shortest path graph attention network. In Proceedings of the Soventy-Eighth International Joint Conference on Artificial Intelli- gence, IJCAT-19, pages 4099-41111 -105- International Joint Conferences on Artificial Intelligence Organization, 7 2019. doi: 10.24963/ijeaa.200 2019//.6
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di Hc, Yanming Shen, and Tic- Yan Liu. Do transformers really perform bad for graph representation? CoRR, abs/2106.05234, 2021.
14

---

Published in Transactions on Machine Learning Research (10/2023)
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hicrarchi- cal graph representation learning with differentiable pooling. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Sys- tems, volume 31. Curran Associates, Inc., 2018. URL #ttp::/0fff...iettaaaratfteeeee2 Pa5 pdf.
prrrr /elper_files/// files/
Jiaxuan You, Rex Ying, and Jure Leskovec. Posilion-aware graph neural nelworks, 2019.
Scongjun Yun, Minbyul Jcong, Rachyun Kim, Jacwoo Kang, and Hyunwoo Kim. Graph transformer networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché-Bue, E. Fox, and R. Garnett, editors, Aduances in Newral Information Processing Systems, volume 32. Curran Associates, 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: Transformers for longer sequences. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Newral Information Processing Systems, volume 33, pages 17283-1111 17297. Curran Associates, Inc., 2020.
Jiawei Zhang, Haopeng Zhang, Congying Xia, and Li Sun. Graph-bert: Only attention needed for learning graph representations, 2020.
Yingxue Zhang, Soumyasundar Pal, Mark Coates, and Deniz Üstebay, Bayesian graph convolutional neural networks for semi-supervised classification, 2018.
15

---

Published in Transactions on Machine Learning Research (10/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 learning rate docay strategy. The initial learning rate set to 10 and is reduced by half if the validation loss does not improve after a fixed ('lr schedule palience") number of epochs, either 5 or 10. Instead of setting a maximum number of epochs, the training is stopped either when the learning rate has reached 10 or when the computational time reaches 12 hours hours for NeighborsMatch). Experiments are with 4 different seeds; report summary statistics from the 4 results.
Below we include training settings for the different datasets.
A.1 ZINC
"model": GatedGCN and Transformer, bbatch_sizee" 128, "Ir
10,
"max_time" time": 12
A.2 AQSOL
"model": GatedGCN and MoNet, "batch_ "batch_size": :ize": 128,
sarrsscheuule__m sechedull__pttience". -_t_paaataae:: 10, fmax_timen 12
A.3 CLUSTER
"model": CatedGCN and Transformer, cratch_sizee. 48 (GatedGCU), 32 or 16 (Transformer), "Ir
5,
"max_times time": 12
A.4 PATTERN
"model": " GatedGCN,
"batch "batch_size size": 48,
"Ir far_sshedule,,o sondduul_patience..... 5,
"max_taa time": 12
A.5 MNIST
"model": GatedGCN, :batch_size":: 128, "Ir wwtsssccheeeeeeeeeeeee 10, "max_time time": 12
A.6 CIFAR10
"model": GatedGCN, "batch seatch_sizee: 128,
"Ir str__scheule__pe "aaieddule_patience... 10,
"max_ time": 12
16

---

Published in Transactions on Machine Learning Research (10/2023)
A.7 NeighborsMatch
"model": CatedGCN, "batch_size"" size": 256,
wtlssssche_eaatiiiiee 10, "max_ "max_time" time": 6
Transformer Implementation
We implemented a simple version of the Transformer adapted graphs:
i # Σ
+
JeNiu(s)
with
2 -BN(ET))
" Che
exp(a!
1.k
ai Eyorio exp(d
e =FFN(E))) e
Here, and are node and edge features (resp.) from the previous layer. WR, A, B dRd and C Rixd are learnable weight-matrices, H is the number of attention heads, and BN is short for batch normalization. k-1 denotes the concatenation of the attention heads.
B.1 Design Choices and Challenges
There are many variations on the Transformer model. Following Ying et al. (2021), we put the normalization before the multi-head attention, which caused instability when training CLUSTER with Laplacian (spec- tral) positional encodings. This was fixed by putting the normalization after using layer normalization instead of batch normalization; however, these changes reduced performance on 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-head attention which puts number-of-heads dimension vectors on each edge seen directed. Hence, the memory load becomes 2 x [E] num nua_heads (in experiments, num heads 6). which compared for GatedGCN is only 2x |E. This causes a memory bottleneck for the Transformer that may force one to use a 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), we ran the path-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 of relative positions in the multi-head attention (see below); however, we found performance to comparable.
In natural language processing, the input is a sequence (a line graph) x (#1...., In) of text tokens from vocabulary set V, with each token having one-hot-encoding fy V [0, 10 The word embeddings
17

---

Published in Transactions on Machine Learning Research (10/2023)
E Rund for n tokens are formed as E = (Wembedfu(z))) a2 E x) where Wembed Rdd is learnable weight matrix.
The original Transformer model used absolute positional encodings. This means that we add the positional encoding to the node embedding at the imput layer. Consider a positional encoding function Pe No - R Then the first input is
h = (Wembeafy (v( + po(i) | .......). =
= E
where U (Pe(1) i= 0, ..... n) Rundd Typically Ps contains sine and cosine functions of different frequencies:
Pe 2 x sin( sin(#/10000 (h (000000002000000222)))))
where l e is the position and Ze N is the dimension. That is, each dimension of the positional encoding corresponds to a simusoid. The wavelengths form a geometric progression from 2π to 10000 x 2x. This function was chosen because it was hypothesized that would allow the model to casily learn to attend by relative positions, since for any fixed offset m, Pe pe(k+m m.) is linear function of pa(k). It was also hypothesized that it may allow the model to extrapolate to sequence lengths longer than the ones encountered during training.
In many cases, absolute positional encodings have been replaced with relative fully learnable positional encodings and relative partially learnable positional encodings (Dai et al., 2019). To justify these, consider the first atlention layer with absolute positional encodings:
1 = W,,,W FT, + Ea, U. +.W, U.W.W
For relative (fully and partially) learnable positional encodings we have instead:
K. Ard = Ez, W.W.BBB E Ez, W
W.W. R uW K. E uW
where u, RI lixd are lcarnable weights and RØ- e IR 1xd is relative positional encoding between i and j. Each term has the following inluitive meaning: term (1) represents content-based addressing, term (2) captures a content-dependent positional bias, term (3) governs a global content bias, and (4) encodes a global positional bias
For relative fully learnable positional encodings, W W., R is learnable weight in Rdx1 for each i N, while for relative partially learnable positional encodings Ri,- (e((-))) where Pe is the sinusoidal function from before.
We implemented both fully and partially learnable positional encodings for the shortest-path positional encodings (integer-valued)) and related versions for the other positional encodings (in IR.). We include results Tables and 9.
C
Over-squashing
Results for over-squashing experiment can be found in Figure 2.
D Additional Evaluation of Positional Encodings
Here provide start to toy data and task for comparing positional encodings. In this task we wish to assess how powerful the positional encodings are in practice, i.c., 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 encodings become the mere instrument for communicating the connoctivity/tont sanncttivity/ooooogyy /tooology of the original graph. The task among all 100 graphs, i.c., the task is graph classification and there is 100 classes. Hence, achieving 100% accuracy means that the GNN, based on the positional encodings, has been able discriminate between all
retrieve a specific graph
18

---

Published in Transactions on Machine Learning Research (10/2023)
Table 8: Increasing ZINC/ 100K parameters.
type:
trans-adj
Irans-short-cls
r=1
0.338=0.020
0.274=0.021
r=2
0.296=0.010
0.179=0.011
3
0.260
0.183=0.018
r=
0.255=0.009
0.271
r=5
0.235=0.022
0.227=0.026
r=
6
0.226=0.015
0.264=0.042
r=7
7
0.219=0.012
12.0300030
r=8
0.210+0.009
0.278+0.026
r-9
0.213=0.010
0.289#0.042
10
0.564+0.221
0.327=0.023
Table 9: Incrcasing r on CLUSTER 100K parameters.
type: trans-adj-cls
trans-adj
trans-short-cls
trans-short
r=1
74.262+0.188
73.445+0.068
74.717=0.308
72.947=0.125
r=2
77.399#0.200 77.390=0.168
76.771+0.012 76.770=0.094
76.454+0.084
77 77.216+0.226
68.38447.975
76.521=0.250
1
0.9
0.8
0.7
Accuracy
0.6
0.5
0.4
-
r=l
0.3
2
r= 3
0.2
r= 4
0.1
1, CLS
0
2
Tp (problem radius)
Figure NeighborsMatch (Alon and Yahav, 2021). Benchmarking the extent of over-squashing via the problem radius Tp.
19

---

Published in Transactions on Machine Learning Research (10/2023)
Laplacian
0.9
4
Shortest
Adj-5
0.8
Train Accuracy
Adj-10
0.7
0.6
0.5
0.4
0.3
0.2
0.1
-8
0
25
50
75
100
125
150
175 200 225 250
Num. Epochs
Figure 3: Learning to retrieve random Erdos graphs.
graphs. We only look at train accuracy here, since we're interested in the power to overfit, not to generalize. Results be found in Figure
All positional encodings are able to solve that task after sufficient amount of training, besides Adj-10. Adj-5 and Adj-10 10 encode the adjacency matrix to 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 at solving the task. This can be due the fact that the Laplacian positional encoding only unique up to sign and that randomly switch the sign during training.
E Computational Runtime and Memory Use
In our implementation, the slep of computing the positional encodings well as expanding the r-hops of the graph is done in the same process for shortest-path and adjacency positional encodings; thus this step always occur and we found that implementing it via iterative matrix multiplications of the adjacency matrix gave the fastest results. How this scales with the r-size can found in Figure Since each increment of the r-size results an additional matrix multiplication, the linear increase is expected. The spectral positional encoding has the samee additive runtime per graph across r-sizes of 1.3 10-3 seconds. These matrix multiplications are done CPU rather than GPUs, but running them on GPUs could results in speed-ups. However, the runtime for computing these positional encodings is at least order of magnitude smaller (per graph) than the runtime for running the subsequent GNN on GPU, so there was no need to optimize this runtime further.
In Figures 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 CIFAR10 datascts. Note, we are here excluding the computation of the positional encoding on the input graph, which can be found in Figure 4.
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., [E] 2 VV. Since all established GNNs make use of the edges in one way or another, the number edges usually determines the asymptotic behavior the runtime and memory use, i.e., they are E).) With modern deep learning and specialized graph learning framework, GPU-parallelization and other more technical aspect affect memory and runtime. Thus, Figures and 6 compare theoretical runtime (dominated by the density) with actual runtime of code GPUs. We find that density and
20

---

Published in Transactions on Machine Learning Research (10/2023)
11
Arg. time per graph, x10-<
10
Adj. Short, LP
Density
P1
2 3
6
9
10
r-hops
Figure 4: P.E. Computational Time on ZINC/molecules The average densities across graphs for r from 1 through 10 are 14, 27, 440, 52, .2, .71, .79, 88, ,90, and .94.
actual runtime is strongly correlated. In Figure 7 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 investigate the correlation between homophily score (Ma et al., 2021) and perfor- mance when increasing hops size. This applies to the node classification datasets, CLUSTER and PATTERN, that we used. We split the test set into three buckets, which is just sorted segmentation of the graphs with increasing homology scores. We evaluate trained Gated-GCN models with adjacency positional encodings for r-values and (at r almost all graphs are fully connected). See Tables and 11 for results.
We find that high homophily score correlates much stronger with performance when than does 2. This indicates that increased r-size diminishes the reliance homophily inductive bias
Table 10: Inereasing on CLUSTER homophily buckets.
density .31
homophily score:
0.315+0.008
0.336=0.006
0.366+0.0160
71.49440.619
72.361+0.499 77.010+0.234
73.812+0.265
>.99
2
76.660+ 0.143 76.965+0.242
Table 11: Incrcasing on PATTERN homophily buckets.
density
homophily score:
0.567=0.031
0.652=0.026
0.774+0.051
.43
r=1
86.862+0.021 84.197+0.048
83.958
92.154a0.44
>.99
2=2
87.214+ 0.062
87.085+0.0822
G Optimal Positional Encoding and Hops Size
Again, we recommend the adjacency positional encodings together with the CLS-node. We find that in terms of ranked performance on the 6 datasels, adjacency- and spectral positional encodings perform al the same level, but the spectral encoding perform considerably worse on 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 a hyperparameter; we found performance hyperparameter but future work could further investigate this. Spectral embeddings also use less memory
be too sensitive to this
21

---

Published in Transactions on Machine Learning Research (10/2023)
30
Avg. time per epoch
25
20
Laplacian
Shortest
Adj
15
Adj-CLS CL-
Density
2
3
4
6
7
10
r-hops
Figure GNN Computational Time on ZINC/molecules
400
Laplacian
350
Shortest
Avg. Lime per epoch
Adj Adj-CLS
300
Density
250
200
150
100
2
r-hops
Figure 6: GNN Computational Time on CIFAR10
22

---

Published in Transactions on Machine Learning Research (10/2023)
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 Density
1,300
3
6
10
r-hops
Figure 7: GNN Memory use on ZINC/molecules
it does not encode its embeddings edge-features; however, since information still is propagated along edges find this memory saving to be significant but not asymptotically different. Adjacency encoding breaks down faster 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-vectoon and its introducing low-signal information that is also easy to overfit to, c.g., the number of paths of length 10 between two nodes (where any edge can Appendix D support this observation. However, all
used multiple times). The Erdos experiments all, the adjacency encoding stands out slightly considering the performance, runtime, memory use, and toy experiments. Furthermore, the CLS-node is part of the best performing configuration more times than it is not, and it has the additional advantage of leading to peak performance 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 a 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 good r-size but ultimately depends on the amount of compute and memory available.
23


Reviews:
[{"review_id": "Lg39ZTFoC1", "reviewer": "Reviewer_EQcj", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\ni) The survey of related works is comprehensive. \n\nii) The presentation and the illustration of the idea are clear and easy to follow. \n\n**Weakness**\n\ni) The conclusions are straightforward and may not be interesting to the community. \n\nii) The experiments are limited to small graphs and baselines.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies increasing the receptive fields of GNNs by incorporating more neighborhood information during the message passing. Instead of making the original graph as a fully connected graph, the authors propose to construct only the fully connected r-hop graphs, and use positional encoding to make up the lost information. The authors conduct extensive empirical comparison with different r, and demonstrate that relatively small r-hop neighborhoods increase performance across models and that performance degrades in the fully-connected setting.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "Although I appreciate the comprehensive experiments conducted in this paper, I am afraid the results and conclusions might not be interesting, as the main conclusions are already covered by the existing works such as [1,2]. \n\nTo be more specific, when one apply graph transformers, propagating upon the fully connected graphs can bring a lot of overhead, especially for large scale social networks, and lead to OOM issue. To fix the issue, it is natural to reduce the hops and propagate only a relatively small hops. That being said, it’s common practice to test with different hop numbers, and the conclusions drawn from the paper may be too straightforward to be interesting to the community. If my reasoning was incorrect, I hop the authors could better clarify it. \n\n\nAs for experiments, \n- some of the baselines are not compared such as [1,2] and their follow-up works.\n- the scope of the benchmarked datasets seems to be limited. Many of the datasets (such as the OGB datasets) where grap transformers succeeds are not compared. As graph transformers (with fully connected input graphs) can even not obtain improvements in the benchmarked datasets, it’s unconvincing to invalidate the conclusions that fully connected input graphs do not work. \n- as the rewiring techniques are widely used in a broad scope of tasks, it would strengthen the conclusions of the paper if they are also verified in node classification tasks.\n\n\nReferences\n\n[1] Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing, 2019.\n\n[2] Position-aware graph neural networks, 2019.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "61l7sqiFAL", "reviewer": "Reviewer_6u58", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\n1. The introduction and related work sections are quite clearly written and give a good framing of the problem.\n2. I don't think I've seen the idea of running GNNs over a $r$-hop neighborhood to increase expressivity within a computational budget before, especially in combination with positional encodings.\n3. I thought the framing of positional encodings as a way to ensure losslessness / bijectivity was insightful.\n4. The paper includes many experiments and ablations comparing different neighborhood sizes, positional encodings, and base model architectures, which show the tradeoffs between the different hyperparameters in the method they propose.\n\n### Weaknesses\n\n1. The authors incorrectly present this approach as \"state of the art\" (in the conclusion), due to comparing only to baselines from 2020 and 2021. More recent works have outperformed the listed baselines and surpass the proposed method. I'm also not fully convinced that the comparison to the existing baselines is fair, due to sensitivity of the approach to hyperparameters.\n2. The novelty of the positional encodings and graph augmentations are quite limited on their own. Most of the individual components are either taken directly from previous work, or adapted with slight variations. There have also been a number of recent works targeting the same setting which I think should be cited.\n3. Although motivated as a way to reduce computational costs, I'm not convinced it will actually save much in practice. For one, the settings recommended by the authors in section 6 seem to negate the compute savings by making graphs nearly fully connected. Additionally, there are a wide variety of recent alternative approaches for scaling transformer-based graph models beyond $O(n^2)$ complexity which seem empirically stronger.\n4. Section 4 has a few confusing statements and clarity issues.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a technique for increasing the power of existing GNN architectures by augmenting existing graphs with new edges and new features. Specifically, the authors propose adding new edges between any disconnected nodes that are within $r$ hops of each other, then augmenting the nodes and edges with new features (\"positional encodings\") to enable the recovery of the original graph structure. The authors motivate this approach as a way to get some of the benefits of expanded receptive fields (e.g. as you would have when applying a transformer) without the computational cost of a full dense adjacency matrix.\n\nThe particular augmentations the authors consider adding are:\n\n1. Edges are added between any unconnected nodes within an $r$-hop neighborhood, with some constant features.\n2. A new \"CLS\" node is added, connected to every node.\n3. Optionally, node features are extended to also include features based on Laplacian eigenvectors.\n4. Alternatively (presented as an alternative to 3), edge features can be extended with either a scalar measurement of the shortest path between the two nodes in the original graph, or a vector that counts the number of paths of each length between the two nodes (e.g. the terms of powers of the adjacency matrix.)\n\nMost of the individual parts of the proposed approach have been proposed before in other works, but the specific combination and motivation seems slightly different (in that it focuses on using positional encodings *without* global attention, and on giving enough information to rebuild the original graph from the $r$-hop augmented one).", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "### Incorrect \"state of the art\" claims, and potentially unfair evaluation\n\nIn the conclusion the authors claim the proposed approach is \"state of the art\", but according to the PapersWithCode leaderboards ([pattern][], [cluster][], [mnist][], [cifar10][], [zinc][]) their approach is behind the state of the art for most of these datasets. It seems that the baselines the authors are considering are a few years out of date.\n\n[pattern]: https://paperswithcode.com/sota/node-classification-on-pattern\n[cluster]: https://paperswithcode.com/sota/node-classification-on-cluster\n[mnist]: https://paperswithcode.com/sota/graph-classification-on-mnist\n[cifar10]: https://paperswithcode.com/sota/graph-classification-on-cifar10-100k\n[zinc]: https://paperswithcode.com/sota/graph-regression-on-zinc-500k\n\nIt also seems like the presented results were selected by taking the best-performing hyperparameter configuration out of dozens or even hundreds of such configurations (e.g. from table 2), including the base model architecture, the specific positional encoding used, and the value of $r$ used. This doesn't seem like a fair way to summarize the results, especially since the authors make a point that different values of $r$ perform better for different base models and different datasets, and that different positional encodings have different characteristics. It seems to me that it would be better to present the results for hyperparameters chosen via cross-validation or some similar procedure.\n\n### Other relevant related work\nThere are a number of recent related works in this space that I believe the authors should cite, discuss, and (for at least the first two) compare against.\n\n- [Recipe for a general, powerful, scalable graph transformer (Rampášek et al. 2022)](https://proceedings.neurips.cc/paper_files/paper/2022/hash/5d4834a159f1547b267a05a4e2b7cf5e-Abstract-Conference.html) gives a thorough taxonomy of positional encodings, which encompasses most of the specific recommendations for positional encodings made here. (It also proposes an alternative architecture for graph transformers that attains sub-quadratic complexity using existing sub-quadratic attention mechanisms.)\n- [EXPHORMER: Sparse Transformers for Graphs (Shirzad et al. 2023)](https://arxiv.org/abs/2303.06147v2) describes another architecture for sub-quadratic sparse graph transformers, which also adds additional edges to expand receptive fields, and which appears to currently be state-of-the-art for some of the benchmarks the authors consider here.\n- [Pure Transformers are Powerful Graph Learners (Kim et al. 2022)](https://arxiv.org/abs/2207.02505) use a pure transformer architecture \nand model both nodes and edges as \"tokens\", with a modified positional encoding. They also consider using sub-quadratic transformers to attain linear asymptotic complexity.\n\nAlso, somewhat less related (and less important): it might be worth discussing some previous work on hierarchical graph pooling, such as [(Ying et al. 2018)](https://proceedings.neurips.cc/paper_files/paper/2018/file/e77dbaf6759253c7c6d0efc5690369c7-Paper.pdf) or [(Gao and Ji, 2019)](https://proceedings.mlr.press/v97/gao19a/gao19a.pdf). These works also improve information flow, but do so by shrinking the graph rather than by adding new edges.\n\n### Computational considerations\n\nMuch of the proposed approach is motivated by computational savings, but I'm not convinced this approach is likely to be actually faster in practice, for a few reasons:\n\n- Accelerator hardware is frequently optimized for dense operations rather than sparse ones. It seems that routing values along a sparse set of edges could end up being slower than doing dense matrix multiplications in practice, even if the sparse computations technically require fewer floating point operations.\n- The strongest results for the proposed method seem to happen for densities greater than 0.5, and section 6 explicitly recommends setting $r$ so that density is greater than 0.5. But doesn't this mean that the augmented graphs contain more than half of the number of nodes in a fully-connected graph? So it seems like the recommended approach would reduce the computational limitations of a full transformer by less than 50% in practice, even if we ignore sparse/dense computation differences.\n- There are a lot of existing transformer architectures with linear attention variants, and some graph versions of these outperform the proposed method on the benchmarks you present (as discussed above). These seem like they might scale better in practice, especially since they don't seem to require reaching 50% density to get good performance.\n\nSince the approach is motivated from the perspective of computational efficiency, I think these factors deserve more discussion.\n\n### Clarity issues\n\nI found some parts of the paper to be unclear or hard to understand. I would suggest revising them (although many of them are fairly minor):\n\n- Do you consider directed or undirected graphs? Section 3 looks like it encompasses directed graphs but it seems like the rest of your paper mostly talks about undirected ones.\n- I was expecting $R$ to be defined in section 3 with the other definitions, but it looks like it was only defined in section 1. It might be worth defining it again in section 3 so that the definitions are self-contained.\n- 4.2.1 says \"Hence, a sufficient condition for lossless positional encodings is as follows: If all edges in G′ have unique positional encodings, then g ∶ G → G is a bijection.\" This isn't very clear; unique with respect to what?\n  - Clearly it's not enough to just have each edge in G' have a different encoding than each other edge in G', since you could just relabel them to be $1, 2, \\dots, |E|$ but lose all information about the original graph. Do you mean something like \"if the edge features of edges in $G' \\setminus G$ identify them as part of $G' \\setminus G$, and edge features in $G$ identify them as part of $G$\"? That seems to be what is implied by the rest of the paper, but I don't think \"all edges in G′ have unique positional encodings\" is a correct summary of this property.\n  - I also don't understand why this property isn't already satisfied by setting the edge feature of the added edges to $C_e$ as you discuss in 4.1, without reference to any positional encodings. Isn't that already enough to identify all of the added edges?\n- 4.2.2 says \"we note that the diffusion equation for graphs can be written as $u_t = -\\Delta u$; this graph PDE can be solved in closed-form given the eigenvectors and eigenvalues of $\\Delta$. Hence, given the spectral embedding of G in G′, we can simulate diffusion-based multi-hop GNN architectures up to spectral truncation.\" Some of this notation isn't clearly explained:\n  - What is $u$, and what is $u_t$?\n  - Is the proposed $p_v$ the same as \"the spectral embedding of G in G′\", or do you mean something else?\n  - It seems like there's two different approximations happening here, both due to truncating the spectrum and truncating the number of hops. Is that right? If so that might be worth stating more clearly.\n- 4.2.2 also says that the adjacency-powers positional encoding is \"strictly more general than using prescribed diffusion-based aggregation weights on G\". Doesn't that depend on the particular functional form of the model?\n- The tables on page 9 are very dense; it might be worth including some figures as well to make it clearer how performance depends on $r$.\n- The runtime figures in the appendix include a \"density\" line, but this line doesn't appear to have any $y$-axis labels (?)", "broader_impact_concerns": "No broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "0J3Ck2TLxR", "reviewer": "Reviewer_wkJN", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Upon searching \"k-hop GNN\" in Google, I found several similar works, such as:\n\n- Feng, Jiarui, et al. \"How powerful are k-hop message passing graph neural networks.\" Advances in Neural Information Processing Systems 35 (2022): 4776-4790.\n- Nikolentzos, Giannis, George Dasoulas, and Michalis Vazirgiannis. \"k-hop graph neural networks.\" Neural Networks 130 (2020): 195-205.\n\nIt appears that the submission closely resembles these prior works, which have not been cited. If my observation is incorrect, please let me know. Consequently, I am uncertain about the contribution of this work.\n\nAdditionally, the authors briefly mention previous k-hop graph models, such as \"Multi-hop Attention Graph Neural Network\" and \"MixHop Graph Convolution Layer.\" However, these models are not included in the experimental section (e.g., Table 1). Comparing the r-hop GNN with only 1-hop GNN models seems unfair, and I recommend incorporating these models into the evaluation for a more comprehensive comparison.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes to improve the receptive file of graph networks by using r-hop position embeddings. \nHowever, I believe such a simple idea has already been explored by previous works, but it seems the submission ignores them.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "N/A", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: I recommend accepting this paper because (1) it presents sufficient evidence to support its claims and (2) some people might find this paper interesting, even though the work is quite straightforward and incremental.  The TMLR acceptance criteria does not count novelty as an important factor so I have discounted some reviewers' concern regarding novelty.

Other than this I found the discussion on compute saving a bit misleading.  This work really explores a compute-accuracy trade-off, i.e. you can pay a bit of compute cost by using a larger r, and get a bit better performance. It would also be more informative to the readers when presented as a trade-off as it shows a more complete picture.
Decision: Accept (poster)