Un'introduzione completa alle Graph Neural Networks (GNN)

Che cos'è un grafo?

Un grafo è una struttura dati che contiene nodi e archi. Un nodo può essere una persona, un luogo o una cosa, e gli archi definiscono la relazione tra i nodi. Gli archi possono essere diretti o non diretti in base alle dipendenze direzionali. 

Nell'esempio qui sotto, i cerchi blu sono nodi e le frecce sono archi. La direzione degli archi definisce le dipendenze tra due nodi. 

Immagine dell'autore 

Conosciamo il dataset di grafi complesso: Jazz Musicians Network. Contiene 198 nodi e 2742 archi. Nel grafico di comunità qui sotto, i colori diversi dei nodi rappresentano varie comunità di musicisti Jazz e gli archi che li collegano. Esiste una rete di collaborazioni in cui un singolo musicista ha relazioni sia all'interno che all'esterno della comunità. 

 Grafico di comunità di Jazz Musicians Network

I grafi sono eccellenti per affrontare problemi complessi con relazioni e interazioni. Sono usati nel riconoscimento di pattern, nell'analisi dei social network, nei sistemi di raccomandazione e nell'analisi semantica. Creare soluzioni basate su grafi è un intero campo a sé che offre ricche intuizioni su dataset complessi e interconnessi.

Grafi con NetworkX

In questa sezione impareremo a creare un grafo usando NetworkX. 

Il codice seguente è ispirato al blog di Daniel Holmberg sulle Graph Neural Networks in Python.

1. Crea l'oggetto DiGraph di networkx "H"
2. Aggiungi nodi che contengono etichette, colori e dimensioni differenti
3. Aggiungi archi per creare una relazione tra due nodi. Ad esempio, "(0,1)" significa che 0 ha una dipendenza direzionale da 1. Creeremo relazioni bidirezionali aggiungendo "(1,0)"
4. Estrai colori e dimensioni sotto forma di liste
5. Traccia il grafo usando la funzione draw di networkx

import networkx as nx
H = nx.DiGraph()

#adding nodes
H.add_nodes_from([
  (0, {"color": "blue", "size": 250}),

  (1, {"color": "yellow", "size": 400}),

  (2, {"color": "orange", "size": 150}),

  (3, {"color": "red", "size": 600})


])

#adding edges
H.add_edges_from([
  (0, 1),

  (1, 2),

  (1, 0),

  (1, 3),

  (2, 3),

  (3,0)


])

node_colors = nx.get_node_attributes(H, "color").values()
colors = list(node_colors)
node_sizes = nx.get_node_attributes(H, "size").values()
sizes = list(node_sizes)

#Plotting Graph
nx.draw(H, with_labels=True, node_color=colors, node_size=sizes)

Nel prossimo passaggio, convertiremo la struttura dati da grafo direzionale a grafo non direzionale usando la funzione to_undirected(). 

#converting to undirected graph
G = H.to_undirected()
nx.draw(G, with_labels=True, node_color=colors, node_size=sizes)

Perché è difficile analizzare un grafo?

Le strutture dati basate su grafi hanno degli svantaggi, e i data scientist devono capirli prima di sviluppare soluzioni basate su grafi.

1. Un grafo esiste in uno spazio non euclideo. Non esiste in uno spazio 2D o 3D, il che rende più difficile interpretare i dati. Per visualizzare la struttura in 2D, devi usare vari strumenti di riduzione della dimensionalità.
2. I grafi sono dinamici; non hanno una forma fissa. Possono esistere due grafi visivamente diversi, ma con rappresentazioni simili tramite matrice di adiacenza. Ciò rende difficile analizzare i dati con strumenti statistici tradizionali. 
3. Dimensioni e dimensionalità elevate aumentano la complessità del grafo per l'interpretazione umana. Una struttura densa con più nodi e migliaia di archi è più difficile da comprendere e da cui estrarre insight. 

Che cos'è una Graph Neural Network (GNN)?

Le Graph Neural Networks sono tipi speciali di reti neurali in grado di lavorare con una struttura dati a grafo. Sono fortemente influenzate dalle Convolutional Neural Networks (CNN) e dal graph embedding. Le GNN sono utilizzate per la previsione di nodi, archi e per compiti basati su grafi. 

• Le CNN sono usate per la classificazione di immagini. Allo stesso modo, le GNN si applicano alla struttura del grafo (griglia di pixel) per prevedere una classe. 
• Le reti neurali ricorrenti sono usate nella classificazione del testo. Analogamente, le GNN si applicano a strutture a grafo in cui ogni parola è un nodo in una frase.  

