📖 Teoría

Graph Neural Networks

De la teoría de grafos a las arquitecturas GNN más modernas: message passing, GCN, GAT, GraphSAGE, GIN, pooling y readout, la CNN como caso especial de GNN, grafos heterogéneos y temporales, Graph Transformers, hardware escalable, y aplicaciones reales con código en PyTorch Geometric y TensorFlow/Spektral.

¿Por qué necesitamos Graph Neural Networks?

Las redes neuronales convencionales (MLPs, CNNs, RNNs) asumen que los datos tienen una estructura regular: cuadrículas de píxeles, secuencias de tokens, vectores de tamaño fijo. Pero una enorme cantidad de datos del mundo real son relacionales: redes sociales, moléculas, grafos de conocimiento, redes de transporte, mallas 3D…

🧬
Moléculas
Átomos = nodos, enlaces = aristas. Predecir propiedades químicas, diseño de fármacos.
👥
Redes sociales
Usuarios = nodos, relaciones = aristas. Detección de comunidades, recomendaciones.
🗺️
Transporte
Intersecciones = nodos, calles = aristas. Predicción de tráfico, rutas óptimas.
📚
Grafos de conocimiento
Entidades = nodos, relaciones = aristas. Búsqueda semántica, Q&A.
🔬
Proteínas
Aminoácidos = nodos, contactos = aristas. Plegamiento, interacciones.
🛒
Recomendación
Usuarios y productos = nodos, interacciones = aristas. Sistemas bipartitos.
💡 Dato clave: Se estima que más del 80% de los datos empresariales tienen una estructura inherentemente relacional. Las GNNs permiten explotar esa estructura en lugar de ignorarla aplanando todo a vectores.

¿Qué es un grafo?

Un grafo \( G = (V, E) \) consiste en un conjunto de nodos (o vértices) \( V \) y un conjunto de aristas (o ejes) \( E \subseteq V \times V \) que representan conexiones entre nodos.

v₁ v₂ v₃ v₄ v₅ G = (V, E) con |V|=5, |E|=6

Representaciones matemáticas de un grafo

Matriz de adyacencia

La matriz de adyacencia \( A \in \{0,1\}^{N \times N} \) codifica la conectividad del grafo:

$$A_{ij} = \begin{cases} 1 & \text{si } (v_i, v_j) \in E \\ 0 & \text{en otro caso} \end{cases}$$

Para grafos no dirigidos, \( A \) es simétrica: \( A = A^T \). Para grafos con pesos, \( A_{ij} = w_{ij} \).

Matriz de grado

La matriz de grado \( D \) es diagonal, donde \( D_{ii} = \text{deg}(v_i) = \sum_j A_{ij} \): el número de vecinos del nodo \( i \).

Matriz de features (atributos)

La matriz de features \( X \in \mathbb{R}^{N \times F} \) contiene un vector de \( F \) atributos para cada nodo:

$$X = \begin{bmatrix} — \mathbf{x}_1^T — \\ — \mathbf{x}_2^T — \\ \vdots \\ — \mathbf{x}_N^T — \end{bmatrix}$$

Laplaciano del grafo

El Laplaciano \( L = D - A \) es fundamental para la teoría espectral de grafos. Su versión normalizada:

$$\hat{L} = I - D^{-1/2} A D^{-1/2}$$

Los autovalores de \( \hat{L} \) revelan propiedades del grafo (conectividad, clustering). Las GNNs espectrales operan en esta base.

📐 Ejemplo concreto

Para el grafo del diagrama anterior (5 nodos, 6 aristas):

$$A = \begin{bmatrix}0&1&0&1&0\\1&0&1&1&0\\0&1&0&0&1\\1&1&0&0&1\\0&0&1&1&0\end{bmatrix} \quad D = \text{diag}(2,3,2,3,2)$$

Tipos de grafos

TipoDescripciónEjemplo
No dirigido Aristas sin dirección: \( (u,v) = (v,u) \). \( A \) simétrica. Redes sociales (amistad), moléculas
Dirigido Aristas con dirección: \( (u,v) \neq (v,u) \). \( A \) no simétrica. Citas académicas, flujo web
Ponderado Aristas con peso \( w_{ij} \in \mathbb{R} \). Distancias en rutas, intensidad de interacción
Bipartito Dos conjuntos de nodos; aristas solo entre conjuntos. Usuarios–productos, autores–papers
Heterogéneo Múltiples tipos de nodos y/o aristas. Knowledge graphs (persona–trabaja_en–empresa)
Dinámico / temporal Estructura cambia en el tiempo. Redes de contacto, transacciones financieras
Hipergrafos Una hiperarista conecta >2 nodos simultáneamente. Co-autoría, reacciones químicas multicomponente

¿Cómo encajan las GNNs con otras redes neuronales?

Las GNNs no reemplazan a las CNNs o RNNs — las generalizan a dominios con estructura irregular:

