Summary
The authors of the paper proposed a non-convolution based approach to solve graph learning tasks using random walks and recurrent neural networks (RNNs), namely a random walk neural network with unifying memory (RUM). Random walks, together with the “anonymous experiment” function, allow to extract topological and semantic information from the graph, while an RNN and a feed-forward neural network take care of “unifying” the features collected from the walks. Research questions on the ability of the model to be more expressive than classical GNNs and to reduce oversmoothing and oversquashing have been answered positively both theoretically and experimentally. The experimental section, along with the appendix section, presents several experiments, ablation studies, training details, and theorem proofs. The code is available.
Strengths
Originality: Novelty is fair/good. The proposed approach can be considered original by choosing to propose a model that does not use the graph convolution operator at all, which is the most widely used approach in the state of the art. In this way, it alleviates the problems associated with convolutions (e.g., oversmoothing, oversquashing) while maintaining or even improving performance. Random walks and RNNs (more specifically GRUs) are not new methodologies, but they are combined in an original way on graph learning.
Quality: The quality of the proposed paper is good. The claims and solutions are technically sound. They present theoretical and experimental proofs of their proposed approach.
Clarity: The clarity of the paper is good. It is well written and organized. The best results in the tables should be in bold or more visible.
Significance: The significance of the paper is medium-high. They proposed an effective method to avoid convolutions in GNNs that effectively outperforms and competes with SOTA methodologies.
Weaknesses
Weakness: The paper lacks a discussion on the proposed method and Graph Transformer architectures. Although they are present in the experimental comparisons on the node classification task in Table 9, Graph Transformer is actually a well-known solution that does not rely on convolutions and can mitigate the over-squashing and oversmoothing problems [1,2]; the discussion should also considering the different computational costs of the two approaches.
Ref.
[1] "Attending to Graph Transformers", Luis Müller and Mikhail Galkin and Christopher Morris and Ladislav Rampášek, 2024, https://arxiv.org/abs/2302.04181
[2] "Do Transformers Really Perform Bad for Graph Representation?", Chengxuan Ying et. al., 2021, https://arxiv.org/abs/2106.05234
Questions
1) At Table.5, showing Graph Regression comparisons on ESOL, FreeSolv and Lipophilicity datasets, it seems to me that for the MoleculeNet [1] benchmark you used the results presented in their papers about the XGBoost model (best performing among
conventional methods) with (0.99, 1.74, 0.799) RMSE scores, respectively to the three datasets, instead using them from the best performing graph-based methods which are (0.58,1.15) for ESOL and FreeSolv datasets by using the MPNN model and 0.655 for Lipophilicity dataset by using GC model, which are the best models in these datasets. This is in contrast on what you said in the caption of Table. 5, since those presented are not the best results and models of [1].
Ref.
[1] "MoleculeNet: a benchmark for molecular machine learning", Wu, Zhenqin and et. al., "Chem. Sci.",2018, doi:10.1039/C7SC02664A, url:http://dx.doi.org/10.1039/C7SC02664A
Limitations
The authors have adequately discussed the potential negative societal impact and the current limitations of their work.