Graph-Constrained Structure Search for Tensor Network Representation
Year: 2021

Abstract:
Recent works paid effort on the structure search issue for tensor network (TN) 1 representation, of which the aim is to select the optimal network for TN contraction 2 to fit a tensor. In practice, however, it is more inclined to solve its sub-problem: 3 searching TN structures from candidates with a similar topology like a cycle or lat4 tice. We name this problem the graph-constrained structure search, and it remains 5 open to this date. In this work, we conduct a thorough investigation of this issue 6 from both the theoretical and practical aspects. Theoretically, we prove that the 7 TN structures are generally irregular under graph constraints yet can be universally 8 embedded into a low-dimensional regular discrete space. Guided by the theoretical 9 results, we propose a simple algorithm, which can encode the graph-constrained 10 TN structures into fixed-length strings for practical purposes by a “random-key” 11 trick, and empirical results demonstrate the effectiveness and efficiency of the 12 proposed coding method on extensive benchmark TN representation tasks. 13

Recent works paid effort on the structure search issue for tensor network (TN)1 representation, of which the aim is to select the optimal network for TN contraction2 to fit a tensor. In practice, however, it is more inclined to solve its sub-problem:3 searching TN structures from candidates with a similar topology like a cycle or lat-4 tice. We name this problem the graph-constrained structure search, and it remains5 open to this date. In this work, we conduct a thorough investigation of this issue6 from both the theoretical and practical aspects. Theoretically, we prove that the7 TN structures are generally irregular under graph constraints yet can be universally8 embedded into a low-dimensional regular discrete space. Guided by the theoretical9 results, we propose a simple algorithm, which can encode the graph-constrained10 TN structures into fixed-length strings for practical purposes by a “random-key”11 trick, and empirical results demonstrate the effectiveness and efficiency of the12 proposed coding method on extensive benchmark TN representation tasks.13
1 Introduction14
Tensor networks (TNs) are recognized as a popular framework for solving extremely15 high-dimensional problems arising in domains such as quantum simulation, machine16 learning and signal processing. In general, TNs are used to represent the high-17 dimensional states/models/data by a network of low-dimensional tensors (a.k.a., cores),18 such that the requirement on computation and storage would be significantly reduced.19
structure search for TN representation.32
The state of affairs raises important unresolved questions. Is the afore-33 mentioned task really easier than the general structure search? What34 are the properties of TN structures under graph constraints, and how to35 effectively solve the problem in practice?36
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.
In this work, we shed light on these questions through a theoretical and empirical investigation of the37 graph-constrained TN structures.38
We first prove the graph constraint makes TN structures being irregular. In particular, both the39 addition and random perturbation is not closed on the candidate set. This result helps to explain40 why the conventional search algorithms on grids give no guarantee of feasibility of the solutions.41 Furthermore, on the scale of the search problem, we prove the symmetry of the graph-constraint plays42 a role to determine the cardinality of TN structures, yet there exists a universal cardinality bound43 across a varies of practical TNs, such as tensor train (TT) [30], tensor ring (TR) and PEPS [38]. The44 result reveals the possibility to construct a regular discrete space, from which we can represent those45 irregular TN structures by elements in a compact manner.46
Guided by the theoretical results, this work also sheds light on a practical solution for the graph-47 constrained structure search issue. We propose a novel coding method to encode TN structures into48 fix-length strings by a “random-key” trick, a random mapping from TN structure space to coding49 space. The regularity of the coding space allows to apply the population-based algorithms equipped50 with the proposed coding method to tackling the search issue for TN representation effectively. We51 conduct extensive experimentation on a variety of benchmarks. The results show that the proposed52 method often obtain better TN structures than many existing rank-selection and structure search53 algorithms.54
2 Preliminaries and problem setup55
In this section, we present the basic concepts on tensor network (TN), and give a formal definition of56 the graph-constrained structure search for TN representation.57
2.1 Tensor network (TN) and structure search for tensor network representation (TNR)58
An order-N tensor is a multi-dimensional array of real numbers represented by Xi1,i2,...,iN ∈59 RI1×I2×···×IN , where im, m ∈ [N ] is defined as the index regarding the mth mode of X 1 and [N ]60 denotes a set of integers from 1 to N . Tensor contraction [10], a binary operation on tensors, is61 defined as a multiplication of two tensors under their same indices. For instance, given two order-262 tensors Ai,j ∈ RI×J , Bj,k ∈ RJ×K , the tensor contraction of A and B under the index j returns63 Ci,k = Ai,jBj,k ∈ RI×K , which is equivalent to the matrix multiplication.64 A tensor network (TN) is roughly defined as a collection of tensors (a.k.a., cores), which are65 tensor-contracted under some, or all, of their indices according to a specific pattern [29]. Recent66 works [25, 42] show that the “patterns” of TNs can be precisely described by edge-weighted simple67 graphs. TN structures thus can be formulated by adjacency matrices of graphs. Formally, we define68 the TN with a general “pattern” as follows.69
Definition 1 (Tensor network.) Let AR = { A ∈ (ZR+1)N×N |A(i, i) = 0, ∀i ∈ [N ], andA = A> } ,70
an order-N tensor network (TN) of the size I1 × I2 × · · · × IN under a structure A ∈ AR defines a71 mapping :72 X = TN(V;A) ∈ RI1×I2×···×IN , (1) where V = {Vi, i ∈ [N ]} represents a collection of cores in which the size of Vi, i ∈ [N ] equals73 the multiplication of Ii and all non-zero entries of A(i, :), and TN( · ;A) denotes a series of tensor74 contractions of V under the indices [25] described by A.75
We observe that Definition. 1 models a rich family of TNs with the ranks upper-bounded by R (due76 to ZR+1), including TT, TR, PEPS and etc., but also note that the TNs that contain internal cores are77 not included in this form.78
Tensor network representation (TNR) of a tensor X is defined as finding a specific core-set V such79 that Eq. (1) holds. The structure search for TNR is thus to find the optimal matrix A ∈ AR, such that80 X can be represented by V that satisfies Eq. (1). In particular, the search problem can be solved by81
min A∈AR
φX (A), s.t.X = TN(V;A) for someV, (2)
1The indices would be omitted for brevity if there is no confusion.
where φX : AR → R denotes a measure of the TN structures like compression ratio. Note that82 similar frameworks were also introduced in works [17, 21], where the entries of A corresponds to83 the TN-ranks formulated as a vector in those works. Lemma 5 in Sec. 3 will show the matrix form of84 A would provide additional structural information to analyse the property of TN structures.85
2.2 Graph-constrained structure search for TNR86
The graph-constrained structure search issue is also modeled as (2) yet constraining the feasible space87 AR into a graph-induced subset, in which the TN structures have similar topological forms. To build88 the connection to graphs, we first show the existence of a bijective mapping from AR to a graph89 space.90
Lemma 2 There is a bijective mapping Ψ : AR → GR, where GR denotes a set containing all91 possible vertex-labeled, simple yet weighted graphs (G, fR) = (V,E, fR) with N vertices and a92 edge-weighting function fR : e ∈ E → [R], and we name the unweighted part G the topology of TN93 a TN structure.94
The claim is naturally true by the relation between graphs and the adjacency matrices. The bijection95 in Lemma 2 implies that for each A ∈ AR we can always find a unique (G, fR) corresponding to96 it. Table 1 in the supplementary material illustrates the correspondence between graphs and the97 well-known TNs. We next construct graph-constrained TN structures by the isomorphism of a graph98 G0 = (V,E0) and the mapping Ψ given in Lemma 2. A formal definition is given as follow.99
Definition 3 (Graph-constrained TN structures.) Given a vertex-labeled simple graph G0 =100 (V,E0) and the mapping Ψ in Lemma 2, the TN structures under G0 are defined as101
HG0,R = {H ∈ AR|GH ∼= G0 where (GH , fR,H) = Ψ(H)} , (3)
where ∼= denotes the graph isomorphism.102
As given in Definition 3, HG0,R is a subset of AR and its elements own the topologies being103 isomorphic to G0. For instance, suppose G0 to be a cycle graph of 4 vertices, i.e., C4, then HC4,R104 contains all TR structures of order-4 with the ranks upper-bounded by R as Figure 1. It is thus105 expected to solve the mentioned optimal matching problem by searching structures on HG0,R. Not106 only that, but also note HG0,R equals AR if G0 is a completion graph, i.e., KN . Next, we define the107 problem of graph-constrained structure search for TNR by HG0,R.108
Definition 4 (Graph-constrained structure search for TNR.) Given a graph G0 and the corre-109 sponding HG0,R obtained as Definition 3, the graph-constrained structure search for TNR is to solve110 the following problem:111
min H∈HG0,R
φX (H), s.t.X = TN(V;H) for someV. (4)
It is shown from Definition 4 that the set HG0,R restricts the optimization process only searching on112 the TN structures, which has the same topology G0 up to permutations of the vertices [5]. Moreover,113 although (4) owns a similar form to its unconstrained counterpart (2), it will be proved in the next114 section that the existing algorithms on (2) may be not available on the graph-constrained search issue.115
Remark. Note that Definition 1 allows the entries of A to equal 1, which implies the rank-one116 contraction between cores. According to the fact given in [25, 42] that the weight-one edges can117 be removed from TNs, we thus know that the solution of (4) would have a subgraph of G0 as its118 “true” topology. Therefore, solving (4) has the capability of achieving not only isomorphic but also119 subgraphs of G0.120
3 Algebraic properties of graph-constrained TN structures121
In this section, we focus on the properties of HG0,R, the set containing all TN structures constrained122 under a graph G0. From an algebraic perspective, we first show HG0,R is irregular under most of123 graph constraints by proving that the set is not closed under addition and random perturbation. After124 that, we analyse the cardinality of HG0,R, which reflects the scale of the search problem. We derive125
the precise cardinality of HG0,R across many well-known TNs, and prove a universal cardinality126 bound of HG0,R under all connected low-degree graphs.127 To understand the property of HG0,R, we first prove all its elements own a factorization of the128 multiplication of a rank-induced matrix and a permutation matrix.129
Lemma 5 (Factorization of HG0,R.) Given a vertex-labeled simple graph G0 = (V,E0), for any130 H ∈ HG0,R, there exists a permutation matrix P of the size |V | × |V | and a bijective linear mapping131 ΩG0 : (ZR+1) |E0| → (ZR+1)|V |×|V | such that H can be factorized as132
H = PΩG0(r)P >, (5)
where | · | denotes the cardinality and r ∈ (ZR+1)|E0| denotes the rank vector of dimension |E0|.133
Intuitively, Lemma 5 implies that the rank-induced matrix ΩG0(r) forms a linear sub-space of134 dimension |E0|, then HG0,R takes all “flips and rotations” of the subspace into account due to the135 permutation matrix P. A visual illustration of HG0,R is shown on the most left of Figure 2. We can136 see that HG0,R has an “irregular shape” visually, and this property is formally proved as follows.137
Proposition 6 (Irregularity of HG0,R.) Assuming R ≥ 2, the following two claims are held.138
1. Addition (modulo R+ 1) is not closed on HG0,R if G0 = (V,E0) or its complement is not139 complete;140
2. With a relatively sparse graph G0, the Bernoulli-distributed perturbation on HG0,R is not141 closed with a probability approximately being larger than (1− 1/R)|E0|.142
The proof is given as supplementary material. Proposition 6 effectively say that the operations used143 in common search algorithms, such as the recombination and mutation in genetic algorithms (GAs)144 or progressive search in greedy methods, cannot guarantee the outputs being contained by HG0,R,145 leading to the invalidation of those algorithms on this issue.146
Next, we jump to the cardinality of HG0,R, which reflects how many candidates we have under a147 graph constraint. From a information-theoretic perspective, the cardinality is proportional to the least148 required code length on TN structures in general. A smaller cardinality generally implies a easier149 search process especially for the population-based algorithms. Below, we first prove the cardinality150 of HG0,R under a general graph constraint.151
Lemma 7 (Cardinality of HG0,R.) Given a vertex-labelled simple graph G0 = (V,E0), we have152
log(|HG0,R|) = |E0| log(R) + log(|V |!)− log(|Aut(G0)|), (6)
where log( · ) denotes the natural logarithm and Aut(G0) denotes the graph automorphisms of G0.153
As shown on the right of Eq. (6), the first two terms correspond to the TN-ranks and permutations as154 Lemma 5, respectively, while the third term log(|Aut(G0)|) reflects the symmetry of G0. it implies155 the cardinality of HG0,R would be small if G0 owns strong symmetry. From the TN perspective, it156 means the TNs with symmetric topologies like TR and the complete TN (CTN) [48] are expected to157 own a smaller size of HG0,R. For those well-known TNs, we show their corresponding cardinality of158 HG0,R as follow.159
Proposition 8 Assume order-N TN models, of which the ranks are upper-bounded by R, then we160 have161
1. TT [30]: log(|HPN ,R|) = (N − 1) log(R) + log(N !)− log(2)162 2. TR [47]: log(|HCN ,R|) = N log(R) + log ((N − 1)!)− log(2)163 3. CTN [48]: log(|HKN ,R|) = (N2 −N) log(R)/2164 4. T-tree [42]: (N − 1) log(R) + log(N) ≤ log(|HTN ,R|) ≤ log(|HPN ,R|)165 5. PEPS [38] : log(|HLm,n |) ≤ (2mn−m− n) log(R) + log((mn)!)− log(4)166 6. Tucker2 [36]: log(|HK1,N |) = N log(R)167
2Note that the Tucker model is not strictly contained by Definition. 1.
In Proposition 8, the inequalities for the T-tree models is due to the variety of the tree structures, and168 in PEPS the equality is held if m and n are relatively prime. We observe from Proposition 8 that169 TR would have a smaller HG0,R than TT in the case of large N . It is intuitively true since the TR170 structure is more symmetric than the one of TT. However, we also observe that, except CTN and the171 Tucker model, there always exists a factorial of N in the equations for the rest of TNs. It implies that172 the cardinality of HG0,R for those TNs is not significantly different from each other. Below, we prove173 the fact is true for all TNs, of which the corresponding G0 is connected and low-degree.174
Proposition 9 (A universal cardinality bound on HG0,R.) Assume G0 = (V,E0) is connected175 graph and its maximum degree ∆G0 is a constant that is far less than |V |, then we have176
log(|HG0,R|) ≥ O (|V | log(R) + |V | log(|V |)) , (7)
where O( · ) denotes the big-O notation.177
The result is proved by bounding the both |E0| and |Aut(G0)| in Lemma 5 by the maximum degree178 ∆G0 using the Handshaking lemma known in graph theory and Theorem 2 given in [22], respectively.179 In addition, we also use the Stirling’s approximation [32] to obtain a tight bound for the logarithm of180 factorials to further simplify the expression.181
The assumption of a small ∆G0 is reasonable since in the practical TNs the cores are expected to be182 low-order (see Table 1 given in the supplementary material for instance). Proposition 9 means that183 there is a G0-independent bound on the cardinality of HG0,R for all connected and low-degree graphs,184 and we can see the bound is relatively tight by intuitively comparing the results with Proposition 8.185
As shown in (7), the first term |V | log(R) corresponds to the number of all possible ranks bounded by186 R, and the second term |V | log(|V |) has the same scale to log(|V |!) for the Stirling’s approximation.187 It implies that, in the case of connected and low-degree G0, the cardinality of HG0,R is close to the188 combination of all possible ΩG0(r) and P in Lemma 5. In other words, the factorization given in189 Lemma 5 is nearly unique on HG0,R. From a pragmatic perspective, the result say that we can solve190 the constrained structure search issue from the factorization space as a alternative. More importantly,191 such the factorization space is independent to topology, because G0 only determine the mapping ΩG0 ,192 which is bijective, linear and fixed beforehand. The result guides us to find the practical solution on193 the graph-constrained structure search issue from the factorization space.194
4 Encoding graph-constrained TN structures via a random-key trick195
Inspired by the theoretical results, we introduce a practical coding method to embed the irregular TN196 structures into a regular discrete space, in which the population-based metaheuristics like GAs can be197 directly used for structure search. Last, experiments on a variety of benchmarks are implemented to198 demonstrate the effectiveness of the method.199
4.1 Method200
Figure. 2 depicts the coding process. We encode the elements of HG0,R from two ingredients: the201 rank-induced matrix ΩG0(r) and the permutation P as Lemma 5. For the former, since the mapping202 ΩG0 is bijective and linear, the rank vector r of dimension |E0| is directly used as the code for this203 ingredient.204
For the latter, we randomly embed P into the space [0, 1]|V |, a set of decimal number vectors, by205 a random-key trick [4], which is popularly used to solve the optimal sequencing tasks. For the206 details, the random-key representation encode a permutation with a vector of random numbers207 from [0, 1], and the order of these random numbers reflects the permutation. For instance, the code208 (0.46, 0.91, 0.33) would represent the permutation 2 → 3 → 1, by which we naturally have its209 matrix form P. Finally,the encoded strings are simply the concatenation of the two ingredients.210
One advantage of the random-key trick is robustness to the structure of HG0,R. Regardless of the211 irregularity of HG0,R, we always have the regular key space [0, 1]|V |, on which the operations such212 as addition and perturbation are always available. It implies that the proposed coding method is213 G0-independent, and many population-based metheuristics such as the one in [25] can be directly214 applied to graph-constrained structure search (see the numerical results given below.) .215
The proposed method gives more compact codes than the work in [25]. In the graph-constraint216 scenario, directly encoding the entries of the adjacency matrix as [25] cannot consider the “low-217 dimensional enssence” of HG0,R due to the irregularity. However, by the proposed method, the218 code length is shorted as O(|V |) compared to O(|V |2) in [25]. A shorter code length implies faster219 convergence and lower computational requirement for the population-based methods in general. For220 the proposed method, we also prove the coding efficiency given in the supplementary material, which221 reflects the gap of the code length from the Shannon entropy on HG0,R.222
4.2 Numerical results223
In this section, we evaluate the practical effectiveness and efficiency of the proposed coding method224 on various benchmark tasks for tensor network representation (TNR).225
4.2.1 Searching the optimal TN structures on synthetic data in TR format and beyond.226
In this experiment, we examine whether using the proposed coding method can learn sufficiently227 good low-dimensional representation on synthetic tensors in TR (including TT) format.228
Data generation. We generate batches of tensors with randomly selecting TR structures. Specifically,229 we first let the dimension of each tensor mode equal 3. Then, we randomly generate the TR-ranks230 at discrete uniform distribution on {1, 2, 3, 4} and the cores at Gaussian distribution N(0, 1), and231 randomly permute the tensor modes after contracting the cores.232
Experiment setup. The proposed coding method are directly applied to the genetic algorithm (GA)233 in [25] by replacing its chromosome design aspect, where we let G0 be a cycle graph and the rank234 bound R be equal to 7. Details of hyper-parameters on the GA are introduced in the supplementary235 material. For comparison, we also implement various types of TR decomposition methods with236 adaptive rank selection, which include the singular value decomposition (SVD) based method TR-237 SVD [47], least-squares-based method TR-ALSAR [47], Bayesian model Bayes-TR [35], and two238 general heuristics TR-LM [28] (exhaustive search) and TNGA [25] (population-based).239
The experimental results are reported in Table 1, where the tensor order covers {4, 6, 8} and the 5240 generated tensors for each order are denoted as Trial A∼E. For performance evaluation, we use the241 Eff. index [25], the ratio of number of parameters between the learned structures and the ground-truth242 TRs, to illustrate the model efficiency. We also illustrate the relative square error (RSE) and the243 generation (Gen.) of the optimal individuals in TNGA and ours in the table.244
Results. As shown in Table 1, only our method can always achieve the same or lower-dimensional245 representation than the ground-truth. We observe that most of the TR decomposition methods fail246 dealing with the permutation on tensor-modes, and such the fact would limit the application of247 the TR methods in the practical use on high-order problems. We also observe the performance of248
TNGA appears dramatically deterioration when increasing the tensor order. As analyzed at the end of249 Section 4.1, TNGA suffers from the dimension explosion of the search space. In this case, TNGA250 has to search the solution from about 4.6× 1023 candidates, which is almost 8.0× 1016 larger than251 the one of ours.252
TN structure search not limit to TR. The proposed coding method is also useful for many well-253 known TNs in machine learning and physic not limit to TR. Under a similar setup for TR, we apply254 the proposed method to the TNs including T-tree (order-7) [42], PEPS (order-6) [38], hieratical255 Tucker (H-Tucker, order-6) [16] and multi-scale entanglement renormalization ansatz (MERA,256
order-8) [11, 33]. Details of the data generation phase are given in the supplementary material.257 Table 2 illustrates the Eff., RSE and Gen. values by our method, where the rows of “ranks” mean258 we only learn the optimal TN-ranks while the rows of “ranks+matching” mean both the ranks and259 permutation are learned by our method. As shown in Table 2, our method achieves the TN structures260 as good as or even better than the ground-truth for various TNs. In addition, we also observe that a261 correct permutation on modes would significantly improve the representational power of TNs.262
4.2.2 Benchmarks on real-world data263
We consider three benchmark TNR problem on real-world data, where two of them is to represent264 the data and the other one is to represent learning models. Details of the experiment setup and more265 results are given in the supplementary material.266
1. Image compression. We use GA equipped with the proposed coding method (in TR format)267 to compress 14 natural images randomly chosen from BSD500 [1], where images are268 grayscaled, resized by 256 × 256, and tensorized into order-8 tensors by two different269 tensorization: a “Python-like” reshaping operation denoted by “Trivial” and visual data270 tensorization (VDT) [6, 24, 45], a image-resolution-based tensorization method. As the271 result, we show the compression ratio (CR, in log form) and RSE (in round brackets) by the272 methods TR-SVD, TR-LM and ours in Table 3, and visualize the summary statistics of the273 learned permutation by our method in Figure 3.274
2. Image completion. The same method is also implemented on image completion, a task275 to predict missing pixels from the observation. In the experiment, 8 images from USC-276 SIPI [40] are chosen and tensorized by VDT of order-9. After that, the entries are randomly277 removed at uniform distribution under the missing rate {50%, 70%, 90%}, respectively. We278 show the average of RSE of predicting the missing values in Table 4 compared with the279 TT/TR completion methods TT-SGD [45], TRLRF [44], TRALS [39].280
3. Reparameterization of tensorial Gaussian process (GP). TNR is applied to parameteriz-281 ing the variational mean of GPs. In the experiment, we reparameterize the TT variational282 mean given in [20] by our method to search better structures. In a regression task on283 datasets CCPP [37], MG [14] and Protein [12], we have the TT variational mean of the284 order-{4, 6, 9}, respectively. In the result, we evaluate the performance by the number of285 parameters and mean square error (MSE, in the round brackets) shown in Table 5.286
288
VDT is verified as a more effective way for tensorization. The results in Table 3 show that,289 our method owns higher compression ratio under close RSE compared to other methods. More290 importantly, the results show a significant difference when learning structures from two tensorization.291 Figure 3 illustrates the statistics on the similarity between the original permutation and the learned292 ones by our method. We observe from Figure 3(a) that in VDT the learned permutation is significantly293 closer to the original one than that in the “Trivial”. Additionally, Figure 3(b) shows the cumulative294 distribution function (CDF), where we can see that, in VDT the probability is larger than 0.8 for295
the similarity being smaller than or equal to 2 . It implies that with a large probability the learned296 structures in VDT own at most a pair of permutation difference compared to the original one. On the297 contrary, for “Trivial” the probability is almost zero in the same interval. Hence, it is verified from298 the empirical results by our method that VDT is more effective way for image tensorization than the299 trivially reshaping operations.300
Exploring TN structures obtains lower-dimensional representation from incomplete data. As301 shown in Table 4, our method achieve a comparable performance on the image completion task.302 Especially when the missing ratio is high, our method is forced to explore better TN structures not303 limit to the ranks, such that the lower-dimensional representation would be applied and results in304 more accurate prediction. Similar claims were also discussed in recent works [7, 17].305
Tensor-reparameterization: a potential way to compress learning models. TNs are known as306 an efficient framework to compress learnables variables by low-dimensional cores. In the experi-307 ment, we illustrate from a “proof-of-concept” level that the model would be further compressed by308 re-parameterizing the learned TN in model. As shown in Table 5, we always use fewer parameters309 than its “teacher” model TTGP [20] to achieve the same MSE on the three datasets. It implies that310 our method give more efficient TNR by search better structures. Unlike training the model with311 simultaneously searching TN structures, we empirically find that searching better structures from the312 well-trained model in TN format would achieve better compression ratio. We intuitively conjecture313 that, by structure search, it is likely to obtain more efficient representation for a tensor, which has314 been in low-rank TN format. In the training phase, on the other hand, the models are not significantly315 low-rank in general. Therefore, the tensor reparameterization often gives better performance in316 practice. A rigorous analysis on this issue is still an open problem.317
5 Discussion318
Our experiments show good TN structures including ranks and permutations can be effectively learned319 in practice by the proposed coding method under extensive family of graph constraints, and our320 theoretical results show the the superior performance is thanks to the low-dimensional essence hidden321 behind the irregularity of the graph-constrained TN structures. More surprisingly, Proposition 9322 shows that such the low-dimensional essence of TN structures is ubiquitous for most of practical323 TNs. As a consequence, we expect this work can promote the understanding on the structure search324 issue on tensor networks from both the theoretical and practical aspects, and the empirical claims in325 experiments are also expected to inspire more potential applications of TNs in machine learning.326
Limitation. Theoretically, we only study the TNs, which do not contain the internal cores. Some327 well-known models like (H-)Tucker and MERA are not contained in the theory, although the proposed328 coding method works well for those models in experiments. Empirically, the proposed coding method329 is more suitable for the population-based methods like GAs, which are still computationally expensive330 compared to other heuristics. Also, the experiments on real-world benchmarks are only illustrative331 and proof-of-concept. More numerical results are necessary if stronger statements such as the332 performance improvement are expected.333
6 Related works334
Learning the optimal TN structures is a generalization of the rank selection issue for TN models [8, 9,335 18, 26–28, 34, 43, 46, 47], and it is known as a tough task especially for the models that contain cycles336 in the topology [3, 23, 42]. More recently, there are several studies on learning TN structures [17, 19,337 21, 25] in a more general form. Another line of works that are close to ours are studies focusing on338 the partition issue for H-Tucker decomposition [2, 13, 15], where the modes would be clustered to339 determine the optimal tree structure. Unlike them, this work is the first to solve the optimal matching340 problem as illustrated in Figure. 1. Moreover, we are the only few to theoretically study the structure341 search issue for tensor networks. From the algorithmic aspect, the random-key trick in our coding342 method is first proposed by [4], and popularly applied to solving difficult sequencing tasks such as343 the “travelling salesman problem” and the “clique problem” [31] in computational graph theory. Our344 method is also close to the subgraph search issue in the recent work [41], yet we focus on the different345 tasks and issues.346
References347 [1] Pablo Arbelaez, Michael Maire, Charless Fowlkes, and Jitendra Malik. Contour detection348 and hierarchical image segmentation. IEEE transactions on pattern analysis and machine349 intelligence, 33(5):898–916, 2010.350
[2] Jonas Ballani and Lars Grasedyck. Tree adaptive approximation in the hierarchical tensor351 format. SIAM journal on scientific computing, 36(4):A1415–A1431, 2014.352
[3] Kim Batselier. The trouble with tensor ring decompositions. arXiv preprint arXiv:1811.03813,353 2018.354
[4] James C Bean. Genetic algorithms and random keys for sequencing and optimization. ORSA355 journal on computing, 6(2):154–160, 1994.356
[5] Lowell W Beineke, Robin J Wilson, Peter J Cameron, et al. Topics in algebraic graph theory,357 volume 102. Cambridge University Press, 2004.358
[6] Johann A Bengua, Ho N Phien, Hoang Duong Tuan, and Minh N Do. Efficient tensor completion359 for color image and video recovery: Low-rank tensor train. IEEE Transactions on Image360 Processing, 26(5):2466–2479, 2017.361
[7] Yunfeng Cai and Ping Li. Tensor completion via tensor networks with a tucker wrapper. arXiv362 preprint arXiv:2010.15819, 2020.363
[8] Yunfeng Cai and Ping Li. A blind block term decomposition of high order tensors. 2021.364
[9] Zhiyu Cheng, Baopu Li, Yanwen Fan, and Yingze Bao. A novel rank selection scheme in tensor365 ring decomposition based on reinforcement learning for deep neural networks. In ICASSP 2020-366 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP),367 pages 3292–3296. IEEE, 2020.368
[10] Andrzej Cichocki, Anh-Huy Phan, Qibin Zhao, Namgil Lee, Ivan Oseledets, Masashi Sugiyama,369 Danilo P Mandic, et al. Tensor networks for dimensionality reduction and large-scale opti-370 mization: Part 2 applications and future perspectives. Foundations and Trends® in Machine371 Learning, 9(6):431–673, 2017.372
[11] Lukasz Cincio, Jacek Dziarmaga, and Marek M Rams. Multiscale entanglement renormalization373 ansatz in two dimensions: quantum ising model. Physical Review Letters, 100(24):240603,374 2008.375
[12] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017.376
[13] Antonio Falcó, Wolfgang Hackbusch Nouy, et al. Geometry of tree-based tensor formats in377 tensor banach spaces. arXiv preprint arXiv:2011.08466, 2020.378
[14] Gary William Flake and Steve Lawrence. Efficient svm regression training with smo. Machine379 Learning, 46(1):271–290, 2002.380
[15] Cécile Haberstich, Anthony Nouy, and Guillaume Perrin. Active learning of tree tensor networks381 using optimal least-squares. arXiv preprint arXiv:2104.13436, 2021.382
[16] Wolfgang Hackbusch and Stefan Kühn. A new scheme for the tensor representation. Journal of383 Fourier analysis and applications, 15(5):706–722, 2009.384
[17] Meraj Hashemizadeh, Michelle Liu, Jacob Miller, and Guillaume Rabusseau. Adaptive tensor385 learning with tensor networks. arXiv preprint arXiv:2008.05437, 2020.386
[18] Cole Hawkins and Zheng Zhang. Bayesian tensorized neural networks with automatic rank387 selection. arXiv preprint arXiv:1905.10478, 2019.388
[19] Kohei Hayashi, Taiki Yamaguchi, Yohei Sugawara, and Shin-ichi Maeda. Exploring unexplored389 tensor network decompositions for convolutional neural networks. In Advances in Neural390 Information Processing Systems, pages 5553–5563, 2019.391
[20] Pavel Izmailov, Alexander Novikov, and Dmitry Kropotov. Scalable gaussian processes with392 billions of inducing inputs via tensor train decomposition. In International Conference on393 Artificial Intelligence and Statistics, pages 726–735. PMLR, 2018.394
[21] Maxim Kodryan, Dmitry Kropotov, and Dmitry Vetrov. Mars: Masked automatic ranks selection395 in tensor decompositions. arXiv preprint arXiv:2006.10859, 2020.396
[22] I Krasikov, A Lev, and BD Thatte. Upper bounds on the automorphism group of a graph.397 Discrete Math., 256(math. CO/0609425):489–493, 2006.398
[23] Joseph M Landsberg, Yang Qi, and Ke Ye. On the geometry of tensor network states. arXiv399 preprint arXiv:1105.4449, 2011.400
[24] Jose I Latorre. Image compression and entanglement. arXiv preprint quant-ph/0510031, 2005.401
[25] Chao Li and Zhun Sun. Evolutionary topology search for tensor network decomposition. In402 Proceedings of the 37th International Conference on Machine Learning (ICML), 2020.403
[26] Nannan Li, Yu Pan, Yaran Chen, Zixiang Ding, Dongbin Zhao, and Zenglin Xu. Heuristic rank404 selection with progressively searching tensor ring network. Complex & Intelligent Systems,405 pages 1–15, 2021.406
[27] Zhen Long, Ce Zhu, Jiani Liu, and Yipeng Liu. Bayesian low rank tensor ring model for image407 completion. arXiv preprint arXiv:2007.01055, 2020.408
[28] Oscar Mickelin and Sertac Karaman. On algorithms for and computing with the tensor ring409 decomposition. Numerical Linear Algebra with Applications, 27(3):e2289, 2020.410
[29] Román Orús. A practical introduction to tensor networks: Matrix product states and projected411 entangled pair states. Annals of Physics, 349:117–158, 2014.412
[30] Ivan V Oseledets. Tensor-train decomposition. SIAM Journal on Scientific Computing,413 33(5):2295–2317, 2011.414
[31] Panos M Pardalos and Jue Xue. The maximum clique problem. Journal of global Optimization,415 4(3):301–328, 1994.416
[32] Karl Pearson. Historical note on the origin of the normal curve of errors. Biometrika, pages417 402–404, 1924.418
[33] Justin Reyes and Miles Stoudenmire. A multi-scale tensor network architecture for classification419 and regression. arXiv preprint arXiv:2001.08286, 2020.420
[34] Farnaz Sedighin, Andrzej Cichocki, and Anh-Huy Phan. Adaptive rank selection for tensor ring421 decomposition. IEEE Journal of Selected Topics in Signal Processing, 15(3):454–463, 2021.422
[35] Zerui Tao and Qibin Zhao. Bayesian tensor ring decomposition for low rank tensor completion.423 In International Workshop on Tensor Network Representations in Machine Learning, IJCAI,424 2020.425
[36] Ledyard R Tucker. Some mathematical notes on three-mode factor analysis. Psychometrika,426 31(3):279–311, 1966.427
[37] Pınar Tüfekci. Prediction of full load electrical power output of a base load operated combined428 cycle power plant using machine learning methods. International Journal of Electrical Power429 & Energy Systems, 60:126–140, 2014.430
[38] Frank Verstraete and J Ignacio Cirac. Renormalization algorithms for quantum-many body431 systems in two and higher dimensions. arXiv preprint cond-mat/0407066, 2004.432
[39] Wenqi Wang, Vaneet Aggarwal, and Shuchin Aeron. Efficient low rank tensor ring completion.433 In Proceedings of the IEEE International Conference on Computer Vision, pages 5697–5705,434 2017.435
[40] Allan G Weber. The usc-sipi image database version 5. USC-SIPI Report, 315(1), 1997.436
[41] Hansi Yang, Quanming Yao, and James Kwok. Tensorizing subgraph search in the supernet.437 arXiv preprint arXiv:2101.01078, 2021.438
[42] Ke Ye and Lek-Heng Lim. Tensor network ranks. arXiv preprint arXiv:1801.02662, 2019.439
[43] Tatsuya Yokota, Qibin Zhao, and Andrzej Cichocki. Smooth parafac decomposition for tensor440 completion. IEEE Transactions on Signal Processing, 64(20):5423–5436, 2016.441
[44] Longhao Yuan, Chao Li, Danilo Mandic, Jianting Cao, and Qibin Zhao. Tensor ring decomposi-442 tion with rank minimization on latent space: An efficient approach for tensor completion. In443 Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 9151–9158,444 2019.445
[45] Longhao Yuan, Qibin Zhao, Lihua Gui, and Jianting Cao. High-order tensor completion via446 gradient-based optimization under tensor train format. Signal Processing: Image Communica-447 tion, 73:53–61, 2019.448
[46] Qibin Zhao, Liqing Zhang, and Andrzej Cichocki. Bayesian cp factorization of incomplete449 tensors with automatic rank determination. IEEE transactions on pattern analysis and machine450 intelligence, 37(9):1751–1763, 2015.451
[47] Qibin Zhao, Guoxu Zhou, Shengli Xie, Liqing Zhang, and Andrzej Cichocki. Tensor ring452 decomposition. arXiv preprint arXiv:1606.05535, 2016.453
[48] Yu-Bang Zheng, Ting-Zhu Huang, Xi-Le Zhao, Qibin Zhao, and Tai-Xiang Jiang. Fully-454 connected tensor network decomposition and its application to higher-order tensor completion.455 2021.456
Checklist457
1. For all authors...458 (a) Do the main claims made in the abstract and introduction accurately reflect the paper’s459 contributions and scope? [Yes]460 (b) Did you describe the limitations of your work? [Yes] See Section 5461 (c) Did you discuss any potential negative societal impacts of your work? [N/A]462 (d) Have you read the ethics review guidelines and ensured that your paper conforms to463 them? [Yes]464 2. If you are including theoretical results...465
(a) Did you state the full set of assumptions of all theoretical results? [Yes]466 (b) Did you include complete proofs of all theoretical results? [Yes] All proofs are given467 in the supplementary material.468 3. If you ran experiments...469
(a) Did you include the code, data, and instructions needed to reproduce the main exper-470 imental results (either in the supplemental material or as a URL)? [Yes] Codes with471 illustrative experiments is uploaded472
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they473 were chosen)? [Yes] See the supplementary material.474
(c) Did you report error bars (e.g., with respect to the random seed after running experi-475 ments multiple times)? [No] Yet we show the results for each sample such as images476 or synthetic data in the supplementary material. The error bars can be estimated from477 those results.478
(d) Did you include the total amount of compute and the type of resources used (e.g., type479 of GPUs, internal cluster, or cloud provider)? [Yes] See the supplementary material.480
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...481 (a) If your work uses existing assets, did you cite the creators? [N/A]482 (b) Did you mention the license of the assets? [N/A]483 (c) Did you include any new assets either in the supplemental material or as a URL? [N/A]484
485
(d) Did you discuss whether and how consent was obtained from people whose data you’re486 using/curating? [N/A]487
(e) Did you discuss whether the data you are using/curating contains personally identifiable488 information or offensive content? [N/A]489
5. If you used crowdsourcing or conducted research with human subjects...490 (a) Did you include the full text of instructions given to participants and screenshots, if491 applicable? [N/A]492 (b) Did you describe any potential participant risks, with links to Institutional Review493 Board (IRB) approvals, if applicable? [N/A]494 (c) Did you include the estimated hourly wage paid to participants and the total amount495 spent on participant compensation? [N/A]496

