Arc-Guided Crossover for Tensor Ring Mode Ordering

A tensor ring stores a large multi-way array, such as a video or an image reshaped into many small dimensions, as a closed loop of small three-way "cores." It needs far fewer numbers than the raw array, but only if the array's dimensions ("modes") are placed around the loop in a good order. Put two strongly coupled modes on opposite sides of the ring and every core between them must grow to carry that coupling. The ring is unchanged by rotating or reversing the order (Tensor Ring Decomposition), but it is very sensitive to any other reordering. Choosing the order is therefore a search over $(d-1)!/2$ distinct cycles for an order-$d$ tensor, and each candidate can only be judged by solving a non-convex fitting problem.

We propose a genetic algorithm for this ordering problem with three features. First, it treats rotated and reversed orders as the same individual. Second, it keeps contiguous runs of modes that both parents share. Third, it places crossover cuts where a cheap measurement says the parent's ring is most expensive. That measurement is the numerical rank of the unfolding that separates a contiguous arc of modes from the rest. The idea is to transfer two operator designs: bottleneck-guided cutting from distributed web-service composition (A memetic algorithm with distance-guided crossover), and symmetry-aware alignment from route problems (CSRX). We replace their geographic "distance" with a quantity that actually bounds tensor ring cost.

Core Claim

The quantity to guide recombination is not a pairwise affinity between modes, which would turn ordering into a traveling-salesperson problem. It is the rank of contiguous-arc unfoldings. Here an unfolding is the matrix obtained by grouping one set of modes as rows and the rest as columns. Write a tensor ring with bond sizes $r_0,\dots,r_{d-1}$, where bond $k$ sits between modes at positions $k$ and $k+1$. Let $A$ be the contiguous arc of modes between bonds $k$ and $l$, and let $X_{\langle A\rangle}$ be the unfolding with $A$ as rows. The trace form of the ring gives

$$\operatorname{rank}\big(X_{\langle A\rangle}\big) \le r_k\, r_l .$$

This holds because cutting the loop at the two bonds writes the tensor as a sum of $r_k r_l$ products of an $A$-part and a complement part.

Low-rank arcs are therefore the natural building blocks of a good ordering. A high-rank arc boundary is the analogue of the high-latency link that distance-guided crossover severs. Pairwise mode statistics cannot see arcs whose low rank comes from three-way or higher interactions. That gap is where we expect the method to beat simpler ordering heuristics.

Relation to Prior Work

The closest work is the evolutionary topology search of Li and Sun. It evolves tensor network graphs encoded as flattened adjacency bit strings, using uniform bit swaps and random flips, and fits every candidate with Adam from scratch. Its crossover is exactly the blind cleaver that the building-block literature warns about. Grefenstette showed that blocks spread across distant positions are torn apart by contiguous cuts. Burlacu et al. traced random crossover in symbolic regression and found it yields offspring that are worse than their parents on average. Our search space is narrower (orderings of a ring rather than arbitrary graphs), and our operators carry structural information.

PSTRN runs a multi-objective genetic algorithm over tensor ring ranks with a fixed ordering. It is complementary rather than competing, since we fix the search over ranks to an adaptive inner solver and search over order.

The operators come from two places. The distance-guided GA-I, GA-II and GA-LCS operators of Sadeghiram et al. (memetic DWSC, repair-based multi-objective DWSC) cut at the largest geographic gap and protect the parents' longest common subsequence. On WSC08-1 they improved mean fitness from 0.54 to 0.42. CSRX (Uray et al.) aligns parents under rotation and reversal before crossover. On st70 it reached 4.88% relative error against 21.19% for Best Order Crossover. Tensor rings have exactly the rotation symmetry CSRX exploits, plus reversal, which flips the bond sense but not the parameter count. This is the motivating evidence that symmetry-blind operators waste effort.

The same papers also constrain the design. GA-II tied GA-LCS on WSC08-1, which suggests that strict subsequence protection can cost diversity. For that reason we make protection a tunable quantity and measure its effect rather than assuming it helps.

For the inner fitting step we use TR-ALS with adaptive ranks (Zhao et al.). Where ranks are homogeneous, we warm-start it with BLOSTR (Chen, Chen and Zhang), a finite-step algebraic method for exact tensor ring recovery. In noisy settings, ALS started from BLOSTR converged reliably within about 10 iterations. BLOSTR assumes a correct, uniform-rank structure. The outer search supplies the ordering that this assumption silently requires.

Research Program

The individual is a cyclic order of $d$ modes, stored in a canonical form under the $2d$ rotations and reflections. Crossover proceeds in three steps.

  1. The second parent is rotated or reflected to maximize the number of contiguous arcs it shares with the first parent. For $d\le 20$ this is a cheap $O(d^2)$ scan.
  2. Shared arcs are marked as protected, with probability $p$, which is the knob that trades protection against diversity.
  3. Each unprotected bond of the first parent is scored by the estimated numerical rank of the arc unfoldings that bond closes. The cut goes at the highest-scoring bond, or at the two highest in a GA-II-style variant. The missing segment is then filled in the second parent's relative order.

