Analisi di grafi di grandi dimensioni con PageRank

Analisi di grafi di grandi dimensioni con PageRank' -> 'Analisi di grafi grandi con PageRank

La classificazione è un problema importante nell’apprendimento automatico. Dato un insieme di documenti, l’obiettivo è ordinarli in base a determinati criteri. La classificazione è ampiamente utilizzata nei sistemi di recupero delle informazioni per ordinare i risultati di ricerca o nei sistemi di raccomandazione per filtrare i contenuti che potrebbero interessare a un determinato utente.

In base al problema e all’obiettivo specifico, esistono numerosi algoritmi di classificazione. Quello che studieremo in questo articolo si chiama PageRank. Il suo obiettivo principale è classificare un insieme di documenti (pagine web) utilizzando le informazioni sulla loro connettività. Il punteggio assegnato a ciascuna pagina web indica la sua importanza: maggiore è il punteggio, maggiore è l’importanza. L’algoritmo si basa su due assunzioni che esamineremo nella prossima sezione.

Assunzioni

Possiamo definire il termine “importanza” di una pagina web facendo due assunzioni.

L’importanza di una pagina web è alta se molte altre pagine web puntano ad essa.

Immagina di avere un articolo di ricerca popolare e molti altri articoli che vi fanno riferimento utilizzando citazioni o risultati da esso. In primo luogo, ha senso assegnare a questo articolo un’importanza elevata. D’altra parte, se c’è una pagina web sconosciuta senza collegamenti ad essa da altre risorse, sembra logico assegnare una bassa importanza alla pagina.

In realtà, dovremmo anche considerare la qualità dei collegamenti in entrata.

L’importanza di una pagina web è proporzionale all’importanza delle pagine web che puntano ad essa.

Se una pagina viene citata originariamente da un articolo di alta qualità su Wikipedia, allora tale collegamento dovrebbe avere un peso maggiore. Al contrario, quando una risorsa assolutamente sconosciuta punta a un’altra pagina web, non dovrebbe normalmente avere un’importanza elevata.

Esempio di distribuzione dell'importanza ottenuta dall'algoritmo PageRank dal paper ufficiale. I punteggi sono stati normalizzati in modo che sommassero a 100. Il nodo con il valore di 38.4 ha un'importanza così alta a causa di un gran numero di altri nodi che puntano ad esso. D'altra parte, il nodo con un'importanza di 34.3 ha solo un collegamento in entrata, ma la sua importanza è comunque relativamente alta perché il suo singolo collegamento in ingresso proviene da un altro nodo influente. I nodi con un'importanza bassa di 1.6 non hanno collegamenti in entrata.

Definizione formale

Supponiamo che l’importanza di un nodo sia pari alla somma dei pesi dei collegamenti in entrata.

Immagina un nodo i con importanza rᵢ che ha k collegamenti in uscita. Come possiamo determinare il peso di ciascun collegamento? L’approccio più diretto è prendere l’importanza del nodo e dividerla equamente tra tutti i collegamenti in uscita. In questo modo, ciascun collegamento in uscita riceverà il peso di rᵢ / k.

Esempio di calcolo del punteggio di un nodo
Il punteggio di un nodo è pari alla somma dei punteggi dei nodi in entrata diviso per il loro grado totale di uscita.

Dato un grafo di n pagine web, possiamo creare un sistema di n equazioni lineari per trovare i pesi del grafo. Tuttavia, tale sistema può avere un numero infinito di soluzioni. Ecco perché dovremmo aggiungere un’altra vincolo che imponga una soluzione unica. A proposito, PageRank aggiunge la condizione normalizzata che la somma di tutte le importanze dei nodi sia uguale a 1.

Ricerca di una soluzione di un sistema di equazioni lineari che descrive la struttura del grafo

Abbiamo trovato una soluzione ma non è scalabile. Anche con l’eliminazione gaussiana, otteniamo una complessità O(n³). Tenendo presente che il numero di pagine web analizzate n può raggiungere miliardi, dobbiamo trovare un approccio più efficiente.

Prima di tutto, semplifichiamo la notazione. A questo scopo, introduciamo la matrice quadrata di adiacenza G che conterrà i pesi dei collegamenti per ogni coppia di pagine web collegate (se due pagine web non sono collegate, metteremo 0 nell’elemento corrispondente della matrice). Più formalmente:

Definizione di un elemento della matrice G[j][i]

La matrice G è chiamata stocastica perché ciascuna delle sue colonne somma a 1.

Successivamente, definiamo il vettore di ranghi r il cui i-esimo elemento è uguale al rango (importanza) della pagina i. La somma di tutti gli elementi di questo vettore è anch’essa uguale a 1. Il nostro obiettivo finale è trovare i valori di questo vettore r.

Equazione di PageRank

Vediamo cosa succede se moltiplichiamo la matrice G per il vettore r. Basandoci sull’esempio del grafo della sezione precedente, possiamo vedere che il risultato è lo stesso vettore r!

Moltiplicando la matrice G per il vettore r otteniamo nuovamente il vettore r

Perché succede? È solo una coincidenza? Ricordiamo che la i-esima riga della matrice G contiene i pesi di tutti i collegamenti di input alla pagina i. Quando moltiplichiamo l’elemento j-esimo della riga i per r[j], otteniamo effettivamente il componente rj / d[j]out, ovvero l’importanza che fluisce dal nodo j al nodo i. Se non c’è collegamento tra i nodi i e j, allora il componente corrispondente viene impostato a 0. Logicamente, il risultato finale della moltiplicazione della riga i per il vettore r sarà uguale alla somma di tutte le importanze che fluiscono da qualsiasi nodo connesso del grafo al nodo i. Per definizione, questo valore è uguale al rango del nodo i. In generale, possiamo scrivere la seguente equazione:

Equazione di PageRank

Quindi, il nostro obiettivo è trovare un vettore r tale che, moltiplicato per la matrice di input G, rimanga lo stesso.

Autovettori

Possiamo trovare la soluzione all’equazione sopra rivedendo la teoria degli autovettori dell’algebra lineare. Data una matrice A, il vettore v è chiamato autovettore se esiste un numero α che soddisfa la seguente equazione:

Definizione di autovalore

Il numero α è chiamato autovalore. Possiamo notare che l’equazione di PageRank corrisponde all’equazione degli autovalori in cui A = G, v = r e α = 1. Normalmente, ogni matrice quadrata ha diversi autovalori e autovettori, ma poiché la nostra matrice G è stocastica, la teoria sostiene che il suo autovalore più grande sia uguale a 1.

Iterazione di potenza

Uno dei modi più popolari per trovare gli autovettori di una matrice è il metodo dell’iterazione di potenza. Consiste nell’inizializzare un vettore iniziale r con alcuni valori (useremo 1 / n dove n è il numero di pagine web), quindi calcolare costantemente il valore di G * r e assegnare nuovamente questo valore a r. Se in qualsiasi iterazione la distanza tra i vettori r e G * r è inferiore a una certa soglia ε, interrompiamo l’algoritmo poiché è convergente con successo.

Algoritmo di PageRank

Nell’esempio sopra possiamo vedere che impostando ε a 0,0005 l’algoritmo converge correttamente dopo solo 9 iterazioni:

Ovviamente, questo è solo un esempio di prova, ma in pratica questo metodo funziona molto bene anche con un numero maggiore di variabili.

Random walk

Immagina un surfista (passeggero) che si trova in qualsiasi nodo del grafo al tempo t. Indichiamo con p(t) il vettore il cui i-esimo componente corrisponde alla probabilità che al tempo t il surfista si trovi nel nodo i. Il surfista sceglie casualmente (con probabilità uguali) un altro nodo collegato a quello attuale e si sposta lì al tempo t + 1. In definitiva, vogliamo trovare il vettore di distribuzione p(t + 1) al momento t + 1.

Random walk del surfista

Possiamo notare che la probabilità che il surfista appaia nel nodo i al momento t + 1 è la somma delle probabilità (su tutti i nodi collegati a i) che il surfista si sia trovato precedentemente in un nodo adiacente j moltiplicato per la probabilità di spostarsi dal nodo j al nodo i.

  • Conosciamo già la probabilità che il surfista appaia nel nodo j al momento t: p(t)[j].
  • La probabilità di spostarsi dal nodo j al nodo i è uguale a G[j][i].

Sommando queste probabilità, otteniamo il valore per p(t + 1)[i]. Per trovare il valore di p(t + 1) per tutti i nodi del grafo, possiamo scrivere la stessa equazione in forma matriciale:

Questa equazione ha esattamente la stessa forma di quella ottenuta per il PageRank! Ciò significa che questi due problemi hanno la stessa soluzione e interpretazione.

Ad un certo punto, il vettore di distribuzione p(t) convergerà: p(t + 1) = M * p(t) = p(t). Il vettore convergente p(t) in questo caso viene chiamato distribuzione stazionaria. In tutti i momenti successivi, la probabilità di trovarsi in un nodo specifico non cambia.

Il punteggio di PageRank di un nodo corrisponde alla probabilità che il surfista si trovi in questo nodo in futuro facendo un percorso casuale nel grafo.

Convergenza

Il processo descritto di attraversamento del grafo è spesso chiamato “catene di Markov”. Esiste un teorema nella teoria delle catene di Markov che afferma:

In determinate condizioni sulla struttura del grafo, la distribuzione stazionaria è unica e può essere raggiunta con qualsiasi distribuzione di probabilità iniziale al momento t = 0.

Nella sezione seguente approfondiremo le condizioni che devono essere soddisfatte per la convergenza unica. Si scopre che non tutti i grafi possono raggiungere una convergenza unica.

In generale, esistono 2 tipi di casi che vogliamo evitare ad ogni costo.

Dead ends

I nodi che non hanno collegamenti di uscita sono chiamati dead ends. Il problema con questo tipo di nodi è che a causa di essi l’importanza totale fuoriesce dalla rete. Ecco un esempio:

Problema del vicolo cieco. Al momento t = 2, l'importanza fuoriesce. Al momento t = 3, il vettore dei ranghi converge.

Trappola del ragno

Un gruppo di nodi forma una trappola del ragno se non ha collegamenti esterni ad altri nodi al di fuori di questo gruppo. Fondamentalmente, una volta entrati, è impossibile uscire da questo gruppo di nodi. Le trappole del ragno portano ai seguenti problemi:

  • L’algoritmo non converge mai.
  • Il gruppo di nodi che forma una trappola del ragno assorbe tutta l’importanza del grafo. Di conseguenza, questi nodi hanno un’importanza molto alta mentre gli altri nodi hanno un’importanza pari a 0.

Il primo problema è illustrato nella figura seguente:

Problema della trappola del ragno. A partire dal momento t = 0, i ranghi di 1 e 0 alternano infinitamente tra due nodi. Di conseguenza, l'algoritmo non converge mai.

L’assorbimento di importanza è dimostrato nella figura successiva. Anche se potrebbe non sembrare un problema grave nell’esempio di prova sottostante, immaginiamo una rete web con milioni di pagine web in cui diverse di esse formano una trappola del ragno. Di conseguenza, queste pagine distribuiranno tutta l’importanza disponibile mentre l’importanza di tutte le altre pagine web sarà impostata a 0. Ovviamente, questo non è ciò che normalmente vogliamo nella vita reale.

I nodi b e d formano una trappola del ragno. Di conseguenza, al momento t = 18 assorbono già tutta l'importanza mentre gli altri nodi rimangono con importanza zero. A partire da questo momento, l'importanza alterna tra i nodi b e d rendendo l'algoritmo divergente.

Teletrasporti

Una delle soluzioni proposte da Google è quella di aggiungere la seguente condizione prima di ogni spostamento del navigatore:

  • Con probabilità β, spostarsi verso un altro nodo collegato.
  • Con probabilità (1 – β), spostarsi verso un nodo casuale (attraverso unteletrasporto).

Il parametro β è chiamato il fattore di smorzamento. Gli autori dell’algoritmo originale di PageRank raccomandano di scegliere il valore β = 0,85, il che significa che in media dopo 5 transizioni il navigatore salterà casualmente su un altro nodo. L’idea è che se il navigatore cade in una trappola del ragno, dopo un po’ di tempo alla fine uscirà da lì attraverso un teletrasporto.

Il diagramma seguente mostra come i teletrasporti possono aiutare a gestire il problema della trappola del ragno. Se il navigatore entra nel nodo c, rimarrà lì per sempre. Introdurre teletrasporti (linee blu) aiuta ad eliminare questo problema garantendo che dopo un po’ di tempo il navigatore dovrà spostarsi verso un altro nodo casuale.

