AH-UGC: Adaptive and Heterogeneous-Universal Graph Coarsening

2025/05/18 by M. C. Kataria, Shreyash Bhilwade, Kataria, Mohit +4
Computer Science · Social Sciences · #Advanced Computing and Algorithms #Advanced Graph Neural Networks #FOS: Computer and information sciences #Graph Theory and Algorithms #Machine Learning (cs.LG) #Social and Information Networks (cs.SI)

paper · pdf · doi:10.48550/arxiv.2505.15842

openalex publication_date 2025/05/18 · openalex created_date 2025/10/19 · openalex updated_date 2026/07/28

Abstract

Graph Coarsening (GC) is a prominent graph reduction technique that compresses large graphs to enable efficient learning and inference. However, existing GC methods generate only one coarsened graph per run and must recompute from scratch for each new coarsening ratio, resulting in unnecessary overhead. Moreover, most prior approaches are tailored to homogeneous graphs and fail to accommodate the semantic constraints of heterogeneous graphs, which comprise multiple node and edge types. To overcome these limitations, we introduce a novel framework that combines Locality Sensitive Hashing (LSH) with Consistent Hashing to enable adaptive graph coarsening. Leveraging hashing techniques, our method is inherently fast and scalable. For heterogeneous graphs, we propose a type isolated coarsening strategy that ensures semantic consistency by restricting merges to nodes of the same type. Our approach is the first unified framework to support both adaptive and heterogeneous coarsening. Extensive evaluations on 23 real-world datasets including homophilic, heterophilic, homogeneous, and heterogeneous graphs demonstrate that our method achieves superior scalability while preserving the structural and semantic integrity of the original graph.

Citations

• Structure-free Graph Condensation: From Large-scale Graphs to Condensed Graph-free Data
• A Unified Framework for Optimization-Based Graph Coarsening
• GBK-GNN: Gated Bi-Kernel Graph Neural Networks for Modeling Both Homophily and Heterophily
• Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods
• Graph Condensation for Graph Neural Networks
• Are we really making much progress? Revisiting, benchmarking, and refining heterogeneous graph neural networks
• Scaling Up Graph Neural Networks Via Graph Coarsening
• Simple and Deep Graph Convolutional Networks
• Adaptive Universal Generalized PageRank Graph Neural Network
• Geom-GCN: Geometric Graph Convolutional Networks
• Revisiting Consistent Hashing with Bounded Loads
• GraphSAINT: Graph Sampling Based Inductive Learning Method
• Reinforced Genetic Algorithm Learning for Optimizing Computation Graphs
• MixHop: Higher-Order Graph Convolutional Architectures via Sparsified\n Neighborhood Mixing
• Simplifying Graph Convolutional Networks
• Pitfalls of Graph Neural Network Evaluation
• How Powerful are Graph Neural Networks?
• Representation Learning on Graphs with Jumping Knowledge Networks
• Graph Attention Networks
• Inductive Representation Learning on Large Graphs
• Semi-Supervised Classification with Graph Convolutional Networks
• Revisiting Semi-Supervised Learning with Graph Embeddings
• Lean Algebraic Multigrid (LAMG): Fast Graph Laplacian Linear Solver\n (Journal Version)
• Kron Reduction of Graphs with Applications to Electrical Networks
• Relaxation-based coarsening and multiscale graph organization
• A Comprehensive Survey on Graph Neural Networks

Related

• GBGC: Efficient and Adaptive Graph Coarsening via Granular-ball Computing
• Graph Coarsening with Neural Networks
• Remedying Coarsening-Based GNN Training under Heterophily via Adaptive Complementary Enhancement
• Graph coarsening: From scientific computing to machine learning
• Adaptive Graph Coarsening for Efficient GNN Training