acceptodds
Withdrawn from ICLR 2027

Low-Rank Recovery of High-Order Neighbor Structure for Scalable Multi-View Clustering

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

Abstract

Anchor-based multi-view clustering has attracted considerable attention for its scalability. However, existing methods face three limitations: (1) direct sample–anchor graphs insufficiently capture high-order neighbor connectivity; (2) conventional tensor nuclear norm regularization may over-shrink dominant singular values; (3) heterogeneous relationships among view pairs are often not explicitly modeled. To address these limitations, we propose High-Order Neighbor Recovery (HONR), a scalable framework for recovering high-order neighbor structure through low-rank tensor learning. Specifically, HONR uses multi-step random walks to capture indirect sample–anchor connections and aggregates transitions across orders and views into a compact tensor. For a more accurate approximation of tensor rank, we introduce an arctangent-based nonconvex approximation that alleviates the excessive shrinkage of dominant singular values. Furthermore, a view-relation regularizer based on order-wise transition similarities explicitly models pairwise view relationships and promotes consistency between structurally similar views. An alternating optimization algorithm is developed, with computational complexity linear in the number of samples when the numbers of anchors and views are fixed. Experiments against eight baselines on seven benchmark datasets demonstrate the effectiveness of the proposed HONR.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
Multi-view clustering, anchor graphs, high-order neighbor recovery, low-rank tensor learning, nonconvex rank approximation

Reviews

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

This paper proposes the anchor-based multi-view clustering framework (HONR). The proposed method adopts random walks to capture indirect sample–anchor connections and construct a compact tensor for clustering. Experiments (including ablation and convergence analyses) show some advantages of the method.

Critical strengths
  • S1. The proposed HONR incorporates high-order neighbor information via anchors. The computational complexity scales linearly with the number of samples under fixed settings.
  • S2. Across seven benchmark datasets, HONR achieves competitive clustering results against eight baselines. Ablation studies also show the effectiveness of different components.
Critical weaknesses
  • W1. HONR mainly combines existing techniques, including random walks, tensor recovery, and view regularization. The transition tensor and view graph are fixed before optimization, leaving limited novelty in their integration.
  • W2. In Eq. (3), transitions from different orders are directly summed before tensor construction. The resulting tensor captures aggregated information, with limited distinction between individual orders.
  • W3. The regularizer in Eq. (5) encourages consistency between similar views. Its ability to model heterogeneous view relationships is not sufficiently demonstrated.
  • W4. Current ablations provide limited comparisons with alternative transition constructions and rank penalties. Runtime and memory comparisons are also missing despite the scalability claim.
  • W5. Section 4.1 uses a bounded penalty parameter, while Theorems 4.1 and 4.2 require summable reciprocals of this parameter. The stated convergence conditions appear inconsistent with a finite upper bound.
Questions for authors

Please see the weaknesses above.

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

This paper proposes HONR, a scalable multi-view clustering framework based on high-order neighborhood recovery and low-rank tensor learning. Multi-step random walks are used to capture indirect sample-anchor relationships, followed by an arctangent-based nonconvex tensor rank approximation. A view-relation regularizer further models structural similarities across views. Experiments on seven datasets show improved clustering performance over several existing methods.

Critical strengths
  1. The paper addresses the limitation of direct sample-anchor graphs in capturing high-order neighborhood relationships, which is relevant to scalable multi-view clustering.
  2. The proposed optimization framework is clearly formulated, with theoretical analyses of convergence and computational complexity.
  3. The experimental results are strong across multiple datasets, and the method maintains favorable computational efficiency.
Critical weaknesses
  1. The overall novelty is limited. The framework combines multi-step random walks, nonconvex tensor regularization, and view-relation modeling, all of which have been explored in related work. The main methodological contribution is not sufficiently distinguished from existing approaches.
  2. The advantage of the arctangent-based rank approximation is not well established. The paper lacks direct comparisons with alternative nonconvex tensor rank surrogates under the same framework.
  3. The effectiveness of high-order neighborhood recovery requires further analysis. Higher-order transitions may introduce noisy or less discriminative relationships, and the paper does not sufficiently examine when this becomes problematic.
