# Graph Attention with Random Rewiring

Tongzhou Liao
School of Computer Science
Carnegie Mellon University
Pittsburgh, USA &Barnabás Póczos
School of Computer Science
Carnegie Mellon University
Pittsburgh, USA

###### Abstract

Graph Neural Networks (GNNs) have become fundamental in graph-structured deep
learning. Key paradigms of modern GNNs include message passing, graph
rewiring, and Graph Transformers. This paper introduces Graph-Rewiring
Attention with Stochastic Structures (GRASS), a novel GNN architecture that
combines the advantages of these three paradigms. GRASS rewires the input
graph by superimposing a random regular graph, enhancing long-range
information propagation while preserving structural features of the input
graph. It also employs a unique additive attention mechanism tailored for
graph-structured data, providing a graph inductive bias while remaining
computationally efficient. Our empirical evaluations demonstrate that GRASS
achieves state-of-the-art performance on multiple benchmark datasets,
confirming its practical efficacy.

##  1 Introduction

Graph neural networks (GNNs) have emerged as a key innovation in machine
learning for tasks involving complex relational data represented as graphs
[67, 72]. Central to the advancement of GNNs are message passing neural
networks (MPNNs), exemplified by the Graph Convolutional Network (GCN) [39].
By aligning computation with the structure of the graph, MPNNs offer a strong
inductive bias for graph-structured data. However, despite recent advances,
limitations persist in challenges such as underreaching, which occurs when
distant nodes cannot communicate [1], oversmoothing, which occurs when node
representations become indistinguishable [52, 15], and oversquashing, which
occurs when task-relevant information is excessively compressed [7, 64]. Graph
rewiring techniques, aimed at modifying the graph structure to enhance
information flow, have shown promise in overcoming these limitations [2].
However, it comes with the risk of distorting the structure of the graph,
leading to loss or misinterpretation of relational information [20].

Building GNNs with Transformers [65] presents another promising solution to
the above-listed problems. However, many Graph Transformers (GTs) face
scalability challenges as a result of their reliance on quadratic-time
Transformers [56]. This makes their applicability to large graphs
computationally challenging. To address these issues, the General, Powerful,
Scalable (GPS) Graph Transformer [56] combines linear-time Transformers with
MPNNs to offer a method with $O(|V|+|E|)$ time complexity, where $|V|$ denotes
the number of vertices and $|E|$ the number of edges. Exphormer [61], which
generalizes sparse Transformers [76] to graphs, represents another promising
approach. All these architectures, however, inherit their attention mechanisms
from Transformers that are intended for sequences, which are often not optimal
for graph-structured data.

#### Our Contribution.

We aim to design a GNN that encompasses the graph inductive bias offered by
message passing, the improved information flow achieved through graph
rewiring, and the representation power of the attention mechanism. Towards
this end, we propose Graph-Rewiring Attention with Stochastic Structures
(GRASS), a novel GNN inspired by these three paradigms. GRASS rewires the
input graph by superimposing a random regular graph. At each layer, it applies
an attentive node aggregator with attention weights computed from edge
representations, and an MLP edge aggregator that updates edge representations
to reflect node relationships.

We demonstrate 1) the intuitive and empirical effectiveness of combining
random rewiring with message passing, 2) the advantage of a graph-tailored
additive attention mechanism over Transformer-style dot-product attention, and
3) the link between randomly rewired message passing and sparse GTs through
two interpretations of GRASS. In addition, we show that GRASS achieves state-
of-the-art performance on multiple datasets.

In Section 2, we briefly review some related work, highlighting their
strengths and weaknesses. In Section 3, we discuss the design principles,
architecture, and interpretations of GRASS, our novel GNN. We demonstrate the
performance of GRASS in Section 4. We finish the paper with some concluding
remarks in Section 5.

##  2 Related Work

In this section, we briefly summarize some of the prior work related to the
main concepts of GRASS.

#### Graph Rewiring.

Graph rewiring involves the strategic modification of graph structures by
adding, removing, or reallocating edges. Techniques include deterministic
adjustment of the graph structure based on spectral properties [29, 64, 2, 20]
and probabilistic rewiring of the graph based on learned distributions [54].
DRew [32] innovatively introduces layer-dependent rewiring, demonstrating
outstanding performance on tasks that depend on long-range relationships.
While graph rewiring enhances MPNNs by improving graph connectivity, and thus
information propagation, they risk compromising informative structural
properties of graphs, degrading its inductive bias [20].

#### Graph Attention and Graph Transformers.

Graph Attention Network (GAT) [68] and its successors [9, 78, 70, 11] have
leveraged similar attention-based approaches to achieve remarkable results [9,
25]. Despite their success, these MPNNs are intrinsically limited by the
structure of the input graph, leading to persistent challenges such as
underreaching [1], oversmoothing [52, 15], and oversquashing [7, 64]. At a
theoretical level, the expressivity of MPNNs is often no more powerful than
the Weisfeiler-Lehman graph isomorphism test [73, 60, 41].

Graph Transformers [75, 22, 40, 74, 48, 36] employ the Transformer
architecture [65] to transcend these limitations of MPNNs. Instead of relying
on message passing within neighborhoods of the input graph, GTs facilitate
simultaneous attention between all nodes, unrestricted by the structure of the
graph. However, its $O(|V|^{2})$ time complexity becomes prohibitive for large
graphs. Linear and sparse Transformers, exemplified by Performer [18] and
BigBird [76], respectively, achieve linear runtime with respect to the number
of tokens. However, integrating a graph inductive bias into these Transformers
can be challenging, since they are designed for Euclidean data [47].

The General, Powerful, Scalable (GPS) Graph Transformer [56] represents a
hybrid approach, merging MPNNs’ inductive bias with the global perspective of
Linear-Time Transformers. Exphormer [61] presents a natural generalization of
BigBird to graphs by incorporating local, global, and random attention. It
employs random regular expander graphs as an alternative to BigBird’s random
attention patterns on sequential data, and is analogous to the random rewiring
mechanism of GRASS. However, these models, along with prior GTs, focus on
adapting Transformer-style dot-product attention to graph-structured data,
rather than investigating graph-specialized alternatives. Their performance
does not exceed that of more tailored attention mechanisms, such as GRIT [47],
on a variety of tasks.

#### Graph Encoding.

By integrating structural information directly into nodes and edges, graph
encoding significantly improves the expressivity of GNNs, especially for GTs
[25]. Techniques such as graph Laplacian positional encoding (LapPE) [25] and
random walk structural encoding (RWSE) [23] have been instrumental in this
regard. The Graph Inductive Bias Transformer (GRIT) [47] introduces a novel
encoding strategy—relative random walk probabilities (RRWP)—which is
particularly powerful in capturing structural properties [47]. However, like
its GT predecessors, GRIT suffers from $O(|V|^{2})$ complexity, limiting its
applicability to large graphs.

In summary, while existing methodologies have significantly advanced the field
of graph neural networks, they are often constrained by limited expressivity
within the MPNN framework, computational inefficiencies, or challenges in
incorporating a graph inductive bias. GRASS emerges as a novel solution that
addresses these challenges through the combination of random rewiring and a
graph-tailored attention mechanism, offering a competitive solution to graph-
structured learning.

##  3 Methods

In this section, we introduce the design of GRASS. We begin by examining the
desirable qualities of a GNN, which guide our architectural design.
Subsequently, we introduce the components of GRASS by following the order of
data processing in our model, and also describe the role of each component.

#### Design Goals.

We center our design around what we consider to be the key characteristics of
an effective GNN. We will focus on the processing of nodes (N1–N3) and edges
(E1–E2), as well as the scalability (S1) of the proposed model.

  1. N1.

Permutation Equivariance. Unlike tokens in a sentence or pixels in an image,
nodes in a graph are unordered, and therefore the model should be permutation
equivariant by construction. Since reordering the nodes of a graph does not
change the graph, permuting the nodes of the input graph of a GNN layer should
only result in the same permutation of its output [67]. Formally, let
$f(\mathbf{X},\mathbf{E},\mathbf{A})$ be the function computed by a layer,
where $\mathbf{X}:\mathbb{R}^{|V|\times n_{\text{node}}}$ represents node
features with $n_{\text{node}}$ dimensions,
$\mathbf{E}:\mathbb{R}^{|V|\times|V|\times n_{\text{edge}}}$ represents edge
features with $n_{\text{edge}}$ dimensions, and
$\mathbf{A}:\\{0,1\\}^{|V|\times|V|}$ represents the adjacency matrix (edge
weights are considered scalar-valued edge features). If the layer is
permutation equivariant and
$(\mathbf{X}_{\text{out}},\mathbf{E}_{\text{out}})=f(\mathbf{X}_{\text{in}},\mathbf{E}_{\text{in}},\mathbf{A})$,
then
$(\mathbf{PX}_{\text{out}},\mathbf{PE}_{\text{out}}\mathbf{P}^{\top})=f(\mathbf{PX}_{\text{in}},\mathbf{PE}_{\text{in}}\mathbf{P}^{\top},\mathbf{PAP}^{\top})$
for an arbitrary permutation matrix $\mathbf{P}$.

  2. N2.

