Greener GRASS: Enhancing GNNs with Encoding, Rewiring, and Attention

## Abstract

Abstract Graph Neural Networks (GNNs) have become important tools for machine learning on graph-structured data. In this paper, we explore the synergistic combination of graph encoding, graph rewiring, and graph attention, by introducing Gr aph A ttention with S tochastic S tructures (GRASS), a novel GNN architecture. GRASS utilizes relative random walk probabilities (RRWP) encoding and a novel decomposed variant (D-RRWP) to efficiently capture structural information. It rewires the input graph by superimposing a random regular graph to enhance long-range information propagation. It also employs a novel additive attention mechanism tailored for graph-structured data. Our empirical evaluations demonstrate that GRASS achieves state-of-the-art performance on multiple benchmark datasets, including a 20.3% reduction in mean absolute error on the ZINC dataset.

## 1 Introduction

Graph Neural Networks (GNNs) have revolutionized machine learning tasks involving graph-structured data Wu et al. (); Veličković (). Various paradigms within GNNs offer distinct advantages: message-passing neural networks (MPNNs) effectively leverage local graph structure Kipf and Welling () and are often complemented with graph rewiring techniques to modify the graph’s topology and facilitate message passing Topping et al. (); Graph Transformers (GTs) incorporate attention mechanisms to capture global dependencies Yun et al. (); Rampášek et al. () and can be enhanced by graph encoding methods that enrich node and edge features with structural information Dwivedi et al. (; ).

The goal of this work is to create a new architecture that can possess the advantageous properties of the methods discussed above. To achieve this goal, we propose Graph Attention with Stochastic Structures (GRASS), a GNN architecture that synergistically combines random walk encoding, random rewiring, and also introduces a novel additive attention mechanism designed for graph-structured data. We conduct a series of experiments on multiple benchmark datasets and perform various ablation studies to assess the performance of GRASS. Our results show that GRASS achieves competitive or superior performance compared to existing methods on multiple popular datasets, suggesting that the synergy of random walk encoding, random rewiring, and a graph-tailored attention mechanism can effectively enhance GNNs.

#### Our Contributions.

- •
We propose GRASS, a GNN architecture that integrates random walk encoding, random rewiring, and a novel additive attention mechanism designed for graphs.
- •
We analyze these components with respect to desirable properties of a GNN and provide insights into how they contribute to the model’s performance.
- •
We provide empirical evidence through experiments and ablation studies that a carefully selected combination of these components can lead to improved performance on multiple benchmark datasets.

In the remainder of the paper, we review related work in Section 2, describe the architecture of GRASS in Section 3, present experimental results in Section 4, and draw conclusions in Section 5.

## 2 Related Work

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

#### Message-Passing Neural Networks.

Message-Passing Neural Networks (MPNNs), such as Graph Convolutional Networks (GCNs) Kipf and Welling (), GraphSAGE Hamilton et al. (), and Graph Isomorphism Networks (GIN) Xu et al. (), propagate information within local neighborhoods of a graph. By aligning computation with the structure of the graph, MPNNs offer a strong inductive bias for graph-structured data Ma et al. ().

#### Graph Rewiring.

Graph rewiring techniques modify the topology of graphs to improve their connectivity, often leveraging spectral properties to guide the process Topping et al. (); Arnaiz-Rodriguez et al. (). Rewiring improves MPNNs by alleviating issues in information propagation, such as underreaching, which occurs when distant nodes cannot communicate Alon and Yahav (). In this work, we explore a form of random rewiring that superimposes a random regular graph on the input graph.

#### Graph Transformers.

Attention mechanisms Vaswani et al. () allow GNNs to weigh the importance of neighboring nodes during aggregation Veličković et al. (). Graph Transformers (GTs), such as Graph Transformer Network (GTN) Yun et al. (), extend this idea to global attention across nodes. GTs often inherit attention mechanisms designed for sequences, which may not be optimal for graphs Chen et al. (). Designing attention mechanisms specifically for graph-structured data is an active area of research, and we aim to contribute to it by proposing a novel additive attention mechanism.

#### Graph Encoding.

Enhancing node and edge features with graph encodings has been shown to improve GNN performance, especially for GTs Dwivedi et al. (). Techniques such as Laplacian positional encodings (LapPE) Dwivedi et al. () and relative random walk probabilities (RRWP) encoding Ma et al. () incorporate structural information into node and edge features, enhancing GTs, which otherwise lack a graph inductive bias Ma et al. (). We utilize RRWP encoding in GRASS, and propose a decomposed variant (D-RRWP) with improved computational efficiency.

#### Notable Combinations.

The General, Powerful, Scalable (GPS) Graph Transformer Rampášek et al. () represents a hybrid of MPNN and GT, merging the inductive bias of message passing with the global perspective of Transformers. Exphormer Shirzad et al. () combines GTs and rewiring by adding random edges and supernodes, generalizing BigBird Zaheer et al. (), a sparse Transformer, to graph-structured data.

