Containments of Tensor Network Varieties

Technische Zusammenfassung: Einbettungen von Varietäten von Tensornetzwerken

Problemstellung
Die Arbeit befasst sich mit der grundlegenden Frage der Einbettung (Containment) zwischen Varietäten von Tensornetzwerken. Gegeben seien zwei Tensorformate, die durch binäre Bäume kodiert sind; die Autoren untersuchen, ob die Menge aller durch ein Netzwerk darstellbaren Tensoren (die Varietät) in der Menge enthalten ist, die durch ein anderes Netzwerk darstellbar ist. Dieses Problem verallgemeinert die „Hackbusch-Vermutung“, die zuvor für spezifische Paare von Bäumen (hierarchische und Train-Track-Bäume) durch Buczyńska et al. [BBM15] gelöst wurde. Die Autoren streben einen allgemeinen Rahmen an, um beliebige binäre Bäume zu vergleichen, wobei die planaren Einbettungen vernachlässigt werden, und um die „Kosten“ der Einbettung zu quantifizieren. Konkret suchen sie zu bestimmen, wie stark die Dimensionsparameter (der „Boost“) eines Netzwerks relativ zu einem anderen skaliert werden müssen, damit die Einbettung gilt.

Methodik
Die Autoren verwenden einen kombinatorischen Ansatz, der auf der Struktur von vollen binären Wurzelbäumen und den Eigenschaften der mit ihnen assoziierten Tensornetzwerkzustände (TNS) basiert.

1. Definitionen und Rahmenbedingungen:

   • Tensornetzwerke: Definiert als Tripel $(T, \mathcal{V}, f)$, wobei $T$ ein voller binärer Baum ist, $\mathcal{V}$ eine Familie von Vektorräumen an den Blättern darstellt und $f$ einen Dimensionsvektor bezeichnet, der die Dimensionen der Unterräume an jedem Knoten zuweist.
   • Varietäten: Die TNS-Varietät $TNS(T)$ ist der Ort der Tensoren, die an jedem Knoten Rangbeschränkungen erfüllen, definiert über lineare Unterräume $U_v$ sodass $U_v \subseteq U_{v_1} \otimes U_{v_2}$.
   • Äußere Beschreibung: Die Autoren nutzen Tensor-Kontraktionen, um die Varietät über Rangbedingungen auf „Flattening“-Abbildungen zu charakterisieren. Ein Tensor gehört zu $TNS(T)$, wenn der Rang seiner Kontraktion über jeden Split $(\downarrow v | \uparrow v)$ durch $f(v)$ beschränkt ist.
   • Doad-Mengen: Ein entscheidendes kombinatorisches Werkzeug, das als „Doad-Menge“ (Descendant oder Anti-Descendant Blätter) bezeichnet wird, bezeichnet $DOAD(T)$. Dies sind Teilmengen der Blätter $S$, sodass $S = \downarrow v$ oder $S = \uparrow v$ für einen Knoten $v$ gilt.