Le GNN sono state introdotte quando le Convolutional Neural Networks non riuscivano a ottenere risultati ottimali a causa della dimensione arbitraria del grafo e della struttura complessa. 

Immagine di Purvanshi Mehta

Il grafo in input viene fatto passare attraverso una serie di reti neurali. La struttura del grafo di input viene convertita in un embedding del grafo, che ci consente di mantenere le informazioni su nodi, archi e contesto globale. 

Poi il vettore di caratteristiche dei nodi A e C viene fatto passare attraverso il livello della rete neurale. Esso aggrega queste caratteristiche e le passa al livello successivo - neptune.ai.

Leggi il nostro tutorial su Deep Learning o segui il corso Introduzione al Deep Learning per saperne di più sugli algoritmi e le applicazioni del deep learning. 

Tipi di Graph Neural Networks

Esistono diversi tipi di reti neurali, e la maggior parte presenta qualche variazione delle Convolutional Neural Networks. In questa sezione vedremo le GNN più popolari. 

• Le Graph Convolutional Networks (GCN) sono simili alle tradizionali CNN. Imparano le caratteristiche ispezionando i nodi vicini. Le GNN aggregano i vettori dei nodi, passano il risultato a un livello denso e applicano la non linearità tramite la funzione di attivazione. In breve, consistono in convoluzione su grafo, livello lineare e funzione di attivazione non lineare. Esistono due tipi principali di GCN: reti convoluzionali spaziali e reti convoluzionali spettrali.
• Le Graph Auto-Encoder Networks apprendono la rappresentazione del grafo usando un encoder e cercano di ricostruire i grafi di input con un decoder. Encoder e decoder sono collegati da un livello collo di bottiglia. Sono comunemente usate nella previsione di collegamenti, poiché gli Auto-Encoder gestiscono bene il bilanciamento delle classi. 
• Le Recurrent Graph Neural Networks (RGNN) apprendono il miglior schema di diffusione e possono gestire grafi multi-relazionali in cui un singolo nodo ha più relazioni. Questo tipo di rete neurale su grafi usa regolarizzatori per aumentare la levigatezza ed eliminare l'eccesso di parametri. Le RGNN usano meno potenza di calcolo per ottenere risultati migliori. Sono utilizzate nella generazione di testo, traduzione automatica, riconoscimento vocale, generazione di descrizioni di immagini, tagging di video e sintesi di testi.
• Le Gated Graph Neural Networks (GGNN) sono migliori delle RGNN nell'eseguire compiti con dipendenze a lungo termine. Le Gated Graph Neural Networks migliorano le Recurrent Graph Neural Networks aggiungendo gate su nodi, archi e tempo per le dipendenze di lungo periodo. Analogamente alle Gated Recurrent Units (GRU), i gate servono a ricordare e dimenticare informazioni in diversi stati. 

Se ti interessa saperne di più sulle Recurrent Neural Networks (RNN), dai un'occhiata al corso di DataCamp. Ti introdurrà a varie architetture di modelli RNN, ai framework Keras e alle applicazioni delle RNN. 

Tipi di task per le Graph Neural Networks

Qui sotto abbiamo elencato alcuni tipi di task per le GNN con esempi:

• Classificazione di grafi: si usa per classificare i grafi in varie categorie. Le sue applicazioni includono l'analisi dei social network e la classificazione di testi. 
• Classificazione di nodi: questo compito usa le etichette dei nodi vicini per prevedere etichette mancanti dei nodi in un grafo. 
• Previsione di collegamenti (Link Prediction): prevede il collegamento tra una coppia di nodi in un grafo con una matrice di adiacenza incompleta. È comunemente usata per i social network. 
• Rilevamento di comunità: divide i nodi in vari cluster sulla base della struttura degli archi. Impara in modo simile da pesi degli archi, distanza e oggetti del grafo. 
• Embedding di grafi: mappa i grafi in vettori, preservando le informazioni rilevanti su nodi, archi e struttura.
• Generazione di grafi: apprende dalla distribuzione di grafi campione per generare una nuova struttura a grafo simile. 

Immagine dell'autore

Svantaggi delle Graph Neural Networks

Ci sono alcuni svantaggi nell'uso delle GNN. Capirli ci aiuterà a determinare quando usare le GNN e come ottimizzare le prestazioni dei nostri modelli di machine learning. 

