Aprendizaje de la Estructura de Grafos de Conexión

Información Básica

• ID del Artículo: 2510.11245
• Título: Learning the Structure of Connection Graphs
• Autores: Leonardo Di Nino, Gabriele D'Acunto, Sergio Barbarossa, Paolo Di Lorenzo (Universidad Sapienza de Roma & CNIT)
• Clasificación: cs.LG (Aprendizaje Automático), eess.SP (Procesamiento de Señales)
• Fecha de Presentación: Presentado a arXiv el 13 de octubre de 2025
• Enlace del Artículo: https://arxiv.org/abs/2510.11245v1

Resumen

Los grafos de conexión (Connection Graphs, CGs) extienden los modelos de grafos tradicionales acoplando la topología de red con transformaciones ortogonales, permitiendo representar consistencia geométrica global. Desempeñan un papel crucial en aplicaciones como sincronización, procesamiento de señales riemannianas y difusión de haces neurales. Este estudio aborda el problema inverso de aprender grafos de conexión directamente a partir de señales observadas. Los autores proponen un marco principista basado en máxima pseudoverosimilitud bajo suposiciones de consistencia, que impone vínculos entre las propiedades espectrales del laplaciano de conexión y el laplaciano combinatorio subyacente. Basándose en esta formulación, se introduce el algoritmo de Aprendizaje Estructurado de Grafos de Conexión (SCGL), un proceso de optimización por bloques en variedades riemannianas que permite inferir conjuntamente la topología de red, pesos de aristas y estructura geométrica.

Contexto de Investigación y Motivación

Definición del Problema

El problema central que aborda este estudio es el problema inverso de aprender la estructura de grafos de conexión a partir de señales observadas. Específicamente incluye:

1. Cómo inferir simultáneamente la estructura de topología de red a partir de datos de señales de valores vectoriales
2. Cómo aprender matrices de transformaciones ortogonales en las aristas
3. Cómo garantizar que el grafo de conexión aprendido satisfaga consistencia geométrica

Importancia del Problema

El procesamiento tradicional de señales en grafos (GSP) solo puede capturar interacciones locales y por pares entre nodos, limitando la capacidad de modelar consistencia global de la red. Los grafos de conexión, mediante la introducción de transformaciones ortogonales, pueden:

• Representar configuraciones de sincronización más ricas que los grafos tradicionales
• Modelar consistencia geométrica global
• Soportar aplicaciones avanzadas como procesamiento de señales riemannianas y difusión de haces neurales

Limitaciones de Métodos Existentes

1. Vector Diffusion Maps (VDM): Utiliza principios geométricos para aproximar el laplaciano de grafos de conexión, pero es un método directo, no adecuado para problemas inversos
2. Métodos SDP: Utiliza programación semidefinida para extender el aprendizaje de laplacianos de haces, pero no puede recuperar correctamente las propiedades geométricas no euclidianas de los grafos de conexión
3. Aprendizaje de Grafos Tradicional: Se enfoca solo en topología y suavidad de señales, sin poder manejar estructura geométrica

Motivación de la Investigación

Los métodos existentes no pueden manejar efectivamente los desafíos clave en el aprendizaje de grafos de conexión:

• Restricciones geométricas no euclidianas de variedades ortogonales
• Optimización conjunta de estructura topológica y geométrica
• Imposición de condiciones de consistencia

Contribuciones Principales

1. Marco Teórico: Propone una formulación de máxima pseudoverosimilitud basada en suposiciones de consistencia, extendiendo el control espectral de grafos tradicionales a grafos de conexión
2. Innovación Algorítmica: Desarrolla el algoritmo SCGL, utilizando optimización de descenso por bloques en variedades riemannianas para recuperar conjuntamente topología y patrones geométricos
3. Verificación Experimental: Demuestra mejoras significativas de SCGL en comparación con líneas base existentes en aprendizaje de grafos de conexión mediante experimentos sintéticos en grafos aleatorios y geométricos
4. Eficiencia Computacional: Implementa una parametrización más eficiente que métodos de programación cónica, reduciendo la complejidad espacial de O(V²n²) a O(Vn²)

Detalles del Método

Definición de la Tarea

Entrada: Conjunto de señales observadas X = {x₁, ..., xₘ}, donde cada señal xᵢ ∈ ℝⁿᵛ se forma apilando mediciones locales de nodos xᵥ ∈ ℝⁿ Salida: Laplaciano de conexión L, incluyendo:

• Laplaciano combinatorio del grafo subyacente L
• Pesos de aristas w
• Bases ortogonales de nodos O = blkdiag({Oᵥ}ᵥ∈V)

Fundamentos Teóricos

Definición de Grafo de Conexión

Un grafo de conexión G = ⟨G,ℝⁿ,w,O(n)⟩ se compone de los siguientes elementos:

• Grafo subyacente G := (V,E)
• Espacio vectorial euclidiano n-dimensional ℝⁿ en cada nodo v ∈ V
• Pesos no negativos wₑ y matrices ortogonales Oₑ ∈ O(n) en cada arista e ∈ E

