Graph Neural Networks

¿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…

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

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:

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:

Laplaciano del grafo

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

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

Intuitivamente, el Laplaciano actúa como un operador de difusión: multiplicar un vector de señal \( \mathbf{x} \) por \( L \) produce un vector que mide, en cada nodo, la diferencia entre su valor y el promedio de sus vecinos. Cuando \( L\mathbf{x} \approx \mathbf{0} \), la señal es "suave" sobre el grafo — los nodos conectados tienen valores similares. Esta noción de suavidad es exactamente lo que las GNNs explotan al propagar información entre vecinos.

El segundo autovalor más pequeño de \( L \), conocido como la conectividad algebraica (o valor de Fiedler), indica cuán bien conectado está el grafo: un valor cercano a 0 señala la presencia de comunidades débilmente conectadas, lo que tiene implicaciones directas para el diseño de GNNs profundas (ver over-smoothing).

Tipos de grafos

¿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:

Una forma útil de pensar en esta relación es a través del concepto de simetría. Cada tipo de red respeta una simetría distinta del dato: las CNNs asumen invariancia translacional (lo mismo da dónde esté un objeto en la imagen), las RNNs asumen que el orden temporal importa, y las GNNs asumen que el etiquetado de los nodos es arbitrario (invariancia a permutaciones). El framework de Geometric Deep Learning (Bronstein et al., 2021) unifica todas estas arquitecturas bajo un mismo paraguas teórico de simetrías de grupo.

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 \):

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

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:

La idea central es elegante: en lugar de diseñar una operación global sobre el grafo completo, definimos una regla local que cada nodo ejecuta consultando únicamente a sus vecinos directos. Al apilar varias capas de esta regla local, la información fluye gradualmente por todo el grafo — de forma análoga a cómo el campo receptivo crece en una CNN al apilar convoluciones.

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:

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)

Esta fórmula tiene una derivación elegante desde la teoría espectral de grafos. Kipf & Welling partieron de la convolución espectral \( g_\theta \star x = U g_\theta(\Lambda) U^T x \) y aplicaron dos simplificaciones sucesivas: (1) aproximar el filtro \( g_\theta(\Lambda) \) con un polinomio de Chebyshev de primer orden (como en ChebNet), y (2) renormalizar la adyacencia con self-loops para evitar inestabilidades numéricas. El resultado es una operación que, para cada nodo, equivale a promediar las features transformadas de sus vecinos y de sí mismo, ponderado por el grado.

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:

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

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:

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

La intuición detrás de GAT es directa: no todos los amigos te dan el mismo consejo. En una red social, el vecino que trabaja en tu mismo campo es más relevante para recomendarte un artículo que un conocido casual. GAT aprende automáticamente a asignar pesos de importancia a cada vecino mediante un mecanismo de atención similar al de los Transformers (aunque restringido a las aristas del grafo, no global). GATv2 (Brody et al., 2022) corrige una limitación del GAT original: la función de atención original es estática (el ranking de vecinos no depende del nodo consultado), mientras que GATv2 usa una atención verdaderamente dinámica.

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:

GIN: Graph Isomorphism Network

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

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.

¿Por qué GIN es tan importante? Porque proporciona una respuesta teórica precisa a la pregunta: "¿cuánto puede distinguir una GNN?" Xu et al. demostraron que la expresividad de una GNN basada en message passing está acotada superiormente por el test de Weisfeiler-Leman (WL), y que GIN alcanza exactamente ese techo. Esto significa que si dos grafos no pueden ser distinguidos por el test WL de primer orden (1-WL), tampoco podrá distinguirlos ninguna GNN de message passing, independientemente de su profundidad o anchura.

En la práctica, GIN es especialmente útil en tareas de clasificación de grafos (como predicción de propiedades moleculares), donde la expresividad del agregador es crítica para distinguir entre moléculas con topologías similares pero no idénticas.

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

Las CNNs son un caso particular de GNN

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

La conexión CNN ↔ GNN no es solo una analogía pedagógica — tiene consecuencias prácticas. Si modelamos una imagen como un grafo grid y aplicamos una GCN, la operación resultante es matemáticamente equivalente a una convolución 2D con kernel promediador. La diferencia es que la CNN puede asignar pesos distintos a cada posición relativa del kernel (arriba-izquierda ≠ abajo-derecha), mientras que la GNN usa la misma función para todos los vecinos (porque en un grafo general no hay noción de "arriba" o "izquierda"). Esta pérdida de información posicional es el precio que pagan las GNNs por ser invariables a permutaciones — y es exactamente lo que los positional encodings de los Graph Transformers intentan recuperar.

