Teoria dei grafi per il machine learning
Nodi, archi, matrice di adiacenza, tipi di grafi, feature dei grafi, rappresentazioni delle reti sociali
Teoria dei grafi per il machine learning è una lezione Learn AI with Python gratuita su CoddyKit. Questa è la lezione 1 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Learn AI with Python, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Learn AI with Python include 4 lezioni in totale.
Che cos'è un grafo
Un grafo modella le entità e le relazioni tra di esse. Formalmente, un grafo è G = (V, E), dove V è l'insieme dei vertici (nodi) ed E è l'insieme degli archi che collegano coppie di nodi. Molti sistemi reali sono naturalmente rappresentabili come grafi.
Nodi e archi
Ogni nodo rappresenta un'entità (un utente, un atomo, una pagina web). Ogni arco rappresenta una relazione (un'amicizia, un legame chimico, un collegamento ipertestuale). Il machine learning sui grafi apprende da questa struttura connettiva, non solo da campioni isolati.
La matrice di adiacenza
La matrice di adiacenza A codifica quali nodi sono collegati. Per n nodi, A è una matrice n per n; A[i][j] = 1 se un arco collega il nodo i al nodo j, altrimenti vale 0.
import numpy as np
# Triangle: 0-1, 1-2, 0-2
A = np.array([
[0, 1, 1],
[1, 0, 1],
[1, 1, 0],
])Caratteristiche dei nodi X
Oltre alla struttura, ogni nodo contiene in genere un vettore di caratteristiche. Affiancati, questi vettori formano la matrice delle caratteristiche X di forma (num_nodes, num_features). In un grafo sociale, una riga potrebbe contenere l'età di un utente, il numero di post e l'anzianità dell'account.
X = np.array([
[25, 120, 3.0], # node 0
[31, 45, 5.5], # node 1
[22, 300, 1.2], # node 2
])Matrice dei gradi
Il grado di un nodo è il numero dei suoi archi. La matrice dei gradi D è diagonale e ogni elemento sulla diagonale è uguale al grado del nodo corrispondente. È il componente fondamentale del laplaciano del grafo.
D = np.diag(A.sum(axis=1))
# Each diagonal entry = number of neighborsIl laplaciano del grafo
Il laplaciano del grafo è definito come L = D - A. Esprime le differenze tra i valori dei nodi collegati ed è fondamentale per la teoria spettrale dei grafi e per molte formulazioni delle GNN.
L = D - A
print(L)Perché il laplaciano è importante
Gli autovalori e gli autovettori del laplaciano rivelano la struttura globale: connettività, gruppi e regolarità. Le convoluzioni sui grafi vengono spesso derivate dal laplaciano, quindi comprendere L = D - A è fondamentale per comprendere le GNN.
Orientati e non orientati
In un grafo non orientato, un arco non ha direzione (come un'amicizia), quindi A è simmetrica. In un grafo orientato, gli archi hanno una direzione (come un follower o una citazione), quindi A può essere asimmetrica: A[i][j] può essere diverso da A[j][i].
# Directed: 0 -> 1 but not 1 -> 0
A_dir = np.array([
[0, 1, 0],
[0, 0, 1],
[0, 0, 0],
])Grafi pesati
Gli archi possono avere pesi che rappresentano intensità o distanza. In tal caso, le voci della matrice di adiacenza sono numeri reali, non soltanto 0 e 1. In una rete stradale, gli archi potrebbero avere come peso il tempo di percorrenza; in un grafo di similarità, la similarità coseno.
Rappresentare gli archi in modo efficiente
Nei grafi sparsi di grandi dimensioni, la matrice di adiacenza spreca memoria perché la maggior parte delle voci è zero. I framework di ML memorizzano invece gli archi come una lista di archi (formato COO): due array che indicano la sorgente e la destinazione di ogni arco. PyTorch Geometric la chiama edge_index.
# Triangle edges as edge_index [2, num_edges]
edge_index = [
[0, 0, 1], # sources
[1, 2, 2], # targets
]Applicazioni del machine learning sui grafi
I grafi sono presenti ovunque:
- Sociali: raccomandazione di amici, rilevamento di comunità
- Molecolari: previsione delle proprietà delle molecole (atomi = nodi, legami = archi)
- Grafi della conoscenza: previsione dei collegamenti tra entità e relazioni
- Web/citazioni: ranking e classificazione
Verifica rapida
Verifichi le Sue conoscenze sulla teoria dei grafi.
Riepilogo
Ha appreso le basi della teoria dei grafi per il ML:
- Un grafo è
G = (V, E)ed è costituito da nodi e archi - La matrice di adiacenza A codifica la connettività; X contiene le caratteristiche dei nodi
- Il laplaciano del grafo è
L = D - A - I grafi possono essere orientati o non orientati, pesati o non pesati
- Le applicazioni comprendono grafi sociali, molecolari e della conoscenza
Impara Python con un tutor IA — gratis
Scrivi ed esegui vero codice nel tuo browser, ricevi aiuto istantaneo da un tutor IA disponibile 24/7, e riprendi da dove hai lasciato sul web o nell'app.
- Corsi
- 53
- Lezioni
- 225
Domande Frequenti
La lezione «Teoria dei grafi per il machine learning» è gratuita?
Sì — il testo completo di «Teoria dei grafi per il machine learning» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Learn AI with Python, passa a CoddyKit PRO. Il corso Learn AI with Python include 4 lezioni in totale.
Cosa imparerò in «Teoria dei grafi per il machine learning»?
Nodi, archi, matrice di adiacenza, tipi di grafi, feature dei grafi, rappresentazioni delle reti sociali Eserciti Learn AI with Python con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Learn AI with Python?
Non è richiesta alcuna esperienza precedente. Learn AI with Python su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 1 di 4.
Quanto tempo richiede la lezione «Teoria dei grafi per il machine learning»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Learn AI with Python?
Sì. Ogni lezione Learn AI with Python include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Teoria dei grafi per il machine learning
- Graph Convolutional Network (GCN)
- Classificazione dei nodi con le GNN
- Predizione dei link e classificazione dei grafi