## Non-convolutional Graph Neural Networks

## Yuanqing Wang

## Kyunghyun Cho

Center for Data Science and Simons Center for Computational Physical Chemistry New York University New York, N.Y. 10004 wangyq@wangyq.net

Center for Data Science, New York University and Prescient Design, Genetech New York, N.Y. 10004 kc119@nyu.edu

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

## 1 Introduction: Convolutions in GNNs

Graph neural networks (GNNs) [1, 2, 3, 4, 5]-neural models operating on representations of nodes ( V ) and edges ( E ) in a graph (denoted by G = {V E} E ⊆ V × V , , , with structure represented by the adjacency matrix A ij = ✶ [( v , v i j ) ∈ 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 |× D are aggregated based on the structure of local neighborhoods:

$$X ^ { \prime } = \hat { A } \mathbf X.$$

Here, ˆ A displays a unique duality-the input features doubles as a 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 ( ˆ A ) of the original adjacency matrix ( A )-the normalized Laplacian for graph convolutional networks (GCN) [1], a 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 a few. For all such transformations, it is easy to verify that permutation equivariance (Equation 9) is 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 1) Xu et 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

Table 1: Schematic illustration of RUM. All 4-step unbiased random walks from the 2-degree carbon atom in the (hydrogen-omitted) chemical graph of propylene oxide , a 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 ( ω x ) and topological ( ω u ) representations of each walk are shown.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00165v3-figure-63221c1a-282e-4e77-8060-245f0fb82ea2.jpg)

as expressive as the WL test [10]. As such, crucial local properties of graphs meaningful in physical and social modeling, including cycle sizes (Example 8.1) and diameters (Example 8.2) [11], cannot be realized by convolution-based GNNs.

Over-smoothing. (Figure 2) As one repeats the convolution (or Laplacian smoothing) operation (Equation 1), sandwiched by linear and nonlinear transformations, the inter-node dissimilarity, measured by Dirichlet energy,

$$\mathcal { E } ( \mathbf X ) = \frac { 1 } { N } \sum _ { ( u, v ) \in \mathcal { E } _ { \mathcal { G } } } \| \mathbf X _ { u } - \mathbf X _ { \mathbf v } \| ^ { 2 },$$

will decrease exponentially as the number of message-passing steps l increases [12, 13], E ( X ( ) l ) ≤ C 1 exp( -C l 2 ) with some constants C 1 2 , , resulting in node representations only dependent upon the topology, but not the initial embedding.

Over-squashing. (Figure 5) As the number of Laplacian smoothing grows, the reception field of GNNs increases exponentially, while the dimension of node representation, and thereby the possible combinations of neighborhood environment, stays unchanged [14]. Quantitatively, Topping et al. [15] quantifies this insight using the inter-node Jacobian and relates it to the powers of the adjacency matrix through sensitivity analysis :

$$| \frac { \partial \mathbf X _ { v } ^ { ( l + 1 ) } } { \partial \mathbf X _ { u } ^ { ( 0 ) } } | \leq | \nabla \phi | ^ { ( l + 1 ) } ( \hat { A } ^ { l + 1 } ) _ { u v },$$

where ϕ is the node-wise update function, whose Jacobian is typically diminishing. If this Equation 3 converges to zero, the node representation is agnostic to the changes happening l 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 1) at all. 1 Specifically, we stochastically sample a random walk terminating at each node and use the anonymous experiment associated with the random walk to describe its topological environment. This is combined with the semantic representations along the walk and fed into a recurrent neural network layer [16] to form the node embedding, which we 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 to the popular convolution-based GNNs.

## 2 Related works: ways to walk on a graph

Walk-based GNNs. RAW-GNN ([17], compared and outperformed in Table 9) also proposes walk-based representations for representing node neighborhoods, which resembles our model without the anonymous experiment ( ω u in Equation 5). CRaWl ([18, 19], outperformed in Table 3) also incorporates a similar structural encoding for random walk-generated subgraphs to feed into an

1 Code at: https://github.com/yuanqing-wang/rum/tree/main

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, respectively. More elaborately, [22] and AgentNet ([23], Table 3) use agent-based learning on random 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], Table 3) 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 a 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 kernel -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 message-passing scheme. Interestingly, most of these works are either not applicable to, or have not been tested on, node-level tasks. In the experimental § 5, we show that RUM not only outperforms these baselines on most graph-level tasks (Table 3) but also competes with a wide array of state-of-the-art convolutional GNNs on node-level tests (Table 2). Moreover, random walk kernelbased architectures, which explicitly enumerate random walk-generated subgraphs are typically much slower than WL-equivalent convolutional GNNs, whereas RUM is faster than even the simplest variation of convolutional GNN (Figure 4).

State-of-the-art methods to alleviate oversmoothing. Stochastic regularization. DropEdge ([26], Figure 2) 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. [27, 28] and GPR-GNN ([29], Appendix Table 9) rewire the graph using personalized page rank algorithm [30] and generalized page rank on graphs, respectively. Similar to JKNet [31], they mitigate over-smoothing by allowing direct message passing between faraway nodes. Constant-energy methods. Zhao and Akoglu [32], Rusch et al. [33] constrain the pair-wise distance or Dirichlet energy among graphs to be constant. Nevertheless, the 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. [13]. Residual GNNs. Residual connection [34] can naturally be added to the GNN architecture, such as GCNII ([35], Table 2), 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 G is a sequence of nodes w = ( v , v 0 1 , . . . ) with landing probability:

̸

P v ( j | ( v , . . . , v 0 i -1 )) = ✶ [( v , v i j ) ∈ E G ] /D v ( i ) , (4) where D v ( i ) = ∑ A ij is the degree of the node v i . Walks originating from or terminating at any given node v can thus be easily generated using this Markov chain. We record the trajectory of embeddings associated with the walk as ω x ( w ) = ( X i ) = ( X 0 , X 1 , . . . , X l ) . In this paper, we only consider finite-long l -step random walk | w | = l ∈ Z + . In our implementation, the random walks are sampled ad hoc during each training and inference step directly on GPU using Deep Graph Library [36] (see Appendix § A). Moreover, the walk considered here is not necessarily a path , as repeated traversal of the same node v i = v , i j = j is not only permitted, but also crucial to effective topological representation, as discussed below.

Anonymous experiment. We use a function describing the topological environment of a walk, termed anonymous experiment [37], ω u ( w ) : R l → R l that records the first unique occurrence of a node in a walk (Appendix Algorithm C). To put it plainly, we label a 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 tensor-accelerating framework in one

line ( w is the node sequence of a walk) and trivially parallelized 2 : (1*(w[..., :,None]==w[..., None,:])).argmax(-1)

Unifying memory: combining semantic and topological representations. Given any walk w , we now have two sequences ω x ( w ) and ω u ( 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 1):

$$h ( w ) = f ( \phi _ { x } ( \omega _ { x } ( w ) ), \phi _ { u } ( \omega _ { u } ( w ) ) ),$$

where ϕ x : R l × D → R D x maps the sequence of semantic embeddings generated by a l -step walk to a fixed D x -dimensional latent space, ϕ u : R l → R D u maps the indicies sequence to another latent space D u , and f : R D x ⊕ R D u → R D 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 l -step ( l being a hyperparameter) walks terminating (for the sake of gradient aggregation) at that node:

