acceptodds
Withdrawn from ICLR 2027

Maximum Variance Unfolding on Disjoint Manifolds

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

An assumption underlying much of machine learning is that observed data are often sampled from a manifold of much lower dimension than the data space itself. While linear methods such as PCA can often be used to perform dimensionality reduction, they fail to capture nonlinear relationships in the data, which are often present in natural datasets. Maximum variance unfolding (MVU) is an established and well-studied neighborhood graph-based method for nonlinear dimensionality reduction with the unique property of retaining strong local isometry. However, its applicability to real-world data is limited due to its dependence on the connectivity of the underlying neighborhood graph: in natural datasets, data are often irregularly sampled, multimodal, or lie on disjoint manifolds, giving rise to clusters of points that are distant in the data space. In this work, we present a method that extends MVU to the common case where data lie on disjoint manifolds. By embedding neighborhood graph components in parallel and later building component connections, our method decreases both computation time and memory requirements, even with a single processor. Furthermore, we identify two practical failure modes of MVU, which our method inherently addresses, resulting in improved performance with respect to standard metrics that assess the extent to which the local structure of the data is preserved.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
manifold learning, maximum variance unfolding, nonlinear dimensionality reduction

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.25 over 4 reviews, above 2% of the others.
Reviewer_uFQhOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This work proposes a formulation of maximum variance unfolding for data sampled from disjoint manifolds. This provides a more flexible formulation of maximum variance unfolding that is faster because it can be run in parallel on different manifolds. This method is verified an many different datasets on computation speed and a variety of standard dimensionality reduction embedding quality metrics.

Critical strengths

The paper is clear and descriptive with a nice recipe-based introduction to the proposed method.

Furthermore, the paper offers extensive experimental validation against a wide variety of baselines.

Critical weaknesses
  1. Interesting idea, but would be stronger with some theory backing the algorithms. This would also clarify/ inform critical mathematical decisions in the algorithm design.

  2. The paper is missing disjoint-manifold dimensionality reduction baselines.

Questions for authors
  1. Theoretical backing:
  • What kind of data can be embedded faithfully by this method?
  • If this embedding doesn’t maximize variance, what optimization problem does it solve on the set of disjoint manifolds?
  • L162 Algorithm 1 Are we guaranteed that each of Y_p are mapped to the same space by MVU? If not, how can we measure distances between points in different R^n?
  • L198 How do you choose the node to begin the breadth first search? Or do you just assume that the k-nearest neighbors graph results in more than 1 connected component?
  • 214 Why do you sample uniformly at random? You could sample from a different distribution. The following sentence sounds like it could be used as an optimization problem that could be solved for optimal representative point sets. “The goal is to choose a sample from each component that both adequately represents its large-scale geometry and that is small enough to keep the component connection step computationally cheap”
  1. Related works:
  • This seems like a valuable related work/ baseline method for embedding data on disjoint manifolds or clustered on one manifold. Isometric Multi-manifold Learning for Feature Extraction by Fan et al.
  • L042 Mention other graph-based methods like Laplacian Eigenmaps for Dimensionality Reduction and Data Representation by Belkin et al?

Other questions

  • L031 Distinguish between feature extraction vs feature selection in dimensionality reduction
  • L067 This is a plot of maximum variance unfolding which is not the algorithm that is proposed in this paper. It seems out of place as a choice for figure 1. Normally figure 1 explains the novel algorithm or workflow. I would expect to see a visual representation of Algorithm 1.
Reviewer_bZpqOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

The authors introduced a variant of the manifold-learning algorithm "maximum variance unfolding" (MVU) that can be used for data sets where the k-nearest neighbor graph (the usual starting point for most manifold learning algorithms) is disconnected. This can occur, for example, when the data points lie on disjoint underlying manifolds. The new algorithm, MVU-DM, works by embedding the components in parallel using vanilla MVU, and then translating those embeddings after by considering/adding inter-component connections.

Critical strengths

Their algorithm is more efficient than vanilla MVU and other MVU variants, and the time speed up is significant when the underlying data lies on disjoint manifolds.

Critical weaknesses
  1. At best, the contributions of this paper need to be reframed. First of all, it is not a challenge to handle disconnected graphs because you can always add a few edges to connect the disconnected components. The authors acknowledge that this is what Van Der Maaten et al (2009) does for MVU. They say that the advantage of their algorithm MVU-DM is that it is faster than vanilla MVU or the Van Der Maaten et al (2009) variant or other MVU variants (this is true as far as I can tell), so one could reframe the main contribution as an efficient version of MVU. However, MVU is one of the slowest manifold learning algorithms out there compared to more common algorithms such as t-SNE, UMAP (discussed but cited incorrectly as Dalmia and Sia 2021 instead of McInnes et al), Isomap (not discussed in related work), LLE (not cited), Laplacian eigenmaps (not cited), not to mention more modern manifold learning algorithms. If the main contribution is a time speed up, then I'd like to see timing + performance comparisons with other major manifold learning algorithms that are not MVU variants. I'd also like to see much larger data sets. I saw the t-SNE and UMAP comparison in Table 8 and Table 10 in the appendix, and it looks like UMAP/t-SNE had stronger performances on the natural datasets (and UMAP and t-SNE aren't really optimized for preserving distances, so I'd be more interested in a comparison with say, Isomap, if distance preservation is the main goal).

  2. My experience in practice is that it's rare to have disconnected kNN graphs for real data sets (i.e., truly disjoint underlying manifolds), unless the neighborhood size parameter k is set way too low (usually fixable by increasing k).

