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

We extend our sincere gratitude to Reviewer Gpnt for his/he valuable feedback and guidance in revising this paper. We have thoroughly addressed each concern raised and are hopeful that all issues have been resolved satisfactorily.

Q1: 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.

A1: Thanks for your constructive comment. The hyper-parameters $\lambda$ and $\beta$ aim at fine-tuning $\left\|| \mathbf{G}_s \right\|| _F^2$ and $\left\|| \mathbf{A} \right\|| _F^2$ respectively. Note that $\mathbf{G} _s \in \mathbb{R}^{m _s \times n}$ and $\mathbf{A} \in \mathbb{R}^{V \times S}$ where $m _s$, $n$, $V$ and $S$ denote the numbers of prototypes at the $s$-th group, samples, views and prototype quantity candidates, respectively. Generally, $V \leq m_s$ and $S \ll n$. Therefore, we have that the size of $\mathbf{G}_s$ is much greater than that of $\mathbf{A}$. Besides, combined with the feasible regions, we have that the absolute values of the elements in $\mathbf{G} _s$ and $\mathbf{A}$ are all within the range $[0,1]$, Therefore, we can get that $\left\|| \mathbf{G} _s \right\|| _F^2$ is much larger than $\left\|| \mathbf{A} \right\|| _F^2$. Based on these, we search $\lambda$ within a small range while searching $\beta$ within a relatively large range.

These have been added in Section A of the appendix. Please check it.

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

A2: There exist a small amount of sub-optimal results in some cases against the algorithms HCPIMSC, LRGRIMVC, IMVCCBG and PIMVC. Possible reasons could be that HCPIMSC exploits the high-order correlation between views via low-rank tensor learning and utilizes a hyper-graph regularizer to capture geometrical structure between samples; LRGRIMVC adopts adaptive graph embedding and rank constraint to extract view features, and combines the global structure, relevant information within views and latent information across views together to construct the similarity relationship; IMVCCBG refines consistency view features through consensus anchors and employs orthogonality learning to highlight the discrimination of potential sub-spaces; PIMVC reformulates the projection learning of each view to alleviate the information imbalance and designs a graph penalty term to extract the geometric structure embedded into original data.

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

A3: The space overhead of Algorithm 2 mainly comes from $\\{ \mathbf{H} _{v,s} \\} _{v=1,s=1}^{V,S}$, $\\{ \mathbf{Q} _{v,s} \\} _{v=1,s=1}^{V,S}$, $\\{ \mathbf{G} _{s} \\} _{s=1}^{S}$ and $\mathbf{A}$. Considering that their sizes are $d _v \times m _s$, $m _s \times n$, $m _s \times n$ and $V \times S$ respectively where $d _v$, $m _s$, $n$, $V$, $S$ denote the feature dimension on the $v$-th view, the number of the $s$-th group prototypes, the number of samples, the number of views and the number of prototype quantity candidates, we have that storing them requires $\mathcal{O}(\sum _{v=1}^{V} \sum _{s=1}^{S} d _v m _s)$, $\mathcal{O}(n \sum _{s=1}^{S} m _s)$, $\mathcal{O}(n \sum _{s=1}^{S} m_s )$ and $\mathcal{O}(VS)$ memory overhead respectively. Therefore, the total space overhead is $\mathcal{O}(\sum _{v=1}^{V} \sum _{s=1}^{S} d _v m _s + n \sum _{s=1}^{S} m _s )$. Note that $d _v$ is a constant and not related to $n$ and that $m_s$ is generally far smaller than $n$, we can obtain that the space complexity is $\mathcal{O}(n)$, which is linear with respect to the number of samples.

Q4: The experimental setup lacks sufficient detail, particularly regarding the range and selection criteria of hyper-parameters.

A4: The parameter selection criteria is as follows.

For $\lambda$ and $\beta$, we observe that they are associated with $\left\|| \mathbf{G}_s \right\|| _F^2$ and $\left\|| \mathbf{A} \right\|| _F^2$ respectively and the sizes of $\mathbf{G} _s$ and $\mathbf{A}$ are $m _s \times n$ and ${V \times S}$. In general, the number of views $V$ is less than or equal to the number of prototypes at the $s$-th group $m_s$; the number of prototype quantity candidates $S$ is far less than the number of samples $n$. Consequently, we can obtain that the size of $\mathbf{A}$ is fare less than that of $\mathbf{G}_s$. Beyond that, in conjunction with the feasible region constrains, we can get that the element absolute values of $\mathbf{A}$ and $\mathbf{G}_s$ are all in $0 \sim 1$. As a result, we have that $\left\|| \mathbf{A} \right\||_F^2$ is far less than $\left\|| \mathbf{G} _s \right\|| _F^2$. So, we fine-tune $\beta$, which is related to $\left\|| \mathbf{A} \right\|| _F^2$, in a large range while fine-tuning $\lambda$ in a small range. These reasons about hyper-parameter setting are added in Section A of the appendix. Please check it.