Condición de Consistencia

El Teorema 1 establece que la consistencia del grafo de conexión es equivalente a las siguientes condiciones:

1. Las composiciones de mapeos ortogonales a lo largo de cada ciclo del grafo resultan en la aplicación identidad
2. Los valores propios del laplaciano de conexión son n-múltiplos de los valores propios del laplaciano combinatorio
3. Existen matrices ortogonales de nodos tales que los mapeos de aristas se descomponen como Oᵢⱼ = Oᵢᵀ Oⱼ

Formulación del Problema de Optimización

Problema de Máxima Pseudoverosimilitud

Asumiendo que las señales siguen una distribución gaussiana N_nv(0,L†), el problema original es:

min_{L∈CL} -log gdet(L) + Tr(SL)     (P1)

Reformulación bajo Restricciones de Consistencia

Utilizando la condición de consistencia L = Oᵀ(L⊗Iₙ)O, el problema se transforma en:

min_{L∈GL, O∈O} -log gdet{Oᵀ(L⊗Iₙ)O} + Tr{SOᵀ(L⊗Iₙ)O}     (P2)

Problema de Optimización Final

Mediante la introducción del laplaciano estructurado de Kronecker y relajación lagrangiana:

min_{O,w,U,Λ} -n log gdet(Λ) + Tr{SOᵀL_K(w)O} + αΨ(w)
             + β/2 ||OᵀL_K(w)O - U(Λ⊗Iₙ)Uᵀ||²_F     (P3)

Algoritmo SCGL

Optimización de Descenso por Bloques de Coordenadas

SCGL adopta una estrategia de minimización alternada por bloques, optimizando separadamente cuatro bloques de variables:

1. Actualización de Pesos de Aristas (w):

   w^{t+1} = P^+_{α/β Ψ}{w^t - 1/τ L*_K[f(w^t)]}
   

   
   Utilizando el método de Minorización-Maximización (MM)
2. Actualización de Bases Ortogonales (O): Utilizando descenso de gradiente riemanniano en la variedad producto SO(n)^v
3. Actualización de Vectores Propios (U): Mediante cálculo de vectores propios principales:

   U^{t+1} = [Eigenvecs{OᵀL_K(w)O}]_{:,(n+1):}
   

4. Actualización de Valores Propios (Λ): Problema de regresión isotónica con solución KKT de forma cerrada

Complejidad Computacional

La complejidad del algoritmo es O(V³n³), determinada principalmente por la descomposición espectral en los pasos de optimización de bases ortogonales y vectores propios, aumentando solo por el factor de escala de dimensión n en comparación con aprendizaje de grafos estructurados.

Configuración Experimental

Conjuntos de Datos

1. Grafos de Conexión Erdős–Rényi (ER):
   • Número de nodos: |V| = 30
   • Probabilidad de arista: p_ER = 1.1 log V / V
   • Dimensión del espacio vectorial: n = 2
   • Pesos de aristas: Unif(0.2, 3)
2. Grafo de Conexión Geométrico Esférico:
   • Esfera en R³, discretizada usando red de Fibonacci
   • 50 puntos, grafo k-NN con k=4
   • Laplaciano de conexión construido usando Vector Diffusion Maps

Métricas de Evaluación

1. Recuperación de Topología: Puntuación F1 (recuperación de patrón disperso), MSE de pesos de aristas
2. Fidelidad Geométrica:
   • Variación total empírica ÊL(Y) = M⁻¹ Tr(L̂YYᵀ)
   • Distancia espectral promedio σ(L,L̂) = 1/(nv) Σᵢ|Λᵢ(L)-Λᵢ(L̂)|
   • Distancia de difusión térmica integrada ξ(L,L̂)

Métodos de Comparación

1. KRON: Versión simplificada de SCGL con bases locales fijas como matrices identidad
2. SDP: Método de aprendizaje suave basado en programación semidefinida
3. SLGP: Trabajo anterior de los autores, aprendizaje suave con priors geométricos

Escenarios de Disponibilidad de Datos

Definidos según la razón de muestreo r = M/(2|V|):

• Bajo: r = 1.5
• Medio: r = 5
• Alto: r = 15

Resultados Experimentales

Resultados de Grafos de Conexión ER

• Recuperación de Topología: Con el aumento de datos, SCGL supera significativamente todos los métodos base en puntuación F1
• Fidelidad Geométrica: SCGL está más cerca del valor esperado teórico en variación total empírica, indicando mejor consistencia
• Estimación de Pesos de Aristas: SCGL estima con precisión pesos de aristas, con la mayoría de falsos positivos asignados pesos negligibles

Resultados de Grafo de Conexión Esférico

• Puntuación F1: SCGL = 0.995 (máximo), SLGP = 0.927, SDP = 0.620, KRON = 0.425
• Distancia Espectral: SCGL = 0.90 (mínimo), significativamente superior a otros métodos
• Distancia de Difusión Térmica: SCGL = 1.19 (mínimo)
• Dimensión del Núcleo: SCGL mantiene correctamente dim(ker(L)) = 2, garantizando consistencia

