Abstract
Recent research in tensor network structure search (TN-SS) has focused on optimizing tensor network (TN) formats and ranks for decomposition and learning tasks. This paper addresses a critical but often overlooked component of TN-SS: the TN permutation search (TN-PS). TN-PS involves finding the optimal mapping from tensor modes onto TN vertices to achieve the most compact representation. We provide a theoretical investigation into the counting and metric properties of the TN-PS search space and propose Tensor Network Local Sampling (TNLS), a meta-heuristic algorithm that navigates this space through local neighborhood sampling. Our numerical results demonstrate that TNLS significantly reduces model size across various benchmarks while requiring substantially less computational effort than previous state-of-the-art evolutionary methods.
Introduction
Tensor Networks (TNs) are indispensable tools for representing high-dimensional data in quantum physics, signal processing, and machine learning. However, the efficiency of a TN is highly sensitive to its structure, which includes the graph topology (format), the bond dimensions (ranks), and the mapping of data dimensions to nodes (permutation).
While optimizing ranks and formats is common, the mode-vertex mapping—the permutation—presents a combinatorial challenge. For a tensor of order $N$, there are $N!$ possible mappings. A poor permutation can lead to unnecessarily large ranks and high computational costs, yet the factorial growth of the search space makes exhaustive search impossible. Previous attempts using global search methods, such as genetic algorithms, often struggle with the sheer scale of the search space and high computational overhead.
Theoretical Framework: The Geometry of Permutations
To move beyond inefficient global searches, this work establishes a theoretical foundation for the "geometry" of the permutation search space. By utilizing the word metric of symmetric groups, we define a structured neighborhood around any given tensor configuration.
This framework allows us to treat the discrete search for permutations as a navigation problem through a structured landscape. By defining a semi-metric, we can quantify the distance between different permutations, enabling the transition from blind global searching to informed local optimization.
The TNLS Algorithm
We propose the Tensor Network Local Sampling (TNLS) algorithm, which leverages the theoretical neighborhood structure to find optimal TN configurations iteratively. The algorithm follows three core phases:
- Local Sampling: Instead of searching the entire $N!$ space, TNLS samples candidates from a defined neighborhood around the current best structure. It adjusts TN-ranks using a truncated Gaussian distribution and modifies permutations by performing random swaps of vertices, guided by the neighborhood theory.
- Annealing Strategy: To ensure both exploration and convergence, the algorithm employs an annealing schedule. The "neighborhood radius" (the extent of the tweaks) shrinks over time, allowing the search to settle into a high-quality local optimum.
- Evaluation and Update: The algorithm evaluates these local candidates and moves the center of the search to the best-performing structure, effectively performing a "steepest-descent" in the space of TN structures.
Experimental Results
TNLS was evaluated against synthetic benchmarks and real-world applications, including image completion and model compression.
Efficiency and Compactness
In synthetic benchmarks for Tensor Ring (TR) and Tensor Train (TT) formats, TNLS achieved parameter efficiency equal to or better than the previous state-of-the-art (TNGA+). Crucially, it reached these results using 2x to 5x fewer model evaluations, representing a significant reduction in computational cost.
Real-World Applications
- Image Completion: On the USC-SIPI database, TNLS consistently identified structures that achieved lower reconstruction errors with fewer parameters compared to standard mapping techniques.
- Model Compression: The algorithm was used to compress Tensorial Gaussian Processes (TGP). On the CCPP (Power Plant) dataset, TNLS reduced the parameter count from 2.64k to 2.24k without sacrificing mean square error, demonstrating its utility in streamlining machine learning models.
Discussion and Insights
The success of TNLS suggests that the "loss landscape" of TN permutations is relatively smooth, allowing local sampling to find efficient paths to optimality. By fixing a "template" (such as a ring or tree) and searching for the best permutation, TNLS imposes a helpful inductive bias that collapses the search space into a manageable size.
While TNLS is significantly faster than genetic algorithms, it remains more demanding than simple greedy heuristics. Future work will explore the simultaneous optimization of the template graph and the permutation, as well as further theoretical analysis of the landscape smoothness to provide more rigorous convergence guarantees.
Summary updated