LSP : Acceleration and Regularization of Graph Neural Networks via Locality Sensitive Pruning of Graphs

Graph Neural Networks (GNNs) have emerged as highly successful tools for\ngraph-related tasks. However, real-world problems involve very large graphs,\nand the compute resources needed to fit GNNs to those problems grow rapidly.\nMoreover, the noisy nature and size of real-world graphs cause GNNs to over-fit\nif not regularized properly. Surprisingly, recent works show that large graphs\noften involve many redundant components that can be removed without\ncompromising the performance too much. This includes node or edge removals\nduring inference through GNNs layers or as a pre-processing step that\nsparsifies the input graph. This intriguing phenomenon enables the development\nof state-of-the-art GNNs that are both efficient and accurate. In this paper,\nwe take a further step towards demystifying this phenomenon and propose a\nsystematic method called Locality-Sensitive Pruning (LSP) for graph pruning\nbased on Locality-Sensitive Hashing. We aim to sparsify a graph so that similar\nlocal environments of the original graph result in similar environments in the\nresulting sparsified graph, which is an essential feature for graph-related\ntasks. To justify the application of pruning based on local graph properties,\nwe exemplify the advantage of applying pruning based on locality properties\nover other pruning strategies in various scenarios. Extensive experiments on\nsynthetic and real-world datasets demonstrate the superiority of LSP, which\nremoves a significant amount of edges from large graphs without compromising\nthe performance, accompanied by a considerable acceleration.\n