Multi-Task Curriculum Graph Contrastive Learning with Clustering Entropy Guidance

1 Introduction

In recent years, the representational capacity of graph data has made it prevalent in various applications, including social networks [Majeed and Rauf, 2020; Newman et al., 2002], knowledge graphs [Ji et al., 2021], and traffic prediction [Zhao et al., 2019; Li et al., 2023]. The prevalence has been further amplified by the emergence of deep graph neural networks [Kipf and Welling, 2016a; Veliˇckovi´c et al., 2017], which has enabled the efficient analysis of complex graph data. Specifically, unsupervised deep graph learning

∗Corresponding author.

[Wang et al., 2021b; Liu et al., 2022a; Mo et al., 2022; Chen and Li, 2022] has garnered extensive research interest due to its ability to extract discriminative, and interpretable graph features.

Graph contrastive learning is a fundamental paradigm within the field of unsupervised graph learning, and consists of two parts including graph augmentation and contrastive learning. Data augmentation changes the original data graph to obtain multiple views with similar semantics, thereby expanding the selection space of positive and negative sample pairs [Xu et al., 2024; Wang et al., 2021c]. For example, many data augmentation methods select the nodes and edges randomly, and delete/mask/disturb them to produce an augmented graph [Zhu et al., 2020; You et al., 2020]. Contrastive learning enhances the similarity of samples with related semantics, while pushing samples with low relevance away from each other. The above process helps to learn graph embeddings with high discriminability, which in turn reveals the implicit structure of the data. The early methods [Hjelm et al., 2019; Veliˇckovi´c et al., 2018] take the noncorresponding nodes among views as negatives, which can mistakenly pull many intra-class samples far apart, resulting in sampling bias. Some recent methods [Lin et al., 2022; Zhao et al., 2021] have attempted to improve the selection strategies for positive and negative samples, adopting specific strategies to select more appropriate positive and negative samples, such as taking the intra-class nodes as positives and the inter-class nodes as negatives.

Existing methods for graph contrastive learning often encounter difficulties when dealing with complex data. On the one hand, the widely used random graph data augmentation methods [Fang et al., 2023] can potentially remove intra-class edges and mask features essential for representing the class. Unlike ideal augmentation, this approach can disrupt the graph structure critical to clustering, thereby limiting the performance of contrastive learning frameworks. On the other hand, most methods adopt the fixed strategy to select positive and negative samples throughout the training process, which is not flexible in practical applications. For example, two common strategies for positive/negative samples selection in contrastive learning are: using corresponding samples from other views as positives and treating all others as negatives [Zhu et al., 2020; You et al., 2020; ?], or using pseudo-labels generated during training to define positive and negative samples [Yang et al., 2023; Lin et al., 2022; Xia et al., 2022]. The first approach focuses on learning the discriminative features for each node. However, taking all non-corresponding samples as negatives hinders intra-class compactness. The second approach employs pseudo-labels generated by simple clustering methods to select positive/negative samples, which may be unreliable in the early stages due to the insufficient discriminability of the learned embeddings. The limitation of fixed strategy hinders the model's ability to explore the intrinsic representation and complex topological relationship, potentially leading the model to converge to a suboptimal solution for clustering.

To alleviate the above problems, we propose clusteringguided Curriculum Graph contrastive Learning (CurGL) framework. As shown in Fig. 1, the intermediate results of the model are clustered to calculate the clustering entropy, which serves as a clustering guidance for the whole framework. On this basis, a clustering-friendly strategy is adopted for performing structure-level and feature-level data augmentation. Then, the multi-task curriculum learning scheme uses clustering entropy to determine the clustering confidence of samples and place them in different contrastive learning tasks. As training progresses, samples are transited from the early stage simple discrimination task to the more challenging clustering task in the late stages, such that the flexible adjustment of sample selection is achieved. The main contributions of this paper are as follows.

• A clustering-guided graph contrastive learning framework is established. The clustering entropy is defined to serve as the clustering guidance, which is used to evaluate the importance and clustering confidence of nodes throughout the whole framework.
• A clustering-friendly graph augmentation method is proposed. Under the clustering guidance, structure augmentation tends to preserve intra-class edges, while feature augmentation is more likely to retain the class-specific features.
• A multi-task curriculum learning scheme is developed to explore the complex data structure. It allows the model to first learn discriminative representations of the samples and then move towards clustering optimization. The dynamic contrastive learning effectively enhances the capability to capture cluster-oriented discriminative features.

2 RelatedWork

2.1 Graph Contrastive Learning