Our work builds upon these paradigms by incorporating random walk encoding and random rewiring, and we also create a novel additive attention mechanism tailored for graphs. Although RRWP encoding and random rewiring have been explored separately Ma et al. (); Shirzad et al. (), their combination with each other and a graph-tailored attention mechanism is, to the best of our knowledge, novel. Our experiments show that this architecture not only matches but often exceeds state-of-the-art performance across a wide range of benchmark problems.

## 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 describe the role of each component in terms of the design goals.

#### 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) of the model.

- 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 Veličković (). 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}$.
- 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 Dwivedi et al. (). However, MPNN layers, which propagate information locally, frequently fail in this regard Ma et al. (). 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$ Alon and Yahav (). 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 Topping et al. (). 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 Alon and Yahav ().
- 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 Veličković (). In deep models, this can lead to oversmoothing, where the representation of nodes becomes too similar to be effectively classified in the process of repeated aggregation Chen et al. (). Therefore, when required by the task, nodes should aggregate information from relevant neighbors only, instead of doing so unconditionally, in order to maintain distinguishability of node representations.
- 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 they connect Gong and Cheng (). In addition to the semantic relationships represented by edge features of the input graph, structural relationships can be represented by edge encodings added by the model Rampášek et al. (). To capture the relationships between nodes, edge representations should combine information from both edge features and encodings, and undergo deep processing through multiple layers.
- E2.
Directionality Preservation – The model should preserve and utilize information carried by edge directions.
Many graphs representing real-world relationships are inherently directed Rossi et al. (). 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 Rossi et al. (). It would be beneficial for the model’s expressivity if edge directionality information could be preserved without severely limiting communication.

Figure: Figure 1: The structure of GRASS. Prior to training, GRASS precomputes (D-)RRWP encodings. At each training iteration, it rewires the input graph and adds distinct embeddings to added edges.
Refer to caption: x2.png

#### The Structure of GRASS.

The high-level structure of GRASS is illustrated in Figure 1. Prior to training, GRASS precomputes the (D-)RRWP encoding 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, we apply relative random walk probabilities (RRWP) encoding Ma et al. () to represent structural relationships. In addition, we propose D-RRWP, a decomposed variant of RRWP
that offers improved computational efficiency.

#### RRWP Encoding.

RRWP encoding has been shown to be an expressive representation of graph structure both theoretically and practically Ma et al. (), 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, a diagonal 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 Dwivedi et al. (). 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) Ioffe and Szegedy () to improve their distribution. Here, $\mathbf{W}$ denotes trainable weights, $n$ denotes the dimensionality of hidden layers, and $\|$ denotes concatenation.

$$ $\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}\,\|\, \mathbf{P}_{:,j,i}):\mathbb{R}^{n}$ (2) $$

Before entering attention layers, RRWP encodings are added to both node features and edge features, including those of edges added by random rewiring. The node encodings are additionally accompanied by degree information Ying et al. (). Here, $\text{d}^{+}(i)$ and $\text{d}^{-}(i)$ denote the out-degree and in-degree of node $i$, respectively.

$$ $\displaystyle\mathbf{x}_{i}^{0}$ $\displaystyle=\mathbf{x}^{\text{in}}_{i}+\mathbf{x}^{\text{RW}}_{i}+\mathbf{W} _{\text{deg}}\text{BN}(\text{d}^{+}(i)\,\|\,\text{d}^{-}(i)):\mathbb{R}^{n}$ (3) $\displaystyle\mathbf{e}_{i,j}^{0}$ $\displaystyle=\mathbf{e}^{\text{in}}_{i,j}+\mathbf{e}^{\text{RW}}_{i,j}: \mathbb{R}^{n}$ (4) $$

#### Improving Efficiency.

RRWP encodings take $O(k|V||E|)$ time to compute and $O(k|V|^{2})$ space to store Ma et al. (). On extremely large graphs, this could be computationally prohibitive even when computed once per dataset. We propose D-RRWP, a decomposed variant of RRWP. Instead of computing the exact random walk probabilities $\mathbf{P}$ from the transition matrix $\mathbf{T}$, we approximate it with its truncated eigendecomposition to reduce the complexity to $O(km(|V|+|E|))$ time and $O((k+m)|V|+k|E|)$ space, where $m\leq|V|$ is the number of eigenpairs used for the approximation.

To ensure that the transition matrix is diagonalizable, we replace $\mathbf{T}$ with $\mathbf{T}_{\text{sym}}=\mathbf{D}^{-\frac{1}{2}}\mathbf{A}\mathbf{D}^{-\frac{
1}{2}}$, which is always diagonalizable if $\mathbf{A}$ is a symmetric adjacency matrix—that of an undirected graph. Given the degree matrix $\mathbf{D}$, this modification does not result in a loss of information, because $\mathbf{T}_{\text{sym}}=\mathbf{D}^{\frac{1}{2}}\mathbf{T}\mathbf{D}^{-\frac{1
}{2}}$. Since $\mathbf{T}_{\text{sym}}$ is diagonalizable, its truncated eigendecomposition coincides with its truncated singular value decomposition (SVD), which is the optimal low-rank approximation of a matrix Eckart and Young ().