$$\psi ( v ) = \sum _ { \{ w \}, | w | = l, w _ { l } = v } p ( w ) h ( w ),$$

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 ( y | \mathcal { G }, \mathbf X ) = \sum _ { \{ w \}, | w | = l, w _ { l } = v } p ( w ) p ( y | \mathcal { G }, \mathbf X, w )$$

The node representation can be summed

$$\Psi ( \mathcal { G } ) = \sum _ { v \in \mathcal { V } \subseteq \mathcal { G } } \psi ( v )$$

to form global representations for graph classification and regression. We call ψ in Equation 6 and Ψ in Equation 8 the node and graph output representations of RUM.

Layer choices. Obvious choices to model f include a feed-forward neural network after concatenation, and ϕ , ϕ x u recurrent neural networks (RNNs). This implies that, different from most convolutional GNNs, parameter sharing is natural and the number of parameters is going to stay constant as the model incorporates a larger neighborhood. Compared to dot product-based, transformer-like modules [38], 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 to the origin have stronger impact on the representation. The gated recurrent unit (GRU)[16] variant is used everywhere in this paper. Additional regularizations are described in Appendix § B.1.

Runtime complexity. To generate random walks for one node has the runtime complexity of O (1) , and for a graph O |V| ( ) , where |V| is the number of nodes in a 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 ϕ , ϕ x u , the overall complexity is O |V| ( lkD ) where l is the length of the random walk, k the samples used to estimate Equation 6, and D the latent size of 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 |V| ) for runtime complexity, and is therefore agnostic to the sparsity of the graph. See Figure 4 for an empirical verification of the time complexity. In Appendix Table 8, we 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.

2 Note that this particular implementation introduces an intermediate O ( l 2 ) complexity term, though it is empirically faster than the linear-complexity naive implementation, since only integer indices are involved and thus the footprint is negligible.

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 [39]. 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, or on subsets. Empirically, in Appendix Table 8, RUM can be naturally scaled to huge graphs.

## 4 Theory: RUM as a joint remedy.

We have insofar designed a new graph learning framework-convolution-free graph neural networks (GNNs) that cleanly represent the semantic ( ω x ) and topological ( ω u ) 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

$$P \mathbf X _ { v } ( \mathcal { G } ) = \mathbf X _ { v } ( P ( \mathcal { G } ) ),$$

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-based GNNs by showing that: (a) the topological representation ω u is more expressive than convolutional-GNNs in distinguishing non-isomorphic graphs; (b) the semantic representation ω x no longer suffers from over-smoothing and over-squashing.

## 4.1 RUMis more expressive than convolutional GNNs.

For the sake of theoretical arguments in this section, we assume that in Equation 5:

Assumption 2. ϕ , ϕ x u , f are universal and injective.

Assumption 3. Graph G discussed in this section is always connected, unweighted, and undirected.

̸

Assumption 2 is easy to satisfy for feed-forward neural networks [40] and RNNs [41]. Composing injective functions, we remark that h w ( ) is also injective w.r.t. ω x ( w ) and ω u ( w ) ; despite of Assumption 3, our analysis can be extended to disjointed graphs by restricting the analysis to the connected regions in a graph. Under such assumptions, we show, in Remark 8 (deferred to the Appendix), that ψ is injective , meaning that nodes with different random walks will have different distributions of representations ψ v ( 1 ) = ψ v ( 2 ) . We also refer the readers to the Theorem 1 in Micali and Zhu [37] for a discussion on the representation power of anonymous experiments on unlabelled graphs. Combining with the semantic representations and promoting the argument from a node level to a graph level, we arrive at:

Theorem 4 (RUMcan distinguish non-isomorphic graphs) . Up to the Reconstruction Conjecture [42], RUM with sufficiently long l -step random walks can distinguish non-isomorphic graphs satisfying Assumption 3.

The main idea of the proof of Theorem 4 (in Appendix § D.2) involves explicitly enumerating all possible non-isomorphic structures for graphs with 3 nodes and showing, by induction, that if the theorem stands for graph of N -1 size it also holds for N -sized graphs. We also show in Appendix § D.1 that a number of key graph properties such as cycle size (Example 8.1) and radius (Example 8.2) that convolutional GNNs struggle [43, 44] to learn can be analytically expressed using ω u . As these are solely functions of ω x , they can be approximated arbitrarily well by universal approximators. These examples are special cases of the finding that RUM is stricly more expressive than Weisfeiler-Lehman isomorphism test [9]:

Corollary 4.1 (RUM is more expressive than WL-test) . Two graphs with N nodes G 1 , G 2 labeled as non-isomorphic by Weisfeiler-Lehman isomorphism test is the necessary, but not sufficient condition that the representation resulting from RUM with walk length N +1 are also different.

̸

$$\Psi ( \mathcal { G } _ { 1 } ) \neq \Psi ( \mathcal { G } _ { 2 } )$$

Thus, due to Xu et al. [2], RUM is also more expressive than convolutional GNNs in distinguishing non-isomorphic graphs. This also confirms the intuition that RUM with longer walks are more expressive. (See Figure 3 on an empirical evaluation.) The proof of this corollary is straightforward to sketch-even if we only employ the embedding trajectory ω x , it would have the effect of performing the function ϕ x in Equation 5 on each traversal of the WL expanded trees.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00165v3-figure-73c1f4f6-6ee4-4e99-b9f0-f658efdf9a3a.jpg)

Figure 1: RUMcan(in closed form), whereas the Weisfeiler-Lehman (WL) isomorphism test and WL-equivalent GNNs cannot , distinguish these two graphsan illustration of Example 8.1 .

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00165v3-figure-9234adeb-5b5f-4025-8fa9-a24aac64bba6.jpg)

Figure 2: RUMalleviates over-smoothing . Dirichlet energy ( E ) on Cora [45] graph plotted against L , the number of steps or layers.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00165v3-figure-06d35e87-5d26-4c52-8286-dfced4bea19e.jpg)

## 4.2 RUMalleviates over-smoothing and over-squashing

Over-smoothing refers to the phenomenon where the node dissimilarity (e.g., measured by Dirichlet energy in 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].

$$\mathcal { E } ( ( 1 - \tilde { \Delta } ) \mathbf X ) & \leq ( 1 - \lambda ) ^ { 2 } \mathcal { E } ( \mathbf X ) & ( 1 1 )$$

where λ is the smallest non-zero eigenvalue of ˜ ∆ , the normalized Laplacian of a graph.

Free of convolution operators, it seems only natural that RUM does not suffer from this symptom (Figure 2). We now formalize this intuition by first restricting ourselves to a class of non-contractive mappings for f in Definition 5.

Definition 5. A map f is non-contractive on region Ω if ∃ α ∈ [1 , + ∞ ) such that | f ( x ) -f ( y ) | ≥ α x || - || ∀ y , x, y ∈ Ω .

A line of fruitful research has been focusing on designing non-contractive RNNs [46, 47], and to be non-contractive is 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 in 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-smoothing.) . If ϕ , f x are non-contractive w.r.t. all elements in the sequence, the expected Dirichlet energy of the corresponding RUM node representation in Equation 6 is greater than its initial value