Effective Communication – The model should facilitate long-range communication
between nodes. Numerous real-world tasks require the GNN to capture
interactions between distant nodes [24]. However, MPNN layers, which propagate
information locally, frequently fail in this regard [47]. A major challenge is
underreaching, where an MPNN with $l$ layers is incapable of supporting
communication between two nodes $x_{i},x_{j}$ with distance
$\delta(x_{i},x_{j})>l$ [1]. Another challenge is oversquashing, where the
structure of the graph forces information from a large set of nodes to squeeze
through a small set of nodes to reach its target [64]. A node with a constant-
size feature vector may need to relay information from exponentially many
nodes (with respect to model depth), leading to excessive compression of
messages in deep MPNNs [1]. Addressing these issues is crucial for effectively
capturing long-distance relationships.

  3. N3.

Selective Aggregation – The model should only aggregate information from
relevant nodes and edges. MPNN layers commonly update node representations by
unconditionally summing or averaging messages from neighboring nodes and edges
[67]. In deep models, this can lead to oversmoothing, where the representation
of nodes from different classes becomes too similar in the process of repeated
aggregation [15]. MPNN like GCN [39] have been shown to behave as low-pass
filters in feature vectors [52]. To address this issue, nodes should only
aggregate information from relevant neighbors, instead of doing so
unconditionally, in order to maintain distinguishability of node
representations when required by the task.

  4. E1.

Relationship Representation – The model should effectively represent the
relationships between nodes with edges. Edges in graph-structured data often
convey meaningful information about the relationship between the nodes it
connects [30]. However, many contemporary GNNs do not use edge features [33,
73, 48], only support scalar-valued edge features (edge weights) [39, 21], or
never update edge features across layers [74, 61]. In addition to the semantic
relationship represented by edge features of the input graph, structural
relationship can be represented by edge encodings added by the model [56]. To
inform the model about the relationship between nodes, edge representations
should incorporate information from both edge features and edge encodings, and
be meaningfully utilized by layers.

  5. E2.

Directionality Preservation – The model should preserve and utilize
information carried by edge directions. Many graphs representing real-world
relationships are inherently directed [58]. Although edge directionality has
been shown to carry important information for various tasks, many GNN variants
require undirected graphs as input, to prevent edge directions from
restricting information flow [58]. It would be beneficial for the model’s
expressivity if edge directionality information could be preserved without
severely limiting communication.

  6. S1.

Efficient Computation – The model should have $O(|V|+|E|)$ time complexity for
its non-precomputable operations. The number of edges $|E|$ in a connected
directed graph with $|V|$ vertices may vary from $|V|$ to $|V|(|V|-1)$.
However, in practical scenarios, the number of edges typically falls somewhere
between these extremes. GNNs with $O(|V|)$ complexity can be incapable of
processing every edge, while those with $O(|V|^{2})$ complexity struggle to
scale to large-and-sparse graphs where $|E|\in O(|V|)$. Meanwhile, a model
with $O(|V|+|E|)$ complexity can be efficient on both dense and sparse graphs.
While this is tempting, we notice that computing certain graph properties,
such as detecting triangles [71] and finding unweighted all-pair shortest
paths [14], cannot be done in $O(|V|+|E|)$ time, which prohibits a model with
$O(|V|+|E|)$ time complexity from completing tasks that require these
properties. As a compromise, we allow the model to preprocess data without
this restriction to capture critical structural properties, as long as the
model’s non-precomputable steps remain $O(|V|+|E|)$ time. Precomputable
operations only need to be performed once per dataset, regardless of the
number of training sessions and epochs, thereby reducing their impact on
overall efficiency.

#### The Structure of GRASS.

The high-level structure of GRASS is illustrated in Figure 2. Prior to
training, GRASS precomputes the degree matrix and random walk probabilities of
each graph in the dataset. At each training iteration, GRASS randomly rewires
the input graph, applies node and edge encodings, and passes the graph through
multiple attention layers, producing an output graph with the same structure.
For tasks that require a graph-level representation, such as graph regression
and graph classification, pooling is performed on the output graph to obtain a
single output vector.

###  3.1 Graph Encoding

Extracting structural information plays an important role in graph-structured
learning and is crucial for Relationship Representation. To this end, GRASS
applies relative random walk probabilities (RRWP) encoding [47] and degree
encoding [74] to represent structural relationships.

#### RRWP Encoding.

RRWP encoding has been shown to be very expressive both theoretically and
practically [47], serving as a major source of structural information for the
model. To calculate random walk probabilities, we first obtain the transition
matrix $\mathbf{T}$, where $\mathbf{T}_{i,j}$ represents the probability of
moving from node $i$ to node $j$ in a random walk step. It is defined as
$\mathbf{T}=\mathbf{D}^{-1}\mathbf{A}:[0,1]^{|V|\times|V|}$, where
$\mathbf{A}\in\\{0,1\\}^{|V|\times|V|}$ is the adjacency matrix of the input
graph $G$, and $\mathbf{D}\in\mathbb{N}^{|V|\times|V|}$ is its degree matrix.
The powers of $\mathbf{T}$ are stacked to form the RRWP tensor $\mathbf{P}$,
with $\mathbf{P}_{h,i,j}$ representing the probability that a random walker
who starts at node $i$ lands at node $j$ at the $h$-th step. Formally,
$\mathbf{P}=[\mathbf{T},\mathbf{T}^{2},...,\mathbf{T}^{k}]:[0,1]^{k\times|V|\times|V|}$,
where $k$ is the number of random walk steps. The diagonal elements
$\mathbf{P}_{:,i,i}$ where $i\in V_{G}$ are used as node encodings, similarly
to RWSE [23]. The rest are used as edge encodings when the corresponding edge
is present in the rewired graph $H$. All node encodings undergo Batch
Normalization (BN) [37] to improve their distribution, while batch noise also
acts as a regularizer that increases the model’s resistance to noise in the
random walk probabilities produced by structural noise in the input graph.
Here, $n$ denotes the dimensionality of hidden layers.

$\displaystyle\mathbf{x}_{i}^{\text{RW}}$
$\displaystyle=\mathbf{W}_{\text{node-
enc}}\text{BN}(\mathbf{P}_{:,i,i}):\mathbb{R}^{n}$ (1)
$\displaystyle\mathbf{e}_{i,j}^{\text{RW}}$
$\displaystyle=\mathbf{W}_{\text{edge-
enc}}\text{BN}(\mathbf{P}_{:,i,j}):\mathbb{R}^{n}$ (2)

As required by Efficient Computation, operations slower than $O(|V|+|E|)$ time
must be precomputable. $\mathbf{P}$ only needs to be computed once per dataset
because it depends only on the adjacency matrix $\mathbf{A}$ of the input
graph. To further improve performance through pipelining, the CPU looks up
$\mathbf{P}_{:,i,i}$ for each $i\in|V_{G}|$ and $\mathbf{P}_{:,i,j}$ for each
edge $(i,j)\in E_{G}$ to hide latency and conserve VRAM.

#### Degree Encoding.

Degree encoding is another simple yet powerful way to represent structural
information [74]. For datasets in which node degrees can take a small number
of values, the model could learn a degree embedding tensor
$\mathbf{E}:\mathbb{R}^{D^{+}\times D^{-}\times n}$, where $D^{+}$ and $D^{-}$
denote the maximum out- and in-degree of the dataset, while $\text{d}^{+}(i)$
and $\text{d}^{-}(i)$ represent the out- and in-degree of node $i$.

$\mathbf{x}_{i}^{\text{deg}}=\mathbf{E}_{\text{d}^{+}(i),\text{d}^{-}(i),:}:\mathbb{R}^{n}$
(3)

For datasets in which degrees can take a large number of values, it could be
more efficient to learn degree encodings with a linear layer
$\mathbf{W}_{\text{deg}}$, at the cost of expressivity. Here, $\|$ denotes
concatenation.

$\mathbf{x}_{i}^{\text{deg}}=\mathbf{W}_{\text{deg}}\text{BN}(\text{d}^{+}(i)\,\|\,\text{d}^{-}(i)):\mathbb{R}^{n}$
(4)

#### Applying Encodings.

Before entering attention layers, RRWP encodings are added to both node
features and edge features (including those of edges added by random
rewiring), while degree encodings are only added to node features.

