EUVIMEDEUVIMED entdecken
Crossref

On the Power of Graph Neural Networks and the Role of the Activation Function

Sammy Khalife, Amitabh Basu

SIAM Journal on Applied Algebra and Geometry · 30.06.2026 · 10 (2) · 350-365

DOI: 10.1137/24m1659704 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Applied Algebra and Geometry, online erschienen am 23.06.2026. Verfasst von Sammy Khalife und 1 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 31 Literaturangaben. Gefördert von: Air Force Office of Scientific Research, National Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In this article we present new results about the expressivity of graph neural networks (GNNs). We prove that for any GNN with piecewise polynomial activations, whose architecture size does not grow with the graph input sizes, there exists a pair of nonisomorphic rooted trees of depth two such that the GNN cannot distinguish their root vertex up to an arbitrary number of iterations. In contrast, it was already known that unbounded GNNs (those whose size is allowed to change with the graph sizes) with piecewise polynomial activations can distinguish these vertices in only two iterations. It was also known prior to our work that with ReLU (piecewise linear) activations, bounded GNNs are weaker than unbounded GNNs [A. Aamand et al., Exponentially improving the complexity of simulating the Weisfeiler-Lehman test with graph neural networks, in Proceedings of the 36th Conference on Neural Information Processing Systems (NeurIPS 2022), Adv. Neural Inform. Process. Syst. 35, Curran Associates, 2022, pp. 27333–27346]. Our approach adds to this result by extending it to handle any piecewise polynomial activation function, which goes towards answering an open question formulated by Grohe more completely [M. Grohe, The logic of graph neural networks, in LICS ’21: Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, IEEE, 2021, pp. 1–17]. Our second result states that if one allows activations that are not piecewise polynomial, then in two iterations a single neuron perceptron can distinguish the root vertices of any pair of nonisomorphic trees of depth two (our results hold for activations like the sigmoid, hyperbolic tan, and others). This shows how the power of GNNs can change drastically if one changes the activation function of the neural networks. The proof of this result utilizes the Lindemann–Weierstrauss theorem from transcendental number theory.

Förderung

  • Air Force Office of Scientific Research
  • National Science Foundation

Zitieren

APA

Khalife, S., & Basu, A. (2026). On the Power of Graph Neural Networks and the Role of the Activation Function. SIAM Journal on Applied Algebra and Geometry, 10(2), 350-365. https://doi.org/10.1137/24m1659704

Vancouver

Khalife S, Basu A. On the Power of Graph Neural Networks and the Role of the Activation Function. SIAM Journal on Applied Algebra and Geometry. 2026;10(2):350-365. doi:10.1137/24m1659704

BibTeX
@article{Khalife2026,
  author = {Khalife, Sammy and Basu, Amitabh},
  title = {On the Power of Graph Neural Networks and the Role of the Activation Function},
  journal = {SIAM Journal on Applied Algebra and Geometry},
  year = {2026},
  volume = {10},
  number = {2},
  pages = {350--365},
  doi = {10.1137/24m1659704}
}
Kostenlos starten →