AH-UGC: Adaptive and Heterogeneous Universal Graph Coarsening

Large-scale graphs are increasingly common in real-world applications, yet their computational and memory requirements can make graph learning difficult, particularly in resource-constrained settings. Graph coarsening alleviates this cost by replacing the original graph with a smaller surrogate; however, existing methods are typically fixed-resolution, requiring recomputation for different coarsening ratios, and are primarily designed for homogeneous graphs. We introduce \textbf{AH-UGC}, an adaptive and heterogeneous graph coarsening framework that combines Locality-Sensitive Hashing (LSH) with Consistent Hashing (CH). AH-UGC performs the expensive projection step only once and subsequently generates multiple graph resolutions through lightweight hash-based merging. For heterogeneous graphs, we introduce type-isolated coarsening, which restricts merges to nodes of the same type while preserving cross-type connectivity. Experiments across homophilic, heterophilic, heterogeneous, and large-scale graphs show that AH-UGC substantially improves adaptive coarsening efficiency while maintaining competitive structural fidelity and downstream predictive performance. AH-UGC provides a simple, model-agnostic, and resource-efficient approach to scalable graph learning.