From Spectrum-free towards Baseline-view-free: Double-track Proximity Driven Multi-view Clustering

Q1: Final steps for deriving clustering and variable initialization.

A1: After getting $\mathbf{C}$, we derive the clustering by sequentially identifying the row numbers where the element 1 is located. We initialize $\mathbf{A}_p$, $\mathbf{T}_p$, $\mathbf{B}_p$ and $\boldsymbol{\alpha}$ with random matrix, unit matrix, orthogonal matrix and $1/v$. For $\mathbf{C}$, we create a zero matrix and then randomly assign a single 1 to each column. For $\mathbf{S}_p$, we assign elements ranging from 0 to 1 column by column and ensure that the diagonal elements remain 0 and the sum of each column equals 1.

Q2: Explanations for sub-optimal results.

A2: Thanks! MSCIAS achieves a marginally superior Fscore (0.72%) on Cora, possibly because of the introduction of HSIC and the employment of local connectivity. FPMVS achieves a 0.29% accuracy gain on CIF10Tra4 owing to the adoption of orthogonal projection ensembles. SFMC integrates a structural coherence and self-supervised attention. MFLVC introduces hierarchical feature learning and consensus semantics.

Q3: Why not learn a unified anchor graph? Performance.

A3: Anchor graphs on respective views may be more conducive to expressing the characteristics of their own views. A single graph structure may not adequately capture the intrinsic characteristics across all views. To confirm this, we conduct relevant experiments. IAG and UAG are the results based on individual and unified anchor graph respectively.

Q4: Interpretation about the clustering outputs and the practical significance.

A4: Our model introduces a alignment mechanism without the necessity of selecting a baseline view. It is adept at synchronizing with the anchor generation, and adeptly rearranges anchors within their original space, well preserving the data diversity. Our model incorporates the geometric properties among anchors into the anchor-sample similarity, more thoroughly uncovering the manifold structure inherent into samples. Besides, our model engages in the direct learning of consensus cluster indicators, consolidating multi-view information at the cluster-label level. Further, our model is equipped with linear complexity. Owing to these, our model yields stable results and is adept at handling large-scale scenes.

Q5: Restriction factors for the proposed method.

A5: The computing cost is $\mathcal{O}(m^2nv+dnm+m!v+m^3kv)$. In general, $m$, $v$ and $k$ are greatly smaller than $n$. $d$ is a constant and irrelevant to $n$. The computing cost is linear with respect to $n$. Compared to the square and cube, the factorial about $m$ needs more cost. Too large $m$ will induce expensive cost. In addition, the space overhead is $\mathcal{O}(nk)$. So, the proposed method is not limited by its space overhead. Further, combined with the sensitivity study, the performance is relatively robust to hyper-parameters. So, the method is mainly influenced by the anchor number.

Q6: Exposition on the alignment criticality.

A6: The works based on shared features (SF) typically derive consensus anchors rather than view-tailored anchors to establish similarity. This harnesses the complementary. The following experiments further show this.

In our model, the alignment mechanism builds pure self-expression affinities. If not aligning, the structure of anchor-anchor affinity would be chaotic, which will in turn impair the anchor-sample proximity, hindering the clustering performance. The following experiments validate this point. WOA is the results without our alignment.

In cases where the consistent information predominates over the complementary, it may be feasible to establish unified anchors to formulate similarity and thus potentially circumvent or mitigate the need for alignment. Nonetheless, given the inherent complexity of multi-view data, accurately quantifying the complementary and consistent information is usually a challenging task.

Q1: The introduction about the computational cost of permutation seems a bit concise.