Let $\tilde{\mathbf{T}}_{\text{sym}}=\tilde{\mathbf{Q}}\tilde{\mathbf{\Lambda}}
\tilde{\mathbf{Q}}^{\top}$ be the truncated eigendecomposition of $\mathbf{T}_{\text{sym}}$, where $\tilde{\mathbf{Q}}:[-1,1]^{|V|\times m}$ and $\tilde{\mathbf{\Lambda}}:[-1,1]^{m\times m}$ contain the $m$-largest (in magnitude) eigenvectors and eigenvalues of $\mathbf{T}_{\text{sym}}$, respectively. Calculating the truncated eigendecomposition of $\mathbf{T}_{\text{sym}}$ takes $O(m|E|)$ time with the Lanczos algorithm Lanczos (); Lehoucq et al. (), and the results can be stored in $O(m|V|)$ space. We approximate $\mathbf{P}_{h,i,j}=\mathbf{T}^{h}_{\text{sym }i,j}$ with $\tilde{\mathbf{T}}^{h}_{\text{sym }i,j}=(\tilde{\mathbf{Q}}\tilde{\mathbf{
\Lambda}}^{h}\tilde{\mathbf{Q}}^{\top})_{i,j}=(\tilde{\mathbf{Q}}_{i}\odot
\tilde{\mathbf{Q}}_{j})\cdot\tilde{\mathbf{\Lambda}}^{h}$
which takes $O(km(|V|+|E|))$ time and $O(k(|V|+|E|))$ space to calculate for all nodes, edges, and random walk steps $1\leq h\leq k$. Here, $\odot$ denotes the Hadamard product. This is possible because we can calculate $\tilde{\mathbf{T}}^{h}_{\text{sym}}$ by taking the powers of $\tilde{\mathbf{\Lambda}}$, a diagonal matrix, in $O(km)$ time and space. If we were to replace $\mathbf{T}_{\text{sym}}$ with a non-diagonalizable transition matrix, and eigendecomposition with SVD, calculating its powers efficiently using this approach would no longer be possible.

Since $\tilde{\mathbf{\Lambda}}^{h}$ can take at most $m$ linearly independent values as we vary $h$, increasing $k$ beyond $m$ does not add additional information to the encoding. Consequently, we fix $k=m$ in our experiments.

### 3.2 Random Rewiring

To achieve Effective Communication, GRASS rewires the input graph by superimposing a random regular graph. We present some motivations for using random regular graphs instead of deterministic or non-regular graphs in Appendix A.1. Shirzad et al. () uses a similar technique in generalizing BigBird Zaheer et al. () to graphs, and discusses additional motivations. We also demonstrate the advantage of using random regular graphs with empirical results shown in Figure 4 and Table 3. Here, we provide details on random regular graph generation and input graph rewiring.

#### Generating Random Regular Graphs.

We generate random regular graphs with the Permutation Model Friedman et al. () that we describe here and with pseudocode in Appendix A.2. 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)\}\}$ (5) $$

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 Friedman et al. (). 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 Ellis ():

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

Therefore, if we regenerate $\tilde{R}$ when it is 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 requires the superimposed graph to be simple to avoid passing duplicate messages. Meanwhile, the regularity of the graph is desired but not strictly required. Therefore, when $\tilde{R}$ is not simple, we remove self-loops and multi-edges from $\tilde{R}$ to obtain $R$, which is always simple but not necessarily regular.

Our empirical results presented in Figure 4 and Table 3 suggest that a small value of $r$ is often sufficient. In our experiments, we use $r\leq 6$.

#### Rewiring the Input Graph.

To rewire the input graph $G$, GRASS superimposes the edges of $R$ on $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\varnothing$, 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.

As illustrated in Figure 1, the added edges $E_{R}$ are given a distinct embedding to distinguish them from the existing edges $E_{G}$. This aids Selective Aggregation, as it allows a node to select between its neighbors and a random node. The added edges also receive (D-)RRWP encodings to enhance 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$ can be represented by the random walk probabilities $\mathbf{P}_{:,i,j}$ given to that edge as its (D-)RRWP encoding.

Figure: Figure 2: Visualization of the proposed random rewiring technique. Solid lines denote existing edges of the input graph, and dashed lines denote added edges. (a) An example of the input graph $G$ that has poor connectivity. (b, c) Two among all possible instances of the randomly rewired graph $H$ with $r=2$. They have better connectivity than the input graph.
Refer to caption: x3.png

### 3.3 Attention Mechanism

Many GTs emulate the structure of Transformers designed for Euclidean data Dwivedi and Bresson (); Kreuzer et al. (); Ying et al. (); Hussain et al. (); Shirzad et al. (). 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 provides a simple visualization, and Figure 5 illustrates its structure in detail. The GRASS attention mechanism is defined as follows, where $\mathcal{N}^{-}$ denotes in-neighbors, $\mathbf{W}$ denotes trainable weights, and $\varepsilon$ denotes a small constant added for numerical stability. For simplicity, biases are not shown in these equations.

