Sketch-Augmented Features Improve Learning Long-Range Dependencies in Graph Neural Networks
Authors: Ryien Hosseini
Filippo Simini
Venkatram Vishwanath
Rebecca Willett
Henry Hoffmann
Venue: NeurIPS 2025 poster ()
Keywords: graph neural networks
learning on graphs
random projection
Primary area: deep_learning
TL;DR: We enhance Graph Neural Networks by incorporating randomized global embeddings of node features alongside traditional local representations, which mitigates oversquashing, oversmoothing, and expressivity limitations.

Abstract: Graph Neural Networks learn on graph-structured data by iteratively aggregating local neighborhood information. While this local message passing paradigm imparts a powerful inductive bias and exploits graph sparsity, it also yields three key challenges: (i) oversquashing of long-range information, (ii) oversmoothing of node representations, and (iii) limited expressive power. In this work we inject randomized global embeddings of node features, which we term Sketched Random Features, into standard GNNs, enabling them to efficiently capture long-range dependencies. The embeddings are unique, distance-sensitive, and topology-agnostic---properties which we analytically and empirically show alleviate the aforementioned limitations when injected into GNNs. Experimental results on real-world graph learning tasks confirm that this strategy consistently improves performance over baseline GNNs, offering both a standalone solution and a complementary enhancement to existing techniques such as graph positional encodings.

Sketch-Augmented Features Improve Learning Long-Range Dependencies in Graph Neural Networks
Ryien Hosseini' Filippo Simini?, Venkatram Vishwanath',
Rebecca Willett Henry Hoffmann'
University of Chicago AAgonnne National Laboratory
3 NSF-Simons National Institute for Theory and Mathematics in Biology
fryien, willett, hankhof fmann] fmann)@uchi cauuhicago.... edu {fsimini, venkat]@anl. gov
Abstract
Graph Neural Networks learn graph- structurrud data by iteratively aggregating lo- cal neighborhood information. While this local message passing paradigm imparts powerful inductive bias and exploits graph sparsity, it also yields three key chal- lenges: (i) oversquashing of long-range information, (ii) oversmoothing of node representations, and (iii) limited expressive power. In this work we inject random- ized global embeddings of node features, which we term Sketched Random Features, into standard GNNs, enabling them to efficiently capture long-range dependencies. The embeddings are unique, distance-sensitive, and which we analytically and empirically show alleviate the aforementioned limita- tions when injected into GNNs. Experimental results on real-world graph learning tasks confirm that this strategy consistently improves performance over baseline GNNs, offering both standalone solution and a complementary enhancement to existing techniques such as graph positional encodings.
Introduction
Graph Neural Networks (GNNs) are a widely adopted approach for representation learning on graph- structured data. Standard GNN architectures employ a message-passing framework [26], wherein each node's 's features are iteratively propagated and aggregated along edges. Thus, GNNs leverage a strong eooology-induced bias: node features are iteratively refined by their neighbors, enabling local interactions shape final node or graph embeddings. Moreover, these localized computations naturally exploit graph sparsity, facilitating efficient training. Despite this success, three persistent challenges remain:
Signals from distant nodes are compressed into a fixed size vector when traversing multiple hops, hindering GNN's ability capture long-range interactions [2].
Oversquashing:
Oversmoothing: As network depth grows, node representations converge exponentially to nearly
identical values, eliminating meaningful distinctions [44, 56).
Limited Expressive Power: Standard GNNs have expressive power no greater than the 1- dimensional Weisfeiler-Lehman heuristic [67]. leading them to fail distinguishing many non- isomorphic graphs or structurally distinct subgraphs [68].
To address these limitations, two primary lines of research have emerged. The first adapts transformers [65] for graph-structured data, either by combining message passing with dense attention layers [59, 70, 38, 46] by replacing message passing altogether [39, 49]. This approach allows the model to attend to arbitrary node pairs regardless of geodesic distance, thus circumventing many limitations of pesssage-passing GNNs. However, these methods typically incur O(N2) memory and computation cost in the number of nodes N and rely on carefully designed node-level signals (called positional
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

or structural encodings) to inject graph structure back into the model [39]. These encodings can be challenging to design, and their theoretical properties remain only partially understood [63].
A second line of work augments traditional GNNs with encodings- inspired by transformers- to improve performance by enhancing expressiveness [53]. These include purely random node features that break symmetry and guarantee universal separation of non-isomorphic graphs [1. 62]. However, such unstructured noise can slow convergence or degrade learning in practice [7]. In contrast, structural encodings (e.g., spectral embeddings [23]) are topologically distance-sensitive but rely on deterministic, graph- graph-based based representations that are difficult make both unique and equivariant under node permutation. This is because, unlike Euclidean spaces, graphs lack a canonical coordinate system that defines cardinal direction, creating anbiguities that the GNN must handle. Notably, both these approaches primarily focus on informative node features typically present in real- graphs.
encodings, and do not consider
This observation motivates our approach: instead of ahandoning message passing or augmenting it solely with structural information, we propose leveraging node features themselves to address GNN limitations. To this end, we introduce Sketched Random Features (SRF), presented in Algorithm 1, simple yet powerful method for injecting global, feauuredistancc--sessiive signals into GNNs. SRF augments each node's features with sketches, or randomized low-dimensional projections, of all node features in kernel space, preserving feature similarity in expectation and breaking symmetry through randomization. This paper describes how sketched random features can augment feature representations in every layer of a message passing GNN to yield accurate predictions in a variety of settings. By the LiinsonnLindeestrauss. lemma [35, 8), such projections preserve important distance relationships in feature space even in significantly reduced dimensions. We leverage these properties to construct node-feature representations that we show overcome the challenges above.
Consider graph's node feature matrix X R where the i-th column of XT, x; R denotes
the features of node i, and a positive-definite similarity function (kernel) k IF x R + R defined between these features. Let & IR XF - N denote a mapping that embeds X into a random feature space via feature map (p-).
While any random kernel feature (xxx) E
RD (c.g., via random Fourier features [57])
Algorithm 1 Sketched Feature GNN
already provides an unbiased approximation of similarity between node features, i.e.,
1: Input 9 = (V, E) X
E[p((x,) ((x,)] = x,), we go fur- ther by applying a cross-node random projec- tion ((ke) E NxN_ Let E x (with (D < N) be the matrix of random kernel fea- tures, where the i-th row of t is (xx,). Mul- tiplying ((A) and & yields the kernel sketch 7 S(k) t, where the i-th column of ZT, denoted z,, is linear combination of all node features in the kernel space. Crucially, these sketched embeddings }z,} } still preserve kernel relationships in expectation, i.e. for any i,
2: 4 EXX)
3: Z S(k)
($)
4: Initialize: h x, for all
5: for layer = 0 to L 1 do
6: for each node 1 E V do
7:
h = [h 2.]
(((+1) = f h [6 :j j N())
8:
9: return (L)
E 2 2j| = xx),,x,).
Interestingly, this sketched random feature matrix provides properties that, when injected into GNNs, are surprisingly effective in mitigating the aforementioned limitations of message-passing graph neural networks. In particular, these sketches:
are unique yet distance-sensitive. Each sketch z, is unique, breaking symmetries, while pre- serving distances in the node-feature space with high probability (Propositions 3.2 and 3.4). This property confers universality (enabling GNNs to distinguish non-isomorphic graphs) and counters oversmoothing by preventing embeddings from converging.
contain sopology-agnosti cross-node information. Since each z; is formed by a linear combina- tion of all node embeddings in the random feature space, it injects global signal into the GNN (Proposition 3.3). This mitigates oversquashing by enabling immediate cross-node interactions, regardless of geodesic distance.
maintain equivariance in expectation. With suitable random projections, the cross-node sketch preserves pairwise feature relationships under node permutation (Proposition 3.5).

---

