LoRe: Adaptive Interaction-Evaluation Routing with Per-Step Interaction Budgets for Iterative Graph Solvers

Resumen Técnico: LoRe – Enrutamiento Adaptativo de Evaluación de Interacciones para Solucionadores de Grafos Iterativos

1. Enunciado del Problema

Los solucionadores neuronales iterativos para optimización combinatoria (CO), particularmente aquellos basados en modelos de difusión (por ejemplo, DIFUSCO) y Redes Neuronales de Grafos (GNN), enfrentan un cuello de botella crítico de escalabilidad. Aunque estos modelos logran un rendimiento sólido en tareas como el Conjunto Independiente Máximo (MIS) y el Problema del Viajante de Comercio (TSP), su costo de inferencia está dominado por la evaluación repetida y densa de topologías de interacción (por ejemplo, todas las aristas o pares de factores) en cada paso de refinamiento.

Este "barrido de soporte completo" resulta en costos computacionales que escalan como $O(T|A|)$ y un uso máximo de memoria que crece linealmente con el tamaño del conjunto de interacciones $|A|$. En consecuencia, las instancias a gran escala a menudo exceden los límites de memoria del hardware (Out-Of-Memory, o OOM) o incurren en latencia inaceptable. Las soluciones existentes presentan un dilema:

• Reducir pasos (por ejemplo, Destilación): Disminuye el tiempo total pero no reduce la memoria máxima requerida por paso.
• Esparsificación Estática (por ejemplo, grafos kNN fijos): Reduce la memoria por paso pero falla en capturar la naturaleza dependiente del estado de los conflictos combinatorios. En el refinamiento iterativo, los "puntos calientes" de alto conflicto o incertidumbre se desplazan con el tiempo; un soporte disperso fijo inevitablemente pierde interacciones recién críticas, lo que lleva a la acumulación de errores y a la deriva de la trayectoria.

2. Metodología: El Protocolo LoRe

Inspirado en las metodologías computacionales de la física de la materia condensada, específicamente en la Teoría de Campo Medio Dinámico de Clusters (C-DMFT), los autores proponen LoRe (Recomputación Local). LoRe es un envoltorio de inserción directa en tiempo de inferencia, libre de entrenamiento, que impone un presupuesto de evaluación de interacciones por paso.

En lugar de evaluar todas las interacciones, LoRe enruta dinámicamente el cálculo hacia un subconjunto de interacciones que varía en el tiempo ($M_t$), mientras aproxima el resto. Esto operacionaliza una descomposición Cluster-Baño:

• El Cluster ($M_t$): Un subconjunto dinámicamente seleccionado de interacciones de alto conflicto (aristas o pares de factores) que se evalúan exactamente en cada paso.
• El Baño ($A \setminus M_t$): Las interacciones omitidas cuya influencia se aproxima mediante una señal global de recuperación ligera, evitando que el cluster local se desconecte del estado global.

Componentes Técnicos Clave:

1. Enrutamiento Dinámico: En cada paso $t$, LoRe identifica un subconjunto $M_t$ tal que $|M_t| \le \rho|A|$, donde $\rho$ es una razón de presupuesto fija. La selección se basa en una puntuación proxy $s_{t,a}$ que prioriza:
   • Incertidumbre de los Puntos Finales: Interacciones donde los estados de los nodos están indecisos (por ejemplo, $x_i \approx 0.5$).
   • Inestabilidad Temporal: Interacciones donde los estados de los nodos han cambiado significativamente desde el paso anterior.
   • Esqueleto Estático: Un pequeño conjunto fijo de aristas estructuralmente importantes (por ejemplo, nodos de alto grado) se retiene para garantizar la estabilidad estructural.
   • El conjunto $M_t$ se actualiza cada $R$ pasos para rastrear los puntos calientes en desplazamiento.
2. Recuperación Global (Opcional): Para aproximar la influencia del "Baño" omitido, se calcula una señal global de bajo costo $g_t$ mediante agrupación sobre $A \setminus M_t$. Esta señal se acopla al cluster mediante una interpolación ponderada por cobertura libre de parámetros, actuando como una corrección de campo medio.
3. Operador Presupuestado: El operador denso estándar $T_t$ se reemplaza por un operador presupuestado $\tilde{T}_t$ que realiza una evaluación exacta solo en $M_t$ y aplica el término de recuperación para el resto. El post-procesamiento (proyección/reparación) permanece idéntico al de la línea base para garantizar una comparación justa.

3. Contribuciones Clave

