Containments of Tensor Network Varieties

기술 요약: 텐서 네트워크 변종의 포함 관계 (Containments of Tensor Network Varieties)

문제 정의
본 논문은 텐서 네트워크 변종 간의 포함 관계라는 근본적인 문제를 다룬다. 이진 트리로 인코딩된 두 텐서 포맷이 주어졌을 때, 저자들은 한 네트워크에 의해 표현 가능한 모든 텐서의 집합(변종)이 다른 네트워크에 의해 표현 가능한 집합에 포함되는지 조사한다. 이 문제는 [BBM15]에서 특정 트리 쌍(계층적 트리 및 트레인 트랙 트리)에 대해 해결되었던 "하크부시 추측(Hackbusch Conjecture)"을 일반화한 것이다. 저자들은 평면 임베딩(planar embedding)을 무시하고 임의의 이진 트리를 비교하기 위한 일반적인 프레임워크를 구축하며, 포함 관계의 "비용"을 정량화하고자 한다. 구체적으로, 한 네트워크가 다른 네트워크에 포함되도록 보장하기 위해 하나의 차원 파라미터(dimension parameters, "boost")를 상대방에 대해 얼마나 스케일링해야 하는지를 결정하고자 한다.

방법론
저자들은 완전 이진 루트 트리(full binary rooted trees)의 구조와 그와 관련된 텐서 네트워크 상태(TNS)의 성질에 기반한 조합론적 접근 방식을 채택한다.

1. 정의 및 프레임워크:

   • 텐서 네트워크: 텐서 네트워크는 $(T, \mathcal{V}, f)$로 정의된다. 여기서 $T$는 완전 이진 트리, $\mathcal{V}$는 잎(leaf)에서의 벡터 공간들의 가족, $f$는 각 정점(vertex)에서의 차원을 할당하는 차원 벡터이다.
   • 변종(Varieties): TNS 변종 $TNS(T)$는 모든 정점에서의 계수 제약(rank constraints)을 만족하는 텐서들의 로커스(locus)이며, 이는 각 정점 $v$에 대해 $U_v \subseteq U_{v_1} \otimes U_{v_2}$를 만족하는 선형 부분 공간 $U_v$를 통해 정의된다.
   • 외부 기술(Outer Description): 저자들은 "플래트닝(flattening)" 사상의 계수 조건(rank conditions)을 통해 텐서 수축(tensor contractions)을 사용하여 변종을 특징짓는다. 텐서가 $TNS(T)$에 속한다는 것은 모든 분할$(\downarrow v | \uparrow v)$에 대한 수축의 계수가$f(v)$에 의해 제한됨을 의미한다.
   • 도드 세트(Doad Sets): 중요한 조합론적 도구로 도입된 "도드 세트"(descendant or anti-descendant leaves) $DOAD(T)$는 어떤 정점$v$에 대해$S = \downarrow v$또는$S = \uparrow v$를 만족하는 잎들의 부분집합$S$를 말한다.

2. 포함 기준:

   • 자명한 포함(Trivial Containment): 네트워크 $T$가 $T'$에 자명하게 포함된다는 것은, $T'$의 모든 도드 세트가 $T$의 도드 세트들에 의해 덮여 있으며, 이를 덮는 $T$의 도드 세트들의 차원 파라미터 곱이 $T'$의 파라미터보다 작거나 같음을 의미한다.
   • 점근적 포함 (Lemma 2.11): 저자들은 만약 $T'$의 모든 도드 세트(또는 그 여집합)가 최대 $c_0$개의 $T$의 도드 세트에 의해 덮일 수 있다면, 충분히 큰 스케일링 인자 $r$에 대하여 $TNS(rT) \subseteq TNS(r^{c_0}T')$가 성립함을 입증한다. 이는 **포함 지수(containment exponent)**의 정의로 이어진다.