$$E ( \mathcal { E } ( \psi ( \mathbf X ) ) ) \geq \mathcal { E } ( \mathbf X ).$$

This implies that the expectation of Dirichlet energy does not diminish even when l → + ∞ , as it 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 internode Jacobian | ∂ X ( +1) l v /∂ X (0) u | decays slower as the distance between u, v grows vis-` a-vis the convolutional counterparts. Briefly, although RUM does not address the information bottleneck with exponentially growing reception field (the 1 / A ( ˆ l +1 ) uv term in Equation 16), it nevertheless can have a non-vanishing (nor exploding) gradient from the aggregation function ( |∇ ϕ x | ).

## 5 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 § 4: Q1: Is 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 [45], as well as the coauthor [48] and co-purchase [49] datasets common in social modeling. Additionally, we hypothesize that RUM, without the smoothing operator, will perform competitively on heterophilic datasets [50]-we test this hypothesis. For graph classification, we benchmark on the popular TU dataset [51]. We also test the graph regression performance on molecular datasets in MoleculeNet [52] and Open Graph Benchmark [53]. In sum, RUMalmost always outperforms, is within the standard deviation of, the state-of-the-art architectures, as shown in Tables 2, 3, 4, 5, as well as in Tables 6, 7, 8, 9 moved to the Appendix due to space constraint.

On sparsity: the subpar performance on the Computer dataset. The most noticeable exception to the good performance of RUM is that on the Computer co-purchase [49] dataset, where RUM is outperformed even by GCN and GAT. This dataset is very dense with an average node degree ( |E| / |V| ) 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 high-variance representations from RUM.

On the other hand, RUM outperforms all models surveyed in two large-scale benchmark studies on molecular learning, GAUCHE [54] and MoleculeNet [52]. The atoms in the molecules always have a degree of 2 ∼ 4 with intricate subgraph structures like small rings. This suggests the utility of unifying memory in chemical graphs and furthermore chemical and physical modeling.

Table 2: Node classification test set accuracy ↑ and standard deviation.

|                                       | Cora                                                         | CiteSeer                                                                             | PubMed                                                                         | Coathor CS                                                | Computer                                | Photo                                                      |
|---------------------------------------|--------------------------------------------------------------|--------------------------------------------------------------------------------------|--------------------------------------------------------------------------------|-----------------------------------------------------------|-----------------------------------------|------------------------------------------------------------|
| GCN [1] GAT [6] MoNet [55] GCNII [35] | 81 . 5 83 . 0 ± 0 . 77 . 4 ± 1 . 81 . 7 ± 0 . 5 85 . 5 ± 0 . | 70 . 3 72 . 5 ± 0 . 67 . 0 ± 1 . 70 . 0 ± 0 . 6 73 . 4 ± 0 . 6 70 . 6 74 . 2 ± 1 . 7 | 79 . 0 79 . 0 ± 0 . 76 . 6 ± 0 . 78 . 8 ± 0 . 80 . 3 ± 0 . 78 . 2 79 . 4 ± 1 . | 91 . 1 ± 0 . 5 90 . 5 ± 0 . 6 85 . 0 ± 1 . 1 90 . 8 ± 0 . | 82 . 6 ± 2 . 4 78 . 0 ± 19 . 0 83 . 5 2 | 91 . 2 ± 1 . 2 85 . 7 ± 20 . 90 . 4 ± 1 . 3 91 . 2 ± 2 . 3 |
|                                       | 7                                                            | 7                                                                                    | 3                                                                              | 93 . 2 0                                                  |                                         | 3                                                          |
| GraphSAGE [4]                         | 0                                                            | 0                                                                                    | 8                                                                              |                                                           |                                         |                                                            |
|                                       |                                                              |                                                                                      | 4                                                                              | 6                                                         | ± 2 .                                   |                                                            |
|                                       | 5                                                            |                                                                                      | 4                                                                              |                                                           |                                         |                                                            |
| PairNorm [32]                         | 81 . 1                                                       |                                                                                      |                                                                                |                                                           |                                         |                                                            |
| GraphCON [33]                         | 84 . 2 ± 1 . 3                                               |                                                                                      | 3                                                                              |                                                           |                                         |                                                            |
| RUM                                   | 84 . 1 ± 0 . 9                                               | 75 . 5 ± 0 . 5                                                                       | 82 . 2 ± 0 . 2                                                                 | ± 0 .                                                     | 77 . 8 ± 2 . 3                          | 92 . 7 ± 0 . 1                                             |

Table 3: Binary graph classification test set accuracy ↑ .

|                  | IMDB-B         | MUTAG                 | PROTEINS       | PTC            | NCI1           |
|------------------|----------------|-----------------------|----------------|----------------|----------------|
| RWK [24] GK [56] |                | 79 . 2 ± 2 . 1 81 . 4 | 59 . 6 ± 0 . 1 | 55 . 9 ± 0 . 3 |                |
|                  |                | ± 1 . 7               | 71 . 4 ± 0 . 3 | 55 . 7 ± 0 . 5 | 62 . 5 ± 0 . 3 |
| WLK [57]         | 73 . 8 ± 3 . 9 | 90 . 4 ± 5 . 7        | 75 . 0 ± 3 . 1 | 59 . 9 ± 4 . 3 | 86 . 0 ± 1 . 8 |
| AWE [20]         | 74 . 5 ± 5 . 9 | 87 . 8 ± 9 . 8        |                |                |                |
| GIN [2]          | 75 . 1 ± 5 . 1 | 90 . 0 ± 8 . 8        | 76 . 2 ± 2 . 6 | 66 . 6 ± 6 . 9 | 82 . 7 ± 1 . 6 |
| GSN [25]         | 77 . 8 ± 3 . 3 | 92 . 2 ± 7 . 5        | 76 . 6 ± 5 . 0 | 68 . 2 ± 7 . 2 | 83 . 5 ± 2 . 0 |
| CRaWl [19]       | 73 . 4 ± 2 . 1 | 90 . 4 ± 7 . 1        | 76 . 2 ± 3 . 7 | 68 . 0 ± 6 . 5 |                |
| AgentNet [23]    | 75 . 2 ± 4 . 6 | 93 . 6 ± 8 . 6        | 76 . 7 ± 3 . 2 | 67 . 4 ± 5 . 9 |                |
| RUM              | 81 . 1 ± 4 . 5 | 91 . 0 ± 7 . 1        | 77 . 3 ± 3 . 8 | 69 . 8 ± 6 . 3 | 81 . 7 ± 1 . 4 |

Graph isomorphism testing (Q1). Having illustrated in § 4 that RUM can distinguish nonisomorphic graphs, we experimentally test this insight on the popular Circular Skip Link dataset [58, 59]. 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. [58] to create an especially challenging task for GNNs. As shown in Appendix Table 7, all convolutional GNNs fail to perform

|               | Texas          | Wisc.          | Cornell        |
|---------------|----------------|----------------|----------------|
| GCN [1]       | 55 . 1 ± 4 . 2 | 51 . 8 ± 3 . 3 | 60 . 5 ± 4 . 8 |
| GAT [6]       | 52 . 2 ± 6 . 6 | 51 . 8 ± 3 . 1 | 60 . 5 ± 5 . 3 |
| GCNII [35]    | 77 . 6 ± 3 . 8 | 80 . 4 ± 3 . 4 | 77 . 9 ± 3 . 8 |
| Geom-GCN [50] | 66 . 8 ± 2 . 7 | 64 . 5 ± 3 . 7 | 60 . 5 ± 3 . 7 |
| PairNorm [32] | 60 . 3 ± 4 . 3 | 48 . 4 ± 6 . 1 | 58 . 9 ± 3 . 2 |
| RUM           | 80 . 0 ± 7 . 0 | 85 . 8 ± 4 . 1 | 71 . 1 ± 5 . 6 |

Table 4: Node classification test set accuracy ↑ and standard deviation on heterophilic [50] datasets.

Table 5: Graph regression RMSE ↓ compared with the best model studied in two large-scale benchmark studies on OGB [53] and MoleculeNet [52] datasets.

|                  | ESOL            | FreeSolv        | Lipophilicity   |
|------------------|-----------------|-----------------|-----------------|
| GAUCHE[54]       | 0 . 67 ± 0 . 01 | 0 . 96 ± 0 . 01 | 0 . 73 ± 0 . 02 |
| MoleculeNet [52] | 0 . 99          | 1 . 74          | 0 . 80          |
| RUM              | 0 . 62 ± 0 . 06 | 0 . 96 ± 0 . 24 | 0 . 66 ± 0 . 01 |

Figure 4: RUM is faster than convolutional GNNs

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00165v3-figure-ded26748-08ed-44eb-81a4-570c45fc1750.jpg)

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00165v3-figure-f23de51c-9130-47b2-970f-5a0eefdede4b.jpg)

Figure 3: Impact of number of samples and walk length. Test classification accuracy of Cora [45] with varying numbers of samples and walk length.

on GPU. Inference time over the Cora [45] graph on CPU and CUDA devices, respectively, plotted against L , the number of message-passing steps or equivalently the length of random walks. Numbers in the bracket indicate the number of sampled random walks drawn.

better than a constant baseline (there are 10 classes uniformly distributed). 3WLGNN [60], a higherorder 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 O |N| ( ) linear complexity, achieves similarly high accuracy. One can think of RUM as a stochastic approximation of the higher-order GNN, with all of its explicitly enumerated subgraphs being identified by RUM with a 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 on performance. Using Cora [45] 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 &gt; 4 yield qualitatively satisfactory results; this empirical finding has guided our hyperparameter design. In Figure 2, we also compare the Dirichlet energy of RUM-generated layer representations with not only baselines GCN [1] and GAT [6], but also strategies to alleviate over-smoothing discussed in § 2, namely residual connection and stochastic regularization [35, 26, 61], and show that when L gets large, only RUM can maintain Dirichlet energy. Traditionally, since Kipf and Welling [1] (see its Figure 5 compared to Figure 3), the best performance on Cora graph was found with 2 or 3 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.

Long-range neighborhood matching (Q3). To verify that RUM indeed alleviates over-squashing (§ B.2), in Figure 5, we adopt the tree neighborhood matching synthetic task in Alon and Yahav [14]

Figure 5: Long-range neighborhood matching training accuracy ↑ [14] with 32 unit models.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00165v3-figure-e37c5d48-b872-4772-bfbb-20c90fc9ae10.jpg)

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00165v3-figure-4a7e4a14-31fa-4b31-a70a-1ca7c5cbe627.jpg)

Figure 6: Robustness analysis . Accuracy ↑ on Cora [45] dataset with % fictitious edges added to the graph.

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 seem that RUM would be slower than convolution-based GCN due to the requirement of multiple random walk samples. This is indeed true for CPU implementations shown in Figure 4 left. When equipped with GPUs (specs in Appendix § A), however, RUM is significantly faster than even the simplest convolutional GNN-GCN [1]. It is worth mentioning that the GCN and GAT [6] results were harvested using the heavily optimized Deep Graph Library [36] sparse implementation whereas RUM is implemented na¨ ıvely in PyTorch [62], though the popular GRU component [16] have already undergone CUDA-specific optimization.

Robustness to attacks (Q5). With the stochasticity afforded by the random walks, it is natural to suspect RUM to be robust. We adopt the robustness test from Feng et al. [63] and attack by randomly adding fake edges to the Cora [45] graph and record the test set performance in Figure 6. Indeed, RUM is much more robust than traditional convolutional GNNs including GCN [1] and GAT [6] and is even slightly more robust than the convolutional GNN specially designed for robustness [63], 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 oversquashing. Most notably, our method is more expressive than the Weisfeiler-Lehman isomorphism test and can distinguish all non-isomorphic graphs up to 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 on GPUs than even the simplest convolutional GNNs (§ 5) and shows superior performance across a plethora of node- and graph-level benchmarks.

Limitations. Very dense graphs. As evidenced by the underwhelming performance of the Computer [49] dataset and discussed in § 5, RUM might suffer from high variance with very dense graphs (average degree over 15). Tottering. 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 [64]). 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 to exist for directed graphs), we would have to symmetrize the graph to

perform on directed graphs (such as the heterophilic datasets [50]); 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 are 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 is also heavily dominated by convolutional GNNs. Inspired by the superior performance of RUM on chemical datasets, we plan to apply our method in drug discovery settings [65, 66, 67, 68, 69] and furthermore on the equivariant modeling of n -body physical systems [70].

Impact statement. We here present a powerful, robust, and efficient learning algorithm on graphs. Used appropriately, this algorithm might advance the modeling of social [71] and physical [72] 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 classification with graph convolutional networks. CoRR , abs/1609.02907, 2016. URL http://arxiv.org/abs/1609.02907 .                                                                                                                            |
|-------|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [2]   | Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.00826 , 2018.                                                                                                                                                      |
| [3]   | Justin Gilmer, Samuel S Schoenholz, Patrick F 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 on 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 arXiv:1806.01261 , 2018. |
| [6]   | Petar Veliˇkovi´, c c Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Li`, o and Yoshua Bengio. Graph attention networks, 2018.                                                                                                                                                      |
| [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 http://arxiv.org/abs/1902.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. URL https://arxiv.org/abs/2106.10934 .                                                                        |
| [9]   | Boris Weisfeiler and Andrei Leman. The reduction of a graph to canonical form and the algebra which appears therein.                                                                                                                                                                            |
| [10]  | Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Li`, o and Petar Veliˇkovi´. c c 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.06157, 2020. URL https://arxiv.org/ abs/2002.06157 .                                                                                               |
| [12]  | Chen Cai and Yusu Wang. A note on over-smoothing for graph neural networks, 2020.                                                                                                                                                                                                               |
| [13]  | T. Konstantin Rusch, Michael M. Bronstein, and Siddhartha Mishra. Asurvey 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 https://arxiv.org/abs/2006.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,                                                                                                                   |

| [16]   | Kyunghyun Cho, Bart van Merrienboer, Caglar ¸ G¨lcehre, u ¸ Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using RNN encoder-decoder for statistical machine translation. CoRR , abs/1406.1078, 2014. URL http://arxiv.org/abs/1406. 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, o Martin Ritzert, Hinrikus Wolf, and Martin Grohe. Graph learning with 1d convolutions on random walks. CoRR , abs/2102.08786, 2021. URL https://arxiv.org/ abs/2102.08786 .                                                                                                                                                                                                    |
| [19]   | Jan T¨nshoff, o 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 a walk and arrive at the answer: Reasoning over paths in knowledge bases using reinforcement learning, 2018.                                                                                                                                     |
| [23]   | Karolis Martinkus, P´l a Andr´s a 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, Inc., 2020. URL https://proceedings.neurips.cc/paper_files/paper/2020/file/ ba95d78a7c942571185308775a97a3a0-Paper.pdf . |
| [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.1109/tpami.2022.3154319. URL http://dx.doi.org/10.1109/TPAMI.2022.3154319                              |
| [26]   | Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. The truly deep graph con- volutional networks for node classification. CoRR , abs/1907.10903, 2019. URL http: //arxiv.org/abs/1907.10903 .                                                                                                                                                                                            |
| [27]   | Johannes Gasteiger, Aleksandar Bojchevski, and Stephan G¨nnemann. u Predict then propagate: Graph neural networks meet personalized pagerank, 2022.                                                                                                                                                                                                                                           |
| [28]   | Johannes Gasteiger, Stefan Weißenberger, and Stephan G¨nnemann. u Diffusion improves graph learning, 2022.                                                                                                                                                                                                                                                                                    |
| [29]   | Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Joint adaptive feature smoothing and topology extraction via generalized pagerank gnns. CoRR , abs/2006.07988, 2020. URL https://arxiv.org/abs/2006.07988 .                                                                                                                                                                           |
| [30]   | 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. semanticscholar.org/CorpusID:1508503 .                                                                                                                                                                              |
| [31]   | Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. CoRR abs/1806.03536, 2018. URL http://arxiv.org/abs/1806.03536 .                                                                                                                                                     |
| [32]   | Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. CoRR abs/1909.12223, 2019. URL http://arxiv.org/abs/1909.12223 .                                                                                                                                                                                                                                                    |
| [33]   | T. Konstantin Rusch, Benjamin Paul Chamberlain, James Rowbottom, Siddhartha Mishra, and Michael M. Bronstein. Graph-coupled oscillator networks. CoRR , abs/2202.02296, 2022. URL https://arxiv.org/abs/2202.02296 .                                                                                                                                                                          |
| [34]   | Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. CoRR , abs/1512.03385, 2015. URL http://arxiv.org/abs/1512.03385 .                                                                                                                                                                                                                       |
| [35]   | Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks, 2020.                                                                                                                                                                                                                                                                        |

| [36]   | 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.                                                                                                                                                                                                          |
|--------|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [37]   | Silvio Micali and Zeyuan Allen Zhu. Reconstructing markov processes from independent and anonymous experiments. Discrete Applied Mathematics , 200:108-122, 2016. ISSN 0166-218X. doi: https://doi.org/10.1016/j.dam.2015.06.035. URL https://www.sciencedirect.com/ science/article/pii/S0166218X15003212 .                                                                                                                                                                             |
| [38]   | 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. URL http://arxiv.org/abs/1706.03762 .                                                                                                                                                                                                                                                              |
| [39]   | 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.                                                                                                                                                                                                                                                                                      |
| [40]   | Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural networks , 2(5):359-366, 1989.                                                                                                                                                                                                                                                                                                                                  |
| [41]   | Anton Maximilian Sch¨fer a and Hans Georg Zimmermann. Recurrent neural networks are universal approximators. In Artificial Neural Networks-ICANN 2006: 16th International Conference, Athens, Greece, September 10-14, 2006. Proceedings, Part I 16 , pages 632-640. Springer, 2006.                                                                                                                                                                                                     |
| [42]   | Paul J Kelly. A congruence theorem for trees. 1957.                                                                                                                                                                                                                                                                                                                                                                                                                                      |
| [43]   | Andreas Loukas. What graph neural networks cannot learn: depth vs width. CoRR , abs/1907.03199, 2019. URL http://arxiv.org/abs/1907.03199 .                                                                                                                                                                                                                                                                                                                                              |
| [44]   | Vikas K. Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks, 2020.                                                                                                                                                                                                                                                                                                                                                          |
| [45]   | Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. CoRR , abs/1603.08861, 2016. URL http://arxiv.org/abs/1603. 08861 .                                                                                                                                                                                                                                                                                                  |
| [46]   | 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.                                                                                                                                                                                                                                                                                                        |
| [47]   | Ant´nio o H. Ribeiro, Koen Tiels, Luis A. Aguirre, and Thomas Sch¨n. o 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 https://proceedings.mlr. press/v108/ribeiro20a.html . |
| [48]   | Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan G¨nnemann. u Pitfalls of graph neural network evaluation. arXiv preprint arXiv:1811.05868 , 2018.                                                                                                                                                                                                                                                                                                                 |
| [49]   | 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 on research and development in information retrieval , pages 43-52, 2015.                                                                                                                                                                                                               |
| [50]   | Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gcn: Geometric graph convolutional networks, 2020.                                                                                                                                                                                                                                                                                                                                                           |
| [51]   | 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.                                                                                                                                                                                                                                                                                                     |
| [52]   | 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-530, 2018. doi: 10.1039/C7SC02664A. URL http://dx.doi. org/10.1039/C7SC02664A .                                                                                                                                                                                               |
| [53]   | 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. URL https://arxiv.org/abs/2005.00687 .                                                                                                                                                                                                                                      |

| [54]   | Ryan-Rhys 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 Strieth-Kalthoff, Alpha A. Lee, Bingqing Cheng, Al´n a Aspuru-Guzik, Philippe Schwaller, and Jian Tang. Gauche: A library for gaussian processes in chemistry, 2023.   |
|--------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [55]   | Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodol`, a Jan Svoboda, and Michael M. Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. CoRR , abs/1611.08402, 2016. URL http://arxiv.org/abs/1611.08402 .                                                                                                                                                                                                                                                 |
| [56]   | 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.                                                                                                                                                                                                                                                                                  |
| [57]   | 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.                                                                                                                                                                                                                                                                                                                |
| [58]   | Ryan L. Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations, 2019.                                                                                                                                                                                                                                                                                                                                                                         |
| [59]   | Vijay Prakash Dwivedi, Chaitanya K. Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks, 2022.                                                                                                                                                                                                                                                                                                                                                   |
| [60]   | Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks, 2020.                                                                                                                                                                                                                                                                                                                                                                                                |
| [61]   | Yuanqing Wang and Theofanis Karaletsos. Stochastic aggregation in graph neural networks. arXiv preprint arXiv:2102.12648 , 2021.                                                                                                                                                                                                                                                                                                                                                                        |
| [62]   | 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, o Edward Z. Yang, Zach DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. CoRR , abs/1912.01703, 2019. URL http://arxiv. org/abs/1912.01703 .                                |
| [63]   | 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 in Neural Information Processing Systems , volume 33, pages 22092-22103. Curran Associates, Inc., 2020. URL https://proceedings.neurips.cc/paper_files/paper/2020/file/ fb4c835feb0a65cc39739320d7a51c02-Paper.pdf .         |
| [64]   | Nils M. Kriege, Fredrik D. Johansson, and Christopher Morris. A survey on graph kernels. CoRR , abs/1903.11835, 2019. URL http://arxiv.org/abs/1903.11835 .                                                                                                                                                                                                                                                                                                                                             |
| [65]   | Yuanqing Wang, Josh Fass, Benjamin Kaminow, John E Herr, Dominic Rufa, Ivy Zhang, Iv´n a 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.                                                                                                                                                                                                               |
| [66]   | Kenichiro Takaba, Iv´n a Pulido, Mike Henry, Hugo MacDermott-Opeskin, John D Chodera, and Yuanqing Wang. Espaloma-0.3. 0: Machine-learned molecular mechanics force field for the simulation of protein-ligand systems and beyond. arXiv preprint arXiv:2307.07085 , 2023.                                                                                                                                                                                                                              |
| [67]   | Michael Retchin, Yuanqing Wang, Kenichiro Takaba, and John D. Chodera. Druggym: Atestbed for the economics of autonomous drug discovery. bioRxiv , 2024. doi: 10.1101/2024.05.28. 596296. URL https://www.biorxiv.org/content/early/2024/06/02/2024.05.28. 596296 .                                                                                                                                                                                                                                     |
| [68]   | Yuanqing Wang, Iv´n a 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):4160-4167, 2024.                                                                                                                                                                                                                                             |
| [69]   | Yuanqing Wang. Graph Machine Learning for (Bio)Molecular Modeling and Force Field Construction . PhD thesis, 2023. URL http://proxy.library.nyu.edu/                                                                                                                                                                                                                                                                                                                                                    |

