Fast Elastic-Net Multi-view Clustering: A Geometric Interpretation Perspective

Venue: acmmm_org_ACMMM_2024_Conference
Published: 2024-04-03 10:00:48

Abstract: Multi-view clustering methods have been extensively explored in the last decades. This kind of methods is built on the assumption that the data are sampled from multiple subspaces with low dimension and each group fits into one of these subspaces. The quadratic or cubic computation complexity produced by these methods is inevitable, resulting in the difficulty for clustering multi-view datasets with large scales. Some efforts have been presented to select key anchors beforehand to capture the data distributions in different views. Despite significant progress, these methods pay few attentions to deriving provably scalable and correct method for finding the optimal shared anchor graph from the geometric interpretation perspective. They also ignore to give a well balance between the connectedness and subspace preserving properties of the shared anchor graph. In this paper, we propose the Fast Elastic- Net Multi-view Clustering (FENMC) from a geometric interpretation perspective. We provide the geometric analysis in determining the optimal shared anchor graph based on the introduced elastic-net regularizer for fast multi-view clustering, where the elastic-net regularizer is built on the mixture of $L_2$ and $L_1$ norms. We also give a theoretical justification for the balance between the connectedness and subspace preserving properties of the shared anchor graph for multi-view clustering. Our experiments on different datasets show that the proposed method not only obtains the satisfied clustering performance, but also deals with large-scale datasets with high efficiency.

Main paper: 
 introduction: 
 In various computer vision tasks, including motion segmentation [5] , image representation [11] , feature extraction [7, 13, 18] and face clustering [10] , the high-dimensional datasets can be approximated by a union subspaces with low dimensions. The subspace clustering [28, 33] has been widely explored in recent decades, which recovers the underlying structure of data with low dimensions and assigns each data point to the corresponding subspace. Significant progress has been made in uncovering such underlying subspace representations and subspace clustering based on graph usually produces the satisfied performance among multiple approaches. As a result, the subspace clustering based on graph has received great attention and a large number of methods have been presented.Among these subspace clustering methods based on graph, some representive works are sparse subspace clustering [6] , least squares regression (LSR) [20] and low-rank representation (LRR) [17] . They learn an 𝑛 × 𝑛 graph to represent the pairwise similarity between data points and then use the learned graph as the input to the existing clustering algorithm, i.e., spectral clustering. Moreover, some subspace clustering networks [12] have been developed to enjoy the merit of discriminative feature representations achieved by deep neural networks. It typically requires O (𝑛 2 ) to obtain the graph and O (𝑛 3 ) for eigen-decomposition in spectral clustering algorithm, where 𝑛 is the total number of data points in dataset. Thus, these two steps inevitably restrict the subspace clustering application on the datasets with large scales.Recently, some research endeavors are devoted to accelerate subspace clustering [35] . For instance, Wang et al. [30] aimed to speed up the computation by adopting a data selection approach. You et al. [33] reduced the computation load based on the orthogonal matching pursuit. Peng et al. [22] converted the large-scale clustering issue as an out-of-sample problem. Alder et al. [1] combined the bipartite graph and sparse representation, resulting in a linear subspace clustering algorithm. Qin et al. [23] targeted at achieving an analytical, symmetrical and nonnegative similarity matrix for dealing with the data with large scales. Unfortunately, these accelerated subspace clustering methods usually target for the scenario with single view and fail to deal with the multi-view data.The heterogeneous feature representations usually provide complementary information [37] , i.e., a video might includes text, sounds and images [32] . As a result, multi-view subspace clustering methods have been exploited [2, 34] . For example, Cao et al. [2] studied both the diversity and consistency among different views. Zhang et al. [34] employed the latent space to perform subspace clustering. Qin et al. [24] explicitly extended the existing multi-view clustering in a semi-supervised manner and used small amount of supervisory information to construct an anti-block-diagonal indicator matrix. Compared with the methods for single view, these methods usually produce more desired results.Unfortunately, most existing multi-view subspace clustering methods encounter the scalability issue, which limits their real application on the dataset with large scales. Some multi-view clustering approaches for dealing with large-scale data have been developed [26] . For example, Han et al. [9] reduced the number of matrix multiplication in the optimization procedure by regarding the intermediate factor matrix as a matrix with diagonal structure. Kang et al. [15] studied smaller graphs for multiple views based on the built anchor bases. Wang et al. [29] explored the shared anchor graph in multi-view subspace clustering, which is guided by the consensus anchor bases in the data. Sun et al. [27] employed the underlying data distribution to learn anchor graph. Chen et al. [3] jointly obtained a more flexible and discriminative anchor representation and the cluster indicator with linear complexity. Despite significant progress, these methods pay few attentions to deriving a scalable and correct method for finding the optimal shared anchor graph in a provable manner from the geometric interpretation perspective. They also ignore to provide a well balance between the connectedness and subspace preserving properties of the shared anchor graph in multi-view subspace clustering.In this work, we propose a Fast Elastic-Net Multi-view Clustering (FENMC) from a geometric interpretation perspective to address the above two issues. To be specific, we introduce the elastic -net regularizer built on the mixture of 𝐿 2 and 𝐿 1 norms for the learned shared anchor graph in multi-view subspace clustering, where 𝐿 2 norm improves the connectivity and 𝐿 1 helps obtain a subspace preserving affinity. The geometry of the elastic-net regularizer is explored and we then adopt it for deriving a provably scalable and correct method in achieving the optimal shared anchor graph. Our analysis shows a geometric interpretation and theoretical justification for the balance between the connectedness and subspace preserving properties of the shared anchor graph in multi-view subspace clustering.The major contributions of this work include• We propose a Fast Elastic-Net Multi-view Clustering (FENMC) from a geometric interpretation perspective. We provide the geometric analysis in determining the optimal shared anchor graph based on the introduced elastic-net regularizer for fast multi-view clustering, where the elastic-net regularizer is built on the mixture of 𝐿 2 and 𝐿 1 norms as well as a refined-anchor algorithm is designed to achieve further efficiency. • We provide a geometric interpretation and theoretical justification for the balance between the connectedness and subspace preserving properties of the shared anchor graph based on the elastic-net regularizer for multi-view clustering. • We conduct extensive experiments on several multi-view datasets to show that the proposed method is able to obtain the satisfied clustering performance and handle large-scale datasets with high efficiency in terms of different metrics. 
