Skip to content
Torna ai risultati

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

Dimensione del carattere

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

1

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).

2

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.

3

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.

4

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

  1. 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 DOI
    Copiato.
  2. 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 DOI
    Copiato.