Large graphs are becoming ubiquitous, presenting significant computational hurdles in data processing and analysis. Graph Coarsening algorithms are frequently employed to condense large graphs while preserving key graph properties. Real-world graphs also have features or contexts associated with each node. However, existing coarsening methods often overlook simultaneity across node features and structural information. Recent approaches to alleviate this limitation are computationally intensive, and primarily suited for homophilic datasets. Most existing approaches are unsuitable for streaming and evolving graphs, as they require recomputation of the coarsened graph at every timestamp. In this paper, we introduce a Fast and Scalable Hashing-Based Universal Graph Coarsening (UGC) Framework, that integrates locality-sensitive hashing, and feature augmentation to effectively coarsen graphs. UGC is exceptionally fast, straightforward to implement, and capable of handling homophilic, heterophilic, and streaming graphs making it a truly universal solution for graph coarsening. We use an optimization-based framework to minimize a constrained $\epsilon$ε similarity between the original and coarsened graphs, where $\epsilon$ε is between zero and one. Through extensive experimentation on real and synthetic datasets, we demonstrate the effectiveness of our approach in terms of improved runtime complexity and generalization to heterophilic and streaming graphs. Furthermore, we showcase its utility in downstream tasks, emphasizing its scalability for training graph neural networks on coarsened graphs from benchmark real-world datasets.

In the era of big data, graphs have emerged as a natural representation of intricate relationships. However, graph sizes often become unwieldy, leading to storage, computation, and analysis challenges. A crucial demand arises for methods that can effectively downsize large graphs while retaining vital insights. Graph coarsening seeks to simplify large graphs while maintaining the basic statistics of the graphs, such as spectral properties and $\epsilon$-similarity in the coarsened graph. This ensures that downstream processes are more efficient and effective. Most published methods are suitable for homophilic datasets, limiting their universal use. We propose **U**niversal **G**raph **C**oarsening (UGC), a framework equally suitable for homophilic and heterophilic datasets. UGC integrates node attributes and adjacency information, leveraging the dataset's heterophily factor. Results on benchmark datasets demonstrate that UGC preserves spectral similarity while coarsening. In comparison to existing methods, UGC is 4x to 15x faster, has lower eigen-error, and yields superior performance on downstream processing tasks even at 70% coarsening ratios.