3. 포함 지수 (The Containment Exponent):

   • 모든 차원 벡터에 대하여 충분히 큰 $r$에 대해 $TNS(rT) \subseteq TNS(r^c T')$가 $c > E$인 모든 $c$에 대해 성립하는 가장 작은 수 $E$로 정의된다.
   • 조합론적 경계: 저자들은 트리의 포셋(poset) 구조에 기반한 경계값을 도출한다. 정리 3.3은 트리 구조로부터 유도된 특정 부분-포셋의 극대 원소의 개수에 기반한 지수 공식을 제공한다.
   • 평면 트리(Plane Trees): 잎의 순서가 정해진 평면 트리의 경우, 저자들은 도드 세트가 구간(interval)에 대응한다는 점을 활용한다. 저자들은 정점의 "높이(height)"와 "쌍대 높이(dual height)"를 도입하여 트레인 트랙 트리($TT_n$)에 대한 포함 관계 및 임의의 평면 트리 간의 포함 관계에 대한 구체적인 경계값을 도출한다(정리 4.4, 따름정리 4.7).

4. 계산적 접근:

   • 저자들은 적은 수의 잎($n \le 8$)에 대해 이러한 지수를 계산하는 알고리즘을 구현하였다.
   • 모든 완전 이진 트리를 생성하기 위해 SageMath 패키지 BinaryTree를 활용하였다.
   • 도드 세트 덮기(doad set coverings)의 전수 조사가 불가능해지는 더 큰 $n$의 경우, 타겟 트리의 분할(splits)을 덮기 위해 필요한 도드 세트의 수를 최소화하는 정수 선형 계획법(ILP)을 구성하였다.

주요 기여 및 결과

• 하크부시 추측의 일반화: 본 논문은 포함 관계 분석을 특정 트리 쌍(계층적 vs 트레인 트랙)에서 임의의 이진 트리 쌍으로 확장하였다.
• 포함 지수의 존재 및 정의: 저자들은 임의의 트리 쌍에 대해 유한한 포함 지수가 존재함을 증명하였으며, 이를 서로 다른 텐서 네트워크 포맷 간의 관계를 정량화하는 척도로 정의하였다.
• 조합론적 경계:
  • $\lfloor n/2 \rfloor$의 일반적인 상계(upper bound)가 제공된다 (명제 3.2).
  • 포셋 구조에 기반한 더 정밀한 경계가 정리 3.3을 통해 제시된다.
  • 평면 트리에 대한 구체적인 경계가 정점 높이를 사용하여 도출되었으며, 트리 $T$가 트레인 트랙 트리 $TT_n$에 포함될 때의 지수는 $\min\{h_\ell, h^*_{\ell+1}\}$의 최댓값과 관련이 있음을 보여준다 (따름정리 4.5).
• 알고리즘 구현: 저자들은 이 지수를 계산하기 위한 알고리즘과 ILP 구성을 제공한다. 저자들은 $n=8$까지의 트리에 대한 전수 조사 결과를 보고하며, 상세한 결과는 별도의 데이터셋 [GM25]에 수집되었다.
• 경계의 비-엄격성(Non-Sharpness): 저자들은 예시(예: 그림 6)를 통해 도출된 조합론적 경계가 반드시 엄격하지(sharp) 않을 수 있음을 보여준다. 어떤 경우에는 실제 포함 지수가 포셋이나 높이 기반 공식에 의해 제공되는 이론적 상계보다 현저히 낮다.

의의 및 주장
저자들은 이 연구를 텐서 네트워크 포함 관계에 대한 더 나은 이해를 위한 "첫 걸음"으로 규정한다. 저자들의 주장은 다음과 같다:

1. 임의의 모양을 가진 이진 트리에 적용 가능한 포함 문제에 대한 일반적인 프레임워크를 제안하였다.
2. 서로 다른 텐서 네트워크 포맷 간의 관계를 정량화하는 새로운 척도인 포함 지수를 도입하였다.
3. 이론적 경계(포셋 구조 및 정수 계획법을 통해)와 작은 $n$에 대한 실험적 데이터를 모두 제공하였다.

논문은 Lemma 2.11의 상계가 항상 엄격한지, 그리고 선형 계획법 완화(linear programming relaxation)의 쌍대 해(dual solutions)를 사용하여 지수의 하계를 주는 텐서를 구성할 수 있는지에 대한 열린 질문을 남기며 겸허하게 마무리된다. 저자들은 포함 지수가 트리 간의 새로운 비대칭적 거리 척도를 제공하며, 기존 문헌의 트리 메트릭들과 비교할 가치가 있다고 제언한다.