Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper discusses a sketching method for tensor network (TN) structured input data. Unlike previous methods mainly focusing on specific TN structures of the input data, this paper considers more general structures. To alleviate the exponentially large sketching size, the authors impose TN structure on the coefficients. Theoretical guarantees are provided. Finally, the authors also present two applications of the proposed model, including CP-ALS and TT-rounding.

For empirical results, they conducted several synthetic data analyses to justify the theoretical results.

strengths_and_weaknesses: Strengths

1. While previous related works focusing on specific input structure, this work studies a sketching algorithm for general TN structures. This may be useful for more applications. It also improves studies in such fields.

2. The authors also present some theoretical results, which may be beneficial to future work.

3. Based on the proposed algorithms, the authors improve the CP-ALS and TT-rounding algorithms, which are two popular tensor decomposition algorithms used in many applications. So the proposed model may have impacts on potential applications.


Weaknesses

1. The authors conducted several synthetic analyses to justify the theoretical results. However, I think it’s better to also include some real data experiments to show the usefulness of the proposed model.

2. The authors presented two applications of the proposed algorithm, i.e., CP-ALS and TT-rounding. However, they did not conduct experiments on these two applications. I think it is very interesting to show how these algorithms perform in experiments.

3. In this work, the authors aim to study sketching for input data of general TN structure. However, in the experiments, they only used TT and Kronecker structures, both of which are very simple TN structures. Did the authors conduct experiments on more general TNs?

questions: See above.
limitations: The authors addressed some limitations. I think one limitation is that they should show some real applications to show the usefulness of the proposed model.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper discussed the tensor network embedding. Specially, they focus on the problem to derive a sequence of sketching matrices. They generalized the embedding accuracy in Theorem 3.1, w.r.t the sketch size of the matrix. They later proposed an efficient sketching algorithm which enjoyed batter per-iteration cost than previous methods.  
strengths_and_weaknesses: Strengths:
1. The theoretical analysis is strong. Especially theorem 3.1 which discussed the accuracy of the tensor network embedding.
2. The proposed sketching method has less computational cost per iteration.
3. This framework showed broad application on different tensor decompositions like CP decomposition and tensor train embedding.

Weaknesses:
1. The theoretical part of this paper discussed a very general tensor network embedding rooted in the hypergraph presentation. But in the later part, they barely discussed it. As for me, such arrangement is quite confusing and disconnected. 
2. This paper is more focused on the sketching size. Following the hypergraph setting, the graph structure is very important to the embedding. Currently the author assumes the graph structure is given, but most of times, the structure is unknown. The paper did not further discuss that.
3. The computational cost is efficient on per-iteration level. It still relies on exhaustive search. The overall computational cost can not be effectively measured.
4. Experimental part is locking. The author only conducted general comparison in algorithm 1, but did not show experimental results with baseline methods.
questions: Though most questions are in weakness. I do curious that, Is there a good way to assume the hypergraph structure of the tensor network embedding?


limitations: N/A
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper investigated an efficient sketching method for embedding the tensor with tensor network (TN) structures into lower-dimensional spaces. Compared with the existing works, the main contribution of this paper includes the points as follows:

- The authors established a systematic framework regarding how to sketch a TN with a lower-dimensional representation.
- The authors carefully discussed the computational cost of the proposed method with necessary proofs for demonstrating the efficiency.
- Two potential applications are introduced: a) ALS-CP algorithm; and b) tensor train rounding algorithm.
strengths_and_weaknesses: **Strengths:**

- (originality) This work reveals the potential advantage regarding of how the inherent TN structure can be leveraged to improve the sketching performance.
- (originality) The joint discussion of the effective sketching with computational cost (modeled by the contraction tree) is very interesting.
- (quality) The theoretical discussion of the paper on complexity analysis is remarkable.

**Weaknesses:**

- (clarity) The paper is relatively well written, but the introduction of the algorithm details (sec. 4) is very hard to follow, even though I carefully go through the appendix. For example, the meaning of the letter U in Eq. (4.2) is not clear. I finally found its definition in the appendix but it should be well defined in the manuscript.
- (significance) A fundamental assumption of the work — the TN ranks should be smaller than the mode dimensions — seems not reasonable in practice. It might be true for some tensor decomposition models such as CP and Tucker for lower-order tensors. In the sense of TN, one typically has to be faced in practice with lower mode dimension (only 2 or 3) but higher ranks (e.g., 100). In this case (also acknowledged by the authors in the paper), the improvement by the proposed method becomes not so significant. The numerical results in the paper also verify this point.
questions: 1. As shown in Figure 4, the embedding network is a  binary tree-structured, of which the vertices are repeatedly represented by a small TN. How do you determine the structure (e.g., bond dimension, network topology) for these small TNs? What happens if another topology is applied as an alternative?
2. Could you give more interpretation, such as an understandable example, for Definition 1, the constrained contraction tree?
3. It would be appreciated if the authors can give more interpretation about the Defs for $D(e_1)$, $\mathcal{S,I}$ given in lines 241-250.
4. Regrading the computational cost, suppose the data TN itself is contractible, meaning that the contraction cost is polynomial to the tensor dimension, I am wondering if the whole sketching of the proposed method is contractible as well? In other words, is the contractibility preserved under sketching?
5. What is the difference between #P-complete and #P-hard? Are they equivalent? 
6. In line 398, why are the entries of the tensor drawn from the uniform distribution, rather than Gaussian?
7. If possible, could you evaluate the sketching dimension (or compression ratio) numerically with varying the parameter $\epsilon$ in a smaller range? Although the authors mentioned that the setting of $\epsilon$ to be 0.1-0.2 might be good, I think it depends on the specific task.
limitations: The main limitation of this work is that the proposed method seems only to work superiorly when the data TN is very low-rank. It might not be suitable for most tasks in practice.
review_title: null

Meta-review: metareview: Summary: 

The major strength is that the sketch size is polynomial in the number of modes for tensor train. This was not known in previous work, for example in the paper by Rakhshan and Rabusseau https://arxiv.org/abs/2003.05101 which is reference 38 and gets a sketch size which is exponential in the number of modes. There is concurrent work that also gets this here: https://arxiv.org/abs/2207.07417

Theorem 4.3 seems like it could be of independent interest. It shows that under reasonable assumptions, assuming the contraction order of the data tensor is fixed, if the embedding is a tree, then this gets the optimal running time - more complex embeddings are not needed (even if the data tensor has cycles). Section 4 is focused on giving an algorithm such that, given a data tensor and an embedding, and a fixed contraction order for the data tensor, applies the embedding to the data tensor with the smallest possible asymptotic running time. Not sure if previous work has studied this question, however.

One weakness is that the works doesn’t seem to compare to previous work related to Section 4, or running time for subspace embeddings for tensor networks. Their CP decomposition algorithm is also incomparable to the other CP decomposition algorithms they mention, since their per-iteration running time for ALS has a 1/eps^5 term. Perhaps if s (the size of each dimension of the tensor) is much bigger than N (the number of modes) or R (the rank), then the second term in the running time should dominate, meaning that the algorithm in this paper would still be significantly better than Recursive LSS (by a factor of NR as they mention in page 8), so this might not be a significant weakness.

Evaluation: 

Based on the reviews and my understanding, I think this meets the bar for NeurIPS. The sketch size for tensor train and the application to CP seem useful, and tensor train rounding seems to be a strong motivation. The significance of Section 4 is not completely clear, but the other results seem to be enough by themselves.

confidence: Less certain
Decision: Accept