2. Einbettungskriterien:

   • Triviale Einbettung: Ein Netzwerk $T$ ist trivial in $T'$ enthalten, wenn jede Doad-Menge von $T'$ durch Doad-Mengen von $T$ abgedeckt werden kann, sodass das Produkt der Dimensionsparameter der abdeckenden Mengen in $T$ kleiner oder gleich dem Parameter in $T'$ ist.
   • Asymptotische Einbettung (Lemma 2.11): Die Autoren stellen fest, dass, falls jede Doad-Menge (oder deren Komplement) durch höchstens $c_0$ Doad-Mengen von $T$ abgedeckt werden kann, für einen ausreichend großen Skalierungsfaktor $r$ gilt: $TNS(rT) \subseteq TNS(r^{c_0}T')$. Dies führt zur Definition des Einbettungsexponenten.

3. Der Einbettungsexponent:

   • Definiert als die kleinste Zahl $E$, sodass für alle Dimensionsvektoren und ein ausreichend großes $r$ die Bedingung $TNS(rT) \subseteq TNS(r^c T')$ für alle $c > E$ erfüllt ist.
   • Kombinatorische Schranken: Die Autoren leiten Schranken basierend auf der Poset-Struktur der Bäume ab. Theorem 3.3 liefert eine Formel für einen Exponenten basän der Anzahl maximaler Elemente in spezifischen Teil-Posets, die aus den Baumstrukturen abgeleitet sind.
   • Plane Bäume: Für plane Bäume (bei denen die Blätter geordnet sind) nutzen die Autoren die Tatsache aus, dass Doad-Mengen Intervallen entsprechen. Sie führen die „Höhe“ und „duale Höhe“ von Knoten ein, um spezifische Schranken für die Einbettung relativ zum Train-Track-Baum ($TT_n$) und zwischen beliebigen planaren Bäumen abzuleiten (Theorem 4.4, Korollar 4.7).

4. Algorithmischer Ansatz:

   • Die Autoren haben einen Algorithmus implementiert, um diese Exponenten für eine kleine Anzahl von Blättern ($n \le 8$) zu berechnen.
   • Sie nutzten das SageMath-Paket BinaryTree, um alle vollen binären Bäume zu generieren.
   • Für größere $n$, wo eine erschöpfende Suche nach Doad-Mengen-Überdeckungen nicht mehr praktikabel ist, formulierten sie ein ganzzahliges Lineares Programm (ILP), um die Anzahl der Doad-Mengen zu minimieren, die zur Abdeckung der Splits des Zielbaums erforderlich sind.

Wesentliche Beiträge und Ergebnisse

• Verallgemeinerung der Hackbusch-Vermutung: Die Arbeit erweitert die Analyse der Einbettung von spezifischen Baumpaaren (hierarchisch vs. Train-Track) auf beliebige binäre Baumpaare.
• Existenz und Definition von Einbettungsexponenten: Die Autoren beweisen die Existenz eines endlichen Einbettungsexponenten für jedes Paar von Bäumen und definieren ihn als Maß für die notwendige Skalierung der Parameter.
• Kombinatorische Schranken:
  • Eine allgemeine obere Schranke von $\lfloor n/2 \rfloor$ wird bereitgestellt (Proposition 3.2).
  • Eine engere Schranke basierend auf der Poset-Struktur der Bäume wird präsentiert (Theorem 3.3).
  • Spezifische Schranken für plane Bäume werden unter Verwendung von Knotenhöhen abgeleitet, wobei der Exponent für einen Baum $T$ im Train-Track-Baum $TT_n$ mit $\max\{\min\{h_\ell, h^*_{\ell+1}\}\}$ zusammenhängt (Korollar 4.5).
• Algorithmische Implementierung: Die Autoren stellen einen Algorithmus und eine ILP-Formulierung zur Berechnung dieser Exponenten bereit. Sie berichten über eine erschöpfende Suche für Bäume mit bis zu $n=8$ Blättern, wobei detaillierte Ergebnisse in einem separaten Datensatz [GM25] gesammelt wurden.
• Nicht-Schärfe der Schranken: Die Arbeit zeigt durch Beispiele (z. B. Abbildung 6), dass die abgeleiteten kombinatorischen Schranken nicht notwendigerweise scharf sind. In einigen Fällen ist der tatsächliche Einbettungsexponent signifikant niedriger als die theoretische obere Schranke, die durch Poset- oder höhenbasierte Formeln gegeben ist.

Bedeutung und Behauptungen
Die Autoren positionieren diese Arbeit als einen „ersten Schritt“ hin zu einem besseren Verständnis von Tensornetzwerk-Einbettungen. Sie behaupten, Folgendes geleistet zu haben:

1. Einen allgemeinen Rahmen für die Einbettungsfrage vorgeschlagen, der auf beliebig geformte binäre Bäume anwendbar ist.
2. Ein neues Maß eingeführt, den Einbettungsexponenten, der die Beziehung zwischen verschiedenen Tensornetzwerkformaten quantifiziert.
3. Sowohl theoretische Schranken (via Poset-Strukturen und ganzzahlige Programmierung) als auch experimentelle Daten für kleines $n$ bereitgestellt.

Die Arbeit schließt bescheiden mit dem Hinweis, dass die Schranken zwar nützlich, aber nicht immer eng sind. Die Autoren identifizieren offene Fragen dazu, ob die oberen Schranken aus Lemma 2.11 immer scharf sind und ob duale Lösungen der linearen Programmierungsrelaxation verwendet werden können, um Tensoren zu konstruieren, die untere Schranken für die Exponenten liefern. Sie legen nahe, dass der Einbettungsexponent ein neues, nicht-symmetrisches Distanzmaß für Bäume darstellt, das einer weiteren Vergleichbarkeit mit existierenden Baummetriken in der Literatur bedarf.