|      | 2Fgraph-machine-learning-bio-molecular-modeling%2Fdocview%2F2789704784% 2Fse-2%3Faccountid%3D12768 . Copyright - Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works; Last updated - 2024-04-24.   |
|------|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [70] | Yuanqing Wang and John D Chodera. Spatial attention kinetic networks with e (n)-equivariance. In ICLR 2023 , 2023.                                                                                                                                   |
| [71] | Justin Grimmer, Margaret E Roberts, and Brandon MStewart. Machine learning for social science: An agnostic approach. Annual Review of Political Science , 24:395-419, 2021.                                                                          |
| [72] | Gerhard Hessler and Karl-Heinz Baringhaus. Artificial intelligence in drug design. Molecules , 23(10):2520, 2018.                                                                                                                                    |
| [73] | Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization, 2017.                                                                                                                                                                   |
| [74] | Stefan Elfwing, Eiji Uchibe, and Kenji Doya. Sigmoid-weighted linear units for neural network function approximation in reinforcement learning, 2017.                                                                                                |
| [75] | 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 ai applications, 2018.           |
| [76] | 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. |
| [77] | Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks, 2013.                                                                                                                                     |
| [78] | Sepp Hochreiter and J¨rgen u Schmidhuber. Long short-term memory. Neural computation , 9(8): 1735-1780, 1997.                                                                                                                                        |
| [79] | Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster- gcn: An efficient algorithm for training deep and large graph convolutional networks. CoRR , abs/1905.07953, 2019. URL http://arxiv.org/abs/1905.07953 .      |
| [80] | Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor K. Prasanna. Graphsaint: Graph sampling based inductive learning method. CoRR , abs/1907.04931, 2019. URL http://arxiv.org/abs/1907.04931 .                             |
| [81] | Jie Chen, Tengfei Ma, and Cao Xiao. Fastgcn: Fast learning with graph convolutional networks via importance sampling. CoRR , abs/1801.10247, 2018. URL http://arxiv.org/abs/1801. 10247 .                                                            |
| [82] | 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/1911.07323, 2019. URL http://arxiv.org/abs/1911.07323 .          |
| [83] | Chuxiong Sun, Hongming Gu, and Jie Hu. Scalable and adaptive graph neural networks with self-label-enhanced training, 2021.                                                                                                                          |
| [84] | Renjie Liao, Zhizhen Zhao, Raquel Urtasun, and Richard S. Zemel. Lanczosnet: Multi- scale deep graph convolutional networks. ArXiv , abs/1901.01484, 2019. URL https://api. semanticscholar.org/CorpusID:57573752 .                                  |
| [85] | Vijay Lingam, Chanakya Ekbote, Manan Sharma, Rahul Ragesh, Arun Iyer, and Sundararajan Sellamanickam. A piece-wise polynomial filtering approach for graph neural networks, 2021.                                                                    |
| [86] | 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. URL https://arxiv.org/abs/2106.05234 .            |
| [87] | Deyu Bo, Chuan Shi, Lele Wang, and Renjie Liao. Specformer: Spectral graph neural networks meet transformers, 2023.                                                                                                                                  |