• Formulación Conceptual: El artículo formaliza la asignación de presupuesto de operador por paso para solucionadores de grafos iterativos, estableciendo un marco para restringir los envoltorios computacionales y de memoria dentro de cada paso de refinamiento sin alterar el horizonte del solucionador ni los parámetros de la columna vertebral.
• El Protocolo LoRe: Introducción de un envoltorio de tiempo de ejecución libre de entrenamiento que operacionaliza la descomposición Cluster-Baño inspirada en la física. Induce esparsidad temporal del operador mediante enrutamiento dinámico y dependiente del estado, en lugar de esparsificación espacial estática.
• Contabilidad Auditable: Los autores establecen un protocolo de contabilidad de tiempo real completo y de extremo a extremo. Todas las métricas reportadas (tiempo y memoria) incluyen pasos de difusión, sobrecarga de enrutamiento y post-procesamiento, proporcionando un punto de referencia transparente para la inferencia con restricciones de recursos.
• Validación Empírica: Demostración de que el enrutamiento dinámico supera significativamente a las alternativas estáticas sólidas bajo presupuestos equiparados, extendiendo las escalas de inferencia factibles y entregando aceleraciones sustanciales mientras se preserva la calidad de la solución.

4. Resultados Experimentales

Los experimentos se realizaron en el Conjunto Independiente Máximo (MIS) y el Problema del Viajante de Comercio (TSP) utilizando el código DIFUSCO y puntos de control preentrenados.

• Escalabilidad y Viabilidad de Memoria (MIS):

  • LoRe extiende la inferencia factible más de 3 veces más allá del límite OOM de la línea base.
  • En $n=15,000$ nodos (la escala más grande donde la línea base es factible), LoRe logra una aceleración de 8.16 veces y reduce la memoria máxima de la GPU en ~12 veces (de 86.7 GB a 7.32 GB) manteniendo la calidad de la solución (Retención $\approx$ 1.01).
  • La línea base falla (OOM) en $n=20,000$, mientras que LoRe permanece factible hasta $n=50,000$.

• Generalización Transversal a Tareas (TSP):

  • LoRe logra una aceleración de ~15 veces en $n=1,000$ y una reducción de memoria de 44 veces.
  • La calidad de la solución (longitud del recorrido) permanece competitiva con la línea base (Retención 0.94–1.01 a través de escalas).
  • El método se generaliza al TSP sin reentrenamiento, utilizando el mismo punto de control entrenado densamente.

• Validación del Mecanismo (Ablación):

  • Experimentos controlados que comparan LoRe con soportes estáticos (máscaras fijas) y estrategias dinámicas codiciosas confirman que el reenrutamiento dependiente del estado es esencial. Los soportes estáticos fallan al rastrear conflictos en desplazamiento, lo que lleva a una saturación temprana y al fracaso para encontrar soluciones factibles.
  • El enfoque híbrido de LoRe (esqueleto estático + puntos calientes dinámicos) demuestra ser más estable que la selección codiciosa puramente dinámica.

• Robustez:

  • Cambios de Topología Zero-Shot: LoRe mantiene una aceleración de ~8 veces y una reducción de memoria de ~12 veces a través de las familias de grafos Erdős–Rényi (ER), Barabási–Albert (BA) y Watts–Strogatz (WS) sin reentrenamiento.
  • Sensibilidad a Hiperparámetros: El método es en gran medida insensible a los hiperparámetros; una sola configuración ($\rho=0.08, R=10$) funciona efectivamente en diferentes tareas y densidades de grafos.

5. Significado y Afirmaciones

El artículo afirma que LoRe aborda un cuello de botella fundamental en el despliegue de solucionadores neuronales iterativos para optimización combinatoria a gran escala. Al cambiar el paradigma de "evaluación densa" a "enrutamiento dinámico consciente del presupuesto", LoRe transforma el perfil de escalado de estos solucionadores.

• Practicidad: Permite la resolución de instancias de problemas que actualmente son inviables debido a restricciones de memoria (OOM), desplazando efectivamente la frontera de lo que es resoluble en hardware estándar.
• Eficiencia: Entrega aceleraciones sustanciales de tiempo real (hasta 15 veces) y reducciones de memoria (hasta 44 veces) sin requerir reentrenamiento del modelo ni cambios arquitectónicos.
• Generalidad: Como un envoltorio de inserción directa, es agnóstico al paradigma y puede aplicarse a varios solucionadores iterativos (por ejemplo, T2TCO, COExpander) y tareas (MIS, TSP) con una adaptación mínima.

Los autores concluyen que LoRe proporciona un mecanismo riguroso y libre de entrenamiento para imponer restricciones de recursos por paso, haciendo que los solucionadores neuronales iterativos sean viables para sistemas de decisión del mundo real a gran escala donde la latencia y la memoria son restricciones vinculantes.