After making progress in image recognition[Zbontar et al., 2021; Wang and Qi, 2022], contrastive learning combined with Graph Neural Networks (GNNs) has also garnered significant attention from many researchers. Explorations in graph contrastive learning have primarily concentrated on graph augmentation technologies and contrastive objectives.

Data augmentation enriches the diversity of training samples by generating different views. MVGRL [Hassani and Khasahmadi, 2020] and DCRN [Liu et al., 2022b] utilize graph diffusion to create augmented views, while methods like GRACE [Zhu et al., 2020] and SCAGC [Xia et al., 2022] achieve this through random attribute and edge perturbations. Most augmentation techniques are often stochastic and uncontrollable, potentially disrupting semantics and cause noise. Recently, several adaptive augmentation methods [Zhang et al., 2024] have been proposed. GCA [Zhu et al., 2021] learns the weights of discarding adaptively, with the expectation that the model's final learned representations will be insensitive to unimportant nodes or edges. However, It is not necessarily suitable for downstream clustering tasks. CurGL is designed with clustering as the objective, aiming to obtain augmented views that better align with the underlying clustering structure.

Contrastive objective learns the embedding by constructing pairs of positive and negative samples. MVGRL designs an InfoMax loss to maximize the cross-view mutual information between nodes and the global summary of the graph. AGE[Cui et al., 2020] devises a pretext task, using a cross-entropy loss to classify similar and dissimilar nodes. Based on k-Means or other graph-based clustering methods[Wang et al., 2021a], some methods[Lin et al., 2022; Yang et al., 2023] use intermediate clustering results to guide the contrast objective. CurGL designed two types of contrastive objectives to tackle tasks of varying difficulties, and we employ curriculum learning to tailor the tasks for each node based on the model's current learning state.

2.2 CurriculumLearning

Curriculum learning [Bengio et al., 2009; Wang et al., 2021d] is a training strategy that mimics the human learning process. It allows the model to start with simpler samples and gradually progress to more complex ones, as well as to advanced knowledge. Some studies [Jiang et al., 2018; Han et al., 2018] have theoretically demonstrated the effectiveness of curriculum learning in enhancing generalization capabilities when dealing with noisy data. Curriculum learning is widely applied across various areas of machine learning[Zbontar et al., 2021] and deep learning[Matiisen et al., 2019; Graves et al., 2017].

Curriculum Learning consists of two main parts: difficulty measurer and training scheduler[Hacohen and Weinshall, 2019]. The difficulty measurer is used to evaluate the difficulty of the sample. Predefined difficulty measurer [Platanios et al., 2019; Spitkovsky et al., 2010; Tay et al., 2019] is mainly designed manually according to the data characteristics of a specific task. The training scheduler determines the appropriate training data to feed into the model based on the evaluation results of the difficulty measurer. But existing predefined training schedulers[Cirik et al., 2016] are usually data and task independent, and most curriculum learning in various scenarios uses a similar training scheduler. The discrete scheduler adjusts the training data at each fixed round or when the current data converges, while the continuous scheduler adjusts the training data at each round according to a defined scheduling function. Different from the general curriculum learning that only controls the number of sample participation, CurGL lets samples perform tasks of different difficulty at different stages of the model, which considers the difficulty distribution of samples.

Clustering Guidance Module

Multi-Task Contrastive Learning

3 Methodology

In this section, we will provide a detailed introduction to the proposed CurGL method. The overall pipeline of CurGL is shown in Fig. 1.

3.1 Notations and ProblemDefinition

In this paper, uppercase letters represent matrices and lowercase letters represent vectors. An undirected graph with n nodes is defined as G = {X,A}, and X ∈ Rn×d is the original feature matrix of the nodes, A ∈ Rn×n represents the adjacency matrix of the graph data.

This paper aims to address an unsupervised graph clustering problem. Specifically, given a graph G = {X,A}, the task is to train a GCN encoder such that Z = f(X,A), and the resulting Z can be used to cluster all nodes V of the graph G into k classes.

3.2 Clustering Guidance Module

The clustering guidance module is introduced to make the learned embeddings more suitable for clustering tasks. Clustering entropy is defined to guide subsequent augmentation and contrastive learning. It also serves as a loss function to improve the quality of pseudo-labels.

Given the original graph data G = {X, A} and embedding Z1 computed by GCN, performing k-Means on Z1 results in k cluster centroids C = {{c1}, {c2}, . . . , {ck}} and pseudolabels L of the samples. Then, we calculate the probability assignment matrix P by

where Z1 · CT calculates the dot product similarity between each sample and the cluster center, the softmax(·) performs exponential normalization of each row of Z1 · CT to obtain the probability assignment matrix P ∈ Rn×k . Each row of P represents the probability that the corresponding node is assigned to all the centroids.

