An Empirical Spectral-Domination Relationship Discovered Through Symbolic Regression

Resumen Técnico: Descubrimiento de una Relación Empírica de Dominación Espectral mediante Regresión Simbólica

Planteamiento del Problema
El artículo aborda el desafío de descubrir relaciones matemáticas entre invariantes de grafos, centrándose específicamente en el número de dominación $\gamma(G)$ (el tamaño del conjunto dominador más pequeño) y el radio espectral $\lambda_1(G)$ (el mayor autovalor de la matriz de adyacencia). Aunque existe una investigación extensa sobre los límites para $\gamma(G)$ que involucran estructuras de grados (por ejemplo, $\gamma(G) \ge n/(\Delta(G)+1)$) y límites espectrales que involucran el espectro del Laplaciano, relativamente pocos límites relacionan $\gamma(G)$ directamente con el radio espectral de adyacencia $\lambda_1(G)$. Los autores pretenden aprovechar el aprendizaje automático para identificar posibles fórmulas empíricas que puedan servir como puntos de partida para la investigación teórica.

Metodología
El estudio emplea un flujo de trabajo basado en datos que combina la generación de grafos, el cómputo de invariantes y la regresión simbólica:

1. Generación de Conjunto de Datos: Se generó un conjunto de datos de 3,429 grafos conexos a partir de cuatro familias distintas con rangos de parámetros expandidos:

   • Erdős–Rényi ($G(n,p)$)
   • Barabási–Albert ($BA(n,m)$)
   • Watts–Strogatz ($WS(n,k,p)$)
   • Regular Aleatorio ($RR(n,d)$)
   • Los parámetros se restringieron a $n \in [10, 60]$ con semillas aleatorias fijas para la reproducibilidad.

2. Cómputo de Invariantes: Para cada grafo, los autores computaron invariantes básicos ($n, m, \Delta, \delta$), invariantes estructurales (número cromático $\chi$, número de clique $\omega$, número de independencia $\alpha$, número de emparejamiento $\nu$) e invariantes espectrales ($\lambda_1$). Se utilizaron algoritmos exactos cuando fue computacionalmente factible ($n \le 30$ o $n \le 40$), y aproximaciones ávidas (greedy) para instancias más grandes.

3. Regresión Simbólica: Utilizando la librería PySR (basada en programación genética), los autores buscaron expresiones matemáticas que se ajustaran a los datos. El espacio de búsqueda incluyó operadores binarios ($+, -, \times, \div$) y operadores unarios ($\sqrt{}, \exp, \log$) con una complejidad máxima de 10. Las regresiones se ejecutaron para predecir varios invariantes, con un enfoque específico en $\gamma$ como función de $n, m, \Delta, \lambda_1, \omega, \alpha, \nu$.

4. Filtrado y Validación: Las fórmulas candidatas fueron examinadas frente a límites conocidos en la literatura y probadas en grafos canónicos (por ejemplo, $K_n, C_n, S_n$). Los candidatos supervivientes se sometieron a una rigurosa "búsqueda de contraejemplos", que incluyó:

   • Pruebas en nuevas generaciones de grafos (diferentes semillas).
   • Pruebas en familias extremas (completos, bipartitos, ciclos, caminos, estrellas, hipercubos).
   • Búsqueda adversarial (ascenso de colinas para maximizar la violación).

5. Reajuste del Modelo: El candidato más prometedor identificado por la regresión simbólica fue reajustado utilizando scipy.optimize.curve_fit para optimizar los coeficientes.

Resultados Clave
El proceso de regresión simbólica identificó una relación empírica específica:
$$\gamma(G) \approx \frac{1.53n}{\lambda_1(G) + 1.55}$$

• Desempeño General: En el conjunto completo de datos de 3,429 grafos, el modelo logró un $R^2$ de 0.9609, con un Error Absoluto Medio (MAE) de 0.6633 y un RMSE de 0.9186.
• Desempeño por Familia: La relación se generalizó bien a través de las cuatro familias de entrenamiento, con valores de $R^2$ que oscilaron entre 0.89 (Barabási–Albert) y 0.96 (Regular Aleatorio).
• Análisis de Fallos: El modelo fue probado explícitamente en familias de grafos extremales para caracterizar su dominio de validez:
  • Grafos Completos ($K_n$): La fórmula sobreestima sistemáticamente $\gamma$ en aproximadamente un 40–50% (prediciendo ~1.5 en lugar de 1).
  • Grafos Estrella ($S_n$): El modelo falla catastróficamente, con errores relativos que superan el 400% para $n=20$. La estructura de núcleo (hub) conduce a una dominación trivial ($\gamma=1$) a pesar de radios espectrales moderados, causando una sobreestimación severa.
  • Grafos Camino y Ciclo: El desempeño es moderado, con errores que oscilan entre el 10% y el 30%, generalmente sobreestimando $\gamma$.
• Supervivencia: Entre varios candidatos generados (incluyendo relaciones para $\omega, \alpha$ y $\chi$), la relación espectral-dominación fue la única en sobrevivir a la búsqueda de contraejemplos con límites de error razonables en grafos no extremales.

Significado y Reivindicaciones
El artículo posiciona este trabajo como un caso de estudio en "Matemáticas Impulsadas por Datos" y "Aprendizaje Automático Científico", en lugar de una prueba teórica definitiva.

• Contribución Metodológica: Los autores demuestran que la regresión simbólica guiada por ML puede identificar con éxito relaciones empíricas prometedoras entre invariantes de grafos complejos que podrían ser no obvias para los investigadores humanos.
• Contribución Empírica: El artículo proporciona una fórmula empírica caracterizada: $\gamma(G) \approx 1.53n/(\lambda_1(G) + 1.55)$.
• Reivindicaciones Modestas: Los autores declaran explícitamente que esto es un modelo empírico, no un teorema. No reclaman validez universal, prueba teórica o caracterización exacta.
  • Las constantes (1.53 y 1.55) carecen actualmente de justificación teórica; los intentos de derivar estos valores a partir de límites clásicos (por ejemplo, combinando $\gamma \ge n/(\Delta+1)$ y $\lambda_1 \le \Delta$) no lograron reproducir los valores específicos.
  • La relación es válida principalmente para grafos de densidad moderada y sin núcleos gigantes.
• Direcciones Futuras: El artículo sugiere que la relación identificada sirve como punto de partida para la investigación teórica, cuestionando específicamente si las constantes tienen interpretaciones estructurales y si se pueden derivar límites más ajustados para clases de grafos restringidas.

En resumen, el artículo utiliza con éxito el aprendizaje automático para generar una conjetura empírica de alta fidelidad sobre la relación inversa entre el radio espectral y el número de dominación, mientras define rigurosamente los límites donde esta conjetura falla.