# Exactk-Component Graph Learning for Image Clustering

Authors: Yufang Min; Yaonan Zhang
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

The performance of graph-based clustering methods highly depends on the quality of the data affinity graph as a good affinity graph can approximate well the pairwise similarity between data samples. To a large extent, existing graph-based clustering methods construct the affinity graph based on a fixed distance metric, which is often not an accurate representation of the underlying data structure. Also, they require postprocessing on the affinity graph to obtain clustering results. Thus, the results are sensitive to the particular graph construction methods. To address these two drawbacks, we propose ak-component graph clustering (k-GC) approach to learn an intrinsic affinity graph and to obtain clustering results simultaneously. Specifically, k-GC learns the data affinity graph by assigning the adaptive and optimal neighbors for each data point based on the local distances. Efficient iterative updating algorithms are derived for k-GC, along with proofs of convergence. Experiments on several benchmark datasets have demonstrated the effectiveness of k-GC.


---

## Body

## 1. Introduction

Clustering is one of the most fundamental topics in computer vision and pattern recognition. The objective of clustering is to discover the data structure and partition a group of data points into several clusters, where the similarity of data points within the same cluster is greater than the similarity from different clusters [1–8].Structure of data is usually characterized by the affinity matrix of the graph whose edges denote the similarities between data points. If vertices belonging to each cluster are connected to be a component, i.e., there is no edge connecting between different clusters,cut is assigned to a value of zero in graph theory. Our purpose is to learn a graph with exact k number of components so that vertices in each connected component of the graph are partitioned into one cluster.Given a cluster indicator matrixZ, it can be constructed by data labels; zic=1 if a data point xi is assigned to the c-th cluster, and zic=0 otherwise. Since ZZ⊤ is a strictly block diagonal matrix in the ideal case, many clustering methods are designed to obtain a block diagonal affinity matrix or they use it as an important prior [9–13]. Actually, we find that a good quality of graph structure results in a good cluster indicator matrix, even if the affinity matrix is not a strictly block diagonal matrix. For example, in Figure 1, we can obtain an ideal cluster indicator matrix Z with the graph itself because one connected component has exactly one cluster, but the affinity matrix W (see Figure 1) constructed from the graph itself is not a strictly block diagonal matrix, i.e., some on-block diagonal elements are zeros. If the graph has k-connected components, we can directly obtain a good cluster indicator matrix with graph itself, even when the connected edges are relatively sparse in each connected component. It means that the graph structure rather than the strictly block diagonal affinity matrix is the intrinsic quality for obtaining a good clustering result.Figure 1
Schematic of thek-component graph learning.We propose a novel graph-based clustering approach to exploitk-connected components for clustering, called k-component graph clustering (k-GC). Figure 1 shows schematic of the k-component graph learning. k-GC aims to learn a graph whose connected edges are tuned adaptively until the graph has exactly k connected components [14]. To evaluate the effectiveness of k-GC, we have conducted experiments on six benchmark datasets in comparison to state-of-the-art approaches. Experimental results have well demonstrated that k-GC performs better than other approaches consistently. k-GC makes following contributions:(1)
k-GC learns to obtain a graph with exact k-connected components. Since the vertices in each connected component belong to one cluster, labels are obtained directly from the learned graph itself.(2)
The clustering indicators are obtained by using the learned graph itself without performing postprocessingk-means clustering algorithm.(3)
k-GC can be used as an alternative to spectral clustering (SC). Similar to SC, k-GC only needs to input an initial affinity graph without involving raw data.


## 2. Related Work

SC, which exploits the eigenstructure of a data affinity graph to partition data into different groups, has become one of the most fundamental clustering approaches. Standard SC uses the radial basis function to construct the affinity matrix [15], and its performance relies heavily on the eigenstructure of the affinity matrix [15–20].In SC, the similarity between pairwise data pointsxi and xj is firstly computed by the radial basis function to construct the affinity matrix W, then the k number of eigenvectors of the normalized Laplacian matrix L corresponding to the top k smallest eigenvalues, H=h1,h2,…,hk∈ℝn×k, are regarded as the low-dimensional embedding of raw data X, and k-means clustering is performed on H to obtain labels finally.However, due to the ambiguity and uncertainty inherent in data structure, the intrinsic affinity matrix cannot be determined by a unified function. Since most existing SC methods use a predefined affinity matrix of the graph, thecut value is usually minimized but not zeroed, e.g., ratio cut [21], normalized cut [16], and min-max cut [22], which results in a postprecessing k-means clustering algorithm to obtain the clustering labels [15, 17, 18].Many approaches have been proposed to improve the performance of SC. Generally, they could be categorized into three paradigms:(1)
How to improve data clustering using a predefined affinity matrix [12, 15, 23](2)
How to construct a better affinity matrix to obtain a better result than standard SC [17, 24, 25](3)
How to learn the affinity matrix and clustering structure simultaneously [26–29]This paper is related to the third paradigm. In the third paradigm, objective functions of [26, 28, 29] usually involve the raw data but k-GC does not involve it. All of them employ a rank constraint on Laplacian matrix [26–29], and clustering with adaptive neighbors (CAN) [26] and constrained Laplacian rank (CLR) [27] are two methods more related to k-GC. CAN learns the graph from raw data. However, CLR learns the graph by minimizing the difference between the input initial graph and the learned graph.Ink-GC, the raw data are not involved in the objective function, and k-GC is directly modified from standard SC to tune the structure of graph so that an intrinsic graph with exact k-connected components is obtained.


## 3.k-Component Graph Clustering

