acceptodds
Under review as a conference paper at ICLR 2027

SCoGF: Spectral Consensus Graph Fusion for Scalable Incomplete Multi-view Clustering

Abstract

Spectral multi-view clustering under view-level missingness faces an unresolved tension: scalable methods rely on kernel evaluations that are undefined when a sample lacks a view, while incomplete-view methods either impute missing views and propagate recovery error, or couple all samples in every iteration at cubic cost. We propose SCoGF (Spectral Consensus Graph Fusion), a single-pass method in which the missing masks shape the graph construction directly rather than entering through any later correction. SCoGF learns per-view anchor graphs from simplex-constrained reconstruction weights on observed anchors only, fuses them by a uniform masked average that is the exact minimizer of the masked aggregation subproblem, and embeds all samples through a randomized SVD with a missing-aware cross-anchor extension. Deterministic -means anchor selection makes the output reproducible given the masks. The pipeline is imputation-free, non-iterative, free of kernel bandwidths and learned view weights, and near-linear in . Theoretically, we prove that the masked average is statistically sound with variance decaying in the view count, the anchor embedding is stable under explicit budgets on the anchor and view counts, and the resulting partition admits an end-to-end normalized-cut consistency bound. Empirically, across multi-view benchmarks under both symmetric and view-dependent missingness, SCoGF is the only compared method that never collapses on feature-heterogeneous data, while running orders of magnitude faster than iterative competitors and requiring no per-rate tuning.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
incomplete multi-view clustering, spectral clustering, consensus graph fusion, scalability, clustering consistency

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_EUaFOpenReview ↗
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
AuthorsOpenReview ↗

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\varepsilon_a+\varepsilon_r from its cluster boundary, which is all but an O(dˉ(εa+εr)/Δsep)O(\bar d(\varepsilon_a+\varepsilon_r)/\Delta_{\mathrm{sep}}) fraction. Such a sample has a cross-anchor row supported on same-cluster anchors, and (C~UK)i=γib~k⊤(\widetilde C U_K)_i=\gamma_i\tilde b_k^\top with γi>0\gamma_i>0 coincides, after row-L2 normalization, with the ideal spectral embedding row of the extended graph G^ext\widehat G^{\mathrm{ext}}. The one block k0k_0 carrying the (K+1)(K{+}1)-th direction keeps the same threshold-plus-Markov control. Hence the kk-means partition of Algorithm 1 coincides with the ideal spectral partition except on that boundary fraction and the O(1/τ2)O(1/\tau^2) fraction inside k0k_0. 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))O(K(\bar d(\varepsilon_a+\varepsilon_r)/\Delta_{\mathrm{sep}}+\tau^{-2})), and the idealization sentence is gone. The connection is also structural: FF 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\varepsilon_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 cc, and the quota never binds in practice (worst class-view cell at η=0.9\eta=0.9: 24 observed anchors against r+1=16r{+}1=16). Appendix F's paired comparison (+0.19 ACC on ALOI at η=0.7\eta{=}0.7, gap growing in NN and η\eta) 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 rr 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)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)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/K0.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)O(N\bar dV) graph, one randomized SVD and a kk-means, with no training, no iterative solver and no per-view weights, which is what keeps it robust at 10510^5 samples on one CPU core.

AuthorsOpenReview ↗

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 R2R^2 price and an ADMM rule that updates α\alpha 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 1/V1/V 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 η=0.5\eta{=}0.5), 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 1/V1/V.

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 η=0.9\eta=0.9 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.

AuthorsOpenReview ↗

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 r=10r=10: 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 m/K=5m/K=5.

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.