Disclosures. YWhas limited financial interests in Flagship Pioneering, Inc. and its subsidiaries.

Funding. YWacknowledges support from the Schmidt Science Fellowship, in partnership with the Rhodes Trust, and the Simons Center for Computational Physical Chemistry at New York University.

## A Experimental details

Code availability. All architectures, as well as scripts to execute the experiment, are distributed open-source under MIT license at https://anonymous.4open.science/r/rum-834D/ . Core dependencies of our package include PyTorch [62] and Deep Graph Library [36].

Hyperparameters. All models are optimized using Adam [73] optimizer and SiLU [74] activation functions. 4 random walk samples are drawn everywhere unless specified. Other hyperparameterslearning rate ( 10 -5 ∼ 10 -2 ), hidden dimension ( 32 ∼ 64 ), L2 regularization strength ( 10 -8 ∼ 10 -2 ), walk length ( 3 ∼ 16 ), temperature for L consistency ( 0 ∼ 1 ), coefficient for L consistency ( 0 ∼ 1 ), coefficient for L self , and dropout probability-are tuned using the Ray platform [75] with the default Ax [76] search algorithm with 1000 trails or 24 hours tuning budget on a 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 ( L consistency ) used in Feng et al. [63] for classifications, we further regularize the model by using the RNNs in ϕ x to predict the semantic representation of the next node on the walk given ω u and jointly maximize this likelihood:

$$\hat { \omega } _ { x _ { i + 1 } } = g ( \{ \omega _ { x _ { 1 } }, \omega _ { x _ { 2 } }, \dots, \omega _ { x _ { i } } \}, \omega _ { u } | \theta ) ; & & ( 1 3 ) \\ \mathcal { L } _ { \text{self} } ( \theta ) = - \log P ( \hat { \omega } _ { x _ { i + 1 } } | \theta ), & & ( 1 4 )$$

where g ( ·| θ ) is modeled as the sequence output of the RNN ϕ x in Equation 5. The total loss is modeled as a combination of:

$$\mathcal { L } ( \theta ) = - \log P ( y | \mathcal { G }, \mathbf X, \theta ) + \mathcal { L } _ { \text{seif} } + \mathcal { L } _ { \text{consistency} }$$

## B.2 RUMattenuates over-squashing

Similarly, we can show that if the composing neural networks defy the vanishing gradient problem (w.r.t. the input) [77], the sensitivity analysis in Equation 3 [15] has a lower bound for RUM.

Lemma 7 (RUM attenuates over-squashing) . If ϕ , f x have lower-bounded derivatives, the inter-node Jacobian for nodes u, v separated by a shortest path of length l , RUM with walk length l also has a lower bound:

$$| \frac { \partial \mathbf X _ { v } ^ { ( l ) } } { \partial \mathbf X _ { u } ^ { ( 0 ) } } | \geq | \nabla \phi _ { x } | | \nabla f | ( \hat { A } ^ { l } ) _ { u v },$$

