Lifelong Multi-view Spectral Clustering

1 Introduction

The classical spectral clustering algorithm was first proposed by [Ng et al., 2001], which performs dimensionality reduction by using the spectrum of the similarity matrix constructed from data before clustering. In the past decades, it has been used in many areas, such as web classification [Zhou and Burges, 2007], text mining [Janani and Vijayarani, 2019], image segmentation [Chahhou et al., 2014], speech recognition [Lin et al., 2019] and machine learning [Sun et al., 2020b]. However, most methods are only applicable to single-view data, while as the number of sensors grows on the Internet-of-Things, data from different sources or styles are more common and publicly available [Huang et al., 2021]. Another key issue is that they usually rely on a fixed set of tasks. When encountering an online environment with unknown amounts of consecutive tasks, they need to repeatedly access data from previous tasks. In real-world applications, like mobile apps or web servers, this may bring high memory consumption and computing work. In this paper, we focus on applying a lifelong multi-view clustering framework to common spectral clustering, enabling it to overcome the shortcomings mentioned above.

∗Corresponding author.

The lifelong machine learning model is trained over a sequence of tasks, which utilizes knowledge from past tasks to help future tasks [Thrun and Mitchell, 1995], meanwhile, alleviates catastrophic forgetting on past tasks. It could be broadly categorized into three categories [De Lange et al., 2019; Masana et al., 2020]: Architecture-based, Regularization-based, and Memory-based methods. In the past decade, It has been successfully adopted into supervised learning [Ruvolo and Eaton, 2013], unsupervised learning [Liu et al., 2016], semi-supervised learning [Mitchell et al., 2018], and reinforcement learning [Ammar et al., 2015]. Inspired by [Sun et al., 2020a], a memory-based method is applicable to solve continuous clustering tasks. A school website clustering problem on text-image web data could be an example. The semantic meaning of teacher web is different from student web, so they should be divided into two clusters. Tasks from different schools can be considered as sequence tasks, the correlation information of teacher or student websites between two schools is similar, so knowledge learned from the past task could be beneficial for future tasks. Although the concept has been proposed for more than 20 years, research in multi-view clustering, a topic in data mining, has not been extensive.

Inspired by the scenario mentioned above, we consider establishing a lifelong multi-view clustering method based on spectral clustering tasks. The problem is how to use the accumulated knowledge to improve performance on future tasks and update knowledge over lifetime. There are two assumptions considered in our paper: 1) Cluster Space Correlation, multiple clustering tasks should have a consistent latent cluster space. For instance, there are two cluster centers(teacher, student) on the website of school A, while school B obviously has the same centers; 2) Feature Embedding Correlation, which sharing between different tasks should be the same. In particular, the feature embedding of the teacher website should be the same, because the semantic meaning of the web(teacher or student) is similar between schools A and B.

In this paper, we propose a lifelong multi-view spectral clustering framework (LMSC) as shown in Figure 1. According to the mentioned two correlations, we use two viewspecific knowledge libraries to transfer knowledge among consecutive tasks and alleviate catastrophic forgetting. They are the Orthogonal Basis Library and Feature Embedding Library respectively. The former contains a set of latent orthogonal cluster centers, and each sample of cluster tasks can be effectively assigned to multiple clusters with different weights. The latter can be modeled by introducing bipartite graph co-clustering, which is able to not only discover the shared manifold information among cluster tasks but also maintain the data manifold information of each individual task. When the model encounters a new multi-view clustering task, it first encodes the new task from each view via the knowledge of both two libraries. Meanwhile, libraries are updated and basis libraries of all views are fused into one. An alternating direction strategy is applied for model optimization, and finally obtains the task-specific representation and Multi-view Fusion Library with clustering center. In summary, this paper makes the following contribution:

• We focus on the lifelong clustering paradigm, which learns and transfers knowledge from previous tasks to
• a new task. Shared knowledge among multiple tasks is effectively mined and stored via two libraries.
• A multi-view model is proposed to learn view-specific Orthogonal Basis Library and Feature Embedding Library, which can simultaneously preserve the latent clustering centers and capture the feature embedding among different tasks, respectively. It also learns a Fusion Basis Library with adaptive weights.
• Various experiments on multi-view datasets certificate the effectiveness and superiority of our method by comparing it with state-of-the-art algorithms