Suppose that the data matrix is denoted byX=X1,X2,…,Xk=x1,x2,…,xn∈ℝd×n, where Xc denotes the data matrix belonging to the c-th cluster, k denotes the cluster number, xi denotes the i-th data point, n is the number of data points, and d denotes the dimension.


### 3.1. Preprocessing

We propose a new simple neighborhood-preserving method to refine the raw data in this section. Assume that a data pointxi and its nearest data point yi are both generated from a same point since they may be disturbed by noise. Then, we define an equation to replace xi by the weighted linear combination of xi and yi:(1)xi⇐xi+riyi1+ri,where ri is defined by(2)ri=exp−xi−yi22/σ2.Since a data point is generally closer to the nearest one belonging to a same cluster than one to a different cluster, it is straightforward to check from equation (2) that ri tends to 1 if xi and yi belong to a same cluster and ri tends to 0 if xi and yi belong to different clusters. It implies that two data points in a same cluster become closer during iteration while two data points in different clusters have very small or even no influence on each other after using the preprocessing. With the iteration of equation (1), data points in same cluster become closer and closer so that the clustering is easier to carry out.


### 3.2.k-Component Graph

An undirected finite graph is denoted byG, and its vertex set is denoted by V=v1,v2,…,vn. We consider the graph is weighted and assign a non-negative real weight wij to each pair vertices of vi and vj. The degree of a vertex vj∈V is defined by dj=∑i=1nwij. The Laplacian matrix of the graph G [30] is defined by(3)L=D−W,where D is the diagonal matrix whose j,j-element is dj.For any vectorf∈ℝn, we have f⊤Lf=1/2∑i,j=1nwijfi−fj2≥0, so L is a positive semidefinite matrix. Since L1=D−W1=01, the smallest eigenvalue of L is equal to zero, and the corresponding eigenvector is 1.Theorem 1.
The number of connected componentsk is equal to the multiplicity of 0 as an eigenvalue of L.Proof.
Suppose there arek-connected components in graph G, the c-th subgraph is denoted by Gc, and the corresponding vertex set of Gc is denoted by Vc. Then, we have ∪c=1kVc=V and Vi∩Vi≠j=∅. For an eigenvector h of L with eigenvalue zero, we have 0=h⊤Lh=1/2∑i,j=1nwijhi−hj2. In the c-th connected component Gc, a connected edge is weighted by a positive value wij>0, and the corresponding term of hi−hj2 needs to be zeroed, i.e., hi and hj have to be a constant μc. ∀vi∈Vc and ∀vj∈Vc, and the terms of hi−hj2 need to be zeroed while these edges are connected with positive weights wij, which means that in the c-th component, ∀vi∈Vc, and each hi is of the same constant, i.e., hi=μc. These eigenvectors of different components are linearly independent, so the multiplicity of 0 as eigenvalue is the number of components of the graph G and vice versa.
Similar proof of Theorem1 can be seen in previous works [13, 18, 31]. We explore Theorem 1 in the context of a specific example. In Figure 1, we show an intrinsic graph G with two connected components, and an intrinsic affinity matrix W of the graph G being consistent in Theorem 1 is given by(4)W=00.500.50000.500.5000000.500.50000.500.50000000000.50.500000.500.500000.50.50,where we constrain the degree dj=∑i=1nwij=1, i.e., the sum of each column of W is equal to one.
The Laplacian matrixL of equation (4) has an eigenvalue zero with the multiplicity k=2, and we have the two corresponding eigenvectors h1 and h2. They are concatenated by H=h1,h2, and its transposition is(5)H⊤=121212120000000131313.
If the graphG in Figure 1 corresponds to an affinity matrix W in equation (4), i.e., the Laplacian matrix L of equation (4) satisfies to Theorem 1, then the clustering labels are easy to obtain without further performing graph-cut or k-means clustering algorithms. Since vertices in each connected component of the graph are partitioned into one cluster, the clustering labels can be obtained easily by using the graph G with strongly connected-component algorithm [32].
Since it is a positive semidefinite matrix,L has n non-negative eigenvalues 0=λ1≤λ2≤⋯≤λn. Theorem 1 indicates that if ∑c=1kλc=0, then the graph G has k-connected components and the vertices are already partitioned into k clusters [18, 30, 31, 33]. Then, according to Fan’s theorem [14, 34], we have(6)∑c=1kλc=minHTrH⊤LHs.t.H∈ℝn×k,H⊤H=I,where Tr⋅ denotes the trace operator, I∈ℝk×k is an identity matrix, L=D−W⊤+W/2 is the Laplacian matrix, and D is a diagonal matrix whose diagonal elements are column sums of W⊤+W/2.
The proof of Fan’s theorem can be seen in [13, 35, 36].
It is straightforward to check that the objective function value of equation (6) does not generally tend to zero because the structure of graph G is varied by varying the graph construction methods. In the following section, we propose a method to tune the graph structure of G adaptively so that the objective function value of equation (6) tends to zero.


### 3.3.k-GC Algorithm

