Adaptive Instance-wise Multi-view Clustering

Venue: acmmm_org_ACMMM_2024_Conference
Published: 2024-04-07 15:41:52

Abstract: Multi-view clustering has garnered attention for its effectiveness in addressing heterogeneous data by unsupervisedly revealing underlying correlations between different views.
As a mainstream method, multi-view graph clustering has attracted increasing attention in recent years. Despite its success, it still has some limitations. Notably, many methods construct the similarity graph without considering the local geometric structure and exploit 
coarse-grained complementary and consensus information from different views at the view level.
To solve the shortcomings, we focus on local structure consistency and fine-grained representations across multiple views. Specifically, each view's local consistency similarity graph is obtained through the adaptive neighbor. Subsequently, the multi-view similarity tensor is rotated and sliced into fine-grained instance-wise slices. Finally, these slices are fused into the final similarity matrix. Consequently, cross-view consistency can be captured by exploring the intersections of multiple views in an instance-wise manner. We design a collaborative framework with the augmented Lagrangian method to refine all subtasks towards optimal solutions iteratively. Extensive experiments on several multi-view datasets confirm the significant enhancement in clustering accuracy achieved by our method.

Main paper: 
 related work: 
 clustering is the task of grouping a set of objects in such a way that objects in the same group (called a cluster) are more similar to each other than to those in other groups. In the era of big data, there are more and more multi-view data. Multi-view clustering has attracted increasing attention in recent years by aiming to exploit complementary and consensus information across multiple views.In the past decade, multi-view graph clustering has been widely used as a mainstream method. However, traditional graph-based clustering methods have historically prioritized similarity construction, relying on a pre-determined data graph to segment data. These methods, however, introduce a significant dependency on the input affinity matrix, making clustering outcomes sensitive to the quality of the initial data representation. Recognizing this limitation, an innovative clustering method proposed by [19] introduces a transformative perspective. This method aims to enhance the acquisition of the data similarity matrix by dynamically assigning adaptive and optimal neighbors for each data point, considering local distance. A series of multi-view clustering methods have emerged in response to this paradigm shift. These approaches strive to address the challenges posed by traditional methods to improve the construction of the affinity matrix. Notable strategies include the automatic allocation of proper weights for each view [17] , leveraging the graph smoothness assumption [6] , devising a series of exponential functions for diverse scenarios [16] , efficiently integrating graph learning with the fusion process [25] , and concurrently harnessing graph information and embedding matrices [23] . These significant advancements depart from the conventional dependence on predetermined data graphs, ushering in a new era of more adaptive and sophisticated approaches to multi-view clustering. Moving away from rigid structures and embracing adaptability, these innovations empower clustering methods to respond dynamically to the intricacies and nuances inherent in diverse datasets, thereby enhancing multi-view clustering techniques' overall effectiveness and robustness.It is crucial to highlight that the methods mentioned above aim to achieve a representation matrix with a primary focus on a vieworiented perspective. To delve into more specifics, it is evident that these methods undertake a sequential computation of one view at a time, subsequently consolidating their results at the view level. This approach, in turn, yields a coarse-grained view-level representation, wherein information integration occurs on a broader scale [21] . While effective for obtaining an overarching perspective and the complementary information from diverse modalities can easily be measured, this methodology may fail to capture the subtleties and intricacies within individual views. As a result, the representation matrix obtained may lack the granularity required for a more nuanced and detailed analysis of the underlying data structure. However, it's important to emphasize that the adaptive neighbor strategy scrutinizes the local connections inherent within the data. This signifies a meticulous examination of the intricate relationships existing in the local context of the dataset [27] . Consequently, the advantage offered by the adaptive neighbors strategy is susceptible to diminishing within a coarse-grained learning framework, where the nuanced details of local connections may not be adequately captured. Unlike the aforementioned MVC approaches, our proposed approach can grasp the local correlations among samples from various views and effectively eliminate redundant or erroneous information between these views. 
