Graph reconstruction from random-walk co-visitation: Geometric, empirical, and controlled networks

Resumen Técnico: Reconstrucción de Grafos a partir de la Co-visitación de Caminata Aleatoria

Planteamiento del Problema
El artículo aborda el problema inverso de reconstruir una estructura de grafo desconocida a partir de la trayectoria de una caminata aleatoria que difunde sobre ella. Esto surge en contextos donde los procesos dinámicos son observables (por ejemplo, series temporales, procesos de propagación o trazadores difusivos), pero la conectividad subyacente (el "cableado") no lo es. Un desafío central en este dominio es la reconstructibilidad: una caminata aleatoria solo puede transmitir información sobre las aristas que realmente atraviesa; las aristas nunca visitadas por la trayectoria muestreada son fundamentalmente irrecuperables de dicha muestra, independientemente del estimador utilizado. Un segundo desafío es la identificabilidad: el observable debe retener suficiente información estructural de pares para distinguir entre grafos que comparten sumarios de nivel de nodo idénticos (como las secuencias de grados).

Metodología
Los autores proponen un flujo de reconstrucción que evita el colapso de la información estructural en estadísticas de nivel de nodo mediante el uso de un observable de pares y un modelo de pares.

1. Observable (Matriz de Co-visitación): En lugar de utilizar probabilidades de ocupación marginales (que convergen a la distribución de grados estacionaria y pierden la información de pares), el método emplea la matriz de co-visitación $C$. Esta matriz registra los pares ordenados $(i, j)$ visitados por el caminante antes de realizar la suma por filas, preservando las transiciones específicas $i \to j$.
2. Modelo (Base de Pesos de Aristas de Pares): El modelo asume un log-peso $\beta_{ij}$ para cada par candidato en la base. La matriz de transición $P$ se deriva de una matriz de pesos $S(\beta)$ mediante normalización por filas. Este enfoque asigna un parámetro único a cada posible arista, lo que permite al modelo capturar estructuras agrupadas que los modelos de potencial de nodo aditivos no pueden capturar.
3. Ajustador (Levenberg–Marquardt Balanceado por Marco - fbLM): Los parámetros $\beta$ se ajustan a la matriz de co-visitación observada utilizando un esquema de Levenberg–Marquardt balanceado por marco (fbLM).
   • Pesos de Grupo: El residuo se agrupa por vértice. Los pesos se optimizan sobre un marco ortonormal (variedad de Stiefel) para asegurar que ningún vértice individual domine el ajuste. Este "balanceo por marco" evita el colapso de los pesos hacia nodos de alto grado y asegura que los vértices con información única reciban el peso apropiado.
   • Fijación de Calibre (Gauge Fixing): La co-visitación es invariante bajo un desplazamiento global de todos los log-pesos ($\beta \to \beta + c\mathbf{1}$). El método fija este calibre explícitamente centrando los parámetros después de cada paso de propuesta.
   • Propagación de la Incertidumbre: Se deriva una matriz de covarianza a partir de la información de Fisher, proyectando explícitamente fuera la dirección del calibre para evitar la inestabilidad numérica.
4. Lectura (Acoplamiento Autocalibrado): El conjunto de aristas final se determina mediante una métrica de acoplamiento autocalibrada $\rho_{ij} = W_{ij}/\sqrt{s_i s_j}$, donde $W$ son los pesos ajustados y $s_i$ son las fuerzas de los vértices. Se declara una arista si $\rho_{ij}$ supera el acoplamiento medio de sus dos extremos. Este umbral es relativo y basado en los datos, y no requiere un corte absoluto o conocimiento previo de la densidad del grafo.

Conjuntos de Datos y Configuración Experimental
El flujo de trabajo se prueba en cinco bancos de pruebas distintos:

• Empírico: Un subgrafo de comunicación de correo electrónico (email-Eu-core) con tamaños variables ($N=20, 100, 240$).
• Geométrico (Astrofísico): Triangulaciones de Delaunay y teselaciones de Voronoi derivadas del catálogo estelar COSMOS, reconstruidas en su extensión completa ($N=119$ y $N=223$).
• Controlado: Dos grafos de 12 vértices (uno unicíclico y otro un árbol) utilizados para verificaciones de consistencia.

Los experimentos se realizan bajo dos regímenes:

1. Régimen de Caminata Finita: Reconstrucción a partir de trayectorias muestreadas de longitud $T$.
2. Régimen de Ruido Multiplicativo: Reconstrucción a partir de una matriz de co-visitación analítica perturbada por ruido gaussiano, aislando la tolerancia del estimador de la cobertura de muestreo.

Resultados Clave

• Reconstrucción de Alta Fidelidad: El flujo de trabajo logra una alta calidad de reconstrucción en todos los bancos de pruebas. En los grafos geométricos de escala completa, recupera las estructuras de Delaunay y Voron la con coeficientes de correlación de Matthews (MCC) de 0.988 y 0.977, respectivamente. En el grafo de correo electrónico empírico ($N=240$), alcanza un MCC de 0.967.
• Comparación con Baselines: El flujo fbLM supera significativamente a un baseline de graphical-lasso. En el grafo Delaunay completo, el baseline devuelve un MCC de 0.540 frente al 0.988 de fbLM.
• Limitación de Cobertura: En el régimen de caminata finita, el factor limitante es la cobertura de la caminata, no el algoritmo de ajuste. El análisis muestra que los falsos negativos corresponden casi exclusivamente a aristas que la caminata aleatoria nunca atravesó. Cuando la caminata cubre el grafo, el estimador recupera las aristas con una fidelidad casi perfecta.
• Robustez al Ruido: En el régimen de ruido multiplicativo (donde todos los pares son candidatos), el método recupera el grafo exactamente a niveles bajos de ruido. Incluso con un 40% de ruido, el método mantiene un ranking perfecto de las aristas (AUC = 1.000), ocurriendo la degradación del rendimiento solo cuando las aristas fuertes caen por debajo del umbral de lectura, no debido a falsos positivos.
• Cuantificación de la Incertidumbre: El método proporciona estimaciones de incertidumbre por arista derivadas de la información de Fisher. Estas incertidumbres son sustancialas (incertidumbre relativa mediana $\sim$30–45%), pero están correctamente localizadas en las aristas de frontera o de baja cobertura, mientras que las aristas interiores permanecen estrechamente restringidas.

Significancia y Reivindicaciones
El artículo afirma establecer un estimador robusto para la reconstrucción de grafos que opera sin conocimiento previo del tamaño, la densidad o la adyacencia de verdad de campo del grafo. Su contribución principal es demostrar que, para grafos geométricos y empíricos, la reconstructibilidad está gobernada por el muestreo del grafo en lugar del estimador.

Los autores enfatizan que:

1. La reconstructibilidad es un problema de muestreo: Si la caminata no visita una arista, ningún estimador puede recuperarla. El método propuesto extrae toda la información disponible de la trayectoria.
2. Los observables de pares son esenciales: El uso de co-visitación en lugar de estadísticas marginales es necesario para distinguir grafos con secuencias de grados idénticas.
3. Autocalibración: El mecanismo de lectura no requiere un ajuste externo o umbrales absolutos, lo que lo hace aplicable a grafos desconocidos.
4. Aplicabilidad Astrofísica: El método se aplica con éxito a grafos geométricos derivados de datos astrofísicos reales (catálogo COSMOS), estableciendo un marco donde el grafo mismo es el objeto de inferencia en lugar de una elección de modelado predefinida.

El artículo concluye que, si bien el estimador es altamente efectivo, el límite práctico de la reconstrucción en escenarios de caminata finita está determinado por la cobertura de la red de la trayectoria, un factor que puede cuantificarse y optimizarse independientemente del procedimiento de ajuste.