Simple yet Effective Incomplete Multi-view Clustering: Similarity-level Imputation and Intra-view Hybrid-group Prototype Construction

Authors: Shengju Yu, Zhibin Dong, Siwei Wang, Pei Zhang, Yi Zhang, Xinwang Liu, Naiyang Guan, Tiejun Li, Yiu-ming Cheung
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords: incomplete multi-view clustering, mulit-view clustering, clustering

Abstract:
Most of incomplete multi-view clustering (IMVC) methods typically choose to ignore the missing samples and only utilize observed unpaired samples to construct  bipartite similarity. Moreover, they employ a single quantity of prototypes to extract the information of $\textbf{all}$ views.   To eliminate these drawbacks, we present a simple yet effective IMVC approach, SIIHPC, in this work.  It firstly transforms partial bipartition learning into original sample form by virtue of   reconstruction concept to split out of  observed similarity, and then loosens traditional non-negative constraints via regularizing samples to more freely characterize the similarity.  Subsequently, 
it learns to recover the incomplete parts by utilizing the connection built between the similarity exclusive on respective view and the consensus graph shared for all views.  On this foundation,  it further introduces a group of hybrid prototype quantities for each individual view  to flexibly extract the data features   belonging to each view itself.  Accordingly, the resulting graphs are with various scales and  describe the overall similarity more comprehensively. It is worth mentioning that these all are optimized in one unified learning framework, 
which makes it possible for them to  reciprocally promote.  Then, to effectively solve the formulated optimization problem,  we design an ingenious auxiliary function that is with theoretically proven monotonic-increasing properties.  Finally, the clustering results are obtained by implementing spectral grouping action on the eigenvectors  of stacked multi-scale consensus similarity.  Experimental results confirm the  effectiveness of  SIIHPC.

Decision: accept (spotlight)
Reviewer scores: 6, 8, 8, 8

Reviews and discussion:
<thread>
creation date:
1730275076106

thread_type:
official_review

<thread_object>
creator: reviewer_gpnt

<content>
summary:
This paper presents an incomplete multi-view clustering (IMVC) algorithm, SIIHPC. To utilize the latent valuable information of incomplete samples, it successfully separates out the observed parts via bipartition learning transformation and relaxes traditional non-negative constraints via sample regularization. It introduces the learnable consensus graphs to provide unified structure, and based on the relationship between consensus graphs and exclusive similarities it imputes the incomplete part at the similarity level. To get rid of the limitations of single prototype quantity, it assigns a group of hybrid prototype quantities for each view, and performs spectral grouping on the resulting multi-scale graphs to generate the cluster labels. Afterwards, it gives a four-step updating scheme to minimize the formulated objective. Overall, the overall organization of this manuscript is clear and easy to follow.

strengths:
1. The motivation is good. Incorporating incomplete samples into the construction of bipartite similarity enhances the representation of relationships between different entities.   Diverse prototype quantities facilitate the accurate characterization of different views.

2. The designed auxiliary function is interesting. It equivalently solves one quadratic programming problem with orthogonal constraints and meanwhile is demonstrated to be with monotonic-increasing properties.

weaknesses:
1. In the paper, the hyper-parameters $\lambda$ and $\beta$ are adjusted in $[10^{-7}, 10^{-6}, \cdots, 10^{-2} ]$  and $[10^{2}, 10^{3}, \cdots, 10^{7} ]$ respectively. The reasons for setting parameters are not given. 

2. Similar to the analysis about Table 3, some reasons for the sub-optimal results in Table 2 should be added. 

3. Descriptions about the theoretical space overhead should be more in-depth.

questions:
1. As descripted, PSIMVC is also based on prototype, what are the differences between the proposed SIIHPC and PSIMVC? Specially, combined with Table 3, PSIMVC can consume less time and/or memory.  

2. Figure 4 show that at each iteration of Algorithm 2, the objective of function $g$ is increasing while at different iterations of Algorithm 2, it doesn't seem like this, such as at the $3$-th, $4$-th, $5$-th iteration respectively. 

3. After transformation, why is the complexity about $\mathbf{H}_{v,s}$ reduced from square to linear?

4. When adopting the prototypes constructed by elicitation sampling, what is the performance of SIIHPC?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730632321726

thread_type:
official_review

<thread_object>
creator: reviewer_yvby

<content>
summary:
This paper proposes a new incomplete multi-view clustering method, which reconstructs similarity relationships through the original sample form to capture the intrinsic information of all views. By relaxing traditional non-negative constraints, the method enables more flexible similarity characterizations. Additionally, a hybrid prototype set is introduced for each view, facilitating view-specific feature extraction and contributing to a comprehensive consensus graph. An innovative auxiliary function with monotonic properties is designed to solve the optimization problem effectively. Experimental results on various incomplete multi-view datasets demonstrate the robust clustering performance of SIIHPC.

