acceptodds
Under review as a conference paper at ICLR 2027

High-Order Consensus Completion for Incomplete Contrastive Multi-View Clustering

Abstract

Incomplete contrastive multi-view clustering aims to learn discriminative representations from incomplete multi-view data. However, existing methods still have two issues: 1) Most imputation-based methods mainly rely on local cross-view relations for missing-view recovery, while neglecting high-order relationships among samples, which may lead to unreliable completion. 2) View incompleteness obscures the latent relationships among samples, making it difficult to expand reliable positive pairs beyond same-sample cross-view pairs. To address these issues, we propose a framework named high-order consensus completion for incomplete contrastive multi-view clustering (HCCIMC). Specifically, we design a high-order consensus completion module, which first constructs a global consensus graph from view-specific bipartite graphs. Then, multi-order random walks are performed on the consensus graph to derive high-order neighborhood structures, which are adaptively combined to recover missing-view representations. Furthermore, we propose a multi-order neighborhood consistency contrastive learning module. It models multi-order neighborhood relationships and evaluates their consistency across different views to select reliable neighborhood samples as positives. These two modules mutually enhance each other and help learn robust clustering-friendly representations. Extensive experimental results demonstrate that our method achieves the state-of-the-art clustering performance.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
Incomplete Multi-View Clustering, Contrastive Learning, High-Order Neighborhood Information, Missing-View Completion

Reviews

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

This paper proposes HCCIMC, a framework for incomplete contrastive multi-view clustering. It constructs a global consensus graph and aggregates multi-order random-walk representations to recover missing-view features. A neighborhood consistency contrastive learning module further selects reliable positive pairs using cross-view structural agreement. Experiments on four benchmark datasets demonstrate competitive clustering performance under different missing rates, supported by ablation and sensitivity analyses.

Critical strengths
  1. The paper addresses two important challenges in incomplete multi-view clustering: unreliable missing-view completion and insufficient positive-pair supervision. The proposed framework establishes a clear connection between these problems.
  2. The integration of high-order consensus propagation and cross-view neighborhood consistency is technically meaningful, enabling the exploitation of structural relationships for representation learning.
  3. Experiments across four datasets and multiple missing rates demonstrate strong clustering performance. The ablation and parameter sensitivity analyses further support the effectiveness of the main components.
Critical weaknesses
  1. The methodological novelty is somewhat limited, as high-order graph propagation and neighborhood-based contrastive learning have been explored in prior studies. The distinction from closely related approaches is not sufficiently established.
  2. The paper lacks direct evaluation of missing-view completion quality and positive-pair reliability, making it difficult to verify the effectiveness of the proposed high-order consensus mechanisms.
  3. The framework involves quadratic computational complexity with respect to the number of samples, but practical runtime, memory consumption, and scalability are not adequately evaluated.
Questions for authors
  1. Could the authors further clarify the methodological differences between HCCIMC and existing high-order graph propagation approaches, particularly their respective contributions to missing-view recovery?
  2. Could the authors provide direct evaluations of completion accuracy and positive-pair precision to substantiate the reliability of the proposed mechanisms?
  3. Could the authors provide runtime and memory comparisons with representative baselines to demonstrate the scalability of the proposed framework?
2 comments

W1: Methodological differences from existing high-order graph propagation approaches.

Thank you for raising this important question. We emphasize that higher-order propagation is not inherently more reliable, as increasing the propagation order may also introduce noisy or misleading structural relationships. Therefore, rather than simply relying on higher-order information, HCCIMC introduces an observation-constrained multi-order calibration mechanism specifically designed for missing-view recovery.

Specifically, HCCIMC first integrates cross-view consensus and view-specific structures to generate complementary multi-order representations through random walks. More importantly, instead of directly aggregating these representations or assigning fixed propagation weights, HCCIMC introduces an observation-constrained objective (Eq. (10)) to adaptively learn the contribution of each propagation order by minimizing the reconstruction discrepancy on observed samples. Ridge and entropy regularization further stabilize the optimization. The learned weights are then transferred to missing samples to recover their representations (Eq. (11)). Therefore, HCCIMC uses observed representations as explicit calibration references to determine how multi-order structural information contributes to missing-view recovery.

