Sketch-Augmented Features Improve Learning Long-Range Dependencies in Graph Neural Networks
2025/11/05 by Ryien Hosseini, Hosseini, Ryien, Filippo Simini +7
Computer Science · #Advanced Graph Neural Networks #FOS: Computer and information sciences #Graph Theory and Algorithms #Machine Learning (cs.LG) #Machine Learning in Healthcare
paper · pdf · doi:10.48550/arxiv.2511.03824
openalex publication_date 2025/11/05 · openalex created_date 2025/11/08 · openalex updated_date 2026/07/28
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. Our source code is available at \hrefhttps://github.com/ryienh/sketched-random-featureshttps://github.com/ryienh/sketched-random-features.
Citations
- Learning Efficient Positional Encodings with Graph Neural Networks
- Homomorphism Counts as Structural Encodings for Graph Learning
- Graph Transformers: A Survey
- Homomorphism Counts for Graph Neural Networks: All About That Basis
- Laplacian Canonization: A Minimalist Approach to Sign and Basis Invariant Spectral Embedding
- On the Stability of Expressive Positional Encodings for Graphs
- Taming graph kernels with random features
- Homomorphism-Distinguishing Closedness for Graphs of Bounded Tree-Width
- A Survey on Oversmoothing in Graph Neural Networks
- On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology
- A Generalization of ViT/MLP-Mixer to Graphs
- Pure Transformers are Powerful Graph Learners
- Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries
- LRGB: Long Range Graph Benchmark
- Recipe for a General, Powerful, Scalable Graph Transformer
- Sign and Basis Invariant Networks for Spectral Graph Representation Learning
- Weisfeiler and Leman go Machine Learning: The Story so far
- Understanding over-squashing and bottlenecks on graphs via curvature
- Transformers Generalize DeepSets and Can be Extended to Graphs and Hypergraphs
- From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness
- Equivariant Subgraph Aggregation Networks
- Dirichlet Energy Constrained Learning for Deep Graph Neural Networks
- Reproducing Kernel Hilbert Space, Mercer's Theorem, Eigenfunctions, Nyström Method, and Use of Kernels in Machine Learning: Tutorial and Survey
- Rethinking Graph Transformers with Spectral Attention
- How Attentive are Graph Attention Networks?
- Mesh Graphormer
- The Surprising Power of Graph Neural Networks with Random Node\n Initialization
- Simple and Deep Graph Convolutional Networks
- Expressive Power of Invariant and Equivariant Graph Neural Networks
- A Note on Over-Smoothing for Graph Neural Networks
- On the Bottleneck of Graph Neural Networks and its Practical Implications
- Bayesian Graph Neural Networks with Adaptive Connection Sampling
- Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond
- Random Features Strengthen Graph Neural Networks
- Coloring graph neural networks for node disambiguation
- DropEdge: Towards Deep Graph Convolutional Networks on Node Classification
- Understanding the Representation Power of Graph Neural Networks in Learning Graph Topology
- Strategies for Pre-training Graph Neural Networks
- DeepGCNs: Can GCNs Go as Deep as CNNs?
- Relational Pooling for Graph Representations
- Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks
- How Powerful are Graph Neural Networks?
- Invariant and Equivariant Graph Networks
- Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning
- Graph Attention Networks
- Attention Is All You Need
- Inductive Representation Learning on Large Graphs
- Neural Message Passing for Quantum Chemistry
- The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings
- Semi-Supervised Classification with Graph Convolutional Networks
Related