2 RelatedWork

The three most relevant topics are multi-task clustering, multi-view clustering, and lifelong learning.

The aim of multi-task clustering (MTC) is to leverage useful information contained in multiple related tasks to help improve the clustering performance of all the tasks [Zhang and Yang, 2021]. Multi-task spectral clustering (MTSC) [Yang et al., 2014] first attempts to apply the multi-task learning paradigm in spectral clustering. It assumes that all related tasks share a low-dimensional representation and use a ℓ2,pnorm regualrizer to constrain the coherence among all tasks. Self-adapted multi-task clustering (SAMTC) [Zhang et al., 2016] points out that tasks are usually partially related in the real world, and automatically identify and transfer reusable instances among the tasks to avoid a negative transfer. Partially related multi-task clustering (PRMC) [Zhang et al., 2018b] extends SAMTC with a manifold regularized coding, which uses a more stable way to learn the related instances. However, in real applications, task sets are not fixed and the model may encounter new tasks at any time. Multi-task does improve clustering performance but also costs high storage and computation consumption.

With the development of data collection, more and more data are gathered from different sources or styles. Multiview clustering (MVC) has also attracted increasing attention in recent years [Xu et al., 2013; Zhao et al., 2017; Huang et al., 2019]. It exploits complementary and consensus information across multiple views to improve clustering performance. Co-regularized multi-view spectral clustering (CoMVC) [Kumar et al., 2011] applies classical spectral clustering framework to multi-view data. By co-regularizing the clustering hypotheses across views, Co-MVC combines multiple kernels (or similarity matrices) for the clustering problem. One-step multi-view spectral clustering (OMSC) [Zhu et al., 2018] outputs the common affinity matrix learned from low-dimensional data as the final clustering result, thus avoiding the negative influence of the two-step processing in classical spectral clustering. For the problem of spectral clustering doesn't work well with high dimensional data in complex distribution, [Wang et al., 2018] proposes a linear space embedded method called spectral embedded adaptive neighbors clustering (SEANC). It processes the high-dimensional data with embedded representation and obtains clustering results by adaptive neighbors clustering.

Lifelong learning aims to learn new tasks while retaining its performance on the previous tasks. Elastic weight consolidation (EWC) [Kirkpatrick et al., 2017] calculates the importance of the parameters by the Fisher information matrix and minimizes the change of important parameters when encountering a new task. Variational continual learning (VCL) [Nguyen et al., 2017] reaches the same goal with Kullback-Leibler (KL) divergence. An efficient lifelong learning algorithm (ELLA) [Ruvolo and Eaton, 2013] considers that all related tasks of the consecutive online tasks should share a common basis, each new task can be obtained by transferring knowledge from the basis. Furthermore, [Sun et al., 2018] considers that the order of tasks can affect performance, and the tasks with more unknown/novel information should be selected.

3 Method

This section presents our proposed lifelong multi-view spectral clustering model. We first review the classic single-view spectral clustering algorithm for a fixed task set and then detail the proposed LMSC.

3.1 Revisit of Spectral Clustering

Given a clustering task m with nm samples Xm ∈ Rd×nm , where d is the dimension of samples. Spectral clustering first calculates the corresponding symmetric similarity matrix W m ∈ Rnm×nm of Xm, where wij represents the similarity between each pair of samples (as an element of the similarity matrix W). Three common ways are used to construct similarity matrix W m ∈ Rnm×nm , e.g., k-nearest-neighborhood (KNN). ϵ -nearest-neighborhood or fully connected graph. The KNN used in this paper is defined as follows:

where N (.)is the function to search k-nearest neighbors, and σ controls the spread of the neighbors. Then apply the normalized Laplacian on W :

where Dm is the diagonal matrix of W m,Dm ii = ∑j W m ij . After all, we can express the final formulation of spectral clustering with normalized cut [Shi and Malik, 2000]:

F m is the optimal cluster assignment matrix, which can be calculated via the eigenvalue decomposition of matrix Km. The final clustering labels of F m can be achieved by postprocessing, e.g., k-means or spectral rotation.

3.2 Problem Statement

Assume that there is a set of M multi-view clustering tasks T 1 , . . . , T M . Each task T m with V views contains nm data samples Xm v ∈ Rdv×nm , v = 1...V , with the dimension of features of v-th view as dv. Different from multi-task spectral clustering learn the correlations among all tasks, a lifelong system considers learning new tasks without access to the previously learned data. The model faces a series of consecutive clustering tasks T m, . . . , T M . When a new task T m is coming, it arbitrarily and efficiently obtains corresponding cluster assignment matrix F m v of different views and adaptively integrates them into one. In the setting of lifelong clustering, the key issue is how to use the knowledge from each learned task T 1 , . . . , T (m-1) to help the future task T m.

3.3 ProposedModel

In this section, we introduce the proposed LMSC model with three parts, i.e., orthogonal basis library, Feature Embedding Library and multi-view fusion basis library.

Orthogonal Basis Library. [Lin et al., 2021] proposes a simple but effective method to store the previously accumulated experiences. An orthogonal basis clustering is applied to uncover the latent cluster centers. Specifically, the assignment matrix F m is decomposed into two submatrices: a basis matrix B ∈ Rk×k and a task-specific representation Em ∈ Rnm×k , as F m = EmB. Then the multi-task spectral clustering model for v-th view of M tasks can be represented as:

and Bv and Em v are view-specific Basis Library and m task representation, respectively.

Feature Embedding Library. Besides latent cluster center transfer across consecutive tasks, there is also common feature embedding shared among multiple tasks. [Jiang and Chung, 2012] achieved knowledge transfer between two tasks based on graph-based co-clustering. Inspired by that, with a invariant feature embedding libraryL ∈ Rd×k with group sparse constraint, we have graph co-clustering term for v-th view:

where ˆXm v is defined as

where Dt1 = diag (Xm v 1) and Dt2 = diag ((Xm v )⊤1) . With the sharing Embedding Library, learned tasks can facilitate the discovery of the embedding in new tasks, and the feature embedding can be transferred with each task [Argyriou et al., 2008].

Multi-view Fusion Basis Library. View-specific Orthogonal Basis Library can be learned by Eq. (4). For task with V views, we learned V basis libraries. Because the clustering centers on different views should be consistent, each library should be helpful for clustering results. We fuse these libraries to learn a consensus one with adaptive weights [Nie et al., 2018]

Algorithm 1 Lifelong multi-view spectral clustering (LSMC) model

Input: multi-view clustering task sets: {X1 v , . . . ,X M v }Vv=1 , view-specific library:{Bv ← 0k×k,Lv ← 0dv×k}Vv=1 , fusion library D,µ ≥ 0, λ ≥ 0, β ≥ 0, statistical records: {(Mv)0 ← 0k×k, (Cv)0 ← 0d×k}Vv=1

Parameter: λ, µ and β

Output: Bv,Lv,Ev and D

• 1: newm-th task {Xm v }Vv=1 .
• 2: compute matrices {Ktv , ˆXtv }Vv=1 .
• 3: while Not converge do
• 4: update Em v by solving Eq.12;
• 5: update Bv by solving Eq.16;
• 6: update Lv by solving Eq.18;
• 7: update D by solving Eq.20;
• 8: update αv by solving Eq.21;
• 9: compute task representation Em = 1 V ∑Vv=1 Em v ;
• 10: compute assignment matrices via F m = EmD;
• 11: execute K-means to obtain indicator matrices;
• 12: end while
• 13: return solution

By combining Eq. (4), Eq. (5) and Eq. (7), the objective function is formally formulated as follows:

where λ is the trade-off parameter between spectral clustering and co-clustering. If λ equals 0, the function can be reduced to common clustering centers.

4 Optimization

In this section, we introduce the optimization for our method. To reduce computing consumption and memory space, all variables in Eq. (8) should be updated without accessing the previously learned tasks. In the following, the final objective function is non-convex, so an alternating iterative algorithm is given.

