Approximating Tensor Network Contraction with Sketches

This paper introduces the first sketching method capable of approximating arbitrary tensor network contractions, including cyclic ones, and proposes a second method for acyclic networks that achieves polynomial time and space complexity, overcoming the exponential limitations of existing approaches.

The Gist

Imagine you are trying to solve a massive, multi-layered puzzle. In the world of math and computer science, this puzzle is called a Tensor Network Contraction.

To understand what that means, let's use an analogy.

The Puzzle: Connecting the Dots

Imagine you have a bunch of different Lego structures (tensors). Some are single bricks, some are long walls, and some are complex 3D shapes. Your goal is to snap them all together according to a specific set of instructions (contractions) to build one final, giant structure.

• In a simple world: You just snap two bricks together. Easy.
• In the real world: You have thousands of bricks, and they are connected in a web. Some bricks connect to three others, some to five. The instructions might say, "Connect the red side of Brick A to the blue side of Brick B, and the green side of Brick B to the yellow side of Brick C."

If the connections form a simple tree (like a family tree with no loops), you can solve it step-by-step. But if the connections form a cycle (a loop where Brick A connects to B, B to C, and C back to A), the math gets incredibly messy. To get the exact answer, a computer might need to try every single possibility, which takes longer than the age of the universe for big problems.

The Problem: The "Expensive" Exact Answer

For decades, computers could only solve these puzzles efficiently if the connections were a simple tree (no loops). If there was a loop, the computer had to do "exponential" work—meaning if you added just one more connection, the time required didn't just double; it multiplied by a huge number.

Furthermore, previous "shortcut" methods (called Sketching) existed to guess the answer quickly. But they had two big flaws:

1. They couldn't handle loops (cycles) at all.
2. Even for simple trees, the "guessing" got worse and worse exponentially as you added more connections. To keep the guess accurate, you needed a massive amount of memory.

The Solution: The "Magic Sketchbook"

The authors of this paper, Mike Heddes and his team, have invented two new ways to use Sketching. Think of sketching not as drawing a picture, but as taking a "compressed summary" or a "fingerprint" of your data. Instead of carrying the whole heavy Lego castle, you carry a tiny, lightweight sketch that represents it.

They introduced two new tricks:

Trick 1: The "Complement" Sketch (For Loopy Puzzles)

The Problem: Previous sketching methods were like a group of people trying to pass a message around a circle. If the circle was even, the message got canceled out. If it was odd, the message got garbled. This is why they couldn't handle loops.

The Fix: The authors invented a "Complement Count Sketch."
Imagine you have a team of messengers. In the old method, they all shouted the message in the same direction. In the new method, for every connection in a loop, the authors assign one messenger to shout the message normally, and another messenger to shout the exact opposite (the complement).
By using this "opposite" messenger, they can cancel out the noise and get a clear signal, even when the connections form a perfect circle. This is the first time anyone has been able to approximate these loopy puzzles accurately.

Trick 2: The "Recursive" Sketch (For Tree Puzzles)

The Problem: Even for simple tree puzzles, the old shortcuts got clumsy. If you had 10 connections, the error rate exploded. It was like trying to guess the weight of a mountain by weighing a single grain of sand, then a pebble, then a boulder—the errors piled up until the guess was useless.

The Fix: The authors realized that a tree structure is just a series of smaller, nested problems. Instead of taking a giant, clumsy snapshot of the whole thing, they built a recursive sketch.
Imagine you are estimating the size of a forest.

• Old way: You try to count every tree at once.
• New way: You count the trees in a small patch, then use that to estimate the next patch, then the next. You build the estimate from the bottom up, refining the "fingerprint" at every single step.
  This keeps the error low and the memory usage small, no matter how many connections you have.

Why Should You Care?

You might think, "I don't build Lego networks." But these puzzles are everywhere:

