Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.
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. 


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.
Detailed comments:
1. ln 64, C_i,k = A_i,j B_j,k -> Should there be a sum on the RHS?
2. 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)).
3. ln 77, internal cores are not defined.
4. ln 83, "corresponds" -> "correspond".
5. ln 84, "...will show the matrix form..." -> "...will show that the matrix form".
6. Please try to make the definitions clearer as [25] did.
7. ln 92, "...with N vertices and a edge..." -> "...an edge..."
8. 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?
9. 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.
10. 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?
11. 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. 
12. ln 190, what does it mean by "nearly unique"?
13. ln 240, "the tensor order covers {4,6,8}" -> Do the authors mean tensors of order 4, 6, 8 are generated?
14. 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?
15. What is the coding format of the image completion experiments?


limitations_and_societal_impact: I identified no potential negative societal impact of their work. The limitations are well discussed in Section 5.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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.

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.

1. 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.

2. 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.

3. 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].

4. 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.

5. 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).

UPDATE AFTER AUTHOR FEEDBACK

I'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.

Some comments on the response:

The 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.

Prop. 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.

Exaggerating 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.

Similar 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.

It'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.

Decent 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.

limitations_and_societal_impact: Ok
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: 	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.
main_review: To solve the searching problems on these structures, this paper has provided the following contributions. 

1. 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.
2. The analysis on the universal bound is interesting, which instructs the process of transferring an irregular space to a regular space. 
3. This paper presents a coding method named as random-key to transform the irregular space. And experiments show that it works well.
4. This paper is technically sound.

However, there still exist some issues to be addressed.

1. In Line 59, $\mathcal{X}_{i_1, i_2, \dots, i_N}$  denotes an element rather than a tensor.
2. In Definition 1, for easy following, it is better to change the suffix $R$ of  $\mathbb{A}$  to ${R+1}$
 for consistent with $\mathbb{Z}_{R+1}$.
3. 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].
4. 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.
5. To be more clear, it is helpful to add more details of random-key.
6. There are some writing typos:
   (a) In Line 155, "it" -> "It";
   (b) In Line 190, "say" -> "says";
   (b) etc..

Overall, for the novel idea and interesting method, I prefer to give acceptance to this paper.

[1] Li, Chao, and Zhun Sun. "Evolutionary topology search for tensor network decomposition." International Conference on Machine Learning. PMLR, 2020.
limitations_and_societal_impact: NA
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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.

The 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.
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_title: null

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