Graph-Constrained Structure Search for Tensor Network Representation
Authors: Chao Li
Junhua Zeng
Zerui Tao
Qibin Zhao
Venue: NeurIPS 2021 Submitted (2021)
Keywords: Tensor network
structure search
tensor decomposition

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

21 It is of importance to select an appropriate structure in the practical Graph-Constrained Structure Search for Tensor Network Representation
Anonymous Author(s)
Affiliation
Address
email
Abstract
Recent works paid effort on the structure search issue for tensor network (TN) representation, of which the aim is select the optimal network for TN contraction to fit a tensor. In practice, however, it is more inclined to solve its sub-problem: searching TN structures from candidates with similar topology like cycle or lat- tice. We name this problem the graph-com conph---ndtraieedd structure search, and it remains open this date. In this work, we conduct thorough investigation of this issue from both the theoretical and practical aspects. Theoretically, we prove that the TN structures are generally irregular under graph constraints yet can be universally embedded into fow-dimensional regular discrete space. Guided by the theoretical results, we propose a simple algorithm, which can encode the graph-constrained TN structures into fixed-length strings for practical purposes by a "random-key trick, and empirical results demonstrate the effectiveness and efficiency of the proposed coding method on extensive benchmark TN representation tasks.
10
11
12
Introduction
14
Tensor networks (TNs) are recognized popular framework for solving extremely 16 high-dimensional problems arising in domains such as quantum simulation, machine learning and signal processing. In general, TNs are used to represent the high- 18 dimensional states/models/ddtta by a network of low-dimensional tensors (akaa, cores), computation and storage would be significantly reduced.
such that the requirement
20
22 use of TNs. There are many studies on learning TN ranks for specific name few, and recently several works 24 paid the effort on learning more general TN structures with arbitrary Surprisingly, however, none of them can 26 effectively solve a seemly easier task: how to learn the optimal matching TN? For instance as illustrated in 28 Figure [ there are three different candidates to represent a tensor by tensor ring (TR) [47]. We need algorithms, which can learn the optimal
models 126-28, 43
46 47
topology 17 21 25
B
D
from the modes onto the cores
30 one from the three. It is actually a special case of learning the optimal TN structures under graph constraints, sub-problem of the existing
decompostion
32 structure search for TNN representation.
Figure 1: Which tensor ring (TR) the optimal?
The state of affairs raises important unresolved questions. Is the afore- mentioned task really easier than the general structure search? What the properties of TN structures under graph constraints, and how to effectively solve the problem in practice?
34
36
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

37 In this work, we shed light on these questions through theoretical and empirical investigation of the graph-constrained TN structures.
38
39 We first prove the graph constraint makes TN structures being irregular. In particular, both the addition and random perturbation is not closed on the candidate set. This result helps explain
40
41 why the conventional search algorithms on grids give no guarantee of feasibility of the solutions. Furthermore, on the scale of the search problem, we prove the symmeetry of the graph-constraint plays a role to determine the cardinality of TN structures, yet there exists a universal cardinality bound across a varies of practical TNs, such as tensor train (TT) (00, tensor ring (TR) and PEPS [38]. The result reveals the possibility to construct regular discrete space, from which we can represent those irregular TN structures by elements in a compact manner.
42
43
44
45
46
47
Guided by the theoretical results, this work also sheds light on a practical solution for the graph- constrained structure search issue. We propose novel coding method to encode TN structures into fix-length strings by a "random-key" trick, a random mapping from TN structure space to coding space. The regularity of the coding space allows apply the population-base with the proposed coding method to tackling the search issue for TN representation effectively, We conduct extensive experimentation on a variety of benchmarks. The results show that the proposed method often obtain better TN structures than many existing rank-selection and structure search algorithms.
49
50
algorithms equipped
51
52
58
54
55
2
Preliminaries and problem setup
56
In this section, we present the basic concepts on tensor network (TN), and give a formal definition of the graph--constrained structure search for TN representation.
57
2.1
Tensor network (TN) and structure search for tensor network representation (TNR)
59
An order-N tensor is a multi-dimensional array of real numbers represented by X,, Sa...,. E T x xaxx where im m E [N] is defined as the index regarding the mth mode of X and [N] denotes set of integers from 1 to N. Tensor contraction [10]. binary operation defined as a multiplication of two tensors under their same indices. For instance, given two order-2
60
tensors, is
62
tensors Ai, E IR. By, / the tensor contraction of A and B under the index returns
63
C.A= Bi, E RI which is equivalent the matrix multiplication.
65
tensor network (TN) is roughly defined as collection of tensors (a.k.a,, cores), which are tensor- contracod under some, or all, of their indices according to a specific pattern (29. Recent
66
67 works 25 show that the "patterns" of TNs can be precisely described by edge-weighted simple
68 graphs. TN structures thus can be formulated by adjacency matrices of graphs. Formally, we define
69 the TN with general "pattern" as follows.
0, Vi E [N, and A AT an order-N tensor network (TN) of the size 11 x 12 X ... X IN under structure A E AR defines mapping: :
Definition 1 (Tensor network.) Let Ar {A (ZR-1)
NXN (A
71
72
x = A) B4xI1x-xIxx
(1)
73 where = E [N]} represents collection of cores in which the size Vi, i E [N] equals the multiplication of and all non-zero entries of A (ii,)) :), and TN (N; denotes a series of tensor contractions V under the indices [25] described by A.
74
75
We observe that Definitinn. models rich family of TNs with the ranks upper- bounded by R (due 77 to IR+1), 1). including TT, TR, PEPS and etc., but also note that the TNs that contain internal cores are
78 not included in this form.
79 Tensor network representation (TNR) a tensor X' is defined as finding a specific core-set such that Eq. ( holds. The structure search for TNR is thus to find the optimal matrix A e Åg. such that
81 X can be represented by V that satisfies Eq. (T. In particular, the search problem can be solved by
min (A),,, AEAR
s.t. X (V; A) for some V,
(2)
'The indices would be omitted for brevity if there is no confusion.

---

82
where Øx Ar + I denotes measure of the TN structures like compression ratio. Note that similar frameworks were also introduced in works [ where the entries of A corresponds to the TN-ranks formulated as a vector in those works. Lemma Sec. will show the matrix form of
83
84
85
A would provide additional structural information to analyse the property of TN structures.
86
2.2
Graph-constrained structure search for TNR
87
The graph-constrained structure search issue is also modeled as (2) yet constraining the feasible space R into a graph-induced subset, which the TN structures have similar topological forms. To build the connection to graphs, we first show the existence of a bijective mapping from Ag to graph space.
86
89
90
Lemma 2 There is bijective mapping VP An Gn. where GR denotes set containing all possible vertex-labeled simple yet weighted graphs (G,RR) = (V, with vertices and a edge-weighting function fR:e E E--- + [R], and we name the unweighted part G the topology of TN a TN structure.
92
93
94
95
The claim is naturally true by the relation between graphs and the adjacency matrices. The bijection in Lemma 2 implies that for each A E An can always find unique (G. fn) corresponding to it. Table in the supplementary material illustrates the correspondence between graphs and the well-knoww TNs. We construct graph-constrained TN structures by the isomorphism of graph
87
89
Go (V, Fb) and the mapping V given in Lemma 2
A formal definition is given as follow.
100
Definition (Graph-constrained TN structures.) Given a vertex-labeled simple graph Go = the TN structures under Go defined as V, Eo) and the mapping y in Lemma 2
HG. {H & AR G _ Go where (GH,JRRH (H)),
(3)
102
where denotes the graph isomorphism.
103
As given in Definition 3 HG.,R R is a subset of Ag and its elements own the topologies being isomorphic to Go. For instance, suppose Go to be a cycle graph of 4 vertices, i.e., C4. then H contains all TR structures of order-4 with the ranks upper-bounded by R Figure [ is thus expected to solve the mentioned optimal matching problem by searching structures on HG.. Not only that, but also note HG., Rt equals R if Go is completion graph, i.e., KN. Next, we define the problem of constraidd structure search for TNR by Ho.,
104
105
106
107
108
109
Definition (Graph-constrainee structure search for TNR.) Given a graph Go and the corre- the graph-constrained structure search for TNR is to solve sponding HG..R obtained as Definition 3 the following problem:
111
s.t. X (N H) for some V. ox (xH HE
min
112 It is shown from Definition 4 that the set HG..R restricts the optimization process only searching on
113 the TN structures, which has the same topology Go up to permutations of the vertices [5]. Moreover, although 4 owns similar form to its unconstrained counterpart (2). it will be proved in the next section that the existing algorithms on (2) may be not available on the graph-constrained search issue.
114
115
116
Note that Definition D allows the entries of A to equal 1, which implies the rank-one contraction between cores. According to the fact given in [25] 42 that the weight-one edges can be removed from TNs, we thus know that the solution of 4 would have a subgraph of Go as its "true" topology. Therefore, solving has the capability of achieving not only isomorphic but also
Remark.
117
118
119
120
subgraphs of Go-
3 Algebraic properties of graph-constrained TN structures
122 In this section, we focus on the properties of HG., the set containing all TN structures constrained under graph Gg. From an algebraic perspective, we first show HH., is irregular under most of
124 graph constraints by proving that the set not closed under addition and random perturbation. After that, we analyse the cardinality of HiG.. R, which reflects the scale of the search problem. We derive
3

---

128
the precise cardinality of H.G... across many well-known TNs, and prove a universal cardinality bound of H...R R under all connected low-degree graphs.
127
128
To understand the property of H. we first prove all its elements own a factorization of the multiplication of rank-induced matrix and permutation matrix.
129
Lemma 5 (Factorization of R.) Given vertex-labeled simple graph Go (V, En), for any RR there exists a permutation matrix P of the size [V] x [V] and a bijective linear mapping nG. (Zn+1) Eal
131
He E IR.
(I.nt1) x|VI such that H can be factorized as
132
H PΩG. (r)PT
(5)
denotes the cardinality and E (2n+1) Boll denotes the rank vector of dimension |ol
where|
134
Intuitively, Lemma 5 implies that the rank- lank-induced matrix Qg. (r) forms a linear sub-space of dimension Eol, then H.G.. n takes all "flips and rotations" of the subspace into account due to the permutation matrix P. A visual illustration of lHG.. is shown on the most left of Figure 2 We can see that H has an "irregular shape" visually, and this property formally proved as tollows.
135
136
137
138
Proposition 6 (Irregularity of R.) Assuming R 2 the following two claims are held.
139
1. Addition (modulo R + 1) is not closed on Ho.. if Go = Ev) or its complement is not complete;
140
141
2. With relatively spurse graph Go, the cernoulliddistribute perturbation on HGG,, is not closed with a probability approximately being larger than (1- - 1/
1/2
143
The proof is given as supplementary material. Proposition @effectively say that the operations used in common search algorithms, such the recombination and mutation in genetic algorithms (GAs) or progressive search in greedy methods, cannot guarantee the outputs being contained by H... R. leading to the invalidation of those algorithms on this issue.
145
147
Next, we jump to the cardinality of HGG.RR which reflects how many candidates we have under graph constraint. From a information-theoree required code length on TN structures general. smaller cardinality generally implies a easier search process especially for the population- algorithms. Below, we first prove the cardinality of HG... under general graph constraint.
148
perspective, the cardinality is proportional to the least
149
150
151
152
Lemma (Cardinality of H.....R.) Given a vertex-labelled simple graph Go (V, Eo), we have log([HGo,RR) |Eo] log( + -og(((())-log((AAA lou((Aul(Go))))
-
(6)
153
where log(.) denotes the natural logarithm and Aut(Go) denotes the graph automorphisms Go-
154
As shown on the right of Eq. (6. the first two terms correspond to the TN-ranks and permutations as Lemma 5 respectively, while the third term (utttl reflects the symmetry of Gg. it implies the cardinality of H. would be small if Go owns strong symmetry. From the TN perspective, means the TNs with symmetric topologies like TR and the complete TN (CTN) 48 are expected to
156
own a smaller size of HG..R. For those well-known TNs, we show their corresponding cardinality of HiG n as follow.
158
159
Proposition 8 Assume order-N TN models, of which the ranks are upper-bounded by R, then have
181
1. TT 30
log( H Px. (x) Rx) (N 1) log( R2) + log(NN) log(2)
163
2. TR [47
log [[ RR) N (R) + log ((N 1)!) log(2)
164
3. CTN [48]:
log (H .R)) = (N2 - N) log R2/2
185
4. T-tree 44
(N - 1) log(1t) - log(N) < log (T, Rl) S 1og([HpxxxR))
186
5.
PEPS 38 log( H
(2mn m - n) Rog(R) + (og((m))]] log(4)
187
6. Tucker 36): log(HH,,,)) = N log(R) R))
Note that the Tucker model is not strictly contained by Definition.

---

168
In Proposition 8 the inequalities for the T-tree models is due to the variety of the tree structures, and in PEPS the equality is held if m and n are relatively prime. We observe from Proposition [8 that
169
170
TR would have a smaller Hz rt than TT in the case of large N. It is intuitively true since the TR structure more symmetric than the one of TT. However, we also observe that, except CTN and the
171
172
Tucker model, there always exists a factorial of N in the equations for the rest of TNs. It implies that the cardinality of H.G,, R for those TNs is not significantly different from each other. Below, we prove the fact is true for all TNs, of which the corresponding Go is connected and low-degree.
173
175
Proposition 9 (A universal cardinality bound on l.l.. R.) Assume Go (V, Eo) is connected graph and its maximum degree Ago is a constant that is far less than [V], then we have
176
log( ul) 2 O (oV) (R) + (V)log((V)))
177
where O.)) denotes the big-O notation.
The result is proved by bounding the both |Eo] and [Aut(Go)] in Lemma by the maximum degree GG, using the Handshaking lemma known in graph theory and Theorem 2 given in [22), respectively. In addition, we also use the Stirling's 's approximation [32] to obtain tight bound for the logarithm of factorials to further simplify the expression.
178
179
180
182
The assumption of small Ago is reasonable since in the practical TNs the cores are expected to be low-order (see Table 1 given in the supplementary material for instance). Proposition 9 means that there is a Go-independent bound on the cardinality of H...R R for all connected and low-degree graphs, and we can see the bound is relatively tight by intuitively comparing the results with Proposition [
183
184
185
As shown in 7. the first term V log [R) corresponds to the number of all possible ranks bounded by R. and the second term [V] lo'((V)) has the same scale to log([V[!) for the Stirling's 's approximation. It implies that, in the case of connected and low-degree Go. the cardinality of lHl.,, is close to the combination of all possible ΩG, (r) and P in Lemma [5] In other words, the factorization given in Lemma is nearly unique on H. From pragmatic perspective, the result say that we can solve the constrained structure search issue from the factorization space as a alternative. More importantly, such the factorization space is independent to topology, because Go only determine the mapping Qo. which is bijective, linear and fixed beforehand. The result guides us to find the practical solution on the graph-constrained structure search issue from the factorization space.
187
189
190
191
192
193
194
Encoding graph-constrained TN structures via a random-key trick
195
196
Inspired by the theoretical results, we introduce practical coding method embed the irregular TN structures into a regular discrete space, in which the population-base based metaheuristics like GAs can be directly used for structure search. Last, experiments variety of benchmarks are implemented to demonstrate the effectiveness of the method.
197
198
199
200
4.1 Method
Figure. depicts the coding process. We encode the elements of Hl n from two ingredients: the rank-induced matrix Lo, (r) and the permutation P as Lemma 5 For the former, since the mapping
202
203
lco is bijective and linear, the rank vector of dimension Fg directly used as the code for this ingredient.
204
For the latter, we randomly embed P into the space [o. 11, a set of decimal number vectors, by random-key trick [4) which is popularly used to solve the optimal sequencing tasks. For the details, the random-key representation encode a permutation with a vector of random numbers from [0, 1}. and the order of these random numbers reflects the permutation. For instance, the code (0.46, 0.91, 0.33) would represent the permutation 2 + 3 + 1, by which we naturally have its matrix form P. Finally,the encoded strings are simply the concatenation of the two ingredients.
205
207
209
211
One advantage of the random-key trick is robustness to the structure of H.G..R. Regardless of the irregularity of HH R. we always have the regular key space [0, 1]lVI, on which the operations such as addition and perturbation are always available. It implies that the proposed coding method is Go-independent, and many population-based metheuristics such as the one in (5 can be directly
212
214
applied to graph-constrained structure search (see the numerical results given below.).
5

---

[
runk-vector
Lemma
(NGO (r),
concatenation
0. Ijl
H.G.. R
random-key
encoded strings
(Grapl-constrained TN structures)
Figure 2: Illustration of encoding the graph-constrrined TN structures into fixed-length strings. As L the structures are factorized by the rank-induced matrix Sag (r) and permutation matrix P. In the method, GGo (r) is encoded by its non-zero entries, i.e. the rank-vector r, into the space [R] (the orange square). By the random-ked key trick, P is represented vector of random number in the "key space" typically [0, 1 (the square with mixed color in the figure). The final string is obtained by the concatenation of the two aspects. Note that, in the key space, different elements in the area with the same color represent the same permutation.
216
The proposed method gives more compact codes than the work in 225 the graph-constraint scenario, directly encoding the entries of the adjacency matrix as 255 cannot consider the "low- dimensional enssence" of HiG.,. due to the irregularity. However, by the proposed method, the code length is shorted as ((V) compared to O( (2)) in [25]. shorter code length implies faster convergence and lower computational requirement for the population-base methods in general. For the proposed method, we also prove the coding efficiency given in the supplementary material, which
218
219
221
reflects the gap of the code length from the Shannon entropy HGG.
4.2
Numerical results
224
In this section, we evaluate the practical effectiveness and efficiency of the proposed coding method on various benchmark tasks for tensor network representation (TNR).
226
4.2.1
Searching the optimal TN structures on synthetic data in TR format and beyond.
227
In this experiment, we examine whether using the proposed coding method can learn sufficiently good low-dimensional representation on synthetic tensors TR (including TT) format.
228
229
Data generation. We generate batches of tensors with randomly selecting TR structures. Specifically, first let the dimension of each tensor mode equal Then, we randomly generate the TR-ranks at discrete uniform distribution on {1, 2, 2,3,4 4} and the cores at Gaussian distribution N 1), and randomly permute the tensor modes after contracting the cores.
230
231
232
233
Experiment setup. The proposed coding method are directly applied to the genetic algorithm (GA) in [5] by replacing its chromosome design aspect, where let Go be cycle graph and the rank bound R be equal to 7. Details of hyper-pann paper-parameters on the GA are introduced in the supplementary material. For comparison,
235
also implement various types of TR decomposition methods with adaptive rank selection, which include the singular value decomposition (SVD) based method TR-
237
238
SVD [7]. beast-squars--based method TR-ALSAR (7). Bayesian model Bayes-TR (35), and two
239
general heuristics TR-LM 28 (exhaustive search) and TNGA 25 (population-based)
The experimental results reported in Table I where the tensor order covers {4, 6, 8} and the 5 generated tensors for each order are denoted as Trial A~E. For performance evaluation, we use the Eff. index (25]. the ratio of number of parameters between the learned structures and the ground-trute TRs, to illustrate the model efficiency. We also illustrate the relative square error (RSE) and the generation (Gen.) of the optimal individuals in TNGA and ours in the table.
241
243
245
Results. As shown in Table only our method can always achieve the same or lower-dimensional representation than the ground-truth. We observe that most of the TR decomposition methods fail dealing with the permutation on tensor-modes, and such the fact would limit the application of the TR methods in the practical use high-order problems. We also observe the performance of
247

---

Table 1: Experimental results of searching structures on synthetic data in TR format. In the table, Efft denotes the parameter ratio between the structures by different methods and the ground-truths; RSE in round brackets indicates the relative square error (ignored if smaller than 10 .) and Gen. in angle brackets indicates the generation of the reported individual in TNGA and our method.
Order 4 (RSEL) (Gen.l)
Trial
TR-SVD
TR-LM 28
TR-ALSAR 47
Bayes-
TNGA 25
Ours
1.00
1.00
0.21
1.00
1.00 (004)
1.00 (003)
B
0,64
1.00
1.00
0.64
1,00 (002)
1.00 (003)
CCC
1.17
1.17
0.23
1,00
1.17 (005)
1.17 (003)
D
0.57
0.57
0.32
1.25 (0.10)
1.00 (003)
1.00 (002)
0.43
0.48
0.40
0.40
1.00 (007)
1.00 (003)
Order 6 Efft (RSEL) (Gen.4)
Trial
TR-SVD 47
TR-LM 28
TR-ALSAR 47
Bayes-TR (35
TNGA 25
Ours
A
0.21
0.44
0.14 (2e-3)
0.25 (2e-3)
0.82 (011)
1.00 (010)
B
0.14
0.15
0.14
0.44 (0.40)
0.90 (6e-3) (015)
1.00 (009)
0.57
1.00
0.85
0.29
1.00 (022)
1.00 (012)
0.21
0.39
0.10
0.13
1.03 (018)
1.16 (010)
0.15
0.30
0.01 (0.02)
0.12
1.00 (016)
1.00 (007)
Order 8 Fff (RSEL) (Gen.
Trial
TR-SVD 47
TR-LM 28
TR-ALSAR
Bayes-TR
TNGA 25
Ours
0.10
0.16
0.03 (0.20)
0.03
0.48 (017)
1.00 (019)
B
0.09
0.43
0.06 (0.02)
0.06 (7e-4)
0.29 (2e-3) (020)
1.02 (015)
C 0.03
0.31
0.02 (0.01)
0.02
0.49 (015)
1.11 (025)
D 0.20
0.53
0,02 (0.07)
0.02 (0.02)
0.32 (027)
1.06 (013)
0.33
0.33
0.02 (0.02)
0.02 (3e-3)
0.23 (023)
0.88 (010)
Table Experimental results of searching structures on synthetic data in various TN format. In the table, Eff. denotes the parameter ratio between the structures by different methods and the ground- truths; RSE in round brackets indicates the relative square error (ignored if smaller than 10 10-4.) and Gen. in angle brackets indicates the generation of the reported individual of our methods. For rows, "ranks" means we fix the permutation part yet only learning the ranks, while "ranks+matching" means both the optimal ranks and permutation are learned.
Trial Eff.t (RSEL) (Gen.))
TNs
Our method
A
B
D
ranks
0.40 (005)
0.41 (0.02) (008)
0.40 (9e-3) (006)
0.65 (0.04) (005)
T-Tree 42
ranks+matching
1.29 (016)
1.17 (014)
1.11 (012)
1.55 (012)
ranks
0.41 (010)
0.43 (0.02) (024)
0.39 (6e-3) (027)
0.71 (005)
PEPS 38
ranks+macching
1.14 (013)
1.00 (016)
1.00 (007)
1.21 (009)
ranks
0.49 (0.01) (014)
0.64 (010)
1.09 (012)
0.81 (006)
H-Tucker 16
ranks+marte matching
1.42 (008)
1.21 (023)
1.18 (007)
1.29 (011)
ranks
0.72 (0.01) (012)
0.95 (011)
1.93 (011)
0.65 (0.04) (014)
MERA
ranks+ matching
0.95 (024)
1.32 (008)
2.30 (024)
1.00 (027)
249
TNGA appears dramatically deterioration when increasing the tensor order. As analyzed at the end of Section 4.1 TNGA suffers from the dimension explosion of the search space. In this case, TNGA has to search the solution from about 4.6 x 20 candidates, which almost 8.0 x 10 larger than the one of ours.
251
253
structure search not limit to TR. The proposed coding method is also useful for many well- known TNs in machine learning and physic not limit to TR. Under similar setup for TR, we apply the proposed method to the TNs including T-tree (order-7) [42]. PEPS (order-6) (38), hieratical Tucker (H-Tucker, order-6) [6 and multi-scale entanglement renormalization ansatz (MERA,
255

---

257
1 33 Details of the data generation phase are given in the supplementary material. Table 2 illustrates the Eff., RSE and Gen. values by our method, where the rows of "ranks" mean we only learn the optimal TN-ranks while the rows of "ranks+matching" mean both the ranks and permutation are learned by our method. As shown Table our method achieves the TN structures as good as or even better than the ground-truth for various TNs. In addition, we also observe that correct permutation on modes would significantly improve the representational power of TNs.
order-8)
258
260
262
263
4.2.2
Benchmarks on real-world data
264
We consider three benchmark TNR problem on real-world data, where two of them is to represent the data and the other one represent learning models. Details of the experiment setup and more results are given in the supplementary material.
265
266
267
1. Image compression. We use GA equipped with the proposed coding method (in TR format) to compress 14 natural images randomly chosen from BSD500 [1, where images are grayscaled, resized by 256 x 256, and tensorized into order-8 tensors by two different tensorization: a "Python like" reshaping operation denoted by "Trivial" and visual data serage-resolutionbaaeeee
268
269
270
271
tensorization (VDT) 6 24 451,
tensorization method. As the result, we show the compression ratio (CR, in log form) and RSE (in round brackets) by the methods TR-SVD, TR-LM and ours in Table and visualize the summary statistics of the learned permutation by our method in Figure
273
274
275
2.
Image completion.
The same method is also implemented on image completion, a task predict missing pixels from the observation. In the experiment, 8 images from USC- SIPI [40] are chosen and tensorized by VDT of order-9. After that, the entries are randomly removed at uniform distribution under the missing rate (50%, 70%. 90%), ). respectively. We
277
278
279
show the average of RSE of predicting the missing values in Table 4 compared with the TT/TR completion methods TT-SGD E5,, TRLRE 44,, TRALS 33
280
3. Reparameterization of tensorial Gaussian process (GP). TNR is applied to parameteriz- ing the variational mean of GPs. In the experiment, we reparameterize the TT variational mean given in [20] by our method to search better structures. In a regression task on datasets CCPP 37 MG [4] and Protein [1]. we have the TT variational mean of the order- (4, 6, 9}. respectively. In the result, we evaluate the performance by the number of
282
284
206
parameters and mean square error (MSE, in the round brackets) shown in Table
Table 3: Average of log compression ratio and Table 4: Average of RSE on image comple- RSE (in round brackets) for image decomposition. tion under various missing percentage.
TR-SVD 47
TR-LM 28
Ours
TTSGD 45
TRLRF
TRALS
33 Ours
Trivial VDT
0.95(0.14)
0,94(0.14)
1.35(0.14)
50%
0.16
0.12
0.13
0.11
1.11(0.15)
1.0(0..4)
1.30(0.14)
70%
0.17
0.13
0.13
0.12
90%
0.18
0.20
0.18
0.16
0.8
Similarity
5-06
Table 5: Number of parameters and MSE (in round brackets) of GP regression under three datasets.
30.4
Trivial VDT
0.
Trival
VITT
Experiments
Similarity
CCPP
MG
Protein
(a)
(b)
TTGP 20
2640 (0.06) 3360 (0.33)
2880 (0.74)
Figure 3: Visualization of statistics on the similar- Ours
2244 (0.06) 3008 (0.33)
2032 (0.74)
ity to the original permutation.
288
289
VDT is verified as a more effective way for tensorization. The results in Table 3 show that, our method owns higher compression ratio under close RSE compared other methods. More importantly, the results show significant difference when learning structures from two tensorization.
290
291
292
Figure 3 illustrrate the statistics on the similarity between the original permutation and the learned ones by our method. We observe from Figure a) that in VDT the learned permutation is significuntly closer to the original one than that in the "Trivial". Additionally, Figure shows the cumulative see that, in VDT the probability is larger than 0.8 for
294
distribution function (CDF), where
8

---

296
the similarity being smaller than or equal to 2. It implies that with large probability the learned structures in VDT own most a pair of permutation difference compared to the original one. On the contrary, for "Trivial" the probability is almost zero in the same interval. Hence, it is verified from the empirical results by our method that VDT is more effective way for image tensorization than the trivially reshaping operations.
297
299
300
301
Exploring TN structures obtains lower-dimensional representation from incomplete data. As shown in Table E our method achieve a comparable performance on the image completion task. Especially when the missing ratio is high, our method forced to explore better TN structures not representation would be applied and results in
302
303
304
limit to the ranks, such that the more accurate prediction. Similar claims were also discussed in recent works [7]
305
306
tensoorreparammetetizaio:: a potential way to compress learning models. TNs are known as an efficient framework compress learnables variables by low-dimensional cores. In the experi- Ment, we illustrate from a "proof-of-concey"
307
308
level that the model would be further compressed by re- re-parameterizing the learned TN in model. As shown in Table we always use fewer parameters
309
310
than its "teacher" model TTGP [20] to achieve the same MSE on the three datasets. It implies that our method give more efficient TNR by search better structures. Unlike training the model with simultaneously searching TN structures, we empirically find that searching better structures from the
311
312
313
well relletrained model in TN format would achieve better compression ratio. We intuitively conjecture
314
that, by structure search, it is likely to obtain more efficient representation for a tensor, which has been in low-rank TN format. In the training phase, on the other hand, the models are not significantly
315
316
low-rank in general. Therefore, the tensor reparameterization often gives better performance in practice. rigorous analysis on this issue is still an open problem.
317
5
Discussion
318
319
Our experiments show good TN structures including ranks and permutations can be effectively learned in practice by the proposed coding method under extensive family of graph constraints, and our theoretical results show the the superior performance is thanks to the low-dimensional essence hidden behind the irregularity of the graph-constrained TN structures. More surprisingly. Proposition shows that such the low-dimensional essence of TN structures is ubiquitous for most of practical TNs. As a consequence, we expect this work can promote the understanding on the structure search issue on tensor networks from both the theoretical and practical aspects, and the empirical claims in experiments are also expected to inspire more potential applications of TNs in machine learning.
320
321
322
323
324
325
326
327
Limitation. Theoretically, we only study the TNs, which do not contain the internal cores. Some well-known models like (H-)Tucker and MERA are not contained in the theory, although the proposed coding method works well for those models in experiments. Empirically, the proposed coding method more suitable for the population-based methods like GAs, which are still computationally expensive compared to other heuristics. Also, the experiments on real-world benchmarks are only illustrative and proof-of-concept. More numerical results are necessary if stronger statements such as the performance improvement are expected.
328
329
330
331
332
333
Related works
334
335
Learning the optimal TN structures is generalization of the rank selection issue for TN models g
9
336
18
26 34
43)
46. 47]. and it is known as a tough task especially for the models that contain cycles
337
the topology [ 23 42). More recently, there are several studies on learning TN structures [17 19
338
25) in more general form. Another line of works that are close to ours are studies focusing on the partition issue for H-Tucker decomposition 2 13 [5), where the modes would be clustered to determine the optimal tree structure. Unlike them, this work is the first to solve the optimal matching
339
340
341
problem as illustrated in Figure. [ Moreover, we are the only few to theoretically study the structure search issue for tensor networks. From the algorithmic aspect, the random- key trick in our coding method is first proposed by 44, and popularly applied to solving difficult sequencing tasks such as the "travelling salesman problem" and the "clique problem" KIl in computational graph theory. Our method is also close to the subgraph search issue the recent work 41. yet we focus on the different
342
343
345
tasks and issues.

---

References
347
348
[1] Pablo Arbelaez, Michael Maire, Charless Fowlkes, and Jitendra Malik. Contour detection and hierarchical image segmentation. IEEE transactions on pattern analysis and machine intelligence, 33(5):898-99) 996, 2010.
350
[2] Jonas Ballani and Lars Grasedyck. Tree adaptive approximation in the hierarchical tensor format. SIAM journal on scientific computing, 36(4):A14155A144 2014.
352
353
[3] Kim Batselier. The trouble with tensor ring decompositions. arXiv preprint arXiv: 181v:1811.0088 2018.
355
[4] James Bean. Genetic algorithms and random keys for sequencing and optimization. ORSA journal on computing, 6(2):154-160, 1994.
357
[5] Lowell W Beineke, Robin J Wilson, Peter J Cameron, al. Topics in algebraic graph theory, volume 102. Cambridge University Press, 2004.
358
[6] Johann A Bengua, Ho N Phien, Hoang Duong Tuan, and Minh N Do. Efficient tensor completion for color image and video recovery: Low-rank tensor train. IEEE Transactions on Image Processing, 26(5):246622479 2017.
360
382
[7] Yunfeng Cai and Ping Li. Tensor completion via tensor networks with a tucker wrapper. arXiv preprint arXiv: 15819, 2020.
363
[8] Yunfeng Cai and Ping Li. A blind block term decomposition of high order tensors. 2021.
365
99
Zhiyu Cheng, Baopu Li, Yanwen Fan, and Yingze Bao. A novel rank selection scheme in tensor ring decomposition based on reinforcement learning for deep neural networks. In ICASSP 2020- 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP),
386
387
388
pages 3292-3296. IEEE, 2020.
[10] Andrzej Cichocki, Anh-Huy Phan, Qibin Zhao, Namgil Lee, Ivan Oseledets, Masashi Sugiyama, Danilo P Mandic, et al. Tensor networks for dimensionality reduction and large-scale opti- mization: Part 2 applications and future perspectives. Foundations and Trends@ in Machine Learning, 9(6)4311-65 1613, 2017.
370
372
373
[1]] Lukasz Cincio, Jacek Dziarmaga, and Marek M Rams. Multiscale entanglement renormalization ansatz in two dimensions: quantum ising model. Physical Review Letters, 100(24):240033, 2008.
374
375
376
[12]
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017.
377
[13] Antonio Falcó, Wolfgang Hackbusch Nouy, et al. Geometry of tree-based tensor formats in tensor banach spaces. arXiv preprint arXiv:201 1.08466, 2020.
[14] Gary William Flake and Steve Lawrence. Efficient regression training with smo. Machine Learning, 46(1):271-290, 2002.
380
[15] Cécile Haberstich, Anthony Nouy, and Guillaume Perrin. Active learning of tree tensor networks using optimal least-squares. arXiv preprint arXiv:2104.1344 13436, 2021.
382
383
166] Wolfgang Hackbusch and Stefan Kühn, A new scheme for the tensor representation. Journal of Fourier analysis and applications, (565):706-22,, 2009.
385
Meraj Hashemizadeh, Michelle Liu, Jacob Miller, and Guillaume Rabusseau. Adaptive tensor learning with tensor networks. arXiv preprint arXiv:2008.0544 2020.
386
[18] Cole Hawkins and Zheng Zhang. Bayesian tensorized neural networks with automatic rank selection. arXiv preprint arXiv: 10478, 2019.
388
[19] Kohei Hayashi, Taiki Yamaguchi, Yohei Sugawara, and Shin-ichi Maeda. Exploring unexplored tensor network decompositions for convolutional neural networks. In Advances in Neural Information Processing Systems, pages 5553-5563, 2019.
390
10

---

382
[20] Pavel Izmailov, Alexander Novikov, and Dmitry Kropotov. Scalable gaussian processes with billions of inducing inputs via tensor train decomposition. In International Conference on Artificial Intelligence and Statistics, pages 726-735. PMLR, 2018.
393
[21]
Maxim Kodryan, Dmitry Kropotov, and Dmitry Vetrov. Mars: Masked automatic ranks selection tensor decompositions. arXiv preprint arXiv:2006. 10859, 2020.
396
397
[22] I Krasikov, A Lev, and BD Thatte. Upper bounds on the automorphism group of a graph. Discrete Math., 256(math. CO/0609455):499 493, 2006.
[23] Joseph M Landsberg. Yang Qi, and Ke Ye. On the geometry of tensor network states. arXiv preprint arXiv: /05,4449, 2011.
400
[24] Jose Latorre. Image compression and entanglement. arXiv preprint quant-ph/0510031,, 2005.
402
[25] Chao Li and Zhun Sun. Evolutionary topology search for tensor network decomposition. In Proceedings of the 37th International Conference on Machine Learning (ICML), 2020.
403
404
[26] Nannan Li, Yu Pan, Yaran Chen, Zixiang Ding, Dongbin Zhao, and Zenglin Xu. Heuristic rank selection with progressively searching tensor ring network. Complex & Intelligent Systems, pages 1-15, 2021.
406
407
[27] Zhen Long, Ce Zhu, Jiani Liu, and Yipeng Liu. Bayesian low rank tensor ring model for image completion. arXiv preprint w:xiv:200.00105. 2020.
[88]
Oscar Mickelin and Sertac Karaman. On algorithms for and computing with the tensor ring decomposition. Numerical Linear Algebra with Applications, 27(3)) 2020.
410
411
[29] Román Orús. A practical introduction to tensor networks: Matrix product states and projected entangled pair states, Annals of Physics, 349:1177-15, 2014.
412
413
[30] Ivan V Oseledets. Tensor-train decomposition. SIAM Journal on Scientific Computing.
414
33(5):2295-23111 2011.
[31] Panos M Pardalos and Jue Xue. The maximum clique problem. Journal of global Optimization, 4(3):301-328, 1994.
416
417
[32] Karl Pearson. Historical note on the origin of the normal curve of errors. Biometrika, pages 402-404, 1924.
419
[33] Justin Reyes and Miles Stoudenmire. A multi-scale tensor network architecture for classification and regression. arXiv preprint arXiv:2001.08288 2020.
420
421
[34] Farnaz Sedighin, Andrzej Cichocki, and Anh-Huy Phan. Adaptive rank selection for tensor ring decomposition. IEEE Journal of Selected Topics in Signal Processing, 15(3):454 463, 2021. [35]
422
423
Zerui Tao and Qibin Zhao. Bayesian tensor ring decomposition for low rank tensor completion. In International Workshop on Tensor Network Representations in Machine Learning, IJCAI, 2020.
424
425
426
[36] Ledyard R Tucker. Some mathematical notes on three-mode factor analysis. Psychometrika,
3 31(3):279-33 1966.
[37] Pinar Tüfekci. Prediction of full load electrical power output of a base load operated combined cycle power plant using machine learning methods. International Journal of Electrical Power & Energy Systems, 60:12661440 2014.
429
430
431
[38] Frank Verstraete and Ignacio Cirac. Renormalization algorithms for quantum-many body systems in two and higher dimensions. arXiv preprint cond-mat/0407066, 2004.
432
433
[39]
Wenqi Wang, Vaneet Aggarwal, and Shuchin Aeron. Efficient low rank tensor ring completion. In Proceedings of the IEEE International Conference on Computer Vision, pages 3697-5705,
434
435
2017.
[40] Allan G Weber. The usc-sipi image database version 5. USC-SIPI Report, 315(1), 1997.
11

---

437
[41] Hansi Yang, Quanming Yao, and James Kwok. Tensorizing subgraph search in the supernet. arXiv preprint arXiv:2101.01078, 2021.
438
439
[42]
Ke Ye and Lek-Heng Lim. Tensor network ranks. arXiv preprint arXiv:1801.02660 2019.
440
[43] Tatsuya Yokota, Qibin Zhao, and Andrzej Cichocki. Smooth parafac decomposition for tensor completion. IEEE Transactions Signal Processing, 64(20):5423- 5436, 2016.
[44] Longhao Yuan, Chao Li, Danilo Mandic, Jianting Cao, and Qibin Zhao. Tensor ring decomposi- tion with rank minimization on latent space: An efficient approach for tensor completion. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 9151-9158, 2019.
443
445
448
[45] Longhao Yuan, Qibin Zhao, Lihua Gui, and Jianting Cao. High-order tensor completion via gradient-based optimization under tensor train format. Signal Processing: Image Communica- lion, 73:53-61, 61, 2019.
447
[46] Qibin Zhao, Liqing Zhang. and Andrzej Cichocki. Bayesian ep factorization of incomplete tensors with automatic rank determination. IEEE transactions on pattern analysis and machine intelligence, 3709):1551-176,, 2015.
450
[47] Qibin Zhao, Guoxu Zhou, Shengli Xie, Liqing Zhang, and Andrzej Cichocki. Tensor ring 2016.
453
decomposition. arXiv preprint
454
[48] Yu-Bang Zheng, Ting-Zhu Huang, Xi-Le Zhao, Qibin Zhao, and Tai-Xiang Jiang, Fully- connected tensor network decomposition and its application higher-order tensor completion.
455
456
2021.
12

---

Checklist
457
458
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
460
contributions and scope? [Yes]
461
(b) Did you descrihe the limitations of your work? [Yes] See Section S
462
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
464
465
2. If you are including theoretical results...
466
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
467
(b) Did you include complete proofs of all theoretical results? [Yes] All proofs are given in the supplementary material.
468
469
3. If you ran experiments..
470
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or as a URL)? [Yes] Codes with illustrative experiments is uploaded
472
473
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See the supplementary material.
474
475
(c) Did you report error bars (e-g.. with respect the random seed after running experi- ments multiple times)? [No] Yet we show the results for each sample such as images or synthetic data in the supplementary material. The error bars can be estimated from those results.
477
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See the supplementary material.
480
481
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
482
(a) If your work uses existing assets, did you eite the creators? [N/A]
485
(b) Did you mention the license of the assets? [N/A]
484
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
486
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A]
487
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
489
490
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
492
493
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
494
495
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "_kTYoH0ItKe", "reviewer": "Reviewer_U3Vg", "summary": "This paper considers the problem of selecting ranks and permutations of a given tensor network structure. It analyzes the size and some properties of the resulting search space, proposes a simple representation, plugs it into a genetic algorithm, and reports some experimental results.\n", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Generally, the ideas put forward in this paper are very simple (which is good), but they are presented poorly (1,2). The novelty and amount of insight of this paper is low (2,3,4); it basically boils down to a small modification of [25]. Nevertheless, the experimental study shows promising results, but it's too \"proof-of-concept\" to be really insightful (5, acknowledged by the authors themselves). For these reasons, I do not recommend to accept the paper, even though it shows a promising direction.\n\n1. The presentation of this paper lacks precision and clarity from time to time. For example, Def 1 is imprecise and consequently confusing,  Prop 6 refers to \"a probability being approximately larger\", and Prop 9 to a \"constant far less than |V|\". Clear, self-contained definitions would make this paper more accessible. That being said, the main points become clear even though I am not an expert in this particular area.\n\n2. The key idea of this paper is to start with a template of a tensor network and then search the space of possible instantiations (rank to each edge + permutation of vertexes). When phrased like this, many of the points raised in Sec. 3 are straighforward, if not trivial (e.g., Lemma 5+7) or unnecessarily (Prop 6). The authors complicate things here by arguing around the adjacency matrix of the template instead of directly the template graph. Since also the representation of a tensor network constraint in terms of a graph is not novel, I did not find this discussion particularly insightful or novel.\n\n3. Similar remarks apply to the encoding scheme of section 4. It's straightforward; the key idea is to enumerate the edge labels in a fixed order and to represent the permutation via order statistics of real numbers associated to each vertex (\"random-key trick\"). The method of [25] is then employed. Overall, this appears to be a small (but admittedly beneficial) improvement over [25].\n\n4. What I find surprising, if not disappointing, is that the authors argue about the need to account for symmetries in the first part of the paper, but then ignore symmetries completely in the second part and their ultimate method. Here they are \"hiding\" behind the O-notation of Prop 9, which (i) may have large constants that are very relevant in practice and (ii) only apply to templates in which the degree is bounded by a constant.\n\n5. The experimental study suggests that the methods produce better results than prior works in term of compression ratio. The experimental setup, however, is not convincing. The authors list a large number of hyperparameter choices in the appendix, but do not state how these hyperparameters have been been selected. The choice of synthetic datasets is not well argued for and they appear small (i.e., dim 3 per mode).\n\nUPDATE AFTER AUTHOR FEEDBACK\n\nI've read the response of the authors. My overall impression remains the unaffected. As mentioned in the original review, I do think that this paper has potential. All of the concerns raised in my original review remain, however.\n\nSome comments on the response:\n\nThe analysis is not very deep and can be presented in simpler terms using the TN template. In fact, the presentation in terms of an adjacency matrix does not add anything other than making the discussion more technical. Note that that's different for [25] because there the graph structure itself is encoded via its adjacency matrix during TN search. But in this submission, the structure is fixed up to permutations and ranks.\n\nProp. 9, which the authors cite in their response, is not clear as stated. It's of the form \"x>=O(...)\", which is confusing at best: \">=\" denotes a lower bound, but O(...) an upper bound. Be that as it may, it would be more helpful if the authors provide bounds that explicitly involve the maximum degree.\n\nExaggerating somewhat, the authors seem to argue that (i) symmetries are very important so that prior methods don't work and (ii) symmetries can be ignored in their method. I do understand what the authors actually want to say, but it's not clearly argued in the write-up.\n\nSimilar remarks as for the analysis apply to the actual algorithm. If expressed in terms of graphs, it boils down to search on rank per edge and position per vertex. The use of the random-key trick for the latter is well-known, as the authors acknowledge. There is nothing wrong with this method, but there is also not much novelty and it does ignore all symmetries.\n\nIt's not clear what the authors mean by \"applied the same genetic operators as [25]\". Clearly, [25] has different operators; e.g., it changes the graph structure.\n\nDecent hyperparameter search and a clear description of the search process across all methods is key for reproducibility and fairness. Likewise, the experimental setup needs to be argued for clearly.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Ok", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "NiQGTQI4rJ5", "reviewer": "Reviewer_4rtP", "summary": "\tThis 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.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "To solve the searching problems on these structures, this paper has provided the following contributions. \n\n1. Formulating this graph constrained TNs is reasonable since that this formulation incorporating plenty of tensor formats and a wide searching space implies a higher probability to find a suitable structure.\n2. The analysis on the universal bound is interesting, which instructs the process of transferring an irregular space to a regular space. \n3. This paper presents a coding method named as random-key to transform the irregular space. And experiments show that it works well.\n4. This paper is technically sound.\n\nHowever, there still exist some issues to be addressed.\n\n1. In Line 59, $\\mathcal{X}_{i_1, i_2, \\dots, i_N}$  denotes an element rather than a tensor.\n2. In Definition 1, for easy following, it is better to change the suffix $R$ of  $\\mathbb{A}$  to ${R+1}$\n for consistent with $\\mathbb{Z}_{R+1}$.\n3. Experiments seem mostly conducted on common tensor formats like the tensor ring and the tensor train. It will be better to dicuss some special format like the odd tensor in [1].\n4. Although I can find many more experiments in the supplementary material, it suggests adding some more SOTA methods in image completion for comparison for  completeness.\n5. To be more clear, it is helpful to add more details of random-key.\n6. There are some writing typos:\n   (a) In Line 155, \"it\" -> \"It\";\n   (b) In Line 190, \"say\" -> \"says\";\n   (b) etc..\n\nOverall, for the novel idea and interesting method, I prefer to give acceptance to this paper.\n\n[1] Li, Chao, and Zhun Sun. \"Evolutionary topology search for tensor network decomposition.\" International Conference on Machine Learning. PMLR, 2020.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "1je8pLd2Ecb", "reviewer": "Reviewer_hLLS", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "General architecture search for tensor networks has been the topic of several recent works (cited in the paper), and the present work singles out a special case of this problem which appears to be previously unexplored. Namely, the case where we have a given TN architecture of interest (e.g. tensor train, tensor tree, Tucker, etc.), and would like to find an optimal means of matching this architecture to an unknown data-dependent tensor. This question occurs frequently in applications of TNs to real-world problems, and previous approaches typically employ either physically-motivated heuristics, or else more general architecture search over arbitrary graphs. One of the main contributions of this paper is therefore the identification of this new intermediate regime, where graphical structures can be specified, and all other TN hyperparameters determined by algorithmic search. I suspect this special case will be of interest to TN practitioners.\n\nThe results provided by the authors are somewhat eclectic and hard to follow in places, and I personally found it difficult to understand the connection between the main theoretical results (Proposition 6 and Lemma 7, along with Propositions 8 and 9) and the proposed search method in Section 4. While some justification of the connection between these two families of results is given in the manuscript (and I am satisfied that they are indeed related), it would be helpful to readers to spend more time motivating the new search method, which is currently introduced rather abruptly. Crucially, it would be very helpful to give a more detailed introduction to the random key trick employed, which is currently described in a single paragraph, with much of the explanatory work deferred to a reference on genetic algorithms. More generally, I would also encourage the authors to give a quick overview of the genetic search algorithm on which the current architecture search method is built [Chao Li and Zhun Sun, 2020], since it is relevant for understand the experiments.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately address the limitations of their work in Section 5, and don't address potential negative societal impacts, owing to the technical nature of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "0YMiO4U65z5", "reviewer": "Reviewer_mrqp", "summary": "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.\nTNR 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.\nSome 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. \n\n", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The topic is of significance and interest. A new topological constraint problem is formulated. However, the clarity of the paper is one concern of mine. The paper could be much improved its clarity and make it more self-contained.\nDetailed comments:\n1. ln 64, C_i,k = A_i,j B_j,k -> Should there be a sum on the RHS?\n2. ln 76, \"with the ranks upper-bounded by R\" -> The rank is not well-defined in the Def 1. It confuses me whether the rank is the deg(v) or the rank(unfold(X)).\n3. ln 77, internal cores are not defined.\n4. ln 83, \"corresponds\" -> \"correspond\".\n5. ln 84, \"...will show the matrix form...\" -> \"...will show that the matrix form\".\n6. Please try to make the definitions clearer as [25] did.\n7. ln 92, \"...with N vertices and a edge...\" -> \"...an edge...\"\n8. ln 132, Omega_G_0 and r are defined but not constructed explicitly. Please try to clarify how to obtain r from the graph G_0 and the detailed definition of r, and please explain what the rank vector of dimension |E_0| means. How is P computed?\n9. In the Supplemental Materials, what is the definition of H_0^u in the proof, and what is the definition of Phi^{-1} and Phi? And where is the Omega_G_0 in the proof of Lemma 5? Please make sure that the proof is completed and correct.\n10. ln 141, what does that mean by \"relatively sparse\"? please be specific. And what does it mean by \"not closed with a probability\"? Should it be a deterministic property when we talk about a set's closeness?\n11. ln 157, \"TNs with symmetric topologies like TR and the complete TN are expected to own a smaller size of H_G0,R\" -> I feel it is not convincing to me since CTN may increase |E_0| in Eq (6) shown in Lemma 7, which could significantly increase the size of H. \n12. ln 190, what does it mean by \"nearly unique\"?\n13. ln 240, \"the tensor order covers {4,6,8}\" -> Do the authors mean tensors of order 4, 6, 8 are generated?\n14. In many real-world cases, the underlying topology is more complicated than TR or TT, and limited prior knowledge is known, so I am curious if the proposed method can generalize well?\n15. What is the coding format of the image completion experiments?\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I identified no potential negative societal impact of their work. The limitations are well discussed in Section 5.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "72"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The problem tackled by this paper, searching for graph constrained tensor network structures, is relevant and potentially impactful, and the core ideas presented in the paper are potentially useful for the intersection of the tensor network and ML communities. However, through the discussion, the reviewers overall agreed that the paper is not yet ready for publication and that a substantial revision of the submission is needed before being published to make sure that the paper obtains the potential impact it deserves. The most important points that were raised in the reviews and the discussion are the following:

- The theoretical analysis seems overall disconnected from the practical/algorithmic contribution of the paper. While it is true that, for an expert in TN methods for ML, the theoretical analysis makes sense and is relevant, these results are presented in a somehow convoluted way that is likely to be an obstacle for the interested readers to benefit from the paper. I recommend the authors to thoroughly go through the reviews and to try to clarify the relevance of the theoretical analysis for the contributions of the paper. I believe revising the paper taking into account the reviews will make the paper more impactful once it is published.

- The novelty of the paper needs to be better argued and demonstrated.

- Several reviewers mentioned that the mathematical exposition needs to be more rigorous in several places. 

In summary, the paper is not yet ready for publication mainly due to lack of rigor in the mathematical exposition, a lack of clarity on the connection between the theoretical results and the proposed algorithm, and the fact that the method could be presented in a simpler manner (which however could potentially question the novelty of the proposed approach, wrt [25] in particular). That being said, the problem considered by the authors is interesting and, if reworked and better formalized, the theoretical results could be relevant as well. 
Decision: Reject