Bifurcate then Alienate: Incomplete Multi-view Clustering via Coupled Distribution Learning with Linear Overhead

Q1: More descriptions on the sample cluster distribution in Eq.(3).

A1: Thanks. Each row of the sample cluster $\mathbf{E}_r$ represents a probability distribution. So, for each row of $\mathbf{E}_r$, its sum needs to be 1. For handling the incompleteness, we introduce the index matrix $\mathbf{G}_r$ which consists of 0 and 1. We can formulate the observed sample clusters as $\mathbf{G} _r^{\top}\mathbf{E} _r$. Hence, we have the incomplete sample clusters need to satisfy $\mathbf{G} _r^{\top}\mathbf{E} _r\mathbf{1} _k =\mathbf{1} _{n _r}$.

Q2: More illustrations on the space rotation influence.

A2: It mainly serves as reordering sample clusters to make them as consistent as possible. Note that the common sample clusters are subject to the similar constraints as space operation, which can help tackle the negative elements that rotation operation brings. Please see the following performance comparisons. DM: direct mapping; RO: rotation operation.

One can observe that after space rotation, the performance receives improvement.

Q3: The initialization lacks clarity.

A3: Thanks! We create a random matrix with element from 0 to 1, and then do column-normalization. We use it to initialize $\mathbf{P}_r$, $\mathbf{C}_r$ and $\mathbf{C}$. For $\mathbf{F}_r$ and $\mathbf{E}$, we use random orthogonal matrix to initialize them. We use the row-normalized random matrix with element from 0 to 1 to initialize $\mathbf{E}_r$, and the random matrix with element from 0 to 1 to initialize $\mathbf{D}$. For $a_r$ and $b_r$, we initialize them with $1/v$ and $1/\sqrt{v}$.

Q4: Analysis of each term's contribution.

A4: The first term is deemed as a error reconstruction, and extracts feature clusters and sample clusters as well as their association. It also adaptively balances the important of each view. The second term separates feature clusters from sample clusters to highlight their discrimination by point-to-point alienation. The third term mitigates the misregistration and constructs complete sample clusters.

Q5: Why do the common sample clusters not adhere to the similar constraints as the view sample clusters?

A5: We introduce orthogonal transformation to reformulate the view sample clusters, which inevitably brings negative elements. Note that the essence of view sample clusters is a probability distribution, and accordingly all elements in them are non-negative. After transformation to produce common sample clusters, there will have negative elements. So, we make the common sample clusters adhere to similar constraints as the orthogonal transformation.

Q6: How is $n_r$ merged during updating the view coefficient? Affect the running speed?

A6: Updating the view coefficient needs to compute $\left\|\mathbf{X} _r\mathbf{G}_r\right\| _F^2$. Note that for each column of $\mathbf{G}_r$, there is only one 1 and other elements are 0. We have $\left\|\mathbf{X} _r\mathbf{G} _r\right\| _F^2$ is equal to $\left\|\mathbf{X} _r\mathbf{G} _r\mathbf{G} _r^{\top}\right\| _F^2$. The diagonal elements of $\mathbf{G} _r\mathbf{G} _r^{\top}$ are 1 or 0 and other elements are 0. Consequently, we have $\mathbf{X} _r\mathbf{G} _r\mathbf{G} _r^{\top}$ aims to select some columns of $\mathbf{X}_r$. So, we have that $\left\|\mathbf{X} _r\mathbf{G} _r\right\| _F^2$ is equal to $\left\|\mathbf{X} _r\odot\mathbf{O} _r\right\| _F^2$. $\mathbf{O}_r$ is $\mathbf{1} _{d _r}\cdot[\sum _{j=1}^{n_v}(\mathbf{G} _r) _{1,j},\cdots,\sum _{j=1}^{n _v}(\mathbf{G} _r) _{n,j} ]$. Before merging, the computing overhead is $\mathcal{O}(n n_r)$. After merging, it is $\mathcal{O}(n)$ and not affected by $n_r$.

