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

• 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.

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/

• 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.

• 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

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.