Cos'è il Graph Isomorphism Network (GIN)?

La Rete di Isomorfismo di Grafi (GIN) è un tipo di rete neurale di grafi (GNN) progettata per distinguere efficacemente i grafi. GIN si basa sull’idea che la sua architettura possa approssimare la potenza dell’algoritmo di verifica di isomorfismo di grafi (test di Weisfeiler-Lehman), rendendola molto espressiva.

L’idea principale di GIN è l’aggregazione delle caratteristiche dei nodi vicini tramite somma e l’applicazione successiva di un perceptron multistrato (MLP). Questo permette alla rete di distinguere meglio le strutture dei grafi rispetto ad altri metodi di aggregazione (ad esempio, la media).

Esempio di formula di aggiornamento delle caratteristiche del nodo v:

h_v^{(k)} = MLP^{(k)} \left( (1 + \epsilon^{(k)}) \cdot h_v^{(k-1)} + \sum_{u \in N(v)} h_u^{(k-1)} \right)

dove:

• (h_v^{(k)}) sono le caratteristiche del nodo v al livello k,
• (N(v)) è l’insieme dei vicini del nodo v,
• (\epsilon^{(k)}) è un parametro apprendibile,
• MLP è un perceptron multistrato.

Pertanto, GIN è efficace per compiti in cui è importante distinguere sottili differenze strutturali tra grafi.