- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes SCoGF, an anchor-graph-based method for incomplete multi-view clustering. It constructs graphs from observed views, combines them through masked averaging, and obtains cluster assignments using randomized spectral embedding and cross-anchor extension. The method avoids explicit imputation during graph construction and does not require iterative graph fusion. The paper also analyzes observation coverage, graph aggregation, spectral stability, and clustering consistency. Experiments on five datasets against 16 baselines show competitive clustering results and relatively low computational cost, particularly compared with iterative approaches.
Critical strengths
SCoGF offers a computationally efficient approach to incomplete multi-view clustering. The non-iterative fusion step and the use of anchor graphs help reduce the cost of clustering without reconstructing missing views.
The theoretical analysis is a useful part of the paper. It examines how missing observations affect graph aggregation and spectral clustering, with detailed proofs provided in the appendix.
The experiments cover a reasonable range of missing rates and include both symmetric and view-dependent missingness. Comparisons with 16 baselines, together with runtime and sensitivity analyses, provide useful evidence for the method's performance.
The paper also reports worst-case results and cases where competing methods perform better, making the experimental comparison more informative.
Critical weaknesses
There is a gap between the theoretical analysis and the actual algorithm. Theorem 5.3 considers spectral clustering on the extended consensus graph, while Algorithm 1 extends the anchor embedding and then applies k-means. It is not clear that the theorem guarantees the output of the implemented procedure.
A similar issue arises with anchor selection. Assumption 3(a) relies on uniformly sampled anchors, but the implementation uses deterministic k-means on standardized, zero-filled features. The experiments in Appendix F support this choice empirically, but they do not establish whether the theoretical results still apply.
The novelty relative to existing methods needs to be clearer. Most of the individual components, including anchor graphs, reconstruction weights, graph fusion, and randomized spectral decomposition, are already established. The paper would benefit from a more specific comparison with IMVC-CBG, RISE, and JVILG to show what SCoGF adds beyond combining these techniques.
Uniform graph fusion ignores differences in view reliability. When some views are much noisier or less informative than others, equal weighting may not be appropriate. The weaker result relative to JVILG on Caltech101-20 does not establish the cause, but it raises the question of how sensitive SCoGF is to differences in view quality. A controlled comparison with adaptive weighting would help.
The experimental setting is somewhat limited. The datasets mainly use handcrafted features, and missingness is introduced through randomized masking. The results therefore say little about missing-not-at-random cases, such as cluster-dependent missingness, or performance with learned representations. The scalability experiments could also cover larger datasets.
Hyperparameters are selected using ground-truth ACC at 50% symmetric missingness and then fixed for other settings. Although this protocol is applied to all methods, it still uses label information unavailable in practical unsupervised clustering. Results with label-free parameter selection would make the evaluation more convincing.
The presentation could be improved with a simple pipeline diagram and plots showing performance and runtime trends. Releasing the code only after acceptance also makes the results harder to reproduce during review.
Questions for authors
How does Theorem 5.3 relate to the actual procedure in Algorithm 1? In particular, does the guarantee extend to cross-anchor embedding followed by k-means?
Can the theoretical analysis be extended to the deterministic k-means anchor selection used in the implementation, rather than uniform random sampling?
How does SCoGF behave when views have substantially different noise levels or discriminative power? Could the authors compare uniform fusion with adaptive view weighting while controlling for missingness?
What happens when missingness depends on sample characteristics or cluster membership? Which theoretical results would remain valid? Could the authors report results using label-free hyperparameter selection, or quantify the gap between label-free selection and the current oracle tuning protocol?
3 comments
Response to Reviewer EUaF (2/3): W4/Q3, W5
W4/Q3 — uniform fusion ignores view reliability; controlled comparison with adaptive weighting. The question came up at the outset of the design. The three weighted variants of N1 — a missing-rate prior, an price and an ADMM rule that updates against the per-view residual — were built before the uniform average, which entered as the control arm; the comparison was run to find the gain, not to defend a choice already made. It did not appear. Across the nine cells none of the three improves on the printed by more than 0.007 on average in either metric, none leads in both, and only the learned rule adds computation, since it replaces the closed-form fusion with an iterative solve.
G3 gives the reason, and carries the per-cell table. A data-independent weighting enters only through a global scale that degree normalization annihilates; on a single-view sample that scale is all there is to shift, and where a sample keeps several views unequal weights only lower the effective view count. We do not claim uniform is universally better. On Caltech101-20, where JVILG's learned weights lead us (0.628 to 0.461 at ), the regime favours them. We claim that at these missingness levels a global coefficient has no measurable room to act, which is why the released configuration keeps the simpler .
W5 — limited setting. (i) MNAR: N4 runs two class-dependent mechanisms, the cluster-dependent kind the reviewer names, and SCoGF leads all four cells on MSRC-v5 and mfeat; on Caltech101-20 JVILG leads, as it does in the paper's Table 1, and Theorem 5.4 states which guarantees survive and where they break. The table is in G2. (ii) Scale: N7 and N8, tabulated in G4a. (iii) Randomized masking is deliberate, since it is the only way to compare sixteen methods under one protocol, and its one structural property is on the record: every sample retains one view, which is why nominal is realized as 0.78–0.81. N6 reports the guarantee-free case honestly (43–47% retained; first on mfeat, behind on MSRC-v5 and Caltech101-20), and its table is in R2-Q1. (iv) Feature family: "handcrafted" is a property of the data, not of the estimator, and all sixteen baselines consume the same released matrices, so the comparison isolates the estimator. The views differ in kind, not only in dimension: colour, texture, shape, gradient-orientation and LBP descriptors of the same photographs (MSRC-v5, Caltech101-20, ALOI), six representations of the same handwritten digit (mfeat), three leaf descriptors (100Leaves), and new in N7 four video-derived visual streams plus one audio stream. The estimator itself takes arbitrary per-view matrices, with no kernel bandwidth and no per-view learned weights, so a learned backbone's outputs could serve as its views. That is the extent of the claim, stated in Appendix E.
Response to Reviewer EUaF (3/3): W6–W7, Q4
W6 — hyperparameters selected with ground-truth ACC. As in Q2 to Reviewer 2: the protocol is identical for all methods, SCoGF's grid spans at most 0.029 ACC end to end (Appendix D), and the label-free reading is available from that same table (fixed : 0.010 average, 0.018 worst-case cost). The normalized-cut criterion on the consensus graph, the very objective Theorem 5.5 controls, and stability selection across mask resamples are the principled label-free selectors. We state plainly that no reliable label-free selector is known to us at .
W7 — presentation; code after acceptance. The revision includes the pipeline diagram (Fig. 1) and the component-attribution table (Appendix J). This response adds the performance and runtime trends as tables with per-cell draws (N1–N11), including the per-stage breakdown in N9.
| Dataset | total | anchors | graph | fuse | spectral | ||
|---|---|---|---|---|---|---|---|
| MSRC-v5 | 210 | 0.0 | 1.24 | 0.45 | 0.36 | 0.000 | 0.40 |
| MSRC-v5 | 210 | 0.3 | 1.16 | 0.54 | 0.29 | 0.000 | 0.30 |
| MSRC-v5 | 210 | 0.5 | 0.97 | 0.52 | 0.20 | 0.000 | 0.21 |
| MSRC-v5 | 210 | 0.7 | 0.87 | 0.55 | 0.14 | 0.000 | 0.15 |
| mfeat | 2000 | 0.0 | 8.14 | 7.12 | 0.27 | 0.009 | 0.68 |
| mfeat | 2000 | 0.3 | 10.35 | 9.53 | 0.26 | 0.008 | 0.48 |
| mfeat | 2000 | 0.5 | 7.82 | 7.21 | 0.20 | 0.008 | 0.33 |
| mfeat | 2000 | 0.7 | 6.53 | 6.09 | 0.14 | 0.007 | 0.21 |
Table N9: per-stage runtime in seconds, one CPU core, means over 3 runs. "spectral" is the randomized SVD plus extension.
Anchor selection dominates at both scales (7.12 of 8.14 s at , 0.45 of 1.24 s at ), and the total tracks the observed entries and the anchor budget rather than . That is the mechanism behind the runtime falling as rises (8.14 → 6.53 s on mfeat from to 0.7, the same direction as the 258–380 s span of the nine YoutubeVideo settings at the 1.5% budget). The reference implementation will be released with the camera-ready version of the paper.
Q4 — missingness depending on sample characteristics. (a) Cluster membership: Theorem 5.4, and the test in N4, whose table is in G2. The masked average becomes block-constant with scale inside each block, degree normalization cancels it blockwise, and the normalized adjacency, hence the stability and consistency guarantees, is unchanged, with only the coverage floors worse. SCoGF leads all four cells on MSRC-v5 and mfeat by +0.120 to +0.204 and on Caltech101-20 keeps the ordering of the paper's Table 1. (b) Which results survive is the same theorem's boundary: everything under block-constant (cluster-dependent) missingness survives; once missingness depends on features within a cluster, block-constancy fails and only the coverage statement remains. (c) Label-free selection is quantified in Q2 to Reviewer 2: one fixed with no labels costs 0.010 ACC on average and 0.018 at most, against 0.54 for a single parameter move in RISE's grid. The residual limitation, no reliable selector at , is stated rather than papered over.
Response to Reviewer EUaF (1/3): W1/Q1, W2/Q2, W3
We thank Reviewer EUaF for the most detailed report, and for the positive assessment of the computational efficiency, the non-iterative fusion, the theory with its proofs, the coverage of missingness protocols and the worst-case reporting.
W1/Q1 — Theorem 5.3 versus the actual procedure. A new row-geometry proposition (Appendix A: structural event plus per-sample occupancy) covers every sample whose Stage-1 neighborhood lies within its own cluster, in particular every sample farther than εa+εr from its cluster boundary, which is all but an O(dˉ(εa+εr)/Δsep) fraction. Such a sample has a cross-anchor row supported on same-cluster anchors, and (CUK)i=γib~k⊤ with γi>0 coincides, after row-L2 normalization, with the ideal spectral embedding row of the extended graph Gext. The one block k0 carrying the (K+1)-th direction keeps the same threshold-plus-Markov control. Hence the k-means partition of Algorithm 1 coincides with the ideal spectral partition except on that boundary fraction and the O(1/τ2) fraction inside k0. The end-to-end theorem (now Theorem 5.5) therefore bounds the realized output with the explicit term O(K(dˉ(εa+εr)/Δsep+τ−2)), and the idealization sentence is gone. The connection is also structural: F is the Nyström/LSC-type extension of the anchor eigensystem, so the label-filling step is inside the analyzed object rather than after it.
W2/Q2 — anchors as uniform draws versus deterministic k-means. As in W2 to Reviewer 2: Assumption 3(a) is now a net condition (εa-net plus per-cluster quota), and a new proposition covers both sufficient instances, uniform draws via Serfling and quantization rules via strong consistency and quantization theory. All budgets are unchanged up to the quota constant c, and the quota never binds in practice (worst class-view cell at η=0.9: 24 observed anchors against r+1=16). Appendix F's paired comparison (+0.19 ACC on ALOI at η=0.7, gap growing in N and η) is now supporting evidence rather than the assumption's justification, and the deterministic rule is kept for its determinism and representativeness, not because it scores higher.
W3 — novelty; comparison with IMVC-CBG, RISE, JVILG. §2 of the revision states the delta component by component, and the paper's Table 3 places the four methods side by side. (i) Where the mask enters. In SCoGF it enters each view's local reconstruction: every observed anchor is re-solved over its r nearest observed anchors, so the graph is built on the observed sub-block and no bandwidth or per-view weight is needed. In IMVC-CBG the fusion is over fixed anchor graphs, with no mask-aware re-solving and no end-to-end guarantee; in RISE it is the kernel values a missing view cannot supply; in JVILG it is learned view weights inside an iterative solver. (ii) What the fusion is. The uniform masked average is the exact minimizer of the masked aggregation objective (Proposition 5.2) with O(1/V) variance, whereas a weighted average of fixed affinities is not the minimizer of anything in particular. (iii) What is guaranteed. The extension error splits into an anchor-subproblem term and a cross-anchor term, and the normalized-cut bound follows (Theorem 5.5, now for the realized output). To our knowledge no method in the panel states a bound connecting missingness to the returned partition; IMVC-CBG offers convergence of its scheme and O(N) cost, statements about the optimization.
The practical content of (i)–(iii) is visible in the results: the same machinery that wins RISE and JVILG their peak cells is their failure mode under missingness (MSRC-v5: JVILG at 0.143=1/K across its whole grid, RISE 0.22 off its plateau), while SCoGF's row never collapses. The per-cell evidence is in N2 (R1-Q2), N7 (G4a) and N11 (R3). We also say plainly what is not new: reconstruction weights, anchor graphs, Nyström-style extension and randomized SVD are all classical. We claim the composition and its analysis, since no part yields the end-to-end bound alone. Because missing entries are never imputed and the fusion is closed form, the method is one anchor pass, one O(NdˉV) graph, one randomized SVD and a k-means, with no training, no iterative solver and no per-view weights, which is what keeps it robust at 105 samples on one CPU core.