Partition First, Embed Later: Laplacian-Based Feature Partitioning for Refined Embedding and Visualization of High-Dimensional Data

Authors: Erez Peterfreund, Ofir Lindenbaum, Yuval Kluger, Boris Landa
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords: data visualization, dimensionality reduction, manifold learning, data embedding, feature partitioning

Abstract:
The utility of embedding and visualization techniques for high-dimensional data in exploratory analysis is well-established. However, when the data embody intricate structures governed by multiple latent variables, standard techniques may distort or even mask part of the phenomenon under study. This paper explores scenarios where the observed features can be partitioned into mutually exclusive subsets, each capturing a different smooth substructure. In such cases, visualizing the data based on each feature partition can better characterize the underlying processes and structures in the data, leading to improved interpretability. To partition the features, we propose solving an optimization problem that promotes a graph Laplacian-based smoothness in each partition, thus prioritizing partitions with simpler geometric structures. Our approach generalizes traditional embedding and visualization techniques such as t-distributed Stochastic Neighbor Embedding and Diffusion Maps, allowing them to learn multiple embeddings simultaneously. We establish that if several independent or partially dependent manifolds are embedded in distinct feature subsets in high-dimensional space, then our framework can reliably identify the correct subsets with theoretical guarantees. Finally, we demonstrate the effectiveness of our approach in extracting multiple low-dimensional structures and partially independent processes from both simulated and real data.

Decision: reject
Reviewer scores: 5, 6, 8, 5

Reviews and discussion:
<thread>
creation date:
1729770982470

thread_type:
official_review

<thread_object>
creator: reviewer_hqpj

<content>
summary:
This paper proposes a technique for separating the data features into several disjoint sets of features (dimensions) and to run tSNE on each of these independently. By doing this, their method learns multiple embeddings simultaneously which can more accurately represent the structure of the features. Much of the paper is devoted to deriving the corresponding optimization problem.

strengths:
I have changed the score from a 3 to a 5

---------------------

This paper sets out to handle an interesting problem: that the embedding of datasets can be performed better if we decompose the dataset into disjoint groups of features. This is a fundamentally interesting problem that lends itself to robust analysis and principled insights. Within this, I really appreciate the development of a dataset which explicitly showcases the objective that the authors are seeking to optimize.

I also applaud the paper's theoretical approach to the topic. Many works in modern dimensionality reduction simply state an objective and optimize it and I find this paper's theoretical derivations to be the exact kind of work that the field is in need of right now.

Furthermore, the paper is aesthetically pleasing -- the images in particular are well-made.

weaknesses:
I believe this paper has three major weaknesses. Although I give a lengthy description of these weaknesses, I do not mean it as a condemnation of the paper -- simply constructive criticism. I believe that if these issues are addressed then this would be a strong paper.

## Presentation and Theoretical Rigor

