Abstract
Abstract-Spectral clustering is a powerful tool for unsupervised data analysis. In this paper, we propose a contextaware hypergraph similarity measure (CAHSM), which leads to robust spectral clustering in the case of noisy data. We construct three types of hypergraph-the pairwise hypergraph, the k-nearest-neighbor (kNN) hypergraph, and the high-order over-clustering hypergraph. The pairwise hypergraph captures the pairwise similarity of data points; the kNN hypergraph captures the neighborhood of each point; and the clustering hypergraph encodes high-order contexts within the dataset. By combining the affinity information from these three hypergraphs, the CAHSM algorithm is able to explore the intrinsic topological information of the dataset. Therefore, data clustering using CAHSM tends to be more robust. Considering the intracluster compactness and the inter-cluster separability of vertices, we further design a discriminative hypergraph partitioning criterion (DHPC). Using both CAHSM and DHPC, a robust spectral clustering algorithm is developed. Theoretical analysis and experimental evaluation demonstrate the effectiveness and robustness of the proposed algorithm.
INTRODUCTION
Spectral clustering is an effective means of clustering data with complex topological structure [8] - [13] , [15] , [16] , [31] , [34] - [36] . It plays an important role in unsupervised learning from data, and therefore has a wide range of applications, including circuit layout [1] , [2] , load balancing [3] , image segmentation [4] - [7] , [14] , motion segmentation [25] , video retrieval [26] , etc. Typically, the affinity relationships between data samples are modeled by a graph, and therefore spectral clustering aims to optimize a graph partitioning criterion for data clustering based on local vertex similarities. However, there are still several unsolved issues for traditional spectral clustering methods: i) how to automatically discover the number of clusters; ii) how to correctly choose the scaling parameter for graph construction; iii) how to counteract the adverse effect of noise or outliers; and iv) how to incorporate different types of information to enhance the clustering performance.
INTRODUCTION
In the literature, Zelnik-Manor and Perona [11] attempt to address issues i) and ii) by designing a local scaling mechanism, which adaptively calculates the affinity matrix and explores the intrinsic structural information on the energy eigenvalue spectrum of the normalized graph Laplacian to discover the number of clusters. However, this local scaling mechanism is susceptible to noise or outliers. Following [11] , Li et al. [15] propose a noise robust spectral clustering (NRSC) algorithm to resolve issues i) and iii). The proposed NRSC algorithm can automatically estimate the number of clusters via computing the largest eigenvalue gap of the normalized graph Laplacian. In addition, the proposed NRSC algorithm maps the original data samples (vertices) into a new space, in which the clusters have a higher intra-cluster compactness and inter-cluster separability. If the noisy data samples are weakly interconnected with each other, this mapping relocates the noisy data samples around the origin of the new space. This usually results in a compact noise cluster. However, the real-world data samples (e.g., images and videos) within a cluster are often not densely interconnected due to problems with the visual feature description. Therefore, the mapping may lead to topological information loss for the clusters. As a result, the weakly interconnected samples in the ordinary clusters are also relocated around the origin of the new space. This may result in low separability between clusters.
INTRODUCTION
More recently, hypergraph analysis [17] , [18] has emerged as a popular tool for addressing issues iii) and iv). The fundamental idea of hypergraph analysis is to explore the underlying affinity relationships among vertices by constructing a hypergraph with a variety of hyperedges that capture affinity. This has been applied to many domains such as image matching [19] , multi-label classification [20] , video object segmentation [21] , and image retrieval [22] . For example, Sun et al. [20] carry out hypergraph construction by sequentially introducing new vertices into existing hyperedges using clique expansion or star expansion. Huang et al. [22] propose a probabilistic hypergraph model that softly assigns a vertex to a hyperedge according to the similarity between the vertex and the centroid of the hyperedge.
INTRODUCTION
Motivation and contribution In general, most existing spectral clustering algorithms only focus on the pairwise interactions between vertices. In other words, the pairwise similarity between two vertices is only based on the individual vertices themselves. If a vertex is corrupted, this pairwise similarity can change significantly. Consequently, their true affinity may not be stably represented. Thus, designing a robust similarity measure is one of the key problems in data clustering.
INTRODUCTION
Here, we show that the high-order contextual information on vertices can help alleviate this problem. Contexts are groups of vertices that share some common properties. Once contexts have been computed, the vertex similarity measure depends on not only two individual vertices but also their corresponding contexts. The similarity measure that includes contextual information is much more stable because it takes into account local grouping and neighborhood information of each vertex. When a single vertex is corrupted, the high-order contextual similarity can still provide complementary information to counteract the impact of the corruption.
INTRODUCTION
Motivated by this observation, we propose a robust spectral clustering algorithm based on a context-aware hypergraph similarity measure. We use three different types of hypergraphs: pairwise hypergraph, k-nearest-neighbor (kNN) hypergraph, and high-order over-clustering hypergraph. The top-left subfigure shows the pairwise edge between any vertex and its two nearest neighbors; the top-right subfigure displays the associated hypergraph structure whose hyperedges (highlighted by ellipses of different colors) consist of each vertex and its two nearest neighbors; the bottom-left subfigure shows the kNN hypergraph incidence matrix Hn; and the bottom-right subfigure exhibits the kNN hypergraph similarity matrix B.
INTRODUCTION
encoding pairwise affinity information on vertices. In contrast, the kNN hypergraph and the over-clustering hypergraph capture the underlying manifold structure on vertices by modeling their highorder neighborhood and contextual grouping properties, respectively. By combining these hypergraphs, we obtain the context-aware hypergraph similarity measure that characterizes the intrinsic connectivity relationships among vertices, resulting in the clustering robustness in the case of noise or outlier corruption. The main contributions of this work are therefore three-fold.
INTRODUCTION
• We introduce a high-order context into the spectral clustering process. The high-order context of a vertex is defined as a set of vertices with similar properties to the vertex. Each vertex in a context is influenced by other vertices in the same context. • The problem of building the high-order context is converted to that of hypergraph construction, which encodes the local affinity information using different types of hypergraphs. To this end, we design three types of hypergraphs to encode the pairwise, neighboring, and local grouping information on vertices. Based on these hypergraphs, we further propose a context-aware hypergraph similarity measure (CAHSM) to capture the intrinsic topological information on vertices. In essence, CAHSM is a generalization of traditional similarity measures, and aims to utilize the hypergraph context to explore the underlying affinity relationships between vertices.
INTRODUCTION
• We propose a discriminative hypergraph partitioning criterion (DHPC) to characterize the intra-cluster compactness and the inter-cluster separability of vertices. By maximizing the DHPC, we effectively capture the discriminative information on vertices. The optimization of DHPC can be relaxed into a trace-ratio maximization problem. Using both CAHSM and DHPC, we develop a pairwise+kNN+over-clustering hypergraph spectral clustering algorithm (referred to as PKO+HSC) for data clustering.
CONTEXT-AWARE HYPERGRAPH CONSTRUCTION
In what follows, we first discuss how to construct a robust hypergraph similarity measure using three different types of hypergraphs, and then describe a discriminative hypergraph partitioning criterion for data clustering.
Context-aware hypergraph similarity measure
In order to effectively explore the high-order affinity relationships among vertices, we propose a hypergraph construction mechanism Specifically, the upper part of (a) shows the 3 nearest neighbors of the face image highlighted by the dot-dashed bounding box; the lower part of (a) displays a vertex community that is a high-order context of the face image highlighted by the dot-dashed bounding box; the upper and lower parts of (b) respectively exhibit the clustering results containing the face image (highlighted by the dot-dashed bounding box) using pairwise+kNN and pairwise+kNN+over-clustering hypergraph similarities (respectively corresponding to PK+HSC and the proposed PKO+HSC). Clearly, the proposed pairwise+kNN+over-clustering similarity measures performs best.
Context-aware hypergraph similarity measure
based on three types of hypergraphs, which are the pairwise hypergraph, the k-nearest-neighbor (kNN) hypergraph, and the overclustering hypergraph. The pairwise hypergraph reflects the pairwise relationships between vertices; the kNN hypergraph characterizes the neighboring information on vertices, and the over-clustering hypergraph captures the local grouping relationships among vertices. By combining these three types of hypergraphs, the proposed hypergraph construction mechanism is capable of exploring the underlying highorder affinity relationships among vertices.
Context-aware hypergraph similarity measure
denote a sample set. Based on Z = {zi} N i=1 , we create a pairwise graph Gp with N vertices. Mathematically, the graph Gp can be denoted as Gp = (V, Ep, Wp), where V = {vi} N i=1 is the vertex set corresponding to {zi} N i=1 , Ep ⊆ V × V is the edge set containing all possible pairwise edges, and Wp is the edge-weight function returning the affinity value between two vertices. In practice, the graph Gp is formulated as a weighted similarity matrix A = (aij)N×N :
Context-aware hypergraph similarity measure
where Wp(vi, vj) = G(zi, zj) is a kernel function used for measuring the similarity between zi and zj. Note that the above procedure of graph creation is independent of the choice of kernel functions. In other words, it is easy to incorporate various kernel functions into the above graph creation process.
Context-aware hypergraph similarity measure
According to the hypergraph theory, the pairwise graph Gp is merely a special hypergraph whose hyperedge cardinality equals 2. Therefore, we reformulate Gp using the hypergraph terminologies. As a generalization of a traditional pairwise graph, a hypergraph is composed of many hyperedges, and each hyperedge corresponds to a set of vertices which have some common properties. Mathematically, these hyperedges are generally associated with a hypergraph incidence matrix Hp = (hp(vi, e p )) |V|×|Ep| :
Context-aware hypergraph similarity measure
where e p = (vm, vn) is the -th hyperedge of Ep. In order to measure the degree of the within-hyperedge vertices belonging to the same cluster, we introduce the notion of the pairwise hyperedge weight, which is defined as the pairwise similarity of the vertices in each hyperedge. So we can define the pairwise hypergraph similarity as:
Context-aware hypergraph similarity measure
where ηp(e p ) is the corresponding hyperedge weight of e p = (vm, vn) such that ηp(e p ) = amn. As a result, we have a weighted hypergraph similarity matrix U = (uij)N×N that characterizes the pairwise affinity relationships between vertices. For simplicity, the resulting pairwise hypergraph similarity matrix is represented as its corresponding matrix form:
Context-aware hypergraph similarity measure
where Σp is a diagonal matrix whose diagonal elements are denoted as (ηp(e p )) e p ∈Ep . 2) k-nearest-neighbor (kNN) hypergraph. Based on the neighboring information on vertices, we further define a kNN hypergraph Gn, as shown in Fig. 1 . For each vertex v , we search its corresponding k nearest neighbors {vq|vq ∈ N k v } (as shown in Fig. 2(a) ), and then use these nearest neighbors to form a kNN hyperedge e n . By concatenating all the kNN hyperedges, a kNN hyperedge set is generated as En = {e n } N =1 , as illustrated in Fig. 3 . To characterize the vertex-to-hyperedge membership, we define an indicator function as:
Context-aware hypergraph similarity measure
Based on this indicator function, we design a hypergraph model for softly assigning a vertex to each hyperedge:
Context-aware hypergraph similarity measure
where δt is the hyperedge weight associated with the t-th hyperedge e n t such that δt = 1 |e n t | j∈{r|vr ∈e n t } atj, and a i represents the vertex-to-hyperedge similarity between vi and the -th kNN hyperedge e n . Specifically, e n is composed of a centroid vertex v and its corresponding k nearest vertices. Based on Eq. (1), the vertexto-hyperedge similarity a i is computed as the pairwise similarity between vi and v . As a result, we obtain a kNN hypergraph incidence matrix Hn = (hn(vi, e n )) |V|×|En| for capturing the vertex-tohyperedge relationships. Based on Hn, a kNN hypergraph similarity bij between vi and vj is derived as:
Context-aware hypergraph similarity measure
where xm = a m I(vm, e n )δ
Context-aware hypergraph similarity measure
, < ·, · > is the inner product operator, and · is the 2-norm. Indeed, xm is a vertex-to-hyperedge feature vector that characterizes the correlation between vm and the kNN hyperedges. For example, the -th element of xm contains two terms: a m and I(vm, e n )δ . The first term a m is the pairwise similarity between vm and the vertex v of the -th kNN hyperedge, and the second term I(vm, e n )δ measures the cohesiveness of the -th kNN hyperedge by computing the average connection similarity between the vertex v and the other vertices in the -th kNN hyperedge. Thus, the kNN hypergraph similarity bij can be interpreted as the cosine similarity between two vertex-to-hyperedge feature vectors xi and xj. As a result, we obtain a weighted similarity matrix B = (bij)N×N associated with Gn. Essentially, B = (bij)N×N aims to explore the local neighboring relationships between vertices. For simplicity, the kNN hypergraph similarity matrix B is denoted as its corresponding matrix form: B = HnΣnH T n where Σn is a diagonal matrix with the -th diagonal element being δ . Fig. 1 gives an illustration of the process of the kNN hypergraph construction.
Context-aware hypergraph similarity measure
3) High-order over-clustering hypergraph. In practice, the vertices are often distributed in different cohesive vertex communities, and each community contains a set of mutually correlated vertices with some common properties. In order to effectively discover such cohesive vertex communities, we propose a high-order over-clustering hypergraph Go based on over-clustering (or over-segmentation) using different clustering methods. Specifically, an over-clustering mechanism is employed to generate a set of vertex groups, each of which corresponds to a cohesive vertex community (as shown in Fig. 2(a) ). In this case, the vertices belonging to the same vertex community are mutually influenced, and work as the high-order contexts of the other vertices in the same vertex community, as illustrated in Fig. 4 . Without loss of generality, we assume that there are L vertex communities in total. For convenience, let
Context-aware hypergraph similarity measure
denote these vertex communities, each of which corresponds to a hyperedge e o . Based on these hyperedges, we define the high-order over-clustering hypergraph incidence matrix Ho = (ho(vi, e o )) |V|×L as:
Context-aware hypergraph similarity measure
where I(·, ·) is the indicator function in Eq. (5), N i is the corresponding vertex index set of the nearest neighbors of vi in the hyperedge e o (s.t. |N i | = 3 in the experiments), and µ is the associated hyperedge weight of e o such that:
Context-aware hypergraph similarity measure
Here, ami is the vertex-to-hyperedge similarity between vi and the -th over-clustering hyperedge e o . To ensure the robustness of similarity evaluation, we only take into account the affinity relationships between vi and its corresponding nearest neighbors (indexed by N i ) in e o . Therefore, ami is the similarity between vi and the m-th vertex of N i . With the definition of Ho, the high-order over-clustering hypergraph similarity cij between vi and vj is formulated as: (9), the left term measures the average cross-link degree of the within-community-vertices with respect to the other vertices in the same community, while the right term reflects the average affinity relationships between vq and the vertices in the -th community. Therefore, the high-order over-clustering hypergraph similarity cij can be viewed as the cosine similarity between two vertexto-hyperedge feature vectors yi and yj. As a result, a weighted similarity matrix C = (cij)N×N is obtained to capture the local grouping information on vertices. For simplicity, the high-order overclustering hypergraph similarity matrix C can be expressed as its corresponding matrix form: C = HoΣoH T o , where Σo is a diagonal matrix with the -th diagonal element being µ . Fig. 5 gives an example of showing the different hypergraph similarity matrices on the ORL face dataset (referred to in Sec. 3). By linearly combining the above three types of hypergraphs, a contextaware hypergraph similarity matrix S = (sij)N×N is obtained as follows:
Context-aware hypergraph similarity measure
where H = (Hp Hn Ho) and (α, β) are the nonnegative weighting factors such that (α + β) ≤ 1. Encoding the local neighboring information, the kNN hypergraph plays a role in locally smoothing the clustering results (obtained by only using the pairwise hypergraph), as shown in the bottom-left part of Fig. 5 . By constructing the highorder over-clustering hypergraph, we are capable of capturing the manifold structure information among data samples at larger scales, which leads to more accurate clustering results (shown in the bottomright part of Fig. 5 ). Therefore, the final context-aware hypergraph similarity matrix keeps a balance among the three types of hypergraph information. In practice, it is easy to emphasize one particular type of hypergraph information by enlarging its associated weight. Specifically, the top-left subfigure shows the ground truth similarity matrix of the ORL face dataset (referred to in Sec. 3); the top-right subfigure displays the pairwise hypergraph similarity matrix; the bottom-left subfigure exhibits the pairwise+kNN hypergraph similarity matrix; the bottom-right subfigure draws our pairwise+kNN +over-clustering hypergraph similarity matrix. Clearly, our hypergraph similarity matrix is the closest to the ground truth.
Context-aware hypergraph similarity measure
based on the above hypergraph similarities.
Discriminative hypergraph partitioning for spectral clustering
Having defined a context aware vertex similarity measure, we now propose a discriminative hypergraph partitioning criterion based on this measure, with its corresponding optimization procedure. 1) Preliminaries of hypergraph partitioning. Hypergraph partitioning seeks an optimal hypergraph cut solution for effective data clustering. K-way normalized cut [12] is a well-known hypergraph partitioning criterion, which aims to optimally partition the vertex set V into K disjoint subsets (i.e., V = K l=1 V l s.t. Vm Vn = ∅, ∀m = n) by solving the following optimization problem:
Discriminative hypergraph partitioning for spectral clustering
where X is an N × K partition matrix such that X T X is a diagonal matrix, 1 d denotes a d × 1 vector with each element being 1, D is an N × N diagonal matrix with the m-th diagonal element being the sum of the elements belonging to the m-th row of S for 1 ≤ m ≤ N , and Xn is the n-th column of X for 1 ≤ n ≤ K. As pointed out in [12] , the optimization problem (12) is typically relaxed to:
Discriminative hypergraph partitioning for spectral clustering
where IK is a K × K identity matrix, tr(·) denotes the trace of a matrix, and Z = X(X T DX)
Discriminative hypergraph partitioning for spectral clustering
2 . Eq. (13) is a trace maximization problem and can be solved by generalized eigenvalue decomposition. To simultaneously capture both intra-cluster compactness and the inter-cluster separability among the vertices in a unified clustering framework, we propose a discriminative hypergraph partitioning criterion which can be formulated as a trace-ratio optimization problem.
Discriminative hypergraph partitioning for spectral clustering
2) Discriminative hypergraph partitioning criterion (DHPC). The proposed DHPC considers both the inter-cluster separability and the intra-cluster compactness, and thus aims to solve the following
Discriminative hypergraph partitioning for spectral clustering
and the number of clusters K 1) Obtain the hypergraph similarity matrix S = (sij ) N ×N .
Discriminative hypergraph partitioning for spectral clustering
• Compute the pairwise hypergraph similarity u p ij in Eq. (3).
Discriminative hypergraph partitioning for spectral clustering
• Obtain the kNN hypergraph similarity u n ij in Eq. (7).
Discriminative hypergraph partitioning for spectral clustering
• Compute the high-order over-clustering hypergraph similarity u c ij in Eq. (10).
Discriminative hypergraph partitioning for spectral clustering
• Combine the above three similarities to generate sij by Eq. (11). 2) Perform spectral graph partitioning.
Discriminative hypergraph partitioning for spectral clustering
• Compute the graph Laplacian matrix Q = D − S.
Discriminative hypergraph partitioning for spectral clustering
• Solve the optimization problem (19) by the Newton-Lanczos algorithm.
Discriminative hypergraph partitioning for spectral clustering
• Calculate a candidate graph partitioning solution X by:
Discriminative hypergraph partitioning for spectral clustering
• Iteratively refine X to find an optimal discrete solution X. Output: The optimal graph partitioning solution X.
Algorithm 1:
The proposed pairwise+kNN+over-clustering hypergraph spectral clustering algorithm (PKO+HSC).
Algorithm 1:
optimization problem:
Algorithm 1:
where Q = D − S. In the proposed DHPC, the intra-cluster compactness and the inter-cluster separability are respectively captured by X T n SXn and X T n QXn, which are formulated as:
Algorithm 1:
where Vn denotes the vertex set belonging to the n-th cluster. The larger the value of X T n SXn, the more compact the intra-cluster samples. The smaller the value of X T n QXn, the more separable the inter-cluster samples. As a result, an optimal hypergraph partitioning solution is obtained by maximizing g(X) in Eq. (14) . For simplicity, let Pn denote the vertex-to-cluster membership vector associated with the n-th cluster such that Pn = Xn(X T n Xn) − 1 2 , and P denote the vertex-to-cluster membership matrix that is a concatenation of all the vertex-to-cluster membership vectors such that P = (P1 P2 . . . PK) = X(X T X)
Algorithm 1:
. It can be shown that P is an orthogonal matrix:
Algorithm 1:
where X T X is a diagonal matrix. According to the conclusion in [12] , we obtain X = Diag(diag
Algorithm 1:
Here, Diag(·) denotes a diagonal matrix formed from its vector argument, and diag(·) represents a column vector formed from the diagonal elements of its matrix argument. Consequently, the optimization problem in Eq. (14) can be rewritten as:
Algorithm 1:
This is a trace-ratio-sum optimization problem, which is non-convex and difficult to solve [28] . Thus, we approximate the original optimization problem (17) using the following sum-trace-ratio optimization problem:
Algorithm 1:
Due to tr(
Algorithm 1:
, the above optimization problem (18) can be reformulated as:
Algorithm 1:
The trace-ratio optimization problem (19) has been investigated in [29] , [30] , [33] , [38] . In order to obtain an effective solution to Eq. (19), we therefore utilize the Newton-Lanczos algorithm [33] for trace-ratio maximization. The Newton-Lanczos algorithm includes the following three iterative steps:
Algorithm 1:
• Compute the trace ratio ρ = tr(P T SP ) tr(P T QP ) ; • Run the Lanczos algorithm [37] to compute the K largest eigenvalues of S − ρQ as well as their associated eigenvectors (P1 P2 . . . PK) ≡ P ; • Repeat the above two steps until convergence. In practice, the initial solution P is chosen as the K principal eigenvectors (i.e., corresponding to the K largest eigenvalues) of the matrix Q −1 S. If Q is a singular matrix, Q −1 S is replaced with the matrix (Q + IN ) −1 S, where IN is an N × N identity matrix and is a small positive constant ( = 10 −6 in the experiments). After solving the trace-ratio optimization problem (19), we obtain a candidate solution X to Eq. (14) as follows:
Algorithm 1:
However, the candidate solution X is a real-valued hypergraph partitioning solution, and thus does not satisfy the discrete-solution requirements for data clustering. As a result, an iterative refining procedure [12] may be used to find the optimal discrete hypergraph partitioning solution X to Eq. (14) (more details can be found in Steps four to eight of the algorithm in [12] ). After combining the constructed pairwise+kNN+over-clustering hypergraphs (referred to in Sec. 2.1), we have a DHPC-based spectral clustering algorithm called PKO+HSC (pairwise+kNN+over-clustering hypergraph spectral clustering), as listed in Algorithm 1.
EXPERIMENTS

Data description and implementation details
In the experiments, we evaluate the proposed PKO+HSC on seven datasets, which have the ground truth labels for classification and clustering tasks. The detailed configurations of these datasets are given as follows.
Data description and implementation details
The first dataset is the ORL face dataset 1 . It comprises 400 face images of 40 persons, and each person has 10 images. The second dataset is a subset of the YaleB face dataset 2 , and contains 2432 near frontal face images from 38 individuals under different illuminations. For computational convenience, all the face images from the two datasets are resized to 32 × 32 pixels. The third dataset is a subset of the US Postal Service (USPS) handwritten digit dataset 3 , and consists of 9298 16 × 16 handwritten digit images from ten clusters. The fourth dataset is a subset of the MNIST handwritten digit dataset 4 , and constitutes 2000 28 × 28 digit images from ten clusters. As shown in Fig. 6 , the fifth dataset [27] is a trajectory dataset containing 2500 trajectories from 50 clusters, and each cluster comprises 50 trajectories with complex shapes. The sixth dataset is the Iris dataset from the UCI repository 5 , and contains 150 samples from 3 clusters. The seventh dataset is the Corel image dataset 6 that is composed of 1000 images from ten clusters, as shown in Fig. 7 .
Data description and implementation details
For graph construction, the features used in the two face datasets and the two digit datasets are directly flattened into grayscale intensity column vectors. As a result, the feature dimensions for these four datasets are 1024 (ORL), 1024 (YaleB), 256 (USPS), and 784 (MNIST), respectively. In addition, the corresponding image features for the Corel dataset are the 960-dimensional GIST descriptors (as in [23] ) that are widely used in computer vision and pattern recognition. The corresponding features for the trajectory dataset are 18-dimensional discrete Fourier transform (DFT) coefficient features (as in [24] ). The feature dimension for the Iris dataset is 4, as shown in the UCI repository. Moreover, the kernel function G(zi, zj) (as in Eq. (3) The task of constructing the high-order over-clustering hypergraph can be accomplished by using a set of existing clustering methods. In our case, we take advantage of classic spectral clustering [10] and multi-class spectral clustering [12] to generate a set of vertex communities. For each over-clustering method, the number of the vertex communities is chosen as 2K with K being the desired number of clusters (referred to in Algorithm 1). Since we focus on the issues of iii) and iv) referred to in Sec. 1, K is directly set as the ground truth number of clusters for each dataset. The above experimental configurations remain the same for all the experiments below.
Data description and implementation details
Computational complexity analysis Given N data samples, our pairwise hypergraph construction requires N 2 kernel computation operations (referred to in Eq. (1)). Accordingly, the kNN hypergraph construction needs to calculate N 2 cosine similarities (defined in Eq. (7)) with respect to the N data samples. Similarly, the overclustering hypergraph construction involves N 2 cosine similarity computation operations (mentioned in Eq. (10)). The main computational cost of graph partitioning lies in the eigenvalue decomposition of S − ρQ while solving the optimization problem (19) using the Newton-Lanczos algorithm. According to [37] , the time complexity of the Lanczos iterations in our graph partitioning is O(N 2 ). Therefore, the overall time complexity of our method is O(N 2 ), which is the same as standard spectral clustering methods. For example, the average running time of our method on the USPS dataset (s.t. N = 9298) is 15.21 seconds. The spatial complexity of our method lies in the four aspects: 1) the N × N pairwise hypergraph incidence matrix Hp; 2) the N × N kNN hypergraph incidence matrix Hn; 3) the N × N over-clustering hypergraph incidence matrix Ho; and 4) the final N × N similarity matrix S. It therefore has O(N 2 ) overall spatial complexity.
Competing algorithms
We compare the proposed PKO+HSC with several representative spectral clustering algorithms. These spectral clustering algorithms are recently proposed, and have significant impacts on the data clustering community. For descriptive convenience, they are respectively referred to as CSC (classic spectral clustering [10] ), STSC (selftuning spectral clustering [11] ), and NRSC (noise-robust spectral clustering [15] ).
Competing algorithms
In order to verify the effect of different hypergraph components, we compare the proposed PKO+HSC with PK+HSC (pairwise+kNN hypergraph spectral clustering) and PO+HSC (pairwise+over-clustering hypergraph spectral clustering). Actually, PK+HSC and PO+HSC are special cases of the proposed PKO+HSC with different configurations of (α, β). In order to evaluate the performance of different graph partitioning criteria, we perform a comparison experiment against PKO+NC (our context-aware hypergraph similarity measure together with the normalized cut criterion [12] ). Furthermore, in order to demonstrate the effectiveness of our context-aware hypergraph similarity measure (defined in Eq. (11)), we make a quantitative comparison with another similarity measure called RWDSM (Random Walk Diffusion Similarity Measure [32] ). We put both RWDSM and our similarity measure into the same discriminative hypergraph partitioning criterion (DHPC) for data clustering.
Evaluation criteria
For a quantitative comparison, we introduce two evaluation criteria-NMI (normalized mutual information) and clustering accuracy. Specifically, the NMI criterion is defined as: NMI(X, Y) = As far as data clustering is concerned, the NMI criterion is explicitly formulated as:
Evaluation criteria
where
Evaluation criteria
is the ground truth clustering configuration of a dataset, S = {S j } K j=1 is the clustering configuration obtained by a clustering algorithm, C is the ground truth cluster number, K is the obtained cluster number, qij is the cardinality of the intersection of Si and S j , mi is the cardinality of Si, m j is the cardinality of S j , and m is the cardinality of the whole dataset. The larger the NMI, the better the clustering performance.
Evaluation criteria
On the other hand, the clustering accuracy is defined as: Accuracy = 1 m K j=1 nj where nj is the number of the samples whose ground truth cluster labels have the highest proportion in the j-th cluster S j . The larger the clustering accuracy, the better the clustering results.
Clustering results
In the experiments, we aim to evaluate the clustering performances of different clustering algorithms in the following three aspects: i) evaluating the clustering performances (i.e., NMI and clustering accuracy) on the original datasets; ii) quantitative comparisons on the datasets after noise-based feature perturbations; and iii) performance evaluations on the datasets with outlier corruptions. The purposes of the above-mentioned three aspects are to verify the clustering effectiveness and the clustering robustness.
Clustering results
For i), Tab. 1 reports the corresponding NMIs and accuracies of the eight clustering algorithms. It is seen from Tab. 1 that the proposed PKO+HSC obtains higher NMIs and accuracies than the other clustering algorithms. More specifically, the average NMI gains of PKO+HSC regarding the seven datasets are (5 configurations of the weighting factors (α, β). From Tab. 2, we see that the clustering performances of the proposed PKO+HSC are not very sensitive to the configurations of the weighting factors.
Clustering results
For ii), noise-based feature perturbations are performed by using additive random noises. Figs. 8 and 9 show the NMI and accuracy curves with error bars in eleven different noise levels (i.e., L0 corresponds to i), and L1 → L10 are associated with ten ascending noise levels whose magnitudes are chosen from {0.2, 0.4, 0.6, 0.8, 1.0, 1.2, 1.4, 1.6, 1.8, 2.0}). Clearly, the proposed PKO+HSC achieves the highest NMIs and accuracies in most noise levels. Furthermore, Tab. 3 reports the average NMIs and accuracies of the eight clustering algorithms regarding different noise levels. The average NMI and accuracy gains of the proposed PKO+HSC are (6.03%, 5.19%, 2.80%, 23.54%, 34.54%, 26.92%, 20.43%) and (7.01%, 6.71%, 3.14%, 24.78%, 35.19%, 28.81%, 24.32%) over those of (PK+HSC, PO+HSC, PKO+NC, CSC, NRSC, RWDSM, STSC), respectively.
Clustering results
For iii), outlier corruptions are performed by randomly setting the feature elements to zeros. Fig. 10 displays the clustering performances of the eight clustering algorithms regarding four outlier corruption levels (i.e., L0 corresponds to i), and L1 → L3 are associated with three ascending corruption levels whose corruption ratios are chosen from {0.2, 0.4, 0.6}). From Fig. 10 , we see that the proposed PKO+HSC consistently achieves higher NMIs and accuracies than the other clustering algorithms. Moreover, Tab. 4 shows the average NMIs and accuracies of the eight clustering algorithms regarding different outlier corruption levels. The average NMI and accuracy gains of the proposed PKO+HSC are (7.87%, 2.96%, 2.99%, 11.02%, 30.55%, 14.83%, 30.58%) and (7.39%, 3.80%, 2.91%, 10.11%, 34.62%, 14.04%, 33.66%) over those of (PK+HSC, PO+HSC, PKO+NC, CSC, NRSC, RWDSM, STSC), respectively.
Clustering results
Besides, we report the clustering results of the proposed PKO+HSC with different configurations of the nearest-neighbor number k for kNN hypergraph construction in Fig. 11. From Fig. 11 , we see that the proposed PKO+HSC is not very sensitive to the settings of k. Moreover, Fig. 12 shows the clustering performances of the proposed PKO+HSC using different numbers of vertex communities for highorder over-clustering hypergraph construction in NMI and clustering accuracy on the two datasets. It is clearly seen from Fig. 12 that the proposed PKO+HSC is not very sensitive to the choice of the vertex community number. Overall, the proposed PKO+HSC outperforms the other clustering algorithms. Considering three types of hypergraph information (i.e., pairwise, kNN, and over-clustering), the proposed PKO+HSC is capable of effectively exploring the intrinsic topological information among vertices. By optimizing the discriminative hypergraph partitioning criterion (DHPC), the proposed PKO+HSC considers both intra-cluster compactness and inter-cluster separability, resulting in the overall clustering robustness.
CONCLUSION AND FUTURE WORK
In this work, we have proposed a context-aware hypergraph similarity measure (CAHSM), which is based on three types of hypergraphspairwise hypergraph, k-nearest-neighbor (kNN) hypergraph, and high-order over-clustering hypergraph. These hypergraphs capture the pairwise, neighborhood, and local grouping information on vertices. By effectively combining these types of affinity information, CAHSM is capable of effectively exploring the intrinsic structural information on vertices, resulting in the robust clustering performance. In order to fully capture the intra-cluster compactness and the inter-cluster separability of vertices, we have also designed a discriminative hypergraph partitioning criterion (DHPC) that is solved by traceratio maximization. Based on both CAHSM and DHPC, a robust spectral clustering algorithm (referred to as PKO+HSC) is developed for data clustering. Experimental results on various datasets, with and without noisy perturbation and outlier corruption, demonstrate that the proposed PKO+HSC has higher clustering robustness and effectiveness than competing algorithms in most cases. On the other hand, this work is likely to have two limitations: 1) it is incapable of adaptively combining the aforementioned three types of hypergraphs; and 2) the number of clusters in spectral clustering is required to be provided in advance. Therefore, our future work is to figure out an adaptive weighting mechanism for hypergraph combination and an effective scheme for automatically estimating the cluster number prior to spectral clustering.

{'paper_id': '8215877', 'title': 'Context-Aware Hypergraph Construction for Robust Spectral Clustering', 's2_url': 'https://api.semanticscholar.org/CorpusID:8215877', 'source': 'S2ORC'}