Resumen Técnico: Algoritmos de Complejidad Temporal Óptima para el Cálculo de RWKs Generales en Grafos Dispersos

Planteamiento del Problema

El artículo aborda el cuello de botella computacional asociado con el cálculo de los Kernels de Caminata Aleatoria Generales (RWKs) para grafos dispersos. Los RWKs son una célebre familia de funciones simétricas y definidas positivas que asignan puntuaciones de similitud a pares de grafos mediante la suma ponderada de caminatas de diferentes longitudes en el producto directo del grafo $G_1 \times G_2$.

Si bien los RWKs abarcan kernels populares como los kernels marginalizados, geométricos y exponenciales, su cálculo exacto es prohibitivamente costoso. Para grafos con $N$ vértices, la evaluación por fuerza bruta a través del grafo de producto directo incurre en una complejidad de $O(N^6)$. Incluso los métodos optimizados, como la resolución de ecuaciones de Sylvester o el uso de la descomposición espectral, suelen requerir un tiempo de $O(N^3)$ y a menudo no logran manejar grafos etiquetados o escalar a conjuntos de datos masivos. Además, los métodos sub-cúbicos existentes generalmente no pueden manejar secuencias de coeficientes arbitrarias $(\mu_i)$ requeridas para el aprendizaje del parámetro del kernel. Notablemente, mientras que el trabajo previo de Kang et al. (2012) proporcionó un algoritmo de $O(N)$, este estaba restringido al caso específico de los RWKs geométricos en grafos no etiquetados.

La pregunta central planteada es: ¿Es posible calcular estimaciones insesgadas de RWKs generales para grafos etiquetados y dispersos con una complejidad temporal lineal de $O(N)$?

Metodología: Graph Voyagers (GVoys)

Los autores proponen Graph Voyagers (GVoys), el primer algoritmo que logra la aproximación insesgada de RWKs generales en un tiempo de $O(N)$ tanto para grafos dispersos etiquetados como no etiquetados. El método generaliza los Graph Random Features (GRFs) pero introduce mecanismos específicos para evitar la instanciación del grafo de producto directo $G_1 \times G_2$ en memoria.

Mecanismo Central

1. Caminatas Aleatorias Dependientes: En lugar de muestrear caminatas en el masivo grafo de producto, GVoys muestrean caminatas aleatorias de forma independiente en $G_1$ y $G_2$. Para emular las caminatas en el grafo de producto, estas caminatas independientes se acoplan utilizando variables aleatorias compartidas.
2. Filtrado mediante Variables Aleatorias:
   • Coincidencia de Longitud ($g$-variables): Para asegurar que solo las caminatas de la misma longitud contribuyan al kernel (como requiere la definición de la caminata del grafo de producto), el algoritmo multiplica las contribuciones de la caminata por variables aleatorias de Rademacher compartidas $g(l)$ en cada paso $l$. Dado que $E[g(l_1)g(l_2)] = \mathbb{I}(l_1 = l_2)$, los términos cruzados donde las longitudes de las caminatas difieren desaparecen en la esperanza.
   • Coincidencia de Etiquetas ($z$-variables): Para grafos etiquetados, el algoritmo introduce variables aleatorias compartidas adicionales $z(l, i)$ correspondientes a las etiquetas de los vértices. Esto filtra las contribuciones de las caminatas donde la secuencia de etiquetas de los vértices no coincide, manejando efectivamente la restricción de que las aristas en el grafo de producto solo existen entre vértices con etiquetas idénticas.
3. Embeddings a Nivel de Grafo: El algoritmo construye vectores de características de baja dimensión para cada grafo. El producto punto de estos embeddings para cualquier par de grafos $(G_i, G_j)$ proporciona una estimación insesgada del verdadero RWK $K_{RWK}(G_i, G_j)$.
4. Eficiencia de Memoria: El método no almacena la matriz de adyacencia del grafo de producto. Utiliza representaciones dispersas y puntos de anclaje para reducir la dimensionalidad, asegurando que la complejidad espacial permanezca lineal respecto al número de nodos.

Detalles Algorítmicos

• Entrada: Grafos $G_i$, función de modulación $f_\mu$ (derivada de los coeficientes $\mu_i$), probabilidad de terminación $p_{halt}$, y número de caminatas $m$.
• Proceso:
  1. Inicializar secuencias aleatorias compartidas $g$ y $z$.
  2. Para cada grafo, simular $m$ caminatas aleatorias comenzando desde varios vértices.
  3. Acumular "depósitos" en vértices de anclaje, ponderados por la función de modulación, las variables aleatorias y la probabilidad de la caminata.
  4. Construir matrices de características $C_i$ y $D_i$.