DatasetNNη\etatotalanchorsgraphfusespectral
MSRC-v52100.01.240.450.360.0000.40
MSRC-v52100.31.160.540.290.0000.30
MSRC-v52100.50.970.520.200.0000.21
MSRC-v52100.70.870.550.140.0000.15
mfeat20000.08.147.120.270.0090.68
mfeat20000.310.359.530.260.0080.48
mfeat20000.57.827.210.200.0080.33
mfeat20000.76.536.090.140.0070.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 N=2000N{=}2000, 0.45 of 1.24 s at N=210N{=}210), and the total tracks the observed entries and the anchor budget rather than NN. That is the mechanism behind the runtime falling as η\eta rises (8.14 → 6.53 s on mfeat from η=0\eta{=}0 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 ρˉkk\bar\rho_{kk} 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 r=10r=10 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 m/K=5m/K=5, is stated rather than papered over.

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

For IMVC tasks, this paper proposed a SCoGF model, in which the missing masks shape the graph construction directly rather than entering through any later correction. SCoGF learns per-view anchor graphs from simplex-constrained reconstruction weights computed on observed anchors only, fuses these graphs by a uniform masked average that is the exact minimizer of the masked aggregation subproblem, and embeds all samples through a randomized SVD with a missing-aware cross-anchor extension. Experiments span five benchmarks, two missingness protocols, missing rates up to 70%, sixteen baselines, and include a tuning sweep, a runtime table, and an applicability/worst-case summary.

Critical strengths
  1. Each view builds its anchor graph only over the anchors it observes, so missing anchors enter as zero rows and columns rather than as imputed values. The pipeline requires only pairwise co-observation rather than jointly visible samples;
  2. This paper proved the statistical soundness of the uniform masked average, anchor spectral stability with explicit budgets in the anchor count, view count, and eigengap, and normalized-cut consistency of the final partition, whose total error decomposes into an anchor-subproblem term and a cross-anchor extension term.
Critical weaknesses
  1. The efectiveness of the proposed method should be proved on the larger scale datasets.
  2. Compared with the methods based on deep learning, what advantages does this method have? This point was not well reflected in the manuscript. Moreover, the experimental results of this method do not have particularly significant superiority.
Questions for authors

See above.

1 comment
AuthorsOpenReview ↗

Response to Reviewer qoio: W1–W2

We thank Reviewer qoio for an accurate summary of the method and of the experimental coverage.

W1 — effectiveness on larger-scale datasets. The scale concern was the paper's weakest point and is now answered with numbers rather than extrapolation. On YoutubeVideo (N=101,498N=101{,}498), with nothing tuned for the dataset, SCoGF at a 1.5% anchor budget matches RISE's published ACC (25.60 vs 25.52), exceeds its NMI (20.81 vs 17.88) and exceeds IMVC-CBG's (22.96 / 14.12), in 380 s per setting on one CPU core — the slowest of the nine — against 900 s and 1168 s as published, i.e. 2.4–3.1× less wall clock. The nine other incomplete-view baselines in that benchmark's comparison are reported out of memory. Three qualifications are stated rather than buried: published runtimes come from each paper's own hardware, so the comparison is of reported budgets; the anchor budgets differ, and we list all five, including m=155m{=}155 where we are behind both; and ACC here is compressed, since the majority class alone gives 26.62, above every method's nine-rate mean, so we read the comparison on NMI and claim to sit inside the published band at a fraction of the cost rather than to be more accurate. The synthetic curve (N8) then isolates cost itself: 0.32–0.37 ms/sample from 20k to 100k samples. Both tables are in the global response (G4a).

W2 — advantages over deep methods; significance. On significance we quote the tests. Cell-level paired tests on the same masks are significant at α=0.05\alpha=0.05 after Holm correction against all sixteen baselines; the weakest, RISE, has p=1.4×10−2p=1.4\times10^{-2}, and being the largest of the sixteen it carries a multiplier of 1, so the corrected value equals the raw one. SCoGF is ahead in 15/20 cells with a median gap of +0.075. The Friedman test over the seven methods that run on all five datasets gives mean ranks 1.65 / 2.30 / 4.20–5.60, χ2(6)=55.99\chi^2(6)=55.99, p=2.9×10−10p=2.9\times10^{-10}, and at the Nemenyi critical difference of 2.01 we are separable from every method except RISE. The worst-case column, the deployment-relevant one, is 0.390 against 0.361 (RISE) and 0.143 (JVILG's trivial 1/K1/K), with SCoGF the only method that never collapses. These tests now appear in §6.2 of the revision, where the claim is worded to match them.

On deep methods, the two families estimate different objects. A deep IMVC method trains a recovery/alignment network per dataset, and its published numbers depend on the backbone, the training schedule and its own missingness model. Copying those numbers across protocols is exactly what we criticize in others; a single row would confound estimator, extractor and protocol. We therefore do not claim ACC superiority over deep methods and keep their numbers out of the controlled tables. Set beside their provenance, however, they answer the question directly.

FamilyMethodACC (%)NMI (%)cost per setting
deepWAH-MVC29.4022.74GPU train
GCFAgg27.5827.31GPU train
DCMVC27.2627.29GPU train
MVCAN25.0124.43GPU train
DSIMVC15.577.46GPU train
shallowSCoGF (ours), V=5V{=}5, 10–90% missing25.6020.81380 s
RISE25.5217.88900 s
IMVC-CBG22.9614.121168 s

Table N11: YoutubeVideo (N=101,498N=101{,}498, K=31K=31). Deep entries: published numbers at V=3V{=}3 with complete views, as tabulated in WAH-MVC; each trains a view-specific network on this dataset. Shallow entries: published numbers and ours at V=5V{=}5 with 10–90% of view entries missing and a 1.5% anchor budget. Not a controlled comparison (view count, completeness and training budget differ); shown to locate our operating point. Runtimes as reported by each paper, deep entries covering the GPU training stage only.

On YoutubeVideo, the one large benchmark both lines report, four of the five deep entries lie between 25.01 and 29.40 ACC at V=3V=3 with complete views, the fifth at 15.57; our 25.60 falls inside that span, obtained at V=5V=5 with 10–90% of view entries missing and a 1.5% anchor budget. The leading deep entries are the more accurate option there, and each pays for that with a network trained on this dataset. Neither number transfers to the other's setting. What the comparison shows is applicability rather than a win: no training, no pretrained features, one CPU core, and the shortest runtime among all non-deep methods (258–380 s per setting against 900 s for RISE and 1168 s for IMVC-CBG). Deep encoder outputs can serve as SCoGF's input views, which we state as future work.

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

The author proposes a new incomplete multi-view clustering method, which utilizes the observed anchor points to learn the simplex constraint of the anchor point graph for each view and reconstruct the weights. It fuses them through a unified mask averaging process, without the need for padding, non-iteration, kernel bandwidth and learning view weights, and reduces the running time. Its effectiveness is verified on multiple datasets.

Critical strengths

(1) The experiment was comprehensive in its evaluation, and it also took into account the worst-case scenario. (2) The paper systematically summarizes three common failure mechanisms of incomplete multi-view spectral clustering - joint visibility bottleneck, iterative fusion error propagation, and interpolation geometric distortion.

Critical weaknesses

(1) All theoretical analyses are based on the MCAR (Missing Completely at Random) assumption, which cannot cover the more common non-random missing situations (MNAR) and scenarios related to sample characteristics in reality. (2) Theoretical part idealizes the anchor points as uniformly random sampling, which does not match the actual deterministic k-means selection. It is only verified through experimental ablation studies and lacks corresponding theoretical support.

Questions for authors

(1) The missing rate in the experiment reached as high as 70%, and no exploration was conducted for extreme missing scenarios. For example, 90% (2) Since the paper focuses on the unsupervised scenario, but the hyperparameter selection adopts a parameter tuning protocol based on the true labels. This is unreasonable. Can we find a way to solve it?

2 comments
AuthorsOpenReview ↗

Response to Reviewer pUB8 (1/2): W1–W2

We thank Reviewer 2 for an accurate summary of the method and for the positive reading of the evaluation's coverage, the worst-case analysis and the three failure mechanisms.

W1 — all theory is MCAR. The revision replaces the assumption with an exact statement plus a test. Theorem 5.4: if Pr⁡(oi(v)=1∣i∈cluster k)=1−ηv,k\Pr(o^{(v)}_i=1\mid i\in\text{cluster }k)=1-\eta_{v,k}, then E[G^ij∣i∈k,j∈ℓ]=ρˉkℓsij⋆\mathbb{E}[\widehat G_{ij}\mid i\in k,j\in\ell]=\bar\rho_{k\ell}s^\star_{ij} with ρˉkℓ=1V∑v(1−ηv,k)(1−ηv,ℓ)\bar\rho_{k\ell}=\frac1V\sum_v(1-\eta_{v,k})(1-\eta_{v,\ell}). On the structural event the consensus graph is block diagonal, each block is scaled by the single constant ρˉkk\bar\rho_{kk}, and degree normalization cancels it blockwise. The normalized adjacency — and with it stability (Theorem 5.3) and consistency (Theorem 5.5) — is unchanged, with only the coverage floors worsened (ρˉ→min⁡kρˉkk\bar\rho\to\min_k\bar\rho_{kk}, ρ0→min⁡v,k(1−ηv,k)2/2\rho_0\to\min_{v,k}(1-\eta_{v,k})^2/2). The failure boundary is stated precisely: within-cluster feature-dependent missingness breaks block-constancy, and then only the coverage statement survives.

N4 tests the mechanism the reviewer names, with masks whose rate is a function of the class (block: half the classes at 0.8, half at 0.2; ramp: one rate per class from 0.2 to 0.8), with the baselines rerun on identical masks at 30 paired draws per cell. SCoGF leads all four cells on MSRC-v5 and mfeat (+0.120 to +0.204, 30/30 draws, p≤5.2×10−6p\le5.2\times10^{-6}): MSRC-v5 0.575 / 0.672 against IMVC-CBG's 0.371 and RISE's 0.481, mfeat 0.768 / 0.805 against JVILG's 0.573 and RISE's 0.685. LMVSC sits at 0.161–0.466 and JVILG collapses to 0.157–0.161 on MSRC-v5. On Caltech101-20 the class-dependent mask leaves the standing ordering intact, with JVILG at 0.634 / 0.642 against our 0.426 / 0.371, the same sign and comparable size as at the published operating point. Because one rate per class breaks cross-class representativeness but not within-class averaging, we present N4 as a lower bound on the damage rather than a robustness claim. The per-cell table is with Theorem 5.4 in the global response (G2).

W2 — anchors idealized as uniform draws. The revision answers on both levels, empirically by the comparison we already had and formally by rewriting the assumption. Assumption 3(a) now requires that the observed anchors of every cluster-view cell form an εa\varepsilon_a-net of the cluster support and satisfy the quota mk(v)≥c mπkρ0m^{(v)}_k\ge c\,m\pi_k\sqrt{\rho_0}. A new proposition shows that (a) uniform draws satisfy it with high probability, by Serfling concentration plus covering regularity, which recovers the previous analysis verbatim, and (b) any rule with bounded per-cluster quantization radius and quotas satisfies it deterministically, since kk-means centroids have vanishing radius by strong consistency. All downstream theorems use only the net condition. The quota is verified empirically and never binds: N10a shows every class-view cell retaining at least r+1r{+}1 observed anchors at every rate up to η=0.9\eta=0.9 (worst cell 24 against 16). Appendix F's paired 30-draw comparison also shows the deterministic rule dominating uniform draws, with the gap growing in NN and η\eta (+0.19 ACC on ALOI at η=0.7\eta{=}0.7), which is now a bonus rather than the assumption's support. A fully axiomatic derivation of the quota for kk-means remains open, and the theory does not need it.

AuthorsOpenReview ↗

Response to Reviewer pUB8 (2/2): Q1–Q2

Q1 — extreme missingness, e.g. 90%. The paper stops at η=0.7\eta=0.7 for a reason worth stating. The protocol keeps one view observed per sample, so a nominal η=0.9\eta=0.9 is realized at only 0.78–0.81, and the genuinely extreme case was never run; the reviewer is right that it should have been. We report both readings.

N5 keeps the one-view guarantee. SCoGF stays ahead of the panel on mfeat and on the NMI of Caltech101-20, while JVILG's partitions stop responding to the draw (sd 0.000) and LMVSC sits at the 1/K1/K floor on two of the three benchmarks, so the competitors degenerate before we do.

Dataset (VV)realized η\etaSCoGFRISEJVILGIMVC-CBGLMVSC
MSRC-v5 (5)0.7820.263 / 0.1200.328 / 0.2030.267 / 0.1170.246 / 0.1370.164 / 0.053
mfeat (6)0.8110.372 / 0.3170.317 / 0.1970.100 / 0.0000.220 / 0.1610.103 / 0.009
Caltech101-20 (6)0.8110.198 / 0.2630.223 / 0.1290.404 / 0.2310.259 / 0.1670.334 / 0.032

Table N5: nominal η=0.9\eta=0.9 with the one-view guarantee active, 30 paired draws per cell; ACC / NMI, best in bold.

N6 removes the guarantee, leaving 53–57% of samples observing nothing and unassignable; on the retained subsample the same picture holds, first on mfeat and first on NMI at Caltech101-20.

DatasetretainedSCoGFRISEJVILGIMVC-CBGLMVSC
MSRC-v589/210 (43%)0.289 / 0.1680.322 / 0.2420.295 / 0.1930.284 / 0.1920.218 / 0.119
mfeat942/2000 (47%)0.520 / 0.4740.484 / 0.4030.113 / 0.0010.245 / 0.1950.118 / 0.020
Caltech101-201124/2386 (47%)0.244 / 0.3290.336 / 0.2240.333 / 0.0010.269 / 0.2070.334 / 0.041

Table N6: true η=0.9\eta=0.9 without the one-view guarantee, evaluated on the samples observing at least one view ("retained"), 30 paired draws per cell, ACC / NMI, best in bold.

These numbers land where the theory places the envelope. Pairwise coverage is 1−∏v(2ηv−ηv2)1-\prod_v(2\eta_v-\eta_v^2) and the budgets scale as ρˉ−1=(1−η)−2\bar\rho^{-1}=(1-\eta)^{-2}, so at η=0.9\eta=0.9 with V≤6V\le6 only about 6% of anchor pairs are supported by any view and the budgets inflate by two orders of magnitude. The guarantees are vacuous there by prediction rather than oversight, while the pipeline stays defined at any rate thanks to the per-sample safeguard. RISE and JVILG in both tables are our re-implementations of those algorithms.

Q2 — true-label tuning. The protocol is the field's, not ours. One configuration per dataset, chosen at a fixed rate, is the protocol of the incomplete-view line we build on: Liu et al. and IMVC-CBG fix one setting per dataset and vary only the missing rate, and the two most recent competitors report their tables the same way. Applying the identical grid to all sixteen methods is what makes the comparison even-handed, and it is applied to SCoGF in the same way. The sweep's purpose is robustness, not selection. It shows that the method does not need a per-cell constant: the whole grid spans at most 0.029 ACC for SCoGF, against 0.54 for RISE on mfeat under the identical protocol (0.677 at β=100\beta{=}100 against 0.138 at β=1\beta{=}1), so our worst configuration is closer to our best than theirs is to theirs.

One fixed configuration with no labels is also reported. A single r=10r=10 across all five datasets, the grid midpoint chosen without labels, costs 0.010 ACC on average and 0.018 at most against the oracle-selected per-dataset rr, and is better than the r=5r=5 default we had written (0.013 / 0.029). Any selection rule — including the normalized cut of the partition on the consensus graph, precisely the objective Theorem 5.5 controls, or stability across mask resamples — therefore lands within 0.018 of the reported numbers. For transparency, at m/K=5m/K=5 we know of no reliable label-free selector, and we say so rather than paper over it.

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

This paper proposes a single-pass method named SCoGF for scalable spectral clustering with incomplete multi-view data. It builds per-view anchor graphs using only observed anchors, fuses them through a uniform masked average, and applies randomized spectral embedding with a missing-aware extension to cluster all samples. The anchor set is selected deterministically from samples with high view‑observation count. It avoids explicit view imputation and full N×N graph operations. It achieves near‑linear time complexity w.r.t sample size.

Critical strengths
  1. The fusion and embedding pipeline is computationally efficient and relatively simple.

  2. The evaluation is comprehensive, including diverse missingness settings and substantial baseline comparisons.

Critical weaknesses
  1. The empirical evidence for large-scale applicability is limited.

  2. The paper lacks targeted ablations to disentangle performance gains.

  3. It applies uniform equal‑weight averaging over available views, without learning view‑specific weights.

  4. Datasets used have relatively balanced cluster sizes. It is unknown whether SCoGF still maintains the worst‑case robustness under scenarios with imbalanced cluster sizes.

Questions for authors
  1. When a view has fewer than r+1 observed anchors, how is its nearest-neighbor graph constructed?

  2. Does SCoGF require the number of clusters K to be specified in advance? How sensitive are its results to a misspecified K?

3 comments
AuthorsOpenReview ↗

Response to Reviewer 48Zm (1/3): W1–W3

We thank Reviewer 1 for the positive assessment of the pipeline's efficiency and of the evaluation's coverage.

W1 — large-scale applicability. The empirical base is already broad: five benchmarks from N=210N=210 (MSRC-v5) to 10,800 (ALOI), with V=3V=3–6, K=7K=7–100 and rates to η=0.7\eta=0.7, nearly two orders of magnitude in NN. What was missing is the 10510^5 regime, and we have measured it. N7 runs YoutubeVideo (N=101,498N=101{,}498, K=31K=31, V=5V=5) through IMVC-CBG's own nine-setting protocol with nothing tuned: 25.60 ± 2.30 ACC / 20.81 ± 2.49 NMI in 380 s, the slowest of the nine settings. That is level with RISE's published 25.52 ACC and ahead of its 17.88 NMI at 900 s, and ahead of IMVC-CBG's 22.96 / 14.12 at 1168 s, at 2.4–3.1× less wall clock. The claim is about wall clock rather than anchor budget, so we report all five budgets, including m=155m{=}155 where we are behind both. The majority-class rate (26.62) exceeds the nine-rate mean ACC of every method, so NMI is the column we read. N8 isolates the cost itself: 0.37 / 0.32 / 0.33 ms per sample at 20k / 50k / 100k, linear with a flat constant. Both blocks are in Appendix I of the revised manuscript, and both tables are in the global response (G4a).

W2 — targeted ablations. The ablation the reviewer asks for is already in the paper in the form of the baseline panel, because the method is small enough that each module has a named counterpart. SCoGF adds four things to the standard anchor pipeline, and each can be removed by choosing a competitor. (i) Learned simplex anchor graphs (Stage 1): remove them and the graph is fixed, which is IMVC-CBG and LMVSC on the same anchor budget (ALOI η=0.7\eta{=}0.7: 0.552 vs 0.194 / 0.053, the largest single gap, widening with η\eta). (ii) Mask-native construction: remove it and observed entries are imputed, which is ZeroFill/Concat on identical downstream machinery (mfeat η=0.7\eta{=}0.7: 0.803 vs 0.364 / 0.346). (iii) Closed-form fusion of all views: remove it and one keeps the best single view or a kernel sum, i.e. BestSV/KernelAdd, which we beat at every η≥0.3\eta\ge0.3 on every dataset. (iv) Deterministic anchor selection: remove it and anchors are uniform draws (Appendix F: +0.19 ACC on ALOI at η=0.7\eta{=}0.7). Neighbor size r∈{5,10,15}r\in\{5,10,15\} moves ACC by at most 0.03 on any dataset (Appendix D), so it is not a tuning knob in disguise. Appendix J of the revision collects these into one attribution table. The panel can serve as the ablation because the pipeline is minimal — one kk-means, one closed-form fusion, one randomized SVD and O(N(K+dˉV))O(N(K+\bar dV)) time, with no solver, no training and no per-view weights — so there is no redundant module to strip, and the competitor lacking a given property is in the panel.

W3 — uniform averaging without learned weights. The full comparison is in the global response (G3), with its per-cell table: nine cells, 30 runs each, the three weighted rules set against the paper's printed 1/V1/V on identical masks, graphs and seeds. No rule improves on it by more than 0.007 on average in either metric, and none leads in both. Only the learned rule costs anything, since it replaces the closed-form fusion with an iterative ADMM solve. Extra computation for no measurable return is a bad trade in a method whose selling point is that it has no solver, so the released model keeps 1/V1/V: closed form, no per-dataset constant, nothing estimated from the mask, nothing learned at fit time. The four rules were designed together and run under the paper's 30-run protocol, so none of the three weighted arms is a straw man.

AuthorsOpenReview ↗

Response to Reviewer 48Zm (2/3): W4, imbalanced cluster sizes; Q1, fewer than r+1 observed anchors

W4. The theory was already imbalance-aware: πmin⁡\pi_{\min} appears explicitly in the net condition and in the budgets, so guarantees degrade polynomially in 1/πmin⁡1/\pi_{\min} rather than failing. The empirical question still needed a direct answer. N3 applies a geometric class-size ladder to a fixed-label subsample (achieved ratios 3.8 and 4.0) and reruns SCoGF, RISE, IMVC-CBG, JVILG and LMVSC on the identical subsample under the main protocol, nothing re-tuned. SCoGF leads at MSRC-v5 η=0.5\eta{=}0.5 (0.670 ± 0.050 vs RISE 0.553 ± 0.069) and on both mfeat cells (0.784 ± 0.025 / 0.723 ± 0.042 vs 0.652 ± 0.054 / 0.471 ± 0.030). At MSRC-v5 η=0.7\eta{=}0.7 the two are level (0.425 ± 0.053 vs 0.417 ± 0.060, p=0.58p{=}0.58), which we report as a tie.

Dataset (NN)η\etaSCoGFRISEIMVC-CBGJVILGLMVSC
MSRC-v5 (117)0.50.670 / 0.5820.553 / 0.4650.420 / 0.3070.335 / 0.2030.273 / 0.096
MSRC-v5 (117)0.70.425†^\dagger / 0.3270.417 / 0.2980.352 / 0.2240.297 / 0.1620.272 / 0.094
mfeat (1100)0.50.784 / 0.7570.652 / 0.5720.444 / 0.3660.197 / 0.0510.188 / 0.023
mfeat (1100)0.70.723 / 0.6550.471 / 0.4150.328 / 0.2570.183 / 0.0020.186 / 0.019
Caltech101-20 (923)0.50.534 / 0.5420.373 / 0.4120.282 / 0.2880.072 / 0.0090.082 / 0.046
Caltech101-20 (923)0.70.429 / 0.4290.241 / 0.2660.214 / 0.2280.069 / 0.0000.081 / 0.044

Table N3: 4:1 class-imbalanced subsamples, 30 paired draws per cell; ACC / NMI, best in bold. †\dagger: margin does not survive Holm correction (tie). RISE and JVILG are our re-implementations of those algorithms.

The failure behavior is more informative. On Caltech101-20 at η=0.7\eta{=}0.7 JVILG returns a bit-identical partition across all thirty draws (sd 0.000), and on mfeat it moves by only 0.014 between η=0.5\eta{=}0.5 and 0.7 while LMVSC stays flat. Neither responds to the mask once the class prior is skewed, whereas SCoGF still tracks it (0.784 → 0.723). Because the subsample also shrinks NN, only within-subsample comparison is valid, which is what N3 reports; the block is in Appendix I.

Q1. The revision states the case in Algorithm 1 and §4: the effective neighborhood size is ri(v)=min⁡(r,∣O(v)∣−1)r^{(v)}_i=\min(r,|O^{(v)}|-1), and a view with ∣O(v)∣≤1|O^{(v)}|\le1 contributes only its self-loop S(v)=diag(m(v))S^{(v)}=\mathrm{diag}(m^{(v)}) and no off-diagonal mass. No result changes, because the rule is a definition rather than an assumption: every theorem uses only per-view coverage and the anchor-net condition, and truncating at ∣O(v)∣−1|O^{(v)}|-1 keeps the self-loop mass, so the fusion minimizer of Proposition 5.2 and the bounds that follow are untouched.

N10a is the observed-anchor audit (the paper's Table 26): across the full 0.0–0.9 sweep on four benchmarks under both anchor rules no view-cell truncates — zero of the audited view–run pairs — and the worst view at η=0.9\eta{=}0.9 still carries 24 observed anchors against the r+1=16r{+}1{=}16 its neighborhood needs. The branch is a safety net, not something the reported numbers rest on. N10b answers the underlying question by force. Sweeping rr up to 150 on N=210N=210 (r=0.71Nr=0.71N) at η=0.9\eta{=}0.9 makes reffr_{\mathrm{eff}} pin at ∣O(v)∣−1|O^{(v)}|-1. ACC enters a plateau exactly at the pin (Δ\Delta +0.005 / −0.0008), the spread stays at 0.021–0.034, the same magnitude as unpinned settings, and there is no divergence and no collapse to a trivial partition. Over-running rr does cost accuracy smoothly, 0.353 at r=5r{=}5 against 0.223 at r=200r{=}200 on mfeat, which is why rr is selected once per dataset.

Datasetrrreffr_{\mathrm{eff}}, k-meansACCreffr_{\mathrm{eff}}, uniformACC
MSRC-v5 (N=210N{=}210)55.00.2915.00.284
1515.00.28515.00.289
3029.60.27130.00.281
5034.9 (pinned)0.27644.50.265
8034.90.27644.7 (pinned)0.265
15034.90.27644.70.265
mfeat (N=2000N{=}2000)55.00.3535.00.327
2020.00.25720.00.237
8079.90.22479.90.216
20095.8 (pinned)0.22393.2 (pinned)0.215

Table N10(b): forcing the truncation branch, η=0.9\eta{=}0.9, six paired draws per (rr, anchor rule); every column is SCoGF. The two blocks differ only in how anchors are drawn (deterministic kk-means vs uniform). Part (a) is the occupancy audit in the paragraph above.

AuthorsOpenReview ↗

Response to Reviewer 48Zm (3/3): Q2, is K required in advance, sensitivity to a misspecified K

Two things are worth separating. First, a misspecified KK reproduces the paper's own ordering rather than a new failure. On Caltech101-20 JVILG already leads at the true KK (0.628 vs our 0.461, the paper's Table 1), so its leading at K/2K/2 and 2K2K is what that table predicts; what our 2K2K cell adds is the size of our own degradation, 0.126 / 0.110 ACC at η=0.5/0.7\eta{=}0.5/0.7 against its 0.020 / 0.032. Second, where we are the published leader the ordering does not move: with KK at K/2K/2 or 2K2K SCoGF is first in all 12 cells on MSRC-v5 and mfeat (eleven significantly, mfeat K=20K{=}20 a tie), and its degradation there is concave and centred on the true KK, since too small merges clusters and too large splits them; even its worst misspecified cell (MSRC-v5, K=3K{=}3 at η=0.7\eta{=}0.7, 0.365) clears the best competitor (0.330).

η\etaKKSCoGFRISEIMVC-CBGJVILGLMVSC
MSRC-v5 (true K=7K{=}7)
0.530.413 / 0.4680.366 / 0.3230.303 / 0.1700.178 / 0.0480.152 / 0.020
0.57⋆7^\star0.733 / 0.6370.568 / 0.4870.416 / 0.2840.155 / 0.0150.166 / 0.055
0.5140.497 / 0.5800.412 / 0.4530.353 / 0.3280.155 / 0.0130.172 / 0.108
0.730.365 / 0.3090.330 / 0.2480.246 / 0.1010.222 / 0.0700.152 / 0.019
0.77⋆7^\star0.524 / 0.4100.449 / 0.3520.334 / 0.2140.223 / 0.0860.165 / 0.054
0.7140.395 / 0.4380.364 / 0.3420.297 / 0.2780.223 / 0.0970.171 / 0.108
mfeat (true K=10K{=}10)
0.550.481 / 0.6790.434 / 0.4700.293 / 0.2840.392 / 0.5420.130 / 0.068
0.510⋆10^\star0.831 / 0.8080.763 / 0.6860.453 / 0.3780.538 / 0.6560.206 / 0.216
0.5200.581†^\dagger / 0.7240.579 / 0.6620.334 / 0.3580.407 / 0.5880.326 / 0.369
0.750.467 / 0.6070.353 / 0.2760.218 / 0.1840.205 / 0.2520.102 / 0.004
0.710⋆10^\star0.803 / 0.7210.549 / 0.4660.306 / 0.2520.194 / 0.2560.103 / 0.010
0.7200.553 / 0.6480.447 / 0.5070.252 / 0.2620.200 / 0.2600.105 / 0.021
Caltech101-20 (true K=20K{=}20)
0.5100.522 / 0.5150.515 / 0.4280.437 / 0.3000.625 / 0.6750.338 / 0.015
0.520⋆20^\star0.461 / 0.5400.483 / 0.4600.372 / 0.2920.628 / 0.7260.352 / 0.047
0.5400.335 / 0.5330.467 / 0.4790.354 / 0.2940.608 / 0.6920.404 / 0.159
0.7100.491 / 0.4610.406 / 0.2890.326 / 0.2140.589 / 0.6340.337 / 0.011
0.720⋆20^\star0.392 / 0.4690.371 / 0.3080.298 / 0.2260.577 / 0.6340.339 / 0.022
0.7400.282 / 0.4630.370 / 0.3280.268 / 0.2410.545 / 0.5740.341 / 0.042

Table N2: 30 paired draws per cell; ACC / NMI, best in bold. ⋆\star marks the six rows at the true KK, quoted verbatim from the paper's Table 1 and its per-dataset appendix tables under the same protocol, so the K/2K/2 and 2K2K rows read as a perturbation of the published numbers; every other row is a new paired rerun. †\dagger: margin does not survive Holm correction (tie). RISE and JVILG are our re-implementations.

The theory says why the cost is bounded: the guarantees hold for any working value K′K' with the eigengap δK′\delta_{K'} in place of δK\delta_K, so misspecification costs accuracy while the K′K'-th eigengap stays positive. The bounded statement is that halving or doubling KK costs little where we lead and materially where we do not, and that the failure mode is a ranking change under over-specification, not instability. A second failure mode appears in the learned-weight baselines at the true KK itself — JVILG 0.155 and LMVSC 0.166 ACC with NMI at 0.015 and 0.055 on MSRC-v5, i.e. near-trivial partitions, which SCoGF does not exhibit. On the label-free side we have no positive result to report: reading KK off as the largest eigengap of the consensus graph returns K=2K{=}2 on MSRC-v5 at every missing rate (η=0.3/0.5/0.7\eta{=}0.3/0.5/0.7) against a true K=7K{=}7, and the peak is shallow (largest gap 3.253.25–4.09×4.09\times the mean gap), so we keep KK as an input and claim only that the drop-first rule needs the top K+1K+1 components.

Comments on the paper

5 comments
AuthorsOpenReview ↗

Global response (1/5): what changed, the protocol, and the index of experiments

We thank the four reviewers. Four concerns recur across the reports: (i) the gap between the theory and the pipeline that is implemented (R2, R4); (ii) the restriction of the theory to MCAR missingness (R2, R4); (iii) uniform fusion without learned view weights (R1, R4); (iv) the breadth of the evidence (R1–R4). Below we take them as G1–G4, then answer each point in turn.

Two things changed: the theory was repaired so its guarantees cover the implemented algorithm, and eleven experiment blocks were run under the paper's own protocol. Across the 36 new cells of N2–N6, SCoGF is best in 24 (22 significantly, 2 by a tie) and behind in 12. Ten of those twelve are on Caltech101-20, where a competitor already leads at the published operating point (the paper's Table 1: JVILG 0.628 against our 0.461 at η=0.5\eta{=}0.5). The one genuine robustness gap is KK over-specification on the same benchmark. It is stated as a limitation, not averaged away. The revised manuscript accompanies this response; all changes are marked in blue.