Q7: When accumulating sample clusters vertically, how does the algorithm behave? Reasons?

A7: For the performance comparison, please refer to A7 in Reviewer xp7C. We attribute this phenomenon to three points. Accumulating sample clusters on all views vertically could result in inadequate communication between sample clusters across different views, which is not conductive to formulating rich representations. This also could not automatically measure the importance of different sample clusters. Meanwhile, the misregistration will disturb the cluster structure, and consequently degrades the formulated representations.

Q1: More details regarding Remark 1.

A1: Thanks. Due to $\mathbf{X} _r\in\mathbb{R}^{d_r\times n}$ and $\mathbf{G} _r\in\mathbb{R}^{n\times n_r}$, computing $q=\|\mathbf{X} _r\mathbf{G} _r-\widehat{\mathbf{A}} _r\mathbf{E} _r^{\top}\mathbf{G} _r\| _F^2$ will take at least $\mathcal{O}(n n_r)$ overhead. Note that $\mathbf{G}_r$ consists of 0 and 1, and there is only one element that is 1 in each column. $\mathbf{G} _r\mathbf{G} _r^{\top}$ is diagonal with 0 and 1. $\mathbf{X} _r\mathbf{G} _r\mathbf{G} _r^{\top}$ and $\mathbf{E} _r^{\top}\mathbf{G} _r\mathbf{G} _r^{\top}$ equal to $\mathbf{X} _r\odot\mathbf{O} _r$ and $\mathbf{E} _r^{\top}\odot\mathbf{Q} _r$. $\mathbf{O} _r$ is $\mathbf{1} _{d _r}\cdot[\sum _{j=1}^{n _v}(\mathbf{G} _r) _{1,j},\cdots,\sum _{j=1}^{n _v}(\mathbf{G} _r) _{n,j}]$ and $\mathbf{Q} _r$ is $\mathbf{1} _{k}\cdot[\sum _{j=1}^{n _v}(\mathbf{G} _r) _{1,j},\cdots,\sum _{j=1}^{n _v}(\mathbf{G} _r) _{n,j}]$. So, we have $q$ equals to $\|\mathbf{X} _r\odot\mathbf{O} _r-\widehat{\mathbf{A}} _r\mathbf{E} _r^{\top}\odot\mathbf{Q} _r\| _F^2$. Computing the latter needs $\mathcal{O}(d_rn)$, which is $\mathcal{O}(n)$.

Q2: Interpretation regarding TCIMC and LSIMV.

A2: TCIMC uses the tensor Schatten p-norm to explore complementary and spatial structure. Despite enhancing view interaction, it induces intensive time overhead due to the tensor operation, and is unsuitable for large-scale tasks. LSIMV constructs sparse and structured representations. It adopts a norm based sparse constraint to generate low-dimensional features, and uses local embedding to do aggregation. This needs a relatively larger memory cost due to the almost full-sized graph.

Q3: Does the orthogonal rotation affect the cluster label quality?

A3: This rotation reorganizes the sample clusters to relieve misregistration. Although altering the distribution, kindly note that the final common sample clusters are also required to be orthogonal, which keeps pace with the rotation. See the following comparisons. NRN: not involve rotation; ART: contains rotation.

Q4: How to set the numbers of feature clusters and sample clusters?

A4: The model based on eq (1) mainly shows that this paradigm can factorize multi-view data as feature clusters and sample clusters as well as association to mine latent patterns. For generality, the numbers of feature clusters and sample clusters can be any value (smaller than the feature dimension and sample size). In practice, we set their values just as $k$. The benefits are multifold. Dataset will be divided into $k$ groups, whether from the view of samples or features. The misregistration will be relieved owing to the small sample cluster number. Also, this makes the association small-sized, saving resources.

Q5: Does assigning view guidance to samples (VGS) facilitate the results?

A5: This a solution to avoid dimension difference. The following experiments reveal the performance. DAM: devised assigning mechanism.