W2: Direct evaluation of completion accuracy and positive-pair precision.

Thank you for this valuable suggestion. To directly evaluate the reliability of HCCM, we measure the similarity between recovered representations and their original counterparts exclusively on masked sample-view pairs, without involving subsequent encoding or contrastive learning. Specifically, we report Cosine Similarity, MAE, and MSE on MSRA-6view and Hdigit under four missing rates (0.1, 0.3, 0.5, and 0.7).

Importantly, HCCM is not intended to exactly reconstruct the original view data, but rather to infer high-quality missing-view representations that preserve meaningful structural information and cross-view consistency for downstream clustering. Therefore, whether the original views can be reconstructed is not an appropriate criterion for evaluating our method, as view reconstruction is not our objective.

Table 1. Direct evaluation of HCCM completion quality under different missing rates.

DatasetMissing RateCosine Similarity ↑MAE ↓MSE ↓
MSRA-6view0.10.89020.10510.0233
MSRA-6view0.30.88690.10710.0249
MSRA-6view0.50.87900.11220.0277
MSRA-6view0.70.88310.12520.0341
Hdigit0.10.69390.18780.0825
Hdigit0.30.69030.18560.0841
Hdigit0.50.68720.18340.0876
Hdigit0.70.67800.18250.0969

The results show that HCCM maintains relatively stable representation similarity across different missing rates. Although reconstruction errors generally increase with more severe incompleteness, the recovered representations retain substantial similarity to their original counterparts.

Table 2. Average multi-order positive-pair precision on MSRA-6view under different missing rates.

DatasetMissing RateMulti-order Pair Precision (%)
MSRA-6view0.192.26
MSRA-6view0.389.70
MSRA-6view0.584.68
MSRA-6view0.781.00
Average—86.91

To quantify positive-pair precision, we first construct multi-order neighborhood sets independently for each view, combining first-order and higher-order neighbors. We then obtain the cross-view consistent positive-pair set by taking the intersection of the neighborhood sets from two views. For evaluation, we exclude self-pairs and compare the selected sample pairs against their ground-truth labels. A pair is considered correct if the two samples share the same class label. Positive-pair precision is calculated as the ratio of correctly selected pairs to all selected pairs.

The results show that the proposed multi-order positive-pair selection mechanism maintains high semantic precision across different missing rates. Although the precision gradually decreases as the missing rate increases, it remains above 81% even under 70% missingness. This indicates that the cross-view consistency constraint effectively identifies semantically reliable positive pairs despite substantial view incompleteness, supporting the effectiveness of the proposed MNCCL mechanism.

W3: Scalability and computational efficiency.

Thank you for raising these important concerns. To further evaluate the scalability of HCCIMC, we conducted additional experiments on two larger-scale datasets, NoisyMNIST and CIFAR10, containing 70,000 and 50,000 samples, respectively.

We acknowledge that graph-based methods may incur considerable computational and memory overhead, particularly when constructing dense sample-wise affinity matrices and performing repeated graph operations. This limitation was also observed in our practical evaluations. Specifically, Mask-IMvC and GHICMC encountered out-of-memory (OOM) errors when processing NoisyMNIST. For reference, a single dense 70,000 × 70,000 float32 matrix requires approximately 18.25 GiB of GPU memory. We also observed substantial runtime overhead in SCVT, where its 500-epoch alignment stage required approximately 18 hours.

To address these computational challenges, we adopt a memory-efficient sparse graph construction and propagation strategy in our large-scale implementation, which consists of three key operations:

(1) Chunk-wise Similarity Computation. We divide the similarity computation process into chunks of 512 samples, avoiding the simultaneous allocation of the entire dense pairwise similarity matrix and thereby reducing peak GPU memory consumption.

(2) Top-K Neighborhood Sparsification. We retain only the Top-10 nearest neighbors for each sample and discard the remaining connections, constructing sparse neighborhood graphs whose storage requirements scale approximately linearly with the number of samples.