$$ $\displaystyle\mathbf{s}_{i,j}^{l}$ $\displaystyle=\text{dropout}(\exp(\mathbf{W}^{l}_{\text{attn}\leftarrow\text{ edge}}\mathbf{e}_{i,j}^{l-1})):{\mathbb{R}^{+}}^{n}$ (7) $\displaystyle\mathbf{a}_{i,j}^{l}$ $\displaystyle=\frac{\mathbf{s}_{i,j}^{l}}{\sum_{h\in\mathcal{N}^{-}(j)\cup\{j \}}\mathbf{s}_{h,j}^{l}+\varepsilon}:{\mathbb{R}^{+}}^{n}$ (8) $\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)\cup\{j\}}\mathbf{a}_{i,j}^{l}\odot(\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}$ (9) $\displaystyle\tilde{\mathbf{e}}_{j,i}^{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}$ (10) $$

#### Attention Weights.

This attention mechanism is unique in the way it uses edge representations as the medium of attention weights. To achieve 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 while preserving Permutation Equivariance. Assuming that Relationship Representation is satisfied, edge features would already represent node relationships, which could be used as attention weights $\mathbf{a}_{i,j}$ after applying a linear layer and performing a component-wise softmax over the neighborhood.

#### Random Edge Removal.

To complement the proposed random rewiring technique, which adds edges but never removes them, GRASS attention randomly removes edges in computing attention weights with the dropout function in Equation 7. The goal is to reduce the model’s dependence on the presence of particular edges in the graph, facilitating Selective Aggregation. Notably, this can also be seen as a generalization of DropKey Li et al. () to graphs, because it randomly masks the attention matrix prior to the softmax operation.

#### 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. In Equation 10, we compute $\tilde{\mathbf{e}}_{j,i}^{l}$, the updated representation of edge $j\rightarrow i$ by using $\mathbf{e}_{i,j}^{l-1}$, the representation of edge $i\rightarrow j$ from the previous layer, effectively flipping the edge.

#### Feed-Forward Network.

Similar to Transformers, the output of the attention mechanism is passed through an FFN. Here, $\phi$ denotes a ReLU-like Nair and Hinton (); Ramachandran et al. () nonlinear activation function, which we choose to be Mish Misra ().

$$ $\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}$ (11) $\displaystyle\hat{\mathbf{e}}_{i,j}^{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}$ (12) $$

#### Normalization and Residual Connection.

We use post-normalization in residual connections, which has been shown to improve the expressiveness of Transformers Liu et al. (). The residual connection is scaled by the constant $\alpha$ to improve training stability Wang et al. ().

$$ $\displaystyle\mathbf{x}_{i}^{l}$ $\displaystyle=\text{BN}(\mathbf{x}_{i}^{l-1}+\alpha\hat{\mathbf{x}}_{i}^{l}): \mathbb{R}^{n}$ (13) $\displaystyle\mathbf{e}_{i,j}^{l}$ $\displaystyle=\text{BN}(\mathbf{e}_{i,j}^{l-1}+\alpha\hat{\mathbf{e}}_{i,j}^{l }):\mathbb{R}^{n}$ (14) $$

#### 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 global properties relevant to the task Wu et al. (). GRASS employs sum pooling, a simple pooling method as powerful as the Weisfeiler-Lehman graph isomorphism test Leman and Weisfeiler (), while many more complicated methods are not Baek et al. (). 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}\;\Bigg{\|}\;\sum_{(i,j)\in E_ {G}}\mathbf{e}_{i,j}^{L}\;\Bigg{\|}\;\sum_{(i,j)\in E_{R}}\mathbf{e}_{i,j}^{L} \;:\mathbb{R}^{3n}$ (15) $$

Table: Table 1: Performance on GNN Benchmark Datasets. The performance of GRASS shown here is the mean ± s.d. of 16 runs on ZINC, and 8 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. (), Shirzad et al. (), and Chen et al. ().

