Tensor Network Structure Search with Program Synthesis

1. O Problema: Busca de Estrutura de Rede Tensorial (TN-SS)

As redes tensoriais (como Tensor Trains, Tucker e Hierarchical Tucker) são ferramentas poderosas para compressão e aproximação de baixo posto de dados multidimensionais. No entanto, a estrutura ótima de uma rede tensorial para um dado tensor de dados depende das características específicas dos dados e dos critérios de otimização (como erro de aproximação vs. tamanho da representação).

O problema central, conhecido como Busca de Estrutura de Rede Tensorial (TN-SS), envolve duas tarefas inter-relacionadas:

1. Busca de Topologia: Identificar a conexão ótima entre os nós (a estrutura do grafo).
2. Busca de Rank: Encontrar os tamanhos de dimensão ideais (ranks) para as arestas.

Desafios das Abordagens Existentes:

• Custo Computacional: Métodos atuais dependem frequentemente de amostragem e validação de milhares de estruturas candidatas, exigindo decomposição tensorial explícita (caríssima) para cada candidato.
• Escalabilidade: Estratégias greedy ou de amostragem falham ao escalar para tensores de alta dimensão ou grandes.
• Subotimidade: Abordagens que tratam topologia e rank separadamente ou que não exploram bem a introdução de nós internos resultam em compressão inferior.

---

2. Metodologia: Síntese de Programas e "Output-Directed Splits"

Os autores reformulam o problema de TN-SS como um problema de Síntese de Programas. Em vez de buscar diretamente em um espaço de grafos, eles buscam em um espaço de "programas de transformação" (sequências de operações de divisão de nós).

2.1. Pipeline Proposto

O algoritmo proposto divide o processo em quatro fases principais (ilustrado na Figura 1 do artigo):

1. Pré-processamento: Cálculo e cache dos valores singulares (SVD) para todas as possíveis matricizações do tensor de entrada.
2. Enumeração de Esboços (Sketches): Geração de programas de transformação simbólicos (esboços) que definem a estrutura, mas não os ranks exatos.
3. Avaliação por Restrições (Scoring): Uso de programação inteira e os valores singulares pré-computados para estimar o custo e a viabilidade de cada esboço sem realizar decomposição tensorial.
4. Decomposição e Arredondamento: Apenas os $k$ esboços mais promissores passam pela decomposição tensorial real e arredondamento para obter a estrutura final.

2.2. Inovação Chave: Output-Directed Splits (Divisões Orientadas à Saída)

Para reduzir o espaço de busca e eliminar estruturas subótimas ou redundantes, os autores introduzem uma nova operação chamada Output-Directed Split (OSplit).

• Diferença para Splits Tradicionais: Splits tradicionais operam em um nó específico. OSplits operam com base em um conjunto de índices livres desejados ($I$) e um rank alvo.
• Funcionamento: O algoritmo procura automaticamente o nó na rede atual que, ao ser dividido, isola o conjunto de índices $I$ em um dos lados da nova aresta.
• Benefícios:
  • Elimina a redundância (diferentes sequências de splits que geram a mesma estrutura).
  • Evita expansões de estruturas que não podem levar a uma solução ótima.
  • Garante que a enumeração foque apenas em partições de índices válidas para árvores.

2.3. Avaliação via Programação Inteira (Constraint Solving)

Em vez de decompor cada candidato, o método utiliza os valores singulares pré-computados do tensor original para criar um limite superior (upper bound) dos valores singulares durante a decomposição progressiva (Teorema 4.1).

• O problema de encontrar o rank ótimo para um esboço é formulado como um problema de Programação Inteira.
• Objetivo: Minimizar o tamanho da rede.
• Restrição: A soma dos erros de truncamento (baseada nos valores singulares) deve estar dentro do limite de erro $\epsilon$.
• Isso permite descartar rapidamente esboços ruins sem gastar tempo em decomposição.

---

3. Principais Contribuições

1. Mudança de Paradigma: Abordagem de TN-SS através da síntese de programas de transformação, permitindo uma exploração abstrata e estruturada do espaço de busca.
2. Output-Directed Splits (OSplits): Uma nova primitiva de operação que substitui os splits baseados em nós, reduzindo drasticamente o espaço de busca ao eliminar estruturas redundantes e subótimas.
3. Separação de Tarefas (Sketch Generation vs. Completion): O método desacopla a busca de topologia da busca de rank. A topologia é gerada como "esboços" (com buracos nos ranks) e completada apenas via resolução de restrições, evitando enumeração exaustiva de ranks.
4. Avaliação sem Decomposição: Uso de valores singulares pré-computados e programação inteira para classificar candidatos, adiando a decomposição tensorial cara apenas para os melhores candidatos.

---

4. Resultados Experimentais

Os autores avaliaram o método em dados sintéticos e reais (Light Fields, BigEarthNet, PDEBench), comparando com Tensor Trains (TT), Hierarchical Tuckers (HT) e métodos de state-of-the-art (como SVDinsTN, TnALE, GreedyTN).

• Velocidade: O método é até 10x mais rápido que as abordagens mais recentes. Em ablações, o uso de OSplits reduziu o número de esboços de 35.727 para apenas 63 em um caso de teste, mantendo a qualidade.
• Compressão: Alcança razões de compressão 1.5x a 3x melhores que os baselines (TT, HT, SVDinsTN).
• Escalabilidade: O método consegue lidar com tensores grandes onde métodos anteriores falham (seja por tempo de execução ou falta de memória).
• Generalização: As topologias descobertas em um lote de treinamento generalizam bem para dados não vistos do mesmo conjunto, permitindo reutilização da estrutura com tempo de execução muito baixo (~110 segundos para decomposição em lotes de teste).

---

5. Significância e Conclusão

Este trabalho representa um avanço significativo na área de álgebra tensorial computacional ao aplicar técnicas de síntese de programas para resolver problemas de otimização estrutural.

• Impacto Prático: Permite a compressão eficiente de dados científicos e de aprendizado de máquina de alta dimensão que antes eram intratáveis devido ao custo computacional da busca de estrutura.
• Rigor Teórico: Fornece garantias de completude (garantia de que a estrutura ótima está dentro do espaço de busca dos OSplits) e limites superiores de erro baseados em propriedades matemáticas dos valores singulares.
• Futuro: Os autores apontam que a extensão para estruturas cíclicas (como Tensor Rings) e tensores de ordem extremamente alta são direções futuras promissoras.

Em resumo, a abordagem proposta transforma um problema de busca combinatória proibitivamente caro em um processo de síntese de programas eficiente, equilibrando rigor algorítmico com eficiência prática.