Arc ranks are estimated with a randomized range finder on sampled fibers, at a tolerance tied to the target reconstruction error. Results are cached by arc identity. There are only $d(d-1)$ arcs, so after a few generations the cache answers almost every query.

A distance-guided local search, analogous to the memetic service-insertion step, moves a single mode out of the worst arc into the position that minimizes the product bound. Fitness is the parameter count of an adaptive-rank TR-ALS fit that reaches the target relative error. Every method we compare is charged for its fitting calls.

We will also study the protection–diversity trade-off identified in the file's Gap 4. We will sweep $p$ and record population entropy over arcs, aiming to locate when protection starts trapping the search in a poor ordering.

Baselines

The naive reference point is the natural order of the data with adaptive-rank TR-ALS, together with best-of-$N$ random cyclic orders under the same budget of fitting calls. On KTH, Zhao et al. report that TR needs an average rank of about 34, against about 78 for TT, at relative error 0.2. We will reproduce that point first, so that every gain is measured against a verified starting configuration.

The strongest existing search method is the GA of Li and Sun. We restrict it to ring topologies by searching over orderings, and also run it unrestricted as a reference. It gets the same inner solver, population size, and number of fitting calls, with its crossover and mutation rates tuned on a held-out tensor using the same tuning budget as ours. No reported numeric log-compression result for this method was found on Lacuna; the paper states only that its topologies beat TT-SVD and TR-SVD on LIVE and Lena. We therefore rerun it rather than quote it.

We also include a GA using Best Order Crossover and a CSRX-only GA (symmetry alignment, random cut, no protection). The CSRX-only GA isolates how much of any gain comes from alignment alone.

The key ablations remove one ingredient at a time:

  • the arc-rank cut, replaced by a random cut;
  • the arc score, replaced by a pairwise score;
  • protection, by setting $p=0$;
  • symmetry alignment.

Beating the strongest baseline means two things, judged over 30 seeds with Wilcoxon signed-rank tests at 0.05, matching the protocol of the DWSC papers. Either we reach the same parameter count at the target error with significantly fewer fitting calls, or we reach a significantly lower parameter count at an equal call budget.

Why not just…?

Why not just compute pairwise mode affinities and solve a traveling-salesperson problem for the ring order? This is the most serious threat. If coupling between modes were pairwise, a good tour solver on a mode-affinity matrix would match any genetic algorithm at a fraction of the cost. We run this baseline, with a 2-opt-refined tour on pairwise unfolding ranks, under the same fitting budget. On real images and video it may well tie us, and we will report it if it does. The decisive test is a synthetic family where the planted ring has low arc ranks generated by three-way interactions, with near-uniform pairwise statistics. If arc guidance does not beat the tour solver there, the central claim is false.

Why not just run simulated annealing or random restarts over orderings with the same arc-rank proxy? If the proxy alone does the work, crossover adds nothing. We give annealing the identical cached arc-rank oracle and the same fitting budget. The ablation in which our operator uses a random cut with protection still on separates the value of recombination from the value of the proxy. The clustering results from HG-means (ARI 0.99 against 0.65 for repeated K-means on 500-dimensional mixtures) suggest that structured recombination beats restarts on rugged landscapes. That is a different problem, so we treat it as motivation, not proof.

Why not just search graph topologies with the existing blind-crossover GA, which explores a larger space? A larger space can contain better solutions, but blind crossover spends most of its fitting calls on offspring that are worse than their parents. We measure this directly, following Burlacu et al. We trace the average offspring-minus-parent fitness change for each operator, and report best-so-far fitness against the number of fitting calls.

Proposed Experiments

We will use three groups of benchmarks.

  • Synthetic tensor rings. We plant orderings at $d=8$ to $16$, in the setting of the BLOSTR experiments, where noiseless recovery reaches relative error $10^{-12}$ to $10^{-14}$. This includes the pairwise-uninformative family described above. Here success is measured as the rate of exactly recovering the planted cycle up to rotation and reflection, with error near machine precision.
  • Real data. KTH video and COIL-100, both used by Zhao et al., and LIVE and Lena images reshaped into order-8 and order-9 tensors as in Li and Sun. Here we measure parameter count at relative errors of 0.1 and 0.2.
  • Downstream check on COIL-100. Classification accuracy from the learned cores, where TR is reported at 99.14%. This confirms that ordering gains in compression do not cost features.

On all benchmarks we report fitting calls and wall-clock time to target. We also report the protection sweep over $p$ against final parameter count and arc entropy.

Two outcomes would settle the question. The method should beat the pairwise tour solver on the higher-order synthetic family. It should also beat the restricted Li–Sun GA in fitting calls to target on KTH and LIVE. If only the first holds, the contribution is a diagnostic for when ordering is genuinely a higher-order problem rather than a better general-purpose search.