method: 
 In this section, we first provide the notations used throughout the paper. Then, we derive the objective function of our method and present its optimization algorithm.Notation: X = X (1) , . . . , X (𝑚) ∈ R 𝑑 𝑣 ×𝑛 is a multi-view data, 𝑑 𝑣 , 𝑛, 𝑚 is the feature dimension of X (𝑣) , number of samples, and number of views, respectively. S = S (1) , . . . , S (𝑚) ∈ R 𝑛×𝑛 is the similarity matrices generated from each view with adaptive neighbors. S ∈ R 𝑛×𝑛×𝑚 is a tensor composed of similarity matrices of all 𝑚 views, S 𝑖 ∈ R 𝑛×𝑚 is the 𝑖-th frontal slice of rotated S. C ∈ R is the optimal fused similarity matrix.Similarity learning is a critical factor that determines the clustering result. Inspired by [19] , the local connectivity of the data point can be mined from its neighbor data points, which helps improve the quality of the similarity matrix. Take the original data X = {𝑥 1 , 𝑥 2 , . . . , 𝑥 𝑛 } as an example. For simplicity, we employ Euclidean distance to learn the probabilistic 𝑘-nearest neighbors.For a data point 𝑥 𝑖 ∈ R 𝑑 𝑣 , all 𝑛 data points in X can be regarded as connected neighbors with different probability 𝑠. The proximity of a data point to 𝑥 𝑖 corresponds to a higher probability. Naturally, 𝑥 𝑖 -𝑥 𝑗 can be employed to gauge the Euclidean distance between two data points, and the optimal neighbors of 𝑥 𝑖 can be determined by the following objective function:EQUATIONEq. ( 1) has a straightforward solution, where only the nearest point has a probability of 1 while all others have 0. This leads to only similarity matrix tensor one nearest neighbor of 𝑥 𝑖 can be found. An alternative extreme solution is to disregard distance information completely: minS 1 ∈ ℝ 𝑛×𝑛 S 2 ∈ ℝ 𝑛×𝑛 S 3 ∈ ℝ 𝑛×𝑛EQUATIONwhere all data points have same probability 1 𝑛 . Considering both of them, the optimal result should be balanced between Eq. ( 1) and Eq. ( 2): minEQUATIONwhere the second term is a regularization constraint. It is clear that Eq. ( 3) can be extended to multi-view domain:min s (𝑣) 𝑖 𝑇 1=1,0≤s (𝑣) 𝑖 ≤1 𝑚 ∑︁ 𝑣=1 𝑛 ∑︁ 𝑗=1 𝑥 (𝑣) 𝑖 -𝑥 (𝑣) 𝑗 2 2 𝑠 (𝑣) 𝑖 𝑗 + 𝜆𝑠 (𝑣) 𝑖 𝑗 2 , (4)The optimal neighbor assignment matrix S (𝑣) is precisely the similarity matrix encompassing the local geometric structure required for the multi-view clustering task.Existing multi-view methods usually fuse multi-view complementary information in view-wise, which neglects the local correlation among samples from different views and disregards certain redundant or erroneous information between views.We performed multi-view fusion at the instance level to enhance the fusion performance. This approach captures more local crossview consistency and minimizes the impact of extra or inaccurate details. Refers to [4, 29] , we perform a simple and effective transformation to achieve that. Firstly, the similarity matrices of multiple views {S (𝑣) ∈ R 𝑛×𝑛 } 𝑚 𝑣=1 are concatenated to a tensor S ∈ R 𝑛×𝑛×𝑚 . Secondly, the tensor is rotated and sliced in the first dimension, and the 𝑖-th frontal slice S 𝑖 ∈ R 𝑛×𝑚 is the cross-view fusion of sample 𝑖. After obtaining 𝑛 slices, we perform instance-wise fusion to calculate the fused similarity matrix:EQUATION)w 𝑖 is the weight of 𝑖-th slice and c 𝑖 is the corresponding column in 𝐶 that integrates consistent information of sample 𝑖 from multiple views.Lastly, combine Eq. ( 4) and Eq. ( 5) we formulate the objective function: minEQUATIONwhere C ∈ R 𝑛×𝑛 is the fused simalirity matrix. A standard spectral clustering is executed with optimal C to obtain the final results. 
