Thank you, Reviewer jBUd, for your thoughtful and constructive review. We also thank you for highlighting the theoretical and empirical benefits. We hope that the following points address your concerns.

Comparison with state-of-the-art models.

Empirically, the gains with RUM are marginal and in some cases, RUM is worse than the baselines.

In line 243, the author claims that RUM almost always outperforms SOTA architectures, this is not true according to the results.

Among the 8 tables totaling 21 benchmark experiments and more than 100 comparisons, the only cases where RUM is not state-of-the-art by a confidence interval are:

• In Table 2, Computers dataset and Table 3, NCI1 dataset. As discussed in sections On sparsity and Limitations, RUM faces challenges on very dense graphs.
• In Appendix Table 8, GNNs specifically designed for large graphs outperform RUM, which works out-of-the-box for both large and small datasets with high efficiency and a modest memory footprint, and is naturally compatible with sub-graph mini-batches.
• In Table 4, RUM is singularly outperformed by GCNII on one of the three tasks.

As such, we feel like the wording of "almost always" is not inaccurate. Nevertheless, we still plan to tune down the statement and put the competitive performance of RUM in the context of the following facts.

• Efficiency. RUM is faster than even the simplest convolutional GNNs on GPUs.
• Robustness naturally afforded by the stochasticity. (Figure 6)

Note that the competitive performance is further demonstrated in the new results provided in the rebuttal period (see the PDF).

Clarification on over-smoothing

In Lemma 6, the author shows that RUM increases Dirichlet energy. Why would this be helpful intuitively?