Review summaries:
	This paper shows that the graph constrained TNs are irregular, which makes it tricky for the conventional search algorithms on grids to obtain feasible solutions. Under this situation, according to universal cardinality bound across a series of practical TNs, this paper construct regular discrete space, representing those irregular TNs in a compact manner. At last, this paper proposes the “random-key” trick to encode TN structures into fix-length strings(i.e., coding space). In the regular coding space, population-based algorithms with the proposed coding method can search TNs effectively. And the experiments demonstrate the good performance of the proposed methods.

This paper addresses a new problem when searching for an optimal structure in the tensor network representation on the condition that the graph's topological structure is constrained and isomorphic to a specific graph G_0. TNR is more flexible than the classical tensor decomposition in terms of its high freedom of how the multiplication among multiple core tensors is done. However, if a specific graph structure is preferred such as TT or TR, when representing the topological structure of TNR by an adjacency matrix, the adjacency matrix may not be the best representation form due to its inability to identify those isomorphic graphs. The proposed work firstly attempted to prove that there exists a bijective mapping from a rank vector r to any graph in an automorphic set. Then, the permutation vector p from the bijective mapping concatenated with r is an encoding vector of a specific graph in the automorphic set. The encoding vector can be used in the later search problem via GA or other population-based algorithms. Some experiments were done to prove the efficacy of the encoding by showing that via the proposed encoding method GA can find the solution quicker and better compared with other baseline methods.   

The paper develop a means of identifying graphical structures which allow a tensor network (TN) to best fit a given input tensor. In contrast to previous work on this topic, a defining graph for the TN is also taken as input, and the optimal vertex permutation (i.e. an assignment of the vertices of the graph to the modes of the tensor) is learned, alongside an optimal choice of TN ranks for the graph in question. The paper gives both theoretical results characterizing the search space of valid TN configurations for this problem, as well as a new search method building on a previous genetic search algorithm [Chao Li and Zhun Sun 2020, "Evolutionary topology search for tensor network decomposition"] in this more limited setting. Experiments on synthetic tensors and real-world data show the efficacy of this new method in practice.