In this section, we will explore how to learn a graphW with exact k-connected components [14].The right term of equation (6) can be solved with respect to H by the eigenvectors of L, but it has trivial solution with respect to W, i.e., only one wij is assigned to a value and others are zeroed in each column of W. We add ℓ2-norm regularization to smooth the weights in W. Then, we optimize W and H simultaneously:(7)minW,HTrH⊤LH+βWF2s.t.∀j,1⊤wj=1,wj≥0,H∈ℝn×c,H⊤H=I,where β is the trade-off parameter.If the affinity matrix is consistent in Theorem1, the procedure of obtaining clustering labels is named as k-GC. In other words, we guarantee the objective function of standard SC to be zeroed in k-GC by means of tuning the graph structure. We divide the problem equation (7) into two subproblems and alternately solve them.The first subproblem is to fixW, updating H. Then, equation (7) becomes(8)minHTrH⊤LHs.t.H∈ℝn×c,H⊤H=I.Equation (8) is solved by calculating the eigenvectors of L.The second subproblem is to fixH, updating W. Then, equation (7) becomes(9)minW∑i,j=1nhi−hj22wij+βWF2s.t.∀j,wj≥0,1⊤wj=1,where hi denotes the i-th column of H⊤.Each column ofW is independent, so solving equation (9) is equal to optimizing the following problem:(10)minwj∑i=1nhi−hj22wij+β∑i=1nwij2s.t.wj≥0,1⊤wj=1.hi−hj22 is denoted by gi and hj is a fixed vector when we solve the j-th column wj. Solving equation (10) is equal to optimizing the following problem:(11)minwj12wj+12βg22s.t.wj≥0,1⊤wj=1.where g=g1,g2,…,gn⊤ is a constant vector.Equation (11) is a Euclidean projection problem on the simplex space, and there are several algorithms for solving it [37–39]. According to the Karush–Kuhn–Tucker condition [37], it can be verified that the optimal solution wj∗ is(12)wj∗=−g2β+η+.Equation (10) will be analysed specifically in Section 3.4, and we show how to obtain exact k-connected components.We alternately optimize equations (9) and (8) until the sum of the top k smallest eigenvalues of L becomes zero. The algorithm for solving equation (7) is summarized by Algorithm 1.Algorithm 1:k-GC algorithm.
(1)
Input: A data matrix X∈ℝd×n, the number of neighbors m, and the number of clusters k.(2)
Output: The affinity graph W.(3)
Initialize: The graph W is initialized by equation (9) where we replace H by X⊤; H is initialized with initial graph W by solving equation (8); and β=∑j=1nβj.(4)
Iterate equation (1) several times.(5)
While not converge do(6)
Forj∈1,2,…,ndo(7)
Updatewj by using equation (12);(8)
end for(9)
W=W+W⊤/2;(10)
UpdateH by using equation (8), i.e., H is formed by k eigenvectors with the top k smallest eigenvalues of L.(11)
end while


### 3.4.k-Component Graph Learning

We find a trade-off between two graph structures: the first case is that one vertex is connected with only one other vertex in vertex setV and the second case is that all vertices are connected with each other by the same weight 1/n. The trade-off renders the objective function of equation (6) close to zero.We optimize each column ofW independently, and one column of W is denoted by wj. Values in the vector wj are zero or positive: wij=0 means vi has no edge with vj and wij>0 means vi and vj are connected with an edge.The first is to optimize the following:(13)minwjwj⊤gs.t.wj≥0,1⊤wj=1.It returns the minimum valuegi=ming, i.e., vj is only connected to the other vi.The second is the following:(14)minwjwj⊤wjs.t.wj≥0,1⊤wj=1.It returnswij∗=1/n,∀j.Thus, an adaptive graph learning objective function is(15)minwjwj⊤g+βjwj⊤wjs.t.wj≥0,1⊤wj=1,where βj is the trade-off parameter.Ifβj=0, then optimizing equation (15) is equivalent to solving equation (13); if βj tends to an infinity positive value, then equation (15) becomes equation (14). If we want to learn a sparse graph, we can tune βj to be a small value; if we want to learn a graph with more edges, we can tune βj to be a relatively large value.Solving equation (15) is equal to optimizing the problem:(16)minwj12wj+12βjg22s.t.wj≥0,1⊤wj=1.According [40], the optimal affinities wij∗ are given by(17)wij∗=gm+1−gimgm+1−∑i=1mgi,ifi≤m;0,otherwise.Actually, it is straightforward to check from equation (17) that the number of neighbors m is also determined by the setting of βj. In practice, the structure of the graph G can be tuned coarsely by m and can be tuned finely by the trade-off parameter βj. m has an explicit meaning while βj has an implicit relation with the structure of the graph. We tune both of them to obtain an intrinsic affinity matrix.As standard SC, we can input any affinity matrix fork-GC. There is one parameter β in equation (7). In Algorithm 1, we use Eq. (9) to obtain the initial graph by replacing H with X⊤. For each wj,j∈1,2,…,n, we have different βj, so before the iteration, we set β=∑j=1nβj for preserving the initial structure. The initial graph structure is mainly determined by m.


### 3.5. Convergence Analysis

Since the second-order derivative of equation (16) with respect wj is equal to 1≥0, equation (16) is a convex problem. Because the Laplacian matrix is a positive semidefinite matrix, equation (8) is a convex optimization problem. Optimizing W and H alternately, both of them decrease monotonically. As a result, the overall objective function value of equation (7) decreases monotonically in each iteration until Algorithm 1 converges.


### 3.6. Computational Complexity Analysis

The first step of the objective function equation (7) is to solve equation (10). We need On time to compute hj, and Ot1n to solve equation (15) where t1 is the iteration number. n times are needed to calculate each wj,∀j, so the complexity of the first step of equation (7) is Ot1+1n2. The second step is an eigendecomposition procedure, and the complexity of the generalized eigenvector problem is On+kn2. For solving equation (8), we need to calculate the k eigenvectors of L, so its cost is Okn2. Thus, the total complexity of equation (7) is(18)Ot1+1+kn2to,where to is the number of iterations of the two steps.


## 3.1. Preprocessing

