Permutation Search of Tensor Network Structures via Local Sampling

Chao Li, Junhua Zeng, Zerui Tao, Qibin Zhao

Overview

This paper introduces Tensor Network Permutation Search (TN-PS), a novel method to optimize how data dimensions (modes) are mapped to the nodes of a tensor network. By shifting from global genetic algorithms to a theoretically grounded local sampling approach, the authors achieve more compact tensor representations with significantly lower computational costs.

The Problem: Mode-Vertex Mapping

Tensor Networks (TNs) are powerful tools for handling high-dimensional data in fields like deep learning and quantum simulation. However, their efficiency depends heavily on their structure. While previous research has focused extensively on finding the right "ranks" (bond dimensions) or "formats" (the graph shape), this paper tackles a neglected but crucial variable: the mapping between tensor modes and network vertices.

Simply changing which data dimension goes to which node in a Tensor Ring (TR) can lead to a nearly 4x difference in the number of parameters required to achieve the same accuracy.

Figure 1: Impact of mode-vertex mapping on TR-ranks and parameter counts.

The challenge is that for a tensor with $N$ dimensions, there are $N!$ possible permutations. Searching this space exhaustively is impossible for large $N$, and standard global search methods are often computationally prohibitive.

Methodology: TN-Structure Local Sampling (TNLS)

To navigate this massive search space, the authors propose TN-structure Local Sampling (TNLS). This meta-heuristic algorithm treats the discrete, non-differentiable search space as a landscape to be navigated via "steepest descent."

Key components of the approach include:

  • Theoretical Framework: The authors rigorously define the "geometry" of the permutation search space. They establish a semi-metric and a neighborhood based on group theory (specifically, adjacent transpositions in symmetric groups).
  • Local Sampling: Instead of a global search (like a Genetic Algorithm), TNLS samples potential structures from a defined neighborhood around the current best candidate.
  • Annealing Trick: The algorithm uses a shrinkage strategy for the sampling range, ensuring it explores broadly at first and converges to a local optimum over time.
  • Template Preservation: Unlike general structure searches that might destroy the desired format (e.g., turning a Tensor Train into something else), TN-PS preserves the chosen "template" graph.

Key Insights

  • Permutations Matter: The "mode-vertex" mapping provides a significant inductive bias. Finding the right permutation allows the model to capture correlations more efficiently, leading to much smaller ranks.
  • The Search Space is "Collapsed": By imposing a fixed template (like a ring or a path), the search space becomes more constrained and structured compared to general structure search. This "collapsed" geometry makes local sampling highly effective.
Figure 2: Visualization of the "collapsed" search space when imposing a template.
  • Local vs. Global: While Genetic Algorithms (like TNGA) are robust, they are "blind" to the local geometry. TNLS leverages the mathematical neighborhood to find better directions faster.

Evaluation and Results

The authors evaluated their approach across a diverse set of benchmarks, including synthetic data, image completion (USC-SIPI database), image compression (BSD500 dataset), and TGP model compression (UCI and LIBSVM archives).

  • Efficiency: TNLS consistently required significantly fewer model evaluations than the state-of-the-art Genetic Algorithm (TNGA+). For example, in image completion tasks, TNLS achieved similar or better Relative Squared Error (RSE) with roughly 1/3 to 1/4 the number of evaluations.
  • Compactness: The method successfully reduced the parameter count across all benchmarks while maintaining high approximation accuracy.
  • Scalability: While the search space grows factorially with the number of vertices $N$, the authors' theoretical bounds show that the growth is manageable if the graph degrees are small (as is typical in Tensor Train or Tensor Ring formats).

Limitations and Future Work

The success of local sampling assumes the optimization landscape is relatively smooth. If the landscape is extremely "flat" or highly jagged, local methods might perform worse than global ones. Additionally, while TNLS uses fewer total evaluations, each iteration still involves multiple TN approximations, which can be expensive for very high-dimensional tensors.

The authors suggest that a more rigorous analysis of the "smoothness" of the TN-SS/PS landscape remains an open and promising area for future research.

Summary updated

Abstract

Recent works put much effort into <em>tensor network structure search</em> (TN-SS), aiming to select suitable tensor network (TN) structures, involving the TN-ranks, formats, and so on, for the dec...
BibTeX
@inproceedings{li2022permutation,
  author = {Chao Li and Junhua Zeng and Zerui Tao and Qibin Zhao},
  title = {{Permutation Search of Tensor Network Structures via Local Sampling}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=08FglarBVbH},
}
Figure