Low-Complexity and Consistent Graphon Estimation from Multiple Networks

1. Planteamiento del Problema

El objetivo central del trabajo es la estimación de la función graphon que parametriza un modelo de grafo aleatorio no paramétrico, a partir de una colección de redes observadas. El desafío específico radica en un escenario donde:

• Las redes no comparten un conjunto común de nodos (los nodos son distintos en cada red).
• Las redes tienen tamaños variables (heterogeneidad en el número de nodos).
• El problema de identificabilidad: Diferentes funciones graphon pueden inducir la misma distribución de grafos debido a reetiquetados que preservan la medida. Solo se puede recuperar una clase de equivalencia de funciones, a menos que se impongan condiciones adicionales (como la monotonicidad estricta de la función de grado normalizado).

Limitaciones de los métodos existentes:

• Enfoques de promediado: Estimar un graphon por separado para cada red y luego promediarlos ignora la alineación de nodos entre redes, es sesgado en redes pequeñas y no aprovecha la información global.
• Métodos basados en redes neuronales (ej. SIGL, IGNR): Ofrecen flexibilidad pero tienen una complejidad computacional prohibitiva para colecciones grandes de redes.
• Métodos basados en transporte óptimo (ej. SGWB): Alinean grafos mediante la distancia de Gromov-Wasserstein, pero son intensivos computacionalmente y enforces una resolución rígida.

2. Metodología: El Estimador de Ordenamiento de Grafos Conjuntos (JGS)

Los autores proponen el Joint Graph Sorting (JGS), un estimador basado en histogramas que realiza una alineación global de todos los nodos de la colección de redes antes de estimar el graphon.

Algoritmo Principal:

1. Cálculo de Grados Normalizados: Para cada nodo $i$ en cada red $m$, se calcula el grado empírico normalizado:
   $$\hat{d}^{norm}_{i,(m)} = \frac{1}{n^{(m)}-1} \sum_{j=1}^{n^{(m)}} A^{(m)}_{i,j}$$
2. Ordenamiento Global (Joint Sorting): En lugar de ordenar nodos red por red, se concatenan todos los grados normalizados de todas las redes ($N = \sum n^{(m)}$ nodos en total) y se ordenan en una sola lista creciente.
   • Esto asume que la función de grado normalizado $g(u) = \int W(u,v)dv$ es estrictamente creciente, lo que permite mapear el grado al espacio latente $[0,1]$.
3. Estimación de Posiciones Latentes: La posición latente estimada $\hat{U}^{JGS}_{i,(m)}$ para un nodo se asigna basándose en su rango global en la lista ordenada:
   $$\hat{U}^{JGS}_{i,(m)} = \frac{\hat{\sigma}^{-1}_{JGS}(i, m)}{N} - \frac{1}{2N}$$
   Donde $\hat{\sigma}_{JGS}$ es la permutación de ordenamiento.
4. Construcción del Histograma: Se particiona el cuadrado unitario $[0,1]^2$ en $k^2$ bloques. Se calcula la frecuencia de aristas observadas dentro de cada bloque utilizando la matriz de adyacencia "ordenada" (que contiene entradas faltantes entre nodos de diferentes redes originales).
5. Selección del Número de Bloques ($k$): Se propone una regla heurística para elegir $k$ que equilibra el sesgo y la varianza, evitando bloques vacíos:
   $$k \asymp \min \left\{ S^{1/4}, \frac{N}{c(M + \log N)} \right\}$$
   Donde $S$ es el número total de aristas observadas y $N$ el número total de nodos.

Complejidad Computacional:

El algoritmo tiene una complejidad de $O(N \log N + S)$, donde $N$ es el número total de nodos y $S$ el número total de aristas observadas. Esto es significativamente más eficiente que los métodos iterativos o basados en optimización de transporte óptimo.

3. Contribuciones Clave

1. Algoritmo Determinista y No Iterativo: JGS infiere simultáneamente las posiciones latentes y produce una estimación unificada del graphon sin necesidad de entrenamiento iterativo costoso.
2. Garantías Teóricas de Consistencia:
   • Se demuestra la consistencia de los estimadores de posiciones latentes bajo la condición de monotonicidad estricta del grado.
   • Se prueba que el estimador del graphon es consistente (el error cuadrático medio integrado tiende a cero) cuando el tamaño de las redes crece ($n_{max} \to \infty$) y el número de redes $M$ es fijo.
   • Nota importante: El paper aclara que el estimador no es consistente si el número de redes $M \to \infty$ mientras los tamaños de las redes permanecen acotados, debido a la falta de consistencia en la estimación de grados en redes pequeñas.
3. Rendimiento Superior en Redes Pequeñas: El método aprovecha la información de todas las redes para mejorar la estimación de posiciones latentes, superando a los métodos que tratan cada red de forma aislada.
4. Eficiencia Computacional: Es sustancialmente más rápido que los métodos de vanguardia consistentes (como SIGL o SGWB), siendo órdenes de magnitud más rápido.

4. Resultados Experimentales

Los autores evaluaron JGS mediante experimentos numéricos extensos:

• Precisión (MISE): En datos sintéticos generados a partir de 13 graphons diferentes (incluyendo casos monótonos y no monótonos), JGS (y su versión suavizada JGS-smooth) logró el Menor Error Cuadrático Medio Integrado (MISE) en la mayoría de los casos, superando a SBA, SAS, USVT, SGWB y SIGL.
  • Excepción: En redes extremadamente dispersas (Graphon 9), SIGL tuvo un rendimiento ligeramente superior, aunque JGS mantuvo el segundo mejor comportamiento.
• Velocidad: Las pruebas de tiempo de ejecución mostraron que JGS es 10 a 100 veces más rápido que SIGL y SGWB, incluso con colecciones grandes de redes o nodos.
• Escalabilidad:
  • Cuando el tamaño de las redes aumenta, el error de JGS converge a cero (confirmación teórica).
  • Cuando solo aumenta el número de redes (con tamaños fijos y pequeños), el error converge a un valor no nulo, validando la limitación teórica identificada.
• Aplicación en Clasificación (G-Mixup): Se integró JGS en un marco de aumento de datos (G-Mixup) para tareas de clasificación con Redes Neuronales de Grafos (GIN). En los conjuntos de datos reales IMDB-BINARY e IMDB-MULTI, el uso de JGS para generar grafos sintéticos mejoró la precisión de clasificación en comparación con el uso de otros estimadores de graphon, demostrando su utilidad práctica para la generalización del modelo.

5. Significado y Conclusión

Este trabajo aborda una brecha crítica en el análisis de redes: la necesidad de métodos que sean tanto estadísticamente sólidos como computacionalmente escalables para colecciones de redes heterogéneas.

• Innovación: La idea de realizar un ordenamiento global ("Joint Sorting") en lugar de local permite una alineación eficiente de nodos sin los costos de optimización de transporte óptimo.
• Impacto: JGS ofrece una solución práctica para aplicaciones en neurociencia, ecología y sociología donde se dispone de múltiples redes de tamaños variables.
• Limitaciones: El método depende de la suposición de monotonicidad estricta del grado (aunque muestra robustez en casos no monótonos) y no es consistente en el régimen asintótico donde el número de redes crece indefinidamente con tamaños fijos.

En resumen, JGS representa un avance significativo al proporcionar un estimador de graphon que combina alta precisión, consistencia teórica bajo condiciones realistas y una eficiencia computacional que lo hace viable para grandes volúmenes de datos de redes.