RedDominioEstructuraInvariancia
MLP Vectores Ninguna (datos tabulares)
CNN Cuadrículas Grid regular (imágenes, audio) Translacional
RNN / Transformer Secuencias Cadena (lineal / atención completa) Temporal
GNN Grafos Irregular, arbitraria Permutacional
🔗 Las CNNs son un caso especial de GNN. Una imagen es un grafo donde cada píxel es un nodo conectado a sus vecinos en una cuadrícula regular. La convolución sobre imágenes es un caso particular de message passing sobre un grafo grid. Cuando el grafo deja de ser regular (moléculas, redes sociales), necesitamos las GNNs generales.
CNN = GNN en grid Vecindario fijo (kernel) generalizar GNN: grafo arbitrario Vecindario variable

Invariancia a permutaciones

Una propiedad fundamental de las GNNs: la salida no debe depender del orden en que se listan los nodos. Si permutamos los nodos del grafo con una matriz de permutación \( P \):

$$f(PAP^T, PX) = Pf(A, X)$$

Esto se llama equivariancia a permutaciones (para tareas de nodos) o invariancia (para tareas de grafo completo, donde el resultado es un escalar). Las GNNs garantizan esta propiedad por diseño, usando funciones de agregación simétricas (sum, mean, max).

🧩 ¿Por qué importa?

El mismo grafo puede representarse numerando los nodos de infinitas maneras. Una red que dé distinto resultado según la numeración no habría aprendido nada real sobre la estructura. La invariancia a permutaciones asegura que la GNN entiende la topología, no los índices.

El paradigma Message Passing

El framework Message Passing Neural Network (MPNN), propuesto por Gilmer et al. (2017), unifica la mayoría de arquitecturas GNN bajo un mismo esquema de tres fases:

1
Message (mensaje): cada nodo \( v \) recibe mensajes de sus vecinos \( u \in \mathcal{N}(v) \):
$$\mathbf{m}_{u \to v}^{(l)} = \phi\left(\mathbf{h}_u^{(l)}, \mathbf{h}_v^{(l)}, \mathbf{e}_{uv}\right)$$
2
Aggregate (agregación): los mensajes se combinan con una función simétrica (invariable a permutaciones):
$$\mathbf{m}_v^{(l)} = \bigoplus_{u \in \mathcal{N}(v)} \mathbf{m}_{u \to v}^{(l)}$$

Donde \( \bigoplus \in \{\text{sum}, \text{mean}, \text{max}\} \).

3
Update (actualización): cada nodo actualiza su representación combinando su estado previo con el mensaje agregado:
$$\mathbf{h}_v^{(l+1)} = \psi\left(\mathbf{h}_v^{(l)}, \mathbf{m}_v^{(l)}\right)$$
v u₁ u₂ u₃ u₄ m₁→v m₂→v m₃→v m₄→v v agrega los mensajes de sus vecinos N(v) = {u₁, u₂, u₃, u₄}
💡 Intuición: cada capa de message passing expande el campo receptivo del nodo en 1 salto. Con \( K \) capas, cada nodo "ve" hasta sus vecinos a distancia \( K \). Es análogo al tamaño del kernel en CNNs: más capas = más contexto.
Gilmer, J. et al. (2017). Neural Message Passing for Quantum Chemistry. ICML.

Graph Convolutional Network (GCN)

La GCN de Kipf & Welling (2017) es la arquitectura GNN más influyente. Simplifica el message passing a una multiplicación matricial elegante:

$$H^{(l+1)} = \sigma\left(\hat{D}^{-1/2}\hat{A}\hat{D}^{-1/2} H^{(l)} W^{(l)}\right)$$

Donde:

  • \( \hat{A} = A + I \) (adyacencia con auto-conexiones)
  • \( \hat{D} \) es la matriz de grado de \( \hat{A} \)
  • \( W^{(l)} \) son los pesos aprendibles de la capa \( l \)
  • \( \sigma \) es una activación (ReLU típicamente)

🔍 Desglose paso a paso

  1. \( \hat{A} = A + I \): añadir self-loops para que cada nodo también se incluya a sí mismo.
  2. \( \hat{D}^{-1/2}\hat{A}\hat{D}^{-1/2} \): normalización simétrica para estabilizar el entrenamiento y ponderar por grado.
  3. \( H^{(l)} W^{(l)} \): transformación lineal de las features.
  4. \( \sigma(\cdot) \): no linealidad.

Para un nodo \( v \) individual, esto equivale a: "promedia las features transformadas de tus vecinos (y de ti mismo)".

Kipf, T.N. & Welling, M. (2017). Semi-Supervised Classification with Graph Convolutional Networks. ICLR.

GraphSAGE

GraphSAGE (SAmple and aggreGatE, Hamilton et al. 2017) aborda la escalabilidad: en lugar de usar todos los vecinos, muestrea un subconjunto fijo y aplica agregadores aprendibles:

$$\mathbf{h}_v^{(l+1)} = \sigma\left(W^{(l)} \cdot \text{CONCAT}\left(\mathbf{h}_v^{(l)},\; \text{AGG}\left(\{\mathbf{h}_u^{(l)} : u \in \mathcal{S}(v)\}\right)\right)\right)$$

Donde \( \mathcal{S}(v) \subseteq \mathcal{N}(v) \) es el muestreo fijo de vecinos. Agregadores: mean, LSTM, max-pool.

  • Inductivo: puede generar embeddings para nodos nunca vistos (GCN es transductivo).
  • Escalable: muestreo fijo → coste computacional controlado, incluso en grafos de millones de nodos.
  • Flexible: distintos agregadores para distintas tareas.
  • Mini-batch: entrenamiento por lotes, compatible con GPUs grandes.