1. La maggior parte delle reti neurali può andare in profondità per ottenere prestazioni migliori, mentre le GNN sono reti poco profonde per lo più con tre livelli. Ci limita nel raggiungere prestazioni allo stato dell'arte su grandi dataset.
2. Le strutture a grafo cambiano costantemente, rendendo più difficile addestrarvi un modello. 
3. Il deployment in produzione del modello affronta problemi di scalabilità poiché queste reti sono computazionalmente costose. Se hai una struttura a grafo grande e complessa, sarà difficile scalare le GNN in produzione. 

Che cos'è una Graph Convolutional Network (GCN)?

La maggior parte delle GNN sono Graph Convolutional Networks, ed è importante conoscerle prima di passare a un tutorial sulla classificazione dei nodi.  

La convoluzione nelle GCN è la stessa delle convoluzioni nelle convolutional neural networks. Moltiplica i neuroni per pesi (filtri) per imparare dalle caratteristiche dei dati. 

Agisce come finestre scorrevoli su intere immagini per apprendere caratteristiche dalle celle vicine. Il filtro usa la condivisione dei pesi per imparare varie caratteristiche facciali nei sistemi di riconoscimento di immagini - Towards Data Science. 

Ora trasferisci la stessa funzionalità alle Graph Convolutional Networks, dove un modello impara le caratteristiche dai nodi vicini. La differenza principale tra GCN e CNN è che le GCN sono sviluppate per lavorare su strutture dati non euclidee, in cui l'ordine di nodi e archi può variare. 

CNN vs GCN | Fonte

Approfondisci le CNN di base seguendo il tutorial Convolutional Neural Networks (CNN) con TensorFlow. 

Esistono due tipi di GCN: 

• Le Spatial Graph Convolutional Networks usano caratteristiche spaziali per apprendere da grafi che sono collocati nello spazio spaziale.  
• Le Spectral Graph Convolutional Networks usano la decomposizione agli autovalori della matrice di Laplaciano del grafo per propagare l'informazione lungo i nodi. Queste reti sono state ispirate dalla propagazione d'onda nei segnali e nei sistemi. 

Come funzionano le GNN? Costruire una Graph Neural Network con Pytorch

Costruiremo e alleneremo una convoluzione spettrale su grafo per un modello di classificazione dei nodi. Il codice sorgente è disponibile in questo workbook DataLab per permetterti di provare ed eseguire il tuo primo modello di machine learning basato su grafi. 

Gli esempi di codice sono ispirati dalla documentazione di Pytorch geometric. 

Per iniziare

Installeremo il pacchetto Pytorch dato che pytorch_geometric è costruito su di esso. 

!pip install -q torch

Poi useremo la versione di torch per installare torch-scatter e torch-sparse. Successivamente installeremo l'ultima release di pytorch_geometric da GitHub. 

%%capture
import os
import torch
os.environ['TORCH'] = torch.__version__
os.environ['PYTHONWARNINGS'] = "ignore"
!pip install torch-scatter -f https://data.pyg.org/whl/torch-${TORCH}.html
!pip install torch-sparse -f https://data.pyg.org/whl/torch-${TORCH}.html
!pip install git+https://github.com/pyg-team/pytorch_geometric.git

Dataset Planetoid Cora

Planetoid è un dataset di reti di citazioni da Cora, CiteSeer e PubMed. I nodi sono documenti con vettori di caratteristiche bag-of-words a 1433 dimensioni, e gli archi sono link di citazione tra articoli di ricerca. Ci sono 7 classi e alleneremo il modello per prevedere le etichette mancanti. 

Caricheremo il dataset Planetoid Cora e normalizzeremo per riga le caratteristiche di input bag of words. Dopodiché analizzeremo il dataset e il primo oggetto grafo. 

from torch_geometric.datasets import Planetoid
from torch_geometric.transforms import NormalizeFeatures

dataset = Planetoid(root='data/Planetoid', name='Cora', transform=NormalizeFeatures())

print(f'Dataset: {dataset}:')
print('======================')
print(f'Number of graphs: {len(dataset)}')
print(f'Number of features: {dataset.num_features}')
print(f'Number of classes: {dataset.num_classes}')

data = dataset[0]  # Get the first graph object.
print(data)

Il dataset Cora ha 2708 nodi, 10.556 archi, 1433 caratteristiche e 7 classi. Il primo oggetto ha 2708 maschere di train, validazione e test. Useremo queste maschere per addestrare e valutare il modello. 

Dataset: Cora():
======================
Number of graphs: 1
Number of features: 1433
Number of classes: 7
Data(x=[2708, 1433], edge_index=[2, 10556], y=[2708], train_mask=[2708], val_mask=[2708], test_mask=[2708])

Classificazione di nodi con GNN

Creeremo una struttura di modello GCN che contiene due layer GCNConv, attivazione relu e un dropout di 0,5. Il modello ha 16 canali nascosti.  