A1: More details are provided here. Due to $\mathbf{A}_p\in{d_p\times m}$, $\mathbf{S}_p\in{m\times m}$, $\mathbf{B}_p\in{m\times k}$, $\mathbf{C}\in{k\times n}$ and $\mathbf{X}_p\in{d_p\times n}$, building $\mathbf{G}_p$, $\mathbf{H}_p$, $\mathbf{M}_p$ and $\mathbf{J}_p$ will require $\mathcal{O}(d_pm^2)$, $\mathcal{O}(m^3)$, $\mathcal{O}(mkn+m^2n)$ and $\mathcal{O}(d_pmn+mnk+m^2k)$ cost. Due to $\mathbf{T}_p\in{m\times m}$ consisting of 0 and 1, conducting traversal searching on one-hot vectors will take $\mathcal{O}(m!)$. So, updating the permutation takes $\mathcal{O}(d_pm^2+d_pmn+m^3+mkn+m^2n+m!)$.

Q2: In Algo 1, the stopping condition is missing.

A2: Thanks! We run the Algo 1 under $f(t)-f(t+1)<=10^{-3}f(t)$. $f(t)$ is the objective value at $t$-th iteration.

Q3: Employing a table format to introduce datasets.

A3: Good advice! We will present that in a table format to enhance its visual appeal.

Q4: Under consensus anchors, how is the performance? Is the permutation necessary?

A4: The paradigm based on consensus anchors extract a set of common anchors rather than multiple sets of view-specific anchors to build similarity. Although avoiding alignment, due to the lack of view-unique characteristics, this could not extract sufficient diverse features. To further demonstrate this, we organize experiments. CA and VA are the results based on consensus and view-related anchors respectively.

The reason of this could be that the view-exclusive representation that view-related (aligned) anchors contain outweighs the view-common information that consensus anchors contain.

Q5: From Eq.(8) to Eq.(9), why does it hold?

A5: For the objective, we have $\operatorname{Tr} \left(\mathbf{B} _p^{\top}\mathbf{H}_p\mathbf{B} _p \mathbf{C}\mathbf{C}^{\top} \right) \Leftrightarrow [\mathbf{B} _p^{\top}] _{j,:} [\mathbf{H}_p\mathbf{B} _p \mathbf{C}\mathbf{C}^{\top}] _{:,j} \Leftrightarrow [\mathbf{B} _p^{\top}] _{j,:}\mathbf{H}_p\mathbf{B} _p[\mathbf{C} \mathbf{C}^{\top}] _{:,j}$ and $\operatorname{Tr}\left(\boldsymbol{\alpha} _p^2\mathbf{C}\mathbf{X} _p^{\top}\mathbf{A} _p \mathbf{T} _p \mathbf{B} _p\right) \Leftrightarrow \left[\boldsymbol{\alpha} _p^2\mathbf{C}\mathbf{X} _p^{\top}\mathbf{A} _p\mathbf{T} _p\right] _{j,:}[\mathbf{B} _p] _{:,j}$ where we omit the $\min$ operator and $\mathbf{H}_p=\beta\mathbf{L _s}+\boldsymbol{\alpha} _p^2\mathbf{Q} _p$. $\mathbf{C}\mathbf{C}^{\top}$ is diagonal, and we have $[\mathbf{B}_p^{\top}] _{j,:}\mathbf{H}_p\mathbf{B} _p[\mathbf{C}\mathbf{C}^{\top}] _{:,j} \Leftrightarrow [\mathbf{B} _p] _{:,j}^{\top}\sum _{i=1}^n \mathbf{C} _{j,i}\mathbf{H}_p[\mathbf{B} _p] _{:,j}$. For the feasible region, $\mathbf{B} _p^{\top}\mathbf{B}_p=\mathbf{I} _k$ can be divided into $[\mathbf{B} _p] _{:,j}^{\top}[\mathbf{B} _p] _{:,j}=1$ and $[\mathbf{B} _p] _{:,j}^{\top}[\mathbf{B} _p] _{:,i}=0,i=1,2, \cdots,k,i\neq j,j=1,2,\cdots,k$. Further, $[\mathbf{B} _p] _{:,j}^{\top}[\mathbf{B} _p] _{:,j}=1$ can be written as $[\mathbf{B} _p] _{:,j}^{\top}\mathbf{I} _{m\times m}[\mathbf{B} _p] _{:,j}-1=0$. The $[\mathbf{B} _p] _{:,j}^{\top}[\mathbf{B} _p] _{:,i}=0,i=1,2,\cdots,k,i\neq j$ can be written as $\left[[\mathbf{B} _p] _{:,1},[\mathbf{B} _p] _{:,2},\cdots,[\mathbf{B} _p] _{:,j-1},[\mathbf{B} _p] _{:,j+1},\cdots,[\mathbf{B} _p] _{:,k}\right]^{\top}[\mathbf{B} _p] _{:,j}=\mathbf{0} _{(k-1)\times 1}$.

