Deep Contrastive Graph Learning with Clustering-Oriented Guidance

In contrastive learning, the selection of positive and negative samples determines the final effect directly. For an anchor $\mathbf{H}_{i}^{v_{1}}$, the universal consensus (Zhu et al. 2021; Liu et al. 2022d) is to treat its embedding in the other branch as the positive sample ($\mathbf{H}_{i}^{v_{2}}$), and all the rest as negative samples, which may misjudges too many samples in the same category as negative. Differently, we employ a rough clustering result to guide the construction of sample pairs. For each anchor, the centroids of other clusters are taken as negative ones.

Specifically, $k$-means is executed on $\mathbf{H}_{i}^{v_{2}}$ to acquire $c$ centroids. Given any node $\mathbf{H}_{i}^{v_{1}}$, the centroids of other clusters constitute the negative sample set $\mathbf{P}^{(i)}\in\mathbb{R}^{(c-1)\times l}$. On this basis, the InfoNCE loss (Oord, Li, and Vinyals 2018) is employed for feature-level contrastive learning

where $\theta(\cdot,\cdot)$ computes the cosine similarity, and $\tau$ is the temperature parameter.

Eq. (6) pushes samples away from incorrect centroids, ensuring the discriminability of the learned representation.

Replacing the $\mathbf{x}_{i}$ in Eq. (1) with the learned $\mathbf{H}_{i}^{{v_{1}}}$, a new graph $\mathbf{S}^{L}$ is derived. This graph learning problem can be converted to trace form as

where $\mathrm{Tr}(\cdot)$ denotes the trace of a square matrix, and $\mathbf{L_{S}}\in\mathbb{R}^{n\times n}$ is the Laplace matrix of $\mathbf{S}^{L}$. The above formulation infers the manifold structure based on the pair-wise similarity, so we term $\mathbf{S}^{L}$ as Local Propinquity Graph (LPG). With a small value of $k$, only the very close samples will be connected, such that the final graph contains fewer incorrect connections. To detect more potential connections, we adopt a staged growth for the neighbor number, which means adding $k$ with a fixed increment after a constant interval.

Contrary to LPG, the new graph encodes the global topological relationship of samples, which requires more links between nodes. Firstly, the structural and attributed nodes are combined to generate a comprehensive representation

Then, the integrated $\mathbf{H}$ is used as the data matrix to construct a graph $\mathbf{G}$ with Eq. (1), which further exploits the original features. The neighbor number for $\mathbf{G}$ is fixed as the upper bound $\left\lfloor{\frac{n}{c}}\right\rfloor$ of the learning procedure of LGP, where $\lfloor{\cdot}\rfloor$ denotes the operation of round down.

Finally, Personalized PageRank graph diffusion (Hassani and Khasahmadi 2020) is introduced to transport the topological similarity through nodes, so as to further capture the global structure. The mathematical expression is

where $\lambda$ is the transport rate, and $\mathbf{D_{G}}\in\mathbb{R}^{n\times n}$ is the degree matrix of $\mathbf{G}$. The corresponding closed-form solution is

where $\mathbf{I_{n}}\in\mathbb{R}^{n\times n}$ is the identity matrix.

$\mathbf{S}^{G}$ is called Global Diffusion Graph (GDG). Compared with the straightforward inner product, the construction of GDG focalizes manifold information of each cluster, rather than the holistic sample space.

With both the local graph $\mathbf{S}^{L}$ and global graph $\mathbf{S}^{G}$, contrastive learning is performed within the cluster space.

We assume that both graphs should share the same cluster structure. To this end, the graphs and embeddings are fed into a siamese GCN to get the cluster indicators

where $\widehat{\mathbf{S}}^{L}$ and $\widehat{\mathbf{S}}^{G}$ are the normalized graphs of $\mathbf{S}^{L}$ and $\mathbf{S}^{G}$. The softmax function is employed to activate the last layer of GCN. In this way, each element of $\mathbf{F}^{v_{1}}\in\mathbb{R}^{n\times c}$ and $\mathbf{F}^{v_{2}}\in\mathbb{R}^{n\times c}$ records the probability that a sample belongs to a cluster. To emphasize the optimization of LPG, both $\mathrm{GCN}_{2}$ and $\mathrm{GCN}_{3}$ use the structural representation $\mathbf{H}^{v_{1}}$ as input.

Then, the cluster-level embedding is calculated as

where $\mathbf{Z}^{v_{1}}\in\mathbb{R}^{c\times l}$ and $\mathbf{Z}^{v_{2}}\in\mathbb{R}^{c\times l}$ consist of the cluster centroids. Eq. (12) projects the cluster indicators into centroid matrices. Afterward, the centroids are used as anchors, and contrastive learning is conducted to search a shared centroid distribution

where

Eq. (13) pushes the centroids of different clusters away, and ensures an explicit cluster structure. The siamese graph convolution module does not involve the initial graph $\mathbf{A}$, so the impact of the initial graph quality is reduced. Moreover, both cluster-level and feature-level contrastive learning employ centroids to leverage cluster structure, and further provide training guidance to facilitate clustering.

Thirteen state-of-the-art clustering methods are applied for performance comparison, including six traditional algorithms $k$-means (Hartigan and Wong 1979), STSC (Zelnik-Manor and Perona 2004), CAN (Nie, Wang, and Huang 2014), PCAN (Nie, Wang, and Huang 2014), RGC (Kang et al. 2019) and GEMMF (Chen and Li 2022), and seven deep models DAEGC (Wang et al. 2019), DCRN (Liu et al. 2022c), DEC (Xie, Girshick, and Farhadi 2016), VGAE (Kipf and Welling 2016b), SpectralNet (Shaham et al. 2018), SUBLIME (Liu et al. 2022d) and AdaGAE (Li, Zhang, and Zhang 2021).

