GRAPHS Flashcards
Cos’è un grafo?
Un grafo eterogeneo, denotato come G=(V,E,R,T), è una struttura dati che combina nodi e archi con attributi e relazioni specifiche.
V rappresenta l’insieme dei nodi, con ciascun nodo che può avere attributi diversi.
E denota l’insieme degli archi, con ogni arco che può avere attributi specifici.
R indica l’insieme delle relazioni che specifica come i nodi e gli archi sono collegati.
T rappresenta l’insieme dei tipi di nodi e archi, che forniscono informazioni sulla natura delle entità e delle relazioni nel grafo.
Cos’è il node embedding?
il processo di creazione di embedding per nodi in grafi attraverso modelli di rappresentazione dei grafi (graph representation learning). Questo approccio automaticamente deduce le caratteristiche dei nodi, eliminando la necessità di costruire manualmente i grafici.
Il processo coinvolge:
Encoder: Trasforma i nodi in embedding. Questo embedding preserva la similarità tra i nodi.
Decoder: Mappa inversamente gli embedding in uno score di similarità. L’obiettivo è ottimizzare i parametri in modo che la similarità tra nodi sia approssimativamente uguale alla similarità tra i loro embedding.
La dimensione dell’embedding dipende dalla grandezza del grafo. Un’opzione di codifica superficiale coinvolge la regressione logistica.
L’encoding può essere effettuato come una ricerca in una tabella contenente gli embedding di tutti i nodi. La similarità tra due nodi all’interno di un grafo viene definita utilizzando random walks, basate sull’esplorazione delle vicinanze per ottenere informazioni sull’ambiente del nodo
Cos’è il random walk?
Il “random walk” è una procedura che coinvolge lo spostamento casuale da un nodo all’altro attraverso gli archi del grafo. Partendo da un nodo iniziale, ad ogni passo, si seleziona casualmente uno dei vicini del nodo corrente e ci si sposta su di esso. Questo processo viene ripetuto per un numero fissato di passi o fino a quando non viene raggiunto un nodo specifico di destinazione.
Random walk embeddings?
Per creare gli embedding dei nodi di un grafo, utilizziamo il processo di random walk per generare sequenze di nodi casuali. Definiamo la probabilità di visitare un nodo v partendo da un nodo u durante una random walk e ottimizziamo gli embedding affinché codifichino queste statistiche. Le random walk sono efficienti perché esplorano solo una frazione dei possibili percorsi. Per creare gli embedding, eseguiamo random walk di lunghezza definita da ogni nodo u, costruiamo l’insieme dei vicini e ottimizziamo gli embedding in modo che la somma delle probabilità di visita sia massimizzata. Per ridurre la complessità computazionale, utilizziamo negative sampling per approssimare il calcolo su tutti i nodi. Calcoliamo la funzione di loss e utilizziamo lo stochastic gradient descent per ottimizzare gli embedding.
Node2Vec
Node2Vec è un modello che migliora la tecnica di random walk utilizzando una strategia biased, anziché casuale, basata su due criteri: la località e la globalità. Nella località, vengono visitati i nodi vicini senza allontanarsi troppo, mentre nella globalità si esplora di più, allontanandosi. La biased random walk ha due parametri: p, che controlla la probabilità di tornare al nodo precedente, e q, che regola il rapporto tra visita locale e globale. Le probabilità di scelta durante la biased random walk sono guidate da questi parametri, con 1/q per esplorare lontano, 1/p per tornare al nodo iniziale e 1 per i nodi a distanza 1, normalizzati in un range 0-1. Node2Vec calcola le probabilità di transizione degli archi, simula random walk partendo da ogni nodo e ottimizza gli embedding utilizzando lo stochastic gradient descent, con complessità lineare e possibilità di parallelizzazione. La scelta tra Node2Vec e random walk dipende dall’applicazione specifica, con entrambi validi ma random walk generalmente più efficiente.
Come puoi creare un embedding dell’intero grafo?
Per creare un embedding dell’intero grafo, ci sono diversi approcci possibili. Uno consiste nella somma o nella media degli embedding di tutti i nodi del grafo. Un altro approccio è quello di creare nodi virtuali che sintetizzano le caratteristiche dei sottografi, riducendo così il problema a un embedding per nodo. Un terzo approccio è quello di embeddare il grado del nodo con una navigazione anonima, dove lo stato nelle random walk anonime corrisponde all’indice della prima visita di un nodo. La tecnica di diff pool clusterizza gerarchicamente i nodi e somma o fa la media degli embedding dei cluster. La fattorizzazione delle matrici è un altro approccio, dove l’obiettivo è costruire una matrice Z in modo che il prodotto tra Z e la sua trasposta sia simile alla matrice di adiacenza del grafo. Questo problema può essere risolto tramite approssimazioni. Le tecniche come DeepWalk e Node2Vec sono anch’esse riconducibili a formule di fattorizzazione per ridurre la complessità. Gli embedding così ottenuti possono essere utilizzati per varie attività come clustering, classificazione dei nodi, predizione dei collegamenti e classificazione del grafo.
Cosa sono i GCN?
I Graph Convolutional Networks (GCN) sono modelli neurali progettati per l’analisi dei grafi. Estendono i concetti delle reti neurali convoluzionali (CNN) ai dati strutturati rappresentati come grafi anziché matrici o tensori. I GCN operano applicando uno o più layer convoluzionali sui grafi, tenendo conto della struttura dei vicini dei nodi
Problemi con le gnn e soluzioni
Il problema con le gnn è che il grafo non ha una struttura fissa quindi quando ci andiamo ad applicare funzioni devono essere o invarianti alla permutazione o equivarianti, invarianti alla permutazione vuol dire che l’output di diverse rappresentazioni dello stesso grafo ha sia stesso ordine che stesso risultato, equivarianti vuol dire che gli output hanno solo lo stesso risultato ma con ordine diverso
deep encoding
gnn vs transformers vs cnn
le Cnn possono essere intese come un GNN con un vicinato fissato, mentre i trasformers come un grafo totalemente connesso
