Graph Homomorphism Distortion: A Metric to Distinguish Them All and in the Latent Space Bind Them

Each language version is independently generated for its own context, not a direct translation.

Imagina que tienes dos ciudades. Una es una ciudad real con calles, edificios y gente. La otra es una ciudad hecha de LEGO, pero que se ve exactamente igual que la primera.

En el mundo de la inteligencia artificial que estudia redes (llamadas grafos), los científicos han tenido un problema: sus herramientas eran como inspectores de aduanas muy estrictos. Si las dos ciudades eran idénticas en estructura, decían "¡Son iguales!". Pero si faltaba una sola calle o un edificio estaba un poco torcido, gritaban "¡Son totalmente diferentes!".

El problema es que, en la vida real, dos cosas pueden ser muy similares pero no idénticas. Y las herramientas antiguas no podían decirte cuánto se parecen, solo si eran iguales o no. Además, ignoraban los "colores" de los edificios (las características o datos que tienen los nodos), enfocándose solo en el plano de las calles.

Aquí es donde entra este nuevo trabajo de Martin Carrasco y su equipo. Han creado una nueva herramienta llamada "Distorsión de Homomorfismo de Grafos".

La Analogía: El "Traductor de Mapas"

Imagina que quieres comparar dos mapas de ciudades (Grafo A y Grafo B).

El Viejo Método (WL): Era como intentar encajar dos piezas de rompecabezas. Si encajaban perfectamente, eran iguales. Si no, eran diferentes. No había término medio.
El Nuevo Método (Distorsión de Homomorfismo): Imagina que tienes un traductor mágico que intenta convertir el mapa de la Ciudad A al idioma de la Ciudad B.
- El traductor toma cada edificio de la Ciudad A y busca su "parecido" en la Ciudad B.
- A veces, el edificio de la Ciudad A es un rascacielos azul, y el traductor lo envía a un edificio gris en la Ciudad B. ¡Hay una distorsión! El color cambió.
- A veces, el edificio es un poco más grande o más pequeño. ¡Otra distorsión!

La Distorsión de Homomorfismo mide cuánto "sufrimiento" o cambio tienen que sufrir los edificios (los datos) para que la Ciudad A pueda "hablar" con la Ciudad B.

Si la distorsión es 0, significa que las ciudades son gemelas perfectas (isomórficas).
Si la distorsión es pequeña, significa que son muy parecidas, pero tienen pequeñas diferencias (quizás un color diferente o un edificio un poco más alto).
Si la distorsión es grande, son muy diferentes.

¿Por qué es esto un gran avance?

El papel nos dice tres cosas importantes con analogías sencillas:

Es una regla de oro (Métrica): Antes, no podías decir "estas dos redes son un 80% similares". Ahora, esta herramienta te da un número exacto. Es como pasar de decir "hace calor o hace frío" a tener un termómetro que te dice "hace 25 grados".
Ve más allá de la estructura: Las herramientas viejas solo miraban las calles (la estructura). Esta nueva herramienta mira también los edificios (los datos o características). Es como si, al comparar dos ciudades, no solo contaras las calles, sino que también compararas si los parques tienen el mismo color o si las escuelas tienen el mismo tamaño.
Ayuda a las I.A. a aprender mejor: Cuando entrenas a una Inteligencia Artificial para predecir cosas (como el precio de una casa o la toxicidad de una molécula), darle esta nueva "regla de comparación" es como darle un superpoder. La IA deja de adivinar y empieza a entender las diferencias sutiles. En los experimentos del papel, las I.A. que usaron esta herramienta fueron mucho mejores que las que usaban las herramientas antiguas.

En resumen

Imagina que antes teníamos una lupa que solo veía si dos cosas eran iguales o diferentes. Ahora, hemos creado una gafas de realidad aumentada que nos permite ver cuánto se parecen dos cosas, incluso si tienen pequeños detalles distintos.

Esto permite a los científicos:

Distinguir entre redes que antes parecían idénticas.
Entender mejor cómo funcionan las redes neuronales.
Crear modelos de inteligencia artificial más precisos y inteligentes.

Es como pasar de un mundo en blanco y negro a un mundo en alta definición donde cada pequeño detalle cuenta.

Each language version is independently generated for its own context, not a direct translation.

Aquí presento un resumen técnico detallado del artículo "Graph Homomorphism Distortion: A Metric to Distinguish Them All and in the Latent Space Bind Them" (Distorsión de Homomorfismo de Grafos: Una Métrica para Distinguirlos a Todos y Unirlos en el Espacio Latente), estructurado según los puntos solicitados.

1. El Problema

El aprendizaje de grafos enfrenta una complejidad fundamental derivada de la interacción entre la estructura del grafo y sus características (features) de los nodos.

Limitaciones de las métricas actuales: Las métricas existentes para evaluar la expresividad de las Redes Neuronales de Grafos (GNNs), como la jerarquía de Weisfeiler-Leman (WL), se centran casi exclusivamente en la estructura topológica.
- La prueba WL es binaria (isomorfo o no isomorfo) y no captura "diferencias sutiles" entre grafos.
- Ignora las características de los nodos, lo que impide evaluar la similitud entre grafos que tienen estructuras ligeramente diferentes pero características muy similares (o viceversa).
- Es una propiedad frágil: una sola modificación de arista puede romper la equivalencia, sin medir el grado de cambio.
La brecha: No existe una métrica robusta que cuantifique la similitud entre grafos atribuidos (estructura + características) de manera continua y que sea capaz de distinguir grafos no isomorfos de forma más fina que los tests de isomorfismo tradicionales.

2. Metodología

Los autores proponen una nueva medida llamada Distorsión de Homomorfismo de Grafos (Graph Homomorphism Distortion, $d_{HD}$ ), inspirada en la distancia de Gromov-Hausdorff de la geometría métrica.