Questions for authors

How many components did the kNN graphs have for the natural data sets, and what was your neighborhood parameter size k? What is the evidence that there are multiple ground-truth disjoint components? Are the different classes truly disjoint?

Reviewer_sgmGOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

The paper proposes a divide and conquer formulation of the Maximum Variance Unfolding (MVU) dimension, subdividing data into separate manifolds process independently and then combined. Processing subdivided manifolds independently is faster and sometimes even more robust, especially when there is underlying disconnect in the manifold.

Critical strengths
  • The proposed method is very simple and very straight forward - classic divide and conquer strategy applied to MVU.
  • It seems to be effective - no worse than MVU (for the most part, varying k might be a bit of an issue, see questions below)
  • The paper is well written
Critical weaknesses

The propose method is kind of obvious. On one hand, I applaud the authors for not making it sound like it's more than it is - it's a very straight forward method that does MVA in chunks that can be run in parallel. But then, for ICLR I would expect a bit more substantial technical novelty of the proposed method.

Questions for authors

Can you make a case for why your approach is not the "obvious" approach?

Also, while picking best k for presenting result in the main paper is understandable, but I wonder if it hides a bit of a limitation of MVUDM. Looking at the appendices and the trustworthiness sensitivity for varying k, MVU curves seem a bit flatter at lower k's; not in every instance, but on average. Is it a fair to say that MVUDM is not as robust to choice of k at lower end of k? Presumably chunking the data too much? I imagine the number of components highly depends on k, doesn't it?

Reviewer_VnBUOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes Maximum Variance Unfolding on Disjoint Manifolds (MVU-DM), an extension of classical Maximum Variance Unfolding (MVU) designed to handle datasets with disconnected neighborhood graphs. The proposed method decomposes the original problem into independent MVU subproblems, embeds each connected component separately, and subsequently aligns these components through representative points and rigid transformations. This decomposition reduces computational and memory requirements while preserving local distance constraints within individual components. Experiments on synthetic and natural datasets demonstrate substantial computational speedups and generally competitive embedding quality compared with conventional MVU and Landmark MVU.

Critical strengths
  1. The paper addresses a well-defined limitation of classical MVU, particularly its difficulty in handling disconnected neighborhood graphs and its high computational complexity.
  2. The proposed component-wise decomposition is conceptually straightforward and computationally attractive. The reported speedups, particularly on datasets with multiple disconnected components, are substantial.
  3. The authors provide experiments on both synthetic and natural datasets, evaluating embedding quality through trustworthiness and continuity, along with computational efficiency.
  4. The discussion of two potential failure modes of conventional MVU provides useful insights into the behavior of variance-maximizing manifold learning methods.
Critical weaknesses
  1. The central idea of decomposing disconnected neighborhood graphs, independently embedding their components, and subsequently aligning them using geometric transformations is relatively straightforward. Similar graph decomposition and component alignment strategies have been explored in previous manifold learning literature. The authors should more clearly explain the fundamental methodological differences between MVU-DM and existing approaches, particularly Fan et al. (2018), and identify the genuinely novel contributions beyond computational decomposition.
  2. Although the method preserves local distances within individual components through rigid transformations, it does not guarantee that the resulting global embedding maximizes variance or preserves the original intercomponent geometry. The authors explicitly acknowledge the absence of global optimality guarantees. A more rigorous theoretical analysis of the approximation quality, global geometric distortion, and conditions under which the proposed method provides reliable embeddings would significantly strengthen the paper.
  3. The proposed alignment procedure relies on representative points, a limited set of candidate directions, and sequential component connections. It is unclear whether this strategy can reliably recover global geometric relationships when components have different intrinsic dimensions, irregular shapes, or ambiguous relative orientations. The authors should investigate the sensitivity of the method to component connection order, anchor selection, and geometric configurations.
Questions for authors
  1. What are the key methodological differences between MVU-DM and the disconnected-neighborhood-graph approach proposed by Fan et al. (2018)? Can the authors provide a more direct comparison?
  2. Can the authors establish theoretical bounds on global geometric distortion or approximation error introduced by independently embedding and aligning disconnected components?
  3. How does the method behave when the neighborhood graph contains one dominant component and several small components? Under what conditions does the decomposition cease to provide meaningful computational advantages?
  4. Why are the candidate alignment directions restricted to the positive and negative canonical basis vectors? Would a more general optimization over rotations and translations improve global geometric preservation?
  5. Since the proposed method uses a fixed proportion of representative points and selects the best-performing neighborhood parameter for each dataset, how sensitive are the conclusions to these choices? Could the authors clarify the parameter-selection protocol?
  6. Can the authors provide experiments on larger datasets and evaluate whether the resulting embeddings improve downstream machine learning performance?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.