In this work, we demonstrate analytically (Section 3) and empirically (Section 4) that these sketched random features provide the necessary global, distance-sensitive signals to overcome fundamental limitations of geessage-passing GNNs while maintaining computational efficiency. Unlike traditional uses of sketching for dimensionality reduction, our method leverages sketching as a mechanism for mixing global feature information across nodes, enabling efficient propagation of non-local signals without altering the graph topology. Experiments on real-world graph learning tasks demonstrate that SRF-augmented models often outperform baseline GNNs, offering computationally efficient alternative to existing structural positional encodings. Moreover, by leveraging orthogonal information derived from node features rather than topology, our approach can be integrated with existing structural encoding methods to yield further performance improvements.
Background and Related Work
Preliminaries. We consider finite node-attributed graphs G = E, with [V|= edges, and node feature matrix E RNNF,, Each column of x X; E IRF, represents the features of node i. A message-passing GNN (MPGNN) [26] initializes each node representation with its features, i.e. for node i, hς X,, and iteratively updates each node's hidden representation h!?) as
= N nodes, [
h ((+1) f(n. (9) (h)2: .jE E E(()))
(1)
where (i) denotes the multiset of node i's neighhors and f()) encapsulates learnable transformations (e.g., linear layers, ML.s) and aggregation mechanisms (e.g., sum, mean, attention). After layers, each node's 's hidden state h can be used for node-level tasks pooled for graph-level tasks. Several popular MPGNN architectures [68, 40, 27, 66] can be considered special cases of this paradigm and differ only in specific choices of learnable functions and aggregations.
2.1 Known Limitations of GNNs
Despite the widespread adoption of MPGNNs, three fundamental limitations have attracted significant attention. We briefly describe each challenge below and provide more comprehensive discussion and review of prior mitigation approaches for the limitations in Appendix A.
Oversquashing. As shown in Equation 1, MPGNNs propagate information through local neigh- borhoods. Consequently, when two nodes i and have geodesic distance d any signal from node i requires at least d message-passing layers to reach node j. and vice versa. During this process, the number of nodes in the effective receptive field can grow exponentially with depth, whereas the hidden dimension h typically remains fixed. This mismatch leads to oversquashing [2], where long-range information is compressed and loses influence on downstream tasks.
Alon and Yahav [2] demonstrate oversquashing empirically with their Tree-eegghborsMatthh dataset, where root node must predict label based on leaf node signals traversing multiple tree levels. De- spite the label being trivial to determine from direct leaf access, compression across the exponentially growing receptive field (O(24) at depth T.) severely degrades performance tree depth increases.
Oversmoothing. A commonly observed phenomenon in MPGNNs is the convergence of node embeddings h to an indistinguishable constant vector as network depth grows [61, 44, 56, 12]. In practice, this leads to GNNs being deployed with substantially fewer layers than their counterparts in other domains (e.g., deep convolutional neural networks [37]), despite depth often being critical for strong performance [19]. This effect is frequently attributed to the smoothing effect of repeated message-passing steps, which iteratively mix each node's features with those of its neighbors [44]. Although moderate smoothing can aid learning, it frequently converges rapidly to a subspace of trivial signals [56, 12]. yielding nearly identical node representations and thus impeding metric performance. Following recent work [61, 12], we measure oversmoothing via a Dirichlet energy metric defined on
node embeddings (
[b(] (6) h 1 E NxF after E MPGNN layers (cf. Equation 1):
((H()) = 1
1 EEI
h 2
(2)
N
TEV JEN(()
A rapid decrease in (0)( grows indicates oversmoothing.
3

---

Limited Expressiveness. Ideally, GNNs should distinguish non nommisomip graphs, as this is pre- requisite for universal approximation of expressiveness is upper-bounded by the 1-dimensional Weisfeiler-LLehman (1-WL) heuristic [67], which measures graph structure through iterative neighborhood aggregation. This expressivity con- straint directly limits MPGNNs ability to distinguish many non-isomorphic graphs that have distinct structural properties but identical neighborhood aggregation patterns [68]. In response, koorder Weisfeiler-Lchman GNNs (k- WLGNNs) were introduced [52, 50J. They operate on k-tuples of nodes and match the expressive power of the generalized k-WL heuristic, but typically require O(N*) computation and memory. Although recent work has shown that this can be reduced in certain cases to ( and (NV)) [4], these methods remain expensive for many applications.
functions [53]. However, standard MPGNNs'
To address this limitation efficiently. recent work proposes positional or structural encodings that augment node features with additional signals. For instance, purely random node features [18] render GNNs universal [62, 1]. but often impair empirical performance [7]. Hence, recent efforts have shifted toward graph-derived features, seeking to make semantically meaningful encodings while retaining invariance to node permutations, Proposed approaches include spectral embeddings [23, 45, 48], subgraph-base -based representations [43, 9], and homomorphism counts [55, 34, 6]. However, designing an encoding that is simultaneously unique, distance-sensiffvy and equivariant is difficult as it is closely tied to the graph canonization problem boolem-known to be at least as hard as distinguishing graph isomorphism in general [5]. Recently, Pearl [36] proposes learning positional encodings with GNNs augmented with either standard basis vectors (B-Pcarl) or random features (R-Pearl). This leads to better asymptotic complexity but can be expensive for small and medium graphs in practice.
In the following subsection, we introduce kernel methods and random feature approximations that serve as the foundation for our approach to address these limitations.
2.2 Kernels, Random Kernel Features, and Sketching
Consider a dositive-definite function x. RF R.F R. By the Moore-Aronszajn theorem [3], there exists Hilbert space H. and a feature map o R + H such that
x(x,y) = (o(x), (ly)) for all x, E Rdd
(3)
In other words, any such function k. known as a kernel, defines lifting & and inner product (t,)). This defines geometry in H. through the norm [ oly)l,,, which in turn defines a notion of distance between and y and thus x(x, y) can be interpreted as similarity measure that we refer to as the kernel similarity between and y. For instance, for linear kernel s(x,y) y) x y, the map is simply the identity, (xx) = and distance in H corresponds to standard Euclidean distance in Rd
Kernel methods [13, 30, 25] facilitate non-linear modeling by leveraging to implicitly measure fea- ture similarity in the space H. thereby allowing otherwise linear models (e.g.. SVMs [1i]) to capture complex relationships without explicitly mapping data into that space. However, these methods typi- cally require instantiation of kernel matrix Kij = <(x,, x,) for a dataset X' = (x1...., X.) } C IR.F.. which leads to ((N2) memory complexity. Consequently, kernel methods often become impractical large scales, motivating efficient approximations.
A powerful class of such approximations are random kernel features. These methods build on lemma, which proves the existence of random linear map that
the famed approximately preserves pairwise distances in a dataset. Concretely, consider the same dataset X C TR. F from the last example. The JI. lemma states that for any ε E (0, 1), there exists linear map R E DxF to dimension D < F (with D= = O log F)) such that for all i,j
(1 =) |x, - 11 < Rxx - Rx < (1++) |1,
(4)
caiihsonnniindnstraan Transform (JL.T) implements such linear map R via random projection (e.g., Gaussian matrix, which achieves the bound above whp). In the context of kernel approxima- tions, one seeks a mapping y Rf + _ that provides an unbiased estimate of the kernel:
[[(((x) s(y)] y)
(5)
In the simplest case of the linear kernel, s((x,) = x y, we can directly take Puineur (x) = Rxx
yielding a lower-dimensional estimation yPtinerr (x) E R.D This provides an unbiased estimate of y while reducing computational costs relative to an explicit ( kernel matrix.

---

More recent work has shown that nonlinear kernels can also be estimated via random transformations akin the JLT [47]. In essence, one applies suitable nonlinearities to the randomly projected inputs, producing an unbiased approximation of a desired kernel (i.e. Equation 5), A prominent example is the use of random Fourier features [57], which enable efficient approximations of popular shift-invariant kernels such as the radial basis function (RBF) kernel ØRBF and Laplacian kernel Φc. Concretely, for the RBF kernel, one draws D frequencies wa for [D] from a Gaussian distribution, and applies a trigonometric mapping:
2 V (w) x b1), ....
GRBE (x)
+ bb)]
where by E [0, 2T) are sampled uniformly at random. Similarly, de is approximated by sampling w from Cauchy distribution and applying the same transformation.
In the next section, we apply these ideas in two distinct ways. First, we apply kernel embedding approximations (e.g., Equation 6) to estimate the feature map Φ. Second, we apply JLT projections to the resulting kernel embeddings and show that doing so leads to desirable qualities when augmenting MPGNNs. To avoid confusion, distinguish these two transformations clearly: the first set kernel transformations of node features and the second are Sketched Random Features (SRF).
Sketched Random Features
3.1 Defining SRF
Building on the ideas discussed in Section 1-2, our goal is to construct Sketched Random Features that (I) are distance-sensitive (2) unique, (3) encode signals across all nodes, and (4) remain permutation- equivariant under node relabelings.
Embedding Operator & Let X E NKF be the raw feature matrix, with each column of XT, denoted x,, corresponding to node We define an embedding operator & : RxF - R that applies function yp R + RDD to each column of X" independently. That is, E(X )., (x,).
In this work, we focus on yp functions that map features random embeddings whose inner products yield unbiased estimates (Equation 5) of a kernel x (Equation 3). Examples are Plinears P2c, and PRBF. as discussed in Section 2.2, yielding embedding operators Einaar Ec, and εRBF, respectively. Hence, we define the kernel feature matrix as
+ = E(X) NND.
Sketch Operator S. We next introduce sketch operator S RNDD NxD, This random projection matrix implements a Johnson Lindenstrauss Transform (JLT) (Section 2.2) which provides approximate preservation of pairwise distances with high probability (see Equation 4). In this work, we focus on the additive Gaussian (AG) sketch, which we define as:
SAG ()) = (1+ G)
where I E NxN the identity matrix, and E ing & by the sketch forms random linear combinations of all rows in Q.
I NNN has i.idd entries Gij ~ N 1). Multiply-
Unlike typical JLT applications, we do not reduce dimension N. Instead, we employ this random projection because it possesses properties (Propositions 3. 3.1-3.5) that we show in Section 3.2 can mitigate the standard limitations of message- -aassing GNNs. Importantly, the dimension D is determined by the embedding operator & rather than S.
Multi- Muoti-Proeection Sketching. SAG introduces one dimensional random projection of each column of Φ. We can generalize this to multiple dimensions via concatenation. Specifically, we introduce the k-order sketch operator AG NxD NXED,
N )b) = [1 J GO) + |1 (1+
|| (I | /N )( Φ
where each (k) E NNN is drawn independently with i.i.d. A'(0 1) entries. This operation concatenates & independent AG sketches, enabling k-dimensional estimates of each feature.
5

---

Sketched Random Features (SRF). Bringing these components together, we define the kernel sketch matrix Z as
7 S (E())) E R-Xx(DD)
(8)
where the new feature embedding of node is given by z; 2 Zz."" In our experiments (Section 4), we primarily analyze the (multi-) projection AG sketch AG introduced above, but also consider the trivial identity sketch S = as an ablation study. For embedding operator &, we consider the operators based on the random kernel features discussed in Section 2.2: Elinear, &c, and εRBF.
3.2 Enhancing MPGNNs with Node Feature Sketches
We next turn to incorporate SRF into MPGNNs, To do so, we augment the node hidden states h at each layer with the corresponding sketched embedding z, via concatination. Let ( [h. (E) denote this augmented representation, where [-|-] represents vector concatenation along the feature dimension. The updated MPGNN formulation becomes (ef. Equation I):
|z,]
(e+1) = / (b. (1) (h)) 1 (())))
By injecting z, at each layer, the model has access to both local node features and the information encoded by SRF. This strategy addresses common MPGNN weaknesses discussed in Section as detailed in the proceeding subsection. Algorithm summarizes the SRF-enhanced GNN procedure.
3.3 Properties of Sketched Random Features
We now establish key theoretical properties' of SRF and demonstrate how they address core limita- tions of message-passing GNNs. The following propositions characterize the fundamental mathemat- ical properties of our approach.
Proposition 3.1 (Unbiased Cross-Terms in the Kernel Matrix). SRF provides an unbiased estimation of tross-terms in the Kernel matrix. Specifically, for any distinct nodes i and j. the cross-term of the Gram matrix is unbiased: Ex.g [z 2j] k(x,,,, x,).
Proof. From Equation 7, the (ith) inner product is
2 2j
Σ
(Tip +
VN Gip) + Ggy ((xp) (x(x))-
p--=1
We note that for i + B[Gip) = and G[G = =5:30p = 0. Thus, by Equation 5, we have
Ex,ol2 z3} = Σ
Ji B(x((xp) (x(x)] [[(((x))T(((x <((x;,))) x,).
p.-=1
Proposition 3.2 (Kernel Distance Sensitivity). With high probability, there exists a positive e O(N-1/2) such that for any nodes i, j:
(1 (1=c))l+(x;) - =p(x))ll2 S |zz 125-2,122 2 s (1 (1+c) c))l(p(x;)) (((x))l2
Proof. By construction, 2; -; = I+ - G) (+(x,, ,x(x)) since each row z, corresponds to the i-th row of (I J G) E(x). If ((x:) = p(x;), then ||z; -2il22 = 0 and the claim holds trivially. Thus, assume (xx;)) # (((x)) and define (((x)) - -p((;)) Applying the triangle inequality:
||v J llvllal < || V| Gv/1, S ||vl2 + / 1|
II the featureless limit where all are identical, SRF degenerates to random node individualization [62, 1]. preserving expressive power through randomization.
For notational clarity, present proofs under base case
(11) and the extension to (k)
straightforward.

---

Next, the JL lemma (Equation 4) guarantees that, given [0, 1], with high probability over the choice of the random Gaussian matrix G
I S v
Substituting these bounds back into the triangle inequality shows
(1
+
z
2/l12
(1
1+
N
1
N
Thus, letting = +E)N completes the proof.
Proposition 3.3 (Cross-Node Information). For any node i, the sketched embedding 24 contains a linear combination of the embeddings of all nodes in the graph.
Remark. Proposition 3.3 ensures that each SRF embedding encodes cross-node information due to the row sketch construction.
Proposition 3.4 (Almost Sure Uniqueness). }z:} are unique with probability 1.
Proof. Without loss of generality, consider the case where the node features are identical, e.g. X; Then (xx;) (1) for all i, and from the definition of SRF with s(1) AG we have for row of Z:
= +11+
Σ G1z((1) ==1
Since (E)= Giyl are independent Gaussian random variables, the coefficients multiplying ((1) are almost surely unique. Thus, 2, f 2, for + j with probability 1. In the general case where node features differ, pxxx) and p(x,) may also differ, providing additional distinctness.
Proposition 3.5 (Permutation Equivariance in Expectation). Let be fixed permutation of node indices, with corresponding permutation matrix Pa. Let the function I SAG o E be the SRF operation (Equation 8). Then f permutation equivariant in expectation: Ex,af((xx)]] =
Ex,c(Pa((X))
Proof. By definition, S(X) = (I G) (X)) and E[G] = 0. Then
[[f(P;x)) = E (1 vN G) Pa Px)( Px)()),
and similarly
E[PaS(X)) = E A x(x) (X).
SRF Mitigates Oversquashing. SRF mitigates oversquashing by encoding topology-agnosti cross-node information in each sketched embedding 2,, as shown in Proposition 3.3. While this encoding into Rº (where typically D < N) is not lossless, enables direct information flow between all node pairs independent of their geodesic distance. This circumvents the exponential information bottleneck inherent in multi-hop message passing [2]. Our empirical analysis in Section 4.1 demonstrates that SRF achieves linear rather than exponential information loss as N increases.
SRF Alleviates Oversmoothing. SRF addresses oversmoothing by introducing node-specific, Distance-sensitivy embeddings that preserve variance across nodes (Propasitions 3.1 and 3.2, respec- tively). The inclusion of unique z, vectors (Proposition 3.4) repeatedly injected into message passing (Equation 9) ensures (i(() [b (*) z,] remain distinct as l grows. Our empirical results (Section 4.1)
show this approach maintains higher representation diversity even in base features h preventing representational collapse with depth.
'Note that while the version of the JL Jemma discussed in Section 2.2 (Equation 4) provides bounds for squared norms, taking square roots is valid since all terms are positive.
7

---

Oversquashing
Overs woothing
Oversmoothing
10'
10a
0.8
Diticheet eceegyy
Jccumay
0.6
Danchiet
10f
100
0.4
0.2
10:
107
0.0
2
Radius
Layer!
Layer 1
Figure Analysis of oversquashing and oversmoothing across model variants. (a) Accuracy vs. graph radius showing the effect of oversquashing across methods. (b) Dirichlet energy across layers for different methods. (c) Dirichlet energy across for & with varying k. Lower Dirichlet energy indicates more oversmoothing.
Universality of SRF in MPGNNs. SRF provides a principled way to achieve universality in MPGNNs. As discussed in Section 2, purely random features guarantee universality, but often fail to improve metric performance in practice. In contrast, structural encodings provide semantically meaningful and equívariant signals which lead improved empirical performance, but often fail to provide an encoding that is unique, distance sensitive and equivariant, due to the inherent difficulty of the graph canonization problem. SRF strikes a balance between these approaches: (Proposition 3. 3.4), ensuring universality, while preserving distance in the node feature kernel space whp (Proposition 3.2). Additionally, it permutation equivariant in expectation (Proposition 3.5).
unique
Memory and Runtime Complexity. While the JLT is traditionally implemented with dense random projection matrices, memory and runtime efficiency can be improved by using structured random matrices (SRMs) [15] detailed in Appendix A.2. SRMs lower storage requirements to ((N) and enable matrix-vecton multiplication in O( log N). Notably, these matrices preserve the theoretical guarantees of Section 3. This yields favorable asymptotic complexity compared many positional encoding methods. Detailed complexity analysis and comparisons are Appendix A.2.
4 Experiments
We empirically evaluate SRF-enhanced GNNs 4, first validating that SRF addresses key MPGNN limitations Section 1. then demonstrating performance on real-world benchmarks (Section 4.2). We use GIN [68] for unattributed-edge graphs and GINE [31] for edge-featured graphs, with additional architectures tested in Appendix B to verify architecture-agnosiie benefits.
We evaluate embedding operators Etinear &c, and εRAF with additive Gaussian sketch S(k) denoting configurations (E))()) ). To isolate sketching effects from kernel features alone, ablate with
) Full dataset descriptions, baseline details, hyperparameter search procedures, and other experimental details are provided in Appendix C. We include additional experiments in the Appendix: validation of SRF benefits across diverse GNN architectures (Appendix B) and analysis of SRF hyperparameters (embedding dimension D and projection count k) on performance (Appendix D).
identity operator S.a I, comparing (Ec, Sta) against (Ec, ((b)
4.1 Synthetic Learning Tasks
Oversquashing. We evaluate SRF's ability to mitigate oversquashing using the Tree- NeighborsMatch synthetic benchmark [2] discussed in Section 2. Recall that radius increases, exponentially more information must be aggregated by the message passing algorithm, making the task progressively harder for standard MPGNNs. Results in Figure show that while baseline GIN and ablation (Ez, suffer severe performance degradation beyond r = 4, SRF-enhanced models maintain higher accuracy at large radii, regardless of choice of E. Notably, all SRF variants achieve
OOu source code is available at bttps//gghhubbcommyyynnnnseeceee htw.sakeeecccddaaaannoo-onnssss

---

Table 1; Performance on synthetic expressiveness benchmarks. All results averaged over 5 runs. Standard deviations (s 0.002 across all experiments) omitted for clarity.
Datasct
Baseline
Ablation
Ours (S
Ours (S
None
Sta)
Elinear
ERBF
Elinear
Ec.
ÊRBF
CSL (Ace f) EXP (Ace f)
0,100
0.100
1.000
1.000
1.000
1.000
1.000
1.000
0.518
0.520
1.000
1.000
1.000
1,000
1.000
1.000
perfect accuracy up to - 4 and demonstrate more graceful performance decay thereafter, with accuracy remaining above 40% even at r 8. This improved performance large radii empiri- cally validates our theoretical analysis that SRF enables comparatively more effective long-range communication MPGNNs.
Oversmoothing. To assess SRF against oversmoothing, we follow Rusch et al. [61]'s protocol using Cora [51] with randomized features (X5x ~ (O, 1)) and measuring Dirichlet energy (Equation 2). Figure I(b) shows baseline GNNs exhibit near-exponential energy decay while SRF variants maintain substantially higher energy. While feature injection alone helps prevent decay (ablation study), Figure I(c) shows that increasing projections (k) further preserves node distinctness in deeper layers.
Expressiveness. We evaluate the universal approximation capabilities of SRF-enhanced MPGNNs using two graph isomorphism discrimination benchmarks: CSL [54] and EXP [1], containing graphs indistinguishable by 1-WL and 2-WL tests respectively. Table 1 shows SRF-enhanced models achieving perfect discrimination both datasets, while baselines and ablations (without sketching) perform no better than random chance.
4.2 Real-world Graph Learning Tasks
(8) Runtime
Memory Usage
We evaluate SRF-enhanced GNNs on real-world datasets, benchmarking against existing posi- tional encoding approaches (Section 2.1). Our results show SRF-enhanced GNNs outperform many positional encoding approaches (Table 2,
Runtime (s)
Memory (MB)
10
150
100
50
left) while offering substantial efficiency gains: about times faster runtime and about or- ders of magnitude less memory than PEARL on evaluated datasets (Figure 2). They show robustness in out-of-da int-of-distribution tasks where other approaches falter, remaining competitive with state-of-tt -t-te-of- approaches (Table 2, right). Finally, they can be combined with positional encodings for cumulative improvements due to their complementary nature (Table 3).
10a
REDDITEE
REDDITM
DragOOD
REDDIT-8
REDDITM
DrugGOD
(ours)
R-PEARL
B-PEARL
Figure 2: Training efficiency comparison of SRF (ours), R-PEARI, and B-PEARL. (a) Runtime in seconds. (b) Memory usage in MB (log scale).
Baselines. We consider several positional encoding baselines discussed in Section 2.1 and Appendix
A: random node features (rand id) [1, 62], SignNet and BasisNet [45], efficient approximations of SignNet (SignNet-8S, SignNet-8L. [36]. SPE [32] with its efficient variant SPE-8S, and Pearl (R-PEARL, B-PEARL) [36]. For some experiments, we include graph transformers and attention- enhanced GNNs:
GPS [58], SAN [41], SUN [24], GNN-AK [71], Graph ViT [29].
Social Network Classification. We evaluate on REDDIT-B and REDDIT-M datasets [69], which represent online discussion threads where nodes are users and edges indicate comment interactions. These datasets require models to classify discussion graphs into their respective subreddits (online communities). As shown Table 2, SRF-augmented GNNs consistently outperform baseline methods. Notably, even our simplest variant (Eiinear) demonstrates substantial improvements over prior ofte-oo-the-art methods, with εRBE providing the strongest performance. The ablation confirms these gains derive from sketching rather than merely adding kernel features.

---

Table 2: Performance comparison of SRF enhanced GNNs and several positional encoding baselines on Reddit (% accuracy) and DrugOOD (% AUC) datasets. Results for baselines from Kanatsoulis et al. [36]. Values missing from the literature are denoted by "-" OOM indicates out of memory. First, second, and third best results are highlighted blue, green, and orange, respectively.
Reddit (Ace f)
DrugOOD (AUC
REDDIT-B
REDDIT-M
Assay
Scaffold
Size
Baselines:
GINE (No PE)
91.8 = 1.0
56,9 2.0
71.68 1.10
68.00 0.60
66.04 = 0.70
GINE rand id
91.8
5.10
SignNet
OOM
OOM
72.27 = 0.97
66.43 1.06
64.03 + 0.70
SignNet-8S
92.4 + 1.1
57.8 0.8
SignNet-8I.
79.5 + 12.3
41.4 +
BasisNet
71,66 0.05
66.32
5.68
60.79 3.19
SPE
72.53 0.66
69.64
0.49
66.02 0.49
SPE-8S
71.72 1 0.71
68.72 1 0.63
1 2.20
R-PEARL
93.0 L 1.3
59.4 L 1.0
72.24 - 0.30
69.20 1 1.00
65.89 1 1.30
B-PEARL
71.22 = 0.42
69.51
0.62
66.58 = 0.67
Ablation: (Ec. Sia)
92.56 + 0.58
58.32 + 0.47
71.89 + 0.37
65.34
0.26
63.29 + 0.63
Ours: (8))
Emnear
94.06 + 0.39
60.18 + 0.39
72.29 = 0.30
68.79 + 0.64
66.45 + 0.24
Ec
94.00 0.35
60.33 + 0.37
72.51 0.69
69.43 0.90
67.23 0.54
εRBF
94.13 + 0.69
60.53 1 0.29
72.63 0.41
69.60 0.48
66.67 0.35
Molecular Graph Out-of-Distribution (OOD) Generalization. We evaluate OOD generalization on DrugOOD [33], which tests molecular property prediction across three domain shifts (Assay, Scaffold, Size). As Kanatsoulis al. [36] demonstrate, these OOD tasks are particularly challenging for positional encoding approaches, with many advanced methods actually degrading performance compared to GNN backbones alone. Conversely, Table 2 demonstrates that our feature-based augmentation approach effectively overcomes this limitation, with all SRF variants consistently outperforming the baseline GINE model across splits. Notably, our approach achieves state-of-the- art performance on the Assay and Size shifts, and remains competitive on the Scaffold split.
Long-Range Interactions in Peptide Structure Prediction. To assess whether SRF complements structural approaches, we evaluate on Peptides-struct [22], a benchmark with long-range dependencies where graph transformers typically excel. Table 3 shows that combining PEARL positional encodings and SRF augmentation (ERBF, A closes the performance gap between graph transformers and GNNs, verifying SRF provides complementary benefits to positional encodings.
Table 3; Performance comparison for peptide-struct (MAE, lower is better). Bascline results reported by Kanatsoulis al. [36]. Error bars presented in Appendix but do not exceed + 0.004.
Baselines
Ours
SAN+ RWSE
R-PEARL +SRF
B-PEARL +SRF
R-PEARL
B-PEARL
GPS
GNN-AK+
SUN
Graph VIT
0.247
0.248
0.252
0.255
0.274
0.250
0.245
0.245
0.243
5
Conclusion
We have presented an unconventional application of the Johnson- Lindens-Lindssssruuss transform for en- hancing message-passingg graph neural networks. Our theoretical analysis and empirical results demonstrate that such strategy overcomes well-known shorteomings of MPGNNs with minimal computational overhead, making it a practical enhancement for existing architectures. A promising direction for future work is to investigate whether analogous sketching techniques generalize to topology-awan aware embeddings (e.g., graph random kernel features [16]) structural encodings.
10

---

Acknowledgments and Disclosure of Funding
This research used resources of the Argonne Leadership Computing Facility, U.S. Department of Energy (DOE) Office of Science user facility at Argonne National Laboratory and is based on research supported by the U.S. DOE Office of Science-Advances Scientific Computing Research Additional funding support comes from the National Science Foundation (CCF-21191 CNS-23131 CCF- CCF-1822949 CNS-19566 1956180)) 80). RW gratefully acknowledges the support of NSF DMS-2023 109, DOE DE-SC0022222. the NSF-Simons National Institute for Theory and Mathematics in Biology (NITMB) through NSF and Simons Foundation MM-TMPPS-000053200 and the Margot and Tom Pritzker Foundation.
Program, under Contract No. DE-AC02-06CHI
References
[1] Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The sur- prising power of graph neural networks with random node initialization. arXiv preprint arXiv:2010.011 179, 2020.
[2] Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021. URL https: /oopnnrviiew wwwperrviie..net/ooumn222... aet/ftorum2:dd11000AAAWV
[3] Nachman Aronszajn. Theory of reproducing kernels. Transactions of the American mathemati- cal society, 68(3)333,4444 1950.
[4] Waiss Azizian and Mare Lelarge. Expressive power of invariant and equivariant graph neural networks. In International Conference on Learning Representations, 2021. URL https: / //openreviww net wearrmmmddxxxxxx4444
[5] László Babai and Eugene M Luks. Canonical labeling of graphs. In Proceedings of the fifteenth annual ACM symposium on Theory of computing, pages 171-183, 1983.
[6] Linus Bao, Emily Jin, Michael Bronstein, ismail ilkan Ceylan, and Matthias Lanzinger. Homo- morphism counts structural encodings for graph learning. arXiv preprint 2rXfv:2410.18676. 2024.
[7] Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M. Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks. In International Conference Learning Representations, 2022.
[8] Ella Bingham and Heikki Mannila. Random projection in dimensionality reduction: applications to image and text data. In Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, pages 245-250, 2001.
[9] Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions Pattern Analysis and Machine Intelligence, 45(1):657-666 2022.
[10] Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? arXiv preprint arXiv:2105. 144.9 2021.
[11] Christopher JC Burges. tutorial on support vector machines for pattern recognition. Data mining and knowledge discovery, 2(2):121 1998.
[12] Chen Cai and Yusu Wang. A note on over-smoothing for graph neural networks. arXiv preprint arXiv:2006. 13318, 2020.
[13] Colin Camphell. Kernel methods: survey of current techniques. Neurocomputing, 48(1-4): 63-84, 2002.
[14] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International conference on machine learning, pages 1725-1735. PMLR, 2020.

---

[15] Krzysztof M Choromanski, Mark Rowland, and Adrian Weller. The unreasonable effectiveness of structured random orthogonal embeddings. Advances in neural information processing systems, 30, 2017.
[16] Krzysztof Marcin Choromanski. Taming graph kernels with random features. In International Conference Machine Learning, pages
PMLR, 2023.
[17] Fan RK Chung. Spectral gruph theory, volume 92, American Mathematical Soc., 1997.
[18] George Dasoulas, Ludovic Dos Santos, Kevin Scaman, and Aladin Virmaux. Coloring graph neural networks for node disambiguation. arXiv preprint arXiv:19120060S: 2019.
[19] Nima Dehmamy, Albert-LászIó Barabási, and Rose Yu. Understanding the representation power of graph neural networks in learning graph topology. Advances in Neural Information Processing Systems, 32, 2019.
[20] Francesco Di Giovanni, Lorenzo Giusti, Federico Barbero, Giulia Luise, Pietro Lio, and Michael M Bronstein. On over-squashing in message passing neural networks: The impact of width, depth, and topology. In International Conference on Machine Learning, pages 7865-7885. PMLR, 2023.
[21] Zchao Dong, Muhan Zhang. Philip RO Payne, Michael A Province, Carlos Cruchaga, Tianyu Zhao, Fuhai Li, and Yixin Chen. Rethinking the power of graph canonization in graph represen- tation learning with stability. arXiv preprint arXiv:2309.00738 2023.
[22] Vijay Prakash Dwivedi, Ladislav Rampášek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. Advances in Neural Information Processing Systems, 0222326-223444 2022.
[23] Vijay Prakash Dwivedi, Chaitanya K Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24(43):1 48, 2023.
[24] Fabrizio Frasca, Beatrice Bevilacqua, Michael Bronstein, and Haggai Maron. Understanding and extending subgraph gnns by rethinking their symmetries. Advances in Neural Information Processing Systems, 35:31376-31390, 2022.
[25] Benyamin Ghojogh, Ali Ghodsi, Fakhri Karray, and Mark Crowley. Reproducing kernel hilbert space, mercer's theorem, eigenfunctions, nystr'." " method, and use of kernels in machine learning: Tutorial and survey. arXiv preprint arXiv:2 08443, 2021.
[26] Justin Gilmer, Samuel S Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning. pages 1263-1272 PMLR, 2017.
[27] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[28] Arman Hasanzadeh, Ehsan Hajiramezanali, Shahin Boluki, Mingyuan Zhou, Nick Duffield, Kr- ishna Narayanan, and Xiaoning Qian. Bayesian graph neural networks with adaptive connection sampling. In International conference on machine learning, pages 4094 4104. PMLR, 2020.
[29] Xiaoxin He, Bryan Hooi, Thomas Laurent, Adam Perold, Yann LeCun, and Xavier Bresson. generalization of vit/mlp-mixer to graphs. In International conference machine learning. pages 12724-12745. PMLR, 2023.
[30] Thomas Hofmann, Bernhard Schölkopf, and Alexander J Smola. Kernel methods in machine learning. 2008
[31] Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks, arXiv preprint arXiv: I 1905. 12265, 2019.
12

---

[32] Yinan Huang, William Lu, Joshua Robinson, Yu Yang. Muhan Zhang, Stefanie Jegelka, and Pan Li. On the stability of expressive positional encodings for graphs. arXiv preprint arXiv:2310002579, 2023.
[33] Yuanfeng Ji, Lu Zhang, Jiaxiang Wu, Bingzhe Wu, Lanqing Li, Long-Kai Huang, Tingyang Xu, Yu Rong, Jie Ren, Ding Xue, et al. Drugood: Out-of-distribttion dataset curator and benchmark for ai-aided drug discovery-a focus on affinity prediction problems with noise annotations. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 2023.
[34] Emily Jin, Michael Bronstein, Ismail IIkan Ceylan, and Matthias Lanzinger. Homomorphism counts for graph neural networks: All about that basis. arXiv preprint wxXv:2442.08855, 2024.
[35] William B Johnson, Joram Lindenstrauss, and Gidcon Schechtman. Extensions of lipschitz maps into banach spaces. Israel Journal of Mathematics, 129-138,, 1986.
[36] Charilaos I Kanatsoulis, Evelyn Choi, Stephanie Jegelka, Jure Leskovec, and Alejandro Ribeiro. Learning efficient positional encodings with graph neural networks. arXiv preprint arXiv:2502.01122 2025.
[37] Asifullah Khan, Anabia Sohail, Umme Zahoora, and Aqsa Saced Qureshi. A survey of the recent architectures of deep convolutional neural networks. Artificial intelligence review, 53: 5455 5516,, 2020.
[38] Jinwoo Kim, Saeyoon Oh, and Seunghoon Hong. Transformers generalize deepsets and can be extended to graphs & hypergraphs. Advances in Newral Information Processing Systems, 34: 28016-28028, 2021.
[39] Jinwoo Kim, Dat Nguyen, Sconwoo Min, Sungjun Cho, Moontae Lee, Honglak Lee, and Se- unghoon Hong. Pure transformers are powerful graph learners. Advances in Neural Information Processing Systems, 155144822-45595 2022.
[40] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: 1609.02907, 2016.
[41] Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létournaau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. Advances in Neural Information Pro- cessing Systems, 34:21618-21622 2021.
[42] Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go deep as cnns? In Proceedings of the IEEE/CVF international conference on computer vision, pages 9267-9276, 2019.
[43] Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. Advances in Neural Information Processing Systems, 33:4465 4478, 2020.
[44] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-super learning. Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
[45] Derek Lim, Joshua Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and basis invariant networks for spectral graph representation learning. arXiv preprint arXhv:2202. 10113, 2022.
[46] Kevin Lin, Lijuan Wang, and Zicheng Liu. Mesh graphormer. In Proceedings of the IEEE/CVF international conference on computer vision, pages 12939-12948, 2021.
[47] Fanghui Liu, Xiaolin Huang, Yudong Chen, and Johan AK Suykens. Random features for kernel approximation: A survey on algorithms, theory, and beyond. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(10):7128-711 2021.
[48] George Ma, Yifei Wang, and Yisen Wang. Laplacian canonization: A minimalist approach to sign and basis invariant spectral embedding. Advances Neural Information Processing Systems, 36:1 (1226-11337) 2023.
13

---

[49] Liheng Ma, Chen Lin, Derek Lim, Adriana
Puneet K Dokania, Mark Coates, Philip Torr, and Ser-Nam Lim. Graph inductive biases in transformers without message passing. In International Conference on Machine Learning, pages 23321-23337. PMIR, 2023.
[50] Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In International Conference on Learning Representations, 2018.
[51] Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3:127-163, 2000.
[52] Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 2602-4609, 2019.
[53] Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M Kriege, Martin Grohe, Matthias Fey, and Karsten Borgwardt. Weisfeiler and leman go machine learning: The story so far. The Journal of Machine Learning Research, 2A(1):15865-1522) 2023.
[54] Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In International Conference Machine Learning, pages 4663-4673. PMLR, 2019.
[55] Daniel Neuen. gammommrphhism-disiingiiiie closedness for graphs of bounded tree-width. arXiv preprint arXiv:2304.07011/ 2023.
[56) Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations, 2020. URL
https://openreiian www.iiiwnee/ffrmmmm.e -iddmdddSSS11SFFFP
[57] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in neural information processing systems, 20, 2007.
[58] Ladislav Rampásek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for a general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 35:14501-145155 2022.
[59] Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 15011-11145,5 2022.
[60] Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. arXiv preprint arXiv: 1907.19000000 2019.
[61] T Konstantin Rusch, Michael M Bronstein, and Siddhartha Mishra. survey on oversmoothing in graph neural networks. arXiv preprint arXiv:2303.1099) 2023.
[62] Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM international conference on data mining (SDM), pages 333-341. SIAM, 2021.
[63] Ahsan Shehzad, Feng Xia, Shagufta Abid, Ciyuan Peng, Shuo Yu, Dongyu Zhang, and Karin Verspoor. Graph transformers: A survey. arXiv preprint axXiv:2407.09777, 2024.
[64] Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. Understanding over-squashing and bottlenecks graphs via curvature. 2021.
arXiv preprint
[65] A Vaswani. Attention is all you need. Advances in Neural Information Processing Systems, 2017.
[66] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710.10003 2017.
14

---

[67] Boris Weisfeiler and Andrei Leman. The reduction of graph to canonical form and the algebra which appears therein. nti, Series, 2(9):12-16, 1968.
[68] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv: 2018.
[69] Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pages 1365-1374, 2015.
[70] Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Ya Liu. Do transformers really perform badly for graph representation? Advances in neural information processing systems, 34:28877-28888,, 2021.
[71] Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any gnn with local structure awareness. arXiv preprint arXiv:2//0.03/// 2021.
[72] Kaixiong Zhou, Xiao Huang. Daochen Zha, Rui Chen, Li Li, Hoyu Choi, and Xia Hu. Dirichlet energy constrained learning for deep graph neural networks. Advances in Neural Information Processing Systems, 34:21834-21 2021.
15

---

A SRF Background and Complexity Analysis
Preprocess (once)
Input EV X K
Feature Encoder ((X)
Cross-Node Sketching
Z
S
irject S,
GNN waiting (per spoch)
Node Update
Initialization
Message Passing
h te1 1
A (b (hif
Output h (
h = vi E
6
x.
J N61)
repert Lyens
Figure 3: Block diagram visualizing the SRF method defined in Algorithm 1. SRF is computed once (top, blue) and then concatenated to node states every GNN layer during training (bottom, green).
This section expands on the limitations of MPGNNs discussed in Section 2.1, reviews prior mitigation strategies, and compares the computational complexity of SRF with recent baselines. Figure overviews the SRF preprocessing strategy defined in Algorithm and described in detail in Section 3.
A.1 Additional Discussion on Prior Work
Oversquashing. Theoretical work formalizes oversquashing by analyzing the partial derivative of the hidden states of nodes and j at depth 1, i.e. jan!) /Ohş). with Topping et al. [64] showing bounded by c- A for constant c. graph adjacency matrix A, and geodesic distance d, thereby implying that node h; and h, become exponentially less sensitive each other as grows. Furthermore,
Di Giovanni et al. [20] validate the intuition posed in Alon and Yahav [2], proving that increasing hidden dimension |h| can alleviate oversquashing, whereas greater depth |L] alone fails to resolve
Recent work seeks to mitigate oversquashing in MPGNNs by defining a rewiring Q R -> Raxx that operates the adjacency matrix A to yield Q(A), hence producing a rewired graph G'. This process reduces either the graph diameter or the Cheeger constant (which quantifies the connectivity of a graph relative its cut size) [17]*. Thus, these strategies alleviate oversquashing by altering topology to remove bottlenecks. However, this leads to an altered and usually denser graph G', undermining the original topological bias of message passing and increasing computational overhead.
Oversmoothing. Common ways to mitigate oversmoothing include strategies based on regulariza- tion [28, 72, 60] skip connections [42, 14]. Nevertheless, striking balance between preventing oversmoothing and preserving the expressive power of deeper GNNs remains challenging. Indeed, recent evidence suggests that merely suppressing oversmoothing without enhancing model's capac- ity may still limit its ultimate performance [61]. We refer interested readers to the recent survey by Rusch al. [61] for more detailed discussion.
Limited Expressiveness.
pedagogical example of the shortcomings of existing positional en- codings described in Section 2 is the use of Laplacian eigenvectors (e.g. [23]), which can produce multiple valid solutions depending on the chosen sign or basis, and may fail to distinguish co-spectral but non-isomorphic graphs. This limitation motivates a body of existing encoding approaches such as learned [50] and heuristic-basee [21] eigenvector canonization. However, as described in the main manuscript, designing encodings based on topology that are unique, distance sensitive, and cquivariant in polynomial time may be impossible due to its relatedness to graph canonization [5]. We refer interested readers to the recent survey by Morris et al. [53] for a more comprehensive overview of positional encodings for GNNs.
As described in the main manuscript, recent work presented by Kanatsoulis et al. [36] instead aim to learn positional encodings using a message passing module that trained end-to-end with the main
We credit Di Giovanni al. [20] for unifying these prior approaches and offering comprehensive overview.
16

---

("backbone") GNN. The PEARL methodology begins by anonymizing the input graph by stripping away all node and edge attributes. For each node in the graph, the framework generates M random (R-PEARL) or basis (B-PEARI) attributes. These generated samples are then individually processed through GNN and its outputs are combined using pooling function p to create (equivariant) positional encodings. In the final stage, the framework processes the graph structure alongside the generated PEs and any existing node or graph attributes, using either a GNN or Graph Transformer for the final analysis. Thus, PEARL's positional encodings enjoy better asympotic complexity than positional encoding methods, including a linear, rather than cubic cost, in the number of nodes in the input graph. However, unlike these classical methods, PEARL pays this (n) cost for each graph at every epoch of training.
many classical (e.g. spectral-based
A.2 Complexity Analysis
SRF Complexity and SRMs. We analyze the runtime complexity of computing Sketched Random Features (SRF) when using structured random matrices (SRMs) as the sketching operator, as intro- duced in Section of the main manuscript. SRMs, introduced by Choromanski el. [15], are designed to accelerate Sransonn-innenstraaii
projections while preserving statistical properties of dense Gaussian matrices. Specifically, SRMs such as SD SD-product matrices (e.g.. Hadamard Rademacher constructions) admit fast matrix-vector multiplication in time O(N log N), rather than the (NN)) cost incurred by unstructured dense matrices. When applied to a full matrix E NxD consisting of D feature vectors, the corresponding matrix-matrix multiplication with SRM costs ( log N).
Our SRF construction proceeds in two stages. Given an input feature matrix X E RNXF, we first compute kernel embeddings by applying a random feature map á : R + R (c.g.. random Fourier features [57]) to each row of X, yielding the matrix = E(X) E R-NxD This step has complexity O(NFD) under the assumption that & involves dense linear projections.
In the second stage, we apply a sketching operator S(R) consisting of k independent SRMs to 4, producing the final sketched matrix 2 = (4) E RNXAD, Since each SRM projection costs O(N² log.N N), the total cost across k independent sketches is O(KN2 log N). Combining both stages, the overall runtime complexity of SRF is:
O(NED + KN2 kN N).
This is asymptotically more efficient than using dense Gaussian projections, which incur a cost of Ok+N3), while preserving similar guarantees on distance preservation and kernel approximation [15].
Finally, in the context of our broader complexity analysis, which considers scaling with respect to the number of nodes N and the number of training epochs T, we observe that SRF features are computed once at initialization and reused throughout training. Thus, like spectral encodings. SRF contributes a one-time cost and does not scale with T. The dominant term is the ROM projection, yielding an effective runtime complexity of O(N2 log N) and memory complexity of O(N) with respect to the graph size.
Additional Discussion on Computational Complexity. We analyze the computational and memory complexity of baseline methods described in Sections 3 and 4. Table 4 presents the complexity of these methods with respect to the number of nodes N. The analysis distinguishes between methods that require preprocessing versus those that perform computations during each forward pass. Preprocessing methods like random id [1] and SRF (ours) incur their computational cost once before training. then impose minimal overhead per epoch, while other methods perform their stated complexity computations during each forward pass. In scenarios where graphs are processed over many training epochs, preprocessing approaches achieve computational advantages as the number of epochs approaches or exceeds the graph size. Many graph learning benchmarks commonly found in the literature, including those used evaluate PEARL and SPE, involve small graphs processed over many training epochs, favoring preprocessing approaches. Runtime benchmarks in Figure 2 complement this complexity analysis, demonstrating that SRF achieves superior computational efficiency in such scenarios. This efficiency advantage is also partially attributed to PEARL's requirement for large number of graph samples that we empirically observe often scale with the number of graphs in the dataset. In scenarios where the required sample count is substantially smaller than the number of nodes, PEARL's empirical runtime would likely be comparatively more favorable. Future work should empirically validate this hypothesis.
17

---

Table 4: Comparison of computational and memory complexity for various GNN positional encoding methods with respect to number of nodes N. Methods marked with incur costs once before training. while others incur costs per forward pass. When the number of training epochs is comparable to graph size, preprocessing methods achieve computational advantages.
Method
Computational Complexity
Memory Complexity
Random id"
(
((N)
SignNet
((N3)
(
SignNet-8S
((Na)
((N)
SignNet-8L.
(N)
O(N)
BasisNet
O(Na)
(
SPE
O(N
O
SPE-8S
O(Na)
O
R-PEARL
O(N)
O(N)
B-PEARL
((2)
O(N)
SRF (ours)* (N2 log N)
O(N)
A.3 Additional Discussion on Baselines
For completeness, describe the key methodological components of baseline encoding approaches referenced throughout the main manuscript. A qualitative summary of the differences between different baseline methods and SRF is provided in Table 5.
SignNet and BasisNet. Lim et al. [45] present SignNet and BasisNet, neural architectures that solve the sign and basis ambiguity problems spectral graph positional encodings. SignNet addresses sign invariance by parameterizing functions of the form f( vx) = p ((0();) + (({+))) where the structure @(u;) + ((-o;) ensures invariance to sign flips of each eigenvector v. and ø and p are neural networks (e.g.. GIN and MLP respectively). BasisNet handles basis invariance in nigher-dimensional eigenspaces by computing fVV...... Vi) p (IGN&, (VVV)))=)) where Vi [_xd; are orthonormal bases of eigenspaces, the mapping V + VVT produces the orthogonal projector which invariant to basis changes VQ for orthogonal Q and IGNs (Invariant Graph Networks) process the resulting matrices while maintaining permutation equivariance. Both methods can incorporate eigenvalues and node features as additional inputs, and the processed eigenvectors concatenated with original node features before being fed to downstream prediction models. Kanatsoulis et al. [36] introduce efficient variants: SignNet-8S and BasisNet-8S utilize the 8 small- eigenvalues while maintaining O(N3) computational complexity, with SignNet-8S achieving reduced O(N) memory complexity compared to the original O(N2). SignNet-8L. uses the 8 largest eigenvalues, achieving both O(N) computational and memory complexity.
Hybrid Models and Miscellanies. GPS [58] proposes modular Graph Transformer frame- work that decouples local message-passing from global attention, combining three components: positionall/sruutuuaal encodings, local aggregation mechanisms, and global attention in unified architecture. SAN [41] uses a learned positional encoding based on the Laplacian spectrum, which is added to node features before processing with a fully-connected Transformer. GNN-AK+ [71] extends standard MPNNs by replacing star-pattern aggregation with general subgraph pattern aggre- gation, where each node representation is computed from an induced subgraph encoding rather than just immediate neighbors. Graph ViT [29] adapts the Vision Transformer architecture, achieving linear complexity while capturing long-range dependencies and mitigating over-squashing through global receptive fields. SUN [24] combines subgraph-bar based methods with neural networks to enhance expressivity beyond traditional message- passgggg limitations.
B GNN Architecture Analysis
To verify that our approach generalizes across different GNN architectures, we evaluate SRF with three additional backbone architectures: Graph Convolutional Networks (GCN) [40], Graph Attention Networks (66)))66), and Graph Attention Networks v2 (1) We compare against random
18

---

Table 5: Qualitative comparison of SRF to common baselines. Properties summarize typical behavior discussed in the main text and Appendix. Entries consolidate theoretical and empirical properties established or referenced throughout the manuscript. "Denotes families of methods; specific variants may differ in details, but the stated properties reflect their typical guarantees and practical behavior.
Method
Unique Represetation?
Semstive?
Equivariant?
Mitigates Oversuashing?
Alleviates Ovrrsmothing?
Random Node Features
Almost surely
No Yes
expectation
No
No
Spectral Encodings
No
Yes
No
No
Sulgruyh encodings!
Yes
Uselea
Homommrphen phiso comnts'
Yes
No
Unclear
PEARL
Unclear Almost surely
With high probability With high probubility
Yes
No
No
SRF (Ours)
In expectation
Yee
Yeu
feature injection baselines that maintain the same total number of learnable parameters. Following Abboud et al. [I], we inject random features, but unlike their approach, we perform reinjection at each layer to provide a fair comparison with our method's 's parameter count. All experiments use the hyperparameter configurations of the GIN/E models for which results are presented in Section 4.
Table 6 presents the results REDDIT-B and REDDIT-M datasets. Across all architectures, most SRF variants consistently outperform random feature haselines, demonstrating that the performance gains are not dependent on the specific choice of GNN backbone. However, we find that random features do slightly outperform a single variant, (ERBr, AA)) on one experiment (REDDIT-B dataset and GAT backbone). Interestingly, relative performance differences between SRF variants across
architectures, are slightly different than in the trend found in Section 4.2, with (Eíinerr ( achieving slightly stronger comparative performance for some dataset/backbone pairs. Future work should investigate whether these performance variations arise from architecture-specffi hyperparameter sensitivities or inherent compatibility differences between SRF variants and GNN backbones.
C Experimental Details
C.1 Dataset Descriptions
Here, we describe properties of the real world graph datasetrs used our experiments. All datasets are used in accordance with their respective licenses and terms of use.
Reddit-B and Reddit-M. The Reddit datasets [69] consist of graph classification tasks where each graph represents online discussion thread. Nodes correspond to users and edges indicate response relationships between users' comments. Reddit-B contains 2,000 graphs across 2 classes with an average of 429.6 nodes per graph, where the task is classify discussion threads belonging to question/answer-baseed communities versus discussion-bar based communities. Reddit-M contains 5,000 graphs across classes with average of 508.5 nodes per graph, where the task is to predict which specific subreddit a discussion thread belongs to.
DrugOOD, The DrugOOD dataset [33] evaluates models on drug-target binding affinity prediction. The dataset focuses on domain shifts arising from different bioassays (Assay), molecular scaffolds (Scaffold), and molecular sizes (Size), testing the ability to generalize to unseen experimental conditions, molecular structures, and compound sizes respectively. Each sample consists of paired protein-compound data with binary classification labels indicating binding activity.
generalization for
Peptides-struct. The Peptides-struct dataset [22] from the Long Range Graph Benchmark com- prises over 15,000 molecular graphs with more than 2 million nodes total, where individual graphs range from 8 to 444 nodes. The dataset involves multi-label regression on 3D structural properties of peptides, including inertia, length, sphericity, and geometric fit measures. Graphs are constructed with heavy atoms as nodes and chemical bonds as edges, requiring models to capture long-range interactions without explicit 3D coordinate information.
19

---

Table 6: Performance (Accuracy %) comparison of SRF variants across different GNN architectures on Reddit datasets. Random feature injection is a parameter-matched baseline with reinjection at each layer.
Architecture
Method
REDDIT-M
REDDIT-B
Random Features
53.46 + 1.00
91.60 + 1.04
GCN
(Etinear S(8)
AG
58.04 + 1.00
93.30 + 0.72
(E
57.20 = 0.90
93.30 + 0.72
(ERRF, S18)
58.08 0.89
93.05 + 0.16
Random Features
47.75 +: 0.84
86.55 + 1.89
GAT
(Etinear AG
51.40 + 1.04
89.05 + 1.17
(Ec, AG
((8)
49.64 = 0.96
88.15 + 1.43
(ERAF, ((8)
49.72 + 1.02
86.15 + 1.43
AGG
Random Features
46.88 + 0.89
84.2 + 0.76
(Eiinear S(8)
GATv2
AG
52.04 + 0.56
87.4 + 0.74
(Ec, ((8]
(E2,
AG)
48.76 + 0.89
87.6 + 0.42
(ERBF, (18)
48.40 1.27
86.7 1.30
C.2 Training Details and Hy perpaaareeee Search Procedure
All experiments use SRF with parameters A: == 8 and search over the SRF hyperparameter D E (16, 32, 64, 128, 256) (See Section 3). Hyperparameter optimization is conducted using Weights and Biases across all datasets. The Adam optimizer is used throughout all experiments.
Reddit Datasets. Following standard practice [36], we employ 10-fold cross coos--valdation and report results for the best epoch across 330 training epochs. We report mean and standard deviation across folds. We CrossEntropy loss with sum pooling. The hyperparameter grid search includes: number of layers {3, 4, 5, 6, 7, 8), hidden dimensions E {32, 64, 128, 256, 512}, batch size e (16,32 32, 64, 128), and learning rate [10-5, 10-2).
DrugOOD. We follow the experimental setup from [36], training for 150 epochs and report- ing results the out-of-distribution test set using LI loss. The hyperparameter search includes: number of layers E {3. 4, 5, 6, 7}, batch size E (16. 32, 64, 128). learning rate E [10 10 2], layer normalization
(true, false), batch normalization [true, false), and hidden dimensions E {32, 64, 80, 90, 100, 110).
Peptides-struct. Models are trained for 500 epochs using LI loss with residual connections. The hyperparameter search includes: number of layers E {4, 5, 6, 7, 8, 9}. hidden dimensions {70, 95, 105, 135, 150), batch size (10, 25, 50, 75), learning rate E [10-) 10021, 21, layer nor- malization E (true, ),lse), and batch normalization E (true, false]. We additionally include the hyperparameters used by PEARL [36] in their evaluation, as combine the methods (Section 4). Results are reported for Eimear sketch variant. Error bars as reported by Kanatsoulis er al. [36] are +0.001 for PEARL-B, PEARL-R, GPS, SUN, and SAN+RWSE: +0.002 for Graph VIT; +00.004 for SAN+LapPE; and 0.00 for GNN-AK+. The error bars for our variants are +-0.004.
C.3 Hardware and Software Tools
Our graph processing and learning experiments utilize the open- source PyTorch Geometric library as the primary framework, with NetworkX serving as supplementary tool for graph operations. To ensure reproducibility and accurate runtime evaluation, we include a catalog of all software depen- dencies and their specific versions in the Supplementary material. An anonymized implementation of our codebase is also made available in the Supplementary material. All performance evaluations were conducted using AMD EPYC 7713 64-Core Processor running Red Hat Enterprise Linux 9.3
20

---

and NVIDIA DGX A100 GPUs (80GB memory). At times during experimentation, cluster of 8 such GPUs were used run parallel experiments.
C.4
Limitations
While SRF provides a principled and efficient mechanism for enhancing GNNs with global, feature- based information, it also has several limitations. First, its effectiveness relies on the presence of informative node features; in domains where features are sparse, noisy, or absent, performance gains may be limited. Second, as SRF relies on randomized projections, its properties hold in expectation; in practice, this introduces variance across runs, although empirical results indicate this effect negligible. Third, SRF is inherently topology-agnosti and may fail to capture structural signals that positional encodings spectral methods explicitly model, but as noted, SRF can be used to complement these approaches. Finally, SRF introduces modest computational overhead compared to vanilla GNN, though it is much more efficient than spectral methods.
D Analysis of SRF Embedding Dimension and Projection Count
(a) Projection Count
(b) SAI Dimension
65.25
61.02
ACCURSIC (46)
59.8
60.23
59.6
60.02
53.4
59.75
53.2
Projection 64)
Total slatcs dimemion (
Figure 4: Hyperparameter sensitivity analysis on REDDIT-M using (Eimeeur A (a) Performance (accuracy %) projection count k with D = 64 fixed. (b) Performance (accuracy %) vs. total sketch dimension D with l: = 8 fixed.
The SRF framework introduces two hyperparameters that control the quality and computational cost of the sketched embeddings: embedding dimension D and projection count 3. Understanding the sensitivity of SRF performance to these parameters is helpful for practical deployment.
The embedding dimension governs the fidelity of the underlying kernel approximation as estab- lished in the main manuscript. Larger D provides more accurate kernel estimates but increases computational overhead. The projection count determines the rank approximation the random projection, with higher & potentially improving the quality of cross-node information encoding at the cost of increased overhead.
In this Appendix, we evaluate the impact of these hyperparameters with simple case-study experi- ment. To isolate the effect of projection count k, we fix D 64 and vary {1, 2, 4, 8, 16, 32, 64). To assess the impact of embedding dimension 1) while controlling for total sketch dimensionality. we fix the total sketched feature size k D E (8, 16, 32, 64, 128} and set 8, allowing to vary accordingly.
Our hyperparameter sensitivity results presented in Figure for the REDDIT-M dataset using operator (Eiincar ((k) ). Due to computational limitations, we focus the analysis on this single dataset-operator combination.
Projection Count Analysis (Figure 4a). The results demonstrate performance trade-off when varying the projection count & and maintaining fixed total sketch dimensionality. Performance peaks and subsequently declines increases. This pattern is likely due an underlying trade-off between the number of independent projections and the quality of said individual projections: with fixed = 64, increasing & provides more diverse cross-node information but at the cost of lower- dimensional kernel feature representations, The decline in performance at high & values suggests
21

---

that the degradation in kernel approximation quality eventually outweighs the benefits of additional projections.
SRF Dimension Analysis (Figure 4b). When varying the total sketch dimension D with fixed k we observe modest performance increase from k D 8 to k D 64, followed by diminishing returns at higher dimensions. However, the substantial variance across runs suggest these differences may be statistically significant. The performance decline k excessive sketch dimensionality may lead to overfitting on this moderately-sized dataset. Future work should investigate scaling properties more thoroughly on larger datasets where overfitting concerns are mitigated.
128 indicates that
empirical study of SRF hyperpa- rameters and the complexity analysis, we provide the following practical guidance for selecting SRF configurations. For kernel selection, recommend RBF embeddings εRBP when computational constraints prevent extensive kernel sweeps. The projection count typically exhibits an inverted-U effect on performance: accuracy improves up a point before declining; across evaluated datasets find k = 4 to be reasonable default. Finally, increasing the total sketch dimension k D improves performance with linear memory/runtime cost but shows diminishing returns; we suggest A D 64 as practical starting point, with adjustments based on dataset size and available compute.
Practical Guidance Hyperparameter Tuning. Based
22

---

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

---

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

---

Answer: [Yes]
Justification: All experiments were conducted on existing and publicly available datasets, with detailed descriptions in Appendix C. A link to open source code is also available in the main manuscript.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/ public/guides/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ /nniss. ccc/public/geee wttp//ggu/////eeeee hatp///ooeSSuiissseeeese massonnnllcy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why. At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended. but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Training and test details necessary to understand the results are provided in Appendix C.
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.
7. 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: Relevant experiments report error bars, either in Section or Appendix
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, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors)
should be clear whether the error bar the standard deviation or the standard error of the mean.
25

---

is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Information about computer resources used for experiments are in Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: http//eerss...// cc
Answer: [Yes]
Justification:
Our work conforms to the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure preserve anonymity (e.g., if there is special considera- tion due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification:
Our work contributes to foundational research in machine learning and is not tied to particular applications. Thus, we follow the guidelines below and do not explicitly discuss societal impacts.
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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point
26

---

out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, not needed point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used 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 negative societal impacts, the authors could also discuss possible mitigation strategies (e.g,, gated release of models, providing defenses in addition to attacks, mecha- nisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our work does release new datasets sensitive models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse 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 access the model 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 challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Creators of assets, including code, data, and models, are credited via citation in the manuscript and licenses and terms are discussed for appropriate assets (e.g. datasets) in Appendix C.
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 dataset.
The authors should state which version the asset is used and, if possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should included for each asset.
For scraped data from particular source (e.g., website), the copyright and terms of service that source should be provided.
If assets 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 dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged reach out the asset's 's creators.
13. New assets
27

---

Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: All pertinent details of the models and code described in Section Appendices A, and C, and the instructions in our open source code repository.
Guidelines:
The answer NA means that the paper does not release new assets. Researchers should communicate the details of the dataset/code/moddl as part of their sub- missions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then much detail as possible should be included in the main paper.
According the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsoureing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
28

---

Justification:
Our work does not involve LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve
LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: (https://neun //trrr//////ss..///// cc/Conferencess /205/ ( for what should or should not be described.
29


Reviews:
[{"review_id": "ozQQgkOJIo", "reviewer": "Reviewer_xCTo", "summary": "This paper studies graph learning with GNNs, and proposed a simple feature augmentation method to improve the long-range dependency learning of GNNs. The main idea is to create a new \"sketch\" for each node by taking all the node features in the graph and mixing them together using a designed but randomized projection. This sketch gives every node a unique, global signature that helps the GNN see long-range patterns and keep node embeddings from becoming too similar. The authors show that this simple and efficient trick works well on its own and can even be stacked with other methods to make GNNs more powerful.", "questions": "1. I would appreciate some discussion from the authors on how the proposed method would work on inductive systems where new nodes/edges show up frequently.", "limitations": "n/a", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "s1. This paper is overall clearly written.\n\ns2. The proposed method, although complicate in design and analysis, is very easy to implement. The proposed method is also task agnostic.\n\ns3. This paper is backed with good thoretical grounding. The authors provide formal propositions to explain why SRF works, showcasing that these sketches are unique, distance-sensitive, and contain cross-node information.\n\nw1. The evaluation is a bit lightweight. This work can benefit from some more comprehensive experiments.\n\nw2. The efficiency comparison in Fig 2 can also be extended to include more methods, which would make the comparison more convincing.", "was_revised": true, "final_justification": "i appreciate the authors' rebuttal, and will keep my positive score", "rebuttal": "Thanks for your thoughtful review of our work and for highlighting the clear presentation, theoretical grounding, and practicality of our work. We address your concerns and questions individually below. \n\n> W1. The evaluation is a bit lightweight. This work can benefit from some more comprehensive experiments.\n\nOur evaluation spans 6 real-world and 3 synthetic datasets across diverse domains (e.g. social networks, molecules), tasks (e.g. classification, regression), out-of-distribution generalization (DrugOOD dataset), and GNN backbone architectures (GIN, GINE, GCN, GAT, GATv2). Additionally, our evaluation is designed to target the core GNN limitations SRF addresses: oversquashing, oversmoothing, and expressiveness. Oversquashing is evaluated both synthetically (Tree-NeighborsMatch) and on a real-world dataset (Peptides-struct from the Long Range Graph Benchmark, which specifically tests long-range dependency modeling [1]). Oversmoothing and expressiveness are assessed through targeted synthetic benchmarks designed to isolate these phenomena. We welcome specific suggestions for additional evaluation areas if you have particular concerns.\n\n> W2. The efficiency comparison in Fig 2 can also be extended to include more methods, which would make the comparison more convincing.\n\nFigure 2 complements our theoretical complexity analysis (Appendix A.2, Table 4), which shows most baseline methods have unfavorable scaling with respect to graph size. We focus on PEARL since it has the most favorable theoretical complexity among baselines. In response to your feedback, we have clarified this in the manuscript (line 317): \"on evaluated datasets, they have about 3 times faster runtime and use about two orders of magnitude less memory than PEARL, which is the baseline encoding with better asymptotic complexity (Appendix A.2).\"\n\n> Q1. I would appreciate some discussion from the authors on how the proposed method would work on inductive systems where new nodes/edges show up frequently.\t\n\nOur sketch operator $S_{AG}$ uses an $N \\times N$ projection matrix where $N$ is the number of nodes. For systems where new nodes appear, one approach is to set $N_{max}$ as an upper bound on graph size. When processing graphs with $N < N_{max}$, the remaining $N_{max} - N$ positions correspond to zero-padded placeholder nodes. As new nodes appear, they can be assigned to these placeholder positions without changing the sketch matrix.\n\n[1] Dwivedi, Vijay Prakash, et al. \"Long range graph benchmark.\" Advances in Neural Information Processing Systems 35 (2022): 22326-22340."}, {"review_id": "eofN14R7Cy", "reviewer": "Reviewer_hHzn", "summary": "The paper proposes Sketched Random Features (SRF), a method for augmenting message-passing Graph Neural Networks (GNNs) with global, randomized embeddings derived from node features. Combining kernel random features and Johnson–Lindenstrauss sketching, these embeddings are injected into each GNN layer to mitigate oversquashing, oversmoothing, and limited expressiveness. The paper provides theoretical justifications for the approach, and experiments on both synthetic and real-world benchmarks demonstrate improved performance and efficiency over standard GNNs and other positional encoding strategies.", "questions": "1. How does SRF  advance beyond prior random feature–based or positional encoding methods for GNNs?\n\n2.1 Have the authors evaluated SRF with diverse GNN architectures (e.g., GraphSAGE, GAT, GCNII) to support its claimed architecture-agnostic applicability?\n\n2.2 Have the authors evaluated on more popular datasets (e.g., from Open Graph Benchmark) and other baselines addressing oversmoothing and oversquashing?\n\n2.3 How does SRF’s performance vary with respect to key hyperparameters such as sketch dimension, kernel type, or the number of random projections?\n\n2.4. Can you provide practical guidance on selecting hyperparameters (e.g., sketch dimension) to balance model accuracy, distance preservation, and computational cost?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n- Clearly motivated solution to major GNN limitations\n- Solid theoretical analysis of key properties\n- Empirically effective on diverse benchmarks\n- Efficient in runtime and memory\n- Modular and conceptually elegant design\n\n## Weaknesses\n\n- *Novelty*: The core contribution combines well-understood ideas -- random feature maps and sketching -- rather than introducing fundamentally new algorithms or theoretical insights. While the combination works, the paper should clarify how SRF advances beyond prior random feature–based or positional encoding methods for GNNs.\n\n- *Experiments*\n  - *Limited architectural diversity in evaluation*: The experiments focus predominantly on GIN/GINE architectures. Although the method is described as architecture-agnostic, the paper does not assess integration or performance with other state-of-the-art models (e.g., GraphSAGE, GAT, GCNII). A broader empirical evaluation could validate SRF’s general applicability.\n\n  - *Dataset/baseline choices*: There have been many papers that address the issues of oversquashing, oversmoothing, and expressivity. It would be better if the authors choose more datasets that are popular in the literature so that they can compare against a more diverse set of methods (e.g., see datasets and methods in the Open Graph Benchmark).\n\n  - *Ablation and sensitivity analysis*: The manuscript briefly mentions variations such as kernel types, projection dimensions, and embedding strategies, but lacks thorough ablations examining how these choices impact empirical performance, stability, and runtime. For example, how sensitive are results to sketch dimension, kernel selection, or the number of random projections? Such analyses would offer practical guidance for applying SRF.\n\n  - *Limited discussion of practical trade-offs*: The paper does not systematically discuss how to choose practical hyperparameters (especially sketch dimension) to balance distance preservation, efficiency, and model accuracy. Insights on this front would strengthen the work’s utility and reproducibility.\n\n- *Presentation* (minor issue): The paper does not provide schematics or diagrams showing how SRF embeddings are computed or incorporated into GNN layers. A clear schematic would help readers understand the interplay between SRF embedding and message passing, especially for practitioners aiming to implement the method.", "was_revised": true, "final_justification": "I have increased my score based on the author's response. I still believe that the novelty is limited; however, the results are good. I believe the writing has to improve significantly to clarify how the proposed work differs from existing work and improves upon it.", "rebuttal": "Thanks for your review and for identifying the strong theoretical analysis, empirical effectiveness, and computational efficiency of our approach. We address your specific concerns below.\n\n> W1: Novelty: The core contribution combines well-understood ideas -- random feature maps and sketching -- rather than introducing fundamentally new algorithms or theoretical insights.  While the combination works, the paper should clarify how SRF advances beyond prior random feature–based or positional encoding methods for GNNs.\n\n> Q1: How does SRF advance beyond prior random feature–based or positional encoding methods for GNNs?\n\nSRF's novelty lies in being the first to use sketching for mixing global feature information in graphs rather than dimensionality reduction. Specifically, the use of this novel sketching application with random kernel features uniquely allows our approach to mix all node information at each layer, regardless of geodesic distance. Unlike prior methods, this combination yields signals that are provably (1) almost surely unique, (2) distance-sensitive in the feature space with high probability, and (3) permutation-equivariant in expectation (Propositions 3.1–3.5). These properties are not simultaneously provided by prior random-feature or positional encoding methods (summarized in the table below). As shown in our manuscript, these properties mitigate or overcome well-known shortcomings of message-passing GNNs (expressiveness, oversquashing, oversmoothing). Furthermore, to the best of our knowledge, our work is the first to leverage node features (rather than random or structure-based methods) to create encodings that mitigate these aforementioned shortcomings of GNNs.\n\n**We discuss how SRF advances beyond prior encoding methods throughout the manuscript.** For example, the introduction (lines 47-57) overviews how our feature-based approach overcomes the limitations of prior methods. The specific weaknesses of existing random/positional encoding methods are discussed in lines 141-151. Section 3.3 (lines 251-270) discusses in detail how specific analytic properties of our proposed approach are able to overcome the aforementioned issues. In response to your feedback, we further provide the following table summarizing the differences between the methods. \n\n| Method | Unique Representation? | Distance Sensitive? | Equivariant? | Mitigates Oversquashing? | Alleviates oversmoothing? |\n|--------|------------------------|-------------------|--------------|-------------------------|--------------------------|\n| Random Node Features | Almost surely | No | In expectation | No | No |\n| Spectral Encodings | No | Yes | Yes | No | No |\n| PEARL | Unclear | With high probability | Yes | No | No |\n| SRF (Ours) | Almost surely | With high probability | In expectation | Yes | Yes |\n\n> W2.1: Limited architectural diversity in evaluation: The experiments focus predominantly on GIN/GINE architectures. Although the method is described as architecture-agnostic, the paper does not assess integration or performance with other state-of-the-art models (e.g., GraphSAGE, GAT, GCNII). A broader empirical evaluation could validate SRF’s general applicability.\n> Q2.1: Have the authors evaluated SRF with diverse GNN architectures (e.g., GraphSAGE, GAT, GCNII) to support its claimed architecture-agnostic applicability?\n\nAs described in our experimental overview (lines 278-288), while we present results for GIN/GINE in the main manuscript, we evaluate SRF with other GNN architectures in the Appendix (found in our supplementary material). **Appendix D presents results on the GCN, GAT, and GATv2 architectures across two datasets (Table 5), demonstrating consistent improvements over baselines and confirming SRF's architecture-agnostic benefits.**\n\n> W2.2: Dataset/baseline choices: There have been many papers that address the issues of oversquashing, oversmoothing, and expressivity. It would be better if the authors choose more datasets that are popular in the literature so that they can compare against a more diverse set of methods (e.g., see datasets and methods in the Open Graph Benchmark).\n> Q 2.2: Have the authors evaluated on more popular datasets (e.g., from Open Graph Benchmark) and other baselines addressing oversmoothing and oversquashing?\n\nOur evaluation comprises of 6 real-world and 3 synthetic datasets, targeting the core GNN limitations SRF addresses. We evaluate comprehensive baselines spanning multiple classes of positional encodings: random features, spectral embeddings, canonized variants, and PEARL (recent state-of-the-art). Our datasets cover diverse domains (e.g. social networks, molecules), tasks (e.g. classification, regression), out-of-distribution generalization (DrugOOD dataset), and GNN backbone architectures (GIN, GINE, GCN, GAT, GATv2). Importantly, our evaluation includes datasets specifically designed for the phenomena our method addresses: oversquashing is evaluated both synthetically (Tree-NeighborsMatch) and on a real-world dataset (peptides-struct from the Long Range Graph Benchmark), while oversmoothing and expressiveness are assessed through targeted synthetic benchmarks. *Additionally, the datasets used are standard in the literature, allowing easier comparison with several baselines (e.g. see recent baselines e.g. [1, 2, 3, 4] that evaluate on overlapping subsets of these same datasets).* We welcome specific suggestions for additional evaluation areas if you have particular concerns.\n\n> W2.3: Ablation and sensitivity analysis: The manuscript briefly mentions variations such as kernel types, projection dimensions, and embedding strategies, but lacks thorough ablations examining how these choices impact empirical performance, stability, and runtime. For example, how sensitive are results to sketch dimension, kernel selection, or the number of random projections? Such analyses would offer practical guidance for applying SRF.\n> Q 2.3: How does SRF’s performance vary with respect to key hyperparameters such as sketch dimension, kernel type, or the number of random projections?\n\n**We provide comprehensive empirical analyses of the noted hyperparameters throughout the manuscript and appendices.** We evaluate on 4 kernel types (3 normal + ablation kernel) in Section 4 (e.g. Figures 1a-1b, Tables 1-2). As noted in our experimental overview (lines 286-288), we evaluate the effect of varying embedding dimension $k\\cdot D$ and projection count $k$ in Appendix F. We summarize some of these results/key takeaways again for reference:\n- For many real-world graphs, the RBF embedding $\\mathcal{E}_{RBF}$ has the best empirical performance among kernel types, though this result is not always statistically significant. (See Table 2)\n- Projection count: For Reddit datasets, performance peaks at $k=4$, then declines due to the trade-off between projection diversity and individual projection quality (Appendix, Figure 3a).\n- Sketch dimension: Modest improvements from $k \\cdot D=8$ to $k \\cdot D=64$, with diminishing returns thereafter (Appendix, Figure 3b).\n\n> W2.4: Limited discussion of practical trade-offs: The paper does not systematically discuss how to choose practical hyperparameters (especially sketch dimension) to balance distance preservation, efficiency, and model accuracy. Insights on this front would strengthen the work’s utility and reproducibility.\n> Q 2.4: Can you provide practical guidance on selecting hyperparameters (e.g., sketch dimension) to balance model accuracy, distance preservation, and computational cost?\n\nBased on our empirical study of SRF hyperparameters (Appendix F) and complexity analysis (lines 271-276, Appendix A), we provide the following practical guidance (to be added to Appendix E):\n- Kernel selection: Use RBF embedding $\\mathcal{E}_{RBF}$ when computational constraints prevent extensive kernel comparison.\n- Projection count: Performance typically follows an inverted-U pattern, peaking then declining with increasing $k$. We find $k=4$ provides a robust default across our evaluated datasets.\n- Sketch dimension: Increasing $k \\cdot D$ improves performance with linear memory/runtime costs, but exhibits diminishing returns. We recommend $k \\cdot D=64$ as a practical starting point, with adjustment based on dataset size and computational budget.\n\n> W3: Presentation (minor issue): The paper does not provide schematics or diagrams showing how SRF embeddings are computed or incorporated into GNN layers. A clear schematic would help readers understand the interplay between SRF embedding and message passing, especially for practitioners aiming to implement the method.\n\nWe agree that a schematic would improve clarity and have prepared a diagram illustrating SRF computation and injection into GNN layers (visualizing Algorithm 1). Due to rebuttal constraints preventing figure uploads, we will include this in a possible camera-ready version.\n\n[1] Kanatsoulis, Charilaos, et al. \"Learning Efficient Positional Encodings with Graph Neural Networks.\" The Thirteenth International Conference on Learning Representations.\n\n[2] He, Xiaoxin, et al. \"A generalization of vit/mlp-mixer to graphs.\" International conference on machine learning. PMLR, 2023.\n\n[3] Huang, Yinan, et al. \"On the Stability of Expressive Positional Encodings for Graphs.\" The Twelfth International Conference on Learning Representations.\n\n[4] Finkelshtein, Ben, et al. \"Cooperative Graph Neural Networks.\" International Conference on Machine Learning. PMLR, 2024."}, {"review_id": "xTfnb7y7AL", "reviewer": "Reviewer_i8dd", "summary": "The authors propose a node augmentation method that individualizes node features while further enriching them with global information. This is accomplished by concatenating the original node features with randomized projections of kernel embeddings of the node features. These so-called 'Sketched Random Features' are computed by first approximating kernel embeddings on the node features, which are then transformed via a random projection matrix. Leveraging results from the Johnson–Lindenstrauss lemma, the authors derive theoretical guarantees that their method mitigates common GNN issues such as oversquashing and oversmoothing. In an experimental evaluation, the authors support their claims on oversquashing and oversmoothing and demonstrate that the individualized node features enable more expressive GNN models. Furthermore, the approach is validated on standard graph classification benchmarks.", "questions": "- How are graphs of varying sizes handled? If I understand correctly, both the embedding and sketch operators assume a fixed graph size N. \n- Individualisation of nodes generally comes at the cost of worse generalisation of the model. Do you have an intuition on how your method affects sample complexity?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n- The article is well written and structured.\n- The technical quality of the paper is excellent. \n- Although conceptually simple, the approach is elegant in how it simultaneously addresses two key aspects: global node information propagation and node individualization. \n- The theoretical results are presented clearly and appropriately support the paper’s claims.\n- The benchmarks on oversmoothing and oversquashing are convincing. \n\nWeaknesses:\n- While the title mentions long-range dependencies, this aspect is not much explored in depth within the paper. Maybe the authors can evaluate their method on standard long-range benchmark datasets.  \n- Minor notes:\n\t- Algorithm 1 is placed in Section 1 but not discussed until Section 3 (page 6). Thus, some of the notations have not been introduced yet such as \\Epsilon or \\mathcal{S}_AG.", "was_revised": true, "final_justification": "The reviewers have addressed all my concerns and questions. I maintain my positive score.", "rebuttal": "Thank you for your positive review and for recognizing the overall technical quality, approach to addressing global information propagation/node individualization, theoretical results, and comprehensive empirical evaluation of our work. We address your concerns and questions individually below.\n\n> W1: While the title mentions long-range dependencies, this aspect is not much explored in depth within the paper. Maybe the authors can evaluate their method on standard long-range benchmark datasets. \n\n We evaluate the ability of Sketched Random Features to account for long-range dependencies in both synthetic and real-world scenarios. The synthetic Tree-NeighborsMatch dataset is specifically designed to measure oversquashing and the compression of long-range dependencies [1], where our results demonstrate strong performance (Figure 1a-b). Additionally, we evaluate on the peptides-struct dataset from the Long Range Graph Benchmark [2], which is designed to require reasoning about long-range dependencies in order to excel (lines 347-349, Table 3). Our performance on this real-world long-range benchmark further validates SRF's effectiveness on long-range dependency tasks. In response to your feedback, we have clarified the motivation for these dataset choices and their relevance to long-range dependency evaluation in the manuscript.\n\n> W2: Algorithm 1 is placed in Section 1 but not discussed until Section 3 (page 6). Thus, some of the notations have not been introduced yet such as \\Epsilon or \\mathcal{S}_AG.\n\nThanks for pointing this out. We have added additional detail to the text so as to properly introduce notation that appears in Algorithm 1.\n\n> Q1: How are graphs of varying sizes handled? If I understand correctly, both the embedding and sketch operators assume a fixed graph size N. \n\nOur method naturally handles graphs of varying sizes (indeed, all our evaluated datasets contain graphs of different sizes). To see why, we note that the embedding operator $\\mathcal{E}$ and sketch operator $\\mathcal{S}$ take as input a matrix with $N$ rows, where $N$ is the number of nodes in the specific graph being processed. We use structured random matrices (SRM) as described in lines 271-276, which can be instantiated for any graph size at runtime by instantiating an appropriately sized SRM and indexing only the number of rows required for a given graph. This is similar to standard practice in the SRM literature [3] or as used to sketch dynamic graphs for representation [4].\n\n> Q2: Individualisation of nodes generally comes at the cost of worse generalisation of the model. Do you have an intuition on how your method affects sample complexity?\n\nWe hypothesize that SRF has better sample complexity than naive random individualization. Unlike random features that create arbitrary coordinate spaces, SRF preserves meaningful geometric structure: our embeddings retain distance sensitivity in kernel space with high probability (Proposition 3.2), providing principled similarity measures between nodes. This distance preservation should facilitate generalization by maintaining inductive biases from the feature space. Empirically, our method performs well even on our smallest dataset (REDDIT-B with 2,000 graphs), suggesting reasonable sample efficiency. Future work should investigate formal sample complexity analysis.\n\n[1] Alon, Uri, and Eran Yahav. \"On the Bottleneck of Graph Neural Networks and its Practical Implications.\" International Conference on Learning Representations.\n\n[2] Dwivedi, Vijay Prakash, et al. \"Long range graph benchmark.\" Advances in Neural Information Processing Systems 35 (2022): 22326-22340.\n\n[3] Choromanski, Krzysztof M., Mark Rowland, and Adrian Weller. \"The unreasonable effectiveness of structured random orthogonal embeddings.\" Advances in neural information processing systems 30 (2017).\n\n[4] Hosseini, Ryien, et al. \"Quality Measures for Dynamic Graph Generative Models.\" The Thirteenth International Conference on Learning Representations."}, {"review_id": "uTUUhS2Tft", "reviewer": "Reviewer_5P6B", "summary": "GNNs often face challenges such as oversquashing, oversmoothing, and limited expressiveness, particularly when modeling long-range dependencies. This paper introduces Sketched Random Features (SRF), randomized global summaries of node features designed to address these issues. SRF is created by first projecting node features into a kernel space using random mappings such as random Fourier features, and then aggregating them across nodes via the Johnson–Lindenstrauss transform. The resulting sketches are unique, distance-sensitive, and independent of graph topology. By injecting these representations into each GNN layer, the model gains efficient access to global context without relying on costly attention mechanisms. This approach consistently improves performance on both synthetic and real-world graph benchmarks, while offering significant gains in memory and runtime efficiency over transformer-based methods.", "questions": "I would request the authors to address the points raised in the weakness section.", "limitations": "The societal or ethical implications of the work are not deeply discussed. For instance, while the method is efficient and scalable, are there settings such privacy-sensitive or fairness-constrained healthcare applications where injecting global summaries might amplify biases?", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The paper is clearly written and easy to follow. It presents the core limitations of GNNs in a well-motivated and accessible manner. The proposed method is grounded in well-established theoretical foundations and makes effective use of them. Empirical results demonstrate that incorporating SRF improves both performance and efficiency compared to strong baselines.  \n\nDespite these positive points, I have the some reservations: \n\n - SRF is positioned as a topology-agnostic method. It is entirely based on node features and random projections, which may reduce effectiveness in tasks where structural cues are critical. While this is acknowledged as complementary to structural encodings, the standalone method may underperform in structurally complex graphs with weak features.\n\n - SRF relies on random kernel mappings and projections. This may lead to variability in performance across different runs, especially in low-data or low-variance settings. The paper does not deeply investigate the robustness of SRF across seeds or noise levels.\n\n - There is no detailed ablation on sketching parameters such as embedding dim and kernel choice.\n\n - While the method is well motivated and grounded in established theoretical tools such as random kernel features and the JL transform, it does not introduce any novel theoretical results. The analysis largely restates known properties and lacks deeper contributions, such as convergence guarantees, generalisation bounds, or new theoretical insights into the behaviour of GNNs.", "was_revised": true, "final_justification": "The authors have addressed my concerns, and I have raised my score accordingly. However, I still believe that the theoretical analysis, while well-grounded, could have been more novel. For this reason, I have leaned toward a borderline accept.", "rebuttal": "Thanks for your thoughtful review and for highlighting the clear presentation, strong theoretical grounding, and empirical results of our work. We address your concerns individually below.\n\n> W1: SRF is positioned as a topology-agnostic method. It is entirely based on node features and random projections, which may reduce effectiveness in tasks where structural cues are critical. While this is acknowledged as complementary to structural encodings, the standalone method may underperform in structurally complex graphs with weak features.\n\nOur method is designed for the common setting where graphs contain informative node features, enabling alternatives to computationally expensive structural encodings. As acknowledged in our limitations (Appendix E.4, lines 750-752), performance gains may be limited when node features are sparse or noisy. However, as you note, SRF can complement structural encodings when needed, and in the worst case (featureless graphs), it reduces to random node individualization—an effective method in itself [1]. This can be seen by applying Algorithm 1 to graphs where all nodes have identical unit features.\n\n> W2: SRF relies on random kernel mappings and projections. This may lead to variability in performance across different runs, especially in low-data or low-variance settings. The paper does not deeply investigate the robustness of SRF across seeds or noise levels.\n\nWe appreciate this important concern. Our experiments vary random seeds and report error bars across multiple runs, demonstrating statistically significant improvements that are often more stable than PEARL (a neural network-based positional encoding baseline). Regarding low-data regime, our empirical evaluation spans diverse scales, from small datasets like REDDIT-B (2,000 graphs) to larger-scale benchmarks, with consistent improvements across this range, suggesting robustness to dataset size variations. \n\nCould you please clarify what you mean by \"low-variance settings\"? We want to ensure we address your specific concern accurately.\n\n> W3: There is no detailed ablation on sketching parameters such as embedding dim and kernel choice.\n\nWe do empirically analyze embedding dimension and kernel choice: We evaluate 4 kernel types across all experiments (Figures 1a-b, Tables 1-2) and examine embedding dimension/projection count effects in Appendix F. Please see our response to Reviewer hHzn W2.3/Q2.3 for a detailed summary of these results.\n\n> W4: While the method is well motivated and grounded in established theoretical tools such as random kernel features and the JL transform, it does not introduce any novel theoretical results. The analysis largely restates known properties and lacks deeper contributions, such as convergence guarantees, generalisation bounds, or new theoretical insights into the behaviour of GNNs.\n\nWe respectfully disagree that our work lacks novel theoretical contributions. We provide five new propositions (Section 3.3) establishing fundamental properties specific to our sketching approach for GNNs. Additionally, we provide the first theoretical analysis connecting how sketched embeddings specifically mitigate oversquashing (through topology-agnostic information flow) and oversmoothing (through distance-sensitive uniqueness preservation). Our theoretical contributions focus on justifying SRF's effectiveness rather than general GNN behavior, which we consider appropriate for the scope of the manuscript. Please see our response to Reviewer hHzn W1/Q1 for additional discussion on the novelty of our approach more generally.\n\n> L1: The societal or ethical implications of the work are not deeply discussed. For instance, while the method is efficient and scalable, are there settings such privacy-sensitive or fairness-constrained healthcare applications where injecting global summaries might amplify biases?\n\nWe do not believe our work introduces ethical implications beyond those inherent to improving ML algorithms generally. However, you raise an interesting point about privacy-sensitive applications. While privacy analysis is beyond our current scope, the sketching process does aggregate node information globally, which could potentially leak private information in sensitive domains. At the same time, sketching techniques are also foundational to many differential privacy mechanisms [2]. We believe such analysis is an interesting direction for future work.\n\n[1] Abboud, Ralph, et al. \"The surprising power of graph neural networks with random node initialization.\" arXiv preprint arXiv:2010.01179 (2020).\n\n[2] Blocki, Jeremiah, et al. \"The johnson-lindenstrauss transform itself preserves differential privacy.\" 2012 IEEE 53rd annual symposium on foundations of computer science. IEEE, 2012."}]

Author rebuttal:

Meta-review: This paper proposes Sketched Random Features (SRF): randomized global embeddings of node features that are injected at each GNN layer to mitigate oversquashing, oversmoothing, and limited expressivity. Reviewers engaged seriously and are broadly positive: two accepts and two borderline-accepts after rebuttal. They highlighted clear writing, modularity, solid theory, and consistent empirical gains, in particular on long-range benchmarks.

Concerns centered on perceived incremental novelty and comprehensiveness of evaluation breadth (diversity, ablations, baselines). The rebuttal substantially improved the case. The authors clarified the novelty—using sketching to mix global feature information rather than for dimensionality reduction, added a contrast table situating SRF among positional/random-feature encodings, provided hyperparameter selection guidelines and additional ablations, included additional backbones, and discussed inductive deployment and efficiency.

In the light of these discussions, I find SRF to be a simple, task-agnostic “add-on” with solid theoretical support, consistent gains, and favorable complexity. I hope that the remaining points can indeed be addressed at the camera-ready stage as promised.
Decision: Accept (poster)