{"ID":2845945,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.03824","arxiv_id":"2511.03824","title":"Sketch-Augmented Features Improve Learning Long-Range Dependencies in Graph Neural Networks","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 \\textit{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 \\href{https://github.com/ryienh/sketched-random-features}{https://github.com/ryienh/sketched-random-features}.","short_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...","url_abs":"https://arxiv.org/abs/2511.03824","url_pdf":"https://arxiv.org/pdf/2511.03824v1","authors":"[\"Ryien Hosseini\",\"Filippo Simini\",\"Venkatram Vishwanath\",\"Rebecca Willett\",\"Henry Hoffmann\"]","published":"2025-11-05T19:41:56Z","proceeding":"cs.LG","tasks":"[\"cs.LG\"]","methods":"[\"Graph Neural Network\"]","has_code":false,"code_links":[{"ID":607399,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_id":2845945,"paper_url":"https://arxiv.org/abs/2511.03824","paper_title":"Sketch-Augmented Features Improve Learning Long-Range Dependencies in Graph Neural Networks","repo_url":"https://github.com/ryienh/sketched-random-features","is_official":false,"mentioned_in_paper":false,"mentioned_in_github":true,"github_stars":0}]}