Mathematical Expressiveness of Graph Neural Networks

Guillaume Lachaud (), Patricia Conde-Cespedes and Maria Trocan
Additional contact information
Guillaume Lachaud: ISEP—Institut Supérieur d’Électronique de Paris, 75006 Paris, France
Patricia Conde-Cespedes: ISEP—Institut Supérieur d’Électronique de Paris, 75006 Paris, France
Maria Trocan: ISEP—Institut Supérieur d’Électronique de Paris, 75006 Paris, France

Mathematics, 2022, vol. 10, issue 24, 1-15

Abstract: Graph Neural Networks (GNNs) are neural networks designed for processing graph data. There has been a lot of focus on recent developments of graph neural networks concerning the theoretical properties of the models, in particular with respect to their mathematical expressiveness, that is, to map different graphs or nodes to different outputs; or, conversely, to map permutations of the same graph to the same output. In this paper, we review the mathematical expressiveness results of graph neural networks. We find that according to their mathematical properties, the GNNs that are more expressive than the standard graph neural networks can be divided into two categories: the models that achieve the highest level of expressiveness, but require intensive computation; and the models that improve the expressiveness of standard graph neural networks by implementing node identification and substructure awareness. Additionally, we present a comparison of existing architectures in terms of their expressiveness. We conclude by discussing the future lines of work regarding the theoretical expressiveness of graph neural networks.

Keywords: graph neural networks; message passing neural networks; expressiveness; Weisfeiler–Leman algorithm (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/24/4770/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/24/4770/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:24:p:4770-:d:1004443

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().