📊 statistics

$k$ -Nearest Neighbors in Gromov--Wasserstein Space

Este artículo implementa la clasificación de $k$ -vecinos más cercanos utilizando las distancias de Gromov--Wasserstein y de Gromov--Wasserstein fusionado para comparar grafos y grafos con atributos de nodos, respectivamente, y demuestra la consistencia universal de estos clasificadores al tiempo que exhibe su sólido desempeño empírico a través de múltiples conjuntos de datos.

Autores originales: Kaitlyn Hohmeier, Nicolas Fraiman, Caroline Moosmueller

Publicado 2026-06-10

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Kaitlyn Hohmeier, Nicolas Fraiman, Caroline Moosmueller

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que estás intentando clasificar una pila enorme de objetos diferentes. Algunos son formas simples, otros son redes complejas como mapas de metro o círculos sociales. Tu objetivo es determinar a qué categoría pertenece un objeto nuevo y no visto observando los objetos que ya conoces. Este es el trabajo de un clasificador de $k$ -Vecinos Más Cercanos ( $k$ -NN).

Piensa en el $k$ -NN como un "concurso de popularidad" entre tus vecinos. Si sueltas un objeto nuevo en una habitación llena de objetos conocidos, buscas a los $k$ más cercanos. Si la mayoría de esos vecinos son "gatos", supones que el nuevo objeto también es un gato.

El problema es: ¿Cómo se mide la "cercanía" cuando los objetos son redes complejas (grafos) que no tienen un tamaño o forma estándar? No puedes simplemente medir la distancia entre dos puntos en un mapa.

Este artículo presenta una nueva y astuta forma de medir esa distancia utilizando algo llamado Gromov–Wasserstein (GW) y Gromov–Wasserstein Fusionado (fGW). Aquí está el desglose en términos sencillos:

1. El Problema: Comparar manzanas con naranjas (y naranjas con aviones)

Normalmente, para comparar dos cosas, estas deben tener el mismo tamaño. Si quieres comparar dos grafos (redes de puntos y líneas), los métodos tradicionales a menudo los obligan a tener el mismo tamaño o los convierten en una lista única de números (un "embedding"). Esto es como intentar comparar un pequeño árbol genealógico con un enorme organigrama corporativo comprimiéndolos ambos en una misma caja diminuta. Se pierde información.

2. La Solución: La regla "cambia-formas"

Los autores utilizan una herramienta matemática llamada distancia de Gromov–Wasserstein.

La analogía: Imagina que tienes dos ciudades diferentes. Una es una cuadrícula (como Manhattan) y la otra es una red de caminos sinuosos (como San Francisco). Se ven totalmente distintas.
La magia del GW: En lugar de comparar las calles directamente, el GW pregunta: "Si pudiera reorganizar mágicamente a las personas de la Ciudad A para que coincidan con la densidad de población de la Ciudad B, ¿cuánto cambiaría la 'distancia de relación' entre los vecinos?"
No le importa si las ciudades tienen 100 personas o 1,000 personas. Solo le importa el patrón de relaciones. Si la Ciudad A tiene un "centro" con muchas conexiones y la Ciudad B tiene un "centro" similar, el GW dice: "Estas dos ciudades son estructuralmente similares", aunque se vean diferentes en un mapa.

3. Añadiendo "Características": La versión fusionada

A veces, los puntos en tu red tienen información adicional. Por ejemplo, en un grafo de una molécula, cada átomo tiene un tipo específico (Carbono, Oxígeno). En un grafo social, cada persona tiene un puesto de trabajo.

La analogía: Imagina comparar dos ciudades de nuevo. El GW observa los patrones de las carreteras. Pero, ¿y si también quieres comparar los tipos de edificios?
La magia del fGW: La distancia de Gromov–Wasserstein Fusionado (fGW) hace ambas cosas a la vez. Comprueba si los patrones de las carreteras coinciden y también si los edificios en puntos similares son del mismo tipo. Es como una regla que mide tanto la forma de la ciudad como el color de las casas.

4. La Gran Afirmación: "Siempre funciona" (Consistencia Universal)

Los autores no solo construyeron una nueva regla; demostraron matemáticamente que usar esta regla con el método $k$ -NN siempre funciona a largo plazo.

La garantía: Demostraron que si sigues añadiendo más y más datos de entrenamiento (más ejemplos de grafos), tu clasificador $k$ -NN usando estas nuevas distancias se volverá tan preciso como sea teóricamente posible.
El matiz: Esta prueba es válida para grafos de cualquier tamaño, siempre y cuando sigas reglas específicas sobre cómo eliges el "número de vecinos" ( $k$ ) a medida que tus datos crecen. Demostraron que el espacio de todos los grafos posibles se comporta lo suficientemente bien como para que esta matemática se sostenga.

