Research map / Graph learning / GNN architectures
Sketch-Augmented Features Improve Learning Long-Range Dependencies in Graph Neural Networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Injects Sketched Random Features (JL-style random projections of kernel embeddings of all node features) into every layer of standard GNNs to address oversquashing, oversmoothing and limited expressiveness, at low cost.
Problem
Message-passing GNNs suffer from oversquashing of long-range information, oversmoothing of node representations, and limited expressive power (bounded by 1-WL), while existing fixes (graph transformers, positional encodings) are costly or hard to design.
Approach
Augment each node's features at every GNN layer with sketched random features: random kernel feature maps of node features followed by an additive Gaussian cross-node random projection (I + G/sqrt(N))Φ, which gives each node a unique, distance-sensitive, topology-agnostic embedding that mixes information globally without changing graph topology.
Key results
- SRF-enhanced GNNs achieve perfect accuracy (1.000) on CSL and EXP, while GIN baseline and ablation without sketching stay at chance (0.100 and about 0.52).
- On REDDIT-B and REDDIT-M, the E_RBF with S_AG^(8) variant reaches 94.13% and 60.53% accuracy, versus 91.8% and 56.9% for GINE without positional encoding.
- On Peptides-struct, B-PEARL+SRF reaches MAE 0.243 versus 0.248 for B-PEARL alone, and R-PEARL+SRF reaches 0.245 versus 0.247 for R-PEARL alone.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add AG sketching to Laplacian kernel features instead of using the identity sketch (ablation) | GIN/GINE with SRF · REDDIT-B | accuracy: 92.56 ± 0.58 -> 94.00 ± 0.35 | Helped |
| Add AG sketching to Laplacian kernel features instead of using the identity sketch (ablation) | GIN/GINE with SRF · REDDIT-M | accuracy: 58.32 ± 0.47 -> 60.33 ± 0.37 | Helped |
| Add AG sketching to Laplacian kernel features instead of using the identity sketch (ablation) | GINE with SRF · DrugOOD Scaffold | AUC: 65.34 ± 0.26 -> 69.43 ± 0.90 | Helped |
| Add AG sketching to Laplacian kernel features instead of using the identity sketch (ablation) | GINE with SRF · DrugOOD Size | AUC: 63.29 ± 0.63 -> 67.23 ± 0.54 | Helped |
| Add AG sketching to Laplacian kernel features instead of using the identity sketch (ablation) | GINE with SRF · DrugOOD Assay | AUC: 71.89 ± 0.37 -> 72.51 ± 0.69 | Mixed |
| Add SRF RBF features and AG sketching | GINE · DrugOOD Scaffold | AUC: 69.64 ± 0.49 -> 69.60 ± 0.48 | Hurt |
| Add SRF linear features and AG sketching | GAT · REDDIT-B | accuracy: 86.55 ± 1.89 -> 89.05 ± 1.17 | Helped |
| Add SRF RBF features and AG sketching | GAT · REDDIT-B | accuracy: 86.55 ± 1.89 -> 86.15 ± 1.43 | Hurt |
| Add SRF features and sketching | GIN · CSL | accuracy: 0.100 -> 1.000 | Helped |
| Replace AG sketching with the identity sketch (ablation) | GIN · EXP | accuracy: 0.518 -> 0.520 | No clear effect |
| Add SRF to B-PEARL | B-PEARL · Peptides-struct | MAE: 0.248 -> 0.243 | Helped |
| Add SRF to R-PEARL | R-PEARL · Peptides-struct | MAE: 0.247 -> 0.245 | Helped |
Surprising findings
- Pure feature-free random node individualization without sketching (the ablation with identity sketch) gives no gain on the expressiveness benchmarks, showing that the cross-node sketch rather than kernel features alone drives the improvement.
- Plain random feature injection baselines are outperformed by SRF variants on most architecture/dataset pairs, but one random-feature baseline slightly beats the RBF variant on REDDIT-B with GAT.
Limitations
- Effectiveness depends on informative node features; gains may be limited when features are sparse, noisy or absent.
- Properties hold only in expectation or with high probability, so results have run-to-run variance.
- Topology-agnostic, so it may miss structural signals captured by positional or spectral encodings.
Experimental setup
Datasets: Tree-NeighborsMatch Cora CSL EXP REDDIT-B REDDIT-M DrugOOD Peptides-struct
Benchmarks: Tree-NeighborsMatch Cora (Dirichlet energy) CSL EXP REDDIT-B REDDIT-M DrugOOD (Assay, Scaffold, Size) Peptides-struct
Metrics: accuracy AUC MAE Dirichlet energy runtime memory
Baselines: GINE (No PE) GINE + rand id SignNet SignNet-8S SignNet-8L BasisNet SPE SPE-8S R-PEARL B-PEARL GPS SAN+RWSE
Builds on: GIN GINE PEARL random Fourier features Johnson-Lindenstrauss lemma
Closest papers by meaning
- Sketch-GNN: Scalable Graph Neural Networks with Sublinear Training Complexity (NeurIPS 2022 · similarity 0.92)
- Learning Long Range Dependencies on Graphs via Random Walks (ICLR 2025 · similarity 0.91)
- On Measuring Long-Range Interactions in Graph Neural Networks (ICML 2025 · similarity 0.88)
- Towards Bridging Generalization and Expressivity of Graph Neural Networks (ICLR 2025 · similarity 0.88)
- Towards characterizing the value of edge embeddings in Graph Neural Networks (ICML 2025 · similarity 0.87)
- A Manifold Perspective on the Statistical Generalization of Graph Neural Networks (ICML 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.