#Experiment (one variable changed)Key resultAnswers
N1Weighting: three weighted rules against the paper's printed 1/V1/V, 9 cells × 30 runsno rule moves either metric by more than 0.007 on average (closest: the mask prior, +0.0017 ACC / +0.0067 NMI); two are closed-form and cost nothing extra, the learned one an iterative solve, so the simplest rule is keptR1-W3, R4-W4/Q3
N2KK set to K/2K/2 and 2K2K, 18 cellsfirst in all 12 cells on MSRC-v5 and mfeat (11 significant, 1 tie); on Caltech101-20 JVILG leads at every KK, and our 2K2K drop is steeper than its ownR1-Q2
N34:1 class-imbalanced subsamples, 6 cellsfirst in all 6 (5 significant, 1 tie), +0.117 to +0.252; on Caltech101-20, otherwise a loss, +0.161/+0.188 at 30/30R1-W4
N4Cluster-dependent (MNAR) masks, 2 mechanisms, 6 cellsfirst in 4 of 6, +0.120 to +0.204; on Caltech101-20 JVILG leads by 0.21/0.27R2-W1, R4-W5/Q4
N5Nominal η=0.9\eta=0.9, one-view guarantee active, 3 benchmarksfirst on mfeat by 0.055; 0.065 behind RISE on MSRC-v5; fifth on Caltech101-20 ACC, first on NMIR2-Q1
N6True η=0.9\eta=0.9, guarantee removed, 3 benchmarksfirst on mfeat by 0.036; third on MSRC-v5; fifth on Caltech101-20 ACC, first on NMIR2-Q1, R4-W5
N7YoutubeVideo, N=101,498N=101{,}498, IMVC-CBG's protocol25.60 ACC / 20.81 NMI in 380 s at the 1.5% budget (the slowest of the nine settings), against RISE 25.52/17.88 at 900 s and IMVC-CBG 22.96/14.12 at 1168 sR1-W1, R3-W1, R4-W5
N8Synthetic scale, NN from 20k to 100k0.32–0.37 ms/sample, linearR1-W1, R3-W1
N9Per-stage runtime breakdown, 8 cellscost tracks observed data, not NNR4-W7
N10Truncation branch: (a) observed-anchor audit, four benchmarks × five rates × both anchor rules (the paper's Table 26); (b) forced sweep to r=0.71Nr=0.71N(a) never fires as configured (worst cell 24 vs 16); (b) truncation pins, ACC plateaus, no instabilityR1-Q1, R2-W2, R4-W2/Q2
N11Deep methods on YoutubeVideo, five published entries vs oursfour of the five deep entries in 25.0–29.4 ACC at V=3V{=}3 with complete views, the fifth at 15.57; ours 25.60 at V=5V{=}5 with 10–90% missing, inside that spanR3-W2

Table Index: one variable per row; the per-cell numbers for each block are in the table of the same name.

Protocol. Every new experiment holds §6.1 fixed: m=min⁡(500,N)m=\min(500,N), the frozen per-dataset rr, λz=0.01\lambda_z=0.01, deterministic kk-means anchors. Only the named variable changes, nothing is re-tuned on the reported cell, and the same mask draws are reused across methods within a cell. Each cell is therefore a paired comparison at n=30n{=}30, as in the paper's Table 1. Where a cell differs from the printed mean by anchor-draw spread, the note under the table says so. Two exceptions: N7 follows IMVC-CBG's published YoutubeVideo protocol (five anchor budgets, one draw per (m,ε)(m,\varepsilon), SCoGF only, competitors quoted from the literature), and N9–N10 are timing and deterministic diagnostics, where repetition does not apply.

RISE and JVILG released no code that runs this protocol when the panels were built, so in N2–N6 both are our re-implementations from the published descriptions, flagged in the table notes, not the authors' binaries. In N7 they appear as the literature values their papers report, not as our runs. N1 is a design block rather than a comparison against a competitor: its three weighted arms are run in-house on the same masks at 30 runs and read against the paper's printed 1/V1/V column. Significance is a paired Wilcoxon test on per-run differences against the best baseline, Holm-corrected per table, with †\dagger marking a cell whose margin does not survive correction and is read as a tie.

AuthorsOpenReview ↗

Global response (2/5): G1, the theory now covers the implemented pipeline; G2, non-random missingness

G1. The gap is that the guarantees were proved for a stylized pipeline; each item below closes one component.

(i) End-to-end, as implemented (R4-W1/Q1). A new row-geometry proposition (Appendix A) shows that the realized embedding F=rowL2(C~UK)F=\mathrm{rowL2}(\widetilde C U_K) places every non-boundary sample on exactly the ray of the ideal extended-graph spectral embedding. The end-to-end theorem (now Theorem 5.5) therefore bounds the partition Algorithm 1 returns, with the boundary term O(K(dˉ(εa+εr)/Δsep+τ−2))O(K(\bar d(\varepsilon_a+\varepsilon_r)/\Delta_{\mathrm{sep}}+\tau^{-2})) added explicitly.

(ii) Deterministic anchors (R2-W2, R4-W2/Q2). Assumption 3(a) is now a deterministic anchor-net condition: an εa\varepsilon_a-net per cluster-view cell plus a per-cluster quota. Uniform draws satisfy it with high probability, and quantization rules of bounded radius satisfy it deterministically. The implemented kk-means rule belongs to the second class, and the quota is verified per class at every rate (N10a). (iii) MNAR (R2-W1): Theorem 5.4, next. (iv) Uniform fusion (R1-W3, R4-W3/Q3): Proposition 5.2 plus N1. (v) Edge cases (R1-Q1): the neighborhood rule of N10. All proofs are in Appendix A of the revised manuscript.

G2. Theorem 5.4: under cluster-dependent missingness, Pr⁡(oi(v)=1∣i∈cluster k)=1−ηv,k\Pr(o^{(v)}_i=1\mid i\in\text{cluster }k)=1-\eta_{v,k}, the masked average acquires a block-constant scale ρˉkℓ=1V∑v(1−ηv,k)(1−ηv,ℓ)\bar\rho_{k\ell}=\frac1V\sum_v(1-\eta_{v,k})(1-\eta_{v,\ell}). Degree normalization cancels ρˉkk\bar\rho_{kk} blockwise, so the normalized adjacency, and with it the stability and consistency guarantees, is unchanged; only the coverage floors worsen. The failure boundary is exact: within-cluster feature-dependent missingness breaks block-constancy, and then only the coverage statement survives.

N4 tests two mechanisms of this family, with rates that are a function of the class (half the classes at η=0.8\eta{=}0.8, half at 0.20.2; and one rate per class ramped 0.2→0.80.2\to0.8). SCoGF leads all four cells on MSRC-v5 and mfeat by +0.120+0.120 to +0.204+0.204 ACC at 30/3030/30 draws, while the competitors degrade or collapse. On Caltech101-20 the ordering is that of the paper's Table 1, with JVILG ahead. We therefore read N4 as a lower bound on the damage, not a robustness claim.

Mask, datasetrealized η\etaSCoGFRISEIMVC-CBGJVILGLMVSC
(a) block, MSRC-v50.5050.575 / 0.4680.343 / 0.4070.371 / 0.3040.157 / 0.0190.171 / 0.083
(a) block, mfeat0.4770.768 / 0.7170.557 / 0.6320.404 / 0.4240.573 / 0.6570.390 / 0.473
(a) block, Caltech101-200.6090.426 / 0.4890.495 / 0.4170.348 / 0.2900.634 / 0.7170.351 / 0.070
(b) ramp, MSRC-v50.4830.672 / 0.5800.481 / 0.4790.421 / 0.3170.161 / 0.0230.161 / 0.063
(b) ramp, mfeat0.4890.805 / 0.7640.685 / 0.6650.465 / 0.4160.559 / 0.6750.328 / 0.415
(b) ramp, Caltech101-200.3500.371 / 0.4840.449 / 0.5340.464 / 0.3680.642 / 0.7360.466 / 0.429

Table N4: cluster-dependent (MNAR) masks, 30 paired draws per cell at the realized marginal rate shown; ACC / NMI, best in bold. RISE and JVILG are our re-implementations of those algorithms (see the protocol paragraph in the previous comment).

AuthorsOpenReview ↗

Global response (3/5): G3, uniform fusion in theory and against three weighted rules

The three weighted variants of N1 — a missing-rate prior, an R2R^2 price, and an ADMM rule that updates α\alpha against the per-view residual — were built before the uniform average, which entered as the control arm. The runs settle it: the weights return nothing measurable, one of the three costs computation, and we keep the simplest rule.

N1 holds the data fixed rather than the hyperparameter: nine cells (three benchmarks × three missingness settings) × 30 runs, one anchor draw and one Stage-1 graph per cell shared across arms, so α\alpha is the only variable. The left column is the paper's printed mean; the three weighted columns are our runs.

DatasetMissingnesspaper 1/V1/VR2R^2 pricemask priorlearned
ACC
Caltech101-20η=0.5\eta{=}0.50.4610.4320.4410.444
η=0.7\eta{=}0.70.3920.3850.3870.393
view-dep.0.4940.4790.4980.502
mfeatη=0.5\eta{=}0.50.8310.8160.8220.826
η=0.7\eta{=}0.70.8030.7820.7830.792
view-dep.0.8480.8430.8390.855
MSRC-v5η=0.5\eta{=}0.50.7330.7210.7330.697
η=0.7\eta{=}0.70.5240.5900.5930.573
view-dep.0.7670.7680.7710.768
Mean Δ\Delta vs paper−0.0041+0.0017−0.0003
Cells ahead of paper2/94/95/9
NMI
Caltech101-20η=0.5\eta{=}0.50.5400.5260.5420.538
η=0.7\eta{=}0.70.4690.4620.4730.471
view-dep.0.5860.5770.5920.595
mfeatη=0.5\eta{=}0.50.8080.7960.8090.810
η=0.7\eta{=}0.70.7210.7060.7120.709
view-dep.0.8470.8400.8420.852
MSRC-v5η=0.5\eta{=}0.50.6370.6230.6360.593
η=0.7\eta{=}0.70.4100.4650.4690.449
view-dep.0.7000.6980.7040.692
Mean Δ\Delta vs paper−0.0028+0.0067−0.0010
Cells ahead of paper1/96/95/9

Table N1: ACC (upper panel) and NMI (lower panel) under four weight rules. The left column is the paper's own 1/V1/V configuration, quoted as printed (the paper's Table 1 for ACC, the per-dataset appendix tables for NMI, means over 30 trials). The three right-hand columns are our runs under the paper's protocol, one anchor draw and one Stage-1 graph per cell shared across the three arms. The Δ\Delta rows are differences against the printed equal-weight value; Cells ahead counts the cells where a weighted rule exceeds it. Complete-data cells are omitted, since no view is missing there and the weighting question does not arise.