### 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 Veličković (). GRASS can be seen as an MPNN that injects additive and multiplicative noise into the adjacency matrix, through random rewiring and random edge removal, 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}$ (16) $$

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 the dropout function in Equation 7 (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 Noh et al. (), and for graph-structured data, the random removal of edges has demonstrated regularization effects Rong et al. ().

#### 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 Veličković () being

$$ $\mathbf{x}^{\prime}_{j}=\phi\Biggl{(}\mathbf{x}_{j},\bigoplus_{i\in\mathcal{N} (j)}a(\mathbf{x}_{i},\mathbf{x}_{j})\psi(\mathbf{x}_{i})\Biggr{)}$ (17) $$

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 Vaswani et al. (), 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 Bahdanau et al. (). 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 Rampášek et al. () or generalizing Shirzad et al. () BigBird’s sparse dot-product attention. Meanwhile, GRASS achieves sparsity in a graph-native way: attention is always local, so non-adjacent 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 16, which contains $O(r|V|+|E|)$ nonzero elements.

Table: Table 2: Performance on LRGB datasets. The performance of GRASS shown here is the mean ± 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. (), Tönshoff et al. (), Ma et al. (), Shirzad et al. (), and Chen et al. (). ^*To provide stronger baselines, Tönshoff et al. () has improved the performance of these models by re-tuning their hyperparameters.

## 4 Experiments

### 4.1 Benchmarking GRASS

#### Experimental Setup.

To measure the performance of GRASS, we train and evaluate it on five of the GNN Benchmark Datasets Dwivedi et al. (): ZINC, MNIST, CIFAR10, CLUSTER, and PATTERN, as well as four of the Long Range Graph Benchmark (LRGB) Dwivedi et al. () datasets: Peptides-func, Peptides-struct, PascalVOC-SP, and COCO-SP. Following the experimental setup of Rampášek et al. () and other work that we compare, 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 E.1.

Due to the use of random rewiring, the output of the model is not deterministic. Therefore, we evaluate the trained model 100 times for ZINC, and 10 times for other datasets, for each training run. The average performance is reported as the performance of that run. We use D-RRWP encoding on Peptides-func, PascalVOC-SP and COCO-SP, and RRWP encoding on other datasets. Models are trained with the Lion optimizer Chen et al. (). Hyperparameters can be found in Appendix E.2.

Figure: Figure 4: Visualized ablation study results for the number of added edges per node, with random regular and non-regular graphs, on ZINC. Error bars represent one standard error of the mean. The setup is identical to that described in Table 3.
Refer to caption: x5.png

#### Results.

As shown in Tables 1 and 2, GRASS ranks first on ZINC, MNIST, CIFAR10, PATTERN, Peptides-struct, PascalVOC-SP, and COCO-SP, while ranking second on CLUSTER and fifth on Peptides-func, among the models compared. Notably, GRASS achieves 20.3% lower MAE on ZINC compared to GRIT Ma et al. (), the second-best model, which has $O(|V|^{2})$ time and space complexity.

Table: Table 3: Ablation study results for the number of added edges per node, with random regular and non-regular graphs, on ZINC. Reported values for ablated models, except peak VRAM consumption, are the mean ± s.d. over 8 runs. The variance of model performance due to random rewiring are measured by evaluating the test set 100 times on each trained model. For comparison, the variance of model performance due to randomness in the training process is 1.79e-6.

### 4.2 Ablation Study

#### Experimental Setup.

We examine the impact of RRWP encoding and D-RRWP encoding by comparing their performance with each other and with LapPE Dwivedi et al. (), a widely used graph encoding technique. We examine the effects of random rewiring by varying the number of added edges per node, and superimposing random non-regular graphs instead of random regular graphs. Furthermore, we assess the effects of the GRASS attention mechanism by replacing it with the attention mechanisms of GAT Veličković et al. (), GatedGCN Bresson and Laurent (), and Transformer Vaswani et al. (), while keeping the rest of the model intact. These experiments are conducted on ZINC, a well-known GNN benchmark that represents tasks on smaller graphs, and PascalVOC-SP, which represents tasks on larger graphs that require long-range interaction. Detailed results on PascalVOC-SP are presented in Appendix C. Additionally on ZINC, we explore the impact of minor design choices, including random edge removal, edge flipping, normalization, graph pooling, and the optimizer. Our findings suggest that the combination of (D-)RRWP encoding, random rewiring, and GRASS attention demonstrates superior effectiveness compared to alternative combinations on the evaluated datasets.

Table: Table 4: Ablation study results for graph encoding, attention mechanism, and minor design decisions on ZINC. This table shows the performance of each ablated model as the mean ± s.d. over 8 runs. The implementations of replacement attention mechanisms are provided by PyTorch Geometric Fey and Lenssen (), and we adjust the head size to approach 500k parameters. ^*The maximum number of Laplacian eigenvectors to use for LapPE on ZINC is 8, which is constrained by the smallest graph in the dataset. For a fair comparison, we include a setup that pads the LapPE of smaller graphs with zeros to raise the maximum number of eigenvectors to 32. ^†The learning rate is adjusted for these configurations to stabilize training. ^‡The batch size, learning rate, betas, and weight decay factor are adjusted for this configuration to stabilize training.

#### Random Walk Encoding.

On both ZINC and PascalVOC-SP, switching between RRWP and D-RRWP results in an insignificant change in performance: 0.64% on ZINC and 0.35% on PascalVOC-SP. However, replacing D-RRWP with RRWP results in a 17.73$\times$ larger preprocessed dataset on PascalVOC-SP. This highlights the viability of D-RRWP as an efficient replacement of RRWP on larger graphs. Replacing RRWP or D-RRWP with LapPE results in a significant degradation of performance on ZINC, but a much smaller degradation on PascalVOC-SP, indicating that the combination of LapPE with other components of GRASS are not as effective and more dataset-dependent.

#### Random Rewiring.

On both ZINC and PascalVOC-SP, the optimal number of added edges per node is 6 with random regular graphs, while adding more or fewer edges leads to suboptimal performance. On ZINC, switching from regular to non-regular random graphs increases the number of added edges required to achieve similar performance, resulting in longer runtime and higher memory consumption. This demonstrates the advantage of random rewiring with regular graphs.

#### GRASS Attention.

On both ZINC and PascalVOC-SP, replacing GRASS attention with alternative attention mechanisms substantially degrades performance, by at least 26.0% on ZINC and 14.7% on PascalVOC-SP. This indicates that GRASS attention, our novel design, is a vital component for GRASS to achieve its competitive performance.

#### Minor Design Decisions.

None of the minor design decisions, when altered or removed, results in a significant performance degradation on ZINC: an advantage of at least 15.2% is maintained compared to GRIT, the second-best model. This verifies that the performance advantage of GRASS is achieved mainly by the proposed combination of encoding, rewiring, and attention mechanism.

## 5 Conclusion

We have presented GRASS, a novel GNN architecture that synergistically integrates (D-)RRWP encoding, random rewiring, and a new graph-tailored additive attention mechanism. Our empirical evaluations show that GRASS achieves and often surpasses state-of-the-art performance across a diverse set of benchmark problems.

### 5.1 Limitations

#### Empirical Evaluation of Scalability.

GRASS has $O(|V|+|E|)$ time and space complexity, which implies good scalability to extremely large-and-sparse graphs. Evaluating GRASS thoroughly on these datasets is not currently within the scope of this project, due to time and resource constraints. We aim to further explore the scalability of GRASS in future work.

#### Nondeterministic Output.

The output of GRASS is inherently random due to random rewiring. The relationship between performance variance and the number of randomly added edges is demonstrated in Table 3 and Table 5. In scenarios that strictly require deterministic output, the random number generator used for random rewiring needs to be seeded with the input graph, making the deployment of GRASS more complicated in these scenarios.

### 5.2 Reproducibility

To enhance the reproducibility of this work, we will release the source code of GRASS on GitHub.

## Appendix A Random Rewiring

### A.1 Motivations for Superimposing Random Regular Graphs

#### 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 Alon and Yahav []. Superimposing a random regular graph on 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|$ (18) $$

is the upper bound of the diameter of almost every random $r$-regular graph with $|V|$ nodes, where $r\geq 3$ and $\varepsilon>0$ Bollobás and Fernandez de la Vega []. 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 Ellens et al. [], which has been shown to be positively associated with oversquashing Black et al. []. 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 Alon and Yahav [], 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$ Ellis []. Menger’s Theorem then lower-bounds the number of internally disjoint paths by a graph’s vertex connectivity Göring [].

#### 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 Karhadkar et al. []. 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 Puder [].
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}$ Lutzeyer and Walden [], lower-bounding the spectral gap with $\lambda_{1}>r-2\sqrt{r-1}-1$.

