Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: Summary: The paper calls into question the significance of previous results on Self-Expressive Deep Subspace Clustering (SEDSC) models, which are touted as successful extensions of the linear subspace clustering (using the self-expressive property) to non-linear data structures. The authors present a set of theoretical results that indicate that the standard formulations of  SEDSC are generally ill-posed. Even with added regularizations, it is shown that such formulations could very well yield trivial geometries that are not conducive to successful subspace clustering. 

Comments: 
Although I have not fully checked the proof of the theoretical results, I believe this is a solid piece of work as it sheds light on shortcomings of SEDSC formulations using a rigorous theoretical approach. The authors verify their arguments using a good set of experiments. The findings also suggest that much of the claimed success of such models can in fact be attributed to post-processing of the encodings rather than the validity of the model. 

- The paper has a limited scope as it raises concerns about an existing deep Subspace Clustering algorithm. I am not sure whether this algorithm is widely adopted and how significant it is -- the paper does also look at a class of similar formulations based on different regularizations. As such, I feel the paper addresses a somewhat limited audience and the impact of the work appears somewhat limited.

- Other than the limited scope, I do not see major weaknesses in this work, and I think the authors did a good job explaining the main ideas. 

- The paper is hard to read for people who have not worked in closely related areas. 

- The findings of this question beg the question -- which the paper does not attempt to answer -- as to whether there exist some other forms of regularizations for such models that would promote geometries of the embeddings that are conducive to successful clustering. 

I believe this is a good paper worthy of being considered. 
review_title: A review for critique of SEDSC

final_score: rating: 7: Good paper, accept
review_content: This paper critiques the commonly-used self-expressive cost function used to learn embeddings for deep subspace clustering. The authors point out that the empirical improvements obtained by deep self-expressive subspace clustering may be artifacts of post processing on the learned affinity matrix. They then theoretically characterize the optimal solutions to a variety of cost functions/normalization procedures used within the deep subspace clustering literature, showing that these encourage points to be mapped to a singleton set up to a sign change.

The theoretical contributions of this paper are significant, and the critique of deep self-expressive subspace clustering is timely and important. A survey of "shallow" subspace clustering methods shows that the alleged performance improvements obtained by deep subspace clustering typically amount to parameter tuning or post processing, as shallow methods often perform at least as well when properly tuned. The paper provides solid evidence that researchers should think more deeply when designing loss functions for unsupervised learning with neural networks. Empirical results are included that verify the theoretical contributions of this work.
review_title: Valid points to consider when designing algorithms for deep self-expressive subspace clustering.

final_score: rating: 7: Good paper, accept
review_content: This paper studies the flaws associated with extending subspace clustering methods to the nonlinear manifolds scenario. In particular, the authors demonstrate that the optimization problem solved due to the extension can be ill-posed and thus lead to solutions which are degenerate/trivial in nature. The paper also showed that the performance benefits often associated with the Self-Expressive Deep Subspace Clustering techniques are potentially due to post-processing steps and other factors rather than due to the efficacy of these methods themselves.

Overall the outline of the paper is good and I found the discussed problem informative. Few aspects were unclear to me (refer below). 

1) In section 2, the authors discuss positively-homogeneous functions i.e. (leaky) Rectifier Linear Units and how it effects the statement in Proposition 1. I would like to understand how Proposition 1 relates to other activation functions i.e. the Hyperbolic Tangent (tanh) and Sigmoid functions for example. In general, given the latter activation functions are not positively-homogeneous and have disparate saturation/non-saturation regions, can we extend the analysis to these activation functions and make the theoretical parts of the paper more generic ? 

2) In section 2.1, the authors talk about how Auto-encoders do not necessarily impose significant constraints on the geometric alignment of points. Are the authors aware of techniques like TopoAE and other state-of-the-art VAE/GAN and generative model variants which use some form of regularization to allow for topology modeling etc. and/or can produce results which achieve the above ? Did the authors consider this ?

3) How do the authors quantify which encoder-decoder architectures are "reasonably expressive" ? Does any constraint as part of the objective function hamper this or are they referring to more specific constraints ?

4) In sections 2.1 - 2.2, the authors mention that to remove trivial solutions the magnitude of the representations should be greater than some minimum value. What is this minimum value and how can we compute it efficiently ?

5) In section 2.2, the authors briefly talk about how optimal solutions to the optimization problem may exist which have zero mean. How often do the computed optimum values fall in this category or in general are degenerate or trivial ? My point is existence of degenerate solutions need not mean that our optimization process will actually end up with these degenerate/trivial solutions. We typically can add constraints (which act like a prior and factor in the objective) and thus push our final solution away from degenerate/trivial solutions. 

I felt that the paper points out an important issue but if the authors could provide a general solution which helps ameliorate the issue (some general directions or even providing rudimentary results for one of the these directions) could have made the their contribution much more stronger. Overall I like the paper and the arguments made even though I have some inhibitions with regards to the scope of the contribution given the problem addressed is so specific.
review_title: Review

final_score: rating: 7: Good paper, accept
review_content: Pros:
1)	Authors theoretically studied a class of self-expression deep subspace clustering methods and found that the optimization problem is typically ill-posed.
2)	Various normalization approaches are studied, including dataset and batch/channel normalization, and instance normalization. However, even with these normalizations, the optimal embedded data geometry is still trivial in various ways.
3)	Authors conducted experiments on real and synthetic data to further verify the theoretical conclusions. 

Cons:
1)	Although authors uncovered the ill-posed issue in existing SEDSC methods, it is more interesting to see how the ill-posed issue can be resolved or alleviated. A proper working solution can further improve the quality of this paper.
2)	The theoretical results seem mainly focusing on (3) with autoencoder regularization. Authors might want to specify the extension of the results to (2) in a more general form. Similarly, the discussion of various SEDSC methods cited in Section 1.1 in terms of the discovered results is important.
3)	Authors mentioned the solutions are optimal in many places of this paper. From the perspective of the nonlinear optimization problems, it is not proper to say “optimal solutions”.  

I change my rating after looking at authors response. 
review_title: Authors theoretically studied a class of self-expressive deep subspace clustering (SEDSC) methods, and found that autoencoder regularization formulation is typically ill-posed and the optimal embedding is still trivial after normalization is applied. 

Meta-review: The authors carefully study a class of unsupervised learning models called self-expressive deep subspace clustering (SEDSC) models,  which involve clustering data arising from mixtures of complex nonlinear manifolds. The main contribution is to show that the SEDSC formulation itself suffers from fundamental degeneracies, and that the experimental gains reported in the literature may be due to ad-hoc preprocessing.

The contributions are compelling, and all reviewers appreciated the paper. Despite the paper being of somewhat narrow focus, my belief is that negative results of this nature are useful and timely. I recommend an accept.
Decision: Accept (Poster)