Phase 01 - Lesson 21

Teoría de Grafos para Aprendizaje Automático

This lesson includes a graded coding exercise that runs in your browser, unlocked with lifetime access.

Los grafos son la estructura de datos de las relaciones. Si tus datos tienen conexiones, necesitas teoría de grafos.

Tipo: Build Lenguaje: Python Prerrequisitos: Fase 1, Lecciones 01-03 (álgebra lineal, matrices) Tiempo: ~90 minutos

Objetivos de Aprendizaje

• Construir una clase de grafo con representaciones en matriz/lista de adyacencia e implementar recorridos BFS y DFS
• Calcular el Laplaciano del grafo y usar sus autovalores para detectar componentes conexas y agrupar nodos
• Implementar una ronda de paso de mensajes al estilo GNN como una multiplicación por matriz de adyacencia normalizada
• Aplicar agrupamiento espectral para particionar un grafo usando el vector de Fiedler

El Problema

Redes sociales, moléculas, bases de conocimiento, redes de citas, mapas de carreteras -- todos son grafos. El ML tradicional trata los datos como tablas planas. Cada fila es independiente. Cada característica es una columna. Pero cuando la estructura de las conexiones importa, las tablas fallan.

Considera una red social. Quieres predecir qué producto comprará un usuario. Su historial de compras importa. Pero el historial de compras de sus amigos importa más. Las conexiones llevan señal.

O considera una molécula. Quieres predecir si se une a una proteína. Los átomos importan, pero lo que realmente importa es cómo están enlazados los átomos entre sí. La estructura es el dato.

Las Redes Neuronales de Grafos (GNN) son el área de más rápido crecimiento en el deep learning. Impulsan el descubrimiento de fármacos, la recomendación social, la detección de fraude y el razonamiento sobre grafos de conocimiento. Toda GNN se construye sobre la misma base: la teoría de grafos básica.

Necesitas cuatro cosas:

1. Una forma de representar grafos como matrices (para poder multiplicarlos)
2. Algoritmos de recorrido para explorar la estructura del grafo
3. El Laplaciano -- la matriz más importante en la teoría espectral de grafos
4. Paso de mensajes -- la operación que hace que las GNN funcionen

El Concepto

Grafos: Nodos y Aristas

Un grafo G = (V, E) consta de vértices (nodos) V y aristas E. Cada arista conecta dos nodos.

Dirigido vs no dirigido. En un grafo no dirigido, la arista (u, v) significa que u conecta con v Y v conecta con u. En un grafo dirigido (digrafo), la arista (u, v) significa que u apunta a v, pero no necesariamente al revés.

Ponderado vs no ponderado. En un grafo no ponderado, las aristas existen o no. En un grafo ponderado, cada arista tiene un peso numérico -- una distancia, un costo, una fuerza.

La Matriz de Adyacencia

La matriz de adyacencia A es la representación central. Para un grafo con n nodos:

A[i][j] = 1    if there is an edge from node i to node j
A[i][j] = 0    otherwise

Para grafos no dirigidos, A es simétrica: A[i][j] = A[j][i]. Para grafos ponderados, A[i][j] = peso de la arista (i, j).

Ejemplo -- un triángulo:

Nodes: 0, 1, 2
Edges: (0,1), (1,2), (0,2)

A = [[0, 1, 1],
     [1, 0, 1],
     [1, 1, 0]]

La matriz de adyacencia es la entrada de toda GNN. Las operaciones matriciales sobre A corresponden a operaciones sobre el grafo.

Grado

El grado de un nodo es el número de aristas conectadas a él. Para grafos dirigidos, tienes grado de entrada (aristas que llegan) y grado de salida (aristas que salen).

La matriz de grado D es diagonal:

D[i][i] = degree of node i
D[i][j] = 0    for i != j

Para el ejemplo del triángulo: D = diag(2, 2, 2) porque cada nodo conecta con otros dos.

El grado te dice sobre la importancia del nodo. Grado alto = nodo hub. La distribución de grados de una red revela su estructura. Las redes sociales siguen leyes de potencia (pocos hubs, muchos nodos hoja). Los grafos aleatorios tienen grados con distribución de Poisson.

BFS y DFS

Los dos algoritmos fundamentales de recorrido de grafos. Necesitas ambos.

Búsqueda en Anchura (BFS): Explora todos los vecinos primero, luego los vecinos de los vecinos. Usa una cola (FIFO).

BFS from node 0:
  Visit 0
  Queue: [1, 2]        (neighbors of 0)
  Visit 1
  Queue: [2, 3]        (add neighbors of 1)
  Visit 2
  Queue: [3]           (neighbors of 2 already visited)
  Visit 3
  Queue: []            (done)