where ˆ A ij = A / ij ∑ j A ij is the degree-normalized adjacency matrix.

Like the upper bound in Equation 3, this lower bound is also controlled by the power of the (normalzied) adjacency matrix, albeit the absence of self-loop will result in a slightly looser bottleneck.

The term ( ˆ ) A l uv 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 can never be alleviated, since there are always roughly 1 / A ( ˆ l +1 ) uv (assuming uniform node degree) structurally equivalent nodes. Nevertheless, 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 in the layer choices of ϕ x -a GRU [16] unit. Its success, just like that of long shortterm memory (LSTM) [78], can be attributed to the near-linear functional form of the long-range gradient. The term |∇ ϕ x | is controlled by a sequence of sigmoidal update gates, which can be optimized to approach 1 (fully open). If we ignore the gradient contribution of X 0 u to these gates, the non-linear activation function has only been applied exactly once on X 0 u ; therefore, the gradient | ∂ X ( +1) l v /∂ X (0) u | is neither rapidly vanishing nor exploding.

Table 6: Ablation study. Cora [45] test set accuracy ↑ with in the architecture deleted.

| ω u = 0        | ω x = 0        | L self = 0     | L consistency = 0   |
|----------------|----------------|----------------|---------------------|
| 82 . 2 ± 1 . 0 | 35 . 0 ± 1 . 0 | 78 . 4 ± 0 . 1 | 80 . 3 ± 1 . 1      |

## 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 is usually lost in the convolution. Since, on this binary tree, the receptive field grows exponentially, Alon and Yahav [14] 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 2 32 D for single-precision floating point ( float32 ). This corresponds to the structural ˆ A l term in Equation 3 and Equation 16. Evidently, when D = 32 , as is the adopted experimental setting in Figure 5, this limit is 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 to tree depth or problem radius r = 5 , and a relatively moderate decrease afterward. Note that when the problem radius exceeds r = 7 , RUM's performance is not significantly different from the convolutional counterparts.

## B.4 Scalaing to large graphs (Q6).

In Appendix Table 8, we apply RUM on an ultra-large graph OGB-PRODUCTS , that cannot fit easily on a single GPU, and compare RUM with architectures specifically designed for large graphs [39].

## B.5 Ablation study (Q7).

In Table 6, we conduct a brief ablation study where we delete, one by one, the components introduced in § 3. ω u = 0 and ω x = 0 refer to the deletion of the topological and semantic representations of walks, respectively. Neglecting topological information results in a moderate decrease in performance, whereas neglecting semantic representation is more detrimental. The ω u = 0 also resembles Jin et al. [17] albeit with different walk-wise aggregation. This offers a qualitative comparison between our work and Jin et al. [17] as no source code was released for this package so no rigorous comparison was possible. We also see that the regularization methods are helpful to 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

```
\frac { \text{qorm} \, \i \text{ anonymous experiment} } { \text{ Input: } } \, w = ( v _ { 0 }, v _ { 1 }, \dots, v _ { l } ) \\ \, C \leftarrow 0 ; \Omega \leftarrow \text{ Dict({})} \\ \, \text{ for } v _ { i } \, \text{ in } w \, \text{ do} \\ \, \text{ if } v _ { i } \, \text{ in } \Omega \colon u _ { i } \leftarrow \Omega [ v _ { i } ] ; \text{ Else } \Omega [ v _ { i } ] \leftarrow C ; C \leftarrow C + 1 \\ \, \text{ end for} \\ \, \text{ Return: } } \, \omega _ { u } = ( u _ { i } ) = ( u _ { 0 }, u _ { 1 }, \dots, u _ { l } )
```

```
+ 1
```

̸

̸

̸

Remark 8 (Inequality in distribution) . For two nodes v , v 1 2 with distribution of random walks terminating at v , v 1 2 not equal in distribution p ω ( u ( w 1 )) = p ω ( u ( w 2 )) or p ω ( x ( w 1 )) = p ω ( x ( w 2 )) , the node representations in Equation 6 are also different ψ v ( 1 ) = ψ v ( 2 ) .

̸

̸

One way to construct h function in Equation 5 is to have h w ( ) positive only where p ω ( u ( w 1 )) &gt; p ω ( u ( w 2 )) ; the same thing can be argued for ω x . In other words, one only needs to prove two walks terminating at two nodes p ω ( u ( w 1 )) = p ω ( u ( w 2 )) or p ω ( x ( w 1 )) = p ω ( x ( w 2 )) are not equal in distribution to verify that RUM can distinguish two nodes. Conversely, we can also show that p ω ( u ( w 1 )) = p ω ( u ( w 2 )) implies that v , v 1 2 are isomorphic without labels- we refer the readers to the Theorem 1 in Micali and Zhu [37] for a discussion on reconstructing unlabelled graphs using anonymous experiments.

|               | Complexity   | CSL accuracy    |
|---------------|--------------|-----------------|
| GCN [1]       | O ( N )      | 10 . 0 ± 0 . 0  |
| GAT [6]       | O ( N )      | 10 . 0 ± 0 . 0  |
| GIN [2]       | O ( N )      | 10 . 0 ± 0 . 0  |
| GraphSAGE [4] | O ( N )      | 10 . 0 ± 0 . 0  |
| 3WLGNN [60]   | O ( N 2 )    | 95 . 7 ± 14 . 8 |
| RUM           | O ( N )      | 93 . 2 ± 0 . 8  |

Table 7: Graph classification accuracy ↑ on CSL [58] synthetic dataset for graph isomorphism test.

Table 8: Node classification accuracy and efficiency on OGB-PRODUCTS [53]

|                 | Accuracy         |   Memory (MB) |   Throughput(iter/s) |
|-----------------|------------------|---------------|----------------------|
| GraphSAGE [4]   | 80 . 61 ± 0 . 16 |        415.94 |                37.69 |
| ClusterGCN [79] | 78 . 62 ± 0 . 61 |         10.62 |               156.01 |
| GraphSAINT [80] | 75 . 36 ± 0 . 34 |         10.95 |               143.51 |
| FastGCN [81]    | 73 . 46 ± 0 . 20 |         11.54 |                93.05 |
| LADIES [82]     | 73 . 51 ± 0 . 56 |         20.33 |                93.47 |
| SGC [7]         | 67 . 48 ± 0 . 11 |          0.01 |               267.31 |
| SIGN [ ? ]      | 76 . 85 ± 0 . 56 |         16.21 |               208.52 |
| SAGN [83]       | 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 |

Table 9: Node classification test accuracy ↑ and standard deviation with 60:20:20 random split.