### A.2 Pseudocode of the Permutation Model

Figure: Algorithm 1 The Permutation Model Friedman et al. []

## Appendix B GRASS Attention

Figure: Figure 5: 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 MLP. For simplicity, biases are not shown here.
Refer to caption: x6.png

## Appendix C Additional Ablation Study Results

Table: Table 5: Ablation study results for the number of added edges per node on PascalVOC-SP. Reported values, except peak VRAM consumption, are the mean ± s.d. over 8 runs. The experimental setup is identical to that described in Table 3. For comparison, the variance of model performance due to randomness in the training process is 2.36e-5.

Table: Table 6: Ablation study results for graph encoding, graph rewiring, and attention mechanism on PascalVOC-SP. This table shows the performance of each ablated model as the mean ± s.d. over 4 runs. The experimental setup is identical to that described in Table 4. ^*Using RRWP encoding with 128 random walk steps would result in OOM during preprocessing. With D-RRWP (128 eigenpairs, 128 steps), the preprocessed dataset has size 6.40 GiB, while with RRWP (32 steps), the preprocessed dataset has size 113.46 GiB, which is 17.73$\times$ larger.

## Appendix D Computational Performance

Table: Table 7: 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 ± s.d. over 30 epochs. Preprocessing time is the wall-clock time taken to load, preprocess, and store the whole dataset prior to training. Specifications of the hardware used to run these experiments are also shown here.

Table: Table 8: Computational performance of GRASS on LRGB datasets. Training time per epoch is shown as the mean ± s.d. over 30 epochs for Peptides-func and Peptides-struct, and over 10 epochs for PascalVOC-SP and COCO-SP. The definition of statistics are identical to that described in Table 7.

## Appendix E Experimental Setup

### E.1 Datasets

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

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