Layer GCN:

La W(ℓ+1) è una matrice di pesi addestrabile nell'equazione sopra e Cw,v denota un coefficiente di normalizzazione fisso per ogni arco.

from torch_geometric.nn import GCNConv
import torch.nn.functional as F

class GCN(torch.nn.Module):
    def __init__(self, hidden_channels):
        super().__init__()
        torch.manual_seed(1234567)
        self.conv1 = GCNConv(dataset.num_features, hidden_channels)
        self.conv2 = GCNConv(hidden_channels, dataset.num_classes)

    def forward(self, x, edge_index):
        x = self.conv1(x, edge_index)
        x = x.relu()
        x = F.dropout(x, p=0.5, training=self.training)
        x = self.conv2(x, edge_index)
        return x

model = GCN(hidden_channels=16)
print(model)

>>> GCN(
    (conv1): GCNConv(1433, 16)
    (conv2): GCNConv(16, 7)
  )

Visualizzare una rete GCN non addestrata

Visualizziamo gli embedding dei nodi di reti GCN non addestrate usando sklearn.manifold.TSNE e matplotlib.pyplot. Verrà tracciato un embedding dei nodi a 7 dimensioni in uno scatter plot 2D.  

%matplotlib inline
import matplotlib.pyplot as plt
from sklearn.manifold import TSNE

def visualize(h, color):
    z = TSNE(n_components=2).fit_transform(h.detach().cpu().numpy())

    plt.figure(figsize=(10,10))
    plt.xticks([])
    plt.yticks([])

    plt.scatter(z[:, 0], z[:, 1], s=70, c=color, cmap="Set2")
    plt.show()

Valuteremo il modello, poi aggiungeremo i dati di training al modello non addestrato per visualizzare vari nodi e categorie. 

model.eval()

out = model(data.x, data.edge_index)
visualize(out, color=data.y)

Addestrare la GNN

Alleneremo il nostro modello per 100 epoche usando l'ottimizzazione Adam e la funzione di perdita Cross-Entropy. 

Nella funzione di train abbiamo:

1. Azzera il gradiente
2. Eseguito un singolo forward pass
3. Calcolato la perdita usando i nodi di training
4. Calcolato il gradiente e aggiornato i parametri

Nella funzione di test abbiamo:

1. Previsto la classe del nodo
2. Estratto l'etichetta di classe con probabilità più alta
3. Verificato quante previsioni sono state corrette
4. Creato il rapporto di accuratezza usando la somma delle previsioni corrette divisa per il numero totale di nodi. 

model = GCN(hidden_channels=16)
optimizer = torch.optim.Adam(model.parameters(), lr=0.01, weight_decay=5e-4)
criterion = torch.nn.CrossEntropyLoss()

def train():
      model.train()
      optimizer.zero_grad()
      out = model(data.x, data.edge_index)
      loss = criterion(out[data.train_mask], data.y[data.train_mask])
      loss.backward()
      optimizer.step()
      return loss

def test():
      model.eval()
      out = model(data.x, data.edge_index)
      pred = out.argmax(dim=1)
      test_correct = pred[data.test_mask] == data.y[data.test_mask]
      test_acc = int(test_correct.sum()) / int(data.test_mask.sum())
      return test_acc


for epoch in range(1, 101):
    loss = train()
    print(f'Epoch: {epoch:03d}, Loss: {loss:.4f}')
GAT(
  (conv1): GATConv(1433, 8, heads=8)
  (conv2): GATConv(64, 7, heads=8)
)

.. .. .. ..
.. .. .. ..
Epoch: 098, Loss: 0.5989
Epoch: 099, Loss: 0.6021
Epoch: 100, Loss: 0.5799

Valutazione del modello

Ora valuteremo il modello su un dataset non visto usando la funzione test e, come puoi vedere, abbiamo ottenuto un ottimo risultato con un'accuratezza dell'81,5%.  

test_acc = test()
print(f'Test Accuracy: {test_acc:.4f}')


>>> Test Accuracy: 0.8150

Ora visualizzeremo l'embedding in output di un modello addestrato per verificare i risultati.

model.eval()
out = model(data.x, data.edge_index)
visualize(out, color=data.y)

Come possiamo vedere, il modello addestrato ha prodotto un miglior clustering dei nodi per la stessa categoria.

Addestrare un modello GATConv

In seguito, sostituiremo GCNConv con layer GATConv. Le Graph Attention Networks usano layer di self-attention mascherati per affrontare gli svantaggi di GCNConv e ottenere risultati allo stato dell'arte. 

