Resumo Técnico: Transporte de Operador de Distância Convexo (CDOT)

Declaração do Problema

O Transporte Ótimo (OT) fornece um arcabouço fundamental para comparar medidas de probabilidade, quantificando o custo mínimo para transportar massa. No entanto, o OT clássico baseado na distância de Wasserstein exige que as distribuições de dados residam no mesmo espaço, uma restrição que limita sua aplicação a domínios heterogêneos. As estruturas de Gromov–Wasserstein (GW) e Fused Gromov–Wasserstein (FGW) abordam isso comparando distribuições através de seus espaços métricos-medida (mm) intrínsecos, alinhando informações estruturais sem exigir um custo entre domínios.

Apesar de sua versatilidade, as formulações (F)GW sofrem de uma limitação fundamental: a não-convexidade. Isso ocorre porque o custo GW envolve um produto tensorial do acoplamento ($\pi \otimes \pi$), levando a comparações de distâncias par a par que criam um panorama de otimização não-convexo. Consequentemente, algoritmos de otimização padrão tipicamente convergem apenas para pontos estacionários locais, e as soluções resultantes podem carecer de garantias de otimalidade global. Além disso, as relaxações convexas existentes frequentemente falham em preservar a propriedade de pseudométrico no espaço de espaços mm atribuídos ou requerem parâmetros de suavização adicionais (ex: regularização entrópica) que alteram a geometria do problema.

Metodologia: Transporte de Operador de Distância Convexo (CDOT)

Os autores propõem o Transporte de Operador de Distância Convexo (CDOT), o primeiro arcabouço de transporte ótimo convexo projetado para alinhar espaços mm heterogêneos enquanto preserva tanto a correspondência de características quanto a estrutura geométrica intrínseca.

Formulação Central

O CDOT eleva a estrutura geométrica de cada espaço e o plano de transporte para operadores lineares atuando em espaços $L^2$. Em vez de comparar distâncias par a par diretamente, o CDOT alinha estruturas de distância agregadas via composição de operadores.

Dados dois espaços mm compactos atribuídos $\mathcal{X} = (X, d_X, P_X, f_X)$ e $\mathcal{Y} = (Y, d_Y, P_Y, f_Y)$, e um plano de transporte $\pi \in \Pi(P_X, P_Y)$, o objetivo do CDOT equilibra dois componentes:

1. Alinhamento de Características: $F(\pi) = \mathbb{E}_\pi[\|f_X(X) - f_Y(Y)\|_2^2]$, que incentiva a similaridade elemento a elemento entre as características.
2. Regularização Estrutural: $R(\pi) = \|D_{P_X} T_\pi - T_\pi D_{P_Y}\|_{HS}^2$, que penaliza a discrepância estrutural.

Aqui:

• $D_{P_X}$ e $D_{P_Y}$ são operadores de distância definidos como operadores integrais em $L^2(X, P_X)$ e $L^2(Y, P_Y)$, representando o análogo contínuo de matrizes de distância par a par.
• $T_\pi$ é o operador de esperança condicional associado ao acoplamento $\pi$, mapeando funções de $L^2(Y, P_Y)$ para $L^2(X, P_X)$.
• $\|\cdot\|_{HS}$ denota a norma de Hilbert–Schmidt.

O problema CDOT é formulado como:
$$\inf_{\pi \in \Pi(P_X, P_Y)} \left[ (1-\alpha)F(\pi) + \frac{\alpha}{2}R(\pi) \right]$$

Fundamentos Teóricos

• Convexidade: Os autores provam que o objetivo do CDOT é convexo. Isso é alcançado porque o termo estrutural $R(\pi)$ depende linearmente do operador de esperança condicional $T_\pi$ (que é afim em $\pi$) e a norma quadrada de Hilbert–Schmidt é convexa. Isso contrasta com o GW, onde a dependência quadrática em $\pi$ cria não-convexidade.
• Pseudometricidade: A discrepância resultante do CDOT, definida como a raiz quadrada do valor mínimo do objetivo, é provada para ser um pseudométrico válido no espaço de espaços mm compactos atribuídos.
• Gap de Dispersão: O artigo introduz uma análise de "gap de dispersão" para elucidar formalmente a relação entre CDOT e GW. Mostra-se que o objetivo GW pode ser decomposto no objetivo CDOT mais uma penalidade de dispersão $V(\pi)$, que quantifica a incerteza espacial do acoplamento. A não-convexidade do GW decorre deste termo de dispersão, que favorece acoplamentos determinísticos (concentrados). O CDOT alcança convexidade ao isolar o componente estrutural e descartar esta penalidade.

Otimização