In Lemma 6, by $E(e(\Phi(X)) \geq e(X)$ under some conditions, we state that RUM is possible to maintain non-decreasing, non-diminishing Dirichlet energy when non-contractive functions (RNNs in this paper) $\phi_x, f$ are prescribed. It does not state that RUM always increases the Dirichlet energy, nor does it state that RUM is anti-smoothing.

In other words, the smoothing behavior of RUM is controlled by the backbone RNN prescribed. All in all, if we want a smoothing RUM, we can couple it with a contractive RNN (if we use contractive activation functions among sequences); an expansive RNN would indeed lead to an anti-smoothing, gradient-exploding RUM (according to the definitions in $1$ ). For vanilla GRUs with sigmoidal updates that are approximately non-contractive (nor expansive), RUM would have roughly constant Dirichlet energy, which is in agreement with our empirical finding in Figure 2.

In comparison, also shown in Figure 2 is that all traditional GNNs are destined to have diminishing Dirichlet energy as a result of the iterative convolutions (Laplacian smoothing), so it is impossible to design deep convolutional GNNs without resulting in very similar neighborhoods.

To summarize, in Lemma 6 we want to show that RUM is possible to be not over-smoothing rather than always anti-smoothing. We do realize that the wording in this section confuses our purpose and will revise it. We thank you again for catching this issue.

Presentation clarity.

The organization and the presentation of the paper can be further improved.

There are too many hyper-references.

There are too many supplementary demonstrations

We apologize for the somewhat convoluting reading experience of this version of the manuscript as it has been significantly condensed and distilled to fit in the page limit. As such, we are disheartened to see that many substantial theoretical and empirical results, have to be moved to the Appendix, including 4 tables, 4 theoretical arguments, and the entire Appendix Section B, which contains important discussions on over-squashing, scaling, and ablation, hence the abuse of hyper-references.

Meanwhile, we had hoped that Section 1 would serve not only as an introduction, but also as a problem statement and a directory. Similarly, Section 2 would relink the display elements scattered around the manuscript to form a thorough comparison between RUM and traditional, convolution-based RNNs. This attempt has clearly failed to provide the desired result and we plan to straighten the confusing sentences and cut down many of the hyper-references and supplementary demonstrations. We thank the reviewer again for bringing our attention to the presentation clarity.

We hope that the discussion above has addressed your concern and that you will consider raising the score to see our manuscript in the next round with significantly improved representation and a clearer discussion on the Dirichlet energy behaviors.

References:

$1$ Yoshua Bengio, Patrice Simard, and Paolo Frasconi. Learning long-term dependencies with gradient descent is difficult. IEEE transactions on neural networks, 5(2):157–166, 1994.

Dear Reviewer jBUd,

Please let us know if our rebuttal has addressed your concerns, especially about the clarification on the over-smoothing behavior.

Thank you!

Many thanks, Reviewer xhjS, for your insightful and constructive review. We also thank you for emphasizing the clarity of our theoretical framework and its potential impact on future research. We address your questions point-by-point as follows.

The impact of random walk lengths.

The paper lacks detailed exploration on how varying random walk lengths impact RUM's performance across diverse tasks and whether optimal lengths are identified for different types of graphs or datasets.

Can you elaborate on how the choice of random walk length  impacts the performance of RUM across different tasks? Are there optimal lengths identified for specific types of graphs or datasets?

When choosing $L$, as noted in the Appendix: Experimental Details, we tune it as a hyperparameter with a range of 3 to 16 for each dataset. The only exception is in the synthetic example of Figure 5, where $L$ is set according to the problem radius $r + 1$. Empirically, citation datasets usually display small-world cluster behavior, hence a smaller optimal $L$, whereas in molecular graphs, optimal $L$ is usually larger since there exist long-term dependencies and rings.

Figure 3 can be seen as a hyperparameter grid search on a citation dataset (Cora). We add a hyperparameter sweep for a molecular dataset (ESOL) in the PDF.

Apart from the impact of the hyperparameter $L$, the length of the random walk and the size of the receptive field, have been discussed in the following sections:

• Corollary 4.1: The impact of $L$ on expressiveness. RUM with $L = N + 1$ is sufficient to distinguish non-isomorphic graphs up to size $N$.
• Figure 2: The impact of $L$ on Dirichlet energy.
• Figure 3: The impact of $L$ on experimental performance.
• Figure 4: The impact of $L$ on efficiency.

We also plan to add the following discussion in Section 3: Architecture to provide a recipe for narrowing the search space for picking $L$ for each problem a priori.

The hyperparameter $L$, the length of the random walk, is an important factor that dictates the size of the receptive field and controls the speed-performance and bias-variance tradeoffs. A higher $L$ affords us a richer, more expressive, more expensive, and potentially higher-variance representation of a larger node neighborhood. We provide the following heuristics for picking the optimal $L$:

• If the problem radius is known a priori, $L$ should match it. In the synthetic setting in Figure 5, $L$ is set to match the problem radius $r+1$.
• If there is rough knowledge about the approximate problem radius (how long-term the interactions are), one can also use such knowledge to confine the search space to the region around it. For example, it is well-known that citation graphs such as that in Figure 3 manifest small-world behavior, whereas physical and chemical graphs sometimes contain long-range dependencies.
• If no such information is available, one can resort to the traditional hyperparameter tuning (one grid search example is replayed in Figure 3). If there is previous experience in tuning the round of message passing for convolutional GNNs, the tuning experiments can start in the vicinity of the optimal solution. Nonetheless, we also note that larger $L$ does not necessarily cause deteriorated performance as evidenced by Figures 2 and 3, and it is possible that the optima for RUM might be larger than that of convolutional GNNs.

The impact of sparsity.

In practical applications, how does RUM handle graph datasets with varying degrees of sparsity?

While the paper demonstrates that RUM outperforms expressive GNNs in certain scenarios, it lacks exploration of scenarios where RUM might face challenges or limitations compared to expressive GNNs.

In the Limitations section as well as the On sparsity paragraph in Section 5: Experiments, we discuss that very dense graphs (such as the Computer dataset with an above 18 average node degree), are where RUM would face challenges, as the variance of the random walk, and thereby the resulting representation, is intrinsically higher. On molecules with an average 2~4 node degree, RUM is more performant even than the best models surveyed in large benchmark studies.

Are there specific strategies employed to ensure robust performance across different graph structures?

As shown in Appendix Section B1, two forms of regularization are employed to ensure consistency:

• Self-supervise: An additional loss is added for the model to predict the semantic embedding of the next node in the walk given its anonymous experiment
• Consistency regularization: Variance among predictions given by different random walk samples is penalized.

Expressiveness comparison with the WL test

For instance, it does not thoroughly investigate potential upper bounds on the WL test, which is a standard measure of graph isomorphism and could provide insights into the discriminative power of RUM compared to more expressive GNNs.

We would also be grateful if you could provide more details on the meaning of "upper bounds of the WL test." Does it mean the dimension $k$ in the $k$-WL test $1$ ?

If that is the case, in Theorem 4, we find that RUM can already distinguish any non-isomorphic graphs (or subgraphs) up to the Reconstruction Conjecture. As such, we can rewrite Corollary 4.1 in a more quantitative manner, that RUM with $k$ -length walks are at least as powerful as $k$-WL:

Corollary 4.1 (RUM is more expressive than k-WL-test.) Up to the Reconstruction Conjecture, two graphs with $G_1 , G_2$ labeled as non-isomorphic by the $k$-dimensional Weisfeiler-Lehman ($k$-WL) isomorphism test, is the necessary, but not sufficient condition that the representations resulting from RUM with walk length $k$ are also different.

References:

$1$ Morris et al. 2018 Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks

Thank you, Reviewer wXB7, for your constructive and encouraging review and for highlighting that RUM is both theoretically innovative and experimentally efficient and performant. We address your question on the directed and weighted graphs as follows, which we plan to incorporate in the manuscript more clearly.

Currently, the proposed architecture only works on unweighted and undirected graphs.

Can the proposed method work well on directed and weighted graphs?

Directed graphs: The inherent dilemma when it comes to directed graphs is that an arbitrarily long walk always exists on undirected graphs but not on directed graphs. As a temporary remedy, to get results on directed graphs in Tables 4 and 8, we have symmetrized the directed graph and annotated whether the walks are going along or against the inherent direction in the topological embedding $\omega_x$. Tables 4 and 8 show that this quick fix produces satisfactory performance---we plan to update the experiment details section to make this clearer. So RUM is already working well on (transformed) directed graphs.

Weighted graphs: we excluded weighted graphs in Section 4 Theory, Assumption 3 only for the simplicity and clarity of the theoretical arguments. In practice, running RUM on directed graphs is feasible with biased random walk, by multiplying the (unnormalized) random walk landing probability (Equation 4) with the edge weight $w_{ij}$:

$P(v_j | (v_0, ..., v_{i-1})) \propto I [(v_i, v_j) \in E_G] * w_{ij} / D(v_i)$

We plan to include this equation in our Section 3: Architecture to clarify that RUM can indeed run on weighted graphs.

To sum up, RUM already works on transformed directed graphs and can be easily extended to weighted graphs. We hope that this has addressed your questions and you will consider increasing the score!

Thank you, Reviewer P1JD, for your thorough and constructive review. We also thank you for recognizing our novelty in using simple building blocks to design novel methods. Based on your review, we plan to revise our manuscript to include a more comprehensive comparison with graph transformer architectures.

Comparison with graph transformers.

Weakness: The paper lacks a discussion on the proposed method and Graph Transformer architectures.

Many thanks for raising this issue. We plan to add the following paragraph to the Related work section to provide a conceptual discussion between graph transformers and RUM:

Graph transformers $1, 2$ ---neural models that perform attention among all pairs of nodes and encode graph structure via positional encoding---are well-known solutions that are not locally convolutional. Their inductive biases determine that over-smoothing and over-squashing among local neighborhoods are, like RUM, also not prominent.

Because of its all-to-all nature, the runtime complexity of graph transformers, just like that of almost all transformers, contains a quadratic term, w.r.t. the size of the system (number of nodes, edges, or subgraphs). This makes it prohibitively expensive and memory intensive on large social graphs (such as that used in Table 8 with millions of nodes). On smaller social graphs, we show in Table 9 that graph transformers are experimentally outperformed by RUM.

We also thank you for pointing us to Ref 1. where there is some overlap in the benchmarking experiments, and we plan to include additional rows in Table 4 to compare with transformer-based models:

The performance for GPS, Graphomer, and Transformer cited here is the best among various positional encodings. RUM outperforms all of them on Texas and Wisc. and is within the confidence interval of the best on Cornell.

For the tasks in Ref. 2, we repeated the smaller MolHIV experiment (Table 3) using RUM and found that RUM performs similarly to Graphformer albeit with a significantly smaller parameter budget:

Out-of-date SOTA reference

Questions: 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

Many thanks, Reviewer P1Jd, for catching this. We were citing performance statistics from a perhaps outdated preprint. We will update these numbers with the new best scores in the correct reference. Though the margin now is smaller for RUM, this update does not change the main message of Table 5.

After careful checking, we find that the condition of walk length $k$ has to be removed in the new Corollary 4.1 reworked during the rebuttal:

Corollary 4.1 (RUM is more expressive than k-WL-test.) Up to the Reconstruction Conjecture, two graphs with $G_1 , G_2$ labeled as non-isomorphic by the $k$-dimensional Weisfeiler-Lehman ($k$-WL) isomorphism test, is the necessary, but not sufficient condition that RUM can distinguish them.

As the authors suggest (and due to the size of the rebuttal), I invite all reviewers to share their main concerns before the rebuttal deadline, to have sufficient time for discussion. I'd be especially interested in feedback from reviewer jBUd, who gave the most negative review as of now.

Thanks, the AC

Thank you, Area Chair bArP, for inviting all reviewers to discuss the remaining concerns!