Q6: How to set $m$?

A6: We set it equal to the number of clusters. During updating $\mathbf{T}_p$, the objective form is $\operatorname{Tr}\left(\mathbf{T} _p^\top\mathbf{B}\mathbf{T} _p\mathbf{C}+\mathbf{T} _p^{\top}\mathbf{D}\right)$. Besides, the feasible region is discrete. These cause it being hard to solve. To this end, we adopt the traversal searching on one-hot vectors to obtain the optimal solution. This takes $\mathcal{O}(m!)$ computing cost. Too large $m$ will induce intensive time.

Q7: Why taking less time than CS? Possible reasons?

A7: CS needs to first form spectrum and then conduct embedding partitioning. These two procedures induce extra computing cost. On the other hand, we directly generate labels via binary learning. The labels can be get in a closed-form solution. It only compares the diagonal elements of $\mathbf{W}$ and the row elements of $\mathbf{Z}$. The element scale is $k$, which is small-sized.

Q1: Can the binary be further refined? How is the performance under orthogonality?

A1: Thanks. Orthogonal constraints (OC) could deteriorate semantic topological continuity and limit the model's expression ability. Moreover, they will change the value and distribution of anchors. The following experiments further illustrate the distinction. BE is the results based on binary elements.

BE outperforms OC in most cases, the reasons of which are that BE does not change anchor characteristics, and only rearrange them within the original space.

Q2: Somewhat sensitive to hyperparameters. Exploring potential implications of anchor noise.

A2: The parameter $\lambda$ is responsible for striking a balance between the reconstruction loss and the regularization of anchor self-expression, whereas $\beta$ modulates the degree of inter-view consistency. Inaccurate calibration may result in diminished performance or instability, particularly in the presence of noisy anchors.

Anchor noise: (1) It could potentially compel the model to assimilate the noise patterns, precipitating an over-fitting condition; (2) It could potentially render the loss surface irregular, complicating the optimization process; (3) It could predispose the model to gravitate towards spurious correlations.

Several potential strategies could be employed: (1) Implement a pre-filtering mechanism or confidence-based thresholds; (2) Develop a multi-anchor voting mechanism; (3) Integrate prior knowledge to dynamically adjust hyper-parameters; (4) Conduct dataset pre-processing to eliminate instances of anchor noise.

Q3: How does self-expression improve the anchor quality? Still functional under anchors with other means?

A3: Self-expression learning helps extract the geometric characteristics between anchors, and facilities the learning of anchors owing to the co-optimized mechanism. OSE-L and WSE-L are to validate the effectiveness of self-expression. OSE-L and WSE-L are the results without/with self-expression under no learning.

The following WSE+L and WSE-L are to show the effectiveness of learning.'+L' denotes having learning.

Besides, OSE-L and WSE-L show that under the anchors constructed by sampling, our mechanism is still functional.

Q4: How does the model perform under varying anchor quality and graph level?

A4: In the paper, we introduce a view-aware weighting to harmonize anchor significance on each view. OVA denotes the results without view-aware weighting.

Perhaps, an instance-aware adaptive weighting paradigm could be more advisable. Implementing anchor-wise importance calibration may yield more superior results since anchors on the same one view also could exhibit diverse importance.

About the performance at the graph similarity level, we first generate view-specific graph and then construct fusion (FGTC) to integrating complementarities .

Evidently, our model gathering information at the cluster-level receives better results in most cases.