To assess the quality of the clustering, we propose the clustering entropy

Ei indicates the uncertainty of the probability distribution for each node. Nodes with high Ei have probabilities that are relatively close to each cluster centroid, indicating a lower confidence in the clustering. Conversely, nodes with low Ei have a higher confidence in clustering. For better clustering, the samples with high confidence should increase during the training procedure, such that a low clustering entropy can be achieved. Therefore, a clustering entropy loss is designed to optimize the clustering effect, defined as

Optimizing LEN can drive the learned embedding Z to reveal a clear cluster structure, and provide more reliable clusteringoriented guidance for the subsequent modules.

3.3 Clustering-Friendly Augmentation

In this part, we design a clustering-friendly augmentation method, which consists of structure augmentation and feature augmentation. They preserve edges between nodes of the intra-class and important features that are beneficial for the clustering task respectively.

Structure Augmentation. Each edge is assigned with an importance weight to determine its probability of being deleted, which can be formulized as

where uij e represents the importance measure between nodes i-th and j-th. The indicator function δ(Li - Lj , 0) is 0 when Li = Lj and 1 otherwise. The meaning of uij e is that when the nodes at both ends of the edge have low clustering entropy and belong to the same class, the value of uij e is relatively smaller, indicating a higher importance of the edge, and thus a lower probability of being removed. After normalization, the probability of each edge being removed is obtained, and the normalization method is given by

where umax e and ¯ue are the maximum and average values of ue respectively. pe is the overall edge deletion probability, and pτ is the truncation probability, which is used to prevent the deletion probability of certain edges from being too high.

The structure augmentation emphasizes the edges that connect reliable nodes of the same class. As a result, important clustering-relevant semantic information is preserved.

Feature Augmentation. Feature augmentation aims to preserve the representative class-specific features. For one-hot encoded features, 1 indicates the presence of a feature, while 0 indicates its absence, the frequency of each feature appearing in nodes within the same class reflects the importance of that feature. Therefore the feature weight for the j-th class fj can be defined as

For features that are not one-hot encoded, the distribution of features within the class can also be used to obtain fj. If the distribution of a feature is more concentrated among the samples within a class, it will have a higher feature weight fj, which can be determined by statistical measures such as variance.

We can obtain the probability that each feature within each class is masked by normalizing fj ,

where pf is the overall probability of feature augmentation and pτ is the truncation probability.

The augmentation approach emphasizes important features within each cluster, which makes it more convenient to judge the subordinate cluster of each sample. Features irrelevant to clustering are more likely to be removed to reduce noise.

3.4 Multi-Task CurriculumLearning

The multi-task curriculum learning scheme is proposed to deal with complex real data. In order to simulate the realworld knowledge learning process, samples should start with simple contrastive task and gradually turn to complex contrastive task. In the early stages of training, the embeddings are not discriminable, and unsuitable for clustering. Therefore, we start from the discrimination task, and gradually transition towards the clustering task.

Self-Paced Curriculum Learning. In each training iteration of the model, we categorize samples into low-confidence and high-confidence groups to perform the discrimination and clustering task, respectively. A self-paced curriculum learning is used to achieve automatic transformation of tasks according to the clustering entropy.

To distinguish the confidence of samples, we define a indicator vector v ∈ {0, 1}n , where vi = 0 denotes that the i-th sample belongs to the low-confidence group. Self-paced curriculum learning assigns the contrastive task to samples by controlling each element in the indicator vector v. Given n samples, we define ntCT as the number of samples in the model at the t-th epoch iteration that are selected to perform the clustering task. The samples are chosen based on their ranking in clustering entropy, and their corresponding elements in the indicator vector v are set to 1. Moreover, nDT is the number of samples that perform discrimination task, and nCT +nDT = n. Curriculum pace ε is defined to control the number of high-confidence samples. With the total number of iterations T, the nt+1 CT is computed as

When ε reaches 1, all samples participate in the clustering task, the nCT will not increase any more.

Discrimination Task. The purpose of discrimination task is to distinguish each sample individually and learn clear self-representations. Since the discrimination task does not consider the topological relationships between samples, it is regarded as a relatively simple task. Samples in the lowconfidence group do not exhibit well-defined clustering structures, so we assign them to perform the discrimination task.

To push nodes apart in the embedding space, the positive and negative sampling corresponding to the discrimination task is that the positive sample is the augmented view of the sample itself, while the negative samples are all other nodes. For zi, the discrimination task loss is

