Embedding di rete — Node2Vec, DeepWalk, LINE
- Anno
- 2014 (DeepWalk); 2016 (Node2Vec)
- Tipo
- Representation learning / unsupervised network method
Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese
A cosa serve?
L'embedding di rete è una famiglia di metodi di apprendimento della rappresentazione che mappa ciascun nodo di un grafo in un vettore denso e a bassa dimensionalità, preservando le proprietà strutturali della rete.
L'approccio è stato formalizzato per dati di social network da Perozzi, Al-Rfou e Skiena con DeepWalk (2014), che ha adattato il modello skip-gram di Word2Vec alle passeggiate casuali sui grafi, ed esteso da Grover e Leskovec con Node2Vec (2016), che ha introdotto una passeggiata casuale con bias che bilancia l'esplorazione in ampiezza (breadth-first) e in profondità (depth-first). Questi embedding trasformano i dati relazionali in vettori di caratteristiche che i classificatori e gli algoritmi di clustering di machine learning standard possono consumare direttamente.
L’intuizione alla base del metodo
Un grafo è composto da nodi e archi, ma la maggior parte degli algoritmi di machine learning si aspetta una tabella di numeri. L'embedding di rete risolve il problema della traduzione. Proprio come Word2Vec apprende i significati delle parole osservando quali parole appaiono vicine tra loro nelle frasi, DeepWalk apprende i significati dei nodi osservando quali nodi appaiono vicini tra loro nelle passeggiate casuali attraverso il grafo. Il risultato è una coordinata in uno spazio vettoriale — nodi strutturalmente simili o frequentemente co-visitati finiscono vicini. Una volta che ogni nodo ha un vettore, è possibile inserire questi vettori in un classificatore, raggrupparli con k-means o visualizzarli con UMAP, senza scrivere alcun codice specifico per il grafo.
Storia
L'idea di applicare Word2Vec a dati strutturati a grafo è stata introdotta da Perozzi, Al-Rfou e Skiena in DeepWalk (KDD 2014), che ha dimostrato che le passeggiate casuali su un grafo sociale potevano sostituire le caratteristiche handcrafted per la classificazione dei nodi. Grover e Leskovec hanno esteso questo in Node2Vec (KDD 2016) introducendo una passeggiata casuale con bias di secondo ordine parametrizzata da p e q, fornendo un controllo esplicito sul compromesso tra esplorazione del vicinato basata sull'omofilia e sull'equivalenza strutturale. Nello stesso periodo Tang et al. hanno proposto LINE (WWW 2015), che apprende gli embedding ottimizzando direttamente gli obiettivi di prossimità di primo e secondo ordine piuttosto che tramite passeggiate casuali, rendendolo adatto per grafi molto grandi. Insieme questi tre metodi hanno stabilito il campo dell'apprendimento della rappresentazione di rete e ispirato architetture successive di reti neurali per grafi.
Quando usarlo
L'embedding di rete è appropriato quando si dispone di un grafo di almeno 50 nodi e sono necessarie caratteristiche vettoriali continue per attività downstream come la classificazione dei nodi, la predizione di link o il clustering dei nodi. Il metodo si adatta sia a grafi non pesati che pesati, e gestisce strutture dirette o non dirette. Scegliere DeepWalk quando una semplice baseline di passeggiata casuale uniforme è sufficiente. Scegliere Node2Vec quando si desidera regolare il bilanciamento tra omofilia ed equivalenza strutturale attraverso i parametri p e q. Se è necessario incorporare nuovi nodi, precedentemente non visti, al momento dell'inferenza senza riaddestramento, preferire un metodo induttivo come GraphSAGE; l'embedding di rete nella sua forma standard è trasduttivo. Il metodo non richiede attributi dei nodi normalmente distribuiti.
Limiti e considerazioni
- Trasduttivo: il modello non può incorporare nodi che non erano presenti durante l'addestramento senza un riaddestramento completo.
- Sensibilità agli iperparametri: la dimensione dell'embedding, la lunghezza della passeggiata, il numero di passeggiate, la dimensione della finestra, p e q influenzano tutti la qualità dell'embedding e richiedono una messa a punto.
- Le passeggiate casuali non catturano la struttura del grafo di ordine superiore (ad es. iperarchi o archi multi-relazionali) senza estensione.
- Le prestazioni degradano su grafi molto piccoli (meno di 50 nodi) dove il corpus di passeggiate è troppo sparso per apprendere statistiche affidabili.
Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.
Punti di forza
- Converte dati relazionali di grafo in vettori a lunghezza fissa compatibili con qualsiasi pipeline di machine learning standard.
- I parametri p e q di Node2Vec consentono all'analista di regolare il bilanciamento tra embedding sensibili alla comunità e sensibili al ruolo.
- I pesi degli archi possono essere incorporati nelle probabilità di passeggiata, catturando la forza della relazione senza passaggi di modellazione aggiuntivi.
- Scala a grafi di grandi dimensioni attraverso un campionamento efficiente di passeggiate casuali e la procedura di addestramento skip-gram.
Applicazioni
- Classificazione dei nodi in reti di citazioni, piattaforme sociali o grafi di interazione biologica.
- Predizione di link — identificazione di archi mancanti o futuri confrontando la similarità degli embedding dei nodi.
- Rilevamento di comunità tramite clustering dei vettori dei nodi con metodi k-means o gerarchici.
- Rilevamento di anomalie — nodi i cui embedding sono outlier nello spazio vettoriale possono rappresentare ruoli strutturali insoliti.
- Sistemi di raccomandazione in cui utenti e articoli sono nodi in un grafo di interazione bipartito o multiplex.
Come funziona
Come funziona
Il processo inizia con un grafo G in cui i nodi sono entità e gli archi rappresentano relazioni. Gli archi possono essere diretti o non diretti e possono trasportare pesi che influenzeranno in seguito la probabilità di attraversamento. Se sono presenti pesi sugli archi, questi sono inclusi nelle probabilità di passeggiata; se assenti, tutti gli archi ricevono peso uguale. In questa fase l'analista sceglie anche la variante dell'algoritmo — DeepWalk per passeggiate casuali uniformi, Node2Vec per passeggiate con bias controllate dai parametri p (ritorno) e q (in-out), o LINE quando la prossimità del vicinato di primo e secondo ordine deve essere appresa separatamente. La scelta tra i regimi di parametri di Node2Vec è guidata dalla proprietà attesa della rete: omofilia (nodi simili si connettono, quindi si preferisce l'esplorazione in ampiezza, q < 1) o equivalenza strutturale (nodi con ruoli simili possono essere distanti, quindi si preferisce l'esplorazione in profondità, p < 1).
Partendo da ciascun nodo, l'algoritmo simula una serie di passeggiate casuali di lunghezza fissa (tipicamente 30 passi) e le ripete molte volte (tipicamente 200 passeggiate per nodo). Ogni passeggiata produce una sequenza di identificatori di nodo analoga a una frase di parole. In DeepWalk il nodo successivo viene scelto uniformemente tra i vicini. In Node2Vec il nodo successivo viene scelto secondo probabilità di transizione con bias p e q: tornare al nodo precedente è penalizzato da 1/p, rimanere alla stessa distanza è mantenuto a 1, e muoversi più lontano è controllato da 1/q. La collezione di tutte le passeggiate forma un corpus di sequenze di nodi che codifica la topologia del grafo.
Il corpus di sequenze di nodi viene inserito in un modello skip-gram (la stessa architettura di Word2Vec). Per ogni nodo in una passeggiata, il modello predice i nodi di contesto circostanti entro una finestra (tipicamente 10 passi). Attraverso la discesa del gradiente stocastico, il modello apprende una rappresentazione vettoriale densa di dimensione fissa — comunemente 64 o 128 — per ogni nodo, in modo tale che i nodi che co-occorrono nelle passeggiate abbiano vettori simili. La dimensione è un iperparametro: dimensioni maggiori catturano più struttura ma aumentano il calcolo e il rischio di overfitting su grafi piccoli.
Una volta addestrato, il modello fornisce un vettore di embedding per nodo. Questi vettori vengono utilizzati come caratteristiche per la classificazione dei nodi (inserendoli in una regressione logistica o in un classificatore neurale), la predizione di link (confrontando i vettori di coppie di nodi candidate), o il rilevamento di comunità (raggruppando i vettori). Gli embedding sono trasduttivi: sono fissi per i nodi visti durante l'addestramento. Se nuovi nodi devono essere incorporati dopo l'addestramento, dovrebbe essere utilizzato un metodo induttivo come GraphSAGE, poiché un modello Node2Vec o DeepWalk standard non può generalizzare a nodi non visti senza riaddestramento.
Errori comuni
- Applicare un modello Node2Vec a nuovi nodi che non erano nel grafo di addestramento — il modello non avrà un vettore per loro; utilizzare un metodo induttivo (ad es. GraphSAGE) quando l'embedding trasduttivo non è accettabile.
- Utilizzare p=1, q=1 di default (equivalente a DeepWalk) senza esaminare se la rete segue un pattern di omofilia o equivalenza strutturale — la messa a punto di p e q sul pattern atteso può migliorare sostanzialmente le prestazioni del task downstream.
- Trattare la dimensione dell'embedding come una costante fissa: su grafi piccoli una dimensione di 64 o 128 può causare overfitting; iniziare con valori più bassi e validare sul task downstream.
- Ignorare il requisito minimo di campionamento: grafi con meno di 50 nodi producono corpus di passeggiate troppo sottili per addestrare embedding affidabili.
Domande frequenti
Qual è la differenza tra DeepWalk, Node2Vec e LINE?
DeepWalk utilizza passeggiate casuali uniformi e il modello skip-gram di Word2Vec — è la baseline più semplice. Node2Vec aggiunge passeggiate casuali con bias controllate da p e q, consentendo all'analista di regolare se la passeggiata esplora come una ricerca in ampiezza (omofilia) o in profondità (equivalenza strutturale). LINE non utilizza affatto passeggiate casuali; ottimizza direttamente gli obiettivi di prossimità di primo e secondo ordine sulla lista degli archi, il che è più scalabile a grafi molto grandi ma sacrifica il segnale del vicinato basato sulle passeggiate.
Come scelgo i parametri p e q in Node2Vec?
p controlla la probabilità di tornare al nodo precedente (p basso = meno backtracking), e q controlla il raggio di esplorazione (q < 1 favorisce l'esplorazione verso l'esterno, q > 1 mantiene la passeggiata vicina alla sorgente). Se ti aspetti che i nodi nella stessa comunità siano simili (omofilia), imposta q < 1 per far vagare la passeggiata verso l'esterno. Se ti aspetti che nodi con lo stesso ruolo strutturale siano simili anche se distanti, imposta p < 1 per incoraggiare l'esplorazione in profondità. Valida entrambi i regimi sul task downstream.
Posso incorporare nuovi nodi dopo l'addestramento senza riaddestrare l'intero modello?
Node2Vec e DeepWalk standard sono trasduttivi: la matrice di embedding copre solo i nodi visti durante l'addestramento. Per la generalizzazione induttiva a nodi nuovi, precedentemente non visti, utilizza un metodo induttivo di rete neurale per grafi come GraphSAGE, che apprende una funzione di aggregazione sui vicinati dei nodi che può essere applicata a qualsiasi nodo al momento dell'inferenza.
Quante dimensioni dovrei usare per l'embedding?
Le scelte più comuni sono 64 e 128, e queste funzionano bene per grafi medi e grandi. Per grafi piccoli (50–200 nodi) inizia con una dimensione inferiore (16 o 32) per evitare l'overfitting, e valuta la qualità dell'embedding misurando le prestazioni del task downstream (ad es. accuratezza della classificazione dei nodi) piuttosto che l'errore di ricostruzione da solo.
Metodi correlati
Fonti
Grover, A. & Leskovec, J. (2016). Node2Vec: Scalable Feature Learning for Networks. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 855-864.
Apri il riferimento DOICopiato.Perozzi, B., Al-Rfou, R., & Skiena, S. (2014). DeepWalk: Online Learning of Social Representations. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 701-710.
Apri il riferimento DOICopiato.