Introduction
Graph Neural Networks (GNNs) have become the standard for processing non-Euclidean data, yet they face significant challenges in scalability and generalization. As graphs scale to millions of nodes, the computational cost of neighborhood aggregation becomes prohibitive. Furthermore, real-world graphs often contain noise that can lead to overfitting, and the "over-squashing" phenomenon—where information from an exponentially growing neighborhood is compressed into a fixed-size vector—can degrade performance.
While edge pruning is a common strategy to mitigate these issues, standard random pruning often destroys critical structural information. This paper introduces Locality Sensitive Pruning (LSP), a novel approach that leverages Locality-Sensitive Hashing (LSH) to sparsify graphs while preserving essential topological patterns.
Methodology
The fundamental insight of LSP is that pruning should be consistent across similar local structures. If two nodes have nearly identical neighborhoods, a GNN should ideally see similar pruned versions of those neighborhoods to maintain their "distinguishability" or "similarity" in the latent space.
Structural Hashing and Categorization
The first step in LSP is to categorize nodes based on their local neighborhoods. By mapping edge and node features into discrete "buckets" using LSH, LSP identifies nodes that exist in similar structural contexts. For instance, nodes might be classified based on the presence of specific neighbor types.
Consistent Pruning via MinHash
Once nodes are bucketed, a global hashing rule (such as MinHash) is used to select which edges to retain. Because the hash functions are global, two nodes in the same bucket will likely have the same types of edges preserved. This consistency is vital: if two similar nodes are pruned differently, they may appear dissimilar to the GNN, leading to a loss of representational power. Conversely, random pruning treats every edge independently, which often makes similar environments look different and dissimilar ones look the same.
LSP is implemented as a preprocessing step, meaning that training and inference proceed on a sparsified adjacency matrix, leading to direct computational speedups. The authors explore two variants: LSP-T (using binary signatures) and LSP-P (using random projections).
Key Insights and Results
The effectiveness of LSP was evaluated across diverse tasks, including node classification (Cora, PPI, GitHub) and graph regression (QM9, ZINC).
- Consistency is King: In "topology-heavy" tasks like protein-protein interaction (PPI) or molecular modeling, preserving the relative similarity of local environments is crucial. LSP maintained high accuracy even at high pruning rates where random pruning failed.
- Mitigating Over-squashing: By reducing node degrees, LSP limits the growth of the receptive field. This reduces the amount of information that must be aggregated into a single node vector, effectively combating over-squashing.
- Performance and Speedup: The authors observed a linear relationship between edge reduction and computational speedup. In a complex synthetic task, pruning ~45% of edges resulted in significant acceleration while maintaining 76% accuracy, compared to a massive performance drop for random pruning.
- Regression Accuracy: In molecular tasks (QM9 and ZINC), LSP variants consistently achieved lower Mean Absolute Error (MAE) than random pruning across various sparsification levels.
Limitations and Future Work
LSP's benefits are most pronounced in graphs where topology is a primary driver of the task. In datasets where node features dominate (e.g., PubMed), the advantage over random pruning is less significant. Future research could focus on developing specialized LSH functions tailored to specific domain-knowledge, such as chemical motifs in molecular graphs, to further refine the pruning process.
Summary updated