1. Databases (The "Join" Problem): When you search a database and ask, "Show me all customers who bought Product A, live in City B, and ordered in 2023," the computer has to "join" these lists. If the lists are huge and the rules are complex (loops), the computer slows down. This new method helps databases guess the size of the result instantly, making your search results appear faster.
2. Quantum Computers: Simulating quantum physics is essentially solving massive tensor networks. This method could help us simulate quantum computers on regular laptops without needing a supercomputer.
3. Social Networks: Counting how many "triangles" of friends exist in a network (A knows B, B knows C, C knows A) is a classic puzzle. This method makes counting these patterns in massive networks (like Facebook or Twitter) much faster.

The Bottom Line

The authors have given us two new tools:

1. A way to solve any tensor network, even the messy, looped ones, that was previously impossible to approximate.
2. A way to solve simple, tree-like networks that is exponentially faster and uses less memory than before.

They turned a problem that required a supercomputer to guess, into a problem a regular laptop can solve in a blink, all by using clever "fingerprinting" tricks to avoid doing the heavy lifting.

Technical Summary

Here is a detailed technical summary of the paper "Approximating Tensor Network Contraction with Sketches" by Heddes et al.

1. Problem Statement

Tensor Network Contraction (TNC) is a fundamental mathematical operation that generalizes dot products and matrix multiplication. It involves contracting a set of tensors based on shared indices (contractions) to produce a result (either a scalar or a lower-order tensor). TNC is central to applications in quantum mechanics, machine learning, database query optimization (join size estimation), and graph theory.

The Challenge:

• Computational Hardness: Exact TNC is NP-hard. The complexity of exact algorithms grows exponentially with the treewidth of the tensor network.
• Limitations of Existing Sketching Methods: While sketching (dimensionality reduction) has been used to approximate TNCs, existing methods (e.g., AMS sketch, Count sketch extensions) suffer from two major flaws:
  1. Cyclic Restriction: They only support acyclic tensor networks. They fail when the network contains cycles.
  2. Exponential Complexity: Even for acyclic networks, the sketch size (and thus time/space complexity) required to maintain a fixed error bound grows exponentially with the number of contractions ($t$). Specifically, the sketch size $m$ scales as $\Omega(3^t / \epsilon^2)$.

2. Methodology

The authors propose two distinct sketching methods to address these limitations, both providing an $(\epsilon, \delta)$-approximate Tensor Network Contraction (ATNC).

Method 1: General TNC Approximation (Supports Cyclic Networks)

This method extends sketching to arbitrary tensor networks, including those with cycles.