|                 | # params               | Cora             | Photo            |
|-----------------|------------------------|------------------|------------------|
| GCN [1]         | 48K                    | 87 . 14 ± 1 . 01 | 88 . 26 ± 0 . 83 |
| GAT [6]         | 49K                    | 88 . 03 ± 0 . 79 | 90 . 04 ± 0 . 68 |
| GCNII [35]      | 49K                    | 88 . 46 ± 0 . 82 | 89 . 94 ± 0 . 31 |
| RAW-GNN         |                        | 87 . 85 ± 1 . 52 |                  |
| LanczosNet [84] | 50K                    | 87 . 77 ± 1 . 45 | 93 . 21 ± 0 . 85 |
| GPR-GNN [29]    | 48K                    | 88 . 57 ± 0 . 69 | 93 . 85 ± 0 . 28 |
| PP-GNN [85]     |                        | 89 . 52 ± 0 . 85 | 92 . 89 ± 0 . 37 |
| Transformer     | 37K                    | 71 . 83 ± 1 . 68 | 90 . 05 ± 1 . 50 |
| Graphomer [86]  | 139K                   | 67 . 71 ± 0 . 78 | 95 . 20 ± 4 . 12 |
| Specformer [87] | 32K                    | 88 . 57 ± 1 . 01 | 95 . 48 ± 0 . 32 |
| RUM             | 23K +20K initial proj. | 89 . 01 ± 1 . 40 | 95 . 35 ± 0 . 26 |

## D Missing mathematical arguments.

## D.1 Examples of Theorem 4

Example 8.1 (Cycle detection.) . A k -cycle C k is a subgraph of G consisting of k nodes, each with degree two. The existence of k -cycle can be determined by:

̸

✶ ( C k ⊆ G ) = ✶ [ P ω ( x j +1 = ω x 0 , ω x i = ω x j , ∀ i &lt; j ) &gt; 0] (17) Example 8.2 (Diameter.) . The diameter, δ G of graph G which equals the length of the longest shortes path in G , can be expressed as

̸

$$\delta _ { \mathcal { G } } = \underset { l = | \omega _ { x } |, \omega _ { x _ { i } } \neq \omega _ { x _ { j } }, \forall i \neq j } { \argmax } | \omega _ { x } | & & ( 1 8 )$$

## D.2 Proof of Theorem 4

Proof. First, we enumerate all possible unlabelled graphs with three nodes satisfying Assumption 3one with two edges, one with three edges. (Note that there is only one non-isomorphic graph with

two nodes.) Now we consider random walks of length l = 3 , where

$$P ( \omega _ { u _ { 3 } } = \omega _ { u _ { 0 } } ) > 0$$

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 2 edges and 3 nodes simply by verifying that

̸

$$P ( \omega _ { u _ { 1 } } \neq \omega _ { u _ { 3 } } ) > 0$$

only stands when v 2 is the 2-degree node.

Moving on to the labeled 3-node graph case, we 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, ω x 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 A and C labels locally, structurally isomorphic),

$$P ( B | \omega _ { x } ( w _ { t } ) ) = \begin{cases} 1, t = 2 n, n \in \mathbb { N }, & ( 2 1 ) \\ 0, t = 2 n + 1, n \in \mathbb { N } & ( 2 1 ) \end{cases}$$

$$P ( A | \omega _ { x } ( w _ { t } ) ) = P ( C | \omega _ { x } ( w _ { t } ) ) = \begin{cases} 0, t = 2 n, n \in \mathbb { N }, \\ 1 / 2, t = 2 n + 1, n \in \mathbb { N } \end{cases}$$

If graphs have the same ω x , 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 N nodes, they also stand for graphs of N +1 nodes, the Reconstruction Conjecture [42]

Suppose we have two non-isomorphic graphs with N + 1 nodes G 1 and G 2 with the same RUM embedding Ψ = Ψ 1 2 . We enumerate all N +1 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 v (ruling out the trivial case where the label or connectivity of v is different for these two graphs), and two remaining subgraphs G \ v 1 , G \ v 2 ; since ϕ , ϕ x u , f are injective, Ψ = Ψ 1 2 implies ω , ω u x are equal in distribution for G 1 , G 2 . As such, the walk distribution

̸

$$P ( \omega _ { x } ( w ), \omega _ { u } ( w ) | w _ { 0 } = v, w _ { i } \neq v, i > 0 )$$

̸

$$= P ( \omega _ { x } ( w _ { 0 } ), \omega _ { u } ( w _ { 0 } ) | w _ { 0 } = v ) P ( \omega _ { x } ( w _ { 1 \dots } ), \omega _ { u } ( w _ { 1 \dots } ) | \omega _ { x } ( w _ { 1 \dots } ), \omega _ { u } ( w _ { 1 \dots } ), w _ { i } \neq v, i > 0 ) \ \ ( 2 4 )$$

are also equal in distribution for G 1 , G 2 .

If there is a link between v and the nodes in G 1 , G 2 , we assign a new label to contain both the old label and the connection. As such, if the second term is not equal in distribution for G 1 , G 2 , we would have

̸

$$\Psi ( \mathcal { G } _ { 1 } ^ { \vee v } ) & \neq \Psi \mathcal { G } _ { 2 } ^ { \vee v } ),$$

which is in conflict with the assumption that Theorem 4 stands for graphs with N nodes.

## D.3 Proof of Lemma 6

Proof. By the definition of Dirichlet energy (Equation 2) and non-contractive mappings (Definition 5),

$$\mathcal { E } ( \psi ( \mathbf X ) ) = \frac { 1 } { N } \sum _ { u, v \in \mathcal { E } _ { \mathcal { G } } } | | \psi ( \omega _ { x } ( \mathbf X _ { u } ) ) - \psi ( \omega _ { x } ( \mathbf X _ { v } ) ) | | ^ { 2 }$$

$$= \frac { 1 } { N } \sum _ { u, v \in \mathcal { E } _ { \phi } } ^ { \cdot } \| f ( \phi _ { x } ( \omega _ { x } ( \mathbf X _ { u } ) ) ) - f ( \phi _ { x } ( \omega _ { x } ( \mathbf X _ { v } ) ) ) \| ^ { 2 }$$

$$\geq \frac { 1 } { N } \sum _ { u, v \in \mathcal { E } _ { \phi } } ^ { \mu } \| \phi _ { x } ( \omega _ { x } ( \mathbf X _ { u } ) ) - \phi _ { x } ( \omega _ { x } ( \mathbf X _ { v } ) ) \| ^ { 2 }$$

$$= \frac { 1 } { N } \sum _ { u, v \in \mathcal { E } _ { \mathcal { G } } } & \| \phi _ { x } ( \sum _ { \{ w \}, | w | = l, w _ { l } = u } p ( w ) \mathbf X _ { u }, u \in w ) - \phi _ { x } ( \sum _ { \{ w \}, | w | = l, w _ { l } = v } p ( w ) \mathbf X _ { v }, v \in w ) \| ^ { 2 } \\ & \quad \Phi \quad.$$

$$& \geq \frac { 1 } { N } \sum _ { u, v \in \mathcal { E } _ { \mathcal { G } } } \| ( \sum _ { \{ w \}, | w | = l, w _ { l } = u } p ( w ) \mathbf X _ { u }, u \in w ) - ( \sum _ { \{ w \}, | w | = l, w _ { l } = v } p ( w ) \mathbf X _ { v }, v \in w ) \| ^ { 2 } \\ & \quad \dots$$

$$\geq \mathcal { E } ( \mathbf x )$$

The last inequality is due to the fact that ϕ x is non-contractive w.r.t. all, and therefore, the last element of the sequence, which are always X u and X v .
Yuanqing Wang Kyunghyun Cho
Non-convolutional Graph Neural Networks
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.