Puoi anche provare altri layer GNN e sperimentare con ottimizzazioni, dropout e numero di canali nascosti per ottenere prestazioni migliori. 

Nel codice sotto abbiamo semplicemente sostituito GCNConv con GATConv con 8 teste di attenzione nel primo layer e 1 nel secondo. 

Imposteremo anche:

• tasso di dropout a 0,6
• canali nascosti a 8
• learning rate a 0,005

Abbiamo modificato la funzione test per trovare l'accuratezza di una specifica maschera (valid, test). Ci aiuterà a stampare i punteggi di validazione e test durante l'addestramento del modello. Stiamo anche salvando i risultati di validazione e test per tracciarli successivamente in un grafico a linee. 

from torch_geometric.nn import GATConv

class GAT(torch.nn.Module):
    def __init__(self, hidden_channels, heads):
        super().__init__()
        torch.manual_seed(1234567)
        self.conv1 = GATConv(dataset.num_features, hidden_channels,heads)
        self.conv2 = GATConv(heads*hidden_channels, dataset.num_classes,heads)

    def forward(self, x, edge_index):
        x = F.dropout(x, p=0.6, training=self.training)
        x = self.conv1(x, edge_index)
        x = F.elu(x)
        x = F.dropout(x, p=0.6, training=self.training)
        x = self.conv2(x, edge_index)
        return x

model = GAT(hidden_channels=8, heads=8)
print(model)

optimizer = torch.optim.Adam(model.parameters(), lr=0.005, weight_decay=5e-4)
criterion = torch.nn.CrossEntropyLoss()

def train():
      model.train()
      optimizer.zero_grad()
      out = model(data.x, data.edge_index)
      loss = criterion(out[data.train_mask], data.y[data.train_mask])
      loss.backward()
      optimizer.step()
      return loss

def test(mask):
      model.eval()
      out = model(data.x, data.edge_index)
      pred = out.argmax(dim=1)
      correct = pred[mask] == data.y[mask]
      acc = int(correct.sum()) / int(mask.sum())
      return acc

val_acc_all = []
test_acc_all = []

for epoch in range(1, 101):
    loss = train()
    val_acc = test(data.val_mask)
    test_acc = test(data.test_mask)
    val_acc_all.append(val_acc)
    test_acc_all.append(test_acc)
    print(f'Epoch: {epoch:03d}, Loss: {loss:.4f}, Val: {val_acc:.4f}, Test: {test_acc:.4f}')

.. .. .. ..
.. .. .. ..
Epoch: 098, Loss: 1.1283, Val: 0.7960, Test: 0.8030

Epoch: 099, Loss: 1.1352, Val: 0.7940, Test: 0.8050

Epoch: 100, Loss: 1.1053, Val: 0.7960, Test: 0.8040

Come possiamo osservare, il nostro modello non ha ottenuto prestazioni migliori di GCNConv. Servono ottimizzazione degli iperparametri o più epoche per raggiungere risultati allo stato dell'arte. 

Valutazione del modello

Nella parte di valutazione, visualizziamo i punteggi di validazione e test usando il grafico a linee di matplotlib.pyplot.  

import numpy as np

plt.figure(figsize=(12,8))
plt.plot(np.arange(1, len(val_acc_all) + 1), val_acc_all, label='Validation accuracy', c='blue')
plt.plot(np.arange(1, len(test_acc_all) + 1), test_acc_all, label='Testing accuracy', c='red')
plt.xlabel('Epochs')
plt.ylabel('Accurarcy')
plt.title('GATConv')
plt.legend(loc='lower right', fontsize='x-large')
plt.savefig('gat_loss.png')
plt.show()

Dopo 60 epoche, l'accuratezza di validazione e test ha raggiunto un valore stabile di 0,8 +/-0,02. 

Di nuovo, visualizziamo il clustering dei nodi del modello GATConv.

model.eval()

out = model(data.x, data.edge_index)
visualize(out, color=data.y)

Come possiamo vedere, il layer GATConv ha prodotto gli stessi risultati di clustering sulla stessa categoria di nodi. 

Possiamo ridurre l'overfitting aggiungendo un secondo dataset di validazione e migliorare le prestazioni del modello sperimentando vari layer GCN da pytoch_geometric. 

Il codice sorgente del tutorial è disponibile in questo workbook DataLab. Crea una copia del workbook che puoi eseguire.

Aggiungi la skill di Deep Learning al tuo curriculum seguendo il percorso Deep Learning in Python. Ti introdurrà agli algoritmi di deep learning, a Keras, Pytorch e al framework TensorFlow.