(3) Sparse Graph Representation and GPU-based Propagation. We use sparse representations for subsequent consensus graph construction and multi-order information propagation, avoiding unnecessary dense matrix operations and reducing downstream memory and computational costs.

Table 1. Clustering performance comparison on NoisyMNIST under different missing rates.

MethodA(.1)N(.1)R(.1)A(.3)N(.3)R(.3)A(.5)N(.5)R(.5)A(.7)N(.7)R(.7)
DCP0.98710.96080.97180.79060.86320.78180.77850.83540.75850.84080.81670.7819
CPSPAN0.55970.59060.44090.62740.59930.46540.64920.62190.50600.53950.58900.4466
DVIMC0.98250.95240.96200.92200.88350.86230.94750.87650.88940.91890.82970.8329
RPCIC0.86970.76750.74460.76150.66970.61960.53860.49600.40330.26080.21150.0951
Mask-IMvCO/MO/MO/MO/MO/MO/MO/MO/MO/MO/MO/MO/M
HSACC0.98960.96790.97710.95810.92330.93800.92550.85920.85500.88890.79050.7773
GHICMCO/MO/MO/MO/MO/MO/MO/MO/MO/MO/MO/MO/M
Ours0.99060.97050.97940.97820.93860.95270.96250.90330.91970.94210.86090.8777

Note: A, N, and R denote ACC, NMI, and ARI, respectively

Table 2. Training time of HCCIMC on NoisyMNIST under different missing rates.

Missing RatePre-train (s)Contrastive (s)Total (s)
0.13725648410215
0.34126659410725
0.53842688710735
0.74183702811216

Overall, our additional experiments demonstrate that HCCIMC can effectively handle large-scale incomplete multi-view data. The proposed sparse computation strategies alleviate memory consumption and computational overhead, improving its practical scalability. Experiments on CIFAR-10 are still ongoing, and the results will be reported once completed.

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

The paper addresses deep incomplete multi-view clustering (DIMVC) and targets two specific failure modes: (i) missing-view completion that relies only on local cross-view relations and therefore produces unreliable recovered representations, and (ii) contrastive positive-pair construction that becomes unreliable when view incompleteness destroys cross-view correspondences and neighborhood structure. The proposed framework, HCCIMC, contains two modules. The High-Order Consensus Completion Module (HCCM) builds view-specific bipartite anchor graphs, aggregates them into a global consensus affinity graph, constructs per-view transition matrices from the consensus and view-specific affinities, propagates latent representations through multi-step random walks, and learns propagation-order weights by an observation-constrained calibration objective on the observed samples only; the missing rows are then filled by the weighted multi-order combination. The Multi-Order Neighborhood Consistency Contrastive Learning module (MNCCL) builds first-order KNN graphs and higher-order graphs via Jaccard similarity over neighbor sets, takes their union per view, and retains as positives only pairs whose neighbor relation is consistent across views.

Critical strengths

The paper is competently executed and the two modules are individually sensible; the TwoMoon illustration of order-dependent cross-class edge reduction is a nice motivation.

  1. This paper proposes a high-order consensus completion mechanism that constructs a global consensus graph from view-specific bipartite structures and adaptively aggregates high-order neighborhood structures for reliable missing-view representation completion.

  2. The authors propose a multi-order neighborhood consistency contrastive learning strategy that integrates first- and high-order neighborhood relations and verifies their cross-view consistency to select reliable positive pairs.

Critical weaknesses
  1. The sensitivity analysis is incomplete. Section 4.4 reports sensitivity to alphaalpha, betabeta amd TT, butt the method's own objective in Eq. (10) uses λ\lambda, gammagamma, and Section 4.4 does not mention them.
  2. A larger-scale benchmark dataset should be added to the comparative experiments to prove the capacity of proposed method on practical applications
Questions for authors

see above.

2 comments
AuthorsOpenReview ↗

Response to Reviewer Comments: Sensitivity Analysis and Scalability

W1: Incomplete sensitivity analysis.