where zj i denotes the i-th node in the j-th view, τ is the temperature parameter, S(·) is the similarity calculation function. The overall discrimination task loss can be expressed as

By minimizing LDT , the low-confidence sample gradually captures the key internal features, resulting in a more discriminative embedding. As the discriminability improves, the topological relationship becomes more clear, and the samples gradually transform into high-confidence ones. Then, they can participate into the clustering task.

ClusteringTask. Once the samples in the embedding space exhibit sufficient discriminability, the pseudo-labels and - centroids obtained by k-Means become more reliable. Therefore, we can consider the complex topological relationships between samples, aiming to push the intra/inter-class nodes close/disperse for clustering improvement.

For the clustering task, the selection strategy for positive and negative samples is as follows: positive samples are defined as the cluster centroid of the sample and its own augmented view, while negative samples are the centroids of other clusters. For zi, the clustering task loss is

where ci is the pseudo-centroid corresponding to zi. Pulling nodes closer to their centroids and pushing them away from other centroids is beneficial to accelerate a clear clustering distribution. The overall loss of clustering contrastive task is

By minimizing LCT , the node features with sufficient discrimination after discrimination task learning further show the clustering structure and facilitates clearer clustering separation.

Through the above task transition, the positive and negative sampling strategy gradually changes from considering only the node itself to mining the cluster structure, thus leveraging the clustering information to guide contrastive learning. The progression from easy to challenging tasks enables our method to consistently learn clustering-oriented discriminative features.

3.5 Joint Loss and Optimization

Combining Eqs. (3), (9), and (11) , the joint loss is

where α, β and γ are hyper-parameters.

The loss of the model can be considered as a function of the model parameters W and the indicator vector v, which can be expressed as L = g(W, v). To optimize the objective function, we use an alternate optimization algorithm to iteratively update both. Specifically, v is first initialized as an all-zero vector, which means that all nodes perform the discrimination task at the beginning of the model training. Perform the following two steps alternately until the final iteration.

Firstly, fix vt and solveWt+1 by

The model parameters Wt+1 can be solved using the Adam optimizer.

Secondly, fix Wt and solve indicator vector vt+1 according to the cluster entropy E

where ntCT initially starts at 0 and increases with the curriculum pace ε. ∥v∥1 is the L1 norm of the vector. As nCT increases, the indicator vector v will eventually become an all-ones vector, meaning that all nodes will participate in the clustering task.

4 Experiments

4.1 Benchmark Datasets

To substantiate the efficiency of the CurGL, fix publicly accessible real-world datasets are adopted as benchmarks, including CORA, UAT, PUBMED, AMAP, and AMAC. The datasets are collected from a range of domains such as air traffic, academic citation, and shopping networks. Further details regarding these datasets are shown in Table 1.

4.2 EvaluationMetrics

The clustering result is evaluated with three well-known metrics, including Accuracy (ACC), Normalized Mutual Information (NMI), and Average Rand Index (ARI). All metrics are positively correlated with clustering performance, and the range is [0, 1].

4.3 Comparison with Competitors

Ten state-of-the-art node clustering algoritms are selected for comparative analysis. This evaluation encompasses a range of approaches, from the traditional k-Means algorithm to advanced GCN-based deep models, such as GAE [Kipf and Welling, 2016b], DAEGC [Wang et al., 2019], and SDCN [Bo et al., 2020], as well as contrastive learning-based techniques including GCA [Zhu et al., 2021], SCAGC [Xia et al., 2022], CCGC [Yang et al., 2023], DCGL [Chen et al., 2024], DCRN [Liu et al., 2022b] and HSAN [Liu et al., 2023].

Setups. The k-Means algorithm only utilizes the original node attributes as input. In contrast, other baseline methods use both the original node attributes and the topological graph. The hyper-parameters for each competitor are configured according to the recommendations provided in the original papers. For the proposed CurGL, we use the adaptive hyper-parameter selection, which means α = ∥v∥1 N and β = 1-α. Additionally, a parameter grid search is conducted for γ. The advantage of this approach is that α will increase as the number of nodes involved in the clustering task grows, while β for the discrimination task will correspondingly decrease.

To ensure a fair comparison, each algorithm is executed 10 times to report the average. All deep models are trained with a NVIDIA RTX-4090 GPU.

