Greener GRASS: Enhancing GNNs with Encoding, Rewiring, and Attention
Authors: Tongzhou Liao
Barnabas Poczos
Venue: ICLR 2025 Poster (2025)
Keywords: graph neural networks
graph encoding
graph rewiring
attention mechanism
Primary area: learning on graphs and other geometries & topologies
TL;DR: We propose a novel GNN that achieves SOTA performance with random walk encoding, random rewiring, and a novel additive attention mechanism.

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 Graph Attention with Stochastic Structures (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.

Published as a conference paper at ICLR 2025
GREENER GRASS: ENHANCING GNNS WITH ENCODING, REWIRING, AND ATTENTION
Tongzhou Liao @
Barnabás Póczos
School of Computer Science Carnegie Mellon University Pittburgh, USA
School of Computer Science Carnegie Mellon University Pittsburgh, USA
ABSTRACT
Graph Neural Networks (GNNs) have become important tools for machine learn- ing on graph-structured data. In this paper, we explore the synergistic combi- nation of graph encoding. graph rewiring, and graph attention, by introducing Graph Attention with Stochastic Structures (GRASS), 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-structure data, Our empirical evaluations demon- strate that GRASS achieves sute-of-the-as performance on multiple benchmark datasets, including 20.3% reduction in mean absolute eттоr on the ZINC dataset.
INTRODUCTION
Graph Neural Networks (GNNs) have revolutionized machine learning tasks involving graph- structured data (Wu et al., 2020; Veličković, 2023). Various paradigms within GNNs offer dis- tinet advantages: message-passing neural networks (MPNNs) effectively leverage local graph struc- ture (Kipf and Welling, 2016) and are often complemented with graph rewiring techniques to mod- ify the graph's topology and facilitate message passing (Topping et al., 2021); Graph Transformers (GTs) incorporate attention mechanisms to capture global dependencies (Yun et al., 2019; Rampášek al., 2022) and can be enhanced by graph encoding methods that enrich node and edge features with structural information (Dwivedi et al., 2021; 2023).
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, ran- dom rewiring, and introduces novel additive attention mechanism designed for graph-structured data. We conduct a series of experiments on multiple benchmark datasets and perform ablation studies to rigorously assess the contribution of each component in 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 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 desirable properties of GNN and provide in- sights into how they contribute to the model's performance.
We provide empirical evidence through experiments and ablation studies that carefully se- lected combination of these components can lead to improved performance on multiple bench- mark 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.

---

Published as a conference paper at ICLR 2025
2
RELATED WORK
In this section, we summarize some of the previous work related to the main concepts of GRASS.
Message-Passingg Neural Networks. Message-Passing Neural Networks (MPNNs), such as Graph Convolutional Networks (GCNs) (Kipf and Welling, 2016), GraphSAGE (Hamilton et al., 2017), and Graph Isomorphism Networks (GIN) (Xu et al., 2018), 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-structure data (Ma et al., 2023).
Graph Rewiring, Graph rewiring techniques modify the topology of graphs to improve their con- nectivity, often leveraging spectral properties to guide the process (Topping et al., 2021; Arnaiz- Rodriguez et al., 2022). Rewiring improves MPNNs by alleviating issues in information propa- gation, such as underreaching, which occurs when distant nodes cannot communicate (Alon and Yahav, 2020). In this work, we explore form of random rewiring that superimposes random regular graph on the input graph.
Graph Transformers. Attention mechanisms (Vaswani et al., 2017) allow GNNs to weigh the importance of neighboring nodes during aggregation (Veličković et al., 2017). Graph Transformers (GTs), such as Graph Transformer Network (GTN) (Yun et al., 2019), extend this idea to global attention across nodes. GTs often inherit attention mechanisms designed for sequences, which may not be optimal for graphs (Chen al., 2024). Designing attention mechanisms specifically for graph-structure data is an active area of research, and we aim to contribute to it by proposing 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., 2023). Techniques such as Laplacian positional encodings (LapPE) (Dwivedi et al., 2021) and relative random walk probabilities (RRWP) encoding (Ma et al., 2023) incorporate structural information into node and edge features, enhancing GTs, which otherwise lack graph inductive bias (Ma et al., 2023). 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ášck et al., 2022) represents hybrid of MPNN and GT, merging the inductive bias of message passing with the global perspective of Transformers. Exphormer (Shirzad al., 2023) combines GTss and rewiring by adding random edges and supernodes, generalizing BigBird (Zaheer et al., 2020), 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 novel additive attention mechanism tailored for graphs. Although RRWP encoding and random rewiring have been explored separately (Ma et al., 2023; Shirzad al., 2023), 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-ar performance across a wide range of benchmark problems.
3 METHODS
In this section, we introduce the design GRASS. We begin by examining the desirable quali- ties of 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 (N7-N3) and edges (EI-E2) of the model.
NI. Permutation Equivariance. Unlike tokens in sentence pixels in image, nodes in graph are unordered, and therefore the model should be permutation equivariant by construction. Since reordering the nodes of graph does not change the graph, permuting the nodes of the
2

---

