Convexified Message-Passing Graph Neural Networks

Saar Cohen, Noa Agmon, Uri Shaham
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:676-684, 2026.

Abstract

Graph Neural Networks (GNNs) are key tools for graph representation learning, demonstrating strong results across diverse prediction tasks. In this paper, we present \textbf{Convexified Message-Passing Graph Neural Networks} (CGNNs), a novel and general framework that combines the power of message-passing GNNs with the tractability of \emph{convex} optimization. By mapping their nonlinear filters into a reproducing kernel Hilbert space, CGNNs transform training into a convex optimization problem, which projected gradient methods can solve both efficiently and optimally. Convexity further allows CGNNs’ statistical properties to be analyzed accurately and rigorously. For two-layer CGNNs, we establish rigorous generalization guarantees, showing convergence to the performance of an optimal GNN. To scale to deeper architectures, we adopt a principled layer-wise training strategy. Experiments on benchmark datasets show that CGNNs significantly exceed the performance of leading GNN models, obtaining 10–40% higher accuracy in most cases, underscoring their promise as a powerful and principled method with strong theoretical foundations. In rare cases where improvements are not quantitatively substantial, the convex models either slightly exceed or match the baselines, stressing their robustness and wide applicability. Though over-parameterization is often used to enhance performance in non-convex models, we show that our CGNNs yield shallow convex models that can surpass non-convex ones in accuracy and model compactness.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-cohen26a, title = { Convexified Message-Passing Graph Neural Networks }, author = {Cohen, Saar and Agmon, Noa and Shaham, Uri}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {676--684}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/cohen26a/cohen26a.pdf}, url = {https://proceedings.mlr.press/v300/cohen26a.html}, abstract = { Graph Neural Networks (GNNs) are key tools for graph representation learning, demonstrating strong results across diverse prediction tasks. In this paper, we present \textbf{Convexified Message-Passing Graph Neural Networks} (CGNNs), a novel and general framework that combines the power of message-passing GNNs with the tractability of \emph{convex} optimization. By mapping their nonlinear filters into a reproducing kernel Hilbert space, CGNNs transform training into a convex optimization problem, which projected gradient methods can solve both efficiently and optimally. Convexity further allows CGNNs’ statistical properties to be analyzed accurately and rigorously. For two-layer CGNNs, we establish rigorous generalization guarantees, showing convergence to the performance of an optimal GNN. To scale to deeper architectures, we adopt a principled layer-wise training strategy. Experiments on benchmark datasets show that CGNNs significantly exceed the performance of leading GNN models, obtaining 10–40% higher accuracy in most cases, underscoring their promise as a powerful and principled method with strong theoretical foundations. In rare cases where improvements are not quantitatively substantial, the convex models either slightly exceed or match the baselines, stressing their robustness and wide applicability. Though over-parameterization is often used to enhance performance in non-convex models, we show that our CGNNs yield shallow convex models that can surpass non-convex ones in accuracy and model compactness. } }
Endnote
%0 Conference Paper %T Convexified Message-Passing Graph Neural Networks %A Saar Cohen %A Noa Agmon %A Uri Shaham %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-cohen26a %I PMLR %P 676--684 %U https://proceedings.mlr.press/v300/cohen26a.html %V 300 %X Graph Neural Networks (GNNs) are key tools for graph representation learning, demonstrating strong results across diverse prediction tasks. In this paper, we present \textbf{Convexified Message-Passing Graph Neural Networks} (CGNNs), a novel and general framework that combines the power of message-passing GNNs with the tractability of \emph{convex} optimization. By mapping their nonlinear filters into a reproducing kernel Hilbert space, CGNNs transform training into a convex optimization problem, which projected gradient methods can solve both efficiently and optimally. Convexity further allows CGNNs’ statistical properties to be analyzed accurately and rigorously. For two-layer CGNNs, we establish rigorous generalization guarantees, showing convergence to the performance of an optimal GNN. To scale to deeper architectures, we adopt a principled layer-wise training strategy. Experiments on benchmark datasets show that CGNNs significantly exceed the performance of leading GNN models, obtaining 10–40% higher accuracy in most cases, underscoring their promise as a powerful and principled method with strong theoretical foundations. In rare cases where improvements are not quantitatively substantial, the convex models either slightly exceed or match the baselines, stressing their robustness and wide applicability. Though over-parameterization is often used to enhance performance in non-convex models, we show that our CGNNs yield shallow convex models that can surpass non-convex ones in accuracy and model compactness.
APA
Cohen, S., Agmon, N. & Shaham, U.. (2026). Convexified Message-Passing Graph Neural Networks . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:676-684 Available from https://proceedings.mlr.press/v300/cohen26a.html.

Related Material