We propose a new simple neighborhood-preserving method to refine the raw data in this section. Assume that a data pointxi and its nearest data point yi are both generated from a same point since they may be disturbed by noise. Then, we define an equation to replace xi by the weighted linear combination of xi and yi:(1)xi⇐xi+riyi1+ri,where ri is defined by(2)ri=exp−xi−yi22/σ2.Since a data point is generally closer to the nearest one belonging to a same cluster than one to a different cluster, it is straightforward to check from equation (2) that ri tends to 1 if xi and yi belong to a same cluster and ri tends to 0 if xi and yi belong to different clusters. It implies that two data points in a same cluster become closer during iteration while two data points in different clusters have very small or even no influence on each other after using the preprocessing. With the iteration of equation (1), data points in same cluster become closer and closer so that the clustering is easier to carry out.


## 3.2.k-Component Graph

An undirected finite graph is denoted byG, and its vertex set is denoted by V=v1,v2,…,vn. We consider the graph is weighted and assign a non-negative real weight wij to each pair vertices of vi and vj. The degree of a vertex vj∈V is defined by dj=∑i=1nwij. The Laplacian matrix of the graph G [30] is defined by(3)L=D−W,where D is the diagonal matrix whose j,j-element is dj.For any vectorf∈ℝn, we have f⊤Lf=1/2∑i,j=1nwijfi−fj2≥0, so L is a positive semidefinite matrix. Since L1=D−W1=01, the smallest eigenvalue of L is equal to zero, and the corresponding eigenvector is 1.Theorem 1.
The number of connected componentsk is equal to the multiplicity of 0 as an eigenvalue of L.Proof.
Suppose there arek-connected components in graph G, the c-th subgraph is denoted by Gc, and the corresponding vertex set of Gc is denoted by Vc. Then, we have ∪c=1kVc=V and Vi∩Vi≠j=∅. For an eigenvector h of L with eigenvalue zero, we have 0=h⊤Lh=1/2∑i,j=1nwijhi−hj2. In the c-th connected component Gc, a connected edge is weighted by a positive value wij>0, and the corresponding term of hi−hj2 needs to be zeroed, i.e., hi and hj have to be a constant μc. ∀vi∈Vc and ∀vj∈Vc, and the terms of hi−hj2 need to be zeroed while these edges are connected with positive weights wij, which means that in the c-th component, ∀vi∈Vc, and each hi is of the same constant, i.e., hi=μc. These eigenvectors of different components are linearly independent, so the multiplicity of 0 as eigenvalue is the number of components of the graph G and vice versa.
Similar proof of Theorem1 can be seen in previous works [13, 18, 31]. We explore Theorem 1 in the context of a specific example. In Figure 1, we show an intrinsic graph G with two connected components, and an intrinsic affinity matrix W of the graph G being consistent in Theorem 1 is given by(4)W=00.500.50000.500.5000000.500.50000.500.50000000000.50.500000.500.500000.50.50,where we constrain the degree dj=∑i=1nwij=1, i.e., the sum of each column of W is equal to one.
The Laplacian matrixL of equation (4) has an eigenvalue zero with the multiplicity k=2, and we have the two corresponding eigenvectors h1 and h2. They are concatenated by H=h1,h2, and its transposition is(5)H⊤=121212120000000131313.
If the graphG in Figure 1 corresponds to an affinity matrix W in equation (4), i.e., the Laplacian matrix L of equation (4) satisfies to Theorem 1, then the clustering labels are easy to obtain without further performing graph-cut or k-means clustering algorithms. Since vertices in each connected component of the graph are partitioned into one cluster, the clustering labels can be obtained easily by using the graph G with strongly connected-component algorithm [32].
Since it is a positive semidefinite matrix,L has n non-negative eigenvalues 0=λ1≤λ2≤⋯≤λn. Theorem 1 indicates that if ∑c=1kλc=0, then the graph G has k-connected components and the vertices are already partitioned into k clusters [18, 30, 31, 33]. Then, according to Fan’s theorem [14, 34], we have(6)∑c=1kλc=minHTrH⊤LHs.t.H∈ℝn×k,H⊤H=I,where Tr⋅ denotes the trace operator, I∈ℝk×k is an identity matrix, L=D−W⊤+W/2 is the Laplacian matrix, and D is a diagonal matrix whose diagonal elements are column sums of W⊤+W/2.
The proof of Fan’s theorem can be seen in [13, 35, 36].
It is straightforward to check that the objective function value of equation (6) does not generally tend to zero because the structure of graph G is varied by varying the graph construction methods. In the following section, we propose a method to tune the graph structure of G adaptively so that the objective function value of equation (6) tends to zero.


## 3.3.k-GC Algorithm