Thank you for pointing this out. We would like to clarify that the sensitivity analyses of the regularization coefficients λ\lambda and γ\gamma have already been conducted and included in the supplementary material. Specifically, as presented in Appendix A.4 (Figure 10, Page 15), we evaluate λ\lambda in the range [0.0001,1.0][0.0001, 1.0] and γ\gamma in the range [0.1,1.0][0.1, 1.0] on the MSRC-V1 dataset under different missing rates. The results show that HCCIMC maintains relatively stable clustering performance across most parameter combinations. Based on these results, we adopt λ=0.01\lambda=0.01 and γ=0.5\gamma=0.5 as the default settings. We will also examine the sensitivity of λ\lambda and γ\gamma on the additional datasets to further evaluate their robustness and generalizability across different datasets.

Furthermore, we have conducted an ablation study to evaluate the effectiveness of these regularization terms. The corresponding results are presented in Appendix A.5 (Figure 11, Page 15) of the supplementary material, and the quantitative results under four missing rates are reported below. The results show that incorporating the regularization terms consistently improves overall clustering performance across all missing rates

Missing Ratew/o Regularizationw/ RegularizationImprovement
0.170.4973.38+2.88
0.368.9469.94+1.00
0.564.9967.65+2.66
0.762.4863.40+0.92

W2: Lack of large-scale benchmark datasets.

Thank you for this valuable suggestion. We are conducting additional experiments on two larger-scale multi-view benchmarks, CIFAR-10 and Noisy MNIST. CIFAR-10 contains 50,000 samples with three views (512/ 2048/1024), while Noisy MNIST contains 70,000 samples with two views (784/784). The experimental results and corresponding analyses will be added to the supplementary material once the experiments are completed.

AuthorsOpenReview ↗

W2: Lack of large-scale benchmark datasets.

We acknowledge that graph-based methods may incur considerable computational and memory overhead, particularly when constructing dense sample-wise affinity matrices and performing repeated graph operations. This limitation was also observed in our practical evaluations. Specifically, Mask-IMvC and GHICMC encountered out-of-memory (OOM) errors when processing NoisyMNIST. For reference, a single dense 70,000 × 70,000 float32 matrix requires approximately 18.25 GiB of GPU memory. We also observed substantial runtime overhead in SCVT, where its 500-epoch alignment stage required approximately 18 hours.

To address these computational challenges, we adopt a memory-efficient sparse graph construction and propagation strategy in our large-scale implementation, which consists of three key operations:

(1) Chunk-wise Similarity Computation. We divide the similarity computation process into chunks of 512 samples, avoiding the simultaneous allocation of the entire dense pairwise similarity matrix and thereby reducing peak GPU memory consumption.

(2) Top-K Neighborhood Sparsification. We retain only the Top-10 nearest neighbors for each sample and discard the remaining connections, constructing sparse neighborhood graphs whose storage requirements scale approximately linearly with the number of samples.

(3) Sparse Graph Representation and GPU-based Propagation. We use sparse representations for subsequent consensus graph construction and multi-order information propagation, avoiding unnecessary dense matrix operations and reducing downstream memory and computational costs.

Table 1. Clustering performance comparison on NoisyMNIST under different missing rates.

MethodA(.1)N(.1)R(.1)A(.3)N(.3)R(.3)A(.5)N(.5)R(.5)A(.7)N(.7)R(.7)
DCP0.98710.96080.97180.79060.86320.78180.77850.83540.75850.84080.81670.7819
CPSPAN0.55970.59060.44090.62740.59930.46540.64920.62190.50600.53950.58900.4466
DVIMC0.98250.95240.96200.92200.88350.86230.94750.87650.88940.91890.82970.8329
RPCIC0.86970.76750.74460.76150.66970.61960.53860.49600.40330.26080.21150.0951
Mask-IMvCO/MO/MO/MO/MO/MO/MO/MO/MO/MO/MO/MO/M
HSACC0.98960.96790.97710.95810.92330.93800.92550.85920.85500.88890.79050.7773
GHICMCO/MO/MO/MO/MO/MO/MO/MO/MO/MO/MO/MO/M
Ours0.99060.97050.97940.97820.93860.95270.96250.90330.91970.94210.86090.8777