4.1 Update Emv

When Bv, Lv, D and αv are fixed, the problem of {Emv }Vv=1 of m-th task can be express independently for different views

where (Emv )⊤ Emv = Ik is the orthonormality constraint. And Et can be effectively updated by Stiefel Manifold Theorem [Manton, 2002]:

Theorem 1. Given a rank p matrix X ∈ Rn×k , and the singular value decomposition of P is UΣV ⊤. On the Stiefel manifold, the projection of P can be calculated by:

The projection could be expressed as π(P) = UIn,kV ⊤. To maximize the objective function, Et could be updated by moving it in the direction of increasing the value of Eq. (9):

where ηT is step size and ∇g (Emv ) is the partial derivatives of objective function of Emv :

4.2 Update Bv

With other fixed variables, the optimization of Bv can be simplified as:

Eq. 13 can be converted into:

Two statistical variables are constructed to represent the knowledge learned from previous tasks:

We also have (Mv)M-1 = ∑M-1 m=1 (Em v )⊤ Km v Em v , and (Cv)M-1 = ∑M-1 m=1 λ ˆXm v Em v . Therefore, Bv in Eq. 14 can be updated by:

Finally, the Bv could be updated by the the eigendecomposition of B⊤v (mm/m + BvL⊤Cm/m - βαv(2I - BvD⊤ -DB⊤v ))Bv.

4.3 Update Lv

With fixed Bv and Emv , the optimization problem for variable Lv on v-th view can be denoted as:

It is equivalent to the following equations:

where Θii = 1 2∥li∥2 and Θ is a diagonal matrix. Eq. (18) can be seen as the projection of CmBv + µΘ-1Lv on Stiefel manifold.

4.4 Update D

The part related to D in the objective function is

According to the formula of F-norm, Eq. (20) can be converted into:

The final solution of D could be obtained by the eigendecomposition of ∑Vv=1 αv(2I - BvD⊤ - DB⊤v ).

4.5 Update αv

Inspired by [Nie et al., 2017], the adaptive weight of each view αv could be calculated via the following formulation:

5 Experiment

In this section, we evaluate the clustering performance of our LMSC model via a throughout empirical comparisons. Starting with a brief introduction to the benchmark datasets and several SOTA methods we adopted, we demonstrate the clustering results and followed by convergence analysis and parameter analysis of our model.

The experimental environment of the paper is AMD Ryzen 5 2600X, Windows 10 Operating System, 16 GB Main Memory, and the experimental platform is MATLAB R2022b.

5.1 Experiment Setup

Aiming at thoroughly examining the clustering performance of our method, several real-world datasets are utilized in our experiment. All datasets are divided into two, three, or four task groups such that each task contains all clusters.

• 3Sources comprises of 3 common online news sources i.e., The Guardian, Reuters, and BBC. 169 different news stories are gathered from the agencies.
• BBC dataset is composed of news stories in five different labels: politics, entertainment, business, tech and sport. We use 685 samples from 4 sources.
• BBCSport contains 544 archives collected from the BBCSport website, where each document is divided into 2 kinds of features.
• Cornell dataset is a popular benchmark for multi-view clustering. It has web pages collected from computer science departments of Cornell University and consists of 195 web pages with two different views.

We also choose some single task multi-view clustering models, multi-task clustering models, and lifelong clustering models as powerful competitors, which are

• SNMF [Kuang et al., 2012]: a graph clustering framework based on NMF.
• Co-regularized multi-view clustering (Coreg) [Kumar et al., 2011] find clustering results that are consistent across the different views.
• Local Learning-based Multi-task Clustering (LLMC) [Zhong and Pun, 2022]: multi-task clustering with shared low-dimensional subspace information.
• Lifelong Spectral Clustering (L2SC) [Sun et al., 2020a]: single-view lifelong spectral clustering.
• Diversity-induced multi-view subspace clustering [Cao et al., 2015] (DiMSC): explores the enhanced complementarity of multi-view representations:
• Generalized latent multi-view subspace clustering (LRMSC) [Zhang et al., 2018a]: multi-view clsutering with latent representation of each view.
• Multiview clustering via adaptively weighted procrustes (AWP) [Nie et al., 2018]: weights each view with its clustering capacities.
• Weighted multi-view spectral clustering (WMSC) [Zong et al., 2018]: employs the spectral perturbation to learn the weight of each view.