Hamilton, W.L. et al. (2017). Inductive Representation Learning on Large Graphs. NeurIPS.

Graph Attention Network (GAT)

GAT (Veličković et al., 2018) introduce atención al message passing: no todos los vecinos son igual de importantes. Cada arista recibe un peso de atención aprendido:

$$e_{ij} = \text{LeakyReLU}\left(\mathbf{a}^T \left[W\mathbf{h}_i \| W\mathbf{h}_j\right]\right)$$
$$\alpha_{ij} = \frac{\exp(e_{ij})}{\sum_{k \in \mathcal{N}(i)} \exp(e_{ik})} \quad \text{(softmax sobre vecinos)}$$
$$\mathbf{h}_i' = \sigma\left(\sum_{j \in \mathcal{N}(i)} \alpha_{ij} W\mathbf{h}_j\right)$$

Se usa multi-head attention (K cabezas) para estabilizar el entrenamiento, concatenando o promediando las K salidas.

🔬 Widget: Atención en GAT

Simula los pesos de atención de un nodo central con 4 vecinos. Observa cómo la atención se redistribuye según la relevancia.

Veličković, P. et al. (2018). Graph Attention Networks. ICLR.

Funciones de agregación: el corazón de las GNNs

La función de agregación \( \bigoplus \) determina qué información captura la GNN de los vecindarios. Cada elección tiene trade-offs:

AgregadorFórmulaProsContrasUsado en
Sum \( \sum_{u \in \mathcal{N}} \mathbf{h}_u \) Distingue multisets, máxima expresividad Sensible al grado del nodo GIN
Mean \( \frac{1}{|\mathcal{N}|}\sum_{u} \mathbf{h}_u \) Invariante al tamaño del vecindario No distingue distribución vs repetición GCN, GraphSAGE
Max \( \max_{u \in \mathcal{N}} \mathbf{h}_u \) Captura features dominantes Pierde información de multiplicidad GraphSAGE, PointNet
Attention \( \sum_{u} \alpha_{vu} \mathbf{h}_u \) Pesos adaptativos por vecino Más costoso computacionalmente GAT, GATv2
📊 Xu et al. (2019) demostraron en el paper de GIN (Graph Isomorphism Network) que la agregación por suma es la más expresiva: puede distinguir cualquier par de grafos que el test WL (Weisfeiler-Leman) pueda distinguir. Mean y max son estrictamente menos expresivos.

GIN: Graph Isomorphism Network

GIN (Xu et al., 2019) es la GNN con máxima expresividad teórica. Su regla de actualización:

$$\mathbf{h}_v^{(l+1)} = \text{MLP}^{(l)}\left((1 + \epsilon^{(l)}) \cdot \mathbf{h}_v^{(l)} + \sum_{u \in \mathcal{N}(v)} \mathbf{h}_u^{(l)}\right)$$

El parámetro \( \epsilon \) (aprendible o fijo) controla el peso del nodo central respecto a sus vecinos. El MLP proporciona capacidad de aproximación universal.

🏆 Test de Weisfeiler-Leman (WL)

El test WL es un algoritmo clásico para determinar si dos grafos son isomorfos. GIN iguala exactamente su poder: es el techo teórico de las GNNs basadas en message passing de 1er orden. Para superar este límite se necesitan GNNs de orden superior (k-WL).

Xu, K. et al. (2019). How Powerful are Graph Neural Networks? ICLR.

Pooling y Readout: del nodo al grafo

Para tareas de clasificación de grafo completo, necesitamos convertir las representaciones de nodos en una representación única del grafo. Esto se logra con readout (o pooling global):

$$\mathbf{h}_G = \text{READOUT}\left(\{\mathbf{h}_v^{(L)} : v \in V\}\right)$$
MétodoFórmulaTipoNotas
Sum readout \( \sum_v \mathbf{h}_v \) Global Más expresivo (GIN). Sensible al tamaño del grafo.
Mean readout \( \frac{1}{|V|}\sum_v \mathbf{h}_v \) Global Normalizado por tamaño. Pierde info de cardinalidad.
Max readout \( \max_v \mathbf{h}_v \) Global Captura el nodo más "extremo".
Set2Set Atención + LSTM Global aprendido Mayor expresividad, más costoso.
DiffPool Clustering diferenciable Jerárquico Agrupa nodos progresivamente. \(O(N^2)\) memoria.
TopKPool Selección por puntuación Jerárquico Retiene los top-k nodos por score aprendido.
READOUT h_G ∈ ℝᵈ Embedding del grafo N representaciones de nodos → 1 vector de grafo

Las CNNs son un caso particular de GNN

Esta idea es clave para entender la relación entre arquitecturas:

1
Imagen como grafo: cada píxel es un nodo. Los vecinos son los píxeles adyacentes (4-conectividad o 8-conectividad). El grafo resultante es un grid regular.
2
Kernel = pesos compartidos: en una CNN, el kernel asigna pesos fijos a cada posición relativa del vecino. En una GNN sobre grid, cada vecino tiene una posición relativa fija → mismos pesos.
3
Convolución = message passing: "multiplicar features de vecinos por pesos y sumar" es exactamente una ronda de message passing con agregación sum y message function lineal.
PropiedadCNN (grid)GNN (grafo general)
Vecindario Fijo (3×3, 5×5…) Variable (depende del grafo)
Pesos Compartidos por posición Compartidos (misma función para todos los nodos)
Orden de vecinos Definido (arriba, izquierda…) No definido → agregación simétrica
Invariancia Translacional Permutacional
Dominio Euclidiano (grid regular) No euclidiano (topología arbitraria)
🔬 Geometric Deep Learning (Bronstein et al., 2021) formaliza esta idea: CNN, GNN, Transformer y DeepSets son todos casos especiales de redes que respetan simetrías de grupo distintas (translación, permutación, atención global). Las GNNs son la familia más general de estas arquitecturas.

Bronstein, M.M. et al. (2021). Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges. arXiv:2104.13478.

Técnicas de estabilización en GNNs

📏
GraphNorm
Normalización específica para grafos que combina batch norm e instance norm. Adapta el factor de normalización al grafo individual.
⤴️
Skip connections
Conexiones residuales: \( \mathbf{h}^{(l+1)} = \mathbf{h}^{(l+1)} + \mathbf{h}^{(l)} \). Críticas para GNNs profundas (>3 capas) para evitar over-smoothing.
🎲
DropEdge
Eliminar aristas aleatoriamente durante entrenamiento. Regularización que reduce over-smoothing y mejora generalización.
🔄
JK-Net (Jumping Knowledge)
Combina representaciones de todas las capas en la salida final (concat/max/LSTM). Cada nodo elige su campo receptivo óptimo.

Tareas fundamentales en grafos

🔵
Clasificación de nodo
Predecir la clase/etiqueta de cada nodo. Ej: categorizar usuarios en redes sociales, clasificar proteínas por función. Loss: CrossEntropy sobre nodos etiquetados.
🔗
Predicción de enlace
Predecir si existe (o existirá) una arista entre dos nodos. Ej: recomendación de amigos, predicción de interacciones fármaco-diana. Loss: Binary CrossEntropy sobre pares.
📊
Clasificación de grafo
Predecir una propiedad del grafo completo. Ej: toxicidad de molécula, clasificación de compuestos, detección de malware. Loss: CrossEntropy/MSE sobre grafo.
🎯
Regresión en grafo
Predecir un valor continuo para nodos o grafos completos. Ej: energía de una molécula, propiedades físicas de materiales. Loss: MSE / MAE.
NODO ¿Clase de cada nodo? ENLACE ? ¿Existe esta arista? GRAFO → ŷ ¿Propiedad del grafo?

El problema del over-smoothing

A diferencia de las CNNs donde más profundidad = mejor, en las GNNs apilar demasiadas capas causa over-smoothing: las representaciones de todos los nodos convergen al mismo vector, perdiendo toda capacidad discriminativa.

$$\lim_{L \to \infty} \mathbf{h}_v^{(L)} = \mathbf{h}^* \quad \forall v \in V$$

Esto ocurre porque con cada capa, el nodo promedia con más vecinos, y tras \( K \) capas toda la información se difumina en el grafo completo.

🔬 Widget: Over-smoothing en acción

Simula cómo las representaciones de nodos se homogenizan con más capas GCN (mean aggregation).

2
⚠️ En la práctica: la mayoría de GNNs usan solo 2–4 capas. Más capas rara vez ayudan. Soluciones: skip connections, DropEdge, JK-Net, PairNorm, o arquitecturas como GCNII (Chen et al., 2020) que incorporan residuales para >64 capas.

Aprendizaje semi-supervisado en grafos

Uno de los usos más potentes de las GNNs: entrenar con muy pocas etiquetas. La estructura del grafo propaga información de los nodos etiquetados a los no etiquetados.

1
Pocas etiquetas: en Cora (benchmark clásico), se usan solo ~5% de nodos para entrenamiento (140 de 2708).
2
Message passing: la GNN propaga features y gradientes a través del grafo, haciendo que nodos sin etiqueta reciban información de sus vecinos etiquetados.
3
Loss solo en etiquetados: la loss se calcula solo sobre los nodos del conjunto de entrenamiento, pero el forward pass usa todo el grafo.

Código: GNN con PyTorch Geometric

import torch
import torch.nn.functional as F
from torch_geometric.nn import GCNConv
from torch_geometric.datasets import Planetoid

# Cargar dataset Cora (2708 nodos, 10556 aristas, 7 clases)
dataset = Planetoid(root='/tmp/Cora', name='Cora')
data = dataset[0]

class GCN(torch.nn.Module):
    def __init__(self, in_channels, hidden_channels, out_channels):
        super().__init__()
        self.conv1 = GCNConv(in_channels, hidden_channels)
        self.conv2 = GCNConv(hidden_channels, out_channels)

    def forward(self, x, edge_index):
        # Capa 1: features → hidden
        x = self.conv1(x, edge_index)
        x = F.relu(x)
        x = F.dropout(x, p=0.5, training=self.training)
        # Capa 2: hidden → clases
        x = self.conv2(x, edge_index)
        return x

