acceptodds
Withdrawn from ICLR 2027

Nonlinear Kernels in Linear Time: Order-Invariant Large-Scale Multiview Subspace Clustering

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

Abstract

Multiview clustering (MVC) has garnered considerable attention owing to its capability to uncover intrinsic data structures by integrating complementary information across multiple views. However, existing large-scale MVC methods still suffer from two notable limitations: 1) tensor-based modeling may implicitly exploit the sequential structure of sorted samples, introducing hidden prior information that conflicts with the unsupervised learning setting, 2) they lack the ability to characterize complex nonlinear structures of multiview data under linear computational complexity. To address these issues, we propose a novel large-scale MVC model for effectively handling nonlinear data, which not only avoids employing the latent priors of sorted samples to enhance order invariance in high-order tensor modeling, but also captures complex nonlinear sample relationships while preserving linear scalability in the number of samples. Then, an efficient ADMM-based alternating optimization algorithm with linear complexity is developed to solve the proposed model. More importantly, the convergence guarantee of the algorithm is theoretically established. Extensive experiments conducted under sorted and shuffled settings on diverse benchmark datasets, including large-scale dataset with more than 100,000 samples, demonstrate that our proposed method achieves superior clustering performance against state-of-the-art methods.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
Multiview Subspace Clustering, Low-Rank Tensor Representation Learning, Nonlinear Kernels, Permutation Invariance, Linear-Time Algorithm

Reviews

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

This paper proposes NK-OLMC, a nonlinear kernel method for large-scale multi-view clustering. It uses random Fourier features (RFF) to approximate Gaussian kernels and weighted tensor nuclear norm (WTNN) to capture high-order cross-view correlations, enhancing nonlinear modeling while maintaining linear computational complexity.

Critical strengths

The paper is clearly written and provides extensive experiments. The experiments cover datasets of various scales, include direct comparisons with strong baselines, and provide several auxiliary experiments.

Critical weaknesses

The novelty is insufficient for ICLR. Compared with LMTC, the paper only replaces the linear kernel with a nonlinear kernel and the tensor norm with WTNN. LMTC has already identified and addressed the issue of tensor rotation exploiting sample-order structures. Thus, the paper offers no substantial contributions beyond introducing nonlinear kernels and WTNN.

Questions for authors
  1. The novelty is insufficient for ICLR. Compared with LMTC, the paper only replaces the linear kernel with a nonlinear kernel and the tensor norm with WTNN. LMTC has already identified and addressed the issue of tensor rotation exploiting sample-order structures. Thus, the paper offers no substantial contributions beyond introducing nonlinear kernels and WTNN.

  2. The authors emphasize the ability to capture complex nonlinear manifold structures, but the experiments mainly report final clustering metrics without controlling the degree of nonlinearity. For example, synthetic multi-view datasets with varying manifold curvature could verify whether the advantages of RFF come from nonlinear modeling rather than additional hyperparameter tuning.

  3. Page 6 reports wide search ranges for Dr,λ,CD_r, \lambda, C. A full grid search would require 1,280 runs, which is too expensive for unsupervised clustering and difficult to reproduce.

  4. LMTC already shows stable robustness to sample ordering. On some datasets, such as COIL20, the proposed method exhibits slightly greater variation than LMTC.

  5. To avoid sample-order dependence, the authors apply FFT along the view dimension. However, this may introduce dependence on view ordering. The authors should clarify this issue.

  6. There are apparent numerical inconsistencies in the experimental tables. The ALOI results in Tables 2 and 4 may contain reporting errors. The authors should verify them.

I will consider revising my score based on the authors' responses.

Reviewer_xxJ6OpenReview ↗
Rating
2
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes NK-OLMC for large-scale multi-view clustering. It uses random Fourier features to approximate view-specific RBF kernels without constructing full sample-by-sample kernel matrices. It then stacks the view-specific latent representations along the view dimension and applies weighted tensor nuclear norm regularization. The authors argue that this design captures nonlinear relationships while avoiding the sensitivity to sample order associated with tensor rotation. Experiments on eight datasets report strong clustering accuracy under shuffled sample order.

Critical strengths
  1. The method is well motivated. It addresses two relevant problems in scalable MVC: nonlinear similarity modeling and sensitivity to sample ordering.
  2. The method has a compact formulation. For a fixed random-feature dimension, its main optimization operations scale linearly with the number of samples.
  3. The shuffled-data experiments are encouraging. The method achieves the highest reported ACC on all eight datasets, with a particularly substantial gain over LMTC on 100leaves. The evaluation also includes a dataset with more than 100,000 samples.