5.2 Clustering Results

To achieve fairness, with the authors' suggested parameter settings, each approach is conducted ten times on every dataset with several tasks. The average values of each task and all tasks are adopted. The task sequences fed into multiview models are the same as a multi-task model and a lifelong model. Three widely used criteria are utilized: Normalized Mutual Information (NMI), Purity, and Rand Index (RI). The clustering results of our method and competitors are demonstrated in Table 1 to Table 4, the best result is in red and the second result is in blue. Note that our method achieves the best performance on BBCSport and Cornell, and obtains the best or second best performance on 3Sources and BBC in most cases. Specifically, as for Cornell, LMSC outperforms other competitors on all metrics with respect to different tasks. Overall, the average evaluation indicator of all tasks is good, which showcases the efficiency and superiority of our LMSC. It is worth noting that multi-view clustering models only utilize the information in the current task, whereas the LMSC exploits the knowledge shared among a sequence of tasks. Compared to multi-task model, LMSC performs better, because both the cluster centers and feature embedding are learned. Hence, LMSC has remarkable advantages over traditional multi-view clustering approaches in lifelong learning scenarios.

5.3 Parameter Discussion

To explore the effect on three parameters in Eq. (8), we tune λ, µ and β within the range [1e-3 , 1e-1 , . . . , 1e3 ]. We see the parameters of LMSC are tuned roughly. Better parameter tuning would achieve better clustering performance than that recorded in this paper. As shown in Fig. 2, the vertical axis is NMI in [20%, 40%, 60%] and the horizontal axes are µ and β in [1e-3 , 1e-1 , . . . , 1e3 ], respectively. We find that a high value of λ is beneficial to clustering results. From a global perspective, our proposed method is not greatly affected by µ and β in most cases. In detail, the performance demonstrates a bell-shaped curve since it first increases and then decreases as µ and β vary. From Fig. 3, it is generally the same in the case of Cornell. We observe that our method achieves consistently better performance when λ is around 1 and the performance is pretty stable under the change of other parameter settings.

5.4 Convergence Analysis

It is worth noticing that the optimization algorithm of our objective function is essentially a non-convex problem. Thus, it is rather critical to validate its convergence property. As shown in Fig. 4, we plot the value of the objective function with respect to each new task on 3Sources. Note that our objective values increase sharply with 200 iterations on both datasets and approach to a boundary. Owing to the limited space, we did not theoretically prove the convergence property of our algorithm, but we still find it converges asymptotically on real-world datasets.

6 Conclusion

In this paper, we introduce a novel lifelong multi-view clustering framework termed lifelong multi-view spectral clustering (LMSC) to deal with tasks involved with multi-view data in a sequence. Specifically, two types of libraries are proposed: 1) orthogonal basis libraries which retain cluster centers for each view, and 2) view-specific feature embedding libraries which embrace feature relationships among tasks in the same sequence. As a new multi-view spectral clustering task arrives, LMSC is able to transfer knowledge embedded in the shared knowledge libraries to encode the coming spectral clustering task and update the libraries with respect to different views. Moreover, an adaptive weighing strategy is utilized to integrate multiple orthogonal basis libraries into a fusion orthogonal basis library. Extensive experiments are conducted to evaluate the superiority of the LMSC: 1) as for clustering results, LMSC outperforms other competitors in the majority of cases. 2) As for parameter analysis, our method is relatively stable with respect to different λ, µ, and β. 3) The convergence analysis proves the effectiveness of our optimization algorithm. In the future, we consider using a multi-layer library to capture the nonlinear correlation of each view.

Acknowledgements

This work is supported by the Key Program of National Science Foundation of China (Grant No. 61836006), the National Science Foundation of China under Grant 62106164, and the Sichuan Science and Technology Program under Grants 2021ZDZX0011 and 2022YFG0188.