# Inicializar
model = GCN(dataset.num_features, 16, dataset.num_classes)
optimizer = torch.optim.Adam(model.parameters(), lr=0.01, weight_decay=5e-4)

# Entrenamiento
def train():
    model.train()
    optimizer.zero_grad()
    out = model(data.x, data.edge_index)
    # Loss SOLO en nodos de entrenamiento
    loss = F.cross_entropy(out[data.train_mask], data.y[data.train_mask])
    loss.backward()
    optimizer.step()
    return loss.item()

# Evaluación
@torch.no_grad()
def test():
    model.eval()
    out = model(data.x, data.edge_index)
    pred = out.argmax(dim=1)
    acc = (pred[data.test_mask] == data.y[data.test_mask]).float().mean()
    return acc.item()

for epoch in range(200):
    loss = train()
    if epoch % 50 == 0:
        acc = test()
        print(f'Epoch {epoch:3d} | Loss: {loss:.4f} | Test Acc: {acc:.4f}')

# Resultado típico: ~81% accuracy con solo 2 capas GCN
from torch_geometric.nn import GATConv

class GAT(torch.nn.Module):
    def __init__(self, in_channels, hidden_channels, out_channels, heads=8):
        super().__init__()
        # Multi-head attention: 8 cabezas × hidden → 8·hidden
        self.conv1 = GATConv(in_channels, hidden_channels, heads=heads,
                             dropout=0.6)
        # Última capa: 1 cabeza (output)
        self.conv2 = GATConv(hidden_channels * heads, out_channels,
                             heads=1, concat=False, dropout=0.6)

    def forward(self, x, edge_index):
        x = F.dropout(x, p=0.6, training=self.training)
        x = F.elu(self.conv1(x, edge_index))
        x = F.dropout(x, p=0.6, training=self.training)
        x = self.conv2(x, edge_index)
        return x

model = GAT(dataset.num_features, 8, dataset.num_classes, heads=8)
# GAT alcanza ~83% en Cora, ligeramente mejor que GCN
from torch_geometric.nn import GINConv, global_add_pool
from torch_geometric.datasets import TUDataset
from torch_geometric.loader import DataLoader
import torch.nn as nn

# Dataset molecular MUTAG (188 moléculas, 2 clases)
dataset = TUDataset(root='/tmp/MUTAG', name='MUTAG')
loader = DataLoader(dataset, batch_size=32, shuffle=True)

class GIN(torch.nn.Module):
    def __init__(self, in_dim, hidden_dim, out_dim):
        super().__init__()
        # GIN usa MLPs como función de actualización
        nn1 = nn.Sequential(nn.Linear(in_dim, hidden_dim), nn.ReLU(),
                            nn.Linear(hidden_dim, hidden_dim))
        nn2 = nn.Sequential(nn.Linear(hidden_dim, hidden_dim), nn.ReLU(),
                            nn.Linear(hidden_dim, hidden_dim))
        self.conv1 = GINConv(nn1)
        self.conv2 = GINConv(nn2)
        self.classifier = nn.Linear(hidden_dim, out_dim)

    def forward(self, x, edge_index, batch):
        # Message passing
        x = F.relu(self.conv1(x, edge_index))
        x = F.relu(self.conv2(x, edge_index))
        # Readout: sum pooling (GIN recomienda sum)
        x = global_add_pool(x, batch)
        # Clasificación del grafo
        return self.classifier(x)

model = GIN(dataset.num_features, 64, dataset.num_classes)
optimizer = torch.optim.Adam(model.parameters(), lr=0.01)

for epoch in range(50):
    model.train()
    for batch in loader:
        optimizer.zero_grad()
        out = model(batch.x, batch.edge_index, batch.batch)
        loss = F.cross_entropy(out, batch.y)
        loss.backward()
        optimizer.step()

Código: GNN con TensorFlow / Spektral

import numpy as np
import tensorflow as tf
from spektral.datasets import Citation
from spektral.layers import GCNConv
from spektral.transforms import AdjToSpTensor, LayerPreprocess

# Cargar Cora
dataset = Citation('cora', transforms=[LayerPreprocess(GCNConv),
                                        AdjToSpTensor()])
graph = dataset[0]

# graph.x: (2708, 1433) features
# graph.a: (2708, 2708) adjacency (sparse)
# graph.y: (2708, 7) one-hot labels

class GCNModel(tf.keras.Model):
    def __init__(self, n_hidden, n_classes):
        super().__init__()
        self.conv1 = GCNConv(n_hidden, activation='relu')
        self.dropout = tf.keras.layers.Dropout(0.5)
        self.conv2 = GCNConv(n_classes, activation='softmax')

    def call(self, inputs, training=False):
        x, a = inputs
        x = self.conv1([x, a])
        x = self.dropout(x, training=training)
        x = self.conv2([x, a])
        return x

model = GCNModel(16, dataset.n_labels)
model.compile(
    optimizer=tf.keras.optimizers.Adam(learning_rate=0.01),
    loss='categorical_crossentropy',
    weighted_metrics=['accuracy']
)

# Crear máscaras de train/val/test
# (Cora split estándar: 140 train, 500 val, 1000 test)
mask_tr = dataset.mask_tr
mask_va = dataset.mask_va
mask_te = dataset.mask_te