$\displaystyle\mathbf{x}_{i}^{0}$
$\displaystyle=\mathbf{x}^{\text{in}}_{i}+\mathbf{x}^{\text{RW}}_{i}+\mathbf{x}^{\text{deg}}_{i}:\mathbb{R}^{n}$
(5) $\displaystyle\mathbf{e}_{i,j}^{0}$
$\displaystyle=\mathbf{e}^{\text{in}}_{i,j}+\mathbf{e}^{\text{RW}}_{i,j}:\mathbb{R}^{n}$
(6)

###  3.2 Random Rewiring

To address the issues of underreaching and oversquashing for Effective
Communication, GRASS rewires the input graph by superimposing a random regular
graph. While deterministic rewiring and non-regular graphs may also improve
connectivity, we present potential advantages of using random regular graphs.
We also provide details on random regular graph generation and input graph
rewiring.

#### Effects on Diameter.

The diameter of a graph upper-bounds the distance between two nodes, and thus
the number of layers for an MPNN to propagate information between them [1].
Superimposing a random regular graph onto the input graph can drastically
decrease its diameter. The least integer $d$ that satisfies
$(r-1)^{d-1}\geq(2+\varepsilon)r|V|\log|V|$ is the upper bound of the diameter
of almost every random $r$-regular graph with $|V|$ nodes, where $r\geq 3$ and
$\varepsilon>0$ [8]. Since adding edges to a graph never increases its
diameter, the diameter $d$ of the rewired graph is asymptotically upper-
bounded by $d\in O(\log_{r}|V|)$ when $r\geq 3$. Subsequently, all nodes would
be able to communicate with each other given $O(\log_{r}|V|)$ message passing
layers, which could significantly reduce the risk of underreaching on large
graphs. In addition, the diameter of a graph is a trivial upper bound of its
effective resistance [26], which has been shown to be positively associated
with oversquashing [7]. Intuitively, it upper bounds the “length” of the
bottleneck through which messages are passed.

#### Effects on Internally Disjoint Paths.

Since oversquashing can be attributed to squeezing too many messages through
the fixed-size feature vector of a node [1], increasing the number of
internally disjoint paths between two nodes may reduce oversquashing by
allowing information to propagate through more nodes in parallel. Intuitively,
it increases the “width” of the bottleneck. A random $r$-regular graph with
$r\geq 2$ almost certainly has a vertex connectivity of $r$ as
$|V|\rightarrow\infty$ [27]. Menger’s Theorem then lower-bounds the number of
internally disjoint paths by a graph’s vertex connectivity [31]. This provides
another perspective on how the random regular graph may reduce oversquashing.

#### Effects on Spectral Gap.

Oversquashing has been shown to decrease as the spectral gap of a graph
increases, which is defined as $\lambda_{1}$, the smallest positive eigenvalue
of the graph’s Laplacian matrix [38]. It has been proven that a random
$r$-regular graph sampled uniformly from the set of all $r$-regular graphs
with $|V|$ nodes almost certainly has $\mu<2\sqrt{r-1}+1$ as
$|V|\rightarrow\infty$, where $\mu$ is the largest absolute value of
nontrivial eigenvalues of its adjacency matrix [53]. Since the graph is
$r$-regular, its $i$-th adjacency matrix eigenvalue $\mu_{i}$ and $i$-th
Laplacian matrix eigenvalue $\lambda_{i}$ satisfy $\lambda_{i}=r-\mu_{i}$
[46], lower-bounding the spectral gap with $\lambda_{1}>r-2\sqrt{r-1}-1$.
Therefore, the superimposed random regular graph may alleviate oversquashing
by increasing the spectral gap of the rewired graph.

#### Generating Random Regular Graphs.

We generate random regular graphs with the Permutation Model [53] that we
describe here and with pseudocode in Appendix A. For a given positive and even
parameter $r\geq 2$, and for the input graph $G=(V_{G},E_{G})$, we randomly
generate a corresponding $r$-regular graph by independently and uniformly
sampling $\frac{r}{2}$ random permutations
$\sigma_{1},\sigma_{2},...,\sigma_{\frac{r}{2}}$ from $S_{|V_{G}|}$, the
symmetric group defined over the nodes of the graph $G$. Using these random
permutations, we construct a random pseudograph
$\tilde{R}=(V_{G},E_{\tilde{R}})$, where the edge set $E_{\tilde{R}}$ of the
graph $\tilde{R}$ is

$E_{\tilde{R}}=\bigsqcup_{i\in
V_{G},j\in[\frac{r}{2}]}\\{\\{i,\sigma_{j}(i)\\}\\}$ (7)

Here, $\sqcup$ denotes the disjoint union of sets. The resulting graph
$\tilde{R}$ is a random regular pseudograph, and the probability that
$\tilde{R}$ is any regular pseudograph with $|V_{G}|$ nodes and degree $r$ is
equal [8]. Being a pseudograph, $\tilde{R}$ might not be simple: it might
contain self-loops and multi-edges. Even when $|V_{G}|$ is large, the
probability that $\tilde{R}$ is simple—that it does not contain self-loops or
multi-edges—would not be prohibitively small. In particular, it has an
asymptotically tight lower bound [8]:

$\lim_{|V_{G}|\rightarrow\infty}\text{Pr}[\tilde{R}\text{ is
simple}]=e^{-\frac{r^{2}}{2}-r}$ (8)

Therefore, if we re-generate $\tilde{R}$ when it’s not simple, the expected
number of trials required for us to obtain a simple $\tilde{R}$ is upper-
bounded by $e^{\frac{r^{2}}{2}+r}$, which can be kept low by keeping $r$ low.
In practice, GRASS would like the superimposed graph to be simple, in order to
avoid unwanted redundancy in the attention mechanism. In particular, self-
loops result in a duplicate path of message passing from a node to itself,
while multi-edges result in multiple identical messages. Meanwhile, the
regularity of the graph is desired but not strictly required. Therefore, when
$\tilde{R}$ is not simple, we simply remove self-loops and multi-edges from
$\tilde{R}$ to obtain $R$, which is always simple but not necessarily regular.

#### Rewiring the Input Graph.

Figure 1: Visualization of the proposed random rewiring mechanism. Solid lines
denote existing edges of the input graph, and dashed lines denote added edges.
(a) The input graph $G$. (b, c) Two among all possible instances of the
randomly rewired graph $H$ with $r=2$.

To rewire the input graph $G$, GRASS superimposes the edges of $R$ onto $G$,
producing a new graph $H=(V_{G},E_{G}\sqcup E_{R})$ that is used as input for
subsequent stages of the model. Since it is possible that $E_{G}\cap
E_{R}\neq\emptyset$, there might be multi-edges in $H$, and in these cases,
$H$ is not a simple graph. GRASS does not remove these multi-edges to avoid
biasing the distribution of the superimposed random regular graph.

The added edges $E_{R}$ are given a distinct embedding to make them
distinguishable from the existing edges $E_{G}$. This aids Selective
Aggregation, as it enables a node to select between its neighbors and a random
node. Edge encodings are also given to the added edges, which are instrumental
in Relationship Representation. Although an added edge $(i,j)\in E_{R}$ lacks
edge features that represent semantic relationships in the input graph, the
structural relationship between nodes $i$ and $j$ is represented by the random
walk probabilities $\mathbf{P}_{:,i,j}$ given to that edge as its RRWP
encoding.

###  3.3 Attention Mechanism

Many GTs emulate the structure of Transformers designed for Euclidean data
[22, 40, 74, 36, 61]. Meanwhile, GRASS uses attentive node aggregators with
attention scores computed by MLP edge aggregators, which is a more tailored
attention mechanism for graph-structured data. Figure 3 illustrates its
structure in detail. The proposed attention mechanism is unique in the way it
uses edge representations as the medium of attention weights. To satisfy the
needs of Relationship Representation, edge representations must be updated
alongside node representations. Unlike a node, whose neighborhood is a set of
nodes, a directed edge always has one head and one tail which is an ordered
pair. An undirected edge can be represented by two directed edges with
opposite directions, which allows us to generalize this observation to
undirected graphs. With an ordered input, an edge can use an MLP as its
aggregator, offering better expressivity by MLP’s universal approximation [35]
while preserving Permutation Equivariance. Assuming Relationship
Representation is satisfied, edge features would already represent node
relationships, which we can use as attention weights $\mathbf{a}_{i,j}$ after
applying a linear layer and taking element-wise softmax [10] to obtain a
probability distribution.

The proposed attention mechanism is defined as follows, where $\odot$ denotes
the Hadamard product, $\hat{\text{d}}^{-}$ denotes in-degree after random
rewiring, and $\mathcal{N}^{-}$ denotes in-neighbors.