Note: A, N, and R denote ACC, NMI, and ARI, respectively

Table 2. Training time of HCCIMC on NoisyMNIST under different missing rates.

Missing RatePre-train (s)Contrastive (s)Total (s)
0.13725648410215
0.34126659410725
0.53842688710735
0.74183702811216

Overall, our additional experiments demonstrate that HCCIMC can effectively handle large-scale incomplete multi-view data. The proposed sparse computation strategies alleviate memory consumption and computational overhead, improving its practical scalability. Experiments on CIFAR-10 are still ongoing, and the results will be reported once completed.

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

This work addresses incomplete contrastive multi‑view clustering. The proposed HCCIMC includes two jointly‑trained core modules. HCCM constructs a global consensus graph and leverages multi‑order random walks with observation‑constrained calibration to adaptively recover missing‑view representations. MNCCL combines first‑ and high‑order neighborhood cues and applies cross‑view consistency to filter trustworthy positive pairs for contrastive learning. Comprehensive experiments across several benchmarks, including ablation, sensitivity, visualization and convergence analyses, demonstrate its competitive clustering performance.

Critical strengths

Motivations target two real pain‑points of incomplete multi‑view clustering: imputation relies too much on local pairwise relations; contrastive positive sampling degrades under view missing.

Experiments cover imputation‑free & imputation‑based SOTAs across four datasets under multiple missing ratios. Ablation, hyper‑parameter sensitivity, t‑SNE visualization, convergence and complexity analysis are provided, with implementation details for reproducibility.

Critical weaknesses
  1. What is the concrete mechanism that enables high‑order relations to yield more reliable completion? Does the phenomenon “higher‑order propagation reduces cross‑class edges”only generalize from the TwoMoon datset?
  2. O(N^2) complexity limits scalability. Only small‑medium datasets are tested. No large‑scale experiments or sampling/sparse mitigation strategies are discussed.
  3. Add runtime/computational performance comparison against baselines.
  4. The similar components in HCCIMC have been proposed from prior works. What specific technical insights or dedicated designs distinguish this work from prior arts, beyond assembling existing components?
Questions for authors

See Weakness

2 comments

W1: Mechanism and generalizability of high-order relations.

Thank you for raising these important questions. We would like to clarify that the key innovation of HCCIMC is not the assumption that higher-order propagation is inherently more reliable, but an observation-constrained multi-order calibration mechanism that adaptively determines the contributions of different propagation orders. HCCIMC generates candidate representations through multi-order random walks over cross-view consensus and view-specific structures. To avoid blindly aggregating potentially unreliable propagation results, we introduce an observation-constrained objective (Eq. (10)), which learns the aggregation weights by minimizing the reconstruction discrepancy between the weighted multi-order representations and the original representations of observed samples. Ridge and entropy regularization further stabilize the weight optimization. The learned weights are then transferred to missing samples for representation completion. Thus, the reliability of HCCIMC comes from the adaptive calibration of multi-order structural information using observed representations, rather than simply increasing the propagation order.

W2-W3: Scalability and computational efficiency.

Thank you for raising these important concerns. To further evaluate the scalability of HCCIMC, we conducted additional experiments on two larger-scale datasets, NoisyMNIST and CIFAR10, containing 70,000 and 50,000 samples, respectively.

We acknowledge that graph-based methods may incur considerable computational and memory overhead, particularly when constructing dense sample-wise affinity matrices and performing repeated graph operations. This limitation was also observed in our practical evaluations. Specifically, Mask-IMvC and GHICMC encountered out-of-memory (OOM) errors when processing NoisyMNIST. For reference, a single dense 70,000 × 70,000 float32 matrix requires approximately 18.25 GiB of GPU memory. We also observed substantial runtime overhead in SCVT, where its 500-epoch alignment stage required approximately 18 hours.

To address these computational challenges, we adopt a memory-efficient sparse graph construction and propagation strategy in our large-scale implementation, which consists of three key operations:

