Sketch-Augmented Features Improve Learning Long-Range Dependencies in Graph Neural Networks

Ryien Hosseini (University of Chicago) · Filippo Simini (Argonne National Laboratory) · Venkatram Vishwanath (Argonne National Laboratory) · Rebecca Willett (U Chicago) · Henry Hoffmann (University of Chicago)

baseline gnnsdistance-sensitiveexpressive powerglobal embeddingsgraph learning tasksgraph neural networksgraph positional encodingsgraph sparsityinductive biaslocal message passinglong-range informationnode representations oversmoothingoversquashingsketched random featurestopology-agnostic

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