$\displaystyle\mathbf{s}_{i,j}^{l}$
$\displaystyle=\text{dropout}\left(\hat{\text{d}}^{-}(j)\exp(\mathbf{W}^{l}_{\text{attn}\leftarrow\text{edge}}\mathbf{e}_{i,j}^{l-1})\right):{\mathbb{R}^{+}}^{n}$
(9) $\displaystyle\mathbf{a}_{i,j}^{l}$
$\displaystyle=\frac{\mathbf{s}_{h,j}^{l}}{\sum_{h\in\mathcal{N}^{-}(j)}\mathbf{s}_{h,j}^{l}+\varepsilon}:{\mathbb{R}^{+}}^{n}$
(10) $\displaystyle\tilde{\mathbf{x}}_{j}^{l}$
$\displaystyle=\mathbf{W}^{l}_{\text{tail}\leftarrow\text{tail}}\mathbf{x}_{j}^{l-1}+\sum_{i\in\mathcal{N}^{-}(j)}\mathbf{a}_{i,j}^{l}\odot\mathbf{(}\mathbf{W}^{l}_{\text{tail}\leftarrow\text{head}}\mathbf{x}_{i}^{l-1}+\mathbf{W}^{l}_{\text{tail}\leftarrow\text{edge}}\mathbf{e}_{i,j}^{l-1}):\mathbb{R}^{n}$
(11) $\displaystyle\tilde{\mathbf{e}}_{i,j}^{l}$
$\displaystyle=\mathbf{W}^{l}_{\text{edge}\leftarrow\text{edge}}\mathbf{e}_{i,j}^{l-1}+\mathbf{W}^{l}_{\text{edge}\leftarrow\text{head}}\mathbf{x}_{i}^{l-1}+\mathbf{W}^{l}_{\text{edge}\leftarrow\text{tail}}\mathbf{x}_{j}^{l-1}:\mathbb{R}^{n}$
(12)

In calculating attention weights, GRASS scales the input to the softmax
operation by the logarithm of the number of keys at each node, which is equal
to the in-degree of that node after random rewiring. This has been shown to
reduce the impact of the number of keys on the entropy of the distribution of
attention weights when there is a large number of keys [17], which supports
Selective Aggregation. Intuitively, this allows a node to concentrate its
attention weight on relevant in-neighbors regardless of the number of in-
neighbors it has. Since the number of keys a node attends to is equal to its
in-degree, this approach is also analogous to degree scaling [19], which is
widely used in MPNNs to incorporate degree information into message passing.

In addition, GRASS uses DropKey [42] as a regularizer, which, in the context
of graph attention, is effective in reducing its dependence on the presence of
particular edges in the graph. This improves the robustness of GRASS against
structural noise and thus facilitates Selective Aggregation. DropKey can be
seen as the random removal of edges because it randomly masks the attention
matrix prior to the softmax operation. Thus, it elegantly complements random
rewiring, which only adds edges. This equivalence could not be established for
Attention Dropout [77] despite its popularity in Transformers.

Like Transformers, the output of the attention mechanism is passed through an
FFN. Here, $\phi$ denotes a ReLU-like [50, 55, 49] nonlinear activation
function.

$\displaystyle\hat{\mathbf{x}}_{i}^{l}$
$\displaystyle=\mathbf{W}^{l}_{\text{node-
out}}\phi(\tilde{\mathbf{x}}_{i}^{l}+\mathbf{b}^{l}_{\text{node-
act}})+\mathbf{b}^{l}_{\text{node-out}}:\mathbb{R}^{n}$ (13)
$\displaystyle\hat{\mathbf{e}}_{j,i}^{l}$
$\displaystyle=\mathbf{W}^{l}_{\text{edge-
out}}\phi(\tilde{\mathbf{e}}_{i,j}^{l}+\mathbf{b}^{l}_{\text{edge-
act}})+\mathbf{b}^{l}_{\text{edge-out}}:\mathbb{R}^{n}$ (14)

#### Normalization and Residual Connection.

PN-V is a variant of Power Normalization [59], which normalizes the root mean
square of the batch and is more stable than BN on large-variance inputs. BN
has been shown to work poorly in GNNs [13], which would be made worse by the
variance introduced with random rewiring. PN-V is used by GRASS to address
this problem, allowing it to achieve adequate stability during training while
still enjoying normalized batch distributions [59].

The residual connection [34] is scaled by $\alpha$, a coefficient calculated
according to DeepNorm [69], which stabilizes the training of deep residual
networks. This allows us to use post-normalization, which has been shown to
increase expressivity while avoiding the problem of exploding model update
[45, 69]. This is essential for us to validate the robustness of GRASS against
oversquashing and oversmoothing, which deep GNNs are more vulnerable to, by
allowing us to train a deeper model.

$\displaystyle\mathbf{x}_{i}^{l}$
$\displaystyle=\text{PN-V}(\mathbf{x}_{i}^{l-1}+\alpha\hat{\mathbf{x}}_{i}^{l}):\mathbb{R}^{n}$
(15) $\displaystyle\mathbf{e}_{i,j}^{l}$
$\displaystyle=\text{PN-V}(\mathbf{e}_{i,j}^{l-1}+\alpha\hat{\mathbf{e}}_{j,i}^{l}):\mathbb{R}^{n}$
(16)

#### Edge Flipping.

While the proposed attention mechanism naturally achieves Directionality
Preservation by aggregating information in the same direction as edges, it can
severely restrict the flow of information, putting it in conflict with
Effective Communication. As a solution, the direction of each edge is switched
from one layer to the next: in odd-numbered layers, the directions match those
of the edges in the rewired graph $H$, whereas in even-numbered layers, they
are reversed. This enables the model to propagate information in both
directions even when the input graph is directed, improving its expressivity
[58]. We empirically find edge flipping to be beneficial on undirected graphs
(where an undirected edge is represented as a pair of directed edges with
opposite directions) as well.

#### Graph Pooling.

For graph-level tasks, graph pooling is required at the output of a GNN to
produce a vector representation of each graph, capturing task-relevant global
properties [72]. GRASS employs sum pooling, a simple pooling method as
powerful as the Weisfeiler-Lehman test, while many more complicated methods
are not [4]. Considering the randomness of the added edges, they are pooled
separately from the preexisting edges in the input graph $G$, because the
pooled output of the randomly added edges may exhibit a different distribution
than that of the preexisting edges. Here, $\|$ denotes concatenation.

$\mathbf{y}=\;\sum_{i\in V_{G}}\mathbf{x}_{i}^{L}\;\left\|\;\sum_{(i,j)\in
E_{G}}\mathbf{e}_{i,j}^{L}\right.\;\left\|\;\sum_{(i,j)\in
E_{R}}\mathbf{e}_{i,j}^{L}\right.\;:\mathbb{R}^{3n}$ (17)

###  3.4 Interpretations of GRASS

#### A Message Passing Perspective.

GRASS is an MPNN on a noisy graph. In an MPNN, information is propagated along
the edges of the input graph, defined by its adjacency matrix [67]. GRASS can
be seen as an MPNN that injects additive and multiplicative noise into the
adjacency matrix, through random rewiring and DropKey, respectively. The
adjacency matrix $\mathbf{A}_{M}$ followed by message passing is given by

$\mathbf{A}_{M}=(\mathbf{A}_{G}+\mathbf{A}_{R})\cdot\mathbf{A}_{D}$ (18)

where $\mathbf{A}_{G}$ is the adjacency matrix of the input graph $G$,
$\mathbf{A}_{R}$ is that of the superimposed random regular graph $R$,
$\mathbf{A}_{D}$ is a random attention mask sampled by DropKey (which can also
be seen as the adjacency matrix of a random graph), $+$ denotes element-wise
OR, and $\cdot$ denotes element-wise AND.

Noise injection is well known as an effective regularizer [51], and for graph-
structured data, the random removal of edges has demonstrated regularization
effects [57]. By adding noise to the adjacency matrix that guides the
propagation of information in message passing, GRASS is encouraged to develop
robustness against structural noise, which is prevalent in graph-structured
data [66].

#### A Graph Transformer Perspective.

GRASS is a sparse Graph Transformer. Graph Transformers allow each node to
aggregate information from other nodes through graph attention mechanisms,
with a general definition [67] being

$\mathbf{x}^{\prime}_{j}=\phi\left(\mathbf{x}_{j},\bigoplus_{i\in\mathcal{N}(j)}a(\mathbf{x}_{i},\mathbf{x}_{j})\psi(\mathbf{x}_{i})\right)$
(19)

where $\phi$ and $\psi$ are neural networks, $a$ is an attention weight
function, and $\bigoplus$ is a permutation-invariant aggregator. Many GTs
compute attention weights using scaled dot-product attention [65], with node
features as keys and queries. However, we observe that edge features in GRASS,
which are updated by aggregating information from its head and tail nodes with
an MLP, could be used to directly compute attention weights as a form of
additive attention [5]. Relationship Representation would then be critical for
the attention weights to be meaningful, which GRASS satisfies through
expressive edge encodings and the deep processing of edge features.

