Non-convolutional graph neural networks.
Authors: Yuanqing Wang
Kyunghyun Cho
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Graph neural networks
Primary area: graph_neural_networks

Abstract: Rethink convolution-based graph neural networks (GNN)---they characteristically suffer from limited expressiveness, over-smoothing, and over-squashing, and require specialized sparse kernels for efficient computation.
Here, we design a simple graph learning module entirely free of convolution operators, coined _random walk with unifying memory_ (RUM) neural network, where an RNN merges the topological and semantic graph features along the random walks terminating at each node.
Relating the rich literature on RNN behavior and graph topology, we theoretically show and experimentally verify that RUM attenuates the aforementioned symptoms and is more expressive than the Weisfeiler-Lehman (WL) isomorphism test.
On a variety of node- and graph-level classification and regression tasks, RUM not only achieves competitive performance, but is also robust, memory-efficient, scalable, and faster than the simplest convolutional GNNs.

Non-convolutional Graph Neural Networks
Yuanqing Wang
Kyunghyun Cho
Center for Data Science and Simons Center
Center for Data Science, New York University and Prescient Design, Genetech New York, N.Y. 10004 kc kc119@nyu.
for Computational Physical Chemistry
New York University New York, N.Y. 10004
wangyq@wangyq.nee
Abstract
Rethink convolution-based graph neural networks (GNN) they characteristically suffer from limited expressiveness, over-smoothing, and over-squashing, and re- quire specialized sparse kernels for efficient computation. Here, we design a simple graph learning module entirely free of convolution operators, coined random walk with unifying memory (RUM) neural network, where RNN merges the topologi- cal and semantic graph features along the random walks terminating at each node. Relating the rich literature on RNN behavior and graph topology, we theoretically show and experimentally verify that RUM attenuates the aforementioned symptoms and is more expressive than the Weisfeiler- Lehmann (WL) isomorphism test. On variety of node- and graph-level classification and regression tasks, RUM not only achieves competitive performance, but is also robust, memorry-effccieee scalable, and faster than the simplest convolutional GNNs.
1 Introduction: Convolutions in GNNs
3 neural models operating on representations of nodes (V) and edges (E) in graph (denoted by (V. V x V, with structure represented by the adjacency matrix Ai = [[v,, v4) E have shown promises in a wide array of social and physical modeling applications. Most GNNs follow a convolutional scheme, where the D-dimensional node representations X R V aggregated based on the structure of local neighborhoods:
Graph neural networks (GNNs)
X =
Here, À displays a unique duality-the input features doubles compute graph. The difference among convolutional GNN architectures, apart from the subsequent treatment of the resulting intermediate representation X', typically amounts to the choices of transformations (Λ) of the original adjacency matrix (A) the normalized Laplacian for graph convolutional networks (GCN) M. learned, sparse stochastic matrix for graph attention networks (GAT) [6]. powers of the graph Laplacian for simplifying graph networks (SGN) [7]. and the matrix exponential thereof for graph neural diffusion (GRAND) [8) to name few. For all such transformations, it is easy to verify that permutation equivariance (Equation 9 trivially satisfied, laying the foundations of data-efficient graph learning. At the same time, this class of methods share common pathologies as well:
Limited expressiveness. (Figure Xu al. 2 groundbreakingly elucidates that GNNs cannot exceed the expressiveness of Weisfeiler-Lehman (WL) isomorphism test (9) Worse still, when the support of neighborhood multiset is uncountable, no GNN with a single aggregation function can be
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

0.3
0,2
0.3
1,3
We COCO
COCD
COCC
COCC
CCCC
CCOC
CCCC
CCOC
We 0101
0121
0120
0123
0101
0121
0121
0120
Table 1: Schematic illustration of RUM. All 4-step unbiased random walks from the 2-degree carbon atom in the (hydrogen-ong) omiiteed) chemical graph of propylene oxide, key precursor for manufacturing polyurethane. The arrows indicate the direction of the walks and numbers the order in which each node is visited. The semantic (W,) and topological (w,,) representations of each walk are shown.
expressive the WL test [10] As such, crucial local properties of graphs meaningful in physical and social modeling, including cycle sizes (Example and diameters (Example be realized by convolution-basel GNNs.
cannot
As one repeats the convolution (or Laplacian smoothing) operation (Equation [T,, sandwiched by linear and nonlinear transformations, the inter-node dissimilarity, measured by Dirichlet energy,
Over-smoothing. (Figure 2)
E(X)
Σ
X.
Xv
N
(u,n)
will decrease exponentially the number of message-passee steps / inereases [12 13 E(X ( <
C1 exp(-C21] with some constants C1,2, resulting in node representations only dependent upon the topology, but not the initial embedding.
As the number of Laplacian smoothing grows, the receptive field of GNNs increases exponentially, while the dimension of node representation, and thereby the possible combinations neighborhood environment, stays unchanged [14.. Quantitatively, Topping et al.
Over-squashing. (Figure 5)
[15 quantifies this insight using the inter-node Jacobian and relates it to the powers of the adjacency matrix through sensitivity analysis:
Ox (++1)
(+))) )
0x
where ò is the node-wise update function, whose Jacobian is typically diminishing. If this Equation converges to zero, the node representation is agnostic to the changes happening edges away, making convolutional GNNs difficult to learn long-range dependencies.
Main contributions: Non-convolutional GNNs as a joint remedy. In this paper, we propose a variant of GNN that does not engage the convolution operator (Equation I all Specificall,, stochastically sample a random walk terminating at each node and use the anonymous experimens associated with the random walk describe its topological environment. This is combined with the semantic representations along the walk and fed into recurrent neural network layer [6] to form the node embedding, which call the unifying memory. We theoretically ($ 4 and experimentally ($ (5) show that the resulting model, termed random walk with unifying memory (RUM) relieves the aforementioned symptoms and offers a compelling alternative the popular convolution-bass GNNs.
2 Related works: ways to walk on graph
compared and outperformed in Table 9 also proposes walk-based representations for representing node neighborhoods, which resembles our model without the anonymous experiment (w, in Equation 55.. CRaWI (18 19,, outperformed in Table 33) also incorporates similar structural encoding for random walk-generated subgraphs to feed into an
Walk-based GNNs. RAW-GNN
'Code at: https:///gtt http://www......oo/aa/aaaa/aaa/a

---

iterative 1-dimensional convolutional network. AWE (20). Table 3) and Wang et al. [21], like ours, use anonymous experiments for graph-level unsupervised learning and temporal graph learning, use agent- bestt learning on random
respectively. More elaborately, [22 and AgentNet 223 Table 3
walks and paths on graphs.
Random walk kernel GNNs. In a closely related line of research, RWK ((24), Table 3) employs the reproducing kernel Hilbert space representations in a neural network for graph modeling and GSN ([25), T counts the explicitly enumerated subgraphs to represent graphs. The subgraph counting techniques intrinsically require prior knowledge about the input graph of a predefined set of node and edge sets. For these works, superior expressiveness has been routinely argued, though usually limited to few special cases where the WL test fails whereas they do not, and often within the unlabelled graphs only.
More importantly, focusing mostly on expressiveness, no aforementioned walk-based or random walk bernel-based GNNs address the issue of over-smoothing and over-squashing in GNNs. Some of these works are also de facto convolutional, as the random walks are only incorporated as features in the pressage-passing scheme. Interestingly, most of these works are either not applicable to, or have not been tested on, node-level tasks. In the experimental $ outperforms these baselines most graph-level tasks (Table 3) but also competes with wide array of state-of of-thhcart convolutional GNNs on node-level tests (Table 2 Moreover, random walk kernel- based architectures, which explicitly enumerate random walk-generated subgraphs are typically much slower than WLL-quivalent convolutional GNNs, whereas RUM is faster than even the simplest variation of convolutional GNN (Figure 4
5 we show that RUM not only
Graph transformers. Graph transformers 26 27 -eurrl models that perform attention among all pairs of nodes and encode graph structure via positional encoding- are well-known solutions that 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 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 Tables 9 4 that graph transformers are experimentally outperformed by RUM.
State-of-the-art methods to alleviate oversmoothing. Stochastic regularization. DropEdge (28) Figure regularizes the smoothing of the node representations by randomly disconnecting edges. Its associated Dirichlet energy indeed decreases slower, though eventually still diminishes as the number of layers increases. Graph rewiring. (29 30 and GPR-GNN (3I), Appendix Table 9 rewire the
graph using personalized page rank algorithm 32 and generalized page rank on graphs, respectively. Similar to JKNet (33). they mitigate over-smoothing by allowing direct message passing between faraway nodes. Constant-energy methods. Zhao and Akoglu [34], Rusch et al. (35) constrain the pair-wise distance or Dirichlet energy among graphs to be constant. Nevertheless, the non- non-decreasing energy does not necessarily translate to better performance, as they sometimes come with the sacrifice of expressiveness, as argued in Rusch et al. [3). Residual GNNs. Residual connection (36] can naturally be added to the GNN architecture, such as GCNII (B77) Table to restraint activation to be similar to the input to allow deep networks. They however can make the model less robust to perturbations in the input. In sum, these works have similar, if not compromised expressiveness compared to a barebone GCN.
3 Architecture: combining topologic and semantic trajectories of walks
Random walks on graphs. An unbiased random walk w on a graph & is sequence of nodes (vo, ... with landing probability:
P(u, ... 1)) [[ v5) E Ev))
(
where D(v))= Aty is the degree of the node U;. Walks originating from or terminating at any given node a can thus be easily generated using this Markov chain. We record the trajectory of embeddings associated with the walk as (w) = (X,) X1........ Xi). In this paper, we only
3

---

consider finite-long 1-step random walk |w| = In our implementation, the random walks are sampled ad hoc during each training and inference step directly on GPU using Deep Graph Library (38 (see Appendix $ A). Moreover, the walk considered here is not necessarily a path, as repeated traversal of the same node f/ = Uy, i * j not only permitted, but also crucial to effective topological representation, as discussed below.
Anonymous experiment. We use function describing the topological environment of a walk, termed anonymous experiment [39], wy (w) ' + R' that records the first unique occurrence of a node in walk (Appendix Algorithm C). To put it plainly, we label node as the number of unique nodes insofar traversed in a walk if the node has not been traversed, and reuse the label otherwise. Practically, this can be implemented using any rensor-accelerating framework in one line (w is the node sequence of a walk) and trivially parallelized 2 (1* (w [..., :, N,None]==w[.... None,: :])) argmax (-1)
Unifying memory: combining semantic and topological representations. Given any walk w, we now have two sequences Wzx (w) and w. (w) describing the semantic and topological (as we shall show in the following sections) features of the walk. We project such sequential representations onto a latent dimension to combine them (illustrated in Table D:
h(w)= (w))))) &u (u(w)(w)))
(S)
where Øu R - RD maps the sequence of semantic embeddings generated by a t-step walk to a fixed D..ddimensional latent space, Φn RC. + RD maps the indicies sequence to another latent space Du. and ʃ RR, @ RD= - RDD combines them. We call Equation 5 the unifying memory of a random walk, Subsequently, the node representations can also be formed as the average representations of 1-step (1 being a hyperparameter) walks terminating (for the sake of gradient aggregation) at that node:
(v) =
Σ
p(w)h(w).
(6)
(wr)//0/==d 10,0==
which can be stochastically sampled with unbiased Monte Carlo gradient and used in downstream tasks as such node classification and regression. We note that this is the only time we perform SUM or MEAN operations. Unlike other GNNs incorporating random walk-generated features (which are sometimes still convolutional and iterative), we do not iteratively pool representations within local neighborhoods. The likelihood of the data written as:
P) =
Σ
p(w)p(sle.x,uu w)
(7)
The node representation can be summed
(G))
Σ (D)
(8)
VEVCS
to form global representations for graph classification and regression. We call ab in Equation 6 and y in Equation g the node and graph output representations of RUM.
Layer choices. Obvious choices to model f include a feed-forward neural network after concate- nation, and dz, &n recurrent neural networks (RNNs). This implies that, different from most convo- lutional GNNs, parameter sharing is natural and the number of parameters is going to stay constant as the model incorporates larger neighborhood. Compared dot product-based, transformer-like modules (40). RNNs not only have linear complexity (see detailed discussions below) w.r.t. the sequence length but also naturally encodes the inductive bias that nodes closer the origin have stronger impact on the representation. The gated recurrent unit (6RU) variant is used everywhere in this paper. Additional regularizations are described in Appendix $ B.I
Note that this particular implementation introduces an intermediate O(P) complexity term, though it is empirically faster than the linear-compled complexity naive implementation, since only integer indices are involved and thus the footprint is negligible.

---

Runtime complexity. To generate random walks for one node has the runtime complexity of (1)) and for a graph O(V)). where [V] the number of nodes in graph g = (V.E). To calculate the anonymous experiment, as shown in Appendix Algorithm C has O(1) complexity (also see Footnote 2 If we use linear-complexity models, such as RNNs, to model Φz. Pus the overall complexity is (DV)LD) where 1 is the length of the random walk, A the samples used to estimate Equation 6 and D the latent size the model (assumed uniform). Note that different from convolutional GNNs, RUM does not depend on the number of edges |E] (which is usually much larger than (VD) for runtime complexity, and is therefore agnostic to the sparsity of the graph. See Figure 4 for empirical verification of the time complexity. In Appendix Table & show, on a large graph, the overhead introduced by generating random walks and computing anonymous experiments accounts for roughly 1/1500 of the memory footprint and 1/8 of the wall time.
Mini-batches. RUM is naturally compatible with mini-batching. For convolutional GNNs, large graphs that do not fit into the GPU memory have traditionally been a challenge, as all neighbors are required to be present and boundary conditions are hard to define [41]. RUM, on the other hand, can be inherently applied on subsets of nodes of a large graph without any alteration in the algorithm the random walks can be generated on a per-node basis, and the FOR loop in Algorithm C can be executed sequentially, in parallel, naturally scaled to huge graphs.
subsets. Empirically, in Appendix Table X RUM can be
4 Theory: RUM as a joint remedy.
We have insofar designed new graph learning framework-convolution www.olutionnoreeeeeoeeeo graph neural networks (GNNs) that cleanly represent the semantic (w₂) and topological (ww, features of graph-structured data before unifying them. First, we state that RUM is permutation equivariant, Remark 1 (Permutation equivariance). For any permutation matrix P, we have
PX. = (P(()))
which sets the foundation for the data-efficient modeling of graphs. Next, we theoretically demonstrate that this formulation jointly remedies the common pathologies of the convolution GNNs by showing that: (a) the topological representation wi, is more expressive than convolttional-GNNs in distinguishing non-isomorphic graphs; (b) the semantic representation wig no longer suffers from over-smog and over over-squashine squashing.
4.1
RUM is more expressive than convolutional GNNs.
For the sake of theoretical arguments in this section, we assume that in Equation 5
Assumption 2. Φz, Ou. f are universal and injective.
Assumption 3. Graph discussed in this section is always connected, unweighted, and undirected.
Assumption 2 is easy to satisfy for feed-forward neural networks 42 and RNNs 43 Note that RUM can be easily extended to weighted graphs by sampling a biased random walk with edge weights wij and keeping rest of the algorithm the same: P(ryl(ro...., 14-1)) α 7[( My) F& waz/ (1v)). Composing injective functions, we remark that f(w) is also injective w.r.t. Wa (w) and w.(w): despite of Assumption 3 our analysis can be extended to disjointed graphs by restricting the analysis to the connected regions in graph. Under such assumptions, we show, in Remark 8 (deferred to the Appendix), that s is injective, meaning that nodes with different random walks will have different distributions of representations (v1) ) * (12)).) We also refer the readers to the Theorem in Micali and Zhu [39] for discussion the representation power of anonymous experiments unlabelled graphs. Combining with the semantic representations and promoting the argument from a node level to graph level, we arrive at:
Theorem 4 (RUM can distinguish non-isomorphic graphs). Up to the Reconstruction Conjecture [44] RUM with sufficiently long 1-step random walks can distinguish non-isomorphic graphs satisfying Assumption
The main idea of the proof of Theorem (in Appendix D.2p involves explicitly enumerating all possible non-isomorphic structures for graphs with nodes and showing, by induction, that if
5

---

10
10-10
GCN
DropEdge
p( 2 2) =
p( 23)> 0
10-14
Res
50
Figure 1: RUM can (in closed form), whereas the Weisfeiler-Lchman (WL) isomorphism test and WL-equivalent GNNs cannot, dis- tinguish these two graphs-an illustration of Example 8.1
L
Figure 2:
RUM alleviates over-smoothing. Dirichlet energy (E) on Cora 44 graph plot- ted against T,, the number of steps or layers.
the theorem stands for graph of N - 1 size it also holds for N-sized graphs. We also show in Appendix |D. that number of key graph properties such as cycle size (Example(8.) and radius (Example 8.2 that convolutional GNNs struggle [45] 46 to learn can be analytically expressed using wa- As these are solely functions of wr, they can approximated arbitrarily well by universal approximators. These examples are special cases of the finding that RUM is stricly more expressive than Weisfeiler-Lehmanl isomorphism test [
Corollary 4.1 (RUM is more expressive than WL-test). Up to the Reconstruction Conjecture, two graphs with G1 G2 labeled non-isomorphic by the k-dimensional Weisfeiler-Lelman (k- (-)) isomorphism test, is the necessary, but not sufficient condition that the representations resulting from RUM with walk length l are also different.
V (9 + (G
(10)
Thus, due to Xu et al. [2], RUM also more expressive than convolutional GNNs in distinguishing non-isomorphic graphs. This also confirms the intuition that RUM with longer walks more expressive. (See Figure an empirical evaluation.) The proof this corollary is straightforward to sketch-ever if we only employ the embedding trajectory w,, it would have the effect of performing the function og in Equation 5 on each traversal of the WL expanded trees.
4.2 RUM alleviates over-smoothing and over-squashing
Smortsmog refers to the phenomenon where the node dissimilarity (e.g., measured by Dirichlet energy Equation 2 decreases exponentially and approaches zero with the repeated rounds of message passing. Cai and Wang [12] relates Dirichlet energy directly with the convolutional operator:
Lemma 3.1 from Cai and Wang 12
E((1 - ÁJX S (1 ())
(11)
where À is the smallest non-zero eigenvalue of P, the normalized Laplacian of a graph.
Free of convolution operators, it seems only natural that RUM does not suffer from this symptom (Figure We now formalize this intuition by first restricting ourselves class of non-contractive mappings for f in Definition [
Definition 5. A map f non-contractive on region Ω if 3a E [1, +0o) such that [f(x) - f(y)]
a||x-~10 v/I, Vx, y E Q.
A line of fruitful research has been focusing on designing non-contractive RNNs 48 49 and to
be non-contractive intimately linked with desirable properties such as preserving the long-range information content and non-vanishing gradients. From this definition, it is easy to show that, for each sampled random walk Equation [5] the Dirichlet energy is greater than its input. One only needs to verify that the integration in Equation 6 does not change this to arrive at:

---

Lemma 6 (RUM alleviates over smoothigg)). If 6z. f are non-contractive w.r.t all elements in the sequence, the expected Dirichlet energy of the corresponding RUM node representation Equation is greater than its initial value
E(E(v(X))) 2 E()).
(12)
This implies that the expectation of Dirichlet energy does not diminish even when | + + as is bounded by the Dirichlet energy of the initial node representation, which is consistent with the trend shown in Figure 2 although the GRU is used out-of-box without constraining it to be explicitly non-contractive.
RUM alleviates over-squashing is deferred to Appenxix B.2 where we verify that the inter- node Jacobian (ax(4+1) /ax_"" decays slower the distance between u, v grows vis-à-vis the convolutional counterparts. Briefly, although RUM does not address the information bottleneck with exponentially growing receptive field (the 1/(A"+1) Jue term in Equation 16). it nevertheless can have a non-vanishing (nor exploding) gradient from the aggregation function ([Véz).
Experiments
On a wide array of real-world node- and graph-level tasks, we benchmark the performance of RUM to show its utility in social and physical modeling. Next, to thoroughly examine the performance of RUM, we challenge it with carefully designed illustrative experiments. Specifically, we ask the following questions in this section, with Q1, Q2, and Q3 already theoretically answered in $ $ Q1: RUM more expressive than convolutional GNNs? Q2: Does RUM alleviate over-smoothing? Q3: Does RUM alleviate over-squashing? Q4: Is RUM slower with convolutional GNNs? Q5: Is
RUM robust? Q6: How does RUM scale up to huge graphs? Q7: What components of RUM are contributing most to the performance of RUM?
Real-world benchmark performance. For node classification, we benchmark our model on the popular Planetoid citation datasets (47), as well as the coauthor (50] and co-purchase (51) datasets common in social modeling. Additionally, we hypothesize that RUM, without the smoothing operator, will perform competitively on heterophilic datasets -52 we test this hypothesis. For graph classification, we benchmark on the popular TU dataset 53 We also test the graph regression performance on molecular datasets in MoleculeNet [54] and Open Graph Benchmark (55). In sum, RUM almost always outperforms, is within the standard deviation of, the state-of-the art architectures, as shown in Tables constraint.
as well as in Tables 6 9 moved to the Appendix due to space
On sparsity: the subpar performance on the Computer dataset. The most noticeable exception to the good performance of RUM is that the Computer co-purchase [5I] dataset, where RUM is outperformed even by GCN and GAT. This dataset is very dense with an average node degree (( of 18.36, the highest among all datasets used in this paper. As the variance of the node embedding (Equation (6 scales with the average degree, we hypothesize that dense graphs with very high average node degrees would have hari-variance representations from RUM.
On the other hand, RUM outperforms all models surveyed in two large-scale benchmark studies on molecular learning, GAUCHE (56) and MoleculeNet [54]. The atoms in the molecules always have a degree of 2 ~ with intricate subgraph structures like small rings. This suggests the utility of unifying memory in chemical graphs and furthermore chemical and physical modeling.
Graph isomorphism testing (Q1). Having illustrated in 4 that RUM can distinguish non- isomorphic graphs, we experimentally test this insight on the popular Circular Skip Link dataset (60 61. Containing 4-regular graph with edges connected to form a cycle and containing skip-links between nodes, this dataset is artificially synthesized in Murphy et al. [60] create an especially challenging task for GNNs. As shown in Appendix Table all convolutional GNNs fail to perform better than constant baseline (there are classes uniformly distributed). 3WL.GNN (22, a higher- order GNN of at least O(2) complexity that operates on explicitly enumerated triplets of graphs, can distinguish these highly similar 4-regular graphs by comparing subgraphs. RUM, with ((Vl) linear complexity, achieves similarly high accuracy. One think of RUM as stochastic approximation
7

---

Cora
CiteSeer
PubMed
Coathor CS
Computer
Photo
GCNO
81.5
70.3
79.0
91.1
82.6+2.4
91.2+1.2
GAT
83.0
42.5
79.0
90.5
18.0
85.7+20.3
GraphSAGEg
77.4+1.0
67.0+1.0
76.610.8
85.041.1
90.441.3
koNet
80.7
70.040.6
78.840.4
90.8
83.5
91.2
GCNIL
85.5+0.5
73.440.6
80.340.4
PairNorm[s
81.1
70.6
78.2
GraphCON
84.2+113
74.2+1.7
79.4+1.3
RUM
84.1
75.540.5
82.2+0.2
93.2+0.0
77.8+2.3
92.7+0.1
Table 2: Node classification test set accuracy 1 and standard deviation.
IMDB-B
MUTAG
PROTEINS
PTC
NCII
RWK 24
79.212.1
59.610.1
55.910.3
GK
81.4+1.7
71.4+0.3
55.7
62.5+0.3
WLK
73.8
90.445.7
75.0+3.1
59.9+4.3
86.0+1.8
AWE
20
74.5
87.849.8
GIN
A
75.1=5.1
90.048.8
76.2+2.6
66.646.9
82.7+1.6
GSN 25
77.8
92.2+7.5
76.6+5.0
68.2+7.2
83.5+2.0
73.4-2.1
90.4+7.1
76.2+3.7
68.0+6.5
AgentNetg3
75.2
93.6
76.7
67.4
RUM
81.1=1.5
91.0+7.1
77.3+3.8
69.8+6.3
81.7+1.4
Table 3: Binary graph classification test set accuracy 1.
of the higher-order GNN, with all its explicitly enumerated subgraphs being identified by RUM with probability that decreases with the complexity of the subgraph.
Effects of walk lengths and number of samples on performance (Q2, Q3). Having studied the relationship between inference speed and the walk lengths and number of samples, we furthermore study its impact performance. Using Cora [47] citation graph and vary the walk lengths and number of samples from 1 to 9, where the performance of RUM improves as more samples are taken and longer walks are employed, though more than 4 samples and walks longer than L > 4 yield qualitatively satisfactory results; this empirical finding has guided our hyperparameter design. In Figure 2 also compare the Dirichlet energy of RUM-generater layer representations with not only baselines GCN ( and GAT [6), but also strategies to alleviate wworssmo discussed and show that when I. gets large, only RUM can maintain Dirichlet energy. Traditionally, since Kipf and Welling [ (see its Figure compared to Figure 3), the best performance Cora graph found with 2 or message-passing rounds, since mostly local interactions are dominating the classification, and more rounds of message-passing almost always lead to worse performance. As theoretically demonstrated in $ 4.2 RUM is not as affected by these symptoms. Thus, RUM is especially appropriate for modeling long-range interactions in graphs without sacrificing local representation power.
in $ $2 namely residual connection and stochastic regularization 37 28 63
Texas
Wisc. Cornell
GCN I
55.1 51.813.3 60.514.8
GAT'
52.2.6.6
51.843.1 60.51..3
ESOL
FreeSolv Lipophilicity
GCNI 57
77.643.8
80.413.
77.943.8
GAUCHEES
0.67 10.01
0.73 0.96
Geom-GCN 52
66.842.7
64.543.7 60.543.7
MoleculeNet 34
0.58
1.15
0.80
PairNorm L0
60.3
48.446.1 58.943.2
RUM
0.62 0.96 0.66
GPS p0
75.4
78.042.9
65.4
Table S: Graph regression RMSE 1 compared with the best model studied in two large-scale
Graphomer
76.8 77.7 12.0 68.4
RUM 80.0 85.814. 71.1
benchmark studies on OGB (55] and Molecu- leNet (54) datasets.
Table 4: Node classification test set accuracy and standard deviation heterophilic (52
datasets.
8

---

0.030
1.25
RUMB)
086
0.025
881
834
1.00
RUMH4)
RUMB)
0.020
0.79
078
Time
0.90
0.75
GAT
0.016
0.110
0.78
0.78
0.25
Lmogi maaos
10
15
10
15
Hhebbar of senples
Figure 4: RUM faster than convolutional GNNs on GPU. Inference time over the Cora 47 graph on CPU and CUDA devices, respectively, plotted against L, the number of message-passing steps equivalently the length of random walks. Numbers in the bracket indicate the number of sampled random walks drawn.
Figure 3: Impact of number of samples and walk length. Test classification accuracy of Cora [47] with varying numbers of samples and walk length.
1.0
RUM
0.8
Accuracy
GON
Accuracy
RUM
GAT
GCN
GGNN
0.6
GAT
GIN
GRAND
10
Problem radius r
Porturbation rate: edges added
Figure 5: Long-range neighborhood match- ing training accuracy f [4 with unit mod- els.
Figure 6: Robustness analysis. Accuracy f on Cora [47 dataset with % fictitious edges added to the graph.
Long-range neighhorhood matching (Q3). verify that RUM indeed alleviates over-squashing ($ B.2), in 5 we adopt the tree neighborhood matching synthetic task in Alon and Yahav [14] where binary tree graphs are proposed with the label and the attributes of the root matching a faraway leave. The full discussion is moved to the Appendix $ B.3
Speed (Q4). Though both have linear runtime complexity (See $ 3 intuitively, it might that RUM would be slower than convolution-basel GCN due to the requirement of multiple random walk samples. This is indeed true for CPU implementations shown in Figure [igure4left. When equipped with GPUs (specs in Appendix $ AA). however, RUM is significantly faster than even the simplest convolutional GNN-GCN (.. is worth mentioning that the GCN and GAT (6) results were harvested using the heavily optimized Deep Graph Library (38 sparse implementation whereas RUM implemented naïvely in PyTorch (64, though the popular GRU component 16 have already undergone CUDA-specife optimization.
Robustness to attacks (Q5). With the stochasticity afforded by the random walks, is natural
suspect RUM to be robust. We adopt the robustness test from Feng et al. (65) and attack by randomly
adding fake edges the Cora [47] graph and record the test performance in Figure Indeed,
RUM is much more robust than traditional convolutional GNNs including GCN [ and GAT (6) and
even slightly more robust than the convolutional GNN specially designed for robustness [65 with
the performance only decreased less than 10% with 10% fake edges added.
Scaling to huge graphs (Q6) and Ablation study (Q7) are deferred to Appendix
B.5

---

6 Conclusions
We design an innovative GNN that uses an RNN to unify the semantic and topological representations along stochastically sampled random walks, termed random walk with unifying memory (RUM) neural networks. Free of the convolutional operators, our methodology does not suffer from symptoms characteristic of Laplacian smoothing, including limited expressiveness, over-smoothing, and over- squashing. Most notably, our method is more expressive than the Seisfeiler-Lehmane isomorphism test and can distinguish all non-isomorphic graphs up the reconstruction conjecture. Thus, it is more expressive than all of convolutional GNNs equivalent to the WL. test, as we demonstrate theoretically in $ 4 RUM is significantly faster GPUs than even the simplest convolutional GNNs ($ 5 and shows superior performance across plethora of node- and graph-level benchmarks.
Limitations. Very dense graphs. As evidenced by the underwhhelming performance of the Computer [51] dataset and discussed in $ RUM might suffer from high variance with very dense graphs (average degree over 15). Tottrrngg. In our implementation, we have not ruled out the 2-cycles from the random walks, as that would require specialized implementation for walk generation. This, however, would reduce the average information content in a fixed-length random walk (known as tottering (66]). We plan to characterize the effect of excluding these walks. Biased walk. Here, we have only considered unbiased random walk, whereas biased random walk might display more intriguing properties as they tend to explore faraway neighborhoods more effectively [17] Directed graphs. Since we have only developed RUM for undirected graph (random walk up to a random length is not guaranteed exist for directed graphs), we would have to symmetrize the graph to perform on directed graphs (such as the heterophilic datasets [52]; this create additional information loss and complexity.
Future directions. Theoretical. We plan to expand our theoretical framework to account for the change in layer width and depth to derive analytical estimates for realizing key graph properties. Applications. Random walks intrinsically applicable to uncertainty-aware learning. We plan to incorporate the uncertainty naturally afforded by the model to design active learning models. On the other hand, the physics-based graph modeling field also heavily dominated by convolutional GNNs, Inspired by the superior performance of RUM on chemical datasets, we plan to apply our method in and furthermore on the equivariant modeling of n-body
drug discovery settings 67 68
physical systems 722.
Impact statement. We here present a powerful, robust, and efficient learning algorithm on graphs. Used appropriately, this algorithm might advance the modeling of social (73) and physical [74] systems, which can oftentimes modeled as graphs. As with all graph machine learning methods, negative implications may be possible if used in the design of explosives, toxins, chemical weapons, and overly addictive recreational narcotics.
References
[1] Thomas N. Kipf and Max Welling. Semi-supervised classfficaoon with graph convolutional networks. CoRR, abs/1600.02907, 2016. Uti. htsp//0b/1110..../
[2] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanic Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.0000 00826, 2018.
[3] Justin Gilmer, Samuel S Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. arXiv preprint arXiv:1704.01212 2017.
[4] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In Advances in neural information processing systems, pages 1024-1034, 2017.
[5] Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo. Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint 106.0118 2018
[6] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks, 2018
10

---

[7] Felix Wu, Tianyi Zhang, Amauri H. Souza Jr., Christopher Fifty, Tao Yu, and Kilian Q. Wein- berger. Simplifying graph convolutional networks. CoRR, abs/1902.07153, 2019. URL
/ttp///rxiiv..rr/aa///990. 07153
[8] Benjamin Paul Chamberlain, James Rowbottom, Maria I. Gorinova, Stefan Webb, Emanuele Rossi, and Michael M. Bronstein. GRAND: graph neural diffusion. CoRR, abs/2106.10934, 2021. CtRLhhttss:////
org/ abs waw.////f 2106 10934
[9] Boris Weisfeiler and Andrei Leman. The reduction of graph to canonical form and the algebra which appears therein.
[10] Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets, 2020.
[11] Vikas K. Garg, Stefanie Jegelka, and Tommi S. Jaakkola. Generalization and representational limits of graph neural networks. CoRR, abs/2002.061577, 2020. bttps:////a:
aba/2002. 2011000006615
[12] Chen Cai and Yusu Wang. note on over-smoothing for graph neural networks, 2020.
[13] T. Konstantin Rusch, Michael M. Bronstein, and Siddhartha Mishra. A survey on oversmoothing in graph neural networks, 2023.
[14] Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. CoRR, abs/2006.05205, 2020. URL httLLhtt/////et /ttpps://arxiin www.xi..oo//bb//00666.6 05205
[15] Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature,
2022.
[16] Kyunghyun Cho, Bart van Merrienboer, Çaglar Gülçehre, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using RNN encoder-decoder for statistical machine translation. CoRR, abs/1406. 1078, 2014. URL httpp:///ariivoorrrb///000. 1078.
[17] Di Jin, Rui Wang, Meng Ge, Dongxiao He, Xiang Li, Wei Lin, and Weixiong Zhang. Raw-gnn: Random walk aggregation based graph neural network, 2022.
[18] Jan Tönshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe. Graph learning with 1d convolutions on random walks. CoRR, abs/2102.08886, 2021. URL https:///axxv org/
abs/2102.
[19] Jan Tönshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe Walking out of the weisfeiler leman hierarchy: Graph learning beyond message passing, 2023.
[20] Sergey Ivanov and Evgeny Burnaev. Anonymous walk embeddings, 2018.
[21] Yanbang Wang. Yen-Yu Chang, Yunyu Liu, Jure Leskovec, and Pan Li. Inductive representation learning in temporal networks via causal anonymous walks, 2022.
[22] Rajarshi Das, Shehzaad Dhuliawala, Manzil Zaheer, Luke Vilnis, Ishan Durugkar, Akshay Krishnamurthy, Alex Smola, and Andrew McCallum. Go for walk and arrive at the answer: Reasoning over paths in knowledge bases using reinforcement learning, 2018.
[23] Karolis Martinkus, Pál András Papp, Benedikt Schesch, and Roger Wattenhofer. Agent-based graph neural networks, 2023.
[24] Giannis Nikolentzos and Michalis Vazirgiannis. Random walk graph neural networks. In
H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neu- ral Information Processing Systems, volume 33, pages 16211-16222. Curran Associates, wwt..a/ss/pppe///////////2
Inc., 2020. URL httpttttts::/ppoceeeeiiiiii ba557788899222111100077777228222
newrips. .dd.f
[25] Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M. Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(1):657-668, January 2023. ISSN 1939-3539, doi:
10. http:////pmmm.22..15555333
URL:ttp:: //tp::://xxx. http::::/xxx.d...ooooo wwg/11.oo.....ooooooo//oo..o.... P..0O////MM......MM 2022. 3154319
[26] Ladislav Rampášek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for general, powerful, scalable graph transformer, 2023. URL
https://arxiv org/ abs 12454

---

[27] Chengxuan Ying. Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen. and Tie- Yan Liu. Do transformers really perform bad for graph representation? CoRR, abs/2106.05234 2021. URI.https:// httpt:t/ttsaiiii www.orgg///////o/////o///eeeee// 220. 05234
[28] Yu Rong, Wenbing Huang. Tingyang Xu, and Junzhou Huang. The truly deep graph con- volutional networks for node classification. CoRR, abs/1907.10900 2019. URL. http:
7
10903
[29] Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate:
Graph neural networks meet personalized pagerank, 2022.
[30] Johannes Gasteiger, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learning, 2022.
[31] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Joint adaptive feature smoothing and topology extraction via generalized pagerank gnns. CoRR, abs/2006.0 077988, 2020. URL
07988
[32] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking : Bringing order to the web. In The Web Conference, 1999. URL https://api
semanticscholars wttgg/CorpssD::::: 1508503
[33] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Jegelna Representation learning on graphs with jumping knowledge networks. CoRR, (bs/1806.03536, 2018. http:/t /ttp:i://axxv....// org abaaaass//1./// 03536
[34] Lingxiao Zhao and Leman Akoglu. Paimoor: Tackling oversmoothing in gnns. CoRR, 1DsS/999..2223, 2019. URL htttp://arxiv..rr/bbbb//// wwtp:rrggabb//999../// 12223
[35] Konstantin Rusch, Benjamin Paul Chamberlain, James Rowbottom, Siddhartha Mishra, and Michael M. Bronstein. Graph-coupled oscillator networks. CoRR, abs/2202.022996, 2022. URL https://ares org/
02296
[36] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. CoRR, abs/1512.00385 2015. URL http:///axiii org/ abaaaaaaa1511 03385
[37] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks, 2020.
[38] Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang. Deep graph library: A graph-centric, highly-performant package for graph neural networks, 2020.
[39] Silvio Micali and Zeyuan Allen Zhu. Reconstructing markov processes from independent and 2016. ISSN 0166-218X. doi: https://boi.org/1.00006... www...mm....m..... URL httphhttp//w//t www.w/wwwwwwweeeeettt.otmm com/
anonymous experiments. Discrete Applied Mathematics,
[40] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. CoRR, abs/1706.03762, 2017.
htt.//ttp//arrii.. orgpaaawwi.....aaaaaaaaaaeaaeaee httgg/bbs/1//.... 03762
[41] Keyu Duan, Zirui Liu, Peihao Wang, Wenqing Zheng, Kaixiong Zhou, Tianlong Chen, Xia Hu, and Zhangyang Wang. A comprehensive study on large-scale graph training: Benchmarking and rethinking, 2023.
[42] Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural networks, 255):359-366, 1989.
[43] Anton Maximilian Schäfer and Hans Georg Zimmermann. Recurrent neural networks universal approximators. In Artificial Neural Networks-ICANN 2006: 16th International Conference, Athens, Greece, September 10-14, 2006. Proceedings, Part 16, pages 632-640. Springer, 2006.
[44] Paul Kelly. A congruence theorem for trees. 1957.
[45] Andreas Loukas. What graph neural networks cannot learn: depth width. CoRR, abs/1907.03199, 2019. URL/http: http::///aa/v.///aa wrtp:/s///////...//// 033999
[46] Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks, 2020.
12

---

[47] Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. seristtnsssmissuuprrisssss learning with graph embeddings. CoRR, wbs/16003088a..0 088611 2016. UtL.tttp///axiiv.or/////
08861
[48] 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.
[49] António H. Ribeiro, Koen Tiels, Luis A. Aguirre, and Thomas Schön. Beyond exploding and vanishing gradients: analysing rnn training using attractors and smoothness. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 2370-2380. PMLR, 26-28 Aug 2020. URL htttps:/proceeddnngggg #ress//110//ibeiro00... html
[50] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv:181 1.05868, 2018.
[51] Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton Van Den Hengel. Image-based recommendations on styles and substitutes. In Proceedings of the 38th international ACM
SIGIR conference research and development in information retrieval, pages 43-52, 2015.
[52] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks, 2020.
[53]
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs, 2020.
[54] Zhenqin Wu, Bharath Ramsundar, Evan N. Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh S. Pappu, Karl Leswing, and Vijay Pande. Moleculenet: a benchmark for molecular machine learning. Chem. Sci., 9:513-5300 530, 2018. doi: 10. 10.1039/C78C006644, URL http://dx: doi
org/10. C77C022646
[55] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. CoRR, abs/2005.00687 2020. URLhhttps: /ttp///aivv/////////////////.att wwtg/ba////a 2005. 00687
[56] Ryan- Griffiths, Leo Klarner, Henry B. Moss, Aditya Ravuri, Sang Truong, Samuel Stanton, Gary Tom, Bojana Rankovic, Yuanqi Du, Arian Jamasb, Aryan Deshwal, Julius Schwartz, Austin Tripp, Gregory Kell, Simon Frieder, Anthony Bourached, Alex Chan, Jacob Moss, Chengzhi Guo, Johannes Durholt, Saudamini Chaurasia, Felix
Alpha A. Lee, Bingqing Cheng, Alán Aspuru- Philippe Schwaller, and Jian Tang. Gauche: A library for gaussian processes in chemistry, 2023.
[57] Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodolà, Jan Svoboda, and Michael M. Bronstein. Geometric deep learning graphs and manifolds using mixture model cnns. CoRR, abs/ 1o6l///1111// 1.08402, 2016. URL lttt:://axxiv http://xxvvoorr////// absaaba//111 1etp//6611.88002
[58] Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt. Efficient graphlet kernels for large graph comparison. In Artificial intelligence and statistics, pages 488 495. PMLR, 2009.
[59] Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(9), 2011.
[60] Ryan L. Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations, 2019.
[61] Vijay Prakash Dwivedi, Chaitanya K. Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks, 2022.
[62] Haggai Maron, Heli Ben- Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks, 2020.
[63] Yuanqing Wang and Theofanis Karaletsos. Stochastic aggregation in graph neural networks. arXiv preprint 212.:22022.1644., 2021.
[64] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Z. Yang, Zach Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy,
13

---

Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style. high-performance deep learning library. CoRR, abs/1912.01703, 2019. http:////arx arg/abs/1912.01f 01703
[65] Wenzheng Feng, Jie Zhang, Yuxiao Dong, Yu Han, Huanbo Luan, Qian Xu, Qiang Yang, Evgeny Kharlamov, and Jie Tang. Graph random neural networks for semi-supervised learning on graphs. In H. Larochelle. M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances Neural Information Processing Systems, volume 33, pages 22092-22103. Curran Associates, Inc., 2020. StLLhhttps://proceeee ings newrips......... cc/ wwc/pappr__a f files/ pappr__teeesppppr//22////////// paaprr/020/filee Fb44335f40066c33377777777111---3
pdff
[66] Nils M. Kriege, Fredrik D. Johansson, and Christopher Morris. A survey on graph kernels. CoRR, abs/1903. 1835, 2019. URL http:://axxiii http//awwww...a//////..... 11835
[67] Yuanqing Wang, Josh Fass, Benjamin Kaminow, John E Herr, Dominic Rufa, Ivy Zhang, Iván Pulido, Mike Henry, Hannah E Bruce Macdonald, Kenichiro Takaba, et al. End-to-end differentiable construction of molecular mechanics force fields. Chemical Science, 13(41): 12016-12033, 2022.
[68] Kenichiro Takaba, Iván Pulido, Mike Henry, Hugo MacDermott SepDermmtt-OOpskin. John D Chodera, and Yuanqing Wang. Espaloma-0.3. O: Machine-learned molecular mechanics force field for the simulation of protein-ligand systems and beyond. arXiv preprini A.Niv:2307.070S: 2023.
[69] Michael Retchin, Yuanqing Wang, Kenichiro Takaba, and John D. Chodera. Druggym: A testbed for the economics of autonomous drug discovery. bioRxiv, 2024. doi: 10. 101/2000/244 596296. URL htttps://wwt biorxiv /ttp://///////a////////////////0 596296
[70] Yuanqing Wang, Iván Pulido, Kenichiro Takaba, Benjamin Kaminow, Jenke Scheen, Lily Wang, and John D Chodera. Espalomacharge: Machine learning-enabled ultrafast partial charge assignment. The Journal of Physical Chemistry A, 128-20):410044167, 2024.
[71] Yuanqing Wang. Graph Machine Learning for (Bio)Molecullr Modeling and Force
Field Construction. PhD thesis. 2023. URL http:://proxy wwwprroooo...bbrrr...a www.rribbbrry.. nyu.
2Fse-2%3 2atee=223acccomm.....120707 Copyright Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works; Last updated- 2024-04-24.
[72] Yuanqing Wang and John D Chodera. Spatial attention kinetic networks with e (n)-eqivvariance. In ICLR 2023, 2023.
[73] Justin Grimmer, Margaret E Roberts, and Brandon M Stewart. Machine learning for social science: An agnostic approach. Annual Review of Political Science, 24:395 2021. [74] Gerhard Hessler and Karl-Heinz Baringhaus. Artificial intelligence in drug design. Molecules, 23(10):2520, 2018.
[75] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization, 2017.
[76] Stefan Elfwing, Eiji Uchibe, and Kenji Doya. Sigmoid-weige weighted linear units for neural network function approximation in reinforcement learning. 2017.
[77] Philipp Moritz, Robert Nishihara, Stephanie Wang, Alexey Tumanov, Richard Liaw, Eric Liang, Melih Elibol, Zongheng Yang, William Paul, Michael I. Jordan, and Ion Stoica. Ray: A distributed framework for emerging applications. 2018.
[78] Eytan Bakshy, Lili Dworkin, Brian Karrer, Konstantin Kashin, Benjamin Letham, Ashwin Murthy, and Shaun Singh. Ae: A domain-agnostic platform for adaptive experimentation. In Conference on neural information processing systems, pages 1-8, 2018.
[79] Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks, 2013.
[80] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9()):
1735-1780, 1997.
[81] Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster- gen: An efficient algorithm for training deep and large graph convolutional networks. CoRR, abs/1905.07953 2019. URL http:/ htttp://axee //trxv/.aiivv///a wttp://a///...00755555553 07953
14

---

[82] Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor K. Prasanna. Graphsaint: Graph sampling based inductive learning method. CoRR, abs/1907 19ts/999770491,, 2019. httpp/ttt///axxi org/ htrggabb/19907 04931
[83] Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. CoRR, abs/1801 10247, 2018. http://tc///aarzvvor///a///////
10247]
[84] Difan Zou, Ziniu Hu, Yewen Wang, Song Jiang. Yizhou Sun, and Quanquan Gu. Layer- dependent importance sampling for training deep and large graph convolutional networks. CoRR, abs/191 1.0323,, 2019. httpatppp//axii..r///aaa////////
[85] Fabrizio Frasca, Emanuele Rossi, Davide Eynard, Ben Chamberlain, Michael Bronstein, and Federico Monti. Sign: Scalable inception graph neural networks, 2020. UtI.tttps://arx.
org/abs/2004.11199
[86] Chuxiong Sun, Hongming Gu, and Jie Hu. Scalable and adaptive graph neural networks with self-label-enhanceed training, 2021.
[87] Renjie Liao, Zhizhen Zhao, Raquel Urtasun, and Richard S. Zemel. Lanczosnet: Multi- scale deep graph convolutional networks. ArXiv, abs/1901.01448 2019. Uttpstss: semanticscholar.
57573777
[88] Vijay Lingam, Chanakya Ekbote, Manan Sharma, Rahul Ragesh, Arun Iyer, and Sundararajan Sellamanickam. A piece-wise polynomial filtering approach for graph neural networks, 2021.
[89] Deyu Bo, Chuan Shi, Lele Wang, and Renjie Liao. Specformer: Spectral graph neural networks meet transformers, 2023.
Disclosures.
YW has limited financial interests in Flagship Pioneering, Inc, and its subsidiaries.
Funding, YW acknowledges support from the Schmidt Science Fellowship. in partnership with the Rhodes Trust, and the Simons Center for Computational Physical Chemistry New York University.
15

---

A Experimental details
Code availability. All architectures, as well as scripts execute the experiment, are distributed open-source under MIT license at /tttss::/aane http////nonmmouuuuuom 4open. science r //ruum-- 834D/ Core dependencies of our package include Py Torch 64 and Deep Graph Library
Hyperparameters. All models are optimized using Adam [75] optimizer and SiLU 76 activation functions. 4 random walk samples are drawn everywhere unless specified. Other hyperparameters learning rate (10-5 ~ 10-2), hidden dimension (32 ~ 64), 1.2 regularization strength (10-& ~ 10 walk length (3 16), temperature for Lconsistancy
1), coefficient for Ceonsistency (0 1), coefficient for Leele, and dropout probability are tuned using the Ray platform [77] with the default Ax 78 search algorithm with 1000 trails or 24 hours tuning budget on Nvidia A100 GPU.
B
Additional technical details
B.1 Self-supervised regularization.
The stochasticity encoded in our model naturally affords it with some level of regularization. Apart from using the consistency loss (Cconsistency) used in Feng et al. [65] for classifications, we further regularize the model by using the RNNs in Φ₂ to predict the semantic representation of the next node on the walk given wa and jointly maximize this likelihood:
Wes+r = g((we, Wa...... Wa, J. wul;);
(13)
Lear (0) = - log P( 10),
(14)
where g(166) is modeled as the sequence output of the RNN &r Equation modeled as combination of:
The total loss is
[()) = log P(y19,X,0) + Leolt + Leanstatency
(15)
B.2 RUM attenuates over-squashing
Similarly, we can show that if the composing neural networks defy the vanishing gradient problem (w.r.t. the input) [7),, the sensitivity analysis in Equation 3 [5] has a lower bound for RUM. Lemma 7 (RUM attenuates over- ver-squashing). If @z. f have hownded derivatives, the inter-node Jacobian for nodes u, v separated by shortest path of length 1, RUM with walk length I also has lower bound:
ox
Voz
(16)
Ox
where Ay = A5 Aig the degrec-normalized adjacency matrix.
Like the upper bound in Equation 3 this lower bound is also controlled by the power of the (nor- malzied) adjacency matrix, albeit the absence of self-loop will result in a slightly looser bottleneck. The term (A')... corresponds to the probability of the shortest path among all possible walks as a product of inverse node degrees (see Equation 4 There is no denying that the lower bound is still controlled by the power of the adjacency matrix, which corresponds to the exponentially growing receptive fields. One can also argue that, without prior knowledge, the contribution of the sensitivity analysis by the power of the graph adjacency matrix never be alleviated, since there always roughly 1/(Á"+' Juo (assuming uniform node degree) structurally equivalent nodes. Nev- ertheless, since Φx is not necessarily an iterative function, we alleviate the over squashing problem by eliminating the power of the update function gradient term.
Now, we plug the layer choices of da.-a GRU 16 unit. success, just like that of long short- term memory (LSTM) [80]. can be attributed to the near-linear functional form of the long-range gradient. The term [V controlled by a sequence of sigmoidal update gates, which can be optimized to approach (fully open). If we ignore the gradient contribution of X to these gates, the non-linear activation function has only been applied exactly once on X therefore, the gradient Jax!! ((+1) 10x(()
(0) is neither rapidly vanishing nor exploding.
16

---

W/
Wy
Laois
L Consistency
82.2 1.0
35.0 + 1.0
78.4 = 0.1
80.3 = 1.1
Table 6: Ablation study. Cora [47] test set accuracy 1 with in the architecture deleted.
B.3 Long-range neighborhood matching (Q3).
Once identifying the target leaf, this task seems trivial; nonetheless, this piece of information needs to be passed through layers of aggregation and non-linear update and usually lost in the convolution. Since, on this binary tree, the receptive field grows exponentially, Alon and Yahav [1]] argues that there is a theoretical lower boundary for the layer width D for the convolutional GNN to be able to encode all possible combinations of leaves, which is 232D for dingle-precisee (float32). This corresponds to the structural A' term in Equation and Equation 16 Evidently, when = 32, as the adopted experimental setting in Figure [S this limit far from being hit. So we hypothesize that the reason why convolutional GNNs cannot overfit the training set is because of the limitation of the functional forms, which are remedied by RUM, which shows 100% accuracy up tree depth or problem radius 5, and relatively moderate decrease afterward. Note that when the problem radius exceeds r = 7, RUM's performance is not significantly different from the convolutional counterparts.
floating point
B.4 Scalaing to large graphs (Q6).
In Appendix Table g we apply RUM on an ultra-large graph OGB-PRODUCTS, that cannot fit easily on single GPU, and compare RUM with architectures specifically designed for large graphs [1]
B.5 Ablation study (Q7).
In Table o conduct brief ablation study where delete, one by one, the components introduced in $ $ W O and W, = O refer to the deletion of the topological and semantic representations of walks, respectively. Neglecting topological information results in moderate decrease in performance, whereas neglecting semantic representation is more detrimental. The w,, 0 also resembles Jin et al. 117 albeit with different walk-wise aggregation. This offers qualitative comparison between our work and Jin et al. [17] no source code was released for this package so no rigorous comparison was possible. We also see that the regularization methods are helpful the performance, with self-supervision being more crucial. We attribute this effect to firstly the relative simplicity of the Cora classification task, and secondly the flexibility of the (overparametrized) RNNs.
C Additional results
Algorithm 1 anonymous experiment
Input: w = (Vo, U1... U2....,,
C 0; Ω Dict(())
for U/ in w do
If u; in Ω: w, A[x:] Else 2(vx) C:C+C++
end for
Return: W. (u:) (Mo, u1.-..;..)) u.)
Remark 8 (Inequality in distribution). For two nodes U1, U2 with distribution of random walks terminating at 01, 22 not equal in distribution (ww,,(w)) * ((w)(w2) or (ww) # p(wr(w2)) the node representations in Equation arre also different (b(1)) # (1(2).
One way to construct h function in Equation 5 is to have h(w) positive only where p(w, (wx)) > ((w,(w2))) the same thing can be argued for Wa. In other words, one only needs prove two walks terminating at two nodes p(w)(w1)) * ((w,((2)) or p(w,(w,)) A p(w=(w2)) are not equal in distribution to verify that RUM can distinguish two nodes. Conversely, we can also show that p(w,,(1) )) p(w,(w2) implies that U1, 02 are isomorphic without labels- we refer the readers to the Theorem Micali and Zhu (39 for a discussion on reconstructing unlabelled graphs using anonymous experiments.
17

---

Complexity
CSL accuracy
GCND 0
((N)
10.0 0.0
GAT R
O(N)
10.0
GINg
O(N)
10.0
GraphSAGEB
O(N)
10.0
3WLGNN
O(N2)
95.7 14.8
RUM
((N)
93.2 = 0.8
Table 7: Graph classification accuracy I on CSL [60] synthetic dataset for graph isomorphism test.
Accuracy
Memory (MB)
Throughput(teers)
GraphSAGE
80.61 + 0.16
415,94
37.69
ClusterGCN
33
78.62 0.61
10.62
156.01
GraphSAINT
75.36 0.34
10,95
143.51
FastGCN
73.46
11.54
93.05
LADIES
73.51 + 0.56
20.33
93.47
SGC 0
N7.4820.1
0.01
267.31
SIGN
76.85 = 0.56
16.21
208.52
SAGN 86
81.21 + 0.07
71.81
80.04
RUM
76.1 0.50
47.64
119.93
w/o walks
47.56
139.45
only walks
0.03
950.66 66
Table 8:
Node classification accuracy and efficiency OGB-PRODUCTS [55
# params
Cora
Photo
GCN
48K
87.14 + 1.01
88.26 + 0.83
GAT
49K
88.03 + 0.79
90.04 + 0.68
GCNII
12
49K
88.46 + 0.82
89.94 + 0.31
RAW-GNN
87.85 1.52
LanczosNet
37
50K
87.77 1.45
93.21 + 0.85
GPR-GNN
48K
48.57
93.85 + 0.28
PP-GNN
SS
89.52 + 0.85
92.89 + 0.37
Transformer
37K
71.83 1.68
90.05 # 1.50
Graphomer
139K
67.71 1 0.78
95.20 + 4.12
Specformer
32K
88.57 + 1.01
95.48 = 0.32
23K
RUM
+20K initial proj.
89.01 +: 1.40
95.35 + 0.26
Table 9: Node classification test accuracy 1 and standard deviation with 60:20:20 random split.
D Missing mathematical arguments.
D.1 Examples of Theorem 4
Example 8.1 (Cycle detection.). k-cycll Ct is subgraph g consisting of k nodes, each with degree two. The existence of k-cycle can be determined by:
(C* C G) 1[P(Way11 Wao Wz; # Way Vi < > 0]
(17)
Example 8.2 (Diameter.). The diameter, 8g of graph G which equals the length of the longest shortes path in G, can be expressed as
5g
argmax 1=|wx Jaiz, Alare Nest
Wwll
(18)
D.2 Proof of Theorem 4
Proof. First, we enumerate all possible unlabelled graphs with three nodes satisfying Assumption one with two edges, one with three edges. (Note that there is only non-isomorphic graph with
18

---

two nodes.) Now we consider random walks of length = 3, where
P(uiu = Wuo) > 0
(19)
only stands for the graph with three edges, but not with two edges, just like Example 8.1
Furthermore, we can also distinguish between the 2-degree node and the 1-degree node in the graph with edges and nodes simply by verifying that
P(wus & Wus) > 0
(20)
only stands when 02 is the 2-degree node.
Moving on the labeled 3-node graph case, can reduce the problem to investigate whether RUM can distinguish 3-node graphs that are isomorphic when unlabeled, but non-isomorphic when labeled. For the three-edged graph, Wr uniformly samples the labels of three nodes. For the two-edged graph, suppose the node labels are A, B, C, and we start from the node with 2 degrees B (with nodes bearing and labels locally, structurally isomorphic).
[1, = 2n, N,
(21)
10,1= = 2n 1,n E
[0,t= = 2n, E N,
P(Alw, = P(CW,,
11/2,1- 2n + E
(22)
If graphs have the same they have the same B and the same or swapped A, C. As such, we have proven Theorem 4 for graphs with 3 nodes.
Now we prove that Theorem 4 stand for graphs of nodes, they also stand for graphs of + nodes, the Reconstruction Conjecture
44
Suppose we have two non-isomorphic graphs with N + nodes Gi and G2 with the same RUM embedding 1 22 We enumerate all N + subgraphs with each node deleted for each of these two graphs. By the Reconstruction Conjecture, at least one pair of subgraphs are non-isomorphic. For this pair, suppose the deleted vertex is (ruling out the trivial case where the label or connectivity of u different for these two graphs), and two remaining subgraphs G)" G. since dz, &u. are injective, V = V2 implies wa, Wa are equal in distribution for G1, G2. As such, the walk distribution
P(w (w), ww(w))oo = e, wi + u 0)
(23)
-P(wz (wo), w (wo)) wo v) P(w (Wo (WI..) wa(wi (u....)ww.ru. ww (WI...), wi # u, 0)
(24)
also equal in distribution for G1, Gz-
there is a link between v and the nodes in 92,92, we assign new label to contain both the old label and the connection. As such, if the second term is not equal in distribution for G G2, we would have
v(g)") + wg)").
(25)
which is in conflict with the assumption that Theorem 4 stands for graphs with N nodes.
19

---

D.3
Proof of Lemma 6
Proof. By the definition of Dirichlet energy (Equation and non-contractive mappings (Definition
(()(
Σ
(X.)) (w (X.))l2
(26)
N
Σ
[If(
(X,))1
(27)
N
Σ
d (w> (w(ww(X)))] (2
(28)
Σ
11
Σ
p(w)X,, u E ()) 2z(
Σ
p E w)ll
W,0EEg
[w)/|//=1,,)=
(29)
Σ
IIC
E
EE))
Σ
pl)) E w)ll
N
u,vEEg
(30)
(
(31)
The last inequality is due to the fact that &s is non-contractive w.r.t. all, and therefore, the last element of the sequence, which are always X, and X,..
20

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We have claimed the theoretical and experimental advantage of RUM, which have been illustrated and $ respectively.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
In the Limitations paragraph in
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
21

---

The assumptions are presented in Assumpsions 3 The proofs are given in the Appendix $D.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The details are given in Appendix A with the code for all models and experiments given in htttps://aoonymoottt 4open. science/r/rum-8344
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
22

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
4open seieenscienne/rr rum 834D All data from public benchmark datasets, as discussed $
Justification:
The code is open source at
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
ollicy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
t/nips.ccppbbll cidoli///gdddss/odeebbmii
hat////oooSueiisseeeeeee weabbbimssiiee SttSSuabissoooooiiiioo.. onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The experimental details are described in Appendix A
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
All error bars of real-world benchmarks are included the results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
23

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: The type of compute is detailed in Appendix the speed and resource requirements of our model.
for discussion on A See $
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http:ppss//oorrppps.ppppppleee.e
Answer: [Yes]
Justification: The Code of Ethics have been closely followed in every step of this research project.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
See the Social Impact paragraph in
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All datasets used in this work is open-source and has been properly cited.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, thcoe com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
25

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No new assets released.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: No human subjects are involved.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not pose risks incurred by study participants.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
26


Reviews:
[{"review_id": "TwXoB3tFfG", "reviewer": "Reviewer_P1Jd", "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.", "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 \nconventional 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].\n\nRef.\n[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.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "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.\n\nQuality: 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.\n\nClarity: 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.\n\nSignificance: 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.\n\nRef.\n[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\n[2] \"Do Transformers Really Perform Bad for Graph Representation?\", Chengxuan Ying et. al., 2021, https://arxiv.org/abs/2106.05234", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n\n## Comparison with graph transformers.\n> Weakness: The paper lacks a discussion on the proposed method and Graph Transformer architectures.\n\nMany 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:\n\n---\n**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. \n\nBecause 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.\n\n---\n\nWe 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:\n\n|             | Texas         | Wisc.         | Cornell       |\n|-------------|---------------|---------------|---------------|\n| GCN         | 55.1 ± 4.2    | 51.8 ± 3.3    | 60.5 ± 4.8    |\n| GAT         | 52.2 ± 6.6    | 51.8 ± 3.1    | 60.5 ± 5.3    |\n| GCNII       | 77.6 ± 3.8    | 80.4 ± 3.4    | 77.9 ± 3.8    |\n| Geom-GCN    | 66.8 ± 2.7    | 64.5 ± 3.7    | 60.5 ± 3.7    |\n| PairNorm    | 60.3 ± 4.3    | 48.4 ± 6.1    | 58.9 ± 3.2    |\n| GPS| 75.4 ±1.5 | 78.0 ±2.9 | 65.4 ±5.7|\n|Transformer| 77.8 ±1.1 | 76.1 ±1.9 | 71.9 ±2.5 |\n|Graphomer| 76.8 ±1.8 | 77.7 ±2.0 | 68.4 ±1.7 |\n| RUM         | 80.0 ± 7.0    | 85.8 ± 4.1    | 71.1 ± 5.6    |\n\nThe 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.\n\nFor 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:\n\n| Method            | #param. | AUC (%)      |\n|-------------------|---------|--------------|\n| GCN-GraphNorm     | 526K    | 78.83 ± 1.00 |\n| PNA               | 326K    | 79.05 ± 1.32 |\n| PHC-GNN           | 111K    | 79.34 ± 1.16 |\n| DeeperGCN-FLAG    | 532K    | 79.42 ± 1.20 |\n| DGN               | 114K    | 79.70 ± 0.97 |\n| GIN-VN (fine-tune)| 3.3M    | 77.80 ± 1.82 |\n| Graphormer-FLAG   | 47.0M   | 80.51 ± 0.53 |\n| RUM | 87K | 80.01 ± 1.20 |\n\n## Out-of-date SOTA reference\n> 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\n\nMany 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.", "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": "mU1jl80BVY", "reviewer": "Reviewer_wXB7", "summary": "The paper introduced a new graph neural network that is not based on convolution but on the random walk. Based on the results of the extensive experiment, the proposed architecture is effective for heterophilic graphs and long-range graphs.", "questions": "Can the proposed method work well on directed and weighted graphs?", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The experiment results include different tasks on different graphs, also, it is faster than baselines.\n2. Theoretical analysis is conducted to show that the proposed architecture is more expressive.\n3. Theoretical analysis shows that the proposed architecture is effective in overcoming over-squashing and over-smoothing issues.", "weaknesses": "Currently, the proposed architecture only works on unweighted and undirected graphs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n> Currently, the proposed architecture only works on unweighted and undirected graphs.\n\n> Can the proposed method work well on directed and weighted graphs?\n\n**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.\n\n**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}$: \n\n$P(v_j | (v_0, ..., v_{i-1})) \\propto I [(v_i, v_j) \\in E_G] * w_{ij} / D(v_i) $\n\nWe plan to include this equation in our **Section 3: Architecture** to clarify that RUM can indeed run on weighted graphs. \n\nTo 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!", "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": "Ak47AGuNm9", "reviewer": "Reviewer_xhjS", "summary": "The paper introduces Random Walk with Unifying Memory (RUM), a non-convolutional graph neural network (GNN) that addresses limitations like limited expressiveness, over-smoothing, and over-squashing typically associated with convolution-based GNNs. RUM leverages random walks and recurrent neural networks (RNNs) to merge topological and semantic graph features, theoretically showing and experimentally verifying its enhanced expressiveness over traditional methods like the Weisfeiler-Lehman (WL) isomorphism test. It demonstrates competitive performance on node- and graph-level tasks while offering advantages in efficiency and scalability.", "questions": "1. 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?\n\n2. In practical applications, how does RUM handle graph datasets with varying degrees of sparsity? Are there specific strategies employed to ensure robust performance across different graph structures?\n\n3. 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. 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.", "limitations": "Yes, The authors have addressed several limitations in the Limitations section.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. RUM introduces a new paradigm in GNNs by eliminating convolutions and leveraging random walks and RNNs for enhanced graph representation.\n\n2. The presentation of the paper is generally clear and coherent. The authors effectively contextualize their work relative to existing literature, highlighting the novelty of RUM and its contributions to the field of graph representation learning.\n\n3. The theoretical advancements (e.g., expressiveness proofs) and empirical results clearly demonstrate the advantages of RUM over traditional convolutional GNNs. The findings are valuable for advancing graph representation learning techniques and are likely to influence future research directions.", "weaknesses": "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. Additionally, while the paper highlights RUM's superiority over expressive GNNs in specific scenarios, it overlooks potential limitations when compared to these models, such as not thoroughly investigating upper bounds on the WL test, which could gauge RUM's discriminative power against more expressive GNNs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n\n## The impact of random walk lengths.\n> 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.\n\n> 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?\n\nWhen 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. \n\nFigure 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.\n\nApart 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:\n- 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$.\n- Figure 2: The impact of $L$ on Dirichlet energy.\n- Figure 3: The impact of $L$ on experimental performance.\n- Figure 4: The impact of $L$ on efficiency.\n\nWe 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_.\n\n---\nThe 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$:\n- 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$. \n- 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.\n- 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.\n---\n\n\n## The impact of sparsity. \n> In practical applications, how does RUM handle graph datasets with varying degrees of sparsity? \n\n> 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.\n\nIn 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.\n\n> Are there specific strategies employed to ensure robust performance across different graph structures?\n\nAs shown in Appendix Section B1, two forms of regularization are employed to ensure consistency:\n- 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_\n- Consistency regularization: Variance among predictions given by different random walk samples is penalized.\n\n\n## Expressiveness comparison with the WL test\n> 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.\n\nWe 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\\]? \n\nIf 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:\n\n**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.\n\nReferences:\n\\[1\\] Morris et al. 2018 Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks", "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": "ly4B56lsYa", "reviewer": "Reviewer_jBUd", "summary": "This paper proposes a random walk-based graph neural network, where an RNN is used to combine the topological and semantic graph features along the walks. The proposed RUM model is free of convolution operators and does not suffer from the limited expressiveness, over-smoothing, and over-squashing, which are commonly faced issues in convolution-based GNNs.", "questions": "1. In Lemma 6, the author shows that RUM increases Dirichlet energy. Why would this be helpful intuitively? As for homophily graphs, GNNs should decrease the Dirichlet energy. This phenomenon is also analyzed in [1,2]. It seems RUM is not just alleviating over-smoothing, but is anti-smoothing.\n2. In line 243, the author claims that RUM almost always outperforms SOTA architectures, this is not true according to the results.\n\n[1] Interpreting and unifying graph neural networks with an optimization framework\n\n[2] A Unified View on Graph Neural Networks as Graph Signal Denoising", "limitations": "The authors adequately discussed the limitations.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper proposes a non-convolutional GNN, named RUM. The benefits of this model over convolutional GNNs are elaborated both theoretically and empirically.", "weaknesses": "Empirically, the gains with RUM are marginal and in some cases, RUM is worse than the baselines.\n\nThe organization and the presentation of the paper can be further improved.\n1. There are too many hyper-references. Most of the hyper-references in Section 1 and Section 2 are unnecessary, especially when reading the paper for the first time.\n2. There are too many supplementary demonstrations (...) Some additional information could be helpful, but too many will hinder the reading. It would be better to reorganize the sentences to make the presentation smoother.\n3. There are some grammar mistakes, like in line 244. Proofreading is needed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n## Comparison with state-of-the-art models.\n> Empirically, the gains with RUM are marginal and in some cases, RUM is worse than the baselines.\n\n>In line 243, the author claims that RUM almost always outperforms SOTA architectures, this is not true according to the results.\n\nAmong 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:\n- 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.\n- 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.\n- In **Table 4**, RUM is singularly outperformed by GCNII on one of the three tasks.\n\nAs 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.\n- **Efficiency.** RUM is faster than even the simplest convolutional GNNs on GPUs.\n- **Robustness** naturally afforded by the stochasticity. (Figure 6)\n\nNote that the competitive performance is further demonstrated in the new results provided in the rebuttal period (see the PDF).\n\n## Clarification on over-smoothing\n>In Lemma 6, the author shows that RUM increases Dirichlet energy. Why would this be helpful intuitively?\n\nIn 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. \n\nIn 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.\n\nIn 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.\n\nTo 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.\n\n## Presentation clarity.\n> The organization and the presentation of the paper can be further improved.\n\n> There are too many hyper-references.\n\n> There are too many supplementary demonstrations\n\nWe 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.\n\nMeanwhile, 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.\n\nWe 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.\n\nReferences:\n\\[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.", "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:
Thank you, all reviewers, for your constructive and detailed feedback, based on which we are further revising our manuscript for better clarity.

---
# Recap: Main contributions
With the common pitfalls of convolutional graph neural networks (GNN) identified, a new graph learning paradigm is designed, completely free of the convolution operator, coined *random walk with unifying memory* (RUM). With RUM, the topological (represented by _anonymous experiments_) and semantic features along random walks terminating at each node are merged by an RNN to form node representations. 

We show that RUM has the following desired properties, with all experimentally validated and (1-3) also theoretically proven:
1. RUM is more expressive than ($k$-dimensional) Weisfeiler-Lehman ($k$-WL)-equivalent GNNs
2. RUM alleviates over-smoothing
3. RUM alleviates over-squashing
4. RUM has linear complexity w.r.t. the number of nodes and is faster than the simplest GNN on GPUs.
5. RUM is robust to random attacks on the graph structure.
6. RUM can be scaled to huge graphs with millions of nodes out-of-the-box and is naturally compatible with node mini-batching

In 8 tables totaling 21 benchmark experiments, we show that RUM achieves competitive performance across real-world graph- and node-level classification and regression tasks.

---
# New results in the rebuttal period: Graph transformer comparison, effect of the walk length, and $k$-WL comparison (see [the PDF](https://openreview.net/attachment?id=TStdjnCJG6&name=pdf))
## Graph Transformer comparison (`P1Jd`)
To compare RUM's performance with graph transformer models (`P1Jd`), Table 4 is expanded [in the separate PDF](https://openreview.net/attachment?id=TStdjnCJG6&name=pdf) to show that RUM outperforms graph transformer models on heterophilic datasets. A new table on `MolHIV` is also added to show that RUM achieves competitive performance on molecular graph regression tasks with a fraction of the parameter budget as Graphomer.

Conceptually, in the **Introduction & Related works** sections, RUM is currently being compared to convolutional GNNs, walk- and path-based GNNs, stochastic and constant-energy regularization methods, and graph rewiring methods. We thank Reviewer `P1JD` again for your valuable suggestion that RUM should be conceptually compared with graph transformers as they are well-known methods for solving over-smoothing and over-squashing that are also not locally convolutional. The discussion paragraph to be included in the updated manuscript can be found in this [separate rebuttal](https://openreview.net/forum?id=JDAQwysFOc&noteId=X8kKjbnpxZ).

---
## The effect of $L$, the length of the random walks, on molecular graph regression (`xhjS`)
An **Appendix Figure** is added to the PDF to show the impact of $L$ over the performance on a molecular graph regression task---ESOL. This also shows that for molecular graphs, because of the existence of long-term dependencies, the optimal $L$ is usually larger, compared to that of citation graphs (Figure 4). A recipe to narrow the hyperparameter search space of $L$ is provided [here](https://openreview.net/forum?id=JDAQwysFOc&noteId=4HQMSRau91).

---
## A more quantitative comparison with $k$-WL test (`xhjS`)
The **Corollary 4.1** is rewritten according to the suggestions from Reviewer `xhjS` to be quantitative linked with $k$-WL test:

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

---


The rest of your suggestions are addressed as follows:

## Limitations: weighted and directed graphs. (`wXB7`)
With some slight modifications, RUM works on both *weighted* and *directed* graphs.

**Weighted graphs** are excluded in **Assumption 3** only for the clarity and simplicity of theoretical arguments. RUM can be easily extended to weighted graphs by sampling a **biased random walk** with edge weights $w_{ij}$ and keeping rest of the algorithm the same:
$P(v_j | (v_0, ..., v_{i-1})) \propto I [(v_i, v_j) \in E_G] * w_{ij} / D(v_i)$

**Directed graphs** are already included in the benchmarks (**Tables 4 and 8**, where RUM achieves competitive performance) with a slight modification---the edges are symmetrized with new, artificial edges annotated.

---
## Clarification on the non-diminishing Dirichlet energy (`jBUd`)
We plan to add more explanation around Lemma 6 to clarify that, higher Dirichlet energy doesn't mean better, and RUM does not *always* increase the Dirichlet energy but *is possible to maintain* a non-diminishing Dirichlet energy when non-contractive RNNs are prescribed as backbones, whereas for traditional convolutional GNNs, the Dirichlet energies are destined to diminish as the number of message-passing rounds increases (Figure 2).

---

Lastly, we apologize for the somewhat convoluting reading experience of this version of the manuscript (`jBUd`)---it has been drastically condensed to fit the page limit. As a result, many substantial results had to be moved to the **Appendix** and the **Introduction** section also doubles as a problem statement and a preliminary. We plan to straighten out many of the verbose sentences, reduce hyper-references and supplementary demonstration, and better highlight the best-performing models (`P1Jd`).

We hope that you will consider raising your score to see these valued suggestions of yours incorporated and representation improved in the next iteration of the manuscript. 

Thank you again, all reviewers, for your time, effort, helpful feedback, and for helping us improve this manuscript together.

Meta-review: The paper presents a non-convolutional graph layer, which extracts topological and semantic information from random walks over the graph and aggregates them with recurrent layers. They show the layer compares favorably to standard models, in terms of accuracy, complexity, and expressiveness. 

The paper had a very favourable round of review, which further improved with the rebuttal - all reviewers recommend acceptance with no remaining concerns. The rebuttal has strengthened the paper, most notably with the inclusion of graph transformer baselines (reviewer `P1Jd`) and hyper-parameters selection (reviewer `xhjS`).

I think the paper has a good organization, the contribution is sufficiently novel, and the theoretical analysis is strong. Overall, I believe this is a very interesting paper for the GNN community at NeurIPS and I recommend its acceptance following some minor language editing (e.g., "reception" field or the first sentence in the abstract).
Decision: Accept (spotlight)