Graph Neural Networks Are Not Continuous Across Graph Resolutions

Christian Koke, Yuesong Shen, Abhishek Saroha, Marvin Eisenberger, Bastian Rieck, Michael M. Bronstein, Daniel Cremers
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:59879-59931, 2026.

Abstract

We show that contrary to conventional wisdom in the community, graph neural networks (GNNs) are not continuous with respect to all natural modes of graph convergence. As a result, GNNs may generate substantially different latent representations for graphs that are very similar. In particular they assign vastly different latent embeddings to graphs that represent the same underlying object at different resolution scales. We trace this failure of continuity back to a structural obstruction arising from commonly used information-propagation schemes. Building on this insight we then derive a principled modification to standard GNN architectures which equips models with continuity across scales. The proposed modification enables consistent integration of distinct resolutions and reliable generalization between them. We systematically validate our theoretical findings in a wide range of numerical experiments.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-koke26a, title = {Graph Neural Networks Are Not Continuous Across Graph Resolutions}, author = {Koke, Christian and Shen, Yuesong and Saroha, Abhishek and Eisenberger, Marvin and Rieck, Bastian and Bronstein, Michael M. and Cremers, Daniel}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {59879--59931}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/koke26a/koke26a.pdf}, url = {https://proceedings.mlr.press/v306/koke26a.html}, abstract = {We show that contrary to conventional wisdom in the community, graph neural networks (GNNs) are not continuous with respect to all natural modes of graph convergence. As a result, GNNs may generate substantially different latent representations for graphs that are very similar. In particular they assign vastly different latent embeddings to graphs that represent the same underlying object at different resolution scales. We trace this failure of continuity back to a structural obstruction arising from commonly used information-propagation schemes. Building on this insight we then derive a principled modification to standard GNN architectures which equips models with continuity across scales. The proposed modification enables consistent integration of distinct resolutions and reliable generalization between them. We systematically validate our theoretical findings in a wide range of numerical experiments.} }
Endnote
%0 Conference Paper %T Graph Neural Networks Are Not Continuous Across Graph Resolutions %A Christian Koke %A Yuesong Shen %A Abhishek Saroha %A Marvin Eisenberger %A Bastian Rieck %A Michael M. Bronstein %A Daniel Cremers %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-koke26a %I PMLR %P 59879--59931 %U https://proceedings.mlr.press/v306/koke26a.html %V 306 %X We show that contrary to conventional wisdom in the community, graph neural networks (GNNs) are not continuous with respect to all natural modes of graph convergence. As a result, GNNs may generate substantially different latent representations for graphs that are very similar. In particular they assign vastly different latent embeddings to graphs that represent the same underlying object at different resolution scales. We trace this failure of continuity back to a structural obstruction arising from commonly used information-propagation schemes. Building on this insight we then derive a principled modification to standard GNN architectures which equips models with continuity across scales. The proposed modification enables consistent integration of distinct resolutions and reliable generalization between them. We systematically validate our theoretical findings in a wide range of numerical experiments.
APA
Koke, C., Shen, Y., Saroha, A., Eisenberger, M., Rieck, B., Bronstein, M.M. & Cremers, D.. (2026). Graph Neural Networks Are Not Continuous Across Graph Resolutions. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:59879-59931 Available from https://proceedings.mlr.press/v306/koke26a.html.

Related Material