Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/38990
Title: | On the Expressive Power of Message-Passing Neural Networks as Global Feature Map Transformers | Authors: | GEERTS, Floris STEEGMANS, Jasper VAN DEN BUSSCHE, Jan |
Issue Date: | 2022 | Publisher: | SPRINGER INTERNATIONAL PUBLISHING AG | Source: | Varzinczak, Ivan (Ed.). Foundations of Information and Knowledge Systems 12th International Symposium, FoIKS 2022 Helsinki, Finland, June 20–23, 2022 Proceedings, SPRINGER INTERNATIONAL PUBLISHING AG, p. 20 -34 | Series/Report: | Lecture Notes in Computer Science | Abstract: | We investigate the power of message-passing neural networks (MPNNs) in their capacity to transform the numerical features stored in the nodes of their input graphs. Our focus is on global expressive power, uniformly over all input graphs, or over graphs of bounded degree with features from a bounded domain. Accordingly, we introduce the notion of a global feature map transformer (GFMT). As a yardstick for expressiveness, we use a basic language for GFMTs, which we call MPLang. Every MPNN can be expressed in MPLang, and our results clarify to which extent the converse inclusion holds. We consider exact versus approximate expressiveness; the use of arbitrary activation functions; and the case where only the ReLU activation function is allowed. | Keywords: | Closure under concatenation;Semiring provenance semantics for modal logic;Query languages for numerical data | Document URI: | http://hdl.handle.net/1942/38990 | ISBN: | 978-3-031-11320-8 978-3-031-11321-5 |
DOI: | 10.1007/978-3-031-11321-5_2 | ISI #: | WOS:000883026400002 | Category: | C1 | Type: | Proceedings Paper | Validations: | ecoom 2023 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Pages from 978-3-031-11321-5.pdf Restricted Access | Published version | 272.06 kB | Adobe PDF | View/Open Request a copy |
helsinki.pdf | Peer-reviewed author version | 273.91 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.