Many GTs achieve sparsity by integrating [56] or generalizing [61] BigBird’s
sparse dot-product attention. Meanwhile, GRASS achieves sparsity in a graph-
native way: attention is always local, so nonadjacent nodes in the rewired
graph would naturally never attend to each other. Seeing GRASS as a
Transformer, its attention mask would be $\mathbf{A}_{M}$ as defined in
Equation 18. Moreover, there might be little computational benefit in using
sparse dot-product attention on graphs-structured data, since its efficient
implementation relies on efficient sparse matrix multiplication [76], which is
challenging [28, 12] due to the lack of exploitable sparsity patterns in many
real-world graphs.

##  4 Experiments

#### Benchmarking GRASS.

To measure the performance of GRASS, we train and evaluate it on five of the
GNN Benchmark Datasets [25]: ZINC, MNIST, CIFAR10, CLUSTER, and PATTERN, as
well as three of the Long Range Graph Benchmark (LRGB) [24] datasets:
Peptides-func, Peptides-struct, and PascalVOC-SP. Following the experimental
setup of Rampášek et al. [56], we configure GRASS to around 100k parameters
for MNIST and CIFAR10, and 500k parameters for all other datasets. Additional
information on the datasets can be found in Appendix D. In all experiments, we
use the Lion optimizer [16] and the 1cycle learning rate schedule [62].

As shown in Tables 1 and 2, GRASS ranks first in ZINC, MNIST, CIFAR, PATTERN,
Peptides-struct, and PascalVOC-SP, while ranking second in CLUSTER. Notably,
GRASS achieves 21.9% lower MAE in ZINC compared to GRIT, the second-best model
on the dataset, which has $O(|V|^{2})$ runtime.

Table 1: Performance on GNN Benchmark Datasets. The performance of GRASS shown
here is the mean $\pm$ s.d. of 8 runs on ZINC, and 6 runs on other datasets.
The best and second-best results are highlighted. Performance numbers other
than that of GRASS are adapted from Ma et al. [47] and Shirzad et al. [61].

Model ZINC MNIST CIFAR10 PATTERN CLUSTER MAE $\downarrow$ Accuracy $\uparrow$
Accuracy $\uparrow$ Accuracy $\uparrow$ Accuracy $\uparrow$ GCN 0.367 $\pm$
0.011 90.705 $\pm$ 0.218 55.710 $\pm$ 0.381 71.892 $\pm$ 0.334 68.498 $\pm$
0.976 GIN 0.526 $\pm$ 0.051 96.485 $\pm$ 0.252 55.255 $\pm$ 1.527 85.387 $\pm$
0.136 64.716 $\pm$ 1.553 GAT 0.384 $\pm$ 0.007 95.535 $\pm$ 0.205 64.223 $\pm$
0.455 78.271 $\pm$ 0.186 70.587 $\pm$ 0.447 GatedGCN 0.282 $\pm$ 0.015 97.340
$\pm$ 0.143 67.312 $\pm$ 0.311 85.568 $\pm$ 0.088 73.840 $\pm$ 0.326 GatedGCN-
LSPE 0.090 $\pm$ 0.001 - - - - PNA 0.188 $\pm$ 0.004 97.94 $\pm$ 0.12 70.35
$\pm$ 0.63 - - DGN 0.168 $\pm$ 0.003 - 72.838 $\pm$ 0.417 86.680 $\pm$ 0.034 -
GSN 0.101 $\pm$ 0.010 - - - - CIN 0.079 $\pm$ 0.006 - - - - CRaW1 0.085 $\pm$
0.004 97.944 $\pm$ 0.050 69.013 $\pm$ 0.259 - - GIN-AK+ 0.080 $\pm$ 0.001 -
72.19 $\pm$ 0.13 86.850 $\pm$ 0.057 - SAN 0.139 $\pm$ 0.006 - - - 76.691 $\pm$
0.65 Graphormer 0.122 $\pm$ 0.006 - - - - K-Subgraph SAT 0.094 $\pm$ 0.008 - -
86.848 $\pm$ 0.037 77.856 $\pm$ 0.104 EGT 0.108 $\pm$ 0.009 98.173 $\pm$ 0.087
68.702 $\pm$ 0.409 86.821 $\pm$ 0.020 79.232 $\pm$ 0.348 Graphormer-URPE 0.086
$\pm$ 0.007 - - - - Graphormer-GD 0.081 $\pm$ 0.009 - - - - GPS 0.070 $\pm$
0.004 - 72.298 $\pm$ 0.356 86.685 $\pm$ 0.059 78.016 $\pm$ 0.180 Exphormer -
98.55 $\pm$ 0.039 74.69 $\pm$ 0.125 86.74 $\pm$ 0.015 78.07 $\pm$ 0.037 GRIT
0.059 $\pm$ 0.002 98.108 $\pm$ 0.111 76.468 $\pm$ 0.881 87.196 $\pm$ 0.076
80.026 $\pm$ 0.277 GRASS (ours) 0.046 $\pm$ 0.001 98.905 $\pm$ 0.034 82.471
$\pm$ 0.319 90.997 $\pm$ 0.225 79.347 $\pm$ 0.087

Table 2: Performance on LRGB datasets. The performance of GRASS shown here is
the mean $\pm$ s.d. of 8 runs. The best and second-best results are
highlighted. Performance numbers other than that of GRASS are adapted from
Gutteridge et al. [32], Tönshoff et al. [63], Ma et al. [47], and Shirzad et
al. [61]. *Tönshoff et al. [63] has improved the performance of these models
via hyperparameter tuning.

Model Peptides-func Peptides-struct PascalVOC-SP AP $\uparrow$ MAE
$\downarrow$ Macro F1 $\uparrow$ GCN* 0.6860 $\pm$ 0.0050 0.2460 $\pm$ 0.0007
0.2078 $\pm$ 0.0031 GINE* 0.6621 $\pm$ 0.0067 0.2473 $\pm$ 0.0017 0.2718 $\pm$
0.0054 GatedGCN* 0.6765 $\pm$ 0.0047 0.2477 $\pm$ 0.0009 0.3880 $\pm$ 0.0040
DIGL+MPNN 0.6469 $\pm$ 0.0019 0.3173 $\pm$ 0.0007 0.2824 $\pm$ 0.0039
DIGL+MPNN+LapPE 0.6830 $\pm$ 0.0026 0.2616 $\pm$ 0.0018 0.2921 $\pm$ 0.0038
MixHop-GCN 0.6592 $\pm$ 0.0036 0.2921 $\pm$ 0.0023 0.2506 $\pm$ 0.0133 MixHop-
GCN+LapPE 0.6843 $\pm$ 0.0049 0.2614 $\pm$ 0.0023 0.2218 $\pm$ 0.0174 DRew-GCN
0.6996 $\pm$ 0.0076 0.2781 $\pm$ 0.0028 0.1848 $\pm$ 0.0107 DRew-GCN+LapPE
0.7150 $\pm$ 0.0044 0.2536 $\pm$ 0.0015 0.1851 $\pm$ 0.0092 DRew-GIN 0.6940
$\pm$ 0.0074 0.2799 $\pm$ 0.0016 0.2719 $\pm$ 0.0043 DRew-GIN+LapPE 0.7126
$\pm$ 0.0045 0.2606 $\pm$ 0.0014 0.2692 $\pm$ 0.0059 DRew-GatedGCN 0.6733
$\pm$ 0.0094 0.2699 $\pm$ 0.0018 0.3214 $\pm$ 0.0021 DRew-GatedGCN+LapPE
0.6977 $\pm$ 0.0026 0.2539 $\pm$ 0.0007 0.3314 $\pm$ 0.0024 Transformer+LapPE
0.6326 $\pm$ 0.0126 0.2529 $\pm$ 0.0016 0.2694 $\pm$ 0.0098 SAN+LapPE 0.6384
$\pm$ 0.0121 0.2683 $\pm$ 0.0043 0.3230 $\pm$ 0.0039 GPS+LapPE* 0.6534 $\pm$
0.0091 0.2509 $\pm$ 0.0014 0.4440 $\pm$ 0.0065 Exphormer 0.6527 $\pm$ 0.0043
0.2481 $\pm$ 0.0007 0.3975 $\pm$ 0.0037 GRIT 0.6988 $\pm$ 0.0082 0.2460 $\pm$
0.0012 - GRASS (ours) 0.6353 $\pm$ 0.0056 0.2447 $\pm$ 0.0009 0.5633 $\pm$
0.0092

It has been suggested that oversmoothing can be alleviated by having a shallow
GNN, and oversquashing can be avoided by having wide hidden layers [64].
However, narrow-and-deep GNNs can have better expressivity than wide-and-
shallow GNNs if the pitfalls of training deep GNNs, such as oversmoothing and
oversquashing, can be avoided [43, 44]. This could potentially explain the
competitive performance of GRASS which we configured to be narrow and deep in
our experiments, as specified in Appendix E. In addition, the datasets we
tested are relatively small in sample size (<100k samples), which makes a good
inductive bias more important [6, 47], highlighting the ability of GRASS to
provide a strong inductive bias on graph-structured data while remaining
computationally efficient.