Q1: The parameter searching may undermine the practical capability.

A1: Thanks! $\lambda$ governs the trade-off between error reconstruction and anchor self-expression, while $\beta$ adjusts the cross-view consistency guidance. They collaboratively modulate the model's capacity. Despite the different searching ranges, our model, as evidenced by the results in Table 1, with the suggested ranges, achieves more competitive data clustering under multiple datasets with diverse scales, which reveals that our model is suitable for various scenes.

The parameter searching indeed compromises practical applicability to some extent, particularly in resource-constrained scenarios. Developing a dynamic parameter derivation mechanism based on data characteristics will be a compelling research direction, and we will conduct systematic investigations in future work.

Q2: The geometric properties of feasible region about permutation should be systematically characterized.

A2: Its feasible region consists of discrete elements, 0 and 1. There is only one 1-element in every column and row. These guarantee that the permutation only rearranges anchors in their original space, and does not alter the values of learned anchors.

Besides, its objective is $\operatorname{Tr}\left(\mathbf{T} _p^\top \mathbf{G} _p \mathbf{T} _p \hat{\mathbf{A}} _p + \mathbf{T} _p^{\top} \hat{\mathbf{B}} _p\right)$ where $\hat{\mathbf{A}} _p=\lambda\mathbf{H} _{p}+\boldsymbol{\alpha} _p^2\mathbf{M} _p-2\lambda\mathbf{S} _{p}^{\top}$ and$\hat{\mathbf{B}} _p=-2\boldsymbol{\alpha} _p^2 \mathbf{J} _{p}$. It exhibits quadratic operation about permutation elements and inherent non-separability, which causes difficulties in optimizing. Note that the permutation is with the size of $m\times m$, we can utilize one-hot vectors to constitute it.

Q3: A fundamental exploration for baseline-view-free mechanism.

A3: This approach rearranges anchors without requiring any baseline views. Given that the misalignment arises from the differing order of anchors, we link each view to a learnable permutation, which allows for the flexible transformation of anchors within the original space. Moreover, it is compatible with anchors in an unified framework, and collaborates with their learning process. Selecting a baseline view introduces complicated solving procedure. An improperly chosen baseline view will also lead to inaccurate graph structure fusion. In contrast, we do not rely on any baseline views and automatically rearranges anchors. Besides, it is also proven to be with linear complexity, and hence does not harm the overall efficiency.

Q4: Do the cluster indicators affect the overall efficiency? How to mitigate these factors?

A4: Combined with Eq.(13), it mainly involves $\mathbf{W}$ and $\mathbf{Z}$. So, updating the cluster indicators will take $\mathcal{O}(d _pmk+d _pk^2+km^2+k^2m+nd _pm+nm^2+nmk)$ cost. Generally, $m$ and $k$ are largely smaller than $n$. $d_p$ is a constant and irrelevant to $n$. As a result, the cost on cluster indicators is linear to $n$. So, it does not affect the overall efficiency.

Besides, the coefficients related to $n$ are $m$, $k$ and $d_p$, while $k$ is an inherent characteristic of datasets, and $m$ is set equal to $k$ in experiments. So, we can decrease the feature dimension to further improve the efficiency.

Q5: What is the reason for no-spectrum strategy spending less time than traditional scheme?

A5: The spectrum generation process and subsequent embedding grouping result in extra computational expense. Besides, we utilize binary learning to directly formulate cluster labels. This only involves the element comparing between two small-sized matrices $\mathbf{W}$ and $\mathbf{Z}$.

Q6: How is the performance under anchors with the same dimension.

A6: Thanks! Via projection, we indeed can make all anchors have the same dimensions (SD). However, even with the same dimensions, due to anchors still being generated on each individual view, the anchor order across views could remain inconsistent. So, the spatial misalignment still exists. The following table summaries the comparisons. DD is the results under anchors with original diverse dimensions.

The paradigm using anchors with SD produces inferior results, the reasons of which could be that the projecting operation causes information loss and degenerates multi-view diversity, weakening the performance.