La BFS encuentra los caminos más cortos en grafos no ponderados. La distancia desde el inicio hasta cualquier nodo es igual al nivel de la BFS en el que ese nodo se descubre por primera vez. Por eso la BFS se usa para distancias en número de saltos (hop-count) en redes sociales.

Búsqueda en Profundidad (DFS): Ve lo más profundo posible antes de retroceder. Usa una pila (LIFO) o recursión.

DFS from node 0:
  Visit 0
  Stack: [1, 2]        (neighbors of 0)
  Visit 2               (pop from stack)
  Stack: [1, 3]         (add neighbors of 2)
  Visit 3               (pop from stack)
  Stack: [1]
  Visit 1               (pop from stack)
  Stack: []             (done)

La DFS es útil para:

• Encontrar componentes conexas (ejecuta DFS desde nodos no visitados)
• Detección de ciclos (aristas de retorno en el árbol DFS)
• Ordenamiento topológico (orden inverso de finalización de la DFS)

El Laplaciano del Grafo

L = D - A. La matriz más importante en la teoría espectral de grafos.

Para el triángulo:

D = [[2, 0, 0],    A = [[0, 1, 1],    L = [[2, -1, -1],
     [0, 2, 0],         [1, 0, 1],         [-1, 2, -1],
     [0, 0, 2]]         [1, 1, 0]]         [-1, -1,  2]]

El Laplaciano tiene propiedades notables:

1. L es semidefinida positiva. Todos los autovalores son >= 0.

2. El número de autovalores cero es igual al número de componentes conexas. Un grafo conexo tiene exactamente un autovalor cero. Un grafo con 3 componentes desconectadas tiene tres autovalores cero.

3. El autovalor no nulo más pequeño (valor de Fiedler) mide la conectividad. Un valor de Fiedler grande significa que el grafo está bien conectado. Un valor de Fiedler pequeño significa que el grafo tiene un punto débil -- un cuello de botella.

4. El autovector del valor de Fiedler (vector de Fiedler) revela la mejor división. Los nodos con valores positivos van a un grupo, los nodos con valores negativos van al otro. Esto es el agrupamiento espectral.

graph TD
    subgraph "Graph to Matrices"
        G["Graph G"] --> A["Adjacency Matrix A"]
        G --> D["Degree Matrix D"]
        A --> L["Laplacian L = D - A"]
        D --> L
    end
    subgraph "Spectral Analysis"
        L --> E["Eigenvalues of L"]
        L --> V["Eigenvectors of L"]
        E --> C["Connected components (zeros)"]
        E --> F["Connectivity (Fiedler value)"]
        V --> S["Spectral clustering"]
    end

Propiedades Espectrales

Los autovalores de la matriz de adyacencia y del Laplaciano revelan propiedades estructurales sin ningún recorrido.

El agrupamiento espectral funciona así:

1. Calcula el Laplaciano L
2. Encuentra los k autovectores más pequeños de L (omite el primero, que es todo de unos para grafos conexos)
3. Usa esos autovectores como nuevas coordenadas para cada nodo
4. Ejecuta k-means sobre esas coordenadas

¿Por qué funciona esto? Los autovectores de L codifican las funciones "más suaves" sobre el grafo. Los nodos que están bien conectados obtienen valores de autovector similares. Los nodos separados por un cuello de botella obtienen valores diferentes. Los autovectores separan naturalmente los agrupamientos.

Conexión con la caminata aleatoria. El Laplaciano normalizado se relaciona con las caminatas aleatorias sobre el grafo. La distribución estacionaria de una caminata aleatoria es proporcional al grado del nodo. El tiempo de mezcla (qué tan rápido converge la caminata) depende del gap espectral.

Paso de Mensajes

La operación central de las Redes Neuronales de Grafos. Cada nodo recolecta mensajes de sus vecinos, los agrega y actualiza su propio estado.

h_v^(k+1) = UPDATE(h_v^(k), AGGREGATE({h_u^(k) : u in neighbors(v)}))

En la forma más simple, AGGREGATE = media, y UPDATE = transformación lineal + activación:

h_v^(k+1) = sigma(W * mean({h_u^(k) : u in neighbors(v)}))

Esto es multiplicación de matrices disfrazada. Si H es la matriz de todas las características de los nodos y A es la matriz de adyacencia:

H^(k+1) = sigma(A_norm * H^(k) * W)

donde A_norm es la matriz de adyacencia normalizada (cada fila suma 1).

Una ronda de paso de mensajes permite que cada nodo "vea" a sus vecinos inmediatos. Dos rondas le permiten ver a los vecinos de sus vecinos. K rondas dan a cada nodo información de su vecindario de K saltos.