Técnicas de estabilización en GNNs

Tareas fundamentales en grafos

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.

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.

El fenómeno tiene una explicación matemática precisa conectada con la teoría espectral: la multiplicación repetida por la matriz de adyacencia normalizada \( \hat{D}^{-1/2}\hat{A}\hat{D}^{-1/2} \) actúa como un filtro paso-bajo que atenúa las frecuencias altas del Laplaciano del grafo. Tras suficientes capas, solo sobrevive la componente correspondiente al autovalor \( \lambda_1 = 0 \), que es un vector constante — todos los nodos convergen a la misma representación.

Este es un problema central en el diseño de GNNs: queremos suficiente profundidad para captar dependencias de largo alcance, pero no tanta como para destruir la información local. La mayoría de resultados competitivos se obtienen con 2–4 capas. Arquitecturas recientes como GCNII (Chen et al., 2020), que incorpora conexiones residuales con una conexión inicial (\( \alpha \cdot H^{(0)} + (1-\alpha) \cdot H^{(l)} \)), permiten entrenar GNNs de hasta 64 capas sin over-smoothing severo.

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.

El aprendizaje semi-supervisado en grafos explota una hipótesis implícita llamada homofilia: los nodos conectados tienden a pertenecer a la misma clase o tener propiedades similares (amigos en redes sociales suelen compartir intereses, artículos que se citan mutuamente pertenecen al mismo campo). La GNN formaliza esta intuición: al propagar features entre vecinos, los nodos no etiquetados "heredan" información de los etiquetados a través de la estructura del grafo. El resultado es que con solo el 5% de etiquetas se pueden obtener precisiones competitivas — algo impensable en MLPs o CNNs sobre datos tabulares.

Cuando la homofilia no se cumple (grafos heterofílicos, donde nodos conectados tienden a ser diferentes), las GNNs clásicas pierden efectividad. Para estos casos se han desarrollado arquitecturas específicas como H2GCN (Zhu et al., 2020) y LINKX (Lim et al., 2021).

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:

La dualidad espectral-espacial refleja una tensión fundamental en el procesamiento de señales sobre grafos. El enfoque espectral —heredero de la transformada de Fourier clásica— tiene la ventaja de ofrecer un marco teórico riguroso: las frecuencias del grafo (autovectores del Laplaciano) separan patrones suaves (baja frecuencia) de patrones locales abruptos (alta frecuencia). Sin embargo, la descomposición espectral tiene coste \( O(N^3) \) y produce filtros que dependen de la estructura específica del grafo, impidiendo la transferencia a grafos nuevos. El enfoque espacial (message passing) evita ambas limitaciones: opera directamente sobre los vecinos con coste \( O(|E|) \) y generaliza naturalmente a grafos no vistos. La GCN puede entenderse como el punto de encuentro entre ambos mundos: derivada espectralmente pero implementada espacialmente.

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

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:

Modelos generativos de grafos

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

Escalabilidad: GNNs en grafos masivos

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

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:

La motivación es clara: el message passing local limita el flujo de información a los vecinos directos en cada capa, lo que causa problemas como over-smoothing y dificultad para captar dependencias de largo alcance. Los Graph Transformers abordan esto permitiendo atención global entre todos los pares de nodos, pero necesitan inyectar la estructura del grafo de alguna forma (sin ella, el Transformer no distinguiría entre un grafo en estrella y un ciclo). Esto se logra mediante positional encodings estructurales: autovectores del Laplaciano (Dwivedi et al., 2020), random walk probabilities, distancias de camino más corto, o centralidad del nodo.

El trade-off principal es coste computacional: la atención global tiene complejidad \( O(N^2) \) frente al \( O(|E|) \) del message passing. Para grafos con millones de nodos, esto es prohibitivo. Por eso las arquitecturas más exitosas (como GPS) combinan una capa MPNN local con una capa Transformer global en cada bloque, obteniendo lo mejor de ambos mundos: localidad eficiente + contexto global.

Aplicaciones de Graph Neural Networks

Las GNNs han pasado de ser un tema académico de nicho a una tecnología desplegada en producción por las mayores empresas tecnológicas. Su capacidad para operar sobre datos relacionales las hace insustituibles en dominios donde la estructura importa tanto como los atributos. A continuación, las áreas de aplicación más impactantes:

Benchmarks y datasets

Estado del arte: resultados recientes

Frameworks y herramientas

Referencias académicas clave

📄 Papers fundacionales

📄 Papers recientes destacados

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