# Entrenamiento
# Spektral soporta modo "single" (grafo completo en memoria)
model.fit(
    [graph.x, graph.a],
    graph.y,
    sample_weight=mask_tr.astype(float),
    validation_data=([graph.x, graph.a], graph.y, mask_va.astype(float)),
    epochs=200,
    batch_size=2708,  # grafo completo
    verbose=0
)

# Evaluación
loss, acc = model.evaluate(
    [graph.x, graph.a], graph.y,
    sample_weight=mask_te.astype(float)
)
print(f"Test accuracy: {acc:.4f}")
import tensorflow as tf
import numpy as np

class GraphConvLayer(tf.keras.layers.Layer):
    """Capa GCN implementada desde cero."""

    def __init__(self, output_dim, activation='relu', **kwargs):
        super().__init__(**kwargs)
        self.output_dim = output_dim
        self.activation = tf.keras.activations.get(activation)

    def build(self, input_shape):
        # input_shape[0] = (N, F_in) features
        f_in = input_shape[0][-1]
        self.W = self.add_weight('W', shape=(f_in, self.output_dim),
                                 initializer='glorot_uniform')
        self.b = self.add_weight('b', shape=(self.output_dim,),
                                 initializer='zeros')

    def call(self, inputs):
        x, adj_norm = inputs  # x: (N, F), adj_norm: (N, N)
        # 1. Transformación lineal
        h = tf.matmul(x, self.W)
        # 2. Agregación (multiplicación por adyacencia normalizada)
        h = tf.matmul(adj_norm, h)
        # 3. Bias + activación
        return self.activation(h + self.b)

# Crear grafo ejemplo (5 nodos)
N, F_in, F_hidden, n_classes = 5, 3, 8, 2
A = np.array([[0,1,0,1,0],[1,0,1,0,0],[0,1,0,1,1],
              [1,0,1,0,0],[0,0,1,0,0]], dtype=np.float32)
X = np.random.randn(N, F_in).astype(np.float32)

# Normalización: D^{-1/2} (A+I) D^{-1/2}
A_hat = A + np.eye(N, dtype=np.float32)
D_hat = np.diag(A_hat.sum(axis=1) ** -0.5)
A_norm = D_hat @ A_hat @ D_hat

# Modelo
x_in = tf.keras.Input(shape=(F_in,))
a_in = tf.keras.Input(shape=(N,))
h = GraphConvLayer(F_hidden)([x_in, a_in])
h = GraphConvLayer(n_classes, activation='softmax')([h, a_in])
model = tf.keras.Model(inputs=[x_in, a_in], outputs=h)

out = model([X, A_norm])
print(f"Output shape: {out.shape}")  # (5, 2) — 1 predicción por nodo

GNNs espectrales vs espaciales

Las GNNs se dividen en dos familias teóricas según cómo definen la "convolución" sobre grafos:

AspectoEspectralesEspaciales
Base teórica Teoría espectral de grafos, autovalores del Laplaciano Agregación directa de vecinos (message passing)
Filtro \( g_\theta(\Lambda) \) en dominio de frecuencias \( \phi(\mathbf{h}_u, \mathbf{h}_v) \) en dominio espacial
Invariancia Depende del grafo (autovectores propios) Generaliza a grafos distintos
Coste \( O(N^3) \) para eigendecomposición \( O(|E|) \) por capa
Modelos clave SpectralCNN, ChebNet GCN, GAT, GraphSAGE, GIN, MPNN

La convolución en el dominio de Fourier del grafo utiliza los autovectores \( U \) del Laplaciano normalizado \( \hat{L} = U\Lambda U^T \):

$$x *_G g = U \cdot g_\theta(\Lambda) \cdot U^T x$$

ChebNet (Defferrard et al., 2016) evita la eigendecomposición usando polinomios de Chebyshev \( T_k \):

$$g_\theta(\hat{L}) = \sum_{k=0}^{K} \theta_k T_k(\tilde{L})$$

GCN es una simplificación de ChebNet con \( K=1 \) y renormalización — por eso funciona como filtro lineal localizado.

Defferrard, M. et al. (2016). Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering. NeurIPS.

GNNs en grafos heterogéneos

Un grafo heterogéneo tiene múltiples tipos de nodos y/o aristas. Ejemplo: un knowledge graph con entidades (persona, empresa, producto) y relaciones (trabaja_en, compra, fabrica).

🏗️
R-GCN
Relational GCN (Schlichtkrull et al., 2018): pesos distintos \( W_r \) para cada tipo de relación \( r \). El message passing se hace por tipo de arista.
🎭
HAN
Heterogeneous Attention Network (Wang et al., 2019): usa meta-paths (caminos semánticos) y atención jerárquica (nodo-nivel + semántica-nivel).
🔀
HGT
Heterogeneous Graph Transformer (Hu et al., 2020): atención multi-cabeza dependiente del tipo. Escalable a grafos académicos y de producción.

GNNs temporales / dinámicas

Muchos grafos del mundo real evolucionan en el tiempo: nuevos nodos, aristas que aparecen y desaparecen, features que cambian. Las GNNs temporales combinan capas de grafo con modelado temporal:

EnfoqueIdeaModelos
Discrete-time Secuencia de snapshots: \( G_1, G_2, \ldots, G_T \). GNN + RNN. DCRNN, EvolveGCN, GCRN
Continuous-time Eventos con timestamp. Neural ODE sobre grafos. TGN, TGAT, DyRep
Spatio-temporal Grafos con features que varían en el tiempo (tráfico, clima). STGCN, ASTGCN, DSTGNN
🚦 Caso estrella: predicción de tráfico. Cada intersección es un nodo, las calles son aristas. Las features (flujo de vehículos) varían con el tiempo. STGCN y variantes son estado del arte en Google Maps, Uber, y sistemas de navegación.

Modelos generativos de grafos

Generar nuevos grafos realistas es clave para el diseño de fármacos y nuevos materiales:

🔬
GraphVAE
Variational Autoencoder para grafos. Encoder GNN → latent z → Decoder que genera adyacencia y features. Genera moléculas válidas.
🌊
Graph Normalizing Flows
GraphAF, GraphDF: generan grafos nodo por nodo con flujos normalizadores. Garantizan invertibilidad y densidad exacta.
💊
Graph Diffusion
DiGress, GDSS: modelos de difusión sobre grafos. Estado del arte en generación molecular (2023-2024). Añaden ruido a la estructura del grafo y aprenden a denoisear.

Escalabilidad: GNNs en grafos masivos

Los grafos del mundo real pueden tener miles de millones de nodos (Facebook, Google Knowledge Graph). Estrategias:

TécnicaIdeaImplementaciones
Mini-batch sampling Muestrear subgrafos/vecinos por lote. GraphSAGE, ClusterGCN, GraphSAINT
Precomputation Precomputar propagación, entrenar solo MLP. SGC (Simplified GCN), SIGN
Graph partitioning Dividir grafo en clusters, procesar en paralelo. ClusterGCN, DistDGL
Distributed training Múltiples GPUs/máquinas con comunicación. DistDGL, AliGraph, PinSage
📌 PinSage (Ying et al., 2018, Pinterest): GNN productiva a escala con 3 mil millones de nodos y 18 mil millones de aristas. Genera embeddings para recomendación de imágenes. Usa random walk sampling + importance pooling.

Ying, R. et al. (2018). Graph Convolutional Neural Networks for Web-Scale Recommender Systems. KDD.

Graph Transformers

Los Graph Transformers combinan la arquitectura Transformer con información estructural del grafo. A diferencia de las GNNs clásicas (que solo ven vecinos locales), los Graph Transformers pueden atender a cualquier nodo del grafo:

Graphormer
Microsoft (Ying et al., 2021). Codifica estructura del grafo con positional encodings basados en distancia y centralidad. Ganó el OGB-LSC challenge (predicción de propiedades moleculares).
🔮
GPS (General Powerful Scalable)
Rampášek et al. (2022). Combina MPNN local + Transformer global en cada capa. Framework unificador para Graph Transformers.
🧬
TokenGT
Kim et al. (2022). Trata los nodos y aristas como tokens y aplica un Transformer estándar. Simple y sorprendentemente efectivo.

🤔 ¿GNN o Graph Transformer?

Las GNNs clásicas (GCN, GAT) son más eficientes (\( O(|E|) \) por capa) pero limitadas a información local. Los Graph Transformers pueden capturar dependencias globales (\( O(N^2) \)) pero son más costosos. En la práctica, los enfoques híbridos (GPS) combinan lo mejor de ambos.

Aplicaciones de Graph Neural Networks

💊
Drug Discovery
Predecir propiedades moleculares, toxicidad, actividad biológica. Diseño de novo de fármacos con modelos generativos de grafos. Usado en: DeepMind (AlphaFold 2), Atomwise, Insilico Medicine.
🧬
Biología estructural
AlphaFold 2 usa un grafo de residuos con atención para predecir estructuras 3D de proteínas. Revolución en biología computacional (Nature, 2021).
🛒
Sistemas de recomendación
Pinterest (PinSage): recomendación a escala de miles de millones. Uber Eats: ranking de restaurantes. Amazon: productos complementarios.
🔒
Detección de fraude
Modelar transacciones como grafo (cuentas = nodos, transferencias = aristas). Detectar patrones de lavado de dinero, cuentas falsas. Usado en: PayPal, Alibaba, American Express.
🚦
Predicción de tráfico
Google Maps usa GNNs spatio-temporales para predecir tiempos de viaje. Red de carreteras como grafo + features temporales de flujo vehicular.
⚛️
Ciencia de materiales
Predecir propiedades de cristales y materiales (bandgap, estabilidad). Google DeepMind GNoME: descubrió 2.2M de nuevos cristales estables (Nature, 2023).
🗣️
NLP y Knowledge Graphs
Razonamiento sobre grafos de conocimiento. Integración con LLMs para respuesta a preguntas con hechos verificables. Link prediction para completar knowledge graphs.
🎮
Física y simulación
GNS (Graph Network Simulator) de DeepMind: simular fluidos, partículas y cuerpos rígidos con GNNs. Hasta 10000× más rápido que simuladores clásicos.

Benchmarks y datasets