The reasons for superior results of VGS are that this operation filters out noisy and data redundancy. For inferior results, possible reasons are that the operation causes information loss in diversity.

Q6: Performance when using the association in eq (1).

A6: This will build an association on each view for feature clusters and sample clusters separately. SAS: separated association scheme in eq (1); DUA: devised unified association.

Under eq (1), the view communication could be inadequate due to the separability. Also, this could fail to propagate feature cluster information across views into sample clusters since the association is established individually.

Q1: View guidance may impair the efficiency goal.

A1: Thanks. The computing cost of view guidance is linear, and thus hardly affects the efficiency goal. It requires constructing $\mathbf{X} _r\mathbf{G} _r\mathbf{G} _r^{\top}\mathbf{E} _r\mathbf{D} _{\gamma}^{\top}\mathbf{C}^{\top}$, $\mathbf{C} _r\mathbf{C}^{\top}$ and $[\mathbf{P} _r\mathbf{C}|\mathbf{C} _r]\mathbf{D}\mathbf{E} _r^{\top}\mathbf{G} _r\mathbf{G} _r^{\top}\mathbf{E} _r\mathbf{D} _{\gamma}^{\top}\mathbf{C}^{\top}$, which takes $\mathcal{O}(d_rn+d_rnk+d_rk^2)$, $\mathcal{O}(d_rk^2)$, $\mathcal{O}( nk + 2d_rk^2 + d_rnk)$. So, it totally takes $\mathcal{O}(d_rnk+d_rk^2)$. This is $\mathcal{O}(n)$ and consistent with the efficiency goal.

Q2: Why introducing common orthogonal sample clusters?

A2: They gather all view sample clusters to formulate full embedding. Due to the missing instances, the sample clusters on each view are incomplete. The orthogonality plays a role in enhancing the separability of learned common sample clusters to better group samples.

Q3: Does the missing ratio affect the complexity of BACDL?

A3: It does not affect the complexity. The index matrix containing missing ratio owns the properties, i.e., there is only one element that is 1 while the other elements are 0 in each column. We have $\mathbf{G} _r\mathbf{G} _r^{\top}$ is diagonal with elements either 0 or 1. So, $\mathbf{X} _r\mathbf{G} _r\mathbf{G} _r^{\top}$ equals to $\mathbf{X} _r\odot\mathbf{O} _r$ where $\mathbf{O} _r=\mathbf{1} _{d _r}\left[\sum _{j=1}^{n _v}(\mathbf{G} _r) _{1,j}, \cdots,\sum _{j=1}^{n _v}(\mathbf{G} _r) _{n,j}\right]$. This takes $\mathcal{O}(d_rn)$ cost and is irrelevant to the missing ratio.

Q4: Why guaranteeing C column-normalized?

A4: Each column of feature clusters denotes a probability distribution on all feature dimensions. Each column sum needs to add up to 1. After bifurcating, each part also should conform to this point. On the basis of column-normalized $\mathbf{P}_r$, we derive that the premise for $\mathbf{P} _r\mathbf{C}$ being column-normalized is that $\mathbf{C}$ only needs to be column-normalized.

Q5: How does the element-wise operation reduce the computational overhead?

A5: This mainly benefits from the equivalent element transformation. For $\mathbf{E}_r$, directly calculating $\left\|\mathbf{E} _r^{\top}\mathbf{G} _r\right\| _F^2$ will take $\mathcal{O}(knn_r)$. As the missing ratio decreases, $n_r$ is gradually increasing. The overhead is almost close to $\mathcal{O}(n^2)$.