related work: 
 As an efficient way, anchors or landmarks are adopted for scalable clustering on large-scale datasets. It usually selects relatively smaller number of data points termed anchors or landmarks to denote the neighborhood structure in the dataset. To be specific, we can build a small graph 𝑆 ∈ 𝑅 𝑚×𝑛 to measure the relationship between the entire dataset and the anchors with the guidance of 𝑚 anchors 𝐴 = {𝑎 1 , • • • , 𝑎 𝑚 } ∈ 𝑅 𝑑 ×𝑚 . The commonly used Gaussian kernel function can be employed to construct the graph 𝑆. However, it is not flexible enough in characterizing the complex data.We can treat 𝐴 as a dictionary and learn affinity matrix 𝑆 for subspace clustering as follows:EQUATIONwhere 𝜂 > 0 represents the balance parameter and 1 is a vector with all entries being one. It is observed that the above approach for constructing the graph is extremely efficient since the computation complexity is low. Likewise, the above model can be extended to the case for dealing with multi-view datasets and some recent works have incorporated anchor graphs into multi-view clustering. Liu et al. [19] combined graph construction and anchor learning for boosting clustering performance and imposed a graph connectivity constraint in the learning process. Yang et al. [31] used the multiple anchor graphs to achieve the efficient 𝐾-means clustering on multiview dataset. However, the existing methods pay few attentions to deriving a scalable and correct method for finding the optimal shared anchor graph in a provable way from the geometric interpretation perspective. These methods also ignore to give a well balance between the connectedness and subspace preserving properties of the shared anchor graph in multi-view subspace clustering. 