strengths:
Paper Strengths
1.The paper is well-organized and easy to follow. The intuition is clearly discussed in the Introduction.
2.The proposed method performs exhaustive experimental analyses, comparing a wide array of clustering algorithms, thereby strengthening the credibility of the results.

weaknesses:
Paper Weaknesses
1.The process for constructing the consensus graph $G$ is not clearly explained, particularly in relation to $G_s$.
2.Does the dataset include both images and text? Please specify the composition of each view within the dataset.
3.It would be helpful to discuss how Similarity Level Imputation and Hybrid-group Prototypes specifically contribute to improving clustering performance in Ablation section.

questions:
1.The experimental setup lacks sufficient detail, particularly regarding the range and selection criteria of hyperparameters.
2.The Symbol Summary in the Appendix does not cover all symbols used throughout the paper, which may hinder clarity for readers. It is recommended to include all symbols and provide detailed explanations for each variable to improve readability and understanding of the methodology.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730632565930

thread_type:
official_review

<thread_object>
creator: reviewer_3rbh

<content>
summary:
In this manuscript, the authors address the challenge of incompleteness due to missing samples by restoring the missing data at the similarity level. They propose a method that employs a hybrid approach to extract data representations, utilizing multiple quantities of prototypes for each individual view rather than relying on a single quantity across all views. This approach effectively resolves the misalignment of observed samples and incorporates potentially useful information from the missing samples into the bipartition similarity. Additionally, the authors balance contributions from different views while defining overall similarity based on the intrinsic characteristics of each view. These goals are effectively realized within a cohesive learning framework. The proposed method's effectiveness is convincingly demonstrated through experimental results on six public datasets with varying missing ratios.

strengths:
1. The manuscript presents a logically structured approach, with Figure 1 providing a clear and intuitive overview of the framework.

2.  The authors utilize a variety of missing ratios and metrics in their experiments to evaluate clustering performance effectively.

3. The proposed SIIHPC demonstrates favorable memory and computational efficiency.

weaknesses:
1. There is an issue with the manuscript's organization where the title of Section 5.5 is found to be identical to that of Section G in the Appendix.

2.  Experiments exhibit that some comparison methods do not function properly on VGGFACEHUND, YOUTUBEFACE and FASHMINST. However, there is a lack of theoretical explanations to substantiate these observations.

3. The space complexity of Algorithm 2 is not described enough.  

4. The manuscript lacks definitions or explanations for certain notations used throughout the text. For instance, the notation $()_{+}$ in (11), N/A in Table 2 and Table 3  are not clarified.

questions:
1. Is the auxiliary function $g$ influenced by the percentage of missing samples?  Both $\mathbf{L} _{v}$ and $\mathbf{P} _{v,s}$ incorporate the missing percentage, which raises the question of how this affects the function.

2. According to the dataset descriptions in Table 1, FASHMINST has more samples than YOUTUBEFACE. However, the results in Table 3 indicate that SIIHPC incurs a higher memory overhead on YOUTUBEFACE compared to FASHMINST. What factors contribute to this discrepancy?

3. As indicated in Table 3, GSRIMC is limited to operating on only two small-sized datasets and exhibits higher consumption of running time and memory overhead. In comparison with SIIHPC, what is the theoretical complexity of GSRIMC?

4. Beyond the comparison with graph or tensor-based methods, how does SIIHPC fare when compared to deep learning approaches?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730709878316

thread_type:
official_review

<thread_object>
creator: reviewer_fe1f

<content>
summary:
This paper introduces SIIHPC, an incomplete multi-view clustering method that bypasses traditional missing view recovery by directly imputing similarities. SIIHPC replaces single prototype construction with hybrid-group prototypes, allowing each view to capture unique features within a unified framework. This framework is optimized through a well-designed iterative algorithm with convergence guarantees, ensuring robust and effective clustering.

strengths:
The paper presents a novel approach SIIHPC to incomplete multi-view clustering through similarity-level imputation, which diverges from conventional methods that focus on reconstructing missing samples or features. This approach serves as an efficient alternative to traditional recovery-based techniques. By addressing incomplete multi-view clustering without explicit missing view imputation, SIIHPC reduces computational overhead and allows clustering methods to function effectively without relying on fully complete data structures.

A key innovation of the paper is the introduction of hybrid-group prototype construction, which replaces single prototypes with a more flexible model that enables each view to capture unique features. This enhances the model’s adaptability to heterogeneous data views, improving clustering performance across diverse datasets and scenarios.