Questions for authors
  1. What is the main technical advance beyond combining existing high-order graph modeling and low-rank tensor recovery techniques?
  2. How does the arctangent-based regularizer compare with other nonconvex rank approximations?
  3. How does the random-walk order affect clustering performance, especially when the underlying graphs contain noisy connections?
Reviewer_4LSmOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes High-Order Neighbor Recovery (HONR) for scalable multi-view clustering. The method aggregates multi-step sample–anchor transitions into a compact tensor, then recovers a nonnegative representation using an arctangent-based nonconvex low-rank penalty and a view-relation graph regularizer. An ADMM-based algorithm is developed with closed-form subproblem updates and a complexity analysis. Experiments on seven benchmark datasets compare HONR with eight baselines, supplemented by ablation and parameter sensitivity studies.

Critical strengths

S1: HONR provides a coherent framework for combining indirect sample–anchor connectivity with cross-view structural consistency. The compact anchor-based representation avoids explicitly constructing full sample–sample graphs and offers potential scalability advantages for multi-view clustering.

S2: The proposed method achieves competitive results across seven benchmark datasets, with particularly noticeable improvements on MSRC, MITIndoor, and ALOI. The ablation studies also provide evidence that high-order transitions, nonconvex regularization, and view-relation modeling contribute to the overall performance.

Critical weaknesses

1.The optimization description and convergence claims contain unresolved inconsistencies. The error update following Eq. (12) omits λ\lambda from its shrinkage threshold, although the stated subproblem requires a threshold proportional to λ/ρ\lambda/\rho. Additionally, Eq. (4) defines the penalty using Fourier transforms along the view dimension, whereas Section 4.2 rotates the tensor and transforms along the anchor dimension; these generally define different regularizers. More substantially, Theorems 4.1-4.2 require summability of the inverse penalty sequence, but the specified update caps ρ\rho at a finite value, violating this assumption. These issues make it difficult to establish that the described algorithm solves the stated objective and that the convergence results apply to the reported experiments.

2.The convergence analysis is not fully consistent with the stated optimization procedure. Theorems 4.1 and 4.2 require summability conditions on the penalty-parameter sequence, whereas the practical update rule caps ρ at a finite maximum value. This schedule does not satisfy the stated assumptions over infinitely many iterations. Consequently, the theoretical results do not directly establish convergence of the algorithm as specified, despite the empirically stable behavior shown in Figure 3.

3.The experimental protocol does not sufficiently clarify how hyperparameters are selected or whether competing methods receive comparable tuning budgets. The reported results are obtained by repeating only the final clustering step, leaving the variability introduced by anchor initialization and representation learning insufficiently evaluated. Furthermore, closely related tensor-based methods, including WTCAGL and S²MVTC, are discussed in the manuscript but are not included in the quantitative comparisons. These omissions make it difficult to fully assess the reliability and fairness of the reported performance improvements.

Questions for authors
  1. Could the authors clarify whether the shrinkage threshold in the E-update should be λ/ρ\lambda/\rho. rather than 1/ρ1/\rho? Additionally, Eq. (4) and Section 4.2 appear to use different tensor orientations for the Fourier transform. Which formulation is adopted in the implementation, and do these inconsistencies affect the reported results?

  2. Theorems 4.1 and 4.2 rely on summability assumptions that are incompatible with the capped penalty update. Could the authors explain how the theoretical convergence guarantees apply to the implemented algorithm? If the assumptions are not satisfied, can the authors provide an alternative justification or appropriately qualify the convergence claims?

  3. How are the hyperparameters selected for HONR and the competing methods, particularly in the absence of ground-truth labels for model selection? Are comparable tuning criteria and search budgets used for all methods? Could the authors also report results from repeated runs of the complete pipeline, including anchor selection, rather than repeating only the final clustering step?

  4. The manuscript discusses closely related tensor-based multi-view clustering approaches, such as WTCAGL and S²MVTC, but does not include them in the experiments. Could the authors provide comparisons with these methods where applicable? Furthermore, can the authors report end-to-end runtime and memory consumption as the number of samples increases to substantiate the claimed scalability?

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

Related papers

Discussion (0)

Sign in to comment.