• Salida: Vectores de características $\phi(G_i)$ tales que $K_{RWK}(G_i, G_j) = \mathbb{E}[\phi(G_i)^\top \phi(G_j)]$.

Contribuciones Clave

1. Complejidad Temporal Lineal: El artículo presenta el primer algoritmo de $O(N)$ para la aproximación insesgada de RWKs generales (que cubre secuencias de coeficientes arbitrarias $(\mu_i)$) tanto para grafos dispersos etiquetados como no etiquetados. Esto va más allá de los métodos $O(N)$ previos que estaban limitados a casos específicos como los RWKs geométricos en grafos no etiquetados.
2. Escalabilidad a Datasets Masivos: Al evitar la instanciación del grafo de producto directo, el método escala a grafos con $>2^{14}$ nodos y conjuntos de datos con miles de grafos, donde los métodos anteriores fallan debido a restricciones de memoria (OOM) o de tiempo.
3. Garantías Teóricas:
   • Insesgadez: El Teorema 4.1 demuestra que el estimador es insesgado.
   • Concentración: El Teorema 4.2 proporciona límites de concentración exponencial, mostrando que el estimador converge rápidamente al valor real del kernel.
   • Optimalidad: El Teorema 4.3 demuestra que el uso de distribuciones de Rademacher para las variables aleatorias minimiza la varianza del estimador.
4. Aprendizaje de Kernel Implícito: La capacidad de aproximar RWKs generales (en lugar de casos especiales fijos) permite el aprendizaje de extremo a extremo de la secuencia de coeficientes $(\mu_i)$, desbloqueando el aprendizaje escalable de kernels de grafos implícitos.

Resultados Experimentales

Los autores evaluaron GVoys en el TUDataset y en grafos sintéticos de Erdős-Rényi:

• Precisión: GVoys convergen a los valores exactos de los RWK a medida que aumenta el número de caminatas aleatorias. En tareas de clasificación de grafos (ej. MUTAG, ENZYMES, NCI1), GVoys igualaron o superaron el rendimiento de las líneas base de RWK exacto.
• Velocidad:
  • Para grafos con $>2^{10}$ nodos, GVoys superaron a la descomposición espectral, el gradiente conjugado y los métodos de iteración de punto fijo.
  • En grafos con $2^{13}$ nodos, GVoys fueron 27 veces más rápidos que la iteración de punto fijo.
  • En grafos con $2^{14}$ nodos, GVoys fueron 8 veces más rápidos que el gradiente conjugado, mientras que otras líneas base se quedaron sin memoria o tiempo.
• Aprendizaje de Kernel: El aprendizaje de los coeficientes $(\mu_i)$ usando GVoys en el dataset MUTAG produjo una precisión del $88.3\%$, una mejora del $8.5\%$ sobre la línea base estándar de RWK geométrico ($81.4\%$).

Significado y Reivindicaciones

El artículo afirma haber resuelto una barrera computacional de larga data en los métodos de kernel de grafos. Al lograr una complejidad de tiempo y espacio lineal, GVoys hacen que sea factible aplicar kernels de caminata aleatoria generales a conjuntos de datos masivos y del mundo real que antes eran intratables.

Los autores enfatizan que su método es el primer algoritmo sub-cúbico que logra la aproximación insesgada para RWKs generales tanto en grafos etiquetados como no etiquetados. Aunque existían algoritmos $O(N)$ previos para instancias específicas (como los RWKs geométricos en grafos no etiquetados), GVoys son los primeros en manejar el caso general con coeficientes arbitrarios y vértices etiquetados. La introducción de nuevos embeddings de grafos (características aleatorias) que preservan la estructura del kernel permite un escalamiento lineal respecto tanto al número de nodos en un grafo como al número de grafos en un conjunto de datos. Esta capacidad se destaca como un prerrequisito para el aprendizaje escalable de kernels de grafos implícitos, donde los propios parámetros del kernel se aprenden de los datos.

El artículo concluye que, si bien el método es insesgado para grafos no dirigidos y no ponderados, la naturaleza estocástica del estimador puede ofrecer robustez al ruido en tareas de downstream, superando potencialmente los cálculos de kernel exactos en escenarios de clasificación.