Linear Complexity Framework for Feature-Aware Graph Coarsening via Hashing

Large-scale graphs are increasingly common in various applications, leading to significant computational challenges in data processing and analysis. To address this, coarsening algorithms are employed to reduce graph size while preserving key properties. However, existing methods for large-scale graphs are computationally intensive, undermining the coarsening goal. Additionally, real-world graphs often contain node-specific features or contexts, which current coarsening approaches overlook, focusing solely on structural information like adjacency matrices. This limitation may not suit downstream tasks reliant on node features. In this paper, we introduce a Feature-Aware graph Coarsening algorithm via Hashing, called FACH, inspired by locality sensitive hashing to coarsen the graph based on the node features. To our knowledge, this is the first-ever method that coarsens a graph with node features in linear time. FACH is over 7× faster than the quickest and around 150× faster than the existing techniques for datasets like Coauthor Physics which has 34,493 nodes. We also demonstrate the efficacy of the proposed framework in terms of superior run-time complexity. The coarsened graph obtained by our method also preserves the spectral properties of the original graph while achieving massive improvement in time-complexity of coarsening which is the primary goal of our study. We showcase the effectiveness of FACH for the downstream task by evaluating the performance on scalable training of graph neural networks using coarsened data on benchmark real-world datasets.