Critical weaknesses
  1. The weighted tensor nuclear norm (WTNN) is an existing regularizer, but the main text introduces it without clearly attributing the prior work.
  2. The value of the bandwidth scaling parameter (alpha) is unclear. Several reporting details affect confidence in the results. LMTC’s ALOI ACC is 68.97 in Table 2 but 47.39 in Table 4.
  3. Since this is an approximation approach for nonlinear kernel construction, it is unclear what the approximation error is.
  4. Kernel approximation is not a new concept. The authors need to clarify the key contributions and how it differs from existing approaches.
Questions for authors
  1. How is the median pairwise distance computed on the largest datasets? Do the runtime and memory measurements include bandwidth estimation?
  2. Can the authors reconcile the ALOI ACC discrepancy between Tables 2 and 4?
  3. The construction of the random Fourier features (Z_v) is mathematically clear in Eqs. (2)–(4), but several details needed for reproduction are missing. What value of (alpha) and what final (D_r) were used for each dataset?
  4. Is it possible to analyze the boundedness of approximation error?
Reviewer_36dpOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

NK-OLMC integrates RFF-based nonlinear similarity and weighted tensor nuclear norm (WTNN) regularization into order-robust multi-view clustering. An ADMM/GPI solver and conditional KKT analysis are provided. Experiments on eight datasets and fourteen baselines evaluate accuracy, efficiency, and permutation robustness.

Critical strengths
  1. Convincing experiments. Eight datasets, fourteen baselines, permutation tests, runtime results, and ablations support the method. It obtains the highest ACC on all eight shuffled datasets, with notable gains on 100leaves and ALOI.

  2. Practical design. The method combines RFF-based nonlinear similarity modeling with non-rotated tensor construction, avoiding explicit N × N kernel matrices while maintaining robustness to sample permutations.

Critical weaknesses
  1. Conditional convergence result. Theorem 1 assumes ρₖ(Nᵥᵏ⁺¹ − Nᵥᵏ) → 0, but does not establish this condition from Algorithm 1. Thus, its KKT guarantee is conditional rather than an unconditional convergence proof.

  2. Unclear WTNN weighting. The weights depend on singular values, but their update schedule is unspecified. If adaptive, Eqs. (22)–(23) and (28)–(36) require justification for the same objective.

Questions for authors
  1. Can the authors derive Theorem 1’s asymptotic condition from the actual updates, or qualify the convergence claim?

  2. Are the WTNN weights fixed or adaptive, and how do Eqs. (22)–(23) support the KKT analysis?

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

This paper proposes a large-scale MVC model for nonlinear data, to capture complex nonlinear sample relationships while preserving linear sample scalability without employing the latent priors of sorted samples. An ADMM based alternating optimization algorithm with linear complexity is developed. Experiments under sorted and shuffled settings on diverse benchmark datasets, including dataset with more than 100,000 samples, are conducted to demonstrate the superior clustering performance of the proposed method against state-of-the-art methods.

Critical strengths
  1. The proposed model measures pairwise relationships in the nonlinear feature space via Gaussian kernel, which extends similarity modeling beyond linear relationships and enables complex nonlinear dependencies among samples to be incorporated into multiview clustering.
  2. This paper uses random Fourier features to provide an explicit approximation to the Gaussian kernel, avoiding quadratic storage and computational costs with respect to the number of samples without anchor selection.
Critical weaknesses
  1. The combination of random Fourier features-approximated kernels + kernel alignment + tensor low-rank regularization offers limited methodological novelty. The paper does not propose a novel modeling principle for MVC.
  2. The persuasiveness of experimental comparison is questionable. For example, "It also successfully completes all experiments, whereas several competitors encounter OT or OM issues on large-scale datasets. These results further corroborate the effectiveness and scalability of our method across different evaluation metrics" is too general and arbitrary. The decision threshold for OT/OM and the time budget for each method were not specified.
Questions for authors
  1. With respect to order invariance, what exactly is the theoretical increment of the proposed method? If the increment lies mainly in absolute accuracy rather than theoretical invariance, should the contribution statement be revised accordingly?
  2. What are the time limit and the memory limit for marking OT/OM? Do all baselines use the same budget?

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

Related papers

Discussion (0)

Sign in to comment.