The theoretical results in this paper are messy. For context, I am very familiar with the related work and come from a theoretical background, so my concern is not that the topic itself is difficult. Instead, many theoretical ideas are presented with little context and the proofs seem to be hand-wavy at times. I include below an inexhaustive list of examples:

 - There are missing definitions. For example, the Laplace-Beltrami operator in equation 32 is never defined and it took me a while to recognize that this is what it represented. Similarly, page 22 references "Slater's conditions for strong duality" which are, to my knowledge, not introduced elsewhere. The same proof also mentions the KKT conditions. What are these?
 - The proof of Proposition 1 references the proof of Proposition 3, which appears 5 pages later in the appendix and one page later in the main body. In an ideal world, theoretical derivations should start at first principles and build up to things in a linear order without requiring one to jump around. However, more worryingly, the proof is simply "[the proof] can be derived from Proposition 3 by... " . But the proof of Proposition 3 simply says "this can be obtained by combining Lemmas 3 and 4." On its surface, it is not clear to me how this should be accomplished (and I've spent 5+ hours now trying to parse the derivations in the appendix). If Prop. 3 can be proven from these lemmas, then it should be shown how this is done. Thus, not only is the proof of Proposition 3 not clear, the proof of Proposition 1 is difficult to check by extension as well.
 - This difficulty in parsing the proofs is partially due to the fact that the lemmas in the appendix appear with no motivation or context. For example, Lemmas 1, 2, 3, and 4 all appear spontaneously and it is unclear to what end they will be used. It would be extremely helpful to have a "proof overview" as is often done in learning theory papers which describes how the lemmas come together to give the ideas.
 - Furthermore, many steps in the proofs are not explained. For example, equations 43-48 are... unclear to me. Specifically, we say equation 43 tends to equation 44 as $N \rightarrow \infty$, where the difference is that we replace the summation by an integral and multiply by $f(y)$ in the integral. This can't be true for all functions $f$, though, right? For example, let $f(y) = ||y||$. This is smooth and positive over the manifold and satisfies the conditions in the lemma statement. Then we have $$ \int_{y \in M} \exp(-||x - y||^2 / \epsilon_i) ||x - y||^2 ||y|| dy $$ in the numerator. Now let $f(y) = ||y||^{100}$. Then our numerator becomes $$ \int_{y \in M} \exp(-||x - y||^2 / \epsilon_i) ||x - y||^2 ||y||^{100} dy. $$ Clearly, these are different. So how can equation 43 tend to 44 under any $f$ if equation 44 depends on the $f$?
    - Similarly, it is unclear how we go from equation 45 to 46. How does the denominator get simplified out?
    - Lastly, there is a reference to Osher et. al between equations 47 and 48. This reference does not appear in the references of the main body and therefore I could not find the corresponding paper.
 - Furthermore, there are cases where the proofs seem to have mistakes? For example, equation 50 to equation 51 is incorrect. As I understand it, the log of a fraction has been separated into the difference of two logs and the distributive property should now be applied to this difference. However, the multiplication is only applied to one of the terms in the difference of the logs. If the distributive property is applied correctly, then the second term will also depend on $x_j$ and the derivative of the second term will not be 0. Thus, the proof is incorrect as it is currently written. Since Proposition 3 depends on Lemma 2 via Lemma 3 (and, subsequently, Proposition 1, Corollary 1, etc.), the remaining theoretical results of the paper are technically unsubstantiated as well.

## Experiments

Unfortunately, it is similarly difficult to understand what the experiments are showing and the experiments feel very incomplete to me.

 - How are the standard tSNE plots obtained in Figures 1 and 4? As described, the dataset has images which include all the pixels (not just those corresponding to a single figurine). So, to be clear, the left column of Figure 1C is the tSNE plot of *all* the pixels and the right columns are the tSNE plots of just subsets of the pixels? If so, then this took quite a while to understand as the color-coding implies that the top-left image in Figure 1C is the tSNE of the yoda figurine under some other, arbitrary partition while the bottom-left is the tSNE of the bulldog figure under the same arbitrary partition.
 - I'm confused what point Figures 5, 8 and 9 are trying to make. Is the premise that, under the partitioning approach proposed by the authors, the dataset's cyclic nature is evidenced when embedding with tSNE on partition 2? This seems poorly motivated to me. If the goal is to find cycles in the data, then I would guess that methods in topological data analysis are more effective and interpretable than partitioning + tSNE, so a comparison should be made there to point out why one should use the author's proposed method. If the point is simply that the visualization is better under partition 2 then I am unconvinced that this is the case. The tSNE embeddings based on "all genes" in figures 5 and 9 look rather good to me. What does partition 2's tSNE embedding provide which quantitatively improves over the "all genes" one? While I agree that the loop "looks" better, is this actually more representative of the input or just representative of what we would like the embedding to look like?
 - Since the authors' primary contribution is a method is for data segmentation with an application to visualization, then they have not conducted sufficient enough experiments to verify the necessity or validity of this approach. With regards to validity, it would be nice to measure against competitors. For example, they analyzed spectral clustering for the ellipsoid dataset but nowhere else. I would hypothesize that an equally valid competitor to the authors' work would be the following algorithm: Step 1: find a good partition of the images over all the data samples using spectral clustering. Step 2: apply this partition to the full dataset. Step 3: visualize each partitioned dataset using tSNE. I would be very interested to see how this performs compared to the authors' approach. Furthermore, if the authors believe that their approach outperforms my suggested competitor algorithm, then they should provide quantitative measures which emphasize this.
     - There is similarly an absent set of references to image segmentation techniques using neural networks. Would those not work for getting the partitions? They consistently outperform all laplacian based methods...
 - This paper is missing quantitative measures of the embedding quality more generally. It is difficult to say one embedding is "better" than another when there is not a quantitative evaluation of this fact.
 - Is there a reason that the authors did not use the coil-20 and coil-100 datasets? These are essentially identical to the authors' proposed figurines and standard datasets for evaluating tSNE, UMAP, and other dim. reduction approaches. Perhaps the coil dataset could help in providing quantitative comparisons of manifold preservation?

## Motivation

Some of the motivation for the technique seems artificial to me. Specifically, entire fields of related work are discarded as "inapplicable" with insufficient description/motivation.
 - On page 2 the authors state that their approach "does not require the observations in each feature partition to be clusterable". But that is required of their method, no? Problem 1 and Problem 2 explicitly define clustering objectives where each feature is placed into a disjoint partition (cluster). Thus, there is an absent set of comparisons to other clustering techniques. For example, the technique in [1] seems particularly relevant.
 - Similarly, page 2 states that subspace clustering (an entire field attempting to do the partitioning that the authors are performing) approaches are "less interpretable and the analytical properties of the solutions are not well understood". Could the authors explain how their techniques are more interpretable than subspace clustering [2]?

[1]: Spectral Clustering Based on Local PCA. Arias-Castro, Lerman and Zhang. 2017.
[2]: Subspace Clustering for High Dimensional Data: A Review. Parsons, Haque and Liu. 2004.

questions:
I will select a few questions from the above weaknesses as the ones which can be responded to in the short reviewer-response period. The numbered elements are those which are more immediately pressing I list some additional things which would be nice-to-have but likely outside the scope of a reviewer-response period.
 1. Can the authors explain how Lemmas 1-4 come together to prove Propositions 3 and 1? A roadmap of the proofs would go a long way to making it easy to follow.
 2. Furthermore, could the authors address the issue in equations 50 -> 51 and verify that Lemma 2 still holds?
    - Similarly, I would appreciate an explanation of steps 43-48. Currently, these steps are completely unclear to me.
 3. For the experiments, could the authors compare against other approaches for partitioning the datasets before doing the tSNE embeddings? I am under the impression that other partitioning approaches (using spectral clustering or neural nets) should give equally good segmentations and therefore lead to comparable embedding quality.
    - Some quantitative measures of the embedding quality would go a long way. When comparing the embeddings visually, I am uncertain what I am looking for in a formal sense.
 4. A more detailed evaluation of the related work is in order. Specifically, the topics of subspace clustering seem very relevant but have been brushed off in the introduction.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730272695681

thread_type:
official_review

<thread_object>
creator: reviewer_sx3t

<content>
summary:
The authors propose an approach for dimensionality reduction that optimize a combined objective function from multiple similarity matrices/graphs that result from partitions the features. This eases known problems with classical techniques for embedding where extreme dimension reduction can distort results/large embedding dimension is required for faithful representation. They provide theoretical results characterizing the solution of their stated optimization problem as well as related asymptotic analysis. They provided experiments that examine the efficacy of their approach in real data.

strengths:
originality: The approach of partitioning features first, and then embedding, is certainly original in the context of dimensionality reduction. (As the authors mention, feature partitioning was considered in the spectral biclustering literature, but the authors' version is more general)

quality: The quality of the mathematical derivations, the exposition, the motivation, and the experiments, are sufficient and satisfactory. The mathematical results are sufficiently deep and relevant, and the application use cases are clearly motivated and illustrated. The experimental results and comparisons are relevant and convincing. 

 clarity: This is perhap the biggest strength of the paper. The mathematical content and derivations involving multi graph setting and Riemannian manifolds naturally look complicated, but the authors did a good job of exposition by first explaining the tradition construction and graph score and then generalizing it to the feature partitioning case. I enjoyed reading the paper and followed it without problem due to the exposition. 

 significance: dimensionality reduction is an important area of study, and the practical technique introduced here (with theoretical analysis) is a welcome and substantial contribution to the area.

weaknesses:
I list my questions and comments here: 

1. How to choose K is an important consideration in this problem, but the authors do not seem to sufficiently address this. I do not expect any theory/simulations etc, but I would like to see a high level discussion that addresses choosing K, and how that could relate to dimensionality of the embedding space etc. 

2. What is the practical computaitonal complexity tradeoff between the feature partition approach vs the traditional approach?

questions:
n/a
</content>
</thread_object>

</thread>
<thread>
creation date:
1730856053187

thread_type:
official_review

<thread_object>
creator: reviewer_gdbr

<content>
summary:
This paper addresses the problem of manifold learning and dimensionality reduction, specifically examining cases where the observed features can be divided into several disjoint subsets. The authors propose an approach that begins by partitioning the features into subsets that minimize a graph-Laplacian-based smoothness score within each partition. Subsequently, traditional manifold learning techniques are applied separately to each subset. As a result, this scheme captures the underlying structure of the observations more effectively than traditional methods that analyze the features as a whole. The method's effectiveness is demonstrated through several examples involving simulated and real datasets, also by presenting some theoretical analysis that supports the method's optimality.

strengths:
- This paper is well-written and easy to follow.
- The problem of manifold learning when the features falls onto several disjoint groups is important and interesting, this is also well-motivated by an example shown in Figure 1.
- The proposed method that aims to finding the partitions by mimimize the Laplacian scores is straight-forward, and appears to be techniqually correct. Especially, I like the result in Proposition 1 that shows how the Laplacian score (Eq. 3) is connected with the Gaussian kernel. Besides, the theretical analysis is a good plus that consolidates the efficacy of the method.

weaknesses:
My primary concern is with the experimental section. Since this paper relies on the assumption that the observed features comprise several disjoint subsets, it would be beneficial to address, or at least discuss, the following questions:

- How can we validate the existence of this assumption given a set of observed features? Answering this question could guide users in selecting the appropriate method for manifold learning.

- What are the results when this assumption does not hold? This is crucial for practical applications, as it is often challenging to confirm this assumption in real datasets (unlike the illustrative example with figurines shown in Figure 1).

- How does the method perform when the number of partitions is not optimal? In real-world applications, finding the ideal number of partitions may not be feasible, so it would be valuable to understand if sub-optimal choices still yield meaningful results. Although it may not be necessary to devise an automatic technique to determine the optimal number, a clear understanding of this hyperparameter would make the proposed method more accessible for practical use.

questions:
N/A
</content>
</thread_object>

</thread>
<thread>
creation date:
1731123441590

thread_type:
official_review

<thread_object>
creator: reviewer_zpyn

<content>
summary:
This paper introduces a new two-step approach that involves partitioning followed by dimensionality reduction. The partitioning is performed using a graph-based approach, drawing on the construction of the affinity graph from t-SNE.

strengths:
The formulation is original and builds upon t-SNE, which is a widely used state-of-the-art dimensionality reduction approach. It relies on an adaptive kernel bandwidth, enabling it to capture heteroscedastic noise in the data.

Some efforts are made to develop theoretical insights in terms of manifold approximation. While I find it challenging to fully assess the relevance of this, the proofs appear to be sound.

weaknesses:
I see two main weaknesses in this work that I believe the authors should address for the paper to meet the required standard:

1- A similar result to Proposition 1 already exists, specifically Proposition 1 in reference (a). This previous result is actually stronger than the one presented here, as it demonstrates that the entropy constraint can be relaxed into a lower bound while still achieving equivalence with the affinity matrix of t-SNE. Although the authors of (a) do not impose a null diagonal, one can simply add the null diagonal in the constraints to recover the matrix W tilde (the t-SNE affinity matrix). Considering such a relaxation in the present paper could add significant value by converting the problem into a convex one.

Reference (a):
Van Assel, H., Vayer, T., Flamary, R., & Courty, N. (2024). SNEkhorn: Dimension Reduction with Symmetric Entropic Affinities. Advances in Neural Information Processing Systems, 36.

2 - The experimental section is insufficient, and the datasets considered are too small. The authors only examine a dataset of 3,745 cells. Larger and more diverse datasets should be considered to strengthen the experimental results in this paper.

questions:
- Can you relate the clustering mechanisms presented here to any known algorithms, such as kernel k-means with the kernel matrix W tilde ? This comparison could provide insights into the quality of the resulting clustering.

- If I understand correctly, Problem 2 not only includes entropy in the objective but also changes the adaptive bandwidth to a global scalar bandwidth. Does this not diverge too much from the original problem?

I believe it would be beneficial to include the algorithm in the main text rather than in the appendix.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733283807921

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
We sincerely thank the area chair and all the reviewers for their valuable time and insightful feedback. Many of your suggestions have been thoughtfully incorporated into this revised version. Key revisions made:


1. **Presentation.** We have significantly improved the presentation of the paper, enhancing both the context and motivation, as well as the clarity of the figures. Specifically, we expanded the discussion of traditional clustering techniques within the context of feature partitioning in the Introduction. In Section 3.3, we strengthened the scientific rationale for applying our approach to the examined biological dataset used in the experiment. Furthermore, we revised Fig. 1 for improved clarity and updated the captions of both Fig. 1 and Fig. 4 for better understanding.


2. **Experiments.** We made the second experiment more comprehensive by including the results of traditional clustering techniques (spectral clustering and k-means) and providing a thorough quantitative comparison with our results (Sections 3.2 and D.2). Originally, such a comparison was only made in the experiment within Section 3.1. Additionally, we added an ablation study on a subset of the COIL-20 dataset (Section H).


3. **Proofs.** The Proofs section (Section F) was significantly enhanced. An overview of the proofs has been added (page 21), and the derivations within the proofs were substantially expanded, ensuring a much more detailed and clear presentation.


4. **Practical Implications and Considerations.** Section G has been introduced to discuss the practical aspects of our algorithm, providing readers with a clearer understanding of how to use it effectively. For example, it discusses how to determine the number of feature partitions, and how a suboptimal choice of this number affects the partitioning results produced by our algorithm.
(This section is placed at the end of the Appendix to preserve the paper's structure during the rebuttal stage but will appear near its beginning in the camera-ready version).


We hope these revisions address the reviewers’ concerns and improve the overall quality of the manuscript.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper provides new insights for visualizing (and embedding) high dimensional data using Laplacian feature partitioning. The reviews lean positive while being split along the border; authors agree on the merits of this paper but also had significant reservations. There was some engagement in the rebuttal period but no discussion ensuing. Overall, significant revisions such as overhauls and additions to the proofs of the main results suggest that this revised submission should undergo a full round of review. I encourage the authors to improve the paper accounting for the constructive comments of the reviewers