DatasetTareaNodosAristasClasesDominio
CoraNodo2.7K10.6K7Citas académicas
CiteSeerNodo3.3K9.1K6Citas académicas
PubMedNodo19.7K88.7K3Artículos médicos
ogbn-arxivNodo169K1.2M40Artículos arXiv
ogbn-productsNodo2.4M61.9M47Productos Amazon
MUTAGGrafo~18/grafo~20/grafo2Moléculas (mutagénicas)
QM9Regresión grafo~18/mol~19/mol12 propsPropiedades cuánticas
ZINCRegresión grafo~23/mol~25/mol1Penalized logP
ogbg-molhivGrafo~26/mol~28/mol2Actividad anti-HIV

📊 Open Graph Benchmark (OGB)

OGB (ogb.stanford.edu) es el benchmark estándar actual para evaluar GNNs. Incluye datasets realistas a escala, splits estandarizados, y leaderboards. Creado por el grupo de Jure Leskovec (Stanford).

Estado del arte: resultados recientes

DatasetMétodoMétricaResultadoAño
CoraGAT + JK-NetAccuracy~85%2022
ogbn-arxivGCNII + DropEdgeAccuracy~73%2023
ogbn-productsGraphSAINT + GATAccuracy~82%2023
ZINCGPS (MPNN + Transformer)MAE0.0592022
QM9GraphormerMAE avgSOTA2022
ogbg-molhivGIN + virtual nodeROC-AUC~80%2022
PCQM4Mv2Graphormer-v2MAE0.08642022

Frameworks y herramientas

📦
PyG (PyTorch Geometric)
github.com/pyg-team/pytorch_geometric
El framework más popular. 100+ capas GNN, >60 datasets, transformaciones, mini-batching, distributed training. +21K ⭐
📦
DGL (Deep Graph Library)
github.com/dmlc/dgl
Multi-backend (PyTorch, TF, MXNet). Excelente para grafos masivos y entrenamiento distribuido. Backed by AWS. +13K ⭐
📦
Spektral
github.com/danielegrattarola/spektral
GNNs con TF/Keras. API limpia, buena para prototyping. +2.4K ⭐
📦
JAX-based: jraph / e3nn-jax
github.com/google-deepmind/jraph
GNNs en JAX (Google DeepMind). Compilación JIT, vectorización. e3nn-jax para GNNs equivariantes (simetrías 3D).
📦
NetworkX + igraph
networkx.org / igraph.org
No son frameworks de ML, pero esenciales para crear, manipular y visualizar grafos. Preprocesamiento antes de GNNs.
📦
OGB (Open Graph Benchmark)
ogb.stanford.edu
Datasets + evaluación estandarizada. Leaderboards públicos. Integración nativa con PyG y DGL.

Referencias académicas clave

📄 Papers fundacionales

PaperAutoresAñoContribución
The Graph Neural Network Model Scarselli, F. et al. 2009 Primera formalización del concepto de GNN.
Spectral Networks and Locally Connected Networks on Graphs Bruna, J. et al. 2014 Primeras convoluciones espectrales en grafos.
Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering Defferrard, M. et al. 2016 ChebNet: filtros de Chebyshev eficientes.
Semi-Supervised Classification with GCNs Kipf, T.N. & Welling, M. 2017 GCN: la arquitectura GNN más influyente.
Neural Message Passing for Quantum Chemistry Gilmer, J. et al. 2017 Framework MPNN unificador.
Inductive Representation Learning on Large Graphs Hamilton, W.L. et al. 2017 GraphSAGE: sampling inductivo escalable.
Graph Attention Networks Veličković, P. et al. 2018 GAT: atención en grafos.
How Powerful are Graph Neural Networks? Xu, K. et al. 2019 GIN: análisis teórico de expresividad, conexión con test WL.

📄 Papers recientes destacados

PaperAutoresAñoContribución
Geometric Deep Learning: Grids, Groups, Graphs Bronstein, M.M. et al. 2021 Marco teórico unificador (CNN, GNN, Transformer como simetrías).
Do Transformers Really Perform Bad for Graph Representation? Ying, C. et al. 2021 Graphormer: Graph Transformer SOTA.
Recipe for a General, Powerful, Scalable Graph Transformer Rampášek, L. et al. 2022 GPS: MPNN + Transformer unificado.
Highly accurate protein structure prediction with AlphaFold Jumper, J. et al. 2021 AlphaFold 2: GNN-like attention para plegamiento de proteínas.
Scaling deep learning for materials discovery (GNoME) Merchant, A. et al. 2023 GNNs para descubrir 2.2M de nuevos cristales estables.

📚 Recursos de aprendizaje

  • CS224W (Stanford, Jure Leskovec): web.stanford.edu/class/cs224w — El curso de referencia sobre GNNs y machine learning en grafos.
  • Geometric Deep Learning course (Bronstein, Veličković): geometricdeeplearning.com — Del paper al libro/curso.
  • PyG tutorials: pytorch-geometric.readthedocs.io/en/latest/get_started/colabs.html
  • DGL tutorials: docs.dgl.ai/tutorials/blitz/index.html
  • Distill.pub: "A Gentle Introduction to Graph Neural Networks" — visualizaciones interactivas excelentes.
  • Libro: Hamilton, W.L. (2020). Graph Representation Learning. Morgan & Claypool.