Non-convolutional graph neural networks.

Authors: yuanqing  wang
kyunghyun  cho
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-08 16:46:30

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.

Main paper: 
 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 = 1[(v i , v 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:EQUATIONHere, Â 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 ( Â) 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 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.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,EQUATIONwill decrease exponentially as the number of message-passing steps l increases [12, 13] , E(X (l) ) ≤ C 1 exp(-C 2 l) 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 receptive 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:EQUATIONwhere ϕ 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 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 ).Graph transformers [26, 27] -neural models that perform attention among all pairs of nodes and encode graph structure via positional encoding-are well-known solutions that are not locally convolutional. Their inductive biases determine that over-smoothing and over-squashing among local neighborhoods are, like RUM, also not prominent.Because of its all-to-all nature, the runtime complexity of graph transformers, just like that of almost all transformers, contains a quadratic term, w.r.t. the size of the system (number of nodes, edges, or subgraphs). This makes it prohibitively expensive and memory intensive on large social graphs (such as that used in Table 8 with millions of nodes). On smaller social graphs, we show in Tables 9, 4 that graph transformers are experimentally outperformed by RUM.State-of-the-art methods to alleviate oversmoothing. Stochastic regularization. DropEdge ([28], 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. [29, 30] and GPR-GNN ( [31] , Appendix Table 9 ) rewire the graph using personalized page rank algorithm [32] and generalized page rank on graphs, respectively. Similar to JKNet [33] , they mitigate over-smoothing by allowing direct message passing between faraway nodes. Constant-energy methods. Zhao and Akoglu [34] , Rusch et al. [35] constrain the pair-wise distance or Dirichlet energy among graphs to be constant. Nevertheless, the non-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 [36] can naturally be added to the GNN architecture, such as GCNII ( [37] , 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 0 , v 1 , . . .) with landing probability:EQUATIONwhere 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 [38] (see Appendix § A). Moreover, the walk considered here is not necessarily a path, as repeated traversal of the same node v i = v j , i ̸ = 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 [39] , ω 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 parallelized2 : (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 ):EQUATIONwhere ϕ x : R l×D → R Dx maps the sequence of semantic embeddings generated by a l-step walk to a fixed D x -dimensional latent space, ϕ u : R l → R Du maps the indicies sequence to another latent space D u , and f : R Dx ⊕ R Du → 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:EQUATIONwhich 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:EQUATIONThe node representation can be summedEQUATIONto 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 [40] , RNNs not only have linear complexity (see detailed discussions below) w.r.t. the sequence length but also naturally encodes the inductive bias that nodes closer 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. 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.Mini-batches. RUM is naturally compatible with mini-batching. For convolutional GNNs, large graphs that do not fit into the GPU memory have traditionally been a challenge, as all neighbors are required to be present and boundary conditions are hard to define [41] . RUM, on the other hand, can be inherently applied on subsets of nodes of a large graph without any alteration in the algorithm-the random walks can be generated on a per-node basis, and the FOR loop in Algorithm C can be executed sequentially, in parallel, 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 haveEQUATIONwhich 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 RUM is 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 [42] and RNNs [43] . Note that RUM can be easily extended to weighted graphs by sampling a biased random walk with edge weights w ij and keeping rest of the algorithm the same:P (v j |(v 0 , ..., v i-1 )) ∝ I[(v i , v j ) ∈ E G ] * w ij /D(v i ).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 [39] 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 (RUM can distinguish non-isomorphic graphs). Up to the Reconstruction Conjecture [44] , 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. EQUATIONThus, 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. 
rum alleviates 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] .EQUATION)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 [48, 49] , 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 6does not change this to arrive at:Lemma 6 (RUM alleviates over-smoothing.). If ϕ x , f are non-contractive w.r.t. all elements in the sequence, the expected Dirichlet energy of the corresponding RUM node representation in Equation 6is greater than its initial valueEQUATIONThis 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(l+1) v /∂X (0)u | decays slower as the distance between u, v grows vis-à-vis the convolutional counterparts. Briefly, although RUM does not address the information bottleneck with exponentially growing receptive field (the 1/( Âl+1 ) uv term in Equation 16), it nevertheless can have a non-vanishing (nor exploding) gradient from the aggregation function (|∇ϕ x |). 
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 [47] , as well as the coauthor [50] and co-purchase [51] datasets common in social modeling. Additionally, we hypothesize that RUM, without the smoothing operator, will perform competitively on heterophilic datasets [52] -we test this hypothesis. For graph classification, we benchmark on the popular TU dataset [53] . We also test the graph regression performance on molecular datasets in MoleculeNet [54] and Open Graph Benchmark [55] . In sum, RUM almost always outperforms, is within the standard deviation of, the state-of-the-art architectures, as shown in Tables 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 [51] 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 [56] and MoleculeNet [54] . 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.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 [60, 61] . Containing 4-regular graph with edges connected to form a cycle and containing skip-links between nodes, this dataset is artificially synthesized in Murphy et al. [60] to create an especially challenging task for GNNs. As shown in Appendix Table 7 , all convolutional GNNs fail to perform better than a constant baseline (there are 10 classes uniformly distributed). 3WLGNN [62] , a higherorder GNN of at least O(2) complexity that operates on explicitly enumerated triplets of graphs, can distinguish these highly similar 4 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 [47] citation graph and vary the walk lengths and number of samples from 1 to 9, where the performance of RUM improves as more samples are taken and longer walks are employed, though more than 4 samples and walks longer than L > 4 yield qualitatively satisfactory results; this empirical finding has guided our hyperparameter design.In Figure 2 , 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 [37, 28, 63] , 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.Texas Wisc. Cornell GCN [1] 55 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] 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 [38] sparse implementation whereas RUM is implemented naïvely in PyTorch [64] , 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. [65] and attack by randomly adding fake edges to the Cora [47] 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 [65] , with the performance only decreased less than 10% with 10% fake edges added.Scaling to huge graphs (Q6) and Ablation study (Q7) are deferred to Appendix § B.5. 
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.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: The experimental details are described in Appendix § A.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes]Justification: All error bars of real-world benchmarks are included in the results.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).• The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. Justification: The Code of Ethics have been closely followed in every step of this research project.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] Justification: See the Social Impact paragraph in § 6.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: The paper poses no such risks. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [Yes] Justification: All datasets used in this work is open-source and has been properly cited. Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. 
 
 Appendix: Very dense graphs. As evidenced by the underwhelming performance of the Computer [51] 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 [66] ). We plan to characterize the effect of excluding these walks. Biased walk. Here, we have only considered unbiased random walk, whereas biased random walk might display more intriguing properties as they tend to explore faraway neighborhoods more effectively [17] . Directed graphs. Since we have only developed RUM for undirected graph (random walk up to a random length is not guaranteed to exist for directed graphs), we would have to symmetrize the graph to perform on directed graphs (such as the heterophilic datasets [52] ); this create additional information loss and complexity.Future directions. Theoretical. We plan to expand our theoretical framework to account for the change in layer width and depth to derive analytical estimates for realizing key graph properties. Applications. Random walks 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 [67, 68, 69, 70, 71] and furthermore on the equivariant modeling of n-body physical systems [72] .Impact statement. We here present a powerful, robust, and efficient learning algorithm on graphs. Used appropriately, this algorithm might advance the modeling of social [73] and physical [74] systems, which can oftentimes modeled as graphs. As with all graph machine learning methods, negative implications may be possible if used in the design of explosives, toxins, chemical weapons, and overly addictive recreational narcotics.ω 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 Table 6 : Ablation study. Cora [47] test set accuracy ↑ with in the architecture deleted.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 32D for single-precision floating point (float32). This corresponds to the structural Â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.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 [41] .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.Input:w = (v 0 , v 1 , . . . , v l ) C ← 0; Ω ← Dict({}) for v i in w do If v i in Ω: u i ← Ω[v i ]; Else Ω[v i ] ← C; C ← C + 1 end for Return: ω u = (u i ) = (u 0 , u 1 , . . . , u l )Remark 8 (Inequality in distribution). For two nodes v 1 , v 2 with distribution of random walks terminating at v 1 , v 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 )) > 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 1 , v 2 are isomorphic without labels-we refer the readers to the Theorem 1 in Micali and Zhu [39] for a discussion on reconstructing unlabelled graphs using anonymous experiments.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 [62] O(N EQUATIONExample 8.2 (Diameter.). The diameter, δ G of graph G which equals the length of the longest shortes path in G, can be expressed asEQUATIOND.2 Proof of Theorem 4Proof. 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 withProof. By the definition of Dirichlet energy (Equation 2) and non-contractive mappings (Definition 5),EQUATIONEQUATIONEQUATIONThe 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 .Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes] Justification:The code is open source at https://anonymous.4open.science/r/ rum-834D. All data is from public benchmark datasets, as discussed in § 5. Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.Code at: https://github.com/yuanqing-wang/rum/tree/mainNote 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. 


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

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

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