• Core Insight: Previous methods relied on circular cross-correlation to combine sketches. In acyclic networks, this naturally results in one conjugated mode per contraction, allowing errors to cancel out. However, in cyclic networks, this pattern breaks, leading to incorrect estimations.
• Innovation: The authors introduce the Complement Count Sketch.
  • A complement count sketch ($C'$) is a circularly reversed version of a standard count sketch ($C$).
  • Crucially, $FC'x = FCx$ (in the Fourier domain), but the spatial arrangement allows explicit control over conjugation.
• Mechanism:
  • For every contraction $(u, v)$, the authors assign an independent count sketch $C_u$ to mode $u$ and its complement $C'_u$ to mode $v$.
  • This ensures that every contraction has exactly one conjugated mode, regardless of whether the network is cyclic or acyclic.
  • The estimation is performed using circular convolution instead of cross-correlation.
• Complexity: The sketch size required is $m = \Omega(3^t / \epsilon^2)$. While this solves the cyclic problem, it retains the exponential dependence on the number of contractions ($t$).

Method 2: Improved Approximation for Acyclic TNCs

This method targets acyclic tensor networks (common in database joins) to eliminate the exponential dependency on the number of contractions.

• Core Insight: An acyclic tensor network can be viewed as a rooted tree. The contraction can be formulated recursively as a sequence of matrix multiplications involving Kronecker products.
• Innovation: The authors utilize Recursive Sketching (based on [AKK+20]) combined with a progressive computation scheme.
  • Instead of sketching the entire tensor product at once (which causes variance to explode), they sketch the Kronecker products recursively from the leaves of the tree up to the root.
  • They decompose the recursive sketch matrix $R = Q \cdot S$ (where $S$ is a Kronecker product of count sketches and $Q$ involves tensor sketches).
• Mechanism:
  • The algorithm traverses the tree from leaves to the root.
  • At each step, it computes a "Sketched Matrix-Vector Product" ($C \cdot \text{mat}(X) \cdot R^T \cdot r$).
  • This transforms the problem from handling high-order tensors into a sequence of manageable matrix-vector operations, keeping the variance low.
• Complexity: The sketch size required is $m = \Omega(t / \epsilon^2)$. This reduces the dependency on the number of contractions from exponential to linear.

3. Key Contributions

1. First Cyclic Approximation: The paper presents the first sketching method capable of approximating cyclic tensor network contractions, overcoming a fundamental limitation of prior work.
2. Polynomial Complexity for Acyclic Networks: For acyclic networks, the authors achieve a sketch size that depends polynomially (linearly) on the number of contractions, rather than exponentially. This is a significant theoretical breakthrough.
3. Complement Count Sketch: The introduction and formalization of the complement count sketch as a tool to manage conjugation in cyclic structures.
4. Unified Framework: The methods are proven to work for both full TNCs (resulting in a scalar) and partial TNCs (resulting in a non-zero order tensor).

4. Results and Complexity Analysis

The authors compare their methods against existing approaches (e.g., [DGGR02], [HNGN24]).

Feature	Existing Methods	Method 1 (General)	Method 2 (Acyclic)
Network Type	Acyclic only	General (Cyclic + Acyclic)	Acyclic only
Sketch Size ($m$)	$\Omega(3^t / \epsilon^2)$	$\Omega(3^t / \epsilon^2)$	$\Omega(t / \epsilon^2)$
Time Complexity	Exponential in $t$	Exponential in $t$	Polynomial in $t$
Space Complexity	Exponential in $t$	Exponential in $t$	Polynomial in $t$

• Notation: $t$ is the number of contractions, $N$ is the total non-zero elements in input tensors, $q$ is the sum of tensor orders, and $m$ is the sketch dimension.
• Theorem 1: Establishes that an $(\epsilon, \delta)$-ATNC can be computed in time $O((pm \log m + qN) \log 1/\delta)$ using $O(mp \log 1/\delta)$ space.
  • For acyclic: $m = \Omega(t/\epsilon^2)$.
  • For general: $m = \Omega(3^t/\epsilon^2)$.

5. Significance and Applications

The proposed methods have broad implications across several domains:

• Database Systems (Join Size Estimation):
  • Estimating the size of multi-join queries is critical for query optimization.
  • Existing estimators fail on cyclic queries (common in real-world schemas) or degrade rapidly as the number of joins increases.
  • This work provides the first accurate estimator for cyclic joins and significantly improves efficiency for acyclic joins with many tables.
• Quantum Mechanics:
  • TNC is used to simulate quantum many-body systems. The ability to approximate cyclic networks (which often represent entangled states in loops) is vital for simulating complex quantum circuits.
• Graph Theory:
  • Problems like counting triangles or $q$-colorings can be reduced to TNC. The new methods allow for faster approximation of these combinatorial problems on large graphs.
• Machine Learning:
  • Efficient contraction of tensor networks is essential for training large models (e.g., Tensor Train decompositions). These methods offer a way to approximate these operations with lower memory footprints.

Conclusion

This paper fundamentally advances the state of the art in tensor network approximation. By introducing the complement count sketch, the authors break the barrier preventing sketching methods from handling cyclic networks. Furthermore, by leveraging recursive sketching on tree-structured networks, they eliminate the prohibitive exponential complexity associated with the number of contractions, making large-scale tensor network approximations feasible for practical applications in databases and physics.