Remedying Coarsening-Based GNN Training under Heterophily via Adaptive Complementary Enhancement

Coarsening-based training for graph neural networks (GNNs), i.e. training on coarsened graphs rather than the original large ones, has become a promising direction for scaling GNNs to massive graphs. However, prior work has been evaluated almost exclusively on textithomophilic graphs, leaving the more challenging textitheterophilic settings underexplored. We show, both empirically and theoretically, that existing coarsening-based training methods suffer significant performance degradation on heterophilic graphs due to inevitable loss of graph information during coarsening. To address this, we propose bf Adaptive bf Complementary bf Enhancement, a plug-and-play, model-agnostic strategy that reintegrates the information discarded in coarsening: ACE learns a projector for re-constructing original node features and applies textitanisotropic structural regularization to embed local heterophily. We further adopt textithomoscedastic uncertainty weighting to adaptively balance the combined training objective of primary coarsened-graph training loss and full-graph auxiliary loss with augmented node features re-constructed by the heterophily-aware projector. Extensive experiments show that ACE drives consistent gains on heterophilic benchmarks while preserving competitive results on homophilic graphs with minimal computational overhead. Code is available at the GitHub repository: https://github.com/vasile-paskardlgm/ACE.