🧮 Computational Mathematics

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

336 — Graph Laplacian

experto clase 16 de 20 4 horas demostración graph_laplacian

La multiplicidad del autovalor cero del Laplaciano cuenta las componentes conexas.

Fórmulas

L = D − A
autovalores: 0 = λ₁ ≤ λ₂ ≤ … ≤ λₙ
λ₂ > 0 ⟺ el grafo es conexo

Desarrollo

El Laplaciano de un grafo se construye restando la matriz de adyacencia a la matriz diagonal de grados. Pese a su simplicidad, su espectro contiene una cantidad notable de información sobre la estructura, y ese es el objeto de la teoría espectral de grafos.

El autovalor cero está siempre presente, con el vector constante como autovector: es inmediato comprobar que L·1 = 0. Lo interesante es su multiplicidad, que coincide exactamente con el número de componentes conexas. Un grafo conexo tiene un único cero.

El segundo autovalor λ₂ se llama conectividad algebraica, y mide cuán bien conectado está el grafo: cerca de cero significa que hay un cuello de botella y el grafo está casi partido en dos. Su autovector asociado, el vector de Fiedler, indica por dónde cortar, y esa es la base del agrupamiento espectral.

Como L es simétrica y semidefinida positiva, todo el aparato del teorema espectral de la parte 06 se aplica: autovalores reales no negativos y autovectores ortogonales. La versión normalizada D^{−1/2}·L·D^{−1/2} acota los autovalores en [0, 2] y es la que usan las redes convolucionales sobre grafos, con la precaución de tratar los nodos aislados para no dividir por cero.

Ejemplo trabajado

Laplaciano de un grafo de cinco nodos.

5 nodos, 6 aristas
grados: [3, 2, 3, 3, 1]

L = D − A:
  [ 3  −1  −1  −1   0]
  [−1   2  −1   0   0]
  [−1  −1   3  ...   ]
  [ ...                ]

autovalores:
  [0,0 ; 0,82991351 ; 2,68889218 ; 4,0 ; 4,4811943]

multiplicidad de 0: 1  →  grafo conexo             ✓
λ₂ = 0,83 > 0        →  confirma la conexión       ✓

Un λ₂ pequeño indicaría un cuello de botella,
y el vector de Fiedler diría por dónde cortarlo.

Qué calcula el laboratorio

Laplaciano del grafo: espectro y componentes conexas.

python classes/part-16-matematica-de-transformers-modelos-generativos-grafos-y-rl/336-graph-laplacian/lab.py
compmath run 336

Salidas del laboratorio (12)

Muestra de la ejecución real

{
  "nodos": 5,
  "aristas": 6,
  "grados": [
    3.0,
    2.0,
    3.0,
    3.0,
    1.0
  ],
  "matriz_de_adyacencia": [
    [
      0.0,
      1.0,
      1.0,
      1.0,
      0.0
    ],
    [
      1.0,
      0.0,
      1.0,
      0.0,
      0.0
    ],
    [
      1.0,
      1.0,
      0.0,
      1.0,
      0.0
    ],
    [
      1.0,
      0.0,
      1.0,
      0.0,
      1.0
    ],
    [
      0.0,
      0.0,
      0.0,
      1.0,
      0.0
    ]
  ],
  "laplaciano": [
    [
      3.0,
      -1.0,
      -1.0,
      -1.0,
      0.0
    ],
    [
      -1.0,
      2.0,
      -1.0,
      0.0,
      0.0
    ],
    [
      -1.0,
      -1.0,
      3.0,
      -1.0,
      0.0
    ],
    [
      -1.0,
      0.0,
      -1.0,
      3.0,
      -1.0
    ],
    [
      0.0,
      0.0,
      0.0,
      -1.0,
      1.0
    ]
  ],
  "autovalores": [
    0.0,
    0.82991351,
    2.68889218,
    4.0,
    4.4811943
  ]
}

Errores comunes

Dónde se usa

Agrupamiento espectral, redes convolucionales sobre grafos, análisis de redes sociales, partición de mallas y detección de comunidades.

Idea rectora de la parte

La atención es un promedio ponderado por similitud, normalizado con softmax.

Error a evitar

Olvidar la máscara causal en el modelado autoregresivo.

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

← 335 Diffusion models: reverse process 337 Message passing en GNN →