#### Ablation Study.

GRASS achieves its design goals with multiple components, whose importance is
evaluated in the ablation studies shown in Table 3. In particular, the
performance of GRASS with different values of $r$, the degree of the
superimposed random regular graph, is compared in Table 4.

##  5 Conclusion

GRASS demonstrates the effectiveness of random rewiring and our graph-tailored
attention mechanism by achieving state-of-the-art performance, surpassing more
elaborate methods of graph rewiring, as well as more computationally demanding
Graph Transformers. To improve the reproducibility of our results, our
codebase will be made publicly available on GitHub.

#### Limitations.

The output of GRASS is inherently random due to random rewiring. The
relationship between performance variance and $r$ is demonstrated in Table 4.
In scenarios that strictly require deterministic model output, the random
number generator used for random rewiring should be seeded with the input
graph, making the deployment of GRASS more complicated in these scenarios.

## References

  * Alon and Yahav [2020] Uri Alon and Eran Yahav.  On the bottleneck of graph neural networks and its practical implications.  _arXiv preprint arXiv:2006.05205_ , 2020.
  * Arnaiz-Rodriguez et al. [2022] Adrian Arnaiz-Rodriguez, Ahmed Begga, Francisco Escolano, and Nuria Oliver.  Diffwire: Inductive graph rewiring via the lovasz bound.  In _The First Learning on Graphs Conference_ , 2022.
  * Ba et al. [2016] Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton.  Layer normalization.  _arXiv preprint arXiv:1607.06450_ , 2016.
  * Baek et al. [2021] Jinheon Baek, Minki Kang, and Sung Ju Hwang.  Accurate learning of graph representations with graph multiset pooling.  _arXiv preprint arXiv:2102.11533_ , 2021.
  * Bahdanau et al. [2014] Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio.  Neural machine translation by jointly learning to align and translate.  _arXiv preprint arXiv:1409.0473_ , 2014.
  * Baxter [2000] Jonathan Baxter.  A model of inductive bias learning.  _Journal of artificial intelligence research_ , 12:149–198, 2000.
  * Black et al. [2023] Mitchell Black, Zhengchao Wan, Amir Nayyeri, and Yusu Wang.  Understanding oversquashing in gnns through the lens of effective resistance.  In _International Conference on Machine Learning_ , pages 2528–2547. PMLR, 2023.
  * Bollobás and Fernandez de la Vega [1982] Béla Bollobás and W Fernandez de la Vega.  The diameter of random regular graphs.  _Combinatorica_ , 2:125–134, 1982.
  * Bresson and Laurent [2017] Xavier Bresson and Thomas Laurent.  Residual gated graph convnets.  _arXiv preprint arXiv:1711.07553_ , 2017.
  * Bridle [1990] John S Bridle.  Probabilistic interpretation of feedforward classification network outputs, with relationships to statistical pattern recognition.  In _Neurocomputing: Algorithms, architectures and applications_ , pages 227–236. Springer, 1990.
  * Brody et al. [2021] Shaked Brody, Uri Alon, and Eran Yahav.  How attentive are graph attention networks?  _arXiv preprint arXiv:2105.14491_ , 2021.
  * Buluc and Gilbert [2008] Aydin Buluc and John R Gilbert.  Challenges and advances in parallel sparse matrix-matrix multiplication.  In _2008 37th International Conference on Parallel Processing_ , pages 503–510. IEEE, 2008.
  * Cai et al. [2021] Tianle Cai, Shengjie Luo, Keyulu Xu, Di He, Tie-yan Liu, and Liwei Wang.  Graphnorm: A principled approach to accelerating graph neural network training.  In _International Conference on Machine Learning_ , pages 1204–1215. PMLR, 2021.
  * Chan et al. [2023] Timothy M Chan, Virginia Vassilevska Williams, and Yinzhan Xu.  Fredman’s trick meets dominance product: Fine-grained complexity of unweighted apsp, 3sum counting, and more.  In _Proceedings of the 55th Annual ACM Symposium on Theory of Computing_ , pages 419–432, 2023.
  * Chen et al. [2020] Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun.  Measuring and relieving the over-smoothing problem for graph neural networks from the topological view.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 34, pages 3438–3445, 2020.
  * Chen et al. [2023] Xiangning Chen, Chen Liang, Da Huang, Esteban Real, Kaiyuan Wang, Yao Liu, Hieu Pham, Xuanyi Dong, Thang Luong, Cho-Jui Hsieh, et al.  Symbolic discovery of optimization algorithms.  _arXiv preprint arXiv:2302.06675_ , 2023.
  * Chiang and Cholak [2022] David Chiang and Peter Cholak.  Overcoming a theoretical limitation of self-attention.  _arXiv preprint arXiv:2202.12172_ , 2022.
  * Choromanski et al. [2020] Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, et al.  Rethinking attention with performers.  _arXiv preprint arXiv:2009.14794_ , 2020.
  * Corso et al. [2020] Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković.  Principal neighbourhood aggregation for graph nets.  _Advances in Neural Information Processing Systems_ , 33:13260–13271, 2020.
  * Deac et al. [2022] Andreea Deac, Marc Lackenby, and Petar Veličković.  Expander graph propagation.  In _Learning on Graphs Conference_ , pages 38–1. PMLR, 2022.
  * Defferrard et al. [2016] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst.  Convolutional neural networks on graphs with fast localized spectral filtering.  _Advances in neural information processing systems_ , 29, 2016.
  * Dwivedi and Bresson [2020] Vijay Prakash Dwivedi and Xavier Bresson.  A generalization of transformer networks to graphs.  _arXiv preprint arXiv:2012.09699_ , 2020.
  * Dwivedi et al. [2021] Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson.  Graph neural networks with learnable structural and positional representations.  _arXiv preprint arXiv:2110.07875_ , 2021.
  * Dwivedi et al. [2022] Vijay Prakash Dwivedi, Ladislav Rampášek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini.  Long range graph benchmark.  _Advances in Neural Information Processing Systems_ , 35:22326–22340, 2022.
  * Dwivedi et al. [2023] Vijay Prakash Dwivedi, Chaitanya K Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson.  Benchmarking graph neural networks.  _Journal of Machine Learning Research_ , 24(43):1–48, 2023.
  * Ellens et al. [2011] Wendy Ellens, Floske M Spieksma, Piet Van Mieghem, Almerima Jamakovic, and Robert E Kooij.  Effective graph resistance.  _Linear algebra and its applications_ , 435(10):2491–2506, 2011.
  * Ellis [2011] David Ellis.  The expansion of random regular graphs.  _Lecture Notes, Lent_ , 34, 2011.
  * Gao et al. [2023] Jianhua Gao, Weixing Ji, Fangli Chang, Shiyu Han, Bingxin Wei, Zeming Liu, and Yizhuo Wang.  A systematic survey of general sparse matrix-matrix multiplication.  _ACM Computing Surveys_ , 55(12):1–36, 2023.
  * Gasteiger et al. [2019] Johannes Gasteiger, Stefan Weißenberger, and Stephan Günnemann.  Diffusion improves graph learning.  _Advances in neural information processing systems_ , 32, 2019.
  * Gong and Cheng [2019] Liyu Gong and Qiang Cheng.  Exploiting edge features for graph neural networks.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 9211–9219, 2019.
  * Göring [2000] Frank Göring.  Short proof of menger’s theorem.  _Discrete Mathematics_ , 219(1-3):295–296, 2000.
  * Gutteridge et al. [2023] Benjamin Gutteridge, Xiaowen Dong, Michael M Bronstein, and Francesco Di Giovanni.  Drew: Dynamically rewired message passing with delay.  In _International Conference on Machine Learning_ , pages 12252–12267. PMLR, 2023.
  * Hamilton et al. [2017] Will Hamilton, Zhitao Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  _Advances in neural information processing systems_ , 30, 2017.
  * He et al. [2016] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 770–778, 2016.
  * Hornik et al. [1989] Kurt Hornik, Maxwell Stinchcombe, and Halbert White.  Multilayer feedforward networks are universal approximators.  _Neural networks_ , 2(5):359–366, 1989.
  * Hussain et al. [2022] Md Shamim Hussain, Mohammed J Zaki, and Dharmashankar Subramanian.  Global self-attention as a replacement for graph convolution.  In _Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_ , pages 655–665, 2022.
  * Ioffe and Szegedy [2015] Sergey Ioffe and Christian Szegedy.  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  In _International conference on machine learning_ , pages 448–456. pmlr, 2015.
  * Karhadkar et al. [2022] Kedar Karhadkar, Pradeep Kr Banerjee, and Guido Montúfar.  Fosr: First-order spectral rewiring for addressing oversquashing in gnns.  _arXiv preprint arXiv:2210.11790_ , 2022.
  * Kipf and Welling [2016] Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  _arXiv preprint arXiv:1609.02907_ , 2016.
  * Kreuzer et al. [2021] Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou.  Rethinking graph transformers with spectral attention.  _Advances in Neural Information Processing Systems_ , 34:21618–21629, 2021.
  * Leman and Weisfeiler [1968] AA Leman and Boris Weisfeiler.  A reduction of a graph to a canonical form and an algebra arising during this reduction.  _Nauchno-Technicheskaya Informatsiya_ , 2(9):12–16, 1968.
  * Li et al. [2022] Bonan Li, Yinhan Hu, Xuecheng Nie, Congying Han, Xiangjian Jiang, Tiande Guo, and Luoqi Liu.  Dropkey.  _arXiv preprint arXiv:2208.02646_ , 2022.
  * Li et al. [2020] Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem.  Deepergcn: All you need to train deeper gcns.  _arXiv preprint arXiv:2006.07739_ , 2020.
  * Li et al. [2021] Guohao Li, Matthias Müller, Bernard Ghanem, and Vladlen Koltun.  Training graph neural networks with 1000 layers.  In _International conference on machine learning_ , pages 6437–6449. PMLR, 2021.
  * Liu et al. [2020] Liyuan Liu, Xiaodong Liu, Jianfeng Gao, Weizhu Chen, and Jiawei Han.  Understanding the difficulty of training transformers.  _arXiv preprint arXiv:2004.08249_ , 2020.
  * Lutzeyer and Walden [2017] JF Lutzeyer and AT Walden.  Comparing graph spectra of adjacency and laplacian matrices.  _arXiv preprint arXiv:1712.03769_ , 2017.
  * Ma et al. [2023] Liheng Ma, Chen Lin, Derek Lim, Adriana Romero-Soriano, Puneet K Dokania, Mark Coates, Philip Torr, and Ser-Nam Lim.  Graph inductive biases in transformers without message passing.  _arXiv preprint arXiv:2305.17589_ , 2023.
  * Mialon et al. [2021] Grégoire Mialon, Dexiong Chen, Margot Selosse, and Julien Mairal.  Graphit: Encoding graph structure in transformers.  _arXiv preprint arXiv:2106.05667_ , 2021.
  * Misra [2019] Diganta Misra.  Mish: A self regularized non-monotonic activation function.  _arXiv preprint arXiv:1908.08681_ , 2019.
  * Nair and Hinton [2010] Vinod Nair and Geoffrey E Hinton.  Rectified linear units improve restricted boltzmann machines.  In _Proceedings of the 27th international conference on machine learning (ICML-10)_ , pages 807–814, 2010.
  * Noh et al. [2017] Hyeonwoo Noh, Tackgeun You, Jonghwan Mun, and Bohyung Han.  Regularizing deep neural networks by noise: Its interpretation and optimization.  _Advances in neural information processing systems_ , 30, 2017.
  * Nt and Maehara [2019] Hoang Nt and Takanori Maehara.  Revisiting graph neural networks: All we have is low-pass filters.  _arXiv preprint arXiv:1905.09550_ , 2019.
  * Puder [2015] Doron Puder.  Expansion of random graphs: New proofs, new results.  _Inventiones mathematicae_ , 201(3):845–908, 2015.
  * Qian et al. [2023] Chendi Qian, Andrei Manolache, Kareem Ahmed, Zhe Zeng, Guy Van den Broeck, Mathias Niepert, and Christopher Morris.  Probabilistically rewired message-passing neural networks.  _arXiv preprint arXiv:2310.02156_ , 2023.
  * Ramachandran et al. [2017] Prajit Ramachandran, Barret Zoph, and Quoc V Le.  Searching for activation functions.  _arXiv preprint arXiv:1710.05941_ , 2017.
  * Rampášek et al. [2022] Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini.  Recipe for a general, powerful, scalable graph transformer.  _Advances in Neural Information Processing Systems_ , 35:14501–14515, 2022.
  * Rong et al. [2019] Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang.  Dropedge: Towards deep graph convolutional networks on node classification.  _arXiv preprint arXiv:1907.10903_ , 2019.
  * Rossi et al. [2024] Emanuele Rossi, Bertrand Charpentier, Francesco Di Giovanni, Fabrizio Frasca, Stephan Günnemann, and Michael M Bronstein.  Edge directionality improves learning on heterophilic graphs.  In _Learning on Graphs Conference_ , pages 25–1. PMLR, 2024.
  * Shen et al. [2020] Sheng Shen, Zhewei Yao, Amir Gholami, Michael Mahoney, and Kurt Keutzer.  Powernorm: Rethinking batch normalization in transformers.  In _International Conference on Machine Learning_ , pages 8741–8751. PMLR, 2020.
  * Shervashidze et al. [2011] Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt.  Weisfeiler-lehman graph kernels.  _Journal of Machine Learning Research_ , 12(9), 2011.
  * Shirzad et al. [2023] Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J Sutherland, and Ali Kemal Sinop.  Exphormer: Sparse transformers for graphs.  In _International Conference on Machine Learning_ , pages 31613–31632. PMLR, 2023.
  * Smith and Topin [2019] Leslie N Smith and Nicholay Topin.  Super-convergence: Very fast training of neural networks using large learning rates.  In _Artificial intelligence and machine learning for multi-domain operations applications_ , volume 11006, pages 369–386. SPIE, 2019.
  * Tönshoff et al. [2023] Jan Tönshoff, Martin Ritzert, Eran Rosenbluth, and Martin Grohe.  Where did the gap go? reassessing the long-range graph benchmark.  _arXiv preprint arXiv:2309.00367_ , 2023.
  * Topping et al. [2021] Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein.  Understanding over-squashing and bottlenecks on graphs via curvature.  _arXiv preprint arXiv:2111.14522_ , 2021.
  * Vaswani et al. [2017] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  _Advances in neural information processing systems_ , 30, 2017.
  * Veličković [2022] Petar Veličković.  Message passing all the way up.  _arXiv preprint arXiv:2202.11097_ , 2022.
  * Veličković [2023] Petar Veličković.  Everything is connected: Graph neural networks.  _Current Opinion in Structural Biology_ , 79:102538, 2023.
  * Veličković et al. [2017] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio.  Graph attention networks.  _arXiv preprint arXiv:1710.10903_ , 2017.
  * Wang et al. [2022] Hongyu Wang, Shuming Ma, Li Dong, Shaohan Huang, Dongdong Zhang, and Furu Wei.  Deepnet: Scaling transformers to 1,000 layers.  _arXiv preprint arXiv:2203.00555_ , 2022.
  * Wang et al. [2019] Xiao Wang, Houye Ji, Chuan Shi, Bai Wang, Yanfang Ye, Peng Cui, and Philip S Yu.  Heterogeneous graph attention network.  In _The world wide web conference_ , pages 2022–2032, 2019.
  * Williams and Williams [2009] Virginia Vassilevska Williams and Ryan Williams.  Triangle detection versus matrix multiplication: A study of truly subcubic reducibility.  2009\.
  * Wu et al. [2020] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip.  A comprehensive survey on graph neural networks.  _IEEE transactions on neural networks and learning systems_ , 32(1):4–24, 2020.
  * Xu et al. [2018] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.  How powerful are graph neural networks?  _arXiv preprint arXiv:1810.00826_ , 2018.
  * Ying et al. [2021] Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu.  Do transformers really perform badly for graph representation?  _Advances in Neural Information Processing Systems_ , 34:28877–28888, 2021.
  * Yun et al. [2019] Seongjun Yun, Minbyul Jeong, Raehyun Kim, Jaewoo Kang, and Hyunwoo J Kim.  Graph transformer networks.  _Advances in neural information processing systems_ , 32, 2019.
  * Zaheer et al. [2020] Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, et al.  Big bird: Transformers for longer sequences.  _Advances in neural information processing systems_ , 33:17283–17297, 2020.
  * Zehui et al. [2019] Lin Zehui, Pengfei Liu, Luyao Huang, Junkun Chen, Xipeng Qiu, and Xuanjing Huang.  Dropattention: A regularization method for fully-connected self-attention networks.  _arXiv preprint arXiv:1907.11065_ , 2019.
  * Zhang et al. [2018] Jiani Zhang, Xingjian Shi, Junyuan Xie, Hao Ma, Irwin King, and Dit-Yan Yeung.  Gaan: Gated attention networks for learning on large and spatiotemporal graphs.  _arXiv preprint arXiv:1803.07294_ , 2018.