Reviews: review: paper_summary: paper_summary: The authors of the paper proposed a non-convolution based approach to solve graph learning tasks using random walks and recurrent neural networks (RNNs), namely a random walk neural network with unifying memory (RUM). Random walks, together with the “anonymous experiment” function, allow to extract topological and semantic information from the graph, while an RNN and a feed-forward neural network take care of “unifying” the features collected from the walks. Research questions on the ability of the model to be more expressive than classical GNNs and to reduce oversmoothing and oversquashing have been answered positively both theoretically and experimentally. The experimental section, along with the appendix section, presents several experiments, ablation studies, training details, and theorem proofs. The code is available.
strength_weakness: strength_weakness: Weakness: The paper lacks a discussion on the proposed method and Graph Transformer architectures. Although they are present in the experimental comparisons on the node classification task in Table 9, Graph Transformer is actually a well-known solution that does not rely on convolutions and can mitigate the over-squashing and oversmoothing problems [1,2]; the discussion should also considering the different computational costs of the two approaches.

Ref.
[1] "Attending to Graph Transformers", Luis Müller and Mikhail Galkin and Christopher Morris and Ladislav Rampášek, 2024, https://arxiv.org/abs/2302.04181
[2] "Do Transformers Really Perform Bad for Graph Representation?", Chengxuan Ying et. al., 2021, https://arxiv.org/abs/2106.05234
questions: questions: 1) At Table.5, showing Graph Regression comparisons on ESOL, FreeSolv and Lipophilicity datasets, it seems to me that for the MoleculeNet [1] benchmark you used the results presented in their papers about the XGBoost model (best performing among 
conventional methods) with (0.99, 1.74, 0.799) RMSE scores, respectively to the three datasets, instead using them from the best performing graph-based methods which are (0.58,1.15) for ESOL and FreeSolv datasets by using the MPNN model and 0.655 for Lipophilicity dataset by using GC model, which are the best models in these datasets. This is in contrast on what you said in the caption of Table. 5, since those presented are not the best results and models of [1].