the proposed method: 
 In this part, we describe the proposed method in details, which includes the motivation, formulation and the complexity analysis.There is much redundancy in the multi-view dataset with large scales and a small number of data points are enough to reconstruct the underlying subspaces. The smaller matrix 𝑆 ∈ 𝑅 𝑚×𝑛 can be adopted to approximate the full matrix, where 𝑚 ≪ 𝑛. That is, 𝑆 is achieved based on the anchors 𝐴 ∈ 𝑅 𝑑 ×𝑚 and the dataset 𝑋 𝑝 for the 𝑝-th view. However, the existing multi-view clustering methods pay few attentions to deriving a scalable and correct method for finding the optimal shared anchor graph in a provable way from the geometric interpretation perspective. These methods also ignore to give a well balance between the connectedness and subspace preserving properties of the shared anchor graph in multi-view subspace clustering.Based on the assumption that a consensus subspace with low dimension is shared by the high-dimensional data from different views, the learned anchors are expected to be consistent in the consensus space. Given multi-view dataset {𝑋 𝑝 ∈ 𝑅 𝑑 𝑝 ×𝑛 } 𝑣 𝑝=1 with 𝑑 𝑝 and 𝑛 being the dimension and size of dataset, we define the projection matrix 𝑈 𝑝 and then align the consensus anchors 𝐴 for the 𝑝-th view. To bridge the gap between the connectedness and subspace preserving properties of the obtained anchor graph 𝑆, we introduce a mixed 𝐿 1 and 𝐿 2 norm 𝑟 (.) to the anchor graph. Here, the mixed norm is also called the elastic-net regularizer. The above process is formulated asEQUATIONwhere 𝜆 ∈ [0, 1] is the trade-off parameter for the two regularizers. Thus, the proposed method has the formulation as follows:minEQUATIONwhere 𝛼 2 𝑝 > 0 represents the parameter of weight coefficient to learn. The above optimization problem can be solved by solving each variable while fixing the others. For simplicity, we adopt the objective function 𝑓 (𝑠; 𝑈 𝑝 𝐴) to denote the optimization problem in Eq. ( 3) and omit the constraints of variables in this formulation for the 𝑝-th view, defined asEQUATION)Without loss of generality, {𝑢 𝑝 𝑗 𝑎 𝑗 } 𝑛 𝑗=1 and 𝑥 𝑝 are assumed to be normalized in the manner of unit 𝐿 2 norm. The above model then calculates 𝑠 * (𝑈 𝑝 𝐴) := arg min 𝑠 𝑓 (𝑠; 𝑈 𝑝 𝐴).(EQUATIONFor clarity, we adopt the notation 𝑠 * in place of 𝑠 * (𝑈 𝑝 𝐴) and fix 𝛼 in Eq. ( 4) for the following analysis. Due to the convex property of 𝑓 (𝑠; 𝑈 𝑝 𝐴), we can guarantee that the obtained 𝑠 * (𝑈 𝑝 𝐴) is unique.In the following part, we provide the detailed analysis of the solution to the proposed method from a geometric interpretation perspective and then design a refined-anchor algorithm to achieve further efficiency. We first give the concept of the trigger point in the following. Definition 1. (Trigger Point) The trigger point regarding the optimization problem Eq. ( 5) isEQUATIONwhere 𝜚 > 0 is the parameter. We adopt 𝜗 to represent 𝜗 (𝑈 𝑝 𝐴) for simplicity and find that the trigger point can be calculated when the optimal 𝑠 * is obtained. Likewise, the solution 𝑠 * can be directly achieved once the trigger point 𝜗 is known, which is shown in the theorem as follows.Theorem 1. The optimal 𝑠 * to Eq. ( 5) satisfiesEQUATIONwhere ∇ 𝜆 (.) represents the soft-thresholding operator. It is defined as0 if |(𝑈 𝑝 𝐴) 𝑇 𝜗 | ≤ 𝜆 and 𝑠𝑔𝑛((𝑈 𝑝 𝐴) 𝑇 )(|(𝑈 𝑝 𝐴) 𝑇 | -𝜆) otherwise.Proof. Due to the convex property of Eq. ( 5), 𝑠 * is unique optimal if and only if it satisfies the optimally condition based on the partial derivative value regarding 𝑠 * as:EQUATIONwhere 𝑧 ∈ 𝜕∥𝑠 * ∥ 1 . We then take the soft-thresholding on Eq. ( 8) for both sides by ∇ 𝜆 (.). Thus, Eq. ( 7) in Theorem 1 can be obtained.The reverse implication can be proved by establishing that the 𝑗-th row of Eq. ( 8) is satisfied when the corresponding row in Eq. ( 7) holds for three cases 𝑠 * < 0, 𝑠 * = 0 and 𝑠 * > 0 separately. As shown in Theorem 1, the value of 𝑠 * is determined by the angle between 𝑢 for representing the coherence. The trigger region is formally defined as follows.Definition 2. (Trigger Region) The trigger region for the optimization problem Eq. ( 5) is defined asEQUATIONAccording to Theorem 1 and the above definition, we can obtain that 𝑠 * ≠ 0 if and only if 𝑢 𝑝 𝑗 𝑎 𝑗 ∈ Γ(𝑈 𝑝 𝐴). The properties of solution can be captured by the trigger region when new columns are added or columns are removed from 𝑈 𝑝 𝐴, which gives us the key insight in designing the refined-anchor method. The basic measure is for solving the reduced-scale problem determined from the trigger region and the obtained anchor is called refined anchor. We denote the refined anchor at iteration 𝑖 as 𝑇 𝑖 and select the next refined anchor 𝑇 𝑖+1 from the trigger region Γ(𝑈𝑝 𝑇 𝑖 𝐴 𝑇 𝑖 ), where 𝑈 𝑝 𝑇 𝑖and 𝐴 𝑇 𝑖 denote the submatrix of 𝑈 𝑝 and 𝐴 with columns indexed by 𝑇 𝑖 , respectively. This iterative process is terminated when 𝑇 𝑖+1 no longer contains any new data points. To show the convergence of this refined-anchor method, we give the lemma as follows.Lemma 1.EQUATIONProof. We first define the sets EQUATIONWe then achieve Theorem 2 with the guidance of Lemma 1, which is shown in the following. Theorem 2. The refined-anchor algorithm converges to the optimal 𝑠 * (𝑈 𝑝 𝐴) in a finite number of iterations.Proof. We find that the objective function is guaranteed to be decreasing for each iteration before the termination happens according to Lemma 1. Since there are limited number of entries in 𝑇 , we conclude that the refined-anchor algorithm converges in a finite number of iterations with 𝑇 𝑖+1 ⊂ 𝑇 𝑖 . We construct 𝑠 * such that 𝑠 ) are desired to be dense for guaranting that the affinity graph is well-connected. That is, the connectedness and subspace preserving properties are two conflicting goals. We then provide the detailed analysis of the tradeoff between the connectedness and subspace preserving properties from a geometric interpretation perspective and the sufficient conditions when the anchor graph is subspace preserving.We perform the detailed analysis upon the optimization problem min 𝑠 𝑓 (𝑠; 𝑢 𝑝 𝑗 𝑎 𝑗 , (𝑈 𝑝 𝐴) 𝑙 -𝑗 ), where (𝑈 𝑝 𝐴) 𝑙 -𝑗 denotes (𝑈 𝑝 𝐴) 𝑙 in the Ξ 𝑙 subspace with the 𝑗-th column removed. We regard anchors from other subspaces as newly added columns to (𝑈 𝑝 𝐴) 𝑙 -𝑗 and achieve the geometric result as follows.Theorem 𝑝 𝑗 𝑎 𝑗 , (𝑈 𝑝 𝐴) -𝑗 ) = 𝑃 • [𝑠 * (𝑢 𝑝 𝑗 𝑎 𝑗 , (𝑈 𝑝 𝐴) 𝑙 -𝑗 ) 𝑇 , 𝑶 𝑇 ] 𝑇 if 𝑥 𝑒 ∉ Γ(𝑢 𝑝 𝑗 𝑎 𝑗 , (𝑈 𝑝 𝐴) 𝑙 -𝑗) for all 𝑥 𝑒 ∉ Ξ 𝑙 , where 𝑃 denotes some permutation matrix. Moreover, the vector of 𝑠 * (𝑢 𝑝 𝑗 𝑎 𝑗 , (𝑈 𝑝 𝐴) -𝑗 ) corresponding to the data points outside of Ξ 𝑙 is nonzero if any 𝑥 𝑒 ∉ Ξ 𝑙 in the trigger region Γ(𝑢 𝑝 𝑗 𝑎 𝑗 , (𝑈 𝑝 𝐴) 𝑙 -𝑗 ). Thus, the obtained solution is incorrect in determining the 𝑙-th space.The above theorem shows that 𝑠 * (𝑢 𝑝 𝑗 𝑎 𝑗 , (𝑈 𝑝 𝐴) -𝑗 ) is subspace preserving if and only if all data points from other subspaces lie outside the trigger region. We desire a small trigger region to ensure that the solution is subspace preserving, while need a large trigger region to ensure the connectedness. It further highlights the tradeoff between connectedness and subspace preserving properties. The elastic-net promotes sparse and dense solution by 𝐿 1 and 𝐿 2 regularizations. Thus, as 𝜆 increases from 0 towards 1, one should expect that the trigger region decreases in size.To solve the optimization problem in Eq. ( 3), we adopt an alternate minimizing algorithm to optimize each variable with others being fixed.𝑺-subproblem: By fixing the other variables, the objective function regarding 𝑆 is minEQUATIONWe then rewrite it as the Quadratic Programming (QP) problem as follows:EQUATIONwhereℎ 𝑇 = -2 𝑣 𝑝=1 (𝑋 𝑝 :,𝑗 ) 𝑇 𝑈 𝑝 𝐴 + 𝜆𝜕∥𝑠 * ∥ 1 and 𝑊 = 2( 𝑣 𝑝=1 𝛼 2 𝑝 + 1-𝜆 2 )𝐼 .𝑼 𝒑 -subproblem: By fixing the other variables, the objective function regarding 𝑈 𝑝 is minEQUATIONWe then transform it into the following form:EQUATIONwhere 𝐺 𝑝 = 𝑋 𝑝 𝑆 𝑇 𝐴 𝑇 . The optimal 𝑈 𝑝 is 𝑊 𝑉 𝑇 , where 𝑊 and 𝑉 are singular matrices for 𝐺 𝑝 . 𝑨-subproblem: By fixing the other variables, the objective function regarding 𝐴 is minEQUATIONLikewise, we can obtain the formulation as follows:EQUATIONwhere 𝐸 = 𝑣 𝑝=1 𝛼 2 𝑝 (𝑈 𝑝 ) 𝑇 𝑋 𝑝 𝑆 𝑇 . The optimal 𝐴 can be obtained by 𝛥Γ 𝑇 , where 𝛥 and Γ 𝑇 are singular matrices for 𝐸.𝜶 𝒑 -subproblem: By fixing the other variables, the objective function regarding 𝐹 is minEQUATIONwhere𝑀 𝑝 = ∥𝑋 𝑝 -𝑈 𝑝 𝐴𝑆 ∥ 2 𝐹 .According to the Cauchy-Buniakowsky-Schwarz inequality, the optimal 𝛼 𝑝 isEQUATION)Due to the optimal solution and convex property of each subproblem, the objective function monotonically decreases in each iteration until convergence. We summarize the whole process for solving the proposed FENMC in Algorithm 2. Then the refined-anchor algorithm as shown in Algorithm 1 can be adopted to achieve further efficiency.  