In this section, we will explore how to learn a graphW with exact k-connected components [14].The right term of equation (6) can be solved with respect to H by the eigenvectors of L, but it has trivial solution with respect to W, i.e., only one wij is assigned to a value and others are zeroed in each column of W. We add ℓ2-norm regularization to smooth the weights in W. Then, we optimize W and H simultaneously:(7)minW,HTrH⊤LH+βWF2s.t.∀j,1⊤wj=1,wj≥0,H∈ℝn×c,H⊤H=I,where β is the trade-off parameter.If the affinity matrix is consistent in Theorem1, the procedure of obtaining clustering labels is named as k-GC. In other words, we guarantee the objective function of standard SC to be zeroed in k-GC by means of tuning the graph structure. We divide the problem equation (7) into two subproblems and alternately solve them.The first subproblem is to fixW, updating H. Then, equation (7) becomes(8)minHTrH⊤LHs.t.H∈ℝn×c,H⊤H=I.Equation (8) is solved by calculating the eigenvectors of L.The second subproblem is to fixH, updating W. Then, equation (7) becomes(9)minW∑i,j=1nhi−hj22wij+βWF2s.t.∀j,wj≥0,1⊤wj=1,where hi denotes the i-th column of H⊤.Each column ofW is independent, so solving equation (9) is equal to optimizing the following problem:(10)minwj∑i=1nhi−hj22wij+β∑i=1nwij2s.t.wj≥0,1⊤wj=1.hi−hj22 is denoted by gi and hj is a fixed vector when we solve the j-th column wj. Solving equation (10) is equal to optimizing the following problem:(11)minwj12wj+12βg22s.t.wj≥0,1⊤wj=1.where g=g1,g2,…,gn⊤ is a constant vector.Equation (11) is a Euclidean projection problem on the simplex space, and there are several algorithms for solving it [37–39]. According to the Karush–Kuhn–Tucker condition [37], it can be verified that the optimal solution wj∗ is(12)wj∗=−g2β+η+.Equation (10) will be analysed specifically in Section 3.4, and we show how to obtain exact k-connected components.We alternately optimize equations (9) and (8) until the sum of the top k smallest eigenvalues of L becomes zero. The algorithm for solving equation (7) is summarized by Algorithm 1.Algorithm 1:k-GC algorithm.
(1)
Input: A data matrix X∈ℝd×n, the number of neighbors m, and the number of clusters k.(2)
Output: The affinity graph W.(3)
Initialize: The graph W is initialized by equation (9) where we replace H by X⊤; H is initialized with initial graph W by solving equation (8); and β=∑j=1nβj.(4)
Iterate equation (1) several times.(5)
While not converge do(6)
Forj∈1,2,…,ndo(7)
Updatewj by using equation (12);(8)
end for(9)
W=W+W⊤/2;(10)
UpdateH by using equation (8), i.e., H is formed by k eigenvectors with the top k smallest eigenvalues of L.(11)
end while


## 3.4.k-Component Graph Learning

We find a trade-off between two graph structures: the first case is that one vertex is connected with only one other vertex in vertex setV and the second case is that all vertices are connected with each other by the same weight 1/n. The trade-off renders the objective function of equation (6) close to zero.We optimize each column ofW independently, and one column of W is denoted by wj. Values in the vector wj are zero or positive: wij=0 means vi has no edge with vj and wij>0 means vi and vj are connected with an edge.The first is to optimize the following:(13)minwjwj⊤gs.t.wj≥0,1⊤wj=1.It returns the minimum valuegi=ming, i.e., vj is only connected to the other vi.The second is the following:(14)minwjwj⊤wjs.t.wj≥0,1⊤wj=1.It returnswij∗=1/n,∀j.Thus, an adaptive graph learning objective function is(15)minwjwj⊤g+βjwj⊤wjs.t.wj≥0,1⊤wj=1,where βj is the trade-off parameter.Ifβj=0, then optimizing equation (15) is equivalent to solving equation (13); if βj tends to an infinity positive value, then equation (15) becomes equation (14). If we want to learn a sparse graph, we can tune βj to be a small value; if we want to learn a graph with more edges, we can tune βj to be a relatively large value.Solving equation (15) is equal to optimizing the problem:(16)minwj12wj+12βjg22s.t.wj≥0,1⊤wj=1.According [40], the optimal affinities wij∗ are given by(17)wij∗=gm+1−gimgm+1−∑i=1mgi,ifi≤m;0,otherwise.Actually, it is straightforward to check from equation (17) that the number of neighbors m is also determined by the setting of βj. In practice, the structure of the graph G can be tuned coarsely by m and can be tuned finely by the trade-off parameter βj. m has an explicit meaning while βj has an implicit relation with the structure of the graph. We tune both of them to obtain an intrinsic affinity matrix.As standard SC, we can input any affinity matrix fork-GC. There is one parameter β in equation (7). In Algorithm 1, we use Eq. (9) to obtain the initial graph by replacing H with X⊤. For each wj,j∈1,2,…,n, we have different βj, so before the iteration, we set β=∑j=1nβj for preserving the initial structure. The initial graph structure is mainly determined by m.


## 3.5. Convergence Analysis

Since the second-order derivative of equation (16) with respect wj is equal to 1≥0, equation (16) is a convex problem. Because the Laplacian matrix is a positive semidefinite matrix, equation (8) is a convex optimization problem. Optimizing W and H alternately, both of them decrease monotonically. As a result, the overall objective function value of equation (7) decreases monotonically in each iteration until Algorithm 1 converges.


## 3.6. Computational Complexity Analysis

The first step of the objective function equation (7) is to solve equation (10). We need On time to compute hj, and Ot1n to solve equation (15) where t1 is the iteration number. n times are needed to calculate each wj,∀j, so the complexity of the first step of equation (7) is Ot1+1n2. The second step is an eigendecomposition procedure, and the complexity of the generalized eigenvector problem is On+kn2. For solving equation (8), we need to calculate the k eigenvectors of L, so its cost is Okn2. Thus, the total complexity of equation (7) is(18)Ot1+1+kn2to,where to is the number of iterations of the two steps.


## 4. Experimental Results

In this section, we conduct experiments on six datasets to demonstrate the effectiveness ofk-GC in terms of clustering accuracy (ACC) and normalized mutual information (NMI).


### 4.1. Dataset Description