No regime de amostra finita, o problema CDOT reduz-se a um programa quadrático convexo sobre um politopo de transporte. Os autores o resolvem usando o algoritmo de Frank–Wolfe (FW), escolhido por sua natureza livre de projeção. Eles propõem uma variante de "gradiente preguiçoso" que explora a estrutura quadrática para atualizar gradientes de forma eficiente, reduzindo o overhead computacional por iteração de tempo cúbico para quadrático em relação às operações de matriz, embora a complexidade geral permaneça dominada pelo oráculo de minimização linear ($O(n^3)$).

Principais Contribuições

1. Primeiro Arcabouço de OT com Consciência Geométrica Convexa: O CDOT é o primeiro arcabouço a fornecer uma formulação convexa para alinhar espaços mm heterogêneos que recupera explicitamente um plano de transporte ótimo, ao contrário dos métodos baseados em fatiamento (slicing) que apenas estimam a discrepância.
2. Garantias Teóricas:
   • Existência e Convexidade: Provada a existência de um acoplamento ótimo e a convexidade do objetivo sem a necessidade de regularização entrópica.
   • Propriedade de Pseudométrico: Estabelecido que a discrepância CDOT é um pseudométrico válido.
   • Consistência de Risco: Derivados limites de risco não-assintóticos decompostos em erros de otimização e estatísticos, provando que o estimador é consistente em risco sob um algoritmo de Frank–Wolfe de convergência global.
3. Insight Geométrico: A análise do "gap de dispersão" explica formalmente a origem da não-convexidade no GW e demonstra como o CDOT filtra o termo de dispersão para alcançar um panorama convexo.
4. Desempenho Empírico: Demonstrou desempenho superior aos métodos existentes (FGW, Entropic FGW, IsoRank, Spectral Matching, COPT) em nuvens de pontos sintéticas, conectomas cerebrais (OASIS-3) e benchmarks de classificação de grafos (TUDataset).

Resultados Experimentais

• Dados Sintéticos: Em nuvens de pontos agrupadas em 2D, o CDOT consistentemente alcançou o menor Erro Quadrático Médio (MSE) através de vários tamanhos de amostra, mostrando convergência estável. Em contraste, o Entropic FGW (EFGW) exibiu alta sensibilidade ao parâmetro de regularização $\epsilon$, muitas vezes falhando em igualar a precisão do CDOT ou ficando preso em ótimos locais quando $\epsilon$ era pequeno.
• Conectomas Cerebrais (OASIS-3): Em redes cerebrais estruturais, o CDOT superou significativamente o FGW ao utilizar a distância de difusão (uma métrica global robusta), alcançando 61,36% de precisão de correspondência contra 18,53% para o FGW. Os autores atribuem isso à capacidade do CDOT de alinhar perfis geométricos agregados mesmo quando os contrastes par a par são suavizados pela difusão, enquanto o objetivo não-convexo do GW perde poder discriminativo em tais paisagens planas. Sob distância geodésica, o FGW performou ligeiramente melhor, destacando o compromisso entre o alinhamento par a par rígido e o alinhamento global robusto.
• Classificação de Grafos: Nos benchmarks do TUDataset, o CDOT superou consistentemente os métodos de base (FGW, GW, COPT) em precisão de classificação, particularmente em datasets ricos em informação de características (ex: MUTAG, ENZYMES). Notavelmente, o CDOT manteve o melhor desempenho mesmo no dataset IMDB-BINARY (sem características de nós), sugerindo que a geometria baseada em operadores do CDOT captura distinções topológicas de forma mais eficaz que as abordagens GW padrão.

Significância e Alegações

O artigo alega que o CDOT oferece uma alternativa robusta e confiável aos métodos de OT não-convexos existentes para dados estruturados. Ao garantir um panorama de otimização convexo, o CDDT garante a convergência para um ótimo global sem a necessidade de ajuste de hiperparâmetros (como a regularização entrópica) que podem desestabilizar soluções. O arcabouço é particularmente significativo para aplicações envolvendo domínios heterogêneos onde estruturas geométricas intrínsecas devem ser preservadas, como análise de redes cerebrais e classificação de grafos.

Os autores notam modestamente duas limitações:

1. O CDOT é projetado para alinhamento de nível de operador em vez de um emparelhamento estrito um-para-um; uma discrepância zero não implica necessariamente uma isometria preservadora de medida exata.
2. Embora convexo, a implementação atual depende de iterações de Frank–Wolfe dominadas por subproblemas de OT, tornando-o mais adequado para tamanhos de problema moderados do que para configurações de escala muito grande.

Direções futuras sugeridas pelos autores incluem o desenvolvimento de arcabouços de inferência estatística (ex: testes de hipótese para isomorfismo) baseados na discrepância CDOT e a integração do objetivo CDOT como uma camada diferenciável em redes neurais profundas para aprender conjuntamente métricas de solo ideais.