### E.2 Hyperparameters

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

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

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 6
presentation: 3
questions: The random-walk-based encoding technique bears a lot of similarity to the position / structural encodings in the context of graph transformer (e.g. random walk encoding in https://arxiv.org/abs/2110.07875). What are the key differences and similarity? How would you demonstrate the advantage of the proposed algorithm in light of those related works?
Since strategies like random walk encoding, random graph rewiring, and attention mechanisms are commonly employed in graph domains, the authors should emphasize the novelty of their framework.

It would be beneficial to explore how GRASS performs on other graph-related tasks, such as link prediction or edge classification. What would be the type of tasks where the proposed method would achieve an advantage?
soundness: 3
strengths: The motivation behind this paper is clear. The method justification is backed by evidence. 
Many types of baselines and ablation studies are considered when evaluating the model performance.
The design goals are clear.
summary: This paper proposes a random-walk-based approach to encode structural information, and rewire the graph accordingly, to enhance the performance of attention-based gnns.
weaknesses: A lot of baseline performance numbers in tables are missing. I'm not sure if there are issues with running these models with the baselines. 

There are many aspects that could affect model design for given graph data. For example, homophily / heterophily properties; sparsity; clustering properties etc. could result in different model performances across designs. It's not clear what would be the type of data where the proposed method can achieve improvements.

The algorithm description could benefit from more clarity.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: - See weaknesses.
- It seems like the recent work NeuralWalker has made significant improvements in comparison to prior baselines. Can you clarify its significance and similarities to your work?
- Can you clarify your procedure for hyper-parameters? Te recent work [1] suggests that many of the baselines for LRGB can be easily improved by simple hyper-parameter changes.
- What impact does the frequency of rewiring during training have on model performance and training stability? Have experiments been conducted on different rewiring frequencies to understand this effect?

[1] Where Did the Gap Go? Reassessing the Long-Range Graph Benchmark
soundness: 3
strengths: - The paper is well written and easy to follow.
- The integration of RRWP encoding, random rewiring, and attention tailored to graph-structured data offers a plausible approach to addressing oversquashing and underreaching in GNNs.
- The proposed D-RRWP variant is a computationally efficient alternative to traditional RRWP encoding, making GRASS more feasible for large graphs.
- The results on Pascal-VOC and COCO-SP seems promising.
summary: This paper introduces GRASS (Graph Attention with Stochastic Structures), a new GNN architecture combining three key elements: graph encoding through Relative Random Walk Probabilities (RRWP), random rewiring of graph structures, and a novel additive attention mechanism. GRASS aims to improve long-range dependencies and selective node aggregation. The authors demonstrate that GRASS outperforms baseline models across several benchmark datasets and supports scalable GNN performance.
weaknesses: - Limited experimentation: Although GRASS is designed for scalability, the paper acknowledges that scalability testing on large, real-world graphs is limited due to resource constraints. Without large dataset evaluations, the real-world applicability to large-scale graph datasets remains unclear. For the currently used datasets, the memory or scalability does not present significant concerns since they are graph-level tasks with a small number of average nodes per graph. For example, the benchmarks are standard in GNN research, yet additional evaluations on real-world applications (e.g., social networks or knowledge graphs) could provide more insight into practical applicability.
- The proposed attention mechanism in GRASS leverages additive attention with edge features to capture relationships uniquely tailored for graph structures. However, random walk encodings like RRWP and related techniques such as Personalized PageRank (PPR) are already established in the graph learning community, as are various graph rewiring methods. To strengthen the paper’s contribution, it would be helpful if the authors could clarify how their additive attention mechanism distinctly advances existing methods.

---

confidence: 3
contribution: 2
initial_rating: 6
presentation: 3
questions: * Have the authors seen [1], the edge attention scheme proposed by the authors looks similar to the model architecture used there. What is the difference between the proposed attention mechanism with the model architecture in [1]?
* What is the advantage of generating random regular graphs in the proposed way when each node can sample nodes from the whole graph without replacement in a simpler manner?
* Can the authors also present results for the attention mechanism part alone, adding encodings to an existing GNN model is possible most of the time so it would be valuable if Tables 1 and 2 contained results for variants of GRASS not including random rewiring and 
RRWP encoding.

[1] https://www.nature.com/articles/s41598-023-44224-1
soundness: 3
strengths: * Strong experimental results on various datasets.
* The paper is well written.
* Figures help communicate the ideas more clearly.
summary: The paper proposes combining random graph rewiring, RRWO encoding and a specially crafted additive attention mechanism. To improve the efficiency of RRWP encoding, the authors utilize the truncated eigen decomposition. The experimental results show favorable results for the proposed combination of the utilized techniques.
weaknesses: * Misses citation to [1], I think it should be discussed in related work and any similarities/difference should be made clear when it comes to the model architecture in [1] vs the author's proposed additive attention mechanism, which is claimed to be a novel contribution.

[1] https://www.nature.com/articles/s41598-023-44224-1

---

confidence: 4
contribution: 1
initial_rating: 3
presentation: 3
questions: The Random Rewiring module, which introduces random edges into the graph structure, raises a critical question: could this random addition disrupt the integrity of the original graph by introducing noise? This potential limitation warrants further investigation. 

The attention mechanism in GRASS is designed to aid in selective aggregation. However, it remains unclear whether this feature significantly enhances GRASS's performance on heterophilous graphs, where connected nodes often have different labels. Providing empirical results or case studies to demonstrate the mechanism's effectiveness in such settings would strengthen the evaluation and highlight the framework's adaptability to varied graph types.
soundness: 3
strengths: - The paper is well-structured and accessible, with a clear presentation of methods and results.
- GRASS demonstrates superior performance in several benchmark datasets.
summary: This paper introduces GRASS, a framework that leverages the strengths of Graph Neural Networks (GNNs) and Graph Transformers (GTs), enhanced by D-RRWP encoding, random regular graph rewiring, and additive graph attention. Experimental results indicate that GRASS achieves competitive performance across several datasets.
weaknesses: The framework builds upon established paradigms, leveraging techniques such as random walk encoding and random rewiring. Both techniques are recognized variants of prior methods [1][2], which raises questions about the extent of the framework's novelty. While this incorporation demonstrates methodological rigor, the contribution in terms of innovation appears constrained. It would be beneficial for the authors to clarify how their approach differs from or improves upon the methods in [1] and [2]. Are there specific aspects of their methodology or implementation that extend or address limitations in these prior works? Providing such explanations would strengthen the argument for the framework's originality.

In terms of performance, GRASS demonstrates marginal or minimal improvement on datasets like CLUSTER, Peptides-func, and Peptides-struct. The datasets used in the experiments are limited in scale and scope, primarily featuring small graphs with an average of 500 nodes per graph and focusing on domains such as molecular chemistry and computer vision. While these domains are valuable, the scope of evaluation is not comprehensive enough to fully assess the proposed GNN architecture. To address this limitation, the authors could extend their evaluation to larger and more diverse datasets, such as those in the OGB benchmark [3], which includes large-scale networks like ogbn-arxiv (citation) and ogbn-products (sales). Additionally, a justification for the choice of current datasets would help contextualize their experimental focus. If there are technical constraints that prevent evaluation on larger graphs, discussing these limitations could provide valuable insights into potential scalability challenges.

[1] Graph inductive biases in transformers without message passing.

[2] Exphormer: Sparse transformers for graphs.

[3] https://ogb.stanford.edu/

---

confidence: 4
contribution: 3
initial_rating: 5
presentation: 2
questions: - How does the model scale with larger datasets? Could you provide more empirical results to back the scalability claims?
- What motivated the choice of specific benchmark datasets? Were other datasets considered, particularly for tasks with very large graphs?
- Could you provide more details on the computational trade-offs of RRWP vs. D-RRWP?
soundness: 3
strengths: - **Novel combination**: The integration of RRWP encoding, random rewiring, and graph-tailored attention is innovative.
- **Performance**: The model shows strong results across multiple datasets, particularly in tasks requiring long-range dependencies.
- **Ablation studies**: Detailed ablation studies demonstrate the impact of each component on the overall model performance.
summary: This paper proposes **GRASS**, a novel Graph Neural Network (GNN) architecture that combines **random walk encoding**, **graph rewiring**, and a new **graph-tailored additive attention mechanism**. The model introduces **Relative Random Walk Probabilities (RRWP)** encoding, a decomposed variant (**D-RRWP**) for computational efficiency, and uses **random regular graph rewiring** to enhance long-range communication between nodes. The paper demonstrates improved performance on several benchmark datasets, including a 20.3% lower MAE in ZINC. Ablation studies are conducted to analyze the contribution of each model component.
weaknesses: - **Clarity in methodology**: The explanation of RRWP and D-RRWP is overly detailed, with an abundance of variable names and step-by-step descriptions. To improve readability, consider starting with a high-level description of the algorithm's purpose and overall process before diving into specifics. Highlight one or two core equations that encapsulate the main idea, and move the more detailed steps to an appendix or illustrate them in a diagram. This approach would make the explanation more accessible while still providing depth for those interested in the finer details.
- **Scalability concerns**: While the authors claim good scalability, there are no experiments to validate this on larger datasets. A more thorough exploration of scalability would improve the strength of the claims. Additionally, reporting runtime and memory usage as graph size increases could offer valuable insights. 
- **Dataset descriptions**: The datasets are not well-described, making it difficult for readers to understand the differences between them and why they were chosen. Including details such as the number of nodes and edges, task type, and dataset relevance to real-world applications would provide useful context. 
- **Table presentation**: Table 1 contains unnecessary whitespace and could be more concise. Streamlining the table to present data more effectively without wasted space should be considered.

Meta-review: This paper introduces GRASS, a Graph Neural Network (GNN) architecture that integrates Relative Random Walk Probabilities (RRWP) encoding, random regular graph rewiring, and a new graph-tailored additive attention mechanism. GRASS aims to enhance long-range dependencies and selective node aggregation in graph models. Experimental results demonstrate that GRASS outperforms baseline models across several benchmark datasets.

The paper is well-written and presents a clear motivation for combining RRWP encoding, random rewiring, and an additive attention mechanism. The integration of these elements is innovative and shows promise in addressing issues like oversquashing and underreaching in GNNs.

However, the technical novelty is somewhat limited, as it builds upon established techniques without sufficiently clarifying how it advances beyond existing works. Important citations and comparisons to closely related methods are missing or improperly cited, particularly concerning the structure of an attention layer and attention mechanisms and encoding strategies. The scalability claims are unvalidated due to limited experimentation on large-scale, real-world graphs, raising concerns about the model's applicability in practical settings.

Overall, based on the evaluations from reviewers, I recommend the acceptance of this paper. The authors are encouraged to improve the paper quality by consulting related survey papers to accurately identify the original sources of certain model components, highlighting the novel contributions over prior work, providing thorough comparisons and validating scalability on larger graphs.

Decision: Accept (Poster)