5. El Experimento: ¿Realmente ayuda?

Los autores probaron su método con datos del mundo real:

Moléculas: Clasificar productos químicos según su estructura y tipos de átomos.
Redes Sociales: Clasificar redes de colaboración de películas (por ejemplo, "Acción" frente a "Romance").
Datos Sintéticos: Redes creadas artificialmente para probar los límites.

Los Resultados:

Su método (GW- $k$ -NN y fGW- $k$ -NN) funcionó muy bien, superando o igualando a menudo a otros métodos populares como las Redes Neuronales de Grafos (GCN) y los complejos kernels de grafos.
Hallazgo clave: Para las moléculas con datos adicionales (tipos de átomos), la versión "Fusionada" (fGW) fue la clara ganadora. Demostró que observar tanto la estructura como las características al mismo tiempo es mejor que mirar solo una de ellas.
Eficiencia: Aunque la matemática es pesada, el método fue sorprendentemente rápido y eficiente en comparación con otros métodos complejos, especialmente para grafos sin atributos.

Resumen

El artículo dice: "Encontramos una forma de medir qué tan similares son dos redes complejas, independientemente de su tamaño o forma. Demostramos que si usas esta medición para clasificar nuevas redes basándote en sus vecinos más cercanos, el método tiene la garantía matemática de que mejorará cada vez más a medida que le suministres más datos. Nuestras pruebas muestran que funciona de maravilla en problemas del mundo real como la identificación de moléculas y géneros de películas".

Lo que NO afirmaron:

No afirmaron que esto funcione para todo tipo de datos (solo para grafos y objetos estructurados).
No afirmaron que sea el método más rápido del mundo (señalaron que puede ser computacionalmente pesado, aunque demostraron que es competitivo).
No lo aplicaron a diagnósticos médicos o usos clínicos; se limitaron estrictamente a tareas de clasificación de grafos.

Resumen Técnico: $k$ -Vecinos más Cercanos en el Espacio de Gromov–Wasserstein

Planteamiento del Problema
El artículo aborda el desafío de la clasificación de datos con estructura de grafo, incluyendo grafos tanto sin atributos como con atributos de nodos, dentro de un marco riguroso de aprendizaje métrico. Los clasificadores tradicionales de $k$ -vecinos más cercanos ( $k$ -NN) dependen de funciones de distancia definidas en espacios euclidianos o espacios métricos estándar. Sin embargo, los grafos suelen poseer estructuras complejas donde la comparación directa es difícil, particularmente cuando los grafos tienen diferentes números de nodos o carecen de un embebido canónico. Si bien la distancia de Gromov–Wasserstein (GW) proporciona un marco para comparar espacios de medida métrica (mm-spaces) y la distancia de Gromov–Wasserstein fusionada (fGW) extiende esto para incluir características de nodos, las propiedades teóricas de los clasificadores $k$ -NN que operan dentro de estos espacios métricos específicos eran previamente desconocidas. Específicamente, no estaba claro si el $k$ -NN es universalmente consistente (convergiendo al riesgo de Bayes óptimo) cuando el espacio subyacente es el espacio de grafos equipado con distancias GW o fGW.

Metodología
Los autores implementan la clasificación $k$ -NN utilizando distancias GW y fGW e investigan su consistencia teórica. El núcleo de su metodología consiste en establecer las propiedades topológicas de los espacios métricos en cuestión para satisfacer las condiciones requeridas para la consistencia universal.