optimization: 
 As S 𝑖 is closely related to S (𝑣) and can not be decomposed into elemental forms s 𝑖 𝑗 . With augmented Lagrangian method (ALM) [20] , we introduce an intermediate variable J (𝑣) for each view: min EQUATIONEQUATION)where 𝜌 is penalty term and E (𝑣) is the Lagrangian multiplier.[t] [1] Multi-view data X (𝑣) (𝑣 = 1,2,...,𝑚), parameter 𝛼 and 𝛽. Clustering result. Update S (𝑣) according to Eq. ( 31). Update J (𝑣) by solving Eq. ( 17). Update W according to Eq. (20) . Update C according to Eq. ( 23). Update Lagrangian multiplier E (𝑣) by:EQUATIONconvergeConduct the standard spectral clustering on the optimal graph C to obtain the final clustering result.According to Eq. ( 8), S (𝑣) is associated with the following function: minEQUATION)It is independent of different 𝑖 so that we can solve the following problem individually for each 𝑖, denote 𝑥 𝑖 𝑗 , the problem can be written in vector form as: minEQUATION)Note that S (𝑣) for each view is independent. Hence we can update S (𝑣) one by one, minEQUATION)The solution to Eq. ( 14) will be detailed later.When the other variables are fixed, Eq. ( 8) become: minEQUATIONthen transform it into instance-wise form: minEQUATIONBy solving the first derivative of J 𝑖 , we have:EQUATIONThe part of Eq. ( 8) with respect to W is:EQUATIONDenote 1c 𝑇 𝑖 -J 𝑖 ∈ R 𝑚×𝑛 as A 𝑖 , and simplify the above functionEQUATIONSimilarly, extreme values can be calculated using the derivation:EQUATIONEQUATION)For C we need to optimize:EQUATIONReformulate it in a vector form, we have: Based on Eq. ( 22), we get the following compact formulation minmin c 𝑖 (𝛼 + 𝛽) c 𝑖 c 𝑇 𝑖 -2𝛼w 𝑇 𝑖 J 𝑖 c 𝑖 s.t. c 𝑖 ≥ 0, c 𝑖 1 = 1.EQUATIONWe can follow the same process in solving Eq. ( 14) to solve Eq. ( 23).The Lagrangian function of Eq. ( 14) isEQUATIONwhere 𝜓 and 𝜉 denote the Lagrange multipliers for the corresponding constraints.Setting 𝜕 L 𝜕s (𝑣) 𝑖 = 0 and according to the KKT condition [1] 𝑠 𝑖 𝑗 𝜉 𝑗 = 0, we have the following solution (denoted as 𝑠EQUATION)Without loss of generality, we order 𝑓EQUATION𝑖𝑛 from small to large. If we constrain 𝑠 𝑖 𝑗 having 𝑘 nonzero entries, we have:EQUATIONCombining Eq. ( 25) and the constraint sEQUATION, substituting Eq. ( 27) into Eq. ( 26),(𝑣)EQUATIONIn order to constrain s (𝑣) 𝑖to have exact 𝑘 nonzero elements, 𝜆 can be set toEQUATIONThus the overall optimal 𝜆 (denoted as 𝜆 * ) of a given dataset isEQUATIONAccording to Eq. ( 26), Eq. ( 27), and Eq. ( 29), the final solution forEQUATION 