Definición Formal

Dado dos grafos atribuidos $G=(V, E, f)$ y $G'=(V', E', f')$ , donde $f$ y $f'$ son funciones que asignan características a los nodos en un espacio normado:

Distorsión de Atributos: Para un homomorfismo $\phi: G \to G'$ , la distorsión se define como la máxima diferencia en las características de los nodos mapeados:
$\text{dis}(\phi) := \max_{v \in V} \|f(v) - f'(\phi(v))\|$
Distorsión de Homomorfismo ( $d_{HD}$ ): Se define como el máximo de las distorsiones mínimas en ambas direcciones (de $G$ a $G'$ y de $G'$ a $G$ ):
$d_{HD}(G, G') := \max \left( \inf_{\phi \in \text{Hom}(G, G')} \text{dis}(\phi), \inf_{\phi' \in \text{Hom}(G', G)} \text{dis}(\phi') \right)$
Nota: Si no existen homomorfismos, la infimum se considera $\infty$ .

Propiedades Teóricas

Pseudo-métrica: $d_{HD}$ satisface las propiedades de no negatividad, simetría y desigualdad triangular.
Completitud: Bajo ciertas condiciones (funciones de atributos inyectivas, invariantes a permutación y dependientes del entorno local), $d_{HD}(G, G') = 0$ si y solo si $G$ e $G'$ son isomorfos.
Invarianza: Es invariante a permutaciones de los nodos.
Continuidad Lipschitz: La distorsión es continua respecto a los cambios en las funciones de atributos.

Codificación y Aproximación

Dado que calcular todos los homomorfismos es un problema NP-completo, los autores proponen:

Codificación HD ( $\Gamma(G)_F$ ): Representar un grafo como un vector de distorsiones hacia una familia de grafos de referencia $F$ (ej. árboles, ciclos).
Completitud por Esperanza: Utilizan técnicas de muestreo aleatorio (inspiradas en Welke et al., 2023) para aproximar la distorsión. Demuestran que si se muestrean suficientes grafos y homomorfismos de una distribución con soporte completo, la codificación resultante es "completa" (puede distinguir cualquier par de grafos no isomorfos) con alta probabilidad.

3. Contribuciones Clave

Nueva Métrica: Introducción de la distorsión de homomorfismo como una métrica (pseudo-métrica) que cuantifica la similitud entre grafos atribuidos considerando tanto estructura como características.
Superioridad sobre WL: Demostración teórica de que $d_{HD}$ es más discriminativa que la prueba 1-WL. Mientras WL produce una métrica discreta (0 o 1), $d_{HD}$ ofrece una medida continua y granular.
Codificación Estructural: Desarrollo de una codificación de grafos basada en $d_{HD}$ que actúa como un sesgo inductivo (inductive bias) para GNNs, mejorando su capacidad predictiva.
Pruebas de Completitud: Pruebas de que, bajo supuestos razonables, esta métrica puede distinguir completamente grafos no isomorfos y subgrafos inducidos, algo que las métricas basadas solo en isomorfismo no logran fácilmente.

4. Resultados Experimentales

Los autores validaron su enfoque en dos escenarios principales:

A. Escenarios sin Aprendizaje (Discriminación)

Dataset: BREC (Benchmark para evaluar la expresividad de GNNs).
Rendimiento: La distorsión de homomorfismo aproximada logró distinguir el 100% de los grafos no isomorfos en clases difíciles (donde 1-WL y 3-WL fallan), superando a métodos basados en homología persistente (PH) y a la prueba 3-WL en varias categorías.
Hallazgo: La elección de la familia de grafos de referencia ( $F$ ) y la función de características ( $f$ ) es crítica. El uso de árboles ( $F^T$ ) mostró un rendimiento superior a los ciclos ( $F^C$ ) en la distinción de grafos complejos.

B. Escenarios de Aprendizaje (Regresión en ZINC-12K)

Tarea: Regresión de propiedades moleculares.
Configuración: Se integró la codificación HD como entrada adicional en modelos GAT, GCN y GIN.
Resultados:
- El uso de la codificación HD por sí sola mejoró el rendimiento (MAE más bajo) en comparación con usar solo conteos de homomorfismos.
- La combinación de Distorsión HD + Conteos de Homomorfismos o Distorsión HD + Conteos de Subgrafos logró el mejor rendimiento en todos los modelos, superando a los métodos state-of-the-art actuales (como Spasm).
- Esto confirma que la distorsión captura información estructural y de características complementaria a los conteos tradicionales.

5. Significado e Impacto

Paradigma de Expresividad: El trabajo desafía el paradigma actual que se basa únicamente en tests de isomorfismo combinatorio (como WL) para medir la expresividad de las GNNs. Propone un enfoque más matizado que integra la geometría de las características.
Puente entre Estructura y Características: Proporciona un marco matemático riguroso para medir cómo las GNNs pueden distinguir grafos cuando tanto la topología como los atributos de los nodos juegan un papel.
Aplicabilidad Práctica: Al ofrecer una codificación que se puede aproximar eficientemente mediante muestreo, la metodología es viable para aplicaciones reales en química computacional y otras áreas donde los grafos tienen atributos complejos.
Futuro: Abre la puerta a nuevas métricas de distancia en espacios latentes de grafos, permitiendo una mejor generalización y comprensión de la similitud estructural más allá de la equivalencia binaria.

En resumen, este artículo presenta una herramienta teórica y práctica que permite "medir" la diferencia entre grafos de forma continua y significativa, superando las limitaciones de las pruebas de isomorfismo tradicionales y mejorando el rendimiento de los modelos de aprendizaje profundo en grafos.