Containments of Tensor Network Varieties

Resumo Técnico: Contenções de Variedades de Redes de Tensores

Enunciado do Problema
O artigo aborda a questão fundamental da contenção entre variedades de redes de tensores. Dados dois formatos de tensores codificados por árvores binárias, os autores investigam se o conjunto de todos os tensores representáveis por uma rede (a variedade) está contido no conjunto representável por outra. Este problema generaliza a "Conjectura de Hackbusch", que foi resolvida anteriormente para pares específicos de árvores (árvores hierárquicas e de trilha de trem) por Buczyńska et al. [BBM15]. Os autores visam estabelecer um arcabouço geral para comparar árvores binárias arbitrárias, desconsiderando incrustações planas, e para quantificar o "custo" da contenção. Especificamente, buscam determinar o quanto os parâmetros de dimensão (o "impulso" ou boost) de uma rede devem ser escalonados em relação a outra para garantir que a contenção ocorra.

Metodologia
Os autores empregam uma abordagem combinatória fundamentada na estrutura de árvores binárias enraizadas completas e nas propriedades de suas associações de estados de redes de tensores (TNS).

1. Definições e Arcabouço:

   • Redes de Tensores: Definidas como uma tripla $(T, \mathcal{V}, f)$, onde $T$ é uma árvore binária completa, $\mathcal{V}$ é uma família de espaços vetoriais nas folhas, e $f$ é um vetor de dimensões que atribui dimensões a subespaços em cada vértice.
   • Variedades: A variedade TNS(T) é o lócus de tensores que satisfazem restrições de posto em cada vértice, definida via subespaços lineares $U_v$ tal que $U_v \subseteq U_{v_1} \otimes U_{v_2}$.
   • Descrição Externa: Os autores utilizam contrações de tensores para caracterizar a variedade via condições de posto em mapas de "achatamento" (flattening). Um tensor pertence a $TNS(T)$ se o posto de sua contração através de qualquer divisão $(\downarrow v | \uparrow v)$ for limitado por $f(v)$.
   • Conjuntos Doad: Uma ferramenta combinatória crucial introduzida é o "conjunto doad" (folhas descendentes ou anti-descendentes), denotado por $DOAD(T)$. Estes são subconjuntos de folhas $S$ tais que $S = \downarrow v$ ou $S = \uparrow v$ para algum vértice $v$.

2. Critérios de Contenção:

   • Contenção Trivial: Uma rede $T$ é trivialmente contida em $T'$ se todo conjunto doad de $T'$ puder ser coberto por conjuntos doad de $T$ de tal forma que o produto dos parâmetros de dimensão dos conjuntos de cobertura em $T$ seja menor ou igual ao parâmetro em $T'$.
   • Contenção Assintótica (Lema 2.11): Os autores estabelecem que, se todo conjunto doad (ou seu complemento) de $T'$ puder ser coberto por no máximo $c_0$ conjuntos doad de $T$, então para um fator de escala $r$ suficientemente grande, $TNS(rT) \subseteq TNS(r^{c_0}T')$. Isso leva à definição do expoente de contenção.

3. O Expoente de Contenção:

   • Definido como o menor número $E$ tal que para todos os vetores de dimensão e para $r$ suficientemente grande, $TNS(rT) \subseteq TNS(r^c T')$ ocorre para todo $c > E$.
   • Limites Combinatórios: Os autores derivam limites baseados na estrutura de posse (poset) das árvores. O Teorema 3.3 fornece uma fórmula para um expoente baseado no número de elementos maximais em sub-possets específicos derivados das estruturas das árvores.
   • Árvores Planas: Para árvores planas (onde as folhas são ordenadas), os autores exploram o fato de que os conjuntos doad correspondem a intervalos. Eles introduzem "altura" e "altura dual" de vértices para derivar limites específicos para a contenção relativa à árvore de trilha de trem ($TT_n$) e entre árvores planas arbitrárias (Teorema 4.4, Corolário 4.7).

4. Abordagem Computacional:

   • Os autores implementaram um algoritmo para computar esses expoentes para pequenos números de folhas ($n \le 8$).
   • Utilizaram o pacote SageMath BinaryTree para gerar todas as árvores binárias completas.
   • Para $n$ maiores, onde a busca exaustiva de coberturas de conjuntos doad torna-se inviável, eles formularam um Programa Linear Inteiro (ILP) para minimizar o número de conjuntos doad necessários para cobrir as divisões da árvore alvo.

Contribuições Principais e Resultados

• Generalização da Conjectura de Hackbusch: O artigo estende a análise de contenção de pares específicos de árvores (hierárquica vs. trilha de trem) para quaisquer pares de árvores binárias.
• Existência e Definição de Expoentes de Contenção: Os autores provam a existência de um expoente de contenção finito para qualquer par de árvores e o definem como uma medida do escalonamento de parâmetros necessário para a contenção.
• Limites Combinatórios:
  • Um limite superior geral de $\lfloor n/2 \rfloor$ é fornecido (Proposição 3.2).
  • Um limite mais apertado baseado na estrutura de posse das árvores é apresentado no Teorema 3.3.
  • Limites específicos para árvores planas são derivados usando alturas de vértices, mostrando que o expoente para uma árvore $T$ na árvore de trilha de trem $TT_n$ está relacionado ao máximo de $\min\{h_\ell, h^*_{\ell+1}\}$ (Corolário 4.5).
• Implementação Algorítmica: Os autores fornecem um algoritmo e uma formulação de ILP para computar esses expoentes. Eles relatam sobre uma busca exaustiva para árvores com até $n=8$ folhas, com resultados detalhados coletados em um conjunto de dados separado [GM25].
• Não-Nitidez dos Limites: O artigo demonstra, através de exemplos (por exemplo, Figura 6), que os limites combinatórios derivados não são necessariamente nítos (sharp). Em alguns casos, o expoente de contenção real é significativamente menor do que o limite superior teórico fornecido pelas fórmulas de posse ou de altura.

Significância e Alegações
Os autores posicionam este trabalho como um "primeiro passo" para uma melhor compreensão das contenções de redes de tensores. Eles alegam ter:

1. Proposto um arcabouço geral para a questão da contenção que se aplica a árvores binárias de formas arbitrárias.
2. Introduzido uma nova medida, o expoente de contenção, que quantifica a relação entre diferentes formatos de redes de tensores.
3. Fornecido tanto limites teóricos (via estruturas de posse e programação inteira) quanto dados experimentais para pequenos $n$.

O artigo conclui modestamente, observando que, embora os limites sejam úteis, eles nem sempre são nítos. Os autores identificam questões em aberto sobre se os limites superiores do Lema 2.11 são sempre nítos e se soluções duais da relaxação de programação linear podem ser usadas para construir tensores que gerem limites inferiores para os expoentes. Eles sugerem que o expoente de contenção oferece uma nova medida de distância não simétrica para árvores, justificando novas comparações com métricas de árvore existentes na literatura.