Except for DAEGC and DCRN, the other methods have been attested to be appropriate for non-graph-type data clustering. All codes are downloaded from online resources uploaded by authors.

The hyper-parameters of competitors are set as the recommendations of the authors. For example, the graph regularization weight of GEMMF is searched from $\{10^{1},10^{3},10^{5},10^{7},10^{9}\}$. The probability of dropout layers is from $\{0.1,0.5,0.9\}$. For those methods that require an initial graph, a KNN graph via Gaussian kernel weighting (Cai et al. 2010) is constructed as input, and the number of neighbors is selected from $\{5,6,7,8,9,10\}$.

For DCGL, the hyper-parameters $\alpha$, $\beta$, and $\gamma$ are fixed to $1$, $10^{3}$, and $2\times 10^{3}$ respectively. The neighbor number for LPG rises every 6 epochs. The maximum epoch number is $30$. To ensure objectivity, the random seed is fixed before code execution, and each algorithm is repeated 10 times.

The best clustering results of each algorithm are recorded in Table 2. We summarize the viewpoints that 1) STSC, GEMMF, VGAE, and SpectralNet perform worse than other graph-based methods relatively. They keep the graph structure fixed during iteration, so the final performance is limited by the initial graph quality. This reveals that adaptive graph learning is beneficial to clustering; 2) both DAEGC and DCRN provide unsatisfactory results. These models assume that the initial graph is highly reliable, and learn the cluster embeddings mainly based on the adjacency relation. The experimental results attest that such graph-type data clustering models are not suitable for general clustering tasks; 3) the deep models for general data clustering, i.e., SUBLIME, AdaGAE, and DCGL, realize a noticeable improvement. This verifies the potential of deep graph-based clustering. The good performance of SUBLIME and DCGL also demonstrates the feasibility of contrastive learning on processing non-vision data; 4) DCGL achieves better clustering compared to GCN-based competitors, which reflects the effects of restraining representation collapse and mining the original features. Besides, the difference between DCGL and GAE-based models mainly dates from the siamese graph convolution module that bootstraps a clear cluster structure gradually. With the cooperation of clustering-oriented mechanisms, DCGL is guided to preserve clustering-relevant information, and presents superior performance compared to other algorithms.

Define DCGL-w/F and DCGL-w/C as the DCGL variants without feature-level and cluster-level contrastive learning respectively. Since the outputs of $\mathrm{GCN}_{2}$ and $\mathrm{GCN}_{3}$ are only related to cluster-level contrastive learning, DCGL-w/C means the entire expurgation of the siamese graph convolution module. Table 3 shows the ablation comparisons. Obviously, DCGL still presents the best clustering performance, which proves the effectiveness of each contrastive learning strategy.

The performance of DCGL-w/F is deteriorated compared to DCGL, which demonstrates the discriminability of the embeddings learned by DCGL. For a better illustration, we calculate the cosine similarity matrix of the data representation from $\mathrm{GCN}_{1}$. The heatmap on Pie is displayed in Fig. 3, where only the large values are preserved to facilitate observation. In the result of DCGL, the nodes across diverse classes have lower similarity, so we can conclude that feature-level contrastive learning is beneficial to improving discriminability.

DCGL exceeds DCGL-w/C on all benchmark datasets, which means the graph generated by DCGL maintains a clearer cluster structure. To verify the efficiency of cluster-level contrastive learning on graph optimization, we plot the converged LPGs from DCGL-w/C and DCGL on ORL in Fig. 4, where all non-zero elements are substituted with 1 to emphasize the adjacency relation. It can be seen that the graph obtained by DCGL exhibits a more distinct block diagonal structure, indicating more links between samples of the same category.

In the proposed contrastive learning strategies, feature-level and cluster-level guidance are introduced into the construction of sample pairs and the selection of anchors. To investigate the effectiveness of the above clustering guidance, we design three variants of DCGL with different contrastive learning approaches, termed as DCGL-w/Fg, DCGL-w/Cg, and DCGL-w/all. Among them, DCGL-w/Fg discards the feature-level guidance, and regards all non-corresponding nodes of the anchor in the other branch as negative samples in feature-level contrastive learning. DCGL-w/Cg removes the cluster-level guidance by taking the output embeddings of $\mathrm{GCN}_{2}$ and $\mathrm{GCN}_{3}$ as anchors directly. DCGL-w/all has the above two alterations.

Fig. 5 presents the comparison results. We can deduce that 1) the evident degradation of DCGL-w/all confirms the significance of clustering guidance; 2) the decline of DCGL-w/Fg implies that the discriminability is decreased without the feature-level guidance; 3) the disparity between DCGL-w/Cg and DCGL demonstrates that contrastive learning within the cluster space is helpful to perceive a clear cluster distribution.

Finally, we focus on the influence of trade-off parameters $\alpha$ and $\beta$. We tune both $\alpha$ and $\beta$ over the range of $\{10^{-3},10^{-2},10^{-1},1,10^{1},10^{2},10^{3}\}$, and keep other experimental environments. Fig. 6 exhibits the clustering ACC of DCGL with different parameter combinations. It is observed that 1) the performance under too small $\alpha$ and $\beta$ is not outstanding, which manifests the failure of related mechanisms, and again attests to the effectiveness of the designed modules; 2) the influence of $\alpha$ is more salient relatively, because $\alpha$ is associated with graph learning and the final cluster partitioning directly; 3) the setting of moderate $\alpha$ and larger $\beta$ is likely to bring satisfactory clustering results. Overall, DCGL is not particularly sensitive to parameter selection in an appropriate range.