Definiciones de Espacio Métrico:
- Espacio GW ( $\mathbb{X}$ ): El espacio de clases de equivalencia de mm-spaces con soporte finito y medida de probabilidad uniforme, equipado con la distancia de Gromov–Wasserstein $p=2$ . Esto modela grafos sin atributos.
- Espacio fGW ( $\mathbb{Y}^f$ ): El espacio de clases de isomorfismo débil de objetos estructurados (mm-spaces con mapas de características hacia $\mathbb{R}^d$ ), equipado con la distancia de Gromov–Wasserstein fusionada ( $p=1, q=2$ ). Esto modela grafos con atributos de nodos.
Marco Teórico:
Los autores se apoyan en resultados establecidos en la teoría del aprendizaje (específicamente Chaudhuri y Dasgupta [9]) que establecen que el $k$ -NN es universalmente consistente en un espacio métrico separable si el espacio posee una dimensión métrica $\sigma$ -finita (una propiedad relacionada con la condición de diferenciación de Lebesgue). Para probar esto para los espacios GW y fGW, los autores:
- Construyen modelos de dimensión finita para espacios de $n$ puntos dentro de estos marcos.
- Demuestran la existencia de mapas bi-Lipschitz entre el espacio de grafos de $n$ puntos y espacios cociente específicos de matrices euclidianas (para GW) y espacios producto de matrices y vectores de características (para fGW).
- Prueban que estos espacios cociente tienen una dimensión Assouad-Nagata finita.
- Utilizan el Lema 2.4 para mostrar que la existencia de mapas bi-Lipschitz hacia espacios con dimensión finita implica que los espacios objetivo ( $\mathbb{X}$ y $\mathbb{Y}^f$ ) poseen una dimensión métrica $\sigma$ -finita.
Experimentos Numéricos:
Los autores evalúan el desempeño de GW- $k_n$ -NN y fGW- $k_n$ -NN en siete conjuntos de datos de referencia:
- Grafos con Atributos: BZR, COX-2 y PROTEINS (conjuntos de datos moleculares).
- Grafos sin Atributos: IMDb-B, IMDb-M (redes sociales) y dos conjuntos de datos sintéticos (ERSBM1, ERSBM2).
- Líneas Base: Comparaciones contra Redes Convolucionales de Grafos (GCN), varios métodos de kernel de grafos (Shortest Path, Graphlet, HOPPER, Propagation) y SVMs usando kernels GW/fGW.

Contribuciones Clave
La contribución principal de este trabajo es la prueba de la consistencia universal para los clasificadores $k$ -NN en el contexto de la clasificación de grafos utilizando distancias GW y fGW.

Resultados Teóricos:
- Teorema 1.8: Prueba que el clasificador GW- $k_n$ -NN es universalmente débilmente consistente en el espacio de grafos $(\mathbb{X}, GW_2)$ bajo las condiciones $k \to \infty$ y $k/n \to 0$ . Es universalmente fuertemente consistente si $k/\log(n) \to \infty$ .
- Teorema 1.9: Prueba los mismos resultados de consistencia para el clasificador fGW- $k_n$ -NN en el espacio de grafos con atributos de nodos $(\mathbb{Y}^f, fGW_{\alpha,1,2})$ .
- Estos resultados se establecen demostrando que ambos espacios son separables y poseen dimensión métrica $\sigma$ -finita, una propiedad derivada mediante embebidos bi-Lipschitz en espacios cociente de espacios euclidianos.
Resultados Empíricos:
- En los conjuntos de datos de grafos con atributos (BZR, COX-2, PROTEINS), fGW- $k_n$ -NN alcanzó consistentemente la precisión promedio más alta, superando a las GCN y otros métodos basados en kernels. GW- $k_n$ -NN también tuvo un desempeño competitivo.
- En los conjuntos de datos sin atributos, GW- $k_n$ -NN logró una precisión perfecta (100%) en el conjunto de datos sintético ERSBM2 y un fuerte desempeño en IMDb-B, a menudo superando a los kernels de grafos y a las GCN.
- Los autores señalan que, si bien los métodos GW/fGW son interpretables (las distancias pequeñas implican similitud estructural), pueden ser computacionalmente intensivos en comparación con algunos métodos de kernel, aunque ofrecen mejoras de eficiencia sobre los SVMs usando kernels GW en ciertos contextos.

Significancia y Reivindicaciones
El artículo afirma establecer una base teórica para el uso de clasificadores métricos como $k$ -NN dentro del marco de Gromov–Wasserstein. Al probar la consistencia universal, los autores argumentan que estos métodos no son meramente heurísticos, sino que son teóricamente sólidos para tareas de clasificación de grafos.

La significancia radica en cerrar la brecha entre la teoría del transporte óptimo y la teoría del aprendizaje estadístico para datos estructurados. Los autores enfatizan que su enfoque ofrece un "marco altamente interpretable" donde la distancia entre grafos mide directamente la similitud estructural (el isomorfismo implica distancia cero). Expresan explícitamente que, según su conocimiento, esta es la primera aplicación de GW- $k$ -NN a la clasificación de grafos y la primera prueba teórica de su consistencia.

El documento se mantiene modesto respecto a generalizaciones futuras. Reconoce que, si bien la consistencia se prueba para parámetros específicos ( $p=2$ para GW, $p=1, q=2$ para fGW), sigue siendo un problema abierto si estos resultados se mantienen para otras elecciones de parámetros o en los entornos Z-Gromov–Wasserstein más generales. Los autores conjeturan que, de manera similar al espacio de Wasserstein, la consistencia universal puede no mantenerse en plena generalidad sin restricciones específicas sobre los espacios de interés.