Extensive experimental evaluations on multiple datasets with varying missing ratios highlight the robustness and effectiveness of SIIHPC. The inclusion of ablation studies further enriches the assessment, providing valuable insights into the contribution of each component to the model's overall performance and validating the framework’s design choices.

weaknesses:
The terminology introduced in the paper is unclear; for instance, terms like T-PBL, SLI, IVHGP, and MSVSG are not properly explained in the captions of Figure 1, making it difficult for readers to follow the framework without additional context.

The overall process of the proposed clustering algorithm lacks clarity. Specifically, the final steps for obtaining clustering results and the initialization settings for relevant parameters should be clearly defined to improve the reader's understanding of the algorithm’s workflow.

While the paper provides strong experimental results, the interpretability of the clustering outputs and the practical implications of hybrid-group prototypes could be explored further. It would be helpful for the authors to discuss how the clustering results or prototype structures might be interpreted in real-world applications, providing insights into the method's broader utility.

questions:
Can the authors clarify the terms used in Figure 1, such as T-PBL, SLI, IVHGP, and MSVSG, and ensure that these terms are defined either in the figure caption or in the text to improve readability?

Could the authors provide a more detailed explanation of the overall process of the clustering algorithm, particularly the final steps for obtaining clustering results and the initial parameter settings?

Given that the method relies on similarity-level imputation rather than missing view recovery, how sensitive is the model's performance to the quality of the imputed similarities? Could the authors discuss any potential limitations in scenarios with high levels of data incompleteness?

To better assess the stability and reliability of SIIHPC’s performance, could the authors provide standard deviation metrics for their experimental results? Including this information would help illustrate the consistency of the method across different runs and give a clearer view of its robustness under varying data conditions.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732543739549

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Reply for SAC, AC, Reviewers

comment:
Dear SAC, AC, Reviewers, 


We would like to extend our heartfelt thanks to SAC and AC as well as Reviewers for the dedicated efforts and invaluable feedback.   Your insightful comments and constructive criticisms have not only helped us improve the quality of our work but also offered us new perspectives and ideas that we had not considered before.  We are truly grateful for your meticulous review and the opportunity to revise our paper based on your suggestions.  

This manuscript mainly focuses on two issues in incomplete multi-view clustering (IMVC): the ignoring of missing samples and the single quantity of prototypes.



Most of existing IMVC  methods typically choose to ignore the missing samples and only utilize the observed samples to  achieve the construction of bipartite similarity.   This will miss out latent useful information from the missing samples, resulting in the generated similarity not that accurate. Also, due to the randomness of sample missing, the remaining observed samples are usually unpaired, which could lead to unbalanced cluster distribution and deteriorate the graph structure.  To this end,  we firstly transform partial bipartition learning into original sample form by virtue of reconstruction concept to split out of observed similarity, and then loosens traditional non-negative constraints via regularizing samples to more freely characterize the similarity. Afterwards, we  learn to recover the incomplete parts by utilizing the connection built between the similarity exclusive on respective view and the consensus graph shared for all views.



Subsequently, different from current techniques that employ a single quantity of prototypes to extract the information of all views,  we introduce the intra-view hybrid-group prototype quantity learning paradigm  to flexibly extract the data features belonging to each view itself.  It can automatically select the appropriate quantity of prototypes according to view characteristics.  Consequently, the resulting graphs are with various scales and describe the overall similarity more comprehensively. 


Further, to optimize the formulated objective loss,  we design an ingenious auxiliary function with  theoretically and experimentally proven monotonic-increasing properties.  


It is worth mentioning that these components are all in one unified framework,  which enables them to mutually support and encourage during the learning process.  Meanwhile, the overall linear complexity guarantees that our model can be extended to large-scale tasks.  

We also count the clustering variance under diverse missing ratios, and the experimental results suggest that our proposed SIIHPC is stable and reliable  under varying data conditions.  
 
Moreover, the algorithm convergence, the hyper-parameter sensitivity and the hybrid prototype quantity influence are also well explored in the manuscript. 


Experiments on several public datasets demonstrate that even encountering diverse missing proportions, our SIIHPC is still able to provide a preferable clustering performance compared to multiple remarkable IMVC competitors.




We hope the above statements have addressed your concerns, and highly appreciate your thoughtful and profound reviews.  If any questions, please feel free to contact us! We are fairly happy to further discuss them.  



Best regards, 

Authors of paper 778
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper aims to tackle the missing sample problem in multi-view clustering task. The problem itself is important and valuable in the real-world scenarios. The proposed approach is technically sound. The extensive empirical studies, both in the manuscript and appendix, are thorough and convincing.

The paper received three clear acceptances and one borderline acceptance from four expert reviewers. I agree with the reviewers’ assessments and recommend acceptance.