Semi-Supervised Clustering via Structural Entropy with Different Constraints

Considering a graph $G=(V,E,\mathbf{W})$ associated to a given dataset $\mathcal{X}=\{x_{1},x_{2},...,x_{n}\}$, where $x_{i}$ is a data point, $V=\{v_{1},v_{2},...,v_{n}\}$ correspond to data points in $\mathcal{X}$, the edges in $E$ connect similar data points, and edge weights in $\mathbf{W}$ represent similarity of data points. We aim to partition graph vertices in $G$ with certain given prior information in the form of constraints to achieve semi-supervised data clustering. The pairwise constraints and label constraints are formulated as follows.

Pairwise constraints reveal the relationship between a pair of vertices in $G$. They consist of a set of must-link constraints $M=\{(v_{i},v_{j}):\>l_{i}=l_{j}\}$, indicating that vertex pair $(v_{i},v_{j})$ must belong to the same cluster, and a set of cannot-link constraints $C=\{(x_{i},x_{j}):\>l_{i}\neq l_{j}\}$, indicating that vertex pair $(v_{i},v_{j})$ must belong to different clusters, where $l_{i}$ is the cluster indicator of $v_{i}$. Pairwise constraints can be stored in a relation graph $G^{\prime}=(V,E^{\prime},\mathbf{W^{\prime}})$, which shares the same vertex set with $G$. If there exists a vertex pair $(v_{i},v_{j})\in M$, an edge exists in $E^{\prime}$ with a positive value $\gamma_{M}$ added to the edge weight $\mathbf{W}^{\prime}_{ij}$. If there exists a vertex pair $(v_{i},v_{j})\in C$, an edge exists in $E^{\prime}$ with a negative value $\gamma_{C}$ added to the edge weight $\mathbf{W}^{\prime}_{ij}$. The values of $\mathbf{W}$ and $\mathbf{W^{\prime}}$ are set in Implementation Details in Section 4.

Label constraints reveal the relationship between vertices in $G$ and ground truth class labels. They include a set of positive-label constraints $P=\{(v_{i},y_{m}):\>v_{i}\in y_{m}\}$, indicating that the true class label of $v_{i}$ is $y_{m}$, and a set of negative-label constraints $N=\{(v_{i},y_{m}):\>v_{i}\notin y_{m}\}$, indicating that the true class label of $v_{i}$ is not $y_{m}$. To form a uniform representation of constraints, we convert label constraints into pairwise constraints which are more compatible for structural entropy. For two vertices $v_{i}$ and $v_{j}$, the conversion rules are set as follows: (1) If they both have positive constraints with the same label, an edge exists in $E^{\prime}$ with a positive value $\gamma_{M}$ added to the edge weight $\mathbf{W}^{\prime}_{ij}$. (2) If they both have positive constraints with different labels, an edge exists in $E^{\prime}$ with a negative value $\gamma_{C}$ added to the edge weight $\mathbf{W}^{\prime}_{ij}$. (3) If they have positive constraint and negative constraints respectively with the same label, an edge exists in $E^{\prime}$ with a negative value $\gamma_{C}$ added to the edge weight $\mathbf{W}^{\prime}_{ij}$.

The constraints are stored in the relation graph $G^{\prime}$ after construction, where a positive value indicates a must-link relationship and a negative value indicates a cannot-link relationship. However, this relation graph can be further improved by exploiting constraint transitivity and entailment [23]. We apply them sequentially on $G^{\prime}$ after constructing it.

In this subsection, we present 2-d SSE modified from 2-d structural entropy to perform semi-supervised partitioning clustering. For a graph $G$ associated with a data set $\mathcal{X}$ with different types of constraints, we transform all types of constraints into a uniform formulation and store them in a relation graph $G^{\prime}$. We aim to find a graph partitioning $\mathcal{P}$ of $G$ that minimizes the structural entropy of $G$ while also minimizing the number of violated constraints in the meantime. The optimization objective of two-dimensional structural entropy is defined as follows:

where $\mathcal{E}^{\mathcal{P}}(G,G^{\prime})$ is a penalty term for constraints violation, and it is defined as:

where $g^{\prime}_{X}$ is the weight sum of edges in $G^{\prime}$ between vertices in and not in module $X$, and other notations share the same meaning with notations in Eq. (2.4).

The intuition of the penalty term is that we modify $g_{X}$, i.e., the cut of module $X$ in Eq. (2.4) according to the constraints, which is increased when must-link constraints are violated, and decreased when cannot-link constraints are satisfied. A positive value of $\mathbf{W}^{\prime}_{ij}$ in $G^{\prime}$ means $v_{i}$ and $v_{j}$ should belong to the same module, and $\mathcal{E}^{\mathcal{P}}>0$ if they are not, leading to a penalty added to $\mathcal{L}^{\mathcal{P}}$. A negative value of $\mathbf{W}^{\prime}_{ij}$ in $G^{\prime}$ means $v_{i}$ and $v_{j}$ should belong to different modules, and $\mathcal{E}^{\mathcal{P}}<0$ if they are, leading to a reward added to $\mathcal{L}^{\mathcal{P}}$. When no constraint exists, i.e., $\mathcal{E}^{\mathcal{P}}=0$, we only minimize unsupervised 2-d structural entropy. In all, $\mathcal{E}^{\mathcal{P}}$ penalizes modules that violate must-link constraints and rewards modules that satisfy cannot-link constraints.