Performance Comparison. Table 2 displays the average clustering performance of all algorithms. In general, the proposed CurGL outperforms other advanced methods, and achieves the best clustering results on all datasets, which indicates the practicability of CurGL on various graph clustering scenarios. From the experimental results, we also summarize the following viewpoints. Firstly, all GCN-based methods surpass k-Means on attributed graph clustering, which manifests the advantage of GCN on graph data mining. GCNbased deep models process the node attributes and the topological structure information simultaneously, so as to detect the internal data distribution more precisely. Secondly, benefiting from the efficient data augmentation techniques, GCNbased models outperform the traditional graph auto-encoder framework. The augmented view provide a more extensive semantic space for presentation learning, so as to improve clustering. Thirdly, compared to contrastive learningbased baselines, CurGL introduces the clustering guidance to improve the graph augmentation, which makes the augmented views more suitable for the downstream clustering task. Fourthly, unlike existing clustering-oriented methods such as CCGC, SCAGC, and HSAN, the proposed CurGL adjusts the contrastive learning task based on the learning state of the samples, alleviating the issue of unreliable pseudolabels in the early stages.

4.4 Ablation Study and Analysis

In this part, the ablation study is conducted to verify the effectiveness of the new mechanisms. Three variants of CurGL are designed, including wo/CL, wo/CE, wo/CUd and wo/CUc. Specifically, in wo/CL, the cluster-friendly graph augmentation is substituted with random data augmentation. In wo/CE, the clustering entropy loss is suspended. Furthermore, in wo/CUd and wo/CUc, the curriculum learning mechanism is suspended, allowing nodes to execute fixed contrastive learning during model training. wo/CUd represents that all nodes only perform the discrimination task, and wo/CUc represents that all nodes only perform the clustering task. Table 3 gives the ablation comparison on five datasets. It can be seen that CurGL still presents the best clustering scores, which proves the effects of the new modules on graph clustering. Furthermore, Fig. 2 shows the visualization results of the embeddings. CurGL obtains the best sample distribution with a clear cluster structure. The structure learned by wo/CUc is unclear because only discriminative features of samples are learned. wo/CUd fails to capture the discriminative features, so some inter-class samples are grouped incorrectly.

Impact of Augmentation probability. The augmentation probability determines the difference between the two views during contrastive learning. The edge deletion probability pe and feature masking probability pf control the intensity of structure and feature augmentation respectively. Fig. 3 shows the impact of different combinations of these two factors on clustering performance. It can be observed that when the augmentation probability is low, the data differences between the two views are very small. In this case, the selection space for positive and negative samples is limted, making it difficult to learn robust representations. On the other hand, when the augmentation probability is too high, the augmented views are excessively perturbed, where critical structures and features are damaged and original semantic information is lost.

Impact of CurriculumPace. The curriculum pace ε determines the learning speed. When ε = 1, the model iterates to the last epoch, and exactly all nodes are transferred to the clustering task. When ε > 1, all nodes are transferred to the clustering task before the end of training. Fig. 4 shows the effect of curriculum pace. The clustering performance reaches the optimal when 1 < ε < 2. The results are consistent with our original intention, as it tries to perform the clustering task for a period of epochs after all nodes complete the discrimination task. Too large curriculum pace also leads to poor clustering, since the sample is transferred to the clustering task prematurely without a discriminative embedding. The experimental result testifies the feasibility of multi-task contrastive scheme.

Impact of Task Ratio. We remove the curriculum learning mechanism and fix the sample ratio of the two tasks to investigate the influence. When the task ratio is 0, all nodes only perform the discrimination task during the entire model training. When the task ratio is 1, all nodes engage in the complex clustering task. The results are visualized in Fig. 5. Obviously, relying solely on either the discrimination task or clustering task yields sub-optimal performances. The discriminanation task neglects the clustering guidance, and the clustering task suffer from the accumulation of adverse noise in pseudo-labels. Compared to performing a single task (i.e., task ratio is 0 or 1), multi-task learning with a fixed sample ratio can improve clustering effects, but it is still not as effective as CurGL with adaptive task allocation. To sum up, the adaptive adjustment of discrimination and clustering tasks is beneficial to learning clustering-friendly graph embedding.

5 Conclusion

In this paper, we establish a clustering-guided Curriculum Graph contrastive Learning (CurGL) framework. Clustering entropy is defined based on the embeddings to serve as the clustering guidance. After that, a clustering-friendly augmentation strategy is developed for structure-/feature-level graph augmentation, which avoids the noise brought by random augmentation. In addition, the proposed multi-task curriculum learning scheme performs contrastive learning on discrimination task in the early stage, and turns to clustering task in the late stage. The flexible transition strategy adjusts the sample selection strategy adaptively during the training process, and is more suitable for data with complex distribution. The efficiency of our method has been validated by a series of comprehensive experiments. In the future, we plan to extend CurGL to multi-view graph learning.

Acknowledgments

This work was supported by the National Key Research and Development Program of China (Grant No:2022ZD0160803).