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

Guoming Li, Jian Yang, Xukun Wang, Zixiao Wang, Shangsong Liang, Yifan Chen
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:3738-3761, 2026.

Abstract

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 *homophilic* graphs, leaving the more challenging *heterophilic* 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 **A**daptive **C**omplementary **E**nhancement, 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 *anisotropic structural regularization* to embed local heterophily. We further adopt *homoscedastic 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: \url{ https://github.com/vasile-paskardlgm/ACE }.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-li26j, title = {Remedying Coarsening-Based GNN Training under Heterophily via Adaptive Complementary Enhancement}, author = {Li, Guoming and Yang, Jian and Wang, Xukun and Wang, Zixiao and Liang, Shangsong and Chen, Yifan}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {3738--3761}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/li26j/li26j.pdf}, url = {https://proceedings.mlr.press/v337/li26j.html}, abstract = {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 *homophilic* graphs, leaving the more challenging *heterophilic* 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 **A**daptive **C**omplementary **E**nhancement, 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 *anisotropic structural regularization* to embed local heterophily. We further adopt *homoscedastic 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: \url{ https://github.com/vasile-paskardlgm/ACE }.} }
Endnote
%0 Conference Paper %T Remedying Coarsening-Based GNN Training under Heterophily via Adaptive Complementary Enhancement %A Guoming Li %A Jian Yang %A Xukun Wang %A Zixiao Wang %A Shangsong Liang %A Yifan Chen %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-li26j %I PMLR %P 3738--3761 %U https://proceedings.mlr.press/v337/li26j.html %V 337 %X 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 *homophilic* graphs, leaving the more challenging *heterophilic* 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 **A**daptive **C**omplementary **E**nhancement, 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 *anisotropic structural regularization* to embed local heterophily. We further adopt *homoscedastic 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: \url{ https://github.com/vasile-paskardlgm/ACE }.
APA
Li, G., Yang, J., Wang, X., Wang, Z., Liang, S. & Chen, Y.. (2026). Remedying Coarsening-Based GNN Training under Heterophily via Adaptive Complementary Enhancement. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:3738-3761 Available from https://proceedings.mlr.press/v337/li26j.html.

Related Material