Six datasets include the following:(1)
Two-moon dataset is a randomly generated synthesis dataset and has two clusters of data distributed in the moon shape. Each cluster has 100 samples and the noise percentage is set to 0.20.(2)
Path-based dataset [41] is made up of 300 samples which belong to three clusters.(3)
Yale dataset (http://vision.ucsd.edu/content/yale-face-database) contains 165 grayscale images of 15 individuals. Each individual has 11 images taken under different facial expression or configuration.(4)
ORL dataset (http://www.cl.cam.ac.uk/research/dtg/attarchive/facedatabase.html) contains ten different images of each with 40 distinct subjects. For some subjects, the images were taken at different time, varying the lighting, facial expressions, and facial details. All the images were taken against a dark homogeneous background with the subjects in an upright, frontal position.(5)
COIL-20 dataset [42] contains 1440 images of 20 object categories. Each category includes 72 images and all the images are normalized to 32 × 32 pixel arrays.(6)
Notting-Hill dataset is derived from the movie “Notting Hill” and includes 4660 faces in 76 tracks belonging to five main casts.The first two datasets are two-dimensional synthesis datasets. For datasets of Yale, ORL, COIL-20, and Notting-Hill, we employ the intensity feature of these images [43, 44]. A small fraction of samples in these image datasets is shown in Figure 2. Dataset description is summarized in Table 1.Figure 2
Example images of different datasets.Table 1
Dataset description.
DatasetSamplesDimensionsClustersTwo-moon20022Path-based30023Yale165409615ORL400409640COIL-201440102420Notting-Hill466020005


### 4.2. Experimental Setup

We comparek-GC with six methods, and the results are summarized in Table 2. We select three classic methods: k-means clustering [45], ratio cut clustering (R-cut) [21], and self-tuning SC (ST-SC) [17]; besides, we select three related state-of-the-art methods: robust graph for SC (RG-SC) [24], clustering with adaptive neighbors (CAN) [26], and constrained Laplacian rank (CLR) [27].Table 2
Clustering performance.
Methodsk-meansR-cutST-SCRG-SCCANCLRk-GCACCTwo-moon75.50± 0.0073.00± 0.0079.00± 0.0078.00± 0.0093.00± 0.0087.50± 0.0098.50±0.00Path-based74.33± 0.0076.85± 2.0579.33± 0.0060.66± 0.0087.00± 0.0087.00± 0.0099.00±0.00Yale50.30± 2.6829.75± 1.8657.63± 1.4962.90± 0.2552.73± 0.0059.39± 0.0068.48±0.00ORL55.45± 3.1030.12± 1.3768.27± 1.7859.82± 0.8656.50± 0.0063.75± 0.0070.75±0.00COIL-2066.79± 2.6545.72± 0.9969.34± 0.0676.65± 0.0290.14± 0.0087.29± 0.0094.03±0.00Notting-Hill79.53± 0.6148.92± 0.0078.71± 0.0080.86± 0.0170.62± 0.0074.79± 0.0083.58±0.00NMITwo-moon19.79± 0.0015.92± 0.0025.85± 0.0024.10± 0.0069.37± 0.0054.88± 0.0090.22±0.00Path-based51.28± 0.0150.92± 8.3857.29± 0.0027.72± 2.3575.63± 0.0075.63± 0.0095.82±0.00Yale56.17± 1.9836.27± 2.6261.72± 0.9265.49± 0.2755.40± 0.0059.21± 0.0068.63±0.00ORL74.31± 1.5655.26± 1.0482.60± 0.7277.91± 0.4374.07± 0.0079.98± 0.0083.33±0.00COIL-2077.83± 1.2255.99± 0.4778.48± 0.3084.83± 0.0394.60± 0.0094.14± 0.0096.42±0.00Notting-Hill68.09± 1.0826.94± 0.0064.19± 0.0067.39± 0.0161.80± 0.0071.05± 0.0077.93±0.00The default parameters given by the respective authors are adopted.(1)
k-means [45] clusters samples based on the similarity between samples and cluster centroids. There is no parameter to tune in k-means. We run k-means clustering 10 times to evaluate the performance. In order to reduce the effect of random initialization, we run 30 times and report the result with the minimum value of the objective function of k-means among these results in each time.(2)
R-cut [21] finds the first k eigenvectors of the Laplacian matrix of the graph so as to minimize the similarity between two parts in the graph. Specifically, R-cut advocates the second eigenvalue of the Laplacian matrix which gives the optimal solution.(3)
ST-SC [17] constructs a graph in a local scale and each data point chooses different neighbors. It has a parameter to determine the number of nearest neighbors for graph construction, and we tune the neighbor number to report the best results in terms of the objective value of k-means.(4)
RG-SC [24] generates robust affinity graphs via identifying and exploiting discriminative features for spectral clustering based on the unsupervised clustering random forest. The default parameters are used in our experiments.(5)
CAN [26] learns the data similarity matrix and clustering structure simultaneously and uses a rank constraint to create the clustering structure in the similarity matrix as several disconnected components. The number of nearest neighbors is searched from 2 to 50 with incremental 2.(6)
CLR [27] imposes a Laplacian rank constraint on the learned graph which best approximates the input initial affinity graph. In our experiments, the number of nearest neighbors is searched from 2 to 50 with interval 2 to obtain the best parameter.Fork-GC, we tune the parameter m in the range of 5,40 with interval two, and β is fixed by β=∑j=1nβj. For preprocessing, we iterate equation (1) ten times with σ=12. We select optimal m in terms of objective value of k-means clustering preformed on H. k-GC obtains the clustering results from the learned graph itself because data points in each connected component belong to one cluster, and the clustering indicators are directly obtained according to Tarjan’s strongly connected-component algorithm [32]. In practice, we can determine β in a heuristic way to accelerate the procedure [26]. As the iteration stopping condition of the sum of the top k smallest eigenvalues of L being zeroed, i.e., the first term of equation (7) is zeroed, is stronger than conventional iteration stopping condition [26], we adopt the former. Because of the iteration stopping condition, we set β to a constant (e.g., β=∑j=1nβj), then increase β if the connected components of W are larger than k, and decrease β if they are smaller than k during iteration.For all these methods, we run each method 10 times and report the mean of performance as well as the standard deviation in Table2.


### 4.3. Results and Analysis

We choose six datasets to demonstrate the effectiveness ofk-GC, the first two of which are synthetic while the rest are real-world datasets. In addition, quantitative results of different methods are shown in Table 2, from which we can find that we have improved the performance to a large extent in comparison to the state-of-the-art methods. The clustering results of the comparing methods using the two synthetic datasets are visualized in Figure 3 so that we can observe in an intuitive way that k-GC approximates the ground truth mostly. What is notable is that on two synthetic datasets of two-moon and path-based, we have a surprisingly good result approximating to 100%, meaning almost entirely accurate clustering. This implies the great importance of the intrinsic graph structure with a comprehensive analysis of which we obtain a significantly success over other methods.Figure 3
Results of comparing methods on two-moon and path-based datasets. GT denotes the ground truth. (a)k-means, (b) R-cut, (c) ST-SC,(d) RG-SC, (e) CAN, (f) CLR, (g) k-GC, (h) GT, (i) k-means, (j) R-cut, (k) ST-SC, (l) RG-SC, (m) CAN, (n) CLR, (o) k-GC, and (p) GT.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)(m)(n)(o)(p)Figure4 shows that the objective value of k-GC, equation (7), is nonincreasing during iterations. They all converge to a fixed value very fast in 10 iteration times. k-GC only needs several times to iterate alternately to obtain a cut-zeroed graph while the conventional SC-based methods need to perform postprocessing by using k-means clustering algorithm. Therefore, the k-GC algorithm is effective overall.Figure 4
Convergence behaviors ofk-GC. (a) Two-moon dataset. (b) Path-based dataset. (c) Yale dataset. (d) ORL dataset. (e) COIL-20 dataset. (f) Notting-Hill dataset.
(a)(b)(c)(d)(e)(f)


## 4.1. Dataset Description

Six datasets include the following:(1)
Two-moon dataset is a randomly generated synthesis dataset and has two clusters of data distributed in the moon shape. Each cluster has 100 samples and the noise percentage is set to 0.20.(2)
Path-based dataset [41] is made up of 300 samples which belong to three clusters.(3)
Yale dataset (http://vision.ucsd.edu/content/yale-face-database) contains 165 grayscale images of 15 individuals. Each individual has 11 images taken under different facial expression or configuration.(4)
ORL dataset (http://www.cl.cam.ac.uk/research/dtg/attarchive/facedatabase.html) contains ten different images of each with 40 distinct subjects. For some subjects, the images were taken at different time, varying the lighting, facial expressions, and facial details. All the images were taken against a dark homogeneous background with the subjects in an upright, frontal position.(5)
COIL-20 dataset [42] contains 1440 images of 20 object categories. Each category includes 72 images and all the images are normalized to 32 × 32 pixel arrays.(6)
Notting-Hill dataset is derived from the movie “Notting Hill” and includes 4660 faces in 76 tracks belonging to five main casts.The first two datasets are two-dimensional synthesis datasets. For datasets of Yale, ORL, COIL-20, and Notting-Hill, we employ the intensity feature of these images [43, 44]. A small fraction of samples in these image datasets is shown in Figure 2. Dataset description is summarized in Table 1.Figure 2
Example images of different datasets.Table 1
Dataset description.
DatasetSamplesDimensionsClustersTwo-moon20022Path-based30023Yale165409615ORL400409640COIL-201440102420Notting-Hill466020005


## 4.2. Experimental Setup

We comparek-GC with six methods, and the results are summarized in Table 2. We select three classic methods: k-means clustering [45], ratio cut clustering (R-cut) [21], and self-tuning SC (ST-SC) [17]; besides, we select three related state-of-the-art methods: robust graph for SC (RG-SC) [24], clustering with adaptive neighbors (CAN) [26], and constrained Laplacian rank (CLR) [27].Table 2
Clustering performance.
Methodsk-meansR-cutST-SCRG-SCCANCLRk-GCACCTwo-moon75.50± 0.0073.00± 0.0079.00± 0.0078.00± 0.0093.00± 0.0087.50± 0.0098.50±0.00Path-based74.33± 0.0076.85± 2.0579.33± 0.0060.66± 0.0087.00± 0.0087.00± 0.0099.00±0.00Yale50.30± 2.6829.75± 1.8657.63± 1.4962.90± 0.2552.73± 0.0059.39± 0.0068.48±0.00ORL55.45± 3.1030.12± 1.3768.27± 1.7859.82± 0.8656.50± 0.0063.75± 0.0070.75±0.00COIL-2066.79± 2.6545.72± 0.9969.34± 0.0676.65± 0.0290.14± 0.0087.29± 0.0094.03±0.00Notting-Hill79.53± 0.6148.92± 0.0078.71± 0.0080.86± 0.0170.62± 0.0074.79± 0.0083.58±0.00NMITwo-moon19.79± 0.0015.92± 0.0025.85± 0.0024.10± 0.0069.37± 0.0054.88± 0.0090.22±0.00Path-based51.28± 0.0150.92± 8.3857.29± 0.0027.72± 2.3575.63± 0.0075.63± 0.0095.82±0.00Yale56.17± 1.9836.27± 2.6261.72± 0.9265.49± 0.2755.40± 0.0059.21± 0.0068.63±0.00ORL74.31± 1.5655.26± 1.0482.60± 0.7277.91± 0.4374.07± 0.0079.98± 0.0083.33±0.00COIL-2077.83± 1.2255.99± 0.4778.48± 0.3084.83± 0.0394.60± 0.0094.14± 0.0096.42±0.00Notting-Hill68.09± 1.0826.94± 0.0064.19± 0.0067.39± 0.0161.80± 0.0071.05± 0.0077.93±0.00The default parameters given by the respective authors are adopted.(1)
k-means [45] clusters samples based on the similarity between samples and cluster centroids. There is no parameter to tune in k-means. We run k-means clustering 10 times to evaluate the performance. In order to reduce the effect of random initialization, we run 30 times and report the result with the minimum value of the objective function of k-means among these results in each time.(2)
R-cut [21] finds the first k eigenvectors of the Laplacian matrix of the graph so as to minimize the similarity between two parts in the graph. Specifically, R-cut advocates the second eigenvalue of the Laplacian matrix which gives the optimal solution.(3)
ST-SC [17] constructs a graph in a local scale and each data point chooses different neighbors. It has a parameter to determine the number of nearest neighbors for graph construction, and we tune the neighbor number to report the best results in terms of the objective value of k-means.(4)
RG-SC [24] generates robust affinity graphs via identifying and exploiting discriminative features for spectral clustering based on the unsupervised clustering random forest. The default parameters are used in our experiments.(5)
CAN [26] learns the data similarity matrix and clustering structure simultaneously and uses a rank constraint to create the clustering structure in the similarity matrix as several disconnected components. The number of nearest neighbors is searched from 2 to 50 with incremental 2.(6)
CLR [27] imposes a Laplacian rank constraint on the learned graph which best approximates the input initial affinity graph. In our experiments, the number of nearest neighbors is searched from 2 to 50 with interval 2 to obtain the best parameter.Fork-GC, we tune the parameter m in the range of 5,40 with interval two, and β is fixed by β=∑j=1nβj. For preprocessing, we iterate equation (1) ten times with σ=12. We select optimal m in terms of objective value of k-means clustering preformed on H. k-GC obtains the clustering results from the learned graph itself because data points in each connected component belong to one cluster, and the clustering indicators are directly obtained according to Tarjan’s strongly connected-component algorithm [32]. In practice, we can determine β in a heuristic way to accelerate the procedure [26]. As the iteration stopping condition of the sum of the top k smallest eigenvalues of L being zeroed, i.e., the first term of equation (7) is zeroed, is stronger than conventional iteration stopping condition [26], we adopt the former. Because of the iteration stopping condition, we set β to a constant (e.g., β=∑j=1nβj), then increase β if the connected components of W are larger than k, and decrease β if they are smaller than k during iteration.For all these methods, we run each method 10 times and report the mean of performance as well as the standard deviation in Table2.


## 4.3. Results and Analysis

We choose six datasets to demonstrate the effectiveness ofk-GC, the first two of which are synthetic while the rest are real-world datasets. In addition, quantitative results of different methods are shown in Table 2, from which we can find that we have improved the performance to a large extent in comparison to the state-of-the-art methods. The clustering results of the comparing methods using the two synthetic datasets are visualized in Figure 3 so that we can observe in an intuitive way that k-GC approximates the ground truth mostly. What is notable is that on two synthetic datasets of two-moon and path-based, we have a surprisingly good result approximating to 100%, meaning almost entirely accurate clustering. This implies the great importance of the intrinsic graph structure with a comprehensive analysis of which we obtain a significantly success over other methods.Figure 3
Results of comparing methods on two-moon and path-based datasets. GT denotes the ground truth. (a)k-means, (b) R-cut, (c) ST-SC,(d) RG-SC, (e) CAN, (f) CLR, (g) k-GC, (h) GT, (i) k-means, (j) R-cut, (k) ST-SC, (l) RG-SC, (m) CAN, (n) CLR, (o) k-GC, and (p) GT.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)(m)(n)(o)(p)Figure4 shows that the objective value of k-GC, equation (7), is nonincreasing during iterations. They all converge to a fixed value very fast in 10 iteration times. k-GC only needs several times to iterate alternately to obtain a cut-zeroed graph while the conventional SC-based methods need to perform postprocessing by using k-means clustering algorithm. Therefore, the k-GC algorithm is effective overall.Figure 4
Convergence behaviors ofk-GC. (a) Two-moon dataset. (b) Path-based dataset. (c) Yale dataset. (d) ORL dataset. (e) COIL-20 dataset. (f) Notting-Hill dataset.
(a)(b)(c)(d)(e)(f)


## 5. Conclusion

In this paper, we have proposed a novelk-component graph clustering method, which learns to obtain a graph with exact k-connected components. Since the vertices in each connected component of the intrinsic graph belong to one cluster, labels are obtained directly from the learned graph itself without performing further graph-cut or k-means clustering algorithms. k-GC learns the affinity matrix and clustering structure simultaneously. Moreover, k-GC can serve as an alternative to SC due to its simplicity and the effectiveness over the standard SC. This paper focuses on the spectral analysis of the graph Laplacian, to which the sum of top k smallest eigenvalues is zeroed. It renders the graph structure update until it has exactly k number of components. The efficient algorithm as well as the optimization algorithm is presented after plentiful analysis. Experiments on six benchmarks have demonstrated the superiority of k-GC.



---

*Source: 5175210-2020-08-06.xml*