Published as a conference paper at ICLR 2025
Original Edge Representation
Training Loop
Atrention
Attention
Attention
Pooling
(Optinal)
Original Edge Embedding
(D-RRWP Encoding
Added Edge Representation
Input Graph
(D- DRRRRRPP
Random
GRASS Attention
Encoding
Rewiring
Layers
Distinct Embedding for Added Edges
(D-RRRW Encoding
Figure 1: The structure of GRASS. Prior training, GRASS precomputes (D-)RRWP encodings. At each training iteration, it rewires the input graph and adds distinct embeddings to added edges.
imput graph of GNN layer should only result in the same permutation of its output (Veličković, 2023). Formally, let f(x, E, A) be the function computed by layer, where X E [ represents node features with nodde dimensions, E I V|x X represents edge fea- tures with Redge dimensions, and A E (0, represents the adjacency matrix (edge weights are considered scalar-valued edge features). If the layer permutation equivariant and (Xout, Eour) = fXin, Ein, A), then (PXour, PE f (PP PE .PAPT) for an arbitrary permutation matrix 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., 2022). However, MPNN layers, which propagate information locally, frequently fail in this regard (Ma et al., 2023). A major challenge underreaching, where an MPNN with / layers is incapable of supporting communication between two nodes i. with (Alon and Yahav, 2020). Another challenge is oversquashing, where the structure of the graph forces information from large set of nodes to squeeze through a small set of nodes to reach target (Topping et al., 2021). 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 deep MPNNs (Alon and Yahav, 2020).
distance 8(i.)) .)
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ć, 2023). In deep models, this can lead to oversmoothing, where the representation of nodes becomes too similar to be ef- fectively classified in the process of repeated aggregation (Chen et al., 2020). Therefore, when required by the task, nodes should aggregate information from relevant neighbors only, instead of doing so unconditionally, order to maintain distinguishability of node representations.
El. Relationship Representation The model should effectively represent the relationships be- tween nodes with edges. Edges in graph-structured data often convey meaningful information about the relationship between the nodes they connect (Gong and Cheng. 2019). addition to the semantic relationships represented by edge features of the input graph, structural rela- tionships can be represented by edge encodings added by the model (Rampášek et al., 2022). 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 di- rected (Rossi al., 2024). Although edge directionality has been shown to carry important information for various tasks, many GNN variants require undirected graphs as input, to pre- vent edge directions from restricting information flow (Rossi et al., 2024). It would be benefi- cial for the model's expressivity if edge directionality information could be preserved without severely limiting communication.
The Structure of GRASS. The high-level structure GRASS 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 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 single output vector.
output graph with the same
3

---

Published as a conference paper at ICLR 2025
3.1 GRAPH ENCODING
Extracting structural information plays an important role in graph-structured learning and is crucial for Relationship Representation. To this end, apply relative random walk probabilities (RRWP) encoding (Ma et al., 2023) 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., 2023), serving as major source of structural information for the model. To calculate random walk probabilities, we first obtain the transition matrix T, where T, represents the probability of moving from node node j in a random walk step. defined as T = D-1A E [0, 1]IVixÍVI where A (0, 1)IVIxIV] the adjacency matrix of the input graph G. and D E NIVIXIV is its degree matrix, a diagonal matrix. The powers of T are stacked to form the RRWP tensor P. with Pa.i,j representing the probability that a random walker who starts at node lands at node j at the hith step. Formally, P (T, T T T [0, 1] where k is the number of random walk steps. The diagonal elements P. where i E Va, are used as node encodings, similarly to RWSE (Dwivedi et al., 2021). The rest are used as edge encodings when the corresponding edge is present in the rewired graph H. All node and edge encodings undergo batch normalization (BN) (loffe and Szegedy, 2015). Here, W denotes trainable weights, n denotes the dimensionality of hidden layers, and denotes concatenation.
RW
W node enc BN (.,,s) E IR"
RW W edge (N((...) :.. P..aa) ER"
(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 accom- panied by degree information (Ying et al., 2021). Here, dt dl((i) and d (i) denote the out-degree and in-degree of node i, respectively.
x = in
RW + X,
+ Waeg BN (1) d (T) ER",
(3)
c c.. + CiJ E R".
in
RW
(4)
Improving Efficiency. RRWP encodings take OK time to compute and ((} space to store (Ma et al., 2023). On extremely large graphs, this could be computationally prohibitive even when computed once per dataset. We propose D-RRWP, decomposed variant of RRWP. Instead of computing the exact random walk probabilities P from the transition matrix T, we approximate it with its truncated eigendecomposition to reduce the complexity ((km( V + [E')) time and (((k+m))VV V| El)") space, where m < V is the number of cigenpairs used for the approximation.
To ensure that the transition matrix is diagonalizable, we replace T with T sym = AD
which is always diagonalizable A is a symmetric adjacency matrix-thh of an undirected graph. Given the degree matrix D. this modification does not result in loss of information, because Taym = D TD 1, Since Tyym is diagonalizable, its truncated cigendecomposition coincides with its truncated singular value decomposition (SVD), which provides the optimal low-rank approxima- tion of the matrix (Eckart and Young, 1936).
Let T sym QAQT T be the truncated eigendecomposition of T Taym- where À [-1, 1, 1| is diagonal matrix containing the m largest eigenvalues (in magnitude) of Taym and Q g hold the corresponding eigenvectors. Decomposing T takes ( El) time with the Lanczos algorithm (Lanczos, 1950; Lehoucq et al., 1998) and requires O(m VI) space. We approximate the h-th power of T sym: i.e. the random walk probabilities P PAiis = (Th (Thy Symmi.g. by computing (I (T = (QÂ* )as = (Q., O Q diag(AA) Here, @ denotes the Hadamard product. Computing this approximation for all nodes (i, i), edges (i.j), and random walk steps S h S requires ( + [E)) time and O(K(V]] + E))) space. This is efficient because raising the diagonal matrix A to the powers 1 to k only costs Okk)) time and space. If T T.ym were not diago- nalizable and we had to use SVD instead, efficient power computation would no longer be possible.
Since A h can take at most m linearly independent values as we vary h, increasing & beyond m does not add additional information to the encoding. Consequently, we fix k in our experiments.
4

---

Published as a conference paper at ICLR 2025
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. (2023) uses a similar technique in generalizing BigBird (Zaheer et al., 2020) 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., 1989) that we describe here and with pseudocode in Appendix A.2. For a given positive, even parameter r 2 2, and for the input graph G (Vg, Eg), we randomly generate a corresponding r-regular graph by independently and uniformly sampling ğ random permutations ..., og & from Svcl. the symmetric group defined over the nodes of the graph G. Using these σ1, .2.., random permutations, we construct a random pseudograph R = (Va: Fejd, where the edge set Fi of the graph R is
RR
U
(
(5)
iEVo.
Here, denotes the disjoint union of sets. The resulting graph Rt is a random regular pseudograph, and the probability that R is any given regular pseudograph with [Val nodes and degree r is uni- form (Friedman et al., 1989).
Being a pseudograph, R might not be simple-it might contain self-loops and multi-edges. Even when |Vel large, the probability that R simple that does not contain self-loops or multi- edges woould not be prohibitively small. In particular, it has an asymptotically tight lower bound (Ellis, 2011)
lim Pr[ft is simple] = - Vall-oo
(6)
Therefore, if we regenerate i when it is not simple, the expected number of trials required for us to obtain a simple R upper-bounded by e which can be kept low by keeping r low. In practice, GRASS requires the superimposed graph to be simple to avoid passing duplicate messages. Mcanwhile, the regularity of the graph is desired but not strictly required. Therefore, when R is not simple, remove self-loops and multi-edges from R to obtain Rt which is always simple but not necessarily regular.
Our empirical results presented in Figure 4 and Table 3 suggest that small value of is often sufficient. our experiments, we use r S 6.
Rewiring the Input Graph. To rewire the input graph G, GRASS superimposes the edges of R on G. producing a new graph H = (Vg, Eg Li ER) that is used as input for subsequent stages of the model. Since it is possible that Eg n ER + Ø, there might be multi-edges in H, and in these cases, H is not 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 Eg are given a distinct embedding to distinguish them from the existing edges Eg. This aids Selective Aggregation, as allows a node to select between its neighbors and random node. The added edges also receive (D-)RRWP encodings to enhance Relationship Representation. Although an added edge (i. j) E ER lacks edge features that represent semantic relationships in the input graph, the structural relationship between nodes and j can be represented by the random walk probabilities P.... given to that edge as its (D-)RRWP encoding.
3.3 ATTENTION MECHANISM
Many GTs emulate the structure of Transformers designed for Euclidean data (Dwivedi and Bresson, 2020: Kreuzer et al., 2021: Ying et al., 2021; Hussain et al., 2022; Shirzad et al., 2023). Meanwhile, GRASS uses attentive node aggregators with attention scores computed by MLP edge aggregators, which is more tailored attention mechanism for graph-structured data. Figure 3 provides simple
5

---

Published as a conference paper at ICLR 2025
Softmax
(a)
(b)
(a)
(b)
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, Two among all possible instances of the randomly rewired graph H with 2. They have better connec- tivity than the input graph.
Figure 3: Simplified visualization of the GRASS attention mechanism. (a) The edge aggregator extracting node relations to update edge repre- sentations. (b) The attentive node aggregator weighted by edge representations. For simplicity, attention from a node to itself, residual connec- tions, and activation functions are omitted here. Figure 5 provides a more detailed visualization.
visualization, and Figure 5 illustrates its structure in detail. The GRASS attention mechanism is defined as follows, where N denotes in-neighbors, W denotes trainable weights, and denotes a small constant added for numerical stability. For simplicity, biases are not shown in these equations.
J = (exp W
amte odge 1-1) ER-
$/.
a EEEN-GYuDT Shi +
E
ER+".
(8)
x/ Wi mill
Σ
(Wl
Inile- head x
+ W
[ E R".
(9)
taile edge
()
2 W odgo
odge 2,5
W head
W til
RR"
(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 (Zhou et al., 2023). A directed edge an ordered pair of nodes, and an undirected edge can be represented by two directed edges with opposite directions. The orderedness of nodes connected by an edge allows us to use an MI.P as the edge 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 a.jj after applying linear layer and performing component-wee 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 's dependence on the presence of particular edges in the graph, facilitating Selective Aggregation. This can also be seen as generalization of DropKey (Li et al., 2022) to graphs, because it randomly masks the attention matrix prior to the softmax operation, unlike DropAttention (Zehui et al., 2019).
Edge Flipping, While the proposed attention mechanism naturally achieves Directionality Preser- vation by aggregating information the same direction as edges, can severely restrict the flow of information, putting it in conflict with Effective Communication. As a solution, the direction of each edge switched from one layer to the next: in odd-numbered layers, the directions match those of the edges in the rewired graph H. while in wven-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 ē/.,, the updated representation of edge j + i by using e the representation of edge i + j from the previous layer, effectively flipping the edge.
Ferd-Forward Network. Similar to Transformers, the output of the attention mechanism is passed through an FFN. Here, & denotes a ReLU-like (Nair and Hinton, 2010; Ramachandran et al., 2017) nonlinear activation function, which choose to be Mish (Misra, 2019).
X W! mode-out ob { + by boods--ee)) + b modd-ouu E IR"
(11)
% Wi
sdge-oot (0e e/
be Ddgo-ooc) be boggooott IR
(12)

---

Published as a conference paper at ICLR 2025
Table Performance on GNN Benchmark Datasets. The performance of GRASS shown here the mean + s.d. of 16 runs 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 al. (2023), Shirzad et al. (2023), and Chen et al. (2024). "-" indicates experiments not reported in these works.
ZINC
MNIST
CIFARTO
PATTERN
CLUSTER
Model
MAE
Accuracy
Accuracy f
Accuracy
Accuracy t
GCN
0.367 = 0.011
90.705 =
55.710 = 0.381
71882 0.334
68.498 = 0,976
GIN
0,526 +: 0.051
96.485 0.252
55.255 # 1,527
85.387
0.136
64.716 + 1.553
GAT
0.384 0.007
95.535 4 0.205
64.223 +: 0.455
78.271 0.186
70.587 # 0.447
GatedGCN
=
97.340
67.312 0.311
85.568 0.088
73.840 = 0.326
GaredGiN-LLSPE
0.090 = 0.001
PNA
0.004
0.12
70.35 = 0.63
DGN
0.168 0.003
72.838 + 0.417
86.680 0.034
GSN
0.101
CIN
CRaWI
0.085 0.004
97.944 0.050
69.013 #: 0.259
GIN-AK+
0.080 + 0.001
72.19 a: 0.13
86.850 0.057
SAN
0.139
76.691 + 0.63
Graphormer
0.122 0.006
K-Subgraph SAT
0.094 0.008
0.037 86.848
77.856 1.104
EGT
0.108 0.009
98.173 0.087
68.702 0.409
86.821 0.020
79.232 0.348
Graphormer- URPE
0.086 0.007
Graphormer-GD
0.081 + 0.009
GPS
0.070 = 0.004
72.298 + 0.356
86.685 0.059
78.016 + 0.180
Exphormer
98.55 + 0.039
74.69 0.125
86.74 + 0.015
78.07 0.037
GRIT
0.059 = 0.002
98.108 0.111
76.468 = 0.881
87.196 0.076
80.026 = 0.277
NelkalWalker
0.065 = 0.001
98.760 0.079
80.027 = 0.185
86.977 0.012
78.189 = 0.188
GRASS (ours)
0.047 = 0.001
98.932 0.076
83,750 # 0.141
89.177 0.313
79.541 + 0.173
Normalization and Residual Connection. We use post-normalization in residual connections, which has been shown to improve the expressiveness of Transformers (Liu et al., 2020). The residual connection scaled by a constant a to improve training stability (Wang et al., 2022).
x BN(x axx)= R",
(13)
d = BN(C + tcd,,) E R".
(14)
Graph Pooling. For graph-level tasks, graph pooling is required at the output of a GNN to pro- duce vector representation of each graph, capturing global properties relevant to the task (Wu al., 2020). GRASS employs sum pooling-a simple method as expressive as the Weisfeiler- Lehman graph isomorphism test (Leman and Weisfeiler, 1968) many more complicated pooling methods are not as expressive (Back et al., 2021). 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.
y
Σ KEVo
Σ
ets
Σ
E 3
(15)
(1.))E
(i.)EER
3.4 INTERPRETATIONS OF GRASS
Message Passing Perspective. GRASS is an MPNN on a noisy graph. In an MPNN, informa- tion is propagated along the edges of the input graph, defined by its adjacency matrix (Veličković, 2023). GRASS can be seen as MPNN that injects additive and multiplicative noise into the ad- jacency matrix, through random rewiring and random edge removal, respectively. The adjacency matrix A Am followed by message passing given by
Av (Aa + Ar) AA.
(16)
where AG is the adjacency matrix of the input graph G, AR is that the superimposed random reg- ular graph R, Ap is 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 denotes element-win wise AND. Noise injection is well known as effective regularizer (Noh et al., 2017), and for graph-structured data, the random removal of edges has demonstrated regularization effects (Rong et al., 2019).
7

---

Published as a conference paper at ICLR 2025
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. (2023), Tönshoff et al. (2023), Ma et al. (2023), Shirzad et al. (2023), and Chen et al. (2024). "_" indicates experiments not reported in these works. "These models are re-tuned by Tönshoff et al. (2023) to provide stronger baselines.
Peptides-tune
Peptides-struct
PascalVOC-SP
COCO-SP
Model
AP t
MAE 4
Macro F1
Macro F1
GCN'
0.6860 0.0050
0.2460 0.0007
0.2078 + 0.0031
0.1338 + 0.0007
GINE
0.6621 0.0067
0.2473
0.0017
0.2718 + 0.0054
0.2125 + 0.0009
GatedGCN"
0.6765 + 0.0047
0.2477
0.0009
0.3880 + 0.0040
0.2922 + 0.0018
DIGL+MPNN
0,6469 = 0.0019
0,3173 = 0.0007
0.2824 + 0.0039
DIGI=MMPNN+LapPE
0.6830 + 0.0026
0.2616 = 0.0018
0.2921 + 0.0038
MiX
0.6592 + 0.0036
0.2921 = 0.0023
0.2506 + 0.0133
MixHlop-GCN+LapPE
0.6843 0.0049
0.2614
0.2218 0.0174
DRew-GCN
0.6996 0.0076
0.2781 0.0028
0.1848 0.0107
DRew-GCN+LapPE
0,7150 0.0044
0.2536 = 0.0015
0.1851 + 0.0092
DRew-GIN
0.6940 = 0.0074
0.2799 = 0.0016
0,2719 + 0.0043
DRew-GIN+LapPE
0.7126 = 0,0045
112606=
0.2692 + 0.0059
DRew-GatedGGN
0.6733 = 0.0094
0.2699
0.3214 = 0.0021 0.0007
DRew.GaeedGCN+LappP
0.6977 0.0026
0.3314 + 0.0024
Transformer+-apPP
0.6326 0.0126
0,2694 0.0029
0.0098
0.2618 0.0031
SAN+LapPE
0.6384 0.0121
0.2683 = 0.0043
0.3230 0.0039
0.2592 + 0.0158
GPS+LapPE'
0.6534 0.0091
0.2509
0.0014
0.4440 0.0065
0.3884 + 0.0055
Exphormer
0.6527 0.0043
0,2481 0.0007
0.3975 + 0.0037
0.3455 + 0.0009
GRIT
0.6988 = 0.0082
0.2460 = 0.0012
NeuralWalker
0.7096 0.0078
0.2463 = 0.0005
0.4912 & 0.0042
0.4398 + 0.0033
GRASS (ours)
0.6737 0.0064
0,2459 = 0.0007
0.5670 = 0,0049
0,4752 = 0,0032
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ć, 2023) being
x
Φ
a(x;, xxx;,,))v((x) x))((()))) iEN(G)
(17)
where é and ve are neural networks, is attention weight function, and + is a permutation- invariant aggregator. Many GTs compute attention weights using scaled dot- dot-product atten- tion (Vaswani et al., 2017), with node features 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 MIP, could be used to directly compute attention weights as form of additive attention (Bah- danau et al., 2014). 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., 2022) or general- izing (Shirzad et al., 2023) BigBird's sparse dot-product attention. Meanwhile, GRASS achieves sparsity in 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 Am as defined in Equation 16, which contains (r + [El) nonzero elements.
4 EXPERIMENTS
4.1 BENCHMARKING GRASS
Experimental Setup. To measure the performance of GRASS, we train and evaluate on five of the GNN Benchmark Datasets (Dwivedi et al., 2023): ZINC, MNIST, CIFAR10, CLUSTER, and PATTERN, as well as four of the Long Range Graph Benchmark (LRGB) (Dwivedi et al., 2022) datasets:
fupee Peptides-struct, PaSCalVOC-SP, and COCO-SP. Following the experimental setup of Rampāšek et al. (2022) 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 F.I.
Due to the use of random rewiring, the output of the model is not deterministic. Therefore, 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 D-RRWWencoding
8

---

Published as a conference paper at ICLR 2025
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 each trained model. For comparison, the variance of model performance due to randomness in the training process is 1.79e-6.
# Added Edge per Node
6
12
Fully Connected
0.0480
0.0470
0.0484
0,1483
Regular
0.0557
1: 0.0019
0.0013
1 0.00018
0.0012
0.0492 # 0.0008
MAE 4
0.0021
0.0488
0.0486
0.0480
0.0475
Non-Regular
+ 0.0015
0,0002
# 0.0011
0.0021
7.60c-8
1.37e-7
L.7c-7
2.24c-7
Regular
Variance MAE Due to Random Rewiring
3.67c-8
# 1.00e-7
8.51e-8
# +ll1le-7
Deterministic
Deterministic
1.201e-
1.39e-7
1.63-7
9.94c.8
Non-Regular
-.2.3c-
* +.775e-8
1,19e-7
* 4.47c-8
1.81
1.95
2.02
2.19
Regular
Training Time per Epoch (S)
1.74
+.110
+0077
+.05
0.05
2.40
+: 0.02
1.75
1.87
2.00
2.20
0.03
Non-Regular
0.04
0007
0.03
0.00
Peak VRAM Consumption (MiB)
Regular
1911
2529
3051
3569
1415
4273
Non-Regular
1889
2489
3009
3511
on Peptides-func PascalVOC-SP and COCO-SP, and RRWP encoding other datasets. Models are trained with the Lion optimizer (Chen et al., 2023). Hyperparameters can be found in Appendix F.2.
Results. As shown in Tables and 2, GRASS ranks first on ZINC, MNIST, CIFAR10, PAT- TERN, Peptides-struct, PascalVOC-SP, and COCO-SP, while ranking second on CLUSTER and fifth on Peptides-fune, among the models compared. Notably, GRASS achieves 20.3%
0,054 0.05e
6,0557
Reguiar (MAE)
12000
Non-Regular (MAE)
(MAE)
10000
Peak VRAM Consumption (MIB)
Reguiar (Peak Consumption)
Nor-Regular iPeak VIAM Consumption)
Common (Peak VRAM Consumption)
5000
lower MAE on ZINC compared to GRIT (Ma et al., 2023), the second-best model, which has ((IV12) time and space complexity.
n.ace MAE
0.0488
0,0486
0.0484
0.0483
0.0492
6000
0,0470
0.0475
4000
3569:5511
19111899
2529
2006
4.2 ABLATION STUDY
1415
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., 2021), a widely used graph encoding technique. We examine the effects of random rewiring by varying the num- ber 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 with the attention mechanisms GAT (Veličković et al., 2017), GatedGCN (Bresson and Laurent, 2017), and Transformer (Vaswani et al., 2017), while keeping the rest of the model intact. These experiments are conducted on ZINC, a well-known GNN benchmark that represents tasks smaller graphs, and PascalVOC-SP, which represents tasks on larger graphs that require long-range interaction. Detailed results on PascalVOCCSP are presented in Appendix D. Additionally random edge removal, edge flipping, normalization, graph pooling, and the optimizer. Our find- ings suggest that the combination of (D-)RRWP encoding, random rewiring, and GRASS attention demonstrates superior effectiveness compared to alternative combinations on the evaluated datasets.
Fully Connected
Added Edges per Node
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.
ZINC, explore the impact of minor design choices, including
Random Walk Encoding. On both ZINC and PascalVOC-SS switching between RRWP and D- RRWP results in an insignificant change in performance: 0.64% on ZINC and 0.35% on PascalVOC: SP. Meanwhile, replacing D-RRWP with RRWP results in a 17.73 x larger preprocessed dataset on PascalVOC-SP. This highlights the viability of D-RRWP as an efficient replacement of RRWP on certain graphs, but we also notice that D-RRWP does not perform as well as RRWP on Peptides- struct. Replacing RRWP or D-RRWP with LapPE results in significant degradation of performance on ZINC, but a much smaller degradation on PascalVOC- indicating that the combination of LapPE with other components of GRASS is more dataset-dependent and generally not as effective.

---

Published as a conference paper at ICLR 2025
Table 4: Ablation study results for random rewiring, 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 runs. The implementations of replacement attention mechanisms are provided by PyTorch Geometric (Fey and Lenssen, 2019), and we adjust the head size to approach 500k parameters. 'The maximum number of Laplacian eigenvectors to use for LapPE on ZINC 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 cigenvectors 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.
Sctup GRASS
MAE
0,0470 0.0013
Rewire every epoch + Rewire once before training
0,0645 0.0015
RRWP (32 steps) + D-RRWP (32 eigenpairs. 32 steps)
0.0473 0.0021
RRWP (32 sleps) + LapPE (8 eigenvectors)
0.0829 0.0041
RRWP (32 steps) + Padded LapPE (32 cigenvectors)"
0.0879 0.0067
GRASS attention GAT attention (Veličković et al., 2017)
0.0592 = 0.0023
GRASS attention - GatedGCNN attention" (Bresson and Laurent, 201 7)
0.0651 0.0030
GRASS attention - Transforner atlention" (Vaswani el al., 2017)
0.0652 0.0016
No random edge removal
0.0500 0.0018
No edge tlipping
0.0470 0.0010
BN +
LN (Ba et al. 2016)
0.0497 0.0009
Sum pooling + Mcan pooling
0.0493 0.0024
Lion > AdamW (Loshchilov et al. 2017)
0.0499 0,0006
Random Rewiring. On both ZINC and PascalVOC-SP, the optimal number of added edges per node 6 when using random regular graphs, with any deviation from this value leading to degraded performance. On ZINC, replacing random regular graphs with non-regular random graphs requires adding more edges to achieve comparable performance, which in turn increases runtime and memory consumption. Moreover, fixing the added edges across epochs rather than resampling them every epoch results in 37.2% increase in MAE. These findings demonstrate that both the regularity and the randomness of the superimposed graphs are crucial for the model's efficiency and performance.
GRASS Attention. On both ZINC and VOC-SS replacing GRASS attention with alter- native attention mechanisms substantially degrades performance, by at least 26.0% on ZINC and 14.7% on PascalVOCC-S. This indicates that GRASS attention, our novel design, is vital compo- nent for GRASS to achieve its competitive performance.
Minor Design Decisions. None of the minor design decisions, when altered or removed, results a significant performance degradation on ZINC: an advantage at least 15.2% is maintained compared to GRIT, the second-best model. This verifies that the performance advantage of GRASS achieved mainly by the proposed combination of encoding, rewiring, and attention mechanism.
CONCLUSION
We have presented GRASS, novel GNN architecture that synergistically integrates (D-)RRWP encoding, random rewiring, and new graph-tailored additive attention mechanism. Our empirical evaluations show that GRASS achieves and often surpasses state-of-the-ar 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 large and sparse graphs. While evaluating GRASS extremely large graphs could provide additional insights, is beyond the scope of this work due to time constraints.
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 demon- strated in Table 3 and Table 6. In scenarios that strictly require deterministic output, the random number generator used for random rewiring needs to be made deterministic with respect to the input graph. For example, the random number generator be seeded with hash of the input graph.
10

---

Published as a conference paper at ICLR 2025
5.2 REPRODUCIBILITY
The source code of GRASS is available at https:/gjttubbboom///rrsmm/aaas
ACKNOWLEDGMENTS
This work is partially supported by the NSF Award 2307698. We sincerely thank Martin Ritzert, Danica Sutherland, Hamed Shirzad, Hanke Chen, Owen Li, and Liangyuan Chen for their valuable feedback.
REFERENCES
Uri Alon and Eran Yahav, On the bottleneck of graph neural networks and its practical implications. arXiv preprint (rXiv:2006.05005, 2020.
Adrian Aamaiz-Rodriguee Ahmed Begga, Francisco Escolano, and Nuria Oliver. Diffwire: Inductive graph rewiring via the lovasz bound. In The First Learning on Graphs Conference, 2022.
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprint arXiv: 16077.06554 2016.
Jinheon Baek, Minki Kang, and Sung Ju Hwang. Accurate learning of graph representations with graph multiset pooling. arXiv preprint arXiv:2102. 1533, 2021.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning align and translate. arXiv preprint arxiv::409.044 2014.
Mitchell Black, Zhengehao Wan, Amir Nayyeri, and Yusu Wang. Understanding oversquashing in gnns through the lens of effective resistance. In International Conference on Machine Learning, pages 2528-228252222 2547. PMLR, 2023.
Béla Bollobás and W Fernandez de la Vega. The diameter of random regular graphs. Combinatorica, 2:125-134, 1982.
Xavier Bresson and Thomas Laurent. Residual
gated
graph convnets.
arXiv preprint
arXiv: 2017.
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.
Dexiong Chen, Till Hendrik Schulz, and Karsten Borgwardt. Learning long range dependencies on graphs via random walks. arXiv preprint arXiv:2406.03386, 2024.
Xiangning Chen, Chen Liang, Da Huang, Esteban Real, Kaiyuan Wang, Yao Liu, Hieu Pham, Xu- anyi Dong, Thang Luong, Cho-Jui Hsieh, et al. Symbolic discovery optimization algorithms. arXiv preprint 202.v:230..06675. 2023.
Yann N Dauphin, Angela Fan, Michael Auli, and David Grangier. Language modeling with gated convolutional networks. In International conference on machine learning, pages 933-941. PMLR, 2017.
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks graphs. arXiv preprint arXiv:2012.09699 2020.
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:2/ 10.07875. 2021.
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.

---

Published as a conference paper at ICLR 2025
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.
Carl Eckart and Gale Young. The approximation of one matrix by another of lower rank. Psychome- trika, ((3):211-235) 1936.
Wendy Ellens, Floske M Spieksma, Piet Van Mieghem, Almerima Jamakovic, and Robert Kooij. Effective graph resistance. Lineur algebru and its applications, 435(10):2491-2506 2011.
David Ellis. The expansion of random regular graphs. Lecture Notes, Lent, 34, 2011.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric.
arXiv preprint 1r0iv 1903.0248, 2019.
Joel Friedman, Jeff Kahn, and Endre Szemeredi. On the second eigenvalue of random regular graphs. In Proceedings of the twenty-first annual ACM symposium Theory of computing, pages 587- 598, 1989.
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 921 1 1-1219, 2019.
Frank Göring. Short proof of menger's theorem. Discrete Mathematics, 219 2000.
Benjamin Gutteridge, Xiaowen Dong, Michael M Bronstein, and Francesco Di Giovanni. Drew: Dy- namically rewired message passing with delay. In International Conference on Machine Learning, pages 12252-12267. PMLR, 2023.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Md Shamim Hussain, Mohammed Zaki, and Dharmashankar Subramanian. Global self-attention as a replacement for graph convolution. Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 655-665, 2022.
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.
Kedar Karhadkar, Pradeep Kr Banerjee, and Guido Montúfar. Fosr: First-order spectral rewiring for addressing oversquashing in gnns. arXiv preprint arXhv:2210.11790 2022.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net-
works. arXiv preprint arXiv: wwt.:/.09000000 2016.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Re- thinking graph transformers with spectral attention. Advances in Neural Information Processing Systems,
2021.
Corellis Lanezos. An iteration method for the solution of the eigenvalue problem of linear differ- ential and integral operators. 1950.
Richard B Lehoucq, Danny C Sorensen, and Chao Yang. ARPACK users' guide: solution of large- scale eigenvalue problems with implicitly restarted Arnoldi methods. SIAM, 1998.
AA Leman and Boris Weisfeiler. A reduction of a graph to canonical form and an algebra arising during this reduction. Mauchhoo-Tehhiicessee Informatsiya, 129): 1968.
Bonan Li, Yinhan Hu, Xuecheng Nie, Congying Han, Xiangjian Jiang, Tiande Guo, and Luoqi Liu. Dropkey, arXiv preprint arXiv:2208. 02646, 2022.
Liyuan Liu, Xiaodong Liu, Jianfeng Gao, Weizhu Chen, and Jiawei Han. Understanding the diffi- culty of training transformers. arXiv preprint arXiv:2004.08244 08249, 2020.
12

---

Published as a conference paper at ICLR 2025
Iyy Loshchilov, Frank Hutter, et al. Fixing weight decay regularization in adam. arXiv preprint arXiv:1711.05101, 5, 2017.
JF Lutzeyer and AT Walden. Comparing graph spectra of adjacency and laplacian matrices. arXiv preprint 1rXiv:1712.037665 2017.
Liheng Ma, Chen Lin, Derek Lim, Adriana Romero-Soriang Puneet K. Dokamia, Mark Coates, Philip Torr and Ser-Nam Lim. Graph inductive biases in transformers without message passing. arXiv preprint arXiv:2305. /7589, 2023.
Diganta Misra. Mish: A self regularized non-monotonic activation function. arXiv preprint 0rXiv:1908.08660 2019.
Vinod Nair and Geoffrey E Hinton. Rectified linear units improve restricted boltzmann machines. In Proceedings of the 27th international conference machine learning (ICML-10), pages 807- 144, 2010.
Hyconwoo 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.
Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look at the evaluation of gnns under heterophily: Are we really making progress? arXiv preprint ar Xrxiv:2302. /640, 2023.
Doron Puder. Expansion of random graphs: New proofs, new results. Inventiones mathematicae, 201(3):845-908. 2015.
Prajit Ramachandran, Barret Zoph, and Quoe V Le. Searching for activation functions. arXiv preprint arXiv:1710.0594/ 2017.
Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 15:14501--45155 2022.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. arXiv preprint 1907 2019.
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.
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.
Jan Tönshoff, Martin Ritzert, Eran Rosenbluth, and Martin Grohe. Where did the gap go? reassess- ing the long-range graph benchmark. arXiv preprint arXiv:2309,00367, 2023.
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 1rXiv:2/11.1455 2021.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Fukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural informa- fion processing systems, 30, 2017.
Petar Veličković. Everything is connected: Graph neural networks. Current Opinion in Structural Biology, 79:102538, 2023.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 10903, 2017.
Hongyu Wang, Shuming Ma, Li Dong, Shaohan Huang, Dongdong Zhang, and Furu Wei. Deepnet: Scaling transformers 1,000 layers. arXiv preprint orXiv:2203.00555 2022.
13

---

Published as a conference paper at ICLR 2025
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.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? arXiv preprint 1rXiv:1810.00826, 2018.
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 Neural Information Processing Systems, 34:28877-28888. 2021.
Seongjun Yun, Minbyul Jeong, Raehyun Kim, Jaewoo Kang, and Hyunwoo J Kim. Graph trans- former networks. Advances in neural information processing systems, 32, 2019.
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:17283112297, 2020.
Lin Zehui, Pengfei Liu, Luyao Huang. Junkun Chen, Xipeng Qiu, and Xuanjing Huang. Dropat- tention: regularization method for fully-connected self-attention networks. arXiv preprint arXiv:1907.1105,, 2019.
Yuchen Zhou, Hongtao Huo, Zhiwen Hou, Lingbin Bu, Jingyi Mao, Yifan Wang, Xiaojun Lv, and Fanliang Bu. Co-embedding of edges and nodes with deep graph convolutional neural networks. Scientific Reports, 13(1):16966, 2023.
14

---

Published as a conference paper at ICLR 2025
A RANDOM REWIRING
A.1 MOTIVATIONS FOR SUPERIMPOSING RANDOM REGULAR GRAPIS
Effects on Diameter. The diameter of graph upper-bounds the distance between nodes, and thus the number of layers for an MPNN to propagate information between them (Alon and Yahav, 2020). Superimposing random regular graph on the input graph can drastically decrease its diameter. The least integer that satisfies
(r (r- (2 (2r log [V]
(18)
the upper bound of the diameter of almost every random r-regular graph with [V] nodes, where r 2 3 and > O (Bollobás and Fernandez de la Vega, 1982). Since adding edges to a graph never increases its diameter, the diameter of the rewired graph is asymptotically upper-bounded by d E Ologg, [V]) when 2 3. Subsequently, all nodes would be able to communicate with each other given Ologg, [VI) message passing layers, which could significantly reduce the risk of underreaching large graphs. In addition, the diameter of graph is trivial upper bound of its effective resistance (Ellens et al., 2011), 1). which has been shown to be positively associated with oversquashing (Black et al., 2023). Intuitivelyy it upper bounds the "length" of the bottleneck through which messages are passed.
Effects on Internally Disjoint Paths. Since oversquashing can be attributed squeezing too many messages through the fixed-size feature vector of node (Alon and Yahav, 2020), increasing the number of internally disjoint paths between information to propagate through more nodes in parallel. Intuitively, it increases the "width" of the bottleneck. random r-regular graph with r almost certainly has vertex connectivity of as V - oo (Ellis, 2011). Menger's Theorem then lower-bounds the number of internally disjoint paths by a graph's 'ss vertex connectivity (Göring, 2000).
nodes may reduce oversquashing by allowing
Effects Spectral Gap. Oversquashing has been shown to decrease the spectral gap of graph increases, which defined as Å₁ the smallest positive cigenvalue of the graph's s Laplacian matrix (Karhadkar et al., 2022). It has been proven that random r-regular graph sampled uniformly from the set of all r-regular graphs with [V] nodes almost certainly has < 2/r - + as [V] co, where μ the largest absolute value of nontrivial eigenvalues of its adjacency matrix (Puder, 2015). Since the graph is r-regular, its i-th adjacency matrix eigenvalue μu, and i-th Laplacian matrix eigenvalue A satisfy À with X r - 2 11
μ4 (Lutzeyer and Walden, 2017), lower-bounding the spectral gap
A.2 PSEUDOCODE OF THE PERMUTATION MODEL
Algorithm The Permutation Model (Friedman et al., 1989)
1: procedure PERMUTATIONMODELGG (V)
2: -- 2D array of size (r, [V])
3: for + t r- do
4: a[i,:] < (AN) > Random permutation of integers between 0 and [V]
5: end for
6:
A Array of size [V|
Create empty adjacency list
7:
for j + 0 to V do
8:
for + to do
9:
A k] + [kk
b Add an edge to the adjacency list
end for end for
11:
12:
A + REMOVESELFLLOOP(4)
Remove self-loops from the adjacency list
13:
A + REMOVEMULTIEDGE(A1)
> Remove multi-edges from the adjacency list
14: return
15: end procedure
15

---

Published as a conference paper at ICLR 2025
B GRASS ATTENTION
jefy N 9
Edge Flipping
BN
BN
Σ
Xa
Xa
W mods-out
Softmax
W eilowent
Activation
Dropout
Activation
W
W
W
W
W
W
Wi
bele-bal
odger tad
odger head
fill edgt
actar odge
edge odge
[x e XD)
(EUU
Figure 5: The structure of attention layer of GRASS. Node aggregation attentive, with attention weights derived from edge representations. Edge aggregation is done through an MLP. For simplic- ity, biases are shown here.
C RESULTS ON HETEROPHILIC GRAPHS
Although tackling heterophily is not the main focus of this work, we have benchmarked GRASS on roman-empire (Platonov et al., 2023), heterophilic graph, with results shown in Table 5. The experimental setup is identical to that described in Section 4.1, and hyperparameters can be found in Appendix F.2.
Table 5: Performance the roman-empire dataset. The performance GRASS shown here the mean + s.d. of 8 runs. The best and second-bess results are highlighted. Performance numbers other than that of GRASS are adapted from Chen et al. (2024).
roman-empire Accuracy t
Model
GCN
73.69 0.74
GAT (-sep)
88.75 0.41
GPS
82,00 0.61
NAGphormer
74.34 0.77
Exphormer
89.03 0.37
Polynormer
92.55 + 0.37
Walkel
92.92 0.36
GRASS (ours)
91.34 + 0.22
16

---

Published as a conference paper at ICLR 2025
D ADDITIONAL ABLATION STUDY RESULTS
Table Ablation study results for the number of added edges per node PascalVOC-SP. Reported values, except peak VRAM consumption, are the mean + s.d. over 8 runs. The experimental setup identical that described in Table 3. For comparison, the variance of model performance due to
randomness in the training process is 2.36e-5.
# Added Edge Node
0
3
6
9
12
0.4430
0.5606
0.5670
0.5612
0.5619
Macro Fl f
1: 0.0105
0.0102
+ 0.0049
+ 0.0056
+ 0.0075
Variance in Macro F1
3,40e-6
2.86e-6
2.27e-6
2.54e-6
Deterministic
Due Random Rewiring
2.122e-6
8.51e--
9.32e--7
1.37e-6
Training Time
13.66
29.55
42.96
56.31
69.87
per Epoch (s)
0.07
+ 0.16
0.09
0.16
0.28
Peak VRAM (MiB)
8525
14191
19893
25591
31231
Table 7: Ablation study results for graph encoding, graph rewiring, and attention mechanism on PascalVOC-SP. This table shows the performance each ablated model as the mean s.d. over runs. The experimental setup is identical to that described in Table 4. "Using RRWP encoding with 128 random walk steps would result in out-of-memory 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 x larger.
Setu
Macro f
GRASS
0.5670 + 0.0049
D-RRWP (128 eigenpairs. 128 steps) RRWP (32 steps)*
0.5690 0.0045
D-RRWP (128 eigenpairs. 128 steps) - LapPE (128 eigenvectors)
0,5387 + 0.0070
Random regular rewiring Random non-regular rewiring
0.5622 + 0.0081
GRASS attention + GAT attention (Velččkovid ct al., 2017)
0,4663 = 0:0079
GRASS attention + GatedGCN attention" (Bresson and Laurent, 2017)
0.4414 0.0075
GRASS attention + Transformer attention' (Vaswani al., 2017)
0.4835 + 0.0062
E COMPUTATIONAL PERFORMANCE
Table 8: Computational performance of GRASS 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 load, preprocess, and store the whole dataset prior to training. Specifications of the hardware used to run these experiments are also shown here.
Dataset
ZINC
MNIST
CIFARIO
PATTERN
CLUSTER
Training Time per Epoch (s)
1.87 = 0.07
11.83 0.21
15.56 0.10
00.05
00.03
Preprocessing Time
25s
Im ls
1m 32s
33s
27s
Model Compilation Activation Checkpointing
Yes No
CPU
AMD Ryzen 9 9950X NVIDIA RTX A6000 Ada
GPU
Table 9: Computational performance of GRASS on LRGB datasets. Training time per epoch is shown 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 Ta- ble 8.
Dataset
Peptides-func
Peptides-struct
VOC-SS
COCO-SP
Training Time per Epoch (8)
6.19 + 0.30
5,90 = 0.03 Im 32s
42.96 0.09
539,50 = 0.32
Preprocessing Time
1m 10s
3m 58s
19m 49s
Model Compilation
Yes
Yes
Activation Checkpointing
No
Yes
CPU
AMD Ryzen 9 9950X
GPU
NVIDIA RTX A6000 Ada
17

---

Published as a conference paper at ICLR 2025
F EXPERIMENTAL SETUP
F.1 DATASETS
Table 10: Statistics of GNN Benchmark Datasets, adapted from Rampášek et al. (2022).
Dutasct
Gruphs
Avg. # Nodes
Avg. Edges
Directionality
Task
Metric
ZINC
12000
23.2
24.9
Undirected
Graph Regression
MAE 4
MIIST
70000
70.6
564.5
Directed
Graph Classification
Accuracy
CIFARIO
60000
117.6
941.1
Directed
Graph Classification
Accuracy
PATTERN
14000
3039.3
Undirected
Node Classification
Accuracy
CLUSTER
12000
117.2
2150.9
Undirected
Node Classification
Accuracy
Table 11: Statistics of LRGB datasets, adapted from Dwivedi et al. (2022).
Dalaset
P Graphs
Avg. Nodess
Fdlges
Avg. Short. Path
Diameler
Task
Matric
Peptides- lune
15535
150.94
307.30
20.89 2 9.79
56.99 a: 28.72
Graph Classiliation
APT
Peptides-struct
15535
150.94
307.30
9.79
$6.99 28.72
Graph Regression
MAE
PascaVVOC-SP
11355
479.40
2710.48
10.74 2 0.51
27.62 a 2.13
Node Clasification
Macro Fl
Classification
F.2 HYPERPARAMETERS
Table 12: Model hyperparameters for experiments on GNN Benchmark Datasets. Hidden layers of
the task head, if any, use the GLU activation function (Dauphin et al., 2017).
Model
ZINC
MNIST
CIFARIO
PATTERN
CLUSTER
#1 Parameters
496545
103690
103738
495298
495558
# 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
50
Warmup Epoch Ratio
0.1
0.05
0.1
0.1
0.1
Batch Size
200
200
200
200
200
Initial Learning Rate
le-7
le-7
le-7
le-7
1e-7
Peak Learning Rate
5c-4
1c-3
1e-3
1c-3
lc-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.5
0.3
0.3
3.0
0.3
Label Smoothing Factor
N/A (Regression)
0.1
0.1
0.1
0.1
Residual Connection Scale
0.2
0.4
0.4
0,2
0.2
Random Walk Encoding Type
RRWP 32
RRWP
RRWP
RRWP
RRWP
(D-JRRWP Random Walk Length
24
24
32
32
Random Regular Graph Degree
6
6
6
6
Random Edge Removal Rate
0.1
0.1
0.1
0.5
0.5
Table 13: Model hyperparameters for experiments on LRGB datasets and the roman-empire dataset. Hidden layers of the task head, if any, the GLU activation function (Dauphin al., 2017). "This dataset consists of single graph.
Model
Peptides-func
Peptides-struct
VOCCSI
COCO-SP
roman-cmpire
Paramneters
500074
498315
501493
499377
2075730
Attention Layers
$3
24
Attention Layer Dim.
32
32
32
32
96
Task Head Hidden Dim.
192
192
N/A (Linear)
N/A (Linear)
N/A (Linear)
Epochs
500
500
500
100
4000
Warmup Epoch Ratio
0.1
Batch Size
200
Initial Learning Rate
Ic-7
Ic-7
Ic-7
Ic-7
1c-7
Peak Learning Rate
le-3
le-3
le-3
le:3
le-3
Final Learning Rate
le-7
le-7
1e-7
le-7
le-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
1.0
Lahel Smoothing Factor
(Regression)
0.1
Residual Connection Scale
0.2
0.2
0.2
0.2
0.3
Random Walk Encoding Type
D-RRWP
RRWP
D-RRWP
D-RRWP
D-RRWP
(D-)RRWP Random Walk Length
128
64
128
64
256
Random Regular Graph Degree
Random Edge Removal Rate
18


Reviews:
[{"review_id": "k1A3T3mAHt", "reviewer": "Reviewer_eNkJ", "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.", "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?\nSince 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.\n\nIt 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?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The motivation behind this paper is clear. The method justification is backed by evidence. \nMany types of baselines and ablation studies are considered when evaluating the model performance.\nThe design goals are clear.", "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. \n\nThere 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.\n\nThe algorithm description could benefit from more clarity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BAmhcokNDP", "reviewer": "Reviewer_budq", "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.", "questions": "- See weaknesses.\n- 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?\n- 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.\n- 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?\n\n[1] Where Did the Gap Go? Reassessing the Long-Range Graph Benchmark", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is well written and easy to follow.\n- 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.\n- The proposed D-RRWP variant is a computationally efficient alternative to traditional RRWP encoding, making GRASS more feasible for large graphs.\n- The results on Pascal-VOC and COCO-SP seems promising.", "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.\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lUbf55piTC", "reviewer": "Reviewer_2g6k", "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.", "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]?\n* 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?\n* 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 \nRRWP encoding.\n\n[1] https://www.nature.com/articles/s41598-023-44224-1", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* Strong experimental results on various datasets.\n* The paper is well written.\n* Figures help communicate the ideas more clearly.", "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.\n\n[1] https://www.nature.com/articles/s41598-023-44224-1", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5tDnz8LWFx", "reviewer": "Reviewer_z9x9", "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.", "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. \n\nThe 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.", "limitations": "", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 1, "strengths": "- The paper is well-structured and accessible, with a clear presentation of methods and results.\n- GRASS demonstrates superior performance in several benchmark 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.\n\nIn 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.\n\n[1] Graph inductive biases in transformers without message passing.\n\n[2] Exphormer: Sparse transformers for graphs.\n\n[3] https://ogb.stanford.edu/", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JB7FDlqTiX", "reviewer": "Reviewer_K5Pp", "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.", "questions": "- How does the model scale with larger datasets? Could you provide more empirical results to back the scalability claims?\n- What motivated the choice of specific benchmark datasets? Were other datasets considered, particularly for tasks with very large graphs?\n- Could you provide more details on the computational trade-offs of RRWP vs. D-RRWP?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- **Novel combination**: The integration of RRWP encoding, random rewiring, and graph-tailored attention is innovative.\n- **Performance**: The model shows strong results across multiple datasets, particularly in tasks requiring long-range dependencies.\n- **Ablation studies**: Detailed ablation studies demonstrate the impact of each component on the overall model performance.", "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.\n- **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. \n- **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. \n- **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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)