Information-geometric adaptive sampling for graph diffusion

1. Formulação do Problema

Os modelos de difusão em grafos emergiram como um framework poderoso para gerar estruturas relacionais complexas (por exemplo, moléculas, redes sociais). No entanto, os métodos de amostragem padrão dependem de passos de tempo uniformes (discretização de passo fixo) para resolver a Equação Diferencial Estocástica (EDE) reversa no tempo. Esta abordagem sofre de duas limitações críticas:

• Dinâmicas Não Homogêneas: A evolução da distribuição de probabilidade durante o processo reverso não é uniforme. Em regimes de alto ruído, as dinâmicas são suaves, enquanto em regimes de baixo ruído (próximos à distribuição de dados), as dinâmicas tornam-se "rígidas" com mudanças rápidas no campo de deriva.
• Ineficiência e Instabilidade: Solucionadores de passo fixo alocam recursos de forma ineficiente. Eles realizam passos desnecessariamente pequenos em regiões suaves (desperdiçando computação) e passos excessivamente grandes em regiões rígidas (causando erros numéricos, instabilidade ou perda de fidelidade estrutural).
• Limitações das Soluções Existentes: Estratégias adaptativas atuais dependem de agendamentos heurísticos (por exemplo, agendamentos quadráticos) ou estimativas de erro no espaço de estados. Estes são estáticos ou ignoram a geometria intrínseca do caminho probabilístico, falhando em adaptar-se à rigidez específica de diferentes conjuntos de dados ou arquiteturas de modelos.

2. Metodologia

Os autores propõem um framework de Amostragem Adaptativa Geometricamente Informada que reinterpreta a trajetória de amostragem de difusão como uma curva paramétrica em uma variedade estatística Riemanniana.

A. Fundamentação Teórica: Métrica de Fisher-Rao

• Os kernels de transição induzidos pela EDE reversa no tempo são tratados como uma família de distribuições Gaussianas parametrizadas pelo vetor de deriva local $f_t$.
• Os autores equipam esta variedade com a métrica de Fisher-Rao, que fornece uma medida principial da distância intrínseca entre distribuições.
• Eles derivam a Pontuação de Variação de Deriva (DVS), um indicador sensível à geometria que quantifica a taxa instantânea de mudança informacional. A DVS é definida como a razão entre o quadrado do comprimento de arco de Fisher-Rao e o incremento de tempo:
  $$V_t = \frac{\|df_t\|^2}{g_t^2}$$
  onde $df_t$ é a mudança no campo de deriva e $g_t$ é a escala de ruído.

B. O Amostrador Adaptativo Guiado por DVS

O mecanismo central impõe uma velocidade informacional constante ao longo da trajetória de amostragem. Em vez de passos de tempo fixos, o amostrador ajusta o tamanho do passo $\Delta t$ para manter um incremento de comprimento de arco constante ($\Delta s^2 \approx \text{constante}$).

• Alta DVS (Alta Curvatura/Rigidez): Indica variação rápida da deriva. O solucionador reduz o tamanho do passo para garantir estabilidade numérica e rastrear a EDE com precisão.
• Baixa DVS (Baixa Curvatura/Estabilidade): Indica evolução suave. O solucionador expande o tamanho do passo para acelerar a amostragem sem sacrificar a precisão.

C. Implementação para Grafos

Como os grafos consistem em características de nós acopladas ($X$) e estruturas de adjacência ($A$) com velocidades de remoção de ruído diferentes, o método calcula pontuações DVS separadas para nós ($V_X$) e arestas ($V_A$).

• Estado Global: Uma Média Móvel Exponencial (EMA) suaviza os sinais DVS para filtrar ruído estocástico.
• Controle de Gargalo: O tamanho do passo final é determinado pelo mínimo dos tamanhos de passo de nós e arestas ($\Delta t = \min(\Delta t_X, \Delta t_A)$) para garantir estabilidade global.
• Plug-and-Play: O método é livre de treinamento e pode ser integrado em solucionadores existentes (Euler-Maruyama ou Heun) com sobrecarga computacional negligenciável.