##  Appendix A Pseudocode of the Permutation Model

1:procedure PermutationModel($r$, $|V|$)

2: $\sigma\leftarrow\text{2D array of size }(r,|V|)$

3: for $i\leftarrow 0\text{ to }r-1$ do

4: $\sigma[i,:]\leftarrow\textsc{RandPerm}(|V|)$ $\triangleright$ Random
permutation of integers between $0$ and $|V|-1$

5: end for

6: $A\leftarrow\text{Array of size }r\times|V|$ $\triangleright$ Create an
empty adjacency list

7: for $j\leftarrow 0\text{ to }|V|$ do

8: for $k\leftarrow 0\text{ to }r$ do

9: $A[j\times r+k]\leftarrow\\{j,\sigma[k,j]\\}$ $\triangleright$ Add an edge
to the adjacency list

10: end for

11: end for

12: $A\leftarrow\textsc{RemoveSelfLoop}(A)$ $\triangleright$ Remove self-loops
from the adjacency list

13: $A\leftarrow\textsc{RemoveMultiEdge}(A)$ $\triangleright$ Remove multi-
edges from the adjacency list

14: return $A$

15:end procedure

Algorithm 1 The Permutation Model

##  Appendix B Graphical Descriptions of GRASS

Figure 2: The high-level structure of GRASS. Figure 3: The structure of an
attention layer of GRASS. Node aggregation is attentive, with attention
weights derived from edge representations. Edge aggregation is done through an
FFN. For simplicity, biases are not shown here.