I teletrasporti (linee blu) eliminano il problema della trappola del ragno

Tuttavia, per i nodi senza uscita, è necessario modificare leggermente l’approccio. Da uno degli esempi precedenti, sappiamo che i vicoli ciechi portano a una fuoriuscita di importanza in un grafo. Questo fenomeno può essere osservato durante il metodo di iterazione di potenza, quando il vettore dei ranghi diventa pieno di zeri a causa di una colonna zero corrispondente nella matrice iniziale G. In definitiva, possiamo fare quanto segue:

Ogni volta che il surfista arriva su un nodo senza uscita, dovrebbe immediatamente passare a un nodo casuale (con una probabilità uguale) del grafo.

In effetti, possiamo modificare la matrice iniziale G per soddisfare questa affermazione: dobbiamo semplicemente sostituire gli zeri con 1 / n al posto di tutti gli elementi delle colonne di tutti i nodi senza uscita della matrice G. L’esempio qui sotto illustra questo principio.

Il nodo c è un nodo senza uscita con una colonna corrispondente di zeri nella matrice G. Aggiungendo n = 3 teletrasporti da c a tutti i nodi del grafo si impone una probabilità uguale p = 1 / 3 di spostarsi da c a qualsiasi nodo. Per tenerne conto, riempiamo la colonna della matrice G corrispondente al nodo c con valori di 1 / 3.

Possiamo notare che dopo l’aggiunta dei teletrasporti la somma di tutte le colonne della matrice è ora uguale a 1. In altre parole, la matrice G diventa stocastica. Questa è una proprietà essenziale che useremo in seguito.

Condizione di convergenza

Esiste un teorema cruciale della teoria delle catene di Markov che definisce la condizione di convergenza.

Per qualsiasi vettore di partenza, la matrice di transizione G converge a un vettore di distribuzione stazionaria positiva e unica r se la catena corrispondente a G è stocastica, aperiodica e irriducibile.

Ricordiamo le ultime tre proprietà di questo teorema e verifichiamo se i teletrasporti introdotti risolvono i problemi sopra descritti.

Una catena G è chiamata stocastica se la somma di ciascuna delle sue colonne è uguale a 1.

Come abbiamo osservato in precedenza, l’aggiunta di teletrasporti ai nodi senza uscita elimina le colonne di zeri nella matrice e fa sì che la somma di tutte le sue colonne sia uguale a 1. La condizione è già soddisfatta.

Una catena G è chiamata periodica se esiste un numero k > 1 tale che la lunghezza del percorso tra ogni coppia di nodi sia sempre un multiplo di k. In caso di aperiodicità, il ritorno avviene a intervalli irregolari. Fondamentalmente, la condizione si riferisce al problema delle trappole per ragni. Poiché abbiamo già affrontato le trappole per ragni aggiungendo i teletrasporti, la catena G è aperiodica.

Una catena G è chiamata irriducibile se la probabilità di passare da un nodo qualsiasi a un altro nodo è sempre maggiore di 0.

Questa condizione implica che esista sempre un collegamento tra due nodi, quindi è impossibile rimanere bloccati su un qualsiasi nodo. In altre parole, la matrice G deve consistere di tutti gli elementi diversi da zero. Vedremo nella prossima sezione come questa condizione sarà soddisfatta collegando tutti i nodi del grafo.

Modificando l’algoritmo

L’algoritmo PageRank proposto da Google prende la matrice iniziale G e la modifica aggiungendo teletrasporti dai nodi senza uscita ad altri nodi. Questo assicura la stocasticità. Per garantire aperiodicità e irriducibilità, aggiunge quindi la condizione descritta prima a ciascun nodo:

  • Con probabilità β, spostarsi su un altro nodo collegato.
  • Con probabilità (1 — β), spostarsi su un nodo casuale.

Matematicamente, ciò si traduce nell’equazione di rank seguente per ogni nodo:

Equazione vettoriale di PageRank

Possiamo trasformare questa equazione nella forma matriciale:

Equazione matriciale di PageRank di Google
La matrice R deve soddisfare le condizioni necessarie per l'esistenza di una distribuzione stazionaria unica r che deve essere trovata.

Disegniamo il grafico modificato e la corrispondente matrice di transizione R da uno degli esempi sopra:

Matrice R composta dalla matrice di collegamento originale G e la matrice di teletrasporto. In questo esempio β = 0.9.

Aumentare l’efficienza

L’unico problema che ci rimane è come memorizzare la matrice di transizione R. Ricordiamo che R è una matrice quadrata di dimensioni n x n, dove n è il numero di pagine web. Attualmente, Google ha più di 25 miliardi di pagine web! La matrice R non contiene zeri, quindi è densa, il che significa che dobbiamo memorizzarla completamente. Supponiamo che ogni elemento della matrice richieda 4 byte per essere memorizzato. La dimensione totale della memoria richiesta per memorizzare la matrice R è pari a (25 * 10⁹)² * 4 (byte) ~ 3 * 10²¹ (byte). Questa è una dimensione di memoria gigantesca! Dobbiamo trovare un altro approccio per ridurre almeno di diverse unità.

In primo luogo, possiamo semplicemente notare che l’aggiunta di teletrasporti è equivalente a ridurre gli elementi della matrice iniziale G del (1 — β)% e distribuirli equamente su ogni nodo. Tenendo presente questo, possiamo trasformare l’equazione matriciale di PageRank in un altro formato:

Trasformazione dell'equazione di PageRank

Guardiamo l’ultima equazione ottenuta. G è la matrice di collegamento iniziale con la maggior parte degli elementi uguali a 0. Perché è così? In realtà, se prendi una qualsiasi pagina web, probabilmente conterrà al massimo una dozzina di collegamenti ad altre pagine web. Tenendo presente che ci sono più di 25 miliardi di pagine web, otteniamo che il numero relativo di collegamenti totali rispetto al numero di pagine web è estremamente piccolo. Pertanto, ci sono molti zeri in G, quindi G è sparso.

La memorizzazione di matrici sparse richiede molta meno memoria rispetto a quelle dense. Supponiamo che ogni pagina web faccia in media link ad altre 40 pagine. Il numero totale di byte richiesto per memorizzare la matrice G diventa ora 25 * 10⁹ * 40 (byte) = 10¹² (byte) = 1 (TB). Risulta che abbiamo bisogno solo di 1 terabyte per memorizzare G. Rispetto a quanto avevamo precedentemente, questa è un’ottima miglioramento!

In effetti, ad ogni iterazione, dobbiamo solo calcolare la moltiplicazione della matrice G per il vettore r, moltiplicarlo per β e aggiungere una costante (1 — β) / n ad ogni elemento del vettore risultante.

Equazione di PageRank risultante

Tieni anche presente che se la catena iniziale G contiene nodi senza uscita, allora la somma del vettore r ad ogni iterazione sarà inferiore a 1. Per affrontare questo problema, è sufficiente rinnormalizzarlo, in modo che tutte le componenti del vettore sommino a 1.

Algoritmo completo

Nella figura sottostante possiamo vedere la versione completa dell’algoritmo di PageRank. Ad ogni iterazione, l’aggiornamento dei ranghi avviene in 2 fasi. La prima fase include solo l’aggiornamento secondo la matrice iniziale G. Poi sommiamo le componenti del vettore di ranghi nella variabile s. In questo modo, il valore di (1 — s) è il valore con cui è stato ridotto il totale del rango di input di un singolo nodo. Per compensare questo, nella seconda fase, teniamo conto dei teletrasporti e li aggiungiamo da un nodo a tutti i nodi con lo stesso valore di (1 — s) / n.

Algoritmo completo di PageRank

Conclusione

In questo articolo, abbiamo esaminato diverse formulazioni dell’algoritmo PageRank per arrivare infine alla sua versione ottimizzata. Nonostante l’esistenza e l’evoluzione di altri metodi per il ranking dei risultati di ricerca, PageRank rimane l’algoritmo più efficiente tra gli altri che operano nel motore di ricerca di Google.

Riferimenti

La struttura logica di questo articolo si basa sulla lezione dell’Università di Stanford sui grafi di grandi dimensioni.

  • Analisi di grandi grafi: Analisi dei collegamenti, PageRank
  • Minerazione di dataset massivi | Jure Leskovec, Anand Rajaraman, Jeff Ullman
  • PageRank: Rimanendo sulle spalle dei giganti

Tutte le immagini, salvo diversa indicazione, sono dell’autore