Hallazgos Clave

1. SCGL presenta mejor desempeño cuando hay datos suficientes, con rendimiento comparable a SLGP cuando hay datos escasos
2. Optimizar bases ortogonales de nodos proporciona mejoras significativas en comparación con fijar matrices identidad
3. SCGL logra simultáneamente la mejor recuperación de topología y fidelidad geométrica
4. El algoritmo mantiene la consistencia del grafo de conexión, que es clave para su significado geométrico

Trabajo Relacionado

Campo de Aprendizaje de Grafos

El aprendizaje tradicional de grafos persigue principalmente dos objetivos:

1. Imponer topología deseada (equilibrando dispersidad y conectividad)
2. Promover suavidad de señales (variación baja entre nodos conectados)

Métodos de Teoría de Haces

• Haces de Red: Asocian datos estructurados en nodos y aristas mediante mapeos que preservan estructura
• Grafos de Conexión: Caso especial de teoría de haces, utilizando transformaciones ortogonales como mapeos que preservan estructura
• Aplicaciones: Problemas de sincronización, procesamiento de señales riemannianas, difusión de haces neurales

Métodos Existentes de Aprendizaje de Grafos de Conexión

1. Vector Diffusion Maps: Aproxima el laplaciano de grafos de conexión mediante principios geométricos
2. Métodos SDP: Extienden aprendizaje suave de grafos a laplacianos de haces
3. Métodos de Programación Cónica: Utilizan alineación de Procrustes y muestreo binario de aristas

Conclusiones y Discusión

Conclusiones Principales

1. Propone el primer marco principista para aprender grafos de conexión bajo suposiciones de consistencia
2. El algoritmo SCGL puede recuperar conjuntamente topología de red, pesos de aristas y estructura geométrica
3. Los experimentos demuestran que SCGL supera métodos existentes tanto en recuperación de topología como en fidelidad geométrica
4. El algoritmo logra mejor parametrización mientras mantiene eficiencia computacional

Limitaciones

1. Suposición de Consistencia: El método asume que el grafo de conexión es consistente, lo que puede no siempre ser cierto en la realidad
2. Suposición de Distribución Gaussiana: El modelo de señal puede ser demasiado simplificado
3. Datos Sintéticos: Los experimentos se realizan principalmente en datos sintéticos, careciendo de validación en el mundo real
4. Robustez al Ruido: La evaluación de rendimiento bajo ruido y violación de modelo no es suficientemente exhaustiva

Direcciones Futuras

1. Extender SCGL para manejar ruido y violación de modelo
2. Incorporar priors flexibles de topología y geometría
3. Abordar grafos de conexión inconsistentes
4. Validar el marco en datos del mundo real

Evaluación Profunda

Fortalezas

1. Contribución Teórica: Extiende aprendizaje de grafos estructurados a grafos de conexión, proporcionando base teórica sólida
2. Innovación Algorítmica: Combina ingeniosamente optimización riemanniana y descenso por bloques de coordenadas, manejando restricciones complejas de variedades
3. Evaluación Experimental Completa: Realiza evaluación exhaustiva en diferentes tipos de grafos de conexión
4. Eficiencia Computacional: Logra parametrización más eficiente comparada con métodos existentes

Deficiencias

1. Limitaciones de Aplicabilidad: La suposición de consistencia puede limitar el rango de aplicaciones prácticas
2. Limitaciones Experimentales: Carece de validación en conjuntos de datos del mundo real
3. Análisis de Ruido: El análisis de robustez al ruido no es suficientemente profundo
4. Limitaciones de Escala: La escala experimental es relativamente pequeña (máximo 50 nodos)

Impacto

1. Valor Académico: Proporciona nuevas herramientas para inferencia de topología de red consciente de geometría
2. Potencial de Aplicación: Tiene perspectivas de aplicación importante en sincronización, procesamiento de señales riemannianas y otros campos
3. Contribución Metodológica: Proporciona nuevo paradigma de optimización para aprendizaje de haces

Escenarios Aplicables

1. Redes de Sincronización: Problemas de sincronización que requieren aprender relaciones de rotación entre nodos
2. Procesamiento de Señales Riemannianas: Tareas de procesamiento de señales en variedades
3. Redes Neurales: Aprendizaje de estructura de redes neurales de haces
4. Robótica: Coordinación y localización de sistemas multirrobóticos

Referencias

El artículo cita 29 referencias relacionadas, cubriendo múltiples campos incluyendo procesamiento de señales en grafos, teoría de haces, optimización riemanniana y otros trabajos importantes, proporcionando base teórica sólida para la investigación.

Evaluación General: Este es un artículo de alta calidad con contribuciones importantes en el campo del aprendizaje de grafos de conexión. El algoritmo SCGL propuesto por los autores es innovador tanto teóricamente como en resultados experimentales convincentes. Aunque existen algunas limitaciones, abre nuevas direcciones de investigación en aprendizaje de grafos consciente de geometría, con importante valor académico y potencial de aplicación.