3. Contribuições Principais

1. Framework Geometricamente Informado: Formaliza a amostragem de difusão em grafos como uma curva em uma variedade Riemanniana equipada com a métrica de Fisher-Rao, indo além da discretização de tempo heurística.
2. Pontuação de Variação de Deriva (DVS): Deriva uma métrica interpretável e livre de treinamento que quantifica explicitamente a taxa instantânea de mudança distribucional, servindo como um sinal de feedback principial para rigidez local.
3. Design de Amostrador Adaptativo: Propõe um solucionador que escala dinamicamente os tamanhos de passo para alcançar uma progressão de comprimento de arco igual, equilibrando efetivamente a fidelidade numérica e a eficiência de amostragem.
4. Validação Empírica: Demonstra que o amostrador DVS supera consistentemente agendamentos padrão de passo fixo e não uniformes heurísticos em benchmarks de grafos moleculares e gerais.

4. Resultados Experimentais

O método foi avaliado em conjuntos de dados moleculares (QM9, ZINC250k) e conjuntos de dados de grafos gerais (Planar, SBM, Ego-small) usando os modelos GruM e GDSS.

• Geração Molecular:

  • Fidelidade: A DVS melhorou significativamente a Distância Fréchet ChemNet (FCD) e as pontuações de Valididade em comparação com agendamentos de Passo Fixo e Quadrático. Por exemplo, no QM9 com o solucionador Euler, a DVS alcançou uma FCD de 0,095 versus 0,107 para a linha de base.
  • Eficiência: A DVS convergiu mais rápido, alcançando valores de erro mais baixos com menos avaliações de função (por exemplo, 787 passos versus 1000 para a linha de base).
  • Insight: A alocação estratégica de passos baseada na geometria da variedade foi encontrada como mais impactante do que simplesmente aumentar a ordem do integrador numérico (por exemplo, DVS-Euler frequentemente superou Heun de Passo Fixo).

• Geração de Grafos Gerais:

  • Fidelidade Estrutural: A DVS alcançou pontuações mais baixas de Discrepância Média Máxima (MMD) em propriedades de grau, agrupamento, órbita e espectro, indicando melhor preservação da topologia global e motivos locais.
  • Qualidade Visual: Instantâneos mostraram que a DVS produziu esqueletos planares mais limpos e estruturas comunitárias mais distintas em grafos SBM, resolvendo arestas "ruidosas" de forma mais eficaz durante a fase de cristalização rígida.

• Estudos de Ablação:

  • O fator de escala de agregação $\gamma$ foi ajustado para equilibrar a intensidade do feedback. Configurações ótimas produziram melhorias significativas na qualidade de geração enquanto reduziam o custo computacional em ~25% em comparação com linhas de base de passo fixo.
  • A análise de tempo de execução confirmou que a sobrecarga de calcular a DVS é negligenciável (<7% por passo), resultando em economias líquidas de tempo devido à redução do total de passos.

5. Significância

Este artigo aborda uma ineficiência fundamental na geração de grafos baseada em difusão: o descompasso entre a discretização de tempo uniforme e as dinâmicas distribucionais não uniformes. Ao mudar a perspectiva de tempo para geometria informacional, os autores fornecem um mecanismo adaptativo rigoroso que:

• Aumenta a Fidelidade Estrutural: Crucial para aplicações como descoberta de fármacos, onde pequenos erros numéricos podem levar a moléculas quimicamente inválidas.
• Melhora a Eficiência: Reduz o número de passos de amostragem necessários sem retreinar modelos.
• Generaliza: Oferece uma solução universal e livre de treinamento aplicável a várias arquiteturas de grafos e conjuntos de dados, preenchendo a lacuna entre análise numérica e teoria da informação na modelagem generativa.