graph LR
    subgraph "Round 0"
        A0["Node A: [1,0]"]
        B0["Node B: [0,1]"]
        C0["Node C: [1,1]"]
    end
    subgraph "Round 1 (aggregate neighbors)"
        A1["Node A: avg(B,C) = [0.5, 1.0]"]
        B1["Node B: avg(A,C) = [1.0, 0.5]"]
        C1["Node C: avg(A,B) = [0.5, 0.5]"]
    end
    A0 --> A1
    B0 --> A1
    C0 --> A1
    A0 --> B1
    C0 --> B1
    A0 --> C1
    B0 --> C1

Conceptos y Aplicaciones en ML

Build It

Paso 1: Clase de grafo desde cero

class Graph:
    def __init__(self, n_nodes, directed=False):
        self.n = n_nodes
        self.directed = directed
        self.adj = {i: {} for i in range(n_nodes)}

    def add_edge(self, u, v, weight=1.0):
        self.adj[u][v] = weight
        if not self.directed:
            self.adj[v][u] = weight

    def neighbors(self, node):
        return list(self.adj[node].keys())

    def degree(self, node):
        return len(self.adj[node])

    def adjacency_matrix(self):
        import numpy as np
        A = np.zeros((self.n, self.n))
        for u in range(self.n):
            for v, w in self.adj[u].items():
                A[u][v] = w
        return A

    def degree_matrix(self):
        import numpy as np
        D = np.zeros((self.n, self.n))
        for i in range(self.n):
            D[i][i] = self.degree(i)
        return D

    def laplacian(self):
        return self.degree_matrix() - self.adjacency_matrix()

La lista de adyacencia (self.adj) almacena los vecinos de forma eficiente. La conversión a matriz de adyacencia usa numpy porque todas las operaciones espectrales lo necesitan.

Paso 2: BFS y DFS

from collections import deque

def bfs(graph, start):
    visited = set()
    order = []
    distances = {}
    queue = deque([(start, 0)])
    visited.add(start)
    while queue:
        node, dist = queue.popleft()
        order.append(node)
        distances[node] = dist
        for neighbor in graph.neighbors(node):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
    return order, distances


def dfs(graph, start):
    visited = set()
    order = []
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for neighbor in reversed(graph.neighbors(node)):
            if neighbor not in visited:
                stack.append(neighbor)
    return order

La BFS usa un deque (cola de doble extremo) para popleft en O(1). La DFS usa una lista como pila. Ambas visitan cada nodo exactamente una vez -- tiempo O(V + E).

Paso 3: Componentes conexas y autovalores del Laplaciano

def connected_components(graph):
    visited = set()
    components = []
    for node in range(graph.n):
        if node not in visited:
            order, _ = bfs(graph, node)
            visited.update(order)
            components.append(order)
    return components


def laplacian_eigenvalues(graph):
    import numpy as np
    L = graph.laplacian()
    eigenvalues = np.linalg.eigvalsh(L)
    return eigenvalues

eigvalsh es para matrices simétricas -- el Laplaciano siempre es simétrico para grafos no dirigidos. Devuelve los autovalores en orden ascendente. Cuenta los ceros para encontrar el número de componentes conexas.

Paso 4: Agrupamiento espectral

def spectral_clustering(graph, k=2):
    import numpy as np
    L = graph.laplacian()
    eigenvalues, eigenvectors = np.linalg.eigh(L)
    features = eigenvectors[:, 1:k+1]

    labels = np.zeros(graph.n, dtype=int)
    for i in range(graph.n):
        if features[i, 0] >= 0:
            labels[i] = 0
        else:
            labels[i] = 1
    return labels

Para k=2, el signo del vector de Fiedler divide el grafo en dos agrupamientos. Para k>2, ejecutarías k-means sobre los primeros k autovectores (excluyendo el autovector trivial de unos).

Paso 5: Paso de mensajes

def message_passing(graph, features, weight_matrix):
    import numpy as np
    A = graph.adjacency_matrix()
    row_sums = A.sum(axis=1, keepdims=True)
    row_sums[row_sums == 0] = 1
    A_norm = A / row_sums
    aggregated = A_norm @ features
    output = aggregated @ weight_matrix
    return output

Esta es una ronda de paso de mensajes de GNN. Las nuevas características de cada nodo son el promedio ponderado de las características de sus vecinos, transformado por la matriz de pesos. Apila varias rondas para propagar la información más lejos.

Use It

Con networkx y numpy, las mismas operaciones son de una sola línea:

import networkx as nx
import numpy as np

G = nx.karate_club_graph()

A = nx.adjacency_matrix(G).toarray()
L = nx.laplacian_matrix(G).toarray()

eigenvalues = np.linalg.eigvalsh(L.astype(float))
print(f"Smallest eigenvalues: {eigenvalues[:5]}")
print(f"Connected components: {nx.number_connected_components(G)}")

