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

Resumo Técnico: LoRe – Roteamento Adaptativo de Avaliação de Interação para Solucionadores Iterativos de Grafos

1. Declaração do Problema

Solucionadores neurais iterativos para otimização combinatória (CO), particularmente aqueles baseados em modelos de difusão (por exemplo, DIFUSCO) e Redes Neurais em Grafos (GNNs), enfrentam um gargalo crítico de escalabilidade. Embora esses modelos alcancem alto desempenho em tarefas como o Conjunto Independente Máximo (MIS) e o Problema do Caixeiro Viajante (TSP), seu custo de inferência é dominado pela avaliação repetida e densa de topologias de interação (por exemplo, todas as arestas ou pares de fatores) em cada etapa de refinamento.

Essa "varredura de suporte total" resulta em custos computacionais que escalam como $O(T|A|)$ e no uso de memória de pico crescendo linearmente com o tamanho do conjunto de interação $|A|$. Consequentemente, instâncias em grande escala frequentemente excedem os limites de memória de hardware (Fora de Memória, ou OOM) ou incorrem em latência inaceitável. As soluções existentes apresentam um dilema:

• Redução de etapas (por exemplo, Destilação): Reduz o tempo total, mas não reduz a memória de pico necessária por etapa.
• Esparsificação Estática (por exemplo, grafos kNN fixos): Reduz a memória por etapa, mas falha em capturar a natureza dependente do estado dos conflitos combinatórios. No refinamento iterativo, os "pontos críticos" de alto conflito ou incerteza deslocam-se ao longo do tempo; um suporte esparsificado fixo inevitavelmente perde interações recém-críticas, levando ao acúmulo de erros e ao desvio de trajetória.

2. Metodologia: O Protocolo LoRe

Inspirado pelas metodologias computacionais da física da matéria condensada — especificamente a Teoria do Campo Médio Dinâmica de Clusters (C-DMFT) —, os autores propõem o LoRe (Recomputação Local). O LoRe é um wrapper de inferência, livre de treinamento, que impõe um orçamento de avaliação de interação por etapa.

Em vez de avaliar todas as interações, o LoRe roteia dinamicamente o cálculo para um subconjunto variável no tempo de interações ($M_t$), enquanto aproxima o restante. Isso operacionaliza uma decomposição Cluster-Banho:

• O Cluster ($M_t$): Um subconjunto dinamicamente selecionado de interações de alto conflito (arestas ou pares de fatores) que são avaliadas exatamente em cada etapa.
• O Banho ($A \setminus M_t$): As interações omitidas cuja influência é aproximada via um sinal global leve de recordação, impedindo que o cluster local se desconecte do estado global.

Componentes Técnicos Principais:

1. Roteamento Dinâmico: Em cada etapa $t$, o LoRe identifica um subconjunto $M_t$ tal que $|M_t| \le \rho|A|$, onde $\rho$ é uma razão de orçamento fixa. A seleção baseia-se em uma pontuação proxy $s_{t,a}$ que prioriza:
   • Incerteza de Extremidade: Interações onde os estados dos nós são indecisos (por exemplo, $x_i \approx 0.5$).
   • Instabilidade Temporal: Interações onde os estados dos nós mudaram significativamente desde a etapa anterior.
   • Esqueleto Estático: Um pequeno conjunto fixo de arestas estruturalmente importantes (por exemplo, nós de alto grau) é mantido para garantir estabilidade estrutural.
   • O conjunto $M_t$ é atualizado a cada $R$ etapas para rastrear pontos críticos em deslocamento.
2. Recordação Global (Opcional): Para aproximar a influência do "Banho" omitido, um sinal global de baixo custo $g_t$ é computado via agrupamento sobre $A \setminus M_t$. Este sinal é acoplado ao cluster via uma interpolação ponderada pela cobertura, livre de parâmetros, atuando como uma correção de campo médio.
3. Operador Orçamentado: O operador denso padrão $T_t$ é substituído por um operador orçamentado $\tilde{T}_t$ que realiza avaliação exata apenas em $M_t$ e aplica o termo de recordação para o restante. O pós-processamento (projeção/reparo) permanece idêntico ao da linha de base para garantir comparação justa.

3. Contribuições Principais