(1) Chunk-wise Similarity Computation. We divide the similarity computation process into chunks of 512 samples, avoiding the simultaneous allocation of the entire dense pairwise similarity matrix and thereby reducing peak GPU memory consumption.

(2) Top-K Neighborhood Sparsification. We retain only the Top-10 nearest neighbors for each sample and discard the remaining connections, constructing sparse neighborhood graphs whose storage requirements scale approximately linearly with the number of samples.

(3) Sparse Graph Representation and GPU-based Propagation. We use sparse representations for subsequent consensus graph construction and multi-order information propagation, avoiding unnecessary dense matrix operations and reducing downstream memory and computational costs.

Table 1. Clustering performance comparison on NoisyMNIST under different missing rates.

MethodA(.1)N(.1)R(.1)A(.3)N(.3)R(.3)A(.5)N(.5)R(.5)A(.7)N(.7)R(.7)
DCP0.98710.96080.97180.79060.86320.78180.77850.83540.75850.84080.81670.7819
CPSPAN0.55970.59060.44090.62740.59930.46540.64920.62190.50600.53950.58900.4466
DVIMC0.98250.95240.96200.92200.88350.86230.94750.87650.88940.91890.82970.8329
RPCIC0.86970.76750.74460.76150.66970.61960.53860.49600.40330.26080.21150.0951
Mask-IMvCO/MO/MO/MO/MO/MO/MO/MO/MO/MO/MO/MO/M
HSACC0.98960.96790.97710.95810.92330.93800.92550.85920.85500.88890.79050.7773
GHICMCO/MO/MO/MO/MO/MO/MO/MO/MO/MO/MO/MO/M
Ours0.99060.97050.97940.97820.93860.95270.96250.90330.91970.94210.86090.8777

Note: A, N, and R denote ACC, NMI, and ARI, respectively

Table 2. Training time of HCCIMC on NoisyMNIST under different missing rates.

Missing RatePre-train (s)Contrastive (s)Total (s)
0.13725648410215
0.34126659410725
0.53842688710735
0.74183702811216

Overall, our additional experiments demonstrate that HCCIMC can effectively handle large-scale incomplete multi-view data. The proposed sparse computation strategies alleviate memory consumption and computational overhead, improving its practical scalability. Experiments on CIFAR-10 are still ongoing, and the results will be reported once completed.

W4: Key innovations of HCCIMC.

Thank you for raising this important concern. We acknowledge that individual techniques, such as anchor-based graphs, random walks, Jaccard similarity, and contrastive learning, have been explored in previous studies. However, our contribution lies in two specific designs that go beyond directly combining these components.

First, HCCM introduces an observation-constrained calibration mechanism for multi-order consensus completion. Rather than directly averaging multi-order propagation results, we construct a global consensus affinity based on the co-observation of samples across views and integrate it with view-specific structures (Eqs. (5)–(7)). More importantly, we use the original representations of observed samples to calibrate the contributions of different propagation orders (Eq. (10)). This allows the model to adaptively determine which propagation orders better preserve the observed representations, and transfer the learned weights to missing samples for completion (Eq. (11)).

Second, MNCCL introduces cross-view consistency-guided multi-order positive selection. It combines mutual first-order neighbors with Jaccard-based higher-order neighbors, and further requires neighborhood relationships to be consistent across different views (Eqs. (12)–(17)). This prevents unreliable neighborhood relations from a single view from being directly treated as positive pairs, addressing the false-positive problem caused by view incompleteness.

The effectiveness of these designs is supported by our ablation study. For example, on MSRC-V1 with a missing rate of 0.7, the complete HCCM+MNCCL achieves an ACC of 0.9000, compared with 0.8857 for KNN+MNCCL and 0.7000 for HCCM+conventional contrastive learning. These results demonstrate the complementary contributions of the proposed completion and positive-pair selection mechanisms. Therefore, the novelty of HCCIMC lies in using observed representations to calibrate multi-order structural propagation and cross-view neighborhood agreement to regulate contrastive positive selection, rather than simply assembling existing graph and contrastive learning components.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.