communities = nx.community.greedy_modularity_communities(G)
print(f"Communities found: {len(communities)}")

pr = nx.pagerank(G)
top_nodes = sorted(pr.items(), key=lambda x: x[1], reverse=True)[:5]
print(f"Top 5 PageRank nodes: {top_nodes}")

networkx maneja grafos de cualquier tamaño con backends C optimizados. Úsalo en producción. Usa tu implementación desde cero para entender lo que hace.

Análisis espectral con numpy

import numpy as np

A = np.array([
    [0, 1, 1, 0, 0],
    [1, 0, 1, 0, 0],
    [1, 1, 0, 1, 0],
    [0, 0, 1, 0, 1],
    [0, 0, 0, 1, 0]
])

D = np.diag(A.sum(axis=1))
L = D - A

eigenvalues, eigenvectors = np.linalg.eigh(L)
print(f"Eigenvalues: {np.round(eigenvalues, 4)}")
print(f"Fiedler value: {eigenvalues[1]:.4f}")
print(f"Fiedler vector: {np.round(eigenvectors[:, 1], 4)}")

fiedler = eigenvectors[:, 1]
group_a = np.where(fiedler >= 0)[0]
group_b = np.where(fiedler < 0)[0]
print(f"Cluster A: {group_a}")
print(f"Cluster B: {group_b}")

El vector de Fiedler hace el trabajo pesado. Entradas positivas en un agrupamiento, negativas en el otro. No se necesita optimización iterativa -- solo una descomposición en autovalores.

Ship It

Esta lección produce:

• outputs/skill-graph-analysis.md -- una referencia de skill para analizar datos estructurados en grafo

Conexiones

Las GNN merecen una mención especial. La operación de convolución de grafo en la GCN (Kipf & Welling, 2017) usa la matriz de adyacencia con bucles propios (self-loops) añadidos, A_hat = A + I:

H^(l+1) = sigma(D_hat^(-1/2) * A_hat * D_hat^(-1/2) * H^(l) * W^(l))

donde A_hat = A + I (adyacencia más bucles propios) y D_hat es la matriz de grado de A_hat. Los bucles propios aseguran que cada nodo incluya sus propias características durante la agregación. Esto es exactamente paso de mensajes con normalización simétrica. D_hat^(-1/2) * A_hat * D_hat^(-1/2) es la matriz de adyacencia normalizada. El Laplaciano aparece porque esta normalización está relacionada con L_sym = I - D^(-1/2) * A * D^(-1/2). Entender el Laplaciano significa entender por qué funcionan las GCN.

Ejercicios

1. Implementa PageRank desde cero. Comienza con puntajes uniformes. En cada paso: score(v) = (1-d)/n + d * sum(score(u)/out_degree(u)) para todo u que apunta a v. Usa d=0.85. Ejecuta hasta la convergencia (cambio < 1e-6). Pruébalo en un pequeño grafo web.

2. Encuentra comunidades usando agrupamiento espectral. Crea un grafo con dos agrupamientos claramente separados (por ejemplo, dos cliques conectados por una sola arista). Ejecuta el agrupamiento espectral y verifica que encuentre la división correcta. ¿Qué sucede a medida que agregas más aristas entre agrupamientos?

3. Implementa el algoritmo de Dijkstra para caminos más cortos en grafos ponderados. Compara los resultados con la BFS en el mismo grafo con pesos uniformes.

4. Construye una red de paso de mensajes de 2 capas. Aplica el paso de mensajes dos veces con matrices de pesos diferentes. Muestra que después de 2 rondas, cada nodo tiene información de su vecindario de 2 saltos.

5. Analiza un grafo del mundo real. Usa el grafo del Karate Club (34 nodos, 78 aristas). Calcula la distribución de grados, los autovalores del Laplaciano y el agrupamiento espectral. Compara el resultado del agrupamiento espectral con la división real conocida (ground truth).

Términos Clave

Lectura Adicional

• Kipf & Welling (2017) -- "Semi-Supervised Classification with Graph Convolutional Networks." El artículo que lanzó las GNN modernas. Muestra que las convoluciones espectrales de grafos se simplifican a paso de mensajes.
• Spielman (2012) -- notas de clase "Spectral Graph Theory". La introducción definitiva a los Laplacianos, gaps espectrales y particionamiento de grafos.
• Hamilton (2020) -- "Graph Representation Learning." Libro que cubre las GNN desde los fundamentos hasta las aplicaciones.
• Bronstein et al. (2021) -- "Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges." El artículo del framework unificador.
• Velickovic et al. (2018) -- "Graph Attention Networks." Extiende el paso de mensajes con mecanismos de atención.