experiments: 
 We perform experiments in this part to demonstrate the performance of the proposed method in terms of effectiveness and efficiency on several datasets. We conduct all experiments on a standard Window PC with AMD Ryzen 5 1600X 3.60 GHz.  
 
 Appendix:  


Decision: This paper studies the scalability issue in anchor based multi-view clustering from a geometric interpretation perspective. It devises an elastic-net regularizer by combining L2 norm and L1 norm to receive an adaptive balance between connectedness and subspace-preserving properties. Then, it provides a theoretically reasonable and technically sound justification. After rebuttal and discussion, all reviewers are positive about this paper. So, acceptance is recommendated.

Reviews: review: paper_summary: paper_summary: This paper proposes the Fast ElasticNet Multi-view Clustering (FENMC) from a geometric interpretation perspective. The authors provide the geometric analysis in determining the optimal shared anchor graph based on the introduced elasticnet regularizer for fast multi-view clustering, where the elastic-net regularizer is built on the mixture of 𝐿2 and 𝐿1 norms. The authors also give a theoretical justification for the balance between the connectedness and subspace preserving properties of the shared anchor graph for multi-view clustering.
strength_weakness: strength_weakness: 1 The authors provide the geometric analysis in determining the optimal shared anchor graph based on the introduced elasticnet regularizer for fast multi-view clustering.

