The expressive power of graph Neural Networks as a query language
Author
dc.contributor.author
Barceló, Pablo
Author
dc.contributor.author
Kostylev, Egor
Author
dc.contributor.author
Monet, Mikael
Author
dc.contributor.author
Pérez Rojas, Jorge
Author
dc.contributor.author
Reutter, Juan L.
Author
dc.contributor.author
Silva, Juan Pablo
Admission date
dc.date.accessioned
2021-07-05T22:03:50Z
Available date
dc.date.available
2021-07-05T22:03:50Z
Publication date
dc.date.issued
2020
Cita de ítem
dc.identifier.citation
SIGMOD Record, June 2020 (Vol. 49, No. 2)
es_ES
Identifier
dc.identifier.uri
https://repositorio.uchile.cl/handle/2250/180430
Abstract
dc.description.abstract
In this paper we survey our recent results characterizing various graph neural network (GNN) architectures in terms of their ability to classify nodes over graphs, for classifiers based on unary logical formulas- or queries. We focus on the language FOC2, a well-studied fragment of FO. This choice is motivated by the fact that FOC2 is related to the Weisfeiler-Lehman (WL) test for checking graph isomorphism, which has the same ability as GNNs for distinguishing nodes on graphs. We unveil the exact relationship between FOC2 and GNNs in terms of node classification. To tackle this problem, we start by studying a popular basic class of GNNs, which we call AC-GNNs, in which the features of each node in a graph are updated, in successive layers, according only to the features of its neighbors. We prove that the unary FOC2 formulas that can be captured by an AC-GNN are exactly those that can be expressed in its guarded fragment, which in turn corresponds to graded modal logic. This result implies in particular that AC-GNNs are too weak to capture all FOC2 formulas. We then seek for what needs to be added to AC-GNNs for capturing all FOC2. We show that it suffices to add readouts layers, which allow updating the node features not only in terms of its neighbors, but also in terms of a global attribute vector. We call GNNs with readouts ACR-GNNs. We also describe experiments that validate our findings by showing that, on synthetic data conforming to FOC2 but not to graded modal logic, AC-GNNs struggle to fit in while ACR-GNNs can generalise even to graphs of sizes not seen during training.
es_ES
Patrocinador
dc.description.sponsorship
Millennium Institute for Foundational Research on Data3
Comision Nacional de Investigacion Cientifica y Tecnologica (CONICYT)
CONICYT FONDECYT
1200967