##  Appendix C Ablation Study

Table 3: Ablation study results on different components of GRASS. This table
shows the performance of each ablated model as the mean $\pm$ s.d. over 8
runs. *The absolute difference between the LapPEs (8 eigenvalues) of
neighboring nodes are used as edge encodings, as proposed by Kreuzer et al.
[40].

Model ZINC MAE $\downarrow$ GRASS 0.0461 $\pm$ 0.0014 Remove RRWP encoding
0.0797 $\pm$ 0.0040 RRWP encoding $\rightarrow$ relative LapPE* 0.0708 $\pm$
0.0032 Remove DropKey 0.0549 $\pm$ 0.0125 Remove edge flipping 0.0477 $\pm$
0.0010 PN-V $\rightarrow$ LN [3] 0.0497 $\pm$ 0.0013 Sum pooling $\rightarrow$
Mean pooling 0.0514 $\pm$ 0.0018

Table 4: Ablation study results on the random regular graph degree $r$. This
table shows the performance of GRASS on ZINC with the corresponding values of
$r$ as the mean $\pm$ s.d. over 8 runs. The average variance of model
performance due to random rewiring, as well as their sample standard
deviations, are also shown. They are measured by evaluating the test set 30
times on each trained model. For comparison, the variance of model performance
due to randomness in the training process is 2.03e-6 with the hyperparameters
shown in Table 7.

Random Regular Graph Degree $r$ 0 3 6 9 12 15 ZINC MAE $\downarrow$ 0.0495
0.0470 0.0461 0.0473 0.0473 0.0478 $\pm$ 0.0016 $\pm$ 0.0023 $\pm$ 0.0014
$\pm$ 0.0015 $\pm$ 0.0024 $\pm$ 0.0011 Variance in ZINC MAE Due to Random
Rewiring - 6.31e-8 1.22e-7 1.23e-7 1.79e-7 1.58e-7 - $\pm$ 2.32e-8 $\pm$
5.90e-8 $\pm$ 9.36e-8 $\pm$ 1.50e-7 $\pm$ 1.04e-7

##  Appendix D Datasets

Table 5: Statistics of GNN Benchmark Datasets used in section 4, adapted from
Rampášek et al. [56].

Dataset # Graphs Avg. # Nodes Avg. # Edges Task Metric ZINC 12000 23.2 24.9
Graph Regression MAE $\downarrow$ MNIST 70000 70.6 564.5 Graph Classif.
Accuracy $\uparrow$ CIFAR10 60000 117.6 941.1 Graph Classif. Accuracy
$\uparrow$ PATTERN 14000 118.9 3039.3 Node Classif. Accuracy $\uparrow$
CLUSTER 12000 117.2 2150.9 Node Classif. Accuracy $\uparrow$

Table 6: Statistics of LRGB datasets used in section 4, adapted from Dwivedi
et al. [24].

Dataset # Graphs Avg. # Nodes Avg. # Edges Avg. Short. Path Avg. Diameter Task
Metric Peptides-func 15535 150.94 307.30 20.89 $\pm$ 9.79 56.99 $\pm$ 28.72
Graph Classif. AP $\uparrow$ Peptides-struct 15535 150.94 307.30 20.89 $\pm$
9.79 56.99 $\pm$ 28.72 Graph Regression MAE $\downarrow$ PascalVOC-SP 11355
479.40 2710.48 10.74 $\pm$ 0.51 27.62 $\pm$ 2.13 Node Classif. Macro F1
$\uparrow$

##  Appendix E Hyperparameters

Table 7: Model hyperparameters for experiments on GNN Benchmark Datasets. The
results are shown in table 1.

Model ZINC MNIST CIFAR10 PATTERN CLUSTER # Parameters 499777 104338 104386
498626 498854 # Attention Layers 49 15 15 53 53 Attention Layer Dim. 32 24 24
32 32 Task Head Hidden Dim. 192 144 144 N/A (Linear) N/A (Linear) # Epochs
2000 200 400 500 100 Warmup Epoch Ratio 0.1 0.05 0.1 0.1 0.1 Batch Size 200
200 200 200 200 Initial Learning Rate 1e-7 1e-7 1e-7 1e-7 1e-7 Peak Learning
Rate 5e-4 1e-3 1e-3 1e-3 1e-3 Final Learning Rate 1e-7 1e-7 1e-7 3e-4 1e-7
Betas (0.95, 0.98) (0.95, 0.98) (0.95, 0.98) (0.95, 0.98) (0.95, 0.98) Weight
Decay Factor 0.3 0.3 0.3 3.0 0.3 Attention DropKey Rate 0.1 0.1 0.1 0.3 0.3
Label Smoothing Factor N/A (Regression) 0.1 0.1 0.1 0.1 Random Regular Graph
Degree 6 3 3 15 15 RRWP Random Walk Length 32 24 24 32 32

Table 8: Model hyperparameters for experiments on LRGB datasets. The results
are shown in table 2.

Model Peptides-func Peptides-struct PascalVOC-SP # Parameters 497866 498155
498133 # Attention Layers 48 48 53 Attention Layer Dim. 32 32 32 Task Head
Hidden Dim. 192 192 N/A (Linear) # Epochs 500 500 600 Warmup Epoch Ratio 0.1
0.1 0.1 Batch Size 200 200 200 Initial Learning Rate 1e-7 1e-7 1e-7 Peak
Learning Rate 1e-3 1e-3 1e-3 Final Learning Rate 1e-7 1e-7 1e-7 Betas (0.95,
0.98) (0.95, 0.98) (0.95, 0.98) Weight Decay Factor 3.0 3.0 1.0 Attention
DropKey Rate 0.1 0.1 0.1 Label Smoothing Factor 0.1 N/A (Regression) 0.1
Random Regular Graph Degree 6 6 3 RRWP Random Walk Length 32 32 16

##  Appendix F Computational Performance

Table 9: Computational performance of GRASS on GNN Benchmark Datasets.
Training time per epoch is the wall-clock time taken to complete a single
training epoch, shown as the mean $\pm$ s.d. over all epochs of a single run.
Preprocessing time is the wall-clock time taken to load, preprocess, and store
the whole dataset prior to training, shown as the mean $\pm$ s.d. over 4 runs.
Specifications of the hardware used to run these experiments are also shown.

Dataset ZINC MNIST CIFAR10 PATTERN CLUSTER Training Time per Epoch (s) 2.71
$\pm$ 0.13 11.41 $\pm$ 0.15 13.08 $\pm$ 0.10 150.30 $\pm$ 0.17 122.31 $\pm$
0.08 Preprocessing Time (s) 28.35 $\pm$ 0.19 74.12 $\pm$ 0.44 139.50 $\pm$
6.55 33.08 $\pm$ 0.40 27.06 $\pm$ 0.10 Model Compilation Yes No Activation
Checkpointing No Yes GPU NVIDIA GeForce RTX 4090 VRAM 24GB CPU AMD Ryzen 9
7950X RAM 128GB

Table 10: Computational performance of GRASS on LRGB datasets. The definitions
of these statistics and the procedure of measuring them are identical to that
described in Table 9.

Dataset Peptides-func Peptides-struct PascalVOC-SP Training Time per Epoch (s)
10.44 $\pm$ 0.10 10.21 $\pm$ 0.09 21.56 $\pm$ 0.10 Preprocessing Time (s)
69.78 $\pm$ 4.09 69.81 $\pm$ 2.18 181.28 $\pm$ 1.33 Model Compilation Yes
Activation Checkpointing No GPU NVIDIA GeForce RTX 4090 NVIDIA RTX A6000 Ada
VRAM 24GB 48GB CPU AMD Ryzen 9 7950X RAM 128GB