Ref.
[1] "MoleculeNet: a benchmark for molecular machine learning", Wu, Zhenqin and et. al., "Chem. Sci.",2018, doi:10.1039/C7SC02664A, url:http://dx.doi.org/10.1039/C7SC02664A
limitations: limitations: The authors have adequately discussed the potential negative societal impact and the current limitations of their work.
paper_summary: paper_summary: The paper introduced a new graph neural network that is not based on convolution but on the random walk. Based on the results of the extensive experiment, the proposed architecture is effective for heterophilic graphs and long-range graphs.
strength_weakness: strength_weakness: Currently, the proposed architecture only works on unweighted and undirected graphs.
questions: questions: Can the proposed method work well on directed and weighted graphs?
limitations: limitations: N/A
paper_summary: paper_summary: The paper introduces Random Walk with Unifying Memory (RUM), a non-convolutional graph neural network (GNN) that addresses limitations like limited expressiveness, over-smoothing, and over-squashing typically associated with convolution-based GNNs. RUM leverages random walks and recurrent neural networks (RNNs) to merge topological and semantic graph features, theoretically showing and experimentally verifying its enhanced expressiveness over traditional methods like the Weisfeiler-Lehman (WL) isomorphism test. It demonstrates competitive performance on node- and graph-level tasks while offering advantages in efficiency and scalability.
strength_weakness: strength_weakness: The paper lacks detailed exploration on how varying random walk lengths impact RUM's performance across diverse tasks and whether optimal lengths are identified for different types of graphs or datasets. Additionally, while the paper highlights RUM's superiority over expressive GNNs in specific scenarios, it overlooks potential limitations when compared to these models, such as not thoroughly investigating upper bounds on the WL test, which could gauge RUM's discriminative power against more expressive GNNs.
questions: questions: 1. Can you elaborate on how the choice of random walk length $𝑙$ impacts the performance of RUM across different tasks? Are there optimal lengths identified for specific types of graphs or datasets?

2. In practical applications, how does RUM handle graph datasets with varying degrees of sparsity? Are there specific strategies employed to ensure robust performance across different graph structures?

3. While the paper demonstrates that RUM outperforms expressive GNNs in certain scenarios, it lacks exploration of scenarios where RUM might face challenges or limitations compared to expressive GNNs. For instance, it does not thoroughly investigate potential upper bounds on the WL test, which is a standard measure of graph isomorphism and could provide insights into the discriminative power of RUM compared to more expressive GNNs.
limitations: limitations: Yes, The authors have addressed several limitations in the Limitations section.
paper_summary: paper_summary: This paper proposes a random walk-based graph neural network, where an RNN is used to combine the topological and semantic graph features along the walks. The proposed RUM model is free of convolution operators and does not suffer from the limited expressiveness, over-smoothing, and over-squashing, which are commonly faced issues in convolution-based GNNs.
strength_weakness: strength_weakness: Empirically, the gains with RUM are marginal and in some cases, RUM is worse than the baselines.

