Resumo Técnico: Modelagem Generativa em Grafos Métricos via Transporte Ótimo Neural

Declaração do Problema

Muitos conjuntos de dados científicos e geométricos, como redes rodoviárias, estruturas vasculares e sistemas fluviais, são naturalmente suportados em grafos métricos. Um grafo métrico é um espaço geodésico unidimensional onde as arestas carregam comprimentos e são tratadas como intervalos contínuos. As abordagens de modelagem generativa existentes enfrentam uma limitação fundamental: os métodos padrão geram pontos em um espaço euclidiano ambiente, falhando em garantir que as amostras permaneçam suportadas no grafo ou respeitem sua geometria métrica intrínseca.

Inversamente, as abordagens tradicionais de Transporte Ótimo (OT) para grafos frequentemente dependem da discretização, aproximando distribuições contínuas com medidas baseadas em nós finitos. Embora acessível computacionalmente, essa abordagem introduz aproximações dependentes da malha e escala mal à medida que a discretização é refinada, perdendo a natureza contínua do domínio original.

O artigo aborda a necessidade de um framework generativo contínuo, suportado por grafos, que possa aproveitar estruturas ambientes suaves para computação sem sacrificar a fidelidade geométrica do grafo métrico.

Metodologia

Os autores propõem um framework de modelagem generativa profunda que incorpora o grafo métrico em um espaço ambiente suave, resolve um problema de OT entrópico lá e projeta as amostras de volta ao grafo. O pipeline consiste em três estágios principais:

1. Incorporação (Embedding): O grafo métrico $\Gamma$ é incorporado em uma variedade ambiente suave $M_\Psi$ via uma aplicação $\Psi$. O artigo investiga duas incorporações específicas:

   • Realização Euclidiana Extrínseca ($\iota$): Mapeia o grafo para $\mathbb{R}^m$ (ex: coordenadas planas de uma rede rodoviária).
   • Incorporação Abel–Jacobi Tropical Intrínseca ($\Phi_p$): Mapeia o grafo para seu Toro de Jacobian Tropical $J(\Gamma)$. Esta incorporação depende apenas dos comprimentos das arestas e da estrutura de ciclos, fornecendo uma geometria intrínseca independente de um desenho euclidiano específico.

2. Transporte Ótimo Entrópico Neural:

   • As medidas de origem ($P_\Gamma$) e destino ($Q_\Gamma$) são empurradas para o espaço ambiente ($P_\Psi, Q_\Psi$).
   • Um problema de Kantorovich entrópico é resolvido entre essas medidas incorporadas usando uma parametrização semidual neural.
   • Diferente das formulações de Monge baseadas em mapas, esta abordagem aprende um acoplamento (plano). O potencial do lado do destino é parametrizado por uma rede neural $g_\theta$.
   • Para gerar saídas contínuas em vez de amostras restritas a átomos de destino, a lei condicional aprendida é suavizada usando o núcleo de calor ambiente (heat kernel). Isso produz amostras no espaço ambiente que podem não estar exatamente sobre o grafo incorporado.

3. Recuperação (Projeção–Pullback):

   • Como as amostras suavizadas pelo calor podem cair fora do grafo incorporado, uma projeção pelo ponto mais próximo no grafo incorporado $\Psi(\Gamma)$ é realizada.
   • A aplicação inversa $\Psi^{-1}$ é então aplicada para mapear o ponto projetado de volta ao grafo métrico original $\Gamma$.
   • O gerador final é construído como $\rho_\Gamma^\Psi = \Psi^{-1} \circ \text{proj}_{\Psi(\Gamma)}$, garantindo que todas as amostras geradas estejam estritamente suportadas no grafo original.

Principais Contribuições

1. Primeiro Framework Generativo Profundo para Grafos Métricos: O artigo introduz, tanto quanto os autores sabem, o primeiro modelo generativo profundo para distribuições de probabilidade continuamente suportadas em grafos métricos compactos.
2. Geometrias de Incorporação Duais: O framework é desenvolvido para duas geometrias de transporte distintas:
   • Uma realização euclidiana extrínseca.
   • A incorporação Abel–Jacobi tropical intrínseca no toro de Jacobian.
3. Convergência Teórica: Os autores provam que, no limite conjunto do aumento da expressividade neural e do desaparecimento da escala de calor, o gerador de projeção–pullback suavizado pelo calor aprendido converge fracamente para um acoplamento válido entre as medidas do grafo original. Isso garante que, apesar de aprender no espaço ambiente, o objeto limite é um acoplamento legítimo no grafo.
4. Tratamento de Pontes (Bridges): O método inclui uma aumentação canônica (adição de arestas paralelas virtuais) para lidar com pontes no grafo, garantindo que o mapa Abel–Jacobi tropical permaneça injetivo e que o grafo possa ser recuperado de sua imagem.

Resultados Experimentais

O método foi avaliado através de benchmarks sintéticos e dados do mundo real:

• Benchmarks Sintéticos: Testado em grafos theta, roda (wheel), grade (grid) e pequenas redes rodoviárias. As variantes de OT neural (tanto Tropical quanto Euclidiana) consistentemente reduziram o erro (em termos de distância de Wasserstein intrínseca do grafo $W_1^\Gamma, W_2^\Gamma$ e erros de densidade/CDF $L_1$) em comparação com baselines heurísticos baseados em OT de grafo discreto (interpolação de nós e pushforward ambiente). As duas geometrias de incorporação performaram de forma comparável, sugerindo que o ganho primário vem da regra de transporte amortizada e não de uma vantagem específica de incorporação.
• Escalabilidade: O método neural escala favoravelmente com o tamanho do suporte. Ao contrário dos métodos de OT de grafo explícitos por pares, que exigem a avaliação de distâncias de caminho mais curto intrínsecas em grandes pares de suporte, o método neural treina em minibatches e aplica a regra aprendida via inferência em lote.
• Aplicação no Mundo Real: O framework foi aplicado a um milhão de localizações de embarque da Uber em Manhattan, Nova York.
  • A tarefa era a geração de densidade espacial suportada por grafo (aprender a gerar embarques a partir de uma fonte rodoviária uniforme).
  • Baselines de OT de grafo denso eram inviáveis nesta escala devido a restrições de memória ($10^{12}$ custos de pares).
  • O modelo Euclidiano Neural (Gromov) conseguiu gerar amostras que recuperaram a estrutura dominante de embarques no grafo rodoviário de Manhattan, superando baselines heurísticos treinados em um subconjunto amostrado (16.384 pontos).

Significância e Alegações

O artigo afirma fornecer uma solução principista para a modelagem generativa em grafos métricos que evita as armadilhas da discretização. Ao resolver o problema de transporte em um espaço ambiente suave e recuperar amostras suportadas pelo grafo via projeção, o método retém a geometria contínua do domínio.

Os autores enfatizam que sua abordagem é baseada em planos (plan-based) em vez de baseada em mapas, permitindo o tratamento de medidas singulares no grafo sem suavizá-las em densidades ambientes. A garantia teórica de convergência fraca para um acoplamento válido assegura que o método não é meramente uma heurística, mas possui uma fundação rigorosa na teoria do transporte ótimo.

O trabalho demonstra que o OT neural pode ser adaptado para domínios geométricos unidimensionais não euclidianos, oferecendo uma alternativa escalável ao OT de grafo discreto para aplicações que variam de mobilidade urbana a redes biológicas. Os autores observam limitações, incluindo a natureza assintótica da prova de convergência (sem taxas de amostra finita) e o foco atual em geração incondicional em vez de previsão temporal ou condicionada por covariáveis.