2. The authors also give a theoretical justification for the balance between the connectedness and subspace preserving properties of the shared anchor graph for multi-view clustering.
limitations: limitations: 1. In the experimental part, the authors give the running time of methods on data sets, so the authors need to add the description of device memory in the experiment.

2. The subsection on the Running time contains relatively little information on the results of the experiments, and a little more description and analysis of the results could be added as appropriate.

3. The best performance in the table of experimental results can be bolded to make the results more visible.

4. The authors should confirm that the formats of references are consistent and correct.
paper_summary: paper_summary: The paper focuses on the problem of multi-view clustering from a geometric interpretation standpoint, introducing a Fast Elastic-Net Multi-view Clustering (FENMC) method. The primary goal is to tackle the scalability challenges encountered by existing methods when clustering large-scale multi-view datasets. The FENMC method incorporates an elastic-net regularizer that combines L2 and L1 norms to achieve a balance between connectedness and subspace-preserving properties within the shared anchor graph. It offers a theoretical justification for this balance and presents experimental results on various datasets to demonstrate the performance and efficiency of the proposed method.
strength_weakness: strength_weakness: The paper presents several strengths in its approach to clustering large-scale multi-view datasets. Firstly, it integrates an elastic-net regularizer that balances L2 and L1 norms, leading to a geometrically grounded and scalable solution for constructing an optimal shared anchor graph. Secondly, the FENMC method provides a geometric interpretation and theoretical justification for the balance between connectedness and subspace preserving properties within the graph. Lastly, the method's clear formulation, complexity analysis, and experimental results contribute to its ease of implementation and improvements in clustering performance across various datasets of considerable scale.
limitations: limitations: The manuscript would benefit from a more detailed explanation of the geometric interpretation perspective and how the proposed method differs from existing approaches in finding the optimal shared anchor graph. Additionally, incorporating more recent anchor graph-based methods in the comparative experiments would provide a more comprehensive evaluation. Furthermore, the relationship between the theorems presented and the overall model needs to be clarified, specifying what each theorem proves and how these results support the proposed method. A thorough review and correction of the notation used throughout the manuscript are necessary to ensure consistency and readability.
paper_summary: paper_summary: This paper proposes a Fast Elastic-Net Multi-view Clustering (FENMC) from a geometric interpretation perspective. It provides the geometric analysis in determining the optimal shared anchor graph based on the introduced elastic-net regularizer for fast multi-view clustering, where the elastic-net regularizer is built on the mixture of 𝐿2 and 𝐿1 norms as well as a refined-anchor algorithm is designed to achieve further efficiency.
strength_weakness: strength_weakness: 1. A geometric interpretation and theoretical justification for the balance between the connectedness and subspace preserving properties of the shared anchor graph based on the elastic-net regularizer for multi-view clustering are given in this paper.
2. The paper is well-organized and easy to be understood by the readers.
3. Extensive experiments on several multi-view datasets are conducted to show that the proposed method is able to obtain the satisfied clustering performance and handle large-scale datasets with high efficiency in terms of different metrics
limitations: limitations: 1. The best results in Tables 1-3 can be bolded to better show the performance gains.
2. N/A in line 3 of Section 4.5 can be denoted by “N/A” for better clarity.
3. The second-best results in Tables 1-3 can also be highlighted to make the results more visible.
paper_summary: paper_summary: A Fast ElasticNet Multi-view Clustering (FENMC) from a geometric interpretation perspective is designed in this paper. The authors provide the geometric analysis for fast multi-view clustering, where the elastic-net regularizer is built on the mixture of 𝐿2 and 𝐿1 norms. They also give a theoretical justification for the balance between the connectedness and subspace preserving properties of the shared anchor graph for multi-view clustering. Experiments on different datasets show that the proposed method not only obtains the satisfied clustering performance, but also deals with large-scale datasets with high efficiency.
strength_weakness: strength_weakness: 1. The authors give the geometric analysis in determining the optimal shared anchor graph based on the introduced elasticnet regularizer for fast multi-view clustering.

2. Experiments on different datasets show that the proposed method not only obtains the satisfied clustering performance, but also deals with large-scale datasets with high efficiency.
limitations: limitations: 1. The authors need to give the device memory in the experiment for the proposed FENMC.

2. The reason for the anchor number selection can be further analyzed in the experiment.

3. Why the parameter \lambda is selected as 0.0001, 0.001, 0.01, 0.1 and 1 for parameter study in the experiment.