For the hybrid prototype quantities on each view, we set them as $[1,2,\cdots,5]k$ where $k$ is the number of clusters. The reason for this is that through experiments we find too few prototype quantities are not adequately to exploit data features, while too many prototype quantities lead to information redundancy and the increasing of running time. Therefore, we set them as $[1,2,\cdots,5]k$ in all experiments. More detailed exploration please refer to 'the influence of hybrid prototype quantities' section in Appendix.

Q5: It is recommended to include all symbols in Symbol Summary and provide detailed explanations for each variable to improve readability and understanding of the methodology.

A5: Thanks! We have carefully modified the Symbol Summary section, and added more symbols and descriptions. Please check it.

We are very grateful for Reviewer yVBy constructive comments and guidance on the revision of this paper. We have carefully addressed all concerns, and truly hope that all issues have been resolved.

Q1: The process for constructing the consensus graph $\mathbf{G}$ is not clearly explained, particularly in relation to $\mathbf{G}_s$.

A1: $\mathbf{G}$ denotes a learnable consensus graph that is shared for all views. (Kindly note that $\mathbf{H}_v^{\top} \mathbf{D}_v \mathbf{W}_v \mathbf{W}_v^{\top}$ denotes the observed similarity on view $v$.) $\mathbf{G}_s$ is the form of $\mathbf{G}$ under $s$-th prototype quantity candidate, and is constructed by Eq. (7) in the manuscript.

Q2: Does the dataset include both images and text? Please specify the composition of each view within the dataset.

A2: The more detailed descriptions about the public multi-view datasets utilized in experiments are as follows.

BDGPFEA is a genomic text sequence dataset, and consists of 2500 samples and 3 views. The feature dimensions on views are 1000, 500, and 250 respectively. The number of clusters is 5.

NUSOBJECT is an object image dataset, and consists of 6251 samples and 5 views. The feature dimensions on views are 129, 74, 145, 226 and 65, respectively. The number of clusters is 10.

VGGFACEFIFTY is a face dataset with 16936 samples. The number of views is 4, and the feature dimensions are 944, 576, 512 and 640, respectively. There are 50 clusters.

VGGFACEHUND is also a fact dataset. It contains 36287 samples. The feature dimensions on 4 views are 512, 576, 640 and 944, respectively. There are 100 clusters.

YOUTUBEFACE is an image dataset collected from YouTube website. There are 63896 samples and 4 views totally. The feature dimensions are 640, 944, 576 and 512 respectively. The number of clusters is 20.

FASHMINST is a fashion product database with 70000 samples and 4 views. The feature dimensions are 576, 512, 944 and 640 respectively. The number of clusters is 10.

Q3: It would be helpful to discuss how Similarity Level Imputation and Hybrid-group Prototypes specifically contribute to improving clustering performance in Ablation section.

A3: The more discussion about the effect of similarity level imputation and hybrid-group prototypes is as follows.

For the similarity level imputation, it recovers the incomplete parts caused by missing samples on current view through utilizing the representations of the same object on other views. It alleviates the cluster imbalance caused by the unpairing of observed samples to improve the clustering performance. Also, it enables information from different views to interact mutually during the similarity forming phase so as to generate more accurate similarity relationship.

For the hybrid-group prototypes, it can utilize the learnable balance factors to automatically adjust the contributions of prototype quantities according to the characteristics of each view itself, and thereby flexibly extracts view features and accordingly brings clustering performance improvement.

Additionally, these two parts are in one common learning framework, which makes them facilitate each other toward a mutual strengthening direction.

We would like to express our gratitude to Reviewer 3rbh for their constructive comments and guidance regarding the revision of this paper. We have addressed all concerns in detail. We sincerely hope that all issues have been resolved.

Q1: The title of Section 5.5 is duplicated with that of Section G in the Appendix.

A1: We carefully proofread the manuscript and revise the title of Section G as 'Other Convergence Examples'.

Q2: Experiments exhibit that some comparison methods can not normally execute on VGGFACEHUND, YOUTUBEFACE and FASHMINST. There is a lack of some theoretical interpretations to support these observations.

A2: The methods LSIMVC, GSRIMC, HCPIMSC, EEIMVC, LRGRIMVC, BGIMVSC, NGSPCGL, PIMVC and HCLSCGL can not properly run on VGGFACEHUND, YOUTUBEFACE or FASHMINST. The reasons for this are as follows.

To effectively eliminate the IMVC problem, these methods adopt various means. LSIMVC combines matrix factorization and sparse representation learning. GSRIMC integrates tensor nuclear norm, cross-view relation learning and bias sub-graph construction together. HCPIMSC adopts the idea of tensor factorization, low-rank learning and hyper-Laplacian regularization. EEIMVC effectively merges multi-kernel learning and consensus clustering learning. Different from them, LRGRIMVC utilizes low-dimensional embedding and adaptive graph learning. BGIMVSC unifies balanced spectral learning, graph generation and view adjustment. NGSPCGL jointly conducts neighbor group structure preserving and consensus representation construction. PIMVC performs graph projection, matrix factorization and global geometric structure maintaining within one shared framework. HCLSCGL embeds the Laplacian rank constraint into the neighbor graph learning. Although achieving effective clustering results from diverse aspects, these methods typically involve constructing $n \times n$ matrix, which causes their complexity being at least $\mathcal{O}(n^2)$. The intensive complexity limits their ability to tackle large-scale IMVC problems.

