A Graphop Analysis of Graph Neural Networks on Sparse Graphs: Generalization and Universal Approximation

Ofek Amran, Tom Gilat, Ron Levie
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:2463-2536, 2026.

Abstract

Generalization and approximation capabilities of message passing graph neural networks (MPNNs) are often studied by defining a compact metric on a space of input graphs under which MPNNs are equicontinuous. Such analyses are of two varieties: 1) when the metric space includes graphs of unbounded sizes, the theory is only appropriate for dense graphs, and, 2) when studying sparse graphs, the metric space only includes graphs of uniformly bounded size. In this work, we present a unified approach, defining a compact metric on the space of graphs of all sizes, both sparse and dense, under which MPNNs are equicontinuous. This leads to more powerful universal approximation theorems and generalization bounds than previous works. The theory is based on, and extends, a recent approach to graph limit theory called graphop analysis.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-amran26a, title = {A Graphop Analysis of Graph Neural Networks on Sparse Graphs: Generalization and Universal Approximation}, author = {Amran, Ofek and Gilat, Tom and Levie, Ron}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {2463--2536}, 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/amran26a/amran26a.pdf}, url = {https://proceedings.mlr.press/v306/amran26a.html}, abstract = {Generalization and approximation capabilities of message passing graph neural networks (MPNNs) are often studied by defining a compact metric on a space of input graphs under which MPNNs are equicontinuous. Such analyses are of two varieties: 1) when the metric space includes graphs of unbounded sizes, the theory is only appropriate for dense graphs, and, 2) when studying sparse graphs, the metric space only includes graphs of uniformly bounded size. In this work, we present a unified approach, defining a compact metric on the space of graphs of all sizes, both sparse and dense, under which MPNNs are equicontinuous. This leads to more powerful universal approximation theorems and generalization bounds than previous works. The theory is based on, and extends, a recent approach to graph limit theory called graphop analysis.} }
Endnote
%0 Conference Paper %T A Graphop Analysis of Graph Neural Networks on Sparse Graphs: Generalization and Universal Approximation %A Ofek Amran %A Tom Gilat %A Ron Levie %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-amran26a %I PMLR %P 2463--2536 %U https://proceedings.mlr.press/v306/amran26a.html %V 306 %X Generalization and approximation capabilities of message passing graph neural networks (MPNNs) are often studied by defining a compact metric on a space of input graphs under which MPNNs are equicontinuous. Such analyses are of two varieties: 1) when the metric space includes graphs of unbounded sizes, the theory is only appropriate for dense graphs, and, 2) when studying sparse graphs, the metric space only includes graphs of uniformly bounded size. In this work, we present a unified approach, defining a compact metric on the space of graphs of all sizes, both sparse and dense, under which MPNNs are equicontinuous. This leads to more powerful universal approximation theorems and generalization bounds than previous works. The theory is based on, and extends, a recent approach to graph limit theory called graphop analysis.
APA
Amran, O., Gilat, T. & Levie, R.. (2026). A Graphop Analysis of Graph Neural Networks on Sparse Graphs: Generalization and Universal Approximation. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:2463-2536 Available from https://proceedings.mlr.press/v306/amran26a.html.

Related Material