Graph Neural Networks (GNNs) have emerged in recent years as a powerful tool to learn tasks across a wide range of graph domains in a data-driven fashion; based on a message passing mechanism, GNNs have gained increasing popularity due to their intuitive formulation, closely linked with the Weisfeiler-Lehman (WL) test for graph isomorphism, to which they have proven equivalent. In this thesis, we provide a broad overview of two essential properties of GNNs by a theoretical point of view, namely, their approximation power and their generalization capabilities. We show that modern GNNs are universal approximators, given that they are made by a sufficient number of layers, which is tightly linked to the stable node coloring of the 1-WL test. GNNs are shown to be universal approximators also on more complex graph domains, like edge-attributed graphs and dynamic graphs. Generalization capabilities of GNNs are investigated by different perspectives. Bounds on the VC dimension of GNNs are provided with respect to the usual hyperparameters and with respect to the number of colors derived from the 1-WL test. GNNs ability to generalize to unseen data is also explored by a neurocognitive point of view, determining whether these models are able to learn the so-called identity effects.

Theoretical Properties of Graph Neural Networks

D'INVERNO, GIUSEPPE ALESSIO
2024

Abstract

Graph Neural Networks (GNNs) have emerged in recent years as a powerful tool to learn tasks across a wide range of graph domains in a data-driven fashion; based on a message passing mechanism, GNNs have gained increasing popularity due to their intuitive formulation, closely linked with the Weisfeiler-Lehman (WL) test for graph isomorphism, to which they have proven equivalent. In this thesis, we provide a broad overview of two essential properties of GNNs by a theoretical point of view, namely, their approximation power and their generalization capabilities. We show that modern GNNs are universal approximators, given that they are made by a sufficient number of layers, which is tightly linked to the stable node coloring of the 1-WL test. GNNs are shown to be universal approximators also on more complex graph domains, like edge-attributed graphs and dynamic graphs. Generalization capabilities of GNNs are investigated by different perspectives. Bounds on the VC dimension of GNNs are provided with respect to the usual hyperparameters and with respect to the number of colors derived from the 1-WL test. GNNs ability to generalize to unseen data is also explored by a neurocognitive point of view, determining whether these models are able to learn the so-called identity effects.
29-apr-2024
Inglese
Universal approximation
Generalization
VC dimension
Identity Effects
SAMPOLI, MARIA LUCIA
SCARSELLI, FRANCO
BIANCHINI, MONICA
Università degli Studi di Siena
Dipartimento di Ingegneria dell'Informazione e Scienze Matematiche
126
File in questo prodotto:
File Dimensione Formato  
phd_unisi_102491.pdf

accesso aperto

Dimensione 7.39 MB
Formato Adobe PDF
7.39 MB Adobe PDF Visualizza/Apri

I documenti in UNITESI sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.14242/87928
Il codice NBN di questa tesi è URN:NBN:IT:UNISI-87928