Q3: The space complexity of Algorithm 2 is not described enough.

A3: Its space cost is mainly from storing $\mathbf{H} _{v,s}$, $\mathbf{G} _s$, $\mathbf{Q} _{v,s}$ and $\mathbf{A}$, $v=1, 2, \cdots, V; s=1, 2, \cdots, S$. In conjunction with the fact that $\mathbf{H} _{v,s}$, $\mathbf{G} _s$, $\mathbf{Q} _{v,s}$ and $\mathbf{A}$ are in $\mathbb{R}^{d _v \times m _s}$, $\mathbb{R}^{m _s \times n}$, $\mathbb{R}^{m _s \times n}$ and $\mathbb{R}^{V \times S}$ respectively, we can get that it needs $\mathcal{O}(d _v m _s)$, $\mathcal{O}(m _s n)$, $\mathcal{O}(m _s n)$ and $\mathcal{O}(VS)$ memory space respectively to store $\mathbf{H} _{v,s}$, $\mathbf{G} _s$, $\mathbf{Q} _{v,s}$ and $\mathbf{A}$. Due to the numbers of views $V$ and prototype quantity candidates $S$ are constants, therefore, it totally needs $\mathcal{O}(n \sum _{s=1}^{S} m _s + \sum _{v=1}^{V} \sum _{s=1}^{S} d _v m _s)$ memory cost to store all of them. Additionally, the number of prototypes $m_s$ is largely smaller than the number of samples $n$, and the dimension of features $d_v$ is a constant and has nothing to do with $n$. Therefore, we have that the space complexity of Algorithm 2 is $\mathcal{O}(n)$.

Q4: The definition/meaning of some notations is missing here, such as the $()_{+}$ in (11), N/A in Table 2 and Table 3.

A4: Thanks! $(x) _{+}$ denotes that if $x>0$, it takes $x$ otherwise 0. N/A denotes the running error caused by the complexity limit of algorithm itself.

We greatly appreciate the profound comments provided by Reviewer fE1F for the revision of this manuscript. We have addressed all concerns in detail and hope that all issues have been successfully resolved.

Q1: 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?

A1: We have updated Figure 1, please check it. Specially,

• T-PBL represents transforming partial bipartition learning into original sample form to split out of observed similarity.

• IVHGP represents introducing a group of hybrid prototype quantities for each individual view to flexibly extract the data features belonging to each view itself, i.e., intra-view hybrid-group prototypes.

• OS represents the observed similarity on each individual view.

• MSVSG represents the generated graphs with various scales on each view, i.e., multi-scale view-specific graphs.

• SLI represents learning 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, i.e., similarity-level imputation.

• CG represents the learned consensus graph that is shared for all views.

• SG represents conducting spectral grouping on the graph generated by stacking multi-scale consensus graphs.

These detailed descriptions are also added in Section C of the appendix.

Q2: 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?

A2: We here provide a more detailed explanation about the overall process of the clustering algorithm.

To be specific, we first initialize the prototype matrix $\mathbf{H} _{v,s}$ with the $s$-th quantity on view $v$ using the orthogonal matrix, the imputation matrix $\mathbf{Q} _{v,s}$ with the $s$-th scale on view $v$ using the random matrix with elements ranging from -1 to 1, the consensus graph $\mathbf{G} _s$ with the $s$-th scale using the random matrix with elements ranging from -1 to 1, the prototype quantity coefficient matrix $\mathbf{A}$ using ${1}/{S}$ where $S$ denotes the number of hybrid prototype quantity candidates.

Then, we perform Algorithm 2 until satisfying $(f _{obj} (t)-f _{obj} (t + 1))/f _{obj} (t) <= 1e-4$ where $f _{obj} (t)$ denotes the objective value at the $t$-th iteration.

Subsequently, we stack all generated unified representation matrices $\\{ \mathbf{G} _s\\} _{s=1}^{S}$ by rows, and conduct spectral grouping on it to obtain the final clustering results.

Q3: 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?

A3(--1): In our model, the incomplete similarity is adaptively imputed by comparing the learned consensus graphs and multi-scale view-specific graphs. It alleviates the cluster imbalance caused by the he unpairing of observed samples, and also makes information from different views able to communicate with each other so as to more accurately construct similarity.

To investigate its effect, we organize some comparison experiments and the results are summarized in the following table where 'NSLF' and 'WSLF' represent the results with/without our similarity-level imputation, respectively. 'BDG.','NUS.','VGY.','VGD.','YOU.' and 'FAS.' are abbreviations of BDGPFEA, NUSOBJECT, VGGFACEFIFTY, VGGFACEHUND, YOUTUBEFACE and FASHMINST, respectively.