In both merging stage and moving stage, $\mathcal{L}^{\mathcal{P}}$ decreases after every iteration, and it converges when no improvement can be made. The time complexity of merging stage is $O(n{\log^{2}n})$ [15]. In the moving stage, each iteration requires calculating $\Delta\mathcal{L}^{\mathcal{R}}_{X,v_{i}}$ and $\Delta\mathcal{L}^{\mathcal{I}}_{Y,v_{i}}$ for every vertex $v_{i}$ and every possible module $Y$, which takes the time of $O(nl)$. Taken together, the time complexity of Algorithm 1 is $O(n\log^{2}n+nlt)$, where $n$, $l$ and $t$ denote the number of vertices, modules, and iterations respectively.

Hereafter, we generalize 2-d SSE into high-d SSE to perform semi-supervised hierarchical clustering. For a graph $G$ associated with data set $\mathcal{X}$ and constraints stored in a relation graph $G^{\prime}$, we aim to find an encoding tree with the height of $K>2$ to form a semi-supervised hierarchical clustering of vertices in $G$. Following the definition of 2-d SSE in Section 3.2, we define the optimization objective of high-d SSE as follows:

where $\mathcal{E}^{\mathcal{T}}(G,G^{\prime})$ is a penalty term for constraints violation, and it is defined as:

where $g^{\prime}_{\alpha}$ is the cut of $\alpha$ in $G^{\prime}$, $|T(\alpha)|$ is the number of vertices in subset $T(\alpha)$ associated to $\alpha$, and other notations share the same meaning with notations in Eq. (2.1). For each node except for leaves in $\mathcal{T}$, the penalty term penalizes the violation of must-link constraints and rewards the satisfaction of cannot-link constraints.

In this part, we aim to evaluate the performance of SSE on semi-supervised partitioning clustering. We conduct experiments on five clustering datasets including face image data (Yale and ORL), object image data (COIL20), spoken letter recognition data (Isolet), and handwritten digit data (OpticalDigits) following Bai et al. [1], whose size ranges from 165 to 5620. We also conduct experiments on four single-cell RAN-seq datasets including 10X PBMC, Mouse bladder, Worm neuron, and Human kidney taken from Tian et al. [22]. We choose the data preprocessed by the original authors to contain 2100 randomly sampled cells on the top 2000 highly dispersed genes in each dataset. We adopt two metrics including Adjusted Rand Index (ARI) [10] and Normalized Mutual Information (NMI) [21] for partitioning clustering performance evaluation. All experiments are repeated 10 times.

We generate constraints using the ground truth class labels from the datasets. For experiments with pairwise constraints, we set the number of must-link constraints the same as cannot-link constraints to be $0.2n$. For experiments with label constraints, we set the number of positive constraints the same as negative constraints to be $0.1n$. The parameters $\gamma_{M}$ and $\gamma_{C}$ control the role of constraints, we define them following Bai et al. [1]. For a pair of data points $(x_{i},x_{j})$ with similarity $\mathbf{W}_{ij}$, we define $\gamma_{M}=max(\mathbf{W})-\mathbf{W}_{ij}$, where $max(\mathbf{W})$ is the maximum similarity between all data points. The process of constraints conversion, constraints transitivity and entailment usually lead to more negative values than positive values in $G^{\prime}$. In order to balance them, we define $\gamma_{C}=\rho(min(\mathbf{W})-\mathbf{W}_{ij})$, where $\rho$ is the ratio between the number of positive values and negative values in $G^{\prime}$, $min(\mathbf{W})$ is the minimum similarity between all data points. The parameter $\phi$ balances the importance between input data and constraints, it is empirically set as $\phi=2$.

The experimental results on four single-cell RNA-seq datasets are presented in Table 2. SSE with pairwise constraints outperforms SE on three out of four datasets and outperforms baseline methods in the pairwise constraint group on all datasets. SSE with label constraints outperforms SE on three out of four datasets and outperforms baseline methods in the label constraint group on three out of four datasets. In all, SSE effectively incorporates prior information in the forms of pairwise constraints and label constraints, and achieves high clustering accuracy on both clustering datasets and single-cell RNA-seq datasets.

In this part, we aim to evaluate the performance of SSE on semi-supervised hierarchical clustering. We conduct experiments on four datasets downloaded from the LIBSVM webpage ²²2https://www.csie.ntu.edu.tw/$\sim$cjlin/libsvmtools/datasets/ following Chierchia and Perret [6], whose size ranges from 175 to 690. We adopt three metrics including Dendrogram Purity (DP) [9, 27], ARI [10], and NMI [21] for hierarchical clustering performance evaluation. DP is a holistic measure of a cluster tree, which is defined as the weighted average purity of each node of the tree with respect to a ground truth labelization of the tree leaves. We take the cluster tree of SSE from the binary encoding tree $\mathcal{T}_{b}$. ARI and NMI require partitioning clustering results from the cluster trees. We perform the $compressing$ operator until the height of the encoding tree is two to obtain the partitioning clustering results. For other methods, we choose the largest tree nodes from the cluster tree as the partitioning clustering results. All experiments are repeated 10 times.

The number of constraints has a great impact on the performance of semi-supervised clustering and a larger number of constraints is usually thought to lead to better performance. We evaluate the performance of SSE for partitioning clustering with different amounts of pairwise constraint, as shown in Figure 2. The ARI and NMI values are generally larger with more constraints except for OpticalDigits. For this dataset, SSE makes too many clusters when the constraints are more than $0.6n$, leading to poor performance. The cause of this problem is that the merging stage in Algorithm 1 stops earlier than expected, which calls for a better optimization algorithm. We also evaluate the performance of SSE for hierarchical clustering with different amounts of pairwise constraint, as shown in Figure 3. The growth of DP values can be barely seen, since the DP values of all amounts of constraint are very high. The ARI and NMI values grow a lot with more constraints provided. In all, SSE performs better with more constraints under most circumstances.