• Formulação Conceitual: O artigo formaliza o orçamento de operador por etapa para solucionadores iterativos de grafos, estabelecendo uma estrutura para restringir os envelopes computacionais e de memória dentro de cada etapa de refinamento sem alterar o horizonte do solucionador ou os parâmetros da espinha dorsal.
• O Protocolo LoRe: Introdução de um wrapper de tempo de execução livre de treinamento que operacionaliza a decomposição Cluster-Banho inspirada na física. Ele induz esparsidade temporal de operadores via roteamento dinâmico e dependente do estado, em vez de esparsificação espacial estática.
• Contabilidade Auditável: Os autores estabelecem um protocolo de contabilidade de tempo de parede totalmente inclusivo, de ponta a ponta. Todas as métricas relatadas (tempo e memória) incluem etapas de difusão, sobrecarga de roteamento e pós-processamento, fornecendo um benchmark transparente para inferência com restrições de recursos.
• Validação Empírica: Demonstração de que o roteamento dinâmico supera significativamente alternativas estáticas robustas sob orçamentos correspondidos, estendendo as escalas de inferência viáveis e entregando acelerações substanciais enquanto preserva a qualidade da solução.

4. Resultados Experimentais

Os experimentos foram conduzidos no Conjunto Independente Máximo (MIS) e no Problema do Caixeiro Viajante (TSP) usando o código DIFUSCO e checkpoints pré-treinados.

• Escalabilidade e Viabilidade de Memória (MIS):

  • O LoRe estende a inferência viável em mais de 3× além do limite de OOM da linha de base.
  • Em $n=15.000$ nós (a maior escala onde a linha de base é viável), o LoRe alcança uma aceleração de 8,16× e reduz a memória de pico da GPU em ~12× (de 86,7 GB para 7,32 GB), mantendo a qualidade da solução (Retenção $\approx$ 1,01).
  • A linha de base falha (OOM) em $n=20.000$, enquanto o LoRe permanece viável até $n=50.000$.

• Generalização entre Tarefas (TSP):

  • O LoRe alcança uma aceleração de ~15× em $n=1.000$ e uma redução de memória de 44×.
  • A qualidade da solução (comprimento do tour) permanece competitiva com a linha de base (Retenção 0,94–1,01 em várias escalas).
  • O método generaliza para o TSP sem retreinamento, usando o mesmo checkpoint treinado densamente.

• Validação do Mecanismo (Ablação):

  • Experimentos controlados comparando o LoRe com suportes estáticos (máscaras fixas) e estratégias dinâmicas gananciosas confirmam que o re-roteamento dependente do estado é essencial. Suportes estáticos falham em rastrear conflitos em deslocamento, levando à saturação precoce e à incapacidade de encontrar soluções viáveis.
  • A abordagem híbrida do LoRe (esqueleto estático + pontos críticos dinâmicos) prova-se mais estável do que a seleção puramente dinâmica e gananciosa.

• Robustez:

  • Deslocamentos de Topologia Zero-Shot: O LoRe mantém ~8× de aceleração e ~12× de redução de memória em famílias de grafos Erdős–Rényi (ER), Barabási–Albert (BA) e Watts–Strogatz (WS) sem retreinamento.
  • Sensibilidade a Hiperparâmetros: O método é largamente insensível a hiperparâmetros; uma única configuração ($\rho=0,08, R=10$) funciona efetivamente em diferentes tarefas e densidades de grafos.

5. Significado e Alegações

O artigo alega que o LoRe aborda um gargalo fundamental na implantação de solucionadores neurais iterativos para otimização combinatória em grande escala. Ao mudar o paradigma de "avaliação densa" para "roteamento dinâmico consciente de orçamento", o LoRe transforma o perfil de escalabilidade desses solucionadores.

• Praticidade: Permite a solução de instâncias de problemas que atualmente são inviáveis devido a restrições de memória (OOM), efetivamente deslocando a fronteira do que é solucionável em hardware padrão.
• Eficiência: Entrega acelerações substanciais de tempo de parede (até 15×) e reduções de memória (até 44×) sem exigir retreinamento do modelo ou alterações arquitetônicas.
• Generalidade: Como um wrapper plug-and-play, é agnóstico ao paradigma e pode ser aplicado a vários solucionadores iterativos (por exemplo, T2TCO, COExpander) e tarefas (MIS, TSP) com adaptação mínima.

Os autores concluem que o LoRe fornece um mecanismo rigoroso e livre de treinamento para impor restrições de recursos por etapa, tornando os solucionadores neurais iterativos viáveis para sistemas de decisão do mundo real em grande escala, onde latência e memória são restrições vinculantes.