The organization and the presentation of the paper can be further improved.
1. There are too many hyper-references. Most of the hyper-references in Section 1 and Section 2 are unnecessary, especially when reading the paper for the first time.
2. There are too many supplementary demonstrations (...) Some additional information could be helpful, but too many will hinder the reading. It would be better to reorganize the sentences to make the presentation smoother.
3. There are some grammar mistakes, like in line 244. Proofreading is needed.
questions: questions: 1. In Lemma 6, the author shows that RUM increases Dirichlet energy. Why would this be helpful intuitively? As for homophily graphs, GNNs should decrease the Dirichlet energy. This phenomenon is also analyzed in [1,2]. It seems RUM is not just alleviating over-smoothing, but is anti-smoothing.
2. In line 243, the author claims that RUM almost always outperforms SOTA architectures, this is not true according to the results.

[1] Interpreting and unifying graph neural networks with an optimization framework

[2] A Unified View on Graph Neural Networks as Graph Signal Denoising
limitations: limitations: The authors adequately discussed the limitations.

Comments: title: Thank you!
Conceptual and experimental comparison with graph transformers
Thank you!
Satisfied with the answers
Correction: to remove the length condition in the new Corollary 4.1
Correction: to remove the length condition in the new Corollary 4.1
Thank you!
Thank you!
Official Comment by Reviewer jBUd
Please let us know if we have addressed your concerns
Comparison with graph transformers
Directed and weighted graphs
Clarification on the over-smoothing behavior
Clarification on the concept of "upper bounds of the WL test"
comment: Thank you, Reviewer `P1Jd` for your comment and for raising the score!
Thank you authors.  I don't have any concerns.  Based on your response and modification, I've increased the score.
Dear Reviewer `P1Jd`, 

As the discussion period is drawing to a close, we just wanted to bring your attention to the new conceptual and experimental comparison with graph transformers.

Since this was the main part of the **weaknesses** section in your review, we would be grateful to know whether this concern has been addressed and if you would consider raising the score. If your concerns have not been addressed, please let us know and we will strive to provide more analysis, experiments, and discussion to provide more clarification! 

Thanks again for your valuable input!
Thanks again, Reviewer `xhjS`!

Please let us know if you have any further questions, or if you think of more ways to characterize the WL upper bound.
Thank you for your update and for revisiting Corollary 4.1. I appreciate the authors' detailed response. I am satisfied with the answers and will maintain my original score.
Thanks authors for the response. I don't have other concerns, so I keep my score.
After careful checking, we find that the condition of walk length $k$ has to be removed in the new Corollary 4.1 reworked during the rebuttal. (See this [post](https://openreview.net/forum?id=JDAQwysFOc&noteId=GFBlZllWUU))

We would be grateful if you could cast more light on the concept of "upper bounds of the WL test" and whether a comparison with the $k$-WL test would be sufficient.
After careful checking, we find that the condition of walk length $k$ has to be removed in the new Corollary 4.1 reworked during the rebuttal:

**Corollary 4.1** (RUM is more expressive than k-WL-test.) Up to the Reconstruction Conjecture, two graphs with $G_1 , G_2$ labeled as non-isomorphic by the $k$-dimensional Weisfeiler-Lehman ($k$-WL) isomorphism test, is the necessary, but not sufficient condition that RUM can distinguish them.
Thank you, Reviewer `jBUd`, for your comment and for raising the score.

Please don't hesitate to let us know if you have any further questions!
Thank you, Area Chair `bArP`, for inviting all reviewers to discuss the remaining concerns!
Thank you for the detailed responses. Your clarifications relieve most of my concerns. I have increased the score.
As the authors suggest (and due to the size of the rebuttal), I invite all reviewers to share their main concerns before the rebuttal deadline, to have sufficient time for discussion. I'd be especially interested in feedback from reviewer `jBUd`, who gave the most negative review as of now.

Thanks, the AC
Dear Reviewers and Area Chairs,

Please let us know if the rebuttal we provided has addressed your concerns. If you have more pending questions, we would be more than happy to carry out more analysis and experiments in the discussion period to address them!

Thank you again for your valuable suggestions!
Dear Reviewer `P1Jd`,

We have included extensive conceptual discussion and additional experiments to incorporate your suggestion of comparing with graph transformer models. Please let us know if you have further questions, we will make sure to address them in the discussion period!
Dear Reviewer `wXB7`, 

We believe that our rebuttal has sufficiently addressed your concern around the limitations when it comes to the weighted and directed graphs---both of which are possible with some slight modifications. Please let us know if you have any further questions!
Dear Reviewer `jBUd`,

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

Thank you!
Hi Reviewer `xhjS`, 

Thanks again for your feedback! We had a question on the meaning of "upper bounds of the WL test", does it mean the dimension of the $k$-WL test? If that's the case, in the rebuttal we had reworked our **Corollary 4.1** to incorporate a comparison with the $k$-WL test.

Please let us know if we have interpreted your comments correctly. We will provide more thorough comparison and discussion to further address your comments if that is not the case.

Thank you!