Note that $\left\|\mathbf{E} _r^{\top}\mathbf{G} _r\right\| _F^2$ is equal to $\left\|\mathbf{E} _r^{\top}\mathbf{G} _r\mathbf{G} _r^{\top}\right\| _F^2$. Then, by the element-wise operation, $\left\|\mathbf{E} _r^{\top}\mathbf{G} _r\mathbf{G} _r^{\top}\right\| _F^2$ is $\left\|\mathbf{E} _r^{\top}\odot\mathbf{Q} _r\right\| _F^2$, which takes $\mathcal{O}(nk)$. $\mathbf{Q}_r$ is $\mathbf{1} _{k}\left[\sum _{j=1}^{n _v}(\mathbf{G} _r) _{1,j}, \cdots, \sum _{j=1}^{n _v}(\mathbf{G} _r) _{n,j}\right]$.

Q6: Why learning the sample clusters on each view respectively (SEV)? Why not directly learning common ones?

A6: The former may facilitate capturing the view characteristics. Learning common sample clusters (CSC) is a feasible scheme, and yet could weaken the view data diversity.

Q7: When stacking sample clusters (STA), the performance?

A7: Please see the following table. MSC: mapping sample clusters.

Directly stacking sample clusters could lead to insufficient interaction among views. Moreover, this does not adaptively balance their contributions. Misregistration also will weaken the quality of sample clusters.

Sincerely thank Reviewer 7KrE for the very constructive comments.

Q1: Providing iteration level convergence and approximation guarantees would enhance the theoretical rigor.

A1: Many thanks! This is a challenging task for authors during the rebuttal period. At this moment, authors have no inspiring ideas about it. So sorry for this. We will strive to explore this topic in future work.

Q2: Ambiguities in theoretical details. Like the convergence level, global optimal.

A2: Thanks! We will carefully proofread the manuscript to state them more precisely. Specially, the convergence refers to the objective function value. The global optimal refers to the approximate solution to the proxy problem.

Q3: Lack of justification for method choices. Like why NMF.

A3: NMF, subspace, kernel and neural network are four common means to tackle IMC problems. Kernel and neural network can perform nonlinear mapping well, while usually suffering from intensive complexity due to the large-sized feature matrix and complex network structure. Moreover, the selection of kernel type and network architecture also heavily relies on empirical knowledge. In virtue of the superior high-dimensional data processing capability, subspace effectively builds affinity via utilizing multiple potential spaces. However, due to the full-sized self-expression characteristics, it generally encounters cubic computing overhead. Unlike them, NMF mines shared low-dimensional structures by decomposing the view data matrix to discover latent clusters. In the decomposed basis vectors, each element can be seen as a contribution to the features, which makes the analysis results more intuitive and helps to understand the reasons for clustering. So, in the paper, we adopt the NMF technique.

Q4: Performance gains and statistical validation.

A4: In experiments, we run 50 times, and record the average value of clustering results. We will add these statistical information in the next version, and further analyze its features.

Q5: Lack thorough review on NMF-based approaches.

A5: Thanks! We will thoroughly review the mentioned works in the next version.

Q6: Writing and structural Issues. Like section transitions, example clarifications.

A6: Thanks! We will carefully polish the manuscript. For the matrix $\mathbf{G}_r$, it consists of 0 and 1, and there is only one 1 in each column.

Q7: Complexity analysis. Considering the number of iterations required for convergence.

A7: Good suggestion! The number of required iterations indeed affects the time complexity. Deriving the iterations required for convergence is a promising research direction. We will make efforts to explore this topic in future work.

Q8: Reproducibility issues.

A8: We will release the source code in the final version.

Q9: What "global optimal" refers to.

A9: It refers to that of the proxy problem.

Q10: Why feature clusters' perspective? Why not sample clusters' perspective?

A10: Kindly note the feature cluster matrix aims at mapping original data to a potential space, and learns the marginal distribution of original data. Bifurcating it will be conductive to extracting representative features from original data. It can be seen as a feature extractor. The sample cluster matrix mainly plays a role in grouping formed representations to generate clusters. A high-quality cluster partition relies on more discriminative representations. So, we adopt the feature clusters' perspective. Please see the following comparisons. BSC: Bifurcate sample clusters; BFC: Bifurcate feature clusters.

Evidently, BFC is more desirable than BSC in most cases, revealing that feature clusters' perspective is more preferable.