The comparison is flat. No rule moves either metric by more than 0.007 on average; the closest is the mask prior, at +0.0017 ACC and +0.0067 NMI, while the R2R^2 price, which prices a view by how well the anchor graph reconstructs it, is behind in both. The largest gaps fall on MSRC-v5 (+0.069 ACC and −0.044 NMI) and change sign across its cells, which is what anchor-draw spread looks like, not a weight effect: a re-run of the equal-weight arm on the same masks lands on the same side of the printed value there (+0.071 ACC, +0.059 NMI), on the smallest benchmark in the panel. Only the learned rule adds computation, replacing the closed-form fusion with an iterative ADMM solve. Extra machinery buys no measurable accuracy, so we ship 1/V1/V: closed form, no per-dataset constant, nothing estimated from the mask, and the widest margin over the iterative baselines.

No fixed weighting can help, and Proposition 5.2 gives the reason. For data-independent weights, E[Gw,ij]=(∑vwvqv)sij⋆\mathbb{E}[G_{w,ij}]=(\sum_v w_v q_v)s^\star_{ij} differs from the uniform average only by a pair-independent scale that degree normalization annihilates. Where noise inflates inversely with coverage, σv2=σ02/qv\sigma_v^2=\sigma_0^2/q_v — the regime Stage-1 graphs live in — uniform is the unique variance minimizer over the simplex. The one case with room for a non-uniform rule is the decoupled case of Proposition 5.2(iii), whose optimum is wv∝1/qvw_v\propto 1/q_v; even there the excess over uniform is bounded by the AM–HM ratio [1V∑vqv][1V∑v1/qv]\big[\frac1V\sum_v q_v\big]\big[\frac1V\sum_v 1/q_v\big].

A global coefficient is also the wrong granularity. It can only rescale the fused graph, and Stage 3's degree normalization removes a positive scale exactly, so on a single-view sample it has nothing to act on; where a sample keeps several views, unequal α\alpha leaves the fused mass unchanged and only lowers the effective number of contributing views, (∑vαv)2/∑vαv2(\sum_v\alpha_v)^2/\sum_v\alpha_v^2. The identifiable axis is per pair, and the mask already acts there.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.