- Rating
- 1
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
This paper proposes One-Step Consistency-aware Graph Dictionary Learning (OCGDL) for incomplete multi-view clustering. It reconstructs partially observed affinity graphs using shared and view-specific orthogonal dictionaries, imposes row-wise regularization on reconstruction coefficients, and applies a tensor nuclear norm to the stacked dictionaries. Spectral rotation with adaptive view weights connects the dictionaries to discrete clustering assignments. The objective is optimized using an ADMM-style alternating procedure. Experiments cover six benchmark datasets, multiple missing rates, ablations, parameter sensitivity, and runtime comparisons.
Critical strengths
The paper reports competitive clustering results, including clear improvements in several settings on Caltech101-20 and ALOI, with repeated-run statistics. This provides some empirical evidence for the usefulness of the proposed combination.
Critical weaknesses
1. The model lacks a convincing justification, and its claimed spectral foundation does not support the final formulation.
The paper does not identify a sufficiently precise limitation of existing models that necessitates this particular objective. Shared-specific decomposition, group-sparse dictionary learning, tensor regularization, and spectral rotation are established ingredients. The main contribution appears to be their integration, while the advantage over a simpler shared basis with view-dependent spectra remains insufficiently established. The shared-dimension sensitivity study and V5 provide partial evidence, but do not replace a matched comparison that isolates the benefit of the proposed decomposition and relaxation.
The theoretical motivation for Eq. (2) is also problematic. The Davis–Kahan bound in Appendix A.2, Eq. (23), controls distances between spectral subspaces; it does not imply the exact shared block asserted in Eq. (24). Two one-dimensional eigenspaces can be arbitrarily close while having no common nonzero vector. Thus, the existence of an exactly shared nonzero requires additional assumptions. Subspace closeness alone also does not establish the particular block-diagonal spectral representation in Eq. (2). These are modeling assumptions requiring justification, rather than consequences of the stated perturbation bound.
The relaxation from Eq. (2) to Eq. (3) further disconnects the final model from this motivation. Replacing with free coefficients preserves the column orthogonality of , but does not generally preserve symmetry of the reconstructed affinity or ensure that contains its eigenvectors. The claim that the orthogonal-complement constraint retains a genuine eigendecomposition is therefore unsupported. For the unmasked, unregularized reconstruction term with a fixed orthonormal , the least-squares solution is , giving a standard projection interpretation. The paper should explain what additional graph-spectral property survives the relaxation and why the rows of , rather than the coefficient columns, are the appropriate clustering features.
The remaining regularizers are insufficiently motivated. The row-wise penalty promotes atom selection within each view, but does not itself explicitly encourage different views to select different atoms. The tensor nuclear norm adds another form of cross-view coupling on top of the explicitly shared dictionary and common clustering indicator, without clearly identifying its distinct role. V4 relocates the tensor penalty to affinity representations rather than removing it, so it does not establish that this additional coupling is necessary. Overall, the objective appears to accumulate familiar terms without sufficiently explaining why they form a coherent and necessary model.
The optimization does not resolve these concerns. In particular, Eq. (8) uses a row-wise argmax, whereas the objective contains , whose normalization depends on cluster sizes. The claimed update does not follow directly from this coupled objective and needs a derivation or a descent guarantee. Standard alternating updates and empirical residual plots do not provide a substantive new theoretical contribution or establish convergence to a stationary solution of the stated problem.
2. The efficiency claims omit unresolved graph-construction costs and are not supported by sufficiently controlled comparisons.
Appendix A.3 analyzes optimization given a preconstructed sparse graph with a constant average number of nonzero entries per row. Its simplification to additionally requires treating the relevant dimensional parameters as constants; and alone do not justify that simplification. More importantly, the analysis does not account for obtaining the input graph from the original data. If all pairwise similarities are computed before sparsification, graph construction already incurs quadratic work in the sample size. Subsequent sparsification does not remove that cost. Approximate nearest-neighbor search may reduce preprocessing, but changes the graph, and the paper would need to verify the reported clustering performance using that actual construction. The graph-building and sparsification procedures are not specified sufficiently to establish an end-to-end near-linear claim.
The storage implications also remain unresolved. An explicitly stored dense graph requires quadratic space per view, while a sparse representation can reduce this cost only under an explicit sparsity and storage assumption. Reporting a smaller regularization tensor does not establish the total memory complexity of the graph, coefficients, auxiliary variables, and intermediate computations. A complete space-complexity analysis and peak-memory measurements are missing.
Graph sparsity is also an input assumption from which compatible competing methods can benefit. A fair efficiency claim therefore requires consistent accounting of sparsity, preprocessing, and implementation across methods. It cannot be established merely by using sparse-graph bounds for the proposed algorithm and dense-graph bounds for competitors. Compact embedding-tensor regularization can reduce the cost of that particular module, as the comparison with V4 suggests, but this saving must be distinguished from savings attributable to graph sparsification.
The comparison with anchor-based methods needs similar care. Sample-level graphs and anchor-based representations differ in both retained relationships and construction costs. Higher accuracy than an anchor-based method, combined with lower runtime than a dense-graph method, does not by itself establish a superior accuracy–efficiency trade-off. The paper should use common graph inputs where the methods support them and report end-to-end accuracy, runtime, and peak memory over graph-density or anchor-budget settings. Different representations are legitimate algorithmic choices, but their costs and approximation effects need to be exposed rather than left as confounding factors.
Section 4.5 and Figure 6 do report runtime; the concern is what those timings include and whether the comparisons support the claimed advantage. Five benchmarks have at most 2,386 samples, the largest has 10,800, and missingness is generated by random sample removal. Without a controlled scaling study, explicit graph-construction and parameter-selection protocols, and consistent end-to-end timing, these experiments provide limited support for broad scalability or robustness claims.
Questions for authors
-
What assumptions justify the exact shared block in Eq. (24) and the decomposition in Eq. (2)? After the coefficient relaxation, what spectral property is retained, and what evidence establishes an advantage over a shared basis with view-dependent spectra?
-
What happens when the tensor nuclear norm is removed while retaining the shared dictionary and spectral-rotation term? Does it provide an independent benefit beyond these existing forms of cross-view coupling?
-
What exact graph-construction and sparsification procedure is used in the reported experiments? Does it compute all pairwise affinities, and do the reported accuracy and runtime use the same exact or approximate graph-building pipeline?
-
Does Figure 6 include preprocessing for every method? Are sparse operations used for compatible baselines? Please clarify the comparison with anchor-based methods through end-to-end time, peak memory, parameter selection, and the accuracy–efficiency trade-off across representation budgets.
-
How is Eq. (8) derived while accounting for the cluster-size dependence of ? Is the update guaranteed to decrease the stated objective, and how are empty clusters handled?
6 comments
Q1: Assumption and corollary justification
Q1: What justifies the exact shared block (Eq. 24) and decomposition (Eq. 2)? After coefficient relaxation, what spectral property remains, and what evidence supports an advantage over a shared basis with view-dependent spectra?
A1: We thank the reviewer. The revised corollary links Eqs. (24) and (2): under small perturbations, each view's leading eigenvectors can approach after orthogonal alignment (Davis--Kahan).
Corollary: Shared and view-specific spectral factors
Let be a symmetric latent consensus affinity, with ordered eigenvalues and gap . Let collect the corresponding orthonormal eigenvectors and set , so . For each view, let be symmetric, and let collect the leading orthonormal eigenvectors of , with . These columns are the view-wise counterpart of :
Davis--Kahan gives
Thus, for some orthogonal ,
where are the principal angles between the two subspaces.
Also,
Let and be the leading orthonormal eigenvectors of (descending eigenvalues), with .
The exact partial eigen-expansion is
and . If , the ordered split is not unique and the two blocks can mix inside the tied subspace. Set .
Substituting the aligned basis gives
where .
With a positive eigengap and small perturbations, Davis--Kahan bounds subspace misalignment. This motivates shared and view-specific in Eq. (2).
After coefficient relaxation (Eq. (3)), stays symmetric and positive semidefinite for any coefficient, while serves as reconstruction coefficients of the affinity columns for flexible graph modeling and do not force to be orthogonal, so are the appropriate clustering features.
In the revised manuscript, we include the Learned per-view graphs on Caltech101-20 and ALOI at a 50% missing rate in Figures 14 and 15 respectively to show that OCGDL and learn effective graphs after the dictionary relaxation, which approximate class-aligned blocks on Caltech101-20 and within-class diagonals on ALOI, with varying contrast across views. At 50% missingness, OCGDL averages 91.69% ACC across six datasets versus 86.25% for V5, supporting coefficient relaxation.
Q2: w/o TNN ablation & Q3: graph-construction procedure & Q4: preprocessing and end-to-end time and peak memory
Q2: What happens when the tensor nuclear norm is removed while retaining the shared dictionary and spectral-rotation term? Does it provide an independent benefit beyond these existing forms of cross-view coupling?
A2: We thank the reviewer for the valuable suggestion. We have added a new ablation variant V6 (w/o TNN) in the revised Table 2, removing only the TNN regularization term while keeping all other components and experimental settings unchanged.
TNN captures high-order cross-view correlations on the compact graph dictionary tensor. At a 50 missing rate, removing TNN reduces the average ACC across six datasets from 91.69 to 63.42, demonstrating its additional contribution beyond the shared dictionary and spectral rotation. See our response to Reviewer BkvR (Q2) for ablation results and complete results in the revised manuscript.
Q3: What exact graph-construction and sparsification procedure is used in the reported experiments? Does it compute all pairwise affinities, and do the reported accuracy and runtime use the same exact or approximate graph-building pipeline?
A3: We thank the reviewer for the valuable suggestions. OCGDL employs kNN to construct similarity graphs by computing all pairwise affinities in ts observed samples with the computational complexity for one view. The corresponding edge weights are computed using a self-tuning Gaussian kernel, followed by symmetrization and normalization to obtain a sparse similarity graph. All reported accuracy and runtime of OCGDL use the same graph initialization by setting k=10.
The compared methods follow the graph initialization strategies of their public implementations, including kNN (LSIMVC, OAGL, HCLS_CGL, OIMC-IAGD), PCA (SCSL), Zeros (CAL). To help understand the effects of different initialization strategies, we compare three graph initialization methods, including kNN, self-representation-based L1SC, and PCA, refer to A5 of Reviewer gLYR. The results show that PCA is an possible alternative of kNN, thus all reported accuracy and runtime of different methods except for CAL use the same exact or approximate graph-building pipeline.
Q4: Does Figure 6 include preprocessing for every method? Are sparse operations used for compatible baselines? Please clarify the comparison with anchor-based methods through end-to-end time, peak memory, parameter selection, and the accuracy--efficiency trade-off across representation budgets.
A4: We thank the reviewer for the valuable comments. Figure 6 in the original manuscript reports runtime including preprocessing and optimization. Figure 6 in the original manuscript reports runtime including preprocessing and optimization. In the revised manuscript, Figure 6(a) distinguishes preprocessing and end-to-end runtime, and Figure 6(b) additionally reports peak memory usage.
The compared methods use their public implementations and their parameter search ranges are added in the revised manuscript in Appendix A.4. OCGDL attains a competitive end-to-end runtime and peak memory usage comparable to anchor-based methods. Applying the tensor nuclear norm to a compact graph dictionary keeps the computational and memory overhead low while capturing low-rank correlations across views, so OCGDL offers a favorable accuracy–efficiency trade-off.
W1 Effect of row-wise ℓ2,1 penalty
We thank the reviewer for the careful and detailed review.
W1: row-wise ℓ2,1 penalty promotes atom selection within each view, but does not itself explicitly encourage different views to select different atoms.
AW1: We thank the reviewer for the valuable comments. Although the row-wise penalty does not directly promote diversity across views, sparsity can remove redundant and non-essential coefficients during reconstruction and then induce view-dependent atom energies and selections in both the shared and the specific blocks, promoting cross-view different dictionaries in Hsv and different atom selection in Hc.
To help understand the effect of the group sparsity, we have added an intuitive comparison of atom activation energy (row ℓ2 norm) and coefficient heatmaps for Caltech101-20 and ALOI in Figures 11--13 of the Appendix 4. Compared with V2 (no sparsity) which retains redundant atoms and V3 (ℓ1) which produces element-wise sparsity without clear row-wise selection patterns, the row-wise ℓ2,1 group sparsity can encourage more differences between views in both shared and view-specific coefficients. Together with the ablation results in Table 2, these results support the effectiveness of group sparsity regularization in encouraging diverse graph dictionaries, reducing redundancy, and improving clustering performance. Please check the complete results and discussion in the revised manuscript.