🧮 Computational Mathematics

Inicio · Parte 16 — Matemática de Transformers, modelos generativos, grafos y RL

337 — Message passing en GNN

experto clase 17 de 20 4 horas demostración message_passing

Una capa de paso de mensajes ve un salto; k capas ven un vecindario de radio k.

Fórmulas

h_v^{(k+1)} = σ(Σ_{u∈N(v)∪{v}} w_{vu}·W·h_u^{(k)})
normalización GCN: D^{−1/2}(A+I)D^{−1/2}
campo receptivo tras k capas: radio k

Desarrollo

El paso de mensajes es el mecanismo central de las redes sobre grafos. En cada capa, cada nodo recoge las representaciones de sus vecinos, las agrega y las combina con la suya para producir una representación nueva. Repetir la operación propaga información cada vez más lejos.

El paralelismo con las convoluciones de la parte 15 es exacto: una capa equivale a un salto, y k capas dan un campo receptivo de radio k. La diferencia es que en una imagen el vecindario es una rejilla regular y en un grafo es arbitrario, con nodos de grado 1 y de grado 1000 en la misma red.

Esa irregularidad obliga a normalizar. Sin ella, un nodo con mil vecinos acumularía una suma con escala completamente distinta a la de un nodo con dos, y las activaciones quedarían descontroladas. La normalización simétrica D^{−1/2}(A+I)D^{−1/2} de las GCN resuelve eso y además añade auto-lazos para que cada nodo conserve su propia información.

La limitación característica es el sobresuavizado: con muchas capas, las representaciones de todos los nodos convergen a algo indistinguible, porque cada una acaba siendo un promedio de casi todo el grafo. Por eso las GNN son típicamente poco profundas —dos o tres capas— al contrario que las CNN, y por eso hay líneas de trabajo enteras dedicadas a permitir GNN profundas.

Ejemplo trabajado

Dos capas de paso de mensajes sobre cinco nodos.

características iniciales:
  [1,0  0,0]  [0,0  1,0]  [1,0  1,0]  [0,5  0,5]  [2,0  −1,0]

tras 1 capa:
  [0,625  0,663675]
  [0,577  0,622008]
  [0,625  0,663675]
  [1,332107  ...]

tras 2 capas:
  [0,812193  0,516758]
  [0,553294  0,590509]
  [0,812193  0,516758]

Los nodos 0 y 2 convergen a lo mismo: tienen
vecindarios equivalentes.

Campo receptivo tras k capas: vecindario de radio k.
Normalización: D^{−1/2}(A+I)D^{−1/2}, como en GCN.

Qué calcula el laboratorio

Message passing: cada capa agrega información de un salto más lejos.

python classes/part-16-matematica-de-transformers-modelos-generativos-grafos-y-rl/337-message-passing-en-gnn/lab.py
compmath run 337

Salidas del laboratorio (10)

Muestra de la ejecución real

{
  "nodos": 5,
  "features_iniciales": [
    [
      1.0,
      0.0
    ],
    [
      0.0,
      1.0
    ],
    [
      1.0,
      1.0
    ],
    [
      0.5,
      0.5
    ],
    [
      2.0,
      -1.0
    ]
  ],
  "tras_1_capa": [
    [
      0.625,
      0.663675
    ],
    [
      0.57735,
      0.622008
    ],
    [
      0.625,
      0.663675
    ],
    [
      1.332107,
      0.021447
    ],
    [
      1.176777,
      0.0
    ]
  ],
  "tras_2_capas": [
    [
      0.812193,
      0.516758
    ],
    [
      0.553294,
      0.590509
    ],
    [
      0.812193,
      0.516758
    ],
    [
      1.06158,
      0.337199
    ],
    [
      1.059359,
      0.007583
    ]
  ],
  "receptivo_tras_k_capas": "vecindario de radio k",
  "normalizacion": "D^{-1/2}(A+I)D^{-1/2} como en GCN"
}

Errores comunes

Dónde se usa

Predicción molecular, sistemas de recomendación sobre grafos, análisis de redes sociales, detección de fraude y simulación física con partículas.

Idea rectora de la parte

La escala 1/√d evita que el producto punto sature la softmax en alta dimensión.

Error a evitar

Confundir temperatura alta con mayor calidad en lugar de mayor entropía.

Conexión con IA

Esta parte es la traducción matemática directa de los papers que definen el estado del arte actual.

Bibliografía de la clase

Archivos de la clase

← 336 Graph Laplacian 338 Bellman equations →