experiment: 
 In this section, we compare our methodology with several state-ofthe-art multi-view clustering on benchmark datasets. The empirical results show that our model achieves competitive results. Five multi-view datasets are used in our experiment: BBC, BBC-Sport, BBC12, HW2, ORL, and cora. the UCI repository.The dataset consists of 2000 samples with two views. Each sample is one of the handwritten digits (0-9). ORL4 face dataset consists of 400 face images in 40 different themes in total. For each subject, the images are described in three features: facial expressions, facial details, and lighting. Cora5 dataset consists of 2708 scientific publications classified into one of seven classes.We selected 12 multi-view clustering methods for comparison: Multi-view Spectral clustering with Co-reg strategy (Co-reg) [10] , Multi-view Spectral Clustering with Co-train strategy (Co-train) [9] , Multi-view clustering and semi-supervised classification with adaptive neighbors (MLAN) [17] , Multi-view Clustering via Adaptively Weighted Procrustes (AWP) [18] , Multi-view Consensus Graph Clustering (MCGC) [32] , Multiple Partitions Aligned Clustering (mPAC) [5] , Multi-view Clustering via Cross-view Graph Diffusion (CGD) [24] , Fast parameter-free multi-view subspace clustering (FPMVS) [28] , Multi-view Subspace Clustering via Co-training (CoMSC) [13] , Consensus One-step Multi-view Subspace Clustering (COMVSC) [33] , Large-scale Multi-view Subspace Clustering (LMVSC) [7] , Metric Multi-view Graph Clustering(MMGC) [22] , Sample-Level Multi-View Graph Clustering(SLMVGC) [21] . Note that the above methods, except for the last one, perform graph fusion in a view-wise way. As for the last method, although it is instance-wise, it computes similarity graphs derived from topological manifold correlations, adept at capturing the entire topological manifold structure from the data space. In contrast, our approach using adaptive neighbor focuses more on the local geometric structure of data.Four criteria of clustering performance (Normalized Mutual Information (NMI), Accuracy (ACC), Purity, and F-Score) are shown in Table 1 -6, and the best results are bolded. The comparison algorithms were repeatedly tested 10 times using the parameter settings recommended by corresponding papers. In most cases, our method consistently outperforms others, showing its effectiveness. In Table 1, on BBC dataset, our method outperforms other methods by at least 1.75%, 3.04%, 1.75%, 1.21% in terms of ACC, NMI, Purity, and F-score. For BBCSport dataset, our method achieves improvements around 3.86%, 2.86% and 0.55% respectively, while 2.25% is lower in F-score. Our method demonstrates the most significant advancement on BBC12 dataset in Table 3 , and the corresponding improvements are 8.27%, 9.55%, 4.96%, 6.41%. Our method also yields competitive results for datasets where the majority of methods perform well, such as HW2 dataset. We can substantiate the effectiveness of mining the local geometric structure of similarity and integrating fine-grained information at the instance level by comparing empirical results. It should be pointed out that all the baselines, excluding the last one, suffer from a coarse-grained representation, resulting in suboptimal experimental outcomes. Regarding the last one, SLMVGC, our method demonstrates a discernible advantage in performance, which can be attributed to our empirical validation that local geometric structure captured by an adaptive neighbor is more tailored for fusion across views. There are four hyperparameters in our method: 𝛼, 𝛽, 𝜌, 𝑎𝑛𝑑𝜆. Note that 𝜌 is a common penalty parameter in ALM (𝜌 = 1.2), and 𝜆 is fine-tuned according to Eq. ( 30). Therefore, we only need to focus on the remaining two parameters. To assess the impact of different parameter settings on clustering results, we vary parameter 𝛼 and 𝛽 in 3𝑒 2 , 4𝑒 2 , 5𝑒 2 , 6𝑒 2 , 7𝑒 2 and 1𝑒 -2 , 5𝑒 -2 , 1𝑒 -1 , 5𝑒 -1 , 1𝑒 0 , 5𝑒 0 , 1𝑒 1 , respectively. Figure 3 shows the visual results in five benchmarks.According to the experiment result, we conclude that our method demonstrates stability across a large range of 𝛽 settings and is robust in the case of a small value for 𝛼.In this subsection, we experimentally verify the convergence of the proposed algorithm by reporting the corresponding loss value with the varying iterations on BBCSport and HW2. As shown in Figure 4 , one may observe that the flexibility exists to seek the optimal solution for each variable, leading to the eventual convergence of the algorithm to a local minimum within 25 iterations. The proposed optimization algorithm is very efficient and converges fast. Hence it is sufficient for all datasets to reach the best performance with the maximum iteration numbers of 25, as set in our experiment.To validate that fusing instance-wise slices can better capture the local consistency, we directly apply spectral clustering to the similarity matrix of the individual views of neighboring instances, i.e., spectral clustering is performed on each{S (𝑣) } 𝑚 𝑣=1 learned by Eq. 1, where 𝑚 is the number of views. As shown in Table 5 , similarity matrices learned on independent views with adaptive neighbor strategy are unreliable inputs for spectral clustering. MLAN, characterized as a view-wise fusion method that utilizes an adaptive neighbor strategy, demonstrates enhanced performance relative to methods employing a single-view approach. Furthermore, instancewise fusion contributes to the most significant improvement of multi-view clustering outcomes by offering fine-grained representations, thereby augmenting local consistency. 
conclusion: 
 In this paper, we propose exploiting local structure consistency across multiple views and focusing on mining fine-grained representations. The cross-view consistency in our model can also be captured by exploring the intersections of multiple views in an instance-wise manner. By utilizing the augmented Lagrangian method, our collaborative model can iteratively refine all subtasks towards optimal solutions. The empirical evaluation on various multi-view datasets shows that our method consistently outperforms other SOTAs in the majority of cases. Our method further  
: 
 form a consensus latent representation [15] . Thus, integrating information from multiple views brings remarkable benefits towards unsupervised data clustering, and the underlying information embedded in the data can be fully utilized, improving the clustering quality. There have been a growing number of studies and applications dedicated to multi-view clustering (MVC) in recent years [2, 3] , especially in real-world scenarios for anomaly detection in finance, data analysis in environmental science, and device collaboration in the Internet of Things.Based on the technical mechanisms of the current MVC methods, they can be classified into two categories [3] , namely heuristicbased MVC (HMVC) and neural networks-based MVC (NNMVC). Heuristic-based MVC extensively utilizes classical machine learning algorithms (Non-negative Matrix Factorisation, Graph Learning, Latent Representation Learning, and Tensor Learning) [8, 14] . Using prior knowledge and domain expertise, it uses heuristics to design clustering algorithms applicable to multi-view data. This approach emphasizes understanding data characteristics and problem context to guide algorithm design and parameter tuning for better adaptation to different application scenarios. Neural network-based MVC (NNMVC) is built on Deep Neural Networks (DNNs) with Deep Representation Learning or Deep Graph Learning [11, 31] . By creating complex neural network structures, the method can automatically learn high-level features and abstract representations in the data, effectively processing large-scale and high-dimensional multi-view data. With their notable nonlinear modeling capabilities, neural network-based MVC are well-equipped to identify complex relationships in data, offering valuable insights alongside traditional methodologies in complex scenarios.Numerous multi-view clustering methods have demonstrated notable success in empirical studies [30] . However, we find some urgent shortcomings in the heuristic-based MVC graph learning method. First, current graph-based multi-view clustering algorithms highly rely on data similarity learning. Nevertheless, they generally lean towards subspace learning and analogous strategies, thereby overlooking the nuances of the data's local geometric structure.Second, traditional methods usually fuse information from multiple views at the view level, which only considers coarse-grained information and reduces clustering accuracy.As shown in Figure 2 , we address the above issues simultaneously within a unified framework. As for the lack of local structure mining, we independently learn the similarity matrix of each view on local distance by assigning the adaptive and optimal neighbors. The local geometric structure directly implied by the data can be explored through the similarity propagation between neighbors. Regarding the fusion strategy, we obtain fine-grained information fusion in a self-weighted manner by instance-wise slicing of the multi-view similarity tensor. Finally, we introduce a unified model that learns both the adaptive similarity matrix and the instance-level structure of multi-view data to obtain better clustering results. In our collaborative model, we skillfully combine these two subtasks, alternatively driving each subtask toward the optimal solution with the augmented Lagrangian method. Experiments on several multiview datasets demonstrate that our proposed approach significantly improves clustering accuracy. 
 
 Appendix: https://www.kaggle.com/datasets/tavarez/the-orl-database-for-training-andtesting5 https://relational.fit.cvut.cz/dataset/CORA 


Decision: This paper focus on local structure consistency and fine-grained representations across multiple views, which is theoretically reasonable and technically sound. The structure of the paper is clear, and the experiment has achieved good performance. All reviewers give positive scores and tend to accept this work.

Reviews: review: paper_summary: paper_summary: This paper exploits the fine-grained consistency information by exploring the intersections of multiple views in an instance-wise manner, which contains the ideas on local similarity graph, multi-view similarity tensor, and slice fusion. Meanwhile, a collaborative framework with the augmented Lagrangian method is developed to refine all subtasks towards optimal solutions iteratively. Extensive experiments can show its effectiveness.
strength_weakness: strength_weakness: 1. The paper introduces a novel approach to multi-view clustering by focusing on local structure consistency and fine-grained representations across multiple views. 
2. The paper provides a solid theoretical foundation for its proposed method, which is mathematically sound and well-justified.
3. The method is evaluated extensively on several multi-view datasets.
4. The paper is well-organized and clearly written.
limitations: limitations: 1. The paper compares the proposed method with a limited set of baseline methods, especially recent neural network-based multi-view works.
2. The paper does not provide a thorough evaluation of the scalability of the proposed method.
paper_summary: paper_summary: In this paper, the authors perform fine-grained information fusion in a self-weighted manner by instance-wise slicing of the multi-view similarity tensor. A novel model that learns both the adaptive similarity matrix and the instance-level structure of multi-view data is introduced to obtain better clustering results. By skillfully combining these two subtasks, alternatively driving each subtask toward the optimal solution is obtained with the augmented Lagrangian method.
strength_weakness: strength_weakness: It is well motivated, the adaptive similarity matrix and the instance-level structure of multi-view data are well exploited simultaneously, which is impressive.

The experiments are sufficient and convincing. The comparison results demonstrate the effectiveness of the instance-wise learning strategy.

The paper is technically sound and overall well-written.
limitations: limitations: From Fig.1, I’m wondering what the essential differences between multi-view and multi-modal are? It seems they describe the same situation in some cases. 

The results of CoMSC are worse than this work except F-score, why is that? It needs more detailed explanation.

The font size in Figure 2 is a little small.
paper_summary: paper_summary: This paper focuses on local structure consistency and fine-grained representations across multiple views with the help of augmented Lagrangian method. Experiments on several multiview datasets demonstrate that our proposed approach significantly improves clustering accuracy.
strength_weakness: strength_weakness: 1. The method considers the local geometric structure and obtains view-specific similarity graphs using adaptive neighbors. This enables capturing detailed information within each view.

2. The method slices and fuses the multi-view similarity tensor at the instance level. By exploring the intersections of multiple views, it captures cross-view consistency, improving clustering performance.

3. The method employs the augmented Lagrangian method within a collaborative framework. This iterative approach refines subtasks towards optimal solutions, enhancing the accuracy of the clustering process.
limitations: limitations: 1. The ablation study is conducted by comparing the MLAN with the proposed method, why is that? The essential difference between MLAN and the proposed method should be pointed out clear. 

2. The overall presentation of the paper requires improvement. Clarity and coherence should be enhanced to ensure the reader can follow the content smoothly.

3. Some statements in the paper are confusing, particularly in the algorithm flow section (lines 365-374 on Page 4). It is necessary to clarify these statements to avoid any ambiguity or misinterpretation.

4. Given the abundance of notations used in the paper, including a notation table would greatly assist readers in better comprehending the content.
paper_summary: paper_summary: This paper proposes an adaptive instance-wise multi-view clustering method which aims to exploit local structure consistency across multiple views and recover the fine-grained representations. Extensive experiments on several multi-view datasets confirm the significant enhancement in clustering accuracy achieved by our method.
strength_weakness: strength_weakness: (a) A novel method for instance-wise MVC by utilizing adaptive local structure is proposed in this paper, and experiments demonstrate that the proposed approach significantly improves clustering accuracy.
(b) The ablation experiments are conducted to verify the effectiveness of each module.
limitations: limitations: (a) Note that there are several paper have been proposed to explore the adaptive local structure, then what's the difference between this paper and other papers, in terms of the adaptive local structure?
(b) The dataset Cora, instead of cora, would be better.