A discrete Benamou-Brenier formulation of Optimal Transport on graphs

Resumo Técnico: Formulação Discreta de Benamou-Brenier para Transporte Ótimo em Grafos

1. Problema e Contexto

O artigo aborda o problema de Transporte Ótimo (OT) em domínios discretos, especificamente em grafos. Enquanto a formulação clássica de Kantorovich define a distância de Wasserstein ($W_p$) como um problema de programação linear sobre acoplamentos de medidas, a formulação de Benamou-Brenier (contínua) reparametriza o problema como uma minimização de energia cinética ao longo de um fluxo dinâmico, sujeito a uma equação de transporte (continuidade).

O desafio central identificado pelos autores é que, em domínios discretos (grafos), a interpolação direta entre medidas não permanece no domínio (ex: interpolações de McCann em $\mathbb{R}$ saem do conjunto discreto). Trabalhos anteriores, como os de Erbar e Maas, formularam uma versão discreta para $W_2$, mas essa métrica é Riemanniana e não coincide com a distância de Wasserstein padrão. O problema de uma formulação de Benamou-Brenier válida para $W_1$ (distância de Wasserstein-1) em grafos gerais permanecia aberto, exceto para casos específicos como a reta inteira ($\mathbb{Z}$).

2. Metodologia

Os autores propõem uma nova estrutura matemática baseada em uma Equação de Transporte Discreta que generaliza o caso contínuo.

• Equação de Transporte Discreta:
  Diferentemente do caso contínuo onde a densidade $f$ e o campo de velocidade $v$ são acoplados ($\partial_t f + \nabla \cdot (fv) = 0$), no grafo a velocidade $v$ e uma distribuição auxiliar $g$ residem nas arestas do grafo, enquanto a distribuição de massa $f$ reside nos vértices.
  A equação é definida como:
  $$\partial_t f(t)_x + (\nabla \cdot (v(t)g(t)))_x = 0$$
  Onde:

  • $f(t)$: Distribuição de massa nos vértices.
  • $v(t)$: Campo de velocidade nas arestas.
  • $g(t)$: Distribuição de massa nas arestas (necessária para lidar com a não unicidade da inversão da matriz de incidência em grafos cíclicos).
  • $\nabla \cdot$: Operador de divergência discreto definido via a matriz de incidência $\Omega$.

• Funcional de Energia:
  Define-se um funcional de custo $I_q(v, g)$ para medir a "energia" do transporte:
  $$I_q(v, g) = \left( \int_0^1 \sum_{k \in E} g_k(t) |v_k(t)|^q dt \right)^{1/q}$$
  O objetivo é minimizar este funcional sujeito à equação de transporte, definindo assim uma nova métrica $V_q(f(0), f(1))$.

• Abordagem por Casos:

  1. Grafos Árvore (Trees): Utilizam a estrutura hierárquica para definir "distribuições de cauda" (tail distributions). Demonstram que a solução de velocidade constante é única e minimiza o funcional, recuperando exatamente a fórmula de $W_1$ baseada em cortes (Evans).
  2. Grafos Gerais: Reconhecem que a matriz de incidência não é invertível em grafos com ciclos. Introduzem uma Formulação Reduzida, onde o problema é visto como encontrar um par $(v, g)$ tal que a integral do fluxo ao longo do tempo iguale a diferença entre as distribuições inicial e final ($\Omega \int_0^1 vg \, dt = f(1) - f(0)$).

3. Contribuições Principais

1. Formulação de Benamou-Brenier Discreta para $W_1$:
   Os autores provam que, para qualquer grafo conexo $G$ e qualquer $q \ge 1$, a distância de Wasserstein-1 entre duas distribuições $f(0)$ e $f(1)$ é exatamente igual ao infimum do funcional de energia:
   $$W_1(f(0), f(1)) = \inf_{f,v,g} \left\{ I_q(v, g) : \partial_t f = \Omega \cdot (vg) \right\}$$
   Isso resolve o problema aberto de fornecer uma interpretação dinâmica para $W_1$ em grafos gerais.

2. Classificação de Geodésicas de Velocidade Constante:
   O artigo caracteriza completamente as geodésicas de velocidade constante em grafos. Eles mostram que:

   • Uma geodésica de velocidade constante é induzida por um par $(v, g)$ onde a magnitude da velocidade $|v|$ é constante no tempo e nas arestas.
   • Interpolação Convexa: A interpolação linear simples $f(t) = (1-t)f(0) + tf(1)$ é sempre uma geodésica de velocidade constante para $W_1$ em qualquer grafo.
   • Não Unicidade: Ao contrário de alguns casos contínuos, existem múltiplas geodésicas de velocidade constante entre dois pontos em grafos (ex: interpolação de parâmetros em distribuições binomiais vs. interpolação linear direta).

3. Generalização de Resultados Anteriores:
   Estendem o trabalho de Hillion e Johnson (que tratava de $\mathbb{Z}$) e conectam a formulação dinâmica ao problema estático de Beckmann (fluxo de custo mínimo), mostrando que o fluxo de Beckmann minimizador gera uma geodésica convexa.

4. Resultados Chave

• Teorema 1 (Árvores): Em uma árvore enraizada, a distância $W_1$ é dada pela soma das diferenças absolutas das distribuições de cauda. A formulação dinâmica atinge esse mínimo com soluções de velocidade constante explícitas.
• Teorema 2 (Grafos Gerais): A igualdade $V_q = W_1$ vale para qualquer grafo conexo. O infimum é alcançado por pelo menos uma tripla $(f, v, g)$.
• Proposição 4 (Caracterização das Geodésicas): Estabelece a equivalência entre pares $(v, g)$ de velocidade constante que minimizam o funcional e os caminhos $f(t)$ que são geodésicas de velocidade constante.
• Exemplos Concretos:
  • Binomial: Mostra que tanto a interpolação linear das distribuições quanto a interpolação linear dos parâmetros da distribuição binomial são geodésicas válidas.
  • Ciclos: Demonstra como lidar com graus de liberdade em grafos cíclicos (ex: um ciclo de 4 vértices), onde o fluxo pode ter componentes cíclicos que não afetam o transporte líquido, mas devem ser otimizados para minimizar a energia.

5. Significado e Impacto

• Fundamentação Teórica: O trabalho fornece uma base rigorosa para o cálculo de gradientes e fluxos em espaços de medidas discretas, essencial para aplicações em aprendizado de máquina (Machine Learning) onde os dados são estruturados em grafos (redes sociais, redes biológicas, etc.).
• Flexibilidade de $W_1$: Ao provar que a formulação dinâmica funciona para $W_1$ (e não apenas $W_2$), o artigo permite o uso de métricas mais robustas a outliers em contextos discretos, mantendo a estrutura de cálculo variacional.
• Interpretação Física: A introdução da variável $g$ (distribuição nas arestas) resolve a ambiguidade de direção do fluxo em grafos não orientados ou cíclicos, oferecendo uma interpretação física clara de como a massa se move através da rede.
• Aplicações Práticas: A capacidade de classificar todas as geodésicas de velocidade constante abre caminho para algoritmos de interpolação mais eficientes e para a definição de "gradientes de Wasserstein" em redes complexas, útil em problemas de difusão, agregação de dados e aprendizado de representações.

Em suma, o artigo preenche uma lacuna teórica importante ao unificar a formulação dinâmica de Benamou-Brenier com a métrica de Wasserstein-1